This paper develops upper bounds on the end-to-end transmission capacity of multihop wireless networks. Potential source-destination paths are dynamically selected from a pool of randomly located relays, from which a closed-form lower bound on the outage probability is derived in terms of the expected number of potential paths. This is in turn used to provide an upper bound on the number of successful transmissions that can occur per unit area, which is known as the transmission capacity. The upper bound results from assuming independence among the potential paths, and can be viewed as the maximum diversity case. A useful aspect of the upper bound is its simple form for an arbitrary-sized network, which allows insights into how the number of hops and other network parameters affect spatial throughput in the nonasymptotic regime. The outage probability analysis is then extended to account for retransmissions with a maximum number of allowed attempts. In contrast to prevailing wisdom, we show that predetermined routing (such as nearest neighbor) is suboptimal, since more hops are not useful once the network is interference-limited. Our results also make clear that randomness in the location of relay sets and dynamically varying channel states is helpful in obtaining higher aggregate throughput, and that dynamic route selection should be used to exploit path diversity.
In addition, the above-mentioned diversity gain from dynamic relay selection has been utilized for opportunistic routing @cite_15 @cite_2 so any node that overhears packets can participate in forwarding. Reference @cite_2 appeared to be the first investigation of the capacity improvement from opportunistic routing compared with predetermined routing in a Poisson field. However, the performance gain shown in @cite_2 is based on simulation without an exact mathematical derivation. Different random hop selection strategies have also been studied and compared @cite_3 @cite_19 without giving tractable throughput bounds. Hence, characterizing the available diversity gain is worth investigating. In this paper, we will explicitly show that since a pool of randomly located relays with varying channels provides more potential routes, more randomness is preferable.
@cite_19 @cite_15 @cite_3 @cite_2
2149622712 2104911317 2043288730 2155564629
This paper addresses the routing problem for large wireless networks of randomly distributed nodes with Rayleigh fading channels. First, we establish that the distances between neighboring nodes in a Poisson point process follow a generalized Rayleigh distribution. Based on this result, it is then shown that, given an end-to-end packet delivery probability (as a quality of service requirement), the energy benefits of routing over many short hops are significantly smaller than for deterministic network models that are based on the geometric disk abstraction. If the permissible delay for short-hop routing and long-hop routing is the same, it turns out that routing over fewer but longer hops may even outperform nearest-neighbor routing, in particular for high end-to-end delivery probabilities. This paper describes Extremely Opportunistic Routing (ExOR), a new unicast routing technique for multi-hop wireless networks. ExOR forwards each packet through a sequence of nodes, deferring the choice of each node in the sequence until after the previous node has transmitted the packet on its radio. ExOR then determines which node, of all the nodes that successfully received that transmission, is the node closest to the destination. That closest node transmits the packet. The result is that each hop moves the packet farther (or average) than the hops of the best possible pre-determined route.The ExOR design addresses the challenge of choosing a forwarding node after transmission using a distributed algorithm. First, when a node transmits a packet, it includes in the packet a simple schedule describing the priority order in which the potential receivers should forward the packet. The node computes the schedule based on shared measurements of inter-node delivery rates. ExOR then uses a distributed slotted MAC protocol for acknowledgements to ensure that the receivers agree who the highest priority receiver was.The efficacy of ExOR depends mainly on the rate at which the reception probability falls off with distance. Simulations based on measured radio characteristics [6] suggest that ExOR reduces the total number of transmissions by nearly a factor of two over the best possible pre-determined route. The multihop spatial reuse Aloha (MSR-Aloha) protocol was recently introduced by Baccelli et aL, where each transmitter selects the receiver among its feasible next hops that maximizes the forward progress of the head of line packet towards its final destination. They identify the optimal medium access probability (MAP) that maximizes the spatial density of progress, defined as the product of the spatial intensity of attempted transmissions times the average per-hop progress of each packet towards its destination. We propose a variant called longest edge routing where each transmitter selects its longest feasible edge, and then identifies a packet in its backlog whose next hop is the associated receiver. The main contribution of this work (and of Baccelli et aL) is the use of stochastic geometry to identify the optimal MAP and the corresponding optimal spatial density of progress. In classical routing strategies for multihop mobile wireless networks packets are routed on a pre-defined route usually obtained by a shortest path routing protocol. In opportunistic routing schemes, for each packet and each hop, the next relay is found by dynamically selecting the node that captures the packet transmission and which is the nearest to the destination. Such a scheme allows each packet to take advantage of the local pattern of transmissions and fadings at any slot and at any hop. The aim of this paper is to quantify and optimize the potential performance gains of such opportunistic routing strategies compared with classical routing schemes. The analysis is conducted under the following lower layer assumptions: the Medium Access (MAC) layer is a spatial version of Aloha which has been shown to scale well for large multihop networks; the capture of a packet by some receiver is determined by the Signal over Interference and Noise Ratio (SINR) experienced by the receiver. The paper contains a detailed simulation study which shows that such time-space opportunistic schemes very significantly outperform classical routing schemes. It also contains a mathematical study where we show how to optimally tune the MAC parameters so as to minimize the average number of time slots required to carry a typical packet from origin to destination on long paths. We show that this optimization is independent of network density.