LoginSignup
0
0
@Yuta_Nakamura_(Yuta Nakamura)

pureALOHA方式の実装

Last updated at Posted at 2023-11-03

概要

  • メディアアクセス制御方式の一つ
    • 1つの伝送媒体(メディア)を複数の端末が共有
      しているときに、パケットの衝突を減らして効率
      よくデータを転送するための方式

特徴

  • 送信端末にパケットが到着すると、送信端末
    はすぐにそのパケットを送信
  • パケットの衝突が発生した場合は、ランダム
    に求めた時間が経過してから再送

パラメータ

  • 伝送帯域: 4.8 kbps
  • パケット長: 256 byte
  • 端末数: 10
  • パケット送信時間 ＝ パケット長/伝送帯域
    • 伝播遅延時間は無視
  • パケットの再送に関するパラメータ K：100
  • 再送回数の上限値: 3
  • シミュレーション時間: 100000 [s]
  • 各送信端末へのパケット到着：率λのポアソン到着
    • 間隔: -1 * (1/λ) * log (1-r)
      • r: 0以上1未満の一様乱数

シミュレーション

  • 入力
    • パケットの到着率(λ)
  • 出力
    • スループット
      • 単位時間あたりの送信成功パケットサイズと伝送帯域の比率

コード

#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>

/* 固定パラメータ */
#define BAND (double)4800   // 伝送帯域(bps)
#define P_LENGTH 256 * 8    // パケット長(bit)
#define T (P_LENGTH / BAND) // パケット送信時間
#define TERMINAL_NUM 10     // 端末数
#define K 100               // パケットの再送に関するパラメータ
#define RETRY  3            // 再送回数の上限値
#define TIME 100000         // シミュレーション時間
#define SIZE 20             // スループットデータの個数
#define RAMDA_MAX 0.1       // 到着率の上限
#define RAMDA_WIDTH 0.01    // 到着率の間隔

/* イベントの種類 */
#define ARRIVE_SEND 1       // 到着＆送信
#define SEND_COMPLITE 2     // 送信完了
#define RESEND 3            // 再送

/* イベントを表現する構造体 */
typedef struct event{
  int eventNo;           // イベントの種類
  int terminalID;        // どの端末か
  double generationTime; // イベントの発生時刻
  int resend;            // 再送回数
  int packetID;          // パケットの識別子 
  int collision;         // 衝突したか
  struct event *next;
}Event;

/* プロトタイプ宣言 */
double frand(void);
double getArriveInterval(double);
double pureALOHA(double);
void insert(Event **, Event *);
Event *make(int, int, double, int, int);
Event *pushList(Event **);
void collision(Event *, int);
void freeList(Event **);
void printThroughput(double, double, int, double[]);

int main()
{
    double ramda;            // 率λのポアソン到着
    double throughput[SIZE]; // スループットデータを格納する配列
    int i;

 
    srand(time(NULL));

    // ポアソン到着を0.01刻みで増やしながらシミュレーションを実行する
    for (ramda = 0.01, i = 0; i < SIZE; i++, ramda += 0.01)
    {
        // 各ポアソン到着に対するスループットを配列に格納
        throughput[i] = pureALOHA(ramda);
    }

    // スループットを表示
    printThroughput(0.01, RAMDA_WIDTH, SIZE, throughput); 
    getchar();
    return 0;
}

// pureALOHAをシュミレーションする関数
double pureALOHA(double ramda)
{
    Event *list;             // リスト用
    Event *new;              // 新しいイベント用
    Event *now;              // 現在のイベント用
    int i;                   // ループ用
    int packetID;            // 何個目のパケットか
    int success;             // 送信成功したパケットの数
    int occupiePacketID;     // 回線を占有しているパケットのID

    // イベントリストを空に初期化
    list = NULL;

    // 回線を未使用に初期化
    occupiePacketID = 0;

    // パケットIDの初期化
    packetID = 1;
 
    // 送信成功パケット数の初期化
    success = 0;

    // イベントの初期化
    for (i = 0; i < TERMINAL_NUM; i++)
    {
        // 各端末の最初のパケット到着＆送信イベントを作成
        if ((new = make(ARRIVE_SEND, i + 1, getArriveInterval(ramda), 
             packetID, 0)) == NULL)
        {
             fprintf(stderr, "make() errror \n");
             return -1;
        }
        packetID++;
        insert(&list, new);
    }  
                         
    while (1)
    {
        // イベントリストの先頭イベントを取り出す
        now = pushList(&list);

        // シミュレーション時間を過ぎていたら
        if (TIME <  (now -> generationTime) )
        {
            // シミュレーションの時間を超えたため終了
            free(now);
            break;
        }
     
        // 1 パケット到着＆送信イベントなら 
        if (now -> eventNo == ARRIVE_SEND)
        {
            // 回線が未使用ならば 
            if (occupiePacketID == 0)
            {
                // 次のパケット到着＆送信イベントを登録 
                if ((new = make(ARRIVE_SEND, now -> terminalID, 
                     now -> generationTime + getArriveInterval(ramda), 
                     packetID, 0)) == NULL)
                {
                     fprintf(stderr, "make() errror \n");
                     return -1;
                }
                packetID++;
                insert(&list, new);
          
                // 送信したパケットの送信完了イベントを登録
                if ((new = make(SEND_COMPLITE, now -> terminalID, 
                     now -> generationTime + T,
                     now -> packetID, 0)) == NULL)
                {
                     fprintf(stderr, "make() errror \n");
                     return -1;
                }
                insert(&list, new);
            }
            // 回線が使用中ならば
            else
            {                
                // 回線使用パケットの再送完了イベントのcollisionを1つ増やす
                collision(list, occupiePacketID);

                // 次のパケット到着＆送信イベントを登録 
                if ((new = make(ARRIVE_SEND, now -> terminalID, 
                     now -> generationTime + getArriveInterval(ramda), 
                     packetID, 0)) == NULL)
                {
                     fprintf(stderr, "make() errror \n");
                     return -1;
                }
                insert(&list, new);
                packetID++;
                    

                // 送信したパケットの送信完了イベントを登録 
                if ((new = make(SEND_COMPLITE, now -> terminalID, 
                     now -> generationTime + T,
                     now -> packetID, 0)) == NULL)
                {
                     fprintf(stderr, "make() errror \n");
                     return -1;
                }
                insert(&list, new);

                // 回線が使用されているので衝突する,そのためcollisionを1つ増やす
                collision(list, now -> packetID); 
             }
             // 回線を使用状態にして回線を使用しているパケットの情報を登録
             occupiePacketID = now -> packetID;
             free(now);
        }
        // 2 パケット送信完了イベントならば
        else if(now -> eventNo == SEND_COMPLITE)
        {
             // 回線を使っている間、別のパケットの到着＆送信イベントが
             // 発生してないならば
             if (now -> packetID == occupiePacketID)
             {
                 // 回線を未使用状態にする
                 occupiePacketID = 0;
             }

             // 送信中に衝突が発生したならば
             if (now -> collision >= 1)
             {
                 // 再送回数が上限値に達していないならば
                 if (now -> resend < RETRY)
                 { 
                     // 再送イベントを登録
                     if ((new = make(RESEND, now -> terminalID,
                         (now -> generationTime - T)
                          + (rand () % K + 1) * T,
                          now -> packetID, now -> resend + 1)) == NULL)
                     {
                          fprintf(stderr, "make() errror \n");
                          return -1;
                     }
                     insert(&list, new);
                 }
	               }
               // 送信中に衝突が発生していないならば
               else
               {
                   // 送信成功パケット数を増やす
                   success++;
               }
               free(now);
         }
         // 3 パケット再送イベントならば
         else if(now -> eventNo == RESEND)
         {
               // 送信したパケットの送信完了イベントを登録する
               if ((new = make(SEND_COMPLITE, now -> terminalID, 
                    now -> generationTime +  T, now -> packetID, 
                    now -> resend)) == NULL)
               {
                    fprintf(stderr, "make() errror \n");
                    return -1;
               }
               insert(&list, new);

               // 回線が使用されているならば
               if (occupiePacketID != 0)
               {
                   // 現在回線を使用しているパケットは衝突,よって,collisionを増やす
                   collision(list, occupiePacketID); 

                   // 回線が使用されているので今再送したパケットは衝突する,
                   // よって,collisionを増やす
                   collision(list, now -> packetID);  
               }
               // 回線を使用状態にして回線を使用しているパケットの情報を登録
               occupiePacketID = now -> packetID;
               free(now);
          }
          // それ以外のイベントなら
          else
          {
               //エラー発生 シミュレーションを停止
               freeList(&list);
               return -1;
          }
       }
       // リストに残っているイベントデータを解放
       freeList(&list);

       // スループットを計算
       return ((double)success * P_LENGTH  / TIME) / BAND; 
}

// 0以上1未満の乱数を発生させる関数 
double frand()
{
    return (double)rand() / ((double)RAND_MAX + 1.0);
}

// パケットの到着間隔を求める関数 
double getArriveInterval(double ramda)
{
    return -1.0 * (1.0 / ramda) * log(1.0 - frand());
}

// リストにイベントデータを挿入する関数
void insert(Event **listPtr, Event *newPtr)
{
    if (*listPtr == NULL)
    {
        newPtr -> next = NULL;
        *listPtr = newPtr;
    }
    else
    {
        // イベント発生時刻の早い順にデータを挿入する
        // 新たに登録されるイベントの発生時刻がリストに登録されているイベントの中で最も早く生成されたものより早いならば
        if ((*listPtr) -> generationTime > newPtr -> generationTime)
        {
            newPtr -> next = *listPtr;
            *listPtr = newPtr;
        }
        else
        {
            insert(&((*listPtr) -> next), newPtr);
        }
    }
}

// イベントを作成する関数
Event *make(int type, int terminalNo, double geneTime, int nowPacket, int resent)
{
    Event *new;

    new = (Event *)malloc(sizeof(Event));

    if (new == NULL)
    {
        return NULL;
    }

    new -> generationTime = geneTime;
    new -> terminalID = terminalNo;
    new -> eventNo = type;
    new -> resend = resent;
    new -> collision = 0;
    new -> packetID = nowPacket;
    return new;
}

// リストの先頭からイベントデータを取り出す関数 
Event *pushList(Event **listPtr)
{
    Event *tmp;

    tmp = *listPtr; 
    *listPtr = (*listPtr) -> next;

    return tmp;
}

// 再送回数を増やす関数
void collision(Event *list, int packetID)
{
   // リストの終端でない間
   while (list != NULL)
   {
       // 衝突パケットに対応するリスト発見
       if (list -> packetID == packetID)
       { 
           list -> collision++;
           return;
       }
       list = list -> next;
   }
}

// リストの先頭データを解放する関数
void freeList(Event **list)
{
   Event *tmp;
   
   // 今のリストの先頭アドレスを記憶
   tmp = *list;

   // 次のリストを先頭に設定
   *list = (*list) -> next;

   // 今のリストを解放
   free(tmp);
}

// スループットを表示する関数
void printThroughput(double r, double width, int size, double t[])
{
   int i;

   for (i = 0; i < size; i++, r += width)
   {
       printf("到着率 %lf のスループットは %10lf\n", r, t[i]);
   }
}

コンパイル(環境: Windowsのコマンドプロンプト)

gcc -o pureALOHA.exe pureALOHA.c -fexec-charset=CP932

実行

C:\Users\YUTA NAKAMURA\Desktop>pureALOHA.exe

結果(乱数依存なので必ずしも下記通りにならない)

到着率 0.010000 のスループットは   0.042547
到着率 0.020000 のスループットは   0.084830
到着率 0.030000 のスループットは   0.126097
到着率 0.040000 のスループットは   0.162611
到着率 0.050000 のスループットは   0.179921
到着率 0.060000 のスループットは   0.171311
到着率 0.070000 のスループットは   0.142818
到着率 0.080000 のスループットは   0.113314
到着率 0.090000 のスループットは   0.086549
到着率 0.100000 のスループットは   0.065058
到着率 0.110000 のスループットは   0.050803
到着率 0.120000 のスループットは   0.038268
到着率 0.130000 のスループットは   0.029060
到着率 0.140000 のスループットは   0.021841
到着率 0.150000 のスループットは   0.016858
到着率 0.160000 のスループットは   0.012305
到着率 0.170000 のスループットは   0.009276
到着率 0.180000 のスループットは   0.006895
到着率 0.190000 のスループットは   0.004937
到着率 0.200000 のスループットは   0.003874

image.png

参考

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0