論文(計算機工程)

1、WSN巡航覆蓋二階段TSP移動策略研究陳燕，張振亞，方潛生安徽省智能建筑重點實驗室，合肥，230022摘要：建筑環(huán)境中關(guān)于能效狀態(tài)的物理參數(shù)可以通過無線傳感器網(wǎng)絡(luò)中的無線傳感器節(jié)點進行監(jiān)測。為了減少系統(tǒng)成本以及降低系統(tǒng)復(fù)雜度，本文對無線傳感器網(wǎng)絡(luò)巡航覆蓋進行了研究。移動傳感器移動路徑規(guī)劃是巡航覆蓋中的一個重要的問題，本文對巡航覆蓋中移動傳感器的移動策略進行了研究，并提出了二階段TSP算法規(guī)劃移動傳感器的移動路徑。實驗結(jié)果表明該方法能夠得到較短較均衡的路徑。關(guān)鍵詞：WSN；巡航覆蓋；二階段TSPResearch on two-stage TSP Method for moving strateg

2、y of WSN sweep coverageCHEN Yan1, ZHANG Zhenya2, FANG Qiansheng21.Intelligent building, Anhui University of Architecture,Hefei;2.Key Laboratory of Intelligent Building, HefeiAbstract: Environment physical parameters about the energy efficiency status in building can be monitored with wireless sensor

3、 network with mobile node. To reduce the cost and complexity of wireless sensor network, sweep coverage in wsn is studied. The moving path planning for mobile sensors is an important problem, the moving strategy of mobile sensors is researched in the paper, and two-stage TSP method is proposed for m

4、oving path planning. Experimental results show that two-stage TSP method can get shorter and balanced moving path.Key words: WSN；sweep coverage; two-stage TSP1、引言建筑能效狀態(tài)可以用建筑能耗狀況以及諸如溫度、濕度、風(fēng)速、氣壓、空氣品質(zhì)等評估建筑能效必須的建筑環(huán)境物理量表示。建筑能效狀態(tài)監(jiān)測是建筑節(jié)能監(jiān)管、能效評估、能效審計實施的重要環(huán)節(jié)。由于建筑空間結(jié)構(gòu)功能繁復(fù)而復(fù)雜多變，集感知、通信乃至控制功能與一體的無線傳感器網(wǎng)絡(luò)1,2,3可以有效

5、應(yīng)用于建筑能效狀態(tài)監(jiān)測。無線傳感器網(wǎng)絡(luò)應(yīng)用于建筑能效狀態(tài)監(jiān)測時，需要使用無線節(jié)點對監(jiān)測區(qū)域內(nèi)的監(jiān)測點進行覆蓋以實現(xiàn)目標(biāo)物理量的采集。無線傳感器網(wǎng)絡(luò)地毯式覆蓋和柵欄覆蓋都可以實現(xiàn)建筑能效監(jiān)測。無線傳感器網(wǎng)絡(luò)地毯式覆蓋4-7是對監(jiān)測區(qū)域的整體連續(xù)覆蓋，柵欄覆蓋是對敏感位置的連續(xù)覆蓋。這兩種覆蓋計算具有時間連續(xù)性和空間連續(xù)性特點。而在以建筑能效狀態(tài)監(jiān)測為目標(biāo)的無線傳感器網(wǎng)絡(luò)應(yīng)用中，對監(jiān)測區(qū)域內(nèi)監(jiān)測點處目標(biāo)物理量的信息采集具有兩個顯著的特點：1）監(jiān)測點在空間中不是連續(xù)的；2）監(jiān)測點處需要感知的物理量不需要實時采集。這兩個特點使得在以建筑能效狀態(tài)監(jiān)測為目標(biāo)的無線傳感器網(wǎng)絡(luò)應(yīng)用中，無論是地毯式覆蓋還是柵欄

6、覆蓋都會造成傳感器信息處理能力的浪費。為提升傳感器節(jié)點的信息處理能力進而提升監(jiān)測系統(tǒng)的能效，可以使用移動節(jié)點8,9實現(xiàn)需要時刻時監(jiān)測點處目標(biāo)物理量的采集，即通過移動節(jié)點實現(xiàn)無線傳感器網(wǎng)絡(luò)對監(jiān)測區(qū)域內(nèi)監(jiān)測點的信息采集的動態(tài)覆蓋。無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋不僅可以顯著減少無線節(jié)點的數(shù)量，也可以實現(xiàn)監(jiān)測區(qū)域內(nèi)不適合靜態(tài)部署監(jiān)測節(jié)點處監(jiān)測點處的物理量的有效采集，具有很大的靈活性。無線傳感器網(wǎng)絡(luò)中采用移動傳感器進行數(shù)據(jù)采集的過程中，移動傳感器之間的能耗均衡性決定了整個網(wǎng)絡(luò)均衡性，同時移動傳感器能耗之間的差異決定了網(wǎng)絡(luò)壽命長短。與此同時，由于移動傳感器本身的成本較高，為了進一步減少系統(tǒng)成本、降低系統(tǒng)的復(fù)雜性以

7、及延長網(wǎng)絡(luò)壽命，此時必須合理規(guī)劃各個移動節(jié)點的興趣點訪問路徑，均衡各個移動傳感器的能量消耗。本文在定義了無線傳感器網(wǎng)絡(luò)巡航覆蓋的基礎(chǔ)上，定義了網(wǎng)絡(luò)均衡性問題并提出了解決網(wǎng)絡(luò)均衡性問題的方法。WSN巡航覆蓋模型在第二部分給出，第三部分提出了二階段TSP算法解決網(wǎng)絡(luò)均衡性問題，第四部分給出并討論了實驗結(jié)果，總結(jié)與研究展望在第五部分給出。2、無線傳感器網(wǎng)絡(luò)巡航覆蓋模型無線傳感器網(wǎng)絡(luò)可以有效應(yīng)用于動態(tài)環(huán)境中的信息感知過程的實現(xiàn)。設(shè)是監(jiān)測區(qū)域，是傳感器部署位置，即可以使用傳感器可以感知附近的目標(biāo)信息，稱是興趣點，同時，傳感器部署在稱作被覆蓋，簡稱被覆蓋。又設(shè)在無線傳感器網(wǎng)絡(luò)應(yīng)用中，信息采集過程需要在興趣

8、點位置周期性進行，。對，處的一次信息采集過程需要在T時刻內(nèi)完成且第k次信息采集過程需要在時刻前完成，稱是興趣點集P的最大訪問截止時刻。由于P中興趣點處的信息采集行為不需要連續(xù)發(fā)生，可以使用移動傳感器在每個興趣點截止時刻到來之前移動到目標(biāo)興趣點并完成信息采集任務(wù)。采用移動傳感器，一方面可以降低監(jiān)測系統(tǒng)中傳感器的部署數(shù)量，另一方面也可以減少傳感器的靜態(tài)部署對監(jiān)測區(qū)域內(nèi)空間使用的占用時間，同時，移動傳感器還適用于無法靜態(tài)部署傳感器的監(jiān)測區(qū)域中興趣點處信息的感知。設(shè)是興趣點集，是興趣點集P的最大訪問截止時刻，是第個移動傳感器節(jié)點在最大訪問截止時刻內(nèi)覆蓋的興趣點順序序列且，則是第個移動傳感器節(jié)點在最大訪

9、問截止時刻內(nèi)的移動路徑。移動傳感器在內(nèi)移動實現(xiàn)各興趣點目標(biāo)信息采集的過程是各興趣點被移動傳感器覆蓋的過程，特別的，對任意移動傳感器，若，且滿足命題2的要求則稱移動傳感器在最大訪問截止時刻內(nèi)對所有興趣點的一次有效巡航覆蓋。命題1：若是興趣點集的最大訪問截止時刻，則是移動傳感器節(jié)點的最小移動周期。#命題2：設(shè)是興趣點集，是興趣點、間的距離,是無線傳感器網(wǎng)全部移動傳感器節(jié)點集, 是的移動速度，,是興趣點集P的最大訪問截止時刻，是在最大訪問截止時刻內(nèi)巡航覆蓋移動路徑，則。#閾于移動傳感器的移動性能以及監(jiān)測區(qū)域中興趣點空間分布的特性，一般需要多個移動傳感器節(jié)點協(xié)作完成截至?xí)r間內(nèi)監(jiān)測區(qū)域中目標(biāo)興趣點的巡航

10、覆蓋。移動傳感器節(jié)點通過巡航覆蓋可以實現(xiàn)對興趣點集的周期性訪問。為確保這種周期性訪問的有效性，無線傳感器網(wǎng)絡(luò)需要對每個移動傳感器節(jié)點的移動、信息采集行為以及其它輔助行為（如移動節(jié)點同步操作）進行維持。設(shè)是興趣點集，是興趣點集P的最大訪問截止時刻，是系統(tǒng)維持移動傳感器節(jié)點從興趣點移動到興趣點付出的移動成本，是系統(tǒng)維持移動傳感器節(jié)點在興趣點處信息采集行為付出的信息采集成本，是系統(tǒng)維持移動傳感器節(jié)點在興趣點處其它行為付出的成本。又設(shè)是第個移動傳感器節(jié)點在一次有效巡航覆蓋過程中的移動路徑，顯然，故無線傳感器網(wǎng)絡(luò)維持第個移動傳感器節(jié)點的成本為=+。設(shè)是無線傳感器網(wǎng)全部移動傳感器節(jié)點集，則該無線傳感器網(wǎng)絡(luò)

11、維持一次有效巡航覆蓋的成本。命題3：一次低成本有效巡航覆蓋過程，每個興趣點被覆蓋且僅被覆蓋一次。#利用命題3的結(jié)論中明確路徑規(guī)劃中可以忽略,這里利用次有效巡航覆蓋的成本的表達式說明降低一次有效巡航覆蓋成本的關(guān)鍵指標(biāo)：移動節(jié)點數(shù)+路徑規(guī)劃。這兩個指標(biāo)之間也是相互制約的，較優(yōu)的路徑規(guī)劃可以減少移動節(jié)點數(shù)，對于固定的移動節(jié)點數(shù)，路徑規(guī)劃結(jié)果要滿足有效巡航覆蓋的條件。本文在移動節(jié)點數(shù)固定的情況下，優(yōu)化移動節(jié)點的訪問路徑在保證訪問路徑長度較短同時也要達到均衡性要求，得到的移動傳感器訪問路徑同時也可以驗證給定的移動節(jié)點數(shù)是否滿足有效巡航覆蓋條件。3、二階段TSP算法規(guī)劃均衡路徑負(fù)載均衡性是無線傳感器網(wǎng)絡(luò)中

12、的一個關(guān)鍵問題，在部署靜態(tài)傳感器節(jié)點的網(wǎng)絡(luò)中，通過優(yōu)化設(shè)計無線傳感器網(wǎng)絡(luò)路由協(xié)議解決網(wǎng)絡(luò)路由中的負(fù)載均衡問題。在完全移動傳感器網(wǎng)絡(luò)中，移動傳感器移動比通信及感知消耗更多的能量。一般情況下，移動成本比其它成本高很多。因此，規(guī)劃出m條負(fù)載均衡且移動距離最短的訪問路徑可以有效節(jié)省網(wǎng)絡(luò)能耗且延長網(wǎng)絡(luò)壽命。為了衡量網(wǎng)絡(luò)負(fù)載均衡性，我們引用了均衡度的概念。均衡度的意義在于評價移動節(jié)點間負(fù)載均衡性，本文中主要考慮移動距離，故將均衡度定義如下：其中為第個移動傳感器節(jié)點的移動距離，值能夠很好地表達各移動節(jié)點移動路徑均衡性。值越接0，表示每條路徑長度越接近。但是在無線傳感器巡航覆蓋中，由于以下兩種性質(zhì)導(dǎo)致移動節(jié)點

13、移動路徑不可能達完全的均衡即，（1）興趣點的分布不均勻性，以致興趣點之間距離大小不一；（2）優(yōu)化移動節(jié)點訪問路徑是一TSP（MTSP），這是典型的NP-Hard問題，很難得到最優(yōu)解，即在有限時間內(nèi)只能得到次優(yōu)移動路徑。盡管如此，的下界是存在的，設(shè)該下界值為（），當(dāng)時，移動節(jié)點的訪問路徑均衡度最小，即達到最佳均衡狀態(tài)。其中可通過實驗獲得。無線傳感器網(wǎng)絡(luò)巡航覆蓋中移動傳感器節(jié)點從各自起點出發(fā)訪問監(jiān)測區(qū)域中所有興趣點，每個興趣點在一個巡航覆蓋周期只能被一個移動節(jié)點訪問且只訪問一次。這是一MTSP，一般監(jiān)測區(qū)域興趣點較多，直觀地可以采用各種近似優(yōu)化算法如智能優(yōu)化算法得到次優(yōu)訪問路徑，目標(biāo)函數(shù)為各移動節(jié)

14、點移動路徑的總長度。而在實際應(yīng)用中往往對移動路徑均衡性有較高的要求。這種情況可將上述問題歸結(jié)為多目標(biāo)優(yōu)化問題，即在滿足各移動節(jié)點移動路徑總和最短的同時也要保證移動路徑的均衡性達到要求。對于這種問題一般地在目標(biāo)函數(shù)中添加均衡因素。對于監(jiān)測區(qū)域較大，興趣點很多的情況，這種方式無疑給已經(jīng)相當(dāng)復(fù)雜的問題帶來了更大的求解難度。同時由于算法需要同時處理兩個優(yōu)化目標(biāo)，且這個優(yōu)化目標(biāo)之間存在制約關(guān)系，很難協(xié)調(diào)二者得到較優(yōu)的結(jié)果，特別在問題規(guī)模較大的情況下，相比較只有一個目標(biāo)函數(shù)算法需要迭代更多的次數(shù)才能得到一較優(yōu)解。因此，如何高效的、快速的求解該問題并得到一個“折中解”顯得尤為重要。本文采用二階段TSP算法規(guī)

15、劃移動節(jié)點的移動路徑同時保證訪問路徑最短及均衡性要求。該算法在保留了TSP路徑最優(yōu)的情況下，同時滿足均衡這一目標(biāo)。算法1：二階段TSP算法輸入：興趣點集，興趣點距離矩陣，是興趣點、間的距離，移動節(jié)點數(shù)k輸出：無線傳感器網(wǎng)絡(luò)巡航覆蓋中各移動傳感器節(jié)點的移動路徑1) 利用算法2得到一個移動節(jié)點訪問所有興趣點優(yōu)化路徑2) s=n/k 3) 按中的訪問順序?qū)⒄麄€路徑分成k段，前k-1段中興趣點的個數(shù)為s，第k段中興趣點至少為s，則（其中,）為第個移動傳感器訪問興趣點的集合，()為最后一個移動傳感器訪問興趣點的集合4) While()5) 按路徑調(diào)整每段中興趣點的數(shù)目6) 利用算法2優(yōu)化每個移動節(jié)點的訪

16、問路徑7) 8) 得到每個移動節(jié)點均衡的移動路徑算法2：基于遺傳操作的廣義粒子群優(yōu)化算法輸入： 被訪問的興趣點集，距離矩陣，是、間的距離輸出：移動傳感器的移動路徑1) 初始化粒子種群2) While（未達到迭代停止條件）3) For 種群中每個粒子4) 5) 6) 與個體極值進行交叉7) 7) 8) 與領(lǐng)域極值進行交叉 9) 中與之間的部分進行反轉(zhuǎn) 無線傳感器網(wǎng)絡(luò)巡航覆蓋基于二階段TSP移動路徑規(guī)劃方法分別由算法1給出。在算法1中調(diào)用了算法2，其中的算法2的適應(yīng)度函數(shù)為路徑長度，解的編碼采用基于順序表達的編碼，興趣點順序按自然數(shù)排列，算法2用于得到單個移動節(jié)點的最佳移動路徑。另外，由算法1所得

17、到的每個移動節(jié)點的訪問路徑可以依據(jù)命題2判斷所給移動節(jié)點數(shù)k值的是否滿足有效巡航覆蓋的要求，如果不滿足可以相應(yīng)增加k值，直至k值滿足命題2中有效巡航覆蓋的要求，如果所給移動節(jié)點數(shù)k滿足，同樣也可以相應(yīng)減少k值，如此在保證有效巡航覆蓋的同時減少移動節(jié)點數(shù)可以降低系統(tǒng)成本及復(fù)雜度，同時依據(jù)命題2，所獲得的每個移動傳感器節(jié)點的訪問序列是一次低成本巡航覆蓋。4、實驗結(jié)果為了驗證算法1的有效性及快速性，本文分別采用算法1以及采用算法3的多目標(biāo)優(yōu)化問題（以下稱為適應(yīng)度函數(shù)法）進行移動節(jié)點的訪問路徑優(yōu)化，其中適應(yīng)度函數(shù)法中適應(yīng)度函數(shù)為：，其中為調(diào)節(jié)目標(biāo)函數(shù)中兩個組成部分之間比例系統(tǒng)（k0）。當(dāng)k值較大時，總

18、目標(biāo)受總行程距離影響較大，得到的總路徑距離較小但是路徑之間長度差異較大，k較小時路徑差較小，但總路徑距離較大。本文實驗的監(jiān)測區(qū)域為一10*10的正方形區(qū)域，移動傳感器的速度為0.5， = 5，適應(yīng)度函數(shù)法迭代5000次，算法1興趣點數(shù)為30，50時迭代500次，興趣點為100，1000時迭代2000次，興趣點為1000時為加快求解速度，初始化種群時采用最近鄰法得到的解作為粒子。本文分別對興趣點數(shù)不同的場景進行了訪問路徑規(guī)劃，表1所示為不同興趣點數(shù)分別采用算法1以及適應(yīng)度函數(shù)法得到的路徑總長度、均衡度及移動節(jié)點數(shù)。表1中第一列是監(jiān)測區(qū)域內(nèi)興趣點的數(shù)目，第二列是采用的算法，每三列是通過各種算法得到

19、的訪問路徑總長度，第四列是根據(jù)路徑長度計算出的移動節(jié)點數(shù)，第五列為通過各種算法得到路徑的均衡度，最后一列是巡航覆蓋一周所用的時間。表1中，使用了算法1以及適應(yīng)度函數(shù)法進行路徑規(guī)劃，由表1可以看出二階段TSP算法相比較適應(yīng)度函數(shù)法在移動節(jié)點數(shù)相同的情況下能夠快速地得到長度更短更均衡的路徑。圖1所示為興趣點為100時分別采用算法1以及適應(yīng)度函數(shù)法得到的興趣點的移動路徑。表1 兩種方法所得結(jié)果興趣點數(shù)算法路徑總長度移動節(jié)點數(shù)均衡度巡航覆蓋一周時間t30算法149.1320.06450.78適應(yīng)度函數(shù)法59.8720.5582.450算法165.3830.0745.7適應(yīng)度函數(shù)法124.2430.45

20、112.27100算法196.1750.2545.86適應(yīng)度函數(shù)法300.2550.92281.371000算法1574.1180.3788.84適應(yīng)度函數(shù)法8045.44180.987998.2a.適應(yīng)度函數(shù)法獲得的移動節(jié)點訪問路徑b.算法1獲得的移動節(jié)點訪問路徑圖1 兩種方法獲得的移動節(jié)點的訪問路徑5、總結(jié)本文對無線傳感器網(wǎng)絡(luò)巡航覆蓋中移動傳感器移動路徑進行規(guī)劃，采用二階段TSP算法規(guī)劃移動節(jié)點的訪問路徑。實驗表明該方法相比較常規(guī)的適應(yīng)度函數(shù)法能夠快速得到均衡且距離最短的訪問路徑。無線傳感器網(wǎng)絡(luò)巡航覆蓋中移動節(jié)點路徑規(guī)劃無論對網(wǎng)絡(luò)成本、壽命、復(fù)雜度對有重大的影響。均衡且距離短的移動路徑不僅

21、可以降低系統(tǒng)成本及復(fù)雜度同時還可以延長網(wǎng)絡(luò)壽命，在實際應(yīng)用中，其具有重要意義。參考文獻1 I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Computer Networks, 2002.38:393-422.2 Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, A survey on sensor networks, IEEE Communications Magazine, 2002, 40(8):102-1143 Ian F. Akyildiz, Xudong Wang ,Weilin Wang, Wireless Mesh Networks: A Survey, Computer Networks Journal, 2005,47(4): 445-4874 S. Kumar, T. H. Lai, and J. Balogh, On k-Coverage in a Mostly Sleeping Sensor Network, proceedings of ACM MobiCom, 2004.5 C.