基于Voronoi圖的無線傳感器網絡中移動節點覆蓋控制算法

宋曉曉, 章 亮

(巢湖學院 信息工程學院， 安徽 巢湖 238000)

0 引 言

無線傳感器網絡(Wire Sensor Network， WSN)技術在國內外受到高度重視，其發展的新型技術和發展方向也逐漸擴大。未來無線傳感器網絡對人類的生活方式將產生重大影響。在我國，WSN的研究幾乎與發達國家同步。2001年，中國科學院上海微系統與信息技術研究所率先建立了微系統研究中心，主要從事無線傳感器相關研究。2002年起，中國國家自然科學基金委員會開始資助WSN等有關工作項目，隨后諸多高校和企業加入到研究隊伍中。如今，WSN作為物聯網核心技術之一，已得到國家工信部和國家發展改革委員會的全力支持。

覆蓋問題來源于計算幾何、機器人系統和地理信息系統等眾多領域。例如畫廊看守(藝術畫廊問題 art gallery problem[1])問題、圓周覆蓋問題(circle covering problem)是計算幾何中兩個典型問題。藝術畫廊問題是如何進行合理部署最少的攝像機，能夠使得整個藝術畫廊都能夠被一臺攝像機節點監控。圓周覆蓋問題是指在目標區域中給定圓的數量一定，如何在圓半徑都相同的情況下，求得目標區域中具有最小半徑的圓。

傳統的WSN覆蓋控制的目的是在目標監測區域WSN節點中，通過監測各個節點，從而能夠獲取正確、完整且實時有效的信息。然而，傳統的WSN節點感知能力和能量基本有限，在大量的WSN節點會出現信息冗余等不良現象。為了提高并改善WSN的服務質量和感知能力，覆蓋控制算法就顯得極其關鍵。覆蓋控制的深入研究可在WSN節點能量、感知能力有限等情況下，使得WSN資源能夠得到合理利用，服務范圍得以改善,減少信息冗余等不良情況的出現。

在基礎的覆蓋控制理論知識，以及Voronoi圖的基本性質和概念的基礎上，依據數學分析結果提出一種移動節點調度算法，在無線傳感器網絡目標區域范圍內，使節點在目標區域可移動，來達到傳感器節點之間的覆蓋低冗余、高收斂的效果。

1 相關技術分析

1.1 Voronoi圖

Voronoi圖在各種科學領域中被廣泛應用，又稱Dirichlet圖或泰森多邊形[1]。設p1,p2為二維平面區域兩個節點，L為線段p1p2的垂直平分線。L將二維平面分為L1與L2兩部分。其中，位于L1平面的任意點pi具有特性

d(pi,p1)

式中：d(pi,pj)----pi和pj之間的歐氏距離。

即位于L1中的任意點pi比二維平面上其他點到p1的距離更近。記L1中所有點的集合為V(p1)。用H(p1,p2)表示半平面L1，則H(p2,p1)表示半平面L2。所以有

V(p1)=H(p1,p2),

V(p2)=H(p2,p1)。

若給定二維平面上n個點集合

S={p1,p2,p3,…,pn},

可定義Voronoi區域為

(1)

而V(pi)表示pi的軌跡區域，是n-1個半平面的交點，也是一個不多于n-1條邊的凸多邊形區域。

1.2 WSN感知模型分析

1)0～1感知模型。當某個目標節點在監測范圍內被監測節點所覆蓋時為1;否則為0。0～1感知模型以WSN節點o為感知節點，rs為監測半徑。若設節點o的位置坐標為(xi,yi)，在圓形目標監測范圍內任意一節點p的坐標為(xj,yj)，則節點p能被節點o監測到的概率大小為

(2)

2)概率感知模型。0～1感知模型是在基礎理論上的模型建立。實際應用中，由于受到電子信號與障礙物的干擾，傳感信號強度會變化，從而對目標區域的目標節點的監測具有二義性。在這種情況下，概率感知模型則可以反映出WSN節點對目標區域內某一節點的感知精度,以及在某種程度上表現出該WSN的置信度。可用公式來表示傳感器節點o對被感知節點p能夠監測到的所發現事件的概率統計規律為

(3)

式中：d(o,p)----節點o與節點p之間的歐氏距離;

R0----目標范圍內的感知半徑;

λ,β----可調參數，是WSN節點o對目標節點p的感知和監測概率，參數α=d(o,p)-r，r為閾值，當半徑小于等于r時為確定監測區域。

2 基于馮諾伊圖的覆蓋控制算法設計

2.1 覆蓋控制算法模型

虛擬力算法[3](VFA)，設WSN中若有一節點i受到虛擬力為Fi，另一節點j對節點i的虛擬力為Fij，兩節點距離為di,j。其中未被網絡覆蓋的WSN節點對節點i的合力記為FiR，并且若邊界存在大量節點，則必會受到強制力的作用，所以規定所有邊界節點約束力為Fb，則節點i所受合力公式為

(4)

最終根據合力公式確定每個節點的位置以及移動距離，將原傳感器的位置(xa,ya)更新為(xnew,ynew)

(5)

其中WSN節點會迭代運動，當迭代次數達到最大值時，會停止運動，算法結束。VFA算法雖然能指示WSN節點運動到相應位置來達到動態部署規劃效果，但在大規模WSN中，由于節點會受到多重因素以及作用力的影響，顯然只通過VFA算法不可行。VFA沒有對移動步長有所限定和研究，只是通過合力來實現位置和距離的改變，會有回路以及振蕩等不良現象。

2.2 算法優化模型

首先是節點覆蓋問題，主要是針對一種存在覆蓋盲區的情況提出一種移動WSN節點的優化算法。WSN節點在局部目標區域監測范圍內，節點分布情況是不對稱、不均勻的。在某一小塊區域中可能存在眾多節點，在大塊區域中可能存在少量節點的情況。為了提高網絡覆蓋范圍與覆蓋率，WSN節點坐標需要進行優化整改，將在小塊區域內集中的WSN節點向密度稀疏的區域移動，使得整個區域分布都能被監測。

2.2.1 Voronoi三角形的劃分

傳感器點集合S={s1,s2,s3,…,sn}。現以點集合作為Voronoi的產生點，構建二維平面區域Voronoi劃分，那么每個WSN節點si都處于相對應的區域Ai，且si對應的頂點集合為

Vsi={v1,v2,v3,…,vn}。

現將si與其相關聯的每個Voronoi區域的頂點相互連接。則可將Voronoi區域劃分為多個三角形組合

Ti={Ti1,Ti2,Ti3,…,Tin},

其中n為Voronoi區域邊的條數,稱劃分之后的三角形為Voronoi三角形[4]。

2.2.2 盲區面積計算

若能根據所劃分的Voronoi三角形來計算出點集合S中每個節點si和Voronoi三角形的每個頂點的坐標信息，那么就能求出單個Voronoi三角形所對應的覆蓋盲區面積bsij，則Voronoi多邊形區域Ai所對應的盲區面積為

(6)

整個Voronoi圖對應的盲區面積為

(7)

2.2.3 盲區面積分類

若歐氏距離[5]

兩種覆蓋盲區如圖1所示。

圖1 兩種覆蓋盲區

(8)

d(si,p)。

d(si,p)。

(9)

扇形simn的面積

(10)

盲區覆蓋面積

area(△simn),

(11)

(12)

其中

(13)

若歐氏距離

即兩個Voronoi頂點都不在監測范圍內。此時，也應進行分析：

a)Rsi≤d(si,p)不能被覆蓋的盲區區域面積

(14)

(15)

(16)

Rsi≤d(si,p)的情況如圖2所示。

(a) 交點p在線段內

(b) 交點p在線段的延長線上圖2 Rsi≤d(si,p)的情況

b)Rsi>d(si,p)也分兩種情況，如圖3所示。

圖3 Rsi>d(si,p)兩種情況

盲區面積

[area(asib)-area(mpn)],

(17)

其中

(18)

area(mpn)表示弧段mn與線段mpn圍成的區域面積。

因為

△msin的面積

(19)

扇形區域面積

(20)

所以

area(mpn)=area(△msin)-area(msin)=

(21)

2.3 算法實現

2.3.1 算法核心思想

首先將目標監測區域進行有界Voronoi劃分，以靜態節點為Voronoi圖產生點集，對所在區域的所有節點si∈S,求出該節點對應的Voronoi區域Ai的漏洞覆蓋盲區。若Ai的所有頂點都包括在si的監測范圍內，則該節點保持不變，說明監測范圍內沒有不能被覆蓋的區域，無漏洞；若在監測范圍內存在不能被覆蓋的區域時，則選定覆蓋盲區面積最大的Voronoi頂點，并使WSN節點si朝(si→v1)方向調整移動。

不能覆蓋的盲區面積S如圖4所示。

圖4 不能覆蓋的盲區面積S

對si所關聯Voronoi區域三角劃分，可構建出△siv1v2,△siv2v3,△siv3v4,△siv4v1共四個Voronoi三角形。顯然，在△siv1v2,△siv3v4,△siv4v1中均存在覆蓋漏洞。根據覆蓋盲區公式bsi1>bsi2計算方法，分別計算出覆蓋盲區bsi1,bsi2的面積。根據實驗計算結果比較可知面積。

由上述算法，WSN節點si應向v1移動。記無法覆蓋區域面積相關聯的點為vmax，則WSN節點移動方向為si→vmax，而移動步長大小是距Voronoi頂點vmax長度為感知半徑Ri點位置。

2.3.2 算法流程

算法流程如圖5所示。

圖5 算法流程

2.4 實驗結果與分析

仿真實驗對比如圖6所示。

(a) 原始情況

(b) 移動過程圖6 仿真實驗對比

原始數據和優化數據見表1。

表1 原始數據和優化數據

首先對Voronoi圖及時進行了三角劃分，在某個WSN節點si構建出多個Voronoi三角形。然后，判定每個Voronoi三角形中是否存在覆蓋漏洞，其次，根據式(6)～式(8)計算出覆蓋盲區面積，并比較大小。最后得出盲區面積最大的Voronoi頂點vmax，將節點si向Voronoi頂點vmax移動。實驗結果表明，原本處于邊緣處的節點4移動到與其他節點的感知半徑范圍之內，1，3，10節點雖處在其通信半徑范圍之內，但卻超出了其感知半徑所覆蓋的范圍，以及散布密集的節點2，6，7和10等節點移動散開，使得覆蓋面積增大，節點冗余度大大降低。這種移動節點優化移動算法造成最小程度的覆蓋能量損失，網絡覆蓋率會達到最優化，且目標區域節點位置坐標信息分布均勻。

3 結 語

WSN網絡覆蓋是網絡服務質量的重要指標之一，在實際應用環境下，要求在監測目標區域中每一個WSN節點都能被監測，并且沒有覆蓋盲區和信息冗余的存在。在國內外相關文獻充分調研情況下，分析了經典的覆蓋控制算法，并且結合數學分析和計算幾何知識提出了自己對算法優化思想。在WSN移動優化算法中，使得節點能夠移動到另一目標位置處，都可能會由于改變了該節點周圍的連通性能等情況導致網絡連線路徑斷裂現象。因此，在綜合考慮上述問題的基礎上，能夠構造出高效且符合實際的覆蓋控制優化算法是非常值得深入研究的方向。在真實的地理環境中，要綜合考慮模擬信號衰減和熱干擾源等不利因素對傳輸信息的影響。因此，研究出考慮到各種綜合因素的實際應用模型對WSN的覆蓋控制優化問題有著重要的意義。此次提出的移動節點優化算法是基于目標監測區域節點位置已知的情況下完成的，然而，在實際中需要通過定位算法和GPS等手段得到目標位置信息都不是十分精準。因此，設計一種目標位置信息的WSN覆蓋優化控制算法在實際應用中將起到舉足輕重的作用。