0 引言

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

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

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

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

1.1 M&S PCO模型

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

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

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

1.2 簡(jiǎn)化相位模型

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

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

2 擁堵避免機(jī)制

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

2.1 隨機(jī)脈沖耦合

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

參考文獻(xiàn)

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