ADAPTIVITY OF A COLORING ALGORITHM TO UNRELIABLE COMMUNICATIONS FOR DATA GATHERING IN WIRELESS SENSOR NETWORKS

Wireless sensor networks (WSNs) are prone to node/link failures, message losses, and dynamic node joins and departures. For instance, in data gathering applications that constitute a common type of applications in WSNs, links between nodes and their parent in the data gathering tree may be broken. Protocols supporting such applications should adapt their behaviour to guarantee reliable wireless communications while keeping a low overhead. In particular, this paper focuses on the optimization of a known coloring algorithm called SERENA (a€ SchEdule RoutEr Node Activitya€ ). SERENA assigns colors to nodes such that no two interfering nodes share the same color. Each color is mapped to a time slot during which nodes having the associated color can transmit data. To ensure collision free communications, SERENA should be aware about the set of interfering nodes. However, in case of topology changes, this set may vary. Consequently, SERENA should adapt to this. Our solutions proactively select one or more parent backups and guarantee that the coloring remains valid if a parent is replaced by its backup. Simulation results show that reliability is obtained at the price of a small increase in the number of colors used to color the network.