基于任务的无线传感器网络可靠性评价模型

基于任务的无线传感器网络可靠性评价模型

无线传感器网络（无线传感器网络）具有随机性、自主性和适应性强环境的优点，能够满足各种场合接收军事信息的准确性、准确性和完整性。在军事领域等特殊的应用环境下,通常要求系统能够满足关键任务的可靠性要求。WSN属于典型的分布式网络系统,与集中式系统不同,前者由密集型、低成本、随机分布的节点组成的,并具有可靠性高、抗打击能力强、系统可降级使用、易于扩充等特点,尤其适合于作战系统在部分节点失效的情况下仍能够完成特定任务的需要。这类系统的可靠性在保证系统能否完成正常功能及系统性能方面至关重要。因此对WSN开展可靠性能研究是国内外关注的重要研究领域之一。现有不少研究分布式网络系统可靠性建模的文献,但基于任务进行WSN可靠性研究的文献不多见。文献假定节点和通信链路均不可靠的情况,从连通性这一最基本的要求出发建立网络系统的可靠性模型;文献提出并定义了基于任务的可靠度,将网络系统可靠性与系统的功能联系起来,该可靠度仅考虑处理机对系统可靠性的影响,未考虑通信链路对系统可靠性的影响,因而难以全面反映系统的可靠性。文献在文献的基础上综合考虑系统的拓扑结构、任务集、通信链路集和处理单元(节点)集对系统可靠性的影响,提出了航空电子分布式系统的可靠性模型;文献对WSN进行了多级簇结构的可靠性描述,采用连通性和覆盖性对基本簇单元进行可靠性研究,但未引入任务可靠度模型评价方法。本文在上述可靠性建模研究的基础上,针对WSN系统规模大、易失效、分布式的特点,给出WSN系统的任务模型,建立了基于任务的WSN系统可靠性模型,实现了从单个任务的局部可靠性评价到系统全局可靠性评价,针对典型WSN拓扑结构给出了建模实例。1无线传感器网络的结构和节点模型1.1wsn网络模型WSN是由大量的密集部署在监控区域的智能传感器节点构成。通常传感器节点数量众多;在任意时刻,节点间通过无线信道连接,采用多跳、对等通信方式,自组织网络拓扑结构;传感器节点间具有很强的协同能力,通过局部的数据采集、预处理以及节点间的数据交换来完成全局任务。WSN系统如图1所示。由大量无线传感器节点和汇聚节点(sink)组成,传感器节点散布在指定的感知区域内,每个节点都可以收集数据,并通过多跳路由方式把数据传送到sink,sink也可用同样的方式将信息发送给各节点。1.2通信单元WSN的基本组成单位是节点,节点具有传感、信号处理和无线通信功能,由处理单元、通信单元、采集单元和供电单元4部分构成,如图1所示。对于节点间的信息交换通常需要处理单元和通信单元的参与。由于采集单元只是在源节点发生作用,不参与转发节点信息交换。因此,假定采集单元始终处于正常工作。同样,对于供电单元假定其正常工作。2分布式节点。节点是以业务节点为网络系统中节点间信息的交换过程依赖互连网络:某一计算任务的完成,不但依赖本地节点的资源,且要求与其它节点进行通信,获取资源。在WSN系统中,参与信息交互的节点可以有2个、多个或者包括系统中所有的节点,本文考虑2个节点之间进行信息交互的情况。2.1任务的源节点定义任务TS,D用二元组[S,D]表示,S为任务的源节点;D为任务的目的节点。因此TS,D表示源节点为S,目的节点为D任务(信息交互过程)。2.2任务的路径设计将网络系统结构抽象为系统节点和无线通信链路的集合。系统节点包含处理单元和通信单元,由于在WSN中是无线通信链路,其功能通过通信单元来实现。因此,系统由一系列节点单元集(包括处理单元集和通信单元集)构成。任务TS,D执行过程当中对应的系统节点的有序排列构成了任务的路径,用rS,D表示。在复杂拓扑网络中任务的路径可能有多个,其数目设为kS,D.则任务TS,D的路径集为R′TS,D={riS,D|i=1,2,…,kS,D}.式中:任务TS,D的第i条路径riS,D由节点单元集(包括处理单元集和通信单元集)组成,分别以ProriS,D和CriS,D表示ProriS,D={proriS,D|proriS,D∈riS,D},(1)CriS,D={criS,D|criS,D∈riS,D}.(2)则任务TS,D的处理单元集表示为ProTS,D=kS,D∪i=1ProriS,D(3)通信单元集表示为CTS,D=kS,D∪i=1CriS,D.(4)3无线传感器可靠性模型3.1正常工作,误动重,导致失效对于由M个节点组成的WSN系统,假设1)网络系统中的处理单元和通信单元都不可靠,但是只有正常工作和故障两种状态,处理单元与通信单元的故障相互独立,失效率可以不同。2)系统中的任务数为m,从而构成系统的任务集T={TkS,D|k=1,2,…,m}.3.2d和通信单元任务TS,D的完成可以具有多条冗余路径,任务TS,D的第i条路径riS,D的可靠度RriS,D定义为路径riS,D的处理单元集ProriS,D和通信单元集CriS,D正常工作的概率,即RriS,D=P{riS,D}=P(ProriS,D)·P(CriS,D).(5)任务TS,D的可靠度RTS,D定义为任务的路径集RTS,D中至少有一条路径正常工作的概率,即RTS,D=P{kS,D∪i=1riS,D}.(6)根据相容事件的概率公式,(6)式可表示为3.3元素的可靠度网络系统可靠度矩阵R中,行坐标为S,列坐标为D的元素代表任务TS,D的可靠度,即R={RTS,D|S=1,…,M;D=1,…,M;S≠D}.(8)3.4可靠度计算ls可靠度矩阵不能衡量整体指标,为更好的比较不同网络拓扑的可靠性,对可靠度矩阵的所有有效元素求加权平均值,定义其为系统总体可靠度,即:Rsystem=Μ∑S=1Μ∑D=1S≠D(αTS,DRTS,D),式中:αTS,D为任务RTS,D所对应的可靠度影响权重。假定所有任务的可靠度影响权重均相同,系统总体可靠度简化为Rsystem=Μ∑S=1Μ∑D=1S≠DRΤS,DΜ⋅(Μ-1).(9)在针对确定任务集的情况下,系统总体可靠度反映了所有该系统可能执行任务的可靠度。4工作可靠性建模WSN系统拓扑组织非常灵活,在不同的应用中往往采用不同的拓扑形式,拓扑选择对任务乃至系统可靠性有重要的影响,因此对拓扑形式进行可靠性评价在WSN系统总体设计中占有至关重要的地位。通常,面对WSN节点规模较大的特点,需要构建适宜的拓扑结构,层次化簇是WSN拓扑的有效方式,这里讨论的簇是由唯一根节点发起形成的“单晶”方式,各级簇头具有树结构,如图2所示。针对图2中典型WSN网络簇拓扑,利用本文所述基于任务的方法对其进行可靠性建模分析。图2中分簇式传感器网络结构分为两个层次:1)从层L1到层Ln各级簇头;2)最低级别簇内结构。设任务Tu,sink表示源点为u、宿点为sink的任务,其中u为第Ln层中最低层簇内的节点;任务Tu,sink所对应的路径如下表所示,根据簇拓扑的特点,这些路径对应的簇层为Ln→Ln-1→…→L1→sink.因此,除最低层簇以外,各级簇头采用树型结构,该部分的路径不变,始终为hn-1,…,h1,sink;而最低层簇内可采用多种复杂结构,任务可存在多个路径(如图2和表1所示):路径u,y,hn、路径u,z,hn、路径u,l,v,hn等。因此,任务Tu,sink的可靠度分两个部分,可表示为RTu,sink=RTh(n-1),sink∩RTu,h(n),(10)式中:n为簇的深度,h(w)=hw(w=1,…,n);RTh(n-1),sink为路径在簇头部分的可靠度;RTu,h(n)为最低层簇内(简称簇内)的可靠度。由簇的定义和(5)式有RTh(n-1),sink=P(Prorh(n-1),sink)·P(Crh(n-1),sink).(11)下面从簇内和系统两个层次进行可靠度研究,针对簇内将其看作一个包含任务集的子系统,按照前述建模方法,开展其可靠性研究。1)簇内:簇内节点规模对可靠度的影响。2)系统:可靠性元素单元(处理单元和通信单元)对任务可靠度的影响;簇层深度对任务可靠度的影响;采用簇头双冗余措施对任务可靠度的影响。4.1集群内的可靠性分析假定簇内除簇头外,还有N=8个节点。下面先从系统角度对几种典型簇内拓扑结构进行可靠性分析,然后再讨论具体任务的可靠性分析。4.1.1rth的大小星型拓扑如图3(a)所示,根据(6)式可计算出任一任务的可靠度,综合这些任务可靠度就构成了星型拓扑的可靠度矩阵Rstar={RTi,h(n)|i=1,…,N+1;h(n)=1,…,N+1;i≠h(n)}.由于对称性,可知RTh,i=RTi,h|i=1,…,N;RT1,2=RTi,j|i=1,…N;j=1,…,N;i≠j代入(9)式,簇内星型系统可靠度为Rstar=∑S=1Ν+1∑D=1S≠DΝ+1RΤS,DΝ⋅(Ν+1)=2Ν⋅RΤh,1+Ν(Ν-1)⋅RΤ1,2Ν⋅(Ν+1)=2rpro2⋅rc2+(Ν-1)⋅rpro3⋅rc3Ν+1.(12)4.1.2阵rall指数rti全连接型拓扑如图3(b)所示,同样根据(6)式可计算出任一任务的可靠度,综合这些任务可靠度就构成了全连接型拓扑的可靠度矩阵Rall={RTi,h(n)|i=1,…,N+1;h(n)=1,…,N+1,i≠h(n)}.由于对称性,可知RT1,h=RTi,j|i=1,…,N+1;j=1,…,N+1;j≠i代入(9)式,簇内全连接型系统可靠度为Rall=∑S=1Ν+1∑D=1S≠DΝ+1RΤS,DΝ⋅(Ν+1)=Ν⋅(Ν+1)⋅RΤ1,hΝ⋅(n+1)=rpro2⋅rc2.(13)4.1.3可靠度矩阵的计算环型拓扑如图3(c)所示,同样根据(6)式可计算出任一任务的可靠度,综合这些任务可靠度就构成了环型拓扑的可靠度矩阵Rring={RTi,h(n)|i=1,…,N+1;h(n)=1,…,N+1,i≠h(n)}.由于对称性,可知:RTi,h=RTk,j|i=1,…,N+1;j=1,…,N+1;k-j=i;i=1,…,N.代入(9)式,簇内环型系统可靠度为4.1.4节点数目对系统可靠性的影响节点数目对可靠度的影响。考虑系统中可能的一种失效概率情况,即所有处理单元和通信单元失效概率同为pepro,c=10-2情况下,簇内3种不同拓扑系统可靠度与节点数目的关系。从图4可得:1)全连接型拓扑随节点增加系统可靠度不变,但是其开销过大;星型在起初(M<8)会明显下降,之后(M>8)随节点增大下降缓慢并有下限;环型在节点数目较少时(M<10)缓慢下降,随后(M>10)恶化加剧。2)在节点数目较小时,环型可靠度优于星型,这是由于环型的任务通常有两个路径冗余,当数目较小时,使得其占优;但随节点数增加后其任务路径跳数增加使得性能下降很快,且没有下限,所以在M>19时星型可靠度优于环型。3)簇内节点数目不宜过多,否则导致系统可靠度快速恶化;簇内节点保持在一定数量内比如M<38才能保证系统有较高的可靠度(>0.9).4.2任务1:路径集假定N=8,n=5,簇内结构为环型,u=4,宿点为sink,则可得该任务的路径集如表2所示。因此,任务T4,sink的可靠度RTr,sink=RTh(4),sink∩RT4,h(5)=rpro5·rc5·(rpro5·rc5+rpro6·rc6-rpro9·rc9).1任务可靠度与模拟失效率的关系考查网络结构及其3种冗余结构中各种部件单元的失效率对于任务可靠度的影响,假设:所有通信单元和处理单元的失效率为10-3;为了准确反映部件失效率对系统可靠度的影响,将待考查部件单元失效率设为较大的动态范围10-2～10-6.根据本文中的可靠性建模方法,通过编制计算机程序,分别求得各种部件单元在上述失效率的水平时,环型拓扑结构中单一任务T4,sink的可靠度,并给出部件单元失效率与任务可靠度的关系图。由图5(a)可以看出,固定处理单元的失效率为10-3:当通信单元的失效率小于10-3时,任务T4,sink的可靠度随其失效率增加缓慢下降,保持在较高水平;当通信单元的失效率大于10-3时,任务的可靠度随失效率增加迅速恶化。同样,由图5(b)固定通信单元的失效率为10-3,可以得到一致的结果。2sisk可靠度取通信单元和处理单元失效率都为10-2,由图6可以看出:簇头不采取双冗余时,任务T4,sink可靠度随层数增多而急剧下降(n=10时,可靠度降至0.8;n=100时,可靠度非常低,小于0.2);对簇头采取双冗余措施后,任务可靠性明显好于前者,随层数增多而略有下降,在n=100时,也能保持较高可靠度(>0.9).3利用质量标准确定任务可靠性作为网络系统的关键部件,对簇头进行双冗余措施。即对簇头的处理单元和通信单元均采用双冗余,则处理单元和通信单元的可靠度分别为rpro-2=1-p2epro和rc-2=1-p,这里簇层深度n=5,则簇内环型时,任务T4,sink可靠度RT4,sink=RTh(4),sink∩RT4,h(5)=r5pro-2·r5c-2·(r5pro·r5c-2+r6pro·r6c-2-r9pro·r9c-2).当处理单元失效率保持10-3,图7给出了采用簇头双冗余措施前后的任务可靠性比较,可以看出:任务