IEICE TRANS. COMMUN., VOL.E93–B, NO.9 SEPTEMBER 2010

2326

PAPER

Cross-Layer Scheme to Control Contention Window for Per-Flowin Asymmetric Multi-Hop Networks
Pham Thanh GIANG†a) , Student Member and Kenji NAKAGAWA†b) , Member

SUMMARY
The IEEE 802.11 MAC standard for wireless ad hoc networks adopts Binary Exponential Back-oﬀ (BEB) mechanism to resolve
bandwidth contention between stations. BEB mechanism controls the
bandwidth allocation for each station by choosing a back-oﬀ value from one
to CW according to the uniform random distribution, where CW is the contention window size. However, in asymmetric multi-hop networks, somestations are disadvantaged in opportunity of access to the shared channel
and may suﬀer severe throughput degradation when the traﬃc load is large.
Then, the network performance is degraded in terms of throughput and fairness. In this paper, we propose a new cross-layer scheme aiming to solve
the per-flow unfairness problem and achieve good throughput performancein IEEE 802.11 multi-hop ad hoc networks. Our cross-layer scheme collects useful information from the physical, MAC and link layers of own station. This information is used to determine the optimal Contention Window(CW) size for per-station fairness. We also use this information to adjust
CW size for each flow in the station in order to achieve per-flow fairness.
Performance of our cross-layer scheme is examined on various asymmetricmulti-hop network topologies by using Network Simulator (NS-2).
key words: cross-layer, per-flow/per-station fairness, bandwidth utilization, multi-hop wireless, IEEE 802.11, back-oﬀ algorithm, asymmetric
topology

1.

Introduction

Multi-hop wireless networks have become increasingly popular. They provide a fast and easy way to establish a new
network in areas where the infrastructure cannot be established because it is expensive or inconvenient. However, inasymmetric multi-hop networks, the network performancein terms of throughput and fairness is not necessarily satisfactory. Here, asymmetric means that the stations havediﬀerent conditions in channel access or diﬀerent number offlows or diﬀerent hop distances to destination. To solve thisproblem, we need to consider both MAC and link layer contentions. Due to the MAC layer contention, the bandwidth
allocation for each station cannot ensure per-station fairness[1], [2]. Each station transmits both direct flow, which is
generated by the station, and forwarding flows, which are
generated by the neighboring stations. Thus, there is a contention between the direct flow and forwarding flows at the
buﬀer space of the link layer, and then forwarding flows often lose in competition against the direct flow [3], [4].
The Distributed Coordination Function (DCF) [5] is a
Manuscript received March 29, 2010.
Manuscript revised May 31, 2010.
†
The authors are with the Department of Electrical Engineering, Nagaoka University of Technology, Nagaoka-shi, 940-2188
Japan.
a) E-mail: giang@kashiwa.nagaokaut.ac.jpb) E-mail: nakagawa@nagaokaut.ac.jp
DOI: 10.1587/transcom.E93.B.2326

fundamental MAC technique of the IEEE 802.11 [6], which
is designed to provide fair opportunity for every station
to transmit its frame in a distributed manner. The DCF
employs the Carrier Sense Multiple Access with Collision
Avoidance (CSMA/CA) protocol with access mechanism
based on Binary Exponential Back-oﬀ (BEB) mechanism[7]. BEB mechanism controls the channel access frequencyof each station by choosing randomly a back-oﬀ value from
one to CW according to the uniform random distribution,
where CW is the contention window size. So, it seems that
all the contending stations will have the same opportunity ofaccess to the shared channel, however, in asymmetry multihop topologies, BEB mechanism suﬀers from the unfairness
problem and low throughput, especially in case of large traffic oﬀered load [8]–[10].
BEB mechanism determines the Contention Window(CW) size for corresponding to the congestion condition.
BEB mechanism doubles the CW size upon each collision
until reaching CWmax and reset the CW size to CWmin uponeach successful transmission. However, BEB mechanism
does not consider other conditions about neighboring stations or higher layer, e.g., the number of flows in the channel or the number of users in the system. Thus, the CW
size after some congestion may not be the optimal value forfairness, especially in asymmetric multi-hop networks [11],[12]. Moreover, because the CW size is the same for allflows generated from one station, all flows will access channel with the same priorities. There is an unfairness problem
between flows in the buﬀer space, so the diﬀerent CW size
should be given for each flow to reduce the contention between them.
If the optimal CW size is determined and set for eachindividual station, BEB mechanism can give fair bandwidth
allocation between stations. Further, if a diﬀerent CW size isgiven to each flow, the contention between flows is controllable. However, determining the optimal CW size requires
global information of the network, which is nearly impossible to obtain in multi-hop ad hoc networks because eachstation works distributive. In our cross-layer scheme, we
control CW size in order to achieve good per-flow fairness
without global information. We collect information from thephysical, MAC and link layers, which is used to determine
a better CW size.
The purpose of this paper is to achieve per-flow fairness
by helping disadvantaged flows get more chance to accesschannel. See Appendix for our detail definition about perflow fairness in case there are both small and large oﬀered

c 2010 The Institute of Electronics, Information and Communication Engineers
Copyright GIANG and NAKAGAWA: CROSS-LAYER SCHEME TO CONTROL CONTENTION WINDOW

2327

load flows. We propose five modules, which work at thephysical, MAC and link layers. CS Flow Estimation module is put at the physical layer to sense whether some flows
are being transmitted in the carrier sensing range but out of
the transmission range of the station. TX Flow Estimation
module is put at the MAC layer to classify the flows which
are being transmitted in the transmission range of the station. Utilization Estimation module is put at the MAC layer
to measure the current link utilization. Queue Estimation
module is put at the link layer to evaluate the contention
between flows in the buﬀer space. The last CW Monitor
module is put at the MAC layer to decide a good CW size
for achieving fair bandwidth allocation between stations andalso between flows in the station based on the informationcollected from above four modules.
In general, there is trade-oﬀ between fairness andthroughput performance [13]. In our cross-layer scheme,
the per-flow fairness performance is much improved and
we also achieve good throughput performance. We use the
Network Simulator (NS-2) [14] to evaluate our cross-layer
scheme in many asymmetric multi-hop topologies.
The rest of the paper is organized as follows: Section 2
reviews related work. Section 3 describes our cross-layer
scheme. Section 4 evaluates our cross-layer scheme by comparing with original FIFO scheduling in IEEE 802.11 standard [6], and PCRQ scheduling [15]. Finally, Sect. 5 concludes the paper and suggest further research.
2.

Related Work

According to studies in the past several years [1], [10], theweaknesses of IEEE802.11 give poor fairness for flows in
multi-hop ad hoc networks. The fairness performance at the
MAC layer is considered in the protocols MACA [1] andits extension MACAW [16], in which the four-way handshake signals RTS/CTS/Data/ACK are used to reduce collisions caused by hidden terminals in the networks. However,the RTS/CTS scheme in DCF does not solve all unfairness
problems in case of asymmetric topology [8], [10]. Li etal. [10] investigated Extended Inter-Frame Spacing (EIFS)
problem, i.e., the fixed EIFS value leads to unfair bandwidth allocation for each station. They proposed flexible
EIFS values based on a measurement of the length of Sensing Range (SR) frame. However, the length of SR frame
cannot be always recognized because of the spatial reuseof the bandwidth. The paper [8] investigated other asymmetric topology, that is the three-pair problem. The analysis of the three-pair problem in [8] is based on Markov
chain and gives some accurate results. Because they studied
the impact of asymmetric multi-hop networks only by thethree-pair scenario, their methodology cannot be applied toarbitrary topology. Moreover, those studies mainly consider
the per-station unfairness problem and they do not consider
the per-flow unfairness problem, which is caused at the link
layer.
Some papers proposed scheduling methods to solve
the per-flow unfairness problem in multi-hop networks.

Jangeun et al. [3] pointed out the weak point of FIFO
scheduling in multi-hop networks. They proposed various
queuing schemes to achieve some level of per-flow fairness.
Shagdar et al. [4] proposed scheduling algorithms which use
Round Robin (RR) queue to solve the link layer contention,and modify the MAC layer by dequeuing all packets at thehead of RR queues with one time back-oﬀ algorithm to solve
the MAC layer contention. Those papers [3], [4] assume that
the MAC layer gives the ideal per-station fairness, however
such assumption cannot be satisfied in general. The paper[15] proved that the RR scheduling cannot help per-flow
fairness due to unfairness at the MAC layer. The Probabilistic Control on Round robin Queue (PCRQ) scheduling[15] improves fair bandwidth allocation at the MAC layer
and achieves good per-flow fairness. The PCRQ scheduling uses RR queues with three algorithms to control input/output packets and the turn of RR queues. Some delays
are given to the direct flow in order to give more chance ofchannel access to forwarding flows. As a result, the fairness of bandwidth allocation is improved and good per-flow
fairness is achieved.
Many other studies also tried to solve the unfairness
problem by modifying BEB mechanism. The CW size in
BEB mechanism is doubled when a station experiences apacket collision and the CW size is reset to CWmin when astation transmits a packet successfully. To prevent a large
oscillation of CW size, some studies tried to adjust BEB
mechanism as Multiplicative Increase and Linear Decrease(MILD) [16], Exponential Increase Exponential Decrease(EIED) [17] and Linear/Multiplicative Increase and Linear
Decrease (LMILD) [18]. Because BEB mechanisms in their
methods still work only based on collision information, theCW size is not necessarily the optimal value for fairness.
Fang et al. [19] reviewed the unfairness problem in BEB
mechanism. Each station estimates the channel utilizationof its own and that of neighboring stations then adjusts the
back-oﬀ algorithm to give each station some value of bandwidth, called the statistical fair access. The statistical fair
access must be predefined, but it is diﬃcult in general because the value depends on topologies. There are some otherstudies on the control of CW size to achieve per-flow fairness [20], [21], but almost all of them consider only singlehop networks. Unlike those studies, our solution tries toevaluate fair bandwidth allocation by examining the number flows which are being transmitted in the carrier sensing
range of the station, then CW size is adjusted to achieve fairbandwidth allocation even in case of asymmetric topologies.
Moreover, we determine a good CW size for each flow toachieve per-flow fairness.
3.

Proposed Cross-Layer Scheme

In multi-hop ad hoc networks, some flows are in diﬃculties
of accessing the channel due to both MAC and link layer
contentions. The CW size is related to the probability ofchannel access. We will propose a new cross-layer scheme
to collect useful information from the physical, MAC andIEICE TRANS. COMMUN., VOL.E93–B, NO.9 SEPTEMBER 2010

2328


nCS =

0,
1,

if there is no CS flow ,if there are one or more CS flows.

(1)

3.2 TX Flow Estimation Module
TX Flow Estimation module works on the MAC layer tocount the number of flows in the transmission range. We
call these flows as TX flows. A TX flow is identified by
MAC and IP addresses of both source and destination bydecoding the header of packets. We denote the number of
TX flows by nT X .
TX Flow Estimation module receives nCS from CS
Flow Estimation module then we have the total number offlows ntotal in the TX Flow Estimation module asntotal = nT X + nCS .
Fig. 1 The proposed five modules. (I) and (II) are Module Set I and II,
respectively.

link layers, and then adjust a good CW size based on this information. By using a flexible CW size in back-oﬀ state, wehelp disadvantaged flows get more chance to access channel.
Our cross-layer scheme in Fig. 1 consists of five modules. CS Flow Estimation module is put at the physical layer
to sense the existence of a flow in the carrier sensing range
but out of the transmission range. TX Flow Estimation module is put at the MAC layer to count the number of flows
in the transmission range. Utilization Estimation module isput at the MAC layer to measure the current link utilization.
Queue Estimation module is put at the link layer to evaluate
the contention between flows in the buﬀer space. The main
module of our cross-layer scheme is CW Monitor module
which is put at the MAC layer.
The five modules are categorized into two sets of modules, i.e., Module Set I and Module Set II as shown in Fig. 1.
Module Set I consists of CS Flow Estimation module, TX
Flow Estimation module, Utilization Estimation module and
CW Monitor module. Module Set II consists of Queue Estimation module and CW Monitor module. Module Set I
decides a good CW size for solving the MAC layer contention. While, Module Set II decides a good CW size forsolving the link layer contention.
3.1 CS Flow Estimation Module
CS Flow Estimation module works on the physical layer. It
senses by the physical power the existence of a flow whichis in the carrier sensing range but out of the transmission
range of the station. We call such a flow as CS flow. The
power of packets from a CS flow is larger than the carrier
sensing threshold and smaller than the reception threshold.
The station can sense the existence of CS flows but cannot
distinguish each flow. Hence, in this case, even if there aremany such flows, we consider all CS flows as one flow. We
define nCS by(2)

Among TX flows, the flows transmitted from the station are denoted as SEND flows. The SEND flows include
the direct flow which is generated by the station and forwarding flows which are generated by the neighboring stations. We define the number of SEND flows as nS END .
We define the fair share ratio of the bandwidth forthe station as the ratio of the number of transmitting flows
nS END to the total number of flows ntotal ;nS END.
(3)
Fair S hare Ratio =ntotalThe total number of flows ntotal in (2) includes both TX
flows and CS flows because the wireless channel is used not
only by the TX flows but also by some of CS flows. However, a CS flow may not share the channel with the station
if the sender station of that CS flow is of the carrier sensing
range. Moreover, we cannot distinguish the CS flows by the
local information of the station. By these two reasons, weconsider all the CS flows as one flow even if there are two
or more flows.
The end of CS and TX flows are estimated as follows.
We set timeout period. If no packet from CS flow is detectedduring the timeout period, we decide the end of CS flow.
Similarly for TX flows.
3.3 Utilization Estimation Module
Utilization Estimation module evaluates the real link utilization of the station. The link utilization is measured by examining the Active T ime of the station in a predefined estimation period EP. The Active T ime of the station is defined as the time used for transmitting packets of its SEND
flows. Algorithm 1 shows how to estimate the Active T ime
by sensing packets.
The Real S hare Ratio is defined as the ratio of the
Active T ime to the estimation period EP as;
Real S hare Ratio =Active time
.
EP

(4)

3.4 Queue Estimation Module
The contention at the link layer causes the problem that theGIANG and NAKAGAWA: CROSS-LAYER SCHEME TO CONTROL CONTENTION WINDOW

2329

Algorithm 1 Active time estimation
Initialization:
Active T ime = 0
T Active = 0
Beginfor each interval time EP do
Active T ime = 0.8 ∗ Active T ime + 0.2 ∗ T Active
T Active = 0
for each packet p do
if p → destID == localID thenif p → T ype == CT S then
T Active = T Active + T RT S + TCT S
else if p → T ype == ACK then
T Active = T Active + T DAT A + T ACK
end ifend ifend forend forEnd

direct flow occupies the buﬀer completely when the oﬀeredload is large. Only by using RR queues, these unfairness
problem cannot be solved [15]. In our cross-layer scheme,
RR queue is used at the link layer and Queue Estimation
module examines the queue length of each flow. The load of
a flow is measured by comparing its queue length to the average queue length of all flows. Then the packet at the headof the queue for f low i is marked at the following probability;⎧
qleni − ave⎪⎪⎪, if qleni > ave,⎨(5)
Pi marked = ⎪(n − 1)ave⎪⎪⎩ 0,
if qleni ≤ ave,where qleni is the queue length of f low i, ave is the averageof the queue lengths for all flows in the station, and n =nS END is the number of SEND flows of the station.
3.5 CW Monitor Module
In the original IEEE 802.11, the CW size is based only on
the congestion condition, so it is not a good value for fairbandwidth allocation. CW size is related to the channel access probability of the station. By reducing the CW size inthe back-oﬀ state, the channel access probability of the station increases, and then the station can take more bandwidth
allocation. Conversely, by increasing the CW size in the
back-oﬀ state, the neighboring stations have more chance inaccessing channel. Based on the CW value in the back-oﬀ
algorithm of the IEEE 802.11 and the network condition, we
will determine a better CW size in the back-oﬀ state in orderto achieve per-flow fairness.
We will show in the next section the functions of Module Set I and II.
3.6 Module Set I
Module Set I consists of CS Flow Estimation module,
TX Flow Estimation module, Utilization Estimation module and CW Monitor module. Module Set I adjusts CW

size based on the relation between Fair Share Ratio (3)and Real Share Ratio (4) in order to achieve perstation fair bandwidth allocation. Fair Share Ratio andReal Share Ratio are estimated by TX Flow Estimation
module and Utilization Estimation module, respectively.
Both values are sent to CW Monitor module by using crosslayer signal.
When there is a packet ready to be sent, CW Monitor
module adjusts CW size as follows;
Real S hare Ratio
CW.
(6)Fair S hare Ratio
In (6), the Fair S hare Ratio value is used as a thresholdof channel access priority. If the station recognizes that its
Real S hare Ratio is smaller than its Fair S hare Ratio, itwill use a smaller CW size in the back-oﬀ state. Then,the station can increase its chance to access channel andits bandwidth allocation. On the other hand, if the station recognizes that its Real S hare Ratio is lager than its
Fair S hare Ratio, it will use a larger CW size in the backoﬀ state. Thus, the station decreases its chance to access channel, so other disadvantaged stations will get morechance to access the channel. In case some stations have
only small oﬀered load flows, they will access channel easily, and the remaining bandwidth is shared by other stations.
Therefore, Module Set I use the channel bandwidth more effectively and ensure fair bandwidth allocation between stations.
CW  =

3.7 Module Set II
Module Set II consists of Queue Estimation module and CWMonitor module. Module Set II adjusts CW size for eachflow to achieve per-flow fairness. Queue Estimation modulemarks a packet at the probability in (5). When the marked
packet is ready to be sent, CW Monitor module will assign
larger back-oﬀ time for this packet as follows;


CW =



κ ∗ CW  , for a marked packet,
for a non-marked packet,
CW  ,(7)

where κ > 1 is a constant, which we call a delay weight constant and CW  is the value defined in (6). Note that the valueof CW is determined by the original IEEE 802.11 back-oﬀ
mechanism and we do not touch the mechanism itself. CW 
and CW  are only used when a packet comes to back-oﬀ
state.
Thus, Module Set II can help disadvantaged flows havemore chance to access channel based on its queue length.
Moreover, when a large back-oﬀ time is set to packetsof large oﬀered load flows, those packets will be delayed
longer before sending than by the conventional method.
Then, during this delay time, packets from the neighboring stations have more chance to reach the station. Thus,
the fairness between the direct flow and forwarding flows is
also improved.
Let us consider the throughput performance of ourIEICE TRANS. COMMUN., VOL.E93–B, NO.9 SEPTEMBER 20102330

method. Module Set II gives longer delay to marked packets than the conventional method, but the extra delay time isvery small. Moreover, the flows of neighboring stations canincrease their throughput. Therefore, the diﬀerence of total
throughput is negligible.
4.

Performance Evaluation

We now evaluate the performance of our cross-layer schemeby comparing with the original FIFO scheduling in IEEE
801.11 standard [6], PCRQ scheduling [15] on various
asymmetric topologies of multi-hop wireless ad hoc networks. We also compare with the method where only Module Set I is used, because we can expect that the per-flow
fairness performance may be improved based on the improvement of per-station fairness by Module Set I. We use
Network Simulator (NS-2) [14] for evaluation. The simulation parameters are shown in Table 1. In PCRQ scheduling,
we use the same parameters as in [15], i.e., the input weight
constant α = 2.0, the hold weight constant β = 0.3, theoutput weight constant γ = 0.3 and delay time δ = 1 [ms].
In our cross-layer scheme, we set the delay weight constantκ = 2, timeout = 2 [s] and EP = 2 [s].
The fairness and throughput performance metrics areevaluated.

See Fig. 2. (0, 0) means the x-y coordinate of station R, andso on. This topology is also known as large-EIFS problem[10], which is described in Fig. 3. In this scenario, stations
S1 and S2 are in one transmission range, and stations S1 and
R are in other transmission range. Stations S2 and R are outof the transmission range but in the carrier sensing range.
At the last state of the four-way handshaking process fromsender S1 to receiver R, R sends an ACK frame in reply to adata frame from S1, then S2 detects the ACK frame, but cannot decode it. Thus, S2 must wait an EIFS before accessing
the channel, while S1 waits a DIFS, which is much smaller
than the EIFS. Li et al. [10] has proved that bandwidth allocation for S1 is four times greater than S2 because of thelarge-EIFS problem.
We examine the network performance in this scenario
by letting the stations S1 and S2 generate traﬃc at the sameoﬀered load G to R. The performance metrics Fairness Index
and Total Throughput are evaluated versus oﬀered load G.
In Figs. 4 and 5, “Module Set I” means the result by using only Module Set I and “Proposed Method” means both
Module Set I and II. Fairness Indices are shown in Fig. 4.
When the oﬀered load G is small, all scheduling methods get
Fairness Index 1. When the oﬀered load G becomes large,
in FIFO scheduling, the direct flow gradually occupies completely the buﬀer space, then Fairness Index becomes very

• Fairness Index: We use Fairness Index, which is defined by R. Jain [22] as follows;( ni=1 xi )2,(8)
Fairness Index =
n · ni=1 x2i
where n is the number of flows, xi is the end-to-end
throughput of f low i. The value of Fairness Index
ranges from 1/n to 1. In the best case, i.e., the throughput of all flows are equal, Fairness Index achieves 1. In
the worst case, the network is totally unfair, i.e., one
flow gets all the capacity while other flows get nothing,then Fairness Index is 1/n. In this paper, Fairness Index is evaluated based on the goodput at the destination
station.
• Total Throughput: We define the Total Throughput as
the sum of throughputs of all flows in the simulation.

Fig. 2

Fig. 3

Scenario-1: The large-EIFS problem.

Unfairness in bandwidth due to large-EIFS problem.

4.1 Scenario-1: The Large-EIFS Topology
Scenario-1 includes a chain of three stations with two flows.
Table 1 Parameters in the simulation.
Channel data rate
2 [Mbps]
Antenna type
Omni direction
Radio Propagation
Two-ray ground
Transmission range
250 [m]Carrier Sensing range
550 [m]
MAC protocol
IEEE 802.11b (RTS/CTS is enable)
Contention Window
CWmin = 32, CWmax = 1024
Connection type
UDP/CBRBuﬀer size
100 [packet]
Packet size
1 [KB]
Simulation time
300 [s]Fig. 4

Fairness index in scenario-1.

GIANG and NAKAGAWA: CROSS-LAYER SCHEME TO CONTROL CONTENTION WINDOW

2331

Fig. 6
Fig. 5

Scenario-2: Three-pair problem.

Total throughput in scenario-1.

bad. In PCRQ scheduling [15], input and output packets
to RR queues are controlled, then the throughput of eachflow becomes fairer and also the bandwidth allocation at the
MAC layer is improved. Thus, PCRQ scheduling achieves
good Fairness Index. In Proposed Method, the fairness performance in both MAC and link layers are improved, so weachieve very good Fairness Index. When only Module Set I
is applied, Fairness Index is much improved compared to
FIFO scheduling.
Total Throughput of all flows are shown in Fig. 5.
When the oﬀered load is small, Total Throughput of all
methods are similar. When the oﬀered load becomes large,
in PCRQ scheduling, bandwidth utilization is less eﬃcientthan the others because PCRQ scheduling gives some delays to packets of advantaged flows. In Module Set I, S2
increases its chance to access channel by reducing backoﬀ time, and then the network utilization is also improved.
Module Set I achieves the best Total Throughput in all
methods. Because Module Set II gives large back-oﬀ time
to some packets of advantaged flows, Proposed Method
achieves Total Throughput slightly smaller than Module
Set I and FIFO scheduling.

Fig. 7

Fairness index in scenario-2.

Fig. 8

Total throughput in scenario-2.

4.2 Scenario-2: The Three-Pair Topology
Figure 6 shows the topology of Scenario-2. The problem
in this scenario is also known as three-pair problem which
was first investigated in [8]. In this scenario, stations S1-S2and S2-S3 are out of the transmission range but in the carrier sensing range. Stations S1 and S3 are out of the carrier
sensing range, hence the two external pairs S1-R1 and S3R3 are completely independent, i.e., they can send packets
simultaneously without interference with each other. Thus,
two external pairs contend bandwidth only with the central
pair S2-R2, while the central pair contends with both external pairs. In this topology, the central pair cannot access themedium in the saturated state in the original IEEE 802.11[8].
We examine the unfairness problem in this topology
by letting the stations S1, S2 and S3 generate traﬃc at thesame oﬀered load G to R1, R2 and R3, respectively. The

performance metrics are evaluated versus oﬀered load G.
Fairness Indices are shown in Fig. 7. When the oﬀeredload becomes large, FIFO scheduling and PCRQ scheduling cannot help the central pair access the medium, because
PCRQ scheduling only works at the link layer, so it does
not have information of flows out of the transmission range.
Therefore, it cannot improve the MAC layer fairness. In
Proposed Method, the central pair finds out that its bandwidth is less than the fair bandwidth allocation. Then Proposed Method tries to improve its chance to access channel
by reducing the back-oﬀ time of station S2. Thus, Proposed
Method can achieve a good MAC layer fairness and per-flow
fairness. Module Set I shows exactly the same results as
Proposed Method, because there is no link layer contention

IEICE TRANS. COMMUN., VOL.E93–B, NO.9 SEPTEMBER 2010

2332

Fig. 9Scenario-3: a five-station chain with four flows.

Fig. 10

Fig. 11

Fig. 12

Scenario-4: Grid scenario.

Fig. 13

Fairness index in scenario-4.

Fig. 14

Total throughput in scenario-4.

Fairness index in scenario-3.

Total throughput in scenario-3.

in this topology.
Total Throughput of all flows are shown in Fig. 8.
When the oﬀered load G becomes large, Module Set I and
Proposed Method achieve smaller Total Throughput than theother methods. This phenomenon is explained as follows.
In FIFO scheduling and PCRQ scheduling, the central paircannot access the channel bandwidth and two external pairs
can use the whole channel bandwidth. Thus, Total Throughput can be twice of the channel bandwidth. While in Module
Set I and Proposed Method, the MAC layer fairness is ensured, so the central pair can achieve a half of the channel
bandwidth, then the two external pairs have only a half ofthe channel bandwidth. Thus, Total Throughput is one anda half of channel bandwidth.
4.3 Scenario-3: The Long Station Chain Topology
Scenario-3 includes a chain of five stations with four flows

as shown in Fig. 9. The stations S1, S2, S3, and S4 generate traﬃc at the same oﬀered load G to R. This scenario
faces with much harder MAC and link layer contentions
than Scenario-1.
The performance results are shown in Figs. 10 and 11.
The results show that both PCRQ scheduling and Proposed
Method get better fairness performance than the others.
Proposed Method also has advantage in throughput performance because of the good operation of Module Set I.

GIANG and NAKAGAWA: CROSS-LAYER SCHEME TO CONTROL CONTENTION WINDOW

2333

4.4 Scenario-4: The Grid Topology
Scenario-4 is a grid topology with high station density andlarge traﬃc density as in Fig. 12. In this scenario, thecolumns are separated by a distance greater than the transmission range but smaller than the carrier sensing range.
The stations in a column generate traﬃc at the same oﬀeredload G to the receiver in the same column. This topology
faces both large-EIFS and three-pair unfairness problems.
Fairness Index between six flows are shown in Fig. 13.
When the oﬀered load G becomes large, each method gives
diﬀerent Fairness Index due to contention between the direct flow and forwarding flows at the link layer, and due toboth large-EIFS and three-pair problems at the MAC layer.
Fairness Index of FIFO scheduling is the worst because of
the unfairness problems in both MAC and link layers. By
the same reason explained in Scenario-2, PCRQ scheduling cannot solve the unfairness in three-pair problem. Thus,
Fairness Index of PCRQ scheduling is not good. Fairness
Index of Module Set I is better than PCRQ scheduling, but
Module Set I still cannot solve the contention at the link
layer. Proposed Method achieves the best per-flow fairness
among all methods because we improved the fairness at both
MAC and link layers.
Total Throughput performance are shown in Fig. 14.
At the large oﬀered load, Total Throughput of Proposed
Method is smaller than the other methods by the same reason with Scenario-2.

Fig. 15

Fairness index in scenario-5.

Fig. 16

Total throughput in scenario-5.

4.5 Scenario-5: The Random Topology
Scenario-5 is a random topology. We make topologies with50 stations at random position in 1000 [m] × 1000 [m] area.
Among those 50 stations, n stations are chosen randomly
and these n stations generate UDP traﬃc to one destination
station. Total oﬀered load of source stations is set equal
to the channel data rate 2 [Mbps]. The average of Fairness
Index and total end-to-end throughput are used as the metrics to compare the throughput and fairness performances,respectively. These terms of the network performance are
examined versus the number of flows. Each data point is
the average over 20 simulations. The simulation results areshown in Figs. 15 and 16.
The simulation results also prove that Proposed
Method achieves good fairness performance as in Fig. 15.
Our throughput performance is slightly reduced by thetrade-oﬀ with fairness performance as described in Fig. 16.
4.6 Scenario-6: The Dynamic Number of Flows and the
Dynamic Oﬀered Loads
Scenario-6 is used to examine bandwidth utilization of Proposed Method in case that the number of flows and oﬀeredload change by time. We use the same topology as Scenario1. The simulation time is 450 [s]. The oﬀered loads offlow 1 and 2 change by time as (0, G, G), (50, G, G/2),

Fig. 17

Throughput in scenario-6.

(100, G, G/10), (150, G, 0), (200, 0, 0), (250, 0, G), (300,
G/10, G), (350, G/2, G), (400, G, G), where (t, G1, G2) denotes the changing time, oﬀered load of flow 1 and oﬀeredload of flow 2, respectively. We set G equal to 0.65 [Mbps].
Proposed Method is compared only with the original IEEE
802.11. The simulation results are shown in Fig. 17.
When the total oﬀered load is small, e.g., from 100 [s]to 200 [s], every flow can get the throughput equal to its offered load in both Proposed Method and the original IEEE
802.11, regardless of the diﬀerence of each flow’s oﬀeredload. When the total oﬀered load is greater than the channel
capacity, e.g., from 50 [s] to 100 [s] and 300 [s] to 400 [s], in
Proposed Method, the throughput of the small oﬀered load

IEICE TRANS. COMMUN., VOL.E93–B, NO.9 SEPTEMBER 2010

2334

flow is equal to its oﬀered load and the large oﬀered load
flow gets the remaining bandwidth. Total Throughput in
Proposed Method is always better than in the original IEEE
802.11 even if the oﬀered loads and the number of flowschange by time.
5.

Conclusion and Future Work

We proposed a new cross-layer scheme to achieve good fairness of throughputs between flows. Our cross-layer scheme
consists of two module sets. Module Set I controls the MAC
layer contention. We used information from the physicaland MAC layers and modify the CW size in back-oﬀ state toachieve the fair bandwidth allocation for each station. Module Set II controls the link layer contention. We controlled
RR queue in order to help each flow use bandwidth fairly.
The cross-layer signal is sent from the link layer to the MAC
layer, and then the MAC layer gives a long back-oﬀ time topackets from large oﬀered load flows.
By NS-2 simulation, we compared our cross-layer
scheme with FIFO scheduling, PCRQ scheduling and themethod using only Module Set I. The results showed that
our cross-layer scheme achieved good performance in largeEIFS problem, three-pair problem scenarios and also complex asymmetric topologies as long-station chain, grid, random and dynamic topologies. In these topologies, FIFO
scheduling cannot solve the link layer contention. PCRQ
scheduling can achieve good per-flow fairness, however, itworks only at the link layer so it cannot solve per-flow fairness between stations. Module Set I tries to achieve fairbandwidth allocation between stations, the per-flow fairness
performance also is improved. Proposed Method uses crosslayer information to improve both MAC and link layer fairness. Therefore, we had good results in per-flow fairness
even in asymmetric topologies.
This paper is our first challenge to apply the proposed
method for per-flow fairness in the multi-hop ad hoc networks, and we evaluated only for UDP traﬃc. A good performance for TCP traﬃc also is obtained by some simulations in our laboratory. This is because TCP data packets
can be considered to be similar with UDP packets, and thefeedback ACK packets can be treated as a small oﬀered load
flow in our cross-layer scheme. They have more priority
to access channel and more chance for successful transmission. However, we found that the fairness performance issueof TCP is a tough issue, because, for example, TCP cannot distinguish packet losses caused by network congestion
from those caused by wireless link errors. In future work,a cross-layer method to exchange information between TCP
layer and MAC layer will be investigated to improve network performance in the mixture of UDP and TCP traﬃcs.
References[1] P. Karn, “Maca: A new channel access method for packet radio,”
ARRL/CRRL Amateur Radio 9th computer Networking Conference, pp.134–140, 1990.
[2] C. Chaudet, D. Dhoutaut, and I.G. Lassous, “Performance issues

with ieee 802.11 in ad hoc networking,” IEEE Commun. Mag.,
vol.43, no.7, pp.110–116, July 2005.
[3] J. Jangeun and M. Sichitiu, “Fairness and qos in multihop wirelessnetworks,” IEEE Vehicular Technology Conference, vol.5, pp.2936–
2940, 2003.
[4] O. Shagdar, K. Nakagawa, and B. Zhang, “Achieving per-flow fairness in wireless ad hoc networks,” Electron. Commun. Jpn. 1, Commun., vol.89, no.8, pp.37–49, 2006.
[5] G. Bianchi, “Performance analysis of the ieee 802.11 distributed
coordination function,” IEEE J. Sel. Areas Commun., vol.18, no.3,
pp.535–547, 2000.
[6] I.S. Department, “IEEE 802.11 wireless lan medium access control(MAC) and physical layer (PHY) specifications,” ANSI/IEEE Standard 802.11, 1999.
[7] K. Xu, M. Gerla, and S. Bae, “How eﬀective is the ieee 802.11 rts/cts
handshake in ad hoc networks,” IEEE Global Telecommunications
Conference: 2002, GLOBECOM’02, pp.72–76, 2002.
[8] C. Chaudet, I.G. Lassous, E. Thierry, and B. Gaujal, “Study of the
impact of asymmetry and carrier sense mechanism in ieee 802.11
multi-hops networks through a basic case,” PE-WASUN’04: Proc.
1st ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, pp.1–7, ACM Press,
New York, NY, USA, 2004.
[9] T. Razafindralambo and F. Valois, “Performance evaluation of backoﬀ algorithms in 802.11 ad-hoc networks,” PE-WASUN’06: Proc.
3rd ACM international workshop on Performance evaluation of
wireless ad hoc, sensor and ubiquitous networks, pp.82–89, ACM
Press, New York, NY, USA, 2006.
[10] Z. Li, S. Nandi, and A.K. Gupta, “Ecs: An enhanced carrier sensing mechanism for wireless ad-hoc networks,” Comput. Commun.,vol.28, no.17, pp.1970–1984, 2005.
[11] C.E. Koksal, H. Kassab, and H. Balakrishnan, “An analysis of shortterm fairness in wireless media access protocols,” ACM Sigmetrics
2000, Santa Clara, CA, June 2000.
[12] G. Berger-Sabbatel, A. Duda, O. Gaudouin, M. Heusse, and
F. Rousseau, “Fairness and its impact on delay in 802.11 networks,”
Proc. IEEE Global Telecommunications Conference (GLOBECOM’04), pp.2967–2973, Dallas, USA, 2004.
[13] H. Kwak and S. Yoshida, “Tradeoﬀ between fairness and throughput
in multi-hop wireless lan,” IEICE Trans. Fundamentals, vol.E-A87,
no.7, pp.1733–1741, July 2004.
[14] The Network Simulator: ns-2. http://www.isi.edu/nsnam/ns/[15] P.T. Giang and K. Nakagawa, “Achieving fairness over 802.11 multihop wireless ad hoc networks,” IEICE Trans. Commun., vol.E92-B,
no.8, pp.2628–2637, Aug. 2009.
[16] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A
media access protocol for wireless lan’s,” Proc. Conf. Communications Architectures, Protocols and Applications, pp.212–225, ACM,
1994.
[17] N. oak Song, B. jae Kwak, J. Song, and L.E. Miller, “Enhancementof ieee 802.11 distributed coordination function with exponential
increase exponential decrease backoﬀ algorithm,” IEEE VehicularTechnology Conference, vol.4, pp.2775–2778, 2003.
[18] J. Deng, P.K. Varshney, and Z. Haas, “A new backoﬀ algorithm
for the ieee 802.11 distributed coordination function,” Communication Networks and Distributed Systems Modeling and Simulation(CNDS’04), pp.215–225, 2004.
[19] Z. Fang, B. Bensaou, and Y. Wang, “Performance evaluation of afair backoﬀ algorithm for ieee 802.11 dfwmac,” MobiHoc’02: Proc.
3rd ACM International Symposium on Mobile Ad Hoc Networking& Computing, pp.48–57, ACM, New York, NY, USA, 2002.
[20] M. Malli, Q. Ni, T. Turletti, and C. Barakat, “Adaptive fair channel
allocation for qos enhancement in ieee 802.11 wireless lans,” IEEE
Int. Conf. Communications, 2004, pp.3470– 3475, 2004.
[21] H.S. Choi and J.T. Lim, “Per-flow fair media access control in wireless ad-hoc networks,” IEICE Trans. Commun., vol.E91-B, no.12,
pp.4046–4049, Dec. 2008.

GIANG and NAKAGAWA: CROSS-LAYER SCHEME TO CONTROL CONTENTION WINDOW

2335[22] R. Jain, D.M. Chiu, and W. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared conputer
systems,” Technical Report TR-301, DEC Research Report, 1984.

Appendix:Definition of Per-Flow Fairness

Here, we consider the definition of per-flow fairness as follows. Let n be the number of flows sharing the channel
bandwidth B. The oﬀered load of f low i is denoted by Gi
and the resulting throughput is denoted by T hi , i = 1, 2, ..., n.
We assume G1 ≤ G2 ≤ ... ≤ Gn . We define per-flow fairness
by⎧⎪for i = 1, ..., m,
Gi ,
⎪
⎪
⎪
m
⎪

⎪
⎪
⎨ B−
Thj
T hi = ⎪(A· 1)
⎪
⎪
⎪
j=1
⎪
⎪
⎪
⎩
, for i = m + 1, ..., n,
n−m
where
m is the index in 0,m ..., n which satisfies Gm ≤B− mj=1 T h j
B− j=1 T h j
and Gm+1 >. We call f low i, i =n−mn−m
1, 2, ..., m, “small” oﬀered load flow and f low i, i = m +1, m + 2, ..., n, “large” oﬀered load flow. In case that allflows are large oﬀered load flows (m = 0), the ideal perflow fairness is achieved when every flow gets the same
throughput. In case there are some small oﬀered load flows(m ≥ 1), the ideal per-flow fairness is such that the throughput of every small oﬀered load flow is equal to its oﬀeredload, and the remaining bandwidth is shared equally bylarge oﬀered load flows. For example, if there are four
flows with oﬀered loads 0.2 [Mbps], 0.5 [Mbps], 0.7 [Mbps],
0.8 [Mbps], and the channel bandwidth is 2 [Mbps]. Then,flows with oﬀered load 0.2 [Mbps] and 0.5 [Mps] are small
oﬀered load flows while flows with oﬀered load 0.7 [Mbps]
and 0.8 [Mbps] are large oﬀered load flows. The ideal perflow fairness is such that the throughputs are 0.2 [Mpbs],
0.5 [Mbps], 0.65 [Mbps], 0.65 [Mbps], respectively.
We can consider the case that the oﬀered loads are notconstant and change by time. The definition of per-flow fairness is based on the average oﬀered loads for a specific interval time.

Pham Thanh Giang
received the B.E. degree from the Hanoi University of Technology,
Vietnam, in 2002, and M.E. degree from the Nagaoka University of Technology, Japan, in 2007.
He is currently a Ph.D. student at Dept. of Electrical Engineering, Nagaoka University of Technology, Japan. His interests are security, mobile
ad hoc networks, the Internet architecture in mobile environments and Internet traﬃc measurement.

Kenji Nakagawa
received the B.S., M.S.
and D.S. degrees from Tokyo Institute of Technology, Tokyo, Japan, in 1980, 1982 and 1986,
respectively. In 1985, he joined NTT (Nippon
Telegraph and Telephone Corp.). Since 1992, hehas been an associate professor of Dept. of Electrical Engineering, Nagaoka University of Technology. He is an associate editor of the IEICE
Transactions on Communications. His researchinterests include queueing theory, performance
evaluation of networks, and geometric theory ofstatics. Dr. Nakagawa is a member of the IEEE, SITA, and MathematicalSociety of Japan.