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. D. M. Blough, M. Leoncini, G. Resta, and P. Santi, "On the symmetric range assignment problem in wireless ad hoc networks," in Proc. IFIP 17th World Computer Congr., TC1 Stream / 2nd IFIP Int. Conf. Theoretical Computer Science, Aug. 2002, pp. 71-78.
3. G. Calinescu, I. L. Mandoiu, and A. Zelikovsky, "Symmetric connectivity with minimum power consumption in radio networks," in Proc. IFIP 17th World Computer Congr., TC1 Stream / 2nd IFIP Int. Conf. Theoretical Computer Science, Aug. 2002, pp. 119-130.
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. 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 Approximation Algorithms Combinatorial Optimization Problems (APPROX), Aug. 1999, pp. 197-208.
6. T. M. Cover and J. A. Thomas, Elements of Information Theory. New York: Wiley, 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. M. Hajiaghayi, N. Immorlica, and V. S. MIrrokni, "Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks," presented at the ACM Mobicom, New York, Sep. 2003.
12. L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, "Power consumption in packet radio networks," Theoret. Comp. Sci., vol. 243, no. 1-2, pp. 289-305, 2000.
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," presented at the ACM Symp. Principle Distrib. Comput. (PODC), Newport, RI, Jun. 2001.
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. M. D. Penrose, "On k-connectivity for a geometric random graph," Random Structures & Algorithms, vol. 15, pp. 145-164, 1999.
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. 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. 2003.
22. P.-J. Wan and C. Yi, "Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks," presented at the ACM Mobihoc, Tokyo, Japan, May 2004.
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

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Model verification and validation

      • Modeling methodologies

    • Simulation evaluation

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic reasoning algorithms

      • Markov-chain Monte Carlo methods

      • Sequential Monte Carlo methods

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks