面向无线传感网络的增量重编程技术研究

摘要

对大规模无线传感网络的研究是一项具有挑战性的课题。其中对已经部署运行的大规模传感网络进行软件更新就是其中一项巨大的挑战。现实的传感网络应用通常需要部署成百上千个节点。在网络的运行过程中，基于修复漏洞、改变网络功能、调优系统参数等原因，经常需要对传感器节点运行的程序进行版本的更新。
　　 当前的软件更新技术有诸多局限。串行编程方法其低下的效率使之无法应用到大规模的网络中去。因此研究者们提出了无线重编程技术来使得节点可以通过无线通信来自动进行代码更新。
　　 由于大部分的代码更新操作，新代码相对于原代码的更改部分远小于整份新代码的大小，如果只需要传输更改部分的增量文件，可以大幅度地减小传输数据，提高更新效率并降低能耗。本文提出增量重编程方法中影响增量文件的大小的两个主要因素:代码相似度以及差分算法。并通过设计与实现新的方法来提高无线传感网络无线重编程效率。
　　 (1)代码相似度问题。保护新版本代码和老版本代码相似度有利于差分算法进一步降低增量文件的大小。本文提出了一个高效的代码相似度保护算法R3sim，在花费少量的额外元数据代价的情况下达到最大限度保护新旧版本代码间相似度的效果。
　　 (2)差分算法。已有的差分算法不能保证生成最优的增量文件，而且一些方法在时空复杂度上代价太大，无法用于更复杂的代码的更新。本文提出了一个高效的差分算法DASA，并且在数学上证明本文设计的算法能够生成最优的增量文件，而且保持了足够高的算法效率。该项工作发表在国际会议IEEE ICC2012并且被SCI期刊Ad-Hoc& Sensor Wireless Networks录用。