張士榮，趙俊杰，談發(fā)明

(1.江蘇理工學院 信息中心，江蘇 常州 213001；2.江蘇理工學院 電氣信息工程學院，江蘇 常州 213001)

0 引 言

傳感器節(jié)點的部署及網絡覆蓋是決定WSN感知、通信質量的關鍵，直接影響無線網絡的生存時間和網絡管理效率[1-3]。節(jié)點部署不佳會導致覆蓋盲區(qū)、節(jié)點密度過高和重復覆蓋、冗余節(jié)點多等問題，優(yōu)化WSN節(jié)點部署，以更少的WSN節(jié)點部署數(shù)量提高監(jiān)測區(qū)域覆蓋率將具有重要意義。

將WSN節(jié)點部署位置搜索與群體智能優(yōu)化算法相結合，可以利用智能算法優(yōu)異的隨機式和啟發(fā)式搜索機制加快節(jié)點部署位置的尋優(yōu)過程。哈里斯鷹算法HHO[4]是一種新的智能優(yōu)化算法，算法以哈里斯鷹種群對獵物的包圍、攻擊過程建立算法數(shù)學模型。該算法綜合性能較優(yōu)已廣泛應用在圖像分割[5]、神經網絡訓練[6]、電力系統(tǒng)控制[7]、時差定位[8]等領域。但HHO算法本身還存在著易早熟收斂、求解精度低的不足。

為了解決WSN節(jié)點覆蓋優(yōu)化問題，本文設計一種改進哈里斯鷹優(yōu)化算法MHIHHO求解節(jié)點覆蓋優(yōu)化問題。為了提高HHO算法的性能，設計Fuch無限折疊混沌初始化策略對種群進行初始化；利用自適應精英個體對立學習提高候選解質量；引入正余弦優(yōu)化改進局部開發(fā)中軟/硬包圍的跳躍式位置更新，提高局部尋優(yōu)能力；結合柯西與拉普拉斯最優(yōu)解變異實現(xiàn)變異，使算法跳離局部極點。結果表明，改進哈里斯鷹算法MHIHHO在優(yōu)化WSN節(jié)點覆蓋率方面實現(xiàn)了預期效果。

1 相關研究現(xiàn)狀

智能優(yōu)化算法因具有較強的全局搜索能力，近年來被廣泛應用于WSN節(jié)點覆蓋優(yōu)化問題。文獻[9]提出混合遺傳與差分進化的多目標覆蓋優(yōu)化算法，實現(xiàn)了傳感節(jié)點的優(yōu)化部署。文獻[10]利用虛擬力對傳統(tǒng)PSO進行優(yōu)化，將節(jié)點覆蓋率提升了5%。文獻[11]提出外推改進人工蜂群算法，應用于WSN節(jié)點部署優(yōu)化后，模型的覆蓋率有所提高，但結果依然存在10%左右盲區(qū)。文獻[12]提出改進灰狼優(yōu)化算法，節(jié)點覆蓋率提升了4%，但節(jié)點分布均勻性仍有不足。文獻[13]則引入了種群分布熵和平均粒距的概念，雖然覆蓋率接近于90%，但依然沒有解決好盲區(qū)。文獻[14]提出改進鯨魚優(yōu)化算法，網絡覆蓋監(jiān)測效率有所提高。文獻[15]利用改進果蠅算法對傳感節(jié)點覆蓋率和連通性進行優(yōu)化，部署效果優(yōu)于蟻群算法。有關哈里斯鷹算法的改進也有一些相關研究，但還未檢索到應用在節(jié)點部署優(yōu)化問題中的文獻，在HHO算法改進工作上，文獻[16]結合偽反射學習機制設計新型哈里斯鷹算法QRHHO，一定程度提升了算法尋優(yōu)精度。文獻[17]結合混沌遍歷、規(guī)律、隨機思想改進HHO，以混沌映射增強初始種群多樣性，并結合模擬退火對算法局部最優(yōu)跳離能力進行改進。文獻[18]結合長期記憶法提高算法全局搜索能力。文獻[19]引入方形鄰域拓撲改進種群個體組成，通過縱橫雙向隨機覓食提高HHO開發(fā)能力。文獻[20]引入偽反向學習提高HHO初始種群的多樣性，進一步提升算法收斂速度。

以上基于智能優(yōu)化算法的WSN節(jié)點覆蓋優(yōu)化策略，雖然可以有效優(yōu)化節(jié)點部署，但智能算法本身存在尋優(yōu)精度差和易于得到局部最優(yōu)的缺陷，且在搜索與精細開采過程的平衡、避免局部最優(yōu)等綜合性能上仍有一些不足。因此，針對WSN節(jié)點覆蓋率的提升和均勻度方面的優(yōu)化工作仍然有進一步的研究空間。

2 HHO算法及其多策略混合改進算法

2.1 HHO算法

HHO過程由搜索與開發(fā)兩個階段組成。兩個階段的切換則由獵物的逃逸能量系數(shù)E決定，不同E值會引導哈里斯鷹展現(xiàn)不同的捕食模式。能量系數(shù)E定義為

E=2E0(1-t/Tmax)

(1)

式中：t為當前迭代，Tmax為算法最大迭代次數(shù)，E0為獵物的初始能量，且E0=2r1-1，r1為[0，1]間的隨機量。式(1)表明：獵物的逃逸能量在算法迭代過程中將在(-1，1)間變化。

(1)全局搜索階段

若滿足 |E|≥1， HHO進入全局搜索階段。此時，哈里斯鷹將依據隨機選擇個體和目標個體的位置對自身的位置進行更新，數(shù)學模型如

Xi(t+1)=

(2)

(3)

式中：Xrand(t)、Xi(t)、Xrabbit(t) 分別指迭代t時隨機選擇個體位置、個體i原位置、種群全局最優(yōu)個體位置，Xi(t+1) 為個體i的更新位置，q、ri(i=1，2，3，4) 為(0，1)間的隨機量，[lb，ub] 為個體搜索邊界值，Xm(t) 為個體位置均值，N為哈里斯鷹的種群規(guī)模。

(2)局部開發(fā)階段

若滿足 |E|<1， HHO進入局部開發(fā)階段。此時，哈里斯鷹擁有4種不同的策略完成對獵物的捕食：軟包圍、硬包圍、漸進式快速俯沖軟包圍和漸進式快速俯沖硬包圍。而選擇哪種策略由獵物逃逸能量系數(shù)E和逃逸概率λ決定。

1)若滿足 |E|≥0.5且λ≥0.5，表明存在逃逸能量，此時的數(shù)學模型如

(4)

式中：ΔX(t) 為獵物與個體間距，r5為隨機量，J為逃逸跳躍值。

2)若 |E<0.5且λ≥0.5， 表明不存在逃逸能量，個體將以硬包圍方式對獵物發(fā)起突襲，數(shù)學模型如

Xi(t+1)=Xrabbit(t)-E|ΔX(t)|

(5)

3)若滿足 |E|≥0.5且λ<0.5， 表明獵物仍有充足能量逃逸，哈里斯鷹將以漸進式快速俯沖軟包圍方式圍捕獵物，并實時糾正圍捕位置和方向，數(shù)學模型如

Xi(t+1)=

(6)

式中：D為搜索位置維度，S為大小為D×1的(0，1)間隨機行向量，LF() 為服從Levy飛行分布的函數(shù)，計算方法為

(7)

式中：μ、v為(0，1)間隨機量，β=1.5。

4)若滿足 |E|<0.5且λ<0.5， 表明獵物能量快耗盡，哈里斯鷹將以漸進式快速俯沖硬包圍方式圍捕獵物，該數(shù)學模型如

Xi(t+1)=

(8)

2.2 多策略混合改進哈里斯鷹算法MHIHHO

2.2.1 Fuch無限折疊混沌初始化策略

初始種群的分布對于算法的尋優(yōu)效率具有很大影響。由于HHO算法對于最優(yōu)解的所在區(qū)域并無先驗知識可用，故采用了隨機初始化方法，會導致個體分布均勻性差，個體質量下降，影響算法尋優(yōu)速度?；煦缦到y(tǒng)具有遍歷性、非重復兼顧了隨機性的特點，有著比完全隨機分布更均勻的特征。常用的混沌映射系統(tǒng)如Logistic映射、Tent映射和Circle映射等，但這些都屬于有限折疊混沌映射。相比而言，F(xiàn)uch混沌映射是一種可無限折疊的混沌映射方式，其遍歷性、動態(tài)隨機性以及最后的收斂性都要優(yōu)于前面3種混沌映射。故MHIHHO引入Fuch無限折疊混沌方式對HHO進行種群初始化操作，以生成個體在搜索空間內的初始位置信息。Fuch混沌映射公式為

y(k+1)=cos(1/y(t)2)

(9)

式中：y(k)≠0。 生成Fuch混沌值后，混沌值與種群搜索空間的映射規(guī)則為

X(t)=lb+y(t)×(ub-lb)

(10)

式中：[lb，ub] 為個體搜索邊界，y(t) 為式(9)生成的Fuch混沌值。

圖1是以隨機初始化和Fuch混沌初始化得到的種群分布。隨機初始化方式為

圖1 兩種種群初始化分布

X(t)=lb+rand×(ub-lb)

(11)

顯然，隨機初始化中個體重疊覆蓋問題較為嚴重，F(xiàn)uch混沌初始化的均勻性更好，能夠更均勻地對解空間遍歷。雖然算法對最優(yōu)解所在區(qū)域并無先驗知識，但更均勻的個體分布將提升算法尋覓最優(yōu)解的搜索效率和穩(wěn)定性。

圖2是在基準函數(shù)Booth的測試下，MHIHHO分別利用隨機初始化、Logistic映射初始化、Circle映射初始化以及Fuch無限折疊混沌初始化策略得到的目標函數(shù)收線曲線。Sphere函數(shù)的理論最優(yōu)解為0。算法進行500次迭代，搜索區(qū)域內布置30個個體。觀察4個曲線，3種混沌映射初始化方法對函數(shù)的求解精度顯然優(yōu)于隨機化方法，隨機初始化在50個數(shù)據級的精度下一直處于平緩，最后收斂，在300次迭代后已經無法進一步提高收斂精度。3種混沌映射均有不同程度精度提高，但趨勢各異。隨機種群初始化在迭代約300次后尋優(yōu)精度已經穩(wěn)定，無法進一步開辟新空間，提升搜索精度。利用混沌種群初始化可以進一步提高搜索精度。所提Fuch無限折疊映射初始迭代初期搜索精度不是最優(yōu)，但后期精度迅速提升，得益于該初始化方法能夠使個體更均勻的分布，遍歷到所有未及區(qū)域，以更高的概率逼近最優(yōu)目標，提升多樣性。

圖2 不同混沌初始化策略對比

2.2.2 自適應精英個體對立學習策略

研究表明，種群個體經對立變異后擁有更大的概率靠近最優(yōu)解區(qū)域，種群可行解的質量可有效提高。為了擴展搜索區(qū)域，提高HHO的全局搜索能力，MHIHHO引入自適應精英個體對立學習策略對HHO進行改進。令X表示一個種群個體，即問題的一個可行解，搜索空間范圍為 [lb，ub]， 定義個體X的對立解X′為

X′=lb+(ub-X)

(12)

若種群所有個體進行對立學習，勢必會增加算法時間復雜度，而若個體適應度較差，其對立解對種群搜索方向引導也有不利。此外，HHO通過模擬哈里斯鷹的種群捕食過程，目標(食物源)的信息決定了種群個體位置更新，決定著算法進化方向。若目標已經處于局部最優(yōu)，則種群個體會向局部極值點靠攏，影響算法尋優(yōu)精度。利用精英個體組成的種群有利于避免單一個體在尋優(yōu)中發(fā)生早熟收斂。改進算法將進一步對精英個體進行對立學習，以自適應比例設置精英個體數(shù)量，進行對立學習。將種群中精英個體的數(shù)量定義為

(13)

式中：nelite為種群所選精英個體數(shù)量，N為種群個體總數(shù)，t為算法當前迭代次數(shù)，Tmax為算法總迭代次數(shù)。根據式(13)，精英個體的數(shù)量將隨著算法迭代線性遞減。迭代早期，精英個體數(shù)量較多，可以盡可能發(fā)揮個體對立解的優(yōu)勢，得到更多適應度較優(yōu)的候選解；迭代后期，精英個體數(shù)量逐步減少，可以加快算法收斂，降低算法時間復雜度。具體過程為：先計算種群個體適應度，按適應度對個體進行升序排列，選取前nelite個個體為精英個體，計算精英個體的對立解，并利用貪婪選擇策略保留適應度較優(yōu)的個體至下一代種群中。

2.2.3 正余弦優(yōu)化策略

當HHO迭代時，個體搜索維度其實在變小，即搜索空間逐步壓縮，種群多樣性逐步缺失。為了提升HHO的全局搜索能力，MHIHHO將引入正余弦優(yōu)化機制SCA[21]對HHO的局部開發(fā)過程進行優(yōu)化。具體針對MHIHHO中軟/硬包圍時的跳躍位置更新。

已知正余弦優(yōu)化中粒子個體的位置更新方式為

xi，j(t+1)=

(14)

式中：xbest，j為全局最優(yōu)解的j維位置，r6為振幅調節(jié)因子，r7∈[0，2π]、r8∈[-2，2]、r9∈[0，1]均為均勻分布隨機量。

結合式(14)，將軟/硬包圍階段的跳躍式位置更新方式定義為

X(t+1)=

(15)

式中：r6為振幅調節(jié)因子，用于均衡全局搜索與局部開發(fā)。若r6值較大，算法可以更大的步長提升全局搜索能力，而較小的r6值則可以使算法在局部范圍內作精細開發(fā)。為了提高改進算法的尋優(yōu)能力，本文結合指數(shù)函數(shù)將r6的更新改進為非線性遞減，定義為

r6(t)=(1+βt)·rmax·e-βt

(16)

式中：β表示曲線調整參數(shù)，rmax表示振幅調節(jié)系數(shù)的最大值。由此可見，r6將隨迭代非線性從最大值遞減到最小值，更好地在搜索與開發(fā)間進行轉換。

慣性權重w(t) 的思想源于粒子群算法，MHIHHO進一步引入該因子在迭代前期以更大權重值增強個體位置對種群的影響，迭代后期以更小權重值增強最優(yōu)個體引導，具體為

(17)

式中：k為調整系數(shù)，wmax、wmin分別是權重最大值和最小值。

2.2.4 高斯與拉普拉斯最優(yōu)個體變異策略

HHO算法的位置更新公式表明，隨著迭代進化，種群搜索將向著最優(yōu)解移動，逐步聚集于最優(yōu)解鄰域，這可能導致因多樣性缺失帶來的局部最優(yōu)解。為此，MHIHHO引入一種針對種群最優(yōu)解的混合變異策略，使得搜索個體具有跳離局部最優(yōu)、擴展搜索空間的能力?；旌献儺惒呗杂筛咚棺儺惡屠绽棺儺悪C制構成。

已知高斯分布的概率密度函數(shù)為

(18)

拉普拉斯分布的概率密度函數(shù)為

(19)

式中：m為高斯分布均值，n為變量；a∈(-∞，+∞)， 表示位置，b為比例參數(shù)，且b>0。

利用式(20)的分布函數(shù)定義拉普拉斯分布L(a，b)， 該函數(shù)關于位置參數(shù)a對稱分布

(20)

為了充分利用搜索空間的隨機性，增強種群多樣性，設拉普拉斯分布L(a，b) 中a=1，b=2。高斯分布G(m，n) 中m=0，n=1。將針對種群最優(yōu)解Xrabbit的混合變異方式定義為

Xrabbit(t+1)=(η1·L(1，2)+η2·G(0，1)+1)·Xrabbit(t)

(21)

(22)

拉普拉斯分布L(1，2) 擁有比高斯分布G(0，1) 更大的波動。而兩個系數(shù)η1和η2均是迭代t的指數(shù)函數(shù)，根據式(22)，系數(shù)η1迭代早期更大，有利于拓展搜索空間；迭代后期，η1漸漸減小，收斂加快。同時，系數(shù)η2不斷增加，高斯系數(shù)G(0，1) 此時利于精細開采，提高局部開發(fā)能力。

3 基于MHIHHO的WSN節(jié)點覆蓋優(yōu)化模型

3.1 覆蓋模型

將WSN節(jié)點部署于矩形區(qū)域，節(jié)點部署后不具備移動性，且節(jié)點均為同質結構。WSN節(jié)點具備感知能力，能夠發(fā)現(xiàn)其通信半徑內其它WSN節(jié)點?，F(xiàn)令部署區(qū)域大小為S=L×M，可將其視為L×M的網格，單個網格大小為1。WSN節(jié)點部署數(shù)量為V，表示為集合Z={Z1，Z2，…，ZV}， 所有節(jié)點為同質結構，具有相同的感知半徑r和通信半徑R，通常r≤2R。令 {xi，yi} 為節(jié)點Zi的坐標位置，i=1，2，…，V。

令點oj坐標為 {xj，yj}， 以歐氏距離度量方式計算傳感節(jié)點Zi與oj的距離為

(23)

若d(Zi，oj)≤r， 則oj被Zi覆蓋。定義oj被Zi感知的概率為

(24)

為了提升監(jiān)測區(qū)域內的感知概率，多個WSN節(jié)點可以協(xié)同進行感知。則點oj的聯(lián)合感知概率為

(25)

則監(jiān)測區(qū)域的覆蓋率即為所有WSN節(jié)點覆蓋的目標點數(shù)量與區(qū)域內總目標點數(shù)量的比值，定義為

(26)

3.2 利用MHIHHO算法求解WSN節(jié)點覆蓋問題

算法優(yōu)化目標是：利用若干數(shù)量WSN節(jié)點部署于監(jiān)測區(qū)域S，求解節(jié)點部署最優(yōu)位置，使目標區(qū)域的覆蓋率Pcov達到最大化。此時，覆蓋優(yōu)化問題可視為目標函數(shù)的搜索問題，算法的最優(yōu)解為各WSN節(jié)點的部署位置，而哈里斯鷹個體的位置則為WSN節(jié)點的覆蓋分布。對于一個搜索哈里斯鷹個體，其2d-1維位置為節(jié)點d的橫坐標，2d維位置則為節(jié)點d的縱坐標。具體步驟如下：

輸入：區(qū)域大小L×M、傳感節(jié)點數(shù)V、感知半徑r；種群規(guī)模n、迭代總數(shù)Tmax、搜索范圍 [lb，ub]、rmax、 系數(shù)k、權重值wmax和wmin；

輸出：WSN節(jié)點部署位置及最優(yōu)覆蓋率Pcov；

步驟1 輸入MHIHHO算法參數(shù)和WSN參數(shù)；

步驟2 在搜索空間內利用Fuch無限折疊混沌策略初始化哈里斯鷹種群；

步驟3 令當前迭代t=1；

步驟4 執(zhí)行自適應精英個體對立學習策略；并計算個體適應度，確定當前最優(yōu)解；

步驟5 根據式(1)更新獵物逃逸能量系數(shù)E；

步驟6 若 |E|≥1且q≥0.5， 根據式(2)中的第1個公式更新個體位置；若 |E|≥1且q<0.5，利用式(2)中的第2個公式更新個體位置；

步驟7 若 |E|≥0.5且λ≥0.5， 根據式(15)的正余弦優(yōu)化策略更新個體位置；

步驟8 若 |E|≥0.5且λ<0.5， 利用式(6)更新個體位置；

步驟9 若 |E|<0.5且λ≥0.5， 先利用式(5)更新個體位置；

步驟10 若 |E|<0.5且λ<0.5， 根據式(15)的正余弦優(yōu)化策略更新個體位置；

步驟11 返回種群更新后的位置，并更新最優(yōu)解；利用式(21)柯西和拉普拉斯分布對最優(yōu)解進行變異，并擇優(yōu)保留；

步驟12 更新迭代t=t+1；

步驟13 判斷終止條件，若未終止則返回步驟4；否則，輸出最優(yōu)解，即：對應的WSN節(jié)點部署的位置坐標及最優(yōu)覆蓋率Pcov。

圖3是MHIHHO求解覆蓋優(yōu)化問題的流程。

圖3 MHIHHO算法求解流程

4 仿真實驗

4.1 基準函數(shù)尋優(yōu)實驗

為了驗證MHIHHO的有效性，先利用6個基準函數(shù)式進行目標函數(shù)的尋優(yōu)實驗，表1是基準函數(shù)相關屬性。表中，基準函數(shù)f(x) 即為尋找最優(yōu)解的目標函數(shù)，搜索范圍為種群個體的活動空間，fmin為函數(shù)理論可達的最優(yōu)值。同時，在表1中，函數(shù)f1(x)～f3(x) 為單峰函數(shù)類型，f4(x)～f6(x) 為多峰函數(shù)類型。為了兼顧公平性，算法獨立運行20次，并計算其適應度均值、標準方差、最優(yōu)值。算法的種群規(guī)模n=30，搜索維度d=20，迭代總次數(shù)Tmax=500，振幅調節(jié)系數(shù)最大值rmax=2，調整系數(shù)k=2，權重最大值wmax=0.9，wmin=0.3。仿真平臺為Matlab2019a。選擇標準哈里斯鷹優(yōu)化算法HHO[4]、改進灰狼優(yōu)化算法IGWO[12]和改進哈里斯鷹優(yōu)化算法QRHHO[16]與本文的MHIHHO同時作縱橫向對比分析。

表1 基準函數(shù)說明

(1)尋優(yōu)精度對比。表2是各算法在基準函數(shù)上的尋優(yōu)結果?？梢钥闯觯琈HIHHO在6個基準函數(shù)中的4個可以取得理論最優(yōu)值，尋優(yōu)成功率達到66.7%，未取得理論最優(yōu)值的Schwefel2.21和Schwefel2.26中依然得到了最高的求解精度。而得到了更小的標準方差值，則表明MHIHHO具有更好的穩(wěn)定性和魯棒性。相比HHO，MHIHHO在求解精度上平均可以提高約4個數(shù)量級，與另外兩種改進的群體智能算法QRHHO和IGWO相比也有較大程度的求解精度提高，說明MHIHHO所引入針對HHO的不同進化階段所做的改進工作對標準HHO中的搜索與開發(fā)的均衡、提升收斂速度和尋優(yōu)精度的改進是切實有效可行的。

表2 算法尋優(yōu)結果

(2)收斂性對比。圖4進一步選取兩個單峰基準函數(shù)f2(x)、f3(x) 和兩個多峰基準函數(shù)f5(x)、f6(x) 共4個基準函數(shù)測試算法的尋優(yōu)收斂曲線。觀察曲線趨勢，MHIHHO在4個基準函數(shù)上都表現(xiàn)出更快的收斂速度，在f2(x)、f3(x)、f5(x)、f6(x) 上都得到了很好的性能表現(xiàn)，

圖4 收斂曲線

其產生收斂的迭代次數(shù)也是最少的。尤其在兩個多峰函數(shù)上，由于具有多個極值點，波峰不定，算法的搜索過程容易到達局部最優(yōu)而無法進化。MHIHHO通過引入基于混合柯西與拉普拉斯變異的動態(tài)擾動機制能夠使算法具備跳離局部最優(yōu)的能力，提高多峰函數(shù)中的尋優(yōu)性能。

(3)種群分布對比。選取基準函數(shù)Schwefel2.21進行實驗，觀察算法在迭代100次、200次和400次時種群個體在搜索空間內的分布，種群規(guī)模設為30。如圖5是不同時期算法種群個體的分布圖。HHO和IGWO在3個不同的迭代時期中，個體在搜索空間內一直處于比較分散的狀態(tài)。迭代后期，甚至一些個體離最優(yōu)解區(qū)域依然相隔較遠，已經陷入局部最優(yōu)而無法脫離，這表明算法本身搜索性能還有待提升。相比而言，改進算法QRHHO全局收斂性能更好，迭代后期一些個體已經聚集在最優(yōu)解區(qū)域，表明算法中采用的偽反射學習機制使HHO種群實現(xiàn)了一定的信息交互，提升了算法搜索精度。MHIHHO總體上在迭代前、中、后期具備更好的分布，前期比較分散，保證種群多樣性，中期逐步聚集于最優(yōu)解附近，后期多數(shù)個體已經逐步收斂于最優(yōu)解或鄰近區(qū)域。MHIHHO通過混合多策略改進思路對HHO的改進是行之有效的。

圖5 種群個體分布

4.2 WSN節(jié)點覆蓋優(yōu)化實驗

令監(jiān)測區(qū)域大小S=100 m×100 m， 部署的WSN傳感節(jié)點總數(shù)V=30，節(jié)點感知半徑r=12 m，通信半徑R=24 m。仿真平臺為Matlab2019a。選擇標準哈里斯鷹優(yōu)化算法HHO[4]、改進灰狼優(yōu)化算法IGWO[12]、改進哈里斯鷹優(yōu)化算法QRHHO[16]與本文的MHIHHO算法進行性能比較。

(1)WSN節(jié)點分布對比。圖6為分別利用HHO算法、IGWO算法、QRHHO算法和MHIHHO算法求解WSN節(jié)點部署位置后得到的區(qū)域覆蓋優(yōu)化情況，圖中黑實心點代表一個傳感器節(jié)點的部署坐標，而圓形弧線區(qū)域則代表相應傳感器節(jié)點所覆蓋的范圍，數(shù)字為傳感器節(jié)點的編號。可以看到，HHO算法得到的節(jié)點部署結果中，節(jié)點分布均勻性較差，存在多個覆蓋盲區(qū)，而部分區(qū)域又存在節(jié)點密度過高、覆蓋重復和冗余較大的問題，說明其尋優(yōu)性能還有待改進。IGWO算法經過節(jié)點位置和使用節(jié)點數(shù)量的優(yōu)化后，區(qū)域覆蓋更加均勻，明顯減少了高密度節(jié)點覆蓋區(qū)域，區(qū)域覆蓋率有所提高，但依然存在一些覆蓋空洞。利用本文的MHIHHO算法進行節(jié)點覆蓋優(yōu)化后，節(jié)點分布更加均勻，節(jié)點使用數(shù)量又進一步降低，幾乎不產生任何冗余節(jié)點和高密度重復覆蓋區(qū)域，覆蓋率接近于100%。

圖6 傳感節(jié)點部署

(2)WSN節(jié)點組網拓撲對比?；趫D6所得的WSN節(jié)點分布，利用普里姆算法構建最小生成樹，結果如圖7所示。在節(jié)點通信距離均勻性上，MHIHHO優(yōu)于對比算法。同時，在MHIHHO所構建的WSN通信網絡中，承接數(shù)據聚合的匯聚節(jié)點能夠更好地分布在區(qū)域邊緣，避免了中心位置，這樣避免了長距離數(shù)據傳輸，降低了遠距離數(shù)據傳送的能耗。綜合來看，智能優(yōu)化算法能夠一定程度上以提高網絡覆蓋率為目標優(yōu)化節(jié)點的位置，但MHIHHO的平均通信距離分布更加均勻，匯聚節(jié)點分布更佳。

圖7 WSN節(jié)點組網

(3)覆蓋率對比。圖8是算法迭代過程中，覆蓋率的變化收斂曲線。可以看到，首先，從迭代完成后的最終區(qū)域覆蓋率上講，MHIHHO算法的覆蓋率接近于100%，是4種算法中最高。QRHHO算法、IGWO算法和HHO算法的覆蓋率分別達到93.6%、91.8%和83.2%，之所以無法進一步提高覆蓋率，在于此時算法在求解最佳節(jié)點部署位置時已經得到局部最優(yōu)解，該結果也驗證MHIHHO算法在求解精度上得到有效提升。同時，從得到相同覆蓋率所使用的迭代次數(shù)上看，MHIHHO明顯使用了更少的迭代次數(shù)，說明算法的進化速度更快，在相同條件下，能夠以相同數(shù)量節(jié)點得到更高的區(qū)域覆蓋率，節(jié)點部署位置更精確。圖9展示WSN節(jié)點部署數(shù)量對覆蓋率的影響。隨著部署節(jié)點數(shù)量的增加，區(qū)域覆蓋率都有所增加，但從覆蓋率增漲速度上看，MHIHHO算法明顯更快，并且在相同部署數(shù)量下，該算法的覆蓋率也是最高的。此外，當部署節(jié)點較少時，在相對廣闊的監(jiān)測區(qū)域內，較少節(jié)點幾乎不存在交叉覆蓋區(qū)域，所有4種算法的覆蓋率比較接近。但增加節(jié)點數(shù)量后，MHIHHO算法的覆蓋率明顯增加的更快，在160個節(jié)點數(shù)時，已經接近于完全覆蓋，說明算法不僅求解精度更高，而且收斂速度更快，可更少部署節(jié)點數(shù)得到更高的區(qū)域覆蓋率。

圖8 覆蓋率隨迭代變化

圖9 部署節(jié)點數(shù)量對覆蓋率的影響

(4)WSN生存時間對比。圖10是利用Leach作為組網協(xié)議，網絡工作后節(jié)點數(shù)量的變化情況。節(jié)點初始能量為0.5 J，采用常規(guī)能耗模型計算能耗[22]。由結果可知，MHIHHO算法的節(jié)點死亡慢于HHO算法、IGWO算法和QRHHO算法，若節(jié)點分布均勻性差，會導致冗余節(jié)點多，從而加快能耗。而未覆蓋區(qū)域數(shù)據中繼傳輸過多同樣會加快節(jié)點能耗。MHIHHO的數(shù)據傳輸距離均勻，遠距離傳輸和近距離的冗余傳輸更少，節(jié)點工作時間更長，可以延長網絡生存時間。

圖10 網絡生存時間

表3是覆蓋所有目標點時不同算法所需要的節(jié)點數(shù)的比較情況。仍然以30個傳感節(jié)點進行部署，在完成相同覆蓋率的情況下，對比各算法所使用的節(jié)點數(shù)量情況。從結果中可以看到，在完成相同區(qū)域覆蓋率的情況下，MHIHHO算法能夠以更少數(shù)量的傳感器節(jié)點進行部署，說明算法所利用的對節(jié)點位置的搜索機制能夠得到最佳的坐標，盡可能地減少了交叉覆蓋的情況。對比算法由于存在對區(qū)域的冗余覆蓋，導致相同數(shù)據的節(jié)點部署下得到的覆蓋率相對較低。綜合說明改進算法能夠求解到最優(yōu)的節(jié)點部署位置，以更少的部署節(jié)點得到更高的區(qū)域覆蓋率。

表3 節(jié)點使用數(shù)量對比

MHIHHO算法時間復雜度分析。令種群規(guī)模為n，搜索維度為d，算法迭代總次數(shù)為Tmax。種群初始化階段的時間復雜度為O(nd)， 執(zhí)行精英個體對立學習過程的最大時間復雜度為O(nd)。 接著算法需要以4種不同的方式更新個體位置，且該過程需要迭代Tmax次。該過程的時間復雜度為O(ndTmax)。 個體變異時間復雜度為O(ndTmax)。 則MHIHHO時間復雜度為O(nd+nd+ndTmax+ndTmax)=O(ndTmax)。

5 結束語

本文提出一種多策略混合改進哈里斯鷹算法的WSN節(jié)點覆蓋優(yōu)化算法。首先，為了提高標準哈里斯鷹算法HHO的尋優(yōu)性能，引入Fuch無限折疊混沌初始化、自適應精英個體對立學習、正余弦優(yōu)化、柯西/拉普拉斯變異對算法進行改進。應用改進算法求解WSN節(jié)點覆蓋優(yōu)化，以覆蓋率最大為目標，求解節(jié)點最佳位置。結果表明，改進算法實現(xiàn)了預期結果，能夠優(yōu)化網絡覆蓋率。未來研究方向可進一步改善哈里斯鷹算法的全局搜索能力，在尋優(yōu)廣度和精度做一些改進，從而達到覆蓋率的最大提升。