パケット中継システム及び無線ノード
【課題】ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できるパケット中継システムを提供する。
【解決手段】パケット中継システムに含まれる各ノードは、ツリー状に構成され、隣接ノード１つからのパケットを所定の送信タイミングが到来するまで保持し、当該送信タイミングが到来するまでに他の隣接ノードからのパケットを受信した場合に当該受信パケットに含まれるアドレスと、当該保持パケットに含まれるアドレスと、自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成し、当該送信タイミングの到来に応じて最上位ノード側に位置する隣接ノードへ当該集約パケットを中継する。
【解決手段】パケット中継システムに含まれる各ノードは、ツリー状に構成され、隣接ノード１つからのパケットを所定の送信タイミングが到来するまで保持し、当該送信タイミングが到来するまでに他の隣接ノードからのパケットを受信した場合に当該受信パケットに含まれるアドレスと、当該保持パケットに含まれるアドレスと、自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成し、当該送信タイミングの到来に応じて最上位ノード側に位置する隣接ノードへ当該集約パケットを中継する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データパケットを相互に中継する複数のノードを含むパケット中継システムに関する。
【背景技術】
【０００２】
パケット中継機能を有する複数の無線ノードによってネットワークを構成し、互いに隣接している無線ノード間で相互にパケットを中継するマルチホップ無線ネットワークが知られている。無線ノード間でパケットを順次中継することにより、電波が直接届かない無線ノードへパケットを転送することができる。
【０００３】
パケットを所望の無線ノードに中継するためには、宛先アドレスから次に転送すべき無線ノードを決定するためのルーティングプロトコルが必要とされる。例えばジグビー（ＺｉｇＢｅｅ（登録商標））アライアンスでは、アドレスの割り当て方法を工夫することによりルーティングテーブルが不要となるクラスタツリールーティング方式、メッシュトポロジーの構成できるＡＯＤＶ（Ad Hoc On-Demand Distance Vector）方式、複数のノードからデータを効率的に収集できるメニートゥーワン（Many to One）方式などによるルーティングプロトコルが標準化されている。特にメニートゥーワン方式は、シンクノードと複数のノードとの間の１対ｎの通信について考慮された方式であるので、環境情報のセンシングやメータの自動検針などのアプリケーションへの適用が期待されている。
【０００４】
図２２は、メニートゥーワン方式におけるルーティング時のノード間のパケット中継の態様を表す模式図である。図２２（ａ）は、ノードｂ〜ｊの各々が、シンクノードであるノードａへパケットを中継するための上り経路を設定するときのＲＲＥＱ（Route Request）パケット中継の態様を表す模式図である。ノードａは、送信先アドレスをブロードキャストアドレスとして、ＲＲＥＱパケットを送信する。ＲＲＥＱパケットを受信したノードは、他のノードへＲＲＥＱパケットを中継する。ＲＲＥＱパケットには、ネットワーク上における任意の２つのノード間の論理的な距離を表すパスコストが含まれている。ＲＲＥＱパケットの中継時には、自身に隣接しているノードについてのリンクコストをパスコストに加算して送信する。リンクコストは、ネットワーク上におけるノード間の論理的な距離を表すものであり、パスコスト算出の基礎となるコストである。リンクコストは、ノード間の受信強度やパケットエラー率などから算出される。このようにＲＲＥＱパケットの中継を繰り返すことにより、ノードｂ〜ｊの各々は、シンクノードａへパケットを転送するための上り経路を設定することができる。つまり、ノードｂ〜ｊの各々は、例えば最も小さいパスコストに対応するノードをパケット中継先のノードとして選択することにより、最適な条件にてパケットをシンクノードへ中継することができる。
【０００５】
図２２（ｂ）は、シンクノードであるノードａからノードｈへの下り経路を設定するときのＲＲＥＣ（Route Record）パケット中継の態様を表す模式図である。ノードｈは、宛先をノードａとし、自身のアドレスを含めたＲＲＥＣパケットを送信する。ＲＲＥＣパケットを受信したノードは自身のアドレス及び中継回数を含めたＲＲＥＣパケットを転送先のノードへ転送する。つまり、ノードｈからｄ、ｃ、ｂ、ａの順にアドレスが追加されたパケットがノードａに転送される。ノードａから他のノードへの下り経路を設定するときも同様の処理がなされる。
【０００６】
図２２（ｃ）は、下り経路設定後にノードａからノードｈへのパケット中継の態様を表す模式図である。ノードａは、下り経路設定時におけるアドレス追加順と逆順にしたアドレスをパケットヘッダに記載してデータパケットを送信する。データパケットを受信したノードは、パケットヘッダ内に記載されている自身のアドレスを削除して転送先のノードへ転送する。このようにして、ノードａからｂ、ｃ、ｄ、ｈの順にデータパケットを中継できる。これらのルーティングは、送信元ノード（ソースノード）が、パケットを中継するノードを一意に決定する経路制御であるので、ソースルーティングと呼ばれている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】ZigBeeSpecification Revision17 (ZigBee Document 053474r17)
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来のメニートゥーワン方式におけるルーティングにおいては、リンクコストの算出方法が明確でなかった。非特許文献１では、ＬＱＩ（Link Qulity Indicator）などの要素からリンクコストを算出するとしているが、ＲＲＥＱコマンドを受信した際のＬＱＩにはばらつきがあるので、正確なリンクコストを算出するのが困難であるという問題があった。特に屋外など広範囲に亘る場所にノードを設置した場合、ノード間を人や自動車などの遮蔽物が通過したとき、ノード間のリンクの瞬断が生じ、リンク状況が変動してしまう。そのため、リンク状況が変動した場合においても、適切なリンクコストを算出できるシステムが要望されている。
【０００９】
また、従来のメニートゥーワン方式におけるルーティングにおいては、シンクノードへの上り経路を確立するために、上記した図２２(ａ)の如くRＲＥＱパケットを定期的にブロードキャスト送信する必要があった。ＲＲＥＱパケットは、各ノードで一度は再送され、ネットワーク全体に配送されるので、ネットワークの規模が大きくなるほどネットワーク内の通信情報量が増加し、無線帯域の利用効率が悪化するという問題があった。そのため、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できるシステムが要望されている。
【００１０】
また、従来のメニートゥーワン方式におけるルーティングにおいては、シンクノードからの下り経路を確立するために、上記した図２２(ｂ)の如く各ノードはユニキャスト送信によりシンクノードへＲＲＥＣコマンドを送信するので、各ノードにおける送信タイミングが重なった場合、シンクノード周辺のトラフィックに輻輳が生じてしまうという問題があった。そのため、トラフィックに輻輳を生じさせること無くシンクノードからの下り経路を確立できるシステムが要望されている。
【００１１】
また、従来のメニートゥーワン方式におけるルーティングにおいては、ノードの接続状態の変化やリンクの瞬断などの影響により、パケットが宛先ノードへ正しく転送されなかった場合、シンクノードからの下り経路を再確立するために、当該宛先ノードからシンクノードに対してＲＲＥＣコマンドを送信していた。このような処理を行った場合、下り経路が再確立されるまでの間は、上記した図２２(ｃ)の如き下り通信を行うことができないという問題があった。そのため、シンクノードからの下り経路の途中でパケット中継を失敗した場合においても、宛先ノードへパケットを迅速に送信できるシステムが要望されている。
【００１２】
本発明は上記した如き問題点に鑑みてなされたものであって、リンク状況が変動した場合においても適切なリンクコストを算出し、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できるパケット中継システムを提供することを目的とする。
【００１３】
また、トラフィックに輻輳を生じさせること無くシンクノードからの下り経路を確立できるパケット中継システム装置を提供することを目的とする。
【００１４】
また、シンクノードからの下り経路においてパケットが宛先ノードへ正しく転送されなかった場合においても、宛先ノードへパケットを迅速に送信できるパケット中継システムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明によるパケット中継システムは、ツリー状に構成された複数のノードを含むパケット中継システムであって、前記ノードの各々は、前記複数のノードのうちの自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とする。
【００１６】
また、本発明によるパケット中継システムは、データパケットを相互に中継する複数のノードを含むパケット中継システムであって、前記ノードの各々は、前記複数のノードのうちの自身に隣接する隣接ノードの一から当該１の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とする。
【００１７】
また、本発明による無線ノードは、ツリー状に構成された無線通信路を介してデータパケットを中継する無線ノードであって、自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とする。
【００１８】
また、本発明による無線ノードは、無線通信路を介してデータパケットを中継する無線ノードであって、自身に隣接する隣接ノードの一から当該一の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とする。
【発明の効果】
【００１９】
本発明によるパケット中継システムによれば、リンク状況が変動した場合においても適切なリンクコストを算出し、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できる。
【００２０】
また、本発明によるパケット中継システムによれば、トラフィックに輻輳を生じさせること無くシンクノードからの下り経路を確立できる。
【００２１】
また、本発明によるパケット中継システムによれば、シンクノードからの下り経路においてリンク瞬断が生じた場合においても、宛先ノードへパケットを迅速に送信できる。
【図面の簡単な説明】
【００２２】
【図１】第１の実施例によるパケット中継システムを表す模式図である。
【図２】第１の実施例によるノードの構成を表すブロック図である。
【図３】ルーティングテーブルの一例を示す表である。
【図４】（ａ）はセンサデータパケットのフォーマットの一例を表す図である。（ｂ）はハローパケットのフォーマットの一例を表す図である。
【図５】ハローパケット送信処理ルーチンを表すフローチャートである。
【図６】パケット中継処理ルーチンを表すフローチャートである。
【図７】ルーティングテーブル更新処理ルーチンを表すフローチャートである。
【図８】各隣接ノード間のリンクコストを表す図である。
【図９】ノードｂ、ｃ、ｆ、ｅ及びｈにおけるルーティングテーブルの一例を示す表である。
【図１０】リンクコストが変動したときのルーティングテーブルの一例を示す表である。
【図１１】第２の実施例によるノードの構成を表すブロック図である。
【図１２】ツリー状に形成されたパケット中継システムをＲＲＥＣパケットの中継方向と共に示す図である。
【図１３】ＲＲＥＣパケット中継処理ルーチンを表すフローチャートである。
【図１４】各中継段階におけるＲＲＥＣパケットの集約例を表す図である。
【図１５】第３の実施例によるノードの構成を表すブロック図である。
【図１６】（ａ）はノードｃのルーティングテーブルの一例を示す表である。（ｂ）はノードｃの２ホップ隣接ノードテーブルの一例を示す表である。
【図１７】下りデータパケット中継処理ルーチンを表すフローチャートである。
【図１８】パケット中継システムを下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。
【図１９】下りデータパケットのフォーマットの一例を表す図である。
【図２０】パケット中継システムを下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。
【図２１】（ａ）はノードｃのルーティングテーブルの一例を示す表である。（ｂ）はノードｃの２ホップ隣接ノードテーブルの一例を示す表である。
【図２２】従来のメニートゥーワン方式におけるルーティング時のノード間のパケット中継の態様を表す模式図である。
【発明を実施するための最良の形態】
【００２３】
以下、本発明に係る実施例について添付の図面を参照しつつ詳細に説明する。
【００２４】
＜第１の実施例＞
図１は本実施例によるパケット中継システム１を表す模式図である。パケット中継システム１は、例えば無線センサネットワークであり、シンクノードであるノードａと、センサノードであるノードｂ〜ｊを含む。ノードａ〜ｊの各々は、自身に隣接するノードとの間で無線通信によりパケットを交換できる。同図中において点線で結ばれているノード同士が相互にパケットを交換できる。例えばノードａはノードｂ及びｆとそれぞれパケットを交換できる。パケット中継システム１においては、例えばノードｂ〜ｊの各々で生成されたセンサデータをノードａへ集約する。
【００２５】
図２は本実施例によるノードｂの構成を表すブロック図である。ノードａ及びｃ〜ｊの各々のノードもノードｂと同一の構成である。
【００２６】
ノードｂは、アンテナ１０１と、増幅器１０２と、無線信号送受信部１０３と、パケット受信部１０４と、中継処理部１０５と、ルーティングテーブル１０６と、データパケット生成部１０７と、制御パケット生成部１０８と、パケット送信部１０９と、を含む。
【００２７】
アンテナ１０１は、ノードｂに隣接するノードとの間で無線信号を送受信する。
【００２８】
増幅器１０２は、アンテナ１０１によって送受信される無線信号又は無線信号送受信部１０３からの電気信号の信号強度を増幅するアンプである。
【００２９】
無線信号送受信部１０３は、増幅器１０２からの無線信号と、パケット受信部１０４又はパケット送信部１０９からの電気信号との間の相互変換及びこれらの信号に対して変調、復調及び周波数変換処理を施し、増幅器１０２及びアンテナ１０１を介して無線信号を送受信する。
【００３０】
パケット受信部１０４は、無線信号送受信部１０３からの無線信号に含まれるパケットを受信する。
【００３１】
中継処理部１０５は、パケット受信部１０４により受信されたパケットに含まれる情報に基づいて、パケットの種別を判別する中継処理部１０５は、パケットが制御パケットであると判別した場合には、そのパケットに含まれる情報に基づいてルーティングテーブル１０６を更新する。中継処理部１０５は、パケットがデータパケットであると判別した場合には、ルーティングテーブルの情報に基づいて中継先ノードの決定を行う。中継処理部１０５は、例えばマイクロプロセッサなどの演算回路である。
【００３２】
ルーティングテーブル１０６は、ノードｂに隣接しているノードについてのリンクコスト、パスコスト及びパケット到達率を記憶する。ルーティングテーブル１０６は、例えばＲＡＭなどのメモリである。
【００３３】
図３は、ノードｂのルーティングテーブル１０６の一例を示す表である。ノードｂに隣接しているノードａ、ｆ、ｃ及びｅの各々についてのリンクコスト、パスコスト及びパケット到達率が記憶されている。例えば、隣接ノードａについてのリンクコストは２、パスコストは２、パケット到着率は０．８である。これらの情報は中継処理部１０５によって更新される。
【００３４】
データパケット生成部１０７は、図示せぬセンサからのセンサ信号に応じたセンサデータを生成しこれを含むセンサデータパケットを生成する。
【００３５】
制御パケット生成部１０８は、ノードｂに隣接しているノードからのパケット到達率やリンクコスト及びパスコストを算出するためのパケット（以下、ハローパケットと称する）や、ノードａからの下り経路の設定のためのＲＲＥＣパケットなどの制御パケットを生成する。制御パケット生成部１０８及びデータパケット生成部１０７は、例えばマイクロプロセッサなどの演算回路である。
【００３６】
図４（ａ）はセンサデータパケットのフォーマットの一例を表す図である。図４（ｂ）はハローパケットのフォーマットの一例を表す図である。
【００３７】
センサデータパケット及びハローパケットのヘッダ部には、パケットの種別を表す識別子であるパケットタイプ、パケット送信元のノードのアドレスである送信元アドレス、パケットの中継回数の制限を表す中継可能回数、パケット毎に付される連続番号であるシーケンス番号が含まれている。
【００３８】
センサデータパケットのペイロード部には、パケット長、再送回数、例えばセンサデータなどのデータが含まれている。ハローパケットのペイロード部には、パケット長及びパスコストが含まれており、更に隣接アドレス毎のリンクコストを含んでも良い。ここでのパスコストは、シンクノードであるノードａから自身のノードまでの各ノードによって算出されたリンクコストの累積値（リンクコスト累積値）である。
【００３９】
パケット送信部１０９は、データパケット生成部１０７又は制御パケット生成部１０８により生成されたパケットを、無線信号送受信部１０３をしてノードｂに隣接しているノードへ送信せしめる。
【００４０】
ノードａ〜ｊの各々は、大別してハローパケット送信処理とパケット中継処理の２つの処理を並行して実行する。
【００４１】
図５は、ハローパケット送信処理ルーチンを表すフローチャートである。制御パケット生成部１０８は、予め設定された例えば数秒〜数十秒間隔などの周期的なハローパケット送信タイミングが到来したか否かを判別し（ステップＳ１０１）、当該タイミングが到来したときにハローパケットを生成する（ステップＳ１０２）。このとき、制御パケット生成部１０８は、ルーティングテーブル１０６に記憶されている、隣接ノード毎のパスコストのうち最小のパスコストをペイロード部に含めたハローパケットを生成する。例えばノードｂにおけるハローパケット生成時のルーティングテーブル１０６が図３に示される如きものである場合、最小のパスコスト「２」をペイロード部に含める。パケット送信部１０９は、制御パケット生成部１０８により生成されたハローパケットを、無線信号送受信部１０３をしてノードｂに隣接しているノードへ送信せしめる（ステップＳ１０３）。
【００４２】
図６は、ノードａ〜ｊの各々におけるパケット中継処理ルーチンを表すフローチャートである。図７は、パケット中継処理ルーチンに含まれるルーティングテーブル更新処理ルーチンを表すフローチャートである。図８は、ノードａ〜ｊにおける各隣接ノード間のリンクコストを各隣接ノード間に数値で示す図である。図９は、ノードｂ、ｆ、ｃ、ｅ及びｈにおけるルーティングテーブル１０６の一例を示す表である。以下、図６〜１０を参照しつつ、パケット中継処理について説明する。
【００４３】
先ず、シンクノードであるノードａに隣接するノードｂおけるパケット中継処理から順に説明する。
【００４４】
ノードｂの中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットがハローパケットか否かを判別する（ステップＳ２０１）。
【００４５】
中継処理部１０５は、当該パケットがハローパケットであると判別した場合、ルーティングテーブル１０６の更新を行う（ステップＳ２０２）。なお、ハローパケットのフォーマットは前述したように図４（ｂ）に示される如き形式である。
【００４６】
中継処理部１０５は、先ず、当該パケットのヘッダ部に含まれる送信元アドレスから当該パケットを送信したノードを判別し、当該ノードについてのパケット到達率を算出する（ステップＳ３０１）。中継処理部１０５は、当該パケットが例えばノードａからのものであると判別した場合、ノードａからのハローパケットの受信履歴及び当該パケットのヘッダ部に含まれるシーケンス番号からパケット到達率を算出する。例えばパケット到達率算出時点までに受信したノードａからのハローパケットの個数が８０個であり、当該パケットのシーケンス番号が１００である場合、パケット到達率は０．８（＝８０／１００）である。中継処理部１０５は、当該算出によって得られたノードａについてのパケット到達率を更新する（図９（ｂ））。なお、当該パケットの送信元アドレスがルーティングテーブル１０６に記録されていない場合には新規にその送信元アドレスを追加する。
【００４７】
次に中継処理部１０５は、隣接ノード毎のリンクコストを算出する（ステップＳ３０２）。中継処理部１０５は、例えばリンクコスト＝１０−パケット到達率×１０として算出する。例えばノードａについてのパケット到達率が０．８である場合、リンクコスト＝１０−０．８×１０＝２となる。中継処理部１０５は、当該算出によって得られたノードａについてのリンクコストを更新する（図９（ｂ））。
【００４８】
次に中継処理部１０５は、当該パケットに含まれるパスコスト（リンクコスト累積値）を取得する（ステップＳ３０３）。例えば当該パケットがノードａからのものである場合、ノードａはシンクノードなので当該パスコストは０である。
【００４９】
次に中継処理部１０５は、ノードａへパケットを中継したときの、ノードｂからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、中継処理部１０５は、ルーティングテーブル１０６に記憶されているノードａについてのリンクコスト「２」と、ノードａからのパケットから取得したパスコスト「０」とを加算してパスコスト「２」＝（２＋０）を算出する。中継処理部１０５は、当該算出によって得られたノードａについてのパスコストを更新する（図９（ｂ））。
【００５０】
ノードｂと同様にノードａに隣接するノードｆの場合も同様にしてノードａについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｆ））。
【００５１】
ノードｂとノードｆも互いに隣接しているので相互にハローパケットを交換する。
【００５２】
先ず、ノードｂは、ノードｆからのハローパケットのパケット到達率「０．５」を算出し（ステップＳ３０１）、ノードｆについてのリンクコスト「５」を算出する（ステップＳ３０２）。ノードｆは、自身のルーティングテーブル１０６中の最小のパスコストである「３」をペイロード部に含めてハローパケットを送信するので、ノードｂは、ノードｆからのハローパケットのパスコスト「３」を取得し（ステップＳ３０３）、ノードｆへパケットを中継したときの、ノードｂからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、ノードｂは、ルーティングテーブル１０６に記憶されているノードｆについてのリンクコスト「５」と、ノードｆからのパケットから取得したパスコスト「３」とを加算してパスコスト「８」＝（５＋３）を算出する。ノードｂの中継処理部１０５は、当該算出によって得られたノードｆについてのパケット到達率、リンクコスト及びパスコストを更新する（図９（ｂ））。
【００５３】
ノードｆの場合も同様にしてノードｂについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｆ））。
【００５４】
次に、ノードｂに隣接するノードｃの場合について説明する。先ず、ノードｃは、ノードｂからのハローパケットのパケット到達率「０．９」を算出し（ステップＳ３０１）、ノードｂについてのリンクコスト「１」を算出する（ステップＳ３０２）。ノードｂは、自身のルーティングテーブル１０６中の最小のパスコストである「２」をペイロード部に含めてハローパケットを送信するので、ノードｃは、ノードｂからのハローパケットのパスコスト「２」を取得し（ステップＳ３０３）、ノードｂへパケットを中継したときの、ノードｃからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、ノードｃは、ルーティングテーブル１０６に記憶されているノードｂについてのリンクコスト「１」と、ノードｂからのパケットから取得したパスコスト「２」とを加算してパスコスト「３」＝（１＋２）を算出する。ノードｃの中継処理部１０５は、当該算出によって得られたノードｂについてのパケット到達率、リンクコスト及びパスコストを更新する（図９（ｃ））。
【００５５】
ノードｂ及びｆに隣接するノードｅの場合も同様にしてノードｂ及びｆについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｅ））。
【００５６】
ノードｃとノードｅも互いに隣接しているので相互にハローパケットを交換する。
【００５７】
先ず、ノードｃは、ノードｅからのハローパケットのパケット到達率「０．６」を算出し（ステップＳ３０１）、ノードｅについてのリンクコスト「４」を算出する（ステップＳ３０２）。ノードｅは、自身のルーティングテーブル１０６中の最小のパスコストである「４」をペイロード部に含めてハローパケットを送信するので、ノードｃは、ノードｅからのハローパケットのパスコスト「４」を取得し（ステップＳ３０３）、ノードｅへパケットを中継したときの、ノードｃからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、ノードｃは、ルーティングテーブル１０６に記憶されているノードｅについてのリンクコスト「４」と、ノードｆからのパケットから取得したパスコスト「４」とを加算してパスコスト「８」＝（４＋４）を算出する。ノードｃの中継処理部１０５は、当該算出によって得られたノードｅについてのパケット到達率、リンクコスト及びパスコストを更新する（図９（ｃ））。
【００５８】
ノードｅの場合も同様にしてノードｃについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｅ））。
【００５９】
次に、シンクノードａから最も遠い位置にあるノードｈの場合について説明する。ノードｈは、隣接するノードｄ、ｇ及びｊの各々からのハローパケットに応じて上記したのと同様の処理により、ノードｄ、ｇ及びｊの各々についてのパケット到達率及びリンクコストを算出する（ステップＳ３０１及びＳ３０２）。
【００６０】
ノードｄ、ｇ及びｊの各々も上記したのと同様に各隣接ノードについてのリンクコスト及びパスコストを算出してルーティングテーブル１０６に記憶している。ノードｄは、ノードｄからノードａまでの最小のパスコスト［６］（ノードａ、ｂ及びｃ経由のパス）、ノードｇは、ノードｇからノードａまでの最小のパスコスト［５］（ノードａ、ｂ及びｃ経由のパス）、ノードｊは、ノードｊからノードａまでの最小のパスコスト［６］（ノードａ、ｆ及びｉ経由のパス）、をそれぞれのハローパケットに含めて送信する。ノードｈは、ノードｄからのハローパケットから取得したパスコスト「６」と、ルーティングテーブル１０６に記憶されているノードｄについてのリンクコスト「２」とを加算してパスコスト「８」＝（６＋２）を算出する。同様にしてノードｈは、ノードｇ及びｊの各々についてのパスコスト「６」及び「７」を算出する。
【００６１】
このように、各隣接ノード間でハローパケットを交換することにより、ノードｂ〜ｊの各々がルーティングテーブル１０６を更新する。
【００６２】
再び図６を参照してノードｈにおけるパケット中継処理について説明する。
【００６３】
ノードｈの中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットが上りデータパケットであると判別した場合（ステップＳ２０３）、当該パケットの中継先ノードを選択する（ステップＳ２０４）。なお、前述したようにデータパケットのフォーマットは図４（ａ）に示される如き形式である。
【００６４】
このとき、中継処理部１０５は、ルーティングテーブル１０６（図９（ｈ））中の最小のパスコスト「６」に対応するノードｇを中継先ノードとして選択し、無線信号送受信部１０３をしてノードｇへ当該データパケットを送信せしめる（ステップＳ２０５）。この場合、データパケットは、ノードｈ、ｇ、ｃ、ｂ、ａの順に転送される。このときのノードｈからノードａまでの最小パスコスト「６」でデータパケットを中継することができる。
【００６５】
中継処理部１０５は、ノードｇからの受信確認パケットがパケット受信部１０４により受信された場合には、パケットの中継が成功したと判別して（ステップＳ２０６）、パケット中継処理を終了する。
【００６６】
一方、中継処理部１０５は、ノードｇからの受信確認パケットがパケット受信部１０４により受信されなかった場合には、パケットの中継が失敗したと判別して（ステップＳ２０６）、再度、中継先ノードを選択する（ステップＳ２０４）。この場合、中継処理部１０５は、ノードｇに対応するパスコスト「６」の次に小さいパスコスト「７」に対応するノードｊを中継先ノードとして選択する。中継処理部１０５は、無線信号送受信部１０３をしてノードｊへ当該データパケットを送信せしめる（ステップＳ２０５）。この場合、データパケットは、ノードｈ、ｊ、ｉ、ｆ、ａの順に転送される。
【００６７】
また、中継処理部１０５は、ノードｊに対するパケットの中継も失敗したと判別した場合、ノードｊに対応するパスコスト「７」の次に小さいパスコスト「８」に対応するノードｄを中継先ノードとして選択し、無線信号送受信部１０３がノードｄへ当該データパケットを送信する（ステップＳ２０５）。ノードｄ、ｇ及びｊの何れに対してもパケット中継が失敗したと判別した場合には、再度、ルーティングテーブル１０６中の最小のパスコストに対応するノードｇを中継先ノードとして選択するなどしてパケット中継処理を継続し、パケット中継が成功したと判別したときに終了する。
【００６８】
また、例えばノードｈとノードｇの間を人や自動車などの遮蔽物が通過したことにより、これら両ノード間のリンク状況が悪化した場合、ノードｇからのノードｈへのハローパケットの到達率が悪化する。例えばその到達率が０．７に悪化した場合、ノードｈが算出するノードgについてのリンクコストは３、パスコストは８となる。この場合、ノードｈのルーティングテーブル１０６は図１０に示されるように更新される。つまり、ルーティングテーブル１０６中の最小パスコストは７となるので、中継処理部１０５は、ルーティングテーブル１０６（図１０）中の最小のパスコスト「７」に対応するノードｊを中継先ノードとして選択し、無線信号送受信部１０３をしてノードｊへ当該データパケットを送信せしめる。この場合、データパケットは、ノードｈ、ｊ、ｉ、ｆ、ａの順に転送される。
【００６９】
なお、中継処理部１０５は、データパケットを中継する際に、そのヘッダ部に含まれる中継可能回数の値を減算する。中継処理部１０５は、中継可能回数の値が０であると判別した場合には、データパケットを中継せずにパケット中継処理を終了する。また、中継処理部１０５は、データパケットの中継が失敗したと判別する毎に、そのペイロード部に含まれる再送回数の値を減算する。中継処理部１０５は、再送回数の値が０であると判別した場合には、データパケットを中継せずにパケット中継処理を終了する。
【００７０】
また、中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットが上りデータパケットではないと判別した場合（ステップＳ２０３）、ＲＲＥＣパケット中継処理ルーチンに移行する（ステップＳ２０７）。ＲＲＥＣパケット中継処理については、第２の実施例で説明する。ノードｂ〜ｇ、ｉ及びｊの各々も上記したのと同様にデータパケットの中継処理を行う。
【００７１】
上記したように、本実施例によるパケット中継システムによれば、ノードｂ〜ｊの各々は、自身からノードａへの最適な経路を選択することが可能になる。つまり、自身からノードａまでのパスコストが最小となるように、データパケットの中継先ノードとすべき隣接ノードを選択できる。
【００７２】
各ノードは、自身に隣接するノードとの間でパケットを交換し、その到達率に基づいて、対応する隣接ノードについてのリンクコストを算出する。したがって、隣接ノード間でリンク状況が変動した場合においても適切なリンクコストを算出できる。また、自身からシンクノードまでの各リンクコストの加算によりシンクノードまでのパスコストを算出しているので、パスコストについてもリンク状況の変動に応じた適切な値を算出できる。
【００７３】
また、各ノードは、自身に隣接していないノードすなわちシンクノードから隣接ノードに至るまでの各ノードにより算出されたリンクコストの累積値を隣接ノードから取得し、当該累積値と自身が算出した隣接ノードについてのリンクコストから、シンクノードまでのパスコストを算出する。このような処理によりパスコストを算出するので、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できる。
【００７４】
また、各ノードは、隣接ノード毎のパスコストを算出して記憶しているので、最適な隣接ノードに対するパケット中継が失敗した場合でも、次にパケット中継対象とすべき隣接ノードを適切に選択することができる。
【００７５】
＜第２の実施例＞
図１１は、本実施例によるノードｂの構成を表すブロック図である。なお、ノードａ及びｃ〜ｊの各々も同一の構成である。第１の実施例におけるノードｂの構成にパケット集約部１１０が更に含まれる。
【００７６】
パケット集約部１１０は、中継処理部１０５が隣接ノードの１からのＲＲＥＣパケットを受信したと判別した場合に当該パケットを所定の送信タイミングが到来するまで保持し、送信タイミングが到来するまでに中継処理部１０５が当該１の隣接ノード以外の隣接ノードからのＲＲＥＣパケットを受信したと判別したときに、これら両パケットに含まれているアドレスを集約した新たなＲＲＥＣパケット（以下、集約パケットとも称する）を生成し、送信タイミングの到来に応じてパケット送信部１０９をして中継先の隣接ノードへ中継せしめる。
【００７７】
図１２は、ツリー状に形成されたパケット中継システム２をＲＲＥＣパケットの中継方向と共に示す図である。パケット中継システム２は、最上位のノードであるノードａと、ノードａの下位のノードであり階層構造を形成しながらツリー状に配置されているノードｂ〜ｈからなる。ノードｂ〜ｈの各々は、同図に矢印で示される如く下位の側に位置するノードからのＲＲＥＣパケットを上位の側に位置するノードへ順次中継する。ノードｂ〜ｈの各々は、ＲＲＥＣパケットを中継する際に自身のアドレスをＲＲＥＣパケットに含めて中継する。パケット集約部１１０は、ＲＲＥＣパケットに含まれるこれらのアドレスを集約した新たなＲＲＥＣパケットを生成するのである。
【００７８】
図１３は、ＲＲＥＣパケット中継処理ルーチンを表すフローチャートである。このＲＲＥＣパケット中継処理ルーチンは、図６に示されるパケット中継処理ルーチンにおけるステップＳ２０７のＲＲＥＣパケット中継処理に対応する処理である。図１４は、各中継段階におけるＲＲＥＣパケットの集約例を、図１２に矢印と共に示される数字に対応させて表す図である。以下、図１２〜１５を参照しつつ、ＲＲＥＣパケット中継処理について説明する。
【００７９】
先ず、最下位ノードであるノードｈおけるＲＲＥＣパケット中継処理から順に説明する。
【００８０】
ノードｈの制御パケット生成部１０８は、ノードｈのアドレスを含むＲＲＥＣパケットを生成し、これをノードｈに隣接するノードｄへ送信する（図１２（１））。このとき、制御パケット生成部１０８は、図１４（１）に示される如く、ヘッダＨＤと、ペイロード部のパケットサイズＬＮと、当該パケットに含まれるアドレスの個数ＮＭ「１」と、ノードｈの例えばＩＰアドレスなどのアドレスＡＤ「ｈ」と、を含むＲＲＥＣパケットを生成する。以下、ノードｈのアドレスを単にアドレスｈと称する。他のノードのアドレスについても同様に、アドレスａ、アドレスｂ、・・・、アドレスｇと称する。
【００８１】
ノードｄの中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットがＲＲＥＣパケットか否かを判別する（ステップＳ４０１）。パケット集約部１１０は、中継処理部１０５が当該パケットがＲＲＥＣパケットであると判別した場合に、当該パケットに含まれるパケット情報を、所定の送信タイミングが到来するまで保持する（ステップＳ４０２、Ｓ４０３）。例えば、当該パケットがノードｈからのＲＲＥＣパケットである場合、パケット集約部１１０は、そのＲＲＥＣパケットに含まれるアドレスｈなどの情報を保持する。所定の送信タイミングは、例えば数秒〜数十秒など周期的なタイミングであり、予め設定されたタイミングである。
【００８２】
ノードｄのパケット集約部１１０は、所定の送信タイミングが到来した場合、アドレスｄ及びｈを含めたＲＲＥＣパケットを上位のノードであるノードｂへ送信する（ステップＳ４０５）。このとき、パケット集約部１１０は、図１４（２）に示される如く、ヘッダＨＤ及びパケットサイズＬＮと、アドレスの個数ＮＭ「２」と、アドレスｄ及びｈと、を含むＲＲＥＣパケットを生成する。なお、ノードｄのパケット受信部１０４はノードｈ以外のノードからはＲＲＥＣパケットを受信しないので、パケット集約部１１０はステップＳ４０４におけるＲＲＥＣパケット集約処理については省略する。
【００８３】
ノードｂの下位のノードｅもノードｈと同様の処理により、図１４（３）に示される如きＲＲＥＣパケットを上位のノードであるノードｂへ送信する。
【００８４】
ノードｂのパケット集約部１１０は、中継処理部１０５がパケット受信部１０４により受信されたパケットがＲＲＥＣパケットであると判別した場合に（ステップＳ４０１）、当該ＲＲＥＣパケットに含まれるパケット情報を、所定の送信タイミングが到来するまで保持する（ステップＳ４０２、Ｓ４０３）。例えば、当該パケットがノードｄからのＲＲＥＣパケットである場合、パケット集約部１１０は、そのＲＲＥＣパケットに含まれるアドレスｄ及びｈを保持する。
【００８５】
ノードｂのパケット集約部１１０は、中継処理部１０５が所定の送信タイミングが到来するまでに更にパケット受信部１０４によりＲＲＥＣパケットが受信されたと判別した場合（ステップＳ４０１）、同様にして当該ＲＲＥＣパケットに含まれるパケット情報を、所定の送信タイミングが到来するまで保持する（ステップＳ４０２、Ｓ４０３）。例えば、当該パケットがノードｅからのＲＲＥＣパケットである場合、パケット集約部１１０は、そのＲＲＥＣパケットに含まれるアドレスｅを保持する。
【００８６】
ノードｂのパケット集約部１１０は、所定の送信タイミングが到来した場合（ステップＳ４０３）、保持しているアドレス情報を集約して新たなＲＲＥＣパケットを生成する（ステップＳ４０４）。パケット集約部１１０は、図１４（４）に示される如く、ヘッダＨＤ及びパケットサイズＬＮと、親子関係にある複数のノードの各アドレスからなるアドレス群と、アドレス群毎のアドレス個数と、を含むＲＲＥＣパケットを生成する。
【００８７】
このとき、ノードｂのパケット集約部１１０は、自身のノードであるノードｂのアドレスｂを先頭のアドレス、ノードｂの子ノードであるノードｄのアドレスｄを２番目のアドレス、同じくノードｂの子ノードであるノードｅのアドレスｅを３番目のアドレスとするアドレス群（アドレスｂ、ｄ、ｅ）を生成し、その個数ＮＭを「３」とする。また、パケット集約部１１０は、ノードｄのアドレスｄを先頭のアドレス、ノードｄの子ノードであるノードｈのアドレスｈを２番目のアドレスとするアドレス群（アドレスｄ、ｈ）を生成し、その個数ＮＭを「２」とする。このようにして、パケット集約部１１０は、図１４（４）に示される如き新たなＲＲＥＣパケット（集約パケット）を生成する。
【００８８】
パケット集約部１１０は、新たなＲＲＥＣパケット（図１４（４））を上位ノードであるノードａへ送信する（ステップＳ４０５）。
【００８９】
ノードｃも、ノードｂと同様のＲＲＥＣパケット中継処理を行う。ノードｃのパケット集約部１１０は、ノードｆからのＲＲＥＣパケット（図１４（５））に含まれるアドレスｆと、ノードｇからのＲＲＥＣパケット（図１４（６））に含まれるアドレスｇと、を所定の送信タイミングが到来するまで保持し（ステップＳ４０２）、送信タイミングが到来したときに（ステップＳ４０３）、新たなＲＲＥＣパケットを生成する。
【００９０】
このとき、ノードｃのパケット集約部１１０は、自身のノードであるノードｃのアドレスｃを先頭のアドレス、ノードｃの子ノードであるノードｆのアドレスｆを２番目のアドレス、同じくノードｃの子ノードであるノードｇのアドレスｇを３番目のアドレスとするアドレス群（アドレスｃ、ｆ、ｇ）を生成し、その個数ＮＭを「３」として、図１４（７）に示される如き新たなＲＲＥＣパケット（集約パケット）を生成する。パケット集約部１１０は、新たなＲＲＥＣパケット（図１４（７））を上位ノードであるノードａへ送信する（ステップＳ４０５）。
【００９１】
ノードａは、下位ノードであるノードｂ及びｃの各々からＲＲＥＣパケット（図１４（４）及び（７））を受信する。ノードａがシンクノードである場合にはＲＲＥＣパケットの中継は行わないが、ノードａが更に上位のノードにＲＲＥＣパケットを中継する場合には、パケット集約部１１０は、ノードｂ及びｃの各々からＲＲＥＣパケットに含まれるアドレスを集約して図１４（８）に示される如きＲＲＥＣパケットを生成する。
【００９２】
このとき、ノードａのパケット集約部１１０は、自身のノードであるノードａのアドレスａを先頭のアドレス、ノードａの子ノードであるノードｂのアドレスｂを２番目のアドレス、同じくノードａの子ノードであるノードｃのアドレスｃを３番目のアドレスとするアドレス群（アドレスａ、ｂ、ｃ）を生成し、その個数ＮＭを「３」とする。また、パケット集約部１１０は、ノードｂのアドレスｂを先頭のアドレス、ノードｂの子ノードであるノードｄのアドレスｄを２番目のアドレス、同じくノードｂの子ノードであるノードｅのアドレスｅを３番目のアドレスとするアドレス群（アドレスｂ、ｄ、ｅ）を生成し、その個数ＮＭを「３」とする。
【００９３】
同様にして、パケット集約部１１０は、アドレス個数ＮＭ「２」のアドレス群（アドレスｄ、ｈ）と、アドレス個数ＮＭ「３」のアドレス群（アドレスｃ、ｆ、ｇ）とを生成し、これら全てのアドレス群を含む新たなＲＲＥＣパケット（図１４（８））を生成する。パケット集約部１１０は、図１４（８）に示される如きＲＲＥＣパケットを更に上位のノード（図示せず）へ送信する。
【００９４】
上記したように、本実施例によるパケット中継システムによれば、ツリー状に形成されたノードのうちの下位のノードから上位のノードへＲＲＥＣパケットを順次中継する際に、各下位ノードからのＲＲＥＣパケットに含まるアドレスを親子関係毎にまとめたアドレス群に集約して生成した新たなＲＲＥＣパケット（集約パケット）を上位ノードへ送信する。
【００９５】
従来のパケット中継システムでは、中継ノードが下位の各ノードからユニキャスト送信により送信されたＲＲＥＣパケットを集約することなくそのまま中継していたので、各ノードにおける送信タイミングが重なった場合、シンクノード周辺のトラフィックに輻輳が生じてしまうという問題があったが、本実施例によるパケット中継システムによれば、下位の各ノードからのＲＲＥＣパケットに含まれるアドレスを集約して１のＲＲＥＣパケットを上位のノードへ中継するので、トラフィックに輻輳が生じさせることはない。また、ＲＲＥＣパケットに含まれる各アドレス群は、親子関係毎にまとめられたものなので、最上位のシンクノードは、下位の各ノードの接続関係を把握することが可能であり、シンクノードからの下り経路を確立できる。
【００９６】
＜第３の実施例＞
図１５は、本実施例によるノードｃの構成を表すブロック図である。なお、ノードａ、ｂ及びｄ〜ｊの各々も同一の構成である。第１の実施例におけるノードｂの構成に２ホップ隣接テーブル１１１が更に含まれる。
【００９７】
図１６（ａ）は、ノードｃのルーティングテーブル１０６の一例を表す図である。図１６（ｂ）は、ノードｃの２ホップ隣接ノードテーブル１１１の一例を表す図である。ノードｃは、第１の実施例と同様のルーティングテーブル１０６の他に、２ホップ隣接テーブル１１１を有している。２ホップ隣接テーブル１１１には、１ホップのノードのアドレスと、２ホップのノードのアドレスが記憶されている。ここで、１ホップのノードとはノードｃに隣接するノードのことをいい、２ホップのノードとは１ホップのノードに隣接するノードであってノードｃとは隣接していないノードのことをいう。例えば、ノードｃについての１ホップのノードはノードｂ、ｅ、ｄ及びｇであり、２ホップのノードはノードａ、ｆ、ｅ、ｊ及びｈである。
【００９８】
ノードｃの中継処理部１０５は、パケット受信部１０４が例えば数秒〜数十秒などの周期的に受信する図４（ｂ）に示される如きハローパケットのペイロード部に含まれている、隣接アドレスに基づいて１ホップ及び２ホップのノードのアドレスを２ホップ隣接テーブル１１１に記憶する。例えばノードｂはノードｃの他、ノードａ、ｆ及びｅに隣接しているので、ペイロード部の隣接アドレスをアドレスａ、ｆ及びｅとしたハローパケットをノードｃへ送信する。
【００９９】
ノードｃの中継処理部１０５は、この隣接アドレスのうちノードｃに隣接していないアドレスすなわちアドレスａ、ｆを２ホップのノードのアドレスとして２ホップ隣接テーブル１１１に記憶すると共に、アドレスａ及びｆの各々にアドレスｂを対応付けて記憶する。中継処理部１０５は、他の隣接ノードからのハローパケットを受信した場合にも、同様の処理を施して図１６（ｂ）に示される如き２ホップ隣接テーブル１１１を生成する。
【０１００】
図１７は、下りデータパケット中継処理ルーチンを表すフローチャートである。この下りデータパケット中継処理ルーチンは、図１３に示されるＲＲＥＣパケット中継処理ルーチンにおけるステップＳ４０６の下りデータパケット中継処理に対応するものである。図１８は、パケット中継システム１を下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。以下、図１７及び図１８を参照しつつ、シンクノードであるノードａからノードｈへの下りデータパケット中継処理について説明する。
【０１０１】
先ず、シンクノードであるノードａにおける処理から説明する。図１９は、下りデータパケットのフォーマットの一例を表す図である。データパケットのヘッダ部には、パケットの種別を表す識別子であるパケットタイプ、パケット送信元のノードのアドレスである送信元アドレス、パケットの中継回数の制限を表す中継可能回数、パケット毎に付される連続番号であるシーケンス番号が含まれている。
【０１０２】
下りデータパケットのペイロード部には、パケット長、アドレス個数、当該アドレス個数分だけのアドレス、宛先へ送信すべきデータが含まれている。以下、ペイロード部に含まれるアドレスの一群をアドレスリストと称する。ノードａのパケット送信部１０９が送信する下りデータパケットのアドレスリストには、アドレスｂ、ｃ、ｇ、ｈの順にアドレスが記載されている。なお、この順番は第２に実施例で説明した如くノードａが受信した、下位のノードからのＲＲＥＣパケットに含まれているアドレス群から把握したノード接続状態に基づいて中継処理部１０５が設定した順番である。
【０１０３】
ノードａのパケット送信部１０９は、下りデータパケットを、アドレスリストの先頭に記載されているアドレスｂを宛先としてつまりノードｂへ送信する。
【０１０４】
ノードｂの中継処理部１０５は、ノードａからの下りデータパケットに含まれるアドレスリストの先頭に記載されているアドレスｂ（つまり自身のノードのアドレス）を削除してアドレスリストを変更する（ステップＳ５０１）。中継処理部１０５は、当該変更したアドレスリストを含む下りデータパケットをアドレスリストの先頭に記載されているアドレスｃを宛先としてつまりノードｃへ送信する（ステップＳ５０２）。
【０１０５】
ノードｂの中継処理部１０５は、パケット受信部１０４がノードｃからのパケット受信通知を受け取ったと判別した場合には、パケット中継が成功したと判別し（ステップＳ５０３）、中継処理を終了する。ノードｂの中継処理部１０５は、パケット受信部１０４がノードｃからのパケット受信通知を受け取れなかったと判別した場合には、パケット中継が失敗したと判別し（ステップＳ５０３）、２ホップ隣接テーブル１１１を参照する（ステップＳ５０４）。ここでは、パケット中継が成功したものとし、中継処理部１０５は、パケット中継処理を終了する。
【０１０６】
ノードｃの中継処理部１０５は、ノードｂからの下りデータパケットに含まれるアドレスリストの先頭に記載されているアドレスｃ（つまり自身のノードのアドレス）を削除してアドレスリストを変更する（ステップＳ５０１）。中継処理部１０５は、当該変更したアドレスリストを含む下りデータパケットをアドレスリストの先頭に記載されているアドレスｇを宛先としてつまりノードｇへ中継する（ステップＳ５０２）。ここで、ノードｃとノードｇと間を例えば人や自動車などの遮蔽物が通過するなどしてリンクの瞬断が生じた影響により、ノードｇへ下りデータパケットが到達できなかったものとする。
【０１０７】
ノードｃの中継処理部１０５は、パケット受信部１０４がノードｇからのパケット受信通知を受け取れなかったつまりパケット中継が失敗したと判別した場合（ステップＳ５０３）、図１６（ｂ）に示される如き２ホップ隣接テーブル１１１を参照する（ステップＳ５０４）。先ず、中継処理部１０５は、アドレスリスト内においてアドレスｇの次に記載されているアドレスｈが２ホップ隣接テーブル１１１における２ホップのノードのアドレスとして記憶されているか検索する（ステップＳ５０５）。
【０１０８】
アドレスｈが２ホップのノードのアドレスとして記憶されていた場合、中継処理部１０５は、アドレスｈに対応する１ホップのノードのアドレスｄ及びｇのうちの未中継のノードのアドレスつまりアドレスｄを下りデータパケットの宛先として決定する。中継処理部１０５は、アドレスリストのアドレスをアドレスｄ、ｈに変更し（ステップＳ５０１）、ノードｄへ中継する（ステップＳ５０２）。
【０１０９】
ノードｃの中継処理部１０５は、パケット受信部１０４がノードｄからのパケット受信通知を受け取ったと判別し（ステップＳ５０３）、パケット中継処理を終了する。ノードｄも上記したのと同様の処理により、アドレスリストのアドレスをアドレスｈに変更した下りデータパケットをノードｈへ中継する。
【０１１０】
上記したように本実施例によるパケット中継システムによれば、各ノードが、隣接ノードとの間で交換するパケットに含まれる２ホップ先のノードのアドレスを隣接ノードのアドレスと対応付けて記憶する。ノードが隣接ノードのうちの１へのパケット中継が失敗したと判別した場合に、２ホップ先の中継先ノードのアドレスに対応付けられているアドレスの１を選択し、当該１のアドレスの隣接ノードへパケットを中継する。
【０１１１】
従来のパケット中継システムにおいては、パケットが宛先ノードへ正しく転送されなかった場合にシンクノードからの下り経路を再確立するため、当該宛先ノードからシンクノードに対してＲＲＥＣコマンドを送信していたので、下り経路が再確立されるまでの間は、下り通信を行うことができないという問題があった。それに対して本実施例による中継システムによれば、パケットの中継先ノードを変更してパケットを中継するので、シンクノードからの下り経路の途中でパケット中継を失敗した場合においても、宛先ノードへパケットを迅速に中継することができる。
【０１１２】
上記した例は、ノードｃがパケット中継に失敗した場合の代替ノードの候補がノードｄのみの場合の例であるが、代替ノード候補が複数ある場合には、以下のような処理がなされる。
【０１１３】
図２０は、パケット中継システム１を下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。上記した例におけるパケット中継システム１に更にノードｋが追加されている。ノードｋは、同図に示されるとおり、ノードｃ及びｈと隣接するノードである。図２１（ａ）は、この場合のノードｃのルーティングテーブルの一例を表す図である。ノードｋについての隣接アドレス、リンクコスト、パスコスト、到着率が追加されている。図２１（ｂ）は、この場合のノードｃの２ホップ隣接ノードテーブルの一例を表す図である。２ホップのノードｈのアドレスｈにアドレスｄ、ｇ及びｋが対応付けられている。
【０１１４】
ノードｃの中継処理部１０５は、ノードｇへの下りデータパケットの中継が失敗したと判別した場合（ステップＳ５０３）、図２１（ｂ）に示される如き２ホップ隣接テーブル１１１を参照する（ステップＳ５０４）。
【０１１５】
中継処理部１０５は、アドレスリスト内においてアドレスｇの次に記載されているアドレスｈが２ホップ隣接テーブル１１１における２ホップのノードのアドレスとして記憶されているか検索する（ステップＳ５０５）。
【０１１６】
アドレスｈが２ホップのノードのアドレスとして記憶されていた場合、中継処理部１０５は、アドレスｈに対応する１ホップのノードのアドレスｄ及びｇのうちの未中継のノードのアドレスつまりアドレスｄ又はｋのいずれか１を下りデータパケットの宛先として決定する。
【０１１７】
このとき、中継処理部１０５は、図２１（ａ）に示される如きルーティングテーブルを参照し、アドレスｄに対応するリンクコスト「３」と、アドレスｋに対応するリンクコスト「１」とを比較し、リンクコストが小さい方のアドレスｋを下りデータパケットの中継先として決定する。中継処理部１０５は、アドレスリストのアドレスをアドレスｋ、ｈに変更し（ステップＳ５０１）、ノードｋへ中継する（ステップＳ５０２）。このような処理により、より適切な中継先ノード選択が可能となる。
【０１１８】
また、上記した例は、中継先ノードからの受信確認応答が１回でも得られなかった場合、直ぐに他の中継先ノードを選択する場合の例であるが、受信確認応答が得られなかった場合でも同一の中継先ノードに複数回のパケット送信を行い、それらの複数回送信が全て失敗したと判別した場合に他の中継先ノードを選択するようにしても良い。
【符号の説明】
【０１１９】
１ パケット中継システム
１０１ アンテナ
１０２ 増幅器
１０３ 無線信号送受信部
１０４ パケット受信部
１０５ 中継処理部
１０６ ルーティングテーブル
１０７ データパケット生成部
１０８ 制御パケット生成部
１０９ パケット送信部
１１０ パケット集約部
１１１ ２ホップ隣接テーブル
【技術分野】
【０００１】
本発明は、データパケットを相互に中継する複数のノードを含むパケット中継システムに関する。
【背景技術】
【０００２】
パケット中継機能を有する複数の無線ノードによってネットワークを構成し、互いに隣接している無線ノード間で相互にパケットを中継するマルチホップ無線ネットワークが知られている。無線ノード間でパケットを順次中継することにより、電波が直接届かない無線ノードへパケットを転送することができる。
【０００３】
パケットを所望の無線ノードに中継するためには、宛先アドレスから次に転送すべき無線ノードを決定するためのルーティングプロトコルが必要とされる。例えばジグビー（ＺｉｇＢｅｅ（登録商標））アライアンスでは、アドレスの割り当て方法を工夫することによりルーティングテーブルが不要となるクラスタツリールーティング方式、メッシュトポロジーの構成できるＡＯＤＶ（Ad Hoc On-Demand Distance Vector）方式、複数のノードからデータを効率的に収集できるメニートゥーワン（Many to One）方式などによるルーティングプロトコルが標準化されている。特にメニートゥーワン方式は、シンクノードと複数のノードとの間の１対ｎの通信について考慮された方式であるので、環境情報のセンシングやメータの自動検針などのアプリケーションへの適用が期待されている。
【０００４】
図２２は、メニートゥーワン方式におけるルーティング時のノード間のパケット中継の態様を表す模式図である。図２２（ａ）は、ノードｂ〜ｊの各々が、シンクノードであるノードａへパケットを中継するための上り経路を設定するときのＲＲＥＱ（Route Request）パケット中継の態様を表す模式図である。ノードａは、送信先アドレスをブロードキャストアドレスとして、ＲＲＥＱパケットを送信する。ＲＲＥＱパケットを受信したノードは、他のノードへＲＲＥＱパケットを中継する。ＲＲＥＱパケットには、ネットワーク上における任意の２つのノード間の論理的な距離を表すパスコストが含まれている。ＲＲＥＱパケットの中継時には、自身に隣接しているノードについてのリンクコストをパスコストに加算して送信する。リンクコストは、ネットワーク上におけるノード間の論理的な距離を表すものであり、パスコスト算出の基礎となるコストである。リンクコストは、ノード間の受信強度やパケットエラー率などから算出される。このようにＲＲＥＱパケットの中継を繰り返すことにより、ノードｂ〜ｊの各々は、シンクノードａへパケットを転送するための上り経路を設定することができる。つまり、ノードｂ〜ｊの各々は、例えば最も小さいパスコストに対応するノードをパケット中継先のノードとして選択することにより、最適な条件にてパケットをシンクノードへ中継することができる。
【０００５】
図２２（ｂ）は、シンクノードであるノードａからノードｈへの下り経路を設定するときのＲＲＥＣ（Route Record）パケット中継の態様を表す模式図である。ノードｈは、宛先をノードａとし、自身のアドレスを含めたＲＲＥＣパケットを送信する。ＲＲＥＣパケットを受信したノードは自身のアドレス及び中継回数を含めたＲＲＥＣパケットを転送先のノードへ転送する。つまり、ノードｈからｄ、ｃ、ｂ、ａの順にアドレスが追加されたパケットがノードａに転送される。ノードａから他のノードへの下り経路を設定するときも同様の処理がなされる。
【０００６】
図２２（ｃ）は、下り経路設定後にノードａからノードｈへのパケット中継の態様を表す模式図である。ノードａは、下り経路設定時におけるアドレス追加順と逆順にしたアドレスをパケットヘッダに記載してデータパケットを送信する。データパケットを受信したノードは、パケットヘッダ内に記載されている自身のアドレスを削除して転送先のノードへ転送する。このようにして、ノードａからｂ、ｃ、ｄ、ｈの順にデータパケットを中継できる。これらのルーティングは、送信元ノード（ソースノード）が、パケットを中継するノードを一意に決定する経路制御であるので、ソースルーティングと呼ばれている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】ZigBeeSpecification Revision17 (ZigBee Document 053474r17)
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来のメニートゥーワン方式におけるルーティングにおいては、リンクコストの算出方法が明確でなかった。非特許文献１では、ＬＱＩ（Link Qulity Indicator）などの要素からリンクコストを算出するとしているが、ＲＲＥＱコマンドを受信した際のＬＱＩにはばらつきがあるので、正確なリンクコストを算出するのが困難であるという問題があった。特に屋外など広範囲に亘る場所にノードを設置した場合、ノード間を人や自動車などの遮蔽物が通過したとき、ノード間のリンクの瞬断が生じ、リンク状況が変動してしまう。そのため、リンク状況が変動した場合においても、適切なリンクコストを算出できるシステムが要望されている。
【０００９】
また、従来のメニートゥーワン方式におけるルーティングにおいては、シンクノードへの上り経路を確立するために、上記した図２２(ａ)の如くRＲＥＱパケットを定期的にブロードキャスト送信する必要があった。ＲＲＥＱパケットは、各ノードで一度は再送され、ネットワーク全体に配送されるので、ネットワークの規模が大きくなるほどネットワーク内の通信情報量が増加し、無線帯域の利用効率が悪化するという問題があった。そのため、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できるシステムが要望されている。
【００１０】
また、従来のメニートゥーワン方式におけるルーティングにおいては、シンクノードからの下り経路を確立するために、上記した図２２(ｂ)の如く各ノードはユニキャスト送信によりシンクノードへＲＲＥＣコマンドを送信するので、各ノードにおける送信タイミングが重なった場合、シンクノード周辺のトラフィックに輻輳が生じてしまうという問題があった。そのため、トラフィックに輻輳を生じさせること無くシンクノードからの下り経路を確立できるシステムが要望されている。
【００１１】
また、従来のメニートゥーワン方式におけるルーティングにおいては、ノードの接続状態の変化やリンクの瞬断などの影響により、パケットが宛先ノードへ正しく転送されなかった場合、シンクノードからの下り経路を再確立するために、当該宛先ノードからシンクノードに対してＲＲＥＣコマンドを送信していた。このような処理を行った場合、下り経路が再確立されるまでの間は、上記した図２２(ｃ)の如き下り通信を行うことができないという問題があった。そのため、シンクノードからの下り経路の途中でパケット中継を失敗した場合においても、宛先ノードへパケットを迅速に送信できるシステムが要望されている。
【００１２】
本発明は上記した如き問題点に鑑みてなされたものであって、リンク状況が変動した場合においても適切なリンクコストを算出し、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できるパケット中継システムを提供することを目的とする。
【００１３】
また、トラフィックに輻輳を生じさせること無くシンクノードからの下り経路を確立できるパケット中継システム装置を提供することを目的とする。
【００１４】
また、シンクノードからの下り経路においてパケットが宛先ノードへ正しく転送されなかった場合においても、宛先ノードへパケットを迅速に送信できるパケット中継システムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明によるパケット中継システムは、ツリー状に構成された複数のノードを含むパケット中継システムであって、前記ノードの各々は、前記複数のノードのうちの自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とする。
【００１６】
また、本発明によるパケット中継システムは、データパケットを相互に中継する複数のノードを含むパケット中継システムであって、前記ノードの各々は、前記複数のノードのうちの自身に隣接する隣接ノードの一から当該１の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とする。
【００１７】
また、本発明による無線ノードは、ツリー状に構成された無線通信路を介してデータパケットを中継する無線ノードであって、自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とする。
【００１８】
また、本発明による無線ノードは、無線通信路を介してデータパケットを中継する無線ノードであって、自身に隣接する隣接ノードの一から当該一の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とする。
【発明の効果】
【００１９】
本発明によるパケット中継システムによれば、リンク状況が変動した場合においても適切なリンクコストを算出し、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できる。
【００２０】
また、本発明によるパケット中継システムによれば、トラフィックに輻輳を生じさせること無くシンクノードからの下り経路を確立できる。
【００２１】
また、本発明によるパケット中継システムによれば、シンクノードからの下り経路においてリンク瞬断が生じた場合においても、宛先ノードへパケットを迅速に送信できる。
【図面の簡単な説明】
【００２２】
【図１】第１の実施例によるパケット中継システムを表す模式図である。
【図２】第１の実施例によるノードの構成を表すブロック図である。
【図３】ルーティングテーブルの一例を示す表である。
【図４】（ａ）はセンサデータパケットのフォーマットの一例を表す図である。（ｂ）はハローパケットのフォーマットの一例を表す図である。
【図５】ハローパケット送信処理ルーチンを表すフローチャートである。
【図６】パケット中継処理ルーチンを表すフローチャートである。
【図７】ルーティングテーブル更新処理ルーチンを表すフローチャートである。
【図８】各隣接ノード間のリンクコストを表す図である。
【図９】ノードｂ、ｃ、ｆ、ｅ及びｈにおけるルーティングテーブルの一例を示す表である。
【図１０】リンクコストが変動したときのルーティングテーブルの一例を示す表である。
【図１１】第２の実施例によるノードの構成を表すブロック図である。
【図１２】ツリー状に形成されたパケット中継システムをＲＲＥＣパケットの中継方向と共に示す図である。
【図１３】ＲＲＥＣパケット中継処理ルーチンを表すフローチャートである。
【図１４】各中継段階におけるＲＲＥＣパケットの集約例を表す図である。
【図１５】第３の実施例によるノードの構成を表すブロック図である。
【図１６】（ａ）はノードｃのルーティングテーブルの一例を示す表である。（ｂ）はノードｃの２ホップ隣接ノードテーブルの一例を示す表である。
【図１７】下りデータパケット中継処理ルーチンを表すフローチャートである。
【図１８】パケット中継システムを下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。
【図１９】下りデータパケットのフォーマットの一例を表す図である。
【図２０】パケット中継システムを下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。
【図２１】（ａ）はノードｃのルーティングテーブルの一例を示す表である。（ｂ）はノードｃの２ホップ隣接ノードテーブルの一例を示す表である。
【図２２】従来のメニートゥーワン方式におけるルーティング時のノード間のパケット中継の態様を表す模式図である。
【発明を実施するための最良の形態】
【００２３】
以下、本発明に係る実施例について添付の図面を参照しつつ詳細に説明する。
【００２４】
＜第１の実施例＞
図１は本実施例によるパケット中継システム１を表す模式図である。パケット中継システム１は、例えば無線センサネットワークであり、シンクノードであるノードａと、センサノードであるノードｂ〜ｊを含む。ノードａ〜ｊの各々は、自身に隣接するノードとの間で無線通信によりパケットを交換できる。同図中において点線で結ばれているノード同士が相互にパケットを交換できる。例えばノードａはノードｂ及びｆとそれぞれパケットを交換できる。パケット中継システム１においては、例えばノードｂ〜ｊの各々で生成されたセンサデータをノードａへ集約する。
【００２５】
図２は本実施例によるノードｂの構成を表すブロック図である。ノードａ及びｃ〜ｊの各々のノードもノードｂと同一の構成である。
【００２６】
ノードｂは、アンテナ１０１と、増幅器１０２と、無線信号送受信部１０３と、パケット受信部１０４と、中継処理部１０５と、ルーティングテーブル１０６と、データパケット生成部１０７と、制御パケット生成部１０８と、パケット送信部１０９と、を含む。
【００２７】
アンテナ１０１は、ノードｂに隣接するノードとの間で無線信号を送受信する。
【００２８】
増幅器１０２は、アンテナ１０１によって送受信される無線信号又は無線信号送受信部１０３からの電気信号の信号強度を増幅するアンプである。
【００２９】
無線信号送受信部１０３は、増幅器１０２からの無線信号と、パケット受信部１０４又はパケット送信部１０９からの電気信号との間の相互変換及びこれらの信号に対して変調、復調及び周波数変換処理を施し、増幅器１０２及びアンテナ１０１を介して無線信号を送受信する。
【００３０】
パケット受信部１０４は、無線信号送受信部１０３からの無線信号に含まれるパケットを受信する。
【００３１】
中継処理部１０５は、パケット受信部１０４により受信されたパケットに含まれる情報に基づいて、パケットの種別を判別する中継処理部１０５は、パケットが制御パケットであると判別した場合には、そのパケットに含まれる情報に基づいてルーティングテーブル１０６を更新する。中継処理部１０５は、パケットがデータパケットであると判別した場合には、ルーティングテーブルの情報に基づいて中継先ノードの決定を行う。中継処理部１０５は、例えばマイクロプロセッサなどの演算回路である。
【００３２】
ルーティングテーブル１０６は、ノードｂに隣接しているノードについてのリンクコスト、パスコスト及びパケット到達率を記憶する。ルーティングテーブル１０６は、例えばＲＡＭなどのメモリである。
【００３３】
図３は、ノードｂのルーティングテーブル１０６の一例を示す表である。ノードｂに隣接しているノードａ、ｆ、ｃ及びｅの各々についてのリンクコスト、パスコスト及びパケット到達率が記憶されている。例えば、隣接ノードａについてのリンクコストは２、パスコストは２、パケット到着率は０．８である。これらの情報は中継処理部１０５によって更新される。
【００３４】
データパケット生成部１０７は、図示せぬセンサからのセンサ信号に応じたセンサデータを生成しこれを含むセンサデータパケットを生成する。
【００３５】
制御パケット生成部１０８は、ノードｂに隣接しているノードからのパケット到達率やリンクコスト及びパスコストを算出するためのパケット（以下、ハローパケットと称する）や、ノードａからの下り経路の設定のためのＲＲＥＣパケットなどの制御パケットを生成する。制御パケット生成部１０８及びデータパケット生成部１０７は、例えばマイクロプロセッサなどの演算回路である。
【００３６】
図４（ａ）はセンサデータパケットのフォーマットの一例を表す図である。図４（ｂ）はハローパケットのフォーマットの一例を表す図である。
【００３７】
センサデータパケット及びハローパケットのヘッダ部には、パケットの種別を表す識別子であるパケットタイプ、パケット送信元のノードのアドレスである送信元アドレス、パケットの中継回数の制限を表す中継可能回数、パケット毎に付される連続番号であるシーケンス番号が含まれている。
【００３８】
センサデータパケットのペイロード部には、パケット長、再送回数、例えばセンサデータなどのデータが含まれている。ハローパケットのペイロード部には、パケット長及びパスコストが含まれており、更に隣接アドレス毎のリンクコストを含んでも良い。ここでのパスコストは、シンクノードであるノードａから自身のノードまでの各ノードによって算出されたリンクコストの累積値（リンクコスト累積値）である。
【００３９】
パケット送信部１０９は、データパケット生成部１０７又は制御パケット生成部１０８により生成されたパケットを、無線信号送受信部１０３をしてノードｂに隣接しているノードへ送信せしめる。
【００４０】
ノードａ〜ｊの各々は、大別してハローパケット送信処理とパケット中継処理の２つの処理を並行して実行する。
【００４１】
図５は、ハローパケット送信処理ルーチンを表すフローチャートである。制御パケット生成部１０８は、予め設定された例えば数秒〜数十秒間隔などの周期的なハローパケット送信タイミングが到来したか否かを判別し（ステップＳ１０１）、当該タイミングが到来したときにハローパケットを生成する（ステップＳ１０２）。このとき、制御パケット生成部１０８は、ルーティングテーブル１０６に記憶されている、隣接ノード毎のパスコストのうち最小のパスコストをペイロード部に含めたハローパケットを生成する。例えばノードｂにおけるハローパケット生成時のルーティングテーブル１０６が図３に示される如きものである場合、最小のパスコスト「２」をペイロード部に含める。パケット送信部１０９は、制御パケット生成部１０８により生成されたハローパケットを、無線信号送受信部１０３をしてノードｂに隣接しているノードへ送信せしめる（ステップＳ１０３）。
【００４２】
図６は、ノードａ〜ｊの各々におけるパケット中継処理ルーチンを表すフローチャートである。図７は、パケット中継処理ルーチンに含まれるルーティングテーブル更新処理ルーチンを表すフローチャートである。図８は、ノードａ〜ｊにおける各隣接ノード間のリンクコストを各隣接ノード間に数値で示す図である。図９は、ノードｂ、ｆ、ｃ、ｅ及びｈにおけるルーティングテーブル１０６の一例を示す表である。以下、図６〜１０を参照しつつ、パケット中継処理について説明する。
【００４３】
先ず、シンクノードであるノードａに隣接するノードｂおけるパケット中継処理から順に説明する。
【００４４】
ノードｂの中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットがハローパケットか否かを判別する（ステップＳ２０１）。
【００４５】
中継処理部１０５は、当該パケットがハローパケットであると判別した場合、ルーティングテーブル１０６の更新を行う（ステップＳ２０２）。なお、ハローパケットのフォーマットは前述したように図４（ｂ）に示される如き形式である。
【００４６】
中継処理部１０５は、先ず、当該パケットのヘッダ部に含まれる送信元アドレスから当該パケットを送信したノードを判別し、当該ノードについてのパケット到達率を算出する（ステップＳ３０１）。中継処理部１０５は、当該パケットが例えばノードａからのものであると判別した場合、ノードａからのハローパケットの受信履歴及び当該パケットのヘッダ部に含まれるシーケンス番号からパケット到達率を算出する。例えばパケット到達率算出時点までに受信したノードａからのハローパケットの個数が８０個であり、当該パケットのシーケンス番号が１００である場合、パケット到達率は０．８（＝８０／１００）である。中継処理部１０５は、当該算出によって得られたノードａについてのパケット到達率を更新する（図９（ｂ））。なお、当該パケットの送信元アドレスがルーティングテーブル１０６に記録されていない場合には新規にその送信元アドレスを追加する。
【００４７】
次に中継処理部１０５は、隣接ノード毎のリンクコストを算出する（ステップＳ３０２）。中継処理部１０５は、例えばリンクコスト＝１０−パケット到達率×１０として算出する。例えばノードａについてのパケット到達率が０．８である場合、リンクコスト＝１０−０．８×１０＝２となる。中継処理部１０５は、当該算出によって得られたノードａについてのリンクコストを更新する（図９（ｂ））。
【００４８】
次に中継処理部１０５は、当該パケットに含まれるパスコスト（リンクコスト累積値）を取得する（ステップＳ３０３）。例えば当該パケットがノードａからのものである場合、ノードａはシンクノードなので当該パスコストは０である。
【００４９】
次に中継処理部１０５は、ノードａへパケットを中継したときの、ノードｂからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、中継処理部１０５は、ルーティングテーブル１０６に記憶されているノードａについてのリンクコスト「２」と、ノードａからのパケットから取得したパスコスト「０」とを加算してパスコスト「２」＝（２＋０）を算出する。中継処理部１０５は、当該算出によって得られたノードａについてのパスコストを更新する（図９（ｂ））。
【００５０】
ノードｂと同様にノードａに隣接するノードｆの場合も同様にしてノードａについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｆ））。
【００５１】
ノードｂとノードｆも互いに隣接しているので相互にハローパケットを交換する。
【００５２】
先ず、ノードｂは、ノードｆからのハローパケットのパケット到達率「０．５」を算出し（ステップＳ３０１）、ノードｆについてのリンクコスト「５」を算出する（ステップＳ３０２）。ノードｆは、自身のルーティングテーブル１０６中の最小のパスコストである「３」をペイロード部に含めてハローパケットを送信するので、ノードｂは、ノードｆからのハローパケットのパスコスト「３」を取得し（ステップＳ３０３）、ノードｆへパケットを中継したときの、ノードｂからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、ノードｂは、ルーティングテーブル１０６に記憶されているノードｆについてのリンクコスト「５」と、ノードｆからのパケットから取得したパスコスト「３」とを加算してパスコスト「８」＝（５＋３）を算出する。ノードｂの中継処理部１０５は、当該算出によって得られたノードｆについてのパケット到達率、リンクコスト及びパスコストを更新する（図９（ｂ））。
【００５３】
ノードｆの場合も同様にしてノードｂについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｆ））。
【００５４】
次に、ノードｂに隣接するノードｃの場合について説明する。先ず、ノードｃは、ノードｂからのハローパケットのパケット到達率「０．９」を算出し（ステップＳ３０１）、ノードｂについてのリンクコスト「１」を算出する（ステップＳ３０２）。ノードｂは、自身のルーティングテーブル１０６中の最小のパスコストである「２」をペイロード部に含めてハローパケットを送信するので、ノードｃは、ノードｂからのハローパケットのパスコスト「２」を取得し（ステップＳ３０３）、ノードｂへパケットを中継したときの、ノードｃからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、ノードｃは、ルーティングテーブル１０６に記憶されているノードｂについてのリンクコスト「１」と、ノードｂからのパケットから取得したパスコスト「２」とを加算してパスコスト「３」＝（１＋２）を算出する。ノードｃの中継処理部１０５は、当該算出によって得られたノードｂについてのパケット到達率、リンクコスト及びパスコストを更新する（図９（ｃ））。
【００５５】
ノードｂ及びｆに隣接するノードｅの場合も同様にしてノードｂ及びｆについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｅ））。
【００５６】
ノードｃとノードｅも互いに隣接しているので相互にハローパケットを交換する。
【００５７】
先ず、ノードｃは、ノードｅからのハローパケットのパケット到達率「０．６」を算出し（ステップＳ３０１）、ノードｅについてのリンクコスト「４」を算出する（ステップＳ３０２）。ノードｅは、自身のルーティングテーブル１０６中の最小のパスコストである「４」をペイロード部に含めてハローパケットを送信するので、ノードｃは、ノードｅからのハローパケットのパスコスト「４」を取得し（ステップＳ３０３）、ノードｅへパケットを中継したときの、ノードｃからノードａまでのパスコストを算出する（ステップＳ３０４）。具体的には、ノードｃは、ルーティングテーブル１０６に記憶されているノードｅについてのリンクコスト「４」と、ノードｆからのパケットから取得したパスコスト「４」とを加算してパスコスト「８」＝（４＋４）を算出する。ノードｃの中継処理部１０５は、当該算出によって得られたノードｅについてのパケット到達率、リンクコスト及びパスコストを更新する（図９（ｃ））。
【００５８】
ノードｅの場合も同様にしてノードｃについてのパケット到達率、リンクコスト及びパスコストを算出してルーティングテーブル１０６を更新する（図９（ｅ））。
【００５９】
次に、シンクノードａから最も遠い位置にあるノードｈの場合について説明する。ノードｈは、隣接するノードｄ、ｇ及びｊの各々からのハローパケットに応じて上記したのと同様の処理により、ノードｄ、ｇ及びｊの各々についてのパケット到達率及びリンクコストを算出する（ステップＳ３０１及びＳ３０２）。
【００６０】
ノードｄ、ｇ及びｊの各々も上記したのと同様に各隣接ノードについてのリンクコスト及びパスコストを算出してルーティングテーブル１０６に記憶している。ノードｄは、ノードｄからノードａまでの最小のパスコスト［６］（ノードａ、ｂ及びｃ経由のパス）、ノードｇは、ノードｇからノードａまでの最小のパスコスト［５］（ノードａ、ｂ及びｃ経由のパス）、ノードｊは、ノードｊからノードａまでの最小のパスコスト［６］（ノードａ、ｆ及びｉ経由のパス）、をそれぞれのハローパケットに含めて送信する。ノードｈは、ノードｄからのハローパケットから取得したパスコスト「６」と、ルーティングテーブル１０６に記憶されているノードｄについてのリンクコスト「２」とを加算してパスコスト「８」＝（６＋２）を算出する。同様にしてノードｈは、ノードｇ及びｊの各々についてのパスコスト「６」及び「７」を算出する。
【００６１】
このように、各隣接ノード間でハローパケットを交換することにより、ノードｂ〜ｊの各々がルーティングテーブル１０６を更新する。
【００６２】
再び図６を参照してノードｈにおけるパケット中継処理について説明する。
【００６３】
ノードｈの中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットが上りデータパケットであると判別した場合（ステップＳ２０３）、当該パケットの中継先ノードを選択する（ステップＳ２０４）。なお、前述したようにデータパケットのフォーマットは図４（ａ）に示される如き形式である。
【００６４】
このとき、中継処理部１０５は、ルーティングテーブル１０６（図９（ｈ））中の最小のパスコスト「６」に対応するノードｇを中継先ノードとして選択し、無線信号送受信部１０３をしてノードｇへ当該データパケットを送信せしめる（ステップＳ２０５）。この場合、データパケットは、ノードｈ、ｇ、ｃ、ｂ、ａの順に転送される。このときのノードｈからノードａまでの最小パスコスト「６」でデータパケットを中継することができる。
【００６５】
中継処理部１０５は、ノードｇからの受信確認パケットがパケット受信部１０４により受信された場合には、パケットの中継が成功したと判別して（ステップＳ２０６）、パケット中継処理を終了する。
【００６６】
一方、中継処理部１０５は、ノードｇからの受信確認パケットがパケット受信部１０４により受信されなかった場合には、パケットの中継が失敗したと判別して（ステップＳ２０６）、再度、中継先ノードを選択する（ステップＳ２０４）。この場合、中継処理部１０５は、ノードｇに対応するパスコスト「６」の次に小さいパスコスト「７」に対応するノードｊを中継先ノードとして選択する。中継処理部１０５は、無線信号送受信部１０３をしてノードｊへ当該データパケットを送信せしめる（ステップＳ２０５）。この場合、データパケットは、ノードｈ、ｊ、ｉ、ｆ、ａの順に転送される。
【００６７】
また、中継処理部１０５は、ノードｊに対するパケットの中継も失敗したと判別した場合、ノードｊに対応するパスコスト「７」の次に小さいパスコスト「８」に対応するノードｄを中継先ノードとして選択し、無線信号送受信部１０３がノードｄへ当該データパケットを送信する（ステップＳ２０５）。ノードｄ、ｇ及びｊの何れに対してもパケット中継が失敗したと判別した場合には、再度、ルーティングテーブル１０６中の最小のパスコストに対応するノードｇを中継先ノードとして選択するなどしてパケット中継処理を継続し、パケット中継が成功したと判別したときに終了する。
【００６８】
また、例えばノードｈとノードｇの間を人や自動車などの遮蔽物が通過したことにより、これら両ノード間のリンク状況が悪化した場合、ノードｇからのノードｈへのハローパケットの到達率が悪化する。例えばその到達率が０．７に悪化した場合、ノードｈが算出するノードgについてのリンクコストは３、パスコストは８となる。この場合、ノードｈのルーティングテーブル１０６は図１０に示されるように更新される。つまり、ルーティングテーブル１０６中の最小パスコストは７となるので、中継処理部１０５は、ルーティングテーブル１０６（図１０）中の最小のパスコスト「７」に対応するノードｊを中継先ノードとして選択し、無線信号送受信部１０３をしてノードｊへ当該データパケットを送信せしめる。この場合、データパケットは、ノードｈ、ｊ、ｉ、ｆ、ａの順に転送される。
【００６９】
なお、中継処理部１０５は、データパケットを中継する際に、そのヘッダ部に含まれる中継可能回数の値を減算する。中継処理部１０５は、中継可能回数の値が０であると判別した場合には、データパケットを中継せずにパケット中継処理を終了する。また、中継処理部１０５は、データパケットの中継が失敗したと判別する毎に、そのペイロード部に含まれる再送回数の値を減算する。中継処理部１０５は、再送回数の値が０であると判別した場合には、データパケットを中継せずにパケット中継処理を終了する。
【００７０】
また、中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットが上りデータパケットではないと判別した場合（ステップＳ２０３）、ＲＲＥＣパケット中継処理ルーチンに移行する（ステップＳ２０７）。ＲＲＥＣパケット中継処理については、第２の実施例で説明する。ノードｂ〜ｇ、ｉ及びｊの各々も上記したのと同様にデータパケットの中継処理を行う。
【００７１】
上記したように、本実施例によるパケット中継システムによれば、ノードｂ〜ｊの各々は、自身からノードａへの最適な経路を選択することが可能になる。つまり、自身からノードａまでのパスコストが最小となるように、データパケットの中継先ノードとすべき隣接ノードを選択できる。
【００７２】
各ノードは、自身に隣接するノードとの間でパケットを交換し、その到達率に基づいて、対応する隣接ノードについてのリンクコストを算出する。したがって、隣接ノード間でリンク状況が変動した場合においても適切なリンクコストを算出できる。また、自身からシンクノードまでの各リンクコストの加算によりシンクノードまでのパスコストを算出しているので、パスコストについてもリンク状況の変動に応じた適切な値を算出できる。
【００７３】
また、各ノードは、自身に隣接していないノードすなわちシンクノードから隣接ノードに至るまでの各ノードにより算出されたリンクコストの累積値を隣接ノードから取得し、当該累積値と自身が算出した隣接ノードについてのリンクコストから、シンクノードまでのパスコストを算出する。このような処理によりパスコストを算出するので、ネットワーク内の通信情報量を増加させること無くシンクノードへの上り経路を確立できる。
【００７４】
また、各ノードは、隣接ノード毎のパスコストを算出して記憶しているので、最適な隣接ノードに対するパケット中継が失敗した場合でも、次にパケット中継対象とすべき隣接ノードを適切に選択することができる。
【００７５】
＜第２の実施例＞
図１１は、本実施例によるノードｂの構成を表すブロック図である。なお、ノードａ及びｃ〜ｊの各々も同一の構成である。第１の実施例におけるノードｂの構成にパケット集約部１１０が更に含まれる。
【００７６】
パケット集約部１１０は、中継処理部１０５が隣接ノードの１からのＲＲＥＣパケットを受信したと判別した場合に当該パケットを所定の送信タイミングが到来するまで保持し、送信タイミングが到来するまでに中継処理部１０５が当該１の隣接ノード以外の隣接ノードからのＲＲＥＣパケットを受信したと判別したときに、これら両パケットに含まれているアドレスを集約した新たなＲＲＥＣパケット（以下、集約パケットとも称する）を生成し、送信タイミングの到来に応じてパケット送信部１０９をして中継先の隣接ノードへ中継せしめる。
【００７７】
図１２は、ツリー状に形成されたパケット中継システム２をＲＲＥＣパケットの中継方向と共に示す図である。パケット中継システム２は、最上位のノードであるノードａと、ノードａの下位のノードであり階層構造を形成しながらツリー状に配置されているノードｂ〜ｈからなる。ノードｂ〜ｈの各々は、同図に矢印で示される如く下位の側に位置するノードからのＲＲＥＣパケットを上位の側に位置するノードへ順次中継する。ノードｂ〜ｈの各々は、ＲＲＥＣパケットを中継する際に自身のアドレスをＲＲＥＣパケットに含めて中継する。パケット集約部１１０は、ＲＲＥＣパケットに含まれるこれらのアドレスを集約した新たなＲＲＥＣパケットを生成するのである。
【００７８】
図１３は、ＲＲＥＣパケット中継処理ルーチンを表すフローチャートである。このＲＲＥＣパケット中継処理ルーチンは、図６に示されるパケット中継処理ルーチンにおけるステップＳ２０７のＲＲＥＣパケット中継処理に対応する処理である。図１４は、各中継段階におけるＲＲＥＣパケットの集約例を、図１２に矢印と共に示される数字に対応させて表す図である。以下、図１２〜１５を参照しつつ、ＲＲＥＣパケット中継処理について説明する。
【００７９】
先ず、最下位ノードであるノードｈおけるＲＲＥＣパケット中継処理から順に説明する。
【００８０】
ノードｈの制御パケット生成部１０８は、ノードｈのアドレスを含むＲＲＥＣパケットを生成し、これをノードｈに隣接するノードｄへ送信する（図１２（１））。このとき、制御パケット生成部１０８は、図１４（１）に示される如く、ヘッダＨＤと、ペイロード部のパケットサイズＬＮと、当該パケットに含まれるアドレスの個数ＮＭ「１」と、ノードｈの例えばＩＰアドレスなどのアドレスＡＤ「ｈ」と、を含むＲＲＥＣパケットを生成する。以下、ノードｈのアドレスを単にアドレスｈと称する。他のノードのアドレスについても同様に、アドレスａ、アドレスｂ、・・・、アドレスｇと称する。
【００８１】
ノードｄの中継処理部１０５は、パケット受信部１０４により受信されたパケットのヘッダ部に含まれるパケットタイプから当該パケットがＲＲＥＣパケットか否かを判別する（ステップＳ４０１）。パケット集約部１１０は、中継処理部１０５が当該パケットがＲＲＥＣパケットであると判別した場合に、当該パケットに含まれるパケット情報を、所定の送信タイミングが到来するまで保持する（ステップＳ４０２、Ｓ４０３）。例えば、当該パケットがノードｈからのＲＲＥＣパケットである場合、パケット集約部１１０は、そのＲＲＥＣパケットに含まれるアドレスｈなどの情報を保持する。所定の送信タイミングは、例えば数秒〜数十秒など周期的なタイミングであり、予め設定されたタイミングである。
【００８２】
ノードｄのパケット集約部１１０は、所定の送信タイミングが到来した場合、アドレスｄ及びｈを含めたＲＲＥＣパケットを上位のノードであるノードｂへ送信する（ステップＳ４０５）。このとき、パケット集約部１１０は、図１４（２）に示される如く、ヘッダＨＤ及びパケットサイズＬＮと、アドレスの個数ＮＭ「２」と、アドレスｄ及びｈと、を含むＲＲＥＣパケットを生成する。なお、ノードｄのパケット受信部１０４はノードｈ以外のノードからはＲＲＥＣパケットを受信しないので、パケット集約部１１０はステップＳ４０４におけるＲＲＥＣパケット集約処理については省略する。
【００８３】
ノードｂの下位のノードｅもノードｈと同様の処理により、図１４（３）に示される如きＲＲＥＣパケットを上位のノードであるノードｂへ送信する。
【００８４】
ノードｂのパケット集約部１１０は、中継処理部１０５がパケット受信部１０４により受信されたパケットがＲＲＥＣパケットであると判別した場合に（ステップＳ４０１）、当該ＲＲＥＣパケットに含まれるパケット情報を、所定の送信タイミングが到来するまで保持する（ステップＳ４０２、Ｓ４０３）。例えば、当該パケットがノードｄからのＲＲＥＣパケットである場合、パケット集約部１１０は、そのＲＲＥＣパケットに含まれるアドレスｄ及びｈを保持する。
【００８５】
ノードｂのパケット集約部１１０は、中継処理部１０５が所定の送信タイミングが到来するまでに更にパケット受信部１０４によりＲＲＥＣパケットが受信されたと判別した場合（ステップＳ４０１）、同様にして当該ＲＲＥＣパケットに含まれるパケット情報を、所定の送信タイミングが到来するまで保持する（ステップＳ４０２、Ｓ４０３）。例えば、当該パケットがノードｅからのＲＲＥＣパケットである場合、パケット集約部１１０は、そのＲＲＥＣパケットに含まれるアドレスｅを保持する。
【００８６】
ノードｂのパケット集約部１１０は、所定の送信タイミングが到来した場合（ステップＳ４０３）、保持しているアドレス情報を集約して新たなＲＲＥＣパケットを生成する（ステップＳ４０４）。パケット集約部１１０は、図１４（４）に示される如く、ヘッダＨＤ及びパケットサイズＬＮと、親子関係にある複数のノードの各アドレスからなるアドレス群と、アドレス群毎のアドレス個数と、を含むＲＲＥＣパケットを生成する。
【００８７】
このとき、ノードｂのパケット集約部１１０は、自身のノードであるノードｂのアドレスｂを先頭のアドレス、ノードｂの子ノードであるノードｄのアドレスｄを２番目のアドレス、同じくノードｂの子ノードであるノードｅのアドレスｅを３番目のアドレスとするアドレス群（アドレスｂ、ｄ、ｅ）を生成し、その個数ＮＭを「３」とする。また、パケット集約部１１０は、ノードｄのアドレスｄを先頭のアドレス、ノードｄの子ノードであるノードｈのアドレスｈを２番目のアドレスとするアドレス群（アドレスｄ、ｈ）を生成し、その個数ＮＭを「２」とする。このようにして、パケット集約部１１０は、図１４（４）に示される如き新たなＲＲＥＣパケット（集約パケット）を生成する。
【００８８】
パケット集約部１１０は、新たなＲＲＥＣパケット（図１４（４））を上位ノードであるノードａへ送信する（ステップＳ４０５）。
【００８９】
ノードｃも、ノードｂと同様のＲＲＥＣパケット中継処理を行う。ノードｃのパケット集約部１１０は、ノードｆからのＲＲＥＣパケット（図１４（５））に含まれるアドレスｆと、ノードｇからのＲＲＥＣパケット（図１４（６））に含まれるアドレスｇと、を所定の送信タイミングが到来するまで保持し（ステップＳ４０２）、送信タイミングが到来したときに（ステップＳ４０３）、新たなＲＲＥＣパケットを生成する。
【００９０】
このとき、ノードｃのパケット集約部１１０は、自身のノードであるノードｃのアドレスｃを先頭のアドレス、ノードｃの子ノードであるノードｆのアドレスｆを２番目のアドレス、同じくノードｃの子ノードであるノードｇのアドレスｇを３番目のアドレスとするアドレス群（アドレスｃ、ｆ、ｇ）を生成し、その個数ＮＭを「３」として、図１４（７）に示される如き新たなＲＲＥＣパケット（集約パケット）を生成する。パケット集約部１１０は、新たなＲＲＥＣパケット（図１４（７））を上位ノードであるノードａへ送信する（ステップＳ４０５）。
【００９１】
ノードａは、下位ノードであるノードｂ及びｃの各々からＲＲＥＣパケット（図１４（４）及び（７））を受信する。ノードａがシンクノードである場合にはＲＲＥＣパケットの中継は行わないが、ノードａが更に上位のノードにＲＲＥＣパケットを中継する場合には、パケット集約部１１０は、ノードｂ及びｃの各々からＲＲＥＣパケットに含まれるアドレスを集約して図１４（８）に示される如きＲＲＥＣパケットを生成する。
【００９２】
このとき、ノードａのパケット集約部１１０は、自身のノードであるノードａのアドレスａを先頭のアドレス、ノードａの子ノードであるノードｂのアドレスｂを２番目のアドレス、同じくノードａの子ノードであるノードｃのアドレスｃを３番目のアドレスとするアドレス群（アドレスａ、ｂ、ｃ）を生成し、その個数ＮＭを「３」とする。また、パケット集約部１１０は、ノードｂのアドレスｂを先頭のアドレス、ノードｂの子ノードであるノードｄのアドレスｄを２番目のアドレス、同じくノードｂの子ノードであるノードｅのアドレスｅを３番目のアドレスとするアドレス群（アドレスｂ、ｄ、ｅ）を生成し、その個数ＮＭを「３」とする。
【００９３】
同様にして、パケット集約部１１０は、アドレス個数ＮＭ「２」のアドレス群（アドレスｄ、ｈ）と、アドレス個数ＮＭ「３」のアドレス群（アドレスｃ、ｆ、ｇ）とを生成し、これら全てのアドレス群を含む新たなＲＲＥＣパケット（図１４（８））を生成する。パケット集約部１１０は、図１４（８）に示される如きＲＲＥＣパケットを更に上位のノード（図示せず）へ送信する。
【００９４】
上記したように、本実施例によるパケット中継システムによれば、ツリー状に形成されたノードのうちの下位のノードから上位のノードへＲＲＥＣパケットを順次中継する際に、各下位ノードからのＲＲＥＣパケットに含まるアドレスを親子関係毎にまとめたアドレス群に集約して生成した新たなＲＲＥＣパケット（集約パケット）を上位ノードへ送信する。
【００９５】
従来のパケット中継システムでは、中継ノードが下位の各ノードからユニキャスト送信により送信されたＲＲＥＣパケットを集約することなくそのまま中継していたので、各ノードにおける送信タイミングが重なった場合、シンクノード周辺のトラフィックに輻輳が生じてしまうという問題があったが、本実施例によるパケット中継システムによれば、下位の各ノードからのＲＲＥＣパケットに含まれるアドレスを集約して１のＲＲＥＣパケットを上位のノードへ中継するので、トラフィックに輻輳が生じさせることはない。また、ＲＲＥＣパケットに含まれる各アドレス群は、親子関係毎にまとめられたものなので、最上位のシンクノードは、下位の各ノードの接続関係を把握することが可能であり、シンクノードからの下り経路を確立できる。
【００９６】
＜第３の実施例＞
図１５は、本実施例によるノードｃの構成を表すブロック図である。なお、ノードａ、ｂ及びｄ〜ｊの各々も同一の構成である。第１の実施例におけるノードｂの構成に２ホップ隣接テーブル１１１が更に含まれる。
【００９７】
図１６（ａ）は、ノードｃのルーティングテーブル１０６の一例を表す図である。図１６（ｂ）は、ノードｃの２ホップ隣接ノードテーブル１１１の一例を表す図である。ノードｃは、第１の実施例と同様のルーティングテーブル１０６の他に、２ホップ隣接テーブル１１１を有している。２ホップ隣接テーブル１１１には、１ホップのノードのアドレスと、２ホップのノードのアドレスが記憶されている。ここで、１ホップのノードとはノードｃに隣接するノードのことをいい、２ホップのノードとは１ホップのノードに隣接するノードであってノードｃとは隣接していないノードのことをいう。例えば、ノードｃについての１ホップのノードはノードｂ、ｅ、ｄ及びｇであり、２ホップのノードはノードａ、ｆ、ｅ、ｊ及びｈである。
【００９８】
ノードｃの中継処理部１０５は、パケット受信部１０４が例えば数秒〜数十秒などの周期的に受信する図４（ｂ）に示される如きハローパケットのペイロード部に含まれている、隣接アドレスに基づいて１ホップ及び２ホップのノードのアドレスを２ホップ隣接テーブル１１１に記憶する。例えばノードｂはノードｃの他、ノードａ、ｆ及びｅに隣接しているので、ペイロード部の隣接アドレスをアドレスａ、ｆ及びｅとしたハローパケットをノードｃへ送信する。
【００９９】
ノードｃの中継処理部１０５は、この隣接アドレスのうちノードｃに隣接していないアドレスすなわちアドレスａ、ｆを２ホップのノードのアドレスとして２ホップ隣接テーブル１１１に記憶すると共に、アドレスａ及びｆの各々にアドレスｂを対応付けて記憶する。中継処理部１０５は、他の隣接ノードからのハローパケットを受信した場合にも、同様の処理を施して図１６（ｂ）に示される如き２ホップ隣接テーブル１１１を生成する。
【０１００】
図１７は、下りデータパケット中継処理ルーチンを表すフローチャートである。この下りデータパケット中継処理ルーチンは、図１３に示されるＲＲＥＣパケット中継処理ルーチンにおけるステップＳ４０６の下りデータパケット中継処理に対応するものである。図１８は、パケット中継システム１を下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。以下、図１７及び図１８を参照しつつ、シンクノードであるノードａからノードｈへの下りデータパケット中継処理について説明する。
【０１０１】
先ず、シンクノードであるノードａにおける処理から説明する。図１９は、下りデータパケットのフォーマットの一例を表す図である。データパケットのヘッダ部には、パケットの種別を表す識別子であるパケットタイプ、パケット送信元のノードのアドレスである送信元アドレス、パケットの中継回数の制限を表す中継可能回数、パケット毎に付される連続番号であるシーケンス番号が含まれている。
【０１０２】
下りデータパケットのペイロード部には、パケット長、アドレス個数、当該アドレス個数分だけのアドレス、宛先へ送信すべきデータが含まれている。以下、ペイロード部に含まれるアドレスの一群をアドレスリストと称する。ノードａのパケット送信部１０９が送信する下りデータパケットのアドレスリストには、アドレスｂ、ｃ、ｇ、ｈの順にアドレスが記載されている。なお、この順番は第２に実施例で説明した如くノードａが受信した、下位のノードからのＲＲＥＣパケットに含まれているアドレス群から把握したノード接続状態に基づいて中継処理部１０５が設定した順番である。
【０１０３】
ノードａのパケット送信部１０９は、下りデータパケットを、アドレスリストの先頭に記載されているアドレスｂを宛先としてつまりノードｂへ送信する。
【０１０４】
ノードｂの中継処理部１０５は、ノードａからの下りデータパケットに含まれるアドレスリストの先頭に記載されているアドレスｂ（つまり自身のノードのアドレス）を削除してアドレスリストを変更する（ステップＳ５０１）。中継処理部１０５は、当該変更したアドレスリストを含む下りデータパケットをアドレスリストの先頭に記載されているアドレスｃを宛先としてつまりノードｃへ送信する（ステップＳ５０２）。
【０１０５】
ノードｂの中継処理部１０５は、パケット受信部１０４がノードｃからのパケット受信通知を受け取ったと判別した場合には、パケット中継が成功したと判別し（ステップＳ５０３）、中継処理を終了する。ノードｂの中継処理部１０５は、パケット受信部１０４がノードｃからのパケット受信通知を受け取れなかったと判別した場合には、パケット中継が失敗したと判別し（ステップＳ５０３）、２ホップ隣接テーブル１１１を参照する（ステップＳ５０４）。ここでは、パケット中継が成功したものとし、中継処理部１０５は、パケット中継処理を終了する。
【０１０６】
ノードｃの中継処理部１０５は、ノードｂからの下りデータパケットに含まれるアドレスリストの先頭に記載されているアドレスｃ（つまり自身のノードのアドレス）を削除してアドレスリストを変更する（ステップＳ５０１）。中継処理部１０５は、当該変更したアドレスリストを含む下りデータパケットをアドレスリストの先頭に記載されているアドレスｇを宛先としてつまりノードｇへ中継する（ステップＳ５０２）。ここで、ノードｃとノードｇと間を例えば人や自動車などの遮蔽物が通過するなどしてリンクの瞬断が生じた影響により、ノードｇへ下りデータパケットが到達できなかったものとする。
【０１０７】
ノードｃの中継処理部１０５は、パケット受信部１０４がノードｇからのパケット受信通知を受け取れなかったつまりパケット中継が失敗したと判別した場合（ステップＳ５０３）、図１６（ｂ）に示される如き２ホップ隣接テーブル１１１を参照する（ステップＳ５０４）。先ず、中継処理部１０５は、アドレスリスト内においてアドレスｇの次に記載されているアドレスｈが２ホップ隣接テーブル１１１における２ホップのノードのアドレスとして記憶されているか検索する（ステップＳ５０５）。
【０１０８】
アドレスｈが２ホップのノードのアドレスとして記憶されていた場合、中継処理部１０５は、アドレスｈに対応する１ホップのノードのアドレスｄ及びｇのうちの未中継のノードのアドレスつまりアドレスｄを下りデータパケットの宛先として決定する。中継処理部１０５は、アドレスリストのアドレスをアドレスｄ、ｈに変更し（ステップＳ５０１）、ノードｄへ中継する（ステップＳ５０２）。
【０１０９】
ノードｃの中継処理部１０５は、パケット受信部１０４がノードｄからのパケット受信通知を受け取ったと判別し（ステップＳ５０３）、パケット中継処理を終了する。ノードｄも上記したのと同様の処理により、アドレスリストのアドレスをアドレスｈに変更した下りデータパケットをノードｈへ中継する。
【０１１０】
上記したように本実施例によるパケット中継システムによれば、各ノードが、隣接ノードとの間で交換するパケットに含まれる２ホップ先のノードのアドレスを隣接ノードのアドレスと対応付けて記憶する。ノードが隣接ノードのうちの１へのパケット中継が失敗したと判別した場合に、２ホップ先の中継先ノードのアドレスに対応付けられているアドレスの１を選択し、当該１のアドレスの隣接ノードへパケットを中継する。
【０１１１】
従来のパケット中継システムにおいては、パケットが宛先ノードへ正しく転送されなかった場合にシンクノードからの下り経路を再確立するため、当該宛先ノードからシンクノードに対してＲＲＥＣコマンドを送信していたので、下り経路が再確立されるまでの間は、下り通信を行うことができないという問題があった。それに対して本実施例による中継システムによれば、パケットの中継先ノードを変更してパケットを中継するので、シンクノードからの下り経路の途中でパケット中継を失敗した場合においても、宛先ノードへパケットを迅速に中継することができる。
【０１１２】
上記した例は、ノードｃがパケット中継に失敗した場合の代替ノードの候補がノードｄのみの場合の例であるが、代替ノード候補が複数ある場合には、以下のような処理がなされる。
【０１１３】
図２０は、パケット中継システム１を下りデータパケットの中継方向と各中継段階におけるアドレスリストと共に表す図である。上記した例におけるパケット中継システム１に更にノードｋが追加されている。ノードｋは、同図に示されるとおり、ノードｃ及びｈと隣接するノードである。図２１（ａ）は、この場合のノードｃのルーティングテーブルの一例を表す図である。ノードｋについての隣接アドレス、リンクコスト、パスコスト、到着率が追加されている。図２１（ｂ）は、この場合のノードｃの２ホップ隣接ノードテーブルの一例を表す図である。２ホップのノードｈのアドレスｈにアドレスｄ、ｇ及びｋが対応付けられている。
【０１１４】
ノードｃの中継処理部１０５は、ノードｇへの下りデータパケットの中継が失敗したと判別した場合（ステップＳ５０３）、図２１（ｂ）に示される如き２ホップ隣接テーブル１１１を参照する（ステップＳ５０４）。
【０１１５】
中継処理部１０５は、アドレスリスト内においてアドレスｇの次に記載されているアドレスｈが２ホップ隣接テーブル１１１における２ホップのノードのアドレスとして記憶されているか検索する（ステップＳ５０５）。
【０１１６】
アドレスｈが２ホップのノードのアドレスとして記憶されていた場合、中継処理部１０５は、アドレスｈに対応する１ホップのノードのアドレスｄ及びｇのうちの未中継のノードのアドレスつまりアドレスｄ又はｋのいずれか１を下りデータパケットの宛先として決定する。
【０１１７】
このとき、中継処理部１０５は、図２１（ａ）に示される如きルーティングテーブルを参照し、アドレスｄに対応するリンクコスト「３」と、アドレスｋに対応するリンクコスト「１」とを比較し、リンクコストが小さい方のアドレスｋを下りデータパケットの中継先として決定する。中継処理部１０５は、アドレスリストのアドレスをアドレスｋ、ｈに変更し（ステップＳ５０１）、ノードｋへ中継する（ステップＳ５０２）。このような処理により、より適切な中継先ノード選択が可能となる。
【０１１８】
また、上記した例は、中継先ノードからの受信確認応答が１回でも得られなかった場合、直ぐに他の中継先ノードを選択する場合の例であるが、受信確認応答が得られなかった場合でも同一の中継先ノードに複数回のパケット送信を行い、それらの複数回送信が全て失敗したと判別した場合に他の中継先ノードを選択するようにしても良い。
【符号の説明】
【０１１９】
１ パケット中継システム
１０１ アンテナ
１０２ 増幅器
１０３ 無線信号送受信部
１０４ パケット受信部
１０５ 中継処理部
１０６ ルーティングテーブル
１０７ データパケット生成部
１０８ 制御パケット生成部
１０９ パケット送信部
１１０ パケット集約部
１１１ ２ホップ隣接テーブル
【特許請求の範囲】
【請求項１】
ツリー状に構成された複数のノードを含むパケット中継システムであって、
前記ノードの各々は、
前記複数のノードのうちの自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、
前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、
前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とするパケット中継システム。
【請求項２】
前記集約パケット生成手段は、複数のアドレスの一に対応する親ノードと前記親ノードに対する子ノードとからなるノード群に対応するアドレス群の集合を前記アドレスリストとして生成したパケットを前記集約パケットとすることを特徴とする請求項１に記載のパケット中継システム。
【請求項３】
データパケットを相互に中継する複数のノードを含むパケット中継システムであって、
前記ノードの各々は、
前記複数のノードのうちの自身に隣接する隣接ノードの一から当該一の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、
前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、
前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とするパケット中継システム。
【請求項４】
前記ノードは、
前記隣接ノードの各々からのパケットの到達率を前記隣接ノード毎に算出する到達率算出手段と、
前記到達率に基づいて前記隣接ノード毎のリンクコストを算出するリンクコスト算出手段と、を更に含み、
前記パケット中継手段は、隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスのうちの前記リンクコストが最小の隣接ノードに対応するアドレスを宛先として前記データパケットを中継することを特徴とする請求項３に記載のパケット中継システム。
【請求項５】
ツリー状に構成された無線通信路を介してデータパケットを中継する無線ノードであって、
自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、
前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、
前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とする無線ノード。
【請求項６】
前記集約パケット生成手段は、複数のアドレスの一に対応する親ノードと前記親ノードに対する子ノードとからなるノード群に対応するアドレス群の集合を前記アドレスリストとして生成したパケットを前記集約パケットとすることを特徴とする請求項５に記載の無線ノード。
【請求項７】
無線通信路を介してデータパケットを中継する無線ノードであって、
自身に隣接する隣接ノードの一から当該一の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、
前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、
前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とする無線ノード。
【請求項８】
前記隣接ノードの各々からのパケットの到達率を前記隣接ノード毎に算出する到達率算出手段と、
前記到達率に基づいて前記隣接ノード毎のリンクコストを算出するリンクコスト算出手段と、を更に含み、
前記パケット中継手段は、隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスのうちの前記リンクコストが最小の隣接ノードに対応するアドレスを宛先として前記データパケットを中継することを特徴とする請求項７に記載の無線ノード。
【請求項１】
ツリー状に構成された複数のノードを含むパケット中継システムであって、
前記ノードの各々は、
前記複数のノードのうちの自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、
前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、
前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とするパケット中継システム。
【請求項２】
前記集約パケット生成手段は、複数のアドレスの一に対応する親ノードと前記親ノードに対する子ノードとからなるノード群に対応するアドレス群の集合を前記アドレスリストとして生成したパケットを前記集約パケットとすることを特徴とする請求項１に記載のパケット中継システム。
【請求項３】
データパケットを相互に中継する複数のノードを含むパケット中継システムであって、
前記ノードの各々は、
前記複数のノードのうちの自身に隣接する隣接ノードの一から当該一の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、
前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、
前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とするパケット中継システム。
【請求項４】
前記ノードは、
前記隣接ノードの各々からのパケットの到達率を前記隣接ノード毎に算出する到達率算出手段と、
前記到達率に基づいて前記隣接ノード毎のリンクコストを算出するリンクコスト算出手段と、を更に含み、
前記パケット中継手段は、隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスのうちの前記リンクコストが最小の隣接ノードに対応するアドレスを宛先として前記データパケットを中継することを特徴とする請求項３に記載のパケット中継システム。
【請求項５】
ツリー状に構成された無線通信路を介してデータパケットを中継する無線ノードであって、
自身に隣接する隣接ノードの一からのパケットを所定の送信タイミングが到来するまで保持するパケット保持手段と、
前記送信タイミングが到来するまでに当該一の隣接ノード以外の隣接ノードからのパケットを受信した場合に当該受信したパケットに含まれるアドレスと前記パケット保持手段によって保持されているパケットに含まれるアドレスと自身のアドレスとを集約して得られたアドレスリストを含む集約パケットを生成する集約パケット生成手段と、
前記送信タイミングの到来に応じて前記隣接ノードのうちの最上位ノード側に位置する隣接ノードへ前記集約パケットを中継する集約パケット中継手段と、を含むことを特徴とする無線ノード。
【請求項６】
前記集約パケット生成手段は、複数のアドレスの一に対応する親ノードと前記親ノードに対する子ノードとからなるノード群に対応するアドレス群の集合を前記アドレスリストとして生成したパケットを前記集約パケットとすることを特徴とする請求項５に記載の無線ノード。
【請求項７】
無線通信路を介してデータパケットを中継する無線ノードであって、
自身に隣接する隣接ノードの一から当該一の隣接ノードのアドレスと前記一の隣接ノードに隣接する２ホップ隣接ノードのアドレスとを取得する２ホップ隣接ノードアドレス取得手段と、
前記２ホップ隣接ノード毎に前記２ホップ隣接ノードのアドレスと前記隣接ノードのアドレスとを対応付けて記憶する２ホップ隣接ノードアドレス記憶手段と、
前記隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスの一を宛先として前記データパケットを中継するパケット中継手段と、を含むことを特徴とする無線ノード。
【請求項８】
前記隣接ノードの各々からのパケットの到達率を前記隣接ノード毎に算出する到達率算出手段と、
前記到達率に基づいて前記隣接ノード毎のリンクコストを算出するリンクコスト算出手段と、を更に含み、
前記パケット中継手段は、隣接ノードの一へ前記データパケットを中継できなかったと判別した場合に当該一の隣接ノードのアドレスと共に前記２ホップ隣接ノードのアドレスの一に対応する隣接ノードのアドレスのうちの前記リンクコストが最小の隣接ノードに対応するアドレスを宛先として前記データパケットを中継することを特徴とする請求項７に記載の無線ノード。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１２−２３９２４３（Ｐ２０１２−２３９２４３Ａ）
【公開日】平成２４年１２月６日（２０１２．１２．６）
【国際特許分類】
【出願番号】特願２０１２−２０１６４０（Ｐ２０１２−２０１６４０）
【出願日】平成２４年９月１３日（２０１２．９．１３）
【分割の表示】特願２００９−１９８０９（Ｐ２００９−１９８０９）の分割
【原出願日】平成２１年１月３０日（２００９．１．３０）
【出願人】（００００００２９５）沖電気工業株式会社 (6,645)
【Ｆターム（参考）】
【公開日】平成２４年１２月６日（２０１２．１２．６）
【国際特許分類】
【出願日】平成２４年９月１３日（２０１２．９．１３）
【分割の表示】特願２００９−１９８０９（Ｐ２００９−１９８０９）の分割
【原出願日】平成２１年１月３０日（２００９．１．３０）
【出願人】（００００００２９５）沖電気工業株式会社 (6,645)
【Ｆターム（参考）】
[ Back to top ]