Graduate School and Research Center in Digital Sciences

Architecture and protocols for supporting routing and quality of service in mobile ad hoc networks

Nikaein, Navid


The topology of an ad hoc network plays a key role in the performance of the control algorithms used in the network for such purposes as routing and broadcasting. In many cases, several network links are used for establishing sharing of the channel among neighbouring nodes or for the routing of data packets. Weeding out redundant and unnecessary topology information is usually called topology management. We suggest a distributed clustering algorithm for topology management in mobile ad hoc networks. The main idea of the algorithm is to select for each node a neighbour, called preferred neighbour that has a maximum degree of connectivity in the neighbourhood (i.e. criteria of the preferred neighbour election algorithm). It has been proven that whatever the network topology is, connecting each node to its preferred neighbour always yield to a forest. In this algorithm, each tree of the forest forms a zone, and each zone is maintained proactively. Therefore, the network is partitioned into a set of non-overlapping zones. Basically, the algorithm combines two notions: forest and zone. Forest reduces the broadcasting overhead by selecting a subset of the set of neighbouring nodes for forwarding a packet, and zones are used to reduce the delay due to routing process and to reach high scalability. We also provide a mechanism to describe the quality of connectivity for extracting the links connecting the pair of best nodes over time from the network point of view, and use this as an enhanced criterion for the preferred neighbour election algorithm. This is desirable because the forwarding nodes belong to the set of nodes with the high quality of connectivity, which in turn improves routing performance. The results have shown that the performance of routing can be significantly improved with the help of topology management. A Hybrid Ad hoc Routing Protocol (HARP), which combines proactive behaviour within a zone and reactive behaviour between zones, is proposed. Routing is performed on two phases: intra-zone and inter-zone, depending on whether the destination belongs to the same zone as the forwarding node. Intra-zone routing relies on an existing proactive mechanism inherited from the topology management strategy, and as a result routing is done without any route acquisition delay. Inter-zone routing, on the other hand, applies the path discovery procedure to find the most suitable path to the destination's zone. The overhead related to flooding nature of this procedure is noticeably reduced due to the combination of forest and query localization technique. The forest structure reduces the broadcast storm problem by selecting a subset of neighboring nodes to forward a packet, while query localization limits the scope of path discovery. A detailed simulation model is used to study the performance of our approach. We evaluate and compare the performance of HARP with DSR, AODV, and OLSR routing protocols under various network loads and mobility rates. The obtained results show that HARP outperforms other protocols. It is demonstrated that our routing protocol together with the topology management strategy succeed to achieve load balancing in the network. The observations have shown that network traffic load and mobility affect the absolute performance of the protocols, and that their impact on different protocols is non-uniform.

Document Doi Bibtex

Title:Architecture and protocols for supporting routing and quality of service in mobile ad hoc networks
Keywords:Mobile ad hoc networks;graph theory;topology management;connected dominating set;clustering;routing;quality of connectivity;quality of service;simulation;performance evaluation
Department:Communication systems
Eurecom ref:1251
Copyright: © EPFL. Personal use of this material is permitted. The definitive version of this paper was published in Thesis and is available at :
Bibtex: @phdthesis{EURECOM+1251, doi = {}, year = {2003}, title = {{A}rchitecture and protocols for supporting routing and quality of service in mobile ad hoc networks}, author = {{N}ikaein, {N}avid}, school = {{T}hesis}, month = {09}, url = {} }
See also: