Wireless multi-hop ad hoc communication networks represent an infrastructure-less and selforganized
generalization oftodays wireless cellular networks. Connectivity within such a network
is an important issue. Continuum percolation and technology-driven mutations thereofallow to
address this issue in the static limit and to construct a simple distributed protocol, guaranteeing
strong connectivity almost surely and independently ofvarious typical uncorrelated and correlated
random spatial patterns ofparticipating ad hoc nodes.
Today’s wireless communication mainly relies on cellular networks [1–3]. At ?rst,
the sending mobile device directly connects to its nearest base station. A backbone network
then routes the communication packets to the cell, where the intended receiving mobile device is registered. Finally, the cell’s base station transmits the passed-by message
to the latter. As part ofthe centralized backbone infrastructure each base station
acts as a router, possesses the network information, controls the single-hop communications
within its cell and assigns diFerent channels to its various mobile clients.
The base stations need to be placed according to some optimized coverage layout.
This requires an enormous planning eFort ahead ofoperation and leads to a static
infrastructure, hard to change and adapt to new, revised needs. This costly inHexibility
motivates a Hexible and infrastructure-less peer-to-peer concept: selforganizing wireless
mobile ad hoc networks [4–7].
In a wireless ad hoc network, a sending mobile device uses inbetween mobile devices
to communicate with the intended receiver. Such a multi-hop connection requires each
mobile device to have additional router functionality. As a central control authority is
missing, the participating devices need coordination amongst themselves to ensure network
connectivity, eJcient discovery and execution ofend-to-end routes and avoidance
ofdata packet collisions on shared radio channels; ofcourse, mobility ofthe devices
also has an impact on the network performance, which has to be coped with. Contrary
to these global network features, the selforganizing coordination rules, called protocols
in the jargon ofelectrical engineers, have to be local. Due to its limited transmission
range, a mobile device is able to communicate only with its current spatial neighbors.
Hence, it can only extract information on its local surrounding. Since this is the only
input into the coordination rule, the latter is by de?nition local. Upon execution, it
readjusts for example the device’s transmission power to its new surrounding.
In this paper we focus on the important connectivity issue and ask: what is a good
local coordination rule for transmission power management, which almost surely guarantees
global connectivity for the whole network? We employ a simple static model for
ad hoc communication networks. This allows a connection to continuum percolation
theory [8,9] based on random geometric graphs [10,11]. The spatially distributed ad
hoc devices correspond to nodes, which are more or less locally connected by communication
links. Two nodes establish a mutual link, only ifthe ?rst node lies within
the transmission range ofthe second and vice versa. For the case ofconstant, isotropic
transmission ranges, a further mapping onto the classical picture of continuum percolation
[12,13], stemming from the transport physics in continuous random media, is
straightforward: whenever discs with radius equaling halfofthe transmission range are
placed around two nodes and overlap, the two nodes are linked.
Continuum percolation allows to study, for example, the dependence of the probability
for strong connectivity on the transmission range and to ?nd a critical range, above
which the ad hoc network graph is almost surely connected. The critical transmission
range can be translated into a critical node neighborhood degree ngbcrit . Hence,
a simple local coordination rule would be for each node to adjust its transmission
power to yield a little above ngbcrit neighbors. As we will demonstrate, such a rule
is not Hexible enough to perform equally well in various diFerent environments, like
homogeneous vs. heterogeneous random spatial arrangements ofnodes or homogeneous
vs. heterogeneous propagation media. Fortunately, such a rule is able to give
some guidance to develop local coordination rules with improved adaptation properties.
In some respect, these new rules represent technology-driven mutations of the continuum percolation problem and demonstrate the usefulness to combine real-world
needs in electrical engineering with modi?ed concepts ofstatistical physics.
In Section 2 a precise de?nition ofrandom geometric graphs in the context of
wireless ad hoc communication networks is given; various spatial point patterns, uncorrelated
and correlated, are introduced. In Section 3 standard continuum percolation
based on discs with constant and random radius is applied to ad hoc networks to obtain
?rst rigorous statements on coordination rules for connectivity. A mutation of continuum
percolation is presented in Section 4, which directly leads to a distributed, local
coordination rule, Hexible enough to cope with various environments. A conclusion and
outlook is given in Section 5.
For wireless mobile ad hoc communication networks connectivity represents an important
issue. In a selforganizing manner, the participating ad hoc nodes have to tune
their transmission powers to establish direct one-hop communication links to their spatial
neighbors and to be able to reach all others via multihop routes. In the static limit,
two-dimensional continuum percolation based on discs with constant or random radius
can be mapped onto arti?cial link coordination rules with constant or random transmission
power. Basically the transmission powers have to be chosen above a percolation
threshold in order to guarantee strong network connectivity almost surely. However,
the percolation threshold does show a sensitive dependence on the speci?c spatial patterning
ofthe ad hoc nodes. DiFerent classes ofuncorrelated and correlated random
point patterns, like homogeneous, multifractal or Manhattan-like distributions, make a
big diFerence. The arti?cial link rules are not Hexible enough to adapt to local spatial
inhomogeneities. A local generalization ofthese rules leads to the minimum-link-degree
rule. It can be viewed as a step towards a selforganizing mutation of continuum percolation.
It requires each ad hoc node to be connected to a minimum number ofclosest
neighbors, which sets a lower bound on the node’s transmission power. This node,
on the other hand, might be forced to increase its transmission power further, in order
to establish an additional communication link to another node, which belongs to
the greater vicinity and has not yet reached the required minimum number ofclosest
neighbors. This distributed rule is able to counterbalance local spatial inhomogeneities
occurring in the random point patterns. As a function of average transmission power
the percolation thresholds associated to the various considered classes ofrandom point
patterns almost collapse onto each other and are tremendously reduced, when compared
to the outcomes with the arti?cial rules.
Compared to other local link rules yielding strongly connected networks, the presented
minimum-link-degree rule is simple. For example, the Rodoplu and Meng algorithm
[32] relies on GPS-based position knowledge ofthe ad hoc nodes to construct
a link enclosure for each node; the construction also requires knowledge about the
assumed uniform path-loss exponent, which can be seen as another drawback of this
algorithm. Another proposal [33] requires ad hoc nodes to come with directional antennas;
strong network connectivity is then guaranteed once each node has neighbors
in each angular sector. Rules like these require more technological equipment for the
ad hoc nodes. In terms ofthe simplicity principle, the presented minimum-link-degree
rule appears to be more attractive. It also has the advantage that it will work in
a heterogeneous propagation medium, where the path-loss exponent is a function of
position, distance and direction. A generalization ofthe distributed minimum-link-degree
rule, which so far only has been developed for the static limit, towards mobile ad hoc
networks is straightforward. These last two issues will be discussed in more detail in
future work. Finding eJcient distributed coordination rules, i.e., protocols, for connectivity is certainly
one important issue for ad hoc communication networks, but there are de?nitely
also others: power consumption, eJcient routing discovery and execution, medium
access control, interference, quality of service, and end-to-end throughput. The construction
ofan optimized protocol for one part alone, needs not be the overall best
for all ofthe partially conHicting entities considered together. Clearly, the design ofa
rather complex, but still simple overall protocol is called for. It is possible that such an
optimized protocol might lead to small-world or scale-free geometric-graph topologies,
which are already observed and discussed for Internet and biochemical communication
networks [34,35].