A probabilistic analysis for the range assignment problem in ad hoc networks

ABSTRACT

In this paper we consider the following problem for ad hoc networks: assume that n nodes are distributed in a d-dimensional region, with 1≤d≤3, and assume that all the nodes have the same transmitting range r; how large must r be to ensure that the resulting network is strongly connected? We study this problem by means of a probabilistic approach, and we establish lower and upper bounds on the probability of connectedness. For the one-dimensional case, these bounds allow us to determine a suitable magnitude of r for a given number of nodes and displacement region size. In an alternate formulation, the bounds allow us to calculate how many nodes must be distributed should the transmitting range be fixed. Finally, we investigate the required magnitude of r in the two- and three-dimensional cases through simulation. Based on the bounds provided and on the simulation analysis, we conclude that, as compared to the deterministic case, a probabilistic solution to this range assignment problem achieves substantial energy savings. A number of other potential uses for our analyses are discussed as well

REFERENCES

• 1: Stefano Basagni , Imrich Chlamtac , Danilo Bruschi, A mobility-transparent deterministic broadcast mechanism for ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.799-807, Dec. 1999 [doi>10.1109/90.811446]
• 2: Imrich Chlamtac , András Faragó, A new approach to the design and analysis of peer-to-peer mobile networks, Wireless Networks, v.5 n.3, p.149-156, May 1999 [doi>10.1023/A:1019186624837]
• 3: 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
• 4: W. Feller, An Introduction to Probability Theory and its Applications, John Wiley & Sons, New York, 1950.
• 5: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 6: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 7: S. Janson, T. Luczak, and A. Rucinski, Random Graphs, John Wiley & Sons, New York, 2000.
• 8: 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]
• 9: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 10: 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]
• 11: Shree Murthy , J. J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, Mobile Networks and Applications, v.1 n.2, p.183-197, Oct. 1996 [doi>10.1007/BF01193336]
• 12: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 13: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 14: R. Ramanathan, and R. Rosales-Hain, 'Topology Control of Multihop Wireless Networks using Transmit Power Adjustment", Proc. IEEE Infocom 2000, pp. 404 - 413, 2000.
• 15: S. Ramanathan , Martha Steenstrup, A survey of routing techniques for mobile communications networks, Mobile Networks and Applications, v.1 n.2, p.89-104, Oct. 1996 [doi>10.1007/BF01193330]
• 16: V. Rodoplu, and T. H. Meng, "Minimum Energy Mobile Wireless Networks", IEEE J. Selected Areas in Comm., vol. 17, n. 8, pp. 1333 - 1344, Aug.1999.
• 17: A. Sen, and M. L. Huson, "A New Model for Scheduling Packet Radio Networks", Proc. IEEE Infocom '96, pp. 1116 - 1124, 1996.
• 18: 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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Performance, Theory, Verification