広島工業大学紀要研究編
第 43 巻（2009）pp.305-310

論文

アドホックネットワークにおけるノード負荷を考慮した高効率ルーティング手法に関する研究
長坂康史＊・金只圭司＊＊（平成 20 年 10 月 31 日受理）

A Study on High Effective Routing Method Using Node Loads in Ad-Hoc Networks
Yasushi NAGASAKA and Keiji KANETADA（Received Oct. 31, 2008）

Abstract
An ad-hoc network technology is focused on realizing the ubiquitous network society.
The network, however, has several problems because it is constructed with several
independent wireless nodes which might be moved. A lot of routing protocols on suchan unstable ad-hoc network have been studied. But most of protocols don’t takeaccount of loads of their nodes in spite of its importance. We have proposed the more
effective routing algorithm for the ad-hoc network using the node loads. The proposed
method uses a CPU usage, a memory usage, and so on, as a definition of the node load,
and also has the features of storing a multiple routes for a dynamic routing, transferring
the node load information, and selecting the most effective route from the information.
The simulation results show that the performance of the proposed method is better
than the existing one in case that there are 50 % of high load nodes in the network.

Key words: routing algorithm, ad-hoc networks, AODV

端末では後者の利用が注目されている。そのようなネット

1. はじめにワークは，アドホックネットワークと呼ばれる。アドホッ

ユビキタス化が進む昨今では，携帯電話や PDA などの移動端末の発達が著しい。移動端末におけるネットワーク

クネットワークは，災害時や車車間通信などの分野での利用が期待されている。

としては，ハードウェアの小型化やその移動性により配線

しかし，アドホックネットワークには多くの課題が残さ不要な無線通信技術が用いられる。そのため，携帯端末にれている。アドホックネットワークには，通信ノードの移は IEEE802.11x や Bluetooth などが標準搭載されている動によるネットワークトポロジの動的変化や，バッテリやものが多い。これらの無線通信技術も 90 年代後半から，メモリのような移動端末のリソースの制約などの問題があ通信速度が飛躍的に向上している。一般的な無線ネットワる。また，アドホックネットワークではマルチホップ通信

ークは，基地局を介して構築されるが，基地局なしで自律を行うことで，通信範囲外のノードと通信することができ的なネットワークを形成することも可能である。特に移動るが，多くの 2 端末間通信で，同じノードを経路とするよ* 広島工業大学情報学部情報工学科** ネットワンシステムズ株式会社―305―長坂康史・金只圭司

うな場合，そのノードに集中的に負荷がかかる。そのため，通信に遅延やパケットロスが生じる可能性が高い。このような問題を解決するためには，ノードの負荷を考慮したルーティング手法が有効であると考えられる。
本研究では，既存のルーティング手法である AODV（Ad hoc On-demand Distance Vector routing）［1］にノー
図 1 AODV の経路確立

ド負荷を考慮するように改良を加えた手法を提案する。提案手法は，それぞれの端末が複数経路を保持し，各経路の負荷を定期的に測定する。そして，その負荷情報から，負経路確立後，経路として利用されている各ノードは，荷が最小である経路を最適経路とする。このような負荷のHello を送信する。Hello はノードの存在を通信範囲内高い端末を回避して構築された経路は，遅延やパケットロ（TTL=1）にブロードキャストするものである。使用中のスを抑え，効率的な通信を行うことができると考えられる。

経路のネクストホップからの Hello を受信することで，その経路の有効期限を延長する。Hello が指定した時間内に2. AODV（Ad hoc On-demand Distance Vector）受信できなければ，リンク切断と判断し，経路を終了する。

AODV では，送信ノードの Route Request（RREQ）と宛先ノードの Route Reply（RREP）によって，経路を3. 提案手法作成する。また，各経路はシーケンス番号で管理され，本研究では，複数の経路から最も中継ノードの負荷が少RREQ や RREP などの経路制御メッセージにシーケンスない経路を最適経路として選択することで，高効率な通信番号を付加し，経路制御メッセージ受信時に，経路が最新を行う手法を提案する［2］。また，経路確立後，Hello で近であるかを調べるために用いられる。

隣ノードと経路情報を交換することで，ネットワークトポロジの動的変化にも対応する。

送信元ノードはデータを送信したい相手，すなわち宛先ノードへの経路を知るため，RREQ を通信範囲内の全ノノード負荷を考慮した最適経路選択は，前章で述べたードにブロードキャストする。図 1 に示すように，RREQ

AODV の RREQ，RREP そして Hello の 3 つの経路制御

は自身の通信範囲内に存在するノードを中継して，送信元メッセージを利用する。各経路制御メッセージパケットに，ノードから宛先ノードに配送される。RREQ を受信した負荷情報である中継ノードは，双方向通信のために，RREQ を送信して経路作成後にコストを考慮した経路選択が可能となる。各きたノードを送信元ノードへの経路として保持する。この制御メッセージの詳細な動作は，3.2 節，3.3 節，3.4 節で送信元ノードへの経路のことを逆経路という。各ノードが述べる。

コストを加えることで，経路作成中と保持する経路は，宛先への中継を行うノードすべての情報

図 2 に提案手法による経路確立例を示す。これは，ノーを保持するわけではない。宛先へ届けるために送るべき 1

ド A がノード F への経路を確立した状態である。提案手ホップ先のノード，つまりネクストホップのみを保持する。

法では，ネクストホップをリスト化し，複数の経路を保持

中継ノードは宛先ノードに達するまで，RREQ のブローするため，ノード B は，ノード F への経路のネクストホッドキャストを続ける。宛先ノードが，RREQ を受信するプとして，ノード C とノード D を保持している。ノードと RREP を送信ノードまでユニキャストする。RREP をB は，この 2 つのネクストホップのうち，コストが低い方受信した中継ノードは，RREP を送信してきたノードを宛の経路に配送する。また，ノード B は複数経路を保持し先ノードへのネクストホップとして保持し，逆経路のネクていることで，どちらかの経路でリンク切断が生じたとき，ストホップへユニキャストする。これによって送信元ノー他方の経路が有効であれば，再度 RREQ を送信することドから宛先ノードまでの経路が作成される。

なく，経路を切り替えることができる。従って，提案手法
では，経路再探索の時間を短縮することが可能となる。

―306―

アドホックネットワークにおけるノード負荷を考慮した高効率ルーティング手法に関する研究

ければ，再度 RREQ を送信する。このとき，RREQ のシーケンス番号は 1 増加させる。RREQ を受信したノードは，逆経路を参照し，以下の 3 つの条件に沿って経路の更新を行う。
（a）逆経路を保持していない場合
この場合，ノードは逆経路を作成する。逆経路への
図 2 提案手法による経路確立例

ネクストホップリストを作成し，RREQ を送信してきたノードのアドレス，ポート番号，Rcost をリスト

コストには，Ncost（ノードコスト）と Rcost（経路コに挿入する。

スト）がある。図 2 の各ノードの下に示す数値が Ncost，（b）逆経路のシーケンス番号＜ RREQ のシーケンス番号

矢印の上の示しているのが Rcost である。ノードコストは，この場合，現在保持している逆経路は最新の経路でノード自体のコストである。Rcost はネクストホップからはないので逆経路を更新する必要がる。既に保持して宛先ノードまでの中継ノードの Ncost の合計である。提いる逆経路のネクストホップリストを破棄する。その案手法では，Rcost が最小となる経路を最適経路とする。

後，シーケンス番号を 1 増加し，ネクストホップリス

例えば，図 2 において，ノード B は Rcost 0.4 の経路とトを作成し，RREQ を送信してきたノードのアドレ

Rcost 0.3 の経路を保持しているため，ノード A から受信ス，ポート番号，Rcost をリストに挿入する。

したデータは，ノード D に配送する。Ncost と Rcost の（c）逆経路のシーケンス番号＝ RREQ のシーケンス番号

算出方法については 3.1 節で述べる。

AODV では破棄されるが，提案手法では複数経路を保持する必要があるため，シーケンス番号が等しい

3.1

コストの算出場合も RREQ を破棄しない。逆経路のネクストホッ

提案手法で利用する Ncost と Rcost について述べる。

プリストの最後尾に RREQ を送信してきたノードのNcost には，CPU 使用率とメモリ使用率を用いる。Ncost

アドレス，ポート番号，Rcost をリストに挿入する。の算出は，次の（1）式で行う。

その後，ネクストホップリストをコストの少ない順に

N cos t = wCPU + (1 - w) Mem……（1）ソートする。提案手法では，常にリストの先頭にあるネクストホップがデータ通信に利用される。

（1）式において，Ncost はノードコスト，w は CPU 使用

次に RREQ の配送処理について述べる。RREQ 受信ノー率の重み， CPU は CPU 使用率， Mem はメモリ使用率でドが RREQ の宛先ノードではなく，（a），（b）の場合は，ある。次に，Rcost を定式化すると（2）式のようになる。

処理が終わると RREQ の Rcost に自身の Ncost の値を加R cos t n = N cos t 1 + N cos t 2 + g + N cos t n - 1 ……（2）え，ホップ数を 1 増加させ，TTL を 1 減少し，再度ブロードキャストする。（c）の場合は，同じ RREQ ID の RREQ

（2）式において， n は宛先ノードから中継ノード数，をすでに配送したことがあるので，無駄な拡散を防ぐため，

Rcost は経路コストを表す。Rcost は中継ノードの Ncost

再度 RREQ をブロードキャストすることはない。図 3 のの合計である。なお，本研究では，各ノードの性能はすべように，これらの処理が宛先ノードまで宛先ノードまで繰て同等と仮定した。

り返される。宛先ノードに到達すると RREP 処理に移行する。

3.2

RREQ フェイズ

本節では，RREQ の動作について述べる。RREQ 処理
は AODV と同様，通信要求を持つ送信元ノードから開始する。提案手法では，RREQ のフォーマットに Rcost を付け加えている。
送信元ノードは，RREQ を通信範囲内に存在するノードすべてにブロードキャストで送信する。このとき，RREQ に自身のコストである Ncost を RREQ 内の Rcostとしてセットする。送信元ノードはこの後，RREP が返って来るまで一定時間待つ。もし，一定時間内に返ってこな―307―

図 3 提案手法の RREQ フェイズ

長坂康史・金只圭司

3.3

RREP フェイズードへのネクストホップには，ネクストホップリストの先RREQ を受信したノードが RREP を返す条件は AODV頭に存在するノードを指定する。これらを含んだ Hello を，とほぼ同じである。しかし，提案手法では複数経路の保持HELLO̲INTERVAL[ms]間隔でブロードキャストする。

を許可するため，RREP を複数回返す場合がある。RREQ

Hello メッセージを受信したノードは次のチェックを行う。

を受信したノードが，RREP を返す条件は次の 2 通りであ（a）Hello 内の宛先ノードが自身であるる。

（b）Hello 内の宛先ノードへの経路を保持している（a）ノードが RREQ の宛先ノードである場合（a）の場合は，Hello を破棄する。（b）の場合，経路のネ（b）ノードが宛先ノードへの経路を保持している場合

クストホップリストに Hello 送信ノードが既に存在していどちらの場合も 3.2 節の処理によって逆経路を作成する。

れば，Rcost の情報と有効期限を更新し，存在していなけ次に，RREP の生成し，逆経路に送信する。このとき，（a）れば新たに追加する。このとき，Hello のネクストホップの場合は RREP のコスト値に宛先ノードの Ncost を付加

が Hello 受信ノードであれば，経路ループが発生するため，する。（b）の場合は，宛先への経路の中で最小の Rcost をその場合は更新を行わない。最後に，Hello 送信ノードをRREP に付加する。既に送信元ノードへの RREP を返しネクストホップとして保持していれば，その経路の有効期た後に，別の経路から RREQ を受信した場合には，保持限を延長する。

している経路のシーケンス番号は増加せず，RREQ 送信

この Hello によって最新の経路のコストが通知され，動ノードに RREP を返す。このとき，宛先ノードは RREQ的に最適経路を切り替えることが可能となる。

送信ノードを逆経路のネクストホップリストに追加する。

4. シミュレーション

次に RREP の配送処理について述べる。RREP を受信したノードは，RREQ 処理と同様に，宛先への経路を作

本研究では，提案手法の有効性についてシミュレーショ成する。既に宛先への経路を保持している場合は，以下のンを行い検証した。提案手法の比較対象は，提案手法の基3 つの場合に経路の更新処理を行う。となっている AODV とした。シミュレーションツールに（a）経路のシーケンス番号が無効は OPNET Modeler を使用した。本章では複数のネット（b）経路のシーケンス番号＜ RREP のシーケンス番号

ワーク環境においてシミュレーションを行い，その結果と（c）経路のシーケンス番号＝ RREP のシーケンス番号

考察を述べる。

（a），（b）の場合は経路のネクストホップリストを一度削

実際のノードのコストは 3.1 節の（1）式から算出する必除し，新たに前ホップをネクストホップリストに追加する。

要があるが，シミュレーション上では単純にコスト＝遅延（b）の場合は経路エントリを作成することなく，ネクスト時間とした。例えば，コストが 0.1 の場合，そのノードのホップリストの最後尾に RREQ を追加する。RREP の配遅延時間は 0.1 s となる。

送は逆経路のネクストホップすべてに行う。RREP 配送時

ノードは図 4 のように 10 台配置した。通信は各ノードには RREP に自身の Ncost を RREP のコスト値に加えて，が 1 s 間に 100 kb のデータをランダムに宛先ノードを選配送する。このようにして，RREP が送信元ノードまで配択し，データを送信する。各ノードは図の四角で囲まれた

送されれば，送信元ノードと宛先ノード間で双方向通信が範囲をランダムに移動する。シミュレーションは 100 s 間可能となる。

行った。シミュレーションでは，ネットワーク内に n 台のノードが高負荷状態（遅延が大きい状態）であるときの，3.4

Hello

到達データ量を AODV と提案手法で比較する。高負荷状

Hello は，TTL が 1 の RREP をブロードキャストする態のノードは，コスト 0.1（遅延 0.1 s）の場合と 0.3（遅ものである。AODV では自身のノードが通信範囲内に存

延 0.3 s）の場合の 2 通りでシミュレーションを行った。

在していることを，HELLO̲INTERVAL[ms]ごとに通知する。提案手法では AODV とは異なり，経路情報の交換に利用する。AODV における HELLO̲INTERVAL のデフォルトは，1000 ms となっている。
Hello は，ノードが保持しているすべての有効な経路について行う。Hello によって通知される内容は，ノードが保持している宛先ノードアドレス，その宛先ノードへのネクストホップと Rcost である。このとき，ノードの宛先ノ―308―

アドホックネットワークにおけるノード負荷を考慮した高効率ルーティング手法に関する研究

図 4 シミュレーションのノード配置
図 6 シミュレーション結果（cost = 0.3）

4.1

結果

高負荷ノードのコストが 0.1 のときのシミュレーション

4.2

考察の結果を図 5 に示す。グラフは，横軸に高負荷ノード数を

図 5 から，コストが 0.1 で高負荷ノードが 4 〜 6 台の場とり，縦軸に宛先ノードへの到達データ量［bps］をとる。

合において，AODV より提案手法の到達データ量が多い。

高負荷ノード数が 0 とは，ネットワーク内に高負荷（コスしかし，誤差を考えるとばらつきが大きくあまり安定してト 0.1）ノードが存在しない場合である。これを 1 から 10いるとはいえない。従って，コスト 0.1 の場合では提案手台まで増加させていった。ノードの移動によるリンク切断法と AODV ではほとんど差はないといえる。

やコストによる通信遅延を考慮しなければ，10 台のノード

図 6 から，コストが 0.3 で高負荷ノードが 3 〜 8 台の場が 1 s 間に 100kb のデータを送信するため，1 Mbps のデ合において，AODV より提案手法の到達データ量が多い。

ータが全宛先ノードに到達する。高負荷ノードは 10 台の特に高負荷ノードが 4 〜 6 台存在する場合には，ばらつきうち，node1 から順に選択した。例えば，高負荷ノード数は大きいものの，AODV より有効である可能性が高い。

が 3 台のときは，node1，node2，node3 がコストを持つ。

以上の結果から，AODV において高負荷ノードを経路として選択する確率が高く，提案手法において高負荷ノードを経路とすることを避けることが可能な確率が高い場合に，提案手法が AODV に比べ有効である可能性が高いと考えられる。

5. まとめ本研究では，アドホックネットワークにおいて各ノードの負荷を考慮することで既存のプロトコルである AODVに改良を加え，新たな手法を提案した。提案手法では，ノードをコストと称し，コストを各経路制御メッセージ内に組み込んだ。これにより，通信ノードはその時点で最もコ
図 5 シミュレーション結果（cost = 0.1）

ストの少ない経路選択し効率的にデータを送信することができる。

次に高負荷ノードのコストが 0.3 のときのシミュレーシ

提案手法をシミュレーションにより評価した。シミュレ

ョン結果を図 6 に示す。先述の場合との違いは高負荷ノーーションでは，ノードが移動する環境において AODV とドの遅延時間が 0.3 s であるということである。の比較を行った。その結果，ネットワーク内に高負荷ノードが 10 台中 4 〜 6 台存在する場合において，提案手法はAODV より有効である可能性が高いことを示した。
提案手法はより多角的な視点からシミュレーション評価されるべきである。また，実際に CPU 使用率とメモリ使用率からコストを算出し，そのコストが実際にどれほどの遅延時間を発生させるのかを知る必要がある。今後これらのことを踏まえ，提案手法の改善を行う必要があると考え―309―

長坂康史・金只圭司

られる。

参考文献
［1］C.Perkins “Ad hoc On-Demand Distance Vector(AODV) Routing” draft-ietf-aodv-13. txt, 2003
［2］金只圭司，長坂康史

アドホックネットワークにおけるノード負荷を考慮した高効率ルーティング手法の提案 ，FIT2007 第 6 回情報科学技術フォーラム，2007―310―