面向无线网络的形式化方法研究

【摘要】无线网络己经被广泛运用于人们日常生活中的许多方面。尤其是在缺少固定基础设施的情况下,无线网络和无线技术是合适的通信解决方案,并且正在被广泛应用于实现信息传输的各种通讯场景中。构成无线网络的基础物理器件是无线网络节点设备,这些无线节点设备为无线网络应用的实现提供了基础的通信功能。无线网络节点设备通常是以无线电波为载体进行广播式的信息发送,这种无线网络的广播信息发送模式与传统的有线以太网络中的全局广播信息发送模式有所不同。在无线网络中,信息数据的广播发送是局部的,也就是说每个无线节点所发送的信息的传输范围是有限的,只有那些处于节点传输半径覆盖范围内的部分接收节点才能够接收到所对应的节点广播发送的信息。受限于有限的信息传输范围,为了使得不在传输范围内的两个无线节点之间能够实现交互,就需要借助其他的中间节点来建立起一条能够传输信息的路由路径。路由协议是实现无线网络中路由路径的建立和维护的一种重要机制,主要是通过各种报文信息在无线网络中的广播来建立路由路径。形式化方法被认为是对无线网络系统进行描述和验证的一种可行并且合适的方式。本文研究面向无线网络系统的形式化方法。我们主要研究无线网络中与通信交互相关的无线网络特性,包括无线节点之间的广播通信交互行为以及无线网络中路由协议建立路由路径的机制。无线网络中无线节点之间的通信实现了无线网路中最根本的信息交互功能。我们考虑无线广播通信的各种物理特征,包括了无线节点的位置、通信范围、通信频率等物理因素。针对通信交互等无线节点底层物理行为的形式化描述和建模通常采用基于通信交互的进程代数演算系统。因此,我们扩展无线系统演算引入无线网络卫兵选择的概念,基于程序统一理提出了无线演算系统的代数语义和指称语义。我们给出了一系列无线系统演算的代数规则,研究从代数语义计算推导出操作语义的方法。无线网络中的路由协议借助无线节点之间的通信交互实现了无线网络中的全局信息交互。针对无线网络中路由协议在路由建立和维护路由路径时的特点,我们主要考虑路由协议实现路由时的各种路由信息数据的处理机制。因此我们采用形式化描述语言对无线网络AODV路由协议进行形式化建模、分析和验证工作并且将底层的无线节点的通信交互行为抽象为针对变量的赋值效果。通过使用这种在更高层次的抽象描述方式,我们能够更直接地分析无线网络路由协议的本质特性。本文的主要贡献包括：·我们提出了无线系统演算的代数语义,给出了一组用于描述无线系统演算并行组合线性展开的代数规则,并且定义了无线网络系统的规范型。借助无线网络系统的规范型,我们给出了从代数语义计算生成操作语义的方法,并且证明了代数语义和操作语义的一致性,从代数语义的角度保证了操作语义的正确性和完备性。我们使用重写逻辑工具Maude实现了从代数语义自动计算操作语义的过程。我们提出了无线系统演算的指称语义,引入了无线网络执行状态和执行轨迹的概念用来描述无线网络的行为。基于指称语义模型,我们证明了无线网络系统的代数性质。·我们使用形式化建模语言Z对无线网络中使用的AODV路由协议进行建模,并且使用基于Rely/Guarantee方法的形式化验证技术证明了协议的性质。通过形式化建模语言,我们在建模过程中消除了路由协议相关文档中自然语言描述的二义性。我们使用程序变量赋值的效果来描述无线节点之间的通信交互。我们对使用形式化语言Z构建的协议模型进行重写得到基于共享变量并行程序语言的改进协议模型。以共享变量并行程序所描述的路由协议形式化模型为基础,我们使用Rely/Guarantee推理规则证明了路由协议建立的路由路径不存在路由环路等性质。
【作者】吴晓峰；
【导师】朱惠彪；
【作者基本信息】华东师范大学，计算机应用技术，2014，博士
【关键词】无线系统演算；代数规则；指称语义；语义联接理论；Rely/Guarantee方法；

【参考文献】
[1]汪芳.模式识别技术及其在文字识别领域的应用研究[D].西北工业大学,计算机软件与理论,2004,硕士.
[2]王林.转双价基因抗虫杂交棉荃银2号的选育及产业化分析[D].安徽农业大学,种植,2011,硕士.
[3]高翠华.燃料气体中有机杂质的萃取方法研究及GC-MS分析[D].辽宁石油化工大学,2012.
[4]郑秉咸.中国近代小说中的鸦片书写研究[D].上海师范大学,中国古代文学,2013,硕士.
[5]李颖.真菌漆酶高效定向固定化新策略探索[D].山东大学,分析化学,2014,博士.
[6]杨宇辰.二十世纪前期买办经济状况研究[D].吉林大学,中国近现代史,2004,硕士.
[7]贾成锁.全民健身“疾控”效益评估研究[D].南京体育学院,社会体育指导,2012,硕士.
[8]兰会晗.文化创意产业视角下的河南工业遗产旅游开发研究[D].河南科技大学,旅游管理,2013,硕士.
[9]鲍莎.河北省农村养老保险制度可持续发展的财政支持政策研究[D].河北大学,社会保障,2014,硕士.
[10]吴金钟,赵玉芹,苏震.TSC就地动态无功功率补偿装置在安钢的试验研究与应用[J].冶金自动化,2002,02:26.
[11]童峰明.改进型的语义Web服务发现框架研究[D].温州大学,计算机应用技术,2012,硕士.
[12]许瑶瑶.美俄法的国家信息安全保护及其启示[J].新视野,2014,03:125-128.
[13]王慎杰,吕艳萍,刘飞,曾国,李俊,邵金良.110kV电阻接地系统电气设备适应性研究及试验[J].电力系统自动化,2015,11:193-198+207.
[14]张立帅.Z源逆变器小信号模型的参数优化与并网控制研究[D].重庆大学,电气工程,2014,硕士.
[15]刘庆.北京市城乡结合部农村居民点用地趋势及对策研究[D].中国农业大学,土地资源管理,2004,硕士.
[16]杨先.普通话特殊型语言障碍儿童对全称量词“都”的习得研究[D].广东外语外贸大学,外国语言学及应用语言学,2013,硕士.
[17]张妍.对我国反兴奋剂工作中运动员权利保护问题的研究[D].北京体育大学,体育人文社会学,2013,硕士.
[18]欧阳强.税收优惠之国际协调[D].湖南师范大学,国际法学,2004,硕士.
[19]姚志东,李炜,高先龙.点缺陷扶手型石墨烯量子点的电子性质研究[J].物理学报,2012,11:449-454.
[20]刘晓旭.民事撤回起诉制度研究[D].山东大学,法律（专业学位）,2013,硕士.
[21]李辰慧.晚期大肠癌中西医维持治疗研究[D].北京中医药大学,中西医结合临床,2013,硕士.
[22]常红霞.山东沿海地区城镇化影响因素及对策研究[D].哈尔滨工业大学,技术经济及管理,2014,硕士.
[23]王文涛.基于离散元法的铁粉模压成形数值仿真研究[D].中北大学,机械制造及其自动化,2014,硕士.
[24]王喜刚,李庭武.平衡在计划中的重要性[J].一重技术.2008(03)
[25]毛慧慧.别墅景观工程材料研究[D].浙江大学,风景园林（专业学位）,2011,硕士.
[26]池明茹.安康水电站生态径流调控研究[D].南京信息工程大学,自然地理学,2012,硕士.
[27]潘寿华.甘氨酸对肾缺血再灌注损伤的保护作用及iNOS表达影响的研究[D].浙江大学,外科学,2004,硕士.
[28]刘凯.中国黄金现货市场收益率日历效应的实证分析[D].华侨大学,金融学,2014,硕士.
[29]李擎.基于MVC模式的油田项目管理系统的设计与实现[D].电子科技大学,软件工程（专业学位）,2013,硕士.
[30]卢志鹏.城市快速路入口匝道及辅路信号协调控制算法研究[D].北方工业大学,控制工程,2013,硕士.
[31]夏文.喷气推进装置驱动与控制关键技术研究[D].沈阳理工大学,检测技术与自动化装置,2012,硕士.
[32]高冬梅.钌基氨合成催化剂的制备及其催化性能研究[D].浙江工业大学,工业催化,2004,硕士.
[33]张亚.跨国公司涉外商业贿赂法律问题研究[D].华中师范大学,经济法学,2014,硕士.
[34]杜开元.伦坡拉盆地丁青湖组烃源岩评价及资源潜力分析[D].中国地质大学（北京）,构造地质学,2014,硕士.
[35]田迎迎.三角范畴中presilting子范畴的mutations及其torsion pairs[D].湖南师范大学,基础数学,2014,硕士.
[36]毛利慧.KK公司融资优化策略研究[D].兰州大学,工商管理（专业学位）,2013,硕士.
[37]林静.机械压力机故障诊断系统的研制[D].广东工业大学,材料加工工程,2013,硕士.
[38]夏若男.电力市场营销效果评价的定量模型及实证研究[D].华北电力大学（北京）,2005.
[39]白天明.球面磨具保形磨损高速研磨[D].长春理工大学,机械制造及其自动化,2004,硕士.
[40]李新.中国企业对外直接投资的障碍及对策研究[D].吉林大学,世界经济,2014,硕士.
[41]王海鹏.EBG结构在高速PCB电源分布网络中的应用研究[D].西安电子科技大学,电路与系统,2012,硕士.
[42]陈薇.论广东“走出去”战略的理论依据和路径选择[D].中共广东省委党校,马克思主义中国化研究,2013,硕士.
[43]高友泉.信息技术在内河海事管理中的应用研究[D].武汉理工大学,2002.
[44]李明昳.我国地方税体系存在的问题和对策研究[D].燕山大学,行政管理,2013,硕士.
[45]王宏建.衬衫袖衩自动缝制机构的分析与设计[D].武汉纺织大学,机械设计及理论,2014,硕士.
[46]玉富达.准固态超级电容器用氧化还原介质掺杂凝胶聚合物电解质制备及电化学性能研究[D].华侨大学,材料学,2013,硕士.
[47]陈百胜.肠内免疫营养在胃癌围手术期的应用意义[D].福建医科大学,外科学,2014,硕士.
[48]罗远根.91例三切口食管癌切除术喉返神经旁淋巴结转移相关因素的临床分析[D].福建医科大学,外科学,2014,硕士.
[49]刘硕.文化传媒上市公司财务竞争力分析[D].山东财经大学,会计（专业学位）,2014,硕士.
[50]仝永娟.电熔镁系统节能新工艺研究[D].东北大学,热能工程,2010,硕士.