Localized LMST and RNG based minimum-energy broadcast protocols in ad hoc networks

被引：47
作者：
Cartigny, Julien [1 ]
Ingelrest, Francois [1 ]
Simplot-Ryl, David [1 ]
Stojmenovic, Ivan [2 ]
机构：
[1] IRCICA/LIFL, Université de Lille 1, INRIA Futurs
[2] SITE, University of Ottawa, Ottawa
来源：
Ad Hoc Networks | 2005年 / 3卷 / 01期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Broadcasting; Energy conservation; Localized algorithm; Wireless ad hoc networks;
D O I：
10.1016/j.adhoc.2003.09.005
中图分类号：
学科分类号：
摘要：
In the minimum energy broadcasting problem, each node adjusts its transmission power to minimize the total energy consumption while still guaranteeing the full coverage of the network. We consider both topology control and broadcast oriented protocols, for which all existing solutions require global network information. In this paper, we describe new localized protocols where nodes require only local informations about their neighborhood (distances or geographic positions). In addition to this, our protocols are shown experimentally to be comparable to the best known globalized BIP solution. Our solutions are based on the use of neighbor elimination scheme applied on the relative neighborhood graph (RNG) and local minimum spanning tree (LMST) which preserve connectivity and are defined in localized manner. Two variants are proposed, one with timeout applied on nodes receiving message from non-RNG (non-LMST) neighbor and retransmitting immediately otherwise (unless list of RNG or LMST neighbors in need of the message is empty), and one with timeout applied on all the nodes. We proved that LMST is a subset of RNG, which explains why LMST always performs better among the two. © 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：1 / 16
页数：15
相关论文
共 32 条
  • [1] Bose P., Morin P., Stojmenovic I., Urrutia J., Routing with guarantee delivery in ad hoc networks, ACM/Kluwer Wireless Networks, 7, 6, pp. 609-616, (2001)
  • [2] Chu T., Nikolaidis I., Energy efficient broadcast in mobile ad hoc networks, Proceedings Ad Hoc Networks and Wireless (ADHOC-NOW), pp. 177-190, (2002)
  • [3] Peng W., Lu X., On the reduction of broadcast redundancy in mobile ad hoc networks, Proceedings of Annual Workshop on Mobile and Ad Hoc Networking and Computing (MobiHoc'2000), pp. 129-130, (2000)
  • [4] Qayyum A., Viennot L., Laouiti A., Multipoint relaying for flooding broadcast messages in mobile wireless networks, Proceedings of the 35th Annual Hawaii Inter-national Conference on System Sciences (HICSS-35), (2002)
  • [5] Wu J., Li H., A dominating-set-based routing scheme in ad hoc wireless networks, Proceedings of the Third International Workshop Discrete Algorithms and Methods for Mobile Computing and Communication (DIALM'99), pp. 7-14, (1999)
  • [6] Kirousis L., Kranakis E., Krizanc D., Pelc A., Power consumption in packet radio networks, Proceedings of the 14th Symposium on Theoretical Computer Science (STACS'97), 1200, pp. 363-374, (1997)
  • [7] Clementi A., Penna P., Silvestri R., The power range assignment problem in radio networks on the plane, Proceedings of 17th Symposium on Theoretical Computer Science (STACS'OO), 1770, pp. 651-660, (2002)
  • [8] Lloyd E., Liu R., Marathe M., Ramanathan R., Ravi S., Algorithmic aspects of topology control problems for ad hoc networks, Proceedings of the Annual Workshop on Mobile and Ad Hoc Networking and Computing (MobiHoc'2002), (2002)
  • [9] Wieselthier J., Nguyen G., Ephremides A., On the construction of energy-efficient broadcast and multicast trees in wireless networks, Proceedings of the IEEE Infocom'2000, pp. 585-594, (2000)
  • [10] Egecioglu O., Gonzalez T., Minimum-energy broadcast in simple graphs with limited node power, Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems, pp. 334-338, (2001)
1234