k-hop Backbone Formation and Cluster Maintenance in Ad Hoc Networks

Several recent research activities have started to recognize the relevant role of k-hop clustering in Mobile Ad hoc NETworks (MANET) to effectively support many relevant tasks, e.g., packet routing and information dissemination at the network and application layer, respectively. k-hop clustering determination and maintenance is especially crucial to achieve good scalability in dense MANET scenarios, i.e., geographical areas with relatively high and almost constant density of mobile devices communicating in ad-hoc mode (such as in airport terminals, shopping malls, and university campuses), which are becoming of growing industrial relevance. The paper specifically addresses a primary aspect not yet widely investigated in the literature about k-hop clustering: how to exploit the k-hop clustering process also to effectively build an optimal backbone connecting all clusterheads identified by the process. We propose an original k-hop backbone formation protocol that, under the dense MANET assumption, outperforms other solutions in the literature especially in terms of imposed overhead, by exploiting highly localized intra-cluster interactions and by avoiding any kind of multi-hop broadcasts.