Towards desynchronization of multi-hop topologies

In this paper we study desynchronization, a closely-related primitive to graph coloring. A valid graph coloring is an assignment of colors to nodes such that no node's color is the same as a neighbor's. A desynchronized configuration is an assignment of real values in S¹ to nodes such that each node's value is exactly at the midpoint of two of its closest neighbors' values. Recent work has shown that a simple, self-organizing algorithm, DESYNC, can solve desynchronization in single-hop networks, with applications to collision-free wireless broadcast [1] and duty-cycling [2]. Here we generalize this work by defining and analyzing desynchronization for multi-hop networks and experimentally analyzing the DESYNC algorithm's behavior for multi-hop networks. We describe desynchronized configurations for several classes of graphs (lines, rings, two-colorable, and hamiltonian cycles) and discuss the relationship with other variants of graph coloring. We extend the DESYNC algorithm and DESYNC-based resource allocation to multi-hop networks and study the performance and efficiency of resource allocation in simulation. While many applications for graph coloring require synchronization and an agreement on a schedule to be effective, we show that the self-organizing algorithm, DESYNC, does not require either of these to achieve desynchronization and to define a resource-allocation schedule. Although applications to wireless sensor networks pose some unique problems, the results suggest that DESYNC has significant potential as a lightweight method for providing non-overlapping variable-sized slots in ad-hoc multi-hop settings.