Fibonacci Backoff Algorithm for Mobile Ad Hoc Networks

Fibonacci Backoff Algorithm for Mobile Ad Hoc Networks Saher S Manaseer Mohamed Ould-Khaoua Lewis M Mackenzie Department of Computing Science University of Glasgow, Glasgow G12 8RZ, UK {saher, mohamed, lewis}@dcs.gla.ac.uk

Abstract- The collision probability in the MAC layer could become very high when a poor backoff algorithm is used, especially in dense networks. The Binary Exponential Backoff (BEB) used in the IEEE 802.11 MAC protocol uses a uniform random distribution to choose the backoff value. This often leads to reducing the effect of window size increment. This paper proposes a new backoff algorithm called “Fibonacci Increment Backoff (FIB)” in which the differences between consecutive contention window sizes are reduced. Results from simulation experiments reveal that the proposed algorithm achieves higher throughput than the BEB when used in a mobile ad hoc environment.

Keywords IEEE 802.11, Ad hoc networks, Medium access control, Backoff algorithm, Throughput analysis.

I. INTRODUCTION Since their emergence, wireless networks have become increasingly popular in the computing industry. This is particularly true within the past decade, which has seen wireless networks being widely adopted to enable mobility. Over the development process of computer networks, two main variations of mobile wireless networks have been introduced, infrastructure and ad hoc wireless networks [10].

Recently, a significant number of researchers have moved towards studying Mobile Ad Hoc Networks (MANETs). Interest in MANETs is due to many new characteristics provided only by this type of networks. Firstly, MANETs are easily deployed allowing a plug-and-communicate method of networking. Secondly, MANETs need no infrastructure [7], eliminating the need for an infrastructure reduces the cost of establishing the network. Moreover, such networks can be useful in disaster recovery where there is not enough time or resources to install and configure an infrastructure. Thirdly, MANETs also do not need central management. Hence, they are used in military operations where units are moving around the battlefield and a central unit cannot be used for synchronization [7].

Nodes forming an ad hoc network are required to have the ability to double up as a client, a server, and a router simultaneously [7]. Moreover, these nodes should also have the ability to connect to and automatically configure to start transmitting data over the network. As a result of having the characteristics mentioned so far,, protocols used for ad hoc networks generally function in a distributed manner [12]. The distributed Coordination Function (DCF) is used for synchronous, contention-based, distributed access to the channel [3]. MANETs use a shared medium to transfer data between its nodes.

It is impractical to expect a MANET to be fully connected, where a node can directly communicate with every other node in the network. Typically, nodes are obliged to use a multihop path for transmission, and a packet may pass through multiple nodes before being delivered to its intended destination.

The wireless medium used by MANETs has a number of problems. Bandwidth sharing, signal fading, noise, interference, etc…. with such a public medium, a well-organized and effective Medium Access Control (MAC) is indispensable to organize sharing the scarce bandwidth resource [4] [7]. Based on the features mentioned, the design of the medium access control (MAC) protocol is a significant factor affecting the performance of MANETs.

Many researchers have proposed the mechanism of channel sensing, or packet sensing to avoid collision. The sensing mechanisms typically rely on the transmitter and receiver performing a handshake prior to the transmission of the data packet [2]. More specifically, The Medium Access Collision Avoidance (MACA) method proposed by Karn [11] implements the handshake via a pair of Request-To-Send (RTS) and Clear-To-Send (CTS) messages. When a node has to send data to another, it first sends a short RTS to the destination. The receiver responds with a CTS packet [2]. On receipt of the CTS, the sender

1sends its queued data packet(s). All other nodes overhearing the CTS message will defer from sending out any packet until the predicted transmission period indicated in the CTS packet, is passed. Any node that overhears the RTS signal but not CTS is allowed to send out packets in a certain time period as either the RTS/CTS handshake is not completed or it is out of range of the receiver.