アド ホックネット ワークに おけ るクラスタ構成法
谷口 博人
†∗井上美智子
†増澤 利光
††藤原 秀雄
†Clustering Algorithms in Ad Hoc Networks
Hirohito TANIGUCHI†∗, Michiko INOUE†, Toshimitsu MASUZAWA††, and Hideo FUJIWARA†
あらまし 本論文では ，移動端末だけからなる分散移動シ ステムであるアド ホックネット ワーク上でのクラス タ構成法を考察する．クラスタ構成法とは ，ネット ワーク上の全ノード をクラスタヘッド とそれ と直接通信可能 な ノード であるクラスタ メンバからなるクラスタに 分割することである．移動端末は ，計算能力，通信能力など の点でパフォーマン スが 低いため ，移動端末にかか る負荷が 小さい手法が 望まれ る．分散シ ステムの問題とし て ， 端末の移動や ，トポロジーの変化に 伴うオーバヘッド を考慮し なければ ならない．更に ，無線チャネル の帯域幅 の空間再利用の観点など から ，クラスタ構成をすることによって ，階層構造を構築する利点がある．その際，ネッ ト ワークで交換する情報量を少なくするためクラスタヘッド を少なくすることや ，管理情報の受け 渡し を少なく するためクラスタヘッド の変更数を少なくすることが 望まれ る．本論文では ，アド ホックネット ワーク上に クラ スタを 構成するクラスタ構成法及び ，移動端末の移動など によりト ポロジ ーが 変化し た場合に 対応するクラスタ 再構成法を提案する．提案するクラスタ構成法は ，トポロジ ーグ ラフが 密な場合を除き，従来手法に 比べて クラ スタ数が 少ないこと ，また，提案するクラスタ再構成法は ，従来手法に 比べ，クラスタ数が 少なく，またクラス タヘッド の変更数が 少ないことをシ ミュレ ーション 実験で示す．
キーワード 分散アルゴ リズム，アド ホックネット ワーク，モバ イルコンピ ューテ ィング，クラスタ構成法
1. ま え がき
近年の移動計算機の普及に伴い，移動端末が 基地局 を介し てネット ワークに 接続するセルラシ ステムに 加 えて ，移動端末間で 直接通信を行うことのできる分散 シ ステムも利用され ている．本論文では ，移動端末だ けからなる分散シ ステムであるアド ホックネット ワー クに関し て ，ネット ワーク上の端末をクラスタに 分割 する クラ スタ構 成に ついて 考え る ．クラスタ構 成は ， ネット ワーク上の多数の端末を階層的に 効率良く管理 するため ，また，周波数等の資源を効率良く割り当て るために 用いられ ，クラスタ構成法に 関し て多くの研 究がなされ ている[1]∼[6]．
アド ホックネット ワークは ，移動端末だけからなる ネット ワークで ，各端末は ，地理的あるいは 論理的な
†
奈良先端科学技術大学院大学情報科学研究科 ，生駒市
Graduate School of Information of Science, Nara Institute of Science and Technology, 8916–5 Takayama-cho, Ikoma-shi, 630–0101 Japan
††大阪大学大学院基礎工学研究科 ，豊中市
Graduate School of Engineering Science, Osaka University, 1–3Machikaneyama-cho, Toyonaka-shi, 560–8531 Japan
∗
現在，NTTド コモ関西株式会社
通信可能範囲をもつ．互いに 通信可能な2端末間は 無 線チャネルを介し て通信を行うことができ，このとき， 2端末は隣接すると呼ぶ ．クラスタとは端末の集合で ， クラスタを 管理するクラスタヘッド とクラスタヘッド に 隣接するクラスタメンバからなる．ネット ワーク上 の全端末をクラスタで 被覆するように クラスタヘッド を選択することをクラスタ構成と呼ぶ ．ただし ，クラ スタヘッド 間の干渉を避け るために ，ど の二つのクラ スタヘッド も隣接し ないことを条件とする．
クラスタ構成は 以下の条件を満たすクラスタヘッド 集合H を求める問題と考えることができる．
• 支配性：各端末は Hに 属する，または ，H 中
の端末と隣接する．
• 独立性：H に 属するど の2端末も隣接し ない．
クラスタヘッド に 選択され た端末は ，クラスタ内及び ク ラ ス タ間 の 接 続 関 係 等の 情 報の 維 持 管 理と いった 負荷を伴うので ，クラスタヘッド 数は 小さい方が 望ま し い．
既存のクラスタ構成法とし て ，最大ID法[3]，最大 次数法[4]が 提案され て いる ．これら の手法では ，端 末と無線チャネルからなるトポロジ ーグ ラフに 対し て，
電子情報通信学会論文誌2001/2 Vol. J84–D–I No. 2
各端末に 対し てクラスタヘッド になる優先度を割り当 て ，最大の優先度をもつ端末をクラスタヘッド に 選択 し ，隣接端末とともにグ ラフから 削除するという処理 を繰り返す．最大ID法[3]は ，各端末に固有の優先度 を用いる手法でトポロジ ーを考慮し ないためクラスタ ヘッド 数を小さくできない．これに 対し ，最大次数法 はトポロジ ーを考慮し てクラスタヘッド 数を抑え るこ とを目的とし ている．し かし ，トポロジ ーに よっては クラスタヘッド 数が 小さくならない場合もある．本論 文では ，最大次数法で クラスタヘッド 数が 小さくなら ない場合も考慮する新たな優先度を利用し た重み付き 最大次数法を 提案する．シ ミュレ ーシ ョン 実験に よっ て ，トポロジーグ ラフが 密な場合を除き，提案手法が 従来法に 比べてより少ないクラスタヘッド を選択する ことを示す．
アド ホックネット ワークでは ，端末の移動に伴うト ポロジ ー変化への対応も考える必要がある．既に クラ スタが 構成され ているネット ワークにおいて ，トポロ ジ ーの 変化によって支配性，または 独立性が 成立し な くなった場合に ，クラスタを再構成することを考える． ク ラ スタ再 構成では ，クラ スタヘッド 数だ けで な く， 新たに クラスタヘッド になる，クラスタヘッド でなく なるといったクラスタヘッド 変更数も少ない方が 望ま し い．これは ，クラスタヘッド の変更によって，クラ スタヘッド が 維持管理する情報の交換が 必要になるた めである．
クラスタ再構成法とし ては ，既存のクラスタ構成法 を 適 用す るこ と も 考え られ る ．こ の 場 合 ，ク ラ ス タ ヘッド 数は 小さく抑えられ るが クラスタヘッド 変更数 は 大きくなってし まう．クラスタヘッド 変更数を小さ くする手法として，LCC（Least Cluster Change）法 が 提案され ている[5]．LCC法では ，トポ ロジ ーが 変 化し た場合に ，支配性，または 独立性が 成り立たない 部分だけで局所的にクラスタを再構成する手法である． LCC法は ，クラスタヘッド 変更数を 抑え ることに 主 眼が おかれ ，クラスタヘッド 数が 大きくなる場合もあ る ．本論文では ，LCC法で の クラスタ再構成法を 改 良し た 改良LCC法を 提案する．提案手法では ，クラ スタヘッド 変更数だけでなくクラスタヘッド 数を抑え ることも考慮し ている．シ ミュレ ーシ ョンによる比較 では ，提案手法がLCC法よりクラスタヘッド 数を 小 さく抑え ることを示す．また ，トポロジ ー変化とクラ スタ再構成を 繰り返し た場合，結果的に 改良LCC法 の方が クラスタヘッド 変更数が 小さくなるという結果
も示す．
2. 諸 定 義
2. 1 アド ホックネット ワーク
アド ホックネット ワーク（ 以下，ネット ワークと呼 ぶ ）は ，有 線チャネル や それ を 経 由す る 基 地 局を も たず，移動ノード だけで 構成され る．各ノード は 無線 が 有効な通信範囲内のノード とだけ 通信できる．ネッ ト ワー クのト ポ ロジ ーをグ ラフ G = (V, E)で 表す． V = {p1, p2, . . . , pn}は ノード の集合，Eは 無線チャ
ネルの集合である．各ノード piは 固有の識別子id(i) を もつ ．ノード pi と ノード pj が それぞ れ の 通信範 囲内に位置し ，互いに メッセージを送受信できるなら ， 無線チャネル(pi, pj)が 存在し ((pi, pj) ∈ E)，piと pjは 隣接し ているとい う．
2. 2 クラスタ構成
クラスタは ，ノード の部分集合で ，一つの クラスタ ヘッド とその全隣接ノード からなる．
［ 定義1］（ クラスタ ）ノード piをクラスタヘッド と するクラスタとは 以下の ノード 集合Cである．
C = {pi} ∪ {pj|(pj, pi) ∈ E}
クラスタヘッド に 隣接するノード をクラスタ メンバと
呼ぶ ． ✷
クラスタ構成とは ，全ノード を被覆するよ うに クラ スタヘッド 集合を選択することである．ただし ，クラ スタヘッド 間の干渉を避けるため ，隣接する2ノード をともに クラスタヘッド には選択できないとする．
［ 定義2］（ クラスタ構成 ）クラスタ構成とは，以下の 条件を 満たすよ うに クラスタヘッド 集合H を選択す ることである．
• 支配性：各ノード はH に 属する，または ，隣
接ノード がH に 属する．
• 独立性：H に 属す るど の2ノード も隣 接し な
い． ✷
図1にクラスタ構成の例を示す．
また ，本論文ではアド ホックネット ワークを構成す る ノード の 移 動に よりト ポ ロジ ーが 変化し たときに ， クラスタを 再構成する問題を考え る．
［ 定義3］（ クラスタ再構成）グラフGにおいて，ネッ ト ワークのクラスタ構成がなされ ているとする．ここ で ，グ ラフが Gから G
′
に 変 化し た と き ，G
′
に 対 す る ク ラ ス タ 構 成を 行 うこと を ク ラ ス タ 再 構 成と 呼
ぶ ． ✷
図1 クラスタ構成 Fig. 1 Clustering.
クラ スタ構 成 ，クラ スタ再 構成の 評価尺度とし て ， 以下の二つを用いる．
• クラスタ数（ クラスタ構成，再構成 ）
• クラスタヘッド の変更数（ クラスタ再構成 ）
グ ラフGのクラスタヘッド の集合をH，グラフG
′
で クラスタ再構成し たときのクラスタヘッド の集合を H′ とする．このとき，クラスタヘッド の変更数は ，
|H − H′| + |H′− H|
と定義する．
クラスタヘッド に 選択されたノード は ，クラスタ内 及び クラスタ間の 接続関係等の情報の 維持管理といっ た負荷を伴う．また，アプ リケーションレベルでは，ク ラスタヘッド 間の論理リン クからなるクラスタヘッド アーキテクチャを考え る．し たが って ，クラスタ数が 少ないと クラスタヘッド アーキテクチャのネット ワー クサイズが 小さくなるため ，ネット ワーク全体へ流れ るトポロジ ー管理情報など を減少させることができる． し たが って ，クラスタ数の小さいクラスタ構成法，ク ラスタ再構成法が 望まし い．
また ，クラスタヘッド が 変更され ると ，古いクラス タヘッド が もっていた 情報を新し いクラスタヘッド へ 渡す，若し くは 新し いクラスタヘッド が 新たに クラス タ メンバの 情報を収集する必要があり，クラスタヘッ ド の変更に伴い，オーバヘッド が 生じ る．し たがって，
クラスタヘッド の変更数が 小さいクラスタ再構成法が 望まし い．
本論文では ，与えられたトポロジ ーグ ラフに 対し て， クラスタ構成，または クラスタ再構成を行うグラフア ルゴ リズムを考察する．既存の多くのクラスタ構成法 で は ，クラ スタの 構 成 中にト ポ ロジ ーが 変 化す ると いった頻繁なトポロジー変化は仮定していない[4], [6]． これは ，トポロジ ー変化が 頻繁に 起こるネット ワーク では ，クラスタの維持にコ ストがかか ってし まい，ク ラ スタ構 成を する 利点が 失われ てし ま うからであ る ．
また ，本論文で 考察する 提案手法 ，及び 従来手法は ， ネット ワーク上の メッセージの伝送遅延のば らつき等 に 依存し ないアルゴ リズムであるため ，クラスタ構成 アルゴ リズムの実行中にトポロジ ー変化が 起きないと いう仮定のもとでは ，評価尺度であるクラスタ数，ク ラスタヘッド の変更数をグ ラフアルゴ リズム上で 評価 することが 可能である．以上のよ うな考察により，本 論文では クラスタ構成法，及び クラスタ再構成法をグ ラフアルゴ リズムとし て扱 う．ただし ，アルゴ リズム の評価尺度，後述するクラスタヘッド となる優先度等 はネット ワークでの実現を考慮し たものとなっている．
3. クラスタ構成法
3. 1 集中型，分散型クラスタ構成法
クラスタ構成法では 一般に各ノード に 対し てクラス タヘッド になる優先度を与え ，この優先度の高いノー ド から順にクラスタヘッド とし て選択する．このとき，
クラスタ構成法には 集中型と分散型の2種類が 考えら れ る．
集中型クラスタ構成法では ，まずネット ワーク全体 で最も優先度の高いノード をクラスタヘッド に選択し ， 選択し たクラスタヘッド とそれに 隣接するノード を削 除する．残ったノード に 対し て優先度を再計算し ，同 じ 手続きを 繰り返す．これを ，ノード が すべて削除さ れ るまで 繰り返す．集中型クラスタ構成法は ，優先度 を正確に 反映することができるが ，ネット ワークの大 域的な情報を必要とする．つまり，ネット ワーク上で 実現し た場合，ネット ワーク全体のノード 情報を知る 必要があるため ，通信量など ネット ワークへの負荷が かか ってし まう．また，クラスタヘッド を 一つず つ決 定し ていくので ，クラスタ構成にかかる時間も大きい．
分散型クラスタ構成法は ，集中型クラスタ構成法の ようにネット ワーク全体で 優先度の比較を行うのでは なく，あるノード の優先度がど の隣接ノード の優先度 よ り 高ければ そ の ノード を クラ ス タヘッド とし て 選 択する．そし て ，これらのクラスタヘッド とその隣接 ノード を削除し ，残った ノード に 対し て優先度を再計 算し ，同じ 手続きを 繰り返す．
分散型クラスタ構成法では ，隣接ノード の情報だけ で クラスタヘッド を 決定し ていく．し たが って ，ネッ ト ワーク上で実現し た場合，集中型クラスタ構成法に 比べて ，クラスタヘッド 決定のために 交換する情報量 が 少ない．また，ネット ワークの異なる部分で ，同時 に クラスタヘッド を決定できるので ，迅速に クラスタ
電子情報通信学会論文誌2001/2 Vol. J84–D–I No. 2
ヘッド を決定し ていくことが 可能である．
図2に 集中型クラスタ構成法を ，図3に 分散型ク ラスタ構成法を示す．このプ ログ ラムで 用いている変 数，関数，手続きは 以下のとおりである．
• H：クラスタヘッド 集合．
• S：ど の クラ スタに も含まれ ていな いノード の
集合．
• G[S]：SによるGの誘導部分グ ラフ（induced subgraph）．
• Γ(x)： ノード xの隣接ノード の集合．
• Γ(X)：X に 属するノード に 隣接するノード の
集合．つまり，Γ(X) = ∪x∈XΓ(x)．
• max(S)：ノード 集合Sの中で優先度が 最も高
いノード を返す関数．
• maximal(S)：ノード 集 合 S の 中で ，優先 度 が 極大（Sに 属するど の隣接ノード よりも優先度が 高 い ）ノード 集合を返す関数．
• compute priority(G)：Gの各ノード の優先度
を計算する手続き．
3. 2 最大ID法，最大次数法
前節で 述べたクラスタ構成法では ，用いる優先度に より，様々なクラスタ構成を 行うことができる．本論
Centralized Clustering(G) { S= V ;
H= ∅;
compute priority(G); /* 優先度の計算 */ while(S |= 0) {
x= max(S); /* 優先度最大ノード を選択 */ H= H ∪ {x};
S= S − ({x} ∪ Γ(x));
compute priority(G[S]); /* 優先度の再計算 */ }
}
図2 集中型クラスタ構成法 Fig. 2 Centralized clustering algorithm.
Distributed Clutering(G) { S= V ;
H= ∅;
compute priority(G);/* 優先度の計算 */ while(S |= 0) {
X= maximal(S); /* 優先度極大ノード を選択 */ H= H ∪ X;
S= S − (X ∪ Γ(X));
compute priority(G[S]); /* 優先度の再計算 */ }
}
図3 分散型クラスタ構成法 Fig. 3Distributed clustering algorithm.
文では ，ネット ワークで 効率良く実現することを考慮 し て ，優先度とし ては ，局所的に 決定できるものに 限 定する．本節では ，既存の優先度の算出法とし て ，最 大ID法と最大次数法について述べる．
最大ID法は ，IDの大きいノード ほど 高い優先度を 割り当てる．つまり，各ノード piのグ ラフGにおけ る優先度priority(G, pi)を次式で 与え る．
priority(G, pi) = id(i);
図4に 最大ID法に よる クラ スタ構 成の 例を 示す． 図中の数字は ，各ノード のIDを示す．
最大ID法では ，各ノード の 優先度はグ ラフに 関係 なく一定のため 優先度の再計算を行う必要はない．ま た ，集中型，分散型とも同じ クラスタヘッド が 選ばれ る．し かし ，トポロジ ーを 考慮せずに 優先度を決定す るので ，クラスタヘッド が 多くなる．
トポロジ ーを考慮し てクラスタヘッド を少なくする ク ラ ス タ 構 成 法とし て ，最 大 次 数 法が 提 案され て い る[4]．最大次数法では ，次数の大きい ノード から順に クラスタヘッド にすることにより，できるだけ 多くの ノード をクラスタに 含んでいく．つまり，各ノード pi のグ ラフGにおける優先度priority(G, pi)を次式で 与え る．
priority(G, pi) = |ΓG(pi)|;
ここで ，ΓG(pi)はグ ラフ Gに おけ るノード piの 隣接ノード を表す．また ，ノード の優先度が 同じ 場合 は ，IDの大きいノード を優先させる．クラスタヘッド が 決定され るにつれ て ，図2，図3のG[S]（Sはど のクラスタにも含まれないノード の集合 ）は 変化する ので ，最大次数法では G[S]の変化に 応じ て ，優先度 を再計算し なければ ならない．また ，集中型と分散型 では クラスタヘッド となるノード や ，クラスタ数が 異 なることがある．
図5に最大次数法によるクラスタ構成の例を示す．
図4 最大ID 法
Fig. 4 Highest ID clustering algorithm.
(a)
(b)
図5 最大次数法(a) 集中型 (b) 分散型 Fig. 5 Highest degree clustering algorithms.
(a) Centralized algorithm. (b) Dis- tributed algorithm.
(a)は 集中 型 ，(b)は 分散型に よる クラスタ構 成で あ
る．この例では ，図4の 同じ ネット ワークに 対し て ， 最大ID法に 比べて ，最大次数法では クラ スタヘッド 数を削減し ている．
3. 3 重み付き最大次数法
最大次数法は ，最大ID法に 比べて クラ スタヘッド の 数 を 少な く 抑え るこ とが で き る ．し かし ，例えば 図6のグ ラフに最大次数法を適用すると ，図6 (a)の よ うに な る ．こ の ク ラ ス タ 構 成で は ，最 初に ノード p8 を クラ スタヘッド に 選択し ，次数の 小さい ノード p1, p3, p5, p6が 残るため ，ノード 数が 二つだけのクラ
スタが 多数できてし まう．このため ，全体のクラスタ ヘッド 数が 多くなってし まう．そこで ，このような最 大次数法の欠点を解決するために ，重み付き最大次数 法を提案する．
提案する優先度は 次数の低いノード を ，より多く隣 接ノード とし てもつノード に高い優先度を与える．そ のために ，隣接ノード の次数の逆数の和を優先度とす る．つまり，各ノード piのグ ラフGにおけ る優先度 priority(G, pi)を次式で 与え る．
priority(G, pi) =
j∈ΓG(pi)
1/|ΓG(pj)|;
重み付き最大次数法を図6に適用すると，その 優先 度は図6 (b )のようになり，図6 (c)のようにクラスタ が 構成され ，最大次数法に 比べ，クラスタ数を少なく
(a) (b)
(c)
図6 (a) 最大次数法 (b) 重み付き最大次数法による優先 度(c) 重み付き最大次数法
Fig. 6 (a) Highest degree clustering algorithm. (b) Priority of weighted highest degree. (c) Weighted highest degree clustering algorithm.
することができる． 4. クラスタ再構成法
4. 1 LCC法（Least Cluster Change clus- tering algorithm）
アド ホックネット ワークでは ，ノード の移動による ネット ワークトポロジ ーの 変化を考慮し なければ いけ ない．トポロジ ー変化に 応じ てクラスタヘッド を変更 し なければ ならないが ，クラスタヘッド の変更が 生じ ると ，クラスタヘッド のもつ管理情報を更新するため に ，大きなオーバヘッド を生じ る．そこで ，クラスタ 再構成アルゴ リズムでは クラスタヘッド の変更数をで きるだけ 少なくすることが 望まれ る．
トポロジ ーの変化により，ど のクラスタヘッド にも 隣接し ない ノード が 生じ 支配性が 成り立たな い場 合 ， クラスタヘッド が 隣接し 独立性が 成り立たない場合に ， クラスタを 再構成する必要がある．このとき，前節の クラスタ構成法を適用し ，（ その 時点でのクラスタヘッ ド を考慮せずに ）一から クラスタを 構成することも可 能であるが ，クラスタヘッド の変更数が 大きくなって し まう．
そこで ，クラスタヘッド の変更を抑え るクラスタ再 構成法として，LCC法[5]が提案されている．LCC法 では ，次の二つの場合のみクラスタヘッド の変更を局
電子情報通信学会論文誌2001/2 Vol. J84–D–I No. 2
所的に 行う．
（1）二つのクラスタヘッド が 隣接し た場合，優先 度の低い方のクラスタヘッド が クラスタヘッド の役割 をやめる．このために ，ど のクラスタヘッド にも隣接 し ないノード が 生じ た場合には ，クラスタ構成法によ り，それらの中からクラスタヘッド を選ぶ．
（2） ど の ク ラ ス タヘッド と も 隣 接し な く なった ノード が 生じ た場合，クラスタ構成法により，それら の中から クラスタヘッド を選ぶ．
図7を用いて ，この動作を説明する．優先度は簡単 のため ，最大ID法を 用いる ．ノード 移動に より，ク ラスタヘッド p1, p2が 隣接し たとする（ 図7 (b )）．こ のと き ，優先度の低い ノード p1 が クラスタヘッド の 役割を 放棄する（ 図7 (c)）．図 7 (c)に おいて ，ど の クラスタヘッド にも隣接し ないノード は p3だけであ るので ，p3が 新たに クラスタヘッド となる．
LCC法を 図8に 示す．ここでは ，以下の変数，関
数を用いている．
• H：トポロジ ー変化前のクラスタヘッド 集合．
• G′：トポロジ ー変化後のグ ラフ．
図7 LCC 法によるクラスタ再構成の例 Fig. 7 An example of re-clustering by LCC
algorithm.
LCC Clustering{ compute priority(G′); X= maximal(H);
/* G′に おけ るH の極大独立頂点集合*/ G′′= G′[V − (X ∪ Γ(X))];
H′= X ∪ Clustering(G′′); }
図8 LCC 法 Fig. 8 LCC algorithm.
• H′：G′でのクラスタヘッド の集合．
• Clustering(G′′)：クラスタ構成法により，G
′′
のクラスタヘッド 集合を返す関数． 4. 2 改良LCC法
LCC法に おいては ，ノード の 移動に より 二つの ク
ラスタヘッド が 隣接し た場合は ，一方の クラスタヘッ ド はそのままクラスタヘッド となり，クラスタヘッド の 役 割をやめ るノード を 一つに 抑え て いる ．し かし ， クラスタヘッド を続け るノード がトポロジ ー変化後の グ ラフに おいても ，高い優 先度を もつとは 限ら な い ． このため ，もとのクラスタヘッド をクラスタヘッド と し て残すことで ，新たに クラスタヘッド となるノード 数が 増え ることも考えられ る．
そこで 本論文では ，改良LCC法を 提案する．改良 LCC法ではクラスタヘッド が隣接し た場合，いったん
両方のクラスタヘッド が 役割を放棄する．その後，ど のクラスタヘッド にも隣接し ていないノード の集合に 対し クラスタ構成法を用いて ，クラスタを再構成する． このことにより，トポロジ ー変化後のグ ラフにおいて 優先度の高いノード をクラスタヘッド とし て選択する ことが で き ，LCC法に 比べて クラスタヘッド 数を 減 らすことができると考えられ る．
具 体 例を 図9に 示す．クラ ス タヘッド が 隣接す る (b)までは ，図7と同じである．改良LCC法では ，ク
ラスタヘッド p1, p2が両方いったんクラスタヘッド の 役割をやめる（ 図9 (c)）．そし て ，ど のクラスタヘッ ド に も隣接し ないノード 集合p1, p2, p3, p4, p5で 優先 度を再計算すると，ノードp5がクラスタヘッド になる
図9 改良LCC 法によるクラスタ再構成の例 Fig. 9 An example of re-clustering by improved LCC
algorithm.
Improved LCC Clustering{ compute priority(G′);
X= {p | p ∈ H, ΓG′[H](p) = ∅}; /* G′[H] における孤立ノード 集合 */ G′′= G′[V − (X ∪ Γ(X))];
Clustering(G′′); }
図10 改良LCC 法 Fig. 10 Improved LCC algorithm.
（ 図 9 (d)）．この 例では ，LCC法に 比べ ，改良LCC 法では クラスタヘッド が 一つ減って いる ．改良LCC 法を 図10に 示す．用いて いる 変数，関数はLCC法
（ 図8）と同じ である． 5. 実験結果，考察
5. 1 クラスタ構成法の比較
本節では ，既存の最大ID法と最大次数法，本論文で 提案し た重み付き最大次数法について ，集中型，分散 型クラスタ構成法のそれぞれに 関するシ ミュレ ーシ ョ ン 結果を示す．
シミュレ ーションは ，ノード 数は100，200，300の 三つの 場合に対し て行った ．いずれの場合もノード を 一様乱数によって1000 × 1000のフィールド 上に配置 する．また ，各ノード の通信範囲はその ノード を中心 とする円とし ，半径50，100，150，200，250，300の 場合について行った ．
表1に集中型クラスタ構成法を実行し たときのクラ スタヘッド 数を，表2に分散型クラスタ構成法を実行 し たときの クラスタヘッド 数を示す．それぞれ100回 初期配置をし て ，クラスタ構成をし たときの平均値を 示し ている．
集中型クラスタ構成法のクラスタヘッド 数を比較す ると ，ほとんど の場合で 重み付き最大次数法が 他の手 法より少ないクラスタヘッド 数になっている．特に 通 信半径が 小さいときほど 差は大きくなっている．また ， ノード 数が 多く，通信半径が 大きくなったときに ，最 大次数法の方が クラスタヘッド の数が 少なくなってい る．この場合のグ ラフは ノード の平均次数が 高くなっ ていて ，次数の低いノード があまり存在し ていないた め ，重み付き最大次数法の効果が 現れないと考えられ る．最大ID法は例外なくクラスタヘッド 数は多くなっ ている．これは ，トポロジ ーに 関係なく優先度を決定 し ているためである．
分 散 型 ク ラ ス タ 構 成 法の ク ラ ス タヘッド 数を 見 る
表1 集中型クラスタ構成法のクラスタヘッド 数 Table 1 The number of clusterheads by centralized
clustering algorithms.
重み付き 全ノード 数 通信半径
最大次数法
最大次数法 最大ID 法 50 69.80 69.94 72.58 100 33.30 34.86 40.62
100 150 18.43 20.00 24.24
200 12.27 13.26 16.02
250 9.29 9.90 11.38
300 6.63 6.92 8.73
50 101.52 103.01 113.47 100 38.63 41.77 50.71
200 150 21.44 23.20 27.76
200 13.83 14.88 17.71 250 11.01 11.12 12.51
300 7.84 7.76 9.30
50 117.71 121.03 138.79 100 41.92 45.41 55.84
300 150 23.17 24.76 29.49
200 15.06 15.52 18.51 250 12.08 11.82 12.82
300 8.60 8.27 9.54
表2 分散型クラスタ構成法のクラスタヘッド 数 Table 2 The number of clusterheads by distributed
clustering algorithms.
重み付き 全ノード 数 通信半径
最大次数法
最大次数法 最大ID 法 50 69.81 69.94 72.58 100 33.71 35.01 40.62
100 150 19.43 20.15 24.24
200 12.89 13.47 16.02
250 9.45 9.96 11.38
300 6.97 7.02 8.73
50 101.74 103.24 113.47 100 40.56 42.14 50.71
200 150 22.47 23.25 27.76
200 14.28 15.02 17.71 250 10.98 11.18 12.51
300 8.34 7.92 9.30
50 118.62 121.68 138.79 100 44.29 45.81 55.84
300 150 24.08 24.81 29.49
200 15.84 15.58 18.51 250 12.00 11.99 12.82
300 9.41 8.44 9.54
と ，集中型クラスタ構成法によって決定され たクラス タヘッド 数より多くなってはいるが ，それほど 値は 変 わっていない．更に ，集中型クラスタ構成法と同様に ， トポロジ ーグ ラフが 密な場合を除いて ，重み付き最大 次数法が 他の手法より少ないクラスタヘ ッド 数になっ ている．
5. 2 LCC法と改良LCC法の比較
本節では ，LCC法[5]と ，4.で 提案し た改良LCC
電子情報通信学会論文誌2001/2 Vol. J84–D–I No. 2
法に 関するシ ミュレ ーシ ョン 結果を示す．
シミュレ ーションは ，ノード 数は100，200，300の 三つの 場合に対し て行った ．いずれの場合もノード の 通信半径は200とし た ．シ ミュレ ーシ ョン の方 法は ， 5. 1と 同じ 方 法で ，まず 初 期 配 置を 決めた 後に クラ
スタ構成法を 実行する．その後 ，全ノード は 確率1/2 で 移動するノード と移動し ないノード に 分け，移動す る ノード は 確率1/4で 上下左右方向に 動くもの とし ， LCC法 ，改 良LCC法に 従って ，クラ ス タ 再 構 成を
行った ．クラスタ再構成法でサブ ルーチンとし て用い るクラスタ構成法には ，集中型重み付き最大次数法を 採 用し た ．ノード 数200の 場 合の クラ ス タヘッド の 変化を 図11に 示す．グ ラフでは ，クラスタヘッド 数 を1000単 位時間ご とに10000単 位 時間まで 表し た ． 1000単位時間ご とで の ク ラ スタヘッド 数は ，その 時 点の100単位時間前から の平 均をとって いる ．更に ， 10000単位時間のシ ミュレ ーシ ョンを異なる初期配置
に 対し て，10回試行し ，その平均をとっている．表3 は ，クラスタヘッド の変更数を示す．変更数は ，10回 試行の平均をとっている．
LCC法では ，移動回数の増加に伴い，クラスタヘッ
ド 数は初期値から上がって16程度で安定している．こ れに 対し て ，改良LCC法では ，移動回数が 増加し て もクラスタヘッド 数はほとんど 増加し ない．また，改
図11 クラスタヘ ッド 数（ ノード 数：200） Fig. 11 The number of clusterheads (the number of
node: 200).
表3 クラスタヘ ッド 変更数
Table 3The number of changes of clusterheads. ノード 数 改良LCC 法 LCC 法
100 562.9 646.4 200 718.0 820.3 300 757.8 948.7
良LCC法はLCC法よりク ラスタヘッド の 変更数が 少ないとい う結果が 得られた．
以上のよ うに ，クラスタヘッド 数，クラスタヘッド の変更数の両方において ，改良LCC法は ，LCC法よ りすぐ れており，移動分散シ ステムのクラスタ維持に 適し た手法といえ る．
6. む す び
本論文では ，移動端末だけからな るアド ホックネッ ト ワークでのクラスタ構成法とし て重み付き最大次数 法を提案し た．更に ，移動に伴いクラスタを 再構成す る手法とし て改良LCC法を提案し た ．
また 本 論 文で 提 案し た 重み 付き 最 大 次 数 法と 既 存 手法の 最大次数法，最大ID法を クラスタヘッド 数に ついてシ ミュレ ーシ ョンにより評価し た ．シ ミュレ ー ション 結果により，トポロジ ーグ ラフが 密な場合を除 き，提案手法では クラスタヘッド 数が 少なくなること が 示され た ．更に ，改良LCC法とLCC法を クラス タヘッド 数，クラスタヘッド の変更数についてシ ミュ レ ーシ ョンにより評価し た ．シ ミュレ ーシ ョン 結果に より，提 案手法では クラ スタヘッド 数を 少な く 抑え ， クラスタヘッド 変更数においても少なくなることが 示 され た ．
本論文では ，クラスタ構成法，クラスタ再構成法を グ ラフ アルゴ リズ ムとし て 考察を 行い ，クラスタ数 ， クラスタヘッド の変更数に 関し て評価を行った．提案 手法を ネット ワー クで 実現し た 場合の クラ スタ構 成 ， 及び クラスタ再構成にかかわる通信量の評価等は 今後 の課題である．
謝辞 本研究に 関し ，多くの貴重な意見を頂いた 本 学の大竹哲史助手及び 情報論理学講座の皆様に感謝し ます．本研究の一部は ，文部省科学研究費補助金（ 特 定領域研究B-2 10205218），及び ，中部電力基礎技術 研究所研究助成による．
文 献
[1] S. Basagni, “Distributed clustering for ad hoc net- works,” Proc. International Symposium on Parallel Architectures, Algorithms, and Networks, pp.310– 315, 1999.
[2] S. Basagni, “A distributed algorithm for finding a maximal weighted independent set in wireless net- works,” Proc. IASTED International Conference, Parallel and Distributed Computing and Systems, pp.517–522, 1999.
[3] A. Ephremides, J.E. Anthony, and D.J. Baker, “A de- sign concept for reliable mobile radio networks with
frequency hopping signaling,” Proc. IEEE, vol.75, no.1, pp.56–73, 1987.
[4] M. Gerla and J.T.C. Tsai, “Multicluster, mobile, multimedia radio network,” ACM-Baltzer J. Wireless Networks, vol.1, no.3, pp.255–265, 1995.
[5] C.C. Chiang, H.K. Wu, W. Liu, and M. Gerla, “Rout- ing in clustered multihop, mobile wireless networks with fading channel,” Proc. IEEE Singapore Interna- tional Conference on Network, 1996.
[6] C.R. Lin and M. Gerla, “Adaptive clustering for mobile wireless networks,” IEEE J. Selected Areas in Communications, vol.15, no.7, pp.1265–1275, 1997.
（ 平成12 年 4 月 20 日受付，8 月 11 日再受付）
谷口 博人
平10 神戸大・工・電気電子卒．平 12 奈 良先端大博士前期課程了．同年NTT ド コ モ関西（ 株 ）に 入社．
井上美智子 （ 正員 ）
昭62 阪大・基礎工・情報卒．平 1 同大 大学院博士前期課程了．同年富士通研究所
（ 株 ）入社．平7 阪大大学院博士後期課程 了．奈良先端科学技術大学院大学情報科学 研究科助手，現在に 至る．分散アルゴ リズ ム，グ ラフ理論，テスト 容易化設計，高位 合成の研究に 従事．工博．IEEE，情報処理学会，人工知能学 会各会員．
増澤 利光 （ 正員 ）
昭57 阪大・基礎工・情報卒．昭 62 同大 大学院博士後期課程了．同年同大情報処理 教育セン ター助手．同大基礎工助教授を経 て ，平6 奈良先端科学技術大学院大学情報 科学研究科助教授 ，平12 大阪大学基礎工 教授．平5 コーネル大客員準教授（ 文部省 在外研究員 ）．分散アルゴ リズム，並列アルゴ リズ ム，テ スト 容易化設計，テスト 容易化高位合成に関する研究に従事．工博． ACM，IEEE，EATCS，情報処理学会各会員．
藤原 秀雄 （ 正員 ）
昭44 阪大・工・電子卒．昭 46 同大大学 院博士後期課程了．阪大工学部助手，明治 大理工学部教授を経て，現在奈良先端科学 技術大学院大学情報科学研究科教授．昭56 ウォータール ー 大 客員助教授．昭59 マッ ギル大客員準教授．論理設計，高信頼設計， 設計自動化，テスト 容易化設計，テスト 生成，並列処理，計算 複雑度に 関する研究に 従事．著書“Logic Testing and Design for Testability” (The MIT Press) など ．大川出版賞．工博． IEEE，情報処理学会各会員，IEEE Fellow，IEEE Golden Core Member．
