基于改進(jìn)正弦余弦算法的無(wú)線傳感器節(jié)點(diǎn)部署優(yōu)化

何慶 徐欽帥 魏康園

摘 要：為了提高無(wú)線傳感器網(wǎng)絡(luò)（WSN）的性能，提出了一種基于改進(jìn)正弦余弦算法（ESCA）的節(jié)點(diǎn)部署優(yōu)化方法。首先，引入雙曲正弦調(diào)節(jié)因子和動(dòng)態(tài)余弦波權(quán)重系數(shù)，以平衡算法的全局探索與局部開(kāi)發(fā)能力;然后，提出了一種基于拉普拉斯和高斯分布的變異策略，避免算法陷入局部最優(yōu)。對(duì)于基準(zhǔn)函數(shù)的優(yōu)化實(shí)驗(yàn)結(jié)果表明，ESCA相比引力搜索算法、鯨魚(yú)優(yōu)化算法、基本正弦余弦算法（SCA）及其改進(jìn)算法具有更高的收斂精度和收斂速度。最后，將ESCA應(yīng)用于WSN節(jié)點(diǎn)部署優(yōu)化，結(jié)果表明其優(yōu)化覆蓋率相比改進(jìn)粒子群優(yōu)化算法、外推人工蜂群算法、改進(jìn)灰狼優(yōu)化算法和自適應(yīng)混沌量子粒子群算法分別提高了1.55個(gè)百分點(diǎn)、7.72個(gè)百分點(diǎn)、2.99個(gè)百分點(diǎn)和7.63個(gè)百分點(diǎn)，用更少節(jié)點(diǎn)便可達(dá)到相同目標(biāo)精度。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)部署;正弦余弦算法;雙曲正弦調(diào)節(jié)因子;拉普拉斯分布

Abstract： In order to improve the performance of Wireless Sensor Network （WSN）， a node deployment optimization method based on Enhanced Sine Cosine Algorithm （ESCA） was proposed. Firstly， hyperbolic sine regulatory factor and dynamic cosine wave weight coefficient were introduced to balance the global exploration and local exploitation capability of the algorithm. Then， a mutation strategy based on Laplacian and Gaussian distribution was proposed to avoid the algorithm falling into local optimum. The experimental results of benchmark function optimization show that， compared with gravitational search algorithm， whale optimization algorithm， basic Sine Cosine Algorithm （SCA） and improved algorithms， ESCA has better convergence accuracy and convergence speed. Finally， ESCA was applied to WSN node deployment optimization. The results show that， compared with enhanced particle swarm optimization algorithm， extrapolation artificial bee colony algorithm， improved grey wolf optimization algorithm and self-adaptive chaotic quantum particle swarm algorithm， ESCA has improved the coverage rate by 1.55 percentage points， 7.72 percentage points， 2.99 percentage points and 7.63 percentage points respectively， and achieves the same target precision with fewer nodes.

Key words： Wireless Sensor Network （WSN）; node deployment; Sine Cosine Algorithm （SCA）; hyperbolic sine regulatory factor; Laplace distribution

0 引言

隨著無(wú)線通信技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）由于其低功耗、低成本、覆蓋范圍廣和集成功能多樣化的優(yōu)點(diǎn)[1]，被廣泛應(yīng)用于智能醫(yī)療[2-3]、城市交通管理[4]、農(nóng)業(yè)生產(chǎn)輔助[5]等多種領(lǐng)域。已知WSN的網(wǎng)絡(luò)感知、監(jiān)視和通信等服務(wù)質(zhì)量的優(yōu)劣在很大程度上取決于其傳感器節(jié)點(diǎn)部署性能的好壞，而該性能同時(shí)影響著網(wǎng)絡(luò)生存期及其資源管理質(zhì)量，因此，研究WSN傳感器節(jié)點(diǎn)的部署優(yōu)化方案，對(duì)于其網(wǎng)絡(luò)性能和服務(wù)質(zhì)量的提高具有重要意義。

針對(duì)WSN節(jié)點(diǎn)部署問(wèn)題，近年來(lái)國(guó)內(nèi)外學(xué)者將智能優(yōu)化算法應(yīng)用其中，提出了許多覆蓋優(yōu)化方法。如：Xu等[6]將WSN能耗最小化、覆蓋最大化和能耗均衡化作為優(yōu)化目標(biāo)，提出了一種混合遺傳算法（Genetic Algorithm， GA）與差分進(jìn)化算法的多目標(biāo)優(yōu)化方法，有效提高了網(wǎng)絡(luò)節(jié)點(diǎn)部署性能;宋明智等[7]通過(guò)在虛擬力與粒子群優(yōu)化混合（Virtual Force Particle Swarm Optimization， VFPSO）算法中引入維度選擇機(jī)制，取得的覆蓋率相比原始算法提高了約5%;于文杰等[8]利用外推公式改進(jìn)人工蜂群（Extrapolation Artificial Bee Colony， EABC）算法，相比原始算法提高了覆蓋率及收斂速度，但其覆蓋率僅達(dá)到了90.86%，仍存在較大覆蓋盲區(qū);胡小平等[9]采用混沌初始化、非線性收斂因子和融合變異的混合策略改進(jìn)灰狼優(yōu)化（Improved Grey Wolf Optimization， IGWO）算法，相比原始算法覆蓋率提高了3.12%，但優(yōu)化后部分區(qū)域節(jié)點(diǎn)較為集中，分布不夠均勻;周海鵬等[10]將種群分布熵與平均粒距引入量子粒子群優(yōu)化算法中，提出了一種動(dòng)態(tài)自適應(yīng)混沌量子粒子群（Dynamic Self-Adaptive Chaotic Quantum-behaved PSO， DACQPSO）算法，其覆蓋效率相比原始算法及其改進(jìn)算法有所提高，但其87.15%的覆蓋率尚不夠理想，且邊界覆蓋盲區(qū)較大。上述方法雖然有效改善了WSN節(jié)點(diǎn)部署效率，但為了滿足實(shí)際應(yīng)用需求，其節(jié)點(diǎn)覆蓋率及均勻度仍需進(jìn)一步提高。

正弦余弦算法（Sine Cosine Algorithm， SCA）是一種新型智能優(yōu)化算法，由Mirjalili[11]于2016年提出。由于SCA具有初始參數(shù)少、結(jié)構(gòu)簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)，已被廣泛應(yīng)用于視覺(jué)目標(biāo)跟蹤[12]、電力系統(tǒng)最優(yōu)潮流優(yōu)化[13]等不同領(lǐng)域，且已有研究證明[11]，SCA的優(yōu)化性能均優(yōu)于GA、PSO算法和螢火蟲(chóng)算法等，因此，將SCA應(yīng)用于WSN節(jié)點(diǎn)部署優(yōu)化問(wèn)題的研究值得深入探索。然而，SCA仍存在收斂精度較低、易早熟收斂等缺陷[14]?；诖耍珽laziz等[15]將反向?qū)W習(xí)機(jī)制引入SCA中，提高了算法的全局搜索能力;Rizk-Allah[16]提出了一種混合SCA與多正交搜索策略的改進(jìn)算法，該算法首先利用SCA進(jìn)行全局探索，然后利用多正交搜索策略加強(qiáng)局部開(kāi)發(fā)能力，有效地改善了算法的收斂性能。盡管上述改進(jìn)算法各有優(yōu)勢(shì)，但是SCA早熟收斂、易陷入局部最優(yōu)等問(wèn)題尚未解決，實(shí)現(xiàn)全局探索與局部開(kāi)發(fā)能力的平衡仍是難題，其收斂性能有待改進(jìn)。

綜上所述，為了更好地利用SCA的尋優(yōu)機(jī)制求解WSN節(jié)點(diǎn)部署優(yōu)化問(wèn)題，本文提出了一種基于雙曲正弦調(diào)節(jié)因子、動(dòng)態(tài)余弦波慣性權(quán)重和混合變異策略的改進(jìn)正弦余弦算法（Enhanced Sine Cosine Algorithm， ESCA）。在仿真實(shí)驗(yàn)部分，首先利用改進(jìn)算法對(duì)8個(gè)基準(zhǔn)函數(shù)進(jìn)行優(yōu)化求解，并將其結(jié)果與基本SCA及其改進(jìn)算法[15-16]、引力搜索算法（Gravitational Search Algorithm， GSA）[17]和鯨魚(yú)優(yōu)化算法（Whale Optimization Algorithm， WOA）[18]進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)策略的有效性;然后，將該算法應(yīng)用于WSN節(jié)點(diǎn)部署優(yōu)化，選取參考文獻(xiàn)[7-10]中的4種改進(jìn)算法在相應(yīng)實(shí)驗(yàn)條件下進(jìn)行對(duì)比，驗(yàn)證了ESCA對(duì)于WSN的覆蓋優(yōu)化性能。

1 問(wèn)題模型

1.1 基本假設(shè)

由于在監(jiān)測(cè)區(qū)域內(nèi)傳感器節(jié)點(diǎn)是隨機(jī)分布的，目前WSN網(wǎng)絡(luò)配置面臨的最大問(wèn)題為區(qū)域覆蓋問(wèn)題，覆蓋率能夠反映區(qū)域的監(jiān)測(cè)和追蹤情況。目前的覆蓋優(yōu)化算法主要可分為連通性覆蓋算法、不規(guī)則覆蓋算法、空間覆蓋算法、多重覆蓋算法4種[19]。

在實(shí)際WSN中，障礙物的遮擋易導(dǎo)致無(wú)線信號(hào)發(fā)生不同程度的衰減，同時(shí)由于無(wú)線信號(hào)的時(shí)變性，使得WSN內(nèi)節(jié)點(diǎn)感知區(qū)域呈不規(guī)則性。然而，覆蓋與連通問(wèn)題是WSN覆蓋優(yōu)化算法中首先要面對(duì)和解決的問(wèn)題，覆蓋率和網(wǎng)絡(luò)連通性是評(píng)價(jià)WSN覆蓋優(yōu)化算法最基本的性能指標(biāo)[19]，因此，本文假設(shè)傳感器節(jié)點(diǎn)分布在規(guī)則的矩形區(qū)域中，專注于求解WSN網(wǎng)絡(luò)覆蓋率最大化問(wèn)題，并約定傳感器節(jié)點(diǎn)屬性如下：1）所有節(jié)點(diǎn)具有相同結(jié)構(gòu);2）節(jié)點(diǎn)部署后位置已知并且固定不變;3）每個(gè)節(jié)點(diǎn)可以實(shí)時(shí)感知并獲取在其通信半徑范圍內(nèi)其他節(jié)點(diǎn)的位置。

1.2 覆蓋模型

假設(shè)監(jiān)測(cè)區(qū)域?yàn)镾=L×L的二維正方形平面，在該區(qū)域內(nèi)隨機(jī)拋撒V個(gè)傳感器節(jié)點(diǎn)，定義為C={C1，C2，…，CV}，其中節(jié)點(diǎn)Ci的位置坐標(biāo)為（xi，yi）（i=1，2，…，V），且每個(gè)節(jié)點(diǎn)具有相同的感知半徑r和通信半徑R。

已知傳感器節(jié)點(diǎn)Ci的感知范圍是一個(gè)以（xi，yi）為中心、以r為半徑的封閉圓形區(qū)域。為了簡(jiǎn)化計(jì)算，將該區(qū)域離散化為m×n個(gè)像素點(diǎn)，定義為zj=（xj，yj）（j=1，2，…，m×n），其位置坐標(biāo)即為節(jié)點(diǎn)部署優(yōu)化目標(biāo)位置。

定義像素點(diǎn)位置zj與任一傳感器節(jié)點(diǎn)Ci之間的歐氏距離為d，如式（1）所示。若存在d≤r，則定義該像素點(diǎn)已被網(wǎng)絡(luò)覆蓋。

采用布爾測(cè)量模型作為節(jié)點(diǎn)感知模型，定義像素點(diǎn)zj被節(jié)點(diǎn)Ci感知的概率為：

其中：p（Ci，zj）為感知概率;r為傳感器節(jié)點(diǎn)的感知半徑。

在該監(jiān)測(cè)區(qū)域內(nèi)，任一像素點(diǎn)zj能夠同時(shí)被多個(gè)傳感器節(jié)點(diǎn)Ci所感知，則定義zj的聯(lián)合感知概率為：

其中：p（C，zj）為聯(lián)合感知概率;V為區(qū)域內(nèi)傳感器節(jié)點(diǎn)數(shù)目;C為監(jiān)測(cè)目標(biāo)點(diǎn)的傳感器節(jié)點(diǎn)集合。

已知區(qū)域節(jié)點(diǎn)部署覆蓋率即傳感器節(jié)點(diǎn)集合C所覆蓋的像素點(diǎn)數(shù)與區(qū)域內(nèi)所有像素點(diǎn)總數(shù)的比值，定義為：

其中pcov為區(qū)域覆蓋率。

因此，改進(jìn)正弦余弦算法應(yīng)用于WSN節(jié)點(diǎn)部署優(yōu)化的目標(biāo)函數(shù)即式（4），并求解其pcov最大值。

2 正弦余弦算法分析及改進(jìn)

2.1 基本正弦余弦算法

正弦余弦算法（SCA）原理簡(jiǎn)單易實(shí)現(xiàn)，僅利用正弦和余弦函數(shù)的性質(zhì)實(shí)現(xiàn)對(duì)搜索空間的全局探索與局部開(kāi)發(fā)，通過(guò)迭代進(jìn)化不斷優(yōu)化目標(biāo)函數(shù)解集。

假設(shè)種群規(guī)模為N，搜索空間維度為D，將優(yōu)化目標(biāo)問(wèn)題的每個(gè)解映射為搜索空間中每個(gè)個(gè)體的位置，則第i（i=1，2，…，N）個(gè)個(gè)體在D維搜索空間中的位置可表示為則第i（i=1，2，…，N）個(gè)個(gè)體在第D維空間此處應(yīng)該為“在第D維空間”吧？請(qǐng)明確?；貜?fù)：2.1節(jié)第2段。原內(nèi)容為“則第i（i=1，2，…，N）個(gè)個(gè)體在第D維空間中的位置可表示為...”，現(xiàn)修改為“則第i（i=1，2，…，N）個(gè)個(gè)體在D維搜索空間中的位置可表示為……”。

中的位置可表示為xi=（xi1，xi2，…，xiD）。首先，在搜索空間中隨機(jī)初始化N個(gè)個(gè)體位置;然后，根據(jù)目標(biāo)函數(shù)計(jì)算個(gè)體適應(yīng)度值;最后，選擇并保存當(dāng)代最優(yōu)個(gè)體適應(yīng)度值及其位置。在算法的每一次迭代中，個(gè)體根據(jù)式（5）更新位置：

其中：t為當(dāng)前迭代次數(shù);xtiD為第t次迭代時(shí)第i個(gè)個(gè)體在第D維空間中的位置;PtD為第t次迭代后算法在第D維空間的全局最優(yōu)值。

其中：a為正常數(shù);T為最大迭代次數(shù)。

2.2 改進(jìn)正弦余弦算法設(shè)計(jì)

2.2.1 基于雙曲正弦調(diào)節(jié)因子和動(dòng)態(tài)余弦波權(quán)重的位置更新

已知在基本SCA的位置更新式（5）中，當(dāng)r1sin（r2）或r1cos（r2）取值位于（1，2]∪[-2，-1）區(qū)間時(shí)，算法處于全局探索階段;當(dāng)其取值位于[-1，1]區(qū)間時(shí)，算法進(jìn)入局部開(kāi)發(fā)階段。其中，振幅調(diào)節(jié)因子r1作為關(guān)鍵參數(shù)，對(duì)于算法搜索方式的平衡起決定性作用。

由式（6）可知，原始r1為單調(diào)遞減的線性函數(shù)，在平衡算法的全局與局部搜索能力方面表現(xiàn)欠佳，因此，受啟發(fā)于雙曲正弦函數(shù)的波形變化，提出一種非線性振幅調(diào)節(jié)因子rsinh，定義為：

其中：λ和ω為調(diào)節(jié)系數(shù)，取值分別為λ=5，ω=0.01;θ為位移量，經(jīng)多次實(shí)驗(yàn)得知θ為1時(shí)，算法在基準(zhǔn)函數(shù)和WSN覆蓋中取得的優(yōu)化結(jié)果及標(biāo)準(zhǔn)差最優(yōu)，因此本文將其取值定義為θ=1。

從式（7）可以看出，rsinh與原始r1同樣是遞減函數(shù)，但基于雙曲正弦函數(shù)特性，rsinh在滿足迭代前期取值較大、后期取值減小條件的同時(shí)，其在算法初期遞減速度較緩慢，有利于個(gè)體在算法初期以較大的步長(zhǎng)搜索最優(yōu)解;在迭代后期，提高遞減速率，有利于算法在最優(yōu)值鄰域快速收斂。

進(jìn)一步，為了使當(dāng)代個(gè)體位置信息xtiD能隨著迭代次數(shù)而逐步被充分利用，受啟發(fā)于余弦函數(shù)波形曲線，提出一種動(dòng)態(tài)余弦波慣性權(quán)重k，使算法不局限于學(xué)習(xí)全局最優(yōu)值而提高收斂精度，定義為：

通過(guò)式（9）中遞減速率變化和動(dòng)態(tài)余弦波自調(diào)節(jié)機(jī)制，實(shí)現(xiàn)算法全局探索能力與局部開(kāi)發(fā)能力的平衡。

2.2.2 基于拉普拉斯分布和高斯分布的動(dòng)態(tài)混合變異

通過(guò)分析SCA基本原理可知，基于正弦和余弦函數(shù)的收斂機(jī)制，隨著算法迭代進(jìn)化，搜索個(gè)體將依據(jù)式（5）朝向精英個(gè)體PtD移動(dòng)，逐漸聚集于當(dāng)代最優(yōu)解鄰域，導(dǎo)致種群多樣性降低，易發(fā)生早熟收斂?；诖?，提出一種動(dòng)態(tài)混合變異策略，避免算法早熟陷入局部最優(yōu)，其實(shí)現(xiàn)流程如圖1所示。

首先，引入文獻(xiàn)[20]中提出的早熟收斂鑒定方法，以判斷算法是否已近似陷入局部極值。定義第t次迭代時(shí)所有個(gè)體的適應(yīng)度方差μt為：

其中： f ti為第i個(gè)個(gè)體在第t代的適應(yīng)度; f tmean為所有個(gè)體在第t代的總適應(yīng)度平均值; f tμ為μt的限定因子。 f tμ定義為：

其中：L為搜索空間的最大對(duì)角長(zhǎng)度;d為當(dāng)前搜索空間的維數(shù)，取值于[1，D];xtid為第i個(gè)個(gè)體在第t代時(shí)于第d維空間的位置;xtmean為所有個(gè)體在第t代時(shí)于第d維空間的位置平均值此處沒(méi)有d的標(biāo)識(shí)，且是否應(yīng)該刪除“第”字？請(qǐng)明確?；貜?fù)：2.2.2節(jié)第5段。原內(nèi)容為“d為當(dāng)前搜索空間的維數(shù)”，現(xiàn)修改為“d為當(dāng)前搜索空間的維度，取值于[1，D]”。

。

由于算法達(dá)到全局收斂或發(fā)生早熟收斂時(shí)，種群中個(gè)體都將聚集靠攏，即種群適應(yīng)度方差μt和個(gè)體間距δt取值均接近于0，因此，為了確實(shí)區(qū)分兩種收斂狀態(tài)，設(shè)當(dāng)μt<10-6且δt<10-3同時(shí)滿足時(shí)，則判定算法已陷入局部最優(yōu)。

最后，提出一種隨迭代次數(shù)動(dòng)態(tài)自適應(yīng)調(diào)整的拉普拉斯與高斯混合變異策略，能在判定算法近似早熟收斂的同時(shí)，使其有效跳出局部極值。

已知拉普拉斯分布[21]和高斯分布的概率密度函數(shù)分別定義為：

為了有效利用搜索空間中更多的隨機(jī)數(shù)，設(shè)拉普拉斯分布Lap（a，b）中參數(shù)a=1，b=2;高斯分布G（m，n）中參數(shù)m=0，n=1，因此，將基于動(dòng)態(tài)混合策略的變異更新式定義為：

已知拉普拉斯隨機(jī)數(shù)Lap（1，2）相比高斯隨機(jī)數(shù)G（0，1）有更大的波動(dòng)范圍，在式（16）中，Lap（1，2）的權(quán)重系數(shù)w1在前期取值相對(duì)較大，使算法能利用更多的隨機(jī)數(shù)，并以較大變異步長(zhǎng)在搜索空間中探索未知更優(yōu)解;在優(yōu)化后期，種群將收斂至最優(yōu)解鄰域，且隨著算法迭代進(jìn)化，w1逐漸減小，而G（0，1）的權(quán)重系數(shù)w2不斷增大，而G（0，1）較小的變異步長(zhǎng)，便于算法在最優(yōu)解鄰域搜索更優(yōu)解，在增強(qiáng)算法局部開(kāi)發(fā)能力的同時(shí)，對(duì)算法后期收斂速度影響較小，因此，混合變異策略通過(guò)迭代次數(shù)的動(dòng)態(tài)自調(diào)整，以避免算法陷入局部最優(yōu)。為了保證種群始終朝向更優(yōu)解方向移動(dòng)，判定近似發(fā)生早熟收斂現(xiàn)象之后，復(fù)制M個(gè)當(dāng)代最優(yōu)個(gè)體位置進(jìn)行混合變異操作，并從變異后個(gè)體選擇最優(yōu)個(gè)體進(jìn)入下一次迭代。

2.3 改進(jìn)算法復(fù)雜度分析

本文仿真實(shí)驗(yàn)針對(duì)相同的基準(zhǔn)函數(shù)和WSN監(jiān)測(cè)區(qū)域進(jìn)行優(yōu)化，為了簡(jiǎn)便計(jì)算，改進(jìn)算法以種群規(guī)模N和最大迭代次數(shù)T作為時(shí)間復(fù)雜度標(biāo)準(zhǔn)。

根據(jù)ESCA改進(jìn)策略，引入的雙曲正弦調(diào)節(jié)因子和動(dòng)態(tài)余弦波權(quán)重位置更新策略，增加了算法的時(shí)間復(fù)雜度為O（T·N）;同時(shí)，提出的早熟收斂判斷和動(dòng)態(tài)混合變異策略，其最差情況下的時(shí)間復(fù)雜度為O（N2），因此，ESCA的最高時(shí)間復(fù)雜度為O（N2）+O（T·N）。

3 WSN節(jié)點(diǎn)部署優(yōu)化

ESCA應(yīng)用于WSN節(jié)點(diǎn)部署優(yōu)化的目標(biāo)為求解網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)覆蓋率pcov的最大值;輸入為監(jiān)測(cè)區(qū)域參數(shù)：面積S、離散化像素點(diǎn)數(shù)m×n、傳感器節(jié)點(diǎn)數(shù)V、感知半徑r等，以及ESCA參數(shù)：種群規(guī)模N、最大迭代次數(shù)T、最優(yōu)個(gè)體復(fù)制數(shù)M;輸出為目標(biāo)函數(shù)pcov最優(yōu)適應(yīng)度值和優(yōu)化后節(jié)點(diǎn)分布坐標(biāo)。ESCA求解WSN節(jié)點(diǎn)部署優(yōu)化的具體算法步驟如下：

步驟1 輸入WSN網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域相關(guān)參數(shù)，以及ESCA的相關(guān)參數(shù)。

步驟2 隨機(jī)初始化ESCA的種群位置。

步驟3 初始化當(dāng)前迭代次數(shù)t=1。

步驟4 計(jì)算個(gè)體適應(yīng)度值，并記錄全局最優(yōu)個(gè)體位置PtD。

步驟5 根據(jù)式（7）和式（8）分別計(jì)算雙曲正弦調(diào)節(jié)因子值rsinh和動(dòng)態(tài)余弦波權(quán)重系數(shù)k。

步驟6 根據(jù)式（9）更新下一代種群中每個(gè)個(gè)體的位置。

步驟7 根據(jù)式（10）和式（11）分別計(jì)算種群適應(yīng)度方差μt和個(gè)體間距δt，并判斷是否發(fā)生早熟收斂現(xiàn)象（μt<10-6且δt<10-3），若是，則執(zhí)行步驟8;否則，跳至步驟10。

步驟8 復(fù)制M個(gè)當(dāng)代最優(yōu)個(gè)體，根據(jù)式（16）進(jìn)行動(dòng)態(tài)混合變異操作。

步驟9 計(jì)算M個(gè)變異個(gè)體和當(dāng)代最優(yōu)個(gè)體的適應(yīng)度值，從中選擇最優(yōu)個(gè)體進(jìn)入下一次迭代。

步驟10 更新當(dāng)前迭代次數(shù)t=t+1。

步驟11 判斷t是否達(dá)到最大迭代次數(shù)T，若是，則終止算法并輸出pcov最優(yōu)值和優(yōu)化后節(jié)點(diǎn)分布坐標(biāo);否則，跳至步驟4繼續(xù)循環(huán)迭代優(yōu)化。

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 基準(zhǔn)函數(shù)優(yōu)化實(shí)驗(yàn)

為了驗(yàn)證ESCA改進(jìn)策略的有效性，選取8個(gè)基準(zhǔn)函數(shù)進(jìn)行優(yōu)化實(shí)驗(yàn)，并將其實(shí)驗(yàn)結(jié)果與優(yōu)化性能較好的算法進(jìn)行對(duì)比，包括基本SCA、GSA、WOA、基于反向?qū)W習(xí)的SCA（Opposition-Based SCA， OBSCA）[15]和結(jié)合多正交搜索策略的SCA（Multi-Orthogonal SCA， MOSCA）[16]。仿真實(shí)驗(yàn)基于Windows 7（64bit）系統(tǒng)，編程采用Matlab R2015b軟件。

實(shí)驗(yàn)選取的基準(zhǔn)函數(shù)如表1所示，其中：f1～ f4為單峰函數(shù)， f5～ f8為多峰函數(shù)。為了測(cè)試實(shí)驗(yàn)的公平性，SCA、GSA、WOA和ESCA對(duì)于每個(gè)基準(zhǔn)函數(shù)均獨(dú)立運(yùn)行30次，取最優(yōu)適應(yīng)度的平均值、最小值和標(biāo)準(zhǔn)差進(jìn)行比較。同時(shí)，每個(gè)算法設(shè)置相同的種群規(guī)模N=30、最大迭代次數(shù)T=500和測(cè)試維度D=30。

表2和圖2分別為不同算法優(yōu)化基準(zhǔn)函數(shù)的數(shù)值結(jié)果和收斂曲線對(duì)比。從表2中可以看出，ESCA除對(duì)函數(shù)f5的收斂精度略低于MOSCA以外，其尋優(yōu)結(jié)果均優(yōu)于其他對(duì)比算法。

在單峰函數(shù)優(yōu)化方面，ESCA對(duì)于函數(shù)f1、f2、f3和f4的優(yōu)化結(jié)果均明顯優(yōu)于其他算法，尤其是對(duì)函數(shù)f1已取得了其理論最優(yōu)值，而對(duì)于函數(shù)f2、f3和f4的平均收斂精度相比基本SCA分別提高了293、304和4個(gè)數(shù)量級(jí)，且相比其他對(duì)比算法也有較大程度的提高，更優(yōu)的最小值和標(biāo)準(zhǔn)差值也表明該算法具有更好的優(yōu)化質(zhì)量和魯棒性。同時(shí)從圖2（a）～（d）可以看出，ESCA的收斂速度相比其他算法也具有明顯優(yōu)勢(shì)。

在多峰函數(shù)優(yōu)化方面，ESCA對(duì)函數(shù)f5的收斂精度略低于MOSCA，但相比其他對(duì)比算法有較大的提升，較小的標(biāo)準(zhǔn)差值也表明該算法具有較好的穩(wěn)定性;對(duì)于由余弦波調(diào)制成的連續(xù)函數(shù)f7，ESCA的收斂精度比基本SCA提高了17個(gè)數(shù)量級(jí);而對(duì)于典型非線性多峰函數(shù)f6和f8，已知其具有大量局部極值點(diǎn)，而且峰形起伏不定，搜索達(dá)到其最優(yōu)區(qū)域較為困難，但由于早熟鑒定方法和動(dòng)態(tài)混合變異策略的引入，使ESCA能夠有效避免陷入局部極值，提升多峰優(yōu)化性能，從而對(duì)函數(shù)f6和f8均取得了其理論最優(yōu)值。同時(shí)，從圖2（f）～（h）可以看出，ESCA在迭代至30次左右便實(shí)現(xiàn)了收斂，表明改進(jìn)策略能夠有效提高算法的多峰收斂速度。

綜上所述，通過(guò)在不同形態(tài)函數(shù)上的優(yōu)化實(shí)驗(yàn)，結(jié)果表明ESCA相比GSA、WOA、基本SCA及其改進(jìn)算法，具有更高的收斂精度、更快的收斂速度和更好的魯棒性，驗(yàn)證了改進(jìn)策略的有效性及優(yōu)越性。

4.2 WSN節(jié)點(diǎn)部署優(yōu)化

4.2.1 實(shí)驗(yàn)設(shè)置

為了充分驗(yàn)證ESCA應(yīng)用于WSN節(jié)點(diǎn)部署優(yōu)化的有效性，選取文獻(xiàn)[7-10]中四種不同算法作為對(duì)比算法，在相同的無(wú)線傳感器網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域中部署同構(gòu)的傳感器節(jié)點(diǎn)，進(jìn)行覆蓋率及均勻度優(yōu)化結(jié)果的比較。實(shí)驗(yàn)環(huán)境設(shè)置與基準(zhǔn)函數(shù)優(yōu)化實(shí)驗(yàn)相同。

實(shí)驗(yàn)中，設(shè)置ESCA的種群規(guī)模為N=30，最大迭代次數(shù)為T=500;每組實(shí)驗(yàn)獨(dú)立運(yùn)行50次，取平均覆蓋率及第50次優(yōu)化的節(jié)點(diǎn)分布圖進(jìn)行對(duì)比結(jié)果展示。

4.2.2 與文獻(xiàn)[7]中改進(jìn)VFPSO算法對(duì)比

假設(shè)監(jiān)測(cè)區(qū)域?yàn)镾=30m×30m的二維正方形平面，將其離散化為31×31個(gè)像素點(diǎn)，并在該區(qū)域內(nèi)拋撒20個(gè)同構(gòu)傳感器節(jié)點(diǎn)，其感知半徑r=5m，通信半徑R=10m。優(yōu)化實(shí)驗(yàn)結(jié)果如表3和圖3所示。

由表3可知，ESCA對(duì)該區(qū)域進(jìn)行50次節(jié)點(diǎn)部署優(yōu)化后，取得的覆蓋率平均值、最優(yōu)值和最差值相比VFPSO算法分別提高了1.55個(gè)百分點(diǎn)、1.69個(gè)百分點(diǎn)和1.60個(gè)百分點(diǎn)，而且覆蓋率標(biāo)準(zhǔn)差相對(duì)較小，表明該算法優(yōu)化覆蓋率能夠較穩(wěn)定地維持在99.21%以上，并且從圖3（a）可以看出，該算法近似實(shí)現(xiàn)了區(qū)域完全覆蓋。

通過(guò)反復(fù)實(shí)驗(yàn)得知，利用ESCA在該區(qū)域內(nèi)部署16個(gè)傳感器節(jié)點(diǎn)所得覆蓋率便可達(dá)到98.04%，減小了4個(gè)節(jié)點(diǎn)的同時(shí)，取得了近似且高于VFPSO算法的覆蓋率，相應(yīng)節(jié)點(diǎn)分布如圖3（b）所示。

4.2.3 與文獻(xiàn)[8]中EABC算法對(duì)比

假設(shè)監(jiān)測(cè)區(qū)域?yàn)镾=100m×100m的二維正方形平面，將其離散化為101×101個(gè)像素點(diǎn)，并在該區(qū)域內(nèi)拋撒50個(gè)同構(gòu)傳感器節(jié)點(diǎn)，其感知半徑r=10m，通信半徑R=20m。優(yōu)化實(shí)驗(yàn)結(jié)果如表4和圖4所示。

從表4可以看出，ESCA對(duì)該區(qū)域的優(yōu)化結(jié)果比EABC算法提高了7.72個(gè)百分點(diǎn)，且圖4（a）表明該算法有效縮小了覆蓋盲區(qū)。文獻(xiàn)[8]指出EABC算法優(yōu)化覆蓋率達(dá)到90.86%平均僅需46個(gè)節(jié)點(diǎn)，而由表4可知，ESCA在該區(qū)域部署46個(gè)節(jié)點(diǎn)時(shí)，其覆蓋率可達(dá)到97.26%，相應(yīng)節(jié)點(diǎn)分布如圖4（b）所示。

通過(guò)反復(fù)實(shí)驗(yàn)可知，ESCA僅需在該區(qū)域部署40個(gè)節(jié)點(diǎn)，便可使覆蓋率達(dá)到91.02%，相比EABC算法節(jié)省了6個(gè)傳感器節(jié)點(diǎn)，且圖4（c）所示優(yōu)化后節(jié)點(diǎn)分布更加均勻。

4.2.4 與文獻(xiàn)[9]中IGWO算法對(duì)比

假設(shè)監(jiān)測(cè)區(qū)域?yàn)镾=50m×50m的二維正方形平面，將其離散化為51×51個(gè)像素點(diǎn)，并在該區(qū)域內(nèi)拋撒40個(gè)同構(gòu)傳感器節(jié)點(diǎn)，其感知半徑r=5m，通信半徑R=15m。優(yōu)化實(shí)驗(yàn)結(jié)果如表5和圖5所示。

由表5可知，ESCA優(yōu)化覆蓋率相比IGWO算法提高了2.99個(gè)百分點(diǎn)，圖5（a）所示為該算法優(yōu)化后的傳感器節(jié)點(diǎn)分布，相比文獻(xiàn)[9]中IGWO優(yōu)化分布更加均勻，改善了節(jié)點(diǎn)區(qū)域集中現(xiàn)象。

通過(guò)反復(fù)實(shí)驗(yàn)得知，ESCA在節(jié)點(diǎn)數(shù)為38時(shí)便取得了94.50%的覆蓋率，相比IGWO算法節(jié)省了2個(gè)傳感器節(jié)點(diǎn)，相應(yīng)優(yōu)化節(jié)點(diǎn)分布如圖5（b）所示。

4.2.5 與文獻(xiàn)[10]中DACQPSO算法對(duì)比

假設(shè)監(jiān)測(cè)區(qū)域?yàn)镾=20m×20m的二維正方形平面，將其離散化為20×20個(gè)像素點(diǎn)，并在該區(qū)域內(nèi)拋撒24個(gè)同構(gòu)傳感器節(jié)點(diǎn)，其感知半徑r=2.5m，通信半徑R=5m。優(yōu)化實(shí)驗(yàn)結(jié)果如表6和圖6所示。

表格（有表名）

由表6和圖6（a）可知，ESCA取得覆蓋率相比DACQPSO算法提高了7.63個(gè)百分點(diǎn)，很大程度上縮減了覆蓋盲區(qū)，而通過(guò)反復(fù)實(shí)驗(yàn)得知，ESCA僅部署21個(gè)節(jié)點(diǎn)便使覆蓋率達(dá)到了87.88%，相對(duì)減小了3個(gè)傳感器節(jié)點(diǎn)，而從圖6（b）可以看出，在相似覆蓋精度下，ESCA優(yōu)化節(jié)點(diǎn)分布改善了邊界盲區(qū)較大的問(wèn)題。

5 結(jié)語(yǔ)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中隨機(jī)節(jié)點(diǎn)部署方法的覆蓋盲區(qū)較大、分布不均勻等缺陷，本文提出了一種改進(jìn)的正弦余弦算法用于求解WSN的節(jié)點(diǎn)部署優(yōu)化問(wèn)題。該算法在個(gè)體位置更新式中引入了雙曲正弦調(diào)節(jié)因子和動(dòng)態(tài)余弦波權(quán)重系數(shù)，實(shí)現(xiàn)了全局探索能力與局部開(kāi)發(fā)能力的有效平衡;利用早熟鑒定方法對(duì)種群狀態(tài)進(jìn)行判別，并提出了一種混合拉普拉斯分布和高斯分布，且隨著迭代次數(shù)而自調(diào)整權(quán)重的變異策略，避免算法陷入局部極值，提高了算法的多峰優(yōu)化性能。在8個(gè)基準(zhǔn)函數(shù)上的優(yōu)化結(jié)果表明，相比基本SCA及其他對(duì)比算法，ESCA表現(xiàn)出更高的收斂精度和收斂速度，驗(yàn)證了改進(jìn)策略的有效性。最后，利用ESCA優(yōu)化WSN節(jié)點(diǎn)分布，在4組不同網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域中進(jìn)行部署優(yōu)化實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，相比其他改進(jìn)算法，ESCA對(duì)WSN優(yōu)化后的覆蓋率均有明顯提高，而且節(jié)點(diǎn)分布更加均勻;同時(shí)，在相同目標(biāo)精度下，該算法相比其他算法減小了傳感器節(jié)點(diǎn)數(shù)，降低了網(wǎng)絡(luò)整體成本，因此，本文提出的ESCA能有效提高WSN網(wǎng)絡(luò)性能。

基于SCA簡(jiǎn)單、快速、復(fù)雜度低等特點(diǎn)，下一步可利用其正弦余弦變換機(jī)制優(yōu)化其他群體智能算法，研究更加高效的WSN覆蓋優(yōu)化方法。

參考文獻(xiàn) （References）

[1] TRIPATHI A， GUPTA H P， DUTTA T， et al. Coverage and connectivity in WSNs： a survey， research issues and challenges [J]. IEEE Access， 2018， 6： 26971-26992.

[2] ALAIAD A， ZHOU L N. Patients adoption of WSN-based smart home healthcare systems： an integrated model of facilitators and barriers [J]. IEEE Transactions on Professional Communication， 2017， 60（1）： 4-23.

[3] ADAME T， BEL A， CARRERAS A， et al. CUIDATS： an RFID-WSN hybrid monitoring system for smart health care environments [J]. Future Generation Computer Systems， 2018， 78（Part 2）： 602-615.

[4] AGUIRRE E， LOPEZ-ITURRI P， AZPILICUETA L， et al. Design and implementation of context aware applications with wireless sensor network support in urban train transportation environments [J]. IEEE Sensors Journal， 2017， 17（1）： 169-178.

[5] CAICEDO-ORTIZ J G， DE-LA-HOZ-FRANCO E， ORTEGA R M， et al. Monitoring system for agronomic variables based in WSN technology on cassava crops [J]. Computers and Electronics in Agriculture， 2018， 145： 275-281.

[6] XU Y， DING O， QU R， et al. Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization [J]. Applied Soft Computing， 2018， 68： 268-282.

[7] 宋明智，楊樂(lè).改進(jìn)VFPSO算法于WSN節(jié)點(diǎn)隨機(jī)部署中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（2）：141-145，204.（SONG M Z， YANG L. Random deployment of sensor nodes using enhanced VFPSO algorithm [J]. Computer Engineering and Applications， 2016， 52（2）： 141-145， 204.）

[8] 于文杰，李迅波，羊行，等.外推人工蜂群算法在WSN部署優(yōu)化中的應(yīng)用研究[J].儀表技術(shù)與傳感器，2017（6）：158-160，164.（YU W J， LI X B， YANG H， et al. Extrapolation artificial bee colony algorithm research on deployment optimization in wireless sensor network [J]. Instrument Technique and Sensor， 2017（6）： 158-160， 164.）

[9] 胡小平，曹敬.改進(jìn)灰狼優(yōu)化算法在WSN節(jié)點(diǎn)部署中的應(yīng)用[J].傳感技術(shù)學(xué)報(bào)，2018，31（5）：753-758.（HU X P， CAO J. Improved grey wolf optimization algorithm for WSN node deployment [J]. Chinese Journal of Sensors and Actuators， 2018， 31（5）： 753-758.）

[10] 周海鵬，高芹，蔣豐千，等.自適應(yīng)混沌量子粒子群算法及其在WSN覆蓋優(yōu)化中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2018，38（4）：1064-1071.（ZHOU H P， GAO Q， JIANG F Q， et al. Application of self-adaptive chaotic quantum particle swarm algorithm in coverage optimization of wireless sensor network [J]. Journal of Computer Applications， 2018， 38（4）： 1064-1071.）

[11] MIRJALILI S. SCA： a sine cosine algorithm for solving optimization problems [J]. Knowledge-Based Systems， 2016， 96： 120-133.

[12] NENAVATH H， JATOTH R K. Hybridizing sine cosine algorithm with differential evolution for global optimization and object tracking [J]. Applied Soft Computing， 2018， 62： 1019-1043.

[13] ATTIA A F， EL-SEHIEMY R A， HASANIEN H M. Optimal power flow solution in power systems using a novel sine-cosine algorithm [J]. International Journal of Electrical Power and Energy Systems， 2018， 99： 331-343.

[14] 徐松金，龍文.求解高維優(yōu)化問(wèn)題的改進(jìn)正弦余弦算法[J].計(jì)算機(jī)應(yīng)用研究，2018，35（9）：2574-2577.（XU S J， LONG W. Improved sine cosine algorithm for solving high-dimensional optimization problems [J]. Application Research of Computers， 2018， 35（9）： 2574-2577）

[15] ELAZIZ M A， OLIVA D， XIONG S W. An improved opposition-based sine cosine algorithm for global optimization [J]. Expert Systems with Applications， 2017， 90： 484-500.

[16] RIZK-ALLAH R M. Hybridizing sine cosine algorithm with multi-orthogonal search strategy for engineering design problems [J]. Journal of Computational Design and Engineering， 2018， 5（2）： 249-273.

[17] RASHEDI E， NEZAMABADI-POUR H， SARYAZDI S. GSA： a gravitational search algorithm [J]. Information Sciences， 2009， 179（13）： 2232-2248.

[18] MIRJALILI S， LEWIS A. The whale optimization algorithm [J]. Advances in Engineering Software， 2016， 95： 51-67.

[19] 梅希薇.無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化算法的研究[D].無(wú)錫：江南大學(xué)，2017：2-3.（MEI X W. Research of coverage control optimization algorithm in wireless sensor network [D]. Wuxi： Jiangnan University， 2017： 2-3.）

[20] DAI Y S， WEI Y Q， CHEN J， et al. Seismic wavelet estimation based on adaptive chaotic embedded particle swarm optimization algorithm [C]// Proceedings of the 2012 5th International Symposium on Computational Intelligence and Design. Piscataway， NJ： IEEE， 2012： 57-60.

[21] CUI J， WANG S S， WANG S Q， et al. Hybrid Laplace distribution-based low complexity rate-distortion optimized quantization [J]. IEEE Transactions on Image Processing， 2017， 26（8）： 3802-3816.