(57)【特許請求の範囲】
【請求項１】
クラスタを形成し、基地局への共通の通信リンクを有する複数の移動ノードの間で、ネットワーク・トポロジを決定するための、ワイヤレス通信システムにおける方法であって、各移動ノードが一意のアイデンティティを有し、前記方法が、
前記移動ノードの少なくとも１つに、送信スロット中に信号を送信させるステップを含み、前記少なくとも１つのノードは、それによって、クラスタ・ヘッド（ＣＨ：cluster head）になり、さらに、
前記ＣＨ以外の移動ノード（以降、「非ＣＨノード」と称する）において、送信フレーム中で１つ又は複数の送信間隔を選択するステップと、
前記非ＣＨノードのそれぞれに、前記選択された送信間隔中、所与の非ＣＨノードに対して信号を送信させるステップと、
少なくとも１つの信号が受信される前記送信間隔によって非ＣＨノードから受信した送信信号の第１のダイジェストを、前記ＣＨが作成するステップと、
前記ダイジェスト、前記ＣＨについてのノード・アイデンティティ及び前記ＣＨ信号が送信された前記送信スロットの関数として、前記ノードのクラスタに関するコンパクトなトポロジ・グラフを構築するステップとを含む、方法。
【請求項２】
請求項１に記載の方法において、
前記非ＣＨノードのそれぞれが、
（１）  一連の送信間隔中に他の非ＣＨノードからの送信信号を検出する、
（２）  前記送信フレームにわたって送信される信号を検出したとき、前記フレームの送信間隔中の少なくとも１つの送信信号の有無をベクトルとして記録する、
（３）  前記ベクトルを前記ＣＨに送信する、方法。
【請求項３】
請求項１に記載の方法において、
前記ＣＨが第１のダイジェストを作成するステップは、前記送信フレーム中の前記送信間隔のそれぞれの間、前記非ＣＨノードのそれぞれから送信される信号の有無について、バイナリ・ベクトルとして、ログをとるステップをさらに含む、方法。
【請求項４】
請求項１に記載の方法において、
前記非ＣＨノードにおいて送信間隔を選択するステップは、前記非ＣＨノードのそれぞれによって選択される前記送信間隔の少なくとも１つに、他の送信する非ＣＨノードとの干渉が無いことが保証されるように実施される、方法。
【請求項５】
請求項１に記載の方法において、
該コンパクトなトポロジ・グラフを構築するステップは、該第１のダイジェスト、該ＣＨについてのノード・アイデンティティ、及び該ＣＨ信号が送信された該送信間隔に基づいて、基地局によって実施される、方法。
【請求項６】
請求項１に記載の方法において、
ノード識別のプライバシーは、ノード・アイデンティティの通信を該基地局とのトランザクションのみに限定することにより維持される、方法。
【請求項７】
クラスタを形成し、基地局への共通の通信リンクを有する複数の移動ノードの間で、ネットワーク・トポロジを決定するための、ワイヤレス通信システムにおける方法であって、各移動ノードが一意のアイデンティティを有し、該方法が、
該複数の移動ノードの少なくとも１つに、送信スロット中に信号を送信させるステップを含み、該少なくとも１つのノードは、それによって、クラスタ・ヘッド（ＣＨ）になり、
該ＣＨ以外の各移動ノード（以降、「非ＣＨノード」と称する）は、送信フレーム中で１つ又は複数の送信間隔を選択するように構成され、各非ＣＨノードは、さらに、その選択された送信間隔中に信号を送信するように構成され、
該ＣＨは、少なくとも１つの信号が受信される該送信間隔によって、非ＣＨノードから受信した送信信号の第１のダイジェストを作成し、該方法は、さらに、
該ダイジェスト、該ＣＨについてのノード・アイデンティティ、及び該ＣＨ信号が送信された該送信スロットの関数として、該ノードのクラスタに関するコンパクトなトポロジ・グラフを構築するステップを含む、方法。
【請求項８】
請求項７に記載の方法において、
該非ＣＨノードのそれぞれが、
（１） 一連の送信間隔中に他の非ＣＨノードからの送信信号を検出する、
（２） 該送信フレームにわたって送信される信号を検出したとき、該フレームの送信間隔中の少なくとも１つの送信信号の有無をベクトルとして記録する、
（３） 該ベクトルを該ＣＨに送信する、方法。
【請求項９】
請求項８に記載の方法において、
該ＣＨは、所与の信号が該非ＣＨノードによって送信される該ベクトルに基づいて検出される該送信間隔によって送信信号の第２のダイジェストを作成する、方法。
【請求項１０】
請求項９に記載の方法において、
該第１のダイジェスト及び該第２のダイジェスト、該ＣＨについてのノード・アイデンティティ、及び該ＣＨ信号が送信される該送信間隔の関数として、第２のコンパクトなトポロジ・グラフを構築するステップをさらに含む、方法。
【請求項１１】
請求項８に記載の方法において、
該非ＣＨノードのそれぞれは、所定の閾値に対する受信される信号のエネルギーの関数として、所与の送信間隔中の送信信号の前記有無を決定する、方法。
【請求項１２】
請求項７に記載の方法において、
該ＣＨが第１のダイジェストを作成するステップは、該送信フレーム中の該送信間隔の各々の間、該非ＣＨノードのそれぞれから送信される信号の有無について、バイナリ・ベクトルとしてログをとるステップをさらに含む、方法。
【請求項１３】
請求項１２に記載の方法において、
該ＣＨは、所定の閾値に対する受信される信号のエネルギーの関数として、所与の送信間隔中の送信信号の前記有無を決定する、方法。
【請求項１４】
請求項７に記載の方法において、
該非ＣＨノードにおいて送信間隔を選択するステップは、該非ＣＨノードのそれぞれによって選択される前記送信間隔の少なくとも１つに、他の送信する非ＣＨノードとの干渉が無いことが保証されるように実施される、方法。
【請求項１５】
請求項１４に記載の方法において、
該非ＣＨノードの各々が、長さｋの送信間隔のウィンドウ中でｄ個の送信間隔まで送信し、ｋ及びｄは該基地局によって提供される整数値である、方法。
【請求項１６】
請求項１５に記載の方法において、
所与の非ＣＨノードが送信するｄ個までの送信間隔の該所与の非ＣＨノードによる決定は、シード値のランダム・ハッシュ及び該所与の非ＣＨノードについての識別子の表示に基づいており、該シード値は、該基地局によって該非ＣＨノードに提供される、方法。
【請求項１７】
請求項７に記載の方法において、
該コンパクトなトポロジ・グラフを構築するステップは、該第１のダイジェスト、該ＣＨについてのノード・アイデンティティ、及び該ＣＨ信号が送信された該送信間隔に基づいて、基地局によって実施される、方法。
【請求項１８】
請求項７に記載の方法において、
ノード識別のプライバシーは、ノード・アイデンティティの通信を該基地局とのトランザクションのみに限定することにより維持される、方法。
【請求項１９】
クラスタを形成し、基地局への共通の通信リンクを有する複数の移動ノードの間で、ネットワーク・トポロジを決定するための、ワイヤレス通信システムにおける方法であって、各移動ノードが一意のアイデンティティを有し、前記方法が、
前記移動ノードの１つによって、送信スロット中に信号を送信するステップを含み、前記１つの移動ノードは、それによって、クラスタ・ヘッド（ＣＨ）になり、さらに、
前記ＣＨ以外の残りの複数の移動ノード（以降、「非ＣＨノード」と称する）のそれぞれから、送信フレーム中の１つ又は複数の送信間隔中に、信号を受信するステップと、
前記信号が受信される前記送信間隔によって、前記非ＣＨノードから受信する送信信号の第１のダイジェストを、前記ＣＨが作成するステップと、
前記第１のダイジェスト、前記ＣＨについてのノード・アイデンティティ、及び前記ＣＨ信号が送信された前記送信スロットを基地局に送信するステップとを含む、方法。
【請求項２０】
請求項１９に記載の方法において、
前記ＣＨが第１のダイジェストを作成するステップは、バイナリ・ベクトルとして、前記送信フレーム中の前記送信間隔のそれぞれ中に前記非ＣＨノードのそれぞれから送信される信号の有無についてログをとるステップをさらに含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にワイヤレス通信システム中のノードのマッピングに関する。
【背景技術】
【０００２】
現代のワイヤレス通信システムは、多数の無線アクセス技術によって特徴付けられており、そのいくつかは、セルラ通信サービス（cellular communications service）の世代の継続的な発展に由来しており、そのいくつかは、従来のセルラ・パラダイムの外側で発達してきたワイヤレス通信サービスを代表している。前者の例は、ユニバーサル・モバイル・テレコミュニケーションズ・システム（ＵＭＴＳ：Universal Mobile Telecommunications System）およびロング・ターム・エボリューション（ＬＴＥ：Long Term Evolution）を含み、一方Ｗｉ−Ｆｉなどの８０２．１１サービスは、後者を典型的に示す。２つ以上の無線アクセス技術に適合するＲＦ性能を有するマルチ・モードのユーザ端末（以降、通常、「移動ノード（mobile node）」と称する）は、当面の時間にもっとも適した、利用可能な技術に切り替えることができる。これは、ユーザと、そのネットワークに多数の技術を用いて運営するシステム事業者との両方に利点をもたらす、すなわち、ユーザは、所与のとき所与の技術によって動作しているが、そのユーザの端末がサポートする他の技術用のネットワークではないネットワークにアクセスできるようになる可能性があり、事業者は、そのネットワークが、異なる技術の通信事業者の間と負荷を分散することがしばしばできるようになり、ネットワークの使用量および性能が改善される。
【０００３】
従来のセルラ方式および８０２．１１方式の両方とのアクセスをサポートするユーザ端末の場合に少なくとも関し、総合的な使用可能なネットワーク（aggregate available network）は、ハイブリッド・セルラ・アーキテクチャを実施するものとして特徴付けることができる。ハイブリッド・セルラ・アーキテクチャの利点は、コンテンツ・キャッシュ、セル・リレー、アグリゲータ（aggregator）、モビリティ・プレディクタ（mobility predictor）などとして動作することによって、様々な機能において基地局（ＢＳ：base station）を支援するエンド・ユーザ装置の能力にある。ハイブリッド・アーキテクチャでは、キー差別化要因は、基地局が、所与の移動ノード（ＭＮ：mobile node）のロケーション、ならびに、それに隣接する移動ノードのロケーションを知っていることである。このロケーション情報は、移動ノードによってそれらの二次無線（一般に、８０２．１１方式へのアクセスをサポートする無線）を使用して形成されるネットワークのトポロジを、基地局が決定するのをサポートする。このトポロジ情報に対する可用性が、ハイブリッド・アーキテクチャの潜在的な利益を十分に活用するために、基地局にとっては不可欠なものである。
【０００４】
セル中の移動ノードによってトポロジ情報を発見するための手順が、当技術分野で一般に知られているが、従来の焦点は、各ノードがネットワーク全体の接続性グラフをどのようにして発見するのかという点にあった。ハイブリッド・モデルでは、基地局は、そのサービスが提供されるＭＮの間での基本的なネットワーク・グラフのトポロジを知る必要がある。しかし、基地局は、サービスが提供されるＭＮのすべての間でのリンクの集合全体を必ずしも知る必要がない。たとえば、基地局は、サービスが提供されるＭＮの間の高品質なリンクだけを知ることに関心があることもあれば、それらのＭＮなどの間に少なくとも１つの経路が存在するのかどうかだけを知ることに関心があることもある。これらの機能の多くは、ＭＮネットワークのトポロジ全体に関する知識なしに、対処することができる。そのように必要とされる縮小されたトポロジは、本明細書ではコンパクトなトポロジ・グラフ（ＣＴＧ：compact topology graph）と称する。
【０００５】
別の問題は、トポロジ発見はアドホックのワイヤレス・ネットワークについては分散した形で行うことができるが、ハイブリッド・ネットワークの場合、プロセスは、本質的に集中型であって、移動ノードすべてが、それに隣接する移動ノードについて単一の宛先（すなわち、基地局）に通知する。これは、過剰な送信オーバーヘッドをもたらす恐れがある。
【０００６】
現代のセルラ・データ・ネットワークでは、ＭＮから基地局への通信は、ベアラ・チャネルを取得するための何らかのシグナリングを必要とし、一度ベアラが取得されると、データがベアラによって送信される。数百のユーザをかかえる典型的なセルの場合、トポロジを発見する目的のためだけに上記のことを実施すると、著しいボトルネックになる恐れがある。
【０００７】
このリソース制約を緩和することができる典型的な方法は、クラスタリングを使用することによるものであり、ＭＮのグループが、クラスタに編成されて、クラスタ・ヘッド（ＣＨ：Cluster Head）が選ばれ、各ＣＨが、クラスタ・トポロジを発見して、これを基地局に伝える。それゆえ、シグナリング・オーバーヘッドが、ＣＨ数に比例し、さらに、データ送信が、多くても前と同じである。原理上では、各ＣＨが、機能、すなわち、（ａ）クラスタ毎にメンバーシップ情報を識別する、または（ｂ）クラスタのトポロジを識別することの少なくとも１つを実施する。しかし、当技術分野の方法は、次善の形でそのような機能を実施している。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国公開特許出願第２０１０／０２９５６５９号
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明は、上記に述べたＣＨ機能の両方を実施する新規な方法を提供する。具体的には、本発明は、ＭＮの二次無線によって形成される基本的なネットワーク・グラフのコンパクトなトポロジ表現を迅速で効率的な形で基地局に伝えるための方法を提供する。
【課題を解決するための手段】
【００１０】
本発明の実施形態では、基地局が、そのセル中の二次無線を備える移動ノードの間でのコンパクトなトポロジを推論することを可能にする、迅速なアルゴリズムが提供される。この方法によって、メンバーシップ情報をほぼ１００ｍｓ以内で収集し、Ｗｉ−Ｆｉ無線でほぼ３００ｍｓ以内に追加のトポロジ情報を移動ノードすべてから収集することが保証される。密なネットワークでは、この時間は、１００ｍｓ以内まで縮めることができる。
【００１１】
さらなる実施形態では、基地局は、いずれもの移動ノードがそのアイデンティティをいずれもの他の移動ノードに明らかにしないで、ネットワークのトポロジを獲得することができる。これは、移動ノードのプライバシーに関して重要な意味を有する。
【００１２】
本発明の教示は、添付図面とともに次の詳細な説明を検討することによって、容易に理解することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の方法を実施することができるワイヤレス・システム構成の概略図である。
【図２】所与のノードのネットワークに関するコンパクトなトポロジ・グラフを例示する図である。
【図３】本発明の方法によって決定されるノードの送信スロットの概略図である。
【図４】本発明の方法によるコンパクトなトポロジ・グラフを計算するためのノードを表す図である。
【発明を実施するための形態】
【００１４】
次の説明では、説明する目的のためであって限定するものでなく、本発明の例示的な実施形態を完全に理解してもらうために、具体的なアーキテクチャ、インターフェース、技法など、具体的な細部を述べる。しかし、本発明は、これらの具体的な細部から逸脱する他の例示的な実施形態の形で、実施することができることは、当業者に明らかなはずである。いくつかの実施例では、良く知られる装置、回路および方法の詳細な記述は、述べる実施形態の記述を不必要な細部のために分かりにくくしないように、省略する。すべての原理、態様および実施形態、さらにまた、その具体的な実施例は、その構造上の、および機能的な同等物の両方を包含すると意図される。さらに、そのような同等物は、現在知られている同等物、ならびに、今後開発される同等物の両方を含むものと意図される。
【００１５】
本発明は、以降、移動ノードのネットワークに関するコンパクトなトポロジ表現を決定するための方法について述べる。ＬＴＥまたは高速パケット・アクセス（ＨＳＰＡ：High Speed Packet Access）などのセルラ・ワイヤレス通信システムに、Ｗｉ−Ｆｉなどの８０２．１１方式に対して二重無線アクセスを有する移動ノードについて、開示する発明を例示的に述べるが、発明の概念は、他のワイヤレス・システムの組み合わせに、または８０２．１１方式に対して単一の無線アクセスだけを有する移動ノードに、どちらかに対して二重無線アクセスを有する移動ノードのネットワークに適用できることは、容易に明らかになるはずである。
【００１６】
本発明の方法の詳細な記述の述部として、図１に示すセルラ・データ・ネットワークを検討し、これは、例示的に、ＬＴＥまたはＨＳＰＡ標準に従って実施することができる。ネットワーク中に多数のセルが存在し、それぞれが基地局の同等物を介してアクセスされ、これは、例示的なＬＴＥ／ＨＳＰＡネットワークの場合、ｅＮｏｄｅＢ（ｅＮＢ）として指定される。ｅＮＢは、シグナリング経路を介して移動性管理事業体（ＭＭＥ：Mobility Management Entity）に接続され、データ経路を介してサービング・ゲートウェイ（ＳＧＷ：Serving Gateway）に接続される。ｅＮＢは、ＭＭＥ／ＳＧＷのペアによって制御され、単一のＭＭＥ／ＳＧＷ複合体が、一般に、たくさんのセルを有する広い地理的領域を代表する。移動ノード（ＭＮ：Mobile Node）は、ネットワークに入ったとき、最初に、それ自体をＭＭＥに登録する（ｅＮＢの適切なものを介して）、それとの制御チャネルを確立する。ＭＮは、データを送るとき、最初に、データを送るためのベアラ・チャネルを取得するために、ｅＮＢに信号を送る必要がある。ｅＮＢ（または別のネットワーク事業体）は、ベアラを割り当てて、ベアラ・チャネルについてＭＮに知らせる。このプロセスは、ＬＴＥネットワーク中で１００ｍｓほどの長さの時間がかかり、およびＨＳＰＡネットワーク中で２秒までかかることがある。本明細書の説明では、ＭＭＥ／ＳＧＷペアは、基地局と呼ぶことにする、というのは、それらは、ＭＮのための制御およびデータ経路の両方のために、単一のロジカル事業体として動作するからであり、また、それらは、ワイヤレス・ローカル・エリア・ネットワーク（ＷＬＡＮ：wireless local area network）セルなど、単一の８０２．１１セルのためのアクセス・ポイントの機能的な同等物を提供するからである。
【００１７】
上記に述べたように、ＭＮは、少なくとも２つの無線を有するマルチ・モード端末として構成され、その無線は、一方がセルラ・ネットワークの基地局に通話するために使用され、他方がＷｉ−ＦｉまたはＷｉＭＡＸなど、８０２．１１ネットワークに対するアクセスのための二次無線として使用される。本明細書の説明では、二次無線は、ＩＥＥＥ８０２．１１標準のファミリーを厳守するＷｉ−Ｆｉ無線であると仮定するが、発明の概念は、そのようには限定されないことを理解されたい。移動ノードは、この二次無線を使用して、Ｗｉ−Ｆｉのアクセス・ポイントと、またはそれらの間で通信することができる。そのように、移動ノードは、ピア・ツー・ピア・モードにあると見なされる。
【００１８】
各基地局は、いずれもの所与の時間に、数百のＭＮを制御し、ＭＮすべてのアイデンティティを知っている、というのは、それらＭＮは、サービスを受けるために、ネットワークに登録する必要があるからである。しかし、基地局は、そのセル中の他のノードに対するＭＮの相対的な位置については、限られた情報だけを有する。アシスト型ＧＰＳ（Ａ−ＧＰＳ：Assisted GPS）または簡素なＧＰＳ（plain GPS）などの技法は、地図上の地理的ロケーションにユーザを置くために使用することができるが、隣接する（互いに対して）２つのノードが、互いに通話することができることを保証することができない。これを行うために、基地局は、この情報を収集して提供するために、ＭＮに頼る必要がある。
【００１９】
用語「リンク」は、本明細書では、２つのＭＮの間のＷｉ−Ｆｉリンクを称する。また、用語「ノード（node）」、「移動体（mobile）」および「ＭＮ（MN）」は、本明細書では、議論中で交換可能に使用されることに留意されたい。
【００２０】
２つのノードの間のリンクは、対称的である。各ノードは、国際移動体装置識別番号（ＩＭＥＩ：International Mobile Equipment Identity）およびＷｉ−ＦｉＭＡＣアドレスからなるＩＤによって一意に識別される。基地局は、移動体すべてのＷｉ−ＦｉＭＡＣアドレスを、登録中にそれらを獲得して、知っている。基地局は、制御チャネル（たとえば、ＨＳＰＡおよびＬＴＥ中のＢＣＣＣＨチャネル）を介して移動体のすべてに同報メッセージを送ることが可能である。また、基地局は、移動体のすべてを同期させるために、タイミング信号を提供し、それゆえ、移動体が、Ｗｉ−Ｆｉインターフェース上で明確に同期すること無く、動作することが可能になる。
【００２１】
全部でＮ個のノードがシステム中に存在し、ノードの密度をρによって示す。干渉域は、データ域の２倍以下であると仮定する。本発明の方法は、ノードが一様に分布することを必要としないし、所与のノードが、すべての他のノードを聞くことができることも必要としない、すなわち、排他的な集団を前提にしない。
【００２２】
本発明の説明では、コンパクトなトポロジ・グラフの観念は、本明細書に定義する。移動ノードの集合を、ネットワーク・グラフＧ＝（Ｖ；Ｅ）の頂点の集合Ｖとして表す。ＭＮの間のリンクの集合は、このグラフの対応する頂点の間の辺の集合Ｅとして表す。
ｕｖ｜ｕｖ∈Ｅ、ｕ、ｖ∈Ｘ
【００２３】
コンパクトなトポロジ・グラフＣＴＧｉ（Ｇ）＝（Ｖ、Ｅｉ）、Ｉ＝１、２、３は、Ｇの重み付けられたサブグラフとして定義される。ノード集合Ｖは、２つの集合Ｘ、Ｙに分割される。ただし、Ｘは、Ｇの支配集合（ＤＳ）であり、Ｙ＝Ｖ＼Ｘである。（グラフ中のすべてのノードが、集合Ｘ中にある、またはＸ中のあるノードに隣接するノードである、そのどちらかである場合、ノードの集合Ｘは、グラフＧの支配集合である）。集合Ｘは、ＧのＤＳであるように選択され、これは、Ｙが、それらに隣接するノードとして支配集合中のノードを有する、Ｇの非支配ノードの集合であることを暗示する。さらに、各ノードには、ｖ∈Ｘ、Ｈ１（ｖ）＝｛ｕ｜ｕｖ∈Ｅ｝が、ｖおよびＨ２（ｖ）＝｛ｕ｜ｕ∈Ｈ１（ｖ）、∃ｗ∈Ｈ１（ｖ）ｓ．ｔ．ｕｗ∈Ｅ｝の１回中継の（one-hop）隣接するノードであると定義される。言い換えると、Ｈ１（ｖ）およびＨ２（ｖ）は、ノードｖ∈Ｘの１回中継および２回中継の（two-hop）隣接するノードを表す。
【００２４】
集合Ｅ１；Ｅ２およびＥ３は、
Ｅ１＝｛ｕｖ｜ｕｖ∈Ｅ、ｕ、ｖ∈Ｘ｝
Ｅ２＝Ｅ１∪｛ｕｖ｜ｕｖ∈Ｅ、ｕ∈Ｘ、ｖ∈Ｙ｝
Ｅ３＝Ｅ２∪｛ｕｖ｜ｕ、ｖ∈Ｅ and ｈＧ（ｕ、ｖ）＝３｝
として定義される。集合Ｅ１およびＥ２中の辺は、重み１を有し、一方集合Ｅ３＼Ｅ２中の辺は、重み３を有して、リンクのエンド・ポイントの間の最小中継回数（minimum hop count）を表す。
【００２５】
グラフＧに関するＣＴＧ２およびＣＴＧ３の実施例を図２に示す。ＣＴＧ２は、Ｇの弱く接続される支配集合（ＷＣＤＳ：weakly connected dominating set）でないことに注目されたい。元のグラフＧが、接続解除された場合、ＣＴＧｉも、また、接続解除される。
【００２６】
支配集合Ｘは、クラスタリング・アルゴリズムによって確立され、そこでは、ノードは、クラスタ・ヘッド（ＣＨ：Cluster-Head）として、それらの近隣で代表的なノードを選出する。このＣＨは、また、支配者（すなわち、ＤＳのメンバ）であり、１、２または３回の中継で別の支配者から離れている。支配ノードの集合が、それらにもっとも近い支配者までの経路を決定し、これらの経路上にノードおよびリンクを加えることができる場合、そのとき、基本的なネットワーク・グラフＧのＣＴＧを構築することができる。
【００２７】
ＭＮから基地局へのベアラ・チャネルを獲得するプロセスが、ＭＮベースで少なくとも１００ｍｓの遅延を含むことを上記に述べた。Ｇ中の各ノードが、ノード・ベースでそのトポロジ情報を伝えようと試みた場合、制御チャネルへの単独でのアクセスを獲得しようと競うと、たとえ伝送容量が高くなくても、基地局のリソースと連携するために、すぐに数秒の時間がかかる恐れがある。したがって、目標は、関連する情報を基地局に転送するために、ＣＨに頼ることである。ＣＨ数が、通常、ネットワーク中のＭＮ数より一桁小さいので、通信オーバーヘッドは、この手法の場合、非常により小さいと予想されることになる。その結果、基地局におけるＣＴＧｉ（Ｇ）の構築は、非常により速く進むことになる。
【００２８】
本発明の方法の一部分として、発明者らは、ネットワーク・グラフのＣＴＧを獲得する、迅速で効率的なアルゴリズムを開発した。本明細書に述べる例示的な実施形態について、より簡単にプレゼンテーションを行うために、ノードによるいずれもの送信が、他に明らかに述べられていない限り、Ｗｉ−Ｆｉインターフェース上にあると仮定する。しかし、本発明の方法の意図する範囲が、そのようなＷｉ−Ｆｉの適用に限定されないことを理解されたい。
【００２９】
本発明のアルゴリズムは、２つの構成要素、すなわち、（ａ）トポロジ発見および（ｂ）トポロジ構築に分けられる。Ｗｉ−Ｆｉリンク上に存在するトラフィックを混乱させないように防止するために、トポロジ発見を、その期間ができるだけ短いように保つ必要がある。また、発見の期間の変動性を回避することが望ましい。
【００３０】
本発明のアルゴリズムは、４つのフェーズで実行され、最初の３つは、トポロジ発見に関し、最後の１つは、トポロジ構築フェーズである。すべてのフェーズは、固定の期間のものであり、移動体の密度によって決定される。アルゴリズムの始めで、基地局が、最初の３つのフェーズの長さ（Ｗ、ｋおよびｋ）、値ｄ、ランダム・シードＲおよびＣＴＧ２またはＣＴＧ３のどちらを発見するのかのその選択を含む同報メッセージをすべてのノードに送る。
【００３１】
第１のフェーズは、クラスタ・ヘッド選択を対象とし（フェーズＺ０とする）、長さがＷスロットであり、各スロットが、８０２．１１中のバック・オフ・スロット（back-off slot）に等しい。ノードは、確率的なスキームに従って、それらに隣接するノードのためにＣＨとして自発的に動作する。このフェーズでは、各ノードが、１つ以下の同報メッセージを送り、その近隣の大きさを知らない。各ノードは、２つの動作の１つが起きたとき、すなわち、（ａ）ノードが送信すること、または（ｂ）ノードが別の送信を漏れ聞くことのうち、どちらかが最初に起きたとき、このフェーズを完了する。
【００３２】
なお、送信が、このフェーズでは衝突することがあるが、プロセスは、最初の送信が、その近隣で起きたとき、各ノードで基本的に終了される。送信した各ノードは、ＣＨの役目を担い、一方送信（成功または衝突）を漏れ聞いたノードは、ＣＨノードにならない。ＣＨノードは、それが送信したスロット番号を書き留める。
【００３３】
アルゴリズムによって実施される第２のフェーズは、１回中継の（one-hop）隣接するノードのリストを獲得することを対象とする（フェーズＺ１とする）。フェーズ１の終わりで、各非ＣＨノードは、ＲＦＩＤタグとの通信を対象とした以前の仕事で発明者ら（および他）の一人によって開発された手法に従って、そのアイデンティティを一意のシグネチャで送出することになる。その手法は、米国公開特許出願第２０１０／０２９５６５９号に詳細に述べられているが、本発明をここで理解するのに十分詳細に、本明細書に要約する。その手法によれば、各非ＣＨノードは、長さｋのスロットのウィンドウＫ中でｄ回まで送信する。ただしｋおよびｄは、基地局によって提供される。各スロットでは、非ＣＨノードは、ビットに相当する１物理層（ＰＨＹ：physical layer）シンボルを送信する。ｄスロットの選択は、ＢＳによって提供されるシード値のランダム・ハッシュおよびノードのＩＤ（ＭＡＣまたはＩＭＥＩ）に基づく。このアイディアは、各ノードが、そのスロット中で隣接するノードと何ら衝突することなしに、送信することができる、少なくとも１つのスロットが存在することを保証することである。ｋおよびｄの値は、２回中継の近隣中のすべてのノードが、それらが送信する唯一のノードになって、高い確率で成功裏に受け取られることになる、少なくとも１つのスロットを有するように選択される。これは、図３に例示する。
【００３４】
各ＣＨノードが、その非ＣＨノードであって隣接するノードのすべての送信をリッスンする。各スロットでは、ＣＨノードは、送信全体のエネルギーを検出し、このスロット中で少なくとも１つの送信があるのか、またはエネルギー閾値に基づいていないのかを決定する。受信されたビットが、実際に復号されないので、隣接していないノードからの干渉が、問題ではない。ＣＨは、長さｋのバイナリ・ビット・ベクトルとして、どのスロットが送信を有し、どのスロットが送信を有していないのかについてログをとり、それをダイジェストΨ１として格納し、これは、ＣＨに隣接するノードすべての符号化として意図される。このアイディアは、以下に詳細に述べる。
【００３５】
この点で、ＣＴＧ２サブグラフを獲得するのに、Ψ１情報から十分にデータを得ており、それを作成するためのトポロジ構築は、アルゴリズムのフェーズ４の説明について以下に述べる。しかし、ＣＴＧ３サブグラフが必要な場合、すぐ下で述べるように、追加の手順が必要になる。
【００３６】
前に述べたように、ｋスロットのウィンドウＫ中に、各非ＣＨノードが、ｄ回まで送信する。ＣＴＧ２サブグラフだけを獲得するために、各スロットは、物理層シンボル長さに同等の持続期間の間、続き、ノードは、そのｄスロット中でシンボルを単に送り、他のスロットではアイドル状態のままに留まる。しかし、ＣＴＧ３サブグラフを決定するために、Ｚ１フェーズ中の非ＣＨノードは、送信と受信のモードの間で切り替わる。したがって、非ＣＨノードのためのスロット持続期間は、最短フレーム送信間隔（ＳＩＦＳ：Short Interframe Space）＋１シンボル長さ（たとえば、８０２．１１ａ／ｇでは２０μｓおよび８０２．１１ｂでは１７μｓ）である。フレームの始めで、すべての非ＣＨノードは、受信機として動作する。スロット中で、非ＣＨノードが送信する必要がある場合、非ＣＨノードは、ＳＩＦＳ間隔中、送信モードに切り替わって、シンボルを送り、受信モードに戻ることになる。すべての他のスロットでは、非ＣＨノードは、上記に述べたＣＨと同じように、それに隣接するノードからのブロードキャストをリッスンすることになる。非ＣＨノードは、一連の送信されたスロット（それ自身のものも含めて）およびアイドル・スロットを検出し、それを、ビット・ベクトルψとして記録することになり、これは、この非ＣＨノードに隣接するノードのすべてを符号化したものとして意図される。
【００３７】
この全体のフェーズが、ネットワーク全体にわたって正確にｋスロット続き、分散した形で行われることに留意することが、重要である。
【００３８】
アルゴリズムによって実施される第３のフェーズは、２回中継の隣接するノードのリストを獲得することを対象とする（フェーズＺ２とする）。フェーズＺ１の終わりで、すべてのノードは、ＣＨが、それらの２回中継の近隣を構築できるようにするフェーズＺ２を開始する。このフェーズは、また、正確にｋスロット続く。ただし、各スロットが、単にデータ・シンボルの持続期間（すなわち、８０２．１１ａ／ｇでは４μｓ）のものであることを除く。このフェーズでは、各非ＣＨノードは、そのψベクトルを、このフェーズ中に単一メッセージとして送信する。ビット・ベクトル中の「１」が、すべて１の物理層データ・シンボルに対応し、一方ビット・ベクトル中の「０」が、送信が無いことに対応する。ＣＨノードは、それに隣接するノードのすべての協調的な送信をリッスンする。上記と同じように、次いで、ＣＨノードは、各スロット中の信号の存在を「１」として、存在しない場合「０」として記録する。長さｋのこのビット・ベクトルは、Ψ２ダイジェストと呼ばれる。
【００３９】
各ＣＨノードでｋシンボルを受信した終わりで、このフェーズは、完了する。各非ＣＨノードは、このフェーズ中に正確に１回（同時に）ブロードキャストする。
【００４０】
フェーズ４は、基地局におけるＣＴＧサブグラフの構築を対象とする（フェーズＺ３とする）。ＭＮが、今まで、何も基地局に全く送信していないことを指摘することが、重要である。トポロジ発見プロセスは、ＣＴＧ２サブグラフに関してＺ１フェーズで終わり、ＣＴＧ３サブグラフに関してＺ２フェーズで終わる。残りのものすべては、基地局が、この情報を使用して、ネットワーク・グラフＧのＣＴＧを構築することである。
【００４１】
前のフェーズの終わりで、各ＣＨノードは、基地局に、次の情報、すなわち、（ａ）その識別子、（ｂ）それがフェーズＺ０中で送信したスロット番号、（ｃ）フェーズＺ１で獲得されたΨ１ダイジェスト、および（ｄ）ＣＴＧ３構築が求められた場合、フェーズＺ２で獲得されたΨ２ダイジェストを送ることに関する情報を送る。基地局は、ネットワーク中のすべてのＭＮの集合を知っているので、各ＭＮｉがＺ１フェーズ中に送信したｄｉスロットの正確な集合を事前に計算することができる。これは、本明細書では、ノード・シグネチャとする。ノードを復号するプロセスは、単に、基地局に登録されたＮノードのそれぞれのシグネチャを調べること、およびこのダイジェストとΨ１（ｖ）およびΨ２（ｖ）とのビットごとのアンド演算を行うことの１つである。その結果がノードのシグネチャである場合、ノードは、Ｈ１（ｖ）およびＨ１（ｖ）∪Ｈ２（ｖ）中にそれぞれ存在するとマークが付けられる。ただし、Ｈ１およびＨ２は、上記に述べている通りである。Ψ１およびΨ２ベクトルが、すべてのノードＮに関して復号された後、次いで、Ｈ２（ｖ）は、後者の集合からＨ１（ｖ）を除去することによって計算することができる。これを使用して、ＣＴＧ２およびＣＴＧ３サブグラフは、計算することができる。
【００４２】
本発明の方法についての追加の細部を次のセクションで提示する。
【００４３】
クラスタ・ヘッド選択−Ｚ０
Ｚ０フェーズの始めで、基地局は、同期信号をすべてのノードに送って、ＣＨ選択プロセスを開始させる。基地局は、各ノードによってノードＩＤとともに使用されるランダム・シードＲを送って、そのランダム・シード発生器を初期化させる。ここで、各ノードｕ∈Ｖは、長さＷのフレーム中でランダムにスロットを選択する（一様分布から）。ノードは、それらのスロット・タイムが来るまで、チャネルをリッスンする。それらノードのスロットが来た場合、それらは、１物理層シンボルとしてランダム文字列を送信し、ＣＨの役目を担う。送信ノードは、このスロット中で送信する他のノードと衝突することがあるが、それらは、それを無視し、このスロット中で衝突するすべてのノードは、ＣＨの役目を担うことになる。
【００４４】
送信を漏れ聞くノードは、それらの１回中継の近隣中のある他のノードがＣＨになったと見なし、したがって、それらの選択アルゴリズムを終了させ、どのノードが、それらのＣＨであるのかを知らない。これは、ノードが衝突を漏れ聞いた場合でも、そうである。本発明の方法のトポロジ発見プロセスの独特な部分は、そもそも、ＣＨまたは基地局がこのＣＨについての情報をノードに利用させるように選ばない限り、ノードが、そのＣＨを知る必要が無いことである。これによって、非ＣＨノードが、その範囲内で多数のＣＨに隣接することが可能になる。
【００４５】
干渉域：ＭＮが、その域の外部にあるいくつかのノードから重複する干渉を漏れ聞き、その近隣にＣＨがあると見なすことができるはずである。本発明の実施形態では、そのように干渉する信号の存在は、有効信号を検出するためのエネルギー閾値をノードで確立することによって、対処することができる。それゆえ、ノードが聞いた信号についての受信された信号強度が一定の閾値より大きい場合、信号は、隣接するノードからのものであると宣言される。この測定は、既存のＷｉ−Ｆｉのチップセット中で使用でき、さらに離れたノードからの干渉の問題に立ち向かうために活用することができる。
【００４６】
ＣＨノードの保守：トポロジが、大幅に変更されない場合、基地局が、ＣＨと同じノードの集合を使用し、トポロジ発見プロセスを繰り返してもらうことは、好ましいことがある。基地局によって提供されるランダム・シードＲを使用すると、このプロセスが支援される。それによって、トポロジが変更されないままである限り（すなわち、新しいノードがネットワーク中に加わらない、既存のノードが退かない、ノードの間に移動性が無い）、同じノードは、再びＣＨになることが保証される。基地局は、ＣＨの異なる集合を望んだ場合、単にランダム・シードＲを変更して、異なる集合を得ることができる。
【００４７】
１回中継の隣接するノードを発見する、Ｚ１
既に述べたように、Ｚ０フェーズの終わりで、各非ＣＨノードは、前のセクション中で述べた手法に従って、一意のシグネチャ中でそのアイデンティティを送出することになり、その手法は、長さｋのスロットのウィンドウ中でｄ回までのノードによる送信に基づく。Ｚ１フェーズでは、基地局は、それが、ＣＴＧ２またはＣＴＧ３を見出したいと望むかどうかを規定し、その評価されるユーザ密度に基づき、ｋおよびｄを規定する。非ＣＨノードは、それらのＩＤとともに、より早期に基地局によって提供されるランダム・シードＲを使用して、サイズｋのフレームからランダムにｄスロットを選択する。各非ＣＨノードは、それが選択するｄスロットのそれぞれ中でランダム・データに相当する８０２．１１物理層シンボルを送信する。なお、このシンボルは、何らプリアンブルの必要が無く、送信できることは留意すべきである。というのは、それが、受信機における信号の同期に影響を与えないからである。実際、ノードは、受信された信号を復号する必要が無いので、同期の疑問は、意味が無い。
【００４８】
ＣＨは、単に、各スロットをリッスンし、このスロット中で、隣接するノードの少なくとも１つによる送信の有無を記録する。やはり、ＣＨは、このスロットを占有されているものとしてマークを付けるために、閾値を超える受信信号を得ることだけが必要である。信号が無い場合、ＣＨは、このスロットを空としてマークを付ける。これによって、既に述べたように、ＣＨが、ビット・ベクトルΨ１中に１回中継の近隣を記録することが可能になる。
【００４９】
非ＣＨノードの振る舞いは、基地局がＣＴＧ２またはＣＴＧ３のどちらを発見したいのかに基づき、異なる。ＣＴＧ２を発見したい場合、非ＣＨノードは、単に送信機として動作し、それによって、スロット長さを、１物理層シンボルの幅にすることが可能になる。ビット完全性を保証するために、追加の１μｓの保護持続期間を、スロットの間に追加することができる。これは、持続期間にほぼ４ｍｓを加えるが、ＣＨにおける伝搬遅延によるビット同期エラーを防止する。
【００５０】
ＣＴＧ３が必要な場合、非ＣＨノードは、送信機および受信機としてのそれらの役目を切り替える必要がある。これは、ＣＴＧ３を獲得するために、各ＣＨノードｕが、その２回中継の近隣Ｈ２（ｕ）を獲得する必要があるからである。これは、Ｈ１（ｕ）中の非ＣＨノードが、それらの１回中継の近隣を知る必要があり、それによって、それらがこれをノードｕに中継することができることを暗示する。それらは、また、それらに隣接するノードが選択しているスロットをリッスンする必要がある。したがって、各スロットが、２つの部分、すなわち、（ａ）送信モードにあるノードが、受信モードに切り替わることを、およびその逆も可能にするＳＩＦＳ持続期間と、（ｂ）非ＣＨノードが送信する／リッスンする物理層シンボル持続期間とに分割される。その結果得られる、非ＣＨノードで記録されるビット・ベクトルｖは、ψ（ｖ）と呼ばれる。このビット・ベクトルでは、ｖによって選択されるｄスロットは、また、１としてマークを付けられる。
【００５１】
２回中継の隣接するノードを発見する、Ｚ２
第２番目のフェーズでは、各非ＣＨノードｖは、ＣＴＧ２を発見するためにフェーズＺ１中でそれらが行うのと同じように、ψ（ｖ）を送出する。ψ（ｖ）中の各１のビットは、データ・シンボルに変換され、０のビットは、送信が無いことによってマークを付けられ、１μｓの保護持続期間が、ダイジェスト中の各ビットを処理する間に挿入される。ＣＨは、この情報を漏れ聞いたとき、それらのψダイジェストをブロードキャストしている、その１回中継の隣接するノードのすべてから聞いている。ウィンドウＫの各スロット中で、ＣＨノードは、送信を検出した場合、このスロットに対応するビットに、Ψ２ダイジェスト中で１としてマークを付け、送信が無い場合、０のビットとしてそれにマークを付ける。
【００５２】
ＣＴＧを計算する、Ｚ３
このフェーズでは、基地局は、Ψ１、Ψ２、さらにまた各ＣＨノードからフェーズＺ０中に送信されたスロット番号を獲得する。
【００５３】
ＣＴＧ１（Ｇ）を構築すること：この方法は、最初に、互いに隣接するそれらＣＨを見出す。これらは、フェーズＺ０中で第１の送信スロット中に衝突していたはずのノードである。それらは、Ｚ０中で同じ送信スロット（tx-slot）番号を有するペアｕ、ｖ∈Ｘを調べ、それらのΨ１ベクトルのビットごとのアンド演算でそれらを比較することによって、識別される。２つのノードの近隣がまばらでない限り、これら２つのベクトルによって表されるＨ１集合の間では、著しく重複することになる。これら２つのノードは、Ψ１（ｕ）が、Ψ１（ｖ）とｄビット位置より非常に小さい、ｂビット位置以下で異なる場合、高い確率で、ＣＴＧ１中の隣接するノードであると考えられる。
【００５４】
ＣＴＧ２（Ｇ）を構築すること：ＣＴＧ２グラフの構築では、ＣＴＧ１グラフが、より多くの辺を用いて増補される。最初に、基地局は、ノードのシグネチャとＣＨによって送られたΨ１ダイジェストに対してビットごとのアンド演算を行い、このシグネチャが、ダイジェスト中に含まれているのかどうかを見る。プロセスは、ブルーム・フィルタ（Bloom filter）と非常に似ている。ノードが、正と識別された場合（すなわち、アンド演算が非ゼロである）、それは、ＣＨノードの１回中継の近隣に加えられる。これは、すべてのＮノードのシグネチャが、ＣＨによって提供されたダイジェストすべてと比較されてしまうまで、繰り返し行われる。すべてのＣＨ（すなわち、ダイジェストを基地局に送るそれら）は、集合Ｘとして示され、そのようにして計算される１回中継の近隣の集合は、Ｈ１（ｕ）∀ｕ∈Ｘ⊆Ｖによって示される。辺が、ｕ∈ＸからＨ１（ｕ）中のすべてのノードに引かれて、ＣＴＧ２を得る。２つのＣＨ、ｕ、ｖ∈Ｘが、Ｈ１（ｕ）∩Ｈ１（ｖ）中にノードを有する場合、それらは、ＣＴＧ２サブグラフ中で接続されることになる。
【００５５】
ＣＴＧ３（Ｇ）を構築すること：ＣＴＧ３（Ｇ）を構築するために、基地局は、Ｇ中で距離が３だけ隔てられているＣＨノードのすべてのペアを見出す必要がある。ＣＴＧ２中のこれらの２つのノードに重み３の辺を加えることによって、ＣＴＧ３が生成される。
【００５６】
ＣＴＧ３の構築は、ＣＴＧ３＝２と設定することによって開始される。ここで、基地局は、ｕによって送られたΨ２ダイジェストを復号することによって、２回中継の非ＣＨノードの近隣Ｈ２（ｕ）、∀ｕ∈Ｘを計算する。これらがＨ１（ｕ）∪Ｈ２（ｕ）を表すことが知られている。各ＭＮのシグネチャをダイジェストと比較して、それが存在するかどうかを見る、前と同じ方法が、適用される。このＨ２（ｕ）から、∀ｕ∈Ｘを計算することができる。
【００５７】
ＣＴＧ２中で接続されていない、いずれもの２つのノードｕ、ｖ∈Ｘについて、基地局は、Ｈ１（ｕ）、Ｈ２（ｖ）を知っている。ここで、基地局は、Ｈ１（ｕ）∩Ｈ２（ｖ）を計算して、ｖから２回中継で離れているが、ｕから１回中継だけで離れている、それらのノードを見出す。これは、図４に例示されている。これを満たす、少なくとも１つのノードが存在する場合、それは、ｈＧ（ｕ、ｖ）＝３であることを暗示し、したがって、重み３の辺が、ＣＴＧサブグラフに加えられる。ＣＴＧ２中のノードの接続解除されたペアのすべてについて、これを繰り返すと、構築が完了する。
【００５８】
３回中継の経路を計算する
ＣＴＧ３中のそれらの間に重み３の辺を有する２つのノードｕ、ｖ∈Ｘでは、Ｇ中でそれらの間に３回中継の最短経路が存在する。ｕとｖの間の少なくとも１つの特定の経路の基地局による識別は、以降、対処する。
【００５９】
基地局は、ノードｘ∈Ｈ１（ｕ）∩Ｈ２（ｖ）およびノードｙ∈Ｈ２（ｕ）∩Ｈ１（ｖ）が存在する、したがってｕ−−ｘ−−ｙ−−ｖの経路が、Ｇ中に存在することを知っている。基地局は、そのアイデンティティが基地局に知られている、Ｈ１（ｕ）∩Ｈ２（ｖ）中のノードｘを調べる。基地局は、ノードｘのシグネチャ、さらにまたΨ２（ｖ）中に表されている、すべてのノードのシグネチャを調べて、Ψ２（ｖ）のどのビットが、一意にｘを表すのかを見出す。ｘをΨ２（ｖ）から復号することができるので、少なくとも１つのそのようなビットの存在が、保証される。基地局は、ノードｖに、このスロット番号を知らせる。次いで、ＣＨノードｖは、このスロット番号をそれに隣接するノードにブロードキャストして、Ｈ１（ｖ）中のいずれかのノードが、それらのψベクトル中に設定された、このスロットに対応するビットを有するのかどうかを問い合わせる。トポロジが変わっていないと仮定すると、少なくとも１つのそのようなノードｙ∈Ｈ１（ｖ）が存在する。ここで、ｙは、ｖを介して、そのＩＤを直接基地局に知らせる、または中継することができる。これによって、基地局が、ＣＴＧ３サブグラフ中のそのようなノードの間の３回中継の最小距離の経路を計算することが可能になる。
【００６０】
以下に、本発明の方法の例示的な適用を述べる。
【００６１】
ネットワーク全体中でノードの集合Ｎを考えると、基地局は、ネットワークの地理的な広がり（すなわち、居住地域）を知っているので、移動体の密度ρを計算することができる。基地局は、この密度に安全マージンを、たとえばそれに３のファクタを乗算することによって、加えることができる。これを前提として、基地局は、２回中継の近隣中の予想されるユーザ数ｍを、たかがｍ２＝π２２＊３ρ＝３７ρとして計算する。１回中継の近隣中では、予想されるユーザ数は、ｍ１＝π＊３ρ＝９．４２ρより小さくなる。
【００６２】
Ｚ０フェーズでは、基地局は、Ｗ＝３＊ｍ１と設定し、一方Ｚ１、Ｚ２フェーズでは、基地局は、ｋ＝２．０８＊ｍ２ｌｎ（Ｎ／ε）と設定する。ただしε＝０．００１である。
【００６３】
フェーズＺ０は、Ｗスロット続く。ただし、各スロットは、８０２．１１中のバック・オフ（back-off）スロットと同じ長さ、すなわち２０μｓである。フェーズＺ２は、ｋデータ・シンボルの送信の持続期間の間、続く。ＩＥＥＥ８０２．１１ａ／ｇでは、シンボル・タイムは、データ・フレーム全体中に１つのシンボルだけがある場合、使用されるビットレートにかかわらず、１０μｓである。フェーズＺ１の長さは、要求されるサブグラフのタイプに応じて変わることができる。ＣＴＧ２だけが要求される場合、Ｚ１は、ｋデータ・シンボルの間、続き、フェーズＺ３は、それに続かない。しかし、ＣＴＧ３が要求される場合、Ｚ１フェーズ中の各スロットは、ＳＩＦＳ＋データ・シンボル持続期間、続き、それは、８０２．１１ａ／ｇでは２０μｓである。
【００６４】
したがって、８０２．１１ａ／ｇ無線を使用すると、ＣＴＧ２を発見するには、（２０Ｗ＋１０ｋ）μｓかかり、ＣＴＧ３を発見するには、（２０Ｗ＋２０ｋ＋１０ｋ）μｓかかる。Ｎユーザが１０ｋｍ２にわたって分布すると仮定した場合、様々なノード密度について、Ｗ、ｋ、ｄの値、さらにまたＣＴＧ２およびＣＴＧ３に関するトポロジ発見時間は、移動体のＷｉ−Ｆｉ域を１００メートルと仮定して、表１に示す。この表では、Ｗ、ｄ、ｋは、スロットであり、一方ＣＴＧ２およびＣＴＧ３を発見するためにかかる時間（それぞれ、Ｔ２、Ｔ３）は、ミリ秒である。
【表１】
0005683723.tif 000002
【００６５】
ノード密度が、ρ＝１０と極めて高い場合でさえ、Ψ１およびΨ２ダイジェストのサイズは、ただｋ＜１２０００ビットであり、それは、１５００バイトである。それゆえ、各ＣＨは、３０００ノードについてのトポロジ発見を支援するために、２つ以下の１５００バイトのパケットを基地局に送る、すなわち、存在するノード当たり１バイトより少ない。トポロジを発見するためにかかる時間は、主にρの関数であり、より広い領域を考えたときでさえ（すなわち、Ｎがより大きい）、大きく変化しない。
【００６６】
ＣＨは、アップリンク・データ・チャネルを使用して、この情報を基地局に送る。これは、各ＣＨノードによってベアラ・チャネルを取得する際、わずかな遅延（ＬＴＥ中でおおよそ１００ｍｓ）があることを暗示する。ＣＨが、ベアラ・チャネルで送信している間、他のＣＨは、同時にアップリンクの制御チャネルを得るように競うことによって、データ・チャネルを取得しようと試みることができ、それによって、ベアラ取得のオーバーヘッドが減少される。ここで、その利点は、基地局に送信するノード数が、ただ小さいことであり、これは、全体のオーバーヘッドを減少させる。
【００６７】
最後に、全体のプロセスの間、ノードが、Ｗｉ−Ｆｉインターフェースによって、どのような識別情報も送信することさえ無いことに、やはり、留意することが、重要である。それゆえ、いずれもの傍受者または他の加入する移動体でさえ、ネットワーク中のいずれもの移動体のアイデンティティを知ることは決してない。基地局だけが、ネットワーク中のすべてのノードを識別することができるようになり、必要に応じて、それを移動体に伝えるかどうかを選ぶことができる。この匿名性の保証が、本発明の方法の独特な面である。
【００６８】
本明細書に、発明者らは、ノード間の通信性能を有する移動端末のネットワークについて、コンパクトなトポロジ・グラフの決定を向上させるためのシステムおよび方法を開示してきた。前述の説明を考慮した当業者に、本発明の多くの修正実施形態および代替実施形態が明らかになるはずである。
【００６９】
したがって、この説明は、単に例示的なものとして解釈すべきであって、本発明を実施する最良の形態を当業者に教示する目的のためのものであり、その可能な形態すべてを例示することは意図されていない。また、使用した言葉は、限定するよりむしろ記述するための言葉であり、構造の細部は、本発明の趣旨から逸脱せずに、実質的に変更することができ、さらに、添付のクレームの範囲内に含まれる、すべての修正実施形態の独占的な使用が留保されることを理解されたい。
【図１】
0005683723.tif 000003
【図２】
0005683723.tif 000004
【図３】
0005683723.tif 000005
【図４】
0005683723.tif 000006