On the asymptotic minimum transporting energy and its implication on the wireless network capacity

ABSTRACT

In this paper we study the asymptotic minimum energy (which is defined as the minimum transporting energy) required to transport (via multiple hops) data packets from a source to a destination. Under the assumptions that nodes are distributed according to a Poisson point process with node density n in a unit-area square and the distance between a source and a destination is of constant order, we prove that the minimum transporting energy is Θ (n^(1-α)/2) with probability approaching one as the node density goes to infinity, where α is the path loss exponent.

We demonstrate use of the derived results to obtain the bounds of the capacity of wireless networks that operate in UWB. In particular, we prove the transport capacity of UWB-operated networks is Θ (n^(α-1)/2) with high probability. We also carry out simulations to validate the derived results and to estimate the constant factor associated with the bounds on the minimum energy. The simulation results indicate that the constant associated with the minimum energy converges to the source-destination distance.

REFERENCES

• 1: M. Bhardwaj and A. P. Chandrakasan, "Bounding the lifetime of sensor network via optimal role assignments," presented at the IEEE Infocom, New York, Jun. 2002.
• 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: G. Calinescu and P.-J. Wan, "Range assignment for high connectivity in wireless ad hoc networks," presented at the Adhoc Now, Montreal, QC, Canada, Oct. 2003.
• 5: 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
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, "Closing the gap in the capacity of random wireless networks," presented at the IEEE Int. Symp. Inf. Theory (ISIT'04), Chicago, IL, Jun. 2004.
• 8: J. Gomez and A. Campbell, "A case for variable-range transmission power control in wireless multihop networks," presented at the IEEE Infocom, Hong Kong, Jun. 2004.
• 9: G. Grimmett, Percolation. New York: Springer-Verlag, 1998.
• 10: 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. Boston, MA: Birkhauser, 1998.
• 11: 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]
• 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: N. Li and J. Hou, "Topology control in heterogeneous wireless networks: Problems and solutions," presented at the IEEE Infocom, Hong Kong, Mar. 2004.
• 15: N. Li, J. Hou, and L. Sha, "Design and analysis of a MST-based topology control algorithm," presented at the IEEE Infocom, San Francisco, CA, Apr. 2003.
• 16: R. Negi and A. Rajeswaran, "Capacity of power constrained ad-hoc networks," presented at the IEEE Infocom, Hong Kong, Mar. 2004.
• 17: M. D. Penrose, "The longest edge of the random minimal spanning tree," Annal. Appl. Probabil., vol. 7, pp. 340-361, 1997.
• 18: 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]
• 19: B. Rengarajan, J. Chen, S. Shakkottai, and T. S. Rappaport, "Connectivity of sensor networks with power control," in Proc. 37th Asilomar Conf. Signals, Syst. Comput., Nov. 2003.
• 20: V. Rodoplu and T. H. Meng, "Minimum energy mobile wireless networks," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1633-1639, Aug. 1999.
• 21: 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-March 2003 [doi>10.1109/TMC.2003.1195149]
• 22: 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]
• 23: H. Zhang and J. Hou, "Capacity of wireless ad hoc networks under ultra wide band with power constraint," presented at the IEEE Infocom, Miami, FL, Mar. 2005.
• 24: H. Zhang and J. Hou, "On the critical total power for asymptotic k-connectivity in wireless networks," presented at the IEEE Infocom, Miami, FL, Mar. 2005.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
asymptotic analysis, capacity, ultra wide band (UWB), wireless network