基于地理位置的贪婪周边无状态路由算法理论及应用研究

摘要

本论文是针对国家自然科学基金项目“基于空气、冰与水物理特性差异的冰层生消过程与力学强度连续在线检测原理研究”(51279122)研究过程中的一项技术难题而开展的研究。为了实现对黄河春季开河时对河道局部区域内浮动冰凌整体及内部物理状态变化的实时监测与预报，我们采用专用的冰情检测传感器与无线数据传输技术结合构成的无线传感器网络来解决这一难题。由于构成无线传感器网络的各节点具有地理位置浮动的特点，如何解决节点间的相互协调，利用节点有限的局部信息来实现节点间数据正确、及时的交付，实现无线传输链路的负载均衡，最大化无线冰凌测报传感器网络的生命期成为实现对黄河中上游河道冰凌灾害预警系统建设（在对海洋或近海浮冰、大型水利水电枢纽工程水库内浮冰的监测与此类似）的一项关键技术。本论文通过对这一问题的专向理论研究，希望为解决这一工程应用难题提供一种新的解决途径。
　　 用于冰凌测报的无线传感器网络与传统的通信网络相比，在路由节点的部署方式、能量消耗、容错性、扩展性等诸多领域有着很大的不同。其中，如何利用有限的局部信息选择下一跳路由转发节点的路由问题成为了无线传感器网络技术中极具挑战性的研究热点和难点。在解决这一问题的诸多现有路由协议中，由哈佛大学研究人员Brad Karp和H.T.Kung于2000年提出的基于地理位置的贪婪周边无状态路由协议GPSR(Greedy PerimeterStateless Routing)是一种特别适用于无线数据报网络的路由协议。其原因是:(1)由于GPSR协议所采用的贪婪转发模式是运行于网络平面化之前的无线网络拓扑之上，GPSR协议可以充分利用无线网络的通信链路，实现数据包转发的高效性;(2)当GPSR协议在转发数据包的过程中，无法从当前路由节点的邻节点中找到比自己更接近目的节点的下一跳转发节点时，即在数据包贪婪转发过程中出现空洞(void)现象时，GPSR协议的贪婪转发模式失效。GPSR协议能够自动转入平面周边遍历模式，采用加百利图GG（Gabriel Graph）或相对邻域图RNG（Relative Neighborhood Graph）算法来构造平面图，结合右手规则，对数据包进行转发。所以，GPSR协议的平面周边遍历模式能够在其贪婪转发模式失效时避免整个协议的失败，提高了无线传感器网络中信息传输的可靠性。正是GPSR协议的这两大特性使其成为基于地理位置的无线路由协议中的典范。
　　 然而，GPSR协议的平面路由模式在实际应用中，由于错误的地理位置信息会导致与单元图假设发生冲突，导致网络拓扑平面化过程不准确，从而会产生三种错误的结果:(1)当平面图某一连接链路中断时会导致平面子图中的连接链路被删除;(2)位于某一连接链路两端的节点就其连接是否属于平面图存在争议（如:单向链路不属于平面图）;(3)在平面子图中出现了两条交叉的链路。这些错误必然会导致路由失败，在源和目的节点之间无法找到路径，使得周边转发模式重新变为GPSR协议的技术瓶颈。
　　 本文结合冰凌测报无线传感器网络中传感器节点能量受限、节点随着冰凌的产生与流动会出现在河道断面局部观测区域的冰凌测报无线传感器网络拓扑结构不断变化这一特性，提出了对GPSR路由协议的改进策略GPSRI(GPSR-Improved)，并借助网络模拟器NS2(Network Simulator2)，对GPSR算法以及改进的路由策略GPSRI进行了模拟仿真实验，对路由算法中涉及到的关键参数的相关实验数据进行了处理分析。模拟仿真实验及评估结果表明，GPSRI在数据包转发的路由跳数、源和目的节点间端到端的传输时延方面与GPSR相比有较大的性能改进。在改进策略GPSRI中，不但解决了GPSR协议平面路由模式产生的瓶颈问题，而且从无线传感器网络路由协议可靠性的角度出发，实现了节点不相关的多路径。本文围绕以下三个方面对改进的路由策略GPSRI进行了具体的研究与探索:
　　 (1)在GPSR协议中，右手法则保证了数据包在平面周边遍历模式中能够走出空洞。但是，如果在路由过程中频繁遭遇空洞现象时，GPSR协议做出的路由选择具有一定的随意性，而正是这种随意性又会导致发现路由的跳数较多，不能保证GPSR协议以较小的代价走出空洞。本文详细分析了GPSR协议由贪婪转发模式转入平面周边遍历模式解决空洞问题的过程，并在改进的路由策略GPSRI中提出了解决空洞问题的回退策略。据此策略，GPSRI可以在从源到目的节点的数据包转发过程中，成功地找到数据包的转发路径。实验证明回退策略能够更加有效地解决平面路由模式中的空洞问题。
　　 (2) GPSR协议有可能在错误的路径上走得很远。因为GPSR协议中创建RNG和GG平面图的两种平面化算法都依赖于节点的当前邻节点集的最新位置信息。如果邻节点没有移入或移出路由节点的信号辐射范围，仅仅是在当前路由节点的信号辐射范围之内移动，那么，当前的拓扑平面化信息将不是最新的。当单元图的平面化信息变得陈旧时，对于准确的周边模式数据包的转发将失去作用，必然导致GPSR协议可能一直在错误的路径上转发数据包。本论文提出的GPSRI改进策略在运用回退策略有效地解决GPSR平面路由模式中出现的空洞现象的基础上，提出了基于节点混杂模式的环路径优化算法，实现了尽量使用最短或较短路径来完成数据包的传输，从而保证在改进的路由策略GPSRI中可以获得最小的或较小的端到端的传输时延。
　　 (3) GPSR协议使用边界转发的前提是:事先构造一个平面图来描述网络拓扑，要求该平面图中任意两条边都不相交，GPSR协议构造平面图的方法是利用GG或RNG平面图算法来删除网络拓扑图中交叉的边。但是，在GG和RNG平面图算法的运行过程中，如果传感器节点间存在某种特殊模式的障碍时可能会破坏图的连通性，从一个平面无法到达另一个周边转发平面，从而导致目的节点不可达，影响到了GPSR协议实现数据交付的可靠性。在本文提出的改进策略GPSRI中实现了多条节点不相关路径，进一步提高了无线冰凌测报传感器网络中数据交付的可靠性。
　　 针对在海洋浮冰或黄河中上游河道的冰凌测报传感器网络系统构建过程中传感器节点能量受限、节点随着冰凌的产生与流动会出现在河道断面局部观测区域的无线冰凌测报网络拓扑结构不断变化这一特性，采用本文提出的对贪婪周边无状态路由协议GPSR的改进策略GPSRI来实现用于冰凌测报传感器节点间的相互协调方案、在没有用户介入的情况下，节点能够自动组织起一个低功耗、灵活性强、扩展性好、低成本的数据采集网络，该数据采集网络系统不会因为某个节点的故障或缺失而影响整个冰凌测报传感器网络系统的功能实现。改进算法GPSRI具有的这一特点，使其有可能应用于海洋浮冰、内陆河道局部区域冰情与冰凌参数的远程无人网络化监测等应用领域中。

目录

声明

论文说明

摘要

图索引

表索引

第一章 绪论

1．1 课题产生的背景和意义

1．2 无线传感器网络的研究现状

1．2．1 无线传感器网络的特点

1．2．2 无线传感器网络的关键技术

1．3 无线传感器网络路由协议

1．3．1 影响路由协议性能的因素

1．3．2 无线传感器网络路由协议的分类

1．3．3 网络流和QOS敏感路由协议

1．4 本章小结

1．5 论文的内容安排

第二章 贪婪周边无状态路由协议GPSR

2．1 概述

2．2 贪婪转发

2．2．1 贪婪转发的概念

2．2．2 邻节点位置信息的获取

2．3 右手规则

2．4 构造平面图

2．4．1 RNG和GG平面图算法

2．4．2 贪婪转发和平面周边转发模式的结台

2．4．3 GPSR协议的具体实现

2．4．4 GPSR协议模拟结果和评估

2．5 GPSR协议存在的缺陷

2．6 本章小结

第三章 GPSR协议缺陷改进现状研究

3．1 GPSR协议缺陷改进现状概述

3．2 交叉链路检测协议CLDP

3．2．1 概念

3．2．2 地理路由

3．2．3 CLDP协议具体描述

3．2．4 CLDP协议改进结果总结

3．3 基于左右手规则的区域周边路由

3．3．1 概述

3．3．2 协议描述

3．3．3 协议特点

3．4 基于两跳节点信息的空洞转发策略

3．4．1 策略概述

3．4．2 两跳节点策略描述

3．4．3 协议特点

3．5 节点不相关多路径路由算法DPMR

3．5．1 DPMR概述

3．5．2 DPMR算法描述

3．5．3 DPMR协议特点

3．6 本章小结

第四章 基于回退策略的地理路由协议GPSRI

4．1 GPSRI概述

4．2 GPSRI核心思想

4．3 无线冰凌测报传感器网络模型及GPSRI协议问题描述

4．3．1 GPSRI中使用的理论定义

4．3．2 GPSRI协议算法基础及分析

4．3．3 地理路由算法比较

4．4 GPSRI协议过程分析

4．4．1 网络收敛

4．4．2 贪婪转发

4．4．3 路径优化

4．4．4 多路径实现

4．5 本章小结

第五章 GPSRI性能及其在冰凌测报环境中的模拟应用分析

5．1 概述

5．2 实验环境

5．2．1 NS2模拟软件

5．2．2 GPSRI在冰凌测报无线传感器网络环境中的模拟应用分析

5．2．3 GPSRI算法实现细节说明

5．3 实验结果

5．3．1 GPSR与GPSRI时延比较

5．3．2 GPSR的平均路由跳数

5．3．3 GPSR的平均传输时延

5．3．4 GPSRI路径优化前后的平均路由跳数

5．3．5 GPSRI路径优化前后的平均传输时延

5．3．6 GPSRI多路径的实现

5．4 算法时间复杂度和空间复杂度的分析

5．5 本章小结

第六章 总结与展望

6．1 研究及解决的问题

6．2 下一步研究和展望

参考文献

致谢

攻读博士学位期间已发表和录用的学术论文

攻读学位期间主持和参与的科研项目