Усовершенствованный алгоритм бинарной экспоненциальной отсрочки для справедливого доступа к каналу в одноранговых сетях

Опубликовано: 14 Сентября, 2022

Алгоритм бинарной экспоненциальной отсрочки предотвращает конфликты пакетов во время одновременного доступа, рандомизируя моменты на станциях, пытающихся получить доступ к беспроводным каналам. Однако эта рандомизация не полностью устраняет коллизии пакетов, что приводит к снижению пропускной способности системы и увеличению задержки и потери пакетов. Кроме того, алгоритм BEB приводит к несправедливому доступу к каналам между станциями.

Мобильная одноранговая сеть — это группа беспроводных узлов, которые могут динамически формировать произвольную и временную топологию без необходимости в уже существующей инфраструктуре для формирования сети. Узел может динамически перемещаться во время связи, что делает узел не поддающимся вычислению. Узел может быстро покинуть топологию сети.

Обычно эта сеть используется в таких приложениях, как аварийные операции , контроль окружающей среды и военные приложения , где нет централизованного управления или поддержки сетевой инфраструктуры , такой как маршрутизаторы или базовые станции. В стандарте IEEE 802.11 алгоритм функции распределенной координации (DCF) — это эффективный и фундаментальный алгоритм, обеспечивающий наилучшую совместимость MANET с постоянно меняющимися топологическими задачами. Основываясь на протоколе множественного доступа с контролем несущей и предотвращением коллизий (CSMA/CA), DCF разделяет доступ к среде, что следует основному принципу «прослушивание, прежде чем говорить». Алгоритм BEB используется в DCF. После коллизии узел, желающий выполнить повторную передачу, ожидает случайный период времени, известный как время отсрочки. Здесь узел с малым значением BT сначала получит доступ к среде относительно узла с более высоким значением BT.

Функция распределенной координации :

Эта функция используется для предотвращения конфликтов с использованием кадров подтверждения CSMA/CA и RTS/CTS. Во время передачи отправитель ожидает время DIFS (межкадровый интервал функции распределенной координации) . Если канал свободен, он отправляет кадр данных, т. е. кадр RTS ACK, в то время как получатель ожидает в течение времени SIFS (короткий интервал между кадрами) , а затем отправляет отправителю подтверждение кадра CTS. Если канал занят, станция ожидает канала до тех пор, пока не будет обнаружено, что он свободен в течение времени DIFS. В этот момент он генерирует случайный BT для отправки кадра данных.

Бинарный экспоненциальный алгоритм отсрочки :

После успешной передачи данных вызывается функция CW() для настройки CW на CWmin. Во время конфликтов данных узел вызывает функцию Double CW() для удвоения CW до тех пор, пока оно не станет равным или больше, чем CWmax.

Если узел семь раз безуспешно пытается отправить данные, также вызывается функция CW() для корректировки CW до CWmin, из-за чего увеличивается задержка и отбрасывание пакетов, а также снижается вероятность повторной передачи кадров данных. Кроме того, возникает проблема справедливости.

Проблема справедливости :

Если время отсрочки предполагаемого узла А мало по сравнению с узлом В , то узел А достигнет нуля первым и сбросит окно конкуренции до минимума, из-за чего первый узел передает с более высокой вероятностью передачи своего узла снова и снова. .

Рассмотрим файл «aaa.txt» . В этом файле сгенерируйте 0 и 1 . Здесь 0 означают неудачу, а 1 - успешно. Ниже приведен текстовый файл:

1010011000100011

Ниже приведена реализация вышеуказанного подхода:

C




// C program for the above approach
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
// Driver Code
int main()
{
    // Slot time
    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+");
 
    // Open File
    if (fp == NULL) {
        printf("%s does not exists"
               " ",
               f_name);
        return 0;
    }
 
    // Otherwise
    else {
        printf("%s: opened in read"
               " mode. ",
               f_name);
    }
 
    // Read characters from the file
    while ((ch = fgetc(fp)) != EOF) {
 
        // End-of-file is reached
        if (ch == "1" || ch == "0") {
            printf("frame %c ", ch);
        }
 
        // If the character is 1
        if (ch == "1") {
 
            x = x + 1;
            printf("successful "
                   "Transmission ");
            Curr_BW = CWmin;
            printf("the current "
                   "window is : %d ",
                   Curr_BW);
 
            BT = Curr_BW * slot_time;
            printf(" =>the backoff"
                   " time is : %0.8f"
                   " ",
                   BT);
 
            counter = 0;
        }
 
        // If the character is 0
        else if (ch == "0") {
 
            y = y + 1;
            if (counter < 7) {
 
                printf("UNsuccessful "
                       "Transmission ");
 
                Curr_BW = Curr_BW * 2;
 
                if (Curr_BW > CWmax) {
 
                    Curr_BW = CWmax;
                }
                printf("the current "
                       "window is :"
                       " %d ",
                       Curr_BW);
 
                counter = counter + 1;
                printf("counter is  :"
                       " %d ",
                       counter);
 
                BT = Curr_BW * slot_time;
 
                printf(" =>the backoff"
                       " time is : %0.8f"
                       " ",
                       BT);
            }
 
            // Otherwise
            else {
 
                Curr_BW = CWmin;
                printf("the current"
                       " window is :"
                       " %d ",
                       Curr_BW);
 
                BT = Curr_BW * slot_time;
                printf(" =>the backoff"
                       " time is : %0.8f"
                       " ",
                       BT);
            }
        }
 
        if (ch == "1" || ch == "0") {
 
            // Find the Backoff Time
            Total_Backoff_time = Total_Backoff_time + BT;
 
            printf(" ");
 
            // Print the time
            printf("=>  Total Back_off"
                   " time for frame is : "
                   " %0.8f ",
                   Total_Backoff_time);
            printf(" ");
        }
    }
 
    // Print the success and
    // unsuccess number
    printf(" success num : %d ", x);
    printf(" unsuccess num : %d ", y);
 
    return 0;
}

Входной файл:

1010011000100011

Выход:

Уточненный и улучшенный алгоритм бинарного экспоненциального отката :

Этот алгоритм (также называемый в этой статье I-BEB) направлен на решение проблемы равноправия между узлами при передаче до точки и снижении задержки пакетов по сравнению с BEB.

После 12 успешной передачи счетчик устанавливается на 1 , и окно конкуренции экспоненциально увеличивается. Тем не менее, I-BEB не решает проблему справедливости. Здесь в этом алгоритме используется пороговое значение, потому что может быть сценарий, при котором количество активных станций будет увеличиваться и увеличивать вероятность столкновения. Когда значение CW меньше порогового значения, оно приравнивает размер своего конфликтного окна к пороговому значению, чтобы увеличить вероятность успешной передачи.

C = 12, D = 4, E = 8, and G = 0.125 * CWmin
CWmin = 32 and CWmax = 1024

where, 
C => Successful sending times
D => Quickly decrease the CW
E => Linearly increase the CW
G => Threshold quantity
CW => The minimum contention window size
BT => Backoff time

Ниже приведена реализация вышеуказанного подхода:

C




// C program for the above approach
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
// Driver Code
int main()
 
{
    int C = 12, D = 4, E = 8;
 
    int counter = 0;
 
    // Slot time
    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 CW
    // E => linearly inc the CW
    // G => Threshold quantity
    // CW => Minimum Contention Window Size
    // BT => Backoff time
 
    // Enter the current BW
    printf("Enter the Curr_BW (CW)"
           " by user  :  ");
    scanf("%lf", &CW);
 
    FILE* fp;
    char* f_name = "aaa.txt";
    char ch;
 
    // Open the file
    fp = fopen(f_name, "r+");
 
    // If file doesn"t exists
    if (fp == NULL) {
        printf("%s does not exists"
               " ",
               f_name);
        return 0;
    }
 
    // Otherwise
    else {
        printf("%s: opened in read"
               " mode. ",
               f_name);
    }
 
    // Read character by characters
    while ((ch = fgetc(fp)) != EOF) {
 
        // End-of-file
        if (ch == "0" || ch == "1") {
            printf("frame %c ", ch);
        }
 
        if (ch == "1" || ch == "0") {
 
            if (counter < C) {
 
                // Print the counter
                // value
                counter = counter + 1;
                printf("counter value"
                       " is : %d ",
                       counter);
 
                CW = CW / D;
                printf(" The CW is :"
                       " %0.8f ",
                       CW);
 
                G = 0.125 * CW;
                printf("Value of G "
                       "[Threshold Quantity]"
                       " is : %0.8f ",
                       G);
 
                if (CW < G) {
                    CW = G;
                    BT = CW * slot_time;
                    printf(
                        " => The"
                        " Backoff Time"
                        " is : %0.8f ",
                        BT);
                }
                else {
                    BT = CW * slot_time;
                    printf(
                        " => The "
                        "Backoff Time"
                        " is : %0.8f ",
                        BT);
                }
            }
            else {
                counter = 1;
                CW = CW + (E * CWmin);
 
                printf(" The CW is :"
                       " %lf ",
                       CW);
 
                if (CW > CWmax) {
                    CW = CWmax;
 
                    BT = CW * slot_time;
                    printf(
                        " => The "
                        "Backoff Time"
                        " is : %0.8f ",
                        BT);
                }
                else {
 
                    BT = CW * slot_time;
                    printf(
                        " => The "
                        "Backoff Time"
                        " is : %0.8f ",
                        BT);
                }
            }
        }
 
        if (ch == "1" || ch == "0") {
 
            // Find the Backoff time
            Total_Backoff_time = Total_Backoff_time + BT;
 
            printf(" ");
 
            // Print the Back Off Time
            printf("=>  Total Back_off"
                   " time for frame is : "