#### Year

2006

#### Degree Name

Doctor of Philosophy

#### Department

School of Electrical, Computer and Telecommunications Engineering - Faculty of Informatics

#### Recommended Citation

Srivastava, Gaurav, Efficient topology control algorithms for ad hoc networks, PhD thesis, School of Electrical, Computer and Telecommunications Engineering, University of Wollongong, 2006. http://ro.uow.edu.au/theses/718

#### Abstract

An Ad-hoc network is a collection of devices equipped with computing and wire- less communication capabilities, co-operating together to form a network. An ad-hoc node can communicate with other nodes within its transmission range, or use intermediate nodes to establish communication paths to nodes outside its transmission range. Intermediate nodes in a route can collaborate to act as routers and forward their own traffic as well as the traffic generated by other nodes in a network. This strategy of routing is different to wired networks were communication is made possible through specialised networking devices includ- ing hubs, switches and routers interconnecting Local Area Networks (LANs) and Wide Area Networks (WANs). The routers used in LANs and WANs are devices with large processing capabilities, and high speed communication links. The topology of a network consists of a set of links and nodes which are used to discover and maintain communication paths and assist in coordinating the flow of packets in a network. The topology information can be used for many purposes including evaluating the connectivity/bi-connectivity of a topology and construction of routing paths for network applications. Nodes generally rely on each other to acquire topology information. Topology information can be disseminated by one centralized node by using a specialised process known as ‘flooding’ or can also be disseminated in a distributed manner by broadcasting partial link state information and generating local topology views. Such local views can be put together to generate a larger topology view of a network. Topology control is defined as a process where the topology of a network can be controlled by selective addition of nodes and links within a network. This process of selective addition can significantly impact the power usage and con- nectivity of network devices and improve longevity of a wireless network. In this thesis we analyse the impact of topology control and propose new algorithms and strategies that improve the connectivity, fault tolerance and communica- tion reliability of topology graphs. We review, classify, categorise existing lit- erature and discuss problems and issues associated with topology construction and maintenance proposed with and without Global Positioning System (GPS) aided techniques. Distributed topology control algorithms proposed for constructing minimum node degree graphs [Bettstetter, 2002] including K-Neigh [Blough et al., 2003], Location Information No Topology (LINT) [Ramanathan and Rosales-Hain, 2000], Location Information Link State Topology (LILT) [Ramanathan and Rosales-Hain, 2000] and MobileGrid (MG) [Liu and Li, 2002], do not necessarily generate bidirec- tional connected topology graphs and may result in isolated nodes and discon- nected clusters. Such isolated nodes and disconnected clusters affect the overall connectivity of a network. The bidirectional connectivity of a network is an im- portant factor in order to determine its performance. A ‘bidirectional connected’ network, generally known as a connected network, is able to provide access to all crucial parts of a network and allows delivery of applications through a net- work. The bidirectional links are critical as they facilitate two way communica- tion between the transmitter and receiver nodes. We proposed two mechanisms, Collaborative Algorithm (CA) [Srivastava et al., 2004a] and Probable Critical Links (PCL) [Srivastava et al., 2004d] to improve the connectivity of minimum node degree graphs and analyse their performance [Srivastava et al., 2006]. Power aware topology graphs use low power communications in order to reduce the overall power consumption of network nodes. A power optimised topology graph reduces the total number of links in the topology graph by eliminating long distance links and replacing them with a number of small links. Removing links in a network topology can impact the fault tolerance of a network. Fault tolerance of a network is the ability of a network to cope with link and node failures. We analyse the fault tolerance issues related to power aware topology graphs including Minimum Spanning Tree (MST) [Prim, 1957] and Relative Neighbourhood graphs (RNG) [Huang et al., 2002]. We propose Link Redun- dancy (LR) algorithm [Srivastava et al., 2005a] to improve the fault tolerance of topology control algorithms. We analyse the performance of LR through worked examples and simulations [Srivastava et al., 2005a]. The LR algorithms yields a higher fault tolerant topology as opposed to the distance based approaches where link selections are made on the basis of the separation distance and may not necessarily yield a higher degree of connectivity [Srivastava et al., 2005a]. Power control also allows nodes to improve the spatial reuse of a wireless channel by reducing interference on other network communications and allowing nodes to communicate simultaneously. We analyse the spatial reuse issues related to topology graphs which can limit the performance of the algorithms due to the presence of hidden nodes [Poon and Li, 2003]. We propose Distributed Range Assignment (DRA) algorithm [Srivastava et al., 2004b] to reduce the hidden nodes in a network topology. We and apply DRA to MST and RNG topology graphs and analyse their performance through worked examples and simulations [Srivastava et al., 2004b]. The distance based topology graphs including MST, RNG, K-Neigh, and CA- PCL [Srivastava et al., 2006] do not model obstacles in a network. The con- nectivity of distance based topology graphs can be severely limited due to the presence of obstacles as nodes alter transmission range on the basis of the sep- aration distance of links. Including signal attenuation characteristics can con- struct an accurate view of a network. We analyse the disconnected nature of distance based topology graphs under Lognormal-shadowing [Cox et al., 1984] [Cox et al., 1987] signal attenuation model. The Lognormal-shadowing model is used to analyse the impact of signal strength variations due to shadowing and scattering on the connectivity of power based topology graphs. We propose CA [Srivastava et al., 2006] in conjunction with the with power based topology graphs to improve the connectivity of a network [Srivastava et al., 2005b].

02Whole.pdf (1262 kB)