周華勇，陳珍萍

(蘇州科技大學(xué)電子與信息工程學(xué)院，江蘇 蘇州 215009)

在工業(yè)化和信息化深度融合的發(fā)展趨勢(shì)下，憑借低功耗、低成本、易部署和自適應(yīng)的優(yōu)勢(shì)，無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)成為了工業(yè)物聯(lián)網(wǎng)的關(guān)鍵技術(shù)，引起了廣泛的關(guān)注[1]。 環(huán)境的不可確定性對(duì)于無(wú)線傳感網(wǎng)絡(luò)的實(shí)時(shí)性、準(zhǔn)確性和可靠性提出了較高的要求。 如今的工業(yè)無(wú)線標(biāo)準(zhǔn)大部分都是基于介質(zhì)訪問(wèn)層控制機(jī)制，如時(shí)分多址技術(shù)，其允許多個(gè)設(shè)備通過(guò)將傳輸周期分成多個(gè)時(shí)隙來(lái)共享對(duì)公共通信信道的訪問(wèn)。 時(shí)間同步是無(wú)線傳感器網(wǎng)絡(luò)中不可缺少的一部分。 無(wú)線傳感器網(wǎng)絡(luò)中的每個(gè)傳感器都是獨(dú)立工作的，都有自己的時(shí)鐘。即使傳感器時(shí)鐘的初始狀態(tài)被調(diào)整得很完美，在實(shí)際的工作過(guò)程中，由于環(huán)境、溫度、硬件等一系列因素的影響，不同的時(shí)鐘可能會(huì)隨著時(shí)間而產(chǎn)生不同的誤差[2]。 當(dāng)傳感器節(jié)點(diǎn)的時(shí)鐘需要通過(guò)與全球定位系統(tǒng)(Global Positioning System，GPS)衛(wèi)星或網(wǎng)絡(luò)時(shí)間協(xié)議[3](Network Time Protocol，NTP)互聯(lián)網(wǎng)上的時(shí)間服務(wù)器來(lái)同步時(shí)，無(wú)線傳感器網(wǎng)絡(luò)中一般裝備了大量從節(jié)點(diǎn)來(lái)與一些主時(shí)間節(jié)點(diǎn)同步。 為了做到這一點(diǎn)，需要分布式網(wǎng)絡(luò)時(shí)鐘同步協(xié)議，通過(guò)該協(xié)議可讀取傳感器的時(shí)鐘，并將讀數(shù)傳輸?shù)狡渌麄鞲衅鞴?jié)點(diǎn)，進(jìn)而根據(jù)需要調(diào)整每個(gè)傳感器節(jié)點(diǎn)的時(shí)鐘。 在這種分布式同步方法中，參與設(shè)備以規(guī)定的間隔與它們選擇的基準(zhǔn)交換定時(shí)信息，并相應(yīng)地調(diào)整它們的邏輯時(shí)鐘。 由于實(shí)際上時(shí)鐘的設(shè)置精度有限，且同一節(jié)點(diǎn)運(yùn)行的不同時(shí)間或同一運(yùn)行時(shí)間的不同節(jié)點(diǎn)，它們時(shí)鐘的晶振頻率不同，因此，分布式時(shí)鐘必須定期同步。

時(shí)間同步是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要問(wèn)題，因?yàn)樵S多協(xié)作任務(wù)都需要時(shí)間協(xié)調(diào)。 無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步協(xié)議發(fā)展至今，針對(duì)不同的應(yīng)用分別提出了很多種集中式和分布式同步協(xié)議和算法。

集中式同步協(xié)議，例如:時(shí)間傳輸協(xié)議(Time Transfer Protocol，TTP)[3]是一個(gè)節(jié)點(diǎn)用來(lái)將它的時(shí)鐘時(shí)間傳送給另一個(gè)目標(biāo)節(jié)點(diǎn)。 目標(biāo)節(jié)點(diǎn)通過(guò)使用消息時(shí)間戳和消息延遲統(tǒng)計(jì)來(lái)估計(jì)源節(jié)點(diǎn)中的時(shí)間，而無(wú)需任何反饋?lái)憫?yīng)或成對(duì)同步。 利用了廣播媒體的固有特性(一個(gè)節(jié)點(diǎn)向單個(gè)廣播區(qū)域內(nèi)的所有節(jié)點(diǎn)發(fā)送定時(shí)信標(biāo))。 無(wú)線傳感器網(wǎng)絡(luò)中最流行的時(shí)鐘同步協(xié)議之一參考廣播同步協(xié)議(Reference Broadcast Synchronization，RBS)[4]就是基于相同的思想提出的，但允許協(xié)議拓展到多個(gè)域。 RBS 是基于事后接收器-接收器同步方法，在無(wú)線基站中，一個(gè)節(jié)點(diǎn)向兩個(gè)或多個(gè)相鄰節(jié)點(diǎn)發(fā)送參考廣播消息，相鄰節(jié)點(diǎn)在接收到廣播消息時(shí)記錄自己的本地時(shí)鐘。 在收集了一些信息之后，節(jié)點(diǎn)交換它們的觀測(cè)值，并且使用線性回歸方法來(lái)估計(jì)它們的相對(duì)時(shí)鐘偏移和偏斜。 傳感器網(wǎng)絡(luò)的定時(shí)同步協(xié)議(Timingsync Protocol for Sensor Networks，TPSN)[5]是一種傳統(tǒng)的發(fā)送方-接收方協(xié)議，它假定有兩個(gè)操作階段:級(jí)別發(fā)現(xiàn)階段和同步階段。 在級(jí)別發(fā)現(xiàn)階段，WSN以生成樹(shù)的形式組織，通過(guò)僅調(diào)整其時(shí)鐘偏移，使用發(fā)送端-接收端機(jī)制沿著層次結(jié)構(gòu)的分支進(jìn)行成對(duì)同步，使每個(gè)節(jié)點(diǎn)能夠與其父節(jié)點(diǎn)(位于相鄰上層的節(jié)點(diǎn))同步。 在無(wú)線傳感器網(wǎng)絡(luò)的分層結(jié)構(gòu)中，當(dāng)有新節(jié)點(diǎn)加入或有節(jié)點(diǎn)損壞導(dǎo)致拓?fù)浣Y(jié)構(gòu)變化時(shí)，集中式同步協(xié)議必須要處理[6]。 因此，集中式同步協(xié)議的設(shè)計(jì)往往計(jì)算復(fù)雜度高，魯棒性差，能耗大。 而且，集中式同步協(xié)議還會(huì)有累計(jì)誤差和不平衡的同步精度等缺點(diǎn)。

分布式同步協(xié)議一般基于一致性算法，如全局時(shí)鐘同步(Global Clock Synchronization，GCS)[7]、分布式時(shí)間同步協(xié)議(Distributed Time Synchronization Protocol，DTSP)[8]和一致性時(shí)鐘同步(Consensus Clock Synchronization，CCS)[9]。 分布式同步協(xié)議利用本地信息不依賴于主節(jié)點(diǎn)或參考時(shí)鐘，因此可以提高可伸縮性、負(fù)載平衡以及魯棒性。 但分布式同步協(xié)議的通信成本高，收斂時(shí)間長(zhǎng)，特別是在大型或稀疏的無(wú)線傳感器網(wǎng)絡(luò)中。 同時(shí)由于其不與外部時(shí)鐘源同步，在網(wǎng)絡(luò)被分割成獨(dú)立的信息孤島后，需要后續(xù)某種形式的時(shí)間同步處理，以能夠融合每個(gè)獨(dú)立區(qū)域的時(shí)間信息[10]。

為了解決以上問(wèn)題，本文將基于群智慧對(duì)選擇算法(Group-wise Pair selection Algorithm，GPA)的分簇技術(shù)和分布式一致性時(shí)間同步技術(shù)結(jié)合，提出了一種應(yīng)用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步方法。 本文主要貢獻(xiàn)為:①基于GPA 算法對(duì)一致性算法的拓?fù)浣Y(jié)構(gòu)進(jìn)行改進(jìn)，使得時(shí)間同步算法能夠適應(yīng)各種環(huán)境；②引入雙向信息交換模型，對(duì)網(wǎng)絡(luò)中由一致性算法形成的各信息孤島進(jìn)行有效的數(shù)據(jù)融合，使得網(wǎng)絡(luò)規(guī)模能夠有較好的可拓展性；③采用分簇的拓?fù)浣Y(jié)構(gòu)，減少節(jié)點(diǎn)之間信息交換的數(shù)據(jù)量，從而減少了能源消耗，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

1 節(jié)點(diǎn)時(shí)鐘模型

本節(jié)我們建立無(wú)線傳感器網(wǎng)絡(luò)時(shí)鐘的數(shù)學(xué)模型。對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)i，建立其一階時(shí)間模型，具體為:

式中:ωi和φi分別是節(jié)點(diǎn)i的頻率偏移和相位偏移。ωi受節(jié)點(diǎn)晶振精度、環(huán)境溫度、壓力和供電電壓等因素影響，φi受節(jié)點(diǎn)初始上電時(shí)刻影響。 雖然ωi和φi無(wú)法直接計(jì)算，但可以通過(guò)兩個(gè)節(jié)點(diǎn)的相對(duì)本地時(shí)鐘信息進(jìn)行估計(jì)。 對(duì)于節(jié)點(diǎn)i，我們可以解得，將其帶入節(jié)點(diǎn)j的^τj(t)中，可以得到:

需要注意的是，考慮到節(jié)點(diǎn)的其他功能，如定時(shí)采樣、操作系統(tǒng)的時(shí)鐘節(jié)拍中斷等，需要根據(jù)的連續(xù)記時(shí)來(lái)進(jìn)行，一般情況下不允許對(duì)進(jìn)行修改。 在無(wú)線傳感網(wǎng)絡(luò)中，通常想把通信范圍內(nèi)所有的節(jié)點(diǎn)時(shí)鐘都同步到一個(gè)虛擬時(shí)鐘，即:

式中:ωv和φv分別是虛擬參考時(shí)鐘的頻率偏移和相位偏移。 對(duì)于虛擬參考時(shí)鐘，它并不是預(yù)先設(shè)定的，它的可調(diào)參數(shù)值(ωv，φv)并不固定，最后能夠使所有的節(jié)點(diǎn)時(shí)鐘收斂到一個(gè)共同的虛擬參考時(shí)鐘。 通過(guò)MAC 層時(shí)間戳技術(shù)，本文假設(shè)本地時(shí)間的讀取和包傳輸是瞬時(shí)的[11]。

網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i的本地時(shí)鐘都是根據(jù)其本地時(shí)鐘的線性函數(shù)估計(jì)值表示，即:

式中:N為無(wú)線傳感網(wǎng)絡(luò)中的總結(jié)點(diǎn)數(shù)。作為一個(gè)虛擬時(shí)鐘，并不是一個(gè)物理時(shí)鐘。 將式(1)帶入式(4)有:

又由式(5)，當(dāng)t→∞時(shí)有:

由式(7)、式(8)可以得到，節(jié)點(diǎn)在同步時(shí)應(yīng)該獲得的補(bǔ)償參數(shù)為＾ωi和＾φi，通過(guò)這兩個(gè)參數(shù)的補(bǔ)償，可讓節(jié)點(diǎn)i時(shí)間能夠與虛擬時(shí)間同步一致。

2 基于GPA 算法的一致性時(shí)間同步

在本文提出的方案中，不是試圖與外部的參考時(shí)間(如世界協(xié)調(diào)時(shí)鐘UTC)同步，而是在網(wǎng)絡(luò)的內(nèi)部就時(shí)間和頻率的偏斜速率達(dá)成一致。 無(wú)線傳感器網(wǎng)絡(luò)在每一次時(shí)間同步后，更新每個(gè)節(jié)點(diǎn)的補(bǔ)償參數(shù)，隨著一輪一輪的同步，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的時(shí)間收斂到一致，具體如式(5)所示。

時(shí)間同步過(guò)程為:在網(wǎng)絡(luò)拓?fù)渖呻A段，本文引入了一種基于GPA 算法的拓?fù)浣Y(jié)構(gòu)生成方案，從匯聚節(jié)點(diǎn)開(kāi)始按照通信半徑將網(wǎng)絡(luò)劃分為一個(gè)一個(gè)的簇；對(duì)簇內(nèi)節(jié)點(diǎn)基于一致性理論實(shí)現(xiàn)同步，而簇與簇之間的時(shí)間同步則通過(guò)簇首間的雙向信息時(shí)間同步實(shí)現(xiàn)。

2.1 基于GPA 算法的網(wǎng)絡(luò)拓?fù)渖?/h3>

現(xiàn)有一致性時(shí)間同步協(xié)議大都假設(shè)底層傳感器網(wǎng)絡(luò)通信圖是強(qiáng)連通的，即網(wǎng)絡(luò)中存在從任意節(jié)點(diǎn)到任意節(jié)點(diǎn)的通信路徑[12]。 然而受通信環(huán)境等因素影響，該假設(shè)在現(xiàn)實(shí)中難以得到保證。 由于建筑、山體等障礙物的阻擋，會(huì)影響節(jié)點(diǎn)信號(hào)的傳輸，導(dǎo)致某些節(jié)點(diǎn)可能無(wú)法與通信范圍內(nèi)的其他節(jié)點(diǎn)通信；甚至有時(shí)因?yàn)樘鞖?、電池能耗等因素?dǎo)致節(jié)點(diǎn)損壞，無(wú)法正常工作。 這些都會(huì)導(dǎo)致網(wǎng)絡(luò)拓?fù)涞母淖?，從而影響時(shí)間同步方案的運(yùn)行。

本文所引入的拓?fù)渖煞桨改軌蛟谕負(fù)浒l(fā)生改變時(shí)，使用較少的信息傳輸數(shù)據(jù)量重新生成網(wǎng)絡(luò)拓?fù)洹?在WSN 拓?fù)渖呻A段，假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)為靜態(tài)節(jié)點(diǎn)，且具有唯一ID 號(hào)；假設(shè)所有感知節(jié)點(diǎn)初始能量相同且不能補(bǔ)充。 記網(wǎng)絡(luò)中的節(jié)點(diǎn)為Sk(k＝1，2，…，N)，其中網(wǎng)關(guān)節(jié)點(diǎn)記為S1。 拓?fù)渖砂▋蓚€(gè)過(guò)程:網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成階段和基于GPA 的成對(duì)同步(Pairwise Synchronization，PS)向量生成階段。生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1 所示。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成階段，網(wǎng)關(guān)節(jié)點(diǎn)S1周期性廣播級(jí)別數(shù)據(jù)包(帶有自身級(jí)別號(hào)和ID 號(hào))，其所有單跳鄰居節(jié)點(diǎn)接收到數(shù)據(jù)包后則分配一個(gè)比發(fā)送數(shù)據(jù)包的節(jié)點(diǎn)高一級(jí)的級(jí)別，同時(shí)這些節(jié)點(diǎn)也會(huì)廣播發(fā)送同樣類似的數(shù)據(jù)包，依次類推，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)都獲得級(jí)別號(hào)。 節(jié)點(diǎn)在分配完級(jí)別號(hào)后會(huì)丟棄其他的級(jí)別發(fā)現(xiàn)數(shù)據(jù)包，以防止沖突。

在基于GPA 的PS 向量生成階段，擁有同一個(gè)級(jí)別號(hào)的節(jié)點(diǎn)作為一個(gè)簇，在每一個(gè)簇內(nèi)的節(jié)點(diǎn)向其他簇內(nèi)的節(jié)點(diǎn)廣播連接發(fā)現(xiàn)數(shù)據(jù)包，若該簇中其他節(jié)點(diǎn)接收到信息包，則發(fā)回應(yīng)答信號(hào)，若收到屬于其他簇的節(jié)點(diǎn)的連接發(fā)現(xiàn)數(shù)據(jù)包也會(huì)將其丟棄。 節(jié)點(diǎn)標(biāo)記節(jié)點(diǎn)間連通值Md，n＝1，否則Md，n＝0；該群中同時(shí)與Sd和Sk節(jié)點(diǎn)連通的節(jié)點(diǎn)個(gè)數(shù)為，與該簇內(nèi)節(jié)點(diǎn)連通最多的節(jié)點(diǎn)號(hào)＾d＝arg maxNd，k。 節(jié)點(diǎn)S＾d可以作為兩個(gè)簇之間進(jìn)行時(shí)間同步的簇首節(jié)點(diǎn)，即PS 節(jié)點(diǎn)。

2.2 同步信息傳輸模型和簇首節(jié)點(diǎn)間成對(duì)同步

由于一致性時(shí)間同步方法無(wú)法實(shí)現(xiàn)獨(dú)立區(qū)域之間的同步進(jìn)而實(shí)現(xiàn)其信息融合，本文在生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)基礎(chǔ)上引入雙向信息交換同步機(jī)制。 考慮到節(jié)點(diǎn)h和j雙向信息交換時(shí)，其共同通信范圍內(nèi)的節(jié)點(diǎn)i可以通過(guò)單向偵聽(tīng)方式獲取信息包，基于雙向交換-單向偵聽(tīng)機(jī)制實(shí)現(xiàn)同步信息的傳輸，具體如圖2 所示。 圖2 中，節(jié)點(diǎn)h與j分別在T1，1和T3，1時(shí)刻向?qū)Ψ絺鬏斝畔黶yn(包含有節(jié)點(diǎn)j的ID和T1，1)和ack(包含有節(jié)點(diǎn)h的ID 和T3，1)時(shí)，syn中包含有一次信息交換后，節(jié)點(diǎn)j獲取的時(shí)間信息{T1，1，T2，1，T3，1，T4，1}。

圖2 同步信息雙向傳輸

假設(shè)兩個(gè)節(jié)點(diǎn)之間時(shí)鐘的相位偏移為φ，相對(duì)斜率為ω。 如圖2 所示，節(jié)點(diǎn)j在T1，1時(shí)刻發(fā)送時(shí)間同步請(qǐng)求包，節(jié)點(diǎn)h在T2，1時(shí)刻收到數(shù)據(jù)包，在T3，1時(shí)刻返回包含節(jié)點(diǎn)h時(shí)間信息的數(shù)據(jù)包，節(jié)點(diǎn)j在T4，1時(shí)刻收到，根據(jù)數(shù)據(jù)包中節(jié)點(diǎn)h的時(shí)鐘信息對(duì)本地時(shí)鐘做出調(diào)整。 節(jié)點(diǎn)j在同步過(guò)程中不斷重復(fù)此操作直到達(dá)到符合要求的精度[13-14]。 所有數(shù)據(jù)包的發(fā)送與接收時(shí)刻均以該節(jié)點(diǎn)的虛擬時(shí)鐘為基準(zhǔn)。數(shù)據(jù)包中包含發(fā)送節(jié)點(diǎn)時(shí)間戳的值、識(shí)別碼、節(jié)點(diǎn)的級(jí)別以及身份。 則T2，k和T3，k可分別表示為:

式中:d為一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的固定延遲，由于分組通常具有相同的長(zhǎng)度和數(shù)據(jù)傳輸速率，這導(dǎo)致節(jié)點(diǎn)間擁有相似的發(fā)送和接收時(shí)間，且傳播時(shí)間和節(jié)點(diǎn)間的距離保持不變，所以在這里假設(shè)d保持不變；、Y(khj)為可變延遲，本文中，X(kjh)、Y(khj)被假設(shè)為均值為0，方差為σ2的獨(dú)立同分布的高斯隨機(jī)變量；φ(jh)、φ(hj)、ω(jh)和ω(hj)分別表示節(jié)點(diǎn)A相對(duì)于節(jié)點(diǎn)P的時(shí)鐘偏移和時(shí)鐘偏斜，且φ(jh)＝φ(hj)、ω(jh)＝ω(hj)。

運(yùn)用極大似然估計(jì)的方法[15]，可以計(jì)算其相位偏移和頻率偏移，具體為:

2.3 基于一致性理論的簇內(nèi)節(jié)點(diǎn)時(shí)間同步

下面來(lái)介紹簇內(nèi)其他節(jié)點(diǎn)關(guān)于簇首節(jié)點(diǎn)的相對(duì)頻偏和相偏的估計(jì)和補(bǔ)償方法。 圖1 中，簇內(nèi)節(jié)點(diǎn)i與其簇首節(jié)點(diǎn)j的相對(duì)頻偏可以用ωij來(lái)估計(jì)，節(jié)點(diǎn)i在自己本地時(shí)間(t1)接收到來(lái)自節(jié)點(diǎn)j的廣播包中存儲(chǔ)的本地時(shí)間(t1)，并將記錄在存儲(chǔ)器中。 由于這里使用的是MAC 層時(shí)間戳，所以假設(shè)的讀數(shù)是瞬時(shí)值。 同理，當(dāng)節(jié)點(diǎn)i從節(jié)點(diǎn)j接收到一個(gè)新的數(shù)據(jù)包時(shí)，就會(huì)得到一組新的數(shù)據(jù)。 則相對(duì)頻偏ωij的估計(jì)可表示為:

設(shè)tk為更新時(shí)刻，初始值為ωij(0)＝ω(0)。 又由于不考慮兩個(gè)采樣時(shí)間t1和t2。則有:

當(dāng)k→∞時(shí)，且0＜ρ＜1，就可得到精確估計(jì)值。其中參數(shù)ρ用于調(diào)整收斂速度(ρ→0)和噪聲抗干擾(ρ→1)之間的平衡。 該算法對(duì)于內(nèi)存的需求很小，每個(gè)節(jié)點(diǎn)i只需存儲(chǔ)相對(duì)頻偏估計(jì)ωij和本地時(shí)鐘對(duì)。

對(duì)于基于一致性理論的簇內(nèi)時(shí)間同步而言，其主要思想是一種基于簇內(nèi)信息交換的分布式共識(shí)算法，即每一個(gè)節(jié)點(diǎn)都會(huì)保留自己對(duì)全局變量的估計(jì)，并通過(guò)相對(duì)于其鄰居的估計(jì)求平均值來(lái)更新其值。在文獻(xiàn)[16]的基礎(chǔ)上，本文采用一致性理論進(jìn)行節(jié)點(diǎn)虛擬時(shí)鐘頻率的迭代更新，具體為:

式中:ρ1∈(0，1)為調(diào)整參數(shù)，是的更新值為節(jié)點(diǎn)j的虛擬時(shí)鐘偏差，每個(gè)節(jié)點(diǎn)的初始條件為(0)＝1。

在采用了頻率偏移估計(jì)補(bǔ)償后，仍需估計(jì)出簇內(nèi)節(jié)點(diǎn)i和簇首節(jié)點(diǎn)j間的相對(duì)相位偏差，并進(jìn)行補(bǔ)償。 根據(jù)式(6)，可以表示出節(jié)點(diǎn)i的虛擬時(shí)鐘估計(jì)，即:

本文選用一致性算法來(lái)更新虛擬時(shí)鐘偏移量，根據(jù)式(4)有:

式中:ρ2∈(0，1)為調(diào)諧參數(shù)，和是同一時(shí)刻計(jì)算的值，為的更新值。

初始條件為(0)＝1，ρ1∈(0，1)，ρ2∈(0，1)，對(duì)于和的兩個(gè)更新方程，假設(shè)對(duì)于所有節(jié)點(diǎn)i和任意時(shí)間t存在ωv＞0 使得ωv＝(t)ωi。 并且假設(shè)存在T＞0 使得網(wǎng)絡(luò)中通信范圍內(nèi)的每個(gè)節(jié)點(diǎn)在任意長(zhǎng)度為T的時(shí)間窗口中至少向其鄰居發(fā)送一次本地虛擬時(shí)鐘參數(shù)。 則有:

也即簇內(nèi)節(jié)點(diǎn)i 同步到簇首節(jié)點(diǎn)j。

3 數(shù)值仿真結(jié)果與分析

本節(jié)將在MATLAB 仿真平臺(tái)上進(jìn)行本文所提基于GPA 算法的一致性時(shí)間同步方法有效性驗(yàn)證。

3.1 拓?fù)浣Y(jié)構(gòu)的生成

為了保證網(wǎng)絡(luò)能夠至少生成一個(gè)簇，將100 個(gè)仿真節(jié)點(diǎn)(其中一個(gè)為網(wǎng)關(guān)節(jié)點(diǎn))隨機(jī)布置在一個(gè)400 m×25 m 的矩形區(qū)域內(nèi)，設(shè)置節(jié)點(diǎn)的通信半徑為25 m。 在MATLAB 仿真平臺(tái)中，模擬生成了節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)以及通信情況如圖3 和圖4 所示。

圖3 初始網(wǎng)絡(luò)拓?fù)?/p>

圖4 基于GPA 算法的網(wǎng)絡(luò)拓?fù)?/p>

圖3 中坐標(biāo)為(0，3)的實(shí)心點(diǎn)表示網(wǎng)關(guān)節(jié)點(diǎn)，其他實(shí)心點(diǎn)表示網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)，實(shí)線表示節(jié)點(diǎn)間的通信，圖4 中直徑較大的實(shí)心點(diǎn)表示網(wǎng)關(guān)節(jié)點(diǎn)或簇首節(jié)點(diǎn)(網(wǎng)關(guān)節(jié)點(diǎn)也可作為簇首節(jié)點(diǎn))，直徑較小的實(shí)心點(diǎn)表示簇內(nèi)的普通節(jié)點(diǎn)，虛線表示簇首節(jié)點(diǎn)與簇內(nèi)節(jié)點(diǎn)和其他簇首節(jié)點(diǎn)、以及簇內(nèi)節(jié)點(diǎn)之間的通信。

表1 為幾種拓?fù)渖煞椒ǖ臄?shù)據(jù)傳輸量對(duì)比。從表1 中可以看出，不同時(shí)間同步協(xié)議在完成時(shí)間同步時(shí)傳輸?shù)臄?shù)據(jù)包數(shù)量對(duì)比，因此與TPSN 算法和RBS 算法相比，本文所提方法所需的信息交換數(shù)量大幅度降低；與FTSP 算法相比信息交換數(shù)量也有一定程度的減少。 因此，本文所提拓?fù)錁?gòu)建方案能夠有效減少節(jié)點(diǎn)間信息傳輸?shù)臄?shù)據(jù)量，從而減少節(jié)點(diǎn)的能量消耗。

表1 拓?fù)渖蓴?shù)據(jù)傳輸量對(duì)比

3.2 一致性時(shí)間同步方法仿真

在圖4 所示的拓?fù)浣Y(jié)構(gòu)上進(jìn)行本文所提一致性算法仿真。 隨機(jī)選取其中一個(gè)包含10 個(gè)節(jié)點(diǎn)的簇進(jìn)行一致性時(shí)間同步方法的仿真。 根據(jù)文獻(xiàn)[17]，設(shè)置同步周期T＝100 s，ρ＝ρ1＝ρ2＝0.6，節(jié)點(diǎn)初始時(shí)鐘頻率偏移從[0.9，1.1]中隨機(jī)選取。

節(jié)點(diǎn)按照式(1)所示時(shí)間模型進(jìn)行迭代，所得本地時(shí)鐘迭代曲線如圖5 所示。

圖5 無(wú)時(shí)鐘調(diào)整下本地時(shí)鐘迭代曲線

從圖5 可以看出，在沒(méi)有算法糾正的情況下，節(jié)點(diǎn)只會(huì)按照自己的本地時(shí)鐘計(jì)時(shí)，無(wú)線傳感器網(wǎng)絡(luò)中的各節(jié)點(diǎn)之間時(shí)間都會(huì)存在誤差，其中2 號(hào)節(jié)點(diǎn)和5 號(hào)節(jié)點(diǎn)的初始值相差0.009 s，而迭代了25 次后，這兩節(jié)點(diǎn)之間的誤差就達(dá)到了0.017 4 s，增長(zhǎng)了近一倍。 因此，有必要采取方案對(duì)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行時(shí)間同步。

根據(jù)式(15)和式(17)的方法進(jìn)行節(jié)點(diǎn)相偏和頻偏的估計(jì)、補(bǔ)償，得到圖6 和圖7 所示的節(jié)點(diǎn)虛擬頻偏估計(jì)補(bǔ)償和虛擬相偏估計(jì)補(bǔ)償曲線。 從圖6 和圖7可以看出，任一節(jié)點(diǎn)與其他節(jié)點(diǎn)的頻偏速率之比，其比值恒定，表示節(jié)點(diǎn)間的頻率偏斜率一致，即節(jié)點(diǎn)間的頻偏能夠保持相對(duì)一致；在進(jìn)行偏移的補(bǔ)償?shù)?，其值基本上能按照預(yù)期收斂于某一恒定值。

圖6 節(jié)點(diǎn)的頻偏估計(jì)補(bǔ)償

圖7 節(jié)點(diǎn)的相偏估計(jì)補(bǔ)償

根據(jù)頻率偏移和相位偏移的估計(jì)值，按照式(3)對(duì)簇內(nèi)節(jié)點(diǎn)進(jìn)行時(shí)鐘調(diào)整，得到圖8 所示的節(jié)點(diǎn)虛擬時(shí)鐘迭代曲線，以及圖9 所示的虛擬時(shí)鐘平均值的誤差百分比迭代曲線，其中虛擬時(shí)鐘平均值的百分比定義為為虛擬時(shí)鐘的平均值)。 從圖8和圖9 可以看出，隨著同步迭代次數(shù)的增加，節(jié)點(diǎn)的虛擬時(shí)鐘能夠趨于一致同步，節(jié)點(diǎn)的偏差最大為31 μs，且虛擬時(shí)鐘瞬時(shí)平均值的誤差百分比也會(huì)越來(lái)越小，即簇內(nèi)節(jié)點(diǎn)的虛擬時(shí)鐘偏差達(dá)到一致。

圖8 節(jié)點(diǎn)的虛擬時(shí)鐘

圖9 虛擬時(shí)鐘瞬時(shí)平均值的誤差百分比

3.3 多跳網(wǎng)絡(luò)的時(shí)間同步算法對(duì)比

本文進(jìn)行了CCS(不分簇的一致性時(shí)間同步方法)、DTSP(分布式時(shí)間同步方法)和本文同步方法的同步速度對(duì)比仿真實(shí)驗(yàn)。 從算法時(shí)間復(fù)雜度的角度分析，時(shí)間同步算法都是節(jié)點(diǎn)根據(jù)接收的鄰居節(jié)點(diǎn)發(fā)送的時(shí)鐘信息運(yùn)行的，其時(shí)間復(fù)雜度與節(jié)點(diǎn)間時(shí)鐘信息交換的次數(shù)相關(guān)。 在簇內(nèi)利用一致性時(shí)間同步方法的時(shí)間復(fù)雜度為O(n1)，n1為簇內(nèi)節(jié)點(diǎn)交換時(shí)鐘信息的次數(shù)；簇間利用雙向信息交換機(jī)制的時(shí)間復(fù)雜度為O(n2)，n2為簇首節(jié)點(diǎn)交換時(shí)鐘信息的次數(shù)；采用不分簇時(shí)間同步方案的時(shí)間復(fù)雜度為O(n3)，n3表示全網(wǎng)節(jié)點(diǎn)交換時(shí)鐘信息的次數(shù)。 采用本文時(shí)間同步方案不需要全網(wǎng)所有節(jié)點(diǎn)之間互相通信，因此減少了時(shí)鐘信息的交換次數(shù)，降低了時(shí)間復(fù)雜度，即O(n1)＋O(n2)＜O(n3)。

圖10 給出了同步速度對(duì)比結(jié)果，從圖10 可以看出，與另外兩種時(shí)間同步方法相比，本文所提方法節(jié)點(diǎn)的虛擬時(shí)鐘平均誤差百分比曲線收斂得更快，在節(jié)點(diǎn)數(shù)N＝100 的網(wǎng)絡(luò)規(guī)模下，本文方法相較于CCS 和DTSP 時(shí)間同步算法能夠在更少的迭代次數(shù)基礎(chǔ)上達(dá)到有效收斂，節(jié)點(diǎn)的同步誤差最大為32.1 μs，說(shuō)明本文所提出的方案在滿足較大規(guī)模的無(wú)線傳感網(wǎng)絡(luò)時(shí)間同步的基礎(chǔ)上，比不分簇的一致性時(shí)間同步方法具有更好的同步性能。

圖10 同步速度仿真對(duì)比結(jié)果

4 總結(jié)

結(jié)合GPA 算法的拓?fù)浣Y(jié)構(gòu)以及節(jié)點(diǎn)間雙向時(shí)間同步的特點(diǎn)，提出了一種改進(jìn)的一致性時(shí)間同步方案，并仿真分析了它的可行性。 本文基于GPA 算法將大規(guī)模網(wǎng)絡(luò)進(jìn)行分簇，并通過(guò)一致性算法進(jìn)行簇內(nèi)節(jié)點(diǎn)的時(shí)間同步，同時(shí)利用雙向信息交換時(shí)間同步實(shí)現(xiàn)獨(dú)立的一致性時(shí)間同步區(qū)域間的時(shí)間信息融合同步。 仿真實(shí)驗(yàn)結(jié)果表明，本文的時(shí)間同步方法能夠有效提高無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步收斂速度，減少節(jié)點(diǎn)間的通信數(shù)據(jù)包數(shù)量。

在實(shí)際的網(wǎng)絡(luò)環(huán)境中可能還有通信噪聲的影響，今后的工作還會(huì)考慮通信噪聲影響下的一致性時(shí)間同步。