基于振蕩器模型的多跳無線傳感器網(wǎng)絡(luò)時間同步問題研究-論文

1、項目名稱 基 于 振 蕩 器 模 型 的 多 跳 無 線 傳 感 器 網(wǎng) 絡(luò) 時 間 同 步 問 題 研 究項目負責人（簽名）_所在學校（蓋章）_“研究類別”含義： 基礎(chǔ)研究：指為獲得關(guān)于現(xiàn)象和可觀察事實的基本原理及新知識而進行的實驗性和理論性工作，它不以任何專門或特定的應用或使用為目的。 應用研究：指為獲得新知識而進行的創(chuàng)造性的研究，它主要是針對某一特定的實際目的或目標。 試驗發(fā)展：指利用從科學研究和實際經(jīng)驗中所獲得的現(xiàn)有知識、生產(chǎn)新材料、新產(chǎn)品、新裝置、新流程和新方法，或?qū)ΜF(xiàn)有的材料、產(chǎn)品、裝置、流程、方法進行本質(zhì)性的改進而進行的系統(tǒng)性工作。 推廣應用、科技服務：指與研究與發(fā)展活動相關(guān)并有

2、助于科學技術(shù)知識的產(chǎn)生、傳播和應用的活動。研究項目項目名稱基于振蕩器模型的多跳無線傳感器網(wǎng)絡(luò)時間同步問題研究研究類別1.基礎(chǔ)研究 2.應用研究 3.試驗發(fā)展 4.推廣應用 5.科技服務依托的一級學科 計算機科學技術(shù)成果形式專利、論文起止時間 2014 年 5 月到 2016 年 4 月經(jīng)費申請總額 1 萬元其他經(jīng)費及其來源無項目負責人姓 名職 稱工作單位電子郵箱項除目負組責主人要外成五員名姓名職稱學位專業(yè)工作單位承擔任務本人簽名項目負責人近三年來承擔的研究項目項目名稱項目來源起止年月排名進展基于普適計算的物聯(lián)網(wǎng)中間件的研究學科帶頭人學術(shù)攀登項目2013年9月-2016年6月3在研海運集裝箱碼頭

3、調(diào)度方法的研究?？蒲谢?009年5月-2011年4月1結(jié)題程序設(shè)計類課程游戲化教學的深度實踐-以數(shù)據(jù)結(jié)構(gòu)課程為例校教改課題2013年12月-2015年12月1在研大宗商品供應鏈企業(yè)間知識共享博弈研究校科研基金2013年7月-2015年6月1在研一種無信標結(jié)點無線傳感器網(wǎng)絡(luò)定位算法研究寧波市自然科學基金2013年8月-2015年6月4在研基于PKI的Zigbee網(wǎng)絡(luò)安全方案研究寧波市自然科學基金2013年7月-2015年4月4在研項目負責人為第一署名人的代表性成果成果名稱成果來源獲得時間排名等級基于耦合振蕩器模型的WSN時間同步算法-以ZigBee網(wǎng)絡(luò)以例論文2014年4月1鼓勵獎Resear

4、ch on Application of Linkage Learning Mechanism of "Player-Learner" 論文2014年4月1鼓勵獎Application on the partner selection of the concrete enterprise based on GAAA論文2012年4月1鼓勵獎1 本項目研究意義及國內(nèi)外同類研究工作現(xiàn)狀（附主要參考文獻及出處）：研究意義： 無線傳感器網(wǎng)絡(luò)是聯(lián)系物理世界和計算機系統(tǒng)的橋梁，對物理世界的觀測必須建立在統(tǒng)一的時間標度上，因此相對與通常的分布式系統(tǒng)，無線傳感器網(wǎng)絡(luò)對時間同步的需求尤為強烈

5、，可以說時間同步是無線傳感器網(wǎng)絡(luò)的一項支撐技術(shù)。其在無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)融合、MAC協(xié)議、測距定位等研究領(lǐng)域有著非常重要的應用。 2002年8月，Jeremy Elson和Kay Römer提出和闡述無線傳感器網(wǎng)絡(luò)時間同步的研究課題后1。不斷有新的時間同步協(xié)議被提出。這些時間同步協(xié)議基于節(jié)點間的包含時間信息的報文交換，力圖提高時戳信息的準確性來提高時間同步的精度；力圖利用無線廣播特性來降低同步功耗。目前，單跳無線傳感器網(wǎng)絡(luò)的時間同步協(xié)議已經(jīng)很成熟，同步誤差在Mica2平臺上已經(jīng)達到幾到十幾微秒的量級，同步功耗也較低，能夠滿足大多數(shù)應用場合的需要。然而，當這些時間同步協(xié)議被擴展到多跳網(wǎng)

6、絡(luò)時，經(jīng)典的無線傳感器網(wǎng)絡(luò)時間同步算法通常是首先按照節(jié)點之間的通信連接關(guān)系建立起一定的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，在該拓撲結(jié)構(gòu)上，按照時間同步協(xié)議的約定，未同步節(jié)點和所選定的已同步節(jié)點之間通過交換含時間信息的同步報文，從而間接地實現(xiàn)與時間基準節(jié)點之間的同步。這種同步機制的特點在于：除時間基準節(jié)點的鄰居節(jié)點外，其余點并不能直接和時間基準節(jié)點同步。傳統(tǒng)時間同步協(xié)議在體系結(jié)構(gòu)上的限制：節(jié)點不能直接和時間基準節(jié)點同步而只能和與時間基準節(jié)點存在同步誤差的節(jié)點進行同步，因此必將出現(xiàn)節(jié)點的同步誤差隨著其離時間基準節(jié)點跳距(Hop Distance)的增加而增加的現(xiàn)象，即出現(xiàn)了同步誤差的累積。理論分析和一些實際實驗表明：在

7、這些傳統(tǒng)的時間同步協(xié)議下，即使在最好的情況下，節(jié)點的同步誤差至少與其跳距的平方根成正2。隨著無線傳感器網(wǎng)絡(luò)的發(fā)展，同步誤差累積問題將越來越嚴重。一方面由于傳感器節(jié)點體積的不斷減小使得節(jié)點的單跳傳播距離可能減小，另一方面由于網(wǎng)絡(luò)規(guī)模的不斷擴大使得網(wǎng)絡(luò)直徑不斷增加，這兩個因素均會導致平均節(jié)點跳距的增加，使得同步誤差的累積現(xiàn)象更加嚴重。這對大規(guī)模無線傳感器網(wǎng)絡(luò)的應用提出了挑戰(zhàn)3。傳統(tǒng)無線傳感器網(wǎng)絡(luò)時間同步協(xié)議還面臨著可擴展性問題的挑戰(zhàn)。它力圖建立起網(wǎng)絡(luò)拓撲結(jié)構(gòu)從而把網(wǎng)絡(luò)中的所有節(jié)點有機組織起來，當網(wǎng)絡(luò)規(guī)模較小時，這是完全可行的，但當網(wǎng)絡(luò)規(guī)模較大時，由于無線傳輸?shù)牟环€(wěn)定性以及節(jié)點工作的動態(tài)性，只有頻繁

8、地進行拓撲更新才能跟蹤拓撲的變化，一方面這對于本已非常有限的網(wǎng)絡(luò)帶寬和節(jié)點電能供應來說是不可想象的，另一方面把網(wǎng)絡(luò)拓撲維護的繁重工作交給時間同步協(xié)議來解決也并不合適。由于存在的上述問題，近些年來，研究者們開始尋找新的時間同步的思路和方法。而借鑒了螢火蟲、心肌細胞等生物同步現(xiàn)象的基于線性振蕩器模型的無線傳感器網(wǎng)絡(luò)時間同步方法逐漸引起了研究者們的注意。這種方法采用完全分布式的形式，節(jié)點之間僅通過簡單的脈沖進行耦合，因此具有較高的健壯性和可擴展性?？梢灶A見，該方法的研究將把無線傳感器網(wǎng)絡(luò)時間同步推入一個新的研究階段。然而，傳統(tǒng)的線性振蕩器模型并不能直接應用在無線傳感器網(wǎng)絡(luò)中。例如，傳統(tǒng)的線性振蕩器模

9、型假設(shè)不存在傳輸和處理延遲，這顯然在無線傳感器網(wǎng)絡(luò)中是不現(xiàn)實的；再如，傳統(tǒng)的線性振蕩器模型假設(shè)任何節(jié)點間都存在著一定程度的耦合，而在多跳的無線傳感網(wǎng)絡(luò)中，這也是不現(xiàn)實的。本項目在無線傳感器網(wǎng)絡(luò)的背景下，旨在解決延遲、多跳拓撲因素對線性振蕩器模型所帶來的關(guān)鍵理論挑戰(zhàn)，以及相關(guān)的工程實現(xiàn)問題，推進線性振蕩器模型在無線傳感器網(wǎng)絡(luò)中的實際應用，并為最終解決大規(guī)模無線傳感器網(wǎng)絡(luò)的時間同步問題打下堅實的理論和工程基礎(chǔ)。通過本項目的實施，首先，可以從理論上解決線性振蕩器模型在無線傳感器網(wǎng)絡(luò)時間同步應用上的理論缺陷問題，并為生物、物理等領(lǐng)域的同步問題的研究提供有益的理論借鑒；其次，項目研究中建立的仿真模型和實

10、驗平臺，可以為同領(lǐng)域在其他方向的研究提供有力的支持；最后，研制基于線性振蕩器模型的輕量級無線傳感器網(wǎng)絡(luò)時間同步硬件設(shè)備，可以直接推進本項目研究成果的實用化。國內(nèi)外同類研究工作現(xiàn)狀：1、經(jīng)典無線傳感器網(wǎng)絡(luò)時間同步算法 對于無線傳感器網(wǎng)絡(luò)時間同步的研究已經(jīng)開展，研究者們提出了許多方法對該問題進行求解，這主要包括DMTS4，TPSN5，LTS6，RBS，F(xiàn)TSP7。等。下面對這些方法做簡要的介紹。 無線網(wǎng)絡(luò)同步最易于想到的方法為：發(fā)送者在同步報文中嵌入其本地時間，在接收到該報文后，接收者立即把自己的本地時間設(shè)置為嵌在該報文中的時間。但這種方法沒有考慮到報文的傳輸延遲。而DMTS（Delay Meas

11、urement Time Synchronization）協(xié)議在此方法的基礎(chǔ)上，進一步考慮了報文的傳輸延遲，接收者測量報文的傳輸延遲，并將本地時間設(shè)置為報文傳輸延遲與發(fā)送時刻之和。DMTS同步協(xié)議沒有考慮傳播延遲、編解碼時間的影響，并且沒有對時鐘飄移進行補償，同步精度不高。但通過單個的廣播報文，一次就可以同步廣播域內(nèi)的所有節(jié)點，并且計算非常簡單，是一種非常簡單有效的同步協(xié)議。 DMTS同步協(xié)議簡單，但同步精度不高，UCLA的NESL實驗室的S.Ganeriwal認為：傳統(tǒng)的發(fā)送者-接收者同步協(xié)議的同步精度較低的根源在于：基于單向報文所估算出的報文傳播延遲不夠精確。如果采用雙向報文，基于報文傳輸

12、的對稱性，有可能精確地計算出報文的傳輸延遲，因此能獲得高的同步精度。為此，他引入了NTP協(xié)議中的雙向報文交換協(xié)議，提出了TPSN（Timing-sync Protocol for Sensor Networks）協(xié)議。TPSN將NTP時間同步方法引入無線傳感器網(wǎng)絡(luò)，相對DMTS獲得了較高的精度，但是其計算較為復雜，功耗較大。并且同步精度受到報文的傳輸延遲的影響，同時如果報文的雙向傳輸不對稱，同步精度也會受到影響。 LTS（Lightweight Tree-based Synchronization）同步算法是一種與TPSN非常類似的算法。無線傳感器網(wǎng)絡(luò)通常只具有非常有限的計算資源，但是其并不要

13、求非常高的時間同步精度。針對無線傳感器網(wǎng)絡(luò)的這一特點，LTS側(cè)重于降低時間同步的復雜度，在有限的計算代價下獲得合理的同步精度。LTS算法與TPSN協(xié)議的區(qū)別在于，LTS算法中節(jié)點只與自己的父節(jié)點進行同步，其同步次數(shù)是路徑長度的線性函數(shù)，同時精度也隨路徑的長度線性降低，即在降低計算代價的同時降低了同步精度。 無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳播介質(zhì)是無線信道，能否利用無線信道的廣播特性設(shè)計相關(guān)的時間同步算法呢？RBS（Reference Broadcast Synchronization）算法就是利用無線信道廣播特性進行同步的算法。與TPSN協(xié)議不同，RBS協(xié)議不是去同步報文的收發(fā)雙方，而是去同步報文的多個

14、接收者，也即接收者-接收者同步機制。RBS算法認為：發(fā)送者-接收者同步機制的同步關(guān)鍵路徑為從發(fā)送方到接收方。關(guān)鍵路徑過長，導致傳輸延遲不確定性的增加，因此同步精度不可能很高。接收者-接收者同步機制的關(guān)鍵路徑大為縮短，完全排除了發(fā)送時間和訪問時間的影響。實驗表明，RBS在Mica2上達到了31.7微秒的同步精度。 作為典型的發(fā)送者-接收者同步算法，TPSN認為：若能精確地估計出報文傳輸延遲，這種方法將能夠取得很高的精度。然而僅根據(jù)單個報文的傳輸很難準確地估計出傳輸延遲，因此，TPSN采用了雙向報文來估計傳輸延遲，在Mica2上達到了17.3微秒的同步精度。 FTSP（Flooding Time

15、Synchronization Protocol）屬于發(fā)送者-接收者協(xié)議，因此發(fā)送者基于MAC層時間戳技術(shù)在報文中嵌入發(fā)送時刻，而接收者也在MAC層記錄下接收時刻。和其它發(fā)送者-接收者同步協(xié)議不同，在FTSP協(xié)議中，發(fā)送者在發(fā)送一個報文時連續(xù)標記了多個時間戳。根據(jù)這多個時間戳，接收者可以估計出中斷等待時間。接收者根據(jù)估計出的中斷等待時間信息以及靜態(tài)設(shè)定的編解碼時間對接收時間戳進行補償，從而得到更精確的同步點。如同RBS協(xié)議一樣，F(xiàn)TSP協(xié)議基于速率恒定模型對節(jié)點間時鐘飄移進行了補償，補償方法仍然采用了最小二乘法。FTSP協(xié)議具有同步精度高，協(xié)議非常健壯，工程實用性很強等優(yōu)點。 國內(nèi)研究者對時間

16、同步算法也進行了深入的研究。包括： 王汝傳等8對RBS算法進行了改進，提出了一種改進的時間同步算法IRBS(Improved References Broadcast Synchronization)。該方法對每個接收節(jié)點的時間值利用最小平方線性回歸方法進行估計，分析出同一節(jié)點的系統(tǒng)時鐘誤差并進行補償。通過仿真表明該方法算法能夠縮小時間誤差，有效提高時間同步的精度。劉海濤等9提出將擴散機制引入FTSP算法，提出了一種基于擴散機制的無線傳感器網(wǎng)絡(luò)時間同步協(xié)議DTSP。該協(xié)議同時利用了容錯、時分等策略，在保證同步精度前提下提高了協(xié)議的健壯性。 徐朝農(nóng)等10針對TPSN的非同步期內(nèi)由于節(jié)點間存在時鐘

17、飄移所造成的失步情況，提出在非同步期內(nèi)對時鐘飄移進行估計和補償。即估算出了直接相鄰節(jié)點間的晶振頻率偏差，然后通過迭代公式計算得到與時間基準節(jié)點間的晶振頻率偏差，并進行補償。應用此方法可設(shè)計的高精度、強可擴展性、低能耗的時間同步協(xié)議。實驗表明，單跳平均同步誤差在Mica2上小于10微秒。 王福豹等11-13提出一種嵌入路由報頭的低功耗時間同步算法，該算法將時間同步集成到消息的路由報頭中，通過在發(fā)送和接收端在路由消息上加蓋精確的時間戳實現(xiàn)同步，從而消除了周期性時間同步消息的傳輸,減小了能量開銷。 近些年提出的算法還包括，皇甫偉14等的網(wǎng)時間同步算法FTS，吳成偉等15的比對廣播時間同步算法PBTS

18、，周新蓮等16的基于簇型的多跳時間同步算法CBTS，齊望東等17的輕量級安全時間同步協(xié)議LiteST，屈玉貴等18的能量高效的時間同步算法EETS。2、基于耦合振蕩器同步模型如前文所述，無線傳感器網(wǎng)絡(luò)經(jīng)典時間同步算法，無法應對同步誤差累積和可擴展性的問題。近些年來，研究者們開始尋找新的時間同步的思路和方法。而螢火蟲同步這一古老的生物同步現(xiàn)象逐漸又被大家重視起來。互相臨近的螢火蟲能夠調(diào)整為同步閃爍，這是一種非常奇妙的生物現(xiàn)象。早在上世紀初，很多學者就在Science上發(fā)文，對此現(xiàn)象進行了討論。Smith 1935年的文章19對東南亞的螢火蟲同步閃爍現(xiàn)象進行了生動詳細的描述，文中描述了在泰國的湄公

19、河延綿十幾英里的河岸邊的樹上，幾乎每篇樹葉上都棲息著近乎完美同步閃爍的螢火蟲。這一現(xiàn)象引起了學者們的廣泛關(guān)注，科學家們紛紛對此展開研究。早在1915年Blair就觀察到了這一現(xiàn)象并試圖對這一現(xiàn)象進行解釋20，他把螢火蟲類比為充電電池每次閃爍暫時性的將電池的電能耗光，而電池經(jīng)過一段時間的充電之后又可以進行下一次的閃爍。同時，每次閃爍都會對其它電池的放電產(chǎn)生影響，最終使得所有的螢火蟲同步的閃爍。Richmond提出了類似的假設(shè)，如果某個螢火蟲將要閃爍的時候看到了其他螢火蟲的閃爍，它將會提前閃爍21。Buck夫婦就是早期研究這一現(xiàn)象的著名學者，他們早期合著的一系列文章22-24對此現(xiàn)象以及其他學者對

20、此現(xiàn)象的解釋進行了歸納總結(jié)，但這些解釋和總結(jié)均只停留在文字描述的層面上，并沒有建立數(shù)學模型。而在文22發(fā)表50年之后，John Buck又再次撰文25對50年中相關(guān)研究進行了總結(jié)，并給出了Phase-Advance和Phase-Delay兩種同步模型。在Phase-Advance模型中，他定義了“l(fā)ate sensitivity window”，即接近螢火蟲閃爍時刻的一個時間段，他認為如果螢火蟲在“l(fā)ate sensitivity window”中受到光刺激（即其它螢火蟲的閃爍），將立即閃爍。盡管Phase-Advance模型對螢火蟲的同步閃爍現(xiàn)象給出了一個較好的解釋，但是螢火蟲之間的相互作用

21、（通常稱為“耦合”）別限制在“l(fā)ate sensitivity window”中。Peskin將耦合作用拓展到螢火蟲閃爍周期的任意時刻。在他1975出版的書中26，Peskin針對心肌細胞同步跳動提出了一種線性振蕩器模型。他把互同步系統(tǒng)建模成許多互相耦合的相同的振蕩器的集合，每個振蕩器由一個狀態(tài)變量描述，滿足：其中和是振蕩器的固有屬性。當時，振蕩器激發(fā)，并回到狀態(tài)，同時會出現(xiàn)與其它振蕩器之間的電耦合，從而把其它振蕩器的狀態(tài)提升一個很小的增量，稱為耦合強度。而正是這種耦合的作用，使得振蕩器的狀態(tài)趨于相同，最終達到同時放電狀態(tài)。根據(jù)上述模型，Peskin提出了兩點假設(shè)：1)對任意初始狀態(tài)，系統(tǒng)總能

22、達到同步狀態(tài)；2)即使每個振蕩器結(jié)構(gòu)不同，系統(tǒng)最終也會達到同步。但是當他試圖證明他的假設(shè)的時候，他發(fā)現(xiàn)當時并沒有現(xiàn)成的數(shù)學工具可以求解這類系統(tǒng)。因此，他退而證明兩個相同結(jié)構(gòu)的振蕩器具有同步收斂性這一最簡單的情況，同時他還問題限制在很小的和，在此最簡單的情況下，Peskin證明了兩個相同結(jié)構(gòu)的耦合振蕩器具有同步收斂性。1990年，Mirollo和Strogatz在Peskin模型的基礎(chǔ)上提出一種更加一般化的線性振蕩器模型（后簡稱為M&S模型）27，在此模型中，振蕩器也使用狀態(tài)變量來描述，的變化服從函數(shù)，其中是一個0,1到0,1上的光滑單調(diào)遞增上凸函數(shù)，是相位變量且滿足(是同步周期)。Mi

23、rollo和Strogatz從理論上證明了此模型下多個耦合振蕩器系統(tǒng)在幾乎所有的初始情況下都能夠達到同步?？v觀線性振蕩器同步模型的研究，研究的主體從生物學家到數(shù)學家、物流學家進而轉(zhuǎn)移到計算機學家。今年來，將這一機制應用于計算機網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)的研究又使得該同步模型的研究成為熱點。M&S模型雖然很好的解釋了螢火蟲同步現(xiàn)象，但是其很多理想的假設(shè)在實際應用中難以保證，因此將其直接用于無線網(wǎng)絡(luò)的同步還存在不少問題。首先，這些模型都是基于即時耦合的，即脈沖的傳播是即時的、沒有延遲的，而無線通信傳輸延遲是無法避免的。Ernst等28, 29對具有延遲的兩個振蕩器之間的同步進行了數(shù)學分析，并對具有延遲

24、的多振蕩器系統(tǒng)進行了仿真。他們得出的結(jié)論是，如果采用負耦合（inhibitory couping，即），系統(tǒng)仍然能夠達到同步。其次，計算機網(wǎng)絡(luò)，特別是無線網(wǎng)絡(luò)通常是多跳網(wǎng)絡(luò)，因此M&S模型的全互聯(lián)的網(wǎng)絡(luò)拓撲也限制了模型應用范圍。Dennis和Wang30證明了M&S模型在只允許鄰居通信的前提下仍然能夠達到同步。相關(guān)工作的綜述可以參考Simeome等的文章31。最后，無線傳感器網(wǎng)絡(luò)的節(jié)點通常采用廉價的單片機作為其處理器，因此無法處理M&S模型的非線性的狀態(tài)函數(shù)。Werner-Allen等針對這一情況使用了一階泰勒展開進行了近似。我們在該方向已經(jīng)提出了一種采用線性狀態(tài)函數(shù)的

25、非漏電線性振蕩器模型，并證明了該模型在幾乎所有的條件下都能達到同步。為進一步的深入研究打下了一定的先期研究基礎(chǔ)。1Elson J, Romer K. Wireless Sensor Networks: A New Regime for Time Synchronization J. SIGCOMM Comput Commun Rev, 2003, 33(1): 149-154.2Elson J, Girod L, Estrin D. Fine-grained Network Time Synchronization Using Reference Broadcasts. J. ACM SIGO

26、PS Operating Systems Review, 2002, 36(SI): 147-163.3徐朝農(nóng), 徐勇軍, 李曉維. 無線傳感器網(wǎng)絡(luò)時間同步新技術(shù) J. 計算機研究與發(fā)展, 2008, 45(1): 138-145.4Ping S. Delay Measurement Time Synchronization for Wireless Sensor Networks. IRB-TR-03-013 R: Intel Research, 2003.5Saurabh G, Ram K, Mani B S. Timing-sync Protocol for Sensor Network

27、s. Proceedings of the 1st international conference on Embedded networked sensor systems, Los Angeles, California, USA C. ACM, 2003: 138-149.6Jana Van G, Jan R. Lightweight time synchronization for sensor networks. Proceedings of the 2nd ACM international conference on Wireless sensor networks and ap

28、plications, San Diego, CA, USA C. ACM, 2003: 11-19.7Mikl, S M, Ti, et al. The Flooding Time Synchronization Protocol. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, MD, USA C. ACM, 2004: 138-149.8李文鋒, 王汝傳, 孫力娟. 基于RBS的無線傳感器網(wǎng)絡(luò)時間同步算法 J. 通信學報, 2008, 29(6

29、): 82-86.9孫德云, 沈杰, 劉海濤. 基于擴散機制的無線傳感器網(wǎng)絡(luò)時間同步協(xié)議 J. 通信學報, 2008, 29(11): 41-49.10徐朝農(nóng), 趙磊, 徐勇軍, et al. 無線傳感器網(wǎng)絡(luò)時間同步協(xié)議的改進策略 J. 計算機學報, 2007, 30(4): 514-523.11任豐原, 董思穎, 何滔, et al. 基于鎖相環(huán)的時間同步機制與算法 J. 軟件學報, 2007, 18(2): 372-380.12李連, 孫利民, 樊孝忠. 無線傳感器網(wǎng)絡(luò)基于概率分發(fā)的時間同步協(xié)議 J. 北京郵電大學學報, 2008, 31(5): 57-60.13王喆, 王福豹, 陳振華.

30、 嵌入路由報頭的無線傳感器網(wǎng)絡(luò)時間同步算法 J. 計算機工程, 2009, 35(1): 132-134.14皇甫偉, 周新運, 陳燦峰. 基于多層抽樣反饋的傳感器網(wǎng)絡(luò)時間同步算法 J. 通信學報, 2009, 30(3): 59-65.15吳成偉, 黃文君. 無線傳感器網(wǎng)絡(luò)比對廣播時間同步算法 J. 傳感技術(shù)學報, 2009, 22(12): 1789-1794.16周新蓮, 黃力. 無線傳感器網(wǎng)絡(luò)中多跳時間同步算法的研究 J. 計算機工程與應用, 2009, 45(27): 102-104.17尹香蘭, 齊望東. LiteST:一種無線傳感器網(wǎng)絡(luò)輕量級安全時間同步協(xié)議 J. 通信學報, 2

31、009, 30(4): 74-85.18楊春明, 屈玉貴. 無線傳感器網(wǎng)絡(luò)中能量高效的時間同步算法 J. 中國科學技術(shù)大學學報, 2009, 39(5): 532-539.19Smith H M. Synchronous Flashing of Fireflies J. Science, 1935, 82(2120): 151-152.20Blair K G. Luminous Insects J. Nature, 1915, 96(2406): 411-415.21Richmond C A. Fireflies Flashing in Unison J. Science, 1930, 71(

32、1847): 537-538.22Buck J B. Synchronous Rhythmic Flashing of Fireflies J. The Quarterly Review of Biology, 1938, 13(3): 301-314.23Buck J, Buck E. Biology of Synchronous Flashing of Fireflies J. Nature, 1966, 211(5049): 562-564.24Buck J, Buck E. Mechanism of Rhythmic Synchronous Flashing of Fireflies

33、J. Science, 1968, 159(3821): 1319-1327.25Buck J. Synchronous Rhythmic Flashing of Fireflies. II J. The Quarterly Review of Biology, 1988, 63(3): 265-289.26Peskin C S. Self-Synchronization of the Cardiac Pacemaker M. Mathematical Aspects of Heart Physiology. New York; New York University. 1975: 268-2

34、78.27Mirollo R E, Strogatz S H. Synchronization of Pulse-Coupled Biological Oscillators J. SIAM Journal on Applied Mathematics, 1990, 50(6): 1645-1662.28Ernst U, Pawelzik K, Geisel T. Synchronization Induced by Temporal Delays in Pulse-Coupled Oscillators J. Physical Review Letters, 1995, 74(9): 157

35、0-1573.29Ernst U, Pawelzik K, Geisel T. Delay-induced multistable synchronization of biological oscillators J. Physical Review E, 1998, 57(2): 2150-2162.30Dennis L, Wang I J. Decentralized Synchronization Protocols with Nearest Neighbor Communication. Proceedings of the 2nd international conference

36、on Embedded networked sensor systems, Baltimore, MD, USA C. ACM, 2004: 62-68.31Simeone O, Spagnolini U, Bar-Ness Y, et al. Distributed Synchronization in Wireless Networks J. IEEE Signal Processing Magazine, 2008, 25(5): 81-97.2 主要研究內(nèi)容、目標、方案和進度及擬解決的關(guān)鍵問題：研究目標：本項目在真實的無線傳感器網(wǎng)絡(luò)環(huán)境下，分析傳統(tǒng)振蕩器模型存在的缺點，建立適合無線傳感

37、器網(wǎng)絡(luò)的基于脈沖耦合振蕩器的時間同步算法，其特點為：充分考慮了無線傳感器網(wǎng)絡(luò)的計算能力弱、頻率存在差異、通信延遲不確定、網(wǎng)絡(luò)拓撲變動因素，具有計算量小、可擴展性好、魯棒性強；將該算法在測試平臺上進行實現(xiàn)，根據(jù)測試平臺中各個參數(shù)對同步的影響程度的差異，對協(xié)議進行優(yōu)化已獲得最佳的精度。脈沖耦合振蕩器是目前對自然界生物同步現(xiàn)象的最有效的模型，其算法存儲量和計算量小，可擴展性好，非常適合于無線傳感網(wǎng)絡(luò)，可能是未來的發(fā)展方向。然而，無線傳感網(wǎng)絡(luò)存在的傳輸和處理延遲、多跳網(wǎng)絡(luò)拓撲這兩個因素在脈沖耦合振蕩器模型中并沒有被考慮，因此仍存在不足。該項目在已有的脈沖耦合振蕩器模型的基礎(chǔ)上，考慮上述兩個因素，建立基

38、于線性振蕩器的時間同步模型。本項目在真實的無線傳感器網(wǎng)絡(luò)環(huán)境下，分析傳統(tǒng)振蕩器模型存在的缺點，建立適合無線傳感器網(wǎng)絡(luò)的基于線性振蕩器的時間同步算法。其特點為：充分考慮了無線傳感器網(wǎng)絡(luò)的計算能力弱、頻率存在差異、通信延遲不確定、網(wǎng)絡(luò)拓撲變動因素，具有計算量小、可擴展性好、魯棒性強；將該算法在測試平臺上進行實現(xiàn)，根據(jù)測試平臺中各個參數(shù)對同步的影響程度的差異，對協(xié)議進行優(yōu)化已獲得最佳的精度。 研究內(nèi)容： 1、建立一種基于線性振蕩器模型的時間同步模型 基于線性振蕩器模型的無線傳感網(wǎng)絡(luò)時間同步方法是無線傳感器網(wǎng)絡(luò)時間同步研究的新方法。其通信模型、通信方式與傳統(tǒng)方法有著較大的差別，因此首先建立起一種基于線

39、性振蕩器模型的無線傳感器網(wǎng)絡(luò)時間同步模型是本項目的首要研究內(nèi)容，也是本項目后續(xù)研究的基礎(chǔ)。2、在傳統(tǒng)模型中引入傳播和處理延遲因素，研究其對模型同步的影響傳統(tǒng)的線性振蕩器模型一個最重要的假設(shè)為不存在報文的傳播和處理延遲。然而，傳播和處理延遲普遍地存在于無線通信中，該因素不僅是影響時間同步精度的重要因素，而且可能會影響振蕩器的同步收斂。因此，在線性振蕩器模型中加入報文的傳播和處理延遲因素，是基于線性振蕩器模型的時間同步算法在無線傳感器網(wǎng)絡(luò)中得到應用的先決條件。 3、在傳統(tǒng)模型中引入多跳網(wǎng)絡(luò)拓撲因素，研究其對模型同步的影響傳統(tǒng)的線性振蕩器模型一個最重要的假設(shè)為單跳網(wǎng)絡(luò)，換句話說，網(wǎng)絡(luò)中的任一個節(jié)點都

40、可以和其他節(jié)點直接通信?，F(xiàn)有的基于多跳網(wǎng)絡(luò)的線性振蕩器同步模型，也是在假設(shè)節(jié)點間耦合強度趨向于0的假設(shè)下，證明其收斂性的。顯然，這個假設(shè)因素不僅是影響時間同步精度的重要因素，而且可能會影響在多跳網(wǎng)絡(luò)條件下振蕩器的收斂性。因此，在線性振蕩器模型中多跳網(wǎng)絡(luò)因素是基于線性振蕩器模型的時間同步算法得到應用的重要條件。4、在傳統(tǒng)模型中引入頻率差異因素，研究其對模型同步的影響眾所周知，無線傳感器網(wǎng)絡(luò)節(jié)點的計數(shù)器受晶體振蕩器驅(qū)動，受到制造工藝和工作環(huán)境的影響 (溫度, 電壓等), 不同節(jié)點的晶振頻率總存在偏差, 而晶體振蕩頻率偏差又使得節(jié)點間的計時速率不一致, 即使節(jié)點在某一時刻實現(xiàn)了同步, 也會出現(xiàn)時間偏

41、移。然而振蕩器模型并沒有考慮頻率對模型同步的影響，本項目在傳統(tǒng)振蕩器的基礎(chǔ)上，分析頻率差異對模型同步的影響，建立一種頻率互異的線性振蕩器同步模型。5、設(shè)計基于線性振蕩器模型的時間同步算法，并在測試平臺上實現(xiàn)依據(jù)所研究出的線性振蕩器模型，設(shè)計適用于傳感器網(wǎng)絡(luò)的基于線性振蕩器的多跳時間同步算法，并且在測試平臺上進行實現(xiàn)；根據(jù)模型中各個參數(shù)對同步的影響程度的差異，對協(xié)議進行優(yōu)化以獲得最佳的精度。關(guān)鍵問題： 1、分別考慮延遲和多跳網(wǎng)絡(luò)拓撲條件下，線性振蕩器模型的同步性證明提出一種適用于無線傳感器網(wǎng)絡(luò)的線性振蕩器模型并證明其同步性是本項目的首要任務，也是設(shè)計同步算法的基礎(chǔ)。然而，正如前文所述，現(xiàn)有的線性

42、振蕩器模型并不適用于無線傳感器網(wǎng)絡(luò)，因此需要針對無線傳感器網(wǎng)絡(luò)的特性，分別考慮延遲和多跳網(wǎng)絡(luò)拓撲兩個因素，設(shè)計相應的振蕩器動態(tài)特性函數(shù)，并討論模型能夠達到同步所需要滿足的條件，再次基礎(chǔ)上對其同步性進行證明。這是本項目要解決的首要問題。2、綜合考慮延遲和多跳網(wǎng)絡(luò)拓撲的條件下，線性振蕩器模型的同步性證明延遲和多跳網(wǎng)絡(luò)拓撲是影響傳感器網(wǎng)絡(luò)時間同步的兩個重要因素，上一個研究點分別考慮延遲和多跳網(wǎng)絡(luò)拓撲因素下，也即假設(shè)這兩個條件不互相沖突，線性振蕩器模型的同步性。然而，延遲和多跳網(wǎng)絡(luò)拓撲這兩個因素的聯(lián)合作用，會對線性振蕩器模型的同步性產(chǎn)生何種影響，這是本項目需要重點解決的問題。3、研究在頻率差異情況下，

43、線性振蕩器模型的同步性證明經(jīng)典的Peskin模型26的第二個假設(shè)“即使每個振蕩器并不相同，系統(tǒng)最終也會達到同步”也是針對頻率的差異而進行的猜想。然而頻率的差異對耦合振蕩器模型卻沒有真正考慮過。正由于振蕩器的頻率之間存在差異，因此無法保證同步了的兩個節(jié)點任意時刻相位相同。針對這一情況，需要研究在頻率差異情況下，對線性振蕩器模型的同步性證明。4、晶振頻率模型和數(shù)據(jù)傳輸延遲模型的建立當前，對時間同步算法仿真的難度在于沒有建立無線傳感器網(wǎng)絡(luò)節(jié)點上晶振以及節(jié)點間數(shù)據(jù)傳輸延遲的模型。由于無線傳感器網(wǎng)絡(luò)通常采用廉價的晶振，因此存在一定的時鐘漂移，要建立準確的晶振頻率模型就必須對其時鐘漂移進行準確的測量，測量

44、方法以及誤差處理方法都是要研究的重要問題。無線傳感器網(wǎng)絡(luò)節(jié)點之間的通信，存在著發(fā)送、接收、編碼、解碼、傳播等一系列延遲，對這些延遲進行準確的測量和統(tǒng)計，是建立晶振頻率模型和數(shù)據(jù)傳輸延遲模型的必要工作。5、探索硬件脈沖耦合的媒介和實現(xiàn)方式基于物理脈沖耦合來對傳感器網(wǎng)絡(luò)進行同步最大的困難在于尋找一種合適的脈沖耦合的媒介。光耦合方式在光線較強時（如白天）非常容易受到環(huán)境的干擾，而采用射頻電波進行耦合，可能會受到正常通信電波的干擾。具體的媒質(zhì)方式選擇還需要進行大量的實驗來確定。另外，研究如何將這種硬件裝置與WSN節(jié)點連接，設(shè)計靈活可靠的接口，并且將這種周期性的耦合脈沖轉(zhuǎn)化為節(jié)點的時鐘值，也是本項目的難

45、度之一。研究方案：首先建立線性振蕩器模型，基于此模型分別研究延遲和網(wǎng)絡(luò)拓撲對模型的影響，并對模型的同步性進行證明。同時，設(shè)計和開發(fā)仿真程序，對模型進行驗證和實驗。在完成理論分析和仿真實驗之后，在測試平臺上進行實驗，測量同步誤差并進行分析。下面分別介紹每一部分擬采取的技術(shù)方案：1、建立線性振蕩器模型1999年P(guān)eskin在M&S模型的基礎(chǔ)上提出了耦合振蕩器模型。即對M&S模型中的，令，且，可以得到。對此微分方程兩邊進行積分可得。令為周期，為相位變量，則可得Peskin模型 前期工作采用了正耦合即耦合強度，并在此前提下證明了系統(tǒng)的同步性。但是有研究發(fā)現(xiàn)，對于M&S模型，正耦

46、合在存在延遲的情況下系統(tǒng)無法達到穩(wěn)定的同步狀態(tài)，而在負耦合的情況下，某些初始條件可以達到同步狀態(tài)。因此，考慮將負耦合引入模型，建立基于負耦合的非漏電線性振蕩器模型。然后使用正耦合的同步證明方法，推導模型達到同步需要滿足的條件。并證明兩個振蕩器組成的系統(tǒng)能夠達到同步，具體利用M&S模型中所提出的“激發(fā)映射”和“回歸映射”方法，證明回歸映射函數(shù)總是趨向于0或者1。最后，在兩個振蕩器系統(tǒng)同步證明的基礎(chǔ)上推導任意多個振蕩器組成的系統(tǒng)的同步條件，并證明同步條件的可滿足性。 2、 分析延遲對同步的影響研究延遲對線性振蕩器模型同步的影響，首先要考慮延遲的線性振蕩器模型，即加入傳播延遲參數(shù)。假設(shè)耦合脈

47、沖經(jīng)過時間后到達接收者，則對于兩個振蕩器的同步問題來說，的引入加大了分析的難度。這是由于在加入了后，使我們在分析回歸映射（即連續(xù)兩次某振蕩器激發(fā)的時候另一個振蕩器的相位）的時候必須考慮振蕩器初始相位與的大小關(guān)系。我們的設(shè)想是：在、和這三個區(qū)間里分別討論，而在每個區(qū)間內(nèi)根據(jù)耦合強度和相位的大小再次劃分出子區(qū)間。區(qū)間劃分好之后，分別對其進行編號，然后分析每一種區(qū)間的回歸映射函數(shù)，并根據(jù)回歸映射函數(shù)判斷其下一個狀態(tài)將會轉(zhuǎn)移到哪個子區(qū)間中去。在得到所有的子區(qū)間和轉(zhuǎn)換關(guān)系之后，根據(jù)這種關(guān)系構(gòu)建狀態(tài)轉(zhuǎn)換圖，即有限狀態(tài)自動機。如果這個有限狀態(tài)機中每個狀態(tài)都能轉(zhuǎn)化到最終的同步狀態(tài)，則系統(tǒng)的同步性得到了證明。對

48、于多個振蕩器，由于狀態(tài)太多，因此使用上述自動機的方法進行理論分析難度過高。擬采取仿真的方式對模型的同步性進行研究。即對振蕩器的個數(shù)和周期、耦合強度、傳輸延遲等參數(shù)在一定范圍內(nèi)分別仿真，每次仿真隨機產(chǎn)生振蕩器的初始狀態(tài)，然后按照模型的參數(shù)進行演化，同時繪制振蕩器狀態(tài)隨時間變化的狀態(tài)圖，通過每輪所有節(jié)點時間值的均方差以及狀態(tài)圖來分析系統(tǒng)的同步情況。3、分析網(wǎng)絡(luò)拓撲對同步的影響研究網(wǎng)絡(luò)拓撲對同步的影響，首先需要在模型中體現(xiàn)網(wǎng)絡(luò)拓撲關(guān)系，令為與節(jié)點相鄰的節(jié)點組成的集合，則節(jié)點的耦合方式為：,其中，為振蕩器和的連通性矩陣（如果振蕩器和連通，否則），為耦合強度。即振蕩器的相位為1時激發(fā)，同時振蕩器的相位增

49、加一個增量，如果增加之后超過1，則其也被激發(fā)。增量為振蕩器耦合強度與連通性矩陣對應元素的乘積。要證明上述情況下系統(tǒng)能夠達到同步的一種思路是，構(gòu)造相位的一個微分方程，將某節(jié)點與相鄰節(jié)點的相位差作為參數(shù)，并證明耦合的過程將導致相位差趨向于某常量。4、在測試平臺上實現(xiàn)基于上述模型的無線傳感器網(wǎng)路時間同步算法由于時間同步的實時性要求高，因此必須建立起準確的時鐘誤差機制。由于測試平臺的節(jié)點的主處理器Atmega128L的外部中斷引腳具有“自中斷”功能，即當外部中斷輸入引腳被配置為中斷輸入時，仍可以由軟件強制在該引腳上輸出任意電平，并且當輸出電平滿足中斷觸發(fā)條件時，還會觸發(fā)該外部中斷。因此，將所有節(jié)點的中

50、斷輸入引腳連接在一起，并讓其中一個節(jié)點在需要測量時鐘偏移時主動輸出一個觸發(fā)脈沖，則該觸發(fā)脈沖將會同時觸發(fā)這兩個節(jié)點的外部中斷。通過在外部中斷服務程序中記錄下節(jié)點此時的本地時刻并通過串口轉(zhuǎn)以太網(wǎng)模塊送入測試平臺的數(shù)據(jù)庫中保存，用作事后分析。通過這種機制，可以準確的獲知節(jié)點間的相對時鐘偏移。實現(xiàn)的主要工作是將理論模型中的各種參數(shù)映射到無線傳感器網(wǎng)絡(luò)的實際環(huán)境中去。首先是相位參數(shù)，由于無線傳感器網(wǎng)絡(luò)節(jié)點通常采用計數(shù)器作為時鐘，因此必須將相位由區(qū)間離散化到整數(shù)區(qū)間上；其次是耦合參數(shù)，考慮使用節(jié)點間的射頻信號或者數(shù)據(jù)包的傳輸作為模型中的耦合；最后還要考慮延遲和網(wǎng)絡(luò)拓撲的表示。另外，由實際算法設(shè)計所引入的新參數(shù)也需要對原模型進行必要的修正以及同步性證明，以保證算法的可靠性。研究進度：1、2014.5.1-2014.7.31 全面調(diào)研國內(nèi)WSN研究最新進展，深入調(diào)研現(xiàn)有國內(nèi)外WSN環(huán)境下時間同步方法的研究情況，整理出國內(nèi)外WSN時間同步方面的研究報告。2、2014.8.1-2014.10.31 研究基于線性振蕩器模型的網(wǎng)絡(luò)時間同步機制，構(gòu)建耦合振蕩器時鐘同步模型。3、2014.11.1-2015.1.31 研究頻率差異對同步的影響，構(gòu)建基于頻率互異的線性振