节点覆盖

节点覆盖（精选3篇）

节点覆盖 篇1

1 概述

现实世界中许多复杂系统都可以被直接或转化为复杂网络表示。复杂网络一般存在一些统计特性,如“无标度”[1],“小世界效应”[2],“社区结构特性”[3]。现在,复杂网络中社区结构发现已经成为计算机科学、生物学、物理学、社会学等领域研究热点之一。例如生物学中蛋白质网络里同一社区内蛋白质往往具有相同功能,社会网络中同一社区范围内的所有个体具有相同行为特征,万维网网络中同一社区内网页属于同一主题或同一关键词相关等。复杂网络社区发现目的就是探测并展示这些复杂网络中固有的社区结构。

自复杂网络中社区发现问题提出至今,各领域学者专家已经提出多种发现算法。2004年Girvan和Newman提出了一个用于刻画网络社区结构优劣的量化标准模块性函数Q[4],并启发其他学者提出基于模块性函数Q的一系列新算法[5,6,7,8],但是该系列算法过程复杂,时间复杂度也较高;2007年Raghavan U N等针对大规模社交网络提出了标签传播算法(LPA)[9],该算法可以在5步之内使得95%以上节点标签达到稳定状态并且适用于超大规模网络,后续有Leung[10],Barber[11],liu[12]等对标签传播进行一系列优化和扩展,但LPA算法的弱点是容易陷入局部最优解同时最终结果对节点更新顺序敏感,算法的准确率有待提升;而国内近年的研究如刘大有[13],何东晓[14]等主要集中在运用蚁群算法和遗传算法结合马尔科夫随机游走或模块性函数Q来产生网络社区结构划分。

本文提出一种基于中心节点覆盖的社区发现算法。算法以拥有最多邻居节点的中心节点开始,依次找到能覆盖整个网络节点的最少中心节点,然后以这些中心节点作为小社区,计算相交小社区间合并度量分值,每次合并两个具有最大合并度量分值的小社区,并以模块性Q值作为全局最优合并序序列评价函数,全局最大Q的合并序列即为最优社区划分结构。

2 算法描述

2.1 定义

定义1:令G=(V,E) 表示具有n个结点、E条边的无向无权复杂网络。seti为节点i的邻居形成的局部社区网络节点的集合,Setall为整个网络节点集合。

定义2:最小覆盖节点集合Listmin={Seti, Seti, Setk,…..},也即邻居节点能覆盖全部网络节点的最少集合。

定义3:社区合并置信度Sim(Ci,Cj)= (cross_a/all_a)*(cross_b/all_b),社区Ci,Cj的节点集合分别为a和b。节点集合a和节点集合b的交集为c,其中cross_a代表节点集合c与集合a相连接的边数目,cross_b代表节点集合c与集合b相连接的边数目,all_a,all_b分别代表集合a和b内部边数目。

定义4:社区交叉节点归属划分。社区Ci,Cj的节点集合分别为Seti,Setj,其节点交集为Setc,对任意节点n∈Setc,若节点n与Seti,内节点有连接的边比与Setj内节点有连接的边多,则节点n重新划分到社区Ci,否则划分到Cj。

2.2 算法步骤

输入:网络G =<V,E>

输出: G的一个局部社区结构

步骤1:找到每个节点的邻居节点,存储在一张哈希表中,设为MapN。其中MapN的元素存储如下:

MapN={{N1, Set1},{N2, Set2},{N3, Set3},……}

其中设每个节点为Ni,节点的邻居节点集合为Seti,时间复杂度为O(n);

步骤2:对MapN按照节点的邻居节点大小排序(排序后,可以保证获取最小覆盖节点集合),把排序后的节点集合(Set1, Set2,Set3,…..)存储在一张表ListTmp中,从ListTmp中提取最小覆盖节点集合Listmin. Listmin中元素满足条件:,时间复杂度O(nlogn);

步骤3:从最小覆盖节点集合Listmin.中顺序选择两两交叉节点集合(每个节点集合形成初始的小社区),计算其社区合并置信度Sim(Ci,Cj)。每一步选择具有最大社区合并置信度的两个社区合并,余下其他所有节点集合作为独立社区,对于存在交叉节点的两个社区按照定义4进行重新划分,形成一个网络社区划分,计算其模块性Q。从以上划分中选择一种有最大Q值得划分作为最终结果。时间复杂度O(ClogC)(c远小于n,为最小覆盖节点集合大小)

3算法应用举例

为了测试算法性能,我们分别使用了计算机随机生成网络和真实世界网络来对算法测试。算法实验环境为:Intel (R) Core TMi5-2450M,CPU 2.50GHZ,内存4GB,操作系统Win764位,编程环境为Java 7,My Eclipse 10。

3.1计算机随机生成的网络

根据Newman等[3]提出了一个用于测试网络社区探测算法性能的随机网络模型RN(a,s, d,zout). 该模型的社区结构已知, 其中a代表网络中社区的个数, s代表每个社区内的结点数目, d代表每个结点的度, zout代表每个结点与社区外结点构成的边数. 它目前作为测试社区探测算法性能的基准数据集,该网络络包含128个节点, 形成4个社区, 每个社区包含32个节点; 每个节点与其所在社区内部节点的连接数为zin, 与其他社区节点的连接数为zout, 且满足zin+ zout= 16. 随着zin的减小, 该网络社区结构越来越模糊。同时使用其“正确划分节点数占节点总数比例”方法作为算法结果准确率的评估方法。

图1展示的是使用被普遍认可的基准随机网络RN(4,32,16,zout)在不同Zin时算法的准确率。从图中可以看出,即便在Zin=8这样模糊的社区结构,算法依然能够保持97.4%的准确率。

图2展示的是在不同网络规模时,算法时间消耗,实验中采用了随机网络RN(a,100,16,10) 进行测试, 该网络的社区结构确定, 但其网络社区的个数可由a值调节, 共包含100 a个网络结点, 1000 a条网络连接。图中X轴代表网络边数目,Y轴代表算法时间消耗。从图中可以看出:算法具有近似时间复杂度。

3.2 真实世界网络

1) 例1:海豚网络

海豚网络是Lusseau[15]对居住在新西兰神奇湾的62个宽吻海豚历时七年的观察建立的, 该网络中的每个节点代表一只海豚,边代表海豚间的联系频度, 它共有159条边.Lusseau称在他观察的两年时间内,海豚网络由于处于两群边缘的部分海豚消失分化成两个社区,其中大一点的社区包含了几乎全部的雌性海豚,而剩下的则包含了全部的雄性海豚.其自然划分结果如图3(其中圆形节点代表雌海豚,方形节点代表雄性海豚,以蓝色曲线分隔)。

利用该文所提出的算法对其划分,结果如图4所示:

从图中可以看出,只有两个节点“SN89”和“DN63”划分错误。实验结果相对较准确。

4 结论及展望

本算法思路简洁,不同于Vincent D Blondel等[16]提出了以多步骤计算Q值作为起始和最终划分凭据方法,提出基于拥有最多邻居节点的初始中心方法,创新性地定义了社区合并置信度度量方法,最后以模块性函数均值Q作为优化函数获取最优划分结果。不仅在小规模网络中划分准确,而且由于算法时间复杂度低可以适用于大规模网络数据。

1) 在小规模网络中划分结果准确。如在空手道网络中的社区结构划分完全正确,在海豚网络社区结构划分只误划分了两个节点。

2) 在大规模网络中应用。算法最耗时间步骤仅仅在于起始时按照节点邻居数量排序,且时间复杂度为O(nlogn),其他步骤均为线性时间复杂度,第二步直接大幅度缩减了计算量。这使得算法具有应用在大规模网络中的可行性。

3) 存在的问题。本算法在两个小数据集空手道数据和海豚网络数据集中并没有以取模块性函数Q,而是取其均值作为目标优化函数,得到较为准确地划分结果,与目前大部分论文不同。而在大网络数据集如科学家协作网络中直接以模块性函数Q作为评价函数,此时我们发现网络中社区数量较大时,模块性函数Q≈1,这也即模块性函数Q的分辨率极限问题[17]。

4) 展望。从算法流程可以看出,算法第三步小社区之间存在交集,本算法在处理时需要对交叉节点进行二次划分,这在一定程度上增加了算法的时间消耗,同时也给其创造了另外一种可能,也即划分重叠社区的可能。今后将继续改进算法并根据网络规模确定划分网络社区结构的时使用平均模块性函数Q’与直接模块性函数Q,同时尝试将改进算法使其能够运用在重叠社区发现研究中。

节点覆盖 篇2

目前已有多种协议利用网络的异构性来提高能量效率、增强稳定性和延长网络寿命[3]。根据算法的目的,HWSN聚类算法可分为两大类:增强网络稳定性和提高能量效率。这些算法能够为网络提供更优的能量效率和更长的寿命,然而,实际中需要在网络服务质量和网络寿命中进行权衡。若想获得更好的网络性能,则需要增加每个节点的能量消耗,但这样就会缩短网络的寿命。例如,文献[4]提出一种稳定选举协议(Stable Election Protocol,SEP),提高了网络寿命(网络寿命即直到网络中出现第一个失效节点的时长),然而,当部署区域中存在多个不同覆盖质量需求的目标时,该协议的效果并不是很理想。文献[5]提出一种随机节能分簇算法,使用了睡眠唤醒调度方案,提高了网络的能量效率,解决了多覆盖目标的问题,然而,由于传感器网络寿命有限,部分节点可能会在一个特定区域内失效,从而形成一块无法感应的空白区。为了更好地解决该问题,可从邻近的高密度区域转移一些节点到空白区。因此,文献[6]提出了一种度分布可调的容错拓扑结构(ADD),通过解析度分布属性对拓扑容错性的影响,得出在能量耗尽与环境损毁综合节点失效情况下可较长时间维持监测任务的网络拓扑提高了网络的容错性能。此外,文献[7]提出采用移动性来增加网络的有效覆盖率,移动性可以是移动Sink节点或移动传感器节点,然而,分簇结构中簇头节点能量消耗过快而容易死亡,即很难同时兼顾能量效率和覆盖率,不利于延长网络寿命。文献[8]研究表明,一个具有较多能量的节点相比一个较少能量的节点,其能够更长时间地覆盖一片区域,因此根据需要,可以将该节点移动到没有活动节点的区域,该过程取决于网络地形及节点数目。

为了更好地均衡能量效率和覆盖率,提出了一种基于网格节点移动(Mobile Grid Node,MGN)[9]的HWSN协议,在扩大覆盖率的同时延长网络寿命。协议中能量高的节点相比能量低的节点可处理更多的任务,从而延长网络的寿命。本文协议中的异构性根据节点的能量不同设定两种类型节点:正常节点和高级节点。假定节点是移动的,但限制其只能在垂直或水平方向移动,而Sink节点位于网络的中心且坐标已知。仿真实验表明,相比几种较新的协议,本文协议具有更好的能量恢复性能和更长的寿命,并在整个网络的生命周期中具有良好的覆盖率。

1 提出协议

1.1 网络部署

在地面层部署HWSN节点,将n个节点随机放置在一个二维矩形区域内。节点包括普通节点与高级节点,高级节点的能量比普通节点高。根据文献[4]的SEP协议,来确定普通节点和高级节点的能量值以及它们的比例。若n为节点总数,则高级节点数量为m×n(m是占节点总数n的比例),普通节点的数量为(1-m)×n。假设普通节点的能量为E0,则每个高级节点的能量为E0×(1+α)。该网络与正常网络相比,能量是其(α×m+1)倍。正常节点、高级节点、Sink节点在二维平面上的部署如图1所示。

1.2 虚拟网格的生成

将整个平面按照行与列划分为网格,每个网格的大小由节点的感知半径确定10-11],以节点最远传输距离为网格对角线,将网格对角线记为Rs,则每个网格的面积为。普通节点和高级节点都随机的分布在每个网格中。本文假定所有网格的面积相同,则平面中网格总数为平面总面积除以单个网格的面积。

本文方法中,第一步是确定网格的过载、中立和欠载状态。假设网格rth有Lr个节点,初始部署到各个网格中平均节点数为A。接下来,采用下列条件计算负载:

1)若Lr>A,则rth网格为过载状态;

2)若Lr=A,则rth网格为中立状态;

3)若Lr<A,则rth网格为欠载状态。

得到网格的负载后,就可以找出需要移动传感器节点的网格,处于过载状态的网格中的节点将会被移动。首先依次扫描所有网格,从1st网格开始扫描到最后一个,确定其当前的负载状况。按照网格的顺序,每个欠载网格将从其相邻过载网格中转移节点加入,这样节点将会从高密度区域分布至低密度区域。rth网格可从其上下左右网格中获取节点。一个5×5的虚拟网格的构成如图2所示,并对各个网格编码。图中,若9th网格为欠载状态,则它可以从2th,8th,10th或12th网格中获取节点。

1.3 能量与覆盖率的解决方案

两个节点之间进行通信,其能量消耗可根据文献[4]的SEP协议中的无线能量模型公式计算获得。在一次收发过程中,每个网格中的发送节点会找到Sink节点并向其发送数据[12,13],根据节点的能量值来选择网格中的发送节点。

首先测量各节点的能量,每一轮都会计算网格中各个节点能量,找出能量最高的节点,使其保持唤醒状态并检测网格,其它节点保持睡眠状态。以此来节省能源,延长网络寿命。图3描述了一个网络中的睡眠-唤醒模式的应用。

每一轮中,在检测并传输数据后,都会重新检测网格来确定是否存在活跃的节点。如果网格为空,则说明网格中的所有节点均失效,那么该网格就会搜索邻近网格以获取额外的节点,以此来保持有效的覆盖范围。

2 实验结果与分析

本文提出的MGN协议的主要目的是提高网络覆盖率并延长覆盖时间。使用MATLAB 7.10.0建立仿真环境来评估协议性能。本文假设传感器节点具有自主移动性的特点,移动过程不产生能量消耗。最初,所有的传感器节点均处于活跃状态,在检测节点能量水平和节点之间的距离后,部分节点进入睡眠状态。将Sink节点放置于平面中央,且不能移动。高级节点的能量是普通节点的4倍。仿真参数如表1所示。

首先将网络区域划分为若干子区域,即网格区域,根据图2中的虚拟网格编码并在平面上部署节点。图4描述了网格编码和随机部署节点的结构。可以看出,网络处于不平衡状态,欠载状态的网格有1,3,8,11和19号网格,过载状态的网格有2,7,15和20号网格。

通过扫描各个网格,得知网格中节点的平均数量。网格中的高级节点最先被移动,在高级节点平衡之后,再次扫描节点总数(包括高级节点与普通节点),进一步调整节点,以此使网格中的节点分布大致平衡,如图5所示。

从图5可以看出,在传感器节点移动后,1,3,8和19号网格中已有足够数量的节点。然后,计算节点转发数据包到Sink节点所消耗的能量。在获得各传感器节点的剩余能量之后,根据距离和能量水平进行睡眠-唤醒调度,唤醒高能量节点,睡眠较低能量节点。

2.1 网络寿命

网络寿命是网络从开始到所有节点死亡的时间。设定当一个节点的能量低于阈值时,则该节点失效,设定该阈值为0.3 J。在数据的发送、接收和聚合过程中,都会产生能量消耗[14]。在从开始到网络中最后一个节点失效期间内,计算网络操作的总次数。将本文MGN协议获得的网络寿命与文献[4]提出的SEP异构协议、文献[6]协议、文献[8]协议进行比较。图6描述了网络中存活节点数目与运作周期数的关系,其中m=0.2,α=3。从图6可以看出,相比其他几种协议,本文协议具有更多的工作周期数,文献[4]协议只能工作2 000个周期,而本文协议能工作3 500个周期,高出了75%,表明本文协议的网络寿命明显长于其他几种协议,当m和α的值增大时,性能会更好。

2.2 网络的覆盖率

若一个网格中至少有一个节点能被检测出,则认为该网格被覆盖[15]。以被覆盖网格数目与网格总数的比例作为覆盖率。进行实验,将本文协议的覆盖率与其他几种协议进行比较,并获取覆盖率随周期数的变化情况,实验结果如图7所示。

从图7可以看出,文献[4]协议网络的覆盖率在周期为1 000附近大幅下降,很快就降低到10%,文献[6]协议在1 700附近开始大幅下降,文献[8]协议与本文协议网络覆盖率在周期2 500前逐步下降,直到2 700周期数时才降低到10%以下。相比其他几种异构协议,由于本文协议引入了睡眠-唤醒调度算法,所以具有更好的能量恢复性能、更长的寿命和更高的覆盖率。

2.3 稳定期

稳定期是指网络从开始到一定比例数量(假设为30%)节点失效的时间。稳定期取决于网络的面积以及其中部署的节点数。如图8所示为案例1在40 m×40 m的区域内部署80个节点,在文献[4]协议曲线的拐点处,本文协议约有3个失效节点。如图9所示所示为案例2在50 m×60 m的区域部署150个节点,在文献[4]协议曲线的拐点处,本文协议仅有1个失效节点。从图8和图9可以看出,相比其他几种协议,本文协议节点存活周期总是最长,即网络寿命最长。

本文协议中,若有一个节点失效,会有另一个节点取代它来覆盖该区域,因此,网络覆盖率不会出现大幅下降,从而增长了网络的稳定期,案例1和案例2的覆盖率曲线分别如图10和图11所示。从图10和图11可以看出,相比其他几种协议,本文协议的覆盖率总是最高,本文协议中,若网格为空,则该网格就会搜索邻近网格以获取额外的节点,从而保持有效的覆盖范围。

3 结束语

节点覆盖 篇3

传感器节点通常大规模、高密度地部署在目标区域内,可能导致网络中大量节点的覆盖区域相互交迭,这种覆盖冗余直接导致采集、传输数据的冗余以及信道的干扰,从而造成不必要的能量消耗。因而周期性的关闭冗余节点的通信和感知模块,并将其设置为睡眠状态能有效减少节点能量消耗、延长WSN的生存时间。基于上述原因,近年来很多研究人员致力于WSN的节点调度设计上,并对这一领域展开了大量的工作且取得了一定的进展[1]。

目前已有的以网络覆盖为研究目标的调度算法大都是在网络全局覆盖的前提下设计的,但WSN是面向应用型的网络,不同的应用环境对覆盖具有不同的要求,因而基于全局覆盖的设计不利于构建低成本的传感器网络。文献[1]和文献[2]同时提出了一种基于布尔感知模型的节点随机调度算法[3],该算法不需要知道节点的位置信息、简单、容错性好,并且在网络密度达到一定程度时,可以实现较高的网络覆盖,所以在随机调度算法中,覆盖度与节点数的关系是节点配置的关键问题。Liu等人[4]详细分析了基于布尔感知模型的随机调度算法的网络覆盖度与节点数之间的关系。之后,许多研究人员在分析结果的基础上对随机调度算法进行了进一步的分析改进[5,6,7,8,9]。但是以上关于随机调度算法的研究成果都是基于布尔感知模型设计的,布尔感知模型尽管简单,但不能真实的反映节点的传感能力。文中首次在概率感知模型下分析了随机调度算法中网络覆盖度与节点数之间的关系,仿真结果验证了理论分析的正确性。

1 背景知识

基于以下假设展开讨论:传感器节点随机部署在一个二维区域(Q=a×a)的静态无线传感器网络中;每个节点不知道自己的位置信息,且感知距离与通信距离是固定的。

1.1 传感器网络的感知模型

在对传感器网络覆盖问题的研究中,通常采用布尔和概率两个感知模型来模拟传感器网络对监控区域的感知能力,布尔感知模型为

$p{}_{ij}=\{\begin{array}{l}1d(i,j)\le R\\ 0d(i,j)＞R\end{array}(1)$

概率感知模型为

$p{}_{ij}=\{\begin{array}{cc}e{}^{-\lambda d}& d(i,j)\le R\\ 0& d(i,j)＞R\end{array}(2)$

其改进形式为

$p{}_{ij}=\{\begin{array}{cc}1& d(i,j)\le r\\ e{}^{-\lambda (d(i,j)-r)}& r＜d(i,j)\le R\\ 0& d(i,j)＞R\end{array}(3)$

其中,pij为目标点j被传感结点i监测到的概率;R,r为传感器的监测距离门限值;d(i,j)为传感结点i和目标点j之间的距离;λ表征的是监测概率随距离变化的比例因子,是传感器质量的体现。

分析模型(2),当节点i和目标点j之间的距离d(i,j)小于门限值r时,传感器对目标点的监测概率为1,但当d(i,j)>r时,监测能力随距离的增加而减少,直到d(i,j)>R时,监测概率变为1。该模型与传感器实际的监测情况是吻合的,相对于理想化的布尔感知模型,该模型能够更加合理的反映传感器节点对目标的监测特性。文中采用模型(3)。

1.2 随机调度算法

文献[3]中提出的随机调度算法设计的出发点是将网络中的节点分成多个集合,当节点密度足够大时每个子集单独地就可以覆盖大部分区域,这里简要介绍一下该算法。

步骤1 令传感器节点组成集合S;

步骤2 将节点集S分成k个子集:每个节点先产生一个0～k-1 之间的随机数i,然后加入到第i个子集中,这样将产生k个互不相交的子集;

步骤3 每个子集轮流交替工作。

2 网络覆盖度分析

在给定的覆盖度要求下,为了更加合理地布置节点数、划分子集数,需要知道网络覆盖度与节点数和子集数之间的关系,鉴于此,这里定义了在概率感知模型下网络的覆盖度。

定义1 点的覆盖度:给定点p,定义p点的覆盖度为$C{}_p=\frac{{\rm T}{}_c}{{\rm T}}$,其中T是任意一个给定的时间周期,Tc是在时间段T内,点p至少被一个工作节点覆盖到的总时间。

定义2 网络覆盖度:用Cp的期望来表示网络覆盖度Cn,即,Cn=E[Cp]。

定理1 在概率感知模型下,随机调度算法的网络覆盖度为

$C{}_n=1-\left[1-\frac{\text{π}r{}^2}{a{}^{2}k}-\frac{2\text{π}}{a{}^{2}k\lambda }\left(r+\frac{1}{\lambda }\right)+\frac{2\text{π}}{a{}^{2}k\lambda }\left(R+\frac{1}{\lambda }\right)e{}^{-\lambda (R-r)}\right]{}^n$

证明:如果监测区域内的一个给定点p在某个传感器节点的以R为半径的圆形区域内,在此称p点被该节点覆盖。假设p点被s个节点覆盖,这些节点构成集合S,随机调度算法将S中的每个节点分配到个不相邻的子集Si(i=0,1,…,k-1)中,考虑每个子集监测不到给定点p的概率,不失一般性,先计算子集S0,用Ai来表示s个节点中的节点i监测不到p点,Bi表示节点i属于S0,则${\rm P}(B{}_i)=\frac{1}{k},{\rm P}(A{}_i|\overline{B{}_i})=1$。

P(S0监测不到p点)=P (s个节点都监测不到p点)$={\displaystyle \prod _{i=1}^s{\rm P}}(A{}_i)$(由于节点监测能力的独立性)$={\displaystyle \prod _{i=1}^s(}{\rm P}(B{}_i){\rm P}(A|B{}_i)+{\rm P}(\overline{B}){\rm P}(A{}_i|\overline{B{}_i}))(4)$

$\begin{array}{l}{\rm P}(A{}_i|B{}_i)={\rm P}(d(i,j,p)＞R){\rm P}(A{}_i|d(i,p)＞R)+{\rm P}(r＜d(i,p)\le R){\rm P}(A{}_i|r＜d(i,p)\le R)+{\rm P}(d(i,p)\le r){\rm P}(A{}_i|d(i,p)\le r){\rm P}(A{}_i|d(i,p)\le r)=\frac{R{}^2-r{}^2}{R{}^2}(1-e{}^{-\lambda (d(i,p)-r)})(5)\\ {\rm P}(A{}_i|B{}_i)={\rm P}(d(i,p)＞R){\rm P}(A{}_i|d(i,p)＞R)+{\rm P}(r＜d(i,p)\le R){\rm P}(A{}_i|r＜d(i,p)\le R)+{\rm P}(d(i,p)\le r){\rm P}(A{}_i|d(i,p)\le r)(5)\\ {\rm P}(A{}_i|d(i,p)\le r)=\frac{R{}^2-r{}^2}{R{}^2}(1-e{}^{-\lambda (d(i,p)-r)})(6)\end{array}$

$\begin{array}{l}\text{所}\text{以},{\rm P}{}_r(\mathit{S}{}_0\text{监}\text{测}\text{不}\text{到}{\rm P}\text{点})=\\ {\displaystyle \prod _{i=1}^s\left[\frac{R{}^2-r{}^2}{kR{}^2}(1-e{}^{-\lambda (d(i,p)-r)})+\left(1-\frac{k}{k}\right)\right]}(7)\end{array}$

$\begin{array}{l}\text{则},{\rm P}{}_r(\mathit{S}{}_0\text{监}\text{测}\text{到}p\text{点})=\\ 1-{\displaystyle \prod _{i=1}^s\left[\frac{R{}^2-r{}^2}{kR{}^2}(1-e{}^{-\lambda (d(i,p)-r)})+\left(1-\frac{1}{k}\right)\right]}(8)\end{array}$

由于相似性,该概率对所有子集都是成立的。定义一个随机变量Xj,如果Sj对点p的监测概率为空,Xj=0,否则Xj=1。设X=∑${}_{j=0}^{k-1}$Xj表示可监测给定点的集合Sj的总数(0≤j≤k-1),那么

$\begin{array}{l}E[X]={\displaystyle \sum _{j=0}^{k-1}E}[X{}_j]=k\times [1-{\displaystyle \prod _{i=1}^s[\frac{R{}^2-r{}^2}{kR{}^2}}\\ (1-e{}^{-\lambda (d(i,p)-r)})+\left(1-\frac{1}{k}\right)]](9)\end{array}$

根据Cp的定义,被s个节点覆盖的点p的覆盖度为

$\begin{array}{l}C{}_p=\frac{E[X]\times {\rm T}}{k\times {\rm T}}=1-{\displaystyle \prod _{i=1}^s[\frac{R{}^2-r{}^2}{kR{}^2}(1-e{}^{-\lambda (d(i,p)-r)})+}\\ \left(1-\frac{1}{k}\right)](10)\end{array}$

其中,

${\rm P}{}_r\{s=j\}=\left(\begin{array}{l}n\\ j\end{array}\right)\times q{}^j\times (1-q){}^{n-j}$

,且q是点p在其它节点的监测区域内的概率,$q=\frac{\text{π}R{}^2}{a{}^2}$。则

$\begin{array}{l}C{}_n=E[C{}_p]=E\left[1-{\displaystyle \prod _{i=1}^s\left[\frac{R{}^2-r{}^2}{kR{}^2}(1-e{}^{-\lambda (d(i,p)-r)})+\left(1-\frac{1}{k}\right)\right]}\right]=1-{\displaystyle \sum _{j=0}^{n}E}[{\displaystyle \prod _{i=1}^s[\frac{R{}^2-r{}^2}{kR{}^2}(1-e{}^{-\lambda (d(i,p)-r)})+}\\ \left(1-\frac{1}{k}\right)]|s=j]{\rm P}{}_r(s=j)=1-{\displaystyle \sum _{j=0}^n\left[\frac{R{}^2-r{}^2}{kR{}^2}E(1-e{}^{-\lambda (d(i,p)-r)})+\left(1-\frac{1}{k}\right)\right]}{}^j{\rm P}{}_r(s=j)=1-[1-\frac{\text{π}r{}^2}{a{}^{2}k}-\frac{2\text{π}}{a{}^{2}k\lambda }\\ \left(r+\frac{1}{\lambda }\right)+\frac{2\text{π}}{a{}^{2}k\lambda }\left(R+\frac{1}{\lambda }\right)e{}^{-\lambda (R-r)}]{}^n(11)\end{array}$

推理1 对给定的子集数k,为了保证网络的覆盖度至少达到t,所需节点数n的下界是

$\left[\frac{\ln (1-t)}{\ln \left(1-\frac{\text{π}r{}^2}{a{}^{2}k}-\frac{2\text{π}}{a{}^{2}k\lambda }\left(r+\frac{1}{\lambda }\right)+\frac{2\text{π}}{a{}^{2}k\lambda }\left(R+\frac{1}{\lambda }\right)e{}^{-\lambda (R-r)}\right)}\right]$

证明:根据定理1,若网络的覆盖度至少为t,则$1-\left[1-\frac{\text{π}r{}^2}{a{}^{2}k}-\frac{\text{π}(R+r)}{a{}^2\lambda k}(1-e{}^{-\lambda (R-r)})\right]{}^n\ge t$那么

$n\ge \left[\frac{\ln (1-t)}{\ln \left(1-\frac{\text{π}r{}^2}{a{}^{2}k}-\frac{2\text{π}}{a{}^{2}k\lambda }\left(r+\frac{1}{\lambda }\right)+\frac{2\text{π}}{a{}^{2}k\lambda }\left(R+\frac{1}{\lambda }\right)e{}^{-\lambda (R-r)}\right)}\right](12)$

由推理1易得推理2。

推理2 对给定的网络节点数n,为了保证网络的覆盖密度至少为t,则不相邻的子集数的上界是

$\frac{\frac{\text{π}r{}^2}{a{}^{2}k}+\frac{2\text{π}}{a{}^{2}k\lambda }\left(r+\frac{1}{\lambda }\right)-\frac{2\text{π}}{a{}^{2}k\lambda }\left(R+\frac{1}{\lambda }\right)e{}^{-\lambda (R-r)}}{1-e{}^{\frac{\ln (1-t)}{n}}}(13)$

3 仿真结果比较

定理1与推论1清楚地说明了网络覆盖度、节点数及子集数之间的关系。仿真了在布尔感知模型下和文中所采用的概率感知模型下网络覆盖度与节点数之间的关系(固定k值)。为了便于比较仿真结果,采用与文献[5]中同样的数据。假设a=200,t=0.9,r=10,R=12,k=3,=0.5,文中分析结果计算得n≥690,文献[5]中n≥878,显然在概率感知模型下要实现同样的覆盖度所需的节点数要少得多。图1反映了在两种感知模型、相同的k值下,网络覆盖度与节点数之间的关系。很显然,网络覆盖度随着节点数的增加而增加,当节点数足够大时,网络实现全覆盖。图2反映了在概率感知模型下当k值不同时网络覆盖度与节点数之间的关系。布置同样的节点数,k值越小网络覆盖度越大。在实际应用随机调度算法时,根据在概率感知模型下所得的关系图,可以设置合理的覆盖度、节点数及子集数,从而加强了随机调度算法的实用性。

4 结束语

概率感知模型与布尔感知模型相比,其优势在于更加接近实际、接近应用。文中在概率感知模型下研究了无需知道节点位置信息的随机调度算法的网络覆盖度、节点数及网络子集数之间的关系,解决了随机调度算法中的节点配置问题,增加了随机调度算法的实用性。

摘要：节点随机调度算法,是一种研究网络局部覆盖的重要方法,它无需知道节点位置信息、简单易用并有较高的实用价值。但是目前对该算法的研究成果均是基于布尔感知模型设计。布尔感知模型尽管简单,但不能真实地反映节点的感知能力。文中首次在概率感知模型下,分析了随机调度算法中网络覆盖度与节点数之间的关系,给出了节点数的下界值,并通过仿真验证了分析的正确性。

关键词：无线传感器网络,随机调度,网络覆盖度,节点数

参考文献

[1]金岩,王玲,杨孝宗,等.无线传感器网络节点调度算法及研究进展[J].宇航学报,2007,28(5):1086-1093.

[2]Liu Chong,Wu Kui,King Valerie.Randomized Sched-uling Algorithm for Wireless Sensor Networks[D].Course Project of CSc523(Randomized Algorithms),University of Victoria,2004.

[3]Abrams Z,Goel A,Plotkin S.Set Kcover Algorithms for Energy Efficient Monitoring in Wireless Sensor Net-works[C].Berkeley,CA:Proceedings of Information Processing in Sensor Networks,2004.

[4]Liu Chong,Wu Kui,King Valerie.Randomized Cover-age-preserving Schedu Ling Schemes for Wireless Sensor Networ Ks[C].Berlin,Springer:Proc of IFIP Networ-king Conf,LNCS3462,2005:956-967.

[5]Liu C,Wu K,Xiao Y,et al.Random Coverage With Guaranteed Connectivity:Joint Scheduling for Wireless Sensor Networks[J].IEEE Trans on Parallel and Dis-tributed Systems,2006,17(6):562-575.

[6]刘巍,崔莉,黄长城.EasiFCCT:一种保证连通性的传感器网络局部覆盖算法[J].计算机研究与进展,2008,45(1):196-204.

[7]Xiao Y,Chen H,Wu K,et al.Maximizing Network Life Time Under QoS Constraints in Wireless Sensor Net-works[C].Proceedings of Globecom,2006.

[8]Xiao Y,Chen H,Wu K,et al.Modeling Detection Metrics in Randomized Scheduling Algorithm in Wireless Sensor Networks[C].Submitted to an IEEE Confer-ence,2003.