劉靜靜，鄭倩倩

（1.鄭州大學(xué)　信息工程學(xué)院，河南　鄭州　450000；2.鄭州澍青醫(yī)學(xué)高等專科學(xué)校，河南　鄭州　450000）

基于改進(jìn)遺傳算法的無(wú)線網(wǎng)絡(luò)覆蓋算法

劉靜靜1，2，鄭倩倩2

（1.鄭州大學(xué)信息工程學(xué)院，河南鄭州450000；2.鄭州澍青醫(yī)學(xué)高等?？茖W(xué)校，河南鄭州450000）

考慮到傳統(tǒng)的遺傳算法在對(duì)無(wú)線傳感網(wǎng)絡(luò)覆蓋進(jìn)行優(yōu)化時(shí)，存在起始階段計(jì)算速度快，后期局部尋找最優(yōu)解能力弱，不能充分使用系統(tǒng)反饋路徑信息，使得算法會(huì)因冗余迭代而導(dǎo)致陷入局部最優(yōu)解，影響優(yōu)化效率和覆蓋率等問(wèn)題，將蟻群算法融合到遺傳算法中，對(duì)遺傳算法進(jìn)行改進(jìn)。通過(guò)不同覆蓋范圍和節(jié)點(diǎn)的三個(gè)實(shí)例進(jìn)行優(yōu)化效果分析，可知在小面積的覆蓋范圍內(nèi)，以及節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，該文研究的改進(jìn)方法與傳統(tǒng)優(yōu)化方法的覆蓋率和完成時(shí)間差別不大，但是隨著覆蓋范圍的增大，節(jié)點(diǎn)個(gè)數(shù)的增加，該文研究的改進(jìn)方法完成時(shí)間明顯縮短，覆蓋率明顯增大，相比傳統(tǒng)優(yōu)化方法具有更大的優(yōu)勢(shì)。

遺傳算法；蟻群算法；無(wú)線傳感網(wǎng)絡(luò)；覆蓋優(yōu)化

無(wú)線傳感網(wǎng)絡(luò)已經(jīng)廣泛地應(yīng)用于各行各業(yè)中，網(wǎng)絡(luò)由多個(gè)傳感節(jié)點(diǎn)通過(guò)樹(shù)形、星形等拓?fù)浣Y(jié)構(gòu)連接，各個(gè)節(jié)點(diǎn)之間相互連接，實(shí)現(xiàn)對(duì)現(xiàn)場(chǎng)數(shù)據(jù)地監(jiān)測(cè)、控制等功能，如何針對(duì)不同的應(yīng)用場(chǎng)合和條件，優(yōu)化調(diào)節(jié)傳感節(jié)點(diǎn)的個(gè)數(shù)和位置，使得無(wú)線傳感網(wǎng)絡(luò)覆蓋率最大，是無(wú)線傳感網(wǎng)絡(luò)研究的熱點(diǎn)問(wèn)題之一，有利于提高無(wú)線傳感網(wǎng)絡(luò)的服務(wù)質(zhì)量［1?5］。

1　無(wú)線傳感網(wǎng)絡(luò)覆蓋問(wèn)題模型

將無(wú)線傳感網(wǎng)絡(luò)覆蓋區(qū)域看作二維平面，在這個(gè)二維平面上設(shè)置有N個(gè)感知半徑和通信半徑分別為r和R的無(wú)線傳感節(jié)點(diǎn)。設(shè)定各個(gè)無(wú)線傳感節(jié)點(diǎn)用表示，是節(jié)點(diǎn)的二維坐標(biāo)，則無(wú)線傳感網(wǎng)絡(luò)中傳感節(jié)點(diǎn)集合表示為。以Ccover表示測(cè)量目標(biāo)傳感節(jié)點(diǎn)集合，則目標(biāo)節(jié)點(diǎn)p聯(lián)合檢測(cè)概率表示為：

將無(wú)線傳感網(wǎng)絡(luò)覆蓋率定位表示為：

有效工作的網(wǎng)絡(luò)節(jié)點(diǎn)率表示為：

式中：S1表示無(wú)線網(wǎng)絡(luò)傳感器總節(jié)點(diǎn)數(shù)量；S2表示有效的傳感器節(jié)點(diǎn)數(shù)量。

定義η為能量均衡系數(shù)，對(duì)無(wú)線傳感網(wǎng)絡(luò)的能耗均衡問(wèn)題進(jìn)行考慮，能量均衡系數(shù)η能夠?qū)o(wú)線網(wǎng)絡(luò)能耗均衡度進(jìn)行反映，η越大，則表示該無(wú)線傳感網(wǎng)絡(luò)的能耗越不均勻。能量均衡系數(shù)η表示為：

式中：k為有效節(jié)點(diǎn)個(gè)數(shù)；Ei為第i節(jié)點(diǎn)的能量剩余量。

無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題需要將覆蓋率、能量均衡以及工作狀態(tài)無(wú)線節(jié)點(diǎn)個(gè)數(shù)三方面進(jìn)行綜合考量。故無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題的數(shù)學(xué)模型可表示為［6?7］：

式中：w1，w2，w3為權(quán)值，三者之和等于1。

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

傳統(tǒng)的遺傳算法（GA）特點(diǎn)是：起始階段計(jì)算速度快，后期局部尋找最憂解能力弱，不能充分使用系統(tǒng)反饋路徑信息，使得算法會(huì)因冗余迭代而導(dǎo)致陷入局部最優(yōu)解［8?9］。有人提出將另外一種群智能算法——蟻群算法與遺傳算法進(jìn)行結(jié)合，改進(jìn)遺傳算法現(xiàn)有問(wèn)題。目前常用的混合方法僅對(duì)兩種算法進(jìn)行簡(jiǎn)單疊加，沒(méi)有對(duì)兩種算法轉(zhuǎn)換時(shí)機(jī)進(jìn)行考慮，沒(méi)有做到真正的融合，因此改進(jìn)后，遺傳算法性能提升不大［10］。本文改進(jìn)方法是首先改進(jìn)蟻群算法初始信息素較低的問(wèn)題。之后在遺傳算法和蟻群算法之間的切換使用動(dòng)態(tài)轉(zhuǎn)移法，而不是靜態(tài)轉(zhuǎn)移法。動(dòng)態(tài)控制適應(yīng)度函數(shù)方法為：

使用動(dòng)態(tài)揮發(fā)系數(shù)方法對(duì)算法后期的信息素進(jìn)行更新，使用信息素以及適應(yīng)度值對(duì)遺傳算法的交叉變異概率進(jìn)行動(dòng)態(tài)調(diào)整，使用信息素和啟發(fā)信息對(duì)遺傳算法的交叉變異位置進(jìn)行調(diào)整。構(gòu)造新的搜索機(jī)制，螞蟻按照下面方式選擇節(jié)點(diǎn)：

式中：allowedk表示螞蟻下次運(yùn)行的取點(diǎn)；q是0～1的隨機(jī)數(shù)；是邊（i，j）的信息素含量；是在第i個(gè)節(jié)點(diǎn)，第k個(gè)螞蟻選取第j個(gè)節(jié)點(diǎn)的概率；q1和q2由用戶設(shè)定；如果進(jìn)化次數(shù)達(dá)到設(shè)定值，或者連續(xù)若干代的個(gè)體平均適應(yīng)值和信息素含量低于設(shè)定的閾值，都可終止優(yōu)化算法，設(shè)定兩個(gè)終止條件目的是為了提高算法進(jìn)化的質(zhì)量［11?13］。具體算法流程如下：

步驟1：依據(jù)實(shí)際優(yōu)化任務(wù)要求對(duì)目標(biāo)函數(shù)和適應(yīng)度函數(shù)進(jìn)行確定。

步驟2：使用遺傳算法生成優(yōu)化解，數(shù)量為nGA組。

步驟3：使用信息素轉(zhuǎn)換方法將遺傳算法生成的優(yōu)化解轉(zhuǎn)換為蟻群算法的初始信息素。

步驟4：將蟻群算法基本參數(shù)進(jìn)行初始化，隨機(jī)地在N個(gè)節(jié)點(diǎn)布置M個(gè)螞蟻。

步驟5：使用由螞蟻狀態(tài)轉(zhuǎn)移規(guī)則建立的搜索方法，將N個(gè)節(jié)點(diǎn)一一遍歷，形成一個(gè)完整路徑。

步驟6：求出每條路徑的信息素含量和適應(yīng)度值。執(zhí)行選擇操作，若達(dá)到終止條件，則直接進(jìn)入步驟10，否則進(jìn)行下一步驟。

步驟7：通過(guò)交叉變異操作得到M條路徑。

步驟8：根據(jù)路徑的適應(yīng)度值和信息素含量對(duì)已經(jīng)得到的M+U條路徑進(jìn)行重新排序，選取排名前M條路徑。

步驟9：更新信息素，并回到步驟5。

步驟10：得到了最優(yōu)的路徑，完成了算法的改進(jìn)和優(yōu)化任務(wù)。

3　實(shí)例分析

本文以一個(gè)覆蓋區(qū)域?yàn)?00 m×100m正方形區(qū)域?yàn)檠芯繉?duì)象，進(jìn)行實(shí)例分析，設(shè)定無(wú)線傳感節(jié)點(diǎn)個(gè)數(shù)為200，通信和感知半徑為3 m和1.5 m，使用軟硬件平臺(tái)為Matlab R2014，Windows 7for 64，酷睿I5 4590處理器，內(nèi)存為4 GB DDR3 1 600×2，初始的無(wú)線傳感節(jié)點(diǎn)分布如圖1所示。

圖1　初始的無(wú)線傳感節(jié)點(diǎn)分布

使用常規(guī)遺傳算法優(yōu)化無(wú)線傳感網(wǎng)絡(luò)覆蓋方法與本文研究的改進(jìn)型遺傳算法優(yōu)化無(wú)線傳感網(wǎng)絡(luò)覆蓋方法進(jìn)行對(duì)比，不同算法下覆蓋率以及能耗率隨著節(jié)點(diǎn)個(gè)數(shù)改變而變化曲線如圖2所示。

圖2　不同算法下覆蓋率及能耗率

通過(guò)對(duì)比兩種算法下覆蓋率以及能耗率隨著節(jié)點(diǎn)個(gè)數(shù)改變而變化曲線可知，本文改進(jìn)方法的平均覆蓋率和能量消耗率相比常規(guī)遺傳優(yōu)化算法分別提高了6.2%，以及降低了5.7%。說(shuō)明本文研究方法對(duì)于網(wǎng)絡(luò)覆蓋率和能耗降低有較好的優(yōu)化效果。下面通過(guò)三種實(shí)驗(yàn)方法，對(duì)覆蓋優(yōu)化算法的效率進(jìn)行分析。三種實(shí)驗(yàn)方案如表1所示。實(shí)驗(yàn)結(jié)果如圖3所示［14?15］。

表1　實(shí)驗(yàn)方案

進(jìn)行三種實(shí)驗(yàn)方案結(jié)果對(duì)比可知，在小面積的覆蓋范圍內(nèi)，以及節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，本文研究的改進(jìn)方法與傳統(tǒng)優(yōu)化方法的覆蓋率和完成時(shí)間差別不大，但是隨著覆蓋范圍的增大，節(jié)點(diǎn)個(gè)數(shù)的增加，本文研究的改進(jìn)方法完成時(shí)間明顯縮短，覆蓋率明顯增大，相比傳統(tǒng)優(yōu)化方法具有更大的優(yōu)勢(shì)。

4　結(jié)　論

本文通過(guò)研究一種改進(jìn)遺傳對(duì)無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋進(jìn)行優(yōu)化。

通過(guò)實(shí)例分析得出結(jié)論：

（1）在小面積的覆蓋范圍內(nèi)以及節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，本文研究的改進(jìn)方法與傳統(tǒng)優(yōu)化方法的覆蓋率和完成時(shí)間差別不大，但是隨著覆蓋范圍的增大，節(jié)點(diǎn)個(gè)數(shù)的增加，本文研究的改進(jìn)方法完成時(shí)間明顯縮短，覆蓋率明顯增大；

（2）在覆蓋區(qū)域?yàn)?00 m×100 m正方形，節(jié)點(diǎn)數(shù)為100的實(shí)例中，本文研究改進(jìn)方法的平均覆蓋率和能量消耗率相比常規(guī)遺傳優(yōu)化算法分別提高了6.2%，以及降低了5.7%。說(shuō)明本文研究方法對(duì)于網(wǎng)絡(luò)覆蓋率和能耗降低有較好的優(yōu)化效果。

圖3　覆蓋優(yōu)化算法的效率實(shí)驗(yàn)結(jié)果

［1］萬(wàn)佳.基于多種群并行粒子群優(yōu)化算法研究［D］.南昌：南昌大學(xué)，2012.

［2］李志武.人工魚(yú)群算法的改進(jìn)及在無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化的應(yīng)用［D］.長(zhǎng)沙：湖南大學(xué)，2012.

［3］周少龍.基于節(jié)點(diǎn)協(xié)同調(diào)度的海事傳感網(wǎng)絡(luò)覆蓋控制研究［D］.武漢：武漢理工大學(xué)，2014.

［4］周利民.基于魚(yú)群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化研究［D］.長(zhǎng)沙：湖南大學(xué)，2010.

［5］宋蘇鳴.基于改進(jìn)人工蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略［D］.西安：西安電子科技大學(xué)，2014.

［6］陳鋒.大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化研究［D］.重慶：重慶大學(xué)，2014.

［7］傅彬.基于改進(jìn)人工魚(yú)群算法在無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化中的研究［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2015（12）：223?227.

［8］喬陽(yáng).基于改進(jìn)遺傳算法的圖像分割方法［D］.成都：電子科技大學(xué)，2013.

［9］林周泉.基于改進(jìn)遺傳算法的電力系統(tǒng)無(wú)功優(yōu)化［D］.衡陽(yáng)：南華大學(xué)，2013.

［10］張可.無(wú)線移動(dòng)自組織及傳感器網(wǎng)絡(luò)中若干問(wèn)題的研究［D］.成都：電子科技大學(xué)，2010.

［11］黃發(fā)良，蘇毅娟.基于GA與PSO混合優(yōu)化的Web文檔聚類算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34（7）：1531?1533.

［12］曹道友.基于改進(jìn)遺傳算法的應(yīng)用研究［D］.合肥：安徽大學(xué)，2010.

［13］陳振同.基于改進(jìn)遺傳算法的車間調(diào)度問(wèn)題研究與應(yīng)用［D］.大連：大連理工大學(xué)，2007.

［14］孫莉.基于一種差分魚(yú)群算法在WSN覆蓋應(yīng)用的研究［J］.科技通報(bào)，2015（9）：187?191.

［15］王明亮，閔新力，薛君志.基于改進(jìn)人工魚(yú)群算法的WSN覆蓋優(yōu)化策略［J］.微電子學(xué)與計(jì)算機(jī)，2015（6）：78?81.

Wireless network coverage algorithm based on improved genetic algorithm

LIU Jingjing1，2，ZHENG Qianqian2
（1.School of Information Engineering，Zhengzhou University，Zhengzhou 450000，China；2.Zhengzhou Shuqing Medical College，Zhengzhou 450000，China）

Since in optimization process of wireless sensor network coverage，the traditional genetic algorithm has fast calcu?lation speed in initial stage，but its local optimization capacity in the later period is weak，and it can not fully use the system feedback path information，which make the algorithm fall into the local optimal solution due to redundancy iteration，and influ?ence the optimization efficiency and coverage rate，in this paper，the ant colony algorithm is fused into genetic algorithm to im?prove genetic algorithm.The optimization effectiveness analysis is conducted by means of three examples of different coverage scale and node，by which a fact that there is no large d8ifference between the improved method and the traditional optimization method in the aspects of coverage rate and completion time when coverage area is small and node number is less is found out，but the improved method’s completion time is shortened obviously，and coverage rate is increased significantly with increase of the coverage scope and the increase of the node number.Therefore，compared with the traditional optimization method，the im?proved method has much better superiority.

genetic algorithm；ant colony algorithm；wireless sensor network；coverage optimization

TN915?34；TP301.6

A

1004?373X（2016）18?0009?03

10.16652/j.issn.1004?373x.2016.18.003

劉靜靜（1982—），女，河南鄭州人，講師，在讀碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)挖掘、現(xiàn)代教育技術(shù)。鄭倩倩（1979—），女，河南商丘人，講師，碩士。主要研究方向?yàn)橛?jì)算機(jī)技術(shù)。

2016?01?18

河南省科技廳項(xiàng)目：基于流量?jī)A斜分類的網(wǎng)絡(luò)調(diào)度算法（豫科鑒委字［2014］第2144號(hào)）