唐菁敏，曲文博，蘇慧慧，鄭錦文

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

無(wú) 線 傳 感 器 網(wǎng) 絡(luò) （Wireless Sensor Network，WSN）[1]是一種分布式網(wǎng)絡(luò)，在能量供應(yīng)和通信能力上具有一定局限性. 網(wǎng)絡(luò)覆蓋是網(wǎng)絡(luò)獲知物理環(huán)境信息的能力[2-3]，為了將傳感器節(jié)點(diǎn)覆蓋在整個(gè)任務(wù)區(qū)并優(yōu)化整體網(wǎng)絡(luò)服務(wù)質(zhì)量，因此覆蓋優(yōu)化成為研究熱點(diǎn)[4]. 在覆蓋優(yōu)化方面的算法研究近幾年主要分為兩大方向，一種是靜態(tài)覆蓋的算法，如自適應(yīng)休眠（Probing Environment and Adaptive Sleeping,PEAS）算法[5]、Ditian算法[6]和地理密度控制(Optimal Geographical Density Control, OGDC)算法[7]等；另一方面是動(dòng)態(tài)覆蓋，主要有虛擬力算法、計(jì)算幾何算法和智能優(yōu)化算法.

PEAS[5]通過(guò)相鄰節(jié)點(diǎn)來(lái)檢測(cè)自身節(jié)點(diǎn)的工作狀態(tài)，減少工作節(jié)點(diǎn)數(shù)目從而節(jié)約能量，但是網(wǎng)絡(luò)的穩(wěn)定性和節(jié)點(diǎn)能量的均衡程度并不理想. Ditian算法[6]屬于分布式算法的一種，根據(jù)節(jié)點(diǎn)之間的幾何關(guān)系來(lái)判斷該節(jié)點(diǎn)是否冗余，在保證網(wǎng)絡(luò)正常連通的情況下，冗余節(jié)點(diǎn)可以處于休眠狀態(tài)，降低能耗，但是沒(méi)有把周?chē)?jié)點(diǎn)對(duì)其帶來(lái)的貢獻(xiàn)考慮在內(nèi)，因此準(zhǔn)確性會(huì)降低. OGDC算法[7]覆蓋率不理想，容易陷入局部最優(yōu). 智能優(yōu)化算法方向的研究也有很多，博弈算法的覆蓋控制[8]針對(duì)節(jié)點(diǎn)冗余造成的能量效率低下問(wèn)題，提出了網(wǎng)絡(luò)覆蓋率和節(jié)點(diǎn)剩余能量組合的收益函數(shù)，保證了網(wǎng)絡(luò)生命周期和覆蓋率，但在實(shí)現(xiàn)完全覆蓋、改進(jìn)局部最優(yōu)方面仍需要改善. 解決覆蓋優(yōu)化問(wèn)題方面，布谷鳥(niǎo)搜索算法[9]和人工蜂群算法[10]等都有待提高. 近期提出的群體智能優(yōu)化算法蟻獅算法[11]改善了局部最優(yōu)的不足之處，相比于其他群智能優(yōu)化算法，算法在應(yīng)用解決覆蓋問(wèn)題時(shí)其有收斂快、節(jié)點(diǎn)存活時(shí)間長(zhǎng)的優(yōu)點(diǎn).

本文針對(duì)優(yōu)化覆蓋率，基于群體智能的帝企鵝優(yōu)化算法[12]提出了帝企鵝改進(jìn)差分算法（Emperor Penguin Difference Algorithm，EPDEA）. EPDEA 根據(jù)帝企鵝冬季取暖的集群行為，首先確定帝企鵝集群過(guò)程中所圍成的邊界范圍；其次根據(jù)集群過(guò)程中不同的梯度位置取暖環(huán)境的溫度是不同的，定義集群不同梯度的溫度；最后，計(jì)算隨機(jī)的帝企鵝與集群中心帝企鵝的距離，由于集群過(guò)程中帝企鵝的位置不斷變化，函數(shù)不斷地對(duì)集群中心的帝企鵝位置進(jìn)行更新，更新過(guò)程中結(jié)合差分進(jìn)化算法，在經(jīng)過(guò)變異、交叉、選擇之后，對(duì)最優(yōu)位置的帝企鵝更新，避免陷入局部最優(yōu).

1 節(jié)點(diǎn)與覆蓋模型

WSN中假設(shè)傳感節(jié)點(diǎn)的感知半徑為R′，節(jié)點(diǎn)集合定義為Z= {z1,z2,···,zi,···,zN}，zi的位置坐標(biāo)為(xj,yj),i=1,2,···,N，分布在邊長(zhǎng)為R六邊形區(qū)域內(nèi)，為了方便計(jì)算，將監(jiān)測(cè)區(qū)域離散化為邊長(zhǎng)為S的六邊形的覆蓋網(wǎng)格，每個(gè)網(wǎng)格點(diǎn)的幾何中心點(diǎn)即覆蓋優(yōu)化目標(biāo)的位置. 其集合為Qj=(xj,yj),j∈{1,2,3,···,M}，其中為覆蓋區(qū)域的面積[13]，節(jié)點(diǎn)zi與網(wǎng)格中心點(diǎn)Qj的距離定義為

當(dāng)R′≤V(zi,Qj) 時(shí)，目標(biāo)點(diǎn)被傳感器節(jié)點(diǎn)檢測(cè)到概率為p(zi,Qj)=0，此時(shí)認(rèn)定Qj已經(jīng)被網(wǎng)絡(luò)覆蓋.

當(dāng)R′?Re＜V(zi,Qj)＜R′時(shí)，目標(biāo)點(diǎn)被傳感器節(jié)點(diǎn)檢測(cè)到概率為

其中，Re為節(jié)點(diǎn)感知誤差，λ 為感知衰減系數(shù)，此時(shí)認(rèn)定Qj未被網(wǎng)絡(luò)覆蓋.

當(dāng)R′?Re＞V(zi,Qj) 時(shí)，目標(biāo)點(diǎn)被傳感器節(jié)點(diǎn)檢測(cè)到概率為p(zi,Qj)=1，此時(shí)認(rèn)定Qj未被網(wǎng)絡(luò)覆蓋.

當(dāng)目標(biāo)點(diǎn)被多個(gè)傳感器感知，此時(shí)對(duì)目標(biāo)點(diǎn)來(lái)說(shuō)聯(lián)合檢測(cè)概率為

所有傳感器節(jié)點(diǎn)對(duì)待檢測(cè)區(qū)域的覆蓋率可以表示為

式（4）便是WSN覆蓋模型的優(yōu)化目標(biāo). 若待測(cè)區(qū)域中兩個(gè)節(jié)點(diǎn)的距離小于等于感知半徑，此時(shí)的通信路徑默認(rèn)為有且僅有一條. 保證不同的節(jié)點(diǎn)i，j之間連通，需定義通信路徑數(shù)量Ti,j≥ 1，同時(shí)要保(證所)有節(jié)點(diǎn)位置要處于待測(cè)的六邊形面積中，即ZQj∈M.

綜上所述目標(biāo)函數(shù)可以表達(dá)為

2 差分進(jìn)化算法

變異算子是差分算法(Difference Algorithm,DE)算法的主要算子[14]，是將個(gè)體種群進(jìn)行交叉、變異、選擇產(chǎn)生后代個(gè)體，如果后代的個(gè)體優(yōu)于父代的個(gè)體將會(huì)進(jìn)行替換，在進(jìn)化的過(guò)程中涉及的參數(shù)主要有種群規(guī)模NP，變異縮放因子F，以及交叉因子CR.

2.1 變異操作DE在經(jīng)過(guò)差分方式后完成個(gè)體的變異，在當(dāng)前種群中隨機(jī)選取兩個(gè)不相同的個(gè)體，將他們向量差分縮放后和另外的待變異個(gè)體進(jìn)行向量運(yùn)算生成新的變異種群，個(gè)體Xit的變異個(gè)體函數(shù)

2.2 交叉操作交叉操作是根據(jù)交叉因子CR， 將變異個(gè)體和父代個(gè)體帶入式（7）得到試驗(yàn)新個(gè)體

其中，jrand是在 [1 ,D]內(nèi)隨機(jī)選擇的整數(shù).

2.3 選擇操作DE 算 法的選擇操作采用的是“貪婪”選擇策略，即在父代個(gè)體和實(shí)驗(yàn)品個(gè)體之間選擇適應(yīng)度更優(yōu)的個(gè)體作為下一代的種群個(gè)體，以迭代進(jìn)入下一輪的操作.

3 帝企鵝算法

目前，關(guān)于帝企鵝算法在國(guó)內(nèi)外研究較少，在文獻(xiàn)[12]中對(duì)該算法進(jìn)行了分析，并且與常見(jiàn)的粒子群算法、螢火蟲(chóng)算法進(jìn)行了對(duì)比分析. 帝企鵝從事各種活動(dòng)，如狩獵、群體覓食，是群居性動(dòng)物[15].每當(dāng)惡劣的氣候來(lái)臨，它們會(huì)擠在一起防風(fēng)御寒.帝企鵝在南極極端冬季期間主要以集群的方式互相取暖來(lái)度過(guò)?40 ℃的冬季. 為了保證每只企鵝都能取暖，因此每只企鵝都在平等地做出貢獻(xiàn)，同時(shí)它們的社交行為極為團(tuán)結(jié)以及分工明確. 集群的行為[12]可歸納如下.

3.1 確定集群邊界范圍設(shè)定在帝企鵝蜷縮取暖的過(guò)程中所選擇的位置范圍在多邊形的網(wǎng)格范圍內(nèi)，帝企鵝在聚集的過(guò)程中至少與兩只以上的帝企鵝相鄰，鄰居的選擇是隨機(jī)的；而在帝企鵝集群過(guò)程中范圍的邊界是不規(guī)則的多邊形，因此用圍繞住帝企鵝集群的風(fēng)的梯度來(lái)表示整體集群的邊界，在此定義風(fēng)速 γ和其梯度 α、 β ，集群邊界 μ ，可表示為

3.2 計(jì)算集群層次周?chē)臏囟饶蠘O嚴(yán)酷的外界環(huán)境使得帝企鵝在遷徙過(guò)程中面對(duì)寒冷天氣會(huì)采取集群取暖來(lái)保持溫度. 若當(dāng)前聚集半徑d＞0.5時(shí)，其溫度W=0；當(dāng)d＜0.5 時(shí)，其溫度W=1. 溫度梯度曲線可以描述為

其中，tmax為最大迭代次數(shù)，x為當(dāng)前迭代次數(shù)，溫度W的表達(dá)式

3.3 計(jì)算帝企鵝間的距離在集群范圍內(nèi)帝企鵝間的距離表示為該個(gè)體與集群中心帝企鵝的距離，集群距離公式如下：

其中，Lep代表帝企鵝距中心距離；x表示當(dāng)前迭代數(shù)；Γ 和I用于帝企鵝體積設(shè)置的影響向量因子，避免個(gè)體間的沖突；Obest(x) 為x輪最優(yōu)解；Oep(x)表示當(dāng)前帝企鵝的位置向量；F() 定義帝企鵝的主體社會(huì)地位，負(fù)責(zé)區(qū)別最優(yōu)個(gè)體與普通個(gè)體. 向量Γ 和I計(jì)算如下：

其中 ，Bmove是移動(dòng)步長(zhǎng)參數(shù)，這里Bmove的值設(shè)置為2.5，Pacc通過(guò)比較與最優(yōu)的差異來(lái)定義多邊形網(wǎng)格精度，而 Ra n dom([0,1]) 是一個(gè)隨機(jī)函數(shù). 函數(shù)F(Γ)計(jì)算如下：

其中， ξ 和 φ 是控制參數(shù)，其值分別在（2,3）（1.5,2）的范圍內(nèi)能得出更好的結(jié)果.

3.4 帝企鵝位置更新帝企鵝集群中的個(gè)體通過(guò)向集群中心帝企鵝Q的方向移動(dòng)更新位置信息，其位置更新如下：

其中，Oep(x+1) 代表皇帝企鵝的下一個(gè)更新位置.在迭代過(guò)程中，一旦移動(dòng)者重新定位，帝企鵝的上述參數(shù)將被重新計(jì)算.

4 基于 EPDEA 的 WSN 覆蓋優(yōu)化

本文算法在對(duì)帝企鵝集群過(guò)程中不斷對(duì)中心帝企鵝位置的尋找定位，再在定位后的集群中心帝企鵝進(jìn)行差分變異中的變異交叉選擇，對(duì)最優(yōu)個(gè)體的位置的準(zhǔn)確度有很大的提升，算法優(yōu)化結(jié)束后輸出搜索到的適應(yīng)度值最優(yōu)的一個(gè)解，計(jì)算目標(biāo)函數(shù)中的覆蓋率最大值，得到傳感器節(jié)點(diǎn)的優(yōu)化方案.EPDEA覆蓋優(yōu)化流程圖如圖1所示.

圖 1 EPDEA 覆蓋優(yōu)化流程圖Fig. 1 EPDEA coverage optimization flowchart

針對(duì)WSN的覆蓋優(yōu)化，EPDEA的具體步驟如下：

步驟 1初始化帝企鵝種群參數(shù)

步驟 2根據(jù)目標(biāo)函數(shù)（5）計(jì)算搜索個(gè)體適應(yīng)度；

步驟 3根據(jù)式（8）（9）確定集群邊界；

步驟 4根據(jù)式（10）計(jì)算帝企鵝溫度曲線；

步驟 5根據(jù)（12）～（16）更新帝企鵝與集群中心的距離；

步驟 6根據(jù)式（17）進(jìn)行搜索個(gè)體位置更新；

步驟 7根據(jù)差分進(jìn)化算法中公式（6）、（7）對(duì)搜索個(gè)體進(jìn)行變異、交叉、選擇；

步驟 8判斷是否到達(dá)終止條件，否則返回步驟3.

5 實(shí)驗(yàn)仿真

5.1 仿真環(huán)境仿真情況將針對(duì)節(jié)點(diǎn)數(shù)N=25和N=50的兩種情況下分別進(jìn)行分析.

傳感器節(jié)點(diǎn)數(shù)為N=25時(shí)，將傳感器節(jié)點(diǎn)離散分布在蜂窩六邊形中，六邊形邊長(zhǎng)S=18 m，此時(shí)每個(gè)傳感器的感知半徑R′=4 m；傳感器節(jié)點(diǎn)數(shù)為N=50時(shí)，將傳感器節(jié)點(diǎn)離散分布在蜂窩六邊形中，六邊形邊長(zhǎng)S=24 m，此時(shí)每個(gè)傳感器的感知半徑與上述情況相同R′=4 m. 如圖 2 (a)、2(b)分別為傳感器節(jié)點(diǎn)數(shù)為N=25和N=50時(shí)的初始節(jié)點(diǎn)分布.

圖 2 初始節(jié)點(diǎn)分布情況Fig. 2 The distribution of initial nodes

5.2 算法覆蓋率對(duì)比EPDEA 在 測(cè)試區(qū)域 W SN的覆蓋優(yōu)化中相關(guān)參數(shù)設(shè)置如下：F∈[0.5,1],φ∈[2,2.5],tmax= 100. 圖 3 (a)、3(b)分別是傳感器節(jié)點(diǎn)數(shù)為N=25和N=50的情況下EPDEA運(yùn)行后的結(jié)果，明顯達(dá)到了覆蓋優(yōu)化的目的.

圖 3 優(yōu)化后節(jié)點(diǎn)分布情況Fig. 3 Nodes distribution after optimization

5.3 算法性能分析將 E PDEA 與 參考文獻(xiàn) [ 12]所提算法的覆蓋優(yōu)化率進(jìn)行比較. 本文所采取的待測(cè)區(qū)域?yàn)榱呅?，以六邊形的重心為坐?biāo)軸原心位置建立坐標(biāo)軸，在此情況下給出不同傳感器節(jié)點(diǎn)的位置坐標(biāo). 經(jīng)過(guò)仿真對(duì)比，本文所提出的EPDEA在傳感器節(jié)點(diǎn)數(shù)N=25的情況下，邊長(zhǎng)S=24 m，此時(shí)的待測(cè)面積為節(jié)點(diǎn)的分布密度約為3%，所提算法的覆蓋率達(dá)到97%. 參考文獻(xiàn)[12]中待測(cè)區(qū)域面積為50 m×50 m的正方形面積，節(jié)點(diǎn)數(shù)為45時(shí)的分布密度為2.8%，如圖4所示，此時(shí)的覆蓋率與未改進(jìn)的情況下覆蓋率接近重疊，當(dāng)節(jié)點(diǎn)數(shù)達(dá)到45時(shí)，本文所提算法所達(dá)到的節(jié)點(diǎn)覆蓋率接近98%，可見(jiàn)本文所提出的EPDEA中在這種情況下略占優(yōu)勢(shì). 從圖5的收斂程度也可以看出EPDEA的明顯優(yōu)勢(shì)，當(dāng)?shù)螖?shù)為38時(shí)EPDEA已開(kāi)始收斂，IGWO算法則在迭代次數(shù)80時(shí)才接近收斂狀態(tài)，凸顯出EPDEA一定的優(yōu)勢(shì).

圖 4 節(jié)點(diǎn)數(shù)量與覆蓋率變化圖Fig. 4 Change in number of nodes and coverage

圖 5 平均適應(yīng)度收斂曲線圖Fig. 5 Convergence curve of average fitness

6 結(jié)束語(yǔ)

針對(duì)目前WSN中覆蓋優(yōu)化時(shí)遇到局部最優(yōu)、精度不高和收斂速度慢的問(wèn)題，提出EPDEA. 在檢測(cè)區(qū)域的設(shè)置方面，六邊形[16]的形狀相對(duì)三角形、正方形來(lái)講，檢測(cè)到的網(wǎng)絡(luò)特殊節(jié)點(diǎn)分布的可能性增大，對(duì)問(wèn)題的研究的提高了多樣性，一定程度上加強(qiáng)了算法全局搜索的能力. 該算法后期將帝企鵝集群現(xiàn)象中中心帝企鵝的最優(yōu)位置作為與目標(biāo)函數(shù)對(duì)應(yīng)的解決方向，針對(duì)帝企鵝在集群現(xiàn)象中的受風(fēng)力等不確定的因素影響邊界范圍，使得最后求出的最優(yōu)解精準(zhǔn)度提高. 關(guān)于該新算法的穩(wěn)定性以及適用的多場(chǎng)景性將是下一步研究方向.