In their seminal work, Gupta and Kumar  introduced and characterized sum-rate scaling in a large wireless ad hoc network. They showed that for a network of 𝑛 sourcedestination (S-D) pairs randomly distributed in a unit area, the total throughput scales as 𝛩 (we use the following notation: i) 𝑓(𝑥) = 𝑂(𝑔(𝑥)) means that there exist constants 𝑀 and 𝑚 such that 𝑓(𝑥) ≤ 𝑀𝑔(𝑥) for all 𝑥 > 𝑚 . ii) 𝑓(𝑥) = 𝛺(𝑔(𝑥)) if 𝑔(𝑥) = 𝑂(𝑓(𝑥)) . iii) 𝑓(𝑥) = 𝛩(𝑔(𝑥)) and 𝑔(𝑥) = 𝑂(𝑓(𝑥))). This throughput scaling is achieved using a multihop communication scheme. Multihop schemes were then further developed and analyzed in the literature [2-4]. A recent result has shown that we can actually achieve a linear scaling of the total throughput in the network by using a hierarchical cooperation strategy  and infrastructure nodes .
Besides the studies conducted to achieve a linear scaling, an important factor that we need to consider in practical wireless networks is the presence of multipath fading. The effect of fading on the scaling laws was studied in [2, 3, 7], where it was shown that achievable scaling laws do not fundamentally change if all nodes are assumed to have their own traffic demands, i.e., if heavily loaded network environments are assumed [2, 3, 7] or the effect of fading is averaged out [2, 7]. However, in the literature, there are some results on the usefulness of fading, where one can exploit an opportunistic gain, e.g., opportunistic scheduling , opportunistic beam-forming , and random beamforming  in broadcast channels. Such opportunism can also be obtained in an ad hoc network by using opportunistic routing in a multihop fashion. In [11, 12], it was shown that fading can improve the throughput by using opportunistic routing when a single S-D pair exists in an ad hoc network. Recent research  has shown that in a large ad hoc network, parallel opportunistic multihop routing, performed simultaneously by multiple S-D pairs, exhibits a net improvement in the overall power-delay trade-off over the conventional multihop routing [1, 4] by providing up to a logarithmic gain. The studies described in [11-13] considered the scaling law for a large value of 𝑛, and thus, it is not clear whether such an opportunistic gain is possible for feasible network conditions (e.g., finite 𝑛).
In this study, our work is basically built upon the study discussed in  to illuminate the performance of parallel opportunistic multihop routing performed to maximize the opportunistic gain in a large ad hoc network with fading. We first analyze a cut-set upper bound on the throughput scaling law of the network. It is shown that for certain feasible operating regimes with respect to the number of active S-D pairs, our upper bound almost matches the throughput scaling achieved by parallel opportunistic routing; i.e., the order optimality of the scheme is guaranteed. In addition, computer simulations are performed to verify the performance of the existing opportunistic routing for finite network conditions and to show trends consistent with the analytical predictions in the scaling law .
The rest of this paper is organized as follows: Section II describes the system and channel models. In Section III, the existing parallel opportunistic multihop routing is reviewed briefly. In Section IV, the cut-set upper bound on the total throughput is derived. Section V shows simulation results for the power-delay trade-off. Finally, Section VI summarizes the paper with some concluding remarks.
Throughout this paper, 𝔼[∙] denotes the expectation. Unless otherwise stated, all logarithms are assumed to be to the base 2.
We consider a two-dimensional wireless network that consists of 𝑛 nodes placed on a square of unit area, i.e., a dense network [1, 4]. The distance between two neighboring nodes is assumed to be 1 unit of distance apart from each other; i.e., a regular network is assumed. We assume that there are 𝑀(𝑛) active S-D pairs, where 𝑀(𝑛) scales slower than 𝑛, which is a feasible scenario in lightly loaded network environments. We randomly pick a match of S-D pairs such that each node is the destination of exactly one source.
The received signal
Since there is no CSI at the transmitters, we assume that each source transmits data to its destination at a fixed target rate. As in the earlier studies [8-10] dealing with opportunism under the block fading model, we suppose that a packet is decoded successfully if the received signal-tointerference- and-noise ratio exceeds a pre-determined threshold. Then, the total throughput
In this section, we briefly review the existing multihop routing protocols with and without parallel opportunistic routing . Let us first introduce the scaling parameters
Mode 1: A relay node that is horizontally or vertically two or three cells apart from the transmitter is chosen to transmit the packet in the next hop. When choosing the relay for the next hop, one needs to consider nodes that correctly decoded the packet. If there is more than one candidate relay, then we choose one among them arbitrarily. Otherwise, an outage occurs. We use Mode 1 until the last two hops to the destination, and then, we switch to Mode 2.
Mode 2: If we use Mode 1 for the last hop, we cannot get any opportunistic gain since the destination is predetermined. Hence, we use the following two-step procedure for Mode 2. Assuming 𝑚 nodes in a cell right ahead of the last hop to the destination, we arbitrarily partition the cell into sub-cells of equal size. In the first step, one node is opportunistically chosen among nodes that received the packet correctly in each sub-cell. Then, nodes in the cell are chosen as potential relays for the packet. In the second step, the final destination sees which one of the relaying nodes in each cell will be the transmitter for the next hop (i.e., the last hop to the destination). Finally, the packet from the selected relaying node in the cell is transmitted to the final destination.
Besides the opportunistic routing, for the sake of comparison, a plain multihop transmission [1, 4] is considered with a pre-determined path for each S-D pair consisting of a source, a destination, and a set of relaying nodes. Therefore, there is no opportunistic gain.
In this section, to see how closely the achievable throughput scaling with and without parallel opportu-nistic multihop routing  approaches an information-theoretic upper bound under certain operating regimes, we analyze the cut-set upper bound on the total throughput. We start from the following lemma:
Lemma 1. Suppose that 𝑔
with high probability as 𝑛 tends to infinity.
which tends to zero as 𝑛 → ∞ . Similarly, by the Chernoff bound, it follows that
Thus, it turns out that the term scales as 𝑛 with probability of at least
which tends to one as 𝑛 → ∞ . This completes the proof of the lemma. □
Using Lemma 1, we establish our main theorem, which shows the cut-set upper bound on the total throughput.
Theorem 1. The total throughput
which is bounded by 𝑀(𝑛) log𝑛. Here, the first equality and the last inequality hold due to (2) and Lemma 1, respectively. The second inequality comes from the fact that per-node distance is at least . Finally, for 𝑀(𝑛) S-D pairs, we obtain
Note that the upper bound in Theorem 1 assumes the full cooperation among all receiver nodes. For all 𝑀(𝑛) = 𝑂(𝑛), our upper bound shown under the multipath fading environment matches the upper bound derived under the random phase model, i.e., no multipath fading assumption . Furthermore, it is seen that the achievable rate
In this section, we use computer simulations to confirm the analytical results (i.e., the achievable throughput, power, and delay scaling laws) shown in . It was shown in  that parallel opportunistic multihop routing exhibits a net improvement in the overall power-delay trade-off over the conventional non-opportunistic routing for a large value of n. The performance of the parallel opportunistic and nonopportunistic multihop routing schemes is now examined for a finite parameter 𝑛.
We slightly modify our system model to make it suitable for numerical evaluation. Horizontal routing is only needed, assuming that a source and its corresponding destination lie on the same horizontal line. Suppose that there are 1024 regularly spaced nodes (i.e., 𝑛 = 1024 ) in the whole network and the path-loss exponent
Figs. 1 and 2 show how the power and the delay change with respect to the number of simultaneously active S-D pairs, corresponding to the total throughput, respectively. Specifically, when the delay is given by 2, 4, and 8, both the corresponding power and the number of active S-D pairs are shown in Figs. 1 and 2. Here,
The cut-set upper bound of ad hoc networks in the presence of fading has been analyzed. We have proven that the achievable rate T(𝑛) = Θ(𝑀(𝑛)) in  almost matches our upper bound as long as 𝑀(𝑛) scales between log𝑛 and 𝑛1/2−𝜀. The trade-offs with and without opportunistic routing have also been verified by a numerical evaluation for finite network conditions.