基于改進(jìn)GA-PSO 的無線傳感網(wǎng)絡(luò)路由算法

張 慧

(榆林學(xué)院信息工程學(xué)院，陜西 榆林 719000)

0 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是一種分布式傳感網(wǎng)絡(luò)，它的末梢可以感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)被感知對(duì)象的信息，最終把這些信息發(fā)送給網(wǎng)絡(luò)所有者的傳感器。WSN 中的傳感器通過無線通信方式形成一個(gè)多跳自組織網(wǎng)絡(luò)，網(wǎng)絡(luò)設(shè)置靈活，設(shè)備位置可以隨時(shí)更改，還可以跟互聯(lián)網(wǎng)進(jìn)行有線或無線方式的連接，所以在實(shí)際中應(yīng)用比較廣泛。但是在WSN 的實(shí)際應(yīng)用中，網(wǎng)絡(luò)節(jié)點(diǎn)在信息傳輸過程中能量不能進(jìn)行補(bǔ)充，因此如何能夠保證數(shù)據(jù)在網(wǎng)絡(luò)傳輸過程中低能耗、正確、高效地傳輸是無線傳感路由的主要任務(wù)，也是當(dāng)前研究的熱點(diǎn)。

近年來經(jīng)常使用遺傳算法、粒子算法、蟻群算法等路由算法來解決上述問題。文獻(xiàn)［1-3］針對(duì)目前PSO 和GA 算法的不足，用遺傳算法中的交叉和變異來更新粒子運(yùn)行的速度和位置，可以提高收斂速度和群體搜索性能。文獻(xiàn)［4］提出了一種獨(dú)立性的粒子群和遺傳算法的新混合算法。算法將樣本分別進(jìn)行粒子群和遺傳運(yùn)算，將其最優(yōu)值作為全局最優(yōu)，進(jìn)而提高了算法整體的性能。文獻(xiàn)［5-8］用PSO 算法對(duì)無線路由協(xié)議、節(jié)點(diǎn)定位進(jìn)行研究。文獻(xiàn)［9-15］對(duì)無線路由中能量的均衡、簇頭的選擇算法進(jìn)行研究。綜上所述大多數(shù)學(xué)者從2 方面進(jìn)行研究，一方面是針對(duì)GA、PSO 結(jié)合的算法提出改進(jìn)，另一方面對(duì)路由算法進(jìn)行改進(jìn)。改進(jìn)后的算法對(duì)任意的網(wǎng)絡(luò)部署有很好的適應(yīng)性，更加滿足環(huán)境的要求，但同時(shí)算法并不能在進(jìn)化過程中進(jìn)行多次信息交換，2 種算法的互補(bǔ)性未得到充分發(fā)揮，實(shí)現(xiàn)過程也比較復(fù)雜，對(duì)實(shí)時(shí)性要求較高的網(wǎng)絡(luò)有一定的限制。

本文針對(duì)無線傳感器節(jié)點(diǎn)路由問題，將改進(jìn)的PSO 算法和改進(jìn)的遺傳算法結(jié)合，將遺傳算法的思想融入到粒子群算法中，通過對(duì)2 種算法相互交叉的改進(jìn)，使得算法避免早收斂，最終有較快的收斂速度。采用改進(jìn)的算法為無線傳感網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行簇頭節(jié)點(diǎn)選擇，改進(jìn)的算法保證了簇頭節(jié)點(diǎn)選擇的高效性，在提高WSN 的生存周期以及節(jié)點(diǎn)存活的數(shù)量的基礎(chǔ)上均衡了節(jié)點(diǎn)能量。仿真實(shí)驗(yàn)表明，本文算法可以延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間，保證網(wǎng)絡(luò)具有更加均衡的能耗。

1 WSN 模型及能耗模型

WSN 路由的主要問題是如何在收斂速度較快和低能耗的條件下，尋找源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)(Sink)的最優(yōu)路徑，保證數(shù)據(jù)能夠正確、高效持續(xù)地進(jìn)行轉(zhuǎn)發(fā)。由于WSN 中節(jié)點(diǎn)的通信、計(jì)算和存儲(chǔ)能力有限，而且經(jīng)常需要長(zhǎng)時(shí)間工作，工作過程中能量不能進(jìn)行補(bǔ)充。因此，WSN 路由算法的主要目標(biāo)是在滿足相關(guān)需求的同時(shí)盡可能地提高網(wǎng)絡(luò)資源利用率，降低能耗，延長(zhǎng)網(wǎng)絡(luò)的生存周期，擴(kuò)大網(wǎng)絡(luò)容量，提高吞吐率。

1.1 WSN 模型

WSN 數(shù)據(jù)傳輸過程中，首先源節(jié)點(diǎn)(Source node)按照一定的算法將數(shù)據(jù)發(fā)送所在簇的簇頭，然后簇頭將處理后的數(shù)據(jù)傳輸至Sink 節(jié)點(diǎn)，其中簇內(nèi)節(jié)點(diǎn)以單跳方式傳輸，簇間節(jié)點(diǎn)以多跳方式傳輸。在傳輸過程中，假設(shè)所有的傳感器節(jié)點(diǎn)都是靜止的，并且每個(gè)節(jié)點(diǎn)初始能量相同，相鄰節(jié)點(diǎn)知道彼此的ID、位置和剩余能量。將無線傳感器網(wǎng)絡(luò)用無向加權(quán)圖G=(V，E)表示，其中V 代表節(jié)點(diǎn)的集合，E 代表鏈路的集合。具體網(wǎng)絡(luò)模型如圖1 所示。

圖1 無線傳感器網(wǎng)絡(luò)模型

1.2 WSN 能耗模型

簇頭節(jié)點(diǎn)與Sink 節(jié)點(diǎn)間的距離為d，當(dāng)發(fā)送k bit數(shù)據(jù)時(shí)，傳感器節(jié)點(diǎn)所消耗的能量為:其中能耗模式分為2 種:自由空間能耗和多路徑衰減傳播能耗。Eelec為發(fā)送電路和接收電路消耗的能量，d0為閾值距離，εfs為自由空間消耗能量，當(dāng)d ＜d0時(shí)為自由空間能耗;εmp為多路徑衰減傳播能量，當(dāng)d≥d0時(shí)為多路徑能耗。其中接受k bit 數(shù)據(jù)，傳感器節(jié)點(diǎn)消耗的能量為kEelec。將m 個(gè)長(zhǎng)度為k bit 的數(shù)據(jù)包容和處理所消耗的能量為m×k×處理1bit 數(shù)據(jù)的能耗。

2 改進(jìn)的GA-PSO 路由算法

2.1 PSO 算法

粒子群算法(Particle Swarm Optimization，PSO)的基本概念源于對(duì)鳥群覓食行為的研究。設(shè)一個(gè)包含M 個(gè)粒子的D 維搜索空間，所有的粒子都有一個(gè)適應(yīng)值(Fitness Value)，這個(gè)適應(yīng)值是被目標(biāo)函數(shù)所決定的。為當(dāng)前粒子的位置，為粒子的速度，粒子們追隨當(dāng)前的最優(yōu)粒子，搜索決定它們飛翔的方向和距離。

其中，w 是慣性權(quán)重;pid是粒子本身所找到的最優(yōu)解;pgbest是整個(gè)種群目前找到的最優(yōu)解;rand()是介于(0，1)之間的隨機(jī)數(shù)，c1，c2是學(xué)習(xí)因子，通常c1=c2=2。

2.2 遺傳算法

遺傳算法(Genetic Algorithm，GA)是一類借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰遺傳機(jī)制)演化而來的隨機(jī)化搜索方法。一般由編碼機(jī)制、適應(yīng)值函數(shù)、遺傳算子、控制參數(shù)等4 部分組成，其工作流程如圖2 所示。

圖2 遺傳算法流程圖

遺傳算法在求解過程中，通過適應(yīng)調(diào)整交叉概率pc和變異概率pm對(duì)早收斂現(xiàn)象進(jìn)行控制，具體調(diào)整如下:

其中，fmax為最大適應(yīng)度，favg為平均適應(yīng)度，f'表示交叉?zhèn)€體的適應(yīng)度;f 表示變異個(gè)體的適應(yīng)度。k1，k2，k3，k4為適應(yīng)調(diào)整參數(shù)。

2.3 一種新的GA-PSO 算法設(shè)計(jì)

PSO 中的粒子在運(yùn)算過程中能夠根據(jù)自身的最優(yōu)位置和在整個(gè)群里的最優(yōu)位置來更新自己的速度和位置，但是由于前期收斂速度較快，后期很容易陷入局部最優(yōu)。為提高PSO 算法解的質(zhì)量，降低早熟收斂的比率，針對(duì)GA 算法與PSO 優(yōu)化算法的優(yōu)點(diǎn)，將2 種算法相結(jié)合，引入一種新的信息交流機(jī)制。將粒子群分為2 個(gè)，一個(gè)按照PSO 進(jìn)行進(jìn)化，一個(gè)按照GA 進(jìn)行進(jìn)化，每次進(jìn)化前都要進(jìn)行信息交流，選擇最優(yōu)個(gè)體形成新的粒子群再進(jìn)行下一代的進(jìn)化，淘汰最劣的個(gè)體。圖3 為GA-PSO 的優(yōu)化圖，從圖中可以看到首先將隨機(jī)種群分為2 組，一組為PSO 子群，按照PSO 進(jìn)行進(jìn)化;另一組為GA 子群，按照GA 進(jìn)行進(jìn)化，并對(duì)2 組進(jìn)行相關(guān)參數(shù)設(shè)置，然后對(duì)2 組種群進(jìn)化的結(jié)果進(jìn)行排序，選取部分最優(yōu)解形成新的種群。根據(jù)目標(biāo)函數(shù)再次更新2 個(gè)種群的相關(guān)參數(shù)。一直循環(huán)到指定的迭代次數(shù)，最后輸出最優(yōu)目標(biāo)函數(shù)和最優(yōu)解。

圖3 改進(jìn)后的GA-PSO 優(yōu)化圖

2.4 改進(jìn)的GA-PSO 路由算法目標(biāo)函數(shù)的建立

針對(duì)無線傳感網(wǎng)絡(luò)能量消耗不均的問題，在整個(gè)優(yōu)化過程中目標(biāo)函數(shù)的選擇非常關(guān)鍵，選取目標(biāo)函數(shù)時(shí)主要考慮以下3 點(diǎn):

1)簇頭節(jié)點(diǎn)能量，簇頭節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)和接收數(shù)據(jù)，所以比其他節(jié)點(diǎn)更消耗能量。因此某個(gè)節(jié)點(diǎn)的剩余能量越大，同時(shí)通過該節(jié)點(diǎn)向基站傳輸數(shù)據(jù)的能耗和最小，那么該節(jié)點(diǎn)成為簇頭的概率就越大。

2)簇頭需要收集和監(jiān)測(cè)節(jié)點(diǎn)，因此需要考慮簇頭到各個(gè)節(jié)點(diǎn)之間的總消耗能量。

3)由于WSN 的路由能耗主要消耗在傳輸過程中，所以需要考慮候選簇點(diǎn)到基站的距離。

因此，建立如下的目標(biāo)函數(shù):

其中，Ei表示當(dāng)前節(jié)點(diǎn)的剩余能量，μ 表示剩余能量均值，f1表示pi節(jié)點(diǎn)的剩余能量均衡，f2表示pi節(jié)點(diǎn)中y 到z 的總消耗能量，dib表示候選簇頭到基站的距離。α，β 分別為每個(gè)函數(shù)所占的權(quán)重。

具體步驟如下:

Step1 隨機(jī)產(chǎn)生2M 大小的種群，隨機(jī)將種群分為2 組，每組M 個(gè)個(gè)體，分別為PSO 子群和GA 子群。

Step2 設(shè)置并初始化相關(guān)參數(shù):最大迭代次數(shù)max_gen=100、初始迭代數(shù)gen=1、PSO 的權(quán)重因子C1、C2;GA 的交叉變異概率、種群的位置、速度、極值、粒子的最大速度。

Step3 如果gen≤max_gen，進(jìn)入Step4，否則轉(zhuǎn)Step7。

Step4 對(duì)于2 組種群，分別采用PSO 和GA 進(jìn)行進(jìn)化，對(duì)進(jìn)化的結(jié)果進(jìn)行排序，選取最小的M 個(gè)最優(yōu)解，選擇最優(yōu)解進(jìn)行復(fù)制保持粒子的數(shù)量為2M。

Step5 根據(jù)目標(biāo)函數(shù)按照公式(2)和公式(3)更新粒子的位置與速度;按照公式(4)和公式(5)分別以pC和pm的概率進(jìn)行交叉和變異。

Step6 通過GA 生成的M 個(gè)個(gè)體和PSO 進(jìn)化的M 個(gè)粒子合并，組成新的2M 個(gè)粒子。

Step7 Gen=Gen+1，返回到Step3。

Step8 輸出最優(yōu)目標(biāo)函數(shù)和最優(yōu)解。

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

3.1 仿真環(huán)境設(shè)置

為了驗(yàn)證改進(jìn)的無線傳感器路由算法的性能，對(duì)路由算法的目標(biāo)函數(shù)分別進(jìn)行改進(jìn)GA-PSO 算法、文獻(xiàn)［4］中的GA-PSO 算法、PSO 算法、GA 算法的對(duì)比實(shí)驗(yàn)，分別對(duì)節(jié)點(diǎn)剩余能耗和網(wǎng)絡(luò)中節(jié)點(diǎn)的存活數(shù)量進(jìn)行Matlab 仿真。仿真實(shí)驗(yàn)區(qū)域參數(shù)如表1 所示。

表1 仿真參數(shù)設(shè)置

3.2 結(jié)果與分析

由于本文采用了PSO 和遺傳算法2 種算法的結(jié)合。在選擇簇點(diǎn)時(shí)，考慮了簇頭節(jié)點(diǎn)能量，當(dāng)某個(gè)節(jié)點(diǎn)的剩余能量越大，同時(shí)通過該節(jié)點(diǎn)向基站傳輸數(shù)據(jù)的能耗和最小，那么該節(jié)點(diǎn)成為簇頭的概率就越大;考慮簇頭到各個(gè)節(jié)點(diǎn)之間的總消耗能量;考慮候選簇點(diǎn)到基站的距離。所以從仿真結(jié)果圖4 可以看到，本算法的節(jié)點(diǎn)剩余能量均衡性比未改進(jìn)的GA-PSO 提高5%，比PSO 和GA 算法的性能提高約10%～15%。從圖5 中可以得到，采用改進(jìn)的GA-PSO 算法比未改進(jìn)的延長(zhǎng)了210 輪，未改進(jìn)的GA-PSO 比PSO和GA 分別延長(zhǎng)了340 輪和390 輪，從結(jié)果可以看到采用改進(jìn)的GA-PSO 算法的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)比對(duì)比算法改進(jìn)較多，改進(jìn)的GA-PSO 算法能夠有效地延長(zhǎng)網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目以及時(shí)間。

圖4 節(jié)點(diǎn)的剩余能量

圖5 網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目對(duì)比

4 結(jié)束語

為了提高無線傳感器網(wǎng)絡(luò)的生存周期，保證能量在節(jié)點(diǎn)傳輸過程中的均衡性，針對(duì)PSO 以及遺傳算法提出一種改進(jìn)GA-PSO 算法優(yōu)化無線傳感器網(wǎng)絡(luò)路由算法。采用改進(jìn)的算法為無線傳感網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行簇頭節(jié)點(diǎn)選擇，改進(jìn)的算法保證了簇頭節(jié)點(diǎn)選擇，從整體上節(jié)約了網(wǎng)絡(luò)節(jié)點(diǎn)的能量，有效地延長(zhǎng)了網(wǎng)絡(luò)的生存周期。仿真對(duì)比實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法均衡了能量消耗，延長(zhǎng)了網(wǎng)絡(luò)生存周期，具有較好的適應(yīng)性和健壯性，可以應(yīng)用到大規(guī)模的無線傳感網(wǎng)絡(luò)中。

［1］雷秀娟，付阿利，孫晶晶.改進(jìn)PSO 算法的性能分析與研究［J］.計(jì)算機(jī)應(yīng)用研究，2010，27(2):453-458.

［2］姚坤，李菲菲，劉希玉.一種基于PSO 和GA 的混合算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(6):62-64.

［3］王亞利，王宇平.基于混合的GA-PSO 神經(jīng)網(wǎng)絡(luò)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(2):38-40，56.

［4］趙欣，葉慶衛(wèi)，周宇.一種保持PSO 與GA 獨(dú)立性的混合優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(26):53-55，100.

［5］陳璟，張曦煌.用PSO 優(yōu)化基于QoS 的WSN 路由協(xié)議［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(20):4931-4933.

［6］趙青杉，胡玉蘭.基于PSO 的無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.計(jì)算機(jī)仿真，2012，29(5):174-177.

［7］沈海洋.劉安豐，吳賢佑，等.一種基于PSO 的有效能量空洞避免的無線傳感器路由算法［J］.計(jì)算機(jī)研究與發(fā)展，2009(4):575-582.

［8］沈海洋.基于遺傳PSO 的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化算法研究［J］.微電子學(xué)與計(jì)算機(jī)，2013，30(3):148-151.

［9］朱永紅，丁恩杰，胡延軍.PSO 優(yōu)化的能耗均衡WSNs路由算法［J］.儀器儀表學(xué)報(bào)，2015，36(1):78-86.

［10］周瑩.改進(jìn)遺傳算法優(yōu)化無線傳感器網(wǎng)絡(luò)路由算法［J］.激光雜志，2015，36(1):113-116.

［11］王力，陳曉磊.基于固定分簇的PSO 優(yōu)化無線傳感器網(wǎng)絡(luò)路由算法［J］.計(jì)算機(jī)測(cè)量與控制，2015，23(4):1309-1311，1315.

［12］張世偉，張海濤，張士杰.基于固定分簇和能量均衡的無線傳感器網(wǎng)絡(luò)多跳路由算法［J］.傳感器與微系統(tǒng)，2013，32(8):117-120，124.

［13］李聰.WSN 中基于能量均衡的路由算法研究［D］.廣州:廣東工業(yè)大學(xué)，2013.

［14］孫涌泉.基于遺傳算法的多約束QoS 多播路由算法研究［D］.哈爾濱:哈爾濱工程大學(xué)，2008.

［15］吉云.基于分簇的無線傳感器網(wǎng)絡(luò)簇頭選擇優(yōu)化算法研究［D］.太原:太原科技大學(xué)，2009.