陳曉松

0 引言

群體智能作為一個新興領(lǐng)域，自20世紀(jì)80年代出現(xiàn)以來，受到了學(xué)術(shù)界和各行各業(yè)的廣泛關(guān)注。如今，群體智能逐步從理論研究向工程應(yīng)用過渡。相比較抽象的行為算法，群體實驗越來越突顯其重要性。

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

在無線傳感網(wǎng)絡(luò)領(lǐng)域，通過無線廣播實現(xiàn)網(wǎng)絡(luò)中批量節(jié)點程序更新的研究總結(jié)如下。

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

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

1 系統(tǒng)框架

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

圖1 批量更新系統(tǒng)的工作流程

2 可靠數(shù)據(jù)分發(fā)協(xié)議

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

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

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

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

圖2 數(shù)據(jù)分發(fā)兩階段通信示意圖

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

圖3 應(yīng)答過程示意圖

當(dāng)某個已完成接收的節(jié)點接收到應(yīng)答信息時，它將會把此信息合并到自己的廣播中；當(dāng)基站接收到應(yīng)答信息時，它將把對應(yīng)節(jié)點的狀態(tài)設(shè)為“更新完成”。一旦所有節(jié)點都標(biāo)記為“更新完成”或超時，基站將發(fā)送“重啟”命令，宣告本次更新結(jié)束。

3 補丁文件

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

3.1 使用補丁進行程序更新

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

表1 指令定義

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

表2 更新程序過程示例

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

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

3.2 補丁生成方法

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

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

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

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

4 測試結(jié)果

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

圖4 通信實驗結(jié)果

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

5 總結(jié)

本文針對群體智能實驗中群體機器人的再編程問題，提出了基于無線廣播的高效可靠的批量節(jié)點程序更新方法。在無線傳感網(wǎng)絡(luò)領(lǐng)域相關(guān)研究的基礎(chǔ)上，考慮了群體機器人的特點，提出并論述了兩階段數(shù)據(jù)分發(fā)協(xié)議和面向字節(jié)的最小程序補丁生成方法。系統(tǒng)在實際應(yīng)用中體現(xiàn)出了高可靠性和高效率。驅(qū)動程序設(shè)計方案，較原來設(shè)計方案更加穩(wěn)定。

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