JP6026675B2 - ワイヤレスネットワークのサイズの監視 - Google Patents

ワイヤレスネットワークのサイズの監視 Download PDF

Info

Publication number
JP6026675B2
JP6026675B2 JP2015555281A JP2015555281A JP6026675B2 JP 6026675 B2 JP6026675 B2 JP 6026675B2 JP 2015555281 A JP2015555281 A JP 2015555281A JP 2015555281 A JP2015555281 A JP 2015555281A JP 6026675 B2 JP6026675 B2 JP 6026675B2
Authority
JP
Japan
Prior art keywords
bloom filter
wireless device
neighboring wireless
bits
neighboring
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2015555281A
Other languages
English (en)
Other versions
JP2016506215A5 (ja
JP2016506215A (ja
Inventor
アブラハム、サントシュ・ポール
スワミナサン、アシュウィン
チェリアン、ジョージ
ライシニア、アリレザ
フレデリクス、ギード・ロベルト
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Qualcomm Inc
Original Assignee
Qualcomm Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Qualcomm Inc filed Critical Qualcomm Inc
Publication of JP2016506215A publication Critical patent/JP2016506215A/ja
Publication of JP2016506215A5 publication Critical patent/JP2016506215A5/ja
Application granted granted Critical
Publication of JP6026675B2 publication Critical patent/JP6026675B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W8/00—Network data management
    • H04W8/005—Discovery of network devices, e.g. terminals
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W52/00—Power management, e.g. Transmission Power Control [TPC] or power classes
    • H04W52/02—Power saving arrangements
    • H04W52/0209—Power saving arrangements in terminal devices
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D30/00—Reducing energy consumption in communication networks
    • Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Databases & Information Systems (AREA)
  • Mobile Radio Communication Systems (AREA)

Description

[0001] 本出願は、一般にワイヤレス通信に関し、より詳細には、ワイヤレスネットワークのサイズを監視するためのシステム、方法、およびデバイスに関する。
[0002] 多くの電気通信システムでは、通信ネットワークは、空間的に分離されたいくつかの対話しているデバイスの間でメッセージを交換するために使用される。ネットワークは、たとえば、メトロポリタンエリア、ローカルエリア、またはパーソナルエリアであり得る地理的範囲に従って分類され得る。そのようなネットワークは、それぞれ、ワイドエリアネットワーク（ＷＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、ワイヤレスローカルエリアネットワーク（ＷＬＡＮ）、またはパーソナルエリアネットワーク（ＰＡＮ）として指定されるであろう。ネットワークはまた、様々なネットワークノードとデバイスとを相互接続するために使用されるスイッチング／ルーティング技法（たとえば、回線交換対パケット交換）、送信のために採用される物理媒体のタイプ（たとえば、ワイヤード対ワイヤレス）、および使用される通信プロトコルのセット（たとえば、インターネットプロトコルスイート、ＳＯＮＥＴ（同期光ネットワーキング）、イーサネット（登録商標）など）によって異なる。
[0003] ワイヤレスネットワークは、ネットワーク要素がモバイルであり、したがって動的接続性の必要を有するときに、またはネットワークアーキテクチャが固定ではなくアドホックなトポロジーで形成される場合に、しばしば好適である。ワイヤレスネットワークは、無線、マイクロ波、赤外線、光などの周波数帯域内の電磁波を使用する非誘導伝搬モードでは、無形物理媒体を採用する。ワイヤレスネットワークは、有利なことに、固定ワイヤードネットワークと比較して、ユーザモビリティと迅速なフィールド展開とを容易にする。
[0004] ワイヤレスネットワーク中のデバイスは、互いの間で情報を送信および／または受信し得る。その情報は、いくつかの態様ではデータユニットと呼ばれることがあるパケットを含み得る。パケットは、ネットワークを通してパケットをルーティングし、パケット中のデータを識別し、パケットを処理することなどを助ける、オーバーヘッド情報（たとえば、ヘッダ情報、パケットプロパティなど）を含み得る。パケットは、パケットのペイロード中で搬送され得る、ユーザデータ、マルチメディアコンテンツなどのデータをさらに含み得る。
[0005] ソーシャルＷｉＦｉ（登録商標）ネットワークなどのワイヤレスネットワークにおいて、スケーラブルな動作を可能にするために、ネットワークにおける各デバイスによる送信は、ネットワークにおけるデバイスの数に基づいて制御されるべきである。たとえば、ネットワークにおけるデバイスの数に基づいて、ビーコンおよび／またはタイミング信号が送信される際のレートを調整することが、望ましいことがある。多数の適用例では、ネットワークにおけるデバイスの数の概算推定値を取得することは、十分である。ワイヤレスデバイスがネットワークにおけるデバイスの数を追跡するための１つの方法は、メッセージにおいて受信され、デバイスを表す、任意の識別子を単に記憶することである。新しいメッセージが入ってくるときは常に、デバイスは、新しいメッセージ中の識別子を、デバイスにおいてすでに記憶されている識別子と比較し、その識別子が前に記憶されていない場合、その識別子を記憶することになる。ただし、この手法は、大きいメモリ要件と、より多数の受信された識別子をソートする必要性とにつながり得る。したがって、より大きいメモリ要件と、識別子をソートする必要性とを大きく低減することができる、ワイヤレスネットワークにおけるデバイスの数を追跡する方法を有することが、有益である。
[0006] 本明細書で説明されるシステム、方法、デバイス、およびコンピュータプログラム製品は、各々いくつかの態様を有し、それらのうちの単一の態様が単独でその望ましい属性に関与するとは限らない。以下の特許請求の範囲によって表される本発明の範囲を限定することなしに、いくつかの特徴について以下で手短に説明する。この説明を考察すれば、特に「発明を実施するための形態」と題するセクションを読めば、本発明の特徴が媒体上にデバイスを導入するときに低減された電力消費を含むことがどのように有利であるかを、通常のスキリｎ当技術分野のうちの１つは諒解されよう。
[0007] 本開示の一態様は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視するように構成されたワイヤレスデバイスを提供する。ワイヤレスデバイスは、近隣ワイヤレスデバイスのうちの１つからメッセージを受信するように構成された受信機を含み、メッセージは、近隣ワイヤレスデバイスに関連付けられた識別子を備える。ワイヤレスデバイスは、ブルームフィルタに識別子を追加するように、および、ブルームフィルタにおける０の数に基づいて、ブルームフィルタに追加された別個の文字列の数を推定するように構成されたプロセッサをさらに含んでよく、別個の文字列の数は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数の推定値を表す。
[0008] 本開示の別の態様は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視する方法を提供する。方法は、近隣ワイヤレスデバイスに関連付けられた識別子を備えるメッセージを、近隣ワイヤレスデバイスのうちの１つから受信することと、ブルームフィルタに識別子を追加することとを含む。方法は、ブルームフィルタにおける０の数に基づいて、ブルームフィルタに追加された別個の文字列の数を推定することをさらに含んでよく、別個の文字列の数は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数の推定値を表す。
[0009] 本開示の別の態様は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視するためのワイヤレスデバイスを提供する。ワイヤレスデバイスは、近隣ワイヤレスデバイスに関連付けられた識別子を備えるメッセージを、近隣ワイヤレスデバイスのうちの１つから受信するための手段と、ブルームフィルタに識別子を追加するための手段とを含む。ワイヤレスデバイスは、ブルームフィルタにおける０の数に基づいて、ブルームフィルタに追加された別個の文字列の数を推定するための手段をさらに含んでよく、別個の文字列の数は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数の推定値を表す。
[0010] 本開示の別の態様は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視するための方法を実施するように構成されたコンピュータ実行可能命令を備える、非一時的物理的コンピュータストレージを提供する。方法は、近隣ワイヤレスデバイスに関連付けられた識別子を備えるメッセージを、近隣ワイヤレスデバイスのうちの１つから受信することと、ブルームフィルタに識別子を追加することとを含む。方法は、ブルームフィルタにおける０の数に基づいて、ブルームフィルタに追加された別個の文字列の数を推定することをさらに含んでよく、別個の文字列の数は、ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数の推定値を表す。
[0011] 本開示の態様が採用され得るワイヤレス通信システムの一例を示す図。 [0012] 図１のワイヤレス通信システム内で採用され得るワイヤレスデバイスの機能ブロック図。 [0013] ワイヤレス通信を送信するためにワイヤレスデバイスにおいて利用され得る様々な構成要素を示す図。 [0014] ワイヤレス通信を受信するためにワイヤレスデバイスにおいて利用され得る様々な構成要素を示す図。 [0015] 一実装形態による、ワイヤレスネットワークにおけるワイヤレスデバイスの数を監視する方法のフローチャート。 [0016] 一実装形態による、ブルームフィルタの１つの例示的な例を示す図。 [0017] ネットワークにおけるワイヤレスデバイスの数と、ブルームフィルタからの推定された数とを比較する、シミュレーション結果を示す図。 [0018] 推定誤り率対ネットワークにおけるワイヤレスデバイスの数を示す、シミュレーション結果を示す図。 [0019] 例示的なベンダー固有発見フレームを示す図。 [0020] 図１のワイヤレス通信システム内で採用され得る発見タイプ長さ値（ＴＬＶ）を示す図。 [0021] 本開示の態様が採用され得る別のワイヤレス通信システムの一例を示す図。 [0022] 媒体アクセス制御（ＭＡＣ）フレームの例示的な構造を示す図。 [0023] 図１１のワイヤレス通信システム内で採用され得る例示的なサービス発見属性を示す図。
[0024] 「例示的」という単語は、本明細書では「例、事例、または例示の働きをすること」を意味するために使用される。本明細書で「例示的」であるとして説明されるいかなる実施形態も、必ずしも他の実施形態よりも好ましいまたは有利であると解釈されるべきではない。添付の図面を参照しながら新規のシステム、装置、および方法の様々な態様について以下でより十分に説明する。ただし、本開示は、多くの異なる形態で実施され得、本開示全体にわたって提示される任意の特定の構造または機能に限定されるものと解釈されるべきではない。むしろ、これらの態様は、本開示が周到で完全になり、本開示の範囲を当業者に十分に伝えるように与えられる。本明細書の教示に基づいて、本開示の範囲は、本発明の任意の他の態様とは無関係に実装されるか、本発明の任意の他の態様と組み合わされるかにかかわらず、本明細書で開示される新規のシステム、装置、および方法の任意の態様を包含するものであることを、当業者は諒解されたい。たとえば、本明細書に記載の態様をいくつ使用しても、装置は実装され得、または方法は実施され得る。さらに、本発明の範囲は、本明細書に記載の本発明の様々な態様に加えてまたはそれらの態様以外に、他の構造、機能、または構造および機能を使用して実施されるそのような装置または方法を包含するものとする。本明細書で開示されるいかなる態様も請求項の１つまたは複数の要素によって実施され得ることを理解されたい。
[0025] 本明細書では特定の態様について説明するが、これらの態様の多くの変形形態および置換は本開示の範囲内に入る。好適な態様のいくつかの利益および利点について説明するが、本開示の範囲は特定の利益、使用、または目的に限定されるものではない。むしろ、本開示の態様は、様々なワイヤレス技術、システム構成、ネットワーク、および送信プロトコルに広く適用可能であることが意図され、そのうちのいくつかが例として図面および好ましい態様の以下の説明において示される。発明を実施するための形態および図面は、限定的なものではなく本開示を説明するものにすぎず、本開示の範囲は添付の特許請求の範囲およびその等価物によって定義される。
[0026] 普及しているワイヤレスネットワーク技術は、様々なタイプのワイヤレスローカルエリアネットワーク（ＷＬＡＮ）を含み得る。ＷＬＡＮは、広く使用されるネットワーキングプロトコルを採用して、近接デバイスを互いに相互接続するために使用され得る。本明細書で説明される様々な態様は、ワイヤレスプロトコル、ＷｉＦｉ、またはより一般的には、ワイヤレスプロトコルのＩＥＥＥ８０２．１１ファミリーの任意のメンバーなど、任意の通信規格に適用され得る。たとえば、本明細書で説明される様々な態様は、サブ１ＧＨｚ帯域を使用するＩＥＥＥ８０２．１１ａｈプロトコルの一部として使用され得る。
[0027] いくつかの実装形態では、ＷＬＡＮは、ワイヤレスネットワークにアクセスする構成要素である様々なデバイスを含む。たとえば、クライアント（局または「ＳＴＡ」とも呼ばれる）。たとえば、ＳＴＡは、ラップトップコンピュータ、携帯情報端末（ＰＤＡ）、モバイルフォンなどであり得る。一例では、ＳＴＡは、インターネットまたは他のワイドエリアネットワークへの一般的接続性を得るために、ＷｉＦｉ（たとえば、ＩＥＥＥ８０２．１１プロトコル）準拠ワイヤレスリンクを介して他のＳＴＡに接続する。
[0028] 局「ＳＴＡ」はまた、アクセス端末（「ＡＴ」）、加入者局、加入者ユニット、移動局、モバイルデバイス、リモート局、リモート端末、ユーザ端末、ユーザエージェント、ユーザデバイス、ユーザ機器、または何らかの他の用語を含むか、それらのいずれかとして実装されるか、またはそれらのいずれかとして知られていることがある。いくつかの実装形態では、アクセス端末は、セルラー電話、コードレス電話、セッション開始プロトコル（「ＳＩＰ」）電話、ワイヤレスローカルループ（「ＷＬＬ」）局、携帯情報端末（「ＰＤＡ」）、ワイヤレス接続能力を有するハンドヘルドデバイス、またはワイヤレスモデムに接続された何らかの他の適切な処理デバイスもしくはワイヤレスデバイスを含み得る。したがって、本明細書で教示される１つまたは複数の態様は、電話（たとえば、セルラーフォンまたはスマートフォン）、コンピュータ（たとえば、ラップトップ）、ポータブル通信デバイス、ヘッドセット、ポータブルコンピューティングデバイス（たとえば、個人情報端末）、エンターテインメントデバイス（たとえば、音楽もしくはビデオデバイス、または衛星ラジオ）、ゲームデバイスまたはシステム、全地球測位システムデバイス、あるいはワイヤレス媒体を介して通信するように構成された任意の他の好適なデバイスに組み込まれ得る。
[0029] 局のグループなどのデバイスは、たとえば、ネイバーフッドアウェアネットワーク（ＮＡＮ：neighborhood aware network）、またはソーシャルＷｉＦｉネットワークにおいて使用され得る。たとえば、ネットワーク内の様々な局は、それらの局の各々がサポートするアプリケーションに関して、デバイス間（たとえば、ピアツーピア通信）ベースで互いと通信することができる。ソーシャルＷｉＦｉネットワークは、非集中タイプのワイヤレスネットワークである、アドホックワイヤレスネットワークであり得る。そのネットワークは、管理された（インフラストラクチャ）ワイヤレスネットワークにおけるアクセスポイントなど、先在するインフラストラクチャに依拠しないので、アドホックである。ソーシャルＷｉＦｉネットワークにおいて使用される発見プロトコルが、安全な通信と低電力消費とを保証しながら、モバイルデバイスが（たとえば、発見パケットまたはメッセージを送ることによって）自らを広告すること、ならびに（たとえば、ページングまたはクエリパケットまたはメッセージを送ることによって）他のＳＴＡによって提供されたサービスを発見することを可能にすることが望ましい。
[0030] 図１は、本開示の態様が採用され得るワイヤレス通信システム１００の一例を示す。ワイヤレス通信システム１００は、第１のモバイルデバイスクラスタ１１０と、第２のモバイルデバイスクラスタ１２０と、第３のモバイルデバイスクラスタ１３０と、モバイルデバイス１４２とを含む。
[0031] 第１のモバイルデバイスクラスタ１１０は、モバイルデバイス１１２、１１４、１１６、１１８を含む。第２のモバイルデバイスクラスタ１２０は、モバイルデバイス１１８、１２２、１２４、１２６、１２８を含む。第３のモバイルデバイスクラスタ１３０は、モバイルデバイス１３２、１３４、１３６、１３８を含む。図１の特定の例では、モバイルデバイス１４２は、モバイルデバイスクラスタ１１０、１２０、１３０のいずれにも加入していない（たとえば、そのメンバーではない）。さらに、図１の特定の例では、モバイルデバイス１１８は、複数のモバイルデバイスクラスタ（すなわち、モバイルデバイスクラスタ１１０、１２０）に加入している（たとえば、そのメンバーである）。
[0032] ワイヤレス通信システム１００は、他のモバイルデバイスのいずれかと通信することができる、モバイルデバイス１１２、１１４、１１６、１１８、１２２、１２４、１２６、１２８、１３２、１３４、１３６、および１３８を含み得る。一例として、モバイルデバイス１１２は、モバイルデバイス１１６と通信することができる。別の例として、モバイルデバイス１１２は、モバイルデバイス１１８と通信することができるが、この通信リンクは図１に示されない。
[0033] 様々なプロセスおよび方法が、モバイルデバイスのうちの任意の２つの間の、ワイヤレス通信システム１００における送信のために使用され得る。たとえば、信号は、ＯＦＤＭ／ＯＦＤＭＡ技法に従って送られ、受信され得る。そうである場合、ワイヤレス通信システム１００は、ＯＦＤＭ／ＯＦＤＭＡシステムと呼ばれることがある。代替として、信号は、ＣＤＭＡ技法に従って、モバイルデバイスのうちの任意の２つの間で送られ、受信され得る。そうである場合、ワイヤレス通信システム１００は、ＣＤＭＡシステムと呼ばれることがある。
[0034] 様々な実施形態によれば、ワイヤレス通信システム１００は、ネイバーフッドアウェアネットワークであってよく、モバイルデバイスクラスタ１１０、１２０、１３０のうちの１つまたは複数は、特定の共通のモバイルデバイスアプリケーションに関連付けられ得る。たとえば、モバイルデバイスクラスタ１１０、１２０、１３０の各々は、ソーシャルネットワーキングモバイルデバイスアプリケーション、ゲームモバイルデバイスアプリケーション、またはその組合せなど、それぞれの共通のモバイルデバイスアプリケーションに関連付けられ得る。
[0035] 動作時、ワイヤレス通信システム１００のモバイルデバイスは、１つまたは複数のワイヤレス通信プロトコルに従って、ワイヤレス通信することができる。たとえば、少なくとも１つの実施形態では、ワイヤレス通信システム１００のモバイルデバイスは、電気電子技術者協会（ＩＥＥＥ）８０２．１１プロトコルに関連付けられた発見ビーコンなど、発見メッセージを送り、受信することができる。別の例として、ワイヤレス通信システム１００のモバイルデバイスは、ワイヤレス通信システム１００の各モバイルデバイスに共通であるネットワーク広告プロトコルを介して通信することができる。別の例として、第１のモバイルデバイスクラスタ１１０は、ネットワーク広告プロトコルとは異なる第２のプロトコルを使用して通信することができる。同様に、第２のモバイルデバイスクラスタ１２０は、ネットワーク広告プロトコルとは異なる第３のプロトコルを使用して通信することができ、第３のモバイルデバイスクラスタ１３０は、ネットワーク広告プロトコルとは異なる第４のプロトコルを使用して通信することができる。これに関連して、プロトコルは、それにおいて通信が発生するチャネル、通信のタイミング（たとえば、発見間隔のタイミング）など、通信するために使用されるパラメータを指す。
[0036] さらに例示のために、モバイルデバイス１４２は、オンになり、ワイヤレス通信システム１００に共通のネットワーク広告プロトコルを介して第１の発見メッセージを受信するために、リスニング状態のままであり得る。たとえば、モバイルデバイス１４２は、モバイルデバイス１２２から第１の発見メッセージを受信することができる。第１の発見メッセージは、第２のモバイルデバイスクラスタ１２０に固有の情報を含んでよく、本明細書では「クラスタ発見メッセージ」と呼ばれることがある。たとえば、情報は、第２のモバイルデバイスクラスタ１２０に関連付けられたプロトコルの特性を指示することなどによって、第２のモバイルデバイスクラスタ１２０を指示（たとえば、広告）することができる。情報は、ネットワーク広告プロトコルに関連付けられたワイヤレスチャネルとは異なり得る、第２のモバイルデバイスクラスタ１２０に関連付けられたワイヤレスチャネルの指示を含み得る。代替または追加として、情報は、ネットワーク広告プロトコルに関連付けられたタイミングパラメータとは異なり得る、第２のモバイルデバイスクラスタ１２０に関連付けられたタイミングパラメータ（たとえば、発見間隔の開始時間および／または持続時間）の指示を含み得る。代替または追加として、情報は、（たとえば、ネットワークサイズがしきい値を超えることに基づいて、たとえば、第２のモバイルデバイスクラスタ１２０に関連付けられた推定帯域幅が小さすぎるかどうかに基づいて、モバイルデバイスが、第２のモバイルデバイスクラスタ１２０に加入するかどうかを決定することを可能にするために）第２のモバイルデバイスクラスタ１２０に関連付けられたネットワークサイズを含み得る。代替または追加として、情報は、第２のモバイルデバイスクラスタ１２０に関連付けられた、発見間隔および／または後続のリスニング間隔の持続時間を含み得る。代替または追加として、情報は、第２のモバイルデバイスクラスタ１２０に関連付けられた、ソーシャルネットワーキングモバイルデバイスアプリケーションまたはゲームモバイルデバイスアプリケーションについての情報など、クラスタ識別情報を含み得る。
[0037] 第１の発見メッセージを受信することに応答して、モバイルデバイス１４２は、第２のモバイルデバイスクラスタ１２０に関連付けられたプロトコルを使用して、モバイルデバイス１２２と通信するために、第１の発見メッセージ中の情報を使用することができる。たとえば、モバイルデバイス１４２は、第２のモバイルデバイスクラスタ１２０に加入するか、第２のモバイルデバイスクラスタ１２０に関連付けられた追加の情報（たとえば、モバイルデバイスアプリケーションに関係する情報）について、第２のモバイルデバイスクラスタ１２０のモバイルデバイスにクエリするか、またはその組合せを行うことができる。モバイルデバイス１２２と通信することは、（ネットワーク広告プロトコルに関連付けられた）第１のチャネルから、（第２のモバイルデバイスクラスタに関連付けられた）第２のチャネルへ、モバイルデバイス１４２のトランシーバを同調させることを含み得る。第２のチャネルに同調した後、モバイルデバイス１４２は、第２のモバイルデバイスクラスタ１２０に関連付けられる第２のタイミングパラメータによって決定される時間において、モバイルデバイス１２２から第２の発見メッセージを受信することができる。
[0038] 別の特定の例では、モバイルデバイス１３２は、ワイヤレス通信システム１００に共通のネットワーク広告プロトコルを介して、第２の発見メッセージを送ることができる。第２の発見メッセージは、第３のモバイルデバイスクラスタ１３０に固有の情報を含み得る。１つまたは複数の他のデバイスが、第２の発見メッセージを受信することができる。たとえば、モバイルデバイス１２８は、モバイルデバイス１３２によって送られた第２の発見メッセージを受信することができる。モバイルデバイス１３２は、第３のモバイルデバイスクラスタ１３０に固有の情報に基づいて送られる、モバイルデバイス１２８からのメッセージを受信することができる。メッセージは、第３のモバイルデバイスクラスタ１３０に関連付けられたプロトコルを使用して送られ得る。モバイルデバイス１２８から送られたメッセージは、第３のモバイルデバイスクラスタ１３０に加入するための要求、第３のモバイルデバイスクラスタ１３０に関係する追加の情報についてのクエリ、またはその組合せであり得る。
[0039] 特定の実施形態では、モバイルデバイスクラスタ１１０、１２０および１３０の各々は、ワイヤレス通信システム１００に共通のネットワーク広告プロトコルに関連付けられた発見間隔中に広告され得る。たとえば、ワイヤレス通信システム１００に共通のネットワーク広告プロトコルに関連付けられた第１の発見間隔中に、第１のモバイルデバイスクラスタ１１０の特定のデバイス（モバイルデバイス１１４など）は、第１のモバイルデバイスクラスタ１１０を広告する発見メッセージを送ることができる。追加として、第１の発見間隔中に、第２のモバイルデバイスクラスタ１２０の特定のデバイス（モバイルデバイス１２６など）は、第２のモバイルデバイスクラスタ１２０を広告する発見メッセージを送ることができる。さらに、第１の発見間隔中に、第３のモバイルデバイスクラスタ１３０の特定のデバイス（モバイルデバイス１３６など）は、第３のモバイルデバイスクラスタ１３０を広告する発見メッセージを送ることができる。このようにして、第１の発見間隔中に、モバイルデバイス１４２は、（たとえば、ワイヤレス通信システム１００に共通のネットワーク広告プロトコルに関連付けられたチャネルに同調することによって）ワイヤレス通信システム１００に共通のネットワーク広告プロトコルを介して、モバイルデバイスクラスタの各々に関連付けられた発見メッセージを受信することができる。したがって、モバイルデバイス１４２は、特定のエリアにおいてアクティブであるモバイルデバイスクラスタを識別するために、（モバイルデバイスクラスタ１１０、１２０および１３０の各々に関連付けられたチャネルなど、様々なチャネルをスキャンする必要がない。
[0040] ワイヤレス通信システム１００に共通のネットワーク広告プロトコルを利用することは、モバイルデバイスの特定のクラスタ（たとえば、モバイルデバイスクラスタ１１０、１２０、１３０のいずれか）に関係する情報の送信と受信とを可能にすることができることは諒解されよう。さらに、ネットワーク広告プロトコルとは異なるクラスタ固有のプロトコルに従って通信することによって、モバイルデバイスクラスタ１１０、１２０、１３０の各々は、特定のモバイルデバイスクラスタに関連付けられた１つまたは複数の特定のモバイルデバイスアプリケーションなど、クラスタ固有の特性に従って、通信を適合させることができる。
[0041] 図２は、ワイヤレス通信システム１００内で採用され得るワイヤレスデバイス２０２において利用され得る様々な構成要素を示す。ワイヤレスデバイス２０２は、本明細書で説明される様々な方法を実施するように構成され得るデバイスの一例である。たとえば、ワイヤレスデバイス２０２は、モバイルデバイスのうちの１つを含み得る。
[0042] ワイヤレスデバイス２０２は、ワイヤレスデバイス２０２の動作を制御するプロセッサ２０４を含み得る。プロセッサ２０４は、中央処理ユニット（ＣＰＵ）と呼ばれることもある。読取り専用メモリ（ＲＯＭ）とランダムアクセスメモリ（ＲＡＭ）の両方を含むことができるメモリ２０６は、命令とデータとをプロセッサ２０４に与えることができる。メモリ２０６の一部はまた、不揮発性ランダムアクセスメモリ（ＮＶＲＡＭ）を含み得る。プロセッサ２０４は、通常、メモリ２０６内に記憶されたプログラム命令に基づいて、論理演算と算術演算とを実施する。メモリ２０６中の命令は、本明細書で説明される方法を実施するように実行可能であり得る。
[0043] プロセッサ２０４は、１つまたは複数のプロセッサとともに実装された処理システムを含み得るか、またはその構成要素であり得る。１つまたは複数のプロセッサは、汎用マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プログラマブル論理デバイス（ＰＬＤ）、コントローラ、状態機械、ゲート論理、個別ハードウェア構成要素、専用ハードウェア有限状態機械、または情報の計算もしくは他の操作を実施することができる任意の他の好適なエンティティの任意の組合せを用いて実装され得る。
[0044] 処理システムは、ソフトウェアを記憶するための機械可読媒体をも含み得る。ソフトウェアは、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語などの名称にかかわらず、任意のタイプの命令を意味すると広く解釈されたい。命令は、（たとえば、ソースコード形式、バイナリコード形式、実行コード形式、または他の適切なコード形式の）コードを含むことができる。命令は、１つまたは複数のプロセッサによって実行されたとき、処理システムに本明細書で説明される様々な機能を実施させる。
[0045] ワイヤレスデバイス２０２はまた、ワイヤレスデバイス２０２とリモートロケーションとの間のデータの送信と受信とを可能にするために送信機２１０および／または受信機２１２を含み得る、ハウジング２０８を含み得る。送信機２１０と受信機２１２とは組み合わされてトランシーバ２１４になり得る。アンテナ２１６は、ハウジング２０８に取り付けられ、トランシーバ２１４に電気的に結合され得る。ワイヤレスデバイス２０２はまた、複数の送信機、複数の受信機、複数のトランシーバ、および／または複数のアンテナ（図示せず）を含むことができる。
[0046] 送信機２１０は、異なるパケットタイプまたは機能を有するパケットをワイヤレスに送信するように構成され得る。たとえば、送信機２１０は、プロセッサ２０４によって生成された異なるタイプのパケットを送信するように構成され得る。ワイヤレスデバイス２０２がモバイルデバイスとして実装または使用されるとき、プロセッサ２０４は、複数の異なるパケットタイプのパケットを処理するように構成され得る。たとえば、プロセッサ２０４は、パケットのタイプを決定し、それに応じて、パケットおよび／またはパケットのフィールドを処理するように構成され得る。ワイヤレスデバイス２０２がモバイルデバイスとして実装または使用されるとき、プロセッサ２０４はまた、複数のパケットタイプのうちの１つを選択および生成するように構成され得る。たとえば、特定の事例では、プロセッサ２０４は、（クラスタ発見メッセージおよび／または発見メッセージなどの）発見パケットを生成し、何のタイプのパケット情報を使用するべきかを決定するように構成され得る。
[0047] 受信機２１２は、異なるパケットタイプを有するパケットをワイヤレスに受信するように構成され得る。いくつかの態様では、受信機２１２は、使用されたパケットのタイプを検出し、それに応じて、パケットを処理するように構成され得る。
[0048] ワイヤレスデバイス２０２はまた、トランシーバ２１４によって受信された信号のレベルを検出および定量化するために使用され得る、信号検出器２１８を含み得る。信号検出器２１８は、総エネルギー、シンボルごとのサブキャリア当たりのエネルギー、電力スペクトル密度および他の信号などの信号を検出することができる。ワイヤレスデバイス２０２はまた、信号を処理する際に使用するためのデジタル信号プロセッサ（ＤＳＰ）２２０を含み得る。ＤＳＰ２２０は、送信のためにパケットを生成するように構成され得る。いくつかの態様では、パケットは物理レイヤデータユニット（ＰＰＤＵ）を含み得る。
[0049] ワイヤレスデバイス２０２は、いくつかの態様では、ユーザインターフェース２２２をさらに含み得る。ユーザインターフェース２２２は、キーパッド、マイクロフォン、スピーカー、および／またはディスプレイを含み得る。ユーザインターフェース２２２は、ワイヤレスデバイス２０２のユーザに情報を伝達し、および／またはユーザからの入力を受信する、任意の要素または構成要素を含み得る。
[0050] ワイヤレスデバイス２０２の様々な構成要素は、バスシステム２２６によって互いに結合され得る。バスシステム２２６は、たとえば、データバスを含み得、ならびに、データバスに加えて、電力バスと、制御信号バスと、ステータス信号バスとを含み得る。ワイヤレスデバイス２０２の構成要素は、何らかの他の機構を使用して、互いに結合されるか、または互いに対する入力を受け付けるかもしくは与え得る。
[0051] いくつかの別々の構成要素が図２に示されているが、それらの構成要素のうちの１つまたは複数は、組み合わされるか、または共通に実装されることがある。たとえば、プロセッサ２０４は、プロセッサ２０４に関して上記で説明された機能を実装するためだけでなく、信号検出器２１８および／またはＤＳＰ２２０に関して上記で説明された機能を実装するためにも使用され得る。さらに、図２に示される構成要素の各々は、複数の別々の要素を使用して実装され得る。
[0052] 複数のモバイルデバイス間の適切な通信を可能にするために、モバイルデバイスは、モバイルデバイスの特性に関する情報を受信することができる。たとえば、モバイルデバイス１４２（図１）は、モバイルデバイス１４２とモバイルデバイス１１４（図１）との間の通信のタイミングを同期させるために、モバイルデバイス１１４についてのタイミング情報を受信することができる。代替または追加として、モバイルデバイス１４２は、別のモバイルデバイスの媒体アクセス制御（ＭＡＣ）アドレスなど、他の情報を受信することができる。モバイルデバイス１４２は、メモリ２０６とプロセッサ２０４とを使用して実行されるソフトウェアを通してなど、そのような情報を単独で必要とするかどうかを決定することができる。
[0053] モバイルデバイス１４２（図１）は、複数の動作モードを有し得る。たとえば、モバイルデバイス１４２は、アクティブモード、通常動作モード、または全出力モードと呼ばれる第１の動作モードを有し得る。アクティブモードでは、モバイルデバイス１４２は、常に「アウェイク」状態であってよく、別のモバイルデバイスとデータをアクティブに送信／受信することができる。さらに、モバイルデバイス１４２は、省電力モードまたはスリープモードと呼ばれる第２の動作モードを有し得る。省電力モードでは、モバイルデバイス１４２は、「アウェイク」状態であり得るか、または、モバイルデバイス１４２が別のモバイルデバイスとデータをアクティブに送信／受信しない「ドーズ」もしくは「スリープ」状態であり得る。たとえば、モバイルデバイス１４２の受信機２１２、ならびに、場合によってはＤＳＰ２２０および信号検出器２１８は、ドーズ状態で低減された電力消費を使用して動作することができる。さらに、省電力モードでは、モバイルデバイス１４２は、別のモバイルデバイスとデータを送信／受信することが可能になるように、モバイルデバイスがある時間において「ウェイクアップ」する（たとえば、アウェイク状態に入る）必要があるかどうかをモバイルデバイスに指示する、他のモバイルデバイスからのメッセージ（たとえば、ページングメッセージ）をリッスンするために、時々アウェイク状態に入ることができる。
[0054] 上記で説明されたように、ワイヤレスデバイス２０２は、ＡＰ１０４またはＳＴＡ１０６を備え得、通信を送信および／または受信するために使用され得る。図３は、ワイヤレス通信を送信するためにワイヤレスデバイス２０２において利用され得る送信機モジュール３００を示す。図３に示された構成要素は、たとえば、ＯＦＤＭ通信を送信するために使用され得る。
[0055] 送信機モジュール３００は、送信のためにビットを変調するように構成された変調器３０２を備え得る。たとえば、送信機モジュール３００が図２のワイヤレスデバイス２０２の構成要素として使用される場合、変調器３０２は、たとえばコンスタレーションに従ってビットを複数のシンボルにマッピングすることによって、プロセッサ２０４またはユーザインターフェース２２２から受信されたビットから複数のシンボルを決定し得る。それらのビットは、ユーザデータまたは制御情報に対応し得る。いくつかの態様では、それらのビットはコードワードにおいて受信される。一態様では、変調器３０２は、ＱＡＭ（直交振幅変調）変調器、たとえば、１６ＱＡＭ変調器または６４ＱＡＭ変調器を備える。他の態様では、変調器３０２は、２位相シフトキーイング（ＢＰＳＫ）変調器または４位相シフトキーイング（ＱＰＳＫ）変調器を備える。
[0056] 送信機モジュール３００は、変調器３０２からのシンボルまたはさもなければ変調されたビットを時間領域に変換するように構成された変換モジュール３０４をさらに備え得る。図３では、変換モジュール３０４は、逆高速フーリエ変換（ＩＦＦＴ）モジュールによって実装されるものとして示されている。いくつかの実装形態では、異なるサイズのデータのユニットを変換する複数の変換モジュール（図示せず）が存在する場合がある。
[0057] 図３では、変調器３０２および変換モジュール３０４は、ＤＳＰ３２０中に実装されるものとして示されている。しかしながら、いくつかの態様では、変調器３０２と変換モジュール３０４の一方または両方は、プロセッサ２０４中でなど、ワイヤレスデバイス２０２の他の構成要素中で実装され得る。
[0058] 概して、ＤＳＰ３２０は、送信のためのデータユニットを生成するように構成され得る。いくつかの態様では、変調器３０２および変換モジュール３０４は、制御情報を含む複数のフィールドと複数のデータシンボルとを備えるデータユニットを生成するように構成され得る。制御情報を含むそれらのフィールドは、たとえば、１つまたは複数のトレーニングフィールドと、１つまたは複数の信号（ＳＩＧ）フィールドとを備える場合がある。トレーニングフィールドの各々は、ビットまたはシンボルの既知のシーケンスを含み得る。ＳＩＧフィールドの各々は、データユニットに関する情報、たとえばデータユニットの長さまたはデータレートの記述を含み得る。
[0059] 図３の説明に戻ると、送信機モジュール３００は、変換モジュールの出力をアナログ信号に変換するように構成されたデジタルアナログ変換器３０６をさらに備え得る。たとえば、変換モジュール３０６の時間領域出力は、デジタルアナログ変換器３０６によってベースバンドＯＦＤＭ信号に変換され得る。いくつかの態様では、送信機モジュール３００の一部は、図２からのワイヤレスデバイス２０２中に含まれ得る。たとえば、デジタルアナログ変換器３０６は、プロセッサ２０４、トランシーバ２１４中で、またはワイヤレスデバイス２０２の別の要素中で実装され得る。
[0060] アナログ信号は、送信機３１０によってワイヤレスに送信され得る。アナログ信号は、送信機３１０によって送信される前に、たとえばフィルタ処理されることによって、または中間周波数もしくは搬送周波数にアップコンバートされることによって、さらに処理され得る。図３に示された態様では、送信機３１０は送信増幅器３０８を含む。送信されるより前に、アナログ信号は送信増幅器３０８によって増幅され得る。いくつかの態様では、増幅器３０８は低雑音増幅器（ＬＮＡ）を備える。
[0061] 送信機３１０は、アナログ信号に基づいてワイヤレス信号中で１つまたは複数のパケットまたはデータユニットを送信するように構成される。それらのデータユニットは、プロセッサおよび／またはＤＳＰ３２０を使用して、たとえば上記で説明されたように変調器３０２と変換モジュール３０４とを使用して、生成され得る。上記で説明されたように生成され、送信され得るデータユニットについて、図５〜図７に関して以下でさらに詳細に説明する。
[0062] 図４は、ワイヤレス通信を受信するためにワイヤレスデバイス２０２において利用され得る受信モジュール４００を示す。図４に示された構成要素は、たとえば、ＯＦＤＭ通信を受信するために使用され得る。いくつかの態様では、図４に示された構成要素は、以下でさらに詳細に説明されるように、１つまたは複数のトレーニングフィールドを含むデータユニットを受信するために使用される。たとえば、図４に示された構成要素は、図３に関して上記で説明された構成要素によって送信されたデータユニットを受信するために使用され得る。
[0063] 受信機４１２は、ワイヤレス信号中の１つまたは複数のパケットまたはデータユニットを受信するように構成される。以下で説明されるように受信され、復号され、またはさもなければ処理され得るデータユニットについて、図５〜図７に関してさらに詳細に説明する。
[0064] 図４に示された態様では、受信機４１２は受信増幅器４０１を含む。受信増幅器４０１は、受信機４１２によって受信されたワイヤレス信号を増幅するように構成され得る。いくつかの態様では、受信機４１２は、自動利得制御（ＡＧＣ）手順を使用して、受信増幅器４０１の利得を調整するように構成される。いくつかの態様では、自動利得制御は、たとえば、利得を調整するために、受信されたショートトレーニングフィールド（ＳＴＦ）などの１つまたは複数の受信されたトレーニングフィールド内の情報を使用する。当業者はＡＧＣを実施するための方法を理解されよう。いくつかの態様では、増幅器４０１はＬＮＡを備える。
[0065] 受信モジュール４００は、受信機４１２からの増幅されたワイヤレス信号をそのデジタル表現に変換するように構成されたアナログデジタル変換器４０２を備え得る。増幅されることに加えて、ワイヤレス信号は、デジタルアナログ変換器４０２によって変換される前に、たとえばフィルタ処理されることによって、または中間周波数もしくはベースバンド周波数にダウンコンバートされることによって、処理され得る。いくつかの態様では、アナログデジタル変換器４０２は、図２のプロセッサ２０４、トランシーバ２１４中で、またはワイヤレスデバイス２０２の別の要素中で実装され得る。
[0066] 受信モジュール４００は、表現ワイヤレス信号を周波数スペクトルに変換するように構成された変換モジュール４０４をさらに備え得る。図４では、変換モジュール４０４は、高速フーリエ変換（ＦＦＴ）モジュールによって実装されるものとして示されている。いくつかの態様では、変換モジュールは、それが使用する各点についてシンボルを識別し得る。
[0067] 受信モジュール４００は、データユニットがそれを介して受信されるチャネルの推定値を形成することと、チャネル推定値に基づいてチャネルのいくつかの影響を除去することとを行うように構成された、チャネル推定器および等化器４０５をさらに備え得る。たとえば、チャネル推定器は、チャネルの関数を近似するように構成され得、チャネル等化器は、その関数の逆を周波数スペクトルにおけるデータに適用するように構成され得る。
[0068] いくつかの態様では、チャネル推定器および等化器４０５は、たとえば、チャネルを推定するために、ロングトレーニングフィールド（ＬＴＦ）など、１つまたは複数の受信されたトレーニングフィールド中の情報を使用する。チャネル推定値は、データユニットの始めにおいて受信された１つまたは複数のＬＴＦに基づいて形成され得る。このチャネル推定値は、その後、１つまたは複数のＬＴＦに続くデータシンボルを等化するために使用され得る。一定の時間期間の後または一定数のデータシンボルの後、データユニット内で１つまたは複数の追加のＬＴＦが受信され得る。追加のＬＴＦを使用して、チャネル推定値が更新され得るか、または新しい推定値が形成され得る。この新しいまたは更新チャネル推定値は、追加のＬＴＦに続くデータシンボルを等化するために使用され得る。いくつかの態様では、新しいまたは更新されたチャネル推定値は、追加のＬＴＦに先行するデータシンボルを再等化するために使用される。当業者はチャネル推定値を形成するための方法を理解されよう。
[0069] 受信モジュール４００は、等化されたデータを復調するように構成された復調器４０６をさらに備え得る。たとえば、復調器４０６は、たとえばコンスタレーションにおけるシンボルへのビットのマッピングを逆転させることによって、変換モジュール４０４とチャネル推定器および等化器４０５とによって出力されたシンボルから複数のビットを決定し得る。いくつかの態様では、受信モジュール４００がワイヤレスデバイス２０２の一部分として実装される場合、それらのビットは、プロセッサ２０４によって処理または評価され得るか、あるいはユーザインターフェース２２２に情報を表示するかまたはさもなければ出力するために使用され得る。このようにして、データおよび／または情報が復号され得る。いくつかの態様では、それらのビットはコードワードに対応する。一態様では、復調器４０６は、ＱＡＭ（直交振幅変調）復調器、たとえば１６ＱＡＭ復調器または６４ＱＡＭ復調器を備える。他の態様では、復調器４０６は、２位相シフトキーイング（ＢＰＳＫ）復調器または４位相シフトキーイング（ＱＰＳＫ）復調器を備える。
[0070] 図４では、変換モジュール４０４、チャネル推定器および等化器４０５、ならびに復調器４０６は、ＤＳＰ４２０中に実装されるものとして示されている。しかしながら、いくつかの態様では、変換モジュール４０４、チャネル推定器および等化器４０５、ならびに復調器４０６のうちの１つまたは複数は、プロセッサ２０４中でなど、ワイヤレスデバイス２０２の別の構成要素中で実装され得る。
[0071] 上記で説明されたように、受信機４１２において受信されたワイヤレス信号は、１つまたは複数のデータユニットを備える。これらのデータユニットは、上記で説明された構成要素を使用して、復号、評価および／または処理され得る。たとえば、プロセッサおよび／またはＤＳＰ４２０は、変換モジュール４０４と、チャネル推定器および等化器４０５と、復調器４０６とを使用して、データユニット中のデータシンボルを復号するために使用され得る。
[0072] ＡＰ１０４とＳＴＡ１０６とによって交換されるデータユニットは、制御情報またはデータを含み得る。物理（ＰＨＹ）レイヤにおいて、これらのデータユニットは、物理レイヤプロトコルデータユニット（ＰＰＤＵ）と呼ばれる場合がある。いくつかの態様では、ＰＰＤＵはパケットまたは物理レイヤパケットと呼ばれることがある。各ＰＰＤＵはプリアンブルとペイロードとを備え得る。プリアンブルはトレーニングフィールドとＳＩＧフィールドとを含み得る。たとえば、トレーニングフィールドは、１つまたは複数のロングトレーニングフィールド（ＬＴＦ）と１つまたは複数のショートトレーニングフィールド（ＳＴＦ）とを含み得る。ペイロードは、メディアアクセス制御（ＭＡＣ）ヘッダおよび／またはユーザデータを備え得る。ペイロードは、ＢＰＳＫシンボルまたはＱＰＳＫシンボルなど、１つまたは複数のデータシンボルを使用して送信され得る。
[0073] モバイルデバイスクラスタ（１１０、１２０、および１３０）など、ソーシャルＷｉＦｉネットワークにおいて、スケーラブルな動作を可能にするために、ネットワークにおける各デバイスによる送信は、ネットワークにおけるデバイスの数に基づいて制御されるべきである。たとえば、ネットワークにおけるデバイスの数に基づいて、ビーコンおよび／またはタイミング信号が送信される際のレートを調整することが、望ましいことがある。多数の適用例では、ネットワークにおけるデバイスの数の概算推定値を取得することは、十分である。ワイヤレスデバイスがネットワークにおけるデバイスの数を追跡するための１つの方法は、メッセージにおいて受信され、デバイスを表す、任意の識別子を単に記憶することである。新しいメッセージが受信されるときは常に、デバイスは、新しいメッセージ中の識別子を、デバイスにおいてすでに記憶されている識別子と比較し、その識別子が前に記憶されていない場合、その識別子を記憶することになる。ただし、この手法は、大きいメモリ要件と、より多数の受信された識別子をソートする必要性とにつながり得る。したがって、より大きいメモリ要件と、識別子をソートする必要性とを大きく低減することができる、ワイヤレスネットワークにおけるデバイスの数を追跡する方法を有することが、有益である。
[0074] 以下で説明されるような実装形態では、ブルームフィルタ（以下でさらに詳細に説明される）が、ネットワークにおけるデバイスの識別子を追跡するために使用される。ブルームフィルタは、ｋ個のハッシュ関数がそれに関連付けられた、ｍビットのビットアレイである。別のワイヤレスデバイスに関連付けられた識別子を含むメッセージが、別のワイヤレスデバイスから受信されるときは常に、その識別子がブルームフィルタに追加される。ブルームフィルタにおける０の密度が、ブルームフィルタにおいてデバイスの数を推定するために使用される。いくつかの態様では、１の密度が、ブルームフィルタにおいてデバイスの数を推定するために使用され得る。ブルームフィルタは、あらかじめ定義されたビット数を含み、各ビットは、０または１のいずれかに設定され得るので、０の数が知られると、ブルームフィルタにおける１の数を決定することは、数学的に単純であり、その逆も同様であり得る。したがって、ネットワークにおけるデバイスの数を決定するために、ブルームフィルタにおける０の数または１の数のいずれかが使用され得る。
[0075] 図５は、一実装形態による、ワイヤレスネットワークにおけるワイヤレスデバイスの数を監視する方法のフローチャートである。方法５００は、（図１に示された）モバイルデバイス１１２などのワイヤレスデバイスによって実施され得る。一実装形態では、ワイヤレスネットワークは、ソーシャルＷｉＦｉネットワークまたはアドホックネットワークである。ワイヤレスネットワークは、（図１に示された）モバイルデバイスクラスタ１１２０、１２０および１３０であり得る。ただし、方法はまた、インフラストラクチャタイプのワイヤレスネットワーク（たとえば、アクセスポイントを含むネットワーク）において使用されてもよく、ここにおいて、ワイヤレスデバイスは、それらの周囲の他のデバイスの数に基づいて、それらの挙動を緩和し得る。
[0076] ブロック５０２で、方法は、ワイヤレスデバイスからメッセージを受信することを含み、メッセージは、ワイヤレスデバイスに関連付けられた識別子を備える。メッセージは、たとえば、ワイヤレスネットワークにおける別のワイヤレスデバイス（「近隣ワイヤレスデバイス」とも呼ばれる）から、（図２に示された）ワイヤレスデバイス２０２の受信機２１２によって受信され得る。「近隣ワイヤレスデバイス」という用語は、単に、同じワイヤレスネットワークにおける別のワイヤレスデバイスを指す。メッセージは、別のワイヤレスデバイスからの任意のパケットまたはフレームであり得る。例示的な実装形態では、メッセージは、近隣ワイヤレスデバイスに関連付けられた識別子を含む。
[0077] ブロック５０４へ進むと、方法は、ブルームフィルタに識別子を追加（または入力）することを含む。このプロセスは、たとえば、（図２に示された）ワイヤレスデバイス２０２のプロセッサ２０４によって実施され得る。一実装形態では、メッセージが別のワイヤレスデバイスから受信されるときは常に、識別子がブルームフィルタに追加される。
[0078] ブルームフィルタは、空間効率の良い確率的データ構造である。ブルームフィルタは、ｍビットのビットアレイと、ｋ個の異なるハッシュ関数とを含む。各ビットは、０または１の値を有し得る。ｋ個の異なるハッシュ関数の各々は、一様なランダム分布をもつｍ個のアレイ位置のうちの１つに、入力文字列をマッピングする。例示的な実装形態では、ｍビットはすべて０に初期化される。識別子が受信されるときは常に、識別子がブルームフィルタに追加される。ブルームフィルタに識別子を追加するプロセスは、ａ）ｋ個のハッシュ関数の各々に入力文字列として識別子を供給することと、ここにおいて、各ハッシュ関数は、１つのアレイ位置に入力文字列をマッピングする、ｂ）ｋ個のハッシュ関数によって識別されたアレイ位置におけるビットを、１に設定することとを含む。
[0079] 次にブロック５０６で、方法は、ブルームフィルタにおける０の数に基づいて、ブルームフィルタに追加された別個の文字列の数を推定することを含み、ここにおいて、別個の文字列の数は、ワイヤレスネットワークにおけるワイヤレスデバイスの数の推定値を表す。このプロセスは、たとえば、（図２に示された）ワイヤレスデバイス２０２のプロセッサ２０４によって実施され得る。一実装形態では、別個の文字列の数が、ブルームフィルタにおける１の密度（または、ブルームフィルタにおける０の密度）に基づいて決定される。別個の入力の推定数、別個の文字列の数N distinct。ブルームフィルタに追加されたN distinctは、たとえば、次の公式によって計算され得る。
Figure 0006026675
ただし、N 0は、ブルームフィルタのｍビットアレイにおける０の数を示す。したがって、方法は、個々の識別子を追跡または記憶する必要なしに、ワイヤレスネットワークにおけるデバイスの数を監視することを可能にする。結果として、方法は、少ない記憶空間のみを必要とする。１つの代替移植では、公式（１）は、次のように簡略化され得る。
Figure 0006026675
公式（１ａ）は、特にｍが十分に大きいとき、ｌｏｇ（１−１／ｍ）が１／ｍにほぼ等しいという事実を活用する。
[0080] 一実装形態では、方法は、任意のプロセスをさらに含んでよく、ここにおいて、第１のワイヤレスデバイスがワイヤレスネットワークに加入するとき、そのワイヤレスデバイスは、第２のワイヤレスデバイスに、第２のデバイスの現在のブルームフィルタを提供するように要求する。これは、第１のデバイスがワイヤレスネットワークにおけるデバイスの数の傾向を得ることを助ける。この時点から、第１のデバイスは、第２のデバイスから受信されたブルームフィルタを更新することによって、いかなる追加のデバイスをもカウントすることができる。一実装形態では、第２のワイヤレスデバイスは、第１のデバイスのネイバーのうちの１つであり得る。別の実装形態では、第１のワイヤレスデバイスは、複数の近隣ワイヤレスデバイスに、それらの現在のブルームフィルタを提供するように要求し得る。第１のワイヤレスデバイスが、２つ以上のワイヤレスデバイスからブルームフィルタを受信する場合、第１のワイヤレスデバイスは、受信されたブルームフィルタのビットＯＲ演算を実施し、得られたブルームフィルタを、第１のワイヤレスデバイスのための現在のブルームフィルタとして記憶し得る。一実装形態では、ワイヤレスデバイスは、１つの近隣ワイヤレスデバイスからメッセージを受信してよく、メッセージは、近隣ワイヤレスデバイスのブルームフィルタと、近隣ワイヤレスデバイスのブルームフィルタが開始された時間とを含む。これは、ブルームフィルタを受信するワイヤレスデバイスが、受信されたブルームフィルタが古すぎるかどうかと、受信されたブルームフィルタが満了することを可能にするかどうかとを、知ることを可能にする。
[0081] いくつかの適用例では、この方法によって行われる推定の精度は、いくつかのワイヤレスデバイスがネットワークを離れていくことを明示的に指示することなく離脱することによって損なわれ得る。追加として、この方法の精度はまた、いくつかのワイヤレスデバイスがセキュリティの理由のためにそれらのＭＡＣアドレスを連続して変更することによっても損なわれる。これらの要因の影響に対処するための様々な方法がある。たとえば、方法は、ワイヤレスデバイスがランダムな時間の間隔において、ブルームフィルタのランダムに選択されたビットをリセットすることを可能にする、任意のプロセスをさらに含み得る。リセットされるべきビット数、およびランダムな間隔の分布は、次の、ネットワークにおけるワイヤレスデバイスの数、ワイヤレスデバイスがネットワークを離れるレート（外部ソースから来ることがある）、および、ワイヤレスデバイスがそれらのアドレスを変更する間隔のうちの１つまたは複数に基づいて、決定され得る。一実装形態では、ブルームフィルタの選択されたビットをリセットするこのプロセスはまた、発見メッセージが、ネットワークにおけるデバイスの数をカウントする際にブルームフィルタによって完全に無視されるとは限らないことを保証するために、発見メッセージを時々送ることを、ワイヤレスデバイスに要求する。ワイヤレスデバイスがそのような発見メッセージを送る頻度は、ブルームフィルタの選択されたビットをリセットするためのそのようなプロセスのパラメータによって決定される。
[0082] 代替として、方法は、ブルームフィルタにおけるｍビットアレイのビットごとにカウンタを割り当て得る。ｍビットアレイのためのｍ個のカウンタがあってよく、各カウンタは、ｍビットアレイの異なるビットに割り当てられる。カウンタは、０と最大値Ｃ＿ｍａｘとの間の整数値に設定され得る。たとえば、カウンタが３ビットを有する場合、Ｃ＿ｍａｘは、７の値を有し得る。ブルームフィルタにおけるｍビットアレイのビットが１に設定されるたびに、そのビットに関連付けられたカウンタが、Ｃ＿ｍａｘの値にリセットされる。非０値を有する各カウンタの値は、持続時間Ｔの時間間隔ごとに１だけ低減される。たとえば、持続時間Ｔは、適用例に応じて、１００マイクロ秒または１分であり得る。一実装形態では、持続時間Ｔは、次の、ワイヤレスデバイスがネットワークを離れるレート（外部ソースから来ることがある）、および、ワイヤレスデバイスがそれらのアドレスを変更する間隔のうちの１つまたは複数に基づいて、決定され得る。カウンタの値が０に低減されるとき、そのカウンタに対応するビットが０に設定される。上記で説明されたように、ネットワークのサイズは、０に設定されるかまたは１に設定される、ブルームフィルタにおけるビットに基づいて、推定され得る。
[0083] 一実装形態では、方法は、任意のプロセスをさらに含んでよく、ここにおいて、ワイヤレスデバイスは、握りこぶし近隣ワイヤレスデバイスにブルームフィルタのコピーを要求する。ワイヤレスデバイスは、次いで、ワイヤレスデバイスのブルームフィルタと、第１の近隣ワイヤレスデバイスのブルームフィルタとのビットＡＮＤを実施することによって、第１のブルームフィルタを生成する。ワイヤレスは、次いで、第１のブルームフィルタに基づいて、ワイヤレスデバイスおよび第１の近隣ワイヤレスデバイスが共有する、近隣ワイヤレスデバイスの数を推定する。第１のブルームフィルタにおける１の密度はまた、ネイバーのセットの交差におけるデバイスの数の良い推定値でもある。
[0084] 上記で説明されたように、ブルームフィルタは、ｋ個の異なるハッシュ関数を含み、その各々は、ビットアレイ中のビット位置に入力文字列をマッピングする。ハッシュ関数は、たとえば、入力文字列の巡回冗長検査（ＣＲＣ）であり得る。一実装形態では、ｋ個の異なるハッシュ関数は、単一のハッシュ関数（たとえば、ＣＲＣ）とｋ個の異なる文字列（「修正文字列（modification string）」と呼ばれる）とを使用して作成され得る。ブルームフィルタへの入力文字列（「ブルーム入力文字列」と呼ばれる）ごとに、ｋ個の異なる入力文字列（「ハッシュ入力文字列」と呼ばれる）が生成され、ここにおいて、各ハッシュ入力文字列は、ｋ個の修正文字列のうちの異なる１つとともにブルーム入力文字列を付加することによって作成される。その後、ｋ個の異なるハッシュ入力文字列の各々が、単一のハッシュ関数に供給され、したがって、ビットアレイ中にビット位置が生成される。ｋ個の異なるハッシュ入力文字列があるので、ビットアレイ中のｋ個のビット位置が識別される（そのうちのいくつかは、同じピット位置であり得る）。結果として、ブルームフィルタは、単一のハッシュ関数とｋ個の異なる文字列とを使用して、ｋ個の異なるハッシュ関数をシミュレートする。
[0085] 別の実装形態では、ｋ個のハッシュ入力文字列は、異なる方法で作成され得る。一例では、各ハッシュ入力文字列は、修正文字列のうちの異なる１つをブルーム入力文字列に付加することによって作成され得る。別の例では、各ハッシュ入力ハッシュ入力文字列は、修正文字列のうちの異なる１つをブルーム入力文字列の中間に挿入することによって作成され得る。
[0086] 上記で説明されたように、ブルームフィルタは、ｍビットのビットアレイと、ｋ個の異なるハッシュ関数とを含む。一実装形態では、ハッシュ関数の数ｋは、１の値を有し、ビットアレイのサイズｍは、推定されるべきワイヤレスネットワークの最大サイズの約２倍である値を有する。いくつかの適用例では、この単純なブルームフィルタは、ネイバーの数を推定する問題のために十分である。別の実装形態では、ブルームフィルタは、最大Ｎ個のデバイスを追跡するように設計され、ブルームフィルタのビットアレイｍは、Ｎビットを有するように設計される。別の実装形態では、ブルームフィルタのサイズ（パラメータｍおよびｋの値）は、次の公式を使用して、ブルームフィルタに記憶されるべき別個の識別子の所望の数（ｎによって示される）と、フィルタに追加されていない識別子がブルームフィルタ中にあると決定される、所望の誤警報確率（ｐによって示される）とに基づいて、決定され得る。
Figure 0006026675
Figure 0006026675
[0087] 一実装形態では、メッセージ中の識別子は、近隣ワイヤレスデバイス、またはサービスもしくはアプリケーションに関連付けられ得る。メッセージ中の識別子は、フレームを送るワイヤレスデバイスを識別する発見フレームのＭＡＣアドレスであり得る。識別子はまた、フレーム中のサービス識別子であってもよく、ここにおいて、サービス識別子は、フレームの本体中にあってよく、または、フレーム中のアドレスフィールドのうちの１つに取って代わってよい。別の例として、識別子は、特定のアプリケーションに基づき、フレームの本体に位置する、識別子であり得る。したがって、方法は、ワイヤレスデバイスが受信する別個の識別子の数を推定するために、ブルームフィルタを使用する。
[0088] 図６は、一実装形態による、ブルームフィルタの１つの例示的な例を示す。ブルームフィルタは、すべてが０に初期化されたｍビットのビットアレイ（６００）と、ｋ個の異なるハッシュ関数（図示せず）とを含み、ここにおいて、ｍ＝１８、およびｋ＝３である。ｋ個の異なるハッシュ関数の各々は、一様なランダム分布をもつｍ個のアレイ位置のうちの１つに、入力文字列をマッピングまたはハッシングする。３つの入力文字列、すなわち、ｘ、ｙ、およびｚが、ブルームフィルタに追加されている。入力文字列ｘに対して、ブルームフィルタは、図６においてｘで始まる３本の矢印によって示されるように、（図示されないｋ個のハッシュ関数を使用して）入力文字列ｘをビットアレイ中の３つの異なるビット位置にマッピングする。結果として、入力文字列「ｘ」に対応する３つのビット位置は、すべて１の値を有する。同様に、入力文字列ｙおよびｚは、これらの文字列の各々をビットアレイ中の３つの異なるビット位置にマッピングし、これらのビット位置を１の値に設定することによって、ブルームフィルタに追加される。ブルームフィルタの得られたビットアレイが、図６に示されている。入力文字列ｗがブルームフィルタに追加されたかどうかを決定するために、ブルームフィルタは、ｗで始まる３本の矢印によって示されるように、入力文字列ｗをビットアレイ中の３つのビット位置にマッピングする。入力文字列ｗに対応するビット位置のうちの１つが０の値を有するので、入力文字列ｗはブルームフィルタ中にないと決定される。この決定は、ブルームフィルタがｘ、ｙ、およびｚのみを記憶し、ｗを記憶していないので、正しい。
[0089] 図７は、ネットワークにおけるワイヤレスデバイスの数と、ブルームフィルタからの推定された数とを比較する、シミュレーション結果７００を示す。図８は、推定誤り率対ネットワークにおけるワイヤレスデバイスの数を示す、シミュレーション結果８００を示す。シミュレーションでは、ブルームフィルタは、６００バイトのビットアレイと、４個のハッシュ関数とを有する。図７および図８に示されるように、シミュレーション結果は、５０個を超えるデバイスを含むワイヤレスネットワークでは、推定誤りがデバイスの実際の数の約２％以内であることを示している。
[0090] 上記の実装形態のいくつかでは、ブルームフィルタは、ｋ個の異なるハッシュ関数（「ブルームハッシュ関数」と呼ばれる）を含み、その各々は、ｍビットのビットアレイ中のビット位置に入力文字列をマッピングする。ブルームハッシュ関数は、０とｐ−１との間の単一の整数に入力文字列をマッピングするハッシュ関数（「一般ハッシュ関数（general hash function）」と呼ばれる）を使用して実現されてよく、ここにおいて、ｐはｍと同様である。ブルームハッシュ関数は、０とｐ−１との間の単一の整数に入力文字列をマッピングするために、一般ハッシュ関数を最初に使用し、次いで、単一の整数をｍで除算した余りを発見するために、モジュロ演算を適用することによって実現されてよく、ここにおいて、余りは、ｍビットのビットアレイ中のビット位置に対応する。余りは、ブルームハッシュ関数によって返される値である。したがって、ブルームハッシュ関数は、次のように表され得る。
Figure 0006026675
[0091] 一実装形態では、一般ハッシュ関数は、たとえば、入力文字列の巡回冗長検査（ＣＲＣ）であり得る。一実装形態では、ブルームフィルタの一般ハッシュ関数は、入力文字列から複数のビットを選択し、パターンに従って、シーケンスにおいてそれらのビットを配列する関数であり得る。ビットのシーケンスの値は、したがって、一般ハッシュ関数の出力整数を表す。入力文字列から選択されたビットは、必ずしも入力文字列内で連続的であるとは限らない。一般ハッシュ関数は、あらかじめ定義されたパターンに基づいて、ビットシーケンスを生成し得る。たとえば、あらかじめ定義されたパターンは、最初のビット、最後のビット、中央のビット、開始からあらかじめ定義されたオフセットにおけるビット、または、終了からあらかじめ定義されたオフセットにおけるビットから開始する、入力文字列のＢビットのシーケンスを定義し得る。あらかじめ定義されたパターンは、識別子文字列の奇数位置におけるＢビットのシーケンス、または、識別子文字列の偶数位置におけるＢビットのシーケンスを定義してよく、ここにおいて、シーケンスは、最初のビット、最後のビット、中央のビット、開始からあらかじめ定義されたオフセットにおけるビット、または、終了からあらかじめ定義されたオフセットにおけるビットから開始する。別の例では、あらかじめ定義されたパターンは、入力文字列からのビット１と、ビット３７と、ビット８と、ビット９と、ビット１５と、ビット３と、ビット２とを含む、ビットのシーケンスを定義し得る。
[0092] 上記の実装形態のうちのいくつかでは、ワイヤレスデバイスは、ワイヤレスネットワークに加入すると、第２のワイヤレスデバイスに、第２のデバイスの現在のブルームフィルタを提供するように要求する。一実装形態では、ブルームフィルタは、指定された管理サービス識別情報（たとえば、管理動作のために予約された０ｘ００００００または０ｘＦＦＦＦＦＦ）とともに、発見タイプ長さ値（ＴＬＶ）を使用して交換され得る。ブルームフィルタは、管理固有情報コンテナ（Management Specific Information Container）と呼ばれる発見ＴＬＶの任意のフィールドに記憶され得る。
[0093] 発見ＴＬＶは、ベンダー固有発見フレーム中で搬送され得る。代替として、ＴＬＶは、（たとえば、ＷｉＦｉダイレクトシステムにおいて）ピアツーピア（Ｐ２Ｐ）情報要素中の属性として搬送され得る。情報要素は、ベンダー固有情報要素であり得る。一実装形態では、ブルームフィルタを交換するためのプロトコルは、新しいワイヤレス局がネイバーフッドアウェアネットワーク（ＮＡＮ）同期ビーコンまたは発見フレームについてスキャンするとき、開始する。同期ビーコンまたは発見フレームが受信されると、新しい局は、同期ビーコンまたは発見フレームの送信側に、ブルームフィルタを求める要求を送る。要求は、管理発見ＴＬＶを使用して行われる。同期ビーコンまたは発見フレームの送信側は、次いで、管理発見ＴＬＶにおいてブルームフィルタで応答する。
[0094] 図９は、例示的なベンダー固有発見フレーム９００を示す。示された実装形態では、ベンダー固有発見フレーム９００は、カテゴリーフィールド９１０と、アクションフィールド９２０と、組織固有識別子（ＯＵＩ）フィールド９３０と、ＯＵＩタイプフィールド９４０と、ＯＵＩサブタイプ９５０と、ダイアログトークン９６０と、１つまたは複数の発見タイプ長さ値（ＴＬＶ）フィールド９７０〜９８０とを含む。示されたように、カテゴリーフィールド９１０は１オクテットであり、アクションフィールド９２０は１オクテットであり、ＯＵＩフィールド９３０は３オクテットであり、ＯＵＩタイプフィールド９４０は１オクテットであり、ＯＵＩサブタイプ９５０は１オクテットであり、ダイアログトークン９６０は１オクテットであり、１つまたは複数の発見ＴＬＶフィールド９７０〜９８０は可変長である。様々な実装形態では、ベンダー固有発見フレーム９００は、図９に示された１つまたは複数のフィールドを省略することができる。ベンダー固有発見フレーム９００中のフィールドは、異なる適切な長さであり得、異なる順序であり得ることを、当業者は諒解されよう。
[0095] いくつかの実装形態では、カテゴリーフィールド９１０は、パブリックアクションフレームを指示することができる。アクションフィールド９２０は、ベンダー固有アクションフレームを指示することができる。ＯＵＩフィールド９３０は、ベンダー、メーカー、または他の組織（「譲受人」と呼ばれる）をグローバルまたは世界的に一意に識別するために使用され得るものであり、譲受人の独占的使用のための各可能なタイプの派生識別子（ＭＡＣアドレス、グループアドレス、サブネットワークアクセスプロトコル識別子など）のブロックを有効に予約することができる。ＯＵＩタイプフィールド９４０は、ＭＡＣ識別子、コンテキスト依存識別子（ＣＤＩ）、拡張一意識別子（ＥＵＩ）など、ＯＵＩフィールド９３０のタイプを指示するために使用され得る。ＯＵＩサブタイプフィールド９５０は、ＯＵＩタイプフィールド９４０のサブタイプを指示することができる。ダイアログトークン９６０は、特定のトランザクションを指示するために選ばれ得る。ＴＬＶフィールド９７０および９８０について、図１０に関して本明細書でより詳細に説明する。
[0096] 図１０は、図１のワイヤレス通信システム１００内で採用され得る発見タイプ長さ値（ＴＬＶ）１０００を示す。発見ＴＬＶ１０００は、発見フレームおよびＰ２Ｐ情報要素など、様々なメッセージ中で送信され得る。ＴＬＶ１０００は、（図９に示された）ＴＬＶ９７０および９８０として、発見フレーム９００中で実装され得る。様々な実装形態では、本明細書で説明されるいかなるデバイス（たとえば、図１に示されたモバイルデバイス１１２などのワイヤレスデバイス）も、発見ＴＬＶ１０００を送信することができる。
[0097] 示された実装形態では、発見ＴＬＶ１０００は、サービス識別子１０１０と、長さフィールド１０２０と、任意のサービス制御フィールド１０３０と、任意の範囲制御フィールド１０５０と、管理制御フィールド１０６０と、任意の管理固有情報コンテナ１０７０とを含む。発見ＴＬＶ１０００は、追加のフィールドを含んでよく、フィールドは並べ替えられ、除去され、および／またはサイズ変更され得ることが当業者には諒解されよう。たとえば、様々な実装形態では、発見ＴＬＶ１０００は、サービス制御フィールド１０３０、範囲制御フィールド１０５０、および／または管理制御１０６０を省略することができる。
[0098] 例示的な実装形態では、示されたサービス識別子フィールド１０１０は、６オクテット長である。いくつかの実装形態では、サービス識別子フィールド１０１０は、信号ごとにおよび／またはサービスプロバイダ間で長さが変化するなど、可変長であり得る。サービス識別子フィールド１０１０は、発見フレームのサービスまたはアプリケーションを識別する値を含み得る。たとえば、サービス識別子１０１０は、サービスに基づく、サービス名または他の値のハッシュを含み得る。いくつかの実装形態では、あらかじめ決定されたトークン値が予約され得る。たとえば、すべて０またはすべて１のサービス識別子は、ＮＡＮ管理動作を指示することができる。
[0099] 長さフィールド１０２０は、発見ＴＬＶ１０００の長さ、または後続のフィールドの全長を指示するために使用され得る。図１０に示された長さフィールド１０２０は、１オクテット長である。いくつかの実装形態では、長さフィールド１０２０は、信号ごとにおよび／またはサービスプロバイダ間で長さが変化するなど、可変長であり得る。いくつかの実装形態では、０（または、別のあらかじめ決定されたトークン値）の長さは、１つまたは複数の他のフィールド（サービス制御フィールド１０３０、範囲制御フィールド１０５０、管理制御１０６０、および／または管理固有情報コンテナ１０７０など）が存在しないことを指示することができる。
[0100] サービス制御フィールド１０３０は、適用可能なサービスの情報を含み得る。図１０に示されたサービス制御フィールド１０３０は、１オクテット長である。いくつかの実装形態では、サービス制御フィールド１０３０は、信号ごとにおよび／またはサービスプロバイダ間で長さが変化するなど、可変長であり得る。
[0101] 範囲制御フィールド１０５０は、管理制御１０６０に関係する情報を含み得る。図１０に示された範囲制御フィールド１０５０は、１オクテット長である。いくつかの実装形態では、範囲制御フィールド１０５０は、信号ごとにおよび／またはサービスプロバイダ間で長さが変化するなど、可変長であり得る。
[0102] 管理制御フィールド１０６０は、管理制御に関係する情報を搬送するために使用され得る。例示的な実装形態では、管理制御フィールド１０６０は、１または２オクテット長であり得る。いくつかの実装形態では、管理制御フィールド１０６０は、可変長を有する。
[0103] 管理固有情報コンテナ１０７０は、関係する追加の情報を搬送するために使用され得る。図１０に示された管理固有情報コンテナ１０７０は、可変長である。例示的な実装形態では、管理固有情報コンテナ１０７０は、ブルームフィルタを含有するために使用され得る。
[0104] いくつかの実施形態では、ピアツーピアネットワークの１つまたは複数のノードは、ピアツーピアネットワークのノード間の通信のために１つまたは複数の可用性ウィンドウを調整するために、同期メッセージを送信することができる。ノードはまた、同じピアツーピアまたはネイバーフッドアウェアネットワーク内で動作するデバイス間のサービス発見を提供するために、発見クエリと応答とを交換することもできる。ネイバーフッドアウェアネットワークは、いくつかの態様では、ピアツーピアネットワークまたはアドホックネットワークと見なされ得る。ノードは、同期メッセージと発見メッセージとを周期的に送信および／または受信するために、スリープ状態から繰返しウェイクする。ノードが、電力を節約するためにスリープ状態により長くとどまり、ネットワーク上で同期メッセージを送信および／または受信するために、スリープ状態からウェイクしないことができた場合、有利となる。追加として、ノードによる同期メッセージと発見メッセージとの送信および再送信は、ネットワークに大量の不必要なオーバーヘッドを導入し得る。
[0105] いくつかの実施形態では、たとえば、ネットワーク輻輳を低減するために、ノードのサブセットのみが、同期メッセージを送信するように構成され得る。いくつかの実施形態では、ノードのサブセットは、指定または選定された「マスター」ノードであり得る。たとえば、外部電源へのアクセスを有するノードが、マスターノードとして選定され得るのに対して、バッテリー電力で実行するノードは、選定されなくてよい。様々な実施形態では、ノードは、発見マスターノード、同期マスターノード、および／またはアンカーマスターノードを含む、１つまたは複数の異なるタイプのマスターノードとして指定され得る。いくつかの実施形態では、１つまたは複数の発見マスターノードは、ＮＡＮ発見メッセージを送信することができるが、一方他のノードは送信しなくてよい。いくつかの実施形態では、１つまたは複数の同期マスターノードは、同期メッセージを送信することができるが、一方他のノードは送信しなくてよい。
[0106] いくつかの実施形態では、１つまたは複数のアンカーマスターノードは、同期マスターノードおよび／または発見マスターノードとして優先的に選定され得る。アンカーノードは、プリセットされ、マスターノード選定に関して本明細書で説明されるように選定され、または、別の方法で決定され得る。アンカーノードを有するＮＡＮは、アンカー付き（anchored）ＮＡＮと呼ばれることがあり、アンカーノードを有していないＮＡＮは、非アンカー付き（non-anchored）ＮＡＮと呼ばれることがある。一実施形態では、ＮＡＮは、単一のアンカーマスターノードを有し得る。
[0107] いくつかの実施形態では、ＮＡＮにおける１つまたは複数のノードは、動的に決定された、またはプリセットされたマスター優先値（ＭＰＶ）に基づいて、１つまたは複数のマスターノードを選定することができる。たとえば、外部電源へのアクセスをもつノードは、それらのＭＰＶをより高く（たとえば、１０に）設定することができるのに対して、バッテリー電力上のノードは、それらのＭＰＶをより低く（たとえば、５に）設定することができる。選定プロセス中に、より高いＭＰＶを有するノードは、選定されたマスターノードになる可能性がより高くなり得る。いくつかの実施形態では、アンカーノードは、非アンカーノードよりも高いＭＰＶを有することができ、したがって、マスターノードとして選定される可能性がより高くなり得る。
[0108] 図１１は、本開示の態様が採用され得る別のワイヤレス通信システム１１００の一例を示す。ワイヤレス通信システム１１００は、アンカーノード１１１０と、マスターノード１１２０と、非マスターノード１１３０とを含む。様々な実施形態では、ワイヤレス通信システム１１００は、ワイヤレス通信システム１００（図１）と同様であり得る。たとえば、１つまたは複数のノード１１１０〜１１３０は、モバイルデバイス１１２〜１１８、１２２〜１２８、および１３２〜１４２（図１）のいずれかを含み得る。いくつかの実施形態では、１つまたは複数のノード１１１０〜１１３０は、ワイヤレスデバイス２０２（図２）を含んでよく、方法５００（図５）を実施することができる。いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、図１に関して上記で説明されたクラスタ１１０、１２０、および１３０など、特定のクラスタと対応し得る。
[0109] いくつかの実施形態では、各マスターノード１１２０は、無線範囲内の他のノードの識別子を追跡することができる。たとえば、各マスターノード１１２０は、図５〜図６に関して上記で説明されたように、範囲内の他のノードの識別子でブルームフィルタをポピュレートすることができる。したがって、いくつかの実施形態では、各マスターノード１１２０は、その関連付けられたクラスタ内のデバイスから受信されたすべてのＮＡＮフレームの送信アドレスをハッシングすることによって、そのブルームフィルタをポピュレートすることができる。いくつかの実施形態では、各マスターノード１１２０は、そのクラスタ内のデバイスのみのための識別子を追跡することができる。いくつかの実施形態では、各マスターノード１１２０は、クラスタにかかわらず、任意の発見されたデバイスのための識別子を追跡することができる。いくつかの実施形態では、マスターノード１１２０は、他のマスターノード１１２０および／またはアンカーノード１１１０の識別子を追跡することを控えることができる。他の実施形態では、マスターノード１１２０は、他のマスターノードおよび／またはアンカーノード１１１０のものを含む、識別子を追跡することができる。様々な実施形態では、アンカーノード１１１０は、マスターノード１１２０に関して本明細書で説明されるように、識別子を追跡することができる。
[0110] 様々な実施形態では、マスターノード１１２０は、アンカーノード１１１０においてルートをもつツリートポロジーを形成することができる。各マスターノード１１２０は、アンカーノード１１１０までのホップ距離を指示する情報を維持することができる。いくつかの実施形態では、アンカーノード１１１０およびマスターノード１１２０は、ツリートポロジーに従って、クラスタサイズを推定および伝搬することができる。本明細書で説明されるように、各マスターノード１１２０および／またはアンカーノード１１１０は、他のノードからブルームフィルタを受信することができる。各マスターノード１１２０および／またはアンカーノード１１１０は、受信されたブルームフィルタと、第１のワイヤレスデバイスのための現在またはローカルのブルームフィルタとのビットＯＲ演算を実施することができる。いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、ブルームフィルタを要求することができる。いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、要求なしにブルームフィルタを受信することができる。
[0111] いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、ツリートポグラフィにおいて隣接したマスターノード１１２０からのみ、ブルームフィルタを受信することができる。いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、ツリートポグラフィにおいて子ノードからのみ、ブルームフィルタを受信することができる。いくつかの実施形態では、各マスターノード１１２０は、親ノードへマージされたブルームフィルタを送る前に、受信されたブルームフィルタとローカルブルームフィルタとの間のビットＯＲ演算を実施することができる。したがって、いくつかの実施形態では、アンカーノード１１１０は、ワイヤレス通信システム１１００におけるすべてのブルームフィルタのビットＯＲを含有するブルームフィルタを、最終的に構築することができる。いくつかの実施形態では、アンカーノード１１１０は、ワイヤレス通信システム１１００におけるブルームフィルタすべての発見された識別子を、最終的に構築することができる。
[0112] 上記で説明されたように、いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、たとえば、各子ノードまたは子マスターノード１１２０になど、他のノードにブルームフィルタを要求することができる。いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、サービス発見フレーム（ＳＤＦ）を使用して要求を送信することができる。たとえば、各マスターノード１１２０および／またはアンカーノード１１１０は、設定された公開ビットを有するサービス発見属性１３００（図１３）を含むサービス発見フレームを送信することができる。
[0113] 様々な実施形態では、発見されたデバイスを求める要求は、送信するデバイスが発見されたデバイスの指示をそこから受信したデバイスの指示を含み得る。たとえば、アンカーノード１１１０は、それらのブルームフィルタ６００（図６）をすでに提供したマスターノード１１２０の完全または部分的識別子（ＭＡＣアドレスなど）のリストを含む、発見されたデバイス要求を、マスターノード１１２０へ送信することができる。いくつかの実施形態では、デバイスの指示自体は、送信するデバイスが発見されたデバイスの指示をそこから受信したデバイスを指示するブルームフィルタであり得る。
[0114] 様々な実施形態では、発見されたデバイスを求める要求は、要求に応答するべきであるデバイスのホップカウントを含み得る。ホップカウントは、最大、最小、または厳密なホップカウントであり得る。たとえば、アンカーノード１１１０は、１のホップカウントを指示する、発見されたデバイス要求を送信することができる。したがって、１ホップ離れたマスターノード１１２０のみが、発見されたデバイスの指示（図６のブルームフィルタ６００など）で応答するように構成される。いくつかの実施形態では、ノードは、要求中に含まれるホップカウントに基づいて、発見されたデバイスを求める要求に選択的に応答することができる。たとえば、１つの特定のデバイスは、特定のデバイスのホップカウントよりも高いホップカウントを有するデバイスからの要求のみに応答することができる。
[0115] いくつかの実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、図５に関してなど、本明細書で説明されたように、クラスタサイズを推定することができる。各マスターノード１１２０および／またはアンカーノード１１１０は、図１２に関して以下で説明されるように、アンカー情報属性を介して、クラスタサイズ推定値またはその指示を送信することができる。一実施形態では、クラスタサイズ推定値またはその指示は、発見ウィンドウ間のある間隔において送信された発見ビーコン中に含まれ得る。
[0116] このようにして、一例では、各マスターノード１１２０は、発見されたデバイスを示すブルームフィルタ６００（図６）を生成することができる。アンカーノード１１１０は、各マスターノード１１２０にブルームフィルタを要求することができ、たとえば、ビットＯＲ演算を介して、ブルームフィルタをそれ自体のものとマージすることができる。いくつかの実施形態では、マスターノード１１２０は、子ノードからブルームフィルタを受信し、受信されたブルームフィルタをそれら自体のローカルブルームフィルタとマージし、マージされたブルームフィルタを親ノードに渡し、それによって、アンカーノード１１１０に、ＮＡＮ全体のためのブルームフィルタを伝搬することができる。アンカーノード１１１０は、ネットワークサイズを推定し、そのビーコン中で推定値を送信することができる。マスターノード１１２０は、親ノードからビーコンを受信することができ、それら自体のビーコン中で推定されたネットワークサイズを再送信し、それによって、ＮＡＮ全体にわたって、推定されたネットワークサイズを伝搬することができる。
[0117] 様々な実施形態では、各マスターノード１１２０および／またはアンカーノード１１１０は、たとえば、発見されたデバイス要求に応答して、間欠的に、周期的に、ランダムに、および／または擬似ランダムに、発見されたデバイス識別子を指示するブルームフィルタ６００（図６）を送信することができる。
[0118] 図１２は、媒体アクセス制御（ＭＡＣ）フレーム１２００の例示的な構造を示す。いくつかの態様では、媒体アクセス制御フレーム（ＭＡＣ）１２００は、上記で説明されたビーコン信号のために利用され得る。示されるように、ＭＡＣフレーム１２００は、フレーム制御（ＦＣ）フィールド１２０２、持続時間／識別情報（ｄｕｒ）フィールド１２０４、受信機アドレス（Ａ１）フィールド１２０６、送信機アドレス（Ａ２）フィールド１２０８、いくつかの態様ではＮＡＮ ＢＳＳＩＤまたはクラスタＩＤを指示することができる宛先アドレス（Ａ３）フィールド１２１０、シーケンス制御（ＳＣ）フィールド１２１２、タイムスタンプフィールド１２１４、ビーコン間隔フィールド１２１６、能力フィールド１２１８、発見ウィンドウ情報を含み得る情報要素１２２０、およびフレーム検査シーケンス（ＦＣＳ）フィールド１２２２という、１１個の異なるフィールドを含む。フィールド１２０２〜１２２２は、いくつかの態様では、ＭＡＣヘッダを含む。各フィールドは、１つまたは複数のサブフィールドまたはフィールドを含み得る。たとえば、媒体アクセス制御ヘッダ１２００のフレーム制御フィールド１２０２は、プロトコルバージョン、タイプフィールド、サブタイプフィールド、および他のフィールドなど、複数のサブフィールドを含み得る。その上、本明細書で説明される様々なフィールドは、並べ替えられ、サイズ変更されてよく、いくつかのフィールドが省略されてよく、追加のフィールドが追加されてよいことが当業者には諒解されよう。
[0119] いくつかの態様では、ＮＡＮ ＢＳＳＩＤフィールド１２１０は、ＮＡＮデバイスのクラスタを指示することができる。別の実施形態では、各ＮＡＮは、異なる（たとえば、擬似ランダム）ＮＡＮ ＢＳＳＩＤ１２１０を有し得る。一実施形態では、ＮＡＮ ＢＳＳＩＤ１２１０は、サービスアプリケーションに基づき得る。たとえば、アプリケーションＡによって作成されたＮＡＮは、アプリケーションＡの識別子に基づくＢＳＳＩＤ１２１０を有し得る。いくつかの実施形態では、ＮＡＮ ＢＳＳＩＤ１２１０は、標準化団体によって定義され得る。いくつかの実施形態では、ＮＡＮ ＢＳＳＩＤ１２１０は、たとえば、デバイスロケーション、サーバにより割り当てられたＩＤなど、他のコンテキスト情報および／またはデバイス特性に基づき得る。一例では、ＮＡＮ ＢＳＳＩＤ１２１０は、ＮＡＮの緯度および経度ロケーションのハッシュを含み得る。示されたＮＡＮ ＢＳＳＩＤフィールド１２１０は、６オクテット長である。いくつかの実装形態では、ＮＡＮ ＢＳＳＩＤフィールド１２１０は、４、５、または８オクテット長であり得る。いくつかの実施形態では、ＡＰ１０４は、情報要素中でＮＡＮ ＢＳＳＩＤ１２１０を指示することができる。
[0120] 様々な実施形態では、フレーム１２００、または別の発見フレームは、アンカー情報属性、および／または、図１３に関して以下で説明されるサービス発見属性１３００などのサービス発見属性を含み得る。一実施形態では、ＮＡＮ ＩＥフィールド１２２０は含み得、フィールド１２０２は、アンカー情報属性および／またはサービス発見属性を含み得る。一実施形態では、アンカー情報属性は、クラスタサイズまたはクラスタサイズ推定値の指示を含み得る。一実施形態では、アンカー情報属性は、発見ウィンドウ間のある間隔において送られた発見ビーコン中に含まれ得る。一実施形態では、アンカー情報属性は、たとえば、周期的に、間欠的に、および／またはランダムもしくは擬似ランダムに、非請求の１つまたは複数のノード１１１０〜１１３０（図１１）によって送信され得る。
[0121] 図１３は、図１１のワイヤレス通信システム１１００内で採用され得る例示的なサービス発見属性１３００を示す。様々な実施形態では、本明細書で説明される任意のデバイス、または別の互換デバイスは、たとえば、任意のノード１１１０〜１１３０（図１１）、任意のモバイルデバイス１１２〜１１８、１２２〜１２８、および１３２〜１４２（図１）、ならびに／またはワイヤレスデバイス２０２（図２）など、サービス発見属性１３００を送信することができる。ワイヤレス通信システム１００（図１）および／またはワイヤレス通信システム１１００（図１１）における１つまたは複数のメッセージは、たとえば、ＮＡＮビーコン１２００（図１２）、発見フレーム、プローブ応答、および／または発見クエリフレームなど、サービス発見属性１３００を含み得る。一実施形態では、サービス発見フレームは、１つまたは複数のサービス発見属性１３００を含有する、パブリックアクションフレームを含み得る。別の例として、サービス発見属性１３００は、ベンダー固有ＩＥ中にあり得る。サービス発見属性１３００の１つまたは複数のフィールドは、サービス発見属性１３００に加えて、またはその代わりに、情報要素の属性中に含まれ得る。
[0122] 示された実施形態では、サービス発見属性１３００は、属性識別子１３０５と、長さフィールド１３２０と、サービス識別子１３１０と、サービス制御フィールド１３３０と、マッチングフィルタコンテナ１３５０と、サービス応答フィルタ（ＳＲＦ）情報コンテナ１３６０と、サービス固有情報コンテナ１３７０とを含む。サービス発見属性１３００は、追加のフィールドを含んでよく、フィールドは並べ替えられ、除去され、および／またはサイズ変更され得ることが当業者には諒解されよう。たとえば、様々な実施形態では、サービス発見属性１３００は、マッチングフィルタコンテナ１３５０および／またはマッチングフィルタコンテナ１３５０を省略することができ、追加の長さフィールドが含まれ得る。
[0123] 示されたサービス識別子フィールド１３１０は、６オクテット長である。いくつかの実装形態では、サービス識別子フィールド１３１０は、２、５、または１２オクテット長であり得る。いくつかの実装形態では、サービス識別子フィールド１３１０は、信号ごとにおよび／またはサービスプロバイダ間で長さが変化するなど、可変長であり得る。サービス識別子フィールド１３１０は、発見フレームのサービスまたはアプリケーションを識別する値を含み得る。たとえば、サービス識別子１３１０は、サービスに基づく、サービス名または他の値のハッシュを含み得る。いくつかの実施形態では、あらかじめ決定されたトークン値が予約され得る。たとえば、すべて０またはすべて１のサービス識別子は、ＮＡＮ管理動作を指示することができる。
[0124] 長さフィールド１３２０は、サービス発見属性１３００の長さ、または後続のフィールドの全長を指示するために使用され得る。図１３に示された長さフィールド１３２０は、２オクテット長である。いくつかの実装形態では、長さフィールド１３２０は、１、５、または１２オクテット長であり得る。いくつかの実装形態では、長さフィールド１３２０は、信号ごとにおよび／またはサービスプロバイダ間で長さが変化するなど、可変長であり得る。いくつかの実施形態では、０（または、別のあらかじめ決定されたトークン値）の長さは、１つまたは複数の他のフィールド（サービス制御フィールド１３３０、マッチングフィルタコンテナ１３５０、サービス応答フィルタ情報コンテナ１３６０、サービス固有情報コンテナ１３７０、および／または発見されたアドレス情報コンテナ１３８０など）が存在しないことを指示することができる。
[0125] サービス制御フィールド１３３０は、適用可能なサービスの情報を指示することができる。図１３に示されたサービス制御フィールド１３３０は、１オクテット長である。いくつかの実装形態では、サービス制御フィールド１３３０は、２、６、または８オクテット長であり得る。いくつかの実装形態では、サービス制御フィールド１３３０は、信号ごとにおよび／またはサービスプロバイダ間で長さが変化するなど、可変長であり得る。一実施形態では、サービス制御フィールド１３３０は、公開フラグと、サブスクライブフラグと、範囲制限フラグと、マッチングフィルタフラグと、サービス情報フラグと、ＡＰフラグと、発見されたアドレスフラグと、予約済みビットとを含み得る。一実施形態では、サービス制御フィールド１３３０は、発見されたデバイスを指示するブルームフィルタをフレームが含むという指示を含み得る。一実施形態では、サブスクライブフラグは、設定されるとき、受信するデバイスがそのブルームフィルタ６００（図６）を送るための要求を指示することができる。一実施形態では、公開フラグは、設定されるとき、ブルームフィルタ６００（図６）を含む応答フレームを指示することができる。サービス制御フィールド１３３０は、追加のフィールドを含んでよく、フィールドは並べ替えられ、除去され、および／またはサイズ変更され得ることが当業者には諒解されよう。
[0126] マッチングフィルタコンテナ１３５０は、マッチングフィルタ情報を指示することができる。図１３に示されたマッチングフィルタコンテナ１３５０は、可変長である。いくつかの実装形態では、マッチングフィルタコンテナ１３５０は、２、６、または８オクテット長であり得る。マッチングフィルタコンテナ１３５０は、ＮＡＮのためのマッチングフィルタ長さフィールドおよび／またはマッチングフィルタを含み得る。マッチングフィルタ長さフィールドは、マッチングフィルタの長さを指示することができる。マッチングフィルタ長さフィールドは、１オクテット長であり得る。一実施形態では、マッチングフィルタ長さは、０（または、別のあらかじめ決定されたトークン値）であってよく、マッチングフィルタが省略され得る。マッチングフィルタは、可変長であり得る。マッチングフィルタコンテナ１３５０は、追加のフィールドを含んでよく、フィールドは並べ替えられ、除去され、および／またはサイズ変更され得ることが当業者には諒解されよう。
[0127] サービス応答フィルタ情報コンテナ１３６０は、デバイスがクエリに応答するべきであるかどうかを指示することができる。いくつかの実施形態では、サービス応答フィルタ情報コンテナ１３６０は、サービス応答フィルタとサービス応答フィルタ長さフィールドとを含み得る。サービス応答フィルタは、たとえば、応答するべきではないデバイスの部分的および／または完全デバイス識別子（たとえば、ＭＡＣアドレス）のリストを含み得る。一実施形態では、サービス応答フィルタは、応答するべきではないデバイスの識別子（たとえば、ＭＡＣアドレス）のリストを指示するブルームフィルタを含み得る。図１３に示されたサービス応答フィルタ情報コンテナ１３６０は、可変長である。いくつかの実装形態では、サービス応答フィルタ情報コンテナ１３６０は、２、６、または８オクテット長であり得る。
[0128] サービス固有情報コンテナ１３７０は、適用可能なサービスに関係する１つまたは複数の追加のデータフィールドをカプセル化することができる。図１３に示されたサービス固有情報コンテナ１３７０は、可変長である。いくつかの実装形態では、サービス固有情報コンテナ１３７０は、１、５、または１２オクテット長であり得る。サービス固有情報コンテナ１３７０は、サービス固有情報長さフィールドおよび／またはサービス固有情報フィールドを含み得る。サービス固有情報長さフィールドは、サービス固有情報フィールドの長さを指示することができる。一実施形態では、サービス固有情報長さフィールドは、０（または、別のあらかじめ決定されたトークン値）であってよく、サービス固有情報フィールドが省略され得る。サービス固有情報フィールドは、可変長であり得る。いくつかの実装形態では、サービス固有情報フィールドは、１、５、または１２オクテット長であり得る。
[0129] いくつかの実施形態では、サービス固有情報フィールドは、発見されたアドレス情報コンテナを含み得る。発見されたアドレス情報コンテナは、送信するデバイス２０２（図２）によって発見されたデバイスの１つまたは複数のアドレスを指示することができる。たとえば、発見されたアドレス情報コンテナは、ブルームフィルタ６００（図６）を含み得る。発見されたアドレス情報は、可変長であり得る。いくつかの実装形態では、発見されたアドレス情報コンテナは、１、５、または１２オクテット長であり得る。
[0130] 本明細書で使用される「決定すること」という用語は、多種多様なアクションを包含する。たとえば、「決定すること」は、計算すること、算出すること、処理すること、導出すること、調査すること、探索すること（たとえば、テーブル、データベース、または別のデータ構造の中で探索すること）、確認することなどを含む場合がある。また、「決定すること」は、受信すること（たとえば、情報を受信すること）、アクセスすること（たとえば、メモリ中のデータにアクセスすること）などを含み得る。また、「決定すること」は、解決すること、選択すること、選ぶこと、確立することなどを含み得る。さらに、本明細書で使用される「チャネル幅」は、いくつかの態様では帯域幅を包含することがあり、または帯域幅と呼ばれることもある。
[0131] 上記で説明された方法の様々な動作は、様々なハードウェア構成要素および／もしくはソフトウェア構成要素、回路、ならびに／またはモジュールなど、その動作を実施することが可能な任意の適切な手段によって実施され得る。一般に、図に示された任意の動作は、その動作を実施することが可能な対応する機能的手段によって実施され得る。
[0132] 本開示に関して説明された様々な例示的な論理ブロック、モジュール、および回路は、汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ信号（ＦＰＧＡ）もしくは他のプログラマブル論理デバイス（ＰＬＤ）、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明された機能を実施するように設計されたそれらの任意の組合せを用いて実装または実施され得る。汎用プロセッサはマイクロプロセッサであり得るが、代替として、プロセッサは、任意の市販のプロセッサ、コントローラ、マイクロコントローラ、または状態機械であり得る。プロセッサはまた、コンピューティングデバイスの組合せ、たとえば、ＤＳＰとマイクロプロセッサとの組合せ、複数のマイクロプロセッサ、ＤＳＰコアと連携する１つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成として実装され得る。
[0133] １つまたは複数の態様では、説明された機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せに実装され得る。ソフトウェアに実装される場合、機能は、１つまたは複数の命令またはコードとして、コンピュータ可読媒体上に記憶され得るか、またはコンピュータ可読媒体を介して送信され得る。コンピュータ可読媒体は、ある場所から別の場所へのコンピュータプログラムの転送を容易にする任意の媒体を含む、コンピュータ記憶媒体と通信媒体の両方を含む。記憶媒体は、コンピュータによってアクセスされ得る任意の利用可能な媒体であり得る。限定ではなく例として、そのようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ（登録商標）、ＣＤ−ＲＯＭもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または、命令もしくはデータ構造の形態の所望のプログラムコードを搬送もしくは記憶するために使用され得、コンピュータによってアクセスされ得る、任意の他の媒体を備え得る。また、いかなる接続もコンピュータ可読媒体と適切に呼ばれる。たとえば、ソフトウェアが、同軸ケーブル、光ファイバーケーブル、ツイストペア、デジタル加入者回線（ＤＳＬ）、または赤外線、無線、およびマイクロ波などのワイヤレス技術を使用して、ウェブサイト、サーバ、または他のリモートソースから送信される場合、同軸ケーブル、光ファイバーケーブル、ツイストペア、ＤＳＬ、または赤外線、無線、およびマイクロ波などのワイヤレス技術は、媒体の定義に含まれる。本明細書で使用されるディスク（disk）およびディスク（disc）は、コンパクトディスク（disc）（ＣＤ）、レーザーディスク（登録商標）（disc）、光ディスク（disc）、デジタル多用途ディスク（disc）（ＤＶＤ）、フロッピー（登録商標）ディスク（disk）およびｂｌｕ−ｒａｙディスク（disc）を含み、ディスク（disk）は、通常、データを磁気的に再生し、一方ディスク（disc）は、データをレーザーで光学的に再生する。したがって、いくつかの態様では、コンピュータ可読媒体は、非一時的コンピュータ可読媒体（たとえば、有形媒体）を備え得る。加えて、いくつかの態様では、コンピュータ可読媒体は、一時的コンピュータ可読媒体（たとえば、信号）を備え得る。上記の組合せもコンピュータ可読媒体の範囲内に含まれるべきである。
[0134] 本明細書で開示された方法は、説明された方法を達成するための１つまたは複数のステップまたはアクションを備える。本方法のステップおよび／またはアクションは、特許請求の範囲から逸脱することなく互いに交換され得る。言い換えれば、ステップまたはアクションの特定の順序が指定されない限り、特定のステップおよび／またはアクションの順序および／または使用は、特許請求の範囲から逸脱することなく変更され得る。
[0135] 説明された機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せに実装され得る。ソフトウェアに実装される場合、機能は１つまたは複数の命令としてコンピュータ可読媒体上に記憶され得る。記憶媒体は、コンピュータによってアクセスされ得る任意の利用可能な媒体であり得る。限定ではなく例として、そのようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または、命令もしくはデータ構造の形態の所望のプログラムコードを搬送もしくは記憶するために使用され得、コンピュータによってアクセスされ得る、任意の他の媒体を備え得る。本明細書で使用されるディスク（disk）およびディスク（disc）は、コンパクトディスク（disc）（ＣＤ）、レーザーディスク（disc）、光ディスク（disc）、デジタル多用途ディスク（disc）（ＤＶＤ）、フロッピーディスク（disk）およびＢｌｕ−ｒａｙ（登録商標）ディスク（disc）を含み、一方ディスク（disk）は、通常、データを磁気的に再生し、ディスク（disc）は、データをレーザーで光学的に再生する。
[0136] したがって、いくつかの態様は、本明細書で提示された動作を実施するためのコンピュータプログラム製品を備え得る。たとえば、そのようなコンピュータプログラム製品は、本明細書で説明された動作を実施するために、１つまたは複数のプロセッサによって実行可能である命令を記憶した（および／または符号化した）コンピュータ可読媒体を備え得る。いくつかの態様では、コンピュータプログラム製品はパッケージング材料を含み得る。
[0137] ソフトウェアまたは命令はまた、送信媒体を介して送信され得る。たとえば、ソフトウェアが、同軸ケーブル、光ファイバーケーブル、ツイストペア、デジタル加入者回線（ＤＳＬ）、または赤外線、無線、およびマイクロ波などのワイヤレス技術を使用して、ウェブサイト、サーバ、または他のリモートソースから送信される場合、同軸ケーブル、光ファイバーケーブル、ツイストペア、ＤＳＬ、または赤外線、無線、およびマイクロ波などのワイヤレス技術は、送信媒体の定義に含まれる。
[0138] さらに、本明細書で説明された方法と技法とを実施するためのモジュールおよび／または他の適切な手段は、適用可能な場合、ユーザ端末および／または基地局によってダウンロードされ、および／または場合によっては取得され得ることを諒解されたい。たとえば、本明細書で説明された方法を実施するための手段の転送を容易にするために、そのようなデバイスがサーバに結合され得る。代替的に、本明細書で説明された様々な方法は、ユーザ端末および／または基地局が記憶手段をデバイスに結合し、または提供すると様々な方法を取得することができるように、記憶手段（たとえば、ＲＡＭ、ＲＯＭ、コンパクトディスク（ＣＤ）またはフロッピーディスクのような物理記憶媒体など）によって提供され得る。その上、本明細書で説明された方法と技法とをデバイスに与えるための任意の他の好適な技法が利用され得る。
[0139] 特許請求の範囲は、上記に示された厳密な構成および構成要素に限定されないことを理解されたい。上記で説明された方法および装置の構成、動作および詳細において、特許請求の範囲から逸脱することなく、様々な改変、変更および変形が行われ得る。
[0140] 上記は本開示の態様を対象とするが、本開示の他の態様およびさらなる態様は、その基本的範囲から逸脱することなく考案され得、その範囲は以下の特許請求の範囲によって決定される。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視するように構成されたワイヤレスデバイスであって、
前記近隣ワイヤレスデバイスのうちの１つからメッセージを受信するように構成された受信機と、前記メッセージは、前記近隣ワイヤレスデバイスに関連付けられた識別子を備える、
ブルームフィルタに前記識別子を追加するように、および、前記ブルームフィルタにおける０の数、または前記ブルームフィルタにおける１の数に基づいて、前記ブルームフィルタに追加された別個の文字列の数を推定するように構成されたプロセッサと、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記近隣ワイヤレスデバイスの数の推定値を表す、
を備えるワイヤレスデバイス。
［Ｃ２］
前記ワイヤレスデバイスが、前記ワイヤレスネットワーク全体にわたる連続する伝搬のために、前記ワイヤレスネットワークにおける前記近隣ワイヤレスデバイスの数の前記推定値を備えるビーコンを送信するように構成されたアンカーデバイスを備える、Ｃ１に記載のワイヤレスデバイス。
［Ｃ３］
前記ブルームフィルタが、ｍビットのビットアレイとｍ個のカウンタとを含み、各カウンタは、前記ビットアレイ中の異なるビットに関連付けられ、各カウンタは、０と最大値との間の整数値を有し、ここにおいて、前記プロセッサが、
持続時間Ｔの時間間隔ごとに、非０値を有する各カウンタの前記値を１だけ低減することと、
カウンタの前記値が０に低減される場合、前記カウンタに対応する前記ビットを０に設定することと
を行うようにさらに構成される、Ｃ１に記載のワイヤレスデバイス。
［Ｃ４］
前記プロセッサが、前記ビットアレイのいずれかのビットが１に設定されるとき、前記ビットに対応する前記カウンタを前記最大値に設定するようにさらに構成される、Ｃ３に記載のワイヤレスデバイス。
［Ｃ５］
前記ブルームフィルタがｍビットのビットアレイであり、前記ビットアレイに関連付けられたｋ個の異なるハッシュ関数を有しており、ここにおいて、各ハッシュ関数が、一様なランダム分布をもつｍ個のアレイ位置のうちの１つに、入力文字列をマッピングする、Ｃ１に記載のワイヤレスデバイス。
［Ｃ６］
前記ブルームフィルタに追加された前記別個の文字列の数Ｎ distinct が、次の公式によって計算され、すなわち、
Figure 0006026675
 ただし、Ｎ 0 は、前記アレイにおける０の数である、Ｃ５に記載のワイヤレスデバイス。
［Ｃ７］
前記ブルームフィルタが、最大Ｎ個のデバイスまで追跡するように設計され、前記ブルームフィルタのパラメータｍが、ほぼＮである値を有する、Ｃ５に記載のワイヤレスデバイス。
［Ｃ８］
前記ｋ個のハッシュ関数のうちの少なくとも１つが、入力文字列の巡回冗長検査である、Ｃ５に記載のワイヤレスデバイス。
［Ｃ９］
前記ｋ個のハッシュ関数のうちの少なくとも１つが、０とｐ−１との間の整数に入力文字列をマッピングする第１のハッシュ関数を使用して作成され、ここにおいて、前記少なくとも１つのハッシュ関数が、０とｐ−１との間の整数に入力文字列をマッピングするために、前記第１のハッシュ関数を使用することと、次いで、前記整数をｍで除算した余りを発見するために、モジュロ演算を適用することとを含み、前記余りは、前記少なくとも１つのハッシュ関数によって返される値である、Ｃ５に記載のワイヤレスデバイス。
［Ｃ１０］
前記第１のハッシュ関数が、前記入力文字列から複数のビットを選択し、パターンに従って、シーケンスにおいて前記ビットを配列し、前記ビットのシーケンスは、前記第１のハッシュ関数によって返される値である整数を表す、Ｃ９に記載のワイヤレスデバイス。
［Ｃ１１］
前記識別子が、次の、ＭＡＣアドレス、サービス識別子、またはアプリケーションベースの識別子のうちの１つである、Ｃ１に記載のワイヤレスデバイス。
［Ｃ１２］
前記プロセッサが、前記ワイヤレスネットワークにおける前記近隣ワイヤレスデバイスのうちの少なくとも１つから、前記ブルームフィルタを要求するようにさらに構成される、Ｃ１に記載のワイヤレスデバイス。
［Ｃ１３］
前記プロセッサが、前記ブルームフィルタを要求するために、前記近隣ワイヤレスデバイスへ、設定されたサブスクライブビットを備えるサービス発見フレームを送るように構成される、Ｃ１２に記載のワイヤレスデバイス。
［Ｃ１４］
前記サービス発見フレームが、そこからブルームフィルタがすでに受信された近隣ワイヤレスデバイスの指示、および、それに対して近隣デバイスが応答するべきであるホップカウントの指示のうちの、少なくとも１つを備える、Ｃ１３に記載のワイヤレスデバイス。
［Ｃ１５］
前記ワイヤレスデバイスが、アンカーノードおよびマスターノードのうちの少なくとも１つを備える、Ｃ１３に記載のワイヤレスデバイス。
［Ｃ１６］
前記プロセッサが、複数の前記近隣ワイヤレスデバイスから受信されたブルームフィルタのビット論理和を記憶することによって、前記近隣ワイヤレスデバイスのためのブルームフィルタを生成するようにさらに構成される、Ｃ１２に記載のワイヤレスデバイス。
［Ｃ１７］
前記ブルームフィルタが、ｍビットのビットアレイを含み、ここにおいて、前記プロセッサが、ランダムな時間の間隔において、１つまたは複数のビットを０にリセットするようにさらに構成され、前記１つまたは複数のビットは、前記ブルームフィルタの前記ｍビットからランダムに選び出され、ここにおいて、前記プロセッサが、次の、前記ネットワークにおけるワイヤレスデバイスの数、ワイヤレスデバイスが前記ネットワークを離れる推定レート、および、ワイヤレスデバイスがそれらのＭＡＣアドレスを変更する時間間隔のうちの１つまたは複数に基づいて、リセットされるべきビット数と前記ランダムな間隔の分布とを選ぶように構成される、Ｃ１に記載のワイヤレスデバイス。
［Ｃ１８］
ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視する方法であって、
前記近隣ワイヤレスデバイスのうちの１つからメッセージを受信することと、前記メッセージは、前記近隣ワイヤレスデバイスに関連付けられた識別子を備える、
ブルームフィルタに前記識別子を追加することと、
前記ブルームフィルタにおける０の数に基づいて、前記ブルームフィルタに追加された別個の文字列の数を推定することと、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記近隣ワイヤレスデバイスの数の推定値を表す、
を備える方法。
［Ｃ１９］
前記ブルームフィルタが、ｍビットのビットアレイとｍ個のカウンタとを含み、各カウンタは、前記ビットアレイ中の異なるビットに関連付けられ、各カウンタは、０と最大値との間の整数値を有し、ここにおいて、前記方法が、
持続時間Ｔの時間間隔ごとに、非０値を有する各カウンタの前記値を１だけ低減することと、
カウンタの前記値が０に低減される場合、前記カウンタに対応する前記ビットを０に設定することと
をさらに備える、Ｃ１８に記載の方法。
［Ｃ２０］
ビットが１に設定されるとき、前記ビットに対応する前記カウンタを前記最大値に設定することをさらに備える、Ｃ１９に記載の方法。
［Ｃ２１］
前記ブルームフィルタがｍビットのビットアレイであり、前記ビットアレイに関連付けられたｋ個の異なるハッシュ関数を有しており、ここにおいて、各ハッシュ関数が、一様なランダム分布をもつｍ個のアレイ位置のうちの１つに、入力文字列をマッピングする、Ｃ１８に記載の方法。
［Ｃ２２］
前記ｋ個のハッシュ関数のうちの少なくとも１つが、入力文字列の巡回冗長検査である、Ｃ２１に記載の方法。
［Ｃ２３］
前記ｋ個のハッシュ関数が、単一のハッシュ関数とｋ個の異なる補足文字列とを使用して実現され、ここにおいて、前記ブルームフィルタに前記識別子を追加することが、
前記識別子および前記ｋ個の補足文字列に基づいて、ｋ個の補正された文字列を生成することと、
前記ｋ個の補正された文字列を前記単一のハッシュ関数に供給し、したがって、ｋ個のアレイ位置を生成することと
を備える、Ｃ２１に記載の方法。
［Ｃ２４］
前記ブルームフィルタのパラメータｋが、１の値を有し、前記ブルームフィルタのパラメータｍが、前記ワイヤレスネットワークの最大サイズの約２倍である値を有する、Ｃ２１に記載の方法。
［Ｃ２５］
前記識別子が、次の、ＭＡＣアドレス、サービス識別子、またはアプリケーションベースの識別子のうちの１つである、Ｃ１８に記載の方法。
［Ｃ２６］
前記方法が、ワイヤレスネットワークに加入すると、前記ワイヤレスネットワークにおける少なくとも１つの近隣ワイヤレスデバイスから、前記ブルームフィルタを要求することと、近隣ワイヤレスデバイスからメッセージを受信することとをさらに備え、前記メッセージは、前記近隣ワイヤレスデバイスのブルームフィルタと、前記近隣ワイヤレスデバイスの前記ブルームフィルタが開始された時間とを含む、Ｃ１８に記載の方法。
［Ｃ２７］
前記方法が、複数の近隣ワイヤレスデバイスから受信されたブルームフィルタのビット論理和を記憶することによって、前記ワイヤレスデバイスのためのブルームフィルタを生成することをさらに備える、Ｃ２６に記載の方法。
［Ｃ２８］
少なくとも第１の近隣ワイヤレスデバイスに前記ブルームフィルタを要求することと、
ブルームフィルタに基づいて、ワイヤレスデバイスおよび前記第１の近隣ワイヤレスデバイスが共に有する、前記近隣ワイヤレスデバイスの数を推定することと、前記ブルームフィルタは、前記ワイヤレスデバイスの前記ブルームフィルタと、前記第１の近隣ワイヤレスデバイスの前記ブルームフィルタとのビット論理積を実施することによって生成される、
をさらに備える、Ｃ１８に記載の方法。
［Ｃ２９］
ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視するためのワイヤレスデバイスであって、
前記近隣ワイヤレスデバイスのうちの１つからメッセージを受信するための手段と、前記メッセージは、前記近隣ワイヤレスデバイスに関連付けられた識別子を備える、
ブルームフィルタに前記識別子を追加するための手段と、
前記ブルームフィルタにおける０の数に基づいて、前記ブルームフィルタに追加された別個の文字列の数を推定するための手段と、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記近隣ワイヤレスデバイスの数の推定値を表す、
を備えるワイヤレスデバイス。
［Ｃ３０］
ワイヤレスネットワークにおける近隣ワイヤレスデバイスの数を監視するための方法を実施するように構成されたコンピュータ実行可能命令を備える、非一時的物理的コンピュータストレージであって、前記方法が、
前記近隣ワイヤレスデバイスのうちの１つからメッセージを受信することと、前記メッセージは、前記近隣ワイヤレスデバイスに関連付けられた識別子を備える、
ブルームフィルタに前記識別子を追加することと、
前記ブルームフィルタにおける０の数に基づいて、前記ブルームフィルタに追加された別個の文字列の数を推定することと、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記近隣ワイヤレスデバイスの数の推定値を表す、
を備える、非一時的物理的コンピュータストレージ。

Claims (28)

  1. ワイヤレスネットワークにおける複数の近隣ワイヤレスデバイスの数を監視するように構成されたワイヤレスデバイスであって、
    前記複数の近隣ワイヤレスデバイスの第１の近隣ワイヤレスデバイスからメッセージを受信するように構成された受信機と、前記メッセージは、前記第１の近隣ワイヤレスデバイスに関連付けられた識別子を備える、
    ｍビットとｍ個のカウンタとを備えたブルームフィルタを利用することと、前記ｍ個のカウンタの各々は、前記ｍビットの異なるビットに関連付けられ、前記ｍ個のカウンタの各々は、０と最大値との間の値を有する、
    前記ブルームフィルタに、前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子を追加することと、
    持続時間Ｔの時間間隔ごとに、非０値を有する前記ｍ個のカウンタの各々の前記値を１だけ低減することと、
    前記ｍ個のカウンタのうちの１つの前記値が０に低減されるとき、前記ｍビットのうちの関連付けられたビットを０に設定することと、
    前記ブルームフィルタにおける０の数、または前記ブルームフィルタにおける１の数に基づいて、前記ブルームフィルタに存在する別個の文字列の数を推定することと
    を行うように構成されたプロセッサと、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスの数の推定値を表す、を備えるワイヤレスデバイス。
  2. 前記ワイヤレスデバイスが、前記ワイヤレスネットワーク全体にわたる連続する伝搬のために、前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスの数の前記推定値を備えるビーコンを送信するように構成されたアンカーデバイスを備える、請求項１に記載のワイヤレスデバイス。
  3. 前記プロセッサが、前記ｍビットのいずれか１つのビットが１に設定されるとき、前記１つのビットに関連付けられたカウンタの前記値を前記最大値に設定するようにさらに構成される、請求項１に記載のワイヤレスデバイス。
  4. ｋ個の異なるハッシュ関数は前記ブルームフィルタに関連付けられ、前記ｋ個のハッシュ関数の各々が、一様なランダム分布をもつ前記ｍビットのうちの１つに、入力文字列をマッピングする、請求項１に記載のワイヤレスデバイス。
  5. 前記別個の文字列の数が、次の公式によって推定され、
    Figure 0006026675
     ただし、Ｎdistinctは、前記別個の文字列の数であり、Ｎ0は、前記ブルームフィルタにおける前記０の数である、請求項４に記載のワイヤレスデバイス。
  6. 前記ブルームフィルタが、最大Ｎ個のデバイスまで追跡するように設計され、前記ブルームフィルタのパラメータｍが、ほぼＮである値を有する、請求項４に記載のワイヤレスデバイス。
  7. 前記ｋ個のハッシュ関数のうちの少なくとも１つが、入力文字列の巡回冗長検査である、請求項４に記載のワイヤレスデバイス。
  8. 前記ｋ個のハッシュ関数のうちの少なくとも１つが、０とｐ−１との間の整数に入力文字列をマッピングする第１のハッシュ関数を使用して作成され、ここにおいて、前記少なくとも１つのハッシュ関数が、０とｐ−１との間の整数に入力文字列をマッピングするために、前記第１のハッシュ関数を使用することと、次いで、前記整数をｍで除算した余りを発見するために、モジュロ演算を適用することとを含み、前記余りは、前記少なくとも１つのハッシュ関数によって返される値である、請求項４に記載のワイヤレスデバイス。
  9. 前記第１のハッシュ関数が、前記入力文字列から複数のビットを選択し、パターンに従って、シーケンスにおいて前記ビットを配列し、前記ビットのシーケンスは、前記第１のハッシュ関数によって返される値である整数を表す、請求項８に記載のワイヤレスデバイス。
  10. 前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子が、次の、ＭＡＣアドレス、サービス識別子、またはアプリケーションベースの識別子のうちの１つである、請求項１に記載のワイヤレスデバイス。
  11. 前記プロセッサが、前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスのうちの少なくとも１つから、前記ブルームフィルタを要求するようにさらに構成される、請求項１に記載のワイヤレスデバイス。
  12. 前記プロセッサが、前記ブルームフィルタを要求するために、前記複数の近隣ワイヤレスデバイスのうちの前記少なくとも１つへ、設定されたサブスクライブビットを備えるサービス発見フレームを送るようにさらに構成される、請求項１１に記載のワイヤレスデバイス。
  13. 前記サービス発見フレームが、そこからブルームフィルタがすでに受信された近隣ワイヤレスデバイスの指示、および、それに対して近隣デバイスが応答するべきであるホップカウントの指示のうちの、少なくとも１つを備える、請求項１２に記載のワイヤレスデバイス。
  14. 前記第１の近隣ワイヤレスデバイスが、アンカーノードまたはマスターノードのうちの少なくとも１つを備える、請求項１２に記載のワイヤレスデバイス。
  15. 前記プロセッサが、前記複数の近隣ワイヤレスデバイスの少なくとも１部分から受信された複数のブルームフィルタのビット論理和を記憶することによって、前記複数の近隣ワイヤレスデバイスのうちの前記少なくとも１つのための前記ブルームフィルタを生成するようにさらに構成される、請求項１１に記載のワイヤレスデバイス。
  16. 前記プロセッサが、ランダムな時間の間隔において、前記ｍビットの１つまたは複数のビットを０にリセットするようにさらに構成され、前記ｍビットの前記１つまたは複数のビットはランダムに選び出され、前記プロセッサが、
    前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスの数、
    前記複数の近隣ワイヤレスデバイスが前記ワイヤレスネットワークを離れる推定レート、および、
    前記複数の近隣ワイヤレスデバイスがそれらのＭＡＣアドレスを変更する１つまたは複数の時間間隔
    のうちの１つまたは複数に基づいて、リセットされるべき前記ｍビットの数と前記ランダムな間隔の分布とを選ぶようにさらに構成される、請求項１に記載のワイヤレスデバイス。
  17. ワイヤレスネットワークにおける複数の近隣ワイヤレスデバイスの数を監視する方法であって、
    前記複数の近隣ワイヤレスデバイスの第１の近隣ワイヤレスデバイスからメッセージを受信することと、前記メッセージは、前記第１の近隣ワイヤレスデバイスに関連付けられた識別子を備える、
    ｍビットとｍ個のカウンタとを備えたブルームフィルタを利用することと、前記ｍ個のカウンタの各々は、前記ｍビットの異なるビットに関連付けられ、前記ｍ個のカウンタの各々は、０と最大値との間の値を有する、
    前記ブルームフィルタに、前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子を追加することと、
    持続時間Ｔの時間間隔ごとに、非０値を有する前記ｍ個のカウンタの各々前記値を１だけ低減することと、
    前記ｍ個のカウンタのうちの１つの前記値が０に低減されるとき、前記ｍビットのうちの関連付けられたビットを０に設定することと、
    前記ブルームフィルタにおける０の数または前記ブルームフィルタにおける１の数に基づいて、前記ブルームフィルタに存在する別個の文字列の数を推定することと、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスの数の推定値を表す、を備える方法。
  18. 前記ｍビットのうちのいずれか１つのビットが１に設定されるとき、前記１つのビットに関連付けられたカウンタの前記値を前記最大値に設定することをさらに備える、請求項１７に記載の方法。
  19. ｋ個の異なるハッシュ関数は前記ブルームフィルタに関連付けられ、ここにおいて、前記ｋ個のハッシュ関数の各々が、一様なランダム分布をもつ前記ｍビットのうちの１つに、入力文字列をマッピングする、請求項１７に記載の方法。
  20. 前記ｋ個のハッシュ関数のうちの少なくとも１つが、入力文字列の巡回冗長検査である、請求項１９に記載の方法。
  21. 前記ｋ個のハッシュ関数が、単一のハッシュ関数とｋ個の異なる補足文字列とを使用して実現され、ここにおいて、前記ブルームフィルタに、前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子を追加することが、
    前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子および前記ｋ個の異なる補足文字列に基づいて、ｋ個の補正された文字列を生成することと、
    前記ｋ個の補正された文字列および前記単一のハッシュ関数に基づいて、ｋ個のアレイ位置を生成することとを備える、請求項１９に記載の方法。
  22. 前記ブルームフィルタのパラメータｋが、１の値を有し、前記ブルームフィルタのパラメータｍが、前記ワイヤレスネットワークの最大サイズの実質的に２倍である値を有する、請求項１９に記載の方法。
  23. 前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子が、次の、ＭＡＣアドレス、サービス識別子、またはアプリケーションベースの識別子のうちの１つである、請求項１７に記載の方法。
  24. 前記方法が、前記ワイヤレスネットワークに加入すると、前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスのうちの少なくとも１つから、現在のブルームフィルタを要求することと、
    前記複数の近隣ワイヤレスデバイスのうちの前記少なくとも１つからメッセージを受信することとをさらに備え、前記メッセージは、前記現在のブルームフィルタと、前記近隣ワイヤレスデバイスの前記現在のブルームフィルタが開始された時間とを含む、請求項１７に記載の方法。
  25. 前記方法が、前記複数の近隣ワイヤレスデバイスのうちの少なくとも１部分から受信された複数のブルームフィルタのビット論理和を記憶することによって、前記複数の近隣ワイヤレスデバイスのうちの前記少なくとも１つのための前記ブルームフィルタを生成することをさらに備える、請求項２４に記載の方法。
  26. 少なくとも第２の近隣ワイヤレスデバイスから第２のブルームフィルタを要求することと、
    組み合わされたブルームフィルタに基づいて、ワイヤレスデバイスおよび前記第２の近隣ワイヤレスデバイスが共に有する、前記複数の近隣ワイヤレスデバイスの共有された数を推定することと、前記組み合わされたブルームフィルタは、前記ワイヤレスデバイスによって利用された前記ブルームフィルタと、前記第２のブルームフィルタとのビット論理積を実施することによって生成される、をさらに備える、請求項１７に記載の方法。
  27. ワイヤレスネットワークにおける複数の近隣ワイヤレスデバイスの数を監視するためのワイヤレスデバイスであって、
    前記複数の近隣ワイヤレスデバイスの第１の近隣ワイヤレスデバイスからメッセージを受信するための手段と、前記メッセージは、前記第１の近隣ワイヤレスデバイスに関連付けられた識別子を備える、
    ｍビットとｍ個のカウンタとを備えたブルームフィルタを利用するための手段と、前記ｍ個のカウンタの各々は、前記ｍビットの異なるビットに関連付けられ、前記ｍ個のカウンタの各々は、０と最大値との間の値を有する、
    前記ブルームフィルタに、前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子を追加するための手段と、
    持続時間Ｔの時間間隔ごとに、非０値を有する前記ｍ個のカウンタの各々の前記値を１だけ低減するための手段と、
    前記ｍ個のカウンタのうちの１つの前記値が０に低減されるとき、前記ｍビットのうちの関連付けられたビットを０に設定するための手段と、
    前記ブルームフィルタにおける０の数または前記ブルームフィルタにおける１の数に基づいて、前記ブルームフィルタに存在する別個の文字列の数を推定するための手段と、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスの数の推定値を表す、を備えるワイヤレスデバイス。
  28. ワイヤレスネットワークにおける複数の近隣ワイヤレスデバイスの数を監視するための方法を実施するように構成されたコンピュータ実行可能命令を備える、非一時的物理的コンピュータストレージであって、前記方法が、
    前記複数の近隣ワイヤレスデバイスの第１の近隣ワイヤレスデバイスからメッセージを受信することと、前記メッセージは、前記第１の近隣ワイヤレスデバイスに関連付けられた識別子を備える、
    ｍビットとｍ個のカウンタとを備えたブルームフィルタを利用することと、前記ｍ個のカウンタの各々は、前記ｍビットの異なるビットに関連付けられ、前記ｍ個のカウンタの各々は、０と最大値との間の値を有する、
    前記ブルームフィルタに、前記第１の近隣ワイヤレスデバイスに関連付けられた前記識別子を追加することと、
    持続時間Ｔの時間間隔ごとに、非０値を有する前記ｍ個のカウンタの各々の前記値を１だけ低減することと、
    前記ｍ個のカウンタのうちの１つの前記値が０に低減されるとき、前記ｍビットのうちの関連付けられたビットを０に設定することと、
    前記ブルームフィルタにおける０の数または前記ブルームフィルタにおける１の数に基づいて、前記ブルームフィルタに存在する別個の文字列の数を推定することと、前記別個の文字列の数は、前記ワイヤレスネットワークにおける前記複数の近隣ワイヤレスデバイスの数の推定値を表す、を備える、非一時的物理的コンピュータストレージ。
JP2015555281A 2013-01-30 2014-01-23 ワイヤレスネットワークのサイズの監視 Active JP6026675B2 (ja)

Applications Claiming Priority (11)

Application Number Priority Date Filing Date Title
US201361758577P 2013-01-30 2013-01-30
US61/758,577 2013-01-30
US201361762246P 2013-02-07 2013-02-07
US61/762,246 2013-02-07
US201361824907P 2013-05-17 2013-05-17
US61/824,907 2013-05-17
US201361842328P 2013-07-02 2013-07-02
US61/842,328 2013-07-02
US14/161,556 US9226231B2 (en) 2013-01-30 2014-01-22 Systems and methods for monitoring the size of a wireless network
US14/161,556 2014-01-22
PCT/US2014/012803 WO2014120557A1 (en) 2013-01-30 2014-01-23 Monitoring the size of a wireless network

Publications (3)

Publication Number Publication Date
JP2016506215A JP2016506215A (ja) 2016-02-25
JP2016506215A5 JP2016506215A5 (ja) 2016-05-26
JP6026675B2 true JP6026675B2 (ja) 2016-11-16

Family

ID=51222852

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2015555281A Active JP6026675B2 (ja) 2013-01-30 2014-01-23 ワイヤレスネットワークのサイズの監視

Country Status (8)

Country Link
US (1) US9226231B2 (ja)
EP (1) EP2952025B1 (ja)
JP (1) JP6026675B2 (ja)
KR (1) KR101660471B1 (ja)
CN (1) CN104956701B (ja)
ES (1) ES2763649T3 (ja)
HU (1) HUE045516T2 (ja)
WO (1) WO2014120557A1 (ja)

Families Citing this family (37)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105191451B (zh) * 2013-02-12 2017-05-17 英特尔Ip公司 用于同步设备和相邻区域网络化(nan)配置的方法、无线通信站和系统
US9154934B2 (en) * 2013-03-28 2015-10-06 Futurewei Technologies, Inc. System and method for pre-association discovery
US10003970B2 (en) * 2013-05-16 2018-06-19 Telefonaktiebolaget L M Ericsson (Publ) Coordinator and device in a radio communication network
CN104053227B (zh) 2013-12-02 2017-06-27 华为终端有限公司 一种用于锚主设备选择的方法和设备
WO2015119440A1 (ko) * 2014-02-05 2015-08-13 엘지전자 주식회사 무선 통신 시스템에서 nan 단말의 신호 송수신 방법 및 장치
US9439089B2 (en) * 2014-05-23 2016-09-06 Google Inc. Device to device round-trip time (RTT) measurement via neighbor aware network
EP3141010B1 (en) * 2014-06-24 2019-09-11 Google LLC Mesh network commissioning
KR102222337B1 (ko) * 2014-08-05 2021-03-04 삼성전자주식회사 전자 기기의 어플리케이션 동기화 방법 및 장치
CN106688258B (zh) 2014-09-04 2020-05-08 Lg电子株式会社 用于nan的无线资源调度方法和装置
US9788264B2 (en) 2014-10-17 2017-10-10 Qualcomm Incorporated Bloom filter for service hint information in advertisements
US10021644B2 (en) * 2014-10-30 2018-07-10 Qualcomm Incorporated Network discovery
US20160142897A1 (en) * 2014-11-14 2016-05-19 Telefonaktiebolaget L M Ericsson (Publ) Enriched D2D Discovery Content
KR102251326B1 (ko) * 2014-11-25 2021-05-12 삼성전자주식회사 근접 네트워크 구성 방법 및 그 전자 장치
US10827484B2 (en) 2014-12-12 2020-11-03 Qualcomm Incorporated Traffic advertisement in neighbor aware network (NAN) data path
US10820314B2 (en) 2014-12-12 2020-10-27 Qualcomm Incorporated Traffic advertisement in neighbor aware network (NAN) data path
US9763074B2 (en) * 2015-01-01 2017-09-12 Intel IP Corporation Apparatus, system and method of communicating a beacon frame
CN105991325B (zh) * 2015-02-10 2019-06-21 华为技术有限公司 处理至少一个分布式集群中的故障的方法、设备和系统
WO2016144088A1 (ko) * 2015-03-09 2016-09-15 엘지전자 주식회사 무선 통신 시스템에서 멀티 채널을 이용하여 데이터를 전송하는 방법 및 장치
US10129813B2 (en) * 2015-03-11 2018-11-13 Cisco Technology, Inc. Minimizing link layer discovery based on advertising access technology parameters in a multimode mesh network
US10277686B2 (en) * 2015-07-29 2019-04-30 Cisco Technology, Inc. Service discovery optimization in a network based on bloom filter
JP6548539B2 (ja) * 2015-09-24 2019-07-24 キヤノン株式会社 無線通信装置、無線通信方法、およびプログラム
US10210195B2 (en) * 2016-02-12 2019-02-19 International Business Machines Corporation Locating data in a set with a single index using multiple property values
CN106647397B (zh) * 2016-12-22 2019-09-10 北京金风科创风电设备有限公司 风电场联网设备列表的获取方法及装置
JP6805816B2 (ja) * 2016-12-27 2020-12-23 富士通株式会社 情報処理装置、情報処理システム、情報処理方法及びプログラム
US20190007903A1 (en) * 2017-06-28 2019-01-03 Qualcomm Incorporated Coordinated neighbor aware network (nan) role assignment
US10999780B2 (en) * 2017-11-15 2021-05-04 Apple Inc. Bluetooth trigger for NAN
KR102501760B1 (ko) * 2018-04-23 2023-02-21 삼성전자주식회사 복수의 주파수 대역에서 신호를 전송하기 위한 장치 및 방법
US11147126B2 (en) * 2018-05-15 2021-10-12 Apple Inc. Neighbor awareness networking discovery window congestion mitigation
CN108718401B (zh) * 2018-08-09 2020-09-01 Oppo广东移动通信有限公司 视频会议实现方法及相关装置
CN109271408B (zh) * 2018-08-31 2020-07-28 阿里巴巴集团控股有限公司 一种分布式数据连接处理方法、装置、设备及存储介质
GB2592792B (en) * 2018-10-18 2022-09-07 Tektronix Communications System and method for space and time efficient probe search analytics
US11595971B1 (en) * 2019-05-28 2023-02-28 Marvell Asia Pte Ltd Quieting a wireless local area network
KR102748855B1 (ko) * 2019-10-02 2025-01-02 삼성전자주식회사 전자 장치 및 전자 장치에서의 서비스 디스커버리 수행 방법
CN113381874B (zh) * 2020-03-10 2023-06-02 上海杰之能软件科技有限公司 一种故障信号处理方法、存储介质及终端
CN113556692A (zh) * 2020-04-24 2021-10-26 北京小米移动软件有限公司 网络设备探测方法、装置及系统
US12483591B2 (en) * 2023-11-29 2025-11-25 Radware Ltd. Detection and mitigation of UDP-based DDoS attacks
US12603770B2 (en) * 2024-09-05 2026-04-14 Ava Labs, Inc. Salted bloom filters for peer-to-peer data dissemination

Family Cites Families (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030026268A1 (en) * 2000-11-28 2003-02-06 Siemens Technology-To-Business Center, Llc Characteristic routing
US7054867B2 (en) * 2001-09-18 2006-05-30 Skyris Networks, Inc. Systems, methods and programming for routing and indexing globally addressable objects and associated business models
US8185653B2 (en) 2004-08-09 2012-05-22 Johnny Yau Method and apparatus for ad hoc mesh routing
US8040836B2 (en) * 2006-05-26 2011-10-18 Microsoft Corporation Local network coding for wireless networks
US8520704B2 (en) * 2007-07-10 2013-08-27 Qualcomm Incorporated Coding methods of communicating identifiers in peer discovery in a peer-to-peer network
US9301121B2 (en) 2007-07-11 2016-03-29 Qualcomm Incorporated Peer to peer multiple identifiers
US8406132B2 (en) * 2008-05-30 2013-03-26 Alcatel Lucent Estimating cardinality distributions in network traffic
JP5536891B2 (ja) * 2009-09-01 2014-07-02 エヌイーシー ヨーロッパ リミテッド ネットワークのモニタリング方法およびモニタリング機能を含むネットワーク
US8134934B2 (en) 2009-09-21 2012-03-13 Alcatel Lucent Tracking network-data flows
US8578049B2 (en) * 2010-10-04 2013-11-05 Futurewei Technologies, Inc. Content router forwarding plane architecture
WO2012059794A1 (en) * 2010-11-05 2012-05-10 Nokia Corporation Method and apparatus for providing efficient management of certificate revocation
US8880880B2 (en) 2011-07-29 2014-11-04 Qualcomm Incorporated Facilitating access control in peer-to-peer overlay networks
US8472983B1 (en) 2011-12-07 2013-06-25 Cisco Technology, Inc. Selective location-aware paging
US20140032714A1 (en) * 2012-07-27 2014-01-30 Interdigital Patent Holdings, Inc. Method and apparatus for publishing location information for a content object
US9071533B2 (en) * 2012-07-31 2015-06-30 Cisco Technology, Inc. Multicast group assignment using probabilistic approximations

Also Published As

Publication number Publication date
US20140211659A1 (en) 2014-07-31
CN104956701A (zh) 2015-09-30
CN104956701B (zh) 2020-01-21
KR20150111994A (ko) 2015-10-06
US9226231B2 (en) 2015-12-29
HUE045516T2 (hu) 2019-12-30
EP2952025B1 (en) 2019-09-25
KR101660471B1 (ko) 2016-09-27
ES2763649T3 (es) 2020-05-29
WO2014120557A1 (en) 2014-08-07
JP2016506215A (ja) 2016-02-25
EP2952025A1 (en) 2015-12-09

Similar Documents

Publication Publication Date Title
JP6026675B2 (ja) ワイヤレスネットワークのサイズの監視
JP6363256B2 (ja) ワイヤレスネットワーク上の改善された通信のためのシステムおよび方法
JP6400599B2 (ja) 近傍アウェアネットワークにおいてフレームをフォーマットするためのシステムおよび方法
JP6158362B2 (ja) 近傍アウェアネットワークにおいてデバイスを発見するためのシステムおよび方法
JP2016507180A5 (ja)
JP5847943B2 (ja) 低電力媒体アクセスのためのシステムおよび方法

Legal Events

Date Code Title Description
A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20160329

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20160329

A871 Explanation of circumstances concerning accelerated examination

Free format text: JAPANESE INTERMEDIATE CODE: A871

Effective date: 20160329

A975 Report on accelerated examination

Free format text: JAPANESE INTERMEDIATE CODE: A971005

Effective date: 20160415

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20160510

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20160810

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20160913

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20161012

R150 Certificate of patent or registration of utility model

Ref document number: 6026675

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250