(57)【要約】ネットワーク内の通信要件を検出し、条件が許す場合にノードを様々なアクティビティ・ステージに配置するためのシステムおよび方法。このシステムおよび方法は、ノード・アクティビティ・レベルの変化を検出し、検出された変化に基づいて、更新伝送および経路選択などの動作を変更するためのアルゴリズムを提供する。特に、このアルゴリズムは、ノードが到達可能な新しい宛先の数、ノードが実現可能な経路変更の数、ノードからの経路のうち、その長さが変化した経路の数、ノードがもはや到達不能な宛先の数などの要因に基づいて、各経路指定更新間隔でのノードのアクティビティ・レベルを決定する。次に、ノードは、このアクティビティ・レベルの増加または減少に基づいて、隣接ノードとその経路指定情報を交換する際の率を増加または減少することができる。
2005525061.tif 000002
【特許請求の範囲】
【請求項１】
ノード・アクティビティに基づいて臨時ワイヤレス・ネットワーク内の通信を制御するための方法において、
アルゴリズムを使用して、あるノードでのアクティビティ・レベルを決定するステップであって、前記ノードが前記ネットワーク内の少なくとも１つの他の隣接ノードに情報を送信する際の情報交換率を前記ノードが有する、前記決定するステップと、
前記アクティビティ・レベルの変化に応答して前記情報交換率を変更するステップとを含む、方法。
【請求項２】
前記アルゴリズムが、前記ノードおよび前記隣接ノードのいずれかのうちの少なくとも１つの移動を考慮する、請求項１に記載の方法。
【請求項３】
前記アルゴリズムが
合計＝新しい宛先＋新しい次のホップ＋新しい経路指定長＋削除された宛先
という式に応じて前記アクティビティ・レベルを決定し、
ここで、「新しい宛先」は前記ノードが到達可能な新しい宛先の数を表し、「新しい次のホップ」は前記ノードが実現可能な経路変更の数を表し、「新しい経路指定長」は前記ノードからの経路のうち、その長さが変化した経路の数を表し、「削除された宛先」は前記ノードがもはや到達不能な宛先の数を表す、請求項１に記載の方法。
【請求項４】
前記ノードがデータ・パケットの形で前記情報を送信する、請求項１に記載の方法。
【請求項５】
前記情報が前記ノードに関する経路指定情報を含む、請求項１に記載の方法。
【請求項６】
前記変更ステップが、それぞれ前記アクティビティの増加または減少に応答して前記情報交換率を増加または減少する、請求項１に記載の方法。
【請求項７】
前記アクティビティ・レベルが最低であるときに前記情報交換率が最小値を有する、請求項１に記載の方法。
【請求項８】
前記ノードが、センサ、モバイル・デバイス、ルータ、またはインテリジェント・アクセス・ポイントを含む、請求項１に記載の方法。
【請求項９】
ノード・アクティビティに基づいてその通信を制御するように適合された臨時通信ネットワーク内のノードにおいて、前記ノードが、
第１のアルゴリズムを使用して、前記ノードでのアクティビティ・レベルを決定するように適合されたコントローラであって、前記ノードが前記ネットワーク内の少なくとも１つの他の隣接ノードに情報を送信する際の情報交換率を前記ノードが有するコントローラを含み、
前記コントローラが、前記アクティビティ・レベルの変化に応答して前記情報交換率を変更するようにさらに適合される、前記ノード。
【請求項１０】
前記アルゴリズムが、前記ノードおよび前記隣接ノードのいずれかのうちの少なくとも１つの移動を考慮する、請求項９に記載のノード。
【請求項１１】
前記アルゴリズムが
合計＝新しい宛先＋新しい次のホップ＋新しい経路指定長＋削除された宛先
という式に応じて前記アクティビティ・レベルを決定し、
ここで、「新しい宛先」は前記ノードが到達可能な新しい宛先の数を表し、「新しい次のホップ」は前記ノードが実現可能な経路変更の数を表し、「新しい経路指定長」は前記ノードからの経路のうち、その長さが変化した経路の数を表し、「削除された宛先」は前記ノードがもはや到達不能な宛先の数を表す、請求項９に記載のノード。
【請求項１２】
データ・パケットの形で前記情報を送信するように適合された送信機をさらに含む、請求項９に記載のノード。
【請求項１３】
前記情報が前記ノードに関する経路指定情報を含む、請求項９に記載のノード。
【請求項１４】
前記コントローラが、それぞれ前記アクティビティの増加または減少に応答して前記情報交換率を増加または減少する、請求項９に記載のノード。
【請求項１５】
前記アクティビティ・レベルが最低であるときに前記情報交換率が最小値を有する、請求項９に記載のノード。
【請求項１６】
前記ノードが、センサ、モバイル・デバイス、ルータ、またはインテリジェント・アクセス・ポイントを含む、請求項９に記載のノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノード・アクティビティ状況に基づいてワイヤレス臨時（ａｄ−ｈｏｃ）ネットワーク内のノード通信を管理するためのシステムおよび方法に関する。詳細には、本発明は、ネットワーク内の通信要件を検出し、条件が許す場合にノードを非アクティブ状態にするためのシステムおよび方法に関する。通信要件の増大の検出は、ノードを様々なアクティビティ・ステージに配置し、ネットワーク内のノード・アクティビティ・レベルに基づいてネットワーク通信経路を変更するために使用する。
【背景技術】
【０００２】
近年、従来のインフラストラクチャの対象範囲を超える複数モバイル・デバイス通信の必要性に対処するために、「臨時（ａｄ−ｈｏｃ）」ネットワークとして知られる、ある種のモバイル通信ネットワークが開発されている。この種のネットワークでは、各ユーザ端末（以下「モバイル・ノード」）は、ネットワーク内の他のモバイル・ノード用の基地局またはルータとして動作することができ、したがって、複数基地局からなる固定インフラストラクチャの必要性が解消される。したがって、ソース・モバイル・ノードから宛先モバイル・ノードに送信されるデータ・パケットは概して、宛先ノードに到達する前にいくつかの中間モバイル・ノードを通って経路指定される。
【０００３】
従来の臨時ネットワーク内のようにモバイル・ノードが相互に通信できるようにすることに加え、さらにモバイル・ノードが固定ネットワークにアクセスし、公衆交換電話網（ＰＳＴＮ）およびインターネット上のものなどの他のタイプのユーザ端末と通信できるようにする、より高度な臨時ネットワークも開発されている。このような高機能タイプの臨時ネットワークの詳細については、２００１年６月２９日に出願され、「Ａｄ  Ｈｏｃ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ａｃｃｅｓｓ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅｄ  ｔｏ  ｔｈｅ  ＰＳＴＮ  ａｎｄ  Ｃｅｌｌｕｌａｒ  Ｎｅｔｗｏｒｋｓ」という発明の名称の米国特許出願第０９／８９７７９０号、２００１年３月２２日に出願され、「Ｔｉｍｅ  Ｄｉｖｉｓｉｏｎ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  ａｎ  Ａｄ−Ｈｏｃ，  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｒａｄｉｏ  Ｎｅｔｗｏｒｋ  Ｈａｖｉｎｇ  Ｃｏｏｒｄｉｎａｔｉｎｇ  Ｃｈａｎｎｅｌ  Ａｃｃｅｓｓ  ｔｏ  Ｓｈａｒｅｄ  Ｐａｒａｌｌｅｌ  Ｄａｔａ  Ｃｈａｎｎｅｌｓ  ｗｉｔｈ  Ｓｅｐａｒａｔｅ  Ｒｅｓｅｒｖａｔｉｏｎ  Ｃｈａｎｎｅｌ」という発明の名称の米国特許出願第０９／８１５１５７号、および２００１年３月２２日に出願され、「Ｐｒｉｏｒｉｔｉｚｅｄ−Ｒｏｕｔｉｎｇ  ｆｏｒ  ａｎ  Ａｄ−Ｈｏｃ，  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ，  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ａｃｃｅｓｓ  Ｓｙｓｔｅｍ」という発明の名称の米国特許出願第０９／８１５１６４号に記載されており、各出願の内容全体は参照により本明細書に組み込まれる。
【０００４】
このような臨時ネットワークでは、データ・フローはノードからノードへのものであり、最適経路選択を大いに当てにしている。伝送電力消費量およびパイプライン遅延などの要因は、ネットワークを通る伝送経路を選択する際に重要な役割を果たす。たとえば、音声データなどの所与のサービス・クラスでは、伝送中のパイプライン遅延が最小限であることを必要とする。しかし、パイプライン遅延を最小限にすると、伝送電力レベルが増大する場合が多く、これはモバイル・ノードの限られた電源に過度に負担をかける可能性がある。モバイル・ノードの電力消費効率を改善するための手法の１つは、通信要件が許す通り、様々な非アクティビティ度になるようノードを配置することを含む。
【０００５】
たとえば、あるネットワーク内のノードがアクティブではない場合、そのノードは、送信できるパケット数が少ない休止状態になる可能性があり、したがって、その無線帯域幅消費量が削減され、そのバッテリおよびこれらのパケットを受信する他のノードのバッテリでの電力消費を大幅に低減して、ノード・バッテリの最大耐用年数を達成することができる。これは、特に、ノード・バッテリの寿命の長さが重要である遠隔センサ・ノードの配備を考慮する際に有用である。センサ・ノードは、上記のノード機能を実行できるノードであるが、たとえば、温度、湿度、風などの環境条件をモニターすることもできる。このようなセンサ・ノードまたはセンサは、ネットワーク機能を有する必要がある装置クラスに属すが、ネットワークを散発的に使用し、潜在的に長期間の間、非アクティブになる。
【０００６】
当業者であれば分かるように、ネットワーク内のノードは、ネットワーク内のノードからノードへ情報パケットを送信し、受信し、経路指定するだけでなく、ネットワークを越えて位置するノードとの間でもパケットを送信し、受信し、経路指定する。臨時ネットワーク内のノードはこれらのパケットを生成するが、これはデータ・パケットまたは制御パケットとして分類することができる。データ・パケットと制御パケットとの区別により、ノードが所与の時点でアクティブであるかどうかに基づいて、ネットワーク内のノード関与を変更することができる。すなわち、データ・パケットは、ユーザによって生成されたパケットを含み、ストリーミング・ビデオ・アプリケーションの使用など、何らかのアクティビティを実行する。制御パケットは、他のノードを発見し、経路指定テーブルを構築し、ノード間でネットワーク・トポロジを共用するために作成される。したがって、ネットワーク・ノード間のように、より高い頻度で制御パケットを送受信すると、結果的に、ネットワークについてより正確で完全な知識が得られる。
【０００７】
しかし、頻繁なパケット伝送の問題は、パケット伝送で使用するノード送信機は概して、ノードのコンポーネントの中で最も電力消費量の大きいコンポーネントであることである。したがって、メッセージを送信しないことによってノード送信機の使用を回避できる事例ごとに、著しい電力消費量の節約を達成することができる。しかし、データ・パケットはユーザによって生成され、何らかのアクティビティを実行するので、制御パケットと比べて、データ・パケットは、同じ程度まで回避することはできない。しかし、ノード更新の必要性が小さい状況では、制御パケット伝送を低減することができる。
【０００８】
臨時ネットワークは概して、他のノードを発見し、経路指定テーブルを構築し、ノード間でネットワーク・トポロジを共用するためのメカニズムを必要とする。これは、概してオーバヘッド・メッセージングとして記述されるメッセージングを使用して達成され、制御パケット伝送を含むことができる。たとえば、制御パケット伝送は、ノード更新が必要な程度まで必要とされる。したがって、ネットワーク・ノード内での送信機の使用を低減するための手法の１つは、頻繁なノード更新の必要性を低減することである。多くの臨時ネットワークは概して、高い変化率と高いトラフィック需要という仮定に基づいて、１〜５秒程度の更新率を有する。ノード更新を低減するための手法の１つは、ネットワーク・ノードが同期化され、情報を共用するためにすべてが同時に「ウェイクアップ」するネットワークを設計することであった。しかし、これは、必ずしもノード・アクティビティの低減により電力節約を達成する効果的な技法であるわけではない。たとえば、このような配置では、「ウェイクアップ」時間までノードはデータを転送できないので、結果的に、頻繁な更新遅延が発生する可能性がある。さらに、ネットワーク・ノードは必ずしも相互に容易に同期化できるわけではない。「ウェイクアップ」時にデータ更新を実現することは、ノードが任意にしかも規則正しくネットワークに加わりネットワークを離れるようなモバイル臨時ネットワークでは特に難しいことである。
【０００９】
したがって、臨時ネットワーク内の制御パケット伝送の頻度を低減し、それにより、モバイル・ノードでの限られた電源の需要を低減するためのシステムおよび方法の必要性が存在する。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の一目的は、ネットワーク通信要件に基づいて臨時ネットワーク内のノードを様々な非アクティビティ・ステージに配置するためのシステムおよび方法を提供することにある。
【００１１】
本発明の他の目的は、ノード・アクティビティ・レベルに基づいて臨時ネットワーク内のノードに必要なデータ更新を計算するためのシステムおよび方法を提供することにある。
【００１２】
本発明のさらに他の目的は、ノード・アクティビティ・レベルに基づいて伝送経路を計算することにある。
【課題を解決するための手段】
【００１３】
上記その他の目的は、通信要件を決定し、臨時ネットワーク内のノードを様々な非アクティビティ・ステージに配置するためのシステムおよび方法を提供することにより、実質的に達成される。このシステムおよび方法は、ノード・アクティビティ・レベルの変化を検出し、検出された変化に基づいて、更新伝送および経路選択などの動作を変更するためのアルゴリズムを提供する。特に、このアルゴリズムは、ノードが到達可能な新しい宛先の数、ノードが実現可能な経路変更の数、ノードからの経路のうち、その長さが変化した経路の数、ノードがもはや到達不能な宛先の数などの要因に基づいて、各経路指定更新間隔でのノードのアクティビティ・レベルを決定する。次に、ノードは、このアクティビティ・レベルの増加または減少に基づいて、隣接ノードとその経路指定情報を交換する際の率を増加または減少することができる。
【００１４】
本発明の上記その他の目的、利点、および新規な特徴は、添付図面に関連して読んだときに以下の詳細な説明から容易に理解されるだろう。
【実施例】
【００１５】
図１は、本発明の一実施形態を使用する臨時パケット交換ワイヤレス通信ネットワーク１００の一例を示すブロック図である。具体的には、ネットワーク１００は、複数のモバイル・ワイヤレス・ユーザ端末１０２−１〜１０２−ｎ（一般にノード１０２またはモバイル・ノード１０２という）を含み、ノード１０２が固定ネットワーク１０４にアクセスできるようにするために、複数のアクセス・ポイント１０６−１、１０６−２、・・・１０６−ｎ（一般にノード１０６またはアクセス・ポイント１０６という）を有する固定ネットワーク１０４を含むことができるが、これを含む必要があるわけではない。固定ネットワーク１０４は、ネットワーク・ノードがその他の臨時ネットワーク、公衆交換電話網（ＰＳＴＮ）、およびインターネットなどのその他のネットワークにアクセスできるようにするために、たとえば、コア・ローカル・アクセス・ネットワーク（ＬＡＮ）と、複数のサーバおよびゲートウェイ・ルータとを含むことができる。ネットワーク１００は、他のノード１０２、１０６、または１０７との間でデータ・パケットを経路指定するために、複数の固定ルータ１０７−１〜１０７−ｎ（一般にノード１０７または固定ルータ１０７という）をさらに含むことができる。この説明のため、前述のノードはひとまとめにして「ノード１０２、１０６、および１０７」または単純に「ノード」と呼ぶことができることは留意すべきである。
【００１６】
ネットワーク１００が使用される適用例または環境のタイプに応じて、モバイル・ノード１０２ならびに固定ルータ１０７はセンサ・ノードとして構成することができる。センサ・ノードまたはセンサは、ネットワーク機能を有する必要がある装置クラスに属すが、ネットワークを散発的に使用し、潜在的に長期間の間、非アクティブになる。センサ・ノードは、諸条件、たとえば、温度、湿度、風速などの環境データをモニターすることができ、その情報を中央集合部に提供することができる。概して、そのノード１０２および／または１０７がセンサ・ノードとして構成されるネットワーク１００は、上記の固定ネットワーク１０４およびＩＡＰ１０６を含まないであろう。センサ・ネットワークは従来のネットワークと同じ動作を実行することになるが、センサ・ネットワークにより、最小更新時間など、わずかに異なる動作上のチューニングが可能になる。さらに、ネットワーク１００は概して、正規のモバイル・ノード１０２および正規の固定ルータ１０７と、センサとして構成されるモバイル・ノード１０２および固定ルータ１０７とを混合しないであろう。換言すれば、ネットワーク１００は概して、センサタイプのノードまたは正規のノードおよびルータ（おそらくＩＡＰ１０６）のいずれか一方を含むことになるが、両方を含むことはないであろう。しかし、本発明の範囲はこの制約事項に制限されず、センサ・ノードと「正規」のノードが共通ネットワーク１００内で使用される情況が発生する可能性がある。
【００１７】
当業者であれば分かるように、参照により本明細書に組み込まれ、Ｍａｙｏｒに交付された米国特許第５９４３３２２号ならびに上記で参照した米国特許出願第０９／８９７７９０号、第０９／８１５１５７号、および第０９／８１５１６４号に記載されているように、ノード１０２、１０６、および１０７は、直接、またはノード間で送信されるパケット用の１つまたは複数のルータとして動作する１つまたは複数の他のノード１０２、１０６、または１０７を介して、相互に通信することができる。
【００１８】
図２に示す通り、各ノード１０２、１０６、および１０７は、アンテナ１１０に結合され、コントローラ１１２の制御下でノード１０２、１０６、または１０７との間でパケット化信号などの信号を送受信可能なトランシーバ１０８を含む。パケット化データ信号は、たとえば、ノード更新情報を含む、音声、データまたはマルチメディア情報、およびパケット化制御信号を含むことができる。
【００１９】
各ノード１０２、１０６、および１０７は、とりわけ、それ自体およびネットワーク１００内の他のノードに関する経路指定情報を保管可能なランダム・アクセス・メモリ（ＲＡＭ）などのメモリ１１４をさらに含む。ノード１０２、１０６、および１０７は、定期的に、たとえば、新しいノードがネットワーク１００に入ったときまたはネットワーク１００内の既存のノードが移動したときに、ブロードキャスト・メカニズムを介して相互に、経路指定公示または経路指定テーブル情報というそれぞれの経路指定情報を交換する。
【００２０】
図２にさらに示す通り、所与のノード、特にモバイル・ノード１０２は、ノートブック・コンピュータ端末、移動電話ユニット、モバイル・データ・ユニット、または任意のその他の適切な装置などの任意の数の装置から構成することができるホスト１１６を含むことができる。各ノード１０２、１０６、および１０７は、インターネット・プロトコル（ＩＰ）およびアドレス解決プロトコル（ＡＲＰ）を実行するための適切なハードウェアおよびソフトウェアも含み、その目的は当業者であれば容易に理解することができる。伝送制御プロトコル（ＴＣＰ）およびユーザ・データグラム・プロトコル（ＵＤＰ）を実行するための適切なハードウェアおよびソフトウェアも含めることができる。
【００２１】
図１に示す通り、ネットワーク１００内のノード１０２、１０６、および１０７の配備は、高モバイル性デバイスから完全静止型デバイスに及ぶ混合特性のものであり、それぞれが潜在的に広範囲のノード・アクティビティ・プロファイルを有する。図１のノード１０２、１０６、または１０７のアクティビティは２つの成分を有する。第１の成分は、ノードが他のノードおよび／または他のネットワークと通信する必要があるときに使用する周波数によって定義される。ノード・アクティビティの第２の成分は、ネットワーク内のノードの位置が変化する際の率によって定義される。この変化率、または換言すれば、ノードのモビリティを測定しモニターすることができる方法の一例は、２００１年１１月１３日に出願され、「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｄｅｔｅｒｍｉｎｉｎｇ  ｔｈｅ  Ｍｅａｓｕｒｅ  ｏｆ  Ｍｏｂｉｌｉｔｙ  ｏｆ  ａ  Ｓｕｂｓｃｒｉｂｅｒ  Ｄｅｖｉｃｅ  ｉｎ  ａｎ  Ａｄ−Ｈｏｃ  Ｗｉｒｅｌｅｓｓ  Ｎｅｔｗｏｒｋ  ｗｉｔｈ  Ｆｉｘｅｄ  Ｗｉｒｅｌｅｓｓ  Ｒｏｕｔｅｒｓ  ａｎｄ  Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ  （ＷＡＮ）  Ａｃｃｅｓｓ  Ｐｏｉｎｔｓ」という発明の名称の米国特許出願第０９／９８７１０２号に記載されており、その出願の内容全体は参照により本明細書に組み込まれる。ノードは、静止して無音である（すなわち、通信していない）場合に非アクティブであるが、ノードが移動し始めるかまたは何かと通信する必要がある場合に、よりアクティブになる。以下に記載する本発明の実施形態は、ノード１０２、１０６、または１０７が非アクティブからアクティブへならびにその逆に変化する際の変化率を管理するための方法およびシステムを提示する。
【００２２】
現在まで、ネットワーク・アーキテクチャの配備は、広域で高モバイル性の適用例に関するものであった。しかし、モバイル臨時ネットワークが適切であるが、ノード・アクティビティ挙動の低減を示すことになるシナリオが存在する。ネットワーク・ノードのアクティビティに関する知識を使用すると、ノード間で交換される定期的制御メッセージで配布する必要がある情報の量を大幅に低減することができる。非アクティブ・ノード１０２、１０６、または１０７は、その制御パケット情報交換の頻度を低減することができる。非アクティブ状態である間、非アクティブ・ノードは使用されず、いかなる外部エンティティもそれと接触しようと試みないという事実により、ネットワーク１００のその他のノードは、他のノードの場合のように頻繁にこのような非アクティブ・ノードに関する情報を共用することを要求されないであろう。
【００２３】
ノードの移動またはノード通信アクティビティのいずれかにより、ノード１０２、１０６、または１０７がアクティブになると、たとえば、アクティブになるノードのコントローラ１１２は、そのノードと外部エンティティとの間で情報を効果的に経路指定するために必要な、他の隣接ノード１０２、１０６、または１０７など、ネットワーク１００の重要メンバーに対し、そのノードの状態をアクティブにするセットアップ制御メッセージ交換を実行することになる。その時点で、新たにアクティブになったノードの制御情報は、そのノードに対してローカルのネットワーク１００の一部（すなわち、ノード・ブロードキャスト範囲内にある隣接ノード）により、より普及したものになり、その結果、効果的かつ信頼できるデータ・ペイロードの送達を支援することになる。
【００２４】
概して、ネットワーク１００のノード１０２、１０６、および１０７が非アクティブであると、更新率は３０秒以上の低速になる可能性があり、これは受動リフレッシュ率と呼ぶことができる。ノードが単に基本的接続性を維持しているだけである間は、更新情報の経過時間は重大ではない。しかし、ノード１０２、１０６、または１０７が情報を送受信する必要がある場合、ノードはより正確なネットワーク情報を必要とし、したがって、更新率が増加する。ネットワーク１００の各ノードが受動聴取モードにある場合、それぞれは、ネットワーク・トラフィックの需要が発生するまで、日常的に経路指定およびネットワーク更新メッセージを低速で受信し、更新メッセージを同じ低速で送信する。
【００２５】
ノード１０２、１０６、または１０７がデータを送信するための要求を感知すると、そのノードはその更新率を（たとえば、受動リフレッシュ率の２倍に等しい新しい率に）増加する。そのノードまたは端末がソース、シンク、または中間ルータとして情報の経路指定に積極的に関わっている場合、その更新率をさらに（たとえば、受動リフレッシュ率の４倍に等しい新しい率に）増加することになる。トラフィックが沈静化すると、ノードは上昇した更新率をゆっくり低減して受動率まで戻すことになる。
【００２６】
図１のネットワーク１００では、ノードは電源投入後に予約チャネル上のアクティビティがないかどうか聴取して、ネットワークに参加しているノードを発見する。ノードが予備ネットワーク・マップを構築すると、そのノードは、ネットワーク１００に積極的に参加し、ルーチン更新を送信する先駆者として、それ自体と、ネットワーク１００に関するそのビューを公示する。しかし、そのノードの近隣領域内のすべてのノード１０２、１０６、および１０７が現在、休止状態になっている可能性があることはあり得ることである。したがって、そのノードがネットワーク・トラフィックを確認しない場合でも、それは必ずしも近隣領域内の唯一のノードであるわけではない。したがって、そのノードはブロードキャスト・メッセージを送信して、ネットワーク１００内のスリープ中の隣接ノードをウェイクすることができるかどうかを確認しなければならない。
【００２７】
また、本発明の一実施形態によれば、様々なアクティビティ・レベルで動作するノード１０２、１０６、および１０７で使用されている「電源投入」アルゴリズムを使用して、経路指定テーブル更新間隔を決定することもできる。前に述べた通り、経路指定テーブルに対する更新は、モバイル・ノードの電力消費レベルに悪影響を及ぼす制御パケット伝送を必要とする。以下に述べる本発明の一実施形態では、必要な更新の頻度が決定され、更新間の最大間隔が計算される。更新間の最大間隔を使用すると、可能な最低数の伝送が達成される。
【００２８】
加えて、各ノード１０２、１０６、および１０７は、基本的接続性を維持し、ある程度まで他のノードと更新を継続的に交換する。ノードがアクティブである場合、より高い頻度で更新を受信することができる。ノードが非アクティブである場合、より低い頻度で更新を受信することができ、結果的に非アクティブ状態からアクティブ状態への遷移が発生する偏差について更新を絶えずモニターする。経路間隔は、経路指定テーブル内の項目の変化率とその経路指定位置に基づくものである。
【００２９】
各ノードの経路指定メトリックは、前の更新からの偏差の合計として、たとえば、そのコントローラ１１２によって計算することができる。以下の説明のため、経路指定メトリックが計算されるノードは、その隣接ノードと区別するために「対象ノード」と呼ぶことにする。偏差は以下のように計算される。
合計＝新しい宛先＋新しい次のホップ＋新しい経路指定長＋削除された宛先  （１）
【００３０】
式（１）の各項は整数値を有する。「新しい宛先」という変数はノードが到達可能な新しい宛先の数を表し、「新しい次のホップ」という変数は隣接経路指定テーブルの変更が組み込まれたときに発生する代替経路によって引き起こされる経路変更を表し、「新しい経路指定長」はノードが使用可能な経路のうち、その長さが変化した経路の数を表し、「削除された宛先」はノードがもはや到達不能な宛先の数を表す。式（１）によって生成される合計は、帯域幅使用状況、輻輳（ノードおよび近隣領域内の両方）、バッテリ・レベル、ネットワーク・フラグメント化（複数の代替経路と強く接続されているかまたは各経路が重要である箇所で弱く接続されている）などのその他の経路指定メトリックを含むように拡張することができる。
【００３１】
ある期間にわたって、各更新間隔で式（１）によって計算された合計により、一連の合計値が発生することは留意すべきである。時間に関してこれらの値をプロットすることにより、合計値の傾向の関数が作成される。このため、そのノードによる経路指定情報の交換率を増加または減少しなければならない程度は、その関数の導関数に基づいて決定することができる。
【００３２】
たとえば、対象ノードが静止したままであり、その隣接ノードがすべて静止したままである場合、上記の式（１）によって計算された合計の値はゼロになる。すなわち、複数の静止ノードからなるネットワークは、いかなる位置変化も発生しないので、「新しい宛先」、「新しい次のホップ」、「新しい経路指定長」、または「削除された宛先」を生成しない。対象ノードおよびその隣接ノードがいくつかの更新について一定のままである場合、経時的な合計値のプロットの関数は増加または減少しない。たとえば、複数の静的センサからなる配備された閉鎖ネットワーク内で予想されるような一定の経路指定テーブルはゼロの導関数をもたらすであろう。このため、任意の経路指定更新間隔で取られる関数（まっすぐな水平線である）の導関数はゼロになる。したがって、対象ノードによる経路指定情報の交換率の増加または減少は一切不要である。むしろ、ゼロの導関数が生成される場合、対象ノードのコントローラ１１２によって実行される経路指定アルゴリズムは、経路指定更新間の最大時間間隔の使用を指示し、その場合、時間間隔はネットワーク要件またはその他の設計要因に基づいて選択可能になる可能性がある。
【００３３】
これは、合計値が一定の期間にわたって所与の値のままになるときに、同様に該当する。たとえば、式（１）の変数の結果、いくつかの更新について５という値が得られると想定すると、この関数もその期間についてまっすぐな水平線になり、したがって、これらの更新間隔のいずれかで取られる関数の導関数はゼロになる。このため、ネットワーク内の対象ノードまたはその他のノードによって移動が発生する可能性があるとしても、その移動が、更新ごとに合計値が変化しないようなものである場合、対象ノードがその隣接ノードと経路指定情報を交換する際の率は変化しない。
【００３４】
これに対して、ネットワーク内の対象ノードおよび／またはその他のノードの移動が、更新ごとに合計値が変化するようなものである場合、これらの更新で取られる関数の導関数は更新ごとに変化することになる。たとえば、対象ノードおよび／またはその隣接ノードの移動によって、ある更新間隔で式（１）から所与の合計値が得られ、次の更新間隔でそれより大きい合計値が得られる場合、これらの間隔間でプロットされる関数は増加線になる。したがって、その関数の導関数は正の値になる。合計値が更新間隔ごとに増加し続ける場合、各間隔で取られる導関数は正の値になり、合計値の増加が更新間隔ごとにより大きくなる場合に増加する可能性がある。
【００３５】
したがって、合計の導関数が増加するにつれて、経路指定更新率を増加して、ネットワーク内のダイナミズムの増加に応答し、ネットワーク接続性を強制的に定常状態にしなければならない。すなわち、アルゴリズムの導関数が正になると、経路指定情報交換率は増加して、経路指定テーブルの変化に応答する。定常状態が達成されると、バッテリ電力を節約するために経路指定更新率をもう一度低減することができる。
【００３６】
これに対して、合計値が更新間隔ごとに減少する場合、これらの間隔間でプロットされる関数は減少線になる。したがって、これらの間隔のいずれかで取られる導関数は負になる。導関数が負になると、経路指定テーブルの変化がないためにもはや不要になっている帯域幅を回復するために経路指定情報交換率を減速する。
【００３７】
瞬間的な正の変化にゼロの導関数が続く場合、このアルゴリズムによって交換率の振動が発生しないことを保証するために、交換率を徐々に減速する。振動を発生しそうな瞬間的な変化の一例は新しいノードの起動である。この場合、それを見つけようとする可能性のある宛先に新しいノードの局所性情報が伝播されることを保証するために、最小率より大きい率で経路指定情報が交換される。漸進的な減速を行わないと、この新しいノードを公示するノードにより、ネットワークが最適経路に収束するときに増大する可能性のある新しい次のホップおよび経路指定長に対する急速反応が発生する可能性がある。
【００３８】
追加として、アクティブ・ノードと非アクティブ・ノードとの間で経路が選択される場合、ルータとして使用するための候補としては非アクティブ・ノードの方が良好である。アクティブ・ノードを使用すると、そのノードはそれ自体のデータならびにアクティブ・ノードをルータとして使用するノード用のデータを送信するので、そのノードがルータとして選択された場合にアクティブ・ノードのスループットがさらに減少することになるであろう。この知識は、これらの情報に基づく決定を可能にする経路指定メトリックとして定期的な制御トラフィックにそれを含めることにより、他のノードに伝播される。
【００３９】
本発明のもう１つの利点は、他のノードの方がアクティブ・ノードを伴う動作を実行する可能性が高いと想定して、ネットワーク１００内のアクティブ・ノードの優先順位を上げる能力であり、したがって、アクティブ・ノードを伴うデータの優先順位を上げることができ、その結果、ノードがデータを処理する際の全体的な効率を高めることができる。この優先順位の上昇により、ネットワーク自体もより広い領域に対するアクティブ・ノードの制御情報の配布を増加し、ネットワークを介してより多くの経路指定オプションをデータ・ストリームに与え、そのデータ・ストリームの頑強性および信頼性を高めることになるだろう。
【００４０】
本発明のいくつかの例示的な実施形態についてのみ上記で詳細に説明したが、当業者であれば、本発明の新規な教示および利点を著しく逸脱せずに例示的な実施形態について多くの変更が可能であることが容易に分かるであろう。したがって、このような変更はいずれも、本発明の範囲内に含まれるものである。
【図面の簡単な説明】
【００４１】
【図１】本発明の一実施形態を使用する複数のノードを含む臨時ワイヤレス通信ネットワークの一例のブロック図である。
【図２】図１に示すワイヤレス・ノードの一例のブロック図である。
【図１】
2005525061.tif 000003
【図２】
2005525061.tif 000004
【国際調査報告】
2005525061.tif 000005
2005525061.tif 000006