非同步脈衝耦合網路之廣義條件與實務考量

Desynchronization of Pulse Coupled Oscillators: Generalized Criteria and Practical Considerations

林依樺(Yi-Hua Lin)

指導教授 ： 洪樂文

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

摘要

此篇論文中，為了使一般無線感測網路(wireless sensor networks)中的使用者達到網路分時多工存取(Time Division Multiple Access)—本文稱為網路的非同步(desynchronization)，我們討論如何藉由設計使用者自身脈衝耦合振盪器(pulse coupled oscillator)達到分散式網路分時多工存取。在分時多工存取網路中，每個使用者週期性的在不同時間點傳送脈衝，利用自己與下一個使用者的脈衝時間差傳送訊息。而在非同步脈衝耦合網路，網路中每個使用者以相同週期的週期性傳送脈衝；藉由使用者觀察到自己以外的使用者傳送脈衝時，他會調整自己的內部時鐘去延遲或提早下一次的脈衝傳送時間讓使用者自發性調整而達到非同步網路。
在Pagliari等作者的一篇研究中，他們考慮一個特定的脈衝耦合振盪器調整機制並首先提出了針對脈衝耦合振盪器調整機制上的廣義條件使網路使用者達到弱非同步(weak desynchronization)。在本篇論文中，針對脈衝耦合振盪器調整機制，我們使用了相同的概念去討論如何設計可以使網路中的使用者達到弱非同步。
在兩使用者網路中，我們證明了當脈衝耦合振盪器調整機制是嚴格遞減且無上限的凸函數(Convex function)，網路中的使用者最後會達到弱非同步。在多使用者網路中，因為針對脈衝耦合振盪器的調整機制的廣義條件很難用簡單的數學式證明，我們在電腦模擬中展示在不同函數的廣義條件下(Pagliari等作者提出的特定機制也包含在內)最終還是可以達到網路上的弱非同步。
此外，我們考慮Pagliari等作者所使用的特定機制在網路中的弱非同步跟強非同步(strict desynchronization)下，當每個使用者有不同的傳送週期及動態網路人數情況下，討論其穩健性。在強非同步的案例中，我們也考慮了適應性的網路人數估計對於網路非同步的影響。

關鍵字

非同步 ； 脈衝耦合振盪器

並列摘要

Desynchronization of pulse coupled oscillators (PCO) has recently been proposed as a new primitive to achieve decentralized TDMA scheduling in wireless sensor networks (WSN). Specifically, this refers to the state where the network of PCOs pulse periodically but at orthogonal instants in time. Each node can utilize the duration of time after its own firing (and before the firing of another node) to transmit information. In a network of PCOs, each node emits a pulse periodically with the same period and adjusts its clock upon its hearing of other nodes' pulses. Extending upon the work by Pagliari et al, where specific PCO dynamics have been considered, this thesis first derives generalized criteria required on the PCO dynamics to achieve weak desynchronization. For a two node network, we show that it is sufficient to have the PCO dynamics be monotonically decreasing, convex, and unbounded at the origin. For networks with arbitrary number of nodes, the general criterion cannot be expressible in a simple form, but different dynamics can be found to satisfy this criterion, including those considered by Pagliari et al. The desynchronization of PCOs with dynamics that satisfy the generalized criteria are shown through computer simulations. Furthermore, to investigate the robustness of both the weak and strict desynchronization schemes proposed by Pagliari et al, experiments are performed on networks of PCOs with heterogeneous clock drifts and non-ideal dynamics. An adaptive node estimation scheme is also examined for the strict desynchronization case.

並列關鍵字

Desynchronization ； Pulse Coupled Oscillators

參考文獻

[1] C. S. Peskin, Mathematical aspects of heart physiology. Courant Institute of Mathematical Sciences, New York University, 1975.

[2] R. E. Mirollo and S. H. Strogatz, "Synchronization of pulse-coupled biological oscilators," SIAM Journal on Applied Mathematics, vol. 50, pp. 1645-1662, 1990.

[3] Y.-W. Hong and A. Scaglione, "A scalable synchronization protocol for large scale sensor

networks and its applications," IEEE Journal on Selected Areas in Communications, vol. 23, pp. 1085-1099, 2005.

[4] G.Werner-Allen, G. Tewari, A. Patel, R. Nagpal, and M.Welsh, "Firefly-inspired sensor network synchronicity with realistic radio effects," in Proc. of The Third Intl Conf. on Embedded Networked Sensor Systems, 2005.