The cluster density of a distributed clustering algorithm in ad hoc networks
Christian Bettstetter · 2004
Given is a wireless multihop network whose nodes are randomly distributed according to a homogeneous Poisson point process of density /spl rho/ (in nodes per unit area). The network employs Basagni's distributed mobility-adaptive clustering (DMAC) algorithm to achieve a self-organizing network structure. We show that the cluster density, i.e., the expected number of cluster- heads per unit area, is /spl rho//sub c/= /spl rho//spl divide/(1+/spl mu//spl divide/2), where /spl mu/ denotes the expected number of neighbors of a node. Consequently, a clusterhead is expected to incorporate half of its neighboring nodes into its cluster. This result also holds in a scenario with mobile nodes and serves as a bound for inhomogeneous spatial node distributions.