Ｖｏｒｏｎｏｉ圖在無線傳感器網絡柵欄覆蓋中的應用研究

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

關鍵詞：無線傳感器網絡； Voronoi圖； 柵欄覆蓋； 進攻軌跡

中圖分類號：TP393.17文獻標志碼：A

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

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

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

本文針對柵欄控制，將傳統策略中的最小暴露軌跡的定性描述，改進為更加精準的定量描述。從少量傳感器分布的場景出發，計算出網絡中的最小暴露軌跡的數學表達式；進而推出多個傳感器節點作用下目標進攻軌跡與Voronoi劃分的關系。在此基礎上，嚴格地將Voronoi圖區分地應用于柵欄覆蓋研究中的不同場景。

1基于Voronoi的最小暴露軌跡

1．1軌跡暴露量的計算

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

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

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

設Sa是參與感應目標q的傳感器的集合，在時間[t1，t2]內，目標q沿軌跡p(t)=[x(t)，y(t)]行進了距離L，在該軌跡上，q受傳感器Sa的感應之和，即是目標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]內連續可微，則存在|dp(t)/dt|=[dx(t)/dt]2+[dy(t)/dt]2；二維空間內p(t)軌跡可表示為y=y(x)，x∈[x(t1)，x(t2)]=[x1，x2]，可將式（2）中的定積分形式化為曲線積分，實現暴露量的計算與時間的解耦：

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最小暴露軌跡

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

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

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

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

2．1單個傳感器作用

設感應場景為二維空間區域Ω內，有且僅有一個傳感器節點s，以其為原點建立坐標系。目標點q的運動軌跡L:y=y(x)，s相距y=y(x)上任意一點q(x，y)的距離為dis(s，q)=x2+y2(x)。利用式（1）和（3），并不失一般性地假設λ=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在兩個完全一致的傳感器節點作用下的感應區域Ω中，如果源點和目的地均位于兩個傳感器的中垂線上，那么目標點q的最小暴露軌跡就是這條中垂線。

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

2．3仿真驗證

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

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

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

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

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

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

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

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

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

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

多次隨機仿真發現Voronoi子區域內最小暴露軌跡表現出與定理1一致的特點，可得到結論1。

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

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

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

完善不完全影響下Voronoi的權重圖的生成方式，使其每一條邊的權重計算包含監測區域內所有傳感器節點的影響。在新的權重圖中，利用現有的路徑算法即可生成相應的軌跡。

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

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

3．3仿真分析

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

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

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

4結束語

本文從定量的角度論證了Voronoi圖的劃分與最小暴露軌跡的關系，并根據影響軌跡的傳感器節點數目的差異，對傳感器網絡中的不完全影響劃分軌跡（IIT）和完全影響劃分軌跡（CIT）對拓撲的敏感性、軌跡的準確性進行了分析。

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

參考文獻：

[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]任彥，張思東，張宏科.無線傳感器網絡中覆蓋控制理論與算法[J].軟件學報，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.

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