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

论文导读：本文提出一种基于抉择因子的QoS多播路由算法—QCFRA_W。算法使用抉择因子合理利用邻居节点资源。分布式路由，基于WSN抉择因子QoS多播路由算法。
关键词：WSN，QoS多播路由，抉择因子，分布式路由
 

1 引言

无线传感器网络是信息感知和采集的一场革命,将给人类的生活和生产带来深远影响.但节点具有能源受限且通常无法补充、节点微型化等形态特征。因此，如何高效使用能量来最大化网络生命周期是无线传感器网络面临的首要挑战[1]。随着无线传感器网络应用的日益广泛，在无线传感器中传输多媒体业务的需求不断提升，通信质量的要求方面也越来越高，QoS多播路由技术已成为网络信息传输的一项关键技术，它可以针对不同业务种类提供服务的聚集效应，从而有效地利用无线传感器中的有限网络资源和能量。但是基于多个不相关可加度量QoS多播路由是NP完全问题[2]。一般QoS路由协议是以链路代价为第一度量的，多播路由过程是建立在满足其它约束条件代价最小的多播树，然而代价最优算法不能保证节点能量利用的最优。无线传感器网络中节点的剩余能量、无线带宽、延时、延时抖动才是反映无线传感器网络本质特性的主要参数。而节点的剩余能量表现得尤为关键[3]。

国内外已提出多种针对无线传感器网络的路由算法[4-6]，其中比较有代表性的是顺序分配路由 (Sequential AssignmentRouting,SAR) 算法 7和DD(Data Distribution)路由算法。论文发表，分布式路由。SAR算法以Sink节点的邻居节点为根生成多个树结构，Packet根据QoS参数、能量情况和Packet的优先级，在所有的生成树中选取一条路径传输。它的缺点是能量消耗过快，同时维护节点的路由表和状态开销很大。DD路由协议是一种典型的以数据为中心的信息传播协议，它与应用紧密联系。其基本思想是传感器节点产生的数据用属性值来表示，当Sink点需要采集数据时，发送Interests消息，泛洪到全网。拥有数据标志属性和Interests相匹配的传感器节点将数据按Interests的反向路径发往Sink。DD路由协议可以分为周期性的兴趣扩散、梯度建立和路径加强三个阶段。但是不适合收到请求后只发一次少量数据的情况，因为这需要花很大的代价来建立梯度。论文发表，分布式路由。

本文提出一种基于抉择因子的QoS多播路由算法—QCFRA_W。QCFRA_W算法使用抉择因子合理利用邻居节点资源，能够以较小的路由消息开销取得较高的路由成功率，依据链路质量参数的不同比重进行调节链路权重，并依据从其链路的动态信息中得到各条链路的权重选择建立路由选择机制. 根据无线传感器网络主要参数的权重，分析比较QCFRA -W、最大可用带宽QCFRA -W-BW，最大延时QCFRA -W-DELAY、最大延时抖动QCFRA -W-DJ的路由成功率、多播树费用。

2 QoS约束多播路由问题网络模型

在研究无线传感器网络路由问题时，可以做如下的假定：

(1) 在无线传感器中每个节点都有一个唯一的标识，并且都有GPS的支持。

(2) 各个节点的有效发射距离相等。若两个节点处于彼此的发射范围之内，则称它们为相邻节点。

(3) 邻居节点之间通过周期性的广播HELLO包来标识自己和相邻节点，并且可以知道相邻节点之间的链路状态[8]。

(4) 由于节点和链路在延时和延时抖动等QoS约束方面具有等价性，所以讨论中只考虑了链路的延时、延时抖动等QoS约束。

定义1：把无线传感器网络表示成一个有向带权连通图G=(V,E)，其中V为传感器节点的集合，E为节点间能互相通信的双向链路的集合。并记e=(u,v)表示从节点u到节点v的链路，e’=(v,u)表示从节点v到节点u的链路。设R为正实数集，R+为非负实数集，对于任意的链路e∈E，可定义链路QoS特征值：延时函数delay(e)：E→R+，固有总能量函数allenergy(e)：E→R+和延时抖动函数delayj(e)：E→R。同样对于任一网络节点n∈V，带宽约束函数bandwidth(e)：E→R+。多播源节点s∈V，多播目的节点集MÍ{V-(s)}，△energy，△delay，△delay_jitter和△bandwidth分别为指定的能量、时延、时延抖动和带宽。

定义2：考虑多播路由问题，给出一棵多播树T(s,M)，P(s,t)为多播树T(s,M)上源节点s到某目的节点t的路由路径。满足：

(1) 时延约束

(1)

(2) 时延抖动约束

(2)

(3) 带宽约束

(3)

(4) 节点剩余能量约束。设Pmin为某多播应用在链路e∈E上所需的最小传输能量，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)为可行链路。

在式中：D(i)和DJ(i)分别表示源节点s到节点i之间的延时值和延时抖动值，energy(j)表示节点j的剩余能量值。

定义4： 参数权重：若记、、和分别为与节点i的有效邻居节点集的平均可用带宽、平均时延、平均时延抖动和平均剩余能量，则有效链路lij各参数权重[9,10]分别为：

lij带宽权重： (4.1)

lij时延权重： (4.2)

lij平均时延抖动权重： (4.3)

lij剩余能量权重： (4.4)

其中，k为权重参数，与节点i的连接链路数来确定取值。对于满足有效链路条件的链路，根据其链路参数权重得到该链路抉择因子C(u,w)值：

(4.5)

其中，w1、w2、w3、w4分别为可用带宽、时延、节点时延抖动和剩余能量在用户QoS需求中相对重要性的权值，0< w1、w2、w3、w4<1且w1+w2+w3+w4=1，w权值越大表示用户对该QoS需求越重要， selectij的值越大说明该条链路在有效邻居节点集中所占的权重越大。在有效邻居集中，根据各条链路的路径抉择因子的大小，选择其中最优的抉择因子对应的节点作为下一跳节点。

3 算法描述

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

 1/2    1 2 下一页 尾页