(57)【要約】  本発明は、ツリールーティング技法及びリンクステートルーティング技法の両方の長所を備えた無線通信システムのルーティング方法を提供する。本発明のルーティング方法は、少なくとも一つのノードを有する少なくとも一つのブランチを含むツリー構造でネットワークを定義する適応ツリーテーブルを生成し、各ノードで、隣接のノードについての情報を含むリンクステートテーブルを生成し、適応ツリーテーブル及びリンクステートテーブルを基にパケットをルーティングする。本発明のルーティング方法は、ツリールーティング技法及びリンクステートルーティング技法の長所を採用することによって、従来のツリールーティングの短所であるＳＰＦをほとんど除去でき、従来のツリールーティングと比較して短い経路を提供できる。【選択図】図３
2009529846.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードで構成される無線通信ネットワークでのルーティング方法であって、
少なくとも一つのノードを有する少なくとも一つのブランチを含むツリー構造で前記ネットワークを定義する適応ツリーテーブルを生成するステップと、
各ノードで、隣接のノードについての情報を含むリンクステートテーブルを生成するステップと、
前記適応ツリーテーブル及びリンクステートテーブルを基にパケットをルーティングするステップと、
を有することを特徴とするルーティング方法。
【請求項２】
前記適応ツリーテーブルを生成するステップは、
前記適応ツリーテーブルを初期化するステップと、
前記ネットワークに変化があるか否かを判断するステップと、
前記ネットワークに変化がある場合、前記適応ツリーテーブルを修正するステップと、を含むことを特徴とする請求項１に記載のルーティング方法。
【請求項３】
前記適応ツリーテーブルを初期化するステップは、
前記ブランチを有するノードを、少なくとも一つのルートノード、中間ノード、葉片ノードとして連結するステップと、
前記連結されたノードにアドレスを割り当てるステップと、
を含むことを特徴とする請求項２に記載のルーティング方法。
【請求項４】
前記ノードを連結するステップは、
他のノードを子ノードとして受諾するか否かを判断するとき、各ノードの性能を考慮することを特徴とする請求項３に記載のルーティング方法。
【請求項５】
前記ノードの性能は、既定の受諾レベルにより表わされることを特徴とする請求項４に記載のルーティング方法。
【請求項６】
前記受諾レベルは、少なくとも一つの無条件的受諾、条件的受諾、否定的受諾、及び拒絶を含むことを特徴とする請求項５に記載のルーティング方法。
【請求項７】
前記アドレスを割り当てるステップは、
前記ネットワークの全体ノードの数が可用アドレスの数以下であるかを判断するステップと、
前記ネットワークの全体ノードの数が可用アドレスの数以下であれば、前記ノードにアドレスを割り当てるステップと、
を含むことを特徴とする請求項３に記載のルーティング方法。
【請求項８】
前記全体ノードの数を判断するステップは、
各ノードで、子ノードのそれぞれのブランチに属しているノードの数を受信するステップと、
前記ルートノードで、前記ルートノード下のノードのブランチに属しているノードの数を合算して全体ノードの数を計算するステップと、
を含むことを特徴とする請求項７に記載のルーティング方法。
【請求項９】
前記リンクステートテーブルを生成するステップは、
幾つかのホップ数以内で隣接ノード間のリンクステート情報を交換するステップと、
各ノードで、前記リンクステート情報を基に前記リンクステートテーブルを更新するステップと、
を含むことを特徴とする請求項１に記載のルーティング方法。
【請求項１０】
前記交換されたリンクステート情報は、前記ノードに割り当てられたアドレスブロックの最初及び最後のアドレス、前記適応ツリーテーブルでの前記ノードのツリーレベル、及び１ホップの隣接ノードを含むことを特徴とする請求項９に記載のルーティング方法。
【請求項１１】
前記リンクステートテーブルは、最大ホップの隣接ノードリスト及び連結マトリックスを含むことを特徴とする請求項９に記載のルーティング方法。
【請求項１２】
前記最大ホップの隣接ノードリストは、各ノードに割り当てられたアドレスブロックの開始アドレス（begAddrn）、最後のアドレス（endAddrn）、前記適応ツリーテーブルでの各ノードのツリーレベル（tree_leveln）、及び各ノードのホップ数（hopsn）を含むことを特徴とする請求項１１に記載のルーティング方法。
【請求項１３】
前記各ノードのホップ数（hopsn）は、前記連結マトリックスにより計算されることを特徴とする請求項１２に記載のルーティング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線通信システムのルーティング方法に係り、特に、ツリールーティング技法及びリンクステートルーティング技法の両方の長所を備えた無線通信システムのルーティング方法に関する。
【背景技術】
【０００２】
無線ネットワークに属しているノードが互いに通信を行うためには、先ず、その経路を探すことが必要である。ツリー構造のルーティング技法は、論理的アドレスをツリー構造で結合させることによって、経路探索なしにルーティングが可能であるために有用である。また、ツリールーティング技法は、経路探索による初期遅延を減らし、ルーティングテーブルを保存するために必要な保存空間を減らすことができる。
【０００３】
しかしながら、ツリールーティング技法は、最適の経路提供を保証できず、システム上の一つの異常がもとで全体の異常に陥るＳＰＦ（Single Point of Failure）現象を有するという短所がある。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、上記問題を解決するためのものであって、本発明の目的は、無線通信システムにおいて論理アドレスを適応的に割り当てることができるルーティング方法を提供することにある。
【０００５】
本発明の他の目的は、無線通信システムにおいてＳＰＦ問題を効果的に解決できるルーティング方法を提供することにある。
【０００６】
本発明の更に他の目的は、無線通信システムにおいて強健性及び経路最適化を向上させるルーティング方法を提供することにある。
【課題を解決するための手段】
【０００７】
本発明の一態様において、上記の目的は、複数のノードで構成される無線通信ネットワークのルーティング方法により達成される。前記ルーティング方法は、少なくとも一つのノードを有する少なくとも一つのブランチを含むツリー構造で前記ネットワークを定義する適応ツリーテーブルを生成するステップと、各ノードで、隣接のノードについての情報を含むリンクステートテーブルを生成するステップと、前記適応ツリーテーブル及びリンクステートテーブルを基にパケットをルーティングするステップと、を含むことを特徴とする。
【０００８】
ここで、前記適応ツリーテーブルを生成するステップは、前記適応ツリーテーブルを初期化するステップと、前記ネットワークに変化があるか否かを判断するステップと、前記ネットワークに変化がある場合、前記適応ツリーテーブルを修正するステップと、を含むことが好ましい。
【０００９】
また、前記適応ツリーテーブルを初期化するステップは、前記ブランチを有するノードを、ルートノード、中間ノード、葉片ノードとして連結するステップと、これらのノードにアドレスを割り当てるステップと、を含むことが好ましい。
【００１０】
また、前記ノードを連結するステップは、他のノードを子ノードとして受諾するか否かを判断するとき、各ノードの性能を考慮することが好ましい。
【００１１】
また、前記ノードの性能は、既定の受諾レベルにより表わされることが好ましい。
【００１２】
また、前記受諾レベルは、無条件的受諾、条件的受諾、否定的受諾、及び拒絶を含むことが好ましい。
【００１３】
また、前記アドレスを割り当てるステップは、前記ネットワークの全体ノードの数が可用アドレスの数以下であるかを判断するステップと、前記ネットワークの全体ノードの数が可用アドレスの数以下であれば、前記ノードにアドレスを割り当てるステップと、を含むことが好ましい。
【００１４】
また、前記全体ノードの数を判断するステップは、各ノードで、子ノードから子ノードのそれぞれのブランチに属しているノードの数を受信するステップと、前記ルートノードで、前記ルートノード下のノードのブランチに属しているノードの数を合算して全体ノードの数を計算するステップと、を含むことが好ましい。
【００１５】
また、前記リンクステートテーブルを生成するステップは、所定のホップ数以内で隣接ノード間のリンクステート情報を交換するステップと、各ノードで、前記リンクステート情報を基に前記リンクステートテーブルを更新するステップと、を含むことが好ましい。
【００１６】
また、前記交換されたリンクステート情報は、前記ノードに割り当てられたアドレスブロックの最初及び最後のアドレス、前記適応ツリーでの前記ノードのツリーレベル、及び前記１ホップの隣接のノードを含むことが好ましい。
【００１７】
また、前記リンクステートテーブルは、最大ホップの隣接ノードリスト及び連結マトリックスを含むことが好ましい。
【００１８】
また、前記最大ホップの隣接ノードリストは、各ノードに割り当てられたアドレスブロックの開始アドレス（begAddrn）、最後のアドレス（endAddrn）、前記適応ツリーテーブルでの各ノードのツリーレベル（tree_leveln）、及び各ノードのホップ数（hopsn）を含むことが好ましい。
【００１９】
また、前記各ノードのホップ数（hopsn）は、前記連結マトリックスにより計算されることが好ましい。
【００２０】
また、前記パケットをルーティングするステップは、前記適応ツリーテーブルを基にパケットの方向を決定するステップと、前記リンクステートテーブルを基に次のホップにパケットを伝達するステップと、を含むことが好ましい。
【発明の効果】
【００２１】
本発明のルーティング方法によれば、ツリールーティング技法及びリンクステートルーティング技法の長所を採用することによって、従来のツリールーティングの短所であるＳＰＦを殆ど除去でき、従来のツリールーティングと比較して短い経路を提供できる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明を実施するための最良の形態によるルーティング方法を、図面を参照しながら詳細に説明する。本発明の説明において、本発明の趣旨を明瞭にするため、周知の機能や構成については説明を省略する。
【００２３】
本発明の実施形態によるルーティングアルゴリズムは、適応ツリールーティング及びリンクステートルーティング技法を組み合わせたツリー案内分散型リンクステート（Tree-guided Distributed Link State：ＴＤＬＳ）アルゴリズムと呼ぶ。
【００２４】
ツリー構造は、パケットが中継される正確な次のホップについての情報よりは、どの方向にパケットを伝送するかについての方向を案内するために利用され、次のホップについての正確な情報は、各中継ノードの地域リンクステートテーブルにより決定される。本発明の実施形態によるＴＤＬＳは、複雑性、適応的アドレス割り当て及び分散リンクステートを減らす特徴を有する。
【００２５】
例えば、ＴＤＬＳは、経路検索及び経路復元が不要であるために複雑性を減らし、ネットワークトポロジを考慮してアドレスを割り当て、子ノードの数、アドレスブロックのサイズ、最大ツリーレベルに制限がなく、アドレス枯渇の問題が発生しない。更に、分散リンクステート技法の適用により拡張性を改善でき、多重経路及び強健性を提供し、経路短縮性能を向上させる。
【００２６】
本発明の実施形態において、各ノードは、表１のような適応ツリーテーブルを有する。
【表１】
2009529846.tif 000003
【００２７】
ここで、num_branchはノードが有するブランチの数であり、beg_addrはｉ番目の（ｉ＝１，２，３，…）ブランチの開始アドレス、end_addrはｉ番目の（ｉ＝１，２，３，…）ブランチの最後のアドレスを表す。各ブランチは、連続したアドレスで構成されるアドレスブロックを割り当てられる。本実施形態では、各ブランチに対して連続したブロックが割り当てられる必要はない。
【００２８】
本発明の実施形態において、ＴＤＬＳは、二つの段階、即ち初期化（設定）段階及び動作段階で構成される。初期化段階で、ノードは、ネットワークに合流してツリーを形成する。初期化段階の後、ネットワークは動作段階に入り、動作段階では、一般的な通信が開始される。動作段階の間、新規ノードがネットワークに合流するが、新規ノードの数は、既にネットワークを構成しているノードの数より小さくなければならない。ノードの数又はネットワークトポロジが大きく変更される場合、初期化段階が再び行われる。
【００２９】
適応ツリー形成ステップは、二つの段階、即ち連結及びアドレス割り当て段階に分けられる。
【００３０】
連結段階では、ルート（例えば、ボタンを押すことで、一般的に手動で割り当てられる）から始まって、ノードが漸進的にネットワークに合流してツリーを形成する。このようなツリーは、いかなるノードもアドレスを割り当てられないため、まだ適応ツリーを構成していない。一つのノードが有する子ノードの数には本質的に制限がない。各ノードは、自身の容量及び他の要素によってどのくらい多くのノード（即ち、どのくらい多くのブランチ）を有するかを自ら決定できる。しかし、子ノードの数に柔軟性がない場合、連結する他のノードを探さないこともある。従って、連結要請を受諾又は拒絶するかわりに、ノードが受諾意志を表すために受諾程度（Acceptance Degree:ＡＤ）概念を利用できる。例えば、次のような四つのＡＤレベルが利用できる。
３‐無条件的受諾
２‐条件的受諾
１‐否定的受諾
０‐拒絶（絶対に必要とする場合以外、ノードはこのＡＤを避ける努力をすべきである）
【００３１】
一つのノードが複数の連結応答を受信した場合、もし、他の高い優先順位要素が介入されないならば、このノードは、最も高い連結ＡＤを有するノードを選択しなければならない。ＡＤを利用することによって、ノードが、個々のノードに過酷な負荷を与えずに成功的にネットワークに合流できる機会が多くなる。
【００３２】
一つのブランチが底まで達すれば、即ち、それ以上ネットワークに合流するために待機するノードがなければ（このような目的のために適切なタイマーが使われる）、各ブランチに沿ってノードの数を計算するための上向き式（ｄｏｗｎ−ｔｏｐ）手順が用いられる。
【００３３】
図１は、本発明の一実施形態による無線ネットワークのルーティング方法を説明するためのグラフである。
【００３４】
図１において、括弧内の数字は、一つのノードに属しているブランチのノードの数を表す。例えば、ノードＡ１１０は、二つのブランチを有している。最初のブランチは、８個のノードＢ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ及びＩを含み、二番目のブランチは、６個のノードＪ，Ｋ，Ｌ，Ｍ，Ｎ及びＯを含む。
【００３５】
ノードの数がブランチの底から頂上まで報告されるとき、各ノードは、所望のアドレスの数を知らせることができる。例えば、ノードＦ１２０は、現在自身のために一つのアドレスのみが必要であるとしても、自身が三つのアドレス（それらのうち二つは、将来の拡張可能性のために）が必要であると報告できる。ノードＥ１３０は、五つのアドレス（ノードＦのための三つのアドレス、自身のための一つのアドレス、及び将来の拡張のための一つのアドレス）を要求できる。ルートノードＡ１１０は、全てのブランチから情報を受信した後、アドレスの割り当てを開始する。
【００３６】
アドレス割り当て段階では、下向き式（ｔｏｐ−ｄｏｗｎ）手順が使用される。先ず、ルートノードＡ１１０は、ネットワーク内の全体ノードの数が可用な全体アドレスの数より少ないか否かを調査する。全体ノードの数が全体アドレスの数より多い場合、アドレス割り当ては失敗する。アドレスが過多になる場合にこれを解決するためには、現在のネットワークを更に小さいネットワークに分割するか、又はアドレス空間を増加させることが可能である。本発明の実施形態では、アドレス枯渇はないものと仮定する。続いて、ルートノードＡ１１０は、実際のノードの数及び所望するアドレスの数を考慮して、各ブランチに対して連続したアドレスで構成されるブロックを割り当てる。本実施形態で、割り当てられる実際のアドレスの数は、アドレスの可用性によって、所望するアドレスの数より少ないか（しかし、実際のノードの数より少なくはない）、又は多い。
【００３７】
このような手順は、ツリーの底に至るまで続く。アドレス割り当てが終了すれば、適応ツリーが形成され、各ノードは、自身のブランチを追跡するための適応ツリーテーブルを有する。例えば、ノードＣ１４０は、表２のような適応ツリーテーブルを有する。
【表２】
2009529846.tif 000004
【００３８】
表２は、ノードＣ１４０が三つのブランチを有し、ノードＣ１４０の一番目から三番目のブランチが、それぞれ［６，７，８］，［９，１０，１１，１２，１３］，［１４］のアドレスブロックを有していることを表している。
【００３９】
適応ツリーテーブルが形成された後、ネットワークは動作段階に入る。適応ツリーテーブルを利用して、パケットの経路は容易に決定される。例えば、一つのパケットが受信されれば、ノードＣ１４０は、このパケットの目的地アドレスが自身のブランチのうちの一つに属しているか否かを調査する。
【００４０】
もし、パケットの目的地アドレスがｉ番目のブランチに属しているならば、このパケットは、ｉ番目のブランチのノードbeg_addriを通じてルーティングされる。もし、パケットの目的地アドレスがいかなるブランチにも属していないならば、このパケットは、ノードＣ１４０の親ノードに経路が決定される。
【００４１】
動作段階でノードの数又はネットワークトポロジに重大な変化がないと予期されるとしても、（初期化段階で予約された）可用アドレスが残っている場合のみ、更に、ツリーの任意のレベルのノード（即ち、ブランチ）を合流することが許諾される。動作段階で処理できないほどノードの数又はネットワークトポロジに重大な変化がある場合、ネットワークは、初期化段階を再び経ることができる。
【００４２】
本発明の実施形態では、リンクステート技法を適用する。基本のリンクステート技法では、各ノードがmaxHops（特定のアプリケーションにより決定されるパラメータ）ホップ範囲内でそのノード自身の全ての隣接するノードに対するリンクステートテーブル（Link State Table：ＬＳＴ）を維持する。各隣接ブロックアドレスがＬＳＴに記録されて、隣接ノードに属する全体ブランチに対してルーティングが可能になる。データパケットを伝達するために、ＬＳＴは、最初に質疑を受け、最上の経路が使われる（多重経路が検索されることもある）。もし、ＬＳＴで経路が見つからなければ、パケットは、親ノードに伝達される。
【００４３】
図２は、本発明の一実施形態による基本のリンクステート技法を適用した無線ネットワークのルーティング方法を説明するためのグラフである。図２において、基本のリンクステート技法のためのノードＪ２２０の２ホップリンクステートが示されている。ノードＫ１５０と異なり、ノードＤ，Ｅ，Ｆ，Ｍ及びＮ（２５０，１３０，１２０，１７０及び２６０のそれぞれ）は、ノードＪ２２０の２ホップ範囲内にはないが、これらのノードがノードＪ２２０のルーティング可能な隣接子ノードであるため、依然としてルーティングが可能である。
【００４４】
純粋な適応ツリー方式と比較すると、リンクステートルーティング方式は、平均的に短縮された経路を提供する。また、ほとんどの場合、従来のツリールーティング方式のＳＰＦ問題が除去される。
【００４５】
拡張されたリンクステート技法では、一つのノードがそのＬＳＴを構築するために、既定のmaxHopsパラメータを使用しなければならないということはない。ノードは、依然としてmaxHops距離の隣接情報を交換しなければならないが、あるノードは、周囲のノード密度によってlinkHop距離の隣接ノード（linkHops<=maxHops）のためのＬＳＴを構築できる。一般的に、ノードは、周囲のノード密度が低い場合に大きいlinkHopsを使用し、ノード密度が高い場合に小さいlinkHopsを使用する。リンクステートルーティングを使用する目的のうちの一つは、壊れたツリー経路をバイパスさせるためである。高いノード密度と共に、ノードは、壊れたツリー経路をバイパスするために使われる更に多くの経路を探すことができる。このように向上した信頼度は、ノードが比較的小さいＬＳＴを構築するようにすることができる。
【００４６】
ある地域のノード密度が非常に低い場合は、maxHopsほどに大きなlinkHopsでさえも十分でないこともある。一つの解決方法は、この地域のノードでmaxHopsより大きいlinkHopsを利用できるように許容することである。しかし、デフォルトによりmaxHopsホップ情報のみが交換されるので、この地域の全てのノードがlinkHops（この場合、maxHopsより大きいlinkHops）ホップ情報を再び交換しなければならない。ここで、本実施形態では、他の更に効率的な取り組みを提案する。基本のＬＳＴが構築された後、各ノードは、linkHopsホップ範囲内に各隣接ノードに対する多重経路が存在するか否かを調査する。もし、多重経路が存在しなければ、ノードは、全部のＬＳＴをその隣接ノードにユニキャストする。ＬＳＴを受信したノードは、そのＬＳＴをユニキャストして起点（ｓｏｕｒｃｅ）に戻す。このようにして、関連したノードの間には、2xlinkHopsホップのＬＳＴが生成される。
【００４７】
図３は、本発明の一実施形態による拡張のリンクステート技法を使用した無線ネットワークのルーティング方法を説明するためのグラフである。図３において、基本のＬＳＴが構築された後、ノードＡ３１０は、linkHopsホップ（本実施形態では、３ホップ）範囲内で自身がノードＤ３２０に対する一つの経路のみを有しているということが分かる。従って、ノードＡ３１０は、ノードＤ３２０とＬＳＴ情報を交換する。このようにして、ノードＡ３１０及びノードＤ３２０の両者は、両者間の他の経路、即ちＡ−Ｉ−Ｊ−Ｋ−Ｄ経路が存在するということが分かる。それらのノードそれぞれは、自身のＬＳＴにこの経路を記録すると共に、ノードＩ，Ｊ，Ｋ及びＬに対して（linkHopsのＴＴＬ範囲内で）それを知らせるメッセージをユニキャストし、その結果、これらのノードもまた、自身のＬＳＴを更新するができる。結局、ノードＡ３１０とノードＢ３２０との間の二番目の経路が検出される。ツリー構造において、linkHopsホップ範囲内の全ての隣接ノードのうち、先祖ノード及び子孫ノードは、他のノードに比べて更に重要である。従って、あるノードは、自身の隣接ノードを選択的に差別化して扱うことができる。例えば、先祖ノード及び子孫ノードに多重経路を保証し、他のノードより先祖ノード及び子孫ノードに更に多くのホップのリンクステートを維持することを保証する。
【００４８】
要約すると、本発明の実施形態による拡張のリンクステート技法は、基本のリンクステート技法に比べて更に信頼性が高く、効率的であり、かつ適応的である。
【００４９】
ツリー形成後、ノードは、maxHopsのＴＴＬを考慮して数回にわたるHelloメッセージを周期的に放送（ｂｒｏａｄｃａｓｔｉｎｇ）することによって、リンクステート情報を交換する。一例として、Helloメッセージフォーマットは、表３の通りである。
【表３】
2009529846.tif 000005
【００５０】
表４のようなmaxHopsホップの隣接ノードリスト及び表５のような連結マトリックスで構成される一つのノードのリンクステートテーブルは、Helloメッセージが受信される度に更新される。
【００５１】
各ノードは、Helloメッセージを受信するやいなや、自身の隣接ノードリストを更新する。Helloメッセージのソースが隣接ノードリストに追加されるだけでなく、このソースの１ホップ隣りのノードも一時的に“未認知”とマークされて、endAddr及びtree_levelと共に追加される。 “未認知”endAddr及びtree_levelは、相手の隣接ノードからHelloメッセージを受信すると共に、実際の値に置き換えられる。もし、全体のHelloメッセージ交換手順の間にHelloメッセージが受信されなければ、ノードは、endAddr及びtree_level情報のない全ての隣接ノードを含む１ホップ隣りのノードに対してメッセージを放送することによって、endAddr及びtree_level情報を要請できる。このメッセージを受信した各１ホップ隣りのノードは、メッセージに含まれた一つ以上の隣接のノードに対するendAddr及びtree_level情報を提供できれば応答する。hopsフィールドは、連結マトリックスによって計算される。
【表４】
2009529846.tif 000006
【００５２】
各Helloメッセージに含まれている１ホップ隣りの情報から、ノードは、隣りのリストに記録されている隣接ノードに対する連結マトリックスを構築できる。表５は、連結マトリックスの一例を示す。
【表５】
2009529846.tif 000007
【００５３】
隣接ノードリストで各ノードのhopsフィールドは、連結マトリックスを利用して計算され、最初に各ノードのhopsフィールドは無限大に設定される。そして、“ｍｅ”に直接連結されている全てのノードは、１ホップ隣りのノードである（上記実施例では、nb2,nbn-1,…）。次に、１ホップ隣りのノードに直接連結された（そして、無限大のホップを有する）全てのノードは、２ホップ隣りのノードである（上記実施例では、nb1,nb3,…）。このような手順は、全ての隣接ノードのホップ数が満たされるまで続く。
【００５４】
下記の擬似コードは、データ伝送のための次のホップを選択する方法を説明している。
＜擬似コード＞
2009529846.tif 000008
【００５５】
複数の隣接ノードが選択される可能性があり（上記疑似コードの１１行及び３２行参照）、一つの隣接ノードを示すコストメトリックが他のメトリックより選好されない場合、ロードバランス目的のために一つの隣接ノードをランダムに選択することが可能である。しかし、無順序（ｏｕｔ  ｏｆ  ｏｒｄｅｒ）問題を緩和するために、一旦、一つのノードが選択されれば（その都度ランダムに一つの隣接ノードを選択するよりは）、この隣接ノードを固守することが好ましい。ルーティング失敗により次のホップのノードを探すことができなければ、リング探索が行われなければならない。リング探索は、リンクステート生成段階で、大きいＴＴＬと共にHelloメッセージを交換することによって行われる。
【００５６】
通信オーバーヘッド及び干渉を減らすために、リンクステート生成段階以後では、周期的なHelloメッセージが放送されない。リンクステート生成段階以後、Helloメッセージは、リンク失敗、リンク復旧、又は新規に隣接ノードが検出される場合にのみ放送される。もし、あるノードが一部のHelloメッセージを見落とせば、このノードのリンクステートは正確でないこともある。不正確なリンクステートは、迂回経路の選択だけでなく、更に深刻なルーティングループを発生させる。
【００５７】
周期的なHelloメッセージを使用せずに不正確なリンク状態を迅速に検出するための方法として、メッセージに１ビットの下向きフラグ及びいわゆる中継ノードの仮想ツリーレベルを含むことが考えられる。下向きフラグは、以前のホップが上向き又は下向きのメッセージ伝達の如何を表す。仮想ツリーレベルは、次の数式１のように定義される。
【数１】
2009529846.tif 000009
【００５８】
ここで、neighborLevelは、上記擬似コードの２１行に与えられたneighbor_foundのツリーレベルであり、hops2Nbは、neighbor_foundに対するホップである。
【００５９】
そして、
flag1＝インカミングメッセージに含まれている下向きフラグ
vTreeLevel1＝インカミングメッセージに含まれている仮想ツリーレベル
flag2＝メッセージ受信器の下向きフラグ
vTreeLevel2＝メッセージ受信器の仮想ツリーレベル
とすれば、数式２のように表わされる。
【数２】
2009529846.tif 000010
【００６０】
もし、受信器がmaxHops-1（即ち、以前のホップにより使われたものより１ホップ小さい）ホップリンクステート情報のみを利用してflag2及びvTreeLevel2を計算するならば、数式２において“＝”記号のみが適用されなければならない。
【００６１】
更に効率的な方法として、メッセージに下向きフラグ及びhops2Nb値のみを含むことも可能である。同様にして、パラメータは、次のように定義される。
flag1＝インカミングメッセージに含まれている下向きフラグ
hops2Nb1＝インカミングメッセージに含まれているhop2Nb値
flag2＝メッセージ受信器の下向きフラグ
hops2Nb2＝メッセージ受信器のhop2Nb値
【００６２】
上記全ての値がmaxHopsホップリンクステート情報を使用して計算されるならば、hops2Nb1とhops2Nb2との間には何らの関係がないということが、数式１及び数式２から分かる。数式２は、二つのvirtual_tree_level値間の関係を表す。もし、二つの値がmaxHopsリンクステート情報（以前のホップ及び受信器は異なるmaxHopsリンクステート情報を持つ）を使用して計算されるならば、二つのneighborLevel値間には何らの連関性がない。従って、数式１によって、hops2Nb1とhops2Nb2との間にも連関性がない。上記を基に、maxHopsホップリンクステート情報は、flag1とhops2Nb1とを計算するために使われ、maxHops-1ホップリンクステート情報のみがflag2とhops2Nb2とを計算するために使われる。この場合、数式３の関係にならなければならない。
【数３】
2009529846.tif 000011
【００６３】
数式２又は数式３が満たされなければ、以前のホップ又は／及び受信器のリンクステート情報は不正確である。この場合、受信器は、自身のmaxHops‐１ホップ連結マトリックスを以前のホップとし、受信した連結マトリックスと自身の連結マトリックスとを比較し、二つの連結マトリックスの不一致記録と関連した全ての隣接ノードに知らせる。このような通知を受けたノードは、隣接ノードのリンク状態を更新するために数回Helloメッセージを放送する。
【００６４】
もし、リンク失敗、リンク復旧、又は新規隣接ノードの検出などの原因により１ホップの連結性が変更されたことが検出されれば、そのノードは、maxHopsのＴＴＬに数回Helloメッセージを放送する。伝送失敗は、（ノード失敗を含む）リンク失敗、衝突、又はバックグラウンド干渉により発生する。従って、伝送失敗の度に経路を変更することは好ましくない。本発明の実施形態では、伝送に失敗した隣接ノードは最初にプローブリストに登載される。プローブリストの隣接ノードは、未知又は故障状態でありうる。未知状態の隣接ノードは、タイマーを使用する（タイマー駆動される）最後のプローブ以後の毎プローブ区間、又はデータ伝送（データ駆動）のための次のホップとして選択される度に直ちにプローブされる。未知状態の隣接ノードが正常な隣接ノードのように次のホップノードとして依然選択されうるとしても、隣接ノードは、データパケットを伝送するために実際に使われることはない。このような隣接ノードを次のホップとして有する全てのパケットデータは、バッファリングされるか、又はメモリが不十分である場合に除去される。プローブは、隣接ノードに対する連結が復元されるか、又はタイマー駆動プローブ及びデータ駆動プローブを含む全体のプローブ数がmax_probe_numに達するまで続く。
【００６５】
もし、リンクが復元されれば、対応する隣接ノードは、プローブリストから削除され、この隣接ノードのためにバッファリングされていた全てのパケットは、この隣接ノードに伝達される。もし、プローブの媒体接続制御確認メッセージ（Media Access Control Acknowledgement:ＭＡＣ  ＡＣＫ）が受信されるか（ルーティング階層がＭＡＣ  ＡＣＫの状態が分かるならば）、又はルーティング階層を通じて隣接ノードから受信されたプローブに対する応答を含むパケットが受信（又は、オーバーヒアリングが支援される場合、ＭＡＣによるオーバーヒアリング）されれば、リンクが発見されたと見なす。
【００６６】
もし、プローブ回数がリンク復元以前にmax_probe_num値に達すれば、隣接ノードの状態は故障に変わる。従って、連結マトリックスは更新され、HelloメッセージがmaxHopsのＴＴＬと共に放送される。最初のHelloメッセージ放送後、隣接ノードのためにバッファリングされていた全てのデータパケットは、他の経路を通じてルーティングされる。本来の次のホップが故障状態であることが決定され、全てのmaxHops-hopホップの隣接ノードがHelloメッセージを通じてそのことを通知される前には、データパケットが他の経路を通じてルーティングされてはならない。その理由は、可能性は高くないが、他のノードが本来の次のホップが故障状態であることを知らないため、データパケットが現在のノードに戻されることもあるためである。
【００６７】
もし、隣接ノードに対するリンクが故障状態と決定されれば、隣接ノードは、プローブリストに残り、隣接ノードは、タイマーによってのみプローブされ（データパケットの次のホップとして使用されることはない）、プローブ間隔は、毎プローブ後に、最大値max_probe_intervalまで増加する。例えば、故障状態である隣接ノードは、２，４，６，…，max_probe_interval秒の間隔でプローブされる。このことは、リンクが復旧される場合、max_probe_interval秒を超えない範囲内でリンクの検出を促進する。
【００６８】
以上。本発明を具体的な実施形態を参照しながら詳細に説明してきたが、本発明の範囲及び精神から逸脱しない限度内で様々な変形が可能であることは、この技術分野における通常の知識を持つ者には明らかである。従って、本発明の範囲は、特許請求の範囲だけでなく、この特許請求の範囲と均等なものにより決まらなければならない。
【図面の簡単な説明】
【００６９】
【図１】本発明の一実施形態による無線ネットワークを示すグラフである。
【図２】本発明の一実施形態による基本のリンクステート技法を説明するための無線ネットワークを示すグラフである。
【図３】本発明の一実施形態による拡張のリンクステート技法を説明するための無線ネットワークを示すグラフである。
【符号の説明】
【００７０】
１１０    ルートノードＡ
１２０    ノードＦ
１３０    ノードＥ
１４０    ノードＣ
１５０    ノードＫ
１７０    ノードＭ
２２０    ノードＪ
２５０、３２０    ノードＤ
２６０    ノードＮ
３１０    ノードＡ
【図１】
2009529846.tif 000012
【図２】
2009529846.tif 000013
【図３】
2009529846.tif 000014
【国際調査報告】
2009529846.tif 000015
2009529846.tif 000016