ファイルを開く - MIUSE

修士論文
近隣通信状況に基づいたアドホックネットワーク用
経路制御プロトコルの研究
平成 2
2年度修了
三重大学大学院工学研究科
博士前期課程電気電子工学専攻
通信工学研究室
豊鷲見和都
三重大学大学院
工学研究科
，
，~
a
P
、
唱
目次
第 1章 序 論
1
1
.1 無 線 通 信 ネ ッ ト ワ ー ク の 現 状 . .• .• • • .• ..• .• • • .• .• ..• ..
1
1
.2 ア ド ホ ッ ク ネ ッ ト ワ ー ク . • • • .• • • • .• ....• ...• ........ 2
1
.3 本 論 文 の 目 的 . • • .• .• • • .• .....• .• ..• • .• ....• • • ••
5
1
.4 本 論 文 の 構 成 . • • • • • • • • .• ...• .• ....• ...• ...• • • .•
6
7
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
2
.
1 ア ド ホ ッ ク ネ ッ ト ワ ー ク の 歴 史 . • .• • ..• ..• .• • • .• • • • • • .•
7
2
.
2 ア ド ホ ッ ク ネ ッ ト ワ ー ク の 基 本 動 作 . • .• • .• .• ..• • • ..• ...
.
8
2
.
3 ル ー チ ン グ プ ロ ト コ ル . .• • • .• • • • • • • • .• .• • • ..• .• • .•• 1
0
3
2
.
4 テ ー プ ル 駆 動 型 ル ー チ ン グ プ ロ ト コ ル . • .• • ...• ...• ..• .•• 1
2
.
5 リ ア ク テ ィ ブ 型 ル ー チ ン グ プ ロ ト コ ル . ....• ..• • .• .• • • • .•
1
4
2
.
6 ハ イ ブ リ ッ ド 型 ル ー チ ン グ プ ロ ト コ ル . • • • ..• • .• • • .• • .• .. 1
5
2
.
7 ホ ッ プ 基 準 ル ー チ ン グ . .• • • • • • • • • .• • • ..• • • ....• • .•• 1
5
2
.
8 電 力 基 準 ル ー チ ン グ . • • ....• • • • .....• .• • ..• • • • • • •• 1
6
7
2
.
8
.
1 通 信 に よ る 消 費 電 力 を 抑 え る ル ー チ ン グ . .• ..• • • • .• .. 1
7
2
.
8
.
2 負 荷 集 中 に よ る 電 力 消 費 を 避 け る ル ー チ ン グ . ..• ....•. 1
8
2
.
9 ト ラ ヒ ッ ク 基 準 ル ー チ ン グ . • .• • • • .• .....• • • .• • • • • • •• 1
8
2
.
9
.
1 ネ ッ ト ワ ー ク 全 体 の ト ラ ヒ ッ ク 情 報 を 収 集 す る ル ー チ ン グ . •• 1
9
2
.
9
.
2 ネットワークの一部のトラヒック情報を収集するルーチング. 1
20
第 3章 AODV
三重大学大学院
工学研究科
u
3
.
1 は じ め に . • • • • • • • .• • • • • • .• ..• ...• .• .• • • • • • • • ••
20
3
.
2 概 要 . • .• .• ..• .• • • .....• .• • .• • • • • • • .......... 20
3
.
3 メッセージフォーマット
• .• • • • • .• ....• • ......• .• • .••
2
1
3
.
4 AODVの 処 理 ..• .• .• .....• • .• • • ....• • .....• • • •• 25
3
.
4
.
1 シ ー ケ ン ス 番 号 の 管 理 . ...• ..• • • ...• • .• .• • ..... 2
5
3.
4.
2 経 路 構 築 処 理 . ..• .• ..• ...• • • ...• • • • • • • ..• .
. 26
3.
4.
3 経 路 維 持 . • • ..• • • .• • • • • .• ....• .......• • • •• 30
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
33
4
.
1 近 隣 通 信 が 経 路 構 築 に 与 え る 影 響 . • .• • ..• .....• .• • • .... 33
4
.
2 近 隣 通 信 状 況 に 基 づ く ル ー チ ン グ 手 法 . .• • • • • • • • .• ...• .•• 34
4
.
2
.
1 帯 域 占 有 率 . • • • • .• .• • .• • .• .• • .• .• ..• ..• • .•• 35
4
.
2
.
2 提 案 方 式 に お け る 経 路 探 索 手 順 . • .• ..• .• .• • ..• .... 37
4
.
2
.
3 デ ー タ パ ケ ッ ト の 配 送 . • • .• • • • .• • .• .• ..• ..• • .•• 40
4
.
3 動 作 例 . • • • ...• • • ..• • • • • ..• .• • • • .• • • .• .• ...... 40
4. 4 計 算 機 シ ミ ュ レ ー シ ョ ン に よ る 特 性 評 価 . • .• .• • ....• • .• .•• 4
2
4
.
4
.
1 経 路 構 築 遅 延 時 間 ...........................43
4.
4.
2 総 端 末 数 に 対 す る ス ル ー プ ッ ト 特 性 . • .• .• • • • ..• • • .. 44
4.
4.
3 正 規 化 リ ン ク 切 断 数 . • • • • ..• • • ..• .• • .• • • • ..... 45
4.
4
.
4 正 規 化 RREQメ ッ セ ー ジ 数 . • .• • • • • .• .• ..• .• .• • •. 4
6
48
第 5章 結 論
5
.
1 本 研 究 の ま と め . .• • • • ..• ....• ..• • • ...• .• • .• ..... 48
参考文献
50
謝辞
54
三重大学大学院
工学研究科
図目次
2
.
1 ア ド ホ ッ ク ネ ッ ト ワ ー ク の 例 . .• • .• • • • .• • • .• • • • • .• • .••
9
2
.
2 マ ル チ ホ ッ プ 通 信 の 例 . • • • • ....• • • • • .• • • .• • .• • ...••
9
2
.
3 経 路 構 築 手 段 別 の ル ー チ ン グ プ ロ ト コ ル の 分 類 . .....• • • .• .
. 1
1
2. 4 経 路 選 択 基 準 別 の ル ー チ ン グ プ ロ ト コ ル の 分 類 . • • • ..• ..• • .
. 1
2
2
3
.
1 RREQメッセージフォーマット. • • • • • • • .• .• .• • .• ..• • .•. 2
3
.
2 RREPメッセージフォーマット
..• .• • • • • .• • • • • • • • • .• .•• 2
3
3
.
3 RERRメッセージフォーマット
• ..• ...• • .• .• .....• ...•• 24
3.
4 AODVにおける RREQメッセージのフローチャート. ...• ..• ..
. 27
3
.
5 AODVにおける RREPメ ッ セ ー ジ の フ ロ ー チ ャ ー ト . • .• ...• .•• 2
8
3
.
6 AODVの 経 路 構 築 例 . ...• .• .• • ....• .• .• .• • .• • ...•• 30
3
.
7 AODVの RERR送 信 例 . ....• • • • • ..• • • .......• • • .• .• 3
2
4
.
1 近 隣 通 信 に よ る 経 路 構 築 へ の 影 響 . .• • .• • .• • • • .• • • ...• .• 34
4
.
2 端 末 C に お け る 信 号 受 信 例 . • ..• • • • • • ..• • • • • .• ..• • • .
. 3
5
4
.
3 端 末 C に お け る 受 信 信 号 の メ ッ セ ー ジ フ ロ ー . ........• • • .•• 36
4.4提案方式における RREQメッセージのフローチャート
..• • • ...• 3
8
4
.
5 提 案 方 式 に お け る 負 荷 計 算 の フ ロ ー チ ャ ー ト . .• .• • ..• .• • • .• 3
9
4
.
6 提 案 方 式 の 経 路 構 築 例 . • .• • ..• .• ...• .• .• ..• • • .• • ..
. 4
1
4
.
7 経 路 構 築 時 の 制 御 メ ッ セ ー ジ フ ロ ー . ....• • .......• • • ..•• 42
4
.
8 経 路 構 築 遅 延 時 間 . .• • • • • .• ..• • • • ..• • .• .• • ..• .• .• 44
4
.
9 パ ケ ッ ト 到 着 率 . • ....• • • ..• .• .• .• • • .• • .• • • .• • ..• 4
5
1
1
1
三南大学大学院
工学研究科
lV
4
.
1
0正 規 化 リ ン ク 切 断 数 . .• • • • • .• • • .• ..• .• .• • • • .• • • • •• 46
4
.
1
1正 規 化 RREQメ ッ セ ー ジ 数 . • • • .• • • • • • • .• • • • • • .• • • • •• 47
二.重大学大学院
工学研究科
表目次
4
.
1 シ ミ ュ レ ー シ ョ ン パ ラ メ ー タ . ..• ......• • .• .• ..• • • .... 4
3
4
.
2 帯 域 占 有 率 に 基 づ く 転 送 遅 延 . • • • • ..• ....• .• ........
. 44
V
三貴大学大学院
工学研究科
第 1章
序論
1
.1 無線通信ネットワークの現状
近年，情報通信技術の発展に伴い無線通信機器が身近なものとなり，現在，多
数の無線通信サービスが提供されつつある
[
1
3
]
.無 線 通 信 サ ー ビ ス の 代 表 格 と
も 言 え る 携 帯 電 話 は ， 国 内 で の 加 入 者 が I億 I千 万 人 を 超 え て 広 く 利 用 さ れ て い
る[
4
]
. また，携帯型 PCや PDAな ど を 利 用 し た 無 線 LANの利用も増加している.
今後，無線通信サービスを利用した更なるサービスが期待される.
現 在 提 供 さ れ て い る 無 線 通 信 サ ー ビ ス の 代 表 例 と し て ， 携 帯 電 話 や 無 線 LANな
ど を 用 い た サ ー ビ ス が 挙 げ ら れ る . 現 在 の 国 内 の 携 帯 電 話 サ ー ビ ス は ， 第 3世 代
サ ー ビ ス が 開 始 さ れ て 以 降 ， メ ー ル の 送 受 信 や Webアクセスなど様々な用途で利
用 さ れ て き て い る . 一 方 ， 現 在 検 討 さ れ て い る 第 4世代のサービスでは， 50Mbps
'
"
"
"1Gbps程 度 の 超 高 速 大 容 量 通 信 が 実 現 し ， 今 後 更 な る サ ー ビ ス の 向 上 が 期 待
される.
無 線 LANサ ー ビ ス は ， ア ク セ ス ポ イ ン ト と 呼 ば れ る 公 衆 無 線 LANが整備され，
インフラに接続されているアクセスポイントの通信エリア内であれば無線通信
によりインターネット接続が可能となる.そして現在，オフィスのみならずコー
ヒーショップや街角でもネットワークに接続出来る環境が整いつつある.今後，公
園などの防災拠点，図書館や自動販売機など，公共インフラとしての展開も期待
されている.公衆無線 LANの 利 用 形 態 に つ い て は ， そ の 場 で ネ ッ ト ワ ー ク を 自 由
に利用出来る場合と提供業者の会員として利用する場合がある.前者はホテルや
1
三平;大学大学院
工学研究科
第 1章 序 論
2
公共施設などで用いられ，誰でも一時的なネットワークへ接続することを可能と
する.一方，後者は喫茶店などで利用される場合が多い.しかし，アクセスポイ
ントの設置場所はまだまだ限られており，どこでも利用できるまでには至ってい
ない.その原因として，アクセスポイントの設置にはケープルの敷設など多額の
費用がかかることが挙げられる.
1
.2 アドホックネットワーク
現在までに一般化している無線ネットワークは，ほとんどが無線基地局などの
インフラストラクチャを必要とするものである.これに対し，インフラを必要とし
ないアドホックネットワークという自律分散ネットワークが注目されている
[
5
7
]
.
アドホックネットワークは，各々の所持している無線通信端末のみでネットワーク
を構築する.そのため，基盤設備が存在しない場所でも，無線通信端末のみでそ
の場限りのネットワークを構築することを可能としている.また，インフラに依
存しないため，比較的低コストでネットワークを構築できるという特徴がある.
アドホックネットワークは，戦場における軍用情報の交換手段の確保を目指して
研究が始まり，近年では，民生通信への応用研究が活発に行われている.その応
用例としては，災害時の利用や防災向け，車車問・路車問通信，センサネットワー
クなどがある.アドホックネットワークの自律的にネットワークを構築する技術
を活用することにより，既存のインフラが破壊された災害現場での通信の確保が
可能となる.また，道を走るクルマに対して渋滞情報，急プレーキ情報，事故情
報 な ど を 瞬 時 に 伝 え る な ど 高 度 交 通 シ ス テ ム ITSへ の 技 術 利 用 も 可 能 と な る . 更
に，アドホックソフトを搭載したカメラを配置することで監視警備の一助として
利用することや，センサーを農場などに配置することで気候データの採取を行う
などの応用も考えられる.
0
2
.
1
1[
9
]
アドホックネットワークでは，一般的な無線通信に用いられている IEEE8
やB
l
u
e
t
o
o
t
hとして知られている IEEE8
0
2
.
1
5
.
1[
1
0
]な ど の 技 術 を 用 い て 通 信 を 行
う.しかし，無線通信端末が直接通信できる範囲には限りがあり，これだけでは
ネットワークを構築することは不可能である.そこで，アドホックネットワーク
では，直接通信を行うことができない場合でも近隣端末が中継処理を行うことで
三重大学大学院
工学研究科
第 1章 序 論
3
ネットワークの構築を行う.ルータの機能を持つ端末を中継端末と言い，中継端末
を経由して通信を行う形態をマルチホップ通信と呼ぶ.マルチホップ通信を行う
ことで，無線通信端末を中継しながら通信エリアを拡大することが可能となる.
アクセスポイントを用いる場合，端末の情報を基地局で集中管理することがで
きる.一方，アドホックネットワークでは端末を管理する基地局を持たず，各無線
通信端末が自律的に働く.そのため，データ送信者からデータ受信者までの通信
経路は固定されず，臨機応変にマルチホップ経路を確立する機能が必要となる.そ
こで，技術的課題として，そのような環境でいかに効率よく安定した経路を構築
できるかということが挙げられる.
アドホックネットワークでは安定した経路構築を行うために，様々なルーチング
1
1，
1
2
]
. アドホックネットワークでは，通信を行う端
プロトコルが提案されている [
末がどこに存在しているのかを把握することは困難である.そこで，アドホック
ネットワークのルーチングプロトコルは，送信先端末を探索するための手法とし
て，テーブル駆動型，リアクティブ型，ハイブリッド型のルーチングプロトコルが
考えられている.テープル 駆動型ルーチングプロトコルでは，データパケットの
d
送信要求が起こる前に経路を構築しておく.リアクティプ型ルーチングプロトコ
ルでは，端末がデータパケットの送信要求を出すとルーチングプロトコルが動作
し，経路構築後に通信を開始する.また，ハイブリッド型のルーチングプロトコ
ルは，リアクティプ型とテープル，駆動型のプロトコルを組み合わせたものである.
アドホックネットワークでは，これらの経路制御手法を用いることで経路構築を
可能としている.
一方，アドホックネットワークでは，複数の経路が存在する場合があり，複数の
経路から最適な経路を選択するための経路選択基準が必要となる.そこで，経路
選択基準として，ホップ数，消費電力，トラヒックを用いるルーチングプロトコル
が考えられている.ホップ数を経路選択基準に採用したルーチングプロトコルで
は，送信元端末から送信先端末までの経路ホップ数が最小となる経路の選択を行
1
3
1
5，
1
7
]
. ホップ基準ルーチングでは，最小ホップ数で経路を構築することか
う[
ら短期間で経路の構築が可能となる.また，他の経路選択基準と比べて経路選択
に考慮する情報が少ないため，経路構築におけるトラヒックを抑えられる.しか
し，経路上の端末の電池残量や経路上のトラヒック情報を考慮しないため，電源
三重大学大学院
工学研究科
第 1章 序 論
4
の切断や近隣通信の影響によってネットワークの性能が低下してしまうことが考
えられる.消費電力を経路構築基準に採用したルーチングプロトコルでは，無線
端末の多くが電池駆動であるという点を考慮し，電池残量などの情報に基づいた
2
02
5
]
. そのため，電力基準ルーチングではネットワークの長寿
経路構築を行う [
命化が可能となる.しかし，経路上のトラヒックを考慮していないことから，通
信遅延の増加やスループットの低下を招くことが考えられる.一方，トラヒックを
経路構築基準に採用するルーチングプロトコルでは，各端末のトラヒック情報を
考慮することによる安定した経路の構築を行う [
2
6
3
6
]
. アドホックネットワーク
では複数の端末が同時に通信を行うということも想定される.そのような環境で
各々の通信が他の通信を考慮しない経路を用いた場合，特定の端末や帯域への負
荷の集中が起こり，ネットワーク性能が大きく劣化してしてしまう可能性がある.
トラヒックを経路選択基準とするルーチングプロトコルでは，ネットワーク内の
負荷を分散させるため，無線資源を有効に利用することができる.そのため，他
のルーチング手法に対して安定した経路構築を行う上で有効な性能改善手法にな
りうると考えられている [
2
6
]
.
既存のトラヒック基準ルーチングでは，ネットワーク全体のトラヒック情報を収
集することにより最適な経路を構築する手法 [
2
7
3
1
]や，端末の周辺部などネット
ワークの一部のトラヒック情報を収集することにより経路を構築する手法 [
3
2
3
6
]
が提案されている.また，トラヒックの指標として，各端末を経由するトラヒック
量を採用するものや，各端末を経由する経路数を採用するものなどがある.
L
A
R
(
D
y
n
a
r
r
u
cL
o
a
d
ネットワーク全体のトラヒック情報を収集する手法として. D
AwareRo
凶 n
g
)[
2
η
.LARA(LoadAwareR
o
u
t
i
n
gi
nAdh
o
c
)[
2
8
]
.LBAR(Load-Bal組 c
e
d
Adh
o
cR
o
u
t
i
n
g
)[
2
9
]などがある.これらの手法では，経路上の端末やその近隣端末
が通信に関与したパケット数や他の通信のルートとなっている数をトラヒックの指
標に用いている.経路構築では，経路制御メッセージを用いてトラヒック情報を送
信先端末に通知する.送信先端末では，受信した複数の経路情報から最も低トラ
ヒックである経路を選択することで通信経路を確立する.無線通信では無線信号は
端末を中心として円状に広がるため，端末は近隣通信の影響を干渉として受ける.
しかし，トラヒックの指標として各端末を経由するパケット数，ルート数を用いた
場合，各端末が近隣通信の影響をどれだけ受けているのかについては十分に考慮
三重大学大学院
工学研究科
第 1章 序 論
5
ができない.一方. BNAR(BusyNodeAvoid
姐 c
eRou
七i
n
g
)[
3
0
]
.BNAR_with_NAV(Busy
NodeAvoidanceRoutingw
i
t
hNAV)[
3
1
]で は ， 経 路 上 に 流 れ る ト ラ ヒ ッ ク 量 を 経 路
選択の指標として用いている.経路構築では，送信先端末でトラヒック情報を収
集し，トラヒックの低い経路を選択する経路構築を行っている.そのため，近隣通
信のトラヒック量を考慮した経路構築が可能となっている.しかしながら，経路
のトラヒック情報を送信先端末に通知するために制御メッセージ量が増大する可
能性がある.
一方，ネットワークの一部のトラヒック情報を用いる手法では. LAOR(Load-Aware
On-dernandRo
u
t
i
n
g
)[
3
2
]や. Workloadを 用 い る 手 法 [
3
3
]などが提案されている.こ
れらの手法では，トラヒックの指標にパケットを受信する際の遅延時間や端末の
キューを占有するパケット数を用いる.経路構築では，各端末が低負荷な端末の
みを用いて制御メッセージのフラッディング行うことで経路構築を行う.各端末で
経路構築への積極性を変化させる手法はオーバーヘッドが少ないことが知られて
3
4
3
6
]
. しかし，これら
おり，現実的な運用状況では有効な一手法と考えられる [
の手法では，トラヒックの指標にパケット受信の際の遅延時間やパケット数を用い
ており，近隣通信の影響をどれだけ受けているかについては考慮できていない.
既存のトラヒック基準ルーチングの研究から，ネットワーク内の総スループット
を改善可能であることが知られている.一方，近隣通信によるトラヒック量を考
慮した経路構築を行う必要があることと，各経路上のトラヒック情報を収集する
ことによるオーバーヘッドの増大が問題点として挙げられる.しかし，これら二
つの条件を満たすルーチング手法は提案されていない.
1
.3 本論文の目的
本論文では，互いの無線信号が到達しない経路を複数構築することにより，空
間的に無線資源の有効利用を可能とし，安定した経路構築を行うことを目的とす
る.そこで，端末が受信する近隣通信量に着目することにより，自端末が利用可
能な無線資源の推定を行い，利用可能な無線資源に応じて端末の経路構築に関わ
る積極性を変化させるルーチングプロトコルの提案を行う.提案方式では，高ト
ラヒック領域に存在する端末の経路構築への積極性を引き下成低トラヒック領
三重大学大学院
工学研究科
第 1章 序 論
6
域に存在する端末の経路構築への積極性を引き上げる.結果として，提案方式で
は経路構築の際に新たな制御メッセージの収集を行うことなく，高トラヒック領
域を迂回する経路を構築可能となる.提案方式は様々なルーチングプロトコルの
拡張として実装可能であるが，本論文では，代表的なアドホックネットワーク用
ル ー チ ン グ プ ロ ト コ ル で あ る AODVを 拡 張 す る こ と に よ り 評 価 を 行 う . ま た ， 提
案方式では各端末が自律的に収集した帯域占有率に基づき自律的に経路構築に関
わる積極性を更新できることから，オーバーヘッドが増加することなくトラヒツ
ク状況を考慮可能な経路構築を実現可能である.数値例より，提案方式を用いる
ことにより，特に高トラヒック時のパケット到着率，平均遅延時間が改善可能であ
ることを示す.
1
.4 本論文の構成
本 論 文 の 構 成 と し て は ， 第 2章でアドホックネットワークの基本的な動作原理，
お よ び 既 存 の ル ー チ ン グ プ ロ ト コ ル に つ い て 述 べ ， 第 3章 で は 提 案 方 式 の 基 盤 プ
ロトコルとして用いる AODVについて述べる.第 4章 で ， 近 隣 通 信 に 基 づ く 経 路
制 御 手 法 の 提 案 と 計 算 機 シ ミ ュ レ ー シ ョ ン に よ る 検 討 結 果 を 述 べ る . 第 5章 で 結
論を述べる.
三重大学大学院
工学研究科
第 2章
アドホックネットワーク
本章では，アドホックネットワーク及び，ルーチングプロトコルについて述べる.
2
.
1 アドホックネットワークの歴史
アドホックネットワークの開発の歴史は比較的古く，インターネットとほぼ同時
期 (
1
9
7
0年 代 [
3
7
3
9
)
)に 軍 事 研 究 を 基 に し て 開 始 さ れ た . 1
9
6
0年 代 の 終 わ り か ら
1
9
7
0年代に，ハワイ大学の ALOHAプロジェクトにおいて，オアフ島にある大学本
部 の 中 央 コ ン ビ ュ ー タ と ハ ワ イ 諸 島 に 分 散 す る 大 学 施 設 の 端 末 を 結 ぶ UHF帯域を
用いたパケット交換網の研究が進められ. 1
9
7
0年代に運用を開始した. ALOHAプ
ロジェクトは，無線のブロードキャストという特性を利用し，データパケットを送
受信するシングルホップシステムの可能性を示した.そして，多くの端末が共通
9
7
2年に，
の無線通信路にアクセスするランダムアクセスの原理が確立された. 1
DARPA(DefenseAdvancedR
e
s
e
a
r
c
hP
r
o
j
e
c
t
sAgency)はパケット無線網 PRNET(Packet
Rad
i
oN
e
t
w
o
r
k
)の研究を開始した.当初、 PRNETは中央制御局を前提とするプロト
コルを用いていたが，その後，自律分散型のアーキテクチャへと変換した. ALOHA
とは違い. PRNETは 無 線 の ブ ロ ー ド キ ャ ス ト を 用 い ， 無 線 の 接 続 性 が 不 十 分 な 環
境の中で十分な接続性を提供するためのマルチホップパケット交換経路制御技術
9
8
0年 の 初 期 に PRNET
を用いており，アドホックネットワークの起源となった. 1
の実現性は実証されたが，当時のパケット無線装置は大きな電力を必要とした.
9
8
0年 代 後 半 に は ， パ ケ ッ ト 無 線 網 の 商 用 利 用 や ア マ チ ュ ア 無 線 に よ る パ
また. 1
7
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
8
ケット交換網の実現も検討されたが，当時の無線装置は大きく実用化には至らな
9
9
0年 代 後 半 の 無 線 端 末 の 小 型 化 ， 高 機 能 化 や 様 々 な 無 線 通 信 技
かった.しかし， 1
術の開発から，軍事利用に留まらず日常生活や社会サービスとしての研究に注目
が集まるようになった
2
0
0
0年代に入り，携帯電話， PDA， ノ ー ト 型 パ ソ コ ン の 爆
発的に普及による既存のインターネット通信にはない無線通信へのニーズの高ま
りから，アドホックネットワークを利用したネットワークサービスやインターネッ
ト接続サービスの提供にも注目が集まっている.
2
.
2 アドホックネットワークの基本動作
ア ド ホ ッ ク ネ ッ ト ワ ー ク と は ， 有 線 通 信 の イ ン フ ラ ス ト ラ ク チ ャ や 無 線 LANの
ようなアクセスポイントを必要としない，無線で接続できる端末のみによって構
成されたネットワークのことである.アドホックネットワークでは直接端末聞の無
線リンク接続が可能な場合，端末聞で直接通信を行う.図 2
.
1で は ， 直 接 通 信 の 可
能な端末聞で無線リンクの接続を行う場合の一例を示す.図 2
.
1に示すように，端
末 A，D が 端 末 B，C，E と 通 信 を 行 う . し か し ， 端 末 が 広 範 囲 に 分 散 し て い る 場 合
や，端末聞に遮蔽物が存在することも考えられる.また，アドホックネットワーク
E
E
E
8
0
2
.
1
1を 用 い た 場 合 ， 通 信 可 能 距 離 は
における無線デ、パイスの使用例として I
約 100m程 度 と な る . そ の よ う な 場 合 ， 情 報 を 受 け 取 る 任 意 の 送 信 先 端 末 は ， 直 接
通信することが可能であるとは限らない.そこで，アドホックネットワークでは
近隣の端末を経由して情報を中継するマルチホップ通信を行う.マルチホップ通
信を行うことで遠方の端末との通信を行うことが可能となる.図 2
.
2に，マルチ
ホ ッ プ 通 信 を 利 用 し た 通 信 の 例 と し て ， 送 信 元 端 末 Sが 送 信 先 端 末 D と通信を行
う 状 況 を 示 す. 8は D と 通 信 を 行 う た め に ， 近 隣 端 末 の A，B，C が 中 継 端 末 と な
り情報を転送することで D への情報伝達を可能とする.このように，マルチホッ
プ通信を行うことで， 8 は D と 通 信 を 行 う こ と が 可 能 と な る .
しかし，マルチホップ通信を行うだけでは，情報を伝達したい端末がどこに存
在するのかを把握することは困難である.また，送信元端末と送信先端末との聞
で最適な経路が確立されるとは限らない.
そこで，送信元端末が送信先端末と通信を行うための経路制御手法が必要とな
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
9
w
i
r
e
l
e
s
sl
i
n
k
図2
.
1アドホックネットワークの例
ーーーーーーーーーーーーー・~
語開圃~-ー周回
D
e
s
t
i
n
a
t
i
o
nn
o
d
e
R
e
l
a
yn
o
d
e
図2
.
2マルチホップ通信の例
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
0
る.経路制御は，通信相手への経路構築，ネットワーク環境の変化に対応するた
めの経路維持，の二つの機能を用いる.経路構築を行う際に，送信先端末のアド
レス情報のみを元に経路発見を行う経路制御プロトコルをリアクティブ型と呼ぶ.
一方，予め定期的な制御メッセージをアドホックネットワーク内で交換すること
で経路制御テープルを構築し，テープル情報を元に経路制御を行うものをテープ
ル駆動型と呼ぶ.リアクティブ型の多くのプロトコルでは，経路探索のためにフ
ラッディングという手法が用いられる.また，テープル駆動型でもアドホックネッ
トワークの開始時にはテープル情報を持たないため，経路発見のためにフラッデイ
ングを用いるプロトコルがある.
フラッデイングとは，送信元端末が隣接端末に向けてパケットをブロードキャス
トで送信することにより，多方面に連鎖的に転送してもらう方式のことである.
フラッデイングにより，パケットは一定の生存期間中に無差別に転送される.フラッ
デイングは，有効範囲を制御することが可能である.これは，この方式は転送を
繰り返すことになるため，ネットワークに与える影響が非常に大きいからである.
そのため，フラッデイングは必要最小限に行うことが望まれている.フラッデイン
グの用途は，送信先端末の探索が主なものであるが，テープル，駆動型における周
辺端末や，全端末への制御情報の配信などにも用いられる.
一方，アドホックネットワークでは，経路を発見し，構築した後も各端末の電源
切断や通信状況の変化などによりネットワーク環境が変化することが考えられる.
そのような変化に対応するのが経路維持の機能である.経路維持には，通信経路
の接続性の断続を元に再度経路発見，または部分的な経路修正を行うプロトコル
e
l
l
oメッセージなどの制御情報を交換する
や，定期的に通信経路上の端末同士で H
プロトコルがある.経路維持にも経路制御プロトコルごとの様々な方式が提案さ
れている.
2
.
3 ルーチングプロトコル
本節では，既存のルーチングプロトコルを基に，アドホックネットワークにおい
てどのような経路構築が行われているのかを述べる.
アドホックネットワークを用いた通信では，送信元端末は送信先端末への通信
三宅大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
1
経路を迅速に構築する必要がある.アドホックネットワークにおける通信経路は，
有線通信のように実際に端末同士が物理的に繋がるものではない.そこで，これ
までに数多くのアドホックネットワーク用ルーチングプロトコルが提案されてい
る.アドホックネットワークでは，送信先端末を探索するための手段が重要とな
.
3に示す.経路構築
る.これまでに提案されてきたルーチングプロトコルを図 2
P
r
o
a
c
t
i
v
e
)，リアクテイブ型 (
R
e
a
c
t
i
v
e
)，ハイブリツ
手段について，テーブル駆動型 (
H
y
b
r
i
d
)に分類することができる.一方，アドホックネットワークにおける経
ド型 (
路構築では，複数の経路が存在する可能性がある.そこで，最適経路で通信を行
うための経路選択基準も重要な課題となる.経路選択基準について，これまでに
提 案 さ れ て き た ル ー チ ン グ プ ロ ト コ ル を 図 2.4に示す.図 2.4に示すように，ホッ
プ数，消費電力，トラヒックに分類することができる.同じタイプのネットワーク
用に設計されているにもかかわらず，これらのルーチングプロトコルにはかなり
の違いがある.以下に，それぞれのプロトコルについて説明し，特徴を述べる.
R
o
u
t
i
n
gP
r
o
t
o
c
o
l
AV
RRD
SOO
DTA
VR3
D S汗
郎乱開
図2
.
3経 路 構 築 手 段 別 の ル ー チ ン グ プ ロ ト コ ル の 分 類
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
2
R
o
u
t
i
n
gP
r
o
t
o
c
o
l
T
r
a
f
f
i
cb
a
s
e
DSDV
DSR
AODV
ZRP
PCM
PAR
MRPC
DLAR
LARA
LBAR
LAOR
LBM
図2
.4経路選択基準別のルーチングプロトコルの分類
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
3
2.
4 テーブル駆動型ルーチングプロトコル
テープル駆動型ルーチングプロトコルは，ネットワーク上の各々の端末から他
の全ての端末への，矛盾のない最新の経路制御情報の維持を行うよう動作する.
これらのプロトコルでは，各端末は経路制御情報を格納するためのテープルを l
つ以上持つ.そして，ネットワーク状況の変化に応じてネットワーク全体に経路の
更新情報を転送する.常に最新の経路表を保持することにより，通信要求に対し
てすぐにデータパケットを送信することを可能としている.テープル駆動型ルー
チングプロトコルでは，ルーチングに要した必要テープル数と，ネットワーク構
造に変化があった場合の通知方法に各プロトコルの違いがある.
D
S
D
V
(
D
e
s
t
i
n
a
t
i
o
nS
e
q
u
e
n
c
e
dDis
t
a
n
c
eV
e
c
t
o
r
)プ ロ ト コ ル は ， 古 典 的 な B
e
l
l
m
組 F
o
r
dル ー チ ン グ ア ル ゴ リ ズ ム を 基 に し た ， テ ー プ ル 駆 動 型 ル ー チ ン グ プ ロ ト コ
1
3
]
.DSDVで は ， 各 端 末 は 経 路 制 御 情 報 が ル ー プ し な い よ う ， 同 一 ネ ッ
ルである [
トワーク内の到達可能な全ての送信先端末とそのホップ数を記録した，経路制御
情報を管理する.また，送信元端末が最新の経路情報を判断するために，シーケ
， 2種 類 の 経 路 情 報 更 新 用 パ ケ ッ ト を 使 用 す る こ
ン ス 番 号 を 使 用 す る . DSDVは
とで，経路の維持を行う. 1つは，フルダンプパケットである.このパケットは，
利用可能な全ての経路情報を格納しており，大きく経路情報が更新される場合に
用 い ら れ る . 2つ 目 は ， フ ル ダ ン プ よ り 小 さ な 差 分 パ ケ ッ ト で あ る . こ の パ ケ ッ
トは，最後に送信したフルダンプ以降の経路更新情報のみを送信する場合に用い
る.新たな経路制御情報を送信する場合，送信先端末の情報を受信した時のシー
ケンス番号を記録する.最も新しいシーケンス番号を持つ経路が常に使用される
ため，同じ経路更新情報がシーケンス番号を持つ場合，ホップ数の少ない経路を
選択する.
O
L
S
R
(
O
p
t
i
m
i
z
e
dL
i
n
kS
t
a
t
eRo
u
t
i
n
g
)プロトコルの特徴は，フラツデイングを効率
1
4
]
. フラッデイングを行った際，メッセージを受
よく行うことが出来る点である [
信した全ての端末がそのメッセージの再送信を行うため，ネットワーク中に冗長
叫t
iP
o
i
n
tR
e
l
a
y
)集
なメッセージが多く流れてしまう.そこで， OLSRでは MPR(M
合の概念を導入している.ある端末がプロードキャストしたパケットをその端末
の 選 択 し た MPRと 呼 ば れ る 端 末 の み が 再 ブ ロ ー ド キ ャ ス ト す る こ と で ， 冗 長 な
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
4
メッセージを削減し，フラッデイングの効率化を図ることが可能になる.経路維持
を 行 う 場 合 は ， 経 路 情 報 の 生 成 は MPRのみが行うことでフラッデイグされる経路
情報を削減することが可能である.また， MPRと し て 選 択 し た 端 末 と の 間 で 経 路
情報を交換することで，経路制御パケットのオーバヘッドを削減することが可能
である.
2
.
5 リアクティブ型ルーチングプロトコル
リアクティプ型のルーチングプロトコルは，通信要求が発生した時にのみ経路
を作成する.ある端末において送信先端末への経路が必要となった場合，ネット
ワーク内に経路要求メッセージをブロードキャストすることで経路構築を開始す
る.経路構築処理は，送信先端末への経路を構築すると終了する.経路構築後は，
送信元端末と送信先端末聞の経路が無効となるか経路が不必要となるまで，経路
が維持される.また，経路要求後に経路構築を行うため，通信開始まで多少の遅
延を伴う.一方，アドホックネットワークで想定する無線端末は，蓄電池などを用
いた稼働が想定される.リアクティプ型ルーチングプロトコルは通信要求がない
場合，プロトコルは完全に動作しないため，無駄な消費電力がかからない.
D
S
R
(
D
y
n
a
m
i
cS
o
u
r
c
eR
o
u
t
i
n
g
)プ ロ ト コ ル は ， 送 信 元 端 末 が 予 め 全 体 の 経 路 を 指
1
5，
1
6
]
. また，全てのデータ
定するソースルーチングという形式を採用している [
パケットが送信元端末から送信先端末までの経路情報を保持し，経路制御を行っ
ている. DSRでは，ソースルート情報を各中継端末がキャッシュすることで，経路
発 見 時 間 の 短 縮 や 経 路 切 断 時 の 経 路 回 復 な ど に 用 い ， 効 率 化 を 図 っ て い る . DSR
は ， 経 路 探 索 と 経 路 保 持 の 2つ の メ カ ニ ズ ム に よ り 成 り 立 つ . 経 路 探 索 で は ， 送
信先端末への有効な経路が存在した場合，パケットの送信にその経路を使用する.
一方，有効な経路が存在しない場合，経路探索を開始して経路要求パケットをプ
ロードキャストする.経路保持では，パケットの送信に問題が発生した場合に経
路エラーパケットが生成され，代替経路や経路探索を行う.
AODV(Adh
o
cO
n
d
e
m
a
n
dD
i
s
t組 c
eV
e
c
t
o
r
)プロトコルは， DSDVアルゴリズムを
基盤として構築されている
に対し，
[
1
7
]
. DSDVで は 完 全 な 経 路 リ ス ト を 維 持 管 理 す る の
AODVは リ ア ク テ ィ プ に 経 路 を 作 成 す る . こ れ に よ り ， 必 要 な ブ ロ ー ド
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
キャスト数を最小化している.また，
1
5
AODVは 送 信 先 端 末 ま で の 各 中 継 端 末 が 送
信先端末のアドレスに基づき，次の中継端末を決定する経路制御方式である.ま
た，シーケンス番号を用いることで，経路のループ防止と最新の経路情報の保持
を 保 証 し て い る . AODVは 経 路 発 見 と 経 路 保 全 を 行 う こ と で ， ア ド ホ ッ ク ネ ッ ト
ワ ー ク を 実 現 す る . AODVは ， ソ ー ス ル ー チ ン グ な ど の 機 能 が な く ， 実 装 が 比 較
的容易であるため，経路制御プロトコルの実装として
る
AODVが最も多くなってい
[
1
8
]
.AODVに つ い て は ， 本 論 文 の 基 と な る プ ロ ト コ ル と し て ， 次 章 で 詳 し く
説明を行う.
2
.
6 ハイブリッド型ルーチングプロトコル
ハイプリッド型プロトコルは，テープル駆動型とリアクティプ型のプロトコルを
r
o
a
c
t
i
v
e型
組み合わせたプロトコルである.送信元端末の近隣の端末に対しては P
e
a
c
t
i
v
e
で経路表を作成する.一方，遠方に存在する端末との通信を行う場合は， R
型のルーチングプロトコルを用いて経路を作成する.
ZRP(ZoneRoutingP
r
o
t
o
c
o
l
)プ ロ ト コ ル は ， テ ー プ ル 駆 動 型 の ル ー チ ン グ プ ロ ト
コルとリアクティブ型のルーチングを複合的に用いたハイプリッド型の経路制御
1
9
]
. ZRPで は ， 経 路 制 御 ゾ ー ン を 中 心 端 末 か ら 1
，2ホップ程
プロトコルである [
度の範囲内の端末で構成する.経路制御ゾーンは，データの送信要求の発生時に
利用し，ゾーン内ではテープル駆動型のルーチングを行う.よって，各端末はゾー
ン内の全ての経路情報を保持している.一方，送信先端末が送信元端末のゾーン
外に存在する場合，リアクティプ型の経路制御手法を用いた経路構築プロセスを
実行する.
2
.
7 ホップ基準ルーチング
ホップ基準ルーチングでは，送信元端末から送信先端末までの中継端末数が最
小となるような経路を構築する.よって，短期間で経路の構築ができることが特
徴として挙げられる.また，他の経路選択基準と比べて経路制御メッセージの情
報を少なく抑えられることから，経路構築にかかるトラヒックを抑えられ，経路
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
6
制御も比較的容易であることが特徴として挙げられる.前節までに述べた代表的
な経路制御プロトコルでは，ホップ基準を用いた経路選択を行っている.一方，ア
ドホックネットワークで想定される端末は，蓄電池などを用いた稼働が想定され
る.また，複数の端末が同時に通信を行うことも考えられる.そのような環境で
ホップ基準ルーチングを適用した場合，トラヒックの集中による特定の端末への
大きな電力負荷や他の通信との干渉を引き起こすことが予想される.これらの問
題はネットワークの性能を低下させる要因となるため，ホップ数を経路選択基準
とした手法は，アドホックネットワークでの経路制御手法として必ずしも最適で
はないと言える.
2
.
8 電力基準ルーチング
電力基準ルーチングでは，経路選択基準に端末の電力情報を用いる.アドホック
ネットワークを構成する端末は，移動性や小型化といった要因のため蓄電池などを
用いた稼働が想定される.そのため，端末の電力を考慮した経路構築はネットワー
クの長寿命化を可能とする手法となりアドホックネットワークにおける重要な経
路制御の一手法となる.電力基準ルーチングでは，経路構築における電力を削減
202
2
]
.
することで，端末の電力消費を抑えるルーチング手法が提案されている [
また，負荷の集中による特定の端末での電力低下に着目し，電力消費の公平性を
2
3
2
5
]
. 端末の電力消
考慮した経路構築を行うルーチング手法も提案されている [
費を抑える手法では，通信時の電力制御を行うことにより経路構築を行う際に必
要となる電力や，データを送信する際の電力の削減を行い，ネットワークの長寿
命化を行っている.しかし，元々電池残量の少ない端末を用いた経路を構築した場
合は，経路が切断する可能性がある.負荷集中による電力低下に着目した手法で
は，各端末や経路全体での電力情報から最も電池残量の少ない経路を選択するこ
とで，特定の端末の電池残量の著しい低下を防いでいる.この手法では，長時間
同じネットワークで通信が行われた場合に電池切れとなる端末が減るため，ネッ
トワークの性能が落ちにくくなる.
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
17
2
.
8
.
1 通信による消費電力を抑えるルーチング
PCM(Powerc
o
n
t
r
o
lMAC)プ ロ ト コ ル で は ， 周 期 的 に DATAの 電 力 レ ベ ル を 最
xtendedIFS(EIFS)期 間 を 終 了 し た 端 末 が
大電力レベルまで上げる制御を行う. E
DATA/ACKの 通 信 中 に 干 渉 し な い た め ， 電 力 効 率 が 向 上 す る [
2
0
]
.
PAR(PowerAwareR
o
u
t
i
n
g
)プ ロ ト コ ル は ， 端 末 の 稼 働 時 間 を 長 引 か せ ら れ る よ
2
1
]
.通信経路上の各端
う，電池残量を効率的に使用することを目的としている [
末で消費される電力に関する情報を予め交換しておき，この情報に基づいて各端
末の消費電力の合計が最小となる経路を選択する.
MTPR(MinimumT
o
t
a
l'
f
r
a
n
s
m
i
s
s
i
o
nPowerR
o
u
t
i
n
g
)プロトコルは，
1パケットあ
2
2
]
.
たりの送信先端末までの送信電力の総量を最小にすることを目的としている [
MTPRで は ， 隣 接 端 末 間 で 通 信 に か か る 電 力 を 数 値 化 し ， 複 数 あ る 経 路 ご と の 通
信電力の総量を求める.そして，通信電力の最も小さい経路を選択する手法をと
る.これにより，通信時の消費電力を最小限に抑えることができる.
2
.
8
.
2 負荷集中による電力消費を避けるルーチング
MRPC(MaximumR
e
s
i
d
u
a
lP
a
c
k
e
tC
a
p
a
c
i
t
y
)プロトコルは，複数の経路が重なるこ
となどにより電力残量が少なくなった端末に対し，迂回経路を選択することによっ
て，電力の公平性を実現する [
2
4
]
. MRPCで は ， 各 端 末 に お い て リ ン ク の エ ラ ー
率，伝送電力，電力残量から送信可能なパケット数を算出し，経路選択の指標と
して用いている.
LBM(LoadB
a
l
a
n
c
e
dRoutingMech
白血m)プロトコルでは，電池残量の少なくなっ
た端末を含まない経路を選択することによる，経路の長寿命化を目的としてい
2
5
]
. LBMで は ， 経 路 上 の 端 末 で の 最 小 電 力 量 ， 端 末 に 並 ぶ パ ケ ッ ト の 平 均 値
る[
とホップ数を指標とした経路選択を行う.
AODV
+G(AODV
+G
o
s
s
i
p
)プロトコルは，中継を依頼された端末がある確率でこ
2
2
]
. 経路探索の際に，制御メッ
れを拒否し，消費電力を抑える手法となっている [
セ ー ジ を 受 信 し た 受 信 端 末 は 確 率 pでパケットを破棄する.そのため， AODV+G
ではシステム全体の電力消費を低減できるが接続成功確率が下がる，という特徴
を持つ.
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
8
2
.
9 トラヒック基準ルーチング
トラヒック基準ルーチングでは，各端末のトラヒック情報を用いた経路構築を
行うことにより，特定の経路にトラヒックが集中することを防ぐ負荷分散を目的
としている.トラヒックを経路選択基準に採用するルーチング手法として，ネッ
トワーク全体のトラヒックを収集することで最適な経路構築を行う手法が提案さ
2
7
3
1
]
. また，端末の周辺部などネットワークの一部のトラヒック情報を
れている [
3
2，
3
3
]
. ネットワーク全体のトラヒックを収集す
収集する手法も提案されている [
る手法では，送信先端末で複数の経路のトラヒック情報を収集し，最適な経路の
選択を行う.そのため，経路全体のトラヒックを把握することが可能となる.しか
し，複数の経路情報を制御メッセージにより伝達する必要があり，トラヒック情報
を収集するためのトラヒック量が増大する可能性がある.ネットワークの一部の
トラヒック情報を収集する手法では，一部のトラヒック情報を用いることで経路
構築を行うが，経路全体のトラヒックを判断することは難しくなる.しかし，各
端末がトラヒックを判断するため，経路情報を伝達するためのトラヒックが不必
要となる.
2
.
9
.
1 ネットワーク全体のトラヒック情報を収集するルーチング
DLAR(DynamicLoad-AwareR
o
u
t
i
n
g
)プ ロ ト コ ル で は ， 経 路 構 築 の 際 に 各 端 末 が
2
7
]
. この情報を制御メッセージを用いて
通信に関与したパケット数を収集する [
送信先端末に通知することにより，トラヒックを考慮する経路選択を実現してい
る.送信先端末では，複数の経路候補から最も負荷の少ない経路に対して経路応
答メッセージを送信することで経路を構築する.
LARA(LoadAwareRo
u
t
i
n
gi
nAdh
o
c
)プ ロ ト コ ル で は ， 各 経 路 ご と の 中 継 端 末 の
2
8
]
.負 荷 の 指 標 に
送信待ちパケットが保持しているキューの長さの総和を求める [
この値を用い，負荷の最も少ない経路を選択することで負荷分散を行う.負荷の
算出には，各端末と近隣端末のキューの長さを一定間隔ごとにサンプリングした
値を用いる.
LBAR(Load-BalancedAdhocR
o
u
t
i
n
g
)プ ロ ト コ ル で は ， 自 端 末 と 隣 接 端 末 が 属 し
2
9
]
.経 路 探 索 時 に ， 各
ている経路の数を負荷の指標とした経路構築を行っている [
三重大学大学院
工学研究科
第 2章 ア ド ホ ッ ク ネ ッ ト ワ ー ク
1
9
端末が制御メッセージを中継するごとに負荷の指標を加えていくことで，送信先
端末に到達したパケットから各経路の負荷を把握している.送信先端末では，複
数の経路から最も負荷の低い経路を選択する.
BNAR(BusyNodeAvoidanceR
o
u
t
i
n
g
) プロトコル， BNAR_with
_N
AV(BusyNode
AvoidanceRoutingw
i
t
hNAV)プ ロ ト コ ル で は ， 経 路 上 に 流 れ る ト ラ ヒ ッ ク 量 を 負
荷の指標として用い，送信先端末で負荷の低い経路を選択する経路構築を行って
3
0，
3
1
]
. そのため， BNAR
，BNAR_with
_N
AVでは，近隣通信のトラヒツク量を
いる [
考慮した経路構築が可能となっている.
2
.
9
.
2 ネットワークの一部のトラヒック情報を収集するルーチング
LAOR(Load-AwareOn-demandR
o
u
t
i
n
g
)プ ロ ト コ ル で は ， パ ケ ッ ト を 受 信 す る 際
3
2
]
. 経路構築では，高負荷な端末ではパケッ
の遅延時間を負荷の指標としている [
トの転送を行わず，低負荷な端末のみを用いて制御メッセージのフラッデイングを
， AODVをベースとしており，経路は最初に送信先端末に到達した
行う. LAORは
経路で構築される.
Workloadを用いる手法では，キューを占有するパケット数により闘値を設け，闘
3
3
]
. 高負荷端末ではパケットの転送を行
値を超える端末を高負荷端末としている [
わず，低負荷な端末のみを用いた経路探索を行う. LAOR
，Workloadではトラヒツ
ク情報を制御メッセージで伝達しないことによって，オーバーヘッドの抑制を可能
， DSRなどのプロ
としている.また，負荷の判断を各端末が行うことで AODVや
トコルへの適応が行いやすくなっている.
三重大学大学院
工学研究科
第 3章
AODV
本 章 で は ， オ ン デ マ ン ド 型 の 代 表 的 な プ ロ ト コ ル の 一 つ で あ る ， AODV(Adhoc
On-demandDi
s
t
a
n
c
eV
e
c
t
o
r
)について説明する.
3
.
1 はじめに
AODVは ， 経 路 構 築 要 求 に 対 し て 動 的 に 経 路 構 築 を 開 始 し ， ア ド ホ ッ ク ネ ッ ト
ワークの経路構築や経路維持に参加する端末間でマルチホップルーチングを可能
とする. AODVは ， 経 路 発 見 と 経 路 保 全 の 二 つ の 機 能 を 持 つ . AODVでは，通信
が行われていない送信先端末への経路情報を保持せず，新しい通信要求に対して
迅速に送信先端末への経路構築を行う.また，リンクの切断や変更に対して適切
に対応する機能を持つ.リンクが切断された場合は，切断されたリンクを使用し
て い る 経 路 を 無 効 化 す る た め ， 影 響 す る 端 末 へ の 通 知 を 行 う . AODVの特徴とし
て ， シ ー ケ ン ス 番 号 を 利 用 し て い る 点 が 挙 げ ら れ る . AODVで は ， シ ー ケ ン ス 番
号を利用することでループの回避を行っている.
3
.
2 概要
AODVで は ， 経 路 要 求 (RREQ:Ro
u
t
eR
β
q
u
e
s
t
)メッセージ，経路応答 (RREP:
RouteR
e
p
l
y
)メッセージ，経路無効 (RERR:RouteE
r
r
o
r
)メッセージが使用される.
AODVで は ， 送 信 先 端 末 へ の 経 路 が 必 要 と な っ た 時 ， 送 信 元 端 末 は RREQメツ
20
三重大学大学院
工学研究科
第 3章
AODV
2
1
セージをネットワーク全体にプロードキャストし，送信先端末への経路を探索す
る . 送 信 先 端 末 か 送 信 先 端 末 へ の 経 路 情 報 を 持 つ 端 末 が RREQメッセージを受信
した場合，経路が決定する. RREQメ ッ セ ー ジ を 受 信 し た 端 末 が 送 信 先 端 末 で な
かった場合，メッセージを受信した端末は中継端末として，送信先端末のアドレス
に基づき次ホップを決定する.また，各端末はシーケンス番号を管理し，経路に
変 化 が あ る と シ ー ケ ン ス 番 号 を I増加させる. AODVで は ， 送 信 先 端 末 の シ ー ケ
ンス番号が大きい経路を選択することにより，経路上のループの発生を防止して
いる.複数の経路が存在する場合は，送信先端末のシーケンス番号が大きい方の
経 路 を 選 ぶ こ と に よ り 最 新 の 経 路 の 選 択 が 可 能 と な る . AODVでは， RREPメッ
セージを RREQメ ッ セ ー ジ が 経 由 し て き た 経 路 を 用 い る こ と で 経 路 が 利 用 可 能 と
なる. RREQメッセージを受信した端末は，送信元端末への逆経路を保持する.そ
のため，中継端末などは保持している経路情報を用いてユニキャストで送信元端
末の返信を行える.
有効な経路上にある端末は，次ホップへのリンク状態を監視する.リンク切断
は
， RERRメッセージによって他の端末へ通知される.
AODVで は ， 各 端 末 が 経 路 表 を 保 持 す る . 経 路 表 に は ， 以 下 の 項 目 が 含 ま れ る .
・送信先アドレス
・送信先シーケンス番号
・次ホップ IPアドレス
・ホップ数
・
TTL(T eT
oL
i
v
e
)
凶
各経路表は
TTLを持ち，経路が利用される度に更新され， TTLを 超 え る と そ の
経路は無効となる.また，各端末は送信先端末ごとに，送信先端末への次ホップ
とする隣接上流端末(プリコーサ)のリストを持つ.プリコーサリストは，経路修
復の際に利用される.
3
.
3 メッセージフォーマット
本節では，図 3
.
1図 3
.
2，図 3
.
3に RREQ，RREP，RERRメッセージのパケットフォー
マットの図を示し，説明をする.
三貴大学大学院
工学研究科
第 3章 AODV
t
y
p
e
2
2
I
JI
RI
GI
DI
UI
r
e
s
e
r
v
e
d
lhopcount
RREQID
d
e
s
t
i
n
a
t
i
o
nI
Paddress
d
e
s
t
i
n
a
t
i
o
nsequencenumber
sourceI
Paddress
sourcesequencenumber
図3
.
1RREQメッセージフォーマット
• t
y
p
e
メッセージを識別するためのフィールド. 1が 入 る こ と で RREQメッセージで
あると識別される.
• J(
J
o
i
nF
l
a
g
)
マルチキャスト通信用に予約されたフィールド.本論文では使用しない.
• R(
R
β阿 rF
l
昭)
マルチキャスト通信用に予約されたフィールド.本論文では使用しない.
• G(
G
r
a
t
u
i
t
o
u
sRREPF
l
a
g
)
不 必 要 な RREPメ ッ セ ー ジ を 送 信 す る か ど う か 判 断 す る た め に 使 用 す る .
• D(
D
e
s
t
i
n
a
t
i
o
nOnlyF
l
a
g
)
送 信 先 端 末 の み が RREPメッセージを生成できるようにするために使用する.
• U (U
山 ownS
equenceNumber)
送信先シーケンス番号が不明な場合に使用する.
• r
e
s
e
r
v
e
d
送信予約をする際に， 0を 格 納 す る . 受 信 時 は 無 視 さ れ る .
• hopc
o
u
n
t
送信元端末から送信先端末までのホップ数を格納する.
・
RREQID
最後に送信した
RREQメッセージの RREQIDに Iを加えた値を格納する.
三重大学大学院
工学研究科
第 3章 AODV
2
3
• d
e
s
t
i
n
a
t
i
o
nIPa
d
d
r
e
s
s
送信先端末の I
Pアドレスを格納する.
• d
e
s
t
i
n
a
t
i
o
ns
e
q
u
e
n
c
enumber
送信元端末が最後に受信した送信先端末へのシーケンス番号を格納する.
• s
o
u
r
c
eI
Pa
d
d
r
e
s
s
送信元端末の I
Pアドレスを格納する.
• s
o
u
r
c
es
e
q
u
e
n
c
enumber
送信元端末への経路において利用される現在のシーケンス番号を格納する.
t
y
p
e
I
RI
AI
r
e
s
e
r
v
e
dIp
r
e
f
i
x I
hopcount
d
e
s
t
i
n
a
t
i
o
nI
Paddress
d
e
s
t
i
n
a
t
i
o
nsequencenumber
sourceI
Paddress
TTL(
t
i
m
et
ol
i
v
e
)
図3
.
2RREPメッセージフォーマット
• t
y
p
e
メッセージを識別するためのフィールド. 2が 入 る こ と で RREPメッセージで
あると識別される.
• R(
R
e
p
a
i
rF
l
a
g
)
マルチキャスト通信用に予約されたフィールド.
• A(
A
c
k
n
o
w
l
e
d
g
e
m
e
n
t恥 q
u
i
r
e
d
)
ACKを 必 要 と す る 場 合 に 使 用 す る .
• r
e
s
e
r
v
e
d
送信予約をする際に， 0を 格 納 す る . 受 信 時 は 無 視 さ れ る .
• p
r
e
f
i
x
アドホックネットワークをいくつかのサブネットワークを分割して行う際に
使用する.本論文では，使用しない.
三重大学大学院
工学研究科
第 3章
AODV
2
4
• hopc
o
u
n
t
送信元端末から送信先端末までのホップ数を格納する.
• d
e
s
t
i
n
a
t
i
o
nI
Pa
d
d
r
e
s
s
送信先端末の I
Pア ド レ ス を 格 納 す る .
• d
e
s
t
i
n
a
t
i
o
ns
e
q
u
e
n
c
enumber
送信元端末が最後に受信した送信先端末へのシーケンス番号を格納する.
• s
o
u
r
c
eI
Pa
d
d
r
e
s
s
送信元端末の I
Pア ド レ ス を 格 納 す る .
• TTL(
T
i
m
et
oL
i
v
e
)
RREPメ ッ セ ー ジ を 受 信 し た 端 末 が ， そ の 経 路 が 有 効 で あ る と 判 断 す る 時 間
を格納する.
t
y
p
e
I
NI
r
e
s
e
r
v
e
d
d
e
s
tcount
unreachabled
e
s
t
i
n
a
t
i
o
nI
Paddress
unreachabled
e
s
t
i
n
a
t
i
o
nsequencenumber
unreachabled
e
s
t
i
n
a
t
i
o
nI
Paddress
unreachabled
e
s
t
i
n
a
t
i
o
nsequencenumber
.
.
.
図3
.
3RERRメッセージフォーマット
• t
y
p
e
メッセージを識別するためのフィールド. 3が 入 る こ と で RERRメッセージで
あると識別される.
• N (NoD
e
l
e
t
eF
l
a
g
)
ローカル経路修復を行う時に使用される.上流端末は経路の削除をずべき
でないという情報を知らせる.
• r
e
s
e
r
v
e
d
送信予約をする際に， 0を 格 納 す る . 受 信 時 は 無 視 さ れ る .
二三重大学大学院
工学研究科
第 3章 AODV
2
5
• d
e
s
tc
o
u
n
t
メ ッ セ ー ジ 内 に 含 ま れ る 非 到 達 送 信 先 端 末 数 を 格 納 す る . 1以上の値が入る.
• u
n
r
e
a
c
h
a
b
l
ed
e
s
t
i
n
a
t
i
o
nI
Pa
d
d
r
e
s
s
リンク切断のために，到達不可の送信先 I
Pア ド レ ス を 格 納 す る .
• u
n
r
e
a
c
h
a
b
l
ed
e
s
t
i
n
a
t
i
o
ns
e
q
u
e
n
c
enumber
リンク切断のために，到達不可の送信先シーケンス番号を格納する.
3
.
4 AODVの処理
本節では，送信元端末への経路を構築するための処理について述べる.
3.
4.
1 シーケンス番号の管理
経路上にある全ての端末は，常に送信先アドレスに対して最新のシーケンス番
号を維持する必要がある.このシーケンス番号を送信先シーケンス番号と呼ぶ.
送信先シーケンス番号は，端末が受信した経路制御メッセージから新しい情報を
取 得 し た 場 合 に 更 新 す る . AODVで は ， 各 端 末 が 送 信 先 シ ー ケ ン ス 番 号 の 管 理 を
行う.送信先シーケンス番号は， 2つ の 条 件 で 自 身 の 番 号 を イ ン ク リ メ ン ト す る .
-端末が経路探索を行う前に，自身のシーケンス番号をインクリメントする.
これにより， RREQ生 成 端 末 へ の 逆 経 路 と の 一 致 を 防 ぐ .
- 送 信 先 端 末 が RREPメッセージを送信する直前に，自身のシーケンス番号と
RREQメ ッ セ ー ジ 内 の 送 信 先 シ ー ケ ン ス 番 号 の 最 大 値 へ シ ー ケ ン ス 番 号 を イ
ンクリメントする.
送信先端末に関するシーケンス番号が最新であることを確認するため，端末は
現在のシーケンス番号の数値を，受信したメッセージのシーケンス番号と比較す
る.受信したメッセージのシーケンス番号から現在のシーケンス番号を引いた値
が O未 満 で あ る 場 合 ， 受 信 し た シ ー ケ ン ス 番 号 は 古 い 情 報 で あ る た め ， メ ッ セ ー
ジの送信先端末に関する情報は破棄される.
三重大学大学院
工学研究科
第 3章 AODV
送信先シーケンス番号は
2
6
送信先端末への次ホップに対するリンクが切断され
るか，寿命となる場合にも変更される.この場合，端末は自身の経路表を参照す
ることで次ホップを送信先端末とする.そして，次ホップを使用する送信先端末に
ついて，シーケンス番号をインクリメントし，経路を無効状態として記録する.
以下の場合に，端末は送信先端末へのシーケンス番号を更新する.
-自身が送信先端末で，新しい経路を提供する場合.
-送信先端末へのシーケンス番号に関する新しい情報を保持するメッセージを
受信した場合.
-送信先端末への経路が切断されるか，寿命となる場合.
3.
4.
2 経路構築処理
AODVプ ロ ト コ ル の 経 路 構 築 処 理 に つ い て 述 べ る .
経路探索
図3
.
4
に
， RREQメッセージのフローチャートを示す.また，図 3
.
5に
， RREPメッ
セージのフローチャートを示す.
送信元端末が通信要求を発生した場合，まず自身の経路表を参照する.送信先
端末への経路を保持していた場合，次ホップヘデータパケットを送信する.経路
を保持していない場合，データパケットは送信待ちバッファに格納され，経路構築
プ ロ セ ス を 開 始 す る . 送 信 元 端 末 は RREQメッセージを生成し，ネットワーク内
の端末へメッセージをブロードキャストする.
RREQメッセージを受信した中継端末はシーケンス番号を確認し，最新の経路で
あ れ ば RREQメッセージの再ブロードキャストを行う. RREQメッセージのブロー
ドキャストは，ネットワークへの過剰なパケットの拡散を招く.そこで， AODVで
は TTLを 利 用 す る こ と で RREQメッセージの拡散制御を行う. TTLはメッセージ
が Iホップ転送されるごとに一つずつ減少し， 0に な る と メ ッ セ ー ジ は 破 棄 さ れ
る.最初の探索で TTLは 初 期 値 に 設 定 さ れ る . 一 定 時 間 以 内 に RREPメッセージ
三重大学大学院
工学研究科
第
3章 AODV
2
7
Updater
o
u
t
i
n
gt
a
b
l
e
End
図3
.
4AODVにおける RREQメッセージのフローチャート
三電大学大学院
工学研究科
第 3章
AODV
2
8
S
t
a
r
t
D
e
s
t
i
n
a
t
i
o
nnode
sendsbackready
s
i
g
n
a
l(RREP)
Updater
o
u
t
i
n
gt
a
b
l
e
Yes
No
ForwardRREP
t
onexthop
Sendqueuemessage
End
図3
.
5AODVにおける RREPメッセージのフローチャート
三事;大学大学院
工学研究科
第 3章
が得られない場合，
しかし，
AODV
2
9
TTLを 一 定 値 増 加 さ せ て RREQメッセージの再転送を行う.
TTLがある値以上になっても RREPメッセージが得られない場合，ネット
ワーク全体を探索できるよう
TTLを設定する.
経路確定
RREPメッセージは，送信先端末が RREQメッセージを受信した場合，送信先端
末 へ の 有 効 な 経 路 を 持 つ 端 末 が RREQメ ッ セ ー ジ を 受 信 し た 場 合 に 生 成 さ れ る .
-送信先端末が
RREPメ ッ セ ー ジ を 生 成 す る 場 合
RREPメッセージのシーケンス番号に Iを 加 え た 値 と ， 送 信 先 端 末 の シ ー ケ
ンス番号を比較し，大きい方の値を
RREQメ ッ セ ー ジ の シ ー ケ ン ス 番 号 と
する.
- 送 信 先 端 末 へ の 経 路 を 持 つ 端 末 が RREPメ ッ セ ー ジ を 生 成 す る 場 合
端末が保持する順経路エントリに基づき，送信先シーケンス番号，ホップ数
が設定される.そして，端末が保持する送信先端末への順経路と送信元端末
への逆経路のエントリを更新する.
RREPメ ッ セ ー ジ は 送 信 先 端 末 と 送 信 元 端 末 へ メ ッ セ ー ジ を 転 送 す る た め に 必
要な情報が付加され，送信を行う.そして，受信した
RREQメッセージが経由し
てきた経路を用いて送信元端末へユニキャストで送信される.一方，送信元端末
で複数の
RREPメ ッ セ ー ジ を 受 信 し た 場 合 は 最 初 に 受 信 し た メ ッ セ ー ジ を 採 用 す
る.しかし，先に受信した
RREPメッセージのホップ数より少ないホップ数の場合
や，送信先シーケンス番号が大きい場合は経路を更新することが可能である.こ
れらの処理により，送信元端末は経路を確立する.経路を確立すると，送信元端
末はデータパケットの送信を開始する.
経路構築例
図3
.
6に AODVで の 経 路 構 築 の 動 作 例 を 示 す . 図 3
.
6で は ， 端 末 8
1から D1 へ
の通信を行うための経路構築を行う状況を示す.端末
三主主大学大学院
工学研究科
81 は RREQメッセージを
ν
m
第 3章
AODV
3
0
.
.
.
.
・
+
RREQ
RREP - ー キ
Sourcenode
C3
¥
/
.
.
‘
①
f
図
3
.
6AODVの 経 路 構 築 例
生成し， ネットワーク全体にプロードキャストする .RREQメッセージを受信した
， D1 へ の 経 路 を 保 持 し て い な い た め ， 再 度 RREQメッセージの
端 末 A，B，C は
プロードキャストを行う.次に， RREQメ ッ セ ー ジ を 受 信 し た 端 末 E，Fは 送 信 先
端末の探索のために再度プロードキャストを行う.結果， C，Fを経由した RREQ
メッセージが最初に D1に到達する. AODVで は ， 最 初 に 送 信 先 端 末 に 到 達 し た 経
路に返信を行うため， RREPメッセージは RREQメッセージの逆経路である
F，C
を 経 由 し て 81へ 転 送 さ れ る . 81が RREPメ ッ セ ー ジ を 受 信 す る と ， 経 路 構 築 が
完了し， デ ー タ の 送 信 が 開 始 さ れ る .
3.
4.
3 経路維持
アドホックネットワークでは，無線環境は常に変化する. そ の た め ， 経 路 構 築 後
も 近 隣 通 信 の 影 響 な ど に よ り 構 築 し た 経 路 が 有 効 で な く な る 場 合 が あ る . リンク
切断が起こった場合その影響がネットワーク全体に影響を与えるため，送信元端
末 へ そ の 情 報 を 知 ら せ ， 経 路 を 再 構 築 す る 処 理 が 必 要 と な る . 本 項 で は ， リンク
切断が起こった場合の
AODVプ ロ ト コ ル の 経 路 維 持 に つ い て 述 べ る .
三電大学大学院
工学研究科
第 3章 AODV
3
1
経路再構築
c
c
e
s
sC
o
n
t
r
o
l
)層 か ら の 通 知 に 基 づ い て 検 出
パケット送信の失敗は， MAC(MediaA
EEE802.11ではパケット送信後， RTS(RequestToS
e
n
d
)送 信 後 に CTS(Clear
する. I
ToS
e
n
d
)が 受 信 さ れ な い 場 合 や ， 確 認 応 答 メ ッ セ ー ジ (ACK)が 受 信 さ れ な い 場 合
にパケット送信が失敗したことを検出する.そして，一定回数以上の再送を行っ
てもパケットを送信できない場合にリンク切断と判断する.
リンク切断を検出した端末は，そのリンクを使用していた経路のエントリを無
効化し， RERRメッセージを生成する. RERRメッセージは，無効化された経路の
Pア ド レ ス の リ ス ト を 入 れ ， プ ロ コ ー サ リ ス ト へ 送 信 す る . こ の
送信先端末の I
時 ， 送 信 先 シ ー ケ ン ス 番 号 を 一 つ イ ン ク リ メ ン ト し ， RERRメッセージに格納す
る.プリコーサリストが一つの場合は，ユニキャストで送信する.プリコーサリ
ストが複数存在する場合は，ユニキャストでの送信を繰り返すか， TTLを Iとし
てブロードキャストで送信する. RERRメッセージを受信した端末は， RERRメッ
セージの不達送信先端末のリストを参照する.そして，経路表の中にリストに含
ま れ る 送 信 先 端 末 へ の 経 路 が あ り ， そ の 経 路 の 次 ホ ッ プ が RERRメッセージを送
信して来た隣接端末である場合は，その経路を無効化する.経路表を更新した端
末は，新たな経路表に基づく RERRメ ッ セ ー ジ を 生 成 し ， プ リ コ ー サ リ ス ト へ 送
信する. RERRメ ッ セ ー ジ の 転 送 を 繰 り 返 す こ と で ， 送 信 元 端 末 に リ ン ク 切 断 が
通知される.送信元端末では経路を無効化し，通信を継続する必要がある場合は
経路構築を再度開始する.
.
7に，リンク切断により RERRメッセージが送信された例を示す。図 3
.
7では，
図3
端 末 F，D1 間 で リ ン ク 切 断 が 起 こ り ， 端 末 D1 に 対 す る 上 流 端 末 に 対 し て RERR
メッセージを送信している.端末 C が RERRメッセージを端末 81に通知すること
で，経路が無効化される.
ローカル経路修復
中継端末がパケットの送信中にリンク切断を検出した時，送信先端末までのホッ
プ数が一定値以下の場合に，送信元端末からの経路を保持したまま，送信先端末
への代替経路を構築することが可能である.これをローカル経路修復という.ロー
三項大学大学院
工学研究科
①'
第 3章
AODV
3
2
RERR-~砂
f
o
r
w
a
r
d
i
n
gr
o
u
t
e- .
.
w
i
r
e
l
e
s
sl
i
n
k-
Sourcenode
EB
B-
，
，
‘
.，
，
，
，
，
，
，
①
、
、
、
、
①
‘
.
D
e
s
t
i
n
a
t
i
o
nnode
図3
.
7AODVの RERR送 信 例
カル経路修復では， リ ン ク 切 断 を 受 信 し た 端 末 が 送 信 先 シ ー ケ ン ス 番 号 を 一 つ 増
加 し て RREQメッセージをブロードキャストする.一定時間以内に RREPメッセー
ジ が 得 ら れ な か っ た 場 合 は ， 通 常 の リ ン ク 切 断 と 同 様 に RERRメ ッ セ ー ジ を 送 信
する. RREPメ ッ セ ー ジ が 得 ら れ た 場 合 ， 新 た な 経 路 と 以 前 の 経 路 の 送 信 先 端 末
へのホップ数を比較する.新たな経路のホップ数は以前の経路のホップ数を上回る
場合， N フ ラ グ を 立 て た RERRメ ッ セ ー ジ を 送 信 元 端 末 へ 通 知 す る . N フラグを
立 て た RERRメ ッ セ ー ジ を 受 信 し た 端 末 で は 経 路 の 無 効 化 は さ れ な い . その後，
R阻 P メ ッ セ ー ジ の 送 信 を 行 い ， 送 信 元 端 末 の 経 路 情 報 の 更 新 を 行 う . R
阻 P メッ
セージが送信元端末に到達すると，経路修復が完了する.
三重大学大学院
工学研究科
第 4章
近隣通信に基づく経路制御手法の提案
本章では，提案方式である近隣通信に基づくルーチング手法について述べる.最
初に，複数の通信が行われている環境で既存のルーチングプロトコルを用いた場
合の問題について説明する.また，提案方式である近通信状況に基づくルーチン
グ手法について述べ，提案方式の有効性を計算機シミュレーションにより明らか
にする.
4
.
1 近隣通信が経路構築に与える影響
一般に，無線信号は端末を中心として円状に広がる.そこで，経路構築により
特定の端末や帯域へ負荷が集中した場合，端末は近隣端末の通信の影響を大き
く受けることが予想される.また，アドホックネットワークを実現するための無
0
2
.
1
1な ど で は ， ラ ン ダ ム ア ク セ ス に よ
線 通 信 デ バ イ ス と し て 想 定 さ れ る IEEE8
e
n
s
eM
u
l
t
i
p
l
eA
c
c
e
s
swith
るコンテンション方式をベースとした CSMAjCA(CarrierS
C
o
l
l
i
s
i
o
nAv
o
i
d
a
n
c
e
)を 用 い て 無 線 資 源 の 共 有 を 実 現 し て い る . CSMAjCAでは，通
信を行う前にキャリアセンスを行うことで無線チャネルの使用状況を確認する.そ
の後，他の端末の送信信号が存在する場合は送信を延期する.未使用であると判
断される場合はランダムな時間待ったのちに送信を行う.このようにすることで，
複数の端末が一斉にパケット送信を行うことを防止している.パケットの送信は，
A
c
k
n
o
w
l
e
d
g
e
)フ レ ー ム が 到 着 す る こ と で ， 正 し く 送 信 さ れ た
受 信 側 か ら の ACK(
と判断している.
3
3
三噴大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
園 田 園 園 田
E
3
4
t
r
a
n
s
m
i
s
s
i
o
nr
o
u
t
e
・ ・.
I
i
n
k
E
.s
e
n
s
l
n
garea
図4
.
1近 隣 通 信 に よ る 経 路 構 築 へ の 影 響
CSMAjCAで は パ ケ ッ ト の 衝 突 を 回 避 す る た め に 端 末 に 送 信 機 会 を 確 率 的 に 割
り当てるため，近隣通信量に応じて，自端末の送信機会が得られる頻度も大きく
.
1では，端末 810 82，83 が通信を行っている例を示す.パケットの
変化する.図 4
転 送 を 行 う 時 ， 端 末 81> F が パ ケ ッ ト の 転 送 を 行 う 場 合 ， 近 隣 通 信 に よ る 影 響 が
少ないため送信機会が得られる確率が高くなると考えられる.しかし，端末 C な
どでは，近隣通信により送信機会が大きく低下する.
4
.
2 近隣通信状況に基づくルーチング手法
本論文では，トラヒックを考慮した経路構築を行うため，既存のルーチングプ
ロトコルに適応することが可能である手法を提案する.また，リアクティプ型の
代 表 的 な AODVを 例 と し て 用 い る . 提 案 方 式 で は ， 各 端 末 が 観 測 し た 帯 域 占 有 率
に基づいて経路の優先度の制御を行うことで複数の安定した経路の構築を行うこ
三'it大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
35
s
i
g
n
a
l
.
.
.
・
.
.interference
-一一 l
i
n
k
.s
e
n
s
l
n
ga
r
e
a
-....oI~transmission
，
，
，
•• •
図4
.
2端 末 C に お け る 信 号 受 信 例
とを目標としている. AODVで は ， 送 信 先 端 末 に 最 初 に 届 い た
を用いて経路構築を行うことから，提案方式では，
RREQメッセージ
RREQメ ッ セ ー ジ 転 送 時 の 転
送遅延量を各端末が観測した帯域占有率に基づいて制御することで，優先度の高
い RREQメ ッ セ ー ジ が よ り 早 く 送 信 先 端 末 に 到 着 す る よ う に 制 御 す る .
4
.
2
.
1 帯域占有率
提案方式では，各端末が利用可能な無線資源の指標として，端末が一定期間内
に近隣端末からの信号を受信した期間の割合に着目する.また，この割合を帯域
占有率と呼ぶものとする.帯域占有率の計算のために，端末は受信信号と受信電
力の情報，コネクシヨンの情報を保存する.帯域占有率として反映させる受信信
号 レ ベ ル は ，CSMAjCAの セ ン シ ン グ 闘 値 を 用 い る . ま た ， 受 信 信 号 に は 自 ら を
経由するコネクションに関わる信号が含まれることから，各信号のコネクション
三重大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
36
82
一
C
83
.
.
.
l@EEEl @
Ii
'
•
⑤
Ii
E
D3
G
@
主
」
81
t
・
，
II
4
A1
「τ
す「
"
'
i
t
i
m
e
(
s
)
D
園4
.
3端 末 C に お け る 受 信 信 号 の メ ッ セ ー ジ フ ロ ー
情報を利用することで自らの通信に関わる影響を除いた帯域占有率を求める.コ
ネクション情報を判断できない場合は，他の通信に関わる信号として処理を行う.
端 末 X が 信 号 を 信 号 観 測 期 間 D の 間 に 受 信 し た 場 合 ， 受 信 信 号 を A とすると，
帯 域 占 有 率 Oxは ， 次 の よ う に 表 す こ と が で き る .
ハ(2:~=1 An)
vx= y
j
(
4
.
1
)
図4
.
2に端末 C の信号受信例を示す.また，その際のパケット受信のタイミング
を図 4
.
3に示す.
2が信号を送信する場合， CSMAjCAにより近隣の通信状況の確認を行う.
端末 8
2，83
一方，端末おも信号を送信するために近隣通信状況の確認を行うが，端末 8
は互いのセンシング範囲より外側に存在するため同時に信号を送信している.端
末 Cで は ， 端 末 ぬ か ら の 信 号 と ， 干 渉 と し て ぬ か ら の 信 号 を 受 信 す る た め ， 信
号の衝突が起こる.そのため，端末 Cでは受信した信号のコネクション情報の判
.
3より，端末 C で は 端 末 82 の 信 号 の 受 信 開 始 か ら ， 干 渉 と し
断はできない.図 4
て受信した端末ぬの信号の受信終了までの時間が受信信号んとなる.その後，
三重大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
37
端 末 C では，端末 G が 端 末 D2 に 送 信 し た 信 号 を 干 渉 と し て 受 信 し ， こ の 信 号 が
受 信 信 号 A2となる.また，端末 81か ら 信 号 を 受 信 す る が ， 端 末 ぬ か ら の 信 号 は
端 末 C が自らの通信に関わる信号であるため，帯域占有率の計算には含めない.
よって，端末 C が 端 末 81 から RREQメ ッ セ ー ジ を 受 信 し た 時 の 帯 域 占 有 率 00は
次のように表される.
ム
ー
1
-A~
oc=」
7
二
(
4
.
2
)
帯域占有率を指標として採用することにより，端末は実際に送信可能な無線信
号の時間割合を知ることができ，送信可能な時間割合が多い端末を優先する経路
構築が実現可能となる.
4
.
2
.
2 提案方式における経路探索手順
4
に
， RREQメ ッ セ ー ジ を 受 信 し た 際 の 中 継 端 末 と 送 信 先 端 末 の 動 作 を 示
図 4.
.
5に，端末での負荷算出の動作を示す.
す.また，図 4
経路探索手順
送信要求が発生した場合， AODVと 同 様 に 送 信 元 端 末 は 新 た に R阻 Qメッセー
ジを生成し，ネットワーク全体にフラッデイングを行う.また，一定時間を待って
も RREPメッセージを受信できない場合には， RREQメ ッ セ ー ジ の シ ー ケ ン ス 番
号 を 増 加 さ せ た の ち ， 再 び RREQメッセージのフラッデイングを行う .RREQメッ
セージを受信した近隣端末は，自端末のアドレスが送信先端末として指定されて
い な い の か を 確 認 す る . 自 端 末 宛 の RREQメ ッ セ ー ジ で は な い 端 末 は ， 中 継 端 末
となり送信元端末からのホップ数を記録するとともに，コネクション情報の確認を
行い，受信信号から自らの関与したコネクションに関する信号を除く.そして，端
末 は 自 端 末 が 利 用 可 能 な 無 線 資 源 の 時 間 割 合 を 考 慮 す る た め に ， RREQメッセー
ジ受信前の一定期間の帯域占有率を計算する.また，端末は帯域占有率に応じた
RREQメ ッ セ ー ジ の 転 送 遅 延 時 間 を 設 定 す る こ と で ， 経 路 構 築 に 関 わ る 積 極 性 を
変更する. AODVで は 最 初 に 送 信 先 端 末 に 到 着 し た RREQメッセージが経由した
三重大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
図 4.4提案方式における RREQメッセージのフローチャート
三重大学大学院
工学研究科
38
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
S
t
a
r
t
D
e
l
e
t
et
h
es
i
g
n
a
lbelow
t
h
esensingl
e
v
e
l
C
a
l
c
u
l
a
t
et
h
et
o
t
a
ls
i
g
n
a
l
r
e
c
e
p
t
i
o
nt
i
m
e
C
a
l
c
u
l
a
t
e
t
h
esameconnection
i
n
f
o
r
m
a
t
i
o
ns
i
g
n
a
l
End
図4
.
5提 案 方 式 に お け る 負 荷 計 算 の フ ロ ー チ ャ ー ト
三重大学大学院
工学研究科
39
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
4
0
経路を構築するため，転送遅延時間は帯域占有率が高いほど長い時聞が設定され
るものとする.端末は設定された遅延時間後，
RREQメッセージのフラッディング
を行う.なお，端末が同一シーケンス番号を含む
た場合，最初に到着した
RREQメッセージを複数受信し
RREQメ ッ セ ー ジ の み の 転 送 処 理 を 行 う も の と す る .
経路確定手順
受信した
RREQメ ッ セ ー ジ の 送 信 先 端 末 ア ド レ ス と 端 末 の ア ド レ ス が 一 致 し た
場合，端末は
RREPメッセージを生成し， RREQメ ッ セ ー ジ が 経 由 し て き た 経 路
を用いてユニキャストで送信元端末に
RREPメッセージの送信を行う.
4
.
2
.
3 データパケットの配送
送信元端末は
RREPメ ッ セ ー ジ を 受 信 し た こ と に よ り 経 路 構 築 が 完 了 し た こ と
を検出し，データパケットの送信を開始する.提案方式では，高トラヒックとなって
いる領域に存在する端末に対して長い転送遅延を設定し，経路構築に積極的に参
加 さ せ な い こ と で 帯 域 占 有 率 の 低 い 端 末 を 経 路 と し て 選 択 す る . そ の た め AODV
と比較して，複数の通信が行われている場合にもデータパケットを安定して送信
できる可能性が高くなる.
4.3 動作例
図4
.
6に ， 提 案 方 式 に よ る 経 路 構 築 の 動 作 例 を 示 す . ま た ， そ の 際 の パ ケ ッ ト 送
信タイミングを図 4
.
7に示す.図 4
.
6の動作例では，端末 82 と端末 D2' 端 末 83と
端 末 D3が 既 に 通 信 を 行 っ て お り ， 新 た に 端 末 ぬ か ら 端 末 D1へ の 通 信 を 行 う た め
の経路構築を行う状況を考える.
経路探索手順
端末
81 は RREQメッセージを生成し，送信先端末の探索のため，ネットワーク
全体にフラッデイングを開始する. RREQメッセージがフラッデイングされると，中
三重大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
4
1
+ - - RREP
田
ー
ー
ー transmissionroute
l
i
n
k
図4
.
6提 案 方 式 の 経 路 構 築 例
継 端 末 で あ る 端 末 A，B，C，E，F は，受信した RREQメ ッ セ ー ジ を 再 転 送 し ， 経
路 を 構 築 す る . 端 末 A，C が RREQメッセージを受信すると， RREQメッセージを
再転送する前に端末の帯域占有率を計算する.この時，端末 Cで は 近 隣 通 信 の 影
響により帯域が混雑しているため帯域占有率が高くなり，混雑した帯域を避ける
ために図 4
.
7に 示 さ れ る 長 い 遅 延 量 が 設 定 さ れ る . 一 方 ， 端 末 A で は 近 隣 で 通 信
が行われていないため，帯域占有率が低くなることによる短い遅延量が設定され
る.同様に，端末 B，E，F においても， RREQメ ッ セ ー ジ を 受 信 す る と 帯 域 占 有 率
.
7に 示 さ れ る よ う に ， 帯 域 占 有 率 に 基 づ い た 遅
に基づいた転送が行われる.図 4
延 量 を 各 端 末 が 設 定 す る こ と に よ り ， 近 隣 通 信 の 影 響 が 少 な い 端 末 A，B，E，F を
経 由 し た RREQメ ッ セ ー ジ が 最 初 に 送 信 先 端 末 に 到 達 す る .
三主主大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
E
._.~:.:"
F
4
2
，
.
.
...............~...
…吋阪司
De
蜘 a
t
i
o
nDl
!
t
i
n
1
e
(
s
)
図4
.
7経 路 構 築 時 の 制 御 メ ッ セ ー ジ フ ロ ー
経路確定手順
送 信 先 端 末 が R阻 Q メッセージを受信すると， AODVと 同 様 に 最 初 に 送 信 先 端
末 に 到 達 し た RREQメッセージに対して RREPメッセージの生成を行う.よって，
端 末 A，B，E，F を 経 由 す る 経 路 が 構 築 さ れ る .
4.
4 計算機シミュレーションによる特性評価
提案方式の有効性を明らかにするために，ネットワークシミュレータ Qualnetを
利用したコンビュータシミュレーションを実施した.表 4
.
1にシミュレーションパラ
メータを示す.
.
2を利用し
ま た ， 提 案 方 式 の 帯 域 占 有 率 に 対 す る RREQの 転 送 遅 延 時 間 は 表 4
m
s
]線 形 に 増 加 さ
た . 転 送 遅 延 時 間 は ， 帯 域 占 有 率 が 1%上昇するのに対して， 1[
せる.一方，高トラヒック領域に存在する端末の経路積極性を下げるため，帯域
m
s
]線 形 に 増 加 さ せ る . ま た ， 帯 域 占
占 有 率 が 21%以上では，伝送遅延時間をlO[
有 率 が 41%以 上 で は ， 伝 送 遅 延 時 間 を 600[
m
s
]に固定した.
三重大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
43
表4
.
1シミュレーションパラメータ
S
i
m
u
l
a
t
o
r
Qualnet
S
i
m
u
l
a
t
i
o
ntime
5
0
0
[
s
]
Networka
r
e
a
1
1
0
0
0
[
m
]x 1
1
0
0
0
[
m
]
Numbero
fnodes
200
Nodep
l
a
c
e
m
e
n
t
Uniform
C
a
l
lg
e
n
e
r
a
t
i
o
n
P
o
i
s
s
o
nd
i
s
t
r
i
b
u
t
i
o
n
配 t
i
o
n
s
5
'
"
"
2
0
c
o
n
n
Datap
a
c
k
e
ts
i
z
e
1
0
2
4
[
b
y
t
e
]
Av
e
r
a
g
es
i
g
n
a
lc
o
n
t
i
n
u
et
i
m
e e
x
p
o
n
e
n
t
i
a
ld
i
s
t
r
i
b
u
t
i
o
n
2
0
[
s
]
τ
'
ra
血c
6
4
K
[
b
y
t
e
j
s
]
P
h
y
s
i
c
a
ll
a
y
e
r
IEEE802.11g
Datar
a
t
e
戸l
6M[b
P
r
o
p
a
g
a
t
i
o
np
a
t
h
l
o
s
smodel FREE-SPACE
A
p
p
l
i
c
a
t
i
o
n
CBR
Routingp
r
o
t
o
c
o
l
AODV
Numbero
ft
r
i
a
l
s
5
0
t
h
4.
4.
1 経路構築遅延時間
図4
.
8に ， 平 均 コ ネ ク シ ョ ン 数 に 対 す る 経 路 構 築 遅 延 時 間 を 示 す . 遅 延 時 間 は ，
送信元端末より経路要求が発生し，データパケットが送信されるまでの時間を示
す . 結 果 よ り ， 帯 域 占 有 率 を 用 い た 提 案 方 式 は 低 ト ラ ヒ ッ ク 環 境 で は AODVと同
等の性能となるものの，高トラヒック環境では経路構築遅延時間を削減している
ことが確認できる. AODVでは，最短ホップで経路を構築するため，高トラヒック
となる帯域での送信機会が減少し，経路構築遅延時間も大きくなったと考えられ
三重大学大学院
工学研究科
第 4章
近隣通信に基づく経路制御手法の提案
44
表4
.
2帯 域 占 有 率 に 基 づ く 転 送 遅 延
帯域占有率
転送遅延(増分)
1
"
'
2
0
10ms"'29ms (
1ms)
2
1"
'
4
0
l
O
ms)
30ms"'220ms (
4
1
600ms
)knsoQg。ZQE
何
回
∞
ロ
。υ35。
出
∞
(
0
.
8
5
P
r
o
p
o
s
e
deAODV ・・持・
0
.
8
0
.
7
5
0
.
7
~)(.
.
0
.
6
5
.?(・..
t
、
、 ， 右J
0
.
6
0
.
5
5
6
8
1
0
12
1
4
16
1
8
20
Av
e
r
a
g
eLoad(
c
o
n
n
e
c
t
i
o
n
s
)
図4
.
8経 路 構 築 遅 延 時 間
る. 一 方 ， 提 案 方 式 で は 近 隣 通 信 を 避 け た 経 路 の 構 築 を 行 う こ と で パ ケ ッ ト の 送
信機会が増え，遅延時聞が向上したと考えられる.
4.
4.
2 総端末数に対するスループット特性
図4
.
9に，平均コネクション数に対するパケット到着率を示す.結果より， AODV
の パ ケ ッ ト 到 着 率 は ト ラ ヒ ッ ク の 増 加 に 対 し て 劣 化 す る こ と が 確 認 で き る . AODV
では，最短ホップで経路を構築するため近隣通信の影響を大きく受けたためであ
三重大学大学院
工学研究科
第 4章
近隣通信に基づく経路制御手法の提案
0
.
9
5
0
.
9
4
。36出
0
.
9
3
•••
•••
•••
•••
••
•••••
•••••
•••
-
WA
0
.
9
1
P
r
oposedー毛ト
AODV.・持・
-
0
.
9
vh
0
.
8
9
-
・
hho
乙古口古川占 Qd円同
0
.
9
2
4
5
••••
•••
•••
•••
••
0
.
8
8
0
.
8
7
0
.
8
6
6
8
1
0
1
2
1
4
1
6
1
8
20
Av
e
r
a
g
eL
o
a
d(
c
o
n
n
e
c
t
i
o
n
s
)
図4
.
9パケット到着率
ると考えられる.一方，提案方式は高トラヒックの状況においても，パケット到着
率の劣化を抑えていることがわかる. これは，提案方式では低トラヒック領域に
存在する端末が積極的に経路構築に関与しているため，近隣通信の影響を受けに
くい経路が構築されているためであると考えられる.
4.
4.
3 正規化リンク切断数
図4
.
1
0に ， 平 均 コ ネ ク シ ョ ン 数 に 対 す る 正 規 化 リ ン ク 切 断 数 を 示 す . 正 規 化 リ
ンク切断数は， リ ン ク 切 断 数 を 送 受 信 デ ー タ パ ケ ッ ト 数 で 正 規 化 し た 値 で あ る .
結 果 よ り ， 提 案 方 式 に お け る リ ン ク 切 断 が 減 少 し て い る こ と が 分 か る . AODVで
は
， リ ン ク 切 断 は デ ー タ リ ン ク 層 の パ ケ ッ ト 損 失 に よ り 発 生 す る . そのため，図
4
.
9と同様に， 高 ト ラ ヒ ッ ク と な っ て い る 帯 域 に 存 在 す る 端 末 を 避 け る こ と で ， 近
隣通信による影響が減少したためであると考えられる.
三重大学大学院
工学研究科
第 4章 近 隣 通 信 に 基 づ く 経 路 制 御 手 法 の 提 案
••
0
.
0
1
1
•••
•
•
••
0
.
0
0
6
0
.
0
0
5
0
.
0
0
4
•••
•
•
•••
•
•
••
•••
••
•
•
•••
x
0
.
0
0
7
-
ny
AV
ハU
υ
A
ロ
ロ
。z
-54-xuN26
460
何
回u
••
•
•
••••
•
••••
x
P
r
o
p
o
s
e
d--Er
0
.
0
1
AODV・・持・
0
.
0
0
8
46
•
3
弓
AU
AU
υ
A
6
8
1
0
1
2
1
4
1
6
1
8
2
0
Av
e
r
a
g
eLoad(
c
o
n
n
e
c
t
i
o
n
s
)
図4
.
1
0正 規 化 リ ン ク 切 断 数
4.
4.
4 正 規 化 RREQメッセージ数
図4
.
1
1に，平均コネクション数に対する正規化 RREQメッセージ数を示す.正規
化 RREQメッセージ数は， RREQメッセージ数を送受信データパケット数で正規化
した値である.結果より，総端末数が増加するに伴い，制御パケット数は増加する
傾 向 が あ る こ と が 分 か る . しかし， ADOVに 対 し て 提 案 方 式 の RREQメッセージ
数が削減されていることが確認できる.特に，平均呼量が 1
5，2
0の時，提案方式
0%程度の RREQメッセージを削減している. RREQメッセージは，経路構
は約 2
築における制御メッセージの多くを占めるパケットであるため， RREQメッセージ
の削減は意義があると思われる.
三重大学大学院
工学研究科
第 4章
近隣通信に基づく経路制御手法の提案
5
針。p
osedー毛ト
4.
5
AODV..持・
国
σ同出回甘ON--eロロo
z
u
n
4
x
3
.
5
3
2.
5
2
6
8
1
0
1
2
1
4
1
6
Av
e
r
a
g
eLoa
d(
c
o
n
n
e
c
t
i
o
n
s
)
図4
.
1
1正 規 化 RREQメ ッ セ ー ジ 数
三重大学大学院
_l学研究科
1
8
20
4
7
第 5章
結論
5
.
1 本研究のまとめ
アドホックネットワーク用ルーチングプロトコルは多数あるが， AODV(Ad-Hoc
OnDemandD
i
s
t
a
n
c
eV
e
c
t
o
r
)な ど の 多 く の プ ロ ト コ ル は ， 最 小 ホ ッ プ ル ー チ ン グ を
採用しており，送信先端末までの経路ホップ数が最小となる経路選択を行う.一
方，アドホックネットワークでは，複数の端末が同時に通信を行うことが想定さ
れるため，端末のトラヒック状態を考慮することにより，特定の経路へのトラヒツ
クの集中を防ぐ負荷分散型ルーチングも近年研究されている.負荷分散型ルーチ
ングを利用することにより，ネットワーク内の総スループットを改善可能である
ことが知られている.しかし，正確なトラヒック量の把握と，各経路上の負荷情
報を収集することによるオーバーヘッドの増大が問題点として挙げられている.
本論文では，互いの無線信号が到達しない経路を複数構築することにより，空間
的に無線資源の有効利用を可能とし，安定した経路構築を行った.そこで，端末
が受信する近隣通信量に着目することにより，自端末が利用可能な無線資源の推
定を行い，利用可能な無線資源に応じて端末の経路構築に関わる積極性を変化さ
せるルーチングプロトコルの提案を行った.提案方式では，高トラヒック領域に
存在する端末の経路構築への積極性を引き下成低トラヒック領域に存在する端
末の経路構築への積極性を引き上げる.結果として，提案方式では経路構築の際
に新たな制御メッセージの収集を行うことなく，高トラヒック領域を迂回する経
路を構築可能となる.提案方式は様々なルーチングプロトコルの拡張として実装
48
三重大学大学院
工学研究科
第 5章 結 論
49
可能であるが，本論文では，代表的なアドホックネットワーク用ルーチングプロ
トコルである AODVを 拡 張 す る こ と に よ り 評 価 を 行 っ た . 数 値 例 よ り ， 提 案 方 式
を用いることにより，特に高トラヒック時の経路構築遅延時間，パケット到着率，
RREQメ ッ セ ー ジ 数 が 改 善 可 能 で あ る こ と を 示 し た . ま た ， 提 案 方 式 で は 各 端 末
が自律的に収集した帯域占有率に基づき自律的に経路構築に関わる積極性を更新
できることから，オーバーヘッドが増加することなくトラヒック状況を考慮可能
な経路構築を実現可能である.
三重大学大学院
工学研究科
参考文献
[
1
] E羽 .
R
ρ
'
y
e
r組 dC
.
K.Toh，
“ Ar
e
v
i
e
wo
fc
u
r
r
e
n
tr
o
u
t
i
n
gp
r
o
t
o
c
o
l
sf
o
radhocm
o
b
i
l
e
令
w
i
r
e
l
e
s
sn
e
t
w
o
r
k
s，
"IEEEP
e
r
s
.Com
皿u
n，Vo
1
.6，No.2，pp.
4
6
5
5，A
p
r
i
l1
9
9
9
.
0
0
7
.
[
2
] AndreaGoldsmith，“ワイヤレス通信工学?"丸善， August2
K.Toh，“アドホックモパイルワイヤレスネットワークープロトコルとシステ
[
3
]C
.
-
ムf共立出版， June2
0
0
3
.
[
4
] 総務省，“平成 2
1年版情報通信白書，"2
0
0
9
.
[
5
] 蓮池和夫， B
.Sompr
叫ash
，植田哲郎，“アドホックネットワークの技術的課題f信
B
)，VoLJ85-B，No.12，p
p
.
2
0
0
7
2
0
1
4，2
0
0
2
.
学論 (
[
6
]S
.
C
o
r
s
o
n叫
J.Mac
k!民“ M
obileadhocnetworking(MANET) :Ro
u
t
加 gp
r
o
t
o
c
o
l
p
e
r
f
o
r
m
a
n
c
ei
s
s
u
e
sande
v
a
l
u
a
t
i
o
nc
o
n
s
i
d
e
r
a
t
i
o
n
s，
"IETF，RFC2
5
0
1，Jan1
9
9
9
.
[
7
]S
.
R
.D紙 R .C制 組eda，組d J.Yan，
“ S
i
m
u
l
a
t
i
o
n
b
a
s
e
dperformancee
v
a
l
u
a
t
i
o
no
f
r
o
u
t
i
n
gp
r
o
t
o
c
o
l
sf
o
rm
o
b
i
l
eadhocn
e
t
w
o
r
k
s，
"MobileNetworksandApplications
(MONET)，Vo
1
.5，No.3 p
p
.
1
7
9
1
8
9，September2
0
0
0
.
ヲ
[
8
]H
.
Y
.
H
s
i
e
h組 dR
.Sivakum
訂，“ P
erformancec
o
m
p
a
r
i
s
o
no
fc
e
l
l
u
a
r姐 dm
u
l
t
i
h
o
pw
i
r
か
l
e
s
sn
e
t
w
o
r
k
s
:A q
u
a
n
t
i
t
a
t
i
v
es
t
u
d
y
，
"P
r
o
c
.ACMSIGMET
RlCS，p
p
.
1
1
3
1
2
2，Boston，
M A，
USA，
J田 l
e2
0
01
.
[
9
]B
.O官 町a，andA
.
P
e
t
r
i
c
k，
“ TheIEEE8
0
2
.
1
1Handboo
k
:A D
esigne
出 C
ompanion，
"
S
t
a
n
d
a
r
d
sI
n
f
o
r
m
a
t
i
o
nNetworkIEEEP
r
e
s
s，
2
0
0
5
.
“B
l
u
e
t
o
o
t
hP
r
o
f
i
l
e
s
:TheD
e
f
i
n
i
t
i
v
eGuide，
"P
r
e
n
t
i
c
eH
a
l
l，2
0
0
2
.
[
1
0
] D.-A.Gratton，
50
三責大学大学院
工学研究科
参考文献
5
1
[
1
1
]J
.
B
r
o
c
h，
D.-A.Maltz，
D.-B.Johnson，
Y.-C.Hu組dJ
.
J
e
t
c
h
e
v
a
“
， A perform姐 ceComs
o
no
fMulti-HopW
i
r
e
l
e
s
sAdHocNetworkRoutingProtoco
1
s
，
"P
r
o
c
.o
ft
h
e
P町 i
ACMjIEEEI
n
t
e
m
a
t
i
o
n
a
lC
o
n
f
e
r
e
n
c
eonMobileComputingandNetworking(
M
o
b
i
p
p
.
8
5
9
7，
October1
9
9
8
.
Com)，
0
0
3
.
[
1
2
] 斉藤匡人，“無線アドホックネットワーク，"2
・
.
P
.
B
h
a
伊 r
a
t，
“ HighlyDyna皿 i
cD
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
dD
i
s
t
a
且.
c
eV
e
c
t
o
rRout[
1
3
] C.P
碍 (
DSDV)f
o
rMobileComputers，
"
P
r
o
c
.ACMSIGCOMM'94，
p
p
.
2
3
4
244，
September
i
1
9
9
4
.
“ OptimizedLinkStateRoutingProtocol，
"IRFC3626，
[
1
4
] T.ClausenandP
.
j
a
c
q
u
e
t，
O
c
t
o
r
b
e
r2
0
0
3
.
[
1
5
] D.Johnson，
Y.-C.HuandD.Maltz“
， TheDynar凶 cSourceRoutingProtocol(DSR)
f
o
rMobileAdHocNetworksf
o
rIPv4，
"RFC-4728，IFTFNetworkWorkingGroup，
2
0
0
7
.
[
1
6
]S
.
R
.D執
C占 .
P
e
r
k
i
n
s，組d E
.
M
.Ro
y
e
r，
“ Performance comp訂 isonoftwo on-
demandr
o
u
t
i
n
gp
r
o
t
o
c
o
l
sf
o
radhocn
e
t
w
o
r
k
s，
"IEEEConferenceonComputerComVo
L
1
， pp.3-12，
2
0
0
0
.
m
u
n
i
c
a
t
i
o
n
s，
[
1
7
]C
.
E
.
P
e
r
k
i
n
s，E.-M.Royer and S
.
R
.Das，
“ Adhoc On-DemandDistanceVector
(AODV)Routing，
"RFC-3561，
IETFNetworkWorkingGroup，
2
0
0
3
.
[
1
8
] AODV P
u
b
l
i
c I
m
p
l
e
m
e
n
t
a
t
i
o
n
s， “
AODV P
u
b
l
i
c I
m
p
l
e
m
e
n
t
a
t
i
o
n
s，
"
h
t
t
p
:
jj
m
o
m
e
n
t
.
c
s
.
u
c
s
b
.
e
d
u
jAODVjaodv.htm#
Im
p
l
e
m
e
n
t
a
t
i
o
n
s
.
[
1
9
]Z
.
J
.
H
蹴，e
ta
l
.，
“ TheZoneRoutingProtocol(ZRP)forAdHocNetworks，
"IETF
J
u
l
y2
0
0
2
.
IntemetD
r
a
f
t，
[
2
0
] Eun
ふ 凪 Jung組 dN
.-H.Vaidya
“
， A PowerControlMACProtocolf
o
rAdHocN
e
t
works，
"Proc.ACMMobiCom'02，
p
p
.
3
6
47，
A
t
l
a
n
t
a
，
USA，
September2
0
0
2
.
，M.Woo，andC
.
S
.Ra
ghavendra
“
， Power-AwareRoutingi
nMobileAdHoc
[
2
1
]S
.
S
i
n
g
h
Networks，
"Proc.MobiCom'98，
p
p
.
1
8
1
1
9
0，
1
9
9
8
.
三重大学大学院
」二学研究科
参考文献
5
2
[
2
2
] CιToh，
“ MaximumBatterγLi島 恥ut也 gtoSupportUbiquitousMobileComp
u
t
i
n
gi
nW
i
r
e
l
e
s
sAdHocNetworks，
"IEEECommunicationsMagazine，
p
p
.
1
3
8
1
4
7，
2001
.
[
2
3
] A.Misra
，
姐dS.Banerjee
“
， MRPC:MaximizingNetworkLifetimef
o
rR
e
l
i
a
b
l
eRout-
"Proc.WCNC'02，
Vo
1
.2，
pp却 0・806，
2
0
0
2
.
i
n
gi
nW
i
r
e
l
e
s
sEnvironments，
[
2
4
] A.Rani組dM.Dave
“
， LoadBalancedRoutingMechanismsf
o
rMobileAdHocN
e
t
works，
"Communication，
NetworkandSystemS
c
i
e
n
c
e
s，
p
p
.
6
2
7
6
3
5，
October2
0
0
9
.
J
.
Y
.
H
a
l
p
e
r
n，
andL
iL
i“
， Gossip
BasedAdHocRouting，
"Proc.IEEE
[
2
5
]Z
.
J
.
H
a
s
s，
INFOCO
乱
1
:
， pp.1707-1716，
June2
0
0
2
.
附 A.RaniandM.Dave，
“ PerformanceEvaluationo
fModi
f
i
.
edAODVf
o
rLoadB
a
l
a
n
c
i
n
g，
"JournalofComputerScience，SciencePublications，pp.863-868，November
2
0
0
7
.
伺 組dM
.Gerla
“
， Dynamicload-awareroutingi
nadhocn
e
t
w
o
r
k
s，
"IEEEI
n
t
'1
[
2
7
]S
.
L
C
o
n
f
e
r
e
n
c
eonCom
皿 u
n
i
c
a
t
i
o
n
s，
Vo
L10，
p
p
.
3
2
0
6
-3
21
O
， 2001.
[
2
8
]V
.
S
a
i
g
a
l，
A
.
K.Nayak，
S
.
K.Pradhan，
andR
.Mall
“
， Loadbalancedroutingi
nm
o
b
i
l
e
"ElsevierComputerCommunications，
Vo
1
.27，
p
p
.
2
9
5
3
0
5，
February
adhocn
e
t
w
o
r
k
s，
2
0
0
4
.
[
2
9
] H.Hassanein，
andA.Zhou
“
， RoutingwithLoadBalancingi
nW
i
r
e
l
e
s
sAdHocN
e
t
works，
"Proc.ACMMSWiM，
Rρme，
I
t
a
l
y
，
p
p
.
8
9
9
6，
2001
.
[
3
0
] J.Hakoda
，
H.UeharaandM.Yokoyama
“
， PerformanceEvaluationofMobileAdHoc
RρutingP
r
o
t
o
c
o
l
sBasedonL
i
出 E
x
p
i
r
a
t
i
o
nTimeandLoado
fNode，
"IEICETr姐s
.
Vo
l
.
J85B
，
No.12，
p
p
.
2
1
0
8
2
1
1
8，
2
0
0
2
.
Commun.，
伊1
]S
.
T
.
山 h
a
s
h
i，J.Hakoda
，H.Uehara叩 d M.Yokoyama
“
， A LoadBalancedRouting
Schemef
o
rM
o
b
i
l
eAdHocNetworks，
"ISITA，
Parma
，
I
t
a
l
y
，
October2
0
0
4
.
三主主大学大学院
工学研究科
参考文献
5
3
[
3
2
]J
.
S
o
n
g，
V.Wong，
姐dV.Leungヲ
“ Load-aw;
訂 eo
n-demandr
o
u
t
i
時 (LAOR)p
r
o
t
o
c
o
l
f
o
rm
o
b
i
l
eadhocn
e
t
w
o
r
k
s，
"Proc.IEEEVehicularTechnologyConference(VTCS
p
r
i
n
g
)，
Vo
1
.3，
p
p
.
1
7
5
3
1
7
5
7，
A
p
r
i
l2
0
0
3
.
andG
.
F
.
R
i
l
e
y
“
， A Workload-BasedAdaptiveLoad-BalancingTechnique
[
3
3
]Y
.
J
.
L
e
e，
f
o
rM
o
b
i
l
eAdHocNetworks，
"IEEECommunicationSociety，
WCNC，
Vo
1
.4，
p
p
.
2
0
0
2
2007，
March2
0
0
5
.
[
3
4
]S
.
J
u
n
g，N.Hundewale組dA
.
Z
e
l
i
k
o
v
s
k
y
，
“ EnergyEfficiencyofLoadBal姐cingin
MANETRoutingP
r
o
t
o
c
o
l
s，
"SNPDjSAWN，
pp.
47
6
483，
May2
0
0
5
.
[
3
5
] Y.-S.Kim，
Y.J
.
C
h
o，
K.Kang
“
，AnEnha即 edLoad-balancingApproachUsingDetour
"WirelessCommunicationsandNetworkingConference，pp.1-5，
i
nAd-hocNetwoeks，
A
p
r
i
l2
0
0
9
.
[
3
6
]J
.
H
.
S
o
n
g，V.-W.-S.WongandV.-C.-M.Leung，
“ E血cienton-demandroutingf
o
r
m
o
b
i
l
eadhocw
i
r
e
l
e
s
sa
c
c
e
s
sn
e
t
w
o
r
k
s，
"IEEEjournalons
e
l
e
c
t
e
dAreasi
nCommun
i
c
a
t
i
o
n
s，
p
p
.
1
3
7
4
-1
3
8
3，
September2
0
0
4
.
[
3
7
] Robert占 .K
油 n，
S
t
e
v
e
n
.
A
.
G
r
o
n
e
m
e
y
e
r，
J
.
B
u
r
c
h
f
i
e
l，
andR.Kunzelman
“
， Advances
i
nP
a
c
k
e
tRadi
oTechnology
ヲ
"Proc.IEEE，
Vo
1
.66，
No.ll，
p
p
.
1
4
6
8
1
4
9
6，
Nov1
9
7
8
.
組d L.Kleinrock，
“ PacketSwitchingi
nRadi
oC
h
a
n
n
e
l
s
:
P
a
r
t t
h
e
[
3
8
]F
.
A
.
T
o
b
a
g
i，
hiddent
e
r
m
i
n
a
lproblemi
nc
a
r
r
i
e
rs
e
n
s
em
u
l
t
i
p
l
←accessmodelsandthebusy-tono
s
o
l
u
t
i
o
n，
"IEEE官組s.Commun.，
Vo
l
.COM-23，
No.12，
p
p
.
1
4
1
7
1
4
3
3，
1
9
7
5
.
[
3
9
]J
.
J
由 民 組d J
心 .T
ornow，
“ The DARPA Packet Radio Network Protocols人
Proc.IEEE，
Vo
1
.75，
No.1，
p
p
.
2
1
3
2，
Jan1
9
8
7
.
alN
e
ti
sh
t
t
p
:
/
/
w
w
w
.
s
c
a
l
a
b
l
令 n
etworks.comj
[
4
0
] NetworkS
i
m
u
l
a
t
o
rQu
三重大学大学院
工学研究科
謝辞
本論文を進めるにあたり，小林英雄教授，森香津夫准教授，内藤克浩助教には
適切な御助言を賜りならびに御指導をしていただき，感謝の意を表します.そし
て，貴重なお時間をさいて本修士論文の査読をしていただきました三重大学大学
院工学研究科電気電子工専攻の川中普晴助教に深く感謝いたします.最後に，常
に完壁な研究設備の環境を整えてくださった山本好弘技官，ならびに通信工学研
究室の院生，学部生に深く感謝致します.
5
4
三重大学大学院
工学研究科