基于聚類的二階段無線傳感網(wǎng)絡SweepCoverage機制.doc

基于聚類的二階段無線傳感網(wǎng)絡SweepCoverage機制 近年來，無線傳感網(wǎng)絡(WSNs)備受關注，而覆蓋問題成為WSN中的一個熱點問題。在一些特定的場景中，如巡回檢查中，我們更關注事件頻發(fā)點POI(PointofInterest)的覆蓋問題1。在這些場景中，采用移動傳感節(jié)點周期性的訪問POIs并完成對信息的采集。 為了解決這類問題，文獻1中首次將SweepCoverage的概念引入WSN中，同時定義了SweepCoverage問題：在POI覆蓋周期的約束下，如何以更少的移動節(jié)點覆蓋POIs，降低網(wǎng)絡覆蓋成本。WeifangCheng等論證SweepCoverage是NP難題。文獻1中提出了集中式的CSWEEP算法和分布式DSWEEP算法。CSWEEP算法簡便易行，但要求POI覆蓋周期相同，在大規(guī)模網(wǎng)絡中并不適用。DSWEEP算法更加靈活，但移動節(jié)點總是傾向于訪問距離自身較近的POIs，難以確保信息的及時采集。另外，文獻3提出多移動傳感節(jié)點協(xié)調覆蓋POIs的MinExpand算法，該算法結構簡單、速度快，但是該算法無法對數(shù)據(jù)延遲的考慮。文獻5同時考慮POI的感應和傳輸延遲限制，但并沒有考慮使用移動節(jié)點的數(shù)量，不適用于較大規(guī)模的網(wǎng)絡。 鑒于目前SweepCoverage中存在的不足與缺陷，本文同時考慮POIs感應延遲限制和傳感節(jié)點的傳輸延時限制，形成二階段SweepCoverage機制，通過對移動傳感節(jié)點的有效控制來解決無線傳感器網(wǎng)絡中的SweepCoverage問題。 2基于聚類的二階段SweepCoverage機制描述 (Descriptionoftwo-stagesweepcoverage mechanismbasedonclustering) 2.1網(wǎng)絡部署 為了模擬真實場景，假定POIs在監(jiān)測區(qū)隨機分布。在該場景下，同時考慮移動節(jié)點對POIs的覆蓋和節(jié)點收集到的數(shù)據(jù)實效性和有用性形成一個二階段的SweepCoverage機制：數(shù)據(jù)感知階段，通過減法聚類改進的K-means對POIs進行分簇，再用遺傳算法對各簇中的POIs進行路徑規(guī)劃，得到MobileSweep(感知節(jié)點)的較優(yōu)移動路徑，從而以較少的MobileSweep覆蓋所有POIs；數(shù)據(jù)傳輸階段，由MobileSink(傳輸節(jié)點)收集MiniSink(存儲節(jié)點)處的信息并將其送回Sink。此處MobileSink的訪問路徑問題可以規(guī)約成MobileSweep的訪問路徑問題。 2.2相關變量定義 對于該機制中用到的變量做如表1解釋。 表1定義 Tab.1Definition 符號定義 TiPOI覆蓋周期 vsMobileSweep的速度 mPOIs數(shù)量 di,jPOIpi與pj之間的歐幾里得距離 vfMobileSink的速度 TfMiniSink的覆蓋周期 3具體算法實現(xiàn)(Specificalgorithmimplementation) 3.1POIs分簇 在POIs隨機分布于監(jiān)測區(qū)中，考慮到MobileSweep路徑的長度，對POIs進行分簇，使同簇中POIs距離較近，不同簇中POIs相距較遠。為了操作簡便，采用K-means分簇。針對K值無法確定的問題，運用減法聚類進行對其改進，形成分簇算法：基于減法聚類的K-means。算法具體步驟如下： POIs分簇算法 輸入：POIs坐標(xi,yi)集合，形成樣本空間。 輸出：K個分簇，及每個簇中的POIs集合。 算法過程： 運用減法聚類確定K值，并找出初始聚類中心集合C。 在步驟的基礎上執(zhí)行K-means。 重新計算聚類中心Z。若聚類準則函數(shù)不收斂收斂轉到步驟。 輸出結果。 通過減法聚類，不僅得到較為合理的K值，同時確定了初始聚類中心，減少K-means的迭代次數(shù)，使算法效率得到提高。 3.2MobileSweep與MobileSink訪問路徑規(guī)劃 MobileSweep周期性的覆蓋POIs，它的路徑由訪問路徑中的POIs連接組成。為了尋找簇內POIs最優(yōu)訪問路徑，本文采用遺傳算法。 (1)MobileSweep訪問路徑算法實現(xiàn) MobileSweep訪問路徑規(guī)劃算法 輸入：K個簇中的POIs坐標(xi,yi)及控制參數(shù)：種群規(guī)模N和終止進化代數(shù)T。 輸出：K條訪問路徑L=l1,l2,lk及路徑長度D=d1,d2,dk。 算法過程： 根據(jù)POIs的位置坐標計算每個簇中POIs的距離矩陣Dis。 為每個簇隨機生成初始種群C1,C2,Cn，計算各個體的適應度值1/dis(Ci)，并按適應度值對個體進行排序。初始終止進化代數(shù)計數(shù)器gen=0。 計算選擇概率p。 根據(jù)步驟，采用“輪盤賭”復制下一代個體。 交叉操作。 變異操作。 gen=gen+1。 如果genT，則轉到步驟；若滿足終止條件，算法結束，輸出K條路徑并保存K條路徑的長度。 (2)最少MobileSweep數(shù) 假設K條路徑集合為L=l1,l2,lk，其對應的長度為D=d1,d2,dk。 已知MobileSweep的速度為vs，第i條遍歷路徑上的POI的最小覆蓋周期為，則第i條路徑上的MobileSweep數(shù)為： (1) 那么，K條路徑MobileSweep的總量為： (2) 其中，第i條路徑上的移動節(jié)點數(shù)為muni，那么SweepCoverage機制中的總節(jié)點數(shù)為mun*。由公式(2)可知，影響mun*大小的因素有兩個di和vs，由于移動節(jié)點勻速運動，本文中，我們只考慮路徑di長度對最小移動節(jié)點數(shù)的影響。 3.3MobileSink訪問路徑規(guī)劃 數(shù)據(jù)傳輸階段，MobileSink的路徑和感知階段POIs的路徑相似，但是考慮到聚類之后，簇的個數(shù)遠小于POIs數(shù)，因此在設計MobileSink訪問路徑時，直接運用遺傳算法尋求MobileSink的最優(yōu)訪問路徑。 4實驗(Experiment) 4.1試驗設置 假設監(jiān)測區(qū)域大小為5005008，匯聚節(jié)點設置在區(qū)域邊界，即在仿真區(qū)域的(0,0)處。對POI數(shù)量從50到150不等隨機分布在監(jiān)測區(qū)域的場景進行試驗。POI的通信范圍為2m，MobileSweep、MobileSink有足夠大的數(shù)據(jù)傳輸帶寬，可以在較短的時間內完成數(shù)據(jù)的感知和相互之間的數(shù)據(jù)傳輸。同時假設MobileSweep、MiniSink、MobileSink數(shù)據(jù)緩沖區(qū)足夠大，且傳感節(jié)點的能量充足。根據(jù)最少移動節(jié)點數(shù)算法，假設所有簇中的最小覆蓋周期相等，所有POI的覆蓋周期均相等且等于簇中最小的POIs的覆蓋周期。 4.2基于減法聚類的K-means分析 當監(jiān)測區(qū)域中POIs個數(shù)為80時，分別運用原始K-means聚和基于減法聚類的K-means對POIs分簇。從圖1可以看出，運用減法聚類改進的K-means分簇后，簇內POIs緊密度更高，算法有更強的優(yōu)越性。 圖1簇中POIs緊密度對比 Fig.1Thepareofclosenessofclustering 4.3MobileSweep及MobileSink路徑的生成 MobileSweep訪問路徑和MobileSink路徑如圖2所示。 圖2MobileSweep及MobileSink路徑 Fig.2ThepathofMobileSweepandMobileSink 4.4參數(shù)設置對MobileSweep數(shù)量的影響 (1)POIs分布密度對MobileSweep數(shù)目的影響 設置MobileSweep速度vs=3m/s，最小覆蓋周期Ts=100s，如圖3所示，在相同條件下，本文算法所需MobileSweep數(shù)量明顯少于MinExpand。 圖3區(qū)域中POI密度對MobileSweep的影響 Fig.3ThedensityofPOIinfluencedonMobileSweep (2)移動速度對節(jié)點數(shù)目的影響 增加節(jié)點的移動速度，會在一定程度上影響所需的節(jié)點數(shù)。當POI的覆蓋周期Ts=100s時，設置MobileSweep的速度為vs=3m/s和vs=5m/s。從圖4可以看出，隨著MobileSweep速度的增加，所需MobileSweep的數(shù)量顯著下降。通常情況下，MobileSink的功率要遠遠大于MobileSweep，因此速度也比較大。當相同覆蓋周期下，設置MobileSink的速度為vf=10m/s和vf=15m/s。隨著MobileSink速度的增加，所需MobileSink數(shù)目增加平穩(wěn)，且增幅較小。因此速度對MobileSink的影響較小。 圖4速度對移動節(jié)點數(shù)量的影響 Fig.4Theinfluenceofspeedonmobilesensors 5結論(Conclusion) 本文在原來完全動態(tài)的網(wǎng)絡模型中加入靜止MiniSink形成一個二階段網(wǎng)絡SweepCoverage機制。實驗證明，運用該機制，可以有效防止感應延時和傳輸延時，并且一定程度上減少了移動節(jié)點數(shù)目，降低了無線網(wǎng)絡覆蓋成本。由于對于真實場景中的一些情況欠缺考慮，下一步，計劃在真實的場景中進行驗證本文提出的覆蓋機制，同時考慮有無Sink節(jié)點對數(shù)據(jù)傳輸階段的影響，從而對SweepCoverage進行完善。 參考文獻(References) 1WeifangCheng,etal.SweepcoveragewithmobilesensorsJ.ParallelandDistributedProcessing,xx.IPDPSxx.IEEEInternationalSymposiumon,xx:1-9. 2MinXi,etal.Runtopotential:SweepcoverageinwirelesssensorworksJ.InternationalConferenceonParallelProcessing,xx:50-57. 3JunzhaoDu,etal.OnsweepcoveragewithminimummobilesensorsJ.InternationalConferenceonParallelandDistributedSystems,xx:283-290. 4ZhenyaZhang,etal.MTSPbasedsolutionforminimummobilenodenumberprobleminsweepconvergeofwirelesssensorworkJ.InternationalConferenceonComputerScienceandNetworkTechnology,xx:1827-1830. 5DongZhao,HuadongMa,LiangLiu.MobileSensorSchedulingforTimelySweepCoverageJ.WirelessCommunicationsandNetworkingConference,xx:1771-1776. 6BarunGorain,ParthaSarathiMandal.PointandAreaSweepCoverageinWirelessSensorNetworksJ.Modeling&OptimizationinMobile,AdHoc&WirelessNetworks,xx:140-145. 7ShuL,etal.AsweepcoverageschemebasedonvehicleroutingproblemJ.Telkomnika,xx,11(4):2029. 8林鋒,王偉,周激流.MASC:一種基于移動輔助節(jié)點的SweepCoverage機制J.四川大學學報(工