(57)【要約】      （修正有）【課題】ネットワーク内のノードが、最初に、各ノードにおいてクラスターヘッド能力（ＣＨＣ）を求めることによってクラスタリングされる。【解決手段】ＣＨＣは、全てのノードがＣＨＣを受信するまで、直接的又は間接的にブロードキャストされる。各ノードは、ＣＨＣに基づいて１つ又は複数の候補クラスターヘッドを指名し３４０、次に、各ノードにおいて、少なくとも１つのクラスターヘッドが、最大ＣＨＣに基づいて、候補クラスターヘッドノードから選択される。【選択図】図３
2014204436.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内のノードをクラスタリングする方法であって、
前記各ノードにおいて、クラスターヘッド能力（ＣＨＣ）を求めるステップと、
全ての前記ノードが前記ＣＨＣを受信するまで、前記ＣＨＣを直接的又は間接的にブロードキャストするステップと、
前記各ノードにおいて、前記ＣＨＣに基づいて１つ又は複数の候補クラスターヘッドを指名するステップと、
前記各ノードにおいて、最大ＣＨＣに基づいて、前記候補クラスターヘッドノードから少なくとも１つのクラスターヘッドを選択するステップと、
を含む、ネットワーク内のノードをクラスタリングする方法。
【請求項２】
前記ノードは異種のものである、請求項１に記載の方法。
【請求項３】
前記各ノードにおいて、前記ノードｉの近傍ノードｊを含む集合（ＮＢ）を保持するステップ、
を更に含み、前記集合ＮＢ（ｉ）内の各エントリーは、フォーマット（ＩＤ，Ｄ，ＣＨＣ）を有し、ここで、ＩＤは、前記近傍ノードｊの識別子を表し、Ｄは、前記ノードｉと前記近傍ノードｊとの間の距離を表し、ＣＨＣは、前記ノードｊのクラスターヘッド能力を表す、請求項１に記載の方法。
【請求項４】
前記距離Ｄは、
【数１】
2014204436.tif 000008
であり、式中、Ｐ０は、前記送信ノードｊから１メートルにおける受信機電力であり、Ｐｒは、前記ノードｉにおいて測定された電力であり、αは、前記ノードｉと前記ノードｊとの間のチャネルのパス損失指数である、請求項１に記載の方法。
【請求項５】
前記ＣＨＣは、
【数２】
2014204436.tif 000009
であり、式中、Ｃ（ｉ）は、前記ノードｉの能力分類であり、Ｃｍａｘは、最大分類インデックスであり、Ｅ（ｉ）は、前記ノードｉの残りエネルギーの割合であり、ＥＲ（ｉ）は、前記ノードｉが前記クラスターヘッドであるときの該ノードの予想信頼度である、請求項１に記載の方法。
【請求項６】
クラスター形成（ＣＦ）をブロードキャストするステップであって、クラスターマネージャーノードによって前記クラスタリングを開始するステップ、
を更に含む、請求項１に記載の方法。
【請求項７】
前記クラスターマネージャーは、ゲートウェイノードである、請求項６に記載の方法。
【請求項８】
前記クラスターマネージャーは最も高い能力分類を有する、請求項７に記載の方法。
【請求項９】
任意の２つのクラスターヘッド間の距離が、送信範囲の２分の１よりも大きい、請求項１に記載の方法。
【請求項１０】
前記１つ又は複数のクラスターヘッドは、１つの主クラスターヘッドと、１つ又は複数の副クラスターヘッドとを含む、請求項１に記載の方法。
【請求項１１】
前記選択するステップは、前記ネットワーク内の前記全てのノードにわたって分散される、請求項１に記載の方法。
【請求項１２】
前記ノードと前記クラスターヘッドとの間の距離が、送信範囲の２分の１よりも小さい、請求項１に記載の方法。
【請求項１３】
前記クラスターヘッドのいずれも、前記ノードの前記送信範囲の２分の１以内に存在せず、前記ノードは、前記候補クラスターヘッドのうちの１つに、そのノードの前記クラスターヘッドになるように要求する、請求項１２に記載の方法。
【請求項１４】
同じクラスターヘッドを有する全てのノードは、互いからデータを受信することができる、請求項１に記載の方法。
【請求項１５】
前記クラスターヘッドは、該クラスターヘッドを選択した前記ノードと通信するタイムスロットを予約する、請求項１に記載の方法。
【請求項１６】
約３Ｒ／２よりも大きな距離にある任意の２つのノードが同時に通信することができ、Ｒは送信範囲である、請求項９に記載の方法。
【請求項１７】
前記クラスターヘッドを選択する確率は、前記能力分類に基づいている、請求項５に記載の方法。
【請求項１８】
前記クラスは、高い順位から低い順位に、ゲートウェイ、スマートメーターデータコンセントレーター又は工場マシンコントローラー、工場マシン、スマートメーター、大規模センサー、及び小規模センサーに関連付けられている、請求項１に記載の方法。
【請求項１９】
特定のノードが前記候補クラスターヘッドになることを拒否する、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、通信ネットワークに関し、特に、衝突を最小限にするように無線マシンツーマシンネットワーク内の通信デバイス（ノード）をクラスタリングすることに関する。
【背景技術】
【０００２】
マシンツーマシン（Ｍ２Ｍ：Ｍａｃｈｉｎｅ−ｔｏ−Ｍａｃｈｉｎｅ）ネットワークでは、センサー及びスマートメーター等のデバイスが、温度、エネルギー消費、マシン動作、車両テレマティクス等のデータを測定する。測定されたデータは、ネットワーク（無線、有線、又はハイブリッド）を通して、これらのデータを処理するアプリケーションに通信される。日本国の電波産業会（ＡＲＩＢ）、電気通信技術委員会（ＴＴＣ）、米国の電気通信産業ソリューション連合（ＡＴＩＳ）、電気通信産業協会（ＴＩＡ）、中国通信標準協会（ＣＣＳＡ）、欧州電気通信標準協会（ＥＴＳＩ）、韓国の電気通信技術連合（ＴＴＡ）、及び国際標準協力（ＧＳＣ）等の標準開発機構（ＳＤＯ）が、複数のＭ２Ｍアプリケーションにわたる一般的な使用事例及びアーキテクチャ原理を用いてＭ２Ｍ通信のエンドツーエンド仕様を策定しようとしている。
【０００３】
無線Ｍ２Ｍネットワークは、ネットワークトポロジー及びマルチホップ通信の意味において従来のセンサーネットワーク又はアドホックネットワークと類似している。無線Ｍ２Ｍネットワーク内のデバイスは、メッシュネットワーク、スターネットワーク、又は双方を形成することができる。これらのデバイスによって測定されたデータは、ゲートウェイ又はデータコンセントレーターに複数のホップで中継することができる。
【０００４】
しかしながら、Ｍ２Ｍネットワークは、Ｍ２Ｍネットワーク内のデバイスが通常、異種であるという点で従来のネットワークと異なる。パーソナルコンピューター等の幾つかのデバイスは、メモリ、処理能力、電源等の十分なリソースを有する。他方で、温度センサー等の小型デバイスは、リソースが非常に限られている。これらのリソースが制約されたデバイスは、視聴覚データ等の大量のデータを通信することができない。従来のセンサーネットワーク又はアドホックネットワークでは、全てのデバイスは、能力及びリソースが同じであることに関して同種である傾向を有する。通常、センサーデバイスは、限られた量のデータしか送信せず、これによって、ピアデバイスは、データをキューイングし、ゲートウェイ又はデータコンセントレーターに向けて転送することが可能になる。したがって、Ｍ２Ｍネットワーク内のデバイスをクラスタリングすることは、従来のセンサーネットワーク内のデバイスをクラスタリングすることとは異なる。
【０００５】
従来のセンサーネットワーク及びアドホックネットワークのための既存のクラスター方法が存在する。例えば、低エネルギー適応クラスタリング階層構造（ＬＥＡＣＨ：Ｌｏｗ−Ｅｎｅｒｇｙ  Ａｄａｐｔｉｖｅ  Ｃｌｕｓｔｅｒｉｎｇ  Ｈｉｅｒａｒｃｈｙ）と呼ばれる無線マイクロセンサーネットワークのための特定用途向けアーキテクチャは、決定論的方法でクラスターヘッドを選択する。ＬＥＡＣＨプロトコルは、ネットワーク内の全てのデバイス間でクラスターヘッドの役割を分配する。各送信ラウンドにおいて、固定の割合のデバイスがクラスターヘッドとして選択される。クラスター内において、クラスターメンバーは、時分割多重アクセス（ＴＤＭＡ：Ｔｉｍｅ−Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）を用いて、自身のデータをクラスターヘッドに通信する。これによって、デバイスは、データを送信しないとき、スタンバイモードになることが可能になる。しかしながら、ＬＥＡＣＨは、異種のＭ２Ｍデバイス、特に、リソース制約のあるデバイスを用いるＭ２Ｍネットワークには好適ではない。
【０００６】
特許文献１は、無線センサーネットワーク内のクラスターを管理する方法を記載している。クラスターヘッドが、センサーノードから検知データを収集し、この検知データを集約する。マスタークラスターのクラスターヘッドは、集約されたデータをシンクノードに送信し、スレーブクラスターのクラスターヘッドは、集約されたデータをマスタークラスターに送信する。マスタークラスターのクラスターサイズが閾値よりも小さい場合、このマスタークラスターのクラスターヘッドは、このクラスターをスレーブクラスターとして別のマスタークラスターにマージする。マスタークラスターのクラスターサイズが閾値よりも大きい場合、スレーブクラスターのクラスターヘッドは、そのクラスターをマスタークラスターから分離する。この方法は、リンク安定値を求める周期的な発見パケット、クラスターサイズ要求、及び応答パケットを送信することによって大きなオーバーヘッドを含む。この方法は、衝突低減を考慮していない。
【０００７】
特許文献２は、無線ネットワーク内のデバイスをクラスタリングする方法を記載している。そのネットワークは、アクセスポイントと、所定のパラメーターの関数としてクラスターにグルーピングされた複数の計算ユニットとを含む。このクラスターは、クラスターヘッド及び少なくとも１つのクラスターメンバーを含む。クラスターメンバーは、クラスターヘッドと通信するとき、第１の電力レベルを用い、クラスターヘッドユニットは、アクセスポイントと通信するとき、第２の電力レベルを用いる。その方法は、ロケーション情報が利用可能であることを前提としている。Ｍ２Ｍネットワークでは、全てのデバイスのロケーションを取得することは実現可能ではない。その方法の別の限界は、デバイスがマルチ電力レベル送信を行うことができることを前提としている。
【０００８】
特許文献３は、エネルギー消費を最小限にする無線センサーネットワークのためのクラスタリング方法を記載している。その方法は、クラスターヘッドの送信範囲内にある通常ノードの送信範囲内の初期ノードの数を求め、初期ノードの数が最も大きな通常ノードをゲートウェイとして設定する。クラスターヘッドが、データを収集及び集約し、ゲートウェイが、集約されたデータをデータシンクにルーティングする。その方法は、クラスターヘッド及びゲートウェイの数を最小限にするように試みる。なぜならば、これらのクラスターヘッド及びゲートウェイは、通常ノードよりも多くのエネルギーを消費するからである。その方法の１つの不利な点は、通信オーバーヘッドである。データをゲートウェイに送信し、その後、次のクラスターに送信するのではなく、クラスターヘッドがデータを次のクラスターに直接送信する。
【０００９】
特許文献４は、アドホック無線ネットワークにおけるクラスタリングの方法を提供している。その方法は、ノードの集合を境界サイズの最小数の接続されたクラスターに編成し、指定マスター（ｍａｓｔｅｒ−ｄｅｓｉｇｎａｔｅ）及び指定スレーブ（ｓｌａｖｅ−ｄｅｓｉｇｎａｔｅ）を規定する。指定マスターは、データを収集し、指定スレーブは、データをルーティングするようにプロシキスレーブとして選択される。その方法の１つの不利な点は、通信オーバーヘッドである。データをプロシキスレーブに送信し、プロシキスレーブがデータを次のクラスターに転送するのではなく、指定マスターがデータを次のクラスターに直接送信することができる。
【００１０】
デバイスのクラスタリングは、衝突の最小化及び他の目的にも用いることができる。衝突は、パケット損失を引き起こす。失われたパケットは、再送信する必要がある。したがって、パケット損失は、信頼性を減少させるとともに、遅延を増大させる。再送信は、帯域幅使用量及び通信オーバーヘッドを増大させ、さらに、これは、エネルギー消費を増大させ、これによって、バッテリー電源型デバイスの寿命が短くなる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】米国特許第８，０５５，７４０号
【特許文献２】米国特許第７，９６１，６７３号
【特許文献３】米国特許第７，５９０，６１１号
【特許文献４】米国特許第６，８７６，６４３号
【発明の概要】
【発明が解決しようとする課題】
【００１２】
Ｍ２Ｍネットワーク内の送信衝突を最小限にするために、異なるクラスタリング方法が必要とされている。したがって、衝突を最小限にする大規模Ｍ２Ｍネットワークのためのクラスタリング方法を提供することが望ましい。衝突を最小限にすることによって、パケット配信の信頼性を改善することができ、送信遅延を低減することができ、ネットワークスループットを増大させることができる。
【課題を解決するための手段】
【００１３】
本発明の実施の形態は、マシンツーマシン（Ｍ２Ｍ）ネットワーク内のノード間の衝突を最小限にするようにノードをクラスタリングする方法を提供する。本方法は、所定の閾値及び大域パラメーターを何ら用いることなく、Ｍ２Ｍネットワーク内のノードを分散形式でクラスターにグルーピングする。
【００１４】
ノードは、高いクラスのノードほど、低いクラスのノードよりもクラスターヘッドとして選択される確率が高くなるように、それらの能力に基づいて異なるクラスに分類される。
【００１５】
各ノードは、クラスターヘッド能力（ＣＨＣ：Ｃｌｕｓｔｅｒ  Ｈｅａｄ  Ｃａｐａｂｉｌｉｔｙ）を求め、このＣＨＣをブロードキャストする。ノードは、ＣＨＣに基づいて、１つ又は複数の自身の近傍ノードをクラスターヘッド候補として指名し、クラスターヘッド候補は、自身のＣＨＣを、例えば、送信範囲の２分の１以内の近傍クラスターヘッド候補のＣＨＣと比較することによって、その指名を受理又は拒否することができる。非クラスターヘッドノードは、主クラスター及び複数の副クラスターに加わることができる。クラスター内の送信衝突は、各クラスターをクリーク（ｃｌｉｑｕｅ）として形成することによって最小限にされる。このクリーク内では、全てのノードが検出可能である。
【００１６】
近傍クラスター間の送信衝突は、当該近傍クラスター間の協調によって回避される。クラスターヘッドは、そのクラスター内でデータを収集するためのタイムスロット予約を行う。近傍クラスターヘッドは、この予約に肯定応答し、他の時間においてデータを収集する。非近傍クラスターは、データを同時に収集することができる。なぜならば、非近傍クラスター内のノードは、衝突が生じる可能性のない送信範囲外にあるからである。
【００１７】
クラスター内でのデータ収集は、任意のチャネルアクセス方式を用いることができるように、クラスターヘッドによって管理される。クラスターヘッドは、ルーティング方法を用いることによってデータを宛先に転送する。
【図面の簡単な説明】
【００１８】
【図１】本発明の幾つかの実施形態が動作することができるマシンツーマシン（Ｍ２Ｍ）ネットワークの概略図である。
【図２Ａ】本発明の実施形態によるクラスター形成（ＣＦ：Ｃｌｕｓｔｅｒ  Ｆｏｒｍａｔｉｏｎ）パケットの構造のブロック図である。
【図２Ｂ】本発明の実施形態によるクラスターヘッド指名（ＣＨＮ：Ｃｌｕｓｔｅｒ  Ｈｅａｄ  Ｎｏｍｉｎａｔｉｏｎ）パケットの構造のブロック図である。
【図２Ｃ】本発明の実施形態によるクラスターヘッド受理（ＣＨＡ：Ｃｌｕｓｔｅｒ  Ｈｅａｄ  Ａｃｃｅｐｔａｎｃｅ）パケットの構造のブロック図である。
【図２Ｄ】本発明の実施形態によるクラスターメンバー登録（ＣＭＲ：Ｃｌｕｓｔｅｒ  Ｍｅｍｂｅｒ  Ｒｅｇｉｓｔｒａｔｉｏｎ）パケットの構造のブロック図である。
【図２Ｅ】本発明の実施形態によるクラスターメンバー公表（ＣＭＡ：Ｃｌｕｓｔｅｒ  Ｍｅｍｂｅｒ  Ａｎｎｏｕｎｃｅｍｅｎｔ）パケットの構造のブロック図である。
【図３】本発明の実施形態によるクラスター形成のブロック図である。
【図４】本発明の実施形態による主クラスターヘッド及び副クラスターヘッドの選択の一例の概略図である。
【図５】本発明の実施形態によるクラスター内の隠れノードを除去する一例の概略図である。
【図６】２つの近傍クラスターが干渉する可能性がある一例の概略図である。
【図７Ａ】本発明の実施形態によるデータ収集予約（ＤＣＲ：Ｄａｔａ  Ｃｏｌｌｅｃｔｉｏｎ  Ｒｅｓｅｒｖａｔｉｏｎ）パケットのフォーマットを示す図である。
【図７Ｂ】本発明の実施形態による予約肯定応答（ＲＡ：Ｒｅｓｅｒｖａｔｉｏｎ  Ａｃｋｎｏｗｌｅｄｇｅｍｅｎｔ）パケットの構成を示す図である。
【図７Ｃ】本発明の実施形態による予約放棄（ＲＲ：Ｒｅｓｅｒｖａｔｉｏｎ  Ｒｅｌｉｎｑｕｉｓｈ）パケットの構成のブロック図である。
【図８】本発明の実施形態によるクラスター間のデータ収集協調プロセスのブロック図である。
【図９】本発明の実施形態による４つのクラスターを有するＭ２Ｍネットワークにおけるデータ収集の一例のブロック図である。
【発明を実施するための形態】
【００１９】
図１は、本発明の実施形態による異種ノードを有するＭ２Ｍネットワークの一例を示している。デバイスに関連付けられた送受信機（ノード）１００は、コントローラー１１５と通信する。センサーに関連付けられたノード１２０、例えば、スマートメーター１２０は、データをコンセントレーター１２５に送信する。コントローラー１１５及びコンセントレーター１２５は、収集されたデータをゲートウェイ１３０に通信し、このゲートウェイは、コアネットワーク１４０と通信し、さらに、このコアネットワークは、データをアプリケーション１５０と通信する。ノードは、無線リンク１６０若しくは有線リンク１７０、又は双方を介して通信することができる。Ｍ２Ｍネットワークは、種々のトポロジー、例えば、スターネットワーク１８０、又は必要に応じて中継ノード及びルーターノードを有するメッシュネットワーク１９０に編成することができる。
【００２０】
本発明の焦点は、ノード（送受信機）にある。ノードに関連付けられたデバイス、マシン、センサー等のタイプはあまり重要ではない。しかしながら、ほとんどの場合、ノードの能力及び特徴は、ノードに関連付けられたデバイスのタイプに依存する。加えて、ノードは、通常、デバイスと同じ場所に配置された構成要素又は一体の構成要素である。したがって、デバイス及びノードという用語は、本明細書では区別なく用いられる。しかし、通信タスクに関して、主に関係するのはノード（送受信機）である。中継器等の幾つかのノードは送受信機しか備えていないことも理解される。
【００２１】
Ｍ２Ｍネットワークは、種々のタイプ、種々の能力、及び種々のリソースの、数千とまではいかないにしても数百のノードを含むことができる。換言すれば、ネットワークは、異種のものである。例えば、工場には、マシン、パーソナルコンピューター、監視センサー、ゲートウェイ等がある。測定されたデータを用いるアプリケーションは、ノードから遠隔にすることができ、そのため、中継器が必要とされる場合がある。
【００２２】
温度センサー等の幾つかの小型デバイスは、他のデバイス用のデータを中継することができないか、又は長い遅延の後にしかデータを中継することができない。信頼性が低いことも問題である。ゲートウェイ等の幾つかのデバイスは、遅延がなく、高い信頼性でデータを中継することができる。したがって、Ｍ２Ｍネットワーク内のノードをクラスターに編成することと、クラスター内の１つの有能なノードをクラスターヘッド（ＣＨ：Ｃｌｕｓｔｅｒ  Ｈｅａｄ）として選択することとが望ましい。有能なノードは、他のノードからデータを収集するとともに、収集したデータを宛先にルーティングするのに好適な任意のノードとして定義される。
【００２３】
クラスターを有するＭ２Ｍネットワークでは、送信衝突が、近傍クラスター内のノードとの衝突及びクラスター内のノード間の衝突の２つの方法で生じる可能性がある。近傍ノードは、指定された送信範囲内の任意のノードとして定義される。搬送波検知多重アクセス（ＣＳＭＡ：Ｃａｒｒｉｅｒ  Ｓｅｎｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）方式を用いると、衝突は双方の場合に起こり得る。時分割多重アクセス（ＴＤＭＡ）方式は、協調することなくクラスター内の衝突を回避することができるが、ＴＤＭＡは、近傍クラスター内のノードとの衝突を解決するものではない。
【００２４】
クラスター内では、ＴＤＭＡ方式が、衝突がなく、バッテリー電源型ノードにはよりエネルギー効率がよい。ＴＤＭＡは、予測可能なデータ送信量を有するノードのクラスターからデータを収集するのに好適である。クラスターが、異なるタイプのノードを含み、データ要件が経時的に変動する場合、ＣＳＭＡがより実用的な手法である。なぜならば、クラスターヘッドが、ノードのそのようなことに時間予約することは困難であるからである。加えて、分散型クラスターでは、クラスターヘッドであるノードは、経時的に変化する可能性があり、これによって、ＴＤＭＡの時間予約が困難になる。したがって、ＣＳＭＡも、Ｍ２Ｍネットワークにおけるデータ収集に必要とされる。ＣＳＭＡを用いると、送信するデータを有するノードのみが、チャネルアクセスを得るために競合し、クラスターヘッドは、ノードの時間割り当てを行う必要がない。しかしながら、送信衝突は、依然としてＣＳＭＡの問題である。
【００２５】
したがって、Ｍ２Ｍネットワークのための本発明者らのクラスタリング方法は、クラスター内及び近傍クラスター間の衝突の確率を最小限にする。
【００２６】
距離決定を伴う近傍ノード発見
本発明者らのＭ２Ｍネットワーク内の各ノードは、そのノードの近傍ノードを含む集合（ＮＢ）を保持する。最初に、ノードｉが、集合ＮＢ（ｉ）を空に設定する。この集合ＮＢ（ｉ）内のエントリーは、フォーマット（ＩＤ，Ｄ，ＣＨＣ）を有する。ここで、ＩＤは、近傍ノードの識別子を表し、Ｄは、ノードｉから近傍ノードまでの距離を表し、ＣＨＣは、近傍ノードのクラスターヘッド能力を表す。ＣＨＣの決定は、以下で説明する。最初に、ＣＨＣは０である。
【００２７】
ネットワーク起動時、各Ｍ２Ｍノードは、発見パケットを送信する。ノードｉが近傍ノードｊから発見パケットを受信すると、ノードｉは、次のように距離Ｄを求める。
【００２８】
【数１】
2014204436.tif 000003
【００２９】
式中、Ｐ０は、ノードｊから１メートルにおける受信機電力であり、Ｐｒは、ノードｉにおける受信電力であり、αは、ノードｉとノードｊとの間のチャネルのパス損失指数である。距離Ｄ（ｉ，ｊ）が求められた後、ノードｉは、ＣＨＣ（ｊ）＝０を有するエントリー（ｊ，Ｄ（ｉ，ｊ）、ＣＨＣ（ｊ））をＮＢ（ｉ）に追加する。近傍ノード発見後、ノードは、空の近傍ノード集合を有しない。換言すれば、本発明者らのＭ２Ｍネットワークには、隠れノードはない。
【００３０】
デバイス分類及びクラスターヘッド能力評価
センサーネットワーク等の従来の同種ネットワークでは、全てのデバイスは、同様の能力及び機能を有する。デバイスは、同様の量のデータを測定する。データシンクに近いデバイスは、データをこのデータシンクに直接送信することができる。しかしながら、幾つかのデバイスによって測定されたデータは、データシンクに向けて複数のホップを中継する必要がある。また、幾つかのデバイスは、他のデバイスよりも多くのデータを中継する。より多くのデータを中継するデバイスは、より多くのエネルギーを消費する。したがって、従来のクラスター方法は、主として、バッテリー電源型デバイスのネットワーク寿命を延長するためにエネルギー節減に焦点を当てている。
【００３１】
一方、異種Ｍ２Ｍネットワークでは、ＡＶデバイス等の幾つかのデバイスは、建物監視センサー等の他のデバイスよりもはるかに多くのデータを送信する。幾つかのデバイスは、他のデバイスよりも多くのリソースを有する。例えば、ゲートウェイ又はコンセントレーター等のデバイスは、高速のプロセッサ及び大きなメモリを有することができる一方、温度センサー又はスマートメーター等のデバイスは、低速（８ビット）のプロセッサ及び小さな（キロバイトサイズの）メモリを有する。したがって、幾つかのＭ２Ｍデバイスは、クラスターヘッドになることができる一方、他のものはなることができない。
【００３２】
Ｍ２Ｍネットワークは、ゲートウェイ、スマートメーターデータコンセントレーター、スマートメーター、工場マシンコントローラー、マシン、バッテリー電源型建物監視センサー、及びバッテリー電源型室温センサー等を含むことができる。能力に基づいて、本発明者らのＭ２Ｍネットワーク内のデバイスは、異なるクラスに分類することができる。クラスターヘッドになる能力が高いノードほど、能力の低いノードよりも高い分類を有する。例えば、能力分類は、６〜０の整数の範囲にあり、０の能力分類を有するノードは、どの状況の下でもクラスターヘッドになることができない。
【００３３】
クラス５：ゲートウェイは、ネットワーク間でデータを転送することができ、主電源型（ｍａｉｎｓ−ｐｏｗｅｒｅｄ）である（電力グリッドに接続されている）。
【００３４】
クラス４：スマートメーターデータコンセントレーター及び工場マシンコントローラーである。なぜならば、これらは、スマートメーター又はマシンからデータを収集するように設計されているとともに、主電源型でもあるからである。
【００３５】
クラス３：工場マシンである。なぜならば、これらは、通常、マシンコントローラーへの有線接続を有するとともに、主電源型であるからである。
【００３６】
クラス２：スマートメーターは、通常、データ送信に無線リンクを用い、主電源型である。
【００３７】
クラス１：大規模センサー、例えば、建物センサー等は、クラス１のデバイスである。なぜならば、これらは、バッテリー電源型であり、リソースが限られているからである。
【００３８】
クラス０：小規模センサー、例えば、室温センサーは、クラス０のデバイスである。なぜならば、これらは、バッテリー電源型であり、データを中継することできないからである。換言すれば、これらは、クラスターヘッドになることができない。
【００３９】
クラス５及びクラス４のデバイスは、十分な処理能力及びリソースを有するとともに主電源型であるので、クラスターヘッドになることができる。クラス３のデバイスは、それらの適度なリソース及び有線通信接続に起因してクラスターヘッド候補になることができる。クラス２のデバイスは、主電源型であり、十分なエネルギーを有するが、リソースが限られており、無線通信リンクを用い、或る特定の量のデータを中継することができる。クラス１のデバイスは、限られた量のデータしか中継することができない。クラス０のデバイスは、どの状況下でもクラスターヘッドになることができない。
【００４０】
デバイス分類は、デバイスタイプ、デバイス能力、デバイスリソース、デバイス機能、デバイス電源、及びＭ２Ｍネットワークの特徴に依存する。したがって、Ｍ２Ｍデバイスを分類する種々の方法がある。
【００４１】
クラスタリングのために、Ｍ２Ｍノードは、動作して、ＣＨＣをブロードキャストする。以下は、ノードｉの一例示のＣＨＣである。
【００４２】
【数２】
2014204436.tif 000004
【００４３】
式中、ＣＨＣは、分数とすることができ、Ｃ（ｉ）は、ノードｉの能力分類であり、Ｃｍａｘは、最大分類であり、Ｅ（ｉ）は、ノードｉの残りエネルギーの割合であり、ＥＲ（ｉ）は、ノードｉがクラスターヘッドであり、データをルーティングするときのこのノードの予想信頼度である。
【００４４】
上記分類例では、Ｃ（ｉ）は、スマートメーターの場合には２であり、Ｃｍａｘは５である。主電源型デバイスの場合、Ｅ（ｉ）は常に１であり、バッテリー電源型デバイスの場合、Ｅ（ｉ）は、最初は１であり、実際の測定に従って更新される。ＥＲ（ｉ）は、最初は１に設定され、Ｔｓ／Ｔｔに従って更新される。ここで、Ｔｓは、データをルーティングしている間に成功した送信の数である一方、Ｔｔは、データをルーティングしている間の全送信数である。
【００４５】
２つのノードｉ及びｊについて、ＣＨＣ（ｉ）＞ＣＨＣ（ｊ）である場合、ノードｉは、ノードｊよりもクラスターヘッドとして指名されるのに好適である。
【００４６】
クラスター形成パケット
図２Ａ、図２Ｂ、図２Ｃ、図２Ｄ、及び図２Ｅは、クラスタリング用のパケットを示している。
【００４７】
図２Ａは、クラスター形成（ＣＦ）パケット２００のフォーマットを示している。このＣＦパケットは、タイプフィールド、ＩＤフィールド、シーケンス（ＳＱ）、ＣＨＣフィールド、及び追加のオプション用のオプションフィールドを含む。
【００４８】
図２Ｂは、クラスターヘッド指名（ＣＨＮ）パケット２１０のフォーマットを示している。このＣＨＮパケットは、タイプフィールド、ＩＤフィールド、クラスターヘッドとして指名されたノードを識別するＩＤ＿ＣＨフィールド、ＣＨＣフィールド、及びオプションフィールドを含む。
【００４９】
図２Ｃは、クラスターヘッド受理（ＣＨＡ）パケット２２０のフォーマットを示している。このＣＨＡパケットは、タイプフィールド、ＩＤフィールド、ＣＳフィールド、ＭＳフィールド、ＡＴＴフィールド、ＭＴＴフィールド、ＴＮフィールド、ＭＮフィールド、及びオプションフィールドを含む。ＣＳフィールドは、ノードがクラスターヘッドとして動作したときのクラスターサイズを示す。ＣＳフィールドは、最初は０に設定される。ＭＳは、ノードによってサポートされる最大クラスターサイズを表す。ＡＴＴは、ノードがクラスターヘッドであり、収集されたデータをルーティングするときの平均送信時間を表す。ＡＴＴは、最初は０に設定される。ＭＴＴは、ノードがクラスターヘッドとして動作し、収集されたデータをルーティングするときの最大送信時間であり、最初は１に設定される。ＴＮは、ノードによって中継される総バイト数であり、これも最初は０に設定される。ＭＮは、ノードが中継することができる最大バイト数である。
【００５０】
図２Ｄは、クラスターメンバー登録（ＣＭＲ）パケット２３０のフォーマットを示している。このパケットは、タイプフィールド、ＩＤフィールド、（ＣＨ）フィールド、及びクラスターヘッド優先順位（ＣＨ＿Ｐ：Ｃｌｕｓｔｅｒ  Ｈｅａｄ  Ｐｒｉｏｒｉｔｙ）を含む。ＣＨ＿Ｐ＝０である場合、対応するクラスターヘッドは、主クラスターであり、ＣＨ＿Ｐ＝１である場合、対応するクラスターヘッドは、第１の副クラスターヘッドであり、ＣＨ＿Ｐ＝２である場合、対応するクラスターヘッドは、第２の副クラスターヘッドであり、以下、同様である。数ｎは、ノードによって選択されたクラスターヘッドの数を表す。
【００５１】
図２Ｅは、クラスターメンバー公表（ＣＭＡ）パケット２４０のフォーマットを示している。このパケットは、タイプフィールド、ＣＨ＿ＩＤフィールド、ＣＭ＿ＩＤフィールド、及びクラスターサイズＣＳ用のオプションフィールドを含む。
【００５２】
クラスター形成
クラスター形成は、周期的に又はオンデマンドで実行することができる。クラスターマネージャーが、クラスタリングをいつ実行するのかを制御する。任意の主電源型ノードをクラスターマネージャーとして選択することができる。しかしながら、高いクラスのノードほど、その能力及びリソースによって、クラスターマネージャーとして好ましい。各ノードｉは、クラスターシーケンス番号ＳＱ（ｉ）を保持し、この番号は、最初は０に設定される。クラスターマネージャーは、このシーケンス番号を用いて、クラスタリングを開始する。クラスター形成中に、クラスターマネージャーは、インクリメントされたクラスターシーケンス番号を有するクラスター形成（ＣＦ）パケット２００をブロードキャストする。ノードは、以前に受信した任意のＣＦパケットよりも大きなシーケンス番号を有するＣＦパケットを受信したときは常に、クラスタリングに参加する。例えば、ゲートウェイをクラスターマネージャーとすることができる。
【００５３】
図３に示すように、クラスタリングは、所定の閾値も大域パラメーターも一切有することなく分散される。クラスタリングを開始するために、クラスターマネージャー、例えば、ゲートウェイｇは、クラスターシーケンス番号ＳＱ（ｇ）をインクリメントし、ＣＦパケットをブロードキャストする（３２０）。クラスターマネージャーは、最も高い能力分類Ｃ（ｇ）を有し、ＥＲ（ｇ）及びＥ（ｇ）の双方は１に設定される。したがって、ＣＨＣ（ｇ）は、この場合、最大ＣＨＣである１．０である。ノードｇの全ての第１ホップ近傍ノードがＣＦパケットを受信する。
【００５４】
第１ホップのノードは、より大きな値を有するＳＱフィールドを含むＣＦパケットを受信した（３３０）後、受信したＣＨＣを用いて集合ＮＢ内の対応するエントリーを更新し、それ自身のＣＨＣ決定を実行し、そのＳＱを、受信したＣＦパケットに含まれるＳＱに設定し、ＣＦパケットを再ブロードキャストする。例えば、ノードｉは、ゲートウェイｇからＣＦパケットを受信した場合、ＣＨＣ（ｉ）を求め、ＳＱ（ｉ）を１．０に設定し、（ｉ、ＳＱ（ｉ）、ＣＨＣ（ｉ））を含むＣＦパケットをブロードキャストする。ノードは、ＳＱフィールド内の等しい値を含むＣＦパケットを受信した後、このＣＦパケット内のＣＨＣを用いて集合ＮＢ内の対応するエントリーを更新する。
【００５５】
ノードは、全ての近傍ノードからＣＦパケットを受信した後、最大ＣＨＣを有する近傍ノードをクラスターヘッド候補として指名し（３４０）、クラスターヘッド指名（ＣＨＮ）パケット２１０を送信する。クラスターマネージャー、例えば、ゲートウェイｇは、最大ＣＨＣを有するので、自身をクラスターヘッド候補として指名する。
【００５６】
ゲートウェイｇの第２ホップのノードは、第１ホップのノードによって送信されたＣＦパケットを受信した後、これらの第１のノードが行うのと同じクラスターヘッド能力評価及びクラスターヘッド指名プロセスを実行する。このクラスターヘッド指名は、Ｍ２Ｍネットワーク内の全てのノードが指名を行うまで続く。
【００５７】
各ノードは、クラスターヘッド指名プロセスを監視し、クラスターヘッドになることができないノードを除いたクラスターヘッド候補情報を記憶する。クラスターヘッド候補として指名されたノードは、この指名を受理又は拒否する（３５０）。クラスターヘッド候補ノードは、自身のＣＨＣを、送信範囲（Ｒ）の２分の１内にある近傍クラスターヘッド候補のＣＨＣと比較する。クラスターヘッド候補は、最大ＣＨＣを有する場合、指名を受理する。そうでない場合、クラスターヘッド候補は指名を拒否する。クラスターヘッド候補は、指名を受理する場合、クラスターヘッド受理（ＣＨＡ）パケット２２０をブロードキャストする（３６０）。
【００５８】
クラスターヘッド受理ルールに基づくと、任意の２つのクラスターヘッド間の距離は、Ｒ／２よりも大きくなければならない。これによって、クラスターヘッドとして選択されるノードの数が制限される。
【００５９】
クラスターヘッドでないノードは、クラスターヘッド選択（ＣＨＳ：Ｃｌｕｓｔｅｒ  Ｈｅａｄ  Ｓｅｌｅｃｔｉｏｎ）判定基準に基づいて、１つの主クラスターヘッドと、１つ又は複数の副クラスターヘッドとを選択する（３７０）。クラスターヘッドは、分散形式で選択される。必要な共通の閾値は存在しない。ノードは、ローカルな要件に基づいてクラスターヘッドを選択する。異なる判定基準が存在することができる。
【００６０】
例えば、各近傍クラスターヘッドｈについて、非クラスターヘッドノードｉは、次のようにｈ用のＣＨＳを求める。
【００６１】
【数３】
2014204436.tif 000005
【００６２】
式中、ＣＨＣ（ｈ）は式（２）によって与えられ、Ｄ（ｉ，ｈ）はノードｉとノードｈとの間の距離であり、Ｒは送信範囲であり、他のパラメーターは、ノードｈによって送信されたＣＨＡパケットから取得される。Ｍ２Ｍネットワーク内の全てのノードは、同様の送信範囲Ｒを有すると仮定される。
【００６３】
ＣＨＳ（ｉ，ｈ）が０よりも小さい場合、クラスターヘッドｈとノードｉとの間の距離は、Ｒ／２よりも大きく、したがって、ノードｉは、ノードｈを自身のクラスターヘッドとして選択しない。ノードｉは、最大ＣＨＳ（ｉ，ｈ）を有する主クラスターヘッドｈを選択し、これに続くＣＨＳ（ｉ，ｈ）を有する副クラスターヘッドを選択する。ノードｉは、主クラスターヘッド及び副クラスターヘッドを選択した後、クラスターメンバー登録（ＣＭＲ）パケット２３０をブロードキャストする（３８０）。
【００６４】
クラスターヘッドは、自身の近傍ノード集合内のノードによって送信されたＣＭＲパケットを監視し、これらのＣＭＲパケットに含まれる主クラスターヘッドを近傍クラスターヘッドの集合に追加する。
【００６５】
式（３）に基づくと、ノードは、このノードから距離Ｒ／２よりも大きなクラスターヘッドを選択しない。これによって、同じクラスター内の任意の２つのクラスターメンバーが送信範囲Ｒよりも小さな距離を有することが保証される。これによって、隠れノード問題が最小限に抑えられる。
【００６６】
クラスターヘッドｈは、自身の全ての非クラスター近傍ノードからＣＭＲパケットを受信又はオーバーヒアした後、クラスターメンバー公表（ＣＭＡ）パケット２４０をブロードキャストする（３９０）。このパケットは、このクラスターヘッドのクラスター内の非クラスターノードの識別子を含む。
【００６７】
ノードの距離Ｒ／２内にクラスターヘッドが存在しない場合、このノードは、選択されたクラスターヘッドを有しない。このノードは、クラスターヘッド候補として指名されたノードにオーファン要求を送信する。非クラスターヘッドノードは、このオーファン要求を受信した後、このオーファンノード用のクラスターヘッドの役割を実行して、データを収集し、データを中継する。
【００６８】
図４は、２つのクラスターＣ１４１０及びＣ２４２０、並びにクラスターヘッドＣＨ１４３０及びＣＨ２４４０を有する一例示のネットワークを示している。ノードｉ４５０は、クラスターＣ１を自身の主クラスターとして選択し、クラスターＣ２を自身の副クラスターとして選択する。クラスターＣ１は、ノードｉに加えて、他のノード４６０も含む。同様に、クラスターＣ２は、ノードｉに加えて、他のノード４７０も含む。ノードｉは、リンク４８０を介してクラスターヘッドＣＨ１と通信することができ、リンク４９０を介してクラスターヘッドＣＨ２と通信することができる。
【００６９】
隠れノード除去
無線通信では、ノードは、そのパケットがどの別のノードによっても受信することができないとき隠れる。ノードＡは、ノードＢがノードＡから受信することができないが、ノードＣがノードＡ及びノードＢの双方を受信することができる場合、ノードＢから隠れていると言われる。隠れノードは、送信衝突及び再送信を引き起こす可能性がある。衝突回避付き搬送波検知多重アクセス（ＣＳＭＡ／ＣＡ：Ｃａｒｒｉｅｒ  Ｓｅｎｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ  ｗｉｔｈ  Ｃｏｌｌｉｓｉｏｎ  Ａｖｏｉｄａｎｃｅ）方式は、隠れノード問題を解決するものではない。
【００７０】
クラスター内の隠れノードを除去するために、クラスター内のノードの集合は、任意のノードによって送信されたパケットをクラスター内のノードの残りが受信することができるようなクリークを形成する。クラスターヘッドｈについて、以下の場合にのみ、そのクラスター集合Ｃ（ｈ）はクリークであることを示すことができる。
【００７１】
【数４】
2014204436.tif 000006
【００７２】
式中、ＮＢ（ｄ）は、ノードｄの近傍ノード集合である。
【００７３】
実施形態によるクラスタリングを用いると、クラスター内の任意の一対のノード間の距離は、送信範囲Ｒ以下である。したがって、距離の観点から、これらのノードは、互いの送信範囲内にある。
【００７４】
しかしながら、図５に示すように、隠れノード問題は、依然として起こる可能性がある。例えば、放射線不透過性物体５７０は、２つのノード間の通信を遮断することができる。隠れノードが存在しないことを確実にするために、クラスターメンバーノードｉは、その主クラスターヘッド及び副クラスターヘッドからＣＭＡパケットを受信した後、全てのクラスターメンバーが自身の集合ＮＢ（ｉ）に属するか否かを調べる。属していない場合、少なくとも１つのノードがノードｉから隠れている。ノードｉは、その主クラスター内に隠れノードがある場合、隠れノードを有しない副クラスターに切り替えることができる。
【００７５】
図５では、クラスター５００は、クラスターヘッド５１０、クラスターメンバー５２０、５３０、５４０、５５０、及び５６０を含む。しかしながら、クラスターメンバー５２０と５３０との間に放射線不透過性物体５７０がある。したがって、クラスターメンバー５２０は、クラスターメンバー５３０から受信することができない。その結果、クラスターメンバー５３０は、クラスターメンバー５２０の近傍ノード集合には存在しない。クラスターメンバー５２０は、クラスターヘッド５１０からＣＭＡパケット５８０を受信した後、ＣＭＲパケットを再送信する（５９０）ことによって、クラスター５００を自身の副クラスターとして変更する。
【００７６】
データ送信のための近傍クラスター間の協調
２つのクラスターは、一方のクラスター内の任意の送信が他方のクラスター内の送信と干渉するとき、近傍クラスターである。２つのクラスターについて、２つのクラスターヘッド間の距離は、約３Ｒ／２よりも大きく、これらの２つのクラスターは、互いに干渉せず、それらのクラスターは、同じタイムスロット中にデータを同時に通信することができる。しかしながら、２つのクラスターヘッド間の距離が約３Ｒ／２以下である場合、これらの２つのクラスター間に干渉の確率がある。クラスター内の隠れノードを除去することによって、同じクラスター内の衝突は最小限に抑えられる。
【００７７】
しかしながら、図６に示すように、近傍クラスター間の衝突は、協調がない場合、依然として起こり得る。それぞれクラスターヘッドＣＨ１６３０及びＣＨ２６４０を有する２つの近傍クラスターＣ１６１０及びＣ２６２０を考える。各ノードは、送信範囲Ｒ  ６００を有し、クラスターメンバーとそのクラスターヘッドとの間の距離は、Ｒ／２  ６０５以下である。クラスターヘッドＣＨ１とＣＨ２との間の距離はＲよりも小さい。
【００７８】
クラスターＣ１内での送信は、クラスターＣ２内での送信によって干渉される可能性があり、その逆の可能性もある。クラスターＣ１は、２つのメンバー６５０及び６６０を有し、クラスターＣ２は、２つのメンバー６７０及び６８０を有する。ノード６５０とノード６７０との間の距離は、Ｒよりも大きい場合であっても、ノード６７０の送信は、ノード６５０からのクラスターヘッドＣＨ１の受信と干渉する。なぜならば、ノード６７０は、ノード６５０から隠されているからである。同様に、ノード６６０の送信は、ノード６８０からのクラスターヘッドＣＨ２の受信と干渉する。なぜならば、ノード６６０は、ノード６８０から隠されているからである。クラスターＣ１のサイズはＮ１であり、クラスターＣ２のサイズはＮ２であり、送信周期はＴ個のタイムスロットに分割されていると仮定する。２つの近傍クラスターＣ１及びＣ２内のノード間の衝突の確率は、以下の式となることを示すことができる。
【００７９】
【数５】
2014204436.tif 000007
【００８０】
図７Ａ、図７Ｂ、及び図７Ｃに示すように、データ収集予約（ＤＣＲ）パケット７１０、予約肯定応答（ＲＡ）パケット７２０、及び予約放棄（ＲＲ）パケット７３０の３つのタイプのパケットが、クラスター間の協調を達成して近傍クラスター間の干渉を除去するのに用いられる。
【００８１】
図７Ａは、ＤＣＲパケットのフォーマットを示している。タイプフィールドは、パケットのタイプを示す。ＲＳ＿ＣＨ＿ＩＤフィールドは、予約を行うクラスターヘッドの識別子を表す。ＳＥＱは、予約を行うクラスターヘッドによって保持された予約シーケンス番号である。ＲＬフィールドは、予約されたタイムスロットの長さを示す。オプションフィールドは、他の任意のオプションに用いられる。予約は、（ＲＳ＿ＣＨ＿ＩＤ、ＳＥＱ）の対によって一意に識別される。
【００８２】
図７Ｂは、ＲＡパケットのフォーマットを示している。タイプフィールドは、パケットのタイプを示す。ＡＣＫ＿ＣＨ＿ＩＤは、予約に肯定応答するクラスターヘッドの識別子を表す。ＲＳ＿ＣＨ＿ＩＤフィールド及びＳＥＱフィールドは、ＤＣＲパケットのものと同じである。オプションフィールドは、他の任意のオプションに用いられる。
【００８３】
図７Ｃは、ＲＲパケットのフォーマットを示している。タイプフィールドは、パケットのタイプを示す。ＲＳ＿ＣＨ＿ＩＤは、予約を放棄するクラスターヘッドの識別子を表す。ＳＥＱは、ＤＣＲパケットのものと同じ値を有する。オプションフィールドは、他の任意のオプションに用いられる。
【００８４】
図８は、近傍クラスター間のデータ収集協調を示している。クラスター内でデータ収集を開始する（８００）ために、クラスターヘッドは、ＤＣＲパケットを作成及び送信して（８１０）、データ収集用のタイムスロットを予約する。ＤＣＲパケットを作成するために、クラスターヘッドは、ＳＥＱを１だけインクリメントし、ＲＳ＿ＣＨ＿ＩＤを自身のＩＤに設定し、ＲＬを適切な値に設定し、オプションを適切な値に設定する。次に、クラスターヘッドは、ＤＣＲパケットをブロードキャストする。予約側クラスターヘッドの全ての近傍ノードは、このＤＣＲパケットを受信する（８２０）。受信側近傍ノードは、予約側クラスターの主メンバーである場合（８３０）、何も行わない（８３５）（動作なし）。
【００８５】
受信側近傍ノードが、予約側クラスターの主メンバーではなく、別のクラスターのクラスターヘッドである場合（８４０）、この近傍クラスターヘッドは、ＲＡパケットを作成し、予約側クラスターヘッドに送信して（８５０）、予約に肯定応答し、そのクラスター内でのデータ収集を遅延させる。
【００８６】
受信側近傍ノードが、予約側クラスターの主メンバーでなく、他のどのクラスターのクラスターヘッドでもない場合、この近傍ノードは、自身の主クラスターヘッドからのＲＡパケットを待機する。この近傍ノードは、自身の主クラスターヘッドからＲＡパケットを受信した場合（８６０）、何ら動作を行わない（８３５）。一方、近傍ノードは、自身の主クラスターヘッドからＲＡパケットを受信しない場合、ＤＣＲパケット中継プロセスを実行する（８７０）。近傍ノードは、受信したＤＣＲパケットが、自身の主クラスター内の任意の主メンバーによって自身の主クラスターヘッドに中継されたか否かを調べる。
【００８７】
中継された場合、近傍ノードは、何ら動作を実行しない。中継されてない場合、近傍ノードは、ＤＣＲパケットを自身の主クラスターヘッドに送信する。近傍クラスターヘッドは、自身の主クラスターメンバーによって中継されたＤＣＲパケットを受信した（８７２）後、ＲＡパケットを作成し、このＲＡパケットを、ＤＣＲパケットを受信した主クラスターメンバーに返信し（８７４）、自身のクラスター内でのデータ収集を遅延させる。
【００８８】
中継近傍ノードは、自身の主クラスターヘッドからＲＡパケットを受信した後、次に、このＲＡパケットを予約側クラスターヘッドに送信する（８７６）。予約側クラスターヘッドは、全ての近傍クラスターヘッドからＲＡパケットを受信した（８８０）後、クラスター内でのデータの収集を開始する（８９０）。近傍クラスターからの干渉はない。なぜならば、全ての近傍クラスターヘッドは、予約されたタイムスロットの終了まで自身のデータ収集を遅延させているからである。
【００８９】
クラスター内では、データ収集は、クラスターヘッドによって管理される。データは、ＴＤＭＡ若しくはＣＳＭＡ又は他の変調方式を用いて送信することができる。クラスターヘッドは、収集されたデータを集約することができるか又は集約することができない。Ｍ２Ｍネットワーク内のクラスターヘッドは、ルーティング方法を用いて、収集されたデータを宛先にルーティングする。任意の実現可能なルーティングプロトコルを用いることができる。
【００９０】
クラスターヘッドは、必要とされるものよりも多くの時間を予約した場合、ＲＲパケットをブロードキャストすることによって予約を放棄することができる。送信されたＲＲパケットは、ＤＣＲパケットと同じく近傍クラスターヘッドに伝播する。近傍クラスターヘッドは、ＲＲパケットを受信した後、それらのデータ収集を開始することができる。非近傍クラスターは、データを同時に収集することができる。
【００９１】
図９は、ノードがクラスターに編成され、データがクラスター間で協調的に収集されてアプリケーションに通信されるＭ２Ｍネットワークの一例を示している。各ノードは、送信範囲Ｒ９００を有し、クラスターメンバーとそのクラスターヘッドとの間の距離は、Ｒ／２  ９０５以下である。４つのクラスターＣ１９１０、Ｃ２９２０、Ｃ３９３０、及びＣ４９４０が存在する。クラスターヘッドは、それぞれＣＨ１９５０、ＣＨ２９６０、ＣＨ３９７０、及びＣＨ４９８０である。クラスターヘッドＣＨ１が、ＤＣＲパケットをブロードキャストすると、Ｃ１の全ての近傍ノードが、このＤＣＲパケットを受信する。ノード９５５及び９５８等のＣ１の主メンバーは、ＤＣＲパケットを中継しない。近傍クラスターヘッドＣＨ２９６０、並びにノード９６５及び９６８等のＣ２の主メンバーのうちの幾つかがＤＣＲパケットを受信する。
【００９２】
近傍クラスターヘッドＣＨ２は、ＤＣＲパケットを受信した後、肯定応答のためにＲＡパケットをクラスターヘッドＣＨ１に返信する。クラスターＣ２の主メンバーは、それらの主クラスターヘッドＣＨ２によって送信されたＲＡパケットを受信し、したがって、ＤＣＲパケットを中継しない。近傍クラスターヘッドＣＨ３９７０は、ＣＨ１の送信範囲外にあるので、ＤＣＲパケットを受信することができない。しかしながら、クラスターＣ３の主メンバー９７３及び９７６の２つは、ＤＣＲパケットを受信する。Ｃ３の主メンバー９７３及び９７６は、それらの主クラスターヘッドＣＨ３からのＲＡパケットをオーバーヒアしないので、メンバー９７３及び９７６のうちの一方のみが、ＤＣＲパケット中継プロセスを実行し、ＣＨ３によって送信されたＲＡパケットをクラスターヘッドＣＨ１に中継する。近傍クラスターヘッドＣＨ２及びＣＨ３は、ＤＣＲパケットを受信した後、自身のデータ収集を遅延させる。
【００９３】
予約側クラスターヘッドＣＨ１は、全ての近傍クラスターヘッドからＲＡパケットを受信した後、クラスターＣ１内でデータ収集を開始する。クラスターヘッドＣＨ４９８０及びメンバー９８５等のＣ４の全ての主メンバーは、クラスターヘッドＣＨ１によって送信されたＤＣＲパケットを受信しない。したがって、クラスターＣ４及びクラスターＣ１は、それらのクラスター用にデータを同時に収集することができる。データが収集された後、クラスターヘッドＣＨ１は、収集されたデータを経路９９０に沿ってコアネットワーク１４０にルーティングする。このコアネットワークは、次に、データをアプリケーション１５０に通信する。また、ノード９５８は、その主クラスターヘッドとしてＣＨ１を選択し、そのバックアップクラスターヘッドとしてＣＨ２を選択する。同様に、ノード９６８は、その主クラスターヘッドとしてＣＨ２を選択し、その副クラスターヘッドとしてＣＨ１を選択する。
【図１】
2014204436.tif 000010
【図２Ａ】
2014204436.tif 000011
【図２Ｂ】
2014204436.tif 000012
【図２Ｃ】
2014204436.tif 000013
【図２Ｄ】
2014204436.tif 000014
【図２Ｅ】
2014204436.tif 000015
【図３】
2014204436.tif 000016
【図４】
2014204436.tif 000017
【図５】
2014204436.tif 000018
【図６】
2014204436.tif 000019
【図７Ａ】
2014204436.tif 000020
【図７Ｂ】
2014204436.tif 000021
【図７Ｃ】
2014204436.tif 000022
【図８】
2014204436.tif 000023
【図９】
2014204436.tif 000024
【外国語明細書】
2014204436.tif 000025
2014204436.tif 000026
2014204436.tif 000027
2014204436.tif 000028
2014204436.tif 000029
2014204436.tif 000030
2014204436.tif 000031
2014204436.tif 000032
2014204436.tif 000033
2014204436.tif 000034
2014204436.tif 000035
2014204436.tif 000036
2014204436.tif 000037
2014204436.tif 000038
2014204436.tif 000039
2014204436.tif 000040
2014204436.tif 000041
2014204436.tif 000042
2014204436.tif 000043
2014204436.tif 000044
2014204436.tif 000045
2014204436.tif 000046
2014204436.tif 000047
2014204436.tif 000048
2014204436.tif 000049
2014204436.tif 000050
2014204436.tif 000051
2014204436.tif 000052
2014204436.tif 000053
2014204436.tif 000054
2014204436.tif 000055
2014204436.tif 000056
2014204436.tif 000057
2014204436.tif 000058
2014204436.tif 000059
2014204436.tif 000060
2014204436.tif 000061
2014204436.tif 000062
2014204436.tif 000063
2014204436.tif 000064
2014204436.tif 000065
2014204436.tif 000066