一種新型的無線傳感器網絡覆蓋算法*

蔣敏蘭，陸鑫潮

(浙江師范大學數理信息工程學院，浙江金華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.