| In this thesis we propose a randomized distributed protocol for heterogeneous wireless sensor networks (WSNs) with two kinds of nodes: White nodes and red nodes. The aim of our protocol is to find a set of red nodes as small as possible fulfilling the requirement that every white node is neighbor to (or is covered by) at least ru red nodes.;Our protocol, termed REDS, proceeds in phases that are distributed and localized, producing the set of red nodes that provide the required covering. We implement REDS in the simulator Castalia, using the CC2420-based radio hardware model. In the experiments we evaluate the performance of REDS in terms of the size of the covering set and of node energy consumption in scenarios with varying percentages of white nodes and covering requirements. We observe that the size of the covering set reduces as the number of nodes increases and is proportional to both the percentage of white nodes as well as the covering requirement ru. In addition, the average energy consumption of a node running REDS grows with the network size, with the percentage of white nodes in the network and with the covering requirement r u. We compare the REDS protocol with a centralized algorithm for set covering, termed BESTDEGREES, and observe that in general REDS produces sets of covering (red) nodes that are smaller than those produced by BESTDEGREES. |
