一種新型的無線傳感器網(wǎng)絡(luò)覆蓋算法*

蔣敏蘭，陸鑫潮

(浙江師范大學(xué)數(shù)理信息工程學(xué)院，浙江金華321004)

無線傳感網(wǎng)絡(luò)(Wireless Sensor Network，簡稱WSN)是由很多具有特定功能的傳感器節(jié)點(diǎn)通過自組織而形成的網(wǎng)絡(luò)系統(tǒng)，廣泛應(yīng)用于國防監(jiān)控，環(huán)境監(jiān)測，智能家居以及醫(yī)療和交通等許多科學(xué)領(lǐng)域。網(wǎng)絡(luò)覆蓋問題是一個NP難問題，已成為無線傳感網(wǎng)絡(luò)研究領(lǐng)域的一個關(guān)鍵問題[1－3]。

近年來，許多研究者在該領(lǐng)域做了大量的研究工作，提出了很多的優(yōu)化算法，比如:文獻(xiàn)[4]在節(jié)點(diǎn)分布滿足正六邊形條件下，提出了基于泊松分布的節(jié)點(diǎn)部署方法以優(yōu)化網(wǎng)絡(luò)覆蓋、連通和節(jié)點(diǎn)布置等問題;文獻(xiàn)[5]在網(wǎng)絡(luò)非完全覆蓋條件下，提出了一種基于概率模型的粒子群算法，優(yōu)化無線傳感網(wǎng)絡(luò)的有效覆蓋率;文獻(xiàn)[6－7]在節(jié)點(diǎn)位置動態(tài)改變條件下，分別提出了基于人工勢場的節(jié)點(diǎn)部署機(jī)制和一種基于禁忌搜索的節(jié)點(diǎn)分布策略，提高了網(wǎng)絡(luò)生命周期和目標(biāo)的監(jiān)測質(zhì)量。上述研究成果并沒有同時考慮節(jié)點(diǎn)分布的隨機(jī)性、靜態(tài)性及完全覆蓋問題。

本文基于傳感器節(jié)點(diǎn)隨機(jī)分布、網(wǎng)絡(luò)完全覆蓋等條件下，利用小波[8－13]局部模極大值理論(即奇異點(diǎn)檢測原理)來處理無線傳感網(wǎng)絡(luò)的完全覆蓋問題。

1 小波變換與模極大值理論

本文中，將網(wǎng)絡(luò)覆蓋問題轉(zhuǎn)化為一個離散信號f(n)，建立離散信號模型:

式中n表示處于工作狀態(tài)時的節(jié)點(diǎn)數(shù)，Cn表示n個節(jié)點(diǎn)處于工作狀態(tài)時的覆蓋率。

基于本論文的研究目標(biāo)，Cn需保證為100%，即為完全覆蓋。則只需求解信號f(n)最大值時的最小節(jié)點(diǎn)數(shù)n即可，并且無需求解信號重構(gòu)等問題，因此采用離散小波變換中的二進(jìn)小波變換來處理此信號。

小波變換的含義:把一稱為基本小波的函數(shù)ψ(t)作位移τ后，再在不同尺度a下與任意L2(R)空間中的函數(shù)f(t)做內(nèi)積:

式中小波母函數(shù)ψ(t)經(jīng)過伸縮和平移后得到函數(shù)ψa，τ(t):

式中，a，τ∈R，且a＞0。由于伸縮因子a和平移因子τ是連續(xù)變化的值，因此稱ψa，τ(t)為連續(xù)小波基函數(shù)。將尺度a和位移τ離散化，得到其離散小波變換。

對于尺度a的離散化，目前通行的方法是對尺度 a 進(jìn)行冪級數(shù)離散化，即令;

而對位移τ的離散化則通常對τ進(jìn)行離散取值，為防止信息的丟失，必須要求采樣間隔τ滿足奈奎斯特采樣定理，采樣率大于等于該尺度下頻率通帶的兩倍。故在尺度 j下，由于的寬度是ψ(t)的倍，因此采樣間隔可以擴(kuò)大，同時也不會引起信息的丟失。因此，ψa，τ(t)可以表示為:

式(4)中，j，k∈Z。如果取離散柵格 a0=2，τ0=1，即連續(xù)小波只在尺度a上進(jìn)行量化，平移參數(shù)τ仍然連續(xù)則稱此小波為二進(jìn)小波，表示為:

則根據(jù)式(2)，可得到信號f(t)的二進(jìn)小波變換為:

離散信號的二進(jìn)小波變換可以通過TROUS算法實(shí)現(xiàn)[14]。h0，h1是 Mallat算法的一對共軛濾波器，對離散信號f(n)進(jìn)行二進(jìn)小波分解:

若第j層的小波系數(shù)W2jf(n)滿足式(9)和式(10)，則W2jf(n)在點(diǎn)t處取得模極大值，記所有的局部模極大值點(diǎn)為，那么，其相應(yīng)極大值為。

故通過二進(jìn)小波變換模極大值理論求解f(n)的最大值，得傳感器節(jié)點(diǎn)在隨機(jī)分布、節(jié)點(diǎn)靜止、實(shí)現(xiàn)完全覆蓋狀態(tài)下的傳感器節(jié)點(diǎn)數(shù)n即為最小值。

2 算法描述

在進(jìn)行Matlab試驗(yàn)仿真前，我們假設(shè)以下三個條件:

(1)無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)為平面結(jié)構(gòu)，且所有節(jié)點(diǎn)是隨機(jī)分布;

(2)網(wǎng)絡(luò)覆蓋要求能達(dá)到完全覆蓋，即覆蓋率為100%;

(3)所有節(jié)點(diǎn)具有相同的感知半徑、通訊半徑及能量，即為同構(gòu)節(jié)點(diǎn)。

本文算法步驟描述如下:

Step 1:在L×L(單位:m)矩形待監(jiān)測區(qū)域內(nèi)，隨機(jī)分布flag·N(flag為記數(shù)標(biāo)志，初始化為1;N表示首次分布節(jié)點(diǎn)數(shù))個節(jié)點(diǎn)，記錄每個節(jié)點(diǎn)的位置Pi;

Step 2:計(jì)算監(jiān)測區(qū)域內(nèi)的覆蓋率CN。其計(jì)算方法是將矩形監(jiān)測區(qū)域網(wǎng)格離散化，如圖1所示。

圖1 區(qū)域離散示意圖

若在監(jiān)測區(qū)域中的小方格長度為l(L為l的整數(shù)倍)，則監(jiān)測區(qū)域被分割成(L/l)2個小方格。由每個小方格的中心點(diǎn)表示其位置，則能夠根據(jù)每個方格到某個節(jié)點(diǎn)的距離是否小于節(jié)點(diǎn)的感知半徑來判斷該網(wǎng)格是否被覆蓋。

假設(shè)記數(shù)標(biāo)志flag2初始值為0，若某網(wǎng)格點(diǎn)Spk(p、k分別為網(wǎng)格點(diǎn)的橫、縱坐標(biāo))到節(jié)點(diǎn)n的距離dpkn小于節(jié)點(diǎn)感知半徑Rs，即:

則flag2=flag2+1。對每一個網(wǎng)格點(diǎn)進(jìn)行判斷，若網(wǎng)格點(diǎn)Spk一旦滿足式(11)，立即停止判斷該網(wǎng)格點(diǎn)是否被其它節(jié)點(diǎn)覆蓋;若始終不滿足式(11)，則判斷下一個網(wǎng)格點(diǎn)。由此可得CN的計(jì)算公式為:

若 CN＜1，則令 flag=flag+1，返回 Step 1;若CN=1，則繼續(xù)下一步Step 3;

Step 4:若 Cn＜1，則令 Cn=0;否則保持不變，并將處于工作狀態(tài)的節(jié)點(diǎn)數(shù)n與對應(yīng)的Cn保存在新的矩陣中;

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

圖2 算法流程圖

3 仿真結(jié)果與分析

將以上算法在雙核2.8 GHz Pentium(R)CPU、512 MB內(nèi)存的計(jì)算機(jī)上使用Matlab 7.0(R14)版本編程實(shí)現(xiàn)。并且令L=100 m，l=0.5 m，節(jié)點(diǎn)的感知半徑Rs=10 m，N=200并進(jìn)行多次運(yùn)行得到的仿真結(jié)果如圖3所示(圖中黑點(diǎn)表示應(yīng)布節(jié)點(diǎn)，圓表示節(jié)點(diǎn)的感知范圍)。

圖3 N為200時的覆蓋情況及最少節(jié)點(diǎn)數(shù)

觀察發(fā)現(xiàn)，圖3(a)和(b)中應(yīng)布節(jié)點(diǎn)數(shù)皆為73個，而圖3(c)和(d)分別為69個和72個。雖然程序每次運(yùn)行后節(jié)點(diǎn)的分布情況不同，得到的最小節(jié)點(diǎn)數(shù)n不完全都相同，但其結(jié)果都很相近。顯然，這是由于節(jié)點(diǎn)分布時帶有一定的隨機(jī)性而造成的，從概率分布的角度符合實(shí)際要求。

為了進(jìn)一步研究參數(shù)N(即首次分布的節(jié)點(diǎn)個數(shù))對最小應(yīng)布節(jié)點(diǎn)數(shù)的影響，我們改變N值的大小，并且各運(yùn)行五次，所得實(shí)驗(yàn)結(jié)果如表1所示。

表1 取不同N值的實(shí)驗(yàn)結(jié)果

從表1中可以看出:當(dāng)N取值不同時，n的變化雖然很小，但是N取值逐漸變大時，n的平均值逐漸變小。即在滿足完全覆蓋的條件下，首次隨機(jī)分布的節(jié)點(diǎn)數(shù)N越大，那么所求的最少節(jié)點(diǎn)數(shù)也就越小。但在表1中，當(dāng)N分別取250和300時，n的平均值卻是相同的。造成這樣的結(jié)果主要有兩大原因:一是節(jié)點(diǎn)分布的隨機(jī)性;二是實(shí)驗(yàn)次數(shù)不夠多。若N的取值過小，則可能會造成flag的值很大，即在Step 1和Step 2之間循環(huán)多次才能成功進(jìn)入Step 3;若N的取值過大，同樣會使程序數(shù)據(jù)量巨大而造成程序運(yùn)行時間很長。

為研究參數(shù)l對本算法運(yùn)行時間t和計(jì)算覆蓋率精度的影響，令 L=100 m，Rs=10 m，N=200，當(dāng) l取不同值時，實(shí)驗(yàn)結(jié)果如表2所示。

表2 取不同l值的算法運(yùn)行時間及覆蓋率精度

由表2可知，當(dāng)網(wǎng)格的長度l越小時，計(jì)算得到的CN也就越精確，但同時計(jì)算量也就越大，程序運(yùn)行時間也就越長。為了在兩者之間獲得平衡，l取0.5 m，此時求得的覆蓋率的精度能達(dá)到千分之一，滿足本實(shí)驗(yàn)的要求。

當(dāng)改變感知半徑Rs的長度時，對傳感器節(jié)點(diǎn)數(shù)最小值n的影響結(jié)果如圖4所示(在L=100 m，l=0.5 m，N=200 條件下)。

由圖4可見，隨著感知半徑Rs的增大，節(jié)點(diǎn)數(shù)n也隨之減小，符合預(yù)期實(shí)驗(yàn)效果。

圖4 在不同Rs值下的覆蓋情況及最小值n

為了將本文算法與文獻(xiàn)[15]中的冗余檢測算法相比較，將L設(shè)為50 m，Rs仍為10 m，在不同的N下多次運(yùn)行結(jié)果如表3所示。

表3 取不同N值時的節(jié)點(diǎn)個數(shù)(L=50 m)

由表3可知，同樣在同構(gòu)節(jié)點(diǎn)感知半徑為10 m、監(jiān)測區(qū)域?yàn)?0 m×50 m，覆蓋率達(dá)到100%的條件下，本文算法所用的節(jié)點(diǎn)數(shù)平均值約為19.2個;而在文獻(xiàn)[15]的圖4中可看出，節(jié)點(diǎn)數(shù)目在60個左右時網(wǎng)絡(luò)覆蓋率接近100%，因此本文算法的得到的最小節(jié)點(diǎn)數(shù)比文獻(xiàn)[15]減少66%以上。由此可見，本文算法具有一定的優(yōu)越性。

4 結(jié)語

從實(shí)驗(yàn)結(jié)果來看，節(jié)點(diǎn)在高密度隨機(jī)分布條件下，本文算法能夠取得良好的穩(wěn)定性。但本文算法未能完全克服節(jié)點(diǎn)分布的隨機(jī)性，而且個別參數(shù)取值較大時，計(jì)算機(jī)處理的數(shù)據(jù)量是相當(dāng)巨大的。

本文的創(chuàng)新之處是將小波模極大值理論與無線傳感網(wǎng)絡(luò)覆蓋問題相結(jié)合，在隨機(jī)分布，節(jié)點(diǎn)靜止及實(shí)現(xiàn)完全覆蓋條件下對傳感器節(jié)點(diǎn)最小值的估算。

[1]李國，趙根森，李明麗.適應(yīng)精度需求變化的無線傳感網(wǎng)絡(luò)覆蓋算法[J].計(jì)算機(jī)應(yīng)用，2010，30(2):15－17.

[2]王燕莉，安世全.無線傳感器網(wǎng)絡(luò)的覆蓋問題研究[J].傳感技術(shù)學(xué)報(bào)，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]趙國炳，陳國定，張奇?zhèn)ィ?一種無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化方法[J].機(jī)電工程，2009，26(6):80－82.

[5]林祝亮，馮遠(yuǎn)靜，俞立.無線傳感網(wǎng)絡(luò)覆蓋的粒子優(yōu)化策略研究[J].傳感技術(shù)學(xué)報(bào)，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]屈巍，李喆.無線傳感器網(wǎng)絡(luò)中一種分布式冗余檢測算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31(4):577－582.