■ 第4回 MANETにおけるさまざまなプロトコル ■

●マルチホップ無線ネットワークの課題

　マルチホップ無線ネットワーク（またはアドホックネットワーク）においては、多くの研究者が、さまざまなテーマについて研究を行なっている。大まかに見ると、2つの大きな流れで構成されているように感じる。

　1つは、転送方式の研究である。現在、インターネットで用いられているプロトコルは、マルチホップ無線ネットワークでそのまま利用することができない。例えば、データを送受信するのに標準的なTCPというプロトコルは、マルチホップ無線ネットワークにはなじまないプロトコルである。マルチホップ無線ネットワークでは、通信障害や通信速度の変化が起こりやすい。その原因は、人が横切っただけなど、電波状況が一時的に悪くなった場合が多い。しかし、TCPは、それを深刻な状態ととらえて通信速度をわざと半分にしてしまったり、それ以降の通信速度をほんの少しずつしか上げていかないという動作をする。この仕組みは、インターネット上では効率よく機能するのだが、マルチホップ無線ネットワークでは逆効果となってしまう。

　もう1つは、ルーティングプロトコルの研究である。今回はこれについて詳しく説明していこう。

●MANETワーキンググループ

　MANET WGを説明する前に、IETFについて知る必要があるので紹介しておこう。

　IETF (Internet Engineering Task Force http://www.ietf.org/ )は、インターネット技術の標準化を推進する団体である。標準化と聞くと非常に重苦しいイメージを抱くかもしれないが、この団体は企業関係者のみの集まりではなく、あくまでインターネット技術の発展を望み、日々研究開発にいそしむ個々人によって成り立っており、基本的にどんな人でも自由に参加することができる。インターネット技術は多岐に渡るが、IETFでは、それぞれの分野に特化したワーキンググループ(WG)を設け、実際の議論などはWG単位で行なわれている。

　MANET WG( http://www.ietf.org/html.charters/manet-charter.html )は、そのWGの1つである。MANET WGでは、MANET(Mobile Ad-hoc Networks)という、移動端末で自律的に構成されるネットワークを実現するルーティングプロトコルについて議論している。これまでに、さまざまなプロトコルが議論されてきたが、現時点で、Internet Draftとして提案されている方式は以下の通りである。

・Ad Hoc On Demand Distance Vector Algorithm (AODV)
・Dynamic Source Routing Protocol (DSR)
・Optimized Link State Routing Protocol (OLSR)
・Topology Broadcast based on Reverse-Path Forwarding Routing Protocol (TBRPF)
・Landmark Routing Protocol (LANMAR)
・Fisheye State Routing Protocol (FSR)
・Zone Routing Protocol (ZRP)
・Interzone Routing Protocol (IERP)
・Intrazone Routing Protocol (IARP)
・The Bordercast Resolution Protocol (BRP)

　このすべてについて触れていくことは難しいが、できるだけ多くのルーティングプロトコルについて細かく解説をしていきたいと考えている。

●ルーティング

　ネットワークが「物理的に」つながっていても、それだけではデータは送り届けることはできない。このことをよく理解するために、ネットワークを道路に置き換えて考えてみよう。

　例えば、東京都庁から東京タワーまで行くには、どうすればよいだろうか。日本には、数え切れないほどの名前のついた道が縦横無尽に走っている。もちろん、都庁から東京タワーに至る道も、たくさん存在する。しかしあなたは、その中で東京タワーに至る道を必ず1つ選び、その道を進まなければならない。その経路はどうやって知るのだろう？　幸い、道路に関しては「道路地図」がある。書店で購入して、よさそうな経路を決定すればいい。

　しかし、コンピューターにより構成されるネットワークでは、そう簡単にはいかない。まず、「道路地図」にあたるものを作るだけでも大変である。インターネットは、全世界につながる巨大なネットワークだが、そこにつながっているすべてのコンピューターの位置関係や全経路を把握することなど、到底できたものではない。

　再び道路の例に戻ってみよう。道路を走っていると、大きな交差点には案内標識があり、大まかに目的地を設定していれば、進むべき方向がわかるようになっている。すなわち、最初から全経路を覚えてその道をたどるのではなく、案内標識に従って逐次進んでいけばいいのである。

　実はコンピューターネットワークでは、このような案内標識のようなものを使って、絶え間なく送られてくるデータ（パケット）の行き先を振り分けている。その案内標識を「経路表」とか、「ルーティングテーブル」と呼ぶ。経路表は、各ノードに記録されており、宛先とその宛先へパケットを届けるために送り出すべき転送先の組が表になったものである。パケットが自分のノードに届いたとき、それが自分宛なら受け取るが、そうでなければ経路表を見て、宛先に適したノードへ転送していく。これをルーティングと呼ぶ。

図1 経路図とルーティングの例

　具体的な例を図1で説明しよう。ここでは、ノードAとE間で通信を行なおうとしている。まずは、ノードAからどのようにパケットが送り届けられるか見てみよう。ノードAの経路表には、「宛先EはDへ送れ」と書いてあるので、パケットをノードDへ送る。ノードDの経路表には、「宛先EはEへ送れ」と書いてあるので、パケットをノードEへ送る。ノードEでは宛先が自分自身なので、そのパケットを受け取る。こうして、無事にノードEにパケットが送り届けられる。

　戻りの経路も同じだ。ただし、来た道を戻らないこともあることに注意しよう。ノードEの経路表には、「宛先AはBへ送れ」と書いてあるので、パケットをノードBへ送る。ノードBでは、経路表には「宛先AはAへ送れ」と書いてあるので、パケットをノードAへ送る。ノードAでは、自分への宛先のパケットが届いたので、それを受け取る。このようにして、無事にノードAとノードE間で、データの送受信ができるわけである。

●ルーティングプロトコル

　　ところで、経路表はどのようにして作られているのだろうか。インターネットでは、人間が手入力で設定することもあるのだが、ワイヤレスP2Pネットワークでは、その手法はとれない。なぜならば、まったく知らない人が所持するノード(端末)同士が連携して構成されるため、「ネットワークの持ち主」がいないのだ。しかも、ノードは勝手に移動しているのだから、経路表は絶えず変化しなければならない。

　そこで、経路表を自動的に設定する仕組みが必要となる。それが「ルーティングプロトコル」の役目である。マルチホップ無線ネットワークでは、ノードが頻繁に移動しており、リンクはつながったり切れたりを繰り返している。また、突然ノードの電源が切られることもある。しかもノードの移動特性、ノードの密集の度合いなど、さまざまな環境の違いによって、最適のルーティングプロトコルは異なってくる。

　IETFのMANET WGでも、さまざまなルーティングプロトコルが考えられており、それぞれに長所短所があるのだが、そのほとんどは「Reactive型」か「Proactive型」のどちらかに属することに注目したい。Reactive型とProactive型の動作イメージを図2と図3にそれぞれ示す。なお、ノード間をつなぐ線は、便宜上、電波の届く関係を表わしいる。

図2 Reactive型プロトコルの動作イメージ

図3 Proactive型プロトコルの動作イメージ

　3つのノードは、電源が入った直後には、電波が届く範囲内にどんなノードがいるのかを知らない。もちろん、経路表も作成されていない。それでは、どのように経路表が作られていくのかを説明していこう。

●Reactive型ルーティングプロトコル

　「AODV」「DSR」「IERP」というルーティングプロトコルは、Reactive型に属する。それぞれのノードに電源が入っただけでは、このまま何も起こらない。当然、経路表もこのまま放っておく限り、いつまでたっても作られない(図2上段)。実際に通信の要求を出すと、ルーティングプロトコルが動作し、周りのノードの存在を電波を出して確かめ、経路表を作成していく(図2下段)。こうして、ようやく通信ができるようになる。

　経路表が作られるのは、通信の要求が起こってからなので、実際に通信が始まるまでには少し時間差が生じる。なぜ、このような面倒な仕組みになっているのだろうか。

　マルチホップ無線ネットワークでは、ほとんどのノードが電池で駆動している。ゆえに、むやみやたらに電波を発信すると、すぐに電池がなくなってしまう。また、常に各ノードは移動しているので、数分前に作った経路表は、ほとんど意味がないことが多い。

　そこで、通信が起こる直前に経路表を作るのだ。また、通信を行なわない時はまったく電波の発信が行なわれないため、駆動時間の長時間化にも一役買っている。Reactive型プロトコルは、通信を要求してから、実際に通信可能になるまでの時間が長くなっても構わないようなネットワークに使われる。

●Proactive型ルーティングプロトコル

　一方、Proactive型のルーティングプロトコルは、あらかじめ経路表を作成しておくプロトコルである。したがって、通信の要求が起こると、すぐに通信を開始できる(図3)。「OLSR」「TBRPF」「LANMAR」「FSR」「IARP」と呼ばれるプロトコルがProactive型に属する。

　あらかじめ経路表を作成するためには、常にパケットを送出し、周辺に存在するノードの確認を行ない、経路表作成のための制御情報のやり取りが必要になる。場合によっては、無駄な電波発信が頻繁に起こる。

　Proactive型で重要となるのは、どのぐらいの周期で経路表の更新を行なうのか、また、どのぐらいの(地理的な)範囲までをカバーするように経路表を作るのかを決めることだ。もちろん、常に最新で、できるだけ遠くのノードにまで通信可能であるほうがいいが、そうすると電波の発信数が多くなり、電力の消費は激しい。実際には、利用パターンをシミュレーションして調整していくことになる。Proactive型は、通信が頻繁に行なわれるネットワークに有効だ。

●そのほかの方式

　これら、2つの方式に当てはまらないプロトコルも存在する。Reactive型とProactive型を組み合わせたハイブリッド方式や、多数のノードと同時に通信を行なうネットワークに適したプロトコルなどが存在する。

　ハイブリッド方式とは、自分の近くに存在するノードに関してはProactive型で経路表を作成し、遠方に存在するノードとの通信を行なう場合には、Reactive型のルーティングプロトコルを用いて、経路を作成する方式である。

●おわりに

　マルチホップ無線ネットワークにおけるルーティングプロトコルは、非常に複雑なものだ。ノードは勝手に動くし、それぞれのノードで利用できる資源も制約がある。さまざまなルーティングプロトコルが考案されているが、必ず欠点が存在する。オールマイティなプロトコルはなかなか構築することはできないのである。

　次回以降は、ワイヤレスとP2Pに関係する少し気になるニュースなども交えながら、いくつかのプロトコルに焦点を当てて詳細な解説をしていきたい

　

■筆者紹介■ 小出俊夫 http://homepage1.nifty.com/toshio-k/ 　常に他人と違うことをすることに喜びを覚える知的好奇心旺盛な人間。他に雑誌連載を1つ手がけ、プログラミングの解説書は5冊。実は博士課程の大学院生で、メーカーの研究所に入りたがっている。求むオファー。

(2003/1/29)

[Reported by 小出俊夫]