0 引言

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

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

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

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

1.1 M&S PCO模型

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

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

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

1.2 簡化相位模型

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

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

2 擁堵避免機(jī)制

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

2.1 隨機(jī)脈沖耦合

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

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

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

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

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

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

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

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

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

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

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

3 仿真與結(jié)果分析

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

3.1 仿真參數(shù)設(shè)置

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

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

3.2 仿真結(jié)果及分析

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

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

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

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

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

4 結(jié)論

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

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

參考文獻(xiàn)

[1] 徐朝農(nóng)，徐勇軍，李曉維.無線傳感器網(wǎng)絡(luò)時間同步新技術(shù)[J].計算機(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)博，宋  萍

（北京理工大學(xué) 機(jī)電學(xué)院，北京100081）