Due to their inherent complexity, engineered wireless multihop ad hoc communication networks represent a technological challenge. Having no mastering infrastructure the nodes have to selforganize themselves in such a way that for example network connectivity, good data traffic performance and robustness are guaranteed. In this contribution the focus is on routing and congestion control. First, random data traffic along shortest path routes is studied by simulations as well as theoretical modeling. Measures of congestion like end-to-end time delay and relaxation times are given. A scaling law of the average time delay with respect to network size is revealed and found to depend on the underlying network topology. In the second step, a distributive routing and congestion control is proposed. Each node locally propagates its routing cost estimates and information about its congestion state to its neighbors, which then update their respective cost estimates. This allows for a flexible adaptation of end-to-end routes to the overall congestion state of the network. Compared to shortest-path routing, the critical network load is significantly increased.
In two previous Papers [1,2] we have already discussed the so-called wireless multihop
ad hoc networks. They represent an engineered communication network, which
reveals many facets of very intriguing and complex behavior. In this respect they Ct
nicely into the cross-disciplinary realm of the Statistical Physics of complex networks
[3–5], which has already opened its doors for other communication networks like the
Internet, but also for biological and social networks.
Wireless multihop ad hoc networks represent an infrastructureless peer-to-peer generalization
of todays wireless cellular phone networks. Instead of being slaved to
a central control authority, each node not only sends or receives packets, but also
forwards them for others. Consequently, communication packets hop via inbetween
ad hoc nodes to connect the initial sender to the Cnal recipient. A lot of coordination
amongst the nodes is needed for the overall network to perform well. They
have to ensure network connectivity, good data-tra4c performance and robustness
against various forms of perturbations, just to name but the most important issues.
Because of this intrinsic coordination, wireless multihop ad hoc networks represent
an excellent example of what is called a selforganizing network. However,
their biggest challenge is yet to come, how to get selforganization to
work.
The connectivity issue has already been discussed quite extensively [1,6–9], also
addressing interference eJects [10,11]. In one form or the other all these eJorts relate
to continuum percolation [12–14]. An interesting distributive scheme has been put
forward in Ref. [1], which turned out to be amazingly robust, guaranteeing strong
network connectivity almost surely; we will brie7y touch upon this scheme again in
Section 2.1. The robustness issue with respect to selCsh users has received inspirations
from the biological immune system and distributive algorithmic suggestions have been
put forward [15].
As to data-tra4c performance, estimates on the throughput, i.e., the capacity of how
much end-to-end tra4c the network is able to handle without overloading, have been
given. In Ref. [16] a rigorous upper bound has been derived to scale with the square
root of the network size. ReCned estimates have been given in [2], revealing that the
scalability of the throughput depends on the underlying network structure. Besides several
other idealistic assumptions, these estimates have employed shortest-path routing.
Although several proactive and reactive routing schemes have already been discussed [17–20], we are not aware of any selfoptimizing scheme, which also accounts for
congestion avoidance.
In this paper we will propose a prototype for such a highly wanted distributive and
adaptive routing and congestion control. The idea is that every node keeps an estimate
of how much it costs to send packets to Cnal destinations and to update these estimates
in a distributive manner. The latter can be achieved in a very elegant way without any
additional exchange of control information. Whenever a node is actively involved in a
forwarding one-hop transmission, it silences its neighbors anyhow, so that those do not
interfere on the shared wireless propagation medium. This blocking is called medium
access control. Upon blocking its neighbors, the node is able to distribute its routing
cost estimates and its congestion state to them, which those then use to update their
cost estimates. In the technical jargon of engineers, this distributive scheme corresponds
to a coupling of the medium access control layer with the routing layer.
The structure of this paper is as follows. Section 2 summarizes the key operational
features of wireless multihop ad hoc networks, introduces plausible simpliCcations and
describes the setup of generic simulations with random data tra4c. Shortest-path routing
is used in Section 3 to investigate certain Cngerprints of congestion like end-to-end
time delay and single-node relaxation times. Whenever possible, the numerical simulations
are accompanied with analytic modeling. Section 4 presents the details of the
proposed distributive routing and congestion control and compares its results to those
obtained with the shortest-path routing. The conclusion and a short outlook are given in
Section 5.
This paper has focused on routing and congestion control in wireless multihop ad hoc
communication networks. Simulations with random data tra4c have been accompanied
with analytic estimates, whenever possible. The focus has Crst been on shortest-path
routing, to understand certain data tra4c characteristics like end-to-end time delay
and correlation time scales, and to Cnd Cngerprints of congestion once the network
is operating close to its critical load. A scaling law has been found for the average
end-to-end time delay with respect to network size, which also revealed a dependence
on the underlying network topology. In a second step and going beyond shortest-path
routing, a distributive routing and congestion control has been proposed, which couples
the MAC- and routing layer of wireless multihop ad hoc communication. Before
one-hop forwarding a packet, the sending as well as receiving node MAC-block their
respective neighbors and distribute information about their congestion state and routing
cost estimates, which the latter then use for updates. This distributive scheme turned
out to be very e4cient. Compared to shortest-path routing, the critical network load
increased noticeably. Routes are constantly adapting to the prevailing congestion state
of the network. With other words, routes selforganize themselves.
The proposed prototype routing and congestion control needs of course further testing
and extensions. Other than simple random data tra4c has to be looked at, such as for
example selfsimilar [30], self-organized-critical [31] and spatially localized. Congestion
updates with diJerent forms of cost metrics are important to investigate as well as the
sparsity issue, i.e., which information is important to be distributed to other nodes
and which is negligible. At the end, the biggest challenge is yet to come, to turn good
ideas into real-life-functioning implementations. This is where Physics and Engineering
should meet again.
