(57)【特許請求の範囲】
【請求項１】
複数の無線装置がメッシュ状に配置されたネットワークに用いられ、複数のチャネルを用いて無線通信を行なう無線装置であって、
経路情報を格納するルーティングテーブルと、
各々が前記複数のチャネルの中から選択された１つのチャネルを用いてパケットを送受信する複数のインターフェースと、
評価対象のリンクを通過し、かつ、ループからなる経路を排除した経路を通過する全てのフローである複数のフローにおけるチャネル分布に基づいて前記評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合をフロー内のチャネル干渉を考慮して演算し、その演算したスループットの最大値に対する割合に基づいて送信先までの経路を選択するための指標である経路指標を演算するとともに、その演算した経路指標を前記送信先に対応付けて前記ルーティングテーブルを作成するテーブル作成手段と、
前記ルーティングテーブルから前記送信先までの最適経路を選択してパケットを送信する通信手段とを備える無線装置。
【請求項２】
前記テーブル作成手段は、前記スループットの最大値に対する割合が第１の割合であるとき第１の値になり、前記スループットの最大値に対する割合が前記第１の割合よりも小さい第２の割合であるとき前記第１の値よりも大きい第２の値になる経路指標と前記経路指標に対応付けられた送信先とを格納して前記ルーティングテーブルを作成する、請求項１に記載の無線装置。
【請求項３】
前記テーブル作成手段は、前記送信先までの各リンクを前記評価対象のリンクとしたときの前記スループットの最大値に対する割合を演算し、各リンクにおける前記スループットの最大値に対する割合の逆数を前記各リンクのコストとして演算し、その演算した各リンクのコストの総和を演算する処理を前記送信先までの全ての経路である複数の経路について実行し、前記複数の経路に対応する複数の前記総和のうち、最小の総和を前記経路指標として演算する、請求項１に記載の無線装置。
【請求項４】
前記テーブル作成手段は、前記チャネル分布に基づいて前記複数のフローにおけるチャネルの分布パターンの全種類を検出し、その検出した全種類の分布パターンを複数の基本分布パターンに分類して各基本分布パターンに分類された分布パターンの個数を計数し、その計数した個数と前記全種類の分布パターンの個数と各基本分布パターンにおけるスループットの実測された最大値に対する割合とに基づいて前記評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合を演算する、請求項１に記載の無線装置。
【請求項５】
前記テーブル作成手段は、前記各基本分布パターンに分類された分布パターンの個数と、前記全種類の分布パターンの個数と、各基本分布パターンにおけるスループットの実測された最大値に対する割合とに基づいて、各基本分布パターンにおけるスループットの実測された最大値に対する割合をチャネルの分布パターンが各基本分布パターンに分類される確率によって重み付け平均し、前記評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合を演算する、請求項４に記載の無線装置。
【請求項６】
前記テーブル作成手段は、前記評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合に反比例するように前記経路指標を演算する、請求項４または請求項５に記載の無線装置。
【請求項７】
前記テーブル作成手段は、前記演算したスループットの最大値に対する割合に基づいて、当該無線装置と当該無線装置に隣接する隣接無線装置との間の全てのリンクについてリンクのコストを演算し、
前記通信手段は、前記テーブル作成手段が前記全てのリンクについて前記リンクのコストを演算すると、その演算されたリンクのコストをフラッディングする、請求項４から請求項６のいずれか１項に記載の無線装置。
【請求項８】
前記テーブル作成手段は、他の無線装置からフラッディングされたリンクのコストを受信し、その受信したリンクのコストに基づいて、前記経路指標を演算する、請求項７に記載の無線装置。
【請求項９】
前記テーブル作成手段は、前記評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合に基づいて、無線通信を行なうアプリケーションの種類に応じて異なる方法を用いて前記経路指標を演算する、請求項１に記載の無線装置。
【請求項１０】
前記テーブル作成手段は、前記無線通信の送信レートが相対的に高い場合、前記評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合に反比例するように前記経路指標を演算する、請求項９に記載の無線装置。
【請求項１１】
請求項１から請求項１０のいずれか１項に記載の無線装置を備えたメッシュ型ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、無線装置およびそれを備えたメッシュ型ネットワークに関し、特に、自律的に構築される無線ネットワークを構成する無線装置およびそれを備えたメッシュ型ネットワークに関するものである。
【背景技術】
【０００２】
複数のインターフェースを搭載し、マルチチャネルで動作可能なアドホックネットワーク用の端末が利用できるようになってきており、マルチチャネルでアドホックネットワークを構成できるようになってきている。
【０００３】
マルチチャネルのアドホックネットワークは、１つのチャネルでネットワークを構成した場合に比べ、ネットワークのスループットが向上することが指摘されている（非特許文献１，２）。
【０００４】
このような、マルチチャネルを用いたアドホックネットワークにおいては、複数のチャネルに跨って張られたリンクをそれぞれのチャネルの状態やリンク間の干渉の度合を適切に評価し、その評価結果をデータの転送に反映させることが、ネットワークの性能をより向上させる上で重要である。
【０００５】
マルチチャネル環境においては、各チャネルの状態に依存して干渉の度合に差が生じる。電子レンジ等の電子機器およびＢｌｕｅｔｏｏｔｈ等の無線デバイスの影響等は、ルーティング方法によって回避し難い干渉であるが、同一ネットワーク内のリンク間の干渉というネットワークのトポロジーに依存した干渉であれば、ルーティングメトリックに干渉の影響を含めることにより、干渉の影響を軽減できる。
【０００６】
そして、このようなメトリックによって干渉の影響を回避する方法が提案されている（非特許文献３〜５）。
【０００７】
非特許文献３に記載の回避方法は、リンクの帯域の大きさを考慮したメトリックを用いる。即ち、従来のメトリックであるＥＴＸ（Ｅｘｐｅｃｔｅｄ  Ｔｒａｎｓｍｉｓｓｉｏｎ Ｃｏｕｎｔ）は、次式に示すようにパケットロス率ｐのみによって決定される。
【０００８】
【数１】
0004517060.tif 000002
【０００９】
式（１）によって演算されるＥＴＸは、リンクの帯域を考慮していないため、低ロスでありさえすれば、帯域の小さいリンクであっても高く評価する傾向がある。そこで、帯域の大きさを考慮したＥＴＴ（Ｅｘｐｅｃｔｅｄ  Ｔｒａｎｓｍｉｓｓｉｏｎ Ｔｉｍｅ）を次式によって演算する。
【００１０】
【数２】
0004517060.tif 000003
【００１１】
式（２）において、Ｓは、パケットサイズであり、Ｂは、データレートである。
【００１２】
そして、式（２）によって演算されたＥＴＴを次式に代入してＷＣＥＴＴ（Ｗｅｉｇｈｔｅｄ  Ｃｕｍｕｌａｔｉｖｅ  ＥＴＴ）を演算する。
【００１３】
【数３】
0004517060.tif 000004
【００１４】
式（３）において、βは、０≦β≦１の範囲の値を持つ可変パラメータであり、Ｘは、チャネルが同じであるＥＴＴの合計である。また、ｉは、ホップ数である。
【００１５】
この方式は、フロー内の干渉を考慮しているが、フロー間の干渉を考慮していないため、フロー間の干渉が多い環境では、高いスループットを達成できない。また、メトリックＷＣＥＴＴは、等張性（ｉｓｏｔｏｎｉｔｙ）を満たしていない。そのため、この方式は、プロアクティブ型であり、かつ、Ｈｏｐ−ｂｙ−Ｈｏｐ型のルーティングプロトコルにおいては、経路選択がループフリーであること、および経路の最適解を保証できない。
【００１６】
ここで、等張性とは、ループからなる経路を排除して経路選択を行なうことを言う。また、Ｈｏｐ−ｂｙ−Ｈｏｐ型のルーティングプロトコルとは、中継器である無線装置がパケットの送信先のみを参照してパケットを送信先へ中継するための経路を選択するルーティングプロトコルを言う。
【００１７】
非特許文献４に記載の回避方法は、フロー間の干渉を考慮し、等張性を満たした方式である。即ち、この回避方法は、次式によってメトリックＭＩＣを演算する。
【００１８】
【数４】
0004517060.tif 000005
【００１９】
式（４）において、Ｎは、ネットワークにおける端末の総数である。また、ｍｉｎ（ＥＴＴ）は、ネットワークにおける最小のＥＴＴであり、無線カードの最低の送信レートに基づいて見積もられる。更に、Ｎｌは、リンクｌ上で相互に干渉する隣接無線装置のセットである。更に、ＣＨ（ｉ）は、端末ｉに割り当てられたチャネルである。更に、ｐｒｅｖ（ｉ）は、経路ｐに沿った端末ｉの以前のホップ数である。
【００２０】
このメトリックＭＩＣは、第２項（ＣＲＣ）によって、このままでは、等張性を満たさないが、バーチャル端末を用いることによって等張性を満たす。
【００２１】
更に、非特許文献５に記載の回避方法は、上述したＷＣＥＴＴを用いて干渉の影響を詳細に見積もる方式である。
【非特許文献１】A. Raniwala, and T. Chiueh, “Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network,” Proc. INFOCOM, 2005.
【非特許文献２】L. Loyola, T. Kumagai, K. Nagata, S. Otsuki and S. Aikawa, “Multi-channel wireless LAN mesh architecture with DCF-based inter AP communication and idle channel search packet forwarding,” Proc. GLOBECOM’05, Vol. 6, pp. 3279-3284, 2005.
【非特許文献３】R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks”, in Proc. ACM MOBICOM, pp. 114-128, 2004.
【非特許文献４】Y. Yang, J. Wang, and R. Kravets, “Designing routing metrics for mesh networks,” Proc. WiMesh’05, 2005.
【非特許文献５】P. Subramanian, M. M. Buddhicot, and S. Miller, “Interference aware routing in multi-radio wireless mesh networks,” Proc. WiMesh’06, 2006.
【発明の開示】
【発明が解決しようとする課題】
【００２２】
しかし、非特許文献３に記載の方法は、等張性を満たしていないため、プロアクティブ型であり、かつ、Ｈｏｐ−ｂｙ−Ｈｏｐ型のルーティングプロトコルにおいては、経路選択がループフリーであること、および経路の最適解を保証できないという問題がある。
【００２３】
また、非特許文献４に記載の方法においては、最短経路探索に用いられるダイクストラアルゴリズムの計算量は、端末数に応じて指数的に増加するため、ネットワークの規模が大きくなると計算量が莫大に増加し、規模が大きいネットワークに対して実装し難くなるという問題がある。
【００２４】
更に、非特許文献５に記載の方法は、ＷＣＥＴＴを用いているため、等張性を満たさないという問題がある。
【００２５】
そこで、この発明は、かかる問題を解決するためになされたものであり、その目的は、等張性を満たし、実装が容易なルーティングプロトコルに従って経路選択を行なう無線装置を提供することである。
【００２６】
また、この発明の別の目的は、等張性を満たし、実装が容易なルーティングプロトコルに従って経路選択を行なう無線装置を備えたメッシュ型ネットワークを提供することである。
【課題を解決するための手段】
【００２７】
この発明によれば、無線装置は、複数の無線装置がメッシュ状に配置されたネットワークに用いられ、複数のチャネルを用いて無線通信を行なう無線装置であって、ルーティングテーブルと、複数のインターフェースと、テーブル作成手段と、通信手段とを備える。ルーティングテーブルは、経路情報を格納する。複数のインターフェースは、各々が複数のチャネルの中から選択された１つのチャネルを用いてパケットを送受信する。テーブル作成手段は、フロー内のチャネル干渉を考慮したときのフロー内のスループットの最大値に対する割合が相対的に大きい経路をループからなる経路を排除して検出し、その検出した経路を送信先までの最適経路として格納することによりルーティングテーブルを作成する。通信手段は、ルーティングテーブルから最適経路を選択してパケットを送信する。
【００２８】
好ましくは、テーブル作成手段は、スループットの最大値に対する割合が相対的に大きいとき相対的に小さくなり、スループットの最大値に対する割合が相対的に小さいとき相対的に大きくなる経路指標と経路指標に対応付けられた送信先とを最適経路としてルーティングテーブルに格納する。
【００２９】
好ましくは、テーブル作成手段は、評価対象のリンクを通過する全てのフローである複数のフローにおけるチャネル分布に基づいて評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合を演算し、その演算したスループットの最大値に対する割合に基づいて経路指標を演算するとともに、その演算した経路指標を送信先に対応付けてルーティングテーブルに格納する。
【００３０】
好ましくは、テーブル作成手段は、チャネル分布に基づいて複数のフローにおけるチャネルの分布パターンの全種類を検出し、その検出した全種類の分布パターンを複数の基本分布パターンに分類して各基本分布パターンに分類された分布パターンの個数を計数し、その計数した個数と全種類の分布パターンの個数と各基本分布パターンにおけるスループットの実測された最大値に対する割合とに基づいて評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合を演算する。
【００３１】
好ましくは、テーブル作成手段は、各基本分布パターンに分類された分布パターンの個数と、全種類の分布パターンの個数と、各基本分布パターンにおけるスループットの実測された最大値に対する割合とに基づいて、各基本分布パターンにおけるスループットの実測された最大値に対する割合をチャネルの分布パターンが各基本分布パターンに分類される確率によって重み付け平均し、評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合を演算する。
【００３２】
好ましくは、テーブル作成手段は、評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合に反比例するように経路指標を演算する。
【００３３】
好ましくは、テーブル作成手段は、演算したスループットの最大値に対する割合に基づいて、当該無線装置と当該無線装置に隣接する隣接無線装置との間の全てのリンクについてリンクのコストを演算する。通信手段は、テーブル作成手段が全てのリンクについてリンクのコストを演算すると、その演算されたリンクのコストをフラッディングする。
【００３４】
好ましくは、テーブル作成手段は、他の無線装置からフラッディングされたリンクのコストを受信し、その受信したリンクのコストに基づいて、経路指標を演算する。
【００３５】
好ましくは、テーブル作成手段は、評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合に基づいて、無線通信を行なうアプリケーションの種類に応じて異なる方法を用いて経路指標を演算する。
【００３６】
好ましくは、テーブル作成手段は、無線通信の送信レートが相対的に高い場合、評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合に反比例するように経路指標を演算する。
【００３７】
また、この発明によれば、メッシュ型ネットワークは、請求項１から請求項１０のいずれか１項に記載の無線装置を備える。
【発明の効果】
【００３８】
この発明によれば、無線装置は、フロー内のチャネル干渉を考慮したときのフロー内のスループットの最大値に対する割合が相対的に大きい経路をループからなる経路を排除して検出し、その検出した経路からなる送信先までの最適経路を格納してルーティングテーブルを作成し、その作成したルーティングテーブルから送信先までの経路を選択する。つまり、無線装置は、フロー内のチャネル干渉を考慮したときのフロー内のスループットの最大値に対する割合が相対的に大きい経路を選択する。
【００３９】
従って、この発明によれば、フロー内のチャネル干渉を考慮したときのフロー内のスループットの最大値に対する割合に基づいて経路を選択するので、等張性を満たし、実装が容易なルーティングプロトコルに従って、計算量を増大させることなく経路を選択できる。
【発明を実施するための最良の形態】
【００４０】
本発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰返さない。
【００４１】
図１は、この発明の実施の形態によるメッシュ型ネットワークの概略図である。メッシュ型ネットワーク１００は、無線装置１〜７を備える。無線装置１〜７は、無線通信空間にメッシュ状に配置され、無線メッシュネットワークを自律的に構成している。
【００４２】
そして、無線装置１〜７の各々は、例えば、２つのインターフェースＩＦ１，ＩＦ２を有し、２つのインターフェースＩＦ１，ＩＦ２を用いて無線通信を行なう。この場合、各無線装置１〜７における２つのインターフェースＩＦ１，ＩＦ２は、メッシュ型ネットワーク１００が構成された時点で相互に異なるチャネルが割り当てられている。
【００４３】
より具体的には、各無線装置１〜７における２つのインターフェースＩＦ１，ＩＦ２は、ｎ（ｎは２以上の整数）個のチャネルＣｈ１〜Ｃｈｎから任意に選択された２つのチャネルＣｈｉ，Ｃｈｊ（ｉ，ｊは、ｉ≠ｊを満たす正の整数）が割り当てられる。従って、各無線装置１〜７において２つのインターフェースＩＦ１，ＩＦ２に割り当てられる２つのチャネルは、他の無線装置において２つのインターフェースＩＦ１，ＩＦ２に割り当てられた２つのチャネルと同じであることもあれば、異なることもある。
【００４４】
メッシュ型ネットワーク１００においては、各無線装置１〜７は、図１における紙面上、横方向および斜め方向に存在する隣接無線装置との間で直接無線通信を行なうことができる。
【００４５】
従って、無線装置１は、インターフェースＩＦ１（チャネルＣｈｉ）を用いて無線装置４との間で無線通信を行なうとともに、インターフェースＩＦ２（チャネルＣｈｊ）を用いて無線装置３との間で無線通信を行なう。
【００４６】
そして、無線装置１は、インターフェースＩＦ１（チャネルＣｈｉ）を用いて無線装置４との間で無線通信を行なう場合、無線装置２，３を介して無線通信４との間で無線通信を行なうことができ、無線装置７を介して無線装置４との間で無線通信を行なうこともでき、無線装置６，５を介して無線通信４との間で無線通信を行なうこともできる。
【００４７】
また、無線装置１は、インターフェースＩＦ２（チャネルＣｈｊ）を用いて無線装置３との間で無線通信を行なう場合、無線装置２を介して無線通信３との間で無線通信を行なうことができ、無線装置７を介して無線装置３との間で無線通信を行なうこともでき、無線装置６，５，４を介して無線通信３との間で無線通信を行なうこともできる。
【００４８】
このように、メッシュ型ネットワーク１００においては、各無線装置１〜７は、２つのインターフェースＩＦ１，ＩＦ２を用いてマルチホップによって送信先との間で無線通信を行なう。従って、メッシュ型ネットワーク１００においては、マルチチャネル環境におけるアドホックネットワークが構成される。
【００４９】
しかし、メッシュ型ネットワーク１００のスループットを向上させるためには、各無線装置１〜７が２つのチャネルを用いて行なう無線通信（＝フロー）のスループットを向上させる必要がある。
【００５０】
そこで、以下においては、各無線装置１〜７が２つのチャネルを用いて行なう無線通信（＝フロー）のスループットを向上させるように経路選択を行なう通信方式について説明する。
【００５１】
なお、この発明の実施の形態においては、送信元と送信先との間で無線通信経路を確立するプロトコルとしてＯＬＳＲ（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）プロトコルを用いる。このＯＬＳＲプロトコルは、プロアクティブ型、かつ、Ｈｏｐ−ｂｙ−Ｈｏｐ型のルーティングプロトコルであり、ＨｅｌｌｏメッセージおよびＴＣ（Ｔｏｐｏｌｏｇｙ  Ｃｏｎｔｒｏｌ）メッセージを用いて経路情報を交換し、ルーティングテーブルを作成するプロトコルである。
【００５２】
図２は、図１に示す無線装置１の構成を示す概略ブロック図である。無線装置１は、アンテナ１０，１１と、入力部１２と、出力部１３と、ユーザアプリケーション１４と、通信制御部１５とを含む。
【００５３】
アンテナ１０，１１の各々は、無線通信空間を介して他の無線装置からデータを受信し、その受信したデータを通信制御部１５へ出力するとともに、通信制御部１５からのデータを無線通信空間を介して他の無線装置へ送信する。
【００５４】
入力部１２は、無線装置１の操作者が入力したメッセージおよびデータの宛先を受付け、その受付けたメッセージおよび宛先をユーザアプリケーション１４へ出力する。出力部１３は、ユーザアプリケーション１４からの制御に従ってメッセージを表示する。
【００５５】
ユーザアプリケーション１４は、入力部１２からのメッセージおよび宛先に基づいてデータを生成して通信制御部１５へ出力する。
【００５６】
通信制御部１５は、ＡＲＰＡ（Ａｄｖａｎｃｅｄ  Ｒｅｓｅａｒｃｈ  Ｐｒｏｊｅｃｔｓ  Ａｇｅｎｃｙ）インターネット階層構造に従って、通信制御を行なう複数のモジュールからなる。即ち、通信制御部１５は、無線インターフェースモジュール１６と、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）モジュール１７と、バッファ１８と、ＬＬＣ（Ｌｏｇｉｃａｌ  Ｌｉｎｋ  Ｃｏｎｔｒｏｌ）モジュール１９と、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）モジュール２０と、ルーティングテーブル２１と、ＴＣＰモジュール２２と、ＵＤＰモジュール２３と、ルーティングデーモン２４とからなる。
【００５７】
無線インターフェースモジュール１６は、物理層に属し、２つのインターフェースＩＦ１，ＩＦ２を有する。そして、無線インターフェースモジュール１６は、所定の規定に従って送信信号または受信信号の変復調を行なうとともに、２つのインターフェースＩＦ１，ＩＦ２の少なくとも１つを用いて信号を送受信する。
【００５８】
ＭＡＣモジュール１７は、ＭＡＣ層に属し、ＭＡＣプロトコルを実行して、以下に述べる各種の機能を実行する。
【００５９】
即ち、ＭＡＣモジュール１７は、ルーティングデーモン２４から受けたＨｅｌｌｏパケットを無線インターフェースモジュール１６を介してブロードキャストする。また、ＭＡＣモジュール１７は、データ（パケット）の再送制御等を行なう。
【００６０】
バッファ１８は、データリンク層に属し、パケットを一時的に格納する。ＬＬＣモジュール１９は、データリンク層に属し、ＬＬＣプロトコルを実行して隣接する無線装置との間でリンクの接続および解放を行なう。
【００６１】
ＩＰモジュール２０は、インターネット層に属し、ＩＰパケットを生成する。ＩＰパケットは、ＩＰヘッダと、上位のプロトコルのパケットを格納するためのＩＰデータ部とからなる。そして、ＩＰモジュール２０は、ＴＣＰモジュール２２からデータを受けると、その受けたデータをＩＰデータ部に格納してＩＰパケットを生成する。
【００６２】
そうすると、ＩＰモジュール２０は、プロアクティブ型のルーティングプロトコルであるＯＬＳＲプロトコルに従ってルーティングテーブル２１を検索し、生成したＩＰパケットを送信するための経路を決定する。そして、ＩＰモジュール２０は、その決定した経路に沿ってＩＰパケットを送信先へ送信する。
【００６３】
ルーティングテーブル２１は、インターネット層に属し、後述するように、各送信先に対応付けて経路情報を格納する。
【００６４】
ＴＣＰモジュール２２は、トランスポート層に属し、ＴＣＰパケットを生成する。ＴＣＰパケットは、ＴＣＰヘッダと、上位のプロトコルのデータを格納するためのＴＣＰデータ部とからなる。そして、ＴＣＰモジュール２２は、生成したＴＣＰパケットをＩＰモジュール２０へ送信する。
【００６５】
ＵＤＰモジュール２３は、トランスポート層に属し、ルーティングデーモン２４によって作成されたＵｐｄａｔｅパケットをブロードキャストし、他の無線装置からブロードキャストされたＵｐｄａｔｅパケットを受信してルーティングデーモン２４へ出力する。
【００６６】
ルーティングデーモン２４は、プロセス／アプリケーション層に属し、他の通信制御モジュールの実行状態を監視するとともに、他の通信制御モジュールからのリクエストを処理する。
【００６７】
また、ルーティングデーモン２４は、他の無線装置から受信したＨｅｌｌｏパケットの経路情報に基づいて、後述する方法によって、最適な経路を算出してルーティングテーブル２１をインターネット層に動的に作成する。
【００６８】
なお、図１に示す無線装置２〜７の各々も、図２に示す無線装置１の構成と同じ構成からなる。
【００６９】
図３は、ＯＬＳＲプロトコルにおけるパケットＰＫＴの構成図である。パケットＰＫＴは、パケットヘッダＰＨＤと、メッセージヘッダＭＨＤとからなる。なお、パケットＰＫＴは、ＵＤＰモジュール２３のポート番号６９８番を使用して送受信される。
【００７０】
パケットヘッダＰＨＤは、パケット長と、パケットシーケンス番号とからなる。パケット長は、１６ビットのデータからなり、パケットのバイト数を表す。また、パケットシーケンス番号は、１６ビットのデータからなり、どのパケットが新しいかを区別するために用いられる。そして、パケットシーケンス番号は、新しいパケットが生成される度に“１”づつ増加される。従って、パケットシーケンス番号が大きい程、そのパケットＰＫＴが新しいことを示す。
【００７１】
メッセージヘッダＭＨＤは、メッセージタイプと、有効時間と、メッセージサイズと、発信元アドレスと、ＴＴＬと、ホップ数と、メッセージシーケンス番号と、メッセージとからなる。
【００７２】
メッセータイプは、８ビットのデータからなり、メッセージ本体に書かれたメッセージの種類を表し、０〜１２７は、予約済みである。有効時間は、８ビットのデータからなり、受信後に、このメッセージを管理しなければならない時間を表す。そして、有効時間は、仮数部と、指数部とからなる。
【００７３】
メッセージサイズは、１６ビットのデータからなり、メッセージの長さを表す。発信元アドレスは、３２ビットのデータからなり、メッセージを生成した無線装置を表す。ＴＴＬは、８ビットのデータからなり、メッセージが転送される最大ホップ数を指定する。そして、ＴＴＬは、メッセージが転送される時に”１”づつ減少される。そして、ＴＴＬが“０”である場合、メッセージは、転送されない。ホップ数は、８ビットのデータからなり、メッセージの生成元からのホップ数を表す。そして、ホップ数は、最初、“０”に設定され、転送される毎に“１”づつ増加される。メッセージシーケンス番号は、１６ビットのデータからなり、各メッセージに割当てられる識別番号を表す。そして、メッセージシーケンス番号は、メッセージが作成される毎に、“１”づつ増加される。メッセージは、送信対象のメッセージである。
【００７４】
ＯＬＳＲプロトコルにおいては、各種のメッセージが図３に示す構成のパケットＰＫＴを用いて送受信される。
【００７５】
図４は、図２に示すルーティングテーブル２１の構成図である。ルーティングテーブル２１は、送信先、次の無線装置、およびメトリックからなる。送信先、次の無線装置、およびメトリックは、相互に対応付けられている。“送信先”は、送信先の無線装置のＩＰアドレスを表す。“次の無線装置”は、送信先にパケットＰＫＴを送信するときに、次に送信すべき無線装置のＩＰアドレスを表す。
【００７６】
メトリックは、各無線装置１〜７が送信先へパケットを送信または中継する場合に各無線装置１〜７から送信先までの間に存在するリンクのコストの総和のうち、最小の総和からなる。メトリックについては、後に詳述する。
【００７７】
図５は、ネイバーリストＮＴＢＬの構成を示す概略図である。ネイバーリストＮＴＢＬは、自己のアドレスと、自己と隣接無線装置との間のリンクのチャネルと、隣接無線装置のアドレスと、隣接無線装置と自己から２ホップの無線装置との間のチャネルと、自己から２ホップの無線装置のアドレスとを含む。
【００７８】
自己のアドレス、自己と隣接無線装置との間のリンクのチャネル、隣接無線装置のアドレス、隣接無線装置と自己から２ホップの無線装置との間のチャネルおよび自己から２ホップの無線装置のアドレスは、相互に対応付けられる。
【００７９】
“自己のアドレス”は、ネイバーリストＮＴＢＬを作成する無線装置のＩＰアドレスからなる。自己と隣接無線装置との間のリンクのチャネルは、自己と隣接無線装置との間の無線通信に用いられているリンクのチャネルからなる。
【００８０】
“隣接無線装置のアドレス”は、ネイバーリストＮＴＢＬを作成する無線装置に隣接する無線装置のＩＰアドレスからなる。
【００８１】
隣接無線装置と自己から２ホップの無線装置との間のチャネルは、隣接無線装置と自己から２ホップの無線装置との間の無線通信に用いられているリンクのチャネルからなる。
【００８２】
自己から２ホップの無線装置のアドレスは、自己から２ホップの位置に存在する無線装置のＩＰアドレスからなる。
【００８３】
図６は、図２に示す無線インターフェースモジュール１６、ＩＰモジュール２０およびルーティングデーモン２４の機能のうち、本発明に係る機能を示す機能ブロック図である。
【００８４】
無線インターフェースモジュール１６は、インターフェースＩＦ１，ＩＦ２を含む。ＩＰモジュール２０は、通信手段２０１を含む。ルーティングデーモン２４は、テーブル作成手段２４１を含む。
【００８５】
インターフェースＩＦ１，ＩＦ２は、それぞれ、チャネルＣｈｉ，Ｃｈｊが割り当てられている。そして、インターフェースＩＦ１は、アンテナ１０に接続されており、インターフェースＩＦ２は、アンテナ１１に接続されている。
【００８６】
インターフェースＩＦ１は、通信手段２０１からパケットを受け、その受けたパケットをチャネルＣｈｉを用いてアンテナ１０を介してパケットを他の無線装置へ送信するとともに、アンテナ１０を介して他の無線装置から受信したパケットを通信手段２０１または通信手段２０１およびテーブル作成手段２４１へ出力する。
【００８７】
インターフェースＩＦ２は、通信手段２０１からパケットを受け、その受けたパケットをチャネルＣｈｊを用いてアンテナ１１を介して他の無線装置へ送信するとともに、アンテナ１１を介して他の無線装置から受信したパケットを通信手段２０１または通信手段２０１およびテーブル作成手段２４１へ出力する。
【００８８】
通信手段２０１は、ＴＣＰモジュール２２からＴＣＰパケットを受け、その受けたＴＣＰパケットをデータ部に格納してＩＰパケットを作成する。そして、通信手段２０１は、ルーティングテーブル２１を参照してＩＰパケットの送信経路を決定し、その決定した送信経路に沿ってインターフェースＩＦ１，ＩＦ２のいずれかを用いてＩＰパケットを送信する。
【００８９】
また、通信手段２０１は、インターフェースＩＦ１，ＩＦ２のいずれかから受けたパケットを上位層へ出力する。
【００９０】
テーブル作成手段２４１は、インターフェースＩＦ１，ＩＦ２のいずれかから受けたＨｅｌｌｏメッセージおよびＴＣメッセージに基づいて、後述する方法によって、ルーティングテーブル２１をインターネット層に動的に作成する。
【００９１】
この発明においては、各無線装置１〜７は、ＯＬＳＲプロトコルに従ってルーティングテーブル２１を作成する。ＯＬＳＲプロトコルに従ったルーティングテーブル２１の作成について説明する。無線装置１〜７は、ルーティングテーブル２１を作成する場合、ＨｅｌｌｏメッセージおよびＴＣメッセージを送受信する。
【００９２】
Ｈｅｌｌｏメッセージは、各無線装置１〜７が有する情報の配信を目的として、定期的に送信される。そして、この発明においては、各無線装置１〜７は、自己に割り当てられたチャネルを示すチャネル情報を含めてＨｅｌｌｏメッセージを送信する。このＨｅｌｌｏメッセージを受信することによって、各無線装置１〜７は、周辺の無線装置に関する情報を収集でき、自己の周辺にどのような無線装置が存在するのかを認識する。
【００９３】
ＯＬＳＲプロトコルにおいては、各無線装置１〜７は、ローカルリンク情報を管理する。そして、Ｈｅｌｌｏメッセージは、このローカルリンク情報の構築および送信を行なうためのメッセージである。ローカルリンク情報は、「リンク集合」、「隣接無線装置集合」、「２ホップ隣接無線装置集合とそれらの無線装置へのリンク集合」、「ＭＰＲ集合」、および「ＭＰＲセレクタ集合」を含む。
【００９４】
リンク集合は、直接的に電波が届く無線装置（隣接無線装置）の集合へのリンクのことであり、各リンクは、２つの無線装置間のアドレスの組の有効時間によって表現される。なお、有効時間は、そのリンクが単方向なのか双方向なのかを表すためにも利用される。
【００９５】
隣接無線装置集合は、各隣接無線装置のアドレス、およびその無線装置の再送信の積極度（Ｗｉｌｌｉｎｇｎｅｓｓ）等によって構成される。２ホップ隣接無線装置集合は、隣接無線装置に隣接する無線装置の集合を表す。
【００９６】
ＭＰＲ集合は、ＭＰＲとして選択された無線装置の集合である。なお、ＭＰＲとは、各パケットＰＫＴをメッシュ型ネットワーク１００内の全ての無線装置１〜７へ送信する場合、必要最小限の通信回数によってパケットＰＫＴを全ての無線装置１〜７へ送信できるように中継無線装置を選択することである。
【００９７】
ＭＰＲセレクタ集合は、自己をＭＰＲとして選択した無線装置の集合を表す。
【００９８】
ローカルリンク情報が確立される過程は、概ね、次のようになる。Ｈｅｌｌｏメッセージは、初期の段階では、各無線装置１〜７が自己の存在を知らせるために、自己のアドレスが入ったＨｅｌｌｏメッセージを隣接する無線装置へ送信する。これを、無線装置１〜７の全てが行ない、各無線装置１〜７は、自己の周りにどのようなアドレスを持った無線装置が存在するのかを把握する。このようにして、リンク集合および隣接無線装置集合が構築される。
【００９９】
そして、構築されたローカルリンク情報は、再び、Ｈｅｌｌｏメッセージによって定期的に送り続けられる。これを繰返すことによって、各リンクが双方向であるのか、隣接無線装置の先にどのような無線装置が存在するのかが徐々に明らかになって行く。各無線装置１〜７は、このように徐々に構築されたローカルリンク情報を蓄える。
【０１００】
更に、ＭＰＲに関する情報も、Ｈｅｌｌｏメッセージによって定期的に送信され、各無線装置１〜７へ告知される。各無線装置１〜７は、自己が送信するパケットＰＫＴの再送信を依頼する無線装置として、いくつかの無線装置をＭＰＲ集合として隣接無線装置の中から選択している。そして、このＭＰＲ集合に関する情報は、Ｈｅｌｌｏメッセージによって隣接する無線装置へ送信されるので、このＨｅｌｌｏメッセージを受信した無線装置は、自己をＭＰＲとして選択してきた無線装置の集合を「ＭＰＲセレクタ集合」として管理する。このようにすることにより、各無線装置１〜７は、どの無線装置から受信したパケットＰＫＴを再送信すればよいのかを即座に認識できる。
【０１０１】
Ｈｅｌｌｏメッセージの送受信により各無線装置１〜７において、ローカルリンク集合が構築されると、メッシュ型ネットワーク１００全体のトポロジーを知らせるためのＴＣメッセージが無線装置１〜７へ送信される。このＴＣメッセージは、ＭＰＲとして選択されている全ての無線装置によって定期的に送信される。そして、ＴＣメッセージは、各無線装置とＭＰＲセレクタ集合との間のリンクを含んでいるため、メッシュ型ネットワーク１００内の全ての無線装置１〜７は、全てのＭＰＲ集合および全てのＭＰＲセレクタ集合を知ることができ、全てのＭＰＲ集合および全てのＭＰＲセレクタ集合に基づいて、メッシュ型ネットワーク１００全体のトポロジーを知ることができる。
【０１０２】
そして、各無線装置１〜７は、Ｈｅｌｌｏメッセージとは別に、ＭＰＲを用いてＴＣメッセージを頻繁に交換する。これによって、各無線装置１〜７は、メッシュ型ネットワーク１００の全体のトポロジーを知ることができる。
【０１０３】
図７は、メッシュ型ネットワーク１００の具体例を示す図である。各無線装置１〜７は、隣接無線装置から受信したＨｅｌｌｏメッセージに含まれているチャネル情報に基づいて、次の方法によって各リンクのチャネルを検知する。
【０１０４】
例えば、無線装置２の通信手段２０１は、チャネルＣｈ１，Ｃｈ２がそれぞれインターフェースＩＦ１，ＩＦ２に割り当てられていれば、インターフェースＩＦ１のＭＡＣアドレスＭＡＣａｄｄ１−２にチャネルＣｈ１を対応付けたチャネル情報ＭＡＣａｄｄ１−２：Ｃｈ１と、インターフェースＩＦ２のＭＡＣアドレスＭＡＣａｄｄ２−２にチャネルＣｈ２を対応付けたチャネル情報ＭＡＣａｄｄ２−２：Ｃｈ２とをメッセージに格納したＨｅｌｌｏメッセージＨＭＧ１＝［ＭＡＣａｄｄ１−２：Ｃｈ１／ＭＡＣａｄｄ２−２：Ｃｈ２］を生成する。そして、無線装置２の通信手段２０１は、その生成したＨｅｌｌｏメッセージＨＭＧ１＝［ＭＡＣａｄｄ１−２：Ｃｈ１／ＭＡＣａｄｄ２−２：Ｃｈ２］をインターフェースＩＦ１，ＩＦ２を用いてブロードキャストする。なお、ＭＡＣアドレスＭＡＣａｄｄ１−２，ＭＡＣａｄｄ２−２は、無線装置２のＭＡＣアドレスであることが識別可能なアドレスである。
【０１０５】
そして、無線装置２のパケットを受信可能な範囲内に配置された無線装置１，３〜６は、自己の２つのインターフェースＩＦ１，ＩＦ２の少なくとも１つにチャネルＣｈ１，Ｃｈ２のいずれかが割り当てられていれば、無線装置２からブロードキャストされたＨｅｌｌｏメッセージＨＭＧ１＝［ＭＡＣａｄｄ１−２：Ｃｈ１／ＭＡＣａｄｄ２−２：Ｃｈ２］を受信することができる。
【０１０６】
例えば、無線装置１のインターフェースＩＦ１にチャネルＣｈ１が割り当てられていれば、無線装置１のインターフェースＩＦ１は、ＨｅｌｌｏメッセージＨＭＧ１＝［ＭＡＣａｄｄ１−２：Ｃｈ１／ＭＡＣａｄｄ２−２：Ｃｈ２］を受信し、その受信したＨｅｌｌｏメッセージＨＭＧ１＝［ＭＡＣａｄｄ１−２：Ｃｈ１／ＭＡＣａｄｄ２−２：Ｃｈ２］を通信手段２０１およびテーブル作成手段２４１へ出力する。そして、無線装置１のテーブル作成手段２４１は、インターフェースＩＦ１からＨｅｌｌｏメッセージＨＭＧ１＝［ＭＡＣａｄｄ１−２：Ｃｈ１／ＭＡＣａｄｄ２−２：Ｃｈ２］を受け、チャネルＣｈ１が割り当てられたインターフェースＩＦ１によってＨｅｌｌｏメッセージＨＭＧ１の受信に成功したことを検知する。
【０１０７】
また、無線装置１のテーブル作成手段２４１は、ＨｅｌｌｏメッセージＨＭＧ１の送信元アドレス（＝無線装置２のＩＰアドレスＩＰａｄｄ２）を参照して、ＨｅｌｌｏメッセージＨＭＧ１を無線装置２から受信したことを検知する。その結果、無線装置１のテーブル作成手段２４１は、チャネルＣｈ１によって無線装置１−無線装置２間にリンクが確立されたことを検知する。
【０１０８】
同様にして、無線装置３，４，５，６のテーブル作成手段２４１は、それぞれ、チャネルＣｈ２，Ｃｈ２，Ｃｈ２，Ｃｈ１によって無線装置２−無線装置３間、無線装置２−無線装置４間、無線装置２−無線装置５間、および無線装置２−無線装置６間にリンクが確立されたことを検知する。
【０１０９】
なお、チャネルＣｈ１，Ｃｈ２以外のチャネルが各無線装置１，３〜６の２つのインターフェースＩＦ１，ＩＦ２に割り当てられていた場合、各無線装置１，３〜６は、無線装置２からブロードキャストされたＨｅｌｌｏメッセージＨＭＧ１を受信できない。従って、この場合、無線装置１，３〜６は、無線装置２との間でリンクを確立しない。
【０１１０】
無線装置４の通信手段２０１は、チャネルＣｈ２が割り当てられたインターフェースＩＦ１によって無線装置２からのＨｅｌｌｏメッセージＨＭＧ１の受信に成功すると、チャネルＣｈ２，Ｃｈ３がそれぞれ無線装置４のインターフェースＩＦ１，ＩＦ２に割り当てられており、無線装置４のインターフェースＩＦ１が無線装置２のインターフェースＩＦ２との間でチャネルＣｈ２によるリンクを確立したことを示すチャネル情報ＭＡＣａｄｄ２−２⇔ＭＡＣａｄｄ１−４：Ｃｈ２／ＭＡＣａｄｄ２−４：Ｃｈ３をメッセージに含めたＨｅｌｌｏメッセージＨＭＧ２＝［ＭＡＣａｄｄ２−２⇔ＭＡＣａｄｄ１−４：Ｃｈ２／ＭＡＣａｄｄ２−４：Ｃｈ３］を生成する。そして、無線装置４の通信手段２０１は、その生成したＨｅｌｌｏメッセージＨＭＧ２＝［ＭＡＣａｄｄ２−２⇔ＭＡＣａｄｄ１−４：Ｃｈ２／ＭＡＣａｄｄ２−４：Ｃｈ３］をインターフェースＩＦ１，ＩＦ２を用いてブロードキャストする。
【０１１１】
そうすると、無線装置６は、チャネルＣｈ３が割り当てられたインターフェースＩＦ２によってＨｅｌｌｏメッセージＨＭＧ２＝［ＭＡＣａｄｄ２−２⇔ＭＡＣａｄｄ１−４：Ｃｈ２／ＭＡＣａｄｄ２−４：Ｃｈ３］の受信に成功し、無線装置６のテーブル作成手段２４１は、ＨｅｌｌｏメッセージＨＭＧ２に基づいて無線装置４−無線装置６間にチャネルＣｈ３によるリンクが確立されたことを検知するとともに、無線装置２−無線装置４間にチャネルＣｈ２によるリンクが確立されたことを検知する。
【０１１２】
同様にして、無線装置６は、無線装置５からもＨｅｌｌｏメッセージを受信し、無線装置５−無線装置６間にチャネルＣｈ３によるリンクが確立され、無線装置２−無線装置５間にチャネルＣｈ２によるリンクが確立されたことを検知する。
【０１１３】
また、無線装置６は、チャネルＣｈ１が割り当てられたインターフェースＩＦ１によってＨｅｌｌｏメッセージＨＭＧ１＝［ＭＡＣａｄｄ１−２：Ｃｈ１／ＭＡＣａｄｄ２−２：Ｃｈ２］の受信に成功し、無線装置６のテーブル作成手段２４１は、無線装置２−無線装置６間にチャネルＣｈ１によるリンクが確立されたことを検知する。
【０１１４】
そして、無線装置６の通信手段２０１は、無線装置２，４，５からのＨｅｌｌｏメッセージの受信に成功すると、チャネルＣｈ１，Ｃｈ３がそれぞれ無線装置６のインターフェースＩＦ１，ＩＦ２に割り当てられており、インターフェースＩＦ１が無線装置２のインターフェースＩＦ１との間でチャネルＣｈ１によるリンクを確立したこと、および無線装置６のインターフェースＩＦ２が無線装置４，５のインターフェースＩＦ２との間でチャネルＣｈ３によるリンクを確立したことを示すチャネル情報ＭＡＣａｄｄ１−２⇔ＭＡＣａｄｄ１−６：Ｃｈ１／ＭＡＣａｄｄ２−４，ＭＡＣａｄｄ２−５⇔ＭＡＣａｄｄ２−６：Ｃｈ３をメッセージに含めたＨｅｌｌｏメッセージＨＭＧ３＝［ＭＡＣａｄｄ１−２⇔ＭＡＣａｄｄ１−６：Ｃｈ１／ＭＡＣａｄｄ２−４，ＭＡＣａｄｄ２−５⇔ＭＡＣａｄｄ２−６：Ｃｈ３］を生成する。
【０１１５】
そして、無線装置６の通信手段２０１は、その生成したＨｅｌｌｏメッセージＨＭＧ３＝［ＭＡＣａｄｄ１−２⇔ＭＡＣａｄｄ１−６：Ｃｈ１／ＭＡＣａｄｄ２−４，ＭＡＣａｄｄ２−５⇔ＭＡＣａｄｄ２−６：Ｃｈ３］をインターフェースＩＦ１，ＩＦ２を用いてブロードキャストする。
【０１１６】
無線装置７は、チャネルＣｈ３が割り当てられたインターフェースＩＦ２によってＨｅｌｌｏメッセージＨＭＧ３＝［ＭＡＣａｄｄ１−２⇔ＭＡＣａｄｄ１−６：Ｃｈ１／ＭＡＣａｄｄ２−４，ＭＡＣａｄｄ２−５⇔ＭＡＣａｄｄ２−６：Ｃｈ３］の受信に成功し、無線装置７のテーブル作成手段２４１は、無線装置６−無線装置７間にチャネルＣｈ３によるリンクが確立されたことを検知するとともに、無線装置２−無線装置６間にチャネルＣｈ１によるリンクが確立されたことおよび無線装置４−無線装置６間および無線装置５−無線装置６間にチャネルＣｈ３によるリンクが確立されたことを検知する。
【０１１７】
同様にして、無線装置８のテーブル作成手段２４１は、無線装置６−無線装置８間にチャネルＣｈ１によるリンクが確立されたことを検知するとともに、無線装置４−無線装置６間および無線装置５−無線装置６間にチャネルＣｈ３によるリンクが確立されたことを検知する。
【０１１８】
このように、各無線装置１〜８は、自己に割り当てられたチャネルをＨｅｌｌｏメッセージに含めてブロードキャストするとともに、自己と隣接無線装置との間に確立されたリンクのチャネルをＨｅｌｌｏメッセージに含めてブロードキャストする。
【０１１９】
これによって、各無線装置１〜８のテーブル作成手段２４１は、自己から２ホップ以内の複数のリンクにおけるチャネルの分布を検知する。
【０１２０】
次に、各無線装置１〜８がチャネルの分布に基づいてリンクを評価する方法について説明する。なお、以下においては、無線装置２が無線装置２−無線装置６間のリンクを評価する場合を例にしてリンクを評価する方法について説明する。図８は、ネイバーリストの具体例を示す図である。無線装置２のテーブル作成手段２４１は、無線装置２に隣接する無線装置１，３〜６からＨｅｌｌｏメッセージを受信し、その受信したＨｅｌｌｏメッセージに基づいて、図８に示すネイバーリストＮＴＢＬ１を作成する。
【０１２１】
そして、無線装置２のテーブル作成手段２４１は、ネイバーリストＮＴＢＬ１に基づいて、無線装置２から２ホップ以内の複数のリンクにおけるチャネル分布として図７に示すチャネル分布を検知する。
【０１２２】
評価対象であるリンク（＝無線装置２−無線装置６）を介してパケットが送信されるフローとしては、無線装置１→無線装置２→無線装置６→無線装置７からなるフロー、無線装置１→無線装置２→無線装置６→無線装置８からなるフローおよび無線装置３→無線装置２→無線装置６→無線装置７からなるフロー等の各種のフローが存在する。
【０１２３】
そして、これらの各フローにおいて、チャネルによるフロー内の干渉とは、２つのリンク間におけるチャネル干渉である。例えば、無線装置１→無線装置２→無線装置６→無線装置７からなるフローにおけるチャネルによるフロー内の干渉とは、無線装置１−無線装置２間のリンク、無線装置２−無線装置６間のリンクおよび無線装置６−無線装置７間のリンクのうちの任意の２つのリンク間におけるチャネル干渉である。
【０１２４】
そして、２つのリンク間において、同じチャネルが使用されていれば、チャネル干渉が生じ、異なるチャネルが使用されていれば、チャネル干渉は生じない。
【０１２５】
従って、１つのフローを構成する複数のリンクにおいて、２つのリンク間でチャネル干渉が生じなければ、フロー内の干渉が無いことになり、２つのリンク間でチャネル干渉が生じれば、フロー内の干渉が存在することになる。
【０１２６】
そこで、図７に示すように、評価対象であるリンク（無線装置２−無線装置６）を通過するフローを考えた場合、フロー内の干渉の有無を示すチャネルの分布パターンは、４個の基本分布パターンに分類される。
【０１２７】
この場合、通常のメッシュネットワークにおける無線装置の配置を考慮すれば、評価対象であるリンクに対して干渉が生じるのは、隣接のリンクだけであるので、隣接のリンクのみを考慮することにした。
【０１２８】
図９は、フロー内の干渉の有無を示すチャネルの基本分布パターンの概念図である。なお、図９における白丸、白三角形、および白四角形は、チャネルを表す。無線装置Ｘ−無線装置Ａ−無線装置Ｂ−無線装置Ｙからなるフローを考えた場合、無線装置Ｘ−無線装置Ａ−無線装置Ｂ−無線装置Ｙからなるフローを構成する３個のリンクＬｉｎｋ１〜Ｌｉｎｋ３におけるチャネルの分布パターンは、図９の（ａ）〜（ｄ）に示す４個の基本分布パターンになる。
【０１２９】
図９の（ａ）の基本分布パターンは、連続して連結された３個のリンクＬｉｎｋ１〜Ｌｉｎｋ３の全てが同じチャネルとなる分布パターンであり、図９の（ｂ）の基本分布パターンは、３個のリンクＬｉｎｋ１〜Ｌｉｎｋ３のうち、一方端のリンクのチャネルが他の２つのリンクのチャネルと異なる分布パターンである。
【０１３０】
また、図９の（ｃ）の基本分布パターンは、３個のリンクＬｉｎｋ１〜Ｌｉｎｋ３のうち、両端のリンクのチャネルが同じであり、中央のリンクのチャネルが両端のリンクのチャネルと異なる分布パターンであり、図９の（ｄ）の基本分布パターンは、３個のリンクＬｉｎｋ１〜Ｌｉｎｋ３のチャネルが相互に異なる分布パターンである。
【０１３１】
フローが３個のリンクからなる場合、３個のリンクにおけるチャネルの分布パターンは、図９に示す４個の基本分布パターンに必ず分類される。そこで、図９の（ａ）〜（ｄ）に示す基本分布パターンをそれぞれＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４とする。
【０１３２】
３個のリンクにおけるチャネルの分布パターンが基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４であるときの無線装置Ｘ−無線装置Ｙ間のスループットを実測した結果を表１に示す。
【０１３３】
【表１】
0004517060.tif 000006
【０１３４】
なお、表１においては、スループットの最大値に対する割合も示されている。
【０１３５】
表１から解るように、無線装置Ｘ−無線装置Ｙ間のスループットは、３個のリンクのチャネルが相互に異なる基本分布パターンＤＰ＿ｓｔｄ４において最も高く、基本分布パターンＤＰ＿ｓｔｄ３、基本分布パターンＤＰ＿ｓｔｄ２、および基本分布パターンＤＰ＿ｓｔｄ１の順に低下する。
【０１３６】
メッシュ型ネットワーク１００におけるスループットを向上させるには、各無線装置１〜７がスループットが最大になる経路を選択してパケットを送信または中継する必要がある。
【０１３７】
そこで、無線装置２のテーブル作成手段２４１は、図７に示すチャネル分布が得られると、評価対象であるリンク（＝無線装置２−無線装置６）を通過する複数のフローの全てを検出し、その検出した複数のフローにおけるチャネルの分布パターンを基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４に分類する。
【０１３８】
そして、無線装置２のテーブル作成手段２４１は、各基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４に分類されるチャネルの分布パターンの個数Ｐ１〜Ｐ４を計数する。
【０１３９】
また、無線装置２のテーブル作成手段２４１は、表１におけるスループットの最大値に対する割合である０．６１，０．６５，０．７８，１．０をそれぞれＣｐ１，Ｃｐ２，Ｃｐ３，Ｃｐ４として保持している。
【０１４０】
そうすると、無線装置２のテーブル作成手段２４１は、評価対象のリンク（無線装置２−無線装置６）におけるチャネルによる干渉を考慮したときのスループットの最大値に対する割合ＣｐＥＸを次式によって演算する。
【０１４１】
【数５】
0004517060.tif 000007
【０１４２】
なお、式（５）におけるＰａｌｌは、評価対象であるリンク（＝無線装置２−無線装置６）を通過するフローの最大個数である。
【０１４３】
そして、無線装置２のテーブル作成手段２４１は、式（５）を用いて演算したスループットの最大値に対する割合ＣｐＥＸを次式に代入して評価対象のリンクのコストＣｏｓｔｎｅｗを演算する。
【０１４４】
【数６】
0004517060.tif 000008
【０１４５】
式（６）においては、Ｃｏｓｔは、例えば、評価対象となるリンクのホップ数（＝１）である。
【０１４６】
式（５）における（Ｐ１／Ｐａｌｌ），（Ｐ２／Ｐａｌｌ），（Ｐ３／Ｐａｌｌ），（Ｐ４／Ｐａｌｌ）は、それぞれ、評価対象のリンクを通過する複数のフローにおけるチャネルの分布パターンが基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４に分類される確率であり、Ｃｐ１〜Ｃｐ４は、それぞれ、チャネルの分布パターンが基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４であるときのスループットの実測された最大値に対する割合であるので、評価対象のリンクを用いて無線通信を行なったときのスループットの最大値に対する割合ＣｐＥＸを式（５）を用いて演算することは、各基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４におけるスループットの実測された最大値に対する割合Ｃｐ１〜Ｃｐ４をチャネルの分布パターンが各基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４に分類される確率（Ｐ１／Ｐａｌｌ），（Ｐ２／Ｐａｌｌ），（Ｐ３／Ｐａｌｌ），（Ｐ４／Ｐａｌｌ）によって重み付け平均してスループットの最大値に対する割合ＣｐＥＸを演算することに相当する。
【０１４７】
コストＣｏｓｔｎｅｗの具体的な求め方について説明する。無線装置２のテーブル作成手段２４１は、評価対象であるリンク（＝無線装置２−無線装置６）を通過するフローの最大個数として次の１４個のフローを検出する。
【０１４８】
（１）無線装置１−無線装置２−無線装置６−無線装置８からなるフロー
（２）無線装置１−無線装置２−無線装置６−無線装置４からなるフロー
（３）無線装置１−無線装置２−無線装置６−無線装置５からなるフロー
（４）無線装置１−無線装置２−無線装置６−無線装置７からなるフロー
（５）無線装置３−無線装置２−無線装置６−無線装置８からなるフロー
（６）無線装置４−無線装置２−無線装置６−無線装置８からなるフロー
（７）無線装置５−無線装置２−無線装置６−無線装置８からなるフロー
（８）無線装置３−無線装置２−無線装置６−無線装置４からなるフロー
（９）無線装置３−無線装置２−無線装置６−無線装置５からなるフロー
（１０）無線装置３−無線装置２−無線装置６−無線装置７からなるフロー
（１１）無線装置４−無線装置２−無線装置６−無線装置５からなるフロー
（１２）無線装置４−無線装置２−無線装置６−無線装置７からなるフロー
（１３）無線装置５−無線装置２−無線装置６−無線装置４からなるフロー
（１４）無線装置５−無線装置２−無線装置６−無線装置７からなるフロー
なお、無線装置２のテーブル作成手段２４１は、ループが形成される無線装置４−無線装置２−無線装置６−無線装置４からなるフローおよび無線装置５−無線装置２−無線装置６−無線装置５からなるフローを評価対象であるリンク（＝無線装置２−無線装置６）を通過するフローから除外する。
【０１４９】
そして、無線装置２のテーブル作成手段２４１は、評価対象であるリンク（＝無線装置２−無線装置６）を通過するフローを検出すると、上記の（１）のフローにおけるチャネルの分布パターンを基本分布パターンＤＰ＿ｓｔｄ１に分類し、上記の（２）〜（７）のフローにおけるチャネルの分布パターンを基本分布パターンＤＰ＿ｓｔｄ２に分類し、上記の（８）〜（１４）のフローにおけるチャネルの分布パターンを基本分布パターンＤＰ＿ｓｔｄ４に分類する。
【０１５０】
この場合、基本分布パターンＤＰ＿ｓｔｄ３に分類されるチャネルの分布パターンは、存在しない。
【０１５１】
その後、無線装置２のテーブル作成手段２４１は、基本分布パターンＤＰ＿ｓｔｄ１に分類されたチャネルの分布パターンの個数Ｐ１を１個と計数し、基本分布パターンＤＰ＿ｓｔｄ２に分類されたチャネルの分布パターンの個数Ｐ２を６個と計数し、基本分布パターンＤＰ＿ｓｔｄ３に分類されたチャネルの分布パターンの個数Ｐ３を０個と計数し、基本分布パターンＤＰ＿ｓｔｄ４に分類されたチャネルの分布パターンの個数Ｐ４を７個と計数する。また、無線装置２のテーブル作成手段２４１は、評価対象であるリンク（＝無線装置２−無線装置６）を通過する複数のフローの全個数Ｐａｌｌを１４個と計数する。
【０１５２】
そうすると、無線装置２のテーブル作成手段２４１は、Ｐ１＝１、Ｐ２＝６、Ｐ３＝０、Ｐ４＝７、Ｃｐ１＝０．６１、Ｃｐ２＝０．６５、Ｃｐ３＝０．７８、Ｃｐ４＝１．０、Ｐａｌｌ＝１４を式（５）に代入し、評価対象のリンク（無線装置２−無線装置６）におけるチャネルによる干渉を考慮したときのスループットの最大値に対する割合ＣｐＥＸを演算する。その結果、次式に示すように、ＣｐＥＸ＝０．８２が得られる。
【０１５３】
【数７】
0004517060.tif 000009
【０１５４】
そして、無線装置２のテーブル作成手段２４１は、その演算したＣｐＥＸ＝０．８２を式（６）に代入してコストＣｏｓｔｎｅｗを演算する（式（８）参照）。
【０１５５】
【数８】
0004517060.tif 000010
【０１５６】
無線装置２のテーブル作成手段２４１は、無線装置２−無線装置４からなるリンク、無線装置２−無線装置５からなるリンクおよび無線装置４−無線装置６からなるリンクについても、上述した方法によってコストＣｏｓｔｎｅｗを演算する。
【０１５７】
また、無線装置２のテーブル作成手段２４１は、無線装置１−無線装置２からなるリンクおよび無線装置３−無線装置２からなるリンクのコストＣｏｓｔｎｅｗを演算する場合、次の方法によってコストＣｏｓｔｎｅｗを演算する。
【０１５８】
図１０は、フロー内の干渉の有無を示すチャネルの他の基本分布パターンの概念図である。無線装置１−無線装置２からなるリンクおよび無線装置３−無線装置２からなるリンクのコストＣｏｓｔｎｅｗを演算する場合、評価対象となるリンクの一方側にのみリンクが存在するので、フロー内でチャネルによる干渉が生じるチャネルの基本分布パターンは、図１０の（ａ），（ｂ）に示す２つの基本分布パターンとなる。
【０１５９】
即ち、無線装置Ａ−無線装置Ｂ間のリンクを評価対象のリンクとすると、無線装置Ａ−無線装置Ｂ間のリンクにおけるチャネルが無線装置Ｂ−無線装置Ｙ間のリンクにおけるチャネルと同じになる基本分布パターン（図１０の（ａ）参照）と、無線装置Ａ−無線装置Ｂ間のリンクにおけるチャネルが無線装置Ｂ−無線装置Ｙ間のリンクにおけるチャネルと異なる基本分布パターン（図１０の（ｂ）参照）とが存在する。
【０１６０】
評価対象であるリンクを通過するフローにおけるチャネルの分布パターンが図１０の（ａ），（ｂ）に示す基本分布パターンになるときのスループットの実測値を表２に示す。
【０１６１】
【表２】
0004517060.tif 000011
【０１６２】
図１０の（ａ）に示す基本分布パターンをＤＰ＿ｓｔｄ５とし、図１０の（ｂ）に示す基本分布パターンをＤＰ＿ｓｔｄ６とすると、評価対象のリンクを通過するフローにおけるチャネルの分布パターンが基本分布パターンＤＰ＿ｓｔｄ６であるときのスループットの最大値に対する割合Ｃｐ６は、表２から１．０であり、評価対象のリンクを通過するフローにおけるチャネルの分布パターンが基本分布パターンＤＰ＿ｓｔｄ５であるときのスループットの最大値に対する割合Ｃｐ５は、表２から０．６８である。
【０１６３】
また、基本分布パターンＤＰ＿ｓｔｄ５に分類されるチャネルの分布パターンの個数をＰ５とし、基本分布パターンＤＰ＿ｓｔｄ６に分類されるチャネルの分布パターンの個数をＰ６とし、評価対象のリンクを通過する複数のフローの全数をＰａｌｌとすると、無線装置１のテーブル作成手段２４１は、評価対象のリンク（無線装置１−無線装置２）におけるチャネルによる干渉を考慮したときのスループットの最大値に対する割合ＣｐＥＸは、次式によって演算される。
【０１６４】
【数９】
0004517060.tif 000012
【０１６５】
無線装置１のテーブル作成手段２４１は、式（９）によってスループットの最大値に対する割合ＣｐＥＸを演算すると、その演算した割合ＣｐＥＸを式（６）に代入して評価対象のリンク（無線装置１−無線装置２）のコストＣｏｓｔｎｅｗを演算する。
【０１６６】
なお、式（９）における（Ｐ５／Ｐａｌｌ），（Ｐ６／Ｐａｌｌ）は、それぞれ、評価対象のリンクを通過する複数のフローにおけるチャネルの分布パターンが基本分布パターンＤＰ＿ｓｔｄ５，ＤＰ＿ｓｔｄ６に分類される確率であり、Ｃｐ５，Ｃｐ６は、それぞれ、チャネルの分布パターンが基本分布パターンＤＰ＿ｓｔｄ５，ＤＰ＿ｓｔｄ６であるときのスループットの実測された最大値に対する割合であるので、評価対象のリンクを用いて無線通信を行なったときのスループットの最大値に対する割合ＣｐＥＸを式（９）を用いて演算することは、各基本分布パターンＤＰ＿ｓｔｄ５，ＤＰ＿ｓｔｄ６におけるスループットの実測された最大値に対する割合Ｃｐ５，Ｃｐ６をチャネルの分布パターンが各基本分布パターンＤＰ＿ｓｔｄ５，ＤＰ＿ｓｔｄ６に分類される確率（Ｐ５／Ｐａｌｌ），（Ｐ６／Ｐａｌｌ）によって重み付け平均してスループットの最大値に対する割合ＣｐＥＸを演算することに相当する。
【０１６７】
無線装置１のテーブル作成手段２４１は、式（９）および式（６）を用いて、無線装置１−無線装置２からなるリンクのコストＣｏｓｔｎｅｗを演算する。より具体的には、無線装置１のテーブル作成手段２４１は、式（９）を用いて、ＣｐＥＸ＝０．６８×（１／４）＋１×（３／４）＝０．９２を演算し、その演算したＣｐＥＸ＝０．９２を式（６）に代入してコストＣｏｓｔｎｅｗ＝１／０．９１＝１．０９を演算する。
【０１６８】
同様にして、無線装置２のテーブル作成手段２４１は、式（９）および式（６）を用いて、無線装置２−無線装置１からなるリンクのコストＣｏｓｔｎｅｗ（＝１．０９）および無線装置２−無線装置３からなるリンクのコストＣｏｓｔｎｅｗ（＝１．０９）を演算し、無線装置３のテーブル作成手段２４１は、式（９）および式（６）を用いて、無線装置３−無線装置２からなるリンクのコストＣｏｓｔｎｅｗ（＝１．０９）を演算し、無線装置６のテーブル作成手段２４１は、式（９）および式（６）を用いて、無線装置６−無線装置７からなるリンクのコストＣｏｓｔｎｅｗ（＝１／０．８４＝１．１９）および無線装置６−無線装置８からなるリンクのコストＣｏｓｔｎｅｗ（＝１／０．８４＝１．１９）を演算し、無線装置７のテーブル作成手段２４１は、式（９）および式（６）を用いて、無線装置７−無線装置６からなるリンクのコストＣｏｓｔｎｅｗ（＝１／０．８４＝１．１９）を演算し、無線装置８のテーブル作成手段２４１は、式（９）および式（６）を用いて、無線装置８−無線装置６からなるリンクのコストＣｏｓｔｎｅｗ（＝１／０．８４＝１．１９）を演算する。
【０１６９】
このように、無線装置１〜３，６〜８のテーブル作成手段２４１は、式（９）および式（６）を用いて、一方側にのみリンクが存在する評価対象のリンクのコストＣｏｓｔｎｅｗを演算する。
【０１７０】
メッシュ型ネットワーク１００においては、ＭＰＲである無線装置は、自己が隣接無線装置との間で有する全てのリンクのコストＣｏｓｔｎｅｗを演算し、その演算したコストＣｏｓｔｎｅｗをＴＣメッセージに含めてフラッディングする。例えば、無線装置２がＭＰＲである場合、無線装置２のテーブル作成手段２４１は、式（５），（６）または式（９），（６）を用いて、上述した方法によって、無線装置１，３〜６との間のリンクのコストＣｏｓｔｎｅｗを演算し、その演算したコストコストＣｏｓｔｎｅｗをＴＣメッセージに含めてフラッディングする。
【０１７１】
より具体的には、ＭＰＲである無線装置２のテーブル作成手段２４１は、無線装置２と無線装置１，３〜６との間のリンクのコストＣｏｓｔｎｅｗ１〜Ｃｏｓｔｎｅｗ５を式（５），（６）または式（９），（６）を用いて演算し、その演算したコストＣｏｓｔｎｅｗ１〜Ｃｏｓｔｎｅｗ５を含むＴＣメッセージ＝［ＩＰａｄｄ１：Ｃｏｓｔｎｅｗ１／ＩＰａｄｄ３：Ｃｏｓｔｎｅｗ２／ＩＰａｄｄ４：Ｃｏｓｔｎｅｗ３／ＩＰａｄｄ５：Ｃｏｓｔｎｅｗ４／ＩＰａｄｄ６：Ｃｏｓｔｎｅｗ５］を作成する。そして、無線装置２のテーブル作成手段２４１は、通信手段２０１を介してＴＣメッセージ＝［ＩＰａｄｄ１：Ｃｏｓｔｎｅｗ１／ＩＰａｄｄ３：Ｃｏｓｔｎｅｗ２／ＩＰａｄｄ４：Ｃｏｓｔｎｅｗ３／ＩＰａｄｄ５：Ｃｏｓｔｎｅｗ４／ＩＰａｄｄ６：Ｃｏｓｔｎｅｗ５］をフラッディングする。
【０１７２】
これによって、他の無線装置１，３〜８は、無線装置２と無線装置１，３〜６との間のリンクのコストコストＣｏｓｔｎｅｗ１〜Ｃｏｓｔｎｅｗ５を収集できる。
【０１７３】
図１１は、図７に示すチャネルの分布パターンにおける各リンクのコストを示す図である。各無線装置１〜８は、ＭＰＲである無線装置から送信されたＴＣメッセージを受信することにより、図７に示すチャネルの分布パターンにおける各リンクのコストＣｏｓｔｎｅｗを収集する。各無線装置１〜８が収集したリンクのコストＣｏｓｔｎｅｗを示すと、図１１に示すようになる。
【０１７４】
図１２は、ルーティングテーブル２１の具体例を示す図である。無線装置１のテーブル作成手段２４１は、ＭＰＲである無線装置から受信したＴＣメッセージに基づいて、図１１に示す各リンクにおけるコストＣｏｓｔｎｅｗを収集し、その収集したコストＣｏｓｔｎｅｗを用いて図１２に示すルーティングテーブル２１Ａを作成する。
【０１７５】
例えば、無線装置１のテーブル作成手段２４１は、無線装置２を送信先とする場合、無線装置２のＩＰアドレスＩＰａｄｄ２を“送信先”および“次の無線装置”に格納し、無線装置１−無線装置２間のリンクのコストＣｏｓｔｎｅｗ＝１．０９をメトリックに格納し、ルーティングテーブル２１Ａの第１行目の経路情報を作成する。
【０１７６】
また、無線装置１のテーブル作成手段２４１は、無線装置３を送信先とする場合、無線装置３のＩＰアドレスＩＰａｄｄ３を“送信先”に格納し、無線装置２のＩＰアドレスＩＰａｄｄ２を“次の無線装置”に格納し、無線装置１−無線装置２−無線装置３からなるフローにおける２つのリンクのコストＣｏｓｔｎｅｗ＝１．０９，Ｃｏｓｔｎｅｗ＝１．０９の和（＝２．１８）を演算して “２．１８”をメトリックに格納し、ルーティングテーブル２１Ａの第２行目の経路情報を作成する。
【０１７７】
無線装置１のテーブル作成手段２４１は、以下、同様にして、ルーティングテーブル２１Ａの第３行目から第７行目の経路情報を作成してルーティングテーブル２１Ａを完成する。
【０１７８】
この場合、ルーティングテーブル２１Ａのメトリックは、送信先までのリンクにおけるコストＣｏｓｔｎｅｗの総和のうち、最小の総和からなり、ダイクストラ法によってコストＣｏｓｔｎｅｗの総和が最小である経路を求める。
【０１７９】
図１３は、ルーティングテーブル２１の他の具体例を示す図である。無線装置２のテーブル作成手段２４１は、図１１に示す各リンクにおけるコストＣｏｓｔｎｅｗに基づいて、各送信先までのフローにおけるリンクのコストＣｏｓｔｎｅｗの総和のうち、最小の総和を演算し、その演算した最小の総和をメトリックに格納して図１３に示すルーティングテーブル２１Ｂを作成する。
【０１８０】
無線装置１の通信手段２０１は、上位層から無線装置７宛てのＴＣＰパケットを受け、その受けたＴＣＰパケットをデータ部に格納してＩＰパケットを生成する。そして、無線装置１の通信手段２０１は、その生成したＩＰパケットを無線装置７へ送信するための経路をルーティングテーブル２１Ａを参照して決定する。即ち、無線装置１の通信手段２０１は、ルーティングテーブル２１Ａを参照して、“送信先”の欄に格納された無線装置７に対応して“次の無線装置”の欄に格納された無線装置２を検出し、ＩＰパケットを送信する経路を無線装置２を経由する経路であると決定する。そして、無線装置１の通信手段２０１は、インターフェースＩＦ１（＝チャネルＣｈ１）を介してＩＰパケットを無線装置２へ送信する。
【０１８１】
無線装置２のインターフェースＩＦ１（＝チャネルＣｈ１）は、無線装置１から送信されたパケットを受信し、その受信したパケットを通信手段２０１へ出力する。
【０１８２】
そして、無線装置２の通信手段２０１は、インターフェースＩＦ１から受けたパケットのヘッダを参照して、その受けたパケットの送信先が無線装置７であることを検知する。そうすると、無線装置２の通信手段２０１は、ルーティングテーブル２１Ｂを参照して、パケットを無線装置７へ送信するための経路が無線装置６を経由する経路であることを検知する。そして、無線装置２の通信手段２０１は、インターフェースＩＦ１（＝チャネルＣｈ１）を介してパケットを無線装置６へ送信する。
【０１８３】
その後、無線装置６は、無線装置２からパケットを受信し、その受信したパケットの送信先のみを参照して、無線装置２と同じ動作によってパケットを無線装置７へ中継する。
【０１８４】
無線装置１，２，６以外の無線装置３〜５，７，８も、無線装置１，２，６と同じように、スループットの最大値に対する割合Ｃｐｅｘの逆数の総和が最小になるように決定された経路を用いてパケットを送信するとともに、受信したパケットの受信先のみを参照してパケットを送信先へ中継する。
【０１８５】
このように、この発明においては、各無線装置１〜７は、スループットの最大値に対する割合Ｃｐｅｘの逆数の総和が最小になるように経路を決定し、その決定した経路を用いてＨｏｐ−ｂｙ−Ｈｏｐによってパケットを送信先へ送信する。つまり、各無線装置１〜７は、スループットの最大値に対する割合Ｃｐｅｘの総和が最大小になるように経路を決定し、その決定した経路を用いてＨｏｐ−ｂｙ−Ｈｏｐによってパケットを送信先へ送信する。
【０１８６】
図１４は、各リンクのコストの他の例を示す図である。なお、図１４における白丸、白三角形、白四角形および白五角形は、チャネルを表す。図１４に示す場合、メッシュ型ネットワーク１００は、碁盤目状に配置された無線装置１〜９からなる。そして、各無線装置１〜９は、自己を中心にして両側の隣接無線装置との間でリンクを確立しているので、チャネル干渉が生じるチャネルの基本分布パターンは、図９に示す基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４からなる。
【０１８７】
そこで、チャネルの分布パターンを基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４に分類して各リンクにおけるコストＣｏｓｔｎｅｗを演算した結果、図１４に示すようになる。
【０１８８】
図１５および図１６は、ルーティングテーブル２１の更に他の具体例を示す図である。無線装置１のテーブル作成手段２４１は、図１４に示す各リンクにおけるコストＣｏｓｔｎｅｗをＴＣメッセージに基づいて収集し、図１５に示すルーティングテーブル２１Ｃを作成する。
【０１８９】
無線装置１のテーブル作成手段２４１は、無線装置２を送信先とする場合、無線装置２のＩＰアドレスＩＰａｄｄ２を“送信先”および“次の無線装置”に格納し、コストＣｏｓｔｎｅｗ＝１．２０をメトリックに格納し、ルーティングテーブル２１Ｃの第１行目の経路情報を作成する。
【０１９０】
また、無線装置１のテーブル作成手段２４１は、無線装置５を送信先とする場合、無線装置１−無線装置４−無線装置５からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ１と、無線装置１−無線装置２−無線装置５からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ２とを演算する。より具体的には、無線装置１のテーブル作成手段２４１は、ＳＭ１＝１．２０＋１．１４＝２．３４およびＳＭ２＝１．２０＋１．１４＝２．３４を演算する。そして、無線装置１のテーブル作成手段２４１は、無線装置１−無線装置４−無線装置５からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ１）と、無線装置１−無線装置２−無線装置５からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ２）とが同じであることを検知する。
【０１９１】
そうすると、無線装置１のテーブル作成手段２４１は、無線装置５のＩＰアドレスＩＰａｄｄ５を“送信先”に格納し、無線装置２，４のＩＰアドレスＩＰａｄｄ２，ＩＰａｄｄ４を“次の無線装置”に格納し、 “２．３４”をメトリックに格納し、ルーティングテーブル２１Ｃの第４行目の経路情報を作成する。
【０１９２】
更に、無線装置１のテーブル作成手段２４１は、無線装置６を送信先とする場合、無線装置１−無線装置２−無線装置３−無線装置６からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ３と、無線装置１−無線装置２−無線装置５−無線装置６からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ４と、無線装置１−無線装置４−無線装置５−無線装置６からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ５とを演算する。
【０１９３】
より具体的には、無線装置１のテーブル作成手段２４１は、ＳＭ３＝１．２０＋１．２０＋１．２０＝３．６０、ＳＭ４＝１．２０＋１．１４＋１．１４＝３．４８およびＳＭ５＝１．２０＋１．１４＋１．１４＝３．４８を演算する。そして、無線装置１のテーブル作成手段２４１は、無線装置１−無線装置２−無線装置５−無線装置６からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ４）および無線装置１−無線装置４−無線装置５−無線装置６からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ５）が同じであり、無線装置１−無線装置２−無線装置３−無線装置６からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ３）よりも小さいことを検知する。
【０１９４】
そうすると、無線装置１のテーブル作成手段２４１は、メトリックが最小となる無線装置２または無線装置４を経由する経路を選択し、無線装置６のＩＰアドレスＩＰａｄｄ６を“送信先”に格納し、無線装置２，４のＩＰアドレスＩＰａｄｄ２，ＩＰａｄｄ４を“次の無線装置”に格納し、 “３．４８”をメトリックに格納し、ルーティングテーブル２１Ｃの第５行目の経路情報を作成する。
【０１９５】
更に、無線装置１のテーブル作成手段２４１は、無線装置９を送信先とする場合、無線装置１−無線装置２−無線装置３−無線装置６−無線装置９からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ６と、無線装置１−無線装置２−無線装置５−無線装置６−無線装置９からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ７と、無線装置１−無線装置２−無線装置５−無線装置８−無線装置９からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ８と、無線装置１−無線装置４−無線装置５−無線装置６−無線装置９からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ９と、無線装置１−無線装置４−無線装置５−無線装置８−無線装置９からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ１０と、無線装置１−無線装置４−無線装置７−無線装置８−無線装置９からなる経路におけるコストＣｏｓｔｎｅｗの総和ＳＭ１１とを演算する。
【０１９６】
より具体的には、無線装置１のテーブル作成手段２４１は、ＳＭ６＝１．２０＋１．２０＋１．２０＋１．２０＝４．８０、ＳＭ７＝１．２０＋１．１４＋１．１４＋１．２０＝４．６８、ＳＭ８＝１．２０＋１．１４＋１．１４＋１．２０＝４．６８、ＳＭ９＝１．２０＋１．１４＋１．１４＋１．２０＝４．６８、ＳＭ１０＝１．２０＋１．１４＋１．１４＋１．２０＝４．６８およびＳＭ１１＝１．２０＋１．２０＋１．２０＋１．２０＝４．８０を演算する。そして、無線装置１のテーブル作成手段２４１は、無線装置１−無線装置２−無線装置５−無線装置６−無線装置９からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ７）、無線装置１−無線装置２−無線装置５−無線装置８−無線装置９からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ８）、無線装置１−無線装置４−無線装置５−無線装置６−無線装置９からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ９）、および無線装置１−無線装置４−無線装置５−無線装置８−無線装置９からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ１０）が同じであり、無線装置１−無線装置２−無線装置３−無線装置６−無線装置９からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ６）および無線装置１−無線装置４−無線装置７−無線装置８−無線装置９からなる経路のメトリック（＝コストＣｏｓｔｎｅｗの総和ＳＭ１１）よりも小さいことを検知する。
【０１９７】
そうすると、無線装置１のテーブル作成手段２４１は、メトリックが最小となる無線装置２，５または無線装置４，５を経由する経路を選択し、無線装置９のＩＰアドレスＩＰａｄｄ９を“送信先”に格納し、無線装置２，４のＩＰアドレスＩＰａｄｄ２，ＩＰａｄｄ４を“次の無線装置”に格納し、 “４．６８”をメトリックに格納し、ルーティングテーブル２１Ｃの第８行目の経路情報を作成する。
【０１９８】
無線装置１のテーブル作成手段２４１は、上述した方法によって、ルーティングテーブル２１Ｃの第２行目、第３行目、第６行目および第７行目の経路情報も作成し、ルーティングテーブル２１Ｃを完成する。
【０１９９】
無線装置２のテーブル作成手段２４１は、図１４に示す各リンクにおけるコストＣｏｓｔｎｅｗに基づいて、各送信先までのフローにおけるリンクのコストＣｏｓｔｎｅｗの総和のうち、最小の総和を演算し、その演算した最小の総和をメトリックに格納して図１６に示すルーティングテーブル２１Ｄを作成する。
【０２００】
無線装置１の通信手段２０１は、上位層から無線装置９宛てのＴＣＰパケットを受け、その受けたＴＣＰパケットをデータ部に格納してＩＰパケットを生成する。そして、無線装置１の通信手段２０１は、その生成したＩＰパケットを無線装置９へ送信するための経路をルーティングテーブル２１Ｃを参照して決定する。即ち、無線装置１の通信手段２０１は、ルーティングテーブル２１Ｃを参照して、“送信先”の欄に格納された無線装置９に対応して“次の無線装置”の欄に格納された無線装置２を検出し、ＩＰパケットを送信する経路を無線装置２を経由する経路であると決定する。そして、無線装置１の通信手段２０１は、インターフェースＩＦ１を介してＩＰパケットを無線装置２へ送信する。
【０２０１】
無線装置２のインターフェースＩＦ１は、無線装置１から送信されたパケットを受信し、その受信したパケットを通信手段２０１へ出力する。
【０２０２】
そして、無線装置２の通信手段２０１は、インターフェースＩＦ１から受けたパケットのヘッダを参照して、その受けたパケットの送信先が無線装置９であることを検知する。そうすると、無線装置２の通信手段２０１は、ルーティングテーブル２１Ｄを参照して、パケットを無線装置９へ送信するための経路が無線装置５を経由する経路であることを検知する。そして、無線装置２の通信手段２０１は、インターフェースＩＦ２を介してパケットを無線装置５へ送信する。
【０２０３】
その後、無線装置５は、無線装置２からパケットを受信し、その受信したパケットの送信先のみを参照して、無線装置２と同じ動作によってパケットを無線装置６へ中継する。また、無線装置６は、無線装置５からパケットを受信し、その受信したパケットの送信先のみを参照して、無線装置５と同じ動作によってパケットを無線装置９へ中継する。
【０２０４】
無線装置１，２，５，６以外の無線装置３，４，７〜９も、無線装置１，２，５，６と同じように、スループットの最大値に対する割合Ｃｐｅｘの逆数の総和が最小になるように決定された経路を用いてパケットを送信するとともに、受信したパケットの受信先のみを参照してパケットを送信先へ中継する。
【０２０５】
このように、この発明においては、各無線装置１〜９は、スループットの最大値に対する割合Ｃｐｅｘの逆数の総和が最小になるように経路を決定し、その決定した経路を用いてＨｏｐ−ｂｙ−Ｈｏｐによってパケットを送信先へ送信する。
【０２０６】
図１７は、この発明によるメッシュ型ネットワーク１００における通信方法を説明するためのフローチャートである。
【０２０７】
一連の動作が開始されると、各無線装置１〜７は、Ｈｅｌｌｏメッセージを隣接無線装置から受信し、上述した方法によって自己から２ホップ内のリンクにおけるチャネルの分布パターンを検出する（ステップＳ１）。
【０２０８】
そして、各無線装置１〜７は、評価対象のリンクを決定し（ステップＳ２）、ループとなる経路を排除して評価対象のリンクを通過する全てのフローである複数のフローを検出するとともに、その複数のフローの個数Ｐａｌｌを検出する（ステップＳ３）。
【０２０９】
その後、各無線装置１〜７は、その検出した複数のフローにおけるチャネルの分布パターンをチャネルによる干渉の有無を示す基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４（またはＤＰ＿ｓｔｄ５，ＤＰ＿ｓｔｄ６）に分類し（ステップＳ４）、各基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４（またはＤＰ＿ｓｔｄ５，ＤＰ＿ｓｔｄ６）に分類されたチャネルの分布パターンの個数Ｐ１〜Ｐ４（またはＰ５，Ｐ６）を計数する（ステップＳ５）。
【０２１０】
そうすると、各無線装置１〜７は、検出した複数のフローの個数Ｐａｌｌと、計数したチャネルの分布パターンの個数Ｐ１〜Ｐ４（またはＰ５，Ｐ６）と、チャネルの各基本分布パターンＤＰ＿ｓｔｄ１〜ＤＰ＿ｓｔｄ４（またはＤＰ＿ｓｔｄ５，ＤＰ＿ｓｔｄ６）におけるスループットの最大値に対する割合Ｃｐ１〜Ｃｐ４（またはＣｐ５，Ｃｐ６）とに基づいて、評価対象のリンクにおけるスループットの最大値に対する割合ＣｐＥＸを演算する（ステップＳ６）。
【０２１１】
そして、各無線装置１〜７は、全てのリンクに対してスループットの最大値に対する割合ＣｐＥＸの演算が終了したか否かを判定する（ステップＳ７）。ステップＳ７において、全てのリンクに対してスループットの最大値に対する割合ＣｐＥＸの演算が終了していないと判定されたとき、一連の動作は、ステップＳ２へ戻り、ステップＳ７において、全てのリンクに対してスループットの最大値に対する割合ＣｐＥＸの演算が終了したと判定されるまで、上述したステップＳ２〜ステップＳ７が繰り返し実行される。
【０２１２】
そして、ステップＳ７において、全てのリンクに対してスループットの最大値に対する割合ＣｐＥＸの演算が終了したと判定されると、各無線装置１〜７は、ステップＳ６において演算された割合ＣｐＥＸを用いて各リンクにおけるコストＣｏｓｔｎｅｗを上述した方法によって演算する（ステップＳ８）。その後、ＭＰＲである無線装置は、その演算したコストＣｏｓｔｎｅｗをＴＣメッセージに含めてネットワーク全体にフラッディングする（ステップＳ９）。
【０２１３】
そして、各無線装置１〜７は、ＴＣメッセージを受信してフラッディングされたコストＣｏｓｔｎｅｗを収集し、ネットワーク全体のトポロジーを検出する（ステップＳ１０）。
【０２１４】
そうすると、各無線装置１〜７は、各送信先に対して、送信先までのリンクのコストＣｏｓｔｎｅｗの総和のうち、最小の総和を検出する（ステップＳ１１）。
【０２１５】
その後、各無線装置１〜７は、その検出した最小の総和を各送信先に対応するメトリックに格納してルーティングテーブル２１を作成する（ステップＳ１２）。そして、各無線装置１〜７は、その作成したルーティングテーブル２１を参照して経路を決定し、その決定した経路に従ってパケットを送信または中継する（ステップＳ１３）。これによって、一連の動作が終了する。
【０２１６】
上述したように、この発明においては、各無線装置１〜７は、ループとなる経路を排除して評価対象のリンクを通過する全てのフローを検出し、その検出した全てのフローにおけるチャネルの分布パターンをチャネルによる干渉の有無を示す基本分布パターンに分類して評価対象のリンクを用いて無線通信を行なった場合のスループットの最大値に対する割合ＣｐＥＸを演算し、その演算した割合ＣｐＥＸを各経路の指標を示すメトリックに反映させて各経路を選択する（ステップＳ３〜ステップＳ１３参照）。
【０２１７】
つまり、各無線装置１〜７は、評価対象であるリンクを用いて無線通信を行なった場合に期待されるスループットの最大値に対する割合を求め、その求めた割合が相対的に大きいリンクを含む経路を選択する。
【０２１８】
従って、この発明によれば、上述した割合ＣｐＥＸおよびコストＣｏｓｔｎｅｗを演算して経路を選択するので、等張性を満たし、実装が容易なルーティングプロトコルに従って計算量の増大を抑制して経路を選択できる。
【０２１９】
なお、上記においては、各無線装置１〜７は、式（６）に従ってコストＣｏｓｔｎｅｗを演算すると説明したが、この発明においては、これに限らず、各無線装置１〜７は、ユーザアプリケーション１４の種類に応じて、コストＣｏｓｔｎｅｗを演算するようにしてもよい。
【０２２０】
即ち、各無線装置１〜７は、ＦＴＰ（Ｆｉｌｅ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ）のような高いデータレートを有するアプリケーションに対しては、次式によってコストＣｏｓｔｎｅｗを演算する。
【０２２１】
【数１０】
0004517060.tif 000013
【０２２２】
なお、式（１０）におけるＡｉｒＴｉｍｅＣｏｓｔは、パケットが無線通信空間を伝搬している時間であり、パケットサイズ、送信レートおよびパケットエラー率を用いて演算される。
【０２２３】
各無線装置１〜７は、ユーザアプリケーション１４が相対的に高いデータレートを有するアプリケーションである場合、スループットの最大値に対する割合ＣｐＥＸに反比例するようにコストＣｏｓｔｎｅｗを演算する。
【０２２４】
また、各無線装置１〜７は、ＶｏＩＰ（Ｖｏｉｃｅ  ｏｖｅｒ  Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）のような低いデータレートを有するアプリケーションに対しては、次式によってコストＣｏｓｔｎｅｗを演算する。
【０２２５】
【数１１】
0004517060.tif 000014
【０２２６】
この場合、各無線装置１〜７は、上述したスループットの最大値に対する割合ＣｐＥＸを用いずにＣｏｓｔｎｅｗを演算する。
【０２２７】
更に、各無線装置１〜７は、Ｖｉｄｅｏを送受信するアプリケーションに対しては、次式によってＣｏｓｔｎｅｗを演算する。
【０２２８】
【数１２】
0004517060.tif 000015
【０２２９】
式（１２）におけるαは、０＜α＜１を満たす実数である。そして、αは、干渉の影響をＦＴＰの場合に対してどの程度含めるかによって決定され、干渉の影響をＦＴＰの半分程度含める場合、α＝０．５に設定される。
【０２３１】
なお、上記においては、各無線装置１〜９は、相互に異なるチャネルが割り当てられた２つのインターフェースを備えると説明したが、この発明においては、これに限らず、各無線装置１〜９は、相互に異なるチャネルが割り当てられた３個以上のインターフェースを備えていてもよく、一般的には、相互に異なるチャネルが割り当てられた複数のインターフェースを備えていればよい。
【０２３２】
また、上記においては、各無線装置１〜９は、プロアクティブ型、かつ、Ｈｏｐ−ｂｙ−Ｈｏｐ型のルーティングプロトコルを用いてルーティングテーブル２１を作成すると説明したが、この発明においては、これに限らず、各無線装置１〜９は、プロアクティブ型、かつ、Ｈｏｐ−ｂｙ−Ｈｏｐ型のルーティングプロトコルであれば、どのようなプロトコルを用いてルーティングテーブル２１を作成してもよい。
【０２３３】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【０２３４】
この発明は、等張性を満たし、実装が容易なルーティングプロトコルに従って経路選択を行なう無線装置に適用される。また、この発明は、等張性を満たし、実装が容易なルーティングプロトコルに従って経路選択を行なう無線装置を備えたメッシュ型ネットワークに適用される。
【図面の簡単な説明】
【０２３５】
【図１】この発明の実施の形態によるメッシュ型ネットワークの概略図である。
【図２】図１に示す無線装置の構成を示す概略ブロック図である。
【図３】ＯＬＳＲプロトコルにおけるパケットの構成図である。
【図４】図２に示すルーティングテーブルの構成図である。
【図５】ネイバーリストの構成を示す概略図である。
【図６】図２に示す無線インターフェースモジュール、ＩＰモジュールおよびルーティングデーモンの機能のうち、本発明に係る機能を示す機能ブロック図である。
【図７】メッシュ型ネットワークの具体例を示す図である。
【図８】ネイバーリストの具体例を示す図である。
【図９】フロー内の干渉の有無を示すチャネルの基本分布パターンの概念図である。
【図１０】フロー内の干渉の有無を示すチャネルの他の基本分布パターンの概念図である。
【図１１】図７に示すチャネルの分布パターンにおける各リンクのコストを示す図である。
【図１２】ルーティングテーブルの具体例を示す図である。
【図１３】ルーティングテーブルの他の具体例を示す図である。
【図１４】各リンクのコストの他の例を示す図である。
【図１５】ルーティングテーブルの更に他の具体例を示す図である。
【図１６】ルーティングテーブルの更に他の具体例を示す図である。
【図１７】この発明によるメッシュ型ネットワークにおける通信方法を説明するためのフローチャートである。
【符号の説明】
【０２３６】
１〜９  無線装置、１０，１１  アンテナ、１２  入力部、１３  出力部、１４  ユーザアプリケーション、１５  通信制御部、１６  無線インターフェースモジュール、１７  ＭＡＣモジュール、１８  バッファ、１９  ＬＬＣモジュール、２０，２０Ａ  ＩＰモジュール、２１  ルーティングテーブル、２２  ＴＣＰモジュール、２３  ＵＤＰモジュール、２４  ルーティングデーモン、１００  メッシュ型ネットワーク、２０１  通信手段、２４１  テーブル作成手段。
【図１】
0004517060.tif 000016
【図２】
0004517060.tif 000017
【図３】
0004517060.tif 000018
【図４】
0004517060.tif 000019
【図５】
0004517060.tif 000020
【図６】
0004517060.tif 000021
【図７】
0004517060.tif 000022
【図８】
0004517060.tif 000023
【図９】
0004517060.tif 000024
【図１０】
0004517060.tif 000025
【図１１】
0004517060.tif 000026
【図１２】
0004517060.tif 000027
【図１３】
0004517060.tif 000028
【図１４】
0004517060.tif 000029
【図１５】
0004517060.tif 000030
【図１６】
0004517060.tif 000031
【図１７】
0004517060.tif 000032