Localized Minimum-Energy Broadcasting for Wireless Multihop Networks with Directional Antennas

J Iguchi-Cartigny, PM Ruiz, D Simplot-Ryl, Ivan Stojmenovic, CM Yago

Research output: Contribution to journalArticle

14 Citations (Scopus)


There are a number of proposals to achieve energy-efficient broadcasting in wireless multihop networks using directional antennas. However, these proposals are based on centralized algorithms, which require global knowledge of the topology of the network. Such global protocols are not suitable for ad hoc networks because of the high number of control messages required to gather such global information. We propose several localized algorithms, where each node needs to know only geographic position of itself and its neighbors. We also introduce a new energy consumption model for directional antennas, which generalizes models commonly used. Our first protocol is called DRBOP and it follows the one-to-one communication model to reach to all nodes following the relative neighborhood graph (RNG). RNG preserves connectivity and can be locally computed by each node without any message exchange. Each node that receives a message for the first time from one of its RNG neighbors will rebroadcast it to each of its remaining RNG neighbors separately. The transmission power is adjusted for each transmission to the minimal necessary for reaching the particular neighbor. Since the average degree of RNG is about 2.5, approximately 1.5 rebroadcasts are done by each node to its neighbors. Next, we describe DLBOP, where RNG is replaced by the local minimum spanning tree (LMST) graph, which is a localized topology resembling the minimum spanning tree. We then observe that, for very dense networks, it is more energy-efficient to reach more than one neighbor at a time. A one-to-many protocol efficient for dense networks is proposed. We then describe an efficient localized protocol, which adaptively switches (without any threshold) between one-to-one and one-to-many communication models and is efficient for both sparse and dense networks. Our simulation results show that for different energy models, the adaptive protocol is able to achieve a competitive performance compared to centralized algorithms while having a fully localized operation.
Original languageEnglish
Pages (from-to)120-131
Number of pages12
JournalIEEE Transactions on Computers
Issue number1
Publication statusPublished - 1 Jan 2009


  • power management
  • Distributed networks
  • broadcasting
  • directional antenna


Dive into the research topics of 'Localized Minimum-Energy Broadcasting for Wireless Multihop Networks with Directional Antennas'. Together they form a unique fingerprint.

Cite this