(57)【要約】【課題】無線メッシュネットワークにおいて、複数のチャネルを各無線リンクに割り当てる場合に必要なチャネル数が、与えられたチャネル数よりも多い場合に、干渉率を低減し、連結率を維持させつつチャネルを割り当てる無線周波数割り当て装置、無線通信システムおよび無線周波数割り当て方法を提供する。【解決手段】無線周波数割り当て装置に、直接伝送可能なノードの情報および他のノードにおけるノードの情報に基づいて、さらし端末問題が発生するリンク同士を干渉関係として求める手段と、さらし端末問題が発生するリンク同士に割り当てる周波数を異なるように割り当て、全リンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数を重複して割り当てる手段と、使用できる周波数が重複して割り当てられたリンクについて辺間隔度を求め、その平均値に基づいて、所定のリンクを使用禁止とする手段とを備えることにより達成される。【選択図】図２
2008047946.tif 000002
【特許請求の範囲】
【請求項１】
仮想キャリアセンスにより無線帯域の割り当て制御を行う無線通信システムにおける、無線周波数割り当て装置において：
直接伝送可能なノードの情報を収集する収集手段；
前記ノードの情報および他のノードにおけるノードの情報に基づいて、さらし端末問題が発生するリンク同士を干渉関係として求める隣接ノード情報作成手段；
前記さらし端末問題により干渉が発生するリンク同士に割り当てる周波数を異なるように割り当て、全てのリンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数を重複して割り当てる無線チャネル割り当て手段；
前記無線チャネル割り当て手段において使用できる周波数が重複して割り当てられたリンクについて辺間隔度を求める辺間隔度計算手段；
前記辺間隔度の平均値および標準偏差に基づいて、所定のリンクを使用禁止とするリンク判定手段；
を備えることを特徴とする無線周波数割り当て装置。
【請求項２】
請求項１に記載の無線周波数割り当て装置において：
前記辺間隔度計算手段は、ノードの組ｓ、ｔの最短経路ｐｓｔが、該当するリンクを通るような組の数を計算することを特徴とする無線周波数割り当て装置。
【請求項３】
請求項１または２に記載の無線周波数割り当て装置において：
前記リンク判定手段は、前記辺間隔度の標準偏差を求め、前記平均値と前記標準偏差により算出される閾値に基づいて、所定のリンクを使用禁止とすることを特徴とする無線周波数割り当て装置。
【請求項４】
仮想キャリアセンスにより無線帯域の割り当て制御を行う無線通信システムにおいて：
直接伝送可能なノードの情報を収集する収集手段；
前記ノードの情報および他のノードにおけるノードの情報に基づいて、さらし端末問題が発生するリンク同士を干渉関係として求める隣接ノード情報作成手段；
前記さらし端末問題による干渉が発生するリンク同士に割り当てる周波数を異なるように割り当て、全てのリンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数を重複して割り当てる無線チャネル割り当て手段；
前記無線チャネル割り当て手段において使用できる周波数が重複して割り当てられたリンクについて辺間隔度を求める辺間隔度計算手段；
前記辺間隔度の平均値および標準偏差に基づいて、所定のリンクを使用禁止とするリンク判定手段；
を備えることを特徴とする無線通信システム。
【請求項５】
仮想キャリアセンスにより無線帯域の割り当て制御を行う無線通信システムにおける、無線周波数割り当て方法において：
直接伝送可能なノードの情報を収集する収集ステップ；
前記ノードの情報および他のノードにおけるノードの情報に基づいて、さらし端末問題が発生するリンク同士を干渉関係として求める隣接ノード情報作成ステップ；
前記さらし端末問題による干渉が発生するリンク同士に割り当てる周波数を異なるように割り当てる場合に、全てのリンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数を重複して割り当てる無線チャネル割り当てステップ；
前記無線チャネル割り当て手段において使用できる周波数が重複して割り当てられたリンクについて辺間隔度を求める辺間隔度計算ステップ；
前記辺間隔度の平均値および標準偏差に基づいて、所定のリンクを使用禁止とするリンク判定ステップ；
を有することを特徴とする無線周波数割り当て方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想キャリアセンスを行う自律分散型非同期ディジタル無線伝送を行う無線通信システムにおいて、無線チャネル割り当てを制御するための無線周波数割り当て装置、無線通信システムおよび無線周波数割り当て方法に関する。
【背景技術】
【０００２】
現在の代表的な無線通信方式である無線ＬＡＮ方式では、アクセスポイント（ＡＰ）が固定的に設置され、ＡＰは有線でバックボーンに接続されている。
【０００３】
端末は、通信を行う際には常にＡＰを介して通信を行うので、無線が使われるのは端末とＡＰの間の１ホップだけである。
【０００４】
一方、ＡＰ間も無線リンクで接続するという無線メッシュネットワークが提案され技術開発が進んでいる。無線メッシュネットワークにおいて、各ＡＰをつなぐ無線リンクにすべて同一のチャネル（周波数）を割り当てることも可能であるが、様々な要因によりスループットが低下するという問題がある。
【０００５】
この問題は、複数のチャネルを各無線リンクに適切に割り当てることにより軽減されるが、チャネル数は有限であるので、場合によってはすべての無線リンクに適切にチャネルを割り当てることができない場合もある。
【０００６】
また、無線メッシュネットワークでは、ある程度離れたリンクにおいて同時に同じ周波数でパケット通信を行うと、帯域予約に失敗し、パケット損失となる「さらし端末問題」と呼ばれる問題が存在する。この「さらし端末」とは、図１に示されるように、無線局１と無線局２が帯域予約のために、ＲＴＳ（送信要求信号）およびＣＴＳ（要求確認信号）を交換した結果、無線局３が無線局２への干渉を回避するために、送信抑制状態となり、無線局４から送信要求があった場合でも、何の応答も返さない状態である無線局３のことを示す。このような状況では、無線局４からのＲＴＳは再送されたとしても無線局３からの応答がこないことから、パケット損失の要因となる。仮に、ＲＴＳ／ＣＴＳの交換を行なわず、無線局１が無線局２にパケットを伝送し、概ね同時に無線局４から無線局３にパケットを送信した場合、図２に示されるように、無線局２あるいは３からのＡＣＫ（応答）パケットがそれぞれ無線局３あるいは２において干渉となり、パケット損失が発生する。以上のように、さらし端末問題は、ＲＴＳ／ＣＴＳの使用の有無に関わらず、その過程は異なるものの、パケット損失の要因となる。このようなさらし端末問題が発生するリンクの組に対して、異なる周波数を割り当てることにより、この問題は回避できる。
【非特許文献１】Ｃｅｎｔｒａｌｉｚｅｄ  Ｃｈａｎｎｅｌ  Ａｌｌｏｃａｔｉｏｎ  Ｔｅｃｈｎｉｑｕｅ  ｔｏ  Ａｌｌｅｖｉａｔｅ  Ｅｘｐｏｓｅｄ  Ｔｅｒｍｉｎａｌ  Ｐｒｏｂｌｅｍ  ｉｎ  ＣＳＭＡ／ＣＡ  Ｂａｓｅｄ  Ｍｅｓｈ  Ｎｅｔｗｏｒｋｓ：  ＩＥＩＣＥ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｖｏｌ．  Ｅ８８−Ｂ  Ｎｏ．３，  ｐｐ．９５８−９６４
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した背景技術には以下の問題がある。
【０００８】
無線メッシュネットワークにおけるスループットを向上させるために、複数のチャネルを各無線リンクに適切に割り当てることが有効である一方で、性能向上のために必要なチャネル数が、与えられたチャネル数よりも多い場合、制約を満たしたチャネル割り当てを行うことができない場合がある。このような場合に、ある程度の干渉が生ずることを許容し、各無線リンクにチャネルを割り当てることは可能であるが、同時に、できるだけ干渉を小さくしたいという要求もある。
【０００９】
そこで、他の無線リンクに干渉を与えてしまう無線リンクの使用を禁止すれば、そもそも干渉が発生しないので、干渉を軽減できる。しかし、このような場合、一部の無線リンクの使用を禁止することによりネットワークが非連結になることもある。この問題を防ぐためには、ネットワークの連結性を保つために重要な無線リンクの使用を禁止することは望ましくない。
【００１０】
そこで、本発明においては、無線メッシュネットワークにおいて、複数のチャネルを各無線リンクに割り当てる場合に必要なチャネル数が、与えられたチャネル数よりも多い場合に、干渉率を低減し、連結率を維持させながらチャネルを割り当てることができる無線周波数割り当て装置、無線通信システムおよび無線周波数割り当て方法を提供することにある。
【課題を解決するための手段】
【００１１】
上記課題を解決するため、本発明の無線周波数割り当て装置は、
仮想キャリアセンスにより無線帯域の割り当て制御を行う無線通信システムにおける、無線周波数割り当て装置において：
直接伝送可能なノードの情報を収集する収集手段；
前記ノードの情報および他のノードにおけるノードの情報に基づいて、さらし端末問題が発生するリンク同士を干渉関係として求める隣接ノード情報作成手段；
前記さらし端末問題により干渉が発生するリンク同士に割り当てる周波数を異なるように割り当て、全てのリンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数を重複して割り当てる無線チャネル割り当て手段；
前記無線チャネル割り当て手段において使用できる周波数が重複して割り当てられたリンクについて辺間隔度を求める辺間隔度計算手段；
前記辺間隔度の平均値および標準偏差に基づいて、所定のリンクを使用禁止とするリンク判定手段；
を備えることを特徴の１つとする。
【００１２】
このように構成することにより、辺間隔度に基づいて、通信を抑制するリンクを選択することができ、ネットワークの接続度の低下を抑えつつ、さらし端末問題の発生度合いを低減でき、パケット損失を低減できる。
【００１３】
本発明の無線通信システムは、
仮想キャリアセンスにより無線帯域の割り当て制御を行う無線通信システムにおいて：
直接伝送可能なノードの情報を収集する収集手段；
前記ノードの情報および他のノードにおけるノードの情報に基づいて、さらし端末問題が発生するリンク同士を干渉関係として求める隣接ノード情報作成手段；
前記さらし端末問題による干渉が発生するリンク同士に割り当てる周波数を異なるように割り当て、全てのリンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数を重複して割り当てる無線チャネル割り当て手段；
前記無線チャネル割り当て手段において使用できる周波数が重複して割り当てられたリンクについて辺間隔度を求める辺間隔度計算手段；
前記辺間隔度の平均値および標準偏差に基づいて、所定のリンクを使用禁止とするリンク判定手段；
を備えることを特徴の１つとする。
【００１４】
このように構成することにより、無線局は、辺間隔度に基づいて、通信を抑制するリンクを選択することができ、ネットワークの接続度の低下を抑えつつ、さらし端末問題の発生度合いを低減でき、パケット損失を低減できる。
【００１５】
本発明の無線周波数割り当て方法は、
仮想キャリアセンスにより無線帯域の割り当て制御を行う無線通信システムにおける、無線周波数割り当て方法において：
直接伝送可能なノードの情報を収集する収集ステップ；
前記ノードの情報および他のノードにおけるノードの情報に基づいて、さらし端末問題が発生するリンク同士を干渉関係として求める隣接ノード情報作成ステップ；
前記さらし端末問題による干渉が発生するリンク同士に割り当てる周波数を異なるように割り当てる場合に、全てのリンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数を重複して割り当てる無線チャネル割り当てステップ；
前記無線チャネル割り当て手段において使用できる周波数が重複して割り当てられたリンクについて辺間隔度を求める辺間隔度計算ステップ；
前記辺間隔度の平均値および標準偏差に基づいて、所定のリンクを使用禁止とするリンク判定ステップ；
を有することを特徴の１つとする。
【００１６】
このようにすることにより、辺間隔度に基づいて、通信を抑制するリンクを選択することができ、ネットワークの接続度の低下を抑えつつ、さらし端末問題の発生度合いを低減でき、パケット損失を低減できる。
【発明の効果】
【００１７】
本発明の実施例によれば、無線メッシュネットワークにおいて、複数のチャネルを各無線リンクに割り当てる場合に必要なチャネル数が、与えられたチャネル数よりも多い場合に、干渉率を低減し、連結率を維持させながらチャネルを割り当てることができる無線周波数割り当て装置、無線通信システムおよび無線周波数割り当て方法を実現できる。
【発明を実施するための最良の形態】
【００１８】
次に、本発明の実施例について図面を参照して説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を用い、繰り返しの説明は省略する。
【００１９】
無線メッシュネットワークにおいてスループットの低下を防ぐために、干渉を避けながら、ある制約条件を満たしながら、各無線リンクに複数のチャネルを割り当てることが効果的であることが知られている。
【００２０】
しかし、チャネル数が有限であることから、与えられたチャネル数ではチャネル割り当てを行うことができない場合もある。このような場合に、本実施例では以下の方法により、高い連結率を維持しながら干渉を低減したチャネル割り当てを実現する。具体的には、与えられたチャネル数で制約を満たしたチャネル割り当てを行えない場合に、チャネルを割り当てることができない無線リンクに対しては制約を満たさないチャネルを割り当てる。同時に、これらの無線リンクの内、辺間隔度が低い無線リンクを選択し、経路制御の際に使用を禁止する。
【００２１】
本発明の実施例にかかるメッシュネットワークの構成について、図３を参照して説明する。本実施例にかかるメッシュネットワークは、仮想キャリアセンスにより無線帯域の割り当て制御を行う。ここで、仮想キャリアセンスを用いる方式とは、送受信を行う無線局同士で、「送信要求信号」と「準備完了信号」とを交換することにより、互いに通信を確立する。また、これらの信号を受信した他の無線局は、受信したこれらの信号に含まれる「送信禁止期間」に基づき、「送信要求信号」の送信を延期する。
【００２２】
本実施例にかかるメッシュネットワークは、複数の無線局により構成される。図３には、一例として、６台の無線局１００（１００１、１００２、１００３、１００４、１００５、１００６）により構成されるメッシュネットワークが示される。また、図３には、無線局１００ｋと無線局１００ｌとの無線リンク（リンク）をLｋｌにより示す（ｋ、ｌは、正の整数）。
【００２３】
各無線局は、通信可能な無線局とのリンクを確立することで、メッシュ状に接続されたネットワークを構成する。無線ＬＡＮシステムのように、無線アクセス制御方式（ＭＡＣ）としてＣＳＭＡ／ＣＡ（Ｃａｒｒｉｅｒ  Ｓｅｎｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ  ｗｉｔｈ  Ｃｏｌｌｉｓｉｏｎ  Ｄｅｔｅｃｔｉｏｎ）方式を用いる場合、特定の法則にしたがうリンクの組（図３では、無線局１００１と無線局１００２のリンクＬ１２と、無線局１００３と無線局１００５のリンクＬ３５など）が同時に通信を行うと、さらし端末問題と呼ばれる問題が発生し、パケットロスなどの通信品質低下をもたらす（例えば、非特許文献１参照）。
【００２４】
すなわち、さらし端末問題とは、干渉しない程度に遠くにあるにもかかわらず、通信を開始できない問題をいう。
【００２５】
次に、本実施例にかかる無線局１００について、図４を参照して説明する。
【００２６】
本実施例にかかる無線局１００は、無線周波数割り当て装置を備え、無線周波数割り当て装置は送受信部１０２と、送受信部１０２と接続され、無線周波数割り当て装置の各部を制御する制御部１０４と、制御部１０４と接続された無線チャネル設定部１１０、隣接ノード情報収集部１０６および隣接ノード情報作成部１０８とを備える。無線チャネル設定部１１０は、無線チャネル割り当て部１１２、辺間隔度計算部１１４およびリンク判定部１１６とを備える。
【００２７】
各無線局１００（１００１、１００２、１００３、１００４、１００５および１００６）の隣接ノード情報作成部１０８は、隣接ノード情報を作成するために、自無線局に関する情報、例えば無線局のＩＤや使用周波数など、および隣接ノード情報を含むパケットをブロードキャストする。このブロードキャストされたパケットを受信した他の無線局は、隣接ノード収集部１０６において隣接ノード情報を収集する。また、無線局１００は、隣接ノード情報作成部１０８において、受信したパケットに自無線局の隣接ノード情報を追加し、自無線局に関する情報および隣接ノード情報を含むパケットをブロードキャストする。以上のプロセスが繰り返されることにより、各無線局の隣接ノード情報収集部１０６は、隣接ノードにより収集された隣接ノード情報を収集できる。
【００２８】
さらに、各無線局は、収集した隣接ノードの隣接ノード情報により、隣接ノード情報作成部１０８において、彩色グラフを作成し、さらし端末問題が発生する通信路の組み合わせを推定する。彩色グラフについては後述する。具体的には、「隣接ノード情報に基づき認識されるある通信路（通信路Ａとする）の送受信局ともに、隣接ノード情報に基づき認識される他の無線局（無線局Ｂとする）の通信範囲外である場合、通信路Ａの通信中は自局と無線局Ｂ間の通信」でさらし端末問題が発生する点を基準にして推定する。
【００２９】
例えば、隣接ノード情報作成部１０８は、図５に示すように、リンクをグラフの節、さらし端末が発生するリンクの組を辺とするグラフを生成する。さらし端末問題を防ぐ問題は接続されている節が同じ色にならないように彩色する「点彩色問題」と等価であることが知られている。この図５に示す例では、彩色グラフは２色で塗り分けることができるため、さらし端末問題を防ぐためには２つのチャネルで十分であることがわかる。
【００３０】
ここで、彩色グラフについて、詳細に説明する。彩色グラフとは、各通信路（リンク）間でさらし問題が発生する通信路同士を通信路間の接続関係として表した図である。
【００３１】
所定のノード（端末）ｋ、ｌ、ｍおよびｎについて、ノードｋとノードｌ間の通信路Ｃｋ，ｌと、ノードｍとノードｎ間の通信路Ｃｍ、ｎとの間でさらし端末問題が発生するか否かの判断基準について、図６を参照して説明する。
【００３２】
ＴＣＰにおける双方向通信においてさらし端末関係にある通信路の組か否かを決定する際に、端末ｋとｌとの間でキャリアセンスの可否の状況が異なるか、端末ｍとｎとの間でキャリアセンスの可否の状況が異なるかを基準に判断する。端末ｋに対する端末ｍからのキャリアセンスの可否の状況をS（k,m）で表すと、If [ {S(k,m) or
S(k,n)} ≠
{S(l,m) or S(l,n)} ] or [{S(k,m) or S(l,m)} ≠ {S(k,n) or S(l,n)}]＝TRUEかFALSEかを判定する。
【００３３】
例えば、（１）端末ｋは端末ｍ及びｎからキャリアセンスができないが端末ｌは端末ｍあるいはｎからキャリアセンスができる場合は、端末ｋからｌに対して信号を送信することに伴い送信禁止期間を端末ｍ及びｎが知ることができないため、端末ｌに対して端末ｍあるいはｎから信号を送信する際にさらし端末問題が生じる。
【００３４】
また（２）端末ｍは端末ｋ及びｌからキャリアセンスができないが端末ｎは端末ｋあるいはｌからキャリアセンスができる場合は、端末ｍからｎに対して信号を送信することに伴い送信禁止期間を端末ｋ及びｌが知ることができないため、端末ｎに対して端末ｋあるいはｌから信号を送信する際にさらし端末問題が生じる。
【００３５】
よって、上記（１）、（２）により何れかの通信においてさらし端末問題が生じる（条件式がTRUE）ならば、彩色グラフにて通信路Ｃｋ，ｌ及びＣｍ，ｎの関係をさらし端末問題が発生する通信路として干渉関係ありとする。ここで、干渉とは、さらし端末問題が発生する無線局同士の関係をいう。
【００３６】
一方何れかの通信により送受信局ともに送信禁止期間を知りうる、あるいは送受信局ともに送信禁止期間を知り得ない、即ち送受信局ともに通信できない場合（条件式がFALSE）ならば、彩色グラフにて通信路Ｃｋ，ｌ及びＣｍ，ｎの関係をさらし端末が発生しない通信路として干渉関係なしとする。この判定を全ての通信路間に対して行うことで、各通信路間の接続関係を彩色グラフにて表すことができる。なおこの発明はＴＣＰに限定されるものではなく、他のプロトコルに適用可能である。また双方向通信に限られるのではなく、単方向通信に適用する場合は上記条件式の何れかを満たせばよいことは言うまでもない。
【００３７】
無線チャネル設定部１１０は、無線チャネル割り当て部１１２において、隣接ノード情報作成部１０８において作成された彩色グラフに基づいて、各無線リンクへチャネルの割り当てを行う。例えば、無線チャネル設定部１１０は、接続されたさらし端末問題が発生するリンク同士に割り当てる周波数を異なるように割り当てる。このように、無線メッシュネットワークの接続関係から彩色グラフを作り、なんらかのグラフ彩色アルゴリズムを用いて彩色グラフの彩色を行った結果から各無線リンクへのチャネル割り当てを行うことで、さらし端末問題による通信品質低下を防ぐことができる。
【００３８】
このようなチャネル割り当ての結果、すべての無線リンクへのチャネル割り当てに必要なチャネル数をＮ、与えられたチャネル数、すなわち使用できるチャネル数をＭとする（Ｍ、Ｎは、正の整数である）。無線チャネル割り当て部１１２は、色（チャネル）番号を１からＭで表す。もし、Ｎ＞Ｍならば、Ｍ＋１番からＮ番のチャネルが割り当てられた無線リンクの集合をＶ´で表す。このＶ´の無線リンクに、１番からＭ番のチャネルのうち、干渉が少ないものを割り当てる。すなわち、全てのリンクへの周波数割り当てに必要な周波数の数が、使用できる周波数の数よりも多い場合、使用できる周波数が割り当てられたリンク以外のリンクに対して、使用できる周波数のうち干渉が少ない周波数を割り当てる。つまり、使用できる周波数が割り当てられたリンク以外のリンクに対して、使用できる周波数を重複して割り当てる。
【００３９】
辺間隔度計算部１１４は、Ｖ´の各無線リンクについて辺間隔度を求める。辺間隔度は、リンクのネットワークにおける重要度を示す指標であり、以下のように算出される。Ｇ＝（Ｖ，Ｅ）をネットワークのグラフ構造とする。ただしＶをノードの集合、Ｅを辺の集合とする。２頂点ｓ，ｔと辺ｅ∈Ｅに対し、ｅのｓ，ｔにおける辺間隔度ｅｂ（ｓ，ｔ）（ｅ）とは、ｓ，ｔ間の最短パス数ｓｐ（ｓ，ｔ）のうちｅを通る最短パス数ｓｐ（ｓ，ｔ）（ｅ）の割合のことを示す。辺ｅ∈Ｅの辺中心間隔度ｅｂｃ（ｓ，ｔ）（ｅ）とは、ｅの任意の２頂点における辺間隔度の合計である。以下、ここでは辺中心間隔度のことを辺間隔度と表記しこちらの意味で使うこととする。辺間隔度は以下のように計算を行う。
【００４０】
【数１】
2008047946.tif 000003
辺間隔度は「メッシュネットワークの無線局の組ｓ，ｔの最短経路ｐｓｔが該当するリンクを通るような組の数」と定義される。
【００４１】
一例として、図７に示すようなメッシュネットワークの接続関係が与えられた場合について説明する。図７には、無線局１００１、１００２、１００３、１００４、１００５、１００６、１００７、１００８および１００９からなるメッシュネットワークが示される。また、図７には、メッシュネットワーク内のすべてのリンクにおける辺間隔度の計算結果が示される（図中の数値）。
【００４２】
リンク判定部１１６は、辺間隔度計算部１１４において求められたＶ´の無線リンクにおける辺間隔度の平均値ａｖｅおよび標準偏差ｓｄを算出し、ａｖｅおよびｓｄを用いて閾値Ｔを求める。例えば、閾値Ｔとして、ａｖｅ−２ｓｄ、ａｖｅ−ｓｄ、ａｖｅ、ａｖｅ＋ｓｄおよびａｖｅ＋２ｓｄのいずれか１つの値を用いる。
【００４３】
リンク判断部１１６は、Ｖ´の無線リンクの辺間隔度がこの閾値Ｔより小さいリンクを切断する。このようにすることにより、メッシュネットワークにおける接続率の低下を抑えつつ、干渉を抑制することができる。
【００４４】
次に、本実施例にかかる無線局の動作について、図８を参照して説明する。
【００４５】
各無線局は、自無線局のＩＤをブロードキャストする（ステップＳ６０２）。隣接ノード収集部１０６は各無線局からブロードキャストされた無線局のＩＤを受信し、各無線局の隣接ノード情報作成部１０８は隣接ノード情報を作成し（ステップＳ６０４）、自無線局のＩＤおよび作成した隣接ノード情報を、他の無線局にブロードキャストする（ステップＳ６０６）。他の無線局のＩＤおよび隣接ノード情報を受信した無線局は、隣接ノードの隣接ノード情報、すなわち隣接ノードにより収集された隣接ノード情報を作成する（ステップＳ６０８）。
【００４６】
次に、隣接ノード情報作成部１０８はさらし端末問題を発生させる条件を算出する。すなわち、彩色グラフを作成する（ステップＳ６１０）。
【００４７】
次に、無線チャネル割り当て部１１２は、全ての無線リンクに必要なチャネル数（Ｎ）が、与えられたチャネル数（Ｍ）、すなわち使用できるチャネル数より多いか否かを判断する（ステップＳ６１２）。
【００４８】
全ての無線リンクに必要なチャネル数が、与えられたチャネル数、すなわち使用できるチャネル数より多くないと判断した場合、すなわち与えられたチャネル数の方が多いと判断した場合（ステップＳ６１２：ＮＯ）、無線チャネル割り当て部１１２は、使用できるチャネルを全ての無線リンクに割り当てる（ステップＳ６１４）。例えば、使用できるチャネル（周波数）のうち干渉が少ない（小さい）チャネルを全ての無線リンクに割り当てる。
【００４９】
一方、全ての無線リンクに必要なチャネル数が、与えられたチャネル数、すなわち使用できるチャネル数より多いと判断した場合（ステップＳ６１２：ＹＥＳ）、無線チャネル割り当て部１１２は、使用できる周波数が割り当てられたリンク以外のリンクに対して、使用できる周波数のうち干渉が少ない周波数を割り当てる（ステップＳ６１６）。例えば、Ｍ＋１番からＮ番に対応する無線リンクへ、１番からＭ番に対応するチャネルの内、干渉が少ないチャネルを割り当てる。
【００５０】
次に、辺間隔度計算部１１４は、Ｍ＋１番からＮ番に対応する無線リンクについて辺間隔度を求める（ステップＳ６１８）。
【００５１】
次に、リンク判定部１１６は、辺間隔度計算部１１４において求められた辺間隔度を用いて、その平均値および標準偏差を求める（ステップＳ６２０）。
【００５２】
次に、リンク判定部１１６は、辺間隔度の平均値および標準偏差により求められる閾値にしたがって、該閾値以下となる無線リンクを使用禁止とする（ステップＳ６２２）。
【００５３】
上述したように、本実施例では、使用を禁止する無線リンクの決定を行う際に、辺間隔度という指標を用いてこの選択を行う。メッシュネットワークにおける既存のチャネル割り当て方式において、辺間隔度という情報を利用するものは存在しない。本実施例では、各無線リンクは辺間隔度という尺度を持ち、辺間隔度の高いリンクはネットワークの連結性を高く維持するためにも重要な役割を果たす。つまり、辺間隔度が小さい無線リンクを使用せずともネットワークの連結性を維持しやすいが、辺間隔度が大きい無線リンクの使用を禁止すればネットワークが非連結になりやすい。よって、辺間隔度の低いリンクの使用を禁止することにより、連結を保ちながら干渉を軽減できる。
【００５４】
本実施例によれば、干渉を低減させること、連結率を維持させることを同時に満たしながら、無線メッシュネットワークへのチャネル割り当てを実現することができる。
【００５５】
上述した実施例により、チャネル割り当てを行った場合の連結率（ｃｏｎｎｅｃｔｉｖｉｔｙ）と干渉率（ｉｎｔｅｒｆｅｒｅｎｃｅ  ｒａｔｉｏ）について、表１の仮定に基づいて求めた結果を、図７および図８を参照して説明する。ここで、連結率とは、上述した方法によりチャネル割り当てを複数回行った場合に、無線局（ノード）の対の総数に対する、互いに連結である無線局の対の数の割合の平均値を示す。全ての無線局が直接接続される場合に限らず、対象となる無線局に他の無線局を介して接続される場合も含む。
【００５６】
また、干渉率とは、異なるチャネルを割り当てなければならないリンク対のうち、同一チャネルを割り当てたリンク対の割合を示す。
【００５７】
図９および図１０において、横軸は通信距離（ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｒａｎｇｅ）である。
【００５８】
【表１】
2008047946.tif 000004
図９および図１０において、ｃａｓｅ１はリンクの除去を行わない、すなわちリンクの使用を禁止しない場合であり、ｃａｓｅ２は辺間隔度がａｖｅ−２ｓｄ以下となるリンクを除去する場合であり、ｃａｓｅ３は辺間隔度がａｖｅ−ｓｄ以下となるリンクを除去する場合であり、ｃａｓｅ４は辺間隔度がａｖｅ以下となるリンクを除去する場合であり、ｃａｓｅ５は辺間隔度がａｖｅ＋ｓｄ以下となるリンクを除去する場合であり、ｃａｓｅ６は辺間隔度がａｖｅ＋２ｓｄ以下となるリンクを除去する場合である。
【００５９】
すなわち、ｃａｓｅ４とは、Ｖ´の無線リンクのうち辺間隔度がａｖｅ以下であるような無線リンクの使用を禁止するという選択基準を用いた場合の結果である。
【００６０】
図９および図１０によれば、辺間隔度を導入して使用を禁止するリンクを選択することにより、連結率を高く保ちながら干渉率を軽減することができることがわかる。
【産業上の利用可能性】
【００６１】
本発明にかかる無線周波数割り当て装置、無線通信システムおよび無線周波数割り当て方法は、仮想キャリアセンスを行う自律分散型ディジタル無線伝送システムに適用できる。
【図面の簡単な説明】
【００６２】
【図１】さらし端末問題を示す説明図である。
【図２】さらし端末問題を示す説明図である。
【図３】本発明の一実施例にかかるメッシュネットワークの構成を示す説明図である。
【図４】本発明の一実施例にかかる無線局を示す部分ブロック図である。
【図５】彩色グラフの一例を示す説明図である。
【図６】チャネルの設定方法を示す説明図である。
【図７】辺間隔度の計算結果の一例を示す説明図である。
【図８】本発明の一実施例にかかる無線局の動作を示すフロー図である。
【図９】本発明の一実施例の効果を示す特性図である。
【図１０】本発明の一実施例の効果を示す特性図である。
【符号の説明】
【００６３】
１００、１００１、１００２、１００３、１００４、１００５、１００６、１００７、１００８、１００９  無線局
１０２  送受信部
１０４  制御部
１０６  隣接ノード情報収集部
１０８  隣接ノード情報作成部
１１０  無線チャネル設定部
１１２  無線チャネル割り当て部
１１４  辺間隔度計算部
１１６  リンク判定部
【図１】
2008047946.tif 000005
【図２】
2008047946.tif 000006
【図３】
2008047946.tif 000007
【図４】
2008047946.tif 000008
【図５】
2008047946.tif 000009
【図６】
2008047946.tif 000010
【図７】
2008047946.tif 000011
【図８】
2008047946.tif 000012
【図９】
2008047946.tif 000013
【図１０】
2008047946.tif 000014