(57)【要約】  ネットワークノードが、ローカル「Ｈｅｌｌｏ」メッセージおよびグローバルトポグラフィ制御（「ＴＣ」）メッセージを含むトポロジ伝播メッセージによって識別されるモバイルアドホック再ルーティングシステムにおいて、新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方に基づいてトポロジ伝播メッセージをトリガするステップが含まれる。【選択図】      図９
2013518466.tif 000002
【特許請求の範囲】
【請求項１】
メディア非依存ハンドオーバ（「ＭＩＨ」）サービスをアドホックルーティングプロトコルと統合するための方法であって、
新たな隣接ノードを特定することおよびリンクロスを特定することに基づいて、ルーティングプロトコルエージェントを中断するためにＭＩＨエージェントを使用するステップ
を含む、方法。
【請求項２】
ネットワークノードがトポロジ伝播メッセージによって識別されるモバイルアドホック再ルーティング方法において、
新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方に基づいてトポロジ伝播メッセージをトリガするステップを含む方法。
【請求項３】
前記トポロジ伝播メッセージをトリガするステップが、新たな隣接ノードの出現を示す、ノード間の受信無線信号の強度を特定することに基づく、請求項２に記載の方法。
【請求項４】
前記トポロジ伝播メッセージをトリガするステップが、隣接ノードを失った可能性があることを示す、ノード間の受信無線信号の強度を特定することに基づく、請求項２に記載の方法。
【請求項５】
「ＯＬＳＲ」（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）プロトコルの一部としてＨｅｌｌｏメッセージおよびＴＣメッセージを使用して前記トポロジ伝播メッセージを実行する、請求項２、３、または４のいずれか一項に記載の方法。
【請求項６】
前記受信無線信号の強度を特定することが物理層パラメータに基づく、請求項３に記載の方法。
【請求項７】
前記物理層パラメータが、無線モデル、無線周波数、伝送電力、および送信ノードと受信ノードとの間の距離のうちの少なくとも１つを含む、請求項６に記載の方法。
【請求項８】
前記新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方を、メディア非依存ハンドオーバ機能（「ＭＩＨＦ」）によって前記ＯＬＳＲに伝える、請求項５に記載の方法。
【請求項９】
前記トリガすることが、新たな隣接ノードを特定することに基づく前記Ｈｅｌｌｏメッセージ、およびリンクロスを特定することに基づく前記ＴＣメッセージの両方にかかる、請求項１に記載の方法。
【請求項１０】
モバイルアドホック再ルーティングシステム内でプロセッサによって実行されるメッセージをトリガする方法であって、
前記モバイルアドホック再ルーティングシステム内で、新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方を実行するステップと、
前記新たな隣接ノードを特定することおよび前記リンクロスを特定することの少なくとも一方に基づいてメッセージをトリガするステップと
を含み、前記新たな隣接ノードの特定を行う場合、前記トリガされるメッセージは、前記隣接ノードを識別するために使用されるＨｅｌｌｏメッセージであり、前記新たな隣接ノードまたはリンクロスの特定を行う場合、前記トリガされるメッセージは、ルーティングコンバージェンスに使用されるトポグラフィ制御（「ＴＣ」）メッセージである、方法。
【請求項１１】
前記トリガするステップが、新たな隣接ノードの出現を示す、ノード間の受信無線信号の強度を特定することに基づくＨｅｌｌｏメッセージまたはＴＣメッセージにかかる、請求項１０に記載の方法。
【請求項１２】
前記トリガするステップが、リンクロスを特定することに基づくＴＣメッセージにかかる、請求項１０に記載の方法。
【請求項１３】
前記ＨｅｌｌｏメッセージおよびＴＣメッセージが、「ＯＬＳＲ」（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）プロトコルの一部として実行される、請求項１０、１１、または１２のいずれか一項に記載の方法。
【請求項１４】
前記受信無線信号の強度を特定することが物理層パラメータに基づく、請求項１０に記載の方法。
【請求項１５】
前記物理層パラメータが、無線モデル、無線周波数、伝送電力、および送信ノードと受信ノードとの間の距離のうちの少なくとも１つを含む、請求項１３に記載の方法。
【請求項１６】
前記新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方を、メディア非依存ハンドオーバ機能（「ＭＩＨＦ」）によってＯＬＳＲに伝える、請求項１２に記載の方法。
【請求項１７】
前記トリガすることが、新たな隣接ノードを特定することに基づく前記Ｈｅｌｌｏメッセージ、およびリンクロスを特定することに基づく前記ＴＣメッセージの両方にかかる、請求項９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
連邦支援の研究または開発に関する声明
米陸軍ＣＥＲＤＥＣによって与えられたＷ１５Ｐ７Ｔ−０８−Ｃ−Ｂ４０５の下、政府の支援により研究への資金提供が行われた。政府は本発明に対して一定の権利を有する。
【０００２】
関連出願の相互参照
本願は、２０１０年１月２１日に出願された米国仮特許出願第６１／２９７，１０７号の出願日の利益を主張し、その開示を参照により本明細書に援用する。
【０００３】
本発明は、アドホックネットワークプロトコルおよび制御アーキテクチャの分野に関する。
【背景技術】
【０００４】
ほとんどのアドホックルーティングプロトコル（大抵はネットワーク層に実装される）はノードの移動性に即座に対応しないので、ノードが動的に移動するモバイルアドホックネットワーク環境では古いルーティング経路が多少の持続時間にわたり残ることがある。その結果、ルーティング経路が更新されるまでパケット損失が発生し、つまりパケットがソースノードから宛先ノードまで搬送される間になくなる。したがって、トラフィックフローが長い期間にわたって中断されることがあり、そのフローに関連するアプリケーションは劣化した性能に見舞われることがある。
【０００５】
「ＯＬＳＲ」（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）などのアドホックルーティングプロトコルでは、ノードの移動性を検出し、ルーティングコンバージェンス（routing convergence）を引き起こすために、ポーリングトリガ式のメカニズムが使用される。ＯＬＳＲで使用されるポーリングトリガメカニズムでは、全てのノードが自らの隣接ノードへのリンク接続に関する情報を周期的にブロードキャストし、各ノードは、受け取ったそれらの周期的提供情報（periodic advertisements）に基づいて自らの隣接ノードの移動性を検出し、自らのルーティングテーブルを更新する。一例として、ＯＬＳＲの「Ｈｅｌｌｏ」メッセージを１秒間隔でブロードキャストすることができ、ＯＬＳＲのトポロジ制御（「ＴＣ」）メッセージを３秒間隔でブロードキャストすることができる。より迅速にノードの移動性を検出し、ルーティングコンバージェンス操作を引き起こすために、ＯＬＳＲのＨｅｌｌｏメッセージやＴＣメッセージなどの周期的な提供情報メッセージの間隔を短くする必要がある。そのような間隔が（例えば１００ミリ秒領域において）短い場合、ノードの移動性をより速く検出することができ、ひいてはルーティングコンバージェンスのための操作を迅速にトリガすることができる。しかし、この手法はより大きな制御オーバーヘッドを結果として招き、つまりとりわけネットワーク密度が高い場合、この手法はネットワーク上で大量の周期的トラフィックを作り出すことによりかなりのネットワークリソースを消費する。
【０００６】
インフラ設置型ネットワーク（infrastructure-based network）のハンドオーバの性能を改善するために、ＩＥＥＥのメディア非依存ハンドオーバ（Media Independent Handover）（「ＭＩＨ」）サービスが使用される。インフラネットワーク環境では、モバイルノードは１つまたは複数のアクセスポイントからの周期的ビーコンメッセージにより自らの１つまたは複数のアクセスポイント（すなわちセルラネットワークの基地局）を検出して保持することができる。周期的ビーコンメッセージのおかげで、モバイルノードはそれらの受信ビーコンの電力レベルを測定することにより、自らの１つまたは複数のアクセスポイントに関する受信電力レベルを保持することもできる。ビーコンメッセージによって得ることができるそのような測定済み受信電力レベルに基づき、インフラネットワークのＭＩＨ機能（「ＭＩＨＦ」）が、ハンドオーバの決定を下すのを助けるフィードバックまたはヒントを提供することができる。ＩＥＥＥ  ８０２．２１ＭＩＨサービスは、インフラ設置型ネットワークのハンドオーバを最適化するように設計されている（「The Network Simulator NS-2 NIST add-on IEEE 802.21 model」NIST Jan.2007を参照されたい）。
【０００７】
しかし、インフラ設置型ネットワークで実現可能な、ビーコンメッセージにより受信電力レベルを取得し保持するためのメカニズムは、アドホックネットワーク環境では周期的ビーコンメッセージがないので実現できない。アドホックネットワーク環境のＭＩＨの観点からすれば、アドホックノードは、アクセスポイントに等しい自らのワンホップ隣接ノードのそれぞれを考慮しなければならない。アドホックノードは、全ての隣接ノードへのリンクの状態（受信電力レベルを含む）を取得し、保持しなければならない。したがって、アドホックノードのＭＩＨＦがワンホップ隣接ノードの受信電力レベルを取得し、保持できるように、ＭＩＨＦの実装をアドホックネットワーク環境のために強化する必要がある。
【０００８】
インフラ設置型ネットワーク環境では、ハンドオフ中のトラフィックの中断を最小限にするために、ＭＩＨＦフレームワークの実装がモバイルインターネットプロトコル（「ＭＩＰ」）などのモビリティプロトコルに統合されている（「The Network Simulator NS-2 NIST add-on IEEE 802.21 model」NIST Jan.2007を参照されたい）。しかし、アドホックネットワーク環境用のアドホックルーティングプロトコルの性能を最適化するためのＭＩＨＦフレームワークにはこれまでのところ対処されていない。
【０００９】
本発明では、アドホックルーティングプロトコルのためのＭＩＨＦフレームワークを実現するのに必要ないくつかの方法（または実施形態）を紹介する。実装の観点では、ＯＬＳＲなどのアドホックルーティングプロトコルとのＭＩＨの統合は、ＮＩＳＴの、ＭＩＰとのＭＩＨの統合とは異なる。ＭＩＰとのＭＩＨの統合では、ＭＩＰを実行しているエンドノードだけがそのＭＩＨＦとインターフェイスし、他のノードはＭＩＨＦを実行する必要がない。しかし、ルーティングとのＭＩＨの統合では、エンドノードだけでなく中間ノード（すなわちルータ）もＭＩＨＦを実行しなければならない。トポロジにもよるが、多くのノードがルーティングコンバージェンスに関与する可能性があるので、ＭＩＨＦおよびアドホックルーティングプロトコルがネットワーク内の全てのノード上で実行される必要がある。ネットワークトポロジに変化が生じるとき、ルーティングのパラメータおよび動作を考慮してハンドオーバのヒントを提供するために、ＭＩＨＦの構成およびフィードバックも異なり得る。
【発明の概要】
【００１０】
本発明の目的は、アドホックルーティングプロトコルのためのＭＩＨフレームワークを提供し、加えてアドホックネットワーク環境上でＭＩＨの有効性を得ることである。
【００１１】
隣接ノードが「Ｈｅｌｌｏ」メッセージによって識別され、ルーティングコンバージェンスがトポグラフィ制御（「ＴＣ」）メッセージに依拠するモバイルアドホック再ルーティング方法を、新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方に基づいて、ＨｅｌｌｏメッセージおよびＴＣメッセージの少なくとも一方をトリガすることによって改善する。好ましくは、このトリガすることは、新たな隣接ノードの出現を示す、ノード間の受信無線信号の強度を特定することに基づくＨｅｌｌｏメッセージにかかるか、またはこのトリガすることは、リンクロスを特定することに基づくＴＣメッセージかかるか、またはその両方にかかる。
【００１２】
ＨｅｌｌｏメッセージおよびＴＣメッセージは「ＯＬＳＲ」（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）プロトコルの一部として実行することができ、受信無線信号の強度を特定することは物理層パラメータに基づくことができ、その物理層パラメータは無線モデル、無線周波数、伝送電力、および送信ノードと受信ノードとの間の距離のうちの少なくとも１つを含むことができる。
【００１３】
好ましい実施形態では、新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方をメディア非依存ハンドオーバ機能（「ＭＩＨＦ」）によってＯＬＳＲに伝える。
【００１４】
言い換えれば、モバイルアドホック再ルーティングシステム内でプロセッサによって実行されるメッセージをトリガする方法を提供し、この方法は、
モバイルアドホック再ルーティングシステム内で、新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方を実行するステップと、新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方に基づいてメッセージをトリガするステップとを含み、新たな隣接ノードの特定を行う場合、トリガされるメッセージは、隣接ノードを識別するために使用されるＨｅｌｌｏメッセージであり、リンクロスの特定を行う場合、トリガされるメッセージは、ルーティングコンバージェンスに使用されるトポグラフィ制御（「ＴＣ」）メッセージである。
【００１５】
本明細書に組み込まれ、本明細書の一部を構成する添付図面に様々な実施形態を例示する。
【図面の簡単な説明】
【００１６】
【図１】静的ネットワークの構成を示す。
【図２】ネットワーク内の物理的操作、ＭＩＨＦ操作、およびＯＬＳＲ操作間の関係を示す。
【図３】第１のネットワークシナリオ（「シナリオ１」）を示す。
【図４】第２のネットワークシナリオ（「シナリオ２」）を示す。
【図５】シナリオ１に適用した第１の手法（「手法１」）の、シミュレーションのパケットドロップ結果を示す。
【図６】シナリオ２に適用した手法１および第２の手法（「手法２」）のシミュレートされたパケットドロップ結果を示す。
【図７】シナリオ１のパケットドロップ率および制御オーバーヘッドの両方を見たときの、シミュレートされた性能比較を示す。
【図８】シナリオ２のパケットドロップ率および制御オーバーヘッドの両方を見たときの、シミュレートされた性能比較を示す。
【図９】ＭＩＨを伴う場合、伴わない場合の、切断時間とオーバーヘッドとの間の性能トレードオフを示す、いくつかのＯＬＳＲ  Ｈｅｌｌｏレートパラメータについてのシミュレートされた性能の結果を示す。
【発明を実施するための形態】
【００１７】
本明細書に提示する技法の完全な理解を提供するために、以下の説明では、限定目的ではなく説明目的で特定のステップシーケンス、インターフェイス、構成などの独特の技法および実施形態を示す。それらの技法および実施形態は、添付図面に照らして主に説明するが、他の電子装置または電子システムでも実践できることを当業者ならさらに理解されよう。
【００１８】
次に、その例を添付図面に示す本発明の例示的実施形態について詳しく言及する。可能な場合はいつも、図面の全体を通して同じ参照番号を使用して同じまたは同様の部分を指す。
【００１９】
本発明では、アドホックネットワーク環境用のアドホックルーティングプロトコルのためのＭＩＨフレームワークを紹介する。そのようなフレームワークを実現するために、ＭＩＨＦが受信電力やリンクロスの特定などの基礎をなす下位層情報を集め、この下位層情報から得たＭＩＨ情報をアドホックルーティングプロトコルに提供する。ルーティングプロトコルはそのＭＩＨ情報を使用して、ＯＬＳＲのＨｅｌｌｏメッセージおよび／またはＴＣメッセージなどの操作上のイベントのトリガを制御する。これらのメッセージを定期間隔で常に伝送させておくのではなく、ＭＩＨの受信電力およびリンクロスの特定を使用することによってこうした同じメッセージをトリガすることができ、したがってより効率的な方法で伝送することができる。その結果これらのイベントは下位層情報を提供し、その下位層情報は、中断によってトリガされるＨｅｌｌｏメッセージおよびＴＣメッセージならびに関係するルーティングコンバージェンス操作のソースとなる、下位層情報または層間情報として分類することができる。
【００２０】
このようにして、大きな制御オーバーヘッドを伴うポーリングトリガの代わりに、本発明は、周期的な検出メッセージに依存しない中断的トリガ(interruptive-trigger)であって、中断をもたらす制御オーバーヘッドを発生させることなしに、受信信号電力や無線リンク状態などの、基礎をなす下位層情報を用いる中断的トリガ(interruptive-trigger)を使用する。
【００２１】
この中断的トリガ手法を実現するために、本発明は、基礎をなす下位層から必要な情報を得るためにＩＥＥＥ  ８０２．２１  ＭＩＨＦのサービスを活用し、ＭＩＨＦのこれらのサービスをＯＬＳＲプロトコルに統合する。ＭＩＨＦから得るサービスに基づいて、ＯＬＳＲプロトコルは、繰り返しの(repeated)Ｈｅｌｌｏ、Ｌｉｎｋ＿Ｄｏｗｎ時のＴＣ、新たな隣接ノード時のＴＣなどのトリガリングイベントを引き起こす。
【００２２】
さらに本発明の中断トリガプロセスでは、ルーティングコンバージェンス操作のためのトリガのシーケンスが性能を改善するための重要な要素になる。シミュレーション結果によれば、新たな隣接ノードの特定時に追加の繰り返しＨｅｌｌｏメッセージを投入するシーケンス、新たな隣接ノードの特定時に追加のＴＣメッセージを送信するシーケンス、およびＬｉｎｋ＿Ｄｏｗｎ時に追加のＴＣメッセージを送信するシーケンスが、モビリティ中のＯＬＳＲルーティングプロトコルの優れた性能を実現した。
【００２３】
本発明者らは、スペインのUniversity of Murcia（「ＵＭ」）からのＯＬＳＲモデルを使用し、それをＭＩＨと連携するように更新した。ＵＭ−ＯＬＳＲは、ＲＦＣ  ３６２６に準拠し（T. ClausenおよびP. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC 3626, Oct. 2003を参照されたい）、ＯＬＳＲの全てのコア機能をサポートする。シミュレータ全体を再コンパイルする必要なしに、デバッグモードを活性化または非活性化することができ、制御メッセージの間隔も設定可能である。
【００２４】
ＵＭ−ＯＬＳＲの動作を検証するために、本発明者らは図１に示すように静的トポロジを有する簡易シミュレーションネットワーク、つまりＯＬＳＲの動作およびパケット配信の検査のための簡易ネットワークを作成した。シミュレーションでは、無線範囲は約２００メートルであり、パケットサイズは１０００バイトであり、データ転送速度は１０パケット／秒であり、ＯＬＳＲのＨｅｌｌｏ間隔は１秒であり、ＯＬＳＲのトポロジ制御（「ＴＣ」）間隔は３秒である。シミュレーションの持続時間は１００秒である。このシミュレーションネットワークのルーティングコンバージェンスの１０秒後のシミュレーション時間に、ソースｎ４がパケットを送信し始める。受信側ｎ０は、パケット損失が一切なしに全６００パケットを受信した。さらに、ルーティングの一貫性を得るために、どのノードのルーティングテーブルも検証される。
【００２５】
本発明は、インフラ設置型ネットワーク向けに設計されたNational Institute of Science and Technology(「ＮＩＳＴ」)のＮＳ−２モデルに基づき、アドホックネットワーク環境についてのＩＥＥＥ  ８０２．２１規格のフレームワーク内で最初に実施した。
【００２６】
本発明によれば、２つのトリガのいずれかまたは両方がＭＩＨＦの機能を使用してＯＬＳＲの性能を改善し、その２つのトリガとはつまり、（１）隣接ノードから受け取る無線信号電力が実際のリンクを確立するのに必要なレベルに到達することを検出することにより、新たな隣接ノードが接近していることをＭＩＨエージェントが検出するとき、繰り返しの「Ｈｅｌｌｏ」メッセージを引き起こすようにＯＬＳＲをトリガすること、（２）加えて、ノードのＭＩＨエージェントがＬｉｎｋ＿Ｇｏｉｎｇ＿Ｄｏｗｎイベントまたは新たな隣接ノードをそれぞれ検出するとき、リンクを除去または追加し、「ＴＣ更新」メッセージを送信するようにＯＬＳＲをトリガすることである。
【００２７】
これらの手法では、Ｈｅｌｌｏメッセージを単により頻繁に送信する従来の手法によって予期され得るよりもＨｅｌｌｏメッセージを低い頻度で送信するが、トリガされる場合、Ｈｅｌｌｏメッセージは好ましくはより素早い連続で送信され、それにより新たなリンクを従来のシーケンスの場合よりも迅速に関与させるが、新たなリンクを形成するために必要である可能性が最も高いときにＨｅｌｌｏメッセージを全体に送信する回数を減らすことにより、オーバーヘッドの増加を回避する。
【００２８】
さらに、ＭＩＨイベントがリンクロスまたは新たなリンクを検出するとき、次に予定されている周期的ＴＣメッセージに依拠するのではなく、ＴＣリンク更新メッセージを送信することにより、ネットワーク内の他のルータ内のリンクリストをより迅速かつ効果的に更新する。
【００２９】
アドホックネットワーク環境では、アドホックノードのＭＩＨＦが新たなリンクを検出し、隣接ノードに関するそれらのリンクの状態を保持する。図２に示すように、これは媒体アクセス制御（「ＭＡＣ」）／物理（「ＰＨＹ」）層によって実現される。各パケットの受信信号電力は、実際の実装形態およびＮＳ−２シミュレーションの両方において、無線モデル、無線周波数、伝送電力、パケットの送信側と受信側との間の距離などのＰＨＹ層パラメータに基づいて推定することができる。無線パラメータがある設定閾値を上回る場合、送信側のアドレス（ＭＡＣアドレスまたはＩＰアドレス）とともにこの推定信号電力に関する情報がＭＩＨＦに送られる。ＯＬＳＲがトリガを受け取り、リンクを維持するのに必要な受信信号電力に近いまたはそれを超える十分な受信信号電力により、ＭＩＨイベントを新たな隣接ノードの検出とみなす場合、Ｈｅｌｌｏメッセージを起こしてその新たな隣接ノードを識別する。ＯＬＳＲがトリガを受け取り、ＭＩＨイベントをリンクロスイベントとみなす場合、適切なＴＣメッセージを起こして関連する隣接ノード内のリンクリストを更新する。
【００３０】
第１の手法（「手法１」）（ソースノードと受信ノードとの間に２つの可能な２ホップ経路を提供する、図３に示す第１のネットワークシナリオ（「シナリオ１」）に適用される）は、繰り返しのＨｅｌｌｏトリガを引き起こす。シナリオ１では、ソースｎ４が横線に沿って移動している受信側ｎ０にパケットを送信し、この横移動は、受信側ｎ０が自らの経路の最初の部分に関してｎ１に接続することを可能にし、自らの経路の後者の部分に関してｎ２に接続することを可能にする。ｎ０がｎ１だけのカバレッジ内にある場合、パケットは転送ノードｎ３およびｎ１を介してｎ０に送られる。ｎ３がｎ０宛のパケットを受け取ると、ｎ３は自らの現在のルーティングテーブルに従い、そのパケットをパケットの次のルーティングホップであるｎ１に転送する。他方で、ｎ０がｎ２だけのカバレッジエリア内に移動すると、ｎ３がパケットをｎ１ではなくｎ２に転送できるように、ｎ２およびｎ３の両方におけるｎ０に関する既存のルーティングエントリを更新しなければならない。このネットワーク（図３に示す）では、ｎ０とｎ２との間に対称リンクを確立するための、ｎ０とｎ２との間の「Ｈｅｌｌｏ」メッセージのやり取り、およびｎ３においてルーティングの更新をもたらす、対称リンクを確立した後のｎ２からの「Ｈｅｌｌｏ」メッセージによってルーティングコンバージェンスが実現される。
【００３１】
図３のシナリオ１のみに例として適用する手法１では、ソースノードから宛先ノードまでの経路上のルーティングテーブルを更新するためにＴＣメッセージは関与せず、２ホップ距離内に限ったノードにおいてルーティングの更新が必要なトポロジ変更に対するルーティングコンバージェンスは、２つの連続したＨｅｌｌｏメッセージによって（それらのＨｅｌｌｏメッセージが衝突やチャネル状態に起因するパケット損失に遭っていない場合に限り）実現することができる。Ｈｅｌｌｏ間隔はＴＣ間隔よりも通常は短いので（例えば１秒対３秒）、このような場合のコンバージェンス時間は短い。重複エリア（すなわちｎ１およびｎ２両方のカバレッジ）内に移動しながらｎ０とｎ１との間の対称リンクを確立できるほど重複エリアが十分に広い場合、ノードはパケット損失を経験しないことに留意されたい。また、より大規模なネットワークのルーティングコンバージェンスのために、ＴＣメッセージは依然として必要であることにも留意されたい。
【００３２】
手法１では、ＭＩＨエージェント（すなわちＭＩＨＦ）が新たな隣接ノードを検出する（すなわち新たなリンクを検出する）場合に、または互いから受信するパケットに関する自らの受信電力レベルが、リンクを維持するのに必要な既定の受信電力レベルに近づく又は上回ることをｎ０およびｎ２のＭＩＨエージェントが検出する場合に、繰り返しの「Ｈｅｌｌｏ」メッセージを引き起こすためのトリガ（すなわちＨｅｌｌｏトリガ）をノードのＭＩＨエージェントがＯＬＳＲエージェントのために生成する。いずれにせよ、ＭＩＨエージェントは自らのＯＬＳＲエージェントをトリガしてＨｅｌｌｏメッセージを引き起こす。無線カバレッジが原因で新たに確立されるリンクのチャネル状態がまだ信頼できない場合があり、（隠れ端末状態（hidden terminal condition）に起因する）Ｈｅｌｌｏメッセージとデータパケットとの間の衝突の可能性もあるので、好ましくはＨｅｌｌｏメッセージを短期間にわたり、時間に関して非常に近接して（例えば２秒間にわたり、１秒当たり５回）リリースする。
【００３３】
第２の手法（「手法２」）（ソースノードと受信ノードとの間に２ホップおよび３ホップの可能な経路を提供する、図４に示す第２のネットワークシナリオ（「シナリオ２」）に適用される）は、Ｈｅｌｌｏトリガに加えてＴＣトリガのシーケンスを提供する。シナリオ２は、２ホップ距離を超える経路上のノードにおいてルーティングの更新が必要な、ソースから宛先までのルーティング経路についてのルーティングコンバージェンスの事例を検討する。シナリオ２では、ｎ０がｎ２に移動するとき、ｎ５からｎ０までの、ｎ３およびｎ１を介した古い経路を削除し、ｎ５、ｎ６、ｎ４、およびｎ２におけるｎ０に関する既存のルーティングエントリを更新することにより、ｎ５からｎ０までの新たなルーティング経路を確立する必要がある。このルーティングコンバージェンスプロセスの興味深い部分は、ｎ５におけるルーティングの更新プロセスである。ｎ０がｎ１と提携している場合、ｎ１からのＴＣメッセージに基づき、ｎ５はｎ０がｎ１に直接接続されており、３ホップ距離離れて位置していることを認識する。そのようなトポロジ情報は、トポロジ制御（「ＴＣ」）テーブル内に記憶される。このＯＬＳＲの実装形態では、ノードがルーティングテーブル、ＴＣテーブル、リンクテーブル、および隣接テーブルを保持することに留意されたい。
【００３４】
ｎ０がｎ２に移動し、ｎ０とｎ２との間の新たな対称リンクが確立されると、ｎ２はＴＣメッセージをフラッディングし（flood）、そのＴＣメッセージによりネットワーク上のｎ５を含むノードは、ｎ２がｎ０との直接接続を有することを知らされる。これは、ｎ１からのＴＣメッセージによって前に記録されたｎ０に関するＴＣ情報を、ｎ５が上書きすることを意味するものではない。むしろｎ５は、ｎ１およびｎ２の両方からのＴＣ情報を別個のＴＣエントリとして保ち、ｎ５はあたかもｎ０がｎ１およびｎ２の両方に接続されているかのようにみなす。この移行期間において、ｎ５はｎ０に関する２つのルーティング経路、つまりｎ１に向かう１つの経路およびｎ２に向かうもう１つの経路を有する。ただし、ｎ１までのルーティング距離はｎ２までのルーティング距離よりも１ホップ短いので、ｎ５はｎ２の代わりにｎ１に向かう経路を選択する。
【００３５】
そのような計算を誤ったルーティングはパケット損失をもたらし、そのパケット損失は、ｎ０がもはやｎ１に接続されていないことをアドバタイズする更新済みＴＣメッセージをｎ５がｎ１から受信するまで続く。この更新済みＴＣメッセージは、ｎ０についての隣接ノード保持タイマが失効することをｎ１が確認する場合にのみ生成することができる。言い換えれば、ｎ１が既定の隣接ノード保持期間（我々のシミュレーションでは約６秒）の間にｎ０から「Ｈｅｌｌｏ」メッセージを一切受信していない場合、ｎ１はもはやｎ０を自らの隣接ノードとみなさず、ＭＰＲに基づく効率的なフラッディングにより更新済みＴＣメッセージを生成してアドバタイズする。
【００３６】
図４のシナリオ２に限定ではなく例として適用する本発明の手法２では、ＭＩＨエージェントが新たな隣接ノードまたはＬｉｎｋ＿Ｇｏｉｎｇ＿Ｄｏｗｎイベントを検出する場合、ノードのＭＩＨエージェントがノードのＯＬＳＲエージェントを中断する。したがって図４のシナリオ２では、ｎ０、ｎ１、およびｎ２のＯＬＳＲエージェントによって３つの異なるトリガのシーケンス、つまり新たな隣接ノードの特定時のｎ０およびｎ２による繰り返しのＨｅｌｌｏトリガ、新たな隣接ノードの特定時のｎ２によるＴＣトリガ、およびＬｉｎｋ＿Ｄｏｗｎ時のｎ１によるＴＣトリガが引き起こされる。ｎ１のＯＬＳＲエージェントは、ｎ１とｎ０との間のリンクが停止していることを迅速に検出でき、典型的には約６秒である隣接ノード保持失効時間を待つことなしにそのリンクを除去する。リンクを削除すると、ｎ１は直ちに（次の周期的ＴＣ更新時間を待たずに）、ｎ０がもはやｎ１の隣接ノードではないことをＴＣメッセージによってアドバタイズする。よって、ｎ０までのルーティングに関してソースｎ５のルーティングテーブルが更新される。その結果、この特定のシナリオでは、０．３秒のトラフィック中断を伴い、ルーティングコンバージェンス時間が大幅に短縮される。
【００３７】
図５に示すように、シミュレーションを通して、ＨｅｌｌｏメッセージをトリガするためのＭＩＨを有するＯＬＳＲは、それぞれに異なる全ての「Ｈｅｌｌｏ」間隔についてＭＩＨなしのＯＬＳＲよりも性能が優れている。ハンドオフ中にドロップしたパケットの数は、ネットワークシナリオ１の手法１によって大幅に減少している。図６に示すように、手法１はここでも大幅に減少したパケット損失を示しているが、手法２がパケット損失をさらに減らせることも示している。したがって、手法１と手法２とを組み合わせることが、シナリオ２ではＭＩＨなしのＯＬＳＲよりもトラフィックの中断を著しく減らす。
【００３８】
図７および図８に示すように、手法１および手法２は、パケット損失だけでなく制御オーバーヘッドも同時に減らすことにより、ＯＬＳＲの性能に対してかなりの改善をもたらしている。例えばシナリオ２に関する図８に示すように、モビリティに起因するパケット損失は、トラフィックの１０パケット／秒の固定ビットレート（「ＣＢＲ」）で約９７％減らすことができ、「Ｈｅｌｌｏ」間隔を１秒から２秒に変えることにより制御オーバーヘッドも約５０％同時に減らすことができる。図９に、手法１および手法２を使用することによる、同時に存在する利得を要約した。このグラフは、ＭＩＨＦ中断トリガ法を使用することが、切断時間の大幅な短縮および低減されたオーバーヘッドの両方を可能にし得ることを示す。基本的には、アドホックネットワーク環境内のアドホックルーティングプロトコルに関するオーバーヘッドと切断時間との間のトレードオフをシフトし、そのようなシフトは、拡張可能、高信頼、かつ効率的なアドホックネットワークを得るための主要な要因の１つである。
【００３９】
このようにして、上記に記載したモビリティシナリオについてシミュレーションを行った。それぞれの事例で、ＭＩＨＦなしのＯＬＳＲおよびＭＩＨＦを有するＯＬＳＲの両方の性能を異なる「Ｈｅｌｌｏ」間隔について評価した。それらをパケット損失および制御オーバーヘッドの点で比較した。以下の表は、シミュレーションの操作パラメータを示す。
【００４０】
【表１】
2013518466.tif 000003
【００４１】
こうして本発明は、アドホックネットワーク環境における性能および効率を高める。本発明によれば、ＭＩＨの値を捕捉するために、ＭＩＨユーザなど、プロアクティブ型のアドホックルーティングプロトコルのうちの１つとともにＯＬＳＲを使用する。ＯＬＳＲをＭＩＨユーザとして使用可能にするために、アドホックネットワーク環境のためのＭＩＨＦのリンク検出メカニズムを強化し、次いでＯＬＳＲプロトコルとＭＩＨプロトコルとの間にＭＩＨイベントをＯＬＳＲプロトコルに送るインターフェイスを実装し、最後に、ＭＩＨからのイベントを処理する機能をＯＬＳＲプロトコル上に実装する。
【００４２】
ＯＬＳＲの典型的なルーティング動作を明らかにすることができる２つのアドホックネットワークシナリオを開示し、その両方をルーティングコンバージェンスに関して分析する。ＯＬＳＲのルーティング動作の分析に基づき、ＭＩＨによってＯＬＳＲのルーティングコンバージェンスを改善するための２つの手法、つまりＭＩＨによって駆動される「Ｈｅｌｌｏ」トリガ、およびＭＩＨによって駆動される「ＨｅｌｌｏとＴＣ」トリガを提供する。
【００４３】
手法１および手法２を用いてシナリオ１およびシナリオ２に関するシミュレーションを行い、ＭＩＨなしのＯＬＳＲと比較した。シミュレーションの結果によれば、手法１は、２ホップ以下のルーティングの更新を必要とするネットワークシナリオについて、ルーティングコンバージェンス時間を短縮することによりＯＬＳＲの性能を改善した。ただしそれ自体では、この手法は２ホップを超えるルーティングの更新を必要とするネットワークシナリオではさほど効果的でない。その一方で手法２は、２ホップを超えるルーティングの更新を必要とするネットワークシナリオについてＯＬＳＲの性能を改善した。全体として、ＭＩＨを統合することにより、ＯＬＳＲの性能が著しく改善された。
【００４４】
上記の説明は例示目的で示してきた。この説明は網羅的ではなく、本発明を開示した厳密な形態または実施形態に限定することはない。本明細書を検討し、開示した本発明の諸実施形態を実践することから、本発明の修正および適合を行うことができる。例えば上記に記載した方法の１つまたは複数のステップを別の順序でまたは同時に実行してもよく、それでもなお望ましい結果を実現することができる。
【００４５】
本明細書を検討し、本明細書に開示した本発明を実践することから、本発明の他の実施形態が当業者に明らかになるであろう。本明細書および各例は専ら例示とみなされることを意図し、本発明の真の範囲は特許請求の範囲に示している。
【図１】
2013518466.tif 000004
【図２】
2013518466.tif 000005
【図３】
2013518466.tif 000006
【図４】
2013518466.tif 000007
【図５】
2013518466.tif 000008
【図６】
2013518466.tif 000009
【図７】
2013518466.tif 000010
【図８】
2013518466.tif 000011
【図９】
2013518466.tif 000012
【手続補正書】
【提出日】平成24年9月21日(2012.9.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワーク内の新たな隣接ノードまたはリンクロスの少なくとも一方を、前記ネットワーク内のコンピューティングデバイスによって特定するステップと、
前記ネットワーク内の前記新たな隣接ノードまたは前記リンクロスの少なくとも一方を特定することに応答し、前記ネットワーク内のルーティングプロトコルエージェントを中断するためにメディア非依存ハンドオーバ（ＭＩＨ）エージェントを前記コンピューティングデバイスによって使用するステップと
を含む、方法。
【請求項２】
新たな隣接ノードまたはリンクロスの少なくとも一方を、ネットワーク内のコンピューティングデバイスによって特定するステップと、
前記新たな隣接ノードまたは前記リンクロスの少なくとも一方を特定することに応答し、トポロジ伝播メッセージを前記コンピューティングデバイスによってトリガするステップと
を含む、方法。
【請求項３】
前記新たな隣接ノードを特定するために、前記ネットワーク内のノード間の受信無線信号の強度を特定するステップをさらに含み、前記トポロジ伝播メッセージをトリガするステップが、前記受信無線信号の前記強度を特定することに少なくとも部分的に基づく、請求項２に記載の方法。
【請求項４】
前記リンクロスを特定するために、ノード間の受信無線信号の強度を特定するステップをさらに含み、前記トポロジ伝播メッセージをトリガするステップが、前記受信無線信号の前記強度を特定することに少なくとも部分的に基づく、請求項２に記載の方法。
【請求項５】
ＯＬＳＲ（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）プロトコルの一部として、ｈｅｌｌｏメッセージまたはトポグラフィ制御（ＴＣ）メッセージの少なくとも一方を使用して前記トポロジ伝播メッセージを実行する、請求項２に記載の方法。
【請求項６】
前記受信無線信号の前記強度を特定することが、１つまたは複数の物理層パラメータに基づく、請求項３に記載の方法。
【請求項７】
前記１つまたは複数の物理層パラメータが、無線モデル、無線周波数、伝送電力、または送信ノードと受信ノードとの間の距離のうちの少なくとも１つを含む、請求項６に記載の方法。
【請求項８】
前記新たな隣接ノードまたは前記リンクロスの少なくとも一方を特定することを、メディア非依存ハンドオーバ機能（ＭＩＨＦ）によって前記ＯＬＳＲに伝える、請求項５に記載の方法。
【請求項９】
トリガするステップが、前記新たな隣接ノードを特定することに応答してｈｅｌｌｏメッセージを、前記リンクロスを特定することに基づいてトポグラフィ制御（ＴＣ）メッセージをトリガするステップを含む、請求項２に記載の方法。
【請求項１０】
モバイル再ルーティングシステム内で、新たな隣接ノードを特定することおよびリンクロスを特定することの少なくとも一方を実行するステップと、
前記新たな隣接ノードを特定することまたは前記リンクロスを特定することの少なくとも一方に応答してメッセージをトリガするステップと
を含み、前記メッセージは、前記新たな隣接ノードの特定に応答した、１つまたは複数の新たな隣接ノードを特定するために使用されるｈｅｌｌｏメッセージであり、前記メッセージは、前記リンクロスの特定に応答した、ルーティングコンバージェンスに使用されるトポグラフィ制御（ＴＣ）メッセージである、方法。
【請求項１１】
ノード間の受信無線信号の強度を特定するステップをさらに含み、前記メッセージは、ノード間の前記受信無線信号の前記強度を特定することに少なくとも部分的に基づく、請求項１０に記載の方法。
【請求項１２】
前記トリガするステップが、前記新たな隣接ノードを特定することに基づく前記ＴＣメッセージにかかる、請求項１０に記載の方法。
【請求項１３】
前記ｈｅｌｌｏメッセージおよび前記ＴＣメッセージが、ＯＬＳＲ（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）プロトコルの一部として実行される、請求項１０に記載の方法。
【請求項１４】
前記受信無線信号の前記強度を特定することが、１つまたは複数の物理層パラメータに基づいて特定される、請求項１１に記載の方法。
【請求項１５】
前記１つまたは複数の物理層パラメータが、無線モデル、無線周波数、伝送電力、または送信ノードと受信ノードとの間の距離のうちの少なくとも１つを含む、請求項１４に記載の方法。
【請求項１６】
前記新たな隣接ノードを特定することまたは前記リンクロスを特定することの少なくとも一方を、メディア非依存ハンドオーバ機能（ＭＩＨＦ）によって前記ＯＬＳＲに伝える、請求項１３に記載の方法。
【請求項１７】
前記トリガするステップが、前記新たな隣接ノードを特定することに基づく前記ｈｅｌｌｏメッセージ、および前記リンクロスを特定することに基づく前記ＴＣメッセージの両方にかかる、請求項１０に記載の方法。
【請求項１８】
メディア非依存ハンドオーバ（ＭＩＨ）エージェントを記憶するように構成されるメモリと、
前記メモリに動作可能に結合され、
ネットワーク内で新たな隣接ノードまたはリンクロスの少なくとも一方を特定し、
前記新たな隣接ノードまたは前記リンクロスの少なくとも一方に応答して、前記ネットワーク内のルーティングプロトコルエージェントを中断するために前記ＭＩＨエージェントを使用する
ように構成されるプロセッサと
を含む、システム。
【請求項１９】
前記プロセッサが、前記リンクロスを特定するためにノード間の受信無線信号の強度を特定するようにさらに構成される、請求項１８に記載のシステム。
【請求項２０】
前記プロセッサが、前記新たな隣接ノードを特定するためにノード間の受信無線信号の強度を特定するようにさらに構成される、請求項１８に記載のシステム。
【請求項２１】
メモリと、
前記メモリに動作可能に結合され、
ネットワーク内で新たな隣接ノードまたはリンクロスの少なくとも一方を特定し、
前記新たな隣接ノードまたは前記リンクロスの少なくとも一方に基づいて、１つまたは複数のトポロジ伝播メッセージをトリガする
ように構成されるプロセッサと
を含む、システム。
【請求項２２】
ＯＬＳＲ（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）プロトコルの一部として、ｈｅｌｌｏメッセージまたはトポグラフィ制御（ＴＣ）メッセージの少なくとも一方を使用して前記トポロジ伝播メッセージを実行する、請求項２１に記載のシステム。
【請求項２３】
前記新たな隣接ノードまたは前記リンクロスの少なくとも一方を特定することを、メディア非依存ハンドオーバ機能（ＭＩＨＦ）によって前記ＯＬＳＲに伝える、請求項２１に記載のシステム。
【請求項２４】
前記１つまたは複数のトポロジ伝播メッセージが、前記新たな隣接ノードを特定することに基づく前記ｈｅｌｌｏメッセージ、および前記リンクロスを特定することに基づく前記ＴＣメッセージの両方を含む、請求項２１に記載のシステム。
【国際調査報告】
2013518466.tif 000013