Ｖｏｒｏｎｏｉ圖在無線傳感器網(wǎng)絡(luò)柵欄覆蓋中的應(yīng)用研究

摘要：Voronoi是計算幾何學(xué)中的一個重要圖結(jié)構(gòu)，將其引入到無線傳感器網(wǎng)絡(luò)的覆蓋控制中，特別是柵欄覆蓋（barrier coverage）的研究中有著極其重要的指導(dǎo)意義。利用Voronoi圖的劃分，可快速搜索出傳感器網(wǎng)絡(luò)中的覆蓋漏洞，在僅考慮鄰近傳感器節(jié)點影響的寬松覆蓋要求下，論證出利用該圖生成的最小暴露進攻軌跡逼近于理想情況；但由于Voronoi的劃分僅僅是一種粗略的軌跡線段的集合，會造成該方法對網(wǎng)絡(luò)拓?fù)淝闆r相當(dāng)敏感，這將一定程度上限制其應(yīng)用范圍。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； Voronoi圖； 柵欄覆蓋； 進攻軌跡

中圖分類號：TP393.17文獻標(biāo)志碼：A

文章編號：1001－3695(2008)03－0863－03

在無線傳感器網(wǎng)絡(luò)中，覆蓋問題是衡量網(wǎng)絡(luò)的QoS指標(biāo)之一[1] 。其重要分支——柵欄覆蓋[2]，從研究覆蓋過程中產(chǎn)生的薄弱區(qū)域出發(fā)，利用（或彌補）該薄弱區(qū)域，探尋在感應(yīng)區(qū)域里暴露[3]程度最小的軌跡，從而制定出更加合理的節(jié)點放置策略。目前，將計算幾何學(xué)中的Voronoi圖應(yīng)用于傳感器網(wǎng)絡(luò)中新興的柵欄覆蓋控制還是一個嶄新的課題。

傳統(tǒng)的覆蓋控制對布撒方而言，考察感應(yīng)區(qū)域中的感應(yīng)盲點和空洞的分布情況。而在柵欄覆蓋問題中，這些感應(yīng)上的空隙被防守方所利用，使得目標(biāo)在移動中被傳感器探測到的可能性降到最低。在感應(yīng)區(qū)域中，布撒傳感器的目的是為更準(zhǔn)確有效地監(jiān)測目標(biāo)。被采集信息的目標(biāo)則應(yīng)回避傳感器節(jié)點的探測，防止自己被暴露。但是在實際的應(yīng)用中回避并不是一個有效的方法。一方面目標(biāo)不可能無限制地回避；另一方面，在特殊應(yīng)用中，目標(biāo)必須穿過感應(yīng)區(qū)域。例如戰(zhàn)場環(huán)境中采集敵方布防情況時，目標(biāo)必須經(jīng)過敵方戰(zhàn)場回報數(shù)據(jù)。該軌跡既是目標(biāo)的安全進攻路線，也是傳感器探測的薄弱地帶，對再次的布撒傳感器節(jié)點具有指導(dǎo)意義。

本文針對柵欄控制，將傳統(tǒng)策略中的最小暴露軌跡的定性描述，改進為更加精準(zhǔn)的定量描述。從少量傳感器分布的場景出發(fā)，計算出網(wǎng)絡(luò)中的最小暴露軌跡的數(shù)學(xué)表達式；進而推出多個傳感器節(jié)點作用下目標(biāo)進攻軌跡與Voronoi劃分的關(guān)系。在此基礎(chǔ)上，嚴(yán)格地將Voronoi圖區(qū)分地應(yīng)用于柵欄覆蓋研究中的不同場景。

1基于Voronoi的最小暴露軌跡

1．1軌跡暴露量的計算

不同的應(yīng)用場合中，傳感器傳感模型有所差異。但是，感應(yīng)能力隨距離的增長而降低的這一基本特性保持不變[4]。傳感器節(jié)點s在目標(biāo)點q的感應(yīng)模型定義如下：

S(s，q)=λ/disk(s，q) （1）

其中：dis(s，q)=[s(x)-q(x)]2+[s(y)-q(y)]2是傳感器節(jié)點s與q在二維空間上的歐幾里德距離；λ>0是感應(yīng)系數(shù)；k=1，2是距離影響系數(shù)。

設(shè)Sa是參與感應(yīng)目標(biāo)q的傳感器的集合，在時間[t1，t2]內(nèi)，目標(biāo)q沿軌跡p(t)=[x(t)，y(t)]行進了距離L，在該軌跡上，q受傳感器Sa的感應(yīng)之和，即是目標(biāo)q在軌跡p(t)上的暴露量。可定義為

E[Sa，p(t)，t1，t2]=∫t2t1∑iS[si，q(t)]×|dp(t)/dt|dt（2）

其中：si∈Sa。

如x(t)、y(t)在時間[t1，t2]內(nèi)連續(xù)可微，則存在|dp(t)/dt|=[dx(t)/dt]2+[dy(t)/dt]2；二維空間內(nèi)p(t)軌跡可表示為y=y(x)，x∈[x(t1)，x(t2)]=[x1，x2]，可將式（2）中的定積分形式化為曲線積分，實現(xiàn)暴露量的計算與時間的解耦：

E[p(x)，y(x)]=∫x2x1∑iS{si，[x，y(x)]}1+y2(x)dx=

∫L∑iS{si，[x，y(x)]}dl（3）

1．2最小暴露軌跡

傳統(tǒng)的Worstcoverage[1，5]策略認(rèn)為：從感應(yīng)區(qū)域Ω中的任意一點到另外一點，進攻目標(biāo)q沿Voronoi圖的劃分線段移動，得到的軌跡暴露量最小，如圖1的粗線所示。所謂Voronoi圖的劃分是指在給定Ω內(nèi)，隨機均勻（概率上）布撒N個傳感器，利用Voronoi圖可將區(qū)域Ω劃分為N個子區(qū)域（Voronoi多邊形），每個子區(qū)域內(nèi)有且僅有一個傳感器，在子區(qū)域中的任何點到該區(qū)域中的傳感器的距離均不大于到其他傳感器的距離。

其中生成Voronoi圖的復(fù)雜度為O[n lg(n)]，n為Voronoi劃分的交點數(shù)。利用worstcoverage策略中的二分法查找軌跡時復(fù)雜度為O(n)，如利用常規(guī)Dijkstra路由算法查找軌跡，則復(fù)雜度為O(n2)。可見，worstcoverage策略在較好的情況下，復(fù)雜度為O[n log(n)]；如改用常規(guī)的算法則復(fù)雜度為O[n2 log(n)]。

Worstcoverage策略給出了在計算機上利用Voronoi圖，解決無線傳感器網(wǎng)絡(luò)中的柵欄覆蓋控制的途徑。但是它僅僅是定性地描述感應(yīng)區(qū)域內(nèi)的暴露程度最小的軌跡，并沒有從定量的角度來證明Voronoi圖的劃分結(jié)論。

2少量傳感器節(jié)點作用下的最小暴露軌跡分析

2．1單個傳感器作用

設(shè)感應(yīng)場景為二維空間區(qū)域Ω內(nèi)，有且僅有一個傳感器節(jié)點s，以其為原點建立坐標(biāo)系。目標(biāo)點q的運動軌跡L:y=y(x)，s相距y=y(x)上任意一點q(x，y)的距離為dis(s，q)=x2+y2(x)。利用式（1）和（3），并不失一般性地假設(shè)λ=1，k=2[3]，則點q在L上的暴露量為

E(s，L)=∫x2x1S(s，(x，y(x))1+y2(x)dx=

∫L1/[x2+y2(x)]dl （4）

2．2兩個傳感器作用

定理1在兩個完全一致的傳感器節(jié)點作用下的感應(yīng)區(qū)域Ω中，如果源點和目的地均位于兩個傳感器的中垂線上，那么目標(biāo)點q的最小暴露軌跡就是這條中垂線。

證明設(shè)兩個傳感器節(jié)點分別為s1和s2，且相距2c。以兩節(jié)點連線及其中垂線為軸線，交點o為原點，建立坐標(biāo)系，如圖2所示。設(shè)源點和目的地位于A(x1，0)，B(x2，0)，以此四個點設(shè)定感應(yīng)區(qū)域Ω，Ω={(x，y)|x∈[x1，x2]，y∈[-c，c]}。在該區(qū)域上尋找q的一條軌跡L:y=y(x)，使得q在此軌跡上的暴露量最小。

2．3仿真驗證

仿真平臺采用MATLAB，場景設(shè)置：Ω=100 m×100 m，兩個傳感器節(jié)點位于頂端和底端的中心位置，即c=50 m；源點和目的地位于左端和右端的中心位置，即x1=-50 m，x2=50 m。

利用文獻[3]提供的Gridbased算法，可以得到理想最小暴露曲線（optimal track，OT）。Gridbased是通過對被監(jiān)控區(qū)域的劃分，形成許多短小的備選路徑段，再通過路徑搜索從這些備選路徑段中搜索路徑。該算法是一種全路徑搜索的方法，但是計算的復(fù)雜度Gridbased算法的復(fù)雜度為O(|VG′|3)（其中|VG′|=2mn2+2mn+n-1為被監(jiān)控區(qū)域的劃分交點數(shù)）。該算法所涉及的劃分參數(shù)設(shè)定為n=16，m=4。

圖3是采用Gridbased方法得到的軌跡。可見，對兩個傳感器節(jié)點作用的情況下，Gridbased全路徑搜索得到的軌

跡與定理1中的最小暴露量軌跡一致。

3多傳感器作用下的最小暴露軌跡在Voronoi圖中的分析

根據(jù)軌跡的暴露量受影響的傳感器節(jié)點個數(shù)的差異，可將Voronoi圖劃分的軌跡分為不完全影響劃分軌跡（incomplete impacting track， IIT）和完全影響劃分軌跡（complete impacting track， CIT）。

3．1不完全影響下的Voronoi圖劃分軌跡

根據(jù)Voronoi圖的性質(zhì)可知，Voronoi邊是距離該邊最近的兩個節(jié)點的中垂線段，稱這兩點是Voronoi邊的鄰近點。在Voronoi圖劃分生成的權(quán)重圖的過程中，邊的權(quán)重計算僅考慮Voronoi邊的鄰近傳感器節(jié)點作用下暴露量，即

weight(ej)=E({sj1，sj2}，ej)（7）

以此生成的軌跡即是不完全影響下的Voronoi圖劃分軌跡。Worstcoverage算法是一種不完全影響下的Voronoi圖劃分軌跡的方法。式（7）中ej∈E，G=(E，V)，節(jié)點{sj1，sj2}是邊ej的鄰近點。

多次隨機仿真發(fā)現(xiàn)Voronoi子區(qū)域內(nèi)最小暴露軌跡表現(xiàn)出與定理1一致的特點，可得到結(jié)論1。

結(jié)論1在進攻目標(biāo)只考慮兩個鄰近傳感器節(jié)點的影響時，其最小暴露軌跡會向著這兩個傳感器節(jié)點的中垂線段靠攏（圖4（a））。在每個Voronoi子區(qū)域內(nèi)的軌跡，則表現(xiàn)為向著子區(qū)域邊緣靠攏的趨勢（圖4（b））。

不完全影響下Voronoi劃分軌跡，雖然僅僅考慮Voronoi邊的鄰近點影響效果，但在Voronoi子區(qū)域內(nèi)，或者在傳感器節(jié)點分布均勻的情況下，該軌跡和Gridbased算法得到理想軌跡較為近似。但在傳感器節(jié)點分布相對不均勻的場景下，或非同一子區(qū)域內(nèi)的情況下，這種只考慮兩個鄰近節(jié)點作用下的最小暴露軌跡顯然準(zhǔn)確程度較低。

3．2完全影響下的Voronoi圖劃分軌跡

完善不完全影響下Voronoi的權(quán)重圖的生成方式，使其每一條邊的權(quán)重計算包含監(jiān)測區(qū)域內(nèi)所有傳感器節(jié)點的影響。在新的權(quán)重圖中，利用現(xiàn)有的路徑算法即可生成相應(yīng)的軌跡。

weight(ej)=E(S，ej)（8）

其中：ej∈E，G=(E，V)，S是所有傳感器節(jié)點的集合。

3．3仿真分析

圖5是在40個傳感器節(jié)點分布相對不均勻的場景下，完全、不完全影響Voronoi圖劃分和理想算法下的三條軌跡（即IIT、CIT、OT）。其中仿真相關(guān)參數(shù)與2．3節(jié)相同。

比較三條軌跡在完全影響和不完全影響下的暴露量，如表1所示。本例中，不完全影響下Voronoi劃分軌跡IIT的生成過程中僅考慮Voronoi邊的兩個鄰近點的影響，但由于在感應(yīng)區(qū)域中傳感器節(jié)點拓?fù)浞植汲尸F(xiàn)出“/”對角方向密集的分布不均勻現(xiàn)象，使得該軌跡受到其他節(jié)點的影響并沒有小到可以忽略程度。正如表1所示，IIT實際上受所有傳感器節(jié)點影響下的暴露量E(S，IIT)和CIT受所有傳感器影響下的暴露量E(S，CIT) 相比，其實更大。

綜上所述，在應(yīng)用中，對軌跡暴露量的限制并不苛刻時，在節(jié)點均勻分布的傳感器網(wǎng)絡(luò)中，僅考慮鄰近點影響的不完全影響下的Voronoi的劃分軌跡方法，可以近似地替代計算量龐大的理想軌跡算法。如果放松計算量的約束，完全影響下的Voronoi的劃分軌跡方法相對于不完全影響下的Voronoi的劃分軌跡方法可以進一步提高和理想軌跡的逼近程度，且對節(jié)點的分布的敏感性降低。

4結(jié)束語

本文從定量的角度論證了Voronoi圖的劃分與最小暴露軌跡的關(guān)系，并根據(jù)影響軌跡的傳感器節(jié)點數(shù)目的差異，對傳感器網(wǎng)絡(luò)中的不完全影響劃分軌跡（IIT）和完全影響劃分軌跡（CIT）對拓?fù)涞拿舾行浴④壽E的準(zhǔn)確性進行了分析。

這種將計算幾何中的Voronoi劃分應(yīng)用于傳感器網(wǎng)絡(luò)的柵欄覆蓋控制中的方法，為利用計算機尋求傳感器網(wǎng)絡(luò)中的最小暴露軌跡提供了一個快速、有效的途徑。利用該劃分生成的最小暴露軌跡，就是傳感器網(wǎng)絡(luò)中的覆蓋漏洞區(qū)域，該軌跡信息對傳感器網(wǎng)絡(luò)的二次布撒具有有益的指導(dǎo)作用。但另一方面，必須看到Voronoi的劃分必須依賴于對傳感器網(wǎng)絡(luò)全局拓?fù)湫畔⒌墨@取，這將限制其應(yīng)用的可操作性，這也是未來研究中所要克服的困難所在。

參考文獻：

[1]MEGUERDICHIAN S， KOUSHANFAR F， POTKONJAK M， et al. Worst and bestcase coverage in sensor networks[J]. IEEE Trans on Mobile Computing， 2005，4(1):84－92.

[2]任彥，張思東，張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報，2006，17（3）:422－433.

[3]MEGUERDICHIAN S， KOUSHANFAR F， QU G，et al. Exposure in wireless Ad hoc sensor networks[C]//Proc of ACM International Conference on Mobile Computing and Networking (MobiCom). Rome， Italy:[s.n.]，2001:139150.

[4]ADLAKHA S， SRIVASTAVA M. Critical density thresholds for co￣verage in wireless sensor networks[C]//Proc of IEEE WCNC. 2003:16－20， 16151620.

[5]VELTRI G， HUANG Q， QU G， et al. Minimal and maximal exposure path algorithms for wireless embedded sensor networks[C]//Proc of ACM Int’1 SENSYS. LA， Calif:[s.n.]，2003:40－50.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”