(57)【要約】    【課題】NEWが複数のCNetに隣接する場合や，無線ノードが離脱する事で無線ネットワークが複数の部分ネットワークに分割される際にも，効率よくCNetを維持することが可能であるクラスタ構造と，それを構築・維持するためのアルゴリズムMove-In及びMove-Outを提供することを課題とする．【解決手段】各端末が新たなノードの発生時にはMove-In アルゴリズムを，ノードの離脱時にはMove-Out アルゴリズムを実行することを特徴とする．    【選択図】図３
2007221428.tif 000002
【特許請求の範囲】
【請求項１】
各移動端末が，自身が属するクラスタを認識するための「ルートID」を備えていることを特徴とする移動端末による通信網の構造化手法．
【請求項２】
任意の2つのクラスタヘッドは，1つ以上のゲートウェイによって接続されることを特徴とする移動端末による通信網の構造化手法．
【請求項３】
請求項２に記載のゲートウェイは，必ず少なくとも1つ以上のヘッドと隣接することを特徴とする移動端末による通信網の構造化手法．
【請求項４】
請求項１乃至３記載の移動端末による通信網の構造化手法によるクラスタ構造を維持・構成するために各端末が新たなノードの発生時にはMove-In アルゴリズムを，ノードの離脱時にはMove-Out アルゴリズムを実行することを特徴とする移動端末による通信網の構造化手法。
【請求項５】
請求項４記載のMove-In アルゴリズムが以下に示すものであることを特徴とする請求項４記載の移動端末による通信網の構造化手法。
まず、Move-Inアルゴリズム中で各ノードが送信するメッセージや述語を説明する．
・AddMe ：新規に発生するノードが送信するメッセージ
AddMe.ID :=自分のID
・Mystatus ：AddMeメッセージを受信したノードがが送信するメッセージ
Mystatus.ID :=自分のID
Mystatus.root :=自分のルートID
・ChangeMyStatus ノードがステータスを変更した事を隣接ノードに連絡するメッセージ
ChangeMyStatus.ID :=自分のID
ChangeMyStatus.status :=自分の新しいステータス
・ImYourChild：送信元のノードが宛先のノードの子供になる際に用いるメッセージ
ImYourChild.status :=自分のステータス
ImYourChild.ID:=自分のID
ImYourChild.To:=宛先のID
・ImYourParent：送信元のノードが宛先のノードの親になる際に用いるメッセージ
ImYourParent.status :=自分のステータス
ImYourParent.ID :=自分のID
ImYourParent.To :=宛先のID
ImYourParent.root:=自分のルートID
MinID(status)：隣接するノードのうちステータスがstatusの物で，一番小さなIDを持つノードのID
Move-Inアルゴリズム中で各ノードが送信するメッセージや述語の説明は、以上である。Move-In アルゴリズムを以下に示す．
・新たな無線ノード(以下「NEW」という。)が実行する動作
CNetに参加するノードNEWは隣接するノードに1からqまで番号を割り振り，
1からqまで順番にAddMeメッセージを送信；
WHILE(隣接するq個のノードの中にAddMeメッセージを未送信のノードが存在)｛
NEWはAddMeメッセージを未送信のノードへAddMeメッセージを送信する；
MyStatusメッセージの受信を待つ；
｝
IF(NEWがルートIDを一つも受信せず)
THEN
NEW.status := ヘッド；
NEW.root := NEW.ID；
ELSE IF( NEW がルートID を一つのみ受信)
THEN
IF(NEW と隣接するノードの中にヘッドが存在)
THEN
NEW.status := メンバー；
MinID(ヘッド) にImYourChild メッセージを送信；
NEW.root := MinID(ヘッド) のルートID；
NEW.prt := MinID(ヘッド)；
NEW.oneigh := MinID(ヘッド) 以外の隣接ノードのID；
ELSE IF(NEW と隣接するノードの中にゲートウェイが存在)
THEN
NEW.status := ヘッド；
MinID(ゲートウェイ) にImYourChild メッセージを送信；
NEW.root := MinID(ゲートウェイ) のルートID；
NEW.prt := MinID(ゲートウェイ)；
NEW.bneigh := MinID(ゲートウェイ)；
NEW.oneigh := MinID(ゲートウェイ) 以外の隣接ノード；
ELSE
NEW.status := ヘッド；
MinID(メンバー) にImYourChild メッセージを送信；
NEW.root := MinID(メンバー) のルートID；
NEW.prt := MinID(メンバー)；
NEW.bneigh := MinID(メンバー)；
NEW.oneigh := MinID(メンバー) 以外の隣接ノード；
ELSE //NEW が複数のルートID を受信
THEN
IF(NEW と隣接するノードの中にヘッドが存在)
THEN
NEW.status := ゲートウェイ；
MinID(ヘッド) にImYourChild メッセージを送信；
NEW.root := MinID(ヘッド) のルートID；
NEW.prt := MinID(ヘッド)；
NEW.bneigh := MinID(ヘッド)；
NEW.oneigh := MinID(ヘッド) 以外の隣接ノードのID；
ELSE IF(NEW と隣接するノードの中にゲートウェイが存在)
THEN
NEW.status := ヘッド；
MinID(ゲートウェイ) にImYourChild メッセージを送信；
NEW.root := MinID(ゲートウェイ) のルートID；
NEW.prt := MinID(ゲートウェイ)；
NEW.bneigh := MinID(ゲートウェイ)；
NEW.oneigh := MinID(ゲートウェイ) 以外の隣接ノード；
ELSE
NEW.status := ヘッド；
MinID(メンバー) にImYourChild メッセージを送信；
NEW.root := MinID(メンバー) のルートID；
NEW.prt := MinID(メンバー)；
NEW.bneigh := MinID(メンバー)；
NEW.oneigh := MinID(メンバー) 以外の隣接ノード；
WHILE(NEW の親または子供が未選択のCNet が存在する)｛
IF(NEW の親または子供を未選択のCNet 中にNEW と隣接するヘッドが存在)
THEN
親と子供を未選択のCNet 中でのMinID(ヘッド) にImYourParent メッセージを送信；
NEW.chd に親または子供を未選択のCNet 中でのMinID(ヘッド) を追加；
NEW.bneigh に親または子供を未選択のCNet 中でのMinID(ヘッド) を追加；
NEW.oneigh からMinID(ヘッド) を削除；
ELSE IF(NEW の親または子供を未選択のCNet 中にNEW と隣接するゲートウェイが存在)
THEN
親と子供を未選択のCNet 中でのMinID(ゲートウェイ) にImYourParent メッセージを送信；
NEW.chd に親または子供を未選択のCNet 中でのMinID(ゲートウェイ) を追加；
NEW.bneigh に親または子供を未選択のCNet 中でのMinID(ゲートウェイ) を追加；
NEW.oneigh からMinID(ゲートウェイ) を削除；
ELSE
親と子供を未選択のCNet 中でのMinID(メンバー) にImYourParent メッセージを送信；
NEW.chd に親または子供を未選択のCNet 中でのMinID(メンバー) を追加；
NEW.bneigh に親または子供を未選択のCNet 中でのMinID(メンバー) を追加；
NEW.oneigh からMinID(メンバー) を削除；
｝END WHILE
・NEW以外のノードPi が実行する動作
IF(AddMe メッセージを受信)
THEN
NEW へMyStatus メッセージを送信；
IF(ImYourChild メッセージを受信)
THEN
IF(ImYourChild.To == Pi.ID)
THEN
Pi.chd := Pi.chd [ ImYourChild.ID；
IF( ImYourChild.status がヘッドかゲートウェイ)
Pi.bneigh := Pi.chd [ ImYourChild.ID；
IF(Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh := Pi.prt；
Pi はChangeMyStatus メッセージを送信；
ELSE
Pi.oneigh := Pi.oneigh [ ImYourChild.ID；
ID がImYourChild.ID のノードのステータスをImYourChild.status に変更；
IF(ImYourParent メッセージを受信)
THEN
IF(ImYourParent.To == Pi.ID)
THEN
Pi.root := ImYourParent.root；
IF(Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh にPi.prt とImYourParent.ID を追加
Pi はChangeMyStatus メッセージを送信；
Pi.prt へImYourParent メッセージを送信；
Pi.chd := Pi.prt；
Pi.prt := ImYourParent.ID；
ELSE IF(Pi がCNet のルート)
THEN
Pi.chd にImYourParent.ID があればこれを削除；
Pi.prt := ImYourParent.ID；
Pi.root をBroad を用いてブロードキャスト；
ELSE
Pi.chd にImYourParent.ID があればこれを削除；
Pi.prt へImYourParent メッセージを送信；
Pi.chd := Pi.chd [ Pi.prt；
Pi.prt := ImYourParent.ID；
IF(ChangeMyStatus メッセージを受信した)
THEN
ID がChangeMyStatus.ID のノードのステータスをChangeMyStatus.status に変更；
IF(Pi.chd にChangeMyStatus.ID が含まれる)
Pi.bneigh := Pi.bneigh [ ChangeMyStatus.ID；
【請求項６】
請求項４または5記載のMove-Outアルゴリズムが以下に示すものであることを特徴とする請求項４または5記載の移動端末による通信網の構造化手法。
まず、Move-Outアルゴリズム中で各ノードが送信するメッセージや述語を説明する．
・Leave ：CNet から退出するノードDEL が送信メッセージ
Leave.ID := 自分のID Leave.status := 自分のステータス
・ChangeMyStatus ノードがステータスを変更した事を隣接ノードに連絡するメッセージ
ChangeMyStatus.ID := 自分のID
ChangeMyStatus.status := 自分の新しいステータス
・CheckYourChd ：宛先のノードに子供が存在するかを確認させる時に用いるメッセージ
CheckYourChd.ID := 自分のID CheckYourChd.To := 宛先のID
・ChangeRootID DEL.chd を根とする部分木のルートID を変更する時に用いるメッセージ
ChangeRootID.ID := 自分のID
ChangeRootID.To := 宛先のID
ChangeRootID.root := 自分のルートID
・CheckYourNeighbors ：DEL.chd を根とする部分木の隣接状況を調べるときに用いるメッセージ
ChechYourNeighbors.list := 隣接する部分木のルートID を集めるリスト型の変数
ChechYourNeighbors.To := 宛先のID
・MergeToNeighbor.ID ：送信元のノードが宛先のノードの親になる際に用いるメッセージ
MergeToNeighbor.ID := 統合先の部分木が持つルートID
MergeToNeighbor.To := 宛先のID
MergeToNeighbor.flag := 統合が実行済みかどうかを示すフラグ．実行済みの時TRUE，未実行の時FALSE
・Independence ：DEL.chd を根とする部分木を独立させる時に用いるメッセージ
Independence.To := 宛先のID
・ImYourChild ：送信元のノードが宛先のノードの子供になる際に用いるメッセージ
ImYourChild.status := 自分のステータス
ImYourChild.ID := 自分のID
ImYourChild.To := 宛先のID
・ImYourParent ：送信元のノードが宛先のノードの親になる際に用いるメッセージ
ImYourParent.ID := 自分のID
ImYourParent.To := 宛先のID
・MinID(status) ：隣接するノードのうちステータスがstatus の物で，一番小さなID を持つノードのID
・MinID(status,root) ：隣接するノードのうちルートID がroot かつステータスがstatus の物で，一番小さなID を持つノードのID
Move-Outアルゴリズム中で各ノードが送信するメッセージや述語の説明は、以上である．
Move-Outアルゴリズムを以下に示す．
・DELが実行する動作
CNet から離脱するノードDEL はLeave メッセージを送信；
WHILE(DEL はChangeRootID メッセージを未送信の子供を持つ)｛
DEL はChangeRootID メッセージを未送信の子供にChangeRootID メッセージを送信；
｝END WHILE
WHILE(DEL はCheckYourNeighbors メッセージを未送信の子供を持つ)｛
CheckYourNeighbors メッセージを未送信の子供にCheckYourNeighbors メッセージを送信する；
｝END WHILE
DEL はDEL.chd を根とする部分木それぞれの隣接ルートID リストより，
各部分木の再統合を実行する順番及び統合先の部分木を決定する；
WHILE(MergeToNeighbor メッセージ又はIndepentence メッセージを未送信の子供を持つ)｛
IF( DEL に統合が実行可能でMergeToNeighbor メッセージを未送信の子供が存在する)
THEN
統合が可能でMergeToNeighbor メッセージを未送信の子供にMergeToNeighbor メッセージを
送信する；
ELSE
MergeToNeighbor メッセージまたはIndependence メッセージを未送信の子供にIndependence
メッセージを送信する；
｝END WHILE
・DEL以外のノードPi が実行する動作
IF(Leave メッセージを受信)
THEN
IF(Leave.ID がPi.chd に含まれる)
THEN
Pi.chd からLeave.ID を削除；
IF( Leave.status == ヘッド)
THEN
IF( Pi.prt.status == ゲートウェイ)
THEN
IF( Pi は子供を持たない)
THEN
IF( Pi.oneigh の中にステータスがヘッドのノードが存在)
THEN
Pi はPi.prt にCheckYourChd メッセージを送信；
Pi.status := メンバー；
Pi はMinID(ヘッド) にImYourChd メッセージを送信；
Pi.prt := MinID(ヘッド)；
ELSE
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
IF( Pi.chd の中にステータスがヘッドのノードが存在しない)
THEN
IF( Pi.oneigh の中にステータスがヘッドのノードが存在)
THEN
Pi はPi.prt にCheckYourChd メッセージを送信；
Pi.prt := MinID(ヘッド)；
ELSE
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
IF( Pi は子供を持たない)
THEN
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
ELSE IF( Leave.status == ゲートウェイ)
THEN
IF( Pi.status == ゲートウェイ)
THEN
IF( Pi は子供を持たない)
Pi.status := メンバー；
Pi はMinID(ヘッド) にImYourChd メッセージを送信；
ELSE IF( Leave.ID == Pi.prt )
THEN
IF( Leave.status == ヘッド)
THEN
IF( Pi.status == ゲートウェイ)
THEN
IF( Pi は子供を複数持つ)
THEN
IF( Pi.oneigh 及びPi.oneigh の中にヘッドのノードが存在しない)
THEN
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
IF( Pi.oneigh 及びPi.oneigh の中にヘッドのノードが存在しない)
THEN
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
IF( Pi.status == メンバー)
THEN
IF( Pi.oneigh の中にステータスがヘッドのノードが存在しない)
THEN
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE IF( Leave.status == ゲートウェイ)
THEN
IF( Pi.status == ゲートウェイ)
THEN
IF( Pi は子供を一つだけ持つ)
THEN
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
ELSE IF( Leave.ID がPi.oneigh に含まれる)
THEN
Pi.oneigh からLeave.ID を削除；
IF( ChangeRootID メッセージを受信した)
THEN
IF( ChangeRootID.To == Pi.ID )
THEN
IF( ChangeRootID.ID == Leave.ID )
THEN
Pi.root := Pi.ID；
WHILE(ChangeRootID メッセージを未送信の子供を持つ)｛
Pi はChangeRootID メッセージを送信；
｝
ELSE IF( ChangeRootID.ID == Pi.prt )
THEN
Pi.root := ChangeRootID.ID
WHILE(ChangeRootID メッセージを未送信の子供を持つ)｛
Pi はChangeRootID メッセージを送信；
｝
IF( CheckYourNeighbors メッセージを受信した)
THEN
IF( CheckYourNeighbors.To == Pi.ID )
THEN
IF( CheckYourNeighbors.list に存在しない(Pi.oneigh).root が存在)
THEN
CheckYourNeighbors.list に存在しない(Pi.oneigh).root を追加；
WHILE(ChangeYourNeighbors メッセージを未送信の子供を持つ)｛
CheckYourNeighbors メッセージを未送信の子供にCheckYourNeighbors メッセージを
送信する；
IF( MergeToNeighbor メッセージを受信した)
THEN
Pi.root := MergeToNeighbor.ID
IF( MergeToNeighbor.ID がPi.oneigh に含まれる)
THEN
IF( MergeToNeighbor.flag == FALSE )
THEN
MergeToNeighbor.flag := TRUE；
Pi.prt へImYourParent メッセージを送信；
IF( Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh := Pi.prt；
Pi はChangeMyStatus メッセージを送信；
IF(Pi.oneigh にルートID がMergeToNeighbor.ID でヘッドのノードが存在)
THEN
Pi はMinID(ヘッド,MergeToNeighbor.ID) へImYourChild メッセージを送信；
Pi.bneigh := Pi.bneigh [ MinID(ヘッド,MergeToNeighbor.ID)
Pi.oneigh からMinID(ヘッド,MergeToNeighbor.ID) を削除；
Pi.prt := MinID(ヘッド,MergeToNeighbor.ID)；
ELSE IF(Pi.oneigh にID がMergeToNeighbor.ID でステータスがゲートウェイのノードが存在)
THEN
Pi はMinID(ゲートウェイ,MergeToNeighbor.ID) へImYourChild メッセージを送信；
Pi.bneigh := Pi.bneigh [ MinID(ゲートウェイ,MergeToNeighbor.ID)；
Pi.oneigh からMinID(ゲートウェイ,MergeToNeighbor.ID) を削除；
Pi.prt := MinID(ゲートウェイ,MergeToNeighbor.ID)；
ELSE
Pi はルートID がMergeToNeighbor.ID のノードの中でのMinID(メンバー) へ
ImYourChild メッセージを送信；
Pi.bneigh := Pi.bneigh [ MinID(メンバー,MergeToNeighbor.ID)；
Pi.oneigh からMinID(メンバー,MergeToNeighbor.ID) を削除；
Pi.prt := MinID(メンバー,MergeToNeighbor.ID)；
WHILE(MergeToNeighbor メッセージを未送信の子供が存在する)｛
MergeToNeighbor メッセージを未送信の子供にMergeToNeighbor メッセージを送信する；
｝
IF(Independence メッセージを受信)
THEN
IF(Independence.To == Pi.ID)
THEN
IF( Pi.status がゲートウェイもしくはメンバー)
THEN
Pi.chd の中でのMinID(ヘッド) にImYourChild メッセージを送信；
Pi.prt := Pi.chd の中でのMinID(ヘッド)；
Pi.chd からPi.chd の中でのMinID(ヘッド) を削除；
IF(ImYourChild メッセージを受信)
THEN
IF(ImYourChild.To == Pi.ID)
THEN
Pi.chd := Pi.chd [ ImYourChild.ID；
Pi.bneigh := Pi.chd [ ImYourChild.ID；
IF(Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh := Pi.prt；
Pi はChangeMyStatus メッセージを送信；
ELSE
ID がImYourChild.ID のノードのステータスをImYourChild.status に変更；
IF(ImYourParent メッセージを受信)
THEN
IF(ImYourParent.To == Pi.ID)
THEN
Pi.prt へImYourParent メッセージを送信；
Pi.chd := Pi.chd [ Pi.prt；
Pi.prt := ImYourParent.ID；
IF(ChangeMyStatus メッセージを受信した)
THEN
ID がChangeMyStatus.ID のノードのステータスをChangeMyStatus.status に変更；
IF( ChangeMyStatus.status == メンバー)
THEN
IF(Pi.bneigh にChangeMyStatus.ID が含まれる)
Pi.bneigh からChangeMyStatus.ID を削除；
ELSE
IF(Pi.chd にChangeMyStatus.ID が含まれる)
Pi.bneigh := Pi.bneigh [ ChangeMyStatus.ID；
IF( CheckYourChd メッセージを受信した)
THEN
IF(CheckYourChd.To == Pi.ID)
THEN
Pi.chd よりCheckYourChd.ID を削除；
IF( Pi は子供を持たない)
THEN
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は移動端末による通信網の構造化手法に関する。
【背景技術】
【０００２】
無線を使って通信を行う端末を無線ノードと呼び，多くの自律的に動作する無線ノードによって形成されたネットワークを無線ネットワークという．通常無線ノードは移動が可能である事，またバッテリーが無くなると無線ノードは動作しなくなる事などから，無線ネットワークの構造は動的に変化するものであるといえる．
ここで，無線を使った通信ではメッセージの衝突(コリジョン) を考慮しなければならない．メッセージの衝突とは，複数の無線ノードが同時にメッセージを送信するとき，それらのメッセージが重なり合い破損してしまう現象を指す．ある時点で衝突の発生する可能性がない通信路が存在したとしても，次の瞬間その通信路の近くに無線ノードが発生する事で新たに衝突が発生する可能性が生じてしまう．このように，動的に構造が変化する無線ネットワークにおいては安定した通信経路を用意しておくことが難しい．
ネットワークを構成する無線ノードをただ起動させるだけではお互いの電波が届く範囲にある無線ノード間で通信が可能になっただけである．このような状態で無線ノードがメッセージを送信すると衝突が発生する可能性があり，その場合無線ノードは同じメッセージをもう一度送信しなければならない．
無線通信モデルとして，衝突が起きたことが分かるモデル(Collision Detection/CD)の場合，再送と受信確認メッセージを利用することで，確実なメッセージ送受信が比較的容易に実現できるが，衝突が分からないモデル(Collision Avoidance/CA)の場合，メッセージが出されていない状態と衝突した状態の区別ができないため，メッセージ送受信が非常に困難となる．つまり，確実なメッセージのやり取りのためには，確率的な手法を用いる必要があり，そのために繰り返し同じメッセージを送信する必要がある．この為にメッセージ数が増大し，またその送受信の分だけ余分に時間が必要となる事から，衝突が発生する可能性がある無線ネットワークでは通信を効率よく行う事が難しい．
そこで，近年の携帯電話や無線通信機能を持つノートPC の普及を受けて，これら自律的に動作する多数の無線ノードにより構成される無線ネットワークにおいて効率良く通信を行う手法へ関心が高まっている．
無線ネットワークにおいて効率のよい通信を行う手法として内田らはクラスタを用いた手法を提案した（非特許文献１）．この手法における各クラスタは一つのクラスタヘッドと呼ばれる無線ノードと，その無線ノードと直接通信が可能な無線ノードによって構成される．この時クラスタヘッドがメッセージを送信すると，そのクラスタ内に存在する無線ノード全てにメッセージが到達する．
内田らの提案手法では，無線ネットワークを複数のクラスタに分割し，全てのクラスタヘッドを結ぶ木構造（バックボーンツリー）を形成する．このように，クラスタ構造を無線ネットワークに付与することをネットワークのクラスタ化と呼び，無線ネットワークをクラスタ化したものをクラスタネットワーク(CNet)と呼ぶ．図1にネットワークのクラスタ化の一例を示す．図1に示すように無線ネットワークをクラスタ化したCNetでは，全てのクラスタ・ヘッドがそれぞれ一回ずつメッセージを送信するだけで，ネットワーク内全ての無線ノードに対しメッセージが到達する．
クラスタ化されていない無線ネットワークで単純にブロードキャストを実行するときネットワーク内全ての無線ノードが最低一度ずつメッセージを送信する必要があり，またこの時衝突の発生を考慮する必要があるのに対し，CNetではクラスタ構造を利用することで，ある無線ノードがメッセージを無線ネットワーク内にブロードキャストするとき，自分自身とバックボーンツリー上の無線ノードが一度ずつメッセージを送信するだけで無線ネットワークへのブロードキャストが完
了する．また，この時衝突の可能性を考慮する必要が無い．図1の例では，ブロードキャストを実行する無線ノードとクラスタ・ヘッド及びGとマークされた無線ノードが一回ずつメッセージを送信することでブロードキャストが完了する．このようにして，クラスタを用いた構造により効率のよい通信を実現する．
内田らは，無線ネットワークに対して上述のクラスタ構造を構築・維持するためのアルゴリズムをあわせて提案している．ここで，提案されたアルゴリズムでは無線ネットワーク全体が常に連結である(任意の二つの無線ノード間に通信路が存在する) という前提が存在する．
この前提により，無線ネットワーク中に構成されているCNetは常に一つであり，新たな無線ノード(NEW)が出現する時には必ず単一のCNetに隣接している(通信が可能である)という制限がある．従って，複数のCNet が存在する無線ネットワーク中にNEWが発生するとき，NEWが複数のCNetと隣接している場合にはいずれか一つのCNetを除き，他のCNetを全て壊してもう一度CNet構造を構築するという，効率の悪い手法を取らざるを得ない．図2に内田らのアルゴリズムによるCNetの統合の一例を示す．
無線ノードがCNetから離脱する場合にも先の無線ネットワークは常に連結であるという前提が存在するため，ある無線ノードの離脱により無線ネットワークが複数の部分ネットワークに分割されるような場合，ある一つの部分ネットワーク上のCNetのみを残し，残りの部分はCNetを初めから再構築する必要があった．
しかし，センサーネットワークのような実際の無線ネットワークにおいては，互いに隣接する無線ノードのみが起動していくという仮定は難しく，無線ネットワーク中には複数の互いに独立したCNetが構成されている状況が生じるのが一般的である．従って，NEWは必ず単一のCNetと隣接しているという制限は不自然なものである．また，無線ノードの離脱時にも無線ネットワーク全体が常に連結であるという前提も不自然である．
【非特許文献１】Jiro Uchida, Islam.A.K.M.Muzahidul, Yoshiaki Katayama, Wei Chen and Koichi Wada, Construction and Maintenance of a Cluster-based Architecture for Sensor Networks, Hawaii International Conference on System Sciences(HICSS), 2006.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
そこで，本発明は内田らの提案したクラスタ構造とその構築・維持アルゴリズムに比べて，これらの問題点を解決したクラスタ構造とその構築・維持アルゴリズムを提供することを解決すべき課題としている。
【０００４】
つまり，NEWが複数のCNetに隣接する場合や，無線ノードが離脱する事で無線ネットワークが複数の部分ネットワークに分割される際にも，効率よくCNetを維持することが可能であるクラスタ構造と，それを構築・維持するためのアルゴリズムMove-In及びMove-Outを提供する．
これらの改良により，無線ネットワークを構成する無線ノードが互いに隣接する物から一つずつ起動させる必要がなくなり，無線ネットワーク中の任意の無線ノードから一つずつ起動させる事が可能になる．さらに，無線ネットワークから無線ノードが離脱した時に複数の部分ネットワークに分割される場合にも，効率よくクラスタ構造を構築・維持する事が可能になる．
【課題を解決するための手段】
【０００５】
本発明で提供するクラスタ構造及びクラスタ構造を構築・維持するアルゴリズムを内田らのものと比較して説明する．
・動作モデル
・内田らのアルゴリズムの動作モデル  
・新たな無線ノードは，一つのクラスタネットワークとのみ通信が可能な位置に発生する．
・CNetから無線ノードが離脱する時，無線ネットワークは複数に分割される事はない．
・本発明で提供するアルゴリズムの動作モデル  
・新たな無線ノードは，複数のクラスタネットワークと通信が可能な位置にも発生する．
・CNet から無線ノードが離脱する時，無線ネットワークが複数に分割される事がある．
・実行時間
・内田らのアルゴリズムの実行時間  
・単一のCNetと隣接する場所に新たに無線ノードが参加するとき，O(q)
q：新たに参加する無線ノードの無線ネットワーク上での次数(直接通信
が可能な無線ノードの数)
・CNetから無線ノードが離脱する時，O(|T|)
T：離脱する無線ノードを根とするＣＮｅｔ上での部分木
・本発明で提供するアルゴリズムの実行時間  
・単一のCNetと隣接する場所に新たに無線ノードが参加するとき，O(q)
・複数のCNetと隣接する場所に新たに無線ノードが参加するとき，
O(q+max|CNetのバックボーンツリー|)
・CNetから無線ノードが離脱する時，O(|T|)
以上の結果を表1にまとめる．
【０００６】
【表１】
2007221428.tif 000003
【０００７】
q：新たに発生した無線ノードNEWと隣接する無線ノードの数
P：クラスタネットワーク中のヘッドの数
T：ネットワークから退出する無線ノードDELを根とするCNet(G)上の部分木
【発明を実施するための最良の形態】
【０００８】
以下、本発明が提供するクラスタ構造及び該クラスタ構造を維持・構成するために各端末が具備するアルゴリズムを図面を参照しつつ説明する．
【実施例１】
【０００９】
本発明で対象としている無線ネットワークのモデルを以下に示す．
・無線ネットワークを構成する各ノードは完全に同期した時計を持ち，決められた時間（ラウンド）ごとにメッセージの送信か受信のどちらかを実行する．
・各ノードは等しい単一のチャネル(シングルチャネル)を用いて通信を行うためある無線ノードと直接通信が可能な距離にある複数の無線ノードが同じラウンドにメッセージを送信した場合，これらの信号の衝突(コリジョン)が生じ，その無線ノードはどのメッセージも受信することができない．この時，衝突が発生したことを検知することができない．つまり，あるノードがメッセージを受信できるのは直接通信が可能な無線ノードのうち，唯一つのみがメッセージを送信したときである．
・各無線ノードは固有の識別子(ＩＤ)を持っている．
・全ての無線ノードの送受信性能及び計算能力は等しいとする．
無線ノードを節点(ノード)とし，あるノードから他のノードへメッセージの送信が可能な場合，送信元ノードから受信ノードへ有向辺を引くことで無線ネットワークを有向グラフとして表現することができる．本研究で対象とする無線ネットワークモデルでは全ての無線ノードの送受信性能が等しいことから，あるノードAから他のノードBへメッセージの送信が可能な場合，BからAにもメッセージの送信が可能である．従って，それらのノード間には双方向に有向辺が引かれる事になる．そこで，本稿では扱う無線ネットワークを無向グラフG=(V,E)(ただしVはノードの集合，Eは無向辺(リンク)の集合)で表す．
次に、本発明で提供するクラスタネットワークについて説明する．
本発明で提供するクラスタネットワークを定義する．
クラスタネットワークとは，以下の性質を持つG上の部分グラフである．無向グラ
フで表現された無線ネットワークG=(V,E)中で互いに独立なノードの集合をヘッ
ドと呼び，各ヘッドを中心としたスターグラフをクラスタと呼ぶ．この時，ヘッ
ドのうち一つをルートと呼ぶ．一つのクラスタはヘッドとクラスタメンバによっ
て構成される．クラスタメンバであるノードは少なくとも一つのヘッドと隣接し(リンクを持ち)，また必ず一つのクラスタに所属している．
G上で互いに隣接する二つのクラスタを考える．G上で互いに隣接するクラスタのヘッド同士は特別なクラスタメンバであるゲートウェイと呼ばれるノードを介し
て連結される．一方のクラスタに所属するゲートウェイと，もう一方のクラスタに所属するヘッドがG上で隣接しているとき，二つのヘッドはこのゲートウェイを通じて連結する．つまり，一方のクラスタに所属しているゲートウェイと，もう一方のクラスタに所属するヘッドとの間にリンクを持つ．
G上で隣接するクラスタのヘッド間にこのようなゲートウェイが存在しない時，互いのクラスタのゲートウェイを一つずつ用いて連結する．ただし，ヘッドとゲートウェイからなるG上の部分グラフにサイクルが出来るような場合，ヘッドとゲートウェイ間にリンクを持たないとする．
以上より，隣接する二つのクラスタのヘッド同士は一つあるいは二つのゲートウェイを介して連結される．この時各ゲートウェイは必ず一つのヘッドとの間にリンクを持つ．このヘッドとゲートウェイによって構成される木構造をバックボーンツリー(BTree(G))と呼ぶ．クラスタメンバの内ゲートウェイ以外のノードをメンバと呼ぶ．
Gが以上のクラスタの定義を満たすとき，G上には以下に示す3 種類のリンクからなる部分グラフが存在する．このG上に存在する部分グラフをクラスタネットワークCNet(G)と呼ぶ．
1.ヘッド-ゲートウェイ間に存在するリンク
2.ゲートウェイ-ゲートウェイ間に存在するリンク
3.ヘッド-メンバー間に存在するリンク
図３にクラスタネットワークの一例を示す．なお，内田らの提案したクラスタネットワークでは，G上で隣接するクラスタのヘッド間は必ず一つのゲートウェイにより連結されている．
補題1.  本発明で提供するクラスタ構造を満たすCNet(G)は，一つのヘッドを根とした木構造になる．
証明.
提案するクラスタ構造の定義から，CNet(G)を構成するノードはヘッド，ゲートウェイ，メンバーのうちいずれか一つとなる．CNet(G)にはヘッドとゲートウェイから木構造であるバックボーンツリーが存在している．この時，残りのメンバーは自分が所属するクラスタのヘッドとの間にのみリンクを持ち，ゲートウェイ及び他のメンバーとの間に辺を持たないことから，CNet(G)上に存在する辺（リンク）でサイクルは発生しない．従って，CNet(G)は一つのヘッドをルートとした木構造とみなすことができる．
BTree(G)のサイズは，次の補題2，補題3 によって導かれる．
補題2.  次に示す3 つの条件を満たすノード数ｎの木においては，ノード数ｎに対して少なくとも（ｎ＋2）/（3）個のノードは黒いノードとなる．
条件1.  ノードは黒色か白色のどちらかである．
条件2.  葉は黒いノードとする．
条件3   白いノードから距離1以内に黒いノードが一つは存在する．
証明.
ｎ=1のとき，題意は条件より明らかに成立する．次に，ｎ≧2の場合について背理法によって証明する．
黒いノードの個数をPとしたとき，P＜（ｎ＋2）/3を満たすようなｎが最小となる木が存在すると仮定する．この時，ある一つの葉(Leaf)に注目し，その隣接する白いノード(w)の次数が2であるか3以上であるかに応じて以下の処理を実行する．
処理1  Leafの隣接する白いノードwの次数が2である
wの先で枝をカットし，Leafとwを取り除く
処理2  Leafの隣接する白いノードwの次数が3以上である
2-1  wの隣にLeaf以外の黒いノードが存在する時
wの手前で枝をカットし，Leafを取り除く
2-2  wの隣にLeaf以外の黒いノードが存在しない時
Leafをwとその隣に存在するいずれかの白いノードの間に挿入する
処理1の場合：ルールに反する事はない
処理2-1の場合：wから先にはLeafをカットする影響が及ばないため，ｗの手前でカットしてもルールには反しない
処理2-2の場合：Leafの移動によりｗの次数3以上の白ノードの次数を減らすことができる．これを繰り返すと必ず処理1か処理2-1が起こるようになる．
今回の条件下では，次数が2の白色のノードは2個以上連続しないため，カットする場合に黒ノード1個に対し高々2個の白ノードがカットされる．
したがって，カットした後のノード数をn’，黒ノードの数をp’とすると，
n’≧ｎ−1−2，  p’=p−1となる．従って，下記の数式１〜３が成立し，nの最小性に反する．従って，ノード数ｎに対して少なくとも（ｎ＋2）/（3）個のノードは黒いノードとなる．
【００１０】
【数１】
2007221428.tif 000004
【００１１】
【数２】
2007221428.tif 000005
【００１２】
【数３】
2007221428.tif 000006
【００１３】
補題3.  提案するCNet(G)におけるBTree(G)のサイズはヘッドの個数をPとしたとき最悪3P-2個である．
証明.
補題2において黒いノードをヘッド，白いノードをゲートウェイと考える時，明らかである．
以上の定義より，CNet(G)が持つ性質についてまとめる．
性質1.  CNet(G)にはヘッド，ゲートウェイ，メンバーが存在する．G上でヘッド同士は隣接する事はなく，ゲートウェイはCNet(G)上で必ず一つ以上のヘッドとの間にリンクを持つ．また，CNet(G)上でメンバーは一つのヘッドとの間にのみリンクを持つ．
性質2.  一つのヘッドをルートと呼ぶ．
性質3.  ヘッドとゲートウェイからなる木構造をバックボーンツリーと呼び，そのサイズはヘッドの個数をPとしたとき最悪3P-2個である．
提案するクラスタ構造を無線ネットワークに付与する事により，ネットワーク内へのブロードキャストを実行時間O（ヘッドの数）で行う事が可能である．この時，ブロードキャスト手法として非特許文献１で内田らが提案した次のブロードキャストアルゴリズムを利用する．
内田らによるブロードキャストアルゴリズム(Broad)
if(メッセージのソースノードsがメンバー)
THEN
sはメッセージを自分が所属するクラスタのヘッドに送信する；
sが所属するクラスタのヘッドはバックボーン上にメッセージを
深さ優先で送信する；
ELSE
sはバックボーン上にメッセージを深さ優先で送信する；
定理1.  提案するCNet（G）においてヘッドの個数をP 個としたとき，CNet内のブロードキャストは実行時間O（P)で可能である．
証明.
補題3より，バックボーンツリーのサイズはヘッドの個数をPとしたとき最悪3P-2である．この時，Broadを利用すると，CNet（G)でのブロードキャストは実行時間O（P）で実行が可能である．
次にクラスタ構造CNet(G)を構築・維持するための二つのアルゴリズムMove-In，Move-Outについて説明する．
新たなノードの発生時にはMove-Inアルゴリズムを，ノードの離脱時にはMove-Outアルゴリズムを実行することで，前記CNet(G)の構造を常に維持することが可能である．ただしこの時，一つのアルゴリズムの動作中に更にノードが発生または消失することはないものとする．
本発明で提供するアルゴリズムを実行するために，各ノードvは以下の情報を保持している．
・v.status ：ノードのステータス．「ヘッド」，「ゲートウェイ」，「メンバー」いずれかの値を持つ．
・v.prt ：CNet(G)上での親ノードのIDを値として持つ．
・v.chd ：CNet(G)上での子ノードのIDの集合を値として持つ．
・v.oneigh ：G上での隣接ノードのうち，CNet(G)上での親(v.prt)および子(v.chd)以外の隣接ノードのIDの集合を値として持つ．
・v.bneigh ：BTree(G)上での隣接ノードのIDの集合を値として持つ．
・v.root ：ノードの所属するCNet(G)上でのルートノードのID(ルートID)を値として持つ．
・G上で隣接するノードのステータスの集合
次に、無線ノードが新たに発生し，クラスタネットワークに参加するときに実行するMove-Inアルゴリズムについて説明する．ここで，無線ネットワークGへ新たに参加するノードをNEWとする．
Move-Inアルゴリズムは，NEWがCNet(G)に参加した後もCNetの性質を満たすようにNEWが保持する情報を決定する必要がある．NEWが新たに発生する時，NEWは隣接する全てのノードのステータス及びそれらのCNetのルートIDを確認する．この時隣接するノードが一つも無かった場合，NEW一つで新たなCNet(G)を構築する．隣接するノードから受け取ったルートIDが一つの時は，NEWの周囲にただ一つのCNetが存在する事を意味する．この場合，そのCNetにNEWを追加する．
一方，NEWが複数のルートIDを受信した時は，NEWの周囲に複数のCNetが存在する事を意味する．つまり，NEWの発生により今までお互いに独立だった複数のCNetが一つの大きなCNetになり，CNetが統合されるという事である．以下で，CNetの統合を効率よく可能にするアルゴリズムを提供する．
NEWが複数のCNetと隣接していた場合に実行するアルゴリズムの動作を順を追って説明する．
NEWは周囲に存在するCNetの中から親となるCNetを一つ選択し，残りのCNetを全て子供とする．この時，親として選択されたCNetのルートIDが，統一後のCNetのルートIDとなる．
図4，図5にNEWの発生によりCNetの統合が行われる一例を示す．この例では，3つのCNet(CNet:A，CNet:B，CNet:C)がNEWの発生により連結されるので，CNetの統合が実行される．  
Step1  NEWのステータス及び親ノード決定
NEWのステータスは周囲に存在するノードのステータスに応じて決定される．NEW
の隣接ノードとしてヘッドが存在する時NEWのステータスはゲートウェイとなり，
NEWの隣接ノードにヘッドが存在しない時NEW のステータスはヘッドとなる．
NEWのステータス決定後，NEWの親ノードが次の優先順位に従ってNEWの隣接ノードの中から一つ選択される．NEWが親を決定した時点で，親として選択されたノードのルートIDがNEWのルートIDとなる．
優先順1  ステータスがヘッドのノード
優先順2  ステータスがゲートウェイのノード
優先順3  ステータスがメンバーのノード
ここで，ステータスがメンバーのノードがNEWの親として選択された場合，
選択されたノードはステータスをゲートウェイに変更する．
図５に続き，図６に親ノード選択時の動作例を示す．この例では，隣接するヘッドが存在するのでNEWのステータスはゲートウェイとなる．またこの時，NEWは隣接する二つのヘッドの中からCNet:Aに属するヘッドを選択し，これを親としている．この時点で，NEWのルートIDは
CNet：A のルートID となっている．
Step2   NEWの子ノードの決定
NEWは自分と隣接するCNetの中で，自分と異なるルートIDを持つ全てのCNetから1
個ずつ子供のノードを選択する．この時それぞれのCNetからNEWが子供として選択
するノードの優先順位は以下の通りである．NEWの子供として選択されたノードは
新しいルートIDがNEWより伝達され，ルートIDを変更する．
優先順1  ステータスがヘッドのノード
優先順2  ステータスがゲートウェイのノード
優先順3  ステータスがメンバーのノード
ここで，ステータスがメンバーのノードがNEWの子供として選択された場合，選択されたノードはステータスをゲートウェイに変更する．
図６に続き，NEWが行う子ノード選択の一例を図７に示す．この例では，NEWは
CNet:Bからヘッドを子供として選択し，またCNet:Cから二つのメンバーのうちから一つを子供と選択している．この時，子供として選択されたノードのステータスがメンバーからゲートウェイに変化している．
NEWの子供として選択されたノード(uとする)は，自分の親をNEWに変更する．こ
れと同時に，uはuが属していたCNetに対して新しいルートIDをブロードキャスト
する．この時，uからルートまでの経路上のノードは，自分のルートIDを更新すると共に親子関係を逆転させる．ルートは自分のルートIDを新しいルートIDに変更後，Broadを用いてルートIDをブロードキャストする．
図７に示した例において，NEWの子供よりバックボーン上の親子関係を変更し，ルートIDのブロードキャストを実行すると，図８に示すようにCNetの統合は完了する．
補題4.  新たに発生するノードNEWの隣接ノードの数がq 個の時，NEWはq 個の隣接ノードを1からqまでO(q)ラウンドで順番付けする事が可能である．
証明.
非特許文献１,Lemma6にて証明されている．
Move-Inアルゴリズム中で各ノードが送信するメッセージや述語を説明する．
・AddMe ：新規に発生するノードが送信するメッセージ
AddMe.ID :=自分のID
・Mystatus ：AddMeメッセージを受信したノードがが送信するメッセージ
Mystatus.ID :=自分のID
Mystatus.root :=自分のルートID
・ChangeMyStatus ノードがステータスを変更した事を隣接ノードに連絡するメッセージ
ChangeMyStatus.ID :=自分のID
ChangeMyStatus.status :=自分の新しいステータス
・ImYourChild：送信元のノードが宛先のノードの子供になる際に用いるメッセージ
ImYourChild.status :=自分のステータス
ImYourChild.ID:=自分のID
ImYourChild.To:=宛先のID
・ImYourParent：送信元のノードが宛先のノードの親になる際に用いるメッセージ
ImYourParent.status :=自分のステータス
ImYourParent.ID :=自分のID
ImYourParent.To :=宛先のID
ImYourParent.root:=自分のルートID
MinID(status)：隣接するノードのうちステータスがstatusの物で，一番小さなIDを持つノードのID
Move-In アルゴリズムを以下に示す．
・NEWが実行する動作
CNetに参加するノードNEWは隣接するノードに1からqまで番号を割り振り，
1からqまで順番にAddMeメッセージを送信；
WHILE(隣接するq個のノードの中にAddMeメッセージを未送信のノードが存在)｛
NEWはAddMeメッセージを未送信のノードへAddMeメッセージを送信する；
MyStatusメッセージの受信を待つ；
｝
IF(NEWがルートIDを一つも受信せず)
THEN
NEW.status := ヘッド；
NEW.root := NEW.ID；
ELSE IF( NEW がルートID を一つのみ受信)
THEN
IF(NEW と隣接するノードの中にヘッドが存在)
THEN
NEW.status := メンバー；
MinID(ヘッド) にImYourChild メッセージを送信；
NEW.root := MinID(ヘッド) のルートID；
NEW.prt := MinID(ヘッド)；
NEW.oneigh := MinID(ヘッド) 以外の隣接ノードのID；
ELSE IF(NEW と隣接するノードの中にゲートウェイが存在)
THEN
NEW.status := ヘッド；
MinID(ゲートウェイ) にImYourChild メッセージを送信；
NEW.root := MinID(ゲートウェイ) のルートID；
NEW.prt := MinID(ゲートウェイ)；
NEW.bneigh := MinID(ゲートウェイ)；
NEW.oneigh := MinID(ゲートウェイ) 以外の隣接ノード；
ELSE
NEW.status := ヘッド；
MinID(メンバー) にImYourChild メッセージを送信；
NEW.root := MinID(メンバー) のルートID；
NEW.prt := MinID(メンバー)；
NEW.bneigh := MinID(メンバー)；
NEW.oneigh := MinID(メンバー) 以外の隣接ノード；
ELSE //NEW が複数のルートID を受信
THEN
IF(NEW と隣接するノードの中にヘッドが存在)
THEN
NEW.status := ゲートウェイ；
MinID(ヘッド) にImYourChild メッセージを送信；
NEW.root := MinID(ヘッド) のルートID；
NEW.prt := MinID(ヘッド)；
NEW.bneigh := MinID(ヘッド)；
NEW.oneigh := MinID(ヘッド) 以外の隣接ノードのID；
ELSE IF(NEW と隣接するノードの中にゲートウェイが存在)
THEN
NEW.status := ヘッド；
MinID(ゲートウェイ) にImYourChild メッセージを送信；
NEW.root := MinID(ゲートウェイ) のルートID；
NEW.prt := MinID(ゲートウェイ)；
NEW.bneigh := MinID(ゲートウェイ)；
NEW.oneigh := MinID(ゲートウェイ) 以外の隣接ノード；
ELSE
NEW.status := ヘッド；
MinID(メンバー) にImYourChild メッセージを送信；
NEW.root := MinID(メンバー) のルートID；
NEW.prt := MinID(メンバー)；
NEW.bneigh := MinID(メンバー)；
NEW.oneigh := MinID(メンバー) 以外の隣接ノード；
WHILE(NEW の親または子供が未選択のCNet が存在する)｛
IF(NEW の親または子供を未選択のCNet 中にNEW と隣接するヘッドが存在)
THEN
親と子供を未選択のCNet 中でのMinID(ヘッド) にImYourParent メッセージを送信；
NEW.chd に親または子供を未選択のCNet 中でのMinID(ヘッド) を追加；
NEW.bneigh に親または子供を未選択のCNet 中でのMinID(ヘッド) を追加；
NEW.oneigh からMinID(ヘッド) を削除；
ELSE IF(NEW の親または子供を未選択のCNet 中にNEW と隣接するゲートウェイが存在)
THEN
親と子供を未選択のCNet 中でのMinID(ゲートウェイ) にImYourParent メッセージを送信；
NEW.chd に親または子供を未選択のCNet 中でのMinID(ゲートウェイ) を追加；
NEW.bneigh に親または子供を未選択のCNet 中でのMinID(ゲートウェイ) を追加；
NEW.oneigh からMinID(ゲートウェイ) を削除；
ELSE
親と子供を未選択のCNet 中でのMinID(メンバー) にImYourParent メッセージを送信；
NEW.chd に親または子供を未選択のCNet 中でのMinID(メンバー) を追加；
NEW.bneigh に親または子供を未選択のCNet 中でのMinID(メンバー) を追加；
NEW.oneigh からMinID(メンバー) を削除；
｝END WHILE
・NEW以外のノードPi が実行する動作
IF(AddMe メッセージを受信)
THEN
NEW へMyStatus メッセージを送信；
IF(ImYourChild メッセージを受信)
THEN
IF(ImYourChild.To == Pi.ID)
THEN
Pi.chd := Pi.chd [ ImYourChild.ID；
IF( ImYourChild.status がヘッドかゲートウェイ)
Pi.bneigh := Pi.chd [ ImYourChild.ID；
IF(Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh := Pi.prt；
Pi はChangeMyStatus メッセージを送信；
ELSE
Pi.oneigh := Pi.oneigh [ ImYourChild.ID；
ID がImYourChild.ID のノードのステータスをImYourChild.status に変更；
IF(ImYourParent メッセージを受信)
THEN
IF(ImYourParent.To == Pi.ID)
THEN
Pi.root := ImYourParent.root；
IF(Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh にPi.prt とImYourParent.ID を追加
Pi はChangeMyStatus メッセージを送信；
Pi.prt へImYourParent メッセージを送信；
Pi.chd := Pi.prt；
Pi.prt := ImYourParent.ID；
ELSE IF(Pi がCNet のルート)
THEN
Pi.chd にImYourParent.ID があればこれを削除；
Pi.prt := ImYourParent.ID；
Pi.root をBroad を用いてブロードキャスト；
ELSE
Pi.chd にImYourParent.ID があればこれを削除；
Pi.prt へImYourParent メッセージを送信；
Pi.chd := Pi.chd [ Pi.prt；
Pi.prt := ImYourParent.ID；
IF(ChangeMyStatus メッセージを受信した)
THEN
ID がChangeMyStatus.ID のノードのステータスをChangeMyStatus.status に変更；
IF(Pi.chd にChangeMyStatus.ID が含まれる)
Pi.bneigh := Pi.bneigh [ ChangeMyStatus.ID；
本発明が提供するアルゴリズムの正当性の証明を以下のように行う．
補題5.  提案アルゴリズムの実行により複数のCNet が一つに統一されたCNet では，ヘッド同士は隣接しない
証明.
Move-In アルゴリズムの実行により新たなヘッドが発生するのはNEW がヘッドになる場合だけであり，この時NEW の隣接ノードにヘッドが存在しないことは，アルゴリズムより明らかである．
補題6.  提案アルゴリズムの実行により複数のCNet が一つに統一されたCNet では，全てのゲートウェイの隣に少なくとも一つのヘッドが存在する
証明.
Move-In アルゴリズムより，NEWがゲートウェイになる場合，その隣には必ずヘッドは存在する．
また，NEWの親もしくは子供がメンバーだったときステータスがゲートウェイに変化する．この時メンバーの定義より，その隣には必ずヘッドが存在する．
補題7.  提案アルゴリズムの実行により複数のCNet が一つに統一されたCNet では，メンバーは一つのヘッドとの間にのみ辺を持つ．
証明.
Move-In アルゴリズムの実行により新たなメンバーが発生する時，親であるヘッドとの間にのみ辺を持つ．また，CNet の統合によりメンバーが子供を持つ場合，Move-In アルゴリズムよりメンバーのステータスはゲートウェイに変化する．従って，メンバーは一つのヘッドとの間にのみ辺を持つ．
補題8.  提案アルゴリズムの実行により複数のCNet が一つに統合されたCNet では，全てのノードが保持するルートID が等しい
証明.
提案アルゴリズムによるCNet の統合では，NEW の親として選択されたCNet のルートが統合後全体のルートとなる．このルートID がNEW を介して統合されるCNet にブロードキャストされる事で，統合後の一つになったCNet に対しルートID を一つだけにしている．
補題9.  提案アルゴリズムの実行により複数のCNet が一つに統一されたCNet は，一つのヘッドを根とした木構造となる
証明.
NEWが子供を選択した時，子供となったノードはMove-In アルゴリズムより，所属していたCNetのルートまで親子関係が入れ替わる．このように親子関係を逆転させることで，全ての統合されるCNet はNEW を根とする一つの木構造となる．
定理2.  Move-In アルゴリズムにより複数のCNet の統合が行われた結果，新しくできるネットワークもCNet の性質を満たしている
ここで，前述したCNet(G)が持つ性質を再掲する．
性質1. CNet(G) にはヘッド，ゲートウェイ，メンバーが存在する．G 上でヘッド同士は隣接する事はなく，ゲートウェイはCNet(G) 上で必ず一つ以上のヘッドとの間にリンクを持つ．また，CNet(G) 上でメンバーは一つのヘッドとの間にのみリンクを持つ．
性質2. 一つのヘッドをルートと呼ぶ．
性質3. ヘッドとゲートウェイからなる木構造をバックボーンツリーと呼び，そのサイズはヘッドの個数をP としたとき最悪3P-2 個である．
証明.
補題5，補題6 より，ヘッド同士は隣接せず，またゲートウェイの隣には必ず一つ以上のヘッドが存在する．また，補題7 より，メンバーは一つのヘッドとの間にのみ辺を持つ．従って，CNet の性質1 は満たされる．
補題8，補題9 より，CNet の性質2 は満たされる．
補題6 より，ゲートウェイの隣には必ず一つ以上のヘッドが存在する．従って，補題3 よりバックボーンツリーのサイズはヘッドの個数をP 個とした時最悪3P-2 個となりCNet の性質3 は満たされる．
従って，Move-In アルゴリズムの実行後，CNet の性質は満たされる．
定理3.  Move-In アルゴリズムは，無線ネットワーク中に新たにノードが発生したときに，CNet(G)を正しく構築・維持するアルゴリズムであり，この時実行時間はO(q + max｛統合されるCNetのBTree(G) のサイズ(ノード数)｝) ラウンドとなる
証明.
補題4 より，NEW は隣接ノードに対して1 からq までO(q) ラウンドで番号を割り振る．その後，それらq 個の隣接ノードがステータス及びルートID をNEW に送信するのにO(q) ラウンド必要である．更に，NEWは親と子供を選択するメッセージを送信するのにO(q) ラウンド必要である．加えてNEW の子供となったCNet へ新しいルートID をブロードキャストし，ルートまで親子関係を逆転するが，これはそれぞれの部分木に対して定理1 より，O(統合されるCNet のBTree(G)のサイズ) ラウンドで実行可能である．従って，全ての統合されるCNet に同時にブロードキャストを実行する事で，実際に必要なのは統合されるCNet のうち最大の物が完了するまでの実行時間である．以上より，Move-In アルゴリズムの実行に必要な実行時間は，NEWに隣接するノードの数をq とする時O(q + max｛統合されるCNet のBTree(G) のサイズ｝) ラウンドとなる．
次に、クラスタネットワークCNet（G） からノードが離脱するときに実行するMove-Out アルゴリズムについて説明する．ここではCNet(G) から離脱しようとするノードをDEL とし，DEL.chd の数をq，DEL を根とするCNet(G) 上の部分木をT，DEL.chd を根とするCNet(G)上の部分木を(T1,T2,T3,...,Tq)，CNet(G) のルートをR，及びCNet(G) からT を除いたR を含む部分木をH とする (参照:図９) ．
CNet(G) からDEL が退出するときMove-Out アルゴリズムは(T1,T2,T3,...,Tq) のうちH と繋がっている部分木を再びH へと統合する必要がある．また，Move-Out アルゴリズムはDEL が離脱する事でH から独立する部分木に対しては新たにルートを設定し，新しいCNet として独立させる必要がある．
そこで，(T1,T2,T3,...,Tq) の中でDEL の退出によりH から独立する可能性のある部分木を発見するために，DEL の子ノードのID を新しいルートID としてそれぞれの部分木内に伝達する．
図１０にルートID 伝達の例を示す．
それぞれの部分木のルートID が更新された後に全ての部分木内を探索して，各部分木が隣接する部分木のルートID をDEL に集める．この作業を行う事で，DEL.chd を根とする部分木(T1,T2,T3,...,Tq) を次の3 グループに分類する事が出来る．図１１にグループ分けの例を示す．
Group1 隣接する部分木が存在し，H と連結である部分木
いくつかの部分木と連結しており，その中にH との間にリンクが存在する部分木がGroup1に分類される．図１１の例では，H と連結であるT1 がこのGroup1 に分類される．さらにこの時，T1 と連結であるT2，更にT2 と連結であるT3 もまたH と連結であることになり， Group1 に分類される．
Group2 隣接する部分木が存在するが，H と繋がらない部分木
いくつかの部分木と連結してはいるが，そのいずれの部分木の中にもH との間にリンクが存在しない部分木はこのGroup2 に分類される．図１１ の例では，T3 とT4 及びT5 がこのGroup2 に分類される．
Group3 孤立する部分木
他の部分木との間に一切辺を持たない部分木がGroup3 に分類される．図3.8 の例ではT7が他の部分木との間にリンクを持たず，Group3 に分類される．
上のように分類されたそれぞれの部分木に対して，DEL はCNet の統合処理を実行する．DELはGroup1 に所属する部分木の中で，H と連結である部分木から順番に統合を実行する．また，Group2 に所属する部分木に対しては，どれか一つを新たなCNet とし，それに隣接するものから統合を実行する事を繰り返す．H から独立する部分木に対しては，新たなルートID を決定して処理を終了する．
本発明が提供するMove-Out アルゴリズムの動作を順を追って説明する．
Step1 DEL.prt,(DEL.prt).prt,DEL.chd のステータス変更
DEL の離脱により，子供を持たないゲートウェイや隣接ノードにヘッドを持たないようなゲートウェイやメンバーが発生しないように，DEL.prt,(DEL.prt).prt 及びDEL.chd は自分自身のステータスを変更する場合がある．
Step2 DEL.chd を根とする部分木に新しいルートID の伝達
(T1,T2,T3,...) の統合を実行するために必要なそれぞれの部分木の隣接情報を調べるために，DEL.chd が自分のID をそれぞれ自分を根とするCNet(G) 上の部分木へルートID として通達する．
Step3 DEL.chd を根とする部分木の隣接情報収集
(T1,T2,T3,...) 内を探索し，各部分木が隣接する部分木のルートID をDEL へと返す．
Step4 DEL.chd を根とする部分木の統合(再統合)
次の手順に従って隣接する部分木へと統合させる．
手順1 ：DEL はH と隣接する部分木に対してH に統合するように命令
手順2 ：DEL はH と隣接する部分木がなくなるまで手順1 を繰り返す
手順3 ：DEL は残りの部分木のうち一つに対し，新しいCNet になるように命令
手順4 ：DEL は手順3 で構成されたCNet に隣接する部分木に対し，手順3 で構
成されたCNet に統合するように命令
手順5 ：DEL は手順3 で構成されたCNet と隣接する部分木がなくなるまで，手
順4 を繰り返す
手順6 ：DEL は全ての部分木に命令を出し終わるまで手順3 から手順5 を繰り
返す
Move-Out アルゴリズム中で各ノードが送信するメッセージや述語を説明する．
・Leave ：CNet から退出するノードDEL が送信メッセージ
Leave.ID := 自分のID Leave.status := 自分のステータス
・ChangeMyStatus ノードがステータスを変更した事を隣接ノードに連絡するメッセージ
ChangeMyStatus.ID := 自分のID
ChangeMyStatus.status := 自分の新しいステータス
・CheckYourChd ：宛先のノードに子供が存在するかを確認させる時に用いるメッセージ
CheckYourChd.ID := 自分のID CheckYourChd.To := 宛先のID
・ChangeRootID DEL.chd を根とする部分木のルートID を変更する時に用いるメッセージ
ChangeRootID.ID := 自分のID
ChangeRootID.To := 宛先のID
ChangeRootID.root := 自分のルートID
・CheckYourNeighbors ：DEL.chd を根とする部分木の隣接状況を調べるときに用いるメッセージ
ChechYourNeighbors.list := 隣接する部分木のルートID を集めるリスト型の変数
ChechYourNeighbors.To := 宛先のID
・MergeToNeighbor.ID ：送信元のノードが宛先のノードの親になる際に用いるメッセージ
MergeToNeighbor.ID := 統合先の部分木が持つルートID
MergeToNeighbor.To := 宛先のID
MergeToNeighbor.flag := 統合が実行済みかどうかを示すフラグ．実行済みの時TRUE，未実行の時FALSE
・Independence ：DEL.chd を根とする部分木を独立させる時に用いるメッセージ
Independence.To := 宛先のID
・ImYourChild ：送信元のノードが宛先のノードの子供になる際に用いるメッセージ
ImYourChild.status := 自分のステータス
ImYourChild.ID := 自分のID
ImYourChild.To := 宛先のID
・ImYourParent ：送信元のノードが宛先のノードの親になる際に用いるメッセージ
ImYourParent.ID := 自分のID
ImYourParent.To := 宛先のID
・MinID(status) ：隣接するノードのうちステータスがstatus の物で，一番小さなID を持つノードのID
・MinID(status,root) ：隣接するノードのうちルートID がroot かつステータスがstatus の物で，一番小さなID を持つノードのID
提案するMove-Out アルゴリズムの動作を順を追って説明する．
・DELが実行する動作
CNet から離脱するノードDEL はLeave メッセージを送信；
WHILE(DEL はChangeRootID メッセージを未送信の子供を持つ)｛
DEL はChangeRootID メッセージを未送信の子供にChangeRootID メッセージを送信；
｝END WHILE
WHILE(DEL はCheckYourNeighbors メッセージを未送信の子供を持つ)｛
CheckYourNeighbors メッセージを未送信の子供にCheckYourNeighbors メッセージを送信する；
｝END WHILE
DEL はDEL.chd を根とする部分木それぞれの隣接ルートID リストより，
各部分木の再統合を実行する順番及び統合先の部分木を決定する；
WHILE(MergeToNeighbor メッセージ又はIndepentence メッセージを未送信の子供を持つ)｛
IF( DEL に統合が実行可能でMergeToNeighbor メッセージを未送信の子供が存在する)
THEN
統合が可能でMergeToNeighbor メッセージを未送信の子供にMergeToNeighbor メッセージを
送信する；
ELSE
MergeToNeighbor メッセージまたはIndependence メッセージを未送信の子供にIndependence
メッセージを送信する；
｝END WHILE
・DEL以外のノードPi が実行する動作
IF(Leave メッセージを受信)
THEN
IF(Leave.ID がPi.chd に含まれる)
THEN
Pi.chd からLeave.ID を削除；
IF( Leave.status == ヘッド)
THEN
IF( Pi.prt.status == ゲートウェイ)
THEN
IF( Pi は子供を持たない)
THEN
IF( Pi.oneigh の中にステータスがヘッドのノードが存在)
THEN
Pi はPi.prt にCheckYourChd メッセージを送信；
Pi.status := メンバー；
Pi はMinID(ヘッド) にImYourChd メッセージを送信；
Pi.prt := MinID(ヘッド)；
ELSE
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
IF( Pi.chd の中にステータスがヘッドのノードが存在しない)
THEN
IF( Pi.oneigh の中にステータスがヘッドのノードが存在)
THEN
Pi はPi.prt にCheckYourChd メッセージを送信；
Pi.prt := MinID(ヘッド)；
ELSE
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
IF( Pi は子供を持たない)
THEN
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
ELSE IF( Leave.status == ゲートウェイ)
THEN
IF( Pi.status == ゲートウェイ)
THEN
IF( Pi は子供を持たない)
Pi.status := メンバー；
Pi はMinID(ヘッド) にImYourChd メッセージを送信；
ELSE IF( Leave.ID == Pi.prt )
THEN
IF( Leave.status == ヘッド)
THEN
IF( Pi.status == ゲートウェイ)
THEN
IF( Pi は子供を複数持つ)
THEN
IF( Pi.oneigh 及びPi.oneigh の中にヘッドのノードが存在しない)
THEN
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
IF( Pi.oneigh 及びPi.oneigh の中にヘッドのノードが存在しない)
THEN
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
IF( Pi.status == メンバー)
THEN
IF( Pi.oneigh の中にステータスがヘッドのノードが存在しない)
THEN
Pi.status := ヘッド；
Pi はChangeMyStatus メッセージを送信；
ELSE IF( Leave.status == ゲートウェイ)
THEN
IF( Pi.status == ゲートウェイ)
THEN
IF( Pi は子供を一つだけ持つ)
THEN
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
ELSE IF( Leave.ID がPi.oneigh に含まれる)
THEN
Pi.oneigh からLeave.ID を削除；
IF( ChangeRootID メッセージを受信した)
THEN
IF( ChangeRootID.To == Pi.ID )
THEN
IF( ChangeRootID.ID == Leave.ID )
THEN
Pi.root := Pi.ID；
WHILE(ChangeRootID メッセージを未送信の子供を持つ)｛
Pi はChangeRootID メッセージを送信；
｝
ELSE IF( ChangeRootID.ID == Pi.prt )
THEN
Pi.root := ChangeRootID.ID
WHILE(ChangeRootID メッセージを未送信の子供を持つ)｛
Pi はChangeRootID メッセージを送信；
｝
IF( CheckYourNeighbors メッセージを受信した)
THEN
IF( CheckYourNeighbors.To == Pi.ID )
THEN
IF( CheckYourNeighbors.list に存在しない(Pi.oneigh).root が存在)
THEN
CheckYourNeighbors.list に存在しない(Pi.oneigh).root を追加；
WHILE(ChangeYourNeighbors メッセージを未送信の子供を持つ)｛
CheckYourNeighbors メッセージを未送信の子供にCheckYourNeighbors メッセージを
送信する；
IF( MergeToNeighbor メッセージを受信した)
THEN
Pi.root := MergeToNeighbor.ID
IF( MergeToNeighbor.ID がPi.oneigh に含まれる)
THEN
IF( MergeToNeighbor.flag == FALSE )
THEN
MergeToNeighbor.flag := TRUE；
Pi.prt へImYourParent メッセージを送信；
IF( Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh := Pi.prt；
Pi はChangeMyStatus メッセージを送信；
IF(Pi.oneigh にルートID がMergeToNeighbor.ID でヘッドのノードが存在)
THEN
Pi はMinID(ヘッド,MergeToNeighbor.ID) へImYourChild メッセージを送信；
Pi.bneigh := Pi.bneigh [ MinID(ヘッド,MergeToNeighbor.ID)
Pi.oneigh からMinID(ヘッド,MergeToNeighbor.ID) を削除；
Pi.prt := MinID(ヘッド,MergeToNeighbor.ID)；
ELSE IF(Pi.oneigh にID がMergeToNeighbor.ID でステータスがゲートウェイのノードが存在)
THEN
Pi はMinID(ゲートウェイ,MergeToNeighbor.ID) へImYourChild メッセージを送信；
Pi.bneigh := Pi.bneigh [ MinID(ゲートウェイ,MergeToNeighbor.ID)；
Pi.oneigh からMinID(ゲートウェイ,MergeToNeighbor.ID) を削除；
Pi.prt := MinID(ゲートウェイ,MergeToNeighbor.ID)；
ELSE
Pi はルートID がMergeToNeighbor.ID のノードの中でのMinID(メンバー) へ
ImYourChild メッセージを送信；
Pi.bneigh := Pi.bneigh [ MinID(メンバー,MergeToNeighbor.ID)；
Pi.oneigh からMinID(メンバー,MergeToNeighbor.ID) を削除；
Pi.prt := MinID(メンバー,MergeToNeighbor.ID)；
WHILE(MergeToNeighbor メッセージを未送信の子供が存在する)｛
MergeToNeighbor メッセージを未送信の子供にMergeToNeighbor メッセージを送信する；
｝
IF(Independence メッセージを受信)
THEN
IF(Independence.To == Pi.ID)
THEN
IF( Pi.status がゲートウェイもしくはメンバー)
THEN
Pi.chd の中でのMinID(ヘッド) にImYourChild メッセージを送信；
Pi.prt := Pi.chd の中でのMinID(ヘッド)；
Pi.chd からPi.chd の中でのMinID(ヘッド) を削除；
IF(ImYourChild メッセージを受信)
THEN
IF(ImYourChild.To == Pi.ID)
THEN
Pi.chd := Pi.chd [ ImYourChild.ID；
Pi.bneigh := Pi.chd [ ImYourChild.ID；
IF(Pi.status == メンバー)
THEN
Pi.status := ゲートウェイ；
Pi.bneigh := Pi.prt；
Pi はChangeMyStatus メッセージを送信；
ELSE
ID がImYourChild.ID のノードのステータスをImYourChild.status に変更；
IF(ImYourParent メッセージを受信)
THEN
IF(ImYourParent.To == Pi.ID)
THEN
Pi.prt へImYourParent メッセージを送信；
Pi.chd := Pi.chd [ Pi.prt；
Pi.prt := ImYourParent.ID；
IF(ChangeMyStatus メッセージを受信した)
THEN
ID がChangeMyStatus.ID のノードのステータスをChangeMyStatus.status に変更；
IF( ChangeMyStatus.status == メンバー)
THEN
IF(Pi.bneigh にChangeMyStatus.ID が含まれる)
Pi.bneigh からChangeMyStatus.ID を削除；
ELSE
IF(Pi.chd にChangeMyStatus.ID が含まれる)
Pi.bneigh := Pi.bneigh [ ChangeMyStatus.ID；
IF( CheckYourChd メッセージを受信した)
THEN
IF(CheckYourChd.To == Pi.ID)
THEN
Pi.chd よりCheckYourChd.ID を削除；
IF( Pi は子供を持たない)
THEN
Pi.status := メンバー；
Pi はChangeMyStatus メッセージを送信；
DEL がCNet（G) より離脱する事により，次の条件を一つでも満たすノードはCNet（G） を構成するために保持する情報の内容が変化する可能性がある．
条件1  DEL.prt,(DEL.prt).prt,DEL.chd のいずれか
DEL が離脱する事により，隣接するヘッドが居なくなってしまうノードや次数が1 となってしまうゲートウェイ等CNet の定義に反する事になるノードが発生する事がある．Move-Outアルゴリズムはそのようなノードの保持する情報をCNet の性質を満たすような正しい内容へと変化させなければならない．
条件2  DEL.chd を根とする部分木に属するノード(T1,T2,T3,...,Tq)
DEL.chd を根とする部分木はG 上において互いに非連結になる可能性があるため，これらの部分木に属するノードは保持する情報が変化する可能性がある．また，H へ統合されるときに部分木内部の親子関係が変化する可能性がある．
条件3  H の中で条件2 を満たすノードに隣接するノードH に属するノードのうち，DEL を根とするCNet(G) 上の部分木中に存在するノード(v とする) と隣接するノードはCNet の統合時にv を子供とする可能性がある．また，そのノードがステータスが変化する可能性がある．
従って，これらのノードがアルゴリズムの実行後もCNet の定義を満たしている事を以下に示す．
補題10.  DEL がヘッドの時，提案アルゴリズムの実行後DEL.prt,(DEL.prt).prt のステータスはCNet(G) の性質1 に反しない
証明.
CNet を構成するためにノードが保持する情報の内容より，DEL.prt は以下の条件の組み合わせにより分類する事ができる．ただし，DEL がヘッドの時DEL.prt はCNet の定義よりゲートウェイである．これにより、ゲートウェイの親となる(DEL.prt).prt のステータスはヘッドかゲートウェイのいずれかである．
条件1.  (DEL.prt).prt のステータスがヘッドかゲートウェイか
(a) ヘッド  (b) ゲートウェイ
条件2. DEL.prt はDEL 以外に子供を持つか持たないか
(a) 持つ  (b) 持たない
条件3. DEL.prt は子供にDEL 以外のヘッドを持つか持たないか
(a) 持つ  (b) 持たない
条件4. DEL.prt はG 上の隣接ノードにDEL 以外のヘッドを持つか持たないか
(a) 持つ  (b) 持たない
条件1〜4の組み合わせを表２に示す．
【００１４】
【表２】
2007221428.tif 000007
【００１５】
DEL がヘッドの時に提案するMove-Out アルゴリズムを実行すると，表２に示した１６通りのDEL.prt は以下のように動作する．
No1 DEL.prt はアルゴリズムの動作後ゲートウェイのままとなる
このDEL.prt はDEL の離脱後，親にヘッドを持ち，同時に子供も持つため，Move-Out アルゴリズムによる影響を受けない．この時DEL.prt はゲートウェイのままでCNet(G) の性質を満たす．
No2 DEL.prt はアルゴリズムの動作後ゲートウェイのままとなる
No1 と同様である．
No3 DEL.prt はアルゴリズムの動作後ゲートウェイのままとなる
No1 と同様である．
No4 DEL.prt はアルゴリズムの動作後ゲートウェイのままとなる
No1 と同様である．
No5 DEL.prt はアルゴリズムの動作後メンバーになる
このDEL.prt はDEL の離脱後，親にヘッドを持つが子供を持たないので，Move-Out アルゴリズムによってステータスがメンバーになりCNet(G) の性質を満たす．
No6 DEL.prt はアルゴリズムの動作後メンバーになる
No5 と同様である．
No7 DEL.prt はアルゴリズムの動作後メンバーになる
No5 と同様である．
No8 DEL.prt はアルゴリズムの動作後メンバーになる
No5 と同様である．
No9 DEL.prt はアルゴリズムの動作後ゲートウェイのままとなる
DEL の離脱後，DEL.prt は親がゲートウェイだが子供にヘッドを持つため，Move-Out アルゴリズムによる影響を受けない．この時DEL.prt はゲートウェイのままでCNet(G) の性質を満たす．
No10 DEL.prt はアルゴリズムの動作後ゲートウェイのまま
No9 と同様である．
No11 DEL.prt はアルゴリズムの動作後親が変更される
DEL の離脱後，DEL.prt は親にも子供にもヘッドが存在しなくなるがDEL.oneigh の中にヘッドが存在するため，Move-Out アルゴリズムによって親を変更することで，DEL.prt はステータスをゲートウェイのままCNet（G) の性質を満たす．この時，ゲートウェイである（DEL.prt）.prt に子供がいなくなるとき，そのステータスもMove-Out アルゴリズムによってメンバーへと変更されるため，この時CNet(G) の性質を満たす．
No12 DEL.prt はアルゴリズムの動作後ヘッドになる
DELの離脱後，DEL.prt の隣接ノードの中にヘッドは存在しなくなるため，DEL.prt がMove-Out アルゴリズムによってステータスがヘッドになりCNet（G) の性質を満たす．
No13 DEL.prt はアルゴリズムの動作後メンバーになり，親が変更される
DEL の離脱後，DEL.prt は親がゲートウェイであり子供を持たないがDEL.oneigh の中にヘッドが存在するため，DEL.prt はMove-Out アルゴリズムによってステータスをメンバーにし，親を変更することでCNet（G) の性質を満たす．この時，（DEL.prt）.prt に子供がいなくなるとき，そのステータスもMove-Out アルゴリズムによって変更されるため，CNet(G)の性質を満たす．
No14 DEL.prt はアルゴリズムの動作後ヘッドになる
DEL の離脱後，DEL.prt の隣接ノードの中にヘッドは存在しなくなるため，Move-Out アルゴリズムによってステータスがヘッドになりCNet（G) の性質を満たす．
No15 DEL.prt はアルゴリズムの動作後メンバーになり，親が変更される
No13 と同様である．
No16 DEL.prt はアルゴリズムの動作後ヘッドになる
No14 と同様である．
従って，いずれの場合もMove-Out アルゴリズムの実行により，DEL.prt 周辺のステータスは維持される．
補題11.  DELがヘッドの時，Move-Out アルゴリズムの実行後DEL.chd のステータスはCNet(G)の性質１に反しない
証明.
CNet を構成するためにノードが保持する情報の内容より，DEL.chd は以下の条件の組み合わせにより分類する事ができる．ただしDEL がヘッドの時，DEL.chd はCNet の定義よりゲートウェイもしくはメンバーである．
条件1. DEL.chd のステータスがゲートウェイかメンバーか
(a) ゲートウェイ  (b) メンバー
条件2. DEL.chd が持つ子供の数
(a)2 個以上持つ  (b)1 個しか持たない
条件3. DEL.chd は隣接ノードにDEL 以外のヘッドを持つか持たないか
(a) 持つ  (b) 持たない
条件１〜３の組み合わせを表３に示す．
【００１６】
【表３】
2007221428.tif 000008
【００１７】
DEL がヘッドの時に提案するMove-Out アルゴリズムを実行すると，表3.2 に示した8 通りのDEL.chd は以下のように動作する．
No1 DEL.chd はアルゴリズムの動作後ゲートウェイのままとなる
DEL の離脱後，ゲートウェイであるDEL.chd は子供を複数持っており，また隣接ノードの中にヘッドが存在する．統合の実行の際そのヘッドの子供になることでCNet(G) の性質を満たす．
No2 DEL.chd はアルゴリズムの動作後ヘッドとなる
DEL の離脱後，ゲートウェイであるDEL.chd は子供を複数持つが，隣接するヘッドが存在しないため，Move-Outアルゴリズムによってヘッドになる事でCNet(G)の性質を満たす．
No3 DEL.chd はアルゴリズムの動作後メンバーとなる
DEL の離脱後，ゲートウェイであるDEL.chd は子供を一つだけ持ち，隣接ノードにヘッドが存在するため，Move-Out アルゴリズムによってメンバーになる事でCNet(G) の性質を満たす．
No4 DEL.chd はアルゴリズムの動作後ヘッドとなる
DEL の離脱後，ゲートウェイであるDEL.chd は子供を一つだけ持つが，隣接ノードにヘッドが存在しないため，Move-Out アルゴリズムによってヘッドになる事でCNet(G) の性質を満たす．
No5 DEL.chd はアルゴリズムの動作後メンバーのままとなる
DEL の離脱後，メンバーであるDEL.chd は隣接ノードにヘッドが存在するため，メンバーのままでCNet(G) の性質を満たす．
No6 DEL.chd はアルゴリズムの動作後メンバーのままとなる
No5 と同様である．
No7 DEL.chd はアルゴリズムの動作後ヘッドになる
DELの離脱後，メンバーであるDEL.chd は隣接ノードにヘッドが存在しないため，Move-OutアルゴリズムによってヘッドとなることでCNet(G) の性質を満たす．
No8 DEL.chd はアルゴリズムの動作後ヘッドになる
No7 と同様である．
従って，いずれの場合もMove-Out アルゴリズムの実行により，DEL.chd 周辺のステータスは維持される．
補題12.  DEL がゲートウェイの時，Move-Out アルゴリズムの実行後DEL.prt,(DEL.prt).prt のステータスはCNet の性質1 に反しない
証明.
CNet を構成するためにノードが保持する情報の内容より，DEL.prt は以下の条件の組み合わせにより分類する事ができる．ただしDEL がゲートウェイの時，DEL.prt はCNet の定義よりヘッドもしくはゲートウェイである．
条件1. DEL.prt のステータスがヘッドかゲートウェイか
(a) ヘッド  (b) ゲートウェイ
条件2. DEL.prt はDEL 以外に子供を持つか持たないか
(a) 持つ  (b) 持たない
条件１〜２の組み合わせとDEL.prt の変化を表４に示す．
【００１８】
【表４】
2007221428.tif 000009
【００１９】
DEL がゲートウェイの時に提案するMove-Out アルゴリズムを実行すると，表３に示した８通りのDEL.prt は以下のように動作する．
No1 DEL.prt はアルゴリズムの動作後ヘッドのままとなる
DEL の離脱後，ヘッドであるDEL.prt に子供の有無は関係無いので，DEL.prt はヘッドのままでCNet(G) の性質を満たす．
No2 DEL.prt はアルゴリズムの動作後ヘッドのままとなる
No1 と同様である．
No3 DEL.prt はアルゴリズムの動作後ゲートウェイのままとなる
DEL の離脱後，ゲートウェイであるDEL.prt はDEL 以外に子供を持つ．この時，DEL.prtはゲートウェイのままでCNet(G) の性質を満たす．
No4 DEL.prt はアルゴリズムの動作後メンバーとなる
DEL の離脱後，ゲートウェイであるDEL.prt は子供を持たない．この時，DEL.prt はMove-Out アルゴリズムによってメンバーになることでCNet(G) の性質を満たす．
従って，いずれの場合もMove-Out アルゴリズムの実行により，DEL.prt 周辺のステータスは維持される．
補題13.  DEL がゲートウェイの時，Move-Out アルゴリズムの実行後DEL.chd のステータスはCNet の性質1 に反しない
証明.
CNet を構成するためにノードが保持する情報の内容より，DEL.chd は以下の条件の組み合わせにより分類する事ができる．ただしDEL がゲートウェイの時，CNet の定義よりDEL.chd はヘッドもしくはゲートウェイである．
条件1. DEL.chd のステータスがヘッドかゲートウェイか
(a) ヘッド  (b) ゲートウェイ
条件2. DEL.chd は子供をいくつ持つか
(a)2 個以上持つ  (b)1 個しか持たない
条件１〜２の組み合わせとDEL.chd のステータス変化を表５に示す．
【００２０】
【表５】
2007221428.tif 000010
【００２１】
DEL がゲートウェイの時に提案するMove-Out アルゴリズムを実行すると，表３に示した８通りのDEL.chd は以下のように動作する．
No1 DEL.chd はアルゴリズムの動作後ヘッドのままとなる
DEL の離脱後，ヘッドであるDEL.chd に子供の有無は関係無いので，DEL.chd はヘッドのままでCNet(G) の性質を満たす．
No2 DEL.chd はアルゴリズムの動作後ヘッドのままとなる
No1 と同様である．
No3 DEL.chd はアルゴリズムの動作後ゲートウェイのままとなる
DEL の離脱後，ゲートウェイであるDEL.chd はDEL 以外に子供を持つ．この時，DEL.chdはゲートウェイのままでCNet(G) の性質を満たす．
No4 DEL.chd はアルゴリズムの動作後メンバーとなる
DEL の離脱後，ゲートウェイであるDEL.chd は子供を持たない．この時，DEL.chd は??行でメンバーになることでCNet(G) の性質を満たす．
従って，いずれの場合もMove-Out アルゴリズムの実行により，DEL.chd 周辺のステータスは維持される。
補題14.  DELがメンバーの時，Move-Out アルゴリズムの実行後DEL.prt,(DEL.prt).prt,DEL.chdのステータスはCNet の性質1 に反しない
証明.
CNet の定義より，メンバーが離脱してもその構造には変化は生じない．
補題15.  Move-Out アルゴリズムの実行によりDELが離脱した後，DEL.prt,(DEL.prt).prt,DEL.chdでCNet(G) の定義を満たすステータスが維持される
証明.
補題10，補題11，補題12，補題13，補題14 より，DEL.prt,(DEL.prt).prt,DEL.chd のステータスはCNet の性質1 に反しない．
補題16.  Move-Out アルゴリズムの実行によりDEL が離脱した後，他の部分木と隣接するノードでCNet(G) の定義を満たすステータスが維持される
証明.
Move-Out アルゴリズムでは部分木同士の統合を実行する際にヘッドは発生しない．従って，部分木の統合を実行するノード付近でヘッド同士が隣接する事は無い．新たにゲートウェイが発生するのはメンバーがゲートウェイに変化する時だけである．従って，メンバーの定義より，新たに発生するゲートウェイの隣には必ずヘッドが存在する．また，この時Move-Out アルゴリズムの実行により，CNet 内部の親子関係も統合地点を基点に変更されている．以上より，CNet の性質は維持されている．
補題17.  Move-Out アルゴリズムの実行によりDEL が離脱した後に存在するCNet にはそれぞれ唯一つのルートが存在する
証明.
Move-Out アルゴリズムにより，DEL.chd を根とするCNet 上の部分木の統合が実行される．この時、統合が実行される部分木を構成するノードが持つルートID は統合先の部分木が持つルートID となる．この時孤立している部分木以外は全てが統合を実行される為，Move-Out アルゴリズムの実行によりDEL が離脱した後に存在するCNet はそれぞれ唯一つのルートを持つ．
定理4.  Move-Out アルゴリズムの実行によりCNet からノードの離脱が行われた結果，新しくできるネットワークもCNet の定義を満たしている
証明.
補題15，補題16 より，CNet の性質1 は維持される．補題17 より，CNet の性質2 は維持される．性質1 より，性質3 はただちに導かれる．
定理5. Move-Out アルゴリズムはノードの離脱時に，O(T) 時間でCNet(G) を維持するアルゴリズムである．
証明.
DEL がLeave メッセージを送信後，DEL.chd を根とする全ての部分木にDEL.chd のID がルートID として伝達されるまでにO（T) 時間必要である．続いて，(T1,T2,T3,...,Tq) それぞれの部分木の隣接情報を全て探索するのにO(T) 時間必要である．最後に，それぞれの部分木へ最終的なルートID の伝達に再びO（T) 時間必要となる．従って，Move-Out アルゴリズムの実行に必要な実行時間はO(T + T + T) より，O（T） となる．
【図面の簡単な説明】
【００２２】
【図１】無線ネットワークのクラスタ化の一例を示す。
【図２】内田らのアルゴリズムによるCNet 統合の一例を示す。
【図３】クラスタネットワークの一例を示す。
【図４】統合実行前を示す。
【図５】NEW の発生を示す。
【図６】NEW の親ノード決定を示す。
【図７】NEW の子ノード決定を示す。
【図８】ルートID の伝達と親子関係逆転を示す。
【図９】CNet(G) と部分木を示す。
【図１０】DEL.chd へのルートID 伝達を示す。
【図１１】DEL.chd を根とする部分木のグループ分けを示す。
【図１】
2007221428.tif 000011
【図２】
2007221428.tif 000012
【図３】
2007221428.tif 000013
【図４】
2007221428.tif 000014
【図５】
2007221428.tif 000015
【図６】
2007221428.tif 000016
【図７】
2007221428.tif 000017
【図８】
2007221428.tif 000018
【図９】
2007221428.tif 000019
【図１０】
2007221428.tif 000020
【図１１】
2007221428.tif 000021