(57)【要約】【課題】  ツリールーティング無線ネットワークを構成しているノードまたはリンクが破壊された時に既存のツリールーティング構造をできるだけ維持しつつ経路を最適に復旧する方法を提供する。【解決手段】  ルーティング経路復旧方法は、第２ノードがルーティング経路の復旧を要求する経路復旧の要求パケットをブロードキャスティングする段階、経路復旧の要求パケットを受信した少なくとも１つのノードが経路の復旧のための中継ノードの役目を果たすために経路復旧の応答パケットを第２ノードに伝送する段階、第２ノードが経路復旧の応答パケットを伝送した少なくとも１つのノードのうちのいずれか１つのノードを中継ノードと選択しこれを知らせる経路復旧の確認パケットを中継ノードに伝送する段階、  及び中継ノードが第１ノードに経路復旧の報知パケットを伝送して第２ノードと第１ノードとのルーティング経路を設定する段階とを含む。【選択図】      図２
2005080316.tif 000002
【特許請求の範囲】
【請求項１】
ツリールーティング連結形態（tree topology）構造の無線ネットワークを構成する複数のノードのうち上位の第１ノードとの連結を喪失した下位の第２ノードが前記無線ネットワーク内でルーティング経路を復旧するルーティング経路復旧方法において、
前記第２ノードがルーティング経路の復旧を要求する経路復旧の要求パケットをブロードキャスティングする段階と、
前記経路復旧の要求パケットを受信した少なくとも１つのノードが経路の復旧のための中継ノードの役目を果たすために経路復旧の応答パケットを前記第２ノードに伝送する段階と、
前記第２ノードが前記経路復旧の応答パケットを伝送した前記少なくとも１つのノードのうちのいずれか１つのノードを前記中継ノードと選択し、これを報知する経路復旧の確認パケットを前記中継ノードに伝送する段階と、
前記中継ノードが前記第１ノードに経路復旧の報知パケットを伝送して、前記第２ノードと前記第１ノードとのルーティング経路を設定する段階とを含むことを特徴とするルーティング経路復旧方法。
【請求項２】
前記ルーティング経路を設定する段階は、
前記第１ノードが前記無線ネットワークに接続されていない場合、前記第１ノードの上位ノードに前記経路復旧の報知パケットを伝送して前記上位ノードと前記第２ノードとのルーティング経路を設定することを特徴とする請求項１に記載のルーティング経路復旧方法。
【請求項３】
前記第２ノードが前記経路復旧の応答パケットを所定の時間中受信しなければ、前記第２ノードの下位ノードが前記経路復旧の要求パケットを再びブロードキャスティングする段階をさらに含むことを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項４】
前記下位ノードが前記経路復旧の応答パケットを受信すれば、前記経路復旧の応答パケットに前記下位ノードのアドレスを含めて前記第２ノードに伝送することを特徴とする請求項３に記載のルーティング経路復旧方法。
【請求項５】
前記中継ノードは、前記下位ノードを経由して、前記第１ノード及び前記上位ノードのうちのいずれか１つと前記第２ノードとのルーティング経路を設定することを特徴とする請求項３に記載のルーティング経路復旧方法。
【請求項６】
前記経路復旧の要求パケットは前記第２ノードのアドレス及び前記パケットのブロードキャストＩＤのうちの少なくとも１つを含むことを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項７】
前記経路復旧の応答パケットは前記第２ノードのアドレス、前記中継ノードのアドレス及び前記中継ノードから前記第２ノードまでのホップ数のうちの少なくとも１つを含むことを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項８】
前記第２ノードは前記経路復旧の要求パケットに前記第２ノードから前記中継ノードまでのホップ数の制限値を設定してブロードキャスティングすることを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項９】
前記第２ノードは所定の時間中前記経路復旧の応答パケットが受信されなければ、前記ホップ数の制限値を増やして前記経路復旧の要求パケットを再びブロードキャスティングすることを特徴とする請求項８に記載のルーティング経路復旧方法。
【請求項１０】
前記第２ノードは前記経路復旧の応答パケットを伝送した前記少なくとも１つのノードのうち前記第２ノードまでのホップ数に基づき前記中継ノードを選択することを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項１１】
前記第２ノードは前記経路復旧の応答パケットを伝送した前記少なくとも１つのノードのうち前記ツリールーティング連結形態構造における順位に基づき前記中継ノードを選択することを特徴とする請求項１０に記載のルーティング経路復旧方法。
【請求項１２】
前記経路復旧の報知パケットは前記経路復旧の報知パケットを伝送する前記ノードのアドレス及び前記第２ノードのアドレスを含むことを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項１３】
前記中継ノードは前記第４ノードと前記第２ノードとの前記ルーティング経路を記録したルーティングテーブルを保存することを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項１４】
前記第４ノードと前記第２ノードとの前記ルーティング経路を構成する各ノードは前記ルーティング経路を記録したルーティングテーブルを保存することを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項１５】
前記第４ノードは、前記第２ノードとの前記ルーティング経路を構成する各ノードのアドレスを含む経路復旧の確認パケットを前記第２ノードに伝送することを特徴とする請求項２に記載のルーティング経路復旧方法。
【請求項１６】
ツリールーティング連結形態構造の無線ネットワークを構成する複数のノードのうち上位の第１ノードとの連結を喪失した下位の第２ノードが前記無線ネットワーク内でルーティング経路を復旧するルーティング経路復旧方法において、
前記第２ノードが前記第１ノードとのルーティング経路の復旧を要求する経路復旧の要求パケットをブロードキャスティングする段階と、
前記第１ノードが前記経路復旧の要求パケットを受信すれば、前記経路復旧の要求パケットが伝送された経路のうちのいずれか１つの経路を代替経路と選択し、選択された前記代替経路を構成するノードを経由して前記第２ノードに経路復旧の応答パケットを伝送する段階と、
選択された前記代替経路を介して前記第２ノードと前記第１ノードとのルーティング経路を設定する段階とを含むことを特徴とするルーティング経路復旧方法。
【請求項１７】
前記第２ノードは所定の時間中前記経路復旧の応答パケットが受信されなければ、前記第１ノードが前記無線ネットワークに接続されていないことと判断し、前記第１ノードの上位ノードとのルーティング経路の復旧を要求する経路復旧の要求パケットをブロードキャスティングすることを特徴とする請求項１６に記載のルーティング経路復旧方法。
【請求項１８】
前記第１ノードの前記上位ノードは前記経路復旧の要求パケットが伝送された経路のうちのいずれか１つの経路を代替経路と選択し、選択された前記代替経路を構成するノードを経由して前記第２ノードに経路復旧の応答パケットを伝送することを特徴とする請求項１７に記載のルーティング経路復旧方法。
【請求項１９】
前記ルーティング経路設定段階では、選択された前記代替経路を介して前記第１ノードの前記上位ノードと前記第２ノードとのルーティング経路を設定することを特徴とする請求項１８に記載のルーティング経路復旧方法。
【請求項２０】
前記経路復旧の応答パケットは、前記代替経路を構成するノードのアドレス、前記代替経路名、前記代替経路のホップ数、前記第１ノードのアドレス及び前記第２ノードのアドレスのうちの少なくとも１つを含むことを特徴とする請求項１８に記載のルーティング経路復旧方法。
【請求項２１】
前記代替経路を構成する前記ノードは前記代替経路を通したルーティング経路に対するルーティング情報を保存することを特徴とする請求項１８に記載のルーティング経路復旧方法。
【請求項２２】
前記第２ノードは前記経路復旧の要求パケットが伝送されるホップ数の制限数を予め設定し、
前記経路復旧の要求パケットを受信したノードは、前記第２ノードからのホップ数が設定された前記ホップ数の制限を越えなければ受信された前記経路復旧の要求パケット要求パケットをブロードキャスティングする段階をさらに含むことを特徴とする請求項１６に記載のルーティング経路復旧方法。
【請求項２３】
前記第２ノードは所定の時間中前記経路復旧の応答パケットが受信されなければ前記ホップ数の制限数を増やして前記経路復旧の要求パケットを再びブロードキャスティングすることを特徴とする請求項２２に記載のルーティング経路復旧方法。
【請求項２４】
前記第２ノードは前記経路復旧の要求パケットを伝送して前記第１ノードが故障であるか前記第２ノードと前記第１ノードとの連結が切れたかを見つけ出すことを特徴とする請求項１７に記載のルーティング経路復旧方法。
【請求項２５】
選択された前記代替経路を構成するノードを代替ノードと定義し、前記第２ノードをＢＢ(Bottom Boundary of the agent link)と、前記第１ノード及び前記上位ノードのうち前記代替経路を構成するノードをＴＢ(Top Boundary of the agent link)と定義し、前記ＴＢと前記ＢＢとのルーティング経路を復旧することを特徴とする請求項１７に記載のルーティング経路復旧方法。
【請求項２６】
前記第２ノードは前記経路復旧の要求パケットをブロードキャスティングする方法で前記上位ノードに伝達することを特徴とする請求項１７に記載のルーティング経路復旧方法。
【請求項２７】
前記第２ノードは前記経路復旧の要求パケットをユニキャストして前記上位ノードに伝達することを特徴とする請求項１７に記載のルーティング経路復旧方法。
【請求項２８】
前記第１ノードまたは前記上位ノードは、前記経路復旧の応答パケットを使用して前記第１ノードまたは前記上位ノードと前記第２ノードとの前記ルーティング経路を設定することを特徴とする請求項１７に記載のルーティング経路復旧方法。
【請求項２９】
選択された前記代替経路を構成する前記ノードにそれぞれ前記ルーティング経路設定のための情報を保存して前記第１ノードまたは前記上位ノードと前記第２ノードとの前記 ルーティング経路を設定することを特徴とする請求項１７に記載のルーティング経路復旧方法。
【請求項３０】
前記第１ノードまたは前記上位ノードは、前記第２ノードに伝送するデータパケットに前記第１ノードのアドレス情報、前記第１ノードまたは前記上位ノードから前記第２ノードまでのホップ数、及び前記第１ノードの各下位ノードを区分するビットを保存することを特徴とする請求項１７に記載のルーティング経路復旧方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はツリールーティング連結形態（tree topology）構造を有する無線ネットワークに係り、特にツリールーティング無線ネットワークを構成しているノード自体またはその連結が喪失した時に既存のツリールーティング構造経路をできるだけ維持し破壊された経路（broken route）を最適に復旧する方法に関する。
【背景技術】
【０００２】
インターネットと移動通信技術の発展に伴って現在の社会においては時間と空間を問わず多様なマルチメディアサービスが提供されているためユーザの生活環境が大きく変化しつつある。特に、最近はノート型ＰＣ、ＰＤＡなどの小型携帯電子機器が次第に普及されることによって、インターネットを基盤とするデータ通信を有線ネットワークだけではなく無線ネットワークを介して実施しようとする努力が増大しつつある。
【０００３】
このような無線ネットワークの代表的な例としてAd-hoc網を挙げられる。Ad-hoc網には中央集約された管理装置がなく、既存の通信基盤構造を用いておらず、移動ノード間連結提供のためには固定された制御装置(ルータ、ホスト、無線基地局など)を使用しないという特徴がある。すなわち、Ad-hoc網によれば移動ノード自らがルータで動作するようになる。従って、所定の移動ノードがコレスポンデントノード（Correspondent node：移動ノードの通信相手となるノード）に通信を行なおうとする場合、その移動ノードはコレスポンデントノードとの間に位置する多数のノードを介して通信経路を開設する必要がある。
【０００４】
このようなAd-hoc網の一例であって、ツリールーティング構造を有する無線ネットワークが挙げられる。ツリールーティング構造はネットワークの機能のうちアドレス割当てやルーティングに長所を持っていて幅広く使用されている。すなわち、ツリールーティング構造のネットワークではツリー階層によってアドレスを順次に割当て、パケットはツリー経路に沿って伝送される。
【０００５】
しかし、このようなツリールーティング構造のネットワークを構成するノードにおいてバッテリーの放電または故障、移動などによるネットワークからの離脱、ネットワークとの連結の切断などにより不具合が生じた場合、該当ノード又はリンクの下位の階層に属するノードはツリー構造の経路においてその通信経路を再設定して復旧しなければならない。
【０００６】
このため、従来のアルゴリズムでは故障したノードまたはリンクの下位に属する全てのノードに対してそれぞれネットワークに再接続を行わせて経路を再設定する方法が取られていた。しかし、この場合制御が過負荷（overload）となる問題点と既存のツリー構造のアドレスに変更が生じる問題、既存のツリー構造のトポロジー（topology：接続形態）が変わる問題点があった。
【０００７】
また、切れたリンクの下位の階層に属するノードについてはローカルアドレス、ツリールーティング構造における位置(depth)、隣接ノードリストなどの情報を保存する情報テーブルを更新する必要があった。特に、切れたリンクがツリー構造で上位に属するノードに該当する場合その下位であるツリー構造全体に影響を与え、リンクを新たに構成しなおす必要があった。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は前述した問題点を解決するために案出されたもので、その目的はツリールーティング無線ネットワークを構成しているノードまたはリンクが破壊され場合に、既存のツリールーティング構造をできるだけ維持し、経路を最適に復旧する方法を提供するところにある。
【課題を解決するための手段】
【０００９】
前述した本発明の目的を達成するためのツリールーティング連結形態構造の無線ネットワークを構成する複数のノードのうち上位の第１ノードとの連結を喪失した下位の第２ノードが前記無線ネットワーク内でルーティング経路を復旧するルーティング経路復旧方法は、前記第２ノードがルーティング経路の復旧を要求する経路復旧の要求パケットをブロードキャスティング（broadcasting）する段階、前記経路復旧の要求パケットを受信した少なくとも１つのノードが経路の復旧のための中継ノードの役目を果たすために経路復旧の応答パケットを前記第２ノードに伝送する段階、前記第２ノードが前記経路復旧の応答パケットを伝送した前記少なくとも１つのノードのうちのいずれか１つのノードを前記中継ノードとして選択しこれを知らせる経路復旧の確認パケットを前記中継ノードに伝送する段階、及び前記中継ノードが前記第１ノードに経路復旧の報知パケットを伝送して前記第２ノードと前記第１ノードとのルーティング経路を設定する段階とを含む。
【００１０】
前記ルーティング経路設定段階は、前記第１ノードが前記無線ネットワークに接続されていない場合、前記第１ノードの上位ノードに前記経路復旧の報知パケットを伝送して前記上位ノードと前記第２ノードとのルーティング経路を設定しても良い。
【００１１】
さらに、前記第２ノードが前記経路復旧の応答パケットを所定の時間中受信しなければ前記第２ノードの下位ノードが前記経路復旧の要求パケットを再びブロードキャスティングする段階をさらに含む。
【００１２】
また、前記下位ノードが前記経路復旧の応答パケットを受信すれば、前記経路復旧の応答パケットに前記下位ノードのアドレスを含めて前記第２ノードに伝送しても良い。
【００１３】
前記中継ノードは、前記下位ノードを経由して、前記第１ノード及び前記上位ノードのうちのいずれか１つと前記第２ノードとの間のルーティング経路を設定しても良い。
【００１４】
前記経路復旧の要求パケットは前記第２ノードのアドレス及び前記パケットのブロードキャストＩＤのうちの少なくとも１つを含んでも良い。
【００１５】
前記経路復旧の応答 パケットは前記第２ノードのアドレス、前記中継ノードのアドレス及び前記中継ノードから前記第２ノードまでのホップ数のうちの少なくとも１つを含ませても良い。
【００１６】
さらに、前記第２ノードは前記経路復旧の要求パケットに前記第２ノードから前記中継ノードまでのホップ数の制限値を設定してブロードキャスティングすることもできる。
【００１７】
また、前記第２ノードは所定の時間中前記経路復旧の応答パケットが受信されなければ前記ホップ数の制限値を増やして前記経路復旧の要求パケットを再びブロードキャスティングするようにしても良い。
【００１８】
前記第２ノードは前記経路復旧の応答パケットを伝送した前記少なくとも１つのノードのうち前記第２ノードまでのホップ数に基づき前記中継ノードを選択することもできる。
【００１９】
また、前記第２ノードは前記経路復旧の応答パケットを伝送した前記少なくとも１つのノードのうち前記ツリー 階層構造における順位に基づき前記中継ノードを選択することができる。
【００２０】
前記経路復旧の報知パケットは前記経路復旧の報知パケットを伝送する前記ノードのアドレス及び前記第２ノードのアドレスを含む。
【００２１】
また、前記中継ノードは前記第４ノードと前記第２ノードとの前記ルーティング経路を記録したルーティングテーブルを保存するができる。
【００２２】
前記第４ノードと前記第２ノードとの前記ルーティング経路を構成する各ノードは前記ルーティング経路を記録したルーティングテーブルを保存することができる。
【００２３】
また、前記第４ノードは、前記第２ノードとの前記ルーティング経路を構成する各ノードのアドレスを含む経路復旧の確認パケットを前記第２ノードに伝送することができる。
【発明の効果】
【００２４】
前述したように、本発明はツリールーティング無線ネットワークを構成しているノード自体またはその連結が喪失した時に既存のツリールーティング構造経路をできるだけ維持し破壊された経路を最適に復旧してルーティング経路を設定することによって、既存のツリー構造を全面的に再設定する必要がなくなり、その結果ネットワーク資源を節約し効率的なルーティングが可能になる。
【発明を実施するための最良の形態】
【００２５】
以下、添付した図面に基づき本発明を詳述する。
【実施例】
【００２６】
図１はツリー構造の無線ネットワークの一例を示した図である。
【００２７】
同図を参照すれば、無線ネットワークは少なくとも２つのノードで構成され、ツリー構造の最上位であるノードＡから下位であるノードＬまで示されている。ここで、ノードＣにおいてバッテリーの放電またはソフトウェアの不備、ハードウェアの故障またはネットワークの外部への移動などの理由からリンクから接続が切れた（disconnect）と仮定する。この場合、ノードＣに対して下位ノードであるノードＧとノードＫ、及びノードＨとノードＬはノードＣを通したツリールーティング構造経路を喪失してネットワークに対する連結が切れるようになる。
【００２８】
図２は本発明の一実施例によるツリールーティング構造経路を維持するための方法の説明に使用される図である。同図を参照すれば、ノードＣの下位ノードであるノードＧ（１２０）、ノードＫ（１３０）、ノードＦ（１４０）及びノードＣの上位ノードであるノードＡ（１１０）間の信号流れを示す。ここで、ノードＣはＰＯＳ(Parent of orphaned sub-tree)、ノードＧ（１２０）はＴＯＳ(Top node of the Orphaned sub-tree)に該当する。ノードＫ（１３０）はＧＦＯ(Gateway node from the orphaned sub-tree)になれ、ノードＦ（１４０）はＧＴＯ(Gateway node to the orphaned sub-tree)になれる。そして、ノードＡ（１１０）はＰＯＦ(grandParent node of the TOS)に該当する。
【００２９】
ノードＣとのリンクが切れると、その下位ノードのうち最上位ノードであるノードＧ （１２０）はネットワーク接続が切れたことを確認し、経路復旧を要求する経路復旧の要求(Local repair request: LREQ)バケットをブロードキャスティングする(Ｓ２１０)。経路復旧の要求パケットはＴＴＬ(Time-to-live)項目を含む。ＴＴＬはノードＧ（１２０）から新たに設定される経路のホップ数の制限数を設定したもので、既設定された値が例えば"２"の場合ノードＧ（１２０）で"２"と設定して経路復旧の要求パケットがブロードキャスティングされ、１ホップを経由する時毎に１つずつ減少して、ノードＫ（１３０）はこれより"１"を差し引いた値である"１"と設定して経路復旧の要求パケットを再びブロードキャスティングするようになり、ＴＴＬが"０"になれば経路復旧の要求パケットは無視される。これは可能な限り最小限のホップ数で経路を復旧するためである。
【００３０】
経路復旧の要求パケットはＴＴＬ領域外にもＴＯＳのアドレス領域、及びブロードキャストＩＤ領域を含む。ブロードキャストＩＤはＴＯＳの下位ノードが同一な経路復旧の要求パケットを反復的にブロードキャスティングすることを防止するためのものである。
【００３１】
これにより、ブロードキャスティングされた経路復旧の要求パケットを受信したノードＫ（１３０）は経路復旧の要求パケットに自分自身のアドレスを含めてブロードキャスティングする(Ｓ２２０)。この場合、ノードＧ（１２０）と１ホップ数（hop count）に存するノードＫ（１３０）及びノードＬだけがパケットをブロードキャスティングするようになる。すなわち、経路復旧の要求パケットはノードＧ（１２０）と１ホップ距離に存する下位ノードによってだけ再びブロードキャスティングされることが望ましい。
【００３２】
経路復旧の要求パケットを受信したノードのうち経路を復旧する中継ノードとしての役目を果たそうとするノードは経路復旧の応答(Local repair reply: LREP)パケットをノードＫ（１３０）を経由してノードＧ（１２０）に伝送する(Ｓ２３０)。ここでは、便宜上ノードＦ（１４０）を例として挙げたが、複数のノードが経路復旧の応答パケットを伝送できる。経路復旧の応答パケットはＧＴＯのアドレス、ＧＴＯの階層順位、ＴＯＳのアドレス及びブロードキャストＩＤを含む。ＧＦＯは経路復旧の応答パケットに自分自身のアドレスを含めてＴＯＳに伝送する。
【００３３】
一方、ノードＦ（１４０）から経路復旧の応答パケットを受信したノードＧ（１２０）はノードＦ（１４０）及びその他経路復旧の応答パケットを伝送したノードのうちツリー階層順位で最上位に位置しつつノードＫ（１３０）からのホップ数が最小のノードを中継ノードと選択する。そして、ノードＧ（１２０）はノードＫ（１３０）を通して選択された中継ノード(ここでは、ノードＦ（１４０）が選択されたと仮定する)に経路復旧の確認(Local repair confirm: LCON) パケットを伝送する(Ｓ２４０)。経路復旧の確認パケットはＴＯＳアドレス、ＰＯＳアドレス、ＧＦＯアドレス及びＧＴＯアドレスを含む。
【００３４】
経路復旧の確認パケットを受信したノードＦ（１４０）は経路復旧の報知(Local repair inform: LINF)パケットをＰＯＳのノードＣに伝送するようになるが、それはノードＦがノードＣが故障なのか、あるいはノードＣとノードＧとの連結が切れたことによるのか分からないからである。この際、ＰＯＦのノードＡ（１１０）がＬＩＮＦを先に受けるようになり、ノードＣが故障か否かを分かって後にノードＡ（１１０）からノードＧ（１２０）への経路を設定することを知らせる(Ｓ２５０)。以上の例はノードＣに問題が発生してネットワークとの連結が切れた場合を仮定したもので、ノードＣに問題が発生せず、ただノードＣとノードＧ（１２０）の連結だけが切れた場合はノードＦ（１４０）は経路復旧の報知パケットをＰＯＳのノードＣに伝送し、ノードＣとノードＧとの経路を再び設定して経路を復旧するようになる。一方、ノードＡ（１１０）は自分自身のアドレス、ノードＧ（１２０）のアドレス及び設定された経路を構成するノードのアドレスを含む経路復旧の確認パケットをノードＧ（１２０）に伝送して経路を構成する各ノードがルーティングテーブルをそれぞれ保存しなくても設定された経路に沿ってパケットを送受信することもできる。前述したような方法でノードＨはノードＬとノードＩを介してノードＡに経路を設定する。
【００３５】
図３及び図４は本発明の他の実施例によるツリールーティング構造経路の復旧のための方法の説明に提供される図である。ここで、図３はノードＣとノードＡの連結が切れた場合であり、図４はノードＣの故障または移動などの状況によってネットワーク連結が切れた場合である。
【００３６】
ここでは、代替経路(Agent link)とＳＮ(Substitute node)、ＴＢ(Top Boundary of the agent link)及びＢＢ(Bottom Boundary of the agent link)の概念を導入して説明する。代替経路はリンクまたはノードの問題の発生によって連結が切れた場合、切れた経路を代替してＴＢとＢＢを連結する経路を意味する。
【００３７】
また、ＴＢは図面においてノードＡを意味し、ＢＢは図３ではノードＣ、図４ではノードＦ、ノードＧ及びノードＪに該当する。ＴＢからＢＢへの連結が切れると、ＢＢは代替経路を介してＴＢとの連結を復旧する。
【００３８】
ノードがその上位ノードとの連結が切れたことを確認すれば、経路を復旧するために自分自身をＢＢ及びＳＮと定義し、その上位ノードをＴＢと定義し、ＴＴＬを設定して経路復旧の要求パケットをブロードキャスティングする。ここではＴＴＬを例えば"２"と設定する。ここで、ＴＴＬはＢＢからＴＢまでの代替経路の最大ホップ数を意味する。
【００３９】
図３ではノードＣが自分自身をＢＢ及びＳＮと定義しその上位ノードであるノードＡをＴＢと定義して、ノードＡへの代替経路を探すために経路復旧の要求パケットをブロードキャスティングする。経路復旧の要求パケットを受信すればノードＡはノードＣに経路復旧の応答パケットを伝送する。
【００４０】
一方、ＢＢは所定の時間(discovery time)中に経路復旧の応答パケットを伝送されなければ、ＴＴＬを"１"増やし、経路復旧の要求パケットを再びブロードキャスティングする。このような過程はＴＴＬの許容最大値(例えば"４")まで繰り返され、これまでの経路復旧の応答パケットを伝送されなければその上位ノードの故障などで上位ノードがネットワークに接続されないため連結が切れたものと判断する。従って、ノードはＳＮを自分自身ではなく上位ノードに変更し、ＴＢをＳＮの上位ノードに変更してＴＢへの代替経路を探すために経路復旧の要求パケットをブロードキャスティングする。
【００４１】
図４において、ノードＦ、ノードＧ及びノードＪはノードＣから経路復旧の応答パケットを伝送されないので、ノードＣに発生した問題によってノードＣがネットワークに接続が切れたことと判断して、ＳＮをノードＣに変更しＴＢをその上位ノードであるノードＡに変更して、ノードＡへの経路を探すために経路復旧の要求パケットをブロードキャスティングする。
【００４２】
一方、ＢＢからＴＢに経路復旧の要求パケットをブロードキャスティングする方法は２種がある。１つはＢＢからＴＢにノードを経由する度に常に経路復旧の要求パケットをブロードキャスティングする。この場合は、さらに多数のノードが代替経路を探すためにパケットをブロードキャスティングするようになって、ＴＢとＢＢの最短の代替経路を探せるようになる。
【００４３】
もう１つはＢＢがブロードキャスティングした経路復旧の要求パケットを受信したノードがＳＮが自分自身の上位ノードではないと判断する際、パケットを受信したノードは自分自身のネットワークのツリールーティング構造経路に沿ってユニキャストすることによってＴＢに経路復旧の要求パケットを伝送するものである。すなわち、パケットを受信したノードはＳＮの下位ノードではないため連結が切れなくてツリールーティング構造経路によるパケット伝送が可能である。この場合、トラフィックは減少するものの、代替経路の長さは多少延びる場合がある。
【００４４】
ＴＢが複数の経路復旧の要求パケットを受信すれば、ＳＮからのホップ数が最小の経路を遡って経路復旧の応答パケットをＢＢに伝送する。また、ＴＢは代替経路のための目録であるＳＮ目録で代替ノード名(Agent Name)、代替ＩＤ(Agent ID)、下位ノードＩＤ(Child ID of the failed node)を設定して自分自身が格納し（Store）、またこれを経路復旧の応答パケットに含めて選択された代替経路に沿って伝送する。
【００４５】
ここで、代替ノード名は１２ビット、代替ＩＤは４ビット、下位ノードＩＤ(故障したノードの下位ノード)は８ビットと定義することができ、代替ノード名はＴＢが該当代替ノード名を有するノードのために代替経路を設定することを意味し、ＳＮのアドレスを使用できる。代替ＩＤはＴＢの場合ＳＮまでのホップ数で表示し、ノード自身がＴＢとしてＳＮの上位ノードであることを意味する。また、ＢＢとＳＮが同一ならば下位ノードＩＤは８ビットの"００００００００"と設定し、これはＳＮがネットワークに接続中であることを意味する。一方、ＢＢとＳＮが相異なると、ＳＮに発生した問題によってネットワーク接続が切れたことを意味し、経路復旧の要求パケットがＳＮの下位ノード中の１つであるＢＢから伝送されたことが分かり、ＢＢのｎ番目の下位ノードについて下位ノードＩＤのｎ番目ビットを"１"と設定して各下位ノードを表示する。図４を参照すれば、ノードＦについて下位ノードＩＤを"１０００００００"と設定し、ノードＧについては"０１００００００"、ノードＪについては"００１０００００"と設定する。
【００４６】
ノードＡ(ＴＢ)から経路復旧の応答パケットを受信した代替経路上の各ノードは自分自身を代替経路上のノードと認識し、ＳＮ目録を生成したり更新したりする。ＳＮ目録生成又は更新において、経路復旧の応答パケットに含まれたＳＮ目録のうち代替ノード名を抽出してこれを代替ノード名で表示し、代替ＩＤは代替経路を構成するノード自身からＳＮまでのホップ数で表示する。ＳＮ目録を更新する場合ホップ数が現在の代替ＩＤより大きい場合は代替ＩＤを更新する。下位ノードＩＤはＢＢがＳＮのｎ番目下位ノードの場合ｎ番目ビットを"１"と設定する。従って、ＳＮとＢＢが同一なノードの場合、下位ノードＩＤは"００００００００"になる。
【００４７】
ＴＢがＢＢに経路復旧の応答パケットを伝送するための代替経路に対する情報は各ノードによって２種の方式で取得できる。
【００４８】
１つはＢＢから経路復旧の要求パケットがＴＢに伝送される際伝送経路を形成する各ノードが自分自身のアドレスを経路復旧の要求パケットに含ませるものである。この場合、各ノードは自分自身が直接に代替経路に対する情報を保存しなくても代替経路に対する情報が経路復旧の要求パケット及び経路復旧の応答パケットに含まれていて、これによりＴＢからＢＢへの経路復旧の要求パケットを伝送するようになる。
【００４９】
もう１つは、代替経路を構成する各ノードがＢＢとＴＢとの間の代替経路に対する情報を保存するものである。この場合、各ノードはＴＢのアドレス、ＢＢのアドレス、経路復旧の要求パケットのＩＤ及びＢＢから伝送された経路復旧の要求パケットを自分自身に伝送したノードのアドレス(すなわち、自分自身が経路復旧の応答パケットを伝送するノードのアドレス)を保存すべきである。
【００５０】
図５及び図６は本発明の更に他の実施例によって復旧された経路による通信の典型的な実行過程の説明に提供される図である。
【００５１】
図５において、ノードＡがノードＬにデータを伝送しようとする場合、１ホップ数の次番にあるノードＣにデータを伝送できないため、データパケットの代替アドレスを<Ｘ、１５、１０００００００>と設定し、RELAY=１と設定してデータをブロードキャスティングする。ここで、代替アドレスは前述したＳＮ目録で順番に<代替ノード名、代替ＩＤ、下位ノードＩＤ>と設定し、代替ノード名"Ｘ"はノードＣのアドレス、代替ＩＤはノードＡからノードＣまでの代替経路のホップ数であり、下位ノードＩＤはノードＬがノードＣの一番目下位ノードに従属されたノードであることを表示する。
【００５２】
図５においてノードＡがブロードキャスティングしたデータをノードＢ及びノードＨが受信するが、データパケットの下位ノードＩＤの一番目ビットだけが"１"であり、ノードＨの下位ノードＩＤの一番目ビットは"１"ではないため、ノードＢだけがデータパケットを再びブロードキャスティングする。同様に、ノードＢがブロードキャスティングしたデータパケットはノードＥが再びブロードキャスティングし、これをノードＦが再びブロードキャスティングして目的地であるノードＬがデータパケットを受信するようになる。
【００５３】
図６においてノードＦがノードＬにデータパケットを伝送しようとする場合、１ホップ距離の次番の上位ノードＣにデータを伝送できないことが分かると、データパケットの代替アドレスを<Ｘ、１、１０００００００>と設定し、RELAY=１と設定してデータをブロードキャスティングする。ここで、代替アドレスは前述したＳＮ目録で順番に<代替ノード名、代替ＩＤ、下位ノードＩＤ>と設定し、代替ノード名"Ｘ"はノードＣのアドレス、代替ＩＤはノードＦ自身はノードＣまでの既存のホップ数が"１"なので"１"と設定し、下位ノードＩＤはノードＦがノードＣの一番目下位ノードなので、一番目ビットを"１"と設定する。
【００５４】
図６においてノードＦがブロードキャスティングしたデータをノードＥ及びノードＪが受信するが、データパケットの下位ノードＩＤの一番目ビットだけが"１"であり、ノードＪの下位ノードＩＤの一番目ビットは"１"でないので、ノードＥだけがデータパケットを再びブロードキャスティングするようになる。同様に、ノードＥがブロードキャスティングしたデータパケットはノードＢが再びブロードキャスティングし、これをノードＡが既存のツリールーティング構造経路に沿って目的地であるノードＬにデータパケットを伝送するようになる。
【産業上の利用可能性】
【００５５】
本発明はツリールーティング無線ネットワークでネットワーク資源を節約し効率的なルーティング方法を提供して、ツリールーティング連結形態構造を有する無線ネットワークにおける通信に用いられる。
【図面の簡単な説明】
【００５６】
【図１】ツリールーティング連結形態構造を有する無線ネットワークの一例を示す図である。
【図２】本発明の一実施例によるツリールーティング構造経路復旧方法の説明に提供される図である。
【図３】本発明の他の実施例によるツリールーティング構造経路復旧方法の説明に提供される図である。
【図４】本発明の他の実施例によるツリールーティング構造経路復旧方法の説明に提供される図である。
【図５】本発明のさらに他の実施例によって復旧された経路による通信の典型的な実行過程に提供される図である。
【図６】本発明のさらに他の実施例によって復旧された経路による通信の典型的な実行過程に提供される図である。
【符号の説明】
【００５７】
１１０    ノードＡ
１２０    ノードＧ
１３０    ノードＫ
１４０    ノードＦ
【図１】
2005080316.tif 000003
【図２】
2005080316.tif 000004
【図３】
2005080316.tif 000005
【図４】
2005080316.tif 000006
【図５】
2005080316.tif 000007
【図６】
2005080316.tif 000008