JP6784707B2 - 無線通信装置、無線通信方法、コンピュータプログラム及び無線マルチホップネットワーク - Google Patents

Description

本発明の実施形態は、無線通信装置、無線通信方法、コンピュータプログラム及び無線マルチホップネットワークに関する。

複数のノードをメッシュ状に接続した無線マルチホップネットワーク（メッシュネットワーク）は、通信線が不要である。この利点を活かし、広範囲を監視するセンサネットワーク等を容易に設置できる。また、メンテナンス性に優れている。このため、無線マルチホップネットワークは、広範囲の監視に有用である。無線マルチホップネットワークにおいて、時分割通信を適用し、ノードの通信に無関係な時間帯では、ノードをスリープさせる仕組みが知られている。これにより、エネルギー資源の節約（省電力化）を図る。

このような無線メッシュネットワークにおいては、親ノードの候補が複数存在する場合、親ノードを選択する処理が必要である。親ノードを選択する方法としては、ＥＴＸ（Expected Transmission）と呼ばれる方式が良く知られている。ＥＴＸ方式では、根ノードまでのホップ数が少なく、かつ通信成功率が大きくなる経路の親ノードを選択できる。

しかしＥＴＸ方式では、経路上の一部のノードにデータが集中することで輻輳が発生する問題がある。輻輳が発生すると、中継が出来なかったり、受信したデータを中継のために記憶することができず、データが消失する。

特開２０１６―５４３４９公報

JP. Vasseur, 他, "Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks," Internet Engineering Task Force (IETF) Request for Comments: 6551, https://tools.ietf.org/html/rfc6551(2012)

本発明の実施形態は、無線マルチホップネットワークにおける輻輳の回避を可能とする無線通信装置、無線通信方法、コンピュータプログラム及び無線マルチホップネットワークを提供することを目的とする。

本発明の実施形態としての無線通信装置は、無線マルチホップネットワークにおける無線通信装置であって、複数の親ノード候補と無線信号を送受信する送受信部と、前記複数の親ノード候補から親ノードを選択する選択部を備える。前記選択部は、前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質と、前記複数の経路の前記根ノードまでのホップ数情報及び前記複数の経路上のノードの中継負荷情報の少なくとも一方とに基づき、前記親ノードを選択する。

第１の実施形態における無線通信システムの構成を示す図。 第１の実施形態における無線通信システムのネットワーク構成図。 第１の実施形態におけるフレーム構成を示す図。 第１の実施形態におけるネットワーク構成を示す図。 第１の実施形態におけるスロットの利用方法を示す図。 ＥＴＸ方式における親ノード選択方法を示す図。 ＥＴＸ方式における親ノード選択方法の問題を示す図。 第１の実施形態におけるネットワーク構成の例を示す図。 第１の実施形態における親ノード選択方法を示す図。 第１の実施形態における無線通信装置のブロック図。 第１の実施形態におけるパケットフォーマットの例を示す図。 第１の実施形態におけるリンクコストテーブルの一例を示す図。 第１の実施形態におけるフローチャートを示す図。 第２の実施形態におけるネットワーク構成の例を示す図。 第２の実施形態における親ノード選択方法を示す図。 第２の実施形態におけるフローチャートを示す図。 第３の実施形態における親ノード選択方法を示す図。 第３の実施形態におけるフローチャートを示す図。 ＥＴＸ方式における親ノード選択方法の更なる問題を示す図。 第５の実施形態における一つ目の親ノード選択方法を示す図。 第５の実施形態における二つ目の親ノード選択方法を示す図。 第５の実施形態における三つ目の親ノード選択方法を示す図。 第５の実施形態における四つ目の親ノード選択方法を示す図。

以下、図面を参照しながら、本発明の実施形態について説明する。

（第１の実施形態）
図１は第１の実施形態に係る無線通信システムの構成を示す図である。本ネットワークは１台のコンセントレータ（集約装置）１０１と複数の無線ノード（以下、ノード）１０２とを備える無線マルチホップネットワークである。各ノード１０２はセンサを搭載している。各ノード１０２は、センサで測定した情報を含むデータと、下位のノード（子ノード）から受信したデータとを上位のノードに送信（中継）する。これにより、各ノード１０２で取得されたセンサ情報がコンセントレータ１０１に集まる。

図２は、図１のシステム構成をネットワークトポロジーの形態で表した図である。コンセントレータ１０１を根ノードと称する。またノード１０２は、丸で囲んだアルファベットで表現されている。ノードＡ，Ｂ，及びＣは直接に根ノードと直接通信する。ノードＤ，Ｅ，Ｆ及びＧは、それぞれＡ，Ｂ，またはＣを介して根ノードと通信する。このように、各ノード１０２は直接あるいは他のノードを介して根ノードと通信する。このようなネットワークを、メッシュネットワークと呼ぶ。ここで、根ノードに近い側（ホップ数が小さい側）を上流側、根ノードから遠い側（ホップ数が多い側）を下流側とする。また各ノードが、下流側のデータを受信し、受信したデータを上流側に向かって送信しなおすことを中継と呼ぶ。中継を行うノードを中継ノードと呼ぶ。中継に当たっては、中継ノードが、自ノードで測定したセンサ情報等のデータを、受信した下流側のデータに追加することもある。中継にあたり、自ノードを送信相手として指定して送信してくる下流側のノードを子ノード、自ノードが無線信号を送信する相手となるノードを親ノードと呼ぶこととする。また、自ノードを集約装置１０１までの経路に含んでいるノードを子孫ノードと呼ぶ。子ノードも子孫ノードの一例である。また、以下の説明において、自ノードよりホップ数が少ないノードを上位ノード、自ノードよりホップ数が多いノードを下位ノードと呼ぶこともある。

図３は、第１の実施形態に係る無線マルチホップネットワークの通信方式を説明する図である。本ネットワークでは通信方式として時分割通信を行う。時分割通信では、時間をフレームに分割し、さらにフレームをスロットに細分化する。各ノードは特定のスロットを占有し、フレーム周期で無線信号を送信する。送信する無線信号は、具体的にはパケットの形態を有する。パケットのフォーマットについては後述する。図３の例では、各フレームにおける１番目のスロットがノードＣに割り当てられている。ノードＣが無線信号を送信するときは、各フレームにおける１番目のスロットにて無線信号を送信する。同様にノードＡは各フレームにおける３番目のスロット、ノードＢは各フレームにおける第５番目のスロットにて無線信号を送信する。

図４は、無線マルチホップネットワークの基本的な動作を説明するための図である。根ノードであるコンセントレータ（図４において図示せず）に至る各経路の途中にノード２，３，４，５，７がある。ノード２に対してノード３と５が無線接続（以下、接続）されている。また、ノード５に対してノード４が接続されており、ノード４に対してノード７が接続されている。接続とは予め接続処理および認証処理を行って、互いのパラメータ交換等を済ませた状態を意味する。接続されたノード間は親ノードと子ノードの関係にある。ノード３と５は、コンセントレータ１０１からＲホップ目である。またノード４はＲ＋１ホップ目である。

図５は、無線マルチホップネットワークの基本的な動作の説明図である。スロットベースの時分割通信を行う動作を示す。横軸は時間である。各ノードに対して根ノードからのホップ数（中継回数）に同じ値のランクを割り当てる。また、隣接する所定数の複数スロットをまとめてスロット群と定義する。フレーム内には複数のスロット群が配置される。そしてスロット群の中で最初のスロットをスロット番号１、次をスロット番号２、というように番号付けする。

各ノードは自ノードのランクに対応したスロット群で送信する。ここで、ランクが大きいノード（根ノードから遠いノード）ほど、フレーム内の複数のスロット群のうち、時間的に早いスロット群を使用する。例えば根ノードに直接信号が届くランクが１のノードについては、フレーム内の複数のスロット群のうち、もっとも時間的に後のスロット群を利用する。またランクが１のノードと通信可能なランクが２のノードについては、フレーム内の複数のスロット群のうち、最後から２番目のスロット群を使う。図４に示した例では、ノード３と５はコンセントレータ１０１からのホップ数がＲであるため、フレーム内の最後からＲ番目のスロット群を用いる。これにより、根ノードから遠い下流側ノードから順に上流側の根ノードに向かって、１フレーム以内でデータを中継する形態が実現できる。

また、各ノードは、自ノードのランクに対応するスロット群の中で、自ノードのＩＤ（ノードＩＤ）と同一の番号のスロット番号のスロットを使う。例えばノード３は、フレーム内の複数のスロット群のうち、最後からＲ番目のスロット群の中で、スロット番号３のスロットを使う。このようにすることで、システム内でノードＩＤの重複が無ければ、送信した無線信号が衝突することは無い。

親ノードは、子ノードの送信タイミングにおいて、受信動作を行う。例えば、ノード５の子ノードであるノード４の送信タイミングは、最後からＲ＋１番目の、スロット番号４である。したがって、ノード５は、最後からＲ＋１番目のスロット番号４において受信動作を行う。

子ノードは、親ノードの存在確認のために親ノードの送信した無線信号を受信する動作を行ってもよい。例えばノード５は、親ノードであるノード２の無線信号を受信し、ノード２が存在している（無線マルチホップネットワークから離脱していない）ことを確認する。ノード２のランクはＲ−１であるから、ノード５は、最後からＲ−１番目のスロット群のスロット番号２において受信動作を行う。

ノードは省電力化のため、送信及び受信するスロット以外の期間では、スリープする。スリープの動作例として、自ノードの回路（プロセッサ、通信回路等）の一部または全部の動作を停止させる。ノード５の場合、送信及び受信するスロットは、子ノードからの受信用のスロット、自ノードの送信用のスロット、親ノードからの受信用のスロットである。ノード５は、これらの３つのスロットでのみ動作し、他のスロットではスリープする。

ここで親ノードからの無線信号の受信について説明する。例えばノード４は、親ノード５からの受信用のスロットでは、親ノード５がさらにその親ノード２に送信する無線信号を受信する。この無線信号には、親ノード５がそのさらに親となるノードに送信するデータの他に、自ノード４が親ノード５に送信したデータが親ノード５で受信成功したかを示す受信確認信号（ＡＣＫ）も含まれている。このＡＣＫを確認することで、ノード４は、自ノードの送信成功可否を確認できる。また、親ノード５からの無線信号を受信することで、親ノード５の存在を確認できる。ここではノード４を例に説明したが、他のノードも同様の動作を行う。

無線マルチホップネットワークにおいて、あるノードについて、通信可能な複数の上位ノード（親ノードの候補）が存在する場合は、これらの上位ノードの中から、親ノードを選択する必要がある。親ノードを選択する方法としては、ＥＴＸ（Ｅｘｐｅｃｔｅｄ Ｔｒａｎｓｍｉｓｓｉｏｎ）と呼ばれる方式が良く知られている。以下、ＥＴＸ方式について説明する。

ＥＴＸ方式では、親ノードの選択のために、リンクコストおよびパスコストを用いる。
リンクコストとは、あるノードから、直接の通信相手のノード（例えば親ノード）までの通信に掛かるコストと定義される。ＥＴＸ方式の場合、リンクコストは、あるノードから、通信相手のノードへデータを誤り無く送るのに必要な送信回数の期待値である。データを誤り無く１回で送れるのであれば、リンクコストは１である。再送が１回あるいは２回必要な場合（再送回数の期待値が１または２の場合）は、リンクコストは２あるいは３となる。再送回数の期待値は、一例として、過去の再送回数の平均値などが用いられる。

パスコストとは、あるノードから根ノードまでの通信に掛かるコストのことである。ＥＴＸ方式の場合、パスコスト（以下、ＥＴＸパスコスト）は、総送信回数の期待値、すなわち根ノードへ至る経路上の全てのリンクコストの加算値である。ＥＴＸパスコストが小さいということは、ホップ数が少ないか、経路上のデータ誤りが少ないことを意味している。

図６に、リンクコスト及びＥＴＸパスコストの計算例を示す。ノードＡから根ノードまでのリングコスト（ＬＣ）は４である。これは、ノードＡから根ノードまでデータを送信するために、最初の送信に加え、期待値として３回の再送が必要であることを示している。ノードＡは根ノードに直接接続されているため、ノードＡのＥＴＸパスコスト（ＰＣ）は、リンクコストと同じ４である。

ノードＣからノードＡまでのリンクコストは３である。ノードＣからノードＡを経由して根ノードまでのＥＴＸパスコストは、ノードＡのＥＴＸパスコストと、ノードＣのリンクコストとの合計で７となる。すなわち、ノードＣからノードＡを経由して根ノードへ至る経路では、期待される総送信回数は７である。

このようなＥＴＸパスコストを利用して親ノードを選択する例を、ノードＮについて説明する。ノードＮの親ノード候補として、ノードＣ、ノードＡ、ノードＢおよび根ノードが存在する。ノードＮは、これらのノードを含む、根ノードへ至る４つの経路のそれぞれについて、ＥＴＸパスコストを計算する。そして、最もＥＴＸパスコストが小さい経路に含まれる親ノード候補を親ノードとする。ＥＴＸパスコストが小さい経路は、言い換えれば安定した通信品質でデータ送信が可能な経路であると言える。本例では、ＥＴＸパスコストが最も少なくなる経路は、ノードＣを経由する経路である。ノードＮは、ノードＣを親ノードとして選択する。

各ノードは、自ノードのＥＴＸパスコストを含む無線信号を、自ノード用のスロットで送信（報知）する。周囲のノードは、この無線信号を受信することで、当該ノードのＥＴＸパスコストを把握できる。例えばノードＡは、ＥＸＴパスコスト４を報知する。なお、以下の説明において、“ＥＸＴパスコストｘ”（ｘは実数）は、値がｘのＥＸＴパスコストを意味する。ノードＣは、ノードＡから受信したＥＸＴパスコスト４に、ノードＡおよびノードＣ間のリンクコスト３を加算して、ＥＸＴパスコスト７を得る。ノードＣは、ＥＸＴパスコスト７を報知する。ノードＮは、ノードＣから受信したＥＸＴパスコスト７に、ノードＮおよびノードＣ間のリンクコスト２を加算して、ノードＣを経由する場合の自ノードから根ノードまでの経路のＥＸＴパスコスト９を得る。ノードＮは、ノードＡ、根ノード、ノードＢに対しても同様にして、ＥＸＴパスコストを計算し、それぞれ１３、１５、１１を得る。ノードＣを経由する場合のパスコストが最も小さいため、ノードＣを親ノードとして選択する。

ＥＴＸ方式では、リンクが安定していて再送回数が少ない経路が選ばれる傾向がある。その結果、安定した経路に含まれるノードに中継されるデータが集中し、輻輳が発生し易い。

図７は、輻輳の問題を説明する図である。この例ではツリー型ネットワークの極端な例のうちの１つとして、全部で９台のノードＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ、Ｈ，Ｉがすべて数珠つなぎになっている。この場合、中継のたびに、各ノードで自ノード用のデータが追加されるため、根ノードに最も近いノードは、全部で９台分のデータを送信しなければならない。図のリンクに付された数字は、何台分のノードのデータを中継しているかを表している。ノードに多くのデータが集まると、このノードでデータのうちの一部を送信できない、あるいはデータのうちの一部をノード内のメモリに蓄積できなくなる場合がある。この結果、データが欠損し、根ノードによりデータの収集が失敗する可能性がある。

図８は、図７で説明した輻輳が解決するネットワーク構成のうちの１つを示す。図８の例では、図７に比べて多くのノードが、根ノードに直接接続されている。根ノードに直接接続するノードは、中継の依頼先となる上位ノードが存在しない。したがって根ノードに直接接続するノードを増やす事は、輻輳の回避に効果がある。一般的には、ホップ数が増えるほど、子孫ノード数が増えることになり、根ノードに近いノードにとっては、輻輳が起こりやすくなる。逆にホップ数が少ない場合は、子孫ノード数が少ない傾向になるため、輻輳が起こりにくくなる。よって、根ノードに直接接続するノードを増やすこと（ランク１のノードを増やすこと）、輻輳を効果的に回避できる。図８の例では、根ノードに直接するノードは３つであり、そのうち２つのノードＨ、Ｉは自ノードのみのデータを根ノードに送信し、残りの１つのノードＧは、７台分のデータを根ノードに送信する。図７の例では根ノードに直接接続するノードＩが、９台分のデータを送信したが、図８の例では、根ノードに直接接続するノードＧは、７台分のデータを送信すればよく、ノードＨ、Ｉは自ノードのみのデータを送信すればよいため、１ノードあたりの負荷を低減できる。

そこで、本実施形態では、ホップ数を減らし、ひいてはランクが１のノードを増やしたネットワーク構成を実現する。このために、１ホップごとに加算されるホップペナルティを導入する。

図９は、本実施形態に係るパスコスト（経路の評価値）を説明する図である。ノードＡは根ノードに直接接続されており、ノードＡと根ノードの間のリンクコスト（ＬＣ）は４である。なお、根ノードに直接されるノードの場合、根ノードへの経路のパスコストは、リンクコストに一致するものとする。

各ノードは、上位ノードから受信したパスコスト（受信ＰＣ）に、リンクコストを加算して、上位ノードを経由する場合の自ノードから根ノードまでの経路のパスコストを計算する。そして、このパスコストに、ホップペナルティ（＝１）を加算し、加算後のパスコストを、自ノードを経由する場合の自ノードから根ノードまでの経路のパスコスト（評価値）として報知する。このパスコストを受信した下流のノードは、受信したパスコスト（受信ＰＣ）にリンクコストを加算することで、当該上位ノードを経由する場合の自ノードから根ノードまでの経路のパスコストを計算する。そして、計算したパスコストにホップペナルティ１を加算して、加算後のパスコストを、自ノードを経由する場合の自ノードから根ノードまでの経路のパスコストとして報知する。このような動作を各ノードで行う。

具体的には、図９において、ノードＡは、根ノードとのリンクコスト４にホップペナルティ１を加算してパスコスト５を取得し、パスコスト５を報知する。つまり、ノードＡを経由する場合のノードＡから根ノードまでのパスコストは５であることを報知する。なお、“パスコストｘ”（ｘは実数）は、値がｘのパスコストを意味する。同様に、ノードＢは根ノードとのリンクコスト５にホップペナルティ１を加算してパスコスト６を取得し、パスコスト６を報知する。つまり、ノードＢを経由する場合のノードＢから根ノードまでのパスコストは６であることを報知する。

ノードＣはノードＡから受信したパスコスト（受信ＰＣ）５に、リンクコスト３を足した値８を、ノードＡを経由の場合のノードＣから根ノードまでの経路のパスコストとする。ノードＣは、パスコスト８にホップペナルティ１を加算してパスコスト９を取得し、パスコスト９を報知する。つまり、ノードＣを経由する場合のノードＣから根ノードまでのパスコストは９であることを報知する。

ノードＮはノードＣから受信したパスコスト９に、ノードＣとのリンクコスト２を足した値１１を、ノードＣを経由する場合のノードＮから根ノードへの経路のパスコストとする。同様に、ノードＮはノードＡから受信したパスコスト５に、ノードＡとのリンクコスト５を足した値１０を、ノードＡを経由する場合のノードＮから根ノードへの経路のパスコストとする。ノードＮは、根ノードと直接接続する場合、根ノードとのリンクコスト１５をそのままノードＮから根ノードへの経路のパスコストとする。ノードＮはノードＢから受信したパスコスト６に、ノードＢとのリンクコスト５を足した値１１を、ノードＢを経由する場合のノードＮから根ノードへの経路のパスコストとする。ノードＮは、最も小さいパスコスト１０が得られた経路の上位ノードであるノードＡを、親ノードとして選択する。パスコストは、親ノード選択に用いられる指標であり、経路の評価値に相当する。

このようにすることで、ホップ数が多いノードは、親ノードとして選ばれにくくなる。図９の例では、ノードＮにとっては、ノードＣを経由する経路よりも、ノードＡを経由する経路の方が、パスコストが小さくなる。従って、ノードＡを経由する経路が選択される。なお、親ノードが決定済みのノードであっても、親ノードの再選択処理を適宜行ってもよい。その場合、ノードＮと同様に、上位ノードから受信したパスコストにリンクコストを加算した値（ホップペナルティを加算する前の値）を用いて、親ノードを決定すればよい。

以上の説明から理解できるように、ノードＮのパスコスト（経路の評価値）は、根ノードに至るまでの経路の通信経路品質（経路上のリンクコストの合計）と、ホップ数情報とに基づいた計算される値である。ホップ数情報は、根ノードに至るまでの経路上のホップ数を表す。ホップペナルティの値が１ホップあたり１である場合、ホップ数情報は、経路上のホップペナルティの合計である。

具体的には、ノードＮについて、ノードＣを経由する場合の根ノードまでの経路の通信経路品質は、経路のリンクコストの合計であり、４＋３＋２＝９である。当該経路上のノードのホップ数情報は２である。すなわち、ノードＮの上流に根ノードに至るまでにノードＡ、Ｃの２つが存在する。したがって、経路の評価値（パスコスト）は９＋２＝１１である。この値は、上記の説明におけるノードＣを経由する場合のパスコスト１１と一致する。

同様に、ノードＮについて、ノードＡを経由する場合の根ノードまでの経路の通信経路品質は、経路のリンクコストの合計であり、４＋５＝９である。当該経路上のノードのホップ数情報は１である。すなわち、ノードＮの上流に根ノードに至るまでにノードＡの１つが存在する。したがって、経路の評価値（パスコスト）は９＋１＝１０である。この値は、上記の説明におけるノードＡを経由する場合のパスコスト１０と一致する。

同様に、ノードＮについて、根ノードまでの経路の通信経路品質は、根ノードとのリンクコストに一致し１５である。当該経路上のノードのホップ数情報は０である。すなわち、ノードＮの上流には、根ノードに至るまでに他のノードは１つも存在しない。したがって、経路の評価値（パスコスト）は１５＋０＝１５である。この値は、上記の説明における根ノードに直接接続する場合のパスコスト１５と一致する。

ノードＮについて、ノードＢを経由する場合の根ノードまでの経路の通信経路品質は、経路のリンクコストの合計であり、５＋５＝１０である。当該経路上のノードのホップ数情報は１である。すなわち、ノードＮの上流に根ノードに至るまでにノードＢの１つが存在する。したがって、経路の評価値（パスコスト）は１０＋１＝１１である。この値は、上記の説明におけるノードＢを経由する場合のパスコスト１１と一致する。

図９の説明では、各ノードはホップペナルティ１を加算して、周囲のノードにパスコストを報知したが、別の方法として、各ノードはホップペナルティを加算せずに、ＥＴＸ方式と同じパスコスト（ＥＴＸパスコスト）を報知してもよい。各ノードは、パスコスト（経路の評価値）を得る際は、上位ノードから受信したＥＴＸパスコストに、“自ノードのランク（ホップ数）−１”（すなわち上位ノードのランク）を加算することで、ペナルティを考慮したパスコスト（経路の評価値）を計算してもよい。このようにペナルティを考慮したパスコストを計算する具体的な方法には種々の方法がある。いずれの方法を用いてもかまわない。

図１０は本実施形態における無線通信装置（ノード）の構成を示す図である。無線通信装置は、アンテナ１０と、無線通信部２０とを備える。

アンテナ１０は、無線周波数の信号（無線信号）の送信及び受信を行う。アンテナ１０は１本でも、複数本でもよい。また、アンテナ１０はアレイアンテナでもよい。

無線通信部２０は、ＲＦ部２１、送受信部２２、データ生成部２５、親ノード選択部（選択部）２６、及び中継制御部２７を備える。送受信部２２は、送信部２３および受信部２４を備える。これらの各要素はＣＰＵ等のプロセッサまたは回路によって構成できる。また、これらの各要素がメモリ等のバッファを備えていてもよい。メモリは、ＤＲＡＭ、ＳＲＡＭ等の揮発性メモリでも、ＮＡＮＤ、ＦＲＡＭ、ＭＲＡＭ等の不揮発性メモリでもよい。また、本装置が、ハードディスク装置またＳＳＤなどのストレージ装置を備えていてもよい。

ＲＦ部２１は、アンテナ１０に接続されている。ＲＦ部２１は、送信用のパケットのビット系列を無線信号に変換し、無線信号を送信する処理を行う。ＲＦ部２１は、受信した無線信号からパケットのビット系列を取り出す処理を行う。図１１はパケットのフォーマットの一例を示す。パケットは、自ノードＩＤ、宛先ノードＩＤ、自ノードのデータ、子孫ノードのデータ、子孫数、パスコストなどのフィールドを有する。

データ生成部２５は、自ノード用のデータを生成する。データ生成部２５は、センサに接続されている。センサは、温度または傾きなどの情報を測定する。データ生成部２５は、センサから測定値を取得し、測定値をビット変換したデータを生成する。ここではセンサから自ノード用のデータを生成したが、これに限定されない。例えばＣＰＵにより行った演算結果でもよいし、装置の内部状態を表す値でもよい。

送信部２３は、データ生成部２５及び中継制御部２７の少なくとも一方から提供されたデータと、パラメータとに基づき、パケットを生成し、パケットの送信ビット系列をＲＦ部２１へ送り出す。ここでのデータとは、データ生成部２５で生成されたデータ（センサの測定値等）及び中継すべきデータ（子ノードから受信したデータ）である。データは自ノードデータフィールド、中継すべきデータは子孫ノードデータフィールドに格納される。パラメータは、送信先の親ノードのＩＤや、送信タイミング（例えばどのフレームのどのスロットか）、送信電力値などである。送信先の親ノードのＩＤは、宛先ノードＩＤフィールドに格納される。自ノードＩＤフィールドには、自ノードのＩＤを格納する。パスコストフィールドには、周囲のノードの報知するパスコスト（後述する親ノード選択部２６で計算される）を格納する。子孫数フィールドには、自ノードの子孫ノードの個数を設定する。その他、子ノードおよび子孫ノードに対応するＡＣＫフィールドを備えてもよい。この場合、例えば、子ノードおよび子孫ノードのデータを子ノードから受信した場合は、該当するノードのＡＣＫフィールドにビット１を立て、受信しなかった場合は０を立てる。パラメータは、データ生成部２５または中継制御部２７から送信部２３に提供される。もしくは、パラメータは、送信部２３内のバッファに事前に設定されていてもよい。

受信部２４は、ＲＦ部２１から受信したパケットのビット系列から、データおよびパラメータを取り出す。取り出されたデータ及びパラメータは、親ノード選択部２６及び中継制御部２７に送られる。ここでのパラメータとは、受信した無線信号の送信元ＩＤ、受信した際の受信電力や受信タイミングなどである。また自ノードが送信した無線信号に対する受信確認信号（ＡＣＫ）である場合もあり得る。

親ノード選択部２６は、受信部２４で得られたデータ（例えばパスコストなど）およびパラメータの少なくとも一方に基づき、親ノード候補の中から親ノードの選択を行う。親ノード候補は、例えば自ノードと無線信号を送受信可能なノードである。親ノード選択部２６は、親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質（例えばリンクコストの合計）と、当該複数の経路の根ノードまでのホップ数情報（中継負荷情報）とに基づき、親ノードを選択する。例えば、通信経路品質とホップ数情報とに基づきパスコスト（経路の評価値）の計算を行い、計算したパスコストに基づき、親ノードを選択する。選択された親ノードの情報は、中継制御部２７に送られる。リンクコストは、一例として、過去の送信履歴から送信に成功するまでに送信回数の期待値を計算することで、取得してもよい。あるいは、実際にリンクコスト計算のための通信を行って送信に成功するまでの送信回数を測定してもよい。リンクコストの別の計算方法として、ノードから受信した無線信号の受信電力値に基づいて、当該ノードとのリンクコストを計算してもよい。例えば受信電力値が大きいほど、小さな値のリンクコストを計算してもよい。一例として、図１２のリンクコストテーブルを用いて、これを実現できる。リンクコストテーブルでは、受信電力とリンクコストが対応づけられている。親ノード選択部２６は、受信した無線信号の受信電力に基づき、対応するリンクコストをリンクコストテーブルから取得する。親ノード選択部２６は、取得したリンクコストを、無線信号の送信元のノードとのリンクコストとする。

中継制御部２７は、受信部２４で受信された子ノードからのデータを受け取って、中継のために送信部２３に送り出す。また、中継制御部２７は、送信タイミングの決定などを行う。

図１３は、本実施形態における親ノード選択の動作の一例を示すフローチャートである。

受信部２４が、周囲のノードから無線信号を受信する（Ｓ１）。受信した無線信号には、送信元のノードＩＤ、および送信元のノードから報知されるパスコスト（図９参照）が含まれている。受信した無線信号から送信元のノードＩＤ、及びパスコストを取り出す（Ｓ２）。複数のノードから無線信号の受信を行うことで、複数の送信元のノードについて、ノードＩＤ及びパスコストを取得する。

親ノード選択部２６は、送信元のノードとの間のリンクコストを計算する（Ｓ３）。過去の送信履歴から送信に成功するまでに送信回数の期待値を計算することで、リンクコストを計算してもよいし、実際にリンクコスト計算のための通信を行って送信に成功するまでの送信回数を測定してもよい。または、上記送信元のノードから受信した無線信号の受信電力値に基づいて、リンクコストを計算してもよい。例えば受信電力値が大きいほど、小さな値のリンクコストを計算してもよい。

親ノード選択部２６は、送信元のノードから受信したパスコストと、計算したリンクコストとを加算し（Ｓ４）、送信元のノードを親とした場合の経路のパスコストを求める。この処理は、各送信元のノードについて行う。

親ノード選択部２６は、複数の送信元のノードに対して計算したパスコスト（経路の評価値）を比較し、パスコストが最小となったノードを親ノードとして選択する（Ｓ５）。

さらに親ノード選択部２６は、当該最小のパスコスト（選択した親ノードを経由する経路のパスコスト）にホップペナルティ（＝１）を加算することで、自ノードを経由する場合の自ノードから根ノードまでの経路のパスコストを計算する（Ｓ６）。

計算したパスコストを含む無線信号を周囲に報知する（Ｓ７）。自ノードに割り当てられたスロットで、親ノードへ送信する中継用データおよび自ノードで測定したデータとともに、パスコストを含むパケットを送信する。

以上の動作により、根ノードからのホップ数が多いノードは、周囲のノードから親ノードとして選択されにくくなる。

［ランクが小さい時だけホップペナルティを加算する］
上述した実施形態において、すべてのノードがホップペナルティ１を加算したが、ランクが小さいノードにおいてのみ、ホップペナルティ（値は１でもよいし、より大きな値でもよい）を加算し、それ以外のノードはホップペナルティの加算を行わない方法も考えられる。前述の通り、ランクが１のノードは直接根ノードに接続されるため、他のノードに負荷を掛けない。したがって、ランクが１のノードを増やすようにネットワークを構築してもよい。このためには、ランクが１のノードでのみ、ホップペナルティを加算すればよい。もちろんランク１に限らずランクが閾値以下のノードでのみ、ホップペナルティを加算する方法でも構わない。

逆に、ランクが閾値より大きいノードでのみ、ホップペナルティを加算する方法も考えられる。この方法を使えば、ランクが大きくなるほど、親ノードとして選ばれにくくなる。この結果、ある程度のホップ数までは、ＥＴＸ方式の場合と同様にネットワークが形成されるが、それ以上より長いホップ数になることが抑制される。結果的に、短すぎず、かつ長すぎないホップ数のノードが増える。

（第２の実施形態）
図１４は、第２の実施形態に係る無線マルチホップネットワークの例を示す。前述した図７及び図８で示した例とノードの位置が同じであるが、ネットワーク構成が異なっている。根ノードから遠いノード（例えばノードＢ）が、ノードＣではなく、ノードＦを親ノードとしている。ノードＢにとっては、ノードＣの方がノードＦよりも通信距離が短いにもかかわらず、ノードＦを親ノードとして選択している。これにより、経路が分岐し、根ノードへ至る経路が複数生成されている。また、ノードＢ等のホップ数は、図７及び図８の例よりも、小さくなっている。一般的にノード間の通信距離が長くなると、その分だけ通信誤りが増える傾向にある。しかしながら、あえて通信距離が長く通信誤りが多い経路を通ってでも、ホップ数を減らすことで、輻輳によるデータ欠損を避けた方が良い場合もある。図１４ではこのようなネットワーク構成を実現している。このための方法として本実施形態では、中継ノードの中継負荷情報としてトラヒックペナルティを導入する。トラフィックペナルティは、一例として、ノードが従えている子ノードの数に応じた値である。中継負荷情報は、ノードの中継負荷を表し、トラヒックペナルティはその一例である。

図１５は本実施形態における親ノードの選択方法を説明する図である。各ノードは、パスコストとして、受信したパスコスト（根ノードに直接接続しているノードの場合はリンクコスト）にトラヒックペナルティを加算し、加算後の値を、自ノードを経由する場合の自ノードから根ノードへ至る経路のパスコストとして報知している。例えばノードＡは、ノードＡと根ノードの間のリンクコスト４に対して、トラヒックペナルティ（ＴＰ）２を加えた６を、自ノードＡを経由する場合の自ノードＡから根ノードまでの経路のパスコストとして報知する。トラフィックペナルティは、自ノードが従えている子ノードの数に応じた値とする。ノードＡの場合、子ノード１台を従えているため、１台あたりのペナルティ値を２とすると、トラフィックペナルティは２となる。もし子ノードが２台であれば、トラフィックペナルティは２台分の４である。

パスコストを受信したノードＣは、受信したパスコストに、ノードＡとノードＣとの間のリンクコスト３を加算してパスコスト９を算出する。ノードＣは、算出したパスコスト９を、ノードＡを経由する場合のノードＣから根ノードまでの経路のパスコストとして報知する（図の状態ではノードＣに子ノードは存在しないため、トラフィックペナルティの加算は行わない）。

このようにノードが持つ子ノードの数に比例したトラヒックペナルティを加算し、加算後の値を、自ノードを経由する場合の自ノードから根ノードまでの経路のパスコストとして報知する。この方法によれば、従える子ノードの数が多いノードは、必然的に報知するパスコストが大きくなるため、親ノードとして選ばれにくくなる。図１５の例では、ノードＮは、一切の子ノードを従えていないノードＢを、親ノードとして選択している。すなわち、ノードＢから報知されるパスコスト５と、ノードＢとのリンクコスト５とを加算した値は１０である。ノードＡから報知されるパスコスト６と、ノードＡとのリンクコスト５とを加算した値は１１である。ノードＣから報知されるパスコスト９と、ノードＣとのリンクコスト２とを加算した値は１１である。よって、ノードＢ経由の経路のパスコストが最も小さい。このため、ノードＮは、ノードＢを親ノードとして選択する。

図１６は、本実施形態における親ノード選択の動作の示すフローチャートである。図１３に比べ、報知するパスコストを算出する処理が異なる。すなわち、周囲のノードから受信したパスコストに対し、当該ノードとの間のリンクコストを加算するのみならず、自ノードのトラヒックペナルティを加算し（Ｓ１１）、加算後のパスコストを、自ノードを経由する場合における自ノードから根ノードまでの経路のパスコストとして周囲に報知する。

なお本実施形態では、トラヒックペナルティとして子ノードの台数に応じた値を用いたか、他の方法も可能である。例えば、トラヒックペナルティの値を、子ノードだけでなく、子孫のノードの台数に応じた値としてもよい。あるいは、子ノードから自ノードに送られてくるデータ量に応じた値、あるいはこのデータの量の平均値に応じた値を、トラヒックペナルティの値としてもよい。子ノードが複数存在する場合は、すべての子ノードからの合計データ量またはその平均値に応じた値を、トラヒックペナルティの値としてもよい。

さらに、各ノードにおいてデータの溢れが発生し、データの一部を中継送信できない、あるいは受信したデータの一部を記憶できない等の事態が生じた場合（あるいは生じうる場合）、トラヒックペナルティの値を無限大、あるいは通常より大きい値、あるいは非常に大きな値としてもよい。これにより、実質的に他のノードが自ノードを親ノードに選択しないようにすることもできる。

（第３の実施形態）
図１７は本実施形態における親ノード選択の動作を示す図である。本実施形態は、第１の実施形態で導入したホップペナルティと、第２の実施形態で導入したトラヒックペナルティの双方を適用する。

例えばノードＡに着目すると、ノードＡは、根ノードまでのリンクコスト４に対し、ホップペナルティ１と、トラヒックペナルティ２（１台の子ノードＣを従えており、１台の子ノードあたりトラヒックペナルティの値は２とする）とを加算した７を、自ノードＡを経由する場合のノードＡから根ノードまでの経路のパスコストとして報知している。これを受信したノードＣは、さらにノードＡとノードＣの間のリンクコストである３と、ホップペナルティ１とを加算し、加算後のパスコスト１１を、自ノードＣを経由する場合の自ノードＣから根ノードまでの経路のパスコストとして、報知している。ノードＣは子を従えていないので、トラヒックペナルティは０である。すなわち、ノードＣは、トラフィックペナルティを加算しない。

ノードＮは、ノードＣから受信したパスコスト１１に、ノードＣとのリンクコスト２を加算して、パスコスト（経路の評価値）１３を得る。また、ノードＮは、ノードＡから受信したパスコスト７に、ノードＡとのリンクコスト５を加算し、パスコスト１２を得る。また、ノードＮは、ノードＢから受信したパスコスト６に、ノードＢとのリンクコスト５を加算し、パスコスト１１を得る。また、ノードＮは、根ノードに直接する場合のリンクコスト１５をパスコストとする。これらのパスコストの中で、最小のパスコストはノードＢである。このため、ノードＮは、ノードＢを親ノードとして選択する。

本実施形態によれば、ホップ数が多いノードや、子ノードを多く従えているノードは親ノードとして選ばれにくくなる。従ってホップ数が少なく、経路の集中が軽減されたネットワークが形成される。これにより、輻輳が起こりにくくなり、結果としてデータの欠損が起こりにくくなる。

図１８は本実施形態においてノードが親ノードを選択する動作のフローチャートを示す。本フローチャートは、受信したパスコストに、リンクコストを加算するのみならず（Ｓ４）、ホップペナルティとトラヒックペナルティの双方を加算している（Ｓ１２）。それ以外のステップは、図１３または図１６と同じである。

（第４の実施形態）
第４の実施形態においては、ホップペナルティの値、およびトラヒックペナルティの値の決め方について記載する。

第１の実施形態では、ホップペナルティは１ホップあたり１、第２の実施形態では、トラヒックペナルティは子ノード１台あたり２とした。これらのペナルティは輻輳を回避するためのペナルティであり、これらのペナルティを利用すると、ペナルティが無い場合に選択される理想的なノードとは異なるノードを親ノードとして選択する場合も起こり得る。例えば、通信品質があまり良くないノードを親ノードとして選択する事態が生じ得る。従って、輻輳が生じにくい場合は、ペナルティを軽減すべきである。逆に輻輳が生じやすい場合は、通信品質を犠牲にしても、積極的にペナルティを大きくして輻輳回避を図った方が良い場合がある。

そこで例えば各ノードは、一定期間の間（例えば１フレームの間）、リスニングを行い、周囲からの無線信号を受信する。受信される無線信号の個数が少ない場合は、周囲に存在するノードの数が少なく（すなわちネットワーク内のノード密度が低く）、結果として輻輳が起きにくいと判断する。この場合、ホップペナルティおよびトラヒックペナルティの少なくとも一方の値を低くする。ここでは受信した無線信号の個数によって周囲のノード数を把握したが、受信した無線信号を復調して送信元のノードのＩＤを把握し、送信元のノードの個数をカウントしてもよい。

逆に、受信される無線信号の個数が多い場合は、周囲に存在するノードの数が多く（すなわちシステム内のノード密度が高く）、結果として輻輳が起きやすいと判断する。この場合、ホップペナルティおよびトラヒックペナルティの少なくとも一方の値を高くする。

これらの制御により、輻輳が起きにくい環境では通信品質に基づく親ノード選択ができるようになり、輻輳が起きやすい環境では、輻輳回避を積極的に行う親ノード選択ができるようになる。

（第５の実施形態）
第１〜第４の実施形態ではホップペナルティまたはトラフィックペナルティを導入することで、ＥＴＸ方式の問題点を解消したが、本実施形態では、別の方法で当該問題を解消する。

図１９は、ＥＴＸ方式の問題点を説明する図である。ＥＴＸ方式では、リンクコストは送信成功に必要な送信回数の期待値を表しており、リンクコストの最小値は１である。図の例では、ノードＡと根ノードのリンクコストは１であり、ノードＣとノードＡのリンクコストは１である。従って、ノードＣのパスコストは最小値の２（＝１＋１）である。ノードＣは、１ホップ目にいるパスコストが１．５のノードＢに比べ、パスコストが大きいため、親として選ばれにくい。しかし、ノードＣおよびノードＡ間、ノードＡおよび根ノード間のリンクコストがそれぞれ最小の１ということは、ノードＣから根ノードまで、再送なしで、１回でデータを確実に送信できるということである。それにも関わらず、再送が必要になる可能性が高いルートＢを通る経路を選択することは、通信の信頼性を追求するのであれば、適切でない。このようにＥＴＸ方式では、必ずしも通信の信頼性の観点から最適では無いノードが選択され易い点がある。信頼性を追求するのであれば、各ノードから根ノードまでのデータ収集が確実に出来る、言い換えると、データ収集成功率が最大となる経路と選ぶべき場合がある。

図２０は、本実施形態に係る親ノード選択の動作を説明する図である。通信成功率を用いてリンクコストを定義している。パスコストは経路上のリンクの通信成功率の乗算値としている。例えば、ノードＡと根ノードの間の通信成功率は０．９５である。ノードＡはパスコスト（リンクコストに等しい）として、この０．９５を報知する。またノードＡとノードＣの間の通信成功率は０．９７である。ノードＣは、ノードＡから受信した０．９５に０．９７を乗じ、０．９２１５をパスコストとして報知する。受信したパスコストにリンクコストを乗じているのは、ノードＣからノードＡを通じて根ノードに至る通信成功率が、両者の積で表されるからである。ノードＢも同様にして通信成功率０．９６のパスコストを報知する。

ノードＮは、ノードＣからのパスコスト０．９１２５を受信し、ノードＮとノードＣとの間のリンクコスト（通信成功率０．９８）を乗算して、ノードＣを経由する経路のノードＮから根ノードまでのパスコスト０．９０３０７を得る。

同様にして、ノードＮは、ノードＡからのパスコスト０．９５を受信し、ノードＮとノードＡとの間のリンクコスト（通信成功率０．９２）を乗算して、ノードＡを経由する場合のノードＮから根ノードまでのパスコスト０．８７４を得る。

同様にして、ノードＮは、根ノードに直接接続する場合のパスコスト０．７７を得る。

同様にして、ノードＮは、ノードＢからのパスコスト０．９６を受信し、ノードＮとノードＢとの間のリンクコスト（通信成功率０．９３）を乗算して、ノードＢを経由する場合のノードＮから根ノードまでのパスコスト０．８９２８を得る。

ノードＣを経由する場合のパスコストが最も大きいため、ノードＮはノードＣを親ノードとして選択する。本実施形態ではリンクコストを通信成功率で表し、パスコストはその積としているため、リンクコストおよびパスコストは、値が高いほど良いことに注意する。

図２１は、図２０の例に、ホップペナルティとトラヒックペナルティとを適用してパスコストを計算する例を示す。本実施形態ではリンクコストやパスコストは高いほど良いため、これらペナルティは、値を減じるために用いられる。具体的には、リンクコストに応じた値、またはパスコストに応じた値を減算することで、ペナルティを実現する。値を減算するとは、言い換えれば、負の値を加算していることである。すなわち、本実施形態ではリンクコストおよびパスコストが負の値であると言える。図２１の例では、ホップペナルティとして０．１、トラヒックペナルティとして子１台あたり０．１を減算する例を示している。この方法によれば、通信成功率の高い経路を選択しつつ、通信の輻輳を回避できるようになる。ここではペナルティとして値を減算したが、１より小さい値を乗じることも可能である。

例えばノードＡは、通信成功率（リンクコスト）０．９５から、ホップペナルティ０．１と、トラヒックペナルティ０．１を減算して、パスコスト０．７５を計算している。ノードＡはパスコスト０．７５を報知する。ノードＣは、パスコスト０．７５を受信し、これにノードＡおよびノードＣ間の通信成功率（リンクコスト）０．９７を乗算して、ノードＡを経由する場合のノードＣから根ノードまでのパスコスト０．７２７５を計算している。さらにノードＣは、これからホップペナルティ０．１を減算して、ノードＣを経由する場合のノードＣから根ノードまでの経路のパスコスト０．６２７５を計算し、このパスコスト０．６２７５を報知している。同様にして、ノードＢは、リンクコスト０．９６から、ホップペナルティ０．１を減算して（ノードＢに子ノードは存在しないため、トラヒックペナルティはゼロ）、パスコスト０．８６を計算している。ノードＢは．パスコスト０．８６を報知している。

ノードＮは、ノードＣからのパスコスト０．６２７５を受信し、ノードＮとノードＣとの間のリンクコスト（通信成功率０．９８）を乗算して、ノードＣを経由する経路のノードＮから根ノードまでのパスコスト０．６１４９５を得る。

同様にして、ノードＮは、ノードＡからのパスコスト０．７５を受信し、ノードＮとノードＡとの間のリンクコスト（通信成功率０．９２）を乗算して、ノードＡを経由する場合のノードＮから根ノードまでのパスコスト０．６９を得る。

同様にして、ノードＮは、根ノードに直接接続する場合のパスコスト０．７７を得る。

同様にして、ノードＮは、ノードＢからのパスコスト０．８６を受信し、ノードＮとノードＢとの間のリンクコスト（通信成功率０．９３）を乗算して、ノードＢを経由する場合のノードＮから根ノードまでのパスコスト０．７９９８を得る。

ノードＢを経由する場合のパスコストが最も大きいため、ノードＮはノードＢを親ノードとして選択する。

ここで、乗算演算（例えばノードＣにおいてノードＡから受信したパスコストと、ノードＣ及びノードＡ間のリンクコストとの乗算）は、電子回路から成る無線機の内部では回路規模が大きくなるなどの理由で実装が難しい場合もある。そこで、リンクコストは通信成功率の対数値とし、パスコストを求める際には加算演算で実現する方法も可能である。２値の乗算値の対数を取ることは、２値の対数を加算することと等価な性質を利用したものである。

図２２は、パスコストの計算を加算演算で行う例を説明する図である。例えばノードＡと根ノードの間の通信成功率０．９５の場合、ノードＡは、０．９５の対数を取り、さらにホップペナルティとトラヒックペナルティを減算して、パスコスト−０．０２９を計算する。ノードＡは、パスコスト−０．０２９を送信する。ノードＣは、Ａから受信した−０．０２９という値に、ノードＡとノードＣの間の通信成功率０．９７の対数値を加算して、ノードＡを経由する場合のノードＣから根ノードまでのパスコストを計算する。さらにノードＣは、この値から、ホップペナルティ０．００２を減算して、ノードＣを経由する場合のノードＣから根ノードまでのパスコスト−０．０４４を計算し、パスコスト−０．０４４を報知する。ノードＢは、０．９６の対数を取り、さらにホップペナルティを減算して、パスコスト−０．０２０を計算する。ノードＢは、パスコスト−０．０２０を送信する。

ノードＮは、ノードＣからのパスコスト−０．０４４を受信し、ノードＮとノードＣとの間のリンクコスト（通信成功率０．９８の対数値）を加算して、ノードＣを経由する経路のノードＮから根ノードまでのパスコスト−０．０５２を得る。

同様にして、ノードＮは、ノードＡからのパスコスト−０．０２９を受信し、ノードＮとノードＡとの間のリンクコスト（通信成功率０．９２の対数値）を加算して、ノードＡを経由する場合のノードＮから根ノードまでのパスコスト−０．０６５を得る。

また、ノードＮは、根ノードとのリンクコスト０．７７の対数値を計算して、根ノードに直接接続する場合のパスコスト−０．１１を得る。

ノードＮは、ノードＢからのパスコスト−０．０２０を受信し、ノードＮとノードＢとの間のリンクコスト（通信成功率０．９３の対数値）を加算して、ノードＢを経由する場合のノードＮから根ノードまでのパスコスト−０．０５１を計算する。

ノードＢを経由する場合のパスコストが最も小さいため、ノードＮはノードＢを親ノードとして選択する。

このように通信成功率の対数値をリンクコストとすることで、ノード内での乗算を回避し、加減算によるパスコスト計算を可能にできる。

さらに、リンクコストやパスコストが負の値（すなわち減算）では実装が困難な場合がある。そこで、加算演算のみでパスコストを計算する方法を以下に示す。この方法では通信成功率の逆数について対数値を取り、これをリンクコストとする（リンクコストの値は小さいほど良い）。そしてリンクコスト及びパスコストは双方とも０以上の値とする。報知するパスコストの計算の際は、リンクコスト及びパスコストを加算する。つまり、ホップペナルティ及びトラヒックペナルティは、報知するパスコストの値を増加させる方向に使われる。

図２３は、通信成功率を利用してリンクコストを定義しつつ、加算演算のみでパスコストを計算する例を説明する図である。通信成功率の逆数の対数値をリンクコストとし、リンクコスト及びパスコストは双方とも０以上の値としている。例えばノードＡと根ノード間の通信成功率は０．９５であるため、根ノードへの経路のパスコストは０．９５の逆数の対数値である。この値にホップペナルティ０．００２と、子ノード１台分のトラヒックペナルティ０．００５とを加算し、加算後の値０．０２９を、ノードＡを経由する場合のノードＡから根ノードまでのパスコストとして報知する。同様にして、ノードＢの根ノードへの経路のパスコストは０．９６の逆数の対数値である。ノードＢは、この値にホップペナルティ０．００２を加算し、加算後の値パスコスト０．０２０を、ノードＢを経由する場合のノードＢから根ノードまでのパスコストとして報知する。

ノードＣは、このパスコスト０．０２９を受信し、ノードＣとノードＡとの間のリンクコスト（通信成功率０．９７の逆数の対数値）を加算して、ノードＡを経由する経路のノードＣから根ノードまでのパスコスト０．０４２を得る。ノードＣは、これにホップペナルティ０．００２を加算して、報知するパスコスト０．０４４を得る。このパスコスト０．０４４を報知する。

ノードＮは、このパスコスト０．０４４を受信し、ノードＮとノードＣとの間のリンクコスト（通信成功率０．９８の逆数の対数値）を加算して、ノードＣを経由する経路のノードＮから根ノードまでのパスコスト０．０５２を得る。

同様にして、ノードＮは、ノードＡからのパスコスト０．０２９を受信し、ノードＮとノードＡとの間のリンクコスト（通信成功率０．９２の逆数の対数値）を加算して、ノードＡを経由する場合のノードＮから根ノードまでのパスコスト０．０６５を得る。

ノードＮは、根ノードに直接接続する場合のパスコスト０．１１を得る。

ノードＮは、ノードＢからのパスコスト０．０２０を受信し、ノードＮとノードＢとの間のリンクコスト（通信成功率０．９３の逆数の対数値）を加算して、ノードＢを経由する場合のノードＮから根ノードまでのパスコスト０．０５１を得る。

ノードＢを経由する場合のパスコストが最も小さいため、ノードＮはノードＢを親ノードとして選択する。

なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。

１０：アンテナ
２０：無線通信部
２１：ＲＦ部
２２：送受信部
２３：送信部
２４：受信部
２５：データ生成部
２６：親ノード選択部（選択部）
２７：中継制御部

Claims (15)

1. 無線マルチホップネットワークにおける無線通信装置であって、
   複数の親ノード候補と無線信号を送受信する送受信部と、
   前記複数の親ノード候補から親ノードを選択する選択部を備え、
   前記選択部は、
   前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算し、前記複数の経路の評価値に基づき、前記親ノードを選択し、
   前記根ノードまでのポップ数が閾値以下の前記ノードについてのみ前記ペナルティ値を加算する
   無線通信装置。
2. 前記選択部は、前記複数の経路上の前記ノードの中継負荷情報に基づき、前記複数の経路の評価値を計算する
   請求項１に記載の無線通信装置。
3. 前記中継負荷情報は、前記複数の経路上の前記ノードの子ノードまたは子孫ノードの個数を表す
   請求項２に記載の無線通信装置。
4. 前記中継負荷情報は、前記複数の経路上の前記ノードの中継データ量を表す
   請求項２に記載の無線通信装置。
5. 前記選択部は、前記経路上の各ノード間の通信の成功確率、前記各ノード間の前記通信の成功に必要な通信回数の期待値、または、前記各ノード間の無線信号の受信電力に基づき、前記経路の通信経路品質を計算する
   請求項１ないし４のいずれか一項に記載の無線通信装置。
6. 前記選択部は、前記送受信部で受信される前記無線信号に基づき、自ノードの周囲の無線通信装置の台数を検出し、前記検出した台数に基づいて前記評価値を計算する
   請求項１に記載の無線通信装置。
7. 前記選択部は、前記通信経路品質を表す値に、前記中継負荷情報に応じたペナルティ値を加算または減算することにより前記評価値を計算する
   請求項２〜４のいずれか一項に記載の無線通信装置。
8. 前記親ノードに、子ノードから受信したデータを中継する中継制御部
   をさらに備えた請求項１ないし７のいずれか一項に記載の無線通信装置。
9. 無線マルチホップネットワークで実行する無線通信方法であって、
   第１ノードが、複数の親ノード候補と無線信号を送受信し、
   前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算し、前記複数の経路の評価値に基づき、前記複数の親ノード候補から親ノードを選択し、
   前記根ノードまでのポップ数が閾値以下の前記ノードについてのみ前記ペナルティ値を加算する
   無線通信方法。
10. 無線マルチホップネットワークにおける無線通信装置に実行させるためのコンピュータプログラムであって、
    複数の親ノード候補と無線信号を送受信するステップと、
    前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算するステップと、
    前記複数の経路の評価値に基づき、前記複数の親ノード候補から親ノードを選択するステップと、を備え、
    前記根ノードまでのポップ数が閾値以下の前記ノードについてのみ前記ペナルティ値を加算する
    コンピュータプログラム。
11. 複数のノードと、根ノードとを備え、前記ノードが保持するデータを、他の前記ノードによる中継により前記根ノードへ集約する、無線マルチホップネットワークであって、
    前記ノードは、複数の親ノード候補と無線信号を送受信し、
    前記ノードは、前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算し、前記複数の経路の評価値に基づき、前記複数の親ノード候補から親ノードを選択し、前記根ノードまでのポップ数が閾値以下の前記ノードについてのみ前記ペナルティ値を加算する
    無線マルチホップネットワーク。
12. 無線マルチホップネットワークにおける無線通信装置であって、
    複数の親ノード候補と無線信号を送受信する送受信部と、
    前記複数の親ノード候補から親ノードを選択する選択部を備え、
    前記選択部は、
    前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算し、前記複数の経路の評価値に基づき、前記複数の親ノード候補から親ノードを選択し、
    前記根ノードまでのポップ数が閾値より大きい前記ノードについてのみ前記ペナルティ値を加算する
    無線通信装置。
13. 無線マルチホップネットワークで実行する無線通信方法であって、
    第１ノードが、複数の親ノード候補と無線信号を送受信し、
    前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算し、前記複数の経路の評価値に基づき、前記複数の親ノード候補から親ノードを選択し、
    前記根ノードまでのポップ数が閾値より大きい前記ノードについてのみ前記ペナルティ値を加算する
    無線通信方法。
14. 無線マルチホップネットワークにおける無線通信装置に実行させるためのコンピュータプログラムであって、
    複数の親ノード候補と無線信号を送受信するステップと、
    前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算するステップと、
    前記複数の経路の評価値に基づき、前記複数の親ノード候補から親ノードを選択するステップと、を備え、
    前記根ノードまでのポップ数が閾値より大きい前記ノードについてのみ前記ペナルティ値を加算する
    コンピュータプログラム。
15. 複数のノードと、根ノードとを備え、前記ノードが保持するデータを、他の前記ノードによる中継により前記根ノードへ集約する、無線マルチホップネットワークであって、
    前記ノードは、複数の親ノード候補と無線信号を送受信し、
    前記ノードは、前記複数の親ノード候補を含む、根ノードへ至る複数の経路の通信経路品質を表す値に、前記複数の経路上のノードの前記根ノードまでのホップ数に応じたペナルティ値を加算することにより前記複数の経路の評価値を計算し、前記複数の経路の評価値に基づき、前記複数の親ノード候補から親ノードを選択し、前記根ノードまでのポップ数が閾値より大きい前記ノードについてのみ前記ペナルティ値を加算する
    無線マルチホップネットワーク。

Images