OLSR 制御パケットの削減法アドホックネットワークにおける

(1)

2007 年度修士論文

アドホックネットワークにおける

OLSR 制御パケットの削減法

提出日： 2008 年 2 月 4 日

指導：後藤滋樹教授

早稲田大学大学院理工学研究科情報・ネットワーク専攻学籍番号： 3606U051-9

鈴木幹也

(2)

図一覧

2.1 マルチホップ通信 . . . 7

3.1 単純なフラッディングとMPR集合を用いたフラッディングの比較 . . . 11

3.2 OLSRパケットフォーマット . . . 13

3.3 OLSR HELLO メッセージフォーマット . . . 15

3.4 OLSR TC メッセージフォーマット . . . 17

3.5 OLSR MID メッセージフォーマット . . . 17

3.6 OLSR HNA メッセージフォーマット . . . 18

4.1 状況変化と対応処理 . . . 23

5.1 拡散的な移動. . . 26

5.2 集合的な移動. . . 26

5.3 ネットワーク範囲とping到達率 . . . 28

5.4 ネットワーク範囲とping応答時間 . . . 28

5.5 ネットワーク範囲と制御パケット量. . . 29

5.6 ノード数とping到達率 . . . 30

5.7 ノード数とping応答時間 . . . 30

5.8 ノード数と制御パケット量 . . . 31

5.9 拡散的な移動の移動速度とping到達率 . . . 32

5.10 拡散的な移動の移動速度とping応答時間. . . 32

5.11 拡散的な移動の移動速度と制御パケット量 . . . 33

5.12 集合的な移動の移動速度とping到達率 . . . 34

5.13 集合的な移動の移動速度とping応答時間. . . 34

5.14 集合的な移動の移動速度と制御パケット量 . . . 35

5.15 ノードの移動速度とping到達率 . . . 36

5.16 ノードの移動速度とping応答時間 . . . 36

5.17 ノードの移動速度と制御パケット量. . . 37

(5)

表一覧

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

2.2 プロアクティブ型の代表的なプロトコルと適するネットワークの条件 . . . 9

2.3 リアクティブ型の代表的なプロトコルと適するネットワークの条件 . . . 10

3.1 OLSRにおけるWillingness . . . 12

3.2 リンクタイプ. . . 16

3.3 近隣タイプ . . . 16

5.1 シミュレータのパラメータ設定 . . . 27

5.2 ネットワーク範囲と制御パケット削減率 . . . 29

5.3 ノード数と制御パケット削減率 . . . 31

5.4 拡散的な移動の速度と制御パケット削減率 . . . 33

5.5 集合的な移動の速度と制御パケット削減率 . . . 35

5.6 移動速度と制御パケット削減率 . . . 37

(6)

第 1 章序論

1.1 研究の背景

無線通信技術の発展と、ノートPCや携帯電話のようなモバイルノードの普及により、無線ノード同士が即席で柔軟にネットワークを構築する、アドホックネットワークと呼ばれる技術が注目されるようになってきた。アドホックネットワークとは、無線ノード同士が通信する際に、無線の基地局などの既存のインフラストラクチャに依存せずに通信を行うことができる技術である。

さらにそれぞれのノードが中継機能を持つことによって、より柔軟にネットワークを構築することを可能にしている。アドホックネットワークはインフラストラクチャに依存しないため、比較的低コストで迅速にネットワークを構築できるという特徴がある。この特徴を活かして、会議中での資料配付や、車両同士で情報をやりとりする車車間通信、センサー同士が情報をやり取りするセンサーネットワークなどの日常的な状況での利用や、災害時にインフラストラクチャが使用不可能になってしまった場合の、即席の通信手段としての利用が期待されている。また、身の回りの様々なものにCPUや無線インターフェースを搭載し、それらがお互いに情報通信を行うユビキタスネットワークにおいても、この柔軟なアドホックネットワークの技術は有効であると考えられている。

しかし、アドホックネットワークは本来、軍事目的として考え出された技術であり、実際に一般的な場面で利用するためにはまだまだ解決しなければならない問題が多く残されているのが実状である。各ノードが無線で通信するため、自由に動き回ることができ、そのためネットワークのトポロジーが頻繁に変化してしまう。また、有線ネットワークにくらべ通信帯域が制限されていたり、ノードの多くはバッテリーによって駆動しているため、電力にも気を使わなければいけない。さらにはインフラストラクチャを利用しなくてもネットワークを構築できるため、今までのインターネットで用いられていた技術では不十分な場合もある。このように、アドホックネットワークには様々な課題が残されている。

(7)

第 1 章序論

1.2 研究の目的

第 1.1節でも述べたように、アドホックネットワークは無線ノード同士が中継機能を持ち、自立分散的にネットワークを形成する。これを可能とするために、アドホックネットワーク特有のプロトコルが必要になる。また、ルータのように経路制御を集中的に管理するノードの存在が保証されないため、ルーティングのために多くの制御パケットが必要になる。その一方で、無線を用いて通信を行うため有線に比べて帯域が制限されてしまい、制御パケットが通信へ与える影響が大きくなる。制御パケットが多くなれば通常の通信パケットと衝突する可能性が高まり、結果的に通信効率を低下させてしまう。さらに、一般的にアドホックネットワークを構成するノードは移動体を主としているため、制御パケットが多くなるほどバッテリの消費も大きくなり、ネットワークの利用性が低下してしまう。そこで、本論文ではネットワークの状態に応じて動的に制御パケットを調整する方法を提案して、ネットワーク中を流れる制御パケットを削減することを提案する。また、様々な状態のネットワークにおける提案手法の有効性を検証する。

1.3 本論文の構成

本論文は以下の章により構成される。

第1章序論

本研究の概要について述べる。

第2章アドホックネットワーク

アドホックネットワークについて解説する。

第3章 OLSR (Optimized Link State Routing)についてルーティングプロトコルOLSRについて解説する。

第4章提案手法

動的な制御パケット削減手法について解説する。

第5章実証実験

提案手法をシミュレーションによって検証する。

第6章結論

本論文の結論を述べるとともに、本論文において残された問題点を今後の課題として提起する。

(8)

第 2 章

アドホックネットワーク

2.1 アドホックネットワークの概要

アドホックネットワークとは、無線LANで広く使われているアクセスポイントを必要とせず、

無線通信機能を備えたノードのみで構成されるネットワークである。そのノードは、その無線範囲内のノードはもちろん、無線範囲外のノードとも通信することが出来る。無線範囲外のノードと通信する場合には、図 2.1 に示すように中継ノードによって中継される。これをマルチホップ通信という。

図 2.1: マルチホップ通信

アドホックネットワークにおける各ノードは一般的に移動体であるため、頻繁にトポロジーの変化が起こる。アドホックネットワークは自己編成機能を持ち、適応性を備えているネットワークであり、形成されたネットワークが管理者を必要とせず、勝手に違った形のネットワークになり得る自立分散型のネットワークである。このため、トポロジーの変化が起こると各ノードが協力して動的にネットワークを構築することができる。

(9)

第 2 章アドホックネットワーク

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

第 2.1節で述べたように、アドホックネットワークにおいて各ノードがその無線通信範囲外のノードと通信する場合には、中間のノードが中継する。この中継機能を持たせる為にはアドホックネットワーク特有のルーティングプロトコルが必要で、現在でも様々なプロトコルが開発されている。しかし、すべての場面に適するプロトコルはいまだに開発されておらず、今後もこのルーティングプロトコルの開発は大きな課題である。

これまでに開発されたルーティングプロトコルは、表 2.1 に示すように3つの型に分類することができる。これらのプロトコルはいずれもすべてのノードが自立分散的に動作することを想定しており、集中管理を行うノードを必要としない。また、それぞれの型ごとに特徴があり、その特徴が活かせる場面ごとに使い分けられる。

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

分類プロトコルの例

プロアクティブ型 OLSR, TBRPF, DSDV, MMRP リアクティブ型 DSR, AODV, TORA, ABR, DYMO ハイブリッド型 ZRP

2.2.1 プロアクティブ型

プロアクティブ型のルーティングプロトコルは、ネットワーク上の各ノードから他のすべてのノードへの、矛盾のない最新のルーティング情報を維持しようとする。そのようなプロトコルでは、各ノードはルーティング情報を格納するためのテーブルを1つ以上持つ。そして、ネットワークトポロジーの変化に反応してネットワーク全体に経路の更新情報を伝送する。こうすると、通信に先だって周囲のネットワークの状態を確認し把握することができる。それぞれのルーティングプロトコル間の違いは、ルーティングに関連した必要なテーブル数と、ネットワークの構造にどのような変化があったかをブロードキャストする方式の違いである。プロアクティブ型のルーティングプロトコルの特徴は、

• 通信を行う際に遅延が発生しない

• データの非通信時にも制御パケットが流れる

• 通信頻度の高いネットワークに適する

• リアクティブ型のプロトコルに比べて消費電力が大きい

(10)

といったことが挙げられる。これらの特徴から考えてプロアクティブ型のルーティングプロトコルではトポロジーの変更頻度に応じて更新間隔を調整する必要がある。更新間隔が長すぎると経路情報が古くなり、短すぎるとそれだけオーバーヘッドが大きくなってしまう。ノードが移動するようなネットワークにおいては場合によっては非常に効率が悪くなってしまうのがプロアクティブ型のルーティングプロトコルの特徴である。よって、いかに効率良く更新情報を伝達するかが重要である。

代表的なプロアクティブ型のルーティングプロトコルと、それぞれに適したネットワークの条件を挙げると表 2.2 のようになる。

表 2.2: プロアクティブ型の代表的なプロトコルと適するネットワークの条件プロトコル名適するネットワークの条件

OLSR ネットワーク規模が大きく、ノードの密度が高い環境で高い性能

TBRPF 通信量が多いネットワークで高い性能

2.2.2 リアクティブ型

リアクティブ型のルーティングプロトコルは、プロアクティブ型とは違い、送信元始動によるいわゆるオンデマンド型のプロトコルである。オンデマンド型というのは、送信元のノードが要求した時にのみ経路を作成するということである。あるノードにおいて宛先ノードへの経路が必要になった時に、ネットワーク内で経路探索プロセスを始動する。このプロセスは、経路が見つかるか、利用可能なすべての経路パターンを試し終えると終了する。いったん経路が発見され、

確立されると、宛先へのアクセスが不可能になるか経路が不必要になるまでは、何らかの手段によってその経路が維持される。リアクティブ型のルーティングプロトコルの特徴は、

• 通信時に、経路を決定するまでの遅延が発生する

• データの非通信時には制御メッセージが流れない

• ノードの移動が頻繁なネットワークに適するという項目が挙げられる。

代表的なリアクティブ型のルーティングプロトコルとそれぞれに適したネットワークの条件を挙げると表 2.3 のようになる。

(11)

表 2.3: リアクティブ型の代表的なプロトコルと適するネットワークの条件プロトコル名適するネットワークの条件

DSR ノード数、通信量、移動が少ない環境で高い性能 AODV ノード数、通信量、移動が多い環境で高い性能

2.2.3 ハイブリッド型

ハイブリッド型のルーティングプロトコルは、プロアクティブ型のルーティングプロトコルとリアクティブ型のルーティングプロトコルの両方の長所を取り入れた複合プロトコルである。ネットワーク内を複数のゾーンと呼ばれるエリアに分割し、ゾーン内ではプロアクティブ型のプロトコルを使用し、定期的な経路情報の更新はゾーン内のノードについてのみ行い、宛先ノードが送信元のゾーン外にある場合はリアクティブ型のプロトコルを用いて経路を構築する。両方の特徴を生かすことができるが、ノードが密集するような場合においてはゾーン内の管理すべきノードが多くなってしまいうために、逆にトポロジー管理が難しくなってしまうという問題がある。代表的なプロトコルとしてはZRPが挙げられる。

(12)

第 3 章

OLSR による経路制御

この章では本研究において使用しているルーティングプロトコルOLSRについて述べる。

3.1 OLSR の概要

OLSR (Optimized Link State Routing)はRFC3626で提案されているプロアクティブ型のルーティングプロトコルである。その基本的な特徴は第 2.2.1節で示した通りである。さらに、

OLSRの大きな特徴として、フラッディングを効率化するためのMPR (Multi Point Relay)集合の概念を導入していることが挙げられる。フラッディングとは、宛先不明のノードへメッセージを送信したり、ネットワーク中のすべてのノードへメッセージを送信する手段である。この時、

単純なフラッディングのメカニズムを用いた場合には、メッセージを受信したすべてのノードがそのメッセージの再送信を行うために、ネットワーク中に冗長なメッセージが多く流れてしまう。

しかし、OLSRではMPR集合を用いてフラッディングを行うことにより、冗長なメッセージを削減し、フラッディングの効率化を図ることが可能になる。両者の比較を図 3.1に示す。

( a )単純なフラッディング ( b ) MPR集合を用いたフラッディング

図 3.1: 単純なフラッディングとMPR集合を用いたフラッディングの比較

(13)

第 3 章 OLSRによる経路制御

3.2 MPR 集合

MPR (Multi Point Relay)集合とは、OLSRプロトコルが動いているネットワーク上でメッ

セージのフラッディングを行う際に、再送信を行うノードの集まりのことである。この再送信を行うノードは各ノードごとに選択される。例えば、ノードAとノードBというノードがあったとする。ノードAから発せられたメッセージを再送するべきノードの集合を「ノードAのMPR 集合」といい、ノードBから発せられたメッセージを再送するべきノードの集合を「ノードBの MPR集合」という。このように実際のMPR集合とは、ネットワーク中の各ノードにより、それぞれ選択された複数のMPR集合により構成されている。なお、あるノードをMPRとして選択しているノードの集合をそのノードの「MPRセレクタ集合」という。この情報を管理することにより、各ノードはどのノードから受信したメッセージを再送信すればよいかを把握することができる。

さらに、各ノードは「Willingness」という0〜7の範囲で定義された値を保持している。この値は各ノードの再送信に対する積極性を表している。つまり、この値が大きければ大きいほど再送信に対して積極的であり、他のノードからMPRとして選択される可能性が高くなる。また、

表 3.1に示すように、それぞれの値にわかりやすいように名前が付けられている。

表 3.1: OLSRにおけるWillingness 定数名値

WILL NEVER 0

WILL LOW 1

WILL DEFAULT 3

WILL HIGH 5

WILL ALWAYS 7

3.3 OLSR のパケットフォーマット

OLSRのパケットは、図 3.2示したように1つのパケットヘッダと複数のメッセージヘッダから成り立っており、各ノードがUDP698番を使用して定期的に送信する。

(14)

図 3.2: OLSRパケットフォーマット

以下に各フィールドの役割を示す。

• パケット長

メッセージまでを含めたパケットの長さを格納するフィールド

• パケットシーケンス番号

ノードから送信されたパケットのシーケンス番号を格納するフィールド

• メッセージタイプ

メッセージの種別を格納するフィールド、1〜127まで予約されている

• 有効時間

メッセージの有効期限を格納するフィールド

• メッセージサイズ

メッセージのサイズを格納するフィールド

• 起点IPアドレス

メッセージの発生源となるノードのIPアドレスを格納するフィールド

• TTL (Time To Live)

最大ホップ数を格納するフィールド

(15)

• ホップ数

メッセージの発生源からのホップ数を格納するフィールド

• メッセージシーケンス番号

メッセージのシーケンス番号を格納するフィールド OLSRのメッセージタイプ

OLSRのメッセージには以下の4種類のメッセージがある。

• HELLOメッセージ

• TC (Topology Control)メッセージ

• MID (Multiple Interface Declaration)メッセージ

• HNA (Host and Network Association)メッセージ Helloメッセージ

HELLOメッセージは、各ノードが持つ情報の通知を目的として定期的に送信されるメッセー

ジであり、これにより周辺情報の収集を行うことができる。OLSRでは、各ノードは「ローカルリンク情報」という以下の5つの要素を含む情報を管理しており、HELLOメッセージを送受信することにより「ローカルリンク情報」を構築する。また、HELLOメッセージを使用する場合には、パケットヘッダのメッセージタイプに1を格納し、TTLを1にする（隣接ノードにのみ送信するため）。

• リンク集合

直接的に電波が届くノードへのリンクの集合である。各リンクは2ノード間のアドレスの組と有効時間により構成される集合

• 隣接ノード集合

各隣接ノードのアドレスや、そのノードへの再送信への積極度 (Willingness)により構成される集合

• 2ホップ隣接ノード集合とそれらのノードへのリンク集合

隣接ノード集合のさらに先に存在するノードの集合とそれらへのリンクにより構成される集合

(16)

• MPR集合

MPRとして選択された隣接ノードの集合

• MPRセレクタ集合

自身をMPRとして選択しているノードの集合

図 3.3にHELLOメッセージのフォーマットを示す。

図 3.3: OLSR HELLO メッセージフォーマット

以下に、HELLOメッセージの各フィールドの役割を示す。

• 予約

予約フィールド

• HELLO発生間隔

HELLOメッセージの送信間隔を格納するフィールド（デフォルトは2秒）

• Willingness

ノードの再送信の積極度を格納するフィールド（デフォルトは3）

• リンクコード

リンク情報とノード情報を格納するフィールド

2bitのリンクタイプ（表 3.2）と2bitの近隣タイプ（表 3.3）の組み合わせで表現される

• リンクメッセージサイズ

リンクメッセージのサイズを格納するフィールド

(17)

• 近隣ノードのインターフェースアドレス

近隣ノードのインターフェースアドレスを格納するフィールド

表 3.2: リンクタイプタイプリンクの状態

UNSPEC LINK 状態不明リンク

ASYM LINK 非対称リンク

SYM LINK 対象リンク

LOST LINK 切断リンク

表 3.3: 近隣タイプ

タイプ近隣のノードの状態

SYM NEIGH 近隣ノード中に1つ以上の注目ノードへの対称リンクを持つものがある

MPR NEIGH 近隣ノード中に1つ以上の注目ノードへの対称リンクかつ

起点ノードのMPR集合を持つものがある

NOT NEIGH 近隣ノード中には注目ノードへの対称リンクが存在しない

TC (Topology Control)メッセージ

TCメッセージは、ネットワーク全体のトポロジーを各ノードに通知するためにフラッディングされるメッセージである。各ノードはそのトポロジー情報を基に実際の通信経路を計算して、

経路表を構築する。ここでいうトポロジーとは、ネットワーク上に存在するすべてのノードのリンクではなく、MPRセレクタ集合から構築されるために、管理するリンク数は実際のリンク数よりも少なくなる。

TCメッセージは、MPRとして選択されているすべてのノードによって定期的に送信され、

最低でも自分自身（MPRノード）とMPRセレクタ集合間のリンク情報が含まれている。この情報から、ネットワーク上のすべてのノードはMPRとそのMPRセレクタの集合を知ることができる。これにより、各ノードがネットワーク全体のトポロジーを把握することができる。また、

TCメッセージを使用する場合には、パケットヘッダのメッセージタイプに2を格納し、TTLはフラッディング範囲に応じて設定される。図 3.4にTCメッセージのフォーマットを示す。

(18)

図 3.4: OLSR TC メッセージフォーマット以下に、TCメッセージの各フィールドの役割を示す。

• 近隣広告シーケンス番号

近隣広告シーケンス番号（近隣ノードの変化を検知するたびに1ずつ増える）を格納するフィールド

• 予約

予約フィールド

• 近隣広告アドレス

MPRセレクタ集合を広告アドレスとして格納するフィールド MID (Multiple Interface Decraration)メッセージ

MIDメッセージは、ノードが複数のインターフェースを備えている場合に使用される補助的なメッセージである。複数のインターフェースを備えるノードは、定期的にそのインターフェースの設定を他のノードに通知する必要があるため、MIDメッセージをフラッディングすることによりこれを行う。なお、このフラッディングはMPR集合を用いて行われる。また、MIDメッセージを使用する場合には、パケットヘッダのメッセージタイプに3を格納する。図 3.5にMID メッセージのフォーマットを示す。

図 3.5: OLSR MID メッセージフォーマット

(19)

以下に、MIDメッセージの各フィールドの役割を示す。

• OLSRインターフェースアドレス

ノードが持つOLSRインターフェースのアドレスを格納するフィールド HNA (Host and Network Association)メッセージ

HNAメッセージとは、ノードがゲートウェイとして機能する場合に使用される補助的なメッセージである。また、HNAメッセージを使用する場合には、パケットヘッダのメッセージタイプに4を格納する。図 3.6にHNAメッセージのフォーマットを示す。

図 3.6: OLSR HNA メッセージフォーマット

以下に、HNAメッセージの各フィールドの役割を示す。

• ネットワークアドレス

ノードが所属するネットワークアドレスを格納するフィールド

• ネットマスク

ノードが所属するネットワークのサブネットマスクを格納するフィールド

3.4 OLSR ノードが管理するテーブル

OLSRプロトコルが動いているノードは、第 3.3節で説明した「ローカルリンク情報」の他に次の2つのテーブルを管理している。

• TC (Topology Control)テーブル

• ルーティングテーブル

(20)

第 3 章 OLSRによる経路制御 TC (Topology Control)テーブル

TC (Topology Control)テーブルはネットワークのトポロジーの情報を管理するテーブルであ

る。ここで言うトポロジーとは、第 3.3節でも述べたとおり、ネットワーク上に存在するすべてのノードのリンクではなくMPRセレクタ集合から構成される。このテーブルはMPRにより定期的にフラッディングされるTCメッセージにより作成される。

ルーティングテーブル

ルーティングテーブルは任意の2ノード間の経路情報を管理するテーブルであり、TCテーブルを基に作成される。TCメッセージのフラッディングによりすべてのノードはすべてのノードのMPR集合を知ることができる。あるノードのMPR集合がわかるということはそのノードまでの最後の１ホップの経路がわかるということだから、結果的にすべてのノードのトポロジーを把握することができる。これに、Dijkstraのアルゴリズムを適用して最短経路を求める。

(21)

第 4 章

パケット削減法

本論文で提案する手法について述べる。

4.1 提案手法の概要

OLSRはプロアクティブ型のルーティングプロトコルであり、第 2.2.1節でも述べたとおり、

非通信時にも制御メッセージが流れている。流れている制御メッセージとしては、ネットワークに存在するすべてのノードが定期的に送信するHELLOメッセージ、MPRノードが定期的に送

信しているTCメッセージ、状況に応じてMIDメッセージ、HNAメッセージがある。なお、HELLO メッセージの送信間隔はデフォルトで2秒、TCメッセージの送信間隔はデフォルトで5秒となっている。これらのメッセージがネットワーク中に頻繁に送信されるために、結果的に帯域を圧迫してしまう。しかし、ネットワークの状況によってはそこまで頻繁に制御メッセージを送信する必要が無い場合がある。そこで、各ノードがネットワークの状況に応じて、動的に制御パケットの送信間隔を調整することによって、冗長な制御パケットを削減する手法を提案する。

4.2 提案手法の詳細

本提案手法は、移動していないノード、もしくはネットワークから離脱する可能性の低いノードの制御メッセージの送信間隔を長くすることにより、ネットワーク中に流れる制御パケットの削減を実現する。ただし、本提案手法においてのノードの移動、ネットワークからの離脱については以下のように定義するものとする。

• ノードの移動

自身が移動している場合はもちろん、自身が停止している場合でも、隣接するノードが移動していれば相対的に見て移動していると考え、そのノードも移動しているとする。つまり、あるノードが移動していた場合、隣接するノードはすべて移動しているものとする。

(22)

第 4 章パケット削減法

• ネットワークからの離脱

本提案手法におけるネットワークからの離脱とは、通信圏外へ移動した場合を指し、各ノードのバッテリ残量切れによる離脱は考えないものとする。つまりネットワークから離脱する可能性の低いノードとは通信圏外へ移動する可能性の低いノードのことを指す。

各ノードはネットワーク中では様々に状況が変化する。その場にとどまり続けるノードもあれば、頻繁に移動するノードがあったり、移動したり止まったりといったノードも存在する。そのため、動的に制御メッセージの送信間隔を調整するためには、各ノードが、状況変化に柔軟に対応する必要がある。その手段として、本提案手法では、各ノードがローカルに持つ情報（ローカルリンク情報）を定期的に参照し、状況変化を把握するよう提案する。

なお、提案手法において調整の対象とする制御メッセージはHELLOメッセージのみとする。

4.2.1 提案手法の規則

本提案手法では次に示す5つの規則を前提とする。

規則1 各ノードは2秒間隔で自身の状況判断を行う

OLSRにおけるHELLOメッセージはデフォルトはで2秒間隔で送信される。そのため本提案

手法で各ノードの状況判断の間隔を2秒間隔とした。

規則2 MPRとして選択されたノードは調整対象から外す

MPRノードは、TCメッセージを送信したりメッセージを積極的に中継したり非常に重要な役割を果たすノードである。このノードの制御メッセージ送信間隔を長くしてしまった場合、その遅れがネットワーク全体に与える影響が非常に大きくなってしまう。そのため、本提案手法ではMPRとして選択されているノードに関しては通常通りの処理を行うものとする。

規則3 MPRでなければ状況に応じた処理を行う

MPRで無い場合は自身の状況に応じた処理を行う。状況とそれに応じた処理については後述する。

規則4 調整する送信間隔は最小値2秒、最大値5秒とする

本提案手法で、HELLOメッセージの送信間隔を調整する際、最小値はデフォルトの2秒とし、

最大値は5秒とする。これはTCメッセージの送信間隔がデフォルトで5秒とされているからである。TCメッセージはネットワークのトポロジーの情報を含む。これらの情報のすべての基に

(23)

なるものはHELLOメッセージであり、その送信間隔がTCメッセージの送信間隔より長くなってしまうとトポロジの正当性が低下してしまう可能性があるため、本提案手法では最大値を5秒とした。

規則5 HELLOメッセージの送信間隔に応じて有効時間も調整

HELLOメッセージの送信間隔を変更したら、それに応じて有効時間も動的に調整する。

4.2.2 ノードの状況判断

各ノードは第 3.3節で述べた「ローカルリンク情報」を基にして各自の状況変化を把握する。

「ローカルリンク情報」のうち、本提案手法で参照するのは以下の3つである。

• 隣接ノード集合

この情報から、自身が移動したかどうかを判断する。隣接ノード集合が変化していれば移動したものとする。

• MPR集合

この情報も、移動の有無を判断する。MPR集合が変化していれば中継経路に変化があったということだから、移動したものとする。

• MPRセレクタ集合

この情報から、自分自身が他のノードからMPRとして選択されているかいないかを把握する。

各ノードはこれらの情報を基に、自分自身の状況を判断し、それに対応する処理を行う。なお、

これらの情報の変化とは、要素自体の変化ではなくそのエントリの数の変化のみを見ている。

4.2.3 制御パケット送信間隔の調整

各ノードの状況とそれに対応する処理について述べる。各ノードの状況判断はそれぞれが持つ

「隣接ノード集合」と「MPR集合」の情報を基に判断する。これらの情報から、各ノードの状況は図 4.1のように9通り考えられる。なお、図 4.1中に制御メッセージ送信とあるが、これは移動があった場合に、そのトポロジの変化を速やかに隣接するノード、もしくはMPRノードへ告知する必要があるためである。また、ここで制御メッセージを送信した場合、制御メッセージ送信タイマをリセットすることにより、最低でも２秒間隔でしか制御メッセージが流れないようにした。これにより、提案手法を用いた場合の制御パケットの量が、既存手法においての制御パ

(24)

ケットの量を上回る可能性を最小限に抑えることができる。ただし、非常にまれではあるが提案手法を用いた場合のほうが上回ることもある。各状況に対応する処理は次の通りである。

• どちらにも変化が無ければ移動がなかったということなので、ネットワークからの離脱の可能性が低いと考える。そのため送信間隔を1秒増やす⇒1

• MPRに変化が無い場合、隣接ノードが増えればネットワークからの離脱の可能性は低いと考える。そのため送信間隔を1秒増やす⇒2

• MPRに変化が無い場合、隣接ノードが減れば、ネットワークから離脱する可能性が高くなると考る。そのため送信間隔を1秒減らす⇒3

• MPRが増加した場合、トポロジーを構成するためにより多くの情報が必要になるため送信間隔を短くする必要がある。そのため隣接ノードの状況に関わらず送信間隔を1秒減らす⇒4、5、6

• 隣接ノードが増えるか変わらずにMPRが減るということは、中継せずに直接送信できるようになったということであり、ネットワークからの離脱の可能性は低いと考える。そのため送信間隔を1秒増やす⇒7、8

• どちらも減少している場合、ネットワークから離脱する可能性が高い考える。そのため送信間隔を1秒減らす⇒9

図 4.1: 状況変化と対応処理

(25)

第 4 章パケット削減法 4.2.4 提案手法の流れ

これらの考え方を基に、各ノードが以下の手順の処理を行うことにより、本提案手法が実現される。

(1) 自身がMPRとして選択されているかいないかを判断

(2) MPRならば通常通りの処理

(3) MPRでなければ状況に応じた処理

(4) ２秒間隔で (1) 〜 (3)を繰り返し行う

(26)

第 5 章実証実験

様々なネットワークの状況において、提案手法の動作を検証し、その有効性を示す。

5.1 検証の目的

本提案手法が、OLSRをベースとしたアドホックネットワークにおいてどのような影響を及ぼすかを検証する。具体的には、提案手法を用いることによって、既存手法と同等の性能を維持したままで制御パケットの削減を実現できることを示す。

5.2 検証の詳細

本検証では、まったく同じ状況のネットワークにおいて、提案手法を使用しない場合(既存手法)と提案手法を使用した場合を比較する。なお、検証にはNS2シミュレータを用いる。

検証するネットワークの状況

検証するネットワークの状況は、ノードが移動体であるため無限のパターンがある。そこで、

今回は以下のようにノードの移動が無い場合、ある場合に分類して数パターンのネットワークを検証した。以下の5パターンのネットワークを検証することで提案手法を用いた場合の一般的な傾向を考察することが出来る。

• ノードの移動がないネットワーク

– ノード数を固定し、ネットワーク範囲を変化させる – ネットワーク範囲を固定しノード数を変化させる

• ノードの移動があるネットワーク

(27)

第 5 章実証実験 – 図 5.1のようにノードが1点から拡散するように移動する場合（拡散的な移動）

– 図 5.2のようにノードが1点に集合するように移動する場合（集合的な移動）

– ノードがランダムに移動する場合

図 5.1: 拡散的な移動

図 5.2: 集合的な移動

以上5パターンについてそれぞれを検証1〜検証5として検証を行う。

測定する項目について

各検証ごとに既存手法と提案手法を比較する際に、以下のような測定を行いその結果を基に比較、考察を行う。

• ping到達率

ネットワーク中の任意の1ノードから他の全ノードへpingを送り、その到達率を測定する。pingは0.2秒間隔で300回ずつ送信する

(28)

第 5 章実証実験

• ping応答時間

各ノードへのすべての応答時間を平均したものを平均応答時間とし、測定する。

• 制御パケット量（制御メッセージ量）

すべてのノードから送信された制御パケットの総数を制御パケット量とし、測定する。

ここでいう制御パケットとはHELLOメッセージ、TCメッセージを含めたすべての制御メッセージのことを指す。

シミュレーションの主なパラメータについて

NS2シミュレータにおいては、主要なパラメータを以下のように設定して行った。なお、シミュレータへのOLSR拡張については一般にソースの公開されているUM-OLSRを用いた。

表 5.1: シミュレータのパラメータ設定

パラメータ設定

インターフェース無線のみアンテナタイプオムニアンテナ

MAC層 IEEE 802.11

プロトコル OLSR

最大通信可能距離 100m

ネットワークの範囲 50m×50m〜500m×500m ノードの数 5〜30

移動速度 1m/s〜15m/s

5.3 検証の結果

以下に、書く検証の詳細な条件と結果を示す。ここで使われる制御パケットとは、HELLOメッセージ、TCメッセージ等のOLSRで使用される制御メッセージの総称とし、単にパケットとは測定用のpingのパケットを指すものとする。

5.3.1 検証1

ノード数を25個に固定し、ネットワークの範囲を50m×50m〜500m×500mまで50m間隔で広げていく。このときの既存手法と提案手法でそれぞれ測定した。なお、ノードはランダムに配置した。各測定結果は次の通り。

(29)

図 5.3: ネットワーク範囲とping到達率

図 5.4: ネットワーク範囲とping応答時間

図 5.3、図 5.4より、既存手法と提案手法の間に大きな性能の差は見られない。つまり、提案手法により制御パケットを削減してもネットワークの構築に大きな問題はないと言える。また、

図 5.3から見て分かる通りネットワークが250m×250mより大きくなるとping到達率が大きく減少する。OLSRをベースにしたネットワークは既存手法でもノードの通信可能範囲の2倍程度のネットワーク範囲までが最適なネットワークであり、それは提案手法を用いても変わらない事が分かる。

(30)

図 5.5: ネットワーク範囲と制御パケット量

図 5.5から、提案手法を用いることで制御パケットが効率よく削減できていることがわかる。

具体的に、既存手法と比較して提案手法でどの程度制御パケットを削減できたかを削減率として算出した。結果を表5.2に示す。表5.2からネットワークの範囲に依存して制御パケットの削減率も変化するのがわかる。特にネットワークの範囲が狭いほど効率よく制御パケットを削減できている。400m×400mあたりで削減率が増えている。これは、範囲が広くなりすぎると各ノードの通信可能範囲を超えてしまい、中継しても25個すべてが通信できないような部分的なネットワークが複数存在しているためである。結果的にそれぞれの部分の範囲が狭くなってしまっているため、より多くの制御パケットが削減されている。

表 5.2: ネットワーク範囲と制御パケット削減率ネットワーク範囲制御パケット削減率(%)

50m×50m 57.59

100m×100m 53.81 150m×150m 40.35 200m×200m 22.39 250m×250m 15.14 300m×300m 12.71 350m×350m 13.33 400m×400m 14.11 450m×450m 23.80 500m×500m 26.51

(31)

第 5 章実証実験 5.3.2 検証2

ノード範囲を200m×200mに固定し、ノード数を5〜30まで5個間隔で増やしていき既存手法と提案手法でそれぞれ測定した。各ノードはランダムに配置されるものとする。各測定結果は次の通り。

図 5.6: ノード数とping到達率

図 5.7: ノード数とping応答時間

図 5.6,図 5.7より、検証1と同様に既存手法と提案手法の性能に大きな差は見られず、問題

(32)

なくネットワークを構築できているといえる。ネットワークの範囲とは違い、ノード数がはping 到達率にそれほど大きな影響を与えていないことも分かる。

図 5.8: ノード数と制御パケット量

また、検証1と同様に図 5.8から制御パケット削減率を算出した。結果を表 5.3に示す。表から分かるように制御パケットの削減率はネットワークの範囲ほどはノード数に依存していないことがわかる。今回はネットワーク範囲を200m×200mに固定したが、検証1の結果と合わせると、範囲が狭ければさらなる制御パケットの削減が期待できる。

表 5.3: ノード数と制御パケット削減率ノード数制御パケット削減率(%)

5個 33.74

10個 30.89

15個 26.39

20個 27.60

25個 25.80

30個 30.07

5.3.3 検証3

ノード数25個、拡散的な動き（図5.1参照）でネットワーク範囲50m×50mから500m×500m まで広がるように移動。その際の速度を1m/s〜15m/sまで2m/s間隔で速くしていき、既存手

(33)

法と提案手法についてそれぞれ測定し比較した。なお、速度はすべてのノードにおいて等速であり、すべてのノードが同時に移動を開始する。各測定結果は次の通り。

図 5.9: 拡散的な移動の移動速度とping到達率

図 5.10: 拡散的な移動の移動速度とping応答時間

図5.9から分かるように、ネットワーク中のノードが拡散するように移動するような場合には、

既存手法より、提案手法のほうがpingの到達率が悪くなってしまう。これはルーティングの際に正確なルーティングエントリが見つからず破棄されるパケットが増えているからである。また、

(34)

図5.10のping応答時間に関してはばらつきはあるものの比較的提案手法の方が短くなっている。

この理由は、本来なら衝突を避けるために再送するべきパケットの一部が、ルーティングエントリ不足により破棄され、再送を待つ時間が短縮されたためにこのような結果になっている。

図 5.11: 拡散的な移動の移動速度と制御パケット量

検証1、検証2同様に図 5.11から制御パケット削減率を算出した。結果を表 5.4に示す。ノードが移動しているにもかかわらず多くの制御パケットが削減されてしまっているのが分かる。このため正確なルーティングが行えずping到達率も既存手法に劣る結果となってしまっている。

表 5.4: 拡散的な移動の速度と制御パケット削減率移動速度（m/s）制御パケット削減率(%)

1 35.68

3 17.53

5 11.98

7 21.54

9 9.93

11 15.97

13 18.03

15 15.39

(35)

第 5 章実証実験 5.3.4 検証4

ノード数25個、集合的な動き（図5.2参照）でネットワーク範囲が500m×500mから50m× 50mまで狭まるように移動。その際の速度を1m/s〜15m/sまで2m/s間隔で早くしていき、既存手法と提案手法についてそれぞれ測定し比較した。検証3と同様、すべてのノードは等速であり、すべてのノードが同時に移動を開始するものとする。各測定結果は次の通り。

図 5.12: 集合的な移動の移動速度とping到達率

図 5.13: 集合的な移動の移動速度とping応答時間

ネットワークが集合的に移動するような場合、図5.12、図5.13から提案手法を用いてもほぼ既

(36)

存手法と同等の性能を維持できることが分かる。

図 5.14: 集合的な移動の移動速度と制御パケット量

表 5.5に制御パケット削減率を示す。移動速度が遅ければネットワークの範囲は広いままであるため、この結果からも検証1で得られた結論と同様、ネットワーク範囲が狭いほうが効率的に制御パケットを削減できるということが言える。

表 5.5: 集合的な移動の速度と制御パケット削減率移動速度（m/s）制御パケット削減率(%)

1 2.82

3 6.25

5 16.01

7 15.28

9 20.99

11 22.12

13 25.38

15 23.06

5.3.5 検証5

ノード数25個、ネットワーク範囲200m×200mで固定し、その中で各ノードがRandom Way

Pointモデルに従い移動する。その際の移動速度を1m/s〜15m/sの間で2m/s間隔で早くして

(37)

いき、既存手法と提案手法でそれぞれ測定し、比較した。なお、移動速度はすべてのノードにおいて等速であり、常に移動しているわけではなく、移動・停止をランダムに行うものとする。各測定結果は次の通り。

図 5.15: ノードの移動速度とping到達率

図 5.16: ノードの移動速度とping応答時間

図 5.15、図 5.16から、移動速度に関わらず全体的に既存手法よりも提案手法のほうがやや性能が劣っているが、それほど大きな差はない。また、OLSRはプロアクティブ型であるので移動するネットワークにはあまり適していない。図 5.15、図 5.16から既存手法でさえ、速度が少

(38)

し速くなるだけで極端に性能が劣化しているのが分かる。全体的な傾向としては提案手法を用いても既存手法と同じような傾向をたどっているため、移動するネットワークであっても既存手法と同等の性能を維持できているといえる。

図 5.17: ノードの移動速度と制御パケット量

他の検証と同様、図 5.17より制御パケット削減率を算出した。結果を表 5.6に示す。表から分かるとおり移動があるネットワークでは制御パケットの削減率も大きく減少することが分かる。

これは、本提案手法でネットワーク的な移動があった場合には臨時で制御メッセージを送信するという手法をとっているため、頻繁に移動する場合はそれだけ多く臨時の制御メッセージが送信されてしまうからである。ただし、臨時の制御メッセージを送信したら、タイマーをクリアするため基本的には既存手法より多くの制御メッセージが流れることは無い。

表 5.6: 移動速度と制御パケット削減率移動速度（m/s）制御パケット削減率(%)

1 18.30

3 7.26

5 5.79

7 2.31

9 3.86

11 3.53

13 2.86

15 1.60

(39)

5.4 考察

検証1〜検証5の結果より、本提案手法を用いることにより、ノードの移動がないネットワークにおいては、本来のネットワークの性能を落とすことなく効率良く制御パケットを削減できることが分かる。また、その効果はノード数にではなく、ネットワークの範囲に大きく依存することが分かった。特にネットワークの範囲が狭い場合には大きな効果が期待できる。しかし、ノードの移動があるネットワークの場合、極端に広がっていくような移動をすると逆にネットワークの性能を劣化させてしまうことも分かった。それ以外の移動に関しては、多少性能の劣化は見られるものの大きく劣るわけではない。また、検証の結果より提案手法を用いることで、各ノードが自立的に状況を判断して処理していることも確認できる。

本来、OLSRを含むプロアクティブ型のプロトコルをベースとしたアドホックネットワークは、第 2.2節で述べたように、頻繁にノードが移動するネットワークには適していない。これは検証3〜検証5の既存手法の結果からも明らかである。また、OLSRに限って言えば、大規模で密度の高いネットワークで高い性能を発揮するのが大きな特徴である。本提案手法も、このOLSR の特徴が顕著に出ていることが分かる。これらの点を考慮すると、本提案手法はOLSRをベースにしたアドホックネットワークにおいて、十分に有効な手法であると言える。

(40)

第 6 章結論

6.1 まとめ

制御メッセージの削減と信頼性の間にはトレードオフの関係がある。制御メッセージを極端に減らしてしまうとトポロジーを把握できず正確なルーティングテーブルも作成できないため信頼性を著しく低下させてしまう。しかし、本論文での提案手法のように、各ノードがその都度ネットワークの状況に応じて動的に制御メッセージの量を調整することにより、信頼性をほぼ保ったままでネットワーク中を流れる制御パケットを削減することができる。また、検証の結果、本論文での提案手法は、多少の例外はあるものの様々なネットワークの状況に柔軟に適応できている。

6.2 今後の課題

より詳細なローカル情報の参照

本提案手法において、各ノードの状況判断材料として、ローカルリンク情報を用いた。しかし、

今回参照したのは各情報に含まれるエントリの数の変化であり、具体的な要素の変化までは着目していない。様々なネットワークの状況変化に適応させるためには、これらの具体的情報も参照する必要がある。

ノード移動時の性能改善

検証の結果から分かる通り、ノードの移動が頻繁になるとやや既存手法に劣る場合がある。プロアクティブ型のプロトコルをベースにしているため、移動するネットワークに向いてないものの、より性能を改善するためには、各ノードで移動速度や移動の方向などを把握する必要がある。

(41)

謝辞

本修士論文の作成にあたり日頃より御指導を頂いた早稲田大学理工学部の後藤滋樹教授に深く感謝致します。また、貴重な助言、多大なる御協力を頂きました後藤研究室の諸氏に感謝致します。

(42)

参考文献

[1] T.Clausen, “ Optimized Link State Routing Protocol (OLSR) ”, RFC3626, October 2003.

[2] INTERNET Watch 第6回 OLSR (Optimized Link State Routing)プロトコル, http://internet.watch.impress.co.jp/www/column/wp2p/wp2p06.htm

[3] Yangcheng Huang, Saleem N.Bhatti, Daryl Parker, “TUNING OLSR”, The 17th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC’06), 2006.

[4] C.Gomez, D.Garcia, J.Paradells, “Improving Performance of a Real Ad-hoc Network by Tuning OLSR Parameters”, Proceedings of the 10th IEEE Symposium on Computer and Communications (ISCC 2005), 2005.

[5] Michael Voorhaen, Chris Blondia, “Analyzing the Impact of Neighbor Sensing on the Performance of the OLSR protocol”, IEEE, 2006.

[6] Stephanie Demers, Latha Kant, “PERFORMANCE ANALYSIS AND MANAGEMENT”, Telcordia Technologies, Inc. 2006.

[7] C-K.Toh 著,構造計画研究所訳『アドホックモバイルワイヤレスネットワーク』共立出版,

2003.

[8] 有田真也『アドホックネットワークにおける消費電力を考慮したルーティングプロトコル』

早稲田大学大学院理工学研究科 2006年度修士論文, 2007.

[9] 荒井大輔『アドホックネットワーク上のサービス発見におけるキャッシュ機構』早稲田大学大学院理工学研究科 2006年度修士論文, 2007.

[10] 熊谷佑紀, 大野優樹, 須藤崇徳, 阪田史郎『アドホックマルチキャストにおける位置情報を利用した制御パケット削減方式』2007年電子情報通信学会総合大会, 2007.

(43)

参考文献

[11] 大薮勇輝『アドホックネットワークにおけるネットワークトラフィックに適応したコンテンツフラッディングモデルの提案』慶応義塾大学環境情報学部 2005年度卒業論文, 2006.

[12] Mobile Ad-hoc Networks (manet) Charter

http://www.ietf.org/html.charters/manet-charter.html [13] Ther Network Simulator - ns-2

http://www.isi.edu/nsnam/ns/

[14] Francisco J.Ros, UM-OLSR http://masimum.dif.um.es/

OLSR 制御パケットの削減法 アドホックネットワークにおける

2007 年度 修士論文

アドホックネットワークにおける