(57)【要約】【課題】高優先度フローのトラフィックに対して干渉の無い通信を実現しエンドツーエンドの平均遅延時間を低下させスループットを向上できる。【解決手段】各無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって各無線局毎に格納するＲＮＬテーブルと、各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを各無線局毎に格納するＧＬＳテーブルとを保存する。発信無線局から宛先無線局までのパスの各リンクにおいて、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値との線形和であるリンクウェイトを計算し、その線形和の合計である全リンクウェイトを計算しその計算値が最小であるパスを選択してより高い優先度の無線信号をルーティングする。【選択図】図１２
2005260478.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線ネットワークのルーティング方法において、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局の記憶手段に保存するステップと、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信するステップと、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新するステップと、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするステップとを含むことを特徴とする無線ネットワークのルーティング方法。
【請求項２】
上記ルーティングするステップにおいて、上記処理対象の通信フローの無線信号のホップ計数値に代えて、当該ホップ計数値に所定のウェイト係数を乗算した乗算値を用いることを特徴とする請求項１記載の無線ネットワークのルーティング方法。
【請求項３】
複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線ネットワークのルーティング方法において、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局の記憶手段に保存するステップと、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信するステップと、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新するステップと、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、上記各パスのうちで最短のパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするステップとを含むことを特徴とする無線ネットワークのルーティング方法。
【請求項４】
複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線ネットワークのルーティング方法において、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局の記憶手段に保存するステップと、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信するステップと、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新するステップと、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に所定の第１のウェイト係数γ１を乗算した乗算値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に、上記第１のウェイト係数γ１よりも小さい第２のウェイト係数γ２を乗算した乗算値との線形和である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするステップとを含むことを特徴とする無線ネットワークのルーティング方法。
【請求項５】
複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線通信システムにおいて、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局において保存する記憶手段と、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信する送信手段と、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新する更新手段と、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするルーティング手段とを備えたことを特徴とする無線通信システム。
【請求項６】
上記ルーティング手段は、上記処理対象の通信フローの無線信号のホップ計数値に代えて、当該ホップ計数値に所定のウェイト係数を乗算した乗算値を用いることを特徴とする請求項５記載の無線通信システム。
【請求項７】
複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線通信システムにおいて、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局において保存する記憶手段と、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信する送信手段と、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新する更新手段と、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、上記各パスのうちで最短のパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするルーティング手段とを備えたことを特徴とする無線通信システム。
【請求項８】
複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線通信システムにおいて、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局において保存する記憶手段と、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信する送信手段と、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新する更新手段と、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に所定の第１のウェイト係数γ１を乗算した乗算値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に、上記第１のウェイト係数γ１よりも小さい第２のウェイト係数γ２を乗算した乗算値との線形和である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするルーティング手段とを備えたことを特徴とする無線通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の無線局を備えた、例えば無線ＬＡＮなどの無線ネットワークにおいてパケット通信を行う、例えばアドホック無線ネットワークなどの無線ネットワークのルーティング方法及び無線通信システムに関する。
【背景技術】
【０００２】
一時的に特定の地域内に集まった不特定多数の人々の間の通信を無線回線を用いてサポートするアドホック無線ネットワークでは、例えばインターネットのルータ装置のようなインフラストラクチャが存在しないために、ネットワーク中のユーザが協調してパケットを中継し、ルーティングを行う必要がある。
【０００３】
モバイルアドホックネットワーク（Mobile Ad Hoc Network：以下、ＭＡＮＥＴという。）のマルチメディアアプリケーション及び潜在的商業利用の人気の高まりは、明らかに、ＭＡＮＥＴにおけるサービス品質（Quality of Service：以下、ＱｏＳという。）のサポートが不可避のタスクであることを示している。特に、時間検出を行うマルチメディアデータの配信を保証するＱｏＳネットワークの開発が急速に推進されている。元来マルチメディアトラフィックは、通信の間、何らかの種類の優先度ベースのリソース予約を通じて従来のデータトラフィックを凌ぐより優先させて、マルチメディアデータの時宜を得た、かつ確実な配信を保証しなければならない。そこで、ＭＡＮＥＴにおいては、ＱｏＳ問題に関して多くの解決方法が提案されている（例えば、非特許文献１乃至７参照。）。
【０００４】
【特許文献１】特開２００１−０２４４３１号公報。
【特許文献２】特開２００１−２４４９８３号公報。
【非特許文献１】Kui Wu et al., "QoS Support in Mobile Ad hoc Networks", Crossing Boundaries  An Interdisciplinary Journal, Vol 1, No 1, Fall 2001.
【非特許文献２】Satyabrata Chakrabarti et al., "QoS issues in Ad Hoc Wireless Networks", IEEE Communications Magazine, Vol. 39, No. 2, pp.142-148, February 2001.
【非特許文献３】Zeinalipour-Yazti Demetrios., "A Glance at Quality of Service in mobile Ad Hoc Networks", http://www.cs.ucr.edu/~csyiazti/cs260.html. Final Research Report for cs260, Seminar on Mobile Ad Hoc Networks, Fall 2001.
【非特許文献４】S. Chen et al., "Distributed Quality-of-Service Routing in Ad hoc Networks", IEEE Journal on selected Areas in Communications, Vol. 17, No. 8, pp.1488 -1505, August 1999.
【非特許文献５】H. Xiao et al., "A Flexible Quality of Service Model for Mobile Ad-Hoc Networks", In the Proceedings of IEEE VTC 2000-spring, Tokyo, Japan, May 2000.
【非特許文献６】Prasant Mohapatra et al., "QoS in Mobile Ad Hoc Networks", IEEE Wireless Communications, Vol. 10, No. 3, June 2003.
【非特許文献７】Xavier Pallot et al., "Implementing Message Priority Policies over an 802.11 Based Mobile Ad Hoc Network", Published in the proceedings of MILCOM 2001, Washington, U.S.A., October 2001.
【非特許文献８】Kui Wu et al., "On-Demand Multipath Routing for Mobile Ad Hoc Networks", EPMCC 2001, Vienna, Austria, February 20-22, 2001
【非特許文献９】M. R. Pearlman et al., "On the Impact of Alternate Path Routing for Load Balancing in Mobile Ad Hoc Networks", MobiHOC 2000, pp. 150, pp. 3-10, 2000.
【非特許文献１０】Somprakash Bandyopadhyay et al., "Multipath Routing in Ad Hoc Networks with Directional Antenna", Proceeding of the IFIP TC6/WG6.8 Conference on Personal Wireless Communications (PWC 2002), Singapore, October 2002.
【非特許文献１１】Seung-Seok Kang et al., "Provisioning Service Differentiation in Ad Hoc Networks by the modification of Backoff Algorithm", International Conference on Computer Communication and Network (ICCCN) 2001, Scottsdale, Arizona, U.S.A., October 2001.
【非特許文献１２】Romit Roy Choudhury et al., "Media Access Control for Ad Hoc Networks: Using directional antennas for medium access control in ad hoc networks", Proceedings of the eighth annual international conference on Mobile computing and networking, September 2002
【非特許文献１３】R. Ramanathan, "On the Performance of Ad Hoc Networks with Beamforming Antennas", ACM MobiHoc, October 2001.
【非特許文献１４】Tetsuro Ueda et al., "Rotational Sector-based, Receiver-Oriented mechanism for Location Tracking and medium Access Control in Ad Hoc Networks using Directional Antenna", Proceedings of the IFIP conference on Personal Wireless Communications PWC 2003, Venice, ITALY, September 23-25, 2003.
【非特許文献１５】Siuli Roy et al., "A Network-Aware MAC and Routing Protocol for Effective Load Balancing in Ad Hoc Wireless Networks with Directional Antenna", ACM MobiHoc,2003, Maryland, U.S.A., June 1-3, 2003.
【非特許文献１６】Romit Roy Choudhury et al., "A Distributed Mechanism for Topology Discovery in Ad hoc Wireless Networks using Mobile Agents", Proceeding of the First Annual Workshop On Mobile Ad Hoc Networking & Computing (MOBIHOC 2000), Boston, Massachusetts, U.S.A., August 11, 2000.
【非特許文献１７】Romit Roy Choudhury et al., "An Agent-based Connection Management Protocol for Ad Hoc Wireless Networks", Journal of Network and System Management, December 2002.
【非特許文献１８】J.A.Bondy et al. "Graph Theory with Applications", Elsevier North-Holland, 1976.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＭＡＮＥＴにおける従来のＱｏＳルーティングプロトコルは、無線環境の主要な局面、すなわち相互干渉を考慮していない。互いの近傍内に存在するノード無線局間の干渉は、ルート結合を引き起こす（例えば、非特許文献８乃至１０参照。）。これは、ゾーン非連結性ルートの使用によって回避することができる（例えば、非特許文献１０参照。）。ここで、１つのパス上のデータ通信が他のパス沿いのデータ通信に干渉しなければ、２つのルートはゾーン非連結性であるとされる。
【０００６】
本願発明の目的は、高い優先度の通信ゾーンを予約することにより、高優先度及び低優先度のトラフィックが使用するルート間の結合効果を低減させる優先度ベースのルーティング方法を考案することにある。高優先度のデータ通信に使用されるネットワーク部分は、一時的に高優先度ゾーンとして予約され、これは、低優先度のデータにより、予約された高優先度ゾーンに対するゾーン非連結を最大化された異なるルート、かつ最終的に高優先度トラフィックのコンテンションのない送信を可能にする異なるルートの選択を介して回避される。
【０００７】
ＭＡＮＥＴにおけるＱｏＳに関連する問題については、既に何人かの研究者達が調査し、論じている。ＭＡＮＥＴにおけるＱｏＳのサポートには、ＱｏＳモデル、ＱｏＳリソース予約信号通信方法（シグナリング）、ＱｏＳルーティング及び媒体アクセス制御（ＭＡＣ）が含まれる（例えば、非特許文献１及び２参照。）。現在、例えばＩｎｔＳｅｒｖ（Integrated Service）／ＲＳＶＰ（Resource reSerVation Protocol）及びＤｉｆｆｓｅｒｖ（Differentiated Service）等の有線ネットワークに利用可能なＱｏＳモデルの基本概念は、各移動ホスト無線局に多大なオーバーヘッドを生成することからＭＡＮＥＴには適さない。さらに、ＩｎｔＳｅｒｖの場合、各ホスト無線局で維持されるフローベースの状態情報の量はフロー数の増加に比例して増大し、これにより、スケーラビリティの問題が発生する。ＱｏＳインターネットにおけるスケーラビリティの問題は、ＤｉｆｆＳｅｒｖによって解決することができる。ＩｎｔＳｅｒｖとは異なり、ＤｉｆｆＳｅｒｖにおける内部ルータは、フロー毎の状態情報ではなく集合としてのフローベースの状態情報を保持する（例えば、非特許文献１乃至３参照。）。従って、ＤｉｆｆＳｅｒｖはＭＡＮＥＴの潜在的ＱｏＳモデルである可能性がある。
【０００８】
インターネットに使用されるＱｏＳ信号方式（シグナリング）プロトコルであるＲＳＶＰは、リソース予約の制御メッセージがデータパケットと競合することからＭＡＮＥＴには適さない。ホスト無線局の移動性が予測されないため、ＭＡＮＥＴでは、ＱｏＳをイネーブルされたネットワークで一旦要求が受け入れられると、ある程度の性能基準が保証されなければならない、という従来の意味合いはもはや通用しない。ＲＳＶＰの類のリソース予約は、移動性がリンクを破壊する場合があり、又はリンク品質を変える場合があって、既存のパスがＱｏＳ要件を提供しなくなる可能性があることから、アドホック移動環境では困難である。従って、有線ネットワークのＱｏＳモデル、信号方式（シグナリング）及びルーティングプロトコルをそのままＭＡＮＥＴにマップすることはできない（例えば、非特許文献４参照。）。ベストエフォート型サービスより高い信頼性を要求するアプリケーションのために保証されたサービスを達成するためには、ＩｎｔＳｅｒｖとＤｉｆｆＳｅｒｖとを適切に混合させることが不可欠である。
【０００９】
例えば、非特許文献５には、ＩｎｔＳｅｒｖとＤｉｆｆＳｅｒｖモデル双方の利点を取り入れたＭＡＮＥＴのためのフレキシブルＱｏＳモデル（ＦＱＭＭ）が提案されている。また、非特許文献６では、アドホックネットワークにおけるＱｏＳ提供に関する幾つかの問題点について包括的研究が行われている。これらの研究において著者達は、ＭＡＮＥＴのための異なる層でのＱｏＳ提供及び層間的なＱｏＳフレームワークに関する幾つかの提案についても検討している。さらに、非特許文献７では、クサビル・パロット（Xavier Pallot）らが、ネットワーク負荷が極めて少ない場合を除いて、移動無線チャネルの限定的な帯域幅があらゆるクラスのトラフィックに同一のＱｏＳを提供することを阻んでいると提言している。従って、リソースの配分に関しては、一方のクラスに他方のクラスを凌ぐ優先性を割り当てて各クラスに異なるＱｏＳを提供するための何らかの手段を実施しなければならない。このように、当該文献においてはＱｏＳと優先性との間の連結は一般的なことであり、これらの２語はほぼ同義である（非特許文献７参照。）。従って、優先度ベースのサービスによるＱｏＳ提供は、ＭＡＮＥＴにおける探究の価値のある興味深い考案である。
【００１０】
ところで、ＭＡＮＥＴにおいては、ＭＡＣ層におけるトラフィックの優先度によってコンテンションウィンドウ（ＣＷ）のサイズを変更しかつバックオフアルゴリズムを適宜修正することにより、ＱｏＳをサポートする幾つかの試みが実行されてきた（例えば、非特許文献１１参照。）。しかしながら、これは、高優先度のパケットが常にデータ通信用媒体へのコンテンション（衝突）のないアクセスを取得することを保証しない。ネットワーク内に高優先度のデータが存在する場合でも、低優先度のトラフィックが、高優先度のトラフィックのものより小さいサイズのコンテンションウィンドウを選定して低優先度のデータを送信する機会を得る可能性はある。さらに、これらの方法においては、媒体を求めて競合する２つの高優先度フローは、必ずしも媒体の公正なアクセスを保証されないと思われる。
【００１１】
優先度ベースの従来のＱｏＳルーティングプロトコルは、ルーティングの間の無線媒体における干渉の効果を考慮していない。互いの近傍内に存在するノード無線局間の干渉は、ルート結合を引き起こす。ルート結合は、データ通信の間に２つのルートが互いに干渉し合うほど物理的に近接して位置づけられる場合に発生する無線媒体の現象である（例えば、非特許文献８及び９参照。）。干渉し合うこれらのルート上のノード無線局は、共用する無線媒体へアクセスするために絶えず競合する。最終的に、パケットのエンドツーエンドの平均遅延時間は増大し、これにより、スループットが劇的に低下する。従って、ＭＡＮＥＴにおいて優先度ベースのＱｏＳをサポートする際の２つの主要な懸念事項であるエンドツーエンドの遅延時間とスループットとは、ルート結合に大きく依存する。ルート結合は、ゾーン非連結性ルートの使用によって回避することができる（例えば、非特許文献１０参照。）。１つのパス上のデータ通信が他のパス沿いのデータ通信に干渉しなければ、２つのルートはゾーン非連結性であるとされる。
【００１２】
図１５が示すように、Ｓ１−Ｎ１−Ｎ２−Ｄ１及びＳ２−Ｎ３−Ｎ４−Ｄ２をそれぞれ、発信無線局Ｓ１及びＳ２がそれぞれ宛先無線局Ｄ１及びＤ２と通信するために使用する２つのノード非連結性パスであるとする。これらはノード非連結性であることから、両者がコンテンションのないパス同士であることは明らかである。図１５の点線により示すように、発信無線局Ｓ１及びＳ２が互いの無指向性の送信レンジ内にあれば、これらが同時に通信を行うことはできない。
【００１３】
同様に、図１の宛先無線局Ｎ１とＮ３、及び宛先無線局Ｎ２とＮ４も同時に通信することはできない。従って、ノード非連結ルートを使用してＳ１−Ｄ１間及びＳ２−Ｄ２間の通信が行われるとしても、ノード非連結ルート間の固有のルート結合によってこれらが同時に通信することは不可能となり、無線環境におけるルーティング性能は大幅に低下する。従って、優先度ベースのＱｏＳを提供するためには、高優先度トラフィックの場合にルート結合の効果を最小限に抑えなければならないことは明らかである。高優先度のトラフィックは、非干渉性パス、すなわち、他の低優先度トラフィックに起因する干渉のないパスを選択して、媒体へのコンテンションのないアクセスを取得しなければならない。反対に、低優先度のパケットは、高優先度のトラフィックとはゾーン非連結性であるルートを選定することができる。このように、低優先度のトラフィックは、ネットワーク内に存在するアクティブな高優先度の通信とのルート結合の影響を最小限に抑えるために、高優先度の通信から可能な限り遠ざけられなければならない。
【００１４】
本発明の目的は以上の問題点を解決し、ゾーン非連結性の優位点を利用しかつこれを、より高い優先度フローのトラフィックを含むゾーンへの干渉を最小限に抑える低優先度フローの多様ルートの計算に使用することにより、エンドツーエンドの平均遅延時間を低下させるとともに、スループットを向上できるルーティング方法及び無線通信システムを提供することにある。
【課題を解決するための手段】
【００１５】
第１の発明に係る無線ネットワークのルーティング方法は、複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線ネットワークのルーティング方法において、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局の記憶手段に保存するステップと、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信するステップと、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新するステップと、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするステップとを含むことを特徴とする。
【００１６】
上記無線ネットワークのための制御方法において、上記ルーティングするステップにおいて、上記処理対象の通信フローの無線信号のホップ計数値に代えて、当該ホップ計数値に所定のウェイト係数を乗算した乗算値を用いることを特徴とする。
【００１７】
第２の発明に係る無線ネットワークのルーティング方法は、複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線ネットワークのルーティング方法において、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局の記憶手段に保存するステップと、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信するステップと、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新するステップと、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、上記各パスのうちで最短のパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするステップとを含むことを特徴とする。
【００１８】
第３の発明に係る無線ネットワークのルーティング方法は、複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線ネットワークのルーティング方法において、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局の記憶手段に保存するステップと、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信するステップと、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新するステップと、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に所定の第１のウェイト係数γ１を乗算した乗算値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に、上記第１のウェイト係数γ１よりも小さい第２のウェイト係数γ２を乗算した乗算値との線形和である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするステップとを含むことを特徴とする。
【００１９】
第４の発明に係る無線通信システムは、複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線通信システムにおいて、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局において保存する記憶手段と、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信する送信手段と、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新する更新手段と、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするルーティング手段とを備えたことを特徴とする。
【００２０】
上記無線通信システムにおいて、上記ルーティング手段は、上記処理対象の通信フローの無線信号のホップ計数値に代えて、当該ホップ計数値に所定のウェイト係数を乗算した乗算値を用いることを特徴とする。
【００２１】
第５の発明に係る無線通信システムは、複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線通信システムにおいて、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局において保存する記憶手段と、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信する送信手段と、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新する更新手段と、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、上記各パスのうちで最短のパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするルーティング手段とを備えたことを特徴とする。
【００２２】
第６の発明に係る無線通信システムは、複数の無線局を備え、各無線局間で優先度を有する無線信号を用いて無線通信を行う無線通信システムにおいて、
上記複数の無線局が通信可能な状態であるか否かを示すデータを通信フローの通信ＩＤ毎であって上記各無線局毎に格納する第１のテーブルと、上記各無線局から無線通信可能な隣接無線局と当該各無線局から当該隣接無線局への方位角のデータを上記各無線局毎に格納する第２のテーブルとを上記各無線局において保存する記憶手段と、
上記第１のテーブルを含む第１の無線信号を所定の第１の送信周期で周期的に送信するとともに、上記第２のテーブルを含む第２の無線信号を所定の第２の送信周期で周期的に送信する送信手段と、
上記送信された第１の無線信号を受信したとき、自局の記憶手段に保存された第１のテーブルのデータを更新するとともに、上記送信された第２の無線信号を受信したとき、自局の記憶手段に保存された第２のテーブルのデータを更新する更新手段と、
発信無線局から宛先無線局までのパスの各リンクにおいて、上記第１と第２のテーブルを参照して、より高い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に所定の第１のウェイト係数γ１を乗算した乗算値との線形和である第１のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングする一方、より低い優先度を有する無線信号をルーチィングするとき、処理対象の通信フローを除く、現在通信中の無線局によって取り扱われている通信フローの全数と、処理対象の通信フローの無線信号のホップ計数値に、上記第１のウェイト係数γ１よりも小さい第２のウェイト係数γ２を乗算した乗算値との線形和である第２のリンクウェイトをそれぞれ計算し、計算された線形和の合計である全リンクウェイトを計算し、計算された全リンクウェイトが最小であるパスを選択して無線信号をルーティングするルーティング手段とを備えたことを特徴とする。
【発明の効果】
【００２３】
従って、本発明に係る無線ネットワークのルーティング方法及び無線通信システムによれば、従来技術に比較して、より高い優先度フローのトラフィックに対して干渉の無い通信を実現でき、より高い優先度フローのエンドツーエンドの平均遅延時間を低下させるとともに、スループットを向上できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明に係る実施形態について図面を参照して説明する。なお、同様の構成要素については同一の符号を付している。
【００２５】
本発明の目的は、上述のように、ゾーン非連結性の優位点を利用しかつこれを、高優先度トラフィックを含むゾーンへの干渉を最小限に抑える低優先度フローの多様ルートの計算に使用することにより、エンドツーエンドの平均遅延時間を低下させるとともに、スループットを向上できるルーティング方法及び無線通信システムを提供することにあるが、無指向性アンテナの送信ゾーンは全方向をカバーすることから、無指向性アンテナを使用してゾーン非連結性パスを部分的にでも取得することは困難である。指向性アンテナは、無指向性アンテナよりも縮小された送信ゾーンを有する。従って、指向性アンテナを使用すれば、干渉し合う２つのルートを容易に非結合にすることができる。
【００２６】
指向性アンテナを使用すれば無線干渉は大幅に減少し、これにより無線媒体の利用度を向上させ、ネットワークスループットを向上させることは証明されている（非特許文献１０，１２及び１３参照。）。先の研究で、本発明者らは指向性の電子制御導波器アレーアンテナ装置を使用するＭＡＣ及びルーティングプロトコルを開発した（例えば、非特許文献１４及び１５参照。）。本発明に係る実施形態では、ゾーン予約を使用する優先度ベースのルーティングにおいて指向性アンテナを使用することを特徴としている。
【００２７】
上述したように、ゾーン非連結パスを取得する確率は無指向性アンテナより指向性アンテナの方が相対的に高く、これによりアドホック無線ネットワークにおける無線媒体の全体的利用度は向上する。図１５は、指向性アンテナを使用すれば、２つのノード非連結ルートであるＳ１−Ｎ１−Ｎ２−Ｄ１及びＳ２−Ｎ３−Ｎ４−Ｄ２を非結合にできることを示している。この場合、これは、無指向性アンテナの使用では不可能である。
【００２８】
本発明に係る実施形態では、高優先度のフローが可能な限り最良のスループットを達成するように、ルーティングの間にネットワークにおけるトラフィックフローを異なる優先度のクラスに分類し、異なるクラスに属するフローに異なる処理を施すことによってＭＡＮＥＴにおける優先度ベースのＱｏＳをサポートする方法を提案している。提案のプロトコルは、高優先度のトラフィックに最短パスを選択し、その高優先度の通信パスに沿ったゾーンを予約する。低優先度フローには、高優先度フローへの干渉を最小限に抑える多様なゾーン非連結ルートを選択し、こうして高優先度及び低優先度ルート間の結合の効果を低減させる。この方法は、高優先度トラフィックによるアダプティブなゾーン予約を介する無線媒体の選択された部分のある種の「捕捉」を使用している。
【００２９】
まず、本実施形態で用いるアドホック無線ネットワークの無線通信システムについて以下に説明する。図１は、本発明に係る実施形態であるアドホック無線ネットワークの構成を示す複数の無線局１−１乃至１−９（総称して、符号１を付す。）の平面配置図であり、図２は、図１の各無線局１の構成を示すブロック図である。
【００３０】
この実施形態の無線通信システムでは、図１に示すように、複数の無線局１が平面的に散在して存在し、各無線局１はそれぞれ、可変ビームアンテナ１０１の利得や送信電力、受信感度などのパラメータで決定される所定のサービスエリアを有し、このサービスエリア内でパケット通信を行うことができ、サービスエリア外の無線局１とパケット通信を行うときは、サービスエリア内の無線局１を中継局として用いてパケットデータを中継することにより、所望の宛先無線局１にパケットデータを伝送する。すなわち、各無線局１は、パケットのルーティングを行うルータ機能を備え、発信無線局、中継局、又は宛先無線局として動作する。
【００３１】
この実施形態の無線通信システムは、例えば無線ＬＡＮなどのアドホック無線ネットワークのパケット通信システムに適用するものであって、無指向性放射パターンであるオムニパターンと、自局を中心とした水平面内の所定の方位角毎にセクタ形状のメインビームを選択的に変更可能なセクタービームパターンと、上記方位角毎にヌル点を形成可能な排他的セクターパターンとを選択的に切り換え可能な可変ビームアンテナ１０１を備え、下記の（ａ）乃至（ｄ）のテーブルをデータベースメモリ１５４に格納し、これらのテーブルに基づいて、可変ビームアンテナ１０１の放射パターンを制御しながらパケット信号のルーティングを行うことを特徴としている。
【００３２】
（ａ）自局を中心とするサービスエリア内の隣接ノード無線局（自局から無線通信可能なノード無線局を隣接ノード無線局という。）１から無線信号を受信するときに測定可能な隣接ノード無線局１に対する方位角及び信号強度レベルを格納する方位角及び信号強度レベルテーブル（Angle and Signal strength Table）（以下、ＡＳテーブルという。）。
（ｂ）自局からの無線信号を隣接ノード無線局が受信したときのＳＩＮＲの測定値を含む隣接ノード無線局からの無線信号に基づいて予め取得された、自局を中心とした水平面内の所定の方位角毎のサービスエリア内の無線局１から見たＳＩＮＲに基づいて、各隣接ノード無線局毎に最大のＳＩＮＲを選択して各隣接ノード無線局との親和度とし、当該親和度と、それに対応する方位角及びそのデータの更新時刻とを含む隣接リンク状態テーブル（Neighbor Link-State Table）（以下、ＮＬＳテーブルという。）。
（ｃ）当該アドホック無線ネットワークにあるノード無線局のうち、当該アドホック無線ネットワークに参加しており通信予約済みの状態（以下、アクティブ状態という。）にある各通信ＩＤのノード無線局のリストを含む予約済み無線局リストテーブル（Reserved Node List Table）（以下、ＲＮＬテーブルという。）。
（ｄ）各無線局間でＮＬＳテーブルのトポロジー情報（アドホック無線ネットワーク内のすべての無線局間のリンク状態を示すパス情報をいい、以下同様である。）を交換することにより、当該アドホック無線ネットワーク内のすべての無線局１に関するＮＬＳテーブルのトポロジー情報を収集し、このトポロジー情報（各無線局１間のリンク状態を含む）と、これにおける各無線局毎の当該トポロジー情報の更新回数（バージョンを示す）と、その時点で任意の通信プロセスに関わる無線局１を示す通信状態フラグ値とを含むグローバルリンク状態テーブル（Global Link State Table）（以下、ＧＬＳテーブルという。）。
【００３３】
次いで、図２を参照して、各無線局１の装置構成について説明する。図２において、無線局１は、可変ビームアンテナ１０１と、その指向性を制御するための指向制御部１０３と、サーキュレータ１０２と、データパケット送信部１４０及びデータパケット受信部１３０を有するデータパケット送受信部１０４と、トラヒックモニタ部１０５と、回線制御部１０６と、上位レイヤ処理装置１０７とを備える。
【００３４】
送受信すべきデータを処理する上位レイヤ処理装置１０７によって発生されたパケット形式の通信用送信信号データは、送信バッファメモリ１４２を介して変調器１４３に入力され、変調器１４３は、所定の無線周波数の搬送波信号を、拡散符号発生器１６０でＣＤＭＡ方式で発生された所定の通信チャネル用拡散符号を用いて、入力された通信用送信信号データに従ってスペクトル拡散変調して、変調後の送信信号を高周波送信機１４４に出力する。高周波送信機１４４は入力された送信信号に対して増幅などの処理を実行した後、サーキュレータ１０２を介して可変ビームアンテナ１０１から他の無線局１に向けて送信する。一方、可変ビームアンテナ１０１で受信されたパケット形式の通信チャネル用受信信号は、サーキュレータ１０２を介して高周波受信機１３１に入力され、高周波受信機１３１は入力された受信信号に対して低雑音増幅などの処理を実行した後、復調器１３２に出力する。復調器１３２は、入力される受信信号を、拡散符号発生器１６０でＣＤＭＡ方式で発生された通信チャネル用拡散符号を用いて、スペクトル逆拡散により復調して、復調後の受信信号データを受信バッファメモリ１３３を介して上位レイヤ処理装置１０７に出力するとともに、トラヒックモニタのためにトラヒックモニタ部１０５に出力する。
【００３５】
本実施形態においては、指向性アンテナである可変ビームアンテナ１０１は、複数のアンテナ素子とその指向性を制御する制御部１０３に接続され、
（ａ）無指向性放射パターンであるオムニパターンと、
（ｂ）例えば図３に示すように、自局を中心とした水平面内の所定の方位角毎にセクタ形状のメインビームを選択的に変更可能なセクタービームパターンと、
（ｃ）上記方位角毎にヌル点を形成可能な排他的セクターパターンと
を電気的な制御により選択的に切り換え可能なアンテナである。なお、可変ビームアンテナ１０１については、例えば、公知のフェーズドアレーアンテナ装置であってもよいし、もしくは、特許文献１及び２に開示された電子制御導波器アレーアンテナ装置（Electronically Steerable Passive Array Radiator Array Antenna Apparatus）である可変ビームアンテナであってもよい。
【００３６】
トラヒックモニタ部１０５は、検索エンジン１５２と、更新エンジン１５３と、データベースメモリ１５４と、クロック回路１５５とを備え、後述のルーティング及び通信処理を実行するとともに、無線局１が他の無線局１とのパケット通信において使用すべき通信チャネルを決定して、決定した通信チャネルに対応する拡散符号の指定データを回線制御部１０６を介して拡散符号発生器１６０に送ることにより、拡散符号発生器１６０が当該指定データに対応する拡散符号を発生するように制御するとともに、決定した通信チャネルに対応するタイムスロットの指定データを回線制御部１０６を介して送信タイミング制御部１４１に送ることにより、送信タイミング制御部１４１が送信バッファメモリ１４２による通信チャネル用送信信号データの書き込み及び読み出しを制御することにより通信チャネル用送信信号が対応するタイムスロットで送信されるように制御する。なお、クロック回路１５５は、現在日時を計時してその情報を、必要に応じて管理制御部１５１に出力する。
【００３７】
トラヒックモニタ部１０５の検索エンジン１５２は、管理制御部１５１の制御によりデータベースメモリ１５４内のデータを検索して検索したデータを管理制御部１５１に返信する。また、更新エンジン１５３は、管理制御部１５１の制御によりデータベースメモリ１５４内のデータを更新する。さらに、データベースメモリ１５４に、ＡＳテーブル、ＮＬＳテーブル、ＲＮＬテーブル、及びルーティングのためのテーブルであるＧＬＳテーブルを記憶している。
【００３８】
本実施形態においては、アンテナ放射パターンを単一の通信相手先方向の利得が最大となるように指向性を変化させるセクタービームパターンの実効的な送信ビーム幅を３０°としており、可変ビームアンテナ１０１は、方位角を３０°毎に選択的に変化可能に設定できる。ビーム幅及び方位角の変化方位角は、６０°又は他の方位角であってもよい。また、本実施形態のパケット通信システムで用いるパケットデータは、図４に示す形式のフォーマットを有する。すなわち、パケットデータは、宛先無線局のＩＤと、パケット種別（トーン、ＧＬＳテーブル、ＲＮＬテーブル、ＲＴＳ（Request To Send）、ＣＴＳ（Clear To Send）、ＤＡＴＡなど）と、自局のＩＤと、通信フロー毎に割り当てられる通信ＩＤと、優先度レベル（高優先度又は低優先度であるか。本実施形態においては、当該２値で優先度レベルを表しているが、本発明はこれに限らず、多値で優先度レベルを表してもよい。）、データ（上位レイヤでのデータなどを含む）とを含む。さらに、データベースメモリ１５４に格納されたＡＳテーブルは、図５に示すように、自局のサービスエリア内の隣接ノード無線局毎に、方位角と、信号強度レベルの情報を格納し、後述する図１１のパケット送受信制御処理により作成更新される。また、データベースメモリ１５４に格納されたＧＬＳテーブルは、図８に示すように、当該アドホック無線ネットワーク内のノード無線局毎に、隣接ノード無線局とその方位角データと、そのデータの更新回数（バージョンを示す）を格納し、後述するパケット送受信制御処理により作成更新される。
【００３９】
次いで、本実施形態で用いるＭＡＣ通信プロトコルについて以下に説明する。本実施形態に係る無線通信ネットワークにおいて、互いに無線通信を行う１組の無線局１は二次元的な閉鎖空間内を動き回り、共通の無線通信チャンネルを共有するものと仮定する。各無線局１は、上述の４個の放射パターンを有する、例えば電子制御導波器アレーアンテナ装置である可変ビームアンテナ１０１を備える。各無線局１は一度に送信又は受信のいずれかを実行可能であるが、１つの無線局１で複数の送受信を行うことはできない。
【００４０】
ＩＥＥＥ８０２．１１のＭＡＣプロトコル基準では、ＲＴＳ／ＣＴＳ／ＤＡＴＡ／ＡＣＫアクセス制御方式を用いて、高信頼性のデータ通信が保証されているが、本実施形態の方法では、このアクセス制御方式をベースとして、図９及び図１０を参照して詳細後述するように、トーン信号＋パケット信号を用いた制御信号を用いて、ＲＮＬテーブル、ＧＬＳテーブル、その他のデータを含むパケット信号を送受信する。従って、データ通信は周期的な、ＲＮＬテーブルの生成及び更新フェーズ、ＧＬＳテーブルの生成及び更新フェーズの合間に実行される。また、各フレームにはトレーニングシーケンスが追加されて送受信アンテナによるそのビーム及びヌルの制御及び適応制御モードへの移行が可能にされる。
【００４１】
次いで、図１の無線局１を用いた、アドホック無線ネットワークのための無線通信システムの詳細について以下に説明する。
【００４２】
まず、アンテナモデルについて以下に説明する。本発明者らは、各ユーザ端末（ノード無線局）が電子制御導波器アレーアンテナ装置として知られる小型で低コストの適応型アンテナ（例えば、特許文献１及び２参照。）を使用する無線アドホック地域ネットワークのテストベッドの実施に向けて努力している。適応型アレーアンテナは通常、デジタル式ビーム形成アンテナである。これに対して、電子制御導波器アレーアンテナ装置はＲＦビーム形成に依存し、これが回路の複雑さを大幅に低減させる。電子制御導波器アレーアンテナ装置は、発信無線局に接続された１つの励振素子と、これを円形に取り囲む幾つかの非励振素子（典型的には、４本乃至６本）とで構成される。各非励振素子は、可変リアクタンス素子を介して接地される。各可変リアクタンス素子のリアクタンス値の調整により、非励振素子は、アンテナアレーの放射パターンを異なる形状に形成する。電子制御導波器アレーアンテナ装置の特徴は、ビーム方向の制御、同一の周波数の多重ビームの形成、可動（３６０度掃引）ビーム及びヌルステアリングの制御にある。本実施形態では、電子制御導波器アレーアンテナ装置を擬似スイッチビームアンテナとして使用する。電子制御導波器アレーアンテナ装置を一般化されたスイッチビームアンテナとして使用することの優位点は、少数のアンテナ素子で継続追跡が可能であり、かつ可変数のビームパターンを保有できることにある。電子制御導波器アレーアンテナ装置は低コスト、低電力の小型アンテナになるため、ユーザ端末の電力消費の低減が促進され、スイッチビームアンテナのあらゆる優位点をもたらすことが可能になると思われる。
【００４３】
次いで、本実施形態に係る無線通信システムにおける幾つかの重要な定義について以下に説明する。
【００４４】
＜定義１＞ノード無線局ｎが送信レンジ（送信距離）Ｒで方位角α及びビーム幅β（ビーム幅の角度）の送信ビームを形成するとき、ノード無線局ｎの送信ゾーンＴＺｎ（α，β，Ｒ）を方位角αにおけるノード無線局ｎの有効範囲（サービスエリア）と定義する。これは、ノード無線局ｍ∈Ｎが送信ゾーンＴＺｎ（α，β，Ｒ）内にあり、かつノード無線局ｍが受信モードにあれば、ノード無線局ｎがノード無線局ｎに対する送信方位角α、ビーム幅β及び送信レンジＲでメッセージを送信する毎に、これは必ずノード無線局ｍによって受信されることを意味する。ノード無線局ｍが送信ゾーンＴＺｎ（α，β，Ｒ）の外へ移動すると、ノード無線局ｎとノード無線局ｍとの接続性又は連結性は失われる。本実施形態では、送信ビーム幅βと送信レンジＲとが一定であるため、以下、送信ゾーンＴＺｎ（α，β，Ｒ）を送信ゾーンＴＺｎ（α）という。
【００４５】
＜定義２＞「高優先度ゾーン」は、高優先度フローの通信を扱う任意のノード無線局ｎによって形成される送信ゾーンＴＺｎ（α）である。
【００４６】
＜定義３＞「ｎ（Ｇｎ）∈Ｎの近傍ノード無線局」を、ノード無線局ｎの無指向性送信レンジＲ内のノード無線局の集合と定義する。
【００４７】
＜定義４＞集合Ｇｎの部分集合Ｇｎα∈Ｇｎを「ノード無線局ｎの指向性近傍のノード無線局」と定義する。ここで、部分集合Ｇｎα内のノード無線局はその送信ゾーンｎ（α）内に含まれる。
【００４８】
＜定義５＞「通信ＩＤｃ」は、通信が進行中である発信無線局と宛先無線局のペアを特定する固有の通信フローＩＤである。
【００４９】
＜定義６＞「予約済みノード無線局リスト［ＲＮＬ（ｔ）］」は、各ノード無線局が任意の高優先度フローの通信プロセスにおける送信局もしくは受信局、又は上述の任意の送信局もしくは受信局であるノード無線局の指向性近傍ノード無線局のいずれかである、時刻ｔにおけるノード無線局の集合である。当該予約済みノード無線局リスト内の各ノード無線局は、各ノード無線局のために予約される通信ＩＤの集合Ｃに関連している。
【００５０】
＜定義７＞「送信ゾーンＴＺｎ（α）におけるノード無線局ｎの予約済みの指向性近傍ノード無線局［ＲＧｎα（ｔ）］」は、その時刻に高優先度フローの通信のために予約されている送信ゾーンＴＺｎ（α）内のノード無線局の集合であり、すなわち、上記予約済みノード無線局リストＲＮＬ（ｔ）に属する。従って、次式で表される。
【００５１】
［数１］
ＲＧｎα（ｔ）＝Ｇｎα（ｔ）∩ＲＮＬ（ｔ）      （１）
【００５２】
＜定義８＞「通信ＩＤｃのパスＰにおけるノード無線局ｎｉの相関係数［ηｎｉｃ（Ｐ）］」、ここで、ノード無線局ｎｊはパスＰにおけるノード無線局ｎｉの次のホップのノード無線局であり、方位角α（ｎｉ→ｎｊ）はノード無線局ｎｊと通信するためにノード無線局ｎｉによりノード無線局ｎｊに向けて形成される送信ゾーンであることを、通信ＩＤｃを除く送信ゾーンＴＺｎｉ（α（ｎｉ→ｎｊ））におけるノード無線局ｎｉの各予約済みの指向性近傍ノード無線局により処理される通信ＩＤの数の和Ｃと定義する。従って、次式で表される。
【００５３】
［数２］
ηｎｉｃ（Ｐ）＝Σ∀ｎ∈ＲＧ−ｎｉ−α（ｎｉ→ｎｊ）（Ｌ）（|Ｃ∩ｃ|）      （２）
【００５４】
ここで、簡単に言えば、ある特定のパスに沿ったノード無線局の相関係数は、その所定の通信方向における高優先度フローの通信のために予約されたその指向性近傍ノード無線局に関する当該ノード無線局の結合の度合いを測定する。例えば、送信ゾーンＴＺα（ｎｉ→ｎｊ）に沿ったパスＰにおけるノード無線局ｎｉの相関係数がゼロであれば、それは、ノード無線局ｎｉが送信ゾーンα（ｎｉ→ｎｊ）において、他のどの高優先度フローの通信にも影響することなく、ノード無線局ｎｊへ送信可能であることを意味する。これに対して、ノード無線局ｎｉが送信ゾーンＴＺα（ｎｉ→ｎｊ）において２つの予約済みの指向性近傍ノード無線局を有し、一方が２つの高優先度フローの通信用に予約され、かつ他方がもう１つの高優先度フローの通信用に予約されていて、さらに、そのどちらかが通信ＩＤｃを有していれば、相関係数［ηｎｉｃ（Ｐ）］は２＋１−１＝２となる。これは、ノード無線局ｎｉは送信ゾーンＴＺα（ｎｉ→ｎｊ）においてノード無線局ｎｊへ送信することはできるが、他の高優先度フローの通信に結合度２で影響することを意味する。ノード無線局ｎｉの予約済みの指向性近傍ノード無線局がその固有の通信ＩＤｃで予約されれば、ノード無線局ｎｉは、相関係数ηｎｉｃ（Ｐ）の計算に際してその通信ＩＤｃに関するそのノード無線局の予約状態を無視する点に注目されたい。
【００５５】
＜定義９＞「通信ＩＤｃのパスＰの相関係数ηである［η（Ｐ）］」を、パスＰにおける全ノード無線局の相関係数の和と定義する。従って、次式で表される。
【００５６】
［数３］
η（Ｐ）＝Σ∀ｎｉ∈Ｐ（ηｎｉｃ（Ｐ））      （３）
【００５７】
ここで、相関係数η（Ｐ）＝０のとき、パスＰに沿ったどんな通信もその時刻における高優先度の通信プロセスを妨害又は干渉しない。相関係数η（Ｐ）＝０でなければ、パスＰは、他の高優先度フローのパスと、相関係数ηの関係にある。ルート結合の測定には、相関係数を使用する（例えば、非特許文献８及び９参照。）。
【００５８】
次いで、本実施形態に係る無線通信システムにおける各ノード無線局１における「ネットワーク認識」について以下に詳細に説明する。
【００５９】
本実施形態では、各ノード無線局が隣接ノード無線局のみを認識しているだけではなく、当該アドホック無線ネットワーク全体のネットワーク認識でもあるような機構を有する無線通信システムを提案する。この「ネットワーク認識」は、後述する前向きな（積極的に率先して行う）ルーティング方法を実施する際に役立つ。当該アドホック無線ネットワークにおける各ノード無線局ｎは、次のようなネットワーク状態情報を示す４つのテーブルを有し、これらのテーブルは図２の各無線局内のデータベースメモリ１５４内に格納される。以下に、これら４つのテーブルの詳細について説明する。
【００６０】
（１）ＡＳテーブル：ＡＳテーブルは、その一例を図５に示すように、自局のサービスエリア内の隣接ノード無線局毎に、方位角と、信号強度レベルの情報を格納し、後述する図１１のパケット送受信制御処理により作成更新される。
【００６１】
（２）ＮＬＳテーブル（ノード無線局ｎにおけるＮＬＳテーブルを、ＮＬＳＴｎと記載する。）：各ノード無線局ｎは、その隣接ノード無線局の方向を追跡するために、周期的にその隣接情報を「収集」してＮＬＳテーブルを形成する。時刻ｔにおけるノード無線局ｎのＮＬＳテーブル（ＮＬＳＴｎ（ｔ））は、隣接ノード無線局ｍ（ｍ∈Ｇｎ）のそれぞれについて、ある特定方向でノード無線局ｎにより検出された無線結合の最大信号強度ＳＩＧＮＡＬθｎ，ｍ（ｔ）を特定することができる。従って、最大信号強度ＳＩＧＮＡＬθｎ，ｍ（ｔ）は、ノード無線局ｎにおいてその隣接ノード無線局ｍからノード無線局ｎに対する方位角θで受信され、かつノード無線局ｎにより任意の時刻で検出されたときの最大信号強度である。ノード無線局ｎのＮＬＳテーブルは、その任意の隣接ノード無線局との最も可能性の高い通信方向を決定する際の手助けとなる。ここで、各ノード無線局は、予め取得された各隣接ノード無線局についてのＳＩＮＲ値が最大となる方位角を選び、このＳＩＮＲ値を隣接ノード無線局との間の親和度とする。各ノード無線局はこの方位角と親和度の値を各隣接ノード無線局毎に取り出し、現在日時を更新日時として、ＮＬＳテーブルを生成して更新する。当該ＮＬＳテーブルには、その一例を図６に示すように、各隣接ノード無線局毎に、最大のＳＩＮＲ値に対応する方位角、最大のＳＩＮＲ値である親和度、更新日時が格納されている。
【００６２】
（３）ＲＮＬテーブル（ノード無線局ｎにおけるＲＮＬテーブルを、ＲＮＬｎと記載する。）：ＲＮＬテーブルは、当該アドホック無線ネットワークにおける通信の予約状態に関するノード無線局ｎの検出結果を含む。これは、時刻ｔにおいてノード無線局ｎが検出できたアドホック無線ネットワーク内のすべてのアクティブな予約済みの通信ＩＤのノード無線局を含むノード無線局ｎに関するリストである。ＲＮＬテーブルは、その一例を図７に示すように、ノード無線局毎に、上述の通信状態のフラグ値とそのデータの更新回数（バージョンを示す）及び通信ＩＤを格納する。ＲＮＬテーブルについては、図７を参照して詳細後述する。
【００６３】
（４）ＧＬＳテーブル（ノード無線局ｎにおけるＧＬＳテーブルを、ＧＬＳｎと記載する。）：ＧＬＳテーブルは、時刻ｔにおいてノード無線局ｎが検出できたアドホック無線ネットワーク内のトポロジー情報を含む。具体的には、ＧＬＳテーブルは、その一例を図８に示すように、各ノード無線局毎に、隣接ノード無線局とその方位角データと、そのデータの更新回数（バージョンを示す）とを格納する。ＧＬＳテーブルについては、図８を参照して詳細後述する。
【００６４】
本実施形態においては、各ノード無線局は、上述のＲＮＬテーブルを含むパケット信号及びＧＬＳテーブルを含むパケット信号（以下、前者をＲＮＬパケット信号といい、後者をＧＬＳパケット信号という。）をそれぞれ異なる所定の周期間隔でブロードキャストして、ＲＮＬテーブル及びＧＬＳテーブルの生成及び更新処理を行うことを特徴としている。以下、これについて説明する。
【００６５】
各ノード無線局ｎは、そのＲＮＬテーブルをある周期的間隔（ＲＮＬパケット信号の送信周期）ＴＡでブロードキャストを行う。ここで、ＲＮＬパケット信号のブロードキャストは、次の２つの目的を果たす。すなわち、ノード無線局ｎがそのすべての隣接ノード無線局（例えば、ｉ、ｊ及びｋ）からのＲＮＬテーブルを受信すると、以下の処理が実行される。
（１）ノード無線局ｎは、隣接ノード無線局ｉ、ｊ及びｋをその隣接ノード無線局として含むように、ＮＬＳテーブル（ＮＬＳＴｎ）を形成し、それらの隣接ノード無線局のうちの任意の隣接ノード無線局との通信方向として最良である可能性のあるものとして記録する。
（２）ノード無線局ｎはまた、ノード無線局ｉの通信状態フラグ値（通信のアクティビティ状態）を記録し、他の隣接ノード無線局についても同様に記録して、当該ノード無線局ｎ自身のＲＮＬテーブルを更新する。
【００６６】
また、各ノード無線局ｎは、そのＧＬＳパケット信号をある周期的間隔（ＧＬＳパケット信号の送信周期）ＴＧでブロードキャストを行う。ここで、あるノード無線局ｎが、その隣接ノード無線局からＧＬＳパケット信号を受信すると、それ自身のＧＬＳテーブルを更新するが、これについては詳細後述する。
【００６７】
２つのパケット信号（ＲＮＬパケット信号とＧＬＳパケット信号）を２種類の送信周期でブロードキャストを行うことには、次のような理由がある。すなわち、ＲＮＬテーブルは各ノード無線局の通信状態のフラグ値（通信アクティビティ状態）を捕捉しており、一旦通信が開始されるとすぐに、あるノード無線局の集合におけるＲＮＬテーブルのデータが影響を受ける（そのデータが最新データで更新される）。従って、ＲＮＬパケット信号は、ＧＬＳパケット信号より速く伝搬される必要がある。さらに、ＲＮＬパケット信号はあたかもビーコン信号として動作する。従って、ＲＮＬパケット信号のより速い伝搬によって、アクティブな（通信可能な）ノード無線局の重要情報をより速く浸透させ得るだけでなく、正確な隣接ノード無線局の情報（方位角や信号強度レベル）を取得することが可能である。本実施形態において実施しようとしているのはフィッシュアイの概念であることから、正確な隣接ノード無線局の情報がより速く要求される。
【００６８】
これに対して、ＧＬＳテーブルはすべてのノード無線局の結合性に関するグローバルな情報であり、ノード無線局の物理的な移動（信号の伝搬に比べて遙かに遅い）に関するトポロジーの変化を反映する。さらに、任意のノード無線局におけるＧＬＳテーブルは、さほど正確である必要がない。データ量が大きいＧＬＳパケット信号はその伝搬が遅く、ＧＬＳテーブルよりもデータ量が小さいＲＮＬパケット信号はその伝搬が速いのは、このためである。
【００６９】
図９は図１のアドホック無線ネットワークにおいて用いられるトーン信号とパケット信号の送受信処理を示すタイミングチャートである。
【００７０】
従来技術に係るＭＡＣプロトコルの方法においては、ビーコン信号、ＲＮＬパケット信号、ＧＬＳパケット信号の３つのパケット信号の定期的な送信が必要であり、占有時間が比較的長く、スループットが落ちるという問題点があった。この問題点を解決するために、本実施形態に係るＭＡＣプロトコルでは、図９に示すように、送信側の無線局は、無変調搬送波であるトーン信号に続いて、ＲＮＬテーブル、ＧＬＳテーブル、ＲＴＳ又はＣＴＳ、もしくは送信したいデータを含むパケット信号を送信する。これに対して、受信側の無線局は、トーン信号を検出した後、パケット信号を復号化して復号化したデータを取り込み、データ処理を実行する。なお、ＲＮＬテーブル又はＧＬＳテーブルを含むＲＮＬパケット信号又はＧＬＳパケット信号の送信は上述のように周期的に実行される。
【００７１】
図１０は図１のアドホック無線ネットワークにおいて用いられる各無線局での放射パターンの種類と無線通信プロトコルを示すタイミングチャートである。図１０では、本実施形態に係る４方向ハンドシェイクのアンテナモードの使用例を示している。適応制御パターンは移動中のノード無線局を追跡することはできるが、ビーム及びヌルはパケット信号が受信されなければ形成され得ない。従って、送信側のノード無線局からのトーン信号＋ＲＴＳの送信やトーン信号＋ＣＴＳの送信では、オムニパターンが使用される。これに対して、受信側のノード無線局におけるトーン信号＋ＲＴＳの受信やトーン信号＋ＣＴＳの受信では、その開始時に回転セクターパターンが使用された後、ＡＳテーブルに基づいた方位角に向けられたセクターパターンを使用し、当該セクターパターンを用いた通信中において適応制御のための準備処理を実行し、最後に適応制御用放射パターンに移行する。
【００７２】
次いで、ＮＬＳテーブルの形成方法について以下に説明する。
【００７３】
例えば任意のノード無線局ｎは、例えば任意のその隣接ノード無線局ｍからＲＮＬパケット信号を受信すると、そのノード無線局ｎのＮＬＳテーブル（ＮＬＳＴｎ）を逐次そのデータをインクリメントしながら形成する。ノード無線局ｎは、その可変ビームアンテナ１０１をある特定の方位角の方位角に設定してＲＮＬパケットを受信することから、その特定の方向でノード無線局ｎによって認知される隣接ノード無線局ｍとの通信方向として最良である可能性のある方位角、及び無線回線でのノード無線局間結合が最大である信号強度ＳＩＧＮＡＬθｎ，ｍ（ｔ）を認識している。本実施形態では、互いに隣接する２つのノード無線局間で対称性のリンクを想定している。
【００７４】
例えば任意のノード無線局ｎは、それ自身の通信状態のフラグ値（予約状態又はアクティビティ状態）を検出する。ノード無線局ｎは、それが通信を希望していることを指示するＲＴＳを発行する必要があればいつでも、それ自身を「アクティブな予約済みのノード無線局」（通信状態のフラグ値＝１）として設定し、所定のしきい値期間の間にＲＴＳを発行しない場合はそれ自体を「非アクティブな又は予約済みでない（通信不可能な）ノード無線局」（通信状態のフラグ値＝０）として設定する。また、ノード無線局ｎは、例えばその隣接ノード無線局ｍからＲＴＳを受信すると、必ずそれ自身のＮＬＳテーブル（ＮＬＳＴｎ）にノード無線局ｍをアクティブノード無線局（通信状態のフラグ値＝１）として設定する。ノード無線局ｍがそれ自身を非アクティブ又は予約済みでない状態にするとき（通信不可能状態とするとき）、この情報がノード無線局ｍからＲＮＬパケットの周期的なブロードキャストによりノード無線局ｎに到達する。
【００７５】
次いで、ＲＮＬテーブルの形成方法について以下に説明する。
【００７６】
各ノード無線局は、当該アドホック無線ネットワークにおける通信の予約状態に関するその認知を含むそのアクティブノード無線局リストを含むＲＮＬテーブルを含むＲＮＬパケット信号を、周期的にブロードキャストする。複数の異なるノード無線局から周期的なＲＮＬパケットを受信すると、各ノード無線局はこれらの情報を取り入れて改訂更新されたＲＮＬテーブルを形成し、周期的間隔を待って更新されたＲＮＬパケット信号をその隣接ノード無線局に対してブロードキャストする。
【００７７】
各ノード無線局では、ＲＮＬパケットはまず、そのノード無線局のＲＮＬテーブルによって更新される。従って、初期状態では、アドホック無線ネットワークの開始時には、すべてのノード無線局は単にそれ自身の隣接ノード無線局の予約状態又はアクティビティ状態（通信可能状態）を認識しているだけであって、当該無線通信システム内の他のノード無線局に関しては「何も知らない状態」にある。各ノード無線局は、周期的にそれ自身のＲＮＬテーブルを更新して、更新したＲＮＬパケット信号をその（１つ又は複数の）隣接ノード無線局に対してブロードキャストを行う。その隣接ノード無線局からのそれらの隣接ノード無線局に関するこの周期的な更新メッセージ（ＲＮＬパケット信号）の送信により、各ノード無線局は次第に、他のノード無線局及びそれらの隣接ノード無線局に関する予約状態の情報（ＲＮＬテーブルに含まれる情報）を取得していく。このように、各ノード無線局は、他のノード無線局から受信した更新メッセージ（ＲＮＬパケット信号）を基礎としてそれ自身のＲＮＬテーブルを更新することができる。
【００７８】
移動中のノード無線局へのネットワーク状態情報の浸透処理における大きな概念は、伝送される情報がある程度正確に認識されなければならないことにある。複数の異なるノード無線局からの更新の伝搬は非同期的であるため、情報の更新回数（バージョン）の概念を導入することが肝要になる。例えば、２つのＲＮＬパケットＡ１及びＡ２がともにノード無線局ｎから複数ホップで離れているノード無線局ｍに関する情報を伝送しながらノード無線局ｎに到達するものとする。ノード無線局ｎにおいてノード無線局ｍに関する情報を更新するためには、ノード無線局ｍに関する最も新しい情報を伝送しているのはどれか、すなわち、「ＲＮＬパケットＡ１であるか、もしくはＲＮＬパケットＡ２であるか？」を発見するメカニズムが存在していなければならない。
【００７９】
これを実行するために、本発明者らは最新性トークンの同一概念（最も新しいかの指標であるバージョンを示す更新回数情報を有すること）及びこれを適正にインクリメントする機構を使用している。仮に２つの更新メッセージ（ＲＮＬパケット）が、例えばノード無線局ｎである同じノード無線局に関するデータ集合を保有していれば、ノード無線局ｎのより高い最新性の値（更新回数）を伝送している更新メッセージ（ＲＮＬパケット）の方がそれに関するより新しい情報を保有している。
【００８０】
ノード無線局ｎにおけるＲＮＬテーブルの一例を示す図７において、ＲｉはＮ個のノード無線局よりなるアドホック無線ネットワークにおけるノード無線局ｎｉの最新性を示す更新回数であり、Ｓｉは各ノード無線局の対応する予約状態又はアクティビティ状態を示す通信状態のフラグ値を示し、０（予約状態ではない非アクティブ：通信不可能）又は１（予約状態であるアクティブ：通信可能）のいずれかである。
【００８１】
次いで、ＧＬＳテーブルの形成方法について以下に説明する。
【００８２】
各ノード無線局は、ネットワーク連結情報を捕捉するためのＧＬＳテーブルを保持している。各ノード無線局では、ＧＬＳテーブルはまず、そのノード無線局のＮＬＳテーブルによって更新される。従って、初期状態では、アドホック無線ネットワークの開始時には、すべてのノード無線局は単にそれ自身の隣接ノード無線局を認識しているだけであって、当該無線通信システム内の他のノード無線局に関しては「何も知らない状態」にある。各ノード無線局は、周期的にそのＧＬＳテーブルを更新して、更新したＧＬＳパケット信号を所定の送信周期でその隣接ノード無線局に対してブロードキャストする。その隣接ノード無線局からのそれらの各隣接ノード無線局に関するこの周期的な更新メッセージ（ＧＬＳパケット信号）により、ノード無線局は次第に、他のノード無線局及びそれらの各隣接ノード無線局に関するＧＬＳテーブル情報を取得していく。このように、各ノード無線局は、他のノード無線局から受信した更新メッセージ（ＧＬＳパケット信号）を基礎として、それ自身のＧＬＳテーブルを更新する。
【００８３】
ここで、更新の周期性を制御すれば、当該アドホック無線ネットワーク内の更新トラフィック及び各ノード無線局に記憶されたネットワーク状態情報の精度を制御できることは留意されるべき点である。例えば、更新メッセージ（ＧＬＳパケット信号）の伝搬が頻繁すぎると、制御トラフィックは増大するが、各ノード無線局に記憶されたネットワーク状態情報の精度も上がる。ここで、当該アドホック無線ネットワークが更新の伝搬でフラッドされることは決してない。任意の時点におけるアドホック無線ネットワーク内の最大パケット数は、常時、アドホック無線ネットワーク内のノード無線局数より少ない。この場合もやはり、ＲＮＬパケットの伝搬について上述したような最新性の概念（更新回数の情報保持）を実施する必要がある。これは、仮に２つのＧＬＳパケット信号の更新メッセージが、例えばノード無線局ｎである同じノード無線局に関するデータ集合を保有していれば、ノード無線局ｎのより高い最新性トークン値（より大きい更新回数）を伝送している更新メッセージ（ＧＬＳパケット信号）の方がそれに関するより新しい情報を保有することを意味している。
【００８４】
ノード無線局ｎは、他のノード無線局からＧＬＳパケット信号を受信すると、それ自身のＧＬＳテーブルを更新する。これを行うために、ノード無線局ｎのＧＬＳテーブルに記憶されたすべてのノード無線局の最新性トークン値（更新回数）と、最近に到着した更新のためのＧＬＳパケット信号に記憶されたすべてのノード無線局の最新性トークン値（更新回数）とが比較される。ノード無線局ｎのＧＬＳテーブルにおける任意のノード無線局、例えばノード無線局Ｘの最新性トークン（更新回数）の方が更新するＧＬＳパケット信号におけるそれより少ないことが分かれば、更新するＧＬＳパケット信号の方がノード無線局Ｘに関する最新の情報を伝送していることは明らかである。従って、ノード無線局ｎのＧＬＳテーブルにおけるノード無線局Ｘに関する全体情報は、受信された更新ＧＬＳパケット信号におけるノード無線局Ｘの情報によって上書きされる。このステップは、すべての更新ＧＬＳパケット信号について、それらのそのホストノード無線局ｎへの到着に伴って非同期的に実行される。このステップにより、更新ＧＬＳパケット信号から収集することのできるすべての最新情報のノード無線局ｎによる捕捉が促進される。
【００８５】
ここで、この機構は、各ノード無線局がアドホック無線ネットワークの正確な状態を認識することを保証するものでないことを留意する必要がある。各ノード無線局がアドホック無線ネットワークのおおよその状態を解明する際に手助けとなるものは、単なる「認識」でしかない。これは、ノード無線局に近接した周辺のノード無線局においてはより正確な状態情報の保持を促進するが、距離が大きくなると（離れてくると）次第にネットワーク情報の詳細の精度が下がる「フィッシュアイアプローチ」に類似している。
【００８６】
任意のノード無線局ｎにおけるＧＬＳテーブルの構造を示す図９において、ＲｉはＮ個のノード無線局よりなるアドホック無線ネットワークにおけるノード無線局ｎｉの最新性トークン値（更新回数）であり、＜ｎｊ，α（ｎｉ，ｎｊ）＞はノード無線局ｎｊがノード無線局ｎｉの隣接ノード無線局であることを示している。ここで、α（ｎｉ，ｎｊ）はノード無線局ｎｉがノード無線局ｎｊと最も良好に通信できる送信ビーム方位角αを示している。
【００８７】
次いで、本実施形態における「ネットワークにおける情報の浸透メカニズム」について以下に詳細に説明する。
【００８８】
このパーコレーションのメカニズムの目的は、各ノード無線局に近似トポロジーとネットワーク内で進行中の通信イベントとを認識させることにある（例えば、非特許文献１５参照。）。この場合の目的は、ローカル情報は正確に認知するが、グローバルなネットワーク情報は近似的に認知することにある。この近似的なネットワーク認識は、例えば非特許文献１４及び１５で検討されているように、ＭＡＣ及び適応型ルーティングプロトコルの双方を実装する上で役立つ。その近傍ノード無線局の方向を追跡するため、各ノード無線局ｎはその指向性近傍の情報を周期的に収集し、従って、その任意の近傍ノード無線局との最良の通信可能方向を決定することができる。ネットワークにおける各ノード無線局ｎは、以下に示すネットワークの状態情報を保有する。
【００８９】
ＲＮＬテーブル（予約済みノード無線局リスト）（ＲＮＬｎ）：これは、ネットワーク全体の高優先度フローの通信アクティビティに関するノード無線局ｎの認知を含んでいる。上述したように、これは、各ノード無線局が任意の高優先度フローの通信プロセスにおける送信局もしくは受信局又はこの送信局もしくは受信局ノード無線局の指向性近傍ノード無線局のいずれかである、時刻ｔにおけるノード無線局の集合である。ＲＮＬテーブルの各ノード無線局は、そのために当該ノード無線局が予約される通信ＩＤの集合Ｃである。
【００９０】
ＧＬＳテーブル（グローバルリンク状態テーブル）（ＧＬＳＴｎ）：これは、その時刻においてｎが認知するグローバルネットワークのトポロジー情報を含んでいる（例えば、非特許文献１４及び１５参照。）。
【００９１】
このＲＮＬテーブル及びＧＬＳテーブルを使用して、ノード無線局は、予約済みのノード無線局を含むゾーンから可能な限り遠ざかるルートを計算する。従って、ＲＮＬテーブルにおける全ノード無線局は、高優先度ゾーンと呼ばれるネットワーク部分を予約しているように考えられる。他の低優先度のトラフィックは、そのゾーンを使用できない。従ってこれらは、ベストエフォート型のＱｏＳを達成するように適切な多様ルートを選択していく。新しい高優先度フローは、後述するように、既存のＲＮＬテーブルを調べて進行中の他の高優先度フローの通信に対するゾーン非連結性を最大化されたルートを選択する。
【００９２】
各ノード無線局は、そのＲＮＬテーブルをある周期間隔、例えばＴＡでブロードキャストする。ＲＮＬテーブルのブロードキャストは、次の２つの目的を果たす。すなわち、ノード無線局ｎがそのすべての近傍ノード無線局（例えばノード無線局ｉ、ｊ及びｋ）からＲＮＬテーブルを受信すると、ノード無線局ｎは、ノード無線局ｉ、ｊ及びｋをその近傍ノード無線局として包含するＧＬＳテーブルＧＬＳＴｎを形成し、それらの各々との最良の通信可能方向を記録する。ノード無線局ｎはまた、ノード無線局ｉの通信アクティビティの状態を記録し、かつ他の近傍ノード無線局についても同様に記録し、受信した情報の最新性に依存してその独自のＲＮＬテーブルを形成する（非特許文献１２参照。）。各ノード無線局は、そのＧＬＳテーブルをある周期間隔、例えばＴＧでブロードキャストする。ノード無線局ｎは、その近傍ノード無線局からＧＬＳテーブルを受信すると、受信した情報の最新性に依存してその独自のＧＬＳテーブルを更新する（非特許文献１２参照。）。
【００９３】
ＲＮＬテーブルは、ビーコンとして作用することからＧＬＳテーブルより速く伝播される必要がある。従って、ＲＮＬテーブルのより速い伝播によって、アクティブなノード無線局の重要情報をより速く浸透させるだけでなく、正確な近傍情報（方向、信号レベル）を取得することが可能である。ＧＬＳテーブルは、物理的移動（信号の伝播に比べて遙かに遅い）に関するトポロジーの変化を反映するため、超高速で伝播される必要はない。オーバーヘッドは、周期間隔ＴＡ及びＴＧを調整して制御することができる。周期間隔ＴＡ及びＴＧの好ましい現在の値はそれぞれ２００ミリ秒及び５秒である。
【００９４】
次いで、「位置の追跡とＭＡＣプロトコル」について以下に説明する。
【００９５】
指向性アンテナの能力を十分に活用するためには、発信無線局及び宛先無線局の近傍ノード無線局はすべて、他の方向で新たな通信を開始することができて発信無線局と宛先無線局との間で現に行われているデータ通信との干渉を防止できるように、通信の方向を認識していなければならない。従って、各ノード無線局においてその近傍ノード無線局の方向を追跡するメカニズムを保有することが不可欠になる。本実施形態においては、各ノード無線局はアイドルの間、全方向性検出モード（オムニパターンモード）で待機する。これは、しきい値を超える何らかの信号を検出するたびに、回転セクターパターンの受信モードに入る。回転セクターパターンの受信モードでは、ノード無線局ｎはその指向性アンテナを全方向へ３０度間隔で順次回転させて各方向における順次指向性受信の形式で３６０度の空間全体をカバーし、各方向で受信された信号を検出する。一回転の後、これは、受信された最大の信号強度によって信号の最良の受信可能方向を決定する。次にこれはそのビームをその方向へ設定し、信号を受信する。
【００９６】
ここで、受信された信号を復号する受信機を有効化するために、各制御パケットは、受信機の回転性受信ビームを３６０度回転させる時間がトーン信号の持続時間（本発明者らのケースでは２００マイクロ秒）より少し短いような持続時間を有する先行トーン信号を伴って送信される。任意の制御パケットより前にこのトーン信号を送信する目的は、受信機が、信号の受信方向として最良である可能性のあるものを追跡できるようにすることにある。これがそのビームをその方向へ設定すると、トーン信号の目的は果たされ、続いて制御パケットが送信される。
【００９７】
提案した本実施形態に係るフレームワークでは、媒体アクセス制御に次の４タイプのブロードキャスト（全方向性）制御パケット、すなわち予約済みノード無線局リスト（ＲＮＬテーブル）、グローバルリンク状態テーブル（ＧＬＳテーブル）、ＲＴＳ信号及びＣＴＳ信号を使用している。この他、制御パケットのＡＣＫ（肯定応答）信号も、指向性の制御パケットである。ＲＮＬテーブル及びＧＬＳテーブルは周期的な信号であり、各ノード無線局から予め画定された間隔で送信される。各周期的間隔において、例えばｍである各ノード無線局は、ＲＮＬテーブルをその近傍ノード無線局へ、もしその無線媒体がフリーであればブロードキャストする。先に指摘した通り、ＲＮＬテーブルは、無線受信機がビーコン信号の最良の受信可能方向を検出する際に役立つ先行のトーン信号を伴って送信される。次いで各受信機はそのビームをその方向へ設定し、パケット信号を受信して復号する。
【００９８】
ノード無線局ｎは、例えばノード無線局ｊとのデータ通信の開始を希望する毎に無線媒体をチェックし、媒体がフリーであれば全方向性のＲＴＳ信号を発行する。送信目標のノード無線局ｊは、ＲＴＳ信号を受信すると全方向性のＣＴＳ信号を発行する。この場合のＲＴＳ／ＣＴＳの目的は、オムニアンテナを使用する場合のように、ノード無線局ｎ及びｊの近傍ノード無線局による送信又は受信を禁止することではなく、ノード無線局ｎ及びｊの近傍ノード無線局にノード無線局ｊがｎからデータを受信しようとしていることを知らせることにある。これはまた、通信のおおよその持続時間も特定する。ノード無線局ｎ及びｊのすべての近傍ノード無線局は、それらの指向性ネットワークアロケーションベクトル（ＤＮＡＶ）をノード無線局ｎ及びｊの方向へ設定することにより、ノード無線局ｎとｊとの間の通信を追跡する。従って、ノード無線局ｎ及びｊの近傍に存在するノード無線局は、ノード無線局ｎとｊとの間で行われている通信を妨害することなく他の方向への通信を開始することができる。
【００９９】
次いで、「ゾーン非連結性を最大化されるルーティング」について以下に説明する。
【０１００】
本実施形態においては、本発明者らは、ルート選択の規範として、相関係数及び伝搬ホップの計数という２つの基準の使用を提案する。上述のように、ルートの相関係数は、そのルートの他のアクティブルートに対するゾーン非連結性に逆比例する。同時に、当該ネットワークにおいては、選択される種々の多様なルートのホップの計数もまた別の関心事である。そうでなければ、通信方法によっては、ある特定の宛先無線局を求めて、各中間ノード無線局が既存の通信ゾーンを避けるルートの選択を試行し、最終的にゾーン非連結ルートを捜してネットワーク中を横断するという事態になることがある。従って、相関係数及び伝搬ホップ計数の双方を最小限に抑えれば、ゾーン非連結性を最大化された最短パスが発生する。ネットワーク内の各ノード無線局は、何らかの通信で既に使用中であるノード無線局との干渉を最小限に抑えるように、ネットワーク状態に関するそのカレント情報（近似トポロジー情報及び進行中の高優先度フローの通信情報）を使用して特定の宛先へ到達する適切な次のホップを計算する。
【０１０１】
まず、発信無線局からパケット信号を送信するときは、ゾーン非連結パス選択基準が優先される。ここで、パケット信号が複数のホップを経験した後に中間ノード無線局に到達する場合は、宛先無線局へ向けて段階的により短かいホップルートが選択される。従って、この適応型ルート計算メカニズムは、本実施形態において提案するルーティングアルゴリズムの収束を保証する。本発明者らは下記の関数を使用し、少ない伝搬ホップ計数にはより少ない相関係数ηを有するパスの選択を、かつより多い伝搬ホップ計数にはより少ないホップパスの選択を保証するリンクウェイトを計算した。公知のディジクストラ（Dijkstra）方法の最短パスアルゴリズムは、最小のリンクウェイトを有するパスを選択するように、すなわちその選択されたパス上の全リンクの合計リンクウェイトが最小になるように修正されている。すなわち、通信ＩＤｃを有する現在の通信フローに対する各リンク（ｎｉ，ｎｊ）のリンクウェイトＬＷ（ｎｉ，ｎｊ）は次式で表される。また、全リンクウェイトＬＷＴは、発信無線局Ｓから宛先無線局Ｄまでのすべてのリンクに対するリンクウェイトＬＷ（ｎｉ，ｎｊ）の線形和であり次式で表される。なお、下記の式（４）は第１の実施形態において高優先度フローに対して適用され、低優先度フローに対し式（４）においてホップ計数値Ｈ＝０として式（６）を用いるが、第３の実施形態で低優先度フローに対しても適用してもよい。
【０１０２】
［数４］
ＬＷ（ｎｉ，ｎｊ）＝α＋ηｎｉｃ＋γＨ      （４）
［数５］
ＬＷＴ（Ｓ，Ｄ）＝ΣＬＷ（ｎｉ，ｎｊ）      （５）
［数６］
ＬＷ（ｎｉ，ｎｊ）＝α＋ηｎｉｃ      （６）
【０１０３】
ここで、αは初期リンクウェイトであり、本実施形態において好ましくは０．０１である。なお、α≪ηｎｉｃかつα≪Ｈである。また、変形例では、αを考慮しなくてもよく、α＝０であってもよい。さらに、ηｎｉｃは現在の処理対象の通信フローの通信ＩＤｃを除き、指向性ゾーン（ｎｉ→ｎｊ）における指向性の各予約済みの近傍ノード無線局によって処理される全通信数の和、すなわち、次式で表される。
【０１０４】
［数７］
ηｎｉｃ＝Σ∀ｎ∈ＡｃｔＧ−ｎｉ−α（ｎｉ→ｎｊ）（ｔ）（｜Ｃ∩ｃ｜）
（７）
【０１０５】
また、Ｈは、ルートパスが計算されている現在処理対象のパケット信号の伝搬されたホップ計数値であり、γはウェイト係数であり、本実施形態では好ましくは０．５である。
【０１０６】
ウェイト係数は、まず多様なパスが選択されるが、収束を保証するために、相関係数ηの駆動ルートよりも漸次最短ホップルートが優先されるような方法で調整される。ホップ計数値Ｈ及び相関係数ηがゼロのときは、αは、最短パスを求める際に各リンクに割り当てられる最初のリンクウェイトである。γは、低優先度フローが常に多様パスを選択するように調整する。ここでこれと同時に、より短い段階的ホップルートをη駆動ルートより優先させて収束を保証しなければならない。そうでなければ、低優先度のスループットは受容不可になる。高優先度フローの場合は、ηよりホップ計数の方が重要視される。この点については、詳細後述する。
【０１０７】
まず、パケットが発信無線局Ｓにより通信ＩＤｃに向けて送信される場合は、サブＩＤであるｃｓ１が割り当てられ、次に、発信無線局ＳがそのＲＮＬテーブル及びＧＬＳテーブルを調べ、リンクウェイトを割当て、最小ウェイトのパス沿いにパケットを伝送すべく宛先無線局方向への適切な次のホップを選択する。通信サブＩＤであるｃｓ１及び現在の次のホップは、発信無線局Ｓ内に後のルート計算のための履歴情報として保持される。よって、発信無線局Ｓに次のパケットが同じ宛先無線局、すなわち通信ＩＤｃに向けて到来すると、パケット信号に例えばｃｓ２という新たなサブＩＤが割り当てられ、パケット信号は、発信無線局Ｓが先に選択したパスとはゾーン非連結であるパスに沿ってルーティングされることが可能である。この第２のパケットに関しては、発信無線局Ｓは先のゾーン（最初のパケットの次のホップを含むゾーン）を回避しようとし、同様にして第２のパケットの次のホップを計算する。次に、履歴はこの新たな次のホップ及び通信サブＩＤであるｃｓ２で上書きされる。次回、第３のパケット信号に割り当てられる通信サブＩＤは、ｃｓ１になる。よって、サブＩＤは、ｃｓ１とｃｓ２との間で切り替わり、発信無線局Ｓによるゾーン非連結最短ルートの交互選択が保証される。従って基本的に、発信無線局Ｓはデータパケットを２つのゾーン非連結パスに沿って交互に送信する。
【０１０８】
各中間ノード無線局は、個々のＲＮＬテーブル及びＧＬＳテーブルによって宛先無線局に向かう適切な次のホップを適応的に選択し、適切なリンクウェイトを割り当てるが、発信無線局Ｓのようには履歴情報を保持しない。本メカニズムは、各ノード無線局がネットワークの正確なステータスを認識することを保証しないため、パス内の各ノード無線局ｎは宛先無線局へ到達するためのその最良の次のホップを計算する。
【０１０９】
次いで、「高優先度のゾーン予約による優先度ベースのサービスの差別化」について以下に説明する。
【０１１０】
本発明者らが提案するプロトコルは、基本的には、高優先度フローに最短かつ他の高優先度フローの通信に対するゾーン非連結性を最大化されたパスを割り当てる。低優先度フローは、進行中の高優先度フローの通信によって予約されたすべての高優先度ゾーンを避けてアダプティブなゾーン非連結パスを辿る。低優先度フローの場合は、最短パス規範が主力の基準ではない。従って、本実施形態に係る提案するプロトコルは、ネットワーク内に低優先度の通信が幾つか存在するとしても、高優先度トラフィックが低優先度トラフィックによって少しでも妨害されることはないという事実を保証する。その結果、優先性が異なる複数のフローを有するネットワークにおいて高優先度のスループットは、ネットワークが高優先度フローしか扱っていないかのようにほぼ同一であり続ける。ネットワーク内に２つ以上の高優先度フローが存在すれば、そのそれぞれは他の高優先度フローに対してゾーン非連結を最大化されるパスを辿ろうとする。
【０１１１】
ネットワーク内の各フローは、固有の通信ＩＤで識別され、高優先度又は低優先度のいずれかの範疇に帰属する。高優先度フローによって送られたパケットが特定の宛先に向かってあるノード無線局に着信すると、そのノード無線局は単純にその宛先に向かう最低コストのパスを選択し、当該パケットをその選択されたパス上の次の中間ホップへ送信する。
【０１１２】
各優先度フローの最低コストパスは、上記式（４）を用いて下記のように計算される。
【０１１３】
（１）ネットワーク内の各リンクウェイトＬＷ（ｎｉ，ｎｊ）が定数値αで初期化される。
【０１１４】
（２）ノード無線局ｎｉ及びｎｊペアのいずれかが何らかの高優先度フローの通信に関わっていれば、送信局ｎｉから受信局ｎｊへ向かう指向性送信ゾーン内の全ノード無線局は、その活動状態を高に設定してそれらがアイドル状態のままでいて高優先度の送信をサポートすべきであることを示す。これらは予約済みノード無線局として扱われ、ＲＮＬテーブルにおいて更新される。ノード無線局のＲＮＬテーブルは他の全ノード無線局に周期的に送信され、他のノード無線局はそのＲＮＬテーブルを更新することができる。
【０１１５】
（３）予約済みのノード無線局（ＲＮＬテーブルに属するノード無線局）に接続される各リンクのリンクウェイトは、上記式（４）を基礎とする値に設定される。各高優先度フローは適宜、他の高優先度フローに対してゾーン非連結を最大化されるパスを辿ろうとする。低優先度フローのソースがそのルートを計算すると、本実施形態において提案するパス選択アルゴリズムは、パス選択プロセスの間に高値を有するリンクを自動的に回避する。従って、こうした方法により、高優先度フローが辿るパス周辺のゾーン全体が回避される。
【０１１６】
（４）高い活動状態を有する予約済みのノード無線局がかなりの時間にわたって高優先度のパケットを受信しなければ、必要に応じて他の通信が通過パスを選択できるように自らを非予約（予約済みではない）として設定する。これは、ルート選択の間に高優先度ノード無線局によって使用される、異なる優先度のフローが所望のスループットを達成できるようにする一種の適応的な送信ゾーンの予約及び解放プロセスである。第３の実施形態に係る提案するプロトコルの場合、ウェイト係数γは、好ましくは、次式のごとく、高優先度の場合はγ１＝０．５、低優先度の場合はγ２＝０．２を採用する。
【０１１７】
［数８］
ＬＷ（ｎｉ，ｎｊ）＝α＋ηｎｉｃ＋γ１Ｈ（高優先度フローのとき）（８）
［数９］
ＬＷ（ｎｉ，ｎｊ）＝α＋ηｎｉｃ＋γ２Ｈ（低優先度フローのとき）（９）
ここで、
［数１０］
γ１＞γ２
【０１１８】
より低いウェイト係数γ２は、選択されるルートがより高いウェイト係数γ１で選択されるルートより長くなることを意味する。これは、低優先度フローのトラフィックは高優先度フローのゾーンを避けてより長くかつ多様なルートを選択するのに対して、高優先度のトラフィックは複数の高優先度フロー間の干渉を低減させるために他の高優先度ルートよりも短い多様ルートを選択することを意味する。
【０１１９】
適応化されたルーティングの処理の詳細を図１１乃至１４を参照して以下に説明する。なお、図１１のサブルーチンであるルーティング及び通信処理（Ｓ１２）については、以下の３つの実施形態に分けて実行することができる。
（Ａ）図１２の第１の実施形態：高優先度フローのパケット信号を最小の全リンクウェイトを有するパスで伝送する一方、低優先度フローのパケット信号を上記高優先度フローのパスを除いて最小の全リンクウェイト（ここで、ホップ数の計数値Ｈ＝０）を有するパスで伝送することを特徴とするルーティングに係るルーティング及び通信処理。
（Ｂ）図１３の第２の実施形態：高優先度フローのパケット信号を、例えばディジクストラ方法の最短アルゴリズムを用いて計算された最短パスで伝送する一方、低優先度フローのパケット信号を上記高優先度フローのパスを除いて最小の全リンクウェイト（ここで、Ｈ＝０）を有するパスで伝送することを特徴とするルーティングに係るルーティング及び通信処理。
（Ｃ）図１４の第３の実施形態：高優先度フローのパケット信号を、低優先度フローのパスよりも短いパスであって、最小の全リンクウェイトを有するパスで伝送する一方、低優先度フローのパケット信号を上記高優先度フローのパスを除いて最小の全リンクウェイトを有するパスで伝送することを特徴とするルーティングに係るルーティング及び通信処理。
【０１２０】
図１１は図２の無線局１の管理制御部１０５によって実行されるパケット送受信制御処理を示すフローチャートである。
【０１２１】
図１１において、まず、ステップＳ１で回転セクターパターンで可変ビームアンテナ１０１を所定の方位角（例えば、３０度）毎に変化して回転走査するように制御して受信信号を受信し、ステップＳ２において所定のしきい値以上の信号強度レベルの受信信号を受信したか否かが判断され、ＹＥＳのときはステップＳ３に進む一方、ＮＯのときはステップＳ９に進む。ステップＳ９において送信すべきパケット信号があるか否かが判断され、ＹＥＳのときはステップＳ１０に進む一方、ＮＯのときはステップＳ１に戻る。ステップＳ１０において送信すべきパケット信号はＲＮＬパケット信号、もしくはＧＬＳパケットであるか否かが判断され、ＹＥＳのときはステップＳ１１に進む一方、ＮＯのときはステップＳ１２に進む。ここで、前者のＲＮＬパケットは、所定の周期期間ＴＡで周期的にそのイベントが発生され、後者のＧＬＳパケットは、所定の周期期間ＴＧで周期的にそのイベントが発生され、このステップでＹＥＳとなる。ステップＳ１１においてオムニパターンで当該テーブルを含むパケット信号を送信した後、ステップＳ１に戻る。一方、ステップＳ１２において図１４のサブルーチンであるルーティング及び通信処理を実行した後、ステップＳ１に戻る。
【０１２２】
ステップＳ３では、回転セクターパターンを停止して、可変ビームアンテナ１０１の放射パターンを、停止した所定の方位角に向けるセクターパターンに設定する。次いで、ステップＳ４において適応制御パターンで受信信号を受信し、パケット情報を復号化し受信信号の信号強度レベルを測定し、ステップＳ５において受信信号ＲＳを判別して以下のようにステップＳ６，Ｓ７又はＳ８に分岐する。
【０１２３】
ここで、受信信号ＲＳ＝ＧＬＳパケット信号であるときは、ステップＳ６でＧＬＳテーブル等更新処理を実行した後、ステップＳ１に戻る。このＧＬＳテーブル等更新処理では、現在格納されているＧＬＳテーブルと、受信信号に含まれるＧＬＳテーブルとを比較して、更新回数がより多いバージョンが新しいデータのみをそれを用いてＧＬＳテーブルを更新し、新しいノード無線局であるときはそのノード無線局についての情報を追加する。また、ステップＳ５では、受信信号ＲＳ＝ＲＮＬパケット信号であるときは、ステップＳ７に進み、ＡＳテーブル等更新処理を実行した後、ステップＳ１に戻る。このＡＳテーブル等更新処理では、パケット信号内のノード無線局のＩＤと、当該受信信号を受信するときに検出された方位角と信号強度レベルに基づいてＡＳテーブルを更新するとともに、上記のＧＬＳテーブルの更新方法と同様に、現在格納されているＲＮＬテーブルと、受信信号に含まれるＲＮＬテーブルとを比較して、更新回数がより多いバージョンが新しいデータのみをそれを用いてＲＮＬテーブルを更新し、新しいノード無線局であるときはそのノード無線局についての情報を追加して更新する。さらに、ステップＳ５で受信信号ＲＳ＝その他の信号であるときは、ステップＳ８でその他の信号の受信処理を実行した後、ステップＳ１に戻る。
【０１２４】
図１１の制御フローにおいては、ステップＳ１，Ｓ２において、可変ビームアンテナ１０１を回転走査して所定のしきい値以上の信号強度レベルの受信信号を受信したときに、その受信信号を検出しているが、本発明はこれに限らず、可変ビームアンテナ１０１を３６０度にわたって回転走査して、所定のしきい値以上の信号強度レベルの受信信号を受信しかつそのうちの最大の受信信号を、検出された受信信号としてもよい。
【０１２５】
図１２は図１１のサブルーチンである、第１の実施形態に係るルーティング及び通信処理（ステップＳ１２）の処理を示すフローチャートである。
【０１２６】
図１２において、まず、ステップＳ２１においてＧＬＳテーブルを参照して、発信無線局と宛先無線局との間において、すべてのパスを検索し、ステップＳ２２において現在の処理対象のパケット信号は高優先度のパケット信号であるか否かが判断され、ＹＥＳのときはステップＳ２３に進む一方、ＮＯのときはステップＳ２４に進む。ステップＳ２３において、ＲＮＬテーブルを参照して各検索されたすべてのパスに対して以下の通り全リンクウェイトを計算する。すなわち、各リンク（ｎｉ，ｎｊ）に対して式（４）を用いてリンクコストを計算した後、式（５）を用いて全リンクウェイトを計算し、ステップＳ２５に進む。一方、ステップＳ２４において、低優先度のパケット信号のときは、ＲＮＬテーブルを参照して各検索されたすべてのパスに対して以下の通り全リンクウェイトを計算する。すなわち、各リンク（ｎｉ，ｎｊ）に対して式（６）を用いてリンクコストを計算した後、式（５）を用いて全リンクウェイトを計算し、ステップＳ２５に進む。
【０１２７】
次いで、ステップＳ２５では、計算されたすべてのパスの全リンクウェイトに基づいて最小の全リンクウェイトを有するパスを選択し、ステップＳ２６において、現在の処理対象のパケット信号は高優先度のパケット信号であるか否かが判断され、ＹＥＳのときはステップＳ２７に進む一方、ＮＯのときはステップＳ２９に進む。ステップＳ２７において、上記選択されたパスに属するノード無線局に対するＲＮＬテーブルの通信状態フラグ値を１にセットし、ステップＳ２８において上記選択されたパスに属するノード無線局に対する予約済みノードリスト情報を含むＲＮＬテーブルを、それを含むＲＮＬパケット信号により他のノード無線局に送信し、各ノード無線局のＲＮＬテーブルを更新させ、ステップＳ２９に進む。そして、ステップＳ２９において、発信無線局はＧＬＳテーブル内のルーチィング情報に基づいて上記選択されたパスを介して宛先無線局と通信し、ステップＳ３０において、現在の処理対象のパケット信号は高優先度のパケット信号であるか否かが判断され、ＹＥＳのときはステップＳ３１に進む一方、ＮＯのときは元のメインルーチンに戻る。ステップＳ３１では、通信終了後、ＧＬＳテーブル内の上記選択されたパスに含まれるノード無線局に対するＲＮＬテーブルの通信状態フラグ値を０にリセットし、上記選択されたパスに含まれるノード無線局に対する予約済みノードリスト情報を含むＲＮＬテーブルを、それを含むＲＮＬパケット信号により他のノード無線局に送信し、各ノード無線局のＲＮＬテーブルを更新させ、元のメインルーチンに戻る。
【０１２８】
図１３は、図１１のサブルーチンである、第２の実施形態に係るルーティング及び通信処理（ステップＳ１２）の処理を示すフローチャートである。図１３のフローチャートは、図１２のフローチャートに比較して、ステップＳ２２と、ステップＳ２６との間の処理が以下のように異なる。
【０１２９】
図１３において、ステップＳ２２でＹＥＳのときは、ステップＳ２３ＡにおいてＲＮＬテーブルを参照して各検索されたすべてのパスのうちで公知のディジクストラ（Dijkstra）方法を用いて最短のパスを選択し、ステップＳ２６に進む。ここで、ディジクストラ方法では、以下の手順によって最短パスを求める。
＜ステップＳＳ１＞発信無線局のラベルを０、それ以外のノード無線局のラベルを無限大とする。
＜ステップＳＳ２＞最短パスの長さが確定したノード無線局のラベルを確定ラベルとし、それ以外のノード無線局を一時ラベルと置き、次に、一時ラベルの中で最小の長さのノード無線局ｘを見つける。
＜ステップＳＳ３＞ステップＳＳ２で見つけた点を確定ラベルに変更し、隣接する点の一時ラベルを、「一時ラベルの値と、ノード無線局ｘのラベルの値とその間のリンクの重みを足したものの小さい方」の値に変更し、確定ラベルにする。
＜ステップＳＳ４＞上記ステップＳＳ１，ＳＳ２，ＳＳ３の処理を繰り返し、すべてのノード無線局が確定ラベルになったら当該最短パスの検索処理を終了する。その結果、各ノード無線局の確定ラベルが発信無線局からの最短パスの長さになっている。
【０１３０】
また、ステップＳ２２でＮＯであれば、ステップＳ２４Ａに進み、ＲＮＬテーブルを参照して各検索されたすべてのパスに対して以下の通り全リンクウェイトを計算する。すなわち、各リンク（ｎｉ，ｎｊ）に対して式（６）を用いてリンクコストを計算した後、式（５）を用いて全リンクウェイトを計算する。次いで、ステップＳ２５において、計算されたすべてのパスの全リンクウェイトに基づいて最小の全リンクウェイトを有するパスを選択した後、ステップＳ２６に進む。
【０１３１】
図１４は、図１１のサブルーチンである、第３の実施形態に係るルーティング及び通信処理（ステップＳ１２）の処理を示すフローチャートである。図１３のフローチャートは、図１２のフローチャートに比較して、以下のように異なることを特徴としている。
（１）ステップＳ２３の処理に代えて、ステップＳ２３Ｂの処理を実行することを特徴としている。ステップＳ２３Ｂでは、ＲＮＬテーブルを参照して各検索されたすべてのパスに対して以下の通り全リンクウェイトを計算する。各リンク（ｎｉ，ｎｊ）に対して式（８）を用いてリンクコストを計算した後、式（５）を用いて全リンクウェイトを計算する。
（２）ステップＳ２４の処理に代えて、ステップＳ２４Ｂの処理を実行することを特徴としている。ステップＳ２４Ｂでは、ＲＮＬテーブルを参照して各検索されたすべてのパスに対して以下の通り全リンクウェイトを計算する。各リンク（ｎｉ，ｎｊ）に対して式（９）を用いてリンクコストを計算した後、式（５）を用いて全リンクウェイトを計算する。
【実施例１】
【０１３２】
本発明者らは、本実施形態に係るルーティング方法及び無線通信システムについて、提案の効果を実証するため、指向性アンテナパターンとして電子制御導波器アレーアンテナ装置（例えば、非特許文献１４及び１５参照。）を使用する提案のルーティングプロトコルを公知のクアルネット（Qualnet）シミュレータ上で実行する。シミュレーションに使用するシミュレーション環境の特定事項及びパラメータを、表１に示す。
【０１３３】
【表１】
2005260478.tif 000003
【０１３４】
６つの通信フロー（フローＦ１乃至フローＦ６という。）によって、以下の方法を用いる。
（ｉ）ネットワークにはフローＦ１しか存在せず、最短パスを選択する場合（図２の「単フローとしてのフローＦ１」の場合）。
（ii）ネットワーク内でフローＦ１が他の５つのフロー（フローＦ２乃至フローＦ６）の存在下で通信していて、優先度なしで、従って、すべてのフローが互いに干渉し合う可能性のある最短パスを選択する場合（図１６の「優先度なしのフローＦ１」の場合）。
（iii）優先度有りでサービスの差別化方法を採用する場合。
【０１３５】
ここで、フローＦ１には高い優先度が割り当てられ、従って、これは最短パスを辿る。さらに、フローＦ１はそのルート上の各ノード無線局の周辺に指向性ゾーンを確保するため、他の５つの高優先度フローは結果的にフローＦ１が確保したゾーンを避けて適応的にパスを選択する。この方法におけるフローＦ１のスループットは、図１６の「高優先度のフローＦ１」として示されている。
【０１３６】
最初のケース（ｉ）では、フローＦ１のスループットが最大であることが観察されるが、これは、他のノード無線局のフローもこれを妨害又は干渉する原因にならないという事実の明らかな帰結である。第２のケース（ii）では、すべてのフローが最短パスを使用していることから、これらのルート間のルート結合の存在がフローＦ１のスループットを劇的に低減させる。しかしながら、第３のケース（iii）では、フローＦ１に高優先度が割り当てられ、提案プロトコルによってルートが選択されるとすぐに、フローＦ１のスループットは最初のケースとほぼ同じである著しい向上を示す。
【０１３７】
また、上述の状況下の５つの低優先度フロー（すなわち、フローＦ２乃至フローＦ６）の平均スループットについても観察した。図１７は、フローＦ１に優先性が与えられると、５つの低優先度通信の平均スループットはフローＦ１に優先性が与えられない場合の対応する平均スループットよりも少し下がることを示している。低優先度フローは高優先度ゾーンを回避して、このゾーンから離れたルートを選択する。従って、低優先度フローはより多いホップを経て宛先無線局に到達せざるを得ない可能性があるが、遭遇する干渉は少なくなる。これは、図１７における５つの低優先度フローの平均スループットの僅かな低下を説明している。
【０１３８】
また、パフォーマンスの向上が同じく保証されるかどうかを明らかにするために、本優先方法を高い移動度（各ノード無線局で０乃至１５ｍ／秒）の下で調査した。図１８は、通信数が６の方法では、フローＦ１に高優先度を与えれば、性能はフローＦ１に優先度を与えない場合より向上することを示している。同様に、低優先度トラフィックの場合も、シミュレーション結果は、優先方法を採用すれば５つの低優先度フロー（フローＦ２乃至フローＦ６）の平均スループットの品質低下は僅かであることを示している。
【０１３９】
最後に、ネットワークの容量を高優先度トラフィックの処理に関連して、すなわち、ネットワークが高優先度フローを幾つまで効率的に処理し得るか、について調査した。この調査を実行するため、合計６つの通信フローを処理するネットワークにおいて、高優先度フローの通信の数を１つから４つへと漸次増加させた。高優先度フローの通信の平均スループットは、高優先度フローの数の増加に伴ってその向上度の段階的低減を示し（図１９）、優先度を与えてネットワーク内で４つの高優先度フローの通信が可能である場合でも、平均スループットは下がるという結果がでている。
【０１４０】
ネットワークが効率的に処理し得る高優先度フローの通信の数は、基本的には次の要素に依存している。
（ｉ）指向性ビームの送信ビーム幅β及び送信レンジＲ（定義１参照。）。
（ii）ネットワーク内の同時的な高優先度フローの数及び低優先度フローの数。
【０１４１】
高優先度フローによりそのルートに沿った各ホップにおいて予約されるゾーンは、本質的には指向性ビームのビーム幅β及び送信レンジＲに依存する。従って、各高優先度フローによって採用される平均ホップ数をＨと仮定すれば、所定の面積Ａ内に形成可能な重複しない高優先度ゾーンの最大数は、（２・Ａ）／（β・Ｒ２・Ｈ）に等しい。
【０１４２】
ここで、ビーム幅β＝６０゜、送信レンジＲ＝３００ｍ（電子制御導波器アレーアンテナ装置の場合）、高優先度フローが採用する平均ホップ数、すなわち、ホップ計数値Ｈ＝５及び面積Ａ＝１５００×１５００ｍ２とすると、重複しない高優先度ゾーンの理論上の最大可能数は約１０になる。ここで、指向性ビームのサイドローブ及び不規則形状の存在に起因して、各ホップにおいて電子制御導波器アレーアンテナ装置が実際にカバーするゾーンは、６０゜の幾何学的ビームがカバーする面積より遙かに広い。その結果、このように広いビームパターンで（上述の式で得られるような）１０もの重複しない高優先度ゾーンを包含することは不可能である。これは、図１９において、他の低優先度フローを凌いでネットワーク内に効率的に包含され得る高優先度送信数が最大で３である理由を説明している。指向性ビームのビーム幅及び送信レンジを縮小すれば、所定の面積内により多くの高優先度ゾーンを包含することができる。そうでなければ、高優先度フローの通信数の増加に伴って重複するゾーンが発生し、これらが互いに干渉し合って優先度ベースの方法の性能が損なわれる。
【０１４３】
さらに、ネットワーク内で高優先度フローの数が増大すると、低優先度フローは高優先度ゾーンを避けてルートを発見することが困難になる。その結果、低優先度フローは高優先度ゾーンを通るルートを取ることを余儀なくされ、干渉を発生させる。これは、システム内のこうした低優先度フローを一時的にブロックすることによって制御可能であるが、未だこうした呼のブロッキングを実施したことはない。
【０１４４】
さらに、複数の高優先度フローのスループットは、これらが実際には最短パスではなく互いとの関連でゾーン非連結性を最大化されたパスを辿ることから低下する可能性がある。従って、高優先度フローの終端間遅延は増大する可能性があり、高優先度のスループットの品質低下を招く。
【０１４５】
以上説明したように、本実施形態では、高優先度フローのトラフィックに干渉のない通信を提供する目的で、優先度を付したルーティングに向けたゾーン予約を基礎とするメカニズムを提案した。従って、従来技術に比較して、より高い優先度フローのトラフィックに対して干渉の無い通信を実現でき、より高い優先度フローのエンドツーエンドの平均遅延時間を低下させるとともに、スループットを向上できる。
【０１４６】
以上の実施形態においては、優先度レベルを高優先度と低優先度の２つのレベルとしているが、本発明はこれに限らず、３つ以上の複数の優先度レベルを設定してもよい。
【図面の簡単な説明】
【０１４７】
【図１】本発明に係る実施形態であるアドホック無線ネットワークを構成する複数の無線局１−１乃至１−９の平面配置図である。
【図２】図１の各無線局１の内部構成を示すブロック図である。
【図３】図１の可変ビームアンテナ１０１のセクタービームパターンの一例を示す図である。
【図４】図１のアドホック無線ネットワークにおいて用いられるパケットデータのフォーマットを示す図である。
【図５】図２のデータベースメモリ１５４において格納される方位角及び信号強度レベルテーブル（ＡＳテーブル）の一例を示す表である。
【図６】図２のデータベースメモリ１５４に格納される隣接リンク状態テーブル（ＮＬＳテーブル）の一例を示す図である。
【図７】図２のデータベースメモリ１５４に格納される予約済みノード無線局テーブル（ＲＮＬテーブル）の一例を示す図である。
【図８】図２のデータベースメモリ１５４に格納されるグローバルリンク状態テーブル（ＧＬＳテーブル）の一例を示す図である。
【図９】図１のアドホック無線ネットワークにおいて用いられるトーン信号とパケット信号の送受信処理を示すタイミングチャートである。
【図１０】図１のアドホック無線ネットワークにおいて用いられる各無線局での放射パターンの種類と無線通信プロトコルを示すタイミングチャートである。
【図１１】図２の無線局１の管理制御部１０５によって実行されるパケット送受信制御処理を示すフローチャートである。
【図１２】図１１のサブルーチンである、第１の実施形態に係るルーティング及び通信処理（ステップＳ１２）の処理を示すフローチャートである。
【図１３】図１１のサブルーチンである、第２の実施形態に係るルーティング及び通信処理（ステップＳ１２）の処理を示すフローチャートである。
【図１４】図１１のサブルーチンである、第３の実施形態に係るルーティング及び通信処理（ステップＳ１２）の処理を示すフローチャートである。
【図１５】従来技術のアドホック無線ネットワークにおける発信無線局Ｓと宛先無線局Ｄと間でのマルチパスルーティングを示す平面図である。
【図１６】本発明に係る実施形態のシミュレーション結果であって、６個の通信が存在するときに、異なった優先度が割り当てられたときに特定の１つのフローＦ１についての平均スループットを示すグラフである。
【図１７】本発明に係る実施形態のシミュレーション結果であって、６個の通信が存在するときに、１つのフローＦ１に対して優先度を割り当てたときと、割り当てないときの平均スループットを示すグラフである。
【図１８】本発明に係る実施形態のシミュレーション結果であって、６個の通信が存在するときに、高い移動度（０乃至１５ｍ／秒）の条件で高優先度のフローと低優先度のフローについての平均スループットを示すグラフである。
【図１９】本発明に係る実施形態のシミュレーション結果であって、６個の通信が存在するときに、高優先度のフローの通信数の増大に対する平均スループットを示すグラフである。
【符号の説明】
【０１４８】
１，１−１乃至１−９，Ｎ１乃至Ｎ４…ノード無線局、
Ｓ１，Ｓ２…発信無線局、
Ｄ１，Ｄ２…宛先無線局、
１０１…可変ビームアンテナ、
１０２…サーキュレータ、
１０３…指向制御部、
１０４…パケット送受信部、
１０５…トラヒックモニタ部、
１０６…回線制御部、
１０７…上位レイヤ処理装置、
１３０…パケット受信部、
１３１…高周波受信機、
１３２…復調器、
１３３…受信バッファメモリ、
１４０…パケット送信部、
１４１…送信タイミング制御部、
１４２…送信バッファメモリ、
１４３…変調器、
１４４…高周波送信機、
１５１…管理制御部、
１５２…検索エンジン、
１５３…更新エンジン、
１５４…データベースメモリ、
１５５…クロック回路、
１６０…拡散符号発生器。
【図１】
2005260478.tif 000004
【図２】
2005260478.tif 000005
【図３】
2005260478.tif 000006
【図４】
2005260478.tif 000007
【図５】
2005260478.tif 000008
【図６】
2005260478.tif 000009
【図７】
2005260478.tif 000010
【図８】
2005260478.tif 000011
【図９】
2005260478.tif 000012
【図１０】
2005260478.tif 000013
【図１１】
2005260478.tif 000014
【図１２】
2005260478.tif 000015
【図１３】
2005260478.tif 000016
【図１４】
2005260478.tif 000017
【図１５】
2005260478.tif 000018
【図１６】
2005260478.tif 000019
【図１７】
2005260478.tif 000020
【図１８】
2005260478.tif 000021
【図１９】
2005260478.tif 000022