1.はじめに

OMNeT++の初心者向けに、なるべくシンプルなコードにて待ち行列のモデルを構築してシミュレーションする方法を紹介します。このコードを基本形として徐々に機能追加すれば複雑なシミュレーションも可能になります。

2.ソースコードの入手

まずソースコードをGitHubから適当なフォルダ（※）にクローンして下さい。OMNeT++のIDEのメニューからFileNew～OMNet++Projectを選択してロケーションを※のフォルダを指定し、EmptyのProjectを作成することにより、OMNeT++Projectとして利用できるようになります。
ソースコードの文字コードはUTF-8ですがWindows版OMNeT++のデフォルトはMS932ですので、文字化けする場合はIDEのメニューからWindow～Preferencesを選択し、General～WorkspaceのText file encodeingをUTF-8に変更してください。なお動作確認はWindows版OMNeT++ 5.6.2にて行っています。

ソースコードを実行すると以下のエラー画面が表示されますが、これは新しくProjectを作成した際に「.oppbuildspec」が変更されるためです。

無視して先に進むことは可能ですが、エラーを解消するにはプロジェクトを右クリックしてPropertiesを選択し、OMNeT++～Makemakeに「Custom Makefile」を指定して下さい。

3.例題の説明

例題は平鍋氏の「サルでもわかる待ち行列」から引用させていただきました。最初の問題は以下の通りです。

ある医院では、患者が平均10分間隔でランダムに訪ねてくる。医師は、1人であり、一人の患者の診断および処方の時間は平均8分の指数分布であった。このとき、患者が診察を受け始めるまでの純粋待ち時間は何分か。

最初に答えを書いてしまいますが、待ち行列の公式にあてはめると例題の解答は32分であることが分かっています。（なぜ答えが分かっているのにシミュレーションするのか？については最後に述べます）

4.シミュレーションのモデルの説明

この例題は３つのノードから構成されるネットワークとして表すことができます。

OMNeT++ではネットワークをNED Languageという言語にて記述し、モジュールのメッセージハンドリングはC++にて記述します。今回の主要なファイルは以下の通りです。

ファイル	開発言語	定義内容
Simulation01.ned	NED	ネットワークを構成するノード、ノードとモジュールの関係、ノード間の接続等
Creat.ned	NED	Createモジュールのパラメータとゲート（出入口）
Queue.ned	NED	Queueモジュールのパラメータとゲート（出入口）
Sink.ned	NED	Sinkモジュールのパラメータとゲート（出入口）
Creat.cc	C++	Createモジュールのメッセージハンドリング
Queue.cc	C++	Queueモジュールのメッセージハンドリング
Sink.cc	C++	Sinkモジュールのメッセージハンドリング
omnetpp.ini	その他	シミュレーション実行時のパラメータ設定

IDEのProject Exploerからsimulation01.nedを開くと。ネットワークのGUIを確認したり、編集することが出来ます。

Sourceタブをクリックするとネットワークのソースコードを確認できます。submodulesブロックはノードの定義、connectionsブロックは各ノード間の接続の定義です。

Simulation01.ned

network Simulation01	// モデル名をSimulation01とする
{
    @display("bgb=459,206");	// 枠の大きさは横459ピクセル、縦206ピクセルとする
    submodules:					// モジュールの定義
        enter: Create {			// Createモジュールを継承してenterノードを定義とする
            parameters:
                @display("p=74,88;i=block/source");		// 座標(74,88)にimages/block/source.pngを表示する
        }
        wait: Queue {			// Queueモジュールを継承してwaitノードを定義する
            parameters:
                @display("p=215,88,c,100;i=block/queue;q=queue");	// 座標(215,88)にimages/block/queue.pngを表示する。ノードにqueueの値を表示する
        }
        doctor: Sink {			// Sinkモジュールを継承してdoctorノードを定義する
            parameters:
                @display("p=348,88,c,100;i=block/sink");	// 座標(348,88)にimages/block/sink.pngを表示する
        }
    connections:					// モジュール間の接続の定義
        enter.out --> wait.in++;	// enterの出口をwaitの入口にセットする
        wait.out --> doctor.in;		// waitの出口をdoctorの入口にセットする
        doctor.out --> wait.in++;	// doctorの出口をwaitの入口にセットする
}

Create.nedは受付を表すCreateモジュールの定義です。パラメータのintervalTimeは患者の到着間隔を表しますが、volatile宣言により読み込み毎に異なる値を取得できます。outという出口があります。入口はありません。

Create.ned

simple Create	// シンプルモジュール名をCreateとする
{
    parameters:
        volatile double intervalTime @unit(s) = default(0);		// パラメータとしてintervalTimeを定義し、単位は秒、初期値はゼロとする
    gates:
        output out;		// 出口としてoutを定義する
}

Queue.nedは待合室を表すQueueモジュールの定義です。inという入口とoutという出口があります。inは複数ノードと接続できるように配列としています。パラメーターはありません。

Queue.ned

simple Queue	// シンプルモジュール名をQueueとする
{
    gates:
		input in[];		// 入口としてinを定義する。数は動的に増える
        output out;		// 出口としてoutを定義する
}

Sink.nedは医師を表すSinkモジュールの定義です。医師の診療時間を表すserviceTimeというパラメータがあります。inという入口とoutという出口が１つづつあります。

Sink.ned

simple Sink		// シンプルモジュール名をSinkとする
{
    parameters:
        volatile double serviceTime @unit(s) = default(0);		// パラメータとしてserviceTimeを定義し、単位は秒、初期値はゼロとする
    gates:
        input in;		// 入口としてinを定義する
        output out;		// 出口としてoutを定義する
}

Create.ccは受付を表すCreateモジュールのメッセージハンドリングの定義です。Define_ModuleマクロはCreateモジュールの定義することを宣言します。２つのメソッドがあり、initializeメソッドはノード生成時の初期処理、handleMessageはメッセージを受け取った時の処理です。initializeは患者の到着を表すbeatメッセージを生成し、パラメータintervalTimeを到着間隔として自身にメッセージを送ります。handleMessageメソッドはbeatメッセージを受け取るとpatientメッセージを待合室に送り、その後、次の患者の到着を表すbeatメッセージを自身に送ります。

Create.cc

#include "Create.h"
Define_Module(Create);

void Create::initialize()
{
    scheduleAt(simTime() + par("intervalTime"), new cMessage("beat"));   // 平均値10分のポアソン分布に基づき、患者を発生させるメッセージを自身に向けて発信
}

void Create::handleMessage(cMessage *msg)
{
    send(new cMessage("patient"), "out");               // 患者を表すメッセージを待ち行列に向けて発信
    scheduleAt(simTime() + par("intervalTime"), msg);   // 次の患者を発生させるメッセージを自身に向けて発信
}

Queue.ccは待合室を表すQueueモジュールのメッセージハンドリングの定義です。initializeメソッドは待ち行列に名前をセットしています。これはシミュレーション時に画面に待ち人数を表示するために使用されます。handleMessageメソッドは患者が到着すると待ち行列に案内して医師にリクエストを送り、医師から診察OKのメッセージが届くと待ち行列の患者を診察室に案内します。

Queue.cc

#include "Queue.h"
Define_Module(Queue);

void Queue::initialize()
{
   queue.setName("queue");              // 待ち行列に名前をつける
}

void Queue::handleMessage(cMessage *msg)
{
    if (strcmp(msg->getName(), "patient") == 0) {       // 患者が到着した場合
        msg->setTimestamp(simTime());   // リードタイムの開始時間をセット
        queue.insert(msg);              // 待ち行列にメッセージを保管
        send(new cMessage("request"), "out");   // リクエストを医師へ
    } else if (strcmp(msg->getName(), "call") == 0) {   // 医師からの呼び出しがあった場合
        if (queue.getLength() > 0) {       // もし患者が待っていれば
            cMessage *patient = check_and_cast<cMessage *>(queue.pop());    // 待ち行列からメッセージを取り出す
            waitTime.collect(simTime() - patient->getTimestamp());          // 待ち時間をカウント
            send(patient, "out");           // 患者を医師へ
        }
        delete msg;     // 呼び出しメッセージを削除
    }
}

//　ノードの統計情報を表示
void Queue::finish()
{
    EV << "Queue Jobs Count:    " << waitTime.getCount() << endl;
    EV << "Queue Min Leadtime:  " << waitTime.getMin() << endl;
    EV << "Queue Mean Leadtime: " << waitTime.getMean() << endl;
    EV << "Queue Max Leadtime:  " << waitTime.getMax() << endl;
    EV << "Standard deviation:  " << waitTime.getStddev() << endl;

    waitTime.recordAs("queue length");
}

Sink.ccは医師を表すSinkモジュールのメッセージハンドリングの定義です。initializeメソッドは変数onWorkingを初期化して診療可能な状態とします。handleMessageメソッドは患者が待合室に到着した際に診療可能ならば診療室に呼んで診察し、診療が終了すれば次の患者を招くことを繰り返します。

Sink.cc

#include "Sink.h"
Define_Module(Sink);

void Sink::initialize()
{
    onWorking = false;  // 現在は空いている
}

void Sink::handleMessage(cMessage *msg)
{
    if (msg->isSelfMessage()) {
        onWorking = false;              // 診察終了
        send(new cMessage("call"), "out");                      // 患者の処置が終わったので、次の患者を呼び出す
        leadTime.collect(simTime() - msg->getCreationTime());   // リードタイムを記録
        delete msg;                                             // 患者メッセージを削除
    } else {
        if (strcmp(msg->getName(), "patient") == 0) {
            onWorking = true;                                   // 診察中
            scheduleAt(simTime() + par("serviceTime"), msg);   // 診療時間は平均値8分のポアソン分布に従う
        } else if (strcmp(msg->getName(), "request") == 0) {
            delete msg;
            if (!onWorking) send(new cMessage("call"), "out");  // 空いていれば次の患者を呼び出す
        }
    }
}

void Sink::finish()
{
    EV << "Total jobs Count:              " << leadTime.getCount() << endl;
    EV << "Total jobs Min leadtime:       " << leadTime.getMin() << endl;
    EV << "Total jobs Mean leadtime:      " << leadTime.getMean() << endl;
    EV << "Total jobs Max leadtime:       " << leadTime.getMax() << endl;
    EV << "Total jobs Standard deviation: " << leadTime.getStddev() << endl;

    leadTime.recordAs("lead time");
}

4.例題の実行

IDEのProject Explorerにてプロジェクトを右クリックし、メニューから「Run As」～「OMNeT++ Simulation」を選んでシミュレーションを実行します。

パラメータを選択する画面が表示されますが、そのまま「OK」をクリックします。

コマンドバーの「FAST」ボタンをクリックするとシミュレーションがスタートします。

しばらく待って、Confirmダイアログが表示されれば終了です。

実行結果を確認すると平均待ち時間は「Queue Mean Leadtime」の値から32.2024です。公式を解く場合の答えは32分ですので想定通りの結果と言えるでしょう。

なお先程のパラメータ選択画面で「Run2」を指定すると異なる実行結果が得られますが、これは乱数ストリームのパラメータを変えているためです。

パラメーターはomnet.iniにて設定できますが、乱数に関する項目は「num-rngs」や「rng-0」です。詳しくはOMNeT++のドキュメント「SimulationManual」を御確認ください。

omnet.ini

[General]
sim-time-limit = 144000s
cpu-time-limit = 144000s
total-stack = 7MiB
cmdenv-express-mode = true
cmdenv-event-banners = true
cmdenv-performance-display = false
record-eventlog = true

network = Simulation01
num-rngs = 3
*.enter.intervalTime = exponential(10.0s)
*.doctor.serviceTime = exponential(8.0s)
*.enter.rng-0=1
*.doctor.rng-0=2

[Config Run2]
*.enter.rng-0=0
*.doctor.rng-0=1

[Config Run3]
*.doctor.serviceTime = exponential(4.0s)

なおさきほどのパラメータ選択画面で「Run3」を指定すると、サービス時間が半分（８分→４分）になったケースの実行結果を得られます。解析的に得られる解の2.7分に対してシミュレーション結果は2.38617分となりました。

5.アニメーション画面やヒストグラム等

シミュレーション実行の際にコマンドバーの「FAST」ではなく「RUN」を実行すると、メッセージ交換の様子をアニメーションにて確認することができます。このときアニメーション速度はスライドバーにてコントロールできます。

またシミュレーション実行後に収集した統計値のヒストグラムを確認することができます。手順としては例えば「wait」ノードをクリックし、画面左下のビューの(cLongHistgram)の変数を右クリックして「Open Graphical View for」を選択します。

これによると約2割のケースは待たずに診療できることが分かります。実行結果では最長281分待つケースがありましたが100分以上待つのはレアケースのようです。

またIDEのProject ExplorerにてresultsフォルダのGeneral-#0.elogファイルを開くと各ノード間の時系列のメッセージの流れを確認することもできます。

6.まとめ

OMNeT++を使ってシミュレーションにて待ち行列問題を解く方法について紹介しましたが、公式で解くのではなくシミュレーションする理由の一つは複雑な条件に対応できるためです。例えば「待ち時間が1時間以上で初診の場合、患者が他医院に行く」等のケースでも柔軟な対応が可能です。また公式を使うと途中経過が分かりませんが、シミュレーションのではログやグラフを見たり、メッセージの流れをアニメーションで確認する等も可能なので、モデルを深く理解するのに役立ちます。

7.次回予告

次回は「サルでもわかる待ち行列」から、待ち行列が２つある例題のシミュレーションを紹介します。

8.改訂履歴

改定日	改定前	改定後
2022.2.20	-	初期登録
2022.3.28	-	文字コード設定について説明を追加
2022.3.28	-	Makefileのエラー対策について説明を追加
2022.3.28	-	見出しの連番や修飾を修正