Variable power broadcast using local information in ad hoc networks

Abstract

Network wide broadcast is a frequently used operation in ad hoc networks. Developing energy efficient protocols to reduce the overall energy expenditure in network wide broadcast can contribute toward increasing the longevity of ad hoc networks. Most of the existing work in energy efficient broadcast protocols use either a fixed transmission power model or assume global knowledge of the entire network at each node. Variable power broadcast with local knowledge has recently been proposed as a promising alternative approach for network wide broadcast in ad hoc networks.

In this paper, we present a novel approach, called INOP, for network wide broadcast. INOP is a variable power broadcast approach that uses local (two-hop neighborhood) information. INOP utilizes a novel technique for determining the transmission power level at each transmitting node. We also propose two alternative methods to cover the nodes that are not covered by the transmission of the source or a retransmitting node.

Our simulation based evaluations show that, compared to other approaches, INOP achieves better results in terms of energy efficiency, and competes with and exceeds other approaches in terms of a number of other performance metrics including traffic overhead, coverage, and convergence time. Based on these results, we can conclude that INOP improves the current state-of-the-art approaches for energy efficient broadcast in ad hoc networks.

Introduction

Network wide broadcast is a frequently used operation in ad hoc networks. In addition to data broadcast, it is used for various protocol operations including route discovery and address assignment [1], [2], [3], [4], [5]. Nodes in ad hoc networks work with limited energy and the efficient utilization of this energy is important for increasing the lifetime of the individual nodes as well as the overall network. Depending on the size and topology of an ad hoc network, network wide broadcast may require multiple nodes to participate in the dissemination of the messages to the entire network. Hence, network wide broadcast is an energy intensive operation. As a result, it is important to develop energy efficient algorithms to implement network wide broadcast in ad hoc networks.

Energy efficient broadcast protocols can be classified into two main groups¹: (1) fixed power approach and (2) power adaptive or variable power approach. In the fixed power approach, nodes use a pre-determined fixed power level for transmission. Here, the aim is to reduce energy expenditure by reducing the overall number of transmissions by selecting a minimal number of relay nodes to cover all the nodes in the network [6] provides an excellent overview and comparison of the proposals in this group.

In the power adaptive approach, nodes adjust their transmission power levels to reduce the overall energy consumption in network wide broadcast. In this case, energy expenditure can be reduced by transmitting with just enough power to reach only the nodes that need to be reached. In has been shown that building a topology structure that would yield a minimum energy in a broadcast operation is an NP-hard problem [7].

The initial proposals in power adaptive approach assume global state knowledge [8], [9], [10], [11]. That is, information about the entire topology including the nodes, the links, and the power costs of each link is assumed to be available at a centralized location. More recently, several heuristics have been proposed to implement network wide broadcast using local one- or two-hops neighborhood information [12], [13], [14], [15], [16]. Considering the difficulties of collecting and maintaining an accurate global topology information in an ad hoc network, the local information based algorithms (or localized algorithms) are considered more practical for their actual deployment in ad hoc networks.

In this paper, we present a novel localized algorithm for power adaptive broadcast in ad hoc networks. Our approach is called INOP (INside-Out Power adaptive approach). The main goal in INOP is to make a better use of the available two-hop local neighborhood information to achieve a better energy utilization in covering the one-hop neighbors. This is achieved by carefully calculating the overall energy budget needed to cover all one-hop neighbors either directly or indirectly via neighbors. On the other hand, the existing approaches [12], [13], [14], [15], [16] make a more limited use of the available two-hop neighborhood information and often result in less energy savings as compared to INOP.

In INOP, starting from the closest neighbor and moving outwards (i.e., centrifugal or inside-out direction), a transmitting node computes the optimal transmission strategy to (directly or indirectly) reach all neighbors within its coverage range. Each transmitting node first sorts its neighbors based on the required power to reach them. Then, starting from the closest neighbor, the node compares the required power levels to reach the next neighbor either directly or indirectly via some other neighbor. Based on this comparison, the transmitting node decides on the transmission power level to use in its broadcast. In this work, we extend upon our preliminary work presented in [17]. We provide an improvement in choosing the power level by a transmitting node. In multi-hop ad hoc networks, energy savings in network wide broadcast depends on the selection of the relay (or rebroadcasting) nodes. If the relay nodes are not chosen carefully, the overall gain in energy savings will be low. In this work, we present two approaches in choosing the rebroadcasting nodes. The first approach is borrowed from the previous work in which each node reactively decides for itself if it will perform a rebroadcast or not. We then propose a second approach where a transmitting node pro-actively selects a subset of its neighbors to perform the rebroadcast operation so that all its one-hop and two-hop neighbors are covered. Our simulation based comparisons show that our approaches provide better overall performance in terms of several performance metrics such as energy consumption per covered node, coverage, number of rebroadcasts, and convergence time.

Finally, in this study, we use a disk to represent the coverage area of wireless transmission [18]. In this model, when a node transmits a packet with a transmission range of r, the packet propagates omni-directionally and all the neighbors within the circular area of radius r are assumed to receive the packet. In practice, wireless channel exhibits randomness due to multi-path propagation or shadowing. These factors may affect the shape of the actual coverage area of wireless transmissions. This may then cause some nodes within the circular coverage range to miss the packet resulting in a potential decrease in the overall coverage of a network wide broadcast operation. These factors introduce similar coverage issues for all broadcast protocols considered in this paper. Given the difficulty level of the broadcast problem (i.e., minimum energy broadcast tree construction is NP-hard even for unit disk graphs [18]), studying the problem under a disk-based coverage model makes it easier to build solutions and easier to compare these solutions with each other. Due to this fact, most previous studies in the area use a disk-based coverage model for wireless transmission. In this work, we follow the same trend and use the disk-based coverage model to build our algorithms and compare them with the previous work. We expect that a similar performance relations follow in more practical coverage models for wireless transmissions.

The rest of the paper is organized as follows. Section 2 presents a classification of the available broadcast approaches. Section 3 describes the communication and the energy models. Section 4 describes INOP, the proposed algorithm. Section 5 presents the simulation based evaluations and Section 6 concludes the paper.