一種具有覆蓋優(yōu)先級的異構WSN覆蓋空洞修復方法

趙逢達,默云鳳,孔令富,景 榮

(燕山大學 信息科學與工程學院,河北 秦皇島 066004 河北省計算機虛擬技術與系統集成重點實驗室,河北 秦皇島 066004)

1 引 言

無線傳感器網絡(Wireless Sensor Network,WSN)是由大量傳感器節(jié)點以自組織多跳的方式組成的無線網絡[1].覆蓋率作為WSN 服務質量的重要度量指標,反映了WSN所能提供的“感知”服務,其能夠使WSN 的空間資源得到優(yōu)化分配,更好地完成環(huán)境感知、信息獲取和有效傳輸的任務,所以提高覆蓋率對WSN 覆蓋空洞的修復有著重要意義.

大量中外文獻對WSN覆蓋空洞的修復問題進行了研究,但是還沒有統一的分類標準.在靜態(tài)WSN中,主要采用調節(jié)傳感器節(jié)點的屬性[2,3]和添加傳感器節(jié)點[4]的方式進行覆蓋空洞的修復;在動態(tài)WSN中通過節(jié)點的移動來完成覆蓋空洞的修復.研究方法主要分為網絡覆蓋空洞修復策略、基于虛擬力以及圖論的算法等[5].韓蕊、閏雒恒、Lei Zuo、Jalal Habibi等人[6-9]分別提出基于現有理論的網絡覆蓋空洞修復方法;文獻[10]提出基于虛擬力的覆蓋空洞修復方法.文獻[11,12]是基于圖論的覆蓋空洞修復算法,通過最值化圖形面積或者兩點距離的方式完成覆蓋空洞的修復.上面提到的覆蓋空洞修復方法假設網絡中不同位置被覆蓋的重要性是相同的,但是在真實環(huán)境中有些位置需要被優(yōu)先覆蓋(如涉及安全問題或重大機密問題).文獻[13-15]在覆蓋空洞修復方法中考慮到了覆蓋優(yōu)先級.孫澤宇[13]利用貪婪算法和節(jié)點調度機制完成具有不同覆蓋優(yōu)先級的監(jiān)測區(qū)域內有效覆蓋問題,但未考慮傳感器節(jié)點異構的情況.景榮等[14]提出通過剔除冗余候選中繼節(jié)點產生最優(yōu)部署位置的方法來完成覆蓋空洞的修復,但該算法只適用于傳感器節(jié)點部署均勻的網絡.在傳感器節(jié)點隨機部署的情況下,H.Mahboubi等人[15]提出了適用于具有不同覆蓋優(yōu)先級的異構無線傳感器網絡的最大加權頂點(MWP)方法來獲得最大網絡覆蓋率.但是當覆蓋優(yōu)先級高的點主要集中在某個區(qū)域內時,按照該方法將傳感器節(jié)點移動到具有最大加權值的頂點的位置,此時傳感器節(jié)點的加權覆蓋面積可能不是最大的,可見該方法的適用性受限制.又由于該方法中的局部加權覆蓋面積采用中心點權重之和與面積的乘積,在提高算法簡潔性的同時降低了所得到覆蓋面積的精確度.因此該方法對傳感器節(jié)點覆蓋面積的精確獲取以及適用性都有待提高.

為了解決上述問題,本文提出了一種具有覆蓋優(yōu)先級的異構WSN覆蓋空洞修復方法,即最佳傳感器節(jié)點配置的方法(Optimal Sensor Configuration,OSC).為了更好地把握本文結構以及更好地理解此覆蓋空洞修復方法(OSC),將覆蓋空洞修復方法流程圖展示如圖1所示.

該方法首先對異構網絡進行區(qū)域劃分,然后根據傳感器節(jié)點的局部加權覆蓋面積計算傳感器節(jié)點的候選位置,最后根據本文所提策略不斷調整傳感器節(jié)點的位置,使傳感器節(jié)點移動到最佳部署位置從而完成覆蓋空洞修復的任務.與該類問題的其它方法相比,本文貢獻主要包括以下幾點:

1.將具有覆蓋優(yōu)先級的異構WSN中覆蓋空洞修復問題模型化,采用MW-Voronoi圖理論對監(jiān)測區(qū)域劃分,并利用不定積分的方法準確獲取傳感器節(jié)點局部加權覆蓋面積.

2.提出the center multiplicatively weighted voronoi(簡稱CMWV)算法,它能使傳感器節(jié)點不斷調整自身位置到達最佳部署位置,從而使具有不同覆蓋優(yōu)先級的異構WSN的整體加權覆蓋面積最大,完成網絡覆蓋空洞修復任務.

3.與MWP方法進行對比,驗證OSC方法的高效性.

2 覆蓋空洞修復數學模型

2.1 前提假設

假設1.網絡中傳感器節(jié)點具有精確的自定位功能.

假設2.傳感器節(jié)點的感知范圍和通信范圍都是以節(jié)點所在位置為圓心,以定長為半徑的圓形區(qū)域,且傳感器節(jié)點的通信半徑等于感知半徑的兩倍,感知范圍和通信范圍不隨時間的變化而變化.

假設3.傳感器節(jié)點之間的通信內容包括其自身的感知半徑和位置信息.

假設4.傳感器節(jié)點之間實施同步協議,保證所有傳感器節(jié)點同時開始第一個階段.同時為了使修復方法更好地發(fā)揮作用,規(guī)定覆蓋周期足夠長.

2.2 覆蓋空洞修復理論描述

本文采用使傳感器節(jié)點向合適的方向移動來進行覆蓋空洞修復.在真實世界的許多應用中,傳感器節(jié)點修復覆蓋空洞的最佳部署位置事先是不知道的,但傳感器節(jié)點的可移動性允許對自身位置進行調整,通過合理部署傳感器節(jié)點完成修復覆蓋空洞的任務.

在空洞修復過程中,由于傳感器節(jié)點感知半徑不完全相同且不同位置點被覆蓋的優(yōu)先級不同,所以本文中覆蓋空洞修復的本質是增大網絡的總加權覆蓋面積,使得空洞范圍不斷減小到消失.由假設可知,網絡中每個傳感器節(jié)點都能獲取其自身及相鄰傳感器節(jié)點的感知半徑和位置信息.根據這些信息采用MW-Voronoi 圖理論方法對網絡進行分塊研究,劃分后每個子區(qū)域中有且僅有一個傳感器節(jié)點.在本文提出的覆蓋空洞修復方法下,每個傳感器節(jié)點向合適的方向不斷移動,使得每個傳感器節(jié)點局部加權覆蓋面積不斷增大,從而增大網絡的總加權覆蓋面積.

2.3 覆蓋空洞修復模型化

本節(jié)首先對覆蓋空洞修復過程中用到的相關概念進行解釋說明,然后將具有覆蓋優(yōu)先級的異構WSN中覆蓋空洞修復問題進行模型化.為了完成覆蓋空洞修復的任務,將網絡中某個空洞范圍視作監(jiān)測區(qū)域,進行覆蓋空洞修復研究.

2.3.1 相關定義

乘法加權泰森多邊形可用于定性分析、統計分析、鄰近分析等,在分析和設計覆蓋空洞的修復過程中此圖非常有用,介紹如下.

假設二維平面R2中存在n個具有不同加權值的節(jié)點,即(S1,ω1),(S2,ω2),…,(Sn,ωn),這些點的集合用S表示,其中對?i∈n,Si的加權因子ωi>0.

定義1.節(jié)點(Si,ωi)到位置點q的加權距離定義如下:

(1)

其中,d(q,Si)是平面內節(jié)點Si和位置點q之間的歐氏距離.

將平面劃分為n個區(qū)域使得每個區(qū)域有且只有一個節(jié)點,且這個節(jié)點是到它所在區(qū)域任何位置點的加權距離最近的節(jié)點.這種圖劃分的方法稱為the multiplicatively weighted Voronoi(MW-Voronoi)diagram[16].每個區(qū)域的特性用數學公式可表示為:

Πi={q∈R2|dω(q,Si)≤dω(q,Sj),?j∈n{i}}

(2)

定義2.平面內任意給定兩個節(jié)點A、B以及正實數k,滿足AE/BE=k的所有點E的軌跡,就叫做線段AB形成的Apollonion circle 即ΩAB,k[17].

在本節(jié)后規(guī)定用Πi來表示第i個MW-Voronoi區(qū)域,為了構建Πi,首先找出所有節(jié)點Sj∈S{Si}的 Apollonion circle,即ΩSiSj,ωi/ωj.這會形成許多Apollonion circle,其中包含第i個節(jié)點的最小閉合區(qū)域就是Πi區(qū)域,如圖2所示.

圖2 擁有4個鄰點s2,s3,s4,s5的s1節(jié)點的MW-Voronoi區(qū)域[10]

2.3.2 覆蓋空洞修復的建模

假設用一個R2的二維平面區(qū)域來表示監(jiān)測區(qū)域,集合S表示隨機分布在區(qū)域中的N個感知半徑為ri的傳感器節(jié)點,傳感器節(jié)點的感知半徑不完全相同.該區(qū)域中不同位置被覆蓋的重要性用優(yōu)先級函數φ(q)來表示.例如q點的重要性大于p點,那么q點比p點被覆蓋的優(yōu)先級高,即φ(q)>φ(p).運用MW-Voronoi圖理論對監(jiān)測區(qū)域進行劃分,所有傳感器節(jié)點在提出的方法下向合適的方向移動,盡可能多地覆蓋優(yōu)先級高的區(qū)域.即通過傳感器節(jié)點之間有限信息的交換,提高監(jiān)測區(qū)域的總加權覆蓋面積.

定義3.優(yōu)先級函數在Πi區(qū)域(即第i個MW-Voronoi區(qū)域)上的積分被稱為第i個區(qū)域的加權值,用α∏i表示,即

(3)

定義4.在區(qū)域Πi中傳感器節(jié)點Si的感知半徑為ri,q是該區(qū)域中的任意一點.以q為圓心ri為半徑的圓與區(qū)域Πi的交集被稱為q點的覆蓋面積,記做覆蓋面積w.r.t.q.同理,覆蓋面積w.r.t.傳感器Si的位置,則被稱為該傳感器節(jié)點Si的局部覆蓋面積.

定義5.在區(qū)域Πi中傳感器節(jié)點Si的感知半徑為ri,x是該區(qū)域中的任意一點.優(yōu)先級函數在該區(qū)域的覆蓋面積w.r.t.x上的積分被稱為第i個區(qū)域的加權覆蓋面積,用數學公式表示為

(4)

其中C(x,ri)是以x為圓心,ri為半徑的圓.

(5)

同理,在某個MW-Voronoi區(qū)域中,令pi為傳感器節(jié)點Si的位置,那么傳感器節(jié)點Si的加權覆蓋面積w.r.t.pi和加權空洞面積w.r.t.pi分別被稱為傳感器節(jié)點Si的局部加權覆蓋面積和傳感器節(jié)點Si的局部加權空洞面積.優(yōu)先級函數在區(qū)域中所有覆蓋區(qū)域和非覆蓋區(qū)域上的積分分別稱為總加權覆蓋面積和總加權空洞面積.

3 OSC方法

本節(jié)提出了一種傳感器節(jié)點部署算法,該算法能使傳感器到達最佳部署位置;隨后給出了部署協議,遵循該協議能使網絡的整體加權覆蓋面積最大,最后給出該部署協議的正確性分析.

3.1 CMWV算法

給出如下公式:

(6)

C∏i為第i個傳感器節(jié)點在第i個MW-Voronoi區(qū)域中修復覆蓋空洞的最佳部署位置,該算法為CMWV算法,其中α∏i為定義3中的第i個區(qū)域的加權值.

CMWV算法能使傳感器節(jié)點不斷調整自身位置到達最佳部署位置,從而使得具有不同覆蓋優(yōu)先級的異構WSN的局部加權覆蓋面積最大.

3.2 部署協議

在部署協議中,CMWV算法會一直迭代直到達到協議終止條件后停止運行,該算法每次迭代都要經過五個階段.

第一階段,每個傳感器節(jié)點都要向其鄰居傳感器節(jié)點廣播自己的位置和感知半徑信息,同時接收來自它們的位置和感知半徑的信息,隨后每個傳感器節(jié)點根據這些信息建立自己的MW-Voronoi區(qū)域.

第二階段,按照本節(jié)所提出的CMWV算法,每個傳感器節(jié)點利用所獲得的信息可計算出自己所在區(qū)域中的候選位置.

第五階段,當每個傳感器節(jié)點的局部加權覆蓋面積增加都不超過預設值時,算法停止.

算法運行停止后,可獲得最大整體加權覆蓋面積.

3.3 部署協議的正確性分析

在無線傳感器網絡覆蓋空洞修復過程中,部署協議的關鍵就是每個傳感器節(jié)點僅在一種情況下移動,這種情況就是傳感器節(jié)點候選位置的局部加權覆蓋面積在相應MW-Voronoi區(qū)域中增加.由此推論,網絡的總加權覆蓋面積也會增加,理論及證明如下.

(7)

(8)

(9)

(10)

從公式(7),(10)可知,β′>β.

4 仿真實驗

鑒于WSN中覆蓋空洞修復問題的復雜性,不同的覆蓋空洞修復方法的有效性的評估和對比主要通過仿真軟件進行的.因為MATLAB仿真軟件的實時性控制和精確度較高,能更好地模擬真實環(huán)境,本文擬在64位Windows系統上的MATLAB軟件上進行仿真.在實驗中,將本文中的OSC方法與文獻[15]中的MWP方法進行比較.在MWP方法中,每個傳感器節(jié)點找到相應子區(qū)域的最大加權頂點位置,并且不斷向此位置點移動直到此位置點被覆蓋為止.實驗從加權覆蓋率和運行時間兩方面對兩種方法進行對比.實驗時,為了排除偶然性因素的影響使結論更具有普遍意義,需要設置重復組求其平均值,以下實驗中涉及的所有數據結果都是50次仿真實驗的平均值.

4.1 實驗設置

在監(jiān)測區(qū)域A上隨機部署n個感知半徑為ri的傳感器節(jié)點,傳感器節(jié)點的感知半徑不一定相同,其中區(qū)域A為一個面積為50m*50m的二維平面區(qū)域.用給定的優(yōu)先級函數φ(q)表示監(jiān)測區(qū)域A中不同位置被覆蓋的重要性,規(guī)定網絡中通信半徑為20m.在MATLAB仿真實驗中,當給定的傳感器節(jié)點的局部加權覆蓋面積增加值都不超過1%時算法停止,否則繼續(xù)執(zhí)行算法.

4.2 運行實例

初始設置如下:監(jiān)測區(qū)域中隨機部署著27個傳感器節(jié)點:15個感知半徑為1m,6個感知半徑為5/6m的,3個感知半徑為7/6m的,3個感知半徑為1.5m的.給定優(yōu)先級函數為φ1(q)=exp(-k*[(xq-25)2+(yq-25)2]),k=0.4,其中xq和yq分別是q點的橫坐標和縱坐標.圖3是該方法的運行實例,圖中給出了三個特定時間點的圖像,區(qū)域中各個位置的覆蓋優(yōu)先級用灰度來表示,且該點的灰度和其自身的覆蓋優(yōu)先級成正比,黑色代表最高優(yōu)先級.圖中黑點表示傳感器節(jié)點的位置,實心灰色圓形表示傳感器節(jié)點的感知范圍,圖中其余曲線代表MW-Voronoi子區(qū)域的邊界.修復覆蓋空洞過程中,覆蓋優(yōu)先級高的位置需要優(yōu)先被覆蓋.從圖3(c)看出算法停止后傳感器節(jié)點聚集在覆蓋優(yōu)先級高的區(qū)域,由此可知OSC方法對修復覆蓋空洞有作用.

圖3 OSC方法的運行實例

4.3 實驗結果分析

實驗1.本實驗的初始設置與運行實例中的完全相同.圖4描繪了每個周期算法執(zhí)行后的加權覆蓋率,圖中數據顯示兩種算法都進行一次迭代后,OSC方法的加權覆蓋率可達到40%,MWP方法的加權覆蓋率在25%左右;隨著迭代周期的增加OSC方法所獲得加權覆蓋率都要比MWP方法高,且運用OSC方法獲得的最終加權覆蓋率要遠遠大于運用MWP方法達到的最終加權覆蓋率.

圖4 每個周期的覆蓋率

實驗2.運行時間是評估覆蓋空洞修復方法優(yōu)劣性的重要標準之一.鑒于不同算法每個周期中傳感器節(jié)點的部署時間相差不了多少,因此達到截止條件時算法的運行周期數可作為評估運行時間的標準.給出四個場景,都用實驗1中的優(yōu)先級函數φ1(q).第一個場景中隨機部署9個傳感器節(jié)點:5個感知半徑為1m,2個感知半徑為5/6m,1個感知半徑為7/6m,1個感知半徑為1.5m.第二個場景中不同感知半徑的傳感器節(jié)點個數變?yōu)閳鼍耙恢械膬杀?即有10個感知半徑為1m,4個感知半徑為5/6m,2個感知半徑為7/6m,2個感知半徑為1.5m.類似地,場景三中不同感知半徑的傳感器節(jié)點數目為場景一中的3倍,場景四中不同感知半徑的傳感器節(jié)點數目為場景一中的4倍.圖5描述了在達到截止條件時每個算法的運行周期數都隨傳感器節(jié)點數目的增多而減少.這是因為當監(jiān)測區(qū)域存在大量傳感器節(jié)點時,劃分后的部分子區(qū)域范圍小于傳感器節(jié)點的感知范圍,傳感器節(jié)點覆蓋了大部分子區(qū)域,算法達到截止條件的時間更快.圖示OSC方法的運行周期數要小于MWP方法,因此OSC方法運行時間更短.

圖5 滿足不同傳感器節(jié)點數目達到截止條件時需要的周期數

實驗3.實驗1優(yōu)先級函數的至高點僅有一個,但現實中可能會出現多個至高點同時存在的情況.為進一步比較兩種算法,實驗設置與實驗1相同,只是優(yōu)先級函數改變?yōu)?/p>

φ2(q)=exp(-k*[(xq-10)2+(yq-40)2])+exp(-k*[(xq-25)2+(yq-7.5)2])+exp(-k*[(xq-37.5)2+(yq-32.5)2])

其中k=0.4,圖6描繪了在算法執(zhí)行完每個周期時,兩種算法的加權覆蓋率.從圖中可以看出,OSC方法所達到的加權覆蓋率都要比MWP方法的加權覆蓋率要高.說明在優(yōu)先級函數具有多個至高點時,OSC方法比MWP方法加權覆蓋率高,可得OSC方法與優(yōu)先級函數的至高點個數無關.

實驗4.本實驗應用優(yōu)先級函數φ1(q),其他設置與實驗1相同,通過討論優(yōu)先級函數的平滑程度對網絡加權覆蓋率的影響來分析所提算法的性能.圖7描述了不同k值時的最終加權覆蓋率.

圖6 每個周期的加權覆蓋率

從圖7可以看出,在優(yōu)先級函數比較平滑時,由MWP方法所得到的加權覆蓋率要高.隨著優(yōu)先級函數變得尖銳,即不同位置被修復的重要程度不同時OSC方法比MWP方法更占優(yōu)勢.可得OSC方法的性能與覆蓋優(yōu)先級函數的平滑程度有關,且更適合優(yōu)先級函數非平滑的情況.

圖7 場景一中k值不同時的最終加權覆蓋面積

通過上述實驗設置和實驗結果分析可以看出,我們所提出的OSC方法能夠在異構和優(yōu)先級兩種實際條件約束下,從覆蓋率、效率兩個評價指標上優(yōu)于對比算法MWP,即OSC方法的約束條件更加非理想化,更加接近于實際應用環(huán)境,故其在實際環(huán)境中的適用性更占優(yōu)勢.

5 結束語

WSN中覆蓋空洞修復問題一直是該領域的熱點,覆蓋率對網絡的服務質量有著直接影響,所以提高覆蓋率是覆蓋空洞修復中的重要內容.針對具有覆蓋優(yōu)先級的異構WSN中覆蓋空洞的修復問題,提出了最佳傳感器節(jié)點配置的方法.該方法采用MW-Voronoi圖理論對監(jiān)測區(qū)域的劃分,運用CMWV算法使傳感器節(jié)點不斷調整位置到達最佳部署位置,此時無線傳感器網絡的整體加權覆蓋面積最大.實驗表明,在不同覆蓋優(yōu)先級及不同網絡規(guī)模下,OSC方法比MWP方法不僅在加權覆蓋率至少提高10%,且減少了空洞修復時間;特殊情況下,在網絡不同位置的覆蓋優(yōu)先級(即重要性)幾乎相同時,MWP方法效果更好一些,但是在實際應用中不同位置被覆蓋的重要性不可能完全相同.因此在修復覆蓋空洞的實際應用中OSC方法適用性更強.本文的下一步工作重點是研究具有覆蓋優(yōu)先級的異構WSN中存在障礙物時的覆蓋空洞的修復問題.