LTS協(xié)議

;;; ;在有些傳感器網(wǎng)絡(luò)應(yīng)用中，對(duì)時(shí)間同L4931ABD33步的精度要求并不是很高，秒級(jí)往往就能夠達(dá)到要求，同時(shí)需要時(shí)間同步的節(jié)點(diǎn)可能不是整個(gè)網(wǎng)絡(luò)的所有節(jié)點(diǎn)，這樣就可以使用簡單的輕量的時(shí)間同步機(jī)制，通過減少時(shí)間同步的頻率和參與同步的節(jié)點(diǎn)數(shù)目，在滿足同步精度要求的同時(shí)降低節(jié)點(diǎn)的通信和計(jì)算開銷，減少網(wǎng)絡(luò)能量的消耗。LTS(Lightweight Tree-based
Synchronization)同步算法的設(shè)計(jì)目標(biāo)就是適用于低成本、低復(fù)雜度的傳感器節(jié)點(diǎn)時(shí)間同步，側(cè)重最小化同步的能量開銷，同時(shí)具有魯棒性和自配置的特點(diǎn)，特別是在出現(xiàn)節(jié)點(diǎn)失敗、動(dòng)態(tài)調(diào)整信道和節(jié)點(diǎn)移動(dòng)的情況下，LTS算法仿能夠正常工作。Anceaume和Puaut把時(shí)間同步模塊劃分為3個(gè)組成部件：重同步時(shí)間監(jiān)測、遠(yuǎn)程時(shí)鐘估計(jì)和時(shí)鐘修正。重同步時(shí)間監(jiān)測用來確定節(jié)點(diǎn)進(jìn)行時(shí)間同步的時(shí)刻，可以采用兩種方式確定重同步時(shí)刻：一種是基于初始同步的時(shí)間，以kR固定周期進(jìn)行重同步，R是單個(gè)時(shí)間同步周期的長度，后是大于1的實(shí)數(shù)，用來防止兩個(gè)同步周期的重疊：另一種是一個(gè)特定節(jié)點(diǎn)在kR時(shí)間后發(fā)送初始同步消息給其他節(jié)點(diǎn)，節(jié)點(diǎn)在收到消息后啟動(dòng)時(shí)間同步，消息延遲會(huì)影響時(shí)間同步的精度。遠(yuǎn)程時(shí)鐘估計(jì)部件用來決定網(wǎng)絡(luò)中另一個(gè)節(jié)點(diǎn)的本地時(shí)鐘。通常采用兩種技術(shù)：第一種技術(shù)是“時(shí)間發(fā)送”，遠(yuǎn)程時(shí)鐘的時(shí)間值放在發(fā)送消息中；第二種技術(shù)是“遠(yuǎn)程時(shí)鐘讀取”，在不知延遲邊界時(shí)使用。它們都需要發(fā)送附加消息，增加了通信開銷，因此在輕量算法中應(yīng)該避免使用。在同步事件發(fā)生和獲取遠(yuǎn)程時(shí)鐘的估計(jì)信息后，時(shí)鐘修正部件用來更正節(jié)點(diǎn)的本地時(shí)間。該部件根據(jù)估計(jì)集計(jì)算一個(gè)調(diào)整值，估計(jì)集是由時(shí)鐘估計(jì)部件產(chǎn)生的包含相關(guān)遠(yuǎn)程時(shí)鐘估計(jì)值的集合。有兩種基本時(shí)鐘修正函數(shù)類型：收斂的基于均值的函數(shù)（返回一個(gè)估計(jì)集中的平均值）和收斂的基于非均值的函數(shù)。
;;; 在分析單跳節(jié)點(diǎn)對(duì)之間基于發(fā)送一接收方式的時(shí)間同步機(jī)制基礎(chǔ)上，J.Greunen和J.Rabaey提出了集中式和分布式兩類LTS多跳時(shí)間同步算法。集中式多跳同步算法是單跳同步的簡單線性擴(kuò)展，其基本思想是構(gòu)造低深度的生成樹，然后以樹根為參考節(jié)點(diǎn)，依次向葉節(jié)點(diǎn)進(jìn)行逐級(jí)同步，最終達(dá)到全網(wǎng)同步。根節(jié)點(diǎn)通過同步其鄰居子節(jié)點(diǎn)啟動(dòng)時(shí)間同步過程；接著，每個(gè)節(jié)點(diǎn)再與它的子節(jié)點(diǎn)同步；如此反復(fù)，直到樹的葉節(jié)點(diǎn)都被同步。集中式多跳同步算法中，根節(jié)點(diǎn)初始化同步，所有節(jié)點(diǎn)采用相同頻率進(jìn)行重同步，算法的運(yùn)行時(shí)間正比于生成樹的深度，優(yōu)化的生成樹具有小的深庋，沿著所有樹枝并進(jìn)行同步操作，葉節(jié)點(diǎn)幾乎能夠同時(shí)完成時(shí)間同步。在聆個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)中，多跳同步需要(n-l)個(gè)節(jié)點(diǎn)之間的同步。多跳同步的通信復(fù)雜性和精度與生成樹的構(gòu)造方法以及樹的深度相關(guān)，重同步頻率與時(shí)鐘漂移以及單跳同步精度相關(guān)。
;;; 在分布式多跳LTS算法中，任何節(jié)點(diǎn)j在需要重同步時(shí)都可以發(fā)起同步請(qǐng)求，從參考節(jié)點(diǎn)到節(jié)點(diǎn)i路徑上的所有節(jié)點(diǎn)采用節(jié)點(diǎn)對(duì)的同步方式，逐跳實(shí)現(xiàn)與參考節(jié)點(diǎn)的時(shí)間同步。節(jié)點(diǎn)需要跟蹤自己的時(shí)鐘漂移和同步精度，確定重同步的發(fā)起時(shí)刻。由于離參考節(jié)點(diǎn)較遠(yuǎn)節(jié)點(diǎn)的同步誤差較大，因而相應(yīng)的重同步頻率也較高。同步請(qǐng)求沿著到參考點(diǎn)的路徑傳送，中間節(jié)點(diǎn)被動(dòng)地現(xiàn)了時(shí)間同步，就不需要產(chǎn)生同步請(qǐng)求。另外，為了減少開銷，可以進(jìn)行同步請(qǐng)求消息的合并，以及節(jié)點(diǎn)以不同概率沿著不同路徑發(fā)送同步請(qǐng)求消息，這可使得更多節(jié)點(diǎn)被動(dòng)地與參考節(jié)點(diǎn)同步。當(dāng)所有節(jié)點(diǎn)需要同時(shí)進(jìn)行時(shí)間同步時(shí)，集中式多跳同步算法更為高效，當(dāng)部分節(jié)點(diǎn)需要頻繁同步時(shí)，分布式機(jī)制需要相對(duì)少量的成對(duì)同步。LTS算法與TPSN協(xié)議的區(qū)別在于LTS只需要與其直接父節(jié)點(diǎn)同步。LTS算法的同步次數(shù)是節(jié)點(diǎn)高度（與根節(jié)點(diǎn)的距離）的線性函數(shù)，降低了交換的信息量，間時(shí)也降低了同步精度。LTS算法的精度與生成樹的深度相關(guān)，構(gòu)造和維護(hù)深度小的生成樹需要一定的計(jì)算和通信開銷，同時(shí)算法還依賴從節(jié)點(diǎn)到參考節(jié)點(diǎn)的路由消息，錯(cuò)誤的路由消息可能導(dǎo)致同步失敗。