無線傳感器網絡中的螢火蟲時間同步改進模型

崔麗珍，曹 堅，安竹林，李丹陽，王巧利

1(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010) 2(中國科學院 計算技術研究所，北京 100190)

1 引 言

時間同步是無線傳感器網絡(Wireless Sensor Network，WSN)的一項支撐技術[1-3].對于WSN時間同步的研究，學者們提出了許多算法和協議[4-7]對該問題進行求解，當這些時間同步算法和協議被擴展到大規模網絡時，存在距離時間基準節點跳距的增加，而發生同步過程中同步誤差的累積，且大量的計算和復雜的數據包交換，使得WSN在實際運行中存在很大的負擔.針對上述問題學者們開始利用自然界中的互同步現象來對WSN進行時間同步的研究[8].

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

2 同步模型以及相關定義

2.1 模型描述

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

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

(1)

用狀態變量x描述振蕩器，x在1〗上單調遞增，當x到達閾值1時，振蕩器激發，并且x立即跳回0，產生耦合強度ε，正耦合強度ε>0，負耦合強度-ε<0.由于狀態和相位變量成線性關系，故使用φ統一表示.

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

(2)

圖1 相位同步過程圖

2.2 基本定義

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

存在兩個振蕩器i和j，一個振蕩器在某次激發之后相位為0，另一個振蕩器的相位等于φ的狀態.

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

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

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

定義2.激發態fire(fire state)：

振蕩器相位φ=1時的狀態.

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

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

各個振蕩器的狀態和相位到達一致時的狀態.

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

3 兩個振蕩器同步

3.1 耦合方式

1)激勵耦合Ex0(Excitatory couplings)

從初始狀態GS1開始，在振蕩器j激發后產生耦合強度ε，此刻振蕩器i選擇正耦合強度(ε>0)，使其相位提升一個增量Δφi.其狀態表達式見式(3)：

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

(3)

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

2)抑制耦合In0(Inhibitory couplings)

從初始狀態GS2開始，振蕩器j激發后產生耦合強度ε，此時振蕩器i選擇負耦合強度(-ε<0)，振蕩器i進行一耦即減的相位抑制作用，狀態表達式定義見式(4)：

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

(4)

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

3.2 同步過程

1)從GS1初始狀態開始：

在振蕩器j激發瞬間，振蕩器i激勵耦合同步.當εj≥φ時，振蕩器i，j達到同步.否則同步演化的相位變化見表1.

表1 兩個振蕩器從GS1開始的相位變化表

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初始狀態開始：

在振蕩器j激發瞬間，振蕩器i抑制耦合，當φi=1-φ-εj≤0，振蕩器i，j達到同步狀態.否則同步演化的相位變化見表2.

3.3 同步條件分析

通過兩個振蕩器組成的振蕩器系統在基態時的相位差來定義同步過程中的激發映射(firing map)與回歸映射(return map)：

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

(5)

其中p表示振蕩器i的激發時刻.

表2 兩個振蕩器從GS2開始的相位變化表

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.激發映射：從基態φi=0,φj=φ起，振蕩器j第一次達到激發狀態時振蕩器i的相位.

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

定義5.回歸映射：從基態φi=0,φj=φ起，振蕩器i第一次達到激發狀態時振蕩器j的相位.

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

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

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

(6)

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

(7)

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

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

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

εj+εi≠0

(8)

則它們達到同步狀態.

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

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

(9)

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

(10)

表明振蕩器i和j的任意初始狀態都會使兩者的相位單調向著0或者1進行演化，兩個脈沖耦合振蕩器組成的振蕩器系統達到同步狀態.

通過上述分析，根據系統在兩種不同的初始狀態下的同步演進過程，構建出完整的狀態轉移圖驗證系統同步性.由圖2所示，系統可從任意基態作為初始狀態進行相位演化，到達激發態后選擇合適的相位耦合方式，耦合強度的影響使得系統逐漸趨向于同步條件A或B，在有限狀態機中的每個狀態轉化到最終的同步狀態.

圖2 兩個振蕩器同步有限狀態自動機

4 多振蕩器同步

4.1 耦合方式

分析多振蕩器進行同步演化時，需要考慮多振蕩器系統內其他振蕩器處于激發瞬間的耦合強度Σk∈Eεk對同步進程的影響.其中E表示在振蕩器i和振蕩器j激發演化過程中到達激發狀態振蕩器的集合.

1)激勵耦合Ex1(Excitatory couplings)

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

2)抑制耦合In1(Inhibitory couplings)

振蕩器i和j在GS1狀態下進行同步演化.Σk∈Eεk使振蕩器i和j的相位下降到φj=φi=0，振蕩器i，j到達同步，組成一個振蕩器同步組.

4.2 同步過程

1)從基態GS1開始：

當φ≤Σk∈Eεk，則經過In1使得φi=φj=0，振蕩器i和j同步，否則未達到同步.本文主要分析未同步狀態，其相位變化見表3.

表3 多振蕩器從GS1開始的相位變化

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)從基態GS2開始：

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

4.3 同步條件

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

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

(11)

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

(12)

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

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

(13)

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

則其能夠到達同步.

證明：對于系統中的兩個振蕩器i和j或兩個振蕩器組m和n，令:

表4 多振蕩器從GS2開始的相位變化

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是多個耦合強度ε的累加，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的任意初始狀態都會使兩者的相位單調向著0或者1進行演化，最終互相吸收成為一個振蕩器組.

圖3 多振蕩器同步有限狀態自動機

振蕩器組的耦合強度為兩個振蕩器耦合強度之和，即εi,j=εj+εi.隨著同步的演進，整個系統中會出現多個振蕩器同步組，各個振蕩器組再互相吸收，最后逐漸減少到兩個較大的振蕩器組，組成一個振蕩器組時系統達到同步狀態.多振蕩器系統同步過程的狀態轉移由圖3所示，在有限狀態機中的每個狀態轉化到最終的同步狀態.

5 仿真與驗證

仿真環境使用Java語言在Eclipse下開發的脈沖耦合振蕩器模型的仿真程序，對本文模型進行數值分析，并與適用于WSN的非漏電脈沖耦合振蕩器同步模型[13]在相同仿真環境下進行實驗對比.

5.1 耦合參數對同步周期的影響分析

將初始相位φ設置為T〗上的一個隨機數，耦合強度ε設為_base-1/2*ε_base*ε_ratio,ε_base+1/2*ε_base*ε_ratio〗中一個隨機數，其中ε_base為耦合強度基數值，ε_ratio為耦合強度數值比率.

圖4為同步所需仿真周期隨ε_ratio對系統進行了1000次同步仿真的變化情況，分別設定ε_base=0.05，ε_ratio=0.05和ε_ratio=0.2，通過兩組差值較大的耦合強度數值比率分析其對系統同步的影響.從圖4可以看出，當振蕩器數目足夠大的時候，仿真周期并不隨其發生變化，同時兩組數據的線性走勢趨同，說明耦合強度的數值比率ε_ratio的大小對于振蕩器系統的同步影響微小.由于耦合強度取決于ε_ratio和ε_base，因此將ε_ratio的值設定為0.1，分析與討論ε_base和振蕩器個數對同步周期的影響.

圖4 不同ε_ratio的同步周期數隨振蕩器數目的變化情況(ε_ratio=0.05,0.2; ε_base=0.05)

圖5 不同ε_base的同步周期數隨振蕩器個數的變化情況(ε_base=0.005,0.01,0.02; ε_ratio=0.1)

通過對比三組不同的ε_base值，分析在振蕩器個數從50擴展到1000所需要的仿真周期數隨振蕩器個數的增加時的變化情況.由圖5所示，系統中的振蕩器越多，振蕩器越容易組合成為同步激發的振蕩器組，仿真周期數隨著振蕩器個數的增加而非線性的減小.因此，ε_base成為系統耦合強度差異的主要參數，耦合強度越大，同步所需周期數就越少.

5.2 模型同步效果分析

設置振蕩器數量為10(小規模)和50(較大規模)兩種不同網絡規模組成的實驗場景，分析本文模型在不同數量振蕩器的實驗場景下的同步性能.如圖6與圖7所示，將該模型與非漏電脈沖耦合振蕩器模型分別在振蕩器數量為10和50的兩種大小不同規模的實驗場景中，進行100次的同步周期對比實驗.

圖6 兩種模型在振蕩器數目10時的同步周期(ε_base=0.005; ε_ratio=0.1)

如圖6所示，本文模型到達同步所需的同步周期低于非漏電脈沖耦合振蕩器模型的同步周期，表現出該模型較快的同步速度.如圖7所示，該模型到達同步的所需的仿真周期的期望與方差小于非漏電脈沖耦合振蕩器模型，表現出該模型的較強的穩定性和較好的同步性能.實驗結果表明，在不同規模的振蕩器模型中，本文模型具有較好的同步效果.

圖7 兩種模型在振蕩器數目50時的同步周期(ε_base=0.005; ε_ratio=0.1)

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

圖8 兩種模型同步所需仿真周期隨振蕩器數目的變化情況(ε_base=0.005; ε_ratio=0.1)

6 結束語

螢火蟲同步技術是解決WSN時間同步問題的一種新型同步機制，本文在基于螢火蟲同步算法提出了一種適用于WSN的時間同步改進模型.對兩個振蕩器以及多振蕩器系統進行理論分析，包括狀態函數、耦合方式、同步過程等，給出了振蕩器系統的同步條件，證明了滿足此條件的振蕩器能夠達到同步.通過仿真實驗，驗證了本文模型具有很好的穩定性的同時降低了同步周期，加快了WSN節點之間的同步速度.