0 引言

    隨著多機器人協(xié)同過程中多機器人組成的網(wǎng)絡規(guī)模的不斷擴大，網(wǎng)絡拓撲關系越來越復雜，傳統(tǒng)常用的集中式無線網(wǎng)絡同步技術逐漸失去優(yōu)勢，人們急需研究出一種分布式時間同步算法^[1]。大自然給了人們研發(fā)分布式同步算法的靈感^[2-4]，其中典型的例子為東南亞螢火蟲同步閃爍現(xiàn)象。MIROLLO R E和STROGATZ S H以前人的研究為基礎^[5]，建立了螢火蟲同步模型的動力學M&S PCO（M&S Pulse Couple Oscillator，M&S PCO）模型，證明其在全鏈接無延時耦合的多振蕩器網(wǎng)絡中可收斂^[6]。利用螢火蟲同步算法可以將同步過程從網(wǎng)絡拓撲結構中獨立出來，使其適應大規(guī)模復雜拓撲結構的網(wǎng)絡，且同步的魯棒性增強^[7]。該類算法已在超幀結構同步和網(wǎng)絡休眠中得到應用^[8]。

    然而基于螢火蟲的時間同步算法雖然一定程度上解決了大規(guī)模網(wǎng)絡時間同步問題，但有兩個問題亟待解決^[1]：一是目前大部分使用的并發(fā)脈沖耦合機制在全網(wǎng)接近同步時，同步報文并發(fā)沖突使得CSMA/CA達到最差的性能，容易造成網(wǎng)絡擁堵和不可預見的延時，對算法穩(wěn)定性造成影響；二是WSN的硬件不能滿足螢火蟲同步算法的大量浮點運算。因此，為彌補目前螢火蟲同步網(wǎng)絡擁堵和不便實現(xiàn)等問題，有些學者已經(jīng)在這個方面做出了努力^[8-9]。然而這些研究僅在一定程度上起到緩解作用，在高密度網(wǎng)絡中，集中發(fā)送同步報文仍會導致嚴重的信道沖突。

    為了最大程度地解決密集節(jié)點集的發(fā)送同步報文擁堵問題，本文探索一種螢火蟲時間同步算法的擁堵避免機制，提出基于隨機脈沖耦合機制的無線傳感器網(wǎng)絡分布式協(xié)同時間同步方法，通過隨機脈沖耦合，盡可能避免網(wǎng)絡擁堵，充分利用網(wǎng)絡帶寬資源，增加了螢火蟲同步算法的實用性。

1 同步數(shù)學模型建立

1.1 M&S PCO模型

    針對初始不同步的系統(tǒng)，Charles將每個網(wǎng)絡節(jié)點看作一個RC振蕩器，建立了單個振蕩器的兩種基本數(shù)學模型^[5]：一種是自由運行模型，另一種是與其他節(jié)點耦合模型。節(jié)點自由運行狀態(tài)下，振蕩器的模型為：

式中，x表示進行了歸一化后的單個振蕩器電壓，S₀代表充電的速度，i代表電阻漏電流因子。當電容電壓達到最大值時，即x=1，振蕩器迅速放電，電壓突變?yōu)?。此時，振動器與其他振蕩器進行脈沖耦合，將其他振蕩器的電壓提升一個耦合系數(shù)ε，即第二種數(shù)學模型：

    MIROLLO R E與STROGATZ S H在Charles模型的基礎上引入了節(jié)點的動力學模型，建立振蕩器M&S PCO模型^[6]：

1.2 簡化相位模型

    上文介紹的M&S PCO為螢火蟲同步提供了理論分析的基礎。但是在以MCU為運算核心的無線傳感器網(wǎng)絡節(jié)點上，硬件運算資源有限，在做相位映射到狀態(tài)值時，需進行大量的浮點運算會占據(jù)硬件資源，影響網(wǎng)絡的正常功能，因此本文參考M&S PCO模型中相位狀態(tài)映射的特征，對M&S PCO模型進行簡化，并盡量避免復雜的浮點運算。

式中μ為相位提升量；以φ_j(t)為例，其表示節(jié)點i在t時刻的相位值。即當節(jié)點接收到有效觸發(fā)信號后，相位提升c₁φ_j(t)+c₂并于相位閾值進行比較，如果達到閾值則觸發(fā)。如此，便可通過相位的處理代替對節(jié)點狀態(tài)值的處理，使用簡單的運算代替復雜的相位狀態(tài)映射，達到簡化運算的目的。

2 擁堵避免機制

    在傳統(tǒng)的M&S PCO模型中，節(jié)點均在觸發(fā)瞬間進行同步耦合。在無線傳感器網(wǎng)絡中，脈沖耦合是通過節(jié)點發(fā)出同步報文實現(xiàn)，而這將導致節(jié)點集接近同步狀態(tài)時，節(jié)點的同步報文交換過于集中。為此，本節(jié)介紹一種擁堵避免機制，通過隨機脈沖耦合(Stochastic Pulse Couple Oscillator，SPCO)將同步報文分散到整個相位增長的過程中，以緩解報文交換過于集中帶來的信道沖突。

2.1 隨機脈沖耦合

    在SPCO中，節(jié)點在網(wǎng)絡中的同步和M&S PCO主要不同在于:將觸發(fā)和發(fā)出同步報文進行脈沖耦合的過程在時間軸上分離。觸發(fā)和同步報文耦合兩個任務相互獨立。節(jié)點在運行過程中以大于一個周期的隨機時間間隔發(fā)送出帶有自身相位信息的同步報文。發(fā)送同步報文的時刻是隨機的而非在節(jié)點相位達到閾值時，并且在同步報文中需包含本節(jié)點在發(fā)送瞬間的相位信息而非單純的脈沖信息。

    在SPCO模型中，當節(jié)點收到同步報文時，從中提取出相位信息，經(jīng)過與自身相位的比對判斷過濾出有效相位信息，并按照簡化模型計算相位增加量。并將所得相位增加量加至相位中，即可對相位產(chǎn)生耦合作用。

    為了方便說明，假設A、B兩個節(jié)點進行隨機脈沖耦合，節(jié)點B在隨機相位β處發(fā)出了一個同步報文，節(jié)點A處理算法的具體過程如下：

    (1)當節(jié)點A收到節(jié)點B同步報文后，記下收到瞬間本地的相位α和所收協(xié)議的前導碼延時相位d，解析同步報文內(nèi)的數(shù)據(jù)，得到節(jié)點B的發(fā)送報文時的相位β。

    (2)進行同步報文過濾，過濾規(guī)則為：當且僅當β≥α-d+r且β≤1+α-d-r時，即節(jié)點A和節(jié)點B的相位誤差在r范圍之外，且在一個周期內(nèi)節(jié)點B先于節(jié)點A觸發(fā)，則接收的數(shù)據(jù)包有效。其中r的作用類似于M&S PCO模型中的不應期(Refractory Period)^[10]，故亦稱其為不應期長度。

    (3)進行有效報文處理。處理的核心思想是模擬節(jié)點B在發(fā)送同步報文的周期內(nèi)觸發(fā)，將該脈沖耦合對節(jié)點A相位的影響提前至收到同步報文的時刻。隨著時間推進，由于β≥α-d+r，節(jié)點B的相位要超前于節(jié)點A，節(jié)點B會先與節(jié)點A到達閾值。當節(jié)點B達到相位閾值時，節(jié)點A的相位值為：

式中μ為調(diào)整步長；r為不應期長度；d為前導碼延時相位；α、β為步驟(1)中記錄的相位值；c₁、c₂為耦合常數(shù)。該次同步報文最終的結果是節(jié)點A的相位提高μ，一般情況下，為了避免節(jié)點集在同步接近收斂時相位抖動，需滿足μ<<r，耦合常數(shù)c₁、c₂應為一個較小常量。

    綜上可知，該次觸發(fā)過程的動力學模型總結為：

式中μ為調(diào)整步長；r為不應期長度；d為前導碼延時相位；α、β為步驟(1)中記錄的相位值；以φ_A(t)為例，其表示節(jié)點A在t時刻的相位值。

2.2 逃逸不穩(wěn)定平衡區(qū)間

    需要額外注意的是，由于當節(jié)點相差相位閾值的一半時，兩個節(jié)點的位置互換并不影響相位調(diào)整的調(diào)整步長，這就導致任意節(jié)點所發(fā)同步報文對另外一個節(jié)點的相位增長影響近乎相同，兩節(jié)點保持相位差相對不變。為了避免這種不穩(wěn)定平衡現(xiàn)象，需要在相位閾值的一半處設置一個逃逸區(qū)間[0.5-δ，0.5]，當節(jié)點相位差落入這個區(qū)間后，調(diào)整步長迅速增大至逃逸速度U，且U>δ，使其逃離該不穩(wěn)定平衡區(qū)域，達到加速同步的目的。

3 仿真與結果分析

    在本節(jié)中，針對第2節(jié)提出的SPCO同步機制進行仿真驗證。為了方便對比，將仿真實驗分為兩組，分別使用傳統(tǒng)的M&S PCO 機制和本文中介紹的SPCO機制進行實驗。通過記錄相位和同步報文并發(fā)情況，從同步收斂精度、同步所需時間、同步報文并發(fā)情況三方面分析SPCO機制對同步過程的影響。

3.1 仿真參數(shù)設置

    為了增強對比性，兩組仿真實驗中存在一些共同的仿真參數(shù)。在仿真實驗中，20個節(jié)點被布置在一個全鏈接網(wǎng)絡中，仿真時間為400 s。網(wǎng)絡中的每個節(jié)點與其他19個節(jié)點向鏈接。節(jié)點的初始相位為隨機分布于0~1之間。節(jié)點的相位閾值為1，相位周期為1 s。節(jié)點的不應期長度設為0.1，節(jié)點相位同步窗體大小為0.001（即相位誤差在0.001之內(nèi)便認為節(jié)點同步）。為滿足μ<<r，耦合常數(shù)設為c₁=0.005，c₂=0.005，SPCO中不穩(wěn)定平衡區(qū)間設為[0.4，0.5]，逃逸速度為0.3。

    為了保證仿真模型的真實性，將每個節(jié)點的晶振速度增加50PPM的跳動，并在消息交換過程中設置了10~100 μs的隨機延時。而為了比較SPCO對同步時間和精度的影響，暫不考慮信道沖突對同步報文傳輸?shù)挠绊憽?/p>

3.2 仿真結果及分析

    這兩組試驗仿真前后網(wǎng)絡節(jié)點相位變化如圖1。從圖中可以看出，節(jié)點集的初始相位是分散的，經(jīng)過SPCO和M&S PCO同步過程，在仿真結束后節(jié)點集相位均收斂。從最后的同步效果來看，基于SPCO的沖突避讓機制并沒有影響同步算法的穩(wěn)定性和精度。

    為統(tǒng)計網(wǎng)絡中同步報文的并發(fā)情況，以0.000 5 s為單位時間區(qū)間，統(tǒng)計以不同中心時刻的單位時間區(qū)間中，同步報文的并發(fā)數(shù)目，以檢測通信的擁堵情況，同時統(tǒng)計此時的相位誤差以方便尋找其中的規(guī)律。

    圖2表示M&S PCO同步過程中的相位誤差和報文并發(fā)數(shù)隨時間的變化。從圖中可看出隨著同步過程的進行，報文并發(fā)數(shù)隨著相位誤差的減少明顯增多。在350 s后，節(jié)點集達到同步，在單位時間區(qū)間內(nèi)，節(jié)點并發(fā)數(shù)甚至達到20。較大的并發(fā)數(shù)會造成無線信道的嚴重堵塞，不利于該時刻數(shù)據(jù)的傳輸穩(wěn)定性和即時性。

    圖3表示M&S PCO同步過程中的相位誤差和報文并發(fā)數(shù)隨時間的變化。從圖中可以看出，網(wǎng)絡相位在30 s時便達到收斂，并且并發(fā)報文數(shù)并沒有隨相位誤差的減小而增加。整個節(jié)點集的同步報文發(fā)送均勻的分布在整個時間軸內(nèi)，并不受相位誤差的影響。

    對比圖2和圖3可知，SPCO沖突避免機制在不影響同步精度的前提下，不僅可縮短同步時間，并且在時間軸上極大緩解了并發(fā)同步報文帶來的信道擁堵。

4 結論

    本文提出了一種基于隨機脈沖耦合同步的螢火蟲同步信道擁堵避免機制，實現(xiàn)多機器人分布式時間同步。文章首先簡化傳統(tǒng)螢火蟲同步的數(shù)學模型，給出信道擁堵避免機制，然后通過仿真實驗，進行對比驗證。試驗證明了相對于傳統(tǒng)M&S PCO，SPCO同步機制可在不影響同步精度的條件下，加速同步進程，并且在很大程度上緩解集中觸發(fā)耦合的信道擁堵，驗證了擁堵避免機制的可行性。

    隨機脈沖耦合同步機制使用簡化相位模型，便于在單片機中實現(xiàn)。其觸發(fā)信息的發(fā)射可以更加充分的利用帶寬，甚至和節(jié)點的常規(guī)數(shù)據(jù)包融合。算法本身對丟包不敏感，可以適應無線環(huán)境較為惡劣的條件。

參考文獻

[1] 徐朝農(nóng)，徐勇軍，李曉維.無線傳感器網(wǎng)絡時間同步新技術[J].計算機研究與發(fā)展，2008，45(1)：138-145.

[2] ALLARD H A.Synchronous flashing of fireflies[J].Science(New York，NY)，1935，82(2120)：151-152.

[3] BUSCH N E，VINNICHE N K，WATERMAN A T，et al.Waves and turbulence[J].Radio Science，1969，4(12)：1377-1379.

[4] GLASS L，MACKEY M C.From clocks to chaos-the rhythms of life[J].Nature，1988，336(6195)：119.

[5] PESKIN C S.Mathematical aspects of heart physiology[M].New York：Courant Institute of Mathematical Sciences，New York University，1975.

[6] MIROLLO R E，STROGATZ S H.Synchronization of pulse-coupled biological oscillators[J].SIAM J Appl.Math.，1990，50(6)：1645-1662.

[7] BOJIC I，PODOBNIK V，LJUBI I，et al.A self-optimizing mobile network：Auto-tuning the network with firefly-synchronized agents[J].Inform Sciences，2012，182(1)：77-92.

[8] TYRRELL A，AUER G，BETTSTETTER C.Emergent slot synchronization in wireless networks[J].IEEE T.Mobile Comput.，2010，9(5)：719-932.

[9] LEIDENFROST R，ELMENREICH W.Firefly clock synchronization in an 802.15.4 wireless network[J].EURASIP Journal on Embedded Systems，2009(1)：1-17.

[10] HONG Y W，SCAGLIONE A.A scalable synchronization protocol for large scale sensor networks and its applications[J].IEEE J.Sel.Area.Comm.，2005，23(5)：1085-1099.

作者信息:

郝創(chuàng)博，宋  萍

（北京理工大學 機電學院，北京100081）