成璐

摘 要：作為WSN網(wǎng)絡(luò)覆蓋中的熱點(diǎn)問(wèn)題之一，Sweep Coverage旨在以較少的傳感節(jié)點(diǎn)覆蓋所有的興趣點(diǎn)（POIs）。針對(duì)現(xiàn)有Sweep Coverage機(jī)制中存在的不足，本文提出一種基于聚類(lèi)的二階段網(wǎng)絡(luò)覆蓋機(jī)制：數(shù)據(jù)感知階段，采用通過(guò)減法聚類(lèi)改進(jìn)的K-means算法對(duì)POIs分簇，并尋求各簇中訪問(wèn)POIs的近似最優(yōu)路徑；數(shù)據(jù)傳輸階段，尋求數(shù)據(jù)傳輸節(jié)點(diǎn)的最優(yōu)訪問(wèn)路徑。實(shí)驗(yàn)表明，在相同網(wǎng)絡(luò)場(chǎng)景下，本文提出的二階段網(wǎng)絡(luò)覆蓋機(jī)制有較好的效果。

關(guān)鍵詞：Sweep Coverage；數(shù)據(jù)感知；數(shù)據(jù)傳輸；K-means

中圖分類(lèi)號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

近年來(lái)，無(wú)線傳感網(wǎng)絡(luò)（WSNs）備受關(guān)注，而覆蓋問(wèn)題成為WSN中的一個(gè)熱點(diǎn)問(wèn)題。在一些特定的場(chǎng)景中，如巡回檢查中，我們更關(guān)注事件頻發(fā)點(diǎn)POI（Point of Interest）的覆蓋問(wèn)題[1]。在這些場(chǎng)景中，采用移動(dòng)傳感節(jié)點(diǎn)周期性的訪問(wèn)POIs并完成對(duì)信息的采集。

為了解決這類(lèi)問(wèn)題，文獻(xiàn)[1]中首次將Sweep Coverage的概念引入WSN中，同時(shí)定義了Sweep Coverage問(wèn)題：在POI覆蓋周期的約束下，如何以更少的移動(dòng)節(jié)點(diǎn)覆蓋POIs，降低網(wǎng)絡(luò)覆蓋成本。Weifang Cheng等論證Sweep Coverage是NP難題。文獻(xiàn)[1]中提出了集中式的CSWEEP算法和分布式DSWEEP算法。CSWEEP算法簡(jiǎn)便易行，但要求POI覆蓋周期相同，在大規(guī)模網(wǎng)絡(luò)中并不適用。DSWEEP算法更加靈活，但移動(dòng)節(jié)點(diǎn)總是傾向于訪問(wèn)距離自身較近的POIs，難以確保信息的及時(shí)采集。另外，文獻(xiàn)[3]提出多移動(dòng)傳感節(jié)點(diǎn)協(xié)調(diào)覆蓋POIs的MinExpand算法，該算法結(jié)構(gòu)簡(jiǎn)單、速度快，但是該算法無(wú)法對(duì)數(shù)據(jù)延遲的考慮。文獻(xiàn)[5]同時(shí)考慮POI的感應(yīng)和傳輸延遲限制，但并沒(méi)有考慮使用移動(dòng)節(jié)點(diǎn)的數(shù)量，不適用于較大規(guī)模的網(wǎng)絡(luò)。

鑒于目前Sweep Coverage中存在的不足與缺陷，本文同時(shí)考慮POIs感應(yīng)延遲限制和傳感節(jié)點(diǎn)的傳輸延時(shí)限制，形成二階段Sweep Coverage機(jī)制，通過(guò)對(duì)移動(dòng)傳感節(jié)點(diǎn)的有效控制來(lái)解決無(wú)線傳感器網(wǎng)絡(luò)中的Sweep Coverage問(wèn)題。

2 基于聚類(lèi)的二階段Sweep Coverage機(jī)制描述

（Description of two-stage sweep coverage

mechanism based on clustering）

2.1 網(wǎng)絡(luò)部署

為了模擬真實(shí)場(chǎng)景，假定POIs在監(jiān)測(cè)區(qū)隨機(jī)分布。在該場(chǎng)景下，同時(shí)考慮移動(dòng)節(jié)點(diǎn)對(duì)POIs的覆蓋和節(jié)點(diǎn)收集到的數(shù)據(jù)實(shí)效性和有用性形成一個(gè)二階段的Sweep Coverage機(jī)制：數(shù)據(jù)感知階段，通過(guò)減法聚類(lèi)改進(jìn)的K-means對(duì)POIs進(jìn)行分簇，再用遺傳算法對(duì)各簇中的POIs進(jìn)行路徑規(guī)劃，得到MobileSweep（感知節(jié)點(diǎn)）的較優(yōu)移動(dòng)路徑，從而以較少的MobileSweep覆蓋所有POIs；數(shù)據(jù)傳輸階段，由MobileSink（傳輸節(jié)點(diǎn)）收集MiniSink（存儲(chǔ)節(jié)點(diǎn)）處的信息并將其送回Sink。此處MobileSink的訪問(wèn)路徑問(wèn)題可以規(guī)約成MobileSweep的訪問(wèn)路徑問(wèn)題。

3.3 MobileSink訪問(wèn)路徑規(guī)劃

數(shù)據(jù)傳輸階段，MobileSink的路徑和感知階段POIs的路徑相似，但是考慮到聚類(lèi)之后，簇的個(gè)數(shù)遠(yuǎn)小于POIs數(shù)，因此在設(shè)計(jì)MobileSink訪問(wèn)路徑時(shí)，直接運(yùn)用遺傳算法尋求MobileSink的最優(yōu)訪問(wèn)路徑。

4 實(shí)驗(yàn) （Experiment）

4.1 試驗(yàn)設(shè)置

假設(shè)監(jiān)測(cè)區(qū)域大小為500×500[8]，匯聚節(jié)點(diǎn)設(shè)置在區(qū)域邊界，即在仿真區(qū)域的（0，0）處。對(duì)POI數(shù)量從50到150不等隨機(jī)分布在監(jiān)測(cè)區(qū)域的場(chǎng)景進(jìn)行試驗(yàn)。POI的通信范圍為2m，MobileSweep、MobileSink有足夠大的數(shù)據(jù)傳輸帶寬，可以在較短的時(shí)間內(nèi)完成數(shù)據(jù)的感知和相互之間的數(shù)據(jù)傳輸。同時(shí)假設(shè)MobileSweep、MiniSink、MobileSink數(shù)據(jù)緩沖區(qū)足夠大，且傳感節(jié)點(diǎn)的能量充足。根據(jù)最少移動(dòng)節(jié)點(diǎn)數(shù)算法，假設(shè)所有簇中的最小覆蓋周期相等，所有POI的覆蓋周期均相等且等于簇中最小的POIs的覆蓋周期。

4.2 基于減法聚類(lèi)的K-means分析

當(dāng)監(jiān)測(cè)區(qū)域中POIs個(gè)數(shù)為80時(shí)，分別運(yùn)用原始K-means聚和基于減法聚類(lèi)的K-means對(duì)POIs分簇。從圖1可以看出，運(yùn)用減法聚類(lèi)改進(jìn)的K-means分簇后，簇內(nèi)POIs緊密度更高，算法有更強(qiáng)的優(yōu)越性。

4.3 MobileSweep及MobileSink路徑的生成

MobileSweep訪問(wèn)路徑和MobileSink路徑如圖2所示。

4.4 參數(shù)設(shè)置對(duì)MobileSweep數(shù)量的影響

（1）POIs分布密度對(duì)MobileSweep數(shù)目的影響

設(shè)置MobileSweep速度vs=3m/s，最小覆蓋周期Ts=100s，如圖3所示，在相同條件下，本文算法所需MobileSweep數(shù)量明顯少于MinExpand。

（2）移動(dòng)速度對(duì)節(jié)點(diǎn)數(shù)目的影響

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

5 結(jié)論（Conclusion）

本文在原來(lái)完全動(dòng)態(tài)的網(wǎng)絡(luò)模型中加入靜止MiniSink形成一個(gè)二階段網(wǎng)絡(luò)Sweep Coverage機(jī)制。實(shí)驗(yàn)證明，運(yùn)用該機(jī)制，可以有效防止感應(yīng)延時(shí)和傳輸延時(shí)，并且一定程度上減少了移動(dòng)節(jié)點(diǎn)數(shù)目，降低了無(wú)線網(wǎng)絡(luò)覆蓋成本。由于對(duì)于真實(shí)場(chǎng)景中的一些情況欠缺考慮，下一步，計(jì)劃在真實(shí)的場(chǎng)景中進(jìn)行驗(yàn)證本文提出的覆蓋機(jī)制，同時(shí)考慮有無(wú)Sink節(jié)點(diǎn)對(duì)數(shù)據(jù)傳輸階段的影響，從而對(duì)Sweep Coverage進(jìn)行完善。

參考文獻(xiàn)（References）

[1] Weifang Cheng，et al.Sweep coverage with mobile sensors[J].Parallel and Distributed Processing，2008.IPDPS 2008.IEEE International Symposium on，2008：1-9.

[2] Min Xi，et al.Run to potential：Sweep coverage in wireless sensor networks[J].International Conference on Parallel Processing，2009：50-57.

[3] Junzhao Du，et al.On sweep coverage with minimum mobile sensors[J].International Conference on 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 Sensor Scheduling for Timely Sweep Coverage[J].Wireless Communications and Networking Conference，2012：1771-1776.

[6] Barun Gorain，Partha Sarathi Mandal.Point and Area Sweep Coverage in Wireless Sensor Networks[J].Modeling & Optimization in Mobile，Ad Hoc & Wireless Networks，2013：140-145.

[7] Shu L，et al.A sweep coverage scheme based on vehicle routing problem[J].Telkomnika，2013，11（4）：2029.

[8] 林鋒，王偉，周激流.MASC：一種基于移動(dòng)輔助節(jié)點(diǎn)的Sweep Coverage機(jī)制[J].四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2010，06：119-125；132.

[9] 劉晨光，林鋒，周激流.一種基于A-means聚類(lèi)算法的Sweep Coverage機(jī)制[J].計(jì)算機(jī)應(yīng)用研究，2012，03：1051-1053.

[10] 李小康，林峰，周激流.一種Sweep Coverage問(wèn)題的插入啟發(fā)式算法[J].四川大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，01：74-78.

作者簡(jiǎn)介：

成 璐（1988-），女，碩士，助教.研究領(lǐng)域：無(wú)線傳感網(wǎng)絡(luò)，人工智能.