Connectivity in Ad Hoc Networks

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

Additional Publications

Related Publications on Flooding