(57)【要約】【課題】広告を行う特定のノードからのフラッディングの際、再送を行う無線通信装置を減らすことができる無線通信装置及び無線通信システムが望まれていた。【解決手段】自ノードに隣接する隣接ノードと隣接し、自ノードには隣接しない２ホップ隣接ノードにおける、広告ノードからの最短ホップ数を求めるＨｅｌｌｏメッセージ処理部２０１と、少なくとも２ホップ隣接ノードの広告ノードからの最短ホップ数に基づき、隣接ノードのうち、自ノードが送信したフラッディングパケットを中継させる１又は複数の隣接ノードを求めるＭＰＲ計算部２０５とを備えたものである。【選択図】図１
2010171577.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークを構築する無線通信装置であって、
当該無線通信装置に隣接する他の無線通信装置である隣接ノードと隣接し、当該無線通信装置には隣接しない他の無線通信装置である２ホップ隣接ノードにおける、広告ノードからの最短ホップ数を求める隣接情報処理部と、
少なくとも前記２ホップ隣接ノードの広告ノードからの最短ホップ数に基づき、前記隣接ノードのうち、当該無線通信装置が送信したフラッディングパケットを中継させる１又は複数の隣接ノードを求める中継ノード計算部と
を備えたことを特徴とする無線通信装置。
【請求項２】
前記中継ノード計算部は、
前記２ホップ隣接ノードのうち、広告ノードからの最短ホップ数が最大となる２ホップ隣接ノードを選択し、
前記隣接ノードのうち、選択した前記２ホップ隣接ノードと隣接する隣接ノードの中から、当該無線通信装置が送信したフラッディングパケットを中継させる１又は複数の隣接ノードを求める
ことを特徴とする請求項１記載の無線通信装置。
【請求項３】
当該無線通信装置における広告ノードからの最短ホップ数を求めるホップ数計算部を備え、
前記隣接情報処理部は、
前記隣接ノードにおける広告ノードからの最短ホップ数を更に求め、
前記中継ノード計算部は、
当該無線通信装置における広告ノードからの最短ホップ数と、
前記隣接ノードにおける広告ノードからの最短ホップ数と、
前記２ホップ隣接ノードにおける広告ノードからの最短ホップ数とに基づき、
前記隣接ノードのうち、当該無線通信装置が送信したフラッディングパケットを中継させる１又は複数の隣接ノードを求める
ことを特徴とする請求項１又は２記載の無線通信装置。
【請求項４】
前記中継ノード計算部は、
前記２ホップ隣接ノードのうち、広告ノードからの最短ホップ数が、当該無線通信装置における広告ノードからの最短ホップ数に２ホップ加算した値である２ホップ隣接ノードを選択し、
前記隣接ノードのうち、選択した前記２ホップ隣接ノードと隣接する隣接ノードの中から、当該無線通信装置が送信したフラッディングパケットを中継させる１又は複数の隣接ノードを求める
ことを特徴とする請求項１〜３の何れかに記載の無線通信装置。
【請求項５】
前記ホップ数計算部は、
前記隣接ノードの広告ノードからの最短ホップ数のうち、最小の値に１ホップ加算した値を、当該無線通信装置における広告ノードからの最短ホップ数として求め、
前記隣接情報処理部は、
当該無線通信装置のアドレス及び広告ノードからの最短ホップ数の情報と、
前記隣接ノードのアドレス及び広告ノードからの最短ホップ数の情報とを前記隣接ノードとの間で授受し、
前記２ホップ隣接ノードのアドレス及び広告ノードからの最短ホップ数を求める
ことを特徴とする請求項３又は４記載の無線通信装置。
【請求項６】
前記隣接ノードの広告ノードからの最短ホップ数に基づき、前記広告ノード宛の上り経路における送信先の隣接ノードを選択する上り次ホップ決定部と、
前記隣接ノードから広告ノード宛の経路制御情報を取得したとき、該経路制御情報を前記上り経路における送信先の隣接ノードに送信し、
取得した前記経路制御情報を送信した隣接ノード及び送信元の無線通信装置のアドレスに基づき、前記広告ノードからの下り経路における送信先の隣接ノードを求める経路情報処理部と
を備えたことを特徴とする請求項１〜５の何れかに記載の無線通信装置。
【請求項７】
前記上り次ホップ決定部は、
前記隣接ノードのうち、広告ノードからの最短ホップ数が、当該無線通信装置の広告ノードからの最短ホップ数より小さい隣接ノードの中から、前記広告ノード宛の上り経路における送信先の隣接ノードを選択し、
前記経路情報処理部は、
前記隣接ノードから広告ノード宛の経路制御情報を取得したとき、当該経路制御情報の送信元の無線通信装置のアドレスの情報と、当該無線通信装置のアドレスの情報とを前記経路制御情報に含めて、前記上り経路における送信先の隣接ノードに送信し、
取得した前記経路制御情報の送信元の無線通信装置のアドレスを、前記広告ノードからの下り経路における宛先アドレスとし、取得した前記経路制御情報を送信した隣接ノードを、前記宛先アドレスに対する前記広告ノードからの下り経路における送信先の隣接ノードとする
ことを特徴とする請求項６記載の無線通信装置。
【請求項８】
請求項１〜７の何れかに記載の無線通信装置を複数備え、アドホックネットワークを構築することを特徴とする無線通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、アドホックネットワークを構築する無線通信装置、及び無線通信システムに関する。
【背景技術】
【０００２】
アドホックネットワーク内の広告を行うときや、ルーティングプロトコルであるＡＯＤＶ（Ad hoc On-Demand Distance Vector）やＯＬＳＲ（Optimized Link State Routing）での経路構築時には、メッセージのフラッディングが行われる。フラッディングが行われる際に、メッセージを再送する無線通信装置（以下「ノード」ともいう。）が必要以上に多いと帯域を無駄に消費することになる。
そこで、ＩＥＴＦ（Internet Engineering Task Force）ＲＦＣ３６２６において規定されているＯＬＳＲでは、ＭＰＲ（Multipoint Relay）集合を用いて再送ノードを減らしている（非特許文献１参照）。
【０００３】
ＯＬＳＲでは、各ノードが、隣接ノードのアドレスを含むＨｅｌｌｏメッセージを定期的に送信する。これにより、各ノードは、隣接ノードと２ホップ隣接ノードとを知ることができる。ＭＰＲ集合とは、あるノードｖが送信したメッセージを、ノードｖの２ホップ先のノードに届けるのに必要な中継ノードの集合である。
ＭＰＲ集合の情報をＨｅｌｌｏメッセージに含めて送信することで、フラッディング時に再送するノードを通知する。
Ｈｅｌｌｏメッセージを受け取ったノードは、Ｈｅｌｌｏパケットに含まれるＭＰＲ集合の情報をもとに、自ノードをＭＰＲとして選択しているノードの集合（ＭＰＲセレクタ集合）の情報を作成する。
【０００４】
そして、ノードｖが送信したフラッディングメッセージを受信したノードｕは、そのメッセージを初めて受信し、かつノードｖがＭＰＲセレクタ集合に含まれているとき、メッセージを再送する。
ノードｕが再送を行ったとき、ノードｕが再送したメッセージを受信したノードが同じ動作を行うことにより、再送ノードを少なくしてフラッディングを実現している（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】IETF MANET RFC3626,(October 2003)
【非特許文献２】小出俊夫、”Ｐ２Ｐとワイヤレスの交差点第６回ＯＬＳＲ（Optimized Link State Routing）プロトコル”、［online］、株式会社  インプレス、［２００９年１月６日検索］、インターネット＜URL:http://internet.watch.impress.co.jp/www/column/wp2p/wp2p06.htm＞
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来の技術では、特定のノードからのフラッディングの際に、必要のないノードもメッセージの再送を行う場合がある、という問題点があった。
【０００７】
例えば、図５に示すネットワークを用いて、従来の技術により、ＭＰＲを用いたフラッディングの際に、必要のないノードがメッセージの再送を行う場合を説明する。
図５において、実線は２つノードが隣接していることを示す。また、実線の矢印は、各ノードのＭＰＲ集合を示す。例えばノード０からノード１への矢印は、ノード０のＭＰＲ集合にノード１が含まれていることを示す。また、点線の矢印は、この例でのメッセージの流れの一部を示している。
【０００８】
ノード０からあるメッセージをフラッディングするとき、ノード０が送信したメッセージをノード０のＭＰＲ集合に含まれるノード１及びノード２が再送する。
ノード１がノード２より先に再送を行ったとき、ノード１からメッセージを受信したノード４は再送を行う。
しかし、ノード０からフラッディングを行う際は、ノード１の２ホップ先のノード２には既にメッセージが到達しているので、ノード４は再送を行う必要はない。
このように、あるノードからフラッディングを行う際、必要がないノードもメッセージの再送を行う場合がある。
【０００９】
また、従来の技術では、広告ノードへの上り及び下りの経路を作成する際、コントロールメッセージ（例えばＴｃメッセージ）などの制御パケットをネットワーク全体にフラッディングし、ネットワーク全体のトポロジーを各ノードに知らしめることにより、各ノードは通信経路を求める。このため、制御パケットに係るトラフィックが増加する、という問題点があった。
【００１０】
したがって、広告を行う特定のノードからのフラッディングの際、再送を行う無線通信装置を減らすことができる無線通信装置及び無線通信システムが望まれていた。
また、制御パケットによるトラフィックの増加を抑制することができる無線通信装置及び無線通信システムが望まれていた。
【課題を解決するための手段】
【００１１】
本発明に係る無線通信装置は、アドホックネットワークを構築する無線通信装置であって、当該無線通信装置に隣接する他の無線通信装置である隣接ノードと隣接し、当該無線通信装置には隣接しない他の無線通信装置である２ホップ隣接ノードにおける、広告ノードからの最短ホップ数を求める隣接情報処理部と、少なくとも前記２ホップ隣接ノードの広告ノードからの最短ホップ数に基づき、前記隣接ノードのうち、当該無線通信装置が送信したフラッディングパケットを中継させる１又は複数の隣接ノードを求める中継ノード計算部とを備えたものである。
【００１２】
また、本発明に係る無線通信システムは、上記の無線通信装置を複数備え、アドホックネットワークを構築するものである。
【発明の効果】
【００１３】
本発明は、２ホップ隣接ノードの広告ノードからの最短ホップ数に基づき、隣接ノードのうち、当該無線通信装置が送信したフラッディングパケットを中継させる隣接ノードを求めるので、広告ノードからのフラッディングの際、再送を行う無線通信装置を減らすことができる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態１に係る無線通信装置の構成を示す図である。
【図２】実施の形態１に係るＭＰＲ集合の計算を説明する図である。
【図３】実施の形態１に係る下り経路の作成を説明する図である。
【図４】実施の形態１に係る下り経路表を示す図である。
【図５】従来技術におけるＭＰＲを用いたフラッディングの例を示す図である。
【発明を実施するための形態】
【００１５】
実施の形態１．
本実施の形態における無線通信システムは、複数の無線通信装置（以下「ノード」ともいう。）を備え、アドホックネットワークを構築する。
このアドホックネットワークにおいては、各ノードは、プロアクティブ（Proactive）なルーティングプロトコルを使用してマルチホップ通信を行う。
本実施の形態においては、ルーティングプロトコルとしてＩＥＴＦ  ＲＦＣ３６２６において規定されているＯＬＳＲを用いる場合について説明する。
【００１６】
図１は実施の形態１に係る無線通信装置の構成を示す図である。
図１に示すように、無線通信装置は、送受信手段２００、Ｈｅｌｌｏメッセージ処理部２０１、記憶手段２１０、ホップ数計算部２０４、ＭＰＲ計算部２０５、Ｔｃメッセージ処理部２０８、及び上り次ホップ決定部２０７を有する。
また、記憶手段２１０には、隣接ノード・ホップ数リスト２０２、２ホップ隣接ノード・ホップ数リスト２０３、ＭＰＲセレクタリスト２０６、及び下り経路表２０９が記憶される。
【００１７】
なお、Ｈｅｌｌｏメッセージ処理部２０１は、本発明における隣接情報処理部に相当する。
また、ＭＰＲ計算部２０５は、本発明における中継ノード計算部に相当する。
また、Ｔｃメッセージ処理部２０８は、本発明における経路情報処理部に相当する。
【００１８】
送受信手段２００は、当該無線通信装置（以下「自ノード」ともいう。）に隣接する他の無線通信装置（以下「隣接ノード」という。）と、パケットを送受信する。
なお、ノードに隣接するとは、ノード間で直接通信が可能であることをいう。
【００１９】
Ｈｅｌｌｏメッセージ処理部２０１は、送受信手段２００を介して、隣接ノードとの間でＨｅｌｌｏメッセージを授受する。
また、Ｈｅｌｌｏメッセージ処理部２０１は、取得したＨｅｌｌｏメッセージを処理し、Ｈｅｌｌｏパケットをもとに、隣接ノード・ホップ数リスト２０２、及び２ホップ隣接ノード・ホップ数リスト２０３を作成して、記憶手段２１０に記憶させる。
【００２０】
この隣接ノード・ホップ数リスト２０２は、各隣接ノードのアドレス及び広告ノードからの最短ホップ数の情報を有する。
また、２ホップ隣接ノード・ホップ数リスト２０３は、各２ホップ隣接ノードのアドレス及び広告ノードからの最短ホップ数の情報を有する。
２ホップ隣接ノードとは、隣接ノードと隣接し、自ノードには隣接しない他のノードである。
広告ノードとは、ネットワーク内にフラッディングを行う特定のノードである。
【００２１】
さらに、Ｈｅｌｌｏメッセージ処理部２０１は、Ｈｅｌｌｏパケットに含まれるＭＰＲ集合から、ＭＰＲセレクタリスト２０６を作成して、記憶手段２１０に記憶させる。
【００２２】
ホップ数計算部２０４は、隣接ノード・ホップ数リスト２０２に基づいて、自ノードの広告ノードからの最短ホップ数（以下、単に「ホップ数」という。）を得る。
【００２３】
ＭＰＲ計算部２０５は、隣接ノード・ホップ数リスト２０２と、２ホップ隣接ノード・ホップ数リスト２０３と、自ノードのホップ数とから、自ノードのＭＰＲ集合を求める。
自ノードのＭＰＲ集合とは、自ノードからのフラッディングパケットを中継させる１又は複数の隣接ノードの集合である。
【００２４】
上り次ホップ決定部２０７は、隣接ノード・ホップ数リスト２０２と、自ノードのホップ数とから、広告ノードへの上り経路における次ホップノードを決定する。
【００２５】
Ｔｃメッセージ処理部２０８は、広告ノードへのＴｃメッセージを処理し、Ｔｃメッセージをもとに、下り経路表２０９を作成して、記憶手段２１０に記憶させる。
【００２６】
Ｈｅｌｌｏメッセージ処理部２０１、ホップ数計算部２０４、ＭＰＲ計算部２０５、Ｔｃメッセージ処理部２０８、上り次ホップ決定部２０７は、これらの機能を実現する回路デバイスなどのハードウェアで実現することもできるし、マイコンやＣＰＵなどの演算装置上で実行されるソフトウェアとして実現することもできる。
記憶手段２１０は、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの記憶装置で構成することができる。
【００２７】
次に、本実施の形態における無線通信装置の動作について説明する。
【００２８】
［リスト作成］
まず、記憶手段２１０に記憶される、各リストの作成動作について説明する。
Ｈｅｌｌｏメッセージ処理部２０１は、定期的に、隣接ノードとの間でＨｅｌｌｏメッセージを授受する。
このＨｅｌｌｏメッセージは、自ノード（送信ノード）のアドレス、隣接ノードのアドレス、及び自ノードのＭＰＲ集合の情報などが含まれる。
さらに、ＲＦＣ３６２６において規定されたＨｅｌｌｏメッセージを拡張して、後述する自ノードのホップ数の情報と、受信したＨｅｌｌｏメッセージに含まれる隣接ノードのアドレスにその隣接ノードの広告ノードからのホップ数の情報とをＨｅｌｌｏメッセージに付与する。
Ｈｅｌｌｏメッセージ処理部２０１は、隣接ノードから取得したＨｅｌｌｏメッセージをもとに、隣接ノードのアドレス及びホップ数と、２ホップ隣接ノードのアドレス及びホップ数とを求める。
そして、Ｈｅｌｌｏメッセージ処理部２０１は、隣接ノード・ホップ数リスト２０２、及び２ホップ隣接ノード・ホップ数リスト２０３を作成する。
【００２９】
無線通信システムを構成する各ノードが、上記Ｈｅｌｌｏメッセージを定期的に授受することにより、各ノードは、それぞれ隣接ノード及び２ホップ隣接ノードのアドレスとホップ数の情報を取得することができる。
【００３０】
［自ノードのホップ数算出］
次に、自ノードのホップ数算出動作について説明する。
ホップ数計算部２０４は、自ノードが広告ノードである場合、自ノードのホップ数を０とする。
また、ホップ数計算部２０４は、自ノードが広告ノードでない場合、隣接ノード・ホップ数リスト２０２に基づき、各隣接ノードのホップ数うち、最小の値に１ホップ加算した値を、自ノードのホップ数として求める。
そして、Ｈｅｌｌｏメッセージ処理部２０１は、上述した動作により、自ノードのホップ数の情報を含むＨｅｌｌｏメッセージを送信する。
このようなＨｅｌｌｏメッセージの授受を各ノードにおいて行うことにより、各ノードは、自ノードにおける広告ノードからの最短ホップ数を得ることができる。
【００３１】
［ＭＰＲ集合の計算］
次に、自ノードが送信したフラッディングパケットを中継させるＭＰＲ集合の計算動作について説明する。
【００３２】
図２は実施の形態１に係るＭＰＲ集合の計算を説明する図である。
図２においては、各ノードを円で示し、各ノードのホップ数を円の中に示している。
以下、図２を用いて、広告ノードからのホップ数がｄ（ｄは非負の整数）であるノード４０１におけるＭＰＲ集合の計算動作を説明する。
【００３３】
なお、図２において、ノード４０１に隣接する隣接ノードの集合を、隣接ノード集合４２という。また、ノード４０１における２ホップ隣接ノードの集合を、２ホップ隣接ノード集合４３という。
即ち、隣接ノード集合４２内のノードのホップ数は、ｄ−１〜ｄ＋１である。
また、２ホップ隣接ノード集合４３内のノードのホップ数は、ｄ−２〜ｄ＋２である。
【００３４】
なお、図２においては、各ホップ数ごとにそれぞれ１つのノードを示しているが、隣接ノード集合４２内、及び２ホップ隣接ノード集合４３内には、同じホップ数となるノードが複数存在する場合もある。
【００３５】
まず、ＭＰＲ計算部２０５は、２ホップ隣接ノード・ホップ数リスト２０３を参照し、２ホップ隣接ノードのうち、広告ノードからの最短ホップ数が最大となるノードを選択する。即ち、２ホップ隣接ノードのホップ数が、自ノードのホップ数に２ホップ加算した値である２ホップ隣接ノードを選択する。
図２の例では、ＭＰＲ計算部２０５は、ホップ数がｄ＋２である２ホップ隣接ノード４３１を選択する。
なお、２ホップ隣接ノード集合４３内に、ホップ数がｄ＋２であるノードが複数存在する場合は、当該ノードを全て選択する。
【００３６】
次に、ＭＰＲ計算部２０５は、隣接ノード・ホップ数リスト２０２を参照し、選択した２ホップ隣接ノード４３１と隣接する隣接ノードの中から、ＭＰＲを求める。
図２の例では、ＭＰＲ計算部２０５は、２ホップ隣接ノード４３１と隣接する隣接ノード４２１をＭＰＲとして求める。
【００３７】
なお、ホップ数がｄ＋２である２ホップ隣接ノード４３１と隣接する隣接ノード４２１が複数存在する場合には、少なくとも１つをＭＰＲとして選択するようにしても良い。
なお、２ホップ隣接ノード４３１を複数選択した場合には、各２ホップ隣接ノード４３１について隣接する隣接ノード４２１の中からＭＰＲを求める。
【００３８】
なお、上記説明では、自ノード、隣接ノード、及び２ホップ隣接ノードのホップ数に基づきＭＰＲを求めたが、本発明はこれに限らず、少なくとも２ホップ隣接ノードの広告ノードからの最短ホップ数に基づき、隣接ノード集合４２内からＭＰＲを求めるようにしても良い。
【００３９】
次に、Ｈｅｌｌｏメッセージ処理部２０１は、ＭＰＲ計算部２０５により求められたＭＰＲ集合の情報をＨｅｌｌｏパケットに含め、隣接ノードとの間で授受する。
そして、Ｈｅｌｌｏメッセージ処理部２０１は、隣接ノードから取得したＨｅｌｌｏメッセージに含まれるＭＰＲ集合の情報から、自ノードをＭＰＲとして選択している、隣接ノードのアドレス情報からなるＭＰＲセレクタリスト２０６を作成する。
【００４０】
以降、各ノードは、ＭＰＲセレクタリスト２０６に登録された隣接ノードからのフラッディングパケットを受信したとき、当該フラッディングパケットを再送信することとなる。
これにより、ホップ数がｄであるノード４０１からのフラッディングパケットは、ホップ数がｄ＋１である隣接ノード４２１により再送信され、ホップ数がｄ、ｄ＋１、ｄ＋２である２ホップ隣接ノードに届くこととなる。
即ち、ホップ数ｄからのフラッディングを行う必要がないノードである、ホップ数がｄ−１、ｄ−２の２ホップ隣接ノードには、フラッディングパケットが届かないことになる。
【００４１】
［上り経路の作成］
各ノードから広告ノードへの上り経路の作成について説明する。
上り次ホップ決定部２０７は、隣接ノード・ホップ数リスト２０２を参照し、隣接ノードのうち、ホップ数が自ノードのホップ数より小さい隣接ノードの中から、任意の隣接ノードを選択する。例えば、隣接ノードのうち、ホップ数が最小となる隣接ノードを選択する。
そして、選択した隣接ノードを、広告ノード宛の上り経路における送信先の隣接ノード（以下「上り次ホップノード」という。）とする。
【００４２】
以降、各ノードは、広告ノード宛のメッセージ（パケット）を送信する際、当該広告ノード宛のメッセージに、上り次ホップ決定部２０７で選択した隣接ノードのアドレスを、上り次ホップノードアドレスとして含める。
そして、広告ノード宛のメッセージを受信したノードは、上り次ホップノードが自ノードのアドレスである場合、当該広告ノード宛のメッセージにおける上り次ホップノードを、自ノードの上り次ホップ決定部２０７で選択した隣接ノードのアドレスに変更し、再送する。
【００４３】
［下り経路の作成］
次に、広告ノードから各ノードへの下り経路の作成について説明する。
Ｔｃメッセージ処理部２０８は、隣接ノードから広告ノード宛の経路制御情報であるＴｃメッセージを取得したとき、Ｔｃメッセージを上り次ホップノードに送信し、取得したＴｃメッセージを送信した隣接ノード及び送信元のノードのアドレスに基づき、広告ノードからの下り経路における送信先の隣接ノード（以下「下り次ホップノード」という。）を求める。
このような動作の詳細を、図３及び図４を用いて次に説明する。
【００４４】
図３は実施の形態１に係る下り経路の作成を説明する図である。
図４は実施の形態１に係る下り経路表を示す図である。
【００４５】
図３においては、各ノードを円で示し、各ノードのアドレスを円の中に示している。
また、実線は２つノードが隣接していることを示す。
また、実線の矢印は、上り経路を示している。
また、アドレス「０」のノードは、広告ノードである。
【００４６】
また、図３においては、Ｔｃメッセージに付与されるアドレスを、括弧書きで、（送信ノード、上り次ホップノード、オリジネータ）の順に示している。詳細は後述する。
また、図３において、５１１、５１２、５１３は、下り経路表に追加されるアドレスを示している。詳細は後述する。
【００４７】
まず、各ノードのＴｃメッセージ処理部２０８は、下り経路作成のために、それぞれＴｃメッセージを作成し、上述した上り経路を用いてＴｃメッセージを広告ノード宛に送る。
Ｔｃメッセージには、当該Ｔｃメッセージを最初に送信した送信元のノード（以下「オリジネータ」という。）と、当該メッセージを中継したノード（以下「送信ノード」という。）と、当該Ｔｃメッセージを次に中継すべき上り次ホップノードのアドレスを含んでいる。
【００４８】
図３において、アドレス「７」のノードが送信するＴｃメッセージ５０１は、送信ノード「７」、上り次ホップノード「３」、オリジネータ「７」が付与される。
なお、次ホップノードは、上述したように、上り次ホップ決定部２０７により選択されるものである。ここではノード「３」であるものとする。
【００４９】
Ｔｃメッセージ５０１を受信したノードは、上り次ホップノードのアドレスが、自ノードアドレスの場合、このパケットを再送する。
図３の例では、ノード「３」は、Ｔｃメッセージ５０１を受信して、Ｔｃメッセージ５０２として再送する。
【００５０】
Ｔｃメッセージ５０１を受信したノード「３」のＴｃメッセージ処理部２０８は、下り経路表２０９に、［Ｔｃメッセージのオリジネータ「７」、送信者アドレス「７」］というエントリ５１１がなければ追加する。
【００５１】
次に、Ｔｃメッセージ５０１を受信したノード「３」のＴｃメッセージ処理部２０８は、Ｔｃメッセージ５０１の送信ノードと上り次ホップノードの情報を変更し、送信ノード「３」、上り次ホップノード「１」、オリジネータ「７」を付与したＴｃメッセージ５０２を送信する。
【００５２】
そして、Ｔｃメッセージ５０２を受信したノード「１」のＴｃメッセージ処理部２０８は、同様に、下り経路表２０９に、［Ｔｃメッセージのオリジネータ「７」、送信者アドレス「３」］というエントリ５１２がなければ追加する。
【００５３】
このような動作を各ノードで行うことにより、図４に示すように、Ｔｃメッセージのオリジネータのアドレスを、広告ノードからの下り経路における宛先ノードのアドレスとし、Ｔｃメッセージの送信者アドレスを、宛先アドレスに対する広告ノードからの下り経路における下り次ホップアドレスからなる下り経路表２０９を作成することができる。
【００５４】
図３の例では、ノード「７」からのＴｃメッセージを広告ノード「０」まで送ることで、Ｔｃメッセージのオリジネータであるノード「７」への下り経路上に存在する、ノード「０」、「１」、「３」の各下り経路表２０９に、ノード「７」への下り経路のエントリ５１３、５１２、５１１が追加される。
【００５５】
以上のように本実施の形態においては、２ホップ隣接ノードの広告ノードからの最短ホップ数に基づき、隣接ノードからＭＰＲを求めるので、広告ノードからのフラッディングの際、再送を行うノードを減らすことができる。
【００５６】
より詳しくは、自ノードのホップ数がｄであるとき、ホップ数がｄ＋２である２ホップ隣接ノード４３１を選択し、選択した２ホップ隣接ノード４３１と隣接する隣接ノードの中からＭＰＲを求める。
このため、ホップ数ｄからのフラッディングを行う必要がないノードである、ホップ数がｄ−１、ｄ−２の２ホップ隣接ノードには、フラッディングパケットが届かないことになり、広告ノードからのフラッディングの際に、必要のないノードがメッセージの再送を行う場合を削減することができる。
【００５７】
また、隣接ノードのホップ数をもとに、広告ノード宛の上り経路における上り次ホップノードを求める。そして、この上り経路を用いて、Ｔｃメッセージを各ノードから広告ノードに転送して、下り経路表２０９を作成する。
このため、コントロールメッセージ（例えばＴｃメッセージ）などの制御パケットをネットワーク全体にフラッディングすることなく、広告ノードへの上り経路、及び下り経路を作成することができる。
これにより、制御パケットに係るトラフィックの増加を抑制することができる。
【００５８】
なお、上記説明において、広告ノードからの最短ホップ数を求める動作について説明したが、広告ノードが複数存在する場合には、各広告ノードごとに、自ノード、隣接ノード、及び２ホップ隣接ノードのホップ数を求めるようにしても良い。
【符号の説明】
【００５９】
４２ 隣接ノード集合、４３ ホップ隣接ノード集合、２００ 送受信手段、２０１  Ｈｅｌｌｏメッセージ処理部、２０２  隣接ノード・ホップ数リスト、２０３  ２ホップ隣接ノード・ホップ数リスト、２０４  ホップ数計算部、２０５  ＭＰＲ計算部、２０６  ＭＰＲセレクタリスト、２０７ 上り次ホップ決定部、２０８ Ｔｃメッセージ処理部、２０９  下り経路表、２１０ 記憶手段、４０１ ノード、４２１ 隣接ノード、４３１ ２ホップ隣接ノード、５０１ Ｔｃメッセージ、５０２ Ｔｃメッセージ、５１１ エントリ、５１２ エントリ、５１３ エントリ。
【図１】
2010171577.tif 000003
【図２】
2010171577.tif 000004
【図３】
2010171577.tif 000005
【図４】
2010171577.tif 000006
【図５】
2010171577.tif 000007