ミリ波アドホック無線アクセスシステムによって

中央大学大学院理工学研究科情報工学専攻 修士論文

ミリ波アドホック無線アクセスシステムによって 構成される通信ネットワークトポロジーの評価

Evaluation of Communication Network Topology Constructed by Millimeter-Wave Ad-Hoc

Wireless Access System

入学年度

年 学籍番号   

佐々木  重彰

指導教員    田口 東 教授

2004

年

月

概要

  アドホックネットワークにおいては，端末の移動に伴って，無線ネットワークは常に動的 に変化するため，技術開発は無線ネットワークの動的な変化を考慮した上でおこなう必要が ある．そこで，本研究においては，無線ネットワークの動的な変化を解析することを目的と している．

初めに，渋谷駅周辺の建物情報を付加した街区の道路ネットワーク上を端末が移動するモ デルにおけるシミュレーション実験の前提や手順，結果を評価するための指標などについて の説明をおこなう．

次に，結果例をいくつか示し，結果を評価するために定義した指標から，無線ネットワー クの動的な変化を推測し，また，無線ネットワークの動的な変化を視覚的に捉え易い形で可 視化する．

最後に，シミュレーション実験の結果をもとに，様々な理論を用いることによって，アド

ホックネットワークにおける無線ネットワークの動的な変化を数理モデルから考察し，シミ

ュレーション実験における考察結果と比較する．

目次

第

章

序論

1.1  研究の背景...1

1.2  研究の目的...1

第

章

アドホックネットワーク

2.1  アドホックネットワークの特徴...3

2.1.1  インフラフリー...3

2.1.2  マルチホップ無線通信...4

2.1.3  動的なトポロジーの変化...5

2.2  ミリ波帯...5

2.3  ミリ波アドホック無線アクセスシステム...6

第

章

シミュレーション実験

3.1  実験における前提...7

3.1.1  端末に関する前提...7

3.1.2  通信可能端末率の定義...8

3.2  実験における対象領域...9

3.3  実験の概要...10

3.3.1  単位時間...10

3.3.2  端末の移動（実験モデル）... 11

3.3.3  端末の移動（ランダムウォークモデル）... 11

3.3.4  通信が可能な他の端末の探索...12

3.3.5  実験の手順...13

3.4  計算結果例（実験モデル）...13

3.4.1  通信可能端末率の変化...14

3.4.2  ネットワークの変化...15

3.5  計算結果例（ランダムウォークモデル）...23

3.5.1  通信可能端末率の変化...23

3.5.2  ネットワークの変化...24

3.6  両モデルにおける結果の比較...28

第

章

結果の解析

4.1  領域の中心部への交通量の集中...29

4.2  各リンクが移動経路に含まれる頻度差...33

4.3  端末の移動に伴う密度分布の変化...35

4.3.1  偏微分方程式...35

4.3.2  差分方程式...36

4.3.3  実験モデルにおける密度分布の解析...37

4.3.4  ランダムウォークモデルにおける密度分布の解析...45

4.4  解析結果の考察...47

第

章 結論

5.1  まとめ...48 5.2  今後の課題...49

謝辞

参考文献

第 1 章   

序論 

1.1  研究の背景  

  近年，通信技術の急速な発展によって，インターネットを介した共有ホワイトボー ドシステムやマルチプレーヤーオンラインゲームなど，複数のユーザが同じ目的を達 成するために，ネットワークを利用して協調作業をおこなうためのネットワーク強調 作業アプリケーションや，前方自動車追尾システムや追突軽減ブレーキなど，無線通 信 技 術 を 利 用 す る こ と に よ っ て 自 動 車 の 運 転 者 を サ ポ ー ト す る

（

Transport System

：高度道路交通システム）といった新しい技術が次々と産みだされて

いる．

  一方，ノートパソコンや

（

），携帯電話などの携帯 端 末 （ 以 下 端 末 と 表 記 ） の 普 及 や 高 機 能 化 に 伴 っ て ， 無 線

（

Network

）や

（短距離無線通信）などに代表される短距離無線通信技術も著

しく発達しており，いつでも，どこでも，誰でも，通信技術を利用したサービスを受 けることのできる，ユビキタス社会の実現がその現実味を帯びてきている．また，ユ ビキタス社会の実現の中核を成す技術として，アドホックネットワーク

に関する研

究

が盛んにおこなわれている．

アドホックネットワークとは，交換局や基地局といった固定通信インフラに依存せ ず，交換機能をもった端末間で動的に構成される自律分散型ネットワークであり，ア ドホックネットワークにおいては，端末同士が直接通信することのできない場合でも，

他の端末を中継することによって通信が可能である．今のところ，戦場や会議室，災 害時になどのへ応用といった，固定通信インフラを利用することができないような状 況下において，既存の固定通信インフラを補完するような役割が主に考えられている が，技術を昇華させることによって，次世代無線通信の主流となる可能性を秘めた画 期的な技術である．

アドホックネットワークにおいて，無線

や

といった様々な電波の使 用が考えられているが，その中でも，ミリ波帯（周波数：

〜

，波長：

〜

の電波）を利用したミリ波アドホック無線アクセスシステムは，ミリ波帯の広 帯域伝送や無線機器の小型化が可能という特徴の優位性から，その実用化が期待され ている．

1.2  研究の目的 

  アドホックネットワークにおける技術的問題点として，端末の移動によってネット

ワークトポロジー（以下トポロジーと表記）が動的に変化し，構成される無線ネット

ワーク（以後ネットワークと表記）も時々刻々と形を変えるために，安定した通信経

路の保持が非常に困難であるということが挙げられる．そこで，アドホックネットワ ークにおいては，ネットワークの動的な変化を前提とした技術開発が必要となる．

しかし，アドホックネットワークに関する研究の多くは，トポロジーやネットワー クの動的な変化を考慮に入れたルーティングプロトコルや通信方式の開発が主であり，

トポロジーやネットワークの動的な変化自体の解析はあまりされていない．また，シ ミュレーション実験においても，

次元や

次元の格子状領域を端末が移動するモデ ルが大半であり，実際の地理情報を用いたモデルにおけるシミュレーション実験はほ とんどおこなわれていない．

  そこで，本研究では，アドホックネットワークにおける動的なネットワークの変化

を，地理情報システムを利用したシミュレーション実験と数理モデルの両面から考察

すし，その結果を考察する．

第 2 章   

アドホックネットワーク  

  アドホックネットワークとは，交換局や基地局といった固定の通信インフラに依存するこ となく，交換機能をもつ端末のみで構成される自律分散型のネットワークである．アドホッ ク（Ad-Hoc）とは，”その場限りの”という意味であり，端末の移動によってネットワーク が動的に変化し，その形を留めることがないことからアドホックネットワークと呼ばれてい る． 

本章においては，アドホックネットワークの特徴やミリ波アドホック無線アクセスシステ ムに関する説明をおこなう． 

2.1  アドホックネットワークの特徴 

  アドホックネットワークの特徴として，

•

固定通信インフラが不要（インフラフリー）

•

マルチホップ無線通信

•

トポロジーの動的な変化

が挙げられる．本節においては，これらの特徴について述べる．

2.1.1  インフラフリー    従来の無線通信においては，

•

端末等の陸上移動局との通信を行うため，陸上に開設する移動しない無線局で ある基地局

•

基地局から送信された電気信号を受けとり，送信先の端末がどの交換局，基地 局の近くにいるかを調べて，そこへ電気信号を送信するまでの仲介役をなす交 換局

といった固定通信インフラに依存したかたちで通信をおこなっている．図

に携帯電話に

おける通信の様子を示す．基地局の通信可能領域内に存在する送信元の端末が送信した電気

信号は，基地局から交換局へと転送され，交換局において，送信先の端末が現在どの交換局，

基地局の近くにいるかを調べて，電気信号を転送する．そして，基地局から送信元の電気信 号を受信した送信先の端末は，逆の経路で送信元の端末へ電気信号を返信することによって，

通信することが可能となる．

送信元の電波 送信先の電波 端末

図

  携帯電話における通信の様子

  一方，アドホックネットワークにおいては，端末自体が交換機能をもっているので，端末 の通信可能領域内に存在する他の端末とは，基地局や交換局などの固定通信インフラに依存 することなく，直接通信が可能である．その様子を図

に示す．

送信元の電波 送信先の電波 端末

図

2.1.2   マルチホップ無線通信 

  アドホックネットワークにおいて，端末が発する電波の伝達可能な距離は，比較的短いと

いえる約

〜

が想定されており，端末が直接通信することが可能な他の端末の個数

には限りがある．しかし，端末同士が直接通信することのできない場合でも，他の端末がパ

ケットを中継することによって通信することが可能であり（図

），このマルチホップ無

線通信によって，大規模なネットワークの構築が可能となる．

送信元の電波 送信先の電波 端末

図

  マルチホップ無線通信

2.1.3  トポロジーの動的な変化 

  アドホックネットワークにおいては，端末は常に移動しているので，トポロジーは時々 刻々と変化し，ネットワークはその姿を留めることはない．よって，安定した通信経路の保 持は非常に困難であり，図

のように，ある瞬間においては，通信経路が確立されており，

通信することが可能であった端末同士（端末

と端末

）が，次の瞬間には通信が不可能 になるということが頻繁に起こる．

送信先の電波 送信元の電波

端末 無線リンク

B

D

C A

B

C

D A

図

2.2  ミリ波帯 

〜

の周波数帯のことをまとめてミリ波帯と呼び，その電波の波長は

〜

である．ミリ波帯は，伝送速度

以上もの広帯域伝送が可能であり，無線機器の小 型化ができるという特徴をもつ．

その中でも，

〜

の周波数帯を

帯と呼び，ミリ波帯の特徴に加えて，酸素 による吸収減衰が特に多いために，遠くまで到達せず他の電波による干渉が起こりにくい．

また，電波の直線性が非常に強いために秘匿性にも優れているという特徴をもつ．

については，

年

月に電気通信技術審議会

帯の周波数の電波を使用する無線設 備の技術的条件

が答申され，超高速無線

，映像多重伝送等を簡単に構築することが可 能な無線システムを提供するために，免許を必要としない

特定省電力無線局

として一般利 用に開放されていることから，大容量伝送が必要なシステムへの利用が期待されている．

2.3  ミリ波アドホック無線アクセスシステム 

  ミリ波帯を利用したアドホック無線アクセスシステムのことをミリ波アドホック無線アク

セスシステムと呼び，アドホックネットワークとミリ波帯の特徴を併せもつ．本研究におい

ては，前節に記述した

帯の特徴の優位性から，

帯を利用したミリ波アドホッ

ク無線アクセスシステムを想定する．

第 3 章   

シミュレーション実験  

  本章においては，建物情報を付加した街区の道路ネットワーク上を端末が移動する モデルにおける，シミュレーション実験の前提や対象領域，実験手順についての説明 をおこない，いくつかの計算例を示す．

シミュレーション実験は，道路ネットワーク上にランダムに配置された端末が，ラ ンダムに与えられた目的地へと最短経路を通って移動するモデル（実験モデル）と，

道路ネットワークの各ノードで端末が移動方向をランダムに選ぶモデル（ランダムウ ォークモデル）について行う．ここでは，シミュレーション実験における対象領域や 前提条件などについて記述する．なお，実験モデルとランダムウォークモデルとでは，

対象領域や前提条件は変わらず，シミュレーション実験の手順（端末の移動）のみが 異なるものとする． 

3.1  実験における前提 

  本節では，シミュレーション実験をおこなう上での前提や，シミュレーション実験 の結果を評価する指標の定義などについて述べる．

3.1.1  端末に関する前提 

本研究においては，全ての端末に関して，その端末を中心とした半径

の円形 領域を通信可能領域とする（図

）．

150m

図

  端末の通信可能領域の定義 通信可能領域

端末

また，第

章で述べたとおり，

帯の特徴の優位性から，

帯を利用した ミリ波アドホック無線アクセスシステムを想定する．よって，電波の大きい伝播減衰 性や強い直線性から，建物によって電波は遮断されるものとし，電波の干渉，回折な どは考慮に入れないものとする（図

）．端末の移動速度に関しては，全端末につい て，人の平均的な移動速度である

端末

以下 建物

図

3.1.2  通信可能端末率の定義 

  シミュレーション実験の結果を評価する指標である，通信可能端末率の定義につい て述べる．

いま，ある領域内に

個の端末が存在し，時刻 （

^{）において，ある端} 末

^（ ）が通信することの可能な他の端末の総数（通信可能端末数）を

（

m j=1,2,L,

aij a_ij =0,1,L,m−1

）で表すとするとき，通信可能端末率を

( ) 1 (

1

≤

≤

−

=

∑

=

i m

j ij

i a m m A

A

      （

）

で定義する．この のとる値によって，領域内に構成されるネットワークに関する情 報が得られる（表

，図

）． が最小値の

をとるときは，領域内に構成される ネットワークの総数は，領域内に存在する端末の総数と等しくなる．つまり，各ネッ トワークの規模は最小であり，各端末は他の全ての端末と通信することが不可能であ るということを表す．逆に， が最大値である

をとるときは，領域内には唯一最大 ネットワークだけが構成され，各端末はすべての他の端末と通信することが可能であ るということを表す．

Ai

Ai

Ai

表

の値による領域内に構成されるネットワークの変化

ネットワークの規模 ネットワーク数

Ai

^→小 小さい 多い

Ai →大

大きい 少ない

Ai

_大

小

図

のとる値によるネットワークの変化の様子

3.2  実験における対象領域 

  渋谷駅を中心として東西方向，南北方向ともに約

の範囲内を対象領域とする．

道路ネットワークと建物情報のデータは，昭文社の「

」を利用して抽出 した．渋谷駅を中心として東西方向，南北方向ともに約

の範囲内における，道 路ネットワークと建物情報を抽出した結果，道路ネットワークのノード数

個，

リンク数

本，建物数約

棟となった．その様子を図

に示す．

ここで，対象領域は有限領域であると仮定し，端末の領域外への移動や，領域外か

らの端末の流入はなく，端末総数の増減はないものとする．

道路 建物

Ν

0m 250m

図

  対象領域における建物情報を付加した道路ネットワーク

500m

3.3  実験の概要 

  本節では，シミュレーション実験における，

•

単位時間

•

端末の移動

•

通信が可能な他の端末の探索

•

実験の手順 に関しての説明をおこなう．

3.3.1 単位時間 

  シミュレーション実験における単位時間（

ステップの時間幅）は

秒

，つまり，

端末は

ステップで約

移動するものとする．これは，領域内に構成されるネッ

トワークの変化を可視化する際に，単位時間を変化させ，どの位の単位時間がネット

ワークの変化を捉えるのに適しているかを視覚的に評価した結果である．

3.3.2  端末の移動（実験モデル） 

  実験モデルにおいては，以下に記すⅰ

ⅴの要領で，端末は移動するものとする．

i.

各端末に移動する目的地を与える．ここで，目的地の候補には道路ネッ トワークの全てのノード上が該当し，各端末にはランダムに選択したあ るノード番号が目的地として与えられる．

ii.

目的地を与えられた各端末の移動経路を定める．ここで，端末は目的地 まで最短経路を通って移動するものとする．なお，最短経路の探索には

dijkstra

法を用いる．

iii.

端末は道路ネットワーク上を

の速度で移動するものとする．

iv.

目的地に到着した端末には，新たな目的地が与えられる．

v.

以下ⅱ〜ⅳを繰り返す．

3.3.3  端末の移動（ランダムウォークモデル） 

  ランダムウォークモデルにおいては，以下に記すⅰ

ⅳの要領で，端末は移動するも のとする．

i.

各端末は道路ネットワークの各ノード上でランダムに移動方向を選択す る．例えば，あるノードを始点とするリンクが 本ある場合には，各リ ンク上をそれぞれ

e

1

の確率で移動するものとする（図

）．

ii.

移動方向を選択した各端末は，次のノード上に到着するまで，道路ネッ トワーク上を

の速度で移動するものとする．

iii.

次のノード上に到着した端末は，新たな進行方向をランダムに選択する．

iv.

以下ⅱ〜ⅲを繰り返す．

13 13 13

図

の場合のランダムウォークにおける端末の移動

3.3.4  通信が可能な他の端末の探索 

  ある時刻 （

）において，ある端末

が通信することの可能な他の端末 を探索する手順を以下に記す．以下の探索によって，通信可能端末数

が求まる．

i.

対象領域を

辺が約

の正方形状のメッシュ毎に分割し，各メッシュ 内に含まれる建物を探索する．

ii.

各メッシュ内に含まれる端末を探索する．

iii.

同一メッシュ内に存在する端末の全組み合わせについて，端末と端末を

結ぶ線分と建物を構成する線分との線分交差判定[3,4]をおこなうことに よって，同一メッシュ内に存在する，各端末が直接通信することのでき る他の端末を探索する．ここで，線分交差判定は電波が建物に遮断され るかどうかを調べることに相当する．

iv.

直接通信することのできる他の端末が存在する可能性があるメッシュ間 の端末の全組み合わせについてのみ，端末間の

距離を計算し，

Euclid

距離が

る線分との線分交差判定をおこなうことによって，他のメッシュ内に存

在する，各端末が直接通信することのできる他の端末を探索する．

v.

直接通信することはできないが，他の端末を経由することによって通信 することのできる他の端末を探索する．なお，探索には深さ優先探索を 用いる．

3.3.5  実験の手順 

  本節では，

節〜

節に記述したことを踏まえた上で実験の手順についての説 明をおこなう．実験の手順は以下のとおりである．

i.

対象領域における道路ネットワークのノード上にランダムに 個の端末 を配置する．

m

ii.

初期状態（

ステップ目，

）において，各端末が通信することの可 能な他の端末を，

節に記述した要領で探索し，通信可能端末数 を 求める．

a₀j

iii.

初期状態における通信可能端末率

を，式（

）を用いて計算する．

iv.

実験モデルにおいては，端末を

節に記述した要領で，ランダムウォ ークモデルにおいては，端末を

節に記述した要領で，単位時間分

（

節）だけ移動させる．

v.

実験の手順ⅱ〜ⅲと同じように，

ステップ目における通信可能端末数 を求め，通信可能端末率 を計算する．

a₁j A₁

vi.

以下 ステップまで実験の手順ⅳ〜ⅴを繰り返し，各ステップにおける 通信可能端末数 を求め，通信可能端末率 を計算する．

n

aij A_ij

3.4  実験モデルにおける計算結果例 

本節においては，

節に端末の移動について記述した，実験モデルにおけるシミ ュレーション実験の計算例として，

例

  領域内に

個の端末が存在する（

^）

例

  領域内に

個の端末が存在する（

^）

{

とした場合における，通信可能端末率 の変化を表すグラフと領域内に構成されるネ ットワークの様子を表す図を示す．また，この

例において

Ai

=1000

n

^{とする．つまり，}

シミュレーション時間は約

分間である．

3.4.1  通信可能端末率の変化 

  実験モデルにおける の値の変化を図

（例

）と図

（例

）にそれぞれ示す．

図

から，

ステップ目においては，約

と非常に小さかった の値が，端末の 移動に伴って，大きくなっていくことがわかる．そして，ある程度大きくなったあと

の の値は約

付近に落ち着き，大きな変化はみられなくなる．つまり，

ステ

ップ目においては，領域内の各端末は，大半の他の端末と通信することができなかっ たが，端末の移動に伴って，各端末における通信可能端末数が増加していき，そして，

ある程度端末が移動し，各端末が約半数の他の端末と通信することが可能となったあ とには，各端末の通信可能端末数には大幅な増減がなくなるということがわかる．

Ai

Ai

Ai

  次に，例

における の値の変化を表すグラフである図

より，

ステップ目にお いては，約

ほどであった の値が，端末の移動に伴って，大きくなっていき，

ある程度大きくなったあとの の値は約

付近で落ち着き，大きな変化はみられ なくなる．これは，図

に示した例

における の値とほぼ同じ変化である．

Ai

Ai

Ai

Ai

また，実験モデルでは， の値が上記

例と異なる場合においても， の値が図

， 図

と似たような変化を示すので，表

，図

から，領域内に構成されるネット ワークの変化に関して以下のことが推測される．

m A_i

•

初めは，領域内に構成されるネットワークの数は多く，それぞれのネットワー クの規模は小さい．

↓

•

端末の移動に伴って，領域内に数多く構成されているネットワーク同士が結合 するために，ネットワークの数は減少していき，それぞれのネットワークの規模 は徐々に大きくなっていく．

↓

•

端末がある程度移動したあとは，領域内に構成されるネットワークの数と規模

には大きな変化がみられなくなる．

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 200 400 600 800 1000

ステップ数

通信可能端末率

図

  例

における通信可能端末率

の変化

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 200 400 600 800 1000

ステップ数

通信可能端末数

図

  例

における通信可能端末率

の変化

3.4.2  ネットワークの変化 

本節では，実験モデルにおける領域内に構成されるネットワークの様子を可視化ソ

フト

を用いて可視化した図を示す．

ここで，領域内に構成されるネットワークの様子を表す図において，四角は端末を，

端末と端末を結ぶ直線は端末間の繋がりをそれぞれ表し，四角や直線の色の違いは，

そのネットワークへ参加している端末の数を表しており，青に近づけば近づくほどネ ットワークへの参加端末数は少なくなり，逆に，赤に近づけば近づくほどネットワー クへの参加端末数は多くなるものとする．図

における，色の違いを表すカラーレ ジェンドの数字は，ネットワークへの参加端末数を領域内の総端末数で除した値であ る．実際には，カラーレジェンドの最大値は

であり，値が

以上をとる場合には四 角や直線の色は赤となる．

小 大

ネットワークの規模

0 0.8

図

  カラーレジェンド

  例

における

〜

ステップ目までの領域内に構成されるネットワークの様子を

図

〜

に，例

における

〜

ステップ目までの領域内に構成されるネットワ

ークの様子を図

〜

にそれぞれ示す．図から，

ステップ目においては領域内に 多数の小規模なネットワークが構成されているが，端末の移動に伴って，ネットワー ク同士が急速に結合し，徐々に大規模なネットワークが領域の中心部付近に構成され ていくことがネットワークの色の違いからわかる（

〜

ステップ目）．そして，あ る程度端末が移動したあとには，ネットワークに大幅な変化はみられなくなる（

〜

ステップ目）．

この結果は，

節における の値の変化から推測したネットワークの変化とほぼ 同様の変化であり， の値の変化から領域内に構成されるネットワークの様子を推測 することが可能であるということを示す．

Ai

Ai

また，可視化することによって，初めは領域内に一様な端末の密度分布が，その移 動に伴って，領域の中心にいくほど高くなることから，大規模なネットワークが領域 の中心部を中心として構成されることがわかり，例

と例

において，端末がある程 度移動したあとには，領域内に存在する総端末数の差による規模の違いはあるものの，

ほぼ同じような形のネットワークが構成されることがみてとれる．

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

図

0

図

  例

における

ステップ目のネットワークの様子

3.5  ランダムウォークにおける計算結果例 

本節においては，

節に端末の移動について記述した，ランダムウォークモデル におけるシミュレーション実験の計算例として，

節と同様の

例

  領域内に

個の端末が存在する（

^）

例

  領域内に

個の端末が存在する（

^）

とした場合における，通信可能端末率 の変化を表すグラフと領域内に構成されるネ ットワークの様子を表す図を示す．また，シミュレーション時間についても

節と 同様に， （約

分間）とする．

Ai

=1000 n

3.5.1  通信可能端末率の変化 

  ランダムウォークモデルにおける の値の変化を図

（例

）と図

（例

） にそれぞれ示す．図

，図

より，ランダムウォークモデルにおける の値には，

端末が移動に伴う大きな値の変化がみられないということがわかる．

Ai

Ai

また，ランダムウォークモデルでは， の値が上記

例と異なる場合においても，

の値が図

，図

と似たような変化を示すので，表

，図

から，領域内 に構成されるネットワークの変化に関して，

ステップ目におけるネットワークと端 末がある程度移動したあとのネットワークには大きな変化はみられないということが わかる．

m Ai

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 200 400 600 800 1000

ステップ数

通信可能端末率

図

  例

における通信可能端末率

の変化

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 200 400 600 800 1000

ステップ数

通信可能端末率

図

  例

における通信可能端末率

の変化

3.5.2  ネットワークの変化 

本節では，ランダムウォークモデルにおける領域内に構成されるネットワークの様 子を可視化ソフト

を用いて可視化した図を示す．ここで，図における四角 や直線及びそれぞれの色の違いは

節に記述したとおりである．

  例

における

〜

ステップ目までの領域内に構成されるネットワークの様子を

図

〜

に，例

における

〜

ステップ目までの領域内に構成されるネットワ

ークの様子を図

〜

にそれぞれ示す．各図から，ランダムウォークモデルにおい ては，端末の移動に伴う端末の密度分布の偏りは生じず，領域内に構成されるネット ワークにも大きな変化はみられないということがわかる．

この結果は，

節における の値の変化から推測したネットワークの変化とほぼ 同様の変化であり，

節に記述したとおり， の値の変化から領域内に構成される ネットワークの様子を推測することが可能であるということを示す．

Ai

Ai

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

0.8

0

図

における

ステップ目のネットワークの様子

0.8

0

図

  例

における

ステップ目のネットワークの様子

3.6  両モデルにおける結果の比較 

  ここで，本章の冒頭に記述したとおり，実験モデルとランダムウォークモデルとで

は端末の移動のみが異なる．よって，実験モデルにおける端末の密度が領域の中心に

いくほど高くなり，領域の中心部を中心とした大規模なネットワークが構成されると

いう現象は，3.3.2 節のランダムに与えられた目的地へと向かう端末の移動が原因で

生じているということが推測される．

第 4 章   

結果の解析  

第

章のシミュレーション実験から，建物情報を付加した街区の道路ネットワーク のノード上にランダムに配置された端末が，ランダムな目的地へと最短経路を通過し て移動するモデル（実験モデル）においては，端末がある程度移動したあとには，領 域の中心にいくほど端末の密度が高くなり，領域の中心部を中心とした大規模なネッ トワークが構成されるという結果を得た．また，ランダムウォークモデルにおける結 果との比較によって，実験モデルにおける端末の密度分布の変化とそれに伴うネット ワークの変化は，

節に記述した端末の移動が原因で生じていると推測した．本 章においては，いくつかの理論の説明と，その理論を用いた結果の解析をおこなう．

4.1  領域の中心部への交通量の集中 

有限な領域においては，中心部を経由する経路が選択されやすいために，領域の中 心部への交通量が多くなる．

節で得られた結果においても，領域の中心部に近づ けば近づくほど交通量は増加し，それに伴って，領域の中心部付近に大規模なネット ワークが構築される傾向にある．

  領域の中心部に端末が密集している場合や，領域の中心部を目的地として移動する 端末が多いといった特別な場合でなくても中心部の交通量は自然と多くなる．

  まず，図

のような長さ の

次元格子状領域

における交通量の分布を考える． 

  l

x

X O

B A

L  

  図

次元格子状領領域

ここで，領域

^{上には端末が密度}

で一様に分布し，交通は各端末が存在している 場所を始終点として，全ての始終点の組み合わせに対して発生すると仮定する．この とき，領域

の左端から距離

^{である地点}

を通過する交通量は領域内のあらゆる 始終点の組み合わせのうち，一方の点が領域

にあり，もう一方の点が領域

にあ るものなので，その交通量

は，

) ( )

(x x l x

s = 2 −

となる．したがって，

格子状領域の左端からの距離とその点を通過する交通量の関 係は，図

のような領域の中心

で最大値

を持つような

次曲線となる．

2 l2

l2 x

) (x s

l2

−

図

次元格子状領域

における交通量の分布

  次に，図

のような

辺の長さが

^{の正方形平面を}

辺の長さが の正方格子状 に区分した

次元正方格子状領域

w Ω

における交通量の分布を考える．

x y

w

l O ^{l 2}

2 l

2

−l 2

−l

図

次元正方格子状領域

いま，領域 上に端末が密度

で一様に分布し，交通は各端末が存在している地 点を始終点とし，全ての始終点の組み合わせに対して発生すると仮定する．また，ラ ンダムに目的地を選択し最短経路を経由するという端末の移動を扱い易くするために，

始点から終点までの端末の移動は，格子の縁上を各軸に沿った方向におこなわれ，多 くても左折

回で終点に辿り着くとする．図

に出発地点を ，目的地点 とした ときの端末の移動経路を示す．

Ω

X P

P

②

X

①

図

ここで，平面上の任意の点における交通量は定義することができないことから，領 域

^{上の任意の点}

における交通量の密度分布を考える．

∆x

p

A

B C

D

∆L

L

図

^上の交通

p

を通り，

^{軸と平行な線分}

^上の線分

^を図

の矢印方向に 通過する交通は，

① 領域

から領域

への交通

② 領域

^から領域

^への交通

③ 領域

^から領域

^への交通

の

通りであり，線分

を矢印方向に通過する交通量は，①の交通量，

x l y

l y l x

p p

p ⎟∆

⎠

⎜ ⎞

⎝⎛ −

⎟⎠

⎜ ⎞

⎝⎛ +

⎟⎠

⎜ ⎞

⎝⎛ +

2 2

2

^（

^）

②の交通量，

(

2

2 l y x

l y

p

p ⎟∆

⎠

⎜ ⎞

⎝⎛ −

⎟⎠

⎜ ⎞

⎝⎛ +

)    

      （

）

③の交通量，

x l y

l y l x

p p

p ⎟∆

⎠

⎜ ⎞

⎝⎛ −

⎟⎠

⎜ ⎞

⎝⎛ +

⎟⎠

⎜ ⎞

⎝⎛ +

2 2

2

        ^（

^） の和となるので，

^{とすると線分}

を矢印方向へ通過する交通量

は

dx l y

l x S

l

l p

L

∫

⎠

⎜⎜ ⎞

⎝

⎛ −

⎟⎠

⎜ ⎞

⎝⎛ +

= ²

2

2 2

4

2 2

        （

） となる．ここで，地点

における矢印方向の交通量の密度を

とおくと，

∫

= ²

2

1) ( 2

l

l L p

L s x dx

S

      （

） から，

⎟⎟⎠

⎜⎜ ⎞

⎝

⎛ −

⎟⎠

⎜ ⎞

⎝⎛ +

= ^{2 2}

4 2 2

)

( _{p p p}

L l y

l x x

s

      （

）

となる．式（

）と同様に，他方向の交通量の密度をそれぞれ求めると，地点

^に おける交通量の密度

は，

) (

2 )

,

(x y l³ l x² y²

s = − +

        （

） となる．したがって，領域 における交通量の密度は，原点で最大値 をとること から，領域の中心部に近づけば近づくほど，交通量の密度は高くなることがわかる

（図

）．

Ω l³

  図

と図

からわかるように，有限の領域内を端末が目的地をもって移動する ようなモデルにおいては，自然と中心部付近の交通量が増えることがわかる．本研究 の実験モデルにおいても，初めは領域の道路ネットワーク上に一様に分布していた端 末が，端末の移動に伴って，中心部付近に集まってきている．

よって，本研究の実験モデルにおいて端末の密度分布が偏る原因の

つとしては，

本節で示した領域の中心部への交通の集中が考えられる．

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

] )[

, (x y p

s ×

x

y

図

次元正方格子状領域

における交通量の密度分布

4.2  各リンクが移動経路に含まれる頻度差 

節で得られた結果から，端末がある程度移動すると，領域内のネットワークが ある特定の道路ネットワークに沿って構成されていることが見てとれる．これは，

3.3.2

節に記述した実験モデルにおける，ランダムに与えられた目的地に最短経路を

通って向かう端末の移動が強く影響していると考えられる．

そこで，

A)

道路ネットワークのノード上に

個の端末をランダムに配置する．

B)

端末にランダムに目的地を与える．

C)

目的地までの最短経路に含まれるリンクを調べる．

という手順の実験を複数回おこない，実験モデルにおける，各リンクが移動経路に含 まれる頻度差を調べる．

  実験の試行回数を

万回としたときの，各リンクが移動経路に含まれる頻度差を 表した図を図

に示す．ここで，リンクの色の違いは，各リンクが移動経路に含ま れる頻度差を表しており，赤色に近づけば近づくほど移動経路に含まれる頻度が高く，

逆に青色に近づけば近づくほど移動経路に含まれる頻度が低くなる．

図

と

節の図

〜

，図

〜

から，端末がある程度移動したあとの

領域内に構成されるネットワークは，図

において，移動経路に含まれる頻度が高 いとされているリンクを含んだ経路に沿って構成されていることがわかる．

よって，本研究の実験モデルにおいて端末の密度分布が偏る原因の

つとしては，

本節で示した各リンクが移動経路に含まれる頻度差が考えられる．

図

  各リンク移動経路に含まれる頻度差

4.3  端末の移動に伴う密度分布の変化 

  前節までに，

節の実験モデルにおける端末の移動に伴って，領域の中心部へ の交通の集中（

節）や各リンクが移動経路に含まれる頻度差（

節）が生じ，

その結果，領域内の端末の密度分布が偏ることによって，大規模なネットワークが領 域内に構成されるということを示した．つまり，アドホックネットワークにおけるト ポロジーやネットワークの動的な変化は，端末の移動に伴う，端末の密度分布の変化 によって生じていることから，端末の密度分布の変化を解析することは，アドホック ネットワークにおけるトポロジーやネットワークの動的な変化を解析することと同意 義であると考えられる．よって，本節では，端末の密度分布の変化を解析する．

4.3.1  偏微分方程式 

  いま，

次元の線形領域上を端末が左から右へ歩行するモデルにおける端末の流れ を考える

．ただし，端末の追い越しや領域外からの端末の流入，領域内からの端 末の流出は考慮に入れないものとする．ここで，

N1

^：時刻

に検査区間

内を歩行中の端末の個数

^：時刻

^{に検査区間}

内を歩行中の端末の個数

^：時刻

^から時刻

^{の間に地点}

^{を通過する端末の個数}

^：時刻

^から時刻

^{の間に地点}

^{を通過する端末の個数}

⎪⎪

⎪

⎩

⎪⎪

⎪

⎨

⎧

とすると，端末の

R

L N

N N

N₂ = ₁ + −

      （

） となる．式（

）は保存則の基本形であり，ある時刻に検査区間内を歩行中の車の 個数が既知である場合において，そこから適当な時間が経過する間に，検査区間内の 左右の境界から出入りする端末の個数を知ることができれば，時間が経過したあとの 検査区間内を歩行中の端末の個数を予測することが可能であるということを表してい る．

ここで，いま考えている検査区間の距離と比べて，各々の端末の大きさと端末間の 距離が十分に小さいと仮定すると，単位距離あたりの端末の個数として密度関数

) , (x t

ρ

^{が定義でき，}

∫

= ^{x dx}

x x t dx

N₁ ρ( , )

              （

）

∫

= ^{x dx}

x x t dt dx

N₂ ρ( , )

      （

） が成り立つ．また，右方向への端末の移動速度を

（左方向へ

^）とす ると，単位時間にある地点を通過する端末の個数は，

^{と の積として表} すことができるので，

) , (x t V

∫

= ^{t dt}

L t x t V x t dt

N ρ( , ) ( , )

      （

）

∫

= ^{t dt}

R t x dx t V x dx t dt

N ρ( , ) ( , )

        ^（

）

が成り立つ．ここで，検査区間を端末に対しては十分大きいが，

^{と の} 変化に対しては十分に小さくなるようにしていくと，式（

）〜式（

）はそれ ぞれ，

) , (x t V

      （

）

t x N₁=ρ( , )

dx dt t x N₂ =ρ( , + )

dt t x V N_L =ρ ( , )

dt t dx x V

N_R=ρ ( + , )

⎪⎪

⎪

⎩

⎪⎪

⎪

⎨

⎧

となる．よって，式（

）に式（

）を代入して，両辺を

で割ると，

) 0 , ( ) , ( )

, ( ) ,

( + − =

− + +

dx

t x V t dx x V dt

t x dt

t

x ρ ρ ρ

ρ

        （

）

を得る．ここで，

とし，各々を

展開すると，

0 )

( =

∂ + ∂

∂

∂ V

x

t ρ

ρ

      （

）

となり，式（

）を保存則の微分形と呼ぶ．

4.3.2  差分方程式 

  いま，ある時刻 t ^に

次元格子状領域上のある地点 x ^{に存在する端末が左へ}

^，右

へ

の確率で移動するモデルを考える．ここで，端末が

回移動したあとの地点 x ^に

おける端末の台数の期待値（密度）は，

) , 1 ( ) , 1 ( )

1 ,

(x t+ =p

ρ

ρ

ρ       （

）

という差分方程式で表すことができる．