基于Gossip協(xié)議的多機器人系統(tǒng)通訊機制的研究

侯 君

0 引言

多機器人系統(tǒng)的通訊機制一直是機器人領(lǐng)域研究的一個重要分支。研究發(fā)現(xiàn)在一些特定的多機器人任務中，加入通訊機制會顯著提高執(zhí)行效率[1]。當機器人群體在執(zhí)行一些特定任務（如探索、聚集）時，節(jié)點并發(fā)地對傳感器獲得的信息進行共享，從而提高執(zhí)行效率。成功執(zhí)行這些任務需要保證信息傳遞的可靠性、快速性。然而在其它一些任務（如區(qū)域覆蓋）中，機器人系統(tǒng)由大量廉價、功能簡單的機器人節(jié)點組成，此時計算速度不是唯一的衡量指標，更應考慮通訊功能是否會對機器人有限的硬件資源（如 CPU、電源、通信帶寬）帶來額外開銷。

現(xiàn)今多機器人通訊機制中應用最成熟的當屬MANET(Mobile Ad Hoc Network)[2]。通過MANET，區(qū)域內(nèi)各節(jié)點可以快速構(gòu)建訪問路由，并實現(xiàn)對音頻、圖像信息的傳遞，但 MANET不足之處也因機器人規(guī)模擴大而凸顯。MANET的路由查找協(xié)議（AODV，DSR[3]）需要構(gòu)建復雜的數(shù)據(jù)包格式，在處理簡單信息時會顯得過于復雜，并且機器人動態(tài)變換的網(wǎng)絡拓撲結(jié)構(gòu)也降低了協(xié)議的擴展性。通過研究發(fā)現(xiàn)，一種已被廣泛應用于分布式系統(tǒng)信息管理的Gossip協(xié)議[4]可避免上述缺點。Gossip協(xié)議通過對冗余的信息不斷轉(zhuǎn)發(fā)，保證了信息擴散的可靠性，同時該協(xié)議隨機選擇通訊節(jié)點，因此無需維護路由表信息。Gossip協(xié)議對數(shù)據(jù)丟包情況有較高的容錯性，并且無需復雜配置，因此非常適用于群體穩(wěn)定但節(jié)點間通訊關(guān)系變化較大的場景中，如區(qū)域覆蓋[1][5]。本文提出將Gossip協(xié)議用于多機器人系統(tǒng)通訊機制中，并讓系統(tǒng)完成群體規(guī)模統(tǒng)計任務以驗證該協(xié)議的可靠性與可擴展性，為進一步研究提供參考。

1 實現(xiàn)原理

1.1 多機器人無線通訊特性

分析發(fā)現(xiàn)多機器人系統(tǒng)節(jié)點的網(wǎng)絡通訊通常具有以下3個特點：（1）隨機性。即機器人節(jié)點A將會與哪一個節(jié)點建立連接、何時建立連接不可預測，對通信節(jié)點的選擇是隨機的。（2）非連續(xù)性。兩個或多個建立通信的機器人的通訊只會保持一段時間，在完成信息交互后，由于機器人不斷運動，通信連接將斷開。（3）局部性。機器人只保證與通信范圍內(nèi)的鄰居節(jié)點共享信息。

因此，多機器人之間的通訊機制應在保證數(shù)據(jù)可靠傳輸?shù)幕A(chǔ)上保持設計簡單，以適應上述3個特性。

1.2 改進的Gossip協(xié)議

傳統(tǒng)的 Gossip協(xié)議主要用于分布式系統(tǒng)信息管理、數(shù)據(jù)庫備份[4]等應用中，直到近幾年才有學者發(fā)現(xiàn)其應用于多機器人通訊中的潛力。Paolo Frasca[1]等人基于Gossip協(xié)議提出一種多機器人覆蓋算法，通過隨機選擇節(jié)點實現(xiàn)異步通訊，表明了Gossip協(xié)議的隨機特性。

Gossip協(xié)議一個重要的特點就是對數(shù)據(jù)的更正，即便兩個節(jié)點間的通訊數(shù)據(jù)出現(xiàn)問題，也會在一段時間后，通過其它節(jié)點得到更正，即Gossip協(xié)議對數(shù)據(jù)有一定的容錯性[6][7]。通過對傳統(tǒng)的 Gossip協(xié)議相關(guān)研究進行總結(jié)，發(fā)現(xiàn)其具有以下特性：

(1)有限性。節(jié)點間傳輸?shù)臄?shù)據(jù)大小有限，可以理解為每次傳輸?shù)臄?shù)據(jù)包很小并且格式固定。

(2)一致性。兩個節(jié)點每次交互，都會有一個節(jié)點更改為另外一個節(jié)點的狀態(tài)。

(3)頻繁性。利用節(jié)點間頻繁的數(shù)據(jù)交互彌補大量數(shù)據(jù)傳輸導致的延遲。

(4)隨機性。節(jié)點在選擇與其通訊的節(jié)點時，考慮就近原則，即與靠近的、通信范圍內(nèi)的節(jié)點通訊。

為滿足多機器人規(guī)模統(tǒng)計的通訊需求，本課題對Gossip協(xié)議進行適當改進。但其核心思想仍是節(jié)點間不斷交互局部視圖信息（鄰居節(jié)點ID），并對本地的全局視圖信息進行維護，進而實現(xiàn)通過分布式的方式獲取全局節(jié)點信息（機器人群體數(shù)目）。改進的Gossip協(xié)議主要分為以下三個步驟：

步驟1：接觸。當新的節(jié)點A加入機器人群體時，會廣播發(fā)送請求建立聯(lián)系的數(shù)據(jù)包，包中信息包括節(jié)點ID以及A之前的鄰居節(jié)點列表。

步驟2：轉(zhuǎn)發(fā)信息。當節(jié)點B第一次收到來自A的請求包時，首先檢測到A的ID是否存在于其本地鄰居節(jié)點列表中，如果不存在，它會將ID記錄到本地的全局節(jié)點列表，反之不進行保存。

步驟3：更新視圖。機器人群體中每個節(jié)點都會維護兩個視圖表：局部視圖表中存儲它所有可以建立通信的鄰居節(jié)點 ID；全局視圖表存儲節(jié)點運行過程中搜集到的所有節(jié)點ID。

通過這種對信息的不斷轉(zhuǎn)發(fā)，以及對全局視圖表的信息更新，最終就可根據(jù)全局視圖表統(tǒng)計出整個機器人群體的數(shù)目。單個節(jié)點A上運行改進的Gossip協(xié)議具有以下通用的算法：

1.3 規(guī)模統(tǒng)計算法

為完成對改進的 Gossip協(xié)議的驗證，本文提出一種機器人規(guī)模統(tǒng)計的應用場景，節(jié)點間信息傳遞由 Gossip協(xié)議實現(xiàn)。具體實現(xiàn)上，每個節(jié)點包含兩個進程完成數(shù)據(jù)包的收發(fā)，分別稱為主動進程和被動進程。主動進程用于定期廣播請求信息數(shù)據(jù)包，并接收來自鄰居節(jié)點的反饋信息，請求信息數(shù)據(jù)包由源節(jié)點標識符和局部視圖組成。局部視圖包含通信范圍內(nèi)的所有鄰居節(jié)點的記錄，每條記錄對應一個心跳信息，用心跳值來記錄鄰居節(jié)點是否存在。主動進程首先檢查本地鄰居列表心跳值是否為“0” ，如果為“0”表示該節(jié)點已不再是鄰居節(jié)點，則將該節(jié)點記錄刪除，否則每個時鐘周期心跳值減1。通過心跳值，每個節(jié)點可以對鄰居列表的信息進行動態(tài)更新，如圖1所示：

圖1 主動進程數(shù)據(jù)包處理流程圖

被動進程用于處理和轉(zhuǎn)發(fā)接收到的請求信息數(shù)據(jù)包，將數(shù)據(jù)包中新的相關(guān)信息添加到本地全局視圖中，全圖視圖維護的是當前節(jié)點運行過程中收集到的節(jié)點記錄。當節(jié)點收到一個請求數(shù)據(jù)包時，先檢查數(shù)據(jù)包中源節(jié)點標識符是否在其局部視圖的鄰居列表中，如果不存在記錄，則被動進程在鄰居列表中新增一條記錄，并將其心跳值設為最大，同時將源節(jié)點記錄添加到全局視圖表中。最后對整個全局視圖進行統(tǒng)計，即可求出整個機器人群體的規(guī)模，如圖2所示：

圖2 被動進程數(shù)據(jù)包處理流程圖

2 性能測試及分析結(jié)果

為了驗證 Gossip協(xié)議的可靠性，本實驗選取Player/Stage[8]軟件作為實驗平臺。Player/Stage是一個為多機器人系統(tǒng)提供內(nèi)部接口和仿真環(huán)境的工具，如圖3所示：

圖3 機器人仿真環(huán)境（節(jié)點數(shù):10）

Player是一個多線程的機器人驅(qū)動服務器，提供了接口程序用于驅(qū)動機器人和傳感器設備，通過TCP Socket與客戶端通信。Stage是仿真層，主要提供虛擬場景下機器人的模擬，并且提供了豐富的傳感器和執(zhí)行器模塊，包括聲納、激光測距儀、WiFi、移動機器人基座等。仿真機器人型號pioneer2dx，配備激光測距儀、WiFi模塊。仿真區(qū)域設定為16m * 16m的平面區(qū)域。機器人設定初始狀態(tài)后通過改進的Gossip協(xié)議進行通訊，完成對群體的規(guī)模統(tǒng)計。實驗主要考察兩個衡量指標：準確率和通信量。

2.1 可靠性

Gossip協(xié)議的可靠性表現(xiàn)為某段時間內(nèi)整個群體的統(tǒng)計準確率。因此，該部分實驗中，機器人在具有障礙物的環(huán)境中隨機行走，一段時間后機器人節(jié)點將獲知整個群體的數(shù)目。實驗結(jié)果，如圖4所示：

圖4 不同時間內(nèi)機器人規(guī)模統(tǒng)計準確率

橫坐標表示不同機器人群體總數(shù)，縱坐標表示測試結(jié)果的準確情況（統(tǒng)計值/真實值）。由圖4可以看出，Gossip協(xié)議在中小規(guī)模機器人群體中（10～40個）具有良好的穩(wěn)定性。當群體數(shù)目超過50個，出現(xiàn)大幅度的誤差。分析其原因，單位區(qū)域中的機器人此時過于密集，會導致群體機動性變差，節(jié)點信息的轉(zhuǎn)發(fā)只在比較集中的區(qū)域進行，因此全局視圖信息更新不完全。而隨著時間進行，隨著節(jié)點不斷移動，其鄰居列表也在不斷更新，同時也增大接受轉(zhuǎn)發(fā)信息的概率，此時對全局視圖的信息更新比較充分。

2.2 可擴展性

Gossip協(xié)議的可擴展性表現(xiàn)為當機器人數(shù)量增加時，單個機器人的通訊量不會受到太大的影響。實驗場景將機器人的數(shù)目從10個一直增加到100個，為了簡化外界環(huán)境影響，場景中不設置障礙物。橫坐標表示機器人個數(shù)，縱坐標表示機器人單位時間內(nèi)的信息量。分別記錄節(jié)點單位時間內(nèi)最大、最小、平均的信息量，如圖5所示：

圖5 不同數(shù)目下機器人通訊量變化圖

由圖5可以看出，使用基于Gossip協(xié)議進行信息擴散，隨著群體規(guī)模的變化，單位時間內(nèi)的平均信息量增長幅度較小。說明機器人群體規(guī)模的變化不會對 Gossip協(xié)議產(chǎn)生太大的影響。因此，Gossip協(xié)議在分布式多機器人應用中具有較高的可擴展性。

4 結(jié)束語

本文將 Gossip協(xié)議引入多機器人系統(tǒng)的無線通訊機制中，并基于Gossip協(xié)議提出多機器人系統(tǒng)的規(guī)模統(tǒng)計算法。針對機器人移動性、計算能力有限、帶寬有限等特性，對Gossip協(xié)議進行適當修改。使得機器人節(jié)點通過轉(zhuǎn)發(fā)局部鄰居列表，以及維護全局視圖即可完成信息的有效傳遞，并進一步統(tǒng)計出群體中機器人數(shù)量。本文從統(tǒng)計準確率和通訊量兩個指標對改進的 Gossip協(xié)議進行衡量。實驗結(jié)果表明，Gossip協(xié)議可有效利用大規(guī)模移動機器人的特點實現(xiàn)信息地快速轉(zhuǎn)發(fā)，并通過對冗余信息的更正保證數(shù)據(jù)可靠性。同時，還能避免機器人通訊量因規(guī)模擴大而劇烈增加，具有良好可擴展性。下一步，本課題將在真實機器人平臺上引入改進 Gossip協(xié)議，以獲得更可靠的實驗數(shù)據(jù)。同時本課題將進一步研究 Gossip協(xié)議在更多的多機器人任務（聚集、擴散、地圖探索等）中的可行性。

[1]P. Frasca, R. Carli, and F. Bullo, “Multiagent coverage algorithms with gossip communication: control systems on the space of partitions,” [C]in American Control Conference, (St. Louis, MO), pp. 2228—2235, June 2009.

[2]Dr. Pradip Ghorpade, Pravin Ghosekar, Girish Katkar.Mobile Ad Hoc Networking: Imperatives and Challenges. IJCA Special Issue [J]on MANETs (3):153—158,2010.

[3]Johnson D B, MaltD A z, Hu Y C. The dynamic source routing protocol for mobile ad hoc networks(DSR). [J]IETF Internet Draft. July, 2004.

[4]Demers, A., D. Greene, et al. Epidemic algorithms for replicated database maintenance. Proceedings of the sixth annual ACM Symposium on Principles of distributed computing. Vancouver, British Columbia, Canada, [J]ACM: 1-12.1987.

[5]F. Bullo, R. Carli, and P. Frasca, "Gossip coverage control for robotic networks: [C]Dynamical systems on the the space of partitions," Dec. 2009.

[6]S. Boyd, A. Ghos h, B. Prabhakar, and D . S hah, “Gossip algorithms :Design, analysis and applications ,”[J]in Proceedings of IEEE Infocom 2005,vo l. 3, pp.1653—1664. March 2005.

[7]Alvisi, L., J. Doumen, et al. "How robust are gossip-based communication protocols?" [J]SIGOPS Oper.Syst. Rev. 41(5): 14-18. 2007.

[8]B.P Gerkey, R.T.Vaughan, and A.Howard, "The player/stage projects: Tools for multi-robot and distributed sensor systems", [C]in International Conference on Advanced Robotics, pp.317-323. 2003.