1. Introduction
A Mobile Ad hoc Network (MANET) is a wireless network in which nodes communicate without a central base station [1] . Nodes in MANET can be routers, senders and receivers. Moreover, these nodes have different abilities and uses, they also have to find other nodes inside the transmission range to form a network because there are no control dedicated units to manage this connection, and this pattern decreases the cost and the complexity of the MANET [1] . The absence of infrastructure design plays a major role in the wide use of MANET networks in our life [2] . There is no need for a complex base station installation or a wiring design for MANETs which are self-building and self-managing [3] , and depend on Backoff algorithm to control the collisions on the shared media. In this work, we introduce a modification on a HBPB algorithm by using absolute value of (β) in the CW computation; β here represents order of collision and successful transmission in the network. MANET can be used in many useful applications that vary from military communication and commercial environments, to education and home networking [2] .
2. Related Work
Many improved backoff algorithms have been proposed in the literature. Mainly these improvements can be classified into two groups. The first, called BEB-like algorithms and the second group modify the CW size according to some computations made by the station depending on some information collected from its neighborhood [4] .
2.1. BEB-Like Algorithms
This category includes backoff algorithms that have the same basic functionality as BEB, which means that directly after a successful transmission, the CW is decreased, and after a collision, the CW is increased. [5] has proposed the Sensing Backoff Algorithm (SBA), in which nodes overhearing a successful transmission reduce its backoff window by a factor, not only the successful nodes. In MILD algorithm [6] a collided node increases its backoff interval by multiplying it by 1.5. A successful node decreases its backoff interval by one step, and migrate the backoff interval to the nodes overhearing a successful transmission through the nodes in the network which reduce the overall throughput of the network.
In [7] the authors proposed Exponential Increase Exponential Decrease (EIED) backoff algorithm in which the CW changed as follows: CW = min[RI*CW, CWmax] on a collision, CW = max[CW/RD, CWmin] on a success, where RI and RD > 0, here RI, RD calculated using the collision experience of the station, A linear increase/linear decrease (LILD) CW algorithm is proposed in [8] In this algorithm, upon a collision, the current CW is increased by a constant value ω. Upon receiving an ACK, it is decreased by ω with probability 1 − δ and unchanged with probability δ. The parameters ω and δ are set experimentally to constant values, LILD perform better than EIED in large network size, but EIED algorithm is more fit than LILD in fast variation of network load.
In [9] , the authors suggested the Pessimistic Linear Exponential Backoff (PLEB) Algorithm which is a mixture between linear and exponential increment behaviors is recommended, initially the CW increased exponentially so a long waiting time will be before trying the next transmission, after (N) retransmission failure the CW increased linearly, the experiments show that PLEB minimize the average of Packet Delay in dense networks.
Recently in 2014 new Contention Window based Multiplicative Increase Decrease Backoff (CWMIDB) algorithm for the DCF presented in [10] , the main objective of CWMIDB is reducing the number of collisions, since most of the previous algorithms improve the performance of MANETs but actually cause high packet collision rate, the algorithm modify CW size upon a collision depending on (I) which represent retransmission count of a packet as follows, Wi = 2i/2W for even values of i and Wi = 4 × 2 (I − 1)/2W for odd values of I, where W = CWmin.
2.2. Backoff Algorithm Based on Network Status
This group includes algorithms that depend on some computation done by the stations in the network to modify the CW size. In Measurement-based Backoff Fair MBFAIR [11] , the algorithm used some information collected from the neighborhood to compute the fair share that is used to modify the CW size. The Load-based Dynamic Backoff algorithm (LDB) described in [12] change CW size dynamically depending on the expected collision rate as a long-term factor and slot utilization as a short-term factor.
Another mechanism is described in [13] , the authors propose Exponential Linear Backoff Algorithm (ELBA) in which the CW size is changed exponentially and linearly according to the network load, a threshold is set to determine the network load which is specified by the number of collisions. If the CW size is smaller than the threshold, the CW size is adjusted exponentially, and if it is larger than the threshold, the CW size is adjusted linearly, ELBA provides better throughput and collision rate compared with both EIED and LILD algorithm. The History Based Adaptive Backoff algorithm (HBAB) [14] depend on the history of the channel, it means the CW is modified depending on the last N states of the channel whether it is busy or free, (0) indicate a busy channel, (1) for a free channel, and use ß, α as factors to modify the size of CW, this algorithm is very simple and provide a good result in reducing the average of packet delay and enhance the packet delivery fraction compared to the standard BEB.
In [15] , Yang ad Song suggest to modify the backoff time for the node depending on the value of its Acknowledgment (ACK) counter, this counter increase by one each time the node receive an ACK that doesn’t belong to it, and reset to zero if the ACK belong to it, different nodes will have different value of ACK counter after some successful transmissions, the algorithm is called the ACK-based Adaptive Backoff (AAB),which is better than BEB and MILD in the throughput, successful rate and energy efficiency. In [16] the authors proposed an enhancement on Probability Based Backoff algorithm (PBB) [17] by adding ß as a parameter in History Based Probabilistic Backoff algorithm (HBPB) which implements the order of collisions or successful transmissions, while PBB depend on α that indicate the collision rate and the success rate to determine the CW value. HBPB algorithm achieves better result than PBB algorithm in terms of throughput and delay. The next section presents the Backoff algorithm used in this paper
3. History Based Increment Backoff (HBIB) Algorithm
The main target of the proposed algorithm is to improve the throughput and end-to- end delay of the MANET which as a result reflects on its performance, that could be achieved by adjusting the increment/decrement procedure of the CW in the backoff algorithm, let us first describe the basic Binary Exponential Backoff algorithm idea, in BEB the CW is doubled upon a collision until the frame successfully transmitted or reach maximum number of retransmissions, and reset to CWmin which is equal to 31 after successful transmission [16] , the transmission terminated after 16 attempts of transmissions and the maximum CW reached is 1023, BEB results in decreased throughput due to resetting of CW to minimum value at every new transmission. BEB works as described in Figure 1.
The CW in case of collision can be mathematically represented as:
[16] (1)
where α is static and equal to 1.
![]()
Figure 1. Binary exponential backoff algorithm.
In general, when trying to modify BEB the best decision always ignoring too short or too long backoff values, as many researches show that has bad effect on the performance of MANET. In HBPB Algorithm the value of α is diverse dynamically between −1 and 1, and set by the equation,
[16] (2)
P here represent traffic load or collision rate,
[16] (3)
where C stand for number of collisions and S number of successful transmission, the variable β represent order of collision or successful transmission and calculated by
[16] (4)
The ± sign used to specify the transmission whether it is a collision or successful one, variable n represents total number of transmissions, as can be shown in the algorithm the contention window size is not reset for every new transmission; it is hold from the preceding transmission. This can be seen in Figure 2.
![]()
Figure 2. History based probabilistic backoff algorithm.
In the following we explain in details the main modification that we have did on the HBPB to produce the suggested algorithm, followed by the pseudo code.
In HBIB algorithm we modify the increment behavior for the CW after a collision, by adding the absolute value of (β) to P equation as follow:
(5)
To increase the waiting time in case of collision which as a result reduces the contention on the channel and contribute in the increasing of the network throughput, also we modify the CW decrement by ignoring β from P calculation as follows:
(6)
To minimize the CW decrement steps, to assist in avoiding the channel capture effect that gives the node with the minimum CW size the priority to access the channel which as a result increase the network delay
Then α is computed as mentioned earlier by Equation (2), the algorithm is summarized in Figure 3.
![]()
Figure 3. History based increment backoff algorithm.
4. Performance Evaluation and Results
In order to evaluate the performance of the suggested backoff algorithms the Network Simulator (NS) version 2.35 have been used with different MANET scenarios, created by Carnegie Mellon University (CMU)’s [18] traffic-pattern generator script cbrgen.tcl which is used to create a Constant Bit Rate (CBR) traffic connection between wireless mobile nodes to allow very tight control over the bandwidth in use at any moment, and CMU’s node-movement generator script “setdest”, which used Random Waypoint algorithm to create node movements pattern for mobile nodes. Our experiments have been run with the following simulation environment parameters (Table 1).
In this thesis we focus on the throughput and end-to-end delay as a performance metrics, since they have a key effect on the total performance of the network.
4.1. Throughput of the Network
Figure 4 and Figure 5 show how HBIB outperforms HBPB in terms of network throughput with different Packet rates 6, 10 Packets/s respectively and different num- ber of nodes due to the CW increment step which is larger in case of HBIB, and it is
![]()
Figure 4. Simulation result of network throughput versus number of nodes and traffic rate 6 Packets/s.
![]()
Figure 5. Simulation result of network throughput versus number of nodes and traffic rate 10 Packets/s.
known as the increment step increase, the backoff (waiting) time increase which as a result decrease the contention on the channel between the nodes, and increases the throughput of the network.
4.2. End-to-End Delay of the Network
Figure 6 and Figure 7 below illustrate how HBIB algorithm minimizes the network end-to-end delay compared with HBPB algorithm, as the CW decrement steps in HBIB algorithm are smaller than the steps in HPBP algorithm and it is known in backoff algorithms with large decrement steps the nodes will meet faster to the same range of backoff time which increase the contention as a result increase the delay of the network, by the time this could result to what is known as the channel capture effect which give the node with the minimum CW the priority to access the channel, leaving other nodes in the network waiting which as a result increase the network delay.
![]()
Figure 6. Simulation result of end-to-end delay versus number of nodes and a traffic rate of 4 Packets/s.
![]()
Figure 7. Simulation result of end-to-end delay versus number of nodes and a traffic rate of 8 Packets/s.
![]()
Table 1. The simulation environment parameters.
5. Conclusion
In this paper, we have enhanced an existing backoff algorithm called History Based Probabilistic Backoff (HBPB) algorithm which depends on (β) that implements the order of collisions and successful transmission for the backoff time computation. The proposed algorithm HBIB modifies the increment/decrement process by adding the absolute value of (β) to the increment formula and ignores it in decrement process, which attains an increment/decrement steps to improve the performance of the network in terms of throughput and end-to-end delay.