Anchored Desynchronization

錨定去同步

張書豪(Shu-Hao Chang)

指導教授 ： 張正尚

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2011年)

https://doi.org/10.6843/NTHU.2011.00452

摘要

Distributed algorithms based on pulse-coupled oscillators have been recently proposed in [5, 14] for achieving desynchronization of a system of identical nodes. Though these algorithms are shown to work properly by various computer simulations, they are still lack of rigorous theoretical proofs for both the convergence of the algorithms and the rates of convergence for these algorithms. On the other hand, all the nodes are not likely
to be identical in many practical applications. In particular, there might be a node that needs to interact with the “outside” world and thus may not have the freedom to adjust its local clock. Motivated by all these, in this paper we consider the desynchronization problem in a system where there exists an anchored node that never adjusts the phase of its oscillator. For such a system, we propose a generic anchored desynchronization algorithm that achieves ϵ-desynchrony (defined in [5]) in O(n2 ln(n ϵ )) rounds of firings. We also prove that our algorithm converges even for the generalized processor sharing
(GPS) scheme, where every node is assigned a weight and the amount of resource received by a node is proportional to its weight. Finally, when the information of the total number of nodes in the system is available to all the nodes, we propose a set of algorithms that achieve perfect desynchrony in 3n − 4 rounds of firings. In comparison with the original algorithm in [5], we show that the rate of convergence of the original algorithm in [5] is not always better than ours and it is only better in the asymptotic regime.

關鍵字

去同步 ； 無線感測網路 ； 通用處理器共享 ； 同步 ； 脈衝耦合震盪器

並列摘要

許多基於脈衝耦合震盪器之分散演算法近來被應用於達到具有相同節點系統之去同步化。雖然這些演算法皆由電腦模擬來說明工作可運行性，但仍缺乏嚴謹理論證明其收斂性質及收斂速率。另一方面，在許多實際應用上，系統裡的節點並非全部皆相同，特別是有一特殊節點必須和系統外溝通且可能無法調整本身時脈，如藍牙系統中的主節點、無線感測網路中的收集者節點…等。
本論文以此為動機，我們考慮一個具有單一不變相位震盪器節點的系統，而在此種系統上探討其去同步化問題。根據此類系統特性，我們提出了一項一般性錨定去同步化演算法。且由理論證明此種演算法可於 O(n^2 ln⁡n) 輪系統全數節點震盪周期內達到極小誤差去同步(ε-desynchrony)。
此外，我們亦將問題擴展於通用處理器共享設計上。此種設計是給定系統裡每一節點各一權重，而節點所分配到之資源會與本身權重成比例。同樣地我們也以相同系統特性，將演算法擴展於此類設計上，且證明其收斂性。
最後，如果系統內每個節點可獲知額外資訊，將有可能提升系統去同步化收斂速度。我們選定系統節點總數作為額外資訊，而基於相同的錨定去同步化特性提出演算法，進而提升系統去同步化收斂速度。此種演算法可於 3n-4 輪系統全數節點震盪周期內達到完美去同步。與參考文獻[5]中的原始演算法比較，我們展示了原始演算法並非永遠優於我們的錨定去同步演算法。

並列關鍵字

Desynchronization ； Wireless sensor network ； Generalized processor sharing ； Synchronization ； pulse-coupled oscillator

參考文獻

[2] S. Boyd, P. Diaconis, L. Xiao, “Fastest mixing markov chain on a graph,” SIAM Review, Vol. 46, No. 4, pp. 667-689, 2004.

[3] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,”IEEE Transactions on Information Theory, Vol. 52, No. 6, pp. 2508–2530, 2006.

[4] P. Diconis and D. Stroock, “Geometric bounds for eigenvalues of markov chains, The Annals of Applied Probability, Vo. 1, pp. 36–61, 1991.

[5] J. Degesys, I. Rose, A. Patel, and R. Nagpal, “Desync: Self-organizing desynchronization and TDMA on wireless sensor networks,” in International Conference on Information Processing in Sensor Networks (IPSN), 2007.

[6] J. Degesys, I. Rose, A. Patel, R. Nagpal, “Desynchronization: the theory of selforganizing algorithms for round-robin scheduling,” First International Conference on Self-Adaptive and Self-Organizing Systems, 2007. SASO ’07.