一種簡單的基于事件觸發的時間同步算法

唐 波,孫 超,彭 力

(江南大學 物聯網工程學院,江蘇 無錫 214122) E-mail:tangb1992@foxmail.com

1 引 言

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

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

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

本文研究了基于事件觸發的時間同步算法,針對絕對時間的更新加上事件觸發策略,同時對事件觸發函數的設計做了改進,提出了一種簡單的基于事件觸發的時間同步算法,通過理論和仿真實驗證明了算法的有效性和優勢.

2 事件觸發基礎知識

為了更好的理解事件觸發機制,本節主要介紹在多智能體領域內事件觸發機制的應用作為基礎知識.

針對一階多智能體系統,智能體i的動態方程如下

(1)

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

(2)

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

f(e(t))=0

(3)

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

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

(4)

系統狀態測量誤差具體的定義如下

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

(5)

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

(6)

其向量形式為

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

(7)

其中L表示網絡拓撲的拉普拉斯矩陣,那么系統的閉環形式如下

(8)

(9)

對式(9)選取李雅普諾夫函數證明穩定性,并由此推導得到滿足系統穩定性的事件觸發函數.證明推導過程見文獻[10],求得的觸發函數如下

(10)

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

3 事件觸發在時間同步中的應用

由第2節關于事件驅動機制的介紹我們了解了事件觸發的控制輸入、測量誤差和觸發函數等基本知識.在多智能體系統中基于連續時間系統的事件觸發算法[5]與時間同步迭代算法離散時間模型不符合,因為對于時間同步算法而言理想時間是未知的,也不能直接使用.文獻[11]的多智能體事件觸發雖然是基于離散時間模型,但是觸發函數是集中式的對于分布式時間同步算法而言不適用.文獻[12]提出的多智能體采樣事件觸發算法有適用時間同步算法的觸發函數,但是采樣的假設前提是多智能體具有相同的時間系統.綜上所述雖然事件觸發算法應用廣泛,但是對于時間同步而言適用性不強.

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

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

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

3.1 絕對時間更新模型及事件觸發函數設計

對節點i,假設節點的絕對時間更新時刻為k,k=1,2,…,事件觸發的絕對時間擴散時刻為kl,l=1,2,…,kl集合是k集合的子集,每個節點的第一次更新時刻和觸發時刻重合.設節點i的絕對時間為τi,類似文獻[11]的狀態更新模型,絕對時間更新如下：

(11)

其中ε∈(0,1/Δ)為統一權重常數,Δ為節點的最大度.記測量誤差ei(k)=τi(kl)-τi(k),絕對時間擴散的事件觸發函數如下：

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

(12)

其中δ表示0到1之間的常數;ξ表示與絕對時間同步精度相關的常數,數量級為同步精度要求的數量級.

記τ(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)

類似文獻[9]將式(13)中的I-εL看成具有ε參數的培龍矩陣P,經過M次更新之后絕對時間表達式如下：

(14)

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

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

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

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

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

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

(15)

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

(16)

根據文獻[6]可知γ(P)∈(0,1),那么

(17)

3.2 仿真實驗

使用Matlab進行仿真實驗,傳感器節點的拓撲結構為環形拓撲結構,節點的數量為8個,如圖2所示.

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

圖2 8節點環形拓撲示意圖Fig.2 8-node ring topology diagram

圖3 時間觸發下絕對時間狀態圖和節點的廣播時刻圖Fig.3 Absolute time state and the node′s broadcast time diagram under time triggerring

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

圖4 事件觸發下絕對時間狀態圖和節點的廣播時刻圖Fig.4 Absolute time state and the node′s broadcast time diagram under event triggerring

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

4 結束語

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

圖5 時變閾值算法和固定閾值算法絕對時間廣播時刻示意圖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.