Optimal coloring for data collection in tree-based wireless sensor networks

Data collection is an important operation in a wireless sensor network (WSN). During data collection, the interference among nodes cannot be ignored. In a multi-hop WSN, one conventional way of defining interference neighbors is to prohibit a node from using the same time slot as those of its 1-hop and 2-hop neighbors. Recently, it is proved that for data collection in a WSN, since the set of communication nodes is limited and the transmission directions are toward the sink, a less strict set of interference neighbors can be defined [16]. The interference problem in a duty-cycle WSN (DC-WSN) with a corona structure is studied in [7]. In this paper, we solve the same problem by using the relaxed interference set defined in [16]. In particular, we give a complete classification of non-interference sets in 2-hop neighbors. We also propose a distributed 6-coloring algorithm. We prove a lower bound of six colors that every tree-based data collection algorithm requires in a dense DC-WSN, which proves our algorithm to be optimal.