MANET でのグループの移動を考慮した安定なクラスタリング手法

黒岩潤平 (0951043)


近年,携帯電話や PDA などの無線端末が広く普及し,モバイルアドホックネットワーク (Mobile Ad-Hoc Network : MANET) への注目が高まっている.クラスタリングはネットワークの階層的な管理を実現する手法であり,大規模な MANET 運用の要素技術である.MANET におけるクラスタリングでは,ネットワークを頂点重み付きグラフとして扱った手法が多く提案されている.これらの手法では,ノードの重み割り当ての方法によってクラスタ構造が頻繁に変化する可能性がある.クラスタ構造が変化すると,クラスタの管理情報を通信する必要がある.クラスタ構造の安定性を向上させる方法として,ノードの具体的な移動状況を想定し,その特徴を活かして重みを割り当てる方法が考えられる.クラスタ構造の安定性に着目したノードの重み割り当て手法もいくつか提案されているが,ノードの具体的な移動状況を想定した手法は少ない.

本研究では,クラスタの安定性を改善するために,ノードが集団で移動する状况に基づいたノードの重み割り当て手法を提案する.特に,イベント会場や駅周辺で見られる,歩行者が集団を形成して移動する状況を想定する.提案手法では,まず各ノードが隣接するノードのうち自身と移動特性が近い局所グループを検出する.その後集団の合流や交差に対応するために局所グループの移動軌跡,サイズ,移動ベクトルに基づいて各ノードに重みを割り当てる.

また本研究では,ノードの移動モデルとしてランダムトラッキングスウォーム (Random Tracking Swarm : RTS) モデルを提案する.RTS モデルは集団の成長と崩壊を扱ったモデルである.RTS モデルでは,仮想的な存在であるゴーストがグラフで表現されたフィールド上をランダムに移動しており,各ノードはこのゴーストに従って移動する.各ノードとゴーストはグラフ上の各頂点で移動方向とゴーストからの離脱/合流を確率的に選択する.

本研究ではこの RTS モデルにおける提案手法のクラスタ構造の安定性を解析した.クラスタ構造の安定性の評価指標として,ノードがクラスタヘッドになってから通常ノードになるまでの時間であるクラスタヘッド維持時間の期待値を示した.

さらにシミュレーション実験を行い,RTS モデルに対して,提案手法のクラスタの安定性を確認した.クラスタの安定性は,クラスタヘッドの変化回数,クラスタメンバの変化回数,クラスタヘッド維持時間から総合的に検討した.従来手法と比較した結果,提案手法は最も増加率が大きい場合,クラスタヘッドの変化回数が 54% 増加したが,削減率と延長率が最も小さかった場合でも,クラスタメンバの変化回数を 51% 削減し,クラスタヘッド維持時間を 58% 延長した.クラスタヘッド変化回数の値は増加したが,クラスタメンバの変化回数の削減率とクラスタヘッド維持時間の増加率がともに大きく,提案手法は比較手法よりも高い安定性を示した.