一种新型覆盖连通率计算方法

フ 要:针对在能量受限的无线传感器网络中传感器节点在部署时必须满足一定覆盖率和连通率的问题，提出一个基于正方形区域的新型覆盖率、连通率计算方法，该方法能够描述网络覆盖率、连通率、部署节点的数量、节点感应(通信半径)和网络区域大小之间的关系，计算出在满足一定覆盖率、连通率所需要部署的节点的数量。模拟实验结果表明该理论值和模拟结果之间的误差较小。

ス丶词:无线传感器网络;覆盖;连通;随机部署;随机图

ブ型挤掷嗪: TP393 文献标志码:A

Abstract: Deploying sensor nodes’ has to meet certain coverage and connectivity in the energy constrained wireless sensor networks. Concerning this, a new square regionbased coverage and connectivity probability computational method was proposed in this paper. The new method can not only depict the relations among coverage rate, connectivity rate, the number of nodes, the sensing (communication) range of nodes and the size of network, but also calculate the number of sensor nodes scattered for maintaining certain coverage rate and connectivity rate. The simulation results show that the errorrate of deployment is less than the value obtained from the theoretical analysis.

Key words: Wireless Sensor Network (WSN); coverage;connectivity; random deployment; random graph

0 引言

随着微型传感器技术、无线通信技术以及嵌入式计算技术的发展，无线传感器网络(Wireless Sensor Network, WSN)已得到越来越广泛的关注，在军事、医疗卫生、环境监测和智能家庭等方面具有广泛的应用前景［1-2］。

传感器网络节点能量有限，为了保证一定的网络覆盖率和连通率，就必须研究部署网络节点的数量，以便尽量延长网络的生命周期。节点的部署分为确定性部署［3-4］和随机部署两种［5］。确定性部署主要研究在二维平面和三维空间上的最优化的节点部署策略，随机部署主要用于不适合人工完成的情况。对于传感器网络，大部分情况下并不需要一直保持完全覆盖状态，只要节点对监测区域能够维持一个合理的覆盖率，就能满足大多数应用要求。

1 相关工作

近几年，在无线传感器网络的连通、覆盖方面，国内、外学者已进行了深入的研究，也取得了一些研究成果。文献［6］基于遗传算法提出了一种混合的具有最大节点数的覆盖划分方法，使得每一种覆盖都能监测所有的目标，网络的生命周期能延长0.54%左右；文献［7］利用自动学习机设计了一种跟踪节点的调度方案，提出了一种能进行动态点覆盖的规划算法，以实现对移动目标点的监测、跟踪，该算法的能耗优于已存在的一些算法。

文献［8］以随机部署的大规模无线传感器网络的区域监测的应用为出发点，提出了一个Most Constrained Minimally Constraining Heuristic算法。他们将覆盖区域划分成块，每一块都被一个节点集合中的节点覆盖,该算法解决了满足一定条件的互不相交的节点集的最大数量以及节点集。

在现实的监测环境中，节点的感知半径会受到自身条件及周围环境的影响，呈现正态分布。文献［9］提出一种无需节点地理位置等信息的网络覆盖方法，能调用最少数量的节点实现一定的网络覆盖。上述方法从多个方面对WSN的节能效果进行研究，但大多没有考虑监测边界的影响。本文采用更为实际的正方形网络区域，在考虑节点边界影响的情况下，提出了一种节点覆盖率及连通率的计算方法，该方法能描述节点感知半径、监测区域边长以及节点数量与覆盖率、网络连通率之间的关系，计算所需要的节点数量。

2 网络模型与问题定义

2.1 网络模型

假设无线传感器网络具有以下性质：

1)网络中传感器节点是同构的，即所有的节点的感应范围相同，所有节点的通信范围也相同；

2)所有传感器节点通信模型和感应模型都是圆盘模型，即通信范围和感应范围都是呈圆盘状；

3)传感器节点随机均匀地部署在边长为l的正方形监测区域Ω内，考虑部署区域的边界因素。オ

2.2 参数与变量说明

П疚牧l表示正方形网络区域的边长；Ω表示监测区域面积，即Ω＝l2；n表示部署节点的数量；rs表示节点的感应半径(rs

2.3 相关定义

定义1 如果某个区域内任一点至少被一个节点覆盖，就称这个区域是覆盖的。

定义2 如果图G里的任一节点对都存在一条路径相通，称这个网络是连通的，否则就是不连通的。オ

定义3 无线传感器网络以无向通信图G=(V,E)作为模型，V是传感器节点集合，且|V|=n；当且仅当节点p和q在相互的通信范围内，则称在E内存在一个无向边(p, q)；节点p的邻居数量称为节点p的度，记为d(p)；通信图G的最小节点度表示为d┆min(G)=┆min p∈V{d(p)}。 オ

2.4 问题定义

Ъ偕柙诩嗖馇域Ω内随机均匀部署若干个节点，需要解决的问题就是在不依赖于节点位置信息的前提下实现传感器网络不同的覆盖率和连通率，并计算出实现上述覆盖率和连通率所需要的节点的最少数量。オ

3 网络参数计算

3.1 网络覆盖性能

Ъ偕柙诩嗖馇域内有若干节点v，节点构成的集合为S，每个节点的覆盖面积为E(C)，节点的覆盖概率为E(C)/Ω，S不为空时，节点的覆盖概率：オ

P(Sn)＝1-(1-E(C)Ω)n(1)

下面求解在考虑边界影响情况下节点覆盖面积期望值。

首先将整个监测区域按图1所示划分成两个区域Ⅰ和Ⅱ，可得到网络节点覆盖的期望值：

E(C)=P(ΩⅠ)E[C│釜Ⅰ]+P(ΩⅡ)E[C│釜Ⅱ](2)

其中：P(ΩⅠ)和P(ΩⅡ)分别表示节点被随机部署在区域Ⅰ和区域Ⅱ里的概率值，E[C│釜Ⅰ]和E[C│釜Ⅱ]Х直鸨硎酒湎嘤Φ母哺瞧谕值。

传感器节点的部署服从均匀分布函数，得到：

P(ΩⅠ)=[(l-2rs)2]/l2

P(ΩⅡ)=[4rs(l-rs)]/l2(3)オ

当节点位于区域Ⅰ时，它的覆盖范围被完全包含，得到如下的覆盖期望值：

E[C│釜Ⅰ]=πr2s(4)

Ъ偕A和B是节点p的感应圆周和网络边界的交叉点。θ是节点p和A、B两点所形成的圆心角，于是可以得到C│釜ⅡУ拇笮∥：

C│釜Ⅱ=12r2s(2π-θ+sin θ)(5)

通过式(5)得到C│釜Ⅱ的期望值：オ

E[C│釜Ⅱ]=rs2(l-rs)∫l- rs0 (2π-θ+sin θ)dx ∫ rs0 dy (6)

其中Е=2 arccos (y/rs)。オ

定理1 假定感应半径为rs的均匀分布在边长为l的正方形区域，在考虑边界因素的情况下，节点的覆盖期望值E(C)为：オ

rsl2π(l-2rs)2+2(l-rs)(2πrs+π2+rs)(7)

证明 由式(2)~(4)和(6)可得到。

定理2 Ъ偕杓嗖馇域为正方形，边长为l，节点感应半径是rs，ε为一个任意小的数值，为了确保网络覆盖率的期望值不小于ε，需部署节点数至少为ln(1-ε)ln (1-（E［C］/Ω))。オ

证明 由式(1)知P(Sn)=1-(1-（E［C］/Ω))n≥ε，в谑仟n ln(1-（E［C］/Ω))≤ln (1-ε)。в钟捎讵Иln (1-（E［C］/Ω))

3.2 网络连通性能

П窘诟定n个传感器节点，在考虑网络边界因素的情况下，考查网络连通概率。オ

в啥ㄒ2，有d┆min(G)>0是通信图G连通的必要条件，而不是充分条件；即“G是连通的”可推导出d┆min(G)>0，反过来则是不成立的。这样，P(Cn)≤P(d┆min(G)>0)，在实际中不知道节点密度的情况下，P(Cn)的下限具有更大的意义。下面介绍它的下限的求解。オ

现在，采用文献［10］提出的一个几何随机图性质，作者证明了随着节点数量n的增加，网络的连通概率也增加。可以这样考虑，假定网络通信图是从仅存在孤立节点的空图开始，增加节点通信半径rt，节点相应的通信链路数量也增加；当节点取得最小节点度k时，这个图也成为一个k连通图。在这里，假如在一个图中，移走任意k-1个节点之后，而这个图仍是连通的，称其为k连通图。因此，对于k=1来说，只要它的通信半径rt足够大，使得d┆min(G)>0，这个网络就成为一个连通的网络，即：オ

P(Cn)=P(d┆min(G)>0)(8)

P(d┆min(G)>0)几乎取值为1。实际上，当维数大于1时，作者证明了它的评价指标lp的正确性，但该指标在一维条件下是不成立的。オ

由于节点的分布是独立的，根据前面所得到的网络覆盖概率式(1)，Ф杂谌我饨诘p(p∈G)，可以得到节点连通率的极限值：┆limn∞1-(1-SpΩ)n=1-exp(-nSpΩ)，G的最小节点度值为：オ

P(d┆min(G)>0)=∏p∈G(1-exp(-nSpΩ))(9)

其中Sp表示节点p的有效通信面积。不考虑边界因素时，P(Cn)=P(d┆min(G)>0)=(1-exp(-nπr2t/l2))n。オ

实际上，如图2所示，当节点p位于区域Ⅰ时，Sp的值等于节点p的通信圆面积；当节点p位于区域Ⅱ时，Sp的值等于其通信圆周面积πr2t减去弓形ACBD的面积。这样，式(9)可如下表示：オ

P(d┆min(G)>0)=(1-exp(-nπr2t/l2))4nrt(l-rt)/l2×

∏p∈ΩⅡ(1-exp(-nSpΩ))(10)

Ф杂谑(10)，当节点p位于区域Ⅱ时，可知Sp >Sq，这里节点q位于正方形部署区域的边界上。这样，Sq=12πr2t，可以得到如下的公式：お

А仟p∈ΩⅡ(1-exp(-nSpΩ))>∏p∈ΩⅡ(1-exp(-nSqΩ))＝

(1-exp(-12nπr2t/l2))4nrt(l-rt)/l2(11)

定理3 Ц定一个边长为l的正方形区域，节点数量值为n，节点的通信半径是rt，在考虑边界因素的情况下，网络的连通概率的下限如下：オ

P(Cn) > ［(1-exp(-nπr2t/l2))×

(1-exp(-12nπr2t/l2))］┆4nrt(l-rt)/l2(12)オ

证明 从式(8)~(11)推导可得到。

4 性能评价

为了评估模型性能，用VC语言设计了一个仿真程序。传感器节点使用第2章所描述的感知模型和无线通信模型。通过改变l值的大小来模拟大小不同的网络规模，Т佣评估模型在不同网络规模下的覆盖、连通性能。主要是检测在网络不同覆盖率和连通率的情况下所需要部署节点的数量。每一个仿真结果均为100次仿真实验的平均值。

4.1 网络覆盖率连通率比较

图3显示了在不同网络规模下实现不同节点覆盖率所需要部署传感器节点数量，从图中可以看到，随着网络规模的扩大，实现一定的网络覆盖率需要部署节点的数量需要增加，并且网络的覆盖率越高，需要部署节点的数量增加得越快。

图4显示了在不同网络规模下实现不同网络连通率下需要部署传感器节点数量，可以看到，随着网络规模的扩大，实现一定的网络连通率，需要部署节点的数量有所增加，当覆盖率较高时，需要部署节点的数量增加较快。

4.2 边界效应影响比较

图5表示的是在考虑边界影响/不考虑边界影响两种情况下，实现不同的连通率需要部署节点的数量。从图中可以看出，相比较考虑边界影响情况，不考虑边界影响时，需要部署的节点数量稍微有所增加；并且可以看到，当节点密度较大时，边界效应的影响也随之降低。

5 结语

本文主要研究在保证一定的覆盖率、连通率的情况下如何部署无线传感器网络中的节点问题。在综合考虑边界影响的情况下，提出了一种新型的网络覆盖率和连通率计算方法。该方法能简化网络的计算复杂度，在网络规模不太大的情况下，能保证一定网络覆盖率和连通率，并且结果更加精确。最后，通过模拟实验结果验证了理论求解的正确性。

げ慰嘉南:

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y. Wireless sensor networks: a survey［J］.Computer Networks, 2002, 38(4): 393-422.

[2] GHOSHA A, DAS S K.Coverage and connectivity issues in wireless sensor networks: a survey［J］. Pervasive and Mobile Computing, 2008, 4(3):303-334.

[3] ZHANG H, HOU J. Maintaining sensing coverage and connectivity in large sensor networks［J］.International Journal of Wireless Ad Hoc and Sensor Networks, 2005, 1(1/2):89-124.

[4] BAI X L, YUN Z, XUAN D, et al. Deploying fourconnectivity and fullcoverage wireless sensor networks［C］// Proceeding of IEEE INFOCOM08. New York:IEEE,2008: 906-914.

[5] JIN Y, JO J Y,WANG L. ECCRA: An energyefficient coverage and connectivity preserving routing algorithm under border effects in wireless sensor networks［J］. Computer Communication, 2008, 31(10):2398-2407.

[6] CHEN C P, CHUANG C L, LIN T S, et al. A coverageguaranteed algorithm to improve network lifetime of wireless sensor networks［C］// 24th Eurosensors Conference. Linz: Elsevier, 2010,5:192-195.

[7] ESNAASHARI M, MEYBODI M R. A learning automata based scheduling solution to the dynamic point coverage problem in wireless sensor networks［J］.Computer Networks,2010,54(14): 2410-2438.

[8] SLIJEPCEVIC S, POTKONJAK M. Power efficient organization of wireless sensor networks［C］// Proceeding of IEEE International Conference on Communications. New York:IEEE,2001,2:472-476.

[9] 王换招,孟凡治,李增智.高效节能的无线传感器网络覆盖保持协议［J］.软件学报,2010,21(12):3124-3137.

[10] PENROSE M. On kconnectivity for a geometric random graph［J］. Wiley Random Structure and Algorithms, 1999, 15(2): 145-164.