Opportunistic routing was originally introduced in various multihop network environments to reduce the number of hops in such a way that, among the relays that decode the transmitted packet for the current hop, the one that is closest to the destination becomes the transmitter for the next hop. Unlike the conventional opportunistic routing case where there is a single active SD pair, for an ad hoc network in the presence of fading, we investigate the performance of
parallel
opportunistic multihop routing that is simultaneously performed by many sourcedestination (SD) pairs to maximize the opportunistic gain, thereby enabling us to obtain a logarithmic gain. We first analyze a cutset upper bound on the throughput scaling law of the network. Second, 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. More specifically, we evaluate both power and delay with respect to the number of active SD pairs and then, numerically show a net improvement in terms of the powerdelay tradeoff over the conventional multihop routing that does not consider the randomness of fading.
I. INTRODUCTION
In their seminal work, Gupta and Kumar
[1]
introduced and characterized sumrate scaling in a large wireless ad hoc network. They showed that for a network of 𝑛 sourcedestination (SD) 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
[5]
and infrastructure nodes
[6]
.
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
[8]
, opportunistic beamforming
[9]
, and random beamforming
[10]
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 SD pair exists in an ad hoc network. Recent research
[13]
has shown that in a large ad hoc network, parallel opportunistic multihop routing, performed simultaneously by multiple SD pairs, exhibits a net improvement in the overall powerdelay tradeoff 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
[13]
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 cutset 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 SD 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
[13]
.
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 cutset upper bound on the total throughput is derived. Section V shows simulation results for the powerdelay tradeoff. 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.
II. SYSTEM AND CHANNEL MODELS
We consider a twodimensional 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 SD pairs, where 𝑀(𝑛) scales slower than 𝑛, which is a feasible scenario in lightly loaded network environments. We randomly pick a match of SD pairs such that each node is the destination of exactly one source.
The received signal
y_{k}
at node
k
∈ {1, ⋯, 𝑛} at a given time instance is given by
where
X_{i}
∈
denotes the signal transmitted by node
i
,
n_{k}
represents the circularly symmetric complex additive white Gaussian noise with zero mean and variance
N
_{0}
, and I ⊂ {1, ⋯
n
} denotes the set of simultaneously transmitting nodes. The channel
h_{ki}
is given by
where 𝑔
_{ki}
represents the complex fading process between nodes
i
and
k
, which is assumed to be Rayleigh with
[𝑔
_{ki}

^{2}
] = 1 and independent for different values of
i
and
k
. Moreover, we assume the block fading model, where 𝑔
_{ki}
is constant during one packet transmission and changes to a new independent value for the next transmission.
r_{ki}
and α > 2 denote the distance between two nodes
i
and
k
and and the pathloss exponent, respectively. We assume that the channel state information (CSI) is available at all the receivers, but not at the transmitters.
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 signaltointerference andnoise ratio exceeds a predetermined threshold. Then, the total throughput
T
(𝑛) of the network would be given by Ω(𝑀(𝑛)) if there is no transmission failure; i.e., there is no outage.
III. OVERVIEW OF PARALLEL OPPORTUNISTIC ROUTING
In this section, we briefly review the existing multihop routing protocols with and without parallel opportunistic routing
[13]
. Let us first introduce the scaling parameters
P
(𝑛) and
D
(𝑛) The average number of hops per SD pair is interpreted as the average delay and is denoted by
D
(𝑛). The parameter
P
(𝑛) denotes the average total transmit power used by all hops for an SD pair. Assuming that the transmit power is the same for each hop, we see that
P
(𝑛) is equal to
D
(𝑛) times the transmit power per hop. We divide the whole area into 1/
A_{s}
(𝑛) square cells with a percell area of
A_{s}
(𝑛). We assume XY routing; i.e., the route for an SD pair consists of a horizontal and a vertical path. All transmitters in a cell transmit simultaneously. The parallel opportunistic multihop routing consists of two transmission modes, Modes 1 and 2, where Mode 2 is used for the last two hops to the destination and Mode 1 is used for all other hops.
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 twostep procedure for Mode 2. Assuming 𝑚 nodes in a cell right ahead of the last hop to the destination, we arbitrarily partition the cell into
subcells of equal size. In the first step, one node is opportunistically chosen among nodes that received the packet correctly in each subcell. 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 predetermined path for each SD pair consisting of a source, a destination, and a set of relaying nodes. Therefore, there is no opportunistic gain.
IV. CUTSET UPPER BOUND
In this section, to see how closely the achievable throughput scaling with and without parallel opportunistic multihop routing
[13]
approaches an informationtheoretic upper bound under certain operating regimes, we analyze the cutset upper bound on the total throughput. We start from the following lemma:
Lemma 1
. Suppose that 𝑔
_{ki}
is the complex fading process between nodes
i
and
k
, where the channel is Rayleigh with 𝔼[𝑔
_{ki}

^{2}
] = 1 and independent for different values of
i
and
k
. Then, it is shown that
with high probability as 𝑛 tends to infinity.
Proof
. From the Chernoff bound, for a constant
δ
> 0 independent of
k
, we obtain the following:
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 cutset upper bound on the total throughput.
Theorem 1
. The total throughput
T
(𝑛) in the network with 𝑀(𝑛) active SD pairs is upperbounded by 𝑀(𝑛) log𝑛 with high probability as tends to infinity.
Proof
. The proof essentially follows the steps similar to those of
[5]
. We basically use the singleinput multipleoutput cut by separating a source node from the rest of the network. Then, the total throughput for 𝑀(𝑛) SD pairs is upperbounded by
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 pernode distance is at least
. Finally, for 𝑀(𝑛) SD pairs, we obtain
T
(𝑛) = 𝑂(𝑀(𝑛) log𝑛), which completes the proof of the theorem. □
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
[5]
. Furthermore, it is seen that the achievable rate
T
(𝑛) = 𝛩(𝑀(𝑛)) of the routing protocols used in
[13]
is close to the upper bound up to log 𝑛 as long as 𝑀(𝑛) scales between log 𝑛 and 𝑛
^{1/2−∊}
for an arbitrarily small
∊
> 0 due to various constraints assumed in
[13]
. In other words, under the operating regimes 𝑀(𝑛) = (log 𝑛) and 𝑀(𝑛) = (𝑛
^{1/2−∊}
), the order optimality is guaranteed.
V. NUMERICAL EVALUATION
In this section, we use computer simulations to confirm the analytical results (i.e., the achievable throughput, power, and delay scaling laws) shown in
[13]
. It was shown in
[13]
that parallel opportunistic multihop routing exhibits a net improvement in the overall powerdelay tradeoff over the conventional nonopportunistic 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 pathloss exponent
α
is given by 4. In this case, we evaluate the average delay
D
(𝑛), the power
P
(𝑛), and the number of active SD pairs, 𝑀(𝑛), such that both the received signal power from the desired transmitter and the total interference power from all other simultaneously transmitting nodes are kept at 1 on average, as in
[13]
.
Figs. 1
and
2
show how the power and the delay change with respect to the number of simultaneously active SD 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 SD pairs are shown in
Figs. 1
and
2
. Here,
R_{o}
and
R
_{𝑛o}
denote the curves with and without opportunistic routing, respectively. We observe that the power decreases while the delay increases as we have more active SD pairs in both schemes. That is, the power is reduced at the expense of the increased delay. Furthermore, it is seen that the use of opportunistic routing increases the power as compared to the nonopportunistic routing case, but it can reduce the delay significantly. Thus, it is not clear whether opportunistic routing is beneficial or not from
Figs. 1
and
2
. Now, we plot the power versus the delay, as shown in
Fig. 3
. In this figure, it can be clearly seen that opportunistic routing
R_{o}
exhibits a better overall powerdelay tradeoff than the nonopportunistic scheme
R
_{𝑛o}
. Although the curves in
Figs. 1
–
3
look slightly different from the analytical ones in
[13]
, it can be seen that the overall trends are similar.
Power with respect to the number of active sourcedestination (SD) pairs.
Delay with respect to the number of active sourcedestination (SD) pairs.
Powerdelay tradeoff.
VI. CONCLUSION
The cutset upper bound of ad hoc networks in the presence of fading has been analyzed. We have proven that the achievable rate T(𝑛) = Θ(𝑀(𝑛)) in
[13]
almost matches our upper bound as long as 𝑀(𝑛) scales between log𝑛 and 𝑛
^{1/2−𝜀}
. The tradeoffs with and without opportunistic routing have also been verified by a numerical evaluation for finite network conditions.
Acknowledgements
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (MSIP) (No. 2012R1A1A1044151).
BIO
WonYong Shin
received his B.S. in Electrical Engineering from Yonsei University, Seoul, Korea, in 2002. He received his M.S. and Ph.D. in Electrical Engineering and Computer Science from Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea, in 2004 and 2008, respectively. From February 2008 to April 2008, he was Visiting Scholar in the School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA. From September 2008 to April 2009, he was with the Brain Korea Inst itute and CHiPS at KAIST as Postdoctoral Fellow. From August 2008 to April 2009, he was with Lumicomm Inc., Daejeon, Korea, as Visiting Researcher. In May 2009, he joined Harvard University as Postdoctoral Fellow and was promoted to Research Associate in October 2011. Since March 2012, he has been with the Department of Computer Science and Engineering, Dankook University, Yongin, Korea, where he is currently Assistant Professor. His research interests include information theory, communications, signal processing, and their applications to multiuser networking issues.
Gupta P.
,
Kumar P. R.
2000
“The capacity of wireless networks,”
IEEE Transactions on Information Theory
46
(2)
388 
404
DOI : 10.1109/18.825799
Xue F.
,
Xie L. L.
,
Kumar P. R
2005
“The transport capacity of wireless networks over fading channels,”
IEEE Transactions on Information Theory
51
(3)
834 
847
DOI : 10.1109/TIT.2004.842628
Nebat Y.
,
Cruz R. L.
,
Bhardwaj S.
2009
“The capacity of wireless networks in nonergodic random fading,”
IEEE Transactions on Information Theory
55
(6)
2478 
2493
DOI : 10.1109/TIT.2009.2019343
El Gamal A.
,
Mammen J.
,
Prabhakar B.
,
Shah D.
2006
“Optimal throughputdelay scaling in wireless networks. Part I: The fluid model,”
IEEE Transactions on Information Theory
52
(6)
2568 
2592
DOI : 10.1109/TIT.2006.874379
Ozgur A.
,
Leveque O.
,
Tse D. N.
2007
“Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks,”
IEEE Transactions on Information Theory
53
(10)
3549 
3572
DOI : 10.1109/TIT.2007.905002
Shin W. Y.
,
Jeon S. W.
,
Devroye N.
,
Vu M. H.
,
Chung S. Y.
,
Lee Y. H.
,
Tarokh V.
2011
“Improved capacity scaling in wireless networks with infrastructure,”
IEEE Transactions on Information Theory
57
(8)
5088 
5102
DOI : 10.1109/TIT.2011.2158881
Jovicic A.
,
Viswanath P.
,
Kulkarni S. R.
2004
“Upper bounds to transport capacity of wireless networks,”
IEEE Transactions on Information Theory
50
(11)
2555 
2565
DOI : 10.1109/TIT.2004.836936
Knopp R.
,
Humblet P. A.
1995
“Information capacity and power control in singlecell multiuser communications,”
in Proceedings of the IEEE International Conference on Communications
Seattle, WA
331 
335
Viswanath P.
,
Tse D. N. C.
,
Laroia R.
2002
“Opportunistic beamforming using dumb antennas,”
IEEE Transactions on Information Theory
48
(6)
1277 
1294
DOI : 10.1109/TIT.2002.1003822
Sharif M.
,
Hassibi B.
2005
“On the capacity of MIMO broadcast channels with partial side information,”
IEEE Transactions on Information Theory
51
(2)
506 
522
DOI : 10.1109/TIT.2004.840897
Chung S. Y.
2006
“On the transport capacity of wireless adhoc networks,”
in Proceedings of the International Symposium on Information Theory and Its Application
Seoul, Korea
546 
550
Shin W. Y.
,
Ishibashi K.
2012
“Effect of multiple antennas on the transport capacity in largescale ad hoc networks,”
IEICE Transactions on Communications
95
(10)
3113 
3119
Shin W. Y.
,
Chung S. Y.
,
Lee Y. H.
2013
“Parallel opportunistic routing in wireless networks,”
IEEE Transactions on Information Theory
59
(10)
6290 
6300
DOI : 10.1109/TIT.2013.2272884