崔小勇， 林 寧,2

(1.上海海洋大學(xué) 信息學(xué)院，上海 201306；2.國(guó)家海洋局信息中心,天津 300171)

基于遺傳模擬退火算法的無(wú)線傳感器網(wǎng)路由協(xié)議*

崔小勇1， 林 寧1,2

(1.上海海洋大學(xué) 信息學(xué)院，上海 201306；2.國(guó)家海洋局信息中心,天津 300171)

在無(wú)線傳感器網(wǎng)絡(luò)中(WSNs)中，由于節(jié)點(diǎn)能量有限，為了延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存周期，提出一種基于遺傳模擬退火算法的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議。利用模擬退火(SA)算法具有較強(qiáng)的局部搜索能力并能以穩(wěn)定的速度收斂，克服遺傳算法(GA)局部搜索能力差并容易早熟收斂等缺點(diǎn)。該路由協(xié)議在簇頭節(jié)點(diǎn)選舉時(shí)充分考慮了節(jié)點(diǎn)的剩余能量，并根據(jù)網(wǎng)絡(luò)中數(shù)據(jù)轉(zhuǎn)發(fā)能量耗損和延遲時(shí)間建立個(gè)體適應(yīng)度函數(shù)，采用遺傳模擬退火算法找到簇頭節(jié)點(diǎn)到基站的最優(yōu)路徑。仿真結(jié)果表明:與其他協(xié)議比較，該方法不僅可以均衡各個(gè)節(jié)點(diǎn)的剩余能量，還可以有效延長(zhǎng)整個(gè)網(wǎng)絡(luò)生存周期和提高網(wǎng)絡(luò)的數(shù)據(jù)傳輸能力。

無(wú)線傳感器網(wǎng)絡(luò)； 遺傳算法； 模擬退火； 生存周期

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(WSNs)[1]是由分布在不同區(qū)域內(nèi)大量的微型傳感器節(jié)點(diǎn)組成。它是以一種無(wú)線通信的方式形成一個(gè)網(wǎng)絡(luò)系統(tǒng)，其主要工作目的是采集和處理網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)感知對(duì)象的信息，并發(fā)布給觀察者[2]。由于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)攜帶的電池能量有限,且節(jié)點(diǎn)布置之后不容易更換電池，所以,減少無(wú)線傳感器網(wǎng)絡(luò)的能量消耗，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期是目前無(wú)線傳感器網(wǎng)絡(luò)研究的主要問(wèn)題[3]。

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來(lái)分主要有兩種路由協(xié)議：層次路由協(xié)議和平面路由協(xié)議[4]。LEACH協(xié)議[5,6]就是一種比較常用和成熟的分層路由協(xié)議。LEACH協(xié)議將整個(gè)網(wǎng)絡(luò)劃分成多個(gè)簇，每個(gè)簇包括一個(gè)簇首節(jié)點(diǎn)跟其余普通節(jié)點(diǎn)，周期性的輪換簇頭節(jié)點(diǎn)[7]。但由于LEACH算法簇頭隨機(jī)產(chǎn)生，沒(méi)有考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量，可能導(dǎo)致最后的分簇不合理，降低了網(wǎng)絡(luò)的生存周期。簇頭直接與基建通信，若兩者之間的距離過(guò)大，會(huì)增大整個(gè)網(wǎng)絡(luò)的能耗。

為了平衡無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存周期，提出了一種遺傳模擬退火算法的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議。仿真結(jié)果表明，遺傳模擬退火算法的無(wú)線傳感器網(wǎng)路由協(xié)議不僅可以延長(zhǎng)網(wǎng)絡(luò)的生存周期，還可以提高網(wǎng)絡(luò)數(shù)據(jù)傳輸能力。

1 通信能耗模型與網(wǎng)絡(luò)模型

任意傳感器節(jié)點(diǎn)發(fā)送mbit的數(shù)據(jù)到距離d的位置，傳感器節(jié)點(diǎn)所消耗的能量為

(1)

(2)

式中Eelec為發(fā)送電路和接收電路每發(fā)送或接收單位比特幣所消耗的能量,εfs為自由空間傳播模型下功率放大所需要的耗能系數(shù),εmp為多路徑衰減傳播模型下功率放大所需要的耗能系數(shù),D0為門(mén)限距離[8]。

2 改進(jìn)遺傳算法的路由協(xié)議

2.1 簇的建立階段

一般情況下，無(wú)線傳感器網(wǎng)絡(luò)會(huì)被分成多個(gè)大小不同的簇，每個(gè)簇中包括一個(gè)簇頭節(jié)點(diǎn)跟多個(gè)普通節(jié)點(diǎn)。由于簇頭節(jié)點(diǎn)不僅要負(fù)責(zé)接收、融合、傳輸簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)而且還要負(fù)責(zé)轉(zhuǎn)發(fā)其他簇頭節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)，因此，簇頭節(jié)點(diǎn)的選擇應(yīng)考慮傳感器節(jié)點(diǎn)的剩余能量。本文在選擇簇頭節(jié)點(diǎn)的時(shí)候，綜合考慮傳感器節(jié)點(diǎn)的剩余能量，首先計(jì)算整個(gè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能量平均值Eavg，然后再計(jì)算每一個(gè)傳感器節(jié)點(diǎn)的剩余能量，如果該傳感器節(jié)點(diǎn)能量低于Eavg則退出簇首節(jié)點(diǎn)的選擇。對(duì)于每一個(gè)傳感器節(jié)點(diǎn)，如果被選中當(dāng)簇頭節(jié)點(diǎn)，那么該節(jié)點(diǎn)向整個(gè)無(wú)線傳感網(wǎng)廣播自己的信息，其他傳感器節(jié)點(diǎn)根據(jù)自己與簇頭節(jié)點(diǎn)的距離加入相應(yīng)的簇。

2.2 數(shù)據(jù)傳輸階段

設(shè)無(wú)線傳感器網(wǎng)絡(luò)的簇頭集合為S=(s1,s2,…,skopt)，其中，skopt表示最優(yōu)簇頭數(shù)本文采用遺傳模擬退火算法選擇最佳數(shù)據(jù)傳輸路徑。

1)個(gè)體編碼方式

個(gè)體編碼采用整數(shù)編碼方式，每個(gè)基因表示經(jīng)過(guò)的簇頭節(jié)點(diǎn)，比如當(dāng)經(jīng)過(guò)的簇頭節(jié)點(diǎn)數(shù)目為5，染色體為[2,3,4,1,5]，表示簇頭節(jié)點(diǎn)遍歷從2開(kāi)始經(jīng)過(guò)3，4，1，最后到5，從而完成遍歷。

2)適應(yīng)度函數(shù)確定

為了延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)生命周期，盡量減少數(shù)據(jù)傳輸過(guò)程中的時(shí)間延時(shí)，適應(yīng)度函數(shù)可以描述如下

(3)

式中 ei為簇頭節(jié)點(diǎn)消耗的能量，t為時(shí)間延遲，a,b為權(quán)重系數(shù)，且a+b=1。

3)選擇操作

選擇的目的是盡量保留種群的最優(yōu)化個(gè)體，首先將最優(yōu)的個(gè)體保留到下一代，其他個(gè)體采用輪盤(pán)賭的方法，個(gè)體適應(yīng)度值越大，被選擇作為下一代父代的概率越大。根據(jù)個(gè)體適應(yīng)度值計(jì)算其被選擇的概率，每個(gè)個(gè)體被選中的概率為

(4)

式中 fi為個(gè)體適應(yīng)度值，f為平均適應(yīng)度值。

4)交叉操作

交叉算法是以某一概率相互交換兩個(gè)個(gè)體之間的部分染色體。本文采用單點(diǎn)交叉的方法，具體交叉方式如圖1所示。

圖1 兩個(gè)染色體的交叉方式Fig 1 Two chromosomal crossover mode

5)變異操作

變異操作時(shí)為了提高種群的適應(yīng)能力，保證種群的多樣性。具體操作方式如下：隨機(jī)選擇一個(gè)個(gè)體中的傳感器節(jié)點(diǎn)xk，然后選擇一個(gè)新的傳感器節(jié)點(diǎn)xl代替xk。

6)模擬退火操作

3 仿真與結(jié)果分析

3.1 仿真環(huán)境

在邊長(zhǎng)100m×100m的正方形區(qū)域內(nèi)，隨機(jī)分布100個(gè)傳感器節(jié)點(diǎn)，仿真采用Matlab2013b模擬，仿真具體環(huán)境設(shè)置如表1。

表1 實(shí)驗(yàn)參數(shù)設(shè)置 Tab 1 Experimental parameters settings

3.2 結(jié)果與分析

在不同的工作次數(shù)下，遺傳算法與本文算法相比，第1個(gè)節(jié)點(diǎn)死亡、第40個(gè)死亡、最后一個(gè)節(jié)點(diǎn)死亡時(shí)間如表2所示。

表2 傳感器節(jié)點(diǎn)死亡時(shí)間Tab 2 Time of death of sensor nodes

無(wú)線傳感網(wǎng)絡(luò)生存周期如圖2所示。

圖2 節(jié)點(diǎn)剩余數(shù)對(duì)比Fig 2 Contrast of node number of remaining

從圖2中可以看出，本文采用的無(wú)線傳感器路由協(xié)議可以延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期，這主要由于本文算法在選擇簇頭節(jié)點(diǎn)的時(shí)候充分考慮了網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)自身的剩余能量，同時(shí)也考慮了數(shù)據(jù)傳輸過(guò)程中節(jié)點(diǎn)與基站之間的跳數(shù)。

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

為了延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存周期，提出一種基于遺傳模擬退火算法的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議。仿真對(duì)比實(shí)驗(yàn)說(shuō)明：本文提出的算法不僅可以延長(zhǎng)網(wǎng)絡(luò)的生存周期還可以提升網(wǎng)絡(luò)的數(shù)據(jù)傳輸能力。

[1] Xiao Renyi,Wu Guozheng.A survey on routing in wireless sensor networks[J].Progress in Natural Science,2007(3):261-269.

[2] 畢 冉,李建中.無(wú)線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[J].智能計(jì)算機(jī)與應(yīng)用,2014(6):54-56,60.

[3] 唐 宏,謝 靜,獸玉芬,等.無(wú)線傳感器網(wǎng)絡(luò)原理及應(yīng)用[M].北京:人民郵電出版社,2010.

[4] AI-Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].IEEE Wireless Communications,2004,11(6):6- 28.

[5] Heinzelman W,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor network-s[J].IEEE Transactions on Wireless Communications,2002,1(4):660- 670.

[6] 任豐原,黃海寧,林 闖.無(wú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2003,14(7):1282-1291.

[7] 盧建剛,樂(lè)紅兵.基于節(jié)點(diǎn)相對(duì)密度的無(wú)線傳感器網(wǎng)絡(luò)成簇算法[J].傳感技術(shù)學(xué)報(bào),2011(4):587-592.

[8] 李成法,陳貴海,葉 懋,等.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2007(1):27-36.

WSNs routing protocol based on genetic simulated annealing algorithm*

CUI Xiao-yong1， LIN Ning1,2

(1.College of Information Technology,Shanghai Ocean University,Shanghai 201306,China;2.National Marine Data & Information Service,Tianjin 300171,China)

In wireless sensor networks(WSNs),due to limited energy of node,in order to extend life cycle of the whole network,a kind of WSNs routing protocol based on genetic simulated annealing algorithm is proposed.Using the simulated annealing algorithm has strong local search ability and can converge in stabilize speed,overcome shortcomings of poor local search ability and easy to premature convergence of Genetic algorithm.The routing portocol fully considers residual energy of nodes in election of cluster head nodes,and according to energy loss of data forwarding in network and delay time to establish individual fitness function,using genetic simulated annealing algorithm to find the optimal path from cluster head nodes to base station. Simulation results show that,compared with other protocols,this method can not only balance remaining energy of each node,but also can effectively prolong the network life cycle and improve data transmission capability of network.

wireless sensor networks(WSNs); genetic algorithm(GA); simulated annealing(SA); life cycle

10.13873/J.1000—9787(2016)07—0032—03

2015—10—29

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272098);上海市科委科研計(jì)劃重點(diǎn)支撐資助項(xiàng)目(1251050200)

TP 393

A

1000—9787(2016)07—0032—03

崔小勇(1990-)，男，江蘇鹽城人，碩士研究生，主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)開(kāi)發(fā)、無(wú)線傳感器網(wǎng)絡(luò)。