research-article

Optimal Initialization and Gossiping Algorithms for Random Radio Networks

Author:

Vlady RavelomananaAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 18, Issue 1

Pages 17 - 28

Published: 01 January 2007 Publication History

Abstract

The initialization problem, also known as naming, consists to give a unique identifier ranging from 1 to n to a set of n indistinguishable nodes in a given network. We consider a network where n nodes (processors) are randomly deployed in a square (respectively, cube) X. We assume that the time is slotted and the network is synchronous, two nodes are able to communicate if they are within distance at most of r of each other (r is the transmitting/receiving range). Moreover, if two or more neighbors of a processor u transmit concurrently at the same time slot, then u would not receive either messages. We suppose also that the anonymous nodes know neither the topology of the network nor the number of nodes in the network. Under this extremal scenario, we first show how the transmitting range of the deployed processors affects the typical characteristics of the network. Then, by allowing the nodes to transmit at various ranges we design sublinear randomized initialization protocols: In the two, respectively, three, dimensional case, our randomized initialization algorithms run in O(n^{1/2}\log n^{1/2}), respectively, O(n^{1/3}\log n^{2/3}), time slots. These latter protocols are based upon an optimal gossiping algorithm which is of independent interest.

References

[1]

M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions. Dover Publication, 1974.

Digital Library

[2]

I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks, vol. 38, pp. 393-422, 2002.

Digital Library

[3]

N. Alon, A. Bar-Noy, N. Linial, and D. Peleg, “A Lower Bound for Radio Broadcast,” J. Computer and System Sciences, vol. 43, pp. 290-298, 1991.

Digital Library

[4]

R. Bar-Yehuda, O. Goldreich, and A. Itai, “Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with No Collision Detection,” Distributed Computing, vol. 5, pp. 67-71, 1991.

Digital Library

[5]

R. Bar-Yehuda, O. Goldreich, and A. Itai, “On the Time-Complexity of Broadcast in Multi-Hop Radio Networks: An Exponential Gap between Determinism and Randomization,” J.Computational and System Sciences, vol. 45, pp. 104-126, 1992.

Digital Library

[6]

A. Cayley, “A Theorem on Trees,” Quarterly J. Math. Oxford Series, vol. 23, pp. 376-378, 1889.

[7]

Y.-C. Cheng and T.G. Robertazzi, “Critical Connectivity Phenomena in Multihop Radio Models,” IEEE Trans. Comm., vol. 36, pp.770-777, 1989.

[8]

B. Chlebus, “Randomized Communication in Radio Networks Chapter,” Handbook of Randomized Computing, P.M. Pardalos, S.Rajasekaran, J.H. Reif, and J.D.P. Rolim, eds., Kluwer Academic, vol. I, pp. 401-456, 2001.

[9]

M. Chrobak, L. Gasieniec, and W. Rytter, “Fast Broadcasting and Gossiping in Radio Networks,” Proc. IEEE Foundation of Computer Science Conf. (FOCS), 2000.

Digital Library

[10]

R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey, and D.E. Knuth, “On the Lambert W Function,” Advances in Computational Math., vol. 5, pp. 329-359, 1996.

[11]

N.G. De Bruijn, Asymptotic Methods in Analysis. Dover, 1981.

[12]

P. Erdös and A. Rényi, “On the Evolution of Random Graphs,” Publication of the Math. Inst. of the Hungarian Academy of Sciences, vol. 5, pp. 17-61, 1960.

[13]

P. Flajolet and R. Sedgewick, Analytic Combinatorics, book in preparation, chapters are available as INRIA research reports, http://algo.inria.fr/flajolet/books, 2006.

[14]

E.N. Gilbert, “Random Plane Networks,” J. Soc. for Industrial and Applied Math, vol. 9, pp. 533-543, 1961.

[15]

P. Gupta and P.R. Kumar, “Critical Power for Asymptotic Connectivity in Wireless Networks,” Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, W.M. McEneaney, G. Yin, and Q. Zhang, Birkhauser, 1998.

[16]

P. Hall, Introduction to the Theory of Coverage Processes. Birkhäuser, 1988.

[17]

T. Hayashi, K. Nakano, and S. Olariu, “Randomized Initialization Protocols for Packet Radio Networks,” Discrete Math. and Theoretical Computer Science, S. Rajasekaran, P. Pardalos, B.Badrinath, and F. Hsu, eds., pp. 221-235, SIAM Press, 2000.

[18]

S. Janson, D.E. Knuth, T. Luczak, and B. Pittel, “The Birth of the Giant Component,” Random Structures & Algorithms, vol. 4, pp.233-358, 1993.

[19]

E.-S. Jung and N. Vaidya, “A Power Control MAC Protocol for Ad Hoc Networks,” Proc. ACM MobiCom '02, pp. 36-47, 2002.

Digital Library

[20]

D.E. Knuth, The Art of Computer Programming—Sorting and Searching, vol. 3. Addison-Wesley, 1973.

[21]

E. Kushilevitz and Y. Mansour, “An $\Omega(D\log (N/D))$ Lower Bound for Broadcast,” Radio Networks SIAM J. Computing, vol. 27, pp. 702-712, 1998.

Digital Library

[22]

D. Liu and M. Prabhakaran, “On Randomized Broadcasting and Gossiping in Radio Networks,” Proc. Int'l Computing and Combinatorics Conf. (COCOON '02), pp. 340-349, 2002.

Digital Library

[23]

R. Meester and R. Roy, Continuum Percolation. Cambridge Univ. Press, 1996.

[24]

R.E. Miles, “On the Homogenous Planar Poisson Point Process,” Math. Biosciences, vol. 6, pp. 85-127, 1970.

[25]

K. Nakano and S. Olariu, “Randomized Initialization Protocols for Ad-Hoc Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 11, pp. 749-759, 2000.

Digital Library

[26]

K. Nakano and S. Olariu, “Energy-Efficient Initialization Protocols for Radio Networks with No Collision Detection,” IEEE Trans. Parallel and Distributed Systems, vol. 11, pp. 851-863, 2000.

Digital Library

[27]

M.D. Penrose, “The Longest Edge of the Random Minimal Spanning Tree,” Annals of Applied Probability, vol. 7, pp. 340-361, 1997.

[28]

M.D. Penrose, “A Strong Law for the Largest Nearest-Neighbour Link between Random Points,” J. London Math. Soc., vol. 60, pp.951-960, 1999.

[29]

M.D. Penrose, “On $k{\hbox{-}}{\rm{Connectivity}}$ for a Geometric Random Graph,” Random Structures & Algorithms, vol. 15, pp. 145-164, 1999.

Digital Library

[30]

M.D. Penrose, Random Geometric Graphs, Oxford Studies in Probability, 2003.

[31]

C.E. Perkins, Ad Hoc Networking. Addison-Wesley, 2001.

[32]

V. Ravelomanana, “Extremal Properties of Three Dimensional Sensor Networks with Applications,” IEEE Trans. Mobile Computing, vol. 3, no. 3, pp. 246-257, July-Sept. 2004.

Digital Library

[33]

L. Santalo, Integral Geometry and Geometric Probability, second ed. Cambridge Univ. Press, 2003.

[34]

P. Santi and D.M. Blough, “The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks,” IEEE Trans. Mobile Computing, vol. 2, no. 1, pp. 25-39, Jan.-Mar. 2003.

Digital Library

[35]

S. Shakkottai, R. Srikant, and N. Shroff, “Unreliable Sensor Grids: Coverage, Connectivity and Diameter,” Ad Hoc Networks J., to appear.

[36]

F. Xue and P.R. Kumar, “The Number of Neighbors Needed for Connectivity of Wireless Networks,” Wireless Networks, vol. 10, pp.169-181, 2004.

Digital Library

Cited By

Bacher ABodini OHwang HTsai T(2017)Generating Random Permutations by Coin TossingACM Transactions on Algorithms10.1145/300990913:2(1-43)Online publication date: 7-Feb-2017
https://dl.acm.org/doi/10.1145/3009909
Farach-Colton MFernández Anta AMosteiro M(2013)Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound)Theoretical Computer Science10.1016/j.tcs.2012.11.030472(60-80)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.tcs.2012.11.030
Myoupo JCheikhna ASow I(2010)A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problemThe Journal of Supercomputing10.1007/s11227-009-0274-952:2(135-148)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1007/s11227-009-0274-9
Show More Cited By

Index Terms

Optimal Initialization and Gossiping Algorithms for Random Radio Networks

Recommendations

Randomized Initialization of a Wireless Multihop Network
HICSS '05: Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences - Volume 09

The initialization problem consists to give a unique identifier ranging from 1 to n for a set of n indistinguishable nodes. We consider here a wireless network where n nodes (processors) are randomly thrown in a square X, uniformly and independently. We ...
Acknowledged broadcasting and gossiping in ad hoc radio networks

A radio network is a collection of transmitter-receiver devices (referred to as nodes). Acknowledged radio broadcasting (ARB) means transmitting a message from one special node called the source to all other nodes and informing the source about its ...
Fast deterministic broadcast and gossiping algorithms for mobile ad hoc networks

We present a mobility resilient deterministic broadcast algorithm with worst-case time complexity of O(nlogn) for ad hoc networks where the nodes possess collision detection capabilities; n is the total number of nodes in the network. The algorithm is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 18, Issue 1

January 2007

142 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Press

Publication History

Published: 01 January 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bacher ABodini OHwang HTsai T(2017)Generating Random Permutations by Coin TossingACM Transactions on Algorithms10.1145/300990913:2(1-43)Online publication date: 7-Feb-2017
https://dl.acm.org/doi/10.1145/3009909
Farach-Colton MFernández Anta AMosteiro M(2013)Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound)Theoretical Computer Science10.1016/j.tcs.2012.11.030472(60-80)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.tcs.2012.11.030
Myoupo JCheikhna ASow I(2010)A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problemThe Journal of Supercomputing10.1007/s11227-009-0274-952:2(135-148)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1007/s11227-009-0274-9
Mo LHe YLiu YZhao JTang SLi XDai GCuller DLiu JWelsh M(2009)Canopy closure estimates with GreenOrbsProceedings of the 7th ACM Conference on Embedded Networked Sensor Systems10.1145/1644038.1644049(99-112)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1644038.1644049
Bomgni AMyoupo JCheikhna AGuizani MMueller PFähnrich KVasilakos AZhang YZhang J(2009)Randomized multi-stage clustering-based geocast algorithms in anonymous wireless sensor networksProceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly10.1145/1582379.1582442(286-291)Online publication date: 21-Jun-2009
https://dl.acm.org/doi/10.1145/1582379.1582442
Gąsieniec L(2009)On efficient gossiping in radio networksProceedings of the 16th international conference on Structural Information and Communication Complexity10.1007/978-3-642-11476-2_2(2-14)Online publication date: 25-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-11476-2_2
Farach-Colton MMosteiro M(2007)Sensor network gossiping or how to break the broadcast lower boundProceedings of the 18th international conference on Algorithms and computation10.5555/1781574.1781603(232-243)Online publication date: 17-Dec-2007
https://dl.acm.org/doi/10.5555/1781574.1781603
Farach-Colton MMosteiro M(2007)Sensor Network Gossiping or How to Break the Broadcast Lower Bound Algorithms and Computation10.1007/978-3-540-77120-3_22(232-243)Online publication date: 17-Dec-2007
https://dl.acm.org/doi/10.1007/978-3-540-77120-3_22

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents