| 図９．２．１ 待時式入線無限大 |
 |
| | HOME | 目次 | | 2009 (C) H.Ishikawa |
| ９．１ | 待ち合わせシステムの種類 | ||
| ９．２ | 待時式入線無限大のシステム−−待ち合わせシステムの標準−− | ||
| ９．３ | 待ち合わせのないシステム−−即時系システム−− | ||
| ９．４ | プライオリティ待ち合わせシステム−−至急と普通−− | ||
| ９．５ | サービス段が複数の場合−−いくつものサービスを受ける−− | ||
| ９．６ | 無線でパケット伝送−−ＡＬＯＨＡシステム−− | ||
| ９．７ | データ伝送の標準方式−−ポーリング・システム−− | ||
| 演習 |
この章では、前章のシミュレーションプログラムのさまざまな変形により、通信トラヒック問題のシミュレーションを行います。この問題は、オペレションズリサーチの分野では、待ち行列の理論として知られているもので、本章は、待ち行列や通信トラヒック問題のシミュレーションを学ぶこととなります。シミュレーションの強みは、システムのメカニズムがよく理解できること、理論式では表現できないことも、解答が得られることです。
９．１ 待ち合わせシステムの種類(文献（２）（３）参照)
待ち行列は身近な問題
公衆電話、駅の出札口、食堂のカウンタ、スーパーマーケットのレジ、高速道路の料金所、コンピュータの内部処理、データ通信回線など、待ち行列は身近な問題で多くの応用があります。８章で作ったプログラムを変形すると、各種のタイプの待ち行列のシミュレーション・プログラムが作れます。
待ち行列を処理する待ち合わせシステムには、非常に数多くの種類があり、次の要素によって分類します。
単位到着の時間的分布
単位とは、公衆電話を使いにくる客、料金所にやってくる車など、サービスを受ける人あるいは物のことです。この単位が到着する時間分布によって待ち行列の種類を分類します。ランダムに到着するのであれば、ポアソン分布となり、到着間隔は指数分布になることは、すでに３．２節、３．３節で述べました。
サービス時間の分布
到着単位のサービスするに要する時間の長短のことです。ランダムな電話の通話時分のような場合、指数分布となり、工場の生産機械が一定の所要時間で製品を作る場合は、一定のサービス時間となります。
待時と即時
電話は昔は、オペレータに申し込み、回線が空いたら接続すると言う方法でしたが、現在はダイヤルによりすぐ接続できます。前者を待時式、後者を即時式と言います。待時式の場合、待たされる時間（待ち時間）が問題となりますが、即時式の場合は、途中の回線がふさがっていて話中となる確率（呼損率）が問題となります。
また待時系でも、待ち合わせの場所が一杯になったあとに到着した客はたち去らざるを得ないことがあります。待ち合わせ場所が０の場合が即時系に相当します。
到着数の制限（入線数）
到着する単位の数には無制限にいくらでも大きくなり得る場合と、一定の限界がある場合とがあります。切符売場の例は前者であり、機械修理の問題（８章参照）場合は、修理所に到着する機械は、機械の総数より大きくならないので後者の例です。電気通信では入線数と呼びます。
サービス・チャネル数（出線数）
サービス・チャネルは、窓口の数、回線数のことで、機械修理の問題では修理者の組数に相当します．一般に、サービス・チャンネルを増やすには、コストがかかり、お客の満足を損なわずに、この数を最適にすることが問題となります。電気通信では出線数と呼びます。
サービス段数
サービス・システムには、単一段階だけでサービスが終わる場合と、直列的にいくつものサービスを経てサービスが終わる場合があります。
サービス順
待ち行列にならんでいる単位の、サービスの順番の決め方には先着順、ランダム、プライオリティ方式などがあります。
８章で扱った機械修理の問題は、上の分類のよれば、次のとおり待時式入線有限の場合に相当します。
単位到着の時間分布 ：機械の故障発生に相当し、指数分布である。
サービス時間の分布 ：修理時間に相当し、指数分布である。
待時と即時 ：待時である。
到着数の制限 ：機械の台数が入線 m に相当する。
サービス・チャネル数 ：修理者の組数がサービス・チャネル数に相当する。
サービス段数 ：１段
サービス順 ：先着順
| この章始め |
９．２ 待時式入線無限大のシステム
−−待ち合わせシステムの標準−−
待時式入線無限大のシステムとは
サービス・チャネルが n 回線あるが、到着数の制限はなく、いくらでも大きくなり得る待ち会わせ系を待時式入線無限大のシステムと言います（図９．２．１参照）。これについてシミュレーションをします。前章で作った変化点方式のプログラムS0830.javaを母体とします。特に、ポアソン到着、指数保留時間の待時式入線無限大の場合の理論式をErlang Ｃ式と呼びます。
| 図９．２．１ 待時式入線無限大 |
|
| 図９．２．２ 待時式入線無限大 シミュレーション結果 |
 |
| S0920.java 待時式入線無限大のシステム | Download | 実行 | |
/* S0920.java
* 待時式入線無限大のシステム
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.text.DecimalFormat;
public class S0920 extends Applet{
int N = 5; /* サービスチャンネル数 */
double A = 20.0; /* 平均到着間隔 */
double H = 80.0; /* 平均サービス時間 */
int Q_LENGTH = 100 ; /* 待行列の最大の長さ */
double T_END = 1000000.0; /* シミュレーションを終る時刻 */
double INF = 1.0e100; /* 十分大きい値 */
double EPS = 1.0e-100; /* 十分小さい値 */
public void paint(Graphics g) {
double tt = 0.0; /* シミュレーション時刻 */
int i, j, k; /* forのカウンタ */
int sn[] = new int[N + 1]; /* サービスチャンネルの状態
sn[k]==0:空き,sn[k]==1:ビジー*/
double tn[] = new double[N +1]; /* サービスチャンネルが次に変化を起こすまでの時間 */
double an[] = new double[N + 1]; /* サービスチャンネルの稼働率 */
double tq[] = new double[Q_LENGTH + 1]; /* 待ち行列についた時刻 */
double fq[] = new double[Q_LENGTH + 1]; /* 待ち行列が長さqである割合 */
int q = 0; /* 待ち行列の長さ */
int nn = 0; /* サービスを終えた客の数 */
double tm; /* 次に客が到着するまでの時間 */
double tw; /* 待ち時間 */
double x = 0.0; /* twの和 */
double x2 = 0.0; /* twの自乗和 */
double at; /* 時刻増分 */
int l = 10; /* 表示行 */
DecimalFormat exFormat1 = new DecimalFormat(" 0.000000");
/* 初期設定 */
tm = - A * Math.log(1.0 - Math.random());
for (k = 1; k <= N; k ++) {
sn[k] = 0; tn[k] = INF;
}
/* 開始 */
while (tt <= T_END) {
/* (1)到着 */
if (Math.abs(tm) < EPS) {
tm = - A * Math.log(1.0 - Math.random());
q = q + 1; tq[q] = tt;
}
/* (2)サービス */
for (k = 1; k <= N; k++) {
if (Math.abs(tn[k]) < EPS || sn[k] == 0 ) {
/* tn[k]が0あるいはサービスチャンネルが空きのとき*/
if (q > 0) {
sn[k] = 1;
tn[k] = - H / 2.0 * Math.log(Math.random() * Math.random());
/* 保留時間はアーラン分布 */
tw = tt - tq[1]; //(3)待ち時間
x = x + tw;
x2 = x2 + tw * tw;
nn = nn + 1;
q = q - 1;
if (q > 0) {
for (i = 1; i <= q; i ++) {
tq[i] = tq[i + 1];
}
}
} else {
sn[k] = 0; tn[k] = INF; //(4)
}
}
}
/* 次に状態変化の起る時刻を求める */
at = INF;
if (tm < at) at = tm;
for (k = 1; k <= N; k++) {
if (tn[k] < at) at = tn[k];
}
/* 時間を進める */
tm = tm - at;
for (k = 1; k <= N; k++) {
tn[k] = tn[k] - at;
if (sn[k] > 0) { an[k] = an[k] + at;}
}
fq[q] = fq[q] + at;
tt =tt + at;
}
/* 出力 */
for (k = 1; k <= N; k ++) {
g.drawString(" an[" + k + "] =" + " " + exFormat1.format(an[k] / T_END) ,10 ,l); l = l +12;
}
l = l +12;
for (q = 0; q <= 9; q ++) {
g.drawString(" fq[" + q + "] =" + " " + exFormat1.format(fq[q] / T_END) ,10 ,l); l = l +12;
}
l = l +12;
g.drawString("平均待ち時間 =" + exFormat1.format(x / nn),10 , l); l = l +12;
g.drawString("待ち時間の標準偏差 =" + exFormat1.format(Math.sqrt((x2 - x * x / nn) / nn)) , 10 ,l);
l = l +12;
g.drawString("サービスを受けた客の数 = " + nn, 10 , l);
}
}
|
実行すると、図９．２．３のように、あきらめて立ち去った客の数が得られ、平均待ち時間は短くなります。
| 図９．２．３ あきらめて立ち去る場合 シミュレーション結果 |
 |
| S0921.java あきらめて立ち去る場合 | Download | 実行 | |
/* S0921.java
* 待時式入線無限大のシステム あきらめて立ち去る場合
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.text.DecimalFormat;
public class S0921 extends Applet{
int N = 5; /* サービスチャンネル数 */
double A = 20.0; /* 平均到着間隔 */
double H = 80.0; /* 平均サービス時間 */
int Q_LENGTH = 5 ; /* (5)待行列の最大の長さ */
double T_END = 1000000.0; /* シミュレーションを終る時刻 */
double INF = 1.0e100; /* 十分大きい値 */
double EPS = 1.0e-100; /* 十分小さい値 */
public void paint(Graphics g) {
double tt = 0.0; /* シミュレーション時刻 */
int i, j, k; /* forのカウンタ */
int sn[] = new int[N + 1]; /* サービスチャンネルの状態
sn[k]==0:空き,sn[k]==1:ビジー*/
double tn[] = new double[N +1]; /* サービスチャンネルが次に変化を起こすまでの時間 */
double an[] = new double[N + 1]; /* サービスチャンネルの稼働率 */
double tq[] = new double[Q_LENGTH + 1]; /* 待ち行列についた時刻 */
double fq[] = new double[Q_LENGTH + 1]; /* 待ち行列が長さqである割合 */
int q = 0; /* 待ち行列の長さ */
int nn = 0; /* サービスを終えた客の数 */
int mm = 0; /* あきらめて立ち去った客の数 */
double tm; /* 次に客が到着するまでの時間 */
double tw; /* 待ち時間 */
double x = 0.0; /* twの和 */
double x2 = 0.0; /* twの自乗和 */
double at; /* 時刻増分 */
int l = 10; /* 表示行 */
DecimalFormat exFormat1 = new DecimalFormat(" 0.000000");
/* 初期設定 */
tm = - A * Math.log(1.0 - Math.random());
for (k = 1; k <= N; k ++) {
sn[k] = 0; tn[k] = INF;
}
/* 開始 */
while (tt <= T_END) {
/* (1)到着 */
if (Math.abs(tm) < EPS) {
tm = - A * Math.log(1.0 - Math.random());
if (q < Q_LENGTH) {
q = q + 1; tq[q] = tt;
} else { /* (6)待行列の長さがQ_LENGTH以上の時立ち去る */
mm = mm + 1;
}
}
/* (2)サービス */
for (k = 1; k <= N; k++) {
if (Math.abs(tn[k]) < EPS || sn[k] == 0 ) {
/* tn[k]が0あるいはサービスチャンネルが空きのとき*/
if (q > 0) {
sn[k] = 1;
tn[k] = - H / 2.0 * Math.log(Math.random() * Math.random());
/* 保留時間はアーラン分布 */
tw = tt - tq[1]; //(3)待ち時間
x = x + tw;
x2 = x2 + tw * tw;
nn = nn + 1;
q = q - 1;
if (q > 0) {
for (i = 1; i <= q; i ++) {
tq[i] = tq[i + 1];
}
}
} else {
sn[k] = 0; tn[k] = INF; //(4)
}
}
}
/* 次に状態変化の起る時刻を求める */
at = INF;
if (tm < at) at = tm;
for (k = 1; k <= N; k++) {
if (tn[k] < at) at = tn[k];
}
/* 時間を進める */
tm = tm - at;
for (k = 1; k <= N; k++) {
tn[k] = tn[k] - at;
if (sn[k] > 0) { an[k] = an[k] + at;}
}
fq[q] = fq[q] + at;
tt =tt + at;
}
/* 出力 */
for (k = 1; k <= N; k ++) {
g.drawString(" an[" + k + "] =" + " " + exFormat1.format(an[k] / T_END) ,10 ,l); l = l +12;
}
l = l +12;
for (q = 0; q <= Q_LENGTH; q ++) {
g.drawString(" fq[" + q + "] =" + " " + exFormat1.format(fq[q] / T_END) ,10 ,l); l = l +12;
}
l = l +12;
g.drawString("平均待ち時間 =" + exFormat1.format(x / nn),10 , l); l = l +12;
g.drawString("待ち時間の標準偏差 =" + exFormat1.format(Math.sqrt((x2 - x * x / nn) / nn)) , 10 ,l);
l = l +12;
g.drawString("サービスを受けた客の数 = " + nn, 10 , l); l = l +12;
g.drawString("あきらめて立ち去った客の数 = " + mm, 10, l);
}
}
|
| この章始め |
| 図９．３．１ 即時系システム |
 |
| 図９．３．２ 即時式入線無限大 シミュレーション結果 |
 |
| S0930.java 即時式入線無限大のシステム | Download | 実行 | |
/* S0930.java
* 即時式入線無限大のシステム
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.text.DecimalFormat;
public class S0930 extends Applet{
int N = 4; /* サービスチャンネル数 */
double A = 10.0; /* 呼びの発生間隔 */
double H = 10.0; /* 平均保留時間 */
double T_END = 1000000.0; /* シミュレーションを終る時刻 */
double INF = 1.0e100; /* 十分大きい値 */
double EPS = 1.0e-100; /* 十分小さい値 */
public void paint(Graphics g) {
double tt = 0.0; /* シミュレーション時刻 */
int i, j, k; /* forのカウンタ */
int sn[] = new int[N + 1]; /* サービスチャンネルの状態 */
double tn[] = new double[N +1]; /* サービスチャンネルが次に変化を起こすまでの時間 */
double an[] = new double[N + 1]; /* サービスチャンネルの稼働率 */
int nn = 0; /* サービスを終えた客の数 */
double tm; /* 次に呼びが生起するまでの時間 */
int busy; /* 全チャンネルビジーの時1 */
int bb = 0; /* 損失となった呼びの数 */
double at; /* 時刻増分 */
int l = 10; /* 表示行 */
DecimalFormat exFormat1 = new DecimalFormat(" 0.000000");
/* 初期設定 */
tm = - A * Math.log(1.0 - Math.random());
for (k = 1;k <= N; k++) {
sn[k] = 0; tn[k] = INF;
}
/* 開始 */
while (tt <= T_END) {
/* (1)呼びが生起した時の処理 */
if (Math.abs(tm) < EPS) {
nn = nn + 1;
busy = 1;
for (k = 1; k <= N; k ++) {
if ( sn[k] == 0) { /* 空きチャンネルを探す */
sn[k] = 1;
tn[k] = - H * Math.log(1.0 - Math.random());
busy = 0;
break;
}
}
if (busy == 1) {
bb = bb + 1;
}
tm = - A * Math.log(1.0 - Math.random());
}
/* (2)チャンネルが空いた時の処理 */
for (k = 1; k <= N; k ++) {
if (Math.abs(tn[k]) < EPS) {
sn[k] = 0; tn[k] = INF;
}
}
/* 次に状態変化の起る時刻を求める */
at = INF;
if (tm < at) at = tm;
for (k = 1; k <= N; k++) {
if (tn[k] < at) at = tn[k];
}
/* 時間を進める */
tm = tm - at;
for (k = 1; k <= N; k++) {
tn[k] = tn[k] - at;
if (sn[k] > 0) { an[k] = an[k] + at;}
}
tt =tt+ at;
}
/* 出力 */
for (k = 1; k <= N; k ++) {
g.drawString(" an[" + k + "] = "+ exFormat1.format(an[k] / T_END), 10 ,l); l = l + 12;
}
l = l + 12;
g.drawString("呼損率 = " + exFormat1.format((double)bb / nn), 10 ,l);
}
}
|
| この章始め |
| 図９．４．１ プライオリティ待ち合わせシステム |
 |
| 図９．４．２ プライオリティ待ち合わせ シミュレーション結果 |
 |
| S0940.java プライオリティ待ち合わせシステム | Download | 実行 | |
/* S0940.java
* プライオリティ待ち合わせシステム
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.text.DecimalFormat;
public class S0940 extends Applet{
int N = 5; /* サービスチャンネル数 */
double A1 = 60.0; /* 高プライオリティ平均到着間隔 */
double A2 = 30.0; /* 低プライオリティ平均到着間隔 */
double H = 80.0; /* 平均サービス時間 */
int Q_LENGTH = 100 ; /* 待行列の最大の長さ */
double T_END = 1000000.0; /* シミュレーションを終る時刻 */
double INF = 1.0e100; /* 十分大きい値 */
double EPS = 1.0e-100; /* 十分小さい値 */
public void paint(Graphics g) {
double tt = 0.0; /* シミュレーション時刻 */
int i, j, k; /* forのカウンタ */
int sn[] = new int[N + 1]; /* サービスチャンネルの状態
sn[k]==0:空き,sn[k]==1:ビジー*/
double tn[] = new double[N +1]; /* サービスチャンネルが次に変化を起こすまでの時間 */
double an[] = new double[N + 1]; /* サービスチャンネルの稼働率 */
double tq1[] = new double[Q_LENGTH + 1]; /* 高プライオリティ待ち行列についた時刻 */
double tq2[] = new double[Q_LENGTH + 1]; /* 低プライオリティ待ち行列についた時刻 */
double fq1[] = new double[Q_LENGTH + 1]; /* 高プライオリティ待ち行列が長さqである割合 */
double fq2[] = new double[Q_LENGTH + 1]; /* 低プライオリティ待ち行列が長さqである割合 */
int q1 = 0; /* 高プライオリティ待ち行列の長さ */
int q2 = 0; /* 低プライオリティ待ち行列の長さ */
int nn1 = 0; /* 高プライオリティでサービスを終えた客の数 */
int nn2 = 0; /* 低プライオリティでサービスを終えた客の数 */
double tm1; /* 高プライオリティの次に客が到着するまでの時間 */
double tm2; /* 低プライオリティの次に客が到着するまでの時間 */
double tw1; /* 高プライオリティの待ち時間 */
double tw2; /* 低プライオリティの待ち時間 */
double x1 = 0.0; /* tw1の和 */
double x2 = 0.0; /* tw2の和 */
double x21 = 0.0; /* tw1の自乗和 */
double x22 = 0.0; /* tw2の自乗和 */
double at; /* 時刻増分 */
int l = 10; /* 表示行 */
DecimalFormat exFormat1 = new DecimalFormat(" 0.000000");
/* 初期設定 */
tm1 = - A1 * Math.log(1.0 - Math.random());
tm2 = - A2 * Math.log(1.0 - Math.random());
for (k = 1; k <= N; k ++) {
sn[k] = 0; tn[k] = INF;
}
/* 開始 */
while (tt <= T_END) {
/* (1)高プライオリティ到着 */
if (Math.abs(tm1) < EPS) {
tm1 = - A1 * Math.log(1.0 - Math.random());
q1 = q1 + 1; tq1[q1] = tt;
}
/* (2)低プライオリティ到着 */
if (Math.abs(tm2) < EPS) {
tm2 = - A2 * Math.log(1.0 - Math.random());
q2 = q2 + 1; tq2[q2] = tt;
}
/* サービス */
for (k = 1; k <= N; k ++) {
if (Math.abs(tn[k]) < EPS || sn[k] == 0 ) {
/* tn[k]が0あるいはサービスチャンネルが空きのとき */
if (q1 > 0) { /* (3)高プライオリティの待行列 */
sn[k] = 1;
tn[k] = - H / 2.0 * Math.log(Math.random() * Math.random());
tw1 = tt - tq1[1];
x1 = x1 + tw1;
x21 = x21 + tw1 * tw1;
nn1 = nn1 + 1;
q1 = q1 - 1;
if (q1 > 0) {
for (i = 1; i <= q1; i++) {
tq1[i] = tq1[i + 1];
}
}
} else if (q2 > 0) { /* (4)低プライオリティの待行列 */
sn[k] = 1;
tn[k] = - H / 2.0 * Math.log(Math.random() * Math.random());
tw2 = tt - tq2[1];
x2 = x2 + tw2;
x22 = x22 + tw2 * tw2;
nn2 = nn2 + 1;
q2 = q2 - 1;
if (q2 > 0) {
for (i = 1; i <= q2; i ++) {
tq2[i] = tq2[i + 1];
}
}
} else { /* だれも待っていない */
sn[k] = 0; tn[k] = INF;
}
}
}
/* 次に状態変化の起る時刻を求める */
at = INF;
if (tm1 < at) at = tm1;
if (tm2 < at) at = tm2;
for (k = 1; k <= N; k ++) {
if (tn[k] < at) at = tn[k];
}
/* 時間を進める */
tm1 = tm1 - at;
tm2 = tm2 - at;
for (k = 1; k <= N; k ++) {
tn[k] = tn[k] - at;
if (sn[k] > 0) { an[k] = an[k] + at;}
}
fq1[q1] = fq1[q1] + at;
fq2[q2] = fq2[q2] + at;
tt =tt + at;
}
/* 出力 */
for (k = 1; k <= N; k ++) {
g.drawString(" an[" + k + "] =" + " " + exFormat1.format(an[k] / T_END) ,10 ,l); l = l +12;
}
l = l +12;
for (q1 = 0; q1 <= 9; q1 ++) {
g.drawString(" fq1[" + q1 + "] =" + " " + exFormat1.format(fq1[q1] / T_END) ,10 ,l); l = l +12;
}
l = l +12;
for (q2 = 0; q2 <= 9; q2 ++) {
g.drawString(" fq2[" + q2 + "] =" + " " + exFormat1.format(fq2[q2] / T_END) ,10 ,l); l = l +12;
}
l = l +12;
g.drawString("高プライオリティの平均待ち時間 =" + exFormat1.format(x1 / nn1),10 , l); l = l +12;
g.drawString("高プライオリティの待ち時間の標準偏差 =" + exFormat1.format(Math.sqrt((x21 - x1 * x1 / nn1) / nn1)) , 10 ,l);
l = l +12;
g.drawString("高プライオリティのサービスを受けた客の数 = " + nn1, 10 , l); l = l +12;
l = l +12;
g.drawString("低プライオリティの平均待ち時間 =" + exFormat1.format(x2 / nn2),10 , l); l = l +12;
g.drawString("低プライオリティの待ち時間の標準偏差 =" + exFormat1.format(Math.sqrt((x22 - x2 * x2 / nn2) / nn2)) , 10 ,l);
l = l +12;
g.drawString("低プライオリティのサービスを受けた客の数 = " + nn2, 10 , l); l = l +12;
}
}
|
| この章始め |
| 図９．５．１ サービス段が複数の場合 |
 |
| 図９．５．２ 多段待時式のシステム シミュレーション結果 |
 |
| S0950.java 多段待時式のシステム | Download | 実行 | |
/* S0950.java
* 多段待時式のシステム
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.text.DecimalFormat;
public class S0950 extends Applet{
int L = 3; /* サービスの段数 */
double A = 5.0; /* 平均到着間隔 */
int SIZE = 5; /* ヒストグラムの大きさ */
int MOD = 128; /* 客の番号の最大値 */
int NN_END = 10000; /* シミュレーションを終る客の数 */
double INF = 1.0e100; /* 十分大きい値 */
double EPS = 1.0e-100; /* 十分小さい値 */
public void paint(Graphics g) {
double tt = 0.0; /* シミュレーション時刻 */
int i; /* サービス段に対するforのカウンタ */
int k; /* チャンネルに対するforのカウウタ */
int u; /* ヒストグラムに対するforのカウンタ */
int ii; /* 待行列の順番に対するforのカウウタ */
int n[] = {0, 4, 4, 3}; /* 各段ごとのチャンネル数 */
double h[] = {0.0, 10.0, 8.0, 8.0}; /* 各段ごとの平均サービス時間 */
int sn[][] = new int[L + 1][10]; /* サービスチャンネルの状態
* sn[i][k]==0:i段目のkチャンネルは空き
* sn[i][k]==mm: 客mmをサービス中 */
double tn[][] = new double[L + 1][10]; /* サービスチャンネルが次に変化を起こすまでの時間 */
double ta[] =new double[MOD + 1]; /* 客ごとの到着時刻 */
int q[] = new int[L + 1] ; /* 各段ごとの待ち行列の長さ */
int sq[][] = new int[L + 1][20]; /* 各段ごとの待ち行列のii番目にならんでいる客の番号 */
int mm = 0; /* 客の番号 1からMODまで */
int nn = 0; /* サービスを終えた客の数 */
double tm; /* 次に客が到着するまでの時間 */
double ts; /* 全サービスを受けたトータルの時間 */
double fr[] = new double[100]; /* tsの分布 */
double x = 0.0; /* tsの和 */
double x2 = 0.0; /* tsの自乗和 */
double at; /* 次に状態の変化が起るまでの時間 */
int l = 12; /* 表示行 */
DecimalFormat exFormat1 = new DecimalFormat(" 0.00000");
/* 初期設定 */
tm = - A * Math.log(1.0 - Math.random());
for (i = 1; i <= L; i ++) {
for (k = 1; k <= n[i]; k ++) {
sn[i][k] = 0; tn[i][k] = INF;
}
}
/* 開始 */
while (nn <= NN_END) {
/* (1)到着 */
if (Math.abs(tm) < EPS) {
if (mm < MOD) { mm = mm + 1; } else { mm = 1; }
tm = - A * Math.log(1.0 - Math.random());
q[1] = q[1] + 1; sq[1][q[1]] = mm; /* 1段目の待行列にならぶ */
ta[mm] = tt;
}
/* (2)サービス */
for (i = 1; i <= L; i ++) { /* すべての段に対し */
for (k = 1; k <= n[i]; k ++) { /* すべてのチャンネルをスキャン */
if (Math.abs(tn[i][k]) < EPS) { /* チャンネルが空いた時 */
if (i < L) {
q[i + 1] = q[i + 1] + 1; /* 次の段にならぶ */
sq[i + 1][q[i + 1]] = sn[i][k];
} else { /* (5)最後の段の場合統計をとる */
ts = tt - ta[sn[i][k]];
x = x + ts;
x2 = x2 + ts * ts;
fr[(int)(ts / SIZE)] = fr[(int)(ts / SIZE)] + 1;/* ヒストグラム */
nn = nn + 1;
}
} else if (sn[i][k] != 0) { /* そのチャンネルがビジーの時は */
continue; /* つぎのkを見に行く */
}
if (q[i] > 0) { /* (3)待行列から取り出す処理 */
sn[i][k] = sq[i][1];
tn[i][k] = - h[i] * Math.log(1.0 - Math.random());
q[i] = q[i] - 1;
if (q[i] > 0) {
for (ii = 1; ii <= q[i]; ii++) {
sq[i][ii] = sq[i][ii + 1];
}
}
} else { /* 待行列に誰もいない */
sn[i][k] = 0; tn[i][k] = INF;
}
}
}
/* 次に状態変化の起る時刻を求める */
at = INF;
if (tm < at) at = tm;
for (i = 1; i <= L; i ++) {
for (k = 1; k <= n[i]; k++) {
if (tn[i][k] < at) at = tn[i][k];
}
}
/* (4)時間を進める */
tm = tm - at;
for (i = 1; i <= L; i ++) {
for (k = 1; k <= n[i]; k ++) {
tn[i][k] = tn[i][k] - at;
}
}
tt =tt + at;
}
/* ヒストグラムの出力 */
g.drawString(" ts fr[ts]", 10, l); l = l + 12;
for (u = 0; u < 19 ; u++) {
g.drawString(" " + u*SIZE + "-" + (u+1)*SIZE + " "+ exFormat1.format((double)(fr[u])/NN_END), 10, l);l = l + 12;
}
g.drawString("全サービスを受けた平均時間 =" + exFormat1.format(x / NN_END), 10, l);l = l +12;
g.drawString("その標準偏差 =" + exFormat1.format(Math.sqrt((x2 - x * x / NN_END) / NN_END)), 10, l);l = l + 12;
}
}
|
| この章始め |
| 図９．６．１ ＡＬＯＨＡシステムの構成 |
 |
| 図９．６．２ パケットのフォーマット |
 |
| 図９．６．３ ＡＬＯＨＡシステムの状態図 |
 |
| 図９．６．４ ALOHAシステムの動作 |
 |
| S0960.java アロハシステム | Download | 実行 | |
/* S0960.java
* アロハシステム
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import window.Window;
public class S0960 extends Applet implements ActionListener{
Button button0;
Button button1;
boolean sw = false;
public void init() {
button0 = new Button(" 実行 ");
button1 = new Button("クリア");
add(button0);
add(button1);
button0.addActionListener(this);
button1.addActionListener(this);
}
public void actionPerformed(ActionEvent e) {
String label = e.getActionCommand();
if (label.equals(" 実行 "))
sw = true;
else
sw = false;
repaint();
}
public void paint(Graphics g) {
Window w;
w = new Window();
int height;
int width;
int SPACE = 30;
int M = 8; /* 端末の数 */
double R = 10.0; /* 再送信タイミング */
int NN_END = 5000; /* シミュレーションを終るパケットの数 */
double H_END = 0.8; /* hの最大 */
double INF = 1.0e100; /* 十分大きい値 */
double EPS = 1.0e-100; /* 十分小さい値 */
double tt; /* シミュレーション時刻 */
double a= 10; /* パケットを送り終って次の送るべきパケットが
発生するまでの平均時間 */
double h= 0.0; /* 平均パケット長 */
int i; /* forのカウンタ */
int j; /* forのカウンタ */
int s[] = new int [M + 1]; /* 端末の状態 s[j]=0,1,2,3 */
double t[] = new double [M + 1]; /* 端末が次に変化を起こすまでの時間 */
double tr[] = new double [M + 1]; /* 再送パケット伝送時間 */
double t0[] = new double [M + 1]; /* パケット伝送開始時刻 */
int ss; /* いずれかの端末が送信中の時ss=1
そうでないときss=0 */
int nn; /* 送信完了したパケットの数 */
double tw; /* 待ち時間の合計 */
double ts; /* 送信成功したパケット伝送時間の合計 */
double at; /* 次に状態の変化が起るまでの時間 */
/* スクリーンの大きさを読み取る */
width = getSize().width;
height = getSize().height;
/* グラフィクの準備 */
w.setWindow(0, 0.0,0.0,H_END,0.2,
SPACE,height/2-SPACE/2,width-SPACE,SPACE);
w.axis(0, "平均パケット長", 0.2, "through put", 0.05, g);
w.setWindow(1, 0.0,0.0,H_END,100,
SPACE,height-SPACE,width-SPACE,height/2+SPACE/2);
w.axis(1, "平均パケット長", 0.2, "waiting time", 20, g);
w.moveTo(0, 0.0, 0.0, g);
w.moveTo(1, 0.0, 0.0, g);
if (sw == true) {
while (h <= H_END) {
/* 初期設定 */
h = h + 0.05; ss = 0; nn = 0; tt = 0; tw = 0.0; ts = 0.0;
for (j = 1; j <= M; j ++) {
s[j] = 0; t[j] = - a * Math.log(1.0 - Math.random());
}
/* 開始 */
while (nn <= NN_END) {
for (j = 1; j <= M; j ++) { /* (1) */
if (Math.abs(t[j]) < EPS) {
switch(s[j]) {
case 0: /* 送信パケット発生 */
t[j] = - h * Math.log(1.0 - Math.random());
tr[j] = t[j];
t0[j] = tt;
ss = 0;
for (i = 1 ;i <= M; i ++) { /* (2) */
if (s[i] == 1 || s[i] == 2 ) { /* 他局送信中 */
s[i] = break;
}
}
if (ss == 0) {
s[j] = 1; /* 送信中 */
}
break;
case 1: /* 送信完了 */
nn = nn + 1; /* 統計をとる */
tw = tw + (tt - t0[j]);
ts = ts + tr[j];
s[j] = 0;
t[j] = - a * Math.log(1.0 - Math.random());
break;
case 2: /* 送信失敗 */
s[j] = 3;
t[j] = - R * Math.log(1.0 - Math.random());
break;
case 3: /* 再送信開始 */
ss = 0;
for (i = 1; i <= M; i ++) {
if ( s[i] == 1 || s[i] == 2) {
s[i] = 2;
s[j] = 2; t[j] = tr[j];
ss = 1;
break;
}
}
if (ss == 0) {
s[j] = 1; t[j]= tr[j];
ss = 1;
}
break;
}
}
}
/* 時間を進める */
at = INF;
for (j = 1; j <= M; j ++) {
if (t[j] < at) at = t[j];
}
for (j = 1; j <= M; j ++) {
t[j] = t[j] - at;
}
tt =tt+ at;
}
/* 出力 */
g.setColor(Color.green);
w.lineTo(0, h, ts / tt, g);
g.setColor(Color.blue);
w.lineTo(1, h, tw / nn, g);
}
}
}
}
|
| 図９．６．５ ＡＬＯＨＡシステム シミュレーション結果 |
 |
| この章始め |
| 図９．７．１ ポーリング・システム |
 |
| 図９．７．２ ポーリング・システムの状態遷移図 |
 |
| 図９．７．３ ポーリング・システムの動作 |
 |
| 図９．７．４ ポーリングシステム シミュレーション結果 |
 |
| S0970.java ポーリングシステム | Download | 実行 | |
/* S0970.java
* ポーリングシステム
* (C) H.Ishikawa 2008
*/
package simulation;
import java.applet.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import window.Window;
public class S0970 extends Applet implements ActionListener{
Button button0;
Button button1;
boolean sw = false;
public void init() {
button0 = new Button(" 実行 ");
button1 = new Button("クリア");
add(button0);
add(button1);
button0.addActionListener(this);
button1.addActionListener(this);
}
public void actionPerformed(ActionEvent e) {
String label = e.getActionCommand();
if (label.equals(" 実行 "))
sw = true;
else
sw = false;
repaint();
}
public void paint(Graphics g) {
Window w;
w = new Window();
int height;
int width;
int SPACE = 30;
int M = 8; /* 2次局の数 */
double HP = 0.001; /* ポーリング周期 */
double HF = 0.001; /* 空きフレーム伝送時間 */
int NN_END = 10000; /* シミュレーションを終るパケットの数 */
double H_END = 5.0; /* hの最大 */
double INF = 1.0e100; /* 十分大きい値 */
double EPS = 1.0e-100; /* 十分小さい値 */
double tt = 0.0; /* シミュレーション時刻 */
double a = 10; /* フレームを送り終ってから次の
フレームが発生するまでの平均時間 */
double h = 0.0; /* 平均データ伝送時間 */
int j; /* forのカウンタ */
int sn; /* 1次局の状態 */
double tn; /* 1次局が次に変化を起こすまでの時間 */
int sm[] = new int [M + 1]; /* 2次局の状態 */
double tm[] = new double [M + 1]; /* 2次局が次に変化を起こすまでの時間 */
double t0[] = new double [M + 1]; /* ポーリング待ち状態に入った時刻 */
double tf[] = new double [M + 1]; /* 送信フレーム時間 */
int p; /* ポーリングをかけている2次局の番号 */
int nn; /* 送信完了したフレームの数 */
double tw; /* 待ち時間の合計 */
double ts; /* 送信したフレーム時間の合計 */
double at; /* 次に状態の変化が起るまでの時間 */
/* スクリーンの大きさを読み取る */
width = getSize().width;
height = getSize().height;
/* グラフィクの準備 */
w.setWindow(0, 0.0,0.0,H_END,1,
SPACE,height/2-SPACE/2,width-SPACE,SPACE);
w.axis(0, "平均パケット長", 1.0, "through put", 0.2, g);
w.setWindow(1, 0.0,0.0,H_END,40,
SPACE,height-SPACE,width-SPACE,height/2+SPACE/2);
w.axis(1, "平均パケット長", 1.0, "waiting time", 5.0, g);
w.moveTo(0, 0.0, 0.0, g);
w.moveTo(1, 0.0, 0.0, g);
if (sw == true) {
while (h < H_END) {
/* 初期設定 */
h = h + 0.5; nn = 0; tt = 0; tw = 0.0; ts = 0.0;
sn = 0; tn = HP;
for (j = 1; j <= M; j ++) {
sm[j] = 0; tm[j] = - a * Math.log(1.0 - Math.random());
}
p = 1;
/* 開始 */
while (nn < NN_END) {
/* (1)1次局のシミュレーション */
if (Math.abs(tn) < EPS) {
switch(sn) {
case 0: /* ポーリング完了 */
if (sm[p] == 1) { /* 2次局pに送るべきデータがある場合 */
sn = 1; tn = INF; /* (2)1次局は状態1へ */
tm[p] = 0.0; /* (8)2次局pのtm[p]を0とする */
} else {
sn = 2; tn = HF; /* 1次局は状態2へ */
}
break;
case 1: /* データフレーム受信完了 */
case 2: /* 空フレーム受信完了 */
sn = 0; tn = HP; /* (4)1次局は状態0へ */
if (p < M) { p = p + 1;} else {p = 1;} /* (5)ポーリング番号を1増加 */
break;
}
}
/* (6)2次局のシミュレーション */
for (j = 1; j <= M; j ++) {
if (Math.abs(tm[j]) < EPS) {
switch(sm[j]) {
case 0: /* 送るべきフレーム発生 */
sm[j] = 1; tm[j] = INF; /* (7)状態1へ */
t0[j] = tt; /* (9) */
break;
case 1: /* ポーリング待へ */
/* 次の送信フレーム */
sm[j] = 2; tm[j] = - h * Math.log(1.0 - Math.random());
tf[j] = tm[j];
tn = tm[j]; /* (3)1次局のtnをtm[j]と同じ値とする */
break;
case 2: /* フレーム送信完了 */
/* 統計をとる */
nn = nn + 1;
tw = tw + (tt - t0[j]); /* (10) */
ts = ts + tf[j];
sm[j] = 0; /* 状態0へ */
tm[j] = - a * Math.log(1.0 - Math.random());
break;
}
}
}
/* 時間を進める */
at = INF;
if (tn < at) at = tn;
for (j = 1; j <= M; j ++) {
if (tm[j] < at) at = tm[j];
}
tn = tn - at;
for (j = 1; j <= M; j ++) {
tm[j] = tm[j] - at;
}
tt =tt + at;
}
/* 出力 */
g.setColor(Color.green);
w.lineTo(0, h, ts / tt, g);
g.setColor(Color.blue);
w.lineTo(1, h, tw / nn, g);
} /* 次のhへ */
}
}
}
|
| この章始め |
| 表ｅ．９．１ |
 |
| この章始め |
| | HOME | 目次 | | 2009 (C) H.Ishikawa |