Abstract
In wireless ad-hoc networks, routing is an important issue regardless of the existence of geographic information. Virtual neighbor is usually used to construct a connection between two nodes each of which is not a neighbor of the other in the network. In this dissertation, I undertake the development of virtual-neighbor-based routing protocols in wireless ad-hoc networks. In the first part of the dissertation, I propose a virtual-neighbor-based scheme capable of augmenting GPSR-like routing protocol to reduce routing path length in wireless ad-hoc networks where each node has the geographic information. I first propose an algorithm to construct the virtual neighbor set (called the progress set for specificity) of each local minimum, such that for any destination at least one progress node is in the progress set or the neighbor set of the node. Subsequently, the ProgressFace algorithm is presented to route a packet based on progress sets during perimeter forwarding. Simulations show that GPSR, GFG, GOAFR+, and GPVFR each conduct a shorter routing path, if augmented with the ProgressFace algorithm. In the second part, since geographic information is obtained with difficulty and a wireless ad-hoc network usually has unidirectional links, I propose a virtual-neighbor-based scheme (ABVCap_Uni) to assign virtual coordinates to nodes that have no geographic information in wireless ad-hoc networks with unidirectional links, and I propose a routing protocol based on the ABVCap Uni virtual coordinates. The proposed routing protocol guarantees packet delivery without computation and storage of global topology features in a discrete domain. Using simulation, I evaluate the performance of the proposed routing protocol (ABVCap_Uni Routing), the greedy landmark-descent routing protocol (GLDR+VLM routing), and the greedy routing protocol based on geographic information (Euclidean routing). The simulations demonstrate that the proposed routing protocol ensures moderate routing path length cost overhead.