=Paper=
{{Paper
|id=Vol-1256/poster5
|storemode=property
|title=Fairness Improvement of MAC in Wireless Ad Hoc Networks
|pdfUrl=https://ceur-ws.org/Vol-1256/poster5.pdf
|volume=Vol-1256
|dblpUrl=https://dblp.org/rec/conf/vecos/MehaouedSB14
}}
==Fairness Improvement of MAC in Wireless Ad Hoc Networks==
https://ceur-ws.org/Vol-1256/poster5.pdf
143
Fairness Improvement of MAC in Wireless Ad Hoc
Networks
Kamal Mehoaued Larbi Sekhri Malika Bourenane
Computer Science Department Industrial Computing and Industrial Computing and
Universiy of Oran, Algeria Networking Laboratory Networking Laboratory
mehaoued.kamal@gmail.com Computer Science Department, Computer Science Department,
University of Oran, University of Oran,
BP 1524 Oran, Algeria BP 1524 Oran, Algeria
Larbi.sekhri@univ-oran.dz mb regina@yahoo.fr
Abstract—There are many medium access control nodes. It is obvious, that in this case, cooperation be-
(MAC) protocols proposed to achieve fairness in presence tween involved nodes is very important in order for the
of hidden and/or exposed nodes. In [2] a general approach network to emerge and operate.
to address the propblem of fairness is proposed. This Since ad hoc networks deploy multi-hop routing pro-
approach defines a fairness index and the goal is to
tocols [5], [14], [9], [15], where each of the nodes in
minimize this fairness index to achieve fairness. in this
paper we propose a fairness index by taking into account
addition to its own packets has to forward packets be-
both node’s data traffic and routed data traffic of the longing to other nodes, selfish behavior may represent a
other nodes for each node and we can easily verify that significant advantage for a node, saving its battery power
the fairness index defined in this paper is always lower or and reserving more bandwidth for its own traffic, if a
equal to the fairness index defined in [2]. large number of nodes start to behave non cooperatively,
Index Terms—Ad Hoc Networks, MAC, Fairness, IEEE the network may break down completely, depriving all
802.11,Scheduling, Routing and Quality of Service. users from using the provided services.
To avoid misbehavior of the mobile nodes in wireless
I. I NTRODUCTION ad hoc networks, compensation has to be made in order
to encourage all the nodes in routing other nodes packets
Ideally, users of wireless networks will want the same without any degradation of their own data transmission.
services and capabilities that they have commonly come While there has been lot of research work on improv-
to expect with wired networks [6]. In [4] architecture ing fairness in the presence of hidden and/or exposed
for managing quality of service (QoS) applied to Diff- terminals [10], [3], [17], [7], [2], [13], [18], [16].
Serv environments and IEEE 802.11e is proposed. This This paper describes an improvement of fairness in
architecture is based on the dynamic coupling between MAC within Wireless Ad Hoc Networks. This improve-
the Diffserv component and the service classes provided ment takes into account both nodes data traffic and
by the standard IEEE 802.11e. routed data traffic of the other nodes. It tends to give
Recent advances in computer and wireless commu- approximatively the same bandwidth share for every
nication technologies have led to an increasing interest node in wireless ad hoc network for its own use, which
in wireless mobile ad hoc networks. In this type of means that it will be used to sending its own packets,
networks, each mobile host plays the role of a router even though it is forwarding other nodes packets.
while being a terminal able to communicate with other The remaining parts of this paper are organized as
wireless mobile nodes. In fact, if a source and destination follows. In section II we give a short overview of IEEE
nodes are not in the communication range of each other, 802.11 MAC functions. In section III, we describe the
data traffic is forwarded to the destination by relaying initial version of RAMAC mechanism. In section IV we
transmission through other mobile nodes which exist describe a short overview of the principle works that
between the two communicating source and destination are proposed to improve fairness in MAC protocols. In
144
section V, we investigate a scalability study of RAMAC III. R ELATED W ORK
in a wireless ad hoc networks. Section VI gives the con-
clusion of this work and outlines future work extensions. A large number of random access MAC protocols have
been developed to enhance the channel performance and
II. IEEE 802.11 OVERVIEW fairness.
The IEEE 802.11 standard defines two operational MACA [10] is based on the following principle: When
modes for wireless LANs networks: infrastructure based hidden terminals exist, lack of carrier does not always
and infrastructure-less or ad hoc based modes [8]. Net- mean it is ok to transmit. Conversely, when exposed
work interface can be set to work in either of these terminals exist, presence of carrier dos not always mean
modes but not in both simultaneously. Infrastructure it is bad to transmit. MACA proposed to get grid of the
mode resembles to cellular infrastructure-based mode CS part in CSMA/CA and extend the CA part. When a
network (GSM). In the ad hoc mode, any station that station overhears an RTS addressed to another station, it
is within the transmission range of any other can start inhibits its own transmitter long enough for the addressed
communicating. No access point is required, but if one station to respond with a CTS. When a station overhears
of the stations operating in the ad hoc mode has a a CTS addressed to another station, it inhibits its own
connection also to a wired network, stations forming the transmitter long enough for the other station to send its
ad hoc network gain wireless access to the Internet. data.
The IEEE 802.11 standard specifies a MAC layer In MACAW [3] the backoff algorithm was modified by
and a PHY layer for WLANs. We only consider the including in the packets header a field which contains the
MAC layer. The MAC layer offers two different types of current value of the backoff counter. Whenever a station
service: a contention service provided by the Distributed hears a packet, it copies that value into its own backoff
Coordination Function (DCF), and a contention free counter. The throughput allocation is now completely
service implemented by the Point Coordination Function fair. The BEB backoff calculation adjusts extremely
(PCF). rapid. To prevent such wild oscillations, MACAW has
instead adopted a gentler adjustment algorithm which
A. Point Coordination Function is called Multiple increase linear decrease MILD. Three
The Point Coordination Function (PCF) is imple- additional control packets ACK, DS and RRTS, are used
mented on top of Distributed Coordination Function in MACAW to alleviate the effect of hidden terminals,
(DCF) and is based on a polling scheme. It uses a Point exposed terminals and make error recovery faster.
Coordination Function that cyclically polls stations, giv- In [7], to minimize collisions and maximize channel
ing them the opportunity to transmit. Since the DCF reutilization, if two flows are contending flows, they are
cannot be adopted in the ad hoc mode, hereafter it will expected not to be scheduled to transmit simultaneously,
not be considered. otherwise, they should eventually transmit simultane-
ously, they should eventually transmit simultaneously in
B. Distributed Coordination Function order to maximize network throughput. In [7], a flow
The Distributed Coordination Function (DCF) pro- contention graph G = (N, A) where N is the set of
vides the basic access method of the 802.11 MAC flows and A is the set of edges of the graph (presence
protocol and is based on CSMA/CA scheme. According of contention), is divided into cliques, where a clique is
to this scheme, when a node receives a packet to be defined as a subset of N such that for all ditinct pair
transmitted, it first listens to the channel to ensure no u, v ∈ cl, the edge [u, v] ∈ A. By construction of the
other node is transmitting. If the channel is clear, it then flow contention graph, and the definition of a clique,
transmits the packet. Otherwise, it chooses a random any two or more flows that belong to the same clique,
backoff value which determines the amount of time cannot be scheduled to transmit simultaneously.
the node must wait until it is allowed to transmit its In [13], a probability based backoff algorithm has been
packet. During periods in which the channel is clear, the proposed to address the unfairness problem, A fairness
node decrements its backoff counter. When the backoff index has been introduced to be the ration of maximum
counter reaches zero, the node transmits the packet. link throughput to minimum link throughput. Each node
Since the probability that two nodes will choose the same calculates a link access probability for each of its links
backoff is small, the probability of packet collisions, based on the number of connections from itself and its
under normal circumstances, is low. neighbors, or based on the average contention period of it
145
and other nodes individual links. Whenever its backoff contention window value CW after each unsuccessful
period ends, a node i will send RTS packet to j with transmission. We believe that by doing so, mobile nodes
probability pij or backoff again with probability 1 − pij participating in routing other nodes data traffic will not
In [18], a JMAC (jamming-based MAC) protocol that suffer from sending their own traffic. For each node i
is not only free from both the hidden terminal and the generating its own traffic and routing other nodes traffic,
erroneous reservation problems but also allows more we define:
current transmission/receipt activities for stations within • Wown (t) : the amount of the own data traffic to send
each others transmission range. The idea behind JMAC belonging to node i at time t
is to separate source stations traffic from destination • Wrouted (t) : the amount of the routed data traffic to
stations traffic into different channels, and explicitly send belonging to node i at time t
signal the channel status by jamming the channel. In Wrouted (t)
• ρi (t) = W : the ratio of the routed
own(t) +Wrouted (t)
JMAC, the medium is divided into two channels: S packets of node i at the also the same time t over
channel and R channel. RTS and DATA frames are the total packets.
transmitted on the S channel and CTS and ACK frames In the basic DCF scheme in IEEE 802.11 for ad hoc
are transmitted on the R channel. It is assumed that each networks, the contention window CW is reset to its min-
station is equipped with two radio devices, one tuned to imum value CWmin after each successful transmission
the S channel and the other tuned to the R channel. The and doubled when collision occurs or the medium is
ration of bandwidth allocated to the R and S channels is sensed to be busy at the end of defer access period. In
assumed to be α : (1 − α) where 0 < α < 1. RAMAC mechanism [1], [11], [12] we propose to this
In [16], a DMAC (Deferrable MAC) protocol that al- mechanism.
leviates the hidden terminal problem by deferring further
1) CW Decrease In the DCF scheme, after each
transmissions until the previously transmitted packets
successful transmission the CW value is reset to
travel far enough to avoid interference with the newly
its minimum contention window value CWmin,
transmitted packets.DMAC leverages the observation
this mechanism is kept invariable since it helps the
that for flows that span multiple hops, it is possible to
node to access the medium with a high probability.
determine how far a packet needs to advance over the
2) CW Increase : After each unsuccessful transmis-
multi-hop route before it is possible to transmit a new
sion, caused by a contention with another transmit-
packet, such that subsequent transmissions of the new
ter or a busy medium sensed after a defer access
and old packets are likely not to interfere with each other.
period, the DCF function doubles the contention
In [2], the fairness index is introduced as in [13]
CW.
to quantify fairness, and proposes a new estimation
based backoff algorithm. The new algorithm can sup- CWnew = min(2 ∗ CWold , CWmax ) (1)
port the case when packets lengths are variable. This
In RAMAC, this mechanism is changed. After
work demonstrated that the unfairness problem can be
each unsuccessful transmission, a mobile node i
very severe with the original binary exponential backoff
updates its contention window using a multiplica-
algorithm when packet length is variable and that their
tive factor M Fi . The multiplicative factor M Fi is
new backoff algorithm can achieve better fairness.
calculated after each update period ∆(t).
IV. RAMAC MECHANISM OVERVIEW M F i = 2 − ρi (2)
To address the problem of efficient bandwidth sharing
The new CW is then calculated following this
among all mobile nodes of a wireless ad hoc network.
equation:
We believe that when a mobile node is participating
in routing other nodes packets, it has to access more CWnew = min(M Fi ∗ CWold , CWmax ) (3)
frequently the channel than one which is not participating
in routing packets. Moreover, depending on the amount V. FAIRNESS I MPROVEMENT
of data to route, one node may access the channel more In [2], this following notation is introduced:
frequently than one which has less data to route • Φi : A predefined fair share that station i should
In order to succeed in obtaining full nodes cooperation receive. Normally, it should be determined at ad-
and efficiently share the channel in 802.11 based wireless mission control.
ad hoc network, we choose to change dynamically the • Wi : The actual throughput achieved by station i
146
• Li : Station i’s offered load. Algorithm 1 the new ajustement of the CW
In [2], If each station is considered to be a greedy source switch(F Ie ) {
and wants to get the same share as all other stations case > C :
as a whole, then it can just set Φi = 0, 5regardless of CWnew = min(CWold × F I, CWmax )
the number of its neighbors. As to any station, say i, it case (1/C, C):
requests the same share as all the others in its vicinity. CWnew = CWold
These stations have a total share of 1 − Φi = 0, 5. which case < C :
equals to this stations share Φi . This can be interpreted CWnew = max(CWold /F D, CWmin )
as a per-station fairness. We propose to set the share Φ }
of any node i to a value which depends on the ratio ρ
Φi = (1 + ρi )/2 (4) Thus the fairness is improved.
3) Proof : In [2], the goal is to design an algorithm
where ρi is the ratio of routed packets of node i over the which minimizes the fairness index. The fairness
total packets. Note that when ρi = 0, which means that index estimated in [5] is:
the node i has no packet to route, we obtain Φi = 0, 5
Wei Weo
and when ρi = 1, which means that the node has only F Ie = ( )/( ) (6)
packets to route Φi = 1, this means that the node gets all Φi Φo
the channel for its own use. The more a node has packets Let’s set the Φi to the constant 0,5. The fairness
to route the more frequently it has access to the channel. index becomes then
We propose a modification in the backoff scheme to take
into account the ratio ρi for any node i in the wireless Wei
F Ie = (7)
ad hoc network. Weo
1) CW Decrease : In [2], the CW is divided by two Let’s calculate the fairness index when we take
when the fairness index is lower than a constant into account ρ
value C which is used to adjust the adaptativity
of the algorithm. We propose to divide the CW Φi = (1 + ρi )/2 (8)
value by a factor of division DF such that
The fairness index becomes:
CWold
DF = ρ( ) − 2(ρ − 1) (5) Wei Weo
CWmin F Ir = ( )/( ) (9)
1 + ρi 1 − ρi
The CW decrease function becomes then:
CWold Now let’s calculate the amount F Ir /F Ie
CWnew = max( , CWmin )
DF 1 − ρi
2) CW Increase : In [2], the CW id doubled when F Ir /F Ie = (10)
1 + ρi
the fairness index is higher than the constant value
C . We propose to change this by multiplying the Given that F Ir > 0, F Ie > 0 and 1−ρ1+ρi > 0 We
i
CW value with a multiplicative M F such that: conclude that F Ir < F Ie for any value of Wei
and Weo and ρi . This leads to say that the fairness
MF = 2 − ρ is improved.
The new CW is then obtained by the following
equation VI. C ONCLUSION
In [2], fairness index is defined and the target to
CWnew = min(M F ∗ CWold , CWmax )
achieve fairness is to minimize this fairness index. In
With these modifications, the backoff algorithm our paper, we proposed a modification to this fairness
in [2] is modified by dividing the CW value by index so that it takes into account both of own data traffic
DF instead of 2 and multiplying the CW value and routed data traffic. We can easily demonstrate that
by MF instead of the constant value 2. With this the fairness index modified is lower or equal than the
estimation, the adjustment of contention window one defined in [2]. This leads to say that the fairness is
is shown in this algorithm improved.
147
R EFERENCES
[1] F. Naı̂t Abdesselam, Towards Routing-aware Adaptive Medium
Access Control in Wireless Ad Hoc Networks, INTERNA-
TIONAL JOURNAL OF WIRELESS AND MOBILE COM-
MUNICATIONS (2004).
[2] B. Besaou, Y. Wang, and C.C Ko, Fair Medium Access in
802.11 based Wireless Ad-Hoc Networks, 1st ACM international
symposium on Mobile ad-hoc Networking, Boston, Massashus-
sets (2000).
[3] V. Bhrghavan, A. Demers, S. Shenker, and L. Zhang, MACAW:
A Media Access Protocol for Wireless LANs, ACM SIGCOMM,
London, England (1994).
[4] M. Bourenane and L. Sekhri, Service differentiation using
reinforcement learning in wireless networks, Verification and
Evaluation of Computer and Communication Systems (2012).
[5] T. Clausen and P. Jacquet, Optimized Link State Routing Pro-
tocol, Internet Engineering Task Force RFC 3626 (2003).
[6] B.P. Crow, I. Widjaja, J.G. Kim, and P.T. Sakai, IEEE 802.11
Wireless Local Area Networks, IEEE Communications Maga-
zine (1997).
[7] X. Huang and B. Bensaou, On Max-min Fairness and Schedul-
ing in Wireless Ad-Hoc Networks, In ACM MobiHoc 01 (2001).
[8] IEEE, Wireless LAN Medium Access Control (MAC) and Phys-
ical Layer (PHY) Specifications, ANSI/IEEE Std 802.11, 1999
Edition (R2003).
[9] D.B. Johnson and D.A. Maltz, Dynamic Source Routing in
Ad Hoc Wireless Networks, Mobile Computing (edited by
Imielinski and Korth, eds.), Cluwer Academic Publishers, 1996,
pp. 153–181.
[10] P. Karn, MACA: A New Channel Access Method for Packet
Radio, ARRL/CRRL Amateur Radio 9th Computer Networking
Confernece (1990).
[11] F. Nait-Abdesselam and H. Koubaa, RAMAC : Routing-aware
Adaptive MAC in IEEE 802.11 Wireless Ad-Hoc Networks,
In 8th International Conference on Cellular and Intelligent
Communications Seoul, Korea (2003).
[12] F. Naı̂t-Abdesselam and H. Koubaa, Enhanced Routing-aware
Adaptive MAC with Traffic Differenciation and Smoothed Con-
tention Window in Wireless Ad-Hoc Networks, Proceedings
of the 24th Conference on Distributed Computing Systems
Workshop IEEE (2004).
[13] T. Ozugur, M. Naghshineh, P. Kermani, and J. Copeland, Fair
Media Access for Wireless NANs , IEEE GLOBECOM, Rio de
Janeiro (1999).
[14] C. Perkins, E. Belding-Royer, and S. Das, Ad hoc On-Demand
Distance Vector (AODV) Routing, Internet Engineering Task
Force RFC 3661 (2003).
[15] C.E. Perkins and E.M. Royer, Ad-hoc On-Demand Distance
Routing, Proceedings of the 2nd IEEE Workshop on Mobile
Computing Systems and Applications (1999), 90–100.
[16] A. Varshavsky and E. D. Lara, Alleviating Self-Interference in
MANATs, Proceedings of the 29th Annual IEEE International
Conference on Local Computer Networks (LCN’04).
[17] Y. Wang and B. Bensaou, Achieving Fairness in IEEE 802.11
DFWMAC with Variable Packet Lengths, IEEE GLOBECOM,
San Antonio, TX, USA (2001).
[18] S. Ye, Y. Wang, and Y. Tseng, A Jamming-Bases MAC Protocol
to Improve the Performance of Wireless Multihop Ad Hoc
Networks, Wireless Communications and Mobile Computing
(2003), 75–84.