一种改进的固件增量更新算法

doi:10.19678/j.issn.1000-3428.0056426

摘要/Abstract

摘要： 针对bsdiff算法在嵌入式设备固件更新中构建新版本固件时内存消耗大的问题，提出一种节约内存的增量更新算法。利用改进的bsdiff算法的补丁文件格式，避免应用补丁文件时记录并频繁计算地址偏移量。将bsdiff算法中的并行解压过程更换为串行解压，并通过分批处理数据以减小需要的辅助空间。同时，将非对称的无损压缩算法应用到改进后的增量更新算法的压缩与解压缩过程，降低由于解压缩补丁文件而造成的较大内存消耗。实验结果表明，与bsdiff算法、xdelta算法、vcdiff算法、zdelta算法相比，该算法能够有效减少构建新版本固件时的内存消耗，且具有良好的压缩性能。

关键词: 增量更新, 内存消耗, 固件, 嵌入式设备, 无损压缩, 补丁文件

Abstract: In order to solve the high memory consumption of bsdiff algorithm when building new versions of firmware in the firmware update of embedded devices,this paper proposes an incremental update algorithm that saves memory.The improved patch file format of the bsdiff algorithm is used to avoid recording and calculating the address offset frequently in the application of the patch files.The parallel decompression process in the bsdiff algorithm is replaced by serial decompression,and the required auxiliary space is reduced by processing data in batches.At the same time,the asymmetric lossless compression algorithm is applied to the compression and decompression process of the improved incremental update algorithm,which reduces the memory consumption caused by the decompression of patch files.Experimental results show that,compared with bsdiff algorithm,xdelta algorithm,vcdif algorithm and zdelta algorithm,the proposed algorithm can effectively reduce the memory consumption when building new versions of firmware,and has good compression performance.

Key words: incremental update, memory consumption, firmware, embedded device, lossless compression, patch file

中图分类号:

TP311

王豫新, 高美凤. 一种改进的固件增量更新算法[J]. 计算机工程, 2020, 46(10): 210-215.

WANG Yuxin, GAO Meifeng. An Improved Incremental Update Algorithm for Firmware[J]. Computer Engineering, 2020, 46(10): 210-215.

https://www.ecice06.com/CN/Y2020/V46/I10/210

图/表 8

20201023093204

20201023093206

20201023093211

20201023093214

20201023093218

20201023093221

20201023093224

20201023093227

参考文献

[1] HUYNH-VAN D,TRAN-QUOC K,LE-TRUNG Q.An empirical study on approaches of internet of things reconfiguration[C]//Proceedings of the 7th International Conference on Communications and Electronics.Washington D.C.,USA:IEEE Press,2018:57-62.
[2] DU Zhenlong,SHA Guangxia,LI Xiaoli,et al.Customization and update research on capsule type firmware based on UEFI[J].Computer Engineering,2014,40(10):292-295,303.(in Chinese)杜振龙,沙光侠,李晓丽,等.基于UEFI的胶囊式固件定制更新研究[J].计算机工程,2014,40(10):292-295,303.
[3] KACHMAN O,BALAZ M.Effective over-the-air reprogramming for low-power devices in cyber-physical systems[M].New York,USA:Springer International Publishing,2016:284-292.
[4] KACHMAN O,BALAZ M,MALIK P.Universal framework for remote firmware updates of low-power devices[J].Computer Communications,2019,139:91-102.
[5] PERCIVAL C.Matching with mismatches and assorted applications[D].Oxford,UK:University of Oxford,2006.
[6] XIA Qi.Research on difference algorithm in mobile Internet data updating[D].Chengdu:University of Electronic Science and Technology of China,2014.(in Chinese)夏棋.移动互联网增量数据差分更新算法研究[D].成都:电子科技大学,2014.
[7] SHI Chao.The research and design of incremental OTA upgrade system based on Android platform[D].Zhenjiang:Jiangsu University,2017.(in Chinese)施超.基于Android平台OTA增量升级系统研究与设计[D].镇江:江苏大学,2017.
[8] NAKANISHI T,SHIH H H,HISAZUMI K,et al.A software update scheme by airwaves for automotive equipment[C]//Proceedings of 2013 International Conference on Informatics,Electronics and Vision.Washington D.C.,USA:IEEE Press,2013:1-6.
[9] TERAOKA H,NAKAHARA F,KUROSAWA K.Incremental update method for resource-constrained in-vehicle ECUs[C]//Proceedings of the 5th Global Conference on Consumer Electronics.Washington D.C.,USA:IEEE Press,2016:1-2.
[10] LI Jinfeng.Design and implementation of APP hosting platform based on play framework[D].Beijing:Beijing University of Posts and Telecommunications,2018.(in Chinese)李锦峰.基于play framework的APP托管平台的设计与实现[D].北京:北京邮电大学,2018.
[11] MOTTA G,GUSTAFSON J,CHEN S.Differential compression of executable code[C]//Proceedings of 2007 Data Compression Conference.Washington D.C.,USA:IEEE Press,2007:103-112.
[12] KOMANO Y,XIA Z F,KAWABATA T,et al.Efficient and secure firmware update/rollback method for vehicular devices[C]//Proceedings of Information Security Practice and Experience.Berlin,Germany:Springer,2018:455-467.
[13] FERREIRA A J,OLIVEIRA A L,FIGUEIREDO M A T.On the suitability of suffix arrays for lempel-ziv data compression[C]//Proceedings of International Conference on E-Business and Telecommunications.Berlin,Germany:Springer,2008:267-280.
[14] WEI Min,WANG Yi.Research and application of remote update technology of IoT terminal[J].Telecommunications Science,2018,34(10):137-142.(in Chinese)魏民,王艺.物联网云平台终端远程更新技术研究与应用[J].电信科学,2018,34(10):137-142.
[15] MAZUMDER B,HALLSTROM J O.An efficient code update solution for wireless sensor network reprogramming[C]//Proceedings of International Conference on Embedded Software.Washington D.C.,USA:IEEE Press,2013:1-10.
[16] STOJKOSKA B R,NIKOLOVSKI Z.Data compression for energy efficient IoT solutions[C]//Proceedings of the 25th Telecommunication Forum.Washington D.C.,USA:IEEE Press,2017:1-4.
[17] STOLIKJ M,CUIJPERS P J L,LUKKIEN J J.Efficient reprogramming of wireless sensor networks using incremental updates[C]//Proceedings of 2013 IEEE International Conference on Pervasive Computing and Communications Workshops.Washington D.C.,USA:IEEE Press,2013:584-589.
[18] CHENG Zhilong,NI Guiqiang,JIANG Jinsong,et al.Incremental update algorithm based on dynamic dictionary[J].Journal of PLA University of Science and Technology (Natural Science Edition),2015,16(5):426-432.(in Chinese)陈志龙,倪桂强,姜劲松,等.基于动态字典的增量更新算法[J].解放军理工大学学报(自然科学版),2015,16(5):426-432.
[19] MACDONALD J.File system support for delta compression[D].Berkeley,USA:University of California at Berkeley,2000.
[20] KORN D,MACDONALD J,MOGUL J,et al.The VCDIFF generic differencing and compression data format[EB/OL].[2019-09-20].https://www.rfc-editor.org/in-notes/pdfrfc/rfc3284.txt.pdf.
[21] TRENDAFIL O V D,MEMON N,SUEL T.Zdelta:an efficient delta compression tool[EB/OL].[2019-09-20].https://www.researchgate.net/profile/Nasir_Memon/publication/2556720_zdelta_An_Efficient_Delta_Compression_Tool/links/0046351f9ae28a19bd000000/zdelta-An-Efficient-Delta-Compression-Tool.pdf.

选择文件类型/文献管理软件名称

选择包含的内容