A statistical analysis of the long-run node spatial distribution in mobile ad hoc networks

ABSTRACT

In this paper, we analyze the node spatial distribution of mobile wireless ad hoc networks. Characterizing this distribution is of fundamental importance in the analysis of many relevant properties of mobile ad hoc networks, such as connectivity, average route length, and network capacity. In particular, we have investigated under what conditions the node spatial distribution resulting after a large number of mobility steps resembles the uniform distribution. This is motivated by the fact that the existing theoretical results concerning mobile ad hoc networks are based on this as sumption. In order to test this hypothesis, we performed extensive simulations using two well-known mobility models: the random waypoint model, which resembles intentional movement, and a Brownian-like model, which resembles non-intentional movement. Our analysis has shown that in the Brownian-like motion the uniformity assumption does hold,and that the intensity of the concentration of nodes in the center of the deployment region that occurs in the ran dom waypoint model heavily depends on the choice of some mobility parameters. For extreme values of these parameters,the uniformity assumption is impaired.

REFERENCES

• 1: Ionuţ D. Aron , Sandeep K. S. Gupta, Analytical comparison of local and end-to-end error recovery in reactive routing protocols for mobile ad hoc networks, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.69-76, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346866]
• 2: F. Avram, D. Bertsimas, "The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model: a Unified Approach", The Annals of Applied Probability, Vol. 2, n. 1, pp. 113--130, 1992.
• 3: Christian Bettstetter, Smooth is better than sharp: a random mobility model for simulation of wireless networks, Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.19-27, July 2001, Rome, Italy [doi>10.1145/381591.381600]
• 4: C. Bettstetter, O. Krause, "On Border Effects in Modeling and Simulation of Wireless Ad Hoc Networks", Proc. 3rd IEEE International Conference on Mobile and Wireless Communication Networks (MWCMN), 2001.
• 5: D.M. Blough, G. Resta, P. Santi, "A Statistical Analysis of the Long-Run Node Spatial Distribution in Mobile Ad Hoc Networks", Tech. Rep. IIT-TR-03/2002, Istituto di Informatica e Telematica, Pisa - Italy, March 2002.
• 6: H. Dette, N. Heinze, "The Limit Distribution of the Largest Nearest-Neighor Link in the Unit d-Cube", Journal of Applied Probability, Vol. 26, pp. 67--80, 1989.
• 7: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 8: Jacob E. Goodman , Joseph O'Rourke, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 9: M. Grossglauser, D. Tse, "Mobility Increases the Capacity of Ad Hoc Wireless Networks", Proc. IEEE INFOCOM 2001, pp. 1360--1369, 2001.
• 10: P. Gupta, P.R. Kumar, "Critical Power for Asymptotic Connectivity in Wireless Networks", Stochastic Analysis, Control, Optimization and Applications, Birkhauser, Boston, pp. 547--566, 1998.
• 11: P. Gupta, P.R. Kumar, "The Capacity of Wireless Networks", IEEE Trans. Information Theory, Vol. 46, n. 2, pp. 388--404, 2000.
• 12: D.B. Johnson, D.A. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks", Mobile Computing, Kluwer Academic Publishers, pp. 153--181, 1996.
• 13: 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]
• 14: V.F. Kolchin, B.A. Sevast'yanov, V.P. Chistyakov, Random Allocations, V.H. Winston and Sons, Washington D.C., 1978.
• 15: S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. Srivastava, "Coverage Problems in Wireless Ad Hoc Sensor Networks", Proc. IEEE Infocom 2001, pp. 1380--1387, 2001.
• 16: Seapahn Meguerdichian , Sasa Slijepcevic , Vahag Karayan , Miodrag Potkonjak, Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501432]
• 17: Asis Nasipuri , Robert Castañeda , Samir R. Das, Performance of multipath routing for on-demand protocols in mobile ad hoc networks, Mobile Networks and Applications, v.6 n.4, p.339-349, Aug. 2001 [doi>10.1023/A:1011426611520]
• 18: M.D. Penrose, "The Longest Edge of the Random Minimal Spanning Tree", The Annals of Applied Probability, Vol. 7, n. 2, pp. 340--361, 1997.
• 19: M.D. Penrose, J.E. Yukich, "Central Limit Theorems for Some Graphs in Computational Geometry", to appear in Annals of Applied Probability.
• 20: Paolo Santi , Douglas M. Blough , Feodor Vainstein, A probabilistic analysis for the range assignment problem in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501446]
• 21: J.M. Steele, "Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges", Annals of Probability, Vol. 16, pp. 1767--1787, 1988.
• 22: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]

INDEX TERMS

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

General Terms:
Performance, Theory

Keywords:
Brownian-like motion, mobility modeling, node spatial distribution, random waypoint motion, wireless ad hoc networks