Performance Evaluation of Distributed Synchronous Greedy Graph Coloring Algorithms on Wireless Ad Hoc and Sensor Networks

Graph coloring is a widely used technique for allocation of time and frequency slots to nodes, for formingclusters, for constructing independent sets and dominating sets on wireless ad hoc and sensor networks. Agood coloring approach should produce low color count as possible. Besides, since the nodes of a wirelessad hoc and sensor network operate with limited bandwidth, energy and computing resources, the coloringshould be computed with few message passing and computational steps. In this paper, we provide aperformance evaluation of distributed synchronous greedy graph coloring algorithms on ad hoc and sensornetworks. We provide both theoretical and practical evaluations of distributed largest first and thedistributed version of Brelaz’s algorithm. We showed that although distributed version of Brelaz’salgorithm produces less color count, its resource consumption is worse than distributed largest firstalgorithm.