Distributed Algorithms for TDMA Link Scheduling in Sensor Networks

Abstract

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 bi-directed graphs and prove tighter lower and upper bounds for the FDLSP problem. We formulate the FDLSP problem as an integer linear program (ILP).  Then, we present two Δ-approximation distributed algorithms for growth bounded graphs (GBG), for modeling the sensor networks, and for general graphs, Δ being the maximum node degree  in the network.  The first algorithm is a synchronous $\Delta$-approximation algorithm based on finding maximal independent sets. The second is an asynchronous Δ-approximation depth first search (DFS) based algorithm. The maximal independent set based algorithm requires only O(Δ log^*n) communication rounds (where n is the number of processors in the network) in growth bounded graphs. For general graphs, the maximal independent set based algorithm requires O(Δ⁴+Δ³log^*n) communication rounds,  improving upon the previous best known 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.