平成14年度 卒業論文
マルチホップ無線網における
移動基地局の導入に関する一考察
エス 佐藤
概要
本研究では、「移動基地局」を
マルチホップ無線通信を適用したセルラシステムに導入した場合についての考察を行う。
移動基地局とは、これまで固定であった基地局が、ノード同様に移動可能となったものである。
移動基地局はノード間通信の中継を専用に行い、マルチホップ無線網の連結性を向上させる。
これにより、無線網全体の品質向上が期待できる。
本研究では、移動基地局にどのような配置、移動パターンを適用すれば効率的か、
コンピュータシミュレーションを用いて検討を行う。
様々な条件下でシミュレーションを行った結果、
ノードの配置や移動方向にランダム性が強い場合は、
移動基地局が有効に機能する地点を見つけられず、移動基地局の有効性は低いことがわかった。
また、 ノードの移動方向が同一で、かつノード配置に偏りがある場合は、
移動基地局がノードの密度が密である地点を追随することにより、有効に機能することがわかった。
このように、移動基地局の移動パターンは単純なものであっても、
移動基地局が無線網の品質向上に有効であることを示すことができた。
Abstruct
This report considers effect of applying
"movable base station" in cellular
systems
with multi-hop wireless network.
Movable base station is a concept that the
base station which was fixation until
get a system of moving.
It relays communication of other nodes and
assist the wireless network by the nodes,
Then the connectivity of the multi-hop wireless
network improves,
and the improvement in quality of the whole
wireless network can be expected.
This report examines whose method of arrangement
and move for movable base station is
efficient using computer simulation.
As a result of simulation under various conditions,
when arrangement and move pettern of nodes
has strong property of random,
movable base station can not be found the
effective point to move,
effect of movable base station is low.
On the other hand, when the move direction
of nodes is the same,
and the arrangement of nodes is biased,
according as movable base station follows
a dense point,
movable base station functions effectively.
Thus, even if method of move for movable
base station is simple,
it is able to be shown that a movable base
station is effective
in the improvement in quality of a wireless
network.
1 まえがき
携帯電話の普及により、
いついかなるときでも通信ができる環境は生活環境の一部として必要不可欠なものとなった。
今後は次世代の移動通信として、より良い通信環境の整備、
さらには通信の高速化、すなわち通信の品質向上が求められていくことになる。
携帯電話のセルラ方式における現状の問題点の一つとして、
地下道やビルの谷間など、
基地局が被覆する領域内であるにも関わらず
局所的に通信困難となる領域が存在することが挙げられる。
この領域をデッドスポットと呼ぶ。
将来、通信の高速化のためセルラ方式で使用する周波数が高くなり、
それによってデッドスポットが増大することが予想される。
このデッドスポット問題を解決する手段として、
マルチホップ無線網をセルラ方式に適用することが提案されている。
マルチホップ無線網は、現状のようにノードが基地局と通信するだけでなく、
ノード同士が直接通信をしながらネットワークを形成する考え方である。
このマルチホップ無線網を用いることで、
ノードがデッドスポット内にある時でも通信が可能となり、
さらには有線網や固定基地局を介することなく、
ノードのみでネットワークを構成できる可能性があり、
盛んに研究が行われている。
しかし、自由意志に従って移動するノードによるマルチホップ無線網の、
通信品質に関する信頼性は決して高くない。
よって現実的には、ノードによるマルチホップ無線網と、
従来の固定基地局による無線網を併用する形態で運用していくことが考えられる。
つまり、デッドスポットに存在するノードは、
マルチホップ無線網を介してデッドスポット外の基地局との接続を構築することになると
考えられる。
その状況を踏まえた上で、
デッドスポット問題解決のための新たなアプローチとして、
移動基地局をシステムに導入することを考える。
移動基地局はノード間通信の中継を専門に行いながら移動する。
移動基地局がネットワークの連結性が低い地点を
自動的に探索、発見することができ、
さらにその地点を追従することができれば、
マルチホップ無線網の連結性が改善され、
無線網全体の信頼性の向上が期待できる。
本研究では、
移動基地局がノードによるマルチホップ無線網の連結性を高めるためには
どのような配置、移動アルゴリズムを適用すれば効果的かを検討し、
マルチホップ無線網を適用したセルラシステムに
さらに移動基地局を導入する有効性を明らかにすることを目的とする。
マルチホップ無線網の連結性が
ノードの配置状況や移動方法に依存して変化することは容易に予想できる。
ノードの移動方法は様々なものが考えられるが、
本稿ではいくつかの移動方法に分類してモデル化し、
それぞれのモデルに対して移動基地局がどのような移動アルゴリズムを適用すれば
効果を挙げられるかを検討する。
具体的には、本稿で用いたノードの移動モデルは次の2つである。
- ノードの移動目標の共通性が小さい場合。
ノードが道路などに沿って移動するのではなく、
また、ノードの目標地点が定まっておらず、
ランダムに移動するような場合。
- ノード群の移動方向に共通性がある場合。
例えば、歩行者が道路に沿って動き、目的地を目指して移動するような場合。
2 実験方法
2.1 仮定
実験を行うにあたり、以下のような状況を想定した。
図1：仮想モデルのイメージ
- 固定基地局からノードまでの電波伝搬が弱い領域がある。
その中で移動基地局とノードが移動する。
- セルラシステムはGPSのような位置情報を取得できるシステムと連携が取れている。
- 電波伝搬が弱いため、ノードと固定基地局間の通信品質は低いが、
ノードの位置を伝える程度の通信は可能である。
- 移動基地局はノードと固定基地局間の通信の中継を行う。
また、周囲のノード配置の情報を蓄積できるシステムを搭載する。
- 移動基地局が領域内で移動することによって
ネットワーク状況をいかに改善していくかに注目する。
ここでネットワーク状況の判断基準は、
領域内でどれだけ大きなマルチホップネットワークが作れるか、にあるとする。
すなわち、接続を確立できたノード数の多さを判断基準とする。
2.2 シミュレーションの環境設定
2.1で想定した状況を、次のような方法でコンピュータシミュレートした。
- 観測フィールドがある。大きさは200×200。
- フィールド内にノードと移動基地局を配置する。
両者はある一定の規則に従って移動する。
- ノードが移動している途中でフィールド外に出た場合、
フィールドの反対側から再び入って来るものとする。
これにより、フィールド内のノード密度は常に一定に保たれる。
- 移動基地局にはノードの位置情報として、
次のような方法で生成された情報が蓄積される。
図2：移動基地局に蓄積される情報の生成法のイメージ
- フィールドを9個のブロックに分割し、番号を振る。
- フィールド全体のノード配置状況を調べる。
- 各ブロック内のノード数を数え、最も多くノードが含まれるブロックを調べる。
- 移動基地局にそのブロック番号が伝えられる。
- 移動基地局の目標地点は各ブロックの中央とする。
- フィールド内でノードと移動基地局が作るネットワークに注目し、
生成されたネットワークに接続しているノード数を
現在のネットワーク状況の評価基準とする。
3 ノードの移動目標の共通性が小さい場合
ノードの移動目標の共通性が小さい状況を想定し、シミュレーションを行った。
シミュレーションの諸条件は以下の通りである。
表1：シミュレーション諸条件
| ノード数 |
400 |
| ノードの初期位置 |
ランダム(一様分布による) |
| ノードの移動方向 |
ランダム |
| ノードの速さ |
1（全ノード一定） |
| ノードの通信可能距離 |
5 |
| 移動基地局の通信可能な距離 |
25 |
移動基地局をこの状況下において様々なパターンで移動させ、
ネットワーク状況の改善性を観察する。
3.1 移動基地局の目標地点の設定
移動基地局が周囲のノード状況を随時調査しながら、
- ノード密度が「高い」ブロックへ移動する場合(to
MAX)
- ノード密度が「低い」ブロックへ移動する場合(to
MIN)
この2つの場合を比較した。
図3：シミュレーションの結果
結果： ノード密度が「高い」地点へ移動するときに良い結果が出た。
3.2 移動基地局の移動パターンの比較
移動基地局を以下の3パターンで移動させた。
- フィールドの中央で固定(fixed)
- 固定路（四角形）を巡回(rectangle)
- ノード密度が「高い」地点へ移動基地局が向かう(to
MAX)
それぞれの場合でネットワーク状況の改善性を観察、比較した。
図4：シミュレーションの結果
結果：どのパターンの場合もほぼ同じ結果であった。
3.3 考察
ノードの配置・移動パターンにランダム性が強い場合、
移動基地局が移動する効果は低いと考えられる。
4 ノード群の移動方向に共通性がある場合
ノードの配置・移動パターンにランダム性が強い場合、
移動基地局が移動する効果は低い。
そこで、ノードの移動パターンに規則性と共通性を持たせ、
その場合の移動基地局の効果を検討する。
この章では、
ノード群が共通の目的地に向かって移動している場合を想定し、シミュレーションを行った。
シミュレーションの諸条件は以下の通りである。
表2：シミュレーション諸条件
| ノード数 |
400 |
| ノードの初期位置 |
ランダム(一様分布による) |
| ノードの移動方向 |
全ノード一定 |
| ノードの速さ |
1（全ノード一定） |
| ノードの通信可能距離 |
5 |
| 移動基地局の通信可能な距離 |
25 |
移動基地局をこの状況下において様々なパターンで移動させ、
ネットワーク状況の改善性を観察する。
4.1 情報を蓄積した後移動基地局が移動を開始する場合
移動基地局が最初しばらく移動せず、周囲ノードの位置情報を蓄積し、
200(単位時間)後からノード密度の高い地点へと移動する場合を考える。
このような移動基地局の移動パターンを採用した理由は、
このシミュレーションにおいて、
ノードの動く向きが一定で、速さも全ノード1で一定なので、
200(単位時間)でノードの状況が元に戻る。
つまり、ノードの配置状況に定常性があり、
情報を蓄積することに効果があると考えたからである。
図5：ノードの移動方法のイメージ
結果図を2つ示す。
図6：結果1：成功例
図7：結果2：失敗例
結果：情報蓄積後に移動基地局が移動することにより、
ネットワーク状況に関して高い改善性を示す場合と、
そうでない場合があった。
結果にばらつきの出た原因として、
ノードの初期配置に関連があることが予想された。
予想では、ノードがある程度偏って配置された場合に良い結果が出て、
全体に散らばった場合に良い結果が出ないようであった。
4.2 ノード配置を意図的に偏らせた場合の検討
ノードの初期配置を意図的に偏らせたあと、
前節と同じく、移動基地局に情報を蓄積させた後に移動させた。
ノードの配置を偏らせる方法は次の通りである。
- 平均100、分散V(変数)の正規乱数をノードの数だけ発生させ、
それぞれをフィールド内のノードの縦座標に対応させていく。
すると、フィールドの上下の中央にノードが偏る。
- 横座標は、一様分布を用いてランダムに設定する。
実際にノードを配置してみるとこのようになる。
（分散V=500）
図8：縦方向に正規分布、横方向に一様分布を用いたノード配置例
補足
これ以降、結果として示す「倍率」データとは、
ここまで指標として扱って来た「ネットワークを形成したノードの個数」を
単位時間ごとに集計し、それの情報収集後の累計を情報収集前の累計で割ったものである。
すなわち、
倍率=（情報収集後の累計）/（情報収集前の累計）
であり、倍率が高いほど、情報収集後に
ネットワーク状況をより改善できている、ということになる。
1つのパターンにつき3つ図を示すが、これは
1.「倍率」の平均値（高いほど改善性が高い）
2.「倍率」データ自体の分散（高いほど、「倍率」データにばらつきがある。
つまり、改善できるときと改善できないときの差が大きい）
3.「倍率」データの度数分布表（平均値が極大のときと小さいときを比較す
る。2つ目のグラフで示すデータのばらつきを視認するために用意した）
以上3つの組み合わせである。
以上の方法に基づいて、結果を示す。
図9：ノード分布の分散と「倍率」の平均値の関係
図10：「倍率」データ自体の分散
図11：実際の「倍率」データの個数
(ノード分布の分散が1000と16000のときのみ)
結果：「倍率」の平均を取る（図9）と、
ノード分布の分散が1000程度の時に最も高くなった。
グラフは単調減少にはならず、
つまりノード配置が偏っているほど（配置時の正規分布の分散が小さいほど）
良い結果が出る訳ではなかった。
また、データ自体の分散図（図10）から、
ノード分布の分散が小さいときにデータの分散が大きい。
つまり、ノードの偏りが大きいときは、
状況を改善できる時とできない時で、幅があることがわかる。
図11でその幅が表れている。
ノード分布の分散が大きくなるにつれて、幅は狭まっていき、
つまり「状況が常に改善されない」ことになる。
4.3 様々なノード配置に対する検討
前節から発展させ、ノードの配置パターンを様々に変えて実験を行った。
結果を前節の結果と比較する。
4.3.1 全体のノード密度が減少した場合
全体のノード密度が減少した場合を考えた。
表3：シミュレーション条件の変更点
|
ノード数
|
400 → 200 |
図12：ノード密度が減少した場合の「倍率」の平均値
図13：ノード密度が減少した場合の「倍率」データ自体の分散
図14：ノード密度が減少した場合の「倍率」データの個数
(ノード分布の分散が1000と16000のとき)>
4.3.2 全体のノード密度が増加した場合
全体のノード密度が減少した場合を考えた。
表4：シミュレーション条件の変更点
| ノード数 |
400 → 800 |
図15：ノード密度が増加した場合の「倍率」の平均値
図16：ノード密度が増加した場合の「倍率」データ自体の分散
図17：ノード密度が増加した場合の「倍率」データの個数
(ノード分布の分散が2000と16000のとき)>
4.3.3 ノードの密集性が増大した場合
ノードの密集性が増大した場合を考えた。
シミュレーション条件の変更点として、ノード配置方法を変更し、
ノードの縦座標の設定のみに用いていた正規分布を
横座標の設定にも用いた。
この結果、フィールドの中央により多くのノードが配置された。
図18：縦・横方向に正規分布を用いたノード配置例（分散V=500）
図19：ノードの密集性が増大した場合の「倍率」の平均値
図20：ノードの密集性が増大した場合の「倍率」データ自体の分散
図21：ノードの密集性が増大した場合の「倍率」データの個数
(ノード分布の分散が2000と16000のとき)
結果：
前節(ノード数400、ノード配置方法は縦：正規分布、横：一様分布である場合)
の結果と相違が見られるのは、
分散が1000以下になった時の倍率データである。
全体のノード数が減少し、偏りが小さくなった時（図12）では
分散1000以下での結果が上がり、グラフが単調減少になった。
反対に、全体のノード数が増加した時（図15）や横座標にも正規分布を適用した場合（図19）、
つまり、ノードの偏りが高くなった時は
分散1000以下の結果が下がり、代わって分散2000付近で極大となった。
ノード配置の偏りと移動基地局の効果には
関連性があることが明確となった。
4.4 考察
ノード群の移動方向に共通性がある場合、
移動基地局の移動パターンが単純であっても、効果をあげられることがわかった。
ノード配置の初期条件によって効果を上げられる条件は様々に変化した。
5 まとめ
本稿では、マルチホップ無線網の連結性を高めるために
移動基地局がどのような移動アルゴリズムを用いれば効果的かを検討してきた。
2つのノード移動モデルにおける検討を通じて、
ノードの配置・移動パターンにランダム性が強い場合、
移動基地局が移動する効果は低いが、
ノード群の移動方向に規則性がある場合、
ノードの位置情報を収集した後、ノードの密度が高い地点を追従することによって、
効果を挙げられることがわかった。
このように、移動基地局は条件により有効に機能することが明らかとなった。
このことの応用として、
例えば、トンネル内で道路の混雑情報を集め、
1日のうち混雑する時間帯、もしくは1年のうちで混雑する季節がわかっているとき、
そのタイミングに合わせて移動基地局を起動させれば効果をあげられる、
などの状況が考えられる。
これからの課題として、
移動基地局が移動すべき場所を決定する条件の定式化を行うことや、
より現実的な基地局システム、ノード移動モデルにおける移動基地局の移動方法の検討、
などが挙げられる。
付録
シミュレーションプログラム
本研究で使用したシミュレーションプログラムを示す。
資料1・3.1（移動基地局の目標設定）で用いたプログラム
/* 目標の比較。(空いている所へ向かう・混んでいるところへ向かう) */
/* データ出力をリダイレクトしてお使いください */
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define NODE_MAX 400 // ノード数
#define NODE_EXIST_P 0.011 // 各格子点にノードが存在する確率
#define SIMULATE_TIME 1000 // 本体内部でループを回す回数(ノードを動かす秒数)
#define CALL_SIMULATE_TIME 1 // 外からシミュレーション本体を呼ぶ回数
#define BS_DIST_DIRECT 25.0 // 移動基地局の腕（直接通信できる距離）の長さ
#define NODE_DIST_DIRECT 5.0 // ノードの腕の長さ
#define CELL_WIDTH 200.0 // 観測を行う場所をここではセルと呼ぶ・セルの横の長さ
#define CELL_HEIGHT 200.0 // セルラ方式のセルとは関係ない・セルの縦の長さ
/* 座標軸に関連する値であることを示す構造体 */
struct axis{
double x;
double y;
};
/* ノードの属性を表す構造体の宣言 */
struct node_property{
struct axis coord; /* 座標 */
struct axis velocity; /* 速度 */
double dist_direct; /* 直接通信できる距離 */
/* 連結性を調査する時に使う */
int counted; /* そのノードを数えたか */
char move_type; /* ノードの動き方タイプ */
};
/* 関数プロトタイプ */
int simulate_main(struct node_property node[], int number_of_node, char BS_move_type);
struct axis table_center_of_block9(int number);
int mini_net_node_count(struct node_property node[], int number_of_node);
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes);
double distance_point(struct axis p1, struct axis p2);
int p_return(double p);
double rnd(void);
/* 関数プロトタイプここまで */
int main(void){
int i, j, k, ret;
int top_loop; /* シミュレーション本体を何度も呼び出す用 */
int number_of_node_out;
int bs_dist_direct_out;
double temp_vel_x; /* ノードに速度を設定するときx軸方向の速さを一時的に格納
(後でノードの速さを1に設定するため) */
struct node_property node_out[NODE_MAX];
struct node_property node_out_backup[NODE_MAX];
/* 乱数列の開始点を設定 */
srand(time(NULL) % 65536);
/* 試行回数だけ以下を繰り返す */
/* 移動基地局がないときの値を出してファイル0に記録 */
/* 動きのパターン1でシミュレート、平均値を出してファイル0に追記 */
/* ノードが動いてたら元に戻して */
/* 動きのパターン2でシミュレート、平均値を出してファイル0に追記 */
/* ノードが動いてたら元に戻して */
/* ……… */
/* 全部の動きパターンでやり終えたら、ノードのばらまき直し */
for(top_loop= 0 ; top_loop < CALL_SIMULATE_TIME ; top_loop++){
/* 変数の初期化 */
for(i = 0 ; i < NODE_MAX ; i++){
/* 念のためノードの位置を初期化しておく(セルの外に) */
node_out[i].coord.x = CELL_WIDTH + 1.0;
node_out[i].coord.y = CELL_HEIGHT + 1.0;
};
/*-----------ノードの配置・速度設定-----------*/
/* ノードを配置する場所を決定 */
/* ノードは格子点(xy座標とも整数の点)にのみ配置する */
i = 0; j = 0; number_of_node_out = 0;
while(number_of_node_out < NODE_MAX && j < CELL_HEIGHT){
/* 確率Pでその格子点にノードが存在するかどうか決める */
if(p_return(NODE_EXIST_P) == 1){
node_out[number_of_node_out].coord.x = (double)i;
node_out[number_of_node_out].coord.y = (double)j;
number_of_node_out++;
};
if(++i >= CELL_WIDTH){
j++;
i = 0;
}
};
/* ノードの速度等 */
/* 速さの絶対値が1になるように */
for(i = 0 ; i < NODE_MAX ; i++){
temp_vel_x = rnd();
node_out[i].velocity.x = temp_vel_x;
node_out[i].velocity.y = sqrt(1.0 - temp_vel_x * temp_vel_x);
node_out[i].dist_direct = NODE_DIST_DIRECT;
};
/* 初期化したノード群の場所等バックアップ */
for(i = 0 ; i < NODE_MAX ; i++){
node_out_backup[i] = node_out[i];
};
printf("n:ノードの少「ない」ブロックへ移動\n");
ret = simulate_main(node_out, number_of_node_out, 'n');
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i] = node_out_backup[i];
};
printf("a:ノードのたくさん「ある」ブロックへ移動\n");
ret = simulate_main(node_out, number_of_node_out, 'a');
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i] = node_out_backup[i];
};
};
return 0;
}
int simulate_main(struct node_property node[], int number_of_node, char BS_move_type){
int i,j,k,l; /* ループカウンタ */
int main_loop; /* ループカウンタ */
int ret = 0; /* 関数の戻り値用+最大ネット数平均値を求める用 */
int block_point; /* ノードがどのブロックに属するか判定用 */
int nodes_in_block[9]; /* ブロック内にあるノード数を格納する */
int MAX_block ; /* ノード数が一番多いブロックの番号 */
int MIN_block ; /* ノード数が一番少ないブロックの番号 */
int temp_MAX ; /* 中間生成物 */
int temp_MIN ; /* 中間生成物 */
struct node_property movableBS; /* 移動基地局の情報を格納 */
/*---------------------初期設定------------------------------*/
/*------------移動基地局の定義------------*/
movableBS.coord.x = CELL_WIDTH / 2.0 ;
movableBS.coord.y = CELL_HEIGHT / 2.0 ;
movableBS.move_type = BS_move_type;
movableBS.dist_direct = BS_DIST_DIRECT;
/* ノード番号が最後のものを移動基地局とする */
/* プログラム上では移動基地局を「ちょっとすごいノード」として扱う */
if(number_of_node >= NODE_MAX){
node[number_of_node - 1] = movableBS;
}else{
node[number_of_node++] = movableBS;
};
/*---------------------シミュレーション本体-------------------------*/
for (main_loop = 0 ; main_loop < SIMULATE_TIME ; main_loop++){
/* 移動する */
/* 外に出たノード反対側からでてくる */
for(i = 0 ; i < number_of_node - 1 ; i++){
node[i].coord.x += node[i].velocity.x;
node[i].coord.y += node[i].velocity.y;
if (node[i].coord.x > CELL_WIDTH) node[i].coord.x -= CELL_WIDTH;
if (node[i].coord.y > CELL_HEIGHT) node[i].coord.y -= CELL_HEIGHT;
if (node[i].coord.x < 0.0) node[i].coord.x += CELL_WIDTH;
if (node[i].coord.y < 0.0) node[i].coord.y += CELL_HEIGHT;
};
/* 各ブロックにあるノード数を数える */
/* ブロックを9個に分け、左上→右下へ0から8までふる */
/* こういうこと
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
*/
for(i = 0; i < 9; i++){
nodes_in_block[i] = 0;
}
block_point = 0;
for(i = 0 ; i < number_of_node - 1 ; i++){ /* 全ノードループ（非BS）*/
block_point = 0;
if(node[i].coord.x < (CELL_WIDTH / 3.0)){
block_point += 0;
}else if(node[i].coord.x < (CELL_WIDTH / 3.0 * 2.0)){
block_point += 1;
}else if(node[i].coord.x < CELL_WIDTH){
block_point += 2;
}
if(node[i].coord.y < (CELL_HEIGHT / 3.0)){
block_point += 0;
}else if(node[i].coord.y < (CELL_HEIGHT / 3.0 * 2.0)){
block_point += 3;
}else if(node[i].coord.y < CELL_HEIGHT){
block_point += 6;
}
nodes_in_block[block_point]++;
};
MAX_block = 0;
MIN_block = 0;
temp_MAX = nodes_in_block[0];
temp_MIN = nodes_in_block[0];
for(i = 0; i < 9; i++){
if(nodes_in_block[i] > temp_MAX){
MAX_block = i;
temp_MAX = nodes_in_block[i];
};
if(nodes_in_block[i] < temp_MIN){
MIN_block = i;
temp_MIN = nodes_in_block[i];
};
};
/*----------移動基地局の移動--------------*/
switch(movableBS.move_type){
case 'n':{ /* move_type == n はもっとも人気が「ない」ブロックへ移動 */
movableBS.coord.x = table_center_of_block9(MIN_block).x;
movableBS.coord.y = table_center_of_block9(MIN_block).y;
}break;
case 'a':{ /* move_type == a はもっとも人気が「ある」ブロックへ移動 */
movableBS.coord.x = table_center_of_block9(MAX_block).x;
movableBS.coord.y = table_center_of_block9(MAX_block).y;
}break;
};
/* 移動基地局の「ノード化」 */
node[number_of_node - 1] = movableBS;
/* ミニネットワーク群のノード数の最大値を求める */
ret = mini_net_node_count(node, number_of_node);
printf("%d\n", ret);
}; /* main_loop ここまで*/
return (ret);
} /* simulate_main()ここまで */
/* ブロック分けしたときの、ブロックの中央の座標値を格納するテーブル */
/* 9分割版 */
struct axis table_center_of_block9(int number){
struct axis temp_4_return;
switch(number){
case 0:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 1:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 2:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 3:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 4:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 5:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 6:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 7:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 8:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
};
return temp_4_return;
};
/* ミニネットワーク群のノード数の最大値を求める */
int mini_net_node_count(struct node_property node[], int number_of_node){
int i, j;
int ret = 0 ; /* node_countup関数の戻り値格納用 */
int temp = 0 ; /* この関数の戻り値用 */
if(number_of_node != 0){
for(i = 0; i < number_of_node; i++){
for(j = 0; j < NODE_MAX; j++){
node[j].counted = FALSE;
};
temp = node_countup(node,number_of_node, i, 0);
if (ret < temp) {
ret = temp;
};
}
}else{
ret = 0;
};
return(ret);
};
/* node_countup 実際にミニネットワークのノード数を数える関数(再帰) */
/* 引数：node_in[] 処理対象のノード情報を格納した配列
number_of_node_in 処理対象のノードの個数
source 数える起点となるノード番号
counted_nodes すでに数えたノードの数 */
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes){
int target; /* 通信できるかどうかを調べる相手のノード番号 */
int ret; /* 返ってくる値、の意味 */
int new_counted_nodes; /* 数えたノード数を更新した後の値 */
double dis; /* 距離、の意味 */
node_in[source].counted = TRUE;
new_counted_nodes = counted_nodes + 1;
for(target = 0; target < number_of_node_in; target++){
dis = distance_point(node_in[source].coord, node_in[target].coord);
if(dis < node_in[source].dist_direct && node_in[target].counted != TRUE){
ret = node_countup(node_in, number_of_node_in, target, new_counted_nodes);
new_counted_nodes = ret;
};
};
return new_counted_nodes;
};
/* 2点の距離を返す関数 */
double distance_point(struct axis p1, struct axis p2){
return sqrt( (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y) );
}
/* 確率 p で 1, 確率 1 - p で 0を返す関数 */
int p_return(double p){
int ret;
double rn;
/* 0以上1未満の範囲の実数乱数を生成 */
rn = rnd();
if (rn < p) ret = 1;
else ret = 0;
return ret;
};
/* 0以上1未満の範囲の実数乱数を生成 */
double rnd(void){
return rand() / (RAND_MAX + 0.1);
};
資料2・3.2（移動基地局の移動パターン比較）で用いたプログラム
/* 移動パターンの比較。(固定・四角く巡回・混んでいる方へ) */
/* データ出力をリダイレクトしてお使いください */
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define NODE_MAX 400 // ノード数
#define NODE_EXIST_P 0.011 // 各格子点にノードが存在する確率
#define SIMULATE_TIME 2000 // 本体内部でループを回す回数(ノードを動かす秒数)
#define CALL_SIMULATE_TIME 1 // 外からシミュレーション本体を呼ぶ回数
#define BS_DIST_DIRECT 25.0 // 移動基地局の腕（直接通信できる距離）の長さ
#define NODE_DIST_DIRECT 5.0 // ノードの腕の長さ
#define CELL_WIDTH 200.0 // 観測を行う場所をここではセルと呼ぶ・セルの横の長さ
#define CELL_HEIGHT 200.0 // セルラ方式のセルとは関係ない・セルの縦の長さ
/* 座標軸に関連する値であることを示す構造体 */
struct axis{
double x;
double y;
};
/* ノードの属性を表す構造体の宣言 */
struct node_property{
struct axis coord; /* 座標 */
struct axis velocity; /* 速度 */
double dist_direct; /* 直接通信できる距離 */
/* 連結性を調査する時に使う */
int counted; /* そのノードを数えたか */
char move_type; /* ノードの動き方タイプ */
};
/* 関数プロトタイプ */
int simulate_main(struct node_property node[], int number_of_node, struct axis bs_start_position, char BS_move_type);
struct axis table_center_of_block9(int number);
int mini_net_node_count(struct node_property node[], int number_of_node);
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes);
double distance_point(struct axis p1, struct axis p2);
int p_return(double p);
double rnd(void);
/* 関数プロトタイプここまで */
int main(void){
int i, j, k, ret;
int top_loop; /* シミュレーション本体を何度も呼び出す用 */
int number_of_node_out;
int bs_dist_direct_out;
double temp_vel_x; /* ノードに速度を設定するときx軸方向の速さを一時的に格納
(後でノードの速さを1に設定するため) */
struct axis bs_start_position_out; /* 移動基地局の初期位置 */
struct node_property node_out[NODE_MAX];
struct node_property node_out_backup[NODE_MAX];
/* 乱数列の開始点を設定 */
srand(time(NULL) % 65536);
/* 試行回数だけ以下を繰り返す */
/* 移動基地局がないときの値を出してファイル0に記録 */
/* 動きのパターン1でシミュレート、平均値を出してファイル0に追記 */
/* ノードが動いてたら元に戻して */
/* 動きのパターン2でシミュレート、平均値を出してファイル0に追記 */
/* ノードが動いてたら元に戻して */
/* ……… */
/* 全部の動きパターンでやり終えたら、ノードのばらまき直し */
for(top_loop= 0 ; top_loop < CALL_SIMULATE_TIME ; top_loop++){
/* 変数の初期化 */
for(i = 0 ; i < NODE_MAX ; i++){
/* 念のためノードの位置を初期化しておく(セルの外に) */
node_out[i].coord.x = CELL_WIDTH + 1.0;
node_out[i].coord.y = CELL_HEIGHT + 1.0;
};
/*-----------ノードの配置・速度設定-----------*/
/* ノードを配置する場所を決定 */
/* ノードは格子点(xy座標とも整数の点)にのみ配置する */
i = 0; j = 0; number_of_node_out = 0;
while(number_of_node_out < NODE_MAX && j < CELL_HEIGHT){
/* 確率Pでその格子点にノードが存在するかどうか決める */
if(p_return(NODE_EXIST_P) == 1){
node_out[number_of_node_out].coord.x = (double)i;
node_out[number_of_node_out].coord.y = (double)j;
number_of_node_out++;
};
if(++i >= CELL_WIDTH){
j++;
i = 0;
}
};
/* ノードの速度等 */
/* 速さの絶対値が1になるように */
for(i = 0 ; i < NODE_MAX ; i++){
temp_vel_x = rnd();
node_out[i].velocity.x = temp_vel_x;
node_out[i].velocity.y = sqrt(1.0 - temp_vel_x * temp_vel_x);
node_out[i].dist_direct = NODE_DIST_DIRECT;
};
/* 初期化したノード群の場所等バックアップ */
for(i = 0 ; i < NODE_MAX ; i++){
node_out_backup[i] = node_out[i];
};
bs_start_position_out.x = CELL_WIDTH / 2.0;
bs_start_position_out.y = CELL_HEIGHT / 2.0;
printf("f:動かない(fixed)\n");
ret = simulate_main(node_out, number_of_node_out, bs_start_position_out, 'f');
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i] = node_out_backup[i];
};
bs_start_position_out.x = CELL_WIDTH / 4.0;
bs_start_position_out.y = CELL_HEIGHT / 4.0;
printf("r:四角く回る\n");
ret = simulate_main(node_out, number_of_node_out, bs_start_position_out, 'r');
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i] = node_out_backup[i];
};
bs_start_position_out.x = CELL_WIDTH / 2.0;
bs_start_position_out.y = CELL_HEIGHT / 2.0;
printf("a:ノードのたくさん「ある」ブロックへ移動\n");
ret = simulate_main(node_out, number_of_node_out, bs_start_position_out, 'a');
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i] = node_out_backup[i];
};
};
return 0;
}
int simulate_main(struct node_property node[], int number_of_node, struct axis bs_start_position, char BS_move_type){
int i,j,k,l; /* ループカウンタ */
int main_loop; /* ループカウンタ */
int ret = 0; /* 関数の戻り値用+最大ネット数平均値を求める用 */
int block_point; /* ノードがどのブロックに属するか判定用 */
int nodes_in_block[9]; /* ブロック内にあるノード数を格納する */
int MAX_block ; /* ノード数が一番多いブロックの番号 */
int MIN_block ; /* ノード数が一番少ないブロックの番号 */
int temp_MAX ; /* 中間生成物 */
int temp_MIN ; /* 中間生成物 */
int move_phase = 1; /* 四角く動く場合の今動いているフェイズを表す */
int moved_in_phase = 0; /* そのフェイズで動いた歩数 */
struct node_property movableBS; /* 移動基地局の情報を格納 */
/*---------------------初期設定------------------------------*/
/*------------移動基地局の定義------------*/
movableBS.coord = bs_start_position;
movableBS.move_type = BS_move_type;
movableBS.dist_direct = BS_DIST_DIRECT;
/* ノード番号が最後のものを移動基地局とする */
/* プログラム上では移動基地局を「ちょっとすごいノード」として扱う */
if(number_of_node >= NODE_MAX){
node[number_of_node - 1] = movableBS;
}else{
node[number_of_node++] = movableBS;
};
/*---------------------シミュレーション本体-------------------------*/
for (main_loop = 0 ; main_loop < SIMULATE_TIME ; main_loop++){
/* 移動する */
/* 外に出たノード反対側からでてくる */
for(i = 0 ; i < number_of_node - 1 ; i++){
node[i].coord.x += node[i].velocity.x;
node[i].coord.y += node[i].velocity.y;
if (node[i].coord.x > CELL_WIDTH) node[i].coord.x -= CELL_WIDTH;
if (node[i].coord.y > CELL_HEIGHT) node[i].coord.y -= CELL_HEIGHT;
if (node[i].coord.x < 0.0) node[i].coord.x += CELL_WIDTH;
if (node[i].coord.y < 0.0) node[i].coord.y += CELL_HEIGHT;
};
/* 各ブロックにあるノード数を数える */
/* ブロックを9個に分け、左上→右下へ0から8までふる */
/* こういうこと
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
*/
for(i = 0; i < 9; i++){
nodes_in_block[i] = 0;
}
block_point = 0;
for(i = 0 ; i < number_of_node - 1 ; i++){ /* 全ノードループ（非BS）*/
block_point = 0;
if(node[i].coord.x < (CELL_WIDTH / 3.0)){
block_point += 0;
}else if(node[i].coord.x < (CELL_WIDTH / 3.0 * 2.0)){
block_point += 1;
}else if(node[i].coord.x < CELL_WIDTH){
block_point += 2;
}
if(node[i].coord.y < (CELL_HEIGHT / 3.0)){
block_point += 0;
}else if(node[i].coord.y < (CELL_HEIGHT / 3.0 * 2.0)){
block_point += 3;
}else if(node[i].coord.y < CELL_HEIGHT){
block_point += 6;
}
nodes_in_block[block_point]++;
};
MAX_block = 0;
MIN_block = 0;
temp_MAX = nodes_in_block[0];
temp_MIN = nodes_in_block[0];
for(i = 0; i < 9; i++){
if(nodes_in_block[i] > temp_MAX){
MAX_block = i;
temp_MAX = nodes_in_block[i];
};
if(nodes_in_block[i] < temp_MIN){
MIN_block = i;
temp_MIN = nodes_in_block[i];
};
};
/*----------移動基地局の移動--------------*/
switch(movableBS.move_type){
case 'f':{ /* move_type = f は動かないとき */
/* 何もしない */
}break;
case 'r':{ /* move_type == r は四角を描いて動くとき */
/* 動く方向を変えるかどうか判定 */
if(move_phase == 1 && moved_in_phase >= CELL_WIDTH / 2.0){
move_phase = 2; moved_in_phase = 0;
};
if(move_phase == 2 && moved_in_phase >= CELL_HEIGHT / 2.0){
move_phase = 3; moved_in_phase = 0;
};
if(move_phase == 3 && moved_in_phase >= CELL_WIDTH / 2.0){
move_phase = 4; moved_in_phase = 0;
};
if(move_phase == 4 && moved_in_phase >= CELL_HEIGHT / 2.0){
move_phase = 1; moved_in_phase = 0;
};
switch(move_phase){ /* 左上をスタートして右回りで四角を描く */
case 1:{ /* 右に動くフェイズ */
movableBS.coord.x += 1.0;
}break;
case 2:{ /* 下に動くフェイズ */
movableBS.coord.y += 1.0;
}break;
case 3:{ /* 左に動くフェイズ */
movableBS.coord.x += -1.0;
}break;
case 4:{ /* 上に動くフェイズ */
movableBS.coord.y += -1.0;
}break;
};
moved_in_phase++;
}break;
case 'a':{ /* move_type == a はもっとも人気が「ある」ブロックへ移動 */
movableBS.coord.x = table_center_of_block9(MAX_block).x;
movableBS.coord.y = table_center_of_block9(MAX_block).y;
}break;
};
/* 移動基地局の「ノード化」 */
node[number_of_node - 1] = movableBS;
/* ミニネットワーク群のノード数の最大値を求める */
ret = mini_net_node_count(node, number_of_node);
printf("%d\n", ret);
}; /* main_loop ここまで*/
return (ret);
} /* simulate_main()ここまで */
/* ブロック分けしたときの、ブロックの中央の座標値を格納するテーブル */
/* 9分割版 */
struct axis table_center_of_block9(int number){
struct axis temp_4_return;
switch(number){
case 0:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 1:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 2:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 3:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 4:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 5:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 6:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 7:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 8:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
};
return temp_4_return;
};
/* ミニネットワーク群のノード数の最大値を求める */
int mini_net_node_count(struct node_property node[], int number_of_node){
int i, j;
int ret = 0 ; /* node_countup関数の戻り値格納用 */
int temp = 0 ; /* この関数の戻り値用 */
if(number_of_node != 0){
for(i = 0; i < number_of_node; i++){
for(j = 0; j < NODE_MAX; j++){
node[j].counted = FALSE;
};
temp = node_countup(node,number_of_node, i, 0);
if (ret < temp) {
ret = temp;
};
}
}else{
ret = 0;
};
return(ret);
};
/* node_countup 実際にミニネットワークのノード数を数える関数(再帰) */
/* 引数：node_in[] 処理対象のノード情報を格納した配列
number_of_node_in 処理対象のノードの個数
source 数える起点となるノード番号
counted_nodes すでに数えたノードの数 */
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes){
int target; /* 通信できるかどうかを調べる相手のノード番号 */
int ret; /* 返ってくる値、の意味 */
int new_counted_nodes; /* 数えたノード数を更新した後の値 */
double dis; /* 距離、の意味 */
node_in[source].counted = TRUE;
new_counted_nodes = counted_nodes + 1;
for(target = 0; target < number_of_node_in; target++){
dis = distance_point(node_in[source].coord, node_in[target].coord);
if(dis < node_in[source].dist_direct && node_in[target].counted != TRUE){
ret = node_countup(node_in, number_of_node_in, target, new_counted_nodes);
new_counted_nodes = ret;
};
};
return new_counted_nodes;
};
/* 2点の距離を返す関数 */
double distance_point(struct axis p1, struct axis p2){
return sqrt( (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y) );
}
/* 確率 p で 1, 確率 1 - p で 0を返す関数 */
int p_return(double p){
int ret;
double rn;
/* 0以上1未満の範囲の実数乱数を生成 */
rn = rnd();
if (rn < p) ret = 1;
else ret = 0;
return ret;
};
/* 0以上1未満の範囲の実数乱数を生成 */
double rnd(void){
return rand() / (RAND_MAX + 0.1);
};
資料3・4.1（情報を蓄積した後移動基地局が移動を開始する場合）で用いたプログラム
/* 向きを全ノード一定に、速さも同じ。*/
/* データ出力をリダイレクトしてお使いください */
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define NODE_MAX 400 // ノード数
#define NODE_EXIST_P 0.0101 // 各格子点にノードが存在する確率
#define SIMULATE_TIME 402 // 本体内部でループを回す回数(ノードを動かす秒数)
#define CALL_SIMULATE_TIME 1 // 外からシミュレーション本体を呼ぶ回数
#define BS_DIST_DIRECT 25.0 // 移動基地局の腕（直接通信できる距離）の長さ
#define NODE_DIST_DIRECT 5.0 // ノードの腕の長さ
#define CELL_WIDTH 200.0 // 観測を行う場所をここではセルと呼ぶ・セルの横の長さ
#define CELL_HEIGHT 200.0 // セルラ方式のセルとは関係ない・セルの縦の長さ
/* 座標軸に関連する値であることを示す構造体 */
struct axis{
double x;
double y;
};
/* ノードの属性を表す構造体の宣言 */
struct node_property{
struct axis coord; /* 座標 */
struct axis velocity; /* 速度 */
double dist_direct; /* 直接通信できる距離 */
/* 連結性を調査する時に使う */
int counted; /* そのノードを数えたか */
char move_type; /* ノードの動き方タイプ */
};
/* 関数プロトタイプ*/
int simulate_main(struct node_property node[], int number_of_node, char BS_move_type);
struct axis table_center_of_block9(int number);
int mini_net_node_count(struct node_property node[], int number_of_node);
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes);
double distance_point(struct axis p1, struct axis p2);
int p_return(double p);
double rnd(void);
/* 関数プロトタイプここまで */
int main(void){
int i, j, k, ret;
int top_loop; /* シミュレーション本体を何度も呼び出す用 */
int number_of_node_out;
int bs_dist_direct_out;
struct node_property node_out[NODE_MAX];
struct node_property node_out_backup[NODE_MAX];
/* 乱数列の開始点を設定 */
srand(time(NULL) % 65536);
for(top_loop= 0 ; top_loop < CALL_SIMULATE_TIME ; top_loop++){
/* 変数の初期化 */
for(i = 0 ; i < NODE_MAX ; i++){
/* 念のためノードの位置を初期化しておく(セルの外に) */
node_out[i].coord.x = CELL_WIDTH + 1.0;
node_out[i].coord.y = CELL_HEIGHT + 1.0;
};
/*-----------ノードの配置・速度設定-----------*/
/* 今のところ整数の場所にしかいない */
/* ノードを配置する場所 */
i = 0; j = 0; number_of_node_out = 0;
while(number_of_node_out < NODE_MAX && j < CELL_HEIGHT){
/* 確率Pでノードが存在するかどうか決める */
if(p_return(NODE_EXIST_P) == 1){
node_out[number_of_node_out].coord.x = (double)i;
node_out[number_of_node_out].coord.y = (double)j;
number_of_node_out++;
};
if(++i >= CELL_WIDTH){
j++;
i = 0;
}
};
/* ノードの速度等 */
/* ノードは横方向に動くのみ */
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i].velocity.x = 1.0;
node_out[i].velocity.y = 0.0;
node_out[i].dist_direct = NODE_DIST_DIRECT;
};
/* 初期化したノード群の場所等バックアップ */
for(i = 0 ; i < NODE_MAX ; i++){
node_out_backup[i] = node_out[i];
};
printf("b:開始200秒後に移動開始\n");
ret = simulate_main(node_out, number_of_node_out, 'b');
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i] = node_out_backup[i];
};
};
return 0;
}
int simulate_main(struct node_property node[], int number_of_node, char BS_move_type){
int i,j,k,l; /* ループカウンタ */
int main_loop; /* ループカウンタ */
int ret = 0; /* 関数の戻り値用+最大ネット数平均値を求める用 */
int block_point; /* ノードがどのブロックに属するか判定用 */
int nodes_in_block[9]; /* ブロック内にあるノード数を格納する */
int MAX_block ; /* ノード数が一番多いブロックの番号 */
int MIN_block ; /* ノード数が一番少ないブロックの番号 */
int temp_MAX ; /* 中間生成物 */
int temp_MIN ; /* 中間生成物 */
int win_the_MAX_block[9]; /* ノード配置調査時、一番ノード数が多いブロックに選ばれた回数 */
int MAX_of_MAX_block; /* 一番ノード数が多いブロックに選ばれた回数が一番多かったブロック */
struct node_property movableBS; /* 移動基地局の情報を格納 */
/*---------------------初期設定------------------------------*/
for(i = 0; i < 9; i++){
win_the_MAX_block[i] = 0;
};
/*------------移動基地局さんの定義------------*/
movableBS.coord.x = CELL_WIDTH / 2.0 ;
movableBS.coord.y = CELL_HEIGHT / 2.0 ;
movableBS.move_type = BS_move_type;
movableBS.dist_direct = BS_DIST_DIRECT;
/* ノード番号が最後のものを移動基地局とする */
/* プログラム上では移動基地局を「ちょっとすごいノード」として扱う */
if(number_of_node >= NODE_MAX){
node[number_of_node - 1] = movableBS;
}else{
node[number_of_node++] = movableBS;
};
/*---------------------シミュレーション本体-------------------------*/
for (main_loop = 0 ; main_loop < SIMULATE_TIME ; main_loop++){
/* 移動する */
/* 外に出たノードはどうしよう？*/
/* 案1：反対側からでてくる */
for(i = 0 ; i < number_of_node - 1 ; i++){
node[i].coord.x += node[i].velocity.x;
node[i].coord.y += node[i].velocity.y;
if (node[i].coord.x > CELL_WIDTH) node[i].coord.x -= CELL_WIDTH;
if (node[i].coord.y > CELL_HEIGHT) node[i].coord.y -= CELL_HEIGHT;
if (node[i].coord.x < 0.0) node[i].coord.x += CELL_WIDTH;
if (node[i].coord.y < 0.0) node[i].coord.y += CELL_HEIGHT;
};
/* 各ブロックにあるノード数のみ数える */
/* ブロックを9個に分け、左上→右下へ0から8までふる */
/* こういうこと
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
*/
for(i = 0; i < 9; i++){
nodes_in_block[i] = 0;
}
block_point = 0;
for(i = 0 ; i < number_of_node - 1 ; i++){ /* 全ノードループ（非BS）*/
block_point = 0;
if(node[i].coord.x < (CELL_WIDTH / 3.0)){
block_point += 0;
}else if(node[i].coord.x < (CELL_WIDTH / 3.0 * 2.0)){
block_point += 1;
}else if(node[i].coord.x < CELL_WIDTH){
block_point += 2;
}
if(node[i].coord.y < (CELL_HEIGHT / 3.0)){
block_point += 0;
}else if(node[i].coord.y < (CELL_HEIGHT / 3.0 * 2.0)){
block_point += 3;
}else if(node[i].coord.y < CELL_HEIGHT){
block_point += 6;
}
nodes_in_block[block_point]++;
};
MAX_block = 0;
MIN_block = 0;
temp_MAX = nodes_in_block[0];
temp_MIN = nodes_in_block[0];
for(i = 0; i < 9; i++){
if(nodes_in_block[i] > temp_MAX){
MAX_block = i;
temp_MAX = nodes_in_block[i];
};
if(nodes_in_block[i] < temp_MIN){
MIN_block = i;
temp_MIN = nodes_in_block[i];
};
};
if(main_loop < 200){
win_the_MAX_block[MAX_block]++; /* 今回、ノードが一番多かったブロックの
「最多ブロックに選ばれた回数」を1増やす。*/
};
if(main_loop == 200){
temp_MAX = win_the_MAX_block[0];
MAX_of_MAX_block = 0;
for(i = 0; i < 9; i++){
if(win_the_MAX_block[i] > temp_MAX){
MAX_of_MAX_block = i;
temp_MAX = win_the_MAX_block[i];
};
};
};
/*----------移動基地局さんの瞬間移動--------------*/
switch(movableBS.move_type){
case 'b':{ /* move_type == b はblock賞に選ばれたブロックへ移動すること */
if(main_loop == 200){
movableBS.coord.x = table_center_of_block9(MAX_of_MAX_block).x;
movableBS.coord.y = table_center_of_block9(MAX_of_MAX_block).y;
};
}break;
};
/* 移動基地局の「ノード化」 */
node[number_of_node - 1] = movableBS;
/* ミニネットワーク群のノード数の最大値を求める */
ret = mini_net_node_count(node, number_of_node);
printf("%d\n", ret);
}; /* main_loop ここまで*/
return (ret);
} /* simulate_main()ここまで */
/* ブロック分けしたときの、ブロックの中央の座標値を格納するテーブル */
/* 9分割版 */
struct axis table_center_of_block9(int number){
struct axis temp_4_return;
switch(number){
case 0:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 1:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 2:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 3:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 4:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 5:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 6:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 7:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 8:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
};
return temp_4_return;
};
/* ミニネットワーク群のノード数の最大値を求める */
int mini_net_node_count(struct node_property node[], int number_of_node){
int i, j;
int ret = 0 ; /* node_countup関数の戻り値格納用 */
int temp = 0 ; /* この関数の戻り値用 */
if(number_of_node != 0){
for(i = 0; i < number_of_node; i++){
for(j = 0; j < NODE_MAX; j++){
node[j].counted = FALSE;
};
temp = node_countup(node,number_of_node, i, 0);
if (ret < temp) {
ret = temp;
};
}
}else{
ret = 0;
};
return(ret);
};
/* node_countup 実際にミニネットワークのノード数を数える関数(再帰) */
/* 引数：node_in[] 処理対象のノード情報を格納した配列
number_of_node_in 処理対象のノードの個数
source 数える起点となるノード番号
counted_nodes すでに数えたノードの数 */
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes){
int target; /* 通信できるかどうかを調べる相手のノード番号 */
int ret; /* 返ってくる値、の意味 */
int new_counted_nodes; /* 数えたノード数を更新した後の値 */
double dis; /* 距離、の意味 */
node_in[source].counted = TRUE;
new_counted_nodes = counted_nodes + 1;
for(target = 0; target < number_of_node_in; target++){
dis = distance_point(node_in[source].coord, node_in[target].coord);
if(dis < node_in[source].dist_direct && node_in[target].counted != TRUE){
ret = node_countup(node_in, number_of_node_in, target, new_counted_nodes);
new_counted_nodes = ret;
};
};
return new_counted_nodes;
};
/* 2点の距離を返す関数 */
double distance_point(struct axis p1, struct axis p2){
return sqrt( (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y) );
}
/* 確率 p で 1, 確率 1 - p で 0を返す関数 */
int p_return(double p){
int ret;
double rn;
/* 0以上1未満の範囲の実数乱数を生成 */
rn = rnd();
if (rn < p) ret = 1;
else ret = 0;
return ret;
};
/* 0以上1未満の範囲の実数乱数を生成 */
double rnd(void){
return rand() / (RAND_MAX + 0.1);
};
資料4・4.2（ノード配置を意図的に偏らせた場合）と
4.3（様々なノード配置に対する検討）で用いたプログラム（兼用）
/*
偏りのあるノード配置の場合。縦方向は正規分布・横方向は一様）
データ出力がファイル出力に変更になりました。
定数 NODE_MAX と NODE_EXIST_P を変更することでノード密度を変更可。
*/
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define PI 3.141592
#define NODE_MAX 400 // ノード数
#define NODE_EXIST_P 0.0101 // 各格子点にノードが存在する確率
#define SIMULATE_TIME 402 // 本体内部でループを回す回数(ノードを動かす秒数）
#define CALL_SIMULATE_TIME 100 // 外からシミュレーション本体を呼ぶ回数
#define BS_DIST_DIRECT 25.0 // 移動基地局の腕（直接通信できる距離）の長さ
#define NODE_DIST_DIRECT 5.0 // ノードの腕の長さ
#define CELL_WIDTH 200.0 // 観測を行う場所をここではセルと呼ぶ・セルの横の長さ
#define CELL_HEIGHT 200.0 // セルラ方式のセルとは関係ない・セルの縦の長さ
/* 座標軸に関連する値であることを示す構造体 */
struct axis{
double x;
double y;
};
/* ノードの属性を表す構造体の宣言 */
struct node_property{
struct axis coord; /* 座標 */
struct axis velocity; /* 速度 */
double dist_direct; /* 直接通信できる距離 */
/* 連結性を調査する時に使う */
int counted; /* そのノードを数えたか */
char move_type; /* ノードの動き方タイプ（に使う予定） */
};
/* 2個のintを返すため、こんな構造体を宣言する */
typedef struct int_2{
int value1;
int value2;
} Int2;
/* 関数プロトタイプ */
Int2 simulate_main(struct node_property node[], int number_of_node, char BS_move_type);
struct axis table_center_of_block9(int number);
int mini_net_node_count(struct node_property node[], int number_of_node);
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes);
double distance_point(struct axis p1, struct axis p2);
int p_return(double p);
double rnd(void);
double box_muller(double variance);
/* 関数プロトタイプここまで */
int main(void){
int i, j, k ;
int top_loop; /* シミュレーション本体を何度も呼び出す用 */
int more_top_loop; /* 分散を変えて何度もシミュレーションを繰り返す用 */
int number_of_node_out;
int bs_dist_direct_out;
Int2 ret;
char file_name_write[50]; /* データを書き込むファイル名 */
double node_variance; /* ノードのばらまき方の分散 */
double node_temp_y; /* ノードのy座標一時格納（範囲を超えていないかチェック用） */
FILE *fp_out;
struct node_property node_out[NODE_MAX];
struct node_property node_out_backup[NODE_MAX];
struct axis pole_array[POLE_MAX];
/* 乱数列の開始点を設定 */
srand(time(NULL) % 65536);
node_variance = 32000.0;
for(more_top_loop = 0 ; more_top_loop < 6 ; more_top_loop++){
node_variance /= 2.0;
sprintf(file_name_write, "data_013_V%d" ,(int)node_variance);
fp_out = fopen(file_name_write,"a");
if (NULL == fp_out){
fprintf(stderr, "File %s をオープン失敗！\n\n", file_name_write);
exit(2);
};
for(top_loop= 0 ; top_loop < CALL_SIMULATE_TIME ; top_loop++){
/* 変数の初期化 */
for(i = 0 ; i < NODE_MAX ; i++){
/* 念のためノードの位置を初期化しておく(セルの外に) */
node_out[i].coord.x = CELL_WIDTH + 1.0;
node_out[i].coord.y = CELL_HEIGHT + 1.0;
};
/*-----------ノードの配置・速度設定-----------*/
/* ノードを配置する場所 */
i = 0; j = 0; number_of_node_out = 0;
while(number_of_node_out < NODE_MAX && j < CELL_HEIGHT){
/* 確率Pでノードが存在するかどうか決める */
if(p_return(NODE_EXIST_P) == 1){
/* x軸は今まで通り一様、 */
/* y軸の値のみ正規乱数に従うようにする */
/* 乱数が0未満や200以上だったらやり直す機構 */
do{
node_temp_y = box_muller(node_variance);
}while((node_temp_y < 0.0) || (node_temp_y > 199.99));
node_out[number_of_node_out].coord.x = (double)i;
node_out[number_of_node_out].coord.y = node_temp_y;
number_of_node_out++;
};
if(++i >= CELL_WIDTH){
j++;
i = 0;
}
};
/* ノードの速度等 */
for(i = 0 ; i < NODE_MAX ; i++){
node_out[i].velocity.x = 1.0;
node_out[i].velocity.y = 0.0;
node_out[i].dist_direct = NODE_DIST_DIRECT;
};
if(top_loop == 0){
fprintf(fp_out, "ただいまの分散 %.0lf\n\n", node_variance);
fprintf(fp_out, "使用(200)前 使用(200)後 倍率\n");
};
ret = simulate_main(node_out, number_of_node_out, 'b');
fprintf(fp_out, "%d %d %.7f\n", ret.value1 , ret.value2, (double)ret.value2 / (double)ret.value1 );
};/* top_loopここまで */
fclose(fp_out);
};/* more_top_loopここまで */
return 0;
}
Int2 simulate_main(struct node_property node[], int number_of_node, char BS_move_type)
{
int i,j,k,l; /* ループカウンタ */
int main_loop; /* ループカウンタ */
int mini_net = 0; /* ミニネットの大きさを調べた値を一時的に */
int block_point; /* ノードがどのブロックに属するか判定用 */
int nodes_in_block[9]; /* ブロック内にあるノード数を格納する */
int MAX_block ; /* ノード数が一番多いブロックの番号 */
int MIN_block ; /* ノード数が一番少ないブロックの番号 */
int temp_MAX ; /* 中間生成物 */
int temp_MIN ; /* 中間生成物 */
int win_the_MAX_block[9]; /* MAX_block賞に選ばれた回数を格納 */
int MAX_of_MAX_block; /* MAX_block賞に選ばれた回数が一番多かったブロック */
Int2 ret; /* 関数の戻り値格納 */
struct node_property movableBS; /* 移動基地局の情報を格納 */
/*---------------------初期設定------------------------------*/
ret.value1 = 0;
ret.value2 = 0;
for(i = 0; i < 9; i++){
win_the_MAX_block[i] = 0;
};
/*------------移動基地局さんの定義(初期位置)------------*/
movableBS.coord.x = CELL_WIDTH / 6.0;
movableBS.coord.y = CELL_HEIGHT / 6.0;
movableBS.move_type = BS_move_type;
movableBS.dist_direct = BS_DIST_DIRECT;
/* ノード番号が最後のものを移動基地局とする */
/* プログラム上では移動基地局を「ちょっとすごいノード」として扱う */
if(number_of_node >= NODE_MAX){
node[number_of_node - 1] = movableBS;
}else{
node[number_of_node++] = movableBS;
};
/*---------------------シミュレーション本体-------------------------*/
for (main_loop = 0 ; main_loop < SIMULATE_TIME ; main_loop++){
/* 移動する */
/* 外に出たノードは反対側からでてくる */
for(i = 0 ; i < number_of_node - 1 ; i++){
node[i].coord.x += node[i].velocity.x;
node[i].coord.y += node[i].velocity.y;
if (node[i].coord.x > CELL_WIDTH) node[i].coord.x -= CELL_WIDTH;
if (node[i].coord.y > CELL_HEIGHT) node[i].coord.y -= CELL_HEIGHT;
if (node[i].coord.x < 0.0) node[i].coord.x += CELL_WIDTH;
if (node[i].coord.y < 0.0) node[i].coord.y += CELL_HEIGHT;
};
/* 各ブロックにあるノード数のみ数える */
/* ブロックを9個に分け、左上→右下へ0から8までふる */
/* こういうこと
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
*/
for(i = 0; i < 9; i++){
nodes_in_block[i] = 0;
}
block_point = 0;
for(i = 0 ; i < number_of_node - 1 ; i++){ /* 全ノードループ（非BS）*/
block_point = 0;
if(node[i].coord.x < (CELL_WIDTH / 3.0)){
block_point += 0;
}else if(node[i].coord.x < (CELL_WIDTH / 3.0 * 2.0)){
block_point += 1;
}else if(node[i].coord.x < CELL_WIDTH){
block_point += 2;
}
if(node[i].coord.y < (CELL_HEIGHT / 3.0)){
block_point += 0;
}else if(node[i].coord.y < (CELL_HEIGHT / 3.0 * 2.0)){
block_point += 3;
}else if(node[i].coord.y < CELL_HEIGHT){
block_point += 6;
}
nodes_in_block[block_point]++;
};
MAX_block = 0;
MIN_block = 0;
temp_MAX = nodes_in_block[0];
temp_MIN = nodes_in_block[0];
for(i = 0; i < 9; i++){
if(nodes_in_block[i] > temp_MAX){
MAX_block = i;
temp_MAX = nodes_in_block[i];
};
if(nodes_in_block[i] < temp_MIN){
MIN_block = i;
temp_MIN = nodes_in_block[i];
};
};
if(main_loop < 200){
win_the_MAX_block[MAX_block]++; /* 今回、ノードが一番多かったブロックの
「最多ブロックに選ばれた回数」を1増やす。*/
};
if(main_loop == 200){
temp_MAX = win_the_MAX_block[0];
MAX_of_MAX_block = 0;
for(i = 0; i < 9; i++){
if(win_the_MAX_block[i] > temp_MAX){
MAX_of_MAX_block = i;
temp_MAX = win_the_MAX_block[i];
};
};
};
/*----------移動基地局さんの瞬間移動--------------*/
switch(movableBS.move_type){
case 'b':{ /* move_type == b はblock賞に選ばれたブロックへ移動すること */
if(main_loop == 200){
movableBS.coord.x = table_center_of_block9(MAX_of_MAX_block).x;
movableBS.coord.y = table_center_of_block9(MAX_of_MAX_block).y;
};
}break;
};
/* 移動基地局の「ノード化」 */
node[number_of_node - 1] = movableBS;
/* ミニネットワーク群のノード数の最大値を求める */
mini_net = mini_net_node_count(node, number_of_node);
if((main_loop >= 0) && (main_loop <= 199)){
ret.value1 += mini_net;
}
if((main_loop >= 200) && (main_loop <= 399)){
ret.value2 += mini_net;
}
}; /* main_loop ここまで*/
return (ret);
} /* simulate_main()ここまで */
/* ブロック分けしたときの、ブロックの中央の座標値を格納するテーブル */
/* 9分割版 */
struct axis table_center_of_block9(int number){
struct axis temp_4_return;
switch(number){
case 0:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 1:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 2:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0;
}break;
case 3:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 4:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 5:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 2.0;
}break;
case 6:{
temp_4_return.x = CELL_WIDTH / 6.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 7:{
temp_4_return.x = CELL_WIDTH / 2.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
case 8:{
temp_4_return.x = CELL_WIDTH / 6.0 * 5.0;
temp_4_return.y = CELL_HEIGHT / 6.0 * 5.0;
}break;
};
return temp_4_return;
};
/* ミニネットワーク群のノード数の最大値を求める */
int mini_net_node_count(struct node_property node[], int number_of_node){
int i, j;
int ret = 0 ; /* node_countup関数の戻り値格納用 */
int temp = 0 ; /* この関数の戻り値用 */
if(number_of_node != 0){
for(i = 0; i < number_of_node; i++){
for(j = 0; j < NODE_MAX; j++){
node[j].counted = FALSE;
};
temp = node_countup(node,number_of_node, i, 0);
if (ret < temp) {
ret = temp;
};
}
}else{
ret = 0;
};
return(ret);
};
/* node_countup 実際にミニネットワークのノード数を数える関数(再帰) */
/* 引数：node_in[] 処理対象のノード情報を格納した配列
number_of_node_in 処理対象のノードの個数
source 数える起点となるノード番号
counted_nodes すでに数えたノードの数 */
int node_countup(struct node_property node_in[], int number_of_node_in, int source, int counted_nodes){
int target; /* 通信できるかどうかを調べる相手のノード番号 */
int ret; /* 返ってくる値、の意味 */
int new_counted_nodes; /* 数えたノード数を更新した後の値 */
double dis; /* 距離、の意味 */
node_in[source].counted = TRUE;
new_counted_nodes = counted_nodes + 1;
for(target = 0; target < number_of_node_in; target++){
dis = distance_point(node_in[source].coord, node_in[target].coord);
if(dis < node_in[source].dist_direct && node_in[target].counted != TRUE){
ret = node_countup(node_in, number_of_node_in, target, new_counted_nodes);
new_counted_nodes = ret;
};
};
return new_counted_nodes;
};
/* 2点の距離を返す関数 */
double distance_point(struct axis p1, struct axis p2){
return sqrt( (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y) );
}
/* 確率 p で 1, 確率 1 - p で 0を返す関数 */
int p_return(double p){
int ret;
double rn;
/* 0以上1未満の範囲の実数乱数を生成 */
rn = rnd();
if (rn < p) ret = 1;
else ret = 0;
return ret;
};
/* 0以上1未満の範囲の実数乱数を生成 */
double rnd(void){
return rand() / (RAND_MAX + 0.1);
};
/* 正規乱数を発生させる関数(Box-Muller法) */
/* 引数:variance は分散 */
double box_muller(double variance){
double mu = 100.0; /* 平均μ = 100 */
return (sqrt(-2 * variance * log(rnd())) * sin(2 * PI * rnd()) + mu);
}
