A k-hop Clustering Protocol for Dense Mobile Ad-Hoc Networks

Dense Mobile Ad-hoc NETworks (MANET), i.e., geographical areas with relatively high and almost constant density of mobile terminals communicating in ad-hoc mode (such as in airport terminals, shopping malls, and university campuses) are becoming deployment scenarios of growing and growing commercial interest. The effective determination of k-hop clusters in MANET is crucial to efficiently support many relevant tasks, e.g., packet routing, and has recently started to be investigated. The paper claims that the assumption of dense MANET permits to propose novel k-hop clustering solutions that outperform existing ones in terms of both effectiveness and limited overhead. In particular, the paper presents an innovative k-clustering protocol, based on circle covering, and quantitatively evaluates its performance when adopting different decentralized heuristics. The proposed protocol, coupled with original heuristics considering the positions of neighbor cluster-heads, has demonstrated to achieve better performance than other solutions in the literature with a significantly lower message overhead.