Asymptotic critical total power for k-connectivity of wireless networks

ABSTRACT

An important issue in wireless ad hoc networks is to reduce the transmission power subject to certain connectivity requirement. In this paper, we study the fundamental scaling law of the minimum total power (termed as critical total power) required to ensure k-connectivity in wireless networks. Contrary to several previous results that assume all nodes use a (minimum) common power, we allow nodes to choose different levels of transmission power. We show that under the assumption that wireless nodes form a homogeneous Poisson point process with density λ in a unit square region [0, 1]², the critical total power required to maintain k-connectivity is Θ ((Γ(c/2+k)/(k-1)!)λ^1-c/2) with probability approaching one as λ goes to infinity, where c is the path loss exponent. If k also goes to infinity, the expected critical total power is of the order of k^c/2λ^1-c/2. Compared with the results that all nodes use a common critical transmission power for maintaining k-connectivity, we show that the critical total power can be reduced by an order of (log λ)^c/2 by allowing nodes to optimally choose different levels of transmission power. This result is not subject to any specific power/topology control algorithm, but rather a fundamental property of wireless networks.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.71-82, August 25-30, 2002
• 3: Gruia Calinescu , Ion I. Mandoiu , Alexander Zelikovsky, Symmetric Connectivity with Minimum Power Consumption in Radio Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.119-130, August 25-30, 2002
• 4: [4] G. Calinescu and P.-J. Wan, "Range assignment for high connectivity in wireless ad hoc networks," in Proc. Adhoc-Now, Oct. 2003.
• 5: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, On the power assignment problem in radio networks, Mobile Networks and Applications, v.9 n.2, p.125-140, April 2004 [doi>10.1023/B:MONE.0000013624.32948.87]
• 6: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.197-208, August 08-11, 1999
• 7: [7] M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, "Closing the gap in the capacity of wireless networks via percolation theory," IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1009-1018, Mar. 2007.
• 8: [8] J. Gomez and A. Campbell, "A case for variable-range transmission power control in wireless multihop networks," in Proc. IEEE INFOCOM , Jun. 2004.
• 9: [9] P. Gupta and P. R. Kumar, "Critical power for asymptotic connectivity in wireless networks," in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming.:, 1998.
• 10: MohammadTaghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939016]
• 11: [11] P. Hall, Introduction to the Theory of Coverage Processes. New York: Wiley, 1988.
• 12: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power consumption in packet radio networks, Theoretical Computer Science, v.243 n.1-2, p.289-305, July 28, 2000 [doi>10.1016/S0304-3975(98)00223-0]
• 13: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 14: [14] N. Li and J. Hou, "Topology control in heterogeneous wireless networks: Problems and solutions," in Proc. IEEE INFOCOM, Mar. 2004.
• 15: [15] N. Li, J. Hou, and L. Sha, "Design and analysis of a mst-based topology control algorithm," in Proc. IEEE INFOCOM, Apr. 2003.
• 16: [16] S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar, "Power control in ad hoc networks: Theory, architecture, algorithm and implementation of the compow protocol," in Proc. European Wireless 2002. Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, Florence, Italy, Feb. 25-28, 2002, pp. 156-162.
• 17: [17] M. Penrose, Random Geometric Graphs. Oxford, U.K.: Oxford Univ. Press, 2003.
• 18: [18] M. D. Penrose, "The longest edge of the random minimal spanning tree," Ann. Appl. Probabil., vol. 7, pp. 340-361, 1997.
• 19: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 20: [20] M. D. Penrose and A. Pisztora, "Large deviations for discrete and continuous percolation," Adv. Appl. Probabil., vol. 28, 1996.
• 21: [21] T. K. Philips, S. S. Panwar, and A. N. Tantawi, "Connectivity properties of a packet radio network model," IEEE Trans. Inf. Theory, vol. 35, no. 5, pp. 1044-1047, 1989.
• 22: [22] B. Rengarajan, J. Chen, S. Shakkottai, and T. S. Rappaport, "Connectivity of sensor networks with power control," in Proc. 37th Asilomar Conf. Signals, Systems and Computers, Nov. 2003.
• 23: [23] V. Rodoplu and T. H. Meng, "Minimum energy mobile wireless networks," IEEE J. Sel. Areas = Commun., vol. 17, no. 8, pp. 1633-1639, 1999.
• 24: Paolo Santi , Douglas M. Blough, The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.1, p.25-39, January 2003 [doi>10.1109/TMC.2003.1195149]
• 25: [25] J. M. Steele, "Growth rates of euclidean minimal spanning trees with power weighted edges," Ann. Probabil., vol. 16, no. 4, 1988.
• 26: Peng-Jun Wan , Chih-Wei Yi, Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989461]
• 27: [27] J. E. Yukich, "Asymptotics for weighted minimal spanning trees on random points," Stochastic Processes and Their Applications, vol. 85, pp. 123-128, 2000.
• 28: [28] H. Zhang and J. Hou, "On the critical total power for asymptotic k-connectivity in wireless networks," Comput. Sci. Dept., Univ. of Illinois, Urbana-Champaign, Tech. Rep. UIUCDCS-R-2004-2454, Jul. 2004 [Online]. Available: http://www.lion.cs.uiuc.edu/hzhang3/papers/k-connect_tech.ps
• 29: [29] H. Zhang and J. Hou, "Capacity of wireless ad hoc networks under ultra wide band with power constraint," in Proc. IEEE INFOCOM, Mar. 2005.
• 30: [30] H. Zhang and J. Hou, "On the critical total power for asymptotic k-connectivity in wireless networks," in Proc. IEEE INFOCOM, Mar. 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Performance

Keywords:
connectivity, critical power, power control, wireless networks