基于改進Bsdiff算法的車載診斷系統遠程升級系統

錢楓 易齊 祝能 王潔

關鍵詞：汽車主動安全；車載診斷（OBD）系統；遠程升級；Bsdiff算法；閃存分區；固件更新

隨著車載診斷（on-boarddiagnostics，OBD）系統終端在汽車上安裝的普及和固件功能的逐漸復雜，車載終端在運行的過程中，一些設計缺陷和軟件漏洞逐漸暴露；同時，隨著車載OBD終端國家相關法規的完善，舊的固件包已經不能滿足相關法規的功能需求，升級現有的固件程序在所難免。當前的固件程序升級流程分為現場升級和全量遠程升級。現場升級每次更換新固件程序需要耗費大量的時間和人力，增加了服務成本。全量遠程升級需要將新版本固件包完整發送給車載OBD終端設備，這不僅讓車載OBD終端設備在使用網絡數據的過程中需要支付高昂的流量費用，而且在傳輸整個新版本固件包的過程中，必然會耗費大量時間和占用大量網絡帶寬，更容易由于不確定的外界環境因素導致系統崩潰。因此如何提升車載OBD終端設備遠程升級固件包安裝的穩定可靠性、減小固件包傳輸體積及提高固件包傳輸速率成為研究和發展的重點。

空中下載升級（overtheair，OTA）[1]是指利用無線通信技術，通過云升級技術，為聯網設備進行遠程管理與升級，分為固件遠程升級（firmwareovertheair，FOTA）和軟件遠程升級（softwareovertheair，SOTA）兩類。

已有大量針對遠程升級的相關研究。D.Makowski等人在xTCA系統上首次嘗試采用智能平臺管理接口標準完成設備的固件升級[2]。Y.Kwon等提出了一種適用于無線傳感器網絡的升級模型[3]。高柱榮等對閃存進行了科學的分區、Bootloader程序進行了簡化、終端的升級操作引入了時效性和服務器IP地址隱藏化，實現了安全、可靠的遠程升級[4]。沈偉等提出了安全穩定、批量化直流充電機遠程升級系統，該系統在升級文件傳輸的過程中不影響充電機的正常業務，同時支持斷點續傳和批量升級[5]。K.MAYAMA等提出了針對RTCCANopen的固件更新系統，該升級系統可以在線控制自動固件更新的整個過程[6]。

江蘇大學施超、鮑可進等提出基于MTK平臺和Spreadtrum平臺實現Android操作系統遠程升級，提出了服務器端自動制作差分升級包的方法，并采用Recovery機制和分區備份的方法來處理軟件系統升級中斷電的情況[7]。電子科技大學夏棋等對增量數據差分更新算法進行了一系列研究，基于二進制文件差分更新算法，提出了一種減少個人云存儲系統中文件更新時傳輸流量的方法，同時解決了在用戶云存儲系統中更新策略的沖突化解問題[8]。劉洋和王劍等基于Bsdiff差分算法和FastLz77壓縮算法有效地減小了固件包的大小，同時使用跳頻和循環異或加密技術，提出了一種適用于LoRa通信設備的固件遠程升級方法[9]。高柱榮和蔣昌茂等采用雙APP程序分區方案，基于應用程序編程技術設計了燃氣表終端遠程升級系統，一定程度上解決了物聯網燃氣表終端遠程升級過程中被惡意攻擊、固件文件安全傳輸和可靠更新等問題[10]。沈偉、衛龍龍等設計了遠程升級直流充電機系統并提出了升級方法，該系統及方法支持斷點續傳和批量升級，并穩定有效保證了充電機正常的充電業務和數據通信[11]。殷杰對Bsdiff算法進行了優化并采用混合加密算法來解決FOTA終端的時效性問題與安全性問題[12]。

遠程升級技術已在各傳統領域得到了廣泛的應用。針對車載OBD終端設備現場升級方法服務成本高及維護難度大和全量遠程升級占用較大網絡帶寬和性能不穩定等問題，本文設計了一種基于改進Bsdiff算法的OBD遠程升級系統，首先闡述了差分算法的基本原理，并對Bsdiff算法進行了優化，然后介紹系統的基本組成，并對閃存（flashmemory，Flash）分區進行了優化設計，闡述了差分包的上傳、下發步驟，最后對SpringBoot和STM32F103搭建的測試環境進行全量升級和差分升級對比試驗，驗證該系統相較于全量遠程升級系統各方面性能指標有大幅度提升。

1算法分析

1.1Bsdiff差分算法

差分升級是指進行固件升級的時候，只對固件變更的地方進行升級，未做變更的地方保持不變。實際流程是：在開發端，以舊版本固件作為基礎，對新版本固件和舊版本固件進行差分對比，生成一個補丁文件；在客戶端，以舊版本固件作為基礎，合并補丁文件還原新版本固件進行安裝，如圖1所示。

生成補丁文件的核心是使用差分算法對新舊版本固件進行差分計算。目前應用廣泛的二進制文件差分算法有：Xdelta、RTPatch、Exediff、Bsdiff等算法。為了評估這些差分算法在計算補丁文件時的壓縮率和性能，本文使用了參考文獻[13]中的結論，該文獻對比、分析了補丁文件的壓縮率。本文主要列舉了3種二進制文件：Agrep、gcc、Alimpse，對比分析結論見表1所示。

從表1中可以看出：對于二進制文件來說，Xdelta算法的壓縮率最低，Exediff算法壓縮率最高，其次Bsdiff算法壓縮率最高。但是Exediff算法對運行的平臺有嚴格要求，所以本文采用能獨立于平臺的Bsdiff算法實現補丁文件的制作。

Bsdiff算法[14]是較為高效的差量更新算法，由于該算法生成的patch補丁文件體積小，因此在各領域得到了廣泛應用[15]。Bsdiff算法分為diff過程和patch過程，diff過程是在開發端對新版本固件與舊版本固件進行差分計算、編碼和壓縮，從而產生補丁文件。patch過程是在客戶端以舊版本固件為基礎，按照規定的解碼規則還原出補丁文件并和舊版本固件進行合并，從而構建出新版本固件進行安裝[16]。

Bsdiff算法首先申請兩個輔助空間并創建一個空的補丁文件，然后采用快速后綴排列算法對舊版本固件的所有后綴按字典順序進行排列得到后綴數組SA[·]，經過逆運算后得到名次數組RANK[·]，如表2所示為以AABAB為例的SA[·]和RANK[·]生成過程中下標位置變化的次數[17]。

利用舊版本固件的后綴數組和二分查找算法檢索新版本固件和舊版本固件中的相似匹配區域與不匹配區域。接下來，對所有近似匹配執行相減操作并記錄下近似匹配區域數據的差值和不匹配區域的內容，最后，快速打包出補丁文件。由于這些相似區域數據的差值包含大量的零值，所以可以使用bzip等壓縮算法壓縮該部分差值，以減少補丁文件的大小[18]。整個補丁文件包括頭部區域、控制區域、差分區域和擴展區域4個部分。

Bsdiff算法在客戶端對新版本固件進行恢復的過程中，首先會申請開辟2個輔助空間并創建3個并行的解壓進程，并分別用于對補丁文件中的控制區域、差分區域和擴展區域進行解壓。然后執行2類操作：復制操作，依據控制區域解壓縮提取的控制信息，對差分區域解壓縮獲得的數據與舊版本固件中對應數據執行相加操作并將生成的數據塊復制到指定區域；插入操作，將擴展區域解壓縮獲得的數據插入到指定區域。圖2所示為新版本固件的恢復流程。

1.2Bsdiff算法優化

通過對Bsdiff算法流程的分析可知，Bsdiff算法生成的補丁文件差分區域數據存在大量冗余零值是目前差分算法的不足。針對該問題，本文以減小補丁文件體積及多線程分包下發為核心思想，對差分區域數據進行了去冗優化，并將補丁文件進行分包處理，采用多線程機制對車載OBD終端進行補丁下發。該方法不僅減少云平臺與車載OBD終端的通信開銷和數據傳輸時間，使數據傳輸更穩定；而且，在車載OBD終端節約內存開銷，讓其他應用程序運行更加穩定，整個系統運行速度更加流暢。

如圖3所示為Bsdiff算法去零流程圖。步驟如下：

步驟1：使用Bsdiff算法處理新舊版本固件，以獲取補丁文件；

步驟2：移動標志指針p的位置，讓其指向差分區域首地址；

步驟3：掃描差分區域，若標志指針p掃描到的是零值，則不做統計與序列編碼，標志指針p直接向后移動一位；若標志指針p掃描到的是非零值，則對該段字節序列進行差值統計，并插入特征字節；

步驟4：重復步驟3直到差分區域字節數據全部編碼完成，最終得到sim-diffblock；

步驟5：掃描差分文件，讀取頭部區域、控制區域、差分區域和擴展區域字節數據臨界位置信息，并對該信息進行序列編碼與存儲。

對差分文件的非零值進行統計和序列編碼消除了大量冗余零值，減小了差分文件的體積，有利于提高云平臺與車載終端之間的數據傳輸速度，節省車載終端內存消耗。

云平臺一般同時備案與管理數千臺車載OBD終端，車載OBD終端之間寬帶共享。如果每臺車載OBD終端的優先級相同，多臺終端設備一起連接到該云平臺并請求升級差分文件，那么每個車載終端所使用的實際帶寬就是云平臺帶寬的均分。所以，如果接入的車載終端數量較多，則每個車載終端所占用的帶寬十分有限，差分文件的下載將十分的耗時，導致遠程升級的效率十分低下。

為充分利用服務器網絡帶寬資源，提高車載OBD終端CPU的利用率和差分文件傳輸效率，本文采用了多線程分包傳輸方案，如圖4所示為多線程差分文件下載流程圖。步驟如下：

步驟1：車載OBD終端請求升級，并下載記錄了差分包屬性值的配置文件；

步驟2：車載OBD終端根據步驟1獲取的差分包屬性信息確定分包參數，包括各片文件大小pieceSize、總片數pieceCount及每片的pieceNumber；

步驟3：車載OBD終端創建差分文件下載任務，并攜帶著分包參數向云平臺發送請求，以獲取文件分片記錄信息；

步驟4：根據步驟3讀取的文件分片記錄信息，車載OBD終端創建pieceCount個線程并分別與云平臺連接，然后發送指定分片文件下載指令；

步驟5：車載OBD終端對pieceCount個線程進行統一管理，并記錄各自片文件下載信息；

步驟6：主線程監聽各子線程數據下載完成進度，如果未下載完畢繼續等待步驟4，直到各線程片文件下載完成后，進行新版本固件的恢復操作。

2系統設計

本文設計的車載OBD遠程升級系統由車載OBD終端、本地開發環境和FOTA云平臺組成，見圖5。車載OBD終端搭載ThreadX操作系統，外接安全芯片、4G聯網、應用調試等模塊，見圖6。

本地開發環境主要負責通過DS-5開發工具進行固件代碼的編寫、通過msys64開發工具對固件進行編譯和通過Bsdiff算法腳本制作差分包；FOTA云平臺主要負責車載OBD終端設備管理、遠程升級任務的管理、升級包的管理、遠程升級任務的下發和升級狀態與數據的監測。

2.1改進閃存分區設計

傳統閃存分區方式將片內閃存劃分為Bootloader引導區和用戶主程序區，如圖7a所示。這種劃分方式需要借助片外閃存來完成遠程更新操作，具體整包升級流程如下。

步驟1：下載更新包數據并保存至片外閃存；

步驟2：重啟設備，進入引導程序；

步驟3：將更新包數據從片外閃存拷貝到片內主程序區；

步驟4：執行新版本程序。

通過分析可知，傳統閃存分區方式不僅浪費閃存空間，而且在片內閃存和片外閃存數據交換上耗費大量時間。對此本文提出了一種動態調整分區空間的閃存分區方式，將閃存劃分為6個區域，如圖7b所示，分別為Bootloader引導區、fota_param區、fota_pkg區、主分區、空閑區和備份區，其中空閑區屬于主分區，主要用于處理程序中的壞塊問題，以提高系統運行的穩定性。fota_param分區用來存放升級時的一些重要參數信息，fota_pkg分區用來存儲升級包。主分區和備份區通過一個字節的標志位來區分，本系統中0代表主分區，1代表備份區。主分區用于存放需要運行的程序。

優化后的更新操作如圖8所示。具體差分升級流程如下。

步驟1：下載參數文件和差分包數據，并將其分別保存至fota_param分區和fota_pkg分區；

步驟2：合并、釋放備份區和空閑區，并將其劃分為一個新的備份區；

步驟3：由步驟1中的fota_param參數信息對備份區進行重新劃分，并將新版本固件包數據寫入剛劃分好的主分區中；

步驟4：固件升級完成，重新設置主分區和備份區的標志位，加載指針跳轉至主分區程序入口，執行新版本程序。

本文采用動態調整分區空間的方式來操作閃存內存空間，與傳統操作閃存內存方式相比，具備以下優勢：無需申請片外閃存空間，有效的節約了嵌入式設備中緊張的存儲資源；主分區與備份區的交替使用，提高了閃存存儲空間的利用率；避免執行傳統整包升級過程中耗時的數據拷貝與數據擦除操作，提高了固件更新的效率。

2.2遠程升級網絡結構

在車載OBD遠程升級系統中，車載終端升級程序主要任務是通過TCP協議請求連接到服務器并維持心跳，在此期間，向服務器發送固件版本對比請求、處理服務器反饋結果和其他信息數據流等。服務器應用程序的主要任務是可以同時接受多臺終端設備的接入和有序地處理多臺客戶端的請求并及時做出有效響應。考慮到移動終端設備的唯一性和合法性，每臺車載OBD終端上都會綁定唯一的IMEI編號，當車載OBD終端請求遠程升級之前，首先會攜帶著終端設備上的IMEI編號進行備案，備案請求通過之后才允許進行遠程固件升級[19，20]。這種網絡拓撲結構如圖9所示。

2.3遠程升級流程

遠程升級分為4個部分：補丁包制作、補丁包上傳、補丁包下載和舊版本固件升級。遠程升級流程如圖10所示。

根據優化后的差分算法制作可執行文件Bsdiff.exe，使用該Bsdiff.exe差分工具對舊版本system文件和新版本system文件進行字節對比，生成最小系統差分包和非最小系統差分包2個差分文件。然后，將這兩個差分文件上傳到遠程升級云平臺中，創建設備分組并下發升級任務。升級時首先下載最小系統差分文件，下載完成后重啟進入updater升級。完成最小系統的升級后重啟運行的就是最新的可聯網的最小系統，然后再下載非最小系統升級文件，下載完成后校驗，校驗通過后整個升級完成。

3實驗對比分析

本文OBD車載終端設備使用ARMCortex-R5應用處理器，搭載FreeRTOS操作系統實現遠程升級。使用IBMX350M4作為服務器（Intel（R）Xeon（R）CPUE5～2680v3@2.50GHz），操作系統為CentOS7.364位，采用Java開發語言配合SpringBoot后端框架編寫服務接口，數據庫采用MongoDB，前端頁面使用Vue框架開發OTAWeb管理系統。

基于以上硬件和服務器環境分別進行優化前的差分升級、優化后的差分升級和傳統的全量遠程升級試驗。使用本地開發環境生成從Test_V1.bin到Test_V5.bin一組測試固件包作為本次實驗樣本。本次實驗所用的樣本數據如表3所示，其中從Test_V1.bin到Test_V5.bin文件大小逐步變大，其代碼差異也逐步變大。為消除網絡、本地環境等隨機誤差，每個樣本均測試30次。本文以全量遠程升級和差分升級過程中壓縮率和編譯運行時間作為主要評價指標。

對比中壓縮率定義為相較于全量遠程升級，通過差分升級減少的數據編譯、傳輸大小的程度。壓縮率越大，表征差分算法性能越好，數據編譯時間、傳輸時間、設備功耗、內存占用及網絡流量占用較少。對比結果如表3所示。

從表3中Ⅰ、Ⅱ、Ⅲ組試驗可以看出：當試驗樣本文件較小時，優化前的差分升級算法壓縮率較大，最高可達68.72%。

從Ⅳ、Ⅴ組試驗可以看出：當試驗樣本文件較大時，優化后的差分升級算法具有明顯優勢，壓縮率可以達到82.30%，相較于優化前的差分升級算法，壓縮性能提高了23.55%。本文優化后的差分算法具有良好的壓縮性能。且壓縮率與試驗樣本的文件大小呈現非線性的正相關。

由表4可知，對比全量遠程升級，差分升級在編譯運行時所耗時間顯著減少；在試驗樣本文件較小時，優化前的差分升級和優化后的差分升級編譯運行時間相差不大；在試驗樣本文件較大時，相較于優化前的差分升級，優化后的差分升級編譯運行時間更短，在第Ⅴ組試驗中，優化前的差分升級編譯耗時42.7s，優化后的差分升級編譯耗時31.6s，節省約26%的編譯運行時間，提升效果明顯，優化后的差分升級算法優越性顯著。

差分升級、全量遠程升級傳輸時間對比和占用內存對比實驗測試數據同樣使用Test_V1.bin到Test_V5.bin該組測試固件包，最終測試結果如圖11、圖12所示。

對圖11分析可得，使用本文優化后的差分升級算法，平均可以減少約73.78%的數據傳輸時間。在試驗樣本文件較小時，優化前差分升級和優化后差分升級傳輸耗時接近，提升比率相差不大。在試驗樣本文件較大時，如第Ⅴ組試驗，優化后差分升級傳輸時間更短，耗時5.9s，提升比率為79.15%，相較于優化前差分升級算法，高出17.31%。

圖12表明在內存開銷方面，當測試包文件較小時，優化后差分升級算法優勢不太明顯，當文件較大時，優化后差分升級算法對比全量遠程升級和優化前差分升級算法，提升明顯，最高可達到約80%。

在測試環境下上述對比試驗表明：相較于優化前差分升級算法，優化后的差分升級算法在壓縮率、編譯運行時間等指標上均有顯著提升。為進一步驗證優化后差分升級實際性能表現及以上試驗結論，進行如下升級試驗，該試驗在實際環境下進行，基于以上硬件和服務器環境分別進行優化后差分升級和全量遠程升級。使用本地開發環境對新版本固件源碼進行編譯得到250MB的新版本固件包，編譯期間耗時8min，并使用新版本固件進行了30次全量遠程升級測試，平均下載時間4min，平均安裝時間為15min。根據2.3所述的遠程升級流程制作了大小為47MB的補丁包文件，補丁包制作期間耗時3min，并使用補丁文件進行了30次差分升級，平均下載時間2min，平均安裝時間2min。測試結果如表5所示。

表5表明：相比于全量遠程升級，優化后差分升級補丁文件要小，編譯耗時要少，下載時間要短以及安裝速度要快，極大地提高了車載OBD的遠程升級效率和減少了遠程升級文件傳輸的流量消耗。

4結論

本文設計的一種基于改進Bsdiff算法的車載診斷系統遠程升級系統。主要在以下方面做了優化：

1）針對原Bsdiff算法生成的補丁文件差分區域數據存在大量冗余零值的問題，本文以減小補丁文件體積及多線程分包下發為核心思想，對差分區域數據進行了去冗優化，并將補丁文件進行分包處理，采用多線程機制對車載OBD終端進行補丁下發；

2）對單片機閃存分區做了優化設計，采用動態調整分區空間的方式提高了閃存空間的利用率，避免了傳統閃存分區執行更新操作時拷貝數據、擦除數據等耗時操作，提高了固件更新效率。

實驗數據證明了在車載OBD終端設備上采用差分遠程升級的可行性和可靠性。同時，與全量升級方法相比，采用優化后差分升級的方法在文件大小方面減小了203MB，性能提升81.2%；在文件編譯、固件包下載及安裝的時間方面性能分別提高了62.5%、50.0%和86.7%。從而，本文的升級系統提高了車載終端遠程升級的效率。