No Access

RNG RELAY SUBSET FLOODING PROTOCOLS IN MOBILE AD-HOC NETWORKS

JULIEN CARTIGNY

IRCICA/LIFL, Univ. Lille 1, Bât. M3 Cité Scientifique, 59655 Villeneuve d'Ascq Cedex, France

Corresponding author.

Search for more papers by this author

FRANÇOIS INGELREST

IRCICA/LIFL, Univ. Lille 1, Bât. M3 Cité Scientifique, 59655 Villeneuve d'Ascq Cedex, France

Search for more papers by this author

, and

DAVID SIMPLOT

IRCICA/LIFL, Univ. Lille 1, Bât. M3 Cité Scientifique, 59655 Villeneuve d'Ascq Cedex, France

Search for more papers by this author

https://doi.org/10.1142/S0129054103001716Cited by:25 (Source: Crossref)

Abstract

In this paper, we study broadcasting protocols where nodes use some of their neighbors to forward messages. We propose a new protocol based on a variant of neighbor elimination scheme using RNG graph to ensure a full coverage of the network. The computation of RNG uses two kinds of distance: a geometrical one and and neighborhood-based distance that permits to use our protocol without positioning system. This protocol, called RRS for RNG Relay Subset, provides a self-selecting forwarding neighbor operating mode which guarantees a fair broadcast loading. In RRS a node v is a relay for a node u if and only if v is a neighbor of u and v has a RNG-neighbor which is not covered by u transmission. Moreover, experiments with 802.11-like MAC layer show that RRS is efficient.

This work was partially supported by a grant fram Gemplus Research Labs., an ACI Jeunes Chercheurs "Objets Mobiles Communicants" (1049CDR1) from the Ministry of Education and Scientific Research, France, the CPER Nord-Pas-de-Calais TACT LOMC C21.

Keywords:

References

C. Adjih, P. Jacquet, and L. Viennot, Computing connected dominated sets with multipoint relays, Tech. Report INRIA 4597, oct. 2002 . Google Scholar
S. A. Borbash and E. Jennings , Distributed topology control algorithm for multihop wireless networks , Proc. 2002 World Congress on Computational Intelligence (WCCI 2002) ( 2002 ) . Google Scholar
J. Cartigny and D. Simplot , Border node retransmission based probabilistic broadcast protocols in ad-hoc networks , Proc. 36th Annual Hawaii International Conference on System Sciences (HICSS'03) ( 2003 ) . Google Scholar
J. Cartigny , D. Simplot and I. Stojmenović , Localized minimum-energy broadcasting in ad-hoc networks , Proc. IEEE INFOCOM'2003 ( 2003 ) . Google Scholar
A. Ephremides, J. E. Wieselthier and D. J. Baker, Proc. IEEE 75, 56 (1987), DOI: 10.1109/PROC.1987.13705. Crossref, Web of Science, Google Scholar
E. Mingozzi, Cluster Computing 5(2), 145 (2002), DOI: 10.1023/A:1013981509844. Crossref, Google Scholar
W. Peng and X. C. Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proc. Annual Workshop on Mobile and Ad Hoc Networking and Computing (MobiHoc'2000) (2000) pp. 129–130. Google Scholar
A. Qayyum , L. Viennot and A. Laouiti , Multipoint relaying for flooding broadcast messages in mobile wireless networks , Proc. 35th Annual Hawaii International Conference on System Sciences (HICSS'02) ( 2002 ) . Google Scholar
M. Seddigh, J. S. Gonzalez and I. Stojmenović, ACM Mobile Computing and Communications Review 5(2), 37 (2001), DOI: 10.1145/584066.584069. Crossref, Web of Science, Google Scholar
I. Stojmenović and M. Seddigh , Broadcasting algorithms in wireless networks , Proc. Int. Conf. on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet SSGRR ( 2000 ) . Google Scholar
I. Stojmenović, M. Seddigh and J. Zunic, IEEE Transactions on Parallel and Distributed Systems 13(1), 14 (2002), DOI: 10.1109/71.980024. Crossref, Web of Science, Google Scholar
G. Toussaint, Pattern Recognition 12(4), 261 (1980), DOI: 10.1016/0031-3203(80)90066-7. Crossref, Web of Science, Google Scholar
Y.-C. Tsenget al., WINET Wireless Networks 8(2–3), 153 (2002), DOI: 10.1023/A:1013763825347. Crossref, Web of Science, Google Scholar
J. Wu and H. Li, A dominating-set-based routing scheme in ad hoc wireless networks, Proc. 3rd Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm (DIALM) (1999) pp. 7–14. Google Scholar