(57)【要約】【課題】マルチホップネットワークにおいてループを回避する優先方路決定方法および装置を提供する。【解決手段】ゲートウェイノードおよび複数のマルチホップノードを含む無線ネットワークにおいて優先方路を決定する優先方路決定方法であって、複数のマルチホップノード中の１つを最終宛先ノードとして設定し、通信コストに基づいてゲートウェイノードと最終宛先ノードとの間の経路を選択し、選択した経路上に配置されているマルチホップノードのうちから最終宛先ノードに隣接する最終中継ノードを決定し、最終中継ノードと最終宛先ノードとの間の経路を、ゲートウェイノードと最終宛先ノードとの間で転送されるパケットを通過させる優先方路として決定する。【選択図】図２
2019121923.tif 000002
【特許請求の範囲】
【請求項１】
ゲートウェイノードおよび複数のマルチホップノードを含む無線ネットワークにおいて優先方路を決定する優先方路決定方法であって、
前記複数のマルチホップノード中の１つを最終宛先ノードとして設定し、
通信コストに基づいて前記ゲートウェイノードと前記最終宛先ノードとの間の経路を選択し、
前記選択した経路上に配置されているマルチホップノードのうちから前記最終宛先ノードに隣接する最終中継ノードを決定し、
前記最終中継ノードと前記最終宛先ノードとの間の経路を、前記ゲートウェイノードと前記最終宛先ノードとの間で転送されるパケットを通過させる優先方路として決定する
ことを特徴とする優先方路決定方法。
【請求項２】
前記最終中継ノードの決定において、
前記選択された経路上に配置されているマルチホップノードのうち、次ホップ宛先ノードと、前記最終宛先ノードと、が一致する場合には、前記最終宛先ノードの前ホップを前記最終中継ノードとして決定する
ことを特徴とする請求項１に記載の優先方路決定方法。
【請求項３】
前記優先方路の決定において、
前記最終中継ノードから前記最終宛先ノードに向かう経路を下り優先方路として決定し、
前記最終宛先ノードから前記最終中継ノードに向かう経路を上り優先方路として決定する
ことを特徴とする請求項１または２に記載の優先方路決定方法。
【請求項４】
前記優先方路の決定において、
前記選択された経路上に配置されているマルチホップノードのうち、前記ゲートウェイノードの次ホップ宛先ノードと、前記最終宛先ノードと、が一致する場合には、前記ゲートウェイノードと前記最終宛先ノードとの間の経路を優先方路として決定する
ことを特徴とする請求項１〜３のうちいずれかに記載の優先方路決定装置。
【請求項５】
前記複数のマルチホップノードのいずれかから無線環境が変化したことを表す情報を受信した場合には、前記優先方路の決定を再度実行する
ことを特徴とする請求項１〜４のうちいずれかに記載の優先方路決定方法。
【請求項６】
ゲートウェイノードおよび複数のマルチホップノードを含む無線ネットワークにおいて優先方路を決定する優先方路決定装置であって、
前記複数のマルチホップノード中の１つを最終宛先ノードとして設定するノード設定部と、
通信コストに基づいて前記ゲートウェイノードと前記最終宛先ノードとの間の経路を選択する経路選択部と、
前記選択した経路上に配置されているマルチホップノードのうちから前記最終宛先ノードに隣接する最終中継ノードを決定する中継ノード決定部と、
前記最終中継ノードと前記最終宛先ノードとの間の経路を、前記ゲートウェイノードと前記最終宛先ノードとの間で転送されるパケットを通過させる優先方路として決定する優先方路決定部と、
を備えることを特徴とする優先方路決定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチホップネットワークにおいて優先方路を決定する優先方路決定方法および優先方路決定装置に係わる。
【背景技術】
【０００２】
マルチホップネットワークにおいては、各ノードが保持する経路情報に基づきパケットが転送される。ただし、再送により代替経路が選択された際などに、ループが発生する場合がある。すなわち、送信元ノードから送信されたパケットが、宛先ノードに到達することなくネットワーク内を循環してしまうことがある。この問題は、例えば、ＩＰヘッダのＴＴＬ（time to live）を利用して循環しているパケットを削除すれば解決され得る。しかし、高信頼かつ低遅延が求められるネットワーク環境においては、ループによるパケットロスを排除する必要がある。
【０００３】
関連技術として、上位の隣接する無線通信装置から下り経路制御メッセージに対する送達確認を受信した場合、ネットワーク制御部に上り経路情報の更新を指示する無線通信装置が提案されている（例えば、特許文献１参照）。また、関連技術として、各ノードが転送したパケットを記憶しておき、ループを検出した際にループ発生前のノードにパケットを戻す方法が提案されている（例えば、非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１６−７６８１６号公報
【非特許文献】
【０００５】
【非特許文献１】U. Herberg, A. Cardenas, T. Iwao, M. Dow, “Depth-First Forwarding (DFF) in Unreliable Networks,” IETF RFC6971, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術によるマルチホップネットワークの方路決定においては、ループの問題を解決しようとすると、遅延時間が大きく、データ伝送の効率が低くなることがある。
【０００７】
本発明の１つの側面に係わる目的は、マルチホップネットワークにおいてループを回避する優先方路決定方法および装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明の１つの態様の優先方路決定方法は、ゲートウェイノードおよび複数のマルチホップノードを含む無線ネットワークにおいて優先方路を決定する優先方路決定方法であって、前記複数のマルチホップノード中の１つを最終宛先ノードとして設定し、通信コストに基づいて前記ゲートウェイノードと前記最終宛先ノードとの間の経路を選択し、前記選択した経路上に配置されているマルチホップノードのうちから前記最終宛先ノードに隣接する最終中継ノードを決定し、前記最終中継ノードと前記最終宛先ノードとの間の経路を、前記ゲートウェイノードと前記最終宛先ノードとの間で転送されるパケットを通過させる優先方路として決定することを特徴とする。
【発明の効果】
【０００９】
上述の態様によれば、マルチホップネットワークにおいてループを回避することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態に係わる無線通信システムの一例を示す図である。
【図２】本発明の実施形態に係わる優先方路決定装置の一例を示す図である。
【図３】優先方路決定方法の手順の一例を示す図である。
【図４】優先方路決定方法の手順の一例を示す図である。
【図５】優先方路決定方法の手順の一例を示す図である。
【図６】優先方路決定方法の手順の一例を示す図である。
【図７】優先方路決定方法の手順の一例を示す図である。
【図８】優先方路を決定する優先方路決定方法の一例を示すフローチャートである。
【図９】優先方路を決定する優先方路決定方法の一例を示すフローチャートである。
【発明を実施するための形態】
【００１１】
図１は、本発明の実施形態に係わる無線通信システムの一例を示す図である。実施形態の無線通信システム１は、図１に示すように、ゲートウェイ（Gateway）ルータ（以下、「ＧＷルータＧ０」という）、ｎ台（ｎは自然数）のルータＭ１〜Ｍｎおよび優先方路決定装置１０を備える。
【００１２】
ＧＷルータＧ０は、他のネットワークと接続するためのゲートウェイルータとして動作する。すなわち、ＧＷルータＧ０は、ゲートウェイのノード（以下、「ゲートウェイノード」という）として動作し得る。
【００１３】
ルータＭ１〜Ｍｎは、他のルータとの間で無線信号を送信および受信することができる。すなわち、各ルータＭ１〜Ｍｎは、マルチホップネットワークの各ノード（以下、「マルチホップノード」という）として動作し得る。また、ルータＭ１〜Ｍｎは、１または複数の無線端末を収容することができ、無線アクセスポイントとして動作し得る。すなわち、ルータＭ１〜Ｍｎは、無線端末から出力される上りリンク信号を受信し、無線端末へ下り信号を送信する。各ルータＭ１〜Ｍｎは、固有のＭＡＣアドレスが付与されている。
【００１４】
本発明の実施形態に係わる優先方路決定装置１０は、図１に示す無線ネットワークに構築されたメッシュ状の経路からツリー構成の優先方路を決定する。
【００１５】
図２は、本発明の実施形態に係わる優先方路決定装置１０の一例を示す図である。
優先方路決定装置１０は、インタフェース（ＩＦ）１１、ノード設定部１２、経路選択部１３、中継ノード決定部１４、優先方路決定部１５およびメモリ２１を備える。メモリ２１には、ノード管理テーブル２２および通信コスト情報２３が格納されている。なお、優先方路決定装置１０は、図２に示していない他の機能を備えていてもよい。また、メモリ２１は、図２に示していない他の情報を格納していてもよい。
【００１６】
インタフェース１１は、ＧＷルータＧ０、ルータＭ１〜Ｍｎにより測定される測定結果を受信する。測定結果は、たとえば、ＧＷルータＧ０やルータＭ１〜Ｍｎから送信されるビーコン信号の受信電力（ＲＳＳＩ：Received Signal Strength Indicator）の測定データを表す。また、測定結果は、ノード情報や、リンク情報、通信コストの情報を含んでもよい。ＧＷルータＧ０やルータＭ１〜Ｍｎから受信した測定結果は、メモリ２１に格納される。
【００１７】
ノード設定部１２は、優先方路を決定すべきマルチホップノードを最終宛先ノードとして設定する。ここで、優先方路決定装置１０は、各ノードについてそれぞれ優先方路を決定する。したがって、ノード設定部１２は、各ノードを１つずつ順番に最終宛先ノードとして設定する。なお、「優先方路」は、この実施例では、ゲートウェイノードと最終宛先ノードとの間で転送されるパケットを通過させる経路を表す。
【００１８】
経路選択部１３は、通信コストに基づいてＧＷルータＧ０と最終宛先ノードとの間の経路を選択する。すなわち、経路選択部１３は、ゲートウェイノードとして動作し得るＧＷルータＧ０とノード設定部１２が最終宛先ノードとして設定したルータＭ１〜Ｍｎとの間の経路を通信コスト情報２３に格納されている通信コストに基づいて選択する。一例としては、最も通信コストが小さい経路が選択される。なお、経路選択部１３は、ＧＷルータＧ０とｎ台のルータＭ１〜Ｍｎとの間の経路をルータＭ１〜Ｍｎ毎に選択する。
【００１９】
中継ノード決定部１４は、経路選択部１３により選択された経路上に配置されているマルチホップノードのうちから最終宛先ノードに隣接する最終中継ノードを決定する。最終中継ノードとは、ノード設定部１２が最終宛先ノードとして設定したノードの前ホップのマルチホップノードをいう。
【００２０】
具体的には、中継ノード決定部１４は、経路選択部１３により選択された経路を構築するノードの次ホップ宛先ノードを選択し、次ホップ宛先ノードと最終宛先のノードとが一致するか否か判定する。そして、中継ノード決定部１４は、次ホップ宛先ノードと最終宛先のノードとが一致した場合には、最終宛先ノードの前ホップを最終中継ノードとして決定する。
【００２１】
優先方路決定部１５は、最終中継ノードと最終宛先ノードとの間の経路を、ゲートウェイノードと最終宛先ノードとの間で転送されるパケットを通過させる優先方路として決定する。具体的には、優先方路決定部１５は、中継ノード決定部１４により決定された最終中継ノードから最終宛先ノードに向かう経路を下り優先方路として決定する。また、優先方路決定部１５は、最終宛先ノードから中継ノード決定部１４により決定された最終中継ノードに向かう経路を上り優先方路として決定する。ゲートウェイノードから最終宛先ノードへのホップ数が１である場合には、優先方路決定部１５は、ゲートウェイノードを最終中継ノードとして、ゲートウェイノードと最終宛先ノードとの間の経路を優先方路として決定する。そして、優先方路決定装置１０は、各ノードについて決定した優先方路を、それぞれ対応するＧＷルータＧ０、ルータＭ１〜Ｍｎに通知する。
【００２２】
優先方路決定部１５は、ＧＷルータＧ０の周辺環境測定部３２またはルータＭ１〜Ｍｎの周辺環境測定部４２で測定されたＲＳＳＩ測定値を報告するＭＲＥＰ（measurement report：測定結果報告）を受信すると、優先方路選択を再実行する。特に、ＭＲＥＰにより通知されるＲＳＳＩ測定値が無線リンクの切断を示すときは、優先方路決定装置１０は、優先方路を再決定する。ただし、無線リンクが切断されていないときであっても、優先方路決定装置１０は、優先方路を再決定してもよい。
【００２３】
ＧＷルータＧ０は、インタフェース（ＩＦ）３１、周辺環境測定部３２、経路管理部３３および経路管理テーブル３４を備える。なお、ＧＷルータＧ０は、図２に示していない他の機能を備えていてもよい。
【００２４】
周辺環境測定部３２は、例えば、他のルータＭ１〜Ｍｎから送信されるビーコン信号のＲＳＳＩなどの周辺環境を測定する。周辺環境測定部３２は、この測定結果を保持し、ＭＲＥＰを利用して優先方路決定装置１０へ通知する。経路管理部３３は、優先方路決定装置１０から通知された優先方路の情報を含む経路情報を経路管理テーブル３４に格納して管理する。経路管理テーブル３４は、優先方路決定装置１０から通知された優先方路の情報を含む経路の情報を格納する。インタフェース３１は、経路情報に紐付けられた経路のＯＮ／ＯＦＦの情報および優先方路決定装置１０から通知される優先方路の情報をＲＩＮＤ（Route Indicator）を利用して受信する。
【００２５】
ルータＭ１〜Ｍｎは、インタフェース（ＩＦ）４１、周辺環境測定部４２、経路管理部４３および経路管理テーブル４４を備える。なお、ルータＭ１〜Ｍｎは、図２に示していない他の機能を備えていてもよい。
【００２６】
周辺環境測定部４２は、例えば、ＧＷルータＧ０や他のルータＭ１〜Ｍｎから送信されるビーコン信号のＲＳＳＩなどの周辺環境を測定する。周辺環境測定部４２は、この測定結果を保持し、ＭＲＥＰを利用してＧＷルータＧ０を経由して優先方路決定装置１０へ通知する。経路管理部４３は、ＧＷルータＧ０を経由して優先方路決定装置１０から通知された優先方路の情報を含む経路情報を経路管理テーブル４４に格納して管理する。経路管理テーブル４４は、優先方路決定装置１０から通知された優先方路の情報を含む経路の情報を格納する。インタフェース４１は、経路情報に紐付けられた経路のＯＮ／ＯＦＦの情報および優先方路決定装置１０から通知される優先方路の情報をＧＷルータＧ０を経由してＲＩＮＤを利用して受信する。
【００２７】
＜優先方路の決定＞
次に、図３〜図７を参照して優先方路を決定する手順について説明する。図３〜図７は、優先方路決定方法の手順の一例を示す図である。なお、図３〜図７において、ノード間を接続する破線は、無線リンクを表している。すなわち、破線により互いに接続される１組のノードは、互いに無線信号を送受信できる。また、ノード間を接続する実線は、無線リンクを利用して設定された優先方路を表している。
【００２８】
ノード設定部１２は、マルチホップノードとして動作し得る全てのルータＭ１〜ルータＭ８をそれぞれ最終宛先ノードとして設定する。経路選択部１３は、ゲートウェイノードとして動作し得るＧＷルータＧ０と、最終宛先ノードとして動作し得るルータＭ１〜ルータＭ８との間の経路を通信コスト情報２３に格納されている通信コストに基づいて選択する。このとき、ＧＷルータＧ０と各ルータＭ１〜Ｍ８との間で、それぞれ、通信コストが最小の経路が選択される。なお、ゲートウェイノードと最終宛先ノード間の経路の選択は、通信コストに基づいてループの発生を考慮せずに仮に設定されるものである。
【００２９】
以下、図３〜図７の説明において、ゲートウェイノードを「Ｇ０」、マルチホップノードを「Ｍ１〜Ｍ８」と省略する。
【００３０】
図３に示すように、ノード設定部１２により、ルータＭ１、ルータＭ２、ルータＭ３が最終宛先ノードとして設定されている場合について考える。この場合、経路選択部１３は、ＧＷルータＧ０と、各ルータＭ１〜Ｍ３との経路を通信コスト情報２３に格納されている通信コストに基づいて選択する。
【００３１】
図３〜図７の例では、経路選択部１３により、通信コストに基づいて、経路「Ｇ０−Ｍ１」、「Ｇ０−Ｍ２」、「Ｇ０−Ｍ３」がそれぞれ選択されている。経路「Ｇ０−Ｍ１」のうち、「Ｇ０」について考えると、図３に示すように、ゲートウェイノード「Ｇ０」の次ホップ宛先ノード「Ｍ１」と最終宛先ノード「Ｍ１」とが一致する。この場合、優先方路決定部１５は、ＧＷルータＧ０を最終中継ノードとして、ゲートウェイノード「Ｇ０」と、最終宛先ノード「Ｍ１」との間の経路「Ｇ０−Ｍ１」を優先方路として決定する。より具体的には、優先方路決定部１５は、ＧＷルータＧ０において、ゲートウェイノードである「Ｇ０」から最終宛先ノードである「Ｍ１」に向かう経路を下り優先方路として決定する。同様に、優先方路決定部１５は、「Ｇ０」から「Ｍ２」に向かう経路、「Ｇ０」から「Ｍ３」に向かう経路をそれぞれ下り優先方路として決定する。決定した優先方路の情報はノード管理テーブル２２に格納される。ノード管理テーブル２２は、各ＧＷルータＧ０、ルータＭ１〜Ｍ８毎に対応するノード情報２２−０〜２２−８が格納されている。ノード情報２２−０〜２２−８は、それぞれ、優先方路の情報および中継ノードの情報を含む。なお、図３〜図５、図７の図中のノード情報２２−０〜２２−８の説明において、最終宛先ノードを「宛」、前ホップのノードを「前」、次ホップのノードを「次」と省略する。
【００３２】
「Ｍ１」について考えると、自ノード「Ｍ１」が最終宛先ノードとなるので、優先方路決定部１５は、前ホップであるゲートウェイノード「Ｇ０」に向かう経路を上り優先方路として決定する。同様に、優先方路決定部１５は、「Ｍ２」から「Ｇ０」に向かう経路、「Ｍ３」から「Ｇ０」に向かう経路をそれぞれ上り優先方路として決定する。
【００３３】
また、図４、図５に示すように、ノード設定部１２により、ルータＭ４〜Ｍ８が最終宛先ノードとして設定されている場合について考える。この場合、経路選択部１３は、ＧＷルータＧ０と、各ルータＭ４〜Ｍ８との経路を通信コスト情報２３に格納されている通信コストに基づいて選択する。
【００３４】
図４、図５の例では、通信コストに基づいて、経路選択部１３により、経路「Ｇ０−Ｍ１−Ｍ４」、「Ｇ０−Ｍ２−Ｍ５」、「Ｇ０−Ｍ２−Ｍ６」、「Ｇ０−Ｍ３−Ｍ７」、「Ｇ０−Ｍ３−Ｍ８」が選択されている。
【００３５】
図４に示すように、経路「Ｇ０−Ｍ１−Ｍ４」のうち、「Ｇ０」について考えると、ゲートウェイノード「Ｇ０」の次ホップ宛先ノード「Ｍ１」と最終宛先ノード「Ｍ４」とが一致しない。この場合、中継ノード決定部１４は、次ホップ宛先ノード「Ｍ１」を中継ノードとして決定する。その他の経路が選択された場合も、同様に、中継ノード決定部１４は、次ホップ宛先ノード「Ｍ２」、「Ｍ３」を中継ノードとして決定する。中継ノード決定部１４は、決定した中継ノードの情報をノード情報２２−０に格納する。
【００３６】
決定された中継ノード「Ｍ１」について考えると、中継ノード「Ｍ１」の次ホップ宛先ノード「Ｍ４」と最終宛先ノード「Ｍ４」とが一致する。この場合、中継ノード決定部１４は、最終宛先ノード「Ｍ４」の前ホップ「Ｍ１」を最終中継ノードとして決定する。優先方路決定部１５は、決定した最終中継ノード「Ｍ１」と、最終宛先ノード「Ｍ４」との間の経路「Ｍ１−Ｍ４」を優先方路として決定する。より具体的には、優先方路決定部１５は、ルータＭ１において、最終中継ノードであるルータＭ１から最終宛先ノードである「Ｍ４」に向かう経路を下り優先方路として決定する。
【００３７】
その他の経路が選択された場合も、同様に、優先方路決定部１５は、各最終宛先ノードに向かう経路を下り優先方路として決定する。優先方路決定部１５は、決定した下り優先方路の情報をノード情報２２−１〜２２−３に格納する。
【００３８】
図５に示すように、最終宛先ノード「Ｍ４」について考えると、自ノード「Ｍ４」が最終宛先ノード「Ｍ４」と一致する。この場合、優先方路決定部１５は、最終宛先ノード「Ｍ４」の前ホップである最終中継ノード「Ｍ１」に向かう経路を上り優先方路として決定する。その他の経路が選択された場合も、同様に、優先方路決定部１５は、各最終中継ノードに向かう経路を上り優先方路として決定する。優先方路決定部１５は、決定した上り優先方路の情報をノード情報２２−４〜２２−８に格納する。
【００３９】
図３〜図５において説明した上りの優先方路の情報をまとめると、図６のようになる。図６は、各ノードに対応するノード情報２２−０〜２２−８に中の優先方路の情報を示す図である。図６に示すように、優先方路決定部１５は、ノード毎に、優先方路の情報を有する。図６の図中のノード情報２２−０〜２２−８の説明において、上りの優先方路を「上」、下りの優先方路を「下」と省略する。優先方路決定部１５で決定され、ノード情報２２−０〜２２−８に格納された優先方路の情報は、ＲＩＮＤを利用してＧＷルータＧ０、各ルータＭ１〜Ｍ８へ通知される。
【００４０】
例えば、ゲートウェイノード「Ｇ０」のノード情報２２−０は、下り優先方路の情報として、「Ｍ１」「Ｍ２」「Ｍ３」を表している。マルチホップノード「Ｍ１」のノード情報２２−１は、上り優先方路の情報として「Ｇ０」、下り優先方路の情報として「Ｍ４」を表している。マルチホップノード「Ｍ４」のノード情報２２−４は、上り優先方路の情報として「Ｍ１」を表している。
【００４１】
ここで、マルチホップノード「Ｍ４」に接続された端末４からゲートウェイノード「Ｇ０」にパケットが送信される場合について考える。
【００４２】
はじめに、ルータＭ４は、送信パケットにゲートウェイノードのＩＰアドレスを付与する。また、ルータＭ４は、ノード情報２２−４に基づいて、送信パケットにマルチホップノード「Ｍ４」の上り優先方路として決定されている「Ｍ１」のＭＡＣアドレスを付与する。そして、ルータＭ４は、上り優先方路「Ｍ１」を介して、マルチホップノード「Ｍ１」へパケットを送信する。
【００４３】
ルータＭ１は、到着パケットのＭＡＣアドレスが「Ｍ１」であるので、そのパケットを受信する。そして、ルータＭ１は、そのパケットの宛先ＩＰアドレスがゲートウェイノードであることを検出すると、ノード情報２２−１に基づいて、そのパケットにマルチホップノード「Ｍ１」の上り優先方路として決定されている「Ｇ０」のＭＡＣアドレスを付与する。そして、ルータＭ１は、上り優先方路を介して、ゲートウェイノード「Ｇ０」へパケットを送信する。
【００４４】
このように、端末４から送信されたパケットは、経路「Ｍ４−Ｍ１−Ｇ０」を介してゲートウェイノードまで転送される。すなわち、端末４から送信されたパケットは、ルータＭ４の上り優先方路およびルータＭ１の上り優先方路を介して、ゲートウェイノードまで転送される。ここで、各優先方路は、ゲートウェイノードを基準としてツリーを構成するように決定される。したがって、この無線通信システムでは、ループが回避される。
【００４５】
＜優先方路の再構築について＞
図７に示す例では、図３〜図６に示す例と比較すると、ルータＭ８の配置が変化している。すなわち、図７に示す例では、ルータＭ８は、ルータＭ３には隣接しておらず、ルータＭ６、Ｍ７に隣接している。この場合、優先方路決定装置１０は、ルータＭ８について優先方路を決定する。
【００４６】
この実施例では、経路選択部１３は、ゲートウェイノード「Ｇ０」と最終宛先ノード「Ｍ８」との間の経路として「Ｇ０−Ｍ３−Ｍ６−Ｍ８」を選択するものとする。ただし、この経路は、ループの発生を考慮していないので、場合によってはループが発生する可能性がある。
【００４７】
中継ノード決定部１４は、経路選択部１３により選択された経路を１ホップずつ進んで最終中継ノードを探索する。具体的には、ゲートウェイノード「Ｇ０」の次ホップであるマルチホップノード「Ｍ３」が最終宛先ノード「Ｍ８」と一致しないので、次ホップが探索される。続いて、マルチホップノード「Ｍ３」の次ホップであるマルチホップノード「Ｍ６」が最終宛先ノード「Ｍ８」と一致しないので、次ホップが探索される。この後、マルチホップノード「Ｍ６」の次ホップであるマルチホップノード「Ｍ８」が最終宛先ノード「Ｍ８」と一致するので、マルチホップノード「Ｍ６」が最終中継ノードとして決定される。
【００４８】
そうすると、マルチホップノード「Ｍ８」の上り優先方路として「Ｍ８」から「Ｍ６」に向かう経路が選択される。ここで、ノード情報２２−６によれば、マルチホップノード「Ｍ６」の上り優先方路として「Ｍ６」から「Ｍ２」に向かう経路が選択されている。また、図４に示すように、ノード情報２２−２によれば、マルチホップノード「Ｍ２」の上り優先方路として「Ｍ２」から「Ｇ０」に向かう経路が選択されている。よって、ルータＭ８からＧＷルータＧ０へ送信されるパケットは、マルチホップノードＭ８、Ｍ６、Ｍ２に対して選択されている優先方路を介して伝送される。
【００４９】
このように、ノードの配置が変化した場合には、新たな経路が再構築される。そして、再構築される経路は、１または複数の優先方路により構成される。したがって、ツリー構成の経路が実現され、ループが回避される。
【００５０】
図８、図９は、優先方路を決定する優先方路決定方法の一例を示すフローチャートである。
【００５１】
Ｓ１１において、ノード設定部１２は、各ルータＭ１〜Ｍｎをそれぞれ最終宛先ノードとして設定する。Ｓ１２において、経路選択部１３は、ゲートウェイノードと最終宛先ノードとの間の経路を、通信コスト情報２３に基づいて選択する。ゲートウェイノードと最終宛先ノードとの間の経路は、通信コストに基づいて仮に選択されるものである。したがって、経路選択部１３によって選択された経路はループの発生を考慮していないので、場合によってはループが発生する可能性がある。
【００５２】
Ｓ１３において経路選択部１３は、ゲートウェイノードの次ホップ宛先ノードと最終宛先ノードとが一致するか否か判定する。ゲートウェイノードの次ホップ宛先ノードと最終宛先ノードとが一致しない場合（Ｓ１３：Ｎｏ）、すなわち、自ホップがＧＷルータＧ０ではない場合には、Ｓ１４において、中継ノード決定部１４は、最終中継ノード決定処理を行う。この処理では、中継ノード決定部１４は、選択した経路の最終中継ノードを決定する処理を行う。最終中継ノード決定処理の詳細については、図９を参照して後述する。Ｓ１５において、優先方路決定部１５は、Ｓ１４で決定した最終中継ノードと最終宛先ノードとの間の経路を優先方路として決定する。この処理が終了すると処理はＳ１７に進む。
【００５３】
一方、ゲートウェイノードの次ホップ宛先ノードと最終宛先ノードとが一致する場合（Ｓ１３：Ｙｅｓ）、すなわち、自ホップがＧＷルータＧ０である場合には、Ｓ１６において、優先方路決定部１５は、ゲートウェイノードを最終中継ノードとして、ゲートウェイノードと最終宛先ノードとの間の経路を優先方路として決定する。この処理が終了すると処理はＳ１７に進む。
【００５４】
Ｓ１７において、経路選択部１３は最終宛先ノードとして設定された全ての経路についてＳ１２において選択されたか否か判定する。選択されていない経路が残っている場合（Ｓ１７：Ｎｏ）には、処理はＳ１２に戻り、全ての経路が選択されるまでＳ１２〜Ｓ１７の処理が繰り返し実行される。これに対し、全ての経路が選択された場合（Ｓ１７：Ｙｅｓ）には、優先方路決定方法の処理は終了する。
【００５５】
図９を参照して最終中継ノード決定処理の詳細について説明する。
Ｓ２１において、中継ノード決定部１４は、Ｓ１２で選択された経路を構築するノードの次ホップのノードを選択する。Ｓ２２において、中継ノード決定部１４は、次ホップ宛先ノードと最終宛先のノードとが一致するか否か判定する。次ホップ宛先ノードと最終宛先のノードとが一致しない場合（Ｓ２２：Ｎｏ）には、中継ノード決定部１４は、次ホップ宛先ノードを中継ノードとして決定し、Ｓ２１の処理に戻る。そして、中継ノード決定部１４は、次ホップ宛先ノードと最終宛先のノードとが一致するまでＳ２１〜Ｓ２３の処理を繰り返し実行する。
【００５６】
次ホップ宛先ノードと最終宛先のノードとが一致した場合（Ｓ２２：Ｙｅｓ）には、Ｓ２４において、中継ノード決定部１４は、最終宛先ノードの前ホップを最終中継ノードとして決定する。この処理が終了すると、最終中継ノード決定処理は終了となり、処理はＳ１５の処理に進む。
【００５７】
＜ハードウェア構成＞
優先方路決定装置１０は、プロセッサを備える。そして、ノード設定部１２、経路選択部１３、中継ノード決定部１４、優先方路決定部１５は、プロセッサを用いて優先方路決定プログラムを実行することにより実現される。この場合、優先方路決定プログラムは、プロセッサがアクセス可能なメモリ領域に格納される。なお、ノード設定部１２、経路選択部１３、中継ノード決定部１４、優先方路決定部１５の機能の一部は、ハードウェア回路で実現してもよい。
【符号の説明】
【００５８】
１  無線通信システム
Ｇ０  ＧＷルータ
Ｍ１〜Ｍｎ  ルータ
４  端末
１０  優先方路決定装置
１１  ＩＦ
１２  ノード設定部
１３  経路選択部
１４  中継ノード決定部
１５  優先方路決定部
２１  メモリ
２２  ノード管理テーブル
２３  通信コスト情報
３１  ＩＦ
３２  周辺環境測定部
３３  経路管理部
３４  経路管理テーブル
４１  ＩＦ
４２  周辺環境測定部
４３  経路管理部
４４  経路管理テーブル
【図１】
2019121923.tif 000003
【図２】
2019121923.tif 000004
【図３】
2019121923.tif 000005
【図４】
2019121923.tif 000006
【図５】
2019121923.tif 000007
【図６】
2019121923.tif 000008
【図７】
2019121923.tif 000009
【図８】
2019121923.tif 000010
【図９】
2019121923.tif 000011