OMNeT++による離散シミュレーション～QUEUEノード編

#1.はじめに
以前から私はOMNeT++という無償のネットワーク・シミュレータに興味を持っており，汎用的な待ち行列問題を解くのに使えないか？と考えていたのですが，最近の新型コロナの影響によりテレワークが増えて時間的余裕が出来たので当該ツールを勉強しつつ，その有益性を紹介したいと思います．

#2.離散型シミュレータとは？
離散型シミュレータが扱う主な問題は待ち行列です．例えば製造ラインや窓口やネットワーク等を新設（または改善）する案件において必要な設備能力や窓口数，帯域幅や優先順位等を検討する際に有益なインサイトを与えてくれます．この種のツールは高価なため勉強する機会を得ることも難しいのですが，OMNeT++は非営利目的であれば無償ですし機能制限がない点が魅力と感じます．

#3.例題
手元に「SLAMⅡによるシステム・シミュレーション入門（1993年構造計画研究所発行）」がありますので例題2.1を解いてみたいと思います．この例題には下記図の通り５つのノードが登場します．最初のenterノードは平均0.4分の指数分布に従う間隔にてメッセージを生成します．queue1ノードは４つの製品を保管することが可能ですが，もし空きがない場合はleave1ノードに製品を送ります．queue1ノードからqueue2ノードの処理には平均0.25分の指数分布に従う時間を要します．queue2ノードは２つの製品を保管することが可能ですが，もし空きがない場合は受入れ出来ません．queue2ノードからleave2ノードの処理には平均0.5分の指数分布に従う時間を要します．最後のleave2ノードはリードタイム等の統計情報を集計します．なおOMNeT++は本来の用途がネットワークシミュレータなので以降は「製品」を「メッセージ」と呼ぶことにします．  
![02A2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/86fb7987-db18-48e2-a136-faace2f6d6fa.png)

#4.OMNeT++のインストールと設定
[「公式ドキュメント」](https://omnetpp.org/documentation/)のインストールガイドに従ってインストールします．以下はWindows10の例です

+ OMNeT++の[「ホームページ」](https://omnetpp.org/)からバイナリをダウンロードします．本稿ではバージョン5.6.2を使用しています
+ 適当なフォルダにzipファイルを展開します
+ Windowsのコントロールパネルの「環境変数を編集」を呼び出し，ユーザー環境変数Pathに以下を追加します．%OMNET_HOME%は環境にあわせて設定して下さい

```
%OMNET_HOME%\bin
%OMNET_HOME%\tools\win64\usr\bin
%OMNET_HOME%\tools\win64\mingw64\bin
```
+ エクスプローラーにて%OMNET_HOME%\mingwenv.cmdをダブルクリックして起動し，ファイルの展開を待ちます．
+ Shellが起動するので以下コマンドを入力しでOMNeT++をビルドします．しばらくお待ち下さい．  

```
$ ./configure
$ make
```
+ 一度Shellを閉じます
+ Shellを起動するためのショートカットを作成します．リンク先は「%OMNET_HOME%\mingwenv.cmd」とします．%OMNET_HOME%は環境にあわせて修正して下さい

#5.IDE起動とワークスペース用フォルダの作成
作成したショートカットにてShellを起動し，以下コマンドを入力し，IDEの起動を待ちます

```
$ omnetpp
```
プロジェクトのあるフォルダの場所を尋ねられるので(初期値はsamplesとなっている)適当な場所に変更します.下記例ではmodelsとしました．IDEが起動したら「Workbench」に移動します  
![A01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/37244b8a-d37d-0952-a5b0-c71f2b8de72e.png)

#6.プロジェクトの作成
メニューから「File」～「New」～「OMNeT++ Project」を選択して適当なプロジェクト名を付与して下さい（今回はSimSlam2.1としています）．プロジェクトを構成するソースファイルは表の通りですが，GitHub[（https://github.com/tsugulin/SimSlam2.1）](https://github.com/tsugulin/SimSlam2.1)から入手可能です．git cloneにてローカルにダウンロードし，Windowsのファイル・エクスプローラーからIDEのプロジェクト・エクスプローラーにドラッグ＆ドロップすることにより取り込み可能です．  
![02B.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/9b6aee1f-3a31-c4d6-9725-73918675ed8b.png)  

|フォルダ名|ファイル名|説明|
|---|---|---|
|simulations|omnetpp.ini|シミュレーションのパラメータ変数の定義|
|simulations|Simulation01.ned|ノードとモジュールの関連付け（＝ネットワーク）を定義|
|src|Create.ned|メッセージを生成するモジュールの宣言|
|src|Terminate.ned|メッセージを削除するモジュールの宣言|
|src|BalkingQueue.ned|溢れた場合に分岐する待ち行列モジュールの宣言|
|src|BlockingQueue.ned|溢れた場合に前工程をブロックする待ち行列モジュールの宣言|
|src|Create.cc|Createモジュールの定義|
|src|Create.h|Createモジュールのクラス宣言|
|src|Terminate.cc|Terminateモジュールの定義|
|src|Terminate.h|Terminateモジュールのクラス宣言|
|src|BalkingQueue.cc|BallingQueueモジュールの定義|
|src|BalkingQueue.h|BallingQueueモジュールのクラス宣言|
|src|BlockingQueue.cc|BlockingQueueモジュールの定義|
|src|BlockingQueue.h|BlockingQueueモジュールのクラス宣言|
|src|Wavg.cc|待ち行列長さの加重平均を計算する「その他」クラス|
|src|Wavg.h|Wavgクラスのヘッダー|

#7.各ファイルの説明
Simulation01.nedの内容を以下に示しますが，例題のネットワークは５つのノード（enter, queue1, leave1, queue2, leave2）から構成されます．また各ノードは４つのモジュール（Create, BalkingQueue, BlockingQueue, Terminate）から生成されます．@displayキーワードのp=50,100はGUI画面上の位置を表します．i=block/sourceは使用するアイコンイメージのファイル名を表します（使用可能なイメージは%OMNET_HOME%/images/blockを確認して下さい）．q=queueはアイコン右上に変数queueの値を表示することを表します（変数queueは後ほどモジュールを定義する際に登場します）．connectionsは各ノードの入口と出口の接続の関係を表します  

```Simulation01.ned
network Simulation01
{
    submodules: 
        enter: Create { 
            parameters: 
            	@display("p=50,100;i=block/source");
        } 
        queue1: BalkingQueue { 
            parameters: 
            	@display("p=200,100;i=block/boundedqueue;q=queue");
        } 
        leave1: Terminate { 
            parameters:
            	@display("p=200,200;i=block/sink");
        } 
        queue2: BlockingQueue { 
            parameters: 
            	@display("p=350,100;i=block/boundedqueue;q=queue");
        } 
        leave2: Terminate { 
            parameters:
            	@display("p=500,100;i=block/sink");
        } 
    connections:
        enter.out --> queue1.in; 
        queue1.out_outer --> leave1.in; 
        queue1.out_inner --> queue2.in; 
        queue2.out --> leave2.in; 
}
```

４つのモジュールの概要は表の通りです．モジュールは*.nedのファイルにて宣言し，*.ccや*.hのファイルにて定義します．  

|宣言ファイル名|変数|入口|出口|主な役割|
|---|---|---|---|---|
|Create.ned|createIntervalTime|なし|out|メッセージの作成|
|BalkingQueue.ned|numQueueおよびproductionTime|in|out_inner,out_outer|分岐方式の待ち行列|
|BlockingQueue.ned|numQueueおよびproductionTime|in|out|ブロック方式の待ち行列|
|Termindate.ned|なし|in|なし|メッセージの削除|

例としてBalkingQueue.nedについて説明します．変数numQueueは待ち行列の最大容量を，変数productionTimeは後続アクティビティの処理時間を表します．単位はOMNeT++の場合は残念ながら「分」を指定出来ないようですので「秒」としています．なおvolatileを指定するのは処理時間にバラツキを与えるためです（volatileを指定しないと常に同じ値になってしまいます）．ちなみに最初のキーワード「simple」はモジュールの種類を表します．  


```BalkingQueue.ned
simple BalkingQueue
{
    parameters:
        int numQueue = default(0);
        volatile double productionTime @unit(s) = default(0);
	gates:
        input in;
        output out_inner;
        output out_outer;
}
```

次にモジュールの定義についての説明ですが，共通の特徴として以下が挙げられます．  
 - C++言語にて記述
 - Define_Moduleマクロにて同じ名前のNEDモジュール宣言と結合
 - シミュレーション開始時の処理をinitialze()に記述
 - メッセージ受取時の処理をhandleMessage()に記述
 - シミュレーション終了時の処理をfinish()に記述

例としてBalkingQueueモジュールについて説明します．このモジュールは指定された数（omnetpp.iniのnumQueue）のメッセージを待ち行列（FIFO）に保管し，待ち行列の先頭からメッセージを取り出すと指定された時間（omnetpp.iniのproductionTime）をかけて後工程にメッセージを送ります．まずinitializeメソッドでは待ち行列の初期化，待ち行列の平均長さを計算するためのクラスの初期化と後工程のポインタ取得を行います．handleMessageメソッドでは待ち行列が一杯であれば迂回しますが，余裕があれば届いたメッセージを待ち行列の最後尾に保管しつつ，startProductionメソッドを呼び出します．startProductionメソッドでは現在生産中でなく，かつ待ち行列にメッセージがあれば取り出して一定時間経過後に後工程に送ります．finishメソッドでは待ち行列の平均長さや平均滞留時間等の統計情報を表示します  

```BalkingQueue.cc
// 満杯の場合は別ルートへの迂回を要求するタイプの待ち行列

#include "BalkingQueue.h"
Define_Module(BalkingQueue);
#include "BlockingQueue.h"

void BalkingQueue::initialize()
{
    // 変数初期化
    onProduction = false;   // 現在は生産中ではない

    // キューの初期化
    queue.setName("queue");             // GUIに待ち行列長さを表示するための名前
    numMaxQueue = (int)par("numQueue"); // omnetpp.iniの待ち行列数を取得

    // 待ち行列の平均長さを計算するクラスを初期化
    queuelen.init(simTime(), numMaxQueue);

    // 後工程のポインタを取得
    cModule *mod = gate("out_inner")->getNextGate()->getOwnerModule();
    nextNode = check_and_cast<BlockingQueue *>(mod);
}

void BalkingQueue::handleMessage(cMessage *msg)
{
    if ( msg->isSelfMessage() ) {
        // セルフメッセージ=生産完了時
        if (nextNode->checkStatus()) {
            simtime_t_cref d = simTime() - msg->getTimestamp();     // 処理時間
            proctime.collect(d);                                    // 統計情報に保管
            send(msg, "out_inner");     // 後工程に送る
            onProduction = false;       // 生産完了とする
        }
        else
            complete.insert(msg);   // 生産完了としてラインに滞留
    }
    else {
        // 前工程から物が届いたｲﾍﾞﾝﾄの場合
        if (queue.getLength() >= numMaxQueue)
            send(msg, "out_outer");     // キューに格納できる上限を超えているならば外注先に送る
        else {
            // 社内にて生産する場合
            queuelen.set(simTime(), queue.getLength()); // 待ち行列長さの加重平均値の計算
            msg->setTimestamp(simTime());   // リードタイムの開始時間をセット
            queue.insert(msg);              // 待ち行列の最後尾にメッセージを保管
        }
    }
    startProduction();      // 可能であれば生産を開始する
}

// 後工程から要求があった場合，完了したメッセージがあれば取り出して後工程に送る
void BalkingQueue::requestMessage(void)
{
    Enter_Method("requestMessage");
    if (complete.getLength() > 0) {
        cMessage *msg = check_and_cast<cMessage *>(complete.pop());    // メッセージを取り出す
        simtime_t_cref d = simTime() - msg->getTimestamp();     // 処理時間
        proctime.collect(d);                                    // 統計情報に保管
        send(msg, "out_inner");     // 後工程に送る
        onProduction = false;       // 生産完了とする
    }
    startProduction();              // 可能であれば生産を開始する
}

// 在庫があれば生産を開始する
void BalkingQueue::startProduction(void)
{
    Enter_Method("startProduction");
    if (!onProduction) {                // 生産中で無ければ
        if (queue.getLength() > 0) {    // 在庫が在れば
            queuelen.set(simTime(), queue.getLength());             // 待ち行列長さの加重平均値の計算
            cMessage *msg = check_and_cast<cMessage *>(queue.pop());    // 待ち行列先頭のメッセージを取り出す
            simtime_t_cref d = simTime() - msg->getTimestamp();     // キュー滞留時間
            waittime.collect(d);                                    // 統計情報に保管
            onProduction = true;                                    // 生産中とする
            msg->setTimestamp(simTime());                           // リードタイムの開始時間をセット
            scheduleAt(simTime() + par("productionTime"), msg);     // 生産終了後にSelfMessageを送る
        }
    }
    if (ev.isGUI()) getDisplayString().setTagArg("i",1, queue.isEmpty() ? "" : "cyan3");    // 在庫に合わせてノードの色を変更
}

//　ノードの統計情報を表示
void BalkingQueue::finish()
{
    EV << "Queue1 AVG Length:   " << queuelen.get(simTime()) << endl;
    EV << "Queue1 Jobs Count:   " << waittime.getCount() << endl;
    EV << "Queue1 Min WaitTime: " << waittime.getMin() << endl;
    EV << "Queue1 Avg WaitTime: " << waittime.getMean() << endl;
    EV << "Queue1 Max WaitTime: " << waittime.getMax() << endl;
    EV << "Standard deviation:  " << waittime.getStddev() << endl;
    EV << "Queue1 Min ProcTime: " << proctime.getMin() << endl;
    EV << "Queue1 Avg ProcTime: " << proctime.getMean() << endl;
    EV << "Queue1 Max ProcTime: " << proctime.getMax() << endl;
    EV << "Standard deviation:  " << proctime.getStddev() << endl;

    waittime.recordAs("Queue1 WaitTime");
    proctime.recordAs("Queue1 ProcTime");
}
``` 

シミュレーションのパラメータはomnetpp.iniに設定します．シミレーション時間として300秒をセットし，Createモジュールの生成ピッチやBalkingQueueモジュールの待ち行列の数やProcessor1モジュールの処理時間等をセットします．exponentialは指数関数の意味です．  

```omnetpp.ini
[General]
network = Simulation01
record-eventlog = true
num-rngs = 4

sim-time-limit = 300s
cpu-time-limit = 300s
total-stack = 7MiB  # increase if necessary
cmdenv-express-mode = true
cmdenv-event-banners = true
cmdenv-performance-display = false

[Config Run1]
*.enter.createIntervalTime = exponential(0.4s)
*.queue1.numQueue = 4
*.queue1.productionTime = exponential(0.25s)
*.queue2.numQueue = 2
*.queue2.productionTime = exponential(0.5s)
*.enter.rng-0 = 1
*.queue1.rng-0 = 2
*.queue2.rng-0 = 3
```
#8.ビルドとシミュレーションの実行
ソースコードの準備が出来たのでビルドします．プロジェクト・エクスプローラーにて「SimSlam2.1」を右クリックして「Build Project」を選択します．  
![ビルド](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/7a143eaa-b815-b1be-874b-2813ea8c3389.png)
シミュレーションを実行します．プロジェクト・エクスプローラーにて「SimSlam」を右クリックして「Run As」～「OMNeT++ Simulation」を選択します．  
![シミュレーション実行](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/5f96bc37-6a6b-93c5-35fe-78b648a8fe6f.png)
omnetpp.iniのConfigは「Run1」を選択します  
![Config](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/64ca0e0b-a2f9-c808-c2ef-9a3a60236e6b.png)

「Run」または「Fast」「Express」ボタンを押してシミュレーションを実行します．Runを選ぶとアニメーションにてメッセージの動きを確認できます．Expressを選ぶと実行の待ち時間を短縮できます．
![02C.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/cf31b4b0-3b3a-4263-99a2-c89541eb14d4.png)

#9.結果の確認
出力内容を確認します
![02D.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/08631b2a-827f-43ae-8a76-93cd678f24fc.png)

シミュレーション時間300秒にて778個のメッセージが作られ，うち204個はラインから溢れました．生産ラインにて処理したメッセージの平均リードタイムは2.9秒であり，最小0.1秒，最大8.6秒，標準偏差は1.5秒でした．queue1には平均2.27個，queue2には平均1.50個のメッセージが滞留しました．教科書とほぼ同じシミュレーション結果を得ることが出来ました（システムにより乱数体系が異なるので全く同じ結果にはなりません）．  

|項目|今回モデル|教科書|
|---|---|---|
|生産ラインにて処理した数|566|586|
|待ち行列から溢れた数|204|179|
|平均リードタイム|2.94869|2.761|
|最小リードタイム|0.0888436|0.1|
|最大リードタイム|8.59922|7.191|
|第一工程の待ち行列長さ|2.27455|2.0434|
|第二工程の待ち行列長さ|1.49516|1.5557|

もしシミュレーション結果に納得できない場合は各ノード間のメッセージの交換の時間経過や順番がresultsフォルダの*.elogファイルに記録されていますので参照することをお勧めします．  
![02E.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/507413/07deb594-9472-6b40-e60c-5a0bc92450ef.png)

#10.今後の予定
今回はQUEUEノードに関する例題でしたが，次回は同じ書籍に紹介されているAWAITノードやPREEMPTノードの例題を解いてみたいと考えます．また他書籍にも取り組んでみたいと考えます．

#11.参考資料
SLAMⅡによるシステム・シミュレーション入門（初版発行:1993年，著者:森戸晋，中野一夫，相沢りえ子，発行者:構造計画研究所発行，発売所:共立出版）

#12.改訂履歴
|改定日|改定前|改定後|
|---|---|---|
|2021.2.3|ソースコードをGitHubに外出し|ソースコードをページ内に記述|
|2021.2.3|ノードとアクティビティを統合して５ノード構成に変更|enter,queue1,queue2,machine1,machine2,leave1,leave2の７ノード構成|
|2021.1.12|初期登録|―|