一种新型的无线传感器网络覆盖算法*

蒋敏兰，陆鑫潮

(浙江师范大学数理信息工程学院，浙江金华321004)

无线传感网络(Wireless Sensor Network，简称WSN)是由很多具有特定功能的传感器节点通过自组织而形成的网络系统，广泛应用于国防监控，环境监测，智能家居以及医疗和交通等许多科学领域。网络覆盖问题是一个NP难问题，已成为无线传感网络研究领域的一个关键问题[1－3]。

近年来，许多研究者在该领域做了大量的研究工作，提出了很多的优化算法，比如:文献[4]在节点分布满足正六边形条件下，提出了基于泊松分布的节点部署方法以优化网络覆盖、连通和节点布置等问题;文献[5]在网络非完全覆盖条件下，提出了一种基于概率模型的粒子群算法，优化无线传感网络的有效覆盖率;文献[6－7]在节点位置动态改变条件下，分别提出了基于人工势场的节点部署机制和一种基于禁忌搜索的节点分布策略，提高了网络生命周期和目标的监测质量。上述研究成果并没有同时考虑节点分布的随机性、静态性及完全覆盖问题。

本文基于传感器节点随机分布、网络完全覆盖等条件下，利用小波[8－13]局部模极大值理论(即奇异点检测原理)来处理无线传感网络的完全覆盖问题。

1 小波变换与模极大值理论

本文中，将网络覆盖问题转化为一个离散信号f(n)，建立离散信号模型:

式中n表示处于工作状态时的节点数，Cn表示n个节点处于工作状态时的覆盖率。

基于本论文的研究目标，Cn需保证为100%，即为完全覆盖。则只需求解信号f(n)最大值时的最小节点数n即可，并且无需求解信号重构等问题，因此采用离散小波变换中的二进小波变换来处理此信号。

小波变换的含义:把一称为基本小波的函数ψ(t)作位移τ后，再在不同尺度a下与任意L2(R)空间中的函数f(t)做内积:

式中小波母函数ψ(t)经过伸缩和平移后得到函数ψa，τ(t):

式中，a，τ∈R，且a＞0。由于伸缩因子a和平移因子τ是连续变化的值，因此称ψa，τ(t)为连续小波基函数。将尺度a和位移τ离散化，得到其离散小波变换。

对于尺度a的离散化，目前通行的方法是对尺度 a 进行幂级数离散化，即令;

而对位移τ的离散化则通常对τ进行离散取值，为防止信息的丢失，必须要求采样间隔τ满足奈奎斯特采样定理，采样率大于等于该尺度下频率通带的两倍。故在尺度 j下，由于的宽度是ψ(t)的倍，因此采样间隔可以扩大，同时也不会引起信息的丢失。因此，ψa，τ(t)可以表示为:

式(4)中，j，k∈Z。如果取离散栅格 a0=2，τ0=1，即连续小波只在尺度a上进行量化，平移参数τ仍然连续则称此小波为二进小波，表示为:

则根据式(2)，可得到信号f(t)的二进小波变换为:

离散信号的二进小波变换可以通过TROUS算法实现[14]。h0，h1是 Mallat算法的一对共轭滤波器，对离散信号f(n)进行二进小波分解:

若第j层的小波系数W2jf(n)满足式(9)和式(10)，则W2jf(n)在点t处取得模极大值，记所有的局部模极大值点为，那么，其相应极大值为。

故通过二进小波变换模极大值理论求解f(n)的最大值，得传感器节点在随机分布、节点静止、实现完全覆盖状态下的传感器节点数n即为最小值。

2 算法描述

在进行Matlab试验仿真前，我们假设以下三个条件:

(1)无线传感器网络的体系结构为平面结构，且所有节点是随机分布;

(2)网络覆盖要求能达到完全覆盖，即覆盖率为100%;

(3)所有节点具有相同的感知半径、通讯半径及能量，即为同构节点。

本文算法步骤描述如下:

Step 1:在L×L(单位:m)矩形待监测区域内，随机分布flag·N(flag为记数标志，初始化为1;N表示首次分布节点数)个节点，记录每个节点的位置Pi;

Step 2:计算监测区域内的覆盖率CN。其计算方法是将矩形监测区域网格离散化，如图1所示。

图1 区域离散示意图

若在监测区域中的小方格长度为l(L为l的整数倍)，则监测区域被分割成(L/l)2个小方格。由每个小方格的中心点表示其位置，则能够根据每个方格到某个节点的距离是否小于节点的感知半径来判断该网格是否被覆盖。

假设记数标志flag2初始值为0，若某网格点Spk(p、k分别为网格点的横、纵坐标)到节点n的距离dpkn小于节点感知半径Rs，即:

则flag2=flag2+1。对每一个网格点进行判断，若网格点Spk一旦满足式(11)，立即停止判断该网格点是否被其它节点覆盖;若始终不满足式(11)，则判断下一个网格点。由此可得CN的计算公式为:

若 CN＜1，则令 flag=flag+1，返回 Step 1;若CN=1，则继续下一步Step 3;

Step 4:若 Cn＜1，则令 Cn=0;否则保持不变，并将处于工作状态的节点数n与对应的Cn保存在新的矩阵中;

以上算法步骤可用流程图表示，如图2所示。

图2 算法流程图

3 仿真结果与分析

将以上算法在双核2.8 GHz Pentium(R)CPU、512 MB内存的计算机上使用Matlab 7.0(R14)版本编程实现。并且令L=100 m，l=0.5 m，节点的感知半径Rs=10 m，N=200并进行多次运行得到的仿真结果如图3所示(图中黑点表示应布节点，圆表示节点的感知范围)。

图3 N为200时的覆盖情况及最少节点数

观察发现，图3(a)和(b)中应布节点数皆为73个，而图3(c)和(d)分别为69个和72个。虽然程序每次运行后节点的分布情况不同，得到的最小节点数n不完全都相同，但其结果都很相近。显然，这是由于节点分布时带有一定的随机性而造成的，从概率分布的角度符合实际要求。

为了进一步研究参数N(即首次分布的节点个数)对最小应布节点数的影响，我们改变N值的大小，并且各运行五次，所得实验结果如表1所示。

表1 取不同N值的实验结果

从表1中可以看出:当N取值不同时，n的变化虽然很小，但是N取值逐渐变大时，n的平均值逐渐变小。即在满足完全覆盖的条件下，首次随机分布的节点数N越大，那么所求的最少节点数也就越小。但在表1中，当N分别取250和300时，n的平均值却是相同的。造成这样的结果主要有两大原因:一是节点分布的随机性;二是实验次数不够多。若N的取值过小，则可能会造成flag的值很大，即在Step 1和Step 2之间循环多次才能成功进入Step 3;若N的取值过大，同样会使程序数据量巨大而造成程序运行时间很长。

为研究参数l对本算法运行时间t和计算覆盖率精度的影响，令 L=100 m，Rs=10 m，N=200，当 l取不同值时，实验结果如表2所示。

表2 取不同l值的算法运行时间及覆盖率精度

由表2可知，当网格的长度l越小时，计算得到的CN也就越精确，但同时计算量也就越大，程序运行时间也就越长。为了在两者之间获得平衡，l取0.5 m，此时求得的覆盖率的精度能达到千分之一，满足本实验的要求。

当改变感知半径Rs的长度时，对传感器节点数最小值n的影响结果如图4所示(在L=100 m，l=0.5 m，N=200 条件下)。

由图4可见，随着感知半径Rs的增大，节点数n也随之减小，符合预期实验效果。

图4 在不同Rs值下的覆盖情况及最小值n

为了将本文算法与文献[15]中的冗余检测算法相比较，将L设为50 m，Rs仍为10 m，在不同的N下多次运行结果如表3所示。

表3 取不同N值时的节点个数(L=50 m)

由表3可知，同样在同构节点感知半径为10 m、监测区域为50 m×50 m，覆盖率达到100%的条件下，本文算法所用的节点数平均值约为19.2个;而在文献[15]的图4中可看出，节点数目在60个左右时网络覆盖率接近100%，因此本文算法的得到的最小节点数比文献[15]减少66%以上。由此可见，本文算法具有一定的优越性。

4 结语

从实验结果来看，节点在高密度随机分布条件下，本文算法能够取得良好的稳定性。但本文算法未能完全克服节点分布的随机性，而且个别参数取值较大时，计算机处理的数据量是相当巨大的。

本文的创新之处是将小波模极大值理论与无线传感网络覆盖问题相结合，在随机分布，节点静止及实现完全覆盖条件下对传感器节点最小值的估算。

[1]李国，赵根森，李明丽.适应精度需求变化的无线传感网络覆盖算法[J].计算机应用，2010，30(2):15－17.

[2]王燕莉，安世全.无线传感器网络的覆盖问题研究[J].传感技术学报，2005，18(2):307－312.

[3]Yun-Ren Tsai.Sensing Coverage for Randomly Distributed Wireless Sensor Network in Shadowed Environments[J].IEEE Transaction on Vehicular Technology，2008，57(1):556－564.

[4]赵国炳，陈国定，张奇伟，等.一种无线传感器网络覆盖优化方法[J].机电工程，2009，26(6):80－82.

[5]林祝亮，冯远静，俞立.无线传感网络覆盖的粒子优化策略研究[J].传感技术学报，2009，22(6):873－877.

[6]Aitsaadi N，Achir N，Boussetta K，et al.Potential Field Approach to Ensure Connectivity and Differentiated Detection in WSN Deployment[C]//IEEE International Conference on Communications，June 14－18，2009:1－6.

[7]Aitsaadi N，Achir N，Boussetta K，et al.A Tabu Search WSN Deployment Method for Monitoring Geographically Irregular Distributed Events[J].Sensors，2009，9(3):1635－1643.

[8]Zhu Kunpeng，Hong Geok Soon，Wong Yoke San.Multiscale Singularity Analysis of Cutting Forces for Micromilling Tool-Wear Monitoring[J].IEEE Transactions on Industrial Electronics，2011，58(6):2512－2521.

[9]Mallat S，Hwang W L.Singularity Detection and Processing with Wavelets[J].IEEE Transactions on Information Theory，1992，38(2):617－643.

[10]Hulzink J，Konijnenburg M，Ashouei M，et al.An Ultra Low Energy Biomedical Signal Processing System Operating at Near-Threshold[J].IEEE Transactions on Biomedical Circuits and System，2011，5(6):546－554.

[11]Nasri M，Helali A，Sghaier H，et al.Energy-Efficient Wavelet Image Compression in Wireless Sensor Network[C]//2010 International Conference on Communication in Wireless Environmentand Ubiquitous System:New Challenges(ICWUS)，Oct 8－10，2010:1－7.

[12]Li Guo-Hua，Zhu Chen-Ming，Li Xin.Application of Chaos Theory and Wavelet to Modeling the Traffic of Wireless Sensor Networks[C]//2010 International Conference on Biomedical Engineering and Computer Science，April 23－25，2010:1－4.

[13]Bai Wen-Le，Yang Wei，Wei Ke，et al.The Traffic Reconstruction of Wireless Sensor Based on Wavelet Denoising[C]//2011 International Conference on Computer Science and Service System(CSSS)，June 27－29，2011:4116－4118.

[14]Shensa M J.The Discrete Wavelet Transform:Wedding the a Trous and MallatAlgorithms[J].IEEE Transactions on Signal Processing，1992，40(10):2464－2482.

[15]屈巍，李喆.无线传感器网络中一种分布式冗余检测算法[J].小型微型计算机系统，2010，31(4):577－582.