技術報告基于聚類的二階段無線傳感網絡Sweep Coverage機制

1、計劃類別 項目編號 項目技術報告課題名稱 項目主持人 承擔單位 題目：基于聚類的二階段無線傳感網絡Sweep Coverage機制作為WSN網絡覆蓋中的熱點問題之一，Sweep Coverage旨在以較少的傳感節(jié)點覆蓋所有的興趣點（POIs）。針對現(xiàn)有Sweep Coverage機制中存在的不足，本文提出一種基于聚類的二階段網絡覆蓋機制：數據感知階段，采用通過減法聚類改進的K-means算法對POIs分簇，并尋求各簇中訪問POIs的近似最優(yōu)路徑；數據傳輸階段，尋求數據傳輸節(jié)點的最優(yōu)訪問路徑。實驗表明，在相同網絡場景下，本文提出的二階段網絡覆蓋機制有較好的效果。關鍵詞：Sweep Coverag

2、e；數據感知；數據傳輸；K-means1 引言（Introduction）近年來，無線傳感網絡（WSNs）備受關注，而覆蓋問題成為WSN中的一個熱點問題。在一些特定的場景中，如巡回檢查中，我們更關注事件頻發(fā)點POI（Point of Interest）的覆蓋問題1。在這些場景中，采用移動傳感節(jié)點周期性的訪問POIs并完成對信息的采集。為了解決這類問題，文獻1中首次將Sweep Coverage的概念引入WSN中，同時定義了Sweep Coverage問題：在POI覆蓋周期的約束下，如何以更少的移動節(jié)點覆蓋POIs，降低網絡覆蓋成本。Weifang Cheng等論證Sweep Coverage是

3、NP難題。文獻1中提出了集中式的CSWEEP算法和分布式DSWEEP算法。CSWEEP算法簡便易行，但要求POI覆蓋周期相同，在大規(guī)模網絡中并不適用。DSWEEP算法更加靈活，但移動節(jié)點總是傾向于訪問距離自身較近的POIs，難以確保信息的及時采集。另外，文獻3提出多移動傳感節(jié)點協(xié)調覆蓋POIs的MinExpand算法，該算法結構簡單、速度快，但是該算法無法對數據延遲的考慮。文獻5同時考慮POI的感應和傳輸延遲限制，但并沒有考慮使用移動節(jié)點的數量，不適用于較大規(guī)模的網絡。鑒于目前Sweep Coverage中存在的不足與缺陷，本文同時考慮POIs感應延遲限制和傳感節(jié)點的傳輸延時限制，形成二階段S

4、weep Coverage機制，通過對移動傳感節(jié)點的有效控制來解決無線傳感器網絡中的Sweep Coverage問題。2 基于聚類的二階段Sweep Coverage機制描述（Description of two-stage sweep coveragemechanism based on clustering）2.1 網絡部署為了模擬真實場景，假定POIs在監(jiān)測區(qū)隨機分布。在該場景下，同時考慮移動節(jié)點對POIs的覆蓋和節(jié)點收集到的數據實效性和有用性形成一個二階段的Sweep Coverage機制：數據感知階段，通過減法聚類改進的K-means對POIs進行分簇，再用遺傳算法對各簇中的POIs

5、進行路徑規(guī)劃，得到MobileSweep（感知節(jié)點）的較優(yōu)移動路徑，從而以較少的MobileSweep覆蓋所有POIs；數據傳輸階段，由MobileSink（傳輸節(jié)點）收集MiniSink（存儲節(jié)點）處的信息并將其送回Sink。此處MobileSink的訪問路徑問題可以規(guī)約成MobileSweep的訪問路徑問題。3.3 MobileSink訪問路徑規(guī)劃數據傳輸階段，MobileSink的路徑和感知階段POIs的路徑相似，但是考慮到聚類之后，簇的個數遠小于POIs數，因此在設計MobileSink訪問路徑時，直接運用遺傳算法尋求MobileSink的最優(yōu)訪問路徑。4 實驗 （Experiment

6、）4.1 試驗設置假設監(jiān)測區(qū)域大小為5005008，匯聚節(jié)點設置在區(qū)域邊界，即在仿真區(qū)域的（0，0）處。對POI數量從50到150不等隨機分布在監(jiān)測區(qū)域的場景進行試驗。POI的通信范圍為2m，MobileSweep、MobileSink有足夠大的數據傳輸帶寬，可以在較短的時間內完成數據的感知和相互之間的數據傳輸。同時假設MobileSweep、MiniSink、MobileSink數據緩沖區(qū)足夠大，且傳感節(jié)點的能量充足。根據最少移動節(jié)點數算法，假設所有簇中的最小覆蓋周期相等，所有POI的覆蓋周期均相等且等于簇中最小的POIs的覆蓋周期。4.2 基于減法聚類的K-means分析當監(jiān)測區(qū)域中POI

7、s個數為80時，分別運用原始K-means聚和基于減法聚類的K-means對POIs分簇。從圖1可以看出，運用減法聚類改進的K-means分簇后，簇內POIs緊密度更高，算法有更強的優(yōu)越性。4.3 MobileSweep及MobileSink路徑的生成MobileSweep訪問路徑和MobileSink路徑如圖2所示。4.4 參數設置對MobileSweep數量的影響（1）POIs分布密度對MobileSweep數目的影響設置MobileSweep速度vs=3m/s，最小覆蓋周期Ts=100s，如圖3所示，在相同條件下，本文算法所需MobileSweep數量明顯少于MinExpand。（2）移

8、動速度對節(jié)點數目的影響增加節(jié)點的移動速度，會在一定程度上影響所需的節(jié)點數。當POI的覆蓋周期Ts=100s時，設置MobileSweep的速度為vs=3m/s和vs=5m/s。從圖4可以看出，隨著MobileSweep速度的增加，所需MobileSweep的數量顯著下降。通常情況下，MobileSink的功率要遠遠大于MobileSweep，因此速度也比較大。當相同覆蓋周期下，設置MobileSink的速度為vf=10m/s和vf=15m/s。隨著MobileSink速度的增加，所需MobileSink數目增加平穩(wěn)，且增幅較小。因此速度對MobileSink的影響較小。 5 結論（Conclu

9、sion）本文在原來完全動態(tài)的網絡模型中加入靜止MiniSink形成一個二階段網絡Sweep Coverage機制。實驗證明，運用該機制，可以有效防止感應延時和傳輸延時，并且一定程度上減少了移動節(jié)點數目，降低了無線網絡覆蓋成本。由于對于真實場景中的一些情況欠缺考慮，下一步，計劃在真實的場景中進行驗證本文提出的覆蓋機制，同時考慮有無Sink節(jié)點對數據傳輸階段的影響，從而對Sweep Coverage進行完善。參考文獻（References）1 Weifang Cheng，et al.Sweep coverage with mobile sensorsJ.Parallel and Distribu

10、ted Processing，2008.IPDPS 2008.IEEE International Symposium on，2008：1-9.2 Min Xi，et al.Run to potential：Sweep coverage in wireless sensor networksJ.International Conference on Parallel Processing，2009：50-57.3 Junzhao Du，et al.On sweep coverage with minimum mobile sensorsJ.International Conference on

11、 Parallel and Distributed Systems，2010：283-290.4 Zhenya Zhang，et al.MTSP based solution for minimum mobile node number problem in sweep converge of wireless sensor network J.International Conference on Computer Science and Network Technology，2011：1827-1830.5 Dong Zhao，Huadong Ma，Liang Liu.Mobile Sen

12、sor Scheduling for Timely Sweep CoverageJ.Wireless Communications and Networking Conference，2012：1771-1776.6 Barun Gorain，Partha Sarathi Mandal.Point and Area Sweep Coverage in Wireless Sensor NetworksJ.Modeling & Optimization in Mobile，Ad Hoc & Wireless Networks，2013：140-145.7 Shu L，et al.A sweep coverage scheme based on vehicle routing problemJ.Telkomnika，2013，11（4）：2029.8 林鋒，王偉，周激流.MASC：一種基于移動輔助節(jié)點的S