Year

2004

Degree Name

Doctor of Philosophy

Department

School of Electrical, Computer and Telecommunications Engineering

Abstract

Importantly the approaches described in literature only consider the use of a constant (full power) transmission range by all nodes when broadcasting.

We propose two mechanisms: Neighbour Aware Adaptive Power (NAAP) flooding and Localised Minimum Spanning Tree Flooding (LMSTFlood). NAAP utilises a combination of techniques based on neighbour coverage, knowledge of neighbouring relays and the decomposition of high power broadcasts into low power broadcasts through local optimisation to reduce the broadcast transmission range. LMSTFlood utilises the minimum spanning tree (MST) in distributed manner and thus benefits from the properties of the distributed MST and the ability for relay nodes to be self selecting, thus reducing the per packet overhead found in NAAP and other optimised flooding mechanisms. Both mechanisms allow for the transmission range of a broadcast to be adjusted to only include (where possible) those necessary nodes within a broadcast. This limits the effect of broadcasts on neighbouring nodes that may not need to receive a broadcast. The proposed mechanisms are shown to scale significantly better (in terms of reducing the broadcast storm problem and energy consumption) in high node densities than those optimised mechanisms based upon a constant transmission range.

Resource awareness implies that the mechanisms are able to make decisions about which nodes are selected to rebroadcast based upon available resources. These resources may be a node's available battery power or constraints imposed upon a devices behaviour by a user. The approach of existing optimised flooding mechanisms is to select rebroadcasting nodes irrespective of available resources. We propose two optimised and resource aware flooding mechanisms: Utility based Multipoint Relay (UMPR) Flooding and Utility Based Flooding (UBF). UMPR extends MPR by allowing a limited selection of relays based upon their resources while maintaining the selection of relays with unique neighbours as in MPR . UMPR shows improved performance over existing optimised flooding mechanisms, but through simulation was found to have deficiencies due to the majority of relays selected having unique neighbours. UBF was developed to address these deficiencies. The proposed mechanisms extend the lifetime of the network over successive floods in an energy and user constrained ad hoc network. Importantly, the addition of resource awareness in the proposed mechanisms does not impact overhead performance compared with existing optimised flooding mechanisms.

Optimised flooding mechanisms reduce problems associated with blind flooding by limiting redundant broadcasts and reducing the effects of broadcasting by reducing transmission power. However, the very nature of Blind flooding and the large number of redundant transmissions ensures higher reliability than optimised flooding mechanisms. We show that the reliability of optimised flooding mechanism are drastically affected by background traffic compared to Blind flooding. This is due to the unreliable nature of IEEE 802.11 broadcasts, which are significantly affected by unicast transmissions and other broadcasts transmissions. W e propose Reliable Minimum Spanning Tree (RMST) flooding. RMST is an optimised flooding mechanism that takes advantage of the unique nature of the Minimum Spanning Tree (MST) to replace unreliable broadcast transmissions (as used by existing optimised flooding mechanisms) with more reliable unicast transmissions. Through simulation R M S T is shown to have equivalent reliability to Blind flooding with overhead performance exceeding M P R and approaching that of LMSTFlood.

A sensor network is a type of ad hoc network that allows for a node acting as a sink request information from other nodes. Sensor networks are specialised to optimise the flow of information from nodes back to the sink. In sensor network literature there is much work on mechanisms for information collection. However, much of this work focuses on sensor networks, not on ad hoc networks. W e propose Resource Aware Information Collection (RAIC), a distributed resource aware information collection mechanism for ad hoc networks. RAIC utilises optimised and resource aware flooding mechanisms to disseminate requests for information and to create a directed backbone of nodes capable of relaying information back to the sink. RAIC is compared to Directed Diffusion and a brute force approach (Direct Response) and shown to be able to collect information from nodes in the ad hoc network with less overhead in terms of packets transmitted and received, and energy consumption. Additionally given an ad hoc network with resource constrained nodes, RAIC is able to perform significantly more repeated requests for information than Directed Diffusion or Direct Response.

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.