An Improved Exponential Algorithm for MAC 802.11 Protocols in MANET

An Improved Exponential Algorithm for MAC 802.11 Protocols in MANET

Vaishali Tiwari Student M.Tech. CSE BIST Bhopal

Prof. Damodar Tiwari M.Tech. CSE BIST Bhopal

Prof. Vijay Lokhande M.Tech. CSE BIST Bhopal

Abstract

A MANET is an ever-changing dynamic wireless network established by a group of mobile users needs not necessarily taking any pre-existing infrastructure or using any centralized administration. These networks are very useful in disaster recovery situations like in military use, in commercial sectors like in case of floods and earthquakes, for Personal Area Network connecting PDAs, laptops and cellular phones and etc. A significant number of researchers have move towards studying MANETs and its various characteristics out of its increasing importance in terms of user mobility and establishing ad-hoc network in emergency situations. The shared media used by wireless network, grant exclusive rights for a node to transmit a packet. Access to this media is controlled by Media Access Protocol. The back-off mechanism is basic part of MAC protocol. Since only one transmitting node uses the channel at any given time, the MAC protocol must suspend other nodes while the media is busy. The major problem with available wireless network is collision and slow collision resolution when the number of station increases. Whenever node access channel the outcome occurs in two cases either successful transmission or collision. The problem with original MAC protocol is its static behaviour. It means at each collision its waiting time increases exponentially and at each successful transmission its waiting time decreases one slot a time. In our proposed we modify the existing back-off algorithm and working of channel access mechanism and proposes an enhanced adaptive MAC

protocol for wireless LAN and compare the performance of enhanced adaptive 802.11 MAC protocol with original 802.11 MAC protocol.

1. Introduction for MANET

   During the last few years, we have all witnessed a continuously increasing growth in the deployment of wireless and mobile communication networks. The growth in the use of wireless communication over the last few years is quite substantial and as compared to other technologies, its huge. The primary advantage of a wireless network is the ability of the wireless node to communicate with the rest of the world while being mobile. Two basic systems have been developed for the wireless network one is fixed infrastructure and the other is, Mobile Ad-hoc Network. MANETs is self configuring network and are easily deployed anywhere without the need of any fixed infrastructure. It is an autonomous terminal in which all mobile nodes are connected through wireless links. In MANETs all mobile nodes are act as a router at the same time; it means all nodes can exchange information without the need of any central coordinator. It is useful in situation where infrastructure is absent, destroyed or impractical. Less expensive infrastructures and quick distribution of information around sender are the key advantages of MANET. There are some applications where MANETs

   1. are mostly used are as:

      1. In Military use (e.g. a network in battlefield).

      2. Commercial sectors (e.g. in case of flood or earthquake).

      3. Local level (in classrooms or conference).

      4. Vehicle to vehicle communications.

      5. Personal Area Network for connecting laptops, PDAs and cellular phones.

   1. MANET Features

      MANET has the following features [1]:

      1. Autonomous terminal: in MANET, each mobile terminal is an autonomous node, which may function as both a host and a router.

      2. Distributed Operation: since there is no background network for the central control of the network operations, the control and management of the network is distributed among the terminals.

      3. Multihop Routing: basic types of ad-hoc routing algorithm can be single-hop and multi- hop, based on different link layer attributes and routing protocols.

      4. Dynamic Network Topology: since the nodes are mobile, the network topology may change rapidly and unpredictably and the connectivity among the terminals may vary with time. MANET should adapt to the traffic and propagation conditions as well as the mobility patterns of the mobile network nodes.

      5. Fluctuating Link Capacity: the nature of high bit-errors rates of wireless connection might be more profound in a MANET.

      6. Light Weight Terminals: in most cases, the MANET nodes are mobile devices with less CPU processing capability, small memory size, and low power storage.

2. The Role of MAC in MANET

   As we know, the collision is quickly detected during transmission in wired network, because of collision detection technique available in Ethernet [3]. In contrast, a transmitter cannot detect its collision during transmission in wireless network rather it relies on the receivers acknowledgement to determine if there is any collision has taken place in the transmitting duration. Clearly the resulting collision period is quite long and it is unaffordable if long data transmission encounters collision. In this regard how to effectively reduce collision become a key issue for MAC design in MANET.

   Several mechanisms have been proposed to avoid collision like carrier sense mechanism, multiple handshakes and back-off mechanism. Carrier sense required that a node transmit only when the channel is determined idle. Handshakes between sender and receiver include some short frames to avoid long collision period of data packet and acknowledgement of successful transmission.

   The Back-off mechanism forces each node to wait a random period before attempting any transmission. In the following we discuss some mechanism in the context of the IEEE 802.11 DCF protocol.

   1. The IEEE 802.11 DCF is a contention based protocol. To reduce the collision possibility, it uses carrier sense functions and binary exponential back-off mechanism [4]. In particular two functions are used in carrier sense function i.e. virtual and physical which is used to determine the state of the medium. The former is provided by the physical layer and later is by the MAC layer, which is also referred to as the network allocation vector (NAV). NAV predicts the duration that the medium will be busy in the future based on duration information announced in transmitted frames. When either function indicates a busy medium, the medium is considered busy otherwise it is considered idle. In the BEB mechanism each node selects a random back-off time uniformly distributed in [0, CW], where CW is the current contention window size. It is decreases by one slot a time in case of successful transmission or in case of idle channels. Transmission shall commence whenever back-off timer reaches zero. When there is collision occur during transmission or in case of transmission fails, contention window increases twice until it reaches a maximum value CWmax. Then node starts back-off process again and retransmit packet when back-off process is complete. If the maximum transmission failure limit is reached then retransmission shall stop, CW shall be set to its initial value CWmin, and packet shall be discarded.

   2. Carrier sense Mechanism [4]: In this mechanism a node determines the channel is busy when the received signal power exceeds a certain threshold referred to as carrier sense threshold (CST). Otherwise, the channel is determined idle. It can be seen clearly that the value of CST decide the sensing range and affects both the collision possibility and spatial reuse in MANETs. The larger the sensing range, the smaller the possibility that a new transmission attempts interferes with

      some ongoing transmission. On the other hand, a larger sensing range implies that more nodes have to defer their transmission when one node is transmitting, which leads to poorer spatial reuse.

   3. Back-off Mechanism: although BEB is widely used in many contention based MAC protocols for its simplicity and good performance, it suffers from both fairness and efficiency [4]. In BEB, each station resets its CW size to the minimum value after a successful transmission, and doubles its CW after a failed

   Distributed Coordination Function

   MAC

   Point Coordination Function

   Required for contention free service

   Used for contention services and basis for PCF

   transmission. Therefore, it might be quite likely that a node that has gained the channel and transmitted successfully. The worst case scenario is that one node monopolizes the channel while all other nodes are completely denied channel access. On the other hand, BEB is also diagnosed from low efficiency when there are many active nodes.

   Medium Access Channel data communication protocol sub-layer provides addressing and channel access mechanism that make it possible for all the nodes to access common wireless channel through Distributed Coordinating Function. DCF provides two access mechanism one is two way handshake i.e. ACK/DATA and the other is four way handshake which includes RTS/CTS/ACK/DATA. When the size of data packet is large then it includes some short frames to avoid long collision period of data packet. The DCF and PCF work as two main component of MAC protocol, DCF is basic medium access method it can be used for both infrastructure based and infrastructure less network. Since its own station cannot hear its own transmission, hence DCF using CSMA/CA to avoid collision. Whereas PCF (point coordination function) used only in infrastructure based network. This is beneficial for time bound applications such as video or voice. MAC sub-layer architecture is given below in figure 1 shown as two components DCF and PCF [5].

3. Related Work

   There are lots of researches discussing new back-off mechanism to enhance MAC protocols are given below:

   Figure 1: MAC Sub-Layer Architecture

   S. Manaseer, M. Ould Khaoua and L.M. Mackenize in [6] introduce Fibonacci back-off algorithm for mobile ad-hoc networks. A backoff algorithm called Fibonacci Alorithm called Fibonacci Increment Backoff algorithm was proposed to reduce the differences among successive contention window sizes. Results from simulation revealed that Fibonacci Increment Backoff algorithm achieves a higher throughput than the Binary Exponential Backoff algorithm used in MANETs.

   N. Song [7] enhanced the Distribution Coordination Function with an exponential increase and exponential decrease backoff algorithm. Whereas also studied the effect of increasing and decreasing the waiting time intervals using exponential backoff algorithm. Results representing the exponential increase algorithm have good results using the coordination function.

   J. Deng et al [10] proposed the Linear Multiplicative Increase and Linear Decrease (LMILD) Backoff algorithm. This algorithm had shown a best performance and aims to achieve best Contention Window (CW) size. If failure transmission occurs it uses a factor multiplicative and linear increment. Firstly multiplicative the contention window by colliding nodes when there is a collision, other nodes hearing this collision makes a linear increment to their contention window. On the other hand all nodes decrease their contention window linearly when there is a transmission success.

   C. Rama Krishna, Saswat Chakrabarti and debasish Datta [8] in this research the Medium Access Protocol (MAC) in IEEE 802.11 wireless LAN employs Distributed Coordination function (DCF) with Binary Exponential Backoff Algorithm for contention resolution. With BEB waiting time gets doubled after every collision. This introduces fast-growing retransmission delays for the backlog traffic. In MANET it would be worthwhile to slow down the

   growth rate of waiting time. This is expected because the nodes communicating in MANET might move out of collision range while waiting for retransmission. In this paper they explore a modification to BEB algorithm and evaluate its performance through extensive simulation. Simulation results indicate that the proposed to BEB enhances packet delivery rate and reduces average end-to-end packet delay.

   Mannu J. Pillai, M P. Sebastian and S. D. Madhukumar [9] in this paper, survey of the MAC approaches for wireless and MANET is presented. In general as MAC level throughput is increases, the energy efficiency also increases due to decrease in the number of frame retransmission. However the approach using directional antennas results in more power consumption. But the use of power efficient MAC protocol increases the overall efficiency of a MANET by saving per node energy consumption. Persistence in transmission increases the maximum throughput, but the throughput stability may decrease. QoS assurance to the real time flows can be provided through increased persistence. By this survey we studied the MAC approaches for wireless network and the use of power efficient MAC protocol increases the overall efficiency of MANET.

4. Proposed Methodology

   1) Fibonacci Increment
   2) Logarithmic Decrement
   3) Fibonacci increment	and	Logarithmic
   decrement
   4) Fibonacci increment	and	Exponential
   decrement

   As we know, in Ad-hoc network MAC protocol is used for improving the performance of existing network and for better results. The distributed coordination function is used in wireless network for the best performance and the role of Backoff algorithm is crucial in ad-hoc network for the performance. When nodes want to access the channel back-off algorithm is executed while backoff timer value depends on random number. So it is very difficult to predict back-off duration accurately. The channel allocation method used BEB algorithm to send data, in case of sending data if acknowledgment not received it means collision is occur at channel and after collision all the involving nodes increases their contention window twice, if there is no collision means in case of successful transmission waiting time decreases by one slot a time. In our proposed we modify back-off procedure and working of channel access mechanism. In our proposed algorithm we defined four different scenarios over existing protocol.

   1. Fibonacci Increment: in this approach we proposed a new back-off procedure means channel is allocated as per new Fibonacci back-off , whenever collision occur at channel the channel allocation method allocate channel by Fibonacci based mathematical function. For e.g. in case of 3 collision the back-off time

      In actual BEB: 23= 8= (0, 1, 2, 3, 4, 5, 6, 7)

      In proposed Fibonacci: f (3) = (0, 1, 1, 2)

      Here, we can see that in actual case or waiting time increases 8 times whereas in proposed waiting time increases 4 times means it is very clear in proposed method waiting time increases slowly as compared to original algorithm. Flow chart (1) is given below:

   2. Logarithmic Decrement: in this method we proposed a new plan in which we will work over channel when it is continuously idle means if we detect continuously idle channel then we call logarithmic algorithm to reduce waiting time so that waiting time reduces logarithmic manner rather reduces one slot a time in actual algorithm. For e.g. in our case it is 5 idle slots

      In actual BEB: each time WT decreases by one slot a time at each successful transmission even if we detect Free channel continuously, like if WT =512 means node have to wait 512 slot time.

      Flowchart 1: Fibonacci MAC Protocol

      In proposed Logarithmic: if (idle slot ==5)

      Then log2 (WT) = new (WT) End if

      e.g. if (idle slot == 5) Then

      Log2 (512) = 9

      End if Therefore WT = 9.

      Here we observed that waiting time reduces fast compared to decreases by one slot a time in original BEB. Flowchart 2 of this method is given below.

   3. Fibonacci Increment and Logarithmic Decrement: in this approach we are using the combination of both method discussed above means, Fibonacci used for increment and Logarithmic used for decrement purpose. Whenever collision occurs at channel we call Fibonacci algorithm to calculate back- off time and then send data for next transmission whereas in case of successful transmission or detection of continuously 5 idle slots we call Logarithmic function to calculate Back-off time. Here we proposed a new protocol i.e. FiLog means slow increment and fast decrement. Flowchart 3 of FiLog is given below

      Flowchart 2: Logarithmic MAC Protocol

      Flowchart 3: FiLog MAC Protocol

   4. Fibonacci Increment and Exponential Decrement: in this method we used the combination of Fibonacci and Exponential method. As we observed Fibonacci gives better results for increment purpose and exponential function can give better results for decrement purpose. Here we proposed a new protocol

      i.e. FiExpo in case if acknowledgement not received then contention window size increases in Fibonacci manner and in case of free channel detection or successful transmission window size decreases by exponential function.

5. Simulation Tool

   To test the new protocol we used NS2 (Network Simulator 2) and compare the performance of proposed protocol with conventional protocol. Simulation is the fundamental tool in the development of MANET protocol, because the difficulty to deploy and debug them in real network. The simulation eases the analysing and the verification of the protocols mainly in large scale system. NS2 is an open source event- driven simulator designed specifically for research in computer communication networks. Simulator will be run for conventional protocol and then will be run for proposed protocol under the same environment to see the performances differences.

   Table 1: Simulator Parameters

   Type	Values
   Channel	Channel/wireless channel
   Radio Propagation Model	Propagation/tworayground
   Network Interface	Physical/Wirelessphy
   MAC	MAC 802_11
   Interface queue	Queue/drop tail/priqueue
   Antenna	Antenna/Omni antenna
   Link Layer	LL
   Interface Queue Length	50
   Routing Protocol	AODV
   Simulation Time	100s
   Number of Mobile Nodes	10

6. Results

   1. Original MAC Protocol: below graph in figure 1 shown original BEB Algorithm against packet transmits, lost and received.

   2. Proposed Fibonacci MAC Protocol: in figure 2 graph shown the results of Fibonacci MAC where we are getting better results compared to original BEB i.e. because of slow increment in waiting time in case of collision.

      Figure 1: Original BEB Algorithm

      Here blue line show Packet transmit, Green line show Packet lost and red line show Packet received in all the graphs.

      Figure 2: Fibonacci MAC Protocol

   3. Proposed Logarithmic MAC Protocol: in figure 3 graph shown the results of proposed Logarithmic MAC protocol.

      Figure 3: Logarithmic MAC Protocol

   4. Proposed FiLog MAC Protocol: in figure 4 graph shown the results of FiLog protocol where we get better results than original protocol because of using

      the combination of Fibonacci and Logarithmic function.

      Figure 4: FiLog MAC Protocol

   5. Proposed FiExpo MAC Protocol: graph shown in figure 5 the results of FiExpo Protocol in which we used the combination of Fibonacci and exponential function.

      Figure 5: FiExpo MAC Protocol

7. Conclusion

   As we have discussed our proposed will improve the performance of existing work. We analyze the existing work with multiple combination of proposed work. We used different mathematical function like Fibonacci, Logarithmic and Exponential function to explore the performance of the current Medium Access Protocol (MAC). As per algorithms and results we have shown that the proposed work gives better results than original work. As in future if the loads were unpredicted or there are less number of competitive node we can use our proposed algorithm for better efficiency and result.

8. Future Enhancement

   As far as future work is concerned we can use different randomization function to change the behaviour of the waiting and can improve the performance of the network, we can also use the Markov model and Data Mining algorithm to prepare the test cases that directed the network load and behaves dynamically as per load and need.

9. References

1. G.V.S. Raju and G. Hernandez, Routing in ad-hoc networks proceedings of the IEEE SMC International Conference, October 2002.

2. IEEE 802.1I Working group. http:/www.mantaa.ieee.org/groups/802/1/I

3. Hongiang Zhai, Jianfeng Wang and Yugang Fang Medium Access Control in MANET: Challenges and Solutions 14th IEEE International Symposium on personal, indoor and Mobile Radio Communication, Beijieng China, September 2003.

4. V. Bhargavan., A. Demers, S. Shenker, and L. Zhang MACAW: A Media Access Protocol for Wireless LAN: proc. ACM SIGCOMM 1994 pp 212-225.

5. G. Bianchi Performance Analysis of the IEEE 802.11 Distributed Coordinating Function IEEE Communication Letters vol. 2 December 1998.

6. S. Manaseer, M. Ould-Khaoua and L.Mackenize Fibonacci Back-off Algorithm for Mobile ad-hoc Network the 7th annual postgraduate symposium on convergence of telecommunications. Networking and Broadcasting Liverpool 2006.

7. N. Song Enhancement of IEEE 802.11 Distributed Coordinating Function with exponential increase and exponential decrease algorithm. IEEE 57th Annual.

8. C. Ramakrishna, Saswat Chakrbarti and Dabasis Data A Modified Back-off Algorithm for IEEE 802.11 DCF based MAC protocol in MANET IEEE 2004.

9. Mannu J. Pillai, M. P. Sebastian, S.D. Madhukumar A Survey of MAC Protocol for MANET ISO2 2011

10. J. Deng and Z. Haas A new back-off algorithm for IEEE 802.11 Distributed Coordinating Function Communication Networks and Distributed system modelling and simulation (CNDS 04) California 2004.

11. Effect of Exponential Back-off Algorithm in MACA and MACAW for MANETs- A Study vikas kumar singh, sujata singh, lekhika chetri and biswaraj sen International Journal of Latest Trends and Engineering Technology in 2012

12. NS-2 Simulator, at http://www.isi.edu/nsnam/ns/.