WSN中基于梯度和粒子群優(yōu)化算法的分級簇算法

閻新芳，嚴(yán)晶晶，馮　巖

(鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001)

?

WSN中基于梯度和粒子群優(yōu)化算法的分級簇算法

閻新芳，嚴(yán)晶晶，馮巖

(鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001)

摘要：為均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，提出一種分級簇算法——GPHCA.該算法采用雙簇頭模式，利用粒子群優(yōu)化算法搜尋能量大且到簇成員平均距離小的兩個節(jié)點(diǎn)作為主簇頭和副簇頭，將簇頭負(fù)擔(dān)均衡到了兩個節(jié)點(diǎn)上；在網(wǎng)關(guān)的選擇上，同時考慮能量和轉(zhuǎn)發(fā)路徑的總距離，使最終選擇的網(wǎng)關(guān)在能量和時延上得到均衡.仿真結(jié)果表明，GPHCA算法能有效延長網(wǎng)絡(luò)的生命周期.

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；梯度；粒子群算法；GPHCA；雙簇頭

0引言

無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量有限且不易補(bǔ)充[1]，所以降低網(wǎng)絡(luò)能量消耗成為傳感網(wǎng)路由協(xié)議的首要設(shè)計(jì)目標(biāo).相對于平面路由協(xié)議來說，分層路由協(xié)議有效節(jié)省了能量且可擴(kuò)展性好[2-4].基于分級簇的拓?fù)浣Y(jié)構(gòu)作為分層路由的基礎(chǔ)[5-7]，能有效減少網(wǎng)絡(luò)的冗余信息，降低節(jié)點(diǎn)的能量負(fù)擔(dān)，因此受到廣泛關(guān)注.

文獻(xiàn)[8-9]提出了一種基于梯度的分級簇算法(energy-aware topology control protocol based on gradient, ETBG)，建立了網(wǎng)絡(luò)中節(jié)點(diǎn)到達(dá)基站的最小跳數(shù)，但是簇內(nèi)緊湊性不夠，且對網(wǎng)關(guān)節(jié)點(diǎn)能量考慮不足.文獻(xiàn)[10]提出一種新的基于粒子群優(yōu)化的雙簇頭分簇路由算法(a new dual-cluster heads clustering routing algorithm based on particle swarm optimization,DHCR)，利用粒子群算法(particle swarm optimization,PSO)進(jìn)行簇頭優(yōu)化，但是采用隨機(jī)的方式進(jìn)行初始分簇，簇的可控性不高，其副簇頭雖減輕了主簇頭的負(fù)擔(dān)，但效果不明顯.因此，為均衡節(jié)點(diǎn)的能耗，筆者提出一種基于梯度和粒子群優(yōu)化算法的分級簇算法(gradient and particle swarm optimization based hierarchical cluster algorithm, GPHCA)，并在簇內(nèi)引入新的雙簇頭模式，從而提高網(wǎng)絡(luò)生命周期.該算法采用分布式與集中式結(jié)合的方式，節(jié)點(diǎn)初步分簇后將信息發(fā)送至基站，在基站對簇頭及路徑進(jìn)行優(yōu)化，因此，優(yōu)化部分并不消耗節(jié)點(diǎn)的能量.

1問題描述

筆者采用和文獻(xiàn)[9]相同的網(wǎng)絡(luò)模型和能量模型，節(jié)點(diǎn)的發(fā)射半徑可調(diào).由能耗公式可知，信息發(fā)送的能耗和距離呈指數(shù)關(guān)系，影響不可忽視.故在簇頭優(yōu)化階段，需要解決的主要問題即是選擇剩余能量大且相對處于簇中心的節(jié)點(diǎn)作為簇頭，以減少簇成員發(fā)送信息的耗能.構(gòu)建數(shù)學(xué)模型如下：

(1)

fCH-2=max{d(CH,ni)/R}.

(2)

fCH=αfCH-1+βfCH-2.

(3)

在簇間數(shù)據(jù)傳輸階段要保證簇頭的下一跳節(jié)點(diǎn)在有較多能量的同時還要處于合適的位置，故主要優(yōu)化目標(biāo)設(shè)定如下：

frout-1=Eaver/E(ni) .

(4)

frout-2=[d(CH,ni)+d(ni,BS)]/R0.

(5)

frout=αfrout-1+βfrout-2.

(6)

式中：K是簇內(nèi)節(jié)點(diǎn)個數(shù)；E(CH)和E(ni)分別是簇頭和節(jié)點(diǎn)i的剩余能量；d(CH,ni)和d(ni,BS)分別是節(jié)點(diǎn)i到簇頭和基站的距離；R是節(jié)點(diǎn)的通信半徑；R0是網(wǎng)絡(luò)中心到基站的距離，引入目的是使fCH-1和fCH-2、frout-1和frout-2在同一數(shù)量級；Eaver是所有節(jié)點(diǎn)的平均剩余能量；α和β是權(quán)重，且α+β=1.fCH-1是能量因子，其值越小表示簇頭剩余能量越大；fCH-2是距離因子，其值越小表示簇越緊湊.所以，fCH值越小，節(jié)點(diǎn)越適合做簇頭.frout-1越小，簇頭下一跳節(jié)點(diǎn)的剩余能量越大；frout-2越小，簇頭經(jīng)過下一跳節(jié)點(diǎn)到達(dá)基站的總距離越小，能耗也越小，所以frout值越小，節(jié)點(diǎn)越適合做網(wǎng)關(guān).

2粒子群算法簡介

粒子群優(yōu)化算法[11-12]是一種基于群體智能的尋優(yōu)算法.每一個粒子i都有一個速度vi和位置xi.對于需要優(yōu)化的問題，定義一個適應(yīng)度函數(shù)，粒子到達(dá)新的位置后計(jì)算當(dāng)前的適應(yīng)度函數(shù)值，并以此判斷當(dāng)前解的優(yōu)劣.粒子跟蹤個體極值pi和全局極值pg對其速度和位置進(jìn)行更新，不斷向最優(yōu)解靠近，更新方式如下：

vij(t+1)=ωvij(t)+c1r1[pij(t)-xij(t)]+

c2r2[pgj(t)-xij(t)].

(7)

xij(t+1)=xij(t)+vij(t+1).

(8)

式中：ω為慣性權(quán)重，代表對當(dāng)前速度繼承的多少；c1和c2為學(xué)習(xí)因子，分別表示粒子對個體和整個群體知識的認(rèn)識；r1和r2為(0,1)的隨機(jī)正數(shù).

3基于PSO的分簇路由算法

3.1初步分簇

在分簇之前先按文獻(xiàn)[9]的方式以基站為圓心根據(jù)節(jié)點(diǎn)通信半徑將整個網(wǎng)絡(luò)劃分成一個梯度場，然后采用ETBG算法進(jìn)行初步分簇并選舉臨時簇頭，臨時簇頭將所有節(jié)點(diǎn)及分簇信息發(fā)送至基站.

3.2簇頭優(yōu)化

假設(shè)簇內(nèi)有K個節(jié)點(diǎn)，x表示實(shí)際坐標(biāo).當(dāng)粒子搜索完簇內(nèi)所有節(jié)點(diǎn)或者達(dá)到最大迭代次數(shù)的時候算法收斂.具體步驟如下.

(1)初始化N個粒子，確定其位置x、速度v，并將其移動到距離最近的節(jié)點(diǎn)位置.

(2)每個粒子以公式(3)作為適應(yīng)度函數(shù)，計(jì)算當(dāng)前位置的適應(yīng)度函數(shù)值，即將當(dāng)前位置節(jié)點(diǎn)設(shè)為簇頭時的fCH函數(shù)值，并將其和當(dāng)前位置節(jié)點(diǎn)號保存在個體極值pi中，將所有個體極值中fCH函數(shù)值最小的存入全局極值pg，將fCH值第二小的存入全局次優(yōu)值ps.

(3)按公式(7)、(8)更新粒子的速度v和位置x，然后計(jì)算每個粒子在新位置上的fCH值，并將其與pi比較，若優(yōu)于pi，則將當(dāng)前位置節(jié)點(diǎn)更新為pi.選出pi中的最優(yōu)值，將其與全局極值pg和全局次優(yōu)值ps比較，將最優(yōu)的保存為pg，次優(yōu)的保存為ps.

(4)判斷是否達(dá)到收斂條件，如果沒有則轉(zhuǎn)到步驟(3).

(5)將最后輸出的全局極值pg所在的節(jié)點(diǎn)設(shè)為當(dāng)前簇的主簇頭，全局次優(yōu)值ps所在的節(jié)點(diǎn)設(shè)為副簇頭，完成簇頭優(yōu)化.

3.3形成簇樹

由于在數(shù)據(jù)傳輸階段主副簇頭是分開工作的，故需要兩條路徑來維持簇間信息的傳輸，路徑選擇的規(guī)則相同.在基站運(yùn)行PSO算法，分別針對主副簇頭按以下步驟形成簇樹.

(1)將梯度為1的簇頭和網(wǎng)關(guān)的下一跳節(jié)點(diǎn)直接設(shè)為BS，將其余簇頭和網(wǎng)關(guān)鄰居中梯度比其小的節(jié)點(diǎn)放入其nexthops集合作為搜尋范圍，沒有梯度比其小的則將同梯度鄰居節(jié)點(diǎn)放入nexthops.

(2)將每個nexthops中能量最大的簇頭設(shè)為下一跳節(jié)點(diǎn)；沒有簇頭的則以nexthops為搜索范圍，以公式(6)為適應(yīng)度函數(shù)，運(yùn)行粒子群算法，具體規(guī)則同3.2，將輸出的全局極值pg所在的節(jié)點(diǎn)設(shè)為下一跳節(jié)點(diǎn)即網(wǎng)關(guān)節(jié)點(diǎn).

(3)查詢是否所有的簇頭和網(wǎng)關(guān)都有了確定的下一跳節(jié)點(diǎn)，如果是，算法結(jié)束，簇樹形成；如果不是，跳回步驟(1).

簇樹建立之后，基站保存全網(wǎng)的路由信息，然后將其廣播給所有節(jié)點(diǎn).收到信息后，主副簇頭分別保存自己的成員節(jié)點(diǎn)和下一跳節(jié)點(diǎn)信息，為各成員節(jié)點(diǎn)分配TDMA傳輸時隙，而普通節(jié)點(diǎn)則只保存自己的主簇頭、副簇頭和TDMA時隙信息，避免存儲資源浪費(fèi).

3.4數(shù)據(jù)傳輸方案

經(jīng)過路由建立階段，整個網(wǎng)絡(luò)建立了主副兩條路徑，它們共同分擔(dān)一輪的數(shù)據(jù)采集工作.在數(shù)據(jù)傳輸過程中，網(wǎng)絡(luò)預(yù)先設(shè)定每輪的數(shù)據(jù)傳輸次數(shù)times和主簇頭的工作比例coef.前coef*times次數(shù)據(jù)傳輸中，主簇頭負(fù)責(zé)簇內(nèi)信息的收集、融合和轉(zhuǎn)發(fā).然后，主簇頭退化成普通節(jié)點(diǎn)，副簇頭繼任簇頭完成剩余的數(shù)據(jù)傳輸.數(shù)據(jù)傳輸達(dá)到預(yù)設(shè)次數(shù)后該輪結(jié)束，網(wǎng)絡(luò)將進(jìn)行重新分簇開始下一輪.

4性能分析

假設(shè)在100 m×100 m的檢測區(qū)域內(nèi)隨機(jī)拋灑100個節(jié)點(diǎn)，每個節(jié)點(diǎn)的通信半徑R設(shè)為30 m，初始能量5 J，ω=0.9，c1=c2=2.

定義第一個節(jié)點(diǎn)死亡時采集的數(shù)據(jù)總輪數(shù)為網(wǎng)絡(luò)的生命周期.假設(shè)times=1 000次，coef=0.6，β=0.6，從實(shí)驗(yàn)中隨機(jī)選取30輪取均值，對GPHCA與ETBG和EBUCP 3種算法進(jìn)行對比分析.

圖1是節(jié)點(diǎn)密度N對3種算法生命周期的影響，GPHCA算法在節(jié)點(diǎn)密度水平處于中度水平時，優(yōu)勢很大.主要原因是節(jié)點(diǎn)密度適中時，GPHCA算法能更好的控制簇頭能量和簇的緊湊性，有優(yōu)化的網(wǎng)關(guān)，且用雙簇頭模式將簇頭任務(wù)分配給了兩個節(jié)點(diǎn)，故其生命周期明顯優(yōu)于另兩個算法.節(jié)點(diǎn)密度過大時，前兩種算法的簇規(guī)模增大，故簇頭負(fù)擔(dān)加大，而DHCR算法簇規(guī)模變化不大，故生命周期穩(wěn)定但是都不長.

圖1　不同N下的生命周期對比

圖2是簇頭采集一輪數(shù)據(jù)的平均能耗.DHCR算法的副簇頭的作用相當(dāng)于ETBG中的網(wǎng)關(guān)節(jié)點(diǎn)，故相比之下，GPHCA算法的雙簇頭模式更有效地分擔(dān)了簇頭負(fù)擔(dān).

圖2　簇頭采集一輪數(shù)據(jù)的平均能耗

圖3是通信半徑R對3種算法生命周期的影響.DHCR算法的通信半徑僅用于使簇頭分散開來，故其生命周期對R不敏感.當(dāng)R較小時，GPHCA算法有效延長了網(wǎng)絡(luò)的生命周期，但是當(dāng)R較大時優(yōu)勢退化.主要原因是當(dāng)R增加時，節(jié)點(diǎn)可以通信的鄰居增多，簇的平均半徑增大，簇頭負(fù)擔(dān)加重，主簇頭任期未滿就已死亡，故無法發(fā)揮雙簇頭模式的優(yōu)勢.因此，適當(dāng)?shù)亟档凸?jié)點(diǎn)的發(fā)射半徑，采取多跳傳輸模式更有利于延長生命周期.

圖3　不同R下的生命周期對比

GPHCA算法的效果受主簇頭工作比例coef的影響，如圖4所示.在coef=0.55時，生命周期達(dá)到最大，這主要是因?yàn)橹鞔仡^比副簇頭有更好的綜合適應(yīng)度值，故其承擔(dān)略多的任務(wù)時，更有利于延長整網(wǎng)的生命周期.

圖4　coef對網(wǎng)絡(luò)生命周期的影響

粒子群算法為隨機(jī)初始化算法，其結(jié)果有一定波動性，對30次不同節(jié)點(diǎn)密度下的實(shí)驗(yàn)結(jié)果求方差，結(jié)果如表1所示.GPHCA算法針對單個簇進(jìn)行單獨(dú)優(yōu)化且有副簇頭輔助工作，故當(dāng)某次PSO優(yōu)化結(jié)果不理想時，影響被控制在半個times以內(nèi)，所以生命周期的波動不超過500次.

表1　GPHCA算法生命周期的方差

5結(jié)論

提出了一種基于梯度和粒子群優(yōu)化算法的分級簇算法，該算法利用適應(yīng)度函數(shù)將剩余能量和節(jié)點(diǎn)到簇頭以及基站的距離結(jié)合起來，通過粒子群的搜尋找出最佳的節(jié)點(diǎn)分任主副簇頭和網(wǎng)關(guān)，通過適當(dāng)調(diào)節(jié)節(jié)點(diǎn)的通信半徑、主簇頭工作比例和數(shù)據(jù)采集頻次等參數(shù)，有效降低了簇頭的平均能耗，優(yōu)化了網(wǎng)關(guān)節(jié)點(diǎn)，均衡了節(jié)點(diǎn)能耗.在數(shù)據(jù)傳輸階段，采用雙簇頭輪換的模式，一次分簇即可生成兩條路徑，在減小簇頭節(jié)點(diǎn)負(fù)擔(dān)的同時避免了頻繁分簇帶來的能量消耗，有效延長了網(wǎng)絡(luò)的生命周期.

參考文獻(xiàn)：

[1]AKKAYA K, YOUNIS M. A survey on routing protocols for wireless sensor networks [J]. Ad hoc networks, 2005, 3(3): 325-349.

[2]CHANG D, CHO K, CHOI N, et al. A probabilistic and opportunistic flooding algorithm in wireless sensor networks [J]. Computer communications, 2012, 35(4): 500-506.

[3]INTANAGONWIWAT C, GOVINDAN R, ESTRIN D, et al. Directed diffusion for wireless sensor networking[J].IEEE/ACM transactions on networking, 2003, 11(1): 2-16.

[4]KUILA P, JANA P. Energy efficient clustering and routing algorithms for wireless sensor networks: particle swarm optimization approach [J]. Engineering applications of artificial intelligence, 2014(33): 127- 140.

[5]WU Y,LIU W B.Routing protocol based on genetic algorithm for energy harvesting-wireless sensor networks [J]. IET wireless sensor systems,2013,3(2):112-118.

[6]閻新芳,張漢,李良,等. WSN中基于負(fù)載均衡的EAMCT-G 優(yōu)化算法[J]. 天津大學(xué)學(xué)報(bào), 2012, 45(8): 735-739.

[7]閻新芳,王曉曉,嚴(yán)晶晶,等. 基于Q學(xué)習(xí)的無線傳感網(wǎng)分簇拓?fù)淇刂扑惴╗J]. 鄭州大學(xué)學(xué)報(bào)(工學(xué)版), 2015, 36(2): 85-88.

[8]閻新芳,段磊,李騰. 無線傳感網(wǎng)中基于梯度的拓?fù)淇刂扑惴╗J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(2): 95-98.

[9]王志龍. 無線傳感器網(wǎng)絡(luò)中基于ETBG算法的分簇拓?fù)淇刂蒲芯縖D]. 鄭州:鄭州大學(xué)信息工程學(xué)院, 2011.5.

[10]解志斌,于謙,沈斌,等. 一種新的基于粒子群優(yōu)化的雙簇頭分簇路由算法[J]. 傳感技術(shù)學(xué)報(bào), 2013, 26(8): 1135-1139.

[11]MA D X, MA J, XU P M. An adaptive assistant-aided clustering protocol for WSNs using Niching Particle Swarm Optimization [C]//Proceedings of the IEEE international conference on software engineering and service sciences. Washington: IEEE Computer Society, 2013: 648-651.

[12]KHALIL B, DRISS E. Particle swarm optimization based clustering in Wireless Sensor Networks: The effectiveness of distance altering [C]// Proceedings of 2012 international conference on complex systems. Washington: IEEE Computer Society, 2012: 1-4．

Gradient and Particle Swarm Optimization Based Hierarchical Cluster Algorithm in WSN

YAN Xinfang, YAN Jingjing, FENG Yan

(School of Information Engineering，Zhengzhou University，Zhengzhou 450001，China)

Abstract:A hierarchical clustering algorithm was proposed to balance the nodes’ energy consumption in the network. A mode of double cluster heads was adopted to select two cluster heads with sufficient remaining energy and small average distances to the cluster members using particle swarm optimization algorithm. The burden of one cluster head was shared by these two nodes. As for the gateways, the residual energy and the total distance of forwarding path was considered to make sure that the final chosen gateways get well balance between energy and delay.The simulation results show that the GPHCA algorithm can effectively prolong the network lifetime.

Key words:wireless sensor networks; gradient; particle swarm optimization; GPHCA; double cluster heads

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.1671-6833.201505017

作者簡介:閻新芳(1958—)，女，河南嵩縣人，鄭州大學(xué)教授，博士，主要從事無線傳感網(wǎng)等方面研究，E-mail:iexfyan@zzu.edu.cn.

基金項(xiàng)目：河南省科技廳基礎(chǔ)與前沿研究計(jì)劃資助項(xiàng)目(152300410023)

收稿日期:2015-05-08；

修訂日期：2015-11-05

文章編號:1671-6833(2016)02-0033-04

引用本文：閻新芳，嚴(yán)晶晶，馮巖.WSN中基于梯度和粒子群優(yōu)化算法的分級簇算法[J].鄭州大學(xué)學(xué)報(bào)(工學(xué)版)，2016，37(2)：33-36．