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

Shih Ming Lo, Wu-Hsiung Lin*, Chiuyuan Chen, Yu-Chee Tseng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish
Pages (from-to)23-36
Number of pages14
JournalTheoretical Computer Science
StatePublished - 14 Nov 2017


  • Coloring
  • Communication network
  • Data collection
  • Graph theory
  • Wireless sensor network

Fingerprint Dive into the research topics of 'Optimal coloring for data collection in tree-based wireless sensor networks'. Together they form a unique fingerprint.

Cite this