Fairness Improvement of MAC in Wireless Ad Hoc Networks

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 proapproach defines a fairness index and the goal is to tocols [5], [14], [9], [15], where each of the nodes in pmaipneimriwzee pthriospofaseirnaefsasirinnedsesxintdoexacbhyietvaekifnagirninetsos.aicncotuhnist addition to its own packets has to forward packets beboth 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. INTRODUCTION 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 improvto 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 improvethe 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

-

section V, we investigate a scalability study of RAMAC in a wireless ad hoc networks. Section VI gives the conclusion of this work and outlines future work extensions.

II. IEEE 802.11 OVERVIEW

The IEEE 802.11 standard defines two operational modes for wireless LANs networks: infrastructure based and infrastructure-less or ad hoc based modes [ 8 ]. Network interface can be set to work in either of these modes but not in both simultaneously. Infrastructure mode resembles to cellular infrastructure-based mode network (GSM). In the ad hoc mode, any station that is within the transmission range of any other can start communicating. No access point is required, but if one of the stations operating in the ad hoc mode has a connection also to a wired network, stations forming the ad hoc network gain wireless access to the Internet.

The IEEE 802.11 standard specifies a MAC layer and a PHY layer for WLANs. We only consider the MAC layer. The MAC layer offers two different types of service: a contention service provided by the Distributed Coordination Function (DCF), and a contention free service implemented by the Point Coordination Function (PCF).

A. Point Coordination Function

The Point Coordination Function (PCF) is implemented on top of Distributed Coordination Function (DCF) and is based on a polling scheme. It uses a Point Coordination Function that cyclically polls stations, giving them the opportunity to transmit. Since the DCF cannot be adopted in the ad hoc mode, hereafter it will not be considered.

B. Distributed Coordination Function

The Distributed Coordination Function (DCF) provides the basic access method of the 802.11 MAC protocol and is based on CSMA/CA scheme. According to this scheme, when a node receives a packet to be transmitted, it first listens to the channel to ensure no other node is transmitting. If the channel is clear, it then transmits the packet. Otherwise, it chooses a random backoff value which determines the amount of time the node must wait until it is allowed to transmit its packet. During periods in which the channel is clear, the node decrements its backoff counter. When the backoff counter reaches zero, the node transmits the packet. Since the probability that two nodes will choose the same backoff is small, the probability of packet collisions, under normal circumstances, is low.

III. RELATED WORK A large number of random access MAC protocols have been developed to enhance the channel performance and fairness.

MACA [ 10 ] is based on the following principle: When hidden terminals exist, lack of carrier does not always mean it is ok to transmit. Conversely, when exposed terminals exist, presence of carrier dos not always mean it is bad to transmit. MACA proposed to get grid of the CS part in CSMA/CA and extend the CA part. When a station overhears an RTS addressed to another station, it inhibits its own transmitter long enough for the addressed station to respond with a CTS. When a station overhears a CTS addressed to another station, it inhibits its own transmitter long enough for the other station to send its data.

In MACAW [ 3 ] the backoff algorithm was modified by including in the packets header a field which contains the current value of the backoff counter. Whenever a station hears a packet, it copies that value into its own backoff counter. The throughput allocation is now completely fair. The BEB backoff calculation adjusts extremely rapid. To prevent such wild oscillations, MACAW has instead adopted a gentler adjustment algorithm which is called Multiple increase linear decrease MILD. Three additional control packets ACK, DS and RRTS, are used in MACAW to alleviate the effect of hidden terminals, exposed terminals and make error recovery faster.

In [ 7 ], to minimize collisions and maximize channel reutilization, if two flows are contending flows, they are expected not to be scheduled to transmit simultaneously, otherwise, they should eventually transmit simultaneously, they should eventually transmit simultaneously in order to maximize network throughput. In [ 7 ], a flow contention graph G = (N; A) where N is the set of flows and A is the set of edges of the graph (presence of contention), is divided into cliques, where a clique is defined as a subset of N such that for all ditinct pair u; v 2 cl, the edge [u; v] 2 A. By construction of the flow contention graph, and the definition of a clique, any two or more flows that belong to the same clique, cannot be scheduled to transmit simultaneously.

In [ 13 ], a probability based backoff algorithm has been proposed to address the unfairness problem, A fairness index has been introduced to be the ration of maximum link throughput to minimum link throughput. Each node calculates a link access probability for each of its links based on the number of connections from itself and its neighbors, or based on the average contention period of it and other nodes individual links. Whenever its backoff period ends, a node i will send RTS packet to j with probability pij or backoff again with probability 1 pij

In [ 18 ], a JMAC (jamming-based MAC) protocol that is not only free from both the hidden terminal and the erroneous reservation problems but also allows more current transmission/receipt activities for stations within each others transmission range. The idea behind JMAC is to separate source stations traffic from destination stations traffic into different channels, and explicitly signal the channel status by jamming the channel. In JMAC, the medium is divided into two channels: S channel and R channel. RTS and DATA frames are transmitted on the S channel and CTS and ACK frames are transmitted on the R channel. It is assumed that each station is equipped with two radio devices, one tuned to the S channel and the other tuned to the R channel. The ration of bandwidth allocated to the R and S channels is assumed to be : (1 ) where 0 < < 1.

In [ 16 ], a DMAC (Deferrable MAC) protocol that alleviates the hidden terminal problem by deferring further transmissions until the previously transmitted packets travel far enough to avoid interference with the newly transmitted packets.DMAC leverages the observation that for flows that span multiple hops, it is possible to determine how far a packet needs to advance over the multi-hop route before it is possible to transmit a new packet, such that subsequent transmissions of the new and old packets are likely not to interfere with each other.

In [ 2 ], the fairness index is introduced as in [ 13 ] to quantify fairness, and proposes a new estimation based backoff algorithm. The new algorithm can support the case when packets lengths are variable. This work demonstrated that the unfairness problem can be very severe with the original binary exponential backoff algorithm when packet length is variable and that their new backoff algorithm can achieve better fairness.

IV. RAMAC MECHANISM OVERVIEW

To address the problem of efficient bandwidth sharing among all mobile nodes of a wireless ad hoc network. We believe that when a mobile node is participating in routing other nodes packets, it has to access more frequently the channel than one which is not participating in routing packets. Moreover, depending on the amount of data to route, one node may access the channel more frequently than one which has less data to route

In order to succeed in obtaining full nodes cooperation and efficiently share the channel in 802.11 based wireless ad hoc network, we choose to change dynamically the contention window value CW after each unsuccessful transmission. We believe that by doing so, mobile nodes participating in routing other nodes data traffic will not suffer from sending their own traffic. For each node i generating its own traffic and routing other nodes traffic, we define:

Wown(t) : the amount of the own data traffic to send belonging to node i at time t Wrouted(t) : the amount of the routed data traffic to send belonging to node i at time t

i(t) = WownW(tr)o+uWtedr(otu)ted(t) : the ratio of the routed packets of node i at the also the same time t over the total packets.

In the basic DCF scheme in IEEE 802.11 for ad hoc networks, the contention window CW is reset to its minimum value CWmin after each successful transmission and doubled when collision occurs or the medium is sensed to be busy at the end of defer access period. In RAMAC mechanism [ 1 ], [ 11 ], [ 12 ] we propose to this mechanism.

1) CW Decrease In the DCF scheme, after each successful transmission the CW value is reset to its minimum contention window value CWmin, this mechanism is kept invariable since it helps the node to access the medium with a high probability. 2) CW Increase : After each unsuccessful transmission, caused by a contention with another transmitter or a busy medium sensed after a defer access period, the DCF function doubles the contention CW.

CWnew = min(2

CWold; CWmax)

(1) In RAMAC, this mechanism is changed. After each unsuccessful transmission, a mobile node i updates its contention window using a multiplicative factor M Fi. The multiplicative factor M Fi is calculated after each update period (t).

M Fi = 2 i The new CW is then calculated following this equation:

CWnew = min(M Fi

CWold; CWmax)

V. FAIRNESS IMPROVEMENT

In [ 2 ], this following notation is introduced:

i : A predefined fair share that station i should receive. Normally, it should be determined at admission control.

Wi : The actual throughput achieved by station i (2) (3) (4) g

Li : Station i’s offered load.

In [ 2 ], If each station is considered to be a greedy source and wants to get the same share as all other stations as a whole, then it can just set i = 0; 5regardless of the number of its neighbors. As to any station, say i, it requests the same share as all the others in its vicinity. These stations have a total share of 1 i = 0; 5. which equals to this stations share i. This can be interpreted 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 where i is the ratio of routed packets of node i over the total packets. Note that when i = 0, which means that the node i has no packet to route, we obtain i = 0; 5 and when i = 1, which means that the node has only packets to route i = 1, this means that the node gets all the channel for its own use. The more a node has packets to route the more frequently it has access to the channel. We propose a modification in the backoff scheme to take into account the ratio i for any node i in the wireless ad hoc network.

1) CW Decrease : In [ 2 ], the CW is divided by two when the fairness index is lower than a constant value C which is used to adjust the adaptativity of the algorithm. We propose to divide the CW value by a factor of division DF such that

DF = ( CWold )

CWmin

2( 1) (5) The CW decrease function becomes then:

CWnew = max( CDWFold ; CWmin) 2) CW Increase : In [ 2 ], the CW id doubled when the fairness index is higher than the constant value C. We propose to change this by multiplying the CW value with a multiplicative M F such that:

M F = 2 The new CW is then obtained by the following equation

CWnew = min(M F

CWold; CWmax)

With these modifications, the backoff algorithm in [ 2 ] is modified by dividing the CW value by DF instead of 2 and multiplying the CW value by MF instead of the constant value 2. With this estimation, the adjustment of contention window is shown in this algorithm (6) (7) (8) (9) (10) Algorithm 1 the new ajustement of the CW switch(F Ie) f case > C:

CWnew = min(CWold case (1=C; C): F I; CWmax)

CWnew = CWold case < C:

CWnew = max(CWold=F D; CWmin)

Thus the fairness is improved.

3) Proof : In [ 2 ], the goal is to design an algorithm which minimizes the fairness index. The fairness index estimated in [ 5 ] is:

F Ie = ( Wei )=( Weo )

i o Let’s set the i to the constant 0,5. The fairness index becomes then

F Ie =

Wei

Weo i = (1 + i)=2 Let’s calculate the fairness index when we take into account

The fairness index becomes:

Now let’s calculate the amount F Ir=F Ie F Ir = (

Wei )=( 1 + i 1 Weo )

i F Ir=F Ie = 1

i 1 + i Given that F Ir > 0, F Ie > 0 and 11+ ii > 0 We conclude that F Ir < F Ie for any value of Wei and Weo and i. This leads to say that the fairness is improved.

VI. CONCLUSION

In [ 2 ], fairness index is defined and the target to achieve fairness is to minimize this fairness index. In our paper, we proposed a modification to this fairness index so that it takes into account both of own data traffic and routed data traffic. We can easily demonstrate that the fairness index modified is lower or equal than the one defined in [ 2 ]. This leads to say that the fairness is improved.

References

[1] F. Naˆıt Abdesselam , Towards Routing-aware Adaptive Medium Access Control in Wireless Ad Hoc Networks , INTERNATIONAL JOURNAL OF WIRELESS AND MOBILE COMMUNICATIONS ( 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, Massashussets ( 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 Protocol, 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 Magazine ( 1997 ).

[7] X. Huang and B. Bensaou , On Max-min Fairness and Scheduling in Wireless Ad-Hoc Networks , In ACM MobiHoc 01 ( 2001 ).

[8] IEEE, Wireless LAN Medium Access Control (MAC) and Physical 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 Contention 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 .