(57)【要約】【課題】  モバイルアドホックネットワーク環境でのマルチキャストルーティング方法を提供する。【解決手段】  ソースノードが目的ノードに伝送するデータが存在する場合、所定の方式によってデータ伝送のための制御パケットが前記ソースノードから目的ノードに伝えられる（ａ）ステップと、制御パケットが伝えられるパス上にあるノードについての情報がツリー構造で形成される（ｂ）ステップと、ソースノードが形成されたツリー構造を利用して目的ノードにデータを伝送する（ｃ）ステップとを含む。【選択図】      図１
2007104675.tif 000002
【特許請求の範囲】
【請求項１】
モバイルアドホックネットワーク環境において、
ソースノードが目的ノードに伝送するデータが存在する場合、所定の方式によってデータ伝送のための制御パケットが前記ソースノードから前記目的ノードに伝えられる（ａ）ステップと、
前記制御パケットが伝えられるパス上にあるノードについての情報がツリー構造で形成される（ｂ）ステップと、
前記ソースノードが前記形成されたツリー構造を利用して前記目的ノードに前記データを伝送する（ｃ）ステップと、を含むマルチキャストルーティング方法。
【請求項２】
前記（ａ）ステップは、
前記ソースノードが前記制御パケットを伝送するステップと、
所定のフラッディング方式によって前記制御パケットが複数のノードを経て前記目的ノードに伝えられるステップと、を含む請求項１に記載のマルチキャストルーティング方法。
【請求項３】
前記制御パケットは、前記ソースノードから１ホップブロードキャスト方式によって伝送される請求項２に記載のマルチキャストルーティング方法。
【請求項４】
前記フラッディング方式は、ＭＰＲフラッディング方式を含む請求項２に記載のマルチキャストルーティング方法。
【請求項５】
前記（ｂ）ステップは、
前記目的ノードが自身の存在を知らせるパケットを伝送するステップと、
前記目的ノードから伝送されたパケットを利用して、前記ソースノードと前記目的ノードとの間に前記制御パケットが伝えられるパス上にあるノードが、自身の子ノードと親ノードについての情報を保存するステップと、
前記保存された情報からツリー構造が形成されるステップと、を含む請求項１に記載のマルチキャストルーティング方法。
【請求項６】
前記（ｃ）ステップは、前記目的ノードに伝送されるデータが遺失された場合、前記遺失されたデータを復元するステップをさらに含む請求項１に記載のマルチキャストルーティング方法。
【請求項７】
前記遺失されたデータを復元するステップは、
子ノードが遺失されたデータを識別する識別情報を親ノードに伝送するステップと、
前記親ノードが前記識別情報に該当するデータパケットを前記子ノードに伝送するステップと、を含む請求項６に記載のマルチキャストルーティング方法。
【請求項８】
前記親ノードが前記識別情報に該当するデータパケットを持っていない場合、前記親ノードは自身の親ノードに前記識別情報を伝送して、前記識別情報に該当するデータパケットを要請するステップを含む請求項７に記載のマルチキャストルーティング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルーティングプロトコルに係り、さらに詳細には、モバイルアドホックネットワーク環境において、マルチキャスト方式によるルーティング方法に関する。
【背景技術】
【０００２】
モバイルアドホックネットワークは、無線モバイル機器間に一時的なネットワークを形成して各無線モバイル機器間の通信を目的として設計され、既存の有線ネットワークとは多くの差異点がある。
【０００３】
この時、前記無線モバイル機器は移動性を持ち、多様な形態のデータを送受信する機能を提供するが、以下では、前記無線モバイル機器を‘ノード’と称する。
【０００４】
モバイルアドホックネットワーク環境で、各ノードがデータを伝送する方法には、特定の一つのノードに対してのみデータを伝送するユニキャスト方法と、グルーピングされた複数のノードに対してデータを伝送するマルチキャスト方法、そして、特定のノードまたは特定のグループを指定せずにモバイルアドホックネットワークに属するあらゆるノードに対してデータを伝送するブロードキャスト方法がある。
【０００５】
このうち、モバイルアドホックネットワーク環境において、現在提案されたマルチキャストルーティングプロトコルには、ＭＡＯＤＶ（Ｍｕｌｔｉｃａｓｔ  Ａｄ−ｈｏｃ  Ｏｎ−ｄｅｍａｎｄ  Ｄｉｓｔａｎｃｅ  Ｖｅｃｔｏｒ）、ＯＤＭＲＰ（Ｏｎ−ｄｅｍａｎｄ  Ｍｕｌｔｉｃａｓｔ  Ｒｏｕｔｉｎｇ  Ｐｒｏｔｏｃｏｌ）、ＭＯＬＳＲ（Ｍｕｌｔｉｃａｓｔ  ｅｘｔｅｎｓｉｏｎ  ｆｏｒ  ｔｈｅ  Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ  ｐｒｏｔｏｃｏｌ）などがあり、このようなプロトコルはフラッディング（ｆｌｏｏｄｉｎｇ）方式を利用している。
【０００６】
しかし、無線という特異な状況のために、データを最初に伝送するノード（以下、‘ソースノード’と称する）が増加するか、複数のノードで構成されたノードの集合（以下、‘グループ’と称する）の数が増えるにつれて多くの制御情報を失ってしまい、データパケットの伝送率が急激に低下する。
【０００７】
特に、ＯＤＭＲＰの場合は、フラッディング（ｆｌｏｏｄｉｎｇ）方式と類似して、制御パケットに対するオーバーヘッドとネットワーク帯域幅の使用量が増加する。
【特許文献１】米国公開特許２００２−１４５９７８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、モバイルアドホックネットワーク環境で、効果的かつ安定したマルチキャストルーティング方法を提供することを目的とする。
【０００９】
本発明は、モバイルアドホックネットワーク環境でソースノードの数が増加するか、グループの数が増加するとしても、効果的かつ信頼すべきマルチキャストルーティング方法を提供することを目的とする。
【００１０】
本発明の目的は、以上で言及した目的に制限されず、言及されていない他の目的は下の記載から当業者に明確に理解されうる。
【課題を解決するための手段】
【００１１】
前記目的を達成するために、モバイルアドホックネットワーク環境での本発明の実施形態によるマルチキャストルーティング方法は、ソースノードが目的ノードに伝送するデータが存在する場合、所定の方式によってデータ伝送のための制御パケットが前記ソースノードから前記目的ノードに伝えられる（ａ）ステップと、前記制御パケットが伝えられるパス上にあるノードについての情報がツリー構造で形成される（ｂ）ステップと、前記ソースノードが前記形成されたツリー構造を利用して前記目的ノードに前記データを伝送する（ｃ）ステップと、を含む。
【００１２】
その他の実施例の具体的な事項は詳細な説明及び図面に含まれている。
【発明の効果】
【００１３】
本発明によれば、モバイルアドホックネットワーク環境でソースノードがマルチキャスト方式によりデータを伝送する場合、制御パケットに対するオーバーヘッドが減少する。
【００１４】
また、本発明によれば、ソースノード及びグループの数が増加するとしても安定的にマルチキャスト方式によるデータ伝送を行える。
【発明を実施するための最良の形態】
【００１５】
本発明の利点及び特徴、そしてこれを達成する方法は添付された図面に基づいて詳細に後述されている実施例を参照すれば明確になる。しかし、本発明は以下で開示される実施例に限定されるものではなく、この実施例から外れて多様な形に具現でき、本明細書で説明する実施例は本発明の開示を完全にし、本発明が属する技術分野で当業者に発明の範ちゅうを完全に報せるために提供されるものであり、本発明は請求項及び発明の詳細な説明により定義されるだけである。一方、明細書全体に亙って同一な参照符号は同一な構成要素を示す。
【００１６】
一方、本発明では、モバイルアドホックネットワークシステムに属する任意のノードは、前記モバイルアドホックネットワークシステムに属する他の任意のノードを知っていると仮定する。
【００１７】
図１は、本発明の一実施形態によるモバイルアドホックネットワークシステムを示す例示図であって、本発明によるマルチキャストルーティング方法を、図１に示すシステム１００を中心として説明する。
【００１８】
モバイルアドホックネットワーク環境で、ソースノード（１番ノード）１１０が特定のグループに属するノード１２０、１３０、１４０に対してデータパケットを伝送しようとする場合には、前記ネットワークでは、本発明の実施によるマルチキャストルーティング方法によりソースノード１１０により伝送されたデータパケットが前記グループ内に属するノード１２０、１３０、１４０に伝えられることができる。
【００１９】
この時、本発明の実施によるマルチキャストルーティングを、本発明では‘オンデマンドＭＰＲ（マルチポイントリレー）フラッディング’と称する。
【００２０】
オンデマンドＭＰＲフラッディングは、従来の一般的なフラッディング方式で発生する過度な帯域幅の使用を低減するためのことであり、従来のＭＰＲフラッディングを改善させたことである。
【００２１】
オンデマンドＭＰＲフラッディングは、ソースノードで伝送するデータが存在する場合、まず、フラッディング過程を通じて隣接ノードの情報を学習した後、学習された情報を利用して２ホップ隣接ノードを探してＭＰＲを選定する方式である。
【００２２】
従来のＭＰＲフラッディング方式では、モバイルアドホックネットワークを構成するそれぞれのノードから周期的にブロードキャストされるヘローパケットのようなパケットを通じて、隣接ノードの情報を学習してＭＰＲを選定した。
【００２３】
しかし、本発明でのオンデマンドＭＰＲフラッディングは、ソースノードから伝送されるデータが存在する場合にのみフラッディングを行うことによって、ヘローパケットのように伝送するデータがない場合にも周期的に伝送される制御パケットを減少させることができる。
【００２４】
ソースノードが特定のグループにデータパケットを伝送しようとする場合、ソースノードは、１ホップブロードキャスト方式により伝送される制御パケットを一般的なフラッディング方式で伝送するか、または従来のＭＰＲフラッディング方式で伝送するかを決定する。
【００２５】
この時、いかなるフラッディング方式を使用するかについての決定は、ソースノードに既定の方式による。
【００２６】
例えば、ソースノードで伝送されるデータが存在する場合、あらゆるデータが伝送されるまで５秒間隔で最初の２回は一般的なフラッディング方式を、それ以後の３回は従来のＭＰＲフラッディング方式を、それ以後の２回は再び一般的なフラッディング方式を、それ以後の３回は再び従来のＭＰＲフラッディング方式を使用できる。すなわち、従来の一般的なフラッディング方式と従来のＭＰＲフラッディング方式とを混合して周期的にフラッディングを行える。
【００２７】
図１を参照すれば、まず、ソースノード（１番ノード）１１０から１ホップブロードキャスト方式によって伝送された制御パケットをソースノードを中心に１ホップの位置にある隣接ノード（３番、４番、６番ノード）が受信する。
【００２８】
次いで、一般的なフラッディング方式が使われる場合、前記隣接ノード（３番、４番、６番ノード）は、前記受信した制御パケットを１ホップブロードキャスト方式によって再伝送し、従来のＭＰＲフラッディング方式が使われる場合、隣接ノードのうちＭＰＲノードに該当する隣接ノードが前記受信した制御パケットを、１ホップブロードキャスト方式によって再伝送する。
【００２９】
このような過程で、例えば、３番ノードが送信した情報をソースノード（１番ノード）１１０が受信することができ、これを通じてソースノード１１０の立場では、３番、４番、６番ノードがソースノード１１０に対する１ホップ隣接ノードであるということが分かる。
【００３０】
次いで、それぞれの隣接ノード（３番、４番、６番ノード）によるフラッディングを通じて、ソースノード（１番ノード）は、２番、７番ノードが３番ノードの１ホップ隣接ノードであるということが分かり、８番、１２番、１１番、５番ノードが４番ノードの１ホップ隣接ノードであるということが分かる。
【００３１】
このような方式を通じて、ソースノード１１０は、２番、７番、８番、１２番、１１番、５番ノードが自身から２ホップほど離れた位置に存在しているということが分かる。
【００３２】
これは、フラッディング過程で伝送される制御パケットには、自身についての情報だけでなく自身を基準に１ホップ隣接ノードについての情報も共に含まれることによって可能である。
【００３３】
図１に示すそれぞれのノードは、前記のような方式によって自身を基準として、１ホップ及び２ホップ隣接ノードについての情報をルーティングテーブルの形態で保存できる。
【００３４】
前記ルーティングテーブルの変化がない場合、ソースノード（１番ノード）は、ＭＰＲ計算を通じて２ホップにパケットを伝達できる１ホップ隣接ノードのうち、最も多くの２ホップ隣接ノードを持つ１ホップ隣接ノードを‘ＭＰＲノード’と選定し、ネットワーク上での制御パケット伝達は、ＭＰＲフラッディング方式による。
【００３５】
この時、ＭＰＲノードを決定するために前記ルーティングテーブルが利用され、ＭＰＲノードを指定するために制御パケットにＭＰＲノードについての情報を含めることができる。
【００３６】
一方、フラッディング方式に制御パケットが伝えられる間、前記制御パケットにはソースノードについての情報も含まれて伝えられる。
【００３７】
前記のような方法によりフラッディングが反復されれば、制御パケットがソースノードにより受信ノードとして指定された目的ノード１２０、１３０、１４０に最終的に伝えられる。このような目的ノードは、マルチキャスト方式によりグルーピングされたノードである。
【００３８】
目的ノードは、自身に制御パケットを伝送したノードを‘親ノード（ｐａｒｅｎｔ  ｎｏｄｅ）’と指定し、前記親ノードに、ユニキャスト方式によって目的ノードの存在を知らせる‘参加要請パケット（ｊｏｉｎ  ｒｅｑｕｅｓｔ  ｐａｃｋｅｔ）’を伝送する。この時、前記親ノードは、自身のルーティングテーブルに前記目的ノードを‘子ノード（ｃｈｉｌｄ  ｎｏｄｅ）’と記録する。
【００３９】
次いで、再び自身に制御パケットを伝送したノードを自身の親ノードと指定し、前記親ノードで、ユニキャスト方式によって‘参加要請パケット’を伝送すれば、前記‘参加要請パケット’を受信したノードは、自身のルーティングテーブルに、前記と同じく前記‘参加要請パケット’を伝送したノードを‘子ノード’と記録する。
【００４０】
このような過程が反復されて、目的ノードから伝送された‘参加要請パケット’がソースノードまで伝えられれば、‘参加要請パケット’を受信または送信したノードで構成されたツリー構造が形成される。これは、‘参加要請パケット’を受信または送信したノードが、自身のルーティングテーブルに子ノードまたは親ノードについての情報を含んでいるためである。
【００４１】
このような過程を図１を例として説明する。
【００４２】
目的ノードの例を１０番ノード１３０とする場合、１０番ノード１３０は、自身に制御パケットを伝送した２番ノードを自身の親ノードと指定し、２番ノードに‘参加要請パケット’をユニキャスト方式によって伝送する。
【００４３】
２番ノードは、１０番ノード１３０により伝送された‘参加要請パケット’を受信した後、自身に‘参加要請パケット’を伝送した１０番ノード１３０を子ノードと、自身に制御パケットを伝送した３番ノードを自身の親ノードと指定する。次いで、３番ノードに‘参加要請パケット’をユニキャスト方式によって伝送する。
【００４４】
３番ノードは、２番ノードにより伝送された‘参加要請パケット’を受信した後、自身に‘参加要請パケット’を伝送した２番ノードを子ノードと、自身に制御パケットを伝送したソースノード１１０を自身の親ノードと指定する。次いで、ソースノード１１０に‘参加要請パケット’をユニキャスト方式によって伝送する。
【００４５】
ソースノード１１０は、自身に‘参加要請パケット’を伝送した３番ノードを子ノードと指定する。
【００４６】
一方、目的ノードのうち一つである１３番ノード１２０は、自身に制御パケットを伝送した２番ノードを自身の親ノードと指定し、２番ノードに‘参加要請パケット’をユニキャスト方式によって伝送する。
【００４７】
次いで、２番ノードは、１３番ノード１２０により伝送された‘参加要請パケット’を受信した後、１３番ノード１２０を子ノードと指定する。この時、２番ノードは、既に３番ノードにより３番ノードの子ノードと指定されており、２番ノードにより２番ノードの親ノードと指定されているので、２番ノードが３番ノードに‘参加要請パケット’を伝送する必要はない。
【００４８】
前記のような方法によって、ソースノード１１０、４番ノード、１１番ノード１３０の間にも親ノード及び子ノードの関係が成立でき、それぞれのノードは、自身の親ノード及び子ノードについての情報を持っている。
【００４９】
このような方法によって、ソースノード１１０とソースノード１１０に対する目的ノード１２０、１３０１４０とで構成されたツリー構造が形成され、これを図２で図示している。
【００５０】
前記のような方法を通じてツリー構造が形成されれば、ソースノード１１０が目的ノード１２０、１３０、１４０にデータパケットをマルチキャスト方式によって伝送する準備ができたことになる。
【００５１】
ソースノード１１０は、データパケットを１ホップブロードキャスト方式によって隣接ノード（３番、４番、６番ノード）に伝送する。
【００５２】
この時、ソースノード１１０から伝送されたデータパケットを受信した隣接ノードのうち、ソースノードの子ノードに該当する３番ノード及び４番ノードは、自身に子ノードがあるかどうかを確認した後、ソースノード１１０から受信したデータパケットを１ホップブロードキャスト方式によって再伝送する。
【００５３】
このような過程を反復すれば、目的ノード１２０、１３０、１４０は、ソースノード１１０から伝送されたデータパケットを受信できる。
【００５４】
図３は、本発明の一実施形態によってモバイルアドホックネットワーク環境でのマルチキャストルーティング方法を示すフローチャートである。
【００５５】
ソースノードが目的ノードに伝送するデータの存否を確認する（Ｓ３１０）。
【００５６】
もし、データが存在すれば、ソースノードは、データ伝送のための制御パケットを１ホップブロードキャスト方式によって伝送する（Ｓ３２０）。しかし、データが存在しなければ、ソースノードはデータ伝送のための別途の制御パケットを伝送しない。
【００５７】
ソースノードにより伝送された制御パケットは、フラッディング方式によって複数のノードを経て目的ノードに伝えられる（Ｓ３３０）。次いで、前述した‘参加要請パケット’を利用することによって、ソースノードと目的ノードとの間に制御パケットが伝えられるパス上にあるノードは、それぞれ自身の親ノード及び子ノードについての情報を保存する（Ｓ３４０）。具体的な方法は、前述したので、ここでは省略する。
【００５８】
ソースノードに前記‘参加要請パケット’が伝えられれば、ソースノードは、データパケットを１ホップブロードキャスト方式によって隣接ノードに伝送し、隣接ノードのうち子ノードを持つノードが前記データパケットを自身の子ノードに伝送する（Ｓ３５０）。このような方法を反復することによって、ソースノードから伝送されたデータパケットが目的ノードに伝えられうる。
【００５９】
図４は、本発明の一実施形態によって遺失されたデータパケットを復元する過程を示すフローチャートである。
【００６０】
無線環境によってデータが伝送される各ノード間にデータが伝送されるうち、伝送されるデータが遺失されることもある。
【００６１】
このような場合、損失されたデータを復元するために、それぞれのノードはソースノードにより伝送されたデータパケットを識別するシーケンスナンバーのような識別情報をキュー（ｑｕｅｕｅ）のようなデータ構造の形態で臨時保存する（Ｓ４１０）。
【００６２】
したがって、子ノードが親ノードからデータパケットを受信する時、前記のようなシーケンスナンバーを検査することによってデータパケットが遺失されたかどうかが分かる。
【００６３】
もし、データパケットが遺失されたと判断されれば（Ｓ４２０）、子ノードは親ノードに対して、遺失されたデータパケットのシーケンスナンバーに該当するデータパケットの再伝送を要請する‘ＮＡＣＫ’パケットを伝送する（Ｓ４３０）。‘ＮＡＣＫ’パケットは、ユニキャストまたは１ホップブロードキャスト方法によって伝送できる。
【００６４】
前記‘ＮＡＣＫ’パケットを受信した親ノードは、損失されたデータパケットを子ノードに再伝送する（Ｓ４４０）。このために、親ノードは、自身が伝送したデータパケットを所定の時間保存する。
【００６５】
一方、データパケットが遺失されたと判断されれば、所定の時間待った後に子ノードが親ノードに対して‘ＮＡＣＫ’パケットを伝送することもできるが、これは、自身の親ノードに対する他の子ノードが同じパケットに対して‘ＮＡＣＫ’パケットを要請することもあるため、重畳する‘ＮＡＣＫ’パケットの伝送を防止するためである。この時、子ノードが‘ＮＡＣＫ’パケットを伝送する時に待つ時間は、少なくとも子ノードと親ノードとの間にパケットが往復する時間（以下では、‘１＿ＨＯＴ＿ＲＴＴ’という）より長いことが望ましい。
例えば、ＩＥＥＥ  ８０２．１１規格でのＭＡＣフレームが使われる場合、‘１＿ＨＯＴ＿ＲＴＴ’時間は
【数１】
2007104675.tif 000003
となる。
【００６６】
一方、場合によっては、図４での親ノードが遺失されたデータパケットを持っていないこともある。
【００６７】
例えば、図１で、２番ノードが３番ノードに対して１０番目のデータパケットの再伝送を要請する‘ＮＡＣＫ’パケットを伝送したが、３番ノードも１０番目のデータパケットを持っていないと仮定する。
【００６８】
このような場合、３番ノードは、自身の親ノードに該当するソースノード１１０に対して１０番目のデータパケットの再伝送を要請する‘ＮＡＣＫ＿ｏｕｔ＿ｏｆ＿ｗｉｎｄｏｗ’パケットを伝送する。
【００６９】
次いで、ソースノード１１０は、１０番目のノードを３番ノードを経由して２番ノードに伝送する。
【００７０】
すなわち、遺失されたデータパケットを復旧する過程において、ツリー構造での上位ノードに該当する親ノードが遺失されたデータパケットを復旧できない場合には、子ノードから伝えられた‘ＮＡＣＫ’パケットが上位ノードに伝達され続けて、ソースノードにまで伝えられることもある。
【００７１】
ソースノードが遺失されたデータパケットを伝送する時には、伝送速度を低めることによってデータ伝送率を高めることもできる。
【００７２】
以上、添付図を参照して本発明の実施例を説明したが、本発明が属する技術分野で当業者ならば本発明がその技術的思想や必須特徴を変更せずとも他の具体的な形に実施されうるということが理解できるであろう。したがって、前述した実施例は全ての面で例示的なものであって、限定的なものではないと理解せねばならない。
【産業上の利用可能性】
【００７３】
本発明は、無線モバイル機器の関連技術分野に好適に用いられる。
【図面の簡単な説明】
【００７４】
【図１】本発明の一実施形態によるモバイルアドホックネットワークシステムを示す例示図である。
【図２】本発明の一実施形態によって、ソースノード及び複数の目的ノードで形成されるツリー構造を示す例示図である。
【図３】本発明の一実施形態によってモバイルアドホックネットワーク環境でのマルチキャストルーティング方法を示すフローチャートである。
【図４】本発明の一実施形態によって遺失されたデータパケットを復元する過程を示すフローチャートである。
【符号の説明】
【００７５】
１００      モバイルアドホックネットワークシステム
１１０      ソースノード
１２０、１３０、１４０      目的ノード
【図１】
2007104675.tif 000004
【図２】
2007104675.tif 000005
【図３】
2007104675.tif 000006
【図４】
2007104675.tif 000007