改进的GPSR模型和其仿真分析.ppt

* * * * * * * 改进的GPSR模型及其仿真分析 2012-28-12 文章结构介绍 无线传感器网络 GPSR算法描述 改进的GPSR算法 网络模型 前向区域划分 节点概率传输机制路径转发域 算法分析 仿真实验及性能分析 结论 无线传感器网络 无线传感器网络 （WSNs） 是由大量具有数据感知、 数据存储和数据通讯能力的传感器节点通过多跳自组织方式构成的分布式网络系统。 NP难问题。NP=P。 高效选择路径、高效转发数据 综合考虑多约束条件下的路由选择问题，采用数学推理逼近路由选择的最优解 GPSR算法描述 XUZWUX，出现循环 删除ZW，构造XUZD 改进算法网络模型 将无线传感器网络抽象为一个平面图G： G= （V,E）。其中V={ni|ni为整个网络拓扑中传感器节点，i=1,2,…,m}为传感器节点集合， E={ni,nj|ni, nj∈V， dij≤min （ri,rj ）， i, j=1,2,…,m}为任意两个能够互相直接通信的节点之间的链路集合，满足 E属于V X V。dij表示节点ni与节点nj的欧氏距离。节点ni的传输半径记为ri，记sink节点为节点ns。由节点ni与节点ns所构成的直线方程为：(y－yi)/ (x－xi)= (ys－yi )/(xs－xi)， 即：(ys- yi)x + y(xs-xi)+xi(ys-yi)-yi(xs-xi)=0，由此， 节点ni的邻居节点nj到过节点ni与ns节点所在直线的有向距离 dv(nj,ni,ns)为： 前向区域划分 GPSR算法中， 如图2距sink节点较近的邻居节点如果多次承担数据转发任务， 其节点能量将较快耗尽， 导致前向区域出现路由空洞， 使得整个网络性能下降。为了均衡网络节点能量消耗防止网络过早出现路由空洞， 当某节点需要从其前向区域的邻居节点中选择路由下一跳时 首先结合前向区域节点剩余能量对其前向区域进行划分。然后比较所划分子前向区域内节点的平均剩余能量， 并选择具有节点平均剩余能量最大的子前向区域作为该节点的路由转发域。如图3所示， 前向区域划分 如图所示，过点N、I、T的圆弧与线段IN、TS（满足SN=IS=TS）构成的扇形区域记为β，该扇形区域与节点ni的传输区域圆I所重叠的部分即为节点ni的前向区域。该前向区域的划分首先可以保证节点ni在其前向区域内选出的下一跳节点到sink的距离都比自己小；同时还防止路由出现循环回路，使路由算法的解收敛速度加快，保证源节点的数据能尽快传输到sink节点。本文在此前向区域的基础上，对扇形区域β划分为k份子区域，分别记为Sik，k?Z+均能量，然后比较子前向区域内节点的平均剩余能。将具有节点平均剩余能量最大值的子前向区域作为节点ni的路径转发域， 节点ni在此选定的路径转发域中根据提出的概率传输机制选择下一跳节点， 以期达到节点前向区域内邻居节点能量能够平均消耗。 前向区域划分 提出的前向区域划分机制中将节点ni的传输范围相应的直径分为2R/k等份， 并沿着等分点作平行与线段IS的 k – 1条直线交圆Oi于P、 B、 Q点。节点ni在其划分的子前向区域内选择路径转发时做以下限定：（1） 所有的节点满足 nj?V ；（2） 节点ni能够确认其所有邻居节点， 若邻居节点nj位于以节点ni为圆心， R为传输半径的传输范围内， 则有dij≤R；（3） 节点ni能够判断某邻居节点是否在区域β内， 即偏转角θ=∠JIS≤β/2， 其中β=2arccos （R/2dis ）；（4） 节点nj能够判断属于哪个子前向区域，节点nj用有向距离dv （nj， ni， nS ） 来确定自己属于某个子前向区域 （例： Si0， Si1， Si2， Si3 ）。综合以上限定得：β 前向区域划分 选择节点ni的路径转发区域 （FDS） 的算法用伪码描述如下： 算法1 FDS： 转发区域选择算法 输入 传感器节点ni以及它的能量 输出 节点ni的前向子前向区域Sik Begin 1： For j=0 to k－1 2： 由公式 （3） 计算传感器节点ni的前向邻居节点集合Sij和前向区域内节点个数vij； End For 3： 计算前向子前向区域Sij中所有节点剩余能量和前向子区域Sij内所有节点的平均剩余能量Eij； 4： 在k个前向子前向区域Sik内选取平均剩余能量Eik最大的一个前向子前向区域Sik； 5： 输出节点ni的前向子前向区域Sik End 节点概率传输机制路径转发域 多约束情况下， 提出的概率传输机制利用以下几个因素定义邻居节点的传输概率：（1） 邻居节点nj的剩余能量， 剩余能量越大， 则被选择为下一跳节点的概率越大；（2） 节点偏转角， 即节点nj偏离IS的角度 （如图4中的θ）， 如果偏转