(57)【要約】無線ネットワークにおけるビーコン送信に関する様々な実施形態が開示される。無線ノードは、１つ以上の無線ノード(MP1、MP2、MP3)からビーコン(312、314)を受信することができる。受信ノードは、ビーコンマップを生成して、ネットワーク内の他の無線ノードに送信することができる。ビーコンマップは、ビーコンのタイムスタンプまたは他の時間情報のような受信ビーコンのうちの１つ以上、および送信元無線ノードのアドレスのようなビーコンの送信元無線ノードに関連する情報を提供することが可能である。ビーコンマップは、リクエストに応じて、またはビーコン内で、あるいは別のメッセージ内で送信することが可能である。別の実施形態の例では、ビーコンマップは、受信側無線ノードで受信することができ、１つ以上の他の無線ノードからのビーコンに関する情報を含む。ビーコンのうちの少なくとも１つの状態は、ビーコンマップに基づいて判断することができる。【選択図】図4
2008529382.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上の無線ノードからビーコンを受信するステップ（410）と、
ビーコンマップを生成するステップ（420）と、
前記ビーコンマップを１つ以上の無線ノードに送信するステップであって、前記ビーコンマップは、前記受信されたビーコンのうちの１つ以上に関する情報を提供するステップ（430）と、を含む方法。
【請求項２】
前記送信するステップは、ビーコンマップを１つ以上の無線ノードに送信するステップを含み、前記ビーコンマップは、１つ以上の受信されたビーコンに関する情報を提供し、前記情報は、前記ビーコンのタイムスタンプまたは他の時間情報、および前記ビーコンの送信元無線ノードに関する情報を含む（432）、請求項1に記載の方法。
【請求項３】
前記送信するステップは、ビーコンマップを１つ以上の無線ノードに送信するステップを含み、前記ビーコンマップは、前記ビーコンのタイムスタンプまたは他の時間情報、および前記受信されたビーコンのうちの１つ以上の前記送信元無線ノードのMAC（Media Access Control; メディアアクセス制御）アドレスを提供する、請求項1に記載の方法。
【請求項４】
前記送信するステップは、ビーコンマップを１つ以上の無線ノードに送信するステップを含み、前記ビーコンマップは、前記ビーコンのタイムスタンプまたは他の時間情報と、前記送信元無線ノードのアドレスと、前記受信されたビーコンのうちの１つ以上のビーコン状態とを提供する、請求項1に記載の方法。
【請求項５】
前記ビーコン状態は、アイドル、受信、または衝突のうちの１つを含む、請求項4に記載の方法。
【請求項６】
前記受信するステップは、無線メッシュネットワーク内の１つ以上のメッシュポイントからビーコンを受信するステップを含み、
前記送信するステップは、前記ビーコンマップを前記メッシュポイントのうちの１つ以上に送信するステップを含み、前記ビーコンマップは、前記受信されたビーコンのうちの１つ以上に関する情報を提供する、請求項1に記載の方法。
【請求項７】
前記送信するステップは、
前記ビーコンマップをリクエストする無線ノードからリクエストメッセージを受信するステップと、
前記リクエストメッセージの受信に応じて、前記ビーコンマップを送信するステップとを含む、請求項1に記載の方法。
【請求項８】
前記送信するステップは、ビーコン内に前記ビーコンマップを送信するステップを含む、請求項1に記載の方法。
【請求項９】
前記送信されたビーコンマップを受信するステップ（440）と、
前記ビーコンマップに基づいてビーコンを再配置するステップ（450）と、をさらに含む、請求項1に記載の方法。
【請求項１０】
前記再配置するステップは、前記ビーコンマップに基づいて、ビーコンのターゲットビーコン送信時間を変更するステップを含む、請求項6に記載の方法。
【請求項１１】
受信側無線ノードでビーコンマップを受信するステップであって、前記ビーコンマップは、１つ以上の他の無線ノードからのビーコンに関する情報を提供するステップ（510）と、
前記ビーコンマップに基づいて、前記１つ以上の他の無線ノードからの前記ビーコンのうちの少なくとも１つの状態を判断するステップ（520）と、を含む方法。
【請求項１２】
前記状態を判断するステップは、前記１つ以上の他の無線ノードからの前記ビーコンのうちの少なくとも１つの送信時間を判断するステップ（524）を含む、請求項11に記載の方法。
【請求項１３】
前記ビーコンマップを受信するステップは、
受信側無線ノードでビーコンマップを受信するステップであって、前記ビーコンマップは、ビーコンのタイムスタンプまたは他の時間情報、および前記ビーコンのそれぞれの送信元無線ノードのアドレスを含むステップ（512）を含む、請求項11に記載の方法。
【請求項１４】
前記ビーコンマップに基づいて、ビーコンを再配置するステップ（530）をさらに含む、請求項11に記載の方法。
【請求項１５】
前記再配置するステップは、前記ビーコンマップに基づいて、ターゲットビーコン送信時間を変更するステップを含む、請求項14に記載の方法。
【請求項１６】
前記再配置するステップは、
前記ビーコンマップに基づいて、前記他の無線ノードのうちの１つからのビーコンが、前記受信側無線ノードから送信されたビーコンと衝突しているか、または衝突する可能性があるかを判断するステップ（532）と、
前記判断に基づいて、前記受信側無線ノードから送信された前記ビーコンを再配置するステップ（534）とを含む、請求項14に記載の方法。
【請求項１７】
制御器（604）と、
前記制御器に接続されたメモリ（606）と、
前記制御器に接続された無線トランシーバ（602）とを備える装置（600）であって、
１つ以上の無線ノードからビーコンを受信し（410）、
ビーコンマップを生成し（420）、
前記ビーコンマップを１つ以上の無線ノードに送信するように構成され、前記ビーコンマップは、前記受信されたビーコンのうちの１つ以上に関する情報を提供する（430）、装置。
【請求項１８】
前記装置は、無線メッシュネットワーク内にメッシュポイント（MP1、MP2、MP3）を備える、請求項16に記載の装置。
【請求項１９】
前記ビーコンマップは、前記受信されたビーコンのうちの１つ以上に関する情報を提供し、前記情報は、前記ビーコンのタイムスタンプまたは他の時間情報、および前記ビーコンの送信元無線ノードに関する情報を含む（432）、請求項16に記載の装置。
【請求項２０】
制御器（604）と、
前記制御器に接続されたメモリ（606）と、
前記制御器に接続された無線トランシーバ（602）とを備える装置であって、
受信側ノードでビーコンマップを受信し、前記ビーコンマップは、１つ以上の他の無線ノードからのビーコンに関する情報を提供し（510）、
前記ビーコンマップに基づいて、前記１つ以上の他の無線ノードからの前記ビーコンのうちの少なくとも１つの状態を判断する（520）ように構成される装置。
【請求項２１】
前記装置は、無線メッシュネットワーク内にメッシュポイント（MP1、MP2、MP3）を備える、請求項20に記載の装置。
【請求項２２】
記憶媒体を備える物であって、
前記記憶媒体は該記憶媒体に記憶される命令を含み、該命令は、プロセッサにより実行されたときに、
１つ以上の無線ノードからビーコンを受信すること（410）、
ビーコンマップを生成（420）すること、
前記ビーコンマップを１つ以上の無線ノードに送信すること（430）、
を実現させ、ここで前記ビーコンマップは、前記受信されたビーコンのうちの１つ以上に関する情報を提供する、物。
【請求項２３】
前記ビーコンマップを送信させる前記命令は、プロセッサにより実行されたときに、
ビーコンマップを１つ以上の無線ノードに送信することを実現させる命令を含み、前記ビーコンマップは、１つ以上の受信されたビーコンに関する情報を提供し、前記情報は、前記ビーコンのタイムスタンプまた他の時間情報、および前記ビーコンの前記送信元無線ノードのＭＡＣアドレスを含む、請求項22に記載の物。
【発明の詳細な説明】
【関連出願の相互参照】
【０００１】
本出願は、米国仮出願第60/685,100号（2005年5月26日出願）、発明の名称 "Beacon Transmission for Meshed Wireless Networks" に対する優先権を主張するものであり、参照することにより本書に組み込まれる。
【背景技術】
【０００２】
無線ローカルエリアネットワーク（Wireless Local Area Network; WLAN）アクセスの急速な普及、およびWLANの受信可能エリアへの需要の高まりは、極めて多数のアクセスポイント（Access Point; AP）の導入を促している。APのコストは慣習的にそれほど高くはないが、APを展開することは、しばしば有線接続（慣習的にイーサネット（登録商標））を介したAPの接続を伴い、これによって、特定の場所に展開することに対する複雑さ、およびコストの増加が生じる。
【０００３】
APまたは他の無線ノードの無線メッシュネットワークの概念が開発されている。１つのメッシュネットワーク内のノードは、場合によっては、同じ周波数で動作する場合がある。これは、そのようなシステムの場合、一般的に導入されているWLANシステムとは対照的に、メッシュネットワーク内の複数のAPが、それらのビーコンメッセージを同じチャネルで送信する場合があることを意味する。現在導入されているWLAN標準（IEEE 802.11bなど）では、ビーコンメッセージのための競合解決が提供されていないので、これはビーコンメッセージの衝突をもたらす可能性があり、また非常に非効率的である。各APは、先のデータ送信が終了しているので、フレーム間隔（Inter-Frame Space; IFS）の後にそのビーコンメッセージを送信する場合がある。このような場合、２つのAPによるビーコンの衝突の生じる可能性が非常に高い。
【発明の開示】
【０００４】
ビーコン、およびWLANネットワーク、無線メッシュネットワークのような無線ネットワーク、または他の無線ネットワークに関する様々な実施形態が開示されている。例示的な一実施形態では、ビーコンマップを生成および送信することが可能である。
【０００５】
別の例示的な実施形態によれば、無線ノードまたはメッシュポイントは、無線ネットワーク内の１つ以上の他のノードまたはメッシュポイントからビーコンを受信し、ビーコンマップを生成することが可能である。無線ノードは、生成されたビーコンマップを、無線ネットワーク内の１つ以上の他のメッシュポイントまたはノードに送信することが可能である。
【０００６】
例示的な一実施形態では、ビーコンマップは、受信されたビーコンのうちの１つ以上に関する情報を提供することが可能である。例示的な一実施形態では、ビーコンマップは、ビーコンのタイムスタンプまたは他の時間情報、およびビーコンの送信元無線ノードまたはメッシュポイントに関する情報を含むことが可能である。例えば、ビーコンマップは、ビーコンの送信元無線ノードの、MAC（Media Access Control; 媒体アクセス制御）アドレスのようなアドレスを含むことが可能である。ビーコンマップは、例えば、プローブリクエストのようなリクエストメッセージに応じて、ビーコンまたは他のメッセージ内で送信することが可能である。
【０００７】
別の実施形態では、ビーコンマップは、受信側無線ノードで受信することが可能である。受信側無線ノードは、ビーコンマップに基づいて、そのビーコンが、別の無線ノードからのビーコンと衝突していることを判断することが可能である。受信側無線ノードは、そのビーコンの位置を再配置することが可能である。
【０００８】
別の例示的な実施形態では、ビーコンマップは、受信側無線ノードで受信することが可能である。ビーコンマップは、１つ以上の他の無線ノードからのビーコンに関する情報を含むことが可能である。ビーコンのうちの少なくとも１つの状態は、ビーコンマップに基づいて判断することが可能である。例えば、受信側無線ノードは、無線ノードからビーコンを送信したかどうか、ビーコンのうちの少なくとも１つの送信時間、ビーコンのうちの１つが他のビーコンまたは信号と衝突している（または衝突した可能性がある）こと、またはビーコンマップに基づいた他のビーコンの状態情報、を判断することが可能である。例示的な実施形態では、ビーコンは、受信されたビーコンマップに基づいて再配置することが可能である。ビーコンの再配置には、例えば、他の無線ノードのうちの１つからのビーコンが、受信側無線ノードから送信されたビーコンと衝突しているか、または衝突する可能性があるかを判断し、次いで、受信ノードのビーコンを再配置して、例えばビーコンが衝突する可能性を減じることを含むことが可能である。ビーコンの再配置には、例えば、ビーコンのターゲットビーコン送信時間の変更を含むことが可能である。
【０００９】
別の実施形態では、制御器と、制御器に接続されたメモリと、制御器に接続されたトランシーバとを備えた装置が提供される。該装置は、１つ以上の無線ノードからビーコンを受信して、ビーコンマップを生成し、ビーコンマップを１つ以上の無線ノードに送信するように適応させるか、または構成することが可能であり、該ビーコンマップは、受信されたビーコンのうちの１つ以上に関する情報を提供する。例示的な実施形態では、装置は、無線メッシュネットワーク内にメッシュポイントを備えることが可能である。
【００１０】
さらに別の実施形態では、無線ノードは、制御器と、制御器に接続されたメモリと、制御器に接続された無線トランシーバとを備えた無線ノードを提供することが可能である。無線ノードは、受信側無線ノードでビーコンマップを受信して、該ビーコンマップに基づいて、受信側無線ノードが、別の無線ノードからのビーコンと衝突しているか、または衝突する可能性があるかを判断し、受信側無線ノードのビーコンを再配置するように適応させることが可能である。例示的な実施形態では、無線ノードは、無線メッシュネットワーク内にメッシュポイントを備えることが可能である。
【００１１】
さらに別の実施形態では、無線ノードは、制御器と、制御器に接続されたメモリと、制御器に接続された無線トランシーバとを備えた無線ノードを提供することが可能である。無線ノードまたは制御器は、受信側無線ノードでビーコンマップを受信するように構成することが可能であり、該ビーコンマップは、１つ以上の他の無線ノードからのビーコンに関する情報を提供する。受信側無線ノードは、ビーコンマップに基づいて、１つ以上の他の無線ノードからのビーコンのうちの少なくとも１つの状態を判断するように構成することも可能である。例えば、受信側無線ノードは、無線ノードからビーコンを送信したかどうか、ビーコンのうちの少なくとも１つの送信時間、ビーコンのうちの１つが他のビーコンまたは信号と衝突している、または衝突した可能性があること、またはビーコンマップに基づいた他のビーコンの状態情報、を判断することが可能である。
【図面の簡単な説明】
【００１２】
【図１】例示的な一実施形態による、無線メッシュネットワークを示す図である。
【００１３】
【図２】２つのメッシュポイントからのビーコンメッセージの衝突の一例を示すタイミング図である。
【００１４】
【図３】例示的な一実施形態による、異なるメッシュポイントからのビーコンメッセージの送信をどのように分離することが可能であるのか示すタイミング図である。
【００１５】
【図４】例示的な一実施形態による、無線ノードのオペレーションを示すフローチャートの図である。
【００１６】
【図５】別の例示的な実施形態による、無線ノードのオペレーションを示すフローチャートの図である。
【００１７】
【図６】例示的な一実施形態による、無線ノード内に備えることが可能な装置を示すブロック図である。
【詳細な説明】
【００１８】
図（同じ符号は同じ要素を示す）を参照する。図1は、例示的な一実施形態による、無線メッシュネットワーク100を示す図である。
【００１９】
例示的な一実施形態によれば、無線メッシュネットワークは、無線リンクと相互接続する一群のメッシュポイント（MP）とすることが可能である。各MPは、アクセスポイント（AP）、無線局、または他の無線ノードとすることが可能である。例えば、無線メッシュネットワークは、完全なメッシュトポロジまたは部分的なメッシュトポロジを用いることが可能である。完全なメッシュトポロジでは、各ノード（またはメッシュポイント）は、無線リンクを経て、他のMPのそれぞれに直接接続することが可能である。部分的なメッシュトポロジでは、メッシュポイントは、メッシュネットワーク内の他のメッシュポイントの一部（必ずしも全てではない）に接続することが可能である。
【００２０】
図1に示される無線メッシュネットワーク100の例では、メッシュポイントMP1、MP2、およびMP3は、有線または無線リンクを経て相互接続することが可能である。また、各メッシュポイント（MP）は、そのローカルセルにおいて１つ以上の無線局に接続することが可能である。例えば、MP1は、セル104内に位置し、無線リンクを経てセル104内のSTA2およびSTA3に接続される。MP2は、セル106内に位置し、無線リンクを経てSTA1に接続される。MP3は、セル102内に位置し、無線リンクを経てSTA4に接続される。無線メッシュネットワーク100は、単なる例示的なネットワークであり、本開示はこれに限定されるものではない。
【００２１】
無線メッシュネットワークの一例では、本開示はこれに限定されないが、各MPは、多対多の接続が可能であり、ネットワークトポロジの学習、動力経路構成、他のネットワーク機能が可能である。各MPはまた、本開示はこれに限定されないが、モバイルであるか、または移動させることができるか、または移動可能であり、それ自体を動的に再構成することが可能である。
【００２２】
各MPは、ビーコンメッセージを送信することが可能であり、また他のMPからビーコンメッセージを受信することが可能である。例示的な一実施形態では、本開示はこれに限定されないが、ビーコンメッセージは、メッシュポイントによって送信される管理または制御メッセージであり、メッシュポイントは、送信元MPに関する情報を提供し、および／または他の無線局またはMPが、MPとの通信を確立することができるようにする。ビーコンメッセージには、例えば、ビーコン間隔（またはビーコン送信間の時間の長さ）のような情報、タイムスタンプ、特定のWALNを識別するネットワークIDまたはSSID（Service Set Identifier; サービスセットID）、対応するデータレートの表示、パラメータセットまたは対応する特定のシグナリング方法に関する情報、機能情報（有線と同等のプライバシー、すなわちWEP（Wired Equivalency Privacy）プロトコルに対応するかどうか、など）、および他の情報を含むことが可能である。
【００２３】
本願明細書に記載される様々な実施形態は、WLANネットワーク（例、IEEE 802.11型ネットワーク）、IEEE 802.16 WiMAXネットワーク、WiMediaネットワーク、超広帯域ネットワーク、携帯電話ネットワーク、無線ネットワーク、または他の無線ネットワークのような、多種多様なネットワークおよび技術に適用可能である。別の例示的な実施形態では、様々な例および実施形態を、例えば、複数のメッシュポイント（例、アクセスポイント）が、有線または無線リンクを経て互いに接続することが可能である、メッシュ無線ネットワークに適用することが可能である。本願明細書に記載される様々な実施形態は、APまたは基地局が、局と通信することが可能な（例、APを介して通信が生じる）インフラモード、および、無線局が、例えばピアツーピアネットワークを経て直接通信することが可能なアドホックモードの両方で、無線ネットワークに適用することが可能である。
【００２４】
"無線ノード"や"ノード"などの用語には、例えば、移動局または加入者局のような無線局、アクセスポイント（AP）または基地局、中継局、無線携帯情報端末（Wireless Personal Digital Assistant; PDA）、携帯電話、802.11 WLAN電話、WiMedia装置、WiMAX装置、無線メッシュポイント（MP）、または他の無線装置を含むことが可能である。これらは単に、本願明細書に記載された様々な実施形態を実施するために使用することが可能な無線装置および技術の少数の例であり、本開示はこれに限定されるものではない。
【００２５】
図2は、２つのメッシュポイントからのビーコンメッセージの衝突の一例を示すタイミング図である。図2に示されるように、ビーコンメッセージの衝突は、同じ周波数で動作する２つの接近して位置するMPが、それらのビーコンメッセージを同じか、またはほぼ同じ時間（例、同じ送信権すなわちTXOP（Transmission Opportunity）の間に送信する場合に生じる可能性がある。図2に示される例では、MP1およびMP2は、互いに十分近接して位置しており、それらのネットワークの受信範囲が重なっている。MP1のターゲットビーコン送信時間（Target Beacon Transmission Time; TBTT）を204で示し、MP2のTBTTを206で示すが、これは媒体がアイドルの場合に、それらのビーコンを送信するためのターゲット時間である。MP1およびMP2それぞれのTBTT204および206は、NAV（Network Allocation Vector; ネットワーク割り当てベクトル）の間に生じるので、MP1およびMP2はどちらも、例えばNAV時間202が終了した後の、ポイントインターフレームスペース（PIFS、210）のタイムアウトの後に、それらのビーコンメッセージを送信する。一実施形態では、NAV時間202は、MP1およびMP2がTBTT上でそれらのビーコンを送信できないように、通信チャネルを占有するデータ送信を表す。この具体例では、MP1は、そのビーコンメッセージ212を最初に送信し、続いて、媒体が利用可能になった後に、MP2がビーコンメッセージ214を送信する。MP2からのビーコンメッセージ214は、ビーコンメッセージ212と衝突してデータの破壊を生じさせる。これは、ビーコンメッセージには競合解決のための技術が現在提供されていないので、今日の無線システムにおいて生じる場合がある。
【００２６】
したがって、例示的な一実施形態によれば、各MPは、ビーコンマップを生成および保持し、次いでこれらのビーコンマップを他のMPと交換することが可能である。例示的な一実施形態によれば、MPによって保持されるビーコンマップは、最後のビーコン期間内にMPが受信したビーコンメッセージのリストを含むことが可能である。この情報（ビーコンマップ）は、ビーコンマップメッセージまたは他のメッセージを経て他のMPと共有することができる。
【００２７】
例示的な一実施形態では、ビーコンマップは、MPに、その隣接（第2のホップ隣接）の隣接に関する（部分的な）情報をさらに提供することが可能である。ビーコンマップを使用して、新しいMPがメッシュネットワーク加わるときに、適切な（利用可能な）および不適切な（利用不可能な）ビーコン送信時間を示すか、またはいつ送信エラーがいつ生じるかを、ビーコンに示す（ビーコンメッセージ）ことが可能である。
【００２８】
初期化時に、MPは無線チャネルをスキャンすることが可能であり、また、すでにメッシュネットワーク内にあるMPと関連付けることが可能である。メッシュネットワークが作動中でない場合、MPは新しいものを起動することができる。プローブまたは関連付けメッセージでは、MPは、受信側MPからのビーコンマップの送信をリクエストするか、または別個のリクエストビーコンマップメッセージを送信して、ビーコンマップをリクエストすることが可能である。また、ビーコン期間、メッシュネットワーク内のノードの最大数などのような、他の機能パラメータを交換することが可能である。
【００２９】
例示的な実施形態によれば、ビーコンマップは、最後のビーコン期間内にMPが受信した１つ以上のビーコンメッセージ（ビーコン）のリストと、受信されたビーコンに関する情報とを含むことが可能である。ビーコンマップ内に提供されるこのビーコン情報は、例えば、ビーコンのタイムインスタンスまたはタイムスタンプと、ビーコンを送信したMPの識別と、ビーコンの（チャネル）状態とを含むことが可能である。複数の異なるチャネル状態は、本開示はこれに限定されないが、アイドル、受信、および衝突のように、ビーコンマップ内で指定することが可能である。
【００３０】
表1は、例示的なビーコンマップを示す。各受信されたビーコンに対して、ビーコンマップは、例えば、受信されたビーコンのタイムスタンプ（または時間情報）と、ビーコンを送信する（またはビーコンに関連付けられた）MPと、ビーコンの状態（例、受信、アイドル、または衝突）とをリストすることが可能である。ビーコンに対するチャネル状態が衝突である場合には、MPは、そのビーコンに対する連続した衝突のカウント数を保持することが可能である（例えば、それは連続するビーコン期間におけるそのビーコンに対する衝突回数の検出を示す）。ビーコンマップは、異なる情報および／または追加情報を含むことが可能である。例示的な実施形態では、ビーコンマップは、送信元MPのビーコン送信時間を示すタイムスタンプ情報と、MP自体のビーコンのタイムスタンプに関連する他のMPのビーコンメッセージの受信時間とを含むことが可能である。受信側MPは、これで、それ自体のクロックに関連するビーコンの送信を判断することができる。ビーコン送信時間が分かると、その情報は、全てのビーコンの代わりに、特定のビーコンだけのリスニングに使用することができる。これは、省電力のオプションに使用することができる。さらに、マップは、送信元MPのMACアドレスと、状態（アイドル、受信、衝突）を含むことが可能である。また、図3に示されるように、他のMPのMACアドレスと、それらのビーコンの状態も含むことも可能である。
【表１】
2008529382.tif 000003
【００３１】
通常動作では、ビーコンメッセージは、全てのビーコン期間で受信される。（ビーコンの）チャネル状態がアイドルである場合、古いMPとともに、ビーコンメッセージは、モビリティに関する情報を提供することができる。例えば、アイドルの状態は、MPが移動されたか、またはもはや動作していないか、あるいは（以下に詳述するように）そのビーコンを再配置したこと、などを示すことが可能である。したがって、ビーコンマップは、MPからビーコンを受信していないことを示す。このような場合、ビーコンマップ内に示されるMPは、その瞬間に作動中の最新のMPである。また、例示的な一実施形態では、衝突のチャネル状態がビーコンスロットに対して検出された場合、ビーコンマップ内に示されるMPは、その瞬間に作動中の最新のMPである。
【００３２】
一実施形態では、ビーコンマップは、MPがビーコンの衝突を検出したときに（例えば、ビーコンマップメッセージを経て）送信することが可能である。例示的な一実施形態では、ビーコンに対する衝突カウント（この衝突カウント数は、設計パラメータとすることが可能である）が所定の衝突数を越えたときに、MPは、ビーコンマップを送信することが可能である。別様には、MPは、リクエスト時に（例えば、リクエストビーコンマップメッセージの受信時に）、そのビーコンマップを別のMPに送信することが可能である。一実施形態では、本出願はこれに限定されないが、ビーコンマップは、ネットワークに不要な更なるトラフィックを追加しないように、ビーコンの衝突が検出されたとき、またはリクエスト時にだけ送信される。別の実施形態では、ビーコンメッセージの長さが長くなるが、MPは、ビーコンメッセージ内のそのビーコンマップを送信することが可能である（例えば、ビーコンマップは、ビーコンメッセージ内に添付するか、または提供することが可能である）。
【００３３】
古いMPとの衝突の状態は、MP間の衝突解決機構に使用することができる。ビーコンマップによって、無線メッシュネットワーク内の１つ以上のMPは、ビーコンの衝突が生じたことを判断することができる。例示的な一実施形態では、少なくともいくつかの状況では、ビーコンマップによって、MPのうちの１つ以上は、どのビーコンが衝突したのかを識別することができる。
【００３４】
例えば、ビーコンの衝突に関与する１つまたは両方のMPが衝突を検出するか、またはネットワーク内の他のMPが衝突を検出することが可能である。例えば、図2に示されるように、MPは、ビーコン214（MP2）による衝突がデータの破損を生じる前に、短期間でMP1からのビーコン212を検出することが可能である。したがって、衝突を検出したMPは、次いで、MP1、（例えばビーコンの）タイムスタンプ、およびMP1のビーコンに対するチャネル状態が衝突であることを示すビーコンマップを生成することが可能である。このビーコンマップは、MP2（衝突ビーコン214を送信したMP）によって受信することが可能である。MP2は、次いで、そのビーコンに対するそれ自体のタイムスタンプと、"衝突"の状態であるあらゆるビーコンに対するビーコンマップ内のタイムスタンプとを比較することが可能である。この場合、ビーコン214（MP2）のビーコンのタイムスタンプの時間が、受信されたビーコンマップ内に提供される衝突ビーコン212（MP1）のタイムスタンプに近接していることを、そのビーコン214がMP1からのビーコン212と衝突したMP2に示すことが可能である。これは単に、ビーコンマップを使用して、どのようにビーコンの衝突解決を達成することが可能であるかを示す一例である。他の技術を使用することも可能である。
【００３５】
そのビーコンが他のビーコンと衝突している（または衝突する可能性がある）とMPが判断すると、MPは、以降のビーコンの衝突の可能性を減じるように、そのビーコンを再配置することが可能である。例示的な実施形態によれば、MPは、最小ビーコン距離だけ、そのビーコンを再配置するか、または他の衝突ビーコンから最小ビーコン距離だけ離して配置することが可能である。最小ビーコン距離（２つのビーコンメッセージ間の送信開始の時間差）は、次式のように決定することが可能である。
【００３６】
2008529382.tif 000004
【００３７】
ここで、tbeaconはビーコン期間の継続期間であり、NMAXはシステム内で同一周波数でビーコンを送信するノードの最大数である。例示的な実施形態では、NMAXは、設計パラメータであり、ネットワークを設定するとき、または別のときに設定することが可能である。これはシナリオによって決まり、家庭環境ではより小さくすることができ、オフィスや小さなキャンパスではより大きくすることができる。例示的な実施形態によれば、NMAXは、32ノードに設定することが可能であるが、他の数を使用することも可能である。
【００３８】
MPは、２つのビーコンメッセージの送信の間に収まるように、最大TXOPの限度を決定することも可能である。
【００３９】
2008529382.tif 000005
【００４０】
ここで、tTx_beaconはビーコンメッセージの送信時間であり、PFISはポイントインターフレームスペースであり、tguardは同期誤差を取り入れるように導入される保護時間である。
【００４１】
図3は、例示的な一実施形態による、異なるメッシュポイントからのビーコンメッセージの送信をどのように分離することが可能であるのか示すタイミング図である。この例では、図2に示される衝突を示したビーコンマップに基づいて、衝突の可能性を減じるように、MP1はそのTBTT304を保持し、MP2は、MP1のTBTT303からいくらかの距離または時間離して、TBTT306およびビーコン314を再配置している。例示的な一実施形態では、再配置に使用することが可能な距離は、上述のような最小ビーコン距離とすることが可能である。MP2のTBTTはNAV保護時間の間にないので、MP2はTBTTにスケジュールされたようにそのビーコンを送信することができる。MP1のTBTTはNAV保護時間の間にあるので、図3のMP1は、ビーコン312を送信できる前に、NAV保護が終了した後にPIFS210を待たなければならない。
【００４２】
どの衝突MPがそれらのビーコンを再配置しなければならないかを判断するための、複数の異なる技術がある。衝突の場合における例示的な再配置方法には以下が挙げられる。
【００４３】
1） 衝突に関与する全てのMP（衝突ビーコンを有する）が、それらのビーコンを再配置する。これは単純だが、２つ以上のMPが、それらのビーコンの再配置またはそれらのビーコンの再配置位置の決定の同じ技術を使用した場合に、以降の衝突を生じさせる場合がある。
【００４４】
2） （衝突に関与する２つ以上のMPの間で）最も低いMACアドレスを再配置する。例示的な一実施形態では、MP（衝突MPのうちの１つなど）は、最も低いMACアドレスを有する衝突MPに再スケジュールメッセージを送信して、そのビーコンを再配置するようにこのMPにリクエストする。別様には、より高い、または最も高いMACアドレスを有するMPを再配置する。
【００４５】
3） 新しいMPを再配置しなければならないが、古いMPはそれらのビーコン送信時間を保持することができる。
【００４６】
4） （図2のMP1のような）衝突に関与するビーコンを送信するために、第1のMPはそのビーコン送信時間またはビーコンの位置を保持することが可能である。一方で、第1のビーコンの後にそれらのビーコンを送信した、衝突に関与するMPは、それらのビーコンを再配置しなければならない（例えば、図2のMP2は、ビーコン214がビーコン212のあとに来たので、そのビーコンを再配置する）。MPは、それ自体のビーコンをいつ送信したのかを示す、それ自体のクロックまたはそれ自体のタイムスタンプと比較して、ビーコンマップ内のタイムスタンプ情報に基づいてこれを決定することができる。
【００４７】
定常状態での動作中に、MPは、メッシュネットワーク内の他のMPに、そのMPが現在受信しているビーコンメッセージのマップを含む、特別な制御メッセージによって現在受信しているそれらのビーコンメッセージを共有するようにリクエストすることができる。マップは、他のMPの隣接したノードに関する情報を提供することが可能であり、またメッシュネットワーク内のノードの数のインプレッションを提供することが可能である。例示的な一実施形態により、ビーコンマップは、修正したプローブまたは関連付けメッセージ、あるいはリクエストビーコンマップの特別なメッセージを送信することによってリクエストすることが可能であり、一般的なルーティングおよびネットワーク状態の情報フレームの一部とすることが可能である。
【００４８】
例示的な一実施形態では、衝突が生じていること、およびビーコン送信時間を変更できることをMPが認識できるように、MPは、衝突した場合に、そのビーコンマップを他のMPに送信するように定義することが可能である。このために、カウンタ（beacon_collision）を各MPで使用することが可能であり、１つの時間インスタンスに関する衝突の数を記録する。例示的な一実施形態では、このカウンタが所定の数を超えた場合、ビーコンマップを送信して、隣接したノードにビーコンの衝突を通知することが可能である。カウンタの値は、MPとノードとの間で交換する初期機能の一部とすることが可能である。
【００４９】
別の例示的な実施形態によれば、beacon_collisionカウンタが所定の値（例えば1）以上のときに、MPがそのビーコンを送信したことに気付いた場合は、フレームを送信して他のターミナルに通知することが可能である。２つ以上のMPが、同時にビーコンを送信する（およびどのMPも"再スケジュールリクエスト"メッセージを送信していない）ことを、１つのMPが通知された場合、MPは、"再スケジュールリクエスト"メッセージを、低いMACアドレス（または高いMACアドレス、規則に従う）を有するMPに送信する。
【００５０】
１つ以上または全てのMPは同じビーコン期間を適用することができる。別の例示的な実施形態では、異なるMPは、異なるビーコン期間を適用することができるが、この情報（ビーコン期間）は、ビーコンマップに含まれることになり、情報がより大きくなる。
【００５１】
図4は、例示的な一実施形態による、無線ノードのオペレーションを示すフローチャートの図である。410で、１つ以上の無線ノードからビーコンを受信する。例えば、無線ネットワーク内１つ以上（または全ての）MPまたはAPは、ビーコンを送信することが可能である。420で、受信ビーコンに基づいて、ビーコンマップを生成する。
【００５２】
430で、生成されたビーコンマップは、１つ以上の無線ノードに送信される。ビーコンマップは、受信されたビーコンのうちの１つ以上に関する情報を提供することが可能である。例えば、ビーコンマップは、メッセージ内のビーコンのタイミング情報要素として、またはその中に送信することが可能である。オペレーション430には、例えば、ビーコンマップの１つ以上の無線ノードへの送信と、ビーコンのタイムスタンプまたは時間情報を提供するビーコンマップと、１つ以上の受信されたビーコンの送信元無線ノードのアドレスとを含むことが可能である（432）。アドレスには、例えば、ビーコンの送信元ノードのMAC（Media Access Control; 媒体アクセス制御）アドレスを含むことが可能である。
【００５３】
送信するオペレーション430は、例えば、プローブリクエストまたは他のリクエストメッセージのようなリクエストメッセージの受信、およびリクエストメッセージの受信に応じてのビーコンマップの送信を含むことが可能である。ビーコンマップは、プローブ応答または、例えば、他のメッセージで送信することが可能である。別の一実施形態では、ビーコンマップは、ビーコンで送信することが可能である。
【００５４】
図4のフローチャートは、例示的な一実施形態による、オペレーション440および450を含むことが可能である。440で、送信されたビーコンマップは、受信側無線ノードで受信することが可能である。450で、ビーコンは、ビーコンマップに基づいて再配置することが可能である。例えば、受信側ノードは、ビーコンマップに基づいて、そのビーコンを異なる時間に再配置して、他のビーコンとの衝突の可能性を減じることが可能である。例えば、受信側ノードは、そのビーコンに対して、そのターゲットビーコン送信時間を変更することができる。別の例示的な実施形態では、受信側ノードは、メッセージを別のノードに送信して、他のノードに、ビーコンマップに基づいて、そのビーコンを再配置するように他のノードにリクエストして、ビーコンの衝突の可能性を減じることが可能である。
【００５５】
図5は、別の例示的な実施形態による、無線ノードのオペレーションを示すフローチャートの図である。510で、ビーコンマップは、受信側無線ノードで受信される。ビーコンマップは、１つ以上の他の無線ノードからのビーコンに関する情報を提供することが可能である。例えば、ビーコンマップは、ビーコンのタイミング情報要素として、またはその中に提供することが可能である。オペレーション510は、受信側無線ノードでのビーコンマップの受信を含むことが可能であり、ビーコンマップは、ビーコンのタイムスタンプまたは他の時間情報、およびビーコンのそれぞれの送信元無線ノードのアドレスを含むことが可能である（512）。
【００５６】
520で、ビーコンマップに基づいて、１つ以上の無線ノードからのビーコンのうちの少なくとも１つの状態を判断することが可能である。オペレーション520は、オペレーション522、524、および／または526のような１つ以上の他のオペレーションを含むことが可能である。ビーコンマップに基づいて、異なるタイプのビーコンの状態を判断することが可能である。
【００５７】
オペレーション522で、ノードからのビーコンが送信されたか、または送信されているかを判断することが可能である。例えば、ビーコンマップが、ノードのアドレスおよびビーコンのタイムスタンプまたは時間オフセット（例、ビーコン送信時間を示す）をリストする場合、これは、そのようなノードのビーコンが送信されていることを示すことが可能である。
【００５８】
オペレーション524で、ビーコンマップに基づいて、１つ以上の無線ノードからのビーコンのうちの少なくとも１つのビーコン送信時間を決定することが可能である。例えば、受信側ノードは、例えばタイムスタンプまたはビーコンのビーコンマップ内に提供された時間オフセットに基づいて、ビーコン送信時間を決定することが可能である。
【００５９】
オペレーション526で、ビーコンのうちの１つが別のビーコンまたは信号と衝突していると判断することが可能である。例えば、ビーコンマップ内のビーコンのタイムスタンプを比較することによって、時間値またはタイムスタンプ値におけるオーバーラップまたは近さに基づいて、２つのビーコンが衝突した可能性があると判断することが可能である。受信局は、例えばビーコンマップ内に提供された他のビーコンの時間情報に基づいて、それ自体のビーコンが衝突しているか、または衝突する可能性があるかを判断することも可能である。
【００６０】
オペレーション530で、ビーコンマップに基づいて、ビーコンを再配置することが可能である。ビーコンは、例えば、ターゲットビーコン送信時間を変更することによって、再配置することが可能である。例示的な一実施形態では、受信側ノードは、そのビーコンを再配置して、例えば他のビーコンとの衝突の可能性を減じることが可能である。
【００６１】
例示的な一実施形態では、オペレーション530は、オペレーション532および／または534を含むことが可能である。オペレーション532で、ビーコンマップに基づいて、他の無線ノードのうちの１つからのビーコンが、受信側無線ノードから送信されたビーコンと衝突しているか、または衝突する可能性があるかを判断することが可能である。オペレーション534で、受信側無線ノードから送信されるビーコンは、その判断（オペレーション532）に基づいて、ターゲットビーコン送信時間を変更することによって再配置することが可能である。
【００６２】
例示的な一実施形態では、各無線ノードまたはメッシュポイント（MP）には、無線トランシーバ、プロセッサまたは制御器、およびメモリを含むことが可能である。図6は、例示的な一実施形態による、無線ノード内に備えることが可能な装置600を示すブロック図である。局、AP、MPなどのような無線ノードは、例えば、信号を送受信するための無線トランシーバ602と、局またはノードの動作を制御し、命令またはソフトウェアを実行するための制御器604と、データおよび／または命令を格納するためのメモリ606とを含むことが可能である。
【００６３】
制御器604は、プログラム可能で、ソフトウェアまたはメモリまたは他のコンピュータ媒体に格納された他の命令を実行して、図1乃至5にある上述の１つ以上のタスクまたはメソッドのような、上述の様々なタスクおよび機能を実行することが可能である。例えば、装置600は、制御器604および装置600内の他のデバイスの動作を介して、１つ以上の無線ノードからビーコンを受信したり、ビーコンマップを生成したり、１つ以上の無線ノードにビーコンマップを送信したりすることが可能である。別の例示的な実施形態では、装置600は、制御器604の動作などを介して、受信側ノードでビーコンマップを受信することが可能であり、ビーコンマップは、１つ以上の他の無線ノードからのビーコンに関する情報を提供して、そのビーコンマップによって、１つ以上の無線ノードからのビーコンのうちの少なくとも１つの状態を判断する。
【００６４】
加えて、制御器またはプロセッサ（メッシュポイントプロセッサなど）により実行されたときに、MPまたはMPプロセッサが、上述の機能またはタスクのうちの１つ以上を実行する、記憶された命令を含む記憶媒体を備えることが可能である。例えば、制御器604により実行されたときに、無線ノードまたは制御器604が、図1乃至5を参照して上述した機能またはタスクのうちの１つ以上を実行する、記憶された命令を含む記憶媒体を備えることが可能である。
【００６５】
本願明細書に記載された様々な技術の実施形態は、デジタル電子回路、またはコンピュータハードウェア、ファームウェア、ソフトウェア、あるいはそれらを組み合わせたものに実装することが可能である。これらの実施形態は、コンピュータプログラムとして、すなわち、データ処理装置（例、プログラム可能なプロセッサ、コンピュータ、または複数のコンピュータ）による実行のための、またはそのオペレーションを制御するための、例えば機械可読の記憶装置内の、または伝播信号内の情報担体に明白に組み込まれたコンピュータプログラム製品として実装することが可能である。上述のコンピュータプログラムまたはメソッドのようなコンピュータプログラムは、コンパイルまたは翻訳されたあらゆる形態のプログラミング言語で作成することができ、また、スタンドアロンプログラム、またはモジュール、コンポーネント、サブルーチン、あるいは、コンピューティング環境での使用に適した他のユニットを含む、あらゆる形態で導入することが可能である。コンピュータプログラムは、１つのサイトの、または複数のサイトにわたって配置された１つのコンピュータまたは複数のコンピュータで実行するように、また通信ネットワークによって相互接続されるように導入することができる。
【００６６】
方法ステップは、コンピュータプログラムを実行する、１つ以上のプログラマブルプロセッサによって行い、データを入力して出力を生成することによって機能を実行することが可能である。方法ステップは、例えばFPGA（Field Programmable Gate Array; フィールドプログラマブルゲートアレイ）、またはASIC（Application-Specific Integrated Circuit; 特定用途向け集積回路）などの専用ロジック回路によって実行することが可能であり、また、装置は専用ロジック回路として実装することが可能である。
【００６７】
例示的な実施形態の特定の機能を、本願明細書に記載したように示してきたが、多数の修正、置換、変更、および同等品が、当業者に生じることになる。したがって、添付の特許請求の範囲は、そのようなすべての修正と変更を、種々の実施形態の真の精神の範囲内としてカバーすることを意図するものであると理解されたい。
【図１】
2008529382.tif 000006
【図２】
2008529382.tif 000007
【図３】
2008529382.tif 000008
【図４】
2008529382.tif 000009
【図５】
2008529382.tif 000010
【図６】
2008529382.tif 000011
【国際調査報告】
2008529382.tif 000012
2008529382.tif 000013
2008529382.tif 000014
2008529382.tif 000015