基于能量和傳輸路徑的時(shí)間同步算法優(yōu)化

王 軍， 易柏言， 蘆 賀

(沈陽(yáng)化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 遼寧 沈陽(yáng) 110142)

時(shí)間同步技術(shù)是當(dāng)前所有的分布式系統(tǒng)中都需要面臨解決的問(wèn)題，因此對(duì)其研究已經(jīng)十分的深入，有許多成熟的方法被用于解決這一問(wèn)題.當(dāng)前，有兩個(gè)相對(duì)成熟的時(shí)間同步技術(shù)，分別是GPS全球定位系統(tǒng)和網(wǎng)絡(luò)時(shí)間協(xié)議.但是由于無(wú)線傳感器節(jié)點(diǎn)能量有限、體積微型，并不適用于此種高功率類型的設(shè)備[1]，再加上無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署的復(fù)雜性和特殊性，GPS無(wú)法實(shí)現(xiàn)更好的應(yīng)用.所以，對(duì)于無(wú)線傳感器網(wǎng)絡(luò)有專家提出了特殊的時(shí)間同步算法，例如由MIT的Heinzelman等提出的低功耗自適應(yīng)分簇算法LEACH[2].其分簇過(guò)程主要分為兩個(gè)階段：第一階段是對(duì)傳感器節(jié)點(diǎn)進(jìn)行分簇；第二階段是分簇之后進(jìn)行簇內(nèi)與簇間的信息交換.具體過(guò)程為：簇首節(jié)點(diǎn)的選擇根據(jù)無(wú)線傳感器對(duì)簇首節(jié)點(diǎn)的期望數(shù)值和到目前為止節(jié)點(diǎn)未成為簇首節(jié)點(diǎn)的輪數(shù)決定，先給每個(gè)節(jié)點(diǎn)隨機(jī)分布一個(gè)0到1之間的數(shù)值，若該數(shù)值小于閾值T(n),那么該節(jié)點(diǎn)成為本輪的簇首節(jié)點(diǎn)，然后剩下的節(jié)點(diǎn)根據(jù)簇頭節(jié)點(diǎn)廣播的訊息選擇加入對(duì)應(yīng)的簇，形成一個(gè)完整的簇群[3-4].對(duì)節(jié)點(diǎn)進(jìn)行分簇之后，每個(gè)簇中所有的子節(jié)點(diǎn)都需要發(fā)送各自的時(shí)鐘訊息給簇首節(jié)點(diǎn)，再由簇首節(jié)點(diǎn)向外進(jìn)行通訊.在其基礎(chǔ)上改進(jìn)的DEEC算法，在能量異構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network with heterogneous energy)中，每個(gè)節(jié)點(diǎn)都有一個(gè)初始的能量值，但每個(gè)節(jié)點(diǎn)的能量值都不同，在節(jié)點(diǎn)進(jìn)行傳輸數(shù)據(jù)的時(shí)候都消耗能量，在能量消耗完全之后節(jié)點(diǎn)死亡，這時(shí)候要補(bǔ)充新的節(jié)點(diǎn).其在進(jìn)行分簇的時(shí)候，是根據(jù)節(jié)點(diǎn)當(dāng)前輪數(shù)剩余能量和網(wǎng)絡(luò)平均能量的比值來(lái)定義節(jié)點(diǎn)成為簇頭的概率[5].

對(duì)于LEACH算法，其存在的問(wèn)題是雖然采用了周期性輪巡的機(jī)制來(lái)選舉簇頭，使節(jié)點(diǎn)都有可能成為簇首節(jié)點(diǎn)，但是沒(méi)有考慮到節(jié)點(diǎn)剩余能量和簇首產(chǎn)生數(shù)目不穩(wěn)定的情況；DEEC算法是在LEACH算法的基礎(chǔ)上增加了節(jié)點(diǎn)剩余能量與平均能量的比值來(lái)限定成為簇首節(jié)點(diǎn)的概率，但是其沒(méi)有考慮到網(wǎng)絡(luò)能量消耗并不是均勻的，與實(shí)際的情況不符合.而且LEACH算法和DEEC算法在進(jìn)行時(shí)間同步的時(shí)候都是根據(jù)節(jié)點(diǎn)廣播其時(shí)鐘訊息的方式進(jìn)行同步，在節(jié)點(diǎn)廣播的時(shí)候其是和節(jié)點(diǎn)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)進(jìn)行通訊，這就使得距離越遠(yuǎn)的節(jié)點(diǎn)其通訊的時(shí)間越長(zhǎng)，導(dǎo)致時(shí)間同步的精度降低.本文針對(duì)節(jié)點(diǎn)能量消耗以及通訊路徑的問(wèn)題，提出一種改進(jìn)算法.因?yàn)楣?jié)點(diǎn)的發(fā)送頻率和傳輸距離與其損失能量有關(guān)，所以計(jì)算出一個(gè)相對(duì)值，可以讓其在最優(yōu)距離內(nèi)發(fā)送信息，這樣既降低了節(jié)點(diǎn)的能量消耗，同時(shí)使總體網(wǎng)絡(luò)所需要進(jìn)行時(shí)間同步的時(shí)間縮短.

1 時(shí)間同步概述

1.1 時(shí)間同步相關(guān)理論

時(shí)間同步技術(shù)是無(wú)線傳感器網(wǎng)絡(luò)各類應(yīng)用運(yùn)行的重要條件之一，其時(shí)間同步精度關(guān)乎著應(yīng)用的功能質(zhì)量.而保持一個(gè)全球性的時(shí)間同步時(shí)鐘對(duì)無(wú)線傳感器網(wǎng)絡(luò)在軍事防控、控制工業(yè)、檢測(cè)環(huán)境、醫(yī)用治療等諸多方面的應(yīng)用起著至關(guān)重要的作用.

基于接收者-接收者機(jī)制的時(shí)間同步算法[6]：全面考慮無(wú)線鏈路層廣播信道自身的特點(diǎn)，利用一個(gè)節(jié)點(diǎn)發(fā)送廣播的分組信息，與該節(jié)點(diǎn)所處同一個(gè)廣播域的其他節(jié)點(diǎn)同時(shí)接收廣播的分組信息，并利用各自本身的本地時(shí)鐘記錄所收到的廣播分組信息時(shí)間，并將彼此各自記錄的時(shí)間交換，通過(guò)分析比較和設(shè)計(jì)達(dá)到時(shí)間同步，即實(shí)現(xiàn)每一個(gè)節(jié)點(diǎn)間的時(shí)間同步.基于成對(duì)同步的雙向時(shí)間同步算法：發(fā)送者發(fā)出同步請(qǐng)求信息，接收者回復(fù)應(yīng)答信息，發(fā)送者依據(jù)分組中的時(shí)間信息估算同步的參量差并調(diào)成統(tǒng)一的本地時(shí)鐘，完成節(jié)點(diǎn)的同步.基于發(fā)送者-接收者的單向時(shí)間同步算法：首先由發(fā)送節(jié)點(diǎn)發(fā)出一個(gè)包含自身的本地時(shí)間信息的時(shí)間同步分組，接收節(jié)點(diǎn)用本地時(shí)間記錄接收到此包含自身本地時(shí)間信息的分組后分析提取同步分組的時(shí)間戳，然后調(diào)整自身的本地時(shí)鐘與發(fā)送節(jié)點(diǎn)的時(shí)鐘達(dá)到一致，實(shí)現(xiàn)時(shí)間同步.

1.2 時(shí)間同步性能指標(biāo)

(1)能量效率：時(shí)間同步算法要求標(biāo)準(zhǔn)的時(shí)鐘源需要在周期內(nèi)向網(wǎng)絡(luò)發(fā)送同步信息，而同步的周期越長(zhǎng)，需要發(fā)送的信息數(shù)量就越少，消耗的能量也就越少.所以時(shí)間同步算法應(yīng)該盡最大可能減少信息的延遲問(wèn)題，提高每一次瞬間的時(shí)間同步精度，并且在非同步周期時(shí)對(duì)時(shí)鐘發(fā)生偏移進(jìn)行補(bǔ)償，并在誤差標(biāo)準(zhǔn)范圍內(nèi)延長(zhǎng)同步周期[7].

(2)可擴(kuò)展性：無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的密度會(huì)影響時(shí)間同步的效率，設(shè)計(jì)一種能夠適應(yīng)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)密度變化問(wèn)題的算法具有實(shí)際價(jià)值和現(xiàn)實(shí)意義.

(3)同步精度：在無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中，對(duì)時(shí)間同步的精度要求不同，有的要求達(dá)到高程度精度上的時(shí)間同步，有的要求達(dá)到普通程度精度上的時(shí)間同步[8].

(4)魯棒性：無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)經(jīng)常需要布置在環(huán)境復(fù)雜或者人跡稀少的地方，并且常常受到惡意攻擊，如果時(shí)間同步算法不具備一定的安全性措施，節(jié)點(diǎn)受到攻擊之后所采集的信息無(wú)法保證準(zhǔn)確，直接影響人們對(duì)當(dāng)?shù)厍闆r的判斷和預(yù)測(cè).

(5)同步周期：同步周期是指在誤差標(biāo)準(zhǔn)范圍內(nèi)，無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)保持時(shí)間同步的時(shí)間長(zhǎng)短.當(dāng)對(duì)此方面要求不高時(shí)，可以選擇在需要同步的時(shí)候進(jìn)行時(shí)間同步；如果對(duì)時(shí)間同步需求很高，需要實(shí)時(shí)性采集信息，則需要節(jié)點(diǎn)時(shí)刻都保持時(shí)間同步.因此，同步周期根據(jù)環(huán)境的不同而改變.

(6)同步范圍：根據(jù)無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用在不同環(huán)境的情況，有的需要全部網(wǎng)絡(luò)上實(shí)現(xiàn)時(shí)間同步，有的需要局部區(qū)域上的時(shí)間同步.

2 時(shí)間同步分簇算法的優(yōu)化與改進(jìn)

對(duì)傳統(tǒng)分簇時(shí)間同步算法存在的問(wèn)題進(jìn)行改進(jìn)與優(yōu)化，提出一種基于能量選擇和最優(yōu)傳輸距離的分簇時(shí)間同步算法CSET(clustering time synchronization algorithm for energy selection and transmission path).此算法考慮到節(jié)點(diǎn)的初始能量和在進(jìn)行數(shù)據(jù)傳輸時(shí)所消耗的能量，并且根據(jù)最優(yōu)的傳輸路徑算法進(jìn)行簇間同步，具體步驟如下：

(1) 因?yàn)樗猩⒉嫉墓?jié)點(diǎn)屬性不同，所以需要對(duì)其各個(gè)屬性(功耗、頻率、電壓)的單位進(jìn)行統(tǒng)一，劃分為不同的類別方便計(jì)算.

(2) 對(duì)隨機(jī)散布的無(wú)線傳感器節(jié)點(diǎn)進(jìn)行初始能量統(tǒng)計(jì)，集合為U，并對(duì)集合內(nèi)所有節(jié)點(diǎn)的能量進(jìn)行統(tǒng)計(jì)，計(jì)算所有節(jié)點(diǎn)能量的平均值：

(1)

(4) 對(duì)于處于P集合內(nèi)的節(jié)點(diǎn)，根據(jù)LEACH算法進(jìn)行分簇，分簇之后進(jìn)行簇間同步.因?yàn)楣?jié)點(diǎn)的發(fā)送頻率不同，所以需要損耗的能量也不同，根據(jù)節(jié)點(diǎn)發(fā)送頻率和損失能量的關(guān)系可以算出最優(yōu)的傳輸距離，根據(jù)這個(gè)傳輸距離使得節(jié)點(diǎn)在這個(gè)范圍內(nèi)進(jìn)行同步，如公式(2)所示.

Ei損=20 lgF+20 lgD+32.4.

(2)

其中：F為節(jié)點(diǎn)的頻率;D為節(jié)點(diǎn)之間的距離.

(5) 計(jì)算節(jié)點(diǎn)之間的歐式距離：

D=minDi，j.

(3)

其中：Di,j表示節(jié)點(diǎn)之間的歐氏距離;x表示節(jié)點(diǎn)的橫坐標(biāo);y表示節(jié)點(diǎn)的縱坐標(biāo);z表示節(jié)點(diǎn)的垂直坐標(biāo);D表示節(jié)點(diǎn)間距離的最小值.

(6) 根據(jù)步驟(4)和步驟(5)可以選擇節(jié)點(diǎn)之間傳輸數(shù)據(jù)的最優(yōu)路徑.如圖1所示，A、B、C、D、E為簇首節(jié)點(diǎn).傳統(tǒng)的算法是通過(guò)廣播的形式進(jìn)行訊息交流，A簇首節(jié)點(diǎn)如果發(fā)送訊息，與其通訊距離越遠(yuǎn)的節(jié)點(diǎn)接收信息所消耗的時(shí)間越長(zhǎng)，這樣就使得總體網(wǎng)絡(luò)的時(shí)間同步變慢.而通過(guò)對(duì)節(jié)點(diǎn)發(fā)送頻率以及傳輸距離的計(jì)算，規(guī)定其一個(gè)最優(yōu)的傳輸距離，即A與B、C節(jié)點(diǎn)通訊，再通過(guò)B節(jié)點(diǎn)與D節(jié)點(diǎn)和D節(jié)點(diǎn)與E節(jié)點(diǎn)通訊，通過(guò)這樣的路徑進(jìn)行訊息交流，就可以縮短同步所需要的時(shí)間.

圖1 簇首節(jié)點(diǎn)最優(yōu)路徑Fig.1 Optimal path of cluster head node

Ei剩=Ei初-Ei損.

(4)

傳統(tǒng)的分簇式時(shí)間同步算法，是對(duì)每個(gè)節(jié)點(diǎn)隨機(jī)分配一個(gè)0到1之間的數(shù)，然后通過(guò)概率選舉的方式選舉簇首節(jié)點(diǎn)[9].但是，這種隨機(jī)概率的選舉方式會(huì)使某一節(jié)點(diǎn)的能量過(guò)度消耗，而其他節(jié)點(diǎn)卻沒(méi)有當(dāng)選簇首節(jié)點(diǎn)，導(dǎo)致節(jié)點(diǎn)的冗余，造成整個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)的浪費(fèi).基于能量選擇和最優(yōu)路徑的CSET算法，增加能量選擇公式，其可以根據(jù)節(jié)點(diǎn)的能量來(lái)限制當(dāng)選簇首節(jié)點(diǎn)的范圍.節(jié)點(diǎn)能量高于平均值則可以當(dāng)選為簇首節(jié)點(diǎn)；節(jié)點(diǎn)能量低于平均值則不可以當(dāng)選為簇首節(jié)點(diǎn).該算法進(jìn)一步地使得節(jié)點(diǎn)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的能耗達(dá)到平均，并且根據(jù)最優(yōu)路徑選擇公式，計(jì)算簇首節(jié)點(diǎn)之間進(jìn)行通訊的路徑，降低因路徑過(guò)遠(yuǎn)而造成的節(jié)點(diǎn)能量的損耗和縮短同步整體網(wǎng)絡(luò)所需要的時(shí)間.

3 仿真實(shí)驗(yàn)及性能分析

通過(guò)能量選擇和最優(yōu)路徑進(jìn)行時(shí)間同步的優(yōu)化和改進(jìn)，并且通過(guò)對(duì)該算法進(jìn)行仿真，驗(yàn)證了該算法的性能.對(duì)在范圍為200 m×200 m的區(qū)域中隨機(jī)散布的400個(gè)基于IEEE802.15.4的節(jié)點(diǎn)進(jìn)行研究，此400個(gè)節(jié)點(diǎn)可以有效去除所有可能發(fā)生的偶然性，如圖2所示.

圖2 區(qū)域內(nèi)節(jié)點(diǎn)分布Fig.2 Node distribution in the selected area

通過(guò)對(duì)LEACH算法、DEEC算法、CSET算法的節(jié)點(diǎn)能量消耗做仿真，發(fā)現(xiàn)CSET算法比其他兩種算法在控制節(jié)點(diǎn)能量消耗造成節(jié)點(diǎn)死亡的方面可以做到有效控制，延緩整個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)癱瘓的過(guò)程.由圖3可知：LEACH算法在進(jìn)行第600輪簇首選舉之后有節(jié)點(diǎn)開始死亡，DEEC算法在第700輪簇首選舉之后有節(jié)點(diǎn)開始死亡，而CSET算法雖然在節(jié)點(diǎn)死亡的起始階段與DEEC算法相差不大，但是提高了節(jié)點(diǎn)存活的時(shí)間，使得整個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)的壽命得到增加.

圖3 存活節(jié)點(diǎn)數(shù)與輪數(shù)的關(guān)系Fig.3 The relationship between the number of surviving nodes and the number of rounds

通過(guò)對(duì)LEACH算法、DEEC算法和CSET算法的能耗進(jìn)行對(duì)比可知:在初始的時(shí)候3種算法節(jié)點(diǎn)消耗的能量大致相同，但是在1500輪選舉之后，CSET算法明顯可以更加節(jié)約節(jié)點(diǎn)能量，使得網(wǎng)絡(luò)壽命更長(zhǎng)，如圖4所示.

圖4 能量消耗與輪數(shù)的關(guān)系Fig.4 The relationship between energy consumption and the number of rounds

通過(guò)對(duì)LEACH算法、DEEC算法和CSET算法的同步誤差做對(duì)比可知:DEEC算法因?yàn)樵贚EACH算法中加入了能量對(duì)比的計(jì)算，使得節(jié)點(diǎn)的運(yùn)算量增大，造成時(shí)間同步的誤差加大.而CSET算法也因?yàn)檫\(yùn)算量增多，所以，在300節(jié)點(diǎn)數(shù)之前同步誤差大于LEACH算法和DEEC算法.但是在300節(jié)點(diǎn)數(shù)之后，因?yàn)楣?jié)點(diǎn)的分布范圍變大，節(jié)點(diǎn)之間的通訊距離變大，使得LEACH算法和DEEC算法在簇間同步的時(shí)候同步誤差加大；而CSET算法因?yàn)樵黾恿俗顑?yōu)距離篩選的方式，使得節(jié)點(diǎn)之間的通訊更加快速，所以，在350節(jié)點(diǎn)數(shù)之后的同步誤差小于LEACH算法和DEEC算法.節(jié)點(diǎn)數(shù)與同步誤差的關(guān)系見(jiàn)圖5.

圖5 節(jié)點(diǎn)數(shù)與同步誤差的關(guān)系Fig.5 The relationship between number of nodes and synchronization error

4 結(jié) 論

無(wú)線傳感器網(wǎng)絡(luò)技術(shù)是在21世紀(jì)興起的一門重要技術(shù)，而時(shí)間同步則是其中最重要的組成部分，它是保障節(jié)點(diǎn)通訊、網(wǎng)絡(luò)協(xié)同的關(guān)鍵.無(wú)線傳感器可以應(yīng)用到各個(gè)方面，而時(shí)間同步越準(zhǔn)確、越節(jié)約能耗，其應(yīng)用范圍就越廣，所以，在今后無(wú)線傳感器網(wǎng)絡(luò)技術(shù)會(huì)更加普及.

初步介紹無(wú)線傳感器網(wǎng)絡(luò)技術(shù)，而其中最主要的是時(shí)間同步技術(shù).雖然隨著無(wú)線傳感器網(wǎng)絡(luò)技術(shù)的發(fā)展，研究時(shí)間同步的人越來(lái)越多，但是時(shí)間同步技術(shù)仍然存在著很大發(fā)展空間.時(shí)間同步是傳感器節(jié)點(diǎn)之間協(xié)調(diào)工作、信息傳輸?shù)幕A(chǔ)，只有基礎(chǔ)牢固頂層才會(huì)發(fā)展得更好.本文主要通過(guò)對(duì)LEACH算法、DEEC算法和CSET算法進(jìn)行對(duì)比，發(fā)現(xiàn)基于能量選擇和最優(yōu)路徑的CSET算法可以在節(jié)點(diǎn)能量消耗、節(jié)點(diǎn)網(wǎng)絡(luò)壽命和節(jié)點(diǎn)網(wǎng)絡(luò)時(shí)間同步方面起到優(yōu)化作用，延長(zhǎng)了節(jié)點(diǎn)網(wǎng)絡(luò)存在的時(shí)間，降低節(jié)點(diǎn)的能量消耗，并且使時(shí)間同步更加快捷.但是還存在著一些缺點(diǎn)，例如：如果節(jié)點(diǎn)的初始能量本就很少，那么該節(jié)點(diǎn)當(dāng)選為簇首節(jié)點(diǎn)的概率就會(huì)很低，會(huì)使得節(jié)點(diǎn)網(wǎng)絡(luò)中的部分節(jié)點(diǎn)處于冗余狀態(tài)，造成節(jié)點(diǎn)的浪費(fèi)[10].