The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

2C3-03

広域アドホック通信環境におけるネットワークの分析∗1

篠田孝祐∗1

野田五十樹∗2

Kosuke Shinoda

Itsuki Noda
∗2

北陸先端大学 知識科学研究科

Japan Advanced Institute of Science and Technology

産業技術研究所

National Institute of Advanced Industrial Science and Technology

In this paper, we propose a novel ad-hoc networking model that applies large-scale areas. We call this “largescale ad-hoc networking”. This networking model aims to use in disaster area, mainly and has applied its ah-hoc
networking’s advantage. Moreover, our proposal model uses social human relation-ship to decide routes of eachmessage. Moreover, we analize the network is construceted by our approach.

1.

はじめに移動できる範囲を想定するのが適当だと考える．それでも，既存のアドホックネットワークが想定している利用範囲からは広く，一般的な通信プロトコルでの通信は難しい．本研究では，
バケツリレーの様に端末に情報を停留させ，人の移動によって情報が移動する形の通信方法を考える．ただし，そのためには，2) のような情報伝達の確実性をあげるネットワーク構造を明らかにする必要がある．それと同時に，3) のようなトラフィックやメッセージのコピー数の制限などによって通信の飽和や情報伝達効率の低下を防ぐ必要がある．
既存のアドホックネットワークプロトコルには，Proactive型プロトコルとして DSDV[Perkins 94] や WRP[Murthy 95]などが，Reactive 型プロトコルとして DSR[Johnson 96],
AODV[Perkins 03] などがある．前者は，個々のノードからネットワーク内のすべてのノードに対するルーティング情報のアップデートによる一貫性の維持を行なうプロトコルである．
これらのプロトコルはトポロジーの変化するネットワークのルーティング情報の維持が難しい．また，後者は，目的ノードへのルートを必要に応じてルートを求めるプロセスを実行する．このプロセスには一つの完全なルートを探すやり方と、可能性のあるすべてのルートを試みる方法がある．よって，トポロジーの変化には耐性があるが，ネットワーク内でデータを保持するのに必要なメモリの量が多くなるなどの問題がある．また，ハイブリット型として ZRP[Haas 02] もあるが，広域環境において利用する上でこれらの共通する問題点として，利用を想定している空間の広さがある．広い空間において，すべての空間が安定した通信経路を得るのに十分な密度で満たされることは，端末自身が移動する可能性があることから非常にまれである．つまり，広域アドホックネットワークでは，Reactive型のネットワークにならざるを得ない．また，メッセージの保留，コピーや受け渡しなどによる積極的なネットワーク構築によって伝達性の向上を図る必要がある．
このような，広域アドホックネットワークの構築にあたり，同様の環境下におけるメッセージの伝達特性やネットワーク特性を調べるために，シミュレーションを構築した．

一般社会における，インターネットや携帯電話をはじめとした通信環境の浸透により，ユビキタスコンピューティングの要となる “通信” の利用が容易になりつつある．これら既存の通信は，大規模な設備を利用することで世界規模での情報交換が行なえる．そして，比較的狭い地域での通信は，その大規模な枠組み内でのの副次的な利用方法に過ぎない．人間環境をバックアップすることを目的とするユビキタスコンピューティ
ングにおける通信は，必ずしも世界規模な通信を必要とはしないで，むしろ狭い地域での通信が重要であることが多いと考える．本研究では，通信範囲の狭い無線を複数繋ぎ合わせることで構築するアドホックネットワークをより広い範囲で実現する枠組みとして “広域アドホックネットワーク” を提案する．
アドホックネットワークとは，移動無線端末から構成されるネットワークであり，その通信範囲の狭さから安定して利用するには．室内程度の広さでの利用が限界とされている．本論文
では，より広範囲で利用するために，ネットワークが分断され安定した利用が望めないアドホックネットワーク通信を，多少でも利用できるようにするためのネットワークの構造を分析す
ることを目的とする．

2.

広域アドホックネットワーク

広域アドホックネットワークの目的は，比較的狭い地域においてより自律的な分散型通信ネットワークを構築することで，災害時のような局所的な通信不能が起こりやすい既存の WANを利用したインターネット環境とは補完するだけでなく，通信の局所性などを利用した情報のコントロールなどにある．このような，アドホックシステムを構築するには，以下の点を考慮する必要がある．

1) 対象となる通信範囲は広域
2) 情報の確実な伝達ができるネットワーク構造
3) 情報伝達におけるトラフィック，コピー数の効率

3.

1) の通信範囲に関しては，都市における震災時には阪神淡路大震災のように都市規模での通信インフラが利用できない可能性がある．ただし，情報の地域性などを利用するには徒歩でシミュレーション

実験に用いるシミュレーションは，格子状空間と，そのうえ移動する点として移動通信端末をもつ移動主体 (基本的に人間を想定) から構成される．その移動主体 (エージェント) がもつ通信端末をによりメッセージが運ばれるという状況を想定する (図 1 参照)．

連絡先: 現所属) 防衛大学校，神奈川県横須賀市走水１丁目 10番 20 号，kshinoda@nda.ac.jp1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
4500

400

evalfunction:home
fullflatting
evalfunction:target

4000

evalfunction:home
fullflatting
evalfunction:target

350

3500

300

3000
250250020020001501500100100050500050100150200250300

350

400

4500500

図 4: 平均到達時間

広域アドホックネットワーク空間の基本的な特性

本シミュレーションでは，通信端末は同一の格子状の点に存在するときのみ通信可能な状態であると想定している．また，移動主体は初期位置を中心とした一定範囲を移動すると設定する．この範囲を限定により，想定する空間の広さを意味付け，一定の距離が離れた任意の端末同士が通信を行なえることを防ぐ意味がある．このような，空間における情報の伝達特性を調べるために，ランダムな選択によるメッセージのバケツリレーを行なった時の結果が，以下の図 2, 3 結果である
70600

50500

4040030300

20200

100150200

250300350

400450500850

home
random walktarget
target; all people open privete data
home; all people open private data

800
750
700
650
600
550
500
450
400

00.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.91

図 6: 個人情報の開示度による到着時間の変化

700

Avarage of Arrival Time60100

図 5: 平均受け渡し回数利用してメッセージルーティングしたときの結果を示したものである．これらの結果から，メッセージ伝達は所有者の簡単な個人情報を利用するだけでランダムウォークからかなり改善されることが分かる．ただし，この条件ではすべての個人に情報提供を求める必要があり必ずしも現実的ではない．そこで，個人情報の開示度合いによるメッセージ伝達への影響を調べた．

図 1: シミュレーション画面．左上の出発地点から右上の目的地までメッセージを運ぶシミュレーションの初期状態

3.150

Avarage of Message Pass

図 6 は，横軸を個人情報の開示度合いとする平均到着時間の変化を示したものである．このグラフから，ある程度のエージェントが個人情報を提示することで，構築されるネットワー
クの伝達特性が大きく変わることが分かる．

1000102030405060

図 2: 到着平均時間の変化

0010203040504.

60

図 3: 受け渡し回数の変化

本論文では，一般的に室内程度の広さで用いられるアドホッ
クネットワークを都市規模での利用を想定した広域アドホックネットワークを構築するための，予備的な実験として，通信ネットワークの特性を調べた．以後，シミュレーションから得られたネットワークの伝達特性をネットワーク分析の技術などを利用して，その特性を明らかにする予定である．

上の図の実験は，50x50 の格子空間上に，500 体のエージェントを配置配置を配置し，マンハッタン距離で 50 の任意の２点間をランダムに移動するエージェントによるバケツリレーにてどのようにメッセージが移動するかを調べたものである．
この図において，横軸はエージェントが移動可能な空間の広さ (マンハッタン距離) であり，それぞれ図 2 では平均到着ス
テップ，図 3 では平均受け渡し回数が示されている．この結果から，人の移動が激しい空間では，受け渡す回数が非常に多くても，到着時間へ影響するほど寄り道はしないと言える．ただし，これらのメッセージ伝達では，人数が多くなればなるほどメッセージはランダムウォークに近づく．

3.2

まとめ

参考文献
[Haas 02]

Haas, Z. J., Pearlman, M. R., and Samar, P.: TheZone Routing Protocol (ZRP)(draft-ietf-manetzone-zrp-04.txt), IETF MANET Draft (2002).

[Johnson 96] Johnson, D. B. and Maltz, D. A.: Dynamic Source
Routing in Ad Hoc Wireless Networks, in Imielinski, and Korth, eds., Mobile Computing, Vol. 353,
Kluwer Academic Publishers (1996).

広域アドホックネットワーク空間におけるネットワーク構造のコントロール

本研究では，端末を携帯する人間の動きを通信経路に加えたネットワークの構築を行なう．具体的には，端末の所有者である人間の個人情報，近隣ネットワーク関係を伝達路ルーティングに利用し，ネットワーク構造そのものの制御を各端末の自律分散的な振る舞いによって試みる．このとき, 端末所有者の個人情報とは，居住地や移動先などである．これらの情報は，基本的に端末内部にある情報を外部の端末に開示することなく利用することを想定しているが，そのような情報の有無によりネットワーク構造の変化を調べることで，ボランティアなどを利用した半強制的な情報開示により情報伝達の効率化が可能かを調べる．
図 4, 5 は，横軸をフィールド上にいるエージェント数 (密度) とする，到着時間と受け渡し回数の平均を縦軸に，すべてのエージェントが個人情報として所在地やこれからの移動先を[Murthy 95] Murthy, S. and Garcia-Luna-Aceves, J. J.: A Routing Protocol for Packet Radio Networks, in Mobile
Computing and Networking, pp. 86–95 (1995).
[Perkins 94] Perkins, C. and Bhagwat, P.: Highly Dynamic
Destination-Sequenced Distance-Vector Routing(DSDV) for Mobile Computers, in ACM SIGCOMM’94 Conference on Communications Architectures, Protocols and Applications, pp. 234–244(1994).
[Perkins 03] Perkins, C. E., Belding-Royer, E. M., andDas, S. R.:
Ad hoc On-Demand DistanceVector (AODV) Routing(draft-ietf-manet-aodv13.txt), IETF MANET Draft (2003).

2