A self-stabilizing distributed algorithm for the multicoloring problem in dynamic networks
スポンサーリンク
概要
- 論文の詳細を見る
The problem of channel (frequency) assignment is an important problem in wireless networks such as cellular networks and wireless LANs. In this paper, we consider a problem of multiple channel assignment to each node in a wireless network, and we formalize this problem as the multicoloring problem of a graph; each node is assigned a set of colors and no two neighbor nodes share the same color. We propose a self-stabilizing distributed algorithm for the multicoloring problem. By the self-stabilizing property, our algorithm is adaptive to topology changes, it tolerates any kind and any finite number of transient faults, and it does not require global reset to recompute multicoloring. Additionally, our algorithm has several desirable properties for dynamic distributed systems.
- 一般社団法人情報処理学会の論文
- 2010-02-25
著者
-
Yukiko Yamauchi
Graduate School of Information Science, Nara Institute of Science and Technology
-
Yamauchi Yukiko
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Yukiko Yamauchi
Graduate School Of Information Science Nara Institute Of Science And Technology Japan
-
Yukiko Yamauchi
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Hirotsugu Kakugawa
Graduate School of Information Science and Technology, Osaka University
-
Hirotsugu Kakugawa
Graduate School Of Information Science And Technology Osaka University Japan
関連論文
- Probabilistic Methods for Spatio-Temporal Coverage in People-Centric Sensing
- Loosely-stabilizing Leader Election in Population Protocol Model
- Node Selection Methods for Probabilistic Coverage in People-Centric Sensing
- Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
- Rendezvous of Asynchronous Mobile Agents in Trees
- A self-stabilizing distributed algorithm for the multicoloring problem in dynamic networks
- Probabilistic Coverage Methods in People-Centric Sensing
- On Space Complexity of Self-Stabilizing Leader Election in Population Protocol Based on Three-interaction