郝創(chuàng)博 宋 萍 楊 誠(chéng) 武江鵬

?

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

郝創(chuàng)博 宋 萍*楊 誠(chéng) 武江鵬

(北京理工大學(xué)仿生機(jī)器人與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100081)

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

無(wú)線傳感器網(wǎng)絡(luò)；分布式時(shí)間同步；局部同步問題；多相位粒度

1 引言

時(shí)間同步在無(wú)線傳感器網(wǎng)絡(luò)中得到廣泛應(yīng)用。它為無(wú)線傳感器網(wǎng)絡(luò)提供了統(tǒng)一的時(shí)間基準(zhǔn)，對(duì)無(wú)線測(cè)試數(shù)據(jù)時(shí)間相關(guān)性建立以及分時(shí)休眠等技術(shù)具有至關(guān)重要的作用。其作為無(wú)線傳感器網(wǎng)絡(luò)中研究熱點(diǎn)之一，一直備受關(guān)注。在早期研究中，時(shí)間同步僅僅是主從關(guān)系之間的時(shí)間信息交換。這種分層形式的同步算法可在簡(jiǎn)單的星形拓?fù)浣Y(jié)構(gòu)中取得良好的同步效果，但在復(fù)雜的網(wǎng)絡(luò)中常常具有可擴(kuò)展性差，魯棒性差，同步誤差隨路由跳數(shù)增加而累積，同步路由建立復(fù)雜等缺點(diǎn)。

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

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

2 預(yù)備知識(shí)

2.1 CHARLES模型

CHARLES針對(duì)心肌細(xì)胞的同步跳動(dòng)進(jìn)行分析，將每個(gè)心肌細(xì)胞看作為一個(gè)電路中的RC振蕩器，并將其自由狀態(tài)和耦合狀態(tài)分別建立數(shù)學(xué)模型[6]。

在自由狀態(tài)時(shí)，振動(dòng)器以如下速度進(jìn)行充電：

在耦合狀態(tài)下，當(dāng)一個(gè)振蕩器的電容放電時(shí)，會(huì)與其他阻容振蕩器之間電耦合，從而把其他振蕩器的電容電壓提升一個(gè)很小的增量，而正是這種耦合的作用，使得振蕩器的電容電壓趨于相同，最終達(dá)到同時(shí)放電狀態(tài)。即

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

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

(4)

最終，MIROLLO與STROGATZ證明了在無(wú)延時(shí)全連接網(wǎng)絡(luò)下該耦合方式可以使任意初始狀態(tài)的網(wǎng)絡(luò)同步。

3 多相位粒度建模

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

(7)

(9)

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

為了簡(jiǎn)化模型，方便在各個(gè)相位空間中進(jìn)行同步，設(shè)每一級(jí)相位粒度是下級(jí)的倍。故有

(13)

(15)

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

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

(17)

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

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

整個(gè)同步算法主要分為3個(gè)任務(wù)：離散相位值自增長(zhǎng)，節(jié)點(diǎn)發(fā)送同步報(bào)文，同步報(bào)文的處理。

4.1離散相位值的自增長(zhǎng)

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

圖1 各相位空間中的相位自增長(zhǎng)

4.2同步報(bào)文發(fā)送

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

需要注意的是，當(dāng)網(wǎng)絡(luò)接近同步時(shí)，節(jié)點(diǎn)在很多的時(shí)間內(nèi)需要廣播大量同步報(bào)文，容易造成網(wǎng)絡(luò)擁堵。因此在節(jié)點(diǎn)觸發(fā)后，在應(yīng)用層上為每個(gè)同步報(bào)文設(shè)置一個(gè)隨機(jī)長(zhǎng)度的避讓時(shí)間，并將該避讓時(shí)間寫入同步報(bào)文中。由于無(wú)線網(wǎng)絡(luò)通信中，節(jié)點(diǎn)發(fā)出在MAC層上普遍采用CSMA/CA的沖突避免機(jī)制，為了可以準(zhǔn)確獲取節(jié)點(diǎn)的觸發(fā)時(shí)刻信息，需要將CSMA/CA所產(chǎn)生的避讓時(shí)間同樣寫入同步報(bào)文中。

4.3同步報(bào)文處理

節(jié)點(diǎn)在同步過(guò)程中接收鄰居節(jié)點(diǎn)發(fā)送的同步報(bào)文，并在各個(gè)空間進(jìn)行耦合同步處理是整個(gè)同步算法的核心。為方便說(shuō)明，我們假設(shè)節(jié)點(diǎn)收到了節(jié)點(diǎn)發(fā)送的同步報(bào)文，則處理過(guò)程如下：

為了方便表示和計(jì)算，將節(jié)點(diǎn)的真實(shí)相位值使用多相位粒度表示，根據(jù)式(13) 可知：

(19)

(4)對(duì)各級(jí)離散相位值進(jìn)行耦合。在第(3)步中通過(guò)式(19)，將每個(gè)相位粒度對(duì)應(yīng)的相位值變?yōu)榱炕?jí)數(shù)同為，真實(shí)相位周期不同的相位空間。將各級(jí)離散相位值按照式(17)所規(guī)定的耦合動(dòng)態(tài)方程進(jìn)行耦合，并將計(jì)算出的各級(jí)狀態(tài)空間的相位值調(diào)整量應(yīng)用于原節(jié)點(diǎn)相位矩陣中，過(guò)程如下：

(22)

(23)

4.4同步穩(wěn)定性分析

類似于文獻(xiàn)[16]中的穩(wěn)定性證明，由第3節(jié)建模過(guò)程可知，該算法模型將其映射至多維馬氏鏈，算法的運(yùn)行過(guò)程相當(dāng)于馬氏鏈的狀態(tài)轉(zhuǎn)移過(guò)程。馬氏鏈中的各個(gè)狀態(tài)空間用集合表示，該狀態(tài)空間中的每個(gè)元素由各節(jié)點(diǎn)狀態(tài)的多粒度狀態(tài)矩陣組成。設(shè)表示馬爾可夫鏈的轉(zhuǎn)移概率矩陣。當(dāng)網(wǎng)絡(luò)強(qiáng)連通且節(jié)點(diǎn)數(shù)有限時(shí)，狀態(tài)空間為有限狀態(tài)空間，算法迭代映射到馬氏鏈?zhǔn)怯邢薏豢杉s遍歷鏈。設(shè)為該馬氏鏈中的唯一穩(wěn)態(tài)分布。根據(jù)馬氏鏈的相關(guān)理論可知，存在轉(zhuǎn)移次數(shù)，使，且。由式(24)可知[16]，穩(wěn)態(tài)為馬氏鏈吸收態(tài)，隨著算法迭代，使其他節(jié)點(diǎn)的多粒度狀態(tài)矩陣趨于同步，最終達(dá)到穩(wěn)定。

而根據(jù)馬氏鏈?zhǔn)諗織l件可知，該算法適用于有限節(jié)點(diǎn)數(shù)目的強(qiáng)連接網(wǎng)絡(luò)，即對(duì)于網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)可以通過(guò)直接或多跳的方式進(jìn)行消息傳遞。

5 仿真驗(yàn)證

本節(jié)中將對(duì)上文介紹的多粒度同步算法進(jìn)行仿真，為了說(shuō)明該算法在穩(wěn)定性和收斂速度方面所做的貢獻(xiàn)，文中同時(shí)對(duì)傳統(tǒng)的M&S PCO螢火蟲同步模型(下文簡(jiǎn)稱M&S算法)進(jìn)行仿真作為對(duì)比，并以MCU為平臺(tái)，模擬執(zhí)行兩種算法，對(duì)比其執(zhí)行時(shí)間，確定算法的執(zhí)行效率。

5.1 仿真條件

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

圖2 節(jié)點(diǎn)分布網(wǎng)絡(luò)及初始化相位

在傳統(tǒng)模型中，我們采用M&S算法，使用文獻(xiàn)[7]中的相位模型對(duì)網(wǎng)絡(luò)進(jìn)行同步，仿真實(shí)驗(yàn)中采用大小兩組耦合系數(shù)，分別為0.001和0.01；在多粒度同步算法中，節(jié)點(diǎn)的相位粒度分為3級(jí)，量化級(jí)數(shù)分別為：50, 2500, 125000。

5.2仿真結(jié)果

5.2.1分組效果

圖3和圖4表示同步過(guò)程穩(wěn)定后(仿真時(shí)間的最后15 s)的節(jié)點(diǎn)相位細(xì)節(jié)。從圖3 (a)中可看出耦合系數(shù)0.001的傳統(tǒng)算法收斂后，全部節(jié)點(diǎn)大體分為3組，3組之間的相位差有輕微抖動(dòng)。當(dāng)耦合系數(shù)增大至0.01后，從圖3(b)中可以明顯看出分組的組數(shù)減少，但是每一組中相位誤差變大相位差的抖動(dòng)較劇烈。由此可知在傳統(tǒng)的M&S算法在耦合系數(shù)的大小決定了同步效果，當(dāng)耦合系數(shù)較大時(shí)，同步分組現(xiàn)象得到緩解，但同步精度較差相位抖動(dòng)明顯。而耦合系數(shù)較小時(shí)，網(wǎng)絡(luò)呈現(xiàn)局部收斂，分組現(xiàn)象嚴(yán)重。圖4為使用多粒度同步算法的收斂后的各節(jié)點(diǎn)相位。可見該算法可以很好地解決分組現(xiàn)象并且相位同步精度較高，各節(jié)點(diǎn)的相位抖動(dòng)不嚴(yán)重，整體取得了較好的同步效果。

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

5.2.2同步精度和速度

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

圖5 同步精度圖

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

5.2.3算法執(zhí)行效率

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

圖6 表征各算法運(yùn)算速度的IO電平波形

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

分布式時(shí)間同步技術(shù)具有可擴(kuò)展性強(qiáng)，魯棒性強(qiáng)等特點(diǎn)，是無(wú)線傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)。本文提出了一種多相位粒度螢火蟲時(shí)間同步算法，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證。結(jié)果表明該算法有效解決了傳統(tǒng)分布式時(shí)間同步中的分組現(xiàn)象和同步速度較慢的問題，并且提高了同步算法的執(zhí)行效率。我們將在后續(xù)工作中進(jìn)一步解決分布式算法中的通信擁堵問題，并進(jìn)一步提高能量效率，使之成為更加實(shí)用的分布式同步算法。

[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] 李立, 劉勇攀, 楊華中, 等. 無(wú)線傳感器網(wǎng)絡(luò)分布式一致時(shí)間同步協(xié)議的收斂分析及加速設(shè)計(jì)[J]. 電子與信息學(xué)報(bào), 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

國(guó)家自然科學(xué)基金(61202433)

The National Natural Science Foundation of China (61202433)

宋萍 sping2002@bit.edu.cn

郝創(chuàng)博： 男，1989年生，博士生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò).

宋 萍： 女，1972年生，教授，研究方向?yàn)閭鞲信c機(jī)電控制.

楊 誠(chéng)： 男，1988年生，博士生，研究方向?yàn)闇y(cè)控技術(shù).

武江鵬： 男，1987年生，博士生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò).