0 引言

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

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

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

1 同步數學模型建立

1.1 M&S PCO模型

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

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

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

1.2 簡化相位模型

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

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

2 擁堵避免機制

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

2.1 隨機脈沖耦合

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

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

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

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

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

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

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

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

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

2.2 逃逸不穩定平衡區間

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

3 仿真與結果分析

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

3.1 仿真參數設置

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

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

3.2 仿真結果及分析

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

    為統計網絡中同步報文的并發情況，以0.000 5 s為單位時間區間，統計以不同中心時刻的單位時間區間中，同步報文的并發數目，以檢測通信的擁堵情況，同時統計此時的相位誤差以方便尋找其中的規律。

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

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

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

4 結論

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

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

參考文獻

[1] 徐朝農，徐勇軍，李曉維.無線傳感器網絡時間同步新技術[J].計算機研究與發展，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.

作者信息:

郝創博，宋  萍

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