基于粒子群優(yōu)化的WSN覆蓋增強(qiáng)算法研究

摘 要：針對(duì)粒子群算法無(wú)線傳感器網(wǎng)絡(luò)（WSN）覆蓋優(yōu)化中算法穩(wěn)定性較差，后期收斂速度慢和易陷入局部最優(yōu)問(wèn)題，本文提出了一種自適應(yīng)擾動(dòng)混沌的粒子群（Adaptive Disturbance Chaotic Particle Swarm Optimization，簡(jiǎn)稱(chēng)ADCPSO）的覆蓋增強(qiáng)算法。一是在覆蓋范圍中應(yīng)用改進(jìn)的混沌Tent映射對(duì)粒子初始化，提高了種群的求解質(zhì)量和算法的穩(wěn)定性；二是采用非線性遞減的慣性權(quán)重和學(xué)習(xí)因子自適應(yīng)操作；三是根據(jù)一定概率對(duì)粒子位置進(jìn)行擾動(dòng)更新，避免粒子陷入局部收斂的問(wèn)題。仿真結(jié)果表明，該算法具有良好的全局搜索能力，穩(wěn)定性好，提高了網(wǎng)絡(luò)覆蓋率。

關(guān)鍵詞：粒子群覆蓋優(yōu)化；改進(jìn)的混沌Tent映射；穩(wěn)定性；自適應(yīng)操作；擾動(dòng)

中圖分類(lèi)號(hào)：TP212.9

網(wǎng)絡(luò)覆蓋是無(wú)線傳感器網(wǎng)絡(luò)的中的一個(gè)核心問(wèn)題。對(duì)于WSN覆蓋問(wèn)題，許多學(xué)者進(jìn)行了很多研究。近幾年，有學(xué)者提出基于遺傳算法、人工魚(yú)群算法、蟻群算法、貪心算法等算法。用這些算法對(duì)WSN覆蓋優(yōu)化問(wèn)題進(jìn)行求解，提高了網(wǎng)絡(luò)的覆蓋率。但是這些算法存在自身的不足，這些基本算法均存在容易陷入“早熟”、局部極優(yōu)、收斂速度等缺陷。

為了增強(qiáng)算法的搜索能力，提高WSN網(wǎng)絡(luò)覆蓋率，通過(guò)采用自適應(yīng)擾動(dòng)混沌粒子群算法找到一條最優(yōu)網(wǎng)絡(luò)覆蓋方案。首先建立無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化數(shù)學(xué)模型，然后采用自適應(yīng)擾動(dòng)混沌粒子群算法對(duì)模型進(jìn)行求解，得到無(wú)線傳感器網(wǎng)絡(luò)最優(yōu)覆蓋方案。

1 WSN覆蓋問(wèn)題的數(shù)學(xué)模型

3 仿真實(shí)驗(yàn)

圖1 網(wǎng)絡(luò)覆蓋率收斂曲線

仿真結(jié)果表明：在經(jīng)過(guò)104次迭代后，基本粒子群算法下的網(wǎng)絡(luò)覆蓋率收斂至穩(wěn)定值76%，不再增加；在經(jīng)過(guò)95次迭代后，文獻(xiàn)[4]提出的混沌粒子群算法下的覆蓋率收斂到83%，自適應(yīng)擾動(dòng)混沌粒子群算法下的覆蓋率在迭代83次后收斂至全局最優(yōu)解，覆蓋率達(dá)到86%。這說(shuō)明自適應(yīng)擾動(dòng)混沌粒子群算法比基本粒子群算法和文獻(xiàn)[4]提出的混沌粒子群算法具有較快的收斂速度，而且自適應(yīng)擾動(dòng)混沌粒子群算法采用對(duì)粒子進(jìn)行自適應(yīng)初始化，并對(duì)群體最優(yōu)位置進(jìn)行擾動(dòng)和混沌優(yōu)化，跳出局部最優(yōu)，增強(qiáng)了全局的搜索能力，提高了網(wǎng)絡(luò)覆蓋率。

4 結(jié)束語(yǔ)

本文是采用改進(jìn)的混沌Tent映射在可行域內(nèi)對(duì)粒子進(jìn)行初始化，提高了求解質(zhì)量，增強(qiáng)了算法的穩(wěn)定性；同時(shí)對(duì)粒子群參數(shù)進(jìn)行的自適應(yīng)調(diào)整；最后引入隨機(jī)擾動(dòng)因子，避免了“早熟”現(xiàn)象，提高了全局搜索能力。用此優(yōu)化算法對(duì)WSN覆蓋優(yōu)化問(wèn)題進(jìn)行求解，仿真結(jié)果表明，該算法與文中的幾種算法相比，有效避免了粒子過(guò)早陷入局部最優(yōu)，提高了算法的穩(wěn)定性，在網(wǎng)絡(luò)覆蓋率上有較高的提高，達(dá)到了很好的覆蓋優(yōu)化目的。

參考文獻(xiàn)：

[1]朱海榮，李平，程劍.基于改進(jìn)PSO算法的WSN覆蓋優(yōu)化方法[J].計(jì)算計(jì)工程，2011（08）：82-84.

[2]仲元昌，趙貞貞，王恒.無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋優(yōu)化算法[J].計(jì)算機(jī)工程，2012（08）：57-60.

[3]魏玉琴，戴永壽，張亞南.基于Tent映射的自適應(yīng)混沌嵌入式粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2013（10）：45-49.

[4]王華東，李巍.混沌粒子群算法在WSN覆蓋優(yōu)化中的應(yīng)用[J].科技通報(bào)，2012（08）：114-117.

作者簡(jiǎn)介：陳維宗（1989-），男，湖北天門(mén)人，碩士研究生，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)；黨小超（1963-），男，陜西韓城人，教授，碩士生導(dǎo)師，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)；郝占軍（1979-），通信作者，男，河北邢臺(tái)人，講師，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)、無(wú)線傳感器網(wǎng)絡(luò)。

作者單位：西北師范大學(xué)，蘭州 730070

基金項(xiàng)目：甘肅省發(fā)展和改革委資助項(xiàng)目（項(xiàng)目編號(hào)：010DKB021）。