基于粒子群優(yōu)化算法的三維無線傳感器網(wǎng)絡(luò)覆蓋增強方法

張磊，焦正華 (長江大學(xué)電子信息學(xué)院，湖北 荊州 434023)

許淼 (長江大學(xué)檔案館，湖北 荊州 434023)

李興五，李鵬，郭頌，王思誠 (長江大學(xué)電子信息學(xué)院，湖北 荊州 434023)

目前，對于無線多媒體傳感器網(wǎng)絡(luò)(wireless multimedia sensor networks, WMSNs)的覆蓋增強研究大多集中在二維平面[1～4]，由于沒有考慮感知高度信息，這些模型不能描繪真實的三維物理環(huán)境，為此研究者設(shè)計出更為準(zhǔn)確的三維有向感知模型。如Ma等[5]提出基于水平感知和垂直感知的三維有向感知模型，肖甫等[6]在文獻[5]基礎(chǔ)上，提出俯仰角優(yōu)化和偏向角優(yōu)化的覆蓋增強策略，但都未考慮節(jié)點的感知范圍。同時，現(xiàn)有文獻[7～11]大多通過調(diào)節(jié)節(jié)點的主感知方向來實現(xiàn)對監(jiān)測區(qū)域的最優(yōu)覆蓋。

Latif等[12]針對水下無線傳感網(wǎng)絡(luò)的能耗問題，提出冗余覆蓋策略和覆蓋盲區(qū)修改策略來有效減少能耗；楊永建等[13]提出一種探索能力增強型的粒子群算法，并利用該算法優(yōu)化概率覆蓋模型以提高覆蓋率；Qasim等[14]通過改進標(biāo)準(zhǔn)蟻群算法，提出一種基于改進蟻群算法的部署方法；孫澤宇等[15]提出基于概率模型的優(yōu)化覆蓋方法，有效改善了覆蓋率和生存周期；Sun等[16]提出一種基于復(fù)雜聯(lián)盟策略的多目標(biāo)覆蓋增強方法，從而實現(xiàn)能耗和覆蓋率的優(yōu)化；Xu等[17]提出一種混合多目標(biāo)分解優(yōu)化算法，并融合離散二進制粒子群策略，來優(yōu)化覆蓋率和生存周期。上述方法均通過隨機方式部署節(jié)點，導(dǎo)致大量節(jié)點集中，節(jié)點間會存在很多感知重疊區(qū)域，此時不管如何調(diào)節(jié)節(jié)點的主感知方向，監(jiān)測區(qū)域的覆蓋率均不會有明顯的提升，致使覆蓋增強方法的收斂性不高。為此，筆者加入節(jié)點感知高度信息和節(jié)點感知半徑，設(shè)計了一種更符合三維物理環(huán)境的三維錐體有向感知模型。同時，推導(dǎo)得出單個節(jié)點的最佳投影面積及其對應(yīng)的俯仰角，并在此基礎(chǔ)上利用粒子群優(yōu)化算法來調(diào)整節(jié)點的位置信息，從而實現(xiàn)對監(jiān)測區(qū)域的最優(yōu)覆蓋。

1 三維錐體有向感知模型

筆者設(shè)計的三維錐體有向感知模型如圖1所示。根據(jù)參考文獻[18]得出，該三維錐體有向模型在二維平面的投影是橢圓ACBD。圖中，P為傳感器節(jié)點，節(jié)點的高度為h，節(jié)點感知半徑為R；AB是橢圓的長軸，CD是橢圓的短軸，H是AB和CD的中點，即橢圓的中心；PK垂直橢圓ACBD；PG是∠APB的角平分線；∠KPG=γ為傳感器垂直方向上偏移的角度，即仰俯角；∠APB=2β是傳感器垂直方向感知區(qū)域視角；水平方向感知區(qū)域視角為2π。

2 無線多媒體傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化

為實現(xiàn)WMSNs的最優(yōu)覆蓋，一方面可以優(yōu)化單個節(jié)點的俯仰角，使其投影覆蓋面積最大；另一方面可以調(diào)整所有節(jié)點的位置，減少節(jié)點間的感知重疊區(qū)以改善覆蓋率。同時優(yōu)化會導(dǎo)致復(fù)雜度過高，通過進一步分析發(fā)現(xiàn)，單個節(jié)點的二維投影面積只與仰俯角有關(guān)，所以可以先求解節(jié)點的最優(yōu)仰俯角，再優(yōu)化節(jié)點的位置信息，減少感知重疊區(qū)和感知盲區(qū)，進而提升覆蓋率。為此，筆者將覆蓋增強過程分為基于仰俯角的節(jié)點投影覆蓋面積優(yōu)化和基于粒子群算法的位置信息優(yōu)化。

2.1 基于仰俯角的節(jié)點投影覆蓋面積優(yōu)化

如圖2所示，P為節(jié)點，圓錐PMWNV為P的空間感知區(qū)域；橢圓ACBD為節(jié)點在二維平面的投影，PN為P的最大感知半徑，即PN=R；∠APB=2β，即為P的垂直感知區(qū)域視角；PG為∠APB的角平分線，則PG必定在圓錐PMWNV的中心軸PQ上；∠KPG=γ，即傳感器的俯仰角；節(jié)點P高度為h，即PK=h。設(shè)∠GPH=θ，過橢圓ACBD的中心點H作垂直中心軸PQ的圓ECFD，圓心為O，與PN、PM分別相交于點E、F。

下面推導(dǎo)單個節(jié)點的二維投影面積及其對應(yīng)的最優(yōu)俯仰角，具體如下。

又AK=PK×tan(β-γ)=htan(β-γ),BK=PK×tan(β+γ)=htan(β+γ),所以橢圓ACBD的長半軸a為：

故：

又PK垂直于橢圓ABCD, 所以PK⊥KH，則：

由OH⊥PQ，且O,H,C,D,E,F在同一個面上, 所以EDFC必定是一個圓，又PD=PF，則圓EDFC和圓MWNV相互平行。

在?OPH中，∠OPH=∠GPH=θ,PO=PHcosθ，從而有PD=PF=PO/cosβ=PHcosθ/cosβ。

又CD⊥面PKH, 所以PH⊥CD，則橢圓ACBD的短半軸b為：

2018年是ABB持續(xù)投資中國、優(yōu)化業(yè)務(wù)布局的一年。例如，ABB在重慶設(shè)立的機器人應(yīng)用中心正式開業(yè)，以重點滿足西部地區(qū)汽車、3C產(chǎn)品制造、裝備制造和消費品制造等領(lǐng)域?qū)I(yè)機器人快速增長的市場需求；不久前，ABB宣布將投資1.5億美元，在上?？禈蚪ㄔO(shè)其全球最大、最先進的機器人超級工廠，以擴大產(chǎn)能，提升效率，鞏固領(lǐng)先的市場地位，更好地滿足激增的客戶需求；而投資額約3億美元的ABB廈門工業(yè)中心將分散于廈門島內(nèi)的多家企業(yè)合而為一，全面提升ABB自身的生產(chǎn)效率和核心競爭力。

b=HD

所以橢圓ABCD的面積為：

S=π×a×b

2.2 基于粒子群優(yōu)化算法的位置信息優(yōu)化

在得出最優(yōu)仰俯角γ后，單個節(jié)點的覆蓋面積將達到最大。但由于通過隨機方式部署大量節(jié)點，會造成節(jié)點間存在著很多感知重疊區(qū)，所以需要優(yōu)化節(jié)點位置以降低感知重疊區(qū)，進一步提升覆蓋率。為此，引入收斂速度快、搜索效率高的粒子群算法[19,20]來調(diào)整節(jié)點位置。

設(shè)在監(jiān)測區(qū)域內(nèi)隨機部署n個節(jié)點，則這組節(jié)點的初始位置可表示為(s1,…,sj,…,sn)，其中，sj為(x,y)，代表節(jié)點j在二維平面X-Y上的坐標(biāo)。設(shè)種群中粒子規(guī)模為m，則粒子xi的位置為(xi,1,…,xi,j,…,xi,n)，i=1,…,m，j=1,…,n，sj=xi,j。粒子xi的速度為vi=(vi,1,…,vi,j,…,vi,n),定義粒子xi的適應(yīng)度函數(shù)為fi:

fi=f(xi,1,…,xi,j,…,xi,n)

(1)

式中：fi的值代表覆蓋率。

粒子的速度和位置更新分別如式(2)和式(3)所示。

(2)

(3)

為保證種群粒子始終在可行域內(nèi)進行搜索，當(dāng)vi,j超出可行域范圍時，則調(diào)整為：

vi,j=r×(vmax-vmin)+vmin

當(dāng)xi,j(t)超出可行域范圍時，則調(diào)整為：

xi,j=r×(xmax-xmin)+xmin

式中:vmax和vmin分別為粒子最大和最小速度；xmax和xmin分別為粒子的最大和最小邊界范圍。實質(zhì)上，粒子的初始位置和初始速度也是根據(jù)上述方法生成的。

綜上，采用粒子群算法優(yōu)化節(jié)點位置的具體步驟如下：

Step 1設(shè)置初始參數(shù)。節(jié)點數(shù)量m，種群規(guī)模n，最大進化代數(shù)Ngmax，學(xué)習(xí)因子C1、C2，w為動態(tài)權(quán)重。生成初始種群，包括每個粒子的位置和速度。

Step 2計算粒子的適應(yīng)度值，即每個粒子所代表的覆蓋率。

Step 3根據(jù)式(2)和式(3)更新粒子的位置和速度。

Step 4判斷是否達到最大進化代數(shù)，是則結(jié)束，并輸出最優(yōu)粒子的位置，即為傳感器網(wǎng)絡(luò)中節(jié)點的部署；否則返回Step 2。

3 仿真試驗

為保證對比的公平性，所有算法中涉及相同的參數(shù)均取值一樣。參考文獻[6]，試驗參數(shù)設(shè)置如下：在200m×200m的二維監(jiān)測區(qū)域內(nèi)，隨機布撒若干節(jié)點，每個節(jié)點高度h=6m，節(jié)點感知半徑R=30m，節(jié)點水平感知視角為2π，垂直感知視角β=2π/3。最大進化代數(shù)Gmax=100，種群規(guī)模n=100，學(xué)習(xí)因子C1=C2=1.5，vmin=-10，vmax=10，計算出節(jié)點的最優(yōu)俯仰角18.46°。所有試驗均在硬件配置為Intel(R) Core(TM) i7-7500U CPU@2.70GHz的計算機上進行，采用MATLAB2014編程。試驗中節(jié)點數(shù)量m=40、50、60、80，仿真試驗結(jié)果如圖3～6和表1、表2所示。

表1 不同節(jié)點數(shù)量時的覆蓋率

從圖3～6可以看出，當(dāng)節(jié)點的俯仰角為最優(yōu)俯仰角時，節(jié)點在二維平面的投影形狀和面積均一樣。未對節(jié)點位置進行優(yōu)化前，由于是隨機部署所有節(jié)點，節(jié)點的分布不均勻，而且節(jié)點間存在大量的感知重疊區(qū)和感知盲區(qū)；對節(jié)點的位置進行優(yōu)化后，節(jié)點分布更加均勻，節(jié)點間的感知重疊區(qū)和感知盲區(qū)明顯降低，整個網(wǎng)絡(luò)的覆蓋率得到較大程度的提升，這表明節(jié)點位置優(yōu)化的有效性和必要性。同時還可以看出，隨著節(jié)點數(shù)的增加，監(jiān)測區(qū)域基本得到較好的覆蓋，但節(jié)點之間的覆蓋重疊區(qū)也隨之增加。

表2 不同算法覆蓋率

從表1可以看出，當(dāng)節(jié)點較少時，覆蓋率的改善不太明顯。這是由于此時節(jié)點間的覆蓋重疊區(qū)較少，通過優(yōu)化節(jié)點位置來提升覆蓋率的效果不太大。隨著節(jié)點數(shù)的增多，未優(yōu)化前的覆蓋率隨之提高，但此時節(jié)點間的覆蓋重疊區(qū)也增多，通過節(jié)點位置優(yōu)化后，覆蓋率得到較大程度的提升。

從表2可以看出，在相同的初始覆蓋率情況下，筆者的算法通過優(yōu)化俯仰角和節(jié)點位置優(yōu)化，最終取得了更優(yōu)的網(wǎng)絡(luò)覆蓋率，具備一定的優(yōu)勢。這進一步說明了筆者提出的基于俯仰角優(yōu)化和節(jié)點位置優(yōu)化的粒子群覆蓋增強方法可以有效減少覆蓋重疊區(qū)和感知盲區(qū)。

4 結(jié)語

筆者對現(xiàn)有感知模型和覆蓋增強方法存在的問題展開了研究，一方面引入感知高度信息和節(jié)點感知半徑，設(shè)計出一種三維錐體有向感知模型，并推導(dǎo)出最優(yōu)二維投影面積；另一方面采用粒子群算法優(yōu)化節(jié)點的位置信息，以提升覆蓋率。仿真試驗結(jié)果表明了該方法較好地提升了覆蓋率。下一步的研究工作將圍繞節(jié)點冗余問題展開研究，即以最少的節(jié)點數(shù)和能耗最大化網(wǎng)絡(luò)覆蓋率。