Improved Binary Exponential Backoff Algorithm for fair channel Access in ad hoc Networks
Introduction :
The BEB [binary exponential backoff] algorithm prevents packet collisions during simultaneous access by randomizing moments at stations attempting to access the wireless channels. However, this randomization does not eliminate packet collisions, leading to reduced system throughput and increased packet delay and drop. Also, the BEB algorithm results in unfair channel access among stations.
A mobile ad hoc network is a group of wireless nodes that can dynamically arrange themselves into an arbitrary and temporary topology without the need for a pre-existing infrastructure to form a network. The node may Move dynamically while communicating and makes the node incalculable. The node can leave the topology network briskly. Usually, this network is used in applications such as emergency operations, environmental control, and military applications where there is no centralized network infrastructure management or support, such as routers or base stations. In the IEEE 802.11 standard, the distributed coordination function (DCF) algorithm is an efficient and fundamental algorithm that ensures the best MANET compatibility with evolving topology challenges. Based on the carrier sense multiple access with collision avoidance (CSMA/CA) protocol, the DCF shares access to the medium, which follows the basic principle of ‘listen before talking.’ BEB Algorithm is employed in DCF. After the Collision the node wishing to retransmit wait for a random amount of time which is known as Backoff time. Here, the node having small BT will first access the medium compare to higher BT.
Distributed Coordination Function:
This is used to prevent collision using CSMA/CA and RTS/CTS acknowledgment frames. At the time of transmission Sender waits for DIFS [distributed coordination function interframe spacing ] time if the channel is idle it sends the data frame i.e RTS ACk frame while the receiver waits for the SIFS [short interframe spacing] amount of time and then sends the CTS frame receipt to the sender. If the channel is busy, the station waits for the channel until it is sensed idle for a DIFS time. At this point, it generates random BT to send the data frame.
A. Binary Exponential Backoff Algorithm:
Upon successful data transmission, the function CW() is invoked to adjust the CW to CWmin. During data collisions, the node invokes the function Double CW() to double the CW until it is equal to or greater than CWmax. When the node attempts to send data unsuccessfully seven times, the function CW() is also
invoked to adjust CW to CWmin due to which packet delay and drop increases also reduce the probability of retransmission of the data frames. Also, the fairness problem occurs.
Fairness Problem:
If the Backoff time of Suppose Node A is low as compare to node B then node A will reach zero first and reset the Contention window to Minimum. Due to which the node first transmits have a higher probability of transmitting its node again and again.
Code & Implementation
Create a file let’s say “aaa.txt”. Here, we are using file handling.
In file we are generating the 0’s and 1’s. Here, 0’s means Unsuccessful and 1’s means successful.
aaa.txt:
1010011000100011
CWmin = Min value of Contention Window
CWmax = Max value of Contention Window
Curr_BW = Contention value by user
BT = Backoff time
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
int main(){ float slot_time = 0.00000166; int CWmin = 32, CWmax = 1024; int k;
int i, Curr_BW = 32, counter = 0;
float BT, Total_Backoff_time = 0; FILE* fp;
char* f_name = "aaa.txt";
char ch;
int x = 0, y = 0; fp = fopen(f_name, "r+");
if (fp == NULL) {
printf("%s does not exists \n", f_name);
return;
}
else {
printf("%s: opened in read mode.\n\n", f_name);
} while ((ch = fgetc(fp)) != EOF) { // end-of-file if (ch == '1' || ch == '0') {
printf("frame %c \n ", ch);
} if (ch == '1') { x = x + 1;
printf("successful Transmission\n");
Curr_BW = CWmin;
printf("the current window is : %d\n", Curr_BW); BT = Curr_BW * slot_time;
printf(" =>the backoff time is : %0.8f \n", BT); counter = 0;
}
else if (ch == '0') { y = y + 1;
if (counter < 7) { printf("UNsuccessful Transmission\n"); Curr_BW = Curr_BW * 2; if (Curr_BW > CWmax) { Curr_BW = CWmax;
}
printf("the current window is : %d\n",
Curr_BW); counter = counter + 1;
printf("counter is : %d \n ", counter); BT = Curr_BW * slot_time; printf(" =>the backoff time is : %0.8f \n",
BT);
}
else { Curr_BW = CWmin;
printf("the current window is : %d\n",
Curr_BW); BT = Curr_BW * slot_time;
printf(" =>the backoff time is : %0.8f \n",
BT);
}
} if (ch == '1' || ch == '0') { Total_Backoff_time = Total_Backoff_time + BT; printf("\n");
printf("=> Total Back_off time for frame is : "
" %0.8f \n ",
Total_Backoff_time);
printf("\n\n");
}
} printf(" success num : %d\n", x);
printf(" unsuccess num : %d\n", y); return;
}
B. Improved binary exponential backoff algorithm. [ I-BEB]
To solve the fairness problem among nodes while transmitting up to the point and lowering the packet delay compare to BEB.
Hereafter the 12th time successful transmission the counter is set to 1 and the Contention window is Exponentially increased.
Still, I-BEB doesn’t solve the fairness problem much. Here in this algorithm, we are using threshold value because there can be a scenario where the number of the active station will increase and increase the chances of a collision. when CW is less than the threshold, equals its contention window size to the threshold to increase the probability of successful transmission
C=12, D=4, E=8, and
G=0.125 * CWmin
CWmin = 32 and CWmax = 1024
// C => successful sending times
// D => Quickly decrease the the CW
// E => linearly inc the CW
// G => Threshold quantity
// CW => Minimun Contention Window Size
// BT => Backoff time
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>int main(){
int C = 12, D = 4, E = 8; int counter = 0;
double slot_time = 0.00000166, CW;
int CWmax = 1024, CWmin = 32;
double BT, G, Total_Backoff_time = 0; // C => successful sending times
// D => Quickly decrease the the CW
// E => linearly inc the CW
// G => Threshold quantity
// CW => Minimun Contention Window Size
// BT => Backoff time printf("Enter the Curr_BW (CW) by user : ");
scanf("%lf", &CW); // printf("Enter the CWmax : ");
// scanf("%d" , &CWmax); FILE* fp;
char* f_name = "aaa.txt";
char ch; fp = fopen(f_name, "r+");
if (fp == NULL) {
printf("%s does not exists \n", f_name);
return;
}
else {
printf("%s: opened in read mode.\n\n", f_name);
} while ((ch = fgetc(fp)) != EOF) {
// end-of-file if (ch == '0' || ch == '1') {
printf("frame %c \n ", ch);
} if (ch == '1' || ch == '0') { if (counter < C) { counter = counter + 1;
printf("counter value is : %d\n ", counter);
CW = CW / D;
printf(" The CW is : %0.8f\n", CW); G = 0.125 * CW;
printf("Value of G [Threshold Quantity] is "
": %0.8f\n",
G); if (CW < G) {
CW = G;
BT = CW * slot_time;
printf(
" => The Backoff Time is : %0.8f\n",
BT);
}
else {
BT = CW * slot_time;
printf(
" => The Backoff Time is : %0.8f\n",
BT);
}
}
else {
counter = 1;
CW = CW + (E * CWmin); printf(" The CW is : %lf\n", CW); if (CW > CWmax) {
CW = CWmax; BT = CW * slot_time;
printf(
" => The Backoff Time is : %0.8f\n",
BT);
}
else { BT = CW * slot_time;
printf(
" => The Backoff Time is : %0.8f\n",
BT);
}
}
} if (ch == '1' || ch == '0') { Total_Backoff_time = Total_Backoff_time + BT; printf("\n");
printf("=> Total Back_off time for frame is : "
" %0.8f \n ",
Total_Backoff_time);
printf("\n\n");
}
}
}
