DocumentCode :
62943
Title :
Game-Theoretic Approach to Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Sets
Author :
Li-Hsing Yen ; Zong-Long Chen
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Univ. of Kaohsiung, Kaohsiung, Taiwan
Volume :
25
Issue :
12
fYear :
2014
fDate :
Dec. 2014
Firstpage :
3201
Lastpage :
3210
Abstract :
Dominating set is a subset of nodes called dominators in a graph such that every non-dominator nodes (called dominatee) is adjacent to at least one dominator. This paper considers a more general multi-dominating problem where each node i, dominator or dominatee, is required to have at least ki neighboring dominators, and different node can have different ki value. We first propose a game design toward this problem. This game is self-stabilizing (i.e., it always ends up with a legitimate state regardless of its initial configuration). The obtained result is guaranteed minimal (i.e., it contains no proper subset that is also a multi-dominating set) and Pareto optimal (we cannot increase the payoff of some player without sacrificing the payoff of any other). We then point out challenges when turning the design into a distributed algorithm using guarded commands. We present an algorithm that is proved weakly stabilizing. Simulation results show that the proposed game and algorithm produce smaller dominating sets, k-dominating sets, and multi-dominating sets in various network topologies when compared with prior approaches.
Keywords :
Pareto optimisation; distributed algorithms; game theory; graph theory; set theory; Pareto optimal; distributed algorithm; dominatee; game-theoretic approach; general multidominating problem; graph theory; guarded commands; k-dominating sets; least-neighboring dominators; legitimate state; minimal multidominating sets; network topologies; node subset; nondominator nodes; player payoff; self-stabilizing distributed formation; self-stabilizing game design; weakly-stabilizing algorithm; Algorithm design and analysis; Distributed algorithms; Games; Nash equilibrium; Network topology; Pareto optimization; Silicon; Dominating set; distributed algorithm; game theory; self-stabilization;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/TPDS.2013.2297100
Filename :
6714459
Link To Document :
بازگشت