無線マルチホップネットワーク、ノード、マルチキャスト経路制御方法及びプログラム
【課題】帯域の狭い無線ネットワークにおいて通信品質の高いマルチキャスト通信を容易に実現する。
【解決手段】他のノードから送信されてきたマルチキャスト情報とTCメッセージとからユニキャスト経路制御情報をユニキャスト経路制御情報取得部１０３にて取得し、当該ユニキャスト経路制御情報を用いて、すべてのマルチキャスト送信ノードをカバーする送信リレーノードセットと、すべてのマルチキャスト受信ノードをカバーする受信リレーノードセットとをリレーノードセット計算部１０４にて計算し、送信リレーノードセットに含まれるノードと受信リレーノードセットに含まれるノードとの間のマルチキャスト経路をマルチキャスト経路計算部１０５にて計算する。
【解決手段】他のノードから送信されてきたマルチキャスト情報とTCメッセージとからユニキャスト経路制御情報をユニキャスト経路制御情報取得部１０３にて取得し、当該ユニキャスト経路制御情報を用いて、すべてのマルチキャスト送信ノードをカバーする送信リレーノードセットと、すべてのマルチキャスト受信ノードをカバーする受信リレーノードセットとをリレーノードセット計算部１０４にて計算し、送信リレーノードセットに含まれるノードと受信リレーノードセットに含まれるノードとの間のマルチキャスト経路をマルチキャスト経路計算部１０５にて計算する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャスト通信を行うための無線マルチホップネットワーク、ノード、マルチキャスト経路制御方法及びプログラムに関する。
【背景技術】
【０００２】
一般的な無線マルチホップネットワークにおけるユニキャスト経路制御は、例えば非特許文献１に開示されている。以下に、非特許文献１に開示されているOLSR（Optimized Link State Routing）について説明する。
【０００３】
OLSRでは、起動後にあらかじめ設定された送信間隔でHelloメッセージを送信する。Helloメッセージは転送されず、無線到達範囲内に存在する通信装置（以下、ノードと称する）のみが受信することができる。
【０００４】
また、他のノードからHelloメッセージを受信した場合、当該Helloメッセージの有効期間中その情報を隣接ノードテーブルに保持する。ノードが次回Helloメッセージを送信する場合は、隣接ノードテーブルに記録されている全ノードのIPアドレスのリストを含める。隣接ノード情報の入ったHelloメッセージを受信したノードは、MPR（Multi Point Reply）ノードの選択を行い、TC（Topology Control）メッセージの送信を行う。
【０００５】
MPRノードとは、あるノードが送信した経路制御メッセージ（TCメッセージ等）を、ネットワーク内の全ノードが受信できるように転送するための転送ノードである。あるノードから見た場合、MPRノードの選択は自ノードの２ホップ先に存在するノード全てをカバーするような隣接ノードの組を計算することで行われる。自ノードが選択したMPRノードは、Helloメッセージによって隣接ノードに通知される。これにより隣接ノードは、自身をMPRノードに選択したノードからTCパケットなどのネットワーク内の全ノードに通知が必要な制御メッセージを受信した場合、自ノードがそのメッセージを転送する必要があることを知ることができる。
【０００６】
TCメッセージは、自分の持つリンク情報（通常は、選択したMPRノードとの間のリンク情報）をネットワーク内の全ノードに通知するためのメッセージである。TCメッセージはあらかじめ設定された送信間隔で作成され、上述のMPRノードによって転送されてネットワーク内の全ノードに通知される。他のノードから受信したTCメッセージのリンク情報は、トポロジーテーブルに保存される。各通信ノードは、トポロジーテーブルに記録されたリンク情報からネットワークトポロジーグラフを作成し、各通信ノードまでの最短経路を計算する。その計算結果にしたがって通信転送経路を設定する。
【０００７】
また、非特許文献１に開示されているOLSRの仕組みを拡張し、無線マルチホップネットワーク上でマルチキャスト制御を行う方式（以下、M-OLSRと称する）が非特許文献２に開示されている。
【０００８】
M-OLSRでは、マルチキャストパケットの送信ノードは、SOURCE_CLAIMメッセージをネットワーク全体にフラッディングする。SOURCE_CLAIMメッセージを受信し、そのマルチキャストを受信したい受信ノードは、送信ノードへのNext Hopノード（送信ノード宛パケットを転送するノード）へCONFIRM_PARENTメッセージを送信する。CONFIRM_PARENETメッセージを受信した中継ノードは、自身がすでに該当するマルチキャストの受信者もしくは中継者でなければ、同様に送信ノードのNext Hopに向けてCONFIRM_PARENETメッセージを転送し、マルチキャスト転送テーブルを設定する。すでに受信者もしくは中継者であれば、マルチキャスト転送テーブルを設定し、CONFIRM_PARENTメッセージは転送しない。マルチキャスト転送テーブルを維持するため、送信ノードはSOURCE_CLAIMを、また、受信ノード及び転送ノードはCONFIRM_PARENTを定期的に送信する。一定時間メッセージを受信しなかった場合、送信ノードもしくは受信ノードが消滅したと判断し、マルチキャスト転送テーブルの該当エントリを削除する。
【０００９】
その他にも、無線マルチホップネットワークのためのマルチキャスト制御方式は、非特許文献３に記載されるような様々な方式が開示されている。非特許文献３によれば、マルチキャスト制御方式には大きく分けてツリー型方式とメッシュ型方式とがある。ツリー型方式は、ある代表ノードを決定し、マルチキャストの送信者および受信者（メンバー）はその代表ノードに向かってJoinを行い、マルチキャスト配信ツリーを構築する。メッシュ型方式の場合、各（送信ノード、受信ノード）ペア間にそれぞれ経路を構築する。前述のM-OLSRもメッシュ型方式の一種である。
【００１０】
しかしながら、上述した従来のメッシュ型マルチキャスト経路制御方式では、送信ノードと受信ノードとの組に対してそれぞれ経路を構築するため、設定する経路数が多くなり、必要な制御メッセージ量も多くなる。そのため、帯域の狭いネットワークでは利用が困難になってしまう。また、経路数の増加に伴い、マルチキャストパケットを転送するノード数が多くなり、互いのパケット送信が干渉して通信劣化（パケットの衝突、パケットロス、遅延の増加等）を引き起こす確率が高くなってしまう。
【００１１】
そこで、自ノードの移動速度を含む移動情報を用いて他ノードとの間に送受信される制御パケットの交換頻度を調整する技術が考えられている（例えば、特許文献１参照）。
【特許文献１】特許第３８９３６２０号公報
【非特許文献１】T. Clausen他、“Optimized Link State Routing Protocol for Ad Hoc Networks”、IEEE INMIC、2001年12月
【非特許文献２】Anis Laouiti他、“Multicast Optimized Link State Routing”、Inria Research Report No.4721、2003年2月、(ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-4721.pdf)
【非特許文献３】Carlos de Morais他、“Multicast over Wireless Mobile Ad HHoc Networks:Present and Future Directions”、IEEE Network Magazine、Jan/Feb 2003
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、特許文献１に記載された技術においては、自ノードの移動速度を測定しなければならなく、その手間を省くものが好ましい。
【００１３】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、帯域の狭い無線ネットワークにおいて通信品質の高いマルチキャスト通信を容易に実現することができる無線マルチホップネットワーク、ノード、マルチキャスト経路制御方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために本発明は、
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成する無線マルチホップネットワークにおいて、
前記ノードは、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得するユニキャスト経路制御情報取得部と、
前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算するリレーノードセット計算部と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算するマルチキャスト経路計算部と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する経路登録部とを有することを特徴とする。
【発明の効果】
【００１５】
以上説明したように本発明においては、他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから複数のノードの情報であるユニキャスト経路制御情報を取得し、ユニキャスト経路制御情報を用いて、すべてのマルチキャスト送信ノードをカバーする送信リレーノードセットと、すべてのマルチキャスト受信ノードをカバーする受信リレーノードセットとを計算し、計算された送信リレーノードセットに含まれるノードと計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算し、計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する構成としたため、帯域の狭い無線ネットワークにおいて通信品質の高いマルチキャスト通信を容易に実現することができる。
【発明を実施するための最良の形態】
【００１６】
以下に、本発明の実施の形態について図面を参照して説明する。
【００１７】
図１は、本発明の無線マルチホップネットワークの実施の一形態を示す図である。無線マルチホップネットワークでは、通信ノード間でパケットの転送を行い、送信通信ノード送信ノード）から宛先通信ノード（受信ノード）までパケットを届ける。通信ノードは自分の無線信号が届く範囲内に存在する任意の通信ノードと直接通信することができる。また、本実施の形態におけるユニキャストの経路制御は、非特許文献１に開示されたOLSRで制御されているとし、本発明のマルチキャスト経路制御方法はOLSRをベースとして拡張する。
【００１８】
本形態は図１に示すように、通信装置であるノード１１〜１６，２１〜２２，３１〜３３から構成されている。図１においては、互いのノード１１〜１６，２１〜２２，３１〜３３間の点線は無線で直接通信可能なノードの関係を示している。通信ノードはそれぞれ固有のノードID及びIPアドレスを持っている。IPアドレスはノード固有の値であるため、ノードIDにはIPアドレスを用いても良い。
【００１９】
ノード２１〜２２は、マルチキャストの送信を行うマルチキャスト送信ノードである。ノード３１〜３３は、マルチキャストの受信を行うマルチキャスト受信ノードである。ノード１１〜１６は、マルチキャストの転送のみを行い、マルチキャストの送信と受信とのいずれも行わないノードである。
【００２０】
図２は、図１に示したノード１１の一構成例を示す図である。
【００２１】
図１に示したノード１１には図２に示すように、TCメッセージ送信部１０１と、TCメッセージ受信部１０２と、ユニキャスト経路制御情報取得部１０３と、リレーノードセット計算部１０４と、マルチキャスト経路計算部１０５と、経路登録部１０６と、マルチキャスト転送テーブル１０７とが設けられている。なお、図２に示した構成要素は、本発明に関わるもののみである。また、ノード１２〜１６，２１〜２２，３１〜３３についてもノード１１と同じ構成要素が設けられている。
【００２２】
TCメッセージ送信部１０１は、ノード１１の接続情報を示すユニキャスト経路制御メッセージであるTC（Topology Control）メッセージを他のノードへ送信する。そのとき、マルチキャスト情報を含めて送信する。
【００２３】
TCメッセージ受信部１０２は、他のノードから送信されてきたTCメッセージを受信する。
【００２４】
ユニキャスト経路制御情報取得部１０３は、TCメッセージ受信部１０２にて受信されたTCメッセージから、ノード１２〜１６，２１〜２２，３１〜３３の情報であるユニキャスト経路制御情報を取得する。
【００２５】
リレーノードセット計算部１０４は、ユニキャスト経路制御情報取得部１０３にて取得されたユニキャスト経路制御情報を用いて、送信ノードであるノード２１〜２２をカバーする送信リレーノードセットを計算する。また、ユニキャスト経路制御情報を用いて、受信ノードであるノード３１〜３３をカバーする受信リレーノードセットを計算する。
【００２６】
マルチキャスト経路計算部１０５は、リレーノードセット計算部１０４にて計算された送信リレーノードセットに含まれるノードと受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算する。
【００２７】
経路登録部１０６は、マルチキャスト経路計算部１０５にて計算されたマルチキャスト経路をマルチキャスト転送テーブル１０７へ登録する。
【００２８】
マルチキャストの送信および受信を行うノードは、OLSRのHelloメッセージに以下のJoin情報を付加して、Helloメッセージを送信する。
【００２９】
（グループアドレス：送受信情報）
Helloメッセージは、ユニキャストと同様に定期的に送信されてもよく、また新たなJoinが発生した時点で適宜送信されても良い。グループアドレスは、送信または受信したいマルチキャストを識別するためのグループアドレスである。送受信情報は、自身がそのグループに対して送信者であるか受信者であるかまたはその両方であるかを示す情報である。
【００３０】
Join情報を含むHelloメッセージを隣接ノードから受信した場合、ノードはその隣接ノードが自身をMPR（Multi Point Reply）ノードに選択しているかどうかをチェックする。これは、Helloメッセージを用いて知ることができる。もし、その隣接ノードが自身をMPRノードとして選択している場合、そのノードはTCメッセージに以下のマルチキャスト情報を含めてTCメッセージ送信部１０１から送信する。
【００３１】
（グループアドレス：ノードリスト）
また、TCメッセージがマルチキャスト情報を含まずに送信されるものであっても良い。この場合、当該マルチキャスト情報は、マルチキャスト経路制御メッセージに含まれて送信される。
【００３２】
TCメッセージは、ユニキャストと同様に定期的に送信されてもよく、また新たな送受信ノードが発生した時点で適宜送信されても良い。グループアドレスは、送受信するマルチキャストを識別するためのグループアドレスである。ノードリストは、自身をMPRノードに選択しているマルチキャストの送信ノードおよび受信ノードのリストである。自身が送信ノードまたは受信ノードである場合は、自身もリストに含める。ノードリストは、以下の情報のリストで構成されている。
【００３３】
（ノードID：送受信情報）
図１では、ノード３１〜３３は、グループGの受信ノードとしてHelloメッセージにJoin情報を付加する。ノード２１〜２２は、グループGの送信ノードとしてHelloメッセージにJoin情報を付加する。
【００３４】
ノード３１はノード１１とノード１４とをMPRノードに選択している。また、ノード３２はノード１４をMPRノードに選択している。また、ノード３３はノード１３をMPRノードに選択している。また、ノード２１はノード１３とノード１６とをMPRノードに選択している。また、ノード２２はノード１３とノード１６とをMPRノードに選択している。MPRノードはユニキャスト経路制御においてOLSRと同じ方式で選択される。
【００３５】
ノード１１，１３，１４，１６は、TCメッセージにマルチキャスト情報を含めて送信する。例えば、ノード１３がTCメッセージに含めるマルチキャスト情報は、以下のようになる。
【００３６】
[グループG：[(ノード２１：送信),(ノード２２：送信),(ノード３３：受信)]]
また、TCメッセージがマルチキャスト情報を含まずに送信されるものであっても良い。この場合、当該マルチキャスト情報は、マルチキャスト経路制御メッセージに含まれて送信される。
【００３７】
MPRノードが送信したTCメッセージは、ネットワーク全体に配信される。各ノードは新たなTCメッセージを受信すると、ユニキャスト経路の計算とともにマルチキャスト経路の計算を開始する。ユニキャスト経路の計算はOLSRと同様であるため省略し、ここではマルチキャスト経路の計算について説明する。
【００３８】
ノードは、はじめに送信リレーノードセットである最小送信MPRセット（Least Sender MPR Set:以下、LSMと称する）と受信リレーノードセットである最小受信MPRセット（Least Receiver MPR Set:以下、LRMと称する）とを計算する。LSMは全送信ノードをカバーする最小のMPRノードの集合である。また、LRMは全受信ノードをカバーする最小のMPRノードの集合である。全てのノードが一意にLSM及びLRMを決定するため、以下の手順でLSM及びLRMを計算する。
・LSMの計算方法
図３は、図１に示した形態におけるLSMの計算方法を説明するためのフローチャートである。
【００３９】
まずは、これまでにTCメッセージ受信部１０２にて受信した有効なTCメッセージから、下記の情報（S, S(m), SN(m), RN(m), W(m)）をユニキャスト経路制御情報取得部１０３にて取得する。これらのノードの情報は、ユニキャスト経路制御情報である。
【００４０】
S : TCで広告された全送信ノードの集合
S(m) : MPR mが広告した送信ノードの集合
SN(m) : MPR mが広告した送信ノードの中でSに含まれている送信ノードの数
RN(m) : MPR mが広告した受信ノードの数
W(m) : MPR mのWillingness
ここで、WillingnessとはOLSRで定義されたノードのパケット転送意思を示す値である。一般に「０」〜「７」の範囲の数値で示され、パケット転送能力が高いノードほど、Willingness値を高く設定する。
【００４１】
これらの情報について、Sが空になるまで、リレーノードセット計算部１０４にて以下に示す（１）〜（９）の処理を繰り返してLSM及びSF(m)を計算する。このとき、MPRノードの選択された順番も覚えておく。ここで、
LSM : 最小送信MPRの集合
SF(m) : MPR mがパケット転送に責任を持つ送信ノードの集合
である。
【００４２】
（１）SN(m)が最大である送信MPR mを選択する（ステップＳ４１）。
【００４３】
（２）（１）で複数のmが存在する場合（ステップＳ４２）、m自身が送信ノードであるのものを選択する（ステップＳ４３）。
【００４４】
（３）（２）で複数のmが存在する場合（ステップＳ４４）、RN(m)が最大のものを選択する（ステップＳ４５）。
【００４５】
（４）（３）で複数のmが存在する場合（ステップＳ４６）、W(m)が最大のものを選択する（ステップＳ４７）。
【００４６】
（５）（４）で複数のmが存在する場合（ステップＳ４８）、アドレス（ノードID）が最小のmを選択する（ステップＳ４９）。
【００４７】
（６）（１）〜（５）で一意に決定されたmをLSMに追加する（ステップＳ５０）。
【００４８】
（７）SからS(m)に含まれる送信ノードを除く（ステップＳ５１）。
【００４９】
（８）（７）でSから除かれた送信ノードをSF(m)に追加する（ステップＳ５２）。
【００５０】
（９）全MPRに対して（７）で更新した新しいSでSN(m)を再計算する（ステップＳ５３）。
【００５１】
LRMもLSMと同様に以下のように計算する。
・LRMの計算方法
図４は、図１に示した形態におけるLRMの計算方法を説明するためのフローチャートである。
【００５２】
まずは、これまでにTCメッセージ受信部１０２にて受信した有効なTCメッセージから、下記の情報（R, R(m), RN(m), SN(m), W(m)）をユニキャスト経路制御情報取得部１０３にて取得する。これらのノードの情報は、ユニキャスト経路制御情報である。
【００５３】
R : TCで広告された全受信ノードの集合
R(m) : MPR mが広告した受信ノードの集合
RN(m) : MPR mが広告した受信ノードの中でRに含まれている受信ノードの数
SN(m) : MPR mが広告した送信ノードの数
W(m) : MPR mのWillingness
これらの情報について、Rが空になるまで、リレーノードセット計算部１０４にて（１１）〜（１９）の処理を繰り返し、LRM及びRF(m)を計算する。このとき、MPRノードの選択された順番も覚えておく。ここで、
LRM : 最小受信MPRの集合
RF(m) : MPR mがパケット転送に責任を持つ受信ノードの集合
である。
【００５４】
（１１）RN(m)が最大であるMPR mを選択する（ステップＳ６１）。
【００５５】
（１２）（１１）で複数のmが存在する場合（ステップＳ６２）、m自身が受信ノードであるものを選択する（ステップＳ６３）。
【００５６】
（１３）（１２）で複数のmが存在する場合（ステップＳ６４）、SN(m)が最大のものを選択する（ステップＳ６５）。
【００５７】
（１４）（１３）で複数のmが存在する場合（ステップＳ６６）、W(m)が最大のものを選択する（ステップＳ６７）。
【００５８】
（１５）（１４）で複数のmが存在する場合（ステップＳ６８）、アドレス（ノードID）が最小のmを選択する（ステップＳ６９）。
【００５９】
（１６）（１１）〜（１５）で一意に決定されたmをLRMに追加する（ステップＳ７０）。
【００６０】
（１７）RからR(m)に含まれる受信ノードを除く（ステップＳ７１）。
【００６１】
（１８）（１７）でRから除かれた受信ノードをRF(m)に追加する（ステップＳ７２）。
【００６２】
（１９）全MPRに対して（１７）で更新した新しいRでRN(m)を再計算する（ステップＳ７３）。
【００６３】
以上の計算によって、以下に示すようなLRM及びLSMが得られる。
【００６４】
図５は、図１に示した形態におけるLSM及びLRMを示す図である。
【００６５】
図５に示すように、受信ノードセット２０４である全受信ノード３１〜３３をカバーする受信MPRセット２０５であるMPRノードは、ノード１１、ノード１３及びノード１４である。ここで、ノード１１がカバーするノード３２をノード１４もカバーしているため、ノード１３及びノード１４が最小受信MPRセット（LRM）２０６となる。順番は、ノード１４のほうがノード１３よりもカバーする受信ノード数が多いため、｛ノード１４，ノード１３｝となる。また、送信ノードセット２０１である全送信ノード２１〜２２をカバーする送信MPRセット２０２であるMPRノードは、ノード１３及びノード１６である。ここで、ノード１３はノード３３もカバーしているため、最小送信MPRセット（LSM）２０３は｛ノード１３｝となる。
【００６６】
LSMとLRMとの計算が終了すると、次にLSM内のノードとLRM内のノードとの間のマルチキャスト経路２０７の計算をマルチキャスト経路計算部１０５にて開始する。全ノードが一意に経路を決定するため、以下のような計算を行う。
【００６７】
LSMのi番目の送信MPRをSMi、LRMのj番目の受信MPRをRMjとする。各i,jに対して、SMi→RMjへの最短経路を計算する。計算はTCメッセージのトポロジー情報のみを用いて、Dijkstraアルゴリズムで計算する。等コスト最短経路は全て計算し、全最短経路を覚えておく。ノードmの転送コストは、Willingnessを使い(Will_always - W(m) + 1)とする。ここで、Will_alwaysとは、値が「７」であるWillingnessである。
【００６８】
また、送信MPR SMiからRM1〜RMjへの経路がなるべく重なるよう計算するために、SMi → RMk への経路の計算時には、SMi → RM1〜RMk-1の計算までにすでに計算された経路上のリンクに対して、メトリックを一定値だけ減算する。さらに、転送時の干渉を避けるため、SMi → RM1〜RMk-1 の計算までにすでに計算された経路上のリンクと干渉するリンクに対して、メトリックを一定値だけ加算し、干渉しにくいリンクを通る経路を計算する。
【００６９】
最短経路が複数有る場合、各ノードが一意に最短経路を決定するため、以下の手順で一意に経路を決定する。
【００７０】
図６は、図１に示した形態におけるマルチキャスト経路の計算方法を説明するためのフローチャートである。以下の（２１）〜（２４）の処理を、経路が一意に決まるまで繰り返し、マルチキャスト経路を計算する。
【００７１】
（２１）Hop数が最短のものを選択する（ステップＳ８１）。
【００７２】
（２２）（２１）が複数ある場合（ステップＳ８２）、経路中のノードのWillingnessの合計値が最大のものを選択する（ステップＳ８３）。
【００７３】
（２３）（２１）及び（２２）が複数ある場合（ステップＳ８４）、経路中のノードIDが最小のものを選択する（ステップＳ８５）。
【００７４】
（２４）（２１）〜（２３）が複数ある場合（ステップＳ８６）、最小IDのノードを除いたノードの中で、最小ノードIDを持つ経路を選択する（ステップＳ８７）。
【００７５】
以上説明したLSMの計算方法、LRMの計算方法及びマルチキャスト経路の計算方法によるマルチキャスト経路制御方法を用いて、通信品質の高いマルチキャスト通信を容易に実現するためのマルチキャスト経路を求めることができる。
【００７６】
図７は、図１に示した形態において、図３、図４及び図６を用いて説明したマルチキャスト経路制御方法を用いて求められたマルチキャスト経路を示す図である。ここでは、全てのノードのWillingnessは同じであると仮定している。
【００７７】
また、図８は、一般的なメッシュ型方式において送信ノードと受信ノードとの対毎に作成されたマルチキャスト経路の一例を示す図である。
【００７８】
図７に示したマルチキャスト経路と、図８に示したマルチキャスト経路とを比較すると、図８に示したマルチキャスト経路よりも、図７に示したマルチキャスト経路の方が、経路の数が少ないことが明らかである。
【００７９】
マルチキャスト経路の計算が終了すると、各ノードは計算した経路に沿って経路登録部１０６によってマルチキャスト転送テーブル１０７にエントリを設定する。
【００８０】
ノード１１〜１４の各ノードは、以下のエントリをマルチキャスト転送テーブルに設定する。
・ノード１１：
宛先：G、送信ノード：ノード２１、上流ノード：ノード１２
宛先：G、送信ノード：ノード２２、上流ノード：ノード１２
・ノード１２：
宛先：G、送信ノード：ノード２１、上流ノード：ノード１３
宛先：G、送信ノード：ノード２２、上流ノード：ノード１３
・ノード１３：
宛先：G、送信ノード：ノード２１、上流ノード：ノード２１
宛先：G、送信ノード：ノード２２、上流ノード：ノード２２
・ノード１４：
宛先：G、送信ノード：ノード２１、上流ノード：ノード１１
宛先：G、送信ノード：ノード２２、上流ノード：ノード１１
ただし、SMiから[RM1,…,RMj]への経路中にSF(SMi)の送信ノードが含まれている場合（その送信ノードをｘとする）、xは、IP Src = xでSMiから受信したマルチキャストパケットは転送しない。つまりSrc=x, Dest=G, Up=SMiのマルチキャスト経路を設定しない。
【００８１】
図９は、通信経路中に送信ノードが含まれている場合に設定されるマルチキャストの一例を示す図である。ここで、s１〜s４は送信ノードであり、r１〜r４は受信ノードである。
【００８２】
図９に示すように、LSM=[A]，LRM＝[C，E]であり、A→Cへの最短経路はA→s１→B→Cである。この場合、経路上にSF(A)=[s１，s２，s３，s４]のノードが含まれているため、s１が送信したパケットはs１→A→s１→B→Cと冗長に転送されることになる。そこでs１は、送信ノード=s１，宛先=G，上流ノード=Aの経路は登録しないようにする。Aはs１から受信したマルチキャストパケットは転送するよう経路を設定する。つまり、送信ノードであるs１が転送ノードとして存在する場合、s１は、s１から送信されてきたマルチキャストパケットの経路のマルチキャスト転送テーブルへの登録を回避する。これによりs１が送信したマルチキャストパケットは、s１→B→C及びs１→A→Eで転送され、全受信ノードに到達する。
ノードAが設定する経路表（マルチキャスト転送テーブル１０７）は以下のとおりである。
【００８３】
宛先：G、送信ノード：s１、上流ノード：s１
宛先：G、送信ノード：s２、上流ノード：s２
宛先：G、送信ノード：s３、上流ノード：s３
宛先：G、送信ノード：s４、上流ノード：s４
ｓ１は以下のように経路を登録する。
【００８４】
宛先：G、送信ノード：s２、上流ノード：A
宛先：G、送信ノード：s３、上流ノード：A
宛先：G、送信ノード：s４、上流ノード：A
上記実施の形態では、LSMの計算方法の送信MPRノード選択手順（１）においてSN(SMi)が最大のMPRノードを優先的に選択する。しかし、下記のように、カバーする送信ノード数と送信ノードから受信ノードまでの経路長である経路コストとの双方を考慮してMPR mを選択することも可能である。
【００８５】
LSMの計算に先立ち、全送信MPR（SMi）から全受信MPR（RMj）への最短経路コストを計算しておく。SMi→RMjへの最短経路のコストをCijとする。
【００８６】
LSMの計算方法の送信MPR選択手順（１）は、以下のようになる。
【００８７】
（１）SN(m) / (Ci１+ Ci２+ … + Cij)が最大であるMPR mを選択する。
【００８８】
また同様に、カバーする受信ノード数と送信ノードから受信ノードまでの経路長である経路コストとの双方を考慮してMPR mを選択することも可能である。
【００８９】
以上説明したように、本発明の通信ノードでは、ユニキャスト経路制御メッセージを使ってマルチキャスト情報を送信することにより、マルチキャストのための制御メッセージ負荷を低減する。
【００９０】
また、ユニキャスト経路制御情報を使って、マルチキャスト送信ノードを全てカバーする送信リレーノードセットと、マルチキャスト受信ノードを全てカバーする受信リレーノードセットとを計算し、送信リレーノードセット内のノードと受信リレーノードセット内のノードとの間のマルチキャスト経路を計算することで、マルチキャスト経路数の増加を抑制する。マルチキャスト経路数を少なくすることで、干渉の少ないマルチキャスト配信ツリーを構築することができる。また、パケット転送時の干渉を軽減し、通信品質を向上させることができる。
【００９１】
これにより、本発明では制御負荷を抑えながら無線に適した干渉の少ないマルチキャスト経路制御が可能となる。
【００９２】
そして、干渉を減らすことにより、CSMA/CAで制御される無線ネットワークでは、衝突を回避しスループットを改善することができる。また、TDMAで制御される無線ネットワークでは、マルチキャスト配信のために必要なタイムスロット数を減らすことができ、リソース効率を向上させることができる。
【００９３】
また、上述した処理は、目的に応じて作製された論理回路で行うようにしても良い。また、処理内容を記述した各ノードにて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムを各ノードに読み込ませ、実行するものであっても良い。各ノードにて読取可能な記録媒体とは、フロッピーディスク（登録商標）、光磁気ディスク、ＤＶＤ、ＣＤなどの移設可能な記録媒体の他、各ノードに内蔵されたＨＤＤ等を指す。この記録媒体に記録されたプログラムは、各ノード内のＣＰＵ（不図示）にて読み込まれ、ＣＰＵの制御によって、上述したものと同様の処理が行われる。ここで、ＣＰＵは、プログラムが記録された記録媒体から読み込まれたプログラムを実行するコンピュータとして動作するものである。
【図面の簡単な説明】
【００９４】
【図１】本発明の無線マルチホップネットワークの実施の一形態を示す図である。
【図２】図１に示したノードの一構成例を示す図である。
【図３】図１に示した形態におけるLSMの計算方法を説明するためのフローチャートである。
【図４】図１に示した形態におけるLRMの計算方法を説明するためのフローチャートである。
【図５】図１に示した形態におけるLSM及びLRMを示す図である。
【図６】図１に示した形態におけるマルチキャスト経路の計算方法を説明するためのフローチャートである。
【図７】図１に示した形態において、図３、図４及び図６を用いて説明したマルチキャスト経路制御方法を用いて求められたマルチキャスト経路を示す図である。
【図８】一般的なメッシュ型方式において送信ノードと受信ノードとの対毎に作成されたマルチキャスト経路の一例を示す図である。
【図９】通信経路中に送信ノードが含まれている場合に設定されるマルチキャストの一例を示す図である。
【符号の説明】
【００９５】
１１〜１６，２１〜２２，３１〜３３ ノード
２０１ 送信ノードセット
２０２ 送信MPRセット
２０３ 最小送信MPRセット(LSM)
２０４ 受信ノードセット
２０５ 受信MPRセット
２０６ 最小受信MPRセット(LRM)
２０７ マルチキャスト経路
【技術分野】
【０００１】
本発明は、マルチキャスト通信を行うための無線マルチホップネットワーク、ノード、マルチキャスト経路制御方法及びプログラムに関する。
【背景技術】
【０００２】
一般的な無線マルチホップネットワークにおけるユニキャスト経路制御は、例えば非特許文献１に開示されている。以下に、非特許文献１に開示されているOLSR（Optimized Link State Routing）について説明する。
【０００３】
OLSRでは、起動後にあらかじめ設定された送信間隔でHelloメッセージを送信する。Helloメッセージは転送されず、無線到達範囲内に存在する通信装置（以下、ノードと称する）のみが受信することができる。
【０００４】
また、他のノードからHelloメッセージを受信した場合、当該Helloメッセージの有効期間中その情報を隣接ノードテーブルに保持する。ノードが次回Helloメッセージを送信する場合は、隣接ノードテーブルに記録されている全ノードのIPアドレスのリストを含める。隣接ノード情報の入ったHelloメッセージを受信したノードは、MPR（Multi Point Reply）ノードの選択を行い、TC（Topology Control）メッセージの送信を行う。
【０００５】
MPRノードとは、あるノードが送信した経路制御メッセージ（TCメッセージ等）を、ネットワーク内の全ノードが受信できるように転送するための転送ノードである。あるノードから見た場合、MPRノードの選択は自ノードの２ホップ先に存在するノード全てをカバーするような隣接ノードの組を計算することで行われる。自ノードが選択したMPRノードは、Helloメッセージによって隣接ノードに通知される。これにより隣接ノードは、自身をMPRノードに選択したノードからTCパケットなどのネットワーク内の全ノードに通知が必要な制御メッセージを受信した場合、自ノードがそのメッセージを転送する必要があることを知ることができる。
【０００６】
TCメッセージは、自分の持つリンク情報（通常は、選択したMPRノードとの間のリンク情報）をネットワーク内の全ノードに通知するためのメッセージである。TCメッセージはあらかじめ設定された送信間隔で作成され、上述のMPRノードによって転送されてネットワーク内の全ノードに通知される。他のノードから受信したTCメッセージのリンク情報は、トポロジーテーブルに保存される。各通信ノードは、トポロジーテーブルに記録されたリンク情報からネットワークトポロジーグラフを作成し、各通信ノードまでの最短経路を計算する。その計算結果にしたがって通信転送経路を設定する。
【０００７】
また、非特許文献１に開示されているOLSRの仕組みを拡張し、無線マルチホップネットワーク上でマルチキャスト制御を行う方式（以下、M-OLSRと称する）が非特許文献２に開示されている。
【０００８】
M-OLSRでは、マルチキャストパケットの送信ノードは、SOURCE_CLAIMメッセージをネットワーク全体にフラッディングする。SOURCE_CLAIMメッセージを受信し、そのマルチキャストを受信したい受信ノードは、送信ノードへのNext Hopノード（送信ノード宛パケットを転送するノード）へCONFIRM_PARENTメッセージを送信する。CONFIRM_PARENETメッセージを受信した中継ノードは、自身がすでに該当するマルチキャストの受信者もしくは中継者でなければ、同様に送信ノードのNext Hopに向けてCONFIRM_PARENETメッセージを転送し、マルチキャスト転送テーブルを設定する。すでに受信者もしくは中継者であれば、マルチキャスト転送テーブルを設定し、CONFIRM_PARENTメッセージは転送しない。マルチキャスト転送テーブルを維持するため、送信ノードはSOURCE_CLAIMを、また、受信ノード及び転送ノードはCONFIRM_PARENTを定期的に送信する。一定時間メッセージを受信しなかった場合、送信ノードもしくは受信ノードが消滅したと判断し、マルチキャスト転送テーブルの該当エントリを削除する。
【０００９】
その他にも、無線マルチホップネットワークのためのマルチキャスト制御方式は、非特許文献３に記載されるような様々な方式が開示されている。非特許文献３によれば、マルチキャスト制御方式には大きく分けてツリー型方式とメッシュ型方式とがある。ツリー型方式は、ある代表ノードを決定し、マルチキャストの送信者および受信者（メンバー）はその代表ノードに向かってJoinを行い、マルチキャスト配信ツリーを構築する。メッシュ型方式の場合、各（送信ノード、受信ノード）ペア間にそれぞれ経路を構築する。前述のM-OLSRもメッシュ型方式の一種である。
【００１０】
しかしながら、上述した従来のメッシュ型マルチキャスト経路制御方式では、送信ノードと受信ノードとの組に対してそれぞれ経路を構築するため、設定する経路数が多くなり、必要な制御メッセージ量も多くなる。そのため、帯域の狭いネットワークでは利用が困難になってしまう。また、経路数の増加に伴い、マルチキャストパケットを転送するノード数が多くなり、互いのパケット送信が干渉して通信劣化（パケットの衝突、パケットロス、遅延の増加等）を引き起こす確率が高くなってしまう。
【００１１】
そこで、自ノードの移動速度を含む移動情報を用いて他ノードとの間に送受信される制御パケットの交換頻度を調整する技術が考えられている（例えば、特許文献１参照）。
【特許文献１】特許第３８９３６２０号公報
【非特許文献１】T. Clausen他、“Optimized Link State Routing Protocol for Ad Hoc Networks”、IEEE INMIC、2001年12月
【非特許文献２】Anis Laouiti他、“Multicast Optimized Link State Routing”、Inria Research Report No.4721、2003年2月、(ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-4721.pdf)
【非特許文献３】Carlos de Morais他、“Multicast over Wireless Mobile Ad HHoc Networks:Present and Future Directions”、IEEE Network Magazine、Jan/Feb 2003
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、特許文献１に記載された技術においては、自ノードの移動速度を測定しなければならなく、その手間を省くものが好ましい。
【００１３】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、帯域の狭い無線ネットワークにおいて通信品質の高いマルチキャスト通信を容易に実現することができる無線マルチホップネットワーク、ノード、マルチキャスト経路制御方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために本発明は、
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成する無線マルチホップネットワークにおいて、
前記ノードは、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得するユニキャスト経路制御情報取得部と、
前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算するリレーノードセット計算部と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算するマルチキャスト経路計算部と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する経路登録部とを有することを特徴とする。
【発明の効果】
【００１５】
以上説明したように本発明においては、他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから複数のノードの情報であるユニキャスト経路制御情報を取得し、ユニキャスト経路制御情報を用いて、すべてのマルチキャスト送信ノードをカバーする送信リレーノードセットと、すべてのマルチキャスト受信ノードをカバーする受信リレーノードセットとを計算し、計算された送信リレーノードセットに含まれるノードと計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算し、計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する構成としたため、帯域の狭い無線ネットワークにおいて通信品質の高いマルチキャスト通信を容易に実現することができる。
【発明を実施するための最良の形態】
【００１６】
以下に、本発明の実施の形態について図面を参照して説明する。
【００１７】
図１は、本発明の無線マルチホップネットワークの実施の一形態を示す図である。無線マルチホップネットワークでは、通信ノード間でパケットの転送を行い、送信通信ノード送信ノード）から宛先通信ノード（受信ノード）までパケットを届ける。通信ノードは自分の無線信号が届く範囲内に存在する任意の通信ノードと直接通信することができる。また、本実施の形態におけるユニキャストの経路制御は、非特許文献１に開示されたOLSRで制御されているとし、本発明のマルチキャスト経路制御方法はOLSRをベースとして拡張する。
【００１８】
本形態は図１に示すように、通信装置であるノード１１〜１６，２１〜２２，３１〜３３から構成されている。図１においては、互いのノード１１〜１６，２１〜２２，３１〜３３間の点線は無線で直接通信可能なノードの関係を示している。通信ノードはそれぞれ固有のノードID及びIPアドレスを持っている。IPアドレスはノード固有の値であるため、ノードIDにはIPアドレスを用いても良い。
【００１９】
ノード２１〜２２は、マルチキャストの送信を行うマルチキャスト送信ノードである。ノード３１〜３３は、マルチキャストの受信を行うマルチキャスト受信ノードである。ノード１１〜１６は、マルチキャストの転送のみを行い、マルチキャストの送信と受信とのいずれも行わないノードである。
【００２０】
図２は、図１に示したノード１１の一構成例を示す図である。
【００２１】
図１に示したノード１１には図２に示すように、TCメッセージ送信部１０１と、TCメッセージ受信部１０２と、ユニキャスト経路制御情報取得部１０３と、リレーノードセット計算部１０４と、マルチキャスト経路計算部１０５と、経路登録部１０６と、マルチキャスト転送テーブル１０７とが設けられている。なお、図２に示した構成要素は、本発明に関わるもののみである。また、ノード１２〜１６，２１〜２２，３１〜３３についてもノード１１と同じ構成要素が設けられている。
【００２２】
TCメッセージ送信部１０１は、ノード１１の接続情報を示すユニキャスト経路制御メッセージであるTC（Topology Control）メッセージを他のノードへ送信する。そのとき、マルチキャスト情報を含めて送信する。
【００２３】
TCメッセージ受信部１０２は、他のノードから送信されてきたTCメッセージを受信する。
【００２４】
ユニキャスト経路制御情報取得部１０３は、TCメッセージ受信部１０２にて受信されたTCメッセージから、ノード１２〜１６，２１〜２２，３１〜３３の情報であるユニキャスト経路制御情報を取得する。
【００２５】
リレーノードセット計算部１０４は、ユニキャスト経路制御情報取得部１０３にて取得されたユニキャスト経路制御情報を用いて、送信ノードであるノード２１〜２２をカバーする送信リレーノードセットを計算する。また、ユニキャスト経路制御情報を用いて、受信ノードであるノード３１〜３３をカバーする受信リレーノードセットを計算する。
【００２６】
マルチキャスト経路計算部１０５は、リレーノードセット計算部１０４にて計算された送信リレーノードセットに含まれるノードと受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算する。
【００２７】
経路登録部１０６は、マルチキャスト経路計算部１０５にて計算されたマルチキャスト経路をマルチキャスト転送テーブル１０７へ登録する。
【００２８】
マルチキャストの送信および受信を行うノードは、OLSRのHelloメッセージに以下のJoin情報を付加して、Helloメッセージを送信する。
【００２９】
（グループアドレス：送受信情報）
Helloメッセージは、ユニキャストと同様に定期的に送信されてもよく、また新たなJoinが発生した時点で適宜送信されても良い。グループアドレスは、送信または受信したいマルチキャストを識別するためのグループアドレスである。送受信情報は、自身がそのグループに対して送信者であるか受信者であるかまたはその両方であるかを示す情報である。
【００３０】
Join情報を含むHelloメッセージを隣接ノードから受信した場合、ノードはその隣接ノードが自身をMPR（Multi Point Reply）ノードに選択しているかどうかをチェックする。これは、Helloメッセージを用いて知ることができる。もし、その隣接ノードが自身をMPRノードとして選択している場合、そのノードはTCメッセージに以下のマルチキャスト情報を含めてTCメッセージ送信部１０１から送信する。
【００３１】
（グループアドレス：ノードリスト）
また、TCメッセージがマルチキャスト情報を含まずに送信されるものであっても良い。この場合、当該マルチキャスト情報は、マルチキャスト経路制御メッセージに含まれて送信される。
【００３２】
TCメッセージは、ユニキャストと同様に定期的に送信されてもよく、また新たな送受信ノードが発生した時点で適宜送信されても良い。グループアドレスは、送受信するマルチキャストを識別するためのグループアドレスである。ノードリストは、自身をMPRノードに選択しているマルチキャストの送信ノードおよび受信ノードのリストである。自身が送信ノードまたは受信ノードである場合は、自身もリストに含める。ノードリストは、以下の情報のリストで構成されている。
【００３３】
（ノードID：送受信情報）
図１では、ノード３１〜３３は、グループGの受信ノードとしてHelloメッセージにJoin情報を付加する。ノード２１〜２２は、グループGの送信ノードとしてHelloメッセージにJoin情報を付加する。
【００３４】
ノード３１はノード１１とノード１４とをMPRノードに選択している。また、ノード３２はノード１４をMPRノードに選択している。また、ノード３３はノード１３をMPRノードに選択している。また、ノード２１はノード１３とノード１６とをMPRノードに選択している。また、ノード２２はノード１３とノード１６とをMPRノードに選択している。MPRノードはユニキャスト経路制御においてOLSRと同じ方式で選択される。
【００３５】
ノード１１，１３，１４，１６は、TCメッセージにマルチキャスト情報を含めて送信する。例えば、ノード１３がTCメッセージに含めるマルチキャスト情報は、以下のようになる。
【００３６】
[グループG：[(ノード２１：送信),(ノード２２：送信),(ノード３３：受信)]]
また、TCメッセージがマルチキャスト情報を含まずに送信されるものであっても良い。この場合、当該マルチキャスト情報は、マルチキャスト経路制御メッセージに含まれて送信される。
【００３７】
MPRノードが送信したTCメッセージは、ネットワーク全体に配信される。各ノードは新たなTCメッセージを受信すると、ユニキャスト経路の計算とともにマルチキャスト経路の計算を開始する。ユニキャスト経路の計算はOLSRと同様であるため省略し、ここではマルチキャスト経路の計算について説明する。
【００３８】
ノードは、はじめに送信リレーノードセットである最小送信MPRセット（Least Sender MPR Set:以下、LSMと称する）と受信リレーノードセットである最小受信MPRセット（Least Receiver MPR Set:以下、LRMと称する）とを計算する。LSMは全送信ノードをカバーする最小のMPRノードの集合である。また、LRMは全受信ノードをカバーする最小のMPRノードの集合である。全てのノードが一意にLSM及びLRMを決定するため、以下の手順でLSM及びLRMを計算する。
・LSMの計算方法
図３は、図１に示した形態におけるLSMの計算方法を説明するためのフローチャートである。
【００３９】
まずは、これまでにTCメッセージ受信部１０２にて受信した有効なTCメッセージから、下記の情報（S, S(m), SN(m), RN(m), W(m)）をユニキャスト経路制御情報取得部１０３にて取得する。これらのノードの情報は、ユニキャスト経路制御情報である。
【００４０】
S : TCで広告された全送信ノードの集合
S(m) : MPR mが広告した送信ノードの集合
SN(m) : MPR mが広告した送信ノードの中でSに含まれている送信ノードの数
RN(m) : MPR mが広告した受信ノードの数
W(m) : MPR mのWillingness
ここで、WillingnessとはOLSRで定義されたノードのパケット転送意思を示す値である。一般に「０」〜「７」の範囲の数値で示され、パケット転送能力が高いノードほど、Willingness値を高く設定する。
【００４１】
これらの情報について、Sが空になるまで、リレーノードセット計算部１０４にて以下に示す（１）〜（９）の処理を繰り返してLSM及びSF(m)を計算する。このとき、MPRノードの選択された順番も覚えておく。ここで、
LSM : 最小送信MPRの集合
SF(m) : MPR mがパケット転送に責任を持つ送信ノードの集合
である。
【００４２】
（１）SN(m)が最大である送信MPR mを選択する（ステップＳ４１）。
【００４３】
（２）（１）で複数のmが存在する場合（ステップＳ４２）、m自身が送信ノードであるのものを選択する（ステップＳ４３）。
【００４４】
（３）（２）で複数のmが存在する場合（ステップＳ４４）、RN(m)が最大のものを選択する（ステップＳ４５）。
【００４５】
（４）（３）で複数のmが存在する場合（ステップＳ４６）、W(m)が最大のものを選択する（ステップＳ４７）。
【００４６】
（５）（４）で複数のmが存在する場合（ステップＳ４８）、アドレス（ノードID）が最小のmを選択する（ステップＳ４９）。
【００４７】
（６）（１）〜（５）で一意に決定されたmをLSMに追加する（ステップＳ５０）。
【００４８】
（７）SからS(m)に含まれる送信ノードを除く（ステップＳ５１）。
【００４９】
（８）（７）でSから除かれた送信ノードをSF(m)に追加する（ステップＳ５２）。
【００５０】
（９）全MPRに対して（７）で更新した新しいSでSN(m)を再計算する（ステップＳ５３）。
【００５１】
LRMもLSMと同様に以下のように計算する。
・LRMの計算方法
図４は、図１に示した形態におけるLRMの計算方法を説明するためのフローチャートである。
【００５２】
まずは、これまでにTCメッセージ受信部１０２にて受信した有効なTCメッセージから、下記の情報（R, R(m), RN(m), SN(m), W(m)）をユニキャスト経路制御情報取得部１０３にて取得する。これらのノードの情報は、ユニキャスト経路制御情報である。
【００５３】
R : TCで広告された全受信ノードの集合
R(m) : MPR mが広告した受信ノードの集合
RN(m) : MPR mが広告した受信ノードの中でRに含まれている受信ノードの数
SN(m) : MPR mが広告した送信ノードの数
W(m) : MPR mのWillingness
これらの情報について、Rが空になるまで、リレーノードセット計算部１０４にて（１１）〜（１９）の処理を繰り返し、LRM及びRF(m)を計算する。このとき、MPRノードの選択された順番も覚えておく。ここで、
LRM : 最小受信MPRの集合
RF(m) : MPR mがパケット転送に責任を持つ受信ノードの集合
である。
【００５４】
（１１）RN(m)が最大であるMPR mを選択する（ステップＳ６１）。
【００５５】
（１２）（１１）で複数のmが存在する場合（ステップＳ６２）、m自身が受信ノードであるものを選択する（ステップＳ６３）。
【００５６】
（１３）（１２）で複数のmが存在する場合（ステップＳ６４）、SN(m)が最大のものを選択する（ステップＳ６５）。
【００５７】
（１４）（１３）で複数のmが存在する場合（ステップＳ６６）、W(m)が最大のものを選択する（ステップＳ６７）。
【００５８】
（１５）（１４）で複数のmが存在する場合（ステップＳ６８）、アドレス（ノードID）が最小のmを選択する（ステップＳ６９）。
【００５９】
（１６）（１１）〜（１５）で一意に決定されたmをLRMに追加する（ステップＳ７０）。
【００６０】
（１７）RからR(m)に含まれる受信ノードを除く（ステップＳ７１）。
【００６１】
（１８）（１７）でRから除かれた受信ノードをRF(m)に追加する（ステップＳ７２）。
【００６２】
（１９）全MPRに対して（１７）で更新した新しいRでRN(m)を再計算する（ステップＳ７３）。
【００６３】
以上の計算によって、以下に示すようなLRM及びLSMが得られる。
【００６４】
図５は、図１に示した形態におけるLSM及びLRMを示す図である。
【００６５】
図５に示すように、受信ノードセット２０４である全受信ノード３１〜３３をカバーする受信MPRセット２０５であるMPRノードは、ノード１１、ノード１３及びノード１４である。ここで、ノード１１がカバーするノード３２をノード１４もカバーしているため、ノード１３及びノード１４が最小受信MPRセット（LRM）２０６となる。順番は、ノード１４のほうがノード１３よりもカバーする受信ノード数が多いため、｛ノード１４，ノード１３｝となる。また、送信ノードセット２０１である全送信ノード２１〜２２をカバーする送信MPRセット２０２であるMPRノードは、ノード１３及びノード１６である。ここで、ノード１３はノード３３もカバーしているため、最小送信MPRセット（LSM）２０３は｛ノード１３｝となる。
【００６６】
LSMとLRMとの計算が終了すると、次にLSM内のノードとLRM内のノードとの間のマルチキャスト経路２０７の計算をマルチキャスト経路計算部１０５にて開始する。全ノードが一意に経路を決定するため、以下のような計算を行う。
【００６７】
LSMのi番目の送信MPRをSMi、LRMのj番目の受信MPRをRMjとする。各i,jに対して、SMi→RMjへの最短経路を計算する。計算はTCメッセージのトポロジー情報のみを用いて、Dijkstraアルゴリズムで計算する。等コスト最短経路は全て計算し、全最短経路を覚えておく。ノードmの転送コストは、Willingnessを使い(Will_always - W(m) + 1)とする。ここで、Will_alwaysとは、値が「７」であるWillingnessである。
【００６８】
また、送信MPR SMiからRM1〜RMjへの経路がなるべく重なるよう計算するために、SMi → RMk への経路の計算時には、SMi → RM1〜RMk-1の計算までにすでに計算された経路上のリンクに対して、メトリックを一定値だけ減算する。さらに、転送時の干渉を避けるため、SMi → RM1〜RMk-1 の計算までにすでに計算された経路上のリンクと干渉するリンクに対して、メトリックを一定値だけ加算し、干渉しにくいリンクを通る経路を計算する。
【００６９】
最短経路が複数有る場合、各ノードが一意に最短経路を決定するため、以下の手順で一意に経路を決定する。
【００７０】
図６は、図１に示した形態におけるマルチキャスト経路の計算方法を説明するためのフローチャートである。以下の（２１）〜（２４）の処理を、経路が一意に決まるまで繰り返し、マルチキャスト経路を計算する。
【００７１】
（２１）Hop数が最短のものを選択する（ステップＳ８１）。
【００７２】
（２２）（２１）が複数ある場合（ステップＳ８２）、経路中のノードのWillingnessの合計値が最大のものを選択する（ステップＳ８３）。
【００７３】
（２３）（２１）及び（２２）が複数ある場合（ステップＳ８４）、経路中のノードIDが最小のものを選択する（ステップＳ８５）。
【００７４】
（２４）（２１）〜（２３）が複数ある場合（ステップＳ８６）、最小IDのノードを除いたノードの中で、最小ノードIDを持つ経路を選択する（ステップＳ８７）。
【００７５】
以上説明したLSMの計算方法、LRMの計算方法及びマルチキャスト経路の計算方法によるマルチキャスト経路制御方法を用いて、通信品質の高いマルチキャスト通信を容易に実現するためのマルチキャスト経路を求めることができる。
【００７６】
図７は、図１に示した形態において、図３、図４及び図６を用いて説明したマルチキャスト経路制御方法を用いて求められたマルチキャスト経路を示す図である。ここでは、全てのノードのWillingnessは同じであると仮定している。
【００７７】
また、図８は、一般的なメッシュ型方式において送信ノードと受信ノードとの対毎に作成されたマルチキャスト経路の一例を示す図である。
【００７８】
図７に示したマルチキャスト経路と、図８に示したマルチキャスト経路とを比較すると、図８に示したマルチキャスト経路よりも、図７に示したマルチキャスト経路の方が、経路の数が少ないことが明らかである。
【００７９】
マルチキャスト経路の計算が終了すると、各ノードは計算した経路に沿って経路登録部１０６によってマルチキャスト転送テーブル１０７にエントリを設定する。
【００８０】
ノード１１〜１４の各ノードは、以下のエントリをマルチキャスト転送テーブルに設定する。
・ノード１１：
宛先：G、送信ノード：ノード２１、上流ノード：ノード１２
宛先：G、送信ノード：ノード２２、上流ノード：ノード１２
・ノード１２：
宛先：G、送信ノード：ノード２１、上流ノード：ノード１３
宛先：G、送信ノード：ノード２２、上流ノード：ノード１３
・ノード１３：
宛先：G、送信ノード：ノード２１、上流ノード：ノード２１
宛先：G、送信ノード：ノード２２、上流ノード：ノード２２
・ノード１４：
宛先：G、送信ノード：ノード２１、上流ノード：ノード１１
宛先：G、送信ノード：ノード２２、上流ノード：ノード１１
ただし、SMiから[RM1,…,RMj]への経路中にSF(SMi)の送信ノードが含まれている場合（その送信ノードをｘとする）、xは、IP Src = xでSMiから受信したマルチキャストパケットは転送しない。つまりSrc=x, Dest=G, Up=SMiのマルチキャスト経路を設定しない。
【００８１】
図９は、通信経路中に送信ノードが含まれている場合に設定されるマルチキャストの一例を示す図である。ここで、s１〜s４は送信ノードであり、r１〜r４は受信ノードである。
【００８２】
図９に示すように、LSM=[A]，LRM＝[C，E]であり、A→Cへの最短経路はA→s１→B→Cである。この場合、経路上にSF(A)=[s１，s２，s３，s４]のノードが含まれているため、s１が送信したパケットはs１→A→s１→B→Cと冗長に転送されることになる。そこでs１は、送信ノード=s１，宛先=G，上流ノード=Aの経路は登録しないようにする。Aはs１から受信したマルチキャストパケットは転送するよう経路を設定する。つまり、送信ノードであるs１が転送ノードとして存在する場合、s１は、s１から送信されてきたマルチキャストパケットの経路のマルチキャスト転送テーブルへの登録を回避する。これによりs１が送信したマルチキャストパケットは、s１→B→C及びs１→A→Eで転送され、全受信ノードに到達する。
ノードAが設定する経路表（マルチキャスト転送テーブル１０７）は以下のとおりである。
【００８３】
宛先：G、送信ノード：s１、上流ノード：s１
宛先：G、送信ノード：s２、上流ノード：s２
宛先：G、送信ノード：s３、上流ノード：s３
宛先：G、送信ノード：s４、上流ノード：s４
ｓ１は以下のように経路を登録する。
【００８４】
宛先：G、送信ノード：s２、上流ノード：A
宛先：G、送信ノード：s３、上流ノード：A
宛先：G、送信ノード：s４、上流ノード：A
上記実施の形態では、LSMの計算方法の送信MPRノード選択手順（１）においてSN(SMi)が最大のMPRノードを優先的に選択する。しかし、下記のように、カバーする送信ノード数と送信ノードから受信ノードまでの経路長である経路コストとの双方を考慮してMPR mを選択することも可能である。
【００８５】
LSMの計算に先立ち、全送信MPR（SMi）から全受信MPR（RMj）への最短経路コストを計算しておく。SMi→RMjへの最短経路のコストをCijとする。
【００８６】
LSMの計算方法の送信MPR選択手順（１）は、以下のようになる。
【００８７】
（１）SN(m) / (Ci１+ Ci２+ … + Cij)が最大であるMPR mを選択する。
【００８８】
また同様に、カバーする受信ノード数と送信ノードから受信ノードまでの経路長である経路コストとの双方を考慮してMPR mを選択することも可能である。
【００８９】
以上説明したように、本発明の通信ノードでは、ユニキャスト経路制御メッセージを使ってマルチキャスト情報を送信することにより、マルチキャストのための制御メッセージ負荷を低減する。
【００９０】
また、ユニキャスト経路制御情報を使って、マルチキャスト送信ノードを全てカバーする送信リレーノードセットと、マルチキャスト受信ノードを全てカバーする受信リレーノードセットとを計算し、送信リレーノードセット内のノードと受信リレーノードセット内のノードとの間のマルチキャスト経路を計算することで、マルチキャスト経路数の増加を抑制する。マルチキャスト経路数を少なくすることで、干渉の少ないマルチキャスト配信ツリーを構築することができる。また、パケット転送時の干渉を軽減し、通信品質を向上させることができる。
【００９１】
これにより、本発明では制御負荷を抑えながら無線に適した干渉の少ないマルチキャスト経路制御が可能となる。
【００９２】
そして、干渉を減らすことにより、CSMA/CAで制御される無線ネットワークでは、衝突を回避しスループットを改善することができる。また、TDMAで制御される無線ネットワークでは、マルチキャスト配信のために必要なタイムスロット数を減らすことができ、リソース効率を向上させることができる。
【００９３】
また、上述した処理は、目的に応じて作製された論理回路で行うようにしても良い。また、処理内容を記述した各ノードにて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムを各ノードに読み込ませ、実行するものであっても良い。各ノードにて読取可能な記録媒体とは、フロッピーディスク（登録商標）、光磁気ディスク、ＤＶＤ、ＣＤなどの移設可能な記録媒体の他、各ノードに内蔵されたＨＤＤ等を指す。この記録媒体に記録されたプログラムは、各ノード内のＣＰＵ（不図示）にて読み込まれ、ＣＰＵの制御によって、上述したものと同様の処理が行われる。ここで、ＣＰＵは、プログラムが記録された記録媒体から読み込まれたプログラムを実行するコンピュータとして動作するものである。
【図面の簡単な説明】
【００９４】
【図１】本発明の無線マルチホップネットワークの実施の一形態を示す図である。
【図２】図１に示したノードの一構成例を示す図である。
【図３】図１に示した形態におけるLSMの計算方法を説明するためのフローチャートである。
【図４】図１に示した形態におけるLRMの計算方法を説明するためのフローチャートである。
【図５】図１に示した形態におけるLSM及びLRMを示す図である。
【図６】図１に示した形態におけるマルチキャスト経路の計算方法を説明するためのフローチャートである。
【図７】図１に示した形態において、図３、図４及び図６を用いて説明したマルチキャスト経路制御方法を用いて求められたマルチキャスト経路を示す図である。
【図８】一般的なメッシュ型方式において送信ノードと受信ノードとの対毎に作成されたマルチキャスト経路の一例を示す図である。
【図９】通信経路中に送信ノードが含まれている場合に設定されるマルチキャストの一例を示す図である。
【符号の説明】
【００９５】
１１〜１６，２１〜２２，３１〜３３ ノード
２０１ 送信ノードセット
２０２ 送信MPRセット
２０３ 最小送信MPRセット(LSM)
２０４ 受信ノードセット
２０５ 受信MPRセット
２０６ 最小受信MPRセット(LRM)
２０７ マルチキャスト経路
【特許請求の範囲】
【請求項１】
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成する無線マルチホップネットワークにおいて、
前記ノードは、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得するユニキャスト経路制御情報取得部と、
前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算するリレーノードセット計算部と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算するマルチキャスト経路計算部と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する経路登録部とを有することを特徴とする無線マルチホップネットワーク。
【請求項２】
請求項１に記載の無線マルチホップネットワークにおいて、
前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信するTCメッセージ送信部を有することを特徴とする無線マルチホップネットワーク。
【請求項３】
請求項１に記載の無線マルチホップネットワークにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算することを特徴とする無線マルチホップネットワーク。
【請求項４】
請求項１に記載の無線マルチホップネットワークにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算することを特徴とする無線マルチホップネットワーク。
【請求項５】
請求項１に記載の無線マルチホップネットワークにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とする無線マルチホップネットワーク。
【請求項６】
請求項１に記載の無線マルチホップネットワークにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とする無線マルチホップネットワーク。
【請求項７】
請求項１に記載の無線マルチホップネットワークにおいて、
前記経路登録部は、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避することを特徴とする無線マルチホップネットワーク。
【請求項８】
互いに無線を用いて情報を交換してマルチホップネットワークを形成するノードであって、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとからノードの情報であるユニキャスト経路制御情報を取得するユニキャスト経路制御情報取得部と、
前記ユニキャスト経路制御情報を用いて、すべてのマルチキャスト送信ノードをカバーする送信リレーノードセットと、すべてのマルチキャスト受信ノードをカバーする受信リレーノードセットとを計算するリレーノードセット計算部と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算するマルチキャスト経路計算部と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する経路登録部とを有するノード。
【請求項９】
請求項８に記載のノードにおいて、
前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信するTCメッセージ送信部を有することを特徴とするノード。
【請求項１０】
請求項８に記載のノードにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算することを特徴とするノード。
【請求項１１】
請求項８に記載のノードにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算することを特徴とするノード。
【請求項１２】
請求項８に記載のノードにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とするノード。
【請求項１３】
請求項８に記載のノードにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とするノード。
【請求項１４】
請求項８に記載のノードにおいて、
前記経路登録部は、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避することを特徴とするノード。
【請求項１５】
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成するためのマルチキャスト経路制御方法であって、
前記ノードが、他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得する処理と、
前記ノードが、前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算する処理と、
前記ノードが、前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算する処理と、
前記ノードが、前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する処理とを有するマルチキャスト経路制御方法。
【請求項１６】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項１７】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項１８】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項１９】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項２０】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項２１】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項２２】
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成するためにコンピュータに実行させるプログラムであって、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得する手順と、
前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算する手順と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算する手順と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する手順とをコンピュータに実行させるプログラム。
【請求項２３】
請求項２２に記載のプログラムにおいて、
前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２４】
請求項２２に記載のプログラムにおいて、
前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２５】
請求項２２に記載のプログラムにおいて、
前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２６】
請求項２２に記載のプログラムにおいて、
前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２７】
請求項２２に記載のプログラムにおいて、
前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２８】
請求項２２に記載のプログラムにおいて、
前記ノードが、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項１】
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成する無線マルチホップネットワークにおいて、
前記ノードは、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得するユニキャスト経路制御情報取得部と、
前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算するリレーノードセット計算部と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算するマルチキャスト経路計算部と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する経路登録部とを有することを特徴とする無線マルチホップネットワーク。
【請求項２】
請求項１に記載の無線マルチホップネットワークにおいて、
前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信するTCメッセージ送信部を有することを特徴とする無線マルチホップネットワーク。
【請求項３】
請求項１に記載の無線マルチホップネットワークにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算することを特徴とする無線マルチホップネットワーク。
【請求項４】
請求項１に記載の無線マルチホップネットワークにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算することを特徴とする無線マルチホップネットワーク。
【請求項５】
請求項１に記載の無線マルチホップネットワークにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とする無線マルチホップネットワーク。
【請求項６】
請求項１に記載の無線マルチホップネットワークにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とする無線マルチホップネットワーク。
【請求項７】
請求項１に記載の無線マルチホップネットワークにおいて、
前記経路登録部は、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避することを特徴とする無線マルチホップネットワーク。
【請求項８】
互いに無線を用いて情報を交換してマルチホップネットワークを形成するノードであって、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとからノードの情報であるユニキャスト経路制御情報を取得するユニキャスト経路制御情報取得部と、
前記ユニキャスト経路制御情報を用いて、すべてのマルチキャスト送信ノードをカバーする送信リレーノードセットと、すべてのマルチキャスト受信ノードをカバーする受信リレーノードセットとを計算するリレーノードセット計算部と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算するマルチキャスト経路計算部と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する経路登録部とを有するノード。
【請求項９】
請求項８に記載のノードにおいて、
前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信するTCメッセージ送信部を有することを特徴とするノード。
【請求項１０】
請求項８に記載のノードにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算することを特徴とするノード。
【請求項１１】
請求項８に記載のノードにおいて、
前記マルチキャスト経路計算部は、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算することを特徴とするノード。
【請求項１２】
請求項８に記載のノードにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とするノード。
【請求項１３】
請求項８に記載のノードにおいて、
前記リレーノードセット計算部は、前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択することを特徴とするノード。
【請求項１４】
請求項８に記載のノードにおいて、
前記経路登録部は、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避することを特徴とするノード。
【請求項１５】
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成するためのマルチキャスト経路制御方法であって、
前記ノードが、他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得する処理と、
前記ノードが、前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算する処理と、
前記ノードが、前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算する処理と、
前記ノードが、前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する処理とを有するマルチキャスト経路制御方法。
【請求項１６】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項１７】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項１８】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項１９】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項２０】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項２１】
請求項１５に記載のマルチキャスト経路制御方法において、
前記ノードが、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避する処理を有することを特徴とするマルチキャスト経路制御方法。
【請求項２２】
マルチキャスト送信ノードとマルチキャスト受信ノードとを含む複数のノードが、互いに無線を用いて情報を交換してマルチホップネットワークを形成するためにコンピュータに実行させるプログラムであって、
他のノードから送信されてきたマルチキャスト情報とノードの接続情報を示すユニキャスト経路制御メッセージとから前記複数のノードの情報であるユニキャスト経路制御情報を取得する手順と、
前記ユニキャスト経路制御情報を用いて、すべての前記マルチキャスト送信ノードをカバーする送信リレーノードセットと、すべての前記マルチキャスト受信ノードをカバーする受信リレーノードセットとを計算する手順と、
前記計算された送信リレーノードセットに含まれるノードと前記計算された受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を計算する手順と、
前記計算されたマルチキャスト経路をマルチキャスト転送テーブルに設定する手順とをコンピュータに実行させるプログラム。
【請求項２３】
請求項２２に記載のプログラムにおいて、
前記マルチキャスト情報を、前記ユニキャスト経路制御メッセージに含めて送信する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２４】
請求項２２に記載のプログラムにおいて、
前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクに対して、メトリックを所定の値だけ減算して計算する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２５】
請求項２２に記載のプログラムにおいて、
前記送信リレーノードセットに含まれるノードと前記受信リレーノードセットに含まれるノードとの間のマルチキャスト経路を、すでに計算されたマルチキャスト経路上のリンクと干渉するリンクに対して、メトリックを所定の値だけ加算して計算する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２６】
請求項２２に記載のプログラムにおいて、
前記マルチキャスト送信ノードの数と前記マルチキャスト受信ノードの数とに基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２７】
請求項２２に記載のプログラムにおいて、
前記マルチキャスト送信ノードと前記マルチキャスト受信ノードとの間の経路長に基づいて、前記送信リレーノードセットと前記受信リレーノードセットとを選択する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【請求項２８】
請求項２２に記載のプログラムにおいて、
前記ノードが、前記マルチキャスト経路上に前記マルチキャスト送信ノードが転送ノードとして存在する場合、当該ノードから送信されてきたマルチキャストパケットのマルチキャスト経路のマルチキャスト転送テーブルへの登録を回避する手順をさらにコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００９−７１５７５（Ｐ２００９−７１５７５Ａ）
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願番号】特願２００７−２３７６５７（Ｐ２００７−２３７６５７）
【出願日】平成１９年９月１３日（２００７．９．１３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願日】平成１９年９月１３日（２００７．９．１３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]