Energy efficient broadcasting in wireless ad hoc networks

Official URL: http://risc01.sabanciuniv.edu/record=b1228178 (Table of Contents)

In recent years wireless multi-hop networks have attracted significant attention due to their wide range of potential civil and military applications. Broadcasting is a funda- mental data dissemination scheme for these networks. The transmission power control is an important issue in wireless ad hoc networks and still has no satisfactory solution methods. The wireless networking environment presents formidable challenges to the study of broadcasting problems. In particular, the properties of the wireless medium and the presence of battery-powered devices require novel modeling and algorithmic approaches concentrating on judicious use of limited energy resources in wireless net- works. In addition, networks are often required to provide certain quality of service (QoS) guarantees in terms of the end-to-end delay along the individual paths from the source to each of the destination nodes. Moreover, the received signal at each receiv- ing node must be strong enough to be successfully decoded. In this study we address the minimum-energy broadcast problem in multi-hop wireless networks with respect to two different constraints: (i) each node must receive broadcast message within a given delay bound Δ, and (ii) signal-to-interference-plus-noise ratio (SINR) of the received signal must be above a given threshold [y] so that the received signal can be successfully decoded at the receiving node. We propose two distinct algorithms Distributed Tree Expansion (DTE) and SINR-BIP which aim to generate minimum power broadcast tree with respect to constraint (i) and (ii), respectively and exclusively. DTE is based on an implementation of a distributed minimum spanning tree algorithm in which the tree grows at each iteration by adding a node that can cover the maximum number of currently uncovered nodes in the network with minimum incremental transmission power and without violating the delay constraint. In SINR-BIP, we apply the similar idea of well-known Broadcast Incremental Power (BIP) algorithm while considering the SINR values of received powers. In addition, we use an embedded pruning procedure in SINR-BIP, so that the myopic effect of the algorithm is mitigated. Both the algo- rithms DTE and SINR-BIP are constructive in nature since the broadcast tree grows at each iteration. We observed that the DTE outperforms the existing algorithms and the total energy consumptions of the generated broadcast trees by DTE is within 20% percent of the solutions obtained by Integer Programming.