無(wú)線傳感器網(wǎng)絡(luò)中的螢火蟲(chóng)時(shí)間同步改進(jìn)模型

崔麗珍，曹 堅(jiān)，安竹林，李丹陽(yáng)，王巧利

1(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010) 2(中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190)

1 引 言

時(shí)間同步是無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)的一項(xiàng)支撐技術(shù)[1-3].對(duì)于WSN時(shí)間同步的研究，學(xué)者們提出了許多算法和協(xié)議[4-7]對(duì)該問(wèn)題進(jìn)行求解，當(dāng)這些時(shí)間同步算法和協(xié)議被擴(kuò)展到大規(guī)模網(wǎng)絡(luò)時(shí)，存在距離時(shí)間基準(zhǔn)節(jié)點(diǎn)跳距的增加，而發(fā)生同步過(guò)程中同步誤差的累積，且大量的計(jì)算和復(fù)雜的數(shù)據(jù)包交換，使得WSN在實(shí)際運(yùn)行中存在很大的負(fù)擔(dān).針對(duì)上述問(wèn)題學(xué)者們開(kāi)始利用自然界中的互同步現(xiàn)象來(lái)對(duì)WSN進(jìn)行時(shí)間同步的研究[8].

螢火蟲(chóng)同步是一種互同步現(xiàn)象，互相臨近的螢火蟲(chóng)通過(guò)脈沖形式的信號(hào)來(lái)相互傳遞信息，逐漸調(diào)整為同步閃爍的狀態(tài).螢火蟲(chóng)同步技術(shù)是解決WSN時(shí)間同步問(wèn)題的一種新型同步機(jī)制[9]，基于螢火蟲(chóng)同步技術(shù)的脈沖耦合器時(shí)間同步模型很好的應(yīng)用于WSN的時(shí)間同步中[10-13]，但大多算法模型忽略了負(fù)耦合強(qiáng)度在脈沖耦合同步過(guò)程中的作用.文獻(xiàn)[14]在耦合延遲固定下的脈沖耦合振蕩器系統(tǒng)的同步研究發(fā)現(xiàn)，只有負(fù)耦合才可能使系統(tǒng)取得同步.因此，本文提出了一種適用于WSN且具有抑制耦合的線性脈沖耦合振蕩器時(shí)間同步模型.該模型避免了傳統(tǒng)時(shí)間同步算法在多跳網(wǎng)絡(luò)中同步誤差積累的現(xiàn)象，并在無(wú)耦合時(shí)滯情況下，使用線性的狀態(tài)函數(shù)更符合WSN使用廉價(jià)單片機(jī)作為處理器的節(jié)點(diǎn)計(jì)算能力.引入負(fù)耦合因子，通過(guò)激勵(lì)與抑制相結(jié)合的相位耦合方式來(lái)縮短同步周期，提升全網(wǎng)絡(luò)的同步速度.

2 同步模型以及相關(guān)定義

2.1 模型描述

將每個(gè)傳感器節(jié)點(diǎn)看作為單個(gè)的脈沖振蕩器，可以周期性輸出脈沖信號(hào)作用在其它振蕩器上，該模型具有線性的狀態(tài)函數(shù)[15，16].對(duì)Peskin模型dx/dt=-λx+S0，令λ=0，S0=1/T，且t∈T〗，得到dx/dt=1/T，對(duì)此微分方程兩邊進(jìn)行積分得x=t/T，T為周期，φ=t/T為相位變量，得到狀態(tài)函數(shù)：

x=f(φ)=φ，φ∈1〗

(1)

用狀態(tài)變量x描述振蕩器，x在1〗上單調(diào)遞增，當(dāng)x到達(dá)閾值1時(shí)，振蕩器激發(fā)，并且x立即跳回0，產(chǎn)生耦合強(qiáng)度ε，正耦合強(qiáng)度ε>0，負(fù)耦合強(qiáng)度-ε<0.由于狀態(tài)和相位變量成線性關(guān)系，故使用φ統(tǒng)一表示.

在脈沖耦合振蕩器系統(tǒng)中，激發(fā)后的節(jié)點(diǎn)瞬間下跳到0產(chǎn)生耦合強(qiáng)度，改變其他節(jié)點(diǎn)的相位，文獻(xiàn)[17]證明了兩個(gè)振蕩器在同步演進(jìn)中，由于相位差的減小，從而實(shí)現(xiàn)完全同步.文獻(xiàn)[18]在脈沖耦合振蕩器網(wǎng)絡(luò)中實(shí)現(xiàn)了連續(xù)的相位演化，對(duì)脈沖耦合同步提供了嚴(yán)格的數(shù)學(xué)證明，分析了在相位連續(xù)性下達(dá)到同步的時(shí)間和同步收斂性.文獻(xiàn)[19]研究了任意相位初始條件演化到全局的脈沖耦合振蕩器同步方案.基于上述研究發(fā)現(xiàn)，在線性狀態(tài)函數(shù)下，存在負(fù)耦合強(qiáng)度的抑制作用，使得未同步的節(jié)點(diǎn)下降到0點(diǎn)后，同樣實(shí)現(xiàn)兩個(gè)振蕩器達(dá)到同步狀態(tài)，并可以提升同步收斂速度.同步模型如圖1所示，黑色圓圈表示振蕩器i，白色圓圈表示振蕩器j，分別處于不同的初始狀態(tài)φi和φj.在該模型中，將振蕩器的相位變量φ∈1〗以φ=1/2進(jìn)行區(qū)間劃分.隨著同步演進(jìn)過(guò)程中振蕩器相位的變化，當(dāng)某個(gè)振蕩器的相位在φ=1瞬間下跳到φ=0時(shí)產(chǎn)生耦合強(qiáng)度ε，使其他振蕩器的狀態(tài)變量提升或者下降ε.通過(guò)耦合互異的方式構(gòu)建出激勵(lì)耦合與抑制耦合，提升同步速度，該模型的動(dòng)態(tài)方程如式(2)所示.

(2)

圖1 相位同步過(guò)程圖

2.2 基本定義

定義1.基態(tài)GS(ground state)：

存在兩個(gè)振蕩器i和j，一個(gè)振蕩器在某次激發(fā)之后相位為0，另一個(gè)振蕩器的相位等于φ的狀態(tài).

相位φ區(qū)分在L1∈(0,1/2)和L2∈2,1)兩個(gè)區(qū)間，基態(tài)的四種存在形式和兩種表示方法如下：

GS1:φi,j=0,φj,i=φ,φ∈(0,1/2)

GS2:φj,i=0,φi,j=φ,φ∈2,1)

定義2.激發(fā)態(tài)fire(fire state)：

振蕩器相位φ=1時(shí)的狀態(tài).

φi,j=φ,φj,i=1,φ∈(0,1)

定義3.同步狀態(tài)Sync(Synchronization state)：

各個(gè)振蕩器的狀態(tài)和相位到達(dá)一致時(shí)的狀態(tài).

Sync:xi=xj=φi=φj=φ,φ∈1〗

3 兩個(gè)振蕩器同步

3.1 耦合方式

1)激勵(lì)耦合Ex0(Excitatory couplings)

從初始狀態(tài)GS1開(kāi)始，在振蕩器j激發(fā)后產(chǎn)生耦合強(qiáng)度ε，此刻振蕩器i選擇正耦合強(qiáng)度(ε>0)，使其相位提升一個(gè)增量Δφi.其狀態(tài)表達(dá)式見(jiàn)式(3)：

φ=φi+Δφi=f-1(minφi)+ε,1〗)=F+(φi,ε)

(3)

當(dāng)滿足條件A：F+(φi,ε)≥1，系統(tǒng)達(dá)到同步.

2)抑制耦合In0(Inhibitory couplings)

從初始狀態(tài)GS2開(kāi)始，振蕩器j激發(fā)后產(chǎn)生耦合強(qiáng)度ε，此時(shí)振蕩器i選擇負(fù)耦合強(qiáng)度(-ε<0)，振蕩器i進(jìn)行一耦即減的相位抑制作用，狀態(tài)表達(dá)式定義見(jiàn)式(4)：

φ=φi+Δφi=f-1(0,maxφi)-ε〗)=F-(φi,ε)

(4)

當(dāng)滿足條件B：F-(φi,ε)≤0，系統(tǒng)達(dá)到同步.

3.2 同步過(guò)程

1)從GS1初始狀態(tài)開(kāi)始：

在振蕩器j激發(fā)瞬間，振蕩器i激勵(lì)耦合同步.當(dāng)εj≥φ時(shí)，振蕩器i，j達(dá)到同步.否則同步演化的相位變化見(jiàn)表1.

表1 兩個(gè)振蕩器從GS1開(kāi)始的相位變化表

Table 1 Phase changes of two oscillators starting fromGS1

TimeΔt?i?j00?1-?1-?→1-?+εj1→0?-εj1→0?-εj→?-εj-εi=?-(εj+εi)

2)從GS2初始狀態(tài)開(kāi)始：

在振蕩器j激發(fā)瞬間，振蕩器i抑制耦合，當(dāng)φi=1-φ-εj≤0，振蕩器i，j達(dá)到同步狀態(tài).否則同步演化的相位變化見(jiàn)表2.

3.3 同步條件分析

通過(guò)兩個(gè)振蕩器組成的振蕩器系統(tǒng)在基態(tài)時(shí)的相位差來(lái)定義同步過(guò)程中的激發(fā)映射(firing map)與回歸映射(return map)：

φi,j(tp,i)=φj(tp,i)-φi(tp,i)=φj(tp,i)-0=φp,i

(5)

其中p表示振蕩器i的激發(fā)時(shí)刻.

表2 兩個(gè)振蕩器從GS2開(kāi)始的相位變化表

Table 2 Phase changes of two oscillators starting fromGS2

TimeΔt?i?j00?1-?1-?→1-?-εj1→0?+εj1→0?+εj→?+εj+εi=?+(εj+εi)

定義4.激發(fā)映射：從基態(tài)φi=0,φj=φ起，振蕩器j第一次達(dá)到激發(fā)狀態(tài)時(shí)振蕩器i的相位.

h：φp,i→φq,j:φq,j=h(φp,i)

定義5.回歸映射：從基態(tài)φi=0,φj=φ起，振蕩器i第一次達(dá)到激發(fā)狀態(tài)時(shí)振蕩器j的相位.

R：φp,i→φp+1,i:φp+1,i=R(φp,i)

由表1,2分別得到兩種初始狀態(tài)的回歸映射：

R(φp,i)=φ-(εj+εi)

(6)

R(φp,i)=φ+(εj+εi)

(7)

在i某次激發(fā)之后，j的相位比上次i激發(fā)時(shí)減少或增加了εj+εi.

通過(guò)分析R(φp,i)可以得到兩個(gè)脈沖耦合振蕩器到達(dá)同步的同步條件：

定理1.【兩個(gè)脈沖振蕩器同步條件】對(duì)于兩個(gè)振蕩器i和j，如果耦合強(qiáng)度滿足式(8)：

εj+εi≠0

(8)

則它們達(dá)到同步狀態(tài).

證明：由于正耦合強(qiáng)度ε>0，負(fù)耦合強(qiáng)度-ε<0，且，故εj+εi>0恒成立，得到兩種初始狀態(tài)下的回歸映射：

R(φp,i)=φ-(εj+εi)<φ

(9)

R(φp,i)=φ+(εj+εi)>φ

(10)

表明振蕩器i和j的任意初始狀態(tài)都會(huì)使兩者的相位單調(diào)向著0或者1進(jìn)行演化，兩個(gè)脈沖耦合振蕩器組成的振蕩器系統(tǒng)達(dá)到同步狀態(tài).

通過(guò)上述分析，根據(jù)系統(tǒng)在兩種不同的初始狀態(tài)下的同步演進(jìn)過(guò)程，構(gòu)建出完整的狀態(tài)轉(zhuǎn)移圖驗(yàn)證系統(tǒng)同步性.由圖2所示，系統(tǒng)可從任意基態(tài)作為初始狀態(tài)進(jìn)行相位演化，到達(dá)激發(fā)態(tài)后選擇合適的相位耦合方式，耦合強(qiáng)度的影響使得系統(tǒng)逐漸趨向于同步條件A或B，在有限狀態(tài)機(jī)中的每個(gè)狀態(tài)轉(zhuǎn)化到最終的同步狀態(tài).

圖2 兩個(gè)振蕩器同步有限狀態(tài)自動(dòng)機(jī)

4 多振蕩器同步

4.1 耦合方式

分析多振蕩器進(jìn)行同步演化時(shí)，需要考慮多振蕩器系統(tǒng)內(nèi)其他振蕩器處于激發(fā)瞬間的耦合強(qiáng)度Σk∈Eεk對(duì)同步進(jìn)程的影響.其中E表示在振蕩器i和振蕩器j激發(fā)演化過(guò)程中到達(dá)激發(fā)狀態(tài)振蕩器的集合.

1)激勵(lì)耦合Ex1(Excitatory couplings)

振蕩器i和j在GS2初始狀態(tài)下，若Σk∈Eεk使振蕩器i和j的相位增加到φi=φj=1，振蕩器i，j到達(dá)同步，組成振蕩器同步組.

2)抑制耦合In1(Inhibitory couplings)

振蕩器i和j在GS1狀態(tài)下進(jìn)行同步演化.Σk∈Eεk使振蕩器i和j的相位下降到φj=φi=0，振蕩器i，j到達(dá)同步，組成一個(gè)振蕩器同步組.

4.2 同步過(guò)程

1)從基態(tài)GS1開(kāi)始：

當(dāng)φ≤Σk∈Eεk，則經(jīng)過(guò)In1使得φi=φj=0，振蕩器i和j同步，否則未達(dá)到同步.本文主要分析未同步狀態(tài)，其相位變化見(jiàn)表3.

表3 多振蕩器從GS1開(kāi)始的相位變化

Table 3 Phase changes of multiple oscillators starting withGS1

TimeΔt?i?j00?1-?+Σk∈Eεk-Σk∈Eεk=1-?1-?→1-?+εj1→0?-εj-Σk∈Eεk1→0?-εj-Σk∈Eεk→?-εj-εi-Σk∈Eεk=?-(εj+εi+Σk∈Eεk)

2)從基態(tài)GS2開(kāi)始：

振蕩器i和j受到Σk∈Eεk的激勵(lì)作用，若Σk∈Eεk足夠大使得φi=φj=1，則振蕩器i和j同步.否則振蕩器j需經(jīng)過(guò)1-φ-Σk∈Eεk相位φj=1，振蕩器j激發(fā)，此時(shí)φi=1-φ-Σk∈Eεk∈(0,1/2)，進(jìn)行抑制耦合同步.當(dāng)1-φ-Σk∈Eεk-εj≤0時(shí)，振蕩器i和j到達(dá)同步.本文主要分析未到達(dá)同步的情況，其相位變化見(jiàn)表4.

4.3 同步條件

由表3和表4可知，多振蕩器系統(tǒng)中振蕩器i和j回歸映射分別為：

R(φp,i)=φ-(εj+εi+Σk∈Eεk)

(11)

R(φp,i)=φ+(εj+εi+Σk∈Eεk)

(12)

通過(guò)式(11)、式(12)可以看出，在i某次激發(fā)之后，j的相位比上次i激發(fā)時(shí)減少或增加了εj+εi+Σk∈Eεk.因此，得到兩個(gè)脈沖耦合振蕩器的同步條件如式(13).

定理2.【多振蕩器系統(tǒng)同步條件】對(duì)于一個(gè)由N個(gè)振蕩器組成的的非漏電脈沖耦合振蕩器系統(tǒng)，令E={ε1,ε2,…,εN}為系統(tǒng)中所有振蕩器的耦合強(qiáng)度的集合，如果該系統(tǒng)滿足條件(13)：

(13)

?E1,E2?E，E1∩E2=?

則其能夠到達(dá)同步.

證明：對(duì)于系統(tǒng)中的兩個(gè)振蕩器i和j或兩個(gè)振蕩器組m和n，令:

表4 多振蕩器從GS2開(kāi)始的相位變化

Table 4 Phase changes of multiple oscillators starting withGS2

TimeΔt?i?j00?1-?-Σk∈Eεk1-?-Σk∈Eεk→1-?-Σk∈Eεk-εj1→0?+Σk∈Eεk+εj+Σk∈Eεk-Σk∈Eεk=?+Σk∈Eεk+εj1→0?+Σk∈Eεk+εj→?+εj+εi+Σk∈Eεk=?+(εj+εi+Σk∈Eεk)

εm，εn和Σk∈Eεk是多個(gè)耦合強(qiáng)度ε的累加，m和n為不同的振蕩器組，其中的振蕩器互不同步，且εj+εi+Σk∈Eεk>0，得到回歸映射：

R(φp,i)=φ-(εj+εi+Σk∈Eεk)<φ

(14)

R(φp,i)=φ+(εj+εi+Σk∈Eεk)>φ

(15)

分析R(φp,i)得到振蕩器i和j的任意初始狀態(tài)都會(huì)使兩者的相位單調(diào)向著0或者1進(jìn)行演化，最終互相吸收成為一個(gè)振蕩器組.

圖3 多振蕩器同步有限狀態(tài)自動(dòng)機(jī)

振蕩器組的耦合強(qiáng)度為兩個(gè)振蕩器耦合強(qiáng)度之和，即εi,j=εj+εi.隨著同步的演進(jìn)，整個(gè)系統(tǒng)中會(huì)出現(xiàn)多個(gè)振蕩器同步組，各個(gè)振蕩器組再互相吸收，最后逐漸減少到兩個(gè)較大的振蕩器組，組成一個(gè)振蕩器組時(shí)系統(tǒng)達(dá)到同步狀態(tài).多振蕩器系統(tǒng)同步過(guò)程的狀態(tài)轉(zhuǎn)移由圖3所示，在有限狀態(tài)機(jī)中的每個(gè)狀態(tài)轉(zhuǎn)化到最終的同步狀態(tài).

5 仿真與驗(yàn)證

仿真環(huán)境使用Java語(yǔ)言在Eclipse下開(kāi)發(fā)的脈沖耦合振蕩器模型的仿真程序，對(duì)本文模型進(jìn)行數(shù)值分析，并與適用于WSN的非漏電脈沖耦合振蕩器同步模型[13]在相同仿真環(huán)境下進(jìn)行實(shí)驗(yàn)對(duì)比.

5.1 耦合參數(shù)對(duì)同步周期的影響分析

將初始相位φ設(shè)置為T〗上的一個(gè)隨機(jī)數(shù)，耦合強(qiáng)度ε設(shè)為_base-1/2*ε_(tái)base*ε_(tái)ratio,ε_(tái)base+1/2*ε_(tái)base*ε_(tái)ratio〗中一個(gè)隨機(jī)數(shù)，其中ε_(tái)base為耦合強(qiáng)度基數(shù)值，ε_(tái)ratio為耦合強(qiáng)度數(shù)值比率.

圖4為同步所需仿真周期隨ε_(tái)ratio對(duì)系統(tǒng)進(jìn)行了1000次同步仿真的變化情況，分別設(shè)定ε_(tái)base=0.05，ε_(tái)ratio=0.05和ε_(tái)ratio=0.2，通過(guò)兩組差值較大的耦合強(qiáng)度數(shù)值比率分析其對(duì)系統(tǒng)同步的影響.從圖4可以看出，當(dāng)振蕩器數(shù)目足夠大的時(shí)候，仿真周期并不隨其發(fā)生變化，同時(shí)兩組數(shù)據(jù)的線性走勢(shì)趨同，說(shuō)明耦合強(qiáng)度的數(shù)值比率ε_(tái)ratio的大小對(duì)于振蕩器系統(tǒng)的同步影響微小.由于耦合強(qiáng)度取決于ε_(tái)ratio和ε_(tái)base，因此將ε_(tái)ratio的值設(shè)定為0.1，分析與討論ε_(tái)base和振蕩器個(gè)數(shù)對(duì)同步周期的影響.

圖4 不同ε_(tái)ratio的同步周期數(shù)隨振蕩器數(shù)目的變化情況(ε_(tái)ratio=0.05,0.2; ε_(tái)base=0.05)

圖5 不同ε_(tái)base的同步周期數(shù)隨振蕩器個(gè)數(shù)的變化情況(ε_(tái)base=0.005,0.01,0.02; ε_(tái)ratio=0.1)

通過(guò)對(duì)比三組不同的ε_(tái)base值，分析在振蕩器個(gè)數(shù)從50擴(kuò)展到1000所需要的仿真周期數(shù)隨振蕩器個(gè)數(shù)的增加時(shí)的變化情況.由圖5所示，系統(tǒng)中的振蕩器越多，振蕩器越容易組合成為同步激發(fā)的振蕩器組，仿真周期數(shù)隨著振蕩器個(gè)數(shù)的增加而非線性的減小.因此，ε_(tái)base成為系統(tǒng)耦合強(qiáng)度差異的主要參數(shù)，耦合強(qiáng)度越大，同步所需周期數(shù)就越少.

5.2 模型同步效果分析

設(shè)置振蕩器數(shù)量為10(小規(guī)模)和50(較大規(guī)模)兩種不同網(wǎng)絡(luò)規(guī)模組成的實(shí)驗(yàn)場(chǎng)景，分析本文模型在不同數(shù)量振蕩器的實(shí)驗(yàn)場(chǎng)景下的同步性能.如圖6與圖7所示，將該模型與非漏電脈沖耦合振蕩器模型分別在振蕩器數(shù)量為10和50的兩種大小不同規(guī)模的實(shí)驗(yàn)場(chǎng)景中，進(jìn)行100次的同步周期對(duì)比實(shí)驗(yàn).

圖6 兩種模型在振蕩器數(shù)目10時(shí)的同步周期(ε_(tái)base=0.005; ε_(tái)ratio=0.1)

如圖6所示，本文模型到達(dá)同步所需的同步周期低于非漏電脈沖耦合振蕩器模型的同步周期，表現(xiàn)出該模型較快的同步速度.如圖7所示，該模型到達(dá)同步的所需的仿真周期的期望與方差小于非漏電脈沖耦合振蕩器模型，表現(xiàn)出該模型的較強(qiáng)的穩(wěn)定性和較好的同步性能.實(shí)驗(yàn)結(jié)果表明，在不同規(guī)模的振蕩器模型中，本文模型具有較好的同步效果.

圖7 兩種模型在振蕩器數(shù)目50時(shí)的同步周期(ε_(tái)base=0.005; ε_(tái)ratio=0.1)

從宏觀的角度進(jìn)行同步速度的對(duì)比觀察，由圖8所示，兩種系統(tǒng)模型達(dá)到同步所需要的仿真周期數(shù)隨振蕩器數(shù)目從10逐漸增加到100的變化情況.同步速度隨著振蕩器數(shù)量的擴(kuò)展而提升，且在同樣數(shù)目的振蕩器系統(tǒng)中，本文模型到達(dá)同步狀態(tài)需要更少的同步周期，有效的提升了系統(tǒng)同步速度.

圖8 兩種模型同步所需仿真周期隨振蕩器數(shù)目的變化情況(ε_(tái)base=0.005; ε_(tái)ratio=0.1)

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

螢火蟲(chóng)同步技術(shù)是解決WSN時(shí)間同步問(wèn)題的一種新型同步機(jī)制，本文在基于螢火蟲(chóng)同步算法提出了一種適用于WSN的時(shí)間同步改進(jìn)模型.對(duì)兩個(gè)振蕩器以及多振蕩器系統(tǒng)進(jìn)行理論分析，包括狀態(tài)函數(shù)、耦合方式、同步過(guò)程等，給出了振蕩器系統(tǒng)的同步條件，證明了滿足此條件的振蕩器能夠達(dá)到同步.通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了本文模型具有很好的穩(wěn)定性的同時(shí)降低了同步周期，加快了WSN節(jié)點(diǎn)之間的同步速度.