(57)【要約】【課題】  アド・ホック・ネットワーク環境等に関連したパフォーマンス目標に合致するルーティング技法を提供する。【解決手段】  本発明の技法は、ネットワークのライフタイムを実質的に最大にするように働く。本発明の１つ局面では、分散ネットワークのノードにおいて使用するためのパケット・ルーティング技法が以下のようなステップ／操作を含む。パケットを保存するためのキューが維持される。この場合、当該ノード及び近隣ノードの間に存在するリンクに１つのキューが関連付けられ、キューはそれに関連した高さを有する。当該ノード及び近隣オードに関連したエネルギ制約が実質的に最大になるように、そのキューに保存された１つ又は複数のパケットに対する経路が近隣ノードにおけるキューの高さに基づいて決定される。上記のように、分散ネットワークは、当該ノード及び少なくとも１つの近隣ノードが無線リンクを介して通信するモバイル・アド・ホック・ネットワークであることが望ましい。
2006513602.tif 000002
【特許請求の範囲】
【請求項１】
パケットを経路指定するために分散ネットワークのノードにおいて使用する方法であって、
前記パケットを保存するためのキューを維持するステップにして、前記ノードと近隣ノードとの間に存在するリンクに少なくとも１つのキューが関連付けられ、該キューがそれに関連した高さを有する、ステップと、
前記ノード及び近隣ノードに関連したエネルギ制約が実質的に最大にされるように、前記キューに保存された１つ又は複数のパケットに対する経路を前記近隣ノードにおける前記キューの高さに基づいて決定するステップと、
を含む、方法。
【請求項２】
前記分散ネットワークがモバイル・アド・ホック・ネットワークであり、更に、前記ノード及び少なくとも１つの前記近隣ノードが無線リンクを介して通信する、請求項１に記載の方法。
【請求項３】
前記ノードのキューの高さが前記近隣ノードのキューの高さよりも大きいとき、１つ又は複数のパケットが前記ノードのキューからリンクを介して前記近隣ノードのキューに送られる、請求項１に記載の方法。
【請求項４】
前記ノードのキューの高さが前記近隣ノードのキューの高さよりも小さいとき、１つ又は複数のパケットが前記近隣ノードのキューからリンクを介して前記ノードのキューにおいて受信される、請求項１に記載の方法。
【請求項５】
前記ノードが、１つの近隣ノードにおける少なくとも１つのキューの高さに関するブロードキャスト情報を少なくとも１つの近隣ノードから受信するステップを更に含む、請求項１に記載の方法。
【請求項６】
前記ノードが、前記ノードにおける少なくとも１つのキューの高さに関する情報を少なくとも１つの近隣ノードにブロードキャストするステップを更に含む、請求項１に記載の方法。
【請求項７】
前記分散ネットワークに関連したライフタイムを実質的に最大にするときにスループット要件が実質的に満たされるようなラウンドにおいて、パケットがそれの少なくとも１つを前記ノードに及び前記ノードから経路指定される、請求項１に記載の方法。
【請求項８】
前記ネットワークのライフタイムがそれに関連した上限及び下限を有する、請求項１に記載の方法。
【請求項９】
前記経路を決定するステップが、
（ｉ）前記ノードに関連したアイドル電力消費量、
（ii）前記ノードに関連した計算電力消費量、
（iii） 前記ノードに関連した定期的再充電量、
（iv）１つ又は複数の制約、
（ｖ）前記ノードにおけるパケットの受信に関連した電力消費量、
の少なくとも１つを考慮することを含む、請求項１に記載の方法。
【請求項１０】
前記分散ネットワークが静的に又は動的に変化する、請求項１に記載の方法。
【請求項１１】
リンクを介して結合され、前記リンクに関連したキューを有する複数のノードを含む分散ネットワークにおいてパケットを経路指定する方法であって、
パケット・フローを、対応するソース・ノードにおいて前記分散ネットワークに導入するステップと、
前記分散ネットワークの各ノードにおけるキューを均等化するステップと、
影響下にあるノードにおける電力損失を実質的に最小にするように、高い高さを有するキューから低い高さを有するキューにパケットが移動するよう前記分散ネットワークにおけるパケット・フローを強要するステップと、
キューの高さがゼロに設定されるような対応するシンク・ノードにおいて前記パケットのフローを吸収するステップと、
を含む、方法。
【請求項１２】
前記分散ネットワークがモバイル・アド・ホック・ネットワークであり、更に、前記ノード及び少なくとも１つの近隣ノードが無線リンクを介して通信する、請求項１１に記載の方法。
【請求項１３】
ノードが、１つの近隣ノードにおける少なくとも１つのキューの高さに関するブロードキャスト情報を少なくとも１つの近隣ノードから受信するステップを更に含む、請求項１１に記載の方法。
【請求項１４】
前記分散ネットワークに関連したライフタイムを実質的に最大にするときにスループット要件が実質的に満たされるような複数のラウンドにわたって、前記導入するステップ、前記均等化するステップ、前記強要するステップ、及び前記吸収するステップが実行される、請求項１１に記載の方法。
【請求項１５】
パケットを経路指定するために分散ネットワークのノードにおいて使用するための装置であって、
メモリと、
前記メモリに結合され、（ｉ）パケットを保存するためのキューを維持し、前記ノードと近隣ノードとの間に存在するリンクに少なくとも１つのキューが関連付けられ、該キューがそれに関連した高さを有し、（ii）前記ノード及び前記近隣ノードに関連したエネルギ制約が実質的に最大にされるように、前記キューに保存された１つ又は複数のパケットに対する経路を前記近隣ノードにおけるキューの高さに基づいて決定するように動作する、少なくとも１つのプロセッサと、
を含む、装置。
【請求項１６】
前記分散ネットワークがモバイル・アド・ホック・ネットワークであり、更に、前記ノード及び少なくとも１つの近隣ノードが無線リンクを介して通信する、請求項１５に記載の装置。
【請求項１７】
前記ノードのキューの高さが前記近隣ノードのキューの高さよりも大きいとき、１つ又は複数のパケットが前記ノードのキューからリンクを介して前記近隣ノードのキューに送られる、請求項１５に記載の装置。
【請求項１８】
前記ノードのキューの高さが前記近隣ノードのキューの高さよりも小さいとき、１つ又は複数のパケットが前記近隣ノードのキューからリンクを介して前記ノードのキューにおいて受信される、請求項１５に記載の装置。
【請求項１９】
前記ノードが、１つの近隣ノードにおける少なくとも１つのキューの高さに関するブロードキャスト情報を少なくとも１つの近隣ノードから受信する、請求項１５に記載の装置。
【請求項２０】
前記ノードが、前記ノードにおける少なくとも１つのキューの高さに関する情報を少なくとも１つの近隣ノードにブロードキャストする、請求項１５に記載の装置。
【請求項２１】
前記分散ネットワークに関連したライフタイムを実質的に最大にするときにスループット要件が実質的に満たされるようなラウンドにおいて、パケットがそれの少なくとも１つを前記ノードに及び前記ノードから経路指定される、請求項１５に記載の装置。
【請求項２２】
前記ネットワークのライフタイムがそれに関連した上限及び下限を有する、請求項１５に記載の装置。
【請求項２３】
前記経路を決定する動作が、
（ｉ）前記ノードに関連したアイドル電力消費量、
（ii）前記ノードに関連した計算電力消費量、
（iii） 前記ノードに関連した定期的再充電量、
（iv）１つ又は複数の制約、
（ｖ）前記ノードにおけるパケットの受信に関連した電力消費量、
の少なくとも１つを計上する、請求項１５に記載の装置。
【請求項２４】
前記分散ネットワークが静的に又は動的に変化する、請求項１に記載の方法。
【請求項２５】
パケットを経路指定するために分散ネットワークのノードにおいて使用するためのコンピュータ・プログラムであって、実行時に、
パケットを保存するためのキューを維持するステップにして、前記ノードと近隣ノードとの間に存在するリンクに少なくとも１つのキューが関連付けられ、該キューがそれに関連した高さを有する、ステップと、
前記ノード及び前記近隣ノードに関連したエネルギ制約が実質的に最大にされるように、前記キューに保存された１つ又は複数のパケットに対する経路を前記近隣ノードにおけるキューの高さに基づいて決定するステップと、
を実行する、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線アド・ホック・ネットワークに関し、詳しく言えば、無線アド・ホック・ネットワークにおいて使用するための最大ライフタイム・ルーティング技法に関するものである。
【背景技術】
【０００２】
モバイル・アド・ホック・ネットワーク（ＭＡＮＥＴ）とも呼ばれる無線アド・ホック・ネットワークは、無線リンクによって接続されたノードの集合体を含むものとして知られている。アド・ホック・ネットワークの代表的な例は、無線センサ・ネットワークである。そのネットワークでは、ノードは、環境データを収集し且つ更なる処理のためにその情報を計算ノードに送るか又は有線ネットワークに対するリレーのためのベース・ステーションに送るセンサである。そのようなネットワークは、例えば、救助活動の援助を行うべき災害地域、鉱物又は石油を探査するための地域、及び防御に専念する戦場のような危険な場所等に配備されることがある。
【０００３】
アド・ホック・ネットワークのトポロジは、ノードが無作為に移動すること及びそれ自体を独断的に編成することが一般に自由であるので、ダイナミックである。従って、トポロジは、ノード及び他の環境条件に関するの現在の地理的な位置、並びにノードが所持する無線送受信装置の特性によって決定されることがある。従って、トポロジは、任意のグラフとして表すことが可能である。その場合、そのグラフの「ノード」がネットワークにおけるノードを表し、そのグラフの「エッジ」がノード間のリンクを表す。
【０００４】
アド・ホック・ネットワークにおけるノードは、一般に、パケットをリレーすることにより相互間で通信しようとする。しかし、アド・ホック・ネットワークにおけるノードの特徴である限定された送信範囲のために、１つのノードがそのネットワークを介して他のノードとデータを交換するには、一般に、複数のネットワーク・「ホップ」が必要である。問題は、そのような通信環境の場合、種々のパフォーマンス上の目標に適合するように効果的なルーティング・プロトコルを設計することである。
【０００５】
無線アド・ホック・ネットワークのためのほとんどの既存のルーティング・プロトコルは、移動性又は他の環境変化によって生じたトポロジの変化にもかかわらず経路を見つけ、その経路を維持することに集中している。代表的なプロトコルは、ホップ・カウント、地理的距離、又は送信電力に基づく最短パス方式を使用する。最初の２つは、遅延を最少にし且つスループットを最大にするという点で重要である。三番目は、無線アド・ホック・ネットワークに独特であり、一般に、関連のノードが限定された電源を有し且つ無線通信がこの電源の大部分を消費するので、重要である。
【０００６】
この問題を処理するために、幾つもの電力問題を意識したルーティング及びトポロジ制御方式が開発されている。これらの方式のほとんどにおいて、その目的は、パケットを目的地まで配送するためにパケット単位の消費されるエネルギを最少することである。代表的な方法は、２つの関連したノード間でパケットを伝送するために必要な電力にエッジ・コストが関連するという分散最短パス方式を使用するものである。この技法に関する問題点は、最少エネルギ・パスにおけるノードが、障害の発生時に電力を急速に消耗してネットワークの接続性に影響を与えることである。
【０００７】
更に複雑なルーティング方式のいくつかは、わずかな予備電力を有するノードを介して経路指定することとコストとを関連付けている。しかし、これは、精々、試行錯誤的な解決方法にとどまる。
【０００８】
電力消費の問題をもっと正確に捉えようとする線形計画法を使用した数式が提案されている。これに関しては、Proceedings of 37th Annual Allerton Conference on Communication,Control and Computing, September 1999 誌における「無線アド・ホック・ネットワークにおける最大システム・ライフタイムのためのルーティング（Routingfor Maximum System Lifetime in Wireless Ad-hoc Networks）」と題した J.H. Chang 氏他の論文、及びProceedings of IEEE INFOCOM, pp. 22-31, March 2000 誌における「無線アド・ホック・ネットワークにおけるエネルギ保全ルーティング（EnergyConserving Routing in Wireless Ad-hoc Networks）」と題した J.H. Chang 氏他の論文を見られたい。その概念は、「ネットワークのライフタイム」の最大化をルーティングの最終目的とすることである。既知のように、ネットワーク・ライフタイムは、ネットワークがノード障害なしに動作する期間である。この最大化方法は、線形計画法を近似的に解くために試行錯誤的な方式を利用する。しかし、そのような試行錯誤的な方法は、最悪の状況では専断的になり、不十分な遂行しかできないことがある。
【０００９】
更に、最大ライフタイムを決定するための集中制御方式が、ComputerScience : Networking 2000, vol. 1815, pp. 702-703, May 2000 誌における「無線アド・ホック・ネットワークにおける最大ライフタイム・ルーティングのための高速近似アルゴリズム（FastApproximation Algorithms for Maximum Lifetime Routing in Wireless Ad-hocNetworks）」と題した J.H. Chang 氏他の論文において提案されている。このような集中制御方式は、Proceedings of 39thAnnual Symposium on Foundations of Computer Science, pp. 300-309, November 1998誌における「マルチコモディティ・フロー及び他の端数処理問題のための高速且つ簡単なアルゴリズム（Faster and Simpler Algorithm forMulticommodity Flow and Fractional Packing Problems）」と題した N. Garg 氏他の論文に開示されているようなマルチコモディティ・フローのためのガルグ・ケネマン（Garg-Koenemann）方式に基づいている。しかし、この方法は、上記線形計画法に関連したすべてのパフォーマンス障害を解決するものではない。
【００１０】
従って、アド・ホック・ネットワーク環境等に関連したパフォーマンス目標に合致した効果的なルーティング技法に対する要求が依然として存在する。
【非特許文献１】Proceedings of 37thAnnual Allerton Conference on Communication, Control and Computing, September1999 誌
【非特許文献２】Proceedings of IEEEINFOCOM, pp. 22-31, March 2000 誌
【非特許文献３】Computer Science :Networking 2000, vol. 1815, pp. 702-703, May 2000 誌
【非特許文献４】Proceedings of 39thAnnual Symposium on Foundations of Computer Science, pp. 300-309, November 1998誌
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、アド・ホック・ネットワーク環境等に関連したパフォーマンス目標に合致した効果的なルーティング技法を提供するものである。
【課題を解決するための手段】
【００１２】
本発明の１つの側面では、分散ネットワークの１つノードで使用するためのパケット・ルーティング技法が以下のようなステップ／操作を含む。パケットを保存するためのキューが維持され、当該ノード及び近隣ノードの間に存在するリンクに少なくとも１つのキューが関連付けられ、しかもキューはそれに関連した高さを有する。そこで、当該ノード及び隣接ノードに関連したエネルギ制約が実質的に最大にされるように、それらのキューに保存された１つ又は複数のパケットに対する経路が近隣ノードにおけるキューの高さに基づいて決定される。上述のように、分散ネットワークは、当該ノード及び少なくとも１つの近隣ノードが無線リンクを介して通信するというモバイル・アド・ホック・ネットワークであることが望ましい。
【００１３】
当該ノードのキューの高さが近隣ノードのキューの高さよりも大きいとき、当該ノードのキューからリンクを介して近隣ノードのキューに、１つ又は複数のパケットを送ることが可能である。更に、当該ノードのキューの高さが近隣ノードのキューの高さよりも小さいとき、１つ又は複数のパケットがその近隣ノードのキューからリンクを介して当該ノードのキューにおいて受信されることが可能である。
【００１４】
当該ノードは、少なくとも１つの近隣ノードの少なくとも１つのキューの高さに関連したブロードキャスト情報を少なくとも１つの近隣ノードから受信することが可能である。更に、当該ノードは、当該ノードの少なくとも１つのキューの高さに関連した情報を少なくとも１つの近隣ノードにブロードキャストすることも可能である。
【００１５】
パケットは、分散ネットワークに関連したライフタイムを実質的に最大にするとき、スループット要件が実質的に満たされるように、ノードに、及び／又は、ノードから経路指定されてもよい。更に、ネットワーク・ライフタイムはそれと関連した上限及び下限を有する。
【００１６】
更に、本発明の経路決定技法は、ノードに関連した１つ又は複数の活動停止中の電力消費量、ノードに関連した計算電力消費量、ノードに関連した定期的な再充電量、１つ又は複数のエッジ制約、及びノードにおけるパケットの受信に関連した電力消費量を考慮することも可能である。
【００１７】
有利なことに、本願において詳細に説明されるように、本発明は、最適なルーティング解決策を漸近的に少量の相対誤差内に近づける分散ルーティング方式を提供し得る。更に、本発明の技法は、マルチコモディティ（multicommodity）・フローの数式に基づくことが望ましく、それらは、種々の電力消費モデル及び帯域幅制約を考慮する。本発明の技法を種々のネットワークと共に使用することが可能であるが、この技法は、静的ネットワーク及びゆっくりと変化する動的ネットワークの両方に対して特によく作用する。しかし、本発明の技法は、動的ネットワークによって実装されることも可能である。
【００１８】
本発明に関するこれらの及び他の目的、特徴、及び利点が、添付図面と関連して読まれるべき本発明の実施例に関する下記の詳細な説明から明らかになるであろう。
【発明を実施するための最良の形態】
【００１９】
以下の記述は、例示的なアド・ホック・ネットワーク・アーキテクチャを使用して本発明を説明するものである。しかし、本発明がいずれの特定なアド・ホック・ネットワーク・アーキテクチャによる使用にも限定されないことは当然である。むしろ、本発明は、一般的には、効果的なデータ・ルーティングを遂行することが望ましい任意のネットワーク・アーキテクチャに適用可能である。
【００２０】
先ず、図１を参照すると、本発明の技法を実装し得る無線アド・ホック・ネットワークがブロック図で示される。図示のように、無線アド・ホック・ネットワーク１００は、無線リンクによって接続された複数のモバイル・ノード１０２−１乃至１０２−Ｎを含む。ノードの数Ｎは、それらのノードが配置されるべきアプリケーションに依存し、従って、本発明はいずれの特定の数にも限定されない。
【００２１】
ノード１０２−１乃至１０２−Ｎは、無作為に移動すること及びそれ自体を任意に編成することが自由である。従って、アド・ホック・ネットワーク１００のトポロジはダイナミックである。更に、ノード１０２−１乃至１０２−Ｎは、パケットをリレーすることによって相互に通信する。しかし、上述のように、アド・ホック・ネットワークにおけるそのようなノードの特徴である限定された送信範囲のため、１つのノードがネットワーク１００を介して他のノードとデータを交換するためには、複数のネットワーク・ホップ（図１では１０４として示される）が必要である。
【００２２】
従って、図１に示されるように、ノード１０２−１は、無線リンクを介してノード１０２−３にパケットを転送（第１ホップ）し、しかる後、ノード１０２−３が無線リンクを介してノード１０２−４にそのパケットを転送（第２ホップ）する。しかる後、ノード１０２−４が無線リンクを介してノード１０２−Ｎにそのパケットを転送（第３ホップ）することによって、ノード１０２−１はノード１０２−Ｎと通信することが可能となる。勿論、種々の要因次第で、パケットがノード１０２−１から、多少のホップ１０４を有する他の経路を介して、ノード１０２−Ｎに転送されることも可能である。図を明瞭にするために、図１は、１つのノードから他のノードにパケットを転送するために利用し得るすべての可能なホップ配列を特定的に示してはいないことを理解すべきである。また、ノードはそれ自身と他のノードとの間に別個の無線リンクを持ち得るが、ホップが、当該ノードからその無線リンクの１つを介して他のノードの１つへのデータの転送を指すことも明らかである。いずれの場合も、本発明が主として焦点を当てているのはネットワークにおける経路の選択（即ち、ルーティングの解決策を決定すること）であることは明らかであろう。
【００２３】
ネットワーク１００におけるノードのうちのいずれか１つが計算ノードとして作用する。計算ノードでは、それに転送されたパケットを何らかの方法で更に処理することが可能であることも明らかであろう。更に、ノード１０２−Ｎが、又はそのネットワークにおけるベース・ステーション１０６の範囲内における他の受信ノードが、有線ネットワーク１０８にリレーするためにベース・ステーションに情報を転送することも可能である。有線ネットワーク１０８は、私設のデータ・ネットワーク、インターネットであってもよい。図を明瞭にするために、図１には、ただ１つのベース・ステーション及び有線ネットワークしか示されないが、１つ又は複数の更なる有線ネットワークと通信する１つ又は複数の更なるベース・ステーションが存在し得ることはいうまでもない。勿論、代替的には、ネットワーク１０８が他の無線ネットワークであってもよいことは当然である。
【００２４】
従って、ノード１０２−１乃至ノード１０２−Ｎが、データを収集するために、危険な環境又は敵対的な環境に配置される場合、それらのノードによって収集されたデータは、それが危険でない又は非敵対的な（或いは、少なくとも危険性の低い又は敵対性の低い）環境において提示又は分析されるよう、有線ネットワーク１０８を介して遠隔のロケーションに転送されることもある。
【００２５】
次に、図２を参照すると、本発明の技法のすべて又は一部分を実装するために使用することが可能なコンピュータ・システム又は装置の一例がブロック図で示される。更に詳しく言うと、１つ又は複数のノード１０２−１乃至１０２−Ｎ、及び／又は、ベース・ステーション１０６は、本発明の技法を遂行するためのそのようなコンピュータ・システム２００を実装することが可能である（しかし、ベース・ステーションは、後述するように、必ずしも「センサ」を必要としない）。勿論、本発明が如何なる特定のコンピュータ・システムの実装形態にも限定されないことはいうまでもない。
【００２６】
この説明上の実装形態では、本発明の方式の少なくとも一部分を実装するためのプロセッサ２０２は、バス２１０又は代替の接続機構を介してメモリ２０４、センサ２０６、及びネットワーク・インターフェース２０８に動作関係に結合される。本願において使用される用語「プロセッサ」は、例えば、中央処理装置（ＣＰＵ）、及び／又は、他の処理回路（例えば、ディジタル信号プロセッサ（ＤＳＰ）、マイクロプロセッサ等）を含むもののような任意の処理装置を含むことを意図されていることは明らかである。更に、用語「プロセッサ」が複数の処理装置を指し得ること及び１つの処理装置に関連した種々の素子が他の処理装置によって共用されることがあり得ることも当然である。
【００２７】
本願において使用される用語「メモリ」は、メモリ、及びプロセッサ又はＣＰＵに関連した他のコンピュータ可読媒体、例えば、ランダム・アクセス・メモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、固定記憶媒体（例えば、ハード・ディスク）、取り外し可能記憶媒体（例えば、ディスケット）、フラッシュ・メモリ等を含むことを意図されている。メモリは、後述されるノードに関連した１つ又は複数のキューを実装するように使用されることが望ましい。
【００２８】
更に、本願において使用される用語「センサ」は、例えば、コンピュータ・システム２００（例えば、モバイル・ノード）が配置される環境からデータを収集することができる１つ又は複数の装置を含むことを意図されている。センサの例は、配置される環境からデータを収集することができる無線通信装置に関連した受信装置であってもよい。しかし、本発明がいずれの特定なセンサにも限定されないことはいうまでもない。更に、ベース・ステーションは、一般に、センサを持たないであろう。
【００２９】
更に、本願において使用されるフレーズ「ネットワーク・インターフェース」は、例えば、コンピュータ・システム２００（例えば、モバイル・ノード又はベース・ステーション）が他のコンピュータ・システム（例えば、モバイル・ノード又はベース・ステーション）と通信することを可能にし得る１つ又は複数の装置を含むことを意図されている。従って、ネットワーク・インターフェースは、適当な無線プロトコルを介して他のコンピュータ・システム（例えば、モバイル・ノード又はベース・ステーション）と通信するように構成された送受信装置を含み得る。無線伝送プロトコルの例は、ブルートゥース（Bluetooth）及び IEEE 801.11 であってもよい。しかし、本発明が如何なる特定の通信プロトコルにも限定されないことは勿論である。
【００３０】
本願ではネットワーク通信システムに関連して本発明を説明するが、本発明の方式がコンピュータ可読媒体の形式で配布可能であること、及び、その配布のために実際に使用される特定のタイプの信号保持媒体に関係なく、本発明が実装可能であり、その利点が実現可能であることは明らかである。本願において使用される用語「コンピュータ可読媒体」は、例えば、フロッピ・ディスク（商標）、ハード・ディスク・ドライブ、ＲＡＭ、コンパクト・ディスク（ＣＤ）、ＲＯＭ等ような記録可能型媒体、並びに、例えば、ディジタル及びアナログ通信リンク、無線周波伝送及び光学的伝送等のような伝送形式を使用する有線又は無線通信リンクのような伝送型媒体を含むことを意図されている。コンピュータ可読媒体は、特定のデータ処理システムにおいて使用するためにデコードされるコード化フォーマットの形態をとることが可能である。
【００３１】
従って、本願において開示される本発明の方式を遂行するための命令又はコードを含む１つ又は複数のコンピュータ・プログラム又はそれのソフトウェア・コンポーネントは、１つ又は複数の関連の記憶媒体（例えば、ＲＯＭ、固定又は取り外し可能記憶装置）に保存することが可能であり、そして、利用の準備ができると、全体的に又は部分的にロードされ、プロセッサ２０２によって実行される。
【００３２】
いずれの場合も、本願において開示され、添付図面に示された本発明の技法を、ハードウェア、ソフトウェア、又はそれらの組み合わせという種々の形式で、例えば、関連のメモリを有する１つ又は複数の動作的にプログラムされた汎用ディジタル・コンピュータ、実装形態特有の集積回路、機能的回路等に実装することが可能であることは明らかある。本願で提供された発明の技法が与えられると、当業者は本発明の技法の別の実装形態を着想することが可能であろう。
【００３３】
参照を容易にするために、詳細な説明の残り部分を次のようなセクションに分けることにする。即ち、
（１）概説
（２）問題の数式化
（３）ローカル制御フロー方式
（４）ライフタイムの最大化
（５）実装形態
（６）ローカル制約に対する拡張
（７）ノードにおける例示的判断フロー
【００３４】
（１）概説
前述のように、アド・ホック・ネットワークの環境の特性を仮定した場合、問題は、アド・ホック・ネットワーク環境の種々のパフォーマンス目標に合致するための効果的なルーティング方式を設計することである。本発明は、この問題を処理し、そのようなパフォーマンス目標を実現するための解決策を提供する。
【００３５】
本発明によれば、後述するように、ルーティング問題が最大並行フロー問題として明示的に数式化される。ルーティング問題は、すべて、類似のフロー実現化方法を有する。この方法では、フローは、パケットがとる経路を表し、要求は、種々のノードによりパケットが生成される速度を表す。この数式化は、最大ネットワーク・ライフタイムのためのルーティングの問題に最大フロー技法を適用することを可能にする。しかし、既知の最大フロー技法の多くは、ルーティング方式にとって必要な分散実装形態に適したものではなく、ネットワーク・トポロジの変化に十分に適応しない。更に、それらは、一般に、制約がリンク帯域幅（単位時間にエッジを介して経路指定されるパケットの数）及びノード容量（単位時間にノードによって送られるパケットの数）である有線ネットワーク・ルーティングの問題によく適応している。
【００３６】
本発明は、ルーティング問題に対する分散フロー方式を提供する。その方式は、実現可能なフローに対する近似値を、それが存在する場合に見つける。都合がよいことに、既存の試行錯誤的方法（例えば、「背景技術」の項において上述した試行錯誤的方法）とは違って、本発明の近似値係数が保証される。また、本発明によれば、その方式のパフォーマンスに対する下限が設定される。本発明の技法は広範なネットワークに適用可能であるが、
その技法は、特に、種々の電力消費モデルを有する静的ネットワーク及びゆっくり変化するエッジ・コストを有する動的ネットワークによく適合する。
【００３７】
本発明の方法が既存のルーティングを越えているという利点の一例は、本発明が分散ローカル制御方法であり、従って、ネットワークに関するグローバルな知識を持った中心ノードを必要としないということである。これは、本発明の方法が動的ネットワークにも十分に対処する１つの理由でもある。
【００３８】
（２）問題の数式化
このセクションでは、問題が更に正確に数式化され、線形計画法及びフロー変換処理の両方が提供される。
【００３９】
本発明のルーティング方式が実装されるべきネットワーク（例えば、図１におけるネットワーク１００のようなネットワーク）がＮ個のノード及びＭ個のエッジによって１つのグラフとして表される。それらのノードは無線装置を表し、エッジはそれらの間の無線リンクを表す。数量Ｅi が各ノードｉと関連付けられ、その装置の初期エネルギ予備量を表す。各エッジij はコストｅij を有し、そのコストは、対応するリンクを介して１つのデータ・パケットを伝送するために必要なエネルギである。
【００４０】
ルーティング問題は、ネットワークにおけるノードのペアであるＫ個のソース及び宛先ペアのセットを含む。各ペアは、スループット要件Ｑc、即ち、ソース・ノード及び宛先ノードの間を経路指定されなければならない１秒当たりのパケットの数、を有する。経路は、パケットが接続ｃのためのリンクij を介して伝送される速度を表す下記「数１」の変数によって与えられる。
【数１】
2006513602.tif 000003
【００４１】
（２.１）線形計画法の数式化
ネットワークの「ライフタイム」は、第１ノードの障害が生じる前の期間、即ち、或るノードのエネルギ予備量がゼロまで減少する前の期間、として定義される。本発明は、スループット要件が満たされている間、ライフタイムが最大にされるという態様でパケットを経路指定する。ライフタイムはＴによって示される。下記「数２」の変数は、ネットワークのライフタイムを通してノードｉからノードｊに伝送される接続ｃに関するパケットの合計数を示す。
【数２】
2006513602.tif 000004
【００４２】
ノードｉにおいて消費される合計のエネルギは、下記「数３」によって与えられる。但し、その和は、ノードｉに隣接したすべてのノード及びすべての接続ｃに関するものである。特定の接続ｃに対するソース及び宛先以外のすべてのノードにおいて、受信されたパケットの数が、送信されたパケットの数に等しい。ソース・ノードでは、送信されたパケットの数は、ネットワークのライフタイムＴの間、ＱｃＴに等しい。
【数３】
2006513602.tif 000005
【００４３】
従って、線形計画法は、
「１」  下記「数４」
「２」  下記「数５」
「３」  下記「数６」
になるようにＴを最大にするものである。なお、i は、別の方法では、ｃに対するソースである。
【数４】
2006513602.tif 000006
【００４４】
【数５】
2006513602.tif 000007
【００４５】
【数６】
2006513602.tif 000008
【００４６】
第２の制約は、ノードにおける有限の電源のためであり、第３の制約は、ソースにおけるスループット要件及び他のノードにおける保全（conservation）制約を表す。
【００４７】
この数式は、理論的には多項式時間で問題を正確に解くことが可能であることを示すように作用する。
【００４８】
（２.２）マルチコモディティ・フロー
ルーティング問題は、一般に、フロー問題として解釈することができる。上記「数１」の変数は、コモディティｃのフロー値として考えることができる。着信パケットが発信パケットと同じ速度で到着する要件は、いずれの中間ノードにおいても、着信フローの量が発信フローの量に等しいというフロー保全制約と同じである。ルーティング問題のソース及び宛先は、フロー問題ではソース及びシンクとなる。スループット要件Ｑc は、フローがソースにおいて生成され、シンクにおいて消費される速度を表す。従って、各瞬間において、ルーティングは、要件Ｑcを満たすマルチコモディティ（multicommodity）として表される。
【００４９】
各ラウンドが単位時間の間継続するという一連の同期ラウンドを続行するものとして、ネットワークの時間的進化（time evolution）が考えられる。各ラウンドにおいて、Ｑc のパケットが各ソース・ノードにおいて生成される。パケットはノード間で伝送されてもよく、各ノードのエネルギ予備量は、それが伝送するパケットのコスト全体だけ減少する。従って、fijがノードｉによってノードｊに伝送されたパケットの数である場合、ノードｉのエネルギ予備量はこのラウンドにおいてΣjeijfijだけ減少する。各ノードは多数の接続に対するパケットを実際に送ろうとしているので、エネルギの減少は下記「数７」によって与えられる。
【数７】
2006513602.tif 000009
【００５０】
問題の数式から、更に一般的なバージョンは、実行可能なマルチコモディティ・フローが時間と共に変化することを許される場合、そのフローを維持することができる多くラウンドを要求するためのものであると思われ、或る中間ノードは、その要求が実行不可能になる前に障害を生じるかもしれない。これは、第１ノードが障害生じるまでしか継続しない静的フローを通して達成し得るライフタイムの改善には通じないが、以下の説明から明らかなように、最大のライフタイムＴを得るフローは、時間ｔにおける下記「数８」であり、あらゆる瞬間における要求を満足する。この可変フローを下記「数９」におけるそれの時間平均によって置換されたい。
【数８】
2006513602.tif 000010
【００５１】
【数９】
2006513602.tif 000011
【００５２】
この静的フローはすべての瞬間において同じ要求を満足し、今や、ライフタイムＴの前に障害を生じるノードはないであろう。そのフローは静的であるので、ノードｉにおいて如何なるラウンドで消費されたエネルギもＥi/Ｔを超えることができない。
【００５３】
従って、それは、すべての要求を満足するマルチフローを見つけるには十分であり、Ｔのライフタイムを得るためには、すべてのｉに対して、下記「数１０」の式により制約される。この問題に対する近似法に関しては、次のセクションで説明することにする。
【数１０】
2006513602.tif 000012
【００５４】
（３）ローカル制御フロー方式
上記フローの説明によって本発明の方式を表すことにする。目標は、ライフタイムＴの所与の値が実現可能であるかどうかを決定することである。即ち、すべての要求が満たされるようにネットワークにおけるフローを経路指定することが可能であるか、及びＴラウンドを通過してしまう前にエネルギを使い尽くすノードがないかを決定する。
【００５５】
要求Ｑc を完全には満足しないがかなり満足するマルチフロー、即ち、或るパラメータ &#8714;＞０に対して要求(１＋&#8714;)Ｑc が存在するものと仮定する。
【００５６】
従って、本発明は、下記のような原理「１」を提供する。即ち、
原理「１」：  要求（１＋&#8714;）Ｑc が実行可能である場合、８ＭＬ(Ｋ＋ｌｎ(６Ｋ/&#8714;))/&#8714;δ ラウンドに対して実行した後、いずれのδ＞０に対しても要求(１−δ)Ｑcを満足するルーティング方式が存在する。
【００５７】
この原理「１」は、そのような方式を実際に説明すること及びそのパフォーマンスの完全な分析を与えることにより以下で証明されるであろう。本発明の方法によれば、各ノードがそれのエネルギ予算量Ｅi/Ｔ に注意しなければならないので、制約がそれらのノードに関するものであることは当然である。
【００５８】
（３.１）説明
各ノードは、そのリンクの各々に対してＫ個のキューを維持する。各ラウンドにおいて、或るキューにおけるフローがリンクの他端まで移動することがある。フローは、単一のノードにおけるキューの間で再配分されてもよい。
【００５９】
ノードｉにおけるリンクij 上のコモディティｃに対するキューの高さが下記「数１１」によって示される。リンクは、それの他端において下記「数１２」によって示されたもう１つのキューを有する。
【数１１】
2006513602.tif 000013
【００６０】
【数１２】
2006513602.tif 000014
【００６１】
すべてのキューに関連したポテンシャル関数φ(ｑ)が定義される。但し、ｑは、キューの高さである。そのポテンシャル関数は、その方式のパフォーマンスが以下において分析されるとき、完全に明確化され、差し当たり、それが２回微分可能な凸関数であることに注目されたい。その方式は、すべてのキューのポテンシャル関数の和を最小にするように動作する。
【００６２】
次に、図３を参照すると、本発明の実施例に従って、ルーティング方式（本願では、「コア」方式と呼ばれる）が流れ図によって示される。方式３００の各ラウンドにおいて、以下のフレーズ（ステップ）が実行される。
・  フローの導入（ステップ３０２）：  各コモディティｃに関し、対応するソースにおいてＱcのフローを加える。
・  ノードの平衡化（ステップ３０４）：  各ノードにおけるキューを等しくする。
・  フローの推進（ステップ３０６）：  エッジ ij に対する上記「数１１」及び「数１２」のキューの各ペアと、キューの高さがより大きいノードとを関連付ける。ポテンシャルを減少させるために、より高いキューからより低いキューにパケットが移動する（これはφの凸面から生じる）。従って下記の関数（「数１３」参照）は最少にされる。ただし、その和はノードｉに関連したエッジijを超え、変数は下記「数１４」の制約を受ける上記「数１」である。
【数１３】
2006513602.tif 000015
【００６３】
【数１４】
2006513602.tif 000016
【００６４】
そこで、上記「数１」が、ノードｉからノードｊにフローを移動させるために使用される。
・  フローの終了（ステップ３０８）：  コモディティｃに関してフローをそれのシンクにおいて吸収する。即ち、シンクにあるコモディティｃに関しすべてのキューの高さをゼロに設定する。
【００６５】
（３.２）分析
時間が経過しても、システムにおけるポテンシャルは制限されたままであることがわかるであろう。それは、ネットワークに導入されたほとんどのフローが適切なシンクに到達するということを意味する。
【００６６】
この概念は、その方式が実施するものと、そのフローが代わりに実行し得るマルチフローに従って選ばれた場合に生じるものと、を比較することによって、１つのラウンドにおけるポテンシャルの降下に下限を設けることである。一方、これは、その方式が反復的に実行されるとき、ポテンシャルが大きくなり得る上限を意味するであろう。
【００６７】
数式の記載を簡単にするために、ソース・ノード及び宛先ノードは両方とも単位等級を有し、各コモディティに対する要求が単一性を持つようにすべてのフロー及びキューがスケーリングされるものと仮定する。
【００６８】
最初の２つのフェーズ後におけるポテンシャルの上昇は、精々、下記「数１５」のようであろう。但し、ｓｃは、フロー導入後のソース・ノードにおけるコモディティｃの合計量である。
【数１５】
2006513602.tif 000017
【００６９】
フローが推進されるとき、ポテンシャルは降下し、そのポテンシャルの降下を算定するために、計算された最小のフロー値の代わりに、要求（１＋&#8714;）を満足させる下記「数１６」の実現可能なフローが使用される。
【数１６】
2006513602.tif 000018
【００７０】
その数式は、下記「数１７」である。その総計はネットワークにおけるすべてのエッジに及ぶものであり、この数式における下記「数１８」及び「数１９」は、それぞれ、エッジの先端及び末端におけるコモディティｃに対するキューの高さを示す。
【数１７】
2006513602.tif 000019
【００７１】
【数１８】
2006513602.tif 000020
【００７２】
【数１９】
2006513602.tif 000021
【００７３】
拡張中間値の法則がφに適用され、その数式は下記「数２０」のように簡約される。但し、この数式におけるζet 及びξeh は０と１との間の適当な定数である。第１の派生的用語はソース及びシンクにおける以外では相殺することに留意されたい。それは、ノード平衡フェーズでは、所与のノードにおける所与のコモディティに対するすべてのキューの高さが等しくされ、上記「数１４」のフローがフロー保全特性を満足するためである。第２の派生的用語がその和に対して非常にわずかな貢献しか行わないようにポテンシャル関数が選ばれる。更に詳しく言えば、それらの貢献は、精々、(&#8714;/２)φ’(ｓc)であると仮定する。従ってポテンシャルの降下は少なくとも下記「数２１」のようになる。
【数２０】
2006513602.tif 000022
【００７４】
【数２１】
2006513602.tif 000023
【００７５】
従って、そのラウンド中の全体では、ポテンシャルは少なくとも下記「数２２」だけ降下する。
【数２２】
2006513602.tif 000024
【００７６】
低い高さのキューから高い高さのキューにフローを移動させる上記「数１６」のフロー値が無視される場合、ポテンシャルの降下が改善されないということに留意されたい。本発明の方式は、最小化するけれどもすべてのそのような実施可能な更新を考慮するので、それが見つけるポテンシャルの降下は今導出されたものよりも良好であろう。
【００７７】
Ｓが下記「数２３」の等式を満足する値であると仮定する。
【数２３】
2006513602.tif 000025
【００７８】
従って、いずれのコモディティに対しても ｓc≧Ｓ である場合、そのラウンド中のポテンシャルの降下は負でないであろう。ネットワークにおけるコモディティｃの量は、Ｓを超える高さのキューがないことを示すことによって、２ＭＳに制限される。
【００７９】
これを達成するために、各ソース・ノードにおいてオーバフロー・バッファが使用される。その概念は、ソース・ノードにおけるキューがＳに達した場合、更なる導入されたフローが特別のオーバフロー・バッファに置かれ、そのオーバフロー・バッファは、それがｂの量のコモディティを有する場合、ポテンシャルｂφ’(Ｓ)を有するということである。このポテンシャル関数によって、フローが導入されたときのポテンシャルの上昇は、φ’(ｓc)によって上限設定されたままである。ソース・キューを限界設定することの利点は、他のキューがこの限界を超えることができないということである。従って、キューの高さの特定な値、この場合はＳ、が与えられると、この高さを超えるべき第１のキューはソース・ノードになければならないことが容易にわかる。
【００８０】
次に、ポテンシャルがいつも２ＭＫφ(Ｓ)よりも小さくなければならないということをラウンドの数に関して帰納法により示す。オーバフロー・バッファがすべてのコモディティに対して空いている限り、これは真実である。一方、フロー導入フェーズが或るソース・キューをオーバフローさせる場合、実際には、このラウンド中、ポテンシャルは降下する。
【００８１】
従って、オーバフロー・バッファの最大サイズは２ＭＫφ(Ｓ)/φ’(Ｓ)である。この結果は次のセクションにおいて必要であるので、それを下記のような原理「２」として言い換える。即ち、
原理「２」：  Ｓが下記「数２４」の等式を満たす場合、オーバフロー・バッファの最大サイズは、２ＭＫφ(Ｓ)/φ’(Ｓ)である。
【数２４】
2006513602.tif 000026
【００８２】
エッジ・キューにおけるコモディティｃの最大量は２ＭＳであり、従って、これをオーバフロー・バッファに関する上限に結合すると、システムにおけるコモディティの合計量に関する２ＭＫφ(Ｓ)/φ’(Ｓ)という上限が得られる。
【００８３】
次に、α＝&#8714;/４Ｌに対するポテンシャル関数φ(ｑ)＝ｅαq が設定される。但し、Ｌは上記「数１４」の実行可能フローにおける最長のフロー・パスの長さに関する上限である。これは十分に小さい &#8714; に対して、下記「数２５」の数式を与える。
【数２５】
2006513602.tif 000027
【００８４】
Ｓに対する等式は、Ｓ≦４Ｌ１ｎ(６Ｋ/&#8714;)/&#8714;となる。従って、システムにおける所与のコモディティの合計量は、精々、Ｒ＝８ＭＬ(Ｋ＋１ｎ(６Ｋ/&#8714;))/&#8714; である。
【００８５】
本方式は、Ｒ/δラウンドに対して連続的に稼動するものと仮定する。ネットワークに導入されたコモディティｃの量はＲ/δであり、ネットワークに残っている量は、精々、Ｒである。従って、ネットワークを介して搬送されるコモディティの１ラウンド当りの平均的な量は１−δである。これは、上記の原理「１」を立証する。
【００８６】
関連あるもう１つのパラメータは、本発明の方式によって経路指定される間に、パケットが体験する平均的な遅延である。システムにおけるコモディティの量は長い実行時間ではＲにより制限されるので、リトルの法則によって、平均的な遅延もＲにより上限設定される。
【００８７】
従って、原理「３」は、次のように記述することが可能である。
原理「３」：  パケットの平均的遅延は、精々、８ＭＬ(Ｋ＋１ｎ(６Ｋ/&#8714;))/&#8714; である。
【００８８】
（４）ライフタイムの最大化
次に、最大のライフタイムに適したルーティングに収斂するためにこの方式を使用する方法に関する説明を行う。集中制御が利用可能であり、すべてのノードにおいて同時に情報を更新することが可能であるものと一時的にみなすことにする。
【００８９】
ノード制約がＥi/Ｔにセットされ、Ｔは、それが最適値Ｔ*に収斂するまで変化する。その概念は、Ｔが大きすぎる場合、実行可能なフローを許容するにはノード制約が厳しすぎ、従って、制限がなくてもソース・キューは成長するであろうということである。実際のライフタイムよりも小さい値でＴを開始させ、オーバフロー・バッファが制限２ＭＫφ(Ｓ)/φ’(Ｓ)を超えたことがわかるまでそれを増加させることが可能である。そこで、２倍以内までの最適ライフタイムＴ*を知り、それを正確に決定するために交差サーチを遂行することが可能となる。
【００９０】
最適ライフタイムＴ*を&#8714; の相対的誤差内に決定することが望ましいものと仮定する。最適ライフタイムＴ*よりも小さいと仮定した適当な値Ｔ0 にＴを初期設定する。２Ｒラウンドの間その方式を実行させる。オーバフロー・バッファが制限２ＭＫφ(Ｓ)/φ’(Ｓ)を超えない場合、ネットワークを介して搬送されたコモディティの平均的な部分比率は原理「１」によって少なくとも半分であることがわかる。
【００９１】
要求λＱc を制約Ｅi/Ｔによって満たすことができる場合、すべてのフロー値の１/λによるスケーリングは、要求Ｑcを制約Ｅi/λＴでもって満足させ得ることを示す。従って、要求Ｑc/２が制約Ｅi/Ｔでもって平均して満たされる場合、要求Ｑcが制約２Ｅi/Ｔによって満たされ、従って、Ｔ*≧Ｔ/２であることがわかる。Ｔは２倍にされ、別の２Ｒラウンドの間実行される。このプロセスは、オーバフロー・バッファが２ＭＫφ(Ｓ)/φ’(Ｓ)の上限まで急増させられるまで、即ち、Ｔ＝Ｔ1 になるときまで、反復される。この時点では、(１＋&#8714;)Ｔ1 ≧Ｔ* ≧Ｔ1/４  であることがわかる。
【００９２】
その上限は、要求(１＋&#8714;) Ｑc が制約Ｅi/Ｔ1でもって実施可能であった場合、原理「２」によって、オーバフロー・バッファが２ＭＫφ(Ｓ)/φ’(Ｓ)を超えることができないためのものである。
【００９３】
たとえ２Ｒラウンド全体が実行されてしまわなくても、オーバフロー・バッファがその限界に達すると、直ちにこの方法は停止する。このため、個々のバッファにおいて生じ得る最大のオーバシュートは１単位であり、それはφ’(Ｓ)のポテンシャル・オーバシュートに対応する。限界２ＭＫφ(Ｓ)以下にポテンシャルを戻すために、オーバシュートしたソースにおける如何なるパケットも導入することなく、その方法の１ラウンドが実行される。ソースのオーバフロー・バッファのＫ’がそれらの限界を超えるものと仮定する。その場合、このラウンドが生じるポテンシャルの降下は少なくともＫ’φ’(Ｓ) になるであろうし、従って、これは、２ＭＫφ(Ｓ)以下にポテンシャルを下げるに十分であろう。
【００９４】
Ｔ*に関する上限を見つけるこのプロセス中にノードｉにおいて消費される電力は、精々、次のようになる。
２ＥiＲ((１/Ｔ0)＋(１/２Ｔ0)＋・・・)≦４ＥiＲ/Ｔ0
【００９５】
上限及び下限が得られると、Ｔ*の値をもっと正確に決定するためのサーチが行われる。第１の方法は、交差サーチを使用して、Ｒ/&#8714; ラウンドがサーチ期間をほぼ半分にカットするようにこの方式を実行することである。しかし、第２のサーチ技法はサーチ時間をかなりカットする。Ｔh及びＴl が現在の上限及び下限である（最初は、Ｔh ＝Ｔ1 及びＴl ＝Ｔ1/４）場合、テスト値Ｔ＝(２Ｔh＋Ｔl)/３がＴh からＴl までの過程の１/３に選択され、この方式がＲ/δラウンドの間実行される。なお、δ＝(Ｔh−Ｔl)/３Ｔである。この概念は、これらの多くのラウンド内でソースのオーバフロー・バッファがその限界を超えない場合、原理「１」によって、
(１+&#8714;)Ｔｈ≧Ｔ* ≧Ｔ(１−δ)＝(Ｔh＋２Ｔl)/３
となり、いずれかのバッファがその限界を超える場合、下記のようになる。
(１+&#8714;)Ｔ1 ≧Ｔ* ≧Ｔ1
【００９６】
いずれの場合も、サーチ期間が２/３だけ減少する。これらのＲ/δラウンド中にノードｉにおいて消費される（理想的なＥi/Ｔ*を超える）過剰電力は、精々、下記「数２６」のようになる。
【数２６】
2006513602.tif 000028
【００９７】
このサーチ・プロセス中に費やされたラウンドの数は、精々、下記「数２７」のようになり、ノードｉにおける過剰電力消費量の合計は、下記「数２８」のようになる。
【数２７】
2006513602.tif 000029
【００９８】
【数２８】
2006513602.tif 000030
【００９９】
従って、Ｔ*の正確な値に収斂するために費やされるラウンドの合計数は下記「数２９」のようになる。
【数２９】
2006513602.tif 000031
【０１００】
残りのラウンド中、ラウンド当たりの消費される電力は、精々、Ｅi/(１−&#8714;)Ｔ*である。従って、下記「数３０」の場合、ノードは、少なくとも、(１−２&#8714;)Ｔ*ラウンドの間継続する。
【数３０】
2006513602.tif 000032
【０１０１】
従って、Ｔ0 ＝８Ｒ/&#8714; が選択される場合、及び下記「数３１」の場合、そのノードの残りのライフタイムは、少なくとも、(１−２&#8714;)Ｔ*である。
【数３１】
2006513602.tif 000033
【０１０２】
更に、原理「４」は、次のように記述することが可能である。即ち、
原理「４」：  下記「数３２」のような場合、(１−２&#8714;)Ｔ*のライフタイムを得るルーティング・プロトコルが存在する。
【数３２】
2006513602.tif 000034
【０１０３】
Ｔ*という所与の値に対して、最良の可能な限界を得るために、下記「数３３」の等式が選択されるべきである。この等式において、ｆ＝Θ(ｇ) は、ｃ1ｇ≦ｆ≦ｃ2ｇ になるようにｃ1 及びｃ2が存在することを意味することを理解すべきである。
【数３３】
2006513602.tif 000035
【０１０４】
（５）実装態様
このセクションでは、ここまでに示された方式の実装に関連した３つの問題点を考察する。第１の問題点は、これまでは、フローが連続的な量として処理されてきたことである。しかし、ルーティングでは、一般に、パケットを分割することは望ましくない。従って、キューは、それらが整数個のパケットを含むように切断され、１つのパケット全体が一時に経路指定される。第２の問題点は、ノードにおけるポテンシャル関数を最小にするフロー値を計算することである。第３の問題点は、上で分析された集中態様ではなく、分散態様で最大ライフタイムに収斂する方法である。
【０１０５】
実際に生じるもう１つの問題点は、トラフィックがスムーズな決定論的な態様では生じないということである。これを処理するために、「漏れ易いバケツ（leaky bucket）」がソースごとに付加されてトラフィックをスムーズにする。
【０１０６】
（５.１）フローの切断
この方式のノード再平衡化フェーズが、各キューにおいて整数個のパケットを維持しながらキューを再平衡化するように修正される。これは、キューの実際の高さがその理想的な高さから１パケット分まで異なることを意味する。
【０１０７】
これは、この方式の分析に誤差期間を導入する。エッジｅにまたがる上記「数１６」のフローを経路指定することによってポテンシャルの降下を引き出すときに下記「数３４」の式が得られる。
【数３４】
2006513602.tif 000036
【０１０８】
第１の期間は、その理想的な値（ｑが連続的に変化することを可能にされるときの値）とは下記「数３５」だけ異なることがある。但し、上記「数３５」における下記「数３６」及び「数３７」の値は−１と＋１との間である。
【数３５】
2006513602.tif 000037
【０１０９】
【数３６】
2006513602.tif 000038
【０１１０】
【数３７】
2006513602.tif 000039
【０１１１】
この和は、精々、下記「数３８」である。
【数３８】
2006513602.tif 000040
【０１１２】
従って、これは、この方式の分析に余り影響を与えるものではない。
【０１１３】
（５.２）ポテンシャルの最小化
各ノードにおいて解決すべき問題点は、下記「数３９」を仮定して下記「数４０」を最小にすることである。
【数３９】
2006513602.tif 000041
【０１１４】
【数４０】
2006513602.tif 000042
【０１１５】
ラグランジュ乗数の手法を使用すると、上記「数１」の変数が下記「数４１」のようにシステムを満足させる。
【数４１】
2006513602.tif 000043
【０１１６】
従って、その量の最大値がエッジij 及び接続ｃに関して下記「数４２」により計算される。なお、「数４２」（最小ポテンシャルの解に達するときには等しくなければならない）はそのエッジ及び接続に対して１つのパケットを経路指定する。キューの高さが更新され、プロセスは、エネルギの貯えＥi/Ｔが尽きるまで繰り返される。
【数４２】
2006513602.tif 000044
【０１１７】
（５.３）分散実装態様
この方式の中心部（セクション３において上述した）が、分散態様で明白な方法により実装することが可能である。ライフタイムを最大にする作業を行うための分散プロトコル（セクション４において上述した）を、更に困難なタスクが定義する。なお、そのような分散プロトコルに関して後述することにする。
【０１１８】
この概念は、各ソースのオーバフロー・バッファが限界２ＭＫφ(Ｓ)/φ’(Ｓ)に達するたびに、各ソースがブロードキャスト（データ・パケットと共に各近隣ノードに送られた）を送出するということである。各ノードは、精々、Ｎ個のラウンドにおいてそのブロードキャストを受け取る。
【０１１９】
初期のフェーズでは、２Ｒ個のラウンドごとに、すべてのノードがそれのローカル値Ｔを２倍にする。次のＮ個のラウンド中、それはソースからのブロードキャスト・メッセージを受け取り、次のフェーズにスイッチし、そしてそのブロードキャストを送る。
【０１２０】
第２フェーズでは、各ノードが上限Ｔh 及び下限Ｔl を維持し、それのローカル・エネルギ予算量を決定するためにテスト値 Ｔ＝(２Ｔh＋Ｔl)/３ を計算する。Ｒ/δ＋Ｎラウンドの後、受信されるソース・ブロードキャストがない場合、Ｔl の値が(Ｔh＋２Ｔl)/３に更新される。ブロードキャストが受信される場合、Ｔh の値がＴに更新される。これは、Ｔ*の値が（相対的誤差 &#8714; 内に）決定されるまで継続する。
【０１２１】
次に、図４を参照すると、本発明の実施例によるルーティング方式（本願では、分散ルーティング方式と呼ばれる）のブロック図が示される。各ノードにおいて実行される方式４００は、次のように要約することができる。
・  初期設定（ステップ４０２）：Ｔ＝Ｔ0 をセットする。
・  上限Ｔh の設定（ステップ４０４）：２Ｒ＋Ｎラウンドが終わるか、ブロードキャストが受信されるか、又は（当該ノードがソースである場合）オーバフロー・バッファが２ＭＫφ(Ｓ)/φ’(Ｓ)に達するまで、コア方式を実行する。２Ｒ＋Ｎラウンドが終わってしまった場合、Ｔを２倍にしてこのステップを繰り返すか、又は、そうでない場合、次のステップに進む。
・  ブロードキャスト（ステップ４０６）：ブロードキャスト・メッセージが受信された場合、それを近隣ノードに送り、さもなければ、新たなメッセージを作成する。
・  サーチ初期設定（ステップ４０８）：Ｔh ＝Ｔ及びＴl ＝Ｔ/４をセットする。
・  サーチ（ステップ４１０）：Ｔ＝(２Ｔh＋Ｔl)/３、δ＝(Ｔh −Ｔl)/３ を計算する。Ｒ/δ＋Ｎラウンドが終わるか、ブロードキャストが受信されるか、又は（当該ノードがソースである場合）オーバフロー・バッファが２ＭＫφ(Ｓ)/φ’(Ｓ)に達するまで、コア方式を実行する。
・  更新（ステップ４１２）：Ｒ/δ＋Ｎラウンドが終わってしまった場合、Ｔl＝(Ｔh ＋２Ｔl)/３をセットする。そうでない場合、Ｔh ＝(２Ｔh＋Ｔl)/３をセットしてブロードキャストを送るか、又は新たな値を生成する。(Ｔh −Ｔl)/Ｔl≧&#8714;である場合、サーチ・ステップに戻る。
【０１２２】
この分散プロトコルの分析は集中プロトコルと同じであり、ＮがＲに比べて小さいので小さい定数を除けば同じ限界を生じる。
（５.４）任意のトラフィック・ソース
【０１２３】
実際には、トラフィックは、これまで仮定されたスムーズな決定論的態様では到着せず、本来は、間歇性又はバースト性のものである。これを処理するために、ソースごとに「漏れ易いバケツ」が付加され、トラフィックをスムーズにする。「漏れ易いバケツ」は
トラフィック・フローをスムーズにするためにネットワーク・アプリケーションにおいて使用されるコントローラである。この概念は、毎秒ρ個のトークンが生成され、トークンがρよりも多く存在する場合、それらのトークンが排除されるということである。各パケット伝送が１つのトークンを消費する。利用可能なトークンがない場合、それらが利用可能になるまで、パケットがバッファされる。そのようなコントローラは伝送されるトラフィックを制限する。タイム・インターバルＴにおいて伝送されるパケットの数はρＴ＋σ超えることができない。本願では、トラフィックが完全にスムーズにされるように、σがゼロである特別のケースが使用される。
【０１２４】
（５.５）方式の加速
遅延は意外に速く大きくなることが実感される。長さＬの経路において、パケットが直面する遅延は、キューがソースからシンクまで線形に減少するので、（適切なフローに収斂した後）Ｌ2 として大きくなる。この遅延を減少させるために及び収斂を加速するために、本方式は、以下の態様で修正することが可能である。エッジを介して送られるべきフローは、或る履歴を使用することによって修正することが可能である。即ち、実際のフローは、オリジナルの方式（又は、１次的方法）が選んだフローの線形結合として計算される。２つのコンポーネントの係数の適当な選択に関しては、この新たな２次的方法では収斂を加速させることが可能である。前のステップにおけるフローの係数が１に近い場合、最終的なキューの高さは１次的方法におけるよりも小さく、従って、遅延を減少させる。
【０１２５】
従って、２次的方法における実際のフローは次式のように計算される。即ち、
ｆ＝αｆ0 ＋βｆ’
但し、ｆ0 は１次的方法によって与えられたフローであり、ｆ ’は前のステップにおいて送られたフローであり、βは適当なパラメータである。α＋β＞１であるとき、収斂はかなり加速される。βが１に近ければ近いほど、及び、αの値が大きければ大きいほど、最終的なキューの高さは小さくなり、収斂は速くなる。しかし、αが大きすぎる場合、この方式は不安定になることがある。
【０１２６】
パス・グラフの簡単なケースに対しては、正確な分析を行うことが可能である。パス・グラフは、α＜１＋βである限り、２次的方法が安定していることを示す。
【０１２７】
この方法は、実際のキューの高さよりも大きいフロー値を要求することがある。これを処理するためには、次の２つの方法がある。
１．これが生じたときに可能な最大値を送り、残りを無視する、又は
２．要求された過剰なフローが記憶され、可能な場合、その後のタイム・ステップｊに送られる。
【０１２８】
（５.６）別の実装態様及びシミュレーション結果
この方式の単純化された実用的な実装態様では、指数関数よりも、むしろキューの高さのちょうど２乗となるように、ポテンシャル関数が要求されることがある。
【０１２９】
更に、真のライフタイムをサーチするために分散プロトコルを使用する代わりに、フローのコストの２乗に比例した期間、即ち、下記「数４３」を加えることによって、ポテンシャル関数を修正することが可能である。
【数４３】
2006513602.tif 000045
【０１３０】
これは、定数αが適切に選択される限り、非常によく作用する。この修正されたポテンシャル関数を用いると、ポテンシャルを最小にするためのフロー値の選択は、素早く且つ正確に行うように合理的に簡単になる。
【０１３１】
シミュレーションに関しては、正方形の領域においてポイントを無作為に生成することによって、グラフが生成された。Lecture Notes in Computer Science: Networking 2000 誌の vol. 1815、pp.702-713, May 2000 における「無線アド・ホック・ネットワークにおける最大ライフタイム・ルーティングのための高速近似法アルゴリズム（FastApproximation Algorithms for Maximum Lifetime Routing in Wireless Ad-hocNetworks）」と題した J.H. Chang 氏他による論文の方式を使用して、先ず、最大ライフタイムを計算すること、ラウンドのライフタイム数に対する第１次及び第２次の方法の両方を実行すること、及び実際にシンクに到達したフローの数を書き留めることによって、パフォーマンスが測定された。
【０１３２】
αを適切に選ぶことは、主として、それが小さ過ぎないことを確認することであるということを、シミュレーションは示している。大きい値は、配布されたフローの合計を減少させるが、わずかに減少するだけである。
【０１３３】
（６）ローカル制約に対する拡張
本発明の方式は、ノード、エッジ、又はそれの両方に関して広範な種々の制約に対して作用する。
【０１３４】
上記のコア方式の証明から、要求１＋&#8714; を満足させ且つすべての制約に適合するフローが存在する限り、その方式がローカル制約（ノーダル制約及びエッジ容量制約の両方）の如何なる組み合わせに対しても作用することになる。これらの制約は、ポテンシャルの最小化を行うことが可能である限り、線形である必要はまったくない。
【０１３５】
（６.１）アイドル電力
一般に、無線ノードでは、通信は単なるエネルギ消費者である。そのノードは、それが伝送するパケットの数に関係ない比率で電力を消費する何らかの計算又はデータ収集を行っていることがある。また、無線インターフェースは、アイドル時でも、或いは、如何なるパケットも受信又は送信していないときでも、電力を消費する。これらの要素を考慮するために、ノード・エネルギ制約に一定の電力消費量Ｃi が加えられると、ノード制約は下記「数４４」のようになる。
【数４４】
2006513602.tif 000046
【０１３６】
コア方式は、この変化によってもまったく影響されない。ライフタイム最大化プロトコルが依然として作用することを示すために確認される必要がある唯一のことは、要求λＱc がライフタイムＴによって満足される場合、要求Ｑc はライフタイムλＴによって満足されるという拡張的な想定である。これは、上記「数１」のフロー値が要求λＱcを得る場合、下記「数４５」のフローがＱc を満足するであろうし、λ≦１の場合、下記「数４６」を満足するであろう。なお、そのλ≦１は、この結果が適用されるとき（セクション４におけるλ＝１−δ）、いつも、真である。
【数４５】
2006513602.tif 000047
【０１３７】
【数４６】
2006513602.tif 000048
【０１３８】
（６.２）定期的な再充電
興味あるケースは、いずれかのノードが定期的に、即ち、Ｔi 秒ごとに再充電されるときである。この場合、このノードに対する制約の右側がＥi/Ｔi でもって置換することが可能である。それは、そのノードの次の再充電まで、そのノードだけは生き延びなければならないためである。このノードは、制御パケットを送ることを除いて、プロトコルのライフタイム決定フェーズには参加しない。
【０１３９】
（６.３）エッジ制約
エッジ制約、例えば、帯域幅制約を組み込むことも可能である。各ノードでは、下記「数４７」のエネルギ制約のほかに、下記「数４８」の更なる制約が含まれる。但し、Ｂij は、パケットがリンクij を介して伝送される可能な最大速度である。それは、おそらく、信号対インターフェース比率（ＳＩＲ）の要件のためである。
【数４７】
2006513602.tif 000049
【０１４０】
【数４８】
2006513602.tif 000050
【０１４１】
非線形の電力従属性を許すようにエネルギ制約を修正することも必要であることがある。例えば、送信装置を使用することに関連した初期起動コスト、或いは、他端におけるノードを用いて無線リンクを設定するための初期起動コストが存在することがある。これは、必要な電力全体のうちのかなりの部分となることがある。これは、本発明の方式に従って実装することが可能である。
【０１４２】
（６.４）受信電力
送受信機は、送信モード及び受信モードにおいて動作するときに電力を消費する。ネットワークがかなり静的なものである場合又はゆっくりと進化している場合、これは、パケットが受信されるときよりも実際に送られるときにそれを充電することにより考慮される。任意のノードにおけるすべての、しかし、限定された数のパケットが送られるので、１つのパケットを受信するために必要なエネルギが、ノード制約においてそれを送信するために必要なエネルギに加えられる。それは、下記「数４９」の形式をとる。なお、その「数４９」における下記「数５０」は送信ための１パケットあたりのエネルギであり、下記「数５１」は受信及び解読のための１パケットあたりのエネルギである。
【数４９】
2006513602.tif 000051
【０１４３】
【数５０】
2006513602.tif 000052
【０１４４】
【数５１】
2006513602.tif 000053
【０１４５】
（６.５）動的ネットワーク
セクション３において説明したコア方式は、ネットワークが動的である場合でも作用し、エッジ・コストは、要求Ｑcを満足するマルチコモディティ・フローが存在することが真実である限り、時間と共に変化している。
【０１４６】
しかし、変化するエッジ・コストのため、ライフタイムが変化することはあり得ることである。いずれかのソースのオーバフロー・バッファがその限界に達する場合、Ｔの現在値は高すぎ、Ｔh ＝Ｔ及びＴl＝０と共に分散プロトコルを使用して、新たなサーチを開始することが可能である。Ｔの現在値が低すぎる場合、これは、ライフタイム最大化プロトコルが再始動されなければ検出されないであろう。これは、少なくともＲ/&#8714;ラウンドが済んでしまった後、開始値Ｔ0 の代わりにＴの現在値を使用して行うことができる。この多くのラウンドを待つことは、パケットの１−&#8714;部分が適切な宛先に送信されることを保証する。従って、ネットワークにおける変化の速度がこれよりも遅い場合、ネットワークが進化するときライフタイムは、追跡することが可能である。
【０１４７】
７．ノードにおける例示的判断フロー
従って、セクション１乃至６において例示的に説明したように、本発明は、ネットワーク・トラフィックを流体の流れになぞらえている。そのような類比を使用すると、ノードにおけるデータ・バッファは流体の容器と考えられる。その場合、バッファの高さは圧力に対応する。既知のように、流体は高さを均一化しようとする。従って、ネットワーク・トラフィックに関して、本発明の技法は、近隣ノードにおけるキューの高さについてのローカル情報に基づいてルーティングの決定を行う。
【０１４８】
有利なこととして、各ノードでは、キューがエッジ全体にわたって均一化される。パケットは、各エッジに関して、高いキューから低いキューに経路指定される。このような経路指定は、高コストのエッジを介して少ないデータが経路指定されるように、エネルギ予算量によって拘束される。更に、エッジと接続との間にはトレード・オフが存在し、そのようなトレード・オフはポテンシャル関数（例えば、上記のφを参照）によって制御される。
【０１４９】
次に、図５を参照すると、図示の流れ図は、本発明による分散ルーティング方式のための各ノードにおける判断フローを示す。判断フロー５００はブロック５０２で開始する。ステップ５０４において、パケットが到着したかどうかをノードが決定する。その決定の結果が肯定的である場合、ステップ５０６において、ノードは、パケットがそのノードに対するものであるかどうかを決定する。この結果が肯定的である場合、そのパケットはステップ５０８において受け付けられ、プロセスはステップ５０４に戻る。パケットがそのノードに対するものでない場合、ステップ５１０において、そのパケットはローカル・キューに入れられる。プロセスは、ステップ５０４に戻る。
【０１５０】
ステップ５０４における初期の決定に戻ると、到着したパケットがない場合、ノードは、ステップ５１２において、それのローカル・キューに何らかのパケットが存在するかどうかを決定する。その決定の結果が否定的である場合、プロセスはステップ５０４に戻る。その決定の結果が肯定的である場合、ステップ５１４において、ノードは、もっと短いキューを有する近隣ノードがあるかどうかを決定する。この結果が否定的である場合、プロセスはステップ５０４に戻る。この決定の結果が肯定的である場合、ステップ５１６において、パケットはその近隣ノードに送られる。
【０１５１】
添付図面を参照して本発明の実施例を説明したが、本発明がこれらの実施例に限定されないこと、及び本発明の範囲又は真意から逸脱することなく、当業者により行われる他の種々の変更及び修正が可能であることはいうまでもない。
【図面の簡単な説明】
【０１５２】
【図１】本発明の技法を実装し得る無線アド・ホック・ネットワークを示すブロック図である。
【図２】本発明の教示事項を実装するために使用し得るコンピュータ・システムの例を示すブロック図である。
【図３】本発明の実施例による主要なルーティング方式を示す流れ図である。
【図４】本発明の実施例による分散ルーティング方式を示す流れ図である。
【図５】本発明の実施例による分散ルーティング方式のための各ノードにおける判断フローを示す流れ図である。
【図１】
2006513602.tif 000054
【図２】
2006513602.tif 000055
【図３】
2006513602.tif 000056
【図４】
2006513602.tif 000057
【図５】
2006513602.tif 000058
【国際調査報告】
2006513602.tif 000059
2006513602.tif 000060
2006513602.tif 000061