Networked embedded systems comprise a large number of deeply embedded nodesthat are interconnected via low power, low bandwidth, wireless links. Data from these nodes must be collected for monitoring and decision-making in applications such a real-time surveillance. It is not feasible for every node to directly send all its data to one or more collection points because of the data volume and power constraints at each node, and the low bandwidth of the wireless links. Data aggregation techniques enable the gathering and processing of data in such contexts.
The use of cluster heads (CHs) for data aggregation is an important approach
that is widely reported in the literature. A cluster head is a special node in the system that can aggregate data in its neighborhood and forward the aggregated data towards the collection points. Depending on how the the CHs are connected, the network of CHs can either be at or hierarchical. Nevertheless, the CHs are selected either in an ad-hoc manner, or by using an estimate of the remaining energy in the nodes. The current approaches do not exploit the topology of the system to select CHs. The idea of dominating sets in graphs oers an alternative, systematic, approach to identifying CHs.
This thesis considered regular mesh topologies in which each node has q neighbors, q = 3; 4; 6; 8. For each of these topologies, intuitive patterns which enable an easy determination of the dominating sets and the location of the CHs, are presented. It is shown that the parameter k impacts the energy efficiency and the Quality of Service (QoS) of the data aggregation scheme. Simulation results provide insights into the eects of the topology. In the future, this work can be extended to address data aggregation in general topologies.