JP2004282244A

JP2004282244A - Routing method and wireless communication system for wireless network

Info

Publication number: JP2004282244A
Application number: JP2003068548A
Authority: JP
Inventors: Tetsuo Ueda; 哲郎植田; Bandyopadhyay Somprakash; ソンプラカッシュ・バンディオパダイ; Kazuo Hasuike; 和夫蓮池
Original assignee: ATR Advanced Telecommunications Research Institute International
Current assignee: ATR Advanced Telecommunications Research Institute International
Priority date: 2003-03-13
Filing date: 2003-03-13
Publication date: 2004-10-07
Anticipated expiration: 2023-03-13
Also published as: JP3946652B2

Abstract

【課題】無線ネットワークにおいてエンド・ツー・エンドの遅延時間を大幅に短縮する。
【解決手段】複数の無線局間のリンク状態を表す情報テーブルに基づいて、発信元無線局と宛先無線局との間で共通の無線局を中継局として含まない複数のパスを検索し、検索された複数のパス上の無線局を無線通信中の無線局として設定する。各パス上の各無線局のサービスエリア内に存在する他の通信中の無線局の個数を計算し、計算された通信中の無線局の個数を各パス毎に加算することによって、各パスに対する当該パスに含まれない他の通信中の無線局との間の結合を表す相関係数を計算し、計算した各パスに対する相関係数にホップ数を乗算してルーティング基準指数を計算し、最大の基準指数を有するパスに含まれる無線局を通信中でない無線局として設定する。上記処理を繰り返し、より小さい２個の基準指数を有する１対のパスを選択してルーティングする。
【選択図】図８An object of the present invention is to significantly reduce end-to-end delay time in a wireless network.
Based on an information table representing a link state between a plurality of wireless stations, a plurality of paths between a source wireless station and a destination wireless station that do not include a common wireless station as a relay station are searched. The wireless stations on the plurality of paths thus set are set as wireless stations performing wireless communication. By calculating the number of other communicating wireless stations present in the service area of each wireless station on each path, and adding the calculated number of communicating wireless stations for each path, Calculate a correlation coefficient representing a coupling with another communicating radio station not included in the path, calculate a routing reference index by multiplying the calculated correlation coefficient for each path by the number of hops, and The wireless station included in the path having the reference index is set as a wireless station that is not communicating. The above process is repeated to select and route a pair of paths having two smaller reference indices.
[Selection] Fig. 8

Description

【０００１】
【発明の属する技術分野】
本発明は、複数の無線局を備えた、例えば無線ＬＡＮなどの無線ネットワークにおいてパケット通信を行う、例えばアドホック無線ネットワークなどの無線ネットワークのためのルーティング方法及び無線通信システムに関する。
【０００２】
【従来の技術】
一時的に特定の地域内に集まった不特定多数の人々の間の通信を無線回線を用いてサポートするアドホック無線ネットワークでは、例えばインターネットのルータ装置のようなインフラストラクチャが存在しないために、ネットワーク中のユーザが協調してパケットを中継し、ルーティングを行う必要がある。
【０００３】
アドホック無線ネットワークのルーティング方式は通常、複数のユーザ端末の無線局を介した単一パスによるルーティングを採用している。しかしながら、例えば、非特許文献１に開示されたように、いったん発信元無線局と宛先無線局との間に複数のパスにてなるセットが発見されれば、データの総容量を複数の個別のブロックに分割してこれらを選択された複数のパスを介して発信元無線局から宛先無線局へ送信することにより、エンド・ツー・エンドの遅延時間を改善することが可能な場合があり、これによって最終的にネットワークの輻輳とエンド・ツー・エンドの遅延時間とを低減することができ、このようなルーティングを「マルチパスルーティング」という。
【０００４】
エム・アール・パールマン（Ｍ．Ｒ．Ｐｅａｒｌｍａｎ）らは、非特許文献２において、マルチパスルーティングがネットワーク負荷をバランス化させることができる点を実証している。非特許文献３で提案されている分割マルチパスルーティング（ＳｐｌｉｔＭｕｌｔｉ−ｐａｔｈＲｏｕｔｉｎｇ；ＳＭＲ）は、各パス間の分離の程度を最大化した複数のパスの構築及び保持に注目している。非特許文献４では、発信元無線局と宛先無線局の間に位置した複数のパス間の相関係数の概念を導入している。
【０００５】
また、非特許文献５では、アドホック無線ネットワークのためのＭＡＣ及びルーティングプロトコルが開示され、この開示内容では、各無線局は周期的にその隣接情報を収集し、各無線局における隣接リンク状態テーブル（ＮｅｉｇｈｂｏｒｈｏｏｄＬｉｎｋＳｔａｔｅＴａｂｌｅ（ＮＬＳＴ））を作成する。非特許文献６では、オーバーヘッドを増大させずにネットワークのトポロジー情報を収集するための方法が開示されている。非特許文献７では、この局所的な情報の周期的な伝搬に基づいて、修正されたリンク状態ルーティングプロトコルを構成した。その目的は、非特許文献８にあるように、ネットワークトポロジーにおけるその無線局を認識させることにある。
【０００６】
さらに、非特許文献９は、アドホック無線ネットワークなどの無線ネットワークにおいて、無線局が頻繁に移動しても、ルーティングテーブルを効率的に更新することができ、安定なルートを確保して安定な無線通信を行うことができる無線ネットワークのためのルーティング方法及びルータ装置を開示している。また、特許文献１、非特許文献１０及び１１は、非特許文献９のようなアドホック無線ネットワーク中の各無線局において使用可能な指向性アンテナを開示している。
【０００７】
【特許文献１】
特開２００１−２４４３１号公報。
【非特許文献１】
Ｓ．Ｋ．Ｄａｓｅｔａｌ．， ”ＩｍｐｒｏｖｉｎｇＱｕａｌｉｔｙ−ｏｆ−ＳｅｒｖｉｃｅｉｎＡｄｈｏｃＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋｓｗｉｔｈＡｄａｐｔｉｖｅＭｕｌｔｉ−ｐａｔｈＲｏｕｔｉｎｇ”，ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＧＬＯＢＥＣＯＭ２０００，ＳａｎＦｒａｎｃｉｓｃｏ，Ｃａｌｉｆｏｒｎｉａ，Ｎｏｖｅｍｂｅｒ２７−Ｄｅｃｅｍｂｅｒ１，２０００。
【非特許文献２】
Ｍ．Ｒ．Ｐｅａｒｌｍａｎｅｔａｌ．， ”ＯｎｔｈｅＩｍｐａｃｔｏｆＡｌｔｅｒｎａｔｅＰａｔｈＲｏｕｔｉｎｇｆｏｒＬｏａｄＢａｌａｎｃｉｎｇｉｎＭｏｂｉｌｅＡｄＨｏｃＮｅｔｗｏｒｋｓ”，Ｍｏｂｉｈｏｃ２０００，ｐ．１５０，３−１０，２０００。
【非特許文献３】
Ｓ．Ｊ．Ｌｅｅｅｔａｌ．， ”ＳｐｌｉｔＭｕｌｔｉ−ｐａｔｈＲｏｕｔｉｎｇｗｉｔｈＭａｘｉｍａｌｌｙＤｉｓｊｏｉｎｔＰａｔｈｓｉｎＡｄＨｏｃＮｅｔｗｏｒｋｓ”，ＩＣＣ２００１。
【非特許文献４】
ＫｕｉＷｕｅｔａｌ．， ”Ｏｎ−ＤｅｍａｎｄＭｕｌｔｉｐａｔｈＲｏｕｔｉｎｇｆｏｒＭｏｂｉｌｅＡｄＨｏｃＮｅｔｗｏｒｋｓ”，ＥＰＭＣＣ２００１，Ｖｉｅｎｎａ，２０ｔｈ−２２ｎｄＦｅｂｒｕａｒｙ２００１。
【非特許文献５】
Ｓ．Ｂａｎｄｙｏｐａｄｈｙａｙｅｔａｌ．， ”ＡｎＡｄａｐｔｉｖｅＭＡＣＰｒｏｔｏｃｏｌｆｏｒＷｉｒｅｌｅｓｓＡｄＨｏｃＣｏｍｍｕｎｉｔｙＮｅｔｗｏｒｋ（ＷＡＣＮｅｔ）ＵｓｉｎｇＥｌｅｃｔｒｏｎｉｃａｌｌｙＳｔｅｅｒａｂｌｅＰａｓｓｉｖｅＡｒｒａｙＲａｄｉａｔｏｒＡｎｔｅｎｎａ”，ＰｒｏｃｅｅｄｉｎｇｓｏｆＧＬＯＢＥＣＯＭ２００１，Ｎｏｖｅｍｂｅｒ２５−２９，ＳａｎＡｎｔｏｎｉｏ，Ｔｅｘａｓ，ＵＳＡ。
【非特許文献６】
Ｓ．Ｂａｎｄｙｏｐａｄｈｙａｙｅｔａｌ．， ”ＴｏｐｏｌｏｇｙＤｉｓｃｏｖｅｒｙｉｎＡｄＨｏｃＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋｓＵｓｉｎｇＭｏｂｉｌｅＡｇｅｎｔｓ”，ＰｒｏｃｅｅｄｉｎｇｓｏｆＭＡＴＡ２０００，Ｐａｒｉｓ。
【非特許文献７】
Ｓ．Ｂａｎｄｙｏｐａｄｈｙａｙｅｔａｌ．， ”ＡｎＡｄａｐｔｉｖｅＭＡＣａｎｄＤｉｒｅｃｔｉｏｎａｌＲｏｕｔｉｎｇＰｒｏｔｏｃｏｌｆｏｒＡｄＨｏｃＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋＵｓｉｎｇＤｉｒｅｃｔｉｏｎａｌＥＳＰＡＲＡｎｔｅｎｎａ”，ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＡＣＭＳｙｍｐｏｓｉｕｍｏｎＭｏｂｉｌｅＡｄＨｏｃＮｅｔｗｏｒｋｉｎｇ＆Ｃｏｍｐｕｔｉｎｇ２００１（ＭＯＢＩＨＯＣ２００１），ＬｏｎｇＢｅａｃｈ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，４−５Ｏｃｔｏｂｅｒ，２００１。
【非特許文献８】
Ｒ．ＲｏｙＣｈｏｕｄｈｕｒｙｅｔａｌ．， ”ＡＤｉｓｔｒｉｂｕｔｅｄＭｅｃｈａｎｉｓｍｆｏｒＴｏｐｏｌｏｇｙＤｉｓｃｏｖｅｒｙｉｎＡｄｈｏｃＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋｓｕｓｉｎｇＭｏｂｉｌｅＡｇｅｎｔｓ”，ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＦｉｒｓｔＡｎｎｕａｌＷｏｒｋｓｈｏｐＯｎＭｏｂｉｌｅＡｄＨｏｃＮｅｔｗｏｒｋｉｎｇ＆Ｃｏｍｐｕｔｉｎｇ２００１（ＭＯＢＩＨＯＣ２０００），Ｂｏｓｔｏｎ，Ｍａｓｓａｃｈｕｓｅｔｔｓ，ＵＳＡ，Ａｕｇｕｓｔ１１，２０００。
【非特許文献９】
昌山一成ほか，「無線アドホックネットワークにおけるＤｉｒｅｃｔｉｏｎａｌルーティングプロトコルの提案」，電子情報通信学会通信ソサイエティ大会講演論文集，Ｂ−５−２０７，電子情報通信学会発行，２００１年９月。
【非特許文献１０】
Ｔ．Ｏｈｉｒａｅｔａｌ．， “Ｅｌｅｃｔｒｏｎｉｃａｌｌｙｓｔｅｅｒａｂｌｅｐａｓｓｉｖｅａｒｒａｙｒａｄｉａｔｏｒａｎｔｅｎｎａｓｆｏｒｌｏｗ−ｃｏｓｔａｎａｌｏｇａｄａｐｔｉｖｅｂｅａｍｆｏｒｍｉｎｇ，” ２０００ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＰｈａｓｅｄＡｒｒａｙＳｙｓｔｅｍ＆Ｔｅｃｈｎｏｌｏｇｙｐｐ．１０１−１０４，Ｄａｎａｐｏｉｎｔ，Ｃａｌｉｆｏｒｎｉａ，Ｍａｙ２１−２５，２０００。
【非特許文献１１】
田野哲ほか，”Ｍ−ＣＭＡ：マイクロ波信号処理による適応ビーム形成のためのデジタル信号処理アルゴリズム”，電子情報通信学会研究技術報告，ＡＰ９９−６２，ＳＡＴ９９−６２，ｐｐ．１５−２２，１９９９年７月。
【０００８】
【発明が解決しようとする課題】
しかしながら、発信元無線局と宛先無線局の間に複数のパスを採用することは、必ずしもエンド・ツー・エンドの遅延時間を縮小させる結果にはならないこともまた示されている。非特許文献２では、移動体アドホックネットワークにおける代替パスルーティング（ＡｌｔｅｒｎａｔｅＰａｔｈＲｏｕｔｉｎｇ；ＡＰＲ）の効果が検討され、ネットワークトポロジー及びチャンネル特性（例えば、ルート間結合）が、ＡＰＲの方法によって提供される利得を大幅に制限する場合があるということが議論されている。
【０００９】
仮に、ただ２つの発信元無線局ｓ_１及びｓ_２がそれぞれ、データパケットを宛先無線局ｄ_１及びｄ_２へ送信しようとしているとする。互いに異なるノード無線局ｘ_１，ｘ_２，ｙ_１及びｙ_２が存在し、これらのノード無線局を含む２つのパス｛ｓ_１−ｘ_１−ｙ_１−ｄ_１｝及び｛ｓ_２−ｘ_２−ｙ_２−ｄ_２｝を選択して通信する場合、互いに共通なノード無線局を含まないこれらのパスを、本願明細書ではノード無線局間分離であるという。ノード無線局間分離であるパス｛ｓ_１−ｘ_１−ｙ_１−ｄ_１｝及び｛ｓ_２−ｘ_２−ｙ_２−ｄ_２｝のそれぞれを介して伝送されるデータパケットのエンド・ツー・エンドの遅延時間は、互いに独立したものであるはずである。しかしながら、ノード無線局ｘ_１及びｘ_２及び／又はｙ_１及びｙ_２が互いに隣接していれば、２つの通信が同時に発生することは不可能である。なぜならば、データ通信の間のＲＴＳ／ＣＴＳ交換は、一度にノード無線局ｘ_１又はｘ_２の何れかのみ、同様にノード無線局ｙ_１又はｙ_２の何れかのみがデータパケットを送信することしか許容しないからである。従って、任意の発信元無線局及び宛先無線局間のエンド・ツー・エンドの遅延時間は、そのパス上のノード無線局の輻輳特性のみに依存するわけではない。隣接領域内の通信のパターンも、この遅延時間に寄与する。これが、ルート間結合（又はルートカップリング）として知られた現象である。ルート間結合は、２つのルートがデータ通信の間に互いに電波干渉し合うほど物理的に近接して配置された場合に発生する。
【００１０】
図１３は、従来技術に係るマルチパスルーティングであって、発信元無線局Ｓと宛先無線局Ｄとの間に２つのパスが存在するときに各パス間でルート間結合が生じていることを示す、各無線局及びルートの平面配置図である。ここで、無線局Ｓ及びＤ間において、無線局｛Ｓ，ｘ１，ｘ２，Ｄ｝にてなる第１のパスと、無線局｛Ｓ，ｙ１，ｙ２，Ｄ｝にてなる第２のパスとが存在し、各パスは無線局Ｓ及びＤ以外に共通のノードを持たず、本願明細書では、これらのパスもそれぞれ「ノード無線局間分離」であるという。従って、各パスを介するパケット伝送のエンド・ツー・エンドの遅延時間は互いに独立であるはずであるが、しかしながら、ノード無線局ｘ１及びｙ１は発信元無線局Ｓのサービスエリア（すなわち、無線信号の送信可能範囲のエリア）２１０内に存在し、かつそれぞれ互いに近接して位置しており、ノード無線局ｘ２及びｙ２は宛先無線局Ｄのサービスエリア２１１内に存在し、かつそれぞれ互いに近接して位置しているので、各パス間にルート間結合が存在している。このため、各パス上でパケットを同時に伝送することは不可能である。それだけではなく、これら２つのパスを用いたデータ伝送の性能は、単一のパスを用いたプロコトルのときよりも悪化する。
【００１１】
図１４は、従来技術に係るマルチパスルーティングであって、発信元無線局Ｓと宛先無線局Ｄとの間に、複数のルート間結合を含む２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝が存在するときの、パス上の各無線局の配置及びアンテナ放射パターンを示す平面図である。
【００１２】
図１４において、ノード無線局１ａ及び１ｄは発信元無線局Ｓからのサービスエリア２２０内に存在し、無線局Ｓ，１ｂ，１ｄ及び１ｅは、ノード無線局１ａからのサービスエリア２２１内に存在し、ノード無線局１ａ，１ｃ，１ｄ，１ｅ及び１ｆは、ノード無線局１ｂからのサービスエリア２２２内に存在している。このような場合、パス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝の間には、ノード無線局１ａと１ｄ間のリンク、ノード無線局１ａと１ｅの間のリンクなどで示されたようなルート間結合が存在し、これら２つのパスを用いたルーティングを妨げることになる。
【００１３】
図１５は、図１４の２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝を介してパケットを伝送するときのタイミングチャートである。実際に、図１４及び図１５を参照して、発信元無線局Ｓと宛先無線局Ｄとの間にルート間結合した２つのパスが存在するときに、各パス上のノード無線局が互いに電波干渉する様子をより詳しく説明する。各無線局は、無指向性アンテナを備えているものとする。
【００１４】
図１５を参照すると、発信元無線局Ｓは時間区間Ｔ_０においてデータパケットＰ_１をノード無線局１ａへ送信しており、ノード無線局１ａは次の時間区間Ｔ_１においてデータパケットＰ_１をノード無線局１ｂへ送信している。各無線局が無指向性アンテナを備えた場合、発信元無線局ＳはＴ_１の間、ノード無線局１ａからＲＴＳを受信しているためにアイドル状態を保持している必要がある。従って、発信元無線局Ｓはその第２のパケットＰ_２を時間区間Ｔ_２になって初めてノード無線局１ｄ（第２のパスの最初のノード無線局）へと送ることができる。図１５に示されたようなパケットの遷移では、宛先無線局Ｄはパケットを１つおきの時間区間で受信する。無線局ＳとＤとの間のパス数を２つよりも増やしたとしても状況は改善されない。
【００１５】
結果的には、無線局ＳとＤのペア間のマルチパス通信においては、これらの複数ルートにおけるノード無線局が絶えずこれらが共用する媒体へのアクセスを求めて競合している可能性があり、通信の性能はその無線局ＳとＤのペア間の単一のパスを介するルーティングの場合よりも悪くなることがある。従ってこのコンテキストでは、マルチパスを構成する複数のルートが互いにノード間分離であるということは性能改善の十分条件とはなり得ない。よって、非特許文献３及び４のような、ノード間分離であるルート又はノード間分離の程度を最大化させたルートを発見しようとする努力は、ルート間結合に起因して効果的ではない場合がある。従って、アドホック無線ネットワークにおいてマルチパスルーティングを実行するときに、エンド・ツー・エンドの遅延時間を短縮させるためのより効果的な方法を提供することが望ましい。
【００１６】
本発明の目的は以上の問題点を解決し、アドホック無線ネットワークなどの無線ネットワークにおいて、従来技術に比較して、エンド・ツー・エンドの遅延時間を大幅に短縮することができる無線ネットワークのためのルーティング方法及び無線通信システムを提供することにある。
【００１７】
【課題を解決するための手段】
第１の発明に係る無線ネットワークのためのルーティング方法は、複数の無線局を備え、各無線局間で無線通信を行う無線ネットワークのためのルーティング方法において、
上記複数の無線局間のリンク状態を表す情報テーブルに基づいて、発信元の無線局と宛先の無線局との間で、少なくとも１つの無線局を中継局として含みかつ互いに共通の無線局を中継局として含まない複数のパスを検索する第１のステップと、
上記無線ネットワークにおいて、上記検索された複数のパス上の無線局を無線通信中の無線局として仮定して設定する第２のステップと、
上記設定された無線通信中の無線局に基づいて、上記各パス上の上記各無線局のサービスエリア内に存在する他の通信中の無線局の個数を計算し、上記計算された通信中の無線局の個数を上記各パス毎に加算することによって、上記各パスに対する、当該パス自体に含まれない他の通信中の無線局との間の電波干渉性に関する結合の度合いを表す相関係数を計算し、上記計算した各パスに対する相関係数に当該パスのホップ数を乗算することにより、他の通信中の無線局から電波干渉無く離間しかつ最短のパスを検索するためのルーティング基準指数を計算する第３のステップと、
上記計算された各パスに対するルーティング基準指数のうち、最大の基準指数を有するパスに含まれる無線局を通信中でない無線局として設定する第４のステップと、
上記第３及び第４のステップを繰り返し、より小さい２個の基準指数を有する１対のパスを上記発信元の無線局と宛先の無線局との間の２個のパスとして選択し、上記選択した２個のパスを用いてルーティングする第５のステップとを含むことを特徴とする。
【００１８】
また、第２の発明に係る無線通信システムは、複数の無線局を備え、各無線局間で無線通信を行う無線ネットワークのための無線通信システムにおいて、
上記複数の無線局間のリンク状態を表す情報テーブルに基づいて、発信元の無線局と宛先の無線局との間で、少なくとも１つの無線局を中継局として含みかつ互いに共通の無線局を中継局として含まない複数のパスを検索し、
上記無線ネットワークにおいて、上記検索された複数のパス上の無線局を無線通信中の無線局として仮定して設定し、
上記設定された無線通信中の無線局に基づいて、上記各パス上の上記各無線局のサービスエリア内に存在する他の通信中の無線局の個数を計算し、上記計算された通信中の無線局の個数を上記各パス毎に加算することによって、上記各パスに対する、当該パス自体に含まれない他の通信中の無線局との間の電波干渉性に関する結合の度合いを表す相関係数を計算し、上記計算した各パスに対する相関係数に当該パスのホップ数を乗算することにより、他の通信中の無線局から電波干渉無く離間しかつ最短のパスを検索するためのルーティング基準指数を計算し、
上記計算された各パスに対するルーティング基準指数のうち、最大の基準指数を有するパスに含まれる無線局を通信中でない無線局として設定し、
上記各パスに対してルーティング基準指数を計算する処理と、上記最大の基準指数を有するパスに含まれる無線局を通信中でない無線局として設定する処理とを繰り返し、より小さい２個の基準指数を有する１対のパスを上記発信元の無線局と宛先の無線局との間の２個のパスとして選択し、上記選択した２個のパスを用いてルーティングするように制御する制御手段を備えたことを特徴とする。
【００１９】
さらに、第３の発明に係る無線ネットワークのためのルーティング方法は、複数の無線局を備え、各無線局間で無線通信を行う無線ネットワークのためのルーティング方法において、
上記複数の無線局間のリンク状態を表す情報テーブルに基づいて、発信元の無線局と宛先の無線局との間で、少なくとも１つの無線局を中継局として含みかつ互いに共通の無線局を中継局として含まない複数のパスを検索するステップと、上記無線ネットワークにおいて、上記検索された複数のパスのうちの各１対のバス上の無線局を通信中の無線局として仮定して設定し、上記各１対のパス上の上記各無線局のサービスエリア内に存在する他の通信中の無線局の個数を計算し、上記計算された通信中の無線局の個数を上記各１対のパス毎に加算することによって、上記各１対のパスに対する、当該パス自体に含まれない他の通信中の無線局との間の電波干渉性に関する結合の度合いを表す相関係数を計算し、上記計算した各１対のパスに対する相関係数に当該パスのホップ数を乗算することにより、他の通信中の無線局から電波干渉無く離間しかつ最短のパスを検索するための上記各１対のパスに対するルーティング基準指数を計算するステップと、
上記計算した各１対のパスに対するルーティング基準指数のうち、より小さい２個の基準指数を有する１対のパスを上記発信元の無線局と宛先の無線局との間の２個のパスとして選択し、上記選択した２個のパスを用いてルーティングするステップとを含むことを特徴とする。
【００２０】
またさらに、第４の発明に係る無線通信システムは、複数の無線局を備え、各無線局間で無線通信を行う無線ネットワークのための無線通信システムにおいて、
上記複数の無線局間のリンク状態を表す情報テーブルに基づいて、発信元の無線局と宛先の無線局との間で、少なくとも１つの無線局を中継局として含みかつ互いに共通の無線局を中継局として含まない複数のパスを検索し、
上記無線ネットワークにおいて、上記検索された複数のパスのうちの各１対のバス上の無線局を通信中の無線局として仮定して設定し、上記各１対のパス上の上記各無線局のサービスエリア内に存在する他の通信中の無線局の個数を計算し、上記計算された通信中の無線局の個数を上記各１対のパス毎に加算することによって、上記各１対のパスに対する、当該パス自体に含まれない他の通信中の無線局との間の電波干渉性に関する結合の度合いを表す相関係数を計算し、上記計算した各１対のパスに対する相関係数に当該パスのホップ数を乗算することにより、他の通信中の無線局から電波干渉無く離間しかつ最短のパスを検索するための上記各１対のパスに対するルーティング基準指数を計算し、
上記計算した各１対のパスに対するルーティング基準指数のうち、より小さい２個の基準指数を有する１対のパスを上記発信元の無線局と宛先の無線局との間の２個のパスとして選択し、上記選択した２個のパスを用いてルーティングするように制御する制御手段を備えたことを特徴とする。
【００２１】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態について説明する。
【００２２】
＜第１の実施形態＞
図１は、本発明に係る第１の実施形態であるアドホック無線ネットワークの構成を示す複数の無線局１−１乃至１−９（総称して、符号１を付す。）の平面配置図であり、図２は、図１の各無線局１の構成を示すブロック図である。
【００２３】
この実施形態の無線通信システムでは、図１に示すように、複数の無線局１が平面的に散在して存在し、各無線局１はそれぞれ、可変ビームアンテナ１０１の利得や送信電力、受信感度などのパラメータで決定される所定のサービスエリアを有し、このサービスエリア内でパケット通信を行うことができ、サービスエリア外の無線局１とパケット通信を行うときは、サービスエリア内の無線局１を中継局として用いてパケットデータを中継することにより、所望の宛先無線局１にパケットデータを伝送する。すなわち、各無線局１は、パケットのルーティングを行うルータ装置を備え、発信元無線局、中継局、又は宛先無線局として動作する。
【００２４】
この実施形態の無線通信システムは、例えば無線ＬＡＮなどのアドホック無線ネットワークのパケット通信システムに適用するものであって、無指向性放射パターンであるオムニパターンと、自局を中心とした水平面内の所定の方位角毎にセクタ形状のメインビームを選択的に変更可能なセクタビームパターンと、上記方位角毎にヌル点を形成可能な排他的セクタパターンとを選択的に切り換え可能な可変ビームアンテナ１０１を備え、
（ａ）自局からのＲＱ（Ｒｅｑｕｅｓｔ）信号を隣接無線局が受信したときの信号電力対干渉雑音電力比（以下、ＳＩＮＲという。）の測定値を含む隣接無線局からのＲＥ（Ｒｅｐｌｙ）信号に基づいて予め取得された、自局を中心とした水平面内の所定の方位角毎のサービスエリア内の無線局１から見たＳＩＮＲに基づいて、各隣接無線局毎に最大のＳＩＮＲを選択して各隣接無線局との親和度とし、当該親和度と、それに対応する方位角及びそのデータの更新時刻とを含む隣接リンク状態テーブル（ＮｅｉｇｈｂｏｒＬｉｎｋ−ＳｔａｔｅＴａｂｌｅ）（以下、ＮＬＳテーブルという。）と、
（ｂ）各無線局間でＮＬＳテーブルのトポロジー情報（アドホック無線ネットワーク内のすべての無線局間のリンク状態を示す経路情報をいい、以下同様である。）を交換することにより、当該アドホック無線ネットワーク内のすべての無線局１に関するＮＬＳテーブルのトポロジー情報を収集し、このトポロジー情報（各無線局１間のリンク状態を含む）と、これにおける各無線局毎の当該トポロジー情報の更新回数と、その時点で任意の通信プロセスに関わる無線局１を示す通信状態フラグ値とを含むグローバルリンク状態テーブル（ＧｌｏｂａｌＬｉｎｋＳｔａｔｅＴａｂｌｅ）（以下、ＧＬＳテーブルという。）と
をデータベースメモリ１５４に格納し、ＮＬＳテーブル及びＧＬＳテーブルとに基づいて、可変ビームアンテナ１０１の放射パターンを制御しながらパケット信号のルーティングを行うことを特徴としている。
【００２５】
特に、各無線局１において、
（１）ＧＬＳテーブルに基づいて、発信元無線局Ｓと宛先無線局Ｄとの間で、それぞれ少なくとも１つの無線局を中継局として含み、かつ互いに共通の無線局を中継局として含まないノード間分離である複数のパスを検索するステップと、
（２）無線ネットワークにおいて通信中の無線局を示す通信状態フラグ値において、上記検索された複数のパス上の無線局を通信中の無線局として設定するステップと、
（３）上記通信状態フラグ値に基づいて、上記各パス上の上記各無線局の無線信号の到達範囲内に存在する他の通信中の無線局の個数を計算し、上記計算された通信中の無線局の個数を上記パス毎に加算することによって、上記各パスに対する、当該パス自体に含まれない他の通信中の無線局との間の電波干渉性に関する結合の度合いを表す相関係数を計算し、上記各パスに対する結合の相関係数に当該パスのホップ数を乗算することにより、他の通信中の無線局から電波干渉無く離間しかつ最短のパスを発見するためのルーティング基準指数γを計算するステップと、
（４）上記通信状態フラグ値において、上記基準指数が最も大きいパスに含まれる無線局を通信中でない無線局として設定するステップと、
（５）上述された（３）と（４）のステップを繰り返し、上記ルーティング基準指数γがより小さい２個のパスを発信元無線局Ｓと宛先無線局Ｄとの間のパスとして選択し、選択されたパスを用いてルーティングするステップとを実行する。
【００２６】
次いで、図２を参照して、各無線局１の装置構成について説明する。図２において、無線局１は、可変ビームアンテナ１０１と、その指向性を制御するための指向制御部１０３と、サーキュレータ１０２と、データパケット送信部１４０及びデータパケット受信部１３０を有するデータパケット送受信部１０４と、トラヒックモニタ部１０５と、回線制御部１０６と、上位レイヤ処理部１０７とを備える。
【００２７】
送受信すべきデータを処理する上位レイヤ処理装置１０７によって発生されたパケット形式の通信用送信信号データは、送信バッファメモリ１４２を介して変調器１４３に入力され、変調器１４３は、所定の無線周波数の搬送波信号を、拡散符号発生器１６０でＣＤＭＡ方式で発生された所定の通信チャネル用拡散符号を用いて、入力された通信用送信信号データに従ってスペクトル拡散変調して、変調後の送信信号を高周波送信機１４４に出力する。高周波送信機１４４は入力された送信信号に対して増幅などの処理を実行した後、サーキュレータ１０２を介して可変ビームアンテナ１０１から他の無線局１に向けて送信する。一方、可変ビームアンテナ１０１で受信されたパケット形式の通信チャネル用受信信号は、サーキュレータ１０２を介して高周波受信機１３１に入力され、高周波受信機１３１は入力された受信信号に対して低雑音増幅などの処理を実行した後、復調器１３２に出力する。復調器１３２は、入力される受信信号を、拡散符号発生器１６０でＣＤＭＡ方式で発生された通信チャネル用拡散符号を用いて、スペクトル逆拡散により復調して、復調後の受信信号データを上位レイヤ処理装置１０７に出力するとともに、トラヒックモニタのためにトラヒックモニタ部１０５に出力する。
【００２８】
本実施形態においては、指向性アンテナである可変ビームアンテナ１０１は、複数のアンテナ素子とその指向性を制御する制御部１０３に接続され、
（ａ）無指向性放射パターンであるオムニパターンと、
（ｂ）例えば図３に示すように、自局を中心とした水平面内の所定の方位角毎にセクタ形状のメインビームを選択的に変更可能なセクタビームパターンと、
（ｃ）上記方位角毎にヌル点を形成可能な排他的セクタパターンと
を電気的な制御により選択的に切り換え可能なアンテナである。なお、可変ビームアンテナ１０１については、例えば、公知のフェーズドアレーアンテナ装置であってもよいし、もしくは、特許文献１又は非特許文献１１に開示された可変ビームアンテナであってもよい。
【００２９】
トラヒックモニタ部１０５は、検索エンジン１５２と、更新エンジン１５３と、データベースメモリ１５４と、クロック回路１５５とを備え、後述のルーティング及び通信処理を実行するとともに、無線局１が他の無線局１とのパケット通信において使用すべき通信チャネルを決定して、決定した通信チャネルに対応する拡散符号の指定データを回線制御部１０６を介して拡散符号発生器１６０に送ることにより、拡散符号発生器１６０が当該指定データに対応する拡散符号を発生するように制御するとともに、決定した通信チャネルに対応するタイムスロットの指定データを回線制御部１０６を介して送信タイミング制御部１４１に送ることにより、送信タイミング制御部１４１が送信バッファメモリ１４２による通信チャネル用送信信号データの書き込み及び読み出しを制御することにより通信チャネル用送信信号が対応するタイムスロットで送信されるように制御する。なお、クロック回路１５５は、現在日時を計時してその情報を、必要に応じて管理制御部１５１に出力する。
【００３０】
トラヒックモニタ部１０５の検索エンジン１５２は、管理制御部１５１の制御によりデータベースメモリ１５４内のデータを検索して検索したデータを管理制御部１５１に返信する。また、更新エンジン１５３は、管理制御部１５１の制御によりデータベースメモリ１５４内のデータを更新する。さらに、データベースメモリ１５４には、ＮＬＳテーブル、及びルーティングのためのテーブルであるＧＬＳテーブルを記憶する。
【００３１】
本実施形態においては、アンテナ放射パターンを単一の通信相手先方向の利得が最大となるように指向性を変化させるセクタビームパターンの実効的な送信ビーム幅を３０°としており、可変ビームアンテナ１０１は、方位角を３０°毎に選択的に変化可能に設定できる。ビーム幅及び方位角の変化角度は、６０°又は他の角度であってもよい。
【００３２】
次いで、ＮＬＳテーブルの生成方法について説明する。可変ビームアンテナ１０１を使用した任意のマルチパスルーティングのプロトコルを実装するためには、各無線局は、パケットをその選択された隣接無線局へ効果的に送信するためのその送信方向の設定方法を知っている必要がある。従って、各無線局は周期的にその隣接情報を収集し、各無線局におけるＮＬＳテーブルを作成する（従来技術文献５を参照）。各無線局は、予め取得された各隣接無線局についてのＳＩＮＲ値が最大となる方位角を選び、このＳＩＮＲ値を隣接無線局との間の親和度とする。各無線局はこの方位角と親和度の値を各隣接無線局毎に取り出し、現在日時を更新日時として、ＮＬＳテーブルを生成して更新する。無線局１のＮＬＳテーブルの一例を図４に示す。ＮＬＳテーブルには、図４から明らかなように、各隣接無線局毎に、最大のＳＩＮＲ値に対応する方位角、最大のＳＩＮＲ値である親和度、更新日時が格納されている。
【００３３】
各隣接無線局についてのＳＩＮＲ値の取得方法について説明する。当該アドホック無線ネットワーク内の各無線局は定期的に隣接無線局情報を収集する。隣接無線局情報を収集する自局の無線局は、まずブロードキャストパケットを３０度毎に１２方向の方位角でセクタビームパターンにより順に送信する。方位角が１２方向であるのはセクタビームパターンが３６０度すべてをカバーするようするためである。このパケット信号をＲＱ信号という。ＲＱ信号には、パケット種別：ＲＱ、ＲＱ信号の発信元無線局のＩＤ（識別番号又は識別符号、以下同様である。）と、送信方位角、待機時間が記されている。具体的には、待機時間は１２方向のＲＱ信号の送信が完了するまでの時間である。次いで、ＲＱ信号を受信した周囲の隣接無線局は受信時のＳＩＮＲを測定する。各隣接無線局は待機時間の間、このＳＩＮＲの値を一時的に一時保存テーブルに保存しておき、待機時間の終了後に、パケット種別：ＲＥ、宛先無線局のＩＤ、発信元無線局のＩＤ、ＲＱ信号に記載されていた方位角情報とともにこのＳＩＮＲの値をユニキャストパケット信号でＲＱ信号の発信元である無線局に返信する。このパケットをＲＥ信号という。ＲＥ信号を送信する際には通常のデータパケットを送信する場合と同じ手順を踏む。そして、ＲＥ信号を受信した（ＲＱ信号の発信元の）無線局は、ＲＥ信号からＲＥ信号の発信元無線局ＩＤ（ここでは、無線局のＩＤ）、方位角情報、そしてＳＩＮＲ情報を取り出す。ここで、ＲＱ信号の発信元の無線局以外、つまり該当ＲＱ信号を送信した無線局と異なる無線局がＲＥ信号を受信した場合には、これを無視するものとする。
【００３４】
本実施形態においては、ＳＩＮＲを測定するためには、他の各無線局１と所定のトレーニングパターンのデータパケットを送受信することによりＢＥＲを測定し、無線通信の変復調方式で決定されるＳＩＮＲに対するＢＥＲ特性のグラフを用いて、ＳＩＮＲに換算する。例えば、ＣＤＭＡ方式を用いるときは、ＳＩＮＲに対するＢＥＲ特性のグラフを用いて換算することができ、例えば、ＱＰＳＫ差動検波方式を用いるときは、所定のＣＮＲに対するＢＥＲ特性のグラフを用いて換算することができる。すなわち、搬送波電力対干渉雑音電力比（ＣＩＮＲ）を用いるか、もしくはＳＩＮＲを用いるかは、無線システムで使用する変復調方式に依存する。本発明では、同一チャンネル干渉雑音に関する測定値であればよい。
【００３５】
次に、ＧＬＳテーブルについて説明する。ＧＬＳテーブルは、当該アドホック無線ネットワーク内のすべての無線局１内のデータベースメモリ１５４に保存され、すべての無線局１のＮＬＳテーブルの情報（各無線局１間の無線リンク情報を含む。）であるトポロジー情報を含む。これは、各無線局１内のＧＬＳテーブル内の情報を周期的に他の無線局と交換することにより、各無線局１はネットワーク全体の完全（ただし近似的）なトポロジー情報を把握することができる。可変ビームアンテナ１０１のコンテキストでは、ＧＬＳテーブルは、任意の２つの無線局間の接続性を示すだけでなく、その選択された任意の隣接無線局にパケットを効果的に送信するために各無線局によって設定される必要があるサービスエリアの情報をも示している。それと同時に、各無線局は、アクティブノードリスト、すなわちその時点で任意の通信プロセスに関わる全てのアクティブな無線局の無線局ＩＤを記述したリストに関するその知識（すなわち通信状態フラグ値の情報）を伝搬する。ただし、ネットワークトポロジー又はネットワークにおけるアクティブな無線局数に関する各無線局の知識が近似的なものでしかないということは注意される必要がある。ここで、「アクティブな無線局」とは、通信状態になる無線局をいう。しかしながら、発信元無線局によるルートの周期的な再計算は、それ自体を、変化するシナリオに対して適応的に調整する。
【００３６】
ＧＬＳテーブルは、すべての無線局１間の接続性、最新性、及び通信状態フラグ値で構成される。ここで、接続性は、親和度と呼ばれる無線局間の接続強度を表す項目であり、各無線局１のＮＬＳテーブルから得ることができる。また、最新性は、各無線局情報の更新回数を示す値であり、隣接無線局からトポロジー情報を受信した際に受信無線局内にあるトポロジー情報と比較しより最新の情報に無線局毎に更新する時や、更新されたトポロジー情報を隣接無線局に送出した後にその隣接無線局から再送信を防止するために使用するとともに、更新されたトポロジー情報の隣接無線局への送信先を決定する際にも用いる。通信状態フラグ値は、その時点で任意の通信プロセスに関わる無線局に対して１の値を有し、通信プロセスに関与していない無線局に対して０の値を有する。
【００３７】
このＧＬＳテーブルの一例を図５に示す。ＧＬＳテーブルは、当該アドホック無線ネットワーク内の各無線局１のＮＬＳテーブルを収集したものであり、ある無線局からある無線局までの親和度値の集合になっている。すなわち、ＧＬＳテーブルにおいては、図５から明らかなように、横軸には送信側の無線局が並置される一方、縦軸には受信側の無線局が並置され、当該無線ネットワークにＮ個の無線局１がある場合、ＧＬＳテーブルは、個々の交差点における値が送信側の無線局から受信側の無線局への親和度（最大のＳＩＮＲ値）を示すＮ×Ｎ個の表となる。さらに、各送信側の無線局に対応して、最新性を示す更新回数を有する。ここで、ＧＬＳテーブルは、トポロジー情報を含むＲＥＮ（Ｒｅｎｅｗａｌ）信号を周期的に他の無線局に対して送信して情報交換されることにより生成され、無線局にトポロジー情報（ある無線局のＧＬＳテーブル）が到着した時、ＧＬＳテーブルの更新が行われ、そのとき、トポロジー情報内のＧＬＳテーブルとトポロジー情報を受信した無線局のＧＬＳテーブルを比較する必要があり、比較には更新回数の値を使用し、更新回数の値の大きい情報を新しいＧＬＳテーブルとして使用する。なお、ＲＥＮ信号は、パケット種別：ＲＥＮ、宛先無線局のＩＤ、発信元無線局のＩＤ（ここでは、無線局ＳのＩＤ）、トポロジー情報を含む。
【００３８】
さらに、本実施形態において用いる、アダプティブＭＡＣ（ＭｅｄｉａＡｃｃｅｓｓＣｏｎｔｒｏｌ）方式について説明する。本実施形態において、各無線局１は２次元の閉空間を動き回るものであり、無線通信をする場合は共通の無線チャネルを共有するものとする。各無線局１は３６０度のビーム／ヌル点形成可能なアダプティブアンテナである可変ビームアンテナ１０１を装備しているものとし、実効的な送信ビーム幅は３０度とする。１つの無線局１は送信と受信を同時に行うことはできず、また、複数の異なる送信や複数の異なる受信を行うこともできないものとする。ただし、複数の方向に同じ信号を送信することは可能である。干渉波の方向を知っている場合、受信を行う各無線局は不要な信号による電波干渉を避けるためにヌル点の形成や調整が可能である。
【００３９】まず、当該アドホック無線ネットワークにおいて、初期状態のアイドル状態では、各無線局１はアンテナ放射パターンを無指向性パターンであるオムニパターンにして送受信の待機を行う。
【００４０】
現在多く用いられている無線ＬＡＮ規格であるＩＥＥＥ８０２．１１のＭＡＣプロトコル標準では、信頼性のあるデータ通信を実現するためにＲＴＳ−ＣＴＳ−ＤＡＴＡ−ＡＣＫ交換手順を用いる。一方、本方式においては無線局Ｓが無線局Ｄと無線通信をしたい場合には、無線局Ｓは最初に無線局Ｄを含む無線局Ｓの隣接無線局に“無線局Ｓから無線局Ｄへの通信を開始する”旨をＲＴＳ（Ｒｅｑｕｅｓｔ−Ｔｏ−Ｓｅｎｄ）信号によりオムニパターンで送信する。このＲＴＳ信号には、ＩＥＥＥ８０２．１１に規定する信号や本方式のＲＥ信号と同様に、パケット種別：ＲＴＳ、発信元無線局のＩＤ（ここでは、無線局ＳのＩＤ）、宛先無線局のＩＤ（ここでは、無線局ＤのＩＤ）、待機時間の値が含まれている。無線局Ｓのすべての隣接無線局（無線局Ｓへの方向は各自のＮＬＳテーブルから既知である。）はこの無線局ＳからのＲＴＳ信号を受信する。
【００４１】
このＲＴＳ信号の宛先無線局である無線局ＤがＲＴＳ信号を受信した場合、無線局Ｄは無線局Ｓに対してＤＡＴＡ信号（データ信号）の送信を許可することを伝えるためにＣＴＳ（Ｃｌｅａｒ−Ｔｏ−Ｓｅｎｄ）信号をオムニパターンで返信する。このＣＴＳ信号には、パケット種別：ＣＴＳ、宛先無線局のＩＤ（ここでは、無線局ＳのＩＤ）と、待機時間の値が含まれている。
【００４２】
次いで、ＲＴＳ信号を送信した無線局である無線局Ｓがその宛先である無線局ＤからのＣＴＳ信号を受信したとき、ＤＡＴＡ信号を送信する。宛先無線局である無線局ＤはＤＡＴＡ信号を受信し、その受信が正常に完了すると確認応答としてＡＣＫ（Ａｃｋｎｏｗｌｅｄｇｅｍｅｎｔ）信号（肯定応答信号）を無線局Ｓに返信する。無線局ＳはＡＣＫ信号を受信することで一つのＤＡＴＡに関する一連の処理を完了し、アイドル状態に戻る。ここで、ＤＡＴＡ信号には、パケット種別：ＤＡＴＡ、発信元無線局のＩＤ（ここでは、無線局ＳのＩＤ）、宛先無線局のＩＤ（ここでは、無線局ＤのＩＤ）、待機時間の値、送信すべきデータが含まれている。また、ＡＣＫ信号には、パケット種別：ＡＣＫ、宛先無線局のＩＤ（ここでは、無線局ＳのＩＤ）、待機時間の値が含まれている。
【００４３】
一方、無線局Ｄ以外の無線局（以下、無線局Ａとする。）がＲＴＳ信号を受信した場合には、無線局ＡはＮＬＳテーブルに基づいてＲＴＳ信号の発信元無線局である無線局Ｓの方位角情報を取得し、ＲＴＳ信号に記載されている待機時間の間だけ無線局Ｓの方向にヌル点を形成する。このような任意の方向にヌル点を形成したようなアンテナ放射パターンを総称して排他的セクタパターンという。
【００４４】
また、無線局Ｓ以外がＣＴＳ信号を受信した場合はＲＴＳ信号の場合と同様にしてＣＴＳ信号の発信元無線局の方向に一定期間ヌル点を形成する。
【００４５】
ＲＴＳ信号やＤＡＴＡ信号を送信した無線局Ｓや、ＣＴＳ信号を送信した無線局Ｄはその送信後に一定時間のタイマーを作動させる。無線局Ｓの場合、ＲＴＳ信号を送信後一定時間内にＣＴＳ信号を受信しない場合、及びＤＡＴＡ信号を送信後一定時間内にＡＣＫ信号を受信しない場合には、タイムアウトしたものとしてＲＴＳ信号の送信処理から一連の処理をやり直す。一方、無線局ＤではＣＴＳ信号を送信後一定時間内にＤＡＴＡ信号を受信しない場合には、無線局Ｓへのセクタビームパターンをオムニパターンに戻し、アイドル状態となる。待機時間の期間が終わると、他にその方向に待機時間の期間中の通信がなければ、可変ビームアンテナ１０１におけるその方向のヌル点を解除する。
【００４６】
さらに、本実施形態においては、指向性アンテナである可変ビームアンテナ１０１を活用し、トポロジー情報の更新度の低い周辺無線局へ優先的に通知することにより、トポロジー情報の最新性を維持するためのオーバーヘッドを削減しつつ、周辺無線局における更新度の均一性を確保する。
【００４７】
以下、ＧＬＳテーブルを更新するためのＲＥＮ信号の送信方法について説明する。トポロジー情報を各無線局に通知させるため、フラッディングを用いるとオーバーヘッドが大きくなり、通常のデータ送信に影響を与える可能性がある。われわれの行った先の研究では、各無線局の隣接情報の周期的な伝搬に基づいて、修正されたリンク状態ルーティングプロトコルを構成した（従来技術文献７を参照）。その目的は、ネットワークトポロジーにおけるその無線局を認識させることにある（従来技術文献８を参照）。主たる目的は、ネットワークをトポロジー更新パケットで溢れさせることなく、ネットワーク内の各無線局からあらゆるトポロジー関連情報を収集して、これらをその隣接のただ１つの無線局のみに周期的に（更新情報として）分配することである。
【００４８】
本実施形態の機構では、各無線局は、一定の間隔で周期的に、その隣接の１つの無線局のみに、トポロジー情報及びアクティブノードリストに関わるその知識を含むＲＥＮ信号を伝搬する。ＲＥＮ信号の受信側の無線局は、その知識に基づいてトポロジー情報及びアクティブノードリストを更新し、これをさらに他の無線局に伝搬する。トポロジー情報及びアクティブノードリストを含むＲＥＮ信号によるオーバーヘッドを減らすため、トポロジーマップ及びアクティブノードリストの伝搬先である目標となる隣接無線局の選択は、公知のｌｅａｓｔ−ｖｉｓｉｔｅｄ−ｎｅｉｇｈｂｏｒ−ｆｉｒｓｔ（ＬＶＮＦ）基準（例えば、非特許文献６を参照。）に基づいて行われる。各無線局は、その隣接無線局の最新性（ｒｅｃｅｎｃｙ）と呼ばれる計量をモニタし、そのうちのどれが最小数の更新メッセージを受信しているかを決定する。その時点で最小数の更新メッセージを受信している隣接無線局が、更新のための目標となる無線局となる。具体的には、無線局がトポロジー更新パケット信号であるＲＥＮ信号を受け取り、ＧＬＳテーブルの更新を行い、新たにＲＥＮ信号を送信するとき、直接に無線通信可能な隣接無線局の最新性を示す更新回数を比較し、最小値の更新回数を持つ無線局に対してのみ、ＲＥＮ信号を送出する。そして、ＲＥＮ信号は、送出先無線局の更新回数を増やした上で送出する。
【００４９】
発信元無線局Ｓは、宛先無線局Ｄとの通信を希望する毎に、無線局ＳからＤまでの複数のノード間分離ルートに関するルーティング基準指数γを計算する。これらの複数ルートから、発信元無線局Ｓはアクティブノードリストを調べて、（上述した通り）無線局ＳとＤの間においてゾーン間分離の程度が最大化されかつ最も短いマルチパス（すなわち、最小のルーティング基準指数γを有するマルチパス）を計算する。しかしながら、移動性及び情報浸透の遅さに起因して、発信元無線局が無線局ＳとＤの間の最小のルーティング基準指数γを有するマルチパスを完全に計算することは不可能な場合がある。こうした状況下で性能を向上させるため、各発信元無線局はその計算を周期的に実行し、そのルーティングの決定を適応的に修正する。
【００５０】
本実施形態においては、ＮＬＳテーブルを用いて、１つの隣接無線局のみに対して指向性アンテナでトポロジー情報を配布するため、従来の無指向性ビームを使用する場合（非特許文献６）に比べ遥かにオーバーヘッドを抑えることができる。また、更新回数の活用により、周辺無線局の最新性を平均化することができる。
【００５１】
以下、発信元無線局Ｓと宛先無線局Ｄの間に複数のパスが存在するときの各パスに対するルーティング基準指数γの計算方法について説明する。
【００５２】
図１３及び図１４に示されたようなルート間結合の影響は、アドホック無線ネットワーク内の各無線局において無指向性アンテナの代わりに指向性アンテナ（すなわち可変ビームアンテナ１０１）を使用すれば、大幅に劇的に軽減させることができる。指向性アンテナの使用は無線干渉を大幅に低減させることが可能であり、これによって無線媒体の利用が向上し、その結果ネットワークスループットが向上するということが示されている（例えば、非特許文献５参照。）。
【００５３】
本発明に係る実施形態で提案する、無線媒体におけるゾーン間分離ルートの概念では、１つのパス上のデータ通信が他のパスのデータ通信と電波干渉しない場合、両パスはゾーン間分離であるとされる。しかしながら、無指向性アンテナを使用してアドホック無線ネットワークにおいてゾーン間分離ルートを捕捉することは、あるいは部分的にゾーン間分離ルートを捕捉することであってさえも、各無線局１のサービスエリアが指向性アンテナの場合と比較して大きいことから困難である。無線局１−ｎが、無線局１−ｎに関して水平面内のビーム角θ及び送信範囲の半径Ｒで送信ビームを形成する場合、無線局１−ｎからの到達範囲はサービスエリアＡ_ｎ（θ）で定義され、θ×Ｒ^２／２に等しい。ビーム角θ＝２πの無指向性アンテナの場合、サービスエリアＡ_ｎ（２π）＝πＲ^２である。従って、無線局のサービスエリアを縮小させる、よってルート間結合を低減させる１つの方法は、ビーム角θが３６０゜を大幅に下回る指向性アンテナを使用することにある。
【００５４】
次に、ノード間分離ルートとゾーン間分離ルートの概念について説明する。これまでのアドホック無線ネットワークにおけるマルチパスルーティングに関する研究のほとんどは、適正な負荷バランス化による有効なマルチパスルーティングのために、発信元無線局Ｓ及び宛先無線局Ｄ間の複数のノード間分離パス／ノード間分離の程度が最大化されたパスを発見しようとしている。無線局Ｓ及びＤ間の２つ（又は３つ以上の複数）のパスは、無線局Ｓ及びＤ以外に共通の無線局を共用していない場合に、「ノード間分離」であると呼ばれる。しかしながら、無線環境におけるルート間結合に起因して、ノード間分離ルートはこのコンテキストにおける改善された性能のための十分条件ではあり得ない。本実施形態では、無線媒体における「ゾーン間分離ルート」の概念を提案し、ここでは、１つのパス上でのデータ通信が他のパスにおけるデータ通信と電波干渉しない場合に両パスはゾーン間分離と呼ばれる。言いかえれば、無線局ＳとＤとの間の２つ（又は３つ以上の複数）のパスは、両者間のルート間結合がゼロのとき、「ゾーン間分離」と呼ばれる。
【００５５】
非特許文献４では、相関係数ηを使用してルート間結合の影響が測定されている。この文献では、パスｐにおける無線局１−ｎの相関係数η^ｎ（ｐ）は、パスｐに属さない、無線局１−ｎのアクティブな隣接無線局の個数として定義され（パスｐに対する、無線局１−ｎのサービスエリア内の他の無線局１の無線リンクの結合の度合いを表す。）、ここで、無線局１−ｎのアクティブな隣接無線局とは、その瞬間において無線局１−ｎのサービスエリア内で任意の通信プロセスに能動的（アクティブ）に関与している（通信状態にある）無線局として定義されている。例えば、図１４では、発信元無線局Ｓ及び宛先無線局Ｄが２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝を使用して通信している。従って、このコンテキストの通信では、全ての無線局がアクティブな無線局である。ここで、無線局１ａのアクティブな隣接無線局は｛Ｓ，１ｄ，１ｅ，１ｂ｝である。よって、パスｐ、すなわちパスｐ｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝における無線局１ａの相関係数は、η^ａ（ｐ）＝「パスｐに属さないアクティブな隣接無線局の数」、すなわち２である。
【００５６】
パスｐの相関係数η、すなわちη（ｐ）は、パスｐにおけるすべての無線局１の相関係数の和として定義される。言い換えると、パスｐの相関係数は、パスｐ上の無線局と他のパス上の無線局との間のリンク数を計数したものになる。相関係数η（ｐ）＝０のとき、パスｐを、他の全てのアクティブなパスに対してゾーン間分離であるという。ここで、アクティブなパスとは、その時点で通信プロセスに関与しているパスを指す。相関係数η（ｐ）＝０でなければ、パスｐは他のアクティブなパスと相関係数ηで関連する。
【００５７】
相関係数が大きいほど、両方のパスに対する平均のエンド・ツー・エンドの遅延時間は大きくなることが分かっている（非特許文献４）。これは、２つのパスの相関係数が大きくなるほど、無線伝搬の持つブロードキャストの特徴により、２つのパスが互いの伝送に電波干渉する機会が増大するためである。それに加えて、相関係数が大きいほど、複数のパスに沿ったエンド・ツー・エンドの遅延時間の差も大きくなる。この研究に基づくと、アドホック無線ネットワークにおけるマルチパスルーティングの成功は、複数ルート間の相関係数に大きく依存すると結論することができる。
【００５８】
しかしながら、無指向性アンテナを使用する場合、完全なゾーン間分離ルートを捕捉することは困難である。図１４が示すように、ノード無線局１ａ及び１ｄは両方とも発信元無線局Ｓの無指向性の送信範囲内にあるため、発信元無線局Ｓからノード無線局１ａへのＲＴＳは同時に宛先無線局Ｄを使用不能にする。同様に、ノード無線局１ｃ及び１ｆは両方とも宛先無線局Ｄの無指向性の送信範囲内にあるため、宛先無線局ＤからのＣＴＳはノード無線局１ｃ及び１ｆを共に使用不能にする。従って、無線局Ｓ及びＤ間の２つのマルチパスと無指向性アンテナを使用する場合、最小の可能な相関係数ηの値は２である。これを、最小相関係数η^ｍｉｎという。より詳しく定義すると、最小相関係数η^ｍｉｎは、パス中のノードの相関係数のうちで、最小の相関係数の値である。
【００５９】
可変ビームアンテナ１０１の場合、これらの２つのルートを分離（デカップリング）してこれらを完全なゾーン間分離にすることが可能である。例えば、図６における各無線局１が可変ビームアンテナ１０１を使用し、各無線局１がそのサービスエリアをその目標となる無線局１のみに向けて設定すれば、パス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝間の通信がパス｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝間の通信に影響することはない。図６は、図１と同様なアドホック無線ネットワークにおいて、発信元無線局Ｓと宛先無線局Ｄとの間に相関係数ηが０である２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝が存在するときの、パス上の各無線局の配置及びアンテナ放射パターンを示す平面図である。図１４に示された従来技術の場合では、パス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝間の相関係数ηが７であったのに対して、図６の本実施形態の場合では２つのパス間でゾーン間分離を達成していることが分かる。従って、無指向性アンテナを用いたときの最小相関係数η^ｍｉｎ（無指向性）＝２に対して、指向性アンテナを用いたときの最小相関係数η^ｍｉｎ（指向性）＝０となる。
【００６０】
その結果、無指向性アンテナを使用して最小の相関係数を有する複数のゾーン間分離ルートを捕捉したとしても、最良の場合における宛先無線局へのパケット到着レートは２×ｔ_ｐ毎に１パケットとなる。ここで、時間ｔ_ｐはパスｐ上のトラフィックストリームのパケットに関する、１ホップ毎の平均遅延時間である。この最良の場合では、エラーのないパケット伝送による、ネットワーク内の発信元無線局Ｓから宛先無線局Ｄまでの単一のトラフィックストリームを仮定している。これに対して、可変ビームアンテナ１０１を使用すれば、宛先無線局における最良の場合のパケット到着レートは時間ｔ_ｐ毎に１パケットとなる。図７（本実施形態）及び図１５（従来技術）のタイミングチャートは、この点を示したものである。
【００６１】
図１４を参照し、各無線局１に無指向性アンテナが設けられていると仮定する。さらに、図示された２つのパスは最小の相関係数、すなわちη＝２を有すると仮定する。これは、ノード無線局｛１ａ，１ｂ，１ｃ｝及びノード無線局｛１ｄ，１ｅ，１ｆ｝が互いに分離していることを含意している。以下、ｔ_ｐで時刻（タイミング）を表わすものとし、各時刻において１つのパケットが１つの無線局から他の無線局へ送信される。
【００６２】
図１５について考察すると、発信元無線局Ｓは時間区間Ｔ_０においてデータパケットＰ_１をノード無線局１ａへ送信しており、ノード無線局１ａは次の時間区間、すなわちＴ_１においてデータパケットＰ_１をノード無線局１ｂへ送信している。無指向性アンテナの場合、発信元無線局Ｓは時間区間Ｔ_１の間、ノード無線局１ａからＲＴＳを受信しているためにアイドル状態を保持している必要がある。従って、発信元無線局Ｓはその第２のパケットＰ_２を時間区間Ｔ_２になって初めてノード無線局１ｄ（第２のパスの最初のノード無線局）へと送ることができる。図１５にはパケットの遷移が示され、宛先無線局Ｄはパケットを１つおきの時間区間で受信する。無線局ＳとＤとの間のパス数を２つよりも増やしたとしても、無指向性アンテナを使用する場合は状況は改善されない。
【００６３】
しかしながら、可変ビームアンテナ１０１を使用すれば、ノード無線局１ａがパケットをノード無線局１ｂに送っているときに、発信元無線局Ｓはノード無線局１ｄへ同時にパケットを送ることができる。図７は、指向性アンテナを使用する場合における、図６の最小相関係数η＝０を有する２つのゾーン間分離パス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝を介してパケットを伝送するときのタイミングチャートである。図７が示すように、可変ビームアンテナ１０１を使用する場合、宛先無線局Ｄは、２つのゾーン間分離パスによりすべての時間区間Ｔ_０，Ｔ_１，Ｔ_２，…にパケットを受信する。ここでは、可変ビームアンテナ１０１を使用する場合の２つのゾーン間分離パスは、この最良の場合の方法を達成するに十分であるということが注意される必要がある。
【００６４】
次に、複数の発信元無線局と複数の宛先無線局が存在するときの、マルチパスルーティングによる多重通信について説明する。ここまでは、無線局Ｓ及びＤの単一のペア上での通信について考察してきた。しかしながら、同時通信に関わる無線局Ｓ及びＤの複数のペアについて考察すると状況は悪くなる。各無線局ＳとＤのペアは、両者間の可能な限り最小の相関係数ηで、両者間の２つのマルチパスを選択するものとする。しかしながら、複数の無線局ＳとＤのペアのコンテキストにおいては、例えば無線局Ｓ１及びＤ１間の２つのマルチパスがゾーン間分離であるとしても、それらのパスは、例えば無線局Ｓ２及びＤ２間の他のアクティブなルートに結合（カップリング）される場合がある。従って、全てのアクティブなルートについて考察し、そのそれぞれについて他のアクティブなルートに関連する相関係数ηを発見して、お互いに関してだけでなくシステム内の全てのアクティブなルートに関してゾーン間分離の程度が最大化されているような無線局ＳとＤのペア間の最大ゾーン間分離マルチパスを決定することが不可欠である。
【００６５】
しかしながら、このことだけでは性能の改善には十分でない。マルチパスルーティングにおいては、パス長もまた他の重要なファクタである（非特許文献４）。より多いホップ数Ｈを有するより長いパスは、エンド・ツー・エンドの遅延時間を増大させ、帯域幅をさらに浪費する。従って、無線局ＳとＤのペア間のより長いバイパスルートが小さな相関係数ηを有していても、エンド・ツー・エンドの遅延時間の短縮にはさほど効果的とはなり得ない。この問題に対処するため、われわれは、相関係数ηとホップ数Ｈとの積を最小化することをルート選択の基準にしている。この積の値を最小化すると、ゾーン間分離の程度が最大化された最短パスを得ることができる。この積の値を、ルーティング基準指数γ（＝η×Ｈ）という。
【００６６】
しかしながら、これは、トポロジー及び通信パターンが変化するアドホック無線ネットワークの動的な環境においては困難なタスクである。この困難さを緩和するための近似解については、後に議論される。ここでは、複数の無線局ＳとＤのペアにおけるゾーン間分離の程度が最大化されかつ最短のマルチパスを発見する機構について議論し、このコンテキストにおいて、無指向性アンテナを凌ぐ可変ビームアンテナ１０１の有効性を示す。この目的に沿って、われわれはまず、シミュレーション環境において静的シナリオを仮定した。各無線局は、ネットワークにおける正確なトポロジー及び通信パターンを認識していると仮定する。無線局ＳとＤの間のゾーン間分離の程度が最大化されかつ最短のパスを求めるに当たっては、図８のフローチャートに示されたアルゴリズムを使用している。
【００６７】
図８は、トラヒックモニタ部１０５内の管理制御部１５１によって実行されるルーティング及び通信処理を示すフローチャートである。
【００６８】
図８のステップＳ１において、ＧＬＳテーブルを参照して、発信元無線局Ｓと宛先無線局Ｄの間において、ホップ数Ｈが最大値Ｈｍａｘよりも小さく、かつ互いにノード間分離であるすべてのパスｐ１，…，ｐｎを検索して見つける。本実施形態では、ホップ数の最大値Ｈｍａｘを例えば５に設定する。ステップＳ２において、すべてのパスｐ１，…，ｐｎをアクティブであると仮定して設定し（みなし）、ＧＬＳテーブル内のパスｐ１，…，ｐｎに含まれるノード無線局に対する通信状態フラグ値を１にする。このとき、ＧＬＳテーブル内の通信状態フラグ値が１であるのは、無線局Ｓ及びＤのペア間で検索されたパス上のノード無線局と、無線局Ｓ及びＤ以外の、実際に通信中の発信元無線局及びあて先無線局のペア間のアクティブなパス上のノード無線局とについてである。
【００６９】
ステップＳ３において、ステップＳ２で発見されたパス数が２個以下ならばステップＳ６に進む。そうでないならば、次にステップＳ４において、ＧＬＳテーブルを参照し、ステップＳ２で各アクティブであると仮定して設定された（みなされた）パスｐｉについて、発信元無線局Ｓ及び宛先無線局Ｄ間のパスｐｉ以外の他のアクティブであると仮定して設定された（みなされた）パスに対するパスｐｉの相関係数を計算し、無線局Ｓ及びＤ以外の発信元無線局及び宛先無線局間のアクティブなパスに対するパスｐｉの相関係数を計算し、計算された２種類の相関係数の和にパスｐｉのホップ数Ｈを乗算することにより、パスｐｉのルーティング基準指数γを計算する。このステップＳ４は、アクティブであると仮定して設定された（みなされた）すべてのパスｐｉに対するルーティング基準指数γが計算されるまで反復される。相関係数の計算は、詳しくは、前述されたように、パスｐｉ上の各無線局のサービスエリア内に存在する、発信元無線局Ｓ及び宛先無線局Ｄ間のパスｐｉ以外の他のアクティブであると仮定して設定された（みなされた）パス上の無線局（すなわち、パスｐｉ上の無線局に対する干渉局）の個数と、無線局Ｓ及びＤ以外の発信元無線局及び宛先無線局間のアクティブなパス上の無線局（パスｐｉ上の無線局に対する干渉局）の個数とを計算し、計算された無線局（干渉局）の個数をパスｐｉ毎に加算することによって実行される。
【００７０】
次いで、ステップＳ５において、最大のルーティング基準指数γを有するパスをアクティブでないと仮定して設定し（みなし）、ＧＬＳテーブル内の当該パスに含まれるノード無線局に対する通信状態フラグ値を０にする。ステップＳ５の後で再び、ステップＳ３において、アクティブであると仮定して設定された（みなされた）パスの個数が２以下であるか否かを決定する。ステップＳ３がＮＯのときはステップＳ４を繰り返し、アクティブであると仮定して設定された（みなされた）パスの個数が２個になるまで（すなわち、最大のルーティング基準指数γを有する２個のパスが発見されるまで）ステップＳ３乃至Ｓ５を反復する。この反復で、ステップＳ５によってパスの個数が減少するたびにステップＳ４においてルーティング基準指数を再計算しているのは、無線局Ｓ及びＤ間のアクティブであると仮定して設定された（みなされた）パスの個数が変化することによって、各アクティブであると仮定して設定された（みなされた）パスに関する他のパスとの相関係数が変化するからである。フローの中で、仮にステップＳ１で３個以上のパスが検索された場合に、ステップＳ４の計算においてすべてのパスをアクティブであると仮定して設定された（みなされた）ことは、最終的な状態（すなわち２つのパスのみがアクティブである状態）との相違、又はある種の近似を含むことになる。
【００７１】
ステップＳ３がＹＥＳになったとき、ステップＳ６に進む。ステップＳ６において、発信元無線局Ｓ及び宛先無線局Ｄ間で最終的にアクティブであると仮定して設定された（みなされた）２つのパス（パスｐａ，ｐｂという。）に含まれるノード無線局に対するアクティブノードリスト情報を、ＬＶＮＦ基準に従って他のノード無線局に送信し、各ノード無線局のＧＬＳテーブルを更新させる。次いで、ステップＳ７において、発信元無線局Ｓは、パケットのヘッダ等に含まれたルーティング情報を中継することに基づいて、これらのパスｐａ，ｐｂを介して宛先無線局と通信する。この通信は、発信元無線局Ｓから宛先無線局Ｄへの１方向の通信のみに限定されず、これら２つの無線局間の双方向の通信であってもよい。通信終了後、ステップＳ８において、ＧＬＳテーブル内のパスｐａ，ｐｂに含まれるノード無線局に対する通信状態フラグ値を０にし、パスｐａ，ｐｂに含まれるノード無線局に対するアクティブノードリスト情報を、ＬＶＮＦ基準に従って他のノード無線局に送信し、各ノード無線局のＧＬＳテーブルを更新させる。
【００７２】
以上説明したように、本実施形態によれば、発信元無線局Ｓはルーティング基準指数γを高速に計算して、宛先無線局Ｄとの通信を実行することができる。
【００７３】
＜第２の実施形態＞
以下、本発明の第２の実施形態に係る無線ネットワークのためのルーティング方法について説明する。本実施形態は、第１の実施形態に対して、トラヒックモニタ部１０５内の管理制御部１５１によって実行されるルーティング及び通信処理のみが異なっている。
【００７４】
図９は、本発明の第２の実施形態であるアドホック無線ネットワークにおいて、トラヒックモニタ部１０５内の管理制御部１５１によって実行されるルーティング及び通信処理を示すフローチャートである。
【００７５】
図９のステップＳ１１において、ＧＬＳテーブル内の通信状態フラグ値を０に初期化する。ステップＳ１２において、ＧＬＳテーブルを参照して、発信元無線局Ｓと宛先無線局Ｄの間において、ホップ数Ｈが最大値Ｈｍａｘよりも小さく、かつ互いにノード間分離であるすべてのパスｐ１，…，ｐｎを検索して見つける。ステップＳ１３において、検索されたすべてのパスｐ１，…，ｐｎの中で２個のパスｐｉ，ｐｊ（１対のパス）を選択してそれらをアクティブであると仮定して設定し（みなし）、ＧＬＳテーブル内のパスｐｉ，ｐｊに含まれるノード無線局に対する通信状態フラグ値を１にする。このとき、ＧＬＳテーブル内の通信状態フラグ値が１であるのは、無線局Ｓ及びＤのペア間のパスｐｉ，ｐｊ上のノード無線局と、無線局Ｓ及びＤ以外の、実際に通信中の発信元無線局及びあて先無線局のペア間のアクティブなパス上のノード無線局とについてである。次にステップＳ１４において、ＧＬＳテーブルを参照し、パスｐｊに対するパスｐｉの相関係数を計算し、無線局Ｓ及びＤ以外の発信元無線局及び宛先無線局間のアクティブなパスに対するパスｐｉの相関係数を計算し、計算された２種類の相関係数の和にパスｐｉのホップ数Ｈを乗算することにより、パスｐｉのルーティング基準指数γ_ｉ，ｊを計算する。相関係数の計算は、詳しくは、前述されたように、パスｐｉ上の各無線局のサービスエリア内に存在する、パスｐｊ上の無線局（すなわち、パスｐｉ上の無線局に対する干渉局）の個数と、無線局Ｓ及びＤ以外の発信元無線局及び宛先無線局間のアクティブなパス上の無線局（パスｐｉ上の無線局に対する干渉局）の個数とを計算し、計算された無線局（干渉局）の個数を加算することによって実行される。
【００７６】
ステップＳ１５でも同様に、ＧＬＳテーブルを参照し、パスｐｉに対するパスｐｊの相関係数を計算し、無線局Ｓ及びＤ以外の発信元無線局及び宛先無線局間のアクティブなパスに対するパスｐｊの相関係数を計算し、計算された２種類の相関係数の和にパスｐｊのホップ数Ｈを乗算することにより、パスｐｊのルーティング基準指数γ_ｊ，ｉを計算する。次いで、ステップＳ１６において、ルーティング基準指数γ_ｉ，ｊ及びγ_ｊ，ｉの平均値γを計算し、ＧＬＳテーブル内のパスｐｉ，ｐｊに含まれるノード無線局に対する通信状態フラグ値を０にする。ステップＳ１３乃至Ｓ１６は、ステップＳ１７において、パスｐ１，…，ｐｎのうちのすべての組み合わせのパスの対に関してルーティング基準指数γを計算したと判断されるまで反復される。ステップＳ１７がＮＯであるときは、ステップＳ１３に戻って別の組み合わせのパスの対をアクティブであるとみなして、そのルーティング基準指数γを計算し、ステップＳ１７がＹＥＳであるときはステップＳ１８に進む。
【００７７】
ステップＳ１８において、最小のルーティング基準指数γに対応する１対のパス（以下、パスｐａ，ｐｂという。）を選択し、ＧＬＳテーブル内のパスｐａ，ｐｂに含まれるノード無線局に対する通信状態フラグ値を１にする。ステップＳ１９において、パスｐａ，ｐｂに含まれるノード無線局に対するアクティブノードリスト情報を、ＬＶＮＦ基準に従って他のノード無線局に送信し、各ノード無線局のＧＬＳテーブルを更新させる。次いで、ステップＳ２０において、発信元無線局Ｓは、パケットのヘッダ等に含まれたルーティング情報を中継することに基づいて、これらのパスｐａ，ｐｂを介して宛先無線局と通信する。通信終了後、ステップＳ２１において、ＧＬＳテーブル内のパスｐａ，ｐｂに含まれるノード無線局に対する通信状態フラグ値を０にし、パスｐａ，ｐｂに含まれるノード無線局に対するアクティブノードリスト情報を、ＬＶＮＦ基準に従って他のノード無線局に送信し、各ノード無線局のＧＬＳテーブルを更新させる。
【００７８】
第１及び第２の実施形態に係るルーティング及び通信処理の計算量を比較するために、ステップＳ１及びステップＳ１１で８個のパスが検索された場合について考察する。第１の実施形態では、ステップＳ４を１回目に実行するとき８個のパスについて相関係数ηを計算し、ステップＳ５で最大のルーティング基準指数γを有するパスをアクティブでないとみなし、ステップＳ４を２回目に実行するときに７個のパスについて相関係数ηを計算し、ステップＳ５で最大のルーティング基準指数γを有するパスをアクティブでないとみなし、以下、パスの個数が２個になるまで繰り返すので、計算量を８＋７＋６＋５＋４＋３＝３３を表すことができる。一方、第２の実施形態では、８個のパスのうちのすべての組み合わせのパスの対に対して、ステップＳ１４及びＳ１５を実行する必要があるので、計算量を_８Ｃ_２×２＝５６と表すことができる。
【００７９】
本実施形態のルーティング及び通信処理によれば、計算量は第１の実施形態に比べて増大するが、第１の実施形態のルーティング及び通信処理のような近似（図８のステップＳ４を参照）を含まないので、第１の実施形態に比べてより正確にルーティング基準指数γを計算することができる。
【００８０】
【実施例】
図１０は、図１のアドホック無線ネットワークにおいて、無指向性アンテナを用いたときの無線局の個数に対する相関係数ηを示すグラフである。
【００８１】
発明者らは、可変ビームアンテナ１０１を使用して２つのゾーン間分離パスより成るセットを捕捉する方が無指向性アンテナを使用する場合より格段に容易であることを確認するために、シミュレーションによる調査を行った。この調査では、無線局を１０００×１５００個の領域に所定の密度でランダムに配置した。発信元無線局と宛先無線局とは、それらが複数のホップで互いに離隔されるようにランダムに選択された。まず、全ての無線局１に、固定されたサービスエリアを有する可変ビームアンテナ１０１が設けられていることを仮定した。各可変ビームアンテナ１０１が形成するビームの送信ゾーン角度は６０゜であると仮定している。選択された発信元無線局と宛先無線局との間には、２つのゾーン間分離ルートが発見された。２つのゾーン間分離ルートがその発信元無線局と宛先無線局のペアには利用可能でないならば、他の発信元無線局と宛先無線局のペアが選択された。次に、各無線局が無指向性アンテナを有していると仮定して、可変ビームアンテナ１０１の場合はゾーン間分離であるこれらの２つのルート間の相関係数η_ｏｍｎｉを計算した。この実験を、２５個の発信元無線局と宛先無線局のペアについて繰り返した。先にも述べたように、各ケースにおいて、可変ビームアンテナ１０１を用いたときの相関係数η_ｄｉｒはゼロであり、無指向性アンテナを備えたときの相関係数η_ｏｍｎｉについて計算している。次に、相関係数η_ｏｍｎｉの平均値を求めた。次に無線局の分布密度を変えて、同じ実験を繰り返した。
【００８２】
図１０に、以上説明したシミュレーションの結果が示されている。システム内の無線局数が増大するにつれて、相関係数η_ｏｍｎｉの平均値も増大している。しかしながら、可変ビームアンテナ１０１を備えたときの相関係数η_ｄｉｒはすべてのケースを通じてゼロである。これは、異なる無線局の密度でも可変ビームアンテナ１０１を使用すればゾーン間分離パスを捕捉することが可能であるが、可変ビームアンテナ１０１を使用する場合のこれらのゾーン間分離パスは、無指向性アンテナを代用した場合には高い相関係数を有するということを表している。
【００８３】
次に、複数の発信元無線局と複数の宛先無線局が存在するときの、マルチパスルーティングを用いた多重通信に関するシミュレーション結果を説明する。
【００８４】
図１１は、図１のアドホック無線ネットワークにおいて、同時通信数に対する、発信元無線局Ｓと宛先無線局Ｄの間のマルチパスに対するルーティング基準指数γの平均値を示すグラフである。シミュレーションはまず、無線局Ｓ及びＤの単一のペア間の２つのゾーン間分離の程度が最大化された最短のパスを発見することから始まる。次に、無線局ＳとＤのペアの数を１つずつ増やし、新しく加えた無線局ＳとＤのペアにおいてゾーン間分離の程度が最大化された最短のパスを計算し、最初の無線局ＳとＤのペアにおけるマルチパスのルーティング基準指数γを計算し直し、複数の同時通信が最初の無線局ＳとＤのペアにおけるマルチパスのルーティング基準指数γの値に与える影響を観察する。
【００８５】
この実験を、いくつかのセットの無線局ＳとＤのペアと、可変ビームアンテナ１０１及び無指向性アンテナの双方とを使用して繰り返す。図１１に示された結果は、無指向性アンテナを使用した場合にルーティング基準指数γの増大がかなり急激であることを示している。これは、システムにおける無線局ＳとＤのペア数が増大するにつれて、特定の無線局ＳとＤのペアの他のアクティブなルートに関するルート間結合は、無指向性アンテナの場合において、可変ビームアンテナ１０１の場合に比較して格段に速く増加することを含意している。
【００８６】
次に、可変ビームアンテナ１０１を使用するマルチパスルーティングの性能に関するシミュレーション結果を示す。図１２は、図１のアドホック無線ネットワークにおいて、同時通信数に対するエンド・ツー・エンドの遅延時間の平均値を示すグラフである。
【００８７】
移動性及び情報浸透の遅さに起因して、発信元無線局が無線局ＳとＤの間のゾーン間分離の程度が最大化された最短のマルチパスを完全に計算することは不可能な場合がある。こうした状況下で性能を向上させるため、各発信元無線局はその計算を周期的に実行し、そのルーティングの決定を適応的に修正する。われわれが行ったシミュレーション環境にはこの点を組み込み、無指向性アンテナと可変ビームアンテナ１０１を用い、同時の通信の個数を増大させて、選択された無線局ＳとＤのペアのセット間のパケット当たりの平均のエンド・ツー・エンドの遅延時間を観察した。タイミングに関する仮定は、上述したものと同じである。図１２は、その結果を示している。縦軸の単位は、１個のパケットをある無線局から他の無線局へ１ホップで送信するときの平均の所要時間である。結果は、同時通信数が増えるにつれて、パケット当たりの平均のエンド・ツー・エンドの遅延時間は、可変ビームアンテナ１０１の場合よりも無指向性アンテナを使用する場合の方が格段に急増することを示している。これは、図１１が示す現象の当然の帰結であり、複数パスを使用するルーティング性能については、無指向性アンテナを使用する場合よりも可変ビームアンテナ１０１を使用する方が格段に向上すると結論することができる。
【００８８】
以上説明したように、本発明に係る実施形態によれば、指向性アンテナがマルチパスルーティングに及ぼす効果を調査し、無指向性アンテナを使用するマルチパスルーティングに対してその有効性を比較した。結論として、複数のパスを使用するルーティング性能は、無指向性アンテナを使用する場合に比べて指向性アンテナを使用する方が格段に向上したといえる。アドホック無線ネットワークにマルチパスルーティングの技術を応用したことによって、信頼性の低い無線リンク及び絶えず変化するトポロジーによる影響を減少させることができる。さらに、アドホック無線ネットワークにおいて、エンド・ツー・エンドの遅延時間の短縮及び負荷のバランス化の実行を促進させることもできる。
【００８９】
【発明の効果】
以上詳述したように、本発明に係る無線ネットワークのためのルーティング方法又は無線通信システムによれば、複数の無線局間のリンク状態を表す情報テーブルに基づいて、発信元の無線局と宛先の無線局との間で、少なくとも１つの無線局を中継局として含みかつ互いに共通の無線局を中継局として含まない複数のパスを検索し、
上記無線ネットワークにおいて、上記検索された複数のパス上の無線局を無線通信中の無線局として仮定して設定し、
上記設定された無線通信中の無線局に基づいて、上記各パス上の上記各無線局のサービスエリア内に存在する他の通信中の無線局の個数を計算し、上記計算された通信中の無線局の個数を上記各パス毎に加算することによって、上記各パスに対する、当該パス自体に含まれない他の通信中の無線局との間の電波干渉性に関する結合の度合いを表す相関係数を計算し、上記計算した各パスに対する相関係数に当該パスのホップ数を乗算することにより、他の通信中の無線局から電波干渉無く離間しかつ最短のパスを検索するためのルーティング基準指数を計算し、
上記計算された各パスに対するルーティング基準指数のうち、最大の基準指数を有するパスに含まれる無線局を通信中でない無線局として設定し、
上記各パスに対してルーティング基準指数を計算する処理と、上記最大の基準指数を有するパスに含まれる無線局を通信中でない無線局として設定する処理とを繰り返し、より小さい２個の基準指数を有する１対のパスを上記発信元の無線局と宛先の無線局との間の２個のパスとして選択し、上記選択した２個のパスを用いてルーティングするように制御する。
【００９０】
また、別の発明に係る無線ネットワークのためのルーティング方法又は無線通信システムによれば、複数の無線局間のリンク状態を表す情報テーブルに基づいて、発信元の無線局と宛先の無線局との間で、少なくとも１つの無線局を中継局として含みかつ互いに共通の無線局を中継局として含まない複数のパスを検索し、
上記無線ネットワークにおいて、上記検索された複数のパスのうちの各１対のバス上の無線局を通信中の無線局として仮定して設定し、上記各１対のパス上の上記各無線局のサービスエリア内に存在する他の通信中の無線局の個数を計算し、上記計算された通信中の無線局の個数を上記各１対のパス毎に加算することによって、上記各１対のパスに対する、当該パス自体に含まれない他の通信中の無線局との間の電波干渉性に関する結合の度合いを表す相関係数を計算し、上記計算した各１対のパスに対する相関係数に当該パスのホップ数を乗算することにより、他の通信中の無線局から電波干渉無く離間しかつ最短のパスを検索するための上記各１対のパスに対するルーティング基準指数を計算し、
上記計算した各１対のパスに対するルーティング基準指数のうち、より小さい２個の基準指数を有する１対のパスを上記発信元の無線局と宛先の無線局との間の２個のパスとして選択し、上記選択した２個のパスを用いてルーティングするように制御する。
【００９１】
従って、複数の無線局間のリンク状態を表す情報テーブルに基づいて、最小の相関係数と最短ホップ数という基準で、従来技術に比較して、より少ない計算量で、１対のパスを検索して、マルチパスルーティングすることができ、このとき、エンド・ツー・エンドの遅延時間を大幅に短縮することができる。
【図面の簡単な説明】
【図１】本発明に係る第１の実施形態であるアドホック無線ネットワークを構成する複数の無線局１−１乃至１−９の平面配置図である。
【図２】図１の各無線局１の内部構成を示すブロック図である。
【図３】図１の可変ビームアンテナ１０１のセクタビームパターンの一例を示す図である。
【図４】図２のデータベースメモリ１５４に格納される隣接リンク状態テーブル（ＮＬＳテーブル）の一例を示す図である。
【図５】図２のデータベースメモリ１５４に格納されるグローバルリンク状態テーブル（ＧＬＳテーブル）の一例を示す図である。
【図６】図１と同様なアドホック無線ネットワークにおいて、発信元無線局Ｓと宛先無線局Ｄとの間に相関係数ηが０である２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝が存在するときの、パス上の各無線局の配置及びアンテナ放射パターンを示す平面図である。
【図７】図６の２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝を介してパケットを伝送するときのタイミングチャートである。
【図８】図２のトラヒックモニタ部１０５内の管理制御部１５１によって実行されるルーティング及び通信処理を示すフローチャートである。
【図９】本発明の第２の実施形態であるアドホック無線ネットワークにおいて、図２のトラヒックモニタ部１０５内の管理制御部１５１によって実行されるルーティング及び通信処理を示すフローチャートである。
【図１０】図１のアドホック無線ネットワークにおいて、無指向性アンテナを用いたときの無線局の個数に対する相関係数ηを示すグラフである。
【図１１】図１のアドホック無線ネットワークにおいて、同時通信数に対する、発信元無線局Ｓと宛先無線局Ｄの間のマルチパスに対するルーティング基準指数γの平均値を示すグラフである。
【図１２】図１のアドホック無線ネットワークにおいて、同時通信数に対するエンド・ツー・エンドの遅延時間の平均値を示すグラフである。
【図１３】従来技術に係るマルチパスルーティングであって、発信元無線局Ｓと宛先無線局Ｄとの間に２つのパス｛Ｓ−ｘ１−ｘ２−Ｄ｝及び｛Ｓ−ｙ１−ｙ２−Ｄ｝が存在するときに各パス間でルート間結合が生じていることを示す、パス上の各無線局及びルートの平面配置図である。
【図１４】従来技術に係るマルチパスルーティングであって、発信元無線局Ｓと宛先無線局Ｄとの間に、複数のルート間結合を含む２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝が存在するときの、パス上の各無線局の配置及びアンテナ放射パターンを示す平面図である。
【図１５】図１４の２つのパス｛Ｓ−１ａ−１ｂ−１ｃ−Ｄ｝及び｛Ｓ−１ｄ−１ｅ−１ｆ−Ｄ｝を介してパケットを伝送するときのタイミングチャートである。
【符号の説明】
１，１−１乃至１−９，１ａ乃至１ｆ，Ｓ，Ｄ…無線局、
１０１…可変ビームアンテナ、
１０２…サーキュレータ、
１０３…指向制御部、
１０４…パケット送受信部、
１０５…トラヒックモニタ部、
１０６…回線制御部、
１０７…上位レイヤー処理装置、
１３０…パケット受信部、
１３１…高周波受信機、
１３２…復調器、
１３３…受信バッファメモリ、
１４０…パケット送信部、
１４１…送信タイミング制御部、
１４２…送信バッファメモリ、
１４３…変調器、
１４４…高周波送信機、
１５１…管理制御部、
１５２…検索エンジン、
１５３…更新エンジン、
１５４…データベースメモリ、
１５５…クロック回路、
１６０…拡散符号発生器、
２００乃至２０４…サービスエリア。[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a routing method and a wireless communication system for a wireless network such as an ad hoc wireless network that performs packet communication in a wireless network such as a wireless LAN provided with a plurality of wireless stations.
[0002]
[Prior art]
In an ad hoc wireless network that temporarily supports communication between an unspecified number of people in a specific area using a wireless line, for example, since there is no infrastructure such as an Internet router, the network is Of users need to cooperatively relay packets and perform routing.
[0003]
Ad-hoc wireless network routing schemes typically employ a single path routing through a plurality of user terminal wireless stations. However, for example, as disclosed in Non-Patent Document 1, once a set including a plurality of paths is found between a source wireless station and a destination wireless station, the total data capacity is reduced to a plurality of individual It may be possible to improve the end-to-end delay by splitting into blocks and transmitting them from the source wireless station to the destination wireless station via the selected paths. This ultimately reduces network congestion and end-to-end delay time, and such routing is called "multipath routing."
[0004]
M. R. Pearlman et al., In Non-Patent Document 2, demonstrate that multipath routing can balance network load. The split multi-path routing (SMR) proposed in Non-Patent Document 3 focuses on the construction and holding of a plurality of paths that maximize the degree of separation between the paths. Non-Patent Document 4 introduces the concept of a correlation coefficient between a plurality of paths located between a source wireless station and a destination wireless station.
[0005]
Non-Patent Document 5 discloses a MAC and a routing protocol for an ad hoc wireless network. In this disclosure, each wireless station periodically collects its neighbor information, and an adjacent link state table (for each wireless station) is collected. Create a Neighborhood Link State Table (NLST). Non-Patent Document 6 discloses a method for collecting network topology information without increasing overhead. In Non-Patent Document 7, a modified link state routing protocol is configured based on the periodic propagation of this local information. Its purpose is to make the radio station known in the network topology, as in [8].
[0006]
Further, Non-Patent Document 9 discloses that in a wireless network such as an ad-hoc wireless network, even if a wireless station frequently moves, a routing table can be updated efficiently, and a stable route can be secured to secure wireless communication. A routing method and a router device for a wireless network capable of performing the above are disclosed. Patent Document 1, Non-Patent Documents 10 and 11 disclose directional antennas that can be used in each wireless station in an ad hoc wireless network as in Non-Patent Document 9.
[0007]
[Patent Document 1]
JP 2001-24431 A.
[Non-patent document 1]
S. K. Das et al. , "Improving Quality-of-Service in Adhoc Wireless Networks with Adaptive Multi-path Routing," Proceedings of the CEO, Commerce, 2000
[Non-patent document 2]
M. R. Pearlman et al. , "On the Impact of Alternate Path Routing for Load Balancing in Mobile Ad Hoc Networks", Mobihoc 2000, p. 150, 3-10, 2000.
[Non-Patent Document 3]
S. J. Lee et al. , "Split Multi-Path Routing with Maximumly Disjoint Paths in Ad Hoc Networks", ICC 2001.
[Non-patent document 4]
Kui Wu et al. , "On-Demand Multipath Routing for Mobile Ad Hoc Networks", EPMCC 2001, Vienna, 20th-22nd February 2001.
[Non-Patent Document 5]
S. Bandyopadhyay et al. , "An Adaptive MAC Protocol for Wireless Ad Hoc Community Network, (WACNet) Using Electronically Steerable Passable Radio Antenna, Canada, Canada, Canada.
[Non-Patent Document 6]
S. Bandyopadhyay et al. , "Topology Discovery in Ad Hoc Wireless Networks Using Mobile Agents", Proceedings of MATA 2000, Paris.
[Non-Patent Document 7]
S. Bandyopadhyay et al. , "An Adaptive MAC and Directional Routing Protocol for Ad Hoc Wireless Network Using Directional ESPAR Antenna", Proceedings of the ACM Symposium on Mobile Ad Hoc Networking & Computing 2001 (MOBIHOC 2001), Long Beach, California, USA, 4-5 October, 2001.
[Non-Patent Document 8]
R. RoyChoudhury et al. , "A Distributed Mechanism for Topology Discovery in Ad hoc Wireless Networks using Mobile Agents", Proceedings of the First Annual Workshop On Mobile Ad Hoc Networking & Computing 2001 (MOBIHOC 2000), Boston, Massachusetts, USA, August 11,2000.
[Non-Patent Document 9]
Kazunari Masayama et al., "Proposal of Directional Routing Protocol in Wireless Ad Hoc Networks", Proc. Of the IEICE Communication Society Conference, B-5-207, Published by the Institute of Electronics, Information and Communication Engineers, September 2001.
[Non-Patent Document 10]
T. Ohira et al. , "Electronically Steerable Passive Array Radiator Antennas for Low-Cost Analog Analog Beamforming," 2000 IEEE International Conference on Electronics and Technology. 101-104, Dana point, California, May 21-25, 2000.
[Non-Patent Document 11]
Satoshi Tano et al., "M-CMA: Digital Signal Processing Algorithm for Adaptive Beamforming by Microwave Signal Processing", IEICE Technical Report, AP99-62, SAT99-62, pp. 139-143. 15-22, July 1999.
[0008]
[Problems to be solved by the invention]
However, it has also been shown that employing multiple paths between a source wireless station and a destination wireless station does not necessarily result in reduced end-to-end delay times. Non-Patent Document 2 discusses the effects of Alternate Path Routing (APR) in a mobile ad hoc network, and considers the network topology and channel characteristics (eg, inter-route coupling) to the gains provided by the APR method. It has been argued that there may be significant restrictions.
[0009]
Suppose only two source radio stations ₁ And s ₂ Respectively transmit the data packet to the destination wireless station d. ₁ And d ₂ You are about to send to. Different node radio stations x ₁ , X ₂ , Y ₁ And y ₂ Exist, and two paths {s} that include these node radio stations ₁ -X ₁ -Y ₁ -D ₁ ｝ And ｛s ₂ -X ₂ -Y ₂ -D ₂ When して is selected for communication, these paths that do not include a common node wireless station are referred to as node wireless station separation in this specification. Path ｛s which is the separation between node radio stations ₁ -X ₁ -Y ₁ -D ₁ ｝ And ｛s ₂ -X ₂ -Y ₂ -D ₂ The end-to-end delay times of the data packets transmitted over each of the｝ s should be independent of each other. However, node radio station x ₁ And x ₂ And / or y ₁ And y ₂ Are adjacent to each other, it is impossible for two communications to occur simultaneously. Because the RTS / CTS exchange during data communication is performed at a time by the node radio station x ₁ Or x ₂ , And similarly, the node radio station y ₁ Or y ₂ Is only allowed to transmit data packets. Thus, the end-to-end delay between any source and destination wireless stations does not depend solely on the congestion characteristics of the node wireless stations on that path. The communication pattern in the adjacent area also contributes to this delay time. This is a phenomenon known as inter-route coupling (or route coupling). Route-to-route coupling occurs when two routes are physically close enough to interfere with each other during data communication.
[0010]
FIG. 13 shows multipath routing according to the prior art, which shows that when two paths exist between a source wireless station S and a destination wireless station D, inter-route coupling occurs between the paths. FIG. 2 is a plan layout view of each wireless station and route shown. Here, a first path including the wireless stations {S, x1, x2, D} and a second path including the wireless stations {S, y1, y2, D} between the wireless stations S and D. Exists, and each path does not have a common node other than the wireless stations S and D. In this specification, these paths are also referred to as “node wireless station separation”. Thus, the end-to-end delay times of packet transmission over each path should be independent of each other, however, the node radio stations x1 and y1 are in the service area of the source radio station S (ie, the radio signal (Radio transmission possible area) 210 and are located close to each other, and the node radio stations x2 and y2 are located in the service area 211 of the destination radio station D and are located close to each other. Therefore, there is an inter-route connection between the paths. For this reason, it is impossible to transmit packets simultaneously on each path. In addition, the performance of data transmission using these two paths is worse than that of a protocol using a single path.
[0011]
FIG. 14 shows a multipath routing according to the prior art, in which two paths {S-1a-1b-1c-D between the source wireless station S and the destination wireless station D, including a plurality of inter-route connections. It is a top view which shows arrangement | positioning of each radio | wireless station on a path | route, and antenna radiation pattern when {and {S-1d-1e-1f-D} exist.
[0012]
In FIG. 14, node radio stations 1a and 1d exist in service area 220 from source radio station S, and radio stations S, 1b, 1d and 1e exist in service area 221 from node radio station 1a. , The node wireless stations 1a, 1c, 1d, 1e, and 1f exist in the service area 222 from the node wireless station 1b. In such a case, between the paths {S-1a-1b-1c-D} and {S-1d-1e-1f-D}, the links between the node radio stations 1a and 1d, the node radio stations 1a and 1e There is a route-to-route coupling as shown by a link between the two paths, which hinders the routing using these two paths.
[0013]
FIG. 15 is a timing chart when a packet is transmitted via the two paths {S-1a-1b-1c-D} and {S-1d-1e-1f-D} of FIG. Actually, referring to FIG. 14 and FIG. 15, when there are two paths coupled between routes between the source wireless station S and the destination wireless station D, the node wireless stations on each path mutually transmit radio waves. The manner of interference will be described in more detail. Each wireless station has an omnidirectional antenna.
[0014]
Referring to FIG. 15, the source wireless station S is located at a time interval T ₀ At the data packet P ₁ Is transmitted to the node wireless station 1a, and the node wireless station 1a ₁ At the data packet P ₁ Is transmitted to the node wireless station 1b. If each radio station has an omnidirectional antenna, the source radio station S ₁ During this period, it is necessary to hold the idle state because the RTS is received from the node wireless station 1a. Therefore, the source wireless station S sends its second packet P ₂ To time interval T ₂ Only after that, it can be sent to the node wireless station 1d (the first node wireless station in the second path). In the transition of the packet as shown in FIG. 15, the destination wireless station D receives the packet every other time interval. Increasing the number of paths between wireless stations S and D beyond two does not improve the situation.
[0015]
Consequently, in multipath communication between a pair of radio stations S and D, it is possible that node radio stations in these multiple routes are constantly competing for access to the media they share, Communication performance may be worse than with routing over a single path between the pair of stations S and D. Therefore, in this context, the fact that a plurality of routes constituting the multipath are separated from each other is not a sufficient condition for improving the performance. Therefore, an effort to find a route that is a node-to-node separation or a route that maximizes the degree of node-to-node separation as in Non Patent Literatures 3 and 4 is not effective due to the route-to-route coupling. There is. Therefore, it is desirable to provide a more effective way to reduce end-to-end delay when performing multipath routing in an ad hoc wireless network.
[0016]
SUMMARY OF THE INVENTION An object of the present invention is to solve the above problems, and to realize a wireless network such as an ad-hoc wireless network capable of significantly reducing end-to-end delay time compared to the related art. A routing method and a wireless communication system are provided.
[0017]
[Means for Solving the Problems]
A routing method for a wireless network according to a first invention is a routing method for a wireless network including a plurality of wireless stations and performing wireless communication between the wireless stations.
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. A first step of searching for a plurality of paths not included as stations;
In the wireless network, a second step of assuming and setting wireless stations on the plurality of paths searched as wireless stations performing wireless communication;
Based on the set wireless communication stations, calculate the number of other communicating wireless stations in the service area of each wireless station on each path, and calculate the calculated number of communicating wireless stations. By adding the number of wireless stations for each of the paths, a correlation coefficient indicating the degree of coupling with respect to each path with respect to radio wave coherence with another communicating wireless station that is not included in the path itself. Is calculated by multiplying the calculated correlation coefficient for each path by the number of hops of the path, thereby obtaining a routing reference index for searching for the shortest path separated from other communicating wireless stations without radio wave interference. A third step of calculating
A fourth step of setting a wireless station included in the path having the largest reference index among the calculated routing reference indexes for each path as a wireless station that is not communicating;
Repeating the third and fourth steps to select a pair of paths having two smaller reference indices as two paths between the source wireless station and the destination wireless station; And a fifth step of routing using the two paths.
[0018]
A wireless communication system according to a second aspect of the present invention is a wireless communication system for a wireless network including a plurality of wireless stations and performing wireless communication between the wireless stations.
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. Search for multiple paths not included as stations,
In the wireless network, the wireless stations on the plurality of paths searched are set assuming wireless stations during wireless communication,
Based on the set wireless communication stations, calculate the number of other communicating wireless stations in the service area of each wireless station on each path, and calculate the calculated number of communicating wireless stations. By adding the number of wireless stations for each of the paths, a correlation coefficient indicating the degree of coupling with respect to each path with respect to radio wave coherence with another communicating wireless station that is not included in the path itself. Is calculated by multiplying the calculated correlation coefficient for each path by the number of hops of the path, thereby obtaining a routing reference index for searching for the shortest path separated from other communicating wireless stations without radio wave interference. And calculate
Of the routing reference indices for each of the calculated paths, a wireless station included in the path having the largest reference index is set as a wireless station that is not communicating,
A process of calculating a routing reference index for each path and a process of setting a wireless station included in the path having the largest reference index as a wireless station not communicating are repeated, and two smaller reference indices are calculated. Control means for selecting a pair of paths as two paths between the source wireless station and the destination wireless station and performing routing using the selected two paths. It is characterized by the following.
[0019]
Furthermore, a routing method for a wireless network according to a third invention is a routing method for a wireless network that includes a plurality of wireless stations and performs wireless communication between the wireless stations.
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. Searching for a plurality of paths that are not included as stations, and setting, in the wireless network, assuming a wireless station on each pair of buses of the searched plurality of paths as a communicating wireless station; The number of other communicating wireless stations existing in the service area of each wireless station on each pair of paths is calculated, and the calculated number of communicating wireless stations is calculated for each pair of paths. By adding each time, a correlation coefficient indicating the degree of coupling of radio wave coherence with respect to each pair of paths with another communicating wireless station not included in the path itself is calculated. For each pair of paths calculated By multiplying the correlation coefficient by the number of hops of the path, a routing reference index is calculated for each pair of the paths for searching for the shortest path apart from other communicating wireless stations without radio interference. Steps to
Among the calculated routing reference indices for each pair of paths, a pair of paths having two smaller reference indices is selected as two paths between the source wireless station and the destination wireless station. Routing using the two selected paths.
[0020]
Still further, a wireless communication system according to a fourth invention is a wireless communication system for a wireless network that includes a plurality of wireless stations and performs wireless communication between the wireless stations.
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. Search for multiple paths not included as stations,
In the wireless network, wireless stations on each pair of buses among the plurality of searched paths are set assuming wireless stations in communication, and each wireless station on each pair of paths is set. By calculating the number of other communicating wireless stations existing in the service area and adding the calculated number of communicating wireless stations for each pair of paths, the pair of paths , A correlation coefficient indicating the degree of coupling with respect to radio wave coherence with another communicating wireless station not included in the path itself is calculated, and the calculated correlation coefficient is calculated for each pair of paths. By multiplying the number of hops of the path, a routing reference index is calculated for each pair of the paths for searching for the shortest path apart from other communicating wireless stations without radio interference,
Among the calculated routing reference indices for each pair of paths, a pair of paths having two smaller reference indices is selected as two paths between the source wireless station and the destination wireless station. Further, there is provided a control means for controlling so as to perform routing using the two selected paths.
[0021]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[0022]
<First embodiment>
FIG. 1 is a plan view of a plurality of wireless stations 1-1 to 1-9 (generally denoted by reference numeral 1) showing the configuration of an ad hoc wireless network according to a first embodiment of the present invention. FIG. 2 is a block diagram showing the configuration of each wireless station 1 in FIG.
[0023]
In the wireless communication system of this embodiment, as shown in FIG. 1, a plurality of wireless stations 1 are scattered in a plane, and each wireless station 1 has a gain, a transmission power, a reception sensitivity, Has a predetermined service area determined by parameters such as the above, and can perform packet communication within this service area. When performing packet communication with the wireless station 1 outside the service area, the wireless station 1 within the service area Is used as a relay station to relay the packet data, thereby transmitting the packet data to a desired destination wireless station 1. That is, each wireless station 1 includes a router device that performs packet routing, and operates as a source wireless station, a relay station, or a destination wireless station.
[0024]
The wireless communication system according to this embodiment is applied to, for example, a packet communication system of an ad hoc wireless network such as a wireless LAN, and includes an omni pattern that is an omnidirectional radiation pattern and a predetermined pattern in a horizontal plane centered on the own station. A variable beam antenna 101 capable of selectively switching between a sector beam pattern capable of selectively changing a sector-shaped main beam for each azimuth and an exclusive sector pattern capable of forming a null point for each azimuth. Prepare,
(A) RE (Reply) signal from an adjacent wireless station including a measured value of a signal power to interference noise power ratio (hereinafter, referred to as SINR) when the adjacent wireless station receives an RQ (Request) signal from the own station. Based on the SINR viewed from the wireless station 1 in the service area for each predetermined azimuth in the horizontal plane centered on the own station, which is obtained in advance based on the local station, the maximum SINR is selected for each adjacent wireless station. And an adjacent link station (Neighbor Link-State Table) (hereinafter referred to as an NLS table) including the affinity, the corresponding azimuth angle, and the update time of the data. ,
(B) By exchanging the topology information of the NLS table (refers to the route information indicating the link state between all the wireless stations in the ad hoc wireless network, the same applies hereinafter) between the wireless stations, the ad hoc wireless network is exchanged. , Collects topology information of NLS tables for all the wireless stations 1, and includes the topology information (including the link state between the wireless stations 1), the number of updates of the topology information for each wireless station, and the number of updates. A Global Link State Table (hereinafter, referred to as a GLS table) including a communication state flag value indicating a wireless station 1 involved in an arbitrary communication process at a time.
Is stored in the database memory 154, and the packet signal is routed while controlling the radiation pattern of the variable beam antenna 101 based on the NLS table and the GLS table.
[0025]
In particular, in each wireless station 1,
(1) Based on the GLS table, between a source wireless station S and a destination wireless station D, each node includes at least one wireless station as a relay station and does not include a common wireless station as a relay station. Searching for multiple paths that are separate;
(2) setting a wireless station on the plurality of paths searched as a communicating wireless station in a communication state flag value indicating a wireless station communicating in the wireless network;
(3) Based on the communication status flag value, calculate the number of other communicating wireless stations within the reach of the wireless signal of each wireless station on each path, and calculate the calculated number of communicating wireless stations. By adding the number of wireless stations for each of the paths, a correlation coefficient indicating the degree of coupling with respect to each path with respect to radio wave coherence with another communicating wireless station that is not included in the path itself. , And by multiplying the correlation coefficient of the coupling for each path by the number of hops of the path, a routing reference index for finding the shortest path separated from other communicating wireless stations without radio wave interference. calculating γ;
(4) setting a wireless station included in the path having the largest reference index in the communication state flag value as a wireless station that is not communicating;
(5) The steps (3) and (4) described above are repeated, and two paths having the smaller routing reference index γ are selected as paths between the source wireless station S and the destination wireless station D, Routing using the selected path.
[0026]
Next, the device configuration of each wireless station 1 will be described with reference to FIG. 2, a wireless station 1 includes a variable beam antenna 101, a directivity control unit 103 for controlling the directivity thereof, a circulator 102, a data packet transmitting / receiving unit including a data packet transmitting unit 140 and a data packet receiving unit 130. 104, a traffic monitor unit 105, a line control unit 106, and an upper layer processing unit 107.
[0027]
Transmission signal data for communication in packet format generated by the upper layer processing device 107 that processes data to be transmitted / received is input to the modulator 143 via the transmission buffer memory 142, and the modulator 143 transmits a signal of a predetermined radio frequency. The carrier signal is spread-spectrum modulated according to the input communication transmission signal data by using a predetermined communication channel spreading code generated by the CDMA method in the spreading code generator 160, and the modulated transmission signal is transmitted at a high frequency. Device 144. After performing processing such as amplification on the input transmission signal, the high-frequency transmitter 144 transmits the signal from the variable beam antenna 101 to another wireless station 1 via the circulator 102. On the other hand, the reception signal for the communication channel in the packet format received by the variable beam antenna 101 is input to the high-frequency receiver 131 via the circulator 102, and the high-frequency receiver 131 performs low noise amplification on the input reception signal. After the processing of (1) is performed, the output is output to the demodulator 132. Demodulator 132 demodulates the input received signal by spectrum despreading using a spread code for a communication channel generated by CDMA method in spread code generator 160, and demodulates the received signal data after demodulation to an upper layer. Output to the processing device 107 and output to the traffic monitor unit 105 for traffic monitoring.
[0028]
In the present embodiment, the variable beam antenna 101 that is a directional antenna is connected to a plurality of antenna elements and a control unit 103 that controls the directivity thereof,
(A) an omni pattern that is an omnidirectional radiation pattern;
(B) As shown in FIG. 3, for example, a sector beam pattern capable of selectively changing a sector-shaped main beam for each predetermined azimuth in a horizontal plane centered on the own station;
(C) an exclusive sector pattern capable of forming a null point for each azimuth angle;
Is an antenna that can be selectively switched by electrical control. Note that the variable beam antenna 101 may be, for example, a known phased array antenna device, or may be a variable beam antenna disclosed in Patent Document 1 or Non-Patent Document 11.
[0029]
The traffic monitor unit 105 includes a search engine 152, an update engine 153, a database memory 154, and a clock circuit 155, executes routing and communication processing described later, and allows the wireless station 1 to communicate with another wireless station 1. By determining the communication channel to be used in the packet communication and transmitting the designated data of the spreading code corresponding to the determined communication channel to the spreading code generator 160 via the line control unit 106, the spreading code generator 160 By controlling to generate a spreading code corresponding to the designated data and transmitting designated data of a time slot corresponding to the determined communication channel to the transmission timing control unit 141 via the line control unit 106, the transmission timing control unit 141 is a transmission signal for a communication channel by the transmission buffer memory 142 Controls to transmit the signal for the communication channel is transmitted in the corresponding time slot by controlling the writing and reading of over data. The clock circuit 155 measures the current date and time and outputs the information to the management control unit 151 as necessary.
[0030]
The search engine 152 of the traffic monitor unit 105 searches data in the database memory 154 under the control of the management control unit 151 and returns the searched data to the management control unit 151. The update engine 153 updates data in the database memory 154 under the control of the management control unit 151. Further, the database memory 154 stores an NLS table and a GLS table which is a table for routing.
[0031]
In this embodiment, the effective transmission beam width of the sector beam pattern for changing the directivity of the antenna radiation pattern so that the gain in the direction of a single communication partner is maximized is set to 30 °. Can be set so that the azimuth can be selectively changed every 30 degrees. The angle of change in beam width and azimuth may be 60 ° or another angle.
[0032]
Next, a method of generating an NLS table will be described. In order to implement any multi-path routing protocol using the variable beam antenna 101, each wireless station must configure its transmission direction to effectively transmit packets to its selected adjacent wireless station. You need to know. Therefore, each wireless station periodically collects its neighbor information and creates an NLS table for each wireless station (see Prior Art Document 5). Each wireless station selects an azimuth at which the previously obtained SINR value for each adjacent wireless station is the maximum, and sets the SINR value as the affinity with the adjacent wireless station. Each wireless station extracts the azimuth and affinity values for each adjacent wireless station, and generates and updates an NLS table using the current date and time as the update date and time. An example of the NLS table of the wireless station 1 is shown in FIG. As is clear from FIG. 4, the azimuth corresponding to the maximum SINR value, the affinity which is the maximum SINR value, and the update date and time are stored in the NLS table for each adjacent wireless station.
[0033]
A method of acquiring the SINR value for each adjacent wireless station will be described. Each wireless station in the ad hoc wireless network periodically collects neighboring wireless station information. First, the wireless station of the own station that collects the adjacent wireless station information transmits the broadcast packets in the azimuth in 12 directions every 30 degrees according to the sector beam pattern. The azimuth angles are 12 directions so that the sector beam pattern covers all 360 degrees. This packet signal is called an RQ signal. The RQ signal includes a packet type: RQ, an ID (identification number or identification code, the same applies hereinafter) of a source radio station of the RQ signal, a transmission azimuth, and a standby time. Specifically, the standby time is a time until the transmission of the RQ signal in the 12 directions is completed. Next, the neighboring wireless stations that have received the RQ signal measure the SINR at the time of reception. Each adjacent wireless station temporarily stores the value of the SINR in the temporary storage table during the standby time, and after the end of the standby time, the packet type: RE, the ID of the destination wireless station, and the ID of the source wireless station , Together with the azimuth information described in the RQ signal, returns the SINR value to the wireless station that is the source of the RQ signal in a unicast packet signal. This packet is called an RE signal. When transmitting the RE signal, the same procedure as when transmitting a normal data packet is performed. Then, the wireless station that has received the RE signal (the source of the RQ signal) extracts the source wireless station ID of the RE signal (here, the ID of the wireless station), azimuth information, and SINR information from the RE signal. Here, when an RE signal is received by a wireless station other than the wireless station that transmitted the RQ signal, that is, when a wireless station different from the wireless station that transmitted the RQ signal is received, the RE signal is ignored.
[0034]
In the present embodiment, in order to measure the SINR, the BER is measured by transmitting and receiving a data packet of a predetermined training pattern to and from each of the other wireless stations 1, and the BER with respect to the SINR determined by the modulation / demodulation method of the wireless communication is measured. It is converted to SINR using a characteristic graph. For example, when using the CDMA system, conversion can be performed using a graph of BER characteristics with respect to SINR. For example, when using the QPSK differential detection system, conversion can be performed using a graph of BER characteristics with respect to a predetermined CNR. Can be. That is, whether to use the carrier power to interference noise power ratio (CINR) or the SINR depends on the modulation / demodulation method used in the wireless system. In the present invention, any measurement value relating to co-channel interference noise may be used.
[0035]
Next, the GLS table will be described. The GLS table is stored in the database memory 154 in all the wireless stations 1 in the ad hoc wireless network, and is information of the NLS tables of all the wireless stations 1 (including information on wireless links between the wireless stations 1). Contains topology information. This is because the information in the GLS table in each wireless station 1 is periodically exchanged with another wireless station, so that each wireless station 1 can grasp complete (but approximate) topology information of the entire network. it can. In the context of the variable beam antenna 101, the GLS table not only indicates the connectivity between any two wireless stations, but also each wireless station in order to effectively transmit a packet to any of its selected adjacent wireless stations. It also shows the information of the service area that needs to be set by. At the same time, each radio station propagates its knowledge (i.e. information on communication state flag values) about the active node list, i.e. a list describing the radio station IDs of all active radio stations involved in any communication process at that time. I do. However, it should be noted that each radio station's knowledge of the network topology or the number of active radio stations in the network is only approximate. Here, the “active wireless station” refers to a wireless station that is in a communication state. However, the periodic recalculation of the route by the source wireless station adjusts itself adaptively to changing scenarios.
[0036]
The GLS table is configured with connectivity, currency, and communication status flag values between all the wireless stations 1. Here, the connectivity is an item indicating the connection strength between wireless stations called an affinity, and can be obtained from the NLS table of each wireless station 1. In addition, the recency is a value indicating the number of updates of each wireless station information, and when topology information is received from an adjacent wireless station, the latest information is compared with the topology information in the receiving wireless station and updated to the latest information for each wireless station. Or when sending updated topology information to an adjacent wireless station to prevent retransmission from that adjacent wireless station and determining the destination of the updated topology information to be sent to the adjacent wireless station. Also used for The communication state flag value has a value of 1 for a wireless station involved in an arbitrary communication process at that time, and has a value of 0 for a wireless station not involved in the communication process.
[0037]
FIG. 5 shows an example of the GLS table. The GLS table is a collection of NLS tables of each wireless station 1 in the ad hoc wireless network, and is a set of affinity values from a certain wireless station to a certain wireless station. That is, in the GLS table, as is apparent from FIG. 5, the transmitting side radio stations are arranged side by side on the horizontal axis, and the receiving side radio stations are arranged side by side on the vertical axis. When there is the wireless station 1, the GLS table is an N × N table in which the value at each intersection indicates the affinity (maximum SINR value) from the transmitting wireless station to the receiving wireless station. Further, it has an update count indicating the latestness corresponding to each transmitting-side radio station. Here, the GLS table is generated by periodically transmitting an REN (Renewal) signal including topology information to another wireless station and exchanging information, and the topology information (GLS of a certain wireless station) is given to the wireless station. When the GLS table arrives, the GLS table is updated. At this time, it is necessary to compare the GLS table in the topology information with the GLS table of the wireless station that has received the topology information. Used, and information having a large value of the number of updates is used as a new GLS table. The REN signal includes a packet type: REN, a destination wireless station ID, a source wireless station ID (here, the ID of the wireless station S), and topology information.
[0038]
Further, an adaptive MAC (Media Access Control) system used in the present embodiment will be described. In the present embodiment, the wireless stations 1 move around in a two-dimensional closed space, and share a common wireless channel when performing wireless communication. Each radio station 1 is equipped with a variable beam antenna 101 which is an adaptive antenna capable of forming a 360-degree beam / null point, and the effective transmission beam width is 30 degrees. It is assumed that one wireless station 1 cannot perform transmission and reception at the same time, and cannot perform a plurality of different transmissions and a plurality of different receptions. However, it is possible to transmit the same signal in a plurality of directions. If the direction of the interference wave is known, each receiving wireless station can form or adjust a null point to avoid radio wave interference due to unnecessary signals.
First, in the idle state of the initial state in the ad hoc wireless network, each wireless station 1 sets the antenna radiation pattern to an omni pattern, which is a non-directional pattern, and waits for transmission / reception.
[0040]
In the MAC protocol standard of IEEE802.11, which is a wireless LAN standard widely used at present, an RTS-CTS-DATA-ACK exchange procedure is used to realize reliable data communication. On the other hand, in the present system, when the wireless station S wants to perform wireless communication with the wireless station D, the wireless station S first notifies a wireless station adjacent to the wireless station S including the wireless station D “from the wireless station S to the wireless station D. Is transmitted in an omni pattern using an RTS (Request-To-Send) signal. The RTS signal includes a packet type: RTS, an ID of the source wireless station (here, the ID of the wireless station S), and an ID of the destination wireless station, similarly to the signal defined in IEEE 802.11 and the RE signal of the present system. (Here, the ID of the wireless station D) and the value of the standby time. All adjacent wireless stations of the wireless station S (the directions to the wireless station S are known from their NLS tables) receive the RTS signal from the wireless station S.
[0041]
When the wireless station D that is the destination wireless station of the RTS signal receives the RTS signal, the wireless station D transmits a CTS (Clear- To-Send) signal is returned in an omni pattern. The CTS signal includes the packet type: CTS, the ID of the destination wireless station (here, the ID of the wireless station S), and the value of the standby time.
[0042]
Next, when the wireless station S that has transmitted the RTS signal receives the CTS signal from the wireless station D that is the destination, the wireless station S transmits the DATA signal. The wireless station D, which is the destination wireless station, receives the DATA signal, and returns an ACK (Acknowledgement) signal (acknowledgment signal) to the wireless station S as an acknowledgment when the reception is completed normally. Upon receiving the ACK signal, the wireless station S completes a series of processes for one DATA, and returns to the idle state. Here, the DATA signal includes the packet type: DATA, the ID of the source wireless station (here, the ID of the wireless station S), the ID of the destination wireless station (here, the ID of the wireless station D), and the value of the standby time. , Data to be transmitted. The ACK signal includes the packet type: ACK, the ID of the destination wireless station (here, the ID of the wireless station S), and the value of the standby time.
[0043]
On the other hand, when a wireless station other than the wireless station D (hereinafter, wireless station A) receives the RTS signal, the wireless station A determines the wireless station S, which is the source wireless station of the RTS signal, based on the NLS table. Is obtained, and a null point is formed in the direction of the wireless station S only during the standby time described in the RTS signal. Such an antenna radiation pattern in which a null point is formed in an arbitrary direction is collectively called an exclusive sector pattern.
[0044]
When a station other than the wireless station S receives the CTS signal, a null point is formed for a certain period in the direction of the source wireless station of the CTS signal in the same manner as in the case of the RTS signal.
[0045]
The wireless station S that has transmitted the RTS signal and the DATA signal and the wireless station D that has transmitted the CTS signal operate a timer for a fixed time after the transmission. In the case of the radio station S, if the CTS signal is not received within a certain time after the transmission of the RTS signal, or if the ACK signal is not received within a certain time after the transmission of the DATA signal, the RTS signal transmission processing is performed assuming that the time-out has occurred. Repeat the series of processing from. On the other hand, when the wireless station D does not receive the DATA signal within a certain period of time after transmitting the CTS signal, the sector beam pattern to the wireless station S is returned to the omni pattern, and the wireless station D enters an idle state. When the waiting time period ends, if there is no other communication in the direction during the waiting time period, the null point in the direction in the variable beam antenna 101 is released.
[0046]
Furthermore, in the present embodiment, the variable beam antenna 101, which is a directional antenna, is used, and priority is given to peripheral wireless stations having a low degree of update of the topology information to maintain the latestness of the topology information. The uniformity of the degree of update in peripheral wireless stations is ensured while reducing overhead.
[0047]
Hereinafter, a method of transmitting the REN signal for updating the GLS table will be described. When flooding is used to notify topology information to each wireless station, overhead increases, which may affect normal data transmission. In our earlier work, we constructed a modified link state routing protocol based on the periodic propagation of neighbor information for each wireless station (see Prior Art Document 7). The purpose is to make the radio station known in the network topology (see prior art document 8). The main purpose is to collect all topology related information from each wireless station in the network without flooding the network with topology update packets, and to periodically (only update information) ) To distribute.
[0048]
In the mechanism of the present embodiment, each wireless station periodically propagates the REN signal containing its topology information and its knowledge of the active node list to only one of its neighbors at regular intervals. The wireless station on the receiving side of the REN signal updates the topology information and the active node list based on the knowledge, and propagates the updated information to other wireless stations. In order to reduce the overhead due to the REN signal including the topology information and the active node list, the selection of the target neighboring wireless station to which the topology map and the active node list are to be propagated is based on a known least-visited-neighbor-first (LVNF) standard. (For example, see Non-Patent Document 6). Each wireless station monitors a metric called recency of its neighbors and determines which of them has received the minimum number of update messages. The neighboring wireless station that has received the minimum number of update messages at that time is the target wireless station for updating. Specifically, when the wireless station receives the REN signal, which is a topology update packet signal, updates the GLS table, and transmits a new REN signal, an update indicating the freshness of an adjacent wireless station that can directly perform wireless communication is performed. The number of times is compared, and the REN signal is transmitted only to the wireless station having the minimum update number. Then, the REN signal is transmitted after increasing the number of updates of the transmission destination radio station.
[0049]
Each time the source wireless station S desires to communicate with the destination wireless station D, it calculates a routing reference index γ for a plurality of inter-node separation routes from the wireless stations S to D. From these multiple routes, the source radio station S looks up the active node list and (as described above) maximizes the degree of inter-zone separation and the shortest multipath (ie, minimum) between radio stations S and D. Multipath with a routing criterion index γ). However, due to mobility and slowness of information penetration, it may not be possible for the source radio station to completely calculate the multipath with the smallest routing reference index γ between radio stations S and D. is there. To improve performance under these circumstances, each source radio station performs its calculations periodically and adaptively modifies its routing decisions.
[0050]
In the present embodiment, the NLS table is used to distribute the topology information to only one adjacent wireless station using a directional antenna. Therefore, compared to the case of using a conventional non-directional beam (Non-Patent Document 6). The overhead can be greatly reduced. Further, by utilizing the number of updates, the latestness of peripheral wireless stations can be averaged.
[0051]
Hereinafter, a method of calculating the routing reference index γ for each path when a plurality of paths exist between the source wireless station S and the destination wireless station D will be described.
[0052]
The influence of the inter-route coupling as shown in FIGS. 13 and 14 is greatly increased if each station in the ad hoc wireless network uses a directional antenna (ie, variable beam antenna 101) instead of the omni-directional antenna. Can be dramatically reduced. It has been shown that the use of directional antennas can significantly reduce radio interference, thereby improving the use of wireless media and consequently increasing network throughput. reference.).
[0053]
In the concept of the inter-zone separation route in the wireless medium proposed in the embodiment according to the present invention, when data communication on one path does not interfere with data communication on another path, both paths are assumed to be inter-zone separation. Is done. However, capturing an inter-zone separation route in an ad hoc wireless network using an omni-directional antenna, or even partially capturing an inter-zone separation route, requires that the service area of each wireless station 1 be It is difficult because it is large compared to the case of a directional antenna. When the radio station 1-n forms a transmission beam with the beam angle θ in the horizontal plane and the radius R of the transmission range with respect to the radio station 1-n, the coverage from the radio station 1-n is the service area A _n (Θ), θ × R ² / 2. In the case of an omnidirectional antenna having a beam angle θ = 2π, the service area A _n (2π) = πR ² It is. Therefore, one way to reduce the service area of the radio station, and thus reduce the inter-route coupling, is to use a directional antenna whose beam angle θ is much less than 360 °.
[0054]
Next, the concept of the inter-node separation route and the inter-zone separation route will be described. Most of the research on multipath routing in the ad hoc wireless network to date has been based on a plurality of separated paths / nodes between a source wireless station S and a destination wireless station D for effective multipath routing with proper load balancing. We are trying to find a path that maximizes the degree of isolation between nodes. Two (or more than two) paths between wireless stations S and D are said to be "inter-node separation" if they do not share a common wireless station other than wireless stations S and D. However, due to inter-route coupling in a wireless environment, an inter-node separation route may not be a sufficient condition for improved performance in this context. In the present embodiment, the concept of the "inter-zone separation route" in the wireless medium is proposed. Here, when data communication on one path does not interfere with data communication on the other path, both paths are separated by the zone. Called. In other words, the two (or more than two) paths between the radio stations S and D are called "inter-zone separation" when the route-to-route coupling between them is zero.
[0055]
In Non-Patent Document 4, the effect of inter-route coupling is measured using a correlation coefficient η. In this document, the correlation coefficient η of the wireless station 1-n on the path p ⁿ (P) is defined as the number of active neighboring wireless stations of the wireless station 1-n that do not belong to the path p (the wireless link of the other wireless station 1 in the service area of the wireless station 1-n to the path p) Where the active neighboring wireless station of the wireless station 1-n is at that moment active in any communication process within the service area of the wireless station 1-n. It is defined as the participating (communicating) radio station. For example, in FIG. 14, a source wireless station S and a destination wireless station D communicate using two paths {S-1a-1b-1c-D} and {S-1d-1e-1f-D}. I have. Therefore, in communication in this context, all wireless stations are active wireless stations. Here, the active neighboring wireless station of the wireless station 1a is {S, 1d, 1e, 1b}. Therefore, the correlation coefficient of the wireless station 1a on the path p, that is, the path p {S-1a-1b-1c-D} is η ^a (P) = “the number of active neighboring wireless stations that do not belong to the path p”, that is, 2.
[0056]
The correlation coefficient η of the path p, ie, η (p), is defined as the sum of the correlation coefficients of all the wireless stations 1 on the path p. In other words, the correlation coefficient of the path p is obtained by counting the number of links between a wireless station on the path p and a wireless station on another path. When the correlation coefficient η (p) = 0, path p is said to be an inter-zone separation with respect to all other active paths. Here, the active path indicates a path that is involved in the communication process at that time. If the correlation coefficient η (p) = 0 is not satisfied, the path p is related to other active paths with a correlation coefficient η.
[0057]
It has been found that the larger the correlation coefficient, the larger the average end-to-end delay time for both paths (Non-Patent Document 4). This is because, as the correlation coefficient between the two paths increases, the opportunity for the two paths to interfere with each other's transmission increases due to the broadcast characteristic of wireless propagation. In addition, the larger the correlation coefficient, the greater the difference between end-to-end delay times along multiple paths. Based on this study, it can be concluded that the success of multipath routing in ad hoc wireless networks depends largely on the correlation coefficient between multiple routes.
[0058]
However, when using an omni-directional antenna, it is difficult to capture a complete inter-zone separation route. As shown in FIG. 14, since the node wireless stations 1a and 1d are both within the omnidirectional transmission range of the source wireless station S, the RTS from the source wireless station S to the node wireless station 1a simultaneously transmits the destination wireless station. Disable station D. Similarly, the CTS from destination radio station D disables both node radio stations 1c and 1f because both node radio stations 1c and 1f are within the omnidirectional transmission range of destination radio station D. Thus, when using two multipaths and omni-directional antennas between stations S and D, the smallest possible correlation coefficient η value is 2. This is called the minimum correlation coefficient η ^min That. More specifically, the minimum correlation coefficient η ^min Is the value of the smallest correlation coefficient among the correlation coefficients of the nodes in the path.
[0059]
In the case of the variable beam antenna 101, it is possible to separate (decouple) these two routes to make them completely inter-zone separated. For example, if each wireless station 1 in FIG. 6 uses the variable beam antenna 101 and each wireless station 1 sets its service area only to the target wireless station 1, the path {S-1a-1b- Communication between 1c-D} does not affect communication between paths {S-1d-1e-1f-D}. FIG. 6 shows two paths {S-1a-1b-1c-D} having a correlation coefficient η of 0 between a source wireless station S and a destination wireless station D in an ad hoc wireless network similar to FIG. FIG. 9 is a plan view showing an arrangement of each wireless station on a path and an antenna radiation pattern when {S-1d-1e-1f-D} exists. In the case of the prior art shown in FIG. 14, the correlation coefficient η between the paths {S-1a-1b-1c-D} and {S-1d-1e-1f-D} was 7, whereas Thus, it can be seen that in the case of the present embodiment in FIG. 6, the separation between zones is achieved between the two paths. Therefore, the minimum correlation coefficient η when using the omnidirectional antenna ^min (Omnidirectional) = 2, minimum correlation coefficient η when using directional antenna ^min (Directivity) = 0.
[0060]
As a result, even if an omni-directional antenna is used to capture a plurality of inter-zone separation routes having the smallest correlation coefficient, the packet arrival rate at the destination wireless station in the best case is 2 × t _p Each packet is one packet. Here, time t _p Is the average delay per hop for packets of the traffic stream on path p. This best case assumes a single traffic stream from the source radio station S to the destination radio station D in the network with error-free packet transmission. On the other hand, if the variable beam antenna 101 is used, the best case packet arrival rate at the destination radio station is time t _p Each packet is one packet. The timing charts of FIG. 7 (this embodiment) and FIG. 15 (prior art) illustrate this point.
[0061]
Referring to FIG. 14, it is assumed that each wireless station 1 is provided with an omnidirectional antenna. Further assume that the two paths shown have the smallest correlation coefficient, ie, η = 2. This implies that the node radio stations {1a, 1b, 1c} and the node radio stations {1d, 1e, 1f} are separated from each other. Hereinafter, t _p Denotes a time (timing), and one packet is transmitted from one wireless station to another wireless station at each time.
[0062]
Considering FIG. 15, the source wireless station S is located in the time interval T ₀ At the data packet P ₁ Is transmitted to the node wireless station 1a, and the node wireless station 1a transmits the next time interval, that is, T ₁ At the data packet P ₁ Is transmitted to the node wireless station 1b. In the case of an omni-directional antenna, the source wireless station S is in the time interval T ₁ During this period, it is necessary to hold the idle state because the RTS is received from the node wireless station 1a. Therefore, the source wireless station S sends its second packet P ₂ To time interval T ₂ Only after that, it can be sent to the node wireless station 1d (the first node wireless station in the second path). FIG. 15 shows the transition of the packet, and the destination wireless station D receives the packet in every other time interval. Even if the number of paths between the radio stations S and D is increased beyond two, the situation will not be improved if an omnidirectional antenna is used.
[0063]
However, if the variable beam antenna 101 is used, when the node wireless station 1a is sending a packet to the node wireless station 1b, the source wireless station S can simultaneously send a packet to the node wireless station 1d. FIG. 7 shows two inter-zone separation paths {S-1a-1b-1c-D} and {S-1d-1e-) having the minimum correlation coefficient η = 0 of FIG. 6 when a directional antenna is used. 5 is a timing chart when transmitting a packet via 1f-D}. As shown in FIG. 7, when the variable beam antenna 101 is used, the destination wireless station D uses all the time intervals T ₀ , T ₁ , T ₂ ,... Receive the packet. It has to be noted here that the separation between the two zones when using the variable beam antenna 101 is sufficient to achieve this best case method.
[0064]
Next, multiplex communication by multipath routing when there are a plurality of source wireless stations and a plurality of destination wireless stations will be described. So far, we have considered communication over a single pair of wireless stations S and D. However, the situation worsens when considering multiple pairs of wireless stations S and D involved in simultaneous communication. Each pair of the wireless stations S and D selects two multipaths between them with the smallest possible correlation coefficient η between them. However, in the context of a plurality of pairs of radio stations S and D, for example, even if the two multi-paths between radio stations S1 and D1 are inter-zone separations, the paths are, for example, between radio stations S2 and D2. It may be coupled to other active routes. Thus, we consider all active routes, find the correlation coefficient η associated with each of the other active routes, for each of them, and measure the degree of inter-zone separation for all active routes in the system, not only with respect to each other. It is essential to determine the maximum inter-zone separation multipath between the pair of wireless stations S and D such that is maximized.
[0065]
However, this alone is not enough to improve performance. In multipath routing, the path length is another important factor (Non-Patent Document 4). Longer paths with more hop counts H increase end-to-end delay time and waste more bandwidth. Thus, even if the longer bypass route between the pair of stations S and D has a small correlation coefficient η, it may not be very effective in reducing the end-to-end delay time. To address this problem, we use the minimization of the product of the correlation coefficient η and the number of hops H as the basis for route selection. When the value of this product is minimized, the shortest path in which the degree of separation between zones is maximized can be obtained. The value of this product is called a routing reference index γ (= η × H).
[0066]
However, this is a difficult task in the dynamic environment of ad hoc wireless networks where topology and communication patterns change. Approximate solutions to alleviate this difficulty will be discussed later. Here, the mechanism for finding the shortest multipath with the maximum degree of separation between zones in a plurality of pairs of wireless stations S and D will be discussed. In this context, the variable beam antenna 101 over the omnidirectional antenna will be discussed. Indicates effectiveness. To this end, we first assumed a static scenario in a simulation environment. It is assumed that each wireless station is aware of the exact topology and communication patterns in the network. The algorithm shown in the flowchart of FIG. 8 is used to determine the shortest path in which the degree of separation between zones between the radio stations S and D is maximized.
[0067]
FIG. 8 is a flowchart showing the routing and communication processing executed by the management control unit 151 in the traffic monitor unit 105.
[0068]
In step S1 of FIG. 8, referring to the GLS table, all the paths p1 between the source wireless station S and the destination wireless station D whose hop count H is smaller than the maximum value Hmax and are separated from each other by nodes. , ..., pn by searching. In the present embodiment, the maximum value Hmax of the number of hops is set to, for example, 5. In step S2, all paths p1,..., Pn are set assuming that they are active (assumed), and the communication state flag value for the node radio stations included in the paths p1,. I do. At this time, the communication status flag value in the GLS table is 1 because the node wireless station on the path searched between the pair of the wireless stations S and D and the wireless stations S and D are not actually communicating. And the node wireless station on the active path between the pair of the source wireless station and the destination wireless station.
[0069]
In step S3, if the number of paths found in step S2 is two or less, the process proceeds to step S6. If not, then in step S4, referring to the GLS table, for the path pi set (assumed) assuming each active in step S2, the source radio station S and the destination radio station D Calculate the correlation coefficient of path pi with respect to the set (assumed) path assuming to be active other than the path pi between the source and destination radio stations other than the radio stations S and D By calculating the correlation coefficient of the path pi with respect to the active path in between, and multiplying the sum of the two calculated correlation coefficients by the number of hops H of the path pi, the routing reference index γ of the path pi is calculated. . This step S4 is repeated until the routing criterion index γ is calculated for all paths pi set (assumed) assuming active. The calculation of the correlation coefficient is performed, as described above, in detail, as described above, other than the path pi between the source wireless station S and the destination wireless station D existing in the service area of each wireless station on the path pi. And the number of radio stations on the path (ie, the interfering stations for the radio stations on the path pi) set (assumed) as the source radio station and the destination radio station other than the radio stations S and D. This is performed by calculating the number of radio stations on the active path between the stations (interference stations for radio stations on the path pi) and adding the calculated number of radio stations (interference stations) for each path pi. You.
[0070]
Next, in step S5, the path having the maximum routing reference index γ is set assuming that it is not active (assumed), and the communication state flag value for the node wireless station included in the path in the GLS table is set to 0. After step S5, it is again determined in step S3 whether the number of paths set (assumed) assuming active is less than or equal to two. When step S3 is NO, step S4 is repeated until the number of paths set (assumed) assuming active is two (that is, two paths having the largest routing reference index γ). Repeat steps S3 to S5 (until a path is found). In this iteration, the recalculation of the routing criterion index in step S4 each time the number of paths is reduced by step S5 is set assuming that there is an active between the radio stations S and D (assumed. This is because when the number of paths changes, the correlation coefficient of the path set (assumed) assuming each active path with other paths changes. In the flow, if three or more paths are searched in step S1, it is finally determined (assumed) that all paths are assumed to be active in the calculation in step S4. Different states (ie, only two paths are active), or some approximation.
[0071]
When step S3 is YES, the process proceeds to step S6. In step S6, the node radios included in the two paths (paths pa and pb) set (assumed) assuming that they are finally active between the source radio station S and the destination radio station D. The active node list information for the station is transmitted to other node radio stations according to the LVNF standard, and the GLS table of each node radio station is updated. Next, in step S7, the source wireless station S communicates with the destination wireless station via these paths pa and pb based on relaying the routing information included in the header or the like of the packet. This communication is not limited to one-way communication from the source wireless station S to the destination wireless station D, but may be two-way communication between these two wireless stations. After the end of the communication, in step S8, the communication status flag value for the node radio stations included in the paths pa and pb in the GLS table is set to 0, and the active node list information for the node radio stations included in the paths pa and pb is set to the LVNF reference. To the other node radio stations according to the above, and the GLS table of each node radio station is updated.
[0072]
As described above, according to the present embodiment, the source wireless station S can calculate the routing reference index γ at high speed and execute communication with the destination wireless station D.
[0073]
<Second embodiment>
Hereinafter, a routing method for a wireless network according to the second embodiment of the present invention will be described. This embodiment differs from the first embodiment only in the routing and communication processing executed by the management control unit 151 in the traffic monitor unit 105.
[0074]
FIG. 9 is a flowchart showing a routing and communication process executed by the management control unit 151 in the traffic monitor unit 105 in the ad hoc wireless network according to the second embodiment of the present invention.
[0075]
In step S11 in FIG. 9, the communication status flag value in the GLS table is initialized to 0. In step S12, referring to the GLS table, all paths p1,..., Between the source wireless station S and the destination wireless station D, where the number of hops H is smaller than the maximum value Hmax and are separated from each other by nodes. Search and find pn. In step S13, two paths pi and pj (a pair of paths) are selected from all the searched paths p1,..., Pn, and set assuming that they are active (assumed). The communication state flag value for the node radio station included in the paths pi and pj in the GLS table is set to 1. At this time, the communication state flag value in the GLS table is 1 because the node radio stations on the paths pi and pj between the pair of the radio stations S and D are actually communicating with each other except for the radio stations S and D. And the node wireless station on the active path between the pair of the source wireless station and the destination wireless station. Next, in step S14, the correlation coefficient of the path pi with respect to the path pj is calculated with reference to the GLS table, and the phase of the path pi with respect to the active path between the source wireless station and the destination wireless station other than the wireless stations S and D is calculated. By calculating the relationship number and multiplying the calculated sum of the two types of correlation coefficients by the hop number H of the path pi, the routing reference index γ of the path pi _{i, j} Is calculated. The calculation of the correlation coefficient is performed, as described above, in detail, as described above, the radio station on the path pj (ie, the interfering station for the radio station on the path pi) existing in the service area of each radio station on the path pi. And the number of radio stations on the active path between the source radio station and the destination radio station other than the radio stations S and D (interference stations for the radio stations on the path pi), and the calculated radio This is performed by adding the number of stations (interfering stations).
[0076]
In step S15, similarly, the correlation coefficient of the path pj with respect to the path pi is calculated with reference to the GLS table, and the phase of the path pj with respect to the active path between the source wireless station and the destination wireless station other than the wireless stations S and D is calculated. By calculating the relationship number and multiplying the sum of the two calculated correlation coefficients by the hop number H of the path pj, the routing reference index γ of the path pj is calculated. _{j, i} Is calculated. Next, in step S16, the routing reference index γ _{i, j} And γ _{j, i} Is calculated, and the communication state flag value for the node radio station included in the paths pi and pj in the GLS table is set to 0. Steps S13 to S16 are repeated until it is determined in step S17 that the routing reference index γ has been calculated for all combinations of path pairs among the paths p1,..., Pn. When step S17 is NO, the process returns to step S13 to consider that another pair of path pairs is active and calculates the routing reference index γ, and when step S17 is YES, the process proceeds to step S18. .
[0077]
In step S18, a pair of paths (hereinafter, paths pa and pb) corresponding to the minimum routing reference index γ is selected, and the communication state flag value for the node radio station included in the paths pa and pb in the GLS table To 1. In step S19, the active node list information for the node wireless stations included in the paths pa and pb is transmitted to other node wireless stations according to the LVNF standard, and the GLS table of each node wireless station is updated. Next, in step S20, the source wireless station S communicates with the destination wireless station via these paths pa and pb based on relaying the routing information included in the header or the like of the packet. After the communication is completed, in step S21, the communication state flag value for the node wireless stations included in the paths pa and pb in the GLS table is set to 0, and the active node list information for the node wireless stations included in the paths pa and pb is set to the LVNF reference. To the other node radio stations according to the above, and the GLS table of each node radio station is updated.
[0078]
In order to compare the calculation amounts of the routing and communication processing according to the first and second embodiments, consider the case where eight paths are searched in step S1 and step S11. In the first embodiment, when step S4 is executed for the first time, the correlation coefficient η is calculated for eight paths, the path having the largest routing reference index γ is regarded as inactive in step S5, and step S4 is performed. When the second execution is performed, the correlation coefficient η is calculated for the seven paths, the path having the maximum routing reference index γ is regarded as inactive in step S5, and thereafter, the processing is repeated until the number of paths becomes two. Therefore, the calculation amount can be expressed as 8 + 7 + 6 + 5 + 4 + 3 = 33. On the other hand, in the second embodiment, since it is necessary to execute steps S14 and S15 for all combinations of the paths among the eight paths, the amount of calculation is reduced. ₈ C ₂ × 2 = 56.
[0079]
According to the routing and communication processing of the present embodiment, the amount of calculation increases as compared with the first embodiment, but an approximation similar to the routing and communication processing of the first embodiment (see step S4 in FIG. 8). , It is possible to calculate the routing reference index γ more accurately than in the first embodiment.
[0080]
【Example】
FIG. 10 is a graph showing a correlation coefficient η with respect to the number of wireless stations when an omnidirectional antenna is used in the ad hoc wireless network of FIG.
[0081]
We have used simulations to confirm that using a variable beam antenna 101 to capture a set of two inter-zone separation paths is much easier than using an omni-directional antenna. A survey was conducted. In this survey, wireless stations were randomly arranged in a 1000 × 1500 area at a predetermined density. The source and destination radio stations were randomly selected such that they were separated from each other by multiple hops. First, it is assumed that all the wireless stations 1 are provided with the variable beam antenna 101 having a fixed service area. It is assumed that the transmission zone angle of the beam formed by each variable beam antenna 101 is 60 °. Two inter-zone separation routes were found between the selected source and destination radio stations. If two inter-zone separation routes were not available for the source and destination wireless station pair, another source and destination wireless station pair was selected. Next, assuming that each wireless station has an omni-directional antenna, the correlation coefficient η between these two routes, which is an inter-zone separation for the variable beam antenna 101, _omni Was calculated. This experiment was repeated for 25 source and destination wireless station pairs. As described above, in each case, the correlation coefficient η when the variable beam antenna 101 is used. _dir Is zero and the correlation coefficient η with an omni-directional antenna is _omni Is calculated. Next, the correlation coefficient η _omni Was calculated. Next, the same experiment was repeated while changing the distribution density of the radio stations.
[0082]
FIG. 10 shows the result of the simulation described above. As the number of wireless stations in the system increases, the correlation coefficient η _omni Also increased. However, the correlation coefficient η when the variable beam antenna 101 is provided _dir Is zero throughout all cases. This is because, even if the variable beam antenna 101 is used, the inter-zone separation path can be captured even at different radio station densities. However, when the variable beam antenna 101 is used, these inter-zone separation paths are omnidirectional. This indicates that the antenna has a high correlation coefficient when the directional antenna is substituted.
[0083]
Next, a description will be given of a simulation result regarding multiplex communication using multipath routing when there are a plurality of source wireless stations and a plurality of destination wireless stations.
[0084]
FIG. 11 is a graph showing the average value of the routing reference index γ for the multipath between the source wireless station S and the destination wireless station D with respect to the number of simultaneous communications in the ad hoc wireless network of FIG. The simulation begins by finding the shortest path that maximizes the degree of separation between the two zones between a single pair of stations S and D. Next, the number of pairs of the radio stations S and D is increased by one, and the shortest path in which the degree of separation between zones is maximized in the newly added pair of the radio stations S and D is calculated. Recalculate the multipath routing criterion index γ for the S and D pair and observe the effect of multiple simultaneous communications on the value of the multipath routing criterion index γ for the first wireless station S and D pair.
[0085]
This experiment is repeated using several sets of radio stations S and D pairs and both the variable beam antenna 101 and the omni-directional antenna. The results shown in FIG. 11 show that the increase of the routing reference index γ is quite sharp when using an omni-directional antenna. This means that as the number of radio station S and D pairs in the system increases, the inter-route coupling for the other active routes of a particular radio station S and D pair, in the case of an omni-directional antenna, becomes a variable beam antenna. This implies that the increase is much faster than in the case of 101.
[0086]
Next, simulation results regarding the performance of multipath routing using the variable beam antenna 101 will be described. FIG. 12 is a graph showing an average value of the end-to-end delay time with respect to the number of simultaneous communications in the ad hoc wireless network of FIG.
[0087]
Due to the mobility and the slowness of information penetration, it is not possible for the source radio station to completely calculate the shortest multipath with the maximum degree of inter-zone separation between radio stations S and D. There are cases. To improve performance under these circumstances, each source radio station performs its calculations periodically and adaptively modifies its routing decisions. We incorporate this point into our simulation environment, use an omnidirectional antenna and a variable beam antenna 101, increase the number of simultaneous communications, and increase the number of packets between the selected set of wireless stations S and D. We observed the average end-to-end delay time per hit. The timing assumptions are the same as described above. FIG. 12 shows the result. The unit on the vertical axis is the average required time when one packet is transmitted from one wireless station to another wireless station in one hop. The results show that, as the number of simultaneous communications increases, the average end-to-end delay time per packet increases dramatically when using an omni-directional antenna rather than with the variable beam antenna 101. Is shown. This is a natural consequence of the phenomenon shown in FIG. 11, and it is concluded that the use of the variable beam antenna 101 is significantly improved with respect to the routing performance using a plurality of paths, compared with the case of using an omnidirectional antenna. be able to.
[0088]
As described above, according to the embodiment of the present invention, the effect of the directional antenna on the multipath routing was investigated, and the effectiveness was compared with the multipath routing using the omnidirectional antenna. In conclusion, it can be said that the routing performance using a plurality of paths is significantly improved when the directional antenna is used as compared with the case where the omnidirectional antenna is used. By applying multipath routing techniques to ad hoc wireless networks, the effects of unreliable wireless links and constantly changing topologies can be reduced. Further, in an ad hoc wireless network, it is possible to promote the reduction of end-to-end delay time and the execution of load balancing.
[0089]
【The invention's effect】
As described in detail above, according to the routing method or the wireless communication system for a wireless network according to the present invention, based on an information table indicating a link state between a plurality of wireless stations, a source wireless station and a destination are determined. Searching for a plurality of paths including at least one wireless station as a relay station and not including a common wireless station as a relay station with the wireless station;
In the wireless network, the wireless stations on the plurality of paths searched are set assuming wireless stations during wireless communication,
Based on the set wireless communication stations, calculate the number of other communicating wireless stations in the service area of each wireless station on each path, and calculate the calculated number of communicating wireless stations. By adding the number of wireless stations for each of the paths, a correlation coefficient indicating the degree of coupling with respect to each path with respect to radio wave coherence with another communicating wireless station that is not included in the path itself. Is calculated by multiplying the calculated correlation coefficient for each path by the number of hops of the path, thereby obtaining a routing reference index for searching for the shortest path separated from other communicating wireless stations without radio wave interference. And calculate
Of the routing reference indices for each of the calculated paths, a wireless station included in the path having the largest reference index is set as a wireless station that is not communicating,
A process of calculating a routing reference index for each path and a process of setting a wireless station included in the path having the largest reference index as a wireless station not communicating are repeated, and two smaller reference indices are calculated. A pair of paths is selected as two paths between the source wireless station and the destination wireless station, and control is performed so that routing is performed using the selected two paths.
[0090]
According to a routing method or a wireless communication system for a wireless network according to another aspect of the present invention, based on an information table indicating a link state between a plurality of wireless stations, a communication between a source wireless station and a destination wireless station is performed. Searching for a plurality of paths that include at least one wireless station as a relay station and do not include a wireless station common to each other as a relay station,
In the wireless network, wireless stations on each pair of buses among the plurality of searched paths are set assuming wireless stations in communication, and each wireless station on each pair of paths is set. By calculating the number of other communicating wireless stations existing in the service area and adding the calculated number of communicating wireless stations for each pair of paths, the pair of paths , A correlation coefficient indicating the degree of coupling with respect to radio wave coherence with another communicating wireless station not included in the path itself is calculated, and the calculated correlation coefficient is calculated for each pair of paths. By multiplying the number of hops of the path, a routing reference index is calculated for each pair of the paths for searching for the shortest path apart from other communicating wireless stations without radio interference,
Among the calculated routing reference indices for each pair of paths, a pair of paths having two smaller reference indices is selected as two paths between the source wireless station and the destination wireless station. Then, control is performed so that routing is performed using the two selected paths.
[0091]
Therefore, based on an information table indicating a link state between a plurality of wireless stations, a pair of paths is searched with a smaller amount of calculation compared to the related art based on the minimum correlation coefficient and the shortest hop number. Thus, multipath routing can be performed, and at this time, the end-to-end delay time can be significantly reduced.
[Brief description of the drawings]
FIG. 1 is a plan layout view of a plurality of wireless stations 1-1 to 1-9 constituting an ad hoc wireless network according to a first embodiment of the present invention.
FIG. 2 is a block diagram showing an internal configuration of each wireless station 1 of FIG.
FIG. 3 is a diagram showing an example of a sector beam pattern of the variable beam antenna 101 of FIG.
FIG. 4 is a diagram illustrating an example of an adjacent link state table (NLS table) stored in a database memory 154 of FIG. 2;
FIG. 5 is a diagram illustrating an example of a global link state table (GLS table) stored in a database memory 154 of FIG. 2;
FIG. 6 shows two paths {S-1a-1b-1c-D} having a correlation coefficient η of 0 between a source wireless station S and a destination wireless station D in an ad hoc wireless network similar to FIG. FIG. 9 is a plan view showing an arrangement of each wireless station on a path and an antenna radiation pattern when {S-1d-1e-1f-D} exists.
FIG. 7 is a timing chart when a packet is transmitted via two paths {S-1a-1b-1c-D} and {S-1d-1e-1f-D} of FIG. 6;
FIG. 8 is a flowchart showing a routing and communication process executed by the management control unit 151 in the traffic monitor unit 105 of FIG.
FIG. 9 is a flowchart showing a routing and communication process executed by the management control unit 151 in the traffic monitor unit 105 of FIG. 2 in the ad hoc wireless network according to the second embodiment of the present invention.
10 is a graph showing a correlation coefficient η with respect to the number of wireless stations when an omnidirectional antenna is used in the ad hoc wireless network of FIG.
11 is a graph showing an average value of a routing reference index γ for a multipath between a source wireless station S and a destination wireless station D with respect to the number of simultaneous communications in the ad hoc wireless network of FIG. 1;
FIG. 12 is a graph showing an average value of an end-to-end delay time with respect to the number of simultaneous communications in the ad hoc wireless network of FIG. 1;
FIG. 13 shows multipath routing according to the prior art, wherein two paths {S-x1-x2-D} and {S-y1-y2-D} are provided between a source wireless station S and a destination wireless station D; FIG. 9 is a plan layout view of wireless stations and routes on a path, showing that inter-route coupling has occurred between paths when ときに exists.
FIG. 14 shows a multipath routing according to the prior art, in which two paths {S-1a-1b-1c-D including a plurality of inter-route couplings between a source wireless station S and a destination wireless station D; It is a top view which shows arrangement | positioning of each radio | wireless station on a path | route, and antenna radiation pattern when {and {S-1d-1e-1f-D} exist.
15 is a timing chart when a packet is transmitted via two paths {S-1a-1b-1c-D} and {S-1d-1e-1f-D} in FIG.
[Explanation of symbols]
1, 1-1 to 1-9, 1a to 1f, S, D ... wireless station,
101 ... variable beam antenna,
102: circulator,
103 ... pointing control unit,
104: Packet transmitting / receiving unit
105: traffic monitor unit
106 ... line control unit,
107: Upper layer processing device,
130 ... Packet receiving unit,
131 ... high frequency receiver,
132 demodulator,
133: reception buffer memory,
140 ... packet transmitting unit,
141: transmission timing control unit,
142 transmission buffer memory,
143: modulator,
144: high frequency transmitter,
151 management and control unit
152 ... search engine,
153 ... Update engine,
154: database memory,
155: clock circuit,
160 ... spreading code generator,
200 to 204: Service area.

Claims

A routing method for a wireless network comprising a plurality of wireless stations and performing wireless communication between the wireless stations,
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. A first step of searching for a plurality of paths not included as stations;
In the wireless network, a second step of assuming and setting wireless stations on the plurality of paths searched as wireless stations performing wireless communication;
Based on the set wireless communication stations, calculate the number of other communicating wireless stations in the service area of each wireless station on each path, and calculate the calculated number of communicating wireless stations. By adding the number of wireless stations for each of the paths, a correlation coefficient indicating the degree of coupling with respect to each path with respect to radio wave coherence with another communicating wireless station that is not included in the path itself. Is calculated by multiplying the calculated correlation coefficient for each path by the number of hops of the path, thereby obtaining a routing reference index for searching for the shortest path separated from other communicating wireless stations without radio wave interference. A third step of calculating
A fourth step of setting a wireless station included in the path having the largest reference index among the calculated routing reference indexes for each path as a wireless station that is not communicating;
Repeating the third and fourth steps to select a pair of paths having two smaller reference indices as two paths between the source wireless station and the destination wireless station; Routing using two paths, and a routing method for a wireless network.

In a wireless communication system for a wireless network comprising a plurality of wireless stations and performing wireless communication between each wireless station,
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. Search for multiple paths not included as stations,
In the wireless network, the wireless stations on the plurality of paths searched are set assuming wireless stations during wireless communication,
Based on the set wireless communication stations, calculate the number of other communicating wireless stations in the service area of each wireless station on each path, and calculate the calculated number of communicating wireless stations. By adding the number of wireless stations for each of the paths, a correlation coefficient indicating the degree of coupling with respect to each path with respect to radio wave coherence with another communicating wireless station that is not included in the path itself. Is calculated by multiplying the calculated correlation coefficient for each path by the number of hops of the path, thereby obtaining a routing reference index for searching for the shortest path separated from other communicating wireless stations without radio wave interference. And calculate
Of the routing reference indices for each of the calculated paths, a wireless station included in the path having the largest reference index is set as a wireless station that is not communicating,
A process of calculating a routing reference index for each path and a process of setting a wireless station included in the path having the largest reference index as a wireless station not communicating are repeated, and two smaller reference indices are calculated. Control means for selecting a pair of paths as two paths between the source wireless station and the destination wireless station and performing routing using the selected two paths. A wireless communication system, comprising:

A routing method for a wireless network comprising a plurality of wireless stations and performing wireless communication between the wireless stations,
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. Searching for a plurality of paths that are not included as stations, and setting, in the wireless network, assuming a wireless station on each pair of buses of the searched plurality of paths as a communicating wireless station; The number of other communicating wireless stations existing in the service area of each wireless station on each pair of paths is calculated, and the calculated number of communicating wireless stations is calculated for each pair of paths. By adding each time, a correlation coefficient indicating the degree of coupling of radio wave coherence with respect to each pair of paths with another communicating wireless station not included in the path itself is calculated. For each pair of paths calculated By multiplying the correlation coefficient by the number of hops of the path, a routing reference index is calculated for each pair of the paths for searching for the shortest path apart from other communicating wireless stations without radio interference. Steps to
Among the calculated routing reference indices for each pair of paths, a pair of paths having two smaller reference indices is selected as two paths between the source wireless station and the destination wireless station. And routing using the two selected paths. 15. A routing method for a wireless network, comprising:

In a wireless communication system for a wireless network comprising a plurality of wireless stations and performing wireless communication between each wireless station,
Based on the information table representing the link state between the plurality of wireless stations, at least one wireless station is included as a relay station and a common wireless station is relayed between the source wireless station and the destination wireless station. Search for multiple paths not included as stations,
In the wireless network, wireless stations on each pair of buses among the plurality of searched paths are set assuming wireless stations in communication, and each wireless station on each pair of paths is set. By calculating the number of other communicating wireless stations existing in the service area and adding the calculated number of communicating wireless stations for each pair of paths, the pair of paths , A correlation coefficient indicating the degree of coupling with respect to radio wave coherence with another communicating wireless station not included in the path itself is calculated, and the calculated correlation coefficient is calculated for each pair of paths. By multiplying the number of hops of the path, a routing reference index is calculated for each pair of the paths for searching for the shortest path apart from other communicating wireless stations without radio interference,
Among the calculated routing reference indices for each pair of paths, a pair of paths having two smaller reference indices is selected as two paths between the source wireless station and the destination wireless station. And a control means for controlling routing using the two selected paths.