A Domination Approach to Clustering Nodes for Data Aggregation

We present a systematic approach to selecting cluster heads in regular mesh topologies based on the idea of k- Domination in graphs. Given a graph, G=(V,E), a subset D of V is said to be a 1-dominating set if every node v in V is either in D or is adjacent to a node in D. A subset D is said to be a k- dominating set if every node v, not in D, is connected to a node in D via a path of length less than or equal to k. Using regular mesh topologies that are obtained by embedding a collection of nodes in a two dimensional grid, where each node has q neighbors, we show how k-dominating sets impact the energy consumed and the quality of service of the data aggregation. We present simulation results that validate the results.