A Lightweight Distributed Method for Connectivity-based Clustering Based on Schelling's Model

摘要

In the literature, there exist connectivity-based distributed clustering methods called CDC (Connec­tivity-based Distributed node Clustering scheme) and SDC (SCM-based Distributed Clustering). CDC and SDC have mechanisms for maintaining clusters against nodes join and leave, but both methods do not assume frequent changes in the network topology. In this paper, we propose a lightweight distributed clustering method called SBDC (Schelling-Based Distributed Clustering), which is inspired by Schelling's model - a popular segregation model in sociology. We also evaluate the effectiveness of our proposed SBDC in environment with frequent changes in the network topology. Our simulation results show that SBDC outperforms CDC and SDC under frequent changes in the network topology caused by high node mobility. Connectivity-based Clustering, Mobile Ad-hoc Network, Schelling's Model%ネットワーク上の分散クラスタリング手法としてCDC（Connectivity-based Distributed node Clustering scheme）およびSDC（SCM-based Distributed Clustering）が提案されている。これらの手法はある程度のノードの参加・離脱に対してクラスタを更新し続けることができるが、ネットワークトポロジの頻繁な変化を想定していない。本稿では、人種間の分居現象を説明する社会モデルであるシェリングモデルに着想を得た、軽量な分散クラスタリング手法SBDC（Schelling-Based Distributed Clustering）を提案する。さらに、ネットワークのトポロジが頻繁に変化する環境におけるSBDC の有効性をシミュレーションにより評価する。その結果、提案するSBDC は、ネットワークトポロジが頻繁に変化する状況であっても、既存手法CDC およびSDC を大きく上回るクラスタ精度を達成できることを示す。