(57)【要約】【課題】ゲートウェイを存在させないことにより、メンテナンスアルゴリズムを簡略化し、バックボーン木のサイズを減少でき、ブロードキャストの効率化を実現するネットワーク構築方法を提供する。【解決手段】一つのヘッドとヘッド以外のノードであるメンバとを含む連結双方向グラフの部分グラフであるクラスタを利用したネットワーク構築方法であり、連結双方向グラフのバックボーンツリーは、ヘッドのみで構成され、ヘッドの集合は、独立点集合を構成せず、連結支配点集合を構成し、ネットワークへ参加する参加ノードが、当該参加ノードに隣接する隣接ノードから受信したステータスに応じて、参加ノード自身のステータスを決定するステップと、隣接ノードが、決定された参加ノードのステータスに応じて、隣接ノードのステータスを更新するステップとを含む。【選択図】図６
2007306135.tif 000002
【特許請求の範囲】
【請求項１】
一つのヘッドとヘッド以外のノードであるメンバとを含む連結双方向グラフの部分グラフであるクラスタを利用したネットワーク構築方法であって、
前記連結双方向グラフのバックボーンツリーは、ヘッドのみで構成され、
前記ヘッドの集合は、独立点集合を構成せず、連結支配点集合を構成し、
ネットワークへ参加する参加ノードが、当該参加ノードに隣接する隣接ノードから受信したステータスに応じて、前記参加ノード自身のステータスを決定するステップと、
前記隣接ノードが、前記決定された参加ノードのステータスに応じて、前記隣接ノードのステータスを更新するステップと
を含むことを特徴とするネットワーク構築方法。
【請求項２】
前記参加ノードは、２−ホップまでの隣接ノードからステータスを受信し、２−ホップまでの隣接ノードへ参加ノード自身のステータスを送信することを特徴とする請求項１に記載のネットワーク構築方法。
【請求項３】
ネットワークから離脱する離脱ノードが、当該離脱ノードに隣接する隣接ノードに離脱メッセージを送信ステップと、
前記離脱ノードがメンバである場合、前記離脱ノードはネットワークから離脱するステップと
を更に含むことを特徴とする請求項１又は２に記載のネットワーク構築方法。
【請求項４】
前記離脱ノードがメンバでなく、クラスタネットワークの根でない場合、
前記離脱ノードを根とする第１の部分木と、前記クラスタネットワークの根を根とする第２の部分木とに分かれるステップを更に含むことを特徴とする請求項３に記載のネットワーク構築方法。
【請求項５】
前記離脱ノードがメンバでなく、クラスタネットワークの根である場合、
前記離脱ノードの隣接ノードが有る場合、当該隣接ノードの一つを前記クラスタネットワークの新たな根とし、
前記離脱ノードの隣接ノードが無い場合、２−ホップの隣接ヘッドの一つを前記クラスタネットワークの新たな根とすることを特徴とする請求項３に記載のネットワーク構築方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク構築方法に関する。
【背景技術】
【０００２】
無線ネットワークは、無線でメッセージの送受信が可能なデバイス（以下において、「ノード」という。）の集合で構成されるネットワークである。
【０００３】
近年、インフラを追加することなく、無線で通信を行う多くの自律的なノードからなる自己組織化マルチホップ無線ネットワークへの関心が高まっている。
【０００４】
無線ネットワークのノードが物理的に展開された後、フラットなネットワークが形成され、そこではお互いの通信範囲内に入っているノードの間にリンクが存在する。このようなフラットなネットワークトポロジーにおいては、各ノードの効率的な通信を可能とする確立した構造は存在しない。
【０００５】
ところで、クラスタリングは、このフラットなネットワークトポロジーに階層的な組織化を提供するための手段として考えられている。基本的なアイデアは、ネットワークをクラスタと呼ばれる小規模のネットワークに分割することである。各クラスタ内は物理的に隣接しており、クラスタヘッド（以下において、「ヘッド」という。）と呼ばれるノードによって簡単に管理される。続いて、クラスタ間の通信を提供する構造を持つバックボーンが構築される。構築されたネットワークは、「通信オーバーヘッドの最小化」、「データの収集点の選択」、「エネルギー消費量の最小化」のような望ましい性質を有する。
【０００６】
ここで、移動性と拡張性を考慮すると、存在するネットワークに対し、ノードの離脱とノードの参加のような操作が必要である。固定ノードでさえ、バッテリーが減少した場合は、離脱してチャージモードに入らなければならない。そして、チャージしたノードは、再びネットワークに参加する。ゆえに、一度階層的なクラスタリングが確立されたら、ネットワークトポロジーの変化に対し、クラスタ機構のメンテナンスが重要となる。
【０００７】
フラットなネットワークに対する分散的なクラスタリングに関しては、多くの論文で議論されてきた。これまでの多くは、階層的なクラスタリングの確立に対しての研究であり、同様のシナリオの下でのクラスタ構造のメンテナンスに関しての研究は、あまり行われていなかったが、この無線ネットワークのクラスタ構造のメンテナンスに重きをおいた研究が開示されている（例えば、非特許文献１及び２参照。）
非特許文献１及び２では、ネットワークトポロジーが動的に変化する無線ネットワークを考え、クラスタ構造維持のためのnode-move-inとnode-move-outを呼ばれる二つの操作が定義された新たなクラスタ構造を提案した。これは、以下のようなネットワークモデルに基づいている。
【０００８】
各ノードは異なるＩＤを持ち、同期した各単位時間において、メッセージを受信又は送信し、衝突検知機能無しで一つの無線チャネルを用いる。フラットネットワークＧの各ノードは、それぞれ独立なクラスタにグループ化され、バックボーンはヘッドとゲートウェイノード（以下において、「ゲートウェイ」という。）からなる。ゲートウェイは、ヘッドをつなぐために用いられる。更に、バックボーンとクラスタとを結合することで、Ｇの全域木となり、この木はクラスタベースネットワークＣＮｅｔ（Ｇ）と呼ばれる。Ｇのノード数をｎ、このクラスタリングによるクラスタの数をｐとし、以下のＣＮｅｔ（Ｇ）の持ついくつかの新しい性質が認められる。
【０００９】
（１）バックボーンは、高々２ｐ−１のノードからなる
（２）ｐは、独立完全部分グラフの最小数以下であり、Ｇが密な場合、ｐ＜＜ｎ
（３）Ｇ上のブロードキャストは、バックボーンを介してＯ（ｐ）時間で行われる（フラットなネットワークにおいては少なくともΩ（ｎ）時間が必要）
（４）Ｇがunit disk graphならば、ｐ≦５×|ＭＤＳ|
【非特許文献１】Jiro uchida, Islam.A.K.M.Muzahidul, YoshiakiKatayama, Wei Chen and Koichi Wada, “Construction and Maintenanace of a Cluster-based Architecture for Sensor Networks”, Hawaii International Conference on System Sciences(HICSS), 2006.
【非特許文献２】宮永慎太郎、「効率の良い統合・分離が可能な動的クラスタネットワーク構築アルゴリズムに関する研究」、名古屋工業大学  電気情報工学科、２００６年卒業論文（2006.02.10提出）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述した非特許文献１及び２の手法においては、端末の種類がヘッド、ゲートウェイ、メンバの３種類であるが、ゲートウェイは、クラスタ内においてはメンバと同等であり、バックボーン木において、ヘッド間を接続するためにのみ使用されている。
【００１１】
しかしながら、従来の手法では、バックボーン木を連結にするために、ゲートウェイ無しには構築ができない。
【００１２】
又、端末の種類が３種類になることにより、端末の出現によるクラスタネットワークの拡大と端末の消失によるネットワーク分離のネットワークの維持に必要なアルゴリズムが複雑になっていた。
【００１３】
更に、バックボーン木において、ヘッドの連結性を保つために用いられているゲートウェイをなくすことができれば、バックボーン木のサイズを減少でき、ひいてはブロードキャストの効率化につながるが、従来の手法においては、それを取り除く手法は分かっていない。
【００１４】
そこで、本発明は、上記の課題に鑑み、ゲートウェイを存在させないことにより、メンテナンスアルゴリズムを簡略化し、バックボーン木のサイズを減少でき、ブロードキャストの効率化を実現するネットワーク構築方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明の特徴は、（ａ）一つのヘッドとヘッド以外のノードであるメンバとを含む連結双方向グラフの部分グラフであるクラスタを利用したネットワーク構築方法であって、（ｂ）連結双方向グラフのバックボーンツリーは、ヘッドのみで構成され、（ｃ）ヘッドの集合は、独立点集合を構成せず、連結支配点集合を構成し、（ｄ）ネットワークへ参加する参加ノードが、当該参加ノードに隣接する隣接ノードから受信したステータスに応じて、参加ノード自身のステータスを決定するステップと、（ｅ）隣接ノードが、決定された参加ノードのステータスに応じて、隣接ノードのステータスを更新するステップとを含むネットワーク構築方法であることを要旨とする。
【００１６】
本発明の特徴に係るネットワーク構築方法によると、ゲートウェイを存在させないことにより、メンテナンスアルゴリズムを簡略化し、バックボーン木のサイズを減少でき、ブロードキャストの効率化を実現することができる。
【００１７】
又、本発明の特徴に係るネットワーク構築方法において、参加ノードは、２−ホップまでの隣接ノードからステータスを受信し、２−ホップまでの隣接ノードへ参加ノード自身のステータスを送信してもよい。
【００１８】
このネットワーク構築方法によると、参加ノードの２ホップ隣接ノードのみで、局所的に参加操作が可能となる。
【００１９】
又、本発明の特徴に係るネットワーク構築方法は、ネットワークから離脱する離脱ノードが、当該離脱ノードに隣接する隣接ノードに離脱メッセージを送信ステップと、離脱ノードがメンバである場合、離脱ノードはネットワークから離脱するステップとを更に含んでもよい。
【００２０】
このネットワーク構築方法によると、ネットワークからの離脱においても、メンテナンスアルゴリズムを簡略化することができる。
【００２１】
又、上記の特徴に係るネットワーク構築方法は、離脱ノードがメンバでなく、クラスタネットワークの根でない場合、離脱ノードを根とする第１の部分木と、クラスタネットワークの根を根とする第２の部分木とに分かれるステップを更に含んでもよい。
【００２２】
又、上記の特徴に係るネットワーク構築方法は、離脱ノードがメンバでなく、クラスタネットワークの根である場合、離脱ノードの隣接ノードが有る場合、当該隣接ノードの一つをクラスタネットワークの新たな根とし、離脱ノードの隣接ノードが無い場合、２−ホップの隣接ヘッドの一つをクラスタネットワークの新たな根としてもよい。
【発明の効果】
【００２３】
本発明によると、ゲートウェイを存在させないことにより、メンテナンスアルゴリズムを簡略化し、バックボーン木のサイズを減少でき、ブロードキャストの効率化を実現するネットワーク構築方法を提供することができる。
【発明を実施するための最良の形態】
【００２４】
次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には、同一又は類似の符号を付している。ただし、図面は模式的なものであることに留意すべきである。
【００２５】
本実施形態では、非特許文献１で提案されているアーキテクチャ（以下において、「アーキテクチャＣ」という。）が持つ望ましい性質を維持しつつ改良を加え、タスクの完了時間、メンテナンスの簡略化などの面において、よりよい性質を持った三つのアーキテクチャ及びそのメンテナンスのためのアルゴリズムを提案する。
【００２６】
一つ目のアーキテクチャをＭと呼ぶ。Ｃにおいては、既存の一つのクラスタネットワークに対するノードの参加／離脱のみを扱っており、ノードの参加による複数のクラスタベースネットワークの統合や、ノードの離脱によるクラスタベースネットワークの分離については考えていない。又、統合を行うにしても提案されている構図ではノード数に対して線形時間が必要となる場合が存在した。しかし、Ｍにおいては、この統合と分離のより高速な実現が可能となっている。
【００２７】
二つ目のアーキテクチャをＩでは、ヘッドとゲートウェイの区別を無くし、統合／分離において、より柔軟な対応が可能となり、その実行時間もＭと同等の高速化が図られている。又、ヘッドとゲートウェイの区別を無くしたことにより、ＣＮｅｔ（Ｇ）のメンテナンスのためのアルゴリズムがより簡略化される利点を持つ。
【００２８】
最後のアーキテクチャＵでは、Ｉを踏襲しつつ、若干の変更を加えることで、バックボーン木ＢＴ（Ｇ）のサイズを減少させ、ブロードキャストをより高速に実行可能であることをシミュレーションにより確認した。
【００２９】
本実施形態に係るクラスタリングにおいては、ＣＮｅｔ（Ｇ）が確立されたとき、各ノードは自身から１−ホップ（ＢＴ（Ｇ）、ＣＮｅｔ（Ｇ）、Ｇのそれぞれの隣接ノード）の情報のみを保持する。ＣＮｅｔ（Ｇ）の確立方法は、全トポロジー情報をあるノードに集め、そこで確立する静的な方法と、すべての情報を集めることなく、各ノードが局所的に確立する方法とがある。動的な方法では、Ｏ（ｎ）時間でＣＮｅｔ（Ｇ）を確立することが可能である。ノードがＧに参加、又は、Ｇから離脱するとき、参加／離脱の操作は、もとの性質を維持したまま、Ｇ上のクラスタ構造をメンテナンスする。本実施形態において提案するこれらの操作のためのアルゴリズムを及びそれらによって維持される性質を持つアーキテクチャを図１に示す。
【００３０】
非特許文献１と同様に、本実施形態に係るアルゴリズムは、無線ネットワークのクラスタリング構造の維持という点に重きをおいている。クラスタリングを行うため、過去のアルゴリズムを用いることができるが、各ノードがどのような情報を持っているかを調べる必要がある。
【００３１】
（用語の定義）
本実施形態で用いる用語は、以下のように定義する。又、ここでは、有向グラフをＧ＝（Ｖ，Ｅ）とする。
【００３２】
双方向グラフ：任意の辺（ｕ，ｖ）∈Ｅに対し、（ｕ，ｖ）が存在するならば、Ｇは双方向グラフである。
【００３３】
強連結成分：任意の二つの異なるノードｕ，ｖに対し、少なくとも一つのｕからｖへのパスが存在する有向グラフは、強連結であるという。Ｇの強連結成分Ｃは、ＧのどのノードをＣに加えてもＣが強連結でなくなるようなＧの部分グラフＣ＝（Ｖ’，Ｅ’）（Ｖ’⊆Ｖ，Ｅ’⊆Ｅ）である。
【００３４】
誘導部分グラフ：グラフＧ＝（Ｖ，Ｅ）に対して、Ｖ’⊆ＶかつＥ’＝｛（ｉ，ｊ）｜ｉ，ｊ∈Ｖ’，ｉ，ｊ∈Ｅ｝となるグラフＧ’＝（Ｖ’，Ｅ’）のことをＶ’によって誘導された部分グラフをいい、Ｇ[Ｖ’]で表す。
【００３５】
独立点集合：Ｕに含まれるどのノードもＧにおいて隣接していないようなＶの部分集合ＵをＧの独立点集合という。
【００３６】
最大独立点集合（ＭＩＳ）：Ｇをどのノードに加えても独立点集合でなくなるような独立点集合Ｉ。
【００３７】
支配点集合：ＧのどのノードもＤ又はＤの隣接ノードに含まれるようなＶの部分集合Ｄ。
【００３８】
木：すべての双方向の辺を無向辺に置き換えたときにサイクルが存在しないような連結双方向グラフ。
【００３９】
単位円グラフ：各辺（ｕ，ｖ）∈Ｅに対し、ノードｕとｖの間のユークリッド距離が高々１であるとき、Ｇを単位円グラフという。
【００４０】
双方向グラフは無向グラフとして扱うことができるので、本実施形態に係るネットワークは、無向グラフで表し、図や用語もそれに従うものとする。例えば、強連結成分→連結成分とする。
【００４１】
又、本実施形態に係る無線ネットワークＧのモデルは、以下のとおりである。
【００４２】
・ノードは、ラウンドと呼ばれる一定の時間間隔ごとに動作状態を決定する。各ラウンド内における動作状態は、送信又は受信のどちらかである。各ラウンドにおいて、各ノードは送信機又は受信機のいずれか一方として動作する。
【００４３】
・各デバイスのラウンドは同期している。即ち、各ラウンドの開始と終了の時刻が一致している。
【００４４】
・各ラウンドにおいて、各ノードは、その隣接ノードのうちただ一つのノードのみが送信したとき、かつ、そのときのみに限り、そのラウンドにおいてメッセージを受信することができる。二つ以上の隣接ノードが送信した場合、衝突が起こり、どのメッセージも受信されない。
【００４５】
・ノードは、衝突が起きたかどうかを判別することはできない。つまり、衝突検知能力を持たない。
【００４６】
・ 各ノードは、それぞれ異なる自身のＩＤを知っている。
【００４７】
（基本構造及び基本構造におけるブロードキャスト）
まず、非特許文献１及び２における既存のアーキテクチャ及び本実施形態に係る三つのアーキテクチャに共通の基本構造と、その構造のもとにおけるブロードキャストについて説明する。
【００４８】
基本構造について、図２を用いて説明する。連結双方向グラフをＧ＝（Ｖ，Ｅ）とする。各ノードには、それぞれステータスと呼ばれるある役割が割り当てられる。Ｇの支配点集合を構成するノードをヘッドといい、一つのヘッドとヘッド以外のノードからなるＧの部分グラフをクラスタという。ヘッド以外のノードはメンバと呼ばれ、各クラスタにおいて、ヘッドはメンバと辺で結ばれており、メンバ間には辺は存在しない。クラスタはヘッドを中心とするＧのスター部分グラフとなる。又、すべてのヘッドはそれぞれ一つのクラスタを形成し、複数のクラスタに属するノードは存在しない。
【００４９】
すべてのヘッドを含むＧの部分木をバックボーンツリーＢＴ（Ｇ）と呼ぶ。Ｇは連結双方向グラフなので、バックボーンツリーは必ず存在する。又、バックボーンツリーに含まれないノードは、すべてメンバとしていずれかのクラスタに属する。
【００５０】
バックボーンツリーはＧにおける高速な通信路として考えられる。メンバをｕ，ｖとし、それらのヘッドをｈu，ｈvとする。ｕがｖへメッセージを送りたい場合、まずｕは自身のヘッドｈuにメッセージを送信する。ｈuはＢＴ（Ｇ）を経由して、ｈvへメッセージを送り、ｈvは自身のメンバｖにメッセージを送信する。
【００５１】
このバックボーンツリーにより各クラスタをつなぎ、構造化されたネットワークを構成する。Ｇ＝（Ｖ，Ｅ）に対し、一つのヘッドを根とした根付き木ＣＮｅｔ（Ｇ）＝（Ｖ，ＥBT(G)∪ＥC）をクラスタベースネットワークと呼ぶ。ここで、ＥBT(G)はバックボーンツリーの、ＥCはすべてのクラスタの辺の集合を表す。ＣＮｅｔ（Ｇ）はＧの全域木となっている。
【００５２】
以下に、フラットなグラフからＣＮｅｔ（Ｇ）へと組織化・維持を行う方法を示す。そのアルゴリズムを説明する前に、まずＣＮｅｔ（Ｇ）に対するデータ構造を定義する。
【００５３】
ＣＮｅｔ（Ｇ）は、１．クラスタの集合、２．各クラスタをつなぐためのバックボーンツリーという、２レベルの構造を持つ。又、Ｇの各ノードｖは、参加／離脱が行われる毎に以下の情報を維持することで、ＣＮｅｔ（Ｇ）を構成するものとする。
【００５４】
・v.stat：ｖのステータス
・v.prt, v.chd：ＣＮｅｔ（Ｇ）におけるｖの親のＩＤ及びｖの子のＩＤ集合。根ｒに対しては、r.prt=⊥、子を持たないノードｍに対しては、m.chd=空集合
・v.oneigh：v.prt, v.chdを除く、Ｇ上のｖの隣接ノードのＩＤ集合
・ v.rootID：ｖが属するＣＮｅｔ（Ｇ）の根のＩＤ
又、ｖは、自身が知っている隣接ノードのステータスをＩＤと対にして保持する。
【００５５】
以下、ｖのＧ上の隣接ノードを表す記号としてv.neighを、ＢＴ（Ｇ）上の隣接ノードを表す記号としてv.bneighをそれぞれ用いる（これらは、v.prt、v.chd、v.oneighから導かれる）。
【００５６】
上記の情報をtotal 1-hop dataと呼ぶ。各ノードに対し、これらの情報が維持されているとき、Ｇは、total 1-hop dataで組織化されているという。
【００５７】
ここで、ＣＮｅｔ（Ｇ）における二つの操作、参加と離脱について以下に定義する。
【００５８】
・参加：新たに加わるノードｖは、既存のＣＮｅｔ（Ｇ）に対しメッセージを送信し、自身の参加を知らせ、ネットワークは新たなＣＮｅｔ（Ｇ’）へと自己組織化を行う。ここで、Ｇ’は、Ｇからｖを加えることにより得られるグラフである。
【００５９】
・離脱：離脱するノードｖは、既存ののＣＮｅｔ（Ｇ）に対しメッセージを送信し、自身の離脱を知らせ、ネットワークは新たなＣＮｅｔ（Ｇ’）へと自己組織化を行う。ここで、Ｇ’は、Ｇからｖを削除することにより得られるグラフである。
【００６０】
又、独立な複数のＣＮｅｔ（Ｇ1），ＣＮｅｔ（Ｇ1），…に対し、ノードの参加が行われることにより、それらが連結され、一つのＣＮｅｔ（Ｇ）へと組織化される操作を統合と呼ぶ（統合は、参加の一部分としても考えられる）。
【００６１】
本実施形態では、参加／離脱の操作後のグラフは、連結であると仮定する。
【００６２】
次に、ＣＮｅｔ（Ｇ）を用いたブロードキャストについて説明する。このアルゴリズムでは、「B.S. Chelebusm L.Gasieniec, A.M. Gibboons, A. Pelc, and W.Rytter, “Deterministic broadcasuting in ad hoc radio network”, Distributed Computing 15, pages 27-38, 2002」で示されているテクニックを用い、その手続きをEulerianと呼ぶことにする。
【００６３】
Eulerian（Ｈ）は、双方向グラフＨ上でブロードキャストを実行するものである。トークンと呼ばれるメッセージがソースノードから送信され、Ｈ上のすべてのノードを巡回した後、ソースノードへと戻ってくる。このトークは、Ｈを深さ優先順にたどる。ｖがトークンを受け取ったとき、ｖはそのトークンに自身のＩＤをメッセージ付加し、まだトークンを受信してない隣接ノードへと送る。もしｖの隣接ノードがすべてトークンを受け取っているならば、最初に自身に対してトークンを送ってきたノードへトークンを送り返す。このトークンの動きはＨのオイラーサイクルを形成している。トークンはＨ上のすべてのノードを巡回し、最終的にソースノードへと戻ってくる。
【００６４】
このEulerianに関して、次の補題が成り立つ。
【００６５】
補題１．連結双方向グラフをＨ＝（Ｖ，Ｅ）とする。Ｈの各ノードが自身の隣接ノードのＩＤをすべて知っていたら、Eulerian（Ｈ）はＯ（｜Ｖ｜）ラウンドでＨ上の風呂ロードキャストを完了する。
【００６６】
ソースノードをｓ，ｓが持っているブロードキャストするメッセージをＭとし、ＣＮｅｔ（Ｇ）上でのブロードキャストアルゴリズムBroadcastALGを図３に示す。
【００６７】
Eulerianを実行するグラフ上のすべてのノードは、必ず送信を行い、かつそのラウンドにおける送信ノードは、そのノードのみであること、及び、ＢＴ（Ｇ）が支配点集合から形成されていることから、ＢＴ（Ｇ）上でのEulerian（ＢＴ（Ｇ））を実行することにより、ＣＮｅｔ（Ｇ）におけるブロードキャストを完了することができる。
【００６８】
定理１．ＧにおけるバックボーンツリーをＢＴ（Ｇ）＝（ＶBT，ＥBT）とする。ＣＮｅｔ（Ｇ）上でのブロードキャストＯ（｜ＶBT｜）ラウンドで実行可能。
【００６９】
（アーキテクチャＣの構造）
次に、アーキテクチャＣの構造について説明する。
【００７０】
上述した定義に加え、Ｃにおいては、すべてのヘッドの集合は、Ｇの独立点集合となっている。ヘッド以外のＢＴ（Ｇ）のノードは、ゲートウェイと呼ばれ、ＢＴ（Ｇ）上でお互いに隣接せず、二つ以上のヘッドと隣接している。
【００７１】
このような構造を持つＣをメンテナンスする参加／離脱については、非特許文献１を参照できる。Ｃは、以下の性質を持つ。
【００７２】
補題２．連結双方向グラフＧとＢＴ（Ｇ）に対し、Ｃにおいて、ＢＴ（Ｇ）がｐ個のヘッドを持つならば、ＢＴ（Ｇ）のノード数は高々２ｐ−１である。
【００７３】
ヘッド同士が隣接しないことから、以下の補題が成り立つ。
【００７４】
補題３．双方向グラフをＧ，Ｇの最小クリーク分割数をｐGとする。ＣＮｅｔ（Ｇ）におけるヘッドの数は、高々ｐGである。
【００７５】
補題４．単位円グラフをＧ，Ｇの最小支配点集合をＭＤＳ（Ｇ）とする。ＣＮｅｔ（Ｇ）におけるクラスタの数は、５×｜ＭＤＳ（Ｇ）｜である。
【００７６】
又、非特許文献１においては、統合操作は考えられていない。
【００７７】
（アーキテクチャＭの構造）
次に、アーキテクチャＭの構造について説明する。
【００７８】
アーキテクチャＣについては、ノードの参加による複数のクラスタベースアーキテクチャの統合については考慮されていなかった。
【００７９】
そこで、ゲートウェイは、ＢＴ（Ｇ）上でお互いに隣接していないというＣにおける条件を緩め、ＢＴ（Ｇ）上でゲートウェイの連続を許すことで、非特許文献２に記載のように、統合を可能にするアーキテクチャＭが提案された。その構造は以下の通りである。
【００８０】
Ｃと同様に、Ｍにおいては、すべてのヘッドの集合は、Ｇの独立点集合である。ＢＴ（Ｇ）の葉は、すべてヘッドであり、ヘッド以外のＢＴ（Ｇ）のノードはゲートウェイと呼ばれる。ゲートウェイは、ＢＴ（Ｇ）上で、少なくとも一つのヘッドと隣接している。
【００８１】
このような構造を持つＭをメンテナンスする参加／離脱については、非特許文献２を参照できる。Ｍは、以下の性質を持つ。
【００８２】
補題５．連結双方向グラフＧとＢＴ（Ｇ）に対し、Ｍにおいて、ＢＴ（Ｇ）がｐ個のヘッドを持つならば、ＢＴ（Ｇ）のノード数は、高々３ｐ−２である。
【００８３】
又、ヘッド同士が隣接しないことから、Ｃと同様に、補題３，４が成り立つ。
【００８４】
このアーキテクチャＭは、Ｃと比べ、バックボーンツリーのサイズのオーダーを変えることなく、つまりブロードキャストの実行時間のオーダーを変えることなく、統合を可能にしている。又、統合が発生しない場合の参加／離脱アルゴリズムに関しても、その実行時間及びバックボーンツリーのサイズは、非特許文献１と同様である。
【００８５】
（アーキテクチャＩの構造）
アーキテクチャＭは、Ｃと比べ、種々の操作の実行時間のオーダーを変えることなく、統合を可能にしたが、ヘッド、メンバ以外にゲートウェイ成るステータスを用いており、又、バックボーンツリーの構造の条件も複雑である。
【００８６】
そこで、ゲートウェイを廃止し、ヘッドとメンバのみで構成されるアーキテクチャＩを提案する。その構造は、Ｃ、Ｍと異なり、ヘッドの集合はＧの独立点集合ではなく、バックボーンツリーはヘッドのみで構成される。
【００８７】
アーキテクチャＩの構造を持つＣＮｅｔ（Ｇ）とＢＴ（Ｇ）をそれぞれＣＮｅｔＩ（Ｇ）とＢＴＩ（Ｇ）とする。
【００８８】
ここで、ＣＮｅｔＩ（Ｇ）に利用されるノードの構造について、図４を用いて説明する。図４に示すように、ノード１００は、送受信部１０１と、ステータス管理部１０２と、root管理部１０３とを備える。
【００８９】
送受信部１０１は、隣接ノードとの情報の送受信を行う。
【００９０】
ステータス管理部１０２は、自身のステータス、具体的には、自身がヘッドであるかメンバであるか判断する。
【００９１】
Root管理部１０３は、自身がクラスタネットワークのrootであるか否か判断する。
【００９２】
その他、無線通信装置としての機能は、従来と同様であるので、ここでは説明を省略する。
【００９３】
次に、Ｉについての参加アルゴリズムについて説明する。図５は、ノードがネットワークに参加する場合のフローチャートである。
【００９４】
ネットワークＧ＝（Ｖ，Ｅ）に参加するノードを参加ノード（以下において、「new」という。）とし、アーキテクチャＩの説明において、Ｇ’＝（Ｖ∪｛new｝，Ｅ∪Ｅnew）とする。ここで、＝｛（u,new）|u∈Ｖ｝、即ち、uは、newの送信範囲内に存在するとする。又、｜Ｅnew｜＝ｑとする。又、ここでは、「Ｇ’上の隣接ノード」を単に「隣接ノード」と表記する。
【００９５】
参加操作によって行われることは、newのステータスの決定とその隣接ノードが持つ情報の更新である。
【００９６】
まず、newは、参加することを示すメッセージ（AddMeメッセージ）を隣接ノードへ送信する（Ｓ１０１）。newは、自身のステータスを決定するために、その隣接ノードのステータスを知る必要がある。このため、隣接ノードは、参加ノードへ自身のＩＤ、ステータス、rootＩＤを送信する（Ｓ１０２）。newは、ヘッドがnewに隣接していたならば、newは隣接しているヘッドを一つ選びそのメンバとなり、そうでなければ、newはヘッドとなり隣接しているメンバの一つをヘッドにする（Ｓ１０３）。そして、newは、決定したステータスを隣接ノードへ送信する（Ｓ１０４）。隣接ノードは、決定されたnewのステータスに基づき、newの隣接ノードは自身の情報を更新する（Ｓ１０５）。いずれの場合も、この操作はnewの2-hopまでの隣接ノードにのみ影響を及ぼす。即ち、メッセージが送られる。
【００９７】
newのステータスを決定し、その情報を更新する際には、newの隣接ノードが一つずつ自身のＩＤとステータスを送信すれば十分である。これは、newの隣接ノードに１からｑまで番号をつけ、その番号順にそれらの情報を送ることにより実現できる。
【００９８】
補題６．平均Ｏ（ｐ）ラウンドでnewの隣接ノードを１からｑまで番号付けられる。
【００９９】
Ｉの構造を維持する参加アルゴリズムＩ-joinを図６に示す。
【０１００】
補題７．連結双方向グラフＧとＣＮｅｔＩ（Ｇ）に対し、Ｇがtotal 1-hop dataで組織化されているとき、newに対するＩ-joinの実行後、Ｇ’はtotal 1-hop dataで組織化されている。
【０１０１】
定理２．連結双方向グラフＧとＣＮｅｔＩ（Ｇ）に対し、Ｇがtotal 1-hop dataで組織化されているとき、newの参加操作及びＧ’のtotal 1-hop dataでの組織化がＯ（ｐ）ラウンドで実行可能。
【０１０２】
Ｉ-joinの実行中、2-hopまでの隣接ノードのみがＩ-joinによって生成されるメッセージを受信する。よって、newの2-hop隣接ノードのみで局所的に参加操作が実行可能である。
【０１０３】
次に、Ｉを維持する離脱アルゴリズムＩ-leaveについて説明する。
【０１０４】
Ｇから離脱するノードをlev,levが離脱した後のグラフをＧ’＝Ｇ[Ｖ＼｛lev｝]とする。ここで、“＼”は、集合の減算を表す。Ｇ及びＧ’は、連結であると仮定する。図７に示すように、levを根とするＣＮｅｔＩ（Ｇ）の部分木をＴ＝（Ｖ（Ｔ），Ｅ（Ｔ））とすると、Ｇ’が連結であるかどうかはＯ（｜Ｔ｜）ラウンドで判別可能である。
【０１０５】
levがネットワークを離脱するとき、本実施形態に係る離脱アルゴリズムが実行される。図８は、ノードがネットワークから離脱する場合のフローチャートである。levがメンバならば、levがI’m leavingメッセージを返信し、ネットワークから離脱すればよい（Ｓ２０２）。levがヘッドならば、ステップＳ２０３へ進み、ＣＮｅｔＩ（Ｇ）は、livを根とする部分木ＴとＣＮｅｔＩ（Ｇ）の根を根とするＴ以外の木Ｈの二つの部分木に分かれる（Ｓ２０４）。アルゴリズムＩ-leaveは、Ｔからlevを取り除き、Ｔに含まれるlev以外のノードをＴの構造を保ったままＨへと加える。
【０１０６】
ここで、図７に示すように、Ｇ’の連結成分をＣi（i＝１，２，…）とする。ＴのノードがＨに追加される度にＨは変化する。
【０１０７】
ＴのノードをＨに追加するため、ＴとＨの間のＧの辺を用いる。上述したＩ-joinを用いることで、ＴのノードはＨへ追加されていく。各ノードは、自身のＧ上の隣接ノード及びそれらのステータスを知っているので、参加操作はＯ（１）ラウンドで決定的に実行可能である。最初に、Ｔのノードを起こすためにlevがEulerian（Ｔ）を行う。起こされたノードｖ∈ＣjからＨへの辺があるならば、ｖはＩ-joinにより一つずつＨへと移動する。この操作をlevを除くＴ内のすべてのノードがＨへ移動するまでを繰り返す。
【０１０８】
levがＣＮｅｔＩ（Ｇ）の根である場合、lev.bneigh≠空集合ならば、levの2-hopの隣接ヘッドを一つ選び、ＣＮｅｔＩ（Ｇ）の新たな根とする（Ｓ２０７）ことで、上記の一般の場合のアルゴリズムを用いることができる。そうでない場合は、levが唯一のヘッドであるので、隣接ノードの一つをＣＮｅｔＩ（Ｇ）の新たな根として選び（Ｓ２０６）、ヘッドとする。その根は、Eulerian（Ｇ[Ｖ＼｛lev｝]）を実行し、トークンを受け取ったノードが順番にＩ-joinを実行することで、ＣＮｅｔＩ（Ｇ）が構築される。
【０１０９】
この離脱アルゴリズムＩ-leaveを図９及び図１０に示す。
【０１１０】
補題８．連結双方向グラフＧとＣＮｅｔＩ（Ｇ）に対し、Ｇがtotal 1-hop dataで組織化されているとき、levに対するＩ-leaveの実行後、Ｇ’はtotal 1-hop dataで組織化されている。
【０１１１】
定理３．連結双方向グラフＧとＣＮｅｔＩ（Ｇ）に対し、Ｇがtotal 1-hop dataで組織化されているとき、levの離脱操作及びＧ’のtotal 1-hop dataでの組織化がＯ（｜Ｔ｜）ラウンドで実行可能である。ここでは、Ｔはlevを根とするＣＮｅｔＩ（Ｇ）の部分木である。
【０１１２】
上述した参加／離脱アルゴリズムによって構成されたＩは、次の性質を持つ。
【０１１３】
補題９．Ｉにおいて、クラスタ数は｜ＢＴＩ（Ｇ）｜と等しい。
【０１１４】
補題１０．双方向グラフをＧ，Ｇの最小クリーク分割数をｐGとする。Ｉ-join/leaveアルゴリズムによって構築されたＩにおいて、ＢＴi（Ｇ）のサイズは、高々３ｐG−２である。
【０１１５】
補題１１．単位円グラフをＧ，Ｇの最小支配点集合をＭＤＳ（Ｇ）とする。Ｉ-join/leaveアルゴリズムによって構築されたＩにおいて、｜ＢＴＩ（Ｇ）｜は、高々１０×｜ＭＤＳ（Ｇ）｜以下である。
【０１１６】
これらの補題１０、１１で示される性質は、Ｉの構造の定義から導かれるものではなく、そのメンテナンスアルゴズム（Algorithm2,3）の特性から示されるものである。
【０１１７】
Ｍと同様に、このアーキテクチャＩは、Ｃと比べ、ブロードキャストの実行時間のオーダーを変えることなく、統合を可能にしている。統合が発生しない場合の参加／離脱アルゴリズムに関しても、その実行時間及びバックボーンツリーのサイズは、非特許文献１と同様である。又、ＣＮｅｔＩ（Ｇ）をヘッドとメンバのみで構成することにより、ステータスの種類を減らし、より簡潔なバックボーンツリーの構造を実現している。
【０１１８】
（アーキテクチャＵの構造）
最後に、バックボーンツリーなどの基本構造は、Ｉを踏襲しつつ、メンバを２種類に分類し、クラスタ数（即ち、バックボーンツリーのサイズ）の減少をはかったアーキテクチャＵを提案する。
【０１１９】
その構造は、Ｉと同様に、ヘッドの集合はＧの独立点集合ではなく、バックボーンツリーはヘッドのみで構成される。又、ヘッド以外のノードのステータスとして、メンバ１／メンバ２を導入する。
【０１２０】
アーキテクチャＵの構造を持つＣＮｅｔ（Ｇ）とＢＴ（Ｇ）をそれぞれＣＮｅｔU（Ｇ）とＢＴU（Ｇ）とする。
【０１２１】
次に、Ｕに対する参加アルゴリズムについて説明する。
【０１２２】
ステータスの決定に関する動作以外はＩにおける参加アルゴリズムと同じであるため、ステータス決定に関連した部分のみを、図１１に抜粋する。
【０１２３】
Ｕ-joinの実行中、2-hopまでのnewの隣接ノードのみがＵ-joinによって生成されるメッセージを受信する。よって、newの2-hop隣接ノードのみで局所的に参加操作が可能である。
【０１２４】
Ｕを維持するleaveアルゴリズムについては、サブルーチンとしてＩ-joinの代わりにＵ-joinを用いる点を除き、Ｉ-leaveと同じである。
【０１２５】
これらの参加／離脱アルゴリズムによって構成されたＵは次の性質を持つ。
【０１２６】
補題１２．Ｕにおいて、クラスタ数は｜ＢＴU（Ｇ）｜と等しい。
【０１２７】
補題１３．双方向グラフをＧ，Ｇの最小クリーク分割数をｐGとする。Ｕ-join/leaveアルゴリズムによって構築されたＵにおいて、｜ＢＴU（Ｇ）｜は、高々３ｐG―２である。
【０１２８】
補題１４．単位円グラフをＧ，Ｇの最小支配点集合をＭＤＳ（Ｇ）とする。Ｕ-join/leaveアルゴリズムによって構築されたＵにおいて、｜ＢＴU（Ｇ）｜は、高々１０×（ＭＤＳ（Ｇ））以下である。
【０１２９】
Ｉ同様これらの補題１３，１４で示される性質は、Ｕの構造の定義から導かれるものではなく、そのメンテナンスアルゴリズムの特性から示されるものである。
【０１３０】
このアーキテクチャＵは、統合の可否／ブロードキャストの実行時間／バックボーンツリーのサイズにおいて、Ｍ、Ｉと同様の性質を満足する。
【０１３１】
（作用及び効果）
本実施形態に係るネットワーク構築方法では、クラスタネットワークをヘッドとメンバのみで構成することにより、ステータスの種類を減らし、より簡潔なバックボーンツリーの構造を実現している。又、ヘッドの集合は、独立点集合を構成せず、連結支配点集合を構成し、ネットワークへ参加する参加ノードが、当該参加ノードに隣接する隣接ノードから受信したステータスに応じて、参加ノード自身のステータスを決定する。このため、本実施形態に係るネットワーク構築方法によると、ゲートウェイを存在させないことにより、メンテナンスアルゴリズムを簡略化し、バックボーン木のサイズを減少でき、ブロードキャストの効率化を実現することができる。
【０１３２】
又、本実施形態に係るネットワーク構築方法では、参加ノードは、２−ホップまでの隣接ノードからステータスを受信し、２−ホップまでの隣接ノードへ参加ノード自身のステータスを送信してもよい。このため、参加ノードの２ホップ隣接ノードのみで、局所的に参加操作が可能となる。
【０１３３】
又、本実施形態に係るネットワーク構築方法によると、ネットワークからの参加に加え、離脱においても、メンテナンスアルゴリズムを簡略化することができる。
【０１３４】
又、上記の離脱方法は、離脱ノードがメンバでなく、クラスタネットワークの根でない場合、離脱ノードを根とする第１の部分木と、クラスタネットワークの根を根とする第２の部分木とに分かれてもよい。
【０１３５】
又、離脱ノードがメンバでなく、クラスタネットワークの根である場合、離脱ノードの隣接ノードが有る場合、当該隣接ノードの一つをクラスタネットワークの新たな根とし、離脱ノードの隣接ノードが無い場合、２−ホップの隣接ヘッドの一つをクラスタネットワークの新たな根としてもよい。
【図面の簡単な説明】
【０１３６】
【図１】本実施形態に係る各アーキテクチャの性質の一覧である。
【図２】本実施形態に係るＧ、ＢＴ（Ｇ）、ＣＮｅｔ（Ｇ）の構成を示す図である。
【図３】本実施形態に係るBroadcastALGの一例である。
【図４】本実施形態に係るノードの構成ブロック図である。
【図５】本実施形態に係る無線ネットワーク構築方法（参加方法）を示すフローチャートである。
【図６】本実施形態に係る参加アルゴリズムの一例である（その１）。
【図７】本実施形態に係るＣＮｅｔＩ（Ｇ）、部分木Ｔ、Ｔの中の連結成分を説明するための図である。
【図８】本実施形態に係る無線ネットワーク構築方法（離脱方法）を示すフローチャートである。
【図９】本実施形態に係る離脱アルゴリズムの一例である（その１）。
【図１０】本実施形態に係る離脱アルゴリズムの一例である（その２）。
【図１１】本実施形態に係る参加アルゴリズムの一例である（その２）。
【符号の説明】
【０１３７】
１００…ノード
１０１…送受信部
１０２…ステータス管理部
１０３…root管理部
【図１】
2007306135.tif 000003
【図２】
2007306135.tif 000004
【図３】
2007306135.tif 000005
【図４】
2007306135.tif 000006
【図５】
2007306135.tif 000007
【図６】
2007306135.tif 000008
【図７】
2007306135.tif 000009
【図８】
2007306135.tif 000010
【図９】
2007306135.tif 000011
【図１０】
2007306135.tif 000012
【図１１】
2007306135.tif 000013