無(wú)線傳感器網(wǎng)絡(luò)二階一致性時(shí)間同步

黃友銳 陳珍萍 李德權(quán) 唐超禮 曲立國(guó)

?

無(wú)線傳感器網(wǎng)絡(luò)二階一致性時(shí)間同步

黃友銳*①陳珍萍②李德權(quán)③唐超禮①曲立國(guó)④

①(安徽理工大學(xué)電氣與信息工程學(xué)院 淮南 232001);②(蘇州科技大學(xué)電子與信息工程學(xué)院 蘇州 215009);③(安徽理工大學(xué)理學(xué)院 淮南 232001);④(安徽師范大學(xué)物理與電子信息學(xué)院 蕪湖 241000)

考慮到在無(wú)線傳感器網(wǎng)絡(luò)中，新節(jié)點(diǎn)的加入或老節(jié)點(diǎn)的死亡均會(huì)導(dǎo)致拓?fù)涑蕜?dòng)態(tài)變化，該文研究一種完全分布式二階一致性時(shí)間同步(Second-Order Consensus Time Synchronization, SOCTS)算法。將節(jié)點(diǎn)的時(shí)鐘特性建模成二階狀態(tài)方程，按照偽同步周期廣播節(jié)點(diǎn)的本地虛擬時(shí)間，根據(jù)鄰居節(jié)點(diǎn)的本地虛擬時(shí)間的不一致來(lái)構(gòu)造同步控制輸入；通過(guò)坐標(biāo)變換將網(wǎng)絡(luò)的一致性時(shí)間同步問(wèn)題轉(zhuǎn)化為變換系統(tǒng)的穩(wěn)定性問(wèn)題，理論分析了SOCTS算法的收斂性和收斂條件，并研究了影響SOCTS算法收斂速度的因素。通過(guò)數(shù)值仿真實(shí)驗(yàn)驗(yàn)證了所提方法的有效性。

無(wú)線傳感器網(wǎng)絡(luò)；時(shí)間同步；一致性；收斂性

1　引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)目的在于協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域里被監(jiān)測(cè)對(duì)象的信息[1]，時(shí)間同步是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)支撐技術(shù)[2,3]，數(shù)據(jù)融合、移動(dòng)物體的速度測(cè)量[4]、時(shí)分多址接入(Time-Division Multiple Access, TDMA) 技術(shù)等的應(yīng)用，都要求無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)擁有一致的時(shí)間。

一致性同步算法借助于網(wǎng)絡(luò)節(jié)點(diǎn)間的局部狀態(tài)信息交流實(shí)現(xiàn)所有節(jié)點(diǎn)的狀態(tài)趨于相同。文獻(xiàn)[8]提出了級(jí)聯(lián)一致性算法，用于同步時(shí)鐘的頻率和相位偏移，按照平均時(shí)鐘同步(Average Time-Sync, ATS)方法將節(jié)點(diǎn)時(shí)鐘同步到網(wǎng)絡(luò)時(shí)鐘的平均值。文獻(xiàn)[9]將二階線性一致性算法應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步中，根據(jù)鄰居節(jié)點(diǎn)與自身本地時(shí)間的差值，對(duì)本地時(shí)間和時(shí)鐘速率補(bǔ)償量進(jìn)行調(diào)整，最終實(shí)現(xiàn)網(wǎng)絡(luò)的一致性同步。文獻(xiàn)[10]研究了在無(wú)傳輸延遲情形下的最大時(shí)間同步算法和考慮傳輸存在延遲時(shí)的加權(quán)最大時(shí)間同步算法，實(shí)現(xiàn)各個(gè)節(jié)點(diǎn)的邏輯時(shí)鐘同步到網(wǎng)絡(luò)的最大邏輯時(shí)鐘。文獻(xiàn)[11]主要研究了最大時(shí)間同步MTS、平均時(shí)間同步ATS算法的同步精度與通信噪聲、傳輸延遲及網(wǎng)絡(luò)拓?fù)溟g的關(guān)系。文獻(xiàn)[12]通過(guò)為一致性算法建立統(tǒng)一的結(jié)構(gòu)模型，得到帶有隨機(jī)延時(shí)網(wǎng)絡(luò)一致性算法的發(fā)散條件和均方發(fā)散條件。

在分布式WSNs中，只有滿足特定條件的網(wǎng)絡(luò)才能實(shí)現(xiàn)一致性時(shí)間同步，且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響算法的收斂速度[13,14]。本文在文獻(xiàn)[9]的基礎(chǔ)上，提出二階一致性時(shí)間同步算法SOCTS(Second-Order Consensus Time Synchronization)，主要做到以下幾點(diǎn)：(1)建立感知節(jié)點(diǎn)時(shí)鐘特性的二階狀態(tài)方程，將WSNs時(shí)間同步問(wèn)題轉(zhuǎn)換為二階一致性問(wèn)題，并給出了同步輸入的完全分布式設(shè)計(jì)方法；(2)通過(guò)矩陣變換和勞斯-赫爾維茨穩(wěn)定判據(jù)分析出一致性時(shí)間同步算法收斂的條件；(3)理論分析出算法收斂因子與網(wǎng)絡(luò)拓?fù)浼翱刂圃鲆?、同步周期間的關(guān)系，給出了提高SOCTS算法收斂速度的方法。

本文內(nèi)容組織如下：第2節(jié)給出了本文用到的數(shù)學(xué)符號(hào)和圖論的相關(guān)預(yù)備知識(shí)；第3節(jié)給出了節(jié)點(diǎn)時(shí)鐘模型、二階一致性時(shí)間同步算法及同步輸入的設(shè)計(jì)；第4節(jié)給出了SOCTS算法的收斂性和收斂因子分析；第5節(jié)對(duì)SOCTS算法進(jìn)行了數(shù)值仿真及分析，最后總結(jié)全文。

2 數(shù)學(xué)符號(hào)和圖論基礎(chǔ)

2.1數(shù)學(xué)符號(hào)

2.2 圖論相關(guān)知識(shí)

3 二階一致性時(shí)間同步

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

在實(shí)際應(yīng)用中，出于對(duì)降低成本的考慮，網(wǎng)絡(luò)中的節(jié)點(diǎn)普遍使用頻率準(zhǔn)確度低和穩(wěn)定度差的廉價(jià)晶體振蕩器[15]，其振蕩頻率會(huì)隨著環(huán)境溫度、壓力和供電電壓的變化而產(chǎn)生波動(dòng)，導(dǎo)致實(shí)際振蕩周期會(huì)偏離標(biāo)稱值。將式(1)寫(xiě)成式(2)所示線性表達(dá)式：

3.2 時(shí)間同步及同步控制輸入

(5)

其中，

3.3 網(wǎng)絡(luò)鄰接權(quán)重分布式設(shè)計(jì)

本文根據(jù)節(jié)點(diǎn)與輸入鄰居節(jié)點(diǎn)的入度信息來(lái)確定節(jié)點(diǎn)間的加權(quán)鄰接權(quán)重。假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)均擁有一個(gè)唯一的ID號(hào)，網(wǎng)絡(luò)鄰接權(quán)重的分布式設(shè)計(jì)過(guò)程為

注解1[16]對(duì)一無(wú)向連通網(wǎng)絡(luò)，若節(jié)點(diǎn)與間鄰接權(quán)重按式(9)來(lái)設(shè)計(jì)，則網(wǎng)絡(luò)的Laplac矩陣為一對(duì)稱矩陣且滿足，它的個(gè)特征值滿足：

4 算法收斂性和收斂因子分析

定義2[5,16,17]假定一維向量序列收斂到某一極限，若存在一實(shí)數(shù)，使得

4.1收斂性分析

則網(wǎng)絡(luò)式(8)能漸近實(shí)現(xiàn)其二階平均一致性時(shí)間同步。

得到網(wǎng)絡(luò)狀態(tài)與收斂狀態(tài)間的狀態(tài)不一致方程為

(11)

至此，已將網(wǎng)絡(luò)式(8)的一致性狀態(tài)時(shí)間同步問(wèn)題轉(zhuǎn)化為網(wǎng)絡(luò)狀態(tài)不一致系統(tǒng)式(12)的穩(wěn)定性問(wèn)題。

由離散時(shí)間系統(tǒng)狀態(tài)穩(wěn)定性定義及判別方法知，式(12)中若系統(tǒng)矩陣的所有特征值均位于單位圓內(nèi)，即，則系統(tǒng)式(12)穩(wěn)定。

應(yīng)用勞斯-赫爾維茨穩(wěn)定判據(jù)，可得到使得其所有的根都具有負(fù)實(shí)部的條件為

對(duì)上述條件進(jìn)行整理可得如式(10)所示條件。證畢

4.2 收斂因子分析

首先來(lái)證明定理2的第1個(gè)結(jié)論。證明分成兩個(gè)部分，確定矩陣特征根的形式，以及確定的表達(dá)式形式。

即為式(14)。反之若式(14)不滿足時(shí)而式(13)滿足時(shí)，即和滿足：

(15)

(16)

5 仿真結(jié)果與分析

為驗(yàn)證本文所提二階一致性時(shí)間同步算法的有效性，現(xiàn)進(jìn)行算法的數(shù)值驗(yàn)證。將個(gè)節(jié)點(diǎn)隨機(jī)布置在一個(gè)的矩形區(qū)域內(nèi)，為每個(gè)節(jié)點(diǎn)隨機(jī)生成一個(gè)唯一的ID號(hào)，節(jié)點(diǎn)的通信半徑設(shè)置為30 m，若兩節(jié)點(diǎn)間空間距離小于30 m，則兩節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)。根據(jù)算法運(yùn)行100次的結(jié)果均值來(lái)繪制曲線和表格。每次運(yùn)行時(shí)，節(jié)點(diǎn)的初始速率和相位分別在和之間隨機(jī)選擇，且初始化和，算法迭代300次。

5.1 SOCTS算法有效性驗(yàn)證

5.2影響SOCTS算法收斂速度的因素

圖1 節(jié)點(diǎn)狀態(tài)偏差迭代曲線

圖2 網(wǎng)絡(luò)同步誤差迭代曲線圖3 不同下的網(wǎng)絡(luò)同步誤差迭代曲線

表1　網(wǎng)絡(luò)通信半徑R對(duì)應(yīng)下的網(wǎng)絡(luò)代數(shù)連通度

從表1可以看出，在節(jié)點(diǎn)位置布置相同的情況下，隨著通信半徑的增加，網(wǎng)絡(luò)代數(shù)連通度增加。從圖3和圖4可以看出，隨著的減小、的增加，SOCTS算法的收斂速度越來(lái)越快，仿真驗(yàn)證了4.2節(jié)的理論分析結(jié)果。

5.3 SOCTS算法同步開(kāi)銷分析

假設(shè)節(jié)點(diǎn)ID號(hào)用1 Byte表示，網(wǎng)絡(luò)最大節(jié)點(diǎn)數(shù)可為256；本地虛擬時(shí)間長(zhǎng)度為6 Byte，在晶振周期標(biāo)稱值為1時(shí)，節(jié)點(diǎn)可連續(xù)記時(shí)8.93 yr。如此同步信息包長(zhǎng)度為7 Byte，在IEEE 802.15.4無(wú)線通信協(xié)議下物理層數(shù)據(jù)幀長(zhǎng)度為15 Byte。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)用于實(shí)現(xiàn)一致性時(shí)間同步的同步開(kāi)銷為Byte，其中為算法的收斂時(shí)間。

6 結(jié)束語(yǔ)

本文提出了一種二階一致性時(shí)間同步SOCTS算法，并給出了網(wǎng)絡(luò)鄰接權(quán)重、控制增益和同步周期的完全分布式設(shè)計(jì)方法，分析得出了影響SOCTS算法收斂速度的因素，并得出可從網(wǎng)絡(luò)鄰接權(quán)重的優(yōu)化設(shè)計(jì)角度提高SOCTS算法的收斂速度。

圖4 不同通信半徑R下的網(wǎng)絡(luò)同步誤差迭代曲線　　　　　　　　　圖5 不同下節(jié)點(diǎn)的同步開(kāi)銷曲線

[1] 李鵬, 王建新, 曹建農(nóng). 無(wú)線傳感器網(wǎng)絡(luò)中基于壓縮感知和 GM(1, 1)的異常檢測(cè)方案[J]. 電子與信息學(xué)報(bào), 2015, 37(7): 1586-1590. doi: 10.11999/JEIT141219.

LI Peng, WANG Jianxin, and CAO Jiannong. Abnormal event detection scheme based on compressive sensing and GM (1,1) in wireless sensor networks[J].&, 2015, 37(7): 1586-1590. doi: 10. 11999/JEIT141219.

[2] LIU Bin, REN Fengyuan, SHEN Junyang,. Advanced self-correcting time synchronization in wireless sensor networks[J]., 2010, 14(4): 309-311. doi: 10.1109/LCOMM.2010.04.092364.

[3] 王義君, 錢志鴻, 王桂琴, 等. 無(wú)線傳感器網(wǎng)絡(luò)能量有效時(shí)間同步算法研究[J]. 電子與信息學(xué)報(bào), 2012, 34(9): 2174-2179.doi: 10.3724/sp.j.1146.2012.00236.

WANG Yijun, QIAN Zhihong, WANG Guiqin,. Research on energy-efficient time synchronization algorithm for wireless sensor networks[J].&, 2012, 34(9): 2174-2179. doi: 10. 3724/sp.j.1146.2012.00236.

[4] ZHANG Weile, YIN Qinye, CHEN Hongyang,. Distributed angle estimation for localization in wireless sensor networks[J]., 2012, 12(2): 527-537. doi: 10.1109/ GLOCOM.2010.5683803.

[5] LI Dequan, LIU Qipeng, WANG Xiaofan,. Consensus seeking over directed networks with limited information communication[J]., 2013, 49(2): 610-618. doi: 10.1016/j.automatica.2012.11.041.

[6] 席裕庚, 李曉麗. 多智能體系統(tǒng)一致性的遞階結(jié)構(gòu)設(shè)計(jì)[J]. 控制理論與應(yīng)用, 2015, 32(9): 1191-1199. doi: 10.7641/CTA. 2015.50393.

XI Yugeng and LI Xiaoli. Hierarchical structure design for multi-agent consensus[J]., 2015, 32(9): 1191-1199. doi: 10.7641/CTA.2015.50393.

[7] HE Wangli, ZHANG Biao, HAN Qianlong,. Leader- following consensus of nonlinear multiagent systems with stochastic sampling[J]., 2016, 99: 1-12. doi: 10.1109/TCYB.2015.2514119.

[8] LUCA S and FEDERICO F. Average timesynch: a consensus- based protocol for clock synchronization in wireless sensor networks[J]., 2011, 47(9): 1878-1886. doi: 10. 1016/j.automatica.2011.06.012.

[9] RUGGERO C and SANDRO Z. Network clock synchronization based on the second-order linear consensus algorithm[J]., 2014, 59(2): 409-422. doi: 10.1109/TAC.2013.2283742.

[10] HE Jianping, CHENG Peng, SHI Lin,Time synchronization in WSNs: A maximum-value-based consensus approach[J]., 2014, 59(3): 660-675. doi: 10.1109/TAC.2013. 2286893.

[11] HE Jiangping, LI Hao, CHEN Jiming,Study of consensus-based time synchronization in wireless sensor networks[J]., 2014, 53(2): 347-357. doi: 10.1016/j.isatra.2013. 11.001.

[12] TIAN Yuping, ZONG Siheng, and CAO Qingqing. Structural modeling and convergence analysis of consensus-based time synchronization algorithms over networks: Non-topological conditions[J]., 2016, 65: 64-75. doi: 10.1016/j. automatica.2015.11.034.

[13] ASENSIO M C and BEFERULL L B. Accelerating consensus gossip algorithms: sparsifying networks can be good for you[C]. IEEE International Conference on Communications, Cape Town, South Africa, 2010: 1-5. doi: 10.1109/ICC.2010. 5502427.

[14] VECCHIO M and LóPEZ-VALCARCE R. A greedy topology design to accelerate consensus in broadcast wireless sensor networks[J]., 2015, 115(3): 408-413. doi: 10.1016/j.ipl.2014.11.009.

[15] 任豐原, 董思穎, 何滔, 等. 基于鎖相環(huán)的時(shí)間同步機(jī)制與算法[J]. 軟件學(xué)報(bào), 2007, 18(2): 372-380. doi: 10.1360/jos180 372.

REN Fengyuan, DONG Siying, HE Tao,A time synchronization mechanism and algorithm based on phase lock loop[J]., 2007, 18(2): 372-380.doi: 10.1360/jos180372.

[16] CARLI R and LOVISARIE E. Robust synchronization of networks of heterogeneous double-integrators[C].IEEE 51st Annual Conference on Decision and Control (CDC), Grand Wailea, Maui, HI, USA, 2012: 260-265. doi: 10.1109/ CDC.2012. 6426768.

[17] LIN Xiao and STEPHEN Boyd. Fast linear iterations for distributed averaging[J].&, 2003, 5(1): 65-78. doi: 10.1109/CDC.2003.1272421.

[18] GEORG S S, DIMOS V D, and KARL H J. Event-based broadcasting for multi-agent average consensus[J]., 2013, 49(1): 245-252. doi: 10.1016/j.automatica. 2012.08.042.

黃友銳： 男，1971年生，教授，博士生導(dǎo)師，主要研究方向是礦山物聯(lián)網(wǎng)和智能信息處理.

陳珍萍： 女，1981年生，副教授，主要研究方向?yàn)槲锫?lián)網(wǎng)技術(shù).

李德權(quán)： 男，1973年生，教授，從事多個(gè)體系統(tǒng)協(xié)調(diào)控制、分布式優(yōu)化理論與方法等研究.

Second-order Consensus Time Synchronization for Wireless Sensor Networks

HUANG Yourui①CHEN Zhenping②LI Dequan③TANG Chaoli①Q(mào)U Liguo④

①(,,232001,)②(,,215009,);③(,,232001,);④(,,241000,)

Since in wireless sensor networks, the joint of new nodes or the death of old nodes lead to a dynamic topology, this paper studies one completely distributed Second-Order Consensus Time Synchronization (SOCTS) algorithm. The clock feature of each node is modeled into a second order state equation, and the local virtual time is broadcasted according to the pseudo synchronous cycle, Moreover, the synchronization control input is constructed according to the disagreement on local virtual time among neighboring nodes. By virtue of the matrix transformation, the network time synchronization issue is turned into the stability issue of some transformed system, and the convergence and convergence condition for the SOCTS algorithm are analyzed theoretically. Moreover, the factors that influence the convergence rate of the SOCTS algorithm are investigated. Finally, the effectiveness of the proposed method is verified by numerical simulations.

Wireless sensor networks; Time synchronization; Consensus; Convergence

TP393

A

1009-5896(2017)01-0051-07

10.11999/JEIT160382

2016-04-19；改回日期：2016-09-09；

2016-11-04

黃友銳 hyr628@163.com

國(guó)家自然科學(xué)基金(51274011, 51404008, 61472003)，安徽省科技攻關(guān)計(jì)劃(1501021027)

The National Natural Science Foundation of China (51274011, 51404008, 61472003), The Science and Technology Research Plan of Anhui Province (1501021027)