Link scheduling in wireless sensor networks: Distributed edge-coloring revisited

We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our algorithm consists of two phases. The first phase involves edge-coloring: an assignment of a color to each edge in the network such that no two edges incident on the same node are assigned the same color. our main result for the first phase is a distributed edge-coloring algorithm that needs at most (Delta + 1) colors, where Delta is the maximum degree of the network. To our knowledge, this is the first distributed algorithm that can edge-color a graph using at most (Delta + 1) colors. The second phase uses the edge-coloring solution for link scheduling. We map each color to a unique timeslot and attempt to assign a direction of transmission along each edge such that the hidden terminal problem is avoided; an important result we obtain is a characterization of network topologies for which such an assignment exists. Next, we consider topologies for which a feasible transmission assignment does not exist for all edges, and obtain such an assignment using additional timeslots. Finally, we show that reversing the direction of transmission along every edge leads to another feasible direction of transmission. Using both the transmission assignments, we obtain a TDMA MAC schedule which enables two-way communication between every pair of adjacent sensor nodes. For acyclic topologies, we prove that at most 2(Delta + 1) timeslots are required. Results for general topologies are demonstrated using simulations; for sparse graphs, we show that the number of timeslots required is around 2(Delta + 1). We show that the message and time complexity of our algorithm is 0(n Delta(2) + n(2)m), where n is the number of nodes and m is the number of edges in the network. Through simulations, we demonstrate that the energy consumption of our solution increases linearly with Delta. We also propose extensions to account for non-ideal radio characteristics. (C) 2008 Elsevier Inc. All rights reserved.