SWING: Small World Iterative Navigation Greedy Routing Protocol in MANETs

Routing is the foremost issue in mobile ad hoc networks (MANETs). In a wireless environment characterized by small bandwidth and limited computational resources, position-based routing is attractive because it requires little communication and storage overhead. To guarantee delivery and improve performance, most position-based routing protocols, e.g. GFG, forward a message in greedy mode until the message is forwarded to a node that has no neighbor closer to the destination, which is called a local minimum. They then switch to a less efficient mode. Face routing, where the message is forwarded along the perimeter of the void, is one example. This paper tackles the void problem with two new methods. First, we construct a virtual small world network by adding virtual long links to the network to reduce the chance of a protocol encountering local minima in greedy mode, and thus decrease the chance to invoke inefficient methods. Second, we use the virtual force method to recover from local minima without relying on face routing. We combine these two methods to be our new purely greedy routing protocol SWING. Simulation shows that SWING finds shorter routes than the state of art geometric routing protocol GOAFR, though with a longer route establishment time. More importantly, SWING is purely greedy which works even if position information is inaccurate, also it can be directly applied to the 3D MANET models. A theoretical proof that it guarantees delivery is given.