一种多传感器信息融合的qos路由算法

一种多传感器信息融合的qos路由算法

0wsn路由策略无线传感器网络通常用于监测环境变量。检测者通常不涉及单个传输的数据信息，而是信息的统计数据，即以数据为中心。从应用层面来讲,人们往往只关注获得特定的数据,而不会访问某个指定的传感器节点;从网络层面来讲,中间节点不但要负责转发数据分组,而且还需要按照一定的规则对数据进行分析和处理,这样不仅能满足以数据为中心的需求,还可以减少信息冗余,同时节省能量。随着应用的不断深入和拓展,不同的业务对WSN的服务质量(QoS)提出了不同的要求,比如,非实时数据(如温度、湿度参数)要求传输可靠,分组丢失率低,而实时数据(如图像、声音等)对延迟比较敏感等。WSN路由策略不但要体现以数据为中心的特点还要尽量满足不同业务的QoS要求。目前提出的针对WSN的路由协议中,TopDisc和定向扩散(DD)等包含数据融合过程的经典路由协议,其数据等待和数据处理阶段引入的大量延迟使其不能适用于延迟敏感的实时业务。这些协议都是针对单一服务的尽力而为模型。而SAR等QOS路由协议,则缺乏对数据高效的融合手段。改进的PEGASIS协议在进行数据融合的同时考虑了传输延迟,但其假设簇头同sink之间可以单跳通信,这在实际应用中是不现实的,必须考虑节点的有效通信距离。本文提出一种针对多跳无线传感器网络,既能满足实时业务QoS要求,又能对数据进行有效的数据融合处理的路由算法。1基本决策权协议1.1下跳黑色节点,以sik节点为根TopDisc(topologydiscovery)协议是带有数据融合的分簇路由算法。用三色算法作为分簇算法的具体实现,在簇结构形成之前,所有节点都被标记为白色,由sink节点发起三色算法。具体过程如下:①sink节点标记为黑色,并广播查询消息。②白色节点收到黑色节点的查询消息时变为灰色,灰色节点等待一段时间再广播查询消息,等待时间的长度与黑色节点之间的距离成反比。③当白色节点收到一个灰色节点的查询消息时,先等待一段时间,等待时间的长度与白色节点到该灰色节点的距离成反比。如果在等待时间内,收到来自黑色节点的查询消息,节点立即变成灰色节点,否则节点变为黑色节点。④当节点变为黑色或者灰色后,它将忽略其它节点的查询消息。黑色节点成为簇头,灰色节点为簇员。黑色节点以最后传来查询消息的黑色节点作为自己的下跳黑色节点,称为其父黑节点,自己成为子黑节点。图1是由三色算法形成的骨干网络的例子。箭头指向sink节点,各边连接两个黑色节点形成以sink节点为根的树状骨干网络。路由过程中,灰色节点将数据转发给黑色节点,黑色节点将数据融合处理后沿树结构转发给父黑节点。1.2自己父黑节点情况树状骨干网络有以下特点:①父黑节点距sink节点的最小跳数小于他的子黑节点距sink节点的最小跳数。②绝大多数父黑节点是在其子节点所有相邻黑节点中距sink节点最小跳数最小的黑节点。由于延迟的设置,也存在黑节点选择最小跳数稍大的邻居黑节点为自己父黑节点的情况,但这种情况很少出现,可以忽略。③在黑节点的所有邻居黑节点中可能存在距sink节点最小跳数与其父黑节点相同的其它黑节点。④黑节点的父黑节点在此黑色节点与sink节点之间的某条最短路径上。簇结构有以下特点:①簇头节点离sink节点的最小跳数小于等于其簇员节点距sink节点的最小跳数。②簇员节点分为两类,一类距sink节点的最小跳数等于簇头节点距sink节点的最小跳数;一类最小跳数比簇头节点多1跳。如图2所示,S为sink节点,成簇过程中A成为他的成员节点并发送查询消息,C和B收到此查询消息,由于C离A较远,它首先成为黑色节点并发送查询消息,B收到此消息后放弃成为黑色节点而成为C的成员节点,D和E收到查询消息也成为C的成员节点。在C的成员节点中,B与其有相同的最小跳数,而D和E的最小跳数比C多1跳。2基于sisk-qos的节点路由维护DAIQoS算法区分实时业务与非实时业务,以TopDisc协议的分簇路由为基础,通过维护簇间和簇内两个梯度场建立到sink节点的多条最短路径,根据数据包的不同QoS需求采用不同的路由策略进行路由。在保证实时数据的QoS要求的同时尽量对更多数据进行融合处理。算法采用优先级调度法在各节点区分不同业务的转发速度。2.1节点间通信能力及剩余能量传感器网络具有以下特征:①节点随机部署在感知区域,且节点具有惟一ID。②网络中有一个与有线网络直接相连的sink节点。sink节点有持续的电量供应。③节点无法自由移动。④除sink节点外的其它节点具有相同的处理和通信能力,传输距离有限,节点在网络中的地位平等。节点之间连接对称,在相互通讯范围之内的节点互为邻居节点。⑤节点可以根据接收信号强弱估计与邻居节点间的距离。⑥传感器节点能量有限,能够知道自身的剩余能量。⑦节点密度大,存在大量采集数据属性相近的节点,节点收集的数据存在大量冗余需要经过融合处理。2.2评估个体质间梯度内的聚类价值借鉴定向扩散协议中梯度场的概念,建立簇间及簇内两个梯度场。簇间梯度场中,各簇以其簇头节点到sink节点的最短路径上经过簇(包括本簇)的个数作为其簇间梯度值,并建立指向比自己簇间梯度值小1的所有邻居簇(包括父黑节点代表的簇)的梯度向量;簇内梯度场区分前文中介绍的两种簇员节点,与簇头有相同最小跳数的簇员节点(包括簇头节点)的簇内梯度值为0,其它簇员节点簇内梯度值为1。梯度值为1的节点建立指向同簇的邻居节点中簇内梯度值为0的节点的梯度向量。依据前文中介绍的TopDisc协议的特点,结合簇间梯度场和簇内梯度可以找到每个节点到sink节点的多条最短路径。2.3构建分簇网络结构节点维护簇内梯度值IG、簇间梯度值OG。IG=I的节点维护簇内梯度列表IGList,保存同簇的邻居节点中簇内梯度值为0的节点信息。IG=0的节点维护簇间梯度列表OGList,保存簇间梯度值比其小1的所有相邻黑色节点以及到达此黑色节点的网关节点信息。在建立骨干网络的过程中完成对这些信息的维护。列表IGList和OGList的数据结构分别是:改进的三色算法过程如下:初始,所有节点标记为白色。步骤1sink节点标记为黑色,置OG=1,IG=0,并广播消息RMsg(ID,C,OG,IG,P,H)。ID为sink节点ID;C记录传输节点颜色,置为BLACK;OG为其OG值;IG为其IG值;P为sink节点能量,由于sink节点有持续供电,置此值为相当于正无穷的大整数;H为其簇头节点ID,此处为自身ID。步骤2白色节点收到黑色RMsg时变为灰色,记录RMsg中ID>和P值为其簇头ID和簇头能量;置自身OG为RMsg中OG;依据1.2节中的阐释,此种情况下灰色节点离sink节点的最小跳数比它的簇头多1,因此设IG=1;建立IGList,记录簇头ID和能量值。等待一段时间(等待时间的长度与其和黑色节点之间的距离成反比)广播RMsg(ID,C,OG,IG,P,H),其中ID为自身ID;C=GREY;OG和IG为其自身OG、IG值;P为自身剩余能量值:H为其簇头ID;步骤3当白色节点收到灰色RMsg时,他可能成为黑色节点或灰色节点。依据前文中的阐释,在这种情况下,无论自己成为簇头还是成为成员节点,他离sink节点的最小跳数都与其簇头相等,置IG为0,维护OGList,将RMsg中H、ID、IG和P值作为其一条记录。暂时缓存RMsg。等待一段时间(等待时间的长度与白色节点到该灰色节点的距离成反比)。在等待时间内,监听更多的RMsg,如果其OG值小于等于原RMsg中的OG值,则将其相关信息记录到OGList中;如果其颜色为黑色,节点立即变成灰色节点,并记录发来此信息的节点为其簇头节点。在等待时间内没有收到黑色RMsg,本节点成为黑色节点。如果成为黑色节点,则设OG为收到的第一个RMsg中OG值加1;发送RMsg(ID,C,OGIG,P,H),其中C=BLACK;OG为自身OG;IG为自身IG;P为自身能量,IG和H域都为自身IG。如果成为灰色节点,则设OG为其簇头发来的RMsg中OG值;发送RMsg(ID,C,OG,IG,P,H),其中各域设置与步骤2中相同。步骤4当节点变为黑色或者灰色后,继续监听邻居节点发送的RMsg信息。分两种情况:IG=0,则查看RMsg中的OG域,如果OG值小于等于本节点OG值减1,则将信息中H、ID、IG和P域记录到OGList中。IG=1,则查看RMsg中H域和IG域,如果H值和自己的簇头IG相等并且IG值等于0,则将信息中IG和P域记录到IGList中。RMsg在全网范围内一次广播之后建立起分簇网络结构并且维护了两个梯度场。在此过程中,节点可能处在黑色、灰色、白色、和未定4个状态,未定状态出现在白色节点收到灰色RMsg后的那段等待时间。简化流程如图3所示(图中忽略了未定状态节点变为黑色节点和节点发送RMsg的过程)。2.4节点用户体验指标分级调度算法区分非实时业务和实时业务,数据包中带有QoS标识位区分业务类型。设数据融合过程中数据等待时间为常量Tw(仿真实验中取Tw=2s)。簇头节点对两种业务设置两个队列缓冲区,对不同业务的数据等待时间分别计时,融合处理在同一类型数据间进行。为更好地满足实时数据的QoS要求,各节点采用按照优先级调度的策略,实时数据比非实时数据有更高的优先级。在信息包排队时,高优先级的实时数据优先得到调度。设定非实时数据等待时限T,在等待时限T内,信息包必须受到调度。2.4.1数据收集和处理非实时业务借鉴TopDisc的路由策略,当灰色节点产生或收到非实时数据包时,直接将其转发给簇头节点,簇头节点收到第一个非实时数据后将其缓存在非实时队列中,在以后的Tw时间内收集更多非实时数据按一定规则进行处理。等待时间结束后,查看OGList,选择Power值最大的条目,将其GateID项作为下跳节点ID,转发处理后的数据。对再度到来的非实时数据重复以上过程。簇头节点自身产生的数据与其收到的数据做相同的处理。2.4.2节点数据融合过程算法用数据包经过的跳数来估计传输时延。路由过程中,IG=1的节点将IGList中记录的节点作为下跳节点;IG=0的节点将OGList中GateIG值最小的条目中GateID代表的节点作为下跳节点,则数据可沿最短路径转发至sink节点。每个节点估计数据从本节点传输到sink节点的延迟上限Dmax。设每跳传输延迟为常数Td,如果路由过程中数据经过每个簇都参加数据融合过程,则延迟最大。此时要求成员节点将所有产生或收到的数据传给簇头节点。这种情况下,数据经过每个簇都增加2跳传输延迟,OG-1是除本簇外最短路径上经过的簇的数量,所以2×(OG-1)为本簇外路由经过的最小跳数。成员节点还有1跳的簇内路由,因此,数据从某成员节点传到sink节点经过的最小跳数为2×(OG-1)+1。簇头节点的簇内跳数为0,所以数据从某簇头节点传到sink节点经过的最小跳数为2×(OG-1)。最坏情况下除传输延迟外,在每个经过的簇头节点都增加等待延迟Tw。实时数据带有时间戳Ts保存数据的产生时间、最大可接受延迟D和紧急位U。本文假设所有传感器节点有同步的时钟设置。如没有同步时钟也可以通过记录数据经过的跳数对经过时间进行估计。路由过程分为以下几种情况:(1)IG=1的节点产生或收到实时数据:计算数据目前仍然可以接受的延迟值Dnow。如数据产生自本节点,则Dnow=D;否则Dnow=D-(Tnow-Ts),Tnow为当前时间。如果Dnow>Dmax,则将紧急位U设为0,将数据发往簇头节点。如果Dnow≤Dmax,则将U设为1,查看IGList,为每条记录i(NodeIDi,Poweri)计算一个权值Wi如果NodeIDi等于本节点簇头ID则α=1;否则α=2。将权值最大的条目中的NodeID作为下跳节点ID,转发数据包。(2)ID=0的簇员节点产生或收到实时数据:首先,按照(1)中方法计算Dnow。如数据产生自本节点或数据中U=0,仍置U为0。如果Dnow>Dmax,则将数据发往簇头节点;如Dnow≤Dmax则查找OGList中IG值最小且能量值最大的条目中GateID作为下跳节点IG,转发数据。如原数据包中U=1,把U置为0,按照上述方法查找OGList中最佳条目的GateID作为下跳节点ID,转发数据。(3)簇头节点产生或收到实时数据:如数据产生自本节点,则按照(2)中处理自身数据的方法进行处理,不同在于当Dnow>Dmax时使数据在本节点进行融合处理,再进行转发。如数据是从成员节点传来,则察看其U位,如果为1,则数据不参加数据融合,直接转发;否则数据在簇头进行融合处理后再进行转发。转发数据U置为0。转发时按照(2)中介绍的方法选择下跳节点,簇头的融合处理过程与非实时数据相同,将融合后产生实时数据的D值设置为被融合数据中的最小D值。路由过程中各节点只决定本簇内的行为。如果Dnow≤Dmax说明数据在后面路程中经过每一个簇时都参加数据融合是不能满足延迟要求的。此时节点不关心数据还可以参加几次数据融合过程,只是放弃他在本簇内的数据融合。每个节点选择最短路径上的下一跳节点转发紧急数据,尽量减少延迟。由于前面对数据融合的放弃,在以后的传输过程中可能再次出现Dnow>Dmax这种可以进行数据融合的情况。这就做到确保数据QoS要求的前提下尽量对数据进行融合处理。3算法分析与模拟测试3.1数据融合过程DAIQoS算法在以下4方面有明显优势:①在体现WSN以数据为中心的特点方面,路由策尽量使更多数据参加数据融合;②在区别服务的QoS保证方面,算法对实时数据提供QoS保证,并充分考虑非实时数据的吞吐量;③在能量节省方面,数据融合过程减少了网络中出现数据冗余的现象,有效地避免了冗余信息处理带来的额外能量消耗。数据沿较短路径转发,减少网络中的数据转发行为,节约网络能量:④在网络的生存期方面,算法在路由选择时充分考虑下一跳节点的剩余能量,可以有效避开剩余能量较小的路径,使得网络中的节点负载相对平衡,从而延长了网络的生存期。3.2节点初始能量优化仿真实验在网络能量和QoS保障两方面将DAIQoS算法与TopDisc和SAR两个算法进行了比较。仿真工具采用Omnet++3.2p1,网络覆盖面积600×600m2,网络节点数目设置为200个,设置节点的传输距离为70m,信道延迟为0.5s.数据包长度为128bit,控制包长64bit。节点的初始能量均为1000J。收发单位比特的能耗参照文献中的模型。设数据融合过程处理数据为原有