基于網格掃描的實現目標點覆蓋的確定性傳感器節點部署方法*

郭秀明，趙春江 ，楊信廷，孫傳恒，李 明，李文勇，周 超

(1．中國農業大學信息與電氣工程學院，北京100083;2．國家農業信息化工程技術研究中心，北京100097;3．農業部農業信息技術重點開放實驗室，北京100097)

無線傳感器網絡(Wireless Sensor Networks，WSNs)是由部署在觀測環境附近的大量微型低功耗的傳感器節點組成的多跳網絡系統，目的是實時檢測、感知和采集各種對象的信息。這些信息通過無線方式發送，并以自組織的網絡方式傳送到用戶終端，從而實現物理世界、計算世界以及人類社會的三元世界的聯通。WSN在軍事國防、環境監測、生物醫療、智能家居、危險區域的遠程監控等領域得到了廣泛的應用，引起了學術界和工業界的高度重視［1－2］。

在構建無線傳感器網絡過程中，網絡覆蓋是最基本的問題之一［3］。根據覆蓋對象，覆蓋可分為區域性全覆蓋［4］、關鍵點覆蓋［5］、邊界覆蓋［6］、柵欄覆蓋［7］等，根據部署方式可分為隨機部署和確定性部署［8］。在人類很難到達的地區，如戰場、森林等，多使用隨機部署方式;飛機拋灑大量節點到目標區域，節點自動組網［9］。在人類容易到達的地方如農田等，手工確定性部署節點能減少傳感器節點數目，降低成本［5］。

近年來，眾多學者對WSN的覆蓋問題進行了研究，取得了一定成果［10］。林祝亮等［11］在粒子進化的多粒子群算法的基礎上，提出了一種無線傳感器網絡覆蓋的優化策略，擴大了網絡覆蓋范圍，延長了網絡壽命。李明等［12］針對異構傳感器網絡節點的高密度部署和監測目標非均勻分布的情況，提出了一種基于模擬退火算法的成本最優化部署方法。Yan Ruoyu等［13］通過網格掃描的再部署方法使用較少的傳感器節點實現了較大的區域覆蓋率。目前的覆蓋技術研究多數集中在區域覆蓋的隨機部署［14－15］、確定性部署［16］以及目標覆蓋的隨機部署等方面［17］;而針對目標覆蓋的確定性部署問題卻很少涉及。

目標覆蓋的確定性部署，主要針對位置已知的離散目標點，尋找最少的傳感器節點數及最佳的節點部署位置。當目標點分散或者對目標點的覆蓋水平要求很高時，須在每個目標點處都放置一個感知節點，如監測目標點的溫濕度［18］。但當目標點密度較大且對目標點覆蓋水平要求不是很高時，一個節點可以同時覆蓋多個目標點。何欣等［5］利用目標點的最多層交疊域和遺傳算法，提出了一個面向目標覆蓋的最優確定性部署方法;該方法極大的降低了網絡的部署成本，實現了目標覆蓋的確定性部署;但該方法也存在一些不足之處，最多層交疊域的計算復雜，而且遺傳算法可能存在早熟問題。

本文提出了一種簡單有效的基于網格掃描的目標點覆蓋的確定性部署方法，首先把目標點所在區域劃分為若干正方形網格，然后從中選擇最合適的網格作為下一個節點的放置位置，直到覆蓋所有目標點;同時為了評價覆蓋水平，本文引入了概率感知模型，更準確的表示節點對目標點的感知水平。文章第二部分詳細介紹了基于網格掃描的目標點覆蓋的確定性部署方法;在第三部分，針對網格邊長和概率感知模型的感知概率下限分別選取不同數值進行仿真實驗，驗證本文算法的有效性;最后是論文的總結和結論。

1 基于網格掃描的目標點覆蓋的節點

如何使用最少的節點實現對已知目標點的覆蓋并達到預設的覆蓋水平是本文要解決的問題。為了更準確評價覆蓋水平，本文引入了概率感知模型，把節點能感知到目標點的最小感知概率作為覆蓋水平的評價指標;為了方便確定節點的位置，算法把目標點所在區域劃分為若干正方形網格;算法通過網格掃描，不斷從中選擇最合適的網格作為下一個節點的放置位置，實現目標點的覆蓋。

1．1 概率感知模型

在二值感知模型中，當節點距離目標點的距離小于或等于感知半徑rs時，認為能感知覆蓋目標點;否則，不能感知覆蓋目標點。由于受到距離、障礙物等各種情況的影響，實際情況與二值感知模型并不一致。本文采用與實際情況較一致的概率感知模型［19］，把信號強弱轉化為感知概率。目標點gi被節點sk感知到的概率為p如式(1)所示:

參數α代表感知節點的物理特性，dki為感知節點和目標點之間的距離。由式(1)可知，目標點與感知節點之間的距離dki小于或等于rs時，節點對目標點的感知概率為 e－αdki，目標點距離節點越近，被感知的概率越大。當距離大于感知半徑rs時，目標節點不能被感知到。

本文假定當節點與目標點的距離小于或等于rs且感知概率不小于預定值β時，節點能感知到目標點，否則不能感知到，如式(2)所示，Ski為1表示節點能感知到目標點，否則不能。β取值越大，覆蓋水平越好;反之則越較差。

1．2 網格劃分

網格劃分是無線傳感器網絡節點部署中常用的一種方法，它把感興趣區域劃分為若干網格。網格可以有多種形狀，如正方形、六邊形、三角形等。目前網格劃分多應用于區域覆蓋的節點部署方法［20］中，把目標區域劃分為若干邊長相同的網格，網格頂點放置感知節點來監測感興趣區域。相同形狀的網格，網格邊長越大，使用的節點越少。但為了滿足節點間的覆蓋連通的要求，網格邊長不能過大。

受區域覆蓋中網格劃分的啟發，本文把網格劃分引入到目標點覆蓋的算法中。為了方便確定節點的位置，算法把目標點所在區域劃分為若干正方形網格，整個監測區域離散化為若干網格的集合。劃分網格的目的和在區域覆蓋中不同，算法把每個網格抽象為一個位置點。當網格邊長較小時，不同形狀的網格對結果影響較小;本文算法為中心式確定性部署，網格邊長可以取值很小。

本文假定目標區域為長方形，用等距的分別與長和寬平行的直線將長方形區域劃分為若干正方形網格。算法通過網格掃描，不斷從中選擇最合適的網格作為下一個節點的放置位置。

1．3 節點部署算法

在一個已知若干目標點的區域中，在每個目標點處放置一個感知節點能達到最好的覆蓋水平。但如果目標點密度較大且對目標點的覆蓋水平要求不高時，每個目標點處都放置一個節點是沒有必要的。針對這種情況，結合網格劃分的方法，本文提出了一種覆蓋算法，實現用最少的節點覆蓋所有目標點并達到預設的覆蓋水平，降低了成本。

節點對目標點的覆蓋水平可由概率感知模型中的感知概率下限β約束，β取值越大則覆蓋水平越好，反之則越差。

初始時，待覆蓋目標點集t為所有目標點的集合。逐行掃描所有的網格，選擇節點感知到目標點的個數最多的網格放置下一個節點，如式(3)所示，網格u作為下一個節點的放置位置。當放置了一個新的節點后，將能被它感知到的目標點從待覆蓋的目標點集中移出，以防止重復覆蓋。繼續逐行掃描所有網格，以同樣的方法選擇下一個放置感知節點的網格，并從待覆蓋目標點集合中移除新加節點感知到的目標點直到待覆蓋目標點集合為空。

在掃描網格選擇下一個放置節點的網格時，可能存在一個以上的網格，在這些網格處節點能感知到同樣最大數量的目標點。此時應選擇覆蓋性較好的網格，在被每個網格處的節點感知的目標點中，被感知概率值最小的目標點決定著整體覆蓋水平，如式(4)所示，ei決定著節點i的總體覆蓋水平。算法選擇目標點被感知概率最小值最大的網格，即網格q放置下一個節點，見式(5)。

算法描述如下:

①初始化:t:目標點集合，初始化為所有目標點;l:目標點被覆蓋標記，初始化為0;d:網格的邊長;a:整個區域長方形的長度;b:長方形區域的寬度;β:預設的感知概率下限值;grid(x，y):記錄當前節點能以不小于β感知到最多的未被覆蓋的目標點的網格;c:記錄grid(x，y)以不小于概率β感知到的目標點的個數;p:記錄grid(x，y)能以不小于概率β感知到的目標點中的感知概率的最小值;x:網格grid(x，y)所在的行號;y:網格grid(x，y)所在的列號;i:當前網格的行號，初始化為1;j:當前網格的列號，初始化為1。

②c1:grid(i，j)以不小于概率β感知到的目標點的個數;p1:grid(i，j)以不小于β感知到的目標點的感知概率的最小值;

③如果c1＞c或者(c1=c且p1＞p)繼續;否則轉⑤;

④c=c1;;p=p1;x=i;y=j

⑤j=j+1;如果 j＞b/d，繼續;否則轉②;

⑥i=i+1;j=1;如果 i＞a/d，繼續;否則，轉②;

⑦輸出網格所在的行號、列號(x，y)以及部署在該網格的節點能以不小于β感知到的目標點集合t1;t=t－t1;如果t為空，結束;否則轉②。

其中，第二步計算當前網格處節點以不小于概率β感知到的待覆蓋目標點的個數c1及其中感知概率的最小值p1。根據節點到各目標點的歐式距離，由式(1)可計算出節點對各目標點的感知概率。與已掃描的以不小于概率β感知到的待覆蓋目標點的個數的最大值c比較，若c1＞c，說明當前網格更適合選為下一個放置節點的位置，把當前網格記錄為最優網格，如第四步所示。如果c1=c，即當前網格與已掃描的最優網格能以不小于概率β感知到同樣數目的最多的待覆蓋目標點，如果p1大于當前以不小于概率β感知到的目標點中的感知概率的最小值p，則當前網格比當前最優網格更適合作為下一個節點的放置位置。逐行掃描所有網格，選出最優的網格放置新節點。把節點以不小于概率β感知到的待覆蓋目標點從待覆蓋目標點集中移出。重復執行，直到待覆蓋目標點集合為空。

2 實驗結果及分析

為了驗證算法的有效性，設計了兩組仿真實驗分別測試網格邊長和感知概率下限β對節點部署的影響。本文假定實驗均在100 m×100 m的區域內，采用隨機方式分別產生10、20個目標點。同時，假定所有的傳感器節點具有同樣的感知半徑20 m，即式(1)中rs等于20 m，概率感知模型中的α取固定值0．04。考慮到實際情況，目標點的位置坐標精確到0．1 m。

2．1 實驗一:不同網格邊長

分別在網格邊長為0．02 m、0．1 m、1 m 三種情況下進行仿真實驗，為了不引入其它影響因素，該仿真試驗中的β值均取0。圖1、圖2分別為目標點為10、20時的實驗結果。

圖1、圖2中，藍色圓圈代表目標點位置，綠色的點代表節點位置，綠色的圓代表節點的感知范圍，綠點后面的數字表示該節點放置的先后次序。由圖可知，網格邊長grid_side取值越小，節點的放置位置越精確。圖1(c)中節點4明顯比圖1(a)中的節點4放置的位置更精確，圖2(c)中的節點7比圖2(a)中的節點6位置更精確。當網格處的節點能覆蓋相同最大數目的目標點時，如圖2(c)中的4以及4周圍的若干網格，放在它們處的節點均能感知到同樣的最多的兩個目標點，但網格4處，最小感知概率值最大，具有最好的覆蓋性，所以網格4是放置下一個節點的最優位置。

圖1 不同網格邊長下傳感器節點的位置及覆蓋情況(目標點個數為10)

圖2 不同網格邊長下傳感器節點的位置及覆蓋情況(目標點個數為20)

2．2 實驗二:不同感知概率下限

該實驗中，目標點取實驗一中的20個目標點、網格邊長均為0．1米。在這種情況下測試感知概率下限β 分別取 0．2、0．4、0．6、0．8 時，對節點數量及位置的影響。實驗結果如圖3 所示。

圖3 β不同取值時節點個數及位置

由圖可知，當β為0．2和0．4時，所需節點個數及節點位置均相同。這是因為由式(1)可計算出當節點與目標點距離為rs時，感知概率值為0．44，0．2和0．4 均小于0．44，β 取值0．2 和0．4 時，距離節點小于rs的目標點能被感知到，所以結果相同。而當β遞增至0．6和0．8時，感知概率下限的增加要求目標點與節點有更小的距離才能被感知，一部分原來能被感知到的目標點將不能被感知，所以需要部署更多的節點。如圖3(b)、3(c)所示。

目標點個數固定為10和20時，本文分別隨機產生了10組目標點集，計算不同的β值下所需的節點個數。圖4顯示了β取不同值時所需節點個數的平均值。由圖4可知，覆蓋相同的目標點，β取值越大，需要的節點個數越多。β取1時，每個目標點處須放置一個節點，達到最好的覆蓋水平。目標點個數越多時，隨著β的增加需增加更多的節點。

圖4 不同β值下覆蓋相同的目標點所需的節點個數

3 結論

本文提出了一種基于網格掃描的實現目標點覆蓋的確定性節點部署方法。算法首先把目標區域劃分為若干網格，掃描所有網格，從中選擇最佳的網格作為下一個傳感器節點的放置位置，直到所有的目標點都被覆蓋。本文引入概率感知模型，把節點能感知到目標點的最小感知概率值作為約束總體覆蓋水平的指標。把節點能感知到目標點的個數及對目標點的最小感知概率值作為網格的評價標準。本文對網格邊長和感知概率下限取不同數值時，分別進行仿真實驗。實驗結果表明，網格邊長越小，節點放置位置越精確;當網格邊長不變時，感知概率下限取值越大，所需的節點越多，覆蓋性能越好。給定感知概率下限，算法能使用最少的節點實現目標覆蓋，達到較好的總體覆蓋水平且能計算出較優的節點部署位置。

本文提出的算法也存在一些不足之處，本文只考慮了對目標點的覆蓋問題，節點間的連通問題是下一步需要解決的問題。此外，每個節點覆蓋目標點的個數不均勻，在不增加算法所需的最少節點個數的前提下，調整節點的位置達到較好的均勻性可以延長網絡生命周期。

［1］ 任豐原，黃海寧，林闖．無線傳感器網絡［J］．軟件學報，2003，14(7):1282－1291．

［2］ Jennifer Yick，Biswanath Mukherjee，Dipak Ghosal．Wireless Sensor Network Survey［J］．IEEE Computer Networks，2008，52(12):2292－2330．

［3］ 傅質馨，徐志良，黃成．無線傳感器網絡節點部署問題研究［J］．傳感器與微系統，2008，14(7):1282－1291．

［4］ Dhillon S S，Chakrabarty K．Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks［C］//IEEE Wireless Communications and Networking Conference(WCNC－03)，2003:1609－1614．

［5］ 何欣，桂小林，安健．面向目標覆蓋的無線傳感器網絡確定性部署方法［J］．西安交通大學學報，2010，44(6):6－10．

［6］ Ka-Shun Hung，King-Shan Lui．On Perimeter Coverage in Wireless Sensor Networks［J］．IEEE Transactions on Wireless Communications，2010，9(7):2156－2164．

［7］ 秦寧寧，蓋祎，張林，等．Voronoi圖在無線傳感器網絡柵欄覆蓋中的應用研究［J］．計算機應用研究，2008，25(3):863－865．

［8］ 劉麗萍，王智，孫優賢．無線傳感器網絡部署及其覆蓋問題研究［J］．電子與信息學報，2006，28(9):1752－1757．

［9］ Yi Zou，Krishnendu Chakrabarty．A Distributed Coverage and Connectivity Centric Technique for Selecting Active Nodes in Wireless Sensor Networks［J］．IEEE Transactions on Computers，2005，54(8):978－991．

［10］ Zhang H，Hou J C．Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］．AdHoc＆Sensor Networks，2005，1(1－2):89－124．

［11］林祝亮，馮遠靜，俞立．無線傳感器網絡覆蓋的粒子進化優化策略研究［J］．傳感技術學報，2009，22(6):873－877．

［12］李明，石為人．異構無線傳感器網絡中基于模擬退火算法的成本最優部署機制［J］．傳感技術學報，2010，23(6):855－858．

［13］ Yan Ruoyu，Zheng Qinhua．Using Renyi Cross Entropy to Analyze Traffic Matrix and DetectDdoS Attacks［J］．Information Technology Journal，2009，8(8):1180－1188．

［14］ Anukool L，Mark C，Christophe D．Mining Anomalies Using Traffic Feature Distributions［C］//Proceedings of Special Interest Group on Data Communication Conference，USA:ACM，2005:217－228．

［15］ George N，Vyas S，David G．An Empirical Evaluation of Entropy-Based Traffic Anomaly Detection［C］//Proceedings of Internet Measurement Conference，USA:ACM，2008:151－156．

［16］ Qin Tao，Guan Xiaohong，Li Wei．Dynamic Features Measurement and Analysis for Large-scale Networks［C］//Proceedings of International Conference on Communications，USA:IEEE，2008:212－216．

［17］ Xingfa Shen，Jiming Chen，Youxian Sun．Grid Scan:A Simple and Effective Approach for Coverage Issue in Wireless Sensor Networks［C］//IEEE International conference on Communications，2006:3480－3484．

［18］ Xiaoyu Chu，Harish Sethu．A New Distributed Algorithm for Even Coverage and Improved Lifetime in a Sensor Network［C］//IEEE INFCOM，2009:361－369．

［19］ Hekmat R，van Mieghem P．Connectivity in Wireless Ad-Hoc Networks with a Log-Normal Radio Model［J］．Mobile Networks and Applications，2006，11(3):351－360．

［20］ Xueqing Wang，Shuxue Zhang．Comparison of Several Sensor Deployments in Wireless Sensor Networks［C］//International Conference on E-Health Networking Digital Ecosystems and Technologies，2010:236－239．