(57)【要約】無線ネットワークでルーティング方法およびその方法を使用する通信装置が開示される。  本発明の無線ネットワークにおけるルーティング方法は、ツリー構造で形成された無線ネットワークにおけるルーティング方法において、隣接ノードに対する情報および隣接ノードの下位ノードに対する情報を受信して作成されたテーブルを利用し最適経路を獲得するステップと、最適経路を介してパケット伝送を行なうステップと、を含む。
2008541505.tif 000002
【特許請求の範囲】
【請求項１】
ツリー構造で形成された無線ネットワークにおけるルーティング方法であって、
隣接ノードに対する情報および前記隣接ノードの下位ノードに対する情報を受信して作成されたテーブルを利用し最適経路を獲得するステップと、
前記最適経路を介してパケット伝送を行なうステップと、
を含むことを特徴とする無線ネットワークにおけるルーティング方法。
【請求項２】
前記最適経路を獲得するステップは、前記テーブルに記録された前記最適経路を検索することによって前記最適経路を獲得することを特徴とする請求項１に記載の無線ネットワークにおけるルーティング方法。
【請求項３】
前記最適経路を獲得するステップは、前記パケットが受信されるべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致する場合、前記テーブルに記録された前記開始アドレスに対応する次のホップのアドレスを有するホップを介した経路を前記最適経路で獲得することを特徴とする請求項２に記載の無線ネットワークにおけるルーティング方法。
【請求項４】
前記最適経路を獲得するステップは、前記パケットを伝送すべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致する場合、前記テーブルに記録された前記開始アドレスに対応する次のホップのアドレスを有するホップを介した代替経路を前記最適経路で獲得することを特徴とする請求項２に記載の無線ネットワークにおけるルーティング方法。
【請求項５】
前記獲得された最適経路を前記パケットが伝送されるべきノードに伝送するステップと、
前記代替経路を介してパケットの伝送を行なうステップと、
を含むことを特徴とする請求項４に記載の無線ネットワークにおけるルーティング方法。
【請求項６】
前記隣接ノードに対する情報および前記隣接ノードの下位ノードに対する情報を受信して作成されたテーブルを利用し代替経路の獲得を行なうステップが更に含まれたことを特徴とする請求項１に記載の無線ネットワークにおけるルーティング方法。
【請求項７】
前記代替経路を獲得するステップは、前記パケットが受信されるべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致しない場合、前記ノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれたか否かを検索することによって、前記代替経路を獲得することを特徴とする請求項６に記載の無線ネットワークにおけるルーティング方法。
【請求項８】
前記代替経路を獲得するステップは、前記パケットの受信されるべきノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれる場合、前記テーブルに記録された前記開始アドレスに対応するノードおよび前記開始アドレスに対応するノードの下位ノードを介した経路を前記代替経路で獲得することを特徴とする請求項７に記載の無線ネットワークにおけるルーティング方法。
【請求項９】
前記代替経路を獲得するステップは、前記パケットを伝送すべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致しない場合、前記ノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれたか否かを検索することによって、前記代替経路を獲得することを特徴とする請求項６に記載の無線ネットワークにおけるルーティング方法。
【請求項１０】
前記代替経路を獲得するステップは、前記パケットを伝送すべきノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれた場合、前記テーブルに記録された前記開始アドレスに対応するノードおよび前記開始アドレスに対応するノードの下位ノードを介した経路を前記代替経路で獲得することを特徴とする請求項９に記載の無線ネットワークにおけるルーティング方法。
【請求項１１】
前記獲得された代替経路が前記パケットの伝送すべきノードへ伝送されるステップを更に含むことを特徴とする請求項９に記載の無線ネットワークにおけるルーティング方法。
【請求項１２】
前記最適経路を獲得するステップにおいて作成されたテーブルは、複数ノードのトポロジー情報を含んでいることを特徴とする請求項１に記載の無線ネットワークにおけるルーティング方法。
【請求項１３】
前記トポロジー情報は、前記ノードの開始アドレス、終了アドレス、次のホップアドレス、前記ノードの開始アドレスまでのホップ数、前記ノードの開始アドレスまでのコスト、および前記ノードが生成されるもしくはリフレッシュされる時間の少なくとも１つを含むことを特徴とする請求項１２に記載の無線ネットワークにおけるルーティング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークにおけるルーティング方法およびその方法を用いる通信装置に関し、詳細にはツリー基盤メッシュルーティング（ｔｒｅｅ−ｂａｓｅｄ  ｍｅｓｈ  ｒｏｕｔｉｎｇ）により効率よくデータを送受信することのできる無線ネットワークにおけるルーティング方法およびその方法を使用する通信装置に関する。
【背景技術】
【０００２】
一般に、ルーティング経路の設定のために用いられる無線ネットワークにおけるルートディスカバリーは１つのノードに対して行なわれる。最近、このような無線ネットワークはその領域内の全てのデバイスがクラスターツリー構造（ｃｌｕｓｔｅｒ  ｔｒｅｅ  ｓｔｒｕｃｔｕｒｅ）をなしていることがほとんどである。かかるクラスターツリー構造に編入（ｊｏｉｎ）する全てのデバイスはツリー構造によるアドレスが割り当てられるようになる。割り当てられたアドレスは各ネットワーク環境におけるルーティング時に用いられる。
【０００３】
図１は従来の無線ネットワークのツリー構造を示す図面である。
【０００４】
同図において、従来の無線ネットワークは親ノードＡ１１０と子ノードＢ〜Ｊ１１２〜１４２から形成されている。
【０００５】
ここで、子ノードＢ１１２は、親ノードＡ１１０の子ノードでありながらも、多数の子ノードＥ１２０、Ｆ１２２、Ｇ１２４の親ノードとなる。さらに、子ノードＣ１１４は、親ノードＡ１１０の子ノードでありながらＨ１３０の親ノードにもなる。そして、子ノードＤ１１６は、親ノードＡ１１０の子ノードでありながら子ノードＩ１４０、Ｊ１４２の親ノードにもなる。図１において、各ノードはデバイスで具現でき、各親ノードは自分に連結されている子ノードに対するアドレス情報のテーブルを有している。
【０００６】
ところで、図１の無線ネットワークにおいて、Ｈ１３０ノードからＦ１２２ノードにデータが伝送される場合、Ｈ１３０ノードはソースノードとなり、Ｆ１２２ノードは目的地ノードとなる。Ｈ１３０ノードから送出されたデータパケットはツリー構造に従ってＦ１２２ノードへ伝送されるので、データパケットがツリー構造に従って隣接ノードへ伝達されるためにも必ず親ノードを介して伝送されるべきである。
【０００７】
これによって、Ｈ１３０ノードから送出されたデータパケットはツリー構造に従ってＣ１１４ノード、Ａ１１０ノード、Ｂ１１２ノードを介してＦ１２２ノードへ伝送される。従って、従来の無線ネットワークにおけるツリー構造において、ソースノードから目的地ノードまでツリー構造に従ってデータパケットが伝送されることにより、ルーティング経路が長くなり、通信コストも上昇してしまう問題がある。
【特許文献１】韓国公開特許２００４−０９６４１８号
【特許文献２】韓国公開特許２００４−０９５１５２号
【特許文献３】米国特許８，４８０，５０２号
【特許文献４】日本公開特許１９９９−３５５３３７号
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は前述した問題点を解決するために案出されたもので、本発明の目的は、無線ネットワークにおいてソースノードから目的地ノードまでの効果的な経路の検索および設定を可能とするツリー基盤のメッシュルーティングに係るルーティング方法を提供することにある。
【課題を解決するための手段】
【０００９】
前述した目的を達成するための本発明に係る無線ネットワークにおけるルーティング方法は、ツリー構造で形成された無線ネットワークにおけるルーティング方法において、隣接ノードに対する情報および前記隣接ノードの下位ノードに対する情報を受信して作成されたテーブルを利用し最適経路を獲得するステップと、前記最適経路を介してパケット伝送を行なうステップと、を含むことを特徴とする。
【００１０】
好ましくは、前記最適経路を獲得するステップは、前記テーブルに記録された前記最適経路を検索することによって前記最適経路を獲得する。つまり、前記パケットが受信されるべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致する場合、前記テーブルに記録された前記開始アドレスに対応する次のホップのアドレスを有するホップを介した経路を前記最適経路で獲得することを特徴とする。
【００１１】
さらに、前記最適経路を獲得するステップは、前記パケットを伝送すべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致する場合、前記テーブルに記録された前記開始アドレスに対応する次のホップのアドレスを有するホップを介した代替経路を前記最適経路で獲得することが好ましい。
【００１２】
また、前記獲得された最適経路を前記パケットが伝送されるべきノードに伝送するステップと、前記代替経路を介してパケットの伝送を行なうステップと、を含むことが好ましい。
【００１３】
また、本発明に係る無線ネットワークにおけるルーティング方法は、前記隣接ノードに対する情報および前記隣接ノードの下位ノードに対する情報を受信して作成されたテーブルを利用し代替経路の獲得を行なうステップが更に含まれたことが好ましい。
【００１４】
また、前記代替経路を獲得するステップは、前記パケットが受信されるべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致しない場合、前記ノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれたか否かを検索することによって、前記代替経路を獲得することを特徴とする。
【００１５】
また、前記代替経路を獲得するステップは、前記パケットの受信されるべきノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれる場合、前記テーブルに記録された前記開始アドレスに対応するノードおよび前記開始アドレスに対応するノードの下位ノードを介した経路を前記代替経路で獲得することが好ましい。
【００１６】
また、前記代替経路を獲得するステップは、前記パケットを伝送すべきノードのアドレスと前記テーブルに記録された開始アドレスのうちいずれか１つとが一致しない場合、前記ノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれたか否かを検索することによって、前記代替経路を獲得することが好ましい。
【００１７】
さらに、前記代替経路を獲得するステップは、前記パケットを伝送すべきノードのアドレスが前記テーブルに記録された開始アドレスに「１」を加えたアドレスと前記開始アドレスに対応する終了アドレスの範囲に含まれた場合、前記テーブルに記録された前記開始アドレスに対応するノードおよび前記開始アドレスに対応するノードの下位ノードを介した経路を前記代替経路で獲得することが好ましい。
【００１８】
ここで、前記獲得された代替経路が前記パケットの伝送すべきノードへ伝送されるステップを更に含むことを特徴とする。
【００１９】
また、前記最適経路を獲得するステップにおいて作成されたテーブルは、複数ノードのトポロジー情報を含んでいることを特徴とする。ここで、前記トポロジー情報は、前記ノードの開始アドレス、終了アドレス、次のホップアドレス、前記ノードの開始アドレスまでのホップ数、前記ノードの開始アドレスまでのコスト、および前記ノードが生成されるもしくはリフレッシュされる時間の少なくとも１つを含むことが好ましい。
【発明の効果】
【００２０】
本発明によると、ブロック単位でルートディスカバリーを行なうツリー基盤のメッシュルーティングが用いられることによって、ルートディスカバリーの効率が増加する。また、最適経路でパケット伝送を行なうことによって通信コストの減少が図れる。
【００２１】
さらに、ＮＴＴ（Ｎｏｎ−Ｔｒｅｅ、Ｔａｂｌｅ）に記録された代替経路を用いることによって、ソースノードと目的地ノードおよび目的地ノードの下位ノード間のパケット伝送時ルートディスパバリーを使用せずに済むので、ルートディスカバリーによるオーバーヘッドが最小化される。
【発明を実施するための最良の形態】
【００２２】
以下、添付の図面に基づいて本発明の最適な実施形態を詳述する。
[実施形態]
【００２３】
本発明にかかる無線ネットワークにおけるルーティング方法は、ツリー基盤のルーティング方法であるＡＲＴ（Ａｄａｐｔｉｖｅ  Ｒｏｂｕｓｔ  Ｔｒｅｅ）、ＭＡＲＴ（Ｍｅｓｈｅｄ  ＡＲＴ）と非ツリー基盤によるルーティング方法（Ｎｏｎ-Ｔｒｅｅ  Ｒｏｕｔｉｎｇ）を全て使用する。このとき、ルーティング時に用いられる各ノードは両方向通信である。
【００２４】
図２は、本発明の一実施形態に係る無線ネットワークにおけるアドレス割り当て方法を説明するためのフローチャートである。図２を参照すると、まず、初期化ステップとして、複数のノードが相互連結されているクラスターツリー構造を形成する（Ｓ２１０）。詳細には、最上位ノード（Ｒｏｏｔ）であるノードＡで連結が開始されると、隣接ノードがノードＡに対して接続要請メッセージを伝送する。ノードＡは接続要請の伝送したノードと接続すべきであれば応答メッセージを伝送する。これによって、ノードＡと各ノード間の連結が行なわれるのである。各ノードに対しても同様な方式に基づいて下位ノードが連結される。
【００２５】
このような方式でクラスターツリー構造が形成されると、最下位レベルないし次上位レベルに属する各ノードが、最下位レベルから次上位レベルの順で自分の上位ノードに対して所定サイズのアドレスブロックを要請する（Ｓ２２０）。
【００２６】
一方、アドレスブロックサイズの通知されたノードは、自分の最上位レベルに属するか否かを判断し（Ｓ２３０）、最上位レベルに属していなければ再度自分の上位ノードについて自分が使用したいアドレスブロックのサイズを通知する（Ｓ２４０）。
【００２７】
最上位ノード（Ｒｏｏｔ）は、各ブランチについて要請されたサイズのアドレスブロックを割り当てる（Ｓ２５０）。この場合、各ブランチに対応する下位ノードの連結順に従って順次割り当てられる。
【００２８】
このとき、各下位ノードは自分が最下位レベルに属していなければ（Ｓ２６０）、自分が割り当てられたアドレスブロックを自分の下位ノードについて再度割り当てる（Ｓ２７０）。この場合、自分の下位ノードが要請したサイズのアドレスブロックを順次割り当てる。これによって、最下位レベルに属する各ノードに到るまでアドレスが割り当てられるようになり、結果的に各ノードは自分に割り当てられたアドレスを用いてＡＲＴＴ（Ａｄａｐｔｉｖｅ  Ｒｏｂｕｓｔ  Ｔｒｅｅ  Ｔａｂｌｅ）が作成され、これによりルーティング動作を行なう。なお、ＡＲＴＴはトポロジー情報を含んでいる。
【００２９】
図３は本発明の一実施の形態に係る無線ネットワークにおけるルートディスカバリー過程を説明するための図面、図４Ａおよび図４Ｂには本発明に係るルーティング経路設定に用いられるＲＲＥＱ（Ｒｏｕｔｅ  Ｒｅｑｕｅｓｔ）およびＲＲＥＰ（Ｒｏｕｔｅ  Ｒｅｐｌｙ）が例示されている。
【００３０】
図３、図４Ａおよび図４Ｂを参照すると、例えば、ソースノードＩから目的地ノードＯにパケット伝送を行なう場合、ソースノードＩは目的地ノードＯと経路設定のために目的地ノードＯに向かってＲＲＥＱをユニキャスト伝送する。つまり、ＲＲＥＱが伝送されるルーティング経路は、Ｉ−Ｈ−Ｋ−Ｏとなる。ここで、ＲＲＥＱは、ソースノードが目的地ノードを検索するため、即ち、経路生成を求めるために使用しているメッセージタイプである。
【００３１】
図４Ａに示すように、ＲＲＥＱは、ルートタイプ（ｒｏｕｔｅ＿ｔｙｐｅ）、目的地ノードの開始アドレス（ｄｓｔ＿ｂｅｇ＿ａｄｄｒ）、ソースノードの開始アドレス（ｓｒｃ＿ｂｅｇ＿ａｄｄｒ）、ソースノードの終了アドレス（ｓｒｃ＿ｅｎｄ＿ａｄｄｒ）、最大リンクコスト（ｍａｘ＿ｌｉｎｋ＿ｃｏｓｔ）、ホップ数（ｈｏｐｓ＿ｔｒａｖｅｌｅｄ）、蓄積コスト（ｃｏｓｔ＿ａｃｃｕｍｅｄ）、およびＴＴＬを収録している。ＲＲＥＱの各フィールドに対する説明は図４Ａで示す通りである。
【００３２】
目的地ノードＯがソースノードＩから伝送したＲＲＥＱを受信すると，目的地ノードＯはソースノードＩまでの最適経路を検索するためにＲＲＥＱをブロードキャストする。
【００３３】
すると、ソースノードＩが目的地ノードＯからブロードキャストされ受信されたＲＲＥＱを受信することにより、目的地ノードＯまでの最適経路を検索することができる。従って、ソースノードＩは最適経路で目的地ノードＯまでのＲＲＥＰを伝送する。つまり、ソースノードＩから目的地ノードＯへＲＲＥＰの伝送される最適経路はＩ−Ｌ−Ｏとなる。なお、ソースノードＩと目的地ノードＯは互いに経路情報の交換が可能であるので、目的地ノードＯもソースノードＩへの最適経路が分かる。
【００３４】
ここで、ＲＲＥＰ（Ｒｏｕｔｅ  Ｒｅｐｌｙ）はＲＲＥＱに対する応答メッセージである。図４Ｂに示すように、ＲＲＥＰはルートタイプ（ｒｏｕｔｅ＿ｔｙｐｅ）、目的地ノードの開始アドレス（ｄｓｔ＿ｂｅｇ＿ａｄｄｒ）、目的地ノードの終了アドレス（ｄｓｔ＿ｅｎｄ＿ａｄｄｒ）、ソースノードの開始アドレス（ｓｒｃ＿ｂｅｇ＿ａｄｄｒ）、ソースノードの終了アドレス（ｓｒｃ＿ｅｎｄ＿ａｄｄｒ）、ホップ数（ｈｏｐｓ＿ｔｒａｖｅｌｅｄ）、総ホップ数（ｈｏｐ＿ｔｏｔａｌ）、蓄積コスト（ｔｏｔａｌ＿ｃｏｓｔ）、総コスト（ｔｏｔａｌ＿ｃｏｓｔ）、およびＴＴＬを収録している。ＲＲＥＰの各フィールドに対する説明は図４Ｂに示す通りである。
【００３５】
さらに、目的地ノードＯからブロードキャストされたＲＲＥＱを受信することによってソースノードＩは目的地ノードＯの下位ノードへの経路も検索することができる。
【００３６】
より具体的には、ブロードキャストされたＲＲＥＱには目的地ノードＯの開始アドレス（ｂｅｇ＿ａｄｄｒ）および終了アドレス（ｅｎｄ＿ａｄｄｒ）などの情報が含まれている。これによりソースノードＩは目的地ノードＯの下位ノードへの代替経路（Ａｕｘｉｌｌｉａｒｙ  Ｒｏｕｔｅ）を探すことができる。ここで、代替経路とは、ソースノードから目的地ノードへの最適経路ではない次先経路のことを指す。
【００３７】
図５には図３のルートディスカバリー過程で作成されたＮＴＴ（Ｎｏｎ−Ｔｒｅｅ−Ｔａｂｌｅ）が図示されている。
【００３８】
同図に示すように、各ノードはＲＲＥＱおよびＲＲＥＰを用いたルートディスカバリーを介して各ノード間の最適経路および代替経路を記録するＮＴＴを作成し、作成されたＮＴＴはルーティング動作に用いられる。なお、各ノードは自分のＮＴＴに記録された情報を参照して最適経路および代替経路を検索し、各ノードは検索された経路によりルーティング動作を行なう。ここで、ＮＴＴに記録された開始アドレス（ｂｅｇ＿ａｄｄｒｉ）がノードｉの最適経路であり、代替経路はノードｉの開始アドレスに１を加えたアドレス（ｂｅｇ＿ａｄｄｒｉ+１）から終了アドレス（ｅｎｄ＿ａｄｄｒｉ）までとなる。
【００３９】
図６は本発明に係るルートディスカバリーを行なった後のソースノードと目的地ノード間のルーティング経路の設定方法を説明するための図面である。
【００４０】
同図に示すように、最初、ソースノードはルートディスカバリーの際に生成された自分のＮＴＴに目的地ノードへの最適経路が記録されているか否かを検索する（Ｓ６１０）。
【００４１】
つまり、ソースノードは、パケットを伝送したい目的地ノードのアドレスがソースノードのＮＴＴに記録された開始アドレス（ｂｅｇ＿ａｄｄｒ）のいずれか１つと一致するか否かを検索する。なお、目的地ノードのアドレスがソースノードのＮＴＴに記録された開始アドレス（ｂｅｇ＿ａｄｄｒ）であれば、ソースノードは目的地ノードへの最適経路が記録されていると判断する。
【００４２】
もし、ＮＴＴに目的地ノードへの最適経路が記録されていなければ、ソースノードは初期ツリー形成時に生成されたＡＲＴＴに目的地ノードへの最適経路が記録されているか否かを検索する（Ｓ６２０）。即ち、ソースノードは自分のＡＲＴＴに記録された開始アドレス（ｂｅｇ＿ａｄｄｒ）のうちいずれか１つと目的地ノードのアドレスとが一致するかを検索する。この時、目的地ノードのアドレスがソースノードのＡＲＴＴに記録された開始アドレス（ｂｅｇ＿ａｄｄｒ）であれば、ソースノードは目的地ノードへの最適経路が記録されたと判断する。
【００４３】
一方、ＡＲＴＴに目的地ノードへの最適経路が記録されていなければ、ソースノードはＮＴＴに目的地ノードへの代替経路が記録されているか否かを検索する（Ｓ６３０）。
【００４４】
より具体的には、ソースノードのＮＴＴおよびＡＲＴＴの開始アドレス（ｂｅｇ＿ａｄｄｒ）のいずれか１つと目的と地ノードのアドレスとが一致していなければ、ソースノードは自分のＮＴＴから目的地ノードへの代替経路が記録されているか否かを検索する。つまり、ソースノードは目的地ノードのアドレスがソースノードのＮＴＴに記録された開始アドレスに１を加えたアドレス（ｂｅｇ＿ａｄｄｒｉ+１）から終了アドレス（ｅｎｄ＿ａｄｄｒｉ）の範囲に含まれるか否かを検索する。当範囲内に目的地ノードのアドレスが存在すれば、ソースノードは自分のＮＴＴに目的地ノードへの代替経路が記録されていると判断する。
【００４５】
ここで、Ｓ６１０、Ｓ６２０、あるいはＳ６３０において、目的地ノードへの最適経路および代替経路が検索されると、ソースノードは目的地ノードまで検索された最適経路および代替経路でパケットの伝送を行なう（Ｓ６４０）。
【００４６】
詳細には、Ｓ６１０において、ＮＴＴに目的地ノードへの最適経路が記録されていれば、ソースノードは目的地ノードまでＮＴＴに記録された最適経路でパケット伝送を行なう。つまり、ソースノードはＳ６１０で検索された開始アドレスに対応する次のホップアドレスを有するホップを介した経路を最適経路にしてパケット伝送を行なう。
【００４７】
一方、Ｓ６１０において、ＮＴＴに目的地ノードへの最適経路が記録されていなければ、Ｓ６３０のようにＡＲＴＴに最適経路が記録されているかを検索し、ＡＲＴＴに目的地ノードへの最適経路が記録されていれば、ソースノードは目的地ノードまでＡＲＴＴに記録された最適経路へのパケット伝送を行なう。
【００４８】
Ｓ６２０において、ＡＲＴＴに最適経路が記録されていなければ、Ｓ６３０のようにソースノードはＮＴＴに代替経路が記録されているかを検索し、代替経路が記録されていれば、ソースノードは目的地ノードまでＮＴＴに記録された代替経路でパケット伝送を行なう。
【００４９】
次に、ＡＲＴＴおよびＮＴＴに目的地ノードへの最適経路および代替経路のいずれか１つが記録されていなければ、ソースノードはツリー経路を用いる（Ｓ６５０）。
【００５０】
より具体的には、ソースノードＩから目的地ノードＯにパケット伝送を行なう場合を例にすると、ソースノードＩは自分のＮＴＴおよびＡＲＴＴに最適経路および代替経路が記録されていなければ、ソースノードＩは初期にアドレス割り当て時に生成されたツリー経路（ＡＲＴ／ＭＡＲＴ）を用いて目的地ノードＯまでパケット伝送を行なう。つまり、ソースノードＩからパケット伝送を行なうルーティング経路はＩ−Ｈ−Ｋ−Ｏとなる。
【００５１】
なお、Ｓ６５０において、ＡＲＴＴおよびＮＴＴに目的地ノードへの最適経路および代替経路のいずれか１つも記録されていなければ、ソースノードはルートディスカバリーを再度行なうことによって目的地ノードへの最適経路をＮＴＴに記録することができる。
【００５２】
一方、本発明に係る無線ネットワークにおけるルーティング方法において、Ｓ６１０〜Ｓ６５０におけるソースノードと目的地ノード間の最適経路設定の手続きはソースノードだけでなく、目的地ノードにおいても行なうことができる。
【００５３】
より具体的には、ソースノードにおいて、Ｓ６１０〜Ｓ６５０を行なうことにおいて、ソースノードで最適経路にパケット伝送が行なわれない場合、目的地ノードはＳ６１０〜Ｓ６５０を行なって最適経路および代替経路を介してソースノードにパケット伝送を行なうことができる。
【００５４】
つまり、目的地ノードは目的地ノードのＮＴＴおよびＡＲＴＴに最適経路および代替経路が記録されているかを検索する。目的地ノードのテーブルに最適経路および代替経路が存在すれば、検索された経路にソースノードまでにパケット伝送が行なわれる。この時、最適経路および代替経路が検索されなければ、目的地ノードはＳ６５０で説明したように、目的地ノードからソースノードへのパケット伝送にツリー経路およびルートディスカバリーのいずれか１つを用いる。
【００５５】
図７Ａおよび図７Ｂには、図６の本発明に係るルーティング方法を詳細に説明するため提供される図面である。図７Ａはルートディスカバリーが行なわれた後、「ソースノード」から既に「目的地ノード」への最適経路を知っている場合のルーティング方法を説明するための図面である。ここで最適経路を知らない場合とは、ＮＴＴおよびＡＲＴＴに「目的地ノード」または「ソースノード」への最適経路および代替経路が記録されていない場合を指す。
【００５６】
図７Ａを参照すると、ソースノードＦから目的地ノードＩにパケット伝送を行なう場合について説明すると、ソースノードＦは自分のＮＴＴに目的地ノードＩへの最適経路が記録されているか否かを検索する。ルートディスカバリーを行なうときに生成されたソースノードＦのＮＴＴには既に目的地ノードＩへの最適経路が記録されていることから、ソースノードＦからパケット伝送を行なうルーティング経路はＦ−Ｇ−Ｉとなる。
【００５７】
より具体的には、ソースノードＦと目的地ノードＩは互いにツリー連結されていないが、ソースノードＦは隣接ノードＧを用いて目的地ノードＩまで最適経路でパケット伝送を行なうことができる。ノードＧは自分の隣接ノードＦとＩから隣接ノードＦとＩの下位ノードに対する情報をやり取りする。つまり、ノードＧは自分がノードＥおよびノードＦと接続されていることを知らせる情報をノードＩへ提供し、ノードＩは自分がノードＬおよびノードＭと接続されていることを知らせる情報をノードＧに提供する。これにより、ソースノードＦは目的地ノードＩまでＮＴＴに記録された最適経路Ｆ−Ｇ−Ｉを用いてパケット伝送を行なうことができる。
【００５８】
図７Ｂは、ルートディスカバリーを行なってから「目的地ノード」にて既に「ソースノード」への最適経路を知っている場合におけるルーティング方法を説明するための図面である。
【００５９】
同図に示すように、ソースノードＦから目的地ノードＩへのパケット伝送を行なう場合について説明すると、ソースノードＦは自分のＡＲＴＴおよびＮＴＴに目的地ノードＩへの最適経路および代替経路が記録されているかどうかを検索する。なお、ソースノードＦのＡＲＴＴおよびＮＴＴには目的地ノードＩへの最適経路および代替経路が記録されていない。これに、ソースノードＦは目的地ノードＩにＲＲＥＱをユニキャストで伝送する。
【００６０】
一方、ＲＲＥＱを受信した目的地ノードＩはソースノードＦへの最適経路を知っている。つまり、目的地ノードＩのＮＴＴには、ソースノードＦへの最適経路が記録されている。これにより、目的地ノードＩはソースノードＦまでに最適経路を用いてＲＲＥＰを伝送する。ここで、ＲＲＥＰが伝送されるルーティング経路はＩ−Ｇ−Ｆとなる。なお、目的地ノードＩはソースノードＦに目的地ノードＩからソースノードＦまでの最適な経路情報を提供する。これにより、ソースノードは目的地ノードへの最適経路が分かり、ソースノードは目的地ノードまでの最適経路でパケット伝送を行なうことができる。
【００６１】
即ち、ソースノードおよび目的地ノードのいずれか１つのＮＴＴおよびＡＲＴＴに各ノードへの最適経路が記録されていれば、ルートディスカバリーを再度行なうことなく、目的地ノードがソースノードに最適経路の情報提供を行なうことによりパケットが最適経路で伝送され得る。
【００６２】
図８Ａおよび図８Ｂは、本発明の一実施の形態にかかる無線ネットワークにおいてノード間の接続が途切れる場合に復旧過程を説明するための図面である。
【００６３】
図８Ａを参照すると、ノードＫに問題が発生し（ｂｒｏｋｅｎ）、ソースノードＣが目的地ノードＭにパケット伝送を行なう場合について説明すると、まず、ソースノードＣは目的地ノードＭに経路（Ｃ−Ｂ−Ｊ−Ｋ−Ｌ−Ｍ）を介してパケット伝送を行なう。この時、ノードＫに問題が生じてノードＪとノードＫ間の接続が途切れてしまうことによりソースノードＣから伝送されたパケットは目的地ノードＭに受信されない。
【００６４】
ノードＫに問題が発生したことを探知したノードＪは、自分の下位ノードにＲＲＥＱをブロードキャストする。ノードＪは自分の下位ノードからＲＲＥＰを受信することによってノードＪとノードＫの下位ノード間の連結を復旧する。なお、ノードＪは目的地ノードＭの上位ノードであるノードＩとノードＬのいずれか１つからＲＲＥＰを先に受信すると、目的地ノードＭへの連結を復旧する。
【００６５】
つまり、ノードＪが目的地ノードＭの上位ノードＩとＬのうちノードＩよりノードＬからＲＲＥＰが先に受信された場合に、ノードＪはノードＬと目的地ノードＭへの連結を復旧する。ここで、ノードＬはツリー内で自分の親ノードをＫからＨに変えて記録する。つまり、ノードＬの親ノードは問題の発生したノードＫの代わりに新たに連結されたノードＨとなる。
【００６６】
さらに、ノードＪが自分の下位ノードからＲＲＥＰを受信する場合に、ノードＪはＲＲＥＰを伝送したノードのうちノードＫと最も隣接したノードをルーティング経路として選択して目的地ノードへの連結を復旧することができる。つまり、ノードＪがノードＩとノードＬからＲＲＥＰを受信した場合に、ノードＪはノードＫと最も隣接したノードであるノードＬをルーティング経路として選択して目的地ノードＭへの連結を復旧することができる。
【００６７】
一方、図８Ｂを参照すると、ノードＪはノードＫに問題があることを探知した時、ノードＫの下位ノードでのみＲＲＥＰを受信して目的地ノードＭまでの連結を復旧することができる。つまり、ノードＪの全ての下位ノードからＲＲＥＰを受信する代わりにノードＫの下位ノードであるノードＬでのみＲＲＥＰを受信し目的地ノードＭおよびＫの下位ノードへの連結を復旧することができる。
【００６８】
以上、添付図面を参照しながら本発明の最適な実施形態について説明したが、本発明は係る例に限定されない。当業者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【図面の簡単な説明】
【００６９】
【図１】従来の無線ネットワークのツリー構造を示す図面である。
【図２】本発明の一実施の形態に係る無線ネットワークにおけるアドレス割り当て方法を説明するためのフローチャートである。
【図３】本発明の一実施の形態に係る無線ネットワークにおけるルートディスカバリー過程を説明するための図面である。
【図４】本発明に係るルーティング経路設定に用いられるＲＲＥＱを例示した図面である。
【図５】本発明に係るルーティング経路設定に用いられるＲＲＥＰを例示した図面である。
【図６】図３のルートディスカバリー過程で作成されたＮＴＴ（Ｎｏｎ−Ｔｒｅｅ−Ｔａｂｌｅ）を例示した図面である。
【図７】本発明に係るルートディスカバリーを行なってからソースノードと目的地ノード間のルーティング経路設定方法を説明するための図面である。
【図８】本発明に係るルートディスカバリーを行なってから「ソースノード」から既に「目的地ノード」への最適経路が分かっている場合のルーティング方法を説明するための図面である。
【図９】本発明に係るルートディスカバリーを行なってから「目的地ノード」から既に「ソースノード」への最適経路が分かっている場合のルーティング方法を説明するための図面である。
【図１０】本発明の一実施の形態に係る無線ネットワークでノード間の接続が途切れた場合に復旧する過程を説明するための図面である。
【図１１】本発明の一実施の形態に係る無線ネットワークでノード間の接続が途切れた場合に復旧する過程を説明するための図面である。
【符号の説明】
【００７０】
１１０  親ノードＡ
１１２  子ノードＢ
１１４  子ノードＣ
１１６  子ノードＤ
１２０  子ノードＥ
１２２  子ノードＦ
１２４  子ノードＧ
１３０  子ノードＨ
１４０  子ノードＩ
１４２  子ノードＪ
【図１】
2008541505.tif 000003
【図２】
2008541505.tif 000004
【図３】
2008541505.tif 000005
【図４】
2008541505.tif 000006
【図５】
2008541505.tif 000007
【図６】
2008541505.tif 000008
【図７】
2008541505.tif 000009
【図８】
2008541505.tif 000010
【図９】
2008541505.tif 000011
【図１０】
2008541505.tif 000012
【図１１】
2008541505.tif 000013
【国際調査報告】
2008541505.tif 000014
2008541505.tif 000015