(57)【要約】【課題】多数のノードにより構成される無線マルチホップネットワークにおいて、距離情報に基づいて通信経路を制御する場合に、無線通信路のトラフィックを抑えると共に、各ノードが必要な記憶容量を小さくするための通信経路制御方法を提供する。【解決手段】無線マルチホップネットワークにおいて、各ノードは、ある２つの基準ノード間の距離、自ノードから２つの基準ノードまでの距離、及び隣接ノードから前記２つの基準ノードまでの距離を経路情報テーブルとして保持し、ノード間の通信パケットは経路制御情報として、パケットのホップ数、データを最初に送信する発信源ノードから２つの基準ノードまでの距離、及び各ノードの送信先ノードＩＤを示す送信先ノードＩＤリストを含み、パケットを受信したノードは隣接ノードに中継送信する際に、パケット内の経路制御情報、及びノードが保持する経路情報テーブルより、パケットの中継の可否を判断する。【選択図】図１３
2007104320.tif 000002
【特許請求の範囲】
【請求項１】
複数のネットワークノード間で情報をデータパケットとして送受信する無線マルチホップネットワークで用いられる通信経路制御方法であって、
前記複数のネットワークノードの内、第１の基準ノードとなるネットワークノードを予め決定し、前記第１の基準ノードからブロードキャストパケットを送信するステップと、
前記第１の基準ノードから送信されたブロードキャストパケットを受信したネットワークノードが、前記ブロードキャストパケットを中継したネットワークノードを隣接ノードとして登録するステップと、
前記第１の基準ノードから送信されたブロードキャストパケットを受信したネットワークノードが、受信した複数のブロードキャストパケットのホップ数の内、最小のホップ数を自ノードから前記第１の基準ノードまでの距離として登録し、前記自ノードから前記第１の基準ノードまでの距離の情報を前記第１の基準ノードに通知するステップと、
前記第１の基準ノードが、前記ネットワークノードから通知された複数の前記自ノードから前記第１の基準ノードまでの距離の情報に基づいて、前記第１の基準ノードから最も遠い位置にあるネットワークノードの１つを第２の基準ノードとして決定し、前記第２の基準ノードとして決定したネットワークノードに前記第２の基準ノードに決定したことを通知するステップと、
前記第１の基準ノードが、他の前記複数のネットワークノードに前記第１の基準ノードと前記第２の基準ノード間の距離を通知するステップと、
前記複数のネットワークノードが、前記第１の基準ノードから通知された前記第１の基準ノードと前記第２の基準ノード間の距離を登録するステップと、
前記第２の基準ノードからブロードキャストパケットを送信するステップと、
前記第２の基準ノードから送信されたブロードキャストパケットを受信したネットワークノードが、受信した複数のブロードキャストパケットのホップ数の内、最小のホップ数を前記自ノードから前記第２の基準ノードまでの距離として登録し、前記自ノードから前記第２の基準ノードまでの距離及び前記自ノードから前記第１の基準ノードまでの距離の情報を前記隣接ノードに通知するステップと、
前記複数のネットワークノードのそれぞれが、隣接ノードから通知された情報を登録するステップと、
前記複数のネットワークノードのそれぞれが、前記登録した情報に基づいて、複数のネットワークノード間の前記データパケットの中継制御を行うステップとを備えたことを特徴とする通信経路制御方法。
【請求項２】
複数のネットワークノード間で情報をデータパケットとして送受信する無線マルチホップネットワークで用いられる通信経路制御方法であって、
前記複数のネットワークノードが、予め決定された第１の基準ノードとなるネットワークノードから、前記第１の基準ノードから最も遠い位置にある第２の基準ノードとなるネットワークノードまでの距離の情報、自ノードから前記第１の基準ノードまでの距離の情報、前記自ノードから前記第２の基準ノードまでの距離の情報、隣接ノードを識別する情報、前記隣接ノードから前記第１の基準ノードまでの距離の情報、前記隣接ノードから前記第２の基準ノードまでの距離の情報を登録するステップと、
前記複数のネットワークノードが、前記データパケットを送信する際、前記データパケットに、前記自ノードから前記第１の基準ノードまでの距離の情報、前記自ノードから前記第２の基準ノードまでの距離の情報、及び送信先ノードリストの情報を格納し、前記送信先の情報に基づいて、全ての前記隣接ノードに前記データパケットを送信するステップと、
前記データパケットを受信した前記ネットワークノードが、前記ネットワークノードに登録した情報及び前記データパケットに格納された情報に基づいて、複数のネットワークノード間の前記データパケットの中継制御を行うステップとを備えたことを特徴とする通信経路制御方法。
【請求項３】
複数のネットワークノード間で情報をデータパケットとして送受信する無線マルチホップネットワークで用いられる通信経路制御方法であって、
前記複数のネットワークノードが、予め決定された第１の基準ノードとなるネットワークノードから、前記第１の基準ノードから最も遠い位置にある第２の基準ノードとなるネットワークノードまでの距離の情報、自ノードから前記第１の基準ノードまでの距離の情報、前記自ノードから前記第２の基準ノードまでの距離の情報、隣接ノードを識別する情報、前記隣接ノードから前記第１の基準ノードまでの距離の情報、前記隣接ノードから前記第２の基準ノードまでの距離の情報を登録するステップと、
前記複数のネットワークノードが、前記データパケットを中継する際、前記ネットワークノードに登録した情報、及び前記データパケットに格納された前記データパケットの発信源ノードから前記第１の基準ノードまでの距離の情報、前記発信源ノードから前記第２の基準ノードまでの距離の情報、送信先ノードリストの情報、及び前記データパケットを中継した発信元ノードの情報に基づいて、前記自ノードと、前記第１の基準ノード、前記第２の基準ノード、及び前記隣接ノードとの位置関係に基づいて、前記データパケットの送信先ノードを選択するステップとを備えたことを特徴する通信経路制御方法。
【請求項４】
請求項３記載の通信経路制御方法において、
前記データパケットの送信先ノードを選択するステップは、前記データパケットに格納された送信先ノードリストに含まれる前記自ノードの隣接ノードに対して前記データパケットの送信先ノードとして選択しないことを特徴とする通信経路制御方法。
【請求項５】
請求項３記載の通信経路制御方法において、
前記データパケットの送信先ノードを選択するステップは、前記データパケットのポップ数の情報が、前記データパケットに格納された送信先ノードリストに含まれる前記データパケットの発信源ノードから前記第１の基準ノードまでの距離の情報と前記ネットワークノードに登録した前記隣接ノードから前記第１の基準ノードまでの距離の情報の和以上となる前記自ノードの隣接ノードに対して前記データパケットの送信先ノードとして選択しないことを特徴とする通信経路制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線マルチホップネットワーク内の任意の１ノードからネットワーク内の全てのノードへ情報を伝送する通信経路制御方法に関し、特に距離情報に基づく経路制御に適用して有効な技術に関するものである。
【背景技術】
【０００２】
無線ネットワークは有線ネットワークのような物理的な接続が不要であり拡張容易性、接続容易性などのユーザメリットが多いことから広く利用されるようになってきている。
【０００３】
無線ネットワークは、あるノードから１ホップのみ有効なパケットを送信するシングルホップのネットワークと、受信したパケットを中継送信するようなマルチホップのネットワークに分類され、一斉同報通信、所謂ブロードキャスト通信及び、１対１の通信、所謂ユニキャスト通信を実現する方法はそれぞれ異なる。特に無線マルチホップネットワークにおける通信方法は、有線ネットワークやシングルホップの無線ネットワークの技術をそのまま利用することはできないため、技術開発が必要である。
【０００４】
無線マルチホップネットワークにおいてブロードキャストを実現する方法として、所謂フラッディングがあるが、この方法ではブロードキャストパケットを受信した全てのノードが隣接ノードに対してブロードキャストパケットを中継送信するため、同一のブロードキャストパケットを重複受信する可能性が高く、通信トラフィックが増加する。
【０００５】
この課題を解決する技術の１つとして、特開２００３−８５９１号公報（特許文献１）に開示される技術がある。ここで当該技術を、図１４を用いて簡単に説明する。図１４は特許文献１のネットワーク構成の一例を示す図である。
【０００６】
まず、当該技術の無線マルチホップネットワークの構成、各ノードが保持する情報及び、無線マルチホップネットワーク内のノード間で送受信されるパケットについて説明する。
【０００７】
図１４において、無線マルチホップネットワーク１４００は、ノードＡ１４０１〜ノードＦ１４０６から構成され、各ノード１４０１〜１４０６は、それぞれ経路情報テーブル１４０７を保持している。図１４に示す例では、ノードＤ１４０４が保持する内容を例示している。
【０００８】
経路情報テーブル１４０７は、当該ノードの全ての隣接ノードＩＤ１４０８に対して、当該隣接ノードから無線マルチホップネットワーク１４００内の全てのノードＩＤ１４０９までの距離１４１０を記録している。ノードＤ１４０４を例にとると、全ての隣接ノードはノードＢ１４０２、ノードＥ１４０５、ノードＦ１４０６であり、これら３つから無線マルチホップネットワーク１４００内の全てのノードまでの距離を記録している。
【０００９】
また、無線マルチホップネットワーク１４００内のノード間で送受信されるパケット１４１３には、パケットを最初に送信するノードである発信源ノードを特定するノードＩＤ及び、現在の中継回数が格納される。ここでは、パケット１４１３として、発信源ノードＩＤがＡで、中継回数が２のパケットを例示している。
【００１０】
次に、当該技術のブロードキャストパケットの送信方法を説明する。
【００１１】
まず、発信源ノードをノードＡ１４０１とし、ノードＤ１４０４がノードＢ１４０２からパケットを受信した場合、ノードＤ１４０４は、経路情報テーブル１４０７の情報に基づいて、隣接ノードＥ１４０５から発信源ノードのノードＡ１４０１までの距離１４１１及び隣接ノードＦ１４０６から発信源ノードのノードＡ１４０１までの距離１４１２と前記受信パケット１４１３に格納されている中継回数を比較する。
【００１２】
発信源ノードから隣接ノードまでの距離が受信パケットの中継回数よりも大きい場合、当該隣接ノードに中継送信する。それ以外の場合は他ノードからパケットを受信していると推定し、中継送信しない。したがって、図１４に示す例では、ノードＤ１４０４はノードＦ１４０６のみに中継送信する。
【００１３】
以上により、特許文献１で開示される技術は、重複通信を防ぎフラッディングよりも通信トラフィックを削減した無線通信を提供可能である。
【特許文献１】特開２００３−８５９１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、上述した特許文献１で開示される技術では、無線マルチホップネットワーク内のノード間の位置関係を把握するために、各ノードが無線マルチホップネットワーク内のノード総数に比例したサイズの経路情報テーブルを保持する必要がある。したがって、多数のノードにより構成される無線マルチホップネットワークの場合、非常に大容量の記憶領域が必要になる。
【００１５】
そこで、本発明の目的は、多数のノードで構成される無線マルチホップネットワークにおいて、無線マルチホップネットワーク内のある１ノードから全ノードへデータを伝送する場合に、フラッディングによるブロードキャスト通信よりも通信トラフィックを削減すると共に、各ノードが必要な記憶容量を小さくすることのできる通信経路制御方法を提供することにある。
【課題を解決するための手段】
【００１６】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次のとおりである。
【００１７】
本発明による通信経路制御方法は、複数のネットワークノード間で情報をデータパケットとして送受信する無線マルチホップネットワークで用いられる通信経路制御方法であって、複数のネットワークノードの内、第１の基準ノードとなるネットワークノードを予め決定し、第１の基準ノードからブロードキャストパケットを送信するステップと、第１の基準ノードから送信されたブロードキャストパケットを受信したネットワークノードが、ブロードキャストパケットを中継したネットワークノードを隣接ノードとして登録するステップと、第１の基準ノードから送信されたブロードキャストパケットを受信したネットワークノードが、受信した複数のブロードキャストパケットのホップ数の内、最小のホップ数を自ノードから第１の基準ノードまでの距離として登録し、自ノードから第１の基準ノードまでの距離の情報を第１の基準ノードに通知するステップと、第１の基準ノードが、ネットワークノードから通知された複数の自ノードから第１の基準ノードまでの距離の情報に基づいて、第１の基準ノードから最も遠い位置にあるネットワークノードの１つを第２の基準ノードとして決定し、第２の基準ノードとして決定したネットワークノードに第２の基準ノードに決定したことを通知するステップと、第１の基準ノードが、他の複数のネットワークノードに第１の基準ノードと第２の基準ノード間の距離を通知するステップと、複数のネットワークノードが、第１の基準ノードから通知された第１の基準ノードと第２の基準ノード間の距離を登録するステップと、第２の基準ノードからブロードキャストパケットを送信するステップと、第２の基準ノードから送信されたブロードキャストパケットを受信したネットワークノードが、受信した複数のブロードキャストパケットのホップ数の内、最小のホップ数を自ノードから第２の基準ノードまでの距離として登録し、自ノードから第２の基準ノードまでの距離及び自ノードから第１の基準ノードまでの距離の情報を隣接ノードに通知するステップと、複数のネットワークノードのそれぞれが、隣接ノードから通知された情報を登録するステップと、複数のネットワークノードのそれぞれが、登録した情報に基づいて、複数のネットワークノード間のデータパケットの中継制御を行うステップとを備えたものである。
【００１８】
また、本発明による通信経路制御方法は、複数のネットワークノード間で情報をデータパケットとして送受信する無線マルチホップネットワークで用いられる通信経路制御方法であって、複数のネットワークノードが、予め決定された第１の基準ノードとなるネットワークノードから、第１の基準ノードから最も遠い位置にある第２の基準ノードとなるネットワークノードまでの距離の情報、自ノードから第１の基準ノードまでの距離の情報、自ノードから第２の基準ノードまでの距離の情報、隣接ノードを識別する情報、隣接ノードから第１の基準ノードまでの距離の情報、隣接ノードから第２の基準ノードまでの距離の情報を登録するステップと、複数のネットワークノードが、データパケットを送信する際、データパケットに、自ノードから第１の基準ノードまでの距離の情報、自ノードから第２の基準ノードまでの距離の情報、及び送信先ノードリストの情報を格納し、送信先の情報に基づいて、全ての隣接ノードにデータパケットを送信するステップと、データパケットを受信したネットワークノードが、ネットワークノードに登録した情報及びデータパケットに格納された情報に基づいて、複数のネットワークノード間のデータパケットの中継制御を行うステップとを備えたものである。
【００１９】
また、本発明による通信経路制御方法は、複数のネットワークノード間で情報をデータパケットとして送受信する無線マルチホップネットワークで用いられる通信経路制御方法であって、複数のネットワークノードが、予め決定された第１の基準ノードとなるネットワークノードから、第１の基準ノードから最も遠い位置にある第２の基準ノードとなるネットワークノードまでの距離の情報、自ノードから第１の基準ノードまでの距離の情報、自ノードから第２の基準ノードまでの距離の情報、隣接ノードを識別する情報、隣接ノードから第１の基準ノードまでの距離の情報、隣接ノードから第２の基準ノードまでの距離の情報を登録するステップと、複数のネットワークノードが、データパケットを中継する際、ネットワークノードに登録した情報、及びデータパケットに格納されたデータパケットの発信源ノードから第１の基準ノードまでの距離の情報、発信源ノードから第２の基準ノードまでの距離の情報、送信先ノードリストの情報、及びデータパケットを中継した発信元ノードの情報に基づいて、自ノードと、第１の基準ノード、第２の基準ノード、及び隣接ノードとの位置関係に基づいて、データパケットの送信先ノードを選択するステップとを備えたものである。
【００２０】
具体的には、本発明では下記のような通信アルゴリズムを提供している。受信したパケットを隣接ノードへ中継送信する無線マルチホップネットワークにおいて、各ノードが保持する経路情報テーブルサイズを抑えるため、予め決定しておいた無線マルチホップネットワーク内の１つの基準ノードから最も遠い位置にある基準ノードを無線マルチホップネットワークの構成状況から判断して１つ決定する。
【００２１】
各ノードが保持する経路情報テーブルには無線マルチホップネットワーク内の２つの基準ノード及び、隣接ノードに関する情報のみ記録し、無線マルチホップネットワーク内の全ノードの位置関係を把握するのではなく、自ノード近傍のネットワークトポロジ概況を把握するようにする。
【００２２】
また、単純なブロードキャスト通信よりも通信トラフィックを削減するため、無線マルチホップネットワーク内のノード間で送受信されるパケット内に、最初にパケットを送信した発信源ノードの位置を示す情報、同じ送信元から同一パケットを受信する隣接ノードを特定できる情報及び、現在のパケットの中継送信回数を判断できる情報を経路制御情報として追加し、各ノードは受信したパケットの経路制御情報及び、自ノード内に保持する経路情報テーブルを基に、以下の条件に従って隣接ノードの中からノードを限定して中継送信を行なうようにする。
【００２３】
全ての隣接ノードの中から中継送信先となるノードを判断するとき、受信パケットの経路制御情報により受信パケットの送信元ノードから同一パケットを受信する隣接ノードを判断することができる。
【発明の効果】
【００２４】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【００２５】
本発明によれば、各ノードが保持する経路情報テーブルを隣接ノード数のみに依存したサイズに抑えることができると共に、フラッディングのような単純なブロードキャストよりも通信トラフィックを削減することができる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００２７】
＜無線マルチホップネットワークの構成＞
図１〜図３により、本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの構成について説明する。図１は本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの構成を示す構成図、図２は本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークを構成する各ノードが保持する経路情報テーブルの構成を示す構成図、図３は本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワーク内のノード間で送受信されるパケット構成の一例を示す図である。
【００２８】
図１において、無線マルチホップネットワーク２００は、基準ノードＸ２０１、基準ノードＹ２０２、ノードＡ２０３、ノードＢ２０４、ノードＣ２０５、ノードＤ２０６、ノードＥ２０７、ノードＦ２０８、ノードＧ２０９、ノードＨ２１０、ノードＩ２１１から構成され、無線マルチホップネットワーク２００を構成する各ノードは個別ノードＩＤを持っている。
【００２９】
基準ノードＸ２０１は、無線マルチホップネットワーク２００内の全ノードの中からネットワーク管理者によって予め一つ決定され、基準ノードＹ２０２は無線マルチホップネットワーク２００の接続状況に依存し、基準ノードＸ２０１から最も離れたノードの中から任意に一つ決定される。
【００３０】
また、図１の２１２で示す接続は、ネットワーク管理者が予め設定する閾値を越えた電界強度状態にある通信可能範囲内のノード間の無線リンクによる接続を示し、他のノード間を結ぶ結線も同様に無線リンクによる接続を示す。
【００３１】
無線リンクにより接続しているノード間の距離を１とし、自ノードから距離が１であるノードを隣接ノードと呼ぶ。例えば、自ノードをノードＤ２０６とした場合、隣接ノードはノードＡ２０３、及びノードＣ２０５である。
【００３２】
本実施の形態の無線マルチホップネットワーク２００は受信したパケットを隣接ノードへ中継送信するようなネットワークであり、以下、無線マルチホップネットワーク２００を構成するノードを、パケットを最初に送信するノードを示す「発信源ノード」、発信源ノードが最終的にデータを伝送したいノードを示す「最終送信先ノード」、受信したパケットを中継送信するノードを示す「送信元ノード」、及び中継送信する宛先のノードを示す「送信先ノード」に区別する。
【００３３】
図２において、無線マルチホップネットワーク２００を構成する各ノードが保持する経路情報テーブル３００は、無線マルチホップネットワーク２００を構成するあるノードから基準ノードまでの距離情報を記録し、基準ノード間の距離３０１、自ノードから２つの基準ノードまでの距離３０２、及び隣接ノードから２つの基準ノードまでの距離３０３の３種類のエントリにより構成される。
【００３４】
基準ノード間の距離３０１は１種類の距離情報、自ノードから２つの基準ノードまでの距離３０２は２種類の距離情報、隣接ノードから２つの基準ノードまでの距離３０３は２種類の距離情報から構成される。
【００３５】
また、各ノードを特定するためのノードＩＤとしては、無線マルチホップネットワーク２００内で一意に決まるものであれば、どのようなＩＤを用いてもよく、例えば、無線マルチホップネットワーク２００で利用されるＭＡＣアドレスのような、メーカＩＤと製品番号を用いている。
【００３６】
また、基準ノードを特定するための基準ノードＩＤとしては、各ノードが持つノードＩＤとは別に、予め無線マルチホップネットワーク２００内で基準ノードであることを認識するためのＩＤとして設定されており、基準ノードに指定されたノードは、基準ノードＩＤを自ノードＩＤとして設定してパケットの送信などを行うようになっている。
【００３７】
また、隣接ノードから２つの基準ノードまでの距離３０３を全ての隣接ノードに関して保持するため、無線マルチホップネットワーク２００を構成する各ノードが保持する経路情報テーブル３００の距離情報の総数は、基準ノード間の距離３０１と自ノードから２つの基準ノードまでの距離３０２の「３つ」の距離情報と、隣接ノード数分の隣接ノードから２つの基準ノードまでの距離３０３の「２×隣接ノード数」の距離情報の合計で、「３＋２×隣接ノード数」となる。
【００３８】
以上より、本実施の形態の経路情報テーブル３００の経路情報テーブルサイズは、ノード総数には依存しないため、多数のノードで構成されるネットワークにおいても隣接ノード数のみに依存した小さなテーブルサイズの実現が可能である。
【００３９】
図３において、図３（ａ）に示すパケット４００は無線マルチホップネットワーク２００の各ノードが送受信するパケットである。
【００４０】
図３（ａ）の４０１から４０３がパケット４００を構成する情報であり、ヘッダ４０１には利用する通信プロトコルのヘッダ情報が、メッセージデータ４０３は発信源ノードが送信したいメッセージデータが格納される。尚、ヘッダ４０１が利用する通信プロトコルは任意であり、特に限定はない。
【００４１】
経路制御情報４０２は、図３（ｂ）に示すように、発信源ノードから基準ノードＸまでの距離４０４、発信源ノードから基準ノードＹまでの距離４０５、ホップ数４０６、送信元ノードＩＤ４０７、送信先ノードＩＤリスト４０８及び、最終送信先ノードＩＤ４０９から構成される。
【００４２】
ホップ数４０６には、発信源ノードから送信されたパケットの送信或いは、中継送信された回数が格納され、発信源ノードから送信される場合のホップ数は１である。
【００４３】
送信元ノードＩＤ４０７にはパケットを送信或いは、中継送信したノードを特定するノードＩＤが格納される。
【００４４】
送信先ノードＩＤリスト４０８には各ノードが同一パケットを送信或いは、中継送信する隣接ノードＩＤのリストが格納される。
【００４５】
最終送信先ノードＩＤ４０９には、発信源ノードが最終的にメッセージデータ４０３を伝送したいノードを特定するノードＩＤが格納される。ただし、発信源ノードがネットワーク内の全ノードへ送信する場合は最終送信先ノードＩＤ４０９を利用する必要はなく、ユニキャスト通信のように発信源ノードが送信先のノードを指定して送信する場合のみ、利用すればよい。
【００４６】
尚、パケット４００は経路制御情報４０２を含むのであれば４００の構成形態に限定されることはない。
【００４７】
また、図３（ｃ）に示すパケット４１０、及び図３（ｄ）に示すパケット４１３は経路情報テーブル３００作成時に、無線マルチホップネットワーク２００内の各ノードが送受信するブロードキャストパケット構成の一例である。
【００４８】
図３（ｃ）の４１１、及び４１２がブロードキャストパケット４１０を構成する情報であり、４１１にはブロードキャストパケット４１０を送信する発信源ノードＩＤが、４１２には現在のホップ数が格納される。
【００４９】
図３（ｄ）の４１４、４１５がブロードキャストパケット４１３を構成する情報であり、４１４にはブロードキャストパケット４１３を送信する発信源ノードＩＤが、４１５には発信源ノードから基準ノードＸまでの距離が格納される。
【００５０】
＜無線マルチホップネットワークの動作＞
図４〜図１２により、本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの動作について説明する。図４〜図１２は本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの動作を示すフローチャートであり、図４は無線マルチホップネットワークの経路情報テーブル作成の動作を示すフローチャート、図５は無線マルチホップネットワーク内の発信源ノードによるパケット送信の動作を示すフローチャート、図６は無線マルチホップネットワーク内のノードによる受信パケットの中継送信の動作を示すフローチャート、図７はノードの位置関係評価１の動作を示すフローチャート、図８はノードの位置関係評価２の動作を示すフローチャート、図９は送信要否選択方法１の動作を示すフローチャート、図１０は送信要否選択方法２の動作を示すフローチャート、図１１は送信要否選択方法３の動作を示すフローチャート、図１２は送信要否選択方法４の動作を示すフローチャートである。
【００５１】
まず、経路情報テーブル作成の動作を図４を用いて説明する。まず、ステップＳ５０１において、基準ノードＸ２０１は、図３（ｃ）に示すような発信源ノードＩＤ４１１、ホップ数４１２を含んだブロードキャストパケット４１０をフラッディングにより送信する。ここで、基準ノードＸ２０１が送信するブロードキャストパケット４１０の発信源ノードＩＤ４１１には基準ノードＸ２０１のノードＩＤを、ホップ数４１２には１を格納する。以下、通信方法はフラッディングを用いる。
【００５２】
そして、ステップＳ５０１による基準ノードＸ２０１からのブロードキャストパケット４１０の送信により、ステップＳ５０２において、無線マルチホップネットワーク２００を構成する全てのノードは、それぞれ複数の経路経由による、複数のブロードキャストパケットを受信する。
【００５３】
そして、ステップＳ５０３において、各ノードでは、ステップＳ５０２で受信したブロードキャストパケットの送信元ノードＩＤが、図２に示す経路情報テーブル３００のエントリ３０３のノードＩＤに登録されているか否かを確認する。ステップＳ５０３で登録されていないノードＩＤがある場合は、図２に示す経路情報テーブル３００に隣接ノードの情報を登録するためにステップＳ５０４に進み、それ以外の場合はステップＳ５０５に進む。
【００５４】
そして、ステップＳ５０４において、各ノードでは、図２に示す経路情報テーブル３００のエントリ３０３に隣接ノードＩＤとして送信元ノードＩＤを登録し、ステップＳ５０５に進む。
【００５５】
そして、ステップＳ５０５において、各ノードでは、ステップＳ５０２で受信した複数のブロードキャストパケットの中で、最小のホップ数を、図２に示す経路情報テーブル３００の自ノードから基準ノードＸ２０１までの距離に登録する。
【００５６】
そして、ステップＳ５０６において、各ノードは、図３（ｄ）に示すような発信源ノードＩＤ４１４、及び発信源ノードから基準ノードＸ２０１までの距離４１５を含むブロードキャストパケット４１３を送信し、基準ノードＸ２０１に対して、自ノードから基準ノードＸ２０１までの距離を基準ノードＸ２０１に通知する。
【００５７】
ここで、各ノードが送信するパケット４１３の発信源ノードＩＤ４１４は自ノードＩＤを、発信源ノードから基準ノードＸ２０１までの距離４１５は自ノードから基準ノードＸ２０１までの距離を格納する。
【００５８】
そして、ステップＳ５０７において、基準ノードＸ２０１は、全てのノードからのブロードキャストパケット４１３を受信し、基準ノードＸ２０１から最も離れたノード、すなわちブロードキャストパケット４１３の発信源ノードから基準ノードＸ２０１までの距離４１５が最も大きいノードの中から基準ノードＹとなるノード（ノード２０２）を１つ任意に決定し、決定したノード（ノード２０２）に対して、基準ノードＹであることを通知する。
【００５９】
基準ノードＹであることを通知されたノード（ノード２０２）では、ノード２０２が元々持っているノードＩＤに代えて、基準ノートＹとしてのノードＩＤを自ノードＩＤとして設定し、以降ノード２０２は基準ノードＹとして、パケットの送信などを行う。
【００６０】
そして、ステップＳ５０８において、基準ノードＸ２０１は無線マルチホップネットワーク２００を構成する全てのノードに基準ノードＸ２０１から基準ノードＹ２０２までの距離を、例えばブロードキャストパケットなどにより通知し、通知を受信した各ノードは経路情報テーブル３００の基準ノード間の距離３０１に同情報を登録する。
【００６１】
そして、ステップＳ５０９において、基準ノードＹ２０２は、発信源ノードＩＤ４１１、及びホップ数４１２を含んだブロードキャストパケット４１０をフラッディングにより送信する。ここで、基準ノードＹ２０２が送信するブロードキャストパケット４１０の発信源ノードＩＤ４１１には基準ノードＹのノードＩＤを、ホップ数４１２には１を格納する。
【００６２】
そして、ステップＳ５０９による基準ノードＹ２０２からのブロードキャストパケット４１０の送信により、ステップＳ５１０において、無線マルチホップネットワーク２００を構成する全てのノードは、それぞれ複数の経路経由による、複数のブロードキャストパケットを受信する。
【００６３】
そして、ステップＳ５１１において、各ノードでは、ステップＳ５１０で受信した複数のブロードキャストパケットの中で、最小のホップ数を、図２に示す経路情報テーブル３００の自ノードから基準ノードＹ２０２までの距離に登録する。
【００６４】
そして、ステップＳ５１２において、各ノードは自ノードから基準ノードＸ２０１までの距離、及び自ノードから基準ノードＹ２０２までの距離を隣接ノードへ通知する。
【００６５】
そして、ステップＳ５１３において、各ノードはステップＳ５１２で隣接ノードから通知された距離情報を、隣接ノード毎に、経路情報テーブル３００の隣接ノードから２つの基準ノードまでの距離３０３に登録する。
【００６６】
以上により、無線マルチホップネットワーク２００内の全てのノードは経路情報テーブル３００にそれぞれに必要とされる情報を登録する。
【００６７】
次に、無線マルチホップネットワーク２００の発信源ノードがパケットを送信する動作を図５を用いて説明する。まず、ステップＳ６０１において、発信源ノードは伝送データをパケット４００のメッセージデータ４０３に格納する。
【００６８】
そして、ステップＳ６０２からステップＳ６０６において、パケット４００の経路制御情報４０２に必要なデータを格納する。まず、ステップＳ６０２、及びステップＳ６０３において、発信源ノードが保持する経路情報テーブル３００のエントリ３０２に記録してある自ノードから基準ノードＸ２０１までの距離を４０４に、自ノードから基準ノードＹ２０２までの距離を４０５にそれぞれ格納する。ステップＳ６０４において、ホップ数４０６に１を格納する。ステップＳ６０５において、送信元ノードＩＤ４０７に自ノードＩＤを格納する。ステップＳ６０６において、送信先ノードＩＤリスト４０８に発信源ノードの全ての隣接ノードＩＤを格納する。発信源ノードは無線マルチホップネットワーク２００内の全てのノードへデータを送信するため、最終送信先ＩＤ４０８を利用しなくてもよい。
【００６９】
そして、ステップＳ６０７において、利用する通信プロトコルのヘッダフォーマットに応じた情報をパケット４００のヘッダ４０１に格納し、隣接ノードへ順次送信する。
【００７０】
以上が本実施の形態に係る発信源ノードの動作である。
【００７１】
次に、無線マルチホップネットワーク２００内のノードによる受信パケットの中継送信の動作を説明する。
【００７２】
上述したように発信源ノードは全ての隣接ノードへ送信する。また、無線マルチホップネットワーク２００内のノードは、明らかに重複受信となると判断される場合を除き、全ての隣接ノードへ中継送信するため、発信源ノードから無線マルチホップネットワーク２００内を波紋状にパケットが伝送されることになる。
【００７３】
しかし、発信源ノードの位置関係によっては、全てのノードへデータが伝送されない場合がある。この問題は、基準ノードＸ２０１、基準ノードＹ２０２を含んだ全てのノードが中継送信を行なうことで解決されるが、前記二つの基準ノードが中継送信を行なうと、フラッディングと同様に重複受信となるノードが増加してしまう。そこで、基準ノードＸ２０１は中継送信を行なうが、基準ノードＹ２０２は中継送信を行なわないとし、且つ、重複受信判断の基準を緩める。これにより、多少、重複受信は増加するが、基準ノードＸ２０１を経由したパケットが無線マルチホップネットワーク２００内を折り返す形となり、最終的に、パケットの伝送方向が基準ノードＸ２０１から基準ノードＹ２０２の向きへ収束すると共に、無線マルチホップネットワーク２００内の全てのノードへのパケットが実現できる。
【００７４】
本実施の形態では、無線マルチホップネットワーク２００内の上記パケットの伝送方向の特徴を踏まえ、以下４つの送信要否選択方法を用いて全ての隣接ノードの中から明らかに重複受信となるノードを判断する。
【００７５】
まず、送信要否選択方法１について説明する。
【００７６】
隣接ノードＩＤが受信パケット４００の送信先ノードＩＤリスト４０８にある場合、既に送信元ノードが当該隣接ノードへ中継送信していると判断でき、自ノードは当該隣接ノードへは中継送信不要と判断できる。すなわち、送信要否選択方法１では中継送信先となるノードとして、送信先ノードＩＤリスト４０８にない全ての隣接ノードを選択する。
【００７７】
次に、送信要否選択方法２について説明する。
【００７８】
基準ノードＸ２０１はパケットを受信した際、隣接ノードへ中継送信する場合があるので、送信元ノードから受信するパケットには発信源ノードから基準ノードＸ２０１を経由して届くものがある。ここで、隣接ノードは発信源ノードから基準ノードＸ２０１までの距離と隣接ノードから基準ノードＸ２０１までの距離の和以下のホップ数で必ずパケットを受信する。したがって、受信パケット４００のホップ数４０６と前記距離の和を比較し、ホップ数が前記距離の和以上の場合は、隣接ノードが自ノード以外のノードから既にパケットを受信していると判断でき、自ノードは当該隣接ノードへ中継送信不要と判断できる。上記判断に加え、送信要否選択方法１に記載した判断も行ない、中継送信先となる隣接ノードを選択する。
【００７９】
次に、送信要否選択方法３について説明する。
【００８０】
無線マルチホップネットワーク２００内のノードは基準ノードＸ２０１から基準ノードＹ２０２までの最短経路上にあるノードと最短経路上にないノードに分類でき、自ノードの隣接ノードの中で最短経路上にあるノードは、自ノード以外のノードを隣接ノードとして必ず有する。また、無線マルチホップネットワーク２００内のパケットは最終的に基準ノードＸ２０１から基準ノードＹ２０２の方向へ収束する。
【００８１】
以上より、自ノードよりも基準ノードＸ２０１に近い最短経路上にある隣接ノードは、当該隣接ノードよりも基準ノードＸ２０１に近いノードからパケットを受信する。そのため、自ノード及び、送信元ノードが最短系路上にあり、基準ノードＸ２０１から基準ノードＹ２０２の向きに伝送されるパケットを受信した場合、自ノードは当該隣接ノードへ中継送信不要と判断できる。上記判断に加え、送信要否選択方法２に記載した判断も行ない、中継送信先となる隣接ノードを選択する。
【００８２】
次に送信要否選択方法４について説明する。
【００８３】
自ノード、及び送信元ノードが共に最短経路上にない場合且つ、自ノード、及び送信元ノードが最短経路上にある互いに異なるノードを隣接ノードとして有する場合、送信元ノードと自ノード間でパケットが伝送される際、最短経路上の前記互いに異なるノード間も必ずパケットが伝送される。そのため、隣接ノードが最短経路上にある場合、隣接ノードはパケットを必ず別の経路から受信すると判断でき、自ノードは当該隣接ノードへ中継送信不要と判断できる。上記判断に加え、送信要否選択方法２に記載した判断も行ない、中継送信先となる隣接ノードを選択する。
【００８４】
ここで、以上４つの送信要否選択方法を用いた無線マルチホップネットワーク２００内のノードによる受信パケットの中継送信の動作を図６〜図１２を用いて説明する。
【００８５】
まず、図６に示すように、中継送信処理は、パケットの受信後、無線マルチホップネットワーク２００の全ての隣接ノードの中から中継送信先を選択する送信先判断７００、及び選択された隣接ノードへパケットを送信する送信動作７０１から構成される。
【００８６】
ここで、パケット４００は送信先ノードＩＤリスト４０８を含むため、全ての隣接ノードに対して中継送信の要否を判断した後、順次中継送信する必要があり、送信先判断７００の後で送信動作７０１を行なう。
【００８７】
送信先判断７００では、無線マルチホップネットワーク２００の基準ノード、送信元ノード、自ノード、隣接ノードのネットワーク上での位置関係を評価し、４つの送信要否選択方法（ステップＳ７０９〜ステップＳ７１２）の中から適切な方法を選択し、同方法により全ての隣接ノードの中から中継送信先となる隣接ノードを選択する。
【００８８】
送信動作７０１では、送信先判断７００で選択した全ての隣接ノードへ中継送信するため、送信パケットの経路制御情報４０２を再構成し、順次送信する。
【００８９】
まず、隣接ノードの中から中継送信先を選択する送信先判断７００を図６を用いて説明する。
【００９０】
まず、ステップＳ７０２において、受信パケット４００のホップ数４０６を確認する。ステップＳ７０２でホップ数が１の場合、ステップＳ７０９に進み、それ以外の場合ステップＳ７０３に進む。
【００９１】
そして、ステップＳ７０３において、自ノードが無線マルチホップネットワーク２００内の基準ノードＸ２０１、基準ノードＹ２０２、或いは前記２つの基準ノードの隣接ノードであるか否かを確認する。ステップＳ７０３で自ノードが基準ノードＸ２０１、基準ノードＹ２０２、或いは前記２つの基準ノードの隣接ノードである場合はステップＳ７０４に進む。それ以外の場合はステップＳ７０５に進む。
【００９２】
そして、ステップＳ７０４において、ノードの位置関係評価１を行なう。ノードの位置関係評価１では、無線マルチホップネットワーク２００内の自ノードが、基準ノードＸ２０１である場合、基準ノードＹ２０２である場合、基準ノードＸ２０１の隣接ノードである場合、及び基準ノードＹ２０２の隣接ノードである場合の４つに分けて評価し、その評価に基づき中継送信の要否を決定する。このステップ７０４でのノードの位置関係評価１の詳細は別途図７を用いて説明する。
【００９３】
そして、ステップＳ７０５において、ノードの位置関係評価２を行なう。ノードの位置関係評価２では、無線マルチホップネットワーク２００内の自ノード、及び送信元ノードが最短経路上にある場合、自ノード、及び送信元ノードが最短系路上にない場合、及び自ノード、或いは送信元ノードのいずれかが最短経路上にない場合の３つに分けて評価する。このステップＳ７０５でのノードの位置関係評価２の詳細は別途図８を用いて説明する。
【００９４】
そして、ステップＳ７０６において、ステップＳ７０４で決定した送信先要否選択方法が送信先要否選択方法１であるか否かを確認する。ステップＳ７０４で送信先要否選択方法１である場合、ステップＳ７０９へ進み、それ以外の場合、終了する。
【００９５】
また、ステップＳ７０７において、ステップＳ７０５で決定した送信先要否選択方法が送信先要否選択方法２であるか否かを確認する。ステップＳ７０７で送信先要否選択方法２である場合、ステップＳ７１０へ進み、それ以外の場合、ステップＳ７０８へ進む。
【００９６】
そして、ステップＳ７０８において、ステップＳ７０５で決定した送信先要否選択方法が送信先要否選択方法３であるか否かを確認する。ステップＳ７０８で送信先要否選択方法３である場合、ステップＳ７１１へ進み、それ以外の場合、ステップＳ７１２へ進む。
【００９７】
また、ステップＳ７０９において、送信先要否選択方法１を行なう。このステップＳ７０９での送信先要否選択方法１の詳細は別途図９を用いて説明する。
【００９８】
また、ステップＳ７１０において、送信先要否選択方法２を行なう。このステップＳ７１０での送信先要否選択方法２の詳細は別途図１０を用いて説明する。
【００９９】
また、ステップＳ７１１において、送信先要否選択方法３を行なう。このステップＳ７１１での送信先要否選択方法３の詳細は別途図１１を用いて説明する。
【０１００】
また、ステップＳ７１２において、送信先要否選択方法４を行なう。このステップＳ７１２での送信先要否選択方法４の詳細は別途図１２を用いて説明する。
【０１０１】
次に、選択された隣接ノードへパケットを中継送信する送信動作７０１を図６を用いて説明する。
【０１０２】
まず、ステップＳ７１３において、受信パケット４００のホップ数４０６を上記ホップ数４０６に１を加えた値に変更する。
【０１０３】
そして、ステップＳ７１４において、受信パケット４００の送信元ノードＩＤ４０７を自ノードＩＤに変更する。
【０１０４】
そして、ステップＳ７１５において、受信パケット４００の送信先ノードＩＤリスト４０８を送信先判断７００で選択した隣接ノードＩＤに変更する。
【０１０５】
そして、ステップＳ７１６において、利用する通信プロトコルのヘッダフォーマットに準じた情報をパケット４００のヘッダ４０１に格納し、送信先ノードＩＤリストにある隣接ノードへ順次送信する。
【０１０６】
以上が本実施の形態に係る通信経路制御方法の動作である。
【０１０７】
次に、図６に示すステップＳ７０４ノードの位置関係評価１の処理、及びステップＳ７０５ノードの位置関係評価２の処理の詳細について順に説明する。
【０１０８】
まず、図６に示すステップＳ７０４でのノードの位置関係評価１の処理を図７を用いて説明する。
【０１０９】
まず、ステップＳ８０１において、自ノードが基準ノードＹ２０２であるか否かを確認する。ステップＳ８０１で自ノードが基準ノードＹ２０２である場合、ステップＳ７０４の処理を終了し、それ以外の場合、ステップＳ８０２へ進む。
【０１１０】
そして、ステップＳ８０２において、自ノードが基準ノードＸ２０１であるか否かを確認する。ステップ８０２で自ノードが基準ノードＸ２０１である場合、ステップＳ８０８へ進み、それ以外の場合、ステップＳ８０３へ進む。
【０１１１】
そして、ステップＳ８０３において、自ノードが基準ノードＸ２０１の隣接ノードであるか否かを確認する。ステップＳ８０３で自ノードが基準ノードＸ２０１の隣接ノードである場合、ステップＳ８０４へ進み、それ以外の場合、ステップＳ８０５へ進む。
【０１１２】
そして、ステップＳ８０４において、受信パケット４００の発信源ノードから基準ノードＸ２０１までの距離４０２とホップ数４０６を比較する。ステップＳ８０４で発信源ノードから基準ノードＸ２０１までの距離４０２がホップ数４０６より大きい場合、受信パケット４００を基準ノードＸ２０１が受信していないと判断し、ステップＳ８０６へ進み、それ以外の場合、ステップＳ８０８へ進む。
【０１１３】
そして、ステップＳ８０６において、自ノードは基準ノードＸ２０１を送信先ノードに選択し、ステップＳ８０８へ進む。
【０１１４】
また、ステップＳ８０５において、受信パケット４００の発信源ノードから基準ノードＹ２０２までの距離４０５とホップ数４０６を比較する。ステップＳ８０５で発信源ノードから基準ノードＹ２０２までの距離４０５がホップ数４０６より大きい場合、受信パケット４００を基準ノードＹ２０２が受信していないと判断し、ステップＳ８０７へ進み、それ以外の場合、ステップＳ８０８へ進む。
【０１１５】
そして、ステップＳ８０７において、自ノードは基準ノードＹを送信先ノードに選択し、ステップＳ８０８へ進む。
【０１１６】
そして、ステップＳ８０８において、送信先要否選択方法１を選択することを決定し、ステップＳ７０４の処理を終了する。
【０１１７】
次に、図６に示すステップＳ７０５でのノードの位置関係評価２の処理を図８を用いて説明する。
【０１１８】
まず、ステップＳ９０１において、自ノードが基準ノードＸ２０１から基準ノードＹ２０２までの最短経路上にあるか否かを確認する。これは、図２に示す経路情報テーブル３００の基準ノード間の距離３０１、及び自ノードから２つの基準ノードまでの距離３０２の情報により確認する。ステップＳ９０１で自ノードが最短系路上にある場合、ステップＳ９０２へ進み、それ以外の場合、ステップＳ９０４へ進む。
【０１１９】
そして、ステップＳ９０２において、送信元ノードが基準ノードＸ２０１から基準ノードＹ２０２までの最短経路上にあるか否かを確認する。これは、受信パケット４００の送信元ＩＤ４０７、図２に示す経路情報テーブル３００の基準ノード間の距離３０１、隣接ノードＩＤの情報により確認する。
【０１２０】
ステップＳ９０２で送信元ノードが最短系路上にある場合、ステップＳ９０３へ進み、それ以外場合、ステップＳ９０７へ進む。
【０１２１】
そして、ステップＳ９０３において、自ノード、及び送信元ノードから基準ノードＸ２０１までの距離を比較する。ステップＳ９０３で送信元ノードが自ノードよりも基準ノードＸ２０１に近い場合、ステップＳ９０６へ進み、それ以外場合、ステップＳ９０７へ進む。
【０１２２】
また、ステップＳ９０４において、送信元ノードが基準ノードＸ２０１から基準ノードＹ２０２までの最短経路上にあるか否かを確認する。これは、受信パケット４００の送信元ＩＤ４０７、図２に示す経路情報テーブル３００の基準ノード間の距離３０１、隣接ノードＩＤの情報により確認する。
【０１２３】
ステップＳ９０４で送信元ノードが最短系路上にある場合、ステップＳ９０７へ進み、それ以外場合、ステップＳ９０５へ進む。
【０１２４】
そして、ステップＳ９０５において、自ノード及び送信元ノードから基準ノードＸ２０１及び基準ノードＹ２０２までの距離を比較する。
【０１２５】
ステップＳ９０５では、自ノードから基準ノードＸ２０１までの距離と送信元ノードから基準ノードＹ２０２までの距離が等しい、且つ、自ノードから基準ノードＹ２０２までの距離と送信元ノードから基準ノードＸ２０１までの距離が等しい場合、自ノードから基準ノードＸ２０１までの距離と自ノードから基準ノードＹ２０２までの距離の和と、送信元ノードから基準ノードＸ２０１までの距離と送信元ノードから基準ノードＹ２０２までの距離の和が等しい、且つ、自ノードから基準ノードＸ２０１までの距離と送信元ノードから基準ノードＸ２０１までの距離が異なる場合、すなわち、自ノード、及び送信元ノードが互いに異なる最短経路上にあるノードを隣接ノードとして有する場合、ステップＳ９０８へ進み、それ以外の場合、ステップＳ９０７へ進む。
【０１２６】
例えば、図１に示す例では、最短経路は、基準ノードＸ２０１−ノードＡ２０３−ノードＦ２０８−基準ノードＹ２０２の経路であり、自ノードをノードＩ２１１、送信元ノードをノードＨ２１０とすると、自ノードから基準ノードＸ２０１までの距離は「３」で、送信元ノードから基準ノードＹ２０２までの距離は「３」で等しく、且つ、自ノードから基準ノードＹ２０２までの距離は「２」で、送信元ノードから基準ノードＸ２０１までの距離は「２」で等しく、且つ、自ノードから基準ノードＸ２０１までの距離と自ノードから基準ノードＹ２０２までの距離の和は「５」で、送信元ノードから基準ノードＸ２０１までの距離と送信元ノードから基準ノードＹ２０２までの距離の和は「５」で等しい。ここで、自ノードから基準ノードＸ２０１までの距離は「３」で送信元ノードから基準ノードＸ２０１までの距離は「２」で異なるので、互いに異なる最短経路上にあるノードを隣接ノードとし有している（ノードＡ２０３とノードＦ２０８）。
【０１２７】
逆に、ノードＤ２０６とノードＣ２０５では、各ノードから基準ノードＸ２０１までの距離と各ノードから基準ノードＹ２０２までの距離の和は「５」で等しいが、各ノードから基準ノードＸ２０１までの距離も「２」で等しいため、互いに異なる最短経路上にあるノードを隣接ノードとし有していない（この場合はノードＤ２０６とノードＣ２０５共にノードＡ２０３を隣接ノードとして有している）。
【０１２８】
次に、図６に示すステップＳ７０９での送信先要否選択方法１の処理、ステップＳ７１０での送信先要否選択方法２の処理、ステップＳ７１１での送信先要否選択方法３の処理、及びステップＳ７１２での送信先要否選択方法４の処理の詳細について順に説明する。
【０１２９】
まず、図６に示すステップＳ７０９での送信先要否選択方法１の処理を図９を用いて説明する。
【０１３０】
まず、ステップＳ１００１において、自ノードの全ての隣接ノードについて中継送信するか否かを判断したかを確認する。ステップＳ１００１で既に全ての隣接ノードについて判断している場合、ステップＳ７０９の処理を終了し、それ以外の場合、ステップＳ１００２へ進む。
【０１３１】
そして、ステップＳ１００２において、未判断の隣接ノードの中から任意に１つのノードを選択し、ステップＳ１００３へ進む。ここで、ステップＳ１００２では、隣接ノードＲを選択したものとして以下説明する。
【０１３２】
そして、ステップＳ１００３において、受信パケット４００の送信先ノードＩＤリスト４０８に隣接ノードＲがあるか否かを確認する。ステップＳ１００３で隣接ノードＲが送信先ノードＩＤリストにない場合、ステップＳ１００４へ進み、それ以外の場合、ステップＳ１００５へ進む。
【０１３３】
そして、ステップＳ１００４において、隣接ノードＲへ中継送信すると判断し、ステップＳ１００１へ戻る。
【０１３４】
また、ステップＳ１００５において、隣接ノードＲへ中継送信不要と判断し、ステップＳ１００１へ戻る。
【０１３５】
次に、図６に示すステップＳ７１０での送信先要否選択方法２の処理を図１０を用いて説明する。
【０１３６】
まず、ステップＳ１１０１において、自ノードの全ての隣接ノードについて中継送信するか否かを判断したかを確認する。ステップＳ１１０１で既に全ての隣接ノードについて判断している場合、ステップＳ７１０の処理を終了し、それ以外の場合、ステップＳ１１０２へ進む。
【０１３７】
そして、ステップＳ１１０２において、未判断の隣接ノードの中から任意に１つのノードを選択し、ステップＳ１１０３へ進む。ここで、隣接ノードＲを選択したものとして以下説明する。
【０１３８】
そして、ステップＳ１１０３において、受信パケット４００の送信先ノードＩＤリスト４０８に隣接ノードＲがあるか否かを確認する。ステップＳ１１０３で隣接ノードＲが送信先ノードＩＤリストにない場合、ステップＳ１１０４へ進み、それ以外の場合、ステップＳ１１０６へ進む。
【０１３９】
そして、ステップＳ１１０４において、受信パケット４００のホップ数４０６と、発信源ノードから基準ノードＸ２０１までの距離と隣接ノードＲから基準ノードＸ２０１までの距離の和（Ｈｓｕｍ）を比較する。ステップＳ１１０４でホップ数４０６が前記距離の和（Ｈｓｕｍ）以上の場合はステップＳ１１０６へ進み、それ以外の場合はステップＳ１１０５へ進む。
【０１４０】
そして、ステップＳ１１０５において、隣接ノードＲへ中継送信すると判断し、ステップＳ１１０１へ戻る。
【０１４１】
また、ステップＳ１１０６において、隣接ノードＲへ中継送信不要と判断し、ステップＳ１１０１へ戻る。
【０１４２】
次に、図６に示すステップＳ７１１での送信先要否選択方法３の処理を図１１を用いて説明する。
【０１４３】
まず、ステップＳ１２０１において、自ノードの全ての隣接ノードについて中継送信するか否かを判断したかを確認する。ステップＳ１２０１で既に全ての隣接ノードについて判断している場合、ステップＳ７１１を終了し、それ以外の場合、ステップＳ１２０２へ進む。
【０１４４】
そして、ステップＳ１２０２において、未判断の隣接ノードの中から任意に１つのノードを選択し、ステップＳ１２０３へ進む。ここで、隣接ノードＲを選択したものとして以下説明する。
【０１４５】
そして、ステップＳ１２０３において、受信パケット４００の送信先ノードＩＤリスト４０８に隣接ノードＲがあるか否かを確認する。ステップＳ１２０３で隣接ノードＲが送信先ノードＩＤリストにない場合、ステップＳ１２０４へ進み、それ以外の場合、ステップＳ１２０８へ進む。
【０１４６】
そして、ステップＳ１２０４において、受信パケット４００のホップ数４０６と、発信源ノードから基準ノードＸまでの距離と隣接ノードＲから基準ノードＸまでの距離の和（Ｈｓｕｍ）を比較する。ステップＳ１２０４でホップ数４０６が前記距離の和（Ｈｓｕｍ）以上の場合はステップＳ１２０８へ進み、それ以外の場合はステップＳ１２０５へ進む。
【０１４７】
そして、ステップＳ１２０５において、隣接ノードＲが基準ノードＸ２０１から基準ノードＹ２０２までの最短経路上にあるか否かを確認する。これは図２に示す経路情報テーブル３００の基準ノード間の距離３０１と隣接ノードの情報により確認する。ステップＳ１２０５で最短経路上にある場合、ステップＳ１２０６へ進み、それ以外の場合、ステップＳ１２０７へ進む。
【０１４８】
そして、ステップＳ１２０６において、隣接ノードＲが自ノードよりも基準ノードＸ２０１に近いか否かを確認する。これは図２に示す経路情報テーブル３００の自ノードの情報と隣接ノードの情報により確認する。ステップＳ１２０６で隣接ノードＲが自ノードよりも基準ノードＸ２０１に近い場合、ステップＳ１２０８へ進み、それ以外の場合、ステップＳ１２０７へ進む。
【０１４９】
そして、ステップＳ１２０７において、隣接ノードＲへ中継送信すると判断し、ステップＳ１２０１へ戻る。
【０１５０】
また、ステップＳ１２０８において、隣接ノードＲへ中継送信不要と判断し、ステップＳ１２０１へ戻る。
【０１５１】
次に、図６に示すステップＳ７１２での送信先要否選択方法４の処理を図１２を用いて説明する。
【０１５２】
まず、ステップＳ１３０１において、自ノードの全ての隣接ノードについて中継送信するか否かを判断したかを確認する。ステップＳ１３０１で既に全ての隣接ノードについて判断している場合、ステップＳ７１２の処理を終了し、それ以外の場合、ステップＳ１３０２へ進む。
【０１５３】
そして、ステップＳ１３０２において、未判断の隣接ノードの中から任意に１つのノードを選択し、ステップＳ１３０３へ進む。ここでは隣接ノードＲを選択したものとして以下説明する。
【０１５４】
そして、ステップＳ１３０３において、受信パケット４００の送信先ノードＩＤリスト４０８に隣接ノードＲがあるか否かを確認する。ステップＳ１３０３で隣接ノードＲが送信先ノードＩＤリストにない場合、ステップＳ１３０４へ進み、それ以外の場合、ステップＳ１３０７へ進む。
【０１５５】
そして、ステップＳ１３０４において、受信パケット４００のホップ数４０６と、発信源ノードから基準ノードＸ２０１までの距離と隣接ノードＲから基準ノードＸ２０１までの距離の和（Ｈｓｕｍ）を比較する。ステップＳ１３０４でホップ数４０６が前記距離の和（Ｈｓｕｍ）以上の場合はステップＳ１３０７へ進み、それ以外の場合はステップＳ１３０５へ進む。
【０１５６】
そして、ステップＳ１３０５において、隣接ノードＲが基準ノードＸ２０１から基準ノードＹ２０２までの最短経路上にあるか否かを確認する。これは図２に示す経路情報テーブル３００の基準ノード間の距離３０１と隣接ノードの情報により確認する。ステップＳ１３０５で最短経路上にある場合、ステップＳ１３０７へ進み、それ以外の場合、ステップＳ１３０６へ進む。
【０１５７】
そして、ステップＳ１３０６において、隣接ノードＲへ中継送信すると判断し、ステップＳ１３０１へ戻る。
【０１５８】
また、ステップＳ１３０７において、隣接ノードＲへ中継送信不要と判断し、ステップＳ１３０１へ戻る。
【０１５９】
以上が、無線マルチホップネットワーク２００において、各ノードがパケットを受信後、パケットのホップ数による判断（ステップＳ７０２）、無線マルチホップネットワーク２００内の自ノードの位置による判断（ステップＳ７０３）、自ノードが基準ノード近隣にある場合の判断（ステップＳ７０４）、及び自ノード及び隣接ノードの無線マルチホップネットワーク２００内の位置関係による判断（ステップＳ７０５）に従い、全ての隣接ノードの中から中継送信先となるノードを選択する方法を４つの送信先要否選択方法１から送信先要否選択方法４の中から決定し、それら４つの送信先要否選択方法のいずれかで中継送信すると判断したノードへ中継送信する、距離情報に基づく通信経路制御方法の動作である。
【０１６０】
＜受信パケットの中継送信の動作の具体例＞
次に、図１３により、図６に示す受信パケットの中継送信の動作の具体例について説明する。図１３は本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの受信パケットの中継送信の動作の具体例を示す図である。
【０１６１】
図１３において、無線マルチホップネットワークはノード１０１〜１０８から構成されている。図１３では、ノード１０１が基準ノードＸ、ノード１０２が基準ノードＹで、発信源ノードをノードＥ１０８とし、自ノードＺ１０７が隣接ノードＢ１０４からパケットを受信したとする。
【０１６２】
また、自ノードＺ１０７は経路情報テーブル１０９を保持し、隣接ノードＢ１０４が中継送信するパケットには経路制御情報１１０が格納されているものとする。
【０１６３】
自ノードＺ１０７は図６のフローチャートに従い、中継送信する隣接ノードを選択する。まず、受信パケットのホップ数は経路制御情報１１０により「２」であり、自ノード１０７は基準ノードＸ１０１及び基準ノードＹ１０２の隣接ノードではないため、図６に示すステップＳ７０５のノード位置関係評価２へ進む。
【０１６４】
また、基準ノード間の距離１１３は「３」であり、自ノードＺ１０７から基準ノードＸ１０１までの距離と自ノードＺ１０７から基準ノードＹ１０２までの距離の和は「４」である。
【０１６５】
したがって、自ノードＺ１０７は、基準ノードＸ１０１から基準ノードＹ１０２の最短経路上にない。一方、送信元ノードである隣接ノードＢ１０４は、隣接ノードＢ１０４から基準ノードＸ１０１までの距離と隣接ノードＢ１０４から基準ノードＹ１０２までの距離の和が「３」のため最短経路上にある。
【０１６６】
以上から、自ノードＺ１０７は送信要否選択方法２を用いて中継送信先を選択する。
【０１６７】
まず、判断１１２において、隣接ノードＣ１０５について判断する。隣接ノードＣ１０５は受信パケットの経路制御情報１１０の送信先ノードＩＤリストにあるため、図１０に示すステップＳ１１０３に従い、隣接ノードＣ１０５へは送信不要と判断できる。
【０１６８】
次に、判断１１１において、隣接ノードＡ１０３について判断する。経路制御情報１１０より、隣接ノードＡ１０３は送信先ノードＩＤリストにない。また、発信源ノードＥ１０８から基準ノードＸ１０１までの距離は「１」であり、自ノードＺ１０７が保持する経路情報テーブル１０９の隣接ノードＡの情報１１５より隣接ノードＡ１０３から基準ノードＸ１０１までの距離は「１」であることがわかる。
【０１６９】
したがって、発信源ノードＥ１０８から基準ノードＸ１０１までの距離と隣接ノードＡ１０３から基準ノードＸ１０１までの距離の和は「２」であり、受信パケットのホップ数は「２」であることから、図１０のステップＳ１１０４の判断に従い、隣接ノードＡ１０３へは送信不要と判断できる。
【０１７０】
次に判断１２０において、隣接ノードＤ１０６について判断する。隣接ノードＤ１０６については隣接ノードＡ１０１の判断手順と同様である。隣接ノードＤ１０６から基準ノードＸ１０１までの距離と発信源ノードＥ１０８から基準ノードＸ１０１までの距離の和は「４」であるため、図１０のステップＳ１１０４に従い、隣接ノードＤへ送信すると判断する。
【０１７１】
以上より、自ノードＺ１０７は、発信源ノードがノードＥ１０８であり隣接ノードＢ１０４からパケットを受信した場合は、隣接ノードＤ１０６へのみ中継送信する。
【０１７２】
以上のように、本実施の形態では、無線ネットワーク、特に無線マルチホップネットワークに好適な距離情報に基づく通信制御方法において、無線マルチホップネットワーク２００内の任意の１ノードから全ノードへデータを伝送する場合に、各ノードが保持する経路情報テーブル、及び受信パケットの経路制御情報を用いて、明らかに重複受信すると自律的に判断し、当該ノード以外の隣接ノードへデータを中継送信するため、単純なフラッディングのようなブロードキャスト通信よりも通信トラフィックを削減することができる。
【０１７３】
また、ブロードキャスト通信はコネクションレス型通信プロトコルによって行われるため、相手にパケットが届いたことを知ることはできない。通信相手に確実に情報を伝送したい場合はコネクション型通信プロトコルが有効であり、そのためにはユニキャスト通信でなければならない。本実施の形態では、中継送信先を限定して、ユニキャスト通信により順次送信するため、ネットワーク内のある１つのノードから全てのノードへ同一のデータを伝送する場合でも、コネクション型通信プロトコルを利用して確実にデータを伝送することができる。
【０１７４】
＜ある１ノードへのデータ伝送＞
次に、無線マルチホップネットワーク２００、経路情報テーブル３００、及びパケット４００において、無線マルチホップネットワーク２００内の任意の１ノードからある１ノードへコネクション型通信プロトコルによりデータを伝送する場合の動作を説明する。
【０１７５】
ある１ノードへ向けて伝送する場合の動作は以下の二つの相違点を除き、上述の全ノードへ伝送する場合の動作と同様である。
【０１７６】
以下、二つの相違点について説明する。
【０１７７】
まず、発信源ノードのパケット送信時における相違点を説明する。無線マルチホップネットワーク２００内の全ノードへデータを伝送する場合は、発信源ノードは経路制御情報４０２内の最終宛先ノードＩＤ４０９を指定しなくともよい。
【０１７８】
ある１ノードへ向けてコネクション通信型プロトコルによりデータを伝送する場合は、発信源ノードが最終的にデータを届けたいノードのノードＩＤを最終送信先ノードＩＤ４０９に指定する。
【０１７９】
次に、各ノードによるパケット中継送信時における相違点を説明する。
【０１８０】
上述の全ノードへデータを伝送する場合は、無線マルチホップネットワーク２００内の各ノードは、図９から図１２に示す４つの送信先要否選択方法の中から１つを選択し、全ての隣接ノードから中継送信先を判断し送信する。
【０１８１】
ある１ノードへ向けてコネクション型通信プロトコルによりデータを伝送する場合は、以下の二つの場合に分類される。
【０１８２】
受信したパケットの最終送信先ノードＩＤに示されるノードが自ノードの隣接ノードに含まれる場合、他の隣接ノードには一切中継送信せず、最終送信先ノードＩＤに示される当該隣接ノードへのみ中継送信する。それ以外の場合は、上述の全ノードへ伝送する場合と同様に前記４つの送信先要否選択方法の中から１つを選択し、全ての隣接ノードから中継送信先を判断し送信する。
【０１８３】
以上により、受信したパケットを隣接ノードへ中継送信するような無線マルチホップネットワークにおいて、無線マルチホップネットワーク２００内の任意の１ノードからある１ノードへコネクション型通信プロトコルによりデータを伝送することができる。
【０１８４】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【０１８５】
本発明は、無線ネットワークに適用可能であり、特に無線マルチホップネットワーク内の任意の１ノードからネットワーク内の全てのノードへ情報を伝送する通信経路制御方法に関し、距離情報に基づく経路制御に適用可能である。
【図面の簡単な説明】
【０１８６】
【図１】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの構成を示す構成図である。
【図２】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークを構成する各ノードが保持する経路情報テーブルの構成を示す構成図である。
【図３】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワーク内のノード間で送受信されるパケット構成の一例を示す図である。
【図４】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの経路情報テーブル作成の動作を示すフローチャートである。
【図５】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワーク内の発信源ノードによるパケット送信の動作を示すフローチャートである。
【図６】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワーク内のノードによる受信パケットの中継送信の動作を示すフローチャートである。
【図７】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークのノードの位置関係評価１の動作を示すフローチャートである。
【図８】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークのノードの位置関係評価２の動作を示すフローチャートである。
【図９】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの送信要否選択方法１の動作を示すフローチャートである。
【図１０】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの送信要否選択方法２の動作を示すフローチャートである。
【図１１】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの送信要否選択方法３の動作を示すフローチャートである。
【図１２】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの送信要否選択方法４の動作を示すフローチャートである。
【図１３】本発明の一実施の形態に係る通信経路制御方法が適用される無線マルチホップネットワークの受信パケットの中継送信の動作の具体例を示す図である。
【図１４】特許文献１のネットワーク構成の一例を示す図である。
【符号の説明】
【０１８７】
１０１〜１０８…ノード、１０９…経路情報テーブル、１１０…経路制御情報、２００…無線マルチホップネットワーク、２０１〜２１１…ノード、３００…経路情報テーブル、４００…受信パケット、４０１…ヘッダ、４０２…経路制御情報、４０３…メッセージデータ４１０、４１３…ブロードキャストパケット。
【図１】
2007104320.tif 000003
【図２】
2007104320.tif 000004
【図３】
2007104320.tif 000005
【図４】
2007104320.tif 000006
【図５】
2007104320.tif 000007
【図６】
2007104320.tif 000008
【図７】
2007104320.tif 000009
【図８】
2007104320.tif 000010
【図９】
2007104320.tif 000011
【図１０】
2007104320.tif 000012
【図１１】
2007104320.tif 000013
【図１２】
2007104320.tif 000014
【図１３】
2007104320.tif 000015
【図１４】
2007104320.tif 000016