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

(1.新疆大學 信息科學與工程學院，烏魯木齊 830046; 2.中國移動通信集團 新疆有限公司，烏魯木齊 830063)

?

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

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

(1.新疆大學 信息科學與工程學院，烏魯木齊 830046; 2.中國移動通信集團 新疆有限公司，烏魯木齊 830063)

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

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

0 引言

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

1 系統(tǒng)模型

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

(1)

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

(2)

2 遺傳算法與改進算法

2.1 標準遺傳算法

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

1)種群初始化：隨機生成W個長度相同的數(shù)組，將每個數(shù)組當作一個染色體，W個染色體共同組成一個種群，把該種群作為進化的初始種群。

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

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

(3)

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

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

(4)

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

5)變異算子：在種群中隨機挑選一個染色體，通過改變該染色體中的某一位，產(chǎn)生新的染色體。染色體am在第k位上執(zhí)行變異操作的具體方法為

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

2.2 改進的遺傳算法

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

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

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

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

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

圖1 改進遺傳算法流程圖

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

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

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

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

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

圖4 覆蓋率對比圖

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

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

表1 RD指標對比

4 結(jié)論

本文針對傳統(tǒng)群體智能算法單個種群串行尋優(yōu)容易早熟這一問題，在標準遺傳算法的基礎(chǔ)上引入多個種群進行改進，通過多個種群并行協(xié)同進化不僅收斂速度快而且有效地克服了早熟這一缺陷。同時充分利用了種群進化過程中積累的信息，設(shè)計出比是否達到最大迭代次數(shù)更為合理的算法終止條件。仿真結(jié)果顯示，將本文算法應(yīng)用到混合WSNs覆蓋優(yōu)化問題中，能有效提高網(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]. 計算機工程與應(yīng)用 , 2009(11):89-98.

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

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

[6] 陳 樹, 錢 成. 一種多目標的覆蓋優(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] 柯 俊， 史文庫， 錢 琛，等. 采用遺傳算法的復合材料板簧多目標優(yōu)化方法[J]. 西安交通大學學報,2015(8):1-7.

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

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

[11]施榮華,朱炫滋,董 健,等.基于粒子群-遺傳混合算法的MIMO雷達布陣優(yōu)化[J].中南大學學報,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。

中國移動通信集團新疆有限公司研究發(fā)展基金項目(XJM2013-2788)。

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

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

1671-4598(2016)03-0168-02

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

TP273

A