© 2004 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
On the Connectivity of Ad Hoc Networks
Technische Universität München (TUM), Inst. of Communication Networks, Munich, Germany NTT DoCoMo Euro-Labs, Future Networking Lab, Munich, Germany
This paper presents a framework for the calculation of stochastic connectivity properties of wireless multihop networks. Assuming that n nodes, each node with transmission range r0, are distributed according to some spatial probability density function, we study the level of connectivity of the resulting network topology from three viewpoints. First, we analyze the number of neighbors of a given node. Second, we study the probability that there is a communication path between two given nodes. Third, we investigate the probability that the entire network is connected, i.e. each node can communicate with every other node via a multihop path. For the last-mentioned issue, we compute a tight approximation for the critical (r0,n) pairs that are required to keep the network connected with a probability close to one. In fact, the problem is solved for the general case of a k-connected network, accounting for the robustness against node failures. These issues are studied for uniformly distributed nodes (with and without ‘border effects’), Gaussian distributed nodes, and nodes that move according to the commonly used random waypoint mobility model. The results are of practical value for the design and simulation of wireless sensor and mobile ad hoc networks.
Received 7 May 2003. Revised 30 October 2003.