We study benefits of opportunistic routing in a large wireless ad hoc network by examining how the power, delay, and total throughput scale as the number of source-destination pairs increases up to the operating maximum. Our opportunistic routing is novel in a sense that it is massively parallel, i.e., it is performed by many nodes simultaneously to maximize the opportunistic gain while controlling the inter-user interference. The scaling behavior of conventional multi-hop transmission that does not employ opportunistic routing is also examined for comparison. Our results indicate that our opportunistic routing can exhibit a net improvement in overall power-delay trade-off over the conventional routing by providing up to a logarithmic boost in the scaling law. Such a gain is possible since the receivers can tolerate more interference due to the increased received signal power provided by the multi-user diversity gain, which means that having more simultaneous transmissions is possible. Multi-hop, multi-user diversity, opportunistic routing, source-destination pair, wireless ad hoc network. , Gupta and Kumar introduced and studied the throughput scaling in large wireless ad hoc networks. They showed that a total throughput scaling of Θ( n/ log n) [bps/Hz] can be obtained by using a multihop strategy when n source-destination (S-D) pairs are randomly distributed in a unit area. 1 Multi-hop schemes were then further developed and analyzed in the literature [3]-[10] while their throughput per S-D pair scales far less than Θ(1). Recent studies [11], [12] have shown that we can actually achieve Θ(n 1−ǫ ) scaling for an arbitrarily small ǫ > 0, i.e., an arbitrarily linear scaling of the total throughput, by using a hierarchical cooperation strategy, thereby achieving the best result we can hope for. Besides the studies to improve the throughput up to the linear scaling, an important factor that we need to consider in practical wireless networks is the presence of multi-path fading. [21] , strategies for improving the throughput scaling over non-faded environments were shown in wireless network models that do not incorporate geometric path loss. In [22] , it was shown how fading improves the throughput using opportunistic routing when a single active S-D pair exists in a wireless ad hoc network. In this paper, we analyze the benefits of fading by utilizing opportunistic routing in multi-hop transmissions when there are multiple randomly located S-D pairs in a large wireless ad hoc network. Our routing protocol describes how multiple nodes perform opportunistic routing simultaneously in a massive scale. To our knowledge, such an attempt for the network model has never been conducted in the literature. Since the throughput scaling of a multi-hop protocol is far less than linear, it is natural to assume that only a subset of S-D pairs are active at a time and active S-D pairs are chosen in a round robin fashion. In this paper, we consider a general scenario where the the number of active S-D pairs scales as a function of n. We are interested in improving the number of simultaneously supportable S-D pairs to maintain a constant throughput per S-D pair by using opportunistic routing. In most network applications, power and delay are also key performance measures along with the throughput. The trade-off among these measures has been examined in terms of scaling laws in some papers [8]-[10], [23] . In this paper, we analyze a power-delay-throughput trade-off of both opportunistic routing and regular multi-hop routing as the number of S-D pairs increases up to the operating maximum, while per-node transmission rate is set to a constant. We first show the existence of a fundamental trade-off between the total transmission power consumed by all hops per S-D pair, the average number of hops per S-D pair, i.e., delay, and the number of active S-D pairs, which is proportional to the total throughput since we assume per-node transmission rate is a constant. It is investigated whether power can be reduced at the expense of increased delay for both routing scenarios, but a net improvement in overall power-delay trade-off can be obtained with opportunistic routing. The improvement comes from the MUD gain over the conventional multi-hop routing. This increases the average received signal power, which in turn makes it possible to have more simultaneous transmissions since more interference is tolerated while per-node transmission rate is maintained. More specifically, we show that such an MUD gain leads to a logarithmic performance improvement.
In REF , multiple disjoint routing paths for a source-destination pair were provided through the unit cell division and signaling message exchange and constant per-node transmission rate is maintained.
Parallel Opportunistic Routing in Wireless Networks
Computer Science Mathematics