论文部分内容阅读
近年来,传感器技术得到了长足而有效的提升,无线传感网络(Wireless Sensor Network, WSN)以其开放、动态的特征获得了极大的关注,并成为了互联网计算的一个重要组成。WSN系统行为复杂,经常面临信息丢失、结点动态变化等不确定因素,且网络中的结点一旦部署将很难更改、维护。因此,为了保证相关应用的正常工作,在系统设计阶段对WSN中的相关协议进行质量保障就成为了一项非常重要的研究问题。系统设计人员不仅需要保证协议功能上的正确性,还应该评估协议在目标工作环境下的性能,以保证其可以胜任相应的工作需求。与仿真和测试相比,形式化分析能够给出对系统相关性质的确定性验证结果。因此,无线传感网络协议的形式化分析是一个重要研究方向。目前,使用模型检验技术对协议进行正确性验证的相关工作已经展开。然而,现有工作中存在一定问题,如建模方法不统一,建模流程不规范,可验证系统规模与网络实际规模相差较大等。针对相应问题,本文提出了一种基于随机时间自动机和统计模型检验技术的WSN协议建模、分析和评估方法框架。其主要工作包括以下两点:·建模方面,采用分阶段、自底向上的建模方法。首先根据协议的工作流程建立其理想情况下的时间自动机。为描述现实中广泛存在的信息丢失和结点失效等不确定性行为,用随机带权迁移扩展相关时间自动机,得到协议的随机时间自动机模型。·分析和验证阶段,首先用模型检验技术在理想时间自动机上检验协议的功能性性质,以验证其逻辑正确性。然后采用基于统计的模型检验技术在随机时间自动机上对其进行数值分析,以进行性能评估和分析、协议选择与比较等。为展示以上建模与验证方法框架的细节及其有效性,文中对两种著名的WSN时间同步协议TPSN(Timing-sync Protocol for Sensor Networks)和FTSP(Flooding Time Syn-chronization Protocol)分别构建了其时间自动机及随机时间自动机模型。在两种模型的基础上,则使用模型检验技术和基于统计的模型检验技术分别对协议进行了正确性验证和数值分析。使用我们的分析和验证方法可以发现,FTSP协议中存在设计缺陷,在特定情况下协议无法完成网络全局范围的时间同步。而TPSN虽然设计逻辑正确,但是对环境极其敏感,在恶劣环境中无法正常工作。相应发现也有力地说明了本文所提方法的有效性。另一方面,一线协议设计工程师直接对WSN协议进行建模与验证存在一定的难度,需要经过长时间的学习与培训。这也是现阶段相关方法尚未能在相关应用中普及的原因所在。针对相应问题,本文从设计人员所熟悉的程序代码及流程图出发,设计了一种程序员友好的WSN协议描述语言WPDL,使得设计人员可以方便的对相关协议进行描述。在此基础上,我们定义了相应规则并开发了辅助建模工具AMT以支持对协议描述文件进行自动化处理并生成时间自动机模型,从而可直接利用现有时间自动机验证工具进行验证分析。该建模过程与原来的过程相比,复杂度大大降低,减化了建模人员的工作。