无线传感器网络GPSR协议及仿真

《无线传感器网络GPSR协议及仿真》由会员分享，可在线阅读，更多相关《无线传感器网络GPSR协议及仿真（75页珍藏版）》请在金锄头文库上搜索。

1、第4章 数据传输路由地理路由及OPNET网络层仿真地理路由概述n网络层的核心功能：数据的转发和路由 为源节点找到一条通向目标节点的传输路径， 接着数据分组从源节点以多跳的方式传送到目标节 点。n典型的路由协议： WSN：flooding，gossiping，SPIN，directed diffusion，rumor，LEACH 自组网：DSDV，AODV，DSR地理路由概述n上述各种非地理路由协议比较： 大多是通过路由探测包获得网络节点间的连接关系和链路 特性，从而确定路由并存储路由表。 基于DV的路由协议：收敛速度慢，出现路由环路。 基于LS的路由协议：会因路由中若干节点的失效、移动而经常中

2、断路由控制负担较大，带宽资源消耗过多。 层次化路由策略： 局部的先应式路由与全局的反应式路由的结合，以期达到提高数据 传输效率和网络可扩展性的目的。 需要维护端到端路由协议，对动态变化网络的适应能力有限。地理路由概述n基于位置信息的路由协议（地理路由）： 需要定位技术支持，节点通过定位技术获得自身、 邻居节点以及目标节点的地理位置信息。 节点利用这些地理位置信息，可以避免路由探测包 的盲目洪泛，从而进行有效的路由发现和路由维护 ，甚至可以基于无状态的分布式的非端到端的数据 转发。地理路由概述n贪婪路由算法： 在整个数据传输中不需要建立端到端的基于全局链 路状态的路由，不需要存储路由信息表，也不

3、需要 发送路由更新信息。 只要求节点准确地存储周围邻居节点的状态信息， 可节省能量的消耗，降低节点的内存、计算能力要 求；同时能够提供很好的数据传输保障，具有良好 的网络可扩展性和鲁棒性。地理路由概述n基于位置信息的路由算法：实现查询传送和广 域数据提取，与物理介质和路由选择无关。n需要解决的问题： 节点定位 贪婪转发 空洞绕行 目标域内转发位置服务n地理路由必须事先得到足够的位置信息才能够 正常工作，包括如下三种位置信息： 节点自身的地理位置信息； 节点的所有一跳邻居节点地理位置信息； 目标节点的地理位置信息。位置服务n节点位置获取方法： 通常可以借助GPS及各种定位算法获得节点自身的地理位

4、置 信息； 通过节点间的信息交换，可获得所有一跳邻居节点的地理 位置信息； 目标节点的地理位置信息的获取是地理路由协议难点： 当目标节点静止时，可以通过目标节点的一次性泛洪广播来通过所 有节点； 当目标节点运动时，需要通过位置服务获取目标节点的地理位置信 息。n典型的位置服务算法：GLS等地理路由分类n根据节点在发送数据前是否需要建立路由，地 理路由可分为： 位置辅助路由协议 基于位置信息的路由协议 定向区域泛洪 贪婪路由算法 分层路由协议n位置辅助路由协议：LARLARnLAR：Location Aided Routing，位置辅助路由 思路：利用移动节点的位置信息将寻找路由的区域限制在一

5、个较小的请求区域（request zone, RZ）内，从而限制路由请 求过程中被影响的节点数目，增强了路由发现的目标性，减 少了路由请求消息的数量，提高路由请求的效率。n前提条件： 节点通过GPS获得自己的当前位置(x,y)。 假定每个节点知道其它节点的平均移动速度。LAR算法n操作过程类似于DSR： 在路由发现过程中，LAR利用位置信息进行有限的广泛搜索，只有在请 求区域（RZ）内的节点才会转发路由请求分组。 若在规定时间内路由请求失败，源节点会扩大RZ，重新进行搜索。随着 RZ的扩大，路由发现的可能性相应增加。 当RZ扩大到全网范围就成了一般的泛洪算法。LAR算法n位置获取： 源节点在发

6、送的“路由请求”中携带自己的当前位置和时间， 目的节点也在“路由应答”中携带自己的当前位置和时间， 沿途转发请求或应答分组的节点可以得到的源节点或目的节点的位置信 息，也可以获得其它节点的位置信息。LAR算法n确定请求区域（RZ）是LAR算法的关键，两种方法： 一、由源节点和目的节点的预测区域确定的矩形区域； 二、距离目的节点更近的节点所在的区域。 RZ过小将降低路由发现成功的概率，出现无法建立路由的情 况；RZ过大会带来多余的控制开销。n两种控制路由查找的策略：区域策略和距离策略LAR算法n区域策略： 通过计算目的节点期望区（Expected Zone, EZ）和路由请求区域（RZ）来 限制

7、路由请求的传播范围，只有在RZ中的节点才参与路由查找。 操作过程： 假设t1时刻节点S要查找节点D的路由，S知道在t0时刻（ t0 DISTs+d ，I丢弃该分组。 若I为目的节点，则发“路由应答”给S。LAR协议评价n优点： 将路由查找限制在RZ中，在RZ之外的节点不受路由请求的干 扰，因此查找速度快，开销小，网络的扩展性能好。 只提出策略，不拘泥于某一种确定的协议，适用范围广。LAR协议评价n缺点： 需要GPS系统支持。 仍然是基于链路状态（LS）建立的端到端路由，对 于网络拓扑动态性变化快的网络不太适用。 例如目的节点的移动速度高于源节点记录的速度，目的节 点并不在EZ中，会造成初次查找

8、失败，此时需要源节点增 加查找范围，重新进行查找，这会增加延迟和网络开销。 若源节点没有目的节点的位置信息时，其查找范围 为整个网络，等同于洪泛法。n基于位置信息的路由协议 贪婪路由算法 定向区域泛洪 分层路由协议基于位置信息的路由协议n节点在发送数据前不需要寻找路由、不需要保存路由表。n节点直接根据自己、邻居节点和目标节点的位置信息来确定数 据转发策略。n两种典型的路由算法：贪婪路由、定向泛洪路由 源节点将数据分组传送给一个（贪婪路由）或多个（定向区域泛洪）距 离目标节点更近的邻居节点。n基于分层网络结构下的分层路由算法，在网络中按照不同的网 络层次采用不同的路由协议，在不同的层次进行路由时

9、可能需 要位置服务的支持。n基于位置信息的路由协议 贪婪路由算法 定向区域泛洪 分层路由协议贪婪路由算法n只需要本节点、所有邻居节点及目标节点的地理位置信息，仅 存储少量信息即可进行路由选择的算法。n路由的选择以到达目标节点的距离为依据，源节点将数据传给 距离目标节点更近的邻居节点，中间节点继续选择距离目标节 点更近的节点为下一跳节点，以此类推，直至数据传送到目标 节点。n对于中间节点I，通常会有多个邻居节点距离目标节点更近， 这些离目标节点更近的邻居节点集合称为N（I）。 基于不同的度量标准在N（I）中选择下一跳节点，所得到的贪婪算法具 有不同的性能。贪婪路由算法n常见的下一跳节点选择策略有

10、四种： 从N（I）中选择距离目标节点D最近的节点，从而使得到达目目标节点 的跳数最少，减少数据在节点中因排队、处理带来的时延。 如果信号能量足够大，节点一跳传输范围的半径将越大。但节点相互干扰 的可能性越大，同时也导致了较大的能量消耗。 若所选择的节点处于通信的边缘，它的移动极易造成路由的终端。 从N（I）中选择距离自己最近的邻居节点作为下一跳节点，从而降低节 点间相互干扰的可能性。 缺点：容易出现距离中间节点I非常近的节点被选中，虽然减少了能耗，但 大大增加了通信的跳数。贪婪路由算法n常见的下一跳节点选择策略有四种： 从N（I）中选择节点F，使得角FSD最小，从而缩小数据分组传送的范 围。

11、会出现路由环路。 Randomized compass路由算法，选择将中间节点与目标节点的连线分为 两侧区域，随机地从N（I）中选取一侧区域中角度最小的节点作为下一 跳节点。 无环路。贪婪路由算法评价n优点： 无需全局网络的链路状态信息，每个节点只需要知道周围邻居节点的位 置信息； 每一次转发都是局部决策，可以进行无状态的完全分布式非端到端的数 据转发； 不需要存储路由信息表，也不需要发送路由更新信息，只要求准确地存 储周围邻居节点的状态信息即可。 节省了能耗的消耗 降低了节点内存、处理要请求 提供很好的数据传输保证，具有良好的扩展性和鲁棒性。贪婪路由算法评价n缺点： 路由空洞 所选择的节点不

12、一定满足数据传输的QoS要求，同时能量的消耗也不平 衡。n改进方法： 概率转发、随机选取、竞争转发等方法选择下一跳节点，均衡传输业务 ，避免拥塞和能耗不均衡的现象。 通过状态最佳门限过滤，优先选择时延低、传输速率高、能量状态好的 节点作为下一跳节点，保证数据分组所经历的路径具有一定的可靠性和 实时性。n基于位置信息的路由协议 贪婪路由算法 定向区域泛洪 分层路由协议定向区域泛洪n节点向目标节点方向的所有邻居节点转发数据分组。n鲁棒性强，但网络负载重。n典型算法：DREAMDREAMnDREAM：Distance Routing Effect Algorithm for Mobility，移动距

13、离效应路由算法： 一种利用位置信息的主动路由协议，使用位置信息确定数据 分组的泛洪方向。因此，DREAM也是一种典型的定向区域 泛洪路由协议。 假设每个节点通过GPS获取自己的位置信息，并以坐标的形 式给出。DREAMn通过给控制信息设置不同的TTL来实现距离效应。n每一个节点周期性地广播一个控制信息，通过控制信 息进行位置更新，此分组包括节点的坐标信息和生存 时间。 大多数控制信息生存时间较短，以较高的频率发送，在传播 较短的距离后失效； 另外一些控制信息则拥有较长的生存时间，发送频率较低， 能够传送的距离较远。n当某个节点收到控制信息，通过计算该分组传播的距 离与生存时间比较的结果来判断是

14、否转发分组，如果 传播的距离大于生存时间则不再进行转发。（图4-11）DREAMn为了减少路由开销，DREAM引入了两个参数：距离影 响、移动速率。 两个节点相距越远，它们移动的相对速度越慢。 根据移动速率的定义，节点移动越快，它向外广播其新位置 的频率越高。 借助GPS系统，在寻找路由时每个节点都可以得知这两个参 数。DREAMn每一个节点都维护一个位置列表，表项内容包括每一 个节点的位置信息，对应节点的方向、距离及更新时 间。 相对方向：图4-11n当源节点要发送数据分组时，它在自己的位置列表中 进行定向的部分泛搜索，寻找目的节点方向的一个节 点子集来传送分组。如果没找到这样的子集，便进行

15、 泛搜索。n目的节点接收到数据分组后，以同样的方式向源节点 会送一个ACK分组（经泛搜索方式到达的分组不回送 ACK）。DREAM协议评价n优点： 无环路。 鲁棒性强，增加了移动环境下传送分组的成功率。 每次数据分组转发都是发送给目标节点发现的多个节点， 类似于提供了到目标节点的多条路径，某条链路分组的丢 弃不会影响到其它链路上的分组。 控制分组中只有位置更新分组和ACK分组，携带信 息少。并且位置更新分组发布的周期依据节点的移 动速度确定，控制分组的数目和传播范围均得到了 进一步优化。DREAM协议评价n缺点： 扩展性差，不适用于大规模的网络。 节点的位置信息是通过全网范围内广播得到的，当网

16、络规 模扩大时，控制开销会显著增加。n基于位置信息的路由协议 贪婪路由算法 定向区域泛洪 分层路由协议分层路由协议n典型两层路由算法：终端路由算法、网格路由算法 其中一层采用基于位置信息的路由协议。n终端路由算法：结合了TLR（Terminode Local Routing ）和TRR（Terminode Remote Routing） TLR：使用DV信息确定路由并转发数据分组，但分组转发 的范围（跳数）有限，其上限称为本地半径。 距离节点S的跳数不大于本地半径的所有节点都是S的TLR可达节点。 对于TLR算法不可到达的节点，采用TRR算法转发数据分组 TRR：类似于源路由协议，源节点给出一个到目标节点的路 由估计，由一