基于QEA優(yōu)化的WSNs簇間路由策略*

余成波，趙西超，楊 佳，田引黎，晏紹奎，代琪怡

（重慶理工大學(xué)遠(yuǎn)程測試與控制技術(shù)研究所，重慶 400054）

0 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）由于節(jié)點(diǎn)能量有限且無法補(bǔ)充，因此，如何高效率地利用傳感器節(jié)點(diǎn)的能量是WSNs中一個重要問題。傳統(tǒng)的單跳通信容易造成節(jié)點(diǎn)過早死亡，出現(xiàn)“局部空洞”，縮短網(wǎng)絡(luò)生存周期等問題;多跳通信方式可減少通信距離，增強(qiáng)網(wǎng)絡(luò)的穩(wěn)定性并提高節(jié)點(diǎn)能量利用效率，延長網(wǎng)絡(luò)生存周期，還能滿足網(wǎng)絡(luò)擴(kuò)展性的需要［1］。但在多跳方式下，距離基站較近的簇頭節(jié)點(diǎn)由于承擔(dān)的轉(zhuǎn)發(fā)任務(wù)較重，容易產(chǎn)生“熱點(diǎn)”問題。因此，合理選擇跳數(shù)和跳選簇頭，可以均衡簇頭節(jié)點(diǎn)能量，避免“熱點(diǎn)”問題，延長網(wǎng)絡(luò)生存周期。

量子進(jìn)化算法（quantum evolutionary algorithm，QEA）［2］是由量子理論和進(jìn)化算法（EA）不斷融合而發(fā)展出來的一種新型優(yōu)化算法，它基于量子計(jì)算的概念和理論，采用量子比特編碼染色體，使一個染色體可以表示多個狀態(tài)的信息;同時利用量子門更新完成進(jìn)化搜索，因此，具有種群規(guī)模小、收斂速度快、全局搜索能力強(qiáng)，具有自適應(yīng)性等優(yōu)勢，從而引起了國內(nèi)外的廣泛關(guān)注。

1996年，Narayanan A最早將量子理論引入到進(jìn)化算法領(lǐng)域，提出了量子衍生型遺傳算法［3］。2000年，Han K H提出遺傳量子算法［4］，該算法首次用量子態(tài)矢量來編碼染色體，利用量子門旋轉(zhuǎn)更新染色體，通過對背包問題的優(yōu)化，證明比常規(guī)遺傳算法有更好的優(yōu)化效果。針對遺傳量子算法的不足，Han K H在2002年提出了QEA［5］。

本文在研究了QEA實(shí)際應(yīng)用地基礎(chǔ)上，結(jié)合WSNs的特點(diǎn)，提出一種基于QEA優(yōu)化的簇間路由策略，用于均衡簇頭節(jié)點(diǎn)能耗。在眾多均衡簇頭節(jié)點(diǎn)能耗協(xié)議中，能量高效的非均勻分簇（energy-efficient uneven clustering，EEUC）［6］是一個非均勻分簇和簇間多跳路由有機(jī)結(jié)合的路由協(xié)議，使靠近基站的簇的成員數(shù)目較小，來達(dá)到均衡簇頭節(jié)點(diǎn)能耗的目的。分布式能量均衡的非均勻分簇（distributed energy-balanced unequal clustering，DEBUC）［7］協(xié)議是一種能量高效均衡的非均勻分簇路由協(xié)議，有效地節(jié)約單個節(jié)點(diǎn)能量，延長了網(wǎng)絡(luò)生存周期。仿真實(shí)驗(yàn)表明，相比與以上2種協(xié)議，該優(yōu)化策略可以有效均衡簇間能耗，延長網(wǎng)絡(luò)的壽命。

1 WSNs能量均衡分簇路由策略

1.1 簇的形成

1.1.1 簇頭選取數(shù)量確定

設(shè)有N個節(jié)點(diǎn)均勻分布，分布的區(qū)域設(shè)為M×M;要生成q個簇頭，簇頭最優(yōu)數(shù)量采用文獻(xiàn)中的方法確定［8］

式中qm為最優(yōu)簇頭節(jié)點(diǎn)數(shù)量，dt-BS為簇頭區(qū)域到基站的距離。εam，εamp為不同信道下信號放大的能量損失率（參考1.2節(jié)能耗模型）。由式（1）可知，最佳簇頭的數(shù)量與區(qū)域面積、初始節(jié)點(diǎn)個數(shù)、以及到基站的距離有關(guān)。

1.1.2 簇頭節(jié)點(diǎn)的形成與輪換策略

每個候選簇頭節(jié)點(diǎn)設(shè)置一個競爭半徑Rc，用于控制簇頭在網(wǎng)絡(luò)中的分布，使距離基站較近的簇頭節(jié)點(diǎn)數(shù)量較多同時其競爭半徑較?。?0］

式中dmax和dmin為節(jié)點(diǎn)到基站的最大和最小距離，d（Ci）為簇頭節(jié)點(diǎn)Ci與基站的距離，c為位于0～1之間的常數(shù)為預(yù)先定義的最大競爭半徑。根據(jù)公式（2）可知，候選簇頭的競爭范圍為（1-c）～之間變化。最后形成離基站較近的簇結(jié)構(gòu)較小，并且隨著距離的增加數(shù)量相應(yīng)減少［9］。同時，簇頭節(jié)點(diǎn)采用分布式競爭算法，若候選簇頭成功競選為簇頭，則在其半徑內(nèi)所有簇頭均不能成為最終簇頭，退出競爭過程。簇頭節(jié)點(diǎn)選舉過程中，點(diǎn)處于休眠狀態(tài)，以減少能耗。

簇頭輪換策略在參考LEACH協(xié)議的基礎(chǔ)上，做了一定的改進(jìn)［10］。門限T（n）定義為

式中p為網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)占總結(jié)點(diǎn)數(shù)目的百分比，r為當(dāng)前的輪數(shù);G為在前1/p輪中沒有擔(dān)當(dāng)過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)集合;mod是求模運(yùn)算符號。Ecut為節(jié)點(diǎn)當(dāng)前能量，Eint為節(jié)點(diǎn)初始能量，可以看出:節(jié)點(diǎn)剩余能量較大的節(jié)點(diǎn)成為簇頭的可能性更大，從而更有利于節(jié)點(diǎn)之間的能量均衡［7］。

1.2 能耗模型

能耗模型如圖1所示。

圖1 節(jié)點(diǎn)能耗模型Fig 1 Node energy consumption model

節(jié)點(diǎn)能耗主要分為3個方面:數(shù)據(jù)接收能耗、數(shù)據(jù)融合能耗和數(shù)據(jù)發(fā)送能耗。由于數(shù)據(jù)融合能耗較小，可忽略不計(jì)。在保證合理信噪比的條件下，建立如下能耗模型。無線通信模塊發(fā)送和接收kbit數(shù)據(jù)時能耗分別為ET和ER。Eelec為射頻能耗系數(shù)，d表示源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離，節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)的能耗為［8］。

選擇2種信道模型進(jìn)行:一種是自由空間，發(fā)射功率以d2衰減，能量損失率為εam;第二種是多路衰減，發(fā)射功率以d2衰減，能量損失率為εamp。

節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)時的能耗為

節(jié)點(diǎn)在數(shù)據(jù)通信時總能耗為數(shù)據(jù)發(fā)送和數(shù)據(jù)接收之和

1.3 QEA優(yōu)化簇間路由策略的算法描述與流程

優(yōu)化策略如圖2所示。

QEA可以很好地求解函數(shù)優(yōu)化問題，根據(jù)以上分析，把該算法用于優(yōu)化于簇間路由［11］，能均衡簇頭節(jié)點(diǎn)的能耗。優(yōu)化步驟如圖3所示［12］。

圖2 QEA優(yōu)化簇間路由策略Fig 2 QEA optimal inter-cluster routing strategy

圖3 QEA優(yōu)化流程圖Fig 3 Flow chart of QEA optimization

圖4 染色體編碼示意圖Fig 4 Sketch map of chromosome encoding

節(jié)點(diǎn)目標(biāo)函數(shù)如下:

網(wǎng)絡(luò)能量均值函數(shù)

能量方差函數(shù)

圖5 簇間路由路徑示意圖Fig 5 Schematic diagram of inter-cluter routing path

2 數(shù)據(jù)仿真與分析

根據(jù)圖2、圖3的流程，結(jié)合1.1，1.2節(jié)的具體步驟，得出最優(yōu)簇頭節(jié)點(diǎn)數(shù)量為20個，根據(jù)最大競爭半徑為R0c，結(jié)合分簇算法把簇頭節(jié)點(diǎn)分成4層，并根據(jù)距離基站的遠(yuǎn)近確定每層簇頭節(jié)點(diǎn)數(shù)量為4，4，5，7，從而染色體長度為:4×4+4×5+5×7=71。

圖6對比了4種協(xié)議的網(wǎng)絡(luò)總能耗隨仿真時間（輪）的變化曲線，較小的坡度表明較慢的能量消耗速度和較長的生存周期。QEA優(yōu)化的簇間路由策略的坡度小于EEUC和DEBUC，說明該策略在一定程度上均衡了簇頭節(jié)點(diǎn)間的能耗。圖7給出3種協(xié)議能量方差隨仿真時間（輪）的變化曲線，該優(yōu)化策略的簇頭節(jié)點(diǎn)剩余的能量方差一直很低，表明其能有效地均衡網(wǎng)絡(luò)簇頭節(jié)點(diǎn)的能耗。

圖6 網(wǎng)絡(luò)簇頭節(jié)點(diǎn)能耗變化曲線Fig 6 Energy consumption change curve of network cluster head node

圖7 網(wǎng)絡(luò)簇頭節(jié)點(diǎn)剩余能量方差變化曲線Fig 7 Residual energy variance change curve of network cluster head node

3 結(jié)束語

針對WSNs中不均勻分簇，多跳通信方式存在的“熱點(diǎn)”問題，本文提出一種基于QEA優(yōu)化的WSNs能量均衡的分簇路由策略，該策略在簇頭輪換、分簇機(jī)制、簇頭數(shù)量確定都做了一定改進(jìn)，并根據(jù)QEA的特點(diǎn)優(yōu)化了簇間路由協(xié)議。仿真實(shí)驗(yàn)表明:該策略提高了網(wǎng)絡(luò)能量的利用率，有效均衡了簇頭節(jié)點(diǎn)間的數(shù)據(jù)轉(zhuǎn)發(fā)能耗，一定程度上避免了“熱點(diǎn)”問題，延長了網(wǎng)絡(luò)生存周期。

［1］薛曉亮，齊榮賓，錢 峰.基于能量均衡的WSN多跳非均勻分簇路由算法［J］.華東理工大學(xué)學(xué)報(bào)，2011（3）:352-358.

［2］范勝輝.量子進(jìn)化算法及其應(yīng)用研究［D］.南京:南京航空航天大學(xué)，2010:2-23.

［3］Narayanan A，Moore M.Quantum-inspired genetic algorithms［C］//Proceedings of the 1996 IEEE International Conference on Evolutionary Computation，ICEC'96，Nogaya:JSME，1996:61-66.

［4］Han K H，Kim J H.Genetic quantumalgorithm and its application to combinatorial optimization problem［C］//Proceedings of the 2000 Int'l Congress on Evolutionary Computation（ICEC），California，2000:1345-1360.

［5］Han K H，Kim J H.Quantum-inspired evolution aryalgorithm for a class of combinatorial optimization［J］.IEEE Trans on Evolutionary Computation，2002（6）:580-593.

［6］Ye M，Li C F，Chen G H，et al.An energy efficient clustering scheme in wireless sensor networks［C］//Proceedings of the 24th IEEE International Performance，Computingand Communications Conference，Phoenix，AZ:IEEE Computer Society，2005:535-540.

［7］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2012，23（5）:1222-1232.

［8］熊 飛.無線傳感網(wǎng)絡(luò)分簇路由的研究［D］.重慶:重慶理工大學(xué)，2012:12-40.

［9］丁 岳，丁 勇，趙國安，等.多約束條件下能耗均衡的WSN路由算法的研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2012，29（5）:244-247.

［10］王艷麗，楊 順.基于能量均衡的無線傳感器網(wǎng)絡(luò)算法的改進(jìn)［J］.微計(jì)算機(jī)控制，2010（24）:117-119.

［11］鄧長春.基于量子進(jìn)化算法的路由選擇［J］.計(jì)算機(jī)工程應(yīng)用，2010，46（23）:103-105.

［12］史 峰，王 輝，郁 磊，等.Matlab智能算法30個案例分析［M］.北京:北京航空航天大學(xué)出版社，2011:78-87.