アドホックルーティングにおける 省電力フラッディング手法の提案

Presentation on theme: "アドホックルーティングにおける 省電力フラッディング手法の提案"— Presentation transcript:

1 アドホックルーティングにおける 省電力フラッディング手法の提案
アドホックルーティングにおける 　省電力フラッディング手法の提案 神奈川大学大学院　　有川　隼　　松田　充敏　　能登　正人

2 序論 アドホックネットワーク IETFのMANET WG 自律無線端末群により構成される 通信インフラが存在しない 1994年設立
プロトコルの標準化 いくつかがRFC化

3 プロトコルの分類 Reactive型（On Demand型） 通信要求があってから，経路を確保する すぐにデータ通信を行うことができない
代表例：DSR，AODV Proactive型（Table Driven型) 一定時間間隔でフラッディングを行っている すぐにデータ通信を行うことができる 代表例:OLSR，TBRPF

4 プロトコルに共通 Route Discovery ①Route Request ②Route Reply
①Route Request:　 DEST (Destination node)を 　　 発見する為の動作 ②Route Reply: 　DESTからSRC (Source node)へ 　　　　　　　　　　　受信できる事を通知

5 Route Requestにおける 無駄なフラッディング
A A A A A A A A A A Hop数の制限をする事も可能だが 狭い範囲でしか通信できない A A A A A S A A D ＲＲＥＰがすぐに届いたにも関わらず、周辺でＲＲＥＰのブロードキャストが 次々に行われてしまう。

6 本研究では 無駄なフラッディングをなくす為の フラッディング手法を提案し， 実装する事によりシミュレーション実験を行った．
まず基本的なプロトコルとしてDSRを 取り上げ，本手法が有用であるか どうかを確かめた． 以下，DSRと本手法について述べる

7 DSRのRREQにおけるキャッシュ D B Destination C A S E Source Cache [S,A,B,C,D]
Cache [S,A,B,C,E]

8 中継ノードAがDに繋がるキャッシュを所持していた 場合，Dに変わってRREPを返すことができる．
B Destination C A Cache [A,B,C,D] S RREP E Source 　　中継ノードAがDに繋がるキャッシュを所持していた 場合，Dに変わってRREPを返すことができる．

9 Route Error Packets 現在SからDまでのルートが今現在確立されている C RERR B D Destination A E
Cache [B,C,D] B D Destination A E S Source BはCに送ろうとして，Cがいない事に気づく． まずBは，キャッシュリストから該当キャッシュを削除する． Route Error Packet 生成し，それを返す． 返す相手は，送信要求をしたノード（S)である．

10 提案フラッディング手法 以上のような無駄を防ぐために、送信ノードから （m,n,l）ホップ先の隣接ノードは、ＲＲＥＱを受け取った後、 すぐに周辺ノードにブロードキャストせず、パケットを所持する。 所持して、一定時間ｔstopを過ぎるとブロードキャストを再開する。 A A CP(Closing Packets)： 経路が見つかったことを知らせる 為に、送信元が送るパケット A A A A A A A A パケットを溜めること によって，余計に時間が 掛かってしまう[1] 経過時間よりもノード負荷を 下げることを優先 A A A A CP S A A D RREP

11 パケットを溜めるアルゴリズム 時間 10 20 1hop先の待機時間:2 2hop先の待機時間:4 RREPの送信時間:3 D
10 20 1hop先の待機時間:2 2hop先の待機時間:4 RREPの送信時間:3 D CPのフラッディング時間:3 S RREQ RREP CP

12 シミュレーション 正方平面上をランダムにノードが移動する Case1 Case2 モデル長 150×150 100×100 ノード数
2～80 2～200 通信可能距離 20 移動距離 5 試行回数 　100フェーズ×1000 100フェーズ×1000 Packetを溜めるホップ数：提案(i) 1hop先 　提案(ii)1hopと2hop先 　提案(iii)1hopと2hopと3hop先

13 パケットの送受信について W（送信にかかる電力消費） 1 Wall （ネットワーク全体の電力消費） W ×受信回数 T（一回の送受信時間）
評価パラメータ W（送信にかかる電力消費） 1 Wall （ネットワーク全体の電力消費） W ×受信回数 T（一回の送受信時間） Tall （到達時間） DESTに届くまでの時間 一回のデータ送信に1packet送信し， その時にかかる受信電力消費を１とする。 Wall＝1*3=3 Tall＝1*2=2

14 結果（総電力消費量(Case1)） ①ノード数が増加すると指数的に電力消費量が増加する ②しかし提案と既存との差に決定的な違いは現れない

15 結果(総電力消費量(Case2)) 12.0%減 39.0%減 50.0%減 密なネットワークでは，提案手法により大幅に負荷を軽減できた

16 結果(DEST到達時間(Case2)) n=40~45付近で最大値をむかえ徐々に減衰 n=40まではDESTまでのホップ数が少ない
2.4倍 n=44 1.62倍 1.13倍 n=40~45付近で最大値をむかえ徐々に減衰 n=40まではDESTまでのホップ数が少ない n=45からは遠回りのルートが少なくなってくる

17 おわりに 本研究では，既存のDSRに提案手法を組み込む事によって，負荷の軽減を行った． その結果，手法によっては負荷を半減させる 程の効果が現れた． 今後は，負荷と時間双方を考慮したフラッディング手法を構想することが考えられる．