アドホックルーティングにおける省電力フラッディング手法の提案神奈川大学大学院有川隼松田充敏能登正人序論 • アドホックネットワーク – 自律無線端末群により構成される – 通信インフラが存在しない • IETFのMANET WG – 1994年設立 – プロトコルの標準化 – いくつかがRFC化プロトコルの分類 Reactive型（On Demand型）  通信要求があってから，経路を確保する  すぐにデータ通信を行うことができない  代表例：DSR，AODV  Proactive型（Table Driven型)  一定時間間隔でフラッディングを行っている  すぐにデータ通信を行うことができる  代表例:OLSR，TBRPF  プロトコルに共通 • Route Discovery ①Route Request ②Route Reply ①Route Request: DEST (Destination node)を発見する為の動作 ②Route Reply: DESTからSRC (Source node)へ受信できる事を通知 Route Requestにおける無駄なフラッディング A A A A A A A A A A A A A A A S A A Hop数の制限をする事も可能だが狭い範囲でしか通信できない D ＲＲＥＰがすぐに届いたにも関わらず、周辺でＲＲＥＰのブロードキャストが次々に行われてしまう。本研究では • 無駄なフラッディングをなくす為のフラッディング手法を提案し，実装する事によりシミュレーション実験を行った． • まず基本的なプロトコルとしてDSRを取り上げ，本手法が有用であるかどうかを確かめた．以下，DSRと本手法について述べる DSRのRREQにおけるキャッシュ Cache [S,A,B,C,D] Cache [S,A,B] B Cache [S,A,B,C] D Destination C A S Source Cache [S,A] E Cache [S,A,B,C,E] キャッシュを用いたRREP D B Destination C A Cache [A,B,C,D] S Source RREP E 中継ノードAがDに繋がるキャッシュを所持していた場合，Dに変わってRREPを返すことができる． Route Error Packets 現在SからDまでのルートが今現在確立されている C Cache [B,C,D] RERR B D Destination A E S Source BはCに送ろうとして，Cがいない事に気づく．まずBは，キャッシュリストから該当キャッシュを削除する． Route Error Packet 生成し，それを返す．返す相手は，送信要求をしたノード（S)である．提案フラッディング手法 • • 以上のような無駄を防ぐために、送信ノードから（m,n,l）ホップ先の隣接ノードは、ＲＲＥＱを受け取った後、すぐに周辺ノードにブロードキャストせず、パケットを所持する。所持して、一定時間ｔstopを過ぎるとブロードキャストを再開する。 A A A A A A A A CP(Closing Packets)：経路が見つかったことを知らせる為に、送信元が送るパケット A A A A A CP A S RREP A A D パケットを溜めることによって，余計に時間が掛かってしまう[1] 経過時間よりもノード負荷を下げることを優先 0 パケットを溜めるアルゴリズム時間 10 20 1hop先の待機時間:2 2hop先の待機時間:4 RREPの送信時間:3 D CPのフラッディング時間:3 S RREQ RREP CP シミュレーション • 正方平面上をランダムにノードが移動するモデル長ノード数通信可能距離移動距離試行回数 Case1 150×150 2～80 20 5 100フェーズ×1000 Case2 100×100 2～200 20 5 100フェーズ×1000 Packetを溜めるホップ数：提案(i) 1hop先提案(ii)1hopと2hop先提案(iii)1hopと2hopと3hop先パケットの送受信について • 評価パラメータ W（送信にかかる電力消費） Wall （ネットワーク全体の電力消費） T（一回の送受信時間） Tall （到達時間） 1 W ×受信回数 1 DESTに届くまでの時間一回のデータ送信に1packet送信し，その時にかかる受信電力消費を１とする。 Wall＝1*3=3 Tall＝1*2=2 結果（総電力消費量(Case1)） ①ノード数が増加すると指数的に電力消費量が増加する ②しかし提案と既存との差に決定的な違いは現れない結果(総電力消費量(Case2)) 12.0%減 39.0%減 50.0%減密なネットワークでは，提案手法により大幅に負荷を軽減できた結果(DEST到達時間(Case2)) 2.4倍 1.62倍 1.13倍 n=44 n=40~45付近で最大値をむかえ徐々に減衰 n=40まではDESTまでのホップ数が少ない n=45からは遠回りのルートが少なくなってくるおわりに • 本研究では，既存のDSRに提案手法を組み込む事によって，負荷の軽減を行った．その結果，手法によっては負荷を半減させる程の効果が現れた． • 今後は，負荷と時間双方を考慮したフラッディング手法を構想することが考えられる．