陳迪榮，包曉安，杜 鵬，胡逸飛，蘇鴻斌

(浙江理工大學 信息學院，浙江 杭州 310018)

物聯(lián)網(wǎng)被視為繼計算機、互聯(lián)網(wǎng)之后信息技術產(chǎn)業(yè)發(fā)展的第三次革命[1-2]?；谖锫?lián)網(wǎng)技術的智能可穿戴設備、智能家居、智能傳感器等應用越來越成熟[3-5]，相應的應用端業(yè)務的更新和迭代也越來越頻繁。由于終端設備數(shù)量龐大且布設范圍廣，為了更好地維護相應的設備，遠程在線更新固件的功能十分重要[6]。傳統(tǒng)的遠程固件更新通常采用全量更新的方式。這種更新方式往往需要長時間占用網(wǎng)絡帶寬，同時還可能會出現(xiàn)丟包、斷連等情況，不僅增加流量資費，還增加終端設備功耗[7]。因此，減少更新傳輸?shù)臄?shù)據(jù)量，提高升級的效率是物聯(lián)網(wǎng)終端設備遠程更新需要解決的關鍵問題。

文獻[8]基于LWM2M 協(xié)議對物聯(lián)網(wǎng)云平臺進行優(yōu)化，提高了遠程更新的通用性、可靠性和穩(wěn)定性。文獻[9]針對無法主動進行聯(lián)網(wǎng)更新的終端設備，提出了通過與終端設備相連的主控設備進行郵遞式升級的方案。但是該方案沒有對接云平臺，在批量作業(yè)中缺乏靈活性。文獻[10]通過改進BSDiff算法生成的補丁文件格式，提高了終端打補丁的效率。文獻[11]在文獻[10]改進的補丁文件的基礎上，將BSDiff 算法中的并行解壓過程替換為串行解壓，并減小了申請的輔助空間，提出了一種節(jié)約內(nèi)存的增量更新算法。文獻[12]設計了一套安全備份和校驗機制，保證遠程升級過程中數(shù)據(jù)傳輸完整可靠，并使用差異文件減少升級的流量消耗。目前，除了軟件升級方面，增量更新還被廣泛應用于數(shù)據(jù)同步、云存儲、蛋白質(zhì)序列比較等場景[13-14]。

以上研究從遠程更新平臺設計、終端設備升級過程以及增量更新的應用進行了分析。由以上分析可知，通過增量更新的方式可以有效減少傳輸?shù)臄?shù)據(jù)量，提高終端設備更新的效率。本文以減少需要傳輸?shù)母聰?shù)據(jù)量為核心思想，對更新服務端的固件管理方案進行優(yōu)化，采用改進的BSDiff差分算法即時生成新舊固件的增量更新文件，減少需要傳輸?shù)母聰?shù)據(jù)量，進而提升了終端設備遠程更新的效率。

1 算法分析

1.1 BSDiff差分算法

可執(zhí)行文件之間的差異復雜，源文件中的微小更改可能會在整個可執(zhí)行文件中造成重大更改。BSDiff差分算法的提出針對可執(zhí)行文件更新前后變動的兩個重要規(guī)律[6，15]：(1)在一個可執(zhí)行文件中，不受修改直接影響的那一部分，差異通常很小，修改后的地址可能僅改變其最低有效的一個或兩個字節(jié)；(2)更新后的代碼和數(shù)據(jù)會有較大的位置變動，但這種變動大多為整塊的移動，即某一塊位置中代碼內(nèi)的指針地址變動均會有相同的位移值。因此相同源代碼對應的兩個代碼塊中，大部分內(nèi)容字節(jié)差為0，而少部分需要更新的地址位移數(shù)據(jù)又存在大量相同的位移值。如圖1所示，截取的是V3和V4這兩個功能一致的相鄰版本固件通過Beyond Compare3軟件進行差異對比后的部分內(nèi)容，可以看到大部分的字節(jié)差異為0，這樣的字節(jié)差異字符串就具有高度可壓縮特性。

圖1 Beyond Compare3差異比較結(jié)果

基于以上特性，通過BSDiff差分算法即可生成高度壓縮的補丁包，其具體步驟如下：

步驟1讀取舊文件，使用后綴排序或者哈希算法生成字符串索引；

步驟2使用該索引遍歷新文件，生成差異文件和新增文件；

步驟3將差異文件和新增文件以及必要的索引控制信息進行壓縮，生成補丁包。

步驟1是目前增量更新算法的瓶頸部分。BSDiff算法采用了qSufSort后綴數(shù)組算法來進行索引的生成。該算法的基本思想是，后綴的后綴是字符串中后綴的前綴，并且已經(jīng)在后綴數(shù)組的另一個區(qū)域中部分排序。因此，不再使用已經(jīng)比較過的字符，而是使用現(xiàn)有的部分結(jié)果。該算法時間復雜度為O(nlogn)，空間復雜度為O(n)。算法偽代碼如下[16]：

def qSufSort(T)

Sort suffixes Si according to their first character into SA

Init additional arraysVandL

h:= 1

while(-L[0]!=n):

Sort suffixes Si in unsorted groups in SA byV[i+h]

Mark borders of Aleft，Amiddle and Aright

Calculate new groups

UpdateVandL

h=h·2

1.2 DivSufSort后綴數(shù)組構(gòu)造算法

后綴數(shù)組的有效構(gòu)造是一個研究熱點，目前已經(jīng)有許多優(yōu)秀的后綴數(shù)組構(gòu)造算法，其中DivSufSort是目前實踐上速度最快的后綴數(shù)組構(gòu)造算法[16]，其理論時間復雜度為O(nlogn)。此外，還有時間復雜度為O(n)的SAIS算法。DivSufSort與SAIS算法都是基于誘導排序的后綴數(shù)組構(gòu)造算法，但是DivSufSort更快。其主要原因可以歸為兩點[17-18]：首先，SAIS算法通過遞歸的方式對初始后綴進行排序，而DivSufSort采用了實際運行時更快的字符串排序和類似前綴倍增的方式，同時還采用了重復檢測等方法，進一步減少了運行時間；其次，在SAIS算法中，已被初步排序的后綴在之后的誘導過程會被移動，而在DivSufSort算法中則保持不動。這使得DivSufSort算法在第一階段的誘導過程中可以更快。Google對以上后綴數(shù)組構(gòu)造算法進行了運行時間以及內(nèi)存空間占用上的對比，對比結(jié)果如下表所示。

綜合表1、表2可知，在運行時間上，DivSufSort表現(xiàn)明顯優(yōu)于qSufSort，平均提升了61.10%。而在內(nèi)存空間占用上，DivSufSort的表現(xiàn)僅次于SAIS。相較于qSufSort，DivSufSort平均減少了約35.51%的內(nèi)存空間占用。

表1 運行時間對比

表2 內(nèi)存空間占用對比

2 遠程增量更新方案設計

為了提高終端設備遠程更新的效率，本文以減少需要傳輸?shù)母聰?shù)據(jù)量為核心思想，采用遠程下發(fā)增量更新包的方式進行終端設備的更新。遠程增量更新方案以BSDiff差分算法為核心，可以生成高度壓縮的增量更新包，有效減少傳輸?shù)臅r間和數(shù)據(jù)量。此外，選用性能更高的DivSufSort后綴數(shù)組構(gòu)造算法還可對BSDiff差分算法進行改進，以提高差分算法的運行效率。遠程增量更新系統(tǒng)整體框圖如圖2所示。首先，在增量更新服務平臺進行終端設備固件版本號的比對；然后在增量更新服務平臺運行改進的BSDiff差分算法，生成新舊版本固件之間的增量更新包；最后，終端設備通過物聯(lián)網(wǎng)無線傳輸網(wǎng)絡請求增量更新包數(shù)據(jù)，終端設備執(zhí)行BSPatch程序構(gòu)造完整的更新包。校驗通過后，終端設備執(zhí)行升級程序。

圖2 增量更新方案整體框圖

2.1 改進的BSDiff差分算法

改進BSDiff差分算法生成補丁包的具體步驟與原先的BSDiff差分算法相同，其主要區(qū)別在于使用DivSufSort后綴數(shù)組構(gòu)造算法對步驟1中生成舊文件的字符串索引的過程進行了改進。具體分為3個階段[16]：

(1)對舊文件進行一次掃描，確定所有后綴的類型，并計算相應的c0和(c0，c1)的桶邊界；

(2)對所有B*后綴進行排序，并將它們放置在SA中的正確位置。首先必須對B*子字符串進行排序。然后，使用排序后的B*子字符串的等級對相應的B*后綴進行排序；

(3)對SA進行兩次掃描，以得出所有剩余后綴的正確位置，從而得到字符串索引。首先從右向左掃描以誘導所有B后綴，然后從左向右掃描以誘導所有A后綴。

2.2 遠程更新服務平臺分析

遠程更新服務平臺主要實現(xiàn)遠程更新的管理控制功能，包括固件包的管理、版本控制以及更新數(shù)據(jù)下發(fā)等。傳統(tǒng)的全量更新方案一般只需要在更新服務平臺保留一個最新版本的固件包。這種方案使得更新服務平臺的控制邏輯變得較為簡單，但是由于每次更新都需要向終端設備發(fā)送整個固件包，這就導致終端設備需要長時間連續(xù)的與更新服務平臺進行數(shù)據(jù)通信，終端設備耗電量大，更新效率低。當同一時段請求更新的設備過多，還會對更新服務平臺造成較大的壓力。

傳統(tǒng)的增量更新方案需要在更新服務平臺進行增量更新包的集中管理，當終端設備進行鄰近版本更新時，只需發(fā)送一個相應的包。由于這些增量更新包通常是高度壓縮的，可以有效減少更新時傳輸?shù)臄?shù)據(jù)量。但是當設備需要跨越多個版本進行更新時，更新服務平臺則需要多次發(fā)送補丁包，這使得終端設備的更新效率有所降低。

2.3 改進的增量更新服務平臺

與傳統(tǒng)遠程更新服務平臺方案不同，本文設計的增量更新服務平臺需要保留用戶上傳的每一個版本的固件包，這是因為無法保證所有的終端設備都已經(jīng)及時升級到最新版本，而增量更新包需要通過對比新舊兩個版本的固件才能生成。雖然這會消耗更新服務平臺更多的存儲空間，但是這使得終端設備可以更加方便地進行版本回退以及跨版本更新等操作，給終端設備地更新帶來了更多的靈活性。在增量更新包的生成上，根據(jù)終端設備的版本查詢請求，在更新服務平臺即時地生成增量更新包。增量更新包的生成基于BSDiff差分算法，并且使用運行效率更高的DivSufSort后綴數(shù)組算法對其進行優(yōu)化，提高增量更新包生成的效率。同時，新生成的增量更新包還需要在更新服務平臺保留一段時間，以便提供給有相同更新需求的終端設備使用，提高更新服務平臺的效率。

3 實驗及結(jié)果分析

本文實驗的終端設備選用樂鑫科技的ESP8266物聯(lián)網(wǎng)芯片，更新服務平臺則搭建在云端，操作系統(tǒng)為Linux，版本為Ubuntu16.04，實驗樣本的具體數(shù)據(jù)如表3所示。其中V1為功能實現(xiàn)的初始版本，V2在V1的基礎上增加了新功能并在整體上進行了完善，V3、V4針對一些運行時出現(xiàn)的問題進行了修復，其中V4為最終版本。從V1到V4，代碼差異逐版本減小。

表3 增量更新測試文件

3.1 評價指標

本文以差分過程耗費的時間和傳輸數(shù)據(jù)壓縮率分別作為差分算法和遠程增量更新系統(tǒng)的主要評價指標。定義壓縮率Rcmp的計算方法如下

Rcmp=(Nnew-Ndate)/Nnew×100%

(1)

式中，Nnew為目標更新版本固件包的總字節(jié)數(shù)；Ndate為傳輸數(shù)據(jù)的總字節(jié)數(shù)；壓縮率Rcmp表示相較于全量更新，通過增量更新可以減少的傳輸數(shù)據(jù)量的程度。壓縮率越大，表示增量更新系統(tǒng)性能越高，傳輸時間、設備功耗以及網(wǎng)絡流量開銷越少。

3.2 實驗設計與分析

實驗通過在Linux命令行運行BSDiff差分算法來仿真更新服務端進行差分運算并獲取指定更新包的過程，通過運行time指令來獲取BSDiff算法運行的準確時間。

在實驗開始前，先將終端固件手動燒寫成V1版本，并根據(jù)實驗場景在服務端上傳指定的更新包。然后，觸發(fā)終端設備更新指令，使用http協(xié)議向服務端請求指定更新包。終端設備接收完成后，校驗更新包，校驗通過則進入更新流程。最后，通過查看終端設備日志確認版本是否更新。

實驗設計了終端設備鄰近版本更新與跨版本更新兩種場景，分別對比了全量更新方案、傳統(tǒng)的增量更新方案以及本文設計的優(yōu)化增量更新方案在這兩種場景下的表現(xiàn)，實驗結(jié)果如表4和表5所示。

表4 鄰近版本升級

表5 跨版本升級

在鄰近版本更新時，相較于全量更新方案，改進的增量更新方案的數(shù)據(jù)壓縮率與傳統(tǒng)的增量更新方案相同，平均能達到96.80%的壓縮率。但是，改進的方案傳輸?shù)臄?shù)據(jù)量平均多了10 Byte。這是由于BSDiff差分算法在處理某些文件時間過長，因此對BSDiff差分算法中查找最大相似字符串的過程進行了改進。

在跨版本升級的場景下，改進的增量更新方案的數(shù)據(jù)壓縮率平均達到了95.09%。對比傳統(tǒng)的增量更新方案，改進增量更新方案的整體數(shù)據(jù)壓縮率平均提高了2.07%，并且從代碼差異最小到最大的版本變更情景中，提高的壓縮率從1.19%上升到了3.3%，說明改進的增量更新方案在跨版本升級時，隨著版本之間的代碼差異增大，其優(yōu)勢也隨之增加。這是由于傳統(tǒng)的增量更新方案在跨版本升級時需要發(fā)送多次patch包，導致重復發(fā)送了部分相同的差異字段與索引控制信息，而改進方案只需要發(fā)送一次。

此外，實驗針對不同大小的文件，對BSDiff與改進BSDiff差分算法的差分性能進行了比較，結(jié)果如圖3以及表6所示。改進BSDiff差分算法在生成增量更新包時，其平均處理時間比原先的BSDiff差分算法平均減少了31.19%，同時，對于原先導致BSDiff算法長時間運行的特殊測試用例，即最后一組數(shù)據(jù)所示的情況，改進BSDiff算法也能進行高效處理。

表6 差分算法運行時間

圖3 差分算法性能比較

從實驗結(jié)果與分析可知，本文所提出的改進增量更新方案可以高效地對需要傳輸?shù)母聰?shù)據(jù)進行壓縮，從而提高遠程更新的效率，達到節(jié)省終端設備功耗的目的。在跨版本更新時，也可以有效減少需要傳輸?shù)臄?shù)據(jù)量，并且版本之間代碼差異越大，其效果就越明顯。此外，改進BSDiff差分算法在運行時間上，相較于原先的BSDiff差分算法也有較大提升，整體上可以將差分運算的時間控制在秒級，達到了預期結(jié)果。

4 結(jié)束語

本文研究了物聯(lián)網(wǎng)終端設備的遠程增量更新方案，綜合考慮了傳統(tǒng)全量更新方案需要傳輸?shù)臄?shù)據(jù)量大但是更新過程簡單，以及傳統(tǒng)增量更新方案傳輸?shù)臄?shù)據(jù)量小但是跨版本更新性能弱的特點，對兩種方案的優(yōu)缺點進行了整合和改進，提出以改進的BSDiff差分算法來減少更新需要傳輸?shù)臄?shù)據(jù)量，同時優(yōu)化更新服務平臺的固件管理方案，從而達到節(jié)省傳輸流量，提高終端設備更新效率的目的。本文對方案進行了仿真驗證，并取得了預期結(jié)果。使用BSDiff差分算法進行終端設備的遠程增量更新可以有效減少需要數(shù)據(jù)量，提高終端設備的更新效率。但大量的物聯(lián)網(wǎng)終端設備內(nèi)存小，資源有限，而運行BSPatch構(gòu)建新版本固件時內(nèi)存消耗大，因此在保持較高壓縮率的同時減小終端設備的內(nèi)存消耗也是一個重要的研究課題。