覆盖算法范文

覆盖算法范文（精选7篇）

覆盖算法 第1篇

无线传感器网络是近几年研究的热点,它主要是由若干个节点组成,节点与节点之间通过传感器参数来进行交互,在无线传感网络中,覆盖控制是最重要的一个应用,通过对网络覆盖的控制的测量可以了解某个区域内的通信情况,更好的了解被该区域中的无线传感网络的覆盖情况。网络覆盖控制主要是针对在无线传感中的节点在一定的受限条件下,通过对节点的设置位置以及网络路由的选择方法,从而在受限的无线网络中使得网络资源得到很好的配置。在无线传感网络中,节点的覆盖分为确定性和随机性两种,在确定性节点设置中,主要是采用人工部署的方法,通过人工部署可以根据实际情况对现场进行部署,从而可以达到最大的覆盖率,随机覆盖主要针对比较危险的区域,比如试验场,重污染化工区,核设备区域,大都主要采用空中投放的方式来进行解决。但是这种方式非常容易造成覆盖的盲区,比如有些区域超过了节点的覆盖范围,另外还容易造成重叠区,浪费了节点的资源。文献[1]提出了采用确定性节点和随机性节点相结合的方式构成了混合无线传感网络.文献[2]提出了混合无线传感器网络的部署策略,通过调节移动节点的位置来进行随机部署。文献[3]提出了利用遗传算法实现覆盖优化,但由于遗传算法本身的收敛速度慢,不适合动态节点选择的实时性要求。文献[4]提出了一种基于粒子群算法的无线传感网络覆盖优化方法,这种方法能够有效的实现无线传感网络的覆盖优化,但在搜索空间的时候,容易陷入“早熟”现象,从而限制了粒子的搜索范围。文献[5]提出了基于虚拟力的混合感知网络节点部署方法。文献[6]提出了对单个移动节点的检测模式进行研究。

现在基本粒子群算法的基础上,引入人工鱼群算法,利用人工鱼群算法快速收敛的特性,加入到粒子群算法中,从而避免了早熟的现象,通过人工鱼群算法的觅食和聚群行为来加速粒子群算法的收敛性,降低了陷入局部最优的几率,从而延长了无线传感网络的生命周期,通过仿真实验,在覆盖优化方面和收敛方面都有了很大的提高。

1 网络覆盖模型

1.1 节点覆盖描述

为了模拟真实的环境,设立一个目标区域,该区域分为MN个网格。每一个网格代表一个检测区域,在这个区域上放置n1个固定的节点和n2个移动节点,给定每一个节点的坐标。节点的感知半径和通信半径分别设为r和R,同时要求通信半径为感知半径的2倍以上,R=2rn,传感器中节点集合表示为C={c1,c2cn},ci={xi,yi,r}表示圆心为(xi,yi),半径为r。

1.2 覆盖率描述

网络覆盖率是传感器中网络部署策略中最重要的一个指标。它是衡量一个网络覆盖利用率的标准,其计算方法是监测区域内能够被节点覆盖的总面积与检测总面积的比值。假设传感器网络中的节点Ci的坐标为(xi,yi),在区域中任意一点坐标是Tj的坐标为(xj,yj),则网络节点与目标节点之间的距离为:

$L(C{}_i,{\rm T}{}_j)=\sqrt{(x{}_i-x{}_j){}^2+(y{}_i-y{}_j){}^2}(1)$

节点Ci到目标节点Tj的测量概率是:

${\rm P}{}_{(C{}_i,{\rm T}{}_j)}=\{\begin{array}{l}0,R{}_s+R{}_e\prec L(C{}_i,{\rm T}{}_j)\\ e{}^{-\alpha \lambda {}^B},R{}_s-R{}_{e}L(C{}_i,{\rm T}{}_j)R{}_s+R{}_e\\ 1,R{}_s-R{}_e\ge L(C{}_i,{\rm T}{}_j)\end{array}(2)$

对于检测区域中的任何一个坐标点(x,y),Ci为目标点的传感器节点的集合,其覆盖的概率是:

${\rm P}{}_{(x,y,c{}_i)}=1-{\displaystyle \prod _{j\in i}[}1-p(x,y,c{}_j)](3)$

传感器中所有的节点集C所覆盖的面积之和就是所有节点覆盖的并集,记作A(c)。

$A(c)={\displaystyle \underset{0}{\overset{L}{\int }}{\displaystyle \underset{0}{\overset{L}{\int }}{\rm P}}}(x,y,s{}_i)\text{d}x\text{d}y(4)$

从公式(2)式(4)中的得到传感网络覆盖率P1(xi,yi)和节点利用率P2(xi,yi)。

${\rm P}{}_1(x{}_i,y{}_i)=\frac{A(c)}{{\rm M}{\rm N}}(5)$

${\rm P}{}_2(x{}_i,y{}_i)={\displaystyle \sum _{i=1}^{n}p}(x{}_i,y{}_i)/{\rm N}(6)$

2 基于粒子群算法和人工鱼群算法的优化

在无线传感网络中,如何保证能够保证网络覆盖率的极大化,节点利用率的极小化。因此,可以看出覆盖优化问题是一个多目标组合优化问题。

2.1 基本粒子群算法

基本粒子群算法(PSO)是目前解决多目标组合优化问题的算法之一,其基本的思想[7]是将空间中的个体比作是一个没有质量和体积的粒子。设群体中第i个粒子为xi={xi1,xi2,,xim},它经历过的位置为pi={pi1,pi2,,pim},其中,最佳的位置为pbest,当前所组成的群体中的所有粒子经历过的最佳位置为pgbest,粒子i的速度用vi={vi1,vi2,,vin}表示。粒子i运动公式为:

其中:w表示惯性权重,c1和c2为常数,rand()为随机数,取值在(0,1)之间。

2.2 人工鱼群算法

人工鱼群算法(AFSA)是李晓磊[8]等人在2002年提出的一种新型的寻优算法,该算法是模拟鱼群觅食的行为,通过鱼之间的集体协作来使群体达到目的。在人工鱼群算法中,每一个备选解被称为一条“人工鱼”,多条“人工鱼”共同存在,合作寻找最优的结果。

在搜索空间中,使用n条组成人工鱼群,其中,第i条人工鱼状态表示为向量Xi=(Xi1,Xi2,Xi3,,XiN),人工鱼群当前的食物浓度用Y=T(x)来表示,在人工鱼群中,鱼个体之间的距离表示为:dij=||xi-xj||,在人工鱼群中的步长用step来表示,人工鱼群的视野范围是Range,Number来表示鱼群个体数,在人工鱼群中的其他伙伴的数目是FNumber,试探次数是TNumber,在人工鱼群算法中,每条人工鱼的状态就是一个解,虽然这个解还不是最优的解,将Xi带入优化函数中,计算出函数的值,从而可以衡量出每条人工鱼的优劣。人工鱼群的基本行为描述如下:

2.2.1 觅食行为

假设人工鱼群算法的当前状态是xi,按照公式(9)随机选择一个状态xj,如果此时的食物浓度满足T(xi)<T(xj),就说明该方向上是可行的,按照公式(10)计算获得,如果T(xi)≥T(xj)则在可视的范围内随机的选择一个状态,来判断是否可以在新的选择的方向上是可行的。在进行了TNumber次数试探之后,如果没有达到前进的条件,则随机的到达一个新的状态。其中rand表示随机数,norm是欧几里德范数。

xj=xi+rand step Range (9)

$x{}_j=x{}_i+randstep\frac{x{}_j-x{}_i}{norm(x{}_j-x{}_i)}(10)$

2.2.2 聚群行为

聚群行为是每条鱼在游动过程中尽量向临近伙伴中心进行移动来避免拥挤,搜索当前在可视范围内伙伴个数n及中心位置xc,当食物浓度T(xi)<T(xc),并且n<FNumber,就表明了伙伴所在的位置有比较高的食物浓度,使用公式(10)来用xc来代替xi,向伙伴的位置前进,如果条件不满足,就继续执行觅食行为。

2.2.3 追尾行为

追尾行为是其中某条人工鱼向临近的同伴进行追捉的行为,它是探索在可视区域内的最优的人工鱼的状态出现T(xi)<T(xmax),且xmax的伙伴数目n<FNumber,就表明xmax所在的位置具有浓度比较的高的食物,并且不拥挤,从而使用公式(10),那么就会用xmax来代替xi,否则执行觅食行为。

2.2.4 公告板

公告板的作用是用来记录最优的人工鱼的状态。在人工鱼的游动过程中,每一条人工鱼都会将自己的状态与公告板中的状态进行相比,如果自身的状态优于公告板中的状态,则用自身的状态取代公告板原来记录的状态,否则,还是自身的状态。

3 基于粒子群算法在人工鱼群算法中改进

3.1 改进人工鱼群算法

人工鱼群算法在搜索方向的选择上避免了陷入局部最优的特性,但是人工鱼群面临两个问题[10,11],(1)漫无目的的随机移动,收敛速度降低;(2)在非全局极值点容易出现严重的聚集情况,搜素准确性降低。为了克服以上的两个问题,在此引入了粒子群算法,根据在粒子群算法中的计算每个粒子的在进行迭代过程中的权重因子的高低来决定人工鱼群中的搜索状态,在算法中通过公告牌来记录最优人工鱼的个体状态,通过自身的当前的函数值与公告板进行比较,如果优于公告板则用自身的状态去取代公告板,否则,就通过计算人工鱼的状态所处的适应度函数值的高低来保留最优的人工鱼的状态。

3.2 算法流程描述

当前的人工鱼群的数目为N条,假设其中有i条人工鱼的当前状态为xi1,xi2,,xii,在可视范围内选择一个状态xj,用f(x)表示某条人工鱼x所处的浓度。(x)表示某条人工鱼x的权重状态,Tix为第i条人工鱼的公告板上的状态。

1)产生算法的初始值设定初始化人工鱼群规模Np,迭代次数为N,人工鱼群的初始状态X。

2)公告板赋值计算初始化中鱼群中各个人工鱼的个体当前的状态,从而选择最小的值进入到公告板中。

3)行为选择默认情况的行为是觅食行为,各个人工鱼群模拟追尾行为和聚群行为,选择标准是以人工鱼群个体状态中的函数值最小的。

4)公告板在人工鱼进行一次行动之后,检查自身的个体函数值与公告板中的函数值,如果自身的状态值游鱼公告板中的值,则取代之。

5)追尾行为通过粒子群算法,可以更快更好的找到路径上的最小值,从而发现最优路径,根据这个特点,在人工鱼群算法中,加入蚁群算法中的信息素的特性,保证人工鱼群xi搜索到最小值,减少了搜索的时间。

6)检查算法终止条件迭代次数是否达到规定的迭代次数,否则退出算法。

4 算法分析及结果分析

为了验证本算法的性能,现通过两个部分来进行测试,一个测试方面是算法的性能,另一个方面是网络覆盖效率。

4.1 算法性能测试

通过选取三个典型基准函数进行仿真实验。通过软件测试平台Visio Studio.Net 2007中的C#进行测试,操作系统为Windows XP。三个函数如下:

(1)$f1(z)={\displaystyle \sum _{i=1}^D[}z{}_i^2-10\cos (2\text{π}z{}_i)+10]$,它是一个多峰函数,在zi=0(i=1,2,,D)的时候达到最小值;

(2)$f2(z)=(1/4000){\displaystyle \sum _{i=1}^{D}z}{}_i^2-{\displaystyle \prod _{i=1}^D\cos }(z{}_i/\sqrt{i})+1$也是一个多峰函数,在zi=0(i=1,2,,D)时候达到全局最小值0;

(3)$f3(z)={\displaystyle \sum _{i=1}^D[}100(z{}_{i+1}^2-z{}_i){}^2+(1-z{}_i){}^2]$是一个单峰函数,在zi=1(i=1,2,,D)时候达到全局最小值0。

针对以上的三个函数,采用粒子群算法,人工鱼群算法和本文的算法进行比较,其中,在人工鱼群算法中,设定人工鱼群规模M=20,visual为2.85,step为2.5,δ为0.618,Lmax为40,测试函数的维度为2。在粒子群算法中设定w为0.5,c1,c2都为0.5。表1是三种算法的结果。

从表1的结果可以看出,本文提出的算法得到的平均最小值和最小值都要比其他三种算法要好,测试效果非常理想。

4.2 网络路由覆盖测试

设置仿真实验的环境为:网络检测区域为10 m10 m,每一个无线传感器的节点的感知半径是1 m,在Matlab7.0环境下,采用酷睿i3的主频为2.2 GHz的计算机进行仿真的网络覆盖优化。根据检测区域的面积以及传感器的参数,在检测区域内固定位置上放置70个传感器节点,如图1所示,再随意放置30个节点,如图2所示。设定人工鱼群中个数目是Number=200个,人工鱼群的Range=5,最大迭代次数N=500,采用本文的算法,进行了50次实验,在监测区域内进行优化覆盖平均使用是84个节点,节点的使用率是84%,节点的利用率为83.32%,达到了很好的优化覆盖的目的。图3表示进行200次迭代之后的分布情况,图4表示进行了300次迭代之后的节点分布情况。

从图5中可以看出,本文的算法产生的收敛速度所消耗的时间优于三种算法时间,并且从图中发现响应时间随着迭代次数的增加,渐渐的趋于平缓,这说明加快了收敛的速度。在相同的环境下,采用了本文的算法与基本粒子群算法,人工鱼群算法相比,只需更少的迭代次数就可以找到最优解,相对与其他算法而言,响应时间缩短了,在稳定性等方面有了实质性的提高。

5 结束语

在人工鱼群算法的基础上,将粒子群算法引入到传感网络覆盖中来,通过仿真实验表明改进的人工鱼群算法能以较小的代价获得最优的覆盖节点,从而减少了网络的延时,提高了网络的能效性,进一步提高节点的覆盖率,减少移动节点的数量,对于实际的应用具有非常重要的意义。

参考文献

[1] Mihaylova L,Bull D R.Localization of mobile nodes in wireless net-works with correlated in time measurement noise.IEEE Transactionson mobile Computing,2011,(10):44—53

[2]张晋,刘大昕,徐悦竹,等.WSN关键区域覆盖启发式优化算法.计算机工程,2009;35(14):16—19

[3]贾杰,陈剑,常桂然,等,无线传感器网络中基于遗传算法的优化覆盖机制.控制与决策,2007;22(11):1289—1292

[4] Burne R A,Buczak A L,Jin Y C.A self-organizing,cooperative sensornetwork for remote surveillance:Current result.The 13 th Annual Int’l Symp on Aero Sense Conference,Orlandence,Orlando,USA,1999

[5]周彤,洪炳镕,朴松昊.基于虚拟力的混合感知网节点部署.计算机研究与发展,2007;44(6):965—972

[6]邹学玉,曹阳,等.面向移动目标的WSN单个检测模式覆盖问题.华中科技大学学报:自然科学版,2008;36(4):24—28

[7]张文爱,刘丽芳,李孝荣.基于粒子进化的多粒子群优化算法.计算机工程与应用,2008;44(7):51—53

[8]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法.系统工程理论与实践,2002;22(11):32—38

[9]刘白,周永权.基于遗传算法的人工鱼群优化算法.计算机工程与设计,2008;29(22):5827—5829

[10]林梅金,苏彩红,王飞.无线传感器网络覆盖优化算法研究.计算机仿真,2011;28(3):178—181

覆盖算法 第2篇

智能楼宇是建筑技术和现代计算机信息技术的结合,在建筑物内部,采用计算机技术对楼宇中的设备进行自动控制,对信息资源进行优化管理,使人们获得安全、舒适、高效的办公和居住环境。智能楼宇包含了楼宇自动化(BA)、通信自动化(CA)、办公自动化(OA)、安全保卫自动化系统(SAS)和消防自动化系统(FAS)五种功能,其中楼宇自动化控制系统是智能建筑中最基本和最重要的部分[1]。它的任务是对建筑物的能源、环境及安全设施进行实时监测和自动控制。

2 无线传感网络在智能楼宇中的应用

传统的楼宇智能化系统无论是DCS集散控制系统还是FCS现场总线控制系统都是基于有线数据传输系统的,在有线系统中数据传输线缆的安装和维护往往比监测传感器本身的成本要贵,而且随着应用范围的加大有线布局的局限性和扩展性不足的缺点日益明显[2]。无线传感器的低廉造价和无线网络的低成本安装正好弥补了这些缺点,所以将无线传感网络应用在楼宇自控系统中显得非常有意义。文中主要介绍了基于无线传感网络的楼宇火灾监测预警系统构成,并针对楼宇中的无线传感网络的特殊性提出了一种高效的节点覆盖设置方法,以实现无线传感网络的最大覆盖。

3 楼宇火灾预警系统总体结构

基于无线传感网络的楼宇火灾预警系统由数据采集传输单元、数据汇聚单元、中央控制单元三个部分组成。系统总体结构图如图1,数据采集传输单元就是前段监测节点,各类无线节点的传感器采集所监测区域的温度、湿度、烟雾浓度等参数,再由该节点的无线通信模块将信息数据传给邻近节点。在监测区域内,各传感节点的采集数据以逐跳的方式通过无线传感网络形成初期已建立的路由传递给数据汇聚单元。数据汇聚单元即汇聚节点负责将各传感节点的数据汇总进行适当的数据融合处理再传输给中央控制单元,数据汇聚单元与数据采集单元间通过无线方式传输数据,与中央控制单元间用以太网方式连接。中央控制单元包括了管理显示平台、中央控制器、系统服务器,控制单元负责将实时监测数据反应在人机管理界面上,并根据监测参数进行预警判断。控制单元的中央控制器和系统服务器是整个楼宇自动化控制系统的控制核心,火灾预警系统的监测数据和结果只作为一个子系统融入整个自动控制系统里,整个楼宇自动化控制系统还可以包括电梯控制系统、供配电系统等[3]。

4 节点覆盖算法

该系统的应用环境是楼宇的火灾监控区域,由于应用环境相对简单,所以传感节点布置相对野外环境的节点布撒要容易定位,而且系统对传感节点的移动性要求不高,节点一旦布置完成后位置基本上不会改变,因此该环境下传感网络的定位和路由建立算法比较简单明确[4]。而无线传感网络在楼宇中的节点覆盖问题则需要我们重点考虑,因为在节点布置相对容易和节点定位比较明确的情况下,如果能找到一种布置方法使节点高效无缝地覆盖整个监控区域,那么我们的整个无线传感网络的使用效率将大大提高。我们在此研究节点的覆盖问题主要是找出怎样尽可能地用更少的节点去覆盖更广的区域,从而参照这种覆盖算法在楼宇这种室内环境中去布置节点。

在无线传感网络中,假设每个节点的传感范围为圆,每个节点在满能量时传感范围是一样的,那么对于某一固定区域内节点的覆盖问题就可以抽象为等半径的圆覆盖问题。由于要将不规则监测区域全部覆盖也就意味着节点间的重复覆盖,我们关心的问题就是如何用最少的圆覆盖一定的区域,我们知道单个节点的覆盖面积是圆如图2(A),两个节点的覆盖的最大面积是两圆相切如图2(B),三个节点的无缝最大覆盖面积即三个圆心相互间离得尽可能远,即圆心距尽量长如图2(C),要得到最大的覆盖面积就要找出三个圆心距何时最大即的面积何时为最大。

当三个圆面相互重叠时如图3(A)所示,O1、O2、O3的重叠面积为弧ab、ac、bc之间围成的面积S1,S1越小的面积就越大,当a、b、c三点重合时S1最小,假定a、b、c重合于图2(C)中P点,此时三个圆交于P点,我们可以找出此时面积最大满足什么条件。

因为三圆交于一点P,故PO1=PO2=PO3=R(R为圆半径),可以将得出O1、O2、O3在以P为圆心,半径为R的圆上,如图3(B)所示为圆内的内接三角形,我们可以证明这个内接三角形为等边三角形时面积最大。证明过程如下:

如图4所示,假设内接三角形的O2O3边平行于X轴,为了简化证明过程假定圆的半径为1,我们可以清楚的看到同样以O2O3为底边,当O1在Y轴上时面积才可能最大,因为此时三角形的高最大。故设O1、O2、O3的坐标分别为,其中角。

则:

由上述证明结果我们可以知道,当相邻三个传感器节点相互构成正三角形,且该三角形的边长等于3R(R为传感半径)时它的覆盖面积是最大的,覆盖率最高冗余量最少。在智能楼宇里的监测区域布置传感器网络应该尽量靠近这样的位置结构以达到最高效的覆盖。

5 算法应用

如图5(A)所示,在楼宇里一室内监测区域内,传感节点按照高效覆盖算法进行布置,我们可以知道此时的覆盖率最高。图5(B)为此时高效覆盖的拓扑图,那么在实际运用中我们怎么确定在一定区域内需要放置多少节点才能按此算法实现高效覆盖。假设在ba区域内布置节点,节点的传感半径为r,通过数学计算我们可以知道当以此种算法覆盖时,最大覆盖率为,折算过来那么每个节点的覆盖面积为,所以我们可以得出:在ba区域内需要的理论节点数为的取整。

6 结束语

在智能楼宇中利用无线传感器网络进行火灾监测报警具有很好的实用性和可靠性,无线传感器网络的应用在实际项目环境中是个比较新的课题,很多方面诸如通信协议、路由建立、定位算法方面都需要在具体环境中去设计实践,文中所讨论的覆盖算法是对其具体应用的一个初探,它的可行性对建立一个高效的无线传感网络提供了有力的支持。经过应用研究,在未来无线传感网络必定会在智能楼宇的控制系统中发挥更大的作用,在面向智能楼宇的能源利用监测、环境数据监测、自动控制等方面无线传感网络的优势会越来越明显。

参考文献

[1]沈佳栋,唐明浩,章力.无线传感网在智能楼宇系统中的应用[C].系统仿真技术及其应用学术会议论文集,2008,(10):658-660.

[2]白华.浅谈无线传感器网络在智能楼宇空调自控系统中的应用[J].科技咨询导报,2007(25):7-8.

[3]江森公司.楼宇自动化控制系统技术方案[J].工程案例楼宇自控,2008(5):85-86.

[4]李玲.面向智能楼宇模拟量监测的无线传感网络协议设计[D].成都:电子科技大学,2006:5-7.

无线传感器网络的动态部分覆盖算法 第3篇

近几年,无线传感器网络(Wireless Sensor Networks, WSN)在电子、计算机、控制等多个领域成为研究热点,并且它被广泛地使用在军事、工业以及科研领域。例如在战场上通过飞机撒播,传感器可以组成网络对战场中敌方车辆和士兵的运动进行及时监测和报告;同时,它还可用于原始森林的防火和动物活动的监测等等。在这些应用场合,监测区域需要大规模部署成百上千的节点。但是由于单个节点带电量有限,并且传感器网络往往被部署在人烟罕至的恶劣环境中,人们无法为节点更换电池。所以如何节省能量从而延长无线传感器网络的生命时间成为一个关键的问题。

无线传感器网络另一个重要的问题是覆盖和连通,它们是评判网络感应和传输数据能力的重要指标。当无线传感器网络覆盖某个区域,如果区域中的任何一点至少被k个节点所感知,这样的覆盖就称k-覆盖 (k-Coverage);如果网络中任两个节点有k条不同的通路,这样的网络就称k-连通(k-connection)。不同无线传感器网络的应用对于覆盖和连通的要求也有所不同。如果要实现较高的监测质量,网络在1-连通的前提下至少1-覆盖监测区域。至今有大量的研究提出了1-连通和1-覆盖的节点布局算法,如随机独立调度算法(RIS)[1],覆盖配置协议(CCP)[2]以及最优密度控制算法(OGDC)[3]等。然而在实际中,由于1-覆盖的无线传感器网络需要大量的节点同时工作,所以整个网络的生命时间比较短暂。事实上,类似的能源浪费完全可以避免。大量的应用场合并不需要1-覆盖的无线传感器网络,局部的覆盖盲区是允许存在的。所以部分研究者提出了部分覆盖方案,它的作用是适当牺牲网络监测质量从而提高网络的生命时间。

文献[4]最早提出了部分覆盖方案并且给它做了明确的定义,即:给定一个高密度抛洒了大量节点的监测区域,在此区域内用一种适当的机制激活部分传感器节点。其它节点为了节省能量仍然处于睡眠状态。这样整个网络在保证部分覆盖的前提下延长了生命时间。

在文献[5]中,Wu等人进一步展开了部分覆盖问题的研究。他们把思路转移到在保证部分覆盖的前提下,如何把多余的工作节点转入到睡眠状态,并且据此提出了一种全新的算法,即LDAS。因为这个算法只能保证监测区域被部分覆盖,所以区域中必然存在覆盖盲区。但是这些覆盖盲区并不是固定的,所以在这种覆盖机制下,监测区域中的突发事件是极少可能被无线传感器网络所忽视。

本文同样提出了一种用于监测的动态部分覆盖算法。此算法第一次用于基于PIR传感器感应模型。通过大量的仿真,得出了监测延迟时间(侵入物从开始移动到被任意节点监测出的时间)和网络生命时间之间的关系,并且证明了该算法能够在保证高监测质量的前提下延长网络的生命时间。

1 传感器的感应与通信模型

在无线传感器网络的实际应用中,监测区域必定抛洒了高密度的传感器节点。这是为了在保证覆盖和连通的要求下能够很好地平衡监测区域中节点的能量损耗。所以引入如下假设:假设监测区域中节点的密度非常高以至于在任意一点都能找到一个节点。

在本文中,采用了PIR节点感应模型,它首先是由Qing等人提出[6]。本文进一步数学量化这个模型:首先以节点为中心把感应区域在十二个方向上做等分。假设每个方向的感应距离在节点出厂前由实际测量所得,那么其余方向的感应距离就可利用插值方法确定。为了分析方便,再适当简化模型,即直接把十二个方向上的感应最远端的端点相连,形成一个十二边形,然后用这个十二边形近似该节点的感应区域。事实上,完全可以假设每个节点在出厂前都把相应的十二边形尺寸拷贝至它的存储芯片中。本文进一步假定节点在各个方向上的通信距离为任意值。

2 动态部分覆盖算法

算法是基于如下三点假设:

(1)每个节点具备自定位能力。

(2)每个节点存储了自身的近似感应区域,即第二节中所定义的十二边形。

(3)为了描述的方便,先假设所有的节点时间同步,在下文中我们会放宽这个假设条件。

在本文的算法中,监测区域被分为N条不重叠且相互平行的带状区域。本文把它们分别标记为Belti,1iN。在任何时间内,节点总是处于如下三个状态:选择状态,睡眠状态以及工作状态。整个算法是周期性的。每个周期分为两个时间段:选择阶段以及稳定阶段。在每个周期的选择阶段内,所有的节点由初始“睡眠状态”进入“选择状态”,无线传感器网络用一种特定的方法选择出N个带状传感器集合,这N个带状传感器集合中所有节点的感应区域之和能够分别覆盖N条带状区域Belti,1iN。

事实上,这N个带状传感器集合类似个带状传感器网络,所以把它们定义为BCSNi(Belt Coverage Sensor Network),1iN。当选择阶段结束时,每个节点重新变为“睡眠状态”。在稳定阶段内,所有的带状传感器集合(BCSN)会相互独立地定时工作γT段时间,然后又重新回到睡眠状态(γ为占空比率,0<γ1)。各个BCSN起始工作的时间点将独立平均分布在(0,T(1-γ))时间段内。算法的周期T必须设定为极大于选择阶段的时间,又极小于单个节点的平均生命时间。

2.1 BCSN的选择机制

在每个周期开始时,首先将确定各个Belt的宽度。Belt1的宽度将独立平均地分布在(0,β)之间。除了Belt1和BeltN,其他带状区域的宽度为β。因为BeltN的宽度必须限定在β内,所以可以通过增加带状区域的数目来控制BeltN的宽度。因此,带状区域的数目,即N必须控制在如下的范围内:${\rm N}\ge \frac{\text{监}\text{测}\text{区}\text{域}\text{的}\text{宽}\text{度}}{\beta }+2$。

接下来,可以解决如何找到一个带状传感器集合(BCSN)来覆盖相应的带状区域(Belt)。假设此带状区域的宽度为l。本文按照从左到右的顺序来选择BCSN中的节点。首先,在带状区域的最左端选择一个节点i,假设它的坐标为(xi,yi)。然后根据限定条件在节点i的右端选择一个最远的节点j,这两个节点必须相互连通并且节点j在θi角(θi的定义如图1所示)内1-周长覆盖[7]节点i。“1-周长覆盖”指节点感应区域的边线至少被另一个节点覆盖,详细定义见文献[7]。

一旦选择好节点j,用同样的方法在节点j的右端选择另一个节点,以此类推。可以简单地证明用这种方法所选择的带状传感器集合将会1-覆盖相应的带状区域。接下来,假设一个传感器节点i位于坐标(xi,yi),节点j与节点i连通并且在θi角内1-周长覆盖节点i。

图1:oi是节点i所处的位置;ai是节点i的近似感应区域,即十二边形与带状区域上边线的交点;bi是节点i的近似感应区域与带状区域的下边线的交点。θi就是角∠aioibi。因为Dj的部分边界处于三角形Δp1oip2之内,所以Dj在角∠p1oip2内1-周长覆盖Di。Dj在角∠p2oip3内没有1-周长覆盖Di是因为没有任何Dj的部分边界处于三角形Δp2oip3之内。

把节点i和j的近似感应区域,即十二边形分别标记为Di和Dj。这里,首先判断Di和Dj是否相交。因为Di和Dj相交的充分必要条件是它们的边相交,所以可以把问题简化为Di和Dj的十二条边是否相交。现在假定Di和Dj的十二条边有部分相交,且把交点以节点i为中心顺时针标记为pi(i=1,2,,k)。可以很容易证明:如果Dj的周长有部分处于三角形(Δpmoip(m+1)modk)之内,那么Dj将会在角∠pmoip(m+1)modk(m=1,2,,k)内1-周长覆盖Di,如图1所示。所以如果要判断节点j是否在在θi角内周长覆盖节点i,只需判断能否找到一个角∠paoipb(a,b∈[1,2,,k]),它包含角θi并且它是由一个或许多个角∠pmoip(m+1)modk(m=1,2,,k)组成,当然在这些角∠pmoip(m+1)modk内,Dj周长覆盖Di。

通过这种方法,可以选择出所有与节点i连通并且在它的θi角内周长覆盖它的所有节点。然后选择一个相距最远的节点作为节点的右相邻节点。

2.2 框架节点集合的作用

为了确保整个网络的2-连通,引入框架节点集合,集合内的节点相互连通并且包围了整个监测区域。假设总能找到节点来组成框架节点集合,这可以在极窄的框架区域内抛洒高密度的节点来实现。框架节点集合具有多重功能,首先它能确保整个网络的2-连通,两个不同BCSN的节点就能通过这两条窄带中的节点来通信;其次它还能提高监测成功率,任何直线移动的侵入物最终都能被它监测出;最后,如果监测区域的面积极大,还能利用框架节点集合把监测区域分割成数个较小的子区域。这样只需保证每个子区域中节点的时间同步性。

3 算法仿真

仿真环境:假定监测区域为10001000的正方形。节点平均地分布在这个监测区域内。在本文中,采用PIR传感器感应模型,并且简化此感应模型为一个十二边形。传感器在十二个方向上的感应距离服从N(100;14.752),即为文献[6]中得出的N(217;322)。这里暂不考虑节点在各个方向上通信距离的限制。

根据监测应用的定义,侵入物将在任意时刻随即出现在任意方位点,并在区域内随机移动任意一段距离然后消失。如果侵入物连续移动一小段距离后被监测出,可以用一段直线来近似侵入物的移动轨迹[8]。因此,为了简化分析,本文假设侵入物在监测区域的最右下角出发,以速度V和仰角θ(0θ90°)直线向前移动。

为了叙述的方便,定义监测延时为侵入物从出发到被网络中任意节点监测出所用的时间。所以本文仿真的重点将是找到监测延时与网络生命时间之间的关系。仿真中一些可调的参数设置如下。

带状区域的宽度β:β的选择决定了每个周期的选择阶段内组成带状传感器集合的节点总数。通过仿真得出β和带状传感器集合节点总数的关系,从而确定一个合理的β。

周期T:周期时间必须设定为极大于选择阶段的时间,又极小于单个传感器的平均生命时间。这里定义T等于600秒。

抛洒的节点总数:因为我们假设监测区域中节点的密度非常高以至于在任意一点都能找到一个节点,所以本文假设随机抛洒的节点总数为20000个。

占空比率γ:本文中,γ是一个重要的变量,并且0<γ1。

侵入物的移动速度V和移动仰角θ:这里假定V为一变量,θ=45°。

3.1 β的选择

β的选择决定了每个周期中组成带状传感器集合的节点总数。通过仿真得出β和BCSN中节点总数的关系,如图2所示。当β等于40(即为节点平均感应距离的0.4倍)时,BCSN中节点总数大约是它最小值的3倍。在本文的接下来的仿真中,定义β等于160,即为节点平均感应距离的1.6倍。

3.2 监测延时与网络生命时间之间的关系

当γ=1时,传感器网络在每个周期的任意时刻1-覆盖监测区域,并且侵入物的监测延迟为零。为了分析方便,假定此时网络生命时间为定值Tfull。当γ<1时,传感器网络只能部分覆盖监测区域,侵入物的监测延迟也将大于零。但是此时由于带状传感器集合在周期T段时间内只工作γT段时间,所以传感器网络的生命时间实际上将提高为$\frac{1}{\gamma }\cdot {\rm T}{}_{\text{f}\text{u}\text{l}\text{l}}$。所以监测延时和网络生命时间的关系实际上等效于监测延时与$\frac{1}{\gamma }$的关系,即如图3所示。从图中可以看出侵入物的移动速度极大地影响两者关系。高速度的侵入物能够在极短时间内到达监测区域的边缘从而被框架节点所监测出,而低速度的侵入物虽然需要更长的时间到达框架节点集合的感应区域,但是它很容易被带状传感器集合所监测出。从图中得出更加惊喜的结果:当占空比率γ接近于零时,最大的监测延时仅为周期T的三分之二。这就是说网络的生命时间可以提高到无穷大,而同时侵入物的监测延时却还控制在周期时间T内。如果节点的硬件允许设定一个极小的T值和一个极小的占空比率γ,那么网络的生命时间可以达到极大值而同时监测延时却为极小值。

E(R)是传感器平均感应距离,T是周期时间,在本文中E(R)=100m;T=600s。

4 结束语

提出了一种用于监测的动态部分覆盖算法。它在延长无线传感器网络工作时间的同时也能实现较好的监测质量。在算法的实现中,本文第一次使用了PIR传感器感应模型并且假定传感器各个方向的通信距离为任意值。通过仿真,证明了算法不仅能够很好地提高网络的生命时间,并且具有较好的监测效果。通过监测延时和网络生命时间的关系分析,得出当接近于零时,最大的监测延时仅为周期T的三分之二。这就是说理想情况下,网络的生命时间可以提高无穷大,而同时侵入物的监测延时却可控制在一个周期时间T内。

参考文献

[1]Lai T H,Balogh J.On k-coverage in a mostly sleeping sensor network[C]//Proceedings of the10th Annual International Conference on Mobile Computing and Networking(Mobicom’04),2004:144-158.

[2]Wang C,Xing G,Zhang Y,et al.Integrated coverage and connectivity configurationin wireless sensor networks[C]//Proceedings of the1st International Conference on Embedded Networked Sensor Systems(Sensys’03),2003:28-39.

[3] Zhang H,Hou J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks[J]//Journal on Wireless Ad Hoc and Sensor Networks,2005:89-123.

[4]Yuzhen Liu,Weifa Liang.Approximate coveragein wireless sensor net-works[C]//Proceedings of the IEEE Conference onthe local Computer Networks30th Anniversary(LCN’05),Nov.2005:68-75.

[5]Wu K,Gao Y,Li F,et al.Lightweight deployment-aware scheduling for wireless sensor networks[J].Mobile Networks and Applications(MONET)Special Issue on”Energy Constraints and Lifetime Perfor-mance in Wireless Sensor Networks,2005,10(6):837-852.

[6]Qing Cao,Ting Yan,John Stankovic,et al.Analysis of Target Detec-tion Performance for Wireless Sensor Networks[C].International Con-ference on Distributed Computingin Sensor Systems,June2005:276-292.

[7] Huang C-F, Tseng Y-C.The Coverage Problem in a Wireless Sensor Network[C].Proceedings of the 2nd. ACM International Conference on Wireless Sensor. Networks and Applications(WSNA),2003:115-121.

覆盖算法 第4篇

无线传感器网路[1](Wireless Sensor Network,简称WSN)是由大量廉价的微型传感器节点随机部署在某一需要监测的区域,通过无线通信的方式自组织而形成的网络系统。近年来,无线传感器网络已广泛应用于军事、医疗、环境、家庭以及其他商业领域等。无线传感器网络的研究主要从节省能量、提高网络的QoS、保持通信量负载均衡、网络的容错率以及安全性等方面来考虑[2]。

大量研究将WSN的目标研究方向转化成覆盖控制问题,从覆盖率出发研究节点的调度问题。覆盖问题指的是传感器节点对需要监测区域的监测程度。目前,无线传感器覆盖按其节点分布方式可以分为静态覆盖和动态覆盖[3],大量的研究工作都是基于WSN覆盖控制问题进行的[4]。文献[5]指出在某一区域中,当传感器感知范围存在重复感知,并且所有交点都被其他节点覆盖到,那么此区域就是完全覆盖的。文献[6]提出了一种基于信标的分布式节点控制算法,节点可以根据信标节点(已知节点)的信息来判定其邻居节点的信息,从而确定该节点的状态情况。文献[7]提出了一种自适应休眠调度算法,利用剩余能量的多少自适应控制网络节点的休眠与活跃。文献[8]研究了基于布尔模型下的休眠节点调度算法(Sponsor Sector算法),提出一种赞助扇区的概念并利用赞助扇区对节点进行调度。算法简单易于实现,然而,该算法考虑的邻居节点都是在该节点的感知范围内的节点。即其考虑冗余节点的方法只考虑节点到其邻居节点的距离小于节点的感知半径的节点。当出现如图1的情况时,该算法不会对节点进行冗余判定而直接将其定义为非冗余节点。

本文针对Sponsor Sector算法的不足提出了一种ARCB算法,考虑了节点间的距离大于感知半径的情况下冗余节点。

2网络模型

N个传感器节点随机静态部署在边长为L(m) 的二维正方形区域内,并假设部署的传感器网络具有如下性质:

(1) 传感器节点采用布尔覆盖模型[9],节点感知半径R相同;

(2) 传感器节点的无线通信范围是以节点为圆心,半径为R'的圆形区域。在通信范围内,节点之间的通信是双向的;

(3) 节点同构,除sink节点(汇聚节点)外,所有的节点初始能量E0 相同且R =2R' ;

(4) 节点可通过GPS设备或者定位算法获知其在地理位置( xi, yi) ;

(5) 每个节点能够确定其自身当前的剩余能量Ei[10];

(6) 节点都可以处于三种状态:准备状态(ready)、活跃状态(active)、休眠状态(sleep);

(7) 网络是事件驱动型网络。

3辅助圆覆盖盲区的节点调度算法

3.1相关定义和定理

定义1:邻居节点集合

对任意传感器节点i ,定义其邻居节点集合N(i)={ j| d(i, j) <2R, j≠i} ,其中d(i, j) 表示节点i到节点j的欧氏距离,数学表达式可以表示为: 。R为节点i的感知半径。

定义2:虚拟传感器节点

如图3,对任意一个传感器节点o存在相互覆盖重叠的传感器节点i和j ,定义重叠交点中以和j距离传感器节点较远的交点为虚拟传感器节点ij。

定义3:辅助圆环

虚拟节点ij为圆心,传感器节点感知距离R为半径的圆定义为辅助圆环。

定义4:覆盖盲区

设V是虚拟传感器节点的集合, 为目标区域,如图3,O定义为覆盖盲区。此定义用在传感器节点中同样有效。

覆盖盲区存在2种情况:

(1) 闭合覆盖盲区:由虚拟传感器节点的感知辅助圆环相交而成的闭合区域。如图2左边

(2) 非闭合覆盖盲区:由虚拟传感器节点的感知辅助圆环相交而成的非闭合区域。如图2右边

定义5:冗余覆盖,冗余节点

设点x是节点i的覆盖区域Si中的任意一点,对于x∈Si,若x∈Uj∈N(i)Sj,则称节点i的覆盖区域为冗余覆盖,节点i为冗余节点。

定义6:覆盖率[11]

传感器监视区域S内,所有节点覆盖区域之和同传感器监视区域的总面积的比值,定义为覆盖率,反映了监视区域内节点的覆盖能力,表示为

定理1:对于任意一个传感器节点i ,如果其邻居节点集合与这个传感器节点i的距离均大于传感器的感知半径R ,则传感器节点i不是冗余节点。

证明:假设传感器节点i的邻居节点集合与其距离均大于传感器的感知半径,即d(i, j) >R,那么一定存在传感器节点i感知圆的圆心这一点(即传感器节点i )永远不可能被任何邻居节点的感知圆覆盖,由定义5得知,传感器节点i不是冗余节点。

引论:有定理1可知,传感器节点i是冗余节点,必然有传感器节点i与其邻居节点集合的距离小于传感器节点的感知半径。

定理2:对于任意一个传感器节点i,如果其邻居节点集合存在相交关系,那么距离传感器节点i较近的交点组成的区域如果存在覆盖盲区,则传感器节点i必然不是冗余节点。

证明:假设邻居节点集合相交点存在覆盖盲区。则覆盖盲区中的任意一点均不被这组邻居节点集合所覆盖,由定义5可得,传感器节点不是冗余节点。

定理3:对于任意一个传感器节点i,在排除定理1和定理2的前提条件下,如果其虚拟传感器节点的感知辅助圆环的交点存在闭合覆盖盲区,且传感器节点i处于此闭合覆盖盲区内,则传感器节点i是冗余节点。

证明:在排除节点不是冗余节点的前提条件下,如图3,对于任意一个传感器节点i ,如果其在闭合覆盖盲区内,则传感器节点i均处于辅助圆环外部。由定义2可知,节点i到虚拟传感器节点的距离均大于传感器感知半径,即ij, 。综上所述,由定义5可知,传感器节点i为冗余节点。

3.2冗余节点的判定流程

随机部署的传感器节点存在大量的重复覆盖区域,假设从一个传感器节点i入手,确定i的冗余覆盖情况,判定流程如图4:

(1) 确定传感器节点i的所有邻居节点N(i) 之间的交点iN(i),选取所有交点在节点i感知范围外的点为交点集OCO,得到交点集为OCO∈?iN(i)。

(2) 计算交点集OCO到节点i的距离,得到距离集DIS ,并将距离集中的元素按从大到小的顺序排列。

(3) 从距离集DIS选取前3个元素,分别以其对应的交点集中的交点iN(i)为圆心,传感器节点的感知范围为半径作辅助圆环,判定其辅助圆环是否存在闭合覆盖盲区;

1如果不存在闭合覆盖盲区,加入交点集中的第四个交点并重复步骤(3)。

2如果存在闭合覆盖盲区,判定节点i所处的位置。

(4) 节点i在闭合覆盖盲区内,节点i为冗余节点,否则,节点i为非冗余节点。

3.3基于辅助圆覆盖盲区的冗余节点调度算法流程

在不降低覆盖率的前提下设计了一种分布式网络的节点调度算法。网络模型中的性质(6)确定了节点所拥有的系统状态。

首先,节点进行初始化设置,传感器网络的生存时间按轮次划分,每轮节点都会进行状态的判定和数据的传输。传感器节点状态在ready、active、sleep状态之间进行切换。当传感器网络进行工作时,每一轮开始节点初始化为ready状态,此时节点广播自身信息,并获取邻居信息;节点通过冗余节点判定机制从监听到的信息来判断自身是否为冗余节点。当其为冗余节点时,节点直接转为sleep状态。如果不是冗余节点,则进入active状态并保持该状态到下一轮调度开始并再次转为ready状态。

如图5,初始化传感器网络节点后,各节点均发送一个SNM消息。SNM消息包括了传感器节点的ID、当前的剩余能量Ei 以及节点位置坐标 ( xi , yi )。当多个节点同时发送SNM消息时可能出现如图6右边所示的阴影部分(覆盖盲区),从而导致信道冲突和消息丢失。因此对每个节点添加一个退避计时器使其能随机等待一段时间Trand 。

覆盖盲区定义:如图6左图所示,节点5发现它的感知区域可以完全被1、2、6节点所覆盖,满足冗余节点条件,5节点进入休眠状态。同时,6节点发现它的感知区域可以完全被3、4、5覆盖,6同节点5一样立即进入休眠状态。但是5和6满足冗余覆盖节点的条件是建立在对方处于活跃状态的基础上,二者相互依赖,当它们独立进行冗余覆盖判断并因为满足冗余覆盖条件而同时进入休眠状态时,网络中将会产生覆盖盲区,如图6右图阴影部分。

从无线传感器节点的剩余能量Ei 和邻居节点的个数N i考虑确定随机退避时间Trand,将剩余能量少和邻居节点个数少的传感器节点优先转入休眠状态。设定的退避时间可以表示为:

3.4算法复杂度分析

如图5,首先,节点获取邻居消息并与其退避时间进行比较的复杂度为O(n),然后,节点判断自身是否为冗余节点的复杂度为O(n2) 。故算法的总复杂度为O(n2),其中n表示节点的最大邻居节点集。

4实验与仿真结果分析

4.1仿真说明

模拟仿真环境为一个100m100m的正方形区域,传感器节点静态随机部署在正方形区域中如图7所示,节点覆盖半径为30m,区域覆盖率达到全覆盖的情况下进行了仿真,需要的节点数如图8所示。

从实验结果可知,当覆盖率达到100%时,监视区域需要的节点个数至少达到23。本文从活跃节点个数、网络生存时间和覆盖冗余度等方面进行了模拟实验并分析结果

4.2节点部署总数,节点感知半径参数分析

在100m100m的区域内,节点的传感半径取15m,通信半径为30m,在区域内随机部署的节点数为{700,800,900,1000,1100,1200,1300,1400,1500}9种情况。并对每种情况进行了20次实验,最后取实验的平均值为实验结果。节点调度后区域的活跃节点数如图9。

从图9中可以看出,本文所采用的ARCBA节点调度算法的活跃节点数明显要比传统的Sponsor Sector算法的活跃节点数目少得多,Sponsor Sector算法没有考虑节点间的距离大于感知半径的冗余覆盖,所以活跃节点数比ARCBA算法多。

在100m100m的区域内随机部署了1 500个传感器节点,节点的感知半径分别取{10m,12m,14m,16m,18m,20m}6个值。仍然对每种情况进行了20次实验并平均值为实验结果。节点调度后仿真结果如图10。

从图10中可以看出,随着感知半径的增大,活跃节点的数目会有所减少。这是由于感知半径增大使得每个传感器覆盖的范围更广,当覆盖总区域不变的情况下,感知半径大的节点覆盖冗余度比感知半径小的要高。本文算法比Sponsor Sector算法的活跃节点要少是由于SponsorSector算法忽略了感知半径以外的覆盖节点,故在相同情况下本文算法比Sponsor Sector算法要具有更少的活跃节点数。

4.3网络生存时间

本文所使用的能量模型参考文献[11],节点总数为{500,600,700,800,900,1000,1100,1200},sink节点处于监视区域中心位置。传感器初始能量为5107 nJ ,传输能量为50 nJ bit ,当节点能量小于5%时,认定节点死亡。实验结果如图11。

仿真表明,网络生存时间随着节点总数的增加而增加。由于相同大小的覆盖范围内节点数目的不同,当此区域内某一节点能量耗尽时,可以激活其他节点来取代已经死亡的节点。故覆盖冗余度越高的区域网络的生命周期越长,本文算法在实验结果中能很好的反映网络的生命周期比Sponsor Sector算法有了很大的提升。

4.4覆盖冗余度

定义在传感器监视区域内,所有节点覆盖区域之和同所有节点覆盖范围的总面积的比值为覆盖冗余度[12],覆盖冗余度反映了监视区域内传感器节点的冗余程度,覆盖冗余度可表示为

在100m100m的区域内,节点的传感半径取10m,在区域内随机部署的节点数为{700,800,900,1000,1100,1200,1300,1400,1500}8种情况。并对每种情况进行了20次实验并取平均值为实验结果。仿真图12反映了节点覆盖冗余度与节点总数的关系。

随着节点总数的增加,网络的覆盖冗余度随之增加,图12显示了本文的算法覆盖冗余度比Sponsor Sector算法要低。但是图中显示ARCBA算法仍然存在覆盖冗余度,故在一定程度上仍能保证网络具有容错力。

5结束语

覆盖算法 第5篇

软件测试是软件工程的重要环节,也是整个软件成本的主要构成,在一些重要的领域内软件测试成本甚至占总成本的60%。许多软件错误是由不同参数相互作用所引起的,参数组合是形成程序缺陷和漏洞一个重要问题。为了尽可能地发现由于参数相互作用而形成的缺陷,必须进行不同参数的组合测试。但是参数组合测试面临着组合爆炸问题,测试用例的数目会随着参数个数或者每个参数取值个数的增加迅速增加,完全组合测试的用例数目往往高达数百万,例如一个模块有13个参数,每个参数有3种取值,那么共有313 = 1594232种可能的参数组合,因此完全测试是不可能的。成对测试也称为两两测试,由于其既能发现大部分参数组合错误又能大量地减少测试用例的数量,具有很好的实用价值[4,5,6]。所谓成对测试就是设计足够多的测试用例,对所有软件系统外部输入参数可能的两两组合至少被测试用例集覆盖一次。设一个系统有N个参数:P={P1,P2,,PN}对于其中的一个参数Pi ∈ P, 1iN 存在Li个可能的取值,用Vi表示,即Vi = {Vi,1,Vi,2,,Vi,Di}。如果一个测试用例集TS满足成对测试。那么任意两个参数的取值组合(Vi,l,Vj,k);Vi,l∈Vi,Vj,k∈Vj ,1i,jN;1lDi,1kDj ,存在一个测试用例TCεTS使得(Vi,l,Vj,k)被TC覆盖。

设一个系统S有三个输入参数A、B、C和D,各个参数的可能的取值如下:

V(A)={2, 3,4}

V(B)={Winxp, Win2k,Vista}

V(C)={IE6,IE7,Firefox2}

V(D)={Mysql,SQLserver,Oracle}

按照全覆盖准则,需要3333 = 81个测试用例,而一个满足成对测试的测试用例最少可以只含9个测试用例,测试用例集如表1所示。

构建满足两两覆盖准则的最小测试用例集一直是人们努力的目标,但是Yu Lie等人已经证明要满足两两覆盖的最小测试用例集是一个NP完全问题[8],因此采用启发式或者人工智能方法产生接近最小用例集是目前采用的主要方法,目前人们构造成对测试的主要方法有交阵列[1,10,17],AETG[4,5],IPO[8]等。IPO方法采用水平扩充和垂直扩充的方法来产生测试用例集。正交阵列构造比较困难,并且并非所有的参数及其取值情况都存在正交阵列,该方法使用有一定的局限性。AETG采用的启发式算法来构造测试用例集,其产生的测试用例集比较少,但是AETG是一个商业软件,费用比较昂贵。

1 成对测试数据生成的遗传算法

1.1 遗传算法

遗传算法是一类模拟生物进化的智能优化算法,它是由J.H.Holland于六十年代提出[7]。通过模拟自然界并应用随机理论而形成的生命进化机制,其主要特征在于群体搜索策略和简单的遗传算子,群体搜索可使遗传算法实现整个解空间的分布式信息探索、采集和继承。

遗传算法是从种群(代表问题潜在解的集合)开始的,按照适者生存和优胜劣汰的原理。逐代演化产生出越来越好的近似解。在每一代,根据问题域中个体的适应度大小挑选个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。新生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。遗传算法包括以下三个基本操作:

选择操作 选择算子从群体中按一概率成对选择个体,某个体Xi被选择的概率Pi与其适应度值成正比。轮盘赌模型和锦标赛模型是两种常用的选择模型。

交叉操作 交叉算子将被选中的两个个体的基因链按概率Pc进行交叉,生成两个新的个体,交叉位置是随机的。其中Pc是一个系统参数。

变异操作 变异算子将新个体的基因链的各位按概率Pm进行变异,对二值基因链(0,l编码)来说即是取反。

遗传算法在测试领域的应用主要集中在结构化测试中,包括语句和分支覆盖[12,14,16]、边界条件分析[15]、路径覆盖[3,9]等方面的测试数据的自动生成。在黑盒测试方面,遗传算法的应用相对较少,主要集中在嵌入式[11]、软件使用模式[13]等方面测试用例的自动生成。

1.2 成对测试生成的算法框架

本文的算法框架受AETG算法启发。构建所有参数覆盖组合UC,算法基本思想是从一个空的测试用例集开始。每次利用遗传算法增加一个测试用例到测试用例集中,该测试用例为当前覆盖UC种参数组合最多的测试用例,并删除该测试用例在UC覆盖的参数组合,一直到UC为空。

具体描述如下:

(1) 初始化参数组合UC和测试用例集TS。

(2) 利用遗传算法计算当前覆盖UC最多的测试用例TC。

(3) 将TC添加到集合TS中TS= TS∪TC, 删除TC 覆盖的UC中参数组合。

(4) 重复步骤(2)和(3),直到UC为空。

设有一个系统S1输入由3个参数组成(A,B,C) ,参数取值个数依次为2,2,3,那么可以构造UC:

1.3 编码方式

所谓编码方式,就是将问题的潜在解使用适合遗传算法的基因编码表示。对于组合测试而言,就是将参数映射成二进制编码。由于不同的参数的取值个数并不相同,一个参数在基因编码中的位数也不相同。一个参数Pi的可能取值为Li,如果2n-1 < Li2n,那么该参数的编码长度为n。设有一个系统S2输入由4个参数组成(P1,P2,P3,P4),参数取值个数依次为4,2,2,3。由于组合测试用例的生成关注点在于测试用例的生成,我们用参数取值的序号来表示参数的实际值,避免参数类型的转换。例如测试用例(3,0,1,2)表示P1取第3个值(第一个为0),P2取第0个值,P3取第1个值,P4取第2个值。若Li2n,那么在Li和2n之间随机填充允许的参数值。系统S2可以采用长度为6的二进制编码表示:P1占用位b0和b1;P2占用位b3,P3占用位b4;P4占用位b5和 b6。对于P4而言,前3个编码00,01,10分别为V4,1,V4,2 ,V4,3,编码11可以随机选取V4,0,V4,1 ,V4,2中的任意一个,也可以是依据某一个启发式算法选取,进一步加大测试覆盖程度,图1选择V4,0作为编码11对应的参数。测试用例(3,0,1,2)的编码表示为110110。

1.4 适应度函数

利用遗传算法生成的测试用例集,要求在满足成对测试准则的前提下,测试用例数尽可能地少,因此在每一代进化时选择尽可能多地覆盖UC中参数组合的测试用例。设群体数量为N,个体(测试用例)TCi覆盖的UC中参数组合数为Ci,1iN。则个体TCi的适应度函数可以表示如下:

$f{}_{{\rm I}}=\frac{C{}_i}{{\displaystyle \sum _{i=1}^{{\rm N}}C}{}_i}$

式中N为候选的个体个数,且∑${}_{i=1}^{{\rm N}}$fi=1。

1.5 选 择

计算当前群体的适应度值后,从当前群体中选择一些个体作为新一代群体的父辈。适应度高的个体,被选中的几率较大,且可能多次被选中;反之,几率较小,甚至不会被选中。根据个体(测试用例)的适应度值fi确定选择的概率PSi =fi。如果累积函数Cj定义如下:

$C{}_j={\displaystyle \sum _{i=1}^j{\rm P}}S{}_i$

在选择新个体时,按照赌轮(rouletter wheele)方式来确定,每个个体TCj处于选择区间[Cj ,Cj+1)。计算时每次产生一个选择随机数,那么处于对应选择区间的个体将被选中作为进化成员。

1.6 交叉和变异

交叉采用单点交叉的方法实现。两个长度为N的个体,分别表示如下:

a1,a2,,am-1,am,,aN

b1, b2,,bm-1,bm,,bN

在m(1<m<N)处进行交叉。则产生的两个新个体分别为:

a1,a2,,am-1,bm,,bN

b1,b2,, bm-1,am,,aN

对于系统S2中有2个测试用例及其编码为:

TC1=(3,0,1,2)TC2=(1,1,0,2)⇒CD1=110110

CD2=011010

选择交叉点为第4位,那么交叉以后编码和测试用例分别为:

CD1=110010CD2=011110⇒TC1=(3,0,0,2)

TC2=(1,1,1,2)

变异可以促进群体的多样化,防止群体进化过早地收敛,即防止群体进化停滞不前或冻结,若无变异,则新群体中的测试数据值即为局限于初始化的数值。变异对于个体选定一个变异位,在变异几率的控制下,将变异位用随机数替换该位,变异过程将产生单个新个体,添加到新一代群体中。由于在本算法实验中采用二进制编码,那对于一个个体(测试用例)a1,a2,,aN,只需将变异位取反就可以得到新的测试用例。以测试用例(3,0,1,2)的编码表示为110110为例,选择变异位为1位和2位,那么变异以后的编码为101110,对应的测试用例演变成为(2,1,1,2)。

2 实验结果

设定遗传算法的初始群体为50个, 交叉操作采用是单点交叉。交叉几率为PC=10%和变异几率为PM=80%, 系统演化最大代数为200代。基于本文讨论的算法,我们实现了一个称为GACT的组合测试工具,采用基于.NET framework 2.0的Visual Studio 2005实现, 编程语言为C#。对一种的输入参数组合,运行5次,取其平均值,GACT运行结果如表2～表4所示。

算法比较数据来自Yu Lie的论文[8], 在表1中R1表示4个3值参数组合;R2表示13个3值参数组合;R3表示20个10值参数组合;R4表示100个2值参数组合;R5表示61个参数,其中15个4值参数,17个3值参数,29个2值参数。从上述结果可以看出,在组合数目比较小时GACT结果略优于IPO方法,但在组合数目较大GACT优势比较明显,如在10个参数,每个参数20值中取值时,GACT测试用例数比IPO方法要少59个。

组合测试要求参数只能有有限多个值。如果某个参数具有无穷多个值,例如参数的取值为整数集,则先应用等价类划分方法将此区域分成几个等价类,在每个等价类中选出一个值来代表这个类中的所有值[2]。利用两两覆盖准则,可以大大地减少测试用例的数量,以R2为例利用穷举法需要313 =1594232个测试用例,利用GACT工具生成的用例数仅仅为18个,为穷举法的0.00112%,可以节省大量测试的成本。

覆盖算法 第6篇

近年来, 随着宇航事业的快速发展, 世界各国及卫星组织相继发射了大量的民用商业卫星。据不完全统计, 商用卫星的最大家族极轨卫星, 目前在轨数量达几百颗。面对如此海量的商业卫星数据, 卫星用户如何选择其所需相关数据已成为制约商用的卫星发展的一个因素。为此, 许多卫星机构相继堆出了卫星覆盖查询系统, 以方便用户能更好更快地对其所需数据作出抉择。但制约卫星对地覆盖查询系统最大的障碍在于如何利用轨道数据及载荷参量建立有效覆盖模型, 因为这不仅涉及到覆盖精度问题, 同时还是影响计算量的重要环节。因此, 建立有效的卫星对地覆盖模型意义重大, 本文提出了一种建立在球面矩形覆盖模型基础上的运用于极轨卫星的平面矩形覆盖模型。

1 卫星 (传感器) 对地覆盖模型

不同类型传感器, 其扫描方式各异。若考虑单位时间内传感器对地覆盖区域, 可将其分为球冠面、球面矩形等不同覆盖模型。本文分别介绍球冠面覆盖模型、球面矩形覆盖模型以及由此转化而来的简化矩形覆盖模型。

1.1 球冠面覆盖模型原理

此覆盖模型在通讯、GPS导航等领域应用非常广泛。如果把地球视为规则的正球体, 该模型假定传感器的瞬时地面覆盖范围为一球冠面, 如图一所示。其中S为卫星所在位置, S'为星下点, 其经度为λs, 纬度为φs, h为卫星瞬时高度, α为传感器观测半角, β为对应的球冠半中心角。由图一可求出球冠面半中心角β:

根据球面三角形的知识可以得出以下球面三角方程式:

其中, λ为经度, φ为地理纬度, 凡满足此方程的 (λ, φ) 的点集合即为覆盖区域边界。

1.2 球面矩形覆盖模型及平面矩形覆盖模型原理

1.2.1 球面矩形覆盖模型原理

球面矩形覆盖模型假定传感器的瞬时地面覆盖区域为一球面矩形, 如图二所示。

由球面几何知识可知, 若想求出球面矩形瞬时包含球面范围, 须求出球面矩形的边界方程, 但此法非常困难且计算量很大。为了在计算量和精度之间找到一个合适的平衡点, 本文提出了一种 (变形) 平面矩形覆盖模型。

1.2.2 平面矩形覆盖模型原理

平面矩形覆盖模型基于以下假设:传感器对地的覆盖宽度不是特别宽 (此条件保证球面弧度较小) ;航天器的轨道倾角在90°附近 (此条件保证球面矩形的覆盖宽近似平行于纬度圈) 。

平面矩形覆盖模型如图三所示:“传感器实际覆盖区域”为单位时间内传感器对地覆盖区域矩形长L为传感器对地扫面幅宽, 矩形宽为星下点单位时间内沿航向扫过的距离;“简化1”四边形是实际覆盖矩形按等面积转化而来 (长边和纬度圈平行, 短边和星下点航向平行) ;“简化2”矩形为“简化1”按等高原则转化而来 (长边和纬度圈平行, 短边和纬度圈垂直) 。“简化2”矩形即为最终平面矩形覆盖模型, 其覆盖区域代表了传感器单位时间内对地覆盖区域。

1.3 平面矩形覆盖模型算法

运用平面矩形覆盖模型求解时刻t传感器对地覆盖区域时, 可按以下步骤进行:

(1) 自定义传感器扫描矩形宽度d (即图三中“简化1”矩形的高度) 以及它所能覆盖的地心纬度角△φ (可取卫星在一个单位时间内转过的地心角) , 该值越小运算精度将越高, 但会增加运算成本;

(2) 计算简化后传感器扫描幅宽L' (也即简化矩形长) :

由等高变换原则可知, “简化2”矩形长L'为:

(3) 求任意时刻星下点S'对应的局部半径:

其中, RE为地球平均半径, f为地球扁率, φs为星下点对应的地心纬度;

(4) 根据星下点S'的局部半径计算该点所在的纬度圈半径:

(5) 由扫描幅宽L'计算纬度圈对应的地心经度角△λ:

(6) 确定某一时刻传感器矩形覆盖范围边界:

通过以上步骤后, 最终得到任意时刻t传感器对地覆盖区域边界, 通过将目标区域经纬度与边界进行比较即可知道其是否在覆盖范围之内。

2 平面矩形覆盖模型精度分析

由图三分析可以知, 在两次转化过程当中, 平面四边形和原覆盖矩形间在面积上存在一些误差, 主要表现在两方面:面积大小误差、面积移位误差。

面积移位误差:在转化过程中, “简化1”四边形和实际覆盖矩形间在转化前后引起的面积错位, 而变得不相重叠的面积差异;

面积大小误差:“简化1”四边形在向“简化2”矩形转化过程中引起的面积大小差异。

2.1 面积大小误差

由图三右侧的转化图可以看出:边沿有色小三角形即为简化后引起的面积误差。由几何关系可以算出, 单次简化引起的面积误差为:

而单次实际覆盖区域面积为:

因此, 可得单次简化引起的面积误差率为:

由式 (10) 可知, 误差率为轨道倾角i、d以及L的函数: (1) 当i=90°或0°时误差率为最小, 随着i的增大或减小都将引起误差率的增大; (2) 误差率η和d呈正比; (3) 误差率和L成反比。由于简化矩形前提假设L不宜过大, 因此不能将L作为改变误差率的因子。

基于以上分析可知, 可以通过以下方式来减小总的面积误差率: (1) 极轨卫星、太阳同步轨道卫星等采用此覆盖模型误差率较小; (2) 减小b的取值, 可适当减小面积误差率。若矩形覆盖宽度b取一无限小量 (即b0+) 时, 面积误差率将趋近于零, 但此法将会增加运算成本; (3) 由图四所示, 若采用多次重复覆盖 (即单次d的取值较大, 但相邻覆盖在面积上有很大重叠) , 虽然不能降低单次面积误差率, 但多次累计面积误差将大幅下降。

2.2 面积移位误差

通过图三右上侧移位图可以发现, 转化过程中引入了上下四个小三角块的面积移位。现假定原覆盖矩形的高为d, 宽为固定值L, 转化后“简化1”四边形的长边为L":, 短边为d':

因此, 根据三角几何关系可以求出单次转化过程中引起的面积移位量为:

面积误差率为:

由式 (13) 可知: (1) η和覆盖宽L成正比; (2) 轨道倾角等于90°时趋近于零, 随着i的增大或减小都将引起的增大; (3) 覆盖矩形宽度d的取值和面积移位误差率成反比。

经分析可通过以下方法减小面积移位误差率: (1) 适当减小覆盖幅宽L; (2) 轨道倾角i接近90°的极轨卫星及太阳同步卫星采用此覆盖模型时效果较好; (3) 适当增大覆盖矩形宽度d值。

2.3 误差综合分析

由面积移位及大小误差分析可知, 影响面积误差率的因素同为三个量:倾角i接近90°时能到达最理想的效果;扫描宽度L越大面积大小误差率将越小, 但面积移位误差率将越大;覆盖矩形宽d越大, 面积移位误差率将越小, 但会增大面积大小误差率。

综合考虑可知:对于扫描宽度L, 应权衡考虑面积大小误差率及面积移位误差率间的关系, 使其达到最优;覆盖矩形宽d的选取可适当大些, 不过宜采用多次重叠覆盖法;轨道倾角i越接近极轨越理想。

2.4 误差对比分析

由图二可知, 球冠面覆盖模型将传感器单位时间内对地覆盖等同一标准球冠面, 而对于极轨卫星或太阳同步卫星而言, 其搭载传感器很少采用该扫面方式, 如Landsat系列的TM及ETM+、spot系列的HRG、CBERS及HJ系列的CCD等传感器均采用光学机械扫描、线性阵列 (推扫式) 扫描等方式对地进行观察 (如图五所示) , 其单位时间对地覆盖范围近似为一球面矩形。显然, 和球冠面覆盖模型相比, 平面矩形覆盖模型更接近于真实覆盖, 由图六可知平面矩形覆盖精度明显优于球冠面覆盖模型。

3 结束语

由以上综合分析可知, 极轨卫星其轨道特性能够较好地满足平面矩形覆盖模型的应用条件 (轨道倾角i在90°左右;轨道高度较低从而覆盖宽度较小) , 这将使转化过程中的面积误差相对较小, 若采用多次重叠覆盖模式进行计算, 能进一步减小整体覆盖面积误差, 使其达到更优。此外, 本模型算法简洁、快速, 能够大大节约运算成本。

摘要：极轨卫星由于其典型的轨道特征而受到业界的青睐, 其数量占卫星总量的绝大多数。单位时间传感器对地覆盖作为制约卫星数据运用的重要因素之一, 其覆盖模型的优劣直接影响覆盖精度和运算速度。本文针对极轨卫星提出了一种平面矩形覆盖模型, 它在保证覆盖精度的基础上大大简化了计算工作量。

关键词：极轨卫星,覆盖模型,传感器

参考文献

[1]刘述民等.基于WEB的资源卫星覆盖查询设计与仿真[J].计算机仿真, 2008, (12) :49-53.

[2]杨嘉墀.航天器轨道动力学与控制[M].北京:宇航出版社, 1995.

[3]刘林.航天器轨道理论[M].北京:国防工业出版社, 2000.

覆盖算法 第7篇

覆盖问题是无线传感器网络的一个基本问题,是近年来该领域的研究热点。目前多数覆盖控制的研究成果都是基于满足全向性感知模型的传感器进行的,但在实际应用中,许多有向传感器,如视频传感器,已被广泛应用于无线多媒体传感器网络中[1]。与基于满足全向性感知模型的无线传感器网络相比,有向传感器网络的覆盖问题更复杂,是该领域的一个重要研究方向[2,3]。

Ma等首先提出了有向传感器网络的概念,设计了一种有向传感器感知模型,并研究了有向传感器网络的覆盖完整性问题[4]。文献[5,6,7,8]等都采用了基于虚拟势场的思想进行有向传感器网络覆盖控制。陶丹等在文献[5]中设计了一种方向可调的感知模型,并以此为基础首先提出了基于虚拟势场的有向传感器网络覆盖增强算法,通过引入“质心”的概念,将有向传感器用质心点代替,并将有向传感器网络的覆盖问题转化为质心分布问题,质心点在虚拟力的作用下运动,消除感知盲区和重叠区。传统基于虚拟势场的有向传感器网络覆盖增强算法只判断和调整方向,节点的调整量为固定值,针对这一问题,黄帅等在文献[6]中利用虚拟力与角度调整量间的关系,根据虚拟力的大小改变节点的角度调整量,提高了网络的调整效率。但是,以上基于虚拟势场思想的无线传感器网络覆盖方法,每个节点均需计算多个相邻节点的合力,节点受力随转动过程不断变化,使得算法较复杂;且节点根据力矢量的大小和方向进行转动,转动角度取值过小会增加调整时间,取值过大则会引起频繁的计算和传感方向的反复调整,且因合力未必为0,可能导致调整过程中角度往复震荡。文献[3]提出了一种分布式贪心算法(DGreedy),以传感器节点的剩余能量为优先级,每个传感器基于局部贪心原则选择工作方向,使传感器网络覆盖尽可能大的区域。但是,DGreedy算法受传感器节点处理顺序影响较大,以剩余能量为优先级的方法没有考虑节点间覆盖区域的相互影响,从而影响整个网络的覆盖率。

本文基于全局贪心原则,提出了一种有向传感器网络覆盖算法。以节点各方向下一重覆盖区域的大小为优先级,优先确定一重覆盖区域面积最大的传感器节点方向,保证了传感器网络的一重覆盖区域面积更大,重叠覆盖区域较少。对比实验验证了本文算法的有效性。

1覆盖算法

1.1 DGreedy算法

分布式贪心算法DGreedy由程卫芳等人提出,并应用于有向传感器网络覆盖中[3]。DGreedy假设传感器节点不同方向的感应范围互不重叠,4个可选方向的传感器节点示例如图1所示,图中Si,j表示第i个传感器的第j个方向。文中还假定所有传感器节点具有相同的结构。给每个传感器分配一个彼此不同的优先级,并定义Gi,j表示节点Si的第j个方向上,没有被更高级的感应邻居所覆盖的面积。

DGreedy算法具体描述如下:

1:if 传感器Si在其所有感应邻居中的优先级最高then

2:$j{}_0=\text{i}\text{n}\text{d}\text{e}\text{x}(\underset{1j{\rm P}}{{\displaystyle \max }}G{}_{i,j})/*$其中P表示传感器节点可选方向的数目*/

3: 将传感器Si的工作方向广播给所有感应邻居

4: return

5:end if

6:while 当前传感器Si收到高优先级感应邻居的工作方向

do

7: 记录邻居的工作方向和覆盖的区域

8: 更新当前传感器Si的Gi,j(1jP)

9: if 传感器Si收到了所有优先级较高的感应邻居的消息

10:$j{}_0=\text{i}\text{n}\text{d}\text{e}\text{x}(\underset{1j{\rm P}}{{\displaystyle \max }}G{}_{i,j})/*$选择1jP方向中Gi,j最大的方向*/

11: if Gi,j0==0 then /*表示传感器Si的所有方向都被高级邻居覆盖*/

12: 关闭传感器Si的感应模块;

13: 退出while循环

14: end if

15: 调整传感器Si的工作方向为j0 /*Gi,j0≠0*/

16: 将自己的覆盖方向广播给优先级较低的邻居

17: return

18: end if

19:end while

1.2 改进的DGreedy算法

DGreedy算法每个传感器以局部贪心的原则确定工作方向,只要感应邻居间的覆盖消息能准确传递,就能在有限时间内终止。但是,传感器的决策顺序,即优先级对最终的覆盖效果有极大的影响,文中以传感器剩余能量为优先级,但以剩余能量为优先级的处理顺序没有考虑覆盖区域面积的影响,因此并不一定能保证传感器的覆盖区域面积最大。同时,文中没有考虑孤立传感器或优先级最高的传感器的传感方向,如图2(a)所示S1～S5五个传感器,假设它们的剩余能量,即优先级从高到低,则S1的传感方向最先被确定,由于S1的优先级最高,其它传感器的存在对它没有影响,此时S1的传感方向可以是4个可选方向中的任意一个;由于S1～S4四个节点互不为邻居,且它们的优先级均高于S5,同理S2～S4的传感方向也可以是4个可选方向中的任意一个,若S1～S4最终选择的方向如图2(a)所示,此时S5的4个可选方向中,均存在重叠区域,显然应选择重叠区域最小的S5,2方向。

本文传感器节点以全局贪心的思想确定工作方向,以传感器节点的最大一重覆盖区域面积大小为优先级,最大一重覆盖区域的定义与DGreedy算法中的Gi,j类似,即节点与邻居间没有重叠的区域,某一节点在某方向上的一重覆盖区域面积越大,则该节点和方向越先被确定。如图2(a)所示,S1～S4四个节点在一个方向上与S5均有重叠覆盖区域,以S1为例,S1存在一个方向为完一重覆盖,因此拥有最高优先级;同理,S2～S4拥有与S1相同的优先级。因此S1～S4的传感方向最先被确定,且选择的方向均为完全一重覆盖方向,如图2(b)所示,此时S5的4个可选方向中,均为完全一重覆盖,可依据固定顺序或指向覆盖区域中心等原则,选择其中任一方向。显然,图2(b)的覆盖效果好于图2(a)。

改进的Greedy算法描述如下:

1:for 所有传感器节点

2: for 所有传感方向

3: 找到具有最大一重覆盖区域面积的方向

4: end for

5: 用数组Range记录各传感器节点的最大一重覆盖区域面积及方向

6: 对Range按一重覆盖区域面积由大到小排序 /*优先级由高到低*/

7:end for

8:while 数组Range不为空 /*还有节点未被处理*/

9: 确定Range[1]节点的传感方向 /* Range[1]为优先级最大的节点*/

10: 更新Range /*更新Range[1]邻居节点的最大一重覆盖区域面积及方向*/

11: 将Range[1]清空,Range中的其他元素前移

12:end while

2实验及分析

下面通过模拟实验评估本文算法的性能,所有实验都用Matalb 7.4.0实现。实验中设定监测区域大小为边长500 m的正方形,不同数目的有向传感器节点随机部署在监测区域中,传感器的覆盖角度为α=90°,传感器可选方向数为P=4,传感半径Rs=60 m。比较了本文算法、DGreedy算法及传感器随机选择工作方向的随机算法Random算法[3]的性能。

当节点个数N=50时,3种算法的覆盖效果如图3所示,图中的圆形表示每个节点的可能覆盖范围,灰色扇形表示每个节点的实际覆盖区域,颜色越深,表示覆盖重叠数越多。很显然,Random算法的覆盖结果中重叠覆盖区域最多,因此覆盖率最低,本文算法覆盖率最高。不同传感器节点数目时,3种算法的覆盖率如图4所示。由于本文算法每次都取一重覆盖区域面积最大的传感器节点及其传感方向,使得整个网络的一重覆盖率较高,多重覆盖率较低;DGreedy算法以剩余能量为优先级,选取一重覆盖区域面积最大的方向,但优先级最高的节点所选方向不一定是所有节点中一重覆盖区域面积最大的方向,因此覆盖率较本文算法有所降低;Random算法节点的覆盖方向随机产生,重叠覆盖区域最多,因此覆盖率最低。

3结语

有向传感器由于传感范围有限,其覆盖问题比基于全向感知模型的传感器覆盖更复杂。有向传感器的覆盖问题,就是按某种原则选择每个传感器的工作方向,以减少重叠覆盖区域,增加一重覆盖区域。本文以传感器最大一重覆盖区域面积作为优先级,以全局贪心原则确定传感器的工作方向,旨在调度传感器的工作方向以覆盖尽可能大的区域。通过仿真实验,与DGreedy算法和Random算法进行比较,验证了本文有向传感器网络覆盖增强算法的有效性。

摘要：针对分布式贪心算法(DGreedy)以传感器节点的剩余能量为优先级,节点处理顺序没有考虑相邻节点间的关系对网络覆盖率的影响,从而影响覆盖率的不足,在此提出了一种新的有向传感器网络覆盖算法。基于全局贪心的原则,以节点一重覆盖区域面积的大小为优先级,优先确定一重覆盖区域面积最大的传感器节点方向,从而保证传感器网络的一重覆盖区域面积更大,重叠覆盖区域较少。对比实验结果表明,该算法能有效提高覆盖率。

关键词：有向传感器网络,全局贪心,一重覆盖,Matlab

参考文献

[1]MISRA S,REISSLEIN M,XUE G L.A survey of multi-media streaming in wireless sensor networks[J].IEEECommunications Surveys&Turorials,2008,10(4):18-39.

[2]李靖,王汝安,黄海平,等.有向传感器网络覆盖控制策略[J].通信学报,2011,32(8):118-127.

[3]程卫芳,廖湘科,沈昌祥.有向传感器网络最大覆盖调度算法[J].软件学报,2009,20(4):975-984.

[4]MA Hua-dong,LIU Yong-he.On coverage problems of di-rectional sensor networks[J].Lecture Notes in ComputerScience:Mobile Ad-hoc and Sensor Networks,2005,3794:721-731.

[5]陶丹,马华东,刘亮.基于虚拟势场的有向传感器网络覆盖增强算法[J].软件学报,2007,18(5):1152-1163.

[6]黄帅,程良伦.一种基于虚拟力的有向传感器网络低冗余覆盖增强算法[J].传感技术学报,2011,24(3):418-422.

[7]陶丹,马华东,刘亮.视频传感器网络中路径覆盖增强算法研究[J].电子学报,2008,36(7):1291-1296.