JP2018139378A - 経路生成装置、経路生成プログラムおよびマルチホップ無線メッシュネットワークシステム - Google Patents

Abstract

【課題】データ通信を遅延させずに経路情報を生成する経路生成装置、経路生成プログラムおよびマルチホップ無線メッシュネットワークシステムを提供することにある。【解決手段】実施形態の経路情報生成装置は、生成部と通信部とを備える。生成部は、送信端末と、宛先端末を含む宛先グループと、複数の第１無線通信端末を含む第１中継グループと、を有するマルチホップ無線メッシュネットワークにおいて、前記宛先グループとの接続性に基づいて、前記第１中継グループに含まれる複数の第１無線通信端末のうちの一つを第１中継端末として設定する。生成部はまた、前記第１中継端末が前記送信端末から送られた前記宛先端末宛てのデータを受信した場合に前記宛先端末へ前記データを転送するための第１経路情報を生成する。通信部は、前記第１経路情報を前記第１中継端末へ配信する。【選択図】図３

Description

経路生成装置、経路生成プログラムおよびマルチホップ無線メッシュネットワークシステムに関する。

近年省エネ化が求められているため、ビルなどの空調機や照明などのインフラ機器の利用状況のデータを収集し、得られたデータを使ってインフラ機器を制御することで省エネを目指すBEMS（Building Energy Management System）の導入が活発である。このデータ収集と制御のフィードバックについて、現在は有線ネットワークを介した実現が主流である。しかし、有線ネットワークは設置コストが高く、また既存のシステを置き換える場合には設置場所に制限があるため、無線ネットワークで実現が求められる。機器を設置する場所の広さによっては、無線ネットワークにおいてデータ収集元となる集約機器にすべての無線通信端末が直接接続できない場合がある。そこで、ある無線通信端末が送信したデータを集約機器までに存在する別の無線通信端末を経由して集約機器までデータを届けることができるマルチホップ無線メッシュネットワークを用いる必要がある。

マルチホップ無線メッシュネットワークでは、どの無線通信端末を経由してルータや他の無線通信端末と通信するかの経路情報を通信開始前に確認するために、管理パケットを交換することで経路情報を設定する方法（AODV；Ad hoc On-Demand Distance Vector）等が知られている。マルチホップ無線メッシュネットワークは膨大な数の無線通信端末から構成されるため、管理パケットを交換する方法では無線帯域を占有する管理パケット数が膨大になり、データ通信が遅くなったり、データ通信が安定しなかったりする場合がある。

特開２００６−１０１４９７号公報 特開２００８−２９４９４４号公報

データ通信を遅延させずに経路情報を生成する経路生成装置、経路生成プログラムおよびマルチホップ無線メッシュネットワークシステムを提供することにある。

実施形態の経路情報生成装置は、生成部と通信部とを備える。生成部は、送信端末と、宛先端末を含む宛先グループと、複数の第１無線通信端末を含む第１中継グループと、を有するマルチホップ無線メッシュネットワークにおいて、前記宛先グループとの接続性に基づいて、前記第１中継グループに含まれる複数の第１無線通信端末のうちの一つを第１中継端末として設定する。生成部はまた、前記第１中継端末が前記送信端末から送られた前記宛先端末宛てのデータを受信した場合に前記宛先端末へ前記データを転送するための第１経路情報を生成する。通信部は、前記第１経路情報を前記第１中継端末へ配信する。

第一の実施形態に係るマルチホップ無線メッシュネットワークシステムの構成例。 第一の実施形態に係る経路生成装置の構成例。 第一の実施形態に係る経路生成装置の処理の一例を示すフローチャート。 通信状態収集部２１０が収集する通信品質データ構造の一例。 第一の実施形態の第一変形例に係るマルチホップ無線メッシュネットワークシステムの他の構成例。 第一の実施形態に係る経路生成装置の処理の他の一例を示すフローチャート。 第一の実施形態の第一変形例に係る経路生成装置の処理の一例を示すフローチャート。 第一の実施形態の第一変形例に係る経路情報の一例。 第一の実施形態の第二変形例に係る経路生成装置の処理の一例を示すフローチャート。 第一の実施形態の第二変形例に係る経路生成装置の処理の他の一例を示すフローチャート。 第一の実施形態の第二変形例に係る経路生成装置の処理の他の一例を示すフローチャート。 第一の実施形態の第三変形例に係る経路生成装置の処理の一例を示すフローチャート。 第一の実施形態の第三変形例に係る経路生成装置の処理の他の一例を示すフローチャート。 第一の実施形態の第三変形例に係る経路生成装置の処理の他の一例を示すフローチャート。 第一の実施形態の第三変形例に係る経路情報の一例。 第二の実施形態に係る経路生成装置の構成例。 第二の実施形態に係る経路生成装置の処理の一例を示すフローチャート。 第三の実施形態に係るハードウェア構成の一例を示すブロック図である。

以下、の実施形態について説明する。実施形態や変形例に共通の構成や処理は、詳細な説明を適宜省略する。

（第一の実施形態）
マルチホップ無線メッシュネットワークシステムに含まれる無線通信端末は、例えば、同じマルチホップ無線メッシュネットワークシステムに含まれる他の無線通信端末から受信した信号によって動作を制御されたり、保持するデータを他の無線通信端末に集約したりする。マルチホップ無線メッシュネットワークシステムに含まれる複数の無線通信端末は、例えば高密度に存在する。

マルチホップ無線メッシュネットワークシステムに含まれる送信端末と宛先端末が直接データ通信することができなかったり、安定してデータ通信することが出来なかったりする場合に、経路生成装置は、送信端末と宛先端末のデータ通信を中継する中継端末を設定し、中継端末のための経路情報を生成する。

経路生成装置は、中継端末となる無線通信端末に生成した経路情報を送信する。経路生成装置の生成した経路情報に基づいて、送信端末のデータは中継端末を介して宛先端末に送られる。経路生成装置は、マルチホップ無線メッシュネットワークシステムに含まれる複数の無線通信端末の識別子と各無線通信端末が属するグループの識別子を予め保持している。

中継端末は一または複数設けられる。送信端末と宛先端末の間に一の中継端末（第１中継端末）が設けられる場合について以下に説明する。

マルチホップ無線メッシュネットワークシステムに含まれる各無線通信端末は、例えば、地理的情報（位置情報）に基づいてグループ分けされる。同一のグループに属する複数の無線通信端末同士は直接通信が可能であることとする。

図１は、第一の実施形態に係るマルチホップ無線メッシュネットワークシステムの構成例である。マルチホップ無線メッシュネットワークシステムは、複数の無線通信端末（１１〜１４、２１〜２４、３１〜３４）と経路生成装置２００とを含む。

図１によると、宛先端末（第１の無線通信端末）１１と無線通信端末１２〜２４は、宛先グループ（第１のグループ）１０に属する。無線通信端末２１〜２４は、第１中継グループ（第２のグループ）２０に属する。送信端末（第３の無線通信端末）３１と無線通信端末３２〜３４は、送信グループ（第３のグループ）に属する。第１中継グループ２０は、２以上の無線通信端末を含む。宛先グループ１０と送信グループ３０には、それぞれ少なくとも１の無線通信端末を含む。

マルチホップ無線メッシュネットワークシステムは、宛先グループ１０と第１中継グループ２０と送信グループ３０のいずれにも含まれない無線通信端末をさらに含んでもよい。マルチホップ無線メッシュネットワークシステムは、他のグループを含んでもよい。

図２は、第一の実施形態に係わる経路生成装置２００の構成例である。経路生成装置２００は、通信状態収集部２１０、接続性指標計算部２２０、経路情報生成部２３０、および通信部２４０を含む。

図３は、第一の実施形態に係る経路生成装置の処理を示すフローチャートである。通信状態収集部２１０は、マルチホップ無線メッシュネットワークシステム内の無線通信端末同士が相互に通信して計測される通信品質データを収集する（Ｓ３０１）。通信品質データは、大小がわかるものであれば何を用いてもよく、例えば値が大きいほど通信品質データが高い。例えば受信信号強度（ＲＳＳＩ：Ｒｅｃｅｉｖｅｄ Ｓｉｇｎａｌ Ｓｔｒｅｎｇｔｈ Ｉｎｄｉｃａｔｏｒ）、受信電力のデシベル値または真値、ＳＮＲ（Ｓｉｇｎａｌ Ｎｏｉｓｅ Ｒａｔｅ）のいずれか、もしくはこれらのうちの２以上を組み合わせて用いてもよい。計測で交換するパケットは、自端末の識別子と所属するグループの識別子をペイロードに含めていればよい。例えば、ＩＥＥＥ８０２．１１に準ずる無線規格で用いられるデータリンク層（ＭＡＣ：ＭｅｄｅｉａＡｃｃｅｓｓＣｏｎｔｒｏｌ）フレームのヘッダを上記ペイロードに付随してブロードキャストする形態でもよい。

図４は、第一の実施形態における通信品質データ構造の一例である。通信品質データは、例えば、通信データの送信端末の識別子と送信グループ識別子と宛先端末識別子と宛先グループ識別子および通信データに関する通信品質の値を含む。通信状態収集部２１０は、各無線通信端末が相互に通信した通信品質データを図４のデータフォーマットで収集してもよい。収集方法としては、経路生成装置と各無線通信端末が直接通信品質データを送受してもよいし、ＳＤカードなどの外部記憶装置を介して通信品質データを送受してもよい。収集されたデータが集まると、通信状態収集部２１０は接続性指標計算部２２０を呼び出す。

接続性指標計算部２２０は、前記通信状態収集部が収取した無線通信端末間の通信品質データに基づいて、第１中継グループ２０に属する無線通信端末それぞれの、宛先グループ３０に対する接続性を求める（Ｓ３０２）。

接続性指標計算部２２０は、例えば通信状態収集部２１０が収集した通信品質データの送信元無線通信端末識別子を使って、通信品質データをグループごとにソートする。続いて、第１中継グループ２０に含まれる各無線通信端末それぞれの、宛先グループへの接続性を計算する。接続性とは、無線通信端末がデータを送信した際、当該無線通信端末が属するグループと別のグループに所属する１以上の無線通信端末にデータが届く期待値を表し、値が大きいほど送信データの到達を高く期待できる。接続性の計算は、通信品質の値、当該別のグループに属する無線通信端末とのリンク数のいずれか、あるいはこれらの組み合わせにより計算する。接続性を計算する式の一例を以下に示す。

（１）式より、当該別のグル―プとのリンク数が多く、当該別のグループに属する各無線通信端末間の通信品質データが大きい無線通信端末ほど接続性が大きくなる。なお、通信可能な無線通信端末が当該別のグループに存在しない場合、リンク数＝０のため、例えば接続性は０になる。各無線通信端末の接続性を求める。

経路情報生成部２３０は、前記接続性指標計算部２２０が算出した接続性にもとづいて、第１中継グループに属する無線通信端末のうちの一つを第１中継端末（第２の無線通信端末）とすることにより経路情報を生成する（Ｓ３０３、Ｓ３０４）。例えば、第１中継グループに属する無線通信端末のうち、宛先グループに対して最も接続性が高い無線通信端末を第１中継端末とする。

経路情報は、第１中継端末が送信端末から送られた宛先端末宛てのデータを受信した場合に宛先端末へ当該データを転送するための情報である。第１中継端末は、送信端末から直接あるいは間接データを受信する。また、第１中継端末はデータを直接宛先端末へ送信してもよいし、他の中継端末を介して宛先端末へ送信してもよい。第１中継端末に紐付けられた経路情報は、例えば、宛先グループ１０の識別子と送信端末３１の識別子を含む。

通信部２４０は、経路情報生成部２３０に保持される経路情報を受け取り、第１中継端末へ配信する（Ｓ３０５）。通信部は、経路情報を、第１中継端末を含む複数の無線通信端末に配信してもよい。各無線通信端末は、自端末に関する経路情報を受信し記憶する。配信方法は、経路生成装置と各無線通信端末が直接経路情報を送受してもよいし、ＳＤカードなどの外部記憶装置を介して経路情報を送受してもよい。

送信端末３１が宛先端末１１宛てのデータを送信し、第１中継端末２１がこのデータを受信した場合には、第１中継端末２１は宛先端末１１へデータを転送する。第１中継グループ２０に含まれる第１中継端末以外の無線通信端末（２２〜２４）は、送信端末３１からデータを受信しても宛先端末１１へ転送しない。送信グループ１０に含まれる第１中継端末以外の無線通信端末は、送信端末３１からデータを受信しても宛先端末１１へ転送しない。

図５は第一の実施形態に係るマルチホップ無線メッシュネットワークシステムの他の構成例である。

マルチホップ無線メッシュネットワークシステムが、宛先グループ１０と送信グループ３０以外に複数のグループを含み、第１中継端末２１と送信グループがデータ通信できない場合がある。この場合には、第１中継グループに対する接続性に基づいて、宛先グループ１０および第１中継グループに属しない無線通信端末の中から選ばれた１または複数の中継端末を介して送信端末３１と第１中継端末２１がデータ通信する。

図６は、第一の実施形態に係る経路生成装置の処理の他の一例を示すフローチャートである。Ｓ３０１からＳ３０４までは図３と同じである。第１中継端末を設定した後に、第１中継グループへの接続性に基づいて、第Ｎ中継端末を設定する（Ｓ６０１）。第Ｎ中継端末は第Ｎグループに属する。Ｎは２以上の正の整数であり、既に設定されている中継端末の数よりも１大きい値である。図５の例では、第１中継端末が設定されているので、Ｎは２である。第２中継端末４１は第２中継グループ４０に属する。

次に、第Ｎ中継端末を中継端末とする経路情報が生成される（Ｓ６０２）。経路情報は、第２中継端末が送信端末から送られた宛先端末宛てのデータを受信した場合に、第２中継端末が第１中継端末へ当該データを転送するための情報である。第２中継端末は、送信端末から直接あるいは間接データを受信する。具体的には、経路情報は、例えば第Ｎ中継端末に紐付けられた経路情報に、宛先グループ１０の識別子と宛先端末３１の識別子を含む。

第Ｎ中継端末と送信端末が同一グループに属していない場合には（Ｓ６０３のＦ）、Ｎの値をＮ＋１に更新する（Ｓ６０４）。続いて、第（Ｎ−１）中継グループへの接続性に基づいて、第Ｎ中継端末を設定する。例えば、第２中継端末４１が送信端末と同じグループに属していない場合には、Ｎを３として、第２中継グループへの接続性に基づいて第３中継端末を設定する。送信端末と同一グループに属する第Ｎ中継端末が見つかるまで、中継端末の設定と経路情報の生成を繰り返す。

第Ｎ中継端末と送信端末が同一グループに属している場合には（Ｓ６０３のＴ）、第Ｎ中継端末と送信端末は直接通信可能なので、経路情報の生成を終了し、経路情報を配信する（Ｓ６０５）。

このように、経路は送信グループ側ではなく宛先グループ側から順次設定される。１つの経路に複数の中継端末が含まれる場合には、各中継端末が属するグループは異なる。

本実施形態により、宛先端末と送信端末の組み合わせに対して適切な経路情報を生成することができる。本実施形態においては、データ通信の前に経路情報が生成されるため、管理パケットの交換が不要であり、無線帯域を効率よく利用することができる。したがって、無線通信端末間で、遅延なくデータ通信を行うことができる。また、データ通信のパケットロス率を低下させることができるので、無線通信端末間で安定したデータ通信を行うことができる。

なお、事前に設定されるグループ分けの情報の中に、各グループの位置情報が含まれていてもよい。経路情報生成部２３０が中継端末を設定するにあたって、宛先グループに対する送信グループの位置ベクトルと宛先グループに対する中継グループの位置ベクトルのなす角大きい場合には、その中継グループに含まれる無線通信端末が中継端末として選ばれ難いようにバイアスをかけることにより、遠回りの経路が設定されないようにすることができる。

（第一の実施形態の第一変形例）
宛先端末１１と送信端末３１の複数の組み合わせに対応した複数の経路情報を生成する場合を説明する。マルチホップ無線メッシュネットワークシステムに含まれる２つの無線通信端末からなる組合せすべてについて、経路情報を求めてもよい。図７は、第一の実施形態の第一変形例に係る経路生成装置の処理の一例を示すフローチャートである。

まず、通信状態収集部２１０は、マルチホップ無線メッシュネットワークシステム内の無線通信端末同士が相互に通信した通信品質を収集する（Ｓ７０１）。次に、宛先端末１１と送信端末３１の複数の組み合わせのための経路情報の設定を完了していれば（Ｓ７０２のＴ）、経路生成装置２００から無線通信端末に経路情報を配信する（Ｓ７１４）。複数の組み合わせのための経路情報の設定が完了していなければ（Ｓ７０２のＦ）、マルチホップ無線メッシュネットワークシステムに含まれる複数の無線通信端末の、ネットワークシステムに含まれる複数のグループそれぞれへの接続性が計算されたかどうかを判断する（Ｓ７０３）。接続性の計算は、マルチホップ無線メッシュネットワークシステムに含まれるすべての無線通信端末について行われてもよい。

接続性の計算が完了していなければ（Ｓ７０３のＦ）、計算されていない接続性を計算する（Ｓ７０４）。接続性の計算が完了していれば（Ｓ７０３のＴ）、まだ経路情報が設定されていない宛先端末１１と送信端末３１の組み合わせについて、経路情報の設定要否を判断する。具体的には、まだ設定されていない経路情報の１つに関わる宛先端末１１と送信端末３１が直接通信可能であれば、経路情報は作成しないで（Ｓ７０５のＴ）、Ｓ７０２へ戻る。

まだ設定されていない経路情報の１つに関わる宛先端末１１と送信端末３１が直接通信できない場合は（Ｓ７０５のＦ）、宛先端末１１と送信端末３１が同一のグループに属するか否かを判断する（Ｓ７０６）。２つの端末が同一のグループに属する場合には（Ｓ７０６のＴ）、グループ内の無線通信端末は相互に通信可能であるため経路情報は作成しないでＳ７０２へ戻る。

２つの端末が同一のグループに属しない場合には（Ｓ７０６のＦ）、経路情報を作成する。宛先グループへの接続性に基づいて、宛先グループに属しない無線通信端末のうちの１つを第１中継端末と設定する（Ｓ７０７）。第１中継端末に紐付けられた経路情報に宛先グループの識別子と送信元端末の識別子を追加することにより経路情報を生成する（Ｓ７０８）。例えば、宛先グループの識別子と送信元端末の識別子が記されたエントリが経路情報に追加される。その後、第１中継端末が属する第１中継グループが送信グループと同一か否かを判断し、同一である場合、当該２つの無線通信端末における経路情報生成処理を終了し（Ｓ７０９のＴ）、Ｓ７０２へ戻る。

一方、第１中継グループ２０と送信グループ３０が同一でない場合（Ｓ７０９のＦ）、第（Ｎ−１）中継端末にデータを転送するための第Ｎ中継端末を設定する（Ｓ７１０）。第Ｎ中継端末は、第（Ｎ−１）中継グループに対する接続性に基づいて設定される。Ｎは２以上の整数であり、その経路について既に設定されている中継端末の数よりも１大きい値である。ここまでに第１中継端末が設定されているので、Ｎは２である。例えば、第２中継端末は、第１中継グループへの接続性が最も高い無線通信端末である。

第Ｎの無線通信端末に紐付けられた経路情報に宛先グループの識別子と送信端末の識別子が記されたエントリを追加することにより経路情報を生成する（Ｓ７１１）。その後、第Ｎ中継端末が属する第Ｎ中継グループが送信グループと同一か否かを判断し（Ｓ７１２）、同一である場合には経路情報生成処理を終了して（Ｓ７１２のＴ）、Ｓ７０２へ戻る。第Ｎ中継グループと送信グループが異なる場合には（Ｓ７１２のＦ）、Ｎの値を１増やし（Ｓ７１３）、新しい第Ｎ中継端末を設定し（Ｓ７１０）、経路情報を生成する（Ｓ７１１）処理を、送信グループに属する中継端末が設定されるまで繰り返す。例えば、第２中継端末が設定された後に、Ｎを３として第３中継端末が設定される。第３中継端末が属する第３中継グループが送信グループと異なれば、第４中継端末が設定される。

これらの処理を完了することにより、宛先端末１１と送信端末３１の複数の組み合わせすべてに関する経路情報の設定が完了する。例えばマルチホップ無線メッシュネットワークシステムに含まれる、すべての宛先端末と送信端末の組み合わせに関する経路情報を生成することも可能である。

図８は、第一の実施形態の第一変形例に係る経路情報の一例である。マルチホップ無線メッシュネットワークシステム内に複数の経路が設定される場合、１つの無線通信端末が２以上の経路の中継端末として働く場合がある。この場合、この無線通信端末に紐付けられた経路情報には、宛先グループの識別子と送信端末の識別子に関する複数の組み合わせが含まれる。図８において、横に並んだ宛先グループ識別子と送信端末の識別子は１つの組を表す。１つの組に含まれる送信端末から同じ組に含まれる宛先グループ宛てに送信されるデータを受信したときには、当該無線通信端末は中継端末として機能し、次の中継端末にデータを送信する。

本変形例により、宛先端末と送信端末の複数の組み合わせに対して適切な経路情報を生成することができる。本変形例においても、データ通信の前に経路情報が生成されるため、管理パケットの交換が不要であり、無線帯域を効率よく利用することができる。したがって、無線通信端末間で、遅延なくデータ通信を行うことができる。また、データ通信のパケットロス率を低下させることができるので、無線通信端末間で安定したデータ通信を行うことができる。

（第一の実施形態の第二変形例）
第一の実施形態において、宛先端末と第１中継端末が直接通信できない場合も考えられる。この場合、宛先グループ内の端末同士では通信できるため、宛先グループ内のいずれかの無線通信端末が第１中継端末からのデータを再送するように経路情報を生成する方法がある。

図９は、第一の実施形態の第二変形例に係る経路生成装置の処理の一例を示すフローチャートである。図９は図３にＳ９０１〜Ｓ９０３を追加した例である。なお、第１中継端末を決定するまでの処理（Ｓ３０１〜Ｓ３０３）は図３および図６と同じである。第１中継端末を設定し経路情報を生成した後（Ｓ３０４）、第１中継端末と宛先端末が直接通信可能か否かを通信品質データに基づいて判断する（Ｓ９０３）。直接通信が可能であれば（Ｓ９０３のＴ）、図３と同じにＳ３０５の処理を行う。直接通信できない場合には（Ｓ９０３のＦ）、宛先グループに含まれ第１中継端末と直接通信可能な１の無線通信端末を第１アシスト中継端末として設定する（Ｓ９０１）。その後、第１アシスト中継端末に紐付けられた経路情報を生成する（Ｓ９０２）。

経路情報は、第１アシスト中継端末が送信端末から送られた宛先端末宛てのデータを受信した場合に、第１アシスト中継端末が宛先端末へ当該データを転送するための情報である。第１アシスト中継端末に紐付けられた経路情報は、宛先グループの識別子と送信端末の識別子を含む。その後、経路情報を配信する（Ｓ３０５）。

図１０は、第一の実施形態の第二変形例に係る経路生成装置の処理の他の一例を示すフローチャートである。図１０は、図６にＳ９０１〜Ｓ９０６を追加した例である。

第１中継端末に紐付けられた経路情報を生成した後（Ｓ３０４）に、第１中継端末と宛先端末が直接通信可能（Ｓ９０３のＴ）であれば、第Ｎ中継装置の設定を行う（Ｓ６０１）。第１中継端末と宛先端末が直接通信できない場合には（Ｓ９０３のＦ）、宛先グループに含まれ第１中継端末と直接通信可能な１の無線通信端末を第１アシスト中継端末として設定する（Ｓ９０１）。その後、第１アシスト中継端末に紐付けられた経路情報を生成する（Ｓ９０２）。第１アシスト中継端末に紐付けられた経路情報は、宛先グループの識別子と送信端末の識別子を含む。その後、第Ｎ中継装置の設定を行う（Ｓ６０１）。第Ｎ中継端末の経路情報を生成し（Ｓ６０２）、第Ｎ中継端末と第（Ｎ−１）中継端末が直接通信可能かどうか判断する（Ｓ９０４）。直接通信できる場合には、第Ｎ中継端末と送信グループが同一グループに属するかどうかを判断する（Ｓ６０３）。

直接通信できない場合には、第（Ｎ−１）中継グループに含まれ第Ｎ中継端末と直接通信可能な１の無線通信端末を第Ｎアシスト端末として設定する（Ｓ９０５）。その後、第Ｎアシスト中継端末に紐付けられた経路情報を生成する（Ｓ９０６）。第１アシスト中継端末に紐付けられた経路情報は、宛先グループの識別子と送信端末の識別子を含む。その後、直接通信できる場合には、第Ｎ中継端末と送信グループが同一グループに属するかどうかを判断する（Ｓ６０３）。Ｓ６０３以降の説明は図６と同じであるので省略する。送信グループに属する中継端末が設定されるまで、中継端末とアシスト端末の設定を次々に行い、経路情報の生成を次々に行う。

次に、マルチホップ無線メッシュネットワークシステムに複数の経路を設定する場合について説明する。図１１は、第一の実施形態の第二変形例に係る経路生成装置の処理の他の一例を示すフローチャートである。図１１は、図７にＳ９０１〜Ｓ９０６を追加した例である。

第１中継端末に紐付けられた経路情報を生成した後（Ｓ７０８）に、第１中継端末と宛先端末が直接通信可能（Ｓ９０３のＴ）であれば、第Ｎ中継装置の設定を行う（Ｓ７０１）。第１中継端末と宛先端末が直接通信できない場合には（Ｓ９０３のＦ）、宛先グループに含まれ第１中継端末と直接通信可能な１の無線通信端末を第１アシスト中継端末として設定する（Ｓ９０１）。その後、第１アシスト中継端末に紐付けられた経路情報を生成する（Ｓ９０２）。第１アシスト中継端末に紐付けられた経路情報は、宛先グループの識別子と送信端末の識別子を含む。その後、第Ｎ中継装置の設定を行う（Ｓ７１０）。第Ｎ中継端末の経路情報を生成し（Ｓ７１１）、第Ｎ中継端末と第（Ｎ−１）中継端末が直接通信可能かどうか判断する（Ｓ９０４）。直接通信できる場合には、第Ｎ中継端末と送信グループが同一グループに属するかどうかを判断する（Ｓ７１２）。

直接通信できない場合には、第（Ｎ−１）中継グループに含まれ第Ｎ中継端末と直接通信可能な１の無線通信端末を第Ｎアシスト端末として設定する（Ｓ９０５）。その後、第Ｎアシスト中継端末に紐付けられた経路情報を生成する（Ｓ９０６）。第１アシスト中継端末に紐付けられた経路情報は、宛先グループの識別子と送信端末の識別子を含む。その後、直接通信できる場合には、第Ｎ中継端末と送信グループが同一グループに属するかどうかを判断する（Ｓ７１２）。Ｓ７１３以降の説明は図７と同じであるので省略する。送信グループに属する中継端末が設定されるまで、中継端末とアシスト端末の設定を次々に行い、経路情報を次々に生成する。

本変形例により、第１中継端末と宛先端末が直接データ通信できない場合に、第１アシスト端末を介してデータ通信を行うことができる。また、第Ｎ中継端末と第（Ｎ−１）中継端末が直接データ通信できない場合に、第（Ｎ−１）アシスト端末を介してデータ通信を行うことができる。したがって、接続性が高くても宛先端末と直接接続できない場合に当該経路をあきらめなければならない状況を回避でき、送信端末のデータを宛先端末へ安定して届けることが可能な経路を作成できる。

本変形例においても、データ通信の前に経路情報が生成されるため、管理パケットの交換が不要であり、無線帯域を効率よく利用することができる。したがって、無線通信端末間で、遅延なくデータ通信を行うことができる。また、データ通信のパケットロス率を低下させることができるので、無線通信端末間で安定したデータ通信を行うことができる。

（第一の実施形態の第三変形例）
次に図を用いて、第一の実施形態の第三変形例について説明する。

本変形例においては、経路中にある無線通信端末が故障等により動作しなくなる場合に、通信が途絶するのを防止する。

図１２は、第一の実施形態の第三変形例に係る経路生成装置の処理の一例を示すフローチャートである。図１２は、図３のＳ３０３をＳ９１０に、Ｓ３０４をＳ９１１に変更したものである。本変形例においては、接続性の計算をした後（Ｓ３０２）、第１中継グループ内に複数の第１中継端末を設定する。具体的には、まず、宛先グループとの接続性の値が０でない無線通信端末を再送候補リストに保存する。すなわち、再送候補リストに保存される無線通信端末は、宛先グループに含まれる少なくとも一の無線通信端末とデータ通信可能である。中継候補リストは、例えば接続性指標計算部において生成される。次に、中継候補リストに含まれる無線通信端末のうち、宛先グループとの接続性が高い無線通信端末ほど高い優先度を付与する（Ｓ９１０）。そして、優先度が付与された無線通信端末すべて、あるいは優先度の高い複数の無線通信端末の無線通信端末それぞれに紐付けられた経路情報を生成する（Ｓ９１１）。

優先度は、例えば０以上の整数で定義され、値が小さいほど優先度が高いことを表す。第１中継グループに含まれる複数の第１中継端末が他のグループに含まれる無線通信端末からデータを受信すると、優先度が高く設定されている無線通信端末ほど早く宛先グループに受信データを送信する。例えば、複数の第１中継端末は、優先度に応じた、受信と送信の間の待ち時間が設けられていてもよい。

経路情報は、例えば、再送候補リストに保存される無線通信端末が送信端末から送られた宛先端末宛てのデータを受信した場合に、優先度に応じた待ち時間の後に宛先端末へ前記データを転送するための情報である。例えば、経路情報は、例えば宛先グループの識別子、送信端末の識別子、および優先度を含む。

接続性が０でない無線通信端末すべてを中継候補リストに含めると、経路情報が膨大な数になり計算負荷が大きくなる。このため、再送候補リストに保存する無線通信端末数を制限してもよい。

図９のフローチャートに本変形例を適用する場合には、同様にＳ３０３を９１０に置き換え、Ｓ３０４をＳ９１１に置き換える。

図１３は、第一の実施形態の第三変形例に係る経路生成装置の処理の他の一例を示すフローチャートである。図１３は、図６のＳ３０３をＳ９１０に変更し、Ｓ３０４をＳ９１１に変更し、Ｓ７０１をＳ９１２に変更し、Ｓ７０２をＳ９１３に変更したものである。図１２の場合と同様に、Ｓ９０１においては、第１中継グループに接続性に基づいて複数の第１中継端末を設定し、複数の第１中継端末それぞれに接続性に基づく優先度を設定する（Ｓ９１０）。続いて、優先度が付与された無線通信端末すべて、あるいは優先度の高い複数の無線通信端末の無線通信端末それぞれに紐付けられた経路情報を生成する（Ｓ９１１）。第１中継グループに含まれる複数の第１中継端末が他のグループに含まれる無線通信端末からデータを受信すると、優先度が高く設定されている無線通信端末ほど早く宛先グループに受信データを送信する。

同様に、第Ｎ中継グループに接続性に基づいて複数の第Ｎ中継端末を設定し、複数の第Ｎ中継端末それぞれに接続性に基づく優先度を設定する（Ｓ９１２）。続いて、優先度が付与された無線通信端末すべて、あるいは優先度の高い複数の無線通信端末の無線通信端末それぞれに紐付けられた経路情報を生成する（Ｓ９１３）。第Ｎ中継グループに含まれる複数の第Ｎ中継端末が他のグループに含まれる無線通信端末からデータを受信すると、優先度が高く設定されている無線通信端末ほど早く第（Ｎ−１）グループに受信データを送信する。

図１０のフローチャートに本変形例を適用する場合には、同様にＳ３０３を９１０に置き換え、Ｓ３０４を９１１に置き換え、Ｓ７０１をＳ９１２に置き換え、Ｓ７０２を９１３に置き換える。

図１４は、第一の実施形態の第三変形例に係る経路生成装置の処理の他の一例を示すフローチャートである。図１４は、図７のＳ７０７をＳ９１０に変更し、Ｓ７０８をＳ９１１に変更し、Ｓ７１０をＳ９１２に変更し、Ｓ７１１をＳ９１３に変更したものである。

Ｓ９１０〜Ｓ９１３の説明は図１３と同じである。

図１１のフローチャートに本変形例を適用する場合には、同様のＳ７０７をＳ９１０に置き換え、Ｓ７０８をＳ９１１に置き換え、Ｓ７１０をＳ９１２に置き換え、Ｓ７１１をＳ９１３に置き換える。

図１５は、第一の実施形態の第三変形例に係る経路情報の一例である。図１４の例においてマルチホップ無線メッシュネットワークシステム内に複数の経路が設定される場合、１つの無線通信端末が２以上の経路の中継端末として働く場合がある。この場合、この無線通信端末に紐付けられた経路情報には、宛先グループの識別子と送信端末の識別子と優先度に関する複数の組み合わせが含まれる。図１５において、横に並んだ宛先グループ識別子と送信端末の識別子と優先度は１つの組を表す。図１５において経路情報は３つの組を含む。１の組に含まれる送信端末からこれと同じ組に含まれる宛先グループに送信されるデータを受信したときには、当該無線通信端末は中継端末として機能し、優先度に従った待ち時間の後に次の中継端末にデータを送信する。

本変形例により、複数の冗長経路が形成されるため、マルチホップ無線メッシュネットワークシステムに含まれる一部の無線通信端末が故障により動作しなくなったとしても安定した通信が可能になる。

本変形例においても、データ通信の前に経路情報が生成されるため、管理パケットの交換が不要であり、無線帯域を効率よく利用することができる。したがって、無線通信端末間で、遅延なくデータ通信を行うことができる。また、データ通信のパケットロス率を低下させることができるので、無線通信端末間で安定したデータ通信を行うことができる。

（第二の実施形態における実施例）
経路生成装置が複数の無線通信端末にモジュールとして組み込まれている場合について説明する。図１６は、第二の実施形態に係る経路生成装置の構成例である。本実施形態では各無線通信端末が他のすべての無線通信端末の識別子と各無線通信端末が属するグループについて把握していることを前提にする。すなわち、マルチホップ無線メッシュネットワークは少なくとも、送信グループと、宛先端末を含む宛先グループと、複数の無線通信端末を含む中継グループとを含み、複数の無線通信端末それぞれに経路生成装置が備えられる。

複数の無線通信端末が相互に通信し、それぞれの無線通信端末が備える経路生成装置２００に含まれる通信状態収集部２１０が通信品質データを収集する。第一の実施形態と異なり、一の無線通信端末と直接データ通信可能な他の無線通信端末との通信品質データが、その無線通信端末が備える通信状態収集部２１０に収集される。接続性指標計算部２２０は、収集した通信品質データをもとに、当該無線通信端末の他グループへの接続性を計算する。計算した接続性は、経路情報生成部２３０に送られる。

次に、接続性指標計算部２２０が通信部２４０を呼び出し、通信部２４０が他の無線通信端末とのデータ送受を行う。

マルチホップ無線メッシュネットワークシステムに含まれる一の無線通信端末から他の無線通信端末へ、経路生成依頼を送信する。経路生成依頼が送られる他の無線通信端末は、複数であってもよい。経路生成依頼には、宛先端末となる無線通信端末が所属するグループと送信端末となる無線通信端末の識別子が含まれる。経路生成依頼を受信した無線通信端末は、周囲の他の無線通信端末と、通信部２４０を介して、接続性指標計算部２２０が算出した接続性を交換する。通信部２４０は、さらに前記接続性指標計算部２２０が算出した接続性の指標も配信してもよい。

続いて、通信部２４０が取得した他の無線通信装置の接続性は、経路情報生成部２３０に送られる。交換により受信した他の無線通信端末の接続性は経路生成部に伝えられ、当該無線通信端末が第１中継端末になるか否かを判断する。

判断は、自端末の接続性と、周囲の他の無線通信端末の接続性を比較することにより行われる。自端末の宛先グループに対する接続性が、他の無線通信端末の宛先グループに対する接続性よりも大きい場合には、自端末を第１中継端末とする判断をする。自端末が保持する経路情報に、宛先グループの識別子と送信端末の識別子が記されたエントリを追加する。さらに、第一の実施形態の第三変形例のように、接続性に基づく優先度を経路情報に含めてもよい。

第１中継端末になると判断した無線通信端末は、依頼元無線通信端末から受信した経路生成依頼を他の無線通信装置へ再送する。一方、自端末の宛先グループに対する接続性が、他の無線通信端末の宛先グループに対する接続性よりも小さい場合には、一度経路生成処理を実行したことを表すフラグを立て、経路情報生成処理を終了する。

新たな経路生成依頼が再送されなくなるまで、上記処理を繰り返すことで複数の経路情報を生成することができる。

図１７は、第二の実施形態に係る経路生成装置の処理の一例を示すフローチャートである。まず、通信状態収集部２１０が通信品質データを収集する（Ｓ７０１）。次に、接続性指標計算部２２０は、収集した通信品質データをもとに、例えば、当該無線通信端末とすべての他グループとの接続性を計算したか否かを判断し、すべての他グループとの接続性が計算されていなければ（Ｓ７０３のＦ）、まだ計算されていない他グループとの接続性を計算する（Ｓ７０４）。すべての他グループとの接続性が計算されていれば（Ｓ７０３のＴ）、経路情報生成部２３０の経路生成処理済みを表すフラグを偽に設定する（Ｓ９２０）。その後、他の無線通信装置から経路生成依頼を受信するまで待機し（Ｓ９２１）、一定の時間以内に他の無線通信装置から経路生成依頼を受信しなければ（Ｓ９２２のＦ）、経路生成処理を終了する。

一方、一定の時間以内に他の無線通信装置から経路生成依頼を受信した場合には（Ｓ９２２のＴ）、経路生成処理済みを表すフラグが真か否かを判断し、真であれば（Ｓ９２３のＴ）、Ｓ９２０に戻る。

経路生成処理済みを表すフラグが偽であれば（Ｓ９２３のＦ）、周囲の他の無線通信端末を介して互いの接続性を交換する（Ｓ９２４）。続いて、端末と経路生成依頼に含まれる宛先グループとの接続性が他の無線通信端末と宛先グループとの接続性よりも大きい場合には（Ｓ９２５のＴ）、経路情報生成部２３０に保持される経路情報に宛先グループの識別子と送信端末の識別子を含むエントリを追加する（Ｓ９２６）。その後、他の無線通信端末に経路生成依頼を再送し（Ｓ９２７）、経路生成処理済みを表すフラグを真に設定してＳ９２０に戻る。自端末と経路生成依頼に含まれる宛先グループとの接続性が他の無線通信端末と宛先グループとの接続性よりも大きい場合には（Ｓ９２５のＦ）、Ｓ９２８の処理を行った後にＳ９２０に戻る。

上記処理を複数の無線通信端末が実行することで経路生成が可能である。

本実施形態においても、データ通信の前に経路情報が生成されるため、管理パケットの交換が不要であり、無線帯域を効率よく利用することができる。したがって、無線通信端末間で、遅延なくデータ通信を行うことができる。また、データ通信のパケットロス率を低下させることができるので、無線通信端末間で安定したデータ通信を行うことができる。

上記の実施形態および変形例では、接続性をメトリックに経路情報を生成したが、マルチホップ無線メッシュネットワークにおいては、接続性だけでなく再送を行う回数であるホップ数、あるいは接続性とホップ数の両方を用いて経路情報を生成することも可能である。ホップ数を用いた場合、第３の無線通信端末と第１の無線通信端末における通信回数が最小になるため、通信遅延が最小な経路を生成することができる。

（第三の実施形態）
図１８は、一実施形態に係るハードウェア構成の一例を示すブロック図である経路生成装置は、プロセッサ４１、主記憶装置４２、補助記憶装置４３、通信装置４４、デバイスインタフェース４５を備え、これらがバス４６を介して接続された、コンピュータ装置として実現できる。

プロセッサ４１が、補助記憶装置４３からプログラムを読み出して、主記憶装置４２に展開して、実行することで、通信状態収集部２１０、接続性指標計算部２２０、経路情報生成部２３０、通信部２４０の機能を実現することができる。

本実施形態の経路生成装置は、実行されるプログラムをコンピュータ装置に予めインストールすることで実現してもよいし、プログラムをＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介してコンピュータ装置に適宜インストールすることで実現してもよい。

主記憶装置４２は、プロセッサ４１が実行する命令、および各種データ等を一時的に記憶するメモリ装置であり、ＤＲＡＭ等の揮発性メモリでも、ＭＲＡＭ等の不揮発性メモリでもよい。補助記憶装置４３は、プログラムやデータ等を永続的に記憶する記憶装置であり、例えば、ＨＤＤまたはＳＳＤ等がある。

ネットワークインタフェース４４は、通信ネットワークに接続するためのインタフェースである。無線機器２との通信は、このネットワークインタフェース４４にて実現してもよい。ここではネットワークインタフェースを１つのみ示しているが、複数のネットワークインタフェースが搭載されていてもよい。

デバイスインタフェース４５は、外部装置５などの機器に接続するインタフェースである。入力部１１、出力部１７は、外部装置としてデバイスインタフェース４５に接続されてもよい。

以上、具体例を参照しつつ、本発明の実施の形態について説明した。しかし、本発明の実施形態は、これらの具体例に限定されるものではない。

また、各具体例のいずれか２つ以上の要素を技術的に可能な範囲で組み合わせたものも、本発明の要旨を包含する限り本発明の範囲に含まれる。

その他、本発明の思想の範疇において、当業者であれば、各種の変更例及び修正例に想到し得るものであり、それら変更例及び修正例についても本発明の範囲に属するものと了解される。

10・・・第１のグループ、20・・・第２のグループ、30・・・第３のグループ、101〜104・・・無線通信端末、101〜104・・・無線通信端末、101〜104・・・無線通信端末、２１０・・・通信状態収集部、２２０・・・接続性指標計算部、２３０・・・経路情報生成部、２４０・・・通信部

Claims (9)

1. 送信端末と、宛先端末を含む宛先グループと、複数の第１無線通信端末を含む第１中継グループと、を有するマルチホップ無線メッシュネットワークにおいて、前記宛先グループとの接続性に基づいて、前記第１中継グループに含まれる複数の第１無線通信端末のうちの一つを第１中継端末として設定し、前記第１中継端末が前記送信端末から送られた前記宛先端末宛てのデータを受信した場合に前記宛先端末へ前記データを転送するための第１経路情報を生成する生成部と、
   前記第１経路情報を前記第１中継端末へ配信する通信部と、
   を備える経路情報生成装置。
2. 前記生成部は、前記第１無線通信端末のうち前記宛先グループとの接続性が最も高いものを前記第１中継端末と設定する、請求項１に記載の経路情報生成装置。
3. 前記マルチホップ無線メッシュネットワークはさらに複数の第２無線通信端末を含む第２中継グループを含み、
   前記生成部は、前記第１中継グループとの接続性に基づいて、前記第２中継グループに含まれる複数の第２無線通信端末のうちの一つを第２中継端末として設定し、前記第２中継端末が前記送信端末から送られた前記宛先端末宛ての前記データを受信した場合に前記第１中継端末へ前記データを転送するための第２経路情報を生成し、
   前記通信部は、前記第２経路情報を前記第２中継端末へ送信する、
   請求項１または２に記載の経路情報生成装置。
4. 前記宛先グループは、前記宛先端末に加えて、前記宛先端末および前記第１中継端末と直接データ通信可能な第３中継端末を含み、
   前記生成部は、前記第３中継端末が前記送信端末から送られた前記宛先端末宛ての前記データを受信した場合に前記宛先端末へ前記データを転送するための第３経路情報を生成し、
   前記通信部は、前記第３経路情報を前記第３中継端末へ送信する、
   請求項１〜３のいずれかに記載の経路情報生成装置。
5. 前記生成部は、前記宛先グループとの接続性に基づいて、複数の第１無線通信端末それぞれに優先度を設定し、
   前記生成部は、複数の前記第１無線通信端末が前記送信端末から送られた前記宛先端末宛てのデータを受信した場合に前記優先度に応じた待ち時間の後に前記宛先端末へ前記データを転送するための第１経路情報を生成し、
   前記通信部は、前記第１経路情報を複数の前記第１無線通信端末へ送信する、
   請求項１〜４のいずれかに記載の経路情報生成装置。
6. 前記宛先端末と前記複数の無線通信端末との間の通信品質を取得する通信状態収集部と、
   前記通信状態から、前記複数の無線通信端末の前記宛先グループとの接続性を求める接続性指標計算部と、
   をさらに備える請求項１〜５のいずれかに記載の経路生成装置。
7. マルチホップ無線メッシュネットワークが有する、送信端末と、宛先端末を含む宛先グループと、複数の無線通信端末を含む中継グループと、のうちの一の前記無線通信端末に備えられる経路生成装置であって、
   他の前記無線通信端末と前記宛先グループとの第１接続性を取得する通信部と、
   自無線通信端末と前記宛先グループとの第２接続性が前記第１接続性よりも大きいならば、前記第１中継端末が前記送信端末から送られた前記宛先端末宛てのデータを受信した場合に前記宛先端末へ前記データを転送するための第１経路情報を生成する生成部と、
   を備える経路生成装置。
8. 請求項１または２に記載の経路生成装置と、
   前記送信端末と、
   前記宛先端末を含む前記宛先グループと、
   前記複数の第１無線通信端末を含む前記第１中継グループと、
   を有するマルチホップ無線メッシュネットワークシステム。
9. 請求項７に記載の経路生成装置を備える複数の無線通信端末と、
   送信端末と、
   宛先端末を含む宛先グループと、
   を含むマルチホップ無線メッシュネットワークシステム。

Images