IEEE COMMUNICATIONS LETTERS, VOL. 10, NO.

7, JULY 2006 531

A Cross-layer Optimization of IEEE 802.11 MAC
for Wireless Multihop Networks
June Hwang, Student Member, IEEE, and Seong-Lyun Kim, Member, IEEE
AbstractIntroducing multihop transmission in wireless net-
works has both pros and cons. It will improve the reliability of
each wireless link by reducing the average transmission distance.
On the other hand, it will add delay to the end-to-end QoS,
which is caused by multiple packet relays. In this Letter, we
analyze the optimal performance of the IEEE 802.11 based
multihop network, by jointly optimizing the carrier-sensing range
of CSMA/CA and the target data rate of each wireless link.
Index TermsWireless multihop networks, cross-layer opti-
mization, CSMA/CA, carrier-sensing range.
I. INTRODUCTION
T
HE IEEE 802.11 MAC (media access control) has been
widely used for wireless local area network [1]. It is
based on CSMA/CA (carrier sensing multiple access/collision
avoidance) with exponential random backoff [2]. The carrier
sensing scheme brings out two problems. The one, hidden
node problem can be solved with collision avoidance which
uses RTS (request-to-send) and CTS (clear-to-send) control
packets. However, the other exposed node problem is still
remained.
There are two points of view about the latter problem. The
authors in [3] pointed out that the exposed node problem
results in serious throughput degradation (end-to-end delay)
and unfairness issues in the wireless multihop networks. On
the other hand, it is concluded in [4] that the exposed node
problem may not necessarily be a problem. In some cases, the
CSMA/CA signaling will introduce reasonable spatial reuse
of radio channels, which reduces the interference and thus
increases the average throughput of the links. In particular,
if the complexity of carrier-sensing could be somehow
avoided, CSMA/CA could be a good strategy for handling
interference and maximizing the network capacity [4].
Thus, an interesting problem is how to adjust the sensing
range of CSMA/CA for the optimal spatial reuse in the
multihop network.
1
Another important subject is the target
data rate of each wireless link. The higher the target data rate
is, the more probable the retransmission by the exponential
random backoff is. In this Letter, we analyze the maximal
average end-to-end throughput of the IEEE 802.11 MAC based
wireless multihop network, by jointly optimizing the carrier
Manuscript received February 13, 2006. The associate editor coordinating
the review of this letter and approving it for publication was Dr. Jae Kim.
This work has been supported by CARUT-ITRC, the Ministry of Information
and Communication, Korea (IITA-2005-C1090-0502-0012).
The authors are with the School of Electrical and Electronic Engineering,
Yonsei University, 134 Sinchon-Dong, Seodaemun-Gu, Seoul 120-749, Korea
(email: [email protected]).
Digital Object Identier 10.1109/LCOMM.2006.060214.
1
In this Letter, we do not distinguish the transmission range from the
interference range.
Fig. 1. Multihop wireless network of a linear topology. The minimal reuse
hop is n =
D
R
=

3K, where K = i
2
+j
2
+ ij, i and j are non-negative
integers. K is 7 (i=2, j=1) in this example [8].
sensing range in the MAC layer and the target data rate in the
physical layer.
Introducing multihop has pros and cons: it will effectively
handle the interference but this is on the cost of packet delay
caused by multihop relays. There have been some previous
researches related to these issues [5]-[7]. However, even the
most relevant work to ours did not include the backoff delay
and analytic solutions [5]. The others [6], [7] evaluate the
maximum expected throughput of a single wireless link, rather
than investigating the throughput of the path-ow composed
of multihop wireless links. Thus, direct application of these
results to our problem is rather hopeless, which motivates our
work.
II. SYSTEM MODEL
Consider a multihop wireless network adopting a single-
frequency. We assume that the nodes are located at centers
and vertices of the hexagon with the same distance away
(Figure 1). The radius of a regular hexagon is R. The number
D denotes the nearest simultaneous transmission distance,
i.e., carrier sensing range. The geometrical distribution of
simultaneous transmitters resembles cochannel base stations
in a regular hexagonal cellular system. Among the nodes,
we consider a linear topology of M nodes. All nodes are
equipped with identical half-duplex radios
2
and with omni-
directional antennas. Consider an instant, at which the channel
gain (received power divided by transmitted power) between
every receiver i and every transmitter j is given by g
ij
. We
2
This means a node cannot transmit and receive simultaneously, and it
makes the constraint that the reuse hop distance has to be at least two hops.
1089-7798/06$20.00 c 2006 IEEE
532 IEEE COMMUNICATIONS LETTERS, VOL. 10, NO. 7, JULY 2006
will denote the power of transmitter i by p
i
. The signal-to-
interference-plus-noise ratio (SIR) at the receiver i is given
by:

i
(P) =
g
ij
p
j

k=i,j
g
ik
p
k
+
, (1)
where denotes the thermal noise at receiver i. The power
vector P contains the power value of each transmitting
node. The quantity (0, 1] denotes the normalized cross-
correlation between signals from different transmitters [8].
Due to the multipath fading, the full orthogonality may not
be assured, even if orthogonal codes are employed. For
simplicity, we assume the worst case of the orthogonality
= 1. However, analyzing the other cases is straightforward.
All packets are assumed to be of the same duration. In the
MAC layer, the network adopts CSMA/CA with the Binary
Exponential Backoff (BEB) for collision resolution.
III. OPTIMAL CARRIER SENSING RANGE AND
TARGET DATA RATE
Consider a multihop wireless network, where the carrier
sensing range allows the nodes more than n = D/R hop-
distance away to simultaneously transmit. In the SIR equation
(1), we assume the channel gain g
ij
is represented by:
g
ij
=
X
ij
d
ij

, (2)
where X
ij
follows the exponential distribution with the mean
1. The number d
ij
denotes the distance between receiver i and
transmitter node j, and is the path-loss exponent. We neglect
the effect of shadowing, assuming the linear route is set up
under no deep shadowing between any links. The random part
of the channel link gain is assumed to be independent of the
other links. If the transmission power of all nodes is assumed
to be same and the receiver noise is negligible, then from
Figure 1, the SIR (1) for a receiver node i located at the
corner of a cell is approximated as [8]:

i
(P) =
X
i
R

6
j=1
Y
j
D

+

12
k=7
Y
k
(

3D)

+

18
l=13
Y
l
(2D)

+
,
(3)
where X
i
, Y
j
, . . . , Y
l
are independently and identically dis-
tributed exponential random variables.
We can get the probability that the received SIR is greater
than or equal to a target SIR . This probability denotes the
one that a node successfully transmits a packet to the next node
under the interference from other simultaneously transmitting
nodes:
Pr[
i
(P) ] =
1
2
e
1
2
(2u+v
2
)
erfc
_
u + v
2

2v
_
(4)
In the above, u and v are given by u = u

_
R
D
_

= u

_
1
n
_

and v = v

_
R
D
_

= v

_
1
n
_

, where u

and v

are functions
of . Details for deriving (4) are contained in Appendix.
In [2], the authors derived the expected number of BEB
time slots taken for a packet to be captured successfully by
the next receiver node, for a given collision probability p
c
and
the minimum contention window size W
0
:
N(p
c
, W
0
) =
1
2
_
1
1 p
c
+
W
0
1 2p
c
_
1, (5)
where p
c
<
1
2
from the stability condition of [2].
In (5), substituting p
c
= 1 Pr[
i
(P) ] and assuming
W
0
is given, we can calculate the mean time until a packet
arrives at the destination from the source, as a function of
and n:
(, n) = n
_
1
2
_
1
1 p
c
+
W
0
1 2p
c
_
1
_
t
slot
, (6)
where t
slot
is the duration for a BEB time slot. In the
above, the rst term n = D/R can be explained as follows:
Assume that the simultaneous transmission occurs at every
other node with n-hop distance away. Then 1/n denotes the
average link activity factor. The average throughput of a link
is proportional to the link activity factor. Thus transmission
time is proportional to the inverse of the link activity factor.
Assume that the data rate between two communicating
nodes is dependent on the target SIR . The amount of data
contained in a packet is bits, which is a function of .
For example, with the Shannons formula, we assume that
() = W log
2
(1 + ), where W denotes the bandwidth.
From throughput-maximization point of view, increasing has
both positive- and negative effects on the average throughput
of a link. A high increases p
c
= 1 Pr[
i
(P) ],
but increases (). As for the reuse hop n, a higher value
of n diminishes the link activity factor, while decreasing p
c
.
In summary, we have the following throughput-maximization
problem with respect to and n:
maximize
, n
()
(, n)
(7)
s.t. p
c
<
1
2
(8)
The value of
()
(,n)
denotes the effective data rate that
is dened as the data amount of a packet divided by the
expected transmission time of the packet between source and
destination
3
. The problem (7)-(8) is a nonlinear optimization
problem. The objective function (7) is neither convex nor
concave, where Karush-Kuhn-Tucker (KKT) condition cannot
be applied. Therefore, we made partial optimization on n for
a given and get a closed formula for the optimal value for
n:
n

= C(, W
0
)()
1

, (9)
where C(, W
0
) is a function of and W
0
, as given in
Appendix. Especially, in case of path loss exponent =4 and
initial window size W
0
=4, the optimal n

is given as follows:
n

= 2.83()
1
4
(10)
See Appendix for more details on (9) and (10).
Putting n

to (4) enables us to express p

c
in (5) as a function
of . Thus the optimization problem (7)-(8) is reduced to
choosing the optimal target SIR. Even after representing
(7)-(8) with respect to , it seems to be hopeless to get
an algebraic solution for the induced optimization problem.
Figure 2 depicts the effective data rate
()
(,n

)
as a function
of target SIR.
In the gure, as the path loss exponent increases, the optimal
target SIR at which the effective data rate is maximized
3
()
(,n)
is actually the Jensen lower bound for the average data rate.
HWANG and KIM: A CROSS-LAYER OPTIMIZATION OF IEEE 802.11 MAC FOR WIRELESS MULTIHOP NETWORKS 533
0 5 10 15 20
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Logscaled target SIR (Log
2
(1+))

)
/

,
n

)
=2
=3
=4
=5
=6
Fig. 2. The effective data rate as a function of a log-scaled target SIR.
We assume that t
slot
=1 (sec), bandwidth W=1 (Hertz), minimum contention
window size W
0
= 4 and the unit of effective data rates is bits/sec. The
dotted circles correspond to the optimal points, where n

=20, 10, 8, 5 and 4

for =2, 3, 4, 5 and 6.
gets higher and the maximum effective data rate itself also
increases. High attenuation coefcient makes a good lter
which eliminates the interference on the multihop transmis-
sion. Under the assumption that the available power budget is
not enough to transmit data directly from source to destination,
at severe path loss environments like the urban, a shorter
carrier sensing range makes good performance. However, if
the path loss is loose like a line-of-sight space, the maximal
throughput is obtained by more long sensing ranges.
IV. CONCLUDING REMARKS
In this Letter, we analyzed the end-to-end throughput of
the IEEE 802.11 (CSMA/CA) based multihop network. Our
approach was to jointly optimize the carrier-sensing range for
simultaneous transmission and the target data rate on each
wireless link. We derived a closed form (9), by which one can
determine the optimal performance of the wireless multihop
network. Our results imply that the multihop transmission with
CSMA/CA gets more benets of multihopping, as the system
becomes noise-limited (high ) than for the interference-
limited cases (low ). As the network becomes denser, ap-
plication of the grid-like topology gets more reasonable and
the geometrical distribution of interferers in the general type
network gets similar to the one in this model. Therefore, even
if our results are derived from a linear network, we believe that
these results are applicable to more general types of networks.
APPENDIX
A. Derivation of (4)
Rewriting Equation (3) gives:
X
i

6
j=1
(
R
D
)

Y
j
+

12
k=7
(
R

3D
)

Y
k
+

18
l=13
(
R
2D
)

Y
l
+
=
X
G
Each interference term of
_
R
D
_

Y ( = 1,

3, 2,

7, )
is a random variable following the weighted exponential
distribution, of which mean and variance are
_
R
D
_

and
_
R
D
_
2
, respectively. For a sufciently large number of
interferers, the denominator follows the Gaussian distri-
bution such that f
G
(g) =
1
v

2
exp{
1
2
(
gu
v
)
2
}, where
u = 6
_
R
D
_

{1 +
1

3
+
1
2

+
1

7
+ } and v =
_
6
_
R
D
_
2
{1 +
1
3

+
1
4

+
1
7

+ }. For = 2, 3, 4, 5
and 6, u and v converge to certain numbers. For example,
when = 4, u 7
_
R
D
_
4
and v 2.5
_
R
D
_
4
. Thus we can
have (4) as follows:
Pr[
X
G
]
=
_

0
_ x

0
1
v

2
exp{
1
2
(
g u
v
)
2
}e
x
dgdx
=
1
2
e
1
2
(2u+v
2
)
erfc
_
u + v
2

2v
_
Further, we have p
c
= 1 Pr[
i
(P) ] = 1
1
2
e
1
2
(2u+v
2
)
erfc
_
u+v
2

2v
_
.
B. Derivation of (9) and (10)
Consider, for example, that is 4. We can approximate the
value of erfc(
u+v
2

2v
) by 2 over the focused values of u, v
and .
4
Thus we can rewrite p
c
= 1 e
1
2
(2u+v
2
)
, which
is a function of n = D/R. Putting p
c
into (6), we get the
optimal value of n

that makes the rst order derivative of

the convex function (6) zero. In case of W
0
= 4, it is given
by:
n

= 2.83()
1
4
(11)
As the same manner, we can get n

= C(, W
0
)()
1

, where
the values of C(, W
0
) are 11.59, 3.6, 2.03 and 1.79 for =
2, 3, 5 and 6, respectively (W
0
= 4).
REFERENCES
[1] B. Crow, I. Widjaja, L. Kim, and P. Sakai, IEEE 802.11 wireless local
area networks, IEEE Commun. Mag., vol. 35, pp. 116-126, Sept. 1997.
[2] B.-J. Kwak, N.-O. Song, and L. E. Miller, Performance analysis of
exponential backoff, IEEE/ACM Trans. Networking, vol. 13, pp. 343-
355, Apr. 2005.
[3] S. Xu and T. Saadawi, Does the IEEE 802.11 MAC protocol work well
in multihop wireless ad hoc networks? IEEE Commun. Mag., vol. 39,
pp. 130-137, June 2001.
[4] R. J antti, J. Mo, and S.-L. Kim, On multihop capacity gain and media
access control in a wireless network, submitted for publication, 2006.
[5] J. Zhu, X. Guo, L. Yang, and W. Conner, Leveraging spatial reuse in
802.11 mesh networks with enhanced physical carrier sensing, in Proc.
IEEE ICC04, pp. 4004-4011.
[6] E. S. Sousa and J. A. Silvester, Optimum transmission ranges in a
direct-sequence spread-spectrum multihop packet radio network, IEEE
J. Sel. Areas Commun., vol. 8, pp. 762-771, June 1990.
[7] M. Zorzi and S. Pupolin, Optimum transmission ranges in multihop
packet radio networks in the presence of fading, IEEE Trans. Commun.,
vol. 43, pp. 2201-2205, July 1995.
[8] J. Zander and S.-L Kim, Radio Resource Management for Wireless
Networks. Norwood MA: Artech House, 2001.
4
erfc(
u+v
2

2v
) =
2

u+v
2

2v
e
t
2
dt. Note that
D
R
=

3K in
Figure 1. Under 3 K 33, the value of erfc(
u+v
2

2v
) varies from 1.9944
to 1.9949 (=1). The higher and K make the function erfc() converge faster
to 2.