Application-Based Optimization of Multi-Level Clustering in Ad Hoc and Sensor Networks

Multi-level clustering offers the scalability that is essential to large-scale ad hoc and sensor networks in addition to supporting energy-efficient strategies for gathering data. The optimality of a multi-level network largely depends on two design variables: 1) the number of levels and 2) the number of nodes operating at each level. We characterize these variables within a multi-hop multi-level hierarchical network of variable sizes that gathers and aggregates data at each level. Our network communication cost model (EEHC-VA) is parameterized by the size of the data forwarded at each level. We minimize the communication cost to obtain the optimal probabilities of distributed and independent selection of level-(n+1) nodes from level-n nodes. Interestingly, we have identified intervals-based on the number of nodes and aggregated data sizes-within which singleor two-level hierarchies are optimal. The results have been numerically verified for a wide range of parameters and validated with network simulations. Finally, the impact of these results on the network architectures is discussed for selected applications and aggregation schemes.