This is the pre-print version. This work was submitted to the ACM for possible publication. (c) ACM, 2015. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution.

A Method at Link Layer to Improve the Fairness
in Multi-hop Wireless Ad Hoc Networks
Nguyen Minh Tuan

Kenji Nakagawa

Kohei Watabe

Graduate School ofEngineering, Nagaoka
University of Technology
Kamitomiokamachi 1603–1
Nagaoka, Niigata, Japan

Graduate School ofEngineering, Nagaoka
University of Technology
Kamitomiokamachi 1603–1
Nagaoka, Niigata, Japan

Graduate School ofEngineering, Nagaoka
University of Technology
Kamitomiokamachi 1603–1
Nagaoka, Niigata, Japantuan@
kashiwa.nagaokaut.ac.jp

nakagawa@nagaokaut.ac.jp

k_watabe@vos.nagaokaut.ac.jp

ABSTRACT
Using the protocol IEEE 802.11, multi-hop wireless ad hoc
networks yield only a poor performance, especially in throughput and fairness. When the offered load becomes large, i.e.
the system is in saturation state, long-distance flows suffera high degree of throughput deterioration. These problems
not only come from medium contention at the MAC layer
but are due to the link layer. In this paper, we propose amethod to solve the throughput degradation and unfairness
problem by providing fair treatment between flows at thelink-layer. In our proposed method, a fair scheduling algorithm using round robin queue and the estimation for the
average interval of packet enqueueing is applied to alleviate
the unfairness problem at both MAC and link layer. The
simulation results reveal that our proposed method is able
to achieve better throughput and fairness compared to thestandard IEEE 802.11.

Keywords
fairness, multihop wireless, throughput, link layer, scheduling

1.

INTRODUCTION

An ad hoc wireless network is an infrastructureless wireless network that consists of a set of wireless stations. Eachstation is able to play a role of both a router and an endpoint, forming a multi-hop wireless ad hoc network. Some
attractive features of wireless adhoc networks such as selforiganization, flexibility and simple deployment offer a widearray of applications.
In wireless ad hoc network, the IEEE 802.11[4] protocol, in
which Distribution Coordinated Function (DCF) performs
a vital role, is de facto standard used at the MAC layer.
DCF prevents channel from colliding, endeavors the fairness in sharing channel resource between stations, and facilitates asynchronous data transfer. However, IEEE 802.11
protocol is known to have throughput unfairness problem,
both short-term and long-term fairness[12]. In particular,
in a multi-hop ad hoc network where direct flows and forwarding flows coexist, the throughput of many hop flows
decrease dramatically. To illustrate this, we carried out anexperiment with a simple topology as Figure 1 by network
simulator 2 (NS-2)[1]. The channel bandwidth is set to 2

Figure 1: A basic multihop network model

Mbps. Each station generates a 1.6 Mbps offered load with1∼Kb payload per packet, enough to make the network inthe saturation state, i.e. each node always has a packet totransmit. The result discloses that the flow 1, or direct flow
has a throughput of about 1.25 Mbps while the throughputof flow 2, the forwarding flow, just reaches at 0.0013 Mbps.
There are many factors causing this unfairness problem[13].
At the MAC layer, one of well-known problems is hidden terminal problem. Although, using RTS/CTS handshake cangreatly reduce the effect of hidden terminal problem, thisproblem can not be solved completely. As shown in the Fig.
1, node R is always ready to receive a packet, i.e. it will
immediately reply a CTS message as soon as a RTS frame
comes. Assume that node S1 and node S2 would like totransmit a packet, then they transmit a RTS frame to node
R and S1 respectively. Node R can immediately answer witha CTS frame while node S1 cannot because of its busy state.
Finally, node S1 succeeds in transmitting its packet and reset its CW back to its minimum value. Thus, it is clearthat node S1 gains more advantages in the next channel
contention. In addition, the standard protocol cannot deal
with the exposed node problem[7] which has injurious effects
in a multi-hop network. Another problem is the large-EIFS
problem[14].
At the link layer, Nandiraju et al.[9] proves that the link
layer buffer management plays an important role for achieving good throughput and fairness. In multi-hop wirelessnetwork, the default queue management is FIFO queue. At
an intermediate node, the queue at the link layer is responsible for both packets of forwarding flows from other sources
and packets of the direct flow from its-own. Unfortunately,a packet of forwarding flow needs some time to arrive at thequeue from its source while a packet of the direct flow canbe enqueued immediately as soon as it is generated. As a

result, packets of a direct flow may occupy almost all thebuffer space, then packets of forwarding flows are dropped
due to buffer overflow.
In this paper, based on Probabilistic Control on Roundrobin Queue (PCRQ)[5], we propose a queue management
scheme for multi-hop wireless networks at the link layer tosolve the unfairness problem and throughput degradation.
The algorithm is formed of Round Robin queue mechanism
in combination with an estimation of the packet enqueue.
According to the packet enqueuing rate of each flow, anarrival packet can be enqueued or dropped. In addition, if
the reading turn comes to an empty queue, we will makea delay time calculated by the packets enqueue interval ofthat queue. This facilitates the fair serving between flows atlink layer and a time delay at an advantageous station will
create a chance for other stations to obtain the channel andtransmit its packets. Our scheme requires no modifications
to the MAC layer, thus in the practical, there is no need to
do hardware modification.
The rest of the paper is organized as follows. In section
2 and 3, we briefly present some related works including
PCRQ. Our proposed method is given in section 4. The
numerical results are shown in section 5. Finally, section 6
commits a short conclusion.

2.

PCRQ

Giang[5] researched the unfairness problem at both MAC
layer and link layer in multi-hop networks. He introduced
a method called probabilistic control on round robin queue(PCRQ) to lessen the unfairness problem and improve the
network performance. PCRQ is composed by three algorithms at the link layer.
The first algorithm is used for controlling the number of
input packets to the queue. An arrival packet is put to thequeue with the probability calculated by(
Pi input =1
i −ave1 − α qlen(n−1)ave

Pi turn =if qleni ≤ ave
if qleni > ave

where α is a constant, n is the number of flows, qleni is
the queue length of the flow i, and ave is the average of theqleni , i = 1, . . . , n.
The second algorithm is used for controlling the turn ofreading queues by giving waiting time δ for the empty queue.
The queue’s turn of a flow i is kept at the following probability

β n×aveqmax
0

if qleni =0
if qleni >0

where β is a constant, qmax is the maximum queue length.
The third algorithm is used to decrease the number ofpackets from heavy offered load flows to MAC layer. The
idea is controlling the number of output packets from RR
queues. A packet at the head of the queue of flow i is sent
to MAC at probability calculated by(1
if qleni ≤ave
Pi output =i −ave1 − γ qlen
if
qleni >ave(n−1)avewhere γ is a constant.
By three above algorithms, PCRQ operates for discarding
packets before entering to a queue or giving delay to packets in the queue basing on some probability. Hence, PCRQ
results in an equal packet distribution between flows. However, within a short-time scale, PCRQ does not always provide a fairness of short-term throughput. In addition, thedetermination of values α, β, γ in PCRQ are not easy andrequire much experimental effort.

4.

RELATED WORKIn reference [8], Nandiraju et al. suggested a fair scheduling algorithm called Dual Queue Service Differentiation(DQSD).
DQSD uses two separate queues for forward flow and direct flows and manages to provide fair service to these twoqueues. However, since packets from all forwarding flows are
put into one queue, it is not ensure the justice for packets
from large distance. Shagdar et. al. [10] and Izumikawa
et. al. [6] also investigated the unfairness of direct flow andforwarding flows. They proposed a scheduling algorithm byusing Round Robin scheduling. Nevertheless, their proposal
considers an ideal MAC layer that is difficult to obtain. Giang[5] shows that only RR mechanism cannot result in a
per-flow fairness.

3.

(

PROPOSED METHOD

Inheriting the basic idea of PCRQ in [5], we offer a modification at link layer to cope with the poor performance interm of fairness in multi-hop wireless network. Our method
consists of two algorithms: the algorithm 1 controls queue
input and and the algorithm 2 controls the queue reading .
The details are as follows.
The time interval between the two consecutive enqueued
packets at a queue of a flow i, called packet enqueue interval
σi , is calculated as below.
Each time a packet is enqueued to the queue i, calculate(σ
if k=1(1)σi = ti (k) − ti (1)if k ≥2k−1
where σ is a pre-defined value, k is the number of packets,ti (k) indicates the time that a kth − packet is enqueued.
Then, average packet enqueue interval σ̄ is calculated as
N
P

σ̄ =

σi

i=1

N

(2)

where N is the number of queues, σi is the value calculatedby (1).

4.1

Algorithm 1 (modified)

As analysis, in a multi-hop wireless ad hoc network, packets from the direct flow come to the queue much faster, andthus the queue of the direct flow has a higher enqueue rate.
Algorithm 1 is proposed to prevent this problem. It takes adecision on enqueueing or dropping an arrived packet. Eachtime a packet arrives to a queue, if the packet enqueue interval of the queue is less than the average packet enqueueinterval between all queues, it is likely that this packet will
be dropped.

Algorithm 1 Packet Drop Decision
when a packet arrives
check source node i of this packet
if there is no queue for this source node thencreate a new queue;enqueue the packet;
else
calculate average packet enqueue interval σ̄ by (2)if σi < σ̄ − η (η is a constant that approximates to 0)
thendrop the packet;
elseenqueue the packet to the queue;
end ifend ifBy this algorithm, packets of a flow with high arrival rate,i.e. heavy offered load are likely to be dropped. This algorithm keeps the balance between queues. Hence, the queue
length of each flow is kept equivalently small.

4.2

Algorithm 2 (modified)

Unlike packets from the direct flow that can be enqueued
immediately when generating, packets from forwarding flowsneed sometime to reach at the intermediate node. Hence,usually, the queues of forwarding flows are empty. This
causes the unfairness when reading queue. Algorithm 2 is
proposed to deal with this problem. It gives a delay time inreading queue if the queue is empty. If the reading pointerpoints to an empty queue, we will give a delay time forpacket traversal from the remote node. However, different
from PCRQ where in an empty queue, a delay action is determined by a probability based on the queue length, andthe period of delay time is fixed in a δ time, our new algorithm tends to calculate how much time the reading pointershould wait when pointing to an empty queue.

Table 1: NS-2 parameters configuration
Channel data rate
Antenna typeRadio Propagation
Transmission range
MAC protocol
Routing protocol
Connection type
Queue type
Maximum Queue length
Packet’s size
Simulation time

2 MbpsOmni direction
Two-ray ground250 [m]IEEE 802.11b(RTS/CTS mechanism is enable)
DSDV
UDP/CBR
FIFO, PCRQ, proposal
100 [packets]
1024 Bytes
75sload about 1.6 Mbps, so large that a single flow can occupy
all the channel and the unfairness occurs when the network
is in a saturation state. The initial values σ and η are respectively set to 0.02 and 0.01 after extensive simulations. The
metrics using to evaluate are throughput and fairness index.
In term of throughput, we consider aggregate throughput,short-term throughput and average throughput of each flow.
In the aspect of fairness, the short-term fairness[3] is examined. Actually, in the context of communication networks,
there are two kinds of fairness, namely, short term fairness
and long term fairness. Long term fairness implies fairness
over long time scales while short term fairness focuses on
the fairness evaluation of shared channel over short timescales[3]. Short-term fairness has a great impact on the performance of applications especially real-time applications[2].
Additionally, short-term fairness may suggest long-term fairness but not vice versa. Short-term fairness can be calculated by sliding window method (SWM), as given in [3], overan arrival packets stream as the illustration figure SWM be-

Algorithm 2 Delay Time Control
Each time reading pointer points to a queue iif this queue is empty thengive a delay σi , σi is the value calculated by (1);read the queue;
if this queue is still empty thenskip to the queue (i + 1);
else
read a packet from queue i;go to the queue (i + 1);
end ifelse
read a packet from queue i;go to the queue (i + 1);
end if5.

Figure 2: Sliding window method for calculating short-term
fairness with the window size equals to 4

PERFORMANCE EVALUATIONIn this section, we compare our proposed method with
PCRQ[5] and FIFO performed by NS-2 version 2.35[1]. NS2 simulation parameters are set as the table 1. In the simulation, the raw bandwidth of the channel is set to 2 Mbps,
causing the maximum throughput about 1.4 Mbps due tothe overhead in IEEE 802.11[14]. For each flow, the packet
interval is set to 200 packets per second, leading the offeredgins from a packet trace and slide a given window size w
across it. Initially, the left edge of the window is matchedwith the left edge of the packet arrival stream, i.e. the first
packet. Then, we determine the packet ratios of packet arrivals from each flow i within this window boundary. Next,
based on these ratios, we will compute Jain fairness index

[11] for this window by this formulanX

FJ(w) =

i=1
n
X

n

measurement and may be affected by other factors at thelink layer. Therefore, this metric reflects the network state
more exactly and can give quickly response with the contemporary network state. The per-flow throughputs are shown!2xi (w)(3)(xi (w))2

1.4
1.2

where n is the number of flows, xi (w) is the ratio of thenumber of packets from a flow i per window w. The fairness
index ranges from 1/n for the worst case to 1 for the bestcase. We then step by step slide the window to the right side
and calculate the appropriate fairness index to each window.
Finally, the short-term fairness index for this given window
size is computed by the average of all acquired fairness indices. Additionally, if the window size is large w = ∞, theshort-term fairness will focus to the long-term fairness.

5.1

Throughput [Mbps]

i=1

1
0.8

Th 1-00.6

Th 2-0
0.4

0.2
0
50

70

80

90

100

110

120

Time [s]Scenario 1

Figure 4: FIFO - short-term throughput

Scenario 1 is a typical 3-node chain topology as Figure 1.
Two stations 1 and 2 generate UDP packets to the destination R. The fairness index and throughput comparison are
shown in Figure 3, Figure 4, Figure 5, Figure 6, and Figure
7.
1
0.95
0.9
0.85
0.8
0.75
0.7
0.65
0.6
0.55
0.5

PCRQ

0.8
0.7

Throughput [Mbps]

Fairness Index

60

0.6
0.5
0.4

Th 1-00.3

Th 2-0

0.2

0.1

FIFO

0

proposal

50

60

70

80

90

100

110

120

Time [s]246

8 10 12 14 16 18 20 22 24 26 28 30 32

Figure 5: PCRQ - short-term throughput

window size

Figure 3: Fairness Index
0.8

Throughput [Mbps]

0.7

It can be clearly seen from the Figure 3 that with our proposed method, the fairness index is greatly improved compared to the case of FIFO. It is also considerably higher
than PCRQ especially with a small window size. Our fairness result is also confirmed by the short-term throughput
shown in the Figure 4, Figure 5 and Figure 6. In our proposed method, the end-to-end throughputs are fairer andmore stable than others, resulting in a better fairness index.
The effect of our method can be explained as follows. With
FIFO queue, as analysis in the Section 1, the direct flow
tends to occupy almost all the buffer, this leads to packets from other flows are easily dropped due to buffer flow.
Also, the position of the station 1 enables much more advantage in channel contention. Compared to FIFO, firstly,
our proposed method provides a fair share between flows by
round robin mechanism to solve the unfairness at the link
layer. Secondly, by controlling packet input and delay using
packet interval time information of each queue, our method
can deal with the unfairness at the MAC layer. Comparedto the PCRQ, this idea is based on the packet rate instead ofqueue length. The packet rate is more closely related to thelower layer. It is the direct measurement that MAC layer
notifies to the link layer while the queue length is indirect

0.6
0.5
0.4

Th1

0.3

Th2

0.2

0.1
0
50

60

70

80

90

100

110

120

Time [s]Figure 6: proposal - short-term throughput

in the Figure 7 with a notice that Th1 and Th2 indicate end
to end throughputs from station S1 and S2 to station R,
respectively. From this chart, the aggregate throughput inthe case of our proposed method is slightly degraded compared to that in the case PCRQ and FIFO. Actually, there
is a trade-off between fairness and aggregate throughput inthis type of topology. To explain about it, assume that the
bandwidth of the channel is B. Then, if we could achieve theperfect fairness, 1 in particular, the per-flow throughput will

0.7

1.4

Throughput [Mbps]

1
0.8

Th2
0.6

Throughput[Mbps]

0.6

1.2

Th1

0.5

Th4
0.4

Th3
0.3

Th2

0.2

Th1

0.1

0.4

0

FIFO

PCRQ

proposal

0.2

Figure 10: Throughput scenario 2

0

FIFO

PCRQ

proposal

Figure 7: Throughput scenario 1

that our proposed method can lead to a small fluctuation
and a minimal difference between flows.
0.8
0.7

Throughput [Mbps]

equal to B/3. This is because the packet from the station S2
to station R need to be forwarded by the station S1. As aresult, the aggregate of per-flow throughput will be 2B/3. In
contrast, when the fairness is worst, 0.25 in particular, thethroughput Th1 can be up to B because of its advantageous
position while throughput Th2 is zero. Clearly, in this case,the aggregate can go up to B.

0.6
0.5

Th1
0.4

Th2

0.3

Th3

0.2

Th4

0.1
0
50

5.2

60

70

80

Scenario 2

90

100

110

120

Time [s]Scenario 2 is a typical 5-node chain topology as Figure 8.
The fairness index and throughput comparison are shown in
Figure 9, Figure 10, Figure 11, Figure 12, and Figure 13.

Figure 11: FIFO - short-term throughput

0.3

Throughput [Mbps]

0.25
0.2

Th1
0.15

Th2
Th3

0.1

Th4
0.05

Figure 8: Network topology for scenario 2

0
50

60

70

80

90

100

110

120

Figure 12: PCRQ - short-term throughput

1
0.95
0.9
0.85
0.8
0.75
0.7
0.65
0.6
0.55
0.5
0.45
0.4
0.35
0.3
0.25

PCRQ
0.3

FIFO

0.25

proposal4

8 12 16 20 24 28 32 36 40 44 48 52 56 60 64

window size

Figure 9: Fairness Index

Throughput [Mpbs]

Fairness Index

Time [s]

0.2

Th1
0.15

Th2
Th3

0.1

Th4
0.05
0
50

60

70

80

90

100

110

120

Time [s]From the figures, although in this case, both channel contention and link layer contention is much harder comparedto the scenario 1, the fairness index is considerably improved
especially in comparison to FIFO. Again, the reason is thatour proposed method can face with both contention at both
MAC and link layer. Also, using the packet interval time will
enable the node to response more quickly with the changeof network state. The short-term throughputs comparison
exhibits in the Figure 11, Figure 12, Figure 13 also prove

Figure 13: proposal - short-term throughput

The Figure 10 shows the aggregate throughput comparison between FIFO, PCRQ and our proposed method. Because of the similar reason in the scenario 1, the aggregate
throughput in our method is decreased a little. In this scenario, we give one more metric to compare the performance,that is the packet delay time shown in the table 2. In thistable, it can be seen that our proposed method gives a small
delay time, just slightly higher than PCRQ. In the case of
FIFO, the delay time of packets from the flow 4 is small.
This is because in FIFO case, the throughput of flow 4 isalmost zero, i.e. there are few packets that are transmitted.

FIFO
PCRQ
proposalFlow 1
1.13
0.12
0.25

Flow 2
0.86
0.23
0.58

Flow 3
0.45
0.29
0.67

Flow 4
0.45
4.79
5.06

Figure 17: FIFO - short-term throughput

Table 2: Delay time [s] Scenario 2

5.3

Scenario 3

Scenario 3 is a two-chains topology as Figure 14 with 4flows. The fairness index and throughput comparison are
shown in Figure 15, Figure 16, Figure 17, Figure 18 and
Figure 19.
Figure 18: PCRQ - short-term throughput

Figure 14: Network topology for scenario 3

Figure 19: proposal - short-term throughput

Figure 15: Fairness Index

Firstly, in the term of fairness index exposed in the Figure
15, our proposal results in the highest fairness. Additionally, the fairness in our proposal still stands at a high valueof about 0.95 even with a smallest window size. This is also
proved in the short-term throughput comparison presented
in the Figure 17, Figure 18, Figure 19. In our method, theper-flow throughputs are keep balance and steady while inothers, the period of simulation time sees a fluctuation between per-flow throughputs. Secondly, in this scenario, theaggregate throughput in Figure 16 shows that our method
can lead to a slightly higher aggregate throughput comparedto PCRQ. The reason for this is, in this type of topology,
our proposed method can lead to an independent increasein the throughput of flow 2 and have a better result in aggregate throughput. Thirdly, the packet delay time shownin the table 3 indicates that there is not much difference inthe packets delay between our method and PRRQ. In thecase of FIFO, the packets delay of forwarding flows are quite
small because in FIFO, the forwarding flows throughputs arealmost zero, i.e. just few packets are transmitted.

Figure 16: Throughput scenario 3

6.

CONCLUSION

FIFO
PCRQ
proposalFlow 1
1.27
0.36
0.12

Flow 2
0.84
6.58
5.76

Flow 3
1.00
5.07
4.68

Flow 4
0.41
6.64
6.46

Table 3: Delay time Scenario 3

In this paper, we focus on the unfairness problem in multihops wireless network. The unfairness not only comes from
the MAC layer but also from the link layer. Then, we
propose a scheduling method based on round robin mechanism and packet interval time to deal with this problem.
Our method solves the unfairness problem at both MAC
and link layers. The simulation results show that our proposed method is able to improve the fairness considerably.
As a result, the short-term throughputs between flows are
kept stable and balance. Thus, it facilitates a better performance especially for real-time applications. Additionally,
this method requires only link layer modifications withoutchanging the hardware.

7.

REFERENCES[1] The network simulator: Ns-2,
http://www.isi.edu/nsnam/ns/.
[2] C. Koksal, H. Kassab and H. Balakrishnan. An
Analysis of Short-Term Fairness in Wireless Media
Access Protocols. In Proc. of ACM SIGMETRICS,
pages 118–119, 2000.
[3] C.L. Barrett, M.V. Marathe, D.C. Engelhart, A.
Sivasubramaniam. Analyzing the Short-term Fairness
of IEEE 802.11 in Wireless Multihop Radio Networks.
In Proc. of MASCOTS’02, pages 137–144. IEEE, 2002.
[4] IEEE Standards Department. IEEE 802.11 Wireless
LAN Medium Access Control (MAC) and PhysicalLayer (PHY) Specifications. 2012.
[5] P.T. Giang and K. Nakagawa. Achieving Fairness over802.11 Multihop Wireless Ad Hoc Networks. IEICE
Trans. on Commun., E92-B(8):2628–2637, 2009.
[6] J. Jun, M.L. Sichitiu. Fairness and QoS in Multihop
Wireless Networks. In Proc. of IEEE VTC, volume 5,
pages 2936–2940. IEEE, 2003.
[7] A. Jayasuriya, S. Perreau, A. Dadej, S. Gordon.
Hidden vs. Exposed Terminal Problem in Ad Hoc
Networks. In Australian Telecommunication Networks
and Applications, 2004.
[8] N. Nandiraju, D. Nandiraju. Service Differentiation in
IEEE802.11s Mesh Networks: A Dual Queue Strategy.
In Proc. of Milcom (Military Communications
Conference), pages 67–72. IEEE, 2007.
[9] N. Nandiraju, D. Nandiraju. A Novel Queue
Management Mechanism for Improving Performanceof Multi-hop Flows in IEEE802.11s Based Mesh
Networks. In Proc. of the 25th IEEE International
Performance Computing and Communications
Conference, pages 168–173. IEEE, 2006.
[10] O. Shagdar, K. Nakagawa, and B. Zhang. Achieving
Per-Flow Fairness in Wireless Ad Hoc Networks. Elec.
Comm. in Japan, Part 1, 89(8):37–49, 2006.
[11] R.Jain, D.M. Chiu, and W. Hawe. A Quantitative
Measure of Fairness and Discrimination for Resource

Allocation in Shared Computer Systems. Technicalreport, DEC Research Report, 1998.
[12] T. Nandagopal, T. Kim, X. Goa and V. Brarghavan.
Achieving MAC Layer Fairness in Wireless Packet
Networks. In Proc. of the 6th annual international
conference on Mobile computing and networking, pages
87–98. ACM, 2000.
[13] S. Xu and T. Saadawi. Does the IEEE 802.11 Mac
Protocol Work Well in Multihop Wireless Ad Hoc
Networks? Communications Magazine, 39(6):130–137,
2001.
[14] Z. Li, S. Nandi, and A. K. Gupta. Ecs: An Enhanced
Carrier Sensing Mechanism for Wireless Ad-hoc
Networks. Computer Communications,28(17):1970–1984, 2005.