多相位粒度螢火蟲同步算法

郝創博 宋 萍 楊 誠 武江鵬

?

多相位粒度螢火蟲同步算法

郝創博 宋 萍*楊 誠 武江鵬

(北京理工大學仿生機器人與系統教育部重點實驗室 北京 100081)

該文針對分布式時間同步算法中，低耦合系數的分組同步問題和大耦合系數的相位振蕩失穩現象，提出一種多粒度一致分布式時間同步算法，采用離散多相位粒度模型，將報文交換的相位信息采用多個相位分辨力進行耦合同步，有效地減少了分組現象，加快了同步進程，并提高了算法的執行效率。最后利用仿真實驗和傳統的M&S仿生算法進行對比實驗，驗證了其在非全連接網絡中，可以取得比傳統算法更好的同步效果。

無線傳感器網絡；分布式時間同步；局部同步問題；多相位粒度

1 引言

時間同步在無線傳感器網絡中得到廣泛應用。它為無線傳感器網絡提供了統一的時間基準，對無線測試數據時間相關性建立以及分時休眠等技術具有至關重要的作用。其作為無線傳感器網絡中研究熱點之一，一直備受關注。在早期研究中，時間同步僅僅是主從關系之間的時間信息交換。這種分層形式的同步算法可在簡單的星形拓撲結構中取得良好的同步效果，但在復雜的網絡中常常具有可擴展性差，魯棒性差，同步誤差隨路由跳數增加而累積，同步路由建立復雜等缺點。

隨著時間同步技術的發展，人們從大自然中找到靈感，發明了一類分布式同步算法[4,5]。典型的模型和算法如文獻[6]針對心肌細胞的分布式同步跳動建立了一種脈沖耦合模型；文獻[7]在其基礎上針對螢火蟲的分布式同步閃爍建立了M&S 脈沖耦合動態學模型。文獻[8]等利用該模型發展為螢火蟲同步算法并運用于無線傳感器網絡時間同步?；诖祟惙植际綍r間同步算法的節點在網絡中的地位是對等的，它們利用其鄰居節點的時間或相位信息進行調整進而到達同步的目的。該同步機制和路由機制相互獨立，避免了主從關系算法的上述缺點。因此該算法具有抗毀傷性和魯棒性強，易擴展，多跳累積誤差小等特點，適合于大規模無線傳感器網絡。文獻[9]總結了分布式同步典型算法，并分析了延時，漂移，干擾等因素對其收斂的影響。最近，優化研究多圍繞分布式時間同步算法的穩定性，收斂速度和通信效率等方面開展。如文獻[10-12]使用特定的事件觸發來修正鄰居節點的相位信息，采用時間離散模型使用離散的數據包修正連續的本地時鐘，但沒有考慮延時與算法復雜度等實際問題。文獻[13-15]針對現實中的噪聲影響，提出具有穩定性和一定精度的同步算法，但是沒有避免非全連接中的分組現象對同步進程的阻礙。文獻[16]研究了非全連接網絡中，影響同步穩定性和速度的因素，并提出了一種通過改變鄰居節點數目來加速收斂的同步策略，僅僅只做了理想模型(無耦合延時)下的研究。目前這些研究僅針對時間離散相位連續的同步方式。時間離散相位連續的同步方式可以在一定程度上解決同步傳輸占用帶寬的問題，但會引入分組現象(局部同步現象)和標準時鐘漂移等問題[17]。目前針對時間和相位均離散的同步算法研究鮮有涉及。

針對連續相位模型的上述問題，本文提出一種多相位粒度螢火蟲同步算法，有別于文獻[10-16]中的離散時間連續相位模型，采用時間和相位離散的多相位空間耦合算法，在建模和算法設計中考慮延時、網絡連通性、算法復雜度實際問題，減少同步過程中的局部同步的半穩定狀態持續時間，有利于加速全局同步，解決分組現象，并且更適合在低性能MCU中運行，提高了算法執行效率。

2 預備知識

2.1 CHARLES模型

CHARLES針對心肌細胞的同步跳動進行分析，將每個心肌細胞看作為一個電路中的RC振蕩器，并將其自由狀態和耦合狀態分別建立數學模型[6]。

在自由狀態時，振動器以如下速度進行充電：

在耦合狀態下，當一個振蕩器的電容放電時，會與其他阻容振蕩器之間電耦合，從而把其他振蕩器的電容電壓提升一個很小的增量，而正是這種耦合的作用，使得振蕩器的電容電壓趨于相同，最終達到同時放電狀態。即

2.2 M&S螢火蟲模型及同步算法

MIROLLO與STROGATZ參考CHARLES模型，對螢火蟲的同步閃爍建模和同步算法研究，其與CHARLES模型的機理相同均采用振蕩器脈沖耦合(Pulse Coupling Oscillator, PCO)正反饋，并引入相位作為中間變量，建立振蕩器動態學模型(MIROLLO & STROGATZ 模型，M&S 模型)：

(4)

最終，MIROLLO與STROGATZ證明了在無延時全連接網絡下該耦合方式可以使任意初始狀態的網絡同步。

3 多相位粒度建模

螢火蟲同步數學模型M&S中的相位模型是連續的，適合于在模擬電路中通過硬件的方式實現同步，而在數字電路中通過邏輯判斷和計算實現螢火蟲分布式同步，需要將M&S模型中的相位離散化，從而簡化同步過程在MCU中的處理。本文所述相位粒度主要是指相位離散過程中量化的分辨率。由式(5)可知相位的觸發閾值為1，我們定義相位粒度為

(7)

(9)

由此可見，相位粒度越小，真實相位值的分布范圍越小，精度越高，反之分布范圍越大，精度就越低。較大的粒度導致量化級數較少，狀態空間的維數較小，有利于離散相位值的同步，但是會影響真實相位值的精度，反之，狀態空間的維數較大，不利于離散相位值的收斂。因此，本節提出一種多相位粒度模型，通過減少相位空間維數加快同步進程，減小分組的可能，同時提供真實相位值精度。

為了簡化模型，方便在各個相位空間中進行同步，設每一級相位粒度是下級的倍。故有

(13)

(15)

在耦合狀態下，由于相位的離散化，相位增長不連續，并且其增量必須為相位粒度的整數倍，為了保證式(3)中相位映射函數的凹函數特性，在多相位粒度模型中，各級相位粒度空間在耦合的向量增量為一個階梯遞增函數。在本文中，我們使用一個階躍函數進行簡化。即

故多相位粒度模型在耦合狀態下的動態方程如式(17)：

(17)

4 多相位粒度螢火蟲同步算法

第3節中介紹了節點的數學模型，本節提出一種多相位粒度螢火蟲同步算法(下文簡稱多粒度同步算法)，利用多相位粒度數學模型對任意初始化相位節點集進行同步，并對算法進行穩定性分析。

整個同步算法主要分為3個任務：離散相位值自增長，節點發送同步報文，同步報文的處理。

4.1離散相位值的自增長

節點在自由狀態下各級相位空間中的離散相位值按照式(15)的速度增長。不同于一般連續相位模型的是，多相位粒度的相位空間屬于離散空間，其相位的增長屬于階梯狀增長，如圖1所示為量化等級為4，相位周期為1 s的前3級相位空間相位的自增長情況。根據式(15)可知，需要每隔將節點第級的離散相位值加1。由于采用離散時間的相位自增長方式，不需要節點對相位信息進行實時更新，方便使用定時器實現，節約節點處理資源。

圖1 各相位空間中的相位自增長

4.2同步報文發送

模型采用離散時間模型的事件耦合方式，不需要節點之間連續的交換相位信息，減少了通信負荷。如RC振蕩器的脈沖耦合相同，由式(11)和式(15)可知，在多粒度的相位模型中，只要任意一級的離散相位值達到其對應的量化級數，則其余各級的相位值均達到對應的量化級數，此時節點觸發(相位達到閾值)，并向其鄰居節點發送同步報文。由于各級為同時達到閾值，故同步報文中暗含了各尺度相位空間中的相位信息，以便在各個相位尺度空間進行相位耦合。

需要注意的是，當網絡接近同步時，節點在很多的時間內需要廣播大量同步報文，容易造成網絡擁堵。因此在節點觸發后，在應用層上為每個同步報文設置一個隨機長度的避讓時間，并將該避讓時間寫入同步報文中。由于無線網絡通信中，節點發出在MAC層上普遍采用CSMA/CA的沖突避免機制，為了可以準確獲取節點的觸發時刻信息，需要將CSMA/CA所產生的避讓時間同樣寫入同步報文中。

4.3同步報文處理

節點在同步過程中接收鄰居節點發送的同步報文，并在各個空間進行耦合同步處理是整個同步算法的核心。為方便說明，我們假設節點收到了節點發送的同步報文，則處理過程如下：

為了方便表示和計算，將節點的真實相位值使用多相位粒度表示，根據式(13) 可知：

(19)

(4)對各級離散相位值進行耦合。在第(3)步中通過式(19)，將每個相位粒度對應的相位值變為量化級數同為，真實相位周期不同的相位空間。將各級離散相位值按照式(17)所規定的耦合動態方程進行耦合，并將計算出的各級狀態空間的相位值調整量應用于原節點相位矩陣中，過程如下：

(22)

(23)

4.4同步穩定性分析

類似于文獻[16]中的穩定性證明，由第3節建模過程可知，該算法模型將其映射至多維馬氏鏈，算法的運行過程相當于馬氏鏈的狀態轉移過程。馬氏鏈中的各個狀態空間用集合表示，該狀態空間中的每個元素由各節點狀態的多粒度狀態矩陣組成。設表示馬爾可夫鏈的轉移概率矩陣。當網絡強連通且節點數有限時，狀態空間為有限狀態空間，算法迭代映射到馬氏鏈是有限不可約遍歷鏈。設為該馬氏鏈中的唯一穩態分布。根據馬氏鏈的相關理論可知，存在轉移次數，使，且。由式(24)可知[16]，穩態為馬氏鏈吸收態，隨著算法迭代，使其他節點的多粒度狀態矩陣趨于同步，最終達到穩定。

而根據馬氏鏈收斂條件可知，該算法適用于有限節點數目的強連接網絡，即對于網絡中的任意兩個節點可以通過直接或多跳的方式進行消息傳遞。

5 仿真驗證

本節中將對上文介紹的多粒度同步算法進行仿真，為了說明該算法在穩定性和收斂速度方面所做的貢獻，文中同時對傳統的M&S PCO螢火蟲同步模型(下文簡稱M&S算法)進行仿真作為對比，并以MCU為平臺，模擬執行兩種算法，對比其執行時間，確定算法的執行效率。

5.1 仿真條件

文獻[7]中對M&S模型的論述基于全連接網絡條件，即網絡中每個節點可以與其他任意節點直接通信，但這往往與現實不符，因此本次仿真主要采用非全連接網絡進行仿真實驗，并于5.2.2節中增加多相位粒度算法在全連接網絡中應用的同步速度與精度說明。仿真實驗中的一些通用參數規定如下：整個網絡由20個節點組成，隨機分布在的區域中，節點的通信距離為450 m，節點所成無方向網絡圖如圖2(a)所示。節點的同步周期為1 s，初始相位如圖2(b)所示。從文獻[9]可知，時鐘漂移和傳輸延時在分布式網絡中對同步的影響是等效的。為了模擬實現中的時鐘漂移和延時，我們為節點的相位增長速度設置了1%的誤差(即每秒累積歸一化相位誤差為)。仿真的時間粒度為0.01 μs，仿真時長為100 s。

圖2 節點分布網絡及初始化相位

在傳統模型中，我們采用M&S算法，使用文獻[7]中的相位模型對網絡進行同步，仿真實驗中采用大小兩組耦合系數，分別為0.001和0.01；在多粒度同步算法中，節點的相位粒度分為3級，量化級數分別為：50, 2500, 125000。

5.2仿真結果

5.2.1分組效果

圖3和圖4表示同步過程穩定后(仿真時間的最后15 s)的節點相位細節。從圖3 (a)中可看出耦合系數0.001的傳統算法收斂后，全部節點大體分為3組，3組之間的相位差有輕微抖動。當耦合系數增大至0.01后，從圖3(b)中可以明顯看出分組的組數減少，但是每一組中相位誤差變大相位差的抖動較劇烈。由此可知在傳統的M&S算法在耦合系數的大小決定了同步效果，當耦合系數較大時，同步分組現象得到緩解，但同步精度較差相位抖動明顯。而耦合系數較小時，網絡呈現局部收斂，分組現象嚴重。圖4為使用多粒度同步算法的收斂后的各節點相位?？梢娫撍惴梢院芎玫亟鉀Q分組現象并且相位同步精度較高，各節點的相位抖動不嚴重，整體取得了較好的同步效果。

圖3 M&S算法同步分組情況???????????????????????? ????????????????圖4 多粒度同步算法同步分組情況

5.2.2同步精度和速度

圖5(a)表示網絡中任意兩個節點同步相位誤差的最大值，可看出無論采取何種耦合系數，傳統的M&S算法的同步精度均不及多粒度同步算法。這是由于在非全連接網絡中，M&S算法的分組同步現象導致。采用多粒度同步算法的仿真實驗，網絡的相位穩定后，歸一化相位誤差維持在0.025以下，并沒有受1%相位增長速度誤差的影響，達到了一定的同步效果。圖5(b)所示為同等實驗條件下去除相位增長速度誤差后或使用全連接網絡仿真理想情況的同步結果，其同步誤差均小于圖5(a)。對比圖5(a)和圖5(b)，得出圖5(a)所示多粒度同步算法收斂后的同步相位誤差是由每個節點的相位增長速度誤差引起，而增加網絡的連通性可以加速同步并在一定程度上減小這種誤差但不能根除。

圖5 同步精度圖

從圖5(a)中可以看出，多粒度同步算法的收斂速度與大耦合系數的M&S算法收斂相近，明顯快于小耦合系數的M&S算法。故多粒度同步算法有一定的加速收斂作用。

5.2.3算法執行效率

由于無線傳感器網絡中常常使用運算能力有限的低成本低功耗MCU，故算法的時間復雜度是決定算法使用性的關鍵。為此，我們利用ATMEL公司的ATMEGA256芯片模擬執行觸發程序100次，通過IO口的低電平時間表示觸發處理程序執行的時間。實驗結果如圖6，運行100次觸發算法，M&S算法耗時約為36.2 μs(如圖6(a))，多粒度同步算法耗時約為5.2 μs(如圖6(b))。從圖6(a)和圖6(b)對比中可以明顯看出多粒度同步算法具有更高的執行效率。

圖6 表征各算法運算速度的IO電平波形

6 結束語

分布式時間同步技術具有可擴展性強，魯棒性強等特點，是無線傳感器網絡中的關鍵技術。本文提出了一種多相位粒度螢火蟲時間同步算法，并通過仿真實驗驗證。結果表明該算法有效解決了傳統分布式時間同步中的分組現象和同步速度較慢的問題，并且提高了同步算法的執行效率。我們將在后續工作中進一步解決分布式算法中的通信擁堵問題，并進一步提高能量效率，使之成為更加實用的分布式同步算法。

[1] Elson J, Girod L, and Estrin D. Fine-grained network time synchronization using reference broadcasts[C]. The 2002 Usenix Symposium on Operating Systems Design and Implementation, Berkeley, CA, USA, 2002: 9-11.

[2] Ganeriwal S, Kumar R, and Srivastava M B. Timing-sync protocol for sensor networks[C]. SenSys’03: the First International Conference on Embedded Networked Sensor Systems, Los Angeles, CA, USA, 2003:138-149.

[3] Xu N, Zhang X, Wang Q,. An improved flooding time synchronization protocol for industrial wireless networks[C]. The 2009 International Conference on Embedded Software and Systems, Hangzhou, China, 2009: 524-529. doi:10.1109/ICESS.2009.10.

[4] Busch N E, Vinniche.N K, Waterman A T,. Waves and turbulence[J]., 1969, 4(12): 1377. doi: 10.1029/RS004i012p01377.

[5] Holden A V. From clocks to chaos - the rhythms of life - glass, L, mackey, MC[J]., 1988, 336(6195): 119. doi: 10.1038/336119a0.

[6] Peskin C S and Courant Institute of Mathematical Sciences. Mathematical Aspects of Heart Physiology[M]. New York, USA, New York: Courant Institute of Mathematical Sciences, 1975: 278.

[7] Mirollo R E and Strogatz S H. Synchronization of pulse-coupled biological oscillators[J]., 1990, 50(6): 1645-1662. doi: 10.1137/ 0150098.

[8] Hong Y W and Scaglione A. A scalable synchronization protocol for large scale sensor networks and its applications[J]., 2005, 23(5): 1085-1099.

[9] Simeone O, Spagnolini U, Bar-Ness Y,. Distributed synchronization in wireless networks[J]., 2008, 25(5): 81-97. doi: 10.1109/ MSP.2008.926661.

[10] Liu T, Cao M, and Hill D J. Distributed event-triggered control for output synchronization of dynamical networks with non-identical nodes[C]. The 2014 53rd IEEE Annual Conference on Decision and Control, Los Angeles, CA, USA, 2014: 3554-3559. doi: 10.1109/CDC.2014.7039941.

[11] Kadowaki Y and Ishii H. Event-based distributed clock synchronization for wireless sensor networks[J]., 2015, 60(8): 2266-2271.

[12] Sun W L, Strom E G, Brannstrom F,. Random broadcast based distributed consensus clock synchronization for mobile networks[J]., 2015, 14(6): 3378-3389.

[13] He J, Duan X, Cheng P,. Distributed time synchronization under bounded noise in wireless sensor networks[C]. The 2014 53rd IEEE Annual Conference on Decision and Control, Los Angeles, CA, USA, 2014: 6883-6888. doi: 10.1109/CDC.2014.7040470.

[14] Tang Y, Gao H, Lu J,. Pinning distributed synchronization of stochastic dynamical networks: A mixed optimization approach[J]., 2014, 25(10): 1804-1815. doi: 10.1109/TNNLS.2013.2295966.

[15] Xiao H, Isshiki T, Li D,. Distributed synchronization for message-passing based embedded multiprocessors[C]. The 25th IEEE International Conference on Application-Specific Systems, Architectures and Processors, Zurich, Switzerland, 2014:82-83. doi:10.1109/ASAP.2014.6868640.

[16] 李立, 劉勇攀, 楊華中, 等. 無線傳感器網絡分布式一致時間同步協議的收斂分析及加速設計[J]. 電子與信息學報, 2010, 32(9): 2045-2051. doi: 10.3724/SP.J.1146.2009.01234.

LI Li, LIU Yongpan, YANG Huazhong,. Convergence analysis and accelerating design for distributed consensus time synchronization protocol in wireless sensor networks[J].&, 2010, 32(9): 2045-2051. doi:10.3724/SP.J.1146.2009.01234.

[17] Kuramoto Y. Chemical Oscillations, Waves, and Turbulence [M]. Berlin, New York: Springer-Verlag, 1984: 156.

Firefly-inspired Synchronicity Algorithm Based on Multi Granularity Phase

HAO Chuangbo SONG Ping YANG Cheng WU Jiangpeng

(Key Laboratory of Biomimetic Robots and Systems, Beijing Institute of Technology, Beijing 100081, China)

Considering that conventional distributed synchronicity algorithm may lead to a state of partial synchronization separately with small couple coefficient or unsteadiness with large couple coefficient, a multi granularity firefly-inspired synchronicity algorithm is proposed. It lets the phase value couple in multi granularity by its divergence in time and phase, which can relieve the issue of partial synchronization and speed up the convergence process. Its performance is tested by simulation in a non-fully connect network by comparing with the conventional M&S algorithm. The result shows that it works better.

Wireless Sensor Network (WSN); Distributed synchronization; Partial synchronization; Multi granularity

TP393.0

A

1009-5896(2016)09-2208-07

10.11999/JEIT151395

2015-12-09；

2016-05-04；

2016-07-04

國家自然科學基金(61202433)

The National Natural Science Foundation of China (61202433)

宋萍 sping2002@bit.edu.cn

郝創博： 男，1989年生，博士生，研究方向為無線傳感器網絡.

宋 萍： 女，1972年生，教授，研究方向為傳感與機電控制.

楊 誠： 男，1988年生，博士生，研究方向為測控技術.

武江鵬： 男，1987年生，博士生，研究方向為無線傳感器網絡.