(57)【要約】【課題】アドホックワイヤレス通信ネットワークは複数のノードを含む。【解決手段】各ノードはルーティングテーブルを保持する。ルーティングテーブルは、ソースノードからルート要求パケットを同報通信することによって構築される。要求パケットは目的地ノードのアドレスを含む。要求パケットを受け取る、ネットワーク内の中間ノードは、ルートに参加する中間ノードに関連する電力コストと遅延コストを求める。コストが閾値未満の場合、中間ノードは他のノードのパケットのルーティングに参加する。次に中間ノードは、応答パケットをソースノードに返送する。応答パケットは中間ノードのアドレス並びに電力コストと遅延コストを含む。ソースはこのようにしてルーティングテーブルを構築することができる。ソースノードは、電力コスト、遅延コスト、又は両方のコストに基きアプリケーションデータパケットを転送する特定のノードを選択することができる。【選択図】図２
2005160062.tif 000002
【特許請求の範囲】
【請求項１】
電池で動作する複数のノードを含むワイヤレスネットワークにおいてルートに沿っての残存電力を最大化する方法であって、
前記ネットワークの中間ノードを経由して目的地ノードからソースノードまでの複数のルートを発見すること、
各中間ノードの前記電池の残存電力を測定すること、
前記中間ノードの残存電力に従って、各ルートに関連する電力コストを求めること、
及び
最小の電力コストを有する特定のルートであって、前記ソースノードから前記目的地ノードにデータを転送する特定のルートを選択すること
を含むワイヤレスネットワークにおいてルートに沿っての残存電力を最大化する方法。
【請求項２】
各ルートに関連する遅延コストを求めること、
及び
最小の遅延コストを有する特定のルートを選択することをさらに含む
請求項１記載の方法。
【請求項３】
各ルートに発見時間を関連付けること、
及び
最新の発見時間を有する特定のルートを選択することをさらに含む
請求項１記載の方法。
【請求項４】
前記ネットワークはアドホック型のものである
請求項１記載の方法。
【請求項５】
各ノードにルーティングを格納することをさらに含む
請求項１記載の方法。
【請求項６】
前記残存電力を電力レベルに量子化し、前記電力コストを求めることをさらに含む
請求項１記載の方法。
【請求項７】
前記電力レベルが最小電力レベルである場合、前記ルートに参加すること、
前記電力レベルが最高レベルである場合、前記ルートに参加しないこと、
及び
前記電力レベルが中間電力レベルである場合、前記ルートに参加し、前記電力レベルに従って前記電力コストを増大させることをさらに含む
請求項６記載の方法。
【請求項８】
ｎ番目のノードの初期電力はＥジュールであり、前記ｎ番目のノードの時間ｔにおける前記残存電力はＲ（ｔ）ジュールであり、中間ノードとして前記ｎ番目のノードを使用する場合の前記電力コストはＰ（ｎ）であり、前記ｎ番目の前記電力レベルＬ（ｔ）は、
Ｒ（ｔ）≦Ｅ＊αの場合、Ｌ（ｔ）＝３、
他の場合で、Ｅ＊α＜Ｒ（ｔ）≦Ｅ＊βの場合、Ｌ（ｔ）＝２、
他の場合で、Ｅ＊β＜Ｒ（ｔ）≦Ｅ＊γの場合、Ｌ（ｔ）＝１、
その他の場合、Ｌ（ｔ）＝０
により求められ、式中、α、β、およびγは、１．０未満の数であり、α＜β＜γに従って単調増加する
請求項６記載の方法。
【請求項９】
前記発見することは、ダイナミックソースルーティングを用いる
請求項１記載の方法。
【請求項１０】
前記発見することは、アドホックオンデマンド距離ベクトルルーティングを用いる
請求項１記載の方法。
【請求項１１】
アドレスおよび電池をそれぞれ有する複数のノードを含むワイヤレスネットワークにおいてルートに沿っての残存電力を最大化する方法であって、
ソースノードのアドレスおよび目的地ノードのアドレスを含む要求パケットを同報通信すること、
前記要求パケットを中間ノードにおいて受信すること、
前記中間ノードの前記電池の残存電力を測定すること、
前記中間ノードの前記残存電力に従って、各ルートに関連する電力コストを求めること、
前記中間ノードのアドレスおよび前記電力コストを含む応答パケットを前記ソースノードに送信すること、
前記要求パケットが前記目的地ノードに到達するまで、前記同報通信すること、受信すること、測定すること、求めること、および送信することを繰り返すこと、
前記応答パケットから前記ソースノードのルーティングテーブルに、前記関連する電力コストを有するルートを構築すること、
及び
最小の電力コストを有する特定のルートであって、前記ソースノードから前記目的地ノードまでデータパケットを転送する特定のルートを選択すること、
を含むワイヤレスネットワークにおいてルートに沿っての残存電力を最大化する方法。
【請求項１２】
電池で動作する複数のノードを含むワイヤレスネットワークであって、
前記ネットワークの中間ノードを経由して目的地ノードからソースノードまでの複数のルートを発見する手段と、
各中間ノードの前記電池の残存電力を測定する手段と、
前記中間ノードの残存電力に従って、各ルートに関連する電力コストを求める手段と、
最小の電力コストを有する特定のルートであって、前記ソースノードから前記目的地ノードにデータを転送する特定のルートを選択する手段と
を備える、電池で動作する複数のノードを含むワイヤレスネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはワイヤレス通信ネットワークの分野に関し、詳細にはアドホック通信ネットワークにおけるルーティングに関する。
【背景技術】
【０００２】
アドホックワイヤレスネットワークでは送受信器、すなわち「ノード」が構成され、ネットワークインフラまたは集中管理がない状態で互いに通信する。構成は静的であっても動的であってもよく、または静的と動的の組み合わせであってもよい。ノードは携帯電話、ポータブル計算装置、またはセンサ等の特別な目的の装置であることができる。ネットワーク内のノードはそれ自体の間にルーティングを確立して、それぞれのネットワークを形成する。送受信器の伝送範囲の制限により、ソースノードからのメッセージは、目的地ノードに届く前に１つまたは複数の中間ルーティングノードを経由する必要がある場合がある。
【０００３】
多くのアドホックワイヤレスネットワークでは、すべてとはいえないにしても大半のノードは電池駆動される。したがって、ノードがそれぞれの電池に貯蔵されている電力を使い尽くすとノードが使用不可能になるため、消費電力を最小化することが一番の関心事である。ノードの損失は深刻な問題である。第１に、ノードは割り当てられたタスクを実行することができない。第２に、ノードはもはや他のノードのルータとして機能することができない。かくして、ノードの損失はネットワークを分断する場合がある。したがって、ネットワーク内の電池で動作するノードの寿命を延ばすことが望ましい。
【０００４】
低電力化する技法によっては、トランスコーダの複雑性を低くし、低電力回路を使用し、かつ低シグナリングコストルーティングプロトコルを使用するものもあれば、ネットワークトポロジを利用して低電力化しようとするものもある。
【０００５】
Heinzelman等は、「Energy  efficient Communication Protocol for Wireless Micro  sensor Networks」Proc. of the IEEE Hawaii Int. Conf. on System Sciences, pp. 3005  3014, January, 2000において、ワイヤレスネットワークを低電力化する通信プロトコルについて説明している。Heinzelman等は、ローカルクラスタヘッドのランダムなローテーションを利用して、最終的にネットワーク内のノードに電力負荷を分散させるクラスタリングベースのプロトコルについて説明している。Heinzelman等はまた、２つのノード同士の距離が短い場合、直接伝送のほうがマルチホップ伝送よりも効率的であることも示している。
【０００６】
Chang等は、「Energy Conserving Routing in Wireless Ad  hoc Networks」Proc. of IEEE INFOCOM 2000, March, 2000において、消費電力が低減されるように、静的なワイヤレスネットワーク内のルートおよび対応する電力レベルを選択する方法について説明している。
【０００７】
Catovic等は、「A new approach to minimum energy routing for next generation multi  hop wireless networks」Journal of Communications and Networks, Special Issue on 「Evolving from 3G deployment to 4G definition」December 2002において、異なる電力レベルの２つの異なるチャネルを経由してデータを伝送する技法について説明している。レイク受信器が使用されて、２つの受信信号を組み合わせることによって元のデータが再構築される。
【０００８】
Chen等は、「Energy Efficient System Design with Optimum Transmission Range for Wireless Ad  hoc Networks」Proc of IEEE Int. Conf. on Communications, ICC'02, pp. 945  952, May, 2002において、ワイヤレスアドホックネットワークにおける最適な伝送範囲およびホップ距離を求めている。
【０００９】
多くのワイヤレスネットワークでは、情報はパケットを使用して交換される。ノードは、無線範囲内にある場合は互いに直接通信し、その他の場合は、他の中間ノードを通しての一連のワイヤレス「ホップ」またはリンクにより間接的に通信する。ソースノードと目的地ノードの間の端から端までのリンクは、ルートとして知られている。
【００１０】
したがって、ノードは、無線範囲内にある近隣ノードを見つけ、他のノードへのルートを求める必要がある。時間に敏感なデータ、たとえばセンサデータの場合、あるいはストリーミングデータ、たとえばオーディオストリームまたはビデオストリームの場合、遅延量が最小のルートを見つける必要がある。電池駆動されるネットワークの場合、十分な電力の蓄えを有するノードを含むルートを見つけることも必要である。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
アドホックネットワークによっては、ノードは、データを交換している間に移動することができる。したがって、ルーティング情報を動的に、かつオンデマンドで更新する必要がある。これは、トラヒックを最小化し、計算負荷を最小化し、メモリ要件を最小化し、かつ消費電力を最小化しながら行われることが望ましい。
【００１２】
従来技術では、上記問題に対処するために２つの技法、すなわちダイナミックソースルーティング（ＤＳＲ）、およびアドホックオンデマンド距離ベクトルルーティング（ＡＯＤＶ）が用いられた。
【００１３】
ＤＳＲは「オンデマンド」である。ＤＳＲは、ソースノードが複数のネットワークリンクを経由しての、アドホックネットワーク内の任意の目的地ノードまでのルートを動的に発見できるようにする。ＤＳＲはまた、各パケットがルートを形成するノードのアドレスの完全な順序付きリストを含むことから「ループなし」でもある。
【００１４】
ＤＳＲは２つのモード、すなわちルート発見およびルート維持で動作する。ルート発見中、ソースノードは、パケットが目的地ノードに移行する間に通らなければならないノードを発見してその順序付きリストを求める。この順序付きリストは、ネットワークで伝送される各パケットに添付される。このようにして、中間ノードは単に受信パケットを順序付きリスト内の次のノードに転送するに過ぎない。したがって、中間ノードはネットワーク内のすべてのノードについてのルーティング情報を発見して維持する必要がない。しかし、中間ノードは後で使用するために、転送パケットに含まれているルーティング情報をメモリに記憶することができる。
【００１５】
ＡＯＤＶもまたオンデマンドであり、マルチキャストをサポートする。しかしこの場合、ネットワーク内の各ノードはルーティングテーブルを保持する。したがって、メモリ要件はＤＳＲよりもこの技法の場合のほうが高い可能性がある。局所連結性のために、各ノードは周期的な「ハロー」パケットを近隣ノードに送る。ＡＯＤＶは、所定量後にアイドルルートを無効にする。移動性の高い環境では、ＡＯＤＶはＤＳＲよりも少ない遅延を有する。しかし、ＡＯＤＶにおけるハローパケットに関連するオーバヘッドが高いことから、ＡＯＤＶのスループットはＤＳＲよりも低い。
【課題を解決するための手段】
【００１６】
本発明は、ネットワーク内の残存電力に基づいてネットワーク内のルートを選択する方法を提供する。具体的には、本発明は、ソースノードから目的地ノードに沿った中間ノードすべての総残存電力が最大になるようなルートを選択する。エンドツーエンド遅延（end  to  end delay）、リンク数、ルートの信頼性、または最短ルート等の他のコスト尺度を考慮することもできる。方法は、ソースノードと目的地ノードの間に複数のルートを求めることもできる。
【００１７】
ソースノードＳから目的地ノードＤに送信される各パケットのヘッダは、ルートに沿った中間ノードのアドレスの順序付きリストを伝達する。ヘッダは、ルート選択のために費用関数により使用される情報、たとえば各ノードの残存電力量も伝達する。
【００１８】
中間ノードは、パケットを受信すると、それ自体のアドレスをリストの中で見つけ、パケットをリスト中の次のノードに転送し、ヘッダ情報を更新する。
【００１９】
ルートはオンデマンドで求めることができる。このモードでは、「アクティブ」なルートのみが維持される。維持は、パケットがソースノードから目的地ノードまでのルートに沿って転送される際に行われる。
【００２０】
パケットを転送する間、中間ノードはパケットヘッダ内の電力コストおよび遅延コストを更新することができる。目的地ノードは各パケットを承認し、この承認は更新されたコスト情報をいずれも含む。パケットの承認を受信しない場合、ソースノードはルーティングテーブルから代替のルートを選択する、または新しいルートを発見することができる。
【００２１】
ルート発見は、ネットワークコーディネータノードからの通知に応答して開始することもできる。
【００２２】
より具体的には、アドホックワイヤレス通信ネットワークは複数のノードを含む。各ノードはルーティングテーブルを保持する。ルーティングテーブルは、ソースノードにおいてルート要求パケットを同報通信することによって構築される。要求パケットは目的地ノードのアドレスを含む。
【００２３】
要求パケットを受信するネットワーク内の中間ノードは、ルートに参加する中間ノードに関連する電力コストおよび遅延コストを求める。コストがしきい値未満の場合、中間ノードはルートの形成に参加する。
【００２４】
中間ノードは、目的地ノードへのルートをすでに有している場合、応答パケットをソースノードに返送することができる。応答パケットは中間ノードアドレス、ならびに電力コストおよび遅延コストを含む。こうしてソースノードはルーティングテーブルを構築することができる。中間ノードが目的地ノードへのルートを有していない場合、中間ノードはリスト中の次のノードにパケットを送信する。これは、ルートが求められるまで繰り返される。
【００２５】
ソースノードは、電力コスト、およびおそらく遅延等の他のコスト要因に基づいて、パケットを転送する特定のルートを選択することができる。
【発明を実施するための最良の形態】
【００２６】
ネットワークの構造
図１は、本発明を用いたネットワーク１００を示す。ネットワークはアドホック型、スター型、およびピアツーピア型のトポロジを組み合わせることができる。ノード２００はワイヤレスリンク１０５を介して互いに通信する。複数のリンクがルートを形成する。ネットワークは自己編成型のものであり、ネットワーク内のノードおよび他のコーディネータノードへのサービスの同期を提供する１つのコーディネータノード１１０が存在する場合がある。コーディネータノードは、すべてのノードに既知の予め割り当てられたアドレスを有することができる。
【００２７】
ネットワーク形成中、コーディネータの無線範囲１２０内のノードはすべてコーディネータノードと提携する。無線範囲１２０外のノード１０２は、境界ノード１０３を経由してコーディネータノード１１０と提携し、それによって通信範囲を拡張して、ネットワークに関連する他のノードにアクセスする。互いの無線範囲内にあるノードはクラスタ１３０を構成する。クラスタ群はネットワーク１００の全体を構成する。
【００２８】
ネットワークノード
図２に示すように、各ノードはバス２４０によって接続されたプロセッサ（Ｐ）２１０、メモリ（Ｍ）２２０、およびＩ／Ｏインタフェース２３０を備える。ノードはまた、ワイヤレス無線通信用の送受信器２６０およびアンテナ２７０も備える。ノードは、ディスプレイ２５０およびユーザ制御キーまたはスイッチ２８０も備えることができる。電池２０１は各ノードで動作する。所定期間にわたってネットワーク内のすべてのノードの総残存電力を最大化することが望ましい。
【００２９】
プロセッサ２１０は、他のノードに送信するパケットを生成し、また受信したパケットを復号化する。特に注目する、通常のアプリケーションデータを通信するデータパケットはルーティングパケットである。ルーティングパケットには、ルート要求パケット２２１、ルート応答パケット２２２、承認パケット２２３、エラーパケット２２４、および発見パケット２２５が含まれる。ノードはデータパケット２２６も生成することができる。プロセッサは、ネットワークを通してルーティングされる各パケットのヘッダも生成する。
【００３０】
メモリ２２０は、通信されたパケットから生成されたルーティングテーブル（Ｔ）３００、および発見パケットシーケンス番号（ＳＮ）２２５のリストを記憶し、これらについて以下さらに説明する。
【００３１】
ルーティングテーブル
図３は、ルーティングテーブル３００を詳細に示す。テーブル３００は各目的地ノード毎に１つのエントリ３０１を備える。各目的地ノード毎に１つまたは複数のルート３１０がある。各ルート３１０は、ルートに沿ったノードの中間ノードアドレス３１１の順序付きリスト、遅延コスト３１２、電力コスト３１３、およびお発見時間３１４を含む。遅延コストは、目的地ノードまでのルートにおいて受けるエンドツーエンド遅延である。電力コストは、ルート上の中間ノードすべての総残存電力である。発見時間は、目的地ノードまでのルートがいつ発見されたかを示す。これらについては以下さらに説明する。
【００３２】
ルート発見
図４に示すように、ルート発見方法４００は以下のように動作する。ソースノードＳがアドレスＤを有する目的地ノードにパケットを送信する必要がある場合、ノードＳはまず、ルーティングテーブル３００がアドレスＤのエントリを含んでいるか否かを判定する（４１０）。真の場合で、ノードＩＤのエントリがある場合、ノードＳはルート３１０を選択し（４２０）、パケットを送信する（４３０）。最適なルート選択について以下さらに説明する。
【００３３】
その他の場合で偽の場合、ノードは目的地ノードまでのルートを発見する必要がある。目的地ノードまでのルートを発見するために、ソースノードはルート要求パケット２１１を同報通信する（４４０）。要求パケット２１１は、ノードに関連するシーケンス番号４４１、ソースノードアドレス４４２、目的地ノードアドレス４４３、中間ノードアドレスの順序付きリスト、すなわち「ルート」４４４、電力コストの順序付きリスト４４５、遅延コストの順序付きリスト４４６、およびパケット２２１がいつ生成されたかを示すタイムスタンプ４４７を含む。
【００３４】
ノードＳの無線範囲内にあるノードはルート要求パケット２２１を受信し、このパケットをプロセッサ２１０に渡す。プロセッサは、ルート要求パケット２２１内のシーケンス番号、ソースノードアドレス、および目的地アドレスを復号化する。
【００３５】
プロセッサは、シーケンス番号がリスト２２５に格納されているか否かを判定する（４５０）。真の場合、要求パケットは破棄される（４６０）。その他の場合で偽の場合、ルーティングテーブル３００が目的地ノードＤまでのルートを含むか否かを判定する（４６０）。
【００３６】
真の場合、中間ノードは、ルート情報を含む応答パケット２２２をソースノードに返送する（４７０）。返送パケットは、ソースノードから目的地ノードまでのルート、すなわちアドレス、ならびに中間ノードから目的地ノードまでのアドレスを含む。ルート情報は、遅延コストおよび電力コストも含む。すなわち、応答パケットは本質的に、要求パケットが更新されたものである。
【００３７】
その他の場合で偽の場合、中間ノードは費用関数の値を求めて（４８０）、中間ノードが所望のルートの中間ノードとしての役割を果たすべきか否かを判定する。偽の場合、要求パケットは破棄される（４８５）。その他の場合で真の場合、中間ノードはそれ自体の「中間」アドレス、遅延コスト、および電力コストを要求パケットに追加し（４９０）、パケットを再び同報通信する（４４０）。このプロセスは、ＰＲＥＱパケットが目的地ノードに到達するまで繰り返される。
【００３８】
この時点で、目的地ノードは応答パケットを生成してＳに送信する。ソースノードＳが応答パケットを受信すると、目的地ノードまでのルートがわかり、ソースノードはルートに沿った各リンクの遅延コストおよび電力コストもわかる。
【００３９】
電力コスト
電力コストは、電池で動作するノードの寿命を最長化するために用いられる。中間ノードは、要求パケットを受信すると、電池２０１の局部残存電力２０２を測定する。残存電力は電力コストに変換され、ノードが所望のルートの中間ノードとしての役割を果たすことが費用効率的であるか否かを判定する。残存電力から電力コストへの変換について以下さらに説明する。
【００４０】
電力コストが予め規定されたしきい値コスト未満の場合、中間ノードはそれ自体のアドレスをパケットに追加し（４９０）、その他の場合、パケットは破棄される（４８５）。ノードは、それ自体の局部電力コストおよび遅延コストもリスト４４５に添付し、パケットを近隣ノードに同報通信する。これは、要求パケットが目的地ノードに到達するまで繰り返される。最終的に、ソースノードへの応答パケットが生成される。
【００４１】
ソースノードＳは、応答パケット２２２を受信すると、新たに発見されたルートに関連する電力コストを、ソースノードが同じ目的地ノードに利用することができる他のルートの費用と比較する。
【００４２】
次に、電力コストの最小のルートを、データパケット２２６の転送に選択することができる。
【００４３】
ルートの電力コストは、中間ノードの残存電力から導き出される。特に重要なのは、いずれのノードの電力もそれ自体の動作を維持するのに十分であることを確実にすることである。
【００４４】
ノードの電力コストの計算を簡易化するため、また電力コストおよび遅延コストの表現に使用されるオーバヘッドのサイズを低減するために、本発明は残存電力を離散レベルに量子化して電力コストを求める。
【００４５】
たとえば、４つのレベルが使用される場合、
レベル０は非常に高い残存電力を意味する。ノードはデータの転送に積極的に参加することができる。ヘッダ中の電力コストは変更されないままである。
レベル１は中程度の残存電力を意味する。ノードはデータの転送に積極的に参加することができるが、パケットヘッダ中の電力コストは１だけ増分される。
レベル２は低い残存電力を意味する。ノードはデータの転送に参加することができるが、ヘッダの電力コストは２だけ増分される。
レベル３は不十分な残存電力を意味する。ノードはルートの形成に参加しない。この場合、要求パケットは破棄される。
【００４６】
換言すれば、最低レベルの場合は常に参加し、電力コストは増分せず、最高レベルの場合は決して参加せず、中間レベルの場合は参加するが、残存電力の量子化量に従ってルートの電力コストを増分する。
【００４７】
ｎ番目のノードの初期電力量がＥジュールである場合、時間ｔにおけるノードの残存電力はＲ（ｔ）ジュールで表され、ｎ番目のノードを中間ノードとして使用する量子化電力コストはＰ（ｎ）である。
【００４８】
電力費用関数
局部電力レベルＬ（ｔ）を求める一方法は、以下の費用関数を使用するというものである。すなわち、
Ｒ（ｔ）≦Ｅ＊αの場合、Ｌ（ｔ）＝３、
他の場合で、Ｅ＊α＜Ｒ（ｔ）≦Ｅ＊βの場合、Ｌ（ｔ）＝２、
他の場合で、Ｅ＊β＜Ｒ（ｔ）≦Ｅ＊γの場合、Ｌ（ｔ）＝１、
その他の場合、Ｌ（ｔ）＝０
であり、式中、α、β、およびγは１．０未満の数であり、α＜β＜γに従って単調増加する。
【００４９】
局部電力コストが求められた後、パケットを次のノードに転送する前にパケットヘッダに追加される（４９０）。すなわち、電力コストＰ（ｎ）はＰ（ｎ）＝Ｌ（ｔ）として更新される。特定のルートの総電力コストは、ルートを形成する中間ノードに関連する電力コストの和である。
【００５０】
ルート要求パケットを受信する各ノードは、同じようにして電力コストを求めて転送する。このようにして、ソースノードは目的地ノードまでのルートを構成するノードの順序付きリスト、およびルートに沿った各ノードに関連する電力コストを受信する。
【００５１】
遅延コスト
パケット中のデータが遅延に敏感なものである場合、中間ノードは遅延コストも計算することができる。ルートの特定のリンクの遅延コストは、現在時間とタイムスタンプ４４７に記憶されている時間との間の差から求められる。このコストはまた、電力コストと同数の離散レベルにマッピングされ、したがって限られた数のビットを使用して表すことができる。ルートの総待ち時間は、ルート応答またはソースが受信した承認における個々の遅延コストの和である。
【００５２】
ルート選択
目的地ノードがルーティングテーブル３００内にある場合、ソースノードは通常、データパケットの送信に最新のルート、すなわち最新の発見時間３１４、および最小の電力コスト３１３のルートを選択する。パケットが時間に敏感である、たとえばセンサデータまたはストリーミングデータである場合、最小の遅延コスト３１２のルートが選択される。
【００５３】
これら選択基準は様々な順序で組み合わせることが可能であることに留意されたい。
【００５４】
中間ノードは、それ自体のアドレスを含む要求パケットを受信すると、パケットをルートリスト４４４中の次のノードに転送する前に、それ自体のアドレスの要求パケット２１１中の電力コストおよび遅延コストを更新する。
【００５５】
承認
目的地ノードＤは、データパケット２２６を受信すると、承認パケット２２３をソースノードに返送する。承認パケットは、逆の順序の中間ノードのルートに沿って送信される。この承認は２つの目的を果たす。承認パケットは、首尾良く送信が行われたことをソースノードに通知する。ここでソースノードは、パケットを再送信する必要がないため、送信済みのパケットを破棄することができる。
【００５６】
承認パケットは、ルートに沿った各リンクの更新されたコスト値も含む。したがって、ソースノードおよび中間ノードは、ソースノードまでのルートに沿って逆に移行するいずれの承認パケットからでもそれぞれのルーティングテーブルを更新することができる。
【００５７】
承認パケットを受信すると、ソースノードはルーティングテーブル３００を更新することができ、発見時間３１４を現在時間に設定することができる。
【００５８】
承認パケットを受信しない場合、ソースノードは、承認パケットを受信するまでパケットを再送信することができる。予め設定された時間しきい値を越えても承認を受信しない場合は、ルートがもはや利用可能ではないものと想定する。この場合、ソースノードはテーブル３００からそのルートを削除し、別のルートを選択することができる。別のルートが利用可能ではない場合、目的地までの新しいルートを発見することができる。
【００５９】
任意の中間ノードが「破断した」ルートを発見することができることに留意されたい。この場合、中間ノードはルートエラーパケット２２４をソースノードに返送することができる。ルートエラーパケットは、ルートが破断していることをソースノードに通知し、ソースノードが再送信をそれ以上試行する必要性をなくす。
【００６０】
ルーティング維持
ルート維持はオンデマンドであり、ルートの通常使用中に行われる。ソースノードが選択されたルートに沿ってパケットを送信すると、各中間ノードは上に説明したように電力および遅延の計算を実行する。新しいコスト値が異なるものである場合、新しいコストが前のコストに取って代わる。
【００６１】
ノードがネットワークを出る場合、いくつかのルートはもはや利用可能でなくなることになる。こういったルートはテーブル３００から削除され、必要であれば代替のルートが発見される。
【００６２】
ノードがネットワークに入る場合、コーディネータノード１１０に通知することができる。次に、コーディネータノード１１０は、上に説明したように、発見パケット２２５をすべてのノードに同報通信して、ルート発見を実行することができる。
【００６３】
本発明の好ましい実施形態について、基礎をなすルート発見プロセスとしてＤＳＲを用いた例を介して説明しているが、アドホックオンデマンド距離ベクトルルーティング（ＡＯＤＶ）等、他のアドホックルーティングアルゴリズムも同じ費用関数を使用して最適ルートを求めることができ、ＤＳＲの使用は提案される本発明の動作要件ではない。
【００６４】
本発明について好ましい実施形態の例として説明したが、他の様々な適合形態および変更形態を本発明の精神および範囲内で行うことができることを理解されたい。したがって、添付の特許請求項の目的は、本発明の真の精神および範囲内にあるこのような変形形態および変更形態をすべて網羅することにある。
【図面の簡単な説明】
【００６５】
【図１】本発明によるワイヤレス通信ネットワークのブロック図である。
【図２】図１のネットワーク内のノードのブロック図である。
【図３】本発明により使用されるルーティングテーブルのブロック図である。
【図４】図１のネットワーク内のルートを発見する方法のブロック図である。
【図１】
2005160062.tif 000003
【図２】
2005160062.tif 000004
【図３】
2005160062.tif 000005
【図４】
2005160062.tif 000006
【外国語明細書】
2005160062.tif 000007
2005160062.tif 000008
2005160062.tif 000009
2005160062.tif 000010
2005160062.tif 000011
2005160062.tif 000012
2005160062.tif 000013
2005160062.tif 000014
2005160062.tif 000015
2005160062.tif 000016
2005160062.tif 000017
2005160062.tif 000018
2005160062.tif 000019
2005160062.tif 000020
2005160062.tif 000021
2005160062.tif 000022
2005160062.tif 000023
2005160062.tif 000024
2005160062.tif 000025
2005160062.tif 000026
2005160062.tif 000027
2005160062.tif 000028
2005160062.tif 000029
2005160062.tif 000030
2005160062.tif 000031