Localized minimum-energy broadcasting in ad-hoc networks
Published 2 March 2004
Julien Cartigny, David Simplot, Ivan Stojmenović
Citations278
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work describes a new localized protocol where each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes (or, alternatively, geographic position of itself and its neighboring node).
Abstract
In the minimum energy broadcasting problem, each node can adjust its transmission power in order to minimize total energy consumption but still enable a message originated from a source node to reach all the other nodes in an ad-hoc wireless network. In all existing solutions each node requires global network information (including distances between any two neighboring nodes in the network) in order to decide its own transmission radius. We describe a new localized protocol where each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes (or, alternatively, geographic position of itself and its neighboring nodes). In addition to using only local information, our protocol is shown experimentally to be comparable to the best known globalized BIP solution. Our solutions are based on the use of relative neighborhood graph, which preserves connectivity and is defined in localized manner.
Keywords
Computer Science
IEEE Journal on Selected Areas in CommunicationsMinimum energy mobile wireless networks
1,690 Citations1999Volkan Rodoplu, T.H. Meng
On calculating connected dominating set for efficient routing in ad hoc wireless networks
1,230 Citations1999Jie Wu, Hailan Li
This paper proposes a simple and efficient distributed algorithm for calculating connected dominating set in ad-hoc wireless networks, where connections of nodes are determined by their geographical distances.
Wireless NetworksRouting with Guaranteed Delivery in Ad Hoc Wireless Networks
1,203 Citations2001Prosenjit Bose, Pat Morin +2 more
On the construction of energy-efficient broadcast and multicast trees in wireless networks
1,063 Citations2002Jeffrey E. Wieselthier, Gam D. Nguyen +1 more
This paper develops the Broadcast Incremental Power algorithm, and adapt it to multicast operation by introducing the Multicast Incremental Power (MIP) algorithm, which exploit the broadcast nature of the wireless communication environment, and address the need for energy-efficient operation.
Pattern RecognitionThe relative neighbourhood graph of a finite planar set
988 Citations1980Godfried T. Toussaint
The ability of the RNG to extract a perceptually meaningful structure from the set of points is briefly discussed and compared to that of two other graph structures: the minimal spanning tree and the Delaunay (Voronoi) triangulation.
IEEE Transactions on Parallel and Distributed SystemsDominating sets and neighbor elimination-based broadcasting algorithms in wireless networks
869 Citations2002Ivan Stojmenović, M. Seddigh +1 more
This paper proposes to significantly reduce or eliminate the communication overhead of a broadcasting task by applying the concept of localized dominating sets, which do not require any communication overhead in addition to maintaining positions of neighboring nodes.
Multipoint relaying for flooding broadcast messages in mobile wireless networks
715 Citations2003Amir Qayyum, Laurent Viennot +1 more
The mechanism of multipoint relays (MPRs) to efficiently flood broadcast messages in mobile wireless networks is discussed and a heuristic to select these MPRs in a mobile wireless environment is proposed, and it is proved that the computation of a multipoint relay set with minimal size is NP-complete.
Mobile Ad Hoc Networking and ComputingOn the reduction of broadcast redundancy in mobile ad hoc networks
581 Citations2000Wei Peng, Xicheng Lu
Mobile Networks and ApplicationsAn Energy Consumption Model for Performance Analysis of Routing Protocols for Mobile Ad Hoc Networks
434 Citations2001Laura Marie Feeney
A model for evaluating the energy consumption behavior of a mobile ad hoc network is presented and energy-aware performance analysis is shown to provide new insights into costly protocol behaviors and suggests opportunities for improvement at the protocol and link layers.
Theoretical Computer SciencePower consumption in packet radio networks
424 Citations2000Lefteris M. Kirousis, Evangelos Kranakis +2 more
For points in three dimensions it is shown that the problem of deciding whether a complete range assignment of a given cost exists, is NP-hard and an O(n 2 ) time approximation algorithm is given which provides a completerange assignment with cost within a factor of two of the minimum.
Minimum-energy broadcast routing in static ad hoc wireless networks
386 Citations2002Peng‐Jun Wan, Gruiă Cälinescu +2 more
By exploring geometric structures of Euclidean MSTs, it is proved that the approximation ratio of MST is between 6 and 12, and the approximation ratios of BIP is between /sup 13///sub 3/ and 12; these are the first analytical results for minimum-energy broadcasting.
Minimum energy paths for reliable communication in multi-hop wireless networks
345 Citations2002Suman Banerjee, Archan Misra
This paper studies how link error rates affect this retransmission-aware metric, and how it leads to an efficient choice between a path with a large number of short- distance hops and another with a smaller number of large-distance hops.
Telecommunication SystemsA Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks
295 Citations2001Jie Wu, Hailan Li
A simple and efficient distributed algorithm for calculating connected dominating set in ad hoc wireless networks, where connections of nodes are determined by their geographical distances and an update/recalculation algorithm for theconnected dominating set when the topology of the ad hoc Wireless Network changes dynamically.
Constructing minimum-energy broadcast trees in wireless ad hoc networks
276 Citations2002Weifa Liang
The technique adopted in this paper is to reduce the minimum-energy broadcast (multicast) tree problem on a wireless ad hoc network to an optimization problem on an auxiliary weighted graph, and solve the optimization Problem on the auxiliary graph which in turn gives an approximate solution for the original problem.
Wireless NetworksMinimum-Energy Broadcasting in Static Ad Hoc Wireless Networks
184 Citations2002Peng‐Jun Wan, Gruiă Cälinescu +2 more
By exploring geometric structures of Euclidean MSTs, it is proved that the approximation ratio of MST is between 6 and 12, and the approximation ratios of BIP is between 13/3 and 12; these are the first analytical results for the minimum-energy broadcasting problem.
Algorithmic aspects of topology control problems for ad hoc networks
175 Citations2002Errol L. Lloyd, Rui Liu +3 more
A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties and a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is developed.
Minimum energy paths for reliable communication in multi-hop wireless networks
171 Citations2002Suman Banerjee, Archan Misra
Energy efficient communications in ad hoc networks using directional antennas
170 Citations2003A. Spyropoulos, C.S. Raghavendra
An energy-efficient routing and scheduling algorithm that coordinates transmissions in ad hoc networks where each node has a single directional antenna and achieves all the possible transmitter/receiver gains possible from using directional antennas is presented.
On the reduction of broadcast redundancy in mobile ad hoc networks
135 Citations2002Wei Peng, Xicheng Lu
In this work, an efficient approach to reduce the broadcast redundancy is proposed using local topology information and the statistical information about the duplicate broadcasts to avoid unnecessary rebroadcasts.
Border node retransmission based probabilistic broadcast protocols in ad-hoc networks
128 Citations2003Julien Cartigny, David Simplot
It is observed that the distance between two nodes can be approximated by comparing neighbor lists, which leads to broadcasting schemes that do not require position or signal strength information and require only knowledge of one hop neighborhood.
Distributed topology control algorithm for multihop wireless networks
118 Citations2003Steven A. Borbash, Esther Jennings
A network initialization algorithm for wireless networks with distributed intelligence is presented to use power control to establish a topology based on the relative neighborhood graph which has good overall performance in terms of power usage, low interference, and reliability.
Energy-limited wireless networking with directional antennas: the case of session-based multicasting
115 Citations2003Jeffrey E. Wieselthier, Gam D. Nguyen +1 more
It is shown that the network's lifetime can be extended significantly by incorporating a simple measure of a node's residual energy into the node's cost function and observing significant improvement with respect to the omnidirectional case.
Lecture notes in computer scienceThe Power Range Assignment Problem in Radio Networks on the Plane
82 Citations2000Andrea Clementi, Paolo Penna +1 more
A lower bound on the total power consumption opth(S) yielded by an optimal range assignment for any instance (S, h) of 2D MIN h R is provided and a polynomial-time approximation algorithm is obtained.
ACM SIGMOBILE Mobile Computing and Communications ReviewRNG and internal node based broadcasting algorithms for wireless one-to-one networks
79 Citations2001M. Seddigh, Julio Solano González +1 more
This paper proposes to reduce the communication overhead of broadcasting algorithm for one-to-one model by applying the concepts of planar graphs such as RNG (relative neighborhood graphs) and connected dominating sets determined by internal nodes.
Lecture notes in computer sciencePower consumption in packet radio networks
76 Citations1997Lefteris M. Kirousis, Evangelos Kranakis +2 more
This paper studies the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the node to ensure that the network is strongly connected.
Minimum-energy Broadcast in Simple Graphs with Limited Node Power
72 Citations2007Ömer Eğecioǧlu, Teofilo F. Gonzalez
This paper shows that the weighted graph minimum-energy broadcast problem is NP-hard in metric space when transmissions are restricted to a given set of power levels by means of an upper bound d on the allowed transmission radius.
Constructing minimum energy mobile wireless networks
72 Citations2001Xiang‐Yang Li, Peng‐Jun Wan
Minimum power broadcast trees for wireless networks: optimizing using the viability lemma
70 Citations2003Robert J. Marks, Arindam Das +3 more
This work proposes an alternate search based paradigm wherein minimum-cost trees in wireless networks are found through a search process, and two computationally efficient procedures for checking the feasibility (viability) of a solution in the search space are presented.
ACM SIGMOBILE Mobile Computing and Communications ReviewConstructing minimum energy mobile wireless networks
46 Citations2001Xiang‐Yang Li, Peng‐Jun Wan
A distributed position-based networking protocol is described to construct an enclosure graph Ge, which is an approximation of G m which improves the previous result that computes G m in O(d (u)3 time.
Energy efficient broadcasting for situation awareness in ad hoc networks
41 Citations2001S. Lindsey, C.S. Raghavendra
This paper considers energy efficient one- to-all and all-to-all broadcast communications in power constrained networks and presents schemes for situation awareness, which significantly improve the life of the network compared to schemes with direct transmissions.
HAL (Le Centre pour la Communication Scientifique Directe)Stochastic Flooding Broadcast Protocols in Mobile Wireless Networks
35 Citations2002Julien Cartigny, David Simplot +1 more
Improvements of the flooding protocols that aim to efficiently broadcast a given information through the whole network are proposed and decrease the number of emitted packets and hence, the medium occupation.
Energy-Efficient Topology Control for Wireless Ad Hoc Sensor Networks
24 Citations2002Yu‐Chee Tseng, Yen-Ning Chang
It is shown that optimal lifetimes can be obtained by using a simple minimum spanning tree construction under the fixed power assumption.
Localized Energy Efficient Broadcast for Wireless Networks With Directional Antennas
15 Citations2002Julien Cartigny, David Simplot +1 more
A localized algorithm where each nodes needs to know only geographic position of itself and its neighbors is described, based on the use of relative neighborhood graphs (RNG) which preserves connectivity.