Extremal Properties of Three-Dimensional Sensor Networks with Applications
|
In this paper, we analyze various critical transmitting/sensing ranges for connectivity and coverage in three-dimensional sensor networks. As in other large-scale complex systems, many global parameters of sensor networks undergo phase transitions: For a given property of the network, there is a critical threshold, corresponding to the minimum amount of the communication effort or power expenditure by individual nodes, above (respectively, below) which the property exists with high (respectively, a low) probability. For sensor networks, properties of interest include simple and multiple degrees of connectivity/coverage. First, we investigate the network topology according to the region of deployment, the number of deployed sensors, and their transmitting/sensing ranges. More specifically, we consider the following problems: Assume that n nodes, each capable of sensing events within a radius of r, are randomly and uniformly distributed in a 3-dimensional region {\cal{R}} of volume V, how large must the sensing range {\rm{R_{SENSE}}} be to ensure a given degree of coverage of the region to monitor? For a given transmission range {\rm{R_{TRANS}}}, what is the minimum (respectively, maximum) degree of the network? What is then the typical hop-diameter of the underlying network? Next, we show how these results affect algorithmic aspects of the network by designing specific distributed protocols for sensor networks.
[1] 246 I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, Wireless Sensor Networks: A Survey Computer Networks, vol. 38, pp. 393-422, 2002.
[2] N. Alon and J. Spencer, The Probabilistic Method. New York: Wiley, 1992.
[3] 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.
[4] 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. Computer and System Sciences, vol. 45, pp. 104-126, 1992.
[5] S. Basagni and I. Chlamtac, A Mobility-Transparent Deterministic Broadcast Mechanism for Ad Hoc Networks IEEE/ACM Trans. Networking, vol. 7, pp. 799-807, 1999.
[6] R. Battiti, A.A. Bertossi, and M.A. Bonuccelli, Assigning Codes in Wireless Networks: Bounds and Scaling Properties Wireless Networks, vol. 5, pp. 195-209, 1999.
[7] Berkeley Wireless Research Center,http:/bwrc.eecs.berkeley. edu, 2004.
[8] C. Bettstetter, On the Minimum Node Degree and Connectivity of a Wireless Multihop Network Proc. ACM Mobihoc '02, pp. 80-91, 2002.
[9] B. Bollobas, Random Graphs. London: Academic Press, 1985.
[10] A. Cayley, A Theorem on Trees Quarterly J. Math. Oxford Series, vol. 23, pp. 376-378, 1889.
[11] Center for Embedded Networked Sensing,http:/cens.ucla.edu/, 2004.
[12] L. Chatzigiannakis, S. Nikoletseas, and P. Spirakis, Efficient and Robust Protocols for Local Detection and Propagation in Smart Dust Protocols ACM/Kluwer Mobile Networks and Applications, 2004.
[13] Y.-C. Cheng and T.G. Robertazzi, Critical Connectivity Phenomena in Multihop Radio Models IEEE Trans. Comm., vol. 36, pp. 770-777, 1989.
[14] 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.
[15] N.G. De Bruijn, Asymptotic Methods in Analysis. New York: Dover, 1981.
[16] O. Dousse, P. Thiran, and M. Hasler, Connectivity in Ad Hoc and Hybrid Network Proc. INFOCOM, 2002.
[17] P. Erdos and A. Renyi, On the Evolution of Random Graphs Publ. Math. Inst. Hung. Acad. Sci., vol. 5, pp. 17-61, 1960.
[18] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, Next Century Challenges: Scalable Coordination in Sensor Networks Proc. IEEE/ACM Int'l Conf. Mobile Computing and Networking, pp. 263-270, 1999.
[19] I. Finocchi, A. Panconesi, and R. Silvestri, Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms Proc. ACM-SIAM Symp. Discrete Algorithms, pp 606-615, 2002.
[20] E. Friedgut and G. Kalai, Every Monotone Graph Property Has a Sharp Threshold Proc. Am. Math. Soc., vol. 124, pp. 2993-3002, 1996.
[21] W. Gautschi, The Incomplete Gamma Functions Since Tricomi, In Tricomi's Ideas and Contemporary Applied Mathematics Atti dei Convegni Lincei, Accademia Nazionale dei Lincei, Roma, vol. 147, pp. 203-237, 1998.
[22] E.N. Gilbert, Random Plane Networks J. Soc. Industrial and Applied Math., vol. 9, pp. 533-543, 1961.
[23] A. Goel, R. Sanatan, and B. Krishnamachari, Sharp Thresholds for Monotone Properties in Random Geometric Graphs ACM Symp. Theory of Computing, to appear in 2004.
[24] 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, Boston: Birkhauser, 1998.
[25] P. Gupta and P.R. Kumar, Internet in the Sky: The Capacity of Three Dimensional Wireless Networks Comm. in Information and Systems, vol. 1, pp. 33-49, 2001.
[26] P. Hall, Introduction to the Theory of Coverage Processes. Boston: Birkhauser, 1988.
[27] L. Hu, Distributed Code Assignments for CDMA Packet Radio Network IEEE/ACM Trans. Networking, vol. 1, pp. 668-677, 1993.
[28] X. Hong, M. Gerla, and H. Wang, Load-Balance, Energy-Aware Communication for Mars Sensor Network Proc. IEEE Aerospace Conf., 2002.
[29] 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.
[30] S. Janson, T. Luczak, and A. Rucinski, Random Graphs. New York: John Wiley, 2000.
[31] E.S. Jung and N. Vaidya, A Power Control MAC Protocol for Ad Hoc Networks Proc. ACM Mobicom '02, pp. 36-47, 2002.
[32] B. Krishnamachari, S.B. Wicker, and R. Bejar, Phase Transition Phenomena in Wireless Ad-Hoc Networks Proc. IEEE GlobeCom '01, 2001.
[33] B. Krishnamachari, R. Bejar, and S.B. Wicker, Distributed Problem Solving and the Boundaries of Self-Configuration in Multi-Hop Wireless Networks Proc. 35th Hawaii Int'l Conf. System Sciences, 2001.
[34] B. Krishnamachari, S.B. Wicker, R. Bejar, and M. Pearlman, Critical Density Thresholds in Distributed Wireless Networks Comm., Information, and Network Security, H. Bhargava, H.V. Poor, V. Tarokh, and S. Yoon, eds., Kluwer Publishers, 2002.
[35] Computer Science and Telecommunication Board, Embedded Everywhere: A Research Agenda for Networked Systems of Embedded Computers, National Research Council, Washington, D.C., 2001.
[36] N. Malpani, J.L. Welch, and N. Vaidya, Leader Election Algorithms for Mobile Ad Hoc Networks Proc. Fourth Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm., pp. 96-103, 2000.
[37] M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method. Berlin: Springer, 2002.
[38] C. McDiarmid, Random Channel Assignment in the Plane Random Structures&Algorithms, vol. 22, pp. 187-212, 2003.
[39] R. Meester and R. Roy, Continuum Percolation. Cambridge: Cambridge Univ. Press, 1996.
[40] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava, Coverage Problems in Wireless Ad-Hoc Sensor Networks Proc. IEEE Infocom '01, pp. 1380-1387, 2001.
[41] S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, Exposure in Wireless Ad-Hoc Sensor Networks Proc. ACM Mobicom '01, pp. 139-150, 2001.
[42] R.E. Miles, On the Homogeneous Planar Poisson Point Process Math. Biosciences, vol. 6, pp. 85-127, 1970.
[43] R.E. Miles, Asymptotic Coverage and Concentration Probabilities for Poisson Spheres Annals of Math. Statistics, vol. 40, pp. 1160, 1969.
[44] Nasa/JPL Sensor Webs Project,http:/sensorwebs.jpl.nasa.gov/, 2004.
[45] M.D. Penrose, The Longest Edge of the Random Minimal Spanning Tree Annals of Applied Probability, vol. 7, pp. 340-361, 1997.
[46] M.D. Penrose, Onk-Connectivity for a Geometric Random Graph Random Structures&Algorithms, vol. 15, pp. 145-164, 1999.
[47] M.D. Penrose, Random Geometric Graphs. Oxford Studies in Probability, 2003.
[48] C.E. Perkins, Ad Hoc Networking. Addison-Wesley, 2001.
[49] T.K. Philips, S.S. Panwar, and A.N. Tantawi, Connectivity Properties of a Packet Radio Network Model IEEE Trans. Information Theory, vol. 35, pp. 1044-1047, 1989.
[50] P. Piret, On the Connectivity of Radio Networks IEEE Trans. Information Theory, vol. 37, pp. 1490-1492, 1991.
[51] J.G. Proakis, E.M. Sozer, J.A. Rice, and M. Stojanovic, Shallow Water Acoustic Networks IEEE Comm. Magazine, vol. 39, pp. 114-119, 2001.
[52] V. Ravelomanana, Asymptotic Critical Ranges for Coverage Properties in Wireless Sensor Networks technical report, Universite de Paris XIII, (submitted).
[53] L. Santalo, Integral Geometry and Geometric Probability. Cambridge Univ. Press, 2003.
[54] 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.
[55] S. Shakkottai, R. Srikant, and N. Shroff, Unreliable Sensor Grids: Coverage, Connectivity and Diameter Ad Hoc Networks, to appear in 2004, also published in Proc. IEEE Infocom, 2003.
[56] N. Temme, Uniform Asymptotic Expansions of the Incomplete Gamma Functions and the Incomplete Beta Functions Math. Comput., vol. 29, pp. 1109-1114, 1975.
[57] N. Temme, The Asymptotic Expansion of the Incomplete Gamma Function SIAM J. Math. Anal., vol. 10, pp. 757-766, 1979.
[58] Wireless Integrated Sensor Networks, http://www.janet.ucla.eduWINS, 2004.
[59] Y. Xu, J.S. Heidemann, and D. Estrin, Geography-Informed Energy Conservation for Ad Hoc Routing Proc. ACM Mobicom '01, pp. 70-84, 2001.
[60] F. Xue and P.R. Kumar, The Number of Neighbors Needed for Connectivity of Wireless Networks Wireless Networks, vol. 10, pp. 169-181, 2004.
Index Terms:
Sensor networks, ad hoc networks, coverage, connectivity, hop-diameter, minimum/maximum degrees, transmitting/sensing ranges, analytical methods, energy consumption, topology control.
Citation:
Vlady Ravelomanana, "Extremal Properties of Three-Dimensional Sensor Networks with Applications," IEEE Transactions on Mobile Computing, vol. 3, no. 3, pp. 246-257, July 2004, doi:10.1109/TMC.2004.23
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb