基于改進(jìn)遺傳算法的無(wú)線傳感網(wǎng)覆蓋優(yōu)化

胡國(guó)龍，賈振紅，覃錫忠，曹傳玲，牛洪梅

(1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046; 2.中國(guó)移動(dòng)通信集團(tuán) 新疆有限公司，烏魯木齊 830063)

?

基于改進(jìn)遺傳算法的無(wú)線傳感網(wǎng)覆蓋優(yōu)化

胡國(guó)龍1，賈振紅1，覃錫忠1，曹傳玲2，牛洪梅2

(1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046; 2.中國(guó)移動(dòng)通信集團(tuán) 新疆有限公司，烏魯木齊 830063)

為提高混合無(wú)線傳感器網(wǎng)絡(luò)(WSNs)的覆蓋率，將改進(jìn)的遺傳算法應(yīng)用到WSNs覆蓋優(yōu)化中，通過(guò)合理調(diào)整移動(dòng)節(jié)點(diǎn)的位置來(lái)提高網(wǎng)絡(luò)覆蓋率;針對(duì)傳統(tǒng)群體智能算法易“早熟”，最大迭代次數(shù)需試探設(shè)定等缺陷，提出了基于多個(gè)種群并行優(yōu)化的改進(jìn)遺傳算法;多個(gè)種群之間并不獨(dú)立，而是通過(guò)移民算子相互聯(lián)系；分別利用人工選擇算子與精華種群選擇并記錄各個(gè)種群每一代最優(yōu)染色體；并利用精華種群中保存的最優(yōu)染色體設(shè)計(jì)出新的進(jìn)化終止條件;仿真結(jié)果表明，改進(jìn)的遺傳算法不僅無(wú)需設(shè)定最大迭代次數(shù)而且收斂速度快，更兼有效地提高了WSNs的覆蓋率。

無(wú)線傳感器網(wǎng)絡(luò)；覆蓋；遺傳算法；移民算子；人工選擇算子

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)現(xiàn)在已經(jīng)被大規(guī)模應(yīng)用到軍事目標(biāo)跟蹤和監(jiān)視、人體健康監(jiān)測(cè)、智能家居控制等多個(gè)領(lǐng)域[1]。網(wǎng)絡(luò)覆蓋率是研究WSNs所面臨的首要問(wèn)題，同時(shí)也是衡量WSNs服務(wù)質(zhì)量的重要指標(biāo)[2]。近年來(lái)，應(yīng)用群體智能算法來(lái)優(yōu)化WSNs的覆蓋成為研究熱點(diǎn)[3-6]。文獻(xiàn)[3]將標(biāo)準(zhǔn)遺傳算法應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化中，研究結(jié)果表明該方法有一定的有效性，但是容易陷入未成熟收斂。文獻(xiàn)[4]將種子雜交算子引入粒子群算法中，一定程度上克服了標(biāo)準(zhǔn)粒子群算法易早熟等問(wèn)題，進(jìn)一步提高了WSNs的覆蓋性能。文獻(xiàn)[5]在傳統(tǒng)人工魚群算法中加入公告板記錄算子并對(duì)人工魚加入變異算子，來(lái)提高算法收斂到最優(yōu)解的概率，有利于網(wǎng)絡(luò)覆蓋率的提升。文獻(xiàn)[6]將差分進(jìn)化算法與人工蜂群算法相結(jié)合來(lái)解決差分進(jìn)化算法后期，種群多樣性低，個(gè)體陷入局部最優(yōu)而早熟的現(xiàn)象。上述研究，都不同程度地提高了經(jīng)典算法的性能以及WSNs的覆蓋率。然而以上算法存在共同的缺點(diǎn)：都是單個(gè)種群串行搜索尋優(yōu)，不同控制參數(shù)對(duì)尋優(yōu)結(jié)果影響很大，而且收斂速度比較低。算法的終止條件最大迭代次數(shù)需要人為設(shè)定，迭代次數(shù)設(shè)置太小，不能收斂到最優(yōu)值；而迭代次數(shù)如果設(shè)置過(guò)大，造成計(jì)算資源的浪費(fèi)。因此，需要能夠多個(gè)種群并行搜索的算法來(lái)減小不同控制參數(shù)對(duì)尋優(yōu)結(jié)果的影響。同時(shí)，充分利用迭代過(guò)程中知識(shí)的積累，設(shè)計(jì)更為合理的算法終止條件。針對(duì)上述研究存在的問(wèn)題，本文提出了一種改進(jìn)的遺傳算法進(jìn)一步優(yōu)化WSNs的覆蓋性能。

1 系統(tǒng)模型

假設(shè)傳感器網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域?yàn)楹?jiǎn)單的二維平面區(qū)域A，P個(gè)不可移動(dòng)節(jié)點(diǎn)(固定節(jié)點(diǎn))、Q個(gè)可移動(dòng)節(jié)點(diǎn)隨機(jī)播撒在監(jiān)測(cè)區(qū)域A。每個(gè)節(jié)點(diǎn)都能準(zhǔn)確獲知自己的位置，并且同一位置節(jié)點(diǎn)部署不重復(fù)，可移動(dòng)節(jié)點(diǎn)具有自移動(dòng)功能。固定節(jié)點(diǎn)與可移動(dòng)節(jié)點(diǎn)的性能相同，感知半徑均為r，通信半徑為R。集合S={S1，S2…, Si, …，SP+Q}代表部署的傳感器節(jié)點(diǎn)集合。節(jié)點(diǎn)Si={(xi,yi), r}可以覆蓋以(xi,yi)為圓心，以r為半徑的區(qū)域。將區(qū)域A離散化為(M(N)個(gè)像素點(diǎn)，當(dāng)某個(gè)像素點(diǎn)(x,y)在Si(i=1, 2,…,P+Q)的覆蓋區(qū)域內(nèi)，則稱該像素點(diǎn)被節(jié)點(diǎn)Si覆蓋。本文采用布爾感知模型，則像素點(diǎn)(x,y)被節(jié)點(diǎn)Si覆蓋的概率計(jì)算如下：

(1)

所以節(jié)點(diǎn)集的聯(lián)合測(cè)量覆蓋率為[7]

(2)

2 遺傳算法與改進(jìn)算法

2.1 標(biāo)準(zhǔn)遺傳算法

遺傳算法(genetic algorithm,GA)是模仿生物進(jìn)化過(guò)程中自然選擇現(xiàn)象的群體智能算法[8]。GA將優(yōu)化參數(shù)進(jìn)行編碼，生成染色體，然后利用選擇算子、交叉算子、變異算子來(lái)交換染色體攜帶的信息，通過(guò)多次重復(fù)上述操作最終獲得優(yōu)化函數(shù)所需的最優(yōu)染色體。具體算法描述如下：

1)種群初始化：隨機(jī)生成W個(gè)長(zhǎng)度相同的數(shù)組，將每個(gè)數(shù)組當(dāng)作一個(gè)染色體，W個(gè)染色體共同組成一個(gè)種群，把該種群作為進(jìn)化的初始種群。

2)適應(yīng)度函數(shù)：用來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣。本文把節(jié)點(diǎn)集的覆蓋率PC(S)作為適應(yīng)度函數(shù)，即PC(S)越大，表示該個(gè)體在種群中適應(yīng)性越強(qiáng)。

3)選擇算子:在當(dāng)前種群中選出適應(yīng)度較高的個(gè)體作為父代，使之以較大的概率繁殖下一代；對(duì)于當(dāng)前種群中適應(yīng)度較低的個(gè)體，則使之以較小的概率繁殖下一代。本文采用文獻(xiàn)[9]中所提的輪盤賭法確定個(gè)體被選中的概率。則第i個(gè)體被選擇的概率為

(3)

其中，F(xiàn)i代表第i個(gè)個(gè)體的適應(yīng)度，W代表該種群中個(gè)體總數(shù)。

4)交叉算子：在種群中任選一對(duì)染色體，通過(guò)交換部分染色體片段，產(chǎn)生新的優(yōu)秀個(gè)體。染色體am與染色體an在第k位上進(jìn)行交叉的具體方法為[10]

(4)

其中：b在區(qū)間[0,1]隨機(jī)產(chǎn)生。

5)變異算子：在種群中隨機(jī)挑選一個(gè)染色體，通過(guò)改變?cè)撊旧w中的某一位，產(chǎn)生新的染色體。染色體am在第k位上執(zhí)行變異操作的具體方法為

其中，amax、amin分別為染色體位amk的上界和下界。Z(c)=r2(1-c/Cmax)2，c代表當(dāng)前進(jìn)化代數(shù)，Cmax代表設(shè)定的最大進(jìn)化代數(shù)，r與r2都是在區(qū)間[0,1]中隨機(jī)產(chǎn)生。

2.2 改進(jìn)的遺傳算法

早熟現(xiàn)象是標(biāo)準(zhǔn)遺傳算法存在的一個(gè)重要缺陷[11]。主要有以下兩個(gè)原因：(1)交叉概率和變異概率對(duì)GA的收斂速度以及尋優(yōu)結(jié)果影響很大。它們分別決定了GA的全局搜索能力和局部搜索能力。不同的概率組合，尋優(yōu)結(jié)果差異非常大。為彌補(bǔ)這一缺點(diǎn)，本文改進(jìn)算法通過(guò)對(duì)多個(gè)種群設(shè)置多組不同組合的交叉概率與變異概率，讓其并行協(xié)同進(jìn)化。同時(shí)，各個(gè)種群之間并不是獨(dú)立的，而是用移民算子相互聯(lián)系，最終尋優(yōu)結(jié)果取所有種群協(xié)同進(jìn)化的最優(yōu)結(jié)果。(2)算法終止條件沒(méi)有理論指導(dǎo)，進(jìn)化代數(shù)設(shè)置過(guò)小，種群沒(méi)有充分進(jìn)化，造成早熟。本文引入人工選擇算子和精華種群來(lái)設(shè)計(jì)算法終止依據(jù)。具體改進(jìn)說(shuō)明如下：

移民算子：在種群協(xié)同進(jìn)化過(guò)程中，每隔幾代將一個(gè)種群中最優(yōu)的個(gè)體轉(zhuǎn)移到相鄰種群中，并且淘汰掉接收移民種群中適應(yīng)度最低的個(gè)體。

人工選擇算子：選出每個(gè)進(jìn)化代中各個(gè)種群最優(yōu)的個(gè)體。

精華種群：由各個(gè)種群中被人工選擇算子選出的最優(yōu)個(gè)體組成的新種群。精華種群不執(zhí)行標(biāo)準(zhǔn)遺傳算法的任何操作，只簡(jiǎn)單記錄每一代各個(gè)種群的最優(yōu)個(gè)體。本文算法終止的條件是精華種群中最優(yōu)個(gè)體保持代數(shù)是否達(dá)到設(shè)定值，這樣設(shè)計(jì)充分利用了種群進(jìn)化過(guò)程中積累的信息，避免不必要的迭代。

本文算法的結(jié)構(gòu)示意圖如圖1。開(kāi)始，N個(gè)種群并行執(zhí)行標(biāo)準(zhǔn)遺傳算法的基本操作；每進(jìn)化一代，各個(gè)種群通過(guò)人工選擇算子將最優(yōu)個(gè)體保存到精華種群中；每隔一定代數(shù)執(zhí)行一次移民操作，用源種群的最優(yōu)個(gè)體代替目標(biāo)種群的最差個(gè)體。循環(huán)執(zhí)行以上操作，直到精華種群中最優(yōu)個(gè)體保持代數(shù)達(dá)到設(shè)定值。

圖1 改進(jìn)遺傳算法流程圖

3 仿真結(jié)果與分析

假定WSNs的監(jiān)控區(qū)域?yàn)?0 m×20 m正方形二維平面區(qū)域，并將其離散化為20×20個(gè)正方形小柵格。所有傳感器節(jié)點(diǎn)的感知半徑均為2 m(即r=2 m)，通信半徑均為4 m(即R=4 m)。傳感器的可移動(dòng)節(jié)點(diǎn)個(gè)數(shù)為20個(gè)，通過(guò)調(diào)整可移動(dòng)節(jié)點(diǎn)的位置來(lái)覆蓋固定節(jié)點(diǎn)留下的空洞。

圖2、圖3中，實(shí)心三角形代表固定節(jié)點(diǎn)，以實(shí)心三角為圓心的圓域代表固定節(jié)點(diǎn)的監(jiān)測(cè)范圍；實(shí)心正方形代表可移動(dòng)節(jié)點(diǎn)，以實(shí)心正方形為圓心的圓域代表可移動(dòng)節(jié)點(diǎn)的監(jiān)測(cè)范圍。圖2是隨機(jī)撒點(diǎn)后形成的初始節(jié)點(diǎn)覆蓋圖，初始覆蓋率為56.5%。圖3為用本文所提算法優(yōu)化后的節(jié)點(diǎn)覆蓋分布圖，優(yōu)化后的覆蓋率為87.5%。通過(guò)圖2與圖3對(duì)比可知，可移動(dòng)節(jié)點(diǎn)通過(guò)調(diào)整自身位置，覆蓋了被監(jiān)測(cè)區(qū)域原來(lái)比較空曠的位置，使得整個(gè)被監(jiān)測(cè)區(qū)域的覆蓋率提高了31%。說(shuō)明應(yīng)用本文算法進(jìn)行WSNs覆蓋優(yōu)化不僅可行而且有效。

圖2 初始節(jié)點(diǎn)分布圖

圖3 本文算法優(yōu)化后節(jié)點(diǎn)分布圖

圖4 覆蓋率對(duì)比圖

算法的終止條件為精華種群中最優(yōu)個(gè)體最少保持代數(shù)為7。從圖4可以看出，標(biāo)準(zhǔn)遺傳算法和人工魚群算在迭代100次時(shí)覆蓋率分別為75.8%、77.3%。而本文所提算法在進(jìn)化到67代時(shí)滿足終止條件停止進(jìn)化，此時(shí)的覆蓋率高達(dá)87.5%?？梢?jiàn)，本文算法不僅收斂速率比另外兩種算法快，而且能有效克服早熟現(xiàn)象，同時(shí)有比較合理的迭代終止條件。

文獻(xiàn)[3]與文獻(xiàn)[4]都研究了衡量覆蓋算法性能的另一個(gè)指標(biāo)RD(RD=覆蓋率/平均移動(dòng)距離)。RD越大，表明算法性能越好。表1給出了不同移動(dòng)節(jié)點(diǎn)比例情況下，文獻(xiàn)[3]、文獻(xiàn)[4]和本文算法RD指標(biāo)對(duì)比結(jié)果。由表1可以看到，本文算法的RD值大于文獻(xiàn)[3]和文獻(xiàn)[4]所提算法的RD值。說(shuō)明本文所提算法在WSNs覆蓋優(yōu)化中的性能優(yōu)于另外兩種算法。

表1 RD指標(biāo)對(duì)比

4 結(jié)論

本文針對(duì)傳統(tǒng)群體智能算法單個(gè)種群串行尋優(yōu)容易早熟這一問(wèn)題，在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上引入多個(gè)種群進(jìn)行改進(jìn)，通過(guò)多個(gè)種群并行協(xié)同進(jìn)化不僅收斂速度快而且有效地克服了早熟這一缺陷。同時(shí)充分利用了種群進(jìn)化過(guò)程中積累的信息，設(shè)計(jì)出比是否達(dá)到最大迭代次數(shù)更為合理的算法終止條件。仿真結(jié)果顯示，將本文算法應(yīng)用到混合WSNs覆蓋優(yōu)化問(wèn)題中，能有效提高網(wǎng)絡(luò)的覆蓋性能。

[1]Joon W L,Ju J L. Ant-Colony-Based Scheduling Algorithm for Energy-Efficient Coverage of WSN[J]. IEEE Sensors Journal, 2012, 12(10): 36-46.

[2] Dimple B, Man J. Maximum Coverage Heuristics (MCH) for Target Coverage Problem in Wireless Sensor Network[A].2014 IEEE International Advance Computing Conference (IACC)[C]. IEEE , 2014:300-305 .

[3] 曾映蘭, 陳 靜, 鄭金華. 基于遺傳算法的WSN 覆蓋優(yōu)化方法[J]. 計(jì)算機(jī)工程與應(yīng)用 , 2009(11):89-98.

[4] 馮 琳, 冉曉旻, 梅關(guān)林. 基于改進(jìn)粒子群算法的無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化[J]. 太赫茲科學(xué)與電子信息學(xué)報(bào), 2015(3):486-496.

[5] 王明亮, 閔新力, 薛君志. 基于改進(jìn)人工魚群算法的WSN覆蓋優(yōu)化策略[J]. 微電子學(xué)與計(jì)算機(jī), 2015(6):78-81.

[6] 陳 樹, 錢 成. 一種多目標(biāo)的覆蓋優(yōu)化策略在WSNs 中的應(yīng)用[J]. 傳感器與微系統(tǒng), 2014(10):151-154.

[7] Zhang Y, Zhang X, Fu W, etal. HDRE: Coverage Hole Detection with Residual Energy in Wireless Sensor Networks[J]. Journal of Communications and Networks , 2014(5):493-501.

[8] 柯 俊， 史文庫(kù)， 錢 琛，等. 采用遺傳算法的復(fù)合材料板簧多目標(biāo)優(yōu)化方法[J]. 西安交通大學(xué)學(xué)報(bào),2015(8):1-7.

[9]艾小祥,俞慈君,方 強(qiáng),等.基于遺傳算法的機(jī)翼壁板掃描路徑優(yōu)化[J].浙江大學(xué)學(xué)報(bào),2015(3):448-456.

[10]孫雅庚,郭慶勝,劉遠(yuǎn)剛,等.顧及格式塔原則的建筑物群移位實(shí)數(shù)編碼遺傳算法[J].武漢大學(xué)學(xué)報(bào),2015(2):269-273.

[11]施榮華,朱炫滋,董 健,等.基于粒子群-遺傳混合算法的MIMO雷達(dá)布陣優(yōu)化[J].中南大學(xué)學(xué)報(bào),2013(11):4499-4505.

Coverage Optimization of Hybrid Wireless Sensor Network Based on Improved Genetic Algorithm

Hu Guolong1, Jia Zhenhong1, Qin Xizhong1,Cao Chuanling2, Niu Hongmei2

(1. School of Information Science and Engineering, Xinjiang University, Urumqi 830046, China;2.Subsidiary Company of China Mobile in Xinjiang, Urumqi 830063, China)

In order to improve the coverage performance,an improved genetic algorithm was applied to coverage optimization of hybrid wireless sensor networks (WSNs).Coverage performance can be improved by changing location of mobile nodes. Traditional intelligence algorithm is liable to fall into the trap of premature and its largest number of iterations is difficult to determine. An improved genetic algorithm is proposed to fill the gaps. Multiple populations can be connected with others by immigration operator. Optimal individual of each population in every generation can be selected by artificial selection operator and recorded by essence of population. A new stopping criterion for iteration is presented according to the recorded information. Simulation shows that our improved genetic algorithm needn't set maximum number of iterations ,has fast convergence rate, and effectively improves coverage performance of WSNs.

wireless sensor network ;coverage;genetic algorithm; immigration operator; artificial selection operator

2015-09-14；

2015-10-26。

中國(guó)移動(dòng)通信集團(tuán)新疆有限公司研究發(fā)展基金項(xiàng)目(XJM2013-2788)。

胡國(guó)龍(1990-)，男，河南南陽(yáng)人，碩士研究生，主要從事傳感器網(wǎng)絡(luò)方向的研究。

賈振紅(1964-)，男，河南洛陽(yáng)人，教授，博士研究生導(dǎo)師，主要從事傳感器技術(shù)方向的研究。

1671-4598(2016)03-0168-02

10.16526/j.cnki.11-4762/tp.2016.03.045

TP273

A