無線傳感器覆蓋

1、利用多種算法在三維地形上部署傳感器使得覆蓋度與工作時間雙目標(biāo)最優(yōu)化1、 引言 無線傳感器網(wǎng)絡(luò)（WSNs）是一種分布式傳感網(wǎng)絡(luò)，被廣泛應(yīng)用于軍事、智能交通、環(huán)境監(jiān)控、醫(yī)療衛(wèi)生等多個領(lǐng)域。如今，無線傳感器面臨的最大問題就是如何合理地部署傳感器用最少的傳感器達到最大的覆蓋度。關(guān)于這方面的研究大多數(shù)都是考慮二維平面上的傳感器部署，而現(xiàn)實實踐中傳感器部署發(fā)生在三維環(huán)境中，所以不同三維地形上最優(yōu)傳感器部署是本文考慮的重點。同時，大多數(shù)研究對目標(biāo)函數(shù)的設(shè)置往往只有無線傳感器覆蓋率，沒有對其所消耗的能量進行研究。而在現(xiàn)實應(yīng)用中，傳感器網(wǎng)絡(luò)的節(jié)點在電池能量上有所限制，而且由于物理限制難以給節(jié)點更換電池，所以傳感

2、器節(jié)點的電池消耗是整個傳感器網(wǎng)絡(luò)設(shè)計最為關(guān)鍵的約束之一，他直接決定了傳感器網(wǎng)絡(luò)的工作壽命。因此，本文在目標(biāo)函數(shù)中加入了傳感器網(wǎng)絡(luò)運行時間這一監(jiān)測量。 本論文的組織形式如下：第二部分，介紹一些準(zhǔn)備工作。第三部分，介紹本文涉及到的算法。第四部分，進行性能評估。該論文在第五部分進行總結(jié)。二、準(zhǔn)備工作 本論文的主要目標(biāo)是通過比較不同算法的性能來確定最優(yōu)算法。在這一部分，我們簡要介紹在該論文中用到的感知模型、工作時間模型與多目標(biāo)函數(shù)的整合。A.感知模型 無線信道是指發(fā)射源向接收源發(fā)送電磁輻射的假象通道，發(fā)射源和接收源天線之間的障礙物密度很大程度上取決于物理環(huán)境，信道上的障礙物將直接對信道可聯(lián)通性產(chǎn)生影響

3、1。WSNs中的概率感知模型描述了傳感器覆蓋率與距離和其他環(huán)境的關(guān)系2。在該模型中，我們定義了傳感器s的兩個檢測范圍，一個不確定的傳感器檢測范圍Ur和一個傳感器可檢測范圍Sr（Ur<Sr）。我們把于(Sr-Ur)和(Sr+Ur)的圓環(huán)范圍稱為模糊環(huán)。如果像素點p處于（Sr-Ur）范圍內(nèi)而且在s和p之間滿足LOS，那p確定可以被檢測到。如果p處于(Sr+Ur)范圍之外，或者s和p之間沒有視線，那么p肯定不能被檢測到。此外，如果p處于(Sr-Ur)和(Sr+Ur)范圍之間而且s和p之間滿足LOS，那么檢測概率可以被表示為exp(-.dist)。概率感知模型可表示為： 表示傳感器s與像素點p間

4、的三維歐式距離。和的值反映了地形的環(huán)境特征，調(diào)整這些變量可以模擬出不同的地形。LOS表示s和p在三維地形所連接的直線不被任何障礙物阻礙，即如圖所示 上圖展示了一種簡單的LOS情形，如圖所示，如果傳感器s和像素點p至今對應(yīng)的任何一個像素點的高度沒有切到連接s和p的線段，那么s和p之間有視線（LOS），否則s和p之間沒有視線（NLOS）3。由于直線是連續(xù)存在的，而地形數(shù)據(jù)是由離散的點集構(gòu)成，在模擬LOS過程中可能會出現(xiàn)的情況是直線穿過兩點之間的空間，即如下圖所示情況， 圖中，直線SP穿過坐標(biāo)A與B之間的C點，而由于地形數(shù)據(jù)中并無C點的高度坐標(biāo)，為應(yīng)對這種情況，我們的策略是令 其中分別代表點A，B，

5、C的高度坐標(biāo)。在概率感知模型下，由于傳感器節(jié)點的不確定性，目標(biāo)區(qū)域內(nèi)的像素點并不是以均一概率被覆蓋。節(jié)點距離目標(biāo)位置越近，其采集的信息越精確可靠；反之，離節(jié)點越遠(yuǎn)，感知能力越弱。若像素點p只被單一傳感器覆蓋或者距離其它傳感器很遠(yuǎn)，則需對該像素點實施多點協(xié)同覆蓋策略，以降低p成為盲點的可能性。設(shè)組成傳感器集合為，為所有傳感器對像素點p的融合覆蓋強度，在概率空間下，可進行如下推導(dǎo)： 經(jīng)典測量是一種可加性測度，然而在客觀實際中，對事物的度量并不滿足可加性。為此，基于Sugno測度的信息分析方法被提出4-6: 其中N代表傳感器數(shù)量,，該融合算子表現(xiàn)為弱可加性，根據(jù)真實情況，可通過選擇適當(dāng)?shù)膮?shù)來跟好地

6、估計傳感器網(wǎng)絡(luò)的覆蓋度。 使用表示像素點p的覆蓋率門限，由于的數(shù)值在0-1之間變化，因此為了評價感知模型下的網(wǎng)絡(luò)覆蓋率，定義： 經(jīng)研究，我們發(fā)現(xiàn)當(dāng)=0.7時比較符合實際情形。 QoC反應(yīng)了每次部署操作后地形被覆蓋的程度，QoC計算如下： 其中P代表像素點數(shù)量。B.時間模型傳感器進行感應(yīng)和通信時需消耗能量，所消耗能量E包含通信能量消耗和其他能量消耗兩部分。在這個模型中，我們定義了一個傳感器的通信距離。如果兩傳感器間的距離小于通信距離，則兩傳感器將進行通信，需要為通信消耗能量，否則不需要消耗能量。考慮到傳感器節(jié)點交換信息的目的在于提高位于傳感器模糊環(huán)處的覆蓋率，同時出于節(jié)能的目的，我們將通信距離設(shè)

7、置為 即讓兩傳感器間恰好能交換位于模糊環(huán)邊緣的像素點的信息。兩傳感器間的通信能量消耗可表示為7： 其中k和n（）為系數(shù)，和表示傳感器，表示兩傳感器間的距離。則某一個傳感器s的耗能可表示為： 假設(shè)每個傳感器的初始能量為e，則節(jié)點s可正常工作的生命周期為： 若網(wǎng)絡(luò)中的部分節(jié)點提前耗盡能量，則網(wǎng)絡(luò)聯(lián)通性將受到影響，整個網(wǎng)絡(luò)將處于癱瘓，因此通常將第一個“失敗”的節(jié)點的生命周期定義為整個網(wǎng)絡(luò)的生命周期： C.目標(biāo)函數(shù) 本文有兩個目標(biāo)函數(shù)，即部署方案的覆蓋率QoC與工作時間T。我們將兩個目標(biāo)函數(shù)進行整合，以適應(yīng)度函數(shù)來替代目標(biāo)函數(shù)。公式如下： 其中為系數(shù)。三、實驗中所用到的算法A.CSO-AVE算法 群智

8、能概念是通過觀察生物的行為發(fā)展起來的，并用于解決組合優(yōu)化問題。通過對貓科動物的觀察，人們提出了貓群優(yōu)化算法（CSO）。 在貓群算法中，貓被分為跟蹤和搜索兩種模型，在搜索模式中貓觀察四周并尋找下一個要移動的位置。在跟蹤模式中，貓跟蹤一些目標(biāo)。CSO的其中一個重要特征是貓花費大多數(shù)時間在搜索模式。它們一旦找到一個好的獵物，就會立即進入跟蹤模式。CSO算法很簡單，它首先創(chuàng)建大量的貓并將其置為搜索模式。將貓隨機灑到M維解空間中，并在預(yù)定義的值范圍內(nèi)隨機選擇值。然后根據(jù)一個選擇標(biāo)準(zhǔn)，隨機地將一部分貓置為跟蹤模式。每次移動之后，貓的適應(yīng)度值都被重新計算，最好的結(jié)果將被存儲起來。這個算法的所有過程都被重復(fù)執(zhí)

9、行，直到滿足終止條件時，循環(huán)結(jié)束。CSO-WT由Samil Temel，Numan Unaldi，和Okyay Kaynak8提出。該算法在傳統(tǒng)貓群算法的基礎(chǔ)上，加入了離散小波變換技術(shù)，對QoC矩陣進行小波變換得到其DWT值用于檢測Qoc矩陣的覆蓋漏洞。變換后得到的逼近系數(shù)矩陣包含了QoC矩陣的能量壓縮，且較QoC矩陣來說有更少的維數(shù)，但它仍然提供了關(guān)于覆蓋漏洞的足夠信息，來確定部署新傳感器的候選像素位置。 基于這一思路，我們用插空均值法替代小波變換，提出了CSO-AVE算法。所謂插空均值法，即對于二維矩陣lon,wid中每個緯度從第一個下標(biāo)其每隔4個下標(biāo)作為首坐標(biāo)截取一個4×4的矩

10、陣，計算該子矩陣的平均值形成新的壓縮矩陣。算法如下：AVE壓縮 for（int i=0;i<lon;i+=4） for（int j=0;j<wid;i+=4） for（int p=0;i<4;i+） for（int q=0;j<4;i+） sum+=QoCi+pj+q; Avei/4j/4=sum/(4*4); 在算法中，我們將一個32×32的QoC矩陣進行AVE運算，得到了一個8×8的壓縮矩陣。這一做法有助于降低壓縮QoC矩陣所需的計算量，并能保持QoC矩陣總體特征。CSO-AVE算法如下：算法 1 CSO-AVE算法 加載 地形T；設(shè)置 Ns；

11、%初始化模式第一步：在地形上部署限制數(shù)量的傳感器并計算該部署情況下的QoC值第二步：對QoC矩陣進行AVE運算來檢測QoC矩陣中的覆蓋漏洞。將剩 余的傳感器部署到未被覆蓋的區(qū)域。稱每個部署為一個Dv，Dv代 表了一個貓。第三步：計算該部署情況的適應(yīng)度值并將其追加到對應(yīng)的Dv上。第四步：保存Dv。跳轉(zhuǎn)到第一步，重復(fù)k次。 重復(fù)執(zhí)行根據(jù)比例MR將部分貓置為跟蹤模式。 %搜索模式If 貓在搜索模式 then第一步：將貓Dv（k）復(fù)制SMP份第二步：對于復(fù)制出的貓，根據(jù)比例CDC，選擇部分貓作為要改變的候 選貓 第三步：對于第二步中選擇出的Dvs，隨機改變其中SRD的傳感器的位 置，傳感器根據(jù)SMR值

12、移動。第四步：計算所有貓的適應(yīng)度值并將這些值追加到對應(yīng)的Dv。第五步：選擇具有最高適應(yīng)度值的Dv，讓其替換原始貓。End if %跟蹤模式If 貓在跟蹤模式 then第一步：對于Dvs中的每個貓，百分之MRT的傳感器將被移動。AVE揭 示了傳感器周圍覆蓋率最低的區(qū)域（覆蓋漏洞），傳感器移動 正是利用了AVE。根據(jù)AVE值移動傳感器到周圍的對應(yīng)區(qū)域。第二步：計算所有貓的適應(yīng)度值，如果移動后Dv的適應(yīng)度值大于原始 貓的，則用移動后的Dv替換原始貓。End ifUntil 滿足終止條件 B.PSO算法 粒子群算法由J.Kennedy和R.C.Eberhart于1995年首次提出，其基本思想是：每一個

13、粒子都在空間中依據(jù)兩類重要的信息來不斷更新飛行的速度和方向，即自身經(jīng)驗信息和整個群體的經(jīng)驗信息。 基于這一思想，粒子群優(yōu)化算法的基本流程如下。設(shè)群體的規(guī)模為N，在一個n維的空間內(nèi)，每個粒子維持著其位置向量和速度向量，i代表種群中第i個粒子。PSO算法如下：算法 2 PSO算法 加載 地形T；設(shè)置 Ns；第一步：對每個粒子i初始化粒子的速度和位置，并將該粒子的歷史最 優(yōu)位置設(shè)置為當(dāng)前位置，整個群體 中最優(yōu)個體位置記為。 重復(fù)執(zhí)行第二步：每個粒子根據(jù)該粒子的歷史最優(yōu)位置和整體最優(yōu)位置來更新粒子的 飛行速度，即 第三步：根據(jù)更新的飛行速度，粒子進一步更新所處的位置 第四步：評估每個粒子位置的適應(yīng)度，

14、如果適應(yīng)度優(yōu)于該粒子的歷史最優(yōu)位 置pbest，則更新pbest；如果適應(yīng)度優(yōu)于整個群體的歷史最優(yōu)位 置gbest，則更新gbest。 Until 滿足終止條件 本文還對CLPSO9、DE等算法進行了比較C.算法優(yōu)化由于地形的大小固定，為避免發(fā)生傳感器越界的現(xiàn)象，需要對算法進行邊界處理。此外，考慮到將傳感器部署到邊界附近時，傳感器感知范圍將大幅度降低，因此在邊界處理的同時應(yīng)避免傳感器與邊界靠近，即傳感器與邊界應(yīng)保持距離d，我們讓d恰好為傳感器感知模糊環(huán)的內(nèi)徑，邊界處理算法 while（判斷傳感器坐標(biāo)值a是否在地形內(nèi)）/超過邊界部分關(guān)于邊界對稱 if (a<0) a=|a| else if

15、 (a>lon) /lon為邊界 a=lon-(a-lon) end while if(a<d)/避免靠近邊界 a=d else if(lon-a)<d) a=lon-d return a 四、性能評估 首先，我們對CSO-AVE、PSO、CLPSO、DE等算法進行測試，每隔20代抽樣一次，結(jié)果如下表所示： 我們可以發(fā)現(xiàn)，在迭代次數(shù)相同條件下，算法性能為PSO>CSO-AVE>CLPSO。迭代次數(shù)csopsoclpso最大值0.7120.7190.7030中位值0.6850.6690.667平均值0.686280.670680.67228標(biāo)準(zhǔn)差0.01293097

16、10.016677630.032843721最大值0.7730.7830.77520中位值0.740.7520.729平均值0.740.753320.72972標(biāo)準(zhǔn)差0.0125399360.0171189950.017331378最大值0.7870.8240.7840中位值0.7560.780.734平均值0.75780.777880.73932標(biāo)準(zhǔn)差0.0130958010.0218523840.016960051最大值0.80.8430.7860中位值0.7660.7890.742平均值0.767240.79260.74504標(biāo)準(zhǔn)差0.0127255650.0258618120.0145

17、75893最大值0.8030.8930.7880中位值0.7730.8050.742平均值0.77460.80960.74696標(biāo)準(zhǔn)差0.013702190.0290516780.014432256最大值0.820.8950.78100中位值0.7820.8220.746平均值0.784360.82160.74896標(biāo)準(zhǔn)差0.0152147950.027937430.013645756最大值0.820.8980.78120中位值0.790.8320.748平均值0.789480.831040.75016標(biāo)準(zhǔn)差0.0135096260.0291425810.013030989最大值0.820.9

18、070.78140中位值0.7950.8410.748平均值0.792840.840160.7502標(biāo)準(zhǔn)差0.0122054630.0294557290.012980755最大值0.820.9130.78160中位值0.7990.8430.751平均值0.797440.847080.75168標(biāo)準(zhǔn)差0.011722770.029856490.013113987最大值0.820.9170.78180中位值0.80.8570.751平均值0.801080.855320.75216標(biāo)準(zhǔn)差0.0096476250.0313551170.012788928最大值0.8210.9730.78200中位值0

19、.8020.860.751平均值0.80380.867520.75268標(biāo)準(zhǔn)差0.0097638790.0380691480.0121061975、 總結(jié) 在WSNs中，如何部署傳感器使其具備較好的覆蓋度、可以被接受的工作時長是一個具有挑戰(zhàn)性的任務(wù)。相較二維地形，在三維地形上部署傳感器需要更多的從視覺、圖像等角度入手進行研究，具有現(xiàn)實性與實用性等特點。本文基于種群進化算法并進行適當(dāng)改進，通過實驗我們發(fā)現(xiàn)在三維地形部署傳感器問題上，類似于PSO以全局最優(yōu)值來優(yōu)化個體的全局性算法收斂性快、效果較好，而類似于CSO這種基于物理方式探索的局部性算法也具有較好效果，而CLPSO由于收斂性較慢，導(dǎo)致可行行

20、差。今后，我們將嘗試將PSO算法與CSO算法結(jié)合成一個新算法，使算法保證粒子向最優(yōu)解收斂的同時也重視粒子的局部多樣性。參考文獻：1 D.Tse and P.Viswanath, Fundamentals of Wireless Communication, Cambridge, U.K.: Cambridge Univ.Press, 2005.2 H.Chizari, M.Hosseini, T.Postonm, S.A.Razak,and A.H.Abdullah,”Delaunay triangulation as a new coverage measurement method in

21、wireless sensor network,” Sensors, vol.11, no.3, pp. 3163-3167,Mar.2011.3 D.Hearn and M.P.Baker,”Computer Graphics”,Englewood Cliffs, NJ, USA: Prentice Hall, 1994.4 M Sugeno. Theory of fuzzy integrals and its applicationsD. Tokyo: Tokyo Institude of Technology,1974.5 Michel Grabisch,Toshiaki Murofushi, Michio Sugeno. Fuzzy Measures and Intergrals Theory and ApplicationM. Germany :Physica-Verlag Heidelb