基于地理位置的路由协议.doc

基于地理位置的路由协议：GEAR与GPSR协议对比 2011-06-16 14:19现有的路由协议分为：能量感知路由协议、以数据为中心的路由协议、基于地理位置的路由协议、可靠的路由协议和层次路由协议五类。地理位置路由假设节点知道自身及目标区域的位置，以这些位置信息作为路由选择的依据，按照一定策略转发数据到目标区域。位置和能量感知的地理路由（geographical and energy aware routing，GEAR）：能量感知的基于位置的地理路由协议，与传统非能量感知的地理路由相比，GEAR路由能极大地延长网络寿命。由于Sink发出的查询消息中经常包含位置属性，GEAR路由协议在向目标区域散布查询消息的同时考虑了地理位置信息的使用。其主要思想是通过利用位置信息使得“兴趣”的传播仅到达目标区域，而不是传播到整个网络，从而避免洪泛方式，减少路由建立的开销。GEAR路由中查询消息的传播包括2个阶段：（1）查询消息转发到目标区域：从Sink节点开始的路径建立过程采用贪婪算法，节点在邻居中选择到目标区域代价最小的节点作为下一跳节点，并将自己的路由代价设为该下一跳节点的路由代价加上到该节点一跳通信的代价。若陷入路由洞，节点则选取邻居中代价最小的节点作为下一跳节点，并修改自己的路由代价；（2）在目标区域内散布查询消息：查询消息到达目标区域后，通过迭代地理（节点密度较大时）或洪泛方式（节点较少时）将查询消息传播到目标区域内的所有节点。这2个阶段完成后，监测数据沿查询消息的反向路径向Sink节点传送。GPSR(贪婪周边无状态路由协议)贪婪周边无状态路由( Greedy Perimeter Stateless Routing,GPSR)是一种基于传统贪婪转发方案的路由协议。为了避免传统贪婪转发方案中通信空洞造成的路由寻径失败，以及由此产生的重复路由请求带来的额外开销，GPSR利用传感节点对位置信息的可知性和节点处于静态的特点，在路由过程遭遇通信空洞而失效时根据网络原始拓扑，生成一个平面子图并沿子图中空洞的周界进行分组转发。同时GPSR算法还利用该机制来支持传感节点的移动性。GPSR协议建立在传统贪婪转发算法之上，具有贪婪转发和周界转发两种分组转发方式。路由开始时采用贪婪转发方式进行分组转发，当贪婪方式失效时（即遇到通信空洞时）转入周界转发模式继续路由，当条件满足时恢复贪婪转发模式，如此反复直至分组到达目的地。GEAR（geographical and energy aware routing，位置和能量感知的地理路由）协议是一个基于贪婪转发与节点能耗均衡性相结合方案的路由协议，在选择邻节点进行下一跳转发的同时，把各直接邻节点的能量信息结合起来考虑，选择综合开销最小的邻节点进行分组转发。基于贪婪转发与节点能耗均衡性相结合方案的路由算法中，综合开销最小邻节点的选择至关重要。GEAR根据邻节点通往目的地的learnedcost（已知代价）来确定下一跳节点，使得分组能够朝向目的地转发，同时还可以平衡邻节点的能量消耗。基于地里位置路由协议研究方向及需要解决问题2011-06-16 14:17利用地理位置信息的路由协议在可扩展性、对动态拓扑的适应能力和节省能量方面均优于以往的基于链路连接性的协议，应用前景广阔。然而，对于利用地理位置信息的路由协议，仍需要进一步关注和研究。1)定位精度对协议性能的影响目前常用的两种获取位置信息的方式是GPS和利用信号强度估计相对坐标。节点可通过GPS接收机获得自己当前的地理位置信息，但是具有一定的误差，一般在15m左右。网络中的节点一跳通信范围一般是几十到一两百米，这样大的位置误差会严重影响路由算法的正确性。同样，在无线环境中，信号受衰减、 噪声干扰等影响，利用信号强度估计节点相对坐标在实际应用中受到很大限制。因此 ,需要分析位置误差对协议性能的影响，并改进协议使其能更好地适应误差环境。2)信标交换的频率对邻节点状态信息的维护和引入的控制开销的影响目前一般采用信标周期性地发送来维护邻节点的状态信息。这种方法对于拓扑结构稳定的网络来说是行之有效的方法，但是该方法不能对动态变化快的网络作出及时准确的反应。为了能在具有移动节点的主动式传感器网络中应用基于地理位置信息的路由协议，信标交换的频率应该与节点的移动速率、与周围邻节点的距离和状态信息的动态变化有关。如何在尽量减少控制开销的情况下准确反映邻节点的状态信息还有待于更深入的研究。3)在贪婪式路由算法中如何制定最佳的下一跳节点选择策略目前提出的下一跳节点选择策略存在不足。考虑了减少跳数来降低时延，但没有考虑节省能量；或相反，考虑能量的节省却大大牺牲了数据传输的时延；同时在能量消耗上也没有考虑进行均衡，在 QoS上没有给予支持。如何考虑各因素，权衡各因素的影响，针对具体应用制定下一跳节点选择策略是值得进一步研究的内容。4)地理位置信息与QoS相结合随着多媒体应用的普及，QoS路由已成为无线传感器网络研究领域的一个重要课题。由于无线传感器网络自身的特点，实现QoS路由是非常困难的。基于地理位置信息的路由中下一跳节点选择时应考虑下一跳节点的传输时延、传输带宽等与 QoS相关的状态参量，改善现有QoS路由性能。目前，已提出一些位置辅助的QoS路由协议，然而在国内外众多研究中，尚未涉及如何在基于地理位置信息的路由协议中保证QoS。如何在节省能量的情况下，保证数据包又快又好地传送至目标节点，有待于深入研究。贪婪无周边路由(GPSR路由协议)存在的不足及改进贪婪型转发和沿周边转发路由(Greedy Perimeter Stateless Routing,GPSR)定义：当需要转发数据分组时，节点利用贪心算法思想，在他的邻节点中选择距离目标最近的节点作为下一跳节点，进行数据传输与数据转发。当贪婪方式失效（节点找不到距离目标节点更近的邻接点，遭遇通信空洞）时，转入周界转发模式继续路由；当条件满足时恢复贪婪转发模式，如此反复直至分组到达目的地不足：(1) 实际应用中，可能会由于节点分布不均匀，部分节点工作量过多，导致通信量不均衡，使得部分节点因能耗过多而失效；(2) 在周边模式中，洞边界节点的通信概率较高，容易耗能过度而失效，使得洞呈现一种不断扩大的趋势；(3) 重复性路由建立过程中，路径最优化问题；(4) 在实际应用中，GPSR简单移动节点的数据转发支持不足；(5) 在下一跳节点的选择中，选择依据是距离目标节点最近的邻节点，如果这个邻节点在通信临界区域，如何确保两个节点之间的通信质量，以及在此情况下，如果节点有轻微位置移动，容易导致信息数据的丢包；(6) 当数据包传到目的节点前，再一次传到已经过的节点时，可能会导致死循环，这种情况下，死循环的跳出或者终止的算法；以上个人总结的六点不足之中，个人认为最为重要的，也是最有希望解决的，那就是第五点：距离过于遥远而导致的丢包现象。无线传感器网络中地理位置路由之GEAR在上篇文章我们提到的无线传感器网络中基于查询的路由协议，基站或汇聚节点需将查询消息发送到事件区域内的所有节点，即通过泛洪方式将查询命令消息传播到整个网络，建立基站或汇聚节点到事件区域的传播路径，这种路由建立过程开销较大。而Y.Yu等人提出的GEAR(Geographicaland Energy Aware Routing)路由协议就是根据事件区域的地理位置信息，建立基站或者汇聚节点到事件区域的优化路径，避免了泛洪查询消息，从而减少了路由建立的开销。GEAR协议假设了已知事件区域的位置信息，且节点都知道自己的位置信息和剩余能量。此外，节点可通过一个简单Hello消息交换机制就能知道所有节点的位置信息和剩余能量信息。GEAR协议和大多数Ad hoc网络路由协议一样，还假定了节点间无线链路是对称的。GEAR协议中的查询消息包含了位置信息，且节点只需将其发送到网络指定的区域。转发查询消息到目的位置是通过某种概率选择邻居来实现的，且查询消息仅在目标区域内泛洪传播。每个传感器节点都需维持一个邻居表，表中包含了节点的剩余能量和每个邻居的位置信息，另外也包含了转发到每个邻居的代价。GEAR路由协议是通过能量感知和地理信息支持的邻居选择启发式方法来选择最小代价的节点来转发分组到邻居，从而达到目的地节点。其核心思想就是通过仅考虑某个区域而不是发送兴趣消息到整个网络的方式来限制定向扩散协议中的兴趣消息数，这样GEAR协议比定向扩散协议可节省更多的能量。 GEAR路由协议中查询消息传播分为两个阶段。首先基站或汇聚节点发出查询消息指令，根据事件区域地理位置消息将查询指令传输到区域内距基站或汇聚节点最近的节点，然后从该节点将查询指令传播到区域内其他所有节点。采集的数据沿着查询指令的反向路径向基站或汇聚节点传播，1) 将查询指令消息传送到事件目标区域GEAR路由协议采用两种代价表示路径代价：获得代价(Learned Cost)和估计的代价(Estimated Cost)。估计代价是综合了节点剩余能量和到事件区域目的节点的归一化距离。节点到事件区域的距离用节点到事件几何中心的距离表示。由于所有节点都知道自己位置和事件区域位置，故所有节点都能计算自己到事件几何中心的距离。获得代价是对估计代价的一种提炼，考虑了网络绕洞的路由问题。所谓出现一个洞是指一个节点不存在任何比自身离目标区域更近的邻居节点的现象，或者说如果节点的所有邻居节点到事件区域的路由代价都比自己的大时，则陷入路由空洞(Routing Void)。克服这种现象可以使节点在邻居节点中选择到事件区域代价最小的节点作为下一跳节点，并将自己的路由代价设为该节点的一跳通信代价加上该下一跳节点的路由代价。当不存在洞现象时，估计代价刚好等于获得代价。每当分组到达目的节点获得代价就会向前回传一跳以至于下一个分组的路由建立需要调整。当还没有建立从基站或汇聚节点到事件区域的路径时，中间节点使用估计代价来决定下一跳节点。GEAR路由协议在路由建立过程中采用了局部最优的贪婪算法，适合无线传感器网络中节点只知道局部拓扑信息的情况，缺陷是可能缺乏足够的拓扑信息导致路由空洞现象出现，降低了路由效率。如果节点采用相邻两跳节点地理位置信息，就可大大降低路由空洞产生的概率。此外，GEAR路由协议假设节点地理位置固定或变化不频繁，适用于移动性较小的传感器网络应用环境。在GEAR路由之前，B.Karp和H.T.Kung还提出一个与其类似的非能量感知的地理路由GPSR(Greedy Perimeter Stateless Routi