群體機器人程序更新系統的設計

陳曉松

0 引言

群體智能作為一個新興領域，自20世紀80年代出現以來，受到了學術界和各行各業的廣泛關注。如今，群體智能逐步從理論研究向工程應用過渡。相比較抽象的行為算法，群體實驗越來越突顯其重要性。

在功能調試過程中或需求發生改變時，使用者需要對機器人節點進行再編程。對于數量相當可觀的群體來說，依靠人力頻繁地對群體中所有節點逐個進行程序更新，將耗費巨大的時間成本。一種解決辦法是采用無線通信的方式（群體機器人一般具有無線通信功能），將新程序文件發送給需要再編程的機器人節點，讓節點進行自我更新。無線廣播的程序更新方式具有避免人工插拔、方便并行燒錄和在線更新程序等優點。

在無線傳感網絡領域，通過無線廣播實現網絡中批量節點程序更新的研究總結如下。

2003 年UC Berkeley公布了一種多跳無線傳感器網絡的數據分發技術[1]，其中提出的Deluge協議，很好地解決了可靠數據分發的問題。2010 年浙江大學的Wei Dong 提出以每個函數作為單元對程序進行更新的思路[2]。這種方法減少了通信量，但依賴于特定的編程語言和編譯器，對于不同的軟硬件平臺一般不具有可移植性。

與無線傳感網絡相比，群體機器人[3]程序更新具有其特殊性，如群體布局范圍有限，多數節點在相互的通信范圍之內；群體實驗中節點程序更新更加頻繁，要求更新過程能迅速收斂等。

1 系統框架

系統分為兩個部分，基站和待更新節點。基站根據待更新的目標程序和當前節點中運行的程序副本，生成補丁文件（即差異文件），并將文件廣播出去；節點接收到完整的補丁文件后，對其解碼，并進行自身程序的更新。更新完成后，節點向基站發送確認信號。實際通信中，使用可靠數據分發無線通信協議，確保所有節點都能快速地接收到完整正確的補丁文件。單個節點的更新過程，如圖1所示：

圖1 批量更新系統的工作流程

2 可靠數據分發協議

保證程序順利更新，首先要確保所有節點得到完整正確的目標程序數據。這就要求在不可靠的MAC層之上，設計一個可靠的運輸層數據分發協議。同時要提高通信效率和收斂速度。系統借鑒了 Deluge數據分發協議[4]并做了若干改進。

Deluge協議的設計初衷是用于進行較大規模的數據分發，比如大塊數據傳輸和遠程系統升級等。協議引入了復雜的控制信息，實現起來難度較高；同時，許多數據分發的應用場景提供Deluge 協議中的一些高級功能并不能明顯提升網絡性能，比如網絡節點較少則不需要流水線數據分發，數據塊較少則不需要分頁等。基于以上原因，論文在提出若干常見應用場景假設的基礎上，對Deluge 協議做了簡化和補充。

改進1：取消分頁，以一幀為單位進行空間多路傳輸。目標文件一般為補丁文件，即新舊程序的差值，文件較小(一般不超過5K)，不需要分頁。

改進2：分為兩階段通信。第一階段為“聽取”階段，由基站廣播目標文件，所有節點只負責接收；第二階段為“交流”階段，運行原Deluge協議，所有節點相互學習直至數據完整。整個數據分發過程類似于講課過程，第一階段類似于上課聽講，第二階段類似于課下討論。在群體實驗中，大部分節點都在基站的通信范圍之內（這與Deluge協議假設的場景不同），因此，“聽取”階段可以一次完成大部分數據的接收，顯著提高了分發效率，整個過程，如圖2所示：

圖2 數據分發兩階段通信示意圖

改進3：在“交流”階段增加了應答信息。應答信息只在已完成接收節點和基站之間使用，用于幫助基站統計已完成接收的節點，控制通信過程的收斂，其內容即為待確認節點的編號。應答信息寄存在Deluge協議MAINTAIN狀態下節點的廣播廣告中，和廣播一同發送和被接收。如圖3所示：

圖3 應答過程示意圖

當某個已完成接收的節點接收到應答信息時，它將會把此信息合并到自己的廣播中；當基站接收到應答信息時，它將把對應節點的狀態設為“更新完成”。一旦所有節點都標記為“更新完成”或超時，基站將發送“重啟”命令，宣告本次更新結束。

3 補丁文件

增量式程序更新方法[5]發送新舊程序之間的差異，即“補丁”，它包含程序更新所需要的全部信息。補丁文件一般比新目標程序小得多，因此傳輸效率更高。補丁文件要盡量小，以減輕通信壓力；同時由于單個節點的資源有限，使用補丁進行更新的時間和空間開銷要足夠小。

3.1 使用補丁進行程序更新

首先定義了集成補丁文件的5種指令。節點根據這些指令進行程序更新，更新的基本單位是字節。指令定長，為2個字節，前3比特為指令標志，具體定義，如表1所示：

表1 指令定義

這里，通過一個示例說明更新指令是如何工作的，如表2所示：

表2 更新程序過程示例

我們用“命令_長度/數據”的格式代表指令，以便更清晰地進行描述。假設某個群體機器人收到了補丁文件中指令集合為第一列所示，原程序為“ABCDEF GHIJKLMOPQ RSTUVWXYZ”。

可以看出，實際上使用Delete和Insert兩條指令就能夠完成程序的更新，引入Replace和Copy指令是為了減小補丁的尺寸。

3.2 補丁生成方法

設i和j，m和n分別代表原程序A和目標程序B中的當前偏移地址和長度。使用各個更新指令的必要條件和代價，注意 Copy和 Delete指令表示的最長連續字節數為213-1=8191，如表3所示：

表3 指令的必要條件和代價

在明確了指令產生的必要條件以及每條指令的代價后，可以得出求解最小差異文件長度的遞歸式。用Cost[i,j]表示從原程序的1到i字節更新為新程序的1到j字節所需的最小代價。

為了避免遞歸求解帶了的重復運算，可以使用動態規劃的方法求解這個遞歸式，并記錄指令序列。具體參考動態規劃方法求解最小編輯距離問題[6]。

4 測試結果

在確認使用補丁進行程序更新無誤的情況下，以分發數據長度和節點數目為變量對更新效率進行了測試。測試結果，如圖4所示：

圖4 通信實驗結果

其中左右子圖中的曲線分別顯示節點個數和數據長度與更新所需時間的關系。完成更新所需時間隨節點數目和數據長度增長而增長，但小于正比例增長關系。實際上，數據通信是影響更新速度的最大因素，其中第一階段通信時間與數據長度相關，第二階段通信受節點數目影響較大。更新的絕對時間還與具體的硬件相關。

5 總結

本文針對群體智能實驗中群體機器人的再編程問題，提出了基于無線廣播的高效可靠的批量節點程序更新方法。在無線傳感網絡領域相關研究的基礎上，考慮了群體機器人的特點，提出并論述了兩階段數據分發協議和面向字節的最小程序補丁生成方法。系統在實際應用中體現出了高可靠性和高效率。驅動程序設計方案，較原來設計方案更加穩定。

[1]Adam Chlipala, Jonathan Hui, Gilman Tolle. [M]"Deluge: Data Dissemination for Network Reprogramming at Scale" ,2003.

[2]Wei Dong, Yunhao Liu, XiaofanWu Lin Gu and Chun Chen Elon: EnablingEfficient and Long-Term Reprogramming [M]forWireless Sensor Networks 2010.

[3]Gerardo Beni, “From Swarm Intelligence to Swarm Robotics”. [C]Lecture Notes in Computer Science, 2005, Volume 3342/2005, 1-9, DOI: 10.1007/978-3-540-30552-1_1

[4]Hui J. and Culler, D. "The dynamic behavior of a data dissemination protocol fornetwork programming at scale," in Proceedings of the 2nd international conference onEmbedded networked sensor systems. [J]ACM Press,2004, pp. 81-94

[5]Michiel Konstapel "Incremental software updates for wireless sensor networks"Master's Thesis [J]in Computer Science, May 24, 2006

[6]Levenshtein VI (1966)."Binary codes capable of correcting deletions, insertions, and reversals".[J]Soviet Physics Doklady 10: 707–10.