This research is motivated by some distributed scheduling problems in distributed sensor networks, in which computational and communication resources are scarce. We first cast these problems as distributed constraint ...
详细信息
This research is motivated by some distributed scheduling problems in distributed sensor networks, in which computational and communication resources are scarce. We first cast these problems as distributed constraint satisfaction problems (DisCSPs) and distributed constraint optimization problems (DisCOPs) and model them as distributed graph coloring. To cope with limited resources and restricted real-time requirement, it is imperative to use distributedalgorithms that have low overhead on resource consumption and high-quality anytime performance. To meet these requirements, we study two existing DisCSP algorithms, distributed stochastic search algorithm (DSA) and distributed breakout algorithm (DBA), for solving DisCOPs and the distributed scheduling problems. We experimentally show that DSA has a phase-transition or threshold behavior, in that its solution quality degenerates abruptly and dramatically when the degree of parallel executions of distributed agents increases beyond some critical value. We also consider the completeness and complexity of DBA for distributed graph coloring. We show that DBA is complete on coloring acyclic graphs, coloring an acyclic graph of n nodes in O(n(2)) steps. However, on a cyclic graph, DBA may never terminate. To improve DBA's performance on coloring cyclic graphs, we propose two stochastic variations. Finally, we directly compare DSA and DBA for solving distributed graph coloring and distributed scheduling problems in sensor networks. The results show that DSA is superior to DBA when controlled properly, having better or competitive solution quality and significantly lower communication cost than DBA. Therefore, DSA is the algorithm of choice for our distributed scheduling problems and other distributed problems of similar properties. (C) 2004 Elsevier B.V. All rights reserved.
暂无评论