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

第4章数据传输路由,地理路由及OPNET网络层仿真,地理路由概述,网络层的核心功能：数据的转发和路由为源节点找到一条通向目标节点的传输路径，接着数据分组从源节点以多跳的方式传送到目标节点。典型的路由协议：WSN：flooding，gossiping，SPIN，directeddiffusion，rumor，LEACH自组网：DSDV，AODV，DSR,地理路由概述,上述各种非地理路由协议比较：大多是通过路由探测包获得网络节点间的连接关系和链路特性，从而确定路由并存储路由表。基于DV的路由协议：收敛速度慢，出现路由环路。基于LS的路由协议：会因路由中若干节点的失效、移动而经常中断路由控制负担较大，带宽资源消耗过多。层次化路由策略：局部的先应式路由与全局的反应式路由的结合，以期达到提高数据传输效率和网络可扩展性的目的。需要维护端到端路由协议，对动态变化网络的适应能力有限。,地理路由概述,基于位置信息的路由协议（地理路由）：需要定位技术支持，节点通过定位技术获得自身、邻居节点以及目标节点的地理位置信息。节点利用这些地理位置信息，可以避免路由探测包的盲目洪泛，从而进行有效的路由发现和路由维护，甚至可以基于无状态的分布式的非端到端的数据转发。,地理路由概述,贪婪路由算法：在整个数据传输中不需要建立端到端的基于全局链路状态的路由，不需要存储路由信息表，也不需要发送路由更新信息。只要求节点准确地存储周围邻居节点的状态信息，可节省能量的消耗，降低节点的内存、计算能力要求；同时能够提供很好的数据传输保障，具有良好的网络可扩展性和鲁棒性。,地理路由概述,基于位置信息的路由算法：实现查询传送和广域数据提取，与物理介质和路由选择无关。需要解决的问题：节点定位贪婪转发空洞绕行目标域内转发,位置服务,地理路由必须事先得到足够的位置信息才能够正常工作，包括如下三种位置信息：节点自身的地理位置信息；节点的所有一跳邻居节点地理位置信息；目标节点的地理位置信息。,位置服务,节点位置获取方法：通常可以借助GPS及各种定位算法获得节点自身的地理位置信息；通过节点间的信息交换，可获得所有一跳邻居节点的地理位置信息；目标节点的地理位置信息的获取是地理路由协议难点：当目标节点静止时，可以通过目标节点的一次性泛洪广播来通过所有节点；当目标节点运动时，需要通过位置服务获取目标节点的地理位置信息。典型的位置服务算法：GLS等,地理路由分类,根据节点在发送数据前是否需要建立路由，地理路由可分为：位置辅助路由协议基于位置信息的路由协议定向区域泛洪贪婪路由算法分层路由协议,位置辅助路由协议：LAR,LAR,LAR：LocationAidedRouting，位置辅助路由思路：利用移动节点的位置信息将寻找路由的区域限制在一个较小的请求区域（requestzone,RZ）内，从而限制路由请求过程中被影响的节点数目，增强了路由发现的目标性，减少了路由请求消息的数量，提高路由请求的效率。前提条件：节点通过GPS获得自己的当前位置(x,y)。假定每个节点知道其它节点的平均移动速度。,LAR算法,操作过程类似于DSR：在路由发现过程中，LAR利用位置信息进行有限的广泛搜索，只有在请求区域（RZ）内的节点才会转发路由请求分组。若在规定时间内路由请求失败，源节点会扩大RZ，重新进行搜索。随着RZ的扩大，路由发现的可能性相应增加。当RZ扩大到全网范围就成了一般的泛洪算法。,LAR算法,位置获取：源节点在发送的“路由请求”中携带自己的当前位置和时间，目的节点也在“路由应答”中携带自己的当前位置和时间，沿途转发请求或应答分组的节点可以得到的源节点或目的节点的位置信息，也可以获得其它节点的位置信息。,LAR算法,确定请求区域（RZ）是LAR算法的关键，两种方法：一、由源节点和目的节点的预测区域确定的矩形区域；二、距离目的节点更近的节点所在的区域。RZ过小将降低路由发现成功的概率，出现无法建立路由的情况；RZ过大会带来多余的控制开销。两种控制路由查找的策略：区域策略和距离策略,LAR算法,区域策略：通过计算目的节点期望区（ExpectedZone,EZ）和路由请求区域（RZ）来限制路由请求的传播范围，只有在RZ中的节点才参与路由查找。操作过程：假设t1时刻节点S要查找节点D的路由，S知道在t0时刻（t0y-z-D）和（x-w-v-D）。但x使用贪婪转发时，x不会将数据包发给w或y，因为在其覆盖范围内找不到一个离D更近的节点作为下一跳。,路由空洞：没有满足贪婪转发条件节点的阴影区域称为路由空洞。（节点x的覆盖范围）与（以x和D之间的距离为半径的圆）的交叉区域没有邻居节点，下图的灰色区域。,路由空洞（续）,此时贪婪转发算法失效，必须用其它机制进行数据包的转发边缘转发及右手法则。,GPSR-边缘转发,边缘转发：右手法则右手法则：针对一个密闭的多边形区域（平面）：遍历区域内部使用顺时针的边顺序。（寻找转发节点的依据）解决图5-3的空洞问题：按照顺时针（x-w-v-D-z-y-x）的顺序遍历空洞区域。,GPSR-边缘转发,节点X到目标节点D的距离已经小于节点A到目标节点D的距离，此时退出边缘转发模式，在X处回到贪婪转发模式，最终用贪婪转发到达目的节点D。,GPSR协议评价,优点：仅依赖于转发节点的一跳邻居节点，节点需要保持的状态信息非常少，仅需要保持其邻居节点的位置信息。在多跳路由有效的网络中，节点的邻居节点数目比网络总节点数小很多，所以每个节点所保持状态信息几乎可以忽略不计。,GPSR协议评价,缺点：信标机制产生了额外的开销。为了减少信标所产生的流量开销，在节点转发的数据包上添加转发节点自己的位置。所有节点的网络接口被设置为混杂模式，这样可以保证当前转发节点的所有邻居节点都可以接收到转发包的一个拷贝。当任一节点转发一个数据包时，可以重新设置它的信标间隔计时器。这种机制以较小的开销（每个包12B）允许让所有的数据包成为信标（扮演了信标的功能，可以向其它节点传递位置信息）。这种优化减少了网络中正在转发数据包区域内的信标流量。,OPNET网络层仿真OPNET三层建模机制有限状态机（FSM，FiniteStateMachine）无线传感器网络OPNET仿真模型GPSR仿真,OPNET三层建模机制,无线传感器网络由多个无线传感器节点组成。监测区域、节点数、节点传输半径、邻节点数、一个无线传感器节点由多种硬件组成，如微控制器（CPU）、无线收发器、传感器电子元件以及各种其它设备，如LED显示、闪存等。节点的每一个组件都可以在不同的状态下运行。例如，一个收发器芯片能够在以下四种状态下运行：关电状态、空闲状态、发送状态、接收状态。CPU可以在空闲状态、中断状态、计算状态下运行。无线传感器节点需要发送或接收数据。,OPNET三层建模机制,OPNET采用了三层建模机制：网络（network）层：设计网络拓扑结构；节点（node）层：设计节点模型；进程（process）层：通过状态转移图实现节点的每一个组成模块的功能。,OPNET三层建模机制-网络层,网络层：监测区域、节点数、节点传输半径、邻节点数、应用类型、节点移动,OPNET三层建模机制-节点层,节点层：分层模型：物理层、MAC层、网络层、传输层、应用层附加功能模块：CPU、移动模块、按照功能划分成不同类型模块：processor、queue数据包传输过程跨层设计,OPNET三层建模机制-进程层,进程层基于有限状态机（FiniteStateMachine，FSM）为各个组件运行过程建立模型，并且按以下规则建立进程模型：节点组件每个操作状态为FSM中的一个状态；每个操作状态之间可能的变化建立成FSM中状态切换的模型；FSM中的每个切换与两个操作状态所需的持续时间相关。,OPNET三层建模机制-进程层,进程层：通过状态转移图实现节点各个组成模块功能；采用Proto-C语言实现每个状态功能；编译和调试进程模型。,backoff,编译,网络模型,无线传感器网络,节点模型,能耗计算,网络层进程模型,GPSR仿真模型,GPSR中要求每个节点能够获得自身无线覆盖范围内的邻居节点列表，必须借助位置服务。在仿真模型中采用变通的方法实现位置服务功能。在仿真开始时利用函数SETNIT完成邻节点统计任务：根据仿真场景中的每个传感器节点的坐标位置和节点的无线覆盖范围计算出每个节点的所有一跳邻居节点。,GPSR仿真模型,在GEO状态中调用SETNIT,常见的下一跳节点选择策略有四种：从N（I）中选择距离目标节点D最近的节点，从而使得到达目目标节点的跳数最少，减少数据在节点中因排队、处理带来的时延。如果信号能量足够大，节点一跳传输范围的半径将越大。从N（I）中选择距离自己最近的邻居节点作为下一跳节点，从而降低节点间相互干扰的可能性。从N（I）中选择节点F，使得角FSD最小，从而缩小数据分组传送的范围。Randomizedcompass路由算法，选择将中间节点与目标节点的连线分为两侧区域，随机地从N（I）中选取一侧区域中角度最小的节点作为下一跳节点。,GPSR仿真-基于距离的GPSR,基于距离的GPSR：选择距离sink节点最近的邻居节点作为下一跳。,基于角度的贪婪路由算法,下一跳节点选择策略：选择与h（源节点或转发节点）和sink所在直线的角度最小的邻居节点作为下一跳。,基于角度的贪婪路由算法,选择下一跳节点的代码实现：GPSR-A,基于角度的贪婪路由算法,GPSR仿真-基于角度的GPSR_A,函数代码：,基于能量和距离选择路由,计算能量消耗