Article Preview
Top1. Introduction
Mobile ad-hoc network (MANET) is a network without infrastructure; it consists of a group of wireless mobile nodes that can communicate with each other wirelessly. A mobile node X in MANET can communicate directly only with the nodes inside a virtual sphere centered at X of radius R (the transmission range). To communicate with nodes outside its transmission range, multi-hop routing is used utilizing intermediate communicating nodes. Since mobile ad-hoc networks may change their topology frequently and because of the resource constraints, routing in such networks is difficult. Numerous routing algorithms for MANET have been proposed to address the multi-hop routing problem.
In general, Ad hoc routing algorithms can be classified in two basic types: static routing and online routing. Static routing algorithms use a predefined route among the network hosts using the information about the virtual links in the network (Basagni, Chlamtac, Syrotiuk, & Woodward, 1998; Choi & Das, 2002; Johnson & Malts, 1996; Perkins & Royer, 1999).
Online routing algorithms use the nodes (source, destination, and neighbors) geometric locations to forward the packets in the direction of the destination (Mauve, Widmer, & Hartenstein, 2001; Takagi & Kleinrock, 1984; Barriere, Fraigniaud, Narayanan, & Opatrny, 2003; Kranakis, Singh, & Urrutia, 1999; Fin, 1987; Abdallah, Fevens, Opatrny, & Stojmenovic, 2010; Abdallah, Fevens, & Opatrny, 2008; Giordano, Stojmenovic, & Blazevic, 2003; Bose, Morin, Stojmenovic, & Urrutia, 2001; Bose & Morin, 1999; Fevens, Abdallah, & Bennani, 2005). In Greedy routing (Chvatal, 1979; Johnson, 1974; Slavik, 1996), a node forwards the packet to one of its neighbors that minimize the Euclidean distance to the destination. Directional routing (Kranakis et al., 1999), the current node forwards the packet to one of the neighbors that minimize the angle between current node, next node, and destination. Clearly, Greedy and directional routing fail to deliver the packet at local minimum (when there is no way to progress any more). The problem has been solved in 2D, using what is called perimeter routing or face routing (Bose et al., 2001; Karp & Kung, 2000; Frey & Stojmenovic, 2006; Bose & Morin, 1999). Perimeter routing can be explained as follows:
- 1.
Nodes locally use their geometric locations to extract a planar sub-graph i.e. Gabriel graph (GG) (Gabriel & Sokal, 1969) or Relative Neighborhood Graph (RNG) (Jaromczyk & Toussaint, 1992);
- 2.
Perimeter routing traverses in a counter clockwise the faces of GG that cross the virtual line between the source and the destination;
- 3.
The algorithm switches between faces, when the packet reaches an edge that crosses the virtual line between the source and the destination at a point closer to the destination than any previously known intersection point. It has been proved that perimeter routing has a guaranteed packet delivery.