توزیع مسیریابی و تراکم کنترل در شبکه های ارتباطی چند جهشی بی سیم تک کاره

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.