Distributed Algorithms for TDMA Link Scheduling in Sensor Networks

The paper is devoted to Time Division Multiple Access Link Scheduling Protocols in wireless sensor networks for full duplex (two-way) communication, where each sensor is scheduled on an incident link as a transmitter and as a receiver in two different time slots. We formulate the full duplex link scheduling problem (FDLSP) as distance-2 edge coloring in bidirected graphs. We proves that there exists a Δ-approximation algorithm for FDLSP (Δ being the maximum node degree in the network). Then, we present two distributed algorithms. The first is a synchronous algorithm based on finding maximal independent sets. The second is an asynchronous depth first search (DFS) algorithm. The maximal independent set based algorithm requires only O(Δlog*n) communication rounds (where n is the number of processors in the network) for growth bounded graphs, which is a realistic geometric model of sensor networks. For general graphs, the maximal independent set based algorithm requires O(Δ⁴ + Δ³log*n) communication rounds, improving upon the previous best algorithm with O(nΔ² +n²m) communication rounds (where m is the number of links in the network). The asynchronous DFS based algorithm requires only O(n) communication rounds for both general and growth bounded graphs. The simulations show that the proposed algorithms assign on average equal or fewer number of time slots compared to the best known distributed algorithm while being significantly faster.