基于粒子群優化算法的三維無線傳感器網絡覆蓋增強方法

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

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

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

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

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

1 三維錐體有向感知模型

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

2 無線多媒體傳感器網絡的覆蓋優化

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

2.1 基于仰俯角的節點投影覆蓋面積優化

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

下面推導單個節點的二維投影面積及其對應的最優俯仰角，具體如下。

又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持續投資中國、優化業務布局的一年。例如，ABB在重慶設立的機器人應用中心正式開業，以重點滿足西部地區汽車、3C產品制造、裝備制造和消費品制造等領域對工業機器人快速增長的市場需求；不久前，ABB宣布將投資1.5億美元，在上海康橋建設其全球最大、最先進的機器人超級工廠，以擴大產能，提升效率，鞏固領先的市場地位，更好地滿足激增的客戶需求；而投資額約3億美元的ABB廈門工業中心將分散于廈門島內的多家企業合而為一，全面提升ABB自身的生產效率和核心競爭力。

b=HD

所以橢圓ABCD的面積為：

S=π×a×b

2.2 基于粒子群優化算法的位置信息優化

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

設在監測區域內隨機部署n個節點，則這組節點的初始位置可表示為(s1,…,sj,…,sn)，其中，sj為(x,y)，代表節點j在二維平面X-Y上的坐標。設種群中粒子規模為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的適應度函數為fi:

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

(1)

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

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

(2)

(3)

為保證種群粒子始終在可行域內進行搜索，當vi,j超出可行域范圍時，則調整為：

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

當xi,j(t)超出可行域范圍時，則調整為：

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

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

綜上，采用粒子群算法優化節點位置的具體步驟如下：

Step 1設置初始參數。節點數量m，種群規模n，最大進化代數Ngmax，學習因子C1、C2，w為動態權重。生成初始種群，包括每個粒子的位置和速度。

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

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

Step 4判斷是否達到最大進化代數，是則結束，并輸出最優粒子的位置，即為傳感器網絡中節點的部署；否則返回Step 2。

3 仿真試驗

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

表1 不同節點數量時的覆蓋率

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

表2 不同算法覆蓋率

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

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

4 結語

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