以賽局理論設計MANET最大獨立集合自我穩定協定

A Game-theoretic Approach to Self-Stabilizing Maximal Independent Set Protocol in MANETs

圖論中的最大獨立集合（maximal independent set）問題是從一個無向圖G中的節點集合V挑選部分的節點集合S，需滿足在S當中不存在任何兩節點相鄰且S不為其它任一獨立集合的子集合。本篇論文透過賽局理論（game theory）尋求較佳的最大獨立集合問題解。我們接著將賽局設計轉換為在分散式系統中運作的自我穩定演算法。自我穩定（self-stabilization）的性質可以保證不論系統初始狀態為何，必定會在有限的時間內到達穩定的合法狀態，即最大獨立集合。為了使我們提出的方法能在MANET中有效的實作，需另外再對演算法進行修改以克服環境上的差異。模擬實驗結果顯示我們提出的演算法有較好的效能表現，比先前的方法有較多的最大獨立集合節點數以及較短的收斂時間。

Given an undirected graph G = (V, E), S ⊆ V is an independent set if no nodes in S are adjacent to one another. An independent set S is maximal if no proper subset of S is an independent set. Maximal independent set problem is to find such a set S. This paper proposes a solution to this problem based on game theory. We turn the solution into a self-stabilizing algorithm running in distributed systems. The self-stability property ensures that system will enter legitimate system states in limited time regardless of initial configurations. We then convert the algorithm into a protocol that runs under MANET environment. Simulation results indicate that the proposed protocol performs better than previous work in terms of independent set size and convergence time.