通信ルートの構築方法およびそれを用いる通信端末
【課題】通信ルートの計算時間を短縮でき、且つ、トポロジーデータを記録するためのメモリ領域を小さくできる通信ルートの構築方法および通信端末を提供する。
【解決手段】通信ネットワークは１台の親機と複数台の子機とで構成され、親機と各子機との間ではマルチホップ通信により信号を送受している。各子機は、直接通信可能な隣接端末を探索する処理を行っており、親機は、各子機から当該子機が直接通信可能な隣接端末に関するリンク情報を受信すると、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルＴＢ１に記録させた後、トポロジーテーブルＴＢ１に記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求めるルート探索処理を行う。
【解決手段】通信ネットワークは１台の親機と複数台の子機とで構成され、親機と各子機との間ではマルチホップ通信により信号を送受している。各子機は、直接通信可能な隣接端末を探索する処理を行っており、親機は、各子機から当該子機が直接通信可能な隣接端末に関するリンク情報を受信すると、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルＴＢ１に記録させた後、トポロジーテーブルＴＢ１に記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求めるルート探索処理を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチホップ通信を用いた通信端末における通信ルートの構築方法およびそれを用いる通信端末に関するものである。
【背景技術】
【０００２】
従来、無線通信網に接続された複数台の通信端末からなる通信ネットワークにおいて、通信端末間で通信信号を中継することで、自端末と直接通信できない端末との通信を行う方法が知られている（いわゆるマルチホップ通信）。
【０００３】
また近年、電力線に接続された複数台の電気機器の間で、電力線を通信線とした電力線搬送通信（以下、ＰＬＣ（Power Line Communication）と略す。）を行う電力線搬送通信ネットワーク（以下、ＰＬＣネットワークと言う。）が普及している。
【０００４】
このようなＰＬＣネットワークを利用し、集合住宅の各住戸に設置された電力量計に電力線搬送通信機能を付加するとともに、電気室にＰＬＣ親機を設置し、ＰＬＣ親機が各住戸の電力量計（ＰＬＣ子機）から検針データを取得して、取得した検針データをネットワークを通じて遠隔の検針サーバに送信するような遠隔検針システムが提案されている。また、集合住宅の電気室などに設置される幹線分岐盤に親機ユニットを設置するとともに、各住戸の住宅分電盤内に子機ユニットを設置して、親機ユニットと子機ユニットの間で分岐幹線を介して電力線搬送通信を行うことで、各住戸の電気使用量を監視、制御するシステムも提案されている。このシステムでは、子機ユニットから親機ユニットへ各住戸の電気使用量を送信させて、親機ユニットで各住戸の電気使用量と集合住宅全体の電気使用量とを同時に監視し、各住戸の電気使用量の合計が共用電気幹線の容量を超えそうな場合には、電気使用量の多い住戸の子機ユニットに親機ユニットが使用制限命令を送信し、子機ユニットが予め設定された家電製品を自動的に停止させて、集合住宅全体の電気使用量を制限するようにしている。ＰＬＣネットワークを利用したこれらのシステムでは、通信端末間の配線長が長く、また通信端末の接続台数も多くなるため、通信可能な距離にある通信端末が通信信号を中継することで、子機と親機との間で通信を行うマルチホップ通信が行われている（例えば、特許文献１を参照）。
【０００５】
ところで、上述した無線の通信ネットワークでは、ネットワーク内で端末が移動するため、ネットワークトポロジーが変化しやすい傾向があり、トポロジーの変化に対応して、各端末間の通信ルートを再構築する必要があった。またＰＬＣネットワークにおいても、電力線を介して通信を行うために、電気機器の発生するノイズの影響により通信不可能な状態になる場合があり、また電気機器からの電源プラグを電源コンセントに抜き差しすることで、電気機器の電力線への接続状態が変化し、通話不可能になる電気機器が発生するため、ネットワークトポロジーが変化しやすいという特徴があり、トポロジーの変化に対応して、各端末間の通信ルートを再構築する必要があった。
【０００６】
そこで、これらの通信ネットワークでは、所定時間が経過する毎に端末間で通信品質レベルの最も良い通信ルートを探索する必要があり、通信ルートを効率的に探索するためにダイクストラアルゴリズムと呼ばれるアルゴリズムが用いられていた（例えば非特許文献１参照）。
【特許文献１】特開２００６−６７５５７号公報
【非特許文献１】西丸泰之、佐藤文明；「ＱｏＳマルチキャスト配送木の構築方式」；情報処理学会研究報告 Vol.2003,No.34；社団法人 情報処理学会；２００３年３月２０日
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述の通信ネットワークでは、親機と各子機との間の通信ルートを構築するために、各通信端末が、自端末の生存を通知する通信パケット（Hello Packet、以下、Ｈパケットと略す。）の送受信を行うことで、直接通信可能な隣接端末を探索した後、探索結果を親機に通知するトポロジー通知メッセージを親機に対して返送しており、親機では受信したトポロジー通知メッセージから、リンクが確立している始点側の通信端末および終点側の通信端末の端末ＩＤと、両端末間の通信品質レベルを示すリンクコストを図１（ｃ）に示すようなトポロジーテーブルＴＢ１’に記録させている。そして、親機ではトポロジーテーブルＴＢ１’に記録されたリンク情報（各子機が直接通信可能な隣接端末に関する情報）をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを構築するようになっている。
【０００８】
ところで、図１（ｃ）に示すトポロジーテーブルＴＢ１’は、例えば始点側の通信端末の端末ＩＤを列、終点側の通信端末の端末ＩＤを行にとった２次元のデータテーブルからなり、始点側の通信端末に対応する列と終点側の通信端末に対応する行とが交差する升目にリンクコストを記録してある。また、升目に「−」が入っている箇所は対応する端末間でリンクが確立していないことを示している。ここで、始点側の通信端末と終点側の通信端末を入れ替えたセルには同じ値が記録されることになるので（ｍ行ｎ列のセルに入るリンクコストとｎ行ｍ列のセルに入るリンクコストは同じ値になるので）、図１（ｃ）に示すトポロジーテーブルＴＢ１’では、対角線を挟んだ一方の領域のみにデータを記録することでテーブルサイズを小さくしているが、リンクが確立していない端末間でもリンクコストを記録させるためのメモリ領域が確保されていた。そのため、メモリ領域が無駄になり、実際に使用するメモリ領域に比べて記憶容量の大きなＲＡＭを用意する必要があり、コスト高になるという問題があった。また、ダイクストラアルゴリズムを用いた通信ルートの探索には時間がかかり、端末の数が増えるほどルート探索に要する時間も長くなるため、通信ルートの探索時間を短縮したいという要求もあった。
【０００９】
本発明は上記問題点に鑑みて為されたものであり、請求項１、７の発明の目的とするところは、トポロジーデータを記録するためのメモリ領域を小さくできる通信ルートの構築方法および通信端末を提供することにある。また、請求項２〜６の発明の目的とするところは、通信ルートの探索に要する時間を短縮しつつ、トポロジーデータを記録するためのメモリ領域を小さくた通信ルートの構築方法を提供することにある。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、請求項１の発明は、通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行うにあたり、親機が各子機から直接通信可能な隣接端末に関するリンク情報を受信し、受信したリンク情報をもとに各子機への通信ルートを構築する通信ルートの構築方法であって、各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信ステップと、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるトポロジー記録ステップと、トポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築ステップとを備えることを特徴とする。
【００１１】
請求項２の発明は、請求項１の発明において、通信ルート構築ステップでダイクストラアルゴリズムを用いて各子機への通信ルートを求める際に、親機から対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、当該子機に至る全ての通信ルートを探索する前に当該子機への通信ルートの探索を終了することを特徴とする。
【００１２】
請求項３の発明は、請求項１又は２の発明において、 始点側の通信端末の端末ＩＤと、終点側の通信端末の端末ＩＤとの大小関係が一定の関係となるようにトポロジーテーブルがソートされた状態で通信ルート構築ステップを実行することを特徴とする。
【００１３】
請求項４の発明は、請求項１乃至３の何れかの発明において、トポロジーテーブルに記憶させた始点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする。
【００１４】
請求項５の発明は、請求項４の発明において、トポロジーテーブルに記憶させた終点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする。
【００１５】
請求項６の発明は、請求項１乃至５の何れかの発明において、トポロジー記録ステップにおいて、始点側または終点側の通信端末の端末ＩＤの少なくとも何れか一方が昇順又は降順に並ぶように、始点側および終点側の通信端末の端末ＩＤとリンクコストとをトポロジーテーブルに記録させることを特徴とする。
【００１６】
請求項７の発明は、通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行う親機側の通信端末であって、各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信手段と、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるテーブル処理手段と、ソートされたトポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築手段とを備えることを特徴とする。
【発明の効果】
【００１７】
請求項１の発明によれば、各子機から受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させているので、始点側の通信端末を列、終点側の通信端末を行にとった二次元のデータテーブルからなるトポロジーテーブルにリンクコストを記録させる場合に比べて、リンクが確立できていない端末間のリンクコストを記録させるメモリ領域が無駄になることがなく、トポロジーデータを記録させるための記憶容量を小さくした通信ルートの構築方法を実現することができる。
【００１８】
請求項２の発明によれば、親機から対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定しているので、親機と子機との間の通信ルートとして所定の通信品質以上の通信ルートを確保でき、また当該子機に至る全ての通信ルートを探索し、その中から通信品質が最も良い通信ルートを選択する場合に比べて短い時間で通信ルートを探索することができる。
【００１９】
請求項３の発明によれば、始点側の通信端末の端末ＩＤと、終点側の通信端末の端末ＩＤとの大小関係が一定の関係となるようにトポロジーテーブルがソートされた状態で通信ルート構築ステップを実行するので、所望の通信端末のリンク情報を検索する際に、まず始点側のみ順番に検索し、始点側が一致した時のみ終点側を検索することで、検索にかかる時間を短縮することができる。
【００２０】
請求項４の発明によれば、始点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築処理を行っているので、所望の通信端末のリンク情報を検索する際に検索にかかる時間を短縮することができる。
【００２１】
請求項５の発明によれば、終点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築処理を行っているので、所望の通信端末のリンク情報を検索する際に検索にかかる時間を短縮することができる。
【００２２】
請求項６の発明によれば、始点側または終点側の通信端末の端末ＩＤの少なくとも何れか一方が昇順又は降順に並ぶように、始点側および終点側の通信端末の端末ＩＤとリンクコストとをトポロジーテーブルに記録させているので、通信ルートを構築する際に端末ＩＤをソートする処理を行う必要がなくなり、通信ルートの探索にかかる時間をさらに短縮することができる。
【００２３】
請求項７の発明によれば、リンク情報受信手段が各子機から受信したリンク情報をもとに、テーブル処理手段が、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させているので、始点側の通信端末を列、終点側の通信端末を行にとった二次元のデータテーブルからなるトポロジーテーブルにリンクコストを記録させる場合に比べて、リンクが確立できていない端末間のリンクコストを記録させるメモリ領域が無駄になることがなく、トポロジーデータを記録させるための記憶容量を小さくできる通信端末を実現することができる。
【発明を実施するための最良の形態】
【００２４】
以下に、本発明に係る通信ルートの構築方法を、電力線搬送通信により通信を行う通信ネットワークに適用した実施形態について図面を参照して説明する。
【００２５】
（実施形態１）
本発明の実施形態１を図面に基づいて説明する。図１６は電力線搬送通信ネットワーク（以下、ＰＬＣネットワークと略す。）１の概略構成図である。このＰＬＣネットワーク１は、例えば集合住宅のような建築物等で用いられ、複数の通信端末２を電力線Ｌに接続することにより構成され、複数台の通信端末２の内の１台を親機Ａ、残りを子機Ｂｎ（ｎ＝１，２，３…）としている。
【００２６】
このＰＬＣネットワーク１では、親機Ａおよび子機Ｂｎが、通信可能な距離にある隣接端末２（親機Ａ又は子機Ｂｎ）との間で所定の通信プロトコル（例えばＳＣＰ、エコーネット等）を用いて電力線搬送通信を行っており、親機Ａが子機Ｂｎから所定の情報を収集するとともに、子機Ｂｎの遠隔監視が行われるものである。ここで、本ネットワーク１では、親機Ａと各子機Ｂｎとの間で直接又は間接に通信が行われ、親機Ａと直接通信できない子機Ｂｎは、通信可能な距離にある他の子機Ｂｎに通信信号を順次中継することで、親機Ａとの通信を行っている。
【００２７】
図１７は本実施形態に用いる通信端末２（親機Ａ又は子機Ｂｎ）のブロック図である。本実施形態では親機Ａと子機Ｂｎとに同一の通信端末２を用いており、例えば何れかの通信端末２で、ジャンパースイッチや切替スイッチなどの設定手段（図示せず）を用いて親機側に設定することで親機Ａとして機能させ、他の通信端末２では設定手段を用いて子機側に設定することで子機Ｂｎとして機能させるようになっている。
【００２８】
通信端末２は、記憶部３と、電力線搬送通信インターフェース部（以下、ＰＬＣインターフェース部と略す）４と、制御部５とを備える。記憶部３は、ＲＯＭなどの不揮発性のメモリや、ＥＥＰＲＯＭなどの書き換え可能な不揮発性のメモリや、ＲＡＭなどの揮発性メモリからなり、通信ルートや通信可能な隣接端末に関するリンク情報などを記憶するテーブル記憶部３ａを備えると共に、この通信端末２を動作させるための制御プログラムなどの各種プログラムや、各プログラムの実行に必要な情報などを記憶する。
【００２９】
テーブル記憶部３ａはテーブル形式のデータを記憶する領域であり、本端末が親機Ａの場合にはテーブル記憶部３ａに、ネットワーク内で構築された端末間の全通信ルートを登録するための通信ルートテーブルや、各端末が直接通信可能な隣接端末の情報（リンク情報）を記録するためのトポロジーテーブルが記憶される。一方、本端末が子機Ｂｎの場合にはテーブル記憶部３ａに、当該子機Ｂｎが通信可能な隣接端末２（親機Ａまたは他の子機Ｂｎ）と、当該子機Ｂｎと隣接端末２（親機Ａまたは他の子機Ｂｎ）との間の通信品質レベルを示す通信コスト値（以下、リンクコストと言う。）と、隣接端末２を経由した当該子機Ｂｎと親機Ａとの間の通信品質レベルを示す通信コスト値（以下、ルートコストと言う。）とを表す通信可能端末テーブルＤを記憶する。
【００３０】
表１は通信可能端末テーブルＤの１例を示し、このデータテーブルＤには、自端末と直接通信が可能な隣接端末２（親機Ａまたは他の子機Ｂｎ）に割り当てた端末ＩＤと、隣接端末２の種別（親機Ａまたは他の子機Ｂｎ）を示す端末種別データと、隣接端末２と自端末との間の通信品質レベルを示すリンクコストと、隣接端末２と親機Ａとの間のルートコストと、隣接端末２から親機Ａまでの通信ルートにおいて自機から１ホップ目、２ホップ目、…、Ｎホップ目の通信端末２を示す端末ＩＤとが対応付けて記憶されている。なお、上記の通信コスト値（リンクコストおよびルートコスト）は、隣接端末から受信した通信信号の受信信号強度を数段階のレベルで表したものであり、値が小さいほど、通信信号の減衰が小さく、通信品質レベルが高いことを示している。また、自端末から親機Ａまでのルートコストは、自端末と隣接端末との間のリンクコストに、隣接端末と親機Ａとの間の上位側ルートコストを加算した値になる。
【００３１】
【表１】
【００３２】
ここで、ＰＬＣネットワーク１では電力線Ｌを通じて通信を行うため、電力線Ｌに接続される他の家電機器から発生するノイズや、他の家電機器が接続されることによる電力線Ｌのインピーダンスの低下等によって、伝送環境が悪化し、通信エラー率が増大する虞がある。またＰＬＣネットワーク１の伝送環境は、家電機器の電源プラグを電源コンセントに抜き差したり、家電機器の可動状態に応じてダイナミックに変化する。そのため、ＰＬＣネットワーク１では、ネットワークトポロジーが固定的ではなく、変化しやすい傾向があり、ネットワークトポロジーが変化しても、親機Ａと子機Ｂｎとの間で通信を良好に行えるように、親機Ａと各子機Ｂｎとの間の通信ルートを定期的に探索し、最適な通信ルートを構築する必要がある。
【００３３】
すなわち通信端末２の制御部５は、例えば、マイクロプロセッサやその周辺回路等で構成され、親機Ａと子機Ｂｎとの間の通信ルートを探索するための処理［すなわち隣接端末を探索する処理や探索結果（リンク情報）を親機に通知する処理や親機側でリンク情報をもとにルートを探索する処理など］を実行するために、通信処理部５ａと、テーブル処理部５ｂと、ハロー・パケット送信タイマ部（以下、Ｈパケット送信タイマ部と略す）５ｃと、リンク通知パケット送信タイマ部５ｄとを備えている。
【００３４】
通信処理部５ａは、ＰＬＣインターフェース部４を用いて他の通信端末２との間で電力線搬送通信により通信信号を送受信し、後述の動作を行うことによって、親機Ａと子機Ｂｎとの間の通信ルートを構築する通信ルート構築処理（ルート探索処理およびルート選択処理からなる）を行う。図１８（ａ）は通信端末２（親機Ａおよび子機Ｂｎ）間で授受される通信パケットの基本フォーマットを示しており、送信元の通信端末２の送信端末ＩＤと、受信側の通信端末２の受信端末ＩＤと、メッセージタイプと、メッセージタイプに応じたデータ（メッセージ依存部）とで構成される。メッセージタイプとしては、自端末の生存や通信ルートを通知するためのハロー・パケット、隣接端末情報を親機に通知するためのリンク通知パケット、通常パケットを送信したときに中継途中で通信エラーが起こった場合に送信するルートエラーパケットなどがある。図１８（ｂ）はハロー・パケット（Ｈパケット）のパケットフォーマットを示し、送信端末ＩＤと、受信端末ＩＤと、メッセージタイプを示すデータ「Ｈｅｌｌｏ」と、送信元の端末タイプ（親機Ａまたは子機Ｂｎの種別）を示すデータと、子機側で求めた自機から親機Ａまでの通信ルートを示すデータとを少なくとも含み、リンクが喪失した端末が存在する場合はそのアドレスを示すリンク喪失端末アドレスを付加して構成される。また図１８（ｃ）はリンク通知パケットのパケットフォーマットを示し、送信端末ＩＤと、受信端末ＩＤと、メッセージタイプを示すデータ「リンク通知」と、子機側で求めた自機から親機Ａまでの通信ルートを示すルート情報と、直接通信可能な隣接端末に関する隣接端末情報とを少なくとも含み、リンクが喪失した端末が存在する場合はそのアドレスを示すリンク喪失端末アドレスを付加して構成される。また図１８（ｄ）はルートエラーパケットのパケットフォーマットを示し、送信端末ＩＤと、受信端末ＩＤと、メッセージタイプを示すデータ「ルートエラー」と、自機から親機Ａまでの通信ルートを示すルート情報と、通信エラーが発生したエラー箇所を示す情報とを含んで構成される。
【００３５】
またテーブル処理部５ｂは、テーブル記憶部３ａに記憶されているデータテーブル（通信ルートテーブル、トポロジーテーブル、通信可能端末テーブルＤなど）を管理する。
【００３６】
Ｈパケット送信タイマ部５ｃは時間を計時する計時手段を有し、所定の送信時間が経過する毎に通信処理部５ａにトリガ信号を与え、通信処理部５ａからＨパケットを送信させる。すなわち、Ｈパケットが所定の送信時間間隔で送信されることになる。
【００３７】
またリンク通知パケット送信タイマ部５ｄも時間を計時する計時手段を有し、所定の送信時間が経過する毎に通信処理部５ａにトリガ信号を与え、通信処理部５ａからリンク通知パケットを送信させる。すなわち、リンク通知パケットが所定の送信時間間隔で送信されることになる。
【００３８】
各通信端末２では、Ｈパケット送信タイマ部５ｃから通信処理部５ａに送信タイミングの到来を示す信号が出力されると、通信処理部５ａがＨパケットを作成し、ブロードキャストで電力線Ｌに送信しており、Ｈパケットを受信可能な隣接端末との間の通信品質レベル（リンクコスト）や、隣接端末の上位ルートに関する情報を取得する。
【００３９】
ここで、図３（ａ）に示す通信ネットワークにおいて通信ルートを構築する処理について以下に説明する。この通信ネットワークは１台の親機Ａと複数台（例えば６台）の子機Ｂ１〜Ｂ６とで構成され、親機Ａの端末ＩＤを１００、子機Ｂ１〜Ｂ６の端末ＩＤをそれぞれ１０１〜１０６に設定してある。また図３（ａ）において実線でつながれた端末同士は直接通信可能な端末を示し、両端末間をつなぐ線の近傍に表示した数字は両端末間のリンクコストを示している。
【００４０】
先ず親機Ａにおいて、Ｈパケット送信タイマ部５ｃから通信処理部５ａに送信タイミングの到来を示す信号が出力されると、通信処理部５ａが上述のＨパケットを作成し、ブロードキャストで電力線Ｌに送信する。この時、親機Ａから送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１００、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが親機となる。
【００４１】
子機Ｂ１，Ｂ２の通信処理部５ａは、親機Ａから送信されたＨパケットを受信することで、親機Ａと直接通信が可能であることが分かり、また上記Ｈパケットの受信信号強度から親機Ａとの間の通信品質レベル（リンクコスト）を算出することができる。そして、各子機Ｂ１，Ｂ２の通信処理部５ａでは、親機ＡからのＨパケットを受信することで、親機と直接通信できることが判明したため、上述のＨパケットを作成し、ブロードキャストで電力線Ｌに送信する。この時、子機Ｂ１から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０１、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、子機の求めた親機へのルートが子機Ｂ１（１０１）→親機Ａ（１００）で、そのルートコストが３となる。子機Ｂ２から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０２、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、子機の求めた親機へのルートが子機Ｂ２（１０２）→親機Ａ（１００）で、そのルートコストが２となる。
【００４２】
子機Ｂ３の通信処理部５ａでは、子機Ｂ１から送信されたＨパケットを受信することにより、子機Ｂ１との間で直接通信が可能であることが分かり、また子機Ｂ１からのＨパケットの受信信号レベルに基づいて子機Ｂ１との間のリンクコスト（＝５）を求める。この時、子機Ｂ３の通信処理部５ａでは、自機と親機とをつなぐ通信ルートとして子機Ｂ１を経由した通信ルートのみを発見でき、この通信ルートのルートコストは各ホップのリンクコストの総和（＝８）になる。なお、子機Ｂ３から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０３、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、親機への通信ルートが子機Ｂ３（１０３）→子機Ｂ１（１０１）→親機Ａ（１００）で、そのルートコストが８となる。
【００４３】
また子機Ｂ４の通信処理部５ａでは、子機Ｂ１，Ｂ２，Ｂ３から送信されたＨパケットを受信することにより、子機Ｂ１，Ｂ２，Ｂ３との間でそれぞれ直接通信が可能であることが分かり、また各子機からのＨパケットの受信信号レベルに基づいて各子機との間のリンクコスト（子機Ｂ１間はリンクコストが２、子機Ｂ２間はリンクコストが４、子機Ｂ３間はリンクコストが５）を求める。この時、子機Ｂ４の通信処理部５ａでは、自機と親機とをつなぐ通信ルートとして子機Ｂ１，Ｂ２，Ｂ３をそれぞれ経由した３つの通信ルートを発見でき、各通信ルートのルートコストは各ホップのリンクコストの総和になるので、子機Ｂ１を経由するルートコストが５、子機Ｂ２を経由するルートコストが６、子機Ｂ３を経由するルートコストが１３であることが分かる。ここで、ルートコストは値が小さいほど通信品質レベルが良好であるので、子機Ｂ１を経由するルートコストが最も小さいことから、子機Ｂ０の通信処理部５ａは、自機と親機Ａとの間の通信ルートとして「子機Ｂ４→子機Ｂ１→親機Ａ」との通信ルートを選択し、選択した通信ルートを通知するためのＨパケットを作成し、ブロードキャストで送信する。なお、子機Ｂ４から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０４、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、親機への通信ルートが子機Ｂ４（１０４）→子機Ｂ１（１０１）→親機Ａ（１００）で、そのルートコストが５となる。
【００４４】
他の子機Ｂ５（１０５），Ｂ６（１０６）も他の子機からのＨパケットを受信することで、直接通信可能な隣接端末を検出でき、隣接端末から親機Ａまでの通信ルートおよびその上位側ルートコストと、隣接端末との間のリンクコストをもとに自端末から親機Ａまでの通信ルートおよびそのルートコストを求め、Ｈパケットによりブロードキャスト送信する。
【００４５】
以上のようにして各子機Ｂ１〜Ｂ６では、親機Ａとの間の通信ルートを選択でき、また各子機ＢｎではＨパケットを送受することで、直接通信可能な隣接端末の情報を取得でき、リンク通知パケット送信タイマ部５ｄからトリガ信号が与えられると、隣接端末に関するリンク情報をリンク通知パケットに格納して親機Ａに送信する。
【００４６】
例えば、子機Ｂ４がリンク通知パケットを送信する場合、そのリンク通知パケットは、送信端末ＩＤが自機のＩＤ＝１０４、受信端末ＩＤが子機Ｂ１のＩＤ＝１０１、メッセージタイプが「リンク通知」、親機へのルートが子機Ｂ４（１０４）→子機Ｂ１（１０１）→親機Ａ（１００）でそのルートコストが５、隣接端末情報が子機Ｂ１（ＩＤ＝１０１、リンクコスト２）、子機Ｂ２（ＩＤ＝１０２、リンクコスト４）、子機Ｂ３（ＩＤ＝１０３、リンクコスト５）となる。このリンク通知パケットを受信した子機Ｂ１の通信処理部５ａでは、リンク通知パケットに含まれるルート情報を参照することにより、親機Ａに中継すれば良いことが分かるので、子機Ｂ４から受信したリンク通知パケットをもとに、親機Ａへ送信するリンク通知パケットを作成し、親機Ａに送信する。ここで、子機Ｂ１が送信するリンク通知パケットは、送信端末ＩＤが自機のＩＤ＝１０１、受信端末ＩＤが親機のＩＤ＝１００、メッセージタイプが「リンク通知」、親機へのルートが子機Ｂ４（１０４）→子機Ｂ１（１０１）→親機Ａ（１００）でそのルートコストが５、隣接端末情報が子機Ｂ１（ＩＤ＝１０１、リンクコスト２）、子機Ｂ２（ＩＤ＝１０２、リンクコスト４）、子機Ｂ３（ＩＤ＝１０３、リンクコスト５）となる。このリンク通知パケットを親機Ａが受信すると、リンク通知パケットに含まれる親機へのルート情報から送信元が子機Ｂ４（ＩＤ＝１０４）であることが分かるので、子機Ｂ４間の通信ルートに関する情報を取得するとともに、上記パケットに含まれる隣接端末情報をもとに、図３（ｂ）に示すようなトポロジーテーブルＴＢ１を作成する。このリンク通知パケットは各子機Ｂｎから一定の時間間隔で送信されるので、親機Ａでは各子機Ｂｎからのリンク通知パケットを受信することで、各子機Ｂｎとの間の通信ルートや、各子機Ｂｎの隣接端末情報を取得することができる。
【００４７】
而して、親機Ａの通信処理部５ａ（リンク情報受信手段）では、各子機Ｂｎからのリンク通知パケットを受信することで、各子機Ｂｎが直接通信可能な隣接端末の情報を取得することができ（リンク情報受信ステップ）、テーブル処理部５ｂを用いて、各子機Ｂｎの隣接端末に関するリンク情報をトポロジーテーブルＴＢ１に記憶させる。なお、リンク通知パケットに含まれる通信ルートのデータは、各子機が、Ｈパケットを送受できる範囲で求めた通信ルートであり、しかも１つのルートのデータしか含まれていなので、トポロジーの変化などによって通信ルートが不通となっている可能性もあり、親機Ａでは、トポロジーテーブルＴＢ１に記録されたリンク情報をもとに後述する探索処理を行って、各子機Ｂｎへの通信ルートを探索するようにしている。
【００４８】
ここで、従来の通信ネットワークでは、親機Ａが子機Ｂｎから送信されたトポロジー通知メッセージに基づいて、このメッセージに格納されたリンク情報（始点側および終点側の通信端末２の端末ＩＤとリンクコストからなる）を図１（ｃ）に示すトポロジーテーブルＴＢ１’に記録させていた。このトポロジーテーブルＴＢ１’は、始点側の通信端末を列、終点側の通信端末を行にとった二次元のデータテーブルで構成されているため、通信端末の個数をｎ個とすると、リンクコストを記録させるメモリ領域が［（ｎ−１）！］個用意されることになり、双方向リンクが確立できていない端末間のリンクコストを記録させるためのメモリ領域が無駄になるという問題があった。
【００４９】
そこで、本実施形態では親機Ａのテーブル処理部５ｂ（テーブル処理手段）が、子機Ｂｎからのトポロジー通知メッセージに格納されて送信されてきたリンク情報を、図１（ａ）に示すようなトポロジーテーブルＴＢ１に格納している（トポロジー記録ステップ）。尚、図１，図２では図示を簡単にするため始点ノードおよび終点ノードを１桁の数字で示している。
【００５０】
本実施形態で用いるトポロジーテーブルＴＢ１は、始点側の通信端末（始点ノード）の端末ＩＤ、終点側の通信端末（終点ノード）の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元に記録したテーブルからなり、リンク情報が通知された分のメモリ領域しか必要とせず、図１（ｃ）に示すトポロジーテーブルＴＢ１’のように予め所定個数のメモリ領域を確保する場合に比べてメモリ領域を小さくでき、無駄になるメモリ領域が発生しないので、メモリ領域を有効に活用することができ、記憶容量が必要以上に大きいメモリを用意する必要がないので、通信端末のコストが増大するのを防止できるという利点がある。
【００５１】
なお親機Ａの通信処理部５ａでは、トポロジーテーブルＴＢ１に記録されたリンク情報をもとに、各子機Ｂｎへの通信ルートを探索する後述のルート探索処理を実行するのであるが、リンク情報の検索を容易にするために、図１（ｂ）に示すように始点ノードの端末ＩＤと、終点ノードの端末ＩＤとの大小関係が一定の関係（例えば、（始点ノードの端末ＩＤ）＜（終点ノードの端末ＩＤ））となるようにトポロジーテーブルＴＢ１に記録させることが好ましい。ここで、検索対象の端末と通信可能なリンク（端末）を検索する際に、始点ノードの端末ＩＤと終点ノードの端末ＩＤとの大小関係に一定の関係付けが行われていない場合は、トポロジーテーブルＴＢ１に記録されている全てのリンク情報の始点側のＩＤと終点側のＩＤを両方共に検索しなければならないが、（始点ノードの端末ＩＤ）＜（終点ノードの端末ＩＤ）となるようにトポロジーテーブルＴＢ１に記録させておけば、始点側或いは終点側の片方だけを検索すれば良く、通信ルートの計算にかかる時間を短縮できるという利点がある。
【００５２】
また、図２（ａ）に示すトポロジーテーブルＴＢ１のように始点ノードの端末ＩＤあるいは終点ノードの端末ＩＤが昇順または降順にソートされていない場合は、所望の端末のリンク情報を検索するのに、先頭レコードから順番に検索しなければならないため時間を要するが、図２（ｂ）に示すように始点ノードの端末ＩＤを昇順にソートすることで、所望の端末のリンク情報を検索するのに２分探索などの探索アルゴリズムを利用できるから、端末の検索処理を効率よく行うことができる。また、図２（ｃ）に示すように始点ノードの端末ＩＤを第１キーとして昇順にソートした後に、終点ノードの端末ＩＤを第２キーとして昇順にソートすることで、所望の端末のリンク情報を検索する処理をさらに効率よく行うことができる。尚、図２（ｂ）（ｃ）に示すトポロジーテーブルＴＢ１では、始点ノードまたは終点ノードを昇順にソートしているが、降順にソートしても良く、所望の端末のリンク情報を検索する処理を効率よく行うことができる。また、図２（ｂ）に示すトポロジーテーブルＴＢ１では、始点ノードの端末ＩＤを昇順にソートしているが、終点ノードの端末ＩＤを昇順にソートしても良いし、終点ノードの端末ＩＤを第１キーとして昇順にソートした後、始点ノードの端末ＩＤを第２キーとして昇順にソートしても良い。また、親機Ａの通信処理部５ａが、テーブル処理部５ｂを用いて始点ノードおよび終点ノードの端末ＩＤとリンクコストとをトポロジーテーブルＴＢ１に記録させる際に、端末ＩＤが昇順又は降順に並ぶようソートしてからトポロジーテーブルＴＢ１に記録させておけば、所望の端末のリンク情報を検索する際に短時間で検索を行えるが、トポロジー通知メッセージを受信した順番にリンク情報をトポロジーテーブルＴＢ１に記録させておき、所望の端末のリンク情報を検索する際に、端末ＩＤが昇順または降順に並ぶようにソートしてから、検索を行うようにしても良い。
【００５３】
以上のようにして、親機Ａが、ネットワークを構成する子機Ｂｎからトポロジー通知メッセージを受信し、記憶部３内のトポロジーテーブルＴＢ１にリンク情報を記録させると、親機Ａの通信処理部５ａ（通信ルート構築手段）が、トポロジーテーブルＴＢ１に記録させたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求めるルート探索処理を行う（通信ルート構築ステップ）。
【００５４】
ここで、親機Ａによるルート探索処理について図３〜図１１を参照して説明する。なお、各端末で隣接端末の探索処理を行い、リンク情報をリンク通知パケットに格納して親機Ａ（１００）に送信することで、親機ＡのトポロジーテーブルＴＢ１には各端末のリンク情報が記録されているものとする（図３（ｂ）参照）。また図５（ａ）は親機Ａのテーブル記憶部３ａに用意された通信ルートの演算テーブルＴＢ２を示している。演算テーブルＴＢ２は通信ルートを探索する過程で使用されるテーブルであり、この演算テーブルＴＢ２には、各端末の端末ＩＤ１００〜１０６に対して、前ホップの端末ＩＤと、ルート構築端末に設定されたか否かを示すフラグＶｉｓｉｔと、親機Ａからのホップ数ＨＯＰと、親機Ａからのルートコストとを記録するようになっている。
【００５５】
図４は親機Ａによるルート探索処理のフローチャートであり、先ず親機Ａの通信処理部５ａは、自機（端末ＩＤ＝１００）をルート構築端末に決定するとともに（Ｓ１）、ルート構築端末を検索対象に決定し、図５（ｂ）に示すように自機（端末ＩＤ＝１００）のフラグＶｉｓｉｔをＴＲＵＥ（○）にする（Ｓ２）。そして、親機Ａの通信処理部５ａは、始点ノードを検索対象の端末ＩＤ（＝１００）に指定するとともに、終点ノードの端末ＩＤを１０１、１０２、１０３、…、１０６に順番に指定し、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。ここで、検索対象の端末と通信可能なリンクをトポロジーテーブルＴＢの先頭から順番に検索していくと、特にトポロジー数が多い場合には検索に非常に長い時間を要するので、始点ノードおよび終点ノードを指定して検索するが、上述のようにトポロジーテーブルＴＢ１は始点ノード或いは終点ノードの端末ＩＤが昇順又は降順にソートされているので、先ず始点ノードを２分探索を用いて検索した後、抽出されたリンクから終点ノードが一致するリンクを検索することで、検索に要する時間をかなり短縮することができる。
【００５６】
そして、Ｓ３においてトポロジーテーブルＴＢ１に該当リンクを発見できれば該当リンクのルートコストＲＣ１と、演算テーブルＴＢ２に記録されているルートコストＲＣとの大小を比較し（Ｓ４）、今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣよりも小さければ（ＲＣ＞ＲＣ１）、演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰを書き込んだ後（Ｓ５）、Ｓ２に戻って処理を続行する。一方、Ｓ４において今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣ以上であれば（ＲＣ≦ＲＣ１）、通信処理部５ａは演算テーブルＴＢ２へのルートコストの書き込み処理は行わず、Ｓ２に戻って処理を続行する。なお演算テーブルＴＢ２にルートコストが記録されていない場合は、今回発見したルートコストＲＣ１を演算テーブルＴＢ２に書き込むものとする。ここで、検索対象の端末が親機（端末ＩＤ＝１００）の場合は、端末ＩＤが１０１，１０２の端末とリンクがつながっており、両端末間のホップ数ＨＯＰ（＝１）と前ホップの端末ＩＤとルートコストＲＣ［端末（１０１）が３，端末（１０２）が２］が演算テーブルＴＢ２に記録される（図５（ｃ）参照）。
【００５７】
検索対象の端末について通信可能なリンクを全て検索し終えると、親機Ａの通信処理部５ａは、演算テーブルＴＢ２から、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（Ｖｉｓｉｔの欄に○がついていない端末）が存在するかを検索し（Ｓ６）、存在する場合はフラグＶｉｓｉｔがＦＡＬＳＥとなっている端末の中でルートコストが最小の端末を検索対象に決定するとともに、この端末のフラグＶｉｓｉｔをＴＲＵＥ（○）として（Ｓ７）、Ｓ３に戻り、上述の処理を繰り返す。
【００５８】
ここで、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０１〜１０６）の中でルートコストが最小の端末は、端末ＩＤが１０２の端末（以下、端末（１０２）と表す）なので、通信処理部５ａは、この端末を検索対象に設定し、図６（ａ）に示すように端末（１０２）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０２）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０１、１０３、１０４、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。そして、トポロジーテーブルＴＢ１に該当リンクを発見できれば、今回発見した該当リンク（端末ＩＤが１０４，１０５，１０６の端末）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きする（図６（ｂ）参照）。なお、ルートコストは自機と親機との間の通信コスト値であるので、ルートコストは各ホップのリンクコストの合計値となる。例えば端末（１０４）では、端末（１００）と端末（１０２）の間のリンクコスト（＝２）と、端末（１０２）と端末（１０４）の間のリンクコスト（＝４）との合計値（＝６）となる。
【００５９】
端末（１０２）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０１、１０４〜１０６）の中でルートコストが最小の端末（１０１）を検索対象に設定し、図７（ａ）に示すように端末（１０１）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０１）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０３、１０４、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。そして、トポロジーテーブルＴＢ１に該当リンクを発見できれば、今回発見した該当リンク（端末ＩＤが１０３〜１０５の端末）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きする（図７（ｂ）参照）。ここで、端末（１０３）は、演算テーブルＴＢ２にデータが記録されていなかったので、今回発見したリンクのルートコストと前ホップの端末ＩＤとホップ数とを演算テーブルに記録する。また、端末（１０４）は、今回発見したリンク（前ホップの端末ＩＤが１０１）のルートコストＲＣ１（＝５）の方が、演算テーブルＴＢ２に記憶されているルートコストＲＣ（＝６）よりも小さいので、今回発見したリンクのルートコストと前ホップの端末ＩＤとホップ数とを演算テーブルに記録する。一方、端末端末（１０５）のルートコストは、今回発見したリンク（前ホップの端末ＩＤが１０１）のルートコストＲＣ１の方が、演算テーブルＴＢ２に記憶されているルートコストＲＣ以上となるので、演算テーブルＴＢ２のデータはそのままとする。
【００６０】
次に、端末（１０１）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０３〜１０６）の中でルートコストが最小の端末（１０４）を検索対象に設定し、図８（ａ）に示すように端末（１０４）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０４）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０３、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。この場合、トポロジーテーブルＴＢ１には該当するリンクが発見できないので、演算テーブルＴＢ２のデータはそのままとする（図８（ｂ）参照）。
【００６１】
端末（１０４）ついて、通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０３，１０５，１０６）の中でルートコストが最小の端末（１０６）を検索対象に設定し、図９（ａ）に示すように端末（１０６）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０６）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０３、１０５に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。そして、トポロジーテーブルＴＢ１に該当リンクが発見できれば、今回発見した該当リンク（端末（１０５））のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較する。この場合、端末（１０５）のルートコストは、今回発見したリンク（前ホップの端末ＩＤが１０６）のルートコストＲＣ１の方が、演算テーブルＴＢ２に記憶されているルートコストＲＣ以上となるので、演算テーブルＴＢ２のデータはそのままとする（図９（ｂ）参照）。
【００６２】
端末（１０６）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０３）、（１０５）の中でルートコストが最小の端末（１０３）を検索対象に設定し（この場合はルートコストが同じ値となっているので端末ＩＤの小さい方に決定）、図１０（ａ）に示すように端末（１０３）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０３）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０５に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。この場合、トポロジーテーブルＴＢ１には該当するリンクが発見できないので、演算テーブルＴＢ２のデータはそのままとする（図１０（ｂ）参照）。
【００６３】
端末（１０３）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０５）を検索対象に設定し、図１１（ａ）に示すように端末（１０５）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０５）に指定するが、フラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末が存在しないので終点ノードの指定が行えず、該当リンクの検索処理は行わないまま、処理を終了するので、演算テーブルＴＢ２のデータはそのままとなる（図１１（ｂ）参照）。そして、端末（１０５）について処理を終えると、全ての端末のフラグＶｉｓｉｔがＴＲＵＥとなるので、通信処理部５ａは、全ての端末の通信ルートが設定できたと判断し、テーブル処理部５ｂを用いて演算テーブルＴＢ２の情報を記憶部３の通信ルートテーブルに反映させて（Ｓ８）、ルート探索処理を終了し、以後は通信ルートテーブルに記録された通信ルートを用いて親機Ａと各子機Ｂｎとの間で通信信号が授受されるのである。
【００６４】
（実施形態２）
本発明の実施形態２を図１２〜図１５に基づいて説明する。本実施形態では、実施形態１で説明した通信ネットワークにおいて、通信ルート構築ステップで親機Ａが各子機への通信ルートを求める際に、親機Ａから対象の子機に至る通信ルートとして、所定の通信品質以上（すなわちルートコストＲＣが所定の閾値以下）の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、探索対象の子機に至る全ての通信ルートを探索する前に当該子機への通信ルートの探索を終了するようにしている。例えば本実施形態ではルートコストの閾値を、１ホップ目であれば５、２ホップ目であれば１０、３ホップ目であれば１５に設定している。尚、ルート探索処理以外は実施形態１で説明した通信ネットワークと同様であるので、同一の構成要素には同一の符号を付して、その説明は省略する。
【００６５】
親機Ａによるルート探索処理を図１２のフローチャートに基づいて説明する。ところで、図１３（ａ）は親機Ａの通信処理部５ａがルート探索処理を行う際に用いる演算テーブルＴＢ２を示し、実施形態１で説明した演算テーブルＴＢ２において通信ルートが決定されたか未決定かを示すルート決定フラグを追加してある。
【００６６】
親機Ａの通信処理部５ａがルート探索処理を開始すると、先ず自機（端末ＩＤ＝１００）をルート構築端末に決定するとともに（Ｓ１０）、ルート構築端末を検索対象に決定し、図１３（ｂ）に示すように自機（端末ＩＤ＝１００）のフラグＶｉｓｉｔをＴＲＵＥ（○）、ルート決定フラグを「決定」にするとともに、他の端末のルート決定フラグを「未決定」にする（Ｓ１１）。そして、親機Ａの通信処理部５ａは、始点ノードを検索対象の端末ＩＤ（＝１００）に指定するとともに、終点ノードの端末ＩＤを１０１、１０２、１０３、…、１０６に順番に指定し、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ１２）。ここで、検索対象の端末と通信可能なリンクをトポロジーテーブルＴＢの先頭から順番に検索していくと、特にトポロジー数が多い場合には検索に非常に長い時間を要するので、始点ノードおよび終点ノードを指定して検索するが、実施形態１で説明したようにトポロジーテーブルＴＢ１は始点ノード或いは終点ノードの端末ＩＤが昇順又は降順にソートされているので、先ず始点ノードを２分探索を用いて検索した後、抽出されたリンクから終点ノードが一致するリンクを検索することで、検索に要する時間をかなり短縮することができる。
【００６７】
そして、Ｓ１２においてトポロジーテーブルＴＢ１に該当リンクを発見できれば該当リンクのルートコストＲＣ１と、演算テーブルＴＢ２に記録されているルートコストＲＣとの大小を比較し（Ｓ１３）、今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣよりも小さければ（ＲＣ＞ＲＣ１）、演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰを書き込む（Ｓ１４）。一方、Ｓ１３において、今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣ以上であれば（ＲＣ≦ＲＣ１）、通信処理部５ａは演算テーブルＴＢ２へのルートコストの書き込みは行わず、Ｓ１２に戻って処理を継続する。なお演算テーブルＴＢ２にルートコストが記録されていない場合は、今回発見したルートコストＲＣ１を演算テーブルＴＢ２に書き込むものとする。また、Ｓ１４で演算テーブルへの書き込みを終えると、通信処理部５ａはルートコストが閾値以下であるか否かを判定し（Ｓ１５）、閾値以下であれば当該子機への通信ルートを決定し、ルート決定フラグを「決定」とした後（Ｓ１６）、Ｓ１２に戻って処理を継続する。また、Ｓ１５においてルートコストが閾値よりも大きければ、通信処理部５ａは、ルート決定フラグを「未決定」のままとし、Ｓ１２に戻って処理を継続する。
【００６８】
ここで、検索対象の端末が親機（端末ＩＤ＝１００）の場合は、端末ＩＤが１０１，１０２の端末（１０１）および端末（１０２）とリンクがつながっているので、通信処理部５ａは、両端末間のホップ数ＨＯＰ（＝１）と前ホップの端末ＩＤとルートコスト［端末（１０１）が３，端末（１０２）が２］を演算テーブルＴＢ２に記録するとともに（図１３（ｂ）参照）、各端末のルートコストが１ホップ目の閾値（＝５）以下となっていることから、各端末（１０１），（１０２）のルート決定フラグを「決定」とする（図１３（ｃ）参照）。
【００６９】
検索対象の端末について通信可能なリンクを全て検索し終えると、親機Ａの通信処理部５ａは、演算テーブルＴＢ２から、ルート決定フラグが「未決定」となっている端末が存在するかを検索し（Ｓ１７）、存在する場合はフラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（Ｖｉｓｉｔの欄に○がついていない端末）が存在するかを検索し（Ｓ１８）、存在する場合はフラグＶｉｓｉｔがＦＡＬＳＥとなっている端末の中でルートコストが最小の端末を検索対象に決定するとともに、この端末のフラグＶｉｓｉｔをＴＲＵＥ（○）として（Ｓ１９）、Ｓ１２に戻り、上述の処理を繰り返す。一方、Ｓ１７でルート決定フラグが「未決定」の端末が存在しなかったり、フラグＶｉｓｉｔがＦＡＬＳＥの端末が存在しなかった場合、親機Ａの通信処理部５ａはルート探索処理が完了したと判断し、演算テーブルＴＢ２の情報を通信ルートテーブルに反映させる（Ｓ２０）。
【００７０】
ここで、親機Ａの通信処理部５ａが、親機１００と通信可能なリンクの検索を全て終了した時点では、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０１〜１０６）の中でルートコストが最小の端末は、端末ＩＤが１０２の端末なので、通信処理部５ａは、この端末（１０２）を検索対象に設定し、図１４（ａ）に示すように端末（１０２）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０２）に指定するとともに、終点ノードを「ルート決定フラグ」が「未決定」となっている端末の端末ＩＤ１０３、１０４、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ１２）。そして、トポロジーテーブルＴＢ１に該当リンクが発見できれば、今回発見した該当リンク（端末ＩＤが１０４，１０５，１０６の端末）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤ（＝１０２）とルートコストＲＣとホップ数ＨＯＰ（＝２）を上書きした後、ルートコストを２ホップ目の閾値（＝１０）と比較し、何れのルートコストも閾値以下となっているので、ルート決定フラグを「決定」とする（図１４（ｂ）参照）。
【００７１】
端末（１０２）について通信可能な端末の検出が全て終了すると、親機Ａの通信処理部５ａは、演算テーブルＴＢ２から、ルート決定フラグが「未決定」となっている端末が存在するかを検索する。ここで、端末ＩＤが１０３の端末（１０３）はルート決定フラグが未決定となっているので、親機Ａの通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末を検索し、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末の中でルートコストが最小の端末（端末ＩＤが１０１の端末）を検索対象に設定し、図１５（ａ）に示すように端末（１０１）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０１）に指定するとともに、終点ノードを「ルート決定フラグ」が「未決定」となっている端末の端末ＩＤ１０３に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ１２）。そして、トポロジーテーブルＴＢ１に該当リンクが発見できれば、端末（１０３）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きする。ここで、端末（１０３）はルートコストが未定であったので、親機Ａの通信処理部５ａは、端末（１０３）について前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きした後、ルートコストを２ホップ目の閾値（＝１０）と比較し、何れのルートコストも閾値以下となっているので、ルート決定フラグを「決定」とする（図１５（ｂ）参照）。
【００７２】
端末（１０１）について通信可能な端末の検出が全て終了すると、全ての端末のルート決定フラグが「決定」となるので、親機Ａの通信処理部５ａは、全ての端末の通信ルートが設定できたと判断し、テーブル処理部５ｂを用いて演算テーブルＴＢ２の情報を記憶部３の通信ルートテーブルに反映させて、ルート探索処理を終了し（Ｓ２０）、以後は通信ルートテーブルに記録された通信ルートを用いて親機Ａと各子機Ｂｎとの間で通信信号が授受されるのである。
【００７３】
以上説明したように本実施形態では、親機Ａの通信処理部５ａがルート探索処理を行う際に、親機Ａから対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルート（つまりルートコストが所定の閾値以下の通信ルート）が探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、当該子機への通信ルートの探索処理を終了しているので、親機Ａと子機Ｂｎとの間の通信ルートとして所定の通信品質以上の通信ルートを確保でき、また当該子機に至る全ての通信ルートを探索し、その中から通信品質が最も良い通信ルートを選択する場合に比べて短い時間で通信ルートを探索することができる。
【００７４】
なお本実施形態では、実施形態１で説明したトポロジーテーブルＴＢ１を用いて通信ルートの探索処理を行っているが、従来のトポロジーテーブルＴＢ１’を用いて本実施形態のようなルート探索処理を行った場合でも、親機Ａから対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルート（つまりルートコストが所定の閾値以下の通信ルート）が探索できると、当該通信ルートを当該子機への通信ルートに決定し、当該子機への通信ルートの探索処理を終了することで、通信ルートの探索時間を短縮することができる。
【００７５】
上述した構成例は、従来構成において説明したＰＬＣネットワークに用いることを想定しているが、他の有線の伝送路を用いる通信ネットワーク、あるいは小電力無線による無線ＬＡＮのように無線の伝送路を用いる無線ネットワークなど、種々のマルチホップ通信ネットワークに上述の技術を適用してもよい。
【００７６】
さらにいえば、ＰＬＣネットワークには、１０〜４５０ｋＨｚの低周波帯を利用する低速ＰＬＣと、２〜３０ＭＨｚの高周波帯を利用する高速ＰＬＣとが知られており、低速ＰＬＣのノードは、高速ＰＬＣより伝送速度が遅いから、上述の構成のように低トラフィックでもネットワークトポロジを把握できることはとくに有効であり、また、通信ネットワーク全体のリンクを各ノードが持たなくとも隣接ノードテーブルがあればよいから、ノードに実装するメモリの容量を小さくすることができる。しかも、他の有線の伝送路を用いる場合に比較すると、ＰＬＣでは各ノードとなる電気機器のオン／オフや稼働状態によってネットワークトポロジや通信品質が変化しやすいから、本発明の技術は有効である。
【図面の簡単な説明】
【００７７】
【図１】（ａ）（ｂ）は実施形態１の通信ルートの構築方法に用いるトポロジーテーブルの説明図、（ｃ）は従来のトポロジーテーブルの説明図である。
【図２】（ａ）〜（ｃ）は同上に用いる他のトポロジーテーブルの説明図である。
【図３】（ａ）は同上を用いる通信ネットワークの概略構成図、（ｂ）はトポロジーテーブルの説明図である。
【図４】同上のルート探索処理を説明するフローチャートである。
【図５】（ａ）〜（ｃ）は同上に用いる演算テーブルの説明図である。
【図６】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図７】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図８】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図９】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１０】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１１】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１２】実施形態２のルート探索処理を説明するフローチャートである。
【図１３】（ａ）〜（ｃ）は同上に用いる演算テーブルの説明図である。
【図１４】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１５】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１６】同上を用いる通信ネットワークのシステム構成図である。
【図１７】同上を用いる通信端末の概略ブロック図である。
【図１８】（ａ）〜（ｄ）は同上に用いるパケットフォーマットの説明図である。
【符号の説明】
【００７８】
１ 通信ネットワーク
２ 通信端末
３ 記憶部
４ ＰＬＣインターフェース部
５ 制御部
５ａ 通信処理部
５ｂ テーブル処理部
５ｃ Ｈパケット送信タイマ部
Ａ 親機
Ｂ１〜Ｂ５ 子機
ＴＢ１ トポロジーテーブル
ＴＢ２ 演算テーブル
【技術分野】
【０００１】
本発明は、マルチホップ通信を用いた通信端末における通信ルートの構築方法およびそれを用いる通信端末に関するものである。
【背景技術】
【０００２】
従来、無線通信網に接続された複数台の通信端末からなる通信ネットワークにおいて、通信端末間で通信信号を中継することで、自端末と直接通信できない端末との通信を行う方法が知られている（いわゆるマルチホップ通信）。
【０００３】
また近年、電力線に接続された複数台の電気機器の間で、電力線を通信線とした電力線搬送通信（以下、ＰＬＣ（Power Line Communication）と略す。）を行う電力線搬送通信ネットワーク（以下、ＰＬＣネットワークと言う。）が普及している。
【０００４】
このようなＰＬＣネットワークを利用し、集合住宅の各住戸に設置された電力量計に電力線搬送通信機能を付加するとともに、電気室にＰＬＣ親機を設置し、ＰＬＣ親機が各住戸の電力量計（ＰＬＣ子機）から検針データを取得して、取得した検針データをネットワークを通じて遠隔の検針サーバに送信するような遠隔検針システムが提案されている。また、集合住宅の電気室などに設置される幹線分岐盤に親機ユニットを設置するとともに、各住戸の住宅分電盤内に子機ユニットを設置して、親機ユニットと子機ユニットの間で分岐幹線を介して電力線搬送通信を行うことで、各住戸の電気使用量を監視、制御するシステムも提案されている。このシステムでは、子機ユニットから親機ユニットへ各住戸の電気使用量を送信させて、親機ユニットで各住戸の電気使用量と集合住宅全体の電気使用量とを同時に監視し、各住戸の電気使用量の合計が共用電気幹線の容量を超えそうな場合には、電気使用量の多い住戸の子機ユニットに親機ユニットが使用制限命令を送信し、子機ユニットが予め設定された家電製品を自動的に停止させて、集合住宅全体の電気使用量を制限するようにしている。ＰＬＣネットワークを利用したこれらのシステムでは、通信端末間の配線長が長く、また通信端末の接続台数も多くなるため、通信可能な距離にある通信端末が通信信号を中継することで、子機と親機との間で通信を行うマルチホップ通信が行われている（例えば、特許文献１を参照）。
【０００５】
ところで、上述した無線の通信ネットワークでは、ネットワーク内で端末が移動するため、ネットワークトポロジーが変化しやすい傾向があり、トポロジーの変化に対応して、各端末間の通信ルートを再構築する必要があった。またＰＬＣネットワークにおいても、電力線を介して通信を行うために、電気機器の発生するノイズの影響により通信不可能な状態になる場合があり、また電気機器からの電源プラグを電源コンセントに抜き差しすることで、電気機器の電力線への接続状態が変化し、通話不可能になる電気機器が発生するため、ネットワークトポロジーが変化しやすいという特徴があり、トポロジーの変化に対応して、各端末間の通信ルートを再構築する必要があった。
【０００６】
そこで、これらの通信ネットワークでは、所定時間が経過する毎に端末間で通信品質レベルの最も良い通信ルートを探索する必要があり、通信ルートを効率的に探索するためにダイクストラアルゴリズムと呼ばれるアルゴリズムが用いられていた（例えば非特許文献１参照）。
【特許文献１】特開２００６−６７５５７号公報
【非特許文献１】西丸泰之、佐藤文明；「ＱｏＳマルチキャスト配送木の構築方式」；情報処理学会研究報告 Vol.2003,No.34；社団法人 情報処理学会；２００３年３月２０日
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述の通信ネットワークでは、親機と各子機との間の通信ルートを構築するために、各通信端末が、自端末の生存を通知する通信パケット（Hello Packet、以下、Ｈパケットと略す。）の送受信を行うことで、直接通信可能な隣接端末を探索した後、探索結果を親機に通知するトポロジー通知メッセージを親機に対して返送しており、親機では受信したトポロジー通知メッセージから、リンクが確立している始点側の通信端末および終点側の通信端末の端末ＩＤと、両端末間の通信品質レベルを示すリンクコストを図１（ｃ）に示すようなトポロジーテーブルＴＢ１’に記録させている。そして、親機ではトポロジーテーブルＴＢ１’に記録されたリンク情報（各子機が直接通信可能な隣接端末に関する情報）をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを構築するようになっている。
【０００８】
ところで、図１（ｃ）に示すトポロジーテーブルＴＢ１’は、例えば始点側の通信端末の端末ＩＤを列、終点側の通信端末の端末ＩＤを行にとった２次元のデータテーブルからなり、始点側の通信端末に対応する列と終点側の通信端末に対応する行とが交差する升目にリンクコストを記録してある。また、升目に「−」が入っている箇所は対応する端末間でリンクが確立していないことを示している。ここで、始点側の通信端末と終点側の通信端末を入れ替えたセルには同じ値が記録されることになるので（ｍ行ｎ列のセルに入るリンクコストとｎ行ｍ列のセルに入るリンクコストは同じ値になるので）、図１（ｃ）に示すトポロジーテーブルＴＢ１’では、対角線を挟んだ一方の領域のみにデータを記録することでテーブルサイズを小さくしているが、リンクが確立していない端末間でもリンクコストを記録させるためのメモリ領域が確保されていた。そのため、メモリ領域が無駄になり、実際に使用するメモリ領域に比べて記憶容量の大きなＲＡＭを用意する必要があり、コスト高になるという問題があった。また、ダイクストラアルゴリズムを用いた通信ルートの探索には時間がかかり、端末の数が増えるほどルート探索に要する時間も長くなるため、通信ルートの探索時間を短縮したいという要求もあった。
【０００９】
本発明は上記問題点に鑑みて為されたものであり、請求項１、７の発明の目的とするところは、トポロジーデータを記録するためのメモリ領域を小さくできる通信ルートの構築方法および通信端末を提供することにある。また、請求項２〜６の発明の目的とするところは、通信ルートの探索に要する時間を短縮しつつ、トポロジーデータを記録するためのメモリ領域を小さくた通信ルートの構築方法を提供することにある。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、請求項１の発明は、通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行うにあたり、親機が各子機から直接通信可能な隣接端末に関するリンク情報を受信し、受信したリンク情報をもとに各子機への通信ルートを構築する通信ルートの構築方法であって、各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信ステップと、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるトポロジー記録ステップと、トポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築ステップとを備えることを特徴とする。
【００１１】
請求項２の発明は、請求項１の発明において、通信ルート構築ステップでダイクストラアルゴリズムを用いて各子機への通信ルートを求める際に、親機から対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、当該子機に至る全ての通信ルートを探索する前に当該子機への通信ルートの探索を終了することを特徴とする。
【００１２】
請求項３の発明は、請求項１又は２の発明において、 始点側の通信端末の端末ＩＤと、終点側の通信端末の端末ＩＤとの大小関係が一定の関係となるようにトポロジーテーブルがソートされた状態で通信ルート構築ステップを実行することを特徴とする。
【００１３】
請求項４の発明は、請求項１乃至３の何れかの発明において、トポロジーテーブルに記憶させた始点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする。
【００１４】
請求項５の発明は、請求項４の発明において、トポロジーテーブルに記憶させた終点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする。
【００１５】
請求項６の発明は、請求項１乃至５の何れかの発明において、トポロジー記録ステップにおいて、始点側または終点側の通信端末の端末ＩＤの少なくとも何れか一方が昇順又は降順に並ぶように、始点側および終点側の通信端末の端末ＩＤとリンクコストとをトポロジーテーブルに記録させることを特徴とする。
【００１６】
請求項７の発明は、通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行う親機側の通信端末であって、各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信手段と、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるテーブル処理手段と、ソートされたトポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築手段とを備えることを特徴とする。
【発明の効果】
【００１７】
請求項１の発明によれば、各子機から受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させているので、始点側の通信端末を列、終点側の通信端末を行にとった二次元のデータテーブルからなるトポロジーテーブルにリンクコストを記録させる場合に比べて、リンクが確立できていない端末間のリンクコストを記録させるメモリ領域が無駄になることがなく、トポロジーデータを記録させるための記憶容量を小さくした通信ルートの構築方法を実現することができる。
【００１８】
請求項２の発明によれば、親機から対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定しているので、親機と子機との間の通信ルートとして所定の通信品質以上の通信ルートを確保でき、また当該子機に至る全ての通信ルートを探索し、その中から通信品質が最も良い通信ルートを選択する場合に比べて短い時間で通信ルートを探索することができる。
【００１９】
請求項３の発明によれば、始点側の通信端末の端末ＩＤと、終点側の通信端末の端末ＩＤとの大小関係が一定の関係となるようにトポロジーテーブルがソートされた状態で通信ルート構築ステップを実行するので、所望の通信端末のリンク情報を検索する際に、まず始点側のみ順番に検索し、始点側が一致した時のみ終点側を検索することで、検索にかかる時間を短縮することができる。
【００２０】
請求項４の発明によれば、始点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築処理を行っているので、所望の通信端末のリンク情報を検索する際に検索にかかる時間を短縮することができる。
【００２１】
請求項５の発明によれば、終点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築処理を行っているので、所望の通信端末のリンク情報を検索する際に検索にかかる時間を短縮することができる。
【００２２】
請求項６の発明によれば、始点側または終点側の通信端末の端末ＩＤの少なくとも何れか一方が昇順又は降順に並ぶように、始点側および終点側の通信端末の端末ＩＤとリンクコストとをトポロジーテーブルに記録させているので、通信ルートを構築する際に端末ＩＤをソートする処理を行う必要がなくなり、通信ルートの探索にかかる時間をさらに短縮することができる。
【００２３】
請求項７の発明によれば、リンク情報受信手段が各子機から受信したリンク情報をもとに、テーブル処理手段が、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させているので、始点側の通信端末を列、終点側の通信端末を行にとった二次元のデータテーブルからなるトポロジーテーブルにリンクコストを記録させる場合に比べて、リンクが確立できていない端末間のリンクコストを記録させるメモリ領域が無駄になることがなく、トポロジーデータを記録させるための記憶容量を小さくできる通信端末を実現することができる。
【発明を実施するための最良の形態】
【００２４】
以下に、本発明に係る通信ルートの構築方法を、電力線搬送通信により通信を行う通信ネットワークに適用した実施形態について図面を参照して説明する。
【００２５】
（実施形態１）
本発明の実施形態１を図面に基づいて説明する。図１６は電力線搬送通信ネットワーク（以下、ＰＬＣネットワークと略す。）１の概略構成図である。このＰＬＣネットワーク１は、例えば集合住宅のような建築物等で用いられ、複数の通信端末２を電力線Ｌに接続することにより構成され、複数台の通信端末２の内の１台を親機Ａ、残りを子機Ｂｎ（ｎ＝１，２，３…）としている。
【００２６】
このＰＬＣネットワーク１では、親機Ａおよび子機Ｂｎが、通信可能な距離にある隣接端末２（親機Ａ又は子機Ｂｎ）との間で所定の通信プロトコル（例えばＳＣＰ、エコーネット等）を用いて電力線搬送通信を行っており、親機Ａが子機Ｂｎから所定の情報を収集するとともに、子機Ｂｎの遠隔監視が行われるものである。ここで、本ネットワーク１では、親機Ａと各子機Ｂｎとの間で直接又は間接に通信が行われ、親機Ａと直接通信できない子機Ｂｎは、通信可能な距離にある他の子機Ｂｎに通信信号を順次中継することで、親機Ａとの通信を行っている。
【００２７】
図１７は本実施形態に用いる通信端末２（親機Ａ又は子機Ｂｎ）のブロック図である。本実施形態では親機Ａと子機Ｂｎとに同一の通信端末２を用いており、例えば何れかの通信端末２で、ジャンパースイッチや切替スイッチなどの設定手段（図示せず）を用いて親機側に設定することで親機Ａとして機能させ、他の通信端末２では設定手段を用いて子機側に設定することで子機Ｂｎとして機能させるようになっている。
【００２８】
通信端末２は、記憶部３と、電力線搬送通信インターフェース部（以下、ＰＬＣインターフェース部と略す）４と、制御部５とを備える。記憶部３は、ＲＯＭなどの不揮発性のメモリや、ＥＥＰＲＯＭなどの書き換え可能な不揮発性のメモリや、ＲＡＭなどの揮発性メモリからなり、通信ルートや通信可能な隣接端末に関するリンク情報などを記憶するテーブル記憶部３ａを備えると共に、この通信端末２を動作させるための制御プログラムなどの各種プログラムや、各プログラムの実行に必要な情報などを記憶する。
【００２９】
テーブル記憶部３ａはテーブル形式のデータを記憶する領域であり、本端末が親機Ａの場合にはテーブル記憶部３ａに、ネットワーク内で構築された端末間の全通信ルートを登録するための通信ルートテーブルや、各端末が直接通信可能な隣接端末の情報（リンク情報）を記録するためのトポロジーテーブルが記憶される。一方、本端末が子機Ｂｎの場合にはテーブル記憶部３ａに、当該子機Ｂｎが通信可能な隣接端末２（親機Ａまたは他の子機Ｂｎ）と、当該子機Ｂｎと隣接端末２（親機Ａまたは他の子機Ｂｎ）との間の通信品質レベルを示す通信コスト値（以下、リンクコストと言う。）と、隣接端末２を経由した当該子機Ｂｎと親機Ａとの間の通信品質レベルを示す通信コスト値（以下、ルートコストと言う。）とを表す通信可能端末テーブルＤを記憶する。
【００３０】
表１は通信可能端末テーブルＤの１例を示し、このデータテーブルＤには、自端末と直接通信が可能な隣接端末２（親機Ａまたは他の子機Ｂｎ）に割り当てた端末ＩＤと、隣接端末２の種別（親機Ａまたは他の子機Ｂｎ）を示す端末種別データと、隣接端末２と自端末との間の通信品質レベルを示すリンクコストと、隣接端末２と親機Ａとの間のルートコストと、隣接端末２から親機Ａまでの通信ルートにおいて自機から１ホップ目、２ホップ目、…、Ｎホップ目の通信端末２を示す端末ＩＤとが対応付けて記憶されている。なお、上記の通信コスト値（リンクコストおよびルートコスト）は、隣接端末から受信した通信信号の受信信号強度を数段階のレベルで表したものであり、値が小さいほど、通信信号の減衰が小さく、通信品質レベルが高いことを示している。また、自端末から親機Ａまでのルートコストは、自端末と隣接端末との間のリンクコストに、隣接端末と親機Ａとの間の上位側ルートコストを加算した値になる。
【００３１】
【表１】
【００３２】
ここで、ＰＬＣネットワーク１では電力線Ｌを通じて通信を行うため、電力線Ｌに接続される他の家電機器から発生するノイズや、他の家電機器が接続されることによる電力線Ｌのインピーダンスの低下等によって、伝送環境が悪化し、通信エラー率が増大する虞がある。またＰＬＣネットワーク１の伝送環境は、家電機器の電源プラグを電源コンセントに抜き差したり、家電機器の可動状態に応じてダイナミックに変化する。そのため、ＰＬＣネットワーク１では、ネットワークトポロジーが固定的ではなく、変化しやすい傾向があり、ネットワークトポロジーが変化しても、親機Ａと子機Ｂｎとの間で通信を良好に行えるように、親機Ａと各子機Ｂｎとの間の通信ルートを定期的に探索し、最適な通信ルートを構築する必要がある。
【００３３】
すなわち通信端末２の制御部５は、例えば、マイクロプロセッサやその周辺回路等で構成され、親機Ａと子機Ｂｎとの間の通信ルートを探索するための処理［すなわち隣接端末を探索する処理や探索結果（リンク情報）を親機に通知する処理や親機側でリンク情報をもとにルートを探索する処理など］を実行するために、通信処理部５ａと、テーブル処理部５ｂと、ハロー・パケット送信タイマ部（以下、Ｈパケット送信タイマ部と略す）５ｃと、リンク通知パケット送信タイマ部５ｄとを備えている。
【００３４】
通信処理部５ａは、ＰＬＣインターフェース部４を用いて他の通信端末２との間で電力線搬送通信により通信信号を送受信し、後述の動作を行うことによって、親機Ａと子機Ｂｎとの間の通信ルートを構築する通信ルート構築処理（ルート探索処理およびルート選択処理からなる）を行う。図１８（ａ）は通信端末２（親機Ａおよび子機Ｂｎ）間で授受される通信パケットの基本フォーマットを示しており、送信元の通信端末２の送信端末ＩＤと、受信側の通信端末２の受信端末ＩＤと、メッセージタイプと、メッセージタイプに応じたデータ（メッセージ依存部）とで構成される。メッセージタイプとしては、自端末の生存や通信ルートを通知するためのハロー・パケット、隣接端末情報を親機に通知するためのリンク通知パケット、通常パケットを送信したときに中継途中で通信エラーが起こった場合に送信するルートエラーパケットなどがある。図１８（ｂ）はハロー・パケット（Ｈパケット）のパケットフォーマットを示し、送信端末ＩＤと、受信端末ＩＤと、メッセージタイプを示すデータ「Ｈｅｌｌｏ」と、送信元の端末タイプ（親機Ａまたは子機Ｂｎの種別）を示すデータと、子機側で求めた自機から親機Ａまでの通信ルートを示すデータとを少なくとも含み、リンクが喪失した端末が存在する場合はそのアドレスを示すリンク喪失端末アドレスを付加して構成される。また図１８（ｃ）はリンク通知パケットのパケットフォーマットを示し、送信端末ＩＤと、受信端末ＩＤと、メッセージタイプを示すデータ「リンク通知」と、子機側で求めた自機から親機Ａまでの通信ルートを示すルート情報と、直接通信可能な隣接端末に関する隣接端末情報とを少なくとも含み、リンクが喪失した端末が存在する場合はそのアドレスを示すリンク喪失端末アドレスを付加して構成される。また図１８（ｄ）はルートエラーパケットのパケットフォーマットを示し、送信端末ＩＤと、受信端末ＩＤと、メッセージタイプを示すデータ「ルートエラー」と、自機から親機Ａまでの通信ルートを示すルート情報と、通信エラーが発生したエラー箇所を示す情報とを含んで構成される。
【００３５】
またテーブル処理部５ｂは、テーブル記憶部３ａに記憶されているデータテーブル（通信ルートテーブル、トポロジーテーブル、通信可能端末テーブルＤなど）を管理する。
【００３６】
Ｈパケット送信タイマ部５ｃは時間を計時する計時手段を有し、所定の送信時間が経過する毎に通信処理部５ａにトリガ信号を与え、通信処理部５ａからＨパケットを送信させる。すなわち、Ｈパケットが所定の送信時間間隔で送信されることになる。
【００３７】
またリンク通知パケット送信タイマ部５ｄも時間を計時する計時手段を有し、所定の送信時間が経過する毎に通信処理部５ａにトリガ信号を与え、通信処理部５ａからリンク通知パケットを送信させる。すなわち、リンク通知パケットが所定の送信時間間隔で送信されることになる。
【００３８】
各通信端末２では、Ｈパケット送信タイマ部５ｃから通信処理部５ａに送信タイミングの到来を示す信号が出力されると、通信処理部５ａがＨパケットを作成し、ブロードキャストで電力線Ｌに送信しており、Ｈパケットを受信可能な隣接端末との間の通信品質レベル（リンクコスト）や、隣接端末の上位ルートに関する情報を取得する。
【００３９】
ここで、図３（ａ）に示す通信ネットワークにおいて通信ルートを構築する処理について以下に説明する。この通信ネットワークは１台の親機Ａと複数台（例えば６台）の子機Ｂ１〜Ｂ６とで構成され、親機Ａの端末ＩＤを１００、子機Ｂ１〜Ｂ６の端末ＩＤをそれぞれ１０１〜１０６に設定してある。また図３（ａ）において実線でつながれた端末同士は直接通信可能な端末を示し、両端末間をつなぐ線の近傍に表示した数字は両端末間のリンクコストを示している。
【００４０】
先ず親機Ａにおいて、Ｈパケット送信タイマ部５ｃから通信処理部５ａに送信タイミングの到来を示す信号が出力されると、通信処理部５ａが上述のＨパケットを作成し、ブロードキャストで電力線Ｌに送信する。この時、親機Ａから送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１００、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが親機となる。
【００４１】
子機Ｂ１，Ｂ２の通信処理部５ａは、親機Ａから送信されたＨパケットを受信することで、親機Ａと直接通信が可能であることが分かり、また上記Ｈパケットの受信信号強度から親機Ａとの間の通信品質レベル（リンクコスト）を算出することができる。そして、各子機Ｂ１，Ｂ２の通信処理部５ａでは、親機ＡからのＨパケットを受信することで、親機と直接通信できることが判明したため、上述のＨパケットを作成し、ブロードキャストで電力線Ｌに送信する。この時、子機Ｂ１から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０１、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、子機の求めた親機へのルートが子機Ｂ１（１０１）→親機Ａ（１００）で、そのルートコストが３となる。子機Ｂ２から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０２、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、子機の求めた親機へのルートが子機Ｂ２（１０２）→親機Ａ（１００）で、そのルートコストが２となる。
【００４２】
子機Ｂ３の通信処理部５ａでは、子機Ｂ１から送信されたＨパケットを受信することにより、子機Ｂ１との間で直接通信が可能であることが分かり、また子機Ｂ１からのＨパケットの受信信号レベルに基づいて子機Ｂ１との間のリンクコスト（＝５）を求める。この時、子機Ｂ３の通信処理部５ａでは、自機と親機とをつなぐ通信ルートとして子機Ｂ１を経由した通信ルートのみを発見でき、この通信ルートのルートコストは各ホップのリンクコストの総和（＝８）になる。なお、子機Ｂ３から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０３、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、親機への通信ルートが子機Ｂ３（１０３）→子機Ｂ１（１０１）→親機Ａ（１００）で、そのルートコストが８となる。
【００４３】
また子機Ｂ４の通信処理部５ａでは、子機Ｂ１，Ｂ２，Ｂ３から送信されたＨパケットを受信することにより、子機Ｂ１，Ｂ２，Ｂ３との間でそれぞれ直接通信が可能であることが分かり、また各子機からのＨパケットの受信信号レベルに基づいて各子機との間のリンクコスト（子機Ｂ１間はリンクコストが２、子機Ｂ２間はリンクコストが４、子機Ｂ３間はリンクコストが５）を求める。この時、子機Ｂ４の通信処理部５ａでは、自機と親機とをつなぐ通信ルートとして子機Ｂ１，Ｂ２，Ｂ３をそれぞれ経由した３つの通信ルートを発見でき、各通信ルートのルートコストは各ホップのリンクコストの総和になるので、子機Ｂ１を経由するルートコストが５、子機Ｂ２を経由するルートコストが６、子機Ｂ３を経由するルートコストが１３であることが分かる。ここで、ルートコストは値が小さいほど通信品質レベルが良好であるので、子機Ｂ１を経由するルートコストが最も小さいことから、子機Ｂ０の通信処理部５ａは、自機と親機Ａとの間の通信ルートとして「子機Ｂ４→子機Ｂ１→親機Ａ」との通信ルートを選択し、選択した通信ルートを通知するためのＨパケットを作成し、ブロードキャストで送信する。なお、子機Ｂ４から送信されるＨパケットは、送信端末ＩＤが自機のＩＤ＝１０４、受信端末ＩＤがブロードキャスト、メッセージタイプが「Ｈｅｌｌｏ」、端末タイプが子機、親機への通信ルートが子機Ｂ４（１０４）→子機Ｂ１（１０１）→親機Ａ（１００）で、そのルートコストが５となる。
【００４４】
他の子機Ｂ５（１０５），Ｂ６（１０６）も他の子機からのＨパケットを受信することで、直接通信可能な隣接端末を検出でき、隣接端末から親機Ａまでの通信ルートおよびその上位側ルートコストと、隣接端末との間のリンクコストをもとに自端末から親機Ａまでの通信ルートおよびそのルートコストを求め、Ｈパケットによりブロードキャスト送信する。
【００４５】
以上のようにして各子機Ｂ１〜Ｂ６では、親機Ａとの間の通信ルートを選択でき、また各子機ＢｎではＨパケットを送受することで、直接通信可能な隣接端末の情報を取得でき、リンク通知パケット送信タイマ部５ｄからトリガ信号が与えられると、隣接端末に関するリンク情報をリンク通知パケットに格納して親機Ａに送信する。
【００４６】
例えば、子機Ｂ４がリンク通知パケットを送信する場合、そのリンク通知パケットは、送信端末ＩＤが自機のＩＤ＝１０４、受信端末ＩＤが子機Ｂ１のＩＤ＝１０１、メッセージタイプが「リンク通知」、親機へのルートが子機Ｂ４（１０４）→子機Ｂ１（１０１）→親機Ａ（１００）でそのルートコストが５、隣接端末情報が子機Ｂ１（ＩＤ＝１０１、リンクコスト２）、子機Ｂ２（ＩＤ＝１０２、リンクコスト４）、子機Ｂ３（ＩＤ＝１０３、リンクコスト５）となる。このリンク通知パケットを受信した子機Ｂ１の通信処理部５ａでは、リンク通知パケットに含まれるルート情報を参照することにより、親機Ａに中継すれば良いことが分かるので、子機Ｂ４から受信したリンク通知パケットをもとに、親機Ａへ送信するリンク通知パケットを作成し、親機Ａに送信する。ここで、子機Ｂ１が送信するリンク通知パケットは、送信端末ＩＤが自機のＩＤ＝１０１、受信端末ＩＤが親機のＩＤ＝１００、メッセージタイプが「リンク通知」、親機へのルートが子機Ｂ４（１０４）→子機Ｂ１（１０１）→親機Ａ（１００）でそのルートコストが５、隣接端末情報が子機Ｂ１（ＩＤ＝１０１、リンクコスト２）、子機Ｂ２（ＩＤ＝１０２、リンクコスト４）、子機Ｂ３（ＩＤ＝１０３、リンクコスト５）となる。このリンク通知パケットを親機Ａが受信すると、リンク通知パケットに含まれる親機へのルート情報から送信元が子機Ｂ４（ＩＤ＝１０４）であることが分かるので、子機Ｂ４間の通信ルートに関する情報を取得するとともに、上記パケットに含まれる隣接端末情報をもとに、図３（ｂ）に示すようなトポロジーテーブルＴＢ１を作成する。このリンク通知パケットは各子機Ｂｎから一定の時間間隔で送信されるので、親機Ａでは各子機Ｂｎからのリンク通知パケットを受信することで、各子機Ｂｎとの間の通信ルートや、各子機Ｂｎの隣接端末情報を取得することができる。
【００４７】
而して、親機Ａの通信処理部５ａ（リンク情報受信手段）では、各子機Ｂｎからのリンク通知パケットを受信することで、各子機Ｂｎが直接通信可能な隣接端末の情報を取得することができ（リンク情報受信ステップ）、テーブル処理部５ｂを用いて、各子機Ｂｎの隣接端末に関するリンク情報をトポロジーテーブルＴＢ１に記憶させる。なお、リンク通知パケットに含まれる通信ルートのデータは、各子機が、Ｈパケットを送受できる範囲で求めた通信ルートであり、しかも１つのルートのデータしか含まれていなので、トポロジーの変化などによって通信ルートが不通となっている可能性もあり、親機Ａでは、トポロジーテーブルＴＢ１に記録されたリンク情報をもとに後述する探索処理を行って、各子機Ｂｎへの通信ルートを探索するようにしている。
【００４８】
ここで、従来の通信ネットワークでは、親機Ａが子機Ｂｎから送信されたトポロジー通知メッセージに基づいて、このメッセージに格納されたリンク情報（始点側および終点側の通信端末２の端末ＩＤとリンクコストからなる）を図１（ｃ）に示すトポロジーテーブルＴＢ１’に記録させていた。このトポロジーテーブルＴＢ１’は、始点側の通信端末を列、終点側の通信端末を行にとった二次元のデータテーブルで構成されているため、通信端末の個数をｎ個とすると、リンクコストを記録させるメモリ領域が［（ｎ−１）！］個用意されることになり、双方向リンクが確立できていない端末間のリンクコストを記録させるためのメモリ領域が無駄になるという問題があった。
【００４９】
そこで、本実施形態では親機Ａのテーブル処理部５ｂ（テーブル処理手段）が、子機Ｂｎからのトポロジー通知メッセージに格納されて送信されてきたリンク情報を、図１（ａ）に示すようなトポロジーテーブルＴＢ１に格納している（トポロジー記録ステップ）。尚、図１，図２では図示を簡単にするため始点ノードおよび終点ノードを１桁の数字で示している。
【００５０】
本実施形態で用いるトポロジーテーブルＴＢ１は、始点側の通信端末（始点ノード）の端末ＩＤ、終点側の通信端末（終点ノード）の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元に記録したテーブルからなり、リンク情報が通知された分のメモリ領域しか必要とせず、図１（ｃ）に示すトポロジーテーブルＴＢ１’のように予め所定個数のメモリ領域を確保する場合に比べてメモリ領域を小さくでき、無駄になるメモリ領域が発生しないので、メモリ領域を有効に活用することができ、記憶容量が必要以上に大きいメモリを用意する必要がないので、通信端末のコストが増大するのを防止できるという利点がある。
【００５１】
なお親機Ａの通信処理部５ａでは、トポロジーテーブルＴＢ１に記録されたリンク情報をもとに、各子機Ｂｎへの通信ルートを探索する後述のルート探索処理を実行するのであるが、リンク情報の検索を容易にするために、図１（ｂ）に示すように始点ノードの端末ＩＤと、終点ノードの端末ＩＤとの大小関係が一定の関係（例えば、（始点ノードの端末ＩＤ）＜（終点ノードの端末ＩＤ））となるようにトポロジーテーブルＴＢ１に記録させることが好ましい。ここで、検索対象の端末と通信可能なリンク（端末）を検索する際に、始点ノードの端末ＩＤと終点ノードの端末ＩＤとの大小関係に一定の関係付けが行われていない場合は、トポロジーテーブルＴＢ１に記録されている全てのリンク情報の始点側のＩＤと終点側のＩＤを両方共に検索しなければならないが、（始点ノードの端末ＩＤ）＜（終点ノードの端末ＩＤ）となるようにトポロジーテーブルＴＢ１に記録させておけば、始点側或いは終点側の片方だけを検索すれば良く、通信ルートの計算にかかる時間を短縮できるという利点がある。
【００５２】
また、図２（ａ）に示すトポロジーテーブルＴＢ１のように始点ノードの端末ＩＤあるいは終点ノードの端末ＩＤが昇順または降順にソートされていない場合は、所望の端末のリンク情報を検索するのに、先頭レコードから順番に検索しなければならないため時間を要するが、図２（ｂ）に示すように始点ノードの端末ＩＤを昇順にソートすることで、所望の端末のリンク情報を検索するのに２分探索などの探索アルゴリズムを利用できるから、端末の検索処理を効率よく行うことができる。また、図２（ｃ）に示すように始点ノードの端末ＩＤを第１キーとして昇順にソートした後に、終点ノードの端末ＩＤを第２キーとして昇順にソートすることで、所望の端末のリンク情報を検索する処理をさらに効率よく行うことができる。尚、図２（ｂ）（ｃ）に示すトポロジーテーブルＴＢ１では、始点ノードまたは終点ノードを昇順にソートしているが、降順にソートしても良く、所望の端末のリンク情報を検索する処理を効率よく行うことができる。また、図２（ｂ）に示すトポロジーテーブルＴＢ１では、始点ノードの端末ＩＤを昇順にソートしているが、終点ノードの端末ＩＤを昇順にソートしても良いし、終点ノードの端末ＩＤを第１キーとして昇順にソートした後、始点ノードの端末ＩＤを第２キーとして昇順にソートしても良い。また、親機Ａの通信処理部５ａが、テーブル処理部５ｂを用いて始点ノードおよび終点ノードの端末ＩＤとリンクコストとをトポロジーテーブルＴＢ１に記録させる際に、端末ＩＤが昇順又は降順に並ぶようソートしてからトポロジーテーブルＴＢ１に記録させておけば、所望の端末のリンク情報を検索する際に短時間で検索を行えるが、トポロジー通知メッセージを受信した順番にリンク情報をトポロジーテーブルＴＢ１に記録させておき、所望の端末のリンク情報を検索する際に、端末ＩＤが昇順または降順に並ぶようにソートしてから、検索を行うようにしても良い。
【００５３】
以上のようにして、親機Ａが、ネットワークを構成する子機Ｂｎからトポロジー通知メッセージを受信し、記憶部３内のトポロジーテーブルＴＢ１にリンク情報を記録させると、親機Ａの通信処理部５ａ（通信ルート構築手段）が、トポロジーテーブルＴＢ１に記録させたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求めるルート探索処理を行う（通信ルート構築ステップ）。
【００５４】
ここで、親機Ａによるルート探索処理について図３〜図１１を参照して説明する。なお、各端末で隣接端末の探索処理を行い、リンク情報をリンク通知パケットに格納して親機Ａ（１００）に送信することで、親機ＡのトポロジーテーブルＴＢ１には各端末のリンク情報が記録されているものとする（図３（ｂ）参照）。また図５（ａ）は親機Ａのテーブル記憶部３ａに用意された通信ルートの演算テーブルＴＢ２を示している。演算テーブルＴＢ２は通信ルートを探索する過程で使用されるテーブルであり、この演算テーブルＴＢ２には、各端末の端末ＩＤ１００〜１０６に対して、前ホップの端末ＩＤと、ルート構築端末に設定されたか否かを示すフラグＶｉｓｉｔと、親機Ａからのホップ数ＨＯＰと、親機Ａからのルートコストとを記録するようになっている。
【００５５】
図４は親機Ａによるルート探索処理のフローチャートであり、先ず親機Ａの通信処理部５ａは、自機（端末ＩＤ＝１００）をルート構築端末に決定するとともに（Ｓ１）、ルート構築端末を検索対象に決定し、図５（ｂ）に示すように自機（端末ＩＤ＝１００）のフラグＶｉｓｉｔをＴＲＵＥ（○）にする（Ｓ２）。そして、親機Ａの通信処理部５ａは、始点ノードを検索対象の端末ＩＤ（＝１００）に指定するとともに、終点ノードの端末ＩＤを１０１、１０２、１０３、…、１０６に順番に指定し、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。ここで、検索対象の端末と通信可能なリンクをトポロジーテーブルＴＢの先頭から順番に検索していくと、特にトポロジー数が多い場合には検索に非常に長い時間を要するので、始点ノードおよび終点ノードを指定して検索するが、上述のようにトポロジーテーブルＴＢ１は始点ノード或いは終点ノードの端末ＩＤが昇順又は降順にソートされているので、先ず始点ノードを２分探索を用いて検索した後、抽出されたリンクから終点ノードが一致するリンクを検索することで、検索に要する時間をかなり短縮することができる。
【００５６】
そして、Ｓ３においてトポロジーテーブルＴＢ１に該当リンクを発見できれば該当リンクのルートコストＲＣ１と、演算テーブルＴＢ２に記録されているルートコストＲＣとの大小を比較し（Ｓ４）、今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣよりも小さければ（ＲＣ＞ＲＣ１）、演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰを書き込んだ後（Ｓ５）、Ｓ２に戻って処理を続行する。一方、Ｓ４において今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣ以上であれば（ＲＣ≦ＲＣ１）、通信処理部５ａは演算テーブルＴＢ２へのルートコストの書き込み処理は行わず、Ｓ２に戻って処理を続行する。なお演算テーブルＴＢ２にルートコストが記録されていない場合は、今回発見したルートコストＲＣ１を演算テーブルＴＢ２に書き込むものとする。ここで、検索対象の端末が親機（端末ＩＤ＝１００）の場合は、端末ＩＤが１０１，１０２の端末とリンクがつながっており、両端末間のホップ数ＨＯＰ（＝１）と前ホップの端末ＩＤとルートコストＲＣ［端末（１０１）が３，端末（１０２）が２］が演算テーブルＴＢ２に記録される（図５（ｃ）参照）。
【００５７】
検索対象の端末について通信可能なリンクを全て検索し終えると、親機Ａの通信処理部５ａは、演算テーブルＴＢ２から、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（Ｖｉｓｉｔの欄に○がついていない端末）が存在するかを検索し（Ｓ６）、存在する場合はフラグＶｉｓｉｔがＦＡＬＳＥとなっている端末の中でルートコストが最小の端末を検索対象に決定するとともに、この端末のフラグＶｉｓｉｔをＴＲＵＥ（○）として（Ｓ７）、Ｓ３に戻り、上述の処理を繰り返す。
【００５８】
ここで、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０１〜１０６）の中でルートコストが最小の端末は、端末ＩＤが１０２の端末（以下、端末（１０２）と表す）なので、通信処理部５ａは、この端末を検索対象に設定し、図６（ａ）に示すように端末（１０２）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０２）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０１、１０３、１０４、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。そして、トポロジーテーブルＴＢ１に該当リンクを発見できれば、今回発見した該当リンク（端末ＩＤが１０４，１０５，１０６の端末）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きする（図６（ｂ）参照）。なお、ルートコストは自機と親機との間の通信コスト値であるので、ルートコストは各ホップのリンクコストの合計値となる。例えば端末（１０４）では、端末（１００）と端末（１０２）の間のリンクコスト（＝２）と、端末（１０２）と端末（１０４）の間のリンクコスト（＝４）との合計値（＝６）となる。
【００５９】
端末（１０２）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０１、１０４〜１０６）の中でルートコストが最小の端末（１０１）を検索対象に設定し、図７（ａ）に示すように端末（１０１）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０１）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０３、１０４、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。そして、トポロジーテーブルＴＢ１に該当リンクを発見できれば、今回発見した該当リンク（端末ＩＤが１０３〜１０５の端末）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きする（図７（ｂ）参照）。ここで、端末（１０３）は、演算テーブルＴＢ２にデータが記録されていなかったので、今回発見したリンクのルートコストと前ホップの端末ＩＤとホップ数とを演算テーブルに記録する。また、端末（１０４）は、今回発見したリンク（前ホップの端末ＩＤが１０１）のルートコストＲＣ１（＝５）の方が、演算テーブルＴＢ２に記憶されているルートコストＲＣ（＝６）よりも小さいので、今回発見したリンクのルートコストと前ホップの端末ＩＤとホップ数とを演算テーブルに記録する。一方、端末端末（１０５）のルートコストは、今回発見したリンク（前ホップの端末ＩＤが１０１）のルートコストＲＣ１の方が、演算テーブルＴＢ２に記憶されているルートコストＲＣ以上となるので、演算テーブルＴＢ２のデータはそのままとする。
【００６０】
次に、端末（１０１）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０３〜１０６）の中でルートコストが最小の端末（１０４）を検索対象に設定し、図８（ａ）に示すように端末（１０４）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０４）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０３、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。この場合、トポロジーテーブルＴＢ１には該当するリンクが発見できないので、演算テーブルＴＢ２のデータはそのままとする（図８（ｂ）参照）。
【００６１】
端末（１０４）ついて、通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０３，１０５，１０６）の中でルートコストが最小の端末（１０６）を検索対象に設定し、図９（ａ）に示すように端末（１０６）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０６）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０３、１０５に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。そして、トポロジーテーブルＴＢ１に該当リンクが発見できれば、今回発見した該当リンク（端末（１０５））のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較する。この場合、端末（１０５）のルートコストは、今回発見したリンク（前ホップの端末ＩＤが１０６）のルートコストＲＣ１の方が、演算テーブルＴＢ２に記憶されているルートコストＲＣ以上となるので、演算テーブルＴＢ２のデータはそのままとする（図９（ｂ）参照）。
【００６２】
端末（１０６）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０３）、（１０５）の中でルートコストが最小の端末（１０３）を検索対象に設定し（この場合はルートコストが同じ値となっているので端末ＩＤの小さい方に決定）、図１０（ａ）に示すように端末（１０３）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０３）に指定するとともに、終点ノードの端末ＩＤをフラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末の端末ＩＤ１０５に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ３）。この場合、トポロジーテーブルＴＢ１には該当するリンクが発見できないので、演算テーブルＴＢ２のデータはそのままとする（図１０（ｂ）参照）。
【００６３】
端末（１０３）について通信可能な端末の検出が全て終了すると、通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０５）を検索対象に設定し、図１１（ａ）に示すように端末（１０５）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０５）に指定するが、フラグＶｉｓｉｔがＴＲＵＥ（○）となっていない端末が存在しないので終点ノードの指定が行えず、該当リンクの検索処理は行わないまま、処理を終了するので、演算テーブルＴＢ２のデータはそのままとなる（図１１（ｂ）参照）。そして、端末（１０５）について処理を終えると、全ての端末のフラグＶｉｓｉｔがＴＲＵＥとなるので、通信処理部５ａは、全ての端末の通信ルートが設定できたと判断し、テーブル処理部５ｂを用いて演算テーブルＴＢ２の情報を記憶部３の通信ルートテーブルに反映させて（Ｓ８）、ルート探索処理を終了し、以後は通信ルートテーブルに記録された通信ルートを用いて親機Ａと各子機Ｂｎとの間で通信信号が授受されるのである。
【００６４】
（実施形態２）
本発明の実施形態２を図１２〜図１５に基づいて説明する。本実施形態では、実施形態１で説明した通信ネットワークにおいて、通信ルート構築ステップで親機Ａが各子機への通信ルートを求める際に、親機Ａから対象の子機に至る通信ルートとして、所定の通信品質以上（すなわちルートコストＲＣが所定の閾値以下）の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、探索対象の子機に至る全ての通信ルートを探索する前に当該子機への通信ルートの探索を終了するようにしている。例えば本実施形態ではルートコストの閾値を、１ホップ目であれば５、２ホップ目であれば１０、３ホップ目であれば１５に設定している。尚、ルート探索処理以外は実施形態１で説明した通信ネットワークと同様であるので、同一の構成要素には同一の符号を付して、その説明は省略する。
【００６５】
親機Ａによるルート探索処理を図１２のフローチャートに基づいて説明する。ところで、図１３（ａ）は親機Ａの通信処理部５ａがルート探索処理を行う際に用いる演算テーブルＴＢ２を示し、実施形態１で説明した演算テーブルＴＢ２において通信ルートが決定されたか未決定かを示すルート決定フラグを追加してある。
【００６６】
親機Ａの通信処理部５ａがルート探索処理を開始すると、先ず自機（端末ＩＤ＝１００）をルート構築端末に決定するとともに（Ｓ１０）、ルート構築端末を検索対象に決定し、図１３（ｂ）に示すように自機（端末ＩＤ＝１００）のフラグＶｉｓｉｔをＴＲＵＥ（○）、ルート決定フラグを「決定」にするとともに、他の端末のルート決定フラグを「未決定」にする（Ｓ１１）。そして、親機Ａの通信処理部５ａは、始点ノードを検索対象の端末ＩＤ（＝１００）に指定するとともに、終点ノードの端末ＩＤを１０１、１０２、１０３、…、１０６に順番に指定し、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ１２）。ここで、検索対象の端末と通信可能なリンクをトポロジーテーブルＴＢの先頭から順番に検索していくと、特にトポロジー数が多い場合には検索に非常に長い時間を要するので、始点ノードおよび終点ノードを指定して検索するが、実施形態１で説明したようにトポロジーテーブルＴＢ１は始点ノード或いは終点ノードの端末ＩＤが昇順又は降順にソートされているので、先ず始点ノードを２分探索を用いて検索した後、抽出されたリンクから終点ノードが一致するリンクを検索することで、検索に要する時間をかなり短縮することができる。
【００６７】
そして、Ｓ１２においてトポロジーテーブルＴＢ１に該当リンクを発見できれば該当リンクのルートコストＲＣ１と、演算テーブルＴＢ２に記録されているルートコストＲＣとの大小を比較し（Ｓ１３）、今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣよりも小さければ（ＲＣ＞ＲＣ１）、演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰを書き込む（Ｓ１４）。一方、Ｓ１３において、今回発見したルートコストＲＣ１が演算テーブルＴＢ２に記録されているルートコストＲＣ以上であれば（ＲＣ≦ＲＣ１）、通信処理部５ａは演算テーブルＴＢ２へのルートコストの書き込みは行わず、Ｓ１２に戻って処理を継続する。なお演算テーブルＴＢ２にルートコストが記録されていない場合は、今回発見したルートコストＲＣ１を演算テーブルＴＢ２に書き込むものとする。また、Ｓ１４で演算テーブルへの書き込みを終えると、通信処理部５ａはルートコストが閾値以下であるか否かを判定し（Ｓ１５）、閾値以下であれば当該子機への通信ルートを決定し、ルート決定フラグを「決定」とした後（Ｓ１６）、Ｓ１２に戻って処理を継続する。また、Ｓ１５においてルートコストが閾値よりも大きければ、通信処理部５ａは、ルート決定フラグを「未決定」のままとし、Ｓ１２に戻って処理を継続する。
【００６８】
ここで、検索対象の端末が親機（端末ＩＤ＝１００）の場合は、端末ＩＤが１０１，１０２の端末（１０１）および端末（１０２）とリンクがつながっているので、通信処理部５ａは、両端末間のホップ数ＨＯＰ（＝１）と前ホップの端末ＩＤとルートコスト［端末（１０１）が３，端末（１０２）が２］を演算テーブルＴＢ２に記録するとともに（図１３（ｂ）参照）、各端末のルートコストが１ホップ目の閾値（＝５）以下となっていることから、各端末（１０１），（１０２）のルート決定フラグを「決定」とする（図１３（ｃ）参照）。
【００６９】
検索対象の端末について通信可能なリンクを全て検索し終えると、親機Ａの通信処理部５ａは、演算テーブルＴＢ２から、ルート決定フラグが「未決定」となっている端末が存在するかを検索し（Ｓ１７）、存在する場合はフラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（Ｖｉｓｉｔの欄に○がついていない端末）が存在するかを検索し（Ｓ１８）、存在する場合はフラグＶｉｓｉｔがＦＡＬＳＥとなっている端末の中でルートコストが最小の端末を検索対象に決定するとともに、この端末のフラグＶｉｓｉｔをＴＲＵＥ（○）として（Ｓ１９）、Ｓ１２に戻り、上述の処理を繰り返す。一方、Ｓ１７でルート決定フラグが「未決定」の端末が存在しなかったり、フラグＶｉｓｉｔがＦＡＬＳＥの端末が存在しなかった場合、親機Ａの通信処理部５ａはルート探索処理が完了したと判断し、演算テーブルＴＢ２の情報を通信ルートテーブルに反映させる（Ｓ２０）。
【００７０】
ここで、親機Ａの通信処理部５ａが、親機１００と通信可能なリンクの検索を全て終了した時点では、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末（１０１〜１０６）の中でルートコストが最小の端末は、端末ＩＤが１０２の端末なので、通信処理部５ａは、この端末（１０２）を検索対象に設定し、図１４（ａ）に示すように端末（１０２）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０２）に指定するとともに、終点ノードを「ルート決定フラグ」が「未決定」となっている端末の端末ＩＤ１０３、１０４、１０５、１０６に順番に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ１２）。そして、トポロジーテーブルＴＢ１に該当リンクが発見できれば、今回発見した該当リンク（端末ＩＤが１０４，１０５，１０６の端末）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤ（＝１０２）とルートコストＲＣとホップ数ＨＯＰ（＝２）を上書きした後、ルートコストを２ホップ目の閾値（＝１０）と比較し、何れのルートコストも閾値以下となっているので、ルート決定フラグを「決定」とする（図１４（ｂ）参照）。
【００７１】
端末（１０２）について通信可能な端末の検出が全て終了すると、親機Ａの通信処理部５ａは、演算テーブルＴＢ２から、ルート決定フラグが「未決定」となっている端末が存在するかを検索する。ここで、端末ＩＤが１０３の端末（１０３）はルート決定フラグが未決定となっているので、親機Ａの通信処理部５ａは、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末を検索し、フラグＶｉｓｉｔがＦＡＬＳＥとなっている端末の中でルートコストが最小の端末（端末ＩＤが１０１の端末）を検索対象に設定し、図１５（ａ）に示すように端末（１０１）のフラグＶｉｓｉｔをＴＲＵＥ（○）に設定した後、始点ノードを検索対象の端末ＩＤ（＝１０１）に指定するとともに、終点ノードを「ルート決定フラグ」が「未決定」となっている端末の端末ＩＤ１０３に指定して、対応するリンクがトポロジーテーブルＴＢ１に存在するか否かを検索する（Ｓ１２）。そして、トポロジーテーブルＴＢ１に該当リンクが発見できれば、端末（１０３）のルートコストＲＣ１と演算テーブルＴＢ２に記録されている当該端末のルートコストＲＣを比較し、ＲＣ＞ＲＣ１であれば演算テーブルＴＢ２に前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きする。ここで、端末（１０３）はルートコストが未定であったので、親機Ａの通信処理部５ａは、端末（１０３）について前ホップの端末ＩＤとルートコストとホップ数ＨＯＰ（＝２）を上書きした後、ルートコストを２ホップ目の閾値（＝１０）と比較し、何れのルートコストも閾値以下となっているので、ルート決定フラグを「決定」とする（図１５（ｂ）参照）。
【００７２】
端末（１０１）について通信可能な端末の検出が全て終了すると、全ての端末のルート決定フラグが「決定」となるので、親機Ａの通信処理部５ａは、全ての端末の通信ルートが設定できたと判断し、テーブル処理部５ｂを用いて演算テーブルＴＢ２の情報を記憶部３の通信ルートテーブルに反映させて、ルート探索処理を終了し（Ｓ２０）、以後は通信ルートテーブルに記録された通信ルートを用いて親機Ａと各子機Ｂｎとの間で通信信号が授受されるのである。
【００７３】
以上説明したように本実施形態では、親機Ａの通信処理部５ａがルート探索処理を行う際に、親機Ａから対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルート（つまりルートコストが所定の閾値以下の通信ルート）が探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、当該子機への通信ルートの探索処理を終了しているので、親機Ａと子機Ｂｎとの間の通信ルートとして所定の通信品質以上の通信ルートを確保でき、また当該子機に至る全ての通信ルートを探索し、その中から通信品質が最も良い通信ルートを選択する場合に比べて短い時間で通信ルートを探索することができる。
【００７４】
なお本実施形態では、実施形態１で説明したトポロジーテーブルＴＢ１を用いて通信ルートの探索処理を行っているが、従来のトポロジーテーブルＴＢ１’を用いて本実施形態のようなルート探索処理を行った場合でも、親機Ａから対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルート（つまりルートコストが所定の閾値以下の通信ルート）が探索できると、当該通信ルートを当該子機への通信ルートに決定し、当該子機への通信ルートの探索処理を終了することで、通信ルートの探索時間を短縮することができる。
【００７５】
上述した構成例は、従来構成において説明したＰＬＣネットワークに用いることを想定しているが、他の有線の伝送路を用いる通信ネットワーク、あるいは小電力無線による無線ＬＡＮのように無線の伝送路を用いる無線ネットワークなど、種々のマルチホップ通信ネットワークに上述の技術を適用してもよい。
【００７６】
さらにいえば、ＰＬＣネットワークには、１０〜４５０ｋＨｚの低周波帯を利用する低速ＰＬＣと、２〜３０ＭＨｚの高周波帯を利用する高速ＰＬＣとが知られており、低速ＰＬＣのノードは、高速ＰＬＣより伝送速度が遅いから、上述の構成のように低トラフィックでもネットワークトポロジを把握できることはとくに有効であり、また、通信ネットワーク全体のリンクを各ノードが持たなくとも隣接ノードテーブルがあればよいから、ノードに実装するメモリの容量を小さくすることができる。しかも、他の有線の伝送路を用いる場合に比較すると、ＰＬＣでは各ノードとなる電気機器のオン／オフや稼働状態によってネットワークトポロジや通信品質が変化しやすいから、本発明の技術は有効である。
【図面の簡単な説明】
【００７７】
【図１】（ａ）（ｂ）は実施形態１の通信ルートの構築方法に用いるトポロジーテーブルの説明図、（ｃ）は従来のトポロジーテーブルの説明図である。
【図２】（ａ）〜（ｃ）は同上に用いる他のトポロジーテーブルの説明図である。
【図３】（ａ）は同上を用いる通信ネットワークの概略構成図、（ｂ）はトポロジーテーブルの説明図である。
【図４】同上のルート探索処理を説明するフローチャートである。
【図５】（ａ）〜（ｃ）は同上に用いる演算テーブルの説明図である。
【図６】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図７】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図８】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図９】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１０】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１１】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１２】実施形態２のルート探索処理を説明するフローチャートである。
【図１３】（ａ）〜（ｃ）は同上に用いる演算テーブルの説明図である。
【図１４】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１５】（ａ）（ｂ）は同上に用いる演算テーブルの説明図である。
【図１６】同上を用いる通信ネットワークのシステム構成図である。
【図１７】同上を用いる通信端末の概略ブロック図である。
【図１８】（ａ）〜（ｄ）は同上に用いるパケットフォーマットの説明図である。
【符号の説明】
【００７８】
１ 通信ネットワーク
２ 通信端末
３ 記憶部
４ ＰＬＣインターフェース部
５ 制御部
５ａ 通信処理部
５ｂ テーブル処理部
５ｃ Ｈパケット送信タイマ部
Ａ 親機
Ｂ１〜Ｂ５ 子機
ＴＢ１ トポロジーテーブル
ＴＢ２ 演算テーブル
【特許請求の範囲】
【請求項１】
通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行うにあたり、親機が各子機から直接通信可能な隣接端末に関するリンク情報を受信し、受信したリンク情報をもとに各子機への通信ルートを構築する通信ルートの構築方法であって、
各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信ステップと、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるトポロジー記録ステップと、トポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築ステップとを備えることを特徴とする通信ルートの構築方法。
【請求項２】
前記通信ルート構築ステップでダイクストラアルゴリズムを用いて各子機への通信ルートを求める際に、親機から対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、当該子機に至る全ての通信ルートを探索する前に当該子機への通信ルートの探索を終了することを特徴とする請求項１記載の通信ルートの構築方法。
【請求項３】
始点側の通信端末の端末ＩＤと、終点側の通信端末の端末ＩＤとの大小関係が一定の関係となるようにトポロジーテーブルがソートされた状態で通信ルート構築ステップを実行することを特徴とする請求項１又は２記載の通信ルートの構築方法。
【請求項４】
トポロジーテーブルに記憶させた始点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする請求項１乃至３の何れか１項に記載の通信ルートの構築方法。
【請求項５】
トポロジーテーブルに記憶させた終点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする請求項４記載の通信ルートの構築方法。
【請求項６】
トポロジー記録ステップにおいて、始点側または終点側の通信端末の端末ＩＤの少なくとも何れか一方が昇順又は降順に並ぶように、始点側および終点側の通信端末の端末ＩＤとリンクコストとをトポロジーテーブルに記録させることを特徴とする請求項１乃至５の何れか１項に記載の通信ルートの構築方法。
【請求項７】
通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行う親機側の通信端末であって、
各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信手段と、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるテーブル処理手段と、ソートされたトポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築手段とを備えることを特徴とする通信端末。
【請求項１】
通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行うにあたり、親機が各子機から直接通信可能な隣接端末に関するリンク情報を受信し、受信したリンク情報をもとに各子機への通信ルートを構築する通信ルートの構築方法であって、
各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信ステップと、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるトポロジー記録ステップと、トポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築ステップとを備えることを特徴とする通信ルートの構築方法。
【請求項２】
前記通信ルート構築ステップでダイクストラアルゴリズムを用いて各子機への通信ルートを求める際に、親機から対象の子機に至る通信ルートとして、所定の通信品質以上の通信ルートが探索できた場合は、当該通信ルートを当該子機への通信ルートに決定し、当該子機に至る全ての通信ルートを探索する前に当該子機への通信ルートの探索を終了することを特徴とする請求項１記載の通信ルートの構築方法。
【請求項３】
始点側の通信端末の端末ＩＤと、終点側の通信端末の端末ＩＤとの大小関係が一定の関係となるようにトポロジーテーブルがソートされた状態で通信ルート構築ステップを実行することを特徴とする請求項１又は２記載の通信ルートの構築方法。
【請求項４】
トポロジーテーブルに記憶させた始点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする請求項１乃至３の何れか１項に記載の通信ルートの構築方法。
【請求項５】
トポロジーテーブルに記憶させた終点側の通信端末の端末ＩＤが昇順又は降順に並ぶようにソートされた状態で通信ルート構築ステップを実行することを特徴とする請求項４記載の通信ルートの構築方法。
【請求項６】
トポロジー記録ステップにおいて、始点側または終点側の通信端末の端末ＩＤの少なくとも何れか一方が昇順又は降順に並ぶように、始点側および終点側の通信端末の端末ＩＤとリンクコストとをトポロジーテーブルに記録させることを特徴とする請求項１乃至５の何れか１項に記載の通信ルートの構築方法。
【請求項７】
通信ネットワークを構成する複数の通信端末の内の１台を親機、残りを子機とし、親機が、当該親機と各子機との間の通信ルートを記憶した記憶部から、所望の子機への通信ルートを読み出し、当該通信ルートにしたがって隣接端末間で通信信号を授受することにより、親機と子機との間で通信を行う親機側の通信端末であって、
各子機から、当該子機が直接通信可能な隣接端末に関するリンク情報を受信するリンク情報受信手段と、受信したリンク情報をもとに、始点側の通信端末の端末ＩＤ、終点側の通信端末の端末ＩＤ、および、両端末間の通信品質レベルを示すリンクコストを一次元のデータテーブルからなるトポロジーテーブルに記録させるテーブル処理手段と、ソートされたトポロジーテーブルに記録されたリンク情報をもとに、ダイクストラアルゴリズムを用いて各子機への通信ルートを求める通信ルート構築手段とを備えることを特徴とする通信端末。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００８−３０１２６９（Ｐ２００８−３０１２６９Ａ）
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願番号】特願２００７−１４６０１３（Ｐ２００７−１４６０１３）
【出願日】平成１９年５月３１日（２００７．５．３１）
【出願人】（０００００５８３２）パナソニック電工株式会社 (17,916)
【Ｆターム（参考）】
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願日】平成１９年５月３１日（２００７．５．３１）
【出願人】（０００００５８３２）パナソニック電工株式会社 (17,916)
【Ｆターム（参考）】
[ Back to top ]