(57)【要約】アドホック無線通信ネットワークのノードにおけるルーティングテーブル更新間隔を調整する方法が提供される。本方法は、ノードによりネットワーク内のローカル変更が検出された（１０４）場合に、ルーティングテーブル更新間隔を第１定数値で割ることによってルーティングテーブル更新間隔を減らす（１０６）工程を有する。ノードによりネットワーク内のリモート変更が検出された（１０４）場合に、ルーティングテーブル更新間隔の逆数であるルーティングテーブル交換レートが第２定数値により増やされる（１１０）。ノードによりネットワーク変更が検出されなかった（１０２）場合に、第２定数値によりルーティングテーブル交換レートが減らされる（１０８）。
2011501921.tif 000002
【特許請求の範囲】
【請求項１】
アドホック無線通信ネットワークのノードにおけるルーティングテーブル更新間隔を調整する方法であって、
前記ノードにより前記ネットワーク内のローカル変更が検出された（１０４）場合に、前記ルーティングテーブル更新間隔を第１定数値で割ることによって前記ルーティングテーブル更新間隔を減らす（１０６）工程と、
前記ノードにより前記ネットワーク内のリモート変更が検出された（１０４）場合に、前記ルーティングテーブル更新間隔の逆数であるルーティングテーブル交換レートを第２定数値により増やす（１１０）工程と、
前記ノードによりネットワーク変更が検出されなかった（１０２）場合に、前記第２定数値により前記ルーティングテーブル交換レートを減らす（１０８）工程と
を有することを特徴とする方法。
【請求項２】
ａ）ローカル変更イベントに関する通知を受信した（２０８）際にローカル変更イベント用カウンタを増やす（２１０）工程と、
ｂ）リモート変更イベントに関する通知を受信した（２１２）際にリモート変更イベント用カウンタを増やす（２１４）工程と、
ｃ）前記ローカル変更イベント用カウンタが以前のルーティングテーブル更新サイクルに比べて値が増えており（３０９）且つ前記ローカル変更イベント用カウンタの変更速度が増加中である（３１０）場合に、前記ルーティングテーブル更新間隔を前記第１定数値で割ることによって前記ルーティングテーブル更新間隔を減らす（３１２）工程と、
ｄ）前記ローカル変更イベント用カウンタが以前のルーティングテーブル更新サイクルに比べて値が増えておらず且つ前記リモート変更イベント用カウンタの値が前記以前のサイクルの値に比べて増えている（３１４）場合に、前記ルーティングテーブル交換レートを前記第２定数値により増やす（３１６）工程と、
ｅ）前記ローカル変更イベント用カウンタの値が以前のルーティングテーブル更新サイクルの値に比べて増えておらず且つ前記リモート変更イベント用カウンタの値が前記以前のサイクルの値に比べて増えていない場合に、前記ルーティングテーブル交換レートを前記第２定数値により減らす（３１８）工程と
を有することを特徴とする請求項１に記載の方法。
【請求項３】
以前のルーティングテーブル更新サイクルの間に経路の何れかが失効され（３０４）且つ前記リモート変更イベント用カウンタの増加が第２所定値よりも小さい場合に、第１所定値により経路失効間隔を増やす（３０８）工程をさらに有することを特徴とする請求項２に記載の方法。
【請求項４】
前記ローカル変更イベント用カウンタは、リンク品質変更又はリンク切断若しくはリンク確立に関する通知をリンク・レイヤから受信すると増やされる（２１０）ことを特徴とする請求項２又は３に記載の方法。
【請求項５】
前記リモート変更イベント用カウンタは、経路失効又はルーティングテーブル内の変更に関する通知を受信すると増やされる（２１４）ことを特徴とする請求項２乃至４の何れか１項に記載の方法。
【請求項６】
前記第１所定値は前記ルーティングテーブル更新間隔に等しいことを特徴とする請求項３に記載の方法。
【請求項７】
前記方法は前記ネットワーク内の個別のノードにより独立して実行されることを特徴とする請求項１乃至６の何れか１項に記載の方法。
【請求項８】
前記更新において前記ルーティングテーブルのすべてのレコードが更新されることを特徴とする請求項１乃至７の何れか１項に記載の方法。
【請求項９】
複数のノードを含むアドホック無線通信ネットワークのためのノード（５００）であって、
前記ネットワークからのイベント通知を受信するためのイベント・モニタ（５０２）と、ローカル変更イベント用カウンタ（５０４）と、リモート変更イベント用カウンタ（５０６）とを備え、
前記イベント・モニタ（５０２）は、ローカル変更に関する通知を受信すると前記ローカル変更イベント用カウンタ（５０４）を増やすように構成されるとともに、リモート変更に関する通知を受信すると前記リモート変更イベント用カウンタ（５０６）を増やすように構成され、
前記ノードは、ルーティングテーブル（５１２）とコントローラ（５１０）とをさらに備え、
前記コントローラ（５１０）は、
前記ローカル変更イベント用カウンタ（５０４）が以前のルーティングテーブル更新サイクルに比べて値が増えており且つ前記ローカル変更イベント用カウンタ（５０４）の変更速度が増加中である場合に、ルーティングテーブル更新間隔を第１定数値で割ることによって前記ルーティングテーブル更新間隔を減らし、
前記ローカル変更イベント用カウンタ（５０４）が以前のルーティングテーブル更新サイクルに比べて値が増えておらず且つ前記リモート変更イベント用カウンタ（５０６）の値が前記以前のサイクルの値に比べて増えている場合に、ルーティングテーブル交換レートを第２定数値により増やし、
前記両カウンタの値が前記以前のサイクルの値に比べて増えていない場合に、前記ルーティングテーブル交換レートを前記第２定数値により減らす
ように構成されることを特徴とするノード（５００）。
【請求項１０】
経路失効用カウンタ（５０８）をさらに備え、
前記イベント・モニタ（５０２）は経路失効に関する通知を受信すると前記経路失効用カウンタ（５０８）を増やすように構成され、
前記コントローラは以前のルーティングテーブル更新サイクルの間に経路の何れかが失効され且つ前記リモート変更イベント用カウンタの増加が第２所定値よりも小さい場合に、第１所定値により経路失効間隔を増やすように構成される
ことを特徴とする請求項９に記載のノード。
【請求項１１】
前記イベント・モニタ（５０２）は、リンク・レイヤからのリンク品質変更又はリンク切断若しくはリンク確立に関する通知の受信に応答して、前記ローカル変更イベント用カウンタ（５０４）を増やすように構成されることを特徴とする請求項９又は１０に記載のノード。
【請求項１２】
前記イベント・モニタ（５０２）は、経路失効又はルーティングテーブル内の変更に関する通知の受信に応答して前記リモート変更イベント（５０６）用カウンタを増やすように構成されることを特徴とする請求項９乃至１１の何れか１項に記載のノード。
【請求項１３】
前記第１所定値は前記ルーティングテーブル更新間隔に等しいことを特徴とする請求項１０に記載のノード。
【請求項１４】
複数のノード（５００−６１０）を備えるアドホック無線通信ネットワーク（６００）であって、前記複数のノードの少なくとも一部は請求項９乃至１３の何れか１項に記載のノードであることを特徴とするアドホック無線通信ネットワーク（６００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にアドホック無線通信ネットワークに関し、特にこのようなアドホック無線端末ネットワークにおいてノードのルーティングテーブル更新の時間間隔を調整する方法に関する。
【背景技術】
【０００２】
無線メッシュ・ネットワーク（ＷＭＮ）は動的自己組織化、自己構成及び自己修復を特徴とするマルチホップ・インフラレス・ネットワークである。これらの要因はＷＭＮが非常に多様な環境において高速で信頼できコスト効率的なネットワーク配置をサポートし、固定又は移動体のユーザへのよりよいカバレッジ及び容量を提供することを可能にする。これに対応して、ＷＭＮは軍隊、災害復旧、商業及び私的な設定における幅広いアプリケーションのホストを務めうる。一つの典型的な例はエリクソン・レスポンス・プログラムであり、可搬型セルラ・ネットワークのロバスト性と迅速な配置とを強化するためにＷＭＮインフラが用いられる。この解決策は災害救助及びその他のミッション・クリティカルなシナリオにおいて効率的且つロバストなサービスを提供する。
【０００３】
宛先シーケンス距離ベクトル型ルーティングプロトコル（ＤＳＤＶ）は古典的なベルマン‐フォード・ルーティングメカニズムに基づいたテーブル駆動型のプロアクティブなルーティングアルゴリズムである。ネットワーク内の各ノードは距離ベクトル即ちネットワーク内のすべての取り得る宛先へのホップ数と、対応する次ホップのノードとを記憶するルーティングテーブルを維持する。経路変更の発生回数に依存して、ＤＳＤＶノードは周期的に又はトリガによってルーティングテーブルを隣接ノードへ送信する。
【０００４】
既存のＤＳＤＶプロトコルには二つの問題があり、これらは遅い収束速度と経路チャーン（churn）とを含む。
【０００５】
ＤＳＤＶでは、リンクの変更は隣接ノード間でルーティングテーブルを交換することによってホップ単位に伝播される。これは制御トラヒックのオーバヘッド量を大幅に減少する。しかしながら、このメカニズムに関する一つの主な懸念点はリンク変更の存在におけるその遅い収束である。ｒをルーティングテーブル更新間隔とし、ｄをリモート・ノードへの距離（即ちホップ数）であるとする。ｄホップの距離にあるリモート・ノードまでリンク変更が伝播されるまで最大でｒ×ｄの期間を要する。
【０００６】
メッシュ・ネットワークの中央管理が欠けているため、メッシュ・ネットワークにおけるリンクの切断又はリンク品質の変更は稀なイベントというわけではない。このような環境において、距離ベクトル型ルーティングはリンク状態型ルーティングよりも遥かに遅く収束し、場合によってはネットワークの安定性を劣化させうる。
【０００７】
ＤＳＤＶは古くなった（stale）経路を削除する際にタイムアウト・メカニズムを用いる。期間内に受信された経路更新が存在しない場合に経路エントリが削除される。ネットワーク・サイズの増加につれて、ネットワーク内の各ノードへ、特にエッジ・ノードへ経路更新が伝播されるまでより長くかかる。従って、すべてのネットワーク・ノードが固定であるとしても、エッジ・ノードのルーティングテーブルは、遠いノードへ経路が構築されるためにゆっくりと「チャーン（churn）」するだろう。次いで、ルーティングテーブルの更新が何も到着しないままタイムアウトする。よって、有効な経路エントリが誤って削除されるかもしれない。
【０００８】
ルーティングテーブルのより短い更新間隔は、ノードがいかなるネットワーク変更により早く適合することを可能にする。従って、遅い収束の問題に取り組む一つの共通のアプローチは、ルーティングテーブルのより短い更新間隔を用いることであり、これは収束待ち時間を低減しうる。
【０００９】
このアプローチには二つの主な問題がある。より短いトポロジ更新間隔は、より多いトポロジ更新頻度を意味する。従って、このアプローチは大きすぎる制御オーバヘッドをもたらす。別の問題は、短い間隔が経路チャーンの問題をいっそう悪くすることである。すべてではないノードが移動状態又は変更状態である比較的安定なネットワークにおいて、より短い間隔は安定ノードにおける経路失効（route expiration）と誤削除とをもたらしうるだろう。
【００１０】
まとめると、ＤＳＤＶにおいてルーティングテーブル更新間隔を減らすことは経路収束速度を改善するものの、本改善は過度な制御オーバヘッド及び経路チャーンを犠牲にする。
【００１１】
適応距離ベクトル（ＡＤＶ）型ルーティングアルゴリズムと呼ばれる代替の既知の解決策では、トポロジ更新の頻度がネットワーク状況に従って調整される。ＤＳＤＶと比較すると、ＡＤＶはいくつかの改善点を有する。ＡＤＶは隣接ノード間で経路更新を交換するが、アクティブ・ノードの経路エントリだけが広告され、これは経路更新メッセージのサイズを減らす。ＡＤＶにおいて、経路更新はオンデマンド方式でトリガされる。トリガ要求は隣接ノードからのものである。隣接ノードが配送するデータ・パケットを有する場合又は隣接ノードがリンク変更を被る場合に経路更新がトリガされる。
【００１２】
しかしながら、ＡＤＶもいくつかの問題を有する。ネットワーク・イベントによりトリガされるため、経路更新の頻度はノード移動で急激に増加するかも知れず、ＤＳＤＶにおける周期的更新よりも大きな制御オーバヘッドを生じさせる。さらに、ＡＤＶを用いることによって、有効経路を見つけるのに長い時間がかかるかもしれない。なぜなら、一部のトポロジだけが維持されるからである。最後に、ＡＤＶは経路チャーンの問題を解決せず、経路エントリはなおも誤って削除されるかもしれない。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上述の不都合の少なくとも一部を取り除き、アドホック無線通信ネットワークのノードで用いられるルーティングテーブル更新間隔を調整する改善された方法を提供することが本発明の目的である。
【００１４】
従って、本発明は、上述の一つ以上の不都合を単独で又は任意の組み合わせで好適には軽減し、緩和し、又は排除しようとする。
【課題を解決するための手段】
【００１５】
本発明の第１の側面によれば、アドホック無線通信ネットワークのノードにおけるルーティングテーブル更新間隔を調整する方法が提供される。本方法は、前記ノードにより前記ネットワーク内のローカル変更が検出された場合に、前記ルーティングテーブル更新間隔を第１定数値で割ることによって前記ルーティングテーブル更新間隔を減らす工程を有する。前記ノードにより前記ネットワーク内のリモート変更が検出された場合に、前記ルーティングテーブル更新間隔の逆数であるルーティングテーブル交換レートが第２定数値により増やされる。さらに、前記ノードによりネットワーク変更が検出されなかった場合に、前記第２定数値により前記ルーティングテーブル交換レートが減らされる。
【００１６】
好適には、本方法は、ローカル変更イベントに関する通知を受信した際にローカル変更イベント用カウンタを増やす工程と、リモート変更イベントに関する通知を受信した際にリモート変更イベント用カウンタを増やす工程とを有する。前記ローカル変更イベント用カウンタが以前のルーティングテーブル更新サイクルに比べて値が増えており且つ前記ローカル変更イベント用カウンタの変更速度が増加中である（加速する）場合に、前記ルーティングテーブル更新間隔を前記第１定数値で割ることによって前記ルーティングテーブル更新間隔が減らされる。前記ローカル変更イベント用カウンタが以前のルーティングテーブル更新サイクルに比べて値が増えておらず且つ前記リモート変更イベント用カウンタの値が前記以前のサイクルの値に比べて増えている場合に、前記ルーティングテーブル交換レートが前記第２定数値により増やされる。前記ローカル変更イベント用カウンタの値が以前のルーティングテーブル更新サイクルに比べて増えておらず且つ前記リモート変更イベント用カウンタの値が前記以前のサイクルに比べて増えていない場合に、前記ルーティングテーブル交換レートが前記第２定数値により減らされる。
【００１７】
本発明はフル更新と呼ばれる一つの更新において前記ルーティングテーブルのすべてのレコードが更新されることと、前記更新において前記ルーティングテーブルの変更されたレコードのみが更新されることを意味するいわゆる部分更新である一部のみが更新されることの何れかを可能にする。
【００１８】
本発明の第２の側面によれば、複数のノードを含むアドホック無線通信ネットワークのためのノードが提供される。前記ノードは、前記ネットワークからのイベント通知を受信するためのイベント・モニタと、ローカル変更イベント用カウンタと、リモート変更イベント用カウンタとを備える。前記イベント・モニタは、ローカル変更に関する通知を受信すると前記ローカル変更イベント用カウンタを増やすように構成されるとともに、リモート変更に関する通知を受信すると前記リモート変更イベント用カウンタを増やすように構成される。前記ノードは、ルーティングテーブルとルーティングテーブル更新間隔を減らすように構成されたコントローラとをさらに備える。前記ローカル変更イベント用カウンタが以前のルーティングテーブル更新サイクルに比べて値が増えており且つ前記ローカル変更イベント用カウンタの変更速度が増加中である場合に、ルーティングテーブル更新間隔を第１定数値で割ることによって前記ルーティングテーブル更新間隔が減らされる。前記コントローラはまた、前記ローカル変更イベント用カウンタが以前のルーティングテーブル更新サイクルに比べて値が増えておらず且つ前記リモート変更イベント用カウンタの値が前記以前のサイクルの値に比べて増えているという二つの条件が満たされる場合に、ルーティングテーブル交換レートを第２定数値により増やすように構成される。前記コントローラはまた、前記両カウンタの値が前記以前のサイクルに比べて増えていない場合に、前記ルーティングテーブル交換レートを前記第２定数値により減らすように構成される。
【００１９】
イベント・モニタは内部状態レポジトリ（即ち隣接テーブル及びルーティングテーブル）を監視する経路デーモンから又はネットワーク内の他のノードからイベント通知を受信する。
【００２０】
本発明の第３の側面によれば、複数のノードを備えるアドホック無線通信ネットワークが提供され、前記ネットワークの複数のノードの少なくとも一部は本発明の第２の側面に従う。
【００２１】
本発明の更なる特徴は従属項において主張される。
【発明の効果】
【００２２】
本発明は以下の利点を有する。
【００２３】
改善された経路収束：リンクが切断されるといつでも、変更が自身の隣接ノードへ迅速に広告されるようにリンクのノードは経路更新間隔を積極的に減らす。ネットワーク内の他のノードは自身のルーティングテーブルの監視を通じてこの変更を検出し、経路更新間隔を段階的に減らし、このアプローチは交換される更新の全体的な数を減らし、イベントにより最も影響を受けるネットワークの領域において更新が迅速に伝播されることが保証される。
【００２４】
魚眼特性：ノードはリモート・ノードよりも自身の隣接ノードがより頻繁に更新されるように維持する（即ち魚眼特性）。これは、制御トラヒック・オーバヘッドの量を大幅に減らす。
【００２５】
経路チャーン低減：経路エントリが誤って削除されないように、安定ネットワークにおいて経路タイムアウト間隔は段階的に増やされる。
【図面の簡単な説明】
【００２６】
【図１】本発明の一つの実施形態におけるアドホック無線通信ネットワークのノードにおいてルーティングテーブル更新間隔を調整する方法を説明する図である。
【図２】本発明の一つの実施形態におけるアドホック無線通信ネットワークのノードにおいてカウンタ値を増やす方法を説明する図である。
【図３】本発明の一つの実施形態におけるアドホック無線通信ネットワークのノードにおいてルーティングテーブル更新間隔を調整する方法を説明する図である。
【図４】本発明の一つの実施形態におけるアドホック無線通信ネットワークのノードにおいてルーティングテーブル更新間隔を調整する方法を説明する擬似コードである。
【図５】本発明の一つの実施形態におけるアドホック無線通信ネットワークのためのノードを説明する図である。
【図６】本発明の一つの実施形態におけるアドホック無線通信ネットワークを説明する図である。
【発明を実施するための形態】
【００２７】
本発明は、図面とともに以下の詳細な説明からより十分に理解され認識されるだろう。
【００２８】
以下、本明細書で、ルーティングテーブル更新間隔という用語はネットワーク・ノードによるその隣接ノードとのルーティングテーブルの二つの連続した交換の間の期間を指す。
【００２９】
以下、本明細書で、経路失効間隔（route expiration interval）という用語は新たなエントリの登録又はルーティングテーブル内の既存のエントリのリフレッシュと、リフレッシュされなければ次に削除される当該経路エントリの失効との間の間隔を指す。
【００３０】
図１と図６とを参照しつつ、アドホック無線通信ネットワーク６００のノードにおいてルーティングテーブル更新間隔を調整する方法の実施形態が示される。この実施形態では、ルーティングテーブル更新間隔（ＲＴＵＩ）はネットワーク状況に基づいて自動的に調整される。このルーティングテーブルの更新において、すべてのレコードが更新される。これはフル更新を意味する。ネットワークにおけるローカル変更が当該ノードにより検出された（１０４）場合に、ルーティングテーブル更新間隔は積極的に減らされる（１０６）。このＲＴＵＩの積極的減少の目的は、ルーティングテーブルをできるだけ迅速に更新させることである。このような積極的減少を実現するために、間隔（ＲＴＵＩ）の長さは第１定数値αにより割られ、α＞１である。一つの実施形態ではα＝２であるが、その他のαの値も可能である。
【００３１】
代替の実施形態では、レコードの一部だけが更新されるいわゆる部分更新であり、これは当該更新において当該ルーティングテーブルの変更されたレコードだけが更新されることを意味する。
【００３２】
このようなアドホック無線通信ネットワーク内のノードの一つの例は無線基地局、ＷＩＦＩアクセスポイント、移動体電話又はＷＩＦＩベースのラップトップであり、これは距離ベクトル型ルーティングプロトコルを実行する。
【００３３】
ルーティングテーブル更新間隔はリモート変更の場合に段階的に減らされる。これは、ネットワークにおけるリモート変更が当該ノードにより検出された（１０４）場合に、ルーティングテーブル交換レートが第２定数値βによって増やされる（１１０）ことを意味する。ルーティングテーブル交換レートはルーティングテーブル更新間隔の逆数である。ｆがルーティングテーブル交換レートを表すとすると、ｆ＝１／ＲＴＵＩとなる。
【００３４】
一つの実施形態ではβ＝０．０２であるが、他の値のβも可能である。このルーティングテーブル更新間隔の段階的減少は変更広告を促進し、経路収束を強化する。
【００３５】
ルーティングテーブル更新間隔はリンク変更又は経路変更が存在しない場合に段階的に増やされる。これは、ネットワークにおける変更が当該ノードにより検出されない（１０２）場合にルーティングテーブル交換レートが係数βによって減らされる（１０８）ことを意味する。このＲＴＵＩの段階的増加（即ちルーティングテーブル交換レートの減少）はネットワークにおける不必要な制御トラヒックの低減に役立ち、（ノードがセットアップされ削除又は移動されない場合に）安定なネットワークにおいて生じる。
【００３６】
本質的に、本発明のアルゴリズムはフィードバック・ベースである。プロトコルの振る舞い（即ちパラメータ）は、大きすぎる制御オーバヘッドをもたらすことなく、よりよい性能を実現するために、経路利用可能性とパケットロス・レートとを含むネットワーク状況に従って調整される。
【００３７】
本発明は内部状態レポジトリ（即ち隣接テーブル及びルーティングテーブル）の監視を通じてネットワーク変更を判定する。そして、リンク変更レートが加速される場合に、ルーティングテーブル交換レートｆが係数α（α＞１）で乗算される。経路変更レートが増やされる場合に、ルーティングテーブル交換レートｆが係数βだけ増分される。それ以外の場合に、ルーティングテーブル変更レートｆは係数βだけ減分される。
【００３８】
図２〜図５を参照しつつ本発明のさらなる実施形態が詳細に説明される。
【００３９】
本発明の一つの実施形態において図５に示されるようにネットワーク・ノード５００はイベント・モニタ５０２、ローカル変更イベント用カウンタ５０４、リモート変更イベント用カウンタ５０６、コントローラ５１０及びルーティングテーブル５１２を備える。
【００４０】
イベント・モニタ５０２は、内部状態レポジトリ（即ち隣接テーブル及びルーティングテーブル）を監視する経路デーモンから又はネットワーク内の他のノードからイベント通知を受信する。イベント・モニタ５０２は、経路デーモンを用いて、以下のイベント即ちリンク・レイヤからの（パケット送信失敗を含む）フィードバックと経路ルックアップ失敗とをローカル変更イベントとして監視する。lo_chgをローカル変更イベント数即ちローカル変更イベント用カウンタ５０４の値であるとする。
【００４１】
〔リンク・レイヤからのフィードバック〕（パケット送信失敗を含む）リンク・レイヤからのフィードバックは、リンク品質、リンク切断及びリンク確立を含むリンクの状態に関する情報を含む。リンク・レイヤからの通知を受信すると、経路デーモンはlo_chgを１だけ増やす。
【００４２】
〔経路ルックアップ失敗〕宛先がＡではないデータ・パケットをノードＡが受信する場合に、ノードＡはそのパケットについての次ホップ・ノードを見つけるために自身のルーティングテーブルをルックアップする。経路が何も見つからない場合に、経路ルックアップ失敗が発生する。このような障害は、相異なるノードのルーティングテーブル間の経路不整合により発生する。宛先ノードについての経路ルックアップ失敗があると、当該イベント・モニタ５０２の経路デーモンはlo_chgを１だけ増やす。
【００４３】
イベント・モニタ５０２は、経路デーモンを用いて、ルーティングテーブル内の変更をリモート変更イベントとして監視する。
【００４４】
〔ルーティングテーブル内の変更〕隣接ノードからルーティングテーブルを受信する場合に、イベント・モニタ５０２は更新する前の自身のルーティングテーブルのコピーを記憶する。経路更新後に、経路デーモンは変更を見つけ出すために最新のルーティングテーブルと自身の古いものとを比較する。２種類の経路変更があり、（新たな隣接ノードが加わった場合に少なくとも新たな経路エントリがルーティングテーブルに追加され、既存の隣接ノードが去った場合に、この隣接ノードへの少なくとも一つの経路エントリが削除される）ローカルに発生する隣接変更に起因するか、リモートに生じるノード変更に起因するかの何れかである。
【００４５】
rt_chgをリモート変更の回数即ちリモート変更イベント用カウンタ５０６の値だとする。各リモート変更について、イベント・モニタ５０２の経路デーモンはrt_chgを１だけ増やす。
【００４６】
好適な実施形態では、さらに経路失効がリモート変更イベントとして監視される。経路失効には二つの原因がある。（ＤＳＤＶの経路チャーン問題で説明したように）経路がなおも有効かも知れないが、経路エントリの更新が失敗するかもしれない。他の可能性は、ノード移動又は失敗のせいで経路がもはや有効でないということである。本発明は、経路失効イベントを監視することによって経路チャーンの問題を解決する。コントローラ５１０はルーティングテーブル更新３０４の以前のサイクルの間に任意の経路が失効され、且つリモート変更用カウンタ５０６の増加が第２所定値３０６よりも小さい場合に、経路失効間隔を増やす。本発明の一つの実施形態では第２所定値はルーティングテーブル・サイズの１／３である。経路失効イベントの監視は経路失効カウンタ５０８を監視して経路失効の際にその値rt_expを１だけ増やすことによって実行される。イベント・モニタ５０２がこのような経路失効を検出すると、経路デーモンはrt_exp値を１だけ増やすための信号を送信する。
【００４７】
代替の実施形態では、カウンタへ適用される増分の他の値が用いられうる。
【００４８】
本発明はルーティングテーブル更新間隔を調整する。前述のように、ルーティングテーブル交換レートｆは、ｆ＝１／ＲＴＵＩである。
【００４９】
従って、ルーティングテーブル交換レートを増やすために、ルーティングテーブル更新間隔は減らされなければならない。本発明の一つの実施形態では、ＲＴＵＩの減少はこれを定数値α＝２で割ることによって実現される。
ＲＴＵＩnew＝ＲＴＵＩ／α
ここで、ＲＴＵＩはルーティングテーブル更新間隔の現在の値であり、ＲＴＵＩnewはローカル変更イベントの結果を受けたルーティングテーブル更新間隔の修正後の値であり、αはα＞１を満たす定数値である。一つの実施形態ではα＝２である。
【００５０】
本発明の一つの実施形態が擬似コードの形式で図４に示される。
【００５１】
（ａ）ローカル変更イベントに増加が存在あり（７行目参照）且つ変更イベントの速度が増える（即ち加速する、８行目参照）場合に、イベント・モニタ５０２の経路デーモンはルーティングテーブル更新間隔を積極的に減らす。すなわちこれをαで割る。一つの実施形態において、これは半分にする（９行目参照）ことを意味する。これは、ルーティングテーブル交換レートの急激な増加をもたらす。図４に示される実施形態では、（デフォルトの）最小ルーティングテーブル更新間隔は１ｓであり、これは設定可能である（１０行目参照）。
【００５２】
（ｂ）ローカル変更イベントに増加はないがルーティングテーブル変更に増加がある場合に、ルーティングテーブル交換レートは係数ベータだけ増分される（１３行目〜１５行目参照）。
【００５３】
（ｃ）それ以外の場合に、不必要な経路更新トラヒックを低減するために、ルーティングテーブル交換レートは係数βだけ減分される。この実施形態では、デフォルトの最大ルーティングテーブル更新間隔は１５ｓに設定され、これは設定可能である（１９行目参照）。
【００５４】
（ｄ）好適な実施形態では、経路失効も監視され、経路失効間隔が調整される。以前の更新間隔の間に経路エントリの何れかが失効され且つルーティングテーブルにほんの少ししか変更がない場合（即ち、rt_chg×３＜rt_table_size）に、イベント・モニタ５０２の経路デーモンはルーティングテーブル更新間隔により経路失効間隔を増やす（２行目、３行目参照）。ネットワークが比較的安定な間にルーティングテーブル・エントリが失効されるため、経路失効間隔の増加は経路失効の解除に役立ち、経路チャーンは低減する。これは、十分な経路変更が検出されなかった場合に、経路失効間隔が段階的に増やされることを意味する。
【００５５】
図２を参照しつつ、本発明の一つの実施形態で用いられる変更検出が説明される。
【００５６】
動作はネットワークにおける変更の検出２０２から始まる。本発明について、３種類のネットワーク変更、即ちローカル変更、リモート変更及び経路失効が前述された。経路失効の検出及び処理はオプションであり、本発明の好適な実施形態において示される。本発明の代替の実施形態は、経路失効の検出と経路失効イベントに応答したネットワークの動作の変更との特徴を含まなくてもよい。
【００５７】
検出されたイベントが経路失効である（２０４）場合に、イベント・モニタ５０２は経路失効カウンタ５０８の値（rt_exp）を１だけ増やす（２０６）。
【００５８】
ローカル変更の検出である（２０８）場合に、イベント・モニタ５０２はローカル用カウンタ５０４（lo_chg）を１だけ増やす。
【００５９】
変更イベントがリモート変更に関する（２１２）場合に、リモート変更イベント用カウンタ（rt_chg）５０６が１だけ増やされる。
【００６０】
イベント・モニタ５０２がこれら三つのグループのいずれにも属さない変更を検出した場合に、当該変更は不明なものとして破棄される（２１６）。
【００６１】
カウンタ５０４、５０６、５０８を増やす動作は二つの連続したルーティングテーブル更新の間の期間に実行される。当該イベントの検出及びカウンタ値の変更の結果として、ルーティングテーブル間隔と、好適な実施形態における経路失効間隔とが調整される。ルーティングテーブル間隔と経路失効間隔との調整は、図３で説明されるように、ルーティングテーブル更新を送信した（３０２）後に実行される。
【００６２】
好適な実施形態では、ノード５００において、経路失効カウンタ５０８が維持され経路失効の際に増やされる。経路失効カウンタ５０８の値が以前のルーティングテーブル更新サイクルと比較して増えており（３０４）、且つリモート変更用カウンタの増加がルーティングテーブルのサイズ（第２所定値）の１／３よりも小さい（３０６）場合に、経路失効間隔はルーティングテーブル更新間隔の値（第１所定値）で増やされる（３０８）．
しかしながら、第１所定値と第２所定値との両方が上述の実施形態のものとは異なる値を有しうることが本発明に意図される範囲内にある。
【００６３】
次のステップにおいて、ローカル変更イベント用カウンタの値が以前のルーティングテーブル更新サイクルと比較して増加したかどうか（３０９）、及びローカル変更イベント用カウンタ５０４変更のレートが増加したかどうか（３１０）が調べられる。結果が「ＹＥＳ」であるならば、ルーティングテーブル更新間隔がコントローラ５１０により積極的に減らされる。一つの実施形態では、ルーティングテーブル更新間隔は２で割られる。ローカル変更イベント用カウンタの値の増加レートが加速しないならば、リモート変更イベント用カウンタ５０６が以前のサイクルから増えたかどうか（３１４）がコントローラ５１０により調べられる。これが確認されたならば、一つの実施形態では、コントローラ５１０はルーティングテーブル交換レートを０．０２だけ増やす（３１６）。リモート変更及びローカル変更が存在せず、且つリモート変更イベント用カウンタとローカル変更イベント用カウンタとが自身の値を変更しないならば、ルーティングテーブル交換レートが０．０２だけ減らされる（３１８）。このサイクルが終了すると、次のルーティングテーブル更新がスケジュールされる（３２０）。
【００６４】
本発明の全体的な利点は制御オーバヘッドの大幅な増加をもたらすことなく、経路収束と経路安定性とを改善することである。
【００６５】
図６は複数のノード５００、６０２〜６１０を備えるアドホック無線通信ネットワーク６００を説明する。一つの実施形態では、当該ノードの少なくとも一部が本発明の方法に従ってこれらを動作させることが可能なノード５００の要素を備える。説明されたように、アドホック通信ネットワークにおいて、一部のノードが削除され又は別の場所へ移動され、若しくはノード間の一部のリンクが削除され又は切断される（６１２）が、これは本発明の実施形態で検討されたようなルーティングテーブルの効率的な更新を必要とする。
【図１】
2011501921.tif 000003
【図２】
2011501921.tif 000004
【図３】
2011501921.tif 000005
【図４】
2011501921.tif 000006
【図５】
2011501921.tif 000007
【図６】
2011501921.tif 000008
【国際調査報告】
2011501921.tif 000009
2011501921.tif 000010