アドホックネットワークの ルーティングプロトコル

Presentation on theme: "アドホックネットワークの ルーティングプロトコル"— Presentation transcript:

1 アドホックネットワークの ルーティングプロトコル
高橋 孝輔

2 アドホック向けルーティングプロトコル マルチホップ無線ネットワークでの経路表を自動的に設定する仕組みのこと
IETF（Internet Engineering Task Force）のワーキンググループであるMANET（Mobile Ad-hoc Networks）で標準化作業が行われている プロアクティブ方式：経路表がわかっている リアクティブ方式：通信時に経路作成 ハイブリッド方式：近くのノードにはプロアクティブ型 　遠くのものにはリアクティブ型

3 プロアクティブ型 あらかじめ経路表を作成しておくプロトコル ⇒通信の要求が起こるとすぐに通信可能
OLSR、TBRPFなどのプロトコルがこの方式にあたる。 経路表作成のためには -常にパケットを送出し、周辺ノードの確認 ⇒経路表作成の制御情報のやり取りが必要 (場合によっては無駄な電波発信が頻繁におこる) 経路表更新の周期と経路表をどのくらいの地理的範囲をカバーするように作るか ⇒最新かつ遠くまで通信が望ましいが、電力消費が増加 通信が頻繁に行われるネットワークに有効

4 OLSR (Optimized Link State Routing)
マルチポイントリレー(MPR)集合(必要最低限のノードだけがパケットを中継する仕組み)と呼ばれる仕組みを利用して フラッディング(同一パケットを1つのノードからすべてのノードへ配信すること)を効率化 各ノードがどのノードのMPRとなっているのかを知っており、そのノードからのパケットだけを中継する

5 OLSR MPRの選択方法の例 A S B E D C J F I G H
ノードSが近隣とのHELLOメッセージ交換により、2ホップ先までの経路情報を収集 1ホップで接続するノードを集合N、2ホップで接続するノードを集合N2 Nの中で唯一のN2を持つノードを選択：B→E→J 最も多くの集合N2を持っているNを選択：C→F,G,H,I N2がなくなるまで繰り返すことでMPR集合が選択される 上記の図ではBとCがSのMPR集合

6 OLSR 各ノードが送信するメッセージには自分のMPR集合のリストも含まれる →各ノードは自分がどの近隣ノードのMPRであるかを知ることができる MPRを利用したフラッディングは経路表の作成に利用される -MPRとして選択されたノードは、自分がどのノードのMPRであるかというリストをMPRに選択されたノードにフラッディング -すべてのノードは1つ以上のMPR集合を選択 →あるノードが選択しているMPR集合がわかる →そのノードへの経路の1つ手前のノードがわかる →1つ手前のノードの経路の1つ手前のノードがわかる →その手前のノードの経路･･･ →各ノードはネットワーク全体のトポロジ構成を作成することが可能

7 TBRPF (Topology Broadcast Based on Reverse - Path Forwarding)
差分情報を積極的に用いるのが特徴 追加・削除などの必要最低限の情報を利用 →メッセージのサイズの縮小 →比較的短い期間に周期的にルーティング情報を送受信可能 ⇒ノードの移動などによる急激なトポロジ変化に比較的強い

8 リアクティブ型 AODV、DSRなどのプロトコルがこの方式にあたる
通信の要求が行われたときルーティングプロトコルが動作 ⇒経路表が作られるのは通信の要求が起こってから 何故通信要求が行われてから経路表が作られるのか -電波の発信を少なくして電力消費を減少 -ノードの移動で前の経路表がほとんど意味がなくなる 通信を要求してから実際に通信可能になるまでの時間が長くなっても構わないようなネットワークに利用

9 DSR (Dynamic Source Routing)
送信ノードがあて先ノードまでの経路をすべてパケットヘッダに含んで送るソースルーティング方式 通信を行ったり周りから経路情報を受け取ったりするたびにルートキャッシュとして蓄えている ⇒頻繁に使うノードに速やかな通信 ノード間ホップ数は数ホップ単位を想定

10 DSR 経路探索(RReq) 経路応答(RRep) 経路エラー(RErr) S RRep [S,B,C,D] S S RReq [S] E
cache[S,B,C,D] cache[S,B,C] cache[S,B,] S RRep [S,B,C,D] S S RReq [S] E B cache[B,C,D] cache[B,C,] A RReq [S,B] E B E B A A F F F C C C cache[C,D] RReq [S,B,C] 切断 D D D 送信ノードへのパケットに自分のアドレスを付加させてフラッディングを行うことを繰り返して経路探索を行う パケットが宛先ノードに到着したら送信ノードへ応答を返す データ中継の確認が出来ない場合、経路エラーを送信ノードに向けて送信 中継するノードは、経路エラーが起こったノード間のリンクを含むすべての経路情報を経路表から消去

11 AODV (Ad - hoc On Demand Vector)
各ノードが次にどのノードにパケットを送れば良いかという経路表を保持している ⇒各ノードは次の中継先だけ知っているが、その後どのようにパケットが届けられるかは関知はしない

12 AODV 経路探索(RReq) 経路応答(RRep) 経路エラー(RErr) S S S E B A E B E B A A F F F C
切断 D D D cache[S,B,C,D] cache[S,B,C] cache[S,B,] Rreqにより作成される 宛先Sへの経路情報 Rreqにより作成される 宛先Dへの経路情報 Rreqパケットを中継するノードは、パケットを中継してきたノードをS宛の経路の次ホップノードとして記録 RRepを中継するノードはD宛の経路の次ホップノードを知ることができる

13 AODV 経路エラー(RErr) S B E A C F 切断 D 各ノードはRRep受信時に前後のノードをprecursorリストに追加
データ中継の確認が出来ない場合、経路エラーを送信ノードに向けて送信 無効となったノードへのリンクを次ホップとしている宛先ノードへの経路をすべて無効にする必要がある -このとき、precursorリストにはその経路を利用する近隣ノードが記録されており、それらのノードは無効となった宛先に対する経路を保持している確率が高いため、precursorリストの全てのノードにREｒｒを送信 宛先：次：PL 　D　：B ：＿ 宛先：次：PL 　S　：S ：C 　D　：C ：S,A S 宛先：次：PL 　E　：E ：B 　D　：B ：E 宛先：次：PL 　S　：B ：D 　D　：D ：B B E A C F 切断 D 宛先：次：PL 　D　：A ：＿

14 MOTEのルーティング Any-to-Base -各センサノードから基地局へデータをマルチホップ伝送していくためのルーティング（その逆も可） ・各センサノードが近隣ノードの送受信の品位を測定し、算出した基地局までのノード間の通信コストが最小となるようなマルチホップの伝送先(親ノード)を選択していく コスト:40 コスト:10 コスト:20 コスト:0 コスト:30

15 参考文献 センサネットワーク技術　ユビキタス情報環境の構築に向けて 2005年5月20日 第1版 1刷発行 安藤 繁　田村 陽介 戸辺 義人 南 正輝 ユビキタスコンピューティングと応用　 -社会や家庭に広がる情報技術- 2008年9月30日 初版 1刷発行 瀧 寛和　堀 聡 P2Pとワイヤレスの交差点 小出 俊夫