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

摘 要： 考慮到傳統(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ì)。

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

中圖分類(lèi)號(hào)： TN915?34； TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ú)線傳感網(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)題模型

通過(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)化效果。

參考文獻(xiàn)

[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文檔聚類(lèi)算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34（7）：1531?1533.

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

[13] 陳振同.基于改進(jìn)遺傳算法的車(chē)間調(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.