Systematic selection of cluster heads for data collection

We present a systematic approach to selecting cluster heads (CHs) in networked sensing systems for data aggregation based on the idea of dominating sets of a graph. A set of vertices, D   of a graph G=(V,E)G=(V,E) is a k  -dominating set if every vertex v∈Vv∈V, is connected to some vertex in D via path of length less than or equal to k. By focusing on regular mesh topologies, in which each node has q   neighbors, q=3,4,6,8q=3,4,6,8, we demonstrate an intuitive approach for identifying the CHs. If E is the energy required for a node to send a message to a collection point, e   is the energy required to send a similar message to its adjacent node in the system, and CC is the compression ratio achieved by aggregation techniques at a CH, we show that CHs selected in our approach are viable whenever k<(3.C.E/2e)−1/2k<(3.C.E/2e)−1/2. We present simulation results that validate the analysis and demonstrate how k affects the Quality of Service of the data aggregation scheme. Finally, we show that the approach extends to systems that have non-regular topologies.