Grid-based geographic routing for mobile ad-hoc networks

This thesis investigates geographic routing in mobile ad hoc networks. In geographic routing, each node knows the position of one-hop neighbors, and packets are forwarded to a neighbor that is closer to the destination. This simple forwarding strategy fails when there are obstacles such as voids or physical obstructions that prevent radio communications between nodes. Then, a recovery procedure is used to get around the obstacle. Earlier recovery techniques require that nodes know the exact position of other nodes. However, inexpensive position devices do not provide sufficient accuracy for these algorithms and it is difficult to obtain the information on moving nodes.; Our approach to geographic routing begins with an observation that, if nodes know the shape and position of obstacles, they can make better routing decisions so that packets can avoid the obstacles in advance. A challenge is that obstacles in networks have complex shapes and change as edge nodes move. Our engineering solution is to partition the network into a grid and represent the obstacles on the grid map. The grid approximation represents obstacles by grid edges that are convenient to use and rarely affected by small movements of nodes. This thesis presents geographic shortest path routing that uses the obstacle map to follow the geographic shortest path.; In addition, the grid partitioning of a network naturally aggregates nodes into non-overlapping grid cells. The mobile network can be modeled as a fixed pattern network of occupied grid cells. The grid cells do not move but may change their state between "on" and "off" according to their occupancy. The occupancy of a grid cell depends on not the mobility of nodes but the density of nodes. As node density increases, grid cells become more stable. Based on this idea, we design a recovery algorithm that is robust against mobility and location errors. The novel recovery algorithm eliminates the need for the planarization of networks, which earlier recovery techniques have used, by taking advantage of the grid structure. The thesis also presents simulation results that evaluate grid-based routing and compare it with conventional position-based routing.