- 図3.1 ネットワーク例
センサーネットワークに使用されるノードには内蔵電源等で動作している場合がある。また、センサーネットワークではアドホックネットワークを構成している場合がある。アドホックネットワークでは直接通信を行いたいノード間で通信が行われない場合は周辺ノードが中継を行って通信を行う。
センサーネットワークで1つの経路にトラフィック集中や、大量のデータの中継を行ったノードでは消費電力の増加が考えられる。そこで今回提案するルーティングでは経路の二重化とあえて最適な経路をしないことによる特定のノードへの負荷を減らし分散させる方法について考える。センサーネットワークで採用されている代表的な無線通信規格としてはZigBeeがあるが、最大でデータ転送速度が250kbpsと低速なこと、センサーデバイスには電池駆動で数年間動作することが望まれており、ノードへの負荷を分散させることは意義があるものと考えている。そこで、今回はアドホックネットワークのルーティングプロトコルの１つであるAODVに改良を加えることにした。
ネットワーク上においては信号の衝突や、衝突回避等が原因でホップ数が増えるほど通信速度を低下させる。そこで、経路を分流させることにより通信帯域を向上できないかを研究することである。
本研究では、アドホックネットワークにおいてルーティングプロトコルの１つであるAODVを改良した方式を提案する。
アドホックネットワークとは無線マルチホップで通信を行い、集中管理機構がない、分散のネットワークである。実ネットワークとして、MANET（mobile ad hoc network）やセンサーネットワーク等での利用が考えられる。通信の経路を制御するルーティングの方式として大きく分けてプロアクティブとリアクティブの２種類に分けることができる。プ ロアクティブ方式では、RIPのように定期的にノード間で経路情報のやりとりを行い、全てのノードが経路情報を所有しており、その経路情報から経路を求めてデータを送信する方式である。対して、リアクティブ方式ではオンデマンド形式であり、データを送信する際に、ルーティングを行うことにより経路を計算する方式であり、今回、本論文の題材にしたAODVもリアクティブ型に分類される。
AODVは２．１で述べたように、リアクティブ型のルーティングプロトコルの一つであり、RFC3561で詳細が決められている。AODVにおいて送信元のノードは実際にどのような経路を通るかの情報を必要としていないという特徴がある。AODVはUDPの654ポートを用いてルーティングを行い、使用するメッセージはRoute Request(RREQ)、Route Reply(RREP)、Route Error(RERR)である。また、ノードそれぞれでシーケンス番号を管理しており、RREQの送信を行うたびにシーケンス番号の加算を行う。このシーケンス番号はメッセージ内に内包させることにより、シーケンス番号の大小により異なるメッセージを複数受信した際などに最新のメッセージはどれかを判断することが可能になっている。主要なメッセージであるRREQとRREPメッセージに内包されている主要な情報として次のような情報がある。
送信ノードが受信ノードの経路情報を持たないとき、経路要求（RREQ）をブロードキャストして、自身のシーケンス番号を加算する。RREQを初めて受信したノードは生成元への 経路エントリを生成し、プリコーサリストにRREQを現在のノードに送信したノードを記憶し、RREQの再ブロードキャストを実行する。RREQの受信先IPアドレスとRREQメッセージを受信したノードIPアドレスが同一なら受信先ノードに到着したと判断する。受信先ノードに到着するとプリコーサリストの情報を元に次点ノードにRREPメッセージをユニキャストする。RREPメッセージが送信ノードに到着することにより最短経路が確定する。
二次元上にノードが配置されている状況で経路を二分化して大容量化を行うのが、本論文で提案内容であり、前提条件として二次元にノードを配置し、三回AODVを実行することにより経路の二分化を行う。AODV改良にあたり、送信元ノードと受信先ノードにおいて経路の二分化を行い、送信元が次ホップを切り替えることにより経路の二分化を行う。
まず、提案するAODVの改良案ではルーティングメッセージに新たに2ビットのフィールドを新設し本論文中ではTypeと呼称する。本論文ではフィールドの値をそれぞれType1,Type2,Type3,Type4と呼び、このうちType1,Type2,Type3を使用する。また、Type値の変更は送信元ノード以外には行わないとする。また、各ノードが保有する経路情報を記録する経路エントリを3つにして、それぞれTable1,Table2,Table3と本論文では呼称するとする。Type1,Type2,Type3とTable1,Table2,Table3はそれぞれ関連づけを行い、Type1の値を持つルーティングメッセージから得た経路情報はTable1に格納し、同様にType2はTable2にType3はTable3にルーティングメッセージから得た経路情報を格納する。
送信元ノードはTypeフィールドの値をType1にしてRREQをブロードキャストする。受信先よりType1のフィールドを持つRREPを受信したのならTypeフィールドの値をType2にしてRREQをブロードキャストする。同様にTypeフィールドの値がType2のRREPを受信したのならTypeフィールドの値をType3にセットしてRREQをブロードキャストする。Type3のRREPを受信したのならTable1とTable3の値を経路とする。もし、受信先からのType2,Type3フィールドを持つRREQを受信出来ないのなら経路の二重化はできないのでType1で求めた経路で送信を行う。送信先ノードはRREQを受信したら受信したRREQのType値に関連づけられているTableを使用してRREPをユニキャストする。RREQを受信して且つノードのIPアドレスとRREQの送信先アドレスが違うのならRREQから得たTypeの値を調べて、関連付けをしたTableの値より低いTableに、送信元と受信先が一致する情報が無いことを確認してからRREQのブロードキャストを実行する。もし、一致するのならRREQのブロードキャストは行わない。つまり、TypeフィールドがType2のRREQを受信したのならTable1に一致する情報が無いことを調べ、Type3のRREQを受信したのならTable1とTable2に一致する情報が無いことを調べてからRREQのブロードキャストを実行する。
図3.1においてAを送信元ノード、Dを受信先ノードとしたときType値をType1にセ ットしてRREQを行い、RREPをAが受信して最短経路であるA-B-C-Dの経路がTable１に経路情報が保存されることになる。次にType2にセットしてRREQを行うときAが送信したRREQをBが受信するがTable1にA,Dを送信元、受信先とする情報があるのでRREQのブロードキャストはおこなわない。同様にCにおいてもRREQを受信しても再送を行わない。そのためBCを利用しない経路を通る。この場合だとA-E-F-G-DもしくはA-H-I-J-Dのルートである。ここではA-E-F-G-Dが選択されたとしてするとD-G-F-E-Aの順番でDからのRREPがAに受信される。
次にType値にType3を持つRREQを送信する。B,C,E,F,GについてはそれぞれのノードのTable1,Table2のどちらかに経路情報があり、RREQをブロードキャストしないので経路としてA-H-J-I-Dを経由する。RREQを受信したDはDのIPアドレスとRREQのIPアドレスが一致するのでRREPをAにTable３の経路を使用して送信する。 Type３の値を持つRREPをAが受信することにより、A-D間に3つの経路が出来るのでType1とType3の経路、A-E-F-G-DとA-H-I-J-Dを使用して通信を行えば経路の二重化を行うことができる。
経路の二分化による通信の変化を確かめるため、コンピュータシミュレーションを作成した。Visual Studio 2008 C#で作成したプログラムについては付録１に記載した。
衝突回避としてCSMA/CAを使用した。Testクラスのコンストラクタで「Node.caSetMaxValue=10」で送信のタイミングをずらす最大値をセットできる。 また、送信先からのAckの返却がない場合に再送を行うタイムアウトとして「Node.timeOutValue=15;」とタイムアウトまでのステップ数を定義することが出来る。 Testクラスのコンストラクタに「Node a = new Node(“a”);」等と記入してノードを定義する。
１つの経路を利用した際のシュミレーション結果は表５．１、重なりあわない２つの経路を利用した際のシュミレーション結果は表５．２とする。また、二つの実験結果を重ねたのをグラフ５．１とする。グラフ５．１より、ホップ数が増加するほど直線的にステップ数が増加することが確認できるが、ホップ数が１０のとき経路を１つのみ利用する場合に比べて重なりあわない２つの経路を利用した場合は増加量が減らすことが出来ていて、ホップ数が１０個の時においては約２．４倍高速にパケットを転送できていることが確認できる。
| ステップ数 | 送信回数 | 衝突回数 | タイムアウト回数 | |
| ホップ３個（パケット１０個送信） | 520 | 52 | 4 | 13 |
| ホップ5個（パケット１０個送信） | 820 | 107 | 6 | 25 |
| ホップ10個（パケット１０個送信） | 1550 | 396 | 44 | 123 |
| ステップ数 | 送信回数 | 衝突回数 | タイムアウト回数 | |
| ホップ３個（パケット１０個送信） | 324 | 58 | 6 | 11 |
| ホップ5個（パケット１０個送信） | 431 | 103 | 7 | 24 |
| ホップ10個（パケット１０個送信） | 641 | 265 | 21 | 47 |
本論文で提案したAODVの改良案を施すことにより二つの経路上にあるノードのそれぞれを離すことによりパケットの損失を抑えながら大容量化ができると考えている。 しかしながら、本論文で提案したAODVの改良案は図3.1を例にとるとA-D間ではType1の経路はA-B-C-Dであり、Type2の経路がA-E-F-G-D、Type3の経路がA-H-I-J-Dとなり、最短距離であるType1のルートを使用しないことによりType2,Type3が隣接することによる速度低下や、パケットの損失を抑えている。だが、E-G間ではType1はE-F-G、Type2はE-B-C-G、Type3ではE-A-H-I-C-J-D-Gとなり、Type1はType2,Type3の経路の間にないので２つの経路間の距離を離すことに成功していない。この場合はType1とType3を使用すべきだがどのように判定すれば適切な2経路を選択できるかを選択することが出来るかが今後の課題だと考えている。