黃寶儀臺灣大學：電機工程學研究所邱奕霖Chiu, Yi-LinYi-LinChiu2007-11-262018-07-062007-11-262018-07-062006http://ntur.lib.ntu.edu.tw//handle/246246/53582感測網路上的應用程式需要把節點調整到同一相位以方便做通訊排程與調整工作週期 。從螢火蟲在同一時間發光中得到啟發，米羅與史托蓋首先用理論模型來模擬螢火蟲在同時間閃爍的現象，同時，在全部的節點都能互相溝通與沒有訊息的延遲與遺失的假設前提之下，他們的理論可以保證將各節點的相位收斂到同步。 然而，這兩個假設前提也使的他們的理論無法應用在實際狀況上，也就是說，並不是每個節點都能互相溝通且碰撞會造成訊息的遺失。 喬佛瑞等人提出了RFA演算法來解決訊息延遲的問題。然而，在每個節點同步之後所送出的訊息封包會因為同時使用頻道而造成碰撞，進一步使封包與其內容遺失。在本篇論文中，我們提出了隨機發射演算法(RandFA)來解決上述碰撞的問題。 隨機發射演算法以及上述兩個演算法都實做在MSP430平台上來比較其效能。我們的結果顯示隨機發射演算法有非常低的機率造成封包碰撞，而且節點也非常迅速的調整到相位同步。Sensor network applications require nodes adjusted to the same phase to do communication scheduling, and to coordinate duty cycles. Inspired by the fireflies, which emit light in perfect synchrony, Mirollo and Strogatz first gave a theoretical model to model the firefly synchronicity phenomenon and prove its synchronization under two assumptions: 1. All-to-all topology and 2. No message delay or loss. Both of them make the theory impractical to real world applications i.e. all-to-all connection is not easily available and packets will lose due to congestion). Geoffrey et al proposed the RFA (Reachback Firefly Algorithm) to compensate for the message delay problem. In the RFA, when nodes are under synchronicity, they will fire synchronizaing packets at the same time, and as a result, causes the synchronizing packets to collide. In this thesis, we propose a randomized algorithm, referred to as RandFA, to eliminate the collision problem. RandFA and the state of art algorithms are implemented on the MSP430 platform for comparision. Our results show that RandFA experiences virtually zero packet loss, and the sensor node phases converge significantly faster to synchrony.Abstract i 1 INTRODUCTION 1 2 RELATED WORK 6 2.1 Firefly Synchronization ..................... 6 2.2 Time Synchronization ........................ 7 3 ALGORITHMS 9 3.1 Notation .....................................9 3.2 Firing Function .............................10 3.3 General Concept ............................ 11 3.4 MS ..........................................13 3.5 RFA ........................................ 14 3.6 RandFA ......................................16 4 SOURCE OF ERRORS 20 5 IMPLEMENTATION 23 6 EVALUATION 30 6.1 Hardware Infrastructure .....................30 6.2 Topology Design and Reference Clock .........31 6.2.1 Problem Description ....................31 6.2.2 Experiment Setup .......................32 6.2.3 From Theory to Practice ................33 6.3 Experiment Result and Analysis ..............33 6.3.1 MS .................................... 34 6.3.2 RFA ....................................36 6.3.3 RandFA..................................37 6.4 Summary .....................................38 7 CONCLUSION 40537016 bytesapplication/pdfen-US相位同步感測網路隨機發射演算法phasesynchronizationsensor networkRandFA[SDGs]SDG11thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53582/1/ntu-95-R93921100-1.pdf