In this work we develop a new theory to analyse the process of routing in large-scale ad-hoc wireless networks. We use a path integral formulation to examine the properties of the paths generated by different routing strategies in these kinds of networks. Using this theoretical framework, we calculate the statistical distribution of the distances between any source to any destination in the network, hence we are able to deduce a length parameter that is unique for each routing strategy. This parameter, defined as the effective radius, effectively encodes the routing information required by a node. Analysing the afore- mentioned statistical distribution for different routing strategies, we obtain a threefold result for practical Large-Scale Wireless Ad-Hoc Networks: 1) We obtain the distribution of the lengths of all the paths in a network for any given routing strategy, 2) We are able to identify "good" routing strategies depending on the evolution of its effective radius as the number of nodes, N , increases to infinity, 3) For any routing strategy with finit e effective radius, we demonstrate that, in a large-scale network, is equivalent to a random routing strategy and that its transport capacity scales asp Nbit-meters per second, thus retrieving the scaling law that Gupta and Kumar (2000) obtained as the limit for single-route large-scale wireless networks.
The use of random walks as an effective (or unique) strategy for routing in Large-Scale Ad-Hoc Networks has been suggested in some works @cite_1 @cite_13 . In these works, the common drive to use this strategy is the logical conclusion that effective distributed routing in a large-scale network is unfeasible as it would require solving an NP-complete problem @cite_9 .
@cite_13 @cite_9 @cite_1
1561598073 2112169033 2120361596
The task of moving data (i.e., the routing problem) in large-scale sensor networks has to contend with several obstacles, including severe power constraints at each node and temporary, but random, failures of nodes, rendering routing schemes designed for traditional communication networks ineffective. We consider the open problem of finding optimum routes between any fixed source-destination pair in a large-scale network, such that the communication load (i.e., the required power) is distributed among all the nodes, the overall latency is minimized, and the algorithm is decentralized and robust. A recent work addressed this problem in the context of a grid topology and showed how to obtain load-balanced routing, but transmissions are restricted to be among near-neighbors and the overall latency grows linearly with the number of nodes. We show how one can route messages between source and destination nodes along random small-world topologies using a decentralized algorithm. Specifically, nodes make connections independently (based only on the source and destination information in the packets), according to a distribution that guarantees an average latency of O(log sup 2 (N)), while preventing hotspot regions by providing an almost uniform distribution of traffic load over all nodes. Surprisingly, the randomized nature of the network structure keeps the average per-node power consumption almost the same as in the case of a grid topology (i.e., local transmissions), while providing an exponential reduction in latency, resulting in a highly fault-tolerant and stable design capable of working in very dynamic environments. The upcoming gigabit-per-second high-speed networks are expected to support a wide range of communication-intensive real-time multimedia applications. The requirement for timely delivery of digitized audio-visual information raises new challenges for next-generation integrated services broadband networks. One of the key issues is QoS routing. It selects network routes with sufficient resources for the requested QoS parameters. The goal of routing solutions is twofold: (1) satisfying the QoS requirements for every admitted connection, and (2) achieving global efficiency in resource utilization. Many unicast multicast QoS routing algorithms have been published, and they work with a variety of QoS requirements and resource constraints. Overall, they can be partitioned into three broad classes: (1) source routing, (2) distributed routing, and (3) hierarchical routing algorithms. We give an overview of the QoS routing problem as well as the existing solutions. We present the strengths and weaknesses of different routing strategies, and outline the challenges. We also discuss the basic algorithms in each class, classify and compare them, and point out possible future directions in the QoS routing area. We consider a routing problem in the context of large scale networks with uncontrolled dynamics. A case of uncontrolled dynamics that has been studied extensively is that of mobile nodes, as this is typically the case in cellular and mobile ad-hoc networks. In this paper however we study routing in the presence of a different type of dynamics: nodes do not move, but instead switch between active and inactive states at random times. Our interest in this case is motivated by the behavior of sensor nodes powered by renewable sources, such as solar cells or ambient vibrations. In this paper we formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random dynamic graphs. We argue that these random walks should be designed so that their resulting invariant distribution achieves a certain load balancing property, and we give simple distributed algorithms to compute the local parameters for the random walks that achieve the sought behavior. A truly novel feature of our formulation is that the algorithms we obtain are able to route messages along all possible routes between a source and a destination node, without performing explicit route discovery repair computations, and without maintaining explicit state information about available routes at the nodes. To the best of our knowledge, these are the first algorithms that achieve true multipath routing (in a statistical sense), at the complexity of simple stateless operations.