(57)【要約】本発明は、少なくとも一つの第二の無線通信デバイス（w）と無線ネットワークを形成する第一の無線通信デバイスのためのアンテナ・パターン割り当てを最適化する方法であって、各通信デバイス（u,w）はマルチセクター・アンテナを備え、アンテナ・パターンは前記アンテナ・セクターの組み合わせであり、前記通信デバイス（u,w）は現在アンテナ・パターン割り当てを使って要求を送り、応答を受信するよう適応されており、当該方法は：・前記第一の通信デバイス（u）によって第一の値S*uを評価する段階と；・前記第一の通信デバイス（u）によって前記第二の通信デバイス（w）に、前記値S*uを含むブロードキャスト要求を送る段階と；・前記第一の通信デバイス（u）によって、前記ブロードキャスト要求を送る日時に依存して第一のタイムアウトを設定する段階と；・前記第一の通信デバイス（u）によって、前記第二の通信デバイス（w）によって送られる、前記ブロードキャスト要求への応答を受信する段階であって、前記応答は前記第二のデバイス（w）によって評価された第二の値S*wに依存する、段階と；・前記第一の通信デバイス（u）によって、前記応答に依存して、新しいアンテナ・セクター割り当てに切り換えるか切り換えないかする段階とを含む、方法に関する。本発明によれば、前記第一の値S*uは、前記現在アンテナ・パターン割り当てを有する前記第一の通信デバイス（u）によって受信された受信信号強度（RSS）に従って第一のローカル関数Suを最小化することによって評価され、前記第二の値S*wは、独自の現在アンテナ・パターン割り当てについて前記第二の通信デバイス（w）によって受信された受信信号強度（RSS）に従って第二のローカル関数Swを最小化することによって評価される。
2013507813.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つの第二の無線通信デバイスと無線ネットワークを形成する第一の無線通信デバイスのためのアンテナ・パターン割り当てを最適化する方法であって、各通信デバイスはマルチセクター・アンテナを備え、アンテナ・パターンは前記アンテナ・セクターの組み合わせであり、前記通信デバイス（u,w）は現在アンテナ・パターン割り当てを使って要求を送り、応答を受信するよう適応されており、当該方法は：
・前記第一の通信デバイスによって第一の値S*uを評価する段階と；
・前記第一の通信デバイス（u）によって前記第二の通信デバイス（w）に、前記値S*uを含むブロードキャスト要求を送る段階と；
・前記第一の通信デバイスによって、前記ブロードキャスト要求を送る日時に依存して第一のタイムアウトを設定する段階と；
・前記第一の通信デバイスによって、前記第二の通信デバイスによって送られる、前記ブロードキャスト要求への応答を受信する段階であって、前記応答は前記第二のデバイスによって評価された第二の値S*wに依存する、段階と；
・前記第一の通信デバイスによって、前記応答に依存して、新しいアンテナ・セクター割り当てに切り換えるか切り換えないかする段階とを含み、
前記第一の値S*uが、前記現在アンテナ・パターン割り当てを有する前記第一の通信デバイスによって受信された受信信号強度（RSS）に従って第一のローカル関数Suを最小化することによって評価され、前記第二の値S*wが、独自の現在アンテナ・パターン割り当てについて前記第二の通信デバイスによって受信された受信信号強度（RSS）に従って第二のローカル関数Swを最小化することによって評価されることを特徴とする、
方法。
【請求項２】
前記第一の通信デバイスによって受信される応答は、前記第二の通信デバイスがS*u≧S*wと判定するときに否定的であることを特徴とする、請求項１記載の方法。
【請求項３】
前記第一の通信デバイスによって受信される応答は、前記第二の通信デバイスがS*u＜S*wと判定するときに肯定的であることを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記切り換える段階は、前記第一の通信デバイスによって前記第一のタイムアウト期間内に諸前記第二の通信デバイスから受信される諸応答が肯定的である場合に、前記第一の通信デバイスによる前記現在アンテナ・パターン割り当てから新しいアンテナ・パターン割り当てへのものからなることを特徴とする、請求項２または３記載の方法。
【請求項５】
前記第二の通信デバイスが、前記第二のタイムアウトが満了するまで、または前記第二の通信デバイスが前記第一の通信デバイスから、前記第二の通信デバイスによって送られた応答の受信を受け取り確認するブロードキャスト確認を受信するとき、その現在のアンテナ・パターン割り当てを修正することを妨げられるさらなる段階を含むことを特徴とする、請求項１または４記載の方法。
【請求項６】
前記第一の通信デバイスが
【数１８】
2013507813.tif 000020
で与えられる関数Su(xu)を、制約条件
【数１９】
2013507813.tif 000021
のもとで、通信デバイス（u）の可能なあらゆるアンテナ・パターン割り当てxuにわたって最小化するアンテナ・パターン割り当て（xu*）および対応する最適値S*u＝Su(xu*)を計算し、ここで、上記の式(13)および(14)において、
E'は、ネットワーク中で通信デバイス（i）を通信デバイス（j）に接続するリンク（i,j）のうち、データが現在送られているリンクの集合を表し、
I(i)は、通信デバイス（i）における干渉を引き起こしうるネットワーク中の通信デバイスの集合を表し、
通信デバイス（u）の一ホップ干渉近傍デバイスであるすべての通信デバイス（w）｛w:  w∈I(u),u∈I(w)｝および通信デバイス（u）の一ホップ通信近傍デバイスであるすべての通信デバイス（v）｛v:  (u,v)∈E'｝は、それぞれのアンテナ・パターン割り当て(xw,xv)を固定したままに保持し、
【数２０】
2013507813.tif 000022
の表現は、通信デバイス（i）がアンテナ・パターン割り当て（xi）を使って送信し、通信デバイス(j)がアンテナ・パターン割り当て（xj）を使って受信する場合の、通信デバイス（i）と通信デバイス(j)を接続するリンク(i,,j)に対する通信デバイス（j）における受信信号強度を表し、
表現RSSij00は、通信デバイス（i）が全方向性アンテナ・パターン割り当てxi＝0を使って送信し、通信デバイス(j)が全方向性アンテナ・パターン割り当てxj＝0を使って受信する場合の、リンク(i,j)に対する通信デバイス（j）における受信信号強度を表し、
Cthは閾値パラメータである、
ことを特徴とする、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
前記第一の通信デバイスが実行するS*uについての評価は、S*wを評価するための前記第二の通信デバイスによって実行される評価と同一であることを特徴とする、請求項２ないし５のうちいずれか一項記載の方法。
【請求項８】
前記第一の通信デバイスは全方向性アンテナ・パターンを使って前記ブロードキャスト要求を送ることを特徴とする、請求項１ないし７のうちいずれか一項記載の方法。
【請求項９】
前記第一の通信デバイスは諸第二の通信デバイスに、全方向性アンテナ・パターンを使って確認ブロードキャストを送り、新しいアンテナ・パターン割り当てとしてxu*を選択することを特徴とする、請求項１ないし６のうちいずれか一項記載の方法。
【請求項１０】
前記第一の通信デバイスが前記第二の通信デバイスから肯定的な応答を受信する場合、前記第二の通信デバイスは第二のタイムアウトを設定し、前記第二のタイムアウトの期限が切れるとき、または前記第二の通信デバイスが前記ブロードキャスト確認パケットを前記第一の通信デバイスから受信するとき、前記第二の通信デバイスはその現在のアンテナ・パターン割り当てを調整することが許されることを特徴とする、請求項３ないし９のうちいずれか一項記載の方法。
【請求項１１】
前記無線ネットワークが複数の通信装置を含み、前記複数の通信装置の各通信装置は、逐次前記第一の通信デバイスとしてはたらき、前記ブロードキャスト要求は前記複数の通信デバイスのうち他のすべての通信デバイスに送られることを特徴とする、請求項１ないし１０のうちいずれか一項記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信ネットワークの分野に関する。
【０００２】
本発明はより詳細には、無線ネットワークにおけるセクター化アンテナ（sectorized  antenna）を使ったトポロジー制御のための方法に関する。
【背景技術】
【０００３】
近年、無線（セルラー、802.11無線LANなど）ネットワークは、潜在的な高いデータ・レートの接続性、非常に低い展開コストおよびユーザーにとって無料または低コストのネットワーク・アクセスのため、著しい関心を集めている。いくつかの企業および大学は、多数のユーザーにサービスするために大規模な無線ネットワークを展開している。
【０００４】
無数の都会の領域はすでに無線ネットワークの密な展開でカバーされており、それらを使ってコミュニティー・メッシュ・ネットワークを形成する努力も進行中である（FON  WiFiコミュニティー。http://www.fon.com/en/）。
【０００５】
しかしながら、無線ネットワーク、特にIEEE802.11ネットワークは、無線媒体のブロードキャスト性および免許されないスペクトル帯域の使用のため、その容量を制限する深刻な干渉問題がある。セクター化アンテナは、より高い空間の再利用を通じて無線干渉を軽減するための魅力的な解決策である。セクター化アンテナは、電波信号エネルギーを、無指向性アンテナのようにあらゆる方向に放射するのではなく、特定の方向に集中することができる。主として、無線ネットワークにおいて指向性の通信を活用する二つのアプローチが存在する。指向性MACプロトコルおよびトポロジー制御プロトコルである。指向性MACプロトコル（非特許文献１および非特許文献２）は、非常に高速な（パケット毎の）時間スケールで異なる近隣者に通信するために異なるセクターの間で切り換えをすることによって、より高い空間の再利用を達成することをねらいとする。指向性MACプロトコルはまた、不可聴性（deafness）および方向性隠れ端末問題（directional  hidden  terminal  problem）に取り組むため、IEEE802.11のMACプロトコルに対する修正を要求する（非特許文献３）。他方、トポロジー制御プロトコル（非特許文献４〜７）は、標準のIEEE802.11MACプロトコルへの複雑な修正を必要とすることなく、潜在的にパフォーマンスを代償として、より遅い時間スケールで（1分またはそれ以上のスケールで）同時に複数のセクターをアクティブ化する。
【０００６】
これらすべての提案されるトポロジー制御解決策は、単純な干渉モデルの仮定（ペア毎の（pairwise）干渉のような）を使い、グラフ理論的なアルゴリズムを適応したものを使う。これらはいくつかの実際上の考察を無視し、シミュレーション研究を通じてのみ評価されている。他方、密に展開されたIEEE802.11ネットワークに対する近年の測定研究（非特許文献８、９）によれば、地理的に指向する（geographically  pointing）セクターの使用およびマルチセクター・アクティブ化に対する独立性といった一般的な設計上の仮定が、反射に富む、密な展開においては最適でないことが示されている。これらの研究はまた、方向性の隠れ端末問題を軽減することに対する、物理層捕捉の効果をも調査しており、セクター化アンテナがより高い空間再利用機会を提供できることを示している。しかしながら、これらの観察は、現実世界の密なIEEE802.11無線環境においてアンテナ・セクター化の容量の利得を抽出できる実際的なプロトコルに翻訳されていない。
【０００７】
IEEE802.11ベースの無線ネットワークにおけるセクター化アンテナおよびトポロジー制御の利用に対する過去の研究の大半は、解析的な研究ならびにシミュレーションを通じたプロトコル設計および評価に焦点を当てている。非特許文献６は、複数の単一セクター・アンテナからなるアンテナ・モデルを使い、メッシュ・ネットワークにおいて最小次数スパニング木（minimum  degree  spanning  tree）を構築する中央集中的アルゴリズムを提案している。非特許文献４、５は、送信電力調整およびマルチセクター・アンテナを使う二つの異なるトポロジー制御アプローチを提案している。最後に、非特許文献７は、メッシュ・ネットワークにおいてノードによって使用されるべき（アンテナ）通信パターンを決定する問題を考察しており、それを「スマート・アンテナ」（デジタル・アダプティブ・アレイ）を使うときの干渉最小化として定式化している。トポロジー制御のための現在のアプローチはすべて、理想化されたアンテナ・モデルを使い、ペア毎の干渉モデルを想定し、グラフ理論的なアルゴリズムに基づく解決策を提案しており、シミュレーションを通じてのみ評価されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】R.  Choudhury  and  N.H.  Vaidya、"Deafness:  A  Mac  Problem  in  Ad  Hoc  Networks  when  using  Directional  Antennas"、Proc.  IEEE  ICNP、October  2004
【非特許文献２】Y.  Ko,  V.  Shankarkumar  and  N.H.  Vaidya、"Medium  Access  Control  Protocols  Using  Directional  Antennas  in  Ad  Hoc  Networks"、In  Proc.  IEEE  INFOCOM、March  2000
【非特許文献３】R.  Choudhury,  X.  Yang,  R.  Ramanathan,  and  N.H  Vaidya、"Using  Directional  Antennas  for  Medium  Access  Control  in  Ad  Hoc  Networks"、Proc.  ACM  MobiCom、September  2002
【非特許文献４】Z.  Huang,  C.  Shen,  C.  Srisathapornphat,  and  C.  Jaikaeo、"Topology  Control  for  Ad  hoc  Networks  with  Directional  Antennas"、IEEE  Int.  Conference  on  Computer  Communications  and  Networks、2002
【非特許文献５】Zhuochuan  Huang  and  Chien-Chung  Shen、"Multibeam  Antenna-based  Topology  Control  with  Directional  Power  Intensity  for  Ad  Hoc  Networks"、5(5)、2006
【非特許文献６】U.  Kumar,  H.  Gupta,  and  S.R.  Das、"A  Topology  Control  Approach  to  using  Directional  Antennas  in  Wireless  Mesh  Networks"、Proc.  ICC、2006
【非特許文献７】K.  Sundaresan,  W.  Wang,  and  S.  Eidenbenz、"Algorithmic  Aspects  of  Communication  in  Ad-hoc  Networks  with  Smart  Antennas"、Proc.  ACM  MobiHoc、2006
【非特許文献８】M.  Blanco,  R.  Kokku,  K.  Ramachandran,  S.  Rangarajan,  and  K.  Sundaresan、On  the  Effectiveness  of  Switched  Beam  Antennas  in  Indoor  Environments、Proc.  Passive  and  Active  Measurements  Conference  (PAM)、2008
【非特許文献９】A.P.  Subramanian,  H.  Lundgren,  and  T.  Salonidis、"Experimental  Characterization  of  Sectorized  Antennas  in  Dense  802.11  Wireless  Mesh  Networks"、Proc.  ACM  MobiHoc、2009
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明は、従来技術の解決策の上述した欠点を解決することをねらいとする。
【課題を解決するための手段】
【００１０】
以前の研究とは対照的に、本発明者らは、本発明において、現在の文献における実験的な研究からの洞察に基づき、トポロジー制御最適化問題を定式化する。本発明者らは、ネットワークにおける全体的な干渉を最小化することをねらいとする。本発明の定式化は、ペア毎の干渉モデルではなく、測定された受信信号強度値に基づく物理的な干渉モデルを使う。さらに、本発明者らは、完璧な放射パターンをもつ理想化されたアンテナ・モデルに依拠しない。その代わり、本発明者らは、アンテナ・セクターを特徴付けるために測定ベースのアプローチを採用した。本発明は、先進的なアンテナまたはデジタル信号処理に依拠せず、その代わり、本発明に基づく解決策は、通常の既製のIEEE802.11ハードウェアとともに容易に使うことのできる、単純で低コストのマルチセクター・アンテナを使うことができる点でも先行研究とは対照的である。
【００１１】
本発明では、無線ネットワーク、特にIEEE802.11無線ネットワークにおけるトポロジー制御のための最適化フレームワークが導入され、セクター化アンテナを使った実際的かつ効率的な分散式プロトコルが開発される。本発明に基づくトポロジー制御アプローチと以前の提案との間の主な区別は、本発明は、設計するのが簡単で、商用無線ハードウェアとともに機能できる低コストのセクター化アンテナを使うトポロジー制御のために測定ベースのアプローチを使うということである。
【００１２】
トポロジー制御最適化問題はまず、全体的なネットワーク干渉を最小化し、それにより容量を最大化するために各ノード上で複数のセクターをアクティブ化する二次整数計画（quadratic  integer  program）として定式化される。本発明者らは次いで、それを等価な線形整数計画（linear  integer  program）に還元する技法を導入する。結果として得られる線形整数計画は、標準的な線形計画法（LP:  Linear  Programming）ソルバーを使って最適解に対する制限（bounds）を得るために、緩和されることができる。本定式化は、種々のセクター・アクティブ化のパフォーマンスをうまく捕捉するよう観察された受信信号強度（RSS:  Received  Signal  Strength）値の測定に基づく物理的な干渉モデルを使う。この定式化はまた、難しく、最適化手順に簡単に組み込めない、IEEE802.11MACプロトコルの詳細な動作のモデル化を避ける。
【００１３】
次いで本発明は、ノードがトポロジー制御最適化問題を逐次反復的に解くために貪欲な発見的方法を使う、貪欲な分散式トポロジー制御プロトコルを提案する。それは隣接するリンク上のアンテナ・パターンのRSS値のローカルな一ホップ測定に基づく。このプロトコルは、商用のIEEE802.11ハードウェアを使って容易に実装でき、IEEE802.11MACプロトコルならびにマルチホップ無線メッシュ・ネットワークにおけるルーティング・プロトコルまたはWLANにおける関連付け機構のようなネットワーク層リンク選択技法とともに透明に動作する。
【００１４】
本発明は、その広義において、少なくとも一つの第二の無線通信デバイスwと無線ネットワークを形成する第一の無線通信デバイスのためのアンテナ・パターン割り当てを最適化するものとして定義される。各通信デバイスu、wはマルチセクター・アンテナを備え、アンテナ・パターンは前記アンテナ・セクターの組み合わせであり、前記通信デバイスu、wは現在アンテナ・パターン割り当てを使って要求を送り、応答を受信するよう適応されており、当該方法は：
・前記第一の通信デバイスuによって第一の値S*uを評価する段階と；
・前記第一の通信デバイスuによって前記第二の通信デバイスwに、前記値S*uを含むブロードキャスト要求を送る段階と；
・前記第一の通信デバイスuによって、前記ブロードキャスト要求を送る日時に依存して第一のタイムアウトを設定する段階と；
・前記第一の通信デバイスuによって、前記第二の通信デバイスwによって送られる、前記ブロードキャスト要求への応答を受信する段階であって、前記応答は前記第二のデバイスwによって評価された第二の値S*wに依存する、段階と；
・前記第一の通信デバイスuによって、前記応答に依存して、新しいアンテナ・セクター割り当てに切り換えるか切り換えないかする段階とを含み、
前記第一の値S*uが、前記現在アンテナ・パターン割り当てを有する前記第一の通信デバイスuによって受信された受信信号強度RSSに従って第一のローカル関数Suを最小化することによって評価され、前記第二の値S*wが、独自の現在アンテナ・パターン割り当てについて前記第二の通信デバイスwによって受信された受信信号強度RSSに従って第二のローカル関数Swを最小化することによって評価されることを特徴とする。
【００１５】
有利には、前記第一の通信デバイス（u）によって受信される応答は、前記第二の通信デバイス（w）がS*u≧S*wと判定するときに否定的である。
【００１６】
有利には、前記第一の通信デバイス（u）によって受信される応答は、前記第二の通信デバイス（w）がS*u＜S*wと判定するときに肯定的である。
【００１７】
有利には、前記切り換える段階は、前記第一の通信デバイスuによって前記第一のタイムアウト内に諸前記第二の通信デバイスwから受信される諸応答が肯定的である場合に、前記第一の通信デバイスuによる前記現在アンテナ・パターン割り当てから新しいアンテナ・パターン割り当てへのものからなる。
【００１８】
有利には、前記第二の通信デバイスwが、前記第二のタイムアウトが満了するまで、または前記第二の通信デバイスwが前記第一の通信デバイスuから、前記第二の通信デバイスwによって送られる応答の受信を受け取り確認する（acknowledging）ためのブロードキャスト確認（confirmation）を受信するとき、その現在のアンテナ・パターン割り当てを修正することを妨げられるさらなる段階を含む。
【００１９】
有利には、前記第一の通信デバイス（u）は下記
【数１】
2013507813.tif 000003
で与えられる関数Su(xu)を、制約条件
【数２】
2013507813.tif 000004
のもとで、通信デバイス（u）の可能なあらゆるアンテナ・パターン割り当てxuにわたって最小化するアンテナ・パターン割り当て（xu*）および対応する最適値S*u＝Su(xu*)を計算する。ここで、上記の式(13)および(14)において、
E'は、ネットワーク中で通信デバイス（i）を通信デバイス（j）に接続するリンク（i,j）のうち、データが現在送られているリンクの集合を表し、
I(i)は、通信デバイス（i）における干渉を引き起こしうるネットワーク中の通信デバイスの集合を表す。
【００２０】
通信デバイス（u）の一ホップ干渉近傍デバイスであるすべての通信デバイス（w）｛w:  w∈I(u),u∈I(w)｝および通信デバイス（u）の一ホップ通信近傍デバイスであるすべての通信デバイス（v）｛v:  (u,v)∈E'｝は、それぞれのアンテナ・パターン割り当て(xw,xv)を固定したままに保持する。
【００２１】
【数３】
2013507813.tif 000005
の表現は、通信デバイス（i）がアンテナ・パターン割り当て（xi）を使って送信し、通信デバイス(j)がアンテナ・パターン割り当て（xj）を使って受信する場合の、通信デバイス（i）と通信デバイス(j)を接続するリンク(i,,j)に対する通信デバイス（j）における受信信号強度を表し、
表現RSSij00は、通信デバイス（i）が全方向性アンテナ・パターン割り当てxi＝0を使って送信し、通信デバイス(j)が全方向性アンテナ・パターン割り当てxj＝0を使って受信する場合の、リンク(i,j)に対する通信デバイス（j）における受信信号強度を表し、
Cthは閾値パラメータである。
【００２２】
有利には、前記第一の通信デバイスuが実行するS*uについての評価は、S*wを評価するための前記第二の通信デバイスによって実行される評価と同一である。
【００２３】
有利には、前記第一の通信デバイスuは全方向性アンテナ・パターンを使って前記ブロードキャスト要求を送る。
【００２４】
有利には、前記第一の通信デバイスuは諸第二の通信デバイスwに、全方向性アンテナ・パターンを使って確認ブロードキャストを送り、新しいアンテナ・パターン割り当てとしてxu*を選択する。
【００２５】
有利には、前記第一の通信デバイスuが前記第二の通信デバイスwから肯定的な応答を受信する場合、前記第二の通信デバイスwは第二のタイムアウトを設定し、前記第二のタイムアウトが満了するとき、または前記第二の通信デバイスwが前記ブロードキャスト確認パケットを前記第一の通信デバイスuから受信するとき、前記第二の通信デバイスwはその現在のアンテナ・パターン割り当てを調整することが許される。
【００２６】
前記無線ネットワークは複数の通信装置を含む。
【００２７】
有利には、前記複数の通信装置の各通信装置は、逐次前記第一の通信デバイスuとしてはたらき、前記ブロードキャスト要求は前記複数の通信デバイスのうち他のすべての通信デバイスに送られる。
【発明の効果】
【００２８】
本発明によって与えられる利点は次のようなものがある。
【００２９】
本発明は、セクター化アンテナを使う無線ネットワークにおける干渉の最小化の問題を解決する。
【００３０】
提案されるトポロジー制御プロトコルは、既存のプロトコルに対する修正を必要としたり、MACプロトコル・スタックの下位層にアクセスしたりしない。本プロトコルは、商用ハードウェアによってすでに提供されているRSS測定を要求する。本プロトコルはまた、送信または受信する各ノードを特定のアンテナ・セクター組み合わせに切り換える制御論理をも必要とする。トポロジー制御はMACプロトコル動作より長い時間スケールで動作するので、この制御論理は、MACプロトコルを修正することなく、より高い諸層で実装されることができる。最後に、トポロジー・プロトコル制御メッセージは、ブロードキャストまたはユニキャストのネットワーク総パケットを使って、MACプロトコルより高い層で実装されることができる。したがって、提案されるプロトコルは、いかなる既存の無線ネットワーク上でも、最小限の努力で広く展開されることができる。
【００３１】
提案されるプロトコルは、マルチホップ無線ネットワークまたは単一ホップ無線ネットワーク（WLAN）のいずれにも分散され、適用可能である。本プロトコルは、リンク選択機構（マルチホップ無線ネットワークにおけるルーティング機構またはWLANにおける関連付け機構）と並行して実行されることができる。
【００３２】
いくつかの応用のなかでも、提案されるプロトコルは、無線ネットワークの干渉緩和、容量増加およびトポロジー最適化に適用されることができる。
【図面の簡単な説明】
【００３３】
以下の詳細な説明は図面を用いてよりよく理解されるであろう。
【図１】本発明に基づく方法を表すフローチャートである。
【発明を実施するための形態】
【００３４】
本発明には二つの部分がある：
・トポロジー制御最適化問題の定式化および最適解の下限を得るための線形計画法（LP）技法と、
・この最適化問題を逐次反復的な仕方で解こうとする分散式トポロジー制御プロトコル、
である。
【００３５】
〈１．モデルおよび最適化問題の定式化〉
この節では、システム・モデルが提示され、トポロジー制御問題が、組み合わせ論的最適化問題としてマルチセクター・アンテナを使って定式化される。
【００３６】
１．１  ネットワーク・モデル
ネットワークは有向グラフG＝(V,E)によって表現され、ここでVはネットワーク中のn個のノードの集合であり、E⊆V2はノードの諸対の間のリンクの集合である。より正確には、ノード対uとvの間にリンク(u,v)∈Eが存在するのは、該リンクが基礎になる物理層によってサポートされる最低ビットレートで動作するときに、閾値（PRRthresh）より高い送達比でuからvにデータが送達できる場合である。これは、ネットワーク中の各リンクが、可能なビットレートのうちの少なくとも一つを使ってデータを搬送できることを保証する。
【００３７】
リンク(u,v)∈Eは、データ・トラフィックを搬送するために選択されている場合に、アクティブであると考えられる。リンク選択は、WLANにおけるAPとクライアントの間の関連付け（association）機構といったネットワーク層プロトコルまたはメッシュ・ネットワークにおけるマルチホップ・ルーティング・プロトコルによって実行される。本発明では、リンク選択手順自身は考えず、単にそのような機構が存在するものとする。E'⊆Eはネットワーク中のアクティブなリンクの集合を表すとする。集合E'は我々のトポロジー制御最適化問題への入力パラメータである。
【００３８】
１．２  アンテナ・モデル
ネットワーク中の各ノードが、s個のセクターからなるマルチセクター・アンテナを備えているとする。これらs個のセクターの任意の組み合わせをアクティブ化することによって、アンテナ・パターン（antenna  pattern）が形成される。
【００３９】
形成できるアンテナ・パターンの総数はk≦2s−1である。
【００４０】
K＝{0,1,…,k−1}は各ノードで利用可能な、可能なアンテナ・パターンの集合を表すとする。ここで、アンテナ・パターン0はすべてのセクターsが有効にされる全方向性モードを表す。Giθが、アンテナ・パターンiを方向θとともに使うときのアンテナの利得（dBi単位）を表すとする。理想的な条件下では、マルチパス反射がなければ、ノードuがパケットを送信するためにアンテナ・パターンiを使っており、ノードvがパケットを受信するためにアンテナ・パターンjを使っているときの、ノードvにおけるノードuからの受信信号強度（RSS）は次式によって与えられる。
【００４１】
【数４】
2013507813.tif 000006
ここで、Putはノードuにおける送信（transmit）電力、θuvはノードuからvへの方向、duvはuとvの間の距離、αは経路損失係数である。実際上は、RSSはパケット受信の間の受信機における信号エネルギー・レベルの推定値であり、PLCPパケット・ヘッダを受信するときに測定される。新しいアンテナ・パターンが選択されるときは常に、アンテナ利得は変化し、結果として受信機におけるエネルギー・レベルが変化する。このように、RSSは、この変化によって影響される基本的な物理層の量である。商用のIEEE802.11無線カードを使って、任意のリンク(u,v)のRSSを、受信される各パケットに加えられたプロトコル・ヘッダ・フィールド（たとえばプリズム（Prism）・モニタリング・ヘッダ）から直接得ることができる。従来の研究において、RSSが、リンクのパケット送達比およびデータ・レートのようなより高い層のメトリックとよい相関をもつことが示されている。RSSはまた、物理干渉モデルの基礎をもなす。次節では、いかにしてリンクRSSを使ってネットワーク中の干渉をモデル化するかを議論し、我々のトポロジー制御最適化問題の目的関数を定義する。
【００４２】
〈１．３  干渉モデルおよび目的関数〉
トポロジー制御に対する明らかなアプローチは、直接、ネットワーク容量を最大化することである。時分割多重アクセス（TDMA:  Time  Division  Multiple  Access）MACプロトコルを使う無線ネットワークでは、容量最大化を実行する最適化問題を定式化することが可能である。しかしながら、我々は主としてキャリア・センス多重アクセス（CSMA:  Carrier  Sense  Multiple  Access）MACプロトコルを使うIEEE802.11ネットワークにおけるトポロジー制御に関心がある。TDMAとは対照的に、CSMAネットワークのネットワーク容量をモデル化することは難しい。近年、CSMAネットワークについてのいくつかの測定ベースの容量モデルが提案されている[9],[13]。しかしながら、これらのモデルは複雑であり、最適化の枠組みに組み込むのは容易ではない。トポロジー制御に対する我々のアプローチは、ネットワーク中の総合干渉（aggregate  interference）を最小化するというものである。このアプローチは[8]においてネットワーク容量を最適化する間接的な方法として使われている。CSMAベースの無線ネットワークでは、伝送は、送信側および受信側両方で干渉を受ける。ノードuからノードvへの送信を考える。送信側では、uは、次の条件が満たされるときにのみ媒体が空いていると感知する。
【００４３】
【数５】
2013507813.tif 000007
ここで、RSSwuはノードuにおけるノードwからの受信信号強度であり、I(u)はノードuにおいて干渉を引き起こすことのできるノードの集合（干渉集合と記される）であり、CSthresはキャリア・センス閾値である。受信側では、vからuに送信されたパケットが成功裏に受信されるのは、次の条件が満たされる場合にのみである。
【００４４】
【数６】
2013507813.tif 000008
ここで、Nは背景雑音であり、βは受信閾値である。ノードuについての干渉集合I(u)は次のようにして定義する。ノードwがI(u)の要素となるのは、(u,w)(w,u)がE'の要素でないときであり、かつそのときに限る。これは、ネットワーク層プロトコルによって選択されたリンクに従ってノードuに送信したりノードuから受信したりしない当該ネットワーク中のすべてのノードが干渉集合の一部であるということを含意する。すると、ノードuにおける干渉は
【数７】
2013507813.tif 000009
となる。これは、ノードuがリンクの送信側ノードであるとき（式1）にもリンクの受信側ノードであるとき（式2）にもノードuに影響する。
【００４５】
我々のアプローチの焦点は、
【数８】
2013507813.tif 000010
のように定義される、ネットワーク中の総合干渉を最小化することである。
【００４６】
１．４  最適化の枠組み
略式には、トポロジー制御への我々のアプローチは、接続性の制約条件のもとで各ノードに適切なアンテナ・パターンを割り当てることによって、式(3)で定義されるネットワーク中の総合干渉を最小化することである。接続性制約条件は、E'（データ・トラフィックを搬送するリンク）中の各リンクについて、次のように定義される。集合E'中の各リンク(u,v)について、アンテナ・パターン割り当て後のそのリンクのRSSは、ノードuおよびノードvの両方が全方向性モードを使うときのそのリンクのRSSと（数dBの閾値の範囲内で）匹敵するべきである。我々は最適化問題を次のように正式に定義する。
【００４７】
Xuiが、アンテナ・パターンiがノードuに割り当てられているか否かを表す決定変数であるとする。アンテナ・パターンiがノードuに割り当てられていればXui＝1であり、そうでなければXui＝0である。集合E'内の各リンク(u,v)について、Cuvijが、アンテナ・パターンiをノードuに割り当て、jをノードvに割り当てることが接続性制約条件を満たすかどうかを表すとする。
【００４８】
【数９】
2013507813.tif 000011
ここで、RSSuv00は、両方のノードが全方向性モードを使う場合のリンク(u,v)のRSSを表し、RSSuvijはノードuがアンテナ・パターンiを使い、ノードvがアンテナ・パターンjを使う場合のRSSを表す。Cthは数dB程度となるよう選ばれる閾値である。Cuvij＝1となるようアンテナ・パターンiおよびjを選ぶことで、リンク(u,v)のデータ・レートがアンテナ・パターン割り当てのために害を受けないことが保証される。
【００４９】
OPT_TOPOCONTROLと名付けられる我々のトポロジー制御問題は次のように定義される：
【数１０】
2013507813.tif 000012
式(4)は、ネットワーク中の各ノードがちょうど一つのアンテナ・パターンを割り当てられることを保証する。式(5)は、データ・トラフィックを搬送する各リンクの、割り当てられたアンテナ・パターンを使ってのRSSが、全方向モードを使うときのRSSのCthの範囲内であることを保証する。最後に、式(6)は、Xuiが値0または1を取ることを保証する。
【００５０】
上記の最適化問題は、二次式で制約された二次最適化問題であり、NP困難であると推測される。次節では、この問題を整数線形計画に還元し、次いでそれを線形計画に緩和して、最適解に対する下限を得る。
【００５１】
１．５  線形計画の定式化
この節での我々の目標は、我々のOPT_TOPOCONTROL定式化における二次目的関数および二次制約条件を線形の目的関数および制約条件で置き換えることである。目的関数は集合E'に属さないリンクのみを含み、制約条件(5)は集合E'のみに属するリンクのみに適用されることを注意しておく。これら二つのリンクの集合は分離している。式(5)において、積XuiXvjを新しい変数Zuvijで置き換え、二つの新しい制約条件を導入する。
【００５２】
Zuvij≦Xui,    ∀u,v∈E',    ∀i,j∈K    (7)
Zuvij≦Xvi,    ∀u,v∈E',    ∀i,j∈K    (8)
もとの最適化定式化では、XuiおよびXvjの両方が1のときにXuiXvj＝1となり、他の場合に0となる。式(7)および(8)は、ZuvijがXuiおよびXvjの両方より小さいことを保証する。よって、XuiおよびXvjの両方が1の場合のほかは、Zuvijは0でなければならない。残りの場合、Zuvijは0または1のいずれでもありうる。式(5)の左辺は1より大きいはずなので、Zuvijの少なくとも一つは強制的に1になる。これは、接続性制約条件がデータを搬送する毎リンクについて満たされることを保証する。我々は、目的関数中の積XuiXvjを変数Yuvijによって置き換え、次の追加的な制約を課す。
【００５３】
Yuvij≧Xui＋Xvj−1,    ∀u,v（E'の要素でない）,    ∀i,j∈K    (9)
もとの最適化定式化では、XuiおよびXvjの両方が1のときに目的関数中のXuiXvj＝1となり、他の場合に0となる。式(9)は、XuiおよびXvjの両方が1の場合にYuvijが強制的に1にされることを保証する。残りの場合、Yuvijは0または1のいずれでもありうる。最適化問題は目的関数を最小化することを目標とするので、変数Yuvijに0または1の選択肢が与えられる場合には、0が選ばれる。上述した還元を使って、当初の二次式の制約条件のもとでの二次最適化問題は、次の整数線形問題に変換される。
【００５４】
【数１１】
2013507813.tif 000013
したがって、上記の整数線形計画における整数性の制約条件を緩和することによって、CPLEX[2]のような標準的なソルバーを使って、もとのトポロジー制御最適化問題（OPT_TOPOCONTROL）の最適解に対する加減を多項式時間で得ることができる。
【００５５】
〈２．貪欲な分散式トポロジー制御プロトコル〉
ここでトポロジー制御最適化問題OPT_TOPOCONTROLを解くことをねらいとする分散式トポロジー制御プロトコルを提示する。このプロトコルは、既存のリンク選択プロトコル（メッシュ・ネットワークの場合のAODVおよびDSRのようなルーティング・プロトコル）とともに透明に機能し、商用のIEEE802.11無線ハードウェアを使ってIEEE802.11MACプロトコルの上に容易に実装できる。このプロトコルは入力として、リンク選択プロトコルからのアクティブなリンクE'と、同時に動作する別個の分散式測定プロトコルからのRSSuvij値を使う。本トポロジー制御プロトコルの動作をよりよく理解するために、まず、その背後にある主要なアイデアを含むアルゴリズムを提示することにする。
【００５６】
２．１  分散式逐次反復アルゴリズム
トポロジー制御最適化問題は、たとえ中央集中された情報があったとしても、解くのは極めて複雑である。我々は、ローカルな情報だけを使ってこの問題を逐次反復的に解くことをねらいとする分散式の発見法的アルゴリズムを提起する。ネットワーク中の各ノードuに割り当てられたアンテナ・パターンをxu∈Kが表す、任意の割り当てを考える。この割り当てについて、目的関数は次式で与えられる。
【００５７】
【数１２】
2013507813.tif 000014
この目的関数は
【数１３】
2013507813.tif 000015
とも書ける。ここで、
【数１４】
2013507813.tif 000016
Suの第一項は他のノードがノードuに対して引き起こす干渉に対応し、第二項はノードuが他のノードに引き起こす干渉に対応する。逐次反復的アルゴリズムは、各Suの逐次反復的な最小化によって目的関数を最小化しようとする。
【００５８】
このアルゴリズムの動作は次のようになる。(xu(n),  ∀u∈V)を反復工程nにおけるアンテナ・パターン割り当てを表すとする。各反復工程において、ノードuが、そのアンテナ・パターン割り当てを修正するものとして選択され、ネットワーク中の残りのノードはその割り当てを固定したままに保持する。ノード選択の順序は種々の基準によることができるが、簡単のため、任意であるとする。
【００５９】
まず、ノードuがCOMPUTE_OWN_BEST_SECTOR〔自らの最良セクターを計算〕と呼ばれるローカルな計算を実行する。より具体的には、ノードuは、制約条件
【数１５】
2013507813.tif 000017
のもとで、そのすべての一ホップ近傍ノード{w:w∈I(u),u∈I(w)}および{v:(u,v)∈E'}がそのアンテナ・パターン割り当てxw(n)およびxv(n)を固定したままに保持するとして、式(11)におけるSu(xu)を最小化するセクターxu*を計算する。
【００６０】
この最小化は(i)集合E'内でリンク(u,v)の接続性制約条件を満たす、すなわち
【数１６】
2013507813.tif 000018
であるすべてのアンテナ・パターンxuを選択し、(ii)これらのxuについて、式(11)に基づいてSuについての対応する値を計算してそれらを比較することを含む。第二に、ノードuはxu*を、その新しいアンテナ・パターン割り当てとして選択する。
【００６１】
上記のアルゴリズムが、初期状態にかかわりなく、有限回の反復工程後に、式(10)の目的関数の局所的な最小に収束することが保証されていることを示すのは容易である。その理由は、各反復工程の間に目的関数が減少し、ネットワーク中のアンテナ・パターンの組み合わせは有限個だからである。
【００６２】
２．２  貪欲な分散式プロトコル
ここで、上記分散式逐次反復アルゴリズムの貪欲バージョンを実現する分散式プロトコルを与えておく。このプロトコルは連続的かつ非同期的に各ノードuにおいて実行され、ローカルな計算および一ホップのメッセージ交換のみに依拠する。これはIEEE802.11MACプロトコルの上で動作し、そのメッセージは、ブロードキャストまたはユニキャストのネットワーク層パケットを用いて実装される。後述するように、このプロトコルのすべての制御メッセージは、全方向性アンテナ・パターンを使って、最低データ・レート（我々のIEEE802.11a実装では6Mbps）で、送られる。これはそれぞれカバー範囲および信頼性を増すためである。カバー範囲および信頼性をさらに増すために、制御メッセージは、近隣ノード間の標準的な時間同期またはランデブー方法を使って、あるいは別個の電波および周波数チャネルを使って、データ・パケットと同じチャネル上で送られることができる。
【００６３】
各ノードuは、各近隣ノードwについての、(i)現在のアンテナ・パターンxwおよび(ii)別個の測定プロトコルによって測定される、リンク(u,w)上のすべてのアンテナ・セクターについての
【数１７】
2013507813.tif 000019
の値を含むテーブルを維持している。各ノードuは、その現在アンテナ・パターン割り当てxuを含んでいるブロードキャスト・パケットをランダムな間隔で送る。それにより近隣ノードはそのテーブルを更新する。
【００６４】
各ノードuは、トポロジー制御プロトコルへの参加に関して二つの状態にある。アンテナ・パターン修正の間、ノードはビジー（BUSY）であり、全方向性アンテナ・パターンを使って送信し、それ以外はフリー（FREE）であり、割り当てられたアンテナ・パターンxuを使って送信する。
【００６５】
ビジー状態にある間に、ノードはそのアンテナ・パターン割り当てを修正しようとする。ノード間で試行は同期されないので、複数のノードがそのアンテナ・パターンを同時に修正しようと試みることがありうる。分散式アルゴリズムの各反復工程において、ノードがその割り当てを修正することを、その近隣ノードがその割り当てを固定したままに保持している間に行う必要があることを想起されたい。この問題は、下記のステップ１〜４で記述される分散式ロック機構を使って対処される。
【００６６】
ここで、ノードuの試行の際のプロトコル動作を記述する。以下の記述では、ノードu（またはw）がビジーになるとき、そのノードは以下の動作を実行する：(i)ビジー状態に切り換わる、(ii)全方向性アンテナ・パターン0に切り換わる、(iii)タイムアウトを、ノードが各試行に参加する最大継続時間であるビジー・タイムアウトに等しく設定する。ノードu（またはw）がアボートするとき、そのノードは以下の動作を実行する：(i)フリー状態に切り換わる、(ii)そのアンテナ・パターン割り当てxu（またはxw）に戻る。
【００６７】
ステップ１。ノードuはまずビジーになり、次いでそのローカルなテーブル中のxwの値に基づいて式(11)におけるSuを最小化し、最小値Su*および対応する割り当てxu*を得る。次いで、ノードuはSu*を含むブロードキャストTOPO  REQパケットを送る。ノードuはまた、すべての近隣ノードからのTOPO  REQ  ACK応答を待つタイムアウトTOPO  REQ  TIMEOUTを設定する。TOPO  REQパケット要求は近隣ノードに、そのアンテナ・パターン割り当てを固定するよう要求する。
【００６８】
ステップ２。ノードwがuからTOPO  REQパケットを受信すると、ノードwは、ビジーであるかSu*≧Sw*である場合には、TOPO  REQ  NACKパケットをuに返す。それ以外の、ノードwがフリーであり、かつSu*＜Sw*である場合には、ノードwはビジーになり、TOPO  REQ  ACKパケットをuに返す。Sw*とSu*の比較は、タイ〔同順〕の場合に決着をつけるとともに、一ホップ近傍内で最小のSu*をもつノードがそのセクター割り当てを修正する貪欲な反復工程を実装するはたらきをする。これは、各一ホップ近傍内でのグローバルな目的関数の最大限の低下につながる。
【００６９】
ステップ３。ノードuが少なくとも一つのTOPO  REQ  NACKを受け取るか、そのTOPO  REQ  TIMEOUTの期限が切れる場合、ノードuはTOPO  CANCELパケットをブロードキャストし、アボートする。それ以外で、TOPO  REQ  TIMEOUT内にすべての近隣ノードからTOPO  REQ  ACKを受信する場合には、ノードuはTOPO  CONFIRM〔確認〕パケットをブロードキャストする。次いで、ノードuはフリー状態に切り換わり、新しいアンテナ・パターン割り当てx*uに切り換わる。
【００７０】
ステップ４。ノードwがuからTOPO  CONFIRMパケット割り当てを受信する場合、ノードwはフリー状態に切り換わり、もとのそのアンテナ・パターン割り当てxwに切り換わる。この時点において、ノードuにおけるアンテナ・パターン再割り当ては完了している。上記の諸ステップの間に、いずれかのビジーなノードのBUSY  TIMEOUTの期限が切れたら、このノードはアボートする。
【００７１】
上記の明細書、例および図面は、本発明に基づく方法の記述が完了する。本発明の精神および範囲から外れることなく本発明の多くの実施形態ができるので、本発明は付属の請求項に存在する。
【図１】
2013507813.tif 000023
【手続補正書】
【提出日】平成24年4月10日(2012.4.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
少なくとも一つの第二の無線通信デバイスと無線ネットワークを形成する第一の無線通信デバイスのためのアンテナ・パターン割り当てのための方法であって、各通信デバイスはマルチセクター・アンテナを備え、アンテナ・パターンは前記アンテナ・セクターの組み合わせであり、前記通信デバイス（u,w）は現在アンテナ・パターン割り当てを使って要求を送り、応答を受信するよう適応されており、当該方法は：
・前記第一の通信デバイスによって第一の値（S*u）を評価する段階と；
・前記第一の通信デバイス（u）によって前記第二の通信デバイス（w）に、前記第一の値（S*u）を含むブロードキャスト要求を送る段階と；
・前記第一の通信デバイスによって、前記第二の通信デバイスによって送られる、前記ブロードキャスト要求への応答を受信する段階であって、前記応答は前記第二のデバイスによって評価された第二の値（S*w）に依存する、段階と；
・前記第一の通信デバイスによって、前記応答に依存して、新しいアンテナ・パターン割り当てに切り換えるか切り換えないかする段階とを含み、
前記第一の値（S*u）が、前記現在アンテナ・パターン割り当てを有する前記第一の通信デバイスによって受信された受信信号強度（RSS）に従って第一のローカル関数（Su）を使うことによって評価され、前記第二の値（S*w）が、独自の現在アンテナ・パターン割り当てについて前記第二の通信デバイスによって受信された受信信号強度（RSS）に従って第二のローカル関数（Sw）を使うことによって評価されることを特徴とする、
方法。
【請求項２】
前記第一の通信デバイスによって受信される応答は、前記第二の通信デバイスが前記第一の値（S*u）が前記第二の値（S*w）以上であると判定するときに否定的であることを特徴とする、請求項１記載の方法。
【請求項３】
前記第一の通信デバイスによって受信される応答は、前記第二の通信デバイスが前記第一の値（S*u）が前記第二の値（S*w）未満であると判定するときに肯定的であることを特徴とする、請求項１または２に記載の方法。
【請求項４】
当該方法が、前記第一の通信デバイスによって、前記ブロードキャスト要求を送る日時に依存して第一のタイムアウトを設定する段階を有し、
前記第一の通信デバイスによって、前記現在アンテナ・パターン割り当てから前記新しいアンテナ・パターン割り当てに切り換える前記段階が、前記第一のタイムアウト期間内に諸前記第二の通信デバイスから前記第一の通信デバイスによって受信される諸応答が肯定的である場合に行われることを特徴とする、請求項２または３記載の方法。
【請求項５】
当該方法が、前記第二の通信デバイスが第二のタイムアウトを設定するさらなる段階を含み、前記第二の通信デバイスが、前記第二のタイムアウトが満了するまで、または前記第二の通信デバイスが前記第一の通信デバイスから、前記第二の通信デバイスによって送られた応答の受信を受け取り確認するブロードキャスト確認を受信するとき、その現在のアンテナ・パターン割り当てを修正することを妨げられることを特徴とする、請求項１または４記載の方法。
【請求項６】
前記第一の通信デバイスが
【数１８】
2013507813.tif 000024
で与えられる関数Su(xu)を、制約条件
【数１９】
2013507813.tif 000025
のもとで、通信デバイス（u）の可能なあらゆるアンテナ・パターン割り当てxuにわたって最小化するアンテナ・パターン割り当て（xu*）および対応する第一の値S*u＝Su(xu*)を計算し、ここで、上記の式(13)および(14)において、
E'は、ネットワーク中で通信デバイス（i）を通信デバイス（j）に接続するリンク（i,j）のうち、データが現在送られているリンクの集合を表し、
I(i)は、通信デバイス（i）における干渉を引き起こしうるネットワーク中の通信デバイスの集合を表し、
通信デバイス（u）の一ホップ干渉近傍デバイスであるすべての通信デバイス（w）｛w:  w∈I(u),u∈I(w)｝および通信デバイス（u）の一ホップ通信近傍デバイスであるすべての通信デバイス（v）｛v:  (u,v)∈E'｝は、それぞれのアンテナ・パターン割り当て(xw,xv)を固定したままに保持し、
【数２０】
2013507813.tif 000026
の表現は、通信デバイス（i）がアンテナ・パターン割り当て（xi）を使って送信し、通信デバイス(j)がアンテナ・パターン割り当て（xj）を使って受信する場合の、通信デバイス（i）と通信デバイス(j)を接続するリンク(i,,j)に対する通信デバイス（j）における受信信号強度を表し、
表現RSSij00は、通信デバイス（i）が全方向性アンテナ・パターン割り当てxi＝0を使って送信し、通信デバイス(j)が全方向性アンテナ・パターン割り当てxj＝0を使って受信する場合の、リンク(i,j)に対する通信デバイス（j）における受信信号強度を表し、
Cthは閾値パラメータである、
ことを特徴とする、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
前記第一の通信デバイスが実行する前記第一の値（S*u）についての評価は、前記第二の値（S*w）を評価するための前記第二の通信デバイスによって実行される評価と同一であることを特徴とする、請求項２ないし５のうちいずれか一項記載の方法。
【請求項８】
前記第一の通信デバイスは全方向性アンテナ・パターンを使って前記ブロードキャスト要求を送ることを特徴とする、請求項１ないし７のうちいずれか一項記載の方法。
【請求項９】
前記第一の通信デバイスは諸第二の通信デバイスに、全方向性アンテナ・パターンを使って確認ブロードキャストを送り、新しいアンテナ・パターン割り当てとしてアンテナ・パターン割り当て（xu*）を選択することを特徴とする、請求項１ないし６のうちいずれか一項記載の方法。
【請求項１０】
前記第一の通信デバイスが前記第二の通信デバイスから肯定的な応答を受信する場合、前記第二の通信デバイスは第二のタイムアウトを設定し、前記第二のタイムアウトの期限が切れるとき、または前記第二の通信デバイスが前記ブロードキャスト確認パケットを前記第一の通信デバイスから受信するとき、前記第二の通信デバイスはその現在のアンテナ・パターン割り当てを調整することが許されることを特徴とする、請求項３ないし９のうちいずれか一項記載の方法。
【請求項１１】
前記無線ネットワークが複数の通信装置を含み、前記複数の通信装置の各通信装置は、逐次前記第一の通信デバイスとしてはたらき、前記ブロードキャスト要求は前記複数の通信デバイスのうち他のすべての通信デバイスに送られることを特徴とする、請求項１ないし１０のうちいずれか一項記載の方法。
【請求項１２】
マルチセクター・アンテナを備え、現在アンテナ・パターン割り当てを使って要求を送り、応答を受信するよう適応された無線通信デバイスであって：
・第一の値（S*u）を評価する手段と；
・無線ネットワークを通じて当該第一の通信デバイスに接続される第二の無線通信デバイスに、前記第一の値（S*u）を含むブロードキャスト要求を送る手段と；
・当該第一の通信デバイスによって前記ブロードキャスト要求への応答を受信する手段と；
・当該第一の通信デバイスによって、前記応答に依存して、新しいアンテナ・パターン割り当てに切り換えるか切り換えないかする手段とを有しており、
前記第一の値（S*u）が、前記現在アンテナ・パターン割り当てを有する当該第一の通信デバイスによって受信された受信信号強度（RSS）に従って第一のローカル関数（Su）を使うことによって評価されることを特徴とする、
無線通信デバイス。
【国際調査報告】
2013507813.tif 000027
2013507813.tif 000028
2013507813.tif 000029