skip to main content
article

Asymptotic critical total power for k-connectivity of wireless networks

Published: 02 April 2008 Publication History

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]2, 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 kc/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]
{1} M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tables.: National Bureau of Standards, 1972, Tenth Printing with corrections.
[2]
{2} D. M. Blough, M. Leoncini, G. Resta, and P. Santi, "On the symmetric range assignment problem in wireless ad hoc networks," in Proc. 2nd IFIP Int. Conf. Theoretical Computer Science, Aug. 2002.
[3]
{3} G. Calinescu, I. L. Mandoiu, and A. Zelikovsky, "Symmetric connectivity with minimum power consumption in radio networks," in Proc. 17th IFIP World Computer Congress, Aug. 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]
{5} A. E. F. Clementi, P. Penna, and R. Silvestri, "On the power assignment problem in radio networks," Mobile Networks and Applications, vol. 9, no. 2, Apr. 2004.
[6]
{6} A. E. F. Clementi, P. Penna, and R. Silvestri, "Hardness results for the power range assignment problem in packet radio networks," in Proc. 2nd Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Aug. 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]
{10} M. Hajiaghayi, N. Immorlica, and V. S. MIrrokni, "Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks," in Proc. ACM Mobicom, Sep. 2003.
[11]
{11} P. Hall, Introduction to the Theory of Coverage Processes. New York: Wiley, 1988.
[12]
{12} L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, "Power consumption in packet radio networks," Theoretical Computer Science, vol. 243, no. 1-2, pp. 289-305, 2000.
[13]
{13} L. Li, J. Halpern, V. Bahl, Y. M. Wang, and R. Wattenhofer, "Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks," in Proc. ACM Symp. Principle of Distributed Computing (PODC), Jun. 2001.
[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]
{19} M. D. Penrose, "On k-connectivity for a geometric random graph," Random Structures and Algorithms, vol. 15, pp. 145-164, 1999.
[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]
{24} P. Santi and D. M. Blough, "The critical transmitting range for connectivity in sparse wireless ad hoc networks," IEEE Trans. Mobile Comput., vol. 2, no. 1, pp. 25-39, 2003.
[25]
{25} J. M. Steele, "Growth rates of euclidean minimal spanning trees with power weighted edges," Ann. Probabil., vol. 16, no. 4, 1988.
[26]
{26} P.-J. Wan and C. Yi, "Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks," in Proc. ACM Mobihoc, May 2004.
[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.

Cited By

View all
  • (2015)Analysis of Stochastic $k$-Coverage and Connectivity in Sensor Networks With Boundary DeploymentIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2014.237969916:4(1861-1871)Online publication date: 31-Jul-2015
  • (2015)Using central nodes for efficient data collection in wireless sensor networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.08.04191:C(425-437)Online publication date: 14-Nov-2015
  • (2014)Connectivity analysis of indoor wireless sensor networks using realistic propagation modelsProceedings of the 17th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems10.1145/2641798.2641803(13-20)Online publication date: 21-Sep-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 2
April 2008
244 pages

Publisher

IEEE Press

Publication History

Published: 02 April 2008
Published in TON Volume 16, Issue 2

Author Tags

  1. connectivity
  2. critical power
  3. power control
  4. wireless networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)Analysis of Stochastic $k$-Coverage and Connectivity in Sensor Networks With Boundary DeploymentIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2014.237969916:4(1861-1871)Online publication date: 31-Jul-2015
  • (2015)Using central nodes for efficient data collection in wireless sensor networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.08.04191:C(425-437)Online publication date: 14-Nov-2015
  • (2014)Connectivity analysis of indoor wireless sensor networks using realistic propagation modelsProceedings of the 17th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems10.1145/2641798.2641803(13-20)Online publication date: 21-Sep-2014
  • (2013)Improved multicriteria spanners for Ad-Hoc networks under energy and distance metricsACM Transactions on Sensor Networks10.1145/2489253.24892549:4(1-25)Online publication date: 23-Jul-2013
  • (2012)Throughput and energy efficiency in wireless ad hoc networks with Gaussian channelsIEEE/ACM Transactions on Networking10.1109/TNET.2011.215823720:1(15-28)Online publication date: 1-Feb-2012
  • (2011)Undirected connectivity of sparse Yao graphsProceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing10.1145/1998476.1998482(25-32)Online publication date: 9-Jun-2011
  • (2010)Improved multi-criteria spanners for ad-hoc networks under energy and distance metricsProceedings of the 29th conference on Information communications10.5555/1833515.1833517(6-10)Online publication date: 14-Mar-2010
  • (2010)Near-optimal multicriteria spanner constructions in wireless ad hoc networksIEEE/ACM Transactions on Networking10.1109/TNET.2010.205338118:6(1963-1976)Online publication date: 1-Dec-2010

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media