- Pdf Fibonacci Increment Backoff Algorithm For Machine
- Pdf Fibonacci Increment Backoff Algorithm For Machine Learning
The IEEE 802.15.4 is a standard for Wireless Personal Area Network (PAN) that supports low data rate, low cost, low complexity and low power consumption applications. The CSMA/CA algorithm of the IEEE 802.15.4 MAC layer employs the Binary Exponential Backoff (BEB) function to compute the backoff delay for each node. Using BEB function, it is possible that two or more nodes may collide if they choose the same backoff exponent value. Consequently this will increase collision and network contention level which will degrade the network overall performance. To overcome this problem, this paper proposes a Fibonacci Backoff (FIB) function to compute the backoff interval.
Pdf Fibonacci Increment Backoff Algorithm For Machine
In FIB, each node shall wait for an incremental backoff periods as they need to access the channel. The performance of FIB algorithm is compared against the BEB function. Beaconless modes and supports both star and peer to peer network topologies 2.
802.11 Backoff Algorithms B.Nithya,C.Mala* and Vijay Kumar B Department of Computer Science, NIT, Tiruchirappalli- 620015,India Abstract The Backoff Algorithm is the heart of Medium Access Control(MAC) protocol which determines the system throughput in IEEE802.11 networks. Fibonacci Increment Backoff (FIB) and Pessimistic Linear.
In beacon enabled mode the central coordinator is responsible for sending beacons in order to synchronize nodes 2.Two successive beacons contain between them what is called a superframe 2. This superframe is divided into 16 active period time slots along with an optional inactive period in which all nodes can sleep together in the case that sleep mode is enabled. The active period in turn consists of a Contention Access Period (CAP) and an optional Contention Free Period (CFP) 2.
In order to avoid all nodes transmit at the same time, a commonly followed approach in CAP is the slotted Carrier Sense Multiple Access/ Collision Avoidance (CSMA/CA) mechanism through which nodes. 1 where BE represents the backoff exponent which is needed to find the period through which a node should stay silent aside before trying to assess the mediu m. The value of BE can be initialized to 0, 1, 2 or 3 but the default is set to 3 and in case the channel sensed busy this value shall increase to the maximum value of 5 3.
This backoff delay time along with channel sensing and finally packet transmission are all happen in the backoff period which is bounded by the boundaries of each slot contained in the 16 superframe slots 3. However, following CSMA/CA backoff strategy cannot totally avoid collisions.
This is due to the fact that the backoff period is randomly chosen from the small range of 0-2. 1 and hence, there is a great possibility that more than two nodes pick up or reach the same backoff periods and as the network becomes larger in scale or nodes emit intensive and frequent traffic loads, this case is more likely to happen 3.
Obviously, this situation makes those nodes which become silent for the same backoff periods detect that the availability of free channel simultaneously. As a result, they start emitting data at the same time causing unavoidable collision. This situation leads to retransmission and consequently will degrade power consumption that is a critical constraint in WSN.
This will also affect network throughput which is a result of packet losses, and hence affect net work performance 3. If we analyze the backoff mechanism carefully, we can conclude that the random nature of the binary exponential backoff (BEB) scheme is the main cause of such a problem. Hence, unless a variation to such mechanism is done, the problem will continue to happen. However, many backoff mechanism modifications have been proposed in literature to accommodate and solve such situation, but they all still follow the BEB strategy. Previous works methods vary between changing the value of BEB parameters according to some conditions and improving the channel crier sensing (CCA) schemes 3.
Obviously, the root responsible cause of the problem which is the randomness chosen period from the insufficient distributed numbers in the small range still exists. Hence, a new backoff mechanism is needed that does not depend on random chose of backoff periods. One suggested way to do so is to follow the Fibonacci Increment, a well known mathematical series that is formulated incrementally as each new subsequent number is formulated by adding the direct previous two numbers 4. The incremental behavior of Fibonacci mechanism is inspired from the Fibonacci backoff. Algorithm proposed by Manaseer 4 for IEEE 802.11 standard based networks and avoids two or more nodes to choose the same backoff period and hence avoid collision caused by BEB mechanism 4. The following section gives an overview of some backoff schemes proposed in literature.
The third section clarifies the new FIB algorithm scheme. The fourth section illustrates some basic calculations and t heoretical scenarios.
Simulation set up along with results achieved ar e illustrated in section 5 after which the paper work is concluded in section 6. Lee and Ryu (2011) 5, set the value of BE in the slotted CSMA/CA to an efficient Backoff Exponent (EBE) variable. EBE value is initialized according to the number of nodes in the PAN. As the number of nodes joining the network decreasing, it is rational to lessen the nodes backoff delay periods. This can be accomplished by initializing EBE to the minimum value between macMinBE variable and 2 while the battery life extension (BLE) in the beacon frame is set to 1. On the contrary, collisions and channel contention shall increase as the number of nodes joining the network increases and the need for longer bac koff periods arises.
This can be accomplished by setting EBE to the average of the number of backoff delay periods by the number of nodes which are joining the network. As the value of EBE is set, it is given to BE and nodes backoff according to this value as usual.
Simulation results reveal that adopting EBE increases throughput while decreases energy consumption and network load. Khan et al (2010) 6, proposed the Improved BEB (IBEB) algorithm. IBEB minimizes the possibility that nodes may pick the same BE values and hence waiting for the same backoff time periods.
In 6 nodes uses another value to calculate the backoff periods rather than choosing only BE randomly. They chose Interim Backoff (IB) value between 10% and 40% of the calculated backoff time and they also used the unit Interim Period (IP) to decrease the probability of choosing both BE and IB. Simulation results revealed that IBEB outperforms the BEB scheme when tested on different network load and scale. (2009) 7, proposed a backoff technique named Non- Overlapping Binary Exponential B ackoff (NO-BEB) that aimed at decreasing collision level in large scale P ANs.
Backoff algorithms are one class of collision resolution algorithms used in the medium access control protocol in mobile ad hoc networks. When there are different nodes competing to access a shared channel at the same time, the possibility of collision is highly probable, especially in high traffic load networks.
Collision is considered as the major problem in wireless networks, so the backoff mechanism should be applied in order to decrease the collision and to achieve an efficient use of the shared channel. This paper aims to propose and evaluate a new. Mobile Ad hoc Networks (MANETs) 3, 23 work without requiring any preexisting communication infrastructure. These types of networks gain a high importance and attract attention due to the need of rapid deployment in emergency cases such as military operations, search and rescue operations and disaster recovery that do not have enough time to build an infrastructure.
A MANET is an autonomous system of wireless nodes connected by wireless links. Each node not only acts as a sender or receiver but also as a router in order to convey the packet via intermediate nodes until reach the desired destination (multi-hop technique). These nodes have mobility characteristic that allow forming a dynamic network topology which is highly changeable and random. The occurrence of packets collision is considered as the major problem in wireless networks and this problem is usually tackled by applying backoff mechanisms.
Once the collision has occurred, the collided nodes are needed to defer for a period time which usually refer to as retransmission delay (or backoff) which is usually selected randomly from bounded contention window that has a predetermined lower and upper values. The number of active nodes and traffic load in the network has a direct impact on these values.
As an example CW. Are usually set to 31 and 1023 respectively in IEEE 802.11 DCF, and set to 2 and 1024 respectively in Ethernet 1, 13, 18, 22. This paper is outlined as follows. Section 2 presents an overview of IEEE 802.11 standard. Section 3 displays related works on backoff algorithms. Section 4 describes the proposed algorithm, how it works and presents our experiments that we made in order to choose suitable threshold values for our proposed algorithm. The simulation results for our proposed algorithm are displayed in Section 5.
Conclusion and Future Work are drawn in Section 6. IEEE 802.11 MAC protocol is a widely used standard in Wireless Local Area Network (WLAN) in its both types: Infrastructure-based and Infrastructure-less (Ad hoc) networks 5, 15, 24. The MAC protocol, positioned in data link layer (layer 2 in the ISO OSI reference model) 2, 6, 7, plays a vital role in controlling the access to the shared medium and thus reducing the collision as ca n as possible. This protocol defines two medium access coordination functions called Distributed Coordination Function (DCF) which is used mandatory and Point Coordination Function (PCF) which is used optionally 8, 9. In ad hoc network, IEEE 802.11 MAC Protocol uses the DCF to access shared channel. DCF offers asynchronous feature, contention based, and a distributed access to the channel 10.
In addition, it offers a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism and Request to Send/Clear to Send (RTS/CTS) techniques 7. IEEE 802.11 DCF uses a Binary Exponential. 2 Backoff (BEB) algorithm 8, 11, 12, 21 which uniformly chooses the backoff value from the Contention Window (CW). The BEB algorithm is used in IEEE 802.11 due to its simplicity and good performance in many used scenarios 13, 14, but it suffers from fairness and stability problems. It also achieves low throughput under high traffic load 24.
It works as follows: when a node attempts to transmit the packet, it listens to the channel before that, using a carrier sensing techniqu e. If the channel is idle for duration more than the Distributed Inter-Frame Space (DIFS), the node has a privilege to access the channel and start transmitting. Otherwise, the node waits for a time period of DIFS and the backoff algorithm will be applied.
Each node selects a random amount of time denoted as Backoff time (BO) in the range 0, CW-1 which is uniformly chosen from the contention window. The following equation is used to calculate the backoff time (BO). And SlotTime is the duration of one slot which is equal to 20 µs for DSSS PHY in IEEE 802.11 28. 1 displays the values of exponential increase of CW in BEB Algorithm. At the first transmission attempt of a packet, the minimum contention window size is initially selected by BEB which is equal 31.
The backoff time is randomly selected from the CW to be any value between 1 and CW-1. Upon unsuccessful transmission caused by collision or lost packet, CW becomes double + 1 at each time. The Contention Window can take one of the values 31, 63, 127, 255, 511, 1023. When the contention window reaches its maximum value (1023 in BEB), it remains there until it can be reset due to transmit packet successfully or dropped the packet that exceeds the maximum limit of allowed transmission retries which bounded by m (m=7 for basic access mechanism (long frames) and m=4 for RTS/CTS mechanism (short frames)) 8, 29. There are many backoff algorithms proposed in the literature in order to decrease the collision and to achieve an efficient use of the shared channel. In 19, the authors have proposed Medium Access with Collision Avoidance-Wireless (MACAW) protocol which used a Multiplicative Increase Linear Decrease (MILD) Backoff algorithm.
In the MILD algorithm, the nodes increase their contention window multiplicatively upon collision or failure in transmission and decrease their contention window linearly upon success. This algorithm introduced to address unfairness problem in Binary Exponential Backoff (BEB) algorithm. Manaseer and Masadeh 17 hav e proposed a Pessimistic Linear Exponential Backoff (PLEB) algorithm. This algorithm based on assumption that the failure in transmission process is caused by the congestion in network. It is considered as a result of combination between linear and exponential increment methods. Using these two increment methods will help to achieve the aim of this algorithm in improving the performance of a MANET in terms of network throughput and average packet delay.
Pdf Fibonacci Increment Backoff Algorithm For Machine Learning
By using the linear increment, this algorithm will improve the performance by reducing network delay. On the other hand, using the exponential increment will improve network throughput. Authors in 10, 16 have proposed Fibonacci Increment Backoff (FIB) algorithm and Logarithmic (LOG) Backoff algorithm respectively.
The former algorithm uses a famous math series called Fibonacci Series which aims to reduce the differences between successive contention window sizes, this algorithm achieves a higher throughput when compared with BEB algorithm, the later algorithm uses Logarithmic increments in order to utilize the distribution of random numbers. It achieves a higher throughput and less packet loss. It also achieves stability of network throughput over various speeds of nodes. In 13, Haas and Deng have proposed the Sensing Backoff Algorithm (SBA) in order to utilize the network throughput and fairness issues. This algorithm based on sensing mechanism ( overhearing the channel t o get the neede d information). So, each node changes its backoff interval based on the results of the sensed channel status.
Authors in 14 have proposed linear Multiplicative Increase Linear Decrease (LMILD) Backoff algorithm, in th is algorithm the collided nodes multiplicatively increase their contention. 3 windows, while other nodes overhearing the collision increase their contention window in linear way. Upon a success, all nodes decrease their contention windows in a linear way. In 8, Exponential Increase Exponential Decrease (EIED) backoff algorithm was proposed to improve the performance of the IEEE 802.11 DCF. Upon a c ollision or Failure, nodes ex ponentially increase their contention window and upon a success all nodes exponentially decrease their contention windows. This algorithm surpasses BEB in terms of throughput and delay.
Authors in 15 have proposed Predictive DCF (P-DCF) Backoff algorithm to be used in IEEE 802.11 DCF. This algorithm enables nodes to choose their next backoff times by listening to the channel continuously. It reduces the collision probability and outperforms the BEB algorithm in terms of throughput and delay.