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

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

關(guān)鍵詞： 遺傳算法； 蟻群算法； 無線傳感網(wǎng)絡(luò)； 覆蓋優(yōu)化

中圖分類號： TN915?34； TP301.6 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）18?0009?03

Abstract： Since in optimization process of wireless sensor network coverage， the traditional genetic algorithm has fast calculation 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 influence the optimization efficiency and coverage rate， in this paper， the ant colony algorithm is fused into genetic algorithm to improve 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 improved method has much better superiority.

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

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

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

通過對比兩種算法下覆蓋率以及能耗率隨著節(jié)點(diǎn)個數(shù)改變而變化曲線可知，本文改進(jìn)方法的平均覆蓋率和能量消耗率相比常規(guī)遺傳優(yōu)化算法分別提高了6.2%，以及降低了5.7%。說明本文研究方法對于網(wǎng)絡(luò)覆蓋率和能耗降低有較好的優(yōu)化效果。下面通過三種實(shí)驗(yàn)方法，對覆蓋優(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é)果對比可知，在小面積的覆蓋范圍內(nèi)，以及節(jié)點(diǎn)個數(shù)較少時，本文研究的改進(jìn)方法與傳統(tǒng)優(yōu)化方法的覆蓋率和完成時間差別不大，但是隨著覆蓋范圍的增大，節(jié)點(diǎn)個數(shù)的增加，本文研究的改進(jìn)方法完成時間明顯縮短，覆蓋率明顯增大，相比傳統(tǒng)優(yōu)化方法具有更大的優(yōu)勢。

4 結(jié) 論

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

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

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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