{'fraction_non_alphanumeric': 0.031348931989374475, 'fraction_numerical': 0.009897747534660311, 'mean_word_length': 4.424694038689301, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Impact of network structure on the capacity of wireless multihop ad hoc communication

As a representative of a complex technological system, 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 differing ad hoc network structure via differing transmission power assignments, are constructed and characterized. They serve as input for a generic data traffic simulation as well as some semi-analytic estimations. The latter reveal that due to the most-critical-node effect the end-to-end throughput capacity sensitively depends on the underlying network structure, resulting in differing scaling laws with respect to network size.


Introduction
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,2,3], which takes a generic and unifying perspective at all of those examples. So far, most of the focus has been on the 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 efficient 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 traffic in particular were also discussed heavily within the physics community over the last years. Key issues have been besides network structure [6,7,8] also phase transition like behavior from a noncongested to a congested traffic regime [9,10,11,12] and selfsimilar data traffic [13]. So far the analysis of network structure and dynamics has been mostly separated from each other. Only very recently a first 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, so-called wireless multihop ad hoc communication networks [15,16,17,18], and discuss the impact of network structure onto their performance to handle data traffic.
Wireless multihop ad hoc communication networks represent an infrastructureless generalization of todays wireless cellular phone networks [19,20,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, efficient 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 co-ordination have already been put forward upon focusing on the connectivity issue. For the other two issues, routing and medium access control, the coordination is much more delicate. Routing efficiency 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 different 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 find an efficient 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 different wireless multihop ad hoc network structures that are created by different 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 traffic 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-traffic performance of such communication networks.
Sect. 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 in Sect. 3 by employing a generic data traffic simulation, the emphasis being on scalability. Semi-analytic insights are presented in Sect. 4 and finally a conclusion is given in Sect. 5. The Appendix summarizes the graph-theoretical variables, which are used throughout the Paper.
2 Network structure models for wireless multihop ad hoc communication In this Section we are only concerned with structural aspects of wireless multihop ad hoc communication networks. Upon invoking some justifiable idealizations in Subsect. 2.1, various classes of random geometric graphs are constructed in Subsects. 2.2-2.6, which we will from then on reference as network models I-V. The various network models differ in the way how transmission power is assigned to the communication nodes. Their structural properties will be discussed in Subsect. 2.7.

Network models in general
Wireless multihop ad hoc networks consist of communication nodes, which are distributed in space and communicate to each other via a wireless medium. For simplicity, mobility of the communication nodes is discarded. Exactly N communication nodes are given random positions (x, y) ∈ [0, L] × [0, L] confined to a square area. Other spatial point patterns, e.g. of clustered multifractal or Manhattan type, have already been discussed in connection with the connectivity issue [23], but will not be given further consideration here.
The radio propagation medium and the receiver characteristics determine whether nodes can communicate to each other. According to a simple propagation-receiver model, a node i is able to listen to a transmitting node j, if relative to a noise the power received at node i, is larger than the signal-tonoise ratio snr: P j denotes the transmission power of node j and r ij represents the distance between the two nodes. Without any loss of generality we choose the normalization noise · snr = 1/( √ 2L) α , so that P = 1 for r = √ 2L. Depending on specific in-/outdoor propagation, the path-loss exponent typically falls into the regime 2 ≤ α ≤ 6 and is assumed to be constant. A specific fixation of its value is not required for our generic view advocated in this Paper. Once (1) is fulfilled, it defines a one-directed communication link j → i. If also the link i → j exists, then the two nodes are connected via a bidirectional link i ↔ j and are able to directly communicate back and forth to each other. Although not strictly required, bidirectional links are preferred for the operation of wireless ad hoc networks, because many protocols require instant feedback. Note also, that according to (1) the communication links are defined in the trafficfree regime. This is an additional simplification and does not take interference into account.
En route to the construction of random geometric ad hoc graphs one further step has to be taken. It deals with power assignment and gives a specific transmission power value to each node. According to (1) this value can be translated into a transmission range. Those nodes which then fall inside this transmission range are then the neighbors, to which the picked node is able to communicate via outgoing wireless links. Power assignment can be done via a number of different approaches. Some of them are presented in the following Subsections and lead to network models I-V. The construction of some of these models is based on standard as well as non-standard graph-theoretical variables, which for convenience are all listed in the Appendix.

Network model I: constant transmission power
The simplest structural design of wireless ad hoc networks is to use the same transmission power P for each node [24]. All existing links are then bidirected. However, the specific choice for P needs to be addressed. If P is chosen too small, the network is not strongly connected. If P is too large, too much bandwidth is given away with an increased blocking by medium access control. Hence, in Ref. [24] it was suggested to tune P such that the network remains just about strongly connected; see also [23,25,26,27]. Unfortunately this choice for P depends on the network size. To proceed further, it is of advantage to first translate P into a transmission range R, which then determines the mean node degree k i ∞ . With P = (R/ √ 2L) α from (1) and ρπR 2 = k i ∞ with the node density ρ = N/L 2 we get the relationship P = ( k i ∞ /2πρL 2 ) α/2 . Note that in the limit N→∞ boundary effects can be neglected, so that k i ∞ = k i . A quick simulation reveals that strong connectivity is guaranteed almost surely for k i ∞ > a+b log N; see also Refs. [25,27]. The values a = 12.7 and b = 2.11 have been determined such that 99% of 1000 sampled random network graphs per network size N had been strongly connected. Since the network size is not a control parameter, but limited in view of practical applications, we choose k i ∞ = 24, unless otherwise noted. This value guarantees strong connectivity for network sizes up to several thousand nodes almost surely. The upper left part of Fig. 1 illustrates a connected wireless multihop ad hoc graph with this parameter setting.

Network model II: minimum node degree
The const-P assignment of the previous Subsection has notorious practical drawbacks. First of all, it is a global rule, where nodes need to access information about the complete network state. Second, the used constant transmission power strongly depends on the nature of the spatial point patterns. As demonstrated in Ref. [23], for random patterns of clustered multifractal or Manhattan type the corresponding k i ∞ values are substantially larger than the outcome with random homogeneous patterns. Clearly, a much more flexible power assignment is needed, which only collects local information and acts in a decentralized manner. A promising proposal has been given recently and has been tested for the various environments: the minimum-node-degree rule [23]. By exchanging so-called "hello" and "hello-reply" messages each ad hoc node is able to access direct information from its immediate neighbors, defined by its links. A simple local observable for a node is its node degree. Based on this observable alone, the simple minimum-node-degree strategy for a node is to adjust its transmission power to have at least k min bidirectional neighbors. While some of the nodes will end up having exactly k min neighbors, some others are forced to have more than k min neighbors in order to give an additional bidirectional link to a node which so far has not accumulated enough neighbors. The only parameter, i.e. k min , turns out to be remarkably insensitive to the procedure on how the random spatial point patterns are thrown. For more algorithmic details and a detailed discussion see [23].
Again, a simulation proves that once k min = a + b log N with a = 3.5, b = 0.66, then 99% or the thrown network graphs are strongly connected. The dependency of k min on the network size is much smaller than in the case of const-P networks, where b = 2.11. To be on the safe side for all network sizes considered within this Paper we fix the minimum-node degree to k min = 8, unless otherwise noted. The upper right part of Fig. 1 illustrates a typical wireless multihop ad hoc graph based on this parameter setting.

Network model III: constant target degree
In the next three Subsections ad hoc network models are again globally constructed, respecting special design properties. They serve to explore new regions of the giant network-state space. For a network consisting of N nodes basically (N −1) N different network states exist. Pick a node and continuously raise its transmission power starting with zero. At P i (1), which follows from (1), the closest neighbor is able to receive the data transmission from i, then at P i (2) the second closest is able to listen, and so on, until P i (N − 1) when the most furthest node is also happy to understand. Thus, a power ladder with N − 1 steps can be assigned to each node. Having N nodes, this makes (N − 1) N different network states. For sure, not all of them qualify because strong network connectivity is a necessary prerequisite. Note however, that the const-P and minimum-node-degree network state represent just two out of these (N − 1) N states, so that there is a good chance to find new gold somewhere in this giant network-state space.
The third set of network models is generated by minimizing the optimization function In the physics literature such an optimization function is traditionally called an energy function. Here it targets all nodes to come with the same node degree k target . Unless noted otherwise, we consider k target = 5. The second term on the right-hand side of (2), which goes with the network diameter, is thought of as a small (ǫ ≈ 0) admixture guaranteeing network connectivity; for the case of partitioned networks we set D = ∞.
The search for the optimized network state is carried out using simulated annealing as described for example in Ref. [28]. Starting from a more or less random initial network state, two search operations are performed in successive time steps: with probability p = 0.8 one node is picked at random and its transmission power P i (n) ladder state is changed to n ± 1, or with probability 1 − p two nodes are picked at random and their ladder states n i ↔ n j are exchanged. For each operation the energy is evaluated and the change is accepted with a certain probability, that depends on a computational temperature. The latter is slowly decreased with ongoing search time, so that tentatively regions of the network-state space are explored with lower and lower energy. The search process stops once a minimum temperature is reached or the energy has remained unchanged after a significantly large amount of time steps. With the computing facilities available to us, we set the upper limit of the number of nodes for the optimized networks to 100 and also the ensemble size to 100. For the parameter choice k target = 5, a typical optimized wireless multihop ad hoc graph is exemplified in the middle left part of Fig. 1.

Network model IV: scale-free target degree
As a technological complex system the Internet comes with a scale-free network structure [6,7,8]. As the Internet and wireless networks are both communication networks, they have many parallel, but also distinct features. Nevertheless, curiosity begins to ask about the Internet-specific scale-free aspect for wireless multihop ad hoc networks.
A rather simple, but straightforward version for the construction of scale-free wireless multihop ad hoc networks uses a modification of the energy function (2), namely Independently of the other nodes, each node is randomly assigned its own target degree k target i according to a truncated scale-free distribution with k min ≤ k target ≤ k max . As parameter values we choose γ = 2.1, k min = 3 and k max = min (30, N). A wireless multihop ad hoc graph, resulting from the optimization of the energy function (3), is shown in the middle right part of Fig. 1.
Note, that the construction (3) relies on bidirected links. For such a link to exist, the two attached nodes need to have suitable transmission power values. With other words, both nodes have to do something to establish a link, and in doing so, additional one-directed links emerge unintentionally to other nodes in their spatial surrounding. This is specific to wireless multihop ad hoc graphs and is in contrast to other constructions of geometric scale-free graphs [29,30,31,32].

Network model V: minimum power consumption vs. shortest path
An obvious design principle for the overall wireless network would be to consume as little power as possible. A suitable measure for the power consumption of node i is given by the product of its transmission power P i and its node inbetweeness B i , the latter representing a measure for the frequency to relay packets within the network. Another, different design principle might be to reach the intended receiver in as few as possible multihop steps in order to reduce the end-to-end time delay. The respective measure would be simply proportional to the network diameter D. Taken together, both design principles lead to the energy function The normalizations N (5−α)/2 and √ N have been introduced for the first and second term, which follow from the intuitively expected D ∼ √ N, B i ∼ ND ∼ N 3/2 of (23) and P i ∼ N −α/2 of (1). λ = 0 reflects the first design principle and will lead to rather sparse network structures. The second design principle is represented by λ = 1 and will prefer fully connected network structures. Since these two design principles come with opposite demands, it is interesting to study also values of λ falling inbetween zero and one. For the parameter settings λ = 0.0 and 0.8 the lower left and right parts of Fig. 1 Table 1 Mean structural properties of wireless ad hoc network graphs resulting from models I-V of sizes N = 100 and N = 2000.

Structural properties of network models I-V
The mean node degree, as well as means and distributions of all following single-node variables, is obtained by sampling first over all nodes within one random geometric graph realization and then over all generated sample realizations representing the corresponding network model. A part of Table 1 summarizes the means of various node and link degrees for network models I-V with N = 100. For network models I and II the mean values are also given for N = 2000. These values show only little variation with the network size and can thus be considered to be close to their asymptotic N→∞ limit. The power-minimizing limit λ→0 of network model V produces the smallest numbers. The scale-free network IV yields the largest mean excess number of one-directed links. The reason for this routes in the uncorrelated assignment of each node's target degree, which does not adapt to the local structure of the spatial point patterns. For all network models the average link degree is about a factor 1.25−1.45 larger than the mean node degree, the exception being again network model IV, where this factor amounts to almost 2.
Without showing we remark on the node degree distributions. Network model R r ij i j Fig. 2. Cluster coefficient resulting from network model I: given a node i and a neighboring node j, the probability that a node k is a common neighbor of i and j is given by the quotient of the shaded area and the area πR 2 of the transmission disc.
I reveals a very broad Gaussian-like distribution. Network model II produces a dominant spike at the minimum node degree k min , which is continued by a small, but broad Gaussian-like tail towards larger degrees. As expected, network model III gives rise to a narrow distribution centered around k target . A scale-free target degree distribution with γ = 2.1 has been the input of network model IV and an approximate scale-free degree distribution is also its output. However, the output is modified to γ = 2.5 (for N = 100) within 5 ≤ k i ≤ 30. This is due to the computationally dictated smallness of the network, the spatial geometry of the network, the node-independence of the degree assignment and the soft square in the expression (3) of the energy function. The node degree distributions of network model V deserve some more attention. The two limiting cases are obvious. For λ → 0 the transmissionpower term in (5) dominates, leading to a very thin network structure with a narrow, small-mean distribution. In the limit λ → 1 the network-diameter term becomes more and more important, leading to an increasingly connected network structure and culminating in a fully connected network, once λ = 1. Inbetween the two extremes no critical network structure emerges. Due to the involved spatial geometry of the node patterns, the resulting Gaussianlike node-degree distributions are very robust and lead to network structures, which are very similar to the ones obtained with network model I with a suitably tuned transmission power P .
As can be read off from Table 1, all network models (except model V in the λ → 1 limit) produce an N → ∞ asymptotic value around C i ≈ 0.6 for the node-based cluster coefficient. A similar behavior is also observed for the linkbased cluster coefficient. This observation can be explained with the following geometrical argument. For large model I networks with constant transmission power, let R be the transmission range of all nodes. Pick any node, say i, and one of its neighbors, say j, the distance between the two nodes being r ij . The shaded area of Fig. 2 describes the locations of possible further nodes that have links to both nodes i and j. In the limit of large N, the quotient between this shaded area and πR 2 then describes jth contribution to the cluster coefficient of node i. Using simple geometry, this contribution amounts to The mean cluster coefficient of node i can now be calculated by averaging C(r) over all 0 ≤ r ≤ R, This calculation very well explains the observed values around 0.6, which now have to be interpreted as a direct consequence of the two-dimensionality of the spatial point patterns. For small networks, finite size effects are essential and lead to a larger cluster coefficient in almost all cases.
The network diameter for models I-V is also listed in Table 1. Models I and II allow to address the dependence of D on the network size. For N > 100 the scaling law D ∼ √ N is found for both types of network models. This outcome is in full agreement with our lattice intuition, when N nodes are fully packed onto a two-dimensional lattice with side length √ N. The quality of this scaling law degrades for networks of small size.
The means of node and link inbetweeness are already fixed by the sum rules (23) and (25) and are fully expressible in terms of the network diameter and the average node degree. As a function of the network size and independent of the network type I or II, both quantities scale as B i ∼ B i↔j ∼ N 3/2 . -It is also interesting to look at the most extreme values. As we will realize in Sect. 4, they are of relevance for the network performance with respect to data traffic load. Table 1 also lists the values of sup i (B i ) and sup i↔j (B i↔j ) for network models I-V of size N = 100 and for network models I and II of size N = 2000, respectively. First the supremum has been taken within one network realization and then this supremum has been averaged over a large enough sample of realizations belonging to the same network model. Table 2 lists the corresponding scaling exponents with respect to the size of network models I and II. The exponents are found to deviate noticeably from 3/2.
The quantities B cum i and sup i B cum i related to the cumulative node inbetweeness are also listed in Table 1 for the various network models. For network models I and II the exponents of the observed scaling laws are put down in Ta Table 2 Exponents γ of the observed scaling laws O ∼ N γ , extracted from network models I and II of sizes 100 ≤ N ≤ 2000.
mately described by a Gamma or log-normal distribution. As outlined in [23] this behavior traces back to the rather narrow node-degree distributions and the random homogeneity of the spatial point patterns. As listed in Table 1, the average transmission power P i ranks these network models in the order I, II, III and V, with model I requiring by far the largest value. However, upon switching from P i to B i P i , all models more or less come with the same average value. This demonstrates that the power consumption of the overall network, where the multihop forwarding of end-to-end communications is taken into account, does not sensitively depend on the network structure. Of course, the scale-free network model IV represents again an exception to this rule.
3 Generic data traffic and end-to-end throughput After having presented the various different wireless multihop ad hoc network models I-V and having discussed their structural properties, we now turn to the dynamics on such networks. A generic data traffic simulation will be described in the first Subsection. In the second Subsection, the end-to-end throughput, which represents the network's capacity to handle data traffic without network overloading, will be discussed and compared between network models I-V.

Generic data traffic simulation
A detailed, engineering-like approach to data traffic simulation would explicitly model the exchange of all control messages needed for link, medium access and routing control and then would aim to analyze and compare different medium access and routing algorithms [17,18]. Since for the time being, we are interested in the overall behavior of the generated network structures, we prefer to use a rather generic approach to data traffic simulation. The sim-ulation uses discrete time steps and assumes that all nodes start each time step simultaneously. A time step begins with the packet creation phase. Then a short contention phase for medium access control is succeeded by a longer packet transmission phase. In the following we give a short description of the used generic simulation.
At each time step, a new data packet is created at each node with the probabilistic packet creation rate µ < 1. At a node, its new packet is assigned a random destination out of the other N − 1 nodes and is then put at the end of its buffer queue, assumed to have infinite capacity. In the future course the packet will be forwarded along the shortest path to its final destination. The routing matrix R ij takes care of this forwarding, where R ij = k means that a packet at node j with destination i has the next hop k. The routing matrix has been determined with Dijkstra's algorithm [33]. If shortest-path degeneracy occurs, then one of the paths is chosen at random and once and forever kept fixed, not only for this specific end-to-end communication, but also for all future communications between the same original sender and the same final recipient. This procedure is not fully consistent with the employed handling of shortest-path degeneracy for the determination of the node and link inbetweeness, but on the other hand still very similar due to the randomness in the selection process. Nodes, for which a new packet has been created, are blocked for the remainder of this time step.
During a short contention phase, still at the beginning of the time step, the remaining non-blocked nodes compete for gaining sender status. One of them with a nonzero buffer is randomly picked first and allowed to transmit its first-in-line packet to the envisaged neighboring node. Both, the sending as well as receiving node block their respective one-hop outgoing neighbors for the remainder of this time step. This blocking is called medium access control (mac) and is very necessary to avoid collision of data packets in a wireless medium. Then another node from the nonzero buffer and non-blocked list is chosen at random and allowed to attempt the transmission of its first-in-line packet. If the intended receiver has already been blocked before, the node tries to submit its second-in-line packet and so on, until either the first idle recipient is found or the end of its buffer queue is reached. We denote this strategy as first-in-first-possible-out (fifpo). If this node succeeds to submit a packet, it then (mac-) blocks again its remaining outgoing neighbors as well as those of the receiving node. This iteration is repeated until no free one-hop transmission is left for this time step.
In case of existing one-directed links, which occur for a heterogeneous assignment of transmission power, it might occur that a one-directed outgoing link associated to the latest mac-operation blocks a node, which within the contention phase of this time step has already gained sender or receiver status in a previously approved one-hop transmission. For such cases, the previously assigned sender and receiver are blocked again. Furthermore, their outgoing neighborhoods remain blocked and are not freed.
Then all chosen transmitting nodes submit their selected packet and remove this packet from their respective buffer list. The receiving nodes either add their incoming packet to the end of their queuing list or, if they are the final recipient, destroy this packet. This concludes the actions taken for this time step and the whole game is repeated for the next time step.

End-to-end throughput
Having generic data traffic simulations now at hand, legitimate questions to ask are: what is the critical network load, how does it scale with the network size and how does it depend on the network structure? The performance of a network depends crucially on the interplay between routing and medium access control. The adopted shortest-path routing would prefer network topologies with small diameter D, but then an active one-hop link would come with a large number k out i↔j of attached one-hop neighbors, which are mac blocked. On the other side, if the mac blocked neighborhood is reduced to a minimum, then the network diameter increases and it needs more hops to deliver a packet to its final destination. Furthermore, not all the nodes are equally loaded. Due to their exposed spatial location in the network center some of them have to forward more packets than others and come with a larger node inbetweeness. The network models I-V, illustrated in Fig. 1 and filed in Table 1, all come with different weightings of the decisive characteristics like D, k out i↔j and sup i B i , so that it is not possible to tell from the beginning which of these models performs best.
Given a specific network model realization and network size, the critical traffic load µ crit per node is defined as the maximum packet creation rate µ, where on average the flux of newly created packets is still equal to the flux of endto-end delivered data packets. µ < µ crit defines the subcritical phase, whereas µ > µ crit is denoted as the supercritical phase. As each node of the network comes with its own in-and out-flux of data packets, the critical network load µ crit is determined by one node, the most critical node, for which its in-and out-flux µ in i = µ out i become identical. For all the other nodes their respective in-flux is still smaller than their out-flux, i.e. µ in j =i < µ out j =i .
The mean in-flux of data packets for node i, is equal to the reciprocal of the average interarrival time t arriv i , the latter meaning the time lag between two successive packet arrivals at node i. Two things should be remarked here: First, it does not matter if a packet is received via transmission from a neighboring node j ∈ N i or if it is generated right at node i as long as they are added to the buffer queue of i. Second, arriving packets to node i with i being the final receiver are not counted because they are not handed over to the buffer queue, but are deleted from the network.
The out-flux of data packets for node i, is given as the reciprocal of the average sending time; for later convenience we introduce the abbreviation t send i = τ i . Conditioned on a non-empty buffer queue, the latter is defined as the time it takes to send the next packet from node i to any of its neighboring nodes. The time counter for the sending time is reset either with a sending event from an n i ≥ 2 buffer queue or with the arrival of a packet to an empty n i = 0 buffer queue.
As function of the packet creation rate the curves for µ in i and µ out i intersect at µ = µ crit i . This intersection point is different for different nodes. The critical network load is now given as This is a per-node quantity. It is related to the overall-network quantity which is denoted as the end-to-end throughput. The latter describes the maximum number of end-to-end communications, which can be completed per time step without network overloading. In this respect, T e2e can also be thought of as a network capacity and µ crit as a specific network capacity. look again at the middle right part of Fig. 1 reveals that the reason for this is the large number of occurring one-directed links, which in addition to the bidirected links block large parts of the network via medium access control.
The observed ranking of small-sized network models I, II, V and III might suggest, that average node degree and end-to-end throughput are correlated: the larger k i , the larger T e2e . This correlation appears to be further supported by a fully connected network, which comes with the largest possible node degree k i = N − 1 and has T e2e = 1. Since each node then has a bidirected link to any other node, medium access control blocks the complete network for a single one-hop transmission. This implies that at maximum only one packet per time step is delivered to its final destination, leading to T e2e = 1. For visualization the T e2e = 1 line is also drawn in Fig. 3.
However, this observational correlation conjecture turns out not to be true.  Table 3 End-to-end throughput T e2e = aN γ and critical size T e2e (N crit ) ≡ 1 for network models I with k i = 24 and II with k min = 8 obtained from generic data traffic simulations and the estimates (12), (15) and (22). For the last estimate two variations have been employed: the first one uses (16) without the ∆τ 2 term and the second one uses the full expression (16). The parameters a and γ have been obtained from best fits in the regime 200 ≤ N ≤ 2000. Fig. 4b shows the network-model II end-to-end throughput for fixed network size N as a function of the minimum node degree k min . For N ≤ 100, T e2e is below one for small k min , then drops towards medium k min and finally increases to T e2e = 1 in the fully connected limit k min = N − 1. A similar conclusion is drawn from Fig. 4a for network model I. Note there, that at k i ∞ = N − 1 the end-to-end throughput has not converged to the fully connected T e2e = 1. This is a finite-size effect, because nodes close to the border of the chosen square area L × L are missing nodes at the other side to connect to. Their node degree is smaller than the asymptotic N − 1, implying a network structure which is not fully connected. Only once all nodes come with a sufficiently larger transmission power, implying k i ∞ > N − 1, the end-to-end throughput converges back to its fully connected limit.
Upon focusing on larger sized networks, the results exemplified in Figs. 3b and 4a+b reveal that sparsely connected networks then come with an endto-end throughput, which is larger than the fully connected T e2e = 1. The critical network size, which separates T e2e < 1 for N < N crit from T e2e > 1 for N > N crit , is of the order of N crit ≈ 100. See also Table 3. In view of several envisaged technological applications of small-sized wireless multihop ad hoc networks, this is an important statement.
For network sizes larger than N crit the end-to-end throughput is larger than one and increases the larger N becomes. In this regime, scalability statements are of utmost importance. For network models I and II such statements can be given; see Fig. 3b. Within 200 ≤ N ≤ 2000 the scaling expression T e2e = aN γ is found to give a precise agreement with the generic-data-traffic results. The fitted parameters are listed in the first row of Table 3. The scaling exponents are found to be γ = 0.38 for network model I with k i ∞ = 24 and γ = 0.24 for network model II with k min = 8. This outcome clearly shows, that network structure has a prominent influence on the network performance with respect to data traffic. It is the goal of the next Section to present semi-analytic estimates, which are compatible with the e2e-throughput scalability observed from the data-traffic simulations.
4 Modeling of end-to-end throughput

Throughput I: back-on-the-envelope estimate
The end-to-end throughput describes the maximum number of end-to-end communications, which can be completed per time step without network overloading. This maximum number can be roughly estimated as the maximum number of one-hop transmissions taking place per time step, divided by the average length D of an end-to-end communication route: On average, 2 + k out i↔j nodes are involved in a one-hop transmission, the onehop sender and receiver as well as their k out i↔j outgoing neighbors, which are blocked by medium access control. The network size N divided by this number represents the maximum number of simultaneous one-hop transmissions taking place per time step. -The expression (12) is consistent with the finding T e2e = 1 for fully connected networks. Since every node has a direct link to every other node, we have D = 1 and k out i↔j = N − 2.
For the various network models the expression (12) can be determined right away. Fig. 5 compares the sample average with the results from the generic data traffic simulations and reveals that for all network models I-V the former noticeably overestimates the latter. This is not the only discrepancy. A quick look into the second row of Table 3 reveals that according to (12) the end-toend throughput of network models I and II would scale with an exponent very close to 1/2. This outcome, being a consequence of the more or less universal D ∼ √ N behavior, has already been proposed earlier [24], but is in conflict with the findings from the generic data traffic simulations. The inherent difficulty with the at first plausible estimate (12) is that it is built with average network properties. Contrary to the generic data traffic it does not account for the most-critical-node effect, which limits the end-to-end throughput.

Throughput II: cumulative node inbetweeness
Analogous to the most-critical-node procedure (8)-(10) for the determination of the end-to-end throughput (11) of the generic data traffic, a more sophisticated estimate for T e2e is now given. The mean in-flux of data packets into node i, is given by the fraction B i /N(N − 1) of the µN newly created data packets per time step, that will be routed via node i at later time steps in order to reach their final destination. Within the numerical uncertainty of the generic data traffic simulations we have tested that the two flux rates (8) and (13) are indeed identical. A realistic description of the out-flux (9) is subject to modeling. A particular simple estimate of the average sending time uses the cumulative node inbetweeness (26): As node i competes with its ingoing neighbors for medium access, it may have to wait a certain amount of time before sending its packet along a one-hop connection. The ansatz (14) weights each of the competing nodes with its relative frequent use for forwarding end-to-end communications. It represents an interpolation between τ i → 1 in the low-load limit µ → 0 and τ i → O(k in i ) holding in the supercritical regime µ ≫ µ crit . As such, it can be hoped that the ansatz (14) catches at least part of the truth when it comes to the proper behavior of the sending time around the critical network load µ crit . Using (13) and (14), the end-to-end throughput (11) now becomes Like (12), the expression (15) is consistent with the finding T e2e = 1 for fully connected networks. In this case every node has the same node inbetweeness B i = N − 1, which results in B cum i = N(N − 1) for the cumulative node inbetweeness.
As can be read off from Fig. 5 the estimate (15) is closer to the genericdata-traffic e2e-throughput than the previous estimate (12). For some of the N ≤ 100 network models, like II, III and V, it even almost matches its datatraffic counterpart. A similar statement can be given for network models I and II in the 100 ≤ N ≤ 2000 regime; compare also the first and third rows of Table 3. According to the expression (15) the scaling exponents of T e2e ∼ N γ are directly determined from the scaling behavior of sup i B cum i , which has already been summarized in Table 2, and are almost identical to the corresponding data-traffic results. In retrospect, this represents a justification for the estimate (15).

Throughput III: sending-times estimate
The modeling (14) of the average sending time does not account for its proper dependence on the packet creation rate µ. This shortcoming will now be removed.
Let us assume that node i has at least one packet to forward. If all nodes in its neighborhood have no packets at this instance, then there is no competition for medium access and node i can send its packet right away. In this case τ i = 1. Competition sets in once some of the one-hop neighbors also have packets to forward. In addition, also some of the two-hop neighbors enter the competition, once they have packets to transmit to one-hop neighbors of i. This brings us to the structural ansatz: For simplification, we neglect spatio-temporal correlations of the network traffic. The independent-node picture then leads to for the competition term from the one-hop neighbors. It sums over the probabilities of ingoing one-hop neighbors to have at least one packet (n j 1 ≥ 1) to forward. On the same footing, the competition term from the two-hop neighbors results to be Here it is not sufficient for a two-hop neighbor j 2 to have at least one packet, the packet also needs to be forwarded to a one-hop neighbor j 1 in order to compete with i for medium access. The ratio B j 2 ↔j 1 /2B j 2 represents this fraction.
Note, that with (18) the competition strength of the two-hop neighbors is overestimated. Active three hop-neighbors might have already blocked some of the two-hop neighbors, so that the sum over j 2 should not extend to the complete two-hop neighborhood of node i. To a minor fraction this overestimation is also true for the expression (17), since a competing one-hop neighbor might already be blocked by an earlier assigned transmission between two two-hop neighbors. Consequently, the expressions (17) and (18) should be corrected by the probability that the one-and two-hop neighbor is not blocked, respectively. For the moment this is too much of a complication. From now on we will operationally proceed with two versions of (16), one excluding and the other including the ∆τ 2 contribution (18).
We are left to model the probability distributions p(n i ) of the queue lengths in the independent-node picture. It is sufficient to characterize the single-node data traffic statistics by the average in-and out-flux. In the stationary limit, this immeadiately leads to the rate equation Its solution leads to Making again use of (9) and (13), the proposed relation (16) for the average sending time then transforms into an inhomogeneous set of N coupled linear equations: The solution for the node-dependent average sending times will explicitly depend on the packet creation rate µ in a nonlinear way.
Let us stress this last point by picking a fully connected network as an example. Since every node is already a one-hop neighbor to each other, the last term on the righthand side of (21) has to be dropped. Furthermore, B i = N − 1 for every node and by symmetry all τ i = τ are identical. This transforms (21) into τ = (1 − µ(N − 1)) −1 , which is a nonlinear function of the packet creation rate. Let us continue for a moment, use the last result for the out-flux (9) and equate it to the in-flux (13), then as expected the critical network load results in µ crit = 1/N. Upon inserting this into the expression for the sending time, we arrive at τ (µ crit ) = N, which again reflects our intuition that at the critical network load every node has to compete with every other node for medium access.
Of course for other, more complicated network structures a further analytical insight into (21) is hard to give. However, once a specific network realization of size N is constructed, the numerically accessible node and link inbetweeness variables serve as input and the coupled linear equations can be solved numerically as a function of µ.
The solution of (21) fixes the out-flux (9). Upon setting this equal to the in-flux (8), the node-specific critical packet creation rate is determined to (10) and (11) this finally leads to the expression for the end-to-end throughput. For consistency, we again check on fully connected networks with B i = N − 1 and τ i (µ crit i ) = N, which leads to T e2e = 1.
Depending on whether the two-hop contribution ∆τ 2 is ex-or included in (21), two further estimates for the end-to-end throughput can be given for network models I-V. They are both illustrated in Fig. 5. The ∆τ 2 -excluding estimate yields an end-to-end throughput a little larger than the result obtained from the generic data traffic simulations. Except for network model I, the ∆τ 2including estimate produces a remarkable agreement with the generic datatraffic observations for small network sizes. For larger network sizes of models I and II the two estimates with and without ∆τ 2 narrowly sandwich the generic data-traffic outcome. Moreover, the fourth and fifth row of Table 3 confirm that the corresponding scaling exponents for T e2e ∼ N γ are in close agreement with those found from the generic data traffic simulations. All of this clearly demonstrates that the deviations from the previously proposed γ = 1/2 [24] are a consequence of the most-critical-node effect and that these deviations do show a strong dependence on the underlying network structure.

Conclusion and Outlook
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 efficient network structures in order to find 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 endto-end communications per time without network overloading. A generic data traffic 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 T e2e ∼ N γ with network size N, (iii) contrary to current mean-field belief [24] γ = 0.5 due to the most-critical node effect, and (iv) the scaling exponent γ depends on the specific structure of the picked network model. Another, although smaller discovery along the way has been that different network structure models lead to quite different average transmission power values, but once the latter is weighted with the amount of data traffic passing over a node, the differences in power consumption between the 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 different user behavior for the modeling of data traffic need to be addressed. Additional network structure models, directly resulting from the global optimization of design principles, like the maximization of 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 then also becoming important. This underlines that it is still a longer way to reach a truly selforganizational 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 selforganization also from other networked complex systems out of physics, biology and sociology.
6 Appendix: graph-theoretical variables Node degree The node degree k i = N j=1 a ij a ji counts the number of bidirected neighbors of node i. The N×N adjacency matrix a ij = 1 (link i→j exists) or 0 (link i→j does not exist, or i = j) most naturally embraces the existence and nonexistence of links between nodes. The node degree is smaller or equal to the outgoing node degree k out i = N j=1 a ij or the ingoing node degree k in i = N j=1 a ji . The sets of bidirected, outgoing and ingoing neighbors of node i are denoted as N i , N out i and N in i , respectively.
Link degree Using the definition N i↔j = (N i ∪ N j )\{i, j} for all bidirected links i↔j, the link degree k i↔j = |N i↔j | is similar to the node degree k i . It counts the number of bidirected neighbors, which are attached either to node i or to node j or to both. Two straightforward and selfexplaining generalizations are k out i↔j and k in i↔j . They are of direct relevance for wireless multihop ad hoc networks. k out i↔j counts all outgoing neighboring nodes of the active one-hop link i↔j, which are silenced by medium access control, and k in i↔j represents the maximum number of possible data packet senders, which directly compete with nodes i and j for medium access.
Cluster coefficient (node-based) The cluster coefficient C i = (2/[k i (k i − 1)]) j 1 >j 2 ∈N i a j 1 j 2 a j 2 j 1 is another popular observable [35]. It counts the number of existing bidirected links with respect to all possible bidirected links among the nodes belonging to the bidirected neighborhood N i of node i. Onedirected variants of the cluster coefficient are not considered.
Cluster coefficient (link-based) Analogous to the distinction between node and link degree, the cluster coefficient can not only be defined in the node-based manner, but also in the link-based manner C i↔j = (2/[k i↔j (k i↔j − 1)]) m 1 >m 2 ∈N i↔j a m 1 m 2 a m 2 m 1 . It counts the number of existing bidirected links with respect to all possible bidirected links among the nodes belonging to the bidirected neighborhood N i↔j of link i↔j.
Diameter The shortest-path distance d ij counts the number of bidirected hops along the shortest (in units of hops) path between nodes i and j. The diameter D = d ij is given by double averaging, in the first step a mean over all node pairs of one network realization and in the second step a mean over a sample of network realizations.
Node Inbetweeness For simplicity, we assume table-based shortest-path routing using bidirected links for all possible end-to-end communications within the network. In general different nodes will be used with different frequency for the relaying of packets. A measure of this frequency is given by the node inbetweeness B i , which counts the number of shortest paths out of the N(N −1) different shortest end-to-end communication routes going via node i. To be more precise, all nodes that are subsequently transmitting along such a shortest path, add a one to their respective node-inbetweeness counter; this includes the initially transmitting node, but not the final recipient. If between two ends more than one, say n shortest paths exist, then each path is weighted with 1/n and nodes along such a path add this weight to their node-inbetweeness counter. This definition of node inbetweeness is similar to the well known betweenness centrality [36]. Contrary to the former, the latter excludes contributions from the initial and final node. For the calculation of the node inbetweeness we use an all-pairs shortest path algorithm similar to that described in Ref. [36]. The sum rule relates the average node inbetweeness to the network diameter.
Link Inbetweeness Similar to the definition of node inbetweeness the link inbetweeness is a measure for the importance of a link. The link inbetweeness B i↔j counts the number of shortest paths that contain the link i↔j. If there exist n shortest paths between two nodes, we proceed as described above for the node inbetweeness, where each of these paths gets the weight 1/n. The link inbetweeness is connected with the node inbetweeness by the flux rule which allows to express the mean link inbetweeness in terms of the network diameter and the mean node degree.
Cumulative Node Inbetweeness For our discussion in Sect. 4 on the end-to-end throughput the quantity is of relevance. We call it the cumulative node inbetweeness, since it adds the node inbetweennesses of all ingoing neighbors to the node inbetweeness of node i. The second term on the right-hand side of (26), when divided by B i , can be seen as an inbetweeness-weighted ingoing node degree. By reordering, the mean can be expressed as B cum i = B i (1 + k out i ) .