(57)【要約】【課題】無線マルチホップネットワークにおいてフラッディングの効率を改善する。【解決手段】無線通信装置は、複数のノードを含む無線ネットワークにおいて使用され、干渉点ノード特定部、中継ノード特定部、グループ化部、設定部、通知部を備える。干渉点ノード特定部は、複数の中継ノードからパケットが到達する干渉点ノードを特定する。中継ノード特定部は、各干渉点ノードについて、当該干渉点ノードに到達するパケットを送信する中継ノードを特定する。グループ化部は、同じ干渉点ノードにパケットを送信する２以上の中継ノードが互いに異なるグループに属するように中継ノードをグループ化する。設定部は、各グループに対して異なる送信タイミングを設定する。通知部は、設定部により設定された送信タイミングを各中継ノードに通知する。【選択図】図４
2020145634.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを含む無線ネットワークにおいて使用される無線通信装置であって、
前記複数のノードのうちの、ブロードキャスト転送を実行する各中継ノードについて、前記ブロードキャスト転送により送信されるパケットを受信するノードを表す経路情報を保存する保存部と、
前記経路情報に基づいて、複数の中継ノードからパケットが到達する干渉点ノードを特定する干渉点ノード特定部と、
各干渉点ノードについて、当該干渉点ノードに到達するパケットを送信する中継ノードを特定する中継ノード特定部と、
同じ干渉点ノードにパケットを送信する２以上の中継ノードが互いに異なるグループに属するように、前記中継ノード特定部により特定された中継ノードをグループ化するグループ化部と、
各グループに対して異なる送信タイミングを設定する設定部と、
前記設定部により設定された送信タイミングを前記中継ノード特定部により特定された各中継ノードに通知する通知部と、
を備える無線通信装置。
【請求項２】
前記グループ化部は、同じ干渉点ノードにパケットを送信する２以上の中継ノードが互いに異なるグループに属し、且つ、同じ干渉点ノードにパケットを送信しない２以上の中継ノードが同じグループに属するように、前記中継ノード特定部により特定された中継ノードをグループ化する
ことを特徴とする請求項１に記載の無線通信装置。
【請求項３】
複数のノードを含む無線ネットワークにおいて使用される無線通信装置において、
前記複数のノードのうちの、ブロードキャスト転送を実行する各中継ノードについて、前記ブロードキャスト転送により送信されるパケットを受信するノードを表す経路情報に基づいて、複数の中継ノードからパケットが到達する干渉点ノードを特定し、
各干渉点ノードについて、当該干渉点ノードに到達するパケットを送信する中継ノードを特定し、
同じ干渉点ノードにパケットを送信する２以上の中継ノードが互いに異なるグループに属するように、前記中継ノードをグループ化し、
各グループに対して異なる送信タイミングを設定し、
前記送信タイミングを各中継ノードに通知する
処理をプロセッサに実行させる通信制御プログラム。
【請求項４】
ゲートウェイノードおよび複数のノードを含む無線通信システムであって、
前記ゲートウェイノードは、
前記複数のノードのうちの、ブロードキャスト転送を実行する各中継ノードについて、前記ブロードキャスト転送により送信されるパケットを受信するノードを表す経路情報を保存する保存部と、
前記経路情報に基づいて、複数の中継ノードからパケットが到達する干渉点ノードを特定する干渉点ノード特定部と、
各干渉点ノードについて、当該干渉点ノードに到達するパケットを送信する中継ノードを特定する中継ノード特定部と、
同じ干渉点ノードにパケットを送信する２以上の中継ノードが互いに異なるグループに属するように、前記中継ノード特定部により特定された中継ノードをグループ化するグループ化部と、
各グループに対して異なる送信タイミングを設定する設定部と、
前記設定部により設定された送信タイミングを前記中継ノード特定部により特定された各中継ノードに通知する通知部と、を備え、
前記中継ノードとして特定された各ノードは、前記通知部により通知される送信タイミングに基づいて、受信パケットをブロードキャスト転送する
ことを特徴とする無線通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線マルチホップネットワークにおけるフラッディング技術に係わる。
【背景技術】
【０００２】
複数のノードを備える無線ネットワークにおいて、マルチホップ方式で全ノードに情報を送信する技術の１つとして、フラッディングが実用化されている。フラッディングにおいては、以下の手順のよりパケットが送信される。
（１）送信元ノードは、パケットをブロードキャストする。
（２）パケットを受信した各ノードは、中継ノードとして、そのパケットをブロードキャストする（マルチホップ転送）。
（３）ただし、各ノードは、過去に受信したパケットと同じパケットを新たに受信したときは、その新たに受信パケットを中継しない（重複送信の回避）。
【０００３】
フラッディングは、上述の手順により、無線ネットワーク内の全ノードに効率よく情報を送信できる。ただし、複数のノードがブロードキャストを行うので、ノード数の多い無線ネットワークにおいては、パケット衝突に起因してパケット損失率が大きくなるおそれがある。また、冗長なパケットの送信により不要なトラフィックが発生し、無線ネットワーク全体の効率が低下するおそれがある。
【０００４】
これらの問題は、例えば、必要最小限の数のノードのみがパケットを中継することで緩和され得る。例えば、ＯＬＳＲ（Optimized Link State Routing）プロトコルを使用する無線マルチホップネットワークにおいて、選択されたノードのみがブロードキャスト転送を実行するフラッディング方法が提案されている。なお、ブロードキャスト転送を実行するために選択されるノードは、ＭＰＲ（multipoint relay）と呼ばれる。ＭＰＲを選択してフラッディングを行う方法は、例えば、特許文献１および非特許文献１〜２に記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第５１３６４３４号
【非特許文献】
【０００６】
【非特許文献１】IETF MANET RFC3626 (October 2003)
【非特許文献２】ＯＬＳＲ（Optimized Link State Routing）プロトコル、https://internet.watch.impress.co.jp/www/column/wp2p/wp2p06.htm
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述のように、選択されたノード（すなわち、ＭＰＲノード）のみがブロードキャスト転送を実行するフラッディングにおいては、不要なトラフィックが削減されて通信効率が改善する。ただし、ＭＰＲノードの数が少な過ぎると、無線ネットワーク内の全ノードに情報を到達しないおそれがある。このため、無線ネットワーク内の全ノードに確実に情報を配布するためには、マージンを含む数のＭＰＲノードが選択されることが好ましい。しかし、このようなポリシでＭＰＲノードを選択すると、一部のノードは、複数のＭＰＲノードから無線電波を受信することになる。この場合、無線電波の干渉によりエラーが発生し、次段のノードにパケットを転送できないことがある。
【０００８】
本発明の１つの側面に係わる目的は、無線マルチホップネットワークにおいてフラッディングの効率を改善することである。
【課題を解決するための手段】
【０００９】
本発明の１つの態様の無線通信装置は、複数のノードを含む無線ネットワークにおいて使用される。この無線通信装置は、前記複数のノードのうちの、ブロードキャスト転送を実行する各中継ノードについて、前記ブロードキャスト転送により送信されるパケットを受信するノードを表す経路情報を保存する保存部と、前記経路情報に基づいて、複数の中継ノードからパケットが到達する干渉点ノードを特定する干渉点ノード特定部と、各干渉点ノードについて、当該干渉点ノードに到達するパケットを送信する中継ノードを特定する中継ノード特定部と、同じ干渉点ノードにパケットを送信する２以上の中継ノードが互いに異なるグループに属するように、前記中継ノード特定部により特定された中継ノードをグループ化するグループ化部と、各グループに対して異なる送信タイミングを設定する設定部と、前記設定部により設定された送信タイミングを前記中継ノード特定部により特定された各中継ノードに通知する通知部と、を備える。
【発明の効果】
【００１０】
上述の態様によれば、無線マルチホップネットワークにおいてフラッディングの効率が改善する。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に係わる無線通信システムの一例を示す図である。
【図２】フラッディングの一例を示す図である。
【図３】ＭＰＲノードを利用したフラッディングの一例を示す図である。
【図４】本発明の実施形態に係わる無線通信装置の一例を示す図である。
【図５】隣接ノード情報およびフラッディング経路表の一例を示す図である。
【図６】相互干渉テーブルおよびフラッディング順序テーブルの一例を示す図である。
【図７】相互干渉テーブルを作成する処理の一例を示すフローチャートである。
【図８】送信元中継ノードのグループ化の一例を示すフローチャートである。
【図９】本発明の実施形態に係わる無線端末装置の一例を示す図である。
【図１０】無線端末装置の動作の一例を示すフローチャートである。
【図１１】本発明の実施形態に係わる通信方法の一例を示す。
【発明を実施するための形態】
【００１２】
図１は、本発明の実施形態に係わる無線通信システムの一例を示す。無線通信システム１００は、複数のノードを含み、マルチホップ方式でパケットを伝送する。この実施例では、無線通信システム１００は、ＯＬＳＲプロトコルに従ってパケットを伝送するものとする。
【００１３】
無線通信システム１００は、ゲートウェイノード１および複数のノード２ａ〜２ｅ、２ｐ〜２ｖを備える。なお、以下の記載では、ノード２ａ〜２ｅ、２ｐ〜２ｖのうちの任意のノードを「ノード２」と呼ぶことがある。
【００１４】
ゲートウェイノード１には、無線通信装置が実装される。無線通信装置は、無線信号を送信できる。また、無線通信装置は、隣接ノードから送信される無線信号を受信できる。さらに、無線通信装置は、フラッディングにより、全ノード２ａ〜２ｅ、２ｐ〜２ｖに情報を配布する。なお、以下の記載では、ゲートウェイノード１に実装されている無線通信装置を「ゲートウェイノード」と呼ぶことがある。
【００１５】
各ノード２には、無線端末装置が実装される。無線端末装置は、無線信号を送信できる。また、無線端末装置は、隣接ノードから送信される無線信号を受信できる。さらに、無線端末装置は、隣接ノードから受信した信号を他のノードに転送できる。すなわち、無線端末装置は、中継ノードとして動作することがある。例えば、ゲートウェイノード１によりフラッディングが行われるときは、無線端末装置は、隣接ノードから受信するフラッディングパケットをブロードキャスト転送する。なお、以下の記載では、ノード２に実装されている無線端末装置を「ノード」と呼ぶことがある。
【００１６】
上記構成の無線通信システム１００において、各ノード２は、定期的に、Ｈｅｌｌｏパケットをブロードキャストする。Ｈｅｌｌｏパケットは、自分の存在を隣接ノードに通知するための制御パケットである。よって、各ノード２は、受信したＨｅｌｌｏパケットの送信元を特定することにより、自分に隣接するノードを認識できる。そして、各ノード２は、自分に隣接するノードを表す隣接ノード情報を作成し、自ノード内のメモリに保存する。また、各ノード２により作成される隣接ノード情報は、ノード間で交換される。よって、各ノード２は、自ノードからカウントして２ホップ先のノードを認識できる。
【００１７】
各ノード２により作成される隣接ノード情報は、ゲートウェイノード１に送信される。すなわち、ゲートウェイノード１は、各ノード２において作成される隣接ノード情報を収集する。したがって、ゲートウェイノード１は、無線通信システム１００のトポロジを認識できる。
【００１８】
図２は、フラッディングの一例を示す。図２に示す例では、ゲートウェイノード１が全ノード２ａ〜２ｅ、２ｐ〜２ｖに情報を配布する。すなわち、ゲートウェイノード１は、フラッディングパケットを送信する。ただし、ゲートウェイノード１から送信されるフラッディングパケットは、ノード２ａ〜２ｅに到達するが、ノード２ｐ〜２ｖには到達しない。なお、フラッディングパケットには、例えば、宛先アドレスとしてブロードキャストアドレスが設定される。
【００１９】
各ノード２ａ〜２ｅは、ゲートウェイノード１から受信したフラッディングパケットをブロードキャスト転送する。このとき、ノード２ａから送信されるフラッディングパケットは、ノード２ｐ〜２ｒに到達する。同様に、ノード２ｂから送信されるフラッディングパケットはノード２ｑ〜２ｓに到達し、ノード２ｃから送信されるフラッディングパケットはノード２ｒ〜２ｔに到達し、ノード２ｄから送信されるフラッディングパケットはノード２ｓ〜２ｕに到達し、ノード２ｅから送信されるフラッディングパケットはノード２ｔ〜２ｖに到達する。これにより、ゲートウェイノード１から送信される情報が全ノード２ａ〜２ｅ、２ｐ〜２ｖにより受信される。
【００２０】
なお、ノード２ａから送信されるフラッディングパケットは、ノード２ｐ〜２ｒ以外のノードにも到達し得る。例えば、ノード２ａから送信されるフラッディングパケットは、ゲートウェイノード１に到達する。ただし、このフラッディングパケットに含まれる情報は、ゲートウェイノード１が送信した情報と同じである。よって、この場合、ゲートウェイノード１は、ノード２ａから受信したフラッディングパケットを転送しない。また、ノード２ａから送信されるフラッディングパケットは、ノード２ｂに到達するものとする。ただし、このフラッディングパケットに含まれる情報は、ノード２ｂが先に受信した情報と同じである。よって、この場合、ノード２ｂは、ノード２ａから受信したフラッディングパケットの再転送を行わない。
【００２１】
このように、図２に示す例では、フラッディングパケットを受信した各ノード２がそのフラッディングパケットをブロードキャスト転送（再転送を除く）する。具体的には、ノード２ａ〜２ｅがそれぞれブロードキャスト転送を行う。このため、パケットの衝突が起こりやすく、また、通信効率が低下することがある。
【００２２】
これらの問題は、例えば、ＭＰＲノードを選択することにより緩和される。ＭＰＲノードは、ノード２ａ〜２ｅ、２ｐ〜２ｖの中から選択され、ブロードキャスト転送を実行する。すなわち、ＭＰＲノードは、フラッディングにおける中継ノードの一例である。尚、ＭＰＲノードとして選択されなかったノード２は、フラッディングパケットを受信してもブロードキャスト転送を実行しない。
【００２３】
図３は、ＭＰＲノードを利用したフラッディングの一例を示す。図３に示す例では、ノード２ａ、２ｃ、２ｅがＭＰＲノードとして選択されている。
【００２４】
ゲートウェイノード１は、図２に示すケースと同様に、フラッディングパケットを送信する。そして、ゲートウェイノード１から送信されるフラッディングパケットは、ノード２ａ〜２ｅに到達する。
【００２５】
ノード２ａ、２ｃ、２ｅは、それぞれゲートウェイノード１から受信したフラッディングパケットを転送する。このとき、ノード２ａから送信されるフラッディングパケットはノード２ｐ〜２ｒに到達し、ノード２ｃから送信されるフラッディングパケットはノード２ｒ〜２ｔに到達し、ノード２ｅから送信されるフラッディングパケットはノード２ｔ〜２ｖに到達する。したがって、ゲートウェイノード１から送信される情報が全ノード２ａ〜２ｅ、２ｐ〜２ｖにより受信される。
【００２６】
なお、ＭＰＲノードを選択する方法は、特に限定されるものではない。たとえば、各ノード２に対して予めWillingness値が設定されているときは、無線通信システム１００のトポロジおよび各ノード２のWillingness値に基づいてＭＰＲノードが選択される。ここで、Willingness値は、パケット転送を行うことについての積極度を表す。この場合、ゲートウェイノード１は、Willingness値の大きいノード２から順番にＭＰＲノードを選択する。あるいは、ゲートウェイノード１は、隣接ノード数の多いノード２から順番にＭＰＲノードを選択してもよい。いずれにしても、すべてのノード２にフラッディングパケットが到達するように、必要な数なＭＰＲノードが選択される。
【００２７】
他方、上述のフラッディング手順において、ノード２ｂ、２ｄは、ブロードキャスト転送を行わない。したがって、図２に示すケースと比較すると、パケット衝突の発生確率は低下し、通信効率が改善し得る。
【００２８】
しかし、ＭＰＲノードを利用してフラッディングを行う場合であっても、パケット衝突を無くすことは困難である。例えば、すべてのノード２に確実にフラッディングパケットを到達させるためには、各ノード２が少なくとも１つのＭＰＲノードからパケットを受信するようにＭＰＲノードを選択する必要がある。そして、このようなポリシでＭＰＲノードを選択すると、幾つかのノードが複数のＭＰＲノードからパケットを受信する可能性が高くなる。図３に示すケースでは、ノード２ｒにおいて、ノード２ａから送信される無線電波とノード２ｃから送信される無線電波との干渉が発生し得る。また、ノード２ｔにおいて、ノード２ｃから送信される無線電波とノード２ｅから送信される無線電波との干渉が発生し得る。そして、このような干渉が発生すると、干渉点に実装される無線端末装置は、フラッディングされた情報を取得できない。
【００２９】
本発明の実施形態に係わる通信方法は、上述の問題を解決または緩和する機能を提供する。一例としては、フラッディングにおいて干渉が発生し得るノード（以下、干渉点ノード）が存在するときは、その干渉点ノードにパケットを送信する複数の中継ノード間で送信タイミングが調整される。
【００３０】
図４は、本発明の実施形態に係わる無線通信装置の一例を示す。無線通信装置１０は、図１に示す無線通信システム１００においては、ゲートウェイノード１に実装される。なお、無線通信装置１０は、例えば、不図示のサーバコンピュータに接続される。また、無線通信システム１００は、複数の無線通信装置１０を備えてもよい。
【００３１】
無線通信装置１０は、図４に示すように、無線送受信部１１、受信処理部１２、通信制御部１３、送信処理部１９、保存部２０を備える。ただし、無線通信装置１０は、図４に示していない他の回路または機能を備えてもよい。
【００３２】
無線送受信部１１は、隣接ノードから送信される無線信号を受信する。また、無線送受信部１１は、無線信号を送信する。受信処理部１２は、受信信号を復号してパケットを再生する。そして、受信信号から再生されたパケット（すなわち、受信パケット）は、通信制御部１３に渡される。送信処理部１９は、送信パケットから送信信号を生成して無線送受信部１１に渡す。
【００３３】
通信制御部１３は、無線通信装置１０の動作を制御する。また、通信制御部１３は、無線通信システム１００におけるフラッディング手順を制御するために、干渉点ノード特定部１４、中継ノード特定部１５、グループ化部１６、設定部１７、通知部１８を備える。なお、通信制御部１３は、この実施例では、プロセッサにより実現される。この場合、干渉点ノード特定部１４、中継ノード特定部１５、グループ化部１６、設定部１７、通知部１８の機能は、プロセッサが通信制御プログラムを実行することにより提供される。
【００３４】
保存部２０は、通信制御部１３が使用する情報を格納する。この実施例では、保存部２０には、隣接ノード情報２１、フラッディング経路表２２、相互干渉テーブル２３、フラッディング順序テーブル２４が格納される。また、保存部２０は、プロセッサ（即ち、通信制御部１３）により実行される通信制御プログラムを格納する。
【００３５】
隣接ノード情報２１は、図５（ａ）に示すように、無線通信システム１００内の各ノードについて隣接ノードを表す。たとえば、隣接ノード情報２１の第１レコードは、ゲートウェイノード１の隣接ノードがノード２ａ、２ｂ、２ｃ、２ｄ、２ｅであること表している。また、隣接ノード情報２１の第２レコードは、ノード２ａの隣接ノードがゲートウェイノード１、およびノード２ｐ、２ｑ、２ｒであること表している。なお、隣接ノード情報２１は、各ノード２ａ〜２ｅ、２ｐ〜２ｖにおいて作成される隣接ノード情報に基づいて作成される。各ノード２ａ〜２ｅ、２ｐ〜２ｖは、上述したように、隣接ノードから送信されるＨｅｌｌｏパケットを検知することで自ノードに隣接するノードを認識できる。
【００３６】
フラッディング経路表２２は、図５（ｂ）に示すように、各ＭＰＲノードについて、フラッディングパケットの受信ノードを表す。この実施例では、無線通信装置１０により、ノード２ａ、２ｃ、２ｅがＭＰＲノードとして選択されている。そして、フラッディング経路表２２は、ノード２ａ、２ｃ、２ｅそれぞれについて、フラッディング時にブロードキャスト転送されるパケットが到達するノードを表している。具体的には、フラッディング経路表２２は、ノード２ａから送信されるパケットがノード２ｐ〜２ｒに到達することを表し、ノード２ｃから送信されるパケットがノード２ｒ〜２ｔに到達することを表し、ノード２ｅから送信されるパケットがノード２ｔ〜２ｖに到達することを表している。
【００３７】
フラッディング経路表２２は、たとえば、ＭＰＲノードを選択する処理の中で作成される。ここで、ＭＰＲノードの選択およびフラッディング経路表２２の作成の一例を示す。ここで、各ノード２が上述したWillingness値を有しているものとする。
【００３８】
（１）無線通信装置１０は、無線通信装置１０に隣接するノード（即ち、２ａ〜２ｅ）の中から、最も大きなWillingness値を有するノードを選択する。ここでは、ノード２ａが選択されるものとする。この場合、ノード２ａは、ＭＰＲノードとしてフラッディング経路表２２の第１レコードに登録される。また、無線通信装置１０は、隣接ノード情報２１を参照してノード２ａの隣接ノードを特定する。この場合、ノード２ｐ〜２ｒが特定される。そして、特定された隣接ノード（即ち、ノード２ｐ〜２ｒ）は、フラッディング経路表２２において、ノード２ａに対応づけられて受信ノードとして登録される。
【００３９】
（２）無線通信装置１０は、無線通信装置１０に隣接するノード以外のノードの中で、フラッディング経路表２２に登録されてないノードが残っているか否かを判定する。この例では、ノード２ｓ〜２ｖが残っている。よって、無線通信装置１０は、次のＭＰＲノードを選択する処理を実行する。
【００４０】
（３）次のＭＰＲノードとして、ノード２ｃが選択されるものとする。この場合、ノード２ｃは、ＭＰＲノードとしてフラッディング経路表２２の第２レコードに登録される。また、無線通信装置１０は、隣接ノード情報２１を参照してノード２ｃの隣接ノードを特定する。この場合、ノード２ｒ〜２ｔが特定される。そして、特定された隣接ノード（即ち、ノード２ｒ〜２ｔ）は、フラッディング経路表２２においてノード２ｃに対応づけられて受信ノードとして登録される。
【００４１】
（４）無線通信装置１０は、無線通信装置１０に隣接するノード以外のノードの中で、フラッディング経路表２２に登録されてないノードが残っているか否かを判定する。この例では、ノード２ｕ〜２ｖが残っている。よって、無線通信装置１０は、次のＭＰＲノードを選択する処理を実行する。
【００４２】
（５）次のＭＰＲノードとして、ノード２ｅが選択されるものとする。この場合、ノード２ｅは、ＭＰＲノードとしてフラッディング経路表２２の第３レコードに登録される。また、無線通信装置１０は、隣接ノード情報２１を参照してノード２ｅの隣接ノードを特定する。この場合、ノード２ｔ〜２ｖが特定される。そして、特定された隣接ノード（即ち、ノード２ｔ〜２ｖ）は、フラッディング経路表２２においてノード２ｅに対応づけられて受信ノードとして登録される。
【００４３】
（６）無線通信装置１０は、無線通信装置１０に隣接するノード以外のノードの中で、フラッディング経路表２２に登録されてないノードが残っているか否かを判定する。この例では、そのようなノードは残っていない。よって、無線通信装置１０は、ＭＰＲノードの選択およびフラッディング経路表２２の作成を終了する。
【００４４】
このように、無線通信装置１０は、ＭＰＲノードを選択し、フラッディング経路表２２を作成する。フラッディング経路表２２は、各ＭＰＲノードについて、ブロードキャスト転送により送信されるフラッディングパケットを受信するノードを表す。
【００４５】
干渉点ノード特定部１４は、フラッディング経路表２２に基づいて、複数の中継ノードからフラッディングパケットが到達する干渉点ノードを特定する。図５（ｂ）に示す例では、ノード２ｒは、第１レコードおよび第２レコードの双方に登録されている。この状態は、第１レコードに登録されているノード２ａから送信される無線電波および第２レコードに登録されているノード２ｃから送信される無線電波がノード２ｒに到達することを表している。すなわち、図５（ｂ）に示すフラッディング経路表２２は、ノード２ｒにおいて、ノード２ａから送信される無線電波およびノード２ｃから送信される無線電波が互いに干渉し得ることを表している。よって、ノード２ｒは、干渉点ノードとして特定される。
【００４６】
同様に、ノード２ｔは、第２レコードおよび第３レコードの双方に登録されている。この状態は、第２レコードに登録されているノード２ｃから送信される無線電波および第３レコードに登録されているノード２ｅから送信される無線電波がノード２ｔに到達することを表している。すなわち、図５（ｂ）に示すフラッディング経路表２２は、ノード２ｔにおいて、ノード２ｃから送信される無線電波およびノード２ｅから送信される無線電波が互いに干渉し得ることを表している。よって、ノード２ｔも、干渉点ノードとして特定される。
【００４７】
中継ノード特定部１５は、干渉点ノード特定部１４により特定された各干渉点ノードについて、干渉点ノードに到達するフラッディングパケットを送信する中継ノード（以下、送信元中継ノード）を特定する。例えば、ノード２ｒには、上述したように、ノード２ａから送信される無線電波およびノード２ｃから送信される無線電波が到達する。即ち、ノード２ｒは、フラッディング手順において、ノード２ａ、２ｃの双方からフラッディングパケットを受信する。したがって、ノード２ｒに対して、フラッディングパケットの送信元中継ノードとして、ノード２ａ、２ｃが特定される。
【００４８】
同様に、ノード２ｔには、ノード２ｃから送信される無線電波およびノード２ｅから送信される無線電波が到達する。即ち、ノード２ｔは、フラッディング手順において、ノード２ｃ、２ｅの双方からフラッディングパケットを受信する。したがって、ノード２ｔに対して、フラッディングパケットの送信元中継ノードとして、ノード２ｃ、２ｅが特定される。
【００４９】
相互干渉テーブル２３には、干渉点ノード特定部１４および中継ノード特定部１５により特定されたノードが登録される。すなわち、相互干渉テーブル２３は、各干渉点ノードについて、フラッディングパケットの送信元中継ノードを表す。この例では、図６（ａ）に示すように、ノード２ｒにフラッディングパケットを送信する中継ノードとしてノード２ａ、２ｃが登録され、また、ノード２ｔにフラッディングパケットを送信する中継ノードとしてノード２ｃ、２ｅが登録されている。
【００５０】
図７は、相互干渉テーブル２３を作成する処理の一例を示すフローチャートである。このフローチャートの処理は、例えば、フラッディング経路表２２が作成または更新されたときに実行される。なお、フラッディング経路表２２は、例えば、隣接ノード情報２１が更新されたときに作成または更新される。
【００５１】
Ｓ１において、通信制御部１３は、フラッディング経路表２２から先頭のレコードを選択する。Ｓ２において、干渉点ノード特定部１４は、Ｓ１またはＳ９において選択されたレコードに登録されている受信ノードを選択する。以下の記載では、Ｓ２において選択された受信ノードを「ノードｉ」と呼ぶことがある。
【００５２】
Ｓ３において、干渉点ノード特定部１４は、フラッディング経路表２２の他のレコードにノードｉが登録されているか否かを判定する。フラッディング経路表２２の他のレコードにノードｉが登録されていれば、Ｓ４において、干渉点ノード特定部１４は、ノードｉを干渉点ノードとして特定する。Ｓ５において、中継ノード特定部１５は、ノードｉが登録されている各レコードに登録されているＭＰＲノードを送信元中継ノードとして特定する。Ｓ６において、通信制御部１３は、干渉点ノード特定部１４により特定された干渉点ノードおよび中継ノード特定部１５により特定された送信元中継ノードを、互いに対応づけて相互干渉テーブル２３に登録する。なお、フラッディング経路表２２の他のレコードにノードｉが登録されていなければ、Ｓ４〜Ｓ６の処理はスキップされる。
【００５３】
Ｓ７において、通信制御部１３は、Ｓ１またはＳ９で選択されたレコード中に、選択されてない受信ノードが残っているか否かを判定する。そして、選択されてない受信ノードが残っていれば、通信制御部１３の処理はＳ２に戻る。すなわち、Ｓ１またはＳ９において選択されたレコードに登録されているすべての受信ノードに対してＳ３〜Ｓ６の処理が実行される。
【００５４】
Ｓ８において、通信制御部１３は、フラッディング経路表２２において選択されてないレコードが残っているか否かを判定する。選択されてないレコードが残っていれば、通信制御部１３は、Ｓ９において、フラッディング経路表２２から次のレコードを選択する。この後、通信制御部１３の処理はＳ２に戻る。したがって、フラッディング経路表２２の各レコードに登録されている各受信ノードに対してＳ３〜Ｓ６の処理が実行される。この結果、相互干渉テーブル２３が作成される。
【００５５】
図７に示すフローチャートに従って図５（ｂ）に示すフラッディング経路表２２から相互干渉テーブル２３を作成する手順を説明する。
【００５６】
（１）Ｓ１において、フラッディング経路表２２の第１レコードが選択される。Ｓ２において、このレコードからノード２ｐが選択される。Ｓ３において、他のレコードにノード２ｐが登録されていないと判定される。よって、Ｓ４〜Ｓ６はスキップされ、通信制御部１３の処理はＳ２に戻る。
【００５７】
（２）Ｓ２において、ノード２ｑが選択される。Ｓ３において、他のレコードにノード２ｑが登録されていないと判定される。よって、Ｓ４〜Ｓ６はスキップされ、通信制御部１３の処理はＳ２に戻る。
【００５８】
（３）Ｓ２において、ノード２ｒが選択される。Ｓ３において、第２レコードにノード２ｒが登録されていると判定される。よって、Ｓ４〜Ｓ６が実行される。Ｓ４において、ノード２ｒが干渉点ノードとして特定される。ここで、ノード２ｒは、第１レコードおよび第２レコードに登録されている。この場合、Ｓ５において、第１レコードに登録されているＭＰＲノード（即ち、ノード２ａ）および第２レコードに登録されているＭＰＲノード（即ち、ノード２ｃ）が、ノード２ｒに対応する送信元中継ノードとして特定される。そして、Ｓ６において、干渉点ノード（即ち、ノード２ｒ）および送信元中継ノード（即ち、ノード２ａ、２ｃ）が相互干渉テーブル２３の第１レコードに登録される。
【００５９】
この後、フラッディング経路表２２の第２レコードおよび第３レコードに対して同様の処理が実行される。この結果、図６（ａ）に示す相互干渉テーブル２３が完成する。
【００６０】
グループ化部１６は、下記の２つの条件を満足するように、中継ノード特定部１５により特定された送信元中継ノードをグループ化する。
（１）同じ干渉点ノードにフラッディングパケットを送信する送信元中継ノードは、互いに異なるグループに属する。
（２）同じ干渉点ノードにフラッディングパケットを送信しない送信元中継ノードは、互いに同じグループに属する。
【００６１】
図６（ａ）に示す例では、ノード２ｒにフラッディングパケットを送信する送信元中継ノードは、ノード２ａ、２ｃである。よって、ノード２ａ、２ｃは、互いに異なるグループに登録される。また、ノード２ｔにフラッディングパケットを送信する送信元中継ノードは、ノード２ｃ、２ｅである。よって、ノード２ｃ、２ｅは、互いに異なるグループに登録される。ただし、ノード２ａ、２ｅは、同じ干渉点ノードにフラッディングパケットを送信していない。したがって、ノード２ａ、２ｅは、同じグループに登録される。
【００６２】
この結果、ノード２ａ、２ｅは互いに同じグループに登録され、ノード２ｃは、ノード２ａ、２ｅとは異なるグループに登録される。図６（ｂ）に示す例では、ノード２ａ、２ｅはグループ１に登録され、ノード２ｃはグループ２に登録されている。
【００６３】
図８は、送信元中継ノードのグループ化の一例を示すフローチャートである。このフローチャートの処理は、例えば、相互干渉テーブル２３が作成または更新されたときに実行される。
【００６４】
Ｓ１１において、グループ化部１６は、相互干渉テーブル２３の先頭レコードに登録されている各送信元中継ノードを互いに異なるグループに登録する。Ｓ１２において、グループ化部１６は、相互干渉テーブル２３から次のレコードを選択する。Ｓ１３において、グループ化部１６は、Ｓ１２において選択されたレコードから送信元中継ノードを選択する。以下の記載では、Ｓ１３において選択された送信元中継ノードを「ノードｊ」と呼ぶことがある。
【００６５】
Ｓ１４において、グループ化部１６は、ノードｊが既にいずれかのグループに登録されているか否かを判定する。ノードｊがいずれのグループにも登録されていないときは、グループ化部１６は、Ｓ１５において、送信先が同じ干渉点ノードとなる送信元中継ノードを含まないグループ（以下、グループＸ）が存在するか否かを判定する。すなわち、グループ化部１６は、Ｓ１５において、ノードｊの送信先ノードに含まれる干渉点ノードにパケットを送信する送信元中継ノードを含まないグループが存在するか否かを判定する。
【００６６】
グループＸが存在するときは、グループ化部１６は、Ｓ１６において、ノードｊをグループＸに登録する。なお、ノードｊに対して複数のグループＸが存在するときは、グループ化部１６は、任意の１つのグループＸにノードｊを登録する。一方、グループＸが存在しないときには、グループ化部１６は、Ｓ１７において、新たなグループを生成する。そして、グループ化部１６は、その新たなグループにノードｊを登録する。なお、ノードｊが既にいずれかのグループに登録されているときは、Ｓ１５〜Ｓ１７の処理はスキップされる。
【００６７】
Ｓ１８において、グループ化部１６は、Ｓ１２において選択されたレコード中に未処理の送信元中継ノードが残っているか否かを判定する。そして、未処理の送信元中継ノードが残っているときは、グループ化部１６の処理はＳ１３に戻る。また、Ｓ１９において、グループ化部１６は、未処理のレコードが残っているか否かを判定する。そして、未処理のレコードが残っているときは、グループ化部１６の処理はＳ１２に戻る。すなわち、相互干渉テーブル２３の各レコードに登録されている各送信元中継ノードに対してＳ１５〜Ｓ１７の処理が実行される。この結果、送信元中継ノードがグループ化される。
【００６８】
図８に示すフローチャートに従って図６（ａ）に示す相互干渉テーブル２３に登録されている送信元中継ノードをグループ化する手順を説明する。
【００６９】
（１）相互干渉テーブル２３の第１レコードに送信元中継ノードとしてノード２ａ、２ｃが登録されている。したがって、ノード２ａ、２ｃは、Ｓ１１において、互いに異なるグループに登録される。この例では、ノード２ａはグループ＃１に登録され、ノード２ｃはグループ＃２に登録される。
【００７０】
（２）Ｓ１２において、相互干渉テーブル２３の第２レコードが選択され、Ｓ１３において、第２レコードからノード２ｃが選択される。ただし、ノード２ｃは、既にグループ＃２に登録されている（Ｓ１４：Ｙｅｓ）。よって、Ｓ１５〜Ｓ１７の処理は実行されない。
【００７１】
（３）Ｓ１３において、第２レコードからノード２ｅが選択される。ここで、ノード２ｅの送信先ノードは、干渉点ノード２ｔを含む。他方、この時点でグループ＃１に登録されているノード２ａの送信先ノードは、ノード２ｔを含まない。すなわち、Ｓ１５において、送信先ノードが同じ干渉点ノードとなる送信元中継ノードを含まないグループ（グループ＃１）が存在する。よって、Ｓ１６において、ノード２ｅは、グループ＃１に登録される。なお、グループ＃１に登録されているノード２ｃの送信先は、ノード２ｔを含む。したがって、ノード２ｅは、グループ＃２に登録されることはない。
【００７２】
設定部１７は、各グループに対して異なる送信タイミングを設定する。送信タイミングは、例えば、フラッディングパケットを送信する順序で表される。この実施例では、グループ＃１に対して「送信順序：１番目」が与えられ、グループ＃２に対して「送信順序：２番目」が与えられる。そして、決定された送信順序は、図６（ｂ）に示すように、フラッディング順序テーブル２４に記録される。ただし、各グループの送信タイミングを他のパラメータで表してもよい。例えば、各グループの送信タイミングは、中継ノードがフラッディングパケットを受信したときからそのフラッディングパケットを転送するまでの待ち時間であってもよい。
【００７３】
通知部１８は、設定部１７により設定される送信タイミング（この例では、送信順序）を各送信元中継ノードに通知する。すなわち、通知部１８は、フラッディングパケットの送信順序を、ノード２ａ、２ｃ、２ｅに通知する。具体的には、グループ＃１に属するノード２ａ、２ｅに対して「送信順序：１番目」が通知され、グループ＃２に属するノード２ｃに対して「送信順序：２番目」が通知さる。なお、この通知は、フラッディングにより実現してもよいし、ユニキャスト通信で実現してもよい。
【００７４】
図９は、本発明の実施形態に係わる無線端末装置の一例を示す。無線端末装置３０は、図１に示す無線通信システム１００においては、各ノード２に実装される。
【００７５】
無線端末装置３０は、図９に示すように、無線送受信部３１、受信処理部３２、通信制御部３３、送信処理部３４、保存部４０を備える。ただし、無線端末装置３０は、図９に示していない他の回路または機能を備えてもよい。
【００７６】
無線送受信部３１は、隣接ノードから送信される無線信号を受信する。また、無線送受信部３１は、無線信号を送信する。受信処理部３２は、受信信号を復号してパケットを再生する。そして、受信信号から再生されたパケット（すなわち、受信パケット）は、通信制御部３３に渡される。送信制御部３４は、送信パケットから送信信号を生成して無線送受信部３１に渡す。
【００７７】
通信制御部３３は、無線端末装置３０の動作を制御する。なお、通信制御部３３は、この実施例では、プロセッサにより実現される。保存部４０は、通信制御部３３が使用する情報を格納する。この実施例では、保存部４０には、隣接ノード情報４１、ＭＰＲ情報４２、フラッディング順序情報４３が格納される。また、保存部４０は、通信制御部３３により実行されるプログラムを格納する。
【００７８】
隣接ノード情報４１は、自ノードに隣接するノードを表す。また、隣接ノード情報４１は、自ノードから２ホップ目のノードを表す情報を含んでもよい。ＭＰＲ情報４２は、自ノードがＭＰＲノードとして動作するか否かを表す。ＭＰＲノードとして動作するノードは、例えば、ゲートウェイノード１により指定される。フラッディング順序情報４３は、フラッディングパケットの送信順序を表す。なお、フラッディング順序情報は、上述したように、ゲートウェイノード１において設定部１８により生成される。
【００７９】
図１０は、無線端末装置３０の動作の一例を示すフローチャートである。なお、このフローチャートは、無線端末装置３０がフラッディングパケットを受信したときの動作を示している。
【００８０】
Ｓ２１において、通信制御部３３は、新たに受信したパケットが先に受信したパケットを同じであるか否かを判定する。新たに受信したパケットが先に受信したパケットを同じであるときは、通信制御部３３は、重複送信を回避するために、そのパケットを転送することなく廃棄する。
【００８１】
新たに受信したパケットが先に受信したパケットを同じでないときは、通信制御部３３は、Ｓ２２において、自ノードがＭＰＲノードであるか否かを判定する。自ノードがＭＰＲノードであるか否かは、ＭＰＲ情報４２に記述されている。そして、自ノードがＭＰＲノードでないときは、通信制御部３３は、そのパケットを転送することなく廃棄する。
【００８２】
自ノードがＭＰＲノードであるときは、通信制御部３３は、Ｓ２３において、フラッディング順序情報４３に基づいて送信タイミングを決定する。そして、Ｓ２４において、無線端末装置３０は、決定した送信タイミングで、受信パケットをブロードキャストする。例えば、自ノードの送信順序が「ｋ番目」であるときは、無線端末装置３０は、パケットの受信時刻から「ｋ×ΔＴ」が経過したときにそのパケットをブロードキャストする。
【００８３】
この場合、ΔＴは、送信順序がｋ番目であるノードから送信される無線電波と送信順序がｋ±１番目であるノードから送信される無線電波との間で干渉が発生しないように決定される。よって、ΔＴは、所定の閾値よりも大きい値であることが要求される。ただし、ΔＴが大き過ぎると、フラッディングが終了するまでに要する時間が長くなってしまう。したがって、ΔＴは、干渉が回避される範囲内で、可能な限り小さい値であることが好ましい。
【００８４】
図１１は、本発明の実施形態に係わる通信方法の一例を示す。この例では、図２〜図３に示すケースと同様に、ゲートウェイノード１からノード２ａ〜２ｅ、２ｐ〜２ｖへのフラッディングが行われる。また、図３に示すケースと同様に、ノード２ａ、２ｃ、２ｅがＭＰＲノードとして指定されている。更に、ゲートウェイノード１において、図６（ａ）に示す相互干渉テーブル２３および図６（ｂ）に示すフラッディング順序テーブルが作成されている。すなわち、ノード２ａ、２ｅに対して「送信順序：１番目」が与えられ、ノード２ｃに対して「送信順序：２番目」が与えられている。
【００８５】
ゲートウェイノード１は、フラッディングパケットをブロードキャストする。そして、ノード２ａ〜２ｅは、このフラッディングパケットを受信する。そうすると、各ノード２ａ〜２ｅは、図１０に示すフローチャートの処理を実行する。
【００８６】
ノード２ａ、２ｅは、ＭＰＲノードとして選択されており、「送信順序：１番目」が与えられている。よって、ノード２ａ、２ｅは「送信待ち時間：ΔＴ」を得る。ノード２ｃは、ＭＰＲノードとして選択されており、「送信順序：２番目」が与えられている。よって、ノード２ｃは「送信待ち時間：２ΔＴ」を得る。ノード２ｂ、２ｄは、ＭＰＲノードとして選択されていないので、転送処理を行わない。
【００８７】
ノード２ａ〜２ｅがフラッディングパケットを受信したときからΔＴが経過すると、図１１（ａ）に示すように、ノード２ａ、２ｅは受信パケットをブロードキャストする。これにより、ノード２ｐ〜２ｒ、２ｔ〜２ｖがフラッディングパケットを受信する。また、ノード２ａ、２ｅがブロードキャスト転送を行ったときからさらにΔＴが経過すると、図１１（ｂ）に示すように、ノード２ｃが受信パケットをブロードキャストする。これにより、ノード２ｒ〜２ｔがフラッディングパケットを受信する。
【００８８】
このように、本発明の実施形態に係わる通信方法によれば、無線ネットワーク内に干渉点ノードが存在するときは、中継ノードが異なるタイミングでパケットを転送する。よって、無線マルチホップネットワークにおいてフラッディングが行われるときに、干渉の発生が回避または抑制され、通信効率が改善する。例えば、ノード２ｒは、ノード２ａ、２ｃからパケットを受信する。ただし、ノード２ａ、２ｃは、図１１に示すように、互いに異なるタイミングでパケットを転送する。したがって、ノード２ｒにおいて干渉は発生しない。
【００８９】
なお、図３に示すケースにおいて、各ＭＰＲノード（２ａ、２ｃ、２ｅ）が互いに異なるタイミングでパケットを転送すれば、ノード２ｒ、２ｔにおいて干渉は発生しない。例えば、ノード２ａ、２ｃ、２ｅが順番にΔＴずつ送信タイミングをずらしながらパケット転送を行えば、ノード２ｒ、２ｔにおいて干渉は発生しない。ただし、この手順では、図１１に示す本発明の実施形態に係わる通信方法と比較して、フラッディングが完了するまでに要する時間が長くなってしまう。換言すれば、本発明の実施形態に係わる通信方法によれば、フラッディングが完了するまでに要する時間を短縮しながら、干渉の発生が回避または抑制される。
【００９０】
また、上述した実施例では、ゲートウェイノード１において送信順序が決定され、各中継ノードにおいて送信タイミングが計算されるが、本発明の実施形態はこの方法に限定されるものではない。例えば、ゲートウェイノード１が各中継ノードの送信タイミングを計算し、その計算結果が各中継ノードに通知されるようにしてもよい。
【符号の説明】
【００９１】
１  ゲートウェイノード
２（２ａ〜２ｅ、２ｐ〜２ｖ）  ノード
１０  無線通信装置
１１  無線送受信部
１２  受信処理部
１３  通信制御部
１４  干渉点ノード特定部
１５  中継ノード特定部
１６  グループ化部
１７  設定部
１８  通知部
１９  送信処理部
２０  保存部
３０  無線端末装置
１００  無線通信システム
【図１】
2020145634.tif 000003
【図２】
2020145634.tif 000004
【図３】
2020145634.tif 000005
【図４】
2020145634.tif 000006
【図５】
2020145634.tif 000007
【図６】
2020145634.tif 000008
【図７】
2020145634.tif 000009
【図８】
2020145634.tif 000010
【図９】
2020145634.tif 000011
【図１０】
2020145634.tif 000012
【図１１】
2020145634.tif 000013