基于Gossip協議的多機器人系統通訊機制的研究

侯 君

0 引言

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

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

1 實現原理

1.1 多機器人無線通訊特性

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

因此，多機器人之間的通訊機制應在保證數據可靠傳輸的基礎上保持設計簡單，以適應上述3個特性。

1.2 改進的Gossip協議

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

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

(1)有限性。節點間傳輸的數據大小有限，可以理解為每次傳輸的數據包很小并且格式固定。

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

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

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

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

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

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

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

通過這種對信息的不斷轉發，以及對全局視圖表的信息更新，最終就可根據全局視圖表統計出整個機器人群體的數目。單個節點A上運行改進的Gossip協議具有以下通用的算法：

1.3 規模統計算法

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

圖1 主動進程數據包處理流程圖

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

圖2 被動進程數據包處理流程圖

2 性能測試及分析結果

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

圖3 機器人仿真環境（節點數:10）

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

2.1 可靠性

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

圖4 不同時間內機器人規模統計準確率

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

2.2 可擴展性

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

圖5 不同數目下機器人通訊量變化圖

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

4 結束語

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

[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.