一種簡單的基于事件觸發(fā)的時(shí)間同步算法

唐 波,孫 超,彭 力

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122) E-mail:tangb1992@foxmail.com

1 引 言

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)具有廉價(jià)、能量有限和無線通信等特點(diǎn),節(jié)點(diǎn)的信息交互、數(shù)據(jù)分析都與時(shí)間順序信息密切相關(guān),涉及到的應(yīng)用包括定位、休眠以及數(shù)據(jù)融合等,因此時(shí)間同步技術(shù)是無線傳感器網(wǎng)絡(luò)中的一項(xiàng)基礎(chǔ)支撐技術(shù)[1].隨著研究的深入,提出的算法從集中式[2]的算法如RBS(Reference-Broadcast Synchronization)算法和TPSN算法(Timing-sync Protocol for Sensor Networks)演變到分布式[3]的GCS(Global Clock Synchronization)算法、ATS(Average TimeSync)算法以及Gossip算法,近年來時(shí)間同步的研究熱點(diǎn)從提高同步算法的精度延伸的同步服務(wù)的性能方面.

分布式時(shí)間同步算法強(qiáng)調(diào)參考節(jié)點(diǎn)無關(guān)性,每個(gè)節(jié)點(diǎn)利用與周圍鄰居節(jié)點(diǎn)的消息交換,進(jìn)而實(shí)現(xiàn)全網(wǎng)的時(shí)間同步.在分布式算法中,迭代輪次的控制通常根據(jù)設(shè)定好的時(shí)間間隔依次執(zhí)行,雖然傳感器節(jié)點(diǎn)的時(shí)鐘頻率不一致,但是執(zhí)行同步過程是有序執(zhí)行的,這樣保證能實(shí)現(xiàn)一致性.在上述分布式同步的過程中,每個(gè)節(jié)點(diǎn)按照一定的時(shí)間間隔詢問周圍節(jié)點(diǎn)的時(shí)間信息并更新自身的時(shí)間,這樣的過程重復(fù)若干次之后全網(wǎng)節(jié)點(diǎn)的時(shí)間達(dá)到同步.分布式時(shí)間同步算法有效地提高了算法的可擴(kuò)展性和魯棒性,但是明顯會(huì)帶來通信量的增加,并且隨著精度要求越高、網(wǎng)絡(luò)規(guī)模越來越大,能耗會(huì)顯著增加.

事件的概念由來已久,最早在控制系統(tǒng)中事件指代實(shí)際的輸入、輸出和期望的輸入、輸出的不同.文獻(xiàn)[4]提出的事件觸發(fā)控制系統(tǒng)中控制輸入只在狀態(tài)量超過某個(gè)閾值的時(shí)候加入,基于這樣的設(shè)計(jì)使得控制器具有更少的狀態(tài)變化.文獻(xiàn)[5]提出了一種能有效減少反饋通信的事件觸發(fā)控制器,事件觸發(fā)器負(fù)責(zé)狀態(tài)值的采樣更新,使得系統(tǒng)能夠有效的節(jié)省資源尤其是通訊資源.基于分布式算法的現(xiàn)狀和事件觸發(fā)的應(yīng)用,事件觸發(fā)方式的時(shí)間同步算法被提了出來,這種算法執(zhí)行同步先后順序不依賴各個(gè)節(jié)點(diǎn)的時(shí)鐘快慢和同步間隔,而是依賴于指定的事件,進(jìn)一步的說依賴于閾值,各個(gè)節(jié)點(diǎn)在閾值被滿足時(shí)觸發(fā)自身時(shí)間同步過程,通過這種方式可以有效的降低時(shí)間同步算法執(zhí)行的次數(shù)即通信量的降低.文獻(xiàn)[6]提出的事件驅(qū)動(dòng)時(shí)間同步算法在分布式算法的基礎(chǔ)上,針對(duì)虛擬時(shí)鐘模型的漂移量補(bǔ)償更新和偏移量補(bǔ)償更新加上事件驅(qū)動(dòng)模型,有效的降低了同步算法同步消息交換的次數(shù),并且實(shí)現(xiàn)了虛擬時(shí)鐘的同步.文獻(xiàn)[7]提出的算法將時(shí)間同步過程看成二階狀態(tài)模型并設(shè)計(jì)了事件觸發(fā)函數(shù),通過理論和仿真實(shí)驗(yàn)證明了算法的有效性.

本文研究了基于事件觸發(fā)的時(shí)間同步算法,針對(duì)絕對(duì)時(shí)間的更新加上事件觸發(fā)策略,同時(shí)對(duì)事件觸發(fā)函數(shù)的設(shè)計(jì)做了改進(jìn),提出了一種簡單的基于事件觸發(fā)的時(shí)間同步算法,通過理論和仿真實(shí)驗(yàn)證明了算法的有效性和優(yōu)勢.

2 事件觸發(fā)基礎(chǔ)知識(shí)

為了更好的理解事件觸發(fā)機(jī)制,本節(jié)主要介紹在多智能體領(lǐng)域內(nèi)事件觸發(fā)機(jī)制的應(yīng)用作為基礎(chǔ)知識(shí).

針對(duì)一階多智能體系統(tǒng),智能體i的動(dòng)態(tài)方程如下

(1)

其中xi(t)表示智能體i的狀態(tài),ui(t)表示智能體i的控制輸入.考慮如下簡單的控制輸入

(2)

類似于Tabuadad[8]的思想,對(duì)每個(gè)多智能體引入一個(gè)狀態(tài)測量誤差ei(t),那么整個(gè)系統(tǒng)的狀態(tài)測量誤差向量為e(t)=(e1(t),e2(t),…,en(t))T,事件觸發(fā)的具體時(shí)間由下式(3)決定.

f(e(t))=0

(3)

根據(jù)事件觸發(fā)函數(shù)可以得到一系列時(shí)間觸發(fā)時(shí)刻{tk},k=0,1,…,在每個(gè)觸發(fā)時(shí)刻均有f(e(tk))=0,k=0,1,…,對(duì)應(yīng)的控制輸入為u(t0),u(t1),….當(dāng)事件觸發(fā)時(shí)更新控制輸入,兩個(gè)觸發(fā)事件中間的控制輸入不變,滿足下式(4).

u(t)=u(tk)t∈[tk,tk+1),k=0,1,…

(4)

系統(tǒng)狀態(tài)測量誤差具體的定義如下

e(t)=x(tk)-x(t)t∈[tk,tk+1),k=0,1,…

(5)

再由式(2)可知,實(shí)際的事件觸發(fā)下的控制輸入如下

(6)

其向量形式為

u(t)=-Lx(tk)t∈[tk,tk+1)

(7)

其中L表示網(wǎng)絡(luò)拓?fù)涞睦绽咕仃?那么系統(tǒng)的閉環(huán)形式如下

(8)

(9)

對(duì)式(9)選取李雅普諾夫函數(shù)證明穩(wěn)定性,并由此推導(dǎo)得到滿足系統(tǒng)穩(wěn)定性的事件觸發(fā)函數(shù).證明推導(dǎo)過程見文獻(xiàn)[10],求得的觸發(fā)函數(shù)如下

(10)

其中λ2(L)表示圖對(duì)應(yīng)的拉普拉斯陣的第二小特征值.從式(10)我們看出事件觸發(fā)函數(shù)中需要知曉圖拉普拉斯陣的特征值和分歧向量,所以這種觸發(fā)方式也被稱為集中式事件觸發(fā)方式.

3 事件觸發(fā)在時(shí)間同步中的應(yīng)用

由第2節(jié)關(guān)于事件驅(qū)動(dòng)機(jī)制的介紹我們了解了事件觸發(fā)的控制輸入、測量誤差和觸發(fā)函數(shù)等基本知識(shí).在多智能體系統(tǒng)中基于連續(xù)時(shí)間系統(tǒng)的事件觸發(fā)算法[5]與時(shí)間同步迭代算法離散時(shí)間模型不符合,因?yàn)閷?duì)于時(shí)間同步算法而言理想時(shí)間是未知的,也不能直接使用.文獻(xiàn)[11]的多智能體事件觸發(fā)雖然是基于離散時(shí)間模型,但是觸發(fā)函數(shù)是集中式的對(duì)于分布式時(shí)間同步算法而言不適用.文獻(xiàn)[12]提出的多智能體采樣事件觸發(fā)算法有適用時(shí)間同步算法的觸發(fā)函數(shù),但是采樣的假設(shè)前提是多智能體具有相同的時(shí)間系統(tǒng).綜上所述雖然事件觸發(fā)算法應(yīng)用廣泛,但是對(duì)于時(shí)間同步而言適用性不強(qiáng).

文獻(xiàn)[6]最早提出了基于事件觸發(fā)的時(shí)間同步算法,文獻(xiàn)[7]提出了基于二階狀態(tài)模型的時(shí)間同步算法.本章提出的算法在這兩篇文獻(xiàn)的基礎(chǔ)上,受文獻(xiàn)[5]提出的觸發(fā)函數(shù)啟發(fā),提出了一種針對(duì)絕對(duì)時(shí)間的基于事件觸發(fā)的時(shí)間同步算法,算法折中了時(shí)變觸發(fā)函數(shù)和固定閾值觸發(fā)函數(shù),有效的避免了固定閾值觸發(fā)函數(shù)前期頻繁觸發(fā)和時(shí)變觸發(fā)函數(shù)后期頻繁觸發(fā)的負(fù)面影響.

圖1 分布式和事件觸發(fā)式時(shí)間同步示意圖Fig.1 Distributed and event triggering time synchronization diagram

類似文獻(xiàn)[6]的事件觸發(fā)策略,本章提出事件觸發(fā)機(jī)制如圖1(b)所示,圖1(a)表示一致性時(shí)間同步示意圖,按照各個(gè)節(jié)點(diǎn)的同步周期進(jìn)行絕對(duì)時(shí)間的更新和擴(kuò)散操作,圖1(b)表示本章的事件觸發(fā)事件同步示意圖,在各個(gè)節(jié)點(diǎn)的第一個(gè)同步周期進(jìn)行絕對(duì)時(shí)間的更新和擴(kuò)散操作,在接下來的時(shí)間里按照同步周期進(jìn)行絕對(duì)時(shí)間的更新操作,按照事件觸發(fā)函數(shù)進(jìn)行絕對(duì)時(shí)間的擴(kuò)散操作.這里指的擴(kuò)散和廣播、消息交換指的同一個(gè)概念.為了更好的說明同步算法,假設(shè)本地時(shí)鐘的更新對(duì)絕對(duì)時(shí)間沒有影響,也就是說在整個(gè)時(shí)間同步算法執(zhí)行開始到實(shí)現(xiàn)時(shí)間同步,絕對(duì)時(shí)間不是連續(xù)的.

3.1 絕對(duì)時(shí)間更新模型及事件觸發(fā)函數(shù)設(shè)計(jì)

對(duì)節(jié)點(diǎn)i,假設(shè)節(jié)點(diǎn)的絕對(duì)時(shí)間更新時(shí)刻為k,k=1,2,…,事件觸發(fā)的絕對(duì)時(shí)間擴(kuò)散時(shí)刻為kl,l=1,2,…,kl集合是k集合的子集,每個(gè)節(jié)點(diǎn)的第一次更新時(shí)刻和觸發(fā)時(shí)刻重合.設(shè)節(jié)點(diǎn)i的絕對(duì)時(shí)間為τi,類似文獻(xiàn)[11]的狀態(tài)更新模型,絕對(duì)時(shí)間更新如下：

(11)

其中ε∈(0,1/Δ)為統(tǒng)一權(quán)重常數(shù),Δ為節(jié)點(diǎn)的最大度.記測量誤差ei(k)=τi(kl)-τi(k),絕對(duì)時(shí)間擴(kuò)散的事件觸發(fā)函數(shù)如下：

fi(ei(k))=δk+ξ=0,δ∈(0,1)

(12)

其中δ表示0到1之間的常數(shù);ξ表示與絕對(duì)時(shí)間同步精度相關(guān)的常數(shù),數(shù)量級(jí)為同步精度要求的數(shù)量級(jí).

記τ(k)=(τ1(k),…,τn(k))T,τ(kl)=(τ1(kl),…,τn(kl))T,e(k)=(e1(k),…en(k)),那么式(11)可寫成如下形式：

τ(k+1)=τ(k)-εLτ(kl)=τ(k)-εL(e(k)+τ(k))=

(I-εL)τ(k)-εLe(k)

(13)

類似文獻(xiàn)[9]將式(13)中的I-εL看成具有ε參數(shù)的培龍矩陣P,經(jīng)過M次更新之后絕對(duì)時(shí)間表達(dá)式如下：

(14)

與文獻(xiàn)[6]證明過程類似,需要用到的定義和引理如下：

定義1[13].對(duì)于隨機(jī)矩陣F∈n×n,矩陣的遍歷性系數(shù)(Coefficient of Ergodicity)為

引理1[13].對(duì)向量υ∈n,S(υ)定義為向量υ中元素的最大差值,S(υ)=maxi,j|υi-υj|,且S(υ)具有如下加性和乘性的性質(zhì)

1.對(duì)向量υ和ω,S(υ+ω)≤S(υ)+S(ω)

2.對(duì)隨機(jī)矩陣F和向量υ,S(Fυ)≤γ(F)S(υ)

證明過程如下,對(duì)式(14)求取向量元素的最大差值得到

(15)

其中S(PMτ(0))部分,根據(jù)培龍矩陣P的性質(zhì)和文獻(xiàn)[9]的證明可知,S(PMτ(0))=0,M→∞.再根據(jù)S(εLe(q))≤2ε‖Le(q)‖∞≤4εΔ‖e(q)‖∞,結(jié)合公式(12)事件觸發(fā)函數(shù)得到S(εLe(q))≤4εΔ(δq+ξ),當(dāng)q→∞時(shí),S(εLe(q))→4εΔξ.根據(jù)這兩部分,式(15)的極限進(jìn)一步放縮如下

(16)

根據(jù)文獻(xiàn)[6]可知γ(P)∈(0,1),那么

(17)

3.2 仿真實(shí)驗(yàn)

使用Matlab進(jìn)行仿真實(shí)驗(yàn),傳感器節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)為環(huán)形拓?fù)浣Y(jié)構(gòu),節(jié)點(diǎn)的數(shù)量為8個(gè),如圖2所示.

如圖3(a)所示時(shí)間觸發(fā)下的絕對(duì)時(shí)間值隨著更新次數(shù)的增加趨于一致;圖3(b)展示了各個(gè)節(jié)點(diǎn)廣播自身絕對(duì)時(shí)間值的時(shí)刻,從圖中可以看出廣播時(shí)刻密集,引起大量的通信消耗.

圖2 8節(jié)點(diǎn)環(huán)形拓?fù)涫疽鈭DFig.2 8-node ring topology diagram

圖3 時(shí)間觸發(fā)下絕對(duì)時(shí)間狀態(tài)圖和節(jié)點(diǎn)的廣播時(shí)刻圖Fig.3 Absolute time state and the node′s broadcast time diagram under time triggerring

相比于圖3(a),圖4(a)在更新次數(shù)靠前的時(shí)刻存在較大震蕩,但是絕對(duì)時(shí)間也是收斂的.時(shí)間觸發(fā)方式在第68次更新時(shí)達(dá)到同步精度要求,事件觸發(fā)方式在第67次更新時(shí)達(dá)到同步精度要求.對(duì)比圖3(b)和圖4(b)可知,以事件觸發(fā)方式廣播絕對(duì)時(shí)間實(shí)現(xiàn)同步的方式具有更少的廣播時(shí)刻,也就意味著是節(jié)省能量的.說明了針對(duì)絕對(duì)時(shí)間以指數(shù)函數(shù)和固定閾值的和作為觸發(fā)函數(shù)的時(shí)間同步算法的可行性和節(jié)省能量的優(yōu)勢.

圖4 事件觸發(fā)下絕對(duì)時(shí)間狀態(tài)圖和節(jié)點(diǎn)的廣播時(shí)刻圖Fig.4 Absolute time state and the node′s broadcast time diagram under event triggerring

將文獻(xiàn)[6]提出的時(shí)變閾值算法觸發(fā)函數(shù)和固定閾值觸發(fā)函數(shù)用本文的簡化模型做對(duì)比,如圖5(a)和圖5(b)所示.對(duì)比圖4(b)和圖5(a)、圖5(b)可見,本章提出的觸發(fā)函數(shù)取得了折中的效果,避免了前期頻繁觸發(fā)和后期頻繁觸發(fā)的負(fù)面影響,在絕對(duì)時(shí)間廣播時(shí)刻上分布更加均勻,相比兩者來說取得了更少的廣播次數(shù),為時(shí)間同步算法節(jié)省了能量消耗.

4 結(jié)束語

本文研究了一種基于事件觸發(fā)的時(shí)間同步算法.為了減少分布式時(shí)間同步算法在迭代過程中大量通信廣播帶來的能量消耗,將事件的概念引入時(shí)間同步算法中.提出的算法利用事件觸發(fā)的方式取代時(shí)間間隔觸發(fā)同步消息廣播的方式,改進(jìn)了觸發(fā)函數(shù),在保證分布式同步算法的收斂性的同時(shí)避免了同步消息廣播的頻繁觸發(fā),降低了同步算法通信能量消耗.

圖5 時(shí)變閾值算法和固定閾值算法絕對(duì)時(shí)間廣播時(shí)刻示意圖Fig.5 Node′s broadcast time diagram under time varying threshold and fixed threshold

[1] Swain A R,Hansdah R C.A model for the classification and survey of clock synchronization protocols in WSNs[J].Ad Hoc Networks,2015,27(C):219-241.

[2] Benza?d C,Bagaa M,Younis M.Efficient clock synchronization for clustered wireless sensor networks[J].Ad Hoc Networks,2016,56(C):13-27.

[3] Luo B,Cheng L,Wu Y C.Fully distributed clock synchronization in wireless sensor networks under exponential delays[J].Signal Processing,2016,125(C):261-273.

[4] Astrom K J,Bernhardsson B M.Comparison of riemann and lebesgue sampling for first order stochastic systems[C].The 41st IEEE Conference on Decision and Control,2002:2011-2016.

[5] Seyboth G,Dimarogonas D V,Johansson K H.Control of multi-agent systems via event-based communication[C].Proc.Ifac World Congress,2011:10086-10091.

[6] Kadowaki Y,Ishii H.Event-based distributed clock synchronization for wireless sensor networks[C].IEEE Conference on Decision and Control,2013:6747-6752.

[7] Chen Z,Li D,Huang Y,et al.Event-triggered communication for distributed time synchronization in WSNs[C].Chinese Control Conference,2015:7789-7794.

[8] Tabuada P.Event-triggered real-time scheduling of stabilizing control tasks[J].IEEE Transactions on Automatic Control,2007,52(9):1680-1685.

[9] Olfati-Saber R,Murray R M.Consensus problems in networks of agents with switching topology and time-delays[J].IEEE Transactions on Automatic Control,2004,49(9):1520-1533.

[10] Zhou Y,Hu J.Event-based bipartite consensus on signed networks[C].IEEE International Conference on Cyber Technology in Automation Control and Intelligent Systems,2013:326-330.

[11] Chen X,Hao F.Event-triggered average consensus control for discrete-time multi-agent systems[J].Iet Control Theory & Applications,2012,6(16):2493-2498.

[12] Cao J,Wu Z,Peng L.Distributed event-triggered average consensus of multi-agent systems[J].International Journal of Computer Science,2015,10(3):5-11.

[13] Hartfiel D J.Markov set-chains[M].Heidelberg:Springer,1998.