無線傳感器網絡二階一致性時間同步

黃友銳 陳珍萍 李德權 唐超禮 曲立國

?

無線傳感器網絡二階一致性時間同步

黃友銳*①陳珍萍②李德權③唐超禮①曲立國④

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

考慮到在無線傳感器網絡中，新節點的加入或老節點的死亡均會導致拓撲呈動態變化，該文研究一種完全分布式二階一致性時間同步(Second-Order Consensus Time Synchronization, SOCTS)算法。將節點的時鐘特性建模成二階狀態方程，按照偽同步周期廣播節點的本地虛擬時間，根據鄰居節點的本地虛擬時間的不一致來構造同步控制輸入；通過坐標變換將網絡的一致性時間同步問題轉化為變換系統的穩定性問題，理論分析了SOCTS算法的收斂性和收斂條件，并研究了影響SOCTS算法收斂速度的因素。通過數值仿真實驗驗證了所提方法的有效性。

無線傳感器網絡；時間同步；一致性；收斂性

1　引言

無線傳感器網絡(Wireless Sensor Networks, WSNs)目的在于協作地感知、采集和處理網絡覆蓋區域里被監測對象的信息[1]，時間同步是無線傳感器網絡的一個支撐技術[2,3]，數據融合、移動物體的速度測量[4]、時分多址接入(Time-Division Multiple Access, TDMA) 技術等的應用，都要求無線傳感器網絡的節點擁有一致的時間。

一致性同步算法借助于網絡節點間的局部狀態信息交流實現所有節點的狀態趨于相同。文獻[8]提出了級聯一致性算法，用于同步時鐘的頻率和相位偏移，按照平均時鐘同步(Average Time-Sync, ATS)方法將節點時鐘同步到網絡時鐘的平均值。文獻[9]將二階線性一致性算法應用到無線傳感器網絡的時間同步中，根據鄰居節點與自身本地時間的差值，對本地時間和時鐘速率補償量進行調整，最終實現網絡的一致性同步。文獻[10]研究了在無傳輸延遲情形下的最大時間同步算法和考慮傳輸存在延遲時的加權最大時間同步算法，實現各個節點的邏輯時鐘同步到網絡的最大邏輯時鐘。文獻[11]主要研究了最大時間同步MTS、平均時間同步ATS算法的同步精度與通信噪聲、傳輸延遲及網絡拓撲間的關系。文獻[12]通過為一致性算法建立統一的結構模型，得到帶有隨機延時網絡一致性算法的發散條件和均方發散條件。

在分布式WSNs中，只有滿足特定條件的網絡才能實現一致性時間同步，且網絡拓撲結構影響算法的收斂速度[13,14]。本文在文獻[9]的基礎上，提出二階一致性時間同步算法SOCTS(Second-Order Consensus Time Synchronization)，主要做到以下幾點：(1)建立感知節點時鐘特性的二階狀態方程，將WSNs時間同步問題轉換為二階一致性問題，并給出了同步輸入的完全分布式設計方法；(2)通過矩陣變換和勞斯-赫爾維茨穩定判據分析出一致性時間同步算法收斂的條件；(3)理論分析出算法收斂因子與網絡拓撲及控制增益、同步周期間的關系，給出了提高SOCTS算法收斂速度的方法。

本文內容組織如下：第2節給出了本文用到的數學符號和圖論的相關預備知識；第3節給出了節點時鐘模型、二階一致性時間同步算法及同步輸入的設計；第4節給出了SOCTS算法的收斂性和收斂因子分析；第5節對SOCTS算法進行了數值仿真及分析，最后總結全文。

2 數學符號和圖論基礎

2.1數學符號

2.2 圖論相關知識

3 二階一致性時間同步

3.1節點時鐘模型

在實際應用中，出于對降低成本的考慮，網絡中的節點普遍使用頻率準確度低和穩定度差的廉價晶體振蕩器[15]，其振蕩頻率會隨著環境溫度、壓力和供電電壓的變化而產生波動，導致實際振蕩周期會偏離標稱值。將式(1)寫成式(2)所示線性表達式：

3.2 時間同步及同步控制輸入

(5)

其中，

3.3 網絡鄰接權重分布式設計

本文根據節點與輸入鄰居節點的入度信息來確定節點間的加權鄰接權重。假設網絡中所有節點均擁有一個唯一的ID號，網絡鄰接權重的分布式設計過程為

注解1[16]對一無向連通網絡，若節點與間鄰接權重按式(9)來設計，則網絡的Laplac矩陣為一對稱矩陣且滿足，它的個特征值滿足：

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

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

4.1收斂性分析

則網絡式(8)能漸近實現其二階平均一致性時間同步。

得到網絡狀態與收斂狀態間的狀態不一致方程為

(11)

至此，已將網絡式(8)的一致性狀態時間同步問題轉化為網絡狀態不一致系統式(12)的穩定性問題。

由離散時間系統狀態穩定性定義及判別方法知，式(12)中若系統矩陣的所有特征值均位于單位圓內，即，則系統式(12)穩定。

應用勞斯-赫爾維茨穩定判據，可得到使得其所有的根都具有負實部的條件為

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

4.2 收斂因子分析

首先來證明定理2的第1個結論。證明分成兩個部分，確定矩陣特征根的形式，以及確定的表達式形式。

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

(15)

(16)

5 仿真結果與分析

為驗證本文所提二階一致性時間同步算法的有效性，現進行算法的數值驗證。將個節點隨機布置在一個的矩形區域內，為每個節點隨機生成一個唯一的ID號，節點的通信半徑設置為30 m，若兩節點間空間距離小于30 m，則兩節點互為鄰居節點。根據算法運行100次的結果均值來繪制曲線和表格。每次運行時，節點的初始速率和相位分別在和之間隨機選擇，且初始化和，算法迭代300次。

5.1 SOCTS算法有效性驗證

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

圖1 節點狀態偏差迭代曲線

圖2 網絡同步誤差迭代曲線圖3 不同下的網絡同步誤差迭代曲線

表1　網絡通信半徑R對應下的網絡代數連通度

從表1可以看出，在節點位置布置相同的情況下，隨著通信半徑的增加，網絡代數連通度增加。從圖3和圖4可以看出，隨著的減小、的增加，SOCTS算法的收斂速度越來越快，仿真驗證了4.2節的理論分析結果。

5.3 SOCTS算法同步開銷分析

假設節點ID號用1 Byte表示，網絡最大節點數可為256；本地虛擬時間長度為6 Byte，在晶振周期標稱值為1時，節點可連續記時8.93 yr。如此同步信息包長度為7 Byte，在IEEE 802.15.4無線通信協議下物理層數據幀長度為15 Byte。網絡中每個節點用于實現一致性時間同步的同步開銷為Byte，其中為算法的收斂時間。

6 結束語

本文提出了一種二階一致性時間同步SOCTS算法，并給出了網絡鄰接權重、控制增益和同步周期的完全分布式設計方法，分析得出了影響SOCTS算法收斂速度的因素，并得出可從網絡鄰接權重的優化設計角度提高SOCTS算法的收斂速度。

圖4 不同通信半徑R下的網絡同步誤差迭代曲線　　　　　　　　　圖5 不同下節點的同步開銷曲線

[1] 李鵬, 王建新, 曹建農. 無線傳感器網絡中基于壓縮感知和 GM(1, 1)的異常檢測方案[J]. 電子與信息學報, 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] 王義君, 錢志鴻, 王桂琴, 等. 無線傳感器網絡能量有效時間同步算法研究[J]. 電子與信息學報, 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] 席裕庚, 李曉麗. 多智能體系統一致性的遞階結構設計[J]. 控制理論與應用, 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] 任豐原, 董思穎, 何滔, 等. 基于鎖相環的時間同步機制與算法[J]. 軟件學報, 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年生，教授，博士生導師，主要研究方向是礦山物聯網和智能信息處理.

陳珍萍： 女，1981年生，副教授，主要研究方向為物聯網技術.

李德權： 男，1973年生，教授，從事多個體系統協調控制、分布式優化理論與方法等研究.

Second-order Consensus Time Synchronization for Wireless Sensor Networks

HUANG Yourui①CHEN Zhenping②LI Dequan③TANG Chaoli①QU 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

國家自然科學基金(51274011, 51404008, 61472003)，安徽省科技攻關計劃(1501021027)

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