(57)【要約】【課題】移動端末によるアドホックネットワークにおいて，端末が頻繁に移動する場合にも安定したクラスタ構造を提供するためのクラスタ構造およびクラスタ構造構築アルゴリズムと，クラスタ構造構築後にクラスタヘッド間で最短経路を用いたクラスタ間通信を行うためのゲートウェイ決定アルゴリズムおよびそれによる通信手法の提供を課題とする．【解決手段】クラスタ構築アルゴリズム SSCL2 乃至 SSCL3 を用いてクラスタ構造を構築し，方針1乃至方針２の通信手段によってクラスタ間通信を実現することを特徴とする．【選択図】    なし【特許請求の範囲】
【請求項１】
各移動端末が自身が属するクラスタを認識するためにクラスタヘッドIDすなわちクラスタヘッドである移動端末の識別子を備えていることを特徴とする移動端末による通信網の自己安定的構造化手法．
【請求項２】
各移動端末が，あらかじめきめられた初期状態ではなく任意の状態から本発明で提供する手法すなわちアルゴリズムを用いた構造化を行っても，正しく目的の構造化を達成することが可能なことを特徴とする移動端末による通信網の自己安定的構造化手法．
【請求項３】
ひとつのクラスタは，クラスタヘッドとメンバによって構成され，メンバであるノードは必ずただひとつのクラスタに所属し，所属するクラスタのクラスタヘッドと隣接するすなわち直接通信可能であることを特徴とする移動端末による通信網の自己安定的構造化手法．
【請求項４】
請求項１乃至２乃至３記載の移動端末による通信網の自己安定的構造化手法によるクラスタ構造を構成・維持するためにアルゴリズム SSL2 乃至 SSL3 を実行することを特徴とする移動端末による通信網の自己安定的構造化手法．
【請求項５】
請求項４記載のSSL2アルゴリズムが以下に示すものであることを特徴とする請求項４記載の移動端末による通信網の自己安定的構造化手法．
通信網上の各移動端末v は，各クラスタ構築アルゴリズム(SSL2, SSL3)で利用する以下の情報を保持している．
・Chv ：True(T) のときv はクラスタヘッド．そうでないときは F．
・Clusterheadv ：v の所属するクラスタのクラスタヘッドID．v 自身がクラスタヘッドならv のID(v.ID)が格納される．
・idneighbor ：v と通信網上で隣接する移動端末 (neighbor) のID．
・wneighbor ： 移動端末neighbor の重み．
・Clusterheadneighbor：移動端末neighbor のクラスタヘッドID．
・Timer ：エントリの有効時間．
・Table_neighbor ：各隣接移動端末に対して，idneighbor ，wneighbor ，Clusterheadneighbor ，Timer の四組を1つのエントリとして保持する表形式データ．
このとき，Clusterheadneighbor がidneighbor であるならば，v は通信網上で隣接する移動端末neighbor がヘッドであることが判別できる．また，各移動端末v はhello パケットの定期的なやり取りによりTable_neighbor を更新する．
各移動端末が保持する情報は，以上のとおりである．アルゴリズム SSCL2 を以下に示す．ただし，以下の記述において01行目から06行目までは移動端末内部で局所的に判定可能な述語であり，07から09行目までは矢印の前半部分の述語が成立したときのみ後半部分の変数操作を行う形式である．また，max_wz{} は，引数として与えられた移動端末集合の中から，重み変数の値が最も大きな移動端末の識別子を返す関数である．重みが等しい場合は，識別子との二項組み (wv,v.ID)を辞書式順序で比較することで最大重みを持つ移動端末を唯一に決定する．
01: Predicates’
02:   G1 (v)≡ (∀z∈ Nv : Chz = F);
03:   G2 (v)≡(Chv = T)∧(∃z ∈ Nv : (Chz = T)∧(wv < wz ));
04:   G3 (v)≡(Chv = F);
05:   G4 (v)≡(Clusterheadv ≠ v);
06:   G5 (v)≡(Clusterheadv ≠ max_wz{z ∈ Nv : Chz = T});
07: Rules
08:   R1 (v) : G1 (v)∧(G3 (v)∨G4 (v)) → Chv := T; Clusterheadv := v;
09:   R2 (v) : (¬G1 (v) ∧G3 (v) ∧G5 (v))∨G2 (v)
→ Chv := F; Clusterheadv := max_wz{z ∈ Nv : Chz = T};
【請求項６】
請求項４記載のSSL3アルゴリズムが以下に示すものであることを特徴とする請求項４記載の移動端末による通信網の自己安定的構造化手法．
通信網上の各移動端末v は，請求項５記載のものと同じ情報を保持している．また，以下のアルゴリズム SSL3 の記述においても，請求項５記載のアルゴリズム SSL2 と同じ形式である．max_wz{} についても請求項５記載のものと同じである．
01: Predicates
02:   G1 (v)≡ (∀z∈ Nv : Chz = F);
03:   G’1 (v)≡(∃z ∈ Nv : (Chz = T)∧(wv < wz ));
04:   G’’1 (v)≡(∃z ∈ Nv : (Chz = T)∧(wv > wz )); 
05:   G2 (v)≡(Chv = F)∨(Clusterheadv ≠ v);
06:   G3 (v)≡(Chv = T);
07:   G4 (v)≡(ChClusterheadv = F); 
08: Rules
09:   R1 (v) : G1 (v)∧G2 (v) → Chv := T; Clusterheadv := v;
10:   R2 (v) : (G’1 (v)∧(G3 (v)∨G4 (v)))∨(¬G’1 (v)∧G’’ 1 (v)∧G4 (v)))
→ Chv := F; Clusterheadv := max_wz{z ∈ Nv : Chz = T};
【請求項７】
クラスタ構造が構築された移動端末による通信網上で，以下の方針１乃至２に従いクラスタヘッド間の最短経路を用いた通信を実現するためのゲートウェイを決定する手法を特徴とする移動端末による通信網の自己安定的構造化手法．
・方針１：メッセージ送信時に相手クラスタヘッドへのゲートウェイを決定する（2 つのクラスタヘッド間をメッセージが往復する経路が異なる可能性がある）．
・方針２：予め隣接するクラスタヘッド間を結ぶゲートウェイを一意に決定しておく（2 つのクラスタヘッド間をメッセージが往復する経路が同一のものになる）.
【請求項８】
請求項7記載の方針1のゲートウェイを以下に示すアルゴリズムによって決定することを特徴とする請求項７の移動端末による通信網の自己安定的構造化手法．
まずアルゴリズムで使用するために各移動端末で保持する情報について説明する．
・Chv ：True(T) のときv はクラスタヘッド．それいがいは F．
・Clusterheadv ：v の所属するクラスタのクラスタヘッドID．v 自身がクラスタヘッドならv のID(v.ID)が格納される．
・idneighbor ：v と通信網上で隣接する移動端末 (neighbor) のID．
・wneighbor ： 移動端末neighbor の重み．
・Clusterheadneighbor：移動端末neighbor のクラスタヘッドID．
・Timer ：エントリの有効時間．
・Table_neighbor ：各隣接移動端末に対して，idneighbor ，wneighbor ，Clusterheadneighbor ，Timer の四組を1つのエントリとして保持する表形式データ．
このとき，Clusterheadneighbor がidneighbor であるならば，v は通信網上で隣接する移動端末neighbor がヘッドであることが判別できる．また，各移動端末v はhello パケットの定期的なやり取りによりTable_neighbor を更新しているものとする．
・Table_gateway ： 各エントリに以下の要素を含む表形式データ． 
各移動端末が保持するTable_gatewayの各フィールドの持つ意味は移動端末の状態によって以下の通りである．
[v がクラスタヘッドのとき]
・Cneighbor ： v のクラスタと隣接するクラスタのクラスタヘッドID
・gateway ： Cneighbor のクラスタに所属する移動端末とリンクを持つ（直接通信可能な）自分のメンバのID，又はvとリンクを持ちCneighbor のクラスタに所属する移動端末のID
・DN ： gateway がCneighbor へのDN であるかIDN であるかを示す．この値が1 のときDN，0 のときIDN とする
・Timer ：エントリの有効時間．
[v がメンバのとき]
・Cneighbor ： 自分が所属するクラスタを除く，vが隣接するクラスタのクラスタヘッドID
・gateway ： Cneighbor のクラスタに所属するv の隣接移動端末のID
・DN ： v 自身がCneighbor へのDN であるかIDNであるかを示す．この値が1 のときDN，0 のときIDN とする
・Timer ：エントリの有効時間．
各エントリにはタイマー（生存時間）が用意されており，時間経過にあわせて値を0 から増加させてゆき，一定値になったときそのエントリを廃棄する．
・DNとIDN ：，隣接する2 つのクラスタに対し，両方のクラスタヘッドとのリンクを持つ移動端末をDirectNeighbor(DN)，一方の（自分の）クラスタヘッドとの間にリンクを持ち，かつ他方のクラスタ内のメンバとの間にリンクを持つ移動端末をInDirectNeighbor(IDN )という．
以下のアルゴリズムを実行中に，各移動端末はhelloパケットに載せて以下のようにメッセージをやり取りする．
移動端末v がクラスタヘッドの場合，v 自身のID とステータス，すなわち(v.ID, v.status) を送信する．一方，v がメンバの場合，v 自身のID と所属するクラスタのクラスタヘッドID に加え，v が隣接するその他のクラスタに関する情報を送信する．具体的には，v が自分とは異なるクラスタに所属する移動端末と隣接している場合に，その隣接移動端末が所属するクラスタのクラスタヘッドID およびvがそのクラスタに対するDNであるかどうかを送信する．つまり，v はTable_gateway の全エントリを確認し，各
Cneighbor に対して(v.ID, Clusterheadv ,Cneighbor , DN)を送信する．
上記メッセージを受信した各移動端末は，以下の手続きによってデータテーブル Table_gateway を更新する．
(1) v がクラスタヘッドで，自分のメンバm からメッセージを受信したとき：
受信したCneighbor の各種類に対し，以下の作業を実行する．Table_gateway 内にエントリ<Cneighbor ,m.ID, *, *> が存在するとき，同エントリに<Cneighbor , m.ID, DN, 0> を上書きする．存在しない時は，Table_gateway にエントリ<Cneighbor ,m.ID, DN, 0> を追加する．
(2) v がクラスタヘッドで，自分のクラスタ外のメンバm からメッセージを受信したとき：
Table_gateway 内にエントリ<Clusterheadm,m.ID, *, *> (*は任意の値を意味する．以下同様）が存在するとき，同エントリに<Clusterheadm, m.ID, 1, 0> を上書きする．存在しない時は，Table_gateway にエントリ<Clusterheadm, m.ID, 1, 0> を追加する．
(3) v がメンバで，自分の所属するクラスタ外のメンバm からメッセージを受信したとき：
Table_gateway 内にエントリ<Clusterheadm,m.ID, *, *> が存在するとき，同エントリに<Clusterheadm, m.ID, 0, 0> を上書きする．存在しない時は，Table_gateway にエントリ
<Clusterheadm, m.ID, 0, 0> を追加する．
(4) v がメンバで，自分の所属するクラスタ以外のクラスタヘッドh からメッセージを受信したとき：
Table_gateway 内にエントリ<h.ID, h.ID, *, *>が存在するとき，同エントリに<h.ID, h.ID, 1, 0>を上書きする．存在しない時は，Table_gateway にエントリ<h.ID, h.ID, 1, 0> を追加する．
(5) 上記以外の場合：
何も実行せず，受信したメッセージを無視する．
一方，Table_gateway の各エントリにはタイマーを設定しておき，一定時間更新されなかったエントリを削除する．また，v のステータスが変化したとき，及びClusterheadv が変化したとき，v はTable_gateway ら全エントリを削除する．
以下，メッセージ送信元クラスタヘッドIDを Sender，送信先クラスタヘッドID を Dest とした場合の通信メッセージと使用する関数および通信手法を説明する．
[クラスタ間通信用メッセージ]
(Dest.ID,To.ID, Message)
・Dest.ID： Dest のID．
・To.ID： 送信先移動端末（ゲートウェイまたはDest）のID．
・Message： Sender がDest へ送信するメッセージの内容．
[クラスタ間通信に用いる関数]
・int selectnode(int Dest.ID)   
自身が持つTable_gateway の中でCneighbor の値がDest.ID であるエントリ集合の中から，(DN,gateway) を辞書式順序で比較した結果，最も大きいエントリのgateway の値(ID) を出力する関数．
[クラスタ間通信手順]
・メッセージ(Dest.ID,To.ID, Message) を受信した移動端末vつまりゲートウェイが実行する動作は，以下の動作を行う．
- 受信したTo.ID がv 自身のID の時，v は通信用メッセージ(Dest.ID, selectnode(Dest.ID), Message)を送信する．ただし，受信したDest.ID がv のクラスタヘッドID であった時は，v は通信用メッセージ(Dest.ID, Dest.ID, Message) を送信する．あるいはDest がv 自身のID である時は，Message を受信して終了する．
【請求項９】
請求項7記載の方針２のゲートウェイを以下に示すアルゴリズムによって決定することを特徴とする請求項７の移動端末による通信網の自己安定的構造化手法．
まずアルゴリズム中で使用するために各端末で保持している情報について説明する．
本発明で提供する本手法における各端末の情報は，請求項８記載のTable_gatewayを除くすべての情報に加え，以下に説明する請求項８記載のものに Flagフィールドを追加した表形式データTable_gateway である．ただし，Flag フィールド以外については請求項８記載の Table_gateway と同じ意味を持ち，更新手法も請求項８記載と同じである．
Flagフィールドは，移動端末 v のステータスによって次の意味を持つ．v がクラスタヘッドのとき，v が受信したv より強い（ID の小さい）隣接クラスタのクラスタヘッドからのメッセージをv へ送信した移動端末を示す．v は自分の隣接クラスタへのゲートウェイ候補であるエントリの中にこの値が1 であるエントリが存在するとき，そのエントリのgateway で指定される移動端末へメッセージを送信する．一方，全てのエントリでFlag の値が0 の時は，請求項８記載の方針1 と同じ手法つまり同じアルゴリズムを実行する．v がメンバの時，Flag の値は利用しないため，全て0 とする．
以下，メッセージ送信元クラスタヘッドIDを Sender，送信先クラスタヘッドID を Dest とした場合の通信メッセージと使用する関数および通信手法を説明する．
[クラスタ間通信用メッセージ]
(Sender.ID, Dest.ID, From.ID, To.ID, Message)
・Sender.ID： Sender のID．
・Dest.ID： Dest のID．
・From.ID： 通信用メッセージの送信元ノードID．
・To.ID： 通信用メッセージの宛先ノードのID．
・Message： Sender がDest に送信するメッセージの内容．
[クラスタ間通信に用いる関数]
・int selectnode(int Dest.ID)   
自身が持つTable_gateway のエントリの中で，Cneighbor がDest.ID であるエントリ集合のうち，(Flag,DN,gateway) の辞書式順序で最も大きいエントリのgateway の値(ID) を出力する関数．
[クラスタ間通信手順]
・メッセージ送信元クラスタヘッドSender の動作：
(Sender.ID, Dest.ID, Sender.ID, selectnode(Dest.ID), Message) を送信．
・メッセージ(Sender.ID, Dest.ID, From.ID, To.ID, Message) を受信した移動端末v が実行する動作：
受信したTo.ID がv 自身のID の時，v は通信用メッセージ( Sender.ID , Dest.ID, v.ID,
selectnode(Dest.ID), Message) を送信する．ただし，受信したDest.ID がv のクラスタヘッドID であった時は，v は通信用メッセージ( Sender.ID ,Dest.ID, v.ID, Dest.ID, Message) を送信する．あるいは，Dest がv 自身のID である時は，Message を受信して終了する．
なお，Dest がMessage を確認した際に，Sender.ID がDest.ID より小さければ，Dest.ID は自分のTable_gateway 内のエントリ< Sender.ID, From.ID, *, *, *> (*は任意の値を意味する）のFlag を1 にする．また，<Sender.ID, From.ID以外, *, *, *> のFlag を にする．
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は移動端末による通信網の自己安定的構造化手法に関する．
【背景技術】
【０００２】
通信のためのインフラストラクチャを持たず，無線通信機能を持つ自律的に動作する移動端末（以下，たんにノード）によって構成されるネットワークを無線アドホックネットワークと呼ぶ．無線アドホックネットワークでは，ノードの能力（電源，通信範囲，通信周波数など）に制限があるため効率のよい通信手法が求められているが，単にノードを起動した状態の無線アドホックネットワーク上では，メッセージの衝突や重複により効率の良い通信を行う事ができない．そこで，無線アドホックネットワーク上で効率よく通信を行うための手法として，クラスタを利用したものが提案されている[非特許文献1]．
しかし，無線アドホックネットワーク中の各ノードが移動する事を考慮する時，既存のものはそのまま適用しづらいという問題がある．例えば，通常の分散アルゴリズムではネットワーク形状の変化が生じたときにはアルゴリズムの実行を一度リセットし，再び最初からアルゴリズムを実行してクラスタを構築する必要がある．また，自己安定（分散）アルゴリズムでも，ネットワーク形状の変化が生じたときには再安定までに多くの時間を必要とする．いずれの場合もネットワーク形状の変化が頻繁に生じる時に問題となるため，ノードの移動が頻繁に生じる無線アドホックネットワーク にそのまま適用することは難しい．
【０００３】
動的なネットワーク形状の変化に対応したクラスタリングアルゴリズムが内田ら[非特許文献1] によって提案されている．この手法ではノードの発生によるネットワーク形状の変化に対してクラスタ構造再構築のオーバヘッドを小さくする事が可能となっているが，ノードの移動には明示的に対応しておらず，ノードの消滅と出現の組み合わせで対応されている．また，アルゴリズムの動作中に新たなノードの発生や離脱が起こらないという制限があるため，各ノードの移動を考慮した無線アドホックネットワーク では，そのまま適用することが難しい．また，Colette ら[非特許文献2] により無線アドホックネットワーク を対象とした自己安定クラスタリングアルゴリズムが提案されているが，ノードの移動が頻繁に起こるとクラスタ構造の変化が頻発するため，安定しているつまりクラスタが正しく構築されている時間が長く続かないという問題点がある．さらに，無線アドホックネットワークで効率の良い通信を行う為には，クラスタ構造を構築するだけでは不十分である．クラスタヘッド間の通信を行う際に何の制御も行わないと，ネットワークを構成する全てのノードがメッセージを送信する可能性がある．
【０００４】
【非特許文献１】J. Uchida, A.K.M. Muzahidul.I, Y. Katayama, W.Chen, K.Wada, Construction and maintenance of a cluster-based architecture for sensor networks, HICSS06, Track9, 2006.
【非特許文献２】C. Johnen, L.H. Nguyen, Self-Stabilizing Clustering Algorithm for Ad hoc Networks,AlgoSensors 2006, L.R.I., July 2006 (pdf) also: research report no. 1429, January, 2006.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は，既存のクラスタ構造構築アルゴリズムに比べ，ノードが移動してもクラスタ構造が変化しにくく従って安定したクラスタ構造を提供可能であるクラスタ構造とそのクラスタ構造を構築する自己安定クラスタリングアルゴリズムを提供することを解決すべき課題としている．
【０００６】
本発明は，提供するアルゴリズムによって構築されたクラスタ構造を利用し，クラスタ間の通信を実現するための最短の通信路を決定する，つまりクラスタヘッド間を結ぶ最短経路上のゲートウェイを自己安定に決定する手法を提供することを解決すべき課題としている．
【０００７】
本発明により，ノード移動が頻繁に起こるつまりネットワーク形状が頻繁に変化する移動端末によるネットワークに対し，より安定したクラスタ構造を提供することが可能となり，さらに本発明によって決定された最短経路を構成するゲートウェイを利用することで，クラスタ間の通信がゲートウェイであるノードがメッセージ送信するだけで可能となるため，クラスタ間の安定したかつ効率の良い通信が可能となる．
【０００８】
本発明により，既存のアルゴリズムより安定したクラスタ構造を提供できていることを，シミュレーションによって明らかにした結果を示す．
【０００９】
シミュレーションの環境について以下に説明する．
・使用したネットワークシミュレータ：  Qualnet3.8
・ノードの配置： 1500m 四方のエリアに，36乃至100個のノードをランダムに配置．
・ノードの移動： ノードが静止している場合および1m/s〜5m/s(平均 2.5m/s)でランダムな方向に移動している場合．（ランダムウェイポイント）
・シミュレーション時間： 1時間相当
・使用する通信モデル： IEEE802.11相当および理想的な（電波雑音等を考慮しない）IEEE802.11．
・評価項目： 実行時間中に各ノードが行った状態遷移回数（ノードのステータスの変更回数）
【００１０】
シミュレーションによって得られた結果を表５ に示す．
表５より，提供するアルゴリズムSSCL2およびSSCL3 が既存手法 SSCL(非特許文献2)に比べて，大幅に状態遷移回数が減少していることは明らかである．つまり，移動端末が頻繁に移動する環境において，提供するアルゴリズムによるクラスタ構造の安定度が高いことを示している．
【００１１】
【表１】
2008219362.tif 000002
【課題を解決するための手段】
【００１２】
本発明で提供するクラスタ構造構築アルゴリズムおよびゲートウェイ決定アルゴリズムSSCL2, SSCL3 について Coletteらの SSCL(非特許文献2) と比較して説明する．
【００１３】
・SSCL
各ノードは自分より重みの大きいノードをクラスタヘッドとみなし，そのノードのメンバとなる．つまり，各ノードは自分より重みの大きなノードと隣接しないとき，すでに隣接ノードにクラスタヘッドが存在している場合でもクラスタヘッドになる．つまり，ノードの移動によるネットワーク形状の変化が頻繁に発生する状況では，新たなクラスタヘッドの発生により再構成する必要のない既存クラスタを破壊・再構成することとなり，クラスタ構造の変化が頻繁に発生する可能性がある．
・SSCL2
メンバであるノードは隣接ノードの中にクラスタヘッドが存在する場合にはヘッドにならないようにSSCL の処理を変更する事で，ノードの移動に対しクラスタ構造の変化を少なくする事が可能にした．ただし，各メンバノードは隣接するクラスタヘッドのうち一番重みの大きいものへと常に更新する為，現在のクラスタヘッドより重みの大きなクラスタヘッドが出現すると，クラスタヘッドの変更が生じ，クラスタ構造の変化が頻繁に発生する可能性がある．
・SSCL3
メンバであるノードは自分の所属するクラスタのクラスタヘッドが存在する限り，所属するクラスタの変更を行わないようにSSCL2 の処理を変更する．このようにする事で，ノードの出現や移動によるクラスタ構造の変化をSSCL2 より更に小さくすることを可能にした．
【発明を実施するための最良の形態】
【００１４】
以下，本発明が提供するクラスタ構造および当該クラスタ構造を構成・維持するため，さらに暮らす多感 通信を実現するために各移動端末が具備するアルゴリズムについて，既存のアルゴリズムとの比較を行いながら説明する．
【実施例１】
【００１５】
本発明で対象とする移動端末による無線網，つまり無線による通信を行う移動端末で構成されたアドホックネットワークのモデルを以下に示す．
・各移動端末（以下，ノード）を節点とし，互いに直接通信が可能なノード間に辺が存在するとして，無線アドホックネットワーク を無向グラフG = (V,E)(V : ノードの集合，E : 無向辺の集合)として扱う．
・各ノードv の送受信性能及び計算能力は等しく，それぞれ固有の識別子(ID) 及び固有の重み(wv ) を持つ．
・ノードの移動や出現・消滅を許す．つまり，G はアルゴリズムの実行中にも変化するものとする．
・各ノードv は要求に応じてパケットを送信する．ただし，これとは別にhello パケットと呼ばれるメッセージを定期的にやりとりする．hello パケットとはノードの状態を交換するためのパケットであり，G 上で隣接するつまり直接通信可能なノード対はhello パケットの送受信を行う事で互いの情報を交換する．
・メッセージの衝突（コリジョン）が発生してもこれを検知し，再送制御等によりそれぞれのメッセージを正しく受信できるとする．
【００１６】
次に，本発明で提供するクラスタネットワークについて説明する．
本発明で提供するする各クラスタ構築自己安定アルゴリズムによって構築されるクラスタ構造は以下の通りである．  無向グラフで表現された無線ネットワークG = (V,E) 上の極大独立点をクラスタヘッドと呼び，それ以外のノードをメンバと呼ぶ．各クラスタヘッドを中心としたスターグラフをクラスタと呼び，一つのクラスタはクラスタヘッドとメンバによって構成される．ただし，メンバであるノードは必ずただ一つのクラスタに所属し，所属するクラスタのクラスタヘッドと隣接している．
【００１７】
本発明で提供するアルゴリズム SSCL2および SSCL3 のために各ノードが保持する情報を説明する．
・Chv ：True(T) のときv はクラスタヘッド．それ以外は F．
・Clusterheadv ：v の所属するクラスタのクラスタヘッドID．v 自身がクラスタヘッドならv のID(v.ID)が格納される．
・idneighbor ：v と通信網上で隣接する移動端末 (neighbor) のID．
・wneighbor ： 移動端末neighbor の重み．
・Clusterheadneighbor：移動端末neighbor のクラスタヘッドID．
・Timer ：エントリの有効時間．
・Table_neighbor ：各隣接移動端末に対して，idneighbor ，wneighbor ，Clusterheadneighbor ，Timer の四組を1つのエントリとして保持する表形式データ(表２２)．
【００１８】
【表２】
2008219362.tif 000003
【００１９】
このとき，Clusterheadneighbor がidneighbor であるならば，v は通信網上で隣接する移動端末neighbor がヘッドであることが判別できる．また，各移動端末v はhello パケットの定期的なやり取りによりTable_neighbor を更新する．
【００２０】
次に，本発明で提供するアルゴリズム SSCL2 および SSCL3 と既存手法の違いを明らかにしつつ説明するために，既存手法 SSCL (非特許文献2) を説明する．
SSCL を以下に示す．
01: Predicates’
02:   G1 (v)≡(∀z ∈Nv : (Chz = F)∨(wv > wz));
03:   G2 (v)≡(Chv = F)∨(Clusterheadv ≠ v)
04:   G3 (v)≡(Chv = T)∨(Clusterheadv ≠ max_wz{z ∈ Nv : Chz = T });
05: Rules
06:   R1 (v) : G1 (v)∧G2(v) → Chv := T; Clusterheadv := v;
07:   R2 (v) : ¬G1 (v) ∧G3 (v)
→ Chv := F; Clusterheadv := max_wz{z ∈ Nv : Chz = T };
【００２１】
SSCL では，各ノードv は自分より重みの大きいクラスタヘッドと隣接する時メンバになり，隣接する一番重みの大きいクラスタヘッドのクラスタに所属する．また，SSCLでは，各ノードv は自分より重みの大きいノードと隣接しないとき，既に隣接ノードにクラスタヘッドが存在していても新たにクラスタヘッドになる事に注意する．
つまり，ノードが移動するネットワークにSSCL を適用する事を考えると，全体としてクラスタ構造が安定している時間が長く続かない可能性がある．G 中でもっとも重みが大きいクラスタヘッドh1 が移動する時を考える．h1 のクラスタに所属するノードの中にG 中で2 番目に重みが大きいノードが存在したとすると，このノードはh1 が移動により隣接しなくなると，既に隣接ノードの中に別のクラスタヘッドが存在していたとしても新たにクラスタヘッドになってしまう．このように，ノードの移動によるネットワーク形状の変化が頻繁に発生する状況では，新たなクラスタヘッドの発生により再構成する必要のない既存クラスタを破壊・再構成することとなり，クラスタ構造の変化が頻繁に発生する可能性がある．
【００２２】
そこで本発明では，メンバであるノードは隣接ノードの中にクラスタヘッドが存在する場合にはヘッドにならないようにSSCL の処理を変更する事で，ノードの移動に対しクラスタ構造の変化を少なくする事が可能なクラスタ構築自己安定アルゴリズムSSCL2を提供する．SSCL2 のために各端末で保持する情報は SSCL と同じである．
以下に SSCL2 を示す．
01: Predicates’
02:   G1 (v)≡ (∀z∈ Nv : Chz = F);
03:   G2 (v)≡(Chv = T)∧(∃z ∈ Nv : (Chz = T)∧(wv < wz ));
04:   G3 (v)≡(Chv = F);
05:   G4 (v)≡(Clusterheadv ≠ v);
06:   G5 (v)≡(Clusterheadv ≠ max_wz{z ∈ Nv : Chz = T });
07: Rules
08:   R1 (v) : G1 (v)∧(G3 (v)∨G4 (v)) → Chv := T; Clusterheadv := v;
09:   R2 (v) : (¬G1 (v) ∧G3 (v) ∧G5 (v))∨G2 (v)
→ Chv := F; Clusterheadv := max_wz{z ∈ Nv : Chz = T };
【００２３】
SSCL2 では，メンバであるノードは隣接ノードの中にクラスタヘッドが存在する場合にはクラスタヘッドにならないようにSSCLの処理を変更する．つまり，SSCL2 では，メンバであるノードm はクラスタヘッドと隣接しないときにのみクラスタヘッドになる（08 行）．これにより，新たなクラスタヘッドの発生により既存のクラスタ構造が壊れてしまう問題点を解決する事ができる．
SSCL では各クラスタヘッドが必ず自分のメンバより重みが大きかったのに対し，SSCL2では自分のメンバより重みの小さなクラスタヘッドが存在する可能性がある．ここでノードの重みを耐久性や信頼性の高さと考えた場合，より重みが大きなノードがクラスタヘッドになるSSCLの方が望ましいアルゴリズムと考えられる．従って，ノードの移動を考えるとき，「ネットワーク形状の変化に対するクラスタ構造の変化の少なさ」と「信頼性の高いクラスタヘッドの選択」のトレードオフとなる．
【００２４】
本発明で提供するアルゴリズムSSCL2 の正しさを証明する．
定理1. SSCL2 は，有限時間内に正しくクラスタ構造を構築する自己安定アルゴリズムである．
略証. SSCL2 のSSCL からの変更点は，メンバであるノードm が新たにクラスタヘッドになる条件がm の隣接ノードにクラスタヘッドが存在しない時のみに変更された点である（08 行）．これは，SSCLから互いに隣接するクラスタヘッドが新たに発生するような動作が無くなっただけであり，隣接するクラスタヘッドが存在しないノードは新たなクラスタヘッドになる事は可能である．ノードがメンバになる条件はSSCLと同様であるため（09 行），正しいクラスタ構造への収束性は変わらず保証される．
【００２５】
SSCL2 の問題点と改良案は以下の通りである．
SSCL2 ではSSCL と同様に，各メンバm は自分のClusterheadm を自分と隣接するクラスタヘッドのうち一番重みの大きいものへと常に更新する為，クラスタ構造の変化が頻繁に発生する可能性がある．そこで，メンバであるノードは自分の所属するクラスタのクラスタヘッドが存在する限り，所属するクラスタの変更を行わないようにSSCL2の処理を変更する．このようにする事で，ノードの出現や移動によるクラスタ構造の変化をSSCL2 より更に小さくすることができる．
【００２６】
本発明では，SSCL2 を改良しアドホックネットワークの形状変化に対しSSCL2より更にクラスタ構造の変化を小さくすることつまりより安定したクラスタ構造を提供することが可能なクラスタ構築自己安定アルゴリズムSSCL3 を提供する．SSCL3 について以下に説明する．
アルゴリズムのために各ノードが保持する情報は SSCLおよび SSCL2 と同じである．
01: Predicates
02:   G1 (v)≡ (∀z∈ Nv : Chz = F);
03:   G’1 (v)≡(∃z ∈ Nv : (Chz = T)∧(wv < wz ));
04:   G’’1 (v)≡(∃z ∈ Nv : (Chz = T)∧(wv > wz )); 
05:   G2 (v)≡(Chv = F)∨(Clusterheadv ≠ v);
06:   G3 (v)≡(Chv = T);
07:   G4 (v)≡(ChClusterheadv = F); 
08: Rules
09:   R1 (v) : G1 (v)∧G2 (v) → Chv := T; Clusterheadv := v;
10:   R2 (v) : (G’1 (v)∧(G3 (v)∨G4 (v)))∨(¬G’1 (v)∧G’’ 1 (v)∧G4 (v)))
→ Chv := F; Clusterheadv := max_wz{z ∈ Nv : Chz = T };
【００２７】
SSCL2 に対して，SSCL3 では，メンバであるノードは所属するクラスタのクラスタヘッドが存在する限り，所属するクラスタを変更しないようにSSCL2の処理を変更する（10 行）．これにより，クラスタヘッドの移動による各メンバの所属するクラスタの変更回数を少なくする事ができる．
【００２８】
本発明で提供するSSCL3 の正しさを証明する．
定理2. SSCL3 は，有限時間内に正しくクラスタ構造を構築する自己安定アルゴリズムである．
略証. SSCL3 のSSCL2 からの変更点は，メンバであるノードm が行う所属するクラスタの変更が，所属するクラスタが壊れたときにのみ行われるようになった点のみである（10 行）．従って，各ノードが起こすステータスの変更部分の動作はSSCL2と同様であるため，正しいクラスタ構造への収束性は変わらず保証される．
【００２９】
次に，本発明で提供するクラスタ構造を用いてクラスタ間通信を実現するための手法を説明する．
無線アドホックネットワーク上に構築されたクラスタ構造で，あるクラスタ内のノードから隣接する（一方のクラスタ内のノードから他方のクラスタ内のノードへのリンクがG 上に存在する）クラスタ内のノードへ通信を行う事を考える．この時，2 つのクラスタヘッド間に通信路が構築されていれば，各クラスタ内のメンバは自分のクラスタヘッドにメッセージを連絡し，クラスタヘッド間で通信路を用いたメッセージ交換をする事で，互いに隣接するクラスタに所属するノード同士の通信が可能になる．しかし，前節のアルゴリズムを実行するだけではクラスタが構築されるだけであり，互いに隣接するクラスタのクラスタヘッド同士の通信路は用意されていない．2 つのクラスタのクラスタヘッド間の通信を行うためには，2 つのクラスタ内に存在するメンバを中継して通信を行う必要がある．この時2 つのクラスタヘッド間で互いのメッセージを中継するメンバをゲートウェイと呼ぶ．
【００３０】
本発明では，各クラスタ構築アルゴリズムによってクラスタ構造が構築された後，隣接するクラスタのクラスタヘッド間を連結するゲートウェイを決定するつまりクラスタ間通信を実現するための以下の2 つの方針による手法を提供する．
・方針1 メッセージ送信時に相手クラスタヘッドへのゲートウェイを決定する（2 つのクラスタヘッド間を往復する経路が異なる可能性がある）．
・方針2 予め隣接するクラスタヘッド間を結ぶゲートウェイを一意に決定しておく（2 つのクラスタヘッド間を往復する経路が同一のものになる）．
ノードの移動が発生する状況では，2 つのクラスタヘッド間に設定した通信路がメッセージを送信する瞬間にも存在している事が保証されない．そのため，方針1 では各ノードがメッセージを送信する瞬間にゲートウェイとなるノードを決定する事で，より新しいネットワーク形状に合わせたゲートウェイを決定する（ただし，2 つのクラスタヘッド間を往復する経路が異なる可能性がある）．2 つのクラスタヘッド間を結ぶ経路が同一である事が求められる場合には，方針2 を利用する．方針2 の手法は方針1 の手法に拡張を加える事で実現する．
【００３１】
方針１によるクラスタ間通信実現方法について説明する．まず，基本的な方針について説明する．
各クラスタヘッドは，隣接するクラスタそれぞれに対し，常にゲートウェイの候補を保持しておく．あるクラスタへの送信要求が発生すると，そのノードに対してメッセージを（宛先クラスタのクラスタヘッドID を添えて）送信する．このメッセージを受信したノード（ゲートウェイ）は添付されている宛先クラスタのクラスタヘッドID より，自分と隣接するノードの中から転送先を一つ選択してメッセージを転送する．この時，転送されたメッセージを受信したノードが宛先クラスタのメンバであるなら，自分のクラスタヘッドへ更に転送する事で，クラスタヘッド間のメッセージ送信が完了する．
以上を実現するために，各ノードv はどの隣接ノードにメッセージを送信すれば，どの隣接クラスタのクラスタヘッドへメッセージが到達できるかを認識している必要がある．そこで，各ノードv は「自分の隣接ノードのID のリストと，その各隣接ノードが所属するクラスタのクラスタヘッドID」を表形式で(Table_gateway とする) 保持する．また，クラスタヘッド間の通信を正しく行うために，各ノードv はTable_gateway を常に最新の状態に更新する必要がある．更新には hello パケットによる情報交換を利用する．その後，実際にクラスタヘッド間で通信を行う際には，メッセージを送信するノードは相手のクラスタヘッドへの最短経路となるゲートウェイを自分が持つTable_gateway から決定する．
【００３２】
Table_gateway について説明する．
に保持している情報に加え，各エントリに以下の要素を含むデータテーブルTable _gateway(表３) を保持する．
【００３３】
【表３】
2008219362.tif 000004
【００３４】
このとき，隣接する2 つのクラスタに対し，両方のクラスタヘッドとのリンクを持つノードをDirectNeighbor(DN)，一方の（自分の）クラスタヘッドとの間にリンクを持ち，かつ他方のクラスタ内のメンバとの間にリンクを持つノードをInDirectNeighbor(IDN )と表記する．
v が保持するTable_gateway は，v のステータスによって各フィールドの意味が異なる．
・v がクラスタヘッドのとき  
・Cneighbor ： v のクラスタと隣接するクラスタのクラスタヘッドID
・gateway ： Cneighbor のクラスタに所属するノードとリンクを持つ自分のメンバのID，又はvとリンクを持ちCneighbor のクラスタに所属するノードのID
・DN ： gateway がCneighbor へのDN であるかIDN であるかを示す．この値が1 のときDN，0 のときIDN とする
・Timer ：エントリの有効時間．
・v がメンバのとき  
・Cneighbor ： 自分が所属するクラスタを除く，v が隣接するクラスタのクラスタヘッドID
・gateway ： Cneighbor のクラスタに所属するv の隣接ノードID
・DN ： v 自身がCneighbor へのDN であるかIDNであるかを示す．この値が1 のときDN，0 のときIDN とする
・Timer ：エントリの有効時間．
各エントリにはタイマー（生存時間）が用意されており，時間経過にあわせて値を0 から増加させてゆき，一定値になったときそのエントリを廃棄する．
【００３５】
次に，hello パケットによる Table_gateway の更新方法を説明する．
各ノードv は自分のステータスに従い，次の情報をhello パケットに乗せて定期的に送信する．
v がクラスタヘッドの場合，v 自身のID とステータス，すなわち(v.ID, v.status) を送信する．
一方，v がメンバの場合，v 自身のID と所属するクラスタのクラスタヘッドID に加え，v が隣接するその他のクラスタに関する情報を送信する．具体的には，v が自分とは異なるクラスタに所属するノードと隣接している場合に，その隣接ノードが所属するクラスタのクラスタヘッドID およびvがそのクラスタに対するDNであるかどうかを送信する．つまり，v はTable_gateway の全エントリを確認し，各Cneighbor に対して(v.ID, Clusterheadv ,Cneighbor , DN)を送信する．
このとき，DN が1 であるエントリが存在する場合にはDN = 1，それ以外はDN = 0 とする．
【００３６】
各ノードが Table_gateway 更新のためにhello パケットに載せて送信するメッセージの具体例を，図面を参照しつつ説明する．
図１でm1 は，Table_gateway に3 つのエントリを保持しており，この中には2 種類のCneighbor が存在する．この時，m1 はh2 に関してはDN が0 のエントリしか持たないが，h3 に関してはDN が1 と0 のエントリが存在する．従って，m1 は(m1,ID, h1.ID, h2.ID, 0)と(m1.ID, h1.ID, h3.ID, 1) を送信する．
【００３７】
Table_gateway 更新のためのメッセージを受信した各ノードは，以下の5種類の手順のうちいずれか該当する手順を行い，Table_gateway を更新する．ただし，このときクラスタリングアルゴリズムで利用する変数 Clusterheadv を利用する．
(1) v がクラスタヘッドで，自分のメンバm からメッセージを受信したとき：
受信したCneighbor の各種類に対し，以下の作業を実行する．Table_gateway 内にエントリ<Cneighbor ,m.ID, ?, ?> が存在するとき，同エントリに<Cneighbor , m.ID, DN, 0> を上書きする．存在しない時は，Table_gateway にエントリ<Cneighbor ,m.ID, DN, 0> を追加する．
(2) v がクラスタヘッドで，自分のクラスタ外のメンバm からメッセージを受信したとき：
Table_gateway 内にエントリ<Clusterheadm,m.ID, *, *> (*は任意の値を意味する．以下同様）が存在するとき，同エントリに<Clusterheadm, m.ID, 1, 0> を上書きする．存在しない時は，Table_gateway にエントリ<Clusterheadm, m.ID, 1, 0> を追加する．
(3) v がメンバで，自分の所属するクラスタ外のメンバm からメッセージを受信したとき：
Table_gateway 内にエントリ<Clusterheadm,m.ID, *, *> が存在するとき，同エントリに<Clusterheadm, m.ID, 0, 0> を上書きする．存在しない時は，Table_gateway にエントリ
<Clusterheadm, m.ID, 0, 0> を追加する．
(4) v がメンバで，自分の所属するクラスタ以外のクラスタヘッドh からメッセージを受信したとき：
Table_gateway 内にエントリ<h.ID, h.ID, *, *>が存在するとき，同エントリに<h.ID, h.ID, 1, 0>を上書きする．存在しない時は，Table_gateway にエントリ<h.ID, h.ID, 1, 0> を追加する．
(5) 上記以外の場合：
何も実行せず，受信したメッセージを無視する．
一方，Table_gateway の各エントリにはタイマーを設定しておき，一定時間更新されなかったエントリを削除する．また，v のステータスが変化したとき，及びClusterheadv が変化したとき，v はTable_gateway ら全エントリを削除する．
【００３８】
次に，各ノードが持つ Table_gateway を利用し，方針1によるクラスタ間の通信を実現するための手法を説明する．すなわち，各クラスタヘッドが自分のクラスタと隣接するクラスタのクラスタヘッドへメッセージを送信する際に実行する手順について説明する．以下，メッセージ送信元クラスタヘッドをSender，メッセージの送信先クラスタヘッドをDest とする．
まずクラスタ間通信用のメッセージを説明し，続いて通信に使用するゲートウェイ選択用関数を定義する．さらにクラスタ間通信の手順を説明する．
[クラスタ間通信用メッセージ]
(Dest.ID,To.ID, Message)
・Dest.ID： Dest のID．
・To.ID： 送信先移動端末（ゲートウェイまたはDest）のID．
・Message： Sender がDest へ送信するメッセージの内容．
[クラスタ間通信に用いる関数]
・int selectnode(int Dest.ID)   
自身が持つTable_gateway の中でCneighbor の値がDest.ID であるエントリ集合の中から，(DN,gateway) の辞書式順序で最も大きいエントリのgateway の値(ID) を出力する関数．
[クラスタ間通信手順]
・メッセージ(Dest.ID,To.ID, Message) を受信した移動端末v（ゲートウェイ）が実行する動作は，以下の動作を行う．
- 受信したTo.ID がv 自身のID の時，v は通信用メッセージ(Dest.ID, selectnode(Dest.ID), Message)を送信する．ただし，受信したDest.ID がv のクラスタヘッドID であった時は，v は通信用メッセージ(Dest.ID, Dest.ID, Message) を送信する．あるいはDest がv 自身のID である時は，Message を受信して終了する．
【００３９】
Table_gateway を用いた方針1によるクラスタ間通信手法の具体例を図面を参照しながら説明する．
図２でh2 がh3 にメッセージを送信する例を考える．この時，h2 ではゲートウェイとしてエントリ3が選択される(selectnode(h3.ID) == m3.ID)．従って，h2 はメッセージ(h3.ID,m3.ID, Message) を送信する．m3 はゲートウェイとしてエントリ5 を選択し，(h3.ID,m5.ID, Message) を送信する．m5 は受信したDest.ID が自分のクラスタヘッドID と一致するため，(h3.ID, h3.ID, Message) を送信する．
【００４０】
Table_gateway を用いた方針1によるクラスタ間通信手法の正しさを以下の通り証明する．
補題1. 本発明で提供するする通信手法では，2 つのクラスタヘッド間の最短経路を用いて通信が可能である．
略証. 互いに隣接するクラスタのクラスタヘッド間の最短経路はDN か，DN が存在しない時はIDN を中継する場合である．
提供する手法では，2 つのクラスタヘッド間にDN が存在する時は必ずDN を用いて通信を行うため，この時最短経路を用いて通信が可能なのは明らかである．2つのクラスタヘッド間にIDN のみ存在する時，各IDNが持つTable_gateway の中には同じクラスタに所属するメンバへの経路情報は含まれていない為，IDN からは必ず他方のクラスタに所属するIDN へメッセージが送信される．従って，IDN のみ存在する場合も最短経路を用いて通信が可能となる．
補題2. 本発明で提供する通信手法では，2 つのクラスタヘッド間のゲートウェイのみがメッセージを送信する．
証明. アルゴリズムより明らか．
定理3. 本発明で提供する通信手法を用いる事で，隣接するクラスタのクラスタヘッド間の双方向それぞれの最短経路を用いた通信が正しく行える．
証明. 補題1，2 より明らか．
【００４１】
次に，Table_gateway を用いた方針２によるクラスタ間通信手法について説明する．方針２による手法は，方針1による手法を拡張し，隣接するクラスタヘッド間の往復経路を一意に決定するゲートウェイ決定アルゴリズムである．
まず基本方針を説明する．
方針２ では方針１ と同様に，各クラスタヘッドはメッセージを隣接クラスタへ送信したい時，そのクラスタへのゲートウェイ候補の中からノードを一つ選択して，そのノードに対してメッセージを（宛先クラスタのクラスタヘッドID を添えて）送信する．
ただし，方針1 では両方のクラスタヘッドがそれぞれ自分から見た最適なゲートウェイ（経路）を送信時に決定し，メッセージを送信していたのに対し，方針2 では「強いクラスタヘッド」からのメッセージを受信した「弱いクラスタヘッド」は，以後「強いクラスタヘッド」の選択した経路を利用する．これにより，互いに隣接するクラスタのクラスタヘッド間の通信路が，双方向で一致する．ここで，よりID の小さなクラスタヘッドが「強い」クラスタヘッドとする．
【００４２】
方針２の手法をを実現するために，ネットワーク中の各ノードは方針1 と同様のTable_ gateway を保持する．この時，各ノードが持つTable_gateway の各エントリに，自分より強いクラスタヘッドが使用した経路を表す為の要素Flag を追加する．
以下に各ノードが保持する情報を説明する．
各ノードv はエントリに以下の要素を含むデータテーブルTable_gateway(表４) を保持する．方針2 で使用するTable_gateway は，方針1 で使用したTable_gatewayの各エントリに新たな要素Flag を追加したものである．
【００４３】
【表４】
2008219362.tif 000005
【００４４】
新たな要素Flag は，v のステータスによって次の意味を持つ．v がクラスタヘッドのとき，v が受信したv より強い（ID の小さい）隣接クラスタのクラスタヘッドからのメッセージをv へ送信したノードを示す．v は自分の隣接クラスタへのゲートウェイ候補であるエントリの中にこの値が1 であるエントリが存在するとき，そのエントリのgateway で指定されるノードへメッセージを送信する．一方，全てのエントリでFlag の値が0 の時は，方針1 と同じ動作を行う．v がメンバの時，Flag の値は利用しないため，全て0 とする．
Table_gateway の各エントリにはタイマー（生存時間）が用意されており，時間経過にあわせて値を0 から増加させてゆき，一定値になったときそのエントリを廃棄する．
Table_gateway  以外の情報は，方針１と同じである．
【００４５】
方針2 におけるTable_gateway の更新手順について説明する．Table_gateway の要素Flag 以外の更新については，方針1 のものと全く同様のメッセージ・手順を利用する．各クラスタヘッドが持つTable_gateway 内の要素Flag は，実際にTable_gateway を利用した通信を行うことで更新される．
つまり，方針1 ではhello パケットの送受信のみでTable_gateway の更新が行えるのに対し，方針2 ではhello パケットの送受信に加えて隣接クラスタ間で実際に通信が起こったときに，Table_gateway 内の要素Flagが更新される．
【００４６】
次に，各ノードが持つ Table_gateway を利用し，方針２によるクラスタ間の通信を実現するための手法を説明する．すなわち，各クラスタヘッドが自分のクラスタと隣接するクラスタのクラスタヘッドへメッセージを送信する際に実行する手順について説明する．以下，メッセージ送信元クラスタヘッドをSender，メッセージの送信先クラスタヘッドをDest とする．
まずクラスタ間通信用のメッセージを説明し，続いて通信に使用するゲートウェイ選択用関数を定義する．さらにクラスタ間通信の手順を説明する．
[クラスタ間通信用メッセージ]
(Sender.ID, Dest.ID, From.ID, To.ID, Message)
・Sender.ID： Sender のID．
・Dest.ID： Dest のID．
・From.ID： 通信用メッセージの送信元ノードID．
・To.ID： 通信用メッセージの宛先ノードのID．
・Message： Sender がDest に送信するメッセージの内容．
[クラスタ間通信に用いる関数]
・int selectnode(int Dest.ID)   
自身が持つTable_gateway のエントリの中で，Cneighbor がDest.ID であるエントリ集合のうち，(Flag,DN,gateway) の辞書式順序で最も大きいエントリのgateway の値(ID) を出力する関数．
[クラスタ間通信手順]
・メッセージ送信元クラスタヘッドSender の動作：
(Sender.ID, Dest.ID, Sender.ID, selectnode(Dest.ID), Message) を送信．
・メッセージ(Sender.ID, Dest.ID, From.ID, To.ID, Message) を受信した移動端末v が実行する動作：
受信したTo.ID がv 自身のID の時，v は通信用メッセージ( Sender.ID , Dest.ID, v.ID,
selectnode(Dest.ID), Message) を送信する．ただし，受信したDest.ID がv のクラスタヘッドID であった時は，v は通信用メッセージ( Sender.ID ,Dest.ID, v.ID, Dest.ID, Message) を送信する．あるいは，Dest がv 自身のID である時は，Message を受信して終了する．
なお，Dest がMessage を確認した際に，Sender.ID がDest.ID より小さければ，Dest.ID は自分のTable_gateway 内のエントリ< Sender.ID, From.ID, *, *, *> (*は任意の値を意味する）のFlag を1 にする．また，<Sender.ID, From.ID以外, *, *, *> のFlag を に
する．
【００４７】
Table_gateway を用いた方針２によるクラスタ間通信手法の具体例を図面を参照しながら説明する．
図２でh2 がh3 にメッセージを送信する例を考える．この時，方針1 とは異なりh2 ではゲートウェイとしてFlag が1 であるエントリ4 が選択される．つまりselectnode(h3.ID)==m4.IDとなる．従って，方針２ではh2はメッセージ(h2.ID, h3.ID, h2.ID, m4.ID, Message) を送信し，往復の経路を一意にする．
【００４８】
Table_gateway を用いた方針２によるクラスタ間通信手法の正しさを以下の通り証明する．
補題3. 本発明で提供する通信手法では，2 つのクラスタヘッド間の最短経路を用いて通信が可能である．
証明. 補題1 と同様である．
補題4. 本発明で提供する通信手法では，2 つのクラスタヘッド間のゲートウェイのみがメッセージを送信する．
証明. 補題2 と同様である．
補題5. 本発明で提供する通信手法では，やがて2 つのクラスタヘッド間の通信経路の往復が一意に決定する．
証明. 隣接する2 つのクラスタのクラスタヘッドをh1，h2 とし，h1 の方が強いとする．また，h1 からのメッセージがh1- g1- g2- h2 という経路でh2 に到達したとする．h2 は自分より強いクラスタヘッドh1 からのメッセージが到達した時点で，g2 にFlag をつける．以後，h2 がh1 にメッセージを送信する際，g2 にFlagが付いている為h2 はg2 にメッセージを送信する．この時，h1 がg1 を選択しているのでg1 はh1-h2 間の最適なゲートウェイである．従って，g2 もg1 を選択する（g2 が選んだ最適なゲートウェイがg1 以外であったなら，h1 はそのノードをゲートウェイとして選択しているはずである）．結果，h2 からh1 へのメッセージはh2-g2-g1-h1 という経路を辿るため，2 つのクラスタヘッドから送信されるメッセージは同じ経路を使用する．
定理4. 本発明で提供する通信手法を用いる事で，隣接するクラスタのクラスタヘッド間の双方向それぞれが同一の最短経路を用いた通信が正しく行える．
証明. 補題3，4，5 より明らかである．
【図面の簡単な説明】
【００４９】
【図１】Table_gatewayの更新のためのメッセージの具体例を示す．
【図２】Table_gatewayを用いた方針1によるクラスタ間通信の具体例を示す．
【図２】
2008219362.tif 000006
【図１】
2008219362.tif 000007