Year

2012

Degree Name

Doctor of Philosophy

Department

School of Electrical, Computer and Telecommunications Engineering

Abstract

Ad hoc networks consist of a set of de-centralised end-user nodes which perform routing in a distributed manner over the wireless medium. This distinct feature of these networks has created a number of new and challenging research issues in the wireless data networking paradigm. One such issue is routing, which has consequently received significant attention in particular, the problem of creating routing protocols that scale well in large networks. This has led to the proposition of various categories of routing protocols. These routing protocols have been classified into three classes according to the strategies for discovering and maintaining routes: proactive, reactive, and hybrid. Each routing protocol reacts differently to node mobility and density.

On-demand routing protocols have the potential to provide scalable information delivery in large ad hoc networks. The novelty of these protocols is in their approach to route discovery, where a route is determined only when it is required by initiating a route discovery procedure. Much of the research in this area has focused on reducing the route discovery overhead when prior knowledge of the destination is available at the source or by routing through stable links. Hence, many of the protocols proposed to date still resort to flooding the network when prior knowledge about the destination is un-available. In addition, the issue of node heterogeneity is not considered in current MANET routing protocols. Although most current MANET routing protocols assume homogeneous networking conditions where all nodes have the same capabilities and resources, in practice MANETs may consist of heterogeneous nodes that have diverse capabilities and resources, for example military (battlefield) networks and rescue operations systems. Homogeneous networks are easy to model and analyse, but tend to exhibit poor scalability compared with heterogeneous networks. Therefore, scalability and heterogeneity in MANETs are issues that significantly affect the performance of routing protocols. Hence, this dissertation examines the scalability properties of ad hoc routing protocols in homogeneous and heterogeneous MANETs.

The research begins with a review of the scalability characteristics of several different classes of routing protocols. This is followed by an extensive study of the performance of current on-demand routing protocols in heterogeneous networks that consist of different nodes with different resources. The study shows that while all protocols perform reasonably well in homogeneous networking conditions, their performance suffer significantly over heterogeneous networks.

This dissertation presents two scalable routing protocols. The first is proposed to improve scalability of homogeneous ad hoc networks when there is no prior knowledge about the destination. This protocol is called On-demand Tree-based Routing Protocol (OTRP) . It combines the idea of hop-by-hop routing (as used by Ad-hoc On-Demand Distance Vector (AODV) with an efficient route discovery algorithm called Tree-based Optimised Flooding (TOF) . In this protocol, route discovery overheads are minimised by selectively flooding the network through a limited set of nodes, referred to as branching nodes. The key factors governing the performance of OTRP are theoretically analysed and evaluated, including the number of branch nodes, location of branching nodes and number of Route REQuest (RREQ) retries. It was found that the performance of OTRP (evaluated using a variety of well-known metrics) improves as the number of branching nodes increases and the number of consumed RREQ retries is reduced. Additionally, theoretical analysis and simulation results shows that OTRP outperforms AODV, Dynamic MANET On-demand (DYMO) , and Optimised Link State Routing (OLSR) with reduced overheads as the number of nodes and traffic load increases.

The second protocol is On-demand Tree-based Routing Protocol Heterogeneity-Aware (OTRP_HA) . It utilises node heterogeneity and optimises route discovery to reduce overheads while ensuring connectivity between different types of nodes with different interfaces.

A node heterogeneity model is developed which can be used to describe common types of node heterogeneity. Nodes in this model are identified by: number of radio interfaces, types of interfaces, and types of power that provides energy for nodes. A strategy called Location-Based Utilisation (LBU) is then introduced to detect unidirectional links and resolve them in a timely fashion. This strategy is based on utilising locations of nodes to filter and cache incoming RREQ packets to find reliable paths to the destination when unidirectional links exist. This strategy is evaluated by applying it on top of ADOV and OTRP. Simulation results show that LBU outperforms existing strategies in homogeneous and heterogeneous MANETs.

Finally, a new approach to route discovery is proposed based on the node heterogeneity model. Each node makes its own decision as to whether or not to participate in the route discovery process according to its location, local density, and available resources. This route discovery strategy is combined with LBU. Theoretical analysis and simulation results show that OTRP_HA outperforms OTRP and AODV while reducing overhead as a the number of nodes and traffic volume increase, while also further prolonging the lifetime of batterypowered single-interface nodes when compared to AODV.

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.