تاثیر ساختار شبکه در ظرفیت ارتباطات بی سیم تک کاره چند جهشی

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.