Cluster-Based Online Routing Protocols for Ad Hoc Network

Cluster-Based Online Routing Protocols for Ad Hoc Network

Alaa E. Abdallah, Mohammad Bsoul, Emad E. Abdallah, Ibrahim Al–Oqily, George Kao
DOI: 10.4018/ijitwe.2014100105
(Individual Articles)
No Current Special Offers


In geographical routing algorithms, mobile nodes rely on geographical position to make routing judgments. Researchers frequently discuss such routing algorithms in (2D) space. However, in reality, mobile nodes spread in (3D) space. In this paper the authors present four new 3D geographical-based routing algorithms Cylinder, Greedy-Cylinder, Cluster-Cylinder, and Greedy-cluster-Cylinder. In Cylinder routing, the nodes are locally projected on the inner surface of a cylinder, perimeter routing is executed after that. Greedy-Cylinder starts with Greedy routing algorithm until a local minimum is reached. The algorithm then switches to Cylinder routing. Cluster-Cylinder elects a dominating set for all nodes and then uses this set for projection and routing. The fourth algorithm Greedy-cluster-Cylinder is a combination between Greedy-Cylinder and Cluster-Cylinder. The authors evaluate their new algorithms and compare them with many classical known algorithms. The simulation outcomes show the substantial enhancement in delivery rate over other algorithms.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Volume 19: 1 Issue (2024)
Volume 18: 1 Issue (2023)
Volume 17: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 16: 4 Issues (2021)
Volume 15: 4 Issues (2020)
Volume 14: 4 Issues (2019)
Volume 13: 4 Issues (2018)
Volume 12: 4 Issues (2017)
Volume 11: 4 Issues (2016)
Volume 10: 4 Issues (2015)
Volume 9: 4 Issues (2014)
Volume 8: 4 Issues (2013)
Volume 7: 4 Issues (2012)
Volume 6: 4 Issues (2011)
Volume 5: 4 Issues (2010)
Volume 4: 4 Issues (2009)
Volume 3: 4 Issues (2008)
Volume 2: 4 Issues (2007)
Volume 1: 4 Issues (2006)
View Complete Journal Contents Listing