无线传感器网络

无线传感器网络第1页，共23页，2023年，2月20日，星期五基于地理位置的路由协议一：引言二：基本思想三：信标发送机制四：局部优化问题五：边界转发六：扩展分析七：优缺点第2页，共23页，2023年，2月20日，星期五引言无线传感器网络(WSN)综合了传感器技术、嵌入式计算机技术、现代网络及无线通信技术、分布式信息处理技术等,能够通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的信息,这些信息通过无线方式被发送,并以自组多跳的网络方式传送到终端用户,让观察者知道何时何地发生何种事情第3页，共23页，2023年，2月20日，星期五引言一个典型的传感器网络结构包括传感器节点(Nodes)、汇聚节点(Sink)、基础设施网络(因特网或卫星)以及传感器网络管理者(User).传感器节点：它都其有数据采集、数据处理和数据传输的功能。第4页，共23页，2023年，2月20日，星期五引言传感网特点：电源能址有限性拓扑结构动态变化性节点自组织性寻址以数据为中心通信能力有限，受外界干扰较大计算能力有限传感器节点数量巨大、分布范围广、感知数量大第5页，共23页，2023年，2月20日，星期五引言协议栈结构：感器网络由物理层、数据链路层、网络层、传输层、应用层、能量管理平面、移动性管理平而和任务竹理平面八个部分组成。第6页，共23页，2023年，2月20日，星期五引言数据量路层：传感器节点的能耗四个来源：空闲侦听、冲突、串扰、控制开销网络层路由协议：平面路由协议层次路由协议第7页，共23页，2023年，2月20日，星期五引言随着定位技术的发展,节点可以方便地获得自己的地理位置信息,地理位置路由就是以这些位置信息作为路由选择的依据,并按照一定的转发策略把数据发送到目的节点。第8页，共23页，2023年，2月20日，星期五基本思想GPSR(GreedyPerimeterStatelessRouting)路由算法是使用地理位置信息实现路由的一种算法,它使用贪婪算法建立路由。当节点S需要向节点D转发数据分组的时候,它首先在自己所有的邻居节点中选择一个距离D最近的节点作为数据分组的下一跳,然后将数据分组传送给它。该过程一直重复,直到数据分组到达目的节点D或者某个最佳主机。在发生最佳主机问题的时候,数据分组采用边界转发的策略来实现路由。第9页，共23页，2023年，2月20日，星期五信标发送机制GPSR周期性地向所有邻居节点发送信标(Beacon)信号,来得到需要用到的邻居节点的信息。该信标信号中包含了节点的标识和节点的地理位置信息,信标采用广播的方式发送,节点广播域中所有的邻居节点都会收到该信标信号。GPSR采用了一种随机选取信标发送间隔的策略,一个节点前后两次发送信标的时间间隔在[0.5B,1.5B]上服从均匀分布,其中B为发送信标的平均时间间隔。采用该方法,可以降低多个邻居节点发送信标信号时的冲突率。采用周期性地发送信标信号地方式,可以检测到是否有邻居节点远离或者新节点的加入。第10页，共23页，2023年，2月20日，星期五局部优化问题GPSR路由算法使用了贪婪转发机制,贪婪转发的最大缺点就是会导致局部最优化问题,如图1所示。在该图中,源节点为S,目的节点为D。在前两跳中采用贪婪算法,数据分组到达中间节点F。从图中可以看出,虽然经过节点F存在一条从S到D的路径,但由于在F传输范围内的所有节点中,F距离目的节点D最近,根据贪婪算法节点F将选择自己作为数据分组的下一跳,这样数据分组将不能到达目的节点D,这就是局部最优化(Localoptimum)问题,节点F被称为最佳主机。针对这种情况,GPSR协议提出了边界转发(PerimeterForwarding)策略,该策略作为贪婪转发的一个补充。第11页，共23页，2023年，2月20日，星期五边界转发空旷域问题：由于X在空旷区域内找不到离D更近的邻居节点，因此它将尽力在空旷区域的外部寻找转发节点以向D转发数据分组，X节点将沿着空旷区域的边界寻找到达节点D的路由。第12页，共23页，2023年，2月20日，星期五边界转发右手法则：当一个数据分组从节点y到达节点x后，它经过的下一边是以x为顶点，沿(x,y)逆时针方向上的第一条链路，图3中为(x,z)，后续各边同样依此法则确定。第13页，共23页，2023年，2月20日，星期五边界转发平面图的构造：使用边界转发的前提是要事先构造一个平面图来描述网络拓扑,平面图中任意两条边都不相交,GPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边。对于网络中所有节点,假设一跳通信范围半径都为r,并且都位于同一平面内。如果节点n和m的距离d(n,m)<r,则认为n和m之间有一条边(n,m)。第14页，共23页，2023年，2月20日，星期五边界转发平面图构造：算法要保证在删除图中的某些边,使原图成为RNG或GG时不会引起网络分割。实际应用中,生成平面图需要采用分布式算法,每个网络节点都要运行该算法,它仅仅需要知道附近的网络拓扑信息(在GPSR算法中只需要知道一跳范围内的节点标识和相关节点的位置信息)。第15页，共23页，2023年，2月20日，星期五边界转发平面图构造：RNG(RelativeNeighborhoodGraph)：RNG中节点u,v之间存在边的条件是对于任意的一个节点w,u到v的距离要小于或等于u到w或是V到w的距离的最大值。第16页，共23页，2023年，2月20日，星期五边界转发平面图构造：GG(GabrielGraph)的定义如下:GIG中的节点U,v之间存在边的条件是在以d(u,v)为直径的圆中没有其他节点。第17页，共23页，2023年，2月20日，星期五边界转发实现由RNG或GG建立的平面图的边将整个图分成许多小的互不重叠的有界多边形和一些无界区域,有界区域称为内部face,无界区域称为外部face。边界转发时数据分组依次沿着这些face的边界转发,在每个face中,依据右手法则选择下一条边。第18页，共23页，2023年，2月20日，星期五边界转发当数据分组在节点X进入边界转发模式时,将依次沿着与直线XD相交的face转发该数据分组。依据右手法则选择第1个face内的第1条边,即选择以X为顶点,沿XD连线逆时针方向上的第1条链路XU为第1个face内的第1条边。第19页，共23页，2023年，2月20日，星期五边界转发如果平面图中没有X到D的路径,导致链路中断的节点可能位于内部face也可能位于外部face。GPSR规定不停地转发数据分组直到其进入导致链路中断的节点所处的face,当进入该face后,由于沿该face的边界找不到与XD相交的边,因此数据分组不能进入下一个face,它将沿着整个face边界传输。当数据分组第2次沿着e0(e0为数据分组进入当前face后的第一条边)发送时,就可以推断目的节点不可达,立即丢弃该数据分组,因此边界转发不会导致数据分组在相同的链路上传输两次。第20页，共23页，2023年，2月20日，星期五边界转发数据分组进入边界模式时,GPSR协议会将贪婪转发失败的位置Lp(节点位置)登记到数据分组中。边界转发过程中收到该数据分组的中间点,首先比较Lp和自己的当前位置,如果自己到目的节点的距离比Lp到目的结点的距离更近,就将该数据分组重新标记为贪婪转发模式,并按照贪婪模式进行转发。第21页，共23页，2023年，2月20日，星期五扩展分析在采用贪婪算法的时候,节点依据一定的标准选择一个邻居节点作为数据分组的下一跳。MFR(MostForwardRadius)NFP(NearestWith