無線傳感器網絡覆蓋控制算法分析

張永棠　羅先錄　周富肯

摘 要：網絡覆蓋算法直接影響無線傳感器網絡“感知”服務質量。文章根據傳感器網絡覆蓋控制理論，對WSN的覆蓋問題進行了歸納與總結，建立了WSN研究框架，從生存時間、部署策略、通信協議和組網等問題對無線傳感器網絡的覆蓋控制策略和算法進行詳細分析。

關鍵詞：無線傳感器網絡；算法；網絡通信；覆蓋控制；信息安全

中圖分類號：TP393 文獻標識碼：A

Abstract：Network coverage algorithm for wireless sensor network directly affects the perception quality of service.The according to the sensor network coverage control theory，on the WSN coverage problem were summed up and summarized，establishes the framework for WSN research，from the survival time，deployment strategy，communication protocol and network of wireless sensor network coverage control strategies and algorithms were analyzed in detail.

Keywords：wireless sensor networks；algorithm；network communication；covering control；information security

1 引言（Introduction）

由于無線傳感器網絡（WSN）節點具備體積小、成本低廉、可無線通信以及有自組織能力等特點，使得其在環境惡劣以及無人值守場合具有很高應用價值。作為一種新興網絡，WSN目前仍存在許多亟待解決的問題，例如節能、部署覆蓋、路由規劃、定位、自組織和協同性等[1]。其中覆蓋方法對傳感器網絡的生存時間、部署策略、通信協議和組網等問題的解決具有十分重要的影響。

由于傳感器和應用場景千變萬化，實際應用中傳感器網絡的覆蓋問題需要考慮很多方面。通過網絡傳感器節點配置以及路由選擇等手段來優化WSN資源分配，改善網絡的感知、監視、傳感和通信等各種服務[2]。目前，WSN的覆蓋控制策略已經有多種，下面對無線傳感器網絡的覆蓋控制策略和算法進行詳細分析。

2 WSN覆蓋控制算法（WSN overlay control

algorithm）

基于傳感器網絡覆蓋控制理論和覆蓋控制問題描述，建立了WSN研究框架，如圖1所示。依照該框架，可以發現現有覆蓋控制策略所研究的問題存在很大差異，例如監測目標（區域）、節點能力（是否可移動）、節點感知模型和信息協同處理、實現方案的約束和先決條件（精確定位、時間同步），導致解決的方案和手段也千差萬別。

2.1 最大流覆蓋

考慮監控區域中有一組位置已知的目標點（targets），足夠數量的傳感器節點（sensors）隨機地部署在區域內，節點將自身所能監控的目標點信息通過無線方式傳輸至集中處理節點（central processing node），由集中處理節點根據所收集的信息利用最大流的研究方法，對網絡中的節點進行分組，使組群之間相互獨立，并能完全監控區域中的目標點。在任何時刻都只有一個組群處于工作狀態，各組群循環工作并保證在任何時刻都能監控到目標點，從而達到資源的合理利用。通過合適算法確定分組的最大個數，可以更加有效地優化網絡資源，延長WSN的工作時間。

在將問題轉換成尋求最大流問題后，提出一個啟發式的算法MC-MIP來計算頂點Y2處所能獲得的最大流及節點分組。如圖2中分組為C1={S1，S3}，C2={S2}。

2.2 最壞/最佳覆蓋

考慮一片隨機部署有傳感器節點的區域，從該區域的一點到另一點，如何選擇路徑使其被WSN網絡節點監控到的幾率最小/大，則為最壞/最佳覆蓋問題。

定義：設一條連接起點和終點的路徑P，則裂縫（Breach）定義為P到任意節點的歐氏距離的最小值；支持（Support）定義為P到其最近節點的歐氏距離的最大值。

最壞/最佳覆蓋問題轉變為在區域中尋找“最大裂縫路徑（Maximal Breach Path）”和“最大支持路徑（Maximal Support Path）”[3]，如圖3所示。采用計算幾何中的Voronoi圖[4]和Delaunay三角形來完成對最大裂縫路徑和最大支持路徑的構建和查找。可見，最壞/最佳覆蓋問題解決了實際應用中路徑跟蹤問題。

2.3 集成覆蓋與連接

為了驗證WSN覆蓋與連接性的關系，設RC為通信距離，RS為傳感距離，證明：（1）對于1-覆蓋的區域，當RC≥2RS時，區域內的節點完全連接；（2）對于KS-覆蓋的區域，當RC≥2RS時，區域內的節點為KS-連接。

考慮兩個相鄰節點存在虛擬的“引力”或“斥力”，在虛擬力的作用下，兩個節點可以相互靠近或者遠離。若在監控區域中存在兩個相鄰的節點Si與Sj，其間距為dij，當dij>dth時，其中dth為相鄰節點的最佳間距，則Si與Sj表現為引力；當dij

圖4表明利用VFA算法可以有效地改善由于節點隨機分布所帶來的覆蓋不均，滿足各種應用場合的覆蓋需求。

2.4 信息覆蓋

將環境參數（光強、聲強和溫度等）的變化考慮成場，利用場理論以及概率論研究在隨機部署、不可移動的大規模WSN中綜合周邊節點的采集數據的基礎上得出監控盲點的環境信息，是一類信息覆蓋問題。如圖5所示，中間“☆”處沒有任何節點可以監控到，然而可以通過綜合周邊部署的節點監控數據，根據場的分布和概率論得出“☆”處的環境信息θ。

如圖5所示，“●”為傳感器節點，設圖中傳感器對環境的檢測值分別為Sk，k為節點編號，節點k與☆處的距離分別為dk，假設環境信息θ隨距離衰減，衰減系數為α（α>0），則在距離d處環境信息為θ/d。由于在實際監測中存在噪聲nk，則有

通過周邊節點的監測信息Sk，根據上式以及概率估計算法可以得出“☆”處的環境信息。記不大于預先設定值A的概率為Pr（A），若Pr（A）≥ε（0≤ε≤1），則稱“☆”處可以被其周邊的K個節點信息覆蓋（記為（K，ε）-覆蓋）。

當K=1時，即為簡單的圓盤覆蓋；當K>1時，信息覆蓋不僅僅是K個圓盤覆蓋的組合。可見，信息覆蓋擴大了原先的覆蓋范圍，更好的對監測區域實行監控。

3 結論（Conclusion）

WSN如何對區域進行監控是在WSN進入工作階段之前必須考慮的問題，網絡覆蓋控制作為WSN實施過程中的一個基本問題，反映了網絡所能提供的“感知”服務質量[5]。本文根據近年來的覆蓋控制研究成果，對WSN的覆蓋問題進行了歸納與總結，提出了研究WSN覆蓋問題時所需關注的各個方面，并詳細介紹了無線傳感器網絡算法。WSN的覆蓋控制依然存在許多亟待解決的問題。例如，現有的WSN覆蓋控制策略主要集中在解決簡單傳感模型下的覆蓋控制，對于節點感知存在方向差異的情況的研究，仍然是一個比較復雜的難題。

參考文獻（References）

[1] 任彥，張思東，張宏科.無線傳感器網絡中覆蓋控制理論與算法[J].軟件學報，2006（3）：422-433.

[2] 曹峰，劉麗萍，王智.能量有效的無線移動傳感器網絡部署[J].信息與控制， 2006（2）：147-153.

[3] 王燕莉，安世全.無線傳感器網絡的覆蓋問題研究[J].傳感技術學報，2005，18（2）：307-312.

[4] 任彥，張思東，張宏科.無線傳感器網絡三維空間最佳覆蓋路由協議[J].電子學報， 2006（2）：306-311.

作者簡介：

張永棠（1981-），男，碩士，副教授，系統分析師.研究領域：光通信與傳感器網絡應用.

羅先錄（1973-），男，碩士，副教授，系統分析師.研究領域：軟件與網絡安全.

周富肯（1982-），男，碩士，講師.研究領域：網絡安全.