A Graph Coloring Based TDMA Scheduling Algorithm for Wireless Sensor Networks

作者：Kang Hui; Zhao Ya nan; Mei Fang^*

来源：Wireless Personal Communications, 2013, 72(2): 1005-1022.

DOI：10.1007/s11277-013-1052-9

• TDMA
• Distributed
• Graph coloring
• Clustering
• Real-time

Wireless sensor networks should provide with valuable service, which is called service-oriented requirement. To meet this need, a novel distributed graph coloring based time division multiple access scheduling algorithm (GCSA), considering real-time performance for clustering-based sensor network, is proposed in this paper, to determine the smallest length of conflict-free assignment of timeslots for intra-cluster transmissions. GCSA involves two phases. In coloring phase, networks are modeled using graph theory, and a distributed vertex coloring algorithm, which is a distance-2 coloring algorithm and can get colors near to , is proposed to assign a color to each node in the network. Then, in scheduling phase, each independent set is mapped to a unique timeslot according to the set's priority which is obtained by considering network structure. The experimental results indicate that GCSA can significantly decrease intra-cluster delay and increase intra-cluster throughput, which satisfies real-time performance as well as communication reliability.

• 出版日期2013-9
• 单位吉林大学