IEICE TRANS. COMMUN., VOL.E92–B, NO.8 AUGUST 2009

2628

PAPER

Achieving Fairness over 802.11 Multihop Wireless Ad Hoc
Networks
Pham Thanh GIANG†a) , Student Member and Kenji NAKAGAWA†b) , Member

SUMMARY
IEEE 802.11 MAC protocol for medium access control inwireless Local Area Networks (LANs) is the de facto standard for wirelessad hoc networks. However, it does not perform well in terms of fairness, delay and throughput specially, in multihop networks. The problem is due toboth the MAC and link layer contentions. Many research papers have been
published in these fields. Among them, a modification of IEEE 802.11
MAC protocol was proposed to achieve per-node fairness, but modifications to the original MAC layer requires a change of hardware, therefore, it
is diﬃcult to implement. Moreover, it fails to solve the per-flow unfairness
problem. In this paper, we propose a new scheduling method, Probabilistic Control on Round robin Queue (PCRQ) scheduling, aiming to achieve
per-flow fairness in multihop ad hoc networks. PCRQ scheduling in thelink layer is proposed without modifying IEEE 802.11 MAC protocol. Our
proposed method achieves good performance results in both UDP and TCP
traﬃc.
key words: fairness, multihop wireless, PCRQ scheduling, scheduling algorithm

1.

Introduction

In a multihop ad hoc network, stations communicate witheach other using multihop wireless links and there is no stationary infrastructure such as a base station. Each station in
the network also acts as a router, forwarding data packets
from other stations. For example, a group of people withlaptops with a wireless Network Interface Card (NIC) with
802.11-equipped may gather together for voice or videoconferences at their company building. In order to transfer
voice, video data, share documents to far colleagues, they
could cooperate with each other by switching their NICs toad hoc mode. The ad hoc network also can integrate withstationary infrastructure networks through a gateway to use
the services in the global Internet or to be reached by anotherterminal in the global Internet. However, IEEE 802.11 MAC
protocol [1], the de facto standard for wireless ad hoc networks was not suitably for multihop network. In asymmetry topologies, as each station’s oﬀered load approaches thesaturated value, the performance of IEEE 802.11 in terms ofdelay, fairness degrades dramatically [2], [3]. In multihop
network, stations cooperate to forward packets from otherstations. A station not only transmits the direct flow, whichis generated by the station, but also forwarding flows, which
Manuscript received October 22, 2008.
Manuscript revised April 12, 2009.
†
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.E92.B.2628

are generated by the neighboring stations. Moreover, thestation also shares the channel capacity with them. The effect of the contentions in the MAC and link layers aﬀects theperformance of the network. In the MAC layer, each station
contends for using bandwidth. Due to the MAC layer contention, the allocated bandwidth for sending and forwarding
packets cannot ensure per-flow fairness [2], [3]. In the link
layer, there is contention between the direct flow and forwarding flows for the buﬀer space. Obviously, the directflow gets more advantage than forwarding flows [4]–[6].
In our research, we consider both UDP and TCP traﬃc.
In UDP traﬃc, packets may arrive out of order, appear duplicated, or go missing without notice. UDP does not adjust
the oﬀered load, even when some packets are dropped by
the MAC layer contention. Thus the direct flow gradually
but completely starves forwarding flows from neighboring
stations. The network becomes totally unfair. TCP reacts
better to the congestion than UDP. In the congestion, TCP
performs a congestion control algorithm to decrease the traffic rate. However, there are still many packets in competingin bandwidth and TCP flows suﬀer from fairness problem.
In this paper, we propose Probabilistic Control on
Round robin Queue (PCRQ) scheduling, in which we use
an individual queue for each of the direct and forwardingflows, each queue is served as Round Robin (RR) fashion.
In the link layer, we propose three algorithms to control
the number of input packets to a queue, the turn of reading queues in RR fashion, and the number of output packets
from a queue. By controlling input packets, heavy oﬀeredloads can be reduced. Controlling the turn of reading queues
will help flows with small oﬀered load get more chance
to send packets. Moreover, by controlling output packets,
number of sending packets from heavy oﬀered load flows is
reduced, and then more bandwidth will be used for receiving forwarding flows. Thus, PCRQ scheduling can improve
the MAC layer fairness and achieve per-flow fairness without modifying the 802.11 MAC layer protocols. In addition to per-flow fairness, PCRQ scheduling archives positive
impact in terms of the eﬀective buﬀer resource and delay
time. We use the Network Simulator (NS) [7] to evaluate
our proposed method in some unfairness situations relying
on asymmetry topologies as chain stations, complex stations
and diﬀerent traﬃc types. Fairness between multihop flows
on the way to a destination and other network performances
are examined. The rest of the paper is organized as follows:
Section 2 compares with related works. Section 3 showsa serious unfairness problem in multihop network explain-c 2009 The Institute of Electronics, Information and Communication Engineers
Copyright GIANG and NAKAGAWA: ACHIEVING FAIRNESS OVER 802.11 MULTIHOP WIRELESS AD HOC NETWORKS

2629

ing why FIFO scheduling and also RR scheduling fail toachieve good fairness. Section 4 describes PCRQ scheduling. Section 5 evaluates our proposed method by comparing with FIFO, RR schedulings and Shagdar’s method [5]in both UDP and TCP traﬃc. The parameters of our proposed method are discussed in Sect. 6. Finally, Section 7
concludes the paper.
2.

Related Work

The fairness performance at the MAC layer has been an
active research field in the past several years. The protocols MACA [8] and its extension MACAW [9] use the fourway RTS/CTS/Data/ACK handshake signals to reduce collisions caused by hidden terminals in the network. The protocol MACAW has been standardized in the IEEE 802.11[1] as Distributed Coordination Function (DCF). However,the RTS/CTS scheme in DCF does not solve all unfairness
bandwidth in case of asymmetric links. Several schemes
for improving the fairness of MAC protocols have been proposed in the literature [10]–[12]. Moreover, Li et al. [13] investigated Extended Inter-Frame Spacing (EIFS) problem,i.e., the fixed EIFS value leads to unfair bandwidth allocation for each stations. They proposed flexible EIFS values based on a measurement of the length of Sensing Range(SR) frame.
Improved fairness of the MAC protocol will certainly
improve per-flow fairness as well. However, a major problem of the MAC layer fairness solutions is diﬃcult to implement. As the IEEE 802.11 standard is the de facto standards
for ad hoc network and has been widely accepted by the industry. In addition, all stations in an ad hoc network require
having a consistent MAC protocol. Thus, any modificationof the MAC protocol results in update at all stations.
Jangeun et al. [4] pointed out the weak point of FIFO
scheduling in multihop networks and proposed various
queuing schemes. Each scheme has oﬀered diﬀerent degreeof fairness. However, their research is based on the ideal
MAC layer fairness assumption, which cannot be satisfied.
Therefore, their schemes do not give good performance inthe real networks. Shagdar et al. [5] and Izumikawa et al.
[6] also focused on the contention of direct flow and forwarding flows, and proposed scheduling algorithms by using RR mechanism. The DCF mechanism are modified in[5] to achieve the bandwidth utilization by sending all thepackets at the head of RR queues continuously without delay by back-oﬀ algorithm. However, in their solutions, thesame problem as in [4] is due to the unsatisfactory assumption that the MAC layer gives fair bandwidth allocation. We
will show in next section that is impossible to achieve goodfairness by using only RR scheduling.
The performance of TCP over wireless networks withIEEE 802.11 medium access also has been studied extensively. The eﬀect of TCP congestion window limits on performance of multihop networks has been evaluated in [14]–[16]. They conclude that TCP window size actually grows
much larger than the optimum. There are too many packets

on the path, which are competing for the same medium. It
results in performance degradation and unfairness. Besides
the schemes described above, there are also some other TCP
enhancement schemes based on modification of the IEEE
802.11 MAC protocol [17], [18]. By modifying the IEEE
802.11, these schemes are shown to improve per-flow fairness of TCP traﬃc to some degree. Unlike those works
on TCP over multihop wireless networks, our solution will
not require significant modification to TCP or IEEE 802.11
MAC protocol. It works on the link layer, generally improves per-flow fairness in both TCP and UDP traﬃc.
3.

Serious Unfairness Problem

We will examine the MAC and link layer contentions how
they aﬀect the per-flow fairness. There are some kinds of
unfairness problem topologies. In this section, one basic
multihop wireless network topology will be illustrated as an
example. Consider the topology in Fig. 1, there are threestations. Stations M1 and M2 are in one transmission range,in which a packet can be transmitted and received successfully. Station M1 and gateway GW are also in another transmission range. Station M2 and GW are out of transmission
range but in carrier-sensing range, in which a transmission
can be detected. The carrier-sensing range is larger than thetransmission range, and may be more than two times of thetransmission range [19]. It is noted that the sizes for thetransmission and carrier-sensing ranges vary according to
the power levels. Stations M1 and M2 are assumed to generate the same oﬀered load G to GW. Let B be the maximum
medium bandwidth, and B1 , B2 be the allocated bandwidth
for stations M1 and M2 in the saturation state, respectively.
We have B = B1 + B2 .
3.1 MAC Layer Contention
The MAC layer contention for a station is defined as thecontention in the MAC layer between the allocated bandwidth for the station B1 , which is considered as the sending
bandwidth of the station, to the allocated bandwidth for its
neighboring stations B2 , which is considered as the receiving bandwidth of the station. We call B1 the sending bandwidth and B2 the receiving bandwidth. In this topology, theserious unfairness problem in the MAC layer is due to the
EIFS problem [13], which is described in Fig. 2.
At the last state of four-way handshaking process fromstation M1 to GW, GW sends an ACK frame in reply to a

Fig. 1

A basic multihop wireless network model.

IEICE TRANS. COMMUN., VOL.E92–B, NO.8 AUGUST 2009

2630

Fig. 2

Unfairness in bandwidth due to EIFS problem.

data frame from station M1, station M2 detects the ACK
frame, but cannot decode it. Therefore, station M2 must
wait an EIFS before accessing the channel, while station M1
waits a DIFS, which is much shorter than the EIFS. Li et al.
[13] has proved that the EIFS problem leads B1 : B2 ≈ 4 : 1
in this topology. In addition, the physical layer capture
mechanism [20] also aﬀects the proportion of the sending
bandwidth B1 to the receiving bandwidth B2 . When stations
M1 and M2 send packets at the same time, the packet fromstation M2 will be ignored by station M1 because its poweris lower than the other. Because the throughputs of forwarding flows are limited by B2 , the fairness between forwardingflows and the direct flow is not achieved.
Next, we will explain this problem in detail.
3.2 Link Layer Contention
The link layer contention is defined as the contention between forwarding flows and the direct flow in the outgoing
buﬀer space. We will examine the link layer contention in
the FIFO and RR scheduling methods from the topology illustrated in Fig. 1. Let the oﬀered load G vary from zero to
maximum medium bandwidth B, the individual throughput
T h( f low 1) and T h( f low 2) from stations M1 and M2, respectively, are calculated in both FIFO and RR schedulingmethods.
3.2.1 Link Layer Contention in FIFO SchedulingFirst, if the bandwidth B is suﬃciently large compared to thesum of all flow’s oﬀered loads, each flow can get its required
throughput.
T h( f low 1) = T h( f low 2) = G, if G <

B
3

(1)

Second, if the bandwidth B is not enough for all flows,
because B1 is much greater than B2 , the flow 1 can get required throughput, and the remaining bandwidth is used forthe flow 2. Throughputs of the flow 1 and flow 2 are calculated as follows.
⎧⎪⎪B⎨ T h( f low 1) = G
B−G(2)
if ≤ G < B1 − B2⎪⎪
⎩ T h( f low 2) =3
2
Third, the network is in the saturation state. In FIFO
scheduling, a common queue is used for all flows. We assume that buﬀer size is infinite. The ratio of the buﬀer allocation Q f low 1 for the flow 1 to Q f low 2 for the flow 2 at station
M1 is Q f low 1 : Q f low 2 = G : B2 . Hence, the throughputs ofFig. 3Throughputs in FIFO scheduling.

Table 1 Parameters in the simulation.
Channel data rate
2[Mbps]Antenna type
Omni direction
Radio Propagation
Two-ray ground
Distance between stations
200[m]
Transmission range
250[m]
Carrier Sensing range
550[m]
MAC protocol
IEEE 802.11b (RTS/CTS is enable)
Connection type
UDP/CBRBuﬀer size
100000[packet]
Packet size
1[KB]
Simulation time
100[s]

the flow 1 and flow 2 at station M1 are calculated as follows.
⎧
G
⎪
⎪
⎪
T h( f low 1) = B1⎪⎪⎪
G + B2⎨
if G ≥ B1 − B2
(3)
⎪
⎪
⎪
B2
⎪
⎪
⎪
⎩ T h( f low 2) = B1
G + B2We show in Fig. 3 the throughputs of the flow 1 andflow 2 of FIFO scheduling in simulation by NS-2 [7] andour analysis. The simulation parameters are shown in Table 1. In the simulation, the channel data rate is set with
2[Mbps], leading to the bandwidths B, B1 and B2 are about
1.074[Mbps], 0.939[Mbps] and 0.135[Mbps], respectively
due to the overhead in IEEE 802.11 [21]. When the oﬀeredload increases, the throughput of the flow 1 comes to B1 ,while the throughput of the flow 2 comes to zero. Thus, thenetwork is totally unfair.
3.2.2 Link Layer Contention in RR Scheduling
In RR scheduling, we have the same results as in the firstand second cases as in (1) and (2) described in Sect. 3.2.1.
In the third case, the flow 1 and flow 2 share the bandwidth,
but the throughput of the forwarding flow 2 T h( f low 2) islimited by the receiving bandwidth B2 , and the flow 1 canget all remaining bandwidth. The throughputs for the flow 1
and flow 2 are calculated as follows.
T h( f low 1) = B1 − B2
if G ≥ B1 − B2(4)
T h( f low 2) = B2
Those RR scheduling’s throughputs in simulation andour analysis are shown in Fig. 4. The result shows that RR

GIANG and NAKAGAWA: ACHIEVING FAIRNESS OVER 802.11 MULTIHOP WIRELESS AD HOC NETWORKS

2631

Fig. 5
Fig. 4scheduling fails to achieve the fairness between the directflow and forwarding flow. When the oﬀered load increases,
the throughput of the flow 1 comes to B1 − B2 , while thethroughput of the flow 2 comes to B2 that is much smaller
than the other. Figures 3 and 4 also show that our analysis isaccurate: the simulation results coincide with the analyticalresults, in both FIFO and RR schedulings.
Thus, the good fairness in multihop ad hoc networks
cannot be achieved by the only use of RR scheduling.
4.

Probabilistic control on round robin queue.

Throughputs in RR scheduling.

Probabilistic Control on Round Robin Queue
Scheduling

The reason why RR mechanism cannot give a satisfactorythroughput for forwarding flows is the limited receiving
bandwidth at the MAC layer. Only a small number of forwarding packets can reach the relay station, the forwardingflow’s queues often become empty and thus RR mechanism
misses turns for forwarding flows. It is clearly of great advance to the direct flow. Our idea is to manage RR queues
to ensure fair buﬀer and bandwidth allocation.
We now propose Probabilistic Control on Round robin
Queue (PCRQ) scheduling. In PCRQ scheduling, RR
queues are used with three algorithms: Algorithm 1 controls the number of input packets to queues, Algorithm 2controls the turn of reading queues, and Algorithm 3 controls the number of output packets from queues. Figure 5
shows our proposed method.
4.1 Algorithm 1 (Controlling the Number of Input Packets
to Queues)
In multihop network, when the oﬀered load is large, thedirect flow’s queue tends to occupy completely the buﬀer
space. Algorithm 1 decides to receive or to drop an input
packet so as not to put too much packets to a queue. An
arriving packet from flow i is put into its queue at the following probability;⎧⎪1,
if qleni ≤ ave
⎪
⎪
⎨
−
ave
qlen
(5)
Pi input = ⎪i⎪⎪⎩ 1 − α (n − 1)ave , if qleni > ave
where α is an input weight constant, ave is the average of thequeue lengths for all flows, n is the number of flows, qleni
is the queue length of flow i. Packets from a heavy oﬀeredload flow may be dropped with probability in range 0 to α.
In case the queue of flow i is full while other queues are
empty, income packet will be dropped with probability α.
In case the queue length of flow i smaller or equal averagequeue length, all packets will be enqueued. Algorithm 1
reduces input packets of a flow with heavy oﬀered load andmakes the queue length of each flow fairer and smaller.
4.2 Algorithm 2 (Controlling the Turn of Reading Queues)
Generally, the receiving bandwidth is small, thus the forwarding flow’s queues often become empty. In this case,the direct flow will get more turns from RR mechanism, andgood per-flow fairness is not ensured. Algorithm 2 keeps theempty queue’s turn for an interval time δ and waits for a new
packet. The queue’s turn of flow i is hold at the following
probability;⎧ qmax⎪⎪, if qleni = 0⎨ β(6)
Pi turn = ⎪n · ave⎪⎩ 0,
if qleni > 0
where β is a hold weight constant, qmax is the maximum
queue length of all queue. The turn of the empty queue is
kept with probability in range β/n to β. In case a queue isfull while other queue are empty, the turn of the empty queue
is kept with probability β. In case the queue lengths of all
flow are almost equal, this probability is about β/n. Because
a delay time δ can be used for receiving packets, the receiving bandwidth at the MAC layer will be improved. Thus,
Algorithm 2 does not only helps RR mechanism working
more eﬀectively but also makes the receiving and sending
bandwidths fairer.
4.3 Algorithm 3 (Controlling the Number of Output Packets from Queues)
The unfairness between the receiving and sending bandwidths is the main reason of per-flow unfairness in RR
scheduling as in Sect. 3. Algorithm 3 prevents heavy offered load flows from sending many packets to the MAC
layer, and more bandwidth is left for receiving forwardingflows. Thus, throughputs of forwarding flows are improved.

IEICE TRANS. COMMUN., VOL.E92–B, NO.8 AUGUST 2009

2632

A packet at the head of the queue for flow i is sent from thelink layer to the MAC layer at the following probability;⎧⎪1,
if qleni ≤ ave⎪⎪⎨
qleni − ave
Pi output = ⎪(7)⎪⎪⎩ 1 − γ (n − 1)ave , if qleni > ave
where γ is an output weight constant. Packets from a heavy
oﬀered load flow may be delay to send with probability inrange 0 to γ. In case the queue is full while other flow isempty, packets may stop sending with probability γ. In casethe queue length smaller or equal average queue length, allpackets will be dequeued. If Algorithm 3 decides postpone
sending a packet, the packet is delayed for an interval time δ.
Thus Algorithm 3 not only makes the receiving and sending
bandwidths fair, but also the throughput for each flow fair.
5.

Performance Evaluation

We now evaluate the performance of PCRQ schedulingby comparing with the original FIFO scheduling in IEEE
801.11 standard, RR scheduling and Shagdar’s method [5].
We use Network Simulator (NS-2) [7] for evaluation. The
simulation parameters are shown in Table 2. In PCRQ
scheduling, we set the input weight constant α = 2.0, thehold weight constant β = 0.3, the output weight constantγ = 0.3 and delay time δ = 1[ms]. Four types of scenarios are used to evaluate the performance of PCRQ scheduling. Scenario-1 is a long chain of stations. The complicated MAC layer contention is examined in the Scenario-2.
Scenario-3 is used to examine the contention between UDP
and TCP flows. The bandwidth utilization is examined incase each station generates diﬀerent oﬀered load in the last
scenario.
In our simulation, the following four important performance metrics are evaluated.

nothing, fairness index is 1/n. In this paper, fairness
index is evaluated based on goodput at the destination
station.
• Average queue length: The average of total queue
lengths of all RR queues at the station during simulation.
• Average delay time: The average end-to-end delay time
during simulation of all packets, which successfully
reached the destination.
• Total throughput: The average of total goodput of allflows during simulation.
5.1 Scenario-1
Scenario-1 includes a chain of five stations with four flows.
The coordinates of stations are shown in Fig. 6. The stations
M1, M2, M3 and M4 generate UDP or TCP traﬃc to gateway GW. To examine UDP traﬃc, we consider all stations
generate at the same oﬀered load G. The performance metrics is evaluated versus the oﬀered load G.
Fairness indices in UDP traﬃc are shown in Fig. 7.
When the oﬀered load is small, all scheduling methods
get perfect fairness index. When the oﬀered load becomeslarger, because a common queue is used in FIFO scheduling, the direct flow gradually occupies completely the buﬀer
space and the fairness index becomes very bad. In RR
scheduling and Shagdar’s method, even diﬀerent queue isused for each flow, but the receiving packets from the forwarding flow are limited because of the MAC layer contention, resulting bad fairness indices. While, in PCRQ
scheduling, the receiving and sending bandwidths at the
MAC layer become fairer, and also the per-flow through-• Fairness index: We use the 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 throughput offlow i. The result ranges from 1/n to 1. In the best
case, throughput of all flows are equal, the fairness index achieves 1. In the worst case, the network is totally
unfair, one flow gets all capacity while other flows get
Table 2 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)
Connection type
UDP/CBR and TCP/FTP
Buﬀer size
100[packet]
Packet size
1[KB]
Simulation time
100[s]

Fig. 6

Fig. 7

Scenario-1: one five-station chain with four flows.

Fairness indices for Scenario-1 in UDP traﬃc.

GIANG and NAKAGAWA: ACHIEVING FAIRNESS OVER 802.11 MULTIHOP WIRELESS AD HOC NETWORKS

2633
Table 3The simulation results of TCP traﬃc in Scenario-1.
FIFO
RR
Shagdar
PCRQ
Fairness index
0.464
0.553
0.487
0.771
Queue length [pkt]a24.011
7.775
6.040
1.707
Delay time [s]b
0.255
0.079
0.087
0.029
Throughput [Mbps]
1.069
1.054
1.089
1.035

a
The average total queue lengths of the direct and forwardingflows at station M1 in TCP traﬃcb
The average end to end delay time of flow 1 in TCP traﬃcFig. 8traﬃc.

Average queue lengths in station M1 for Scenario-1 in UDP

Fig. 9Average delay time of flow 1 for Scenario-1 in UDP traﬃc.

shown in Fig. 9. The average delay time is directly proportional to the average queue lengths. The average delay timein PCRQ scheduling is also smallest among all schedulingmethods.
The total throughputs of all flows in UDP traﬃc are
shown in Fig. 10. When the oﬀered load is small, throughputs in all methods are similar. When the oﬀered load becomes greater, PCRQ scheduling uses bandwidth slightly
less eﬃciently than the others. The reason can be explained
as follows. Algorithms 2 and 3 give delay to sending packets
to give chance for receiving packets. However, if forwarding
packets may not come, the next packet is taken longer timeto transfer. Thus, our total throughput is slightly smaller
than the other methods.
Table 3 shows the results in TCP traﬃc. Because TCP
can adapt the window size to the network condition andreduce oﬀered load of the direct flow. Thus, fairness in
TCP traﬃc is better than in UDP traﬃc in FIFO scheduling. However, due to the MAC layer contention, only small
number of forwarding packets can reach relay stations, fairness is not improved much in RR scheduling and Shagdar’s
method. In PCRQ scheduling, Algorithms 2 and 3 improve
the receiving bandwidth. Therefore, our fairness index isbetter than the other methods. As the same reason above,other performance metrics as queue length, delay time in
PCRQ scheduling also much better than the other methods.
Total throughout are similar in all scheduling methods.
5.2 Scenario-2

Fig. 10

Total throughput for Scenario-1 in UDP traﬃc.

put becomes fairer by Algorithms 2 and 3, the input oﬀeredload of each flow becomes fairer by Algorithm 1. Therefore,
we get good fairness index.
The average total queue lengths of the direct and forwarding flows at station M1 in UDP traﬃc are shown in
Fig. 8. When the oﬀered load is small, the total oﬀered load
is smaller than the maximum medium bandwidth, and queue
lengths are small in all the scheduling methods. When theoﬀered load is larger, the common queue in FIFO scheduling and the direct flow’s queue in RR scheduling and Shagdar’s method will be full of packets. In PCRQ scheduling,
input packets are controlled by Algorithm 1 that describes
our queue length as the smallest among all the schedulingmethods.
The average delay time of flow 1 in UDP traﬃc is

Scenario-2 includes two chains of stations, one consists ofthree stations and the other consists of two stations. The
coordinates of stations are shown in Fig. 11. The number offlows is four. The stations M1, M2, M3, and M4 generate
UDP or TCP traﬃc to gateway GW. In this scenario, theMAC layer contention at station M1 is more complicatedthan in the previous scenario because there are more stationsin the same transmission range with station M1.
The performance results in UDP traﬃc are shown in
Figs. 12, 13, 14 and 15. The results show that PCRQ
scheduling still gives better performance metrics in term
fairness, queue length and delay time than the others. Moreover, the throughput performance is similar to the othermethods.
The performance results in TCP traﬃc are shown in Table 4. PCRQ scheduling still archives good results in termsof fairness, queue length and delay time. Our total through-IEICE TRANS. COMMUN., VOL.E92–B, NO.8 AUGUST 2009

2634

Fig. 14

Average delay time of flow 1 for Scenario-2 in UDP traﬃc.

Fig. 11 Scenario-2: one three-station chain and one four-station chain
with four flows.

Fig. 15
Fig. 12

Fairness indices for Scenario-2 in UDP traﬃc.

Total throughput for Scenario-2 in UDP traﬃc.

one station M2 in Scenario-1. Thus, station M1 achieves alittle smaller bandwidth than in Scenario-1, and the MAC
layer unfairness at station M1 is slightly reduced comparedto Scenario-1. It makes fairness performance in Scenario-2
higher than in Scenario-1.
5.3 Scenario-3

Fig. 13
traﬃc.

Average queue lengths in station M1 for Scenario-2 in UDP

Table 4The simulation results of TCP traﬃc in Scenario-2.
FIFO
RR
Shagdar
PCRQ
Fairness index
0.653
0.659
0.708
0.746
Queue length [pkt]35.72736.181
6.026
2.273
Delay time [s]
0.393
0.394
0.099
0.036
Throughput [Mbps]
1.069
1.070
1.098
1.060

put is slightly smaller as the trade-oﬀ between fairness andthroughput.
In this scenario, the fairness result is better than in
Scenario-1 for all scheduling methods. The reason can be
explained as follows. Two stations M2 and M3 compete forbandwidth with station M1 in Scenario-2, while there is only

Scenario-3 is created to examine the contention between
UDP and TCP flows. The coordinates of stations are shownin Fig. 16. These are one UDP flow from station M2 andtwo TCP flows from stations M3 and M4 respectively. The
UDP flow’s oﬀered load is set equal to channel data rate.
The performance results are shown in Table 5. PCRQ
scheduling achieves better fairness index than other methods also in case of mixed UDP and TCP. PCRQ schedulingalso achieves good result in terms of queue length. The fairness index of this scenario as in Table 5 is better than previous scenarios in Tables 3 and 4. This reason is that stations
M2, M3 and M4 are fairer in the MAC layer contention in
Scenario-3, while the MAC layer contentions are harder because of asymmetric stations’ location in Scenarios-1 and
2.
5.4 Scenario-4
Scenario-4 is used to examine bandwidth utilization in caseeach station generates diﬀerent oﬀered load. We use thebasic multihop network model as in Fig. 1. Stations M1 andM2 generate UDP traﬃc with two cases:

GIANG and NAKAGAWA: ACHIEVING FAIRNESS OVER 802.11 MULTIHOP WIRELESS AD HOC NETWORKS

2635

Fig. 16

Scenario-3: Five-station with one UDP flow and two TCP flows.

Fig. 19

Total throughput for Scenario-4 in Case-2.

Fig. 20

Fairness indices for Scenario-4 in Case-2.

Table 5The simulation results in Scenario-3.
FIFO
RR
Shagdar
PCRQ
Fairness index
0.909
0.921
0.948
0.968
Queue length [pkt]37.34251.1503.329
2.55
Throughput [Mbps]
1.206
1.201
1.162
1.194

Fig. 17

Total throughput for Scenario-4 in Case-1.

Fig. 18

Fairness indices for Scenario-4 in Case-1.

• Case-1: The oﬀered load of flow1 is G, while the offered load of flow2 is G/2.
• Case-2: The oﬀered load of flow1 is G/2, while theoﬀered load of flow2 is G.
The simulation results in total throughput are shown in
Figs. 17 and 19. Consider Case-1, where station M1 gener-

ates twice as much oﬀered load as station M2. When G issmall, each station can achieve maximum throughput in allscheduling methods. Even each station has diﬀerent oﬀeredload, the utilization in PCRQ scheduling is not aﬀected because our algorithms operate based on queue length. WhenG becomes larger, our throughput is slightly smaller thanthe other method because our algorithms try to reduce thethroughput of flow 1 to give chance for flow 2.
Consider Case-2, where station M1 generates half as
much oﬀered load as station M2. In this case, PCRQ
scheduling achieves better throughput than other method
when G becomes larger. Our algorithms also reduce thethroughput of flow 1. However, the throughput of flow 2much improved due to the oﬀered load of flow 2 is higher
than in Case-1. Thus, in total throughput, PCRQ schedulingis better than the others.
Fairness indices in Cases-1 and 2 are shown in Figs. 18
and 20, respectively. When G is small, fairness indices of all
methods are the same in both Cases-1 and 2. When G becomes larger, fairness indices of PCRQ scheduling are improved in both Cases-1 and 2 because the light throughput
flow has a better chance for sending packets than the heavy
throughput flow by the operation of our Algorithms.
While in the other methods, the direct flow becomes
more advantageous for sending packets than the forwarding flow when G becomes larger. In Case-1, the oﬀeredload of flow 1 is two times greater than flow 2, of course,
flow 1 will fast starve the bandwidth, thus their fairness in-

IEICE TRANS. COMMUN., VOL.E92–B, NO.8 AUGUST 2009

2636

dices decrease (see Fig. 18). In Case-2, even the oﬀeredload of flow 2 is two times greater than flow 1, the throughput of flow 1 still gradually increases while the throughputof flow 2 decreases. When the oﬀered load G is around
0.8[Mbps], the throughput of flow 1 is equal to flow 2 andthe fairness indices is equal to 1 (see Fig. 20). However,their fairness indices will fast decrease because the throughput of flow 1 continues increasing.
In case of a heavy oﬀered load, PCRQ scheduling gives
a delay for a packet from heavy flows. Meanwhile, PCRQ
scheduling greatly improves fairness performance even in
the case of asymmetric topologies, and ensures a sustainable throughput for long-hop flows. Due to the absenceof global scheduling in the IEEE 802.11 [1], there exists
a trade-oﬀ between the fairness and the throughput performances. PCRQ scheduling improves the fairness index by
up to 70% compared to the other methods, while the difference of throughputs between PCRQ scheduling and theother methods is smaller than 6% which is acceptable. In addition, PCRQ scheduling also achieves better performancein delay time and buﬀer utilization than the other methods.
6.

Discussion on Parameter Values

Our Algorithms’s target is to improve network performancein IEEE 802.11 [1] multihop wireless network. Algorithm 1controls input packets and queue length of each flow become fairer due to dropping some packets from a flow withthe heavy input oﬀered load. Eq. (5) showed Algorithm 1’s
operation. The larger value of the input weight constant
α is, the more packets are dropped from the heavy oﬀeredload flow. Algorithm 1 tries to reduce queue length of theheavy oﬀered load flow to make it reduce to the averagequeue length and Algorithm 1 stops to drop packets whenthe queue length is smaller than the average queue length.
Thus, α can greater than 1. In our simulations, we chose αequal to 2.
Algorithm 2 only makes a delay for waiting a new
packet to an empty flow. Thus, the hold weight constantβ also can be greater than 1. However the greater value of βis, the longer delay time is. It is not good for bandwidth utilization. To avoid processing finished flows, we need to determine when a flow finishes by using a timeout. If a flow isempty over a timeout, its queue is removed from RR queues.
In our simulations, we chose β equal to 0.3.
Algorithm 3 makes a delay for sending a packet basedon queue length. It leads to increase queue length, with theresult that Poutput decreases. Thus the output weight constant γ must be smaller than 1, otherwise Poutput becomeszero and no packet can be sent. Algorithms 1 and 3 are pairalgorithms that aﬀect to queue length. Algorithm 3 may delay for sending packets and the queue length may increase.
In opposite, Algorithm 1 reduces the queue length by dropping packets. These algorithms help queue length get stable.
The same reason with Algorithm 2, the large value of γ may
degrade bandwidth utilization. In our simulations, we chose
γ equal to 0.3.

7.

Conclusion

In this paper, we proposed a new scheduling method to improve the fairness in multihop wireless ad hoc networks andcompared it to conventional methods. FIFO scheduling has
only one queue; therefore, it cannot solve the unfairness
problem by the link layer contention. RR scheduling andShagdar’s method also work ineﬀectively because the allocated bandwidths at the MAC layer are not suitable for forwarding and direct flows in the link layer. We proposed the
PCRQ scheduling in the link layer to solve these problems.
By controlling input/output packets to/from a queue andturns of reading queues in RR fashion, PCRQ schedulingcontrols the contention at the MAC layer indirectly. Our Algorithms improved per-flow fairness and helped RR mechanism work more eﬀectively. In addition to fairness, thequeue length in PCRQ scheduling was smaller; it results inless buﬀer resource than the other methods. Moreover, ourdelay time was also lower than the others. Therefore, it isuseful for services, which require real-time packet transmission. Since PCRQ scheduling works on the link layer, it iseasy to implement without changing hardware.
Acknowledgment
We would like to thank Ms. Oyunchimeg Shagdar of ATR
Adaptive Communications Research Laboratories for sharing her knowledge, her program, and assistance throughout our research. We also acknowledge Mr. Kazuhiro
Yamaguchi of Kobe Digital Labo. CO., Ltd. for his assistance in NS programming.
References[1] I.S. Department, “IEEE 802.11 wireless lan medium access control(mac) and physical layer (phy) specifications,” ANSI/IEEE Standard
802.11, 1999.
[2] 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, no.6, pp.130–137, 2001.
[3] J. He and H.K. Pung, “One/zero fairness problem of mac protocols
in multi-hop ad hoc networks and its solution,” Proc. International
Conference on Wireless Networks, pp.479–485, 2003.
[4] J. Jangeun and M. Sichitiu, “Fairness and qos in multihop wirelessnetworks,” IEEE Vehicular Technology Conference, vol.5, pp.2936–
2940, 2003.
[5] 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.
[6] H. Izumikawa, K. Sugiyama, and S. Matsumoto, “Scheduling algorithm for fairness improvement among subscribers in multihop wireless networks,” Electron. Commun. Jpn. 1, Commun., vol.90, no.4,
pp.11–22, 2007.
[7] The Network Simulator: ns-2. http://www.isi.edu/nsnam/ns/[8] P. Karn, “Maca: A new channel access method for packet radio,”
ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp.134–140, 1990.
[9] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “Macaw:
A media access protocol for wireless lan’s,” SIGCOMM’94: Proc.

GIANG and NAKAGAWA: ACHIEVING FAIRNESS OVER 802.11 MULTIHOP WIRELESS AD HOC NETWORKS

2637

Conference on Communications Architectures, Protocols and Applications, pp.212–225, ACM, New York, NY, USA, 1994.
[10] T. Nandagopal, T.E. Kim, X. Gao, and V. Bharghavan, “Achieving mac layer fairness in wireless packet networks,” MobiCom’00:
Proc. 6th Annual International Conference on Mobile Computing
and Networking, pp.87–98, ACM, New York, NY, USA, 2000.
[11] B. Bensaou, Y. Wang, and C.C. Ko, “Fair medium access in 802.11
based wireless ad-hoc networks,” MobiHoc’00: Proc. 1st ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp.99–106, IEEE Press, Piscataway, NJ, USA, 2000.
[12] L.B. Jiang and S.C. Liew, “Improving throughput and fairness by reducing exposed and hidden nodes in 802.11 networks,” IEEE Trans.
Mobile Computing, vol.7, no.1, pp.34–49, 2008.
[13] 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.
[14] K. Chen, Y. Xue, and K. Nahrstedt, “On setting tcp’s congestion
window limit in mobile ad hoc networks,” Communications, 2003.
ICC’03. IEEE International Conference on, pp.1080–1084, 2003.
[15] K. Xu, M. Gerla, L. Qi, and Y. Shu, “Enhancing tcp fairness inad hoc wireless networks using neighborhood red,” MobiCom’03:
Proc. 9th Annual International Conference on Mobile Computing
and Networking, pp.16–28, ACM, New York, NY, USA, 2003.
[16] Z. Fu, H. Luo, P. Zerfos, S. Lu, L. Zhang, and M. Gerla, “The impact of multihop wireless channel on tcp performance,” IEEE Trans.
Mobile Computing, vol.4, no.2, pp.209–221, 2005.
[17] W. Haitao, P. Yong, L. Keping, C. Shiduan, and M. Jian, “Performance of reliable transport protocol over ieee 802.11 wireless lan:
Analysis and enhancement,” INFOCOM 2002. Twenty-First Annual
Joint Conference of the IEEE Computer and Communications Societies, Proc. IEEE, pp.599–607, 2002.
[18] L. Yang, W.K. Seah, and Q. Yin, “Improving fairness among tcp
flows crossing wireless ad hoc and wired networks,” MobiHoc’03:
Proc. 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp.57–63, ACM, New York, NY, USA,2003.
[19] H. Gossain, C. de M. Cordeiro, and D.P. Agrawal, “Energy eﬃcient
mac protocol with spatial reusability for wireless ad hoc networks,”
International Journal of Ad Hoc and Ubiquitous Computing, vol.1,
no.1/2, pp.13–26, 2005.
[20] A. Kochut, A. Vasan, A.U. Shankar, and A. Agrawala, “Sniﬃng out
the correct physical layer capture model in 802.11b,” Network Protocols, 2004. ICNP 2004. Proc. 12th IEEE International Conferenceon, pp.252–261, 2004.
[21] 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.
[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.

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.