UC Santa Cruz

A wireless network is any type of computer network that uses wireless communication links for connecting network nodes. There are two major types of wireless networks: one is infrastructure-based which is centralized and managed by at least one wireless access point (AP) to maintain the connections between all other nodes. The other type is self-configuring infrastructureless which is independent of AP and

node communicate each other directly without requiring centralized management, for instance, Ad hoc Network. A Mobile Ad-hoc Nework(MANET) is consisted of mobile nodes which can change geographic positions randomly in any directions. MANET

usually has a routable networking environment on top of a Link Layer ad hoc network.

In mobile ad hoc networks, each node randomly moves with various velocity and has no knowledge of other node's location. Before data is transmitted between nodes, each node is required to establish a path from source to destination which is so-called Routing. It may have multiple paths between source and destination. The path can be one-hop or multiple-hop. One-hop is referred to adjacent neighbors within a fixed radio distance. Imagine an undirected graph G={V,E} , there are multiple paths between pairs of vertices and each vertex obtains a path to other vertex so that it effectively arrives to destination vertex.

In this dissertation, we study multiple distributed routing strategies for MANET. The major contributions are to mitigate routing overhead with the guaranty of covering all nodes in MANET and no knowledge of the geographical locations of destinations are required. All protocols are adaptive to the scenarios of independent of network mobility,

cardinality of network and number of neighbors. It is noteworthy to mention that in experiemental study, for the purpose of the best observation, the set of scenarios is relatively selective to maintain the well established connected networks. The proportion of the size of terrains and the density of networks must be reasonable, which is not too dense or too sparse so that the performance is able to show more explicitly.

First, we propose a novel directional routing scheme Dircast: Floodingreduced routing in MANET without destination coordinates [34] for which address the flooding problems that played many routing protocols designed in MANET. Dircast assumes that each node knows its own geographical coordinates and nominates the limited

number of relay nodes at each hop to proceed routing discovery. The selected relay nodes have the shortest distance to all boundary vertices so that the span of routing can be extended to a maximal degree. Message complexity of Dircast is O(C) ≍ O(1), regardless of density of network and the number of neighbors of nodes.

Second, we introduce a new methodology ORCA: On-demand Routing with Coordinates Awareness [36], using geographical coordinates to attain efficient route signaling in MANET . The selection of relaying nodes at each node in ORCA is done by computing the shortest Euclidean Distance from all neighbors of the node to four

polar points located in the transmission range of the node. ORCA is capable to cover all nodes in a connected MANET and the maximal number of relay nodes at each hop is six. Message complexity of ORCA is O(C) ≍ O(1), regardless of density of network and the number of neighbors of nodes.

Third, we develop an innovative protocol ORTHCA: On-demand Routing

with Two Hop Coordinates Awareness for minimizing dissemination of routing overhead with two-hop coordinate awareness in MANET [35]. The selection of relaying nodes is implemented as follows: firstly computes the best two hop relay nodes R2(u), whose

Euclidean Distance to four polar points are the shortest among all two hop neighbors N2(u); then determines one hop relay nodes R1(u) connecting with R2(u). This process is iterated only by each member of R2(u). Message complexity of ORTHCA is O(C) ≍

O(1), regardless of density of network and the number of neighbors of nodes.

Fourth, we present CBORCA: A Cluster Based ORCA Routing Protocol in

MANET, by eliminating the redundant relay nodes and creating overlapping clusters to guarantee full coverage in MANET. This algorithm exploits the advantages of cluster's properties and achieves the enhanced performance better than ORCA. It divides the network into multiple overlapping clusters and select cluster head set H(u) by extracting a limited number of relay nodes from a given relay node set R(u) of the node. The selected cluster heads are the only relay nodes to forward routing requests. Both theoretical analysis and experimental simulation have proved message complexity is a constant number O(C) ≍ O(1), regardless of density of network and the number of

neighbors of nodes.