In an ad hoc network, mobile devices communicate with each other in a peer-to-peer fashion; they establish a self-organizing wireless network without the need for base stations or any other preexisting infrastructure. An outstanding feature of this emerging technology is multihop communication. If two devices cannot establish a direct wireless link (because they are too far away from each other), the devices in between act as relays to forward the data from the source to the destination. In other words, each device acts as both a terminal and a node of the network.
A fundamental property of an ad hoc network is its connectivity. Whereas a mobile device in a cellular network is connected if it has a wireless link to at least one base station, the situation in an ad hoc network is more complicated. Since mobile devices also act as relays (routers) for messages of other devices, each single device contributes to the connectivity of the entire network. If a device fails, the connectivity between two other devices might be destroyed. If the spatial density of the devices is too low, the multihop principle for communication does not work at all. In other words, the communication among devices is not guaranteed, but only probabilistic measures can be given.
Bettstetter has studied various aspects of network connectivity using probabilistic methods. “Given a certain random spatial distribution of the devices and a certain radio link model, the network topology is described as a random geometric graph,” he explains. A device is represented by a node and a wireless link by an edge between two nodes. Based on this network model, the following questions are addressed: What is the probability that the complete network is connected, i.e., a wireless multihop path exists between each node pair. How does node mobility affect the connectivity?
The key to answering the first question is to employ Penrose’s theorem on the connectivity for a geometric random graph. “With this theorem, we can give a tight approximation for the critical (r, n)-pairs for n nodes with radio range r on a given area that are required to keep the network connected with a probability close to one,” Bettstetter states. The (r, n)-pairs can also be solved for k-connected networks, accounting for the robustness against node failures, and for wireless networks that suffer from shadow fading.
Selected Publications
- Connectivity of wireless multihop networks in a shadow fading environment
Wireless Networks, September 2005 - On the connectivity of ad hoc networks
The Computer Journal, July 2004 - Failure-resilient ad hoc and sensor networks in a shadow fading environment
IEEE/IFIP Intern. Conf. on Dependable Syst. Networks Workshops, June 2004 - On the minimum node degree and connectivity of a wireless multihop network
ACM MobiHoc, June 2002
Additional Publications
- On the degree distribution of k-connected random networks
- Hop distances and flooding in wireless multihop networks with randomized beamforming
- How does randomized beamforming improve the connectivity of ad hoc networks?
- Connectivity of wireless multihop networks in a shadow fading environment
- Topology properties of ad hoc networks with random waypoint mobility
- Hop distances in homogeneous ad hoc networks
- … Konnektivitätsanalyse von gleich- und normalverteilten drahtlosen Sensornetzen
- On the connectivity of wireless multihop networks with … inhomogeneous range assignment
- How to achieve a connected ad hoc network with homogeneous range assignment …
- On border effects in modeling and simulation of wireless ad hoc networks