トップ :: H 電気 :: H04 電気通信技術




【発明の名称】 仮想座標を取得する方法及び装置
【発明者】 【氏名】ドミニク・チョップ

【氏名】イェルク・ヴィドマー

【氏名】スハス・ディッガヴィ

【氏名】マティアス・グロスグラウザー

【氏名】クリスティアン・プレホーファー
【要約】 【課題】移動性及び現実的なチャンネル条件の下でロバスト性があるビーコンに基づく埋め込みを提供する。

【構成】ノードの仮想座標を更新するためビーコン信号を定期的に送信するステップと、ビーコンノードの集合中のビーコンメッセージを送信するノードを、ビーコンの役割を引き継ぐ新しいノードと置き換えるステップを備え、置き換えが仮想座標の決定を改善するために所定の置き換えスキームに従って定期的に実行され、ある距離尺度に従ってビーコンノードの集合の中の第１のビーコンノードから他のビーコンノードまでの距離を決定し、距離尺度量が最小値をとったビーコンノードを選択し、選択されたビーコンノードまでの距離尺度を計算し、距離尺度量が第１のビーコンノードの距離尺度量より高いならば、第１のビーコンノードを距離尺度がより高い値をとった近傍ノードと置き換える。
【特許請求の範囲】
【請求項１】
アドホックワイヤレスネットワークのノードのロケーションの表現であり、前記ネットワーク内のビーコンノードの集合から送信されたビーコン信号に基づいている前記ノードの仮想座標を取得する方法であって、
前記ビーコン信号を受信するノードと前記ビーコン信号を送信したノードとの間の近接性を表す近接性尺度を決定するため前記ビーコン信号を使用するステップと、
前記近接性尺度に基づいて前記ビーコンを受信したノードの仮想座標を決定するステップと、
を含み、
前記ノードの前記仮想座標を更新するため前記ビーコン信号を定期的に送信するステップと、
前記ビーコンノードの集合に属し、かつ、ビーコンメッセージを送信するノードを、前記ビーコンの役割を引き継ぐ新しいノードと置き換えるステップと、
をさらに含み、
前記置き換えが前記仮想座標の決定を改善するために所定の置き換えスキームに従って定期的に実行され、
前記置き換えスキームが、
前記ビーコンノードの集合の中の第１のビーコンノードに関して、ある距離尺度に従って前記第１のビーコンノードから前記ビーコンノードの集合の中の他のビーコンノードまでの距離を決定するステップと、
距離尺度量が最小値をとったビーコンノードを選択するステップと、
前記第１のビーコンノードの近傍ノードに関して、前記選択されたビーコンノードまでの前記距離尺度を計算するステップと、
前記近傍ノードのうちの１つに関して、前記距離尺度量が前記第１のビーコンノードの距離尺度量より高いならば、前記ビーコンノードの集合の中の前記第１のビーコンノードを距離尺度がより高い値をとった前記近傍ノードと置き換えるステップと、
を含む、方法。
【請求項２】
ビーコンノードの初期集合をランダムに選択するステップと、
対応するビーコンノードから個々のノードまでビーコン信号が進むホップ数によってそれぞれ決定される前記ビーコンノードまでの距離に基づいて前記ネットワーク内の前記個々のノードの座標を決定するステップと、
前記ビーコンノードを含む前記ネットワーク内の全ノードに関して前記座標を決定するステップと、
このようにして決定された座標に基づいて、第１のビーコンノードに関して、別のビーコンノードまでの最小距離を決定し、前記第１のビーコンノードの近傍ノードがより大きな距離をとるならば、前記第１のビーコンを前記近傍ノードと置き換える置き換えスキームを実行するステップと、
前記ビーコンノードの集合の中の前記ビーコンノードの全てに関して前記置き換えスキームを繰り返すステップと、
を含む、請求項１に記載の方法。
【請求項３】
前記距離の差がある特定のスレッショルドを超えるという条件、
前記距離の差がある特定の期間に亘って存在し続けるという条件、
置き換えられるべき前記ビーコンノードが仮想空間内で移動したという条件、及び、
前記置き換えられるべきビーコンノードの近傍集合が変化したという条件
のうちの１つ以上の条件が満たされる場合に限り、前記ビーコンノードの前記置き換えを実行するステップをさらに含む、請求項１又は２の一項に記載の方法。
【請求項４】
前記ネットワークの前記ノード及び前記ビーコンノードの任意の仮想座標を選択するステップと、
前記ネットワーク内のノードに関して、前記ビーコンノードの集合の中の前記ビーコンノード毎に、前記ノードから前記ビーコンノードの各々までの距離を表す近接性尺度を前記ビーコンノードによって送信されたビーコンに基づいてそれぞれ決定するステップと、
前記ビーコンノードの集合の中のビーコンノード毎に前記仮想座標に基づいて前記ノードと前記ビーコンノードとの距離を表す距離尺度を決定するステップと、
前記ビーコンノードの集合の中のビーコンノード毎に、前記仮想座標に基づいて取得された前記距離尺度及び前記ビーコンノードによって送信された前記ビーコンに基づいて取得された前記近接性尺度が、シフトの量が前記ノードの前記仮想座標の修正ベクトルに対応するようなシフト後に一致すべきであるならば、前記ノードの前記仮想座標が前記ビーコンノードの方向へシフトされるべき量を決定するステップと、
修正ベクトルのベクトル和を決定し、次の反復で使用されるべき修正仮想座標を取得するために、得られたベクトルを前記ノードの前記仮想座標に加算するステップと、
前記置き換えスキームを適用した後に新しいビーコンノードの集合を使用して次の反復中に前記ステップを繰り返すステップと、
をさらに含む、請求項１〜３の一項に記載の方法。
【請求項５】
前記置き換えスキームが、
ある特定のノードがビーコンノードとしての機能を果たす確率を表すネットワークのノードに割り当てられた確率に基づいて前記ビーコンノードの集合の中の既存のビーコンノードを置き換える新しいビーコンノードをランダムに選択するステップと、
個別のノードがビーコンノードとしての機能を果たす順序を表す所定の順序に基づいて前記ビーコンノードの集合の中の既存のビーコンノードを置き換える新しいビーコンノードを選択するステップと、
のうちの一方を含む、請求項４に記載の方法。
【請求項６】
前記近接性尺度はビーコンが前記ネットワーク内でビーコンノードからノードへ進むホップ数に基礎を置き、
前記距離尺度は前記ネットワーク内のノードと前記ネットワーク内のビーコンとの間でそれぞれの仮想座標に基づいて計算されたユークリッド距離に基礎を置いている、請求項４又は５に記載の方法。
【請求項７】
近接性尺度又は距離尺度が、個別のノードに関して決定された値をこのノードの近傍ノードに関して取得された値と平均化することにより前記個別のノードに関して決定される、請求項１〜６の一項に記載の方法。
【請求項８】
ノードがビーコンノードとしての機能を果たす確からしさは、
前記仮想座標の安定性、
前記ネットワーク内のノード数、及び、
ビーコンノードに関する前記ノードの前記ロケーション
のうちの１つ以上のパラメータに基づいて適合される、請求項４〜７の一項に記載の方法。
【請求項９】
ネットワークを介して起点から宛先までメッセージを経路制御する方法であって、
前記起点から前記宛先へパケットを経路制御するルートを決定するため、請求項１〜８の一項に記載の方法を使用して決定された前記仮想座標を使用するステップを含む方法。
【請求項１０】
アドホックワイヤレスネットワークのノードのロケーションの表現であり、前記ネットワーク内のビーコンノードの集合から送信されたビーコン信号に基づいている前記ノードの仮想座標を取得する装置であって、
前記ビーコン信号を受信するノードと前記ビーコン信号を送信したノードとの間の近接性を表す近接性尺度を決定するため前記ビーコン信号を使用するモジュールと、
前記近接性尺度に基づいて前記ビーコンを受信した前記ノードの仮想座標を決定するモジュールと、
を備え、
前記ノードの前記仮想座標を更新するため前記ビーコン信号を定期的に送信するモジュールと、
前記ビーコン集合に属し、かつ、ビーコンメッセージを送信するノードを前記ビーコンノードの役割を引き継ぐ新しいノードと置き換えるモジュールと、
をさらに備え、
前記置き換えが前記仮想座標の決定を改善するために所定の置き換えスキームに従って定期的に実行され、
前記置き換えスキームが、
前記ビーコンノードの集合の中の第１のビーコンノードに関して、ある距離尺度に従って前記第１のビーコンノードから前記ビーコンノードの集合の中の他のビーコンノードまでの距離を決定するステップと、
距離尺度量が最小値をとったビーコンノードを選択するステップと、
前記第１のビーコンノードの近傍ノードに関して、前記選択されたビーコンノードまでの前記距離尺度を計算するステップと、
前記近傍ノードのうちの１つに関して、前記距離尺度量が前記第１のビーコンノードの距離尺度量より高いならば、前記ビーコンノードの集合の中の前記第１のビーコンノードを距離尺度がより高い値をとった前記近傍ノードと置き換えるステップとを含む、装置。
【請求項１１】
ビーコンノードの初期集合をランダムに選択するモジュールと、
対応するビーコンノードから個々のノードまでビーコン信号が進むホップ数によってそれぞれ決定される前記ビーコンノードまでの距離に基づいて前記ネットワーク内の前記個々のノードの座標を決定するモジュールと、
前記ビーコンノードを含む前記ネットワーク内の全ノードに関して前記座標を決定するモジュールと、
このようにして決定された座標に基づいて、第１のビーコンノードに関して、別のビーコンノードまでの最小距離を決定し、前記第１のビーコンノードの近傍ノードがより大きな距離をとるならば、前記第１のビーコンを前記近傍ノードと置き換えるステップを備える置き換えスキームを実行するモジュールと、
前記ビーコンノードの集合の中の前記ビーコンノードの全てに関して前記置き換えスキームを繰り返すモジュールと、
を備える、請求項１０に記載の装置。
【請求項１２】
前記距離の差がある特定のスレッショルドを超えるという条件、
前記距離の差がある特定の期間に亘って存在し続けるという条件、
置き換えられるべき前記ビーコンノードが仮想空間内で移動したという条件、及び、
前記置き換えられるべきビーコンノードの近傍集合が変化したという条件
のうちの１つ以上の条件が満たされる場合に限り、前記ビーコンノードの前記置き換えを実行するモジュールをさらに備える、請求項１０又は１１の一項に記載の装置。
【請求項１３】
前記ネットワークの前記ノード及び前記ビーコンノードの任意の仮想座標を選択するモジュールと、
前記ネットワーク内のノードに関して、前記ビーコンノードの集合の中の前記ビーコンノード毎に、前記ノードから前記ビーコンノードの各々までの距離を表す近接性尺度を前記ビーコンノードによって送信されたビーコンに基づいてそれぞれ決定するモジュールと、
前記ビーコンノードの集合の中のビーコンノード毎に前記仮想座標に基づいて前記ノードと前記ビーコンノードとの距離を表す距離尺度を決定するモジュールと、
前記ビーコンノードの集合の中のビーコンノード毎に、前記仮想座標に基づいて取得された前記距離尺度及び前記ビーコンノードによって送信された前記ビーコンに基づいて取得された前記近接性尺度が、シフトの量が前記ノードの仮想座標の修正ベクトルに対応するようなシフト後に一致すべきであるならば、前記ノードの前記仮想座標が前記ビーコンノードの方向へシフトされるべき量を決定するモジュールと、
修正ベクトルのベクトル和を決定し、次の反復で使用されるべき修正仮想座標を取得するために、得られたベクトルを前記ノードの前記仮想座標に加算するモジュールと、
前記置き換えスキームを適用した後に新しいビーコンノードの集合を使用して次の反復中に前記ステップを繰り返すモジュールと、
を備える、請求項１０〜１２の一項に記載の装置。
【請求項１４】
前記置き換えスキームが、
ある特定のノードがビーコンノードとしての機能を果たす確率を表すネットワークのノードに割り当てられた確率に基づいて前記ビーコンノードの集合の中の既存のビーコンノードを置き換える新しいビーコンノードをランダムに選択するステップと、
個別のノードがビーコンノードとしての機能を果たす順序を表す所定の順序に基づいて前記ビーコンノードの集合の中の既存のビーコンノードを置き換える新しいビーコンノードを選択するステップと、
のうちの一方を備える、請求項１３に記載の装置。
【請求項１５】
前記近接性尺度はビーコンが前記ネットワーク内でビーコンノードからノードへ進むホップ数に基礎を置き、
前記距離尺度は前記ネットワーク内のノードと前記ネットワーク内のビーコンとの間でそれぞれの仮想座標に基づいて計算されたユークリッド距離に基礎を置いている、請求項１３又は１４に記載の装置。
【請求項１６】
近接性尺度又は距離尺度が、個別のノードに関して決定された値をこのノードの近傍ノードに関して取得された値と平均化することにより前記個別のノードに関して決定される、請求項１０〜１５の一項に記載の装置。
【請求項１７】
ノードがビーコンノードとしての機能を果たす確からしさは、
前記仮想座標の安定性、
前記ネットワーク内のノード数、及び、
ビーコンノードに関する前記ノードの前記ロケーション
のうちの１つ以上のパラメータに基づいて適合される、請求項１３〜１６の一項に記載の装置。
【請求項１８】
アドホックワイヤレスネットワークを介して起点から宛先までメッセージを経路制御する装置であって、
前記起点から前記宛先へパケットを経路制御するルートを決定するため、請求項１０〜１７の一項に記載の装置を使用して決定された仮想座標を使用するモジュールを備える装置。
【請求項１９】
コンピュータ上で実行されているときに前記コンピュータに請求項１〜９の一項に記載の方法を実行させることができるコンピュータプログラム。
【発明の詳細な説明】【技術分野】
【０００１】
本発明は、ネットワークのノードの仮想座標を取得する方法に関する。
【背景技術】
【０００２】
アドホックネットワークは、中央インフラストラクチャを有さないワイヤレスネットワークである。全ノードは端末としての機能を果たすが、リレールータとしても機能を果たす。より詳細には、このことは、無線範囲の外側にある別のノードと通信しようとするノードがパケットを近傍ノードのうちの１つへ送信し、この近傍ノードのうちの１つが今度はパケットを近隣へ転送し、パケットが宛先に到着するまで同様に続くことを意味する。このことから、宛先の識別子しか知らないノードは、宛先へ届けるためにパケットを転送しなければならない転送先をどのようにして知ることができるのか、という疑問が即座に生じる。
【０００３】
典型的に、帯域幅、電力などのようなネットワークリソースの最小限の使用を意味する宛先への最短経路に基づく経路制御が必要とされ、制御オーバーヘッド（すなわち、これらの経路を発見し、かつ、維持するために必要な全てのパケット）が最小限に抑えられる。アドホックネットワークのためのルーティングアルゴリズムの主要なパラダイムは、リンクに基づく通信グラフ（トポロジー）、又は、ワイヤレスノードのジオメトリ（地理的ルーティング）の何れかを利用する。トポロジーに基づくルーティングは、複雑な通信チャンネルの存在を考慮するが、ワイヤレスネットワークの固有のジオメトリを利用しない。トポロジーに基づくルーティングは、後でルーティングテーブルに記憶される経路を確立し維持するために、「ベルマンフォード（Ｂｅｌｌｍａｎ−Ｆｏｒｄ）」又は「リンクステートルーティング（Ｌｉｎｋ Ｓｔａｔｅ Ｒｏｕｔｉｎｇ）」のようなインターネットプロトコルの変形に依拠する（例えば、Ｃ．Ｅ．Ｐｅｒｋｉｎｓ ａｎｄ Ｐ．Ｂｈａｇｗａｔ，Ｈｉｇｈｌｙ ｄｙｎａｍｉｃ ｄｅｓｔｉｎａｔｉｏｎ−ｓｅｑｕｅｎｃｅｄ ｄｉｓｔａｎｃｅ−ｖｅｃｔｏｒ ｒｏｕｔｉｎｇ（ＤＳＤＶ）ｆｏｒ ｍｏｂｉｌｅ ｃｏｍｐｕｔｅｒｓ，Ｉｎ ＡＣＭ ＳＩＧＣＯＭＭ ９４，ｐａｇｅ ２３４−２４４，Ｌｏｎｄｏｎ，１９９４、又は、Ｔ．Ｃｌａｕｓｅｎ，Ｐ．Ｊａｃｑｕｅｔ，Ａ．Ｌａｏｕｔｉ，Ｐ．Ｍｕｈｌｅｔｈａｌｅｒ，ａ．Ｑａｙｙｕｍ，ａｎｄ Ｌ．Ｖｉｅｎｎｏｔ，Ｏｐｔｉｍｉｚｅｄ ｌｉｎｋ ｓｔａｔｅ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ，Ｉｎ ＩＥＥＥ ＩＮＭＩＣ，Ｐａｋｉｓｔａｎ，２００１を参照のこと）。
【０００４】
地理的ルーティングでは、パケットはノードの地理的位置に基づいて経路制御される（例えば、Ｇ．Ｇ．Ｆｉｎｎ，Ｒｏｕｔｉｎｇ ａｎｄ ａｄｄｒｅｓｓｉｎｇ ｐｒｏｂｌｅｍｓ ｉｎ ｌａｒｇｅ ｍｅｔｒｏｐｏｌｉｔａｎ−ｓｃａｌｅ ｉｎｔｅｒｎｅｔｗｏｒｋｓ，ＩＳＩ Ｒｅｓｅａｒｃｈ Ｒｅｐｏｒｔ ＩＳＵ／ＲＲ−８７−１８０，Ｍａｒｃｈ １９８７、又は、Ｐ．Ｂｏｓｅ，Ｐ．Ｍｏｒｉｎ，Ｉ．Ｓｔｏｊｍｅｎｏｖｉｃ ａｎｄ Ｊ．Ｕｒｒｕｔｉａ，Ｒｏｕｔｉｎｇ ｗｉｔｈ ｇｕａｒａｎｔｅｅｄ ｄｅｌｉｖｅｒｙ ｉｎ ａｄ ｈｏｃ ｗｉｒｅｌｅｓｓ ｎｅｔｏｗｏｒｋｓ，ＡＣＭ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋｓ，Ｎｏｖｅｍｂｅｒ ２００１を参照のこと）。典型的に、パケットは、パケットが最終目的地へ到達するまで、宛先の位置へ向かって最も前進する近隣へ送信することによって、グリーディ法で転送される。
【０００５】
トポロジーに基づくルーティングの限界は、ルート発見及び維持がフラッディングに基づき、かつ、特に、安定した終端間ルートを維持することが困難であるモバイル環境及び不確実な環境において、オーバーヘッドの点でコストがかかるということである。一方、地理的ルーティングは、ジオメトリへの依存度が高く、複雑なリンク挙動を無視する。グリーディ転送の背後には、機器の地理座標がネットワークトポロジーの優れた近似であるという認識がある。しかし、このことは常に真であるとは限らず、パケットは、いわゆるデッドエンドから抜け出せなくなることがある（すなわち、それ自体より地理的に宛先に近い近隣をもたないノードに到達する）。このようなデッドエンドは、回避されるべき、コストのかかるリカバリ手順を必要とする。デッドエンドは局所的であることも大域的であることもある。ジオメトリの大きな空洞は、ある方向へ移動している間に多数のパケットを抜け出せなくさせ、（例えば、ノイズを含む位置推定に起因する）小さな局所的な置き間違いはパケットを遮断する可能性もある。このことが図１に例示され、図１の左側には、ネットワーク全体が示され、矢印の方向へ移動しているパケットは、大きな障害のために抜け出せなくなる。右側には、局所的な混乱が示されている。ノードｋへ向かうパケットは、ノードｊよりノードｉの方がノードｋから僅かに離れているので、ノードｊから抜け出せなくなる。
【０００６】
地理的ルーティングは、さらに全てのノードが固有の位置を知ることを要求する。一般的に、ノードは、例えば、「全地球測位システム（ＧＰＳ）」機器のようなある種の形式の位置決め用ハードウェアが装備されていると考えられる。しかし、このような機器は、高価であり、及び／又は、バッテリー寿命が制限されているノードの場合に非常に大量の電力を消費する。ＧＰＳを用いることなく位置情報を取得する解決法は存在するが（例えば、Ｓ．Ｃａｐｋｕｎ，Ｍ．Ｈａｍｂｉ，Ｊ．Ｈｕｂａｕｘ，ＧＰＳ−Ｆｒｅｅ Ｐｏｓｉｔｉｏｎｉｎｇ ｉｎ Ｍｏｂｉｌｅ ａｄ−ｈｏｃ Ｎｅｔｗｏｒｋｓ，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ３４ｔｈ Ａｎｎｕａｌ Ｈａｗａｉｉ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ，２００１を参照のこと）、この情報の構築及び維持はかなりのネットワークリソースを消費する。さらに、チャンネル品質は、例えば、散乱に起因して、必ずしもノード間距離の関数ではない。ノードは、さらに、パケットを送信しようとする宛先の位置を知るために、分散データベース、いわゆるロケーションサービスの一形式を更新し、問い合わせる必要がある。典型的に、このコストは、トポロジーに基づくルーティングの場合の上記の経路発見コストより低い。しかし、位置が高速に変化するモバイル環境では、このコストはノードが更新頻度を増加させる必要に応じて増大する。
【０００７】
トポロジーに基づく地理的ルーティングの欠点を回避するため、現実の地理座標ではなく、ノードの仮想座標に基づいてルーティングを行うことが可能である。このような座標は、通例、基礎となる連結グラフに基づいてノードに割り当てられる（すなわち、直ぐ隣にある、又は、少数個の中間ホップを介して接続されているノードは、類似した座標を有する）。仮想座標は、通信するために少数のリソースしか必要としないノードが仮想座標系内で一緒に近くに配置されるので、より最適なルーティングスキームをもたらすことができる。特に、宛先の方向へグリーディ法で転送するパケットは、一方的に悪いルートをもたらさないはずである。仮想座標は、座標系内の目標に接近しているとき、連結グラフ内の目標にも接近しているというある種の保証を与える。ロケーションサービスと共に使用できるように、ノードの仮想座標は、時間的に大きく変動すべきでなく、すなわち、ノードは仮想空間内で「ジャンプ」すべきでない。オフィス環境におけるアドホック端末の連結グラフ及びノード位置が図２Ａに示されている。これらの実座標を用いるグリーディルーティングは、悪い性能を生じる可能性がある。２次元仮想空間内の考え得る接続性の埋め込みが図２Ｂに示されている。実世界内では地理的に接近しているが、連結グラフ内では数ホップ離れているノードｉ及びノードｊは、仮想空間内では明瞭に分離されていることに注意すべきである。連結グラフの最短経路距離は、この仮想座標によってより良好に捕捉され、グリーディルーティングは非常に優れた性能をもたらす。
【０００８】
仮想座標が地理座標より好ましい別の例が図３に示されている。左側は、現実の地理座標を使用するネットワークの表現を示している。地理的に非常に接近しているノードＢとノードＦは、実際、接続性の観点で互いに遠く離れていることがわかる。このことは、ノードＢとノードＦが互いに遠く離れていることがわかる図３の右側に示されているように、ノードが仮想座標によって表現されているときに反映される。
【０００９】
埋め込み（すなわち、接続性に基づく仮想座標によるネットワーク内のノードのロケーションの表現）は、仮想座標系を確立し維持するための通信オーバーヘッドがトポロジーに基づくルーティングによる通信オーバーヘッド、又は、実座標によるデッドエンドリカバリオーバーヘッドより低いときに意味がある。所望の特性は、さらに、オーバーヘッドがノードの個数に伴って増大しないことである。アドホックネットワークに連結グラフを埋め込む数通りのアプローチが提案され、そのうちの幾つかは以下に簡単に紹介されている。
【００１０】
「Ａ．Ｒａｏ，Ｓ．Ｒａｔｎａｓａｍｙ，Ｃ．Ｐａｐａｄｉｍｉｔｒｉｏｕ，Ｓ．Ｓｈｅｎｋｅｒ，ａｎｄ Ｉ．Ｓｔｏｉｃａ，Ｇｅｏｇｒａｐｈｉｃ ｒｏｕｔｉｎｇ ｗｉｔｈｏｕｔ ｌｏｃａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ，ＭＯＢＩＣＯＭ，２００３」には、仮想座標系を反復的に構築する分散緩和アルゴリズムを用いるルーティングスキームが提示されている。このアルゴリズムは、多数のいわゆる周辺ノード（ネットワークの境界に位置しているノード）が予め実座標を知っていることを仮定している。全ての他のノードはランダム仮想座標で始まる。次に、反復毎に、非周辺ノードは、近隣の座標を平均化することにより、それ自体の仮想座標を更新する。周辺ノードがそれ自体の座標を知らないか、又は、ノードがそれ自体は周辺ノードであることさえ知らないならば、緩和アルゴリズム（平均化）を適用する前にこのような情報を取得する手順が提案される。この手順はフラッディング(flooding)に基礎を置き、メッセージの個数がネットワークサイズと共に著しく増大するので、オーバーヘッドの点でコスト高である。周辺のビーコンの位置を見つけることは、グリーディ(greedy)ルーティングの成功率の点ですばらしい性能をもたらすが、これらのビーコンを発見し維持するためのコストは、トポロジーがダイナミックであるときには、オーバーヘッドの点で高い。
【００１１】
ビーコン・ベクトル・ルーティング（例えば、Ｒ．Ｆｏｎｓｅｃａ，Ｓ．Ｒａｔｎａｓａｍｙ，Ｊ．Ｚｈａｏ，Ｃ．Ｔ．Ｅｅ，Ｄ．Ｃｕｌｌｅｒ，Ｓ．Ｓｈｅｎｋｅｒ，Ｉ．Ｓｔｏｉｃａ，Ｂｅａｃｏｎ−Ｖｅｃｔｏｒ Ｒｏｕｔｉｎｇ：Ｓｃａｌａｂｌｅ Ｐｏｉｎｔ−ｔｏ−Ｐｏｉｎｔ Ｒｏｕｔｉｎｇ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ，Ｉｎ ＮＳＤＩ，２００５を参照のこと）は、複数個のランダムに選択されたビーコンノードまでのノードのホップ距離に基づいて、仮想座標をノードに割り当てる。ランダム選択が最初に行われ、ビーコンセットはビーコンが機能しなくなるまで変化しない。ここで、座標空間の次元はビーコンの台数と対応する。Ｒａｏ ｅｔ ａｌ．のアプローチと同様に、ノード座標上のグリーディ転送はルーティングスキームとして使用される。ビーコンの方向へのグリーディルーティングはビーコンから遠ざかるルーティングより宛先に到達する可能性が高いということを考慮する距離規準が定義される。デッドエンドの場合、小さな範囲のフラッディングが再びグリーディな前進を行うノードを発見するために始動される。しかし、このスキームは、モバイルノード又は不確実なチャンネル環境を取り扱わない。ビーコンの移動はノードの仮想位置に大きなシフトを生じさせ、この大きなシフトは今度は、不安定な座標系を意味する。この場合、ノードの位置を用いる分散データベース（ロケーションサービス）は、仮想空間内のノードの頻繁かつ大きな移動に起因するオーバーヘッドの点で非常にコスト高である。更新が行われないならば、パケットは非常に不正確な場所へ送信されるので、ルーティングの品質は非常に悪い。
【００１２】
ＧＥＭフレームワーク（例えば、Ｊａｍｅｓ Ｎｅｗｓｏｍｅ ａｎｄ Ｄａｗｎ Ｓｏｎｇ，ＧＥＭ：ｇｒａｐｈ ｅｍｂｅｄｄｉｎｇ ｆｏｒ ｒｏｕｔｉｎｇ ａｎｄ ｄａｔａ−ｃｅｎｔｒｉｃ ｓｔｏｒａｇｅ ｉｎ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｗｉｔｈｏｕｔ ｇｅｏｇｒａｐｈｉｃ ｉｎｆｏｒｍａｔｉｏｎ，Ｉｎ １ｓｔ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｅｍｂｅｄｄｅｄ ｎｅｔｗｏｒｋｅｄ ｓｅｎｓｏｒ ｓｙｓｔｅｍ，２００３を参照のこと）は、データ名からノードへルーティング及びマッピングの問題を一緒に取り組むことにより、データセントリック情報処理及び蓄積のための効率的なインフラストラクチャを提供する。このインフラストラクチャは、ネットワークトポロジーに埋め込まれたリング型ツリーグラフを使用する。このように取得された仮想座標は極座標と類似している。あらゆるノードはラベルと角度（ツリー内の方位及び方位奥行き）が割り当てられ、ルーティングは、パケットが宛先により近い角度及び奥行きを有するノードへ転送されるように行われる。ネットワークの奥深くに位置するノードへの負荷は、全トラフィックが中心のビーコンノードを通過すること、又は、コストの高い並べ替え手順が適用されることの何れかが必要とされるので、このアプローチにおいては非常に高い。この場合も、移動性の条件下で、座標系は不安定である。
【００１３】
Ｆｏｎｓｅｃａ ｅｔ ａｌ．のアプローチ及びＮｅｗｓｏｍｅ ｅｔ ａｌ．のアプローチは、局所的な無秩序を効果的に処理しないように思われるが、実際には大域的なデッドエンドの個数をかなり削減することに注意すべきである。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
したがって、移動性及び現実的なチャンネル条件の下でロバスト性があるビーコンに基づく埋め込みを提供することが望ましい。
【課題を解決するための手段】
【００１５】
一実施形態により提供される方法は、アドホックワイヤレスネットワークのノードのロケーションの表現であり、上記ネットワーク内のビーコンノードの集合から送信されたビーコン信号に基づいている上記ノードの仮想座標を取得する方法であって、
上記ビーコン信号を受信するノードと上記ビーコン信号を送信したノードとの間の近接性を表す近接性尺度を決定するため上記ビーコン信号を使用するステップと、
上記近接性尺度に基づいて上記ビーコンを受信したノードの仮想座標を決定するステップと、
を備え、
上記ノードの上記仮想座標を更新するため上記ビーコン信号を定期的に送信するステップと、
上記ビーコンノードの集合に属し、かつ、ビーコンメッセージを送信するノードを、ビーコンの役割を引き継ぐ新しいノードと置き換えるステップと、
をさらに備え、
上記置き換えが上記仮想座標の決定を改善するために所定の置き換えスキームに従って定期的に実行され、
上記置き換えスキームが、
上記ビーコンノードの集合の中の第１のビーコンノードに関して、ある距離尺度に従って上記第１のビーコンノードから上記ビーコンノードの集合の中の他のビーコンノードまでの距離を決定するステップと、
距離尺度量が最小値をとったビーコンノードを選択するステップと、
上記第１のビーコンノードの近傍ノードに関して、上記選択されたビーコンノードまでの上記距離尺度を計算するステップと、
上記近傍ノードのうちの１つに関して、上記距離尺度量が上記第１のビーコンノードの距離尺度量より高いならば、上記ビーコンノードの集合の中の上記第１のビーコンノードを距離尺度がより高い値をとった上記近傍ノードと置き換えるステップとを備える、
方法である。
【００１６】
従来技術において、ビーコンノードの集合は固定されていたが、本発明によれば、ビーコンノードの集合は、ある置き換えスキームに従って１個のメンバーを別のメンバーと置き換えることにより定期的に変更される。このことは、ビーコニングが、それまで考慮されていなかったネットワークの他の部分からの「新しい情報」を継続的にもたらすという効果を奏し、これは、今度は、より良好な埋め込みをもたらし、ノードの移動性の影響に対処することが可能である。
【００１７】
このようにして、ビーコンノードは互いに「押しのけられ（pushed away）」、換言すると、ビーコンノードはネットワークの周辺の方へ押される。このことは、ビーコンが故障すれば、ビーコン集合は変化しないという従来技術の欠点を回避する。この事例では、ノードの移動によって引き起こされる座標のシフトは不安定かつ不正確な埋め込みの原因となる。
【００１８】
一実施形態によれば、上記方法は、
ビーコンノードの初期集合をランダムに選択するステップと、
対応するビーコンノードから個々のノードまでビーコン信号が進むホップ数によってそれぞれ決定される上記ビーコンノードまでの距離に基づいてネットワーク内の個々のノードの座標を決定するステップと、
上記ビーコンノードを含む上記ネットワーク内の全ノードに関して上記座標を決定するステップと、
このようにして決定された座標に基づいて、第１のビーコンノードに関して、別のビーコンノードまでの最小距離を決定し、上記第１のビーコンノードの近傍ノードがより大きな距離をとるならば、上記第１のビーコンを上記近傍ノードと置き換える置き換えスキームを実行するステップと、
上記ビーコンノードの集合の中の上記ビーコンノードの全てに関して上記置き換えスキームを繰り返すステップと、
を備える。
【００１９】
本実施形態では、仮想座標の次元はビーコンの個数と対応する。各ビーコンｋはビーコン信号を送信し、ビーコン信号がネットワーク内のノードｉまで進むホップ数に基づいて、ノードｉの仮想座標のｋ番目の成分が決定される。さらに、この座標系は、ビーコン自体の座標も与えるので、これらに基づいて、ビーコンが周辺へ向かって押されるべきであるかどうかを検査する置き換えスキームが実行され得る。このようにして、最初にランダムに選択されたビーコン集合に基づいて、ある程度の反復後にビーコンが最も好ましいネットワークの周辺に位置するように、ビーコンの完全な集合が状況に動的に適応する。
【００２０】
一実施形態によれば、上記方法は、
上記距離の差がある特定のスレッショルドを超えるという条件、
上記距離の差がある特定の期間に亘って存在し続けるという条件、
置き換えられるべきビーコンノードが仮想空間内で移動したという条件、及び、
置き換えられるべきビーコンノードの近傍の集合が変化したという条件
のうちの１つ以上の条件が満たされる場合に限り、上記ビーコンノードの上記置き換えを実行するステップをさらに備える。
【００２１】
この種の保護手段措置を用いて、例えば、発振をもたらすかもしれないビーコンノードの集合の非常に頻繁な変化が回避される。
【００２２】
一実施形態によれば、上記方法は
上記ネットワークのノード及びビーコンノードの任意の仮想座標を選択するステップと、
上記ネットワーク内のノードに関して、上記ビーコンノードの集合の中の上記ビーコンノード毎に、上記ノードから上記ビーコンノードの各々までの距離を表す近接性尺度を、それぞれ上記ビーコンノードによって送信されたビーコンに基づいて、決定するステップと、
上記ビーコンノードの集合の中のビーコンノード毎に上記仮想座標に基づいて上記ノードとビーコンノードとの距離を表す距離尺度を決定するステップと、
上記ビーコンノードの集合の中のビーコンノード毎に、仮想座標に基づいて取得された距離尺度及びビーコンノードによって送信されたビーコンに基づいて取得された近接性尺度が、シフトの量が上記ノードの仮想座標の修正ベクトルに対応するようなシフト後に一致すべきであるならば、上記ノードの仮想座標が上記ビーコンノードの方向へシフトされるべき量を決定するステップと、
修正ベクトルのベクトル和を決定し、次の反復で使用されるべき修正仮想座標を取得するために、得られたベクトルを上記ノードの仮想座標に加算するステップと、
上記置き換えスキームを適用した後に新しいビーコンノードの集合を使用して次の反復中に上記ステップを繰り返すステップと、
をさらに備える。
【００２３】
一実施形態によれば、上記置き換えスキームは、
ある特定のノードがビーコンノードとしての機能を果たす確率を表すネットワークのノードに割り当てられた確率に基づいてビーコンノードの集合の中の既存のビーコンノードを置き換える新しいビーコンノードをランダムに選択するステップと、
個別のノードがビーコンノードとしての機能を果たす順序を表す所定の順序に基づいてビーコンノードの集合の中の既存のビーコンノードを置き換える新しいビーコンノードを選択するステップと、
を備える。
【００２４】
一実施形態によれば、上記近接性尺度はビーコンがネットワーク内でビーコンノードからノードへ進むホップ数に基礎を置き、上記距離尺度は、上記ネットワーク内のノードと上記ネットワーク内のビーコンとの間で、それぞれの仮想座標に基づいて計算されたユークリッド距離に基礎を置いている。
【００２５】
一実施形態によれば、近接性尺度又は距離尺度は、個別のノードに関して決定された値をこのノードの近傍ノードに関して取得された値と平均化することにより、個別のノードに関して決定される。
【００２６】
局所的な平均化は、座標値及び近接性尺度を局所的な歪みに対してより安定化させる。
【００２７】
一実施形態によれば、ビーコンノードとしての機能を果たすノードの確からしさは、
仮想座標の安定性、
ネットワーク内のノード数、及び、
ビーコンノードに関するノードのロケーション
のうちの１つ以上のパラメータに基づいて適合される。
【００２８】
このようにして、メカニズム全体がネットワーク内の大域的な状況に適合する。
【００２９】
一実施形態により提供される装置は、アドホックワイヤレスネットワークのノードのロケーションの表現であり、上記ネットワーク内のビーコンノードの集合から送信されたビーコン信号に基づいている上記ノードの仮想座標を取得する装置であって、
上記ビーコン信号を受信するノードと上記ビーコン信号を送信したノードとの間の近接性を表す近接性尺度を決定するため上記ビーコン信号を使用するモジュールと、
上記近接性尺度に基づいて上記ビーコンを受信したノードの仮想座標を決定するモジュールと、
を備え、
上記ノードの上記仮想座標を更新するため上記ビーコン信号を定期的に送信するモジュールと、
上記ビーコン集合に属しビーコンメッセージを送信するノードをビーコンノードの役割を引き継ぐ新しいノードと置き換えるモジュールと、
をさらに備え、
上記置き換えが上記仮想座標の決定を改善するために所定の置き換えスキームに従って定期的に実行され、
上記置き換えスキームが、
上記ビーコンノードの集合の中の第１のビーコンノードに関して、ある距離尺度に従って上記第１のビーコンノードから上記ビーコンノードの集合の中の他のビーコンノードまでの距離を決定するステップと、
距離尺度量が最小値をとったビーコンノードを選択するステップと、
上記第１のビーコンノードの近傍ノードに関して、上記選択されたビーコンノードまでの上記距離尺度を計算するステップと、
上記近傍ノードのうちの１つに関して、上記距離尺度量が上記第１のビーコンノードの距離尺度量より高いならば、上記ビーコンノードの集合の中の上記第１のビーコンノードを距離尺度がより高い値をとった上記近傍ノードと置き換えるステップとを備える、装置である。
【００３０】
一実施形態によれば、上記装置は、
ビーコンノードの初期集合をランダムに選択するモジュールと、
対応するビーコンノードから個々のノードまでビーコン信号が進むホップ数によってそれぞれ決定される上記ビーコンノードまでの距離に基づいてネットワーク内の個々のノードの座標を決定するモジュールと、
上記ビーコンノードを含む上記ネットワーク内の全ノードに関して上記座標を決定するモジュールと、
このようにして決定された座標に基づいて、第１のビーコンノードに関して、別のビーコンノードまでの最小距離を決定し、上記第１のビーコンノードの近傍ノードがより大きな距離をとるならば、上記第１のビーコンノードを上記近傍ノードと置き換える置き換えスキームを実行するモジュールと、
上記ビーコンノードの集合の中の上記ビーコンノードの全てに関して上記置き換えスキームを繰り返すモジュールと、
を備える。
【００３１】
一実施形態によれば、装置は、
上記距離の差がある特定のスレッショルドを超えるという条件、
上記距離の差がある特定の期間に亘って存在し続けるという条件、
置き換えられるべきビーコンノードが仮想空間内で移動したという条件、及び、
置き換えられるべきビーコンノードの近傍の集合が変化したという条件
のうちの１つ以上の条件が満たされる場合に限り、上記ビーコンノードの上記置き換えを実行するモジュールを備える。
【００３２】
一実施形態によれば、装置は、
上記ネットワークのノード及びビーコンノードの任意の仮想座標を選択するモジュールと、
上記ネットワーク内のノードに関して、上記ビーコンノードの集合の中の上記ビーコンノード毎に、上記ノードから上記ビーコンノードの各々までの距離を表す近接性尺度を、それぞれ上記ビーコンノードによって送信されたビーコンに基づいて決定するモジュールと、
上記ビーコンノードの集合の中のビーコンノード毎に上記仮想座標に基づいて上記ノードとビーコンノードとの距離を表す距離尺度を決定するモジュールと、
上記ビーコンノードの集合の中のビーコンノード毎に、仮想座標に基づいて取得された距離尺度及びビーコンノードによって送信されたビーコンに基づいて取得された近接性尺度が、シフトの量が上記ノードの仮想座標の修正ベクトルに対応するようなシフト後に一致すべきであるならば、上記ノードの仮想座標が上記ビーコンノードの方向へシフトされるべき量を決定するモジュールと、
修正ベクトルのベクトル和を決定し、次の反復で使用されるべき修正仮想座標を取得するために、得られたベクトルを上記ノードの仮想座標に加算するモジュールと、
上記置き換えスキームを適用した後に新しいビーコンノードの集合を使用して次の反復中に上記ステップを繰り返すモジュールと、
を備える。
【００３３】
一実施形態によれば、装置は、本発明の実施形態による方法を実行するモジュールを備える。
【００３４】
一実施形態によれば、ネットワークを介して起点から宛先までメッセージを経路制御する装置であって、上記起点から上記宛先へパケットを経路制御するルートを決定するため、本発明の実施形態による装置又は方法を使用して決定された仮想座標を使用するモジュールを備える装置が提供される。
【００３５】
これは、本発明の実施形態によって決定された仮想座標によって達成され得る効率的な経路制御を使用する。
【００３６】
一実施形態によれば、コンピュータ上で実行されているときに、上記コンピュータに本発明の実施形態による方法を実行させることができるコンピュータプログラムが提供される。
【発明を実施するための最良の形態】
【００３７】
次に本発明の実施形態が以下に詳細に記載されている。特に、本実施形態は、
ビーコンハンドオフマネージメント
確率論的ビーコニング
という２つの態様に関している。
【００３８】
これらの方法は後で示される。表１は、本文書を通じて使用される付加的な表記表である。
【００３９】
【表１】


【００４０】
ビーコンハンドオフマネージメントは、特に、Ｂｏｕｒｇａｉｎタイプの埋め込みに適用可能である（例えば、Ｒａｏ ｅｔ ａｌ．及びＦｏｎｓｅｃａ ｅｔ ａｌ．を参照のこと）。このようなスキームでは、ノードの座標はビーコンまでの距離によって与えられる。座標系の非常に大きなシフトを避けるため、ビーコンとしてマークされているノードは、フラッドがネットワークのおおよそ同じ領域から常に出てくるように、ビーコンを「ハンドオフ」する（すなわち、ビーコンノードであるという特性をネットワーク内の別のノードへ引き渡す）。より詳細には、ネットワークには、最初にランダムに選定され、番号付けされたｄ個のビーコンが存在する。次元ｕに対応するビーコンは、ｂuとラベル付けされる。時刻ｋにおけるｄ個のビーコンノードの集合をＢ（ｋ）と呼び、ノードｉが知っている時刻ｋにおけるｂuへの最後の近接性をＰi（ｕ，ｋ）と呼ぶ。反復ｋにおいて、ｗ＝ｋ ｍｏｄ ｄであるビーコンｗがネットワークをフラッド（flood）させる。ネットワーク内の全ての他のノードは、このようにしてｂwまでのホップ距離（近接性）を取得する。時刻ｋにノードｉによって記憶された情報は、このノードのビーコンベクトルｖi及び仮想位置である。反復ｋにおいて、ｖ≠ｗの場合に、Ｐi（ｖ，ｋ）は期限切れであるが、座標を計算するために依然として使用されることに注意すべきである。以下に、ビーコンベクトル（時刻ｋにおけるノードｉからビーコン１〜ｄまでの距離）及び仮想座標ｘiを備える、ノードｉに関して記憶された情報が与えられている。
【数１】


【００４１】
ノードｉは、後述のアルゴリズム１に示されているように、時刻ｋ＋１に対するそれ自体の仮想位置を計算する。さらに、ビーコンｌを保持するノードは、後述のアルゴリズム２に示されているように、ビーコンを引き渡す。
【００４２】
【表２】


【００４３】
【表３】


【００４４】
上述されたアルゴリズム１が今度はより詳細に説明される。
【００４５】
あらゆるノードはビーコンまでの距離を以下の通り推定する。第１ステップにおいて、ビーコン毎にノードは、ビーコンまでのそれ自体の距離が、ビーコンまでのそれ自体の距離と、ビーコンまでのそれ自体の近傍ノードの距離との平均であると考える。距離規準は、例えば、ビーコン信号がビーコンノードから座標が決定されるべきノードまで進まなければならないホップ数であり得る。したがって、第１のビーコンまでのノードの距離が１０であり、このノードが第１のビーコンまでの距離が９、１１及び１３である近傍ノードを有するならば、このノードはそれ自体の距離を（９＋１０＋１１＋１３）／４として推定する。ノードは、推定のためそれ自体の最も新しい距離（すなわち、前の反復中に取得された距離）を用いることに注意すべきである。ビーコンまでの距離は、規則的な間隔で行われるビーコンによるネットワークのフラッドが行われたときに取得される。
【００４６】
第２ステップにおいて、ノードの座標は、ビーコンまでのこのノードの推定された距離によって与えられる。したがって、３個のビーコンがあり、ノードが３個のビーコンまでの距離を２．１、３．５５及び７．９９として推定したならば、このノードの位置は（２．１，３．５５，７．９９）である。
【００４７】
上述されたようなアルゴリズム１は、ビーコンが常に同じ順序で連続して送出されることを定めるが、必ずしもこのようであるとは限らない。ビーコンノードは、他のノードとは独立して、かつ、それ自体固有の特定のビーコニング周波数でそれ自体のビーコンをフラッドさせてもよい。ノードがビーコンに関するそれ自体の距離情報を使用する方法はアルゴリズム１とアルゴリズム２との間で変化し、アルゴリズム１はこの点に関して単に例に過ぎない。
【００４８】
ビーコンロケーションが安定した状態を保ち、次に、埋め込みが安定した状態を保つことを保証するため、一実施形態によれば、上述され、今度はより詳細に説明されるアルゴリズム２によるハンドオフ手順が設けられる。
【００４９】
本実施形態によれば、ビーコンノードは、後述されるようなある種の条件を満たす近傍ノードを有する、それ自体のビーコンの役割を引き渡す。
【００５０】
上述されているように、ノードの座標は、ビーコンまでの推定距離によって与えられる。すなわち、ビーコンノードは、それ自体の座標の中に、それ自体までの推定距離である１つの座標を有する。それ自体までの距離に対応する座標を除外して、ビーコンｌは、別のビーコンまでの最小距離が別のビーコンまでのそれ自体固有の最小距離より大きい近傍ノードを有するかどうかを検査する。
【００５１】
換言すると、ビーコンｌは、それ自体以外のビーコン毎に、このビーコンまでの距離を計算する。これは、ビーコンの座標を使用してユークリッド距離を計算することだけによって行われる。このようにして得られた他のビーコンまでの距離の中で、最小値を有する１個のビーコンと、対応するビーコンＶとが選択される。次に、ビーコンｌの近傍ノード（ビーコンではなく、単に普通のノードである）に関して、ビーコンＶまでの距離が計算される。これらのノードのうちの１個からビーコンＶまでの距離がビーコンｌからビーコンＶまでの距離より長いならば、この近傍ノードはビーコンｌからビーコンの役割を引き継ぐために選択される。
【００５２】
その目的のため、ビーコンｌは、（他のビーコンＶまでの最も大きい最小距離を有する）このようにして決定されたノードへメッセージを送信し、このノードがビーコンの役割を引き継ぐ。
【００５３】
最小距離を用いる代わりに、別の距離尺度、例えば平均距離又は他のビーコンまでの距離の何らかのその他の関数を調べることもできることに注意すべきである。同じ距離尺度がより高い値を生じる近傍ノードが存在するならば、これは、このノードを新しいビーコンとして使用することがビーコンの全体的な構造を「膨張させる」こと、又は、「ビーコンを互いに遠ざける」ことを意味する。しかし、このような効果は、仮想座標及び埋め込みの安定性の観点から非常に好ましく、なぜならば、これは、ビーコンベクトルの成分の「線形独立の程度」が増大することを意味するからである。
【００５４】
ビーコンハンドオフ手順はビーコンを互いに遠ざけ、このようにして、ビーコンから出てくるビーコン信号が仮想座標を決定するためできる限り有用であることを保証する。このことは図４Ａ及び４Ｂからより明瞭になる。図４Ａは、例えば、ノードの移動性に起因して、どのように座標系がシフトするかを示している。図４Ｂは、ノードがネットワークの中心から縁へどのように移動するかを示すことによってこの効果をより明らかにしている。図４Ｂの右上側には、中心に位置するノードが示され、ビーコンはネットワークの周囲の付近に示されている。このことは、仮想座標系内のビーコン座標が図４Ｂの右側の上部分に示されているように位置しているという効果がある。しかし、ノードが図４Ｂの右側の下部分に示されているように縁へ向かって移動するならば、これは、ビーコン座標がもはや異なる方向にほとんど位置せずに、むしろ、その逆に、殆ど同じ直線上に位置する（すなわち、殆ど完全に線形従属である）という効果がある。このような事例では、縁へ向かって移動したノードに到達するビーコン信号は、もはや、仮想座標を決定するために有用な情報を与えない。
【００５５】
この状況を回避するため、ビーコンは図５に示されているように互いに遠ざけられる。距離尺度の決定が、ビーコンは（図４の左側部分に示されているように）もはやネットワークの周辺に位置していないということを示すならば、この点に関してよりよく位置付けられている別のノードがビーコンの役割を引き継ぐ新しいビーコンとして選択される。
【００５６】
ノードの役割が変動することを避けるため、ハンドオフは、旧ビーコンノードと新ビーコンノードとの間の距離差がある特定のスレッショルドを超える場合に限り実行される。
【００５７】
最適なビーコンの個数は、ネットワークの固有の次元性に依存するが（不均一なトポロジーはより多くのビーコンを必要とするが）、ネットワークダイナミクスはビーコニング周波数を決定する。一実施形態によれば、ビーコンの個数は、例えば、パケット配信比率又はルーティング経路内のデッドエンドの出現によって測定されるような、埋め込みの性質に適合される。ビーコンの個数は、例えば、ルーティングの品質が所与のスレッショルドより低下した場合に増加させられる。同様に、ビーコンノードがビーコンメッセージをフラッドさせる周波数は、（ノード移動性のような外部パラメータのみならず、埋め込みアルゴリズムの収束速度にも依存する）仮想座標が反復毎に変化する量に適合される。最後に、一実施形態によれば、ビーコンハンドオフは、アルゴリズム２における基準が満たされる度に毎回行われる必要はない。代替的に、一実施形態では、条件が数回に亘って満たされたときに、或いは、ノードの座標の安定性（すなわち、ノードの近傍又は仮想座標が変化する速さ）に依存してハンドオフするように決められる。この事例では、ハンドオフは、近傍又は仮想座標が（スレッショルドを超えて）急速に変化する場合に実行されないが、その理由は、この事例では、ビーコンの役割の変更が、埋め込みの安定性を低下させる原因になるという意味で、逆効果を招き得るからである。
【００５８】
以下、アンカーポイントまでのノードの近接性、及び、アンカーポイントの位置が与えられた場合に、ノードがそれ自体の最適位置決めを試行する確率論的なビーコニングアプローチが説明される。反復ｋ毎に、ランダムに選択されたビーコンｂkは、仮想位置ｘbkでネットワークをフラッドさせる。ネットワーク内の全ての他のノードは、このようにｂkまでのそれ自体のホップ距離（＝近接性）を取得する。最初に、ｘb0は完全にランダムなｄ次元ベクトルであることに注意すべきである。次元ｄは任意に選択されるが、より高次の次元（例えば、３次元以上、より好ましくは、１０次元より高次）が好ましい。
【００５９】
ノードは、ｂ＿ｂｕｆｆラストビーコンまでのそれ自体の近接性及びこれらのビーコンの位置を格納しているバッファを有する。時刻ｋにおけるｂ＿ｂｕｆｆラストビーコン集合（ｋは反復の回数を表す）をＢ（ｋ）とし、時刻ｋ−ｌにおけるノードｉとビーコンｋ−ｌとの近接性をＰi（ｋ−ｌ）とする。上述のｘbkは、ｄ次元で指定されたｋ番目のラストビーコンの仮想位置である。時刻ｋにノードｉによって記憶されている情報は、（ホップ単位によるラストｂ＿ｂｕｆｆビーコンまでのそれ自体の近接性及びラストｂ＿ｂｕｆｆビーコンの位置からなる）それ自体のビーコンベクトルｖiとそれ自体の仮想位置とであり、
【数２】


のように見える。
【００６０】
この情報は、ラストｂ＿ｂｕｆｆビーコンメッセージに対応するが、これらのｂ＿ｂｕｆｆビーコンメッセージのそれぞれは、ランダムに選択された異なるビーコンノードによって送信されている。上述のように、反復毎に、異なるビーコンノードがランダムに選択される。ビーコンノードとしての役割を果たす（かつ、そのようにするための対応する確率が割り当てられている）ノードの集合は、ネットワークの全ノード、又は、全ノードの部分集合を備える。一実施形態によれば、全部でｄ個のビーコンノードのうちの各ビーコンノードがビーコンメッセージを送信するある所定の確率が存在する。この確率は、実施に応じて、全ノードに対して同一でもよく、又は、予め決定されるか若しくは進行中に生成された、ある種のノードを優先する確率分布でもよい。
【００６１】
実際にビーコンを送信したラストｂ＿ｂｕｆｆビーコンノードは、ネットワークのノードの位置を計算するため使用され、反復毎にランダムに選択された新しいビーコンノードがこの集合に含まれ、ｂ＿ｂｕｆｆノードの集合の中の別のノード（例えば、最も古いノード）がこの集合から削除される。したがって、ビーコンベクトルｖiは、後述されるようにネットワークの個別のノードの仮想座標を計算するため使用されるラストｂ＿ｂｕｆｆビーコンノードに関する情報を格納するある種の移動窓であると言える。
【００６２】
ノードｉは、パラメータ「ｉｔｅｒａｔｉｏｎ」が埋め込みの精度を決定するユーザ定義パラメータである、後述のアルゴリズム３に示されているように、それ自体の仮想位置を計算する。これらは同じビーコン集合を使用するローカル反復であり、新しいビーコンメッセージの受信に依存する反復とは異なることに注意すべきである。この「ｉｔｅｒａｔｉｏｎ」は、例えば、（３回の反復という定数のような）固定パラメータでもよく、又は、座標がさらなる反復毎に変化する量のようなある基準に依存していてもよい。著しい変化が存在しないならば、反復は中止される。
【００６３】
このアルゴリズムは、最初に、ビーコンまでのノードの距離を推定し、次に、推定された近接性に適合するように、「振幅」を徐々に減少させながら、ビーコンの方向へノードを押引する。近傍における近接性の平均として近接性を推定することは、ノードが移動可能であるとき、既知の近接性が期限切れになるかもしれないので、特に有用である。
【００６４】
【表４】


【００６５】
アルゴリズム３が今度はより詳細に説明される。
【００６６】
確率論的ビーコニングアプローチでは、ノードの座標はビーコンまでの距離ではないこと、すなわち、ビーコンの個数は仮想座標によるノードの位置を表す座標系の次元性と同じではないことに注意すべきである。しかし、個別のノードのビーコンまでの距離は、ビーコンの仮想座標と共に、後で明らかになるように、このアルゴリズムで使用されている。一実施形態では、全てのノードが以下のステップを実行する（反復ｋの間に、このことは新しいビーコンが新たに選択されたビーコンノードからちょうど送信されたということを意味する）。
【００６７】
（１）反復の最初に、ノードは、それ自体の仮想位置とそれ自体の近傍ノードの仮想位置の平均を計算する。この値は、「プッシュ・アンド・プル」アルゴリズムへの入力である。ノードの仮想位置とその近傍ノードの仮想位置との平均化は選択肢の１つであることに注意すべきである。仮想座標系内のノードの局所的な並べ替えに対処することは役立つが、確率論的ビーコニング手順に必須ではない。このステップ（１）は、アルゴリズム３中でステップ１によって表されている。
【００６８】
（２）再び、アルゴリズム１と同様に、ノードはビーコンまでのそれ自体の距離を、ビーコンまでのそれ自体の距離とビーコンまでのそれ自体の近傍ノードの距離との平均として推定する。この場合の距離指標はホップ数である。同様に、この平均化は、好ましいけれども、選択肢の１つである。このステップは、上述のアルゴリズム３中でステップ２によって表されている。また、このステップは上述のアルゴリズム１中のステップ２とも類似している。
【００６９】
ステップ（１）及び（２）の後に、今度は、ノード毎に２つのタイプの位置情報が存在し、一方の位置情報は、ビーコンベクトル、すなわち可能であれば、近傍ノードと平均化されたホップ数で表された個々のビーコンまでの近接性尺度であり、もう一方は、ｄ次元で表されたノード（及びビーコン）の仮想座標である。これらの２つの異なる位置指標に基づいて、今度は次のステップ３に基づいて、ノード毎に改良された座標が推定される。
【００７０】
（３）開始点として（１）で計算された位置を用いて、ノードは、あらゆるビーコン毎にそれ自体の位置とビーコンの位置との間の直線上で、ノードが移動すべき位置を計算するので、ユークリッド距離（ビーコンの位置とそれ自体の位置との間の距離）が（２）において推定された距離と一致する。換言すると、２種類の距離指標（座標及びビーコンベクトル）が一致される。１回目の反復におけるユークリッド距離は、（ノードの初期座標は単に任意的に選択されているので）完全に誤った値をとるが、ビーコニングメカニズム及び得られるビーコンベクトルは、仮想座標がどの程度間違っているかの指標を与える。ノードｉに対し、ビーコンノードｌの仮想座標に基づいて計算されたビーコンノードｌまでのユークリッド距離が、単なる例として、３であり、ノードｉのビーコンベクトル（又は、よりよくは、ビーコンノードｌに対応するビーコンベクトルの成分）によって与えられる対応する距離尺度が５であると仮定すると、このことは、ビーコンノードｌまでの得られるユークリッド距離が５であるように、ノードｉの仮想座標が補正されるべきであることを意味する。
【００７１】
このステップ３の数学的表現は、上記のアルゴリズム３の３に記載されている。そこから、ビーコンベクトルの成分ｖ毎に（すなわち、ｖ＝０からｂ＿ｂｕｆｆ−１まで）、ノードｉの仮想座標と、ビーコンベクトルの対応する成分、すなわち、この成分に対応するビーコンノードの位置との間で差ベクトルが計算されることがわかる。この差ベクトルは、ノードｉの仮想座標をビーコン信号から取得された近接性尺度と一致させるためにノードｉの仮想座標がシフトされるべき方向を与える。シフトが行われるべきである（かつ、この差ベクトルに乗じられる）量は、ビーコンベクトル成分の対応する成分によって表された近接性尺度ｈvと、ノードｉ及びビーコンノードｖの仮想座標から取得され、ユークリッド距離によって正規化された、ビーコンノードｖまでのユークリッド距離との差によって与えられる。得られた修正ベクトルは、次に、反復が開始したとき用いられた出発ベクトルｘinit（すなわち、ノードｉの出発座標）に加算される。
【００７２】
この結果、ビーコンノードｖ（０からｂ＿ｂｕｆｆ−１まで）毎に修正ベクトルｘtmpが得られ、これらのベクトルがその後総和され、ｂ＿ｂｕｆｆによって正規化され、次の反復ｋ＋１に用いられるノードｉの出発座標ｘを形成する新しいｘinitが取得される。
【００７３】
２回目の反復（ステップｋ＋１）の入力は、したがって、アルゴリズム３のステップ１に関連して既に説明されているように、これらの位置の平均である。今度は、あらゆる後続のステップにおいて、あらゆるビーコン毎にノードは、再び、ビーコンまでの推定距離に適合するように、前の反復において計算された位置と（ビーコンベクトルによって表されているような）ビーコンの位置との間の直線上でそれ自体が移動すべき位置を計算する。所定の回数のステップ（または、誤差がもはや十分に減少しない、というような別の停止基準）の後、アルゴリズムが終了する。ノードの新しい仮想位置は上記の最後の反復の出力である。
【００７４】
図６は、３個のビーコンと２次元の仮想位置とを用いる上記のアルゴリズムの概略的な説明図である。図６に示されている初期位置は、アルゴリズム３のステップ（１）で計算された位置であり、すなわち、それ自体の近傍ノードの座標を使って平均化されたノードｉの仮想座標である。この初期位置に基づいて、現在の反復中にビーコン集合を形成するビーコンノードＢ１、Ｂ２及びＢ３までのユークリッド距離が計算され得る。ノードＢ１、Ｂ２及びＢ３までのユークリッド距離は、初期位置とこれらのノードのロケーションとの間の距離によって図６に概略的に示されている。
【００７５】
ノードＢ１、Ｂ２及びＢ３の周りの円は、ビーコンノード毎に、これらのビーコンによってそれぞれ送信されたビーコン信号によって取得されるような、近接性尺度（proximity measure）（ホップ単位）を概略的に示している。既に説明されているように、近接性尺度は、近傍ノードの近接性尺度と平均化される。ノードｉの初期位置と、ビーコンノードを取り囲むそれぞれの円との間の差は、今度は、ノードｉの仮想座標が近接性尺度と一致させるためにシフトされるべき量を示している。ノードｉ’の位置をビーコンノードＢ１の方向へ修正するため、ノードｉは、Ｂ１を取り囲む大きな円上に小さな円として示されている点までＢ１の方向へシフトされなければならない。同様に、Ｂ２の方向では、ノードｉは、このノードがビーコンノードＢ２を取り囲む大きな円上に示された小さな円に位置するような量だけシフトされなければならない。さらに、Ｂ３の方向では、ノードｉは、シフト後に、このノードがＢ３を取り囲む大きな円上に示された小さな円に位置するような量だけ、シフトされなければならない。
【００７６】
これは、３個のシフトベクトルが結果として生じ、これらのシフトベクトル（各ビーコンに１個ずつ）が次に総計され、ノードｉを「１回目の反復の出力」としてラベル付けされたロケーションへ押し進める合成シフトベクトルを生じることを意味する。１回目反復の出力位置は２回目の反復の入力であり、以下同様である。その後、再び、次の反復において、新しい座標に基づくビーコンまでのユークリッド差が計算され、再度、これらの座標がホップ数によって与えられ、ビーコン信号から取得された近接性尺度と一致又は合致するように、これらの座標をシフトさせることが試行される。これによって、次にビーコン毎に、ビーコンを取り囲む大きな円上に位置する四角形によって表されているような所望の新しい位置、及び、対応する修正ベクトルが得られる。この場合も、合成修正ベクトルが決定され、これにより図６に「２回目の反復の出力」によって表されているようにノードｉの新しい座標が得られる。
【００７７】
この反復手順が収束するか、又は、中止されると（ノードｉの新しい座標が得られ）、プロセス全体は新たな反復を開始する。２つのタイプの反復について話をし、一方は直前に説明され、所与のビーコン集合に基づいてノードｉの位置のための修正ベクトルを取得するために役立つことに注意すべきである。この反復は、ビーコン集合がこれらの反復中にそのまま維持されるので「小さな反復」プロセスとも呼ばれる。さらに、これらの反復は、実際には、これらの「小さな反復」のうちの１回目の反復中に取得された、既に修正された新しい仮想座標をさらに改善するという意味で随意的である。これらの「小さな反復」は、パラメータ「ｉｔｅｒａｔｉｏｎ」として上記の数学的に表されたアルゴリズム３に表現されている。
【００７８】
「大きな反復（large iteration）」と呼ばれ、ここまでは「反復ｋ」又は「反復ｋ＋１」と呼ばれていた反復は、次の反復ｋ＋１におけるビーコン集合の変化である。ビーコンＢ１〜Ｂ３を用いる図６に示されているような手順がノードｉの新しい座標ｘを生成すると、ビーコン集合は、新しいビーコンノードをビーコン集合に組み入れることにより修正される。新しいビーコンノードは、ビーコン集合の中の既存のビーコンノード、例えば、最も旧いビーコンノード、例えば、図６では、Ｂ２及びＢ３の前に集合に入っていたと考えられるビーコンＢ１を置き換える。Ｂ１は、その後、近接性尺度（及びビーコン座標の）サンプルを変更する新しいビーコンＢ４（図６に示されていない）で置き換えられる。このようにして、各々の大きな反復を伴う手順全体は、ネットワークの新たな異なる部分から、埋め込みの品質を改良するために役立つ情報（すなわち、ノードの仮想座標）を取得する。
【００７９】
当業者に明白であるように、ビーコン集合の変更及び新しいビーコンの組み込みは、正確かつ安定した埋め込みを取得するためにアルゴリズム全体の収束を改善するだけでなく、その上、ビーコン集合の定期的な変更は、ノードの移動性及びネットワークの変化の効果に対処するために特に適している。
【００８０】
新しいノードのビーコン集合への組み込みは、ネットワークのノードのうち、ビーコン信号を送信する準備が整い、かつ、ビーコンになるある確率が割り当てられたノードを使用する。実際、任意のノードはある確率ｐでビーコンのフラッディングを開始する。
【００８１】
一実施形態では、ビーコンの個数は、長期間に亘って、埋め込みの品質及び安定性に適合される。このメカニズムは、埋め込み品質（embedding quality）が低いときに確率ｐを増加させ、品質が良好であるときに確率ｐを減少させることにより実施される（確率は、ここでは、ある期間の範囲内での確率、すなわち、頻度を意味する）。埋め込みの品質は、パケット配信比率を測定すること、及び、単一のビーコニングが仮想座標を変化させる量により推定される。この確率は、一実施形態によれば、ネットワークの密度、又は、ビーコンまでの距離にも依存する。
【００８２】
ノード数とは独立であるｐを用いると、ネットワークサイズの増減は時間的にビーコンメッセージの個数を変化させる。上述のように、ビーコンの個数は、ノードの個数ではなく、埋め込みの品質に依存すべきである。一実施形態によれば、確率ｐはしたがって、オーバーヘッドをノードの個数から独立させるために、ネットワークのサイズの変化に適合する（すなわち、確率ｐは、ネットワークサイズが変化したときに、長期間に亘るビーコンメッセージの平均個数が変わらないように適合する）。ネットワークサイズの変化はネットワーク内のビーコニング周波数から推定される。ビーコンの個数の増加はネットワークの大型化を表すので、確率ｐを減少させる原因となる（その逆もまた同様である）。
【００８３】
一実施形態によれば、ビーコンニング確率は、他のビーコンから離れているノード、又は、ネットワークの縁若しくは障害物の近くにあるノードの場合に増加する。同じことは、トラフィック宛先がより高い確率でビーコンを送出するトラフィックに基づくビーコニングの場合にも当てはまる。埋め込みは、通常、ビーコンノードの周りで「より正確」であるので、このような修正はルーティングが成功する確率の上昇につながる。
【００８４】
上記の説明中、本発明の実施形態が詳細に記載されている。これらの実施形態のうちの１つでは、ネットワークの周辺でビーコンを維持し、不利な移動性とチャンネルの条件下で仮想座標系を安定化させるため使用されるビーコンハンドオフ手順が提供される。ビーコン埋め込みアルゴリズム及び局所的な並び替えを取り扱う平均化と組み合わせて使用されると、このアルゴリズムは、モバイルネットワーク内で非常に効率的なルーティングをもたらす。メッセージオーバーヘッドは、連結グラフの固有の次元性（複雑性）だけに依存し、連結グラフのサイズに依存しないが、グリーディルーティングの成功率は実座標の場合より遙かに高い。
【００８５】
別の態様によれば、新しいビーコンが反復毎にランダムに選択される確率論的ビーコニングスキームが提供される。このようなスキームは、損失ビーコンを取り扱うことができるので、ロバスト性を保証する。特に、所与のビーコンの集合への依存性は排除される。Ｆｏｎｓｅｃａ ｅｔ ａｌ．のアプローチと同様に、非常に少数のビーコンノードが、全ての他のノードがビーコンまでのそれ自体の最短経路を学習するように、ネットワークを周期的にフラッドさせる。しかし、Ｆｏｎｓｅｃａ ｅｔ ａｌ．とは違って、ビーコンの集合は、ビーコンが故障した場合だけでなく、連続的に変化する。それどころか、ビーコンの集合は、ある種の所定の方法に従って、例えば、集合内の１個のビーコンをランダムに選択された新しいビーコンとランダムに置き換えることにより、定期的にかつ反復的に変化する。この点は移動性環境及び不確実な環境において有利であり、その理由は、同じビーコンの集合を維持することは、座標系の膨大なシフトの原因となり、その後に、ルーティング目的に適さない非常に不安定な座標系をもたらすからである。しかし、（多少効率は劣るかもしれないが）同じ効果は、新しいビーコンを集合にランダムに挿入することによってのみならず、ある種の所定のパターンに従ってビーコンの集合を変更することによっても達成されることに注意すべきである。このアプローチは、ビーコン集合が定期的かつ反復的にそれ自体のメンバーを変更する限り、ビーコンの集合に基づいて安定した埋め込みを達成することに注意することが重要である。
【００８６】
さらに、一実施形態によれば、数個のビーコンからの独立した距離情報として全てのビーコンを考慮する代わりに、全てのビーコンが次元を削減し、ロバスト性を高めるために組み合わされる。換言すると、ノードのｉ番目の座標は、ビーコンｉまでのそれ自体の距離に依存するだけでなく、全てのビーコンへの距離に基づいて計算される。この手順は、不正確な測定の影響、又は、受信されなかったメッセージの影響を緩和する。
【００８７】
ビーコンを使用して最短経路を計算することは、例えば、ビーコンノードが、それ自体の識別子、シーケンス番号、及び、発信源（初期的に０）から全てのその近傍ノードまでのホップカウントを格納するパケットをブロードキャストし、次に、近傍ノードが、このパケットが初めて見つけられた場合、又は、近傍ノードが記憶していたパケットより小さいホップカウントを有するコピーを受信する場合に、このパケットをブロードキャストするようにして行われる。アルゴリズム３の場合に、ビーコンノードの仮想座標も組み込まれなければならないことに注意すべきである。単一のフラッドのコストは、典型的に１ノード当たり１パケットである。その上、全ノードが少なくとも１回パケットを転送しなければならないので、局所的なブロードキャストが近傍発見メッセージとしてさらに使用される。このアルゴリズムは、ノードを正しい領域に粗く配置するために（不正確な過去の）距離推定値を使用する。一実施形態における新しいビーコンは、実行中にランダムかつ独立に選択される（新しいビーコンはあらゆる反復毎にランダムに選択される）。このようにして、距離情報がこれらのランダムかつ独立に選ばれたビーコンから合成されるように、過去の不正確な距離を取り扱うことが可能である。これは、局所的な平均化アルゴリズムを用いて大域的な「プッシュ・アンド・プルアルゴリズム」の新しい組み合わせを提供すると言える。この局所的なコンポーネントと大域的なコンポーネントとの組み合わせは、上記の不利な条件下で優れた性能をもたらす。
【００８８】
提案されたルーティングスキームによれば、ネットワークは不利な条件（例えば、高い移動性、チャンネルの不確実さ）の下で動作可能な状態を保つ。ルート発見及び維持が持ち込むオーバーヘッドは、匹敵するアプローチより非常に少ない。この点に関して、ビーコンノードによるフラッディングは、ルートを発見するためにフラッドを使用するのとは異なることに注意すべきである。フラッドのコストは、ネットワークのサイズ及びデータトラフィックとは独立に、１ノード当たりのメッセージの個数が少数に保たれるならば、完全に許容可能であり、一方、このコストは、フラッドが送信されたパケット毎に、又は、新しいルート毎に必要であるときには非常に高い。仮想座標スキームによれば、必要とされるビーコンの個数は、ネットワークのサイズに依存せずに、むしろ、ネットワークの固有の次元性に依存する。例えば、ネットワークが２次元内に等距離で埋め込み可能であるならば、ネットワークがどのように大型であっても、全てのノードが３個のノードまでのそれ自体の距離を知れば、全ての他の距離を正確に一意に決定するために十分である。
【００８９】
位置を用いてルーティングするときに極めて重要であるのは、座標系の安定性である。実施形態により提案されているビーコンハンドオフ手順は、第一に、ビーコンがより有用であるネットワークの周辺上にビーコンを維持し、第二に、ノード移動性及び不確実なチャンネルのような不利な条件下で効果的なルーティングを可能にするため十分に座標系を安定化させるので、非常に効果的な地理的ルーティングを可能にする。発振を避けるために、（適応的な）スレッショルドを使用することが可能である。ビーコンノードは、例えば、近傍が所与の期間に亘ってハンドオフ基準を満たしているときに限り、それ自体のビーコンをこの近傍へ引き渡すことに決定する。代替的に、ビーコンノードは、それ自体が仮想空間内で移動したとき、又は、それ自体の近傍集合が変化したときに限り、引き渡しを行うように決定することがある。ビーコンハンドオフ手順は、ビーコンの通過を除いてオーバーヘッドを加えることがなく、既存のアプローチの非常に明瞭な改良である。
【００９０】
確率論的ビーコニングは、埋め込みアルゴリズムがビーコンの特定の集合に依存せずに、むしろ、全ノード（又は、ノードの大規模な集合）がビーコンとしての役割を果たし得るときにも適用可能である。既存のアプローチは、ビーコンの固定した集合に依拠するか、又は、ビーコンがネットワーク内の特定のロケーション（例えば、周辺）に位置することを要求する。反復毎に新たにランダムに選択されたビーコンは、本発明の埋め込みスキームにロバスト性を付け加えるが、その理由は、特定のビーコンの損失が大域的な性能に非常に僅かな影響しか与えないからである。さらに、ランダムに選ばれたビーコンが非常に悪い埋め込みの原因となる可能性は非常に低いが（良好な平均的性能があるが）、決定論的に選択されたビーコンによる最悪のケースは悪い結果をもたらす。このことは、不均一なネットワークにおいて特にその通りであり、運の悪い初期ビーコン選択は性能を台無しにすることがある（例えば、ネットワークの粗く接続されている領域内のビーコンを選択し、密な領域内の全ノードが殆ど同様の位置を取得し、リンクが故障するならば、ビーコンと連絡できなくなるおそれがある）。過去の、しかし、依然として有用な距離情報の記憶と組み合わせは、ルーティングの成功率を見限らないが、あらゆる反復において完全かつ最新の距離情報を必要とする既存のアプローチより通信オーバーヘッドをかなり低減させることを可能にする。ビーコンとしてノードを選択する確率は、ノード全体に亘って均等でもよく、又は、ノードのある種の特性に依存してもよい。ビーコン選択を、ノードの位置、ビーコンノードまでのノードの距離、時刻、ノードの周りのネットワークの密度などに依存させることが可能である。提案されている埋め込みスキームは、低いオーバーヘッドコスト及び分散された方式でグリーディルーティングを実行可能かつ有利にするため、上記の不利な状況下で十分に良好かつ安定した埋め込みを効果的に維持する。
【００９１】
当業者によって理解されるように、上述された実施形態は、ハードウェア、ソフトウェア、又は、ソフトウェアとハードウェアの組み合わせによって実施される。本発明の実施形態と関連して記載されたモジュール及び機能は、本発明の実施形態と関連して説明された方法に従って動作するように適切にプログラムされているマイクロプロセッサ又はコンピュータによって、全体として、又は、部分的に実施され得る。本発明の実施形態を実施する装置は、例えば、本発明の実施形態に記載されているようなアルゴリズムを実行可能であるように適切にプログラムされている、ネットワーク内のノードを備える。
【００９２】
本発明の実施形態によれば、データ担体、又は、記録媒体若しくは伝送リンクのようなある種の物理的な手段によって具現化されたその他の手段の何れかに記憶され、コンピュータ上で実行されるときに、コンピュータが上述された本発明の実施形態に従って動作することを可能にさせるコンピュータプログラムが提供される。
【００９３】
本発明の実施形態は、例えば、上述されているようなルーティングメカニズムに従って動作するようにプログラムされている、ネットワーク内のノードによって実施される。
【図面の簡単な説明】
【００９４】
【図１】本発明が適用されるネットワーク環境を説明する図である。
【図２Ａ】本発明が適用される環境を左側の地理座標において説明する図である。
【図２Ｂ】本発明が適用される環境を右側の仮想座標において説明する図である。
【図３】本発明が適用されるさらなる環境を、左側の地理座標及び右側の仮想座標において説明する図である。
【図４Ａ】ネットワークの変化に起因する座標系のシフトを概略的に説明する図である。
【図４Ｂ】ノードの移動性に起因してどのように埋め込みが時間的に変化するかを概略的に説明する図である。
【図５】本発明の一実施形態によるハンドオフ手順を概略的に説明する図である。
【図６】本発明の一実施形態による埋め込み手順を概略的に説明する図である。
【出願人】 【識別番号】３９２０２６６９３
【氏名又は名称】株式会社エヌ・ティ・ティ・ドコモ
【出願日】 平成１９年７月２７日（２００７．７．２７）
【代理人】 【識別番号】１０００９９６２３
【弁理士】
【氏名又は名称】奥山 尚一

【識別番号】１０００９６７６９
【弁理士】
【氏名又は名称】有原 幸一

【識別番号】１００１０７３１９
【弁理士】
【氏名又は名称】松島 鉄男
【公開番号】 特開２００８−６１２２９（Ｐ２００８−６１２２９Ａ）
【公開日】 平成２０年３月１３日（２００８．３．１３）
【出願番号】 特願２００７−１９６２０１（Ｐ２００７−１９６２０１）