基于Voronoi圖的無線傳感器網(wǎng)絡(luò)中移動節(jié)點覆蓋控制算法

宋曉曉, 章 亮

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

0 引 言

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

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

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

在基礎(chǔ)的覆蓋控制理論知識，以及Voronoi圖的基本性質(zhì)和概念的基礎(chǔ)上，依據(jù)數(shù)學(xué)分析結(jié)果提出一種移動節(jié)點調(diào)度算法，在無線傳感器網(wǎng)絡(luò)目標(biāo)區(qū)域范圍內(nèi)，使節(jié)點在目標(biāo)區(qū)域可移動，來達到傳感器節(jié)點之間的覆蓋低冗余、高收斂的效果。

1 相關(guān)技術(shù)分析

1.1 Voronoi圖

Voronoi圖在各種科學(xué)領(lǐng)域中被廣泛應(yīng)用，又稱Dirichlet圖或泰森多邊形[1]。設(shè)p1,p2為二維平面區(qū)域兩個節(jié)點，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區(qū)域為

(1)

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

1.2 WSN感知模型分析

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

(2)

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

(3)

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

R0----目標(biāo)范圍內(nèi)的感知半徑;

λ,β----可調(diào)參數(shù)，是WSN節(jié)點o對目標(biāo)節(jié)點p的感知和監(jiān)測概率，參數(shù)α=d(o,p)-r，r為閾值，當(dāng)半徑小于等于r時為確定監(jiān)測區(qū)域。

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

2.1 覆蓋控制算法模型

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

(4)

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

(5)

其中WSN節(jié)點會迭代運動，當(dāng)?shù)螖?shù)達到最大值時，會停止運動，算法結(jié)束。VFA算法雖然能指示W(wǎng)SN節(jié)點運動到相應(yīng)位置來達到動態(tài)部署規(guī)劃效果，但在大規(guī)模WSN中，由于節(jié)點會受到多重因素以及作用力的影響，顯然只通過VFA算法不可行。VFA沒有對移動步長有所限定和研究，只是通過合力來實現(xiàn)位置和距離的改變，會有回路以及振蕩等不良現(xiàn)象。

2.2 算法優(yōu)化模型

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

2.2.1 Voronoi三角形的劃分

傳感器點集合S={s1,s2,s3,…,sn}?，F(xiàn)以點集合作為Voronoi的產(chǎn)生點，構(gòu)建二維平面區(qū)域Voronoi劃分，那么每個WSN節(jié)點si都處于相對應(yīng)的區(qū)域Ai，且si對應(yīng)的頂點集合為

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

現(xiàn)將si與其相關(guān)聯(lián)的每個Voronoi區(qū)域的頂點相互連接。則可將Voronoi區(qū)域劃分為多個三角形組合

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

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

2.2.2 盲區(qū)面積計算

若能根據(jù)所劃分的Voronoi三角形來計算出點集合S中每個節(jié)點si和Voronoi三角形的每個頂點的坐標(biāo)信息，那么就能求出單個Voronoi三角形所對應(yīng)的覆蓋盲區(qū)面積bsij，則Voronoi多邊形區(qū)域Ai所對應(yīng)的盲區(qū)面積為

(6)

整個Voronoi圖對應(yīng)的盲區(qū)面積為

(7)

2.2.3 盲區(qū)面積分類

若歐氏距離[5]

兩種覆蓋盲區(qū)如圖1所示。

圖1 兩種覆蓋盲區(qū)

(8)

d(si,p)。

d(si,p)。

(9)

扇形simn的面積

(10)

盲區(qū)覆蓋面積

area(△simn),

(11)

(12)

其中

(13)

若歐氏距離

即兩個Voronoi頂點都不在監(jiān)測范圍內(nèi)。此時，也應(yīng)進行分析：

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

(14)

(15)

(16)

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

(a) 交點p在線段內(nèi)

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

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

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

盲區(qū)面積

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

(17)

其中

(18)

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

因為

△msin的面積

(19)

扇形區(qū)域面積

(20)

所以

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

(21)

2.3 算法實現(xiàn)

2.3.1 算法核心思想

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

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

圖4 不能覆蓋的盲區(qū)面積S

對si所關(guān)聯(lián)Voronoi區(qū)域三角劃分，可構(gòu)建出△siv1v2,△siv2v3,△siv3v4,△siv4v1共四個Voronoi三角形。顯然，在△siv1v2,△siv3v4,△siv4v1中均存在覆蓋漏洞。根據(jù)覆蓋盲區(qū)公式bsi1>bsi2計算方法，分別計算出覆蓋盲區(qū)bsi1,bsi2的面積。根據(jù)實驗計算結(jié)果比較可知面積。

由上述算法，WSN節(jié)點si應(yīng)向v1移動。記無法覆蓋區(qū)域面積相關(guān)聯(lián)的點為vmax，則WSN節(jié)點移動方向為si→vmax，而移動步長大小是距Voronoi頂點vmax長度為感知半徑Ri點位置。

2.3.2 算法流程

算法流程如圖5所示。

圖5 算法流程

2.4 實驗結(jié)果與分析

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

(a) 原始情況

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

原始數(shù)據(jù)和優(yōu)化數(shù)據(jù)見表1。

表1 原始數(shù)據(jù)和優(yōu)化數(shù)據(jù)

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

3 結(jié) 語

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