RNG and internal node based broadcasting algorithms for wireless one-to-one networks
Authors:
Open Access
- 1 April 2001
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOBILE Mobile Computing and Communications Review
- Vol. 5 (2) , 37-44
Abstract
In a multihop wireless network, each node has a transmission radius and is able to send a message to one of its neighbors (one-to-one) or all of its neighbors (one-to-all) that are located within the radius. In a broadcasting task, a source node needs to send the same message to all the nodes in the network. In this paper, we propose 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. Regular message exchanges between neighbors, which include location updates or signal strengths, suffice to maintain these structures, and they therefore do not impose additional communication overhead. In internal node based broadcasting, messages are forwarded on the edges that connect two internal nodes, and on edges that connect each non-internal node with its closest internal node. A neighbor elimination scheme is added to the internal node concept, to improve its performance. Similarly, only edges in a planar subgraph may be used for retransmissions. The reduction in communication overhead for broadcasting task, with respect to existing methods, is measured experimentally. The number of retransmissions is reduced to about 50% for sparse networks and to about 5% for dense networks, and the overhead with respect to ideal solution is up to 20% (for 100 nodes).Keywords
This publication has 9 references indexed in Scilit:
- On the reduction of broadcast redundancy in mobile ad hoc networks2002
- Next century challenges1999
- Adaptive protocols for information dissemination in wireless sensor networks1999
- Routing with guaranteed delivery in ad hoc wireless networks1999
- On calculating connected dominating set for efficient routing in ad hoc wireless networks1999
- The broadcast storm problem in a mobile ad hoc network1999
- A performance comparison of multi-hop wireless ad hoc network routing protocols1998
- Simple traversal of a subdivision without extra storageInternational Journal of Geographical Information Science, 1997
- The relative neighbourhood graph of a finite planar setPattern Recognition, 1980