JP2008135914A - 経路制御方法および通信ノード - Google Patents

Abstract

【課題】アプリケーションの特性に応じて最適な経路を構築する。
【解決手段】送信ノード１１は、パケットの宛先に該当する経路エントリが存在しない場合に、転送ノードと転送リンクの転送コストであるメトリックを計算する際のメトリック計算重み情報と、メトリックとを含む経路要求メッセージを作成して、隣接ノードに送信する。中継ノードは、、経路要求メッセージに含まれるメトリックを基に最良の経路要求を選択し、選択結果に従って経路要求メッセージを更新し、更新後の経路要求メッセージを隣接ノードに送信する。宛先ノード１２は、経路要求メッセージに含まれるメトリックを基に最良の経路要求を選択する経路要求受信手順と、メトリック計算重み情報は、送信ノード１１のアプリケーション毎に設定される。
【選択図】 図１

Description

本発明は、無線マルチホップネットワークに係り、特にアプリケーション毎に適した経路を動的に探索して構築することができるアプリケーション適応型の経路制御方法および通信ノードに関するものである。

従来、無線ネットワークでは、ノード同士が無線により直接通信するだけでなく、自らの無線信号が届く通信範囲内に存在する他のノードを中継ノードとして経由することで、その無線通信範囲を超えて通信ノード間でデータを送受信することを可能とする無線マルチホップネットワークが知られている。

この無線マルチホップネットワークは、複数の通信ノードで構成されており、各通信ノードは自分宛でないパケットを転送するためのパケット転送機能を持っている。このパケット転送機能により各ノードは、直接無線の届かない宛先ノードに対して中継ノードを介することによりパケットを届けることができる。無線マルチホップネットワークでは、パケットの送受信及び転送を行う通信ノードは頻繁に移動し、それに伴い各通信ノード間の無線到達可否（直接通信できるかどうか）が変化し、宛先ノードまでパケットを伝達するための転送経路も頻繁に変化する。

このパケット転送経路を自律分散的に制御するルーティングプロトコルとしては、通信開始時に経路を探索するリアクティブ型プロトコルや、定期的に他の通信ノードとメッセージを交換して常時最新経路を維持するプロアクティブ型プロトコル等が採用されている。代表的なリアクティブ型ルーティングプロトコルについては、非特許文献１〜非特許文献５などで開示されている。これらのルーティングプロトコルは、送信ノードから宛先ノードまでの最善経路をホップ数（転送するノードの数）で決定する。しかし現実には、ホップ数の短い経路が必ずしも良い経路とは限らない。無線では、ノード間の距離や障害物、隣接ノードとの干渉、移動など通信を阻害する様々な要因が存在するためである。

非特許文献３では、通信ノード間の無線受信強度を測定し、受信強度の強いノード間で転送を行う経路を構築することにより、通信品質を高める方式が開示されている。
非特許文献４では、ノードの相対速度から通信可能時間を推定することにより、最も通信可能時間が長い転送経路を構築する方式が開示されている。
非特許文献５では、自ノードが保持する経路数を考慮することにより、通信が集中するノードを回避して経路を構築する方式が開示されている。
また、特許文献１では、非特許文献３〜非特許文献５の方式で開示されるメトリック（判断基準）及びその他のメトリックを統合したＱｏＳメトリックを採用することにより、無線マルチホップネットワークの特性を複合的に判断して最善の経路を構築する方式が開示されている。

特開２００４−５６７８７号公報 C.Perkins et al.，"Ad hoc On-Demand Distance Vector (AODV) Routing"，IETF RFC3561，2003 David B.Jhonson et al.，"The Dynamic Source Routing Protocol for Mobile Ad hoc Networks (DSR)"，IETF draft-ietf-manet-dsr-09.txt，2003 R.Dube et al.，"Signal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks"，Proc. Of ACM/IEEE MobiCom'98，1999 W.Su et al.，"IPv6 FLOW HANDOFF IN AD HOC WIRELESS NETWORKS USING MOBILITY PREDICTION"，Proc. Of IEEE GlobeCom'99，1999 H.Hassanein et al.，"Routing with Load Balancing in Wireless Ad hoc Networks"，Proc. Of MSWiM，2001

特許文献１及び非特許文献１〜非特許文献５に開示された従来の方式では、無線マルチホップネットワークにおいて、ホップカウントや信号強度、バッテリー残量、移動性（リンク寿命）、通信誤り率、帯域幅、経路数など様々なメトリック（判断基準）に基づき、最良の経路を構築することができる。これらの方式は全て事前に設定された方法でメトリックを計算する。そのため、どのアプリケーションが通信する場合でも、同じ経路が選択される。例えば、それほど長く通信を継続しないアプリケーションに対して経路の推定生存時間を基準に経路を選択したり、トラフィックの多くないアプリケーションに対してトラフィック集中度を基準に経路を選択するなど、不適切な経路選択が行われる。

現実にはアプリケーションの特性により、最適な経路は異なってくる。例えば、非常に小さいデータをすばやく届けたい場合は、経路の生存時間はそれほど問題ではなく、ホップカウントが小さい経路が最良である。音声通話のような、比較的長い時間しかも一定帯域を消費する通信では、経路生存時間が長く、帯域も空いていて遅延の少ない経路が良い経路となる。帯域と経路生存時間のどちらをどのくらい優先するかも、音声品質や通話時間などによって異なる。従来の方式では、こうしたアプリケーションの特性に応じたきめ細かな経路選択ができず、結果的にユーザにアプリケーション毎に高品質な通信を提供することができないという問題点があった。

本発明の目的は、無線マルチホップネットワークにおけるＥｎｄ−ｔｏ−Ｅｎｄの通信において、アプリケーションの特性に応じて最適な経路を構築し、ユーザに高品質な無線マルチホップ通信環境を提供することである。

本発明は、複数の通信ノード間で無線によりマルチホップネットワークを形成し、そのネットワーク内に経路要求メッセージをブロードキャスト送信して通信経路の探索を行う無線マルチホップネットワークの経路制御方法において、パケットの宛先に該当する経路エントリが存在しない場合に、転送ノードと転送リンクの転送コストであるメトリックを計算する際のメトリック計算重み情報と、前記メトリックとを含む経路要求メッセージを送信ノードが作成して、隣接ノードに送信する経路要求作成送信手順と、中継ノードが、受信した前記経路要求メッセージに含まれるメトリック計算重み情報を基にメトリックを計算するメトリック計算手順と、前記中継ノードが、前記経路要求メッセージに含まれるメトリックと前記メトリック計算手順で計算されたメトリックを基に最良の経路要求を選択し、選択結果にしたがって前記経路要求メッセージを更新し、更新後の経路要求メッセージを隣接ノードに送信する経路要求更新転送手順と、宛先ノードが、受信した前記経路要求メッセージに含まれるメトリックを基に最良の経路要求を選択する経路要求受信手順と、前記宛先ノードが、前記経路要求メッセージを最初に受信してから一定時間後に経路応答メッセージを隣接ノードに送信する経路応答作成送信手順と、前記宛先ノードが、前記選択した経路要求に基づいて経路エントリを作成して経路を設定する第１の経路設定手順と、前記中継ノードが、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第２の経路設定手順と、前記中継ノードが、受信した経路応答メッセージを隣接ノードに転送する経路応答転送手順と、前記送信ノードが、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第３の経路設定手順とを含むものである。

また、本発明の経路制御方法の１構成例において、前記メトリック計算重み情報は、前記送信ノードのアプリケーション毎に設定されるものである。
また、本発明の経路制御方法の１構成例において、前記送信ノードのアプリケーションは、通信に先立ち、自身に最適な前記メトリック計算重み情報を設定するものである。
また、本発明の経路制御方法の１構成例において、前記メトリックは、経路上のノードメトリック合計値と、経路上のリンクメトリック合計値と、最悪ノードメトリックと、最悪リンクメトリックとを含むものである。
また、本発明の経路制御方法の１構成例は、前記中継ノード及び宛先ノードが、メトリックの良い順に複数個の前記経路要求メッセージを保持し、前記宛先ノードが複数の前記経路応答メッセージを送信することにより、複数の経路を構築するようにしたものである。
また、本発明の経路制御方法の１構成例において、前記送信ノード及び中継ノードは、パケットの宛先アドレス、上位プロトコル及び宛先ポートに基づいてパケット転送を行うものである。
また、本発明の経路制御方法の１構成例において、前記送信ノード及び中継ノードは、前記経路エントリに上位プロトコル及び宛先ポートが登録されていない場合、宛先アドレスのみに基づいてパケットの転送を行うものである。
また、本発明の経路制御方法の１構成例において、前記経路要求メッセージは、前記一定時間を指定するタイムアップ時間の情報を含むものである。

また、本発明の通信ノードは、送信ノードである場合に、パケットの宛先に該当する経路エントリが存在しないとき、転送ノードと転送リンクの転送コストであるメトリックを計算する際のメトリック計算重み情報と、前記メトリックとを含む経路要求メッセージを作成して、隣接ノードに送信する経路要求作成送信手段と、中継ノードである場合に、受信した前記経路要求メッセージに含まれるメトリックを基に最良の経路要求を選択し、選択結果に従って前記経路要求メッセージを更新し、更新後の経路要求メッセージを隣接ノードに送信する経路要求更新転送手段と、宛先ノードである場合に、受信した前記経路要求メッセージに含まれるメトリックを基に最良の経路要求を選択する経路要求受信手段と、前記宛先ノードである場合に、前記経路要求メッセージを最初に受信してから一定時間後に経路応答メッセージを隣接ノードに送信する経路応答作成送信手段と、前記宛先ノードである場合に、前記選択した経路要求に基づいて経路エントリを作成して経路を設定する第１の経路設定手段と、前記中継ノードである場合に、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第２の経路設定手段と、前記中継ノードである場合に、受信した経路応答メッセージを隣接ノードに転送する経路応答転送手段と、前記送信ノードである場合に、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第３の経路設定手段とを有するものである。

また、本発明の通信ノードの１構成例において、前記メトリック計算重み情報は、前記送信ノードのアプリケーション毎に設定されるものである。
また、本発明の通信ノードの１構成例において、前記送信ノードのアプリケーションは、通信に先立ち、自身に最適な前記メトリック計算重み情報を設定するものである。
また、本発明の通信ノードの１構成例において、前記経路要求メッセージは、前記一定時間を指定するタイムアップ時間の情報を含むものである。

本発明によれば、リアクティブ型経路制御方式で制御された無線マルチホップネットワークにおいて、経路要求メッセージにメトリック計算重み情報および経路メトリック情報を格納することにより、アプリケーションに適した経路を構築し、高品質な通信を実現することができる。

また、本発明では、送信ノードのアプリケーションが、通信に先立ち、自身に最適なメトリック計算重み情報を設定できるようにすることにより、アプリケーションの特性に最適な経路を構築することができる。

また、本発明では、宛先ノードが経路要求メッセージを最初に受信してから経路応答メッセージを隣接ノードに送信するまでのタイムアップ時間の情報を経路要求メッセージに設定することにより、送信ノードは、すぐに構築したい経路か、少し時間をかけても良い経路を探索したいのかを明示的に宛先ノードに伝えることができる。

［第１の実施の形態］
以下、本発明に係る無線マルチホップネットワークの経路制御方式の最良の形態について、添付図面を参照して説明する。ここでは、非特許文献１で開示されているＡＯＤＶ（Ad hoc On-Demand Distance Vector）を元に本発明の方式を拡張するとして説明する。
図１は、本発明の第１の実施の形態に係る無線マルチホップネットワークの構成例を示すブロック図である。本実施の形態の無線マルチホップネットワークは、複数の通信ノード１１〜１７から構成されている。図１の例では、通信ノード１１を送信ノード、通信ノード１２を宛先ノードとして記載している。

図２は、各通信ノード１１〜１７の内部構成例を示すブロック図である。各通信ノード１１〜１７は、パケット転送経路を確立する経路制御部３１と、データの送受信を行うアプリケーション３２と、アプリケーション３２および経路制御部３１が生成したデータ、経路要求メッセージ、経路応答メッセージ等をＩＰパケットとして送受信または転送するＩＰ通信部３３と、アプリケーション３２に最適なメトリック計算重み情報４５を格納するメトリック計算重みテーブル３４と、送受信又は転送するＩＰパケットの転送経路を記録したＩＰ経路テーブル３５と、経路要求メッセージを一時的に記録するための経路要求キャッシュ３６と、経路構築が完了するまでの間、アプリケーション３２からのデータパケットを一時的に保管するためのパケットバッファ３７とを有する。

経路制御部３１及びＩＰ通信部３３は、経路要求作成送信手段と、経路要求更新転送手段と、経路要求受信手段と、経路応答作成送信手段と、経路設定手段と、経路応答転送手段とを構成している。
なお、図２では、通信ノード１１についてのみ内部構成を示しているが、他の通信ノード１２〜１７も内部構成は同一である。

次に、本実施の形態の無線マルチホップネットワークの動作を説明する。ここでは、図１の送信ノード１１上で動作するアプリケーション３２がデータを送信しようとした場合について説明する。図３は送信ノードの動作を示すフローチャートである。

送信ノード１１上で動作するアプリケーション３２がデータを送信しようとした場合、この送信しようとするデータ（送受信データ４４）を経路制御部３１が受け取る（図３ステップＳ１００）。経路制御部３１は、受信した送受信データ４４の宛先アドレスと宛先ポートに基づいてＩＰ経路テーブル３５を検索する。アプリケーション３２が宛先アドレス及び宛先ポートに該当する相手に初めて通信を行う場合、ＩＰ経路テーブル３５にはその宛先アドレス及び宛先ポートに該当する経路情報が存在しない。経路制御部３１は、ＩＰ経路テーブル３５に該当するＩＰ経路エントリが存在しない場合（ステップＳ１０１において判定ＮＯ）、アプリケーション３２から受信した送受信データ４４をパケットバッファ３７に格納し（ステップＳ１０２）、経路の構築を開始する。

経路制御部３１は、まず自ノードのメトリック計算重みテーブル３４から該アプリケーション３２のメトリック計算重み情報４５を取得する（ステップＳ１０３）。メトリック計算重みテーブル３４には、あらかじめアプリケーション３２の特性に合わせた標準的なメトリック計算重み情報４５が格納されている。また、アプリケーション３２は、通信に先立ち適切なメトリック計算重み情報４５を設定することが可能である。図４にメトリック計算重みテーブル３４の構成例を示す。メトリック計算重み情報４５は、アプリケーション３２のトランスポート層プロトコルの情報と、宛先ポート番号と、送信ポート番号と、メトリック計算重みＷ１〜ＷＮとを含んでいる。

メトリック計算重みＷ１〜ＷＮを使って計算されるメトリックには、ノードメトリックとリンクメトリックの２種類が存在する。
ノードメトリックは、通信ノードがパケットの転送を行う際のコストを表す値であり、値が大きいほど転送コストが高いことを意味する。ノードメトリックＭｎは、例えば以下のように計算される。
Ｍｎ＝Ｍｎｂ＋Ｗ１×Ｔｒ＋Ｗ２×（Ｅｍａｘ−Ｅ）／Ｅｍａｘ＋Ｗ３×Ｖ／Ｖｍａｘ
・・・（１）

式（１）において、Ｍｎｂは基本ノードメトリックであり、通信ノードの種類などによって決まる基本値である。例えばアンテナや車載ルータなど能力の高い通信ノードでは、基本ノードメトリックＭｎｂが小さい値に設定され、携帯電話機やＰＤＡ（Personal Digital Assistant）など能力の低い通信ノードでは、基本ノードメトリックＭｎｂが大きい値に設定される。Ｖｍａｘは、全ノードで想定される最大移動速度である。

Ｗ１はパケット転送処理負荷に対するメトリック計算重みであり、Ｔｒは通信ノードが持つ有効な経路数である。なお、Ｔｒは平均送信キュー長など、通信ノードのパケット転送処理負荷を表す他の値でも良い。
Ｗ２はバッテリー残量に対するメトリック計算重みである。Ｅｍａｘは通信ノードのバッテリーの最大容量であり、Ｅは通信ノードのバッテリーの残量である。
Ｗ３は通信ノードの移動速度に対するメトリック計算重みであり、Ｖは通信ノードの移動速度である。

リンクメトリックは、２台の通信ノード間でパケットを転送する際のコストを表す値であり、値が大きいほどノード間でのパケット転送コストが高いことを意味する。リンクメトリックＭｌは、例えば以下のように計算される。
Ｍｌ＝Ｍｌｂ＋Ｗ４×（Ｑｍａｘ−Ｑ）／Ｑｍａｘ
＋Ｗ５×（Ｒｍａｘ−Ｒ）／Ｒｍａｘ ・・・（２）

式（２）において、Ｍｌｂは基本リンクメトリックであり、その値は通常は１に設定されている。
Ｗ４はリンク品質に対するメトリック計算重みである。Ｑｍａｘは品質情報最大値（固定値）であり、Ｑはノード間の信号受信強度である。なお、ＱはＳ／Ｎ比、エラーレートなどリンクの品質を表す他の値でも良い。Ｑｍａｘとしては、Ｑに対応する品質が取り得る最良の値が設定される。

Ｗ５は２つの通信ノード間の相対速度に対するメトリック計算重みである。Ｒｍａｘは２つの通信ノード間で発生し得る推定最大相対速度、または２つの通信ノード間のリンクの推定最大生存時間（固定値）であり、Ｒは２つの通信ノード間の相対速度、または相対速度から計算したリンクの生存時間である。

経路制御部３１は、アプリケーション３２が送信しようとする宛先ノードのＩＰアドレスとポート番号、アプリケーション３２が使用するプロトコル（例えばＴＣＰ（Transmission Control Protocol）、ＵＤＰ（User Datagram Protocol）等）、送信ノードのアドレスと送信ポート番号、メトリック計算重みテーブル３４から取得したメトリック計算重み情報４５、ＧＰＳ（Global Positioning Systems）等から取得した自ノードの位置情報、センサーから取得した自ノードの速度ベクトル情報等から、経路要求メッセージ４２を作成する（ステップＳ１０４）。

図５に、経路要求メッセージ４２の構成を示す。図５の上部の０，１，２・・・・９，０，１，２・・・・はビットを表している。経路要求メッセージ４２の先頭のＴｙｐｅフィールドからＯｒｉｇｉｎａｔｏｒ Ｓｅｑｕｅｎｃｅ Ｎｕｍｂｅｒフィールドまでは、ＡＯＤＶと同様である。すなわち、Ｔｙｐｅフィールドには必ず１が入る。Ｈｏｐ Ｃｏｕｎｔは送信元から何回転送されたかを表わすホップ数である。Ｒｅｑｕｅｓｔ ＩＤには、自ノードが最後に送信した経路要求メッセージ４２で利用したＲｅｑｕｅｓｔ ＩＤに１つ加えた値が設定される。

Ｄｅｓｔｉｎａｔｉｏｎ ＩＰ Ａｄｄｒｅｓｓは宛先ノードのＩＰアドレス、Ｄｅｓｔｉｎａｔｉｏｎ Ｓｅｑｕｅｎｃｅ Ｎｕｍｂｅｒは宛先シーケンス番号である。宛先シーケンス番号には、その宛先について最後に知ったシーケンス番号が設定される。
Ｏｒｉｇｉｎａｔｏｒ ＩＰ Ａｄｄｒｅｓｓは送信ノードのＩＰアドレスである。Ｏｒｉｇｉｎａｔｏｒ Ｓｅｑｕｅｎｃｅ Ｎｕｍｂｅｒは送信者シーケンス番号であり、自ノードのシーケンス番号が設定される。このとき、経路制御部３１は、経路要求メッセージ４２を作成する直前に自ノードの送信者シーケンス番号を増加させる。

本実施の形態では、さらに次のフィールドを経路要求メッセージ４２に加える。Ａｐｐｌｉｃａｔｉｏｎ Ｐｒｏｔｏｃｏｌ Ｎｏ．はアプリケーション３２のトランスポート層プロトコル（上位プロトコル ＵＤＰ、ＴＣＰ他）を識別する番号、Ｄｅｓｔｉｎａｔｉｏｎ Ｐｏｒｔ Ｎｏ．はパケットの宛先ポート番号、Ｏｒｉｇｉｎａｔｏｒ Ｐｏｒｔ Ｎｏ．はパケットの送信ポート番号である。

Ｐｏｓｉｔｉｏｎ ＩｎｆｏｒｍａｔｉｏｎはＧＰＳなどから取得した自ノードの位置情報、Ｖｅｌｏｃｉｔｙ Ｉｎｆｏｒｍａｔｉｏｎは加速度センサーやジャイロセンサー等から計算された自ノードの速度ベクトル情報である。
Ｓｕｍ ｏｆ ｎｏｄｅ ｍｅｔｒｉｃは経路要求メッセージ４２が辿った経路におけるノードメトリックの合計値、Ｓｕｍ ｏｆ ｌｉｎｋ ｍｅｔｒｉｃは経路要求メッセージ４２が辿った経路におけるリンクメトリックの合計値、Ｗｏｒｓｔ ｎｏｄｅ ｍｅｔｒｉｃは経路要求メッセージ４２が辿った経路における最悪ノードメトリック値、Ｗｏｒｓｔ ｌｉｎｋ ｍｅｔｒｉｃは経路要求メッセージ４２が辿った経路における最悪リンクメトリック値である。

Ｗｅｉｇｈｔ ＃はメトリック計算重みの数、Ｗｅｉｇｈｔ Ｔｙｐｅ（ｘ）はｘ（ｘは任意の値）番目のメトリック計算重みの種類、Ｗｅｉｇｈｔ Ｖａｌｕｅ（ｘ）はｘ番目のメトリック計算重みの値である。このＷｅｉｇｈｔ Ｖａｌｕｅ（ｘ）にメトリック計算重みテーブル３４から取得したメトリック計算重みが設定される。値が０であるメトリック計算重みは省略することもできる。
送信ノード１１の場合、経路制御部３１は、Ｓｕｍ ｏｆ ｎｏｄｅ ｍｅｔｒｉｃ，Ｓｕｍ ｏｆ ｌｉｎｋ ｍｅｔｒｉｃ，ｗｏｒｓｔ ｎｏｄｅ ｍｅｔｒｉｃ，ｗｏｒｓｔ ｌｉｎｋ ｍｅｔｒｉｃフィールドには０をセットする。

経路制御部３１は、作成した経路要求メッセージ４２をＩＰ通信部３３に渡す。ＩＰ通信部３３は、経路要求メッセージ４２を隣接する（すなわち、中継なしで通信可能な）通信ノードにブロードキャスト送信する（ステップＳ１０５）。
なお、後述の宛先ノードがセットする経路応答タイマーのタイムアップ時間を経路要求メッセージに含めることも可能である。それにより、送信ノードのアプリケーション３２は、すぐに構築したい経路か、少し時間をかけても良い経路を探索したいのかを明示的に宛先ノードに伝えることができる。

図６は中継ノードの動作を示すフローチャートである。中継ノードの経路制御部３１は、隣接ノードから経路要求メッセージ４２を受信すると（図６ステップＳ２００において判定ＹＥＳ）、受信した経路要求メッセージ４２に含まれるメトリック計算重み情報と、基本リンクメトリックＭｌｂ、品質情報最大値Ｑｍａｘ、ノード間の品質を表す値Ｑ、ノード間の推定最大相対速度Ｒｍａｘ、及び相対速度Ｒとを用いて、経路要求メッセージ４２の転送元である隣接ノードとの間のリンクメトリックを計算する（ステップＳ２０１）。

続いて、経路制御部３１は、受信した経路要求メッセージ４２と宛先ノードアドレス、宛先ポート番号、送信ノードアドレス、送信ポート番号、及びプロトコルの組が一致する経路要求エントリがあるかどうかを経路要求キャッシュ３６から検索する（ステップＳ２０２）。

図７に経路要求キャッシュ３６の構成例を示す。経路要求キャッシュ３６に格納された経路要求エントリは、宛先ノードアドレスと、プロトコルを識別する情報と、宛先ポート番号と、宛先シーケンス番号と、送信ノードアドレスと、送信ポート番号と、送信者シーケンス番号と、隣接ノードアドレスと、受信ＩＦ（インタフェース）番号と、ノードメトリックの合計値と、リンクメトリックの合計値と、最悪ノードメトリックと、最悪リンクメトリックと、ホップ数と、リンクの有効時間の情報を含んでいる。

経路要求キャッシュ３６に該当する経路要求エントリが無い場合、中継通信ノードの経路制御部３１は、以下の処理を行う。
まず、経路制御部３１は、経路要求メッセージ４２に対応する経路要求エントリを経路要求キャッシュ３６に新たに追加する（ステップＳ２０３）。このとき、経路制御部３１は、経路要求メッセージ４２のノードメトリック合計値を経路要求エントリのノードメトリック合計値とし、経路要求メッセージ４２のリンクメトリック合計値に、ステップＳ２０１で計算したリンクメトリックを加算した値を経路要求エントリのリンクメトリック合計値とする。また、経路制御部３１は、経路要求メッセージ４２の最悪ノードメトリックを経路要求エントリの最悪ノードメトリックとし、経路要求メッセージ４２の最悪リンクメトリックとステップＳ２０１で計算したリンクメトリックを比較して、大きい方の値を経路要求エントリの最悪リンクメトリックとする。

続いて、経路制御部３１は、経路要求メッセージ４２を更新する（ステップＳ２０４）。このとき、経路制御部３１は、受信した経路要求メッセージ４２のホップ数、Ｒｅｑｕｅｓｔ ＩＤにそれぞれ１加算する。また、経路制御部３１は、受信した経路要求メッセージ４２に含まれるメトリック計算重み情報と、自ノードの基本ノードメトリックＭｎｂ、パケット転送処理負荷を表す値Ｔｒ、バッテリーの最大容量Ｅｍａｘ、バッテリーの残量Ｅ、及び移動速度Ｖを用いて、自ノードのノードメトリックを計算し、受信した経路要求メッセージ４２のノードメトリック合計値に、計算したノードメトリックを加算した値を更新後の経路要求メッセージ４２のノードメトリック合計値とする。

また、経路制御部３１は、受信した経路要求メッセージ４２のリンクメトリック合計値に、ステップＳ２０１で計算したリンクメトリックを加算した値を更新後の経路要求メッセージ４２のリンクメトリック合計値とする。さらに、経路制御部３１は、受信した経路要求メッセージ４２の最悪ノードメトリックと計算したノードメトリックとを比較して、大きい方の値を更新後の経路要求メッセージ４２の最悪ノードメトリックとし、受信した経路要求メッセージ４２の最悪リンクメトリックと計算したリンクメトリックとを比較して、大きい方の値を更新後の経路要求メッセージ４２の最悪リンクメトリックとする。

次に、経路制御部３１は、更新した経路要求メッセージ４２をＩＰ通信部３３に渡す。ＩＰ通信部３３は、経路要求メッセージ４２を隣接する通信ノードにブロードキャスト送信する（ステップＳ２０５）。

一方、経路要求キャッシュ３６に該当する経路要求エントリが既に存在する場合、中継通信ノードの経路制御部３１は、以下の処理を行う。
まず、経路制御部３１は、経路要求キャッシュ３６の該当する経路要求エントリと受信した経路要求メッセージ４２とを比較する（ステップＳ２０６）。この比較方法については後述する。
経路制御部３１は、既存の経路要求エントリの方が良い場合は、経路要求メッセージ４２を破棄し（ステップＳ２０７）、ステップＳ２００に戻る。

また、経路制御部３１は、経路要求メッセージ４２の方が良い場合は、該当する経路要求エントリを更新し（ステップＳ２０８）、ステップＳ２０４に進む。ステップＳ２０８において、経路制御部３１は、経路要求メッセージ４２のノードメトリック合計値を経路要求エントリのノードメトリック合計値とし、経路要求メッセージ４２のリンクメトリック合計値に、ステップＳ２０１で計算したリンクメトリックを加算した値を経路要求エントリのリンクメトリック合計値とする。また、経路制御部３１は、経路要求メッセージ４２の最悪ノードメトリックを経路要求エントリの最悪ノードメトリックとし、経路要求メッセージ４２の最悪リンクメトリックとステップＳ２０１で計算したリンクメトリックを比較して、大きい方の値を経路要求エントリの最悪リンクメトリックとする。

次に、経路要求メッセージ４２と経路要求キャッシュ３６の経路要求エントリの比較方法について説明する。経路要求の比較は、以下の（ａ）〜（ｈ）の経路要求比較ルールの順位で条件を比較して行い、経路要求メッセージ４２と経路要求エントリのうち一方の経路要求を優先すべきと判断できた時点で、比較を終了する。

（ａ）まず、経路要求メッセージ４２と経路要求エントリを比較したときに、ノードメトリック合計値とリンクメトリック合計値が共に良い経路要求が存在するならば、合計値が良い方の経路要求を優先する。
メトリック値の優劣比較は、値が小さい方が良いと判断する。ただし、ノードメトリック合計値とリンクメトリック合計値は値が大きいため、経路要求メッセージ４２の合計値と経路要求エントリの合計値の双方の平均値から±５％以内であれば、同じ値とみなす。例えば経路要求メッセージ４２のノードメトリック合計値が１００００で、経路要求エントリのノードメトリック合計値が１０５００である場合、双方の平均値は１０２５０であるから、許容誤差は１０２５０×０．０５＝５１２．５である。経路要求メッセージ４２のノードメトリック合計値と経路要求エントリのノードメトリック合計値はいずれも１０２５０±５１２．５の範囲内であるため、両数値は等しいと判断される。

（ｂ）ノードメトリック合計値とリンクメトリック合計値のうちどちらか一方の合計値が良い経路要求が存在し、かつもう一方の合計値が経路要求メッセージ４２と経路要求エントリで同じ場合、合計値が良い方の経路要求を優先する。
（ｃ）ノードメトリック合計値とリンクメトリック合計値のうちどちらか一方の合計値が良い経路要求が存在し、かつこの経路要求でもう一方の合計値が悪い場合、経路要求メッセージ４２と経路要求エントリで差が大きい方の合計値の比較結果を優先する。例えば、経路要求メッセージ４２のノードメトリック合計値が１００００、経路要求エントリのノードメトリック合計値が９０００、経路要求メッセージ４２のリンクメトリック合計値が９０００で、経路要求エントリのリンクメトリック合計値が１１０００であった場合、経路要求メッセージ４２と経路要求エントリでノードメトリック合計値の差は１０００、リンクメトリック合計値の差は２０００なので、リンクメトリック合計値の比較結果が優先される。ここでは、経路要求メッセージ４２の方がリンクメトリック合計値が良いので、経路要求メッセージ４２を優先すべきと判断される。

（ｄ）経路要求メッセージ４２と経路要求エントリを比較したときに、最悪ノードメトリック値と最悪リンクメトリック値が共に良い経路要求が存在するならば、最悪値が良い方の経路要求を優先する。
（ｅ）最悪ノードメトリック値と最悪リンクメトリック値のうちどちらか一方の最悪値が良い経路要求が存在し、かつもう一方の最悪値が経路要求メッセージ４２と経路要求エントリで同じ場合、最悪値が良い方の経路要求を優先する。
（ｆ）最悪ノードメトリック値と最悪リンクメトリック値のうちどちらか一方の最悪値が良い経路要求が存在し、かつこの経路要求でもう一方の最悪値が悪い場合、経路要求メッセージ４２と経路要求エントリで差が大きい方の最悪値の比較結果を優先する。
（ｇ）ホップ数の小さい経路要求を優先する。
（ｈ）早く受信した経路要求（すなわち、経路要求キャッシュ３６の経路要求エントリ）の方を優先する。

以上のようにして、経路要求メッセージ４２は、中継ノードを経由して転送される。
図８は宛先ノード１２の動作を示すフローチャートである。宛先ノード１２が経路要求メッセージ４２を受信すると（図８ステップＳ３００において判定ＹＥＳ）、宛先ノード１２の経路制御部３１は、上記中継通信ノードと同様に自ノードの経路要求キャッシュ３６を検索する（ステップＳ３０１）。
経路要求メッセージ４２に該当する経路要求エントリが経路要求キャッシュ３６に無い場合、宛先ノードの経路制御部３１は、以下の処理を行う。

まず、経路制御部３１は、受信した経路要求メッセージ４２に含まれるメトリック計算重み情報と、基本リンクメトリックＭｌｂ、品質情報最大値Ｑｍａｘ、ノード間の品質を表す値Ｑ、ノード間の推定最大相対速度Ｒｍａｘ、及び相対速度Ｒを用いて、経路要求メッセージ４２の転送元である隣接ノードとの間のリンクメトリックを計算する（ステップＳ３０２）。

続いて、経路制御部３１は、受信した経路要求メッセージ４２のリンクメトリック合計値に、計算したリンクメトリックを加算してリンクメトリック合計値を更新する。また、経路制御部３１は、経路要求メッセージ４２の最悪リンクメトリックよりも、計算したリンクメトリックが悪い（値が大きい）場合は、計算したリンクメトリックを最悪リンクメトリックとして更新する（ステップＳ３０３）。

経路制御部３１は、リンクメトリック合計値を更新すると共に必要に応じて最悪リンクメトリックを更新した後の経路要求メッセージ４２に基づいて、経路要求エントリを経路要求キャッシュ３６に新たに作成する（ステップＳ３０４）。そして、経路制御部３１は、一定時間後に経路応答メッセージを返すための経路応答タイマーをセットする（ステップＳ３０５）。

一方、経路要求キャッシュ３６に該当する経路要求エントリが既に存在する場合、宛先ノードの経路制御部３１は、以下の処理を行う。
まず、経路制御部３１は、ステップＳ３０２と同様にリンクメトリックを計算し（ステップＳ３０６）、ステップＳ３０３と同様に経路要求メッセージ４２のリンクメトリック合計値を更新すると共に、必要に応じて経路要求メッセージ４２の最悪リンクメトリックを更新する（ステップＳ３０７）。

続いて、経路制御部３１は、経路要求キャッシュ３６の該当する経路要求エントリと更新後の経路要求メッセージ４２とを比較する（ステップＳ３０８）。このときの比較方法は前述の通りである。
経路制御部３１は、既存の経路要求エントリの方が良い場合は、経路要求メッセージ４２を破棄する（ステップＳ３０９）。また、経路制御部３１は、更新後の経路要求メッセージ４２の方が良い場合は、この経路要求メッセージ４２に対応して、経路要求キャッシュ３６の該当する経路要求エントリも更新する（ステップＳ３１０）。

次に、宛先ノード１２の経路制御部３１は、経路応答タイマーをセットした時刻から一定のタイムアップ時間が経過した場合、経路応答メッセージ４３を作成する（ステップＳ３１１）。図９に、経路応答メッセージ４３の構成を示す。経路応答メッセージ４３の先頭のＴｙｐｅフィールドからＬｉｆｅＴｉｍｅフィールドまでは、ＡＯＤＶと同様である。すなわち、Ｔｙｐｅフィールドには２が入る。Ｈｏｐ Ｃｏｕｎｔフィールドには、ホップ数として０が格納される。

Ｄｅｓｔｉｎａｔｉｏｎ ＩＰ ＡｄｄｒｅｓｓとＯｒｉｇｉｎａｔｏｒ ＩＰ Ａｄｄｒｅｓｓフィールドには、受信した経路要求メッセージ４２からコピーした値がそのまま格納される。また、経路制御部３１は、経路応答メッセージ４３を作成する前に、自ノードのシーケンス番号が経路要求メッセージ４２に書かれている送信者シーケンス番号よりも小さい場合、自ノードのシーケンス番号を送信者シーケンス番号で書き換えた上で、このシーケンス番号をＤｅｓｔｉｎａｔｉｏｎ Ｓｅｑｕｅｎｃｅ Ｎｕｍｂｅｒフィールドに書き込む。Ｌｉｆｅｔｉｍｅは、隣接するノードとの間のリンクの生存時間である。Ａｐｐｌｉｃａｔｉｏｎ Ｐｒｏｔｏｃｏｌ Ｎｏ．、Ｄｅｓｔｉｎａｔｉｏｎ Ｐｏｒｔ Ｎｏ．、Ｏｒｉｇｉｎａｔｏｒ Ｐｏｒｔ Ｎｏ．フィールドには、経路要求メッセージ４２からコピーした値がそのまま格納される。

宛先ノード１２の経路制御部３１は、作成した経路応答メッセージ４３をＩＰ通信部３３に渡す。ＩＰ通信部３３は、経路応答メッセージ４３を経路要求キャッシュ３６の該当する経路要求エントリに登録された隣接ノードアドレス宛にユニキャストで送信する（ステップＳ３１２）。

同時に、経路制御部３１は、該当する経路要求エントリに基づいて、この経路要求エントリに登録された送信ノードアドレス及び送信ポート番号宛のＩＰ経路エントリを自ノードのＩＰ経路テーブル３５に作成する（ステップＳ３１３）。図１０にＩＰ経路テーブル３５の構成例を示す。ＩＰ経路エントリは、宛先ノードアドレス（経路要求エントリの送信ノードアドレス）と、プロトコルを識別する情報と、宛先ポート番号（経路要求エントリの送信ポート番号）と、隣接ノードアドレスと、送信ＩＦ番号と、ホップ数と、リンクの有効時間の情報を含んでいる。有効時間は、この経路が利用されなくなってから無効になるまでの時間を示し、あらかじめ設定された値となる。パケットの送受信、転送等に利用された経路エントリの有効時間は更新される。

なお、ＩＰ経路エントリにプロトコルと宛先ポート番号が登録されていない場合（すなわち、経路要求エントリにプロトコルと送信ポート番号が登録されていない場合）、経路制御部３１は、宛先アドレスのみをマッチさせて経路応答メッセージ４３の送信を行う。

次に、中継ノードの経路制御部３１は、経路応答メッセージ４３を受信すると（図６ステップＳ２０９において判定ＹＥＳ）、経路応答メッセージ４３に該当する経路要求エントリがあるかどうかを自ノードの経路要求キャッシュ３６から検索する（ステップＳ２１０）。経路制御部３１は、該当する経路要求エントリが存在する場合、この経路要求エントリに登録された宛先ノードアドレス及び宛先ポート番号宛のＩＰ経路エントリと、経路要求エントリに登録された送信ノードアドレス及び送信ポート番号宛のＩＰ経路エントリとを、自ノードのＩＰ経路テーブル３５に作成する（ステップＳ２１１）。

そして、中継ノードの経路制御部３１は、経路要求エントリに登録された隣接ノード宛に経路応答メッセージ４３を転送する（ステップＳ２１２）。なお、ＩＰ経路エントリにプロトコルと宛先ポート番号が登録されていない場合（すなわち、経路要求エントリにプロトコルと送信ポート番号が登録されていない場合）、経路制御部３１は、宛先アドレスのみをマッチさせて経路応答メッセージの転送を行う。

最後に、送信ノード１１の経路制御部３１は、経路応答メッセージ４３を受信すると（図３ステップＳ１０６において判定ＹＥＳ）、経路応答メッセージ４３に該当する経路要求エントリがあるかどうかを自ノードの経路要求キャッシュ３６から検索する（ステップＳ１０７）。経路制御部３１は、該当する経路要求エントリが存在する場合、この経路要求エントリに登録された宛先ノードアドレス及び宛先ポート番号宛のＩＰ経路エントリを自ノードのＩＰ経路テーブル３５に作成する（ステップＳ１０８）。

そして、送信ノード１１の経路制御部３１は、パケットバッファ３７に保管していたアプリケーションデータの転送を開始する（ステップＳ１０９）。このとき、アプリケーションデータは、ステップＳ１０８で作成されたＩＰ経路エントリに従って、隣接ノードアドレス宛に転送される。

次に、ＩＰ経路エントリ作成後の中継ノードの動作を図１１を用いて説明する。まず、中継ノードの経路制御部３１は、有効時間の切れたＩＰ経路エントリが存在するかどうかを判定する（ステップＳ４００）。経路制御部３１は、ＩＰ経路エントリの有効時間が切れていない場合に、アプリケーションデータを受信すると（ステップＳ４０１において判定ＹＥＳ）、このアプリケーションデータと宛先ノードアドレス、宛先ポート番号及びプロトコルの組が一致するＩＰ経路エントリがあるかどうかをＩＰ経路テーブル３５から検索する（ステップＳ４０２）。経路制御部３１は、該当するＩＰ経路エントリが存在する場合、このＩＰ経路エントリに登録された隣接ノードアドレス宛にアプリケーションデータを転送して（ステップＳ４０３）、ステップＳ４００に戻る。経路制御部３１は、該当するＩＰ経路エントリが存在しない場合、受信したアプリケーションデータを破棄して（ステップＳ４０４）、ステップＳ４００に戻る。

また、中継ノードの経路制御部３１は、ステップＳ４００において有効時間の切れたＩＰ経路エントリが存在すると判定した場合、この有効時間の切れたＩＰ経路エントリをＩＰ経路テーブル３５から削除する（ステップＳ４０５）。そして、経路制御部３１は、ＩＰ経路テーブル３５のＩＰ経路エントリ数が０になったかどうかを判定する。ＩＰ経路エントリ数が０でない場合はステップＳ４００に戻り、ＩＰ経路エントリ数が０の場合は、図１１の処理を終了する。

次に、図１２を用いて本実施の形態の実際の動作の例を説明する。送信ノード１１は、自ノードのアプリケーション３２のデータ送信に伴い、アプリケーション３２に応じたメトリック計算重み情報等を取得し、経路要求メッセージ５１をブロードキャスト送信する。経路要求メッセージ５１には、ホップ数１、宛先ノード１２のアドレス、宛先シーケンス番号３、プロトコルＴＣＰ、宛先ポート番号８０、送信ノード１１のアドレス、送信者シーケンス番号９、送信ポート番号４３３５、ノードメトリック合計値０、リンクメトリック合計値０、最悪ノードメトリック０、最悪リンクメトリック０、メトリック計算重みＷ１＝３０，Ｗ２＝４０，Ｗ３＝０，Ｗ４＝１０，Ｗ５＝３０、位置情報（Ｘ，Ｙ，Ｚ）、速度ベクトル情報（ｄＸ，ｄＹ，ｄＺ）が設定されている。

経路要求メッセージ５１は、中継ノード１３，１４がそれぞれ受信する。中継ノード１３，１４は、それぞれメッセージの受信強度や、自ノードの位置情報と速度、バッテリー残量、送信ノード１１との相対速度等を測定する。中継ノード１３，１４は、これらの測定した情報と、経路要求メッセージ５１に含まれるメトリック計算重み情報から、リンクメトリックとノードメトリックを計算する。図１２の例では、中継ノード１３のノードメトリックを１０、中継ノード１３と送信ノード１１間のリンクメトリックを２０、中継ノード１４のノードメトリックを４０、中継ノード１４と送信ノード１１間のリンクメトリックを１０とする。

中継ノード１３，１４は、それぞれ計算したリンクメトリック、ノードメトリックを経路要求メッセージ５１のノードメトリック合計値、リンクメトリック合計値に加算してノードメトリック合計値、リンクメトリック合計値を更新し、さらに必要に応じて経路要求メッセージ５１の最悪ノードメトリック、最悪リンクメトリックを更新する。そして、中継ノード１３，１４は、更新後の経路要求メッセージをそれぞれ経路要求メッセージ５３，５２としてブロードキャスト送信する。

図１２の例では、経路要求メッセージ５３のノードメトリック合計値が１０、リンクメトリック合計値が２０、最悪ノードメトリックが１０、最悪リンクメトリックが２０に更新されている。また、経路要求メッセージ５２のノードメトリック合計値が４０、リンクメトリック合計値が１０、最悪ノードメトリックが４０、最悪ノードメトリックが１０に更新されている。なお、経路要求メッセージを転送するノードとして中継ノード１３，１４が加わるため、経路要求メッセージ５２，５３のホップ数は２に更新される。

また、中継ノード１３は、経路要求エントリを自ノードの経路要求キャッシュ３６に登録する。この経路要求エントリには、宛先ノード１２のアドレス、プロトコルＴＣＰ、宛先ポート番号８０、宛先シーケンス番号３、送信ノード１１のアドレス、送信ポート番号４３３５、送信者シーケンス番号９、隣接ノード１１のアドレス、受信ＩＦ番号ＩＦ＃１、ノードメトリック合計値１０、リンクメトリック合計値２０、最悪ノードメトリック１０、最悪リンクメトリック２０、ホップ数１、リンクの有効時間３０秒が登録されている。

同様に、中継ノード１４は、経路要求エントリを自ノードの経路要求キャッシュ３６に登録する。この経路要求エントリには、宛先ノード１２のアドレス、プロトコルＴＣＰ、宛先ポート番号８０、宛先シーケンス番号３、送信ノード１１のアドレス、送信ポート番号４３３５、送信者シーケンス番号９、隣接ノード１１のアドレス、受信ＩＦ番号ＩＦ＃１、ノードメトリック合計値４０、リンクメトリック合計値１０、最悪ノードメトリック４０、最悪リンクメトリック１０、ホップ数１、リンクの有効時間３０秒が登録されている。

宛先ノード１２は、中継ノード１３から経路要求メッセージ５３を、中継ノード１４から経路要求メッセージ５２をそれぞれ受信する。宛先ノード１２は、中継ノード１３，１４から受信した経路要求メッセージ５３，５２を前述の比較方法に従って比較する。この場合、比較する経路要求は、以下の２つである。まず、経路要求メッセージ５３に基づく経路要求では、隣接ノードアドレスがノード１３のアドレス、ノードメトリック合計値が１０、リンクメトリック合計値が５０、最悪ノードメトリックが１０、最悪リンクメトリックが３０、ホップ数が２となっている。また、経路要求メッセージ５２に基づく経路要求では、隣接ノードアドレスがノード１４のアドレス、ノードメトリック合計値が４０、リンクメトリック合計値が３０、最悪ノードメトリックが４０、最悪リンクメトリックが２０、ホップ数が２となっている。ここでは、前述の経路要求比較ルール（ｃ）により、経路要求メッセージ５３に基づく経路要求の方が優先される。

なお、このときのリンクメトリック合計値と最悪リンクメトリックは、ステップＳ３０２，Ｓ３０３又はステップＳ３０６，Ｓ３０７の処理により更新されている。すなわち、経路要求メッセージ５３，５２のどちらか一方を先に受信すると、この経路要求メッセージがステップＳ３０２，Ｓ３０３の処理により更新されて経路要求エントリが作成され、次にもう一方の経路要求メッセージを受信すると、この経路要求メッセージがＳ３０６，Ｓ３０７の処理により更新されて経路要求エントリと比較される。

宛先ノード１２は、中継ノード１３に対して経路応答メッセージを作成して送信する。それと同時に、ＩＰ経路エントリを自ノードのＩＰ経路テーブル３５に登録する。このＩＰ経路エントリには、宛先ノードアドレスとしてノード１１のアドレス、ＮｅｘｔＨｏｐアドレスとしてノード１３のアドレスが登録され、またプロトコルＴＣＰ、宛先ポート番号４３３５、送信ＩＦ番号ＩＦ＃１、ホップ数２、有効時間３０秒が登録されている。

中継ノード１３は、宛先ノード１２から経路応答メッセージを受信すると、自ノードの経路要求キャッシュ３６から該当する経路要求エントリ、すなわち受信した経路応答メッセージと宛先ノードアドレス、宛先ポート番号、送信ノードアドレス、送信ポート番号、及びプロトコルの組が一致する経路要求エントリを検索して、自ノードのＩＰ経路テーブル３５にＩＰ経路エントリを作成し、検索した経路要求エントリに登録された隣接ノードであるノード１１宛に経路応答メッセージを転送する。

このとき、中継ノード１３は、ノード１１宛のＩＰ経路エントリとノード１２宛のＩＰ経路エントリを作成する。ノード１１宛のＩＰ経路エントリには、宛先ノードアドレス及びＮｅｘｔＨｏｐアドレスとしてノード１１のアドレスが登録され、またプロトコルＴＣＰ、宛先ポート番号４３３５、送信ＩＦ番号ＩＦ＃１、ホップ数１、有効時間３０秒が登録される。ノード１２宛のＩＰ経路エントリには、宛先ノードアドレス及びＮｅｘｔＨｏｐアドレスとしてノード１２のアドレスが登録され、またプロトコルＴＣＰ、宛先ポート番号８０、送信ＩＦ番号ＩＦ＃１、ホップ数１、有効時間３０秒が登録される。

送信ノード１１は、ノード１３から経路応答メッセージを受信すると、自ノードのＩＰ経路テーブル３５にＩＰ経路エントリを作成する。このＩＰ経路エントリには、宛先ノードアドレスとしてノード１２のアドレス、ＮｅｘｔＨｏｐアドレスとしてノード１３のアドレスが登録され、またプロトコルＴＣＰ、宛先ポート番号８０、送信ＩＦ番号ＩＦ＃１、ホップ数２、有効時間３０秒が登録される。そして、送信ノード１１は、パケットバッファ３７に保管されたパケット及びアプリケーション３２から受け取ったパケットの送信を開始する。

従来の無線マルチホップネットワークにおけるリアクティブ型経路制御方式では、あらかじめ決められた基準によってのみ経路を選択していた。従来の基準とは、ホップ数、信号強度、推定生存時間、トラフィック集中度、バッテリー残量またはそれらの複合基準である。しかし、固定的な選択基準では、アプリケーション毎に異なる特性に応じた経路の選択ができない。そのため、それほど長く通信を継続しないアプリケーションのための経路を推定生存時間を基準に選択したり、トラフィックの多くないアプリケーションの経路をトラフィック集中度を基準に選択するなど、不適切な経路構築が行われる。

本実施の形態では、経路要求メッセージに経路選択の基準となるメトリックを計算するためのメトリック計算重み情報を含め、アプリケーション毎にメトリック計算重み情報を設定することにより、アプリケーションの特性に応じた最適な経路の選択を可能とする。本実施の形態では、メトリック計算重みテーブル３４にメトリック計算重みがアプリケーション３２毎に登録されるので、異なるアプリケーション３２では異なるメトリック計算重みが利用される。そのため、各中継ノードで計算されるリンクメトリックとノードメトリックがアプリケーション毎に異なり、結果的に選択される経路も異なる場合が生じる。アプリケーション３２が最適なメトリック計算重みを通信に先立ちメトリック計算重みテーブル３４に登録しておくことで、アプリケーション３２は自身が望む評価基準で経路制御部３１に経路を構築させることができる。こうして、本実施の形態では、ユーザに対して快適な通信環境を提供することが可能となる。

［第２の実施の形態］
前述の第１の実施の形態では、中継ノードおよび宛先ノードは、最良の経路要求エントリのみを経路要求キャッシュ３６に保持していたが、同じ経路要求メッセージを異なる隣接ノードから複数個受け取った場合、それらのうちの上位Ｎ個までの経路要求エントリを経路要求キャッシュ３６に保持することも可能である。

この場合、宛先ノードは、経路応答タイマーをセットした時刻から一定のタイムアップ時間が経過したとき、自ノードの経路要求キャッシュ３６に保持された上位Ｎ個の経路要求エントリに登録された隣接ノードに対して経路応答メッセージを送信する。
中継ノードは、経路応答メッセージを受信すると、自ノードの経路要求キャッシュ３６から経路応答メッセージに該当する上位Ｎ個の経路要求エントリを検索し、このうち最良（最上位）の経路要求エントリを選択して、自ノードのＩＰ経路テーブル３５にＩＰ経路エントリを作成し、選択した経路要求エントリに登録された隣接ノードアドレス宛に経路応答メッセージを転送し、選択した経路要求エントリを削除する。

中継ノードは、同一経路に対する経路応答メッセージを複数受信した場合、経路応答メッセージに該当する経路要求エントリが存在する限り、最良の経路要求エントリを選択して、ＩＰ経路エントリを作成し、選択した経路要求エントリに登録された隣接ノードアドレス宛に経路応答メッセージを転送し、選択した経路要求エントリを削除する。中継ノードは、経路応答メッセージに該当する経路要求エントリが経路要求キャッシュ３６に無くなった場合は、経路応答メッセージを破棄する。なお、利用されない経路要求エントリは、一定時間後に自動的に破棄される。

また、非特許文献２に開示されたＤＳＲ（Dynamic Source Routing）をベースとして本発明を適用することも可能である。ＤＳＲの場合、経路要求メッセージにメッセージが辿った経路が格納されているため、宛先ノードは応答を返す経路を明示的に示すことができる。そのため、複数の応答を、重複しない経路に沿って返すことが可能である。

第１、第２の実施の形態の各通信ノードは、それぞれＣＰＵ、記憶装置および外部とのインタフェースを備えたコンピュータと、これらのハードウェア資源を制御するプログラムによって実現することができる。このようなコンピュータにおいて、本発明の経路制御方法を実現させるためのプログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、メモリカードなどの記録媒体に記録された状態で提供される。ＣＰＵは、記録媒体から読み込んだプログラムを記憶装置に書き込み、プログラムに従って前述の処理を実行する。

本発明は、無線マルチホップネットワークに適用することができる。

本発明の第１の実施の形態に係る無線マルチホップネットワークの構成例を示すブロック図である。 本発明の第１の実施の形態に係る無線マルチホップネットワークの通信ノードの内部構成例を示すブロック図である。 本発明の第１の実施の形態における送信ノードの動作を示すフローチャートである。 本発明の第１の実施の形態における通信ノードのメトリック計算重みテーブルの構成例を示す図である。 本発明の第１の実施の形態における経路要求メッセージの構成を示す図である。 本発明の第１の実施の形態における中継ノードの動作を示すフローチャートである。 本発明の第１の実施の形態における通信ノードの経路要求キャッシュの構成例を示す図である。 本発明の第１の実施の形態における宛先ノードの動作を示すフローチャートである。 本発明の第１の実施の形態における経路応答メッセージの構成を示す図である。 本発明の第１の実施の形態におけるＩＰ経路テーブルの構成例を示す図である。 本発明の第１の実施の形態におけるＩＰ経路エントリ作成後の中継ノードの動作を示すフローチャートである。 本発明の第１の実施の形態の動作例を説明する図である。

符号の説明

１１〜１７…通信ノード、３１…経路制御部、３２…アプリケーション、３３…ＩＰ通信部、３４…メトリック計算重みテーブル、３５…ＩＰ経路テーブル、３６…経路要求キャッシュ、３７…パケットバッファ。

Claims (12)

1. 複数の通信ノード間で無線によりマルチホップネットワークを形成し、そのネットワーク内に経路要求メッセージをブロードキャスト送信して通信経路の探索を行う無線マルチホップネットワークの経路制御方法において、
   パケットの宛先に該当する経路エントリが存在しない場合に、転送ノードと転送リンクの転送コストであるメトリックを計算する際のメトリック計算重み情報と、前記メトリックとを含む経路要求メッセージを送信ノードが作成して、隣接ノードに送信する経路要求作成送信手順と、
   中継ノードが、受信した前記経路要求メッセージに含まれるメトリック計算重み情報を基にメトリックを計算するメトリック計算手順と、
   前記中継ノードが、前記経路要求メッセージに含まれるメトリックと前記メトリック計算手順で計算されたメトリックを基に最良の経路要求を選択し、選択結果にしたがって前記経路要求メッセージを更新し、更新後の経路要求メッセージを隣接ノードに送信する経路要求更新転送手順と、
   宛先ノードが、受信した前記経路要求メッセージに含まれるメトリックを基に最良の経路要求を選択する経路要求受信手順と、
   前記宛先ノードが、前記経路要求メッセージを最初に受信してから一定時間後に経路応答メッセージを隣接ノードに送信する経路応答作成送信手順と、
   前記宛先ノードが、前記選択した経路要求に基づいて経路エントリを作成して経路を設定する第１の経路設定手順と、
   前記中継ノードが、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第２の経路設定手順と、
   前記中継ノードが、受信した経路応答メッセージを隣接ノードに転送する経路応答転送手順と、
   前記送信ノードが、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第３の経路設定手順とを含むことを特徴とする経路制御方法。
2. 請求項１記載の経路制御方法において、
   前記メトリック計算重み情報は、前記送信ノードのアプリケーション毎に設定されることを特徴とする経路制御方法。
3. 請求項２記載の経路制御方法において、
   前記送信ノードのアプリケーションは、通信に先立ち、自身に最適な前記メトリック計算重み情報を設定することを特徴とする経路制御方法。
4. 請求項１乃至３のいずれか１項に記載の経路制御方法において、
   前記メトリックは、経路上のノードメトリック合計値と、経路上のリンクメトリック合計値と、最悪ノードメトリックと、最悪リンクメトリックとを含むことを特徴とする経路制御方法。
5. 請求項１記載の経路制御方法において、
   前記中継ノード及び宛先ノードが、メトリックの良い順に複数個の前記経路要求メッセージを保持し、前記宛先ノードが複数の前記経路応答メッセージを送信することにより、複数の経路を構築することを特徴とする経路制御方法。
6. 請求項１記載の経路制御方法において、
   前記送信ノード及び中継ノードは、パケットの宛先アドレス、上位プロトコル及び宛先ポートに基づいてパケット転送を行うことを特徴とする経路制御方法。
7. 請求項６記載の経路制御方法において、
   前記送信ノード及び中継ノードは、前記経路エントリに上位プロトコル及び宛先ポートが登録されていない場合、宛先アドレスのみに基づいてパケットの転送を行うことを特徴とする経路制御方法。
8. 請求項１記載の経路制御方法において、
   前記経路要求メッセージは、前記一定時間を指定するタイムアップ時間の情報を含むことを特徴とする経路制御方法。
9. 他の通信ノードとの間で無線によりマルチホップネットワークを形成し、そのネットワーク内に経路要求メッセージをブロードキャスト送信して通信経路の探索を行う通信ノードにおいて、
   送信ノードである場合に、パケットの宛先に該当する経路エントリが存在しないとき、転送ノードと転送リンクの転送コストであるメトリックを計算する際のメトリック計算重み情報と、前記メトリックとを含む経路要求メッセージを作成して、隣接ノードに送信する経路要求作成送信手段と、
   中継ノードである場合に、受信した前記経路要求メッセージに含まれるメトリック計算重み情報を基にメトリックを計算するメトリック計算手段と、
   前記中継ノードである場合に、前記経路要求メッセージに含まれるメトリックと前記メトリック計算手段で計算されたメトリックを基に最良の経路要求を選択し、選択結果にしたがって前記経路要求メッセージを更新し、更新後の経路要求メッセージを隣接ノードに送信する経路要求更新転送手段と、
   宛先ノードである場合に、受信した前記経路要求メッセージに含まれるメトリックを基に最良の経路要求を選択する経路要求受信手段と、
   前記宛先ノードである場合に、前記経路要求メッセージを最初に受信してから一定時間後に経路応答メッセージを隣接ノードに送信する経路応答作成送信手段と、
   前記宛先ノードである場合に、前記選択した経路要求に基づいて経路エントリを作成して経路を設定する第１の経路設定手段と、
   前記中継ノードである場合に、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第２の経路設定手段と、
   前記中継ノードである場合に、受信した経路応答メッセージを隣接ノードに転送する経路応答転送手段と、
   前記送信ノードである場合に、受信した経路応答メッセージに該当する経路要求に基づいて経路エントリを作成して経路を設定する第３の経路設定手段とを有することを特徴とする通信ノード。
10. 請求項９記載の通信ノードにおいて、
    前記メトリック計算重み情報は、前記送信ノードのアプリケーション毎に設定されることを特徴とする通信ノード。
11. 請求項１０記載の通信ノードにおいて、
    前記送信ノードのアプリケーションは、通信に先立ち、自身に最適な前記メトリック計算重み情報を設定することを特徴とする通信ノード。
12. 請求項９記載の通信ノードにおいて、
    前記経路要求メッセージは、前記一定時間を指定するタイムアップ時間の情報を含むことを特徴とする通信ノード。

Images