2005/08/24 by Shashidhar Gandham, Milind Dawande, Ravi Prakash · 1 citation
Computer Science · Engineering · Mathematics · #Energy Efficient Wireless Sensor Networks #Mobile Ad Hoc Networks #Energy Harvesting in Wireless Networks #Time division multiple access #Computer science #Network topology #Scheduling (production processes) #Wireless sensor network #Graph coloring #Enhanced Data Rates for GSM Evolution #Transmission (telecommunications) #Computer network #Topology (electrical circuits) #Algorithm #Graph #Mathematics #Theoretical computer science #Combinatorics #Mathematical optimization #Artificial intelligence #Telecommunications
paper · doi:10.1109/infcom.2005.1498534
openalex publication_date 2005/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our link scheduling algorithm involves two phases. In the first phase, we assign a color to each edge in the network such that no two edges incident on the same node are assigned the same color. We propose a distributed edge coloring algorithm that needs at most (/spl delta/+1) colors, where /spl delta/ is the maximum degree of the graph. To the best of our knowledge, this is the first distributed algorithm that can edge color a graph with at most (/spl delta/+1) colors. In the second phase, we map each color to a unique timeslot and attempt to identify a direction of transmission along each edge such that the hidden terminal and the exposed terminal problems are avoided. Next, considering topologies for which a feasible solution does not exist, we obtain a direction of transmission for each edge using additional timeslots, if necessary. 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 neighbors. For acyclic topologies, we show that at most 2(/spl delta/+1) timeslots are required. Through simulations we show that for sparse graphs with cycles the number of timeslots assigned is close to 2(/spl delta/+1).