As a representative of a complex technological system, the so-called wireless multihop ad hoc
communication networks are discussed. They represent an infrastructure-less generalization of
todays wireless cellular phone networks. Lacking a central control authority, the ad hoc nodes
have to coordinate themselves such that the overall network performs in an optimal way. A performance
indicator is the end-to-end throughput capacity. Various models, generating di4ering
ad hoc network structure via di4ering transmission power assignments, are constructed and characterized.
They serve as input for a generic data tra5c simulation as well as some semi-analytic
estimations. The latter reveal that due to the most-critical-node e4ect the end-to-end throughput
capacity sensitively depends on the underlying network structure, resulting in di4ering scaling
laws with respect to network size.
Complex networked systems are widespread in nature, society and engineering. Some
examples from biology are regulatory gene and metabolic networks, the neural network
of the brain, the immune system, and, on larger scales, food webs and the ecosystem.
Another example, now from the social sciences, is multiagent economics, where a multitude
of large and small traders are interwoven together to curse the course of exchange
rates and stock prices. Also engineering contributes with communication networks, such
as the Internet, the world wide web and grid computing.
Recently, physics has started a new branch, the Statistical Physics of complex networks
[1–3], which takes a generic and unifying perspective at all of those examples.
So far, most of the focus has beenonthe structure of such networks. The analysis of a
great deal of the above mentioned examples has led to the unifying scale-free discovery
and its respective growth modeling with preferential attachment. Beyond structure,
it is now also dynamics on and function of networks, which are about to move onto
center stage. The new insight which along these lines has already been given to regulatory
gene networks [4] constitutes for sure a remarkable highlight. The impact of
structure on dynamics is also key to epidemic spreading and the proposal of e5cient
immunization strategies for populations and computer networks [5].
The structure and dynamical properties of engineered communication networks in
general and computer as well as Internet tra5c in particular were also discussed heavily
withinthe physics community over the last years. Key issues have beenbesides
network structure [6–8] also phase transition like behavior from a non-congested to
a congested tra5c regime [9–12] and self-similar data tra5c [13]. So far, the analysis
of network structure and dynamics has been mostly separated from each other.
Only very recently a Jrst coupling of these issues has been picked up, focusing on the
impact of structure on synchronization dynamics [14]. In this paper, we introduce a new
and intriguing complex technological system to the Physics community, the so-called
wireless multihop ad hoc communication networks [15–18], and discuss the impact of
network structure onto their performance to handle data tra5c.
Wireless multihop ad hoc communication networks represent an infrastructureless
generalization of todays wireless cellular phone networks [19–21]. Lacking a central
control authority in the form of base stations, each end device acts as router and relays
packets for other participants. End-to-end communications are possible via multihop
connections. In order to ensure network connectivity, e5cient discovery and execution
of end-to-end routes and avoidance of data packet collisions on shared radio channels,
the participating devices need coordination amongst themselves. Proposals [22,23] for
such a coordinationhave already beenput forward uponfocusin g onthe connectivity
issue. For the other two issues, routing and medium access control, the coordination is
much more delicate. Routing e5ciency would require rather short end-to-end routes,
resulting in a small network diameter. Due to the overall presence of interference,
medium access control takes care of collision avoidance for data packets traveling on
di4erent routes. It blocks all neighboring devices of an active one-hop transmission
and thus would rather favor a small neighborhood, implying a small node degree. The
opposite demands of these counteracting mechanisms leave the network in a state of frustration. This opens the door for the generic Statistical Physics of complex networks,
asking the question what is the impact of network structure on the performance of
wireless multihop ad hoc communication.
Well-performing network structures would be those which Jnd an e5cient compromise
out of this frustration. They would come with a small end-to-end time delay and a
large end-to-end throughput. In this paper, we analyze and compare di4erent wireless
multihop ad hoc network structures that are created by di4erent transmission power
assignments. Note that the regulation of its transmission power is the only intrinsic
control action a communication node is able to perform to enforce a certain structure
of the network. A generic data tra5c simulation as well as a semi-analytic approach
is used to calculate the end-to-end throughput associated to these network structures.
This allows us to study the impact of network structure on the data-tra5c performance
of such communication networks.
Section 2 explains the used network model and various transmission power assignments.
Some properties of the resulting geometric network graphs are also discussed.
The performance of these network structure classes with respect to end-to-end throughput
is evaluated inSection 3 by employing a generic data tra5c simulation, the emphasis
being on scalability. Semi-analytic insights are presented in Section 4 and Jnally
a conclusionis giveninSection 5. The appendix summarizes the graph-theoretical
variables, which are used throughout the paper.
Wireless ad hoc communication networks represent an example for a complex,
networked technological system. Their key operational controls, routing and medium
access control, come with opposite demands and leave the network in a state of frustration.
This opens the door for the Statistical Physics of complex networks to ask,
what are e5cient network structures in order to Jnd a good compromise. Various network
models, all of them constrained by spatial geometry, the wireless propagation
medium and some selected design principles, have been proposed to explore the huge
network structure state space and to test the impact of network structure on network
performance. As a measure the end-to-end throughput has been chosen. It represents
the network’s capacity, sometimes also called bandwidth, to deliver a certain amount of end-to-end communications per time without network overloading. A generic data
tra5c simulation as well as several semianalytic estimates of increasing sophistication
demonstrate that (i) below a critical network size a fully connected structure always
comes with the largest and then size-independent throughput, (ii) well above the critical
network size the throughput scales as Te2e ∼ N with network size N, (iii) contrary
to current mean-Jeld belief [24]
= 0:5 due to the most-critical node e4ect, and (iv)
the scaling exponent depends on the speciJc structure of the picked network model.
Another, although smaller discovery along the way has been that di4erent network
structure models lead to quite di4erent average transmission power values, but once
the latter is weighted with the amount of data tra5c passing over a node, the di4erences
inpower consumptionbetweenthe network structure models decline.
The generic network approach to wireless ad hoc communication, which has been
advocated in this paper, gives guidance to several yet-to-come generalizations. Straightforward
issues like the spatial heterogeneity of static and mobile point patterns, the
spatio-temporal heterogeneity of the wireless propagation medium, interference, synchronization
and di4erent user behavior for the modeling of data tra5c need to be
addressed. Additional network structure models, directly resulting from the global optimizationof
designprin ciples, like the maximizationof end-to-end throughput itself,
need to be developed and will then serve as benchmarks for an even bigger challenge,
the construction of such optimized network structures via decentralized topology
control rules. Functional aspects like routing coupled to congestion control and new
technology-driven aspects like geometric routing [34] are thenalso becoming important.
This underlines that it is still a longer way to reach a truly self-organizational
control of wireless ad hoc networks and other networked technological systems. Upon
further pursuing this road, it is a good idea to learn more about self-organization also
from other networked complex systems out of physics, biology and sociology.
