基于WSN抉择因子QoS多播路由算法

1、基于WSN抉择因子QoS多播路由算法论文导读：本文提出一种基于抉择因子的QoS多播路由算法QCFRA_W。算法使用抉择因子合理利用邻居节点资源。分布式路由，基于WSN抉择因子QoS多播路由算法。关键词：WSN，QoS多播路由，抉择因子，分布式路由1 引言无线传感器网络是信息感知和采集的一场革命,将给人类的生活和生产带来深远影响.但节点具有能源受限且通常无法补充、节点微型化等形态特征。因此，如何高效使用能量来最大化网络生命周期是无线传感器网络面临的首要挑战【1】。随着无线传感器网络应用的日益广泛，在无线传感器中传输多媒体业务的需求不断提升，通信质量的要求方面也越来越高，QoS多播路由技术已成为网

2、络信息传输的一项关键技术，它可以针对不同业务种类提供效劳的聚集效应，从而有效地利用无线传感器中的有限网络资源和能量。但是基于多个不相关可加度量QoS多播路由是NP完全问题【2】。一般QoS路由协议是以链路代价为第一度量的，多播路由过程是建立在满足其它约束条件代价最小的多播树，然而代价最优算法不能保证节点能量利用的最优。无线传感器网络中节点的剩余能量、无线带宽、延时、延时抖动才是反映无线传感器网络本质特性的主要参数。而节点的剩余能量表现得尤为关键【3】。国内外已提出多种针对无线传感器网络的路由算法，其中比拟有代表性的是顺序分配路由 (Sequential AssignmentRouting,SA

3、R) 算法 7和DD(Data Distribution)路由算法。论文发表，分布式路由。SAR算法以Sink节点的邻居节点为根生成多个树结构，Packet根据QoS参数、能量情况和Packet的优先级，在所有的生成树中选取一条路径传输。它的缺点是能量消耗过快，同时维护节点的路由表和状态开销很大。DD路由协议是一种典型的以数据为中心的信息传播协议，它与应用紧密联系。其根本思想是传感器节点产生的数据用属性值来表示，当Sink点需要采集数据时，发送Interests消息，泛洪到全网。拥有数据标志属性和Interests相匹配的传感器节点将数据按Interests的反向路径发往Sink。DD路由协议

4、可以分为周期性的兴趣扩散、梯度建立和路径加强三个阶段。但是不适合收到请求后只发一次少量数据的情况，因为这需要花很大的代价来建立梯度。论文发表，分布式路由。本文提出一种基于抉择因子的QoS多播路由算法QCFRA_W。QCFRA_W算法使用抉择因子合理利用邻居节点资源，能够以较小的路由消息开销取得较高的路由成功率，依据链路质量参数的不同比重进行调节链路权重，并依据从其链路的动态信息中得到各条链路的权重选择建立路由选择机制. 根据无线传感器网络主要参数的权重，分析比拟QCFRA -W、最大可用带宽QCFRA -W-BW，最大延时QCFRA -W-DELAY、最大延时抖动QCFRA -W-DJ的路由成

5、功率、多播树费用。2 QoS约束多播路由问题网络模型在研究无线传感器网络路由问题时，可以做如下的假定：(1) 在无线传感器中每个节点都有一个唯一的标识，并且都有GPS的支持。(2) 各个节点的有效发射距离相等。假设两个节点处于彼此的发射范围之内，那么称它们为相邻节点。(3) 邻居节点之间通过周期性的播送HELLO包来标识自己和相邻节点，并且可以知道相邻节点之间的链路状态。(4) 由于节点和链路在延时和延时抖动等QoS约束方面具有等价性，所以讨论中只考虑了链路的延时、延时抖动等QoS约束。定义1：把无线传感器网络表示成一个有向带权连通图G=(V,E)，其中V为传感器节点的集合，E为节点间能互相通

6、信的双向链路的集合。并记e=(u,v)表示从节点u到节点v的链路，e=(v,u)表示从节点v到节点u的链路。设R为正实数集，R+为非负实数集，对于任意的链路eE，可定义链路QoS特征值：延时函数delay(e)：ER+，固有总能量函数allenergy(e)：ER+和延时抖动函数delayj(e)：ER。同样对于任一网络节点nV，带宽约束函数bandwidth(e)：ER+。多播源节点sV，多播目的节点集MV-(s)，energy，delay，delay_jitter和bandwidth分别为指定的能量、时延、时延抖动和带宽。定义2：考虑多播路由问题，给出一棵多播树T(s,M)，P(s,t)为

7、多播树T(s,M)上源节点s到某目的节点t的路由路径。满足：(1) 时延约束(1)(2) 时延抖动约束(2)(3) 带宽约束(3)(4) 节点剩余能量约束。设Pmin为某多播应用在链路eE上所需的最小传输能量，P(s,t)为多播树T(s,M)上源节点s到某目的节点t的路由路径。论文发表，分布式路由。那么此路径上可用的链路能量：(4)在所有满足(1)-(3)条件的多播树集合中，要求P(P)取最大值。定义3：在无线传感器网络G=(V,E)中，对于l(i,j)E，假设满足式(5)的条件，那么链路l(i,j)为可行链路。 (5) 在式中：D(i)和DJ(i)分别表示源节点s到节点i之间的延时值和延时抖

8、动值，energy(j)表示节点j的剩余能量值。定义4： 参数权重：假设记、和分别为与节点i的有效邻居节点集的平均可用带宽、平均时延、平均时延抖动和平均剩余能量，那么有效链路lij各参数权重分别为：lij带宽权重： (4.1)lij时延权重： (4.2)lij平均时延抖动权重： (4.3)lij剩余能量权重： (4.4)其中，k为权重参数，与节点i的连接链路数来确定取值。对于满足有效链路条件的链路，根据其链路参数权重得到该链路抉择因子C(u,w)值： (4.5) 其中，w1、w2、w3、w4分别为可用带宽、时延、节点时延抖动和剩余能量在用户QoS需求中相对重要性的权值，03 算法描述给定图G=

9、V,E,节点 s为多播源节点,目的节点集合为D,构造以 s为根节点且包含所有目的节点的最短路径树 T.假定对于任意存在的边(u,w),其抉择因子为 C(u,w)0. 引进 3个向量 Dist,Mist 和Parent.Dist表示当前搜索到的从源节点 s到节点 u 的最短路径长度;Parent表示在 FLSPT 算法所选择的最短路径上节点 u 的前一个节点,也就是最短路径生成树 T 上节点 u 的父节点;Mist表示生成树 T 上已计算的目的节点到节点 u 的最短距离.设 ADJ(u)表示节点 u 的邻接节点集,Q 为一个待开展节点的序列,存储已被访问但尚未被添加到生成树 T 上的节点.QCF

10、RA_W Algorithm(G,s,D)1. Initialize tree T with sourcenode s and clear Q;2. For all wVDo/算法初始化3. IfwADJ(s) Then4. DistC(s,w); MistC(s,w);Parents;5. QQw;6.Else7. Dist; Mist; Parentnil;8.End If9. End For10. Dist0;Mist0; Parentnil; /源节点为第 1 个已计算节点11. While there exists a node in D thathas not been added

11、 to tree T Do12. Select node ufrom Q which statisfies Dist=minDist|mQ;13. If u isa destination nodeThen /如果是目的节点那么将最短路径添加到 T14. Establishshortest path from source node s to node u;15Mist0; /目的节点那么需将 Mist 向量清零16. End If17. For all wADJ(u) Do18. IfDist= Then QQw End If19. IfDist+C(u,w)20.DistDist+C(u,

12、w); MistMist+C(u,w); Parentu;21. Else IfDist+C(u,w)=DistThen/最短路径不惟一22.If Mist+C(u,w)23.MistMist+C(u,w); Parentu; /记录最优父节点24.End If25. End If26. End For27. End While4 算法复杂性分析4.1 算法时间复杂度分析用 n 表示图 G 中节点数目,e 表示所有边的数目,d(u)表示节点 u 的邻接节点数目.T2 = nlogn + = O(nlogn + e) .算法的总时间复杂度为T = T1 +T2 = O(n) + O(nlogn

13、+ e) = O(n + nlogn + e) = O(nlogn + e) .4.2 算法空间复杂度分析QCFRA_W 算法除了进行图的存储以外,还需要 3 个包含n 个分量的一维向量和一个待开展节点集来存储计算过程的中间信息,而待开展节点集中最多包含 n 个节点.因此,采用图的邻接表存储方式, QCFRA算法的空间复杂度为S = O(e + n) + 4O(n) = O(e +5n) = O(e + n) .1.1 5仿真试验为了验证QCFRA-W的效率性，对其进行了仿真。在实验中，我们共仿真了四个算法：QCFRA-W，最大可用带宽路径算法QCFRA-W-BW，最大延时路径算法QCFRA-

14、W-DELAY，最大延时抖动路径算法QCFRA-W-DJ，以上算法的网络拓扑采用随机网络模型。论文发表，分布式路由。网络覆盖面积100 x100m2，网络节点数目设置为100个，每个节点的发射范围被限制在半径为20m的圆内。论文发表，分布式路由。当两个节点处在彼此的发射范围内，彼此之间就存在一条链路。节点的平均度数是7.48。图1是采用上述算法的100个节点的网络拓扑图，编号为21的节点为源节点，随机选取剩余节点作为目标节点，主要参数取如下值：k=0.0005，w1=0.2，w2=0.3，w3=0.4，w4=0.1，energy_req均匀分布于个能量单位，bandwidth_req=100K

15、，delay_req=300ms，delay_jitter_req=3ms。为了比拟QCFRA-W算法性能，通过调整权值系数将算法进行简化处理，当w1=0，w2=1，w3=0，w4=0时得到最大可用带宽路径算法QCFRA-W-BW，当w1=0，w2=0，w3=1，w4=0时得到延时约束路径算法QCFRA-W-DELAY，当w1=0，w2=0，w3=0，w4=1时得到延时抖动约束路径算法QCFRA-W-DJ，当w1=0.5，w2=0.3，w3=0.1，w4=0.1时得到路径算法QCFRA-W。图3和图4分别是QCFRA-W、QCFRA-W-BW、QCFRA-W-DELAY、QCFRA-W-DJ四

16、种算法在不同的网络规模下多播树费用和路由成功率的比拟结果。实验结果说明，QCFRA-W、QCFRA-W-BW、QCFRA-W-DELAY、QCFRA-W-DJ四种算法在路由过程中由于都有可行链路的约束，所以它们有相近的多播树费用和路由成功率。但是用QCFRA-W算法生成的多播树，不但满足多QoS约束，同时更能真实反映WSN本质特征，所以该算法在路由成功率、多播树费用方面均具有较好的特性。将QCFRA-W算法和SAR算法、DD算法进行比拟。网络覆盖面积100 x100m2，网络节点数目设置为100个、节点传输距离为20m、数据传输率为250Kb、出错率为0、数据包长度为128bit，网络节点分布

17、如图1，其中编号为21的节点代表Sink节点，其余节点代表传感节点。论文发表，分布式路由。实验中，从第2s开始，每隔2s，网络都有30个随机节点构造信息包向Sink节点发送。初始时设定所有节点的初始能量为9000个能量单位，接收一个消息消耗2个单位能量，发送一个消息消耗4个单位能量。实验对两种算法的网络总体能量消耗数据进行了收集整理。由图5可以看出，和SAR算法、DD算法相比，QCFRA-W算法能显著节省网络的整体能量。结合能量均衡的路由策略，网络生存期能得到明显提高。仿真结果说明，和SAR算法相比，QCFRA-W算法的网络生存期提高了78.4%。和DD算法相比，QCFRA-W算法的网络生存期提高了76%。1.2 5结论多播路由算法QCFRA-W通过抉择因子能反映无线网络真实特性的剩余能量、带宽和延时等重要因素，同时通过可行链路的定义使生成的多播链路满