基于遺傳模擬退火算法的無線傳感器網路由協議*

崔小勇， 林 寧,2

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

基于遺傳模擬退火算法的無線傳感器網路由協議*

崔小勇1， 林 寧1,2

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

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

無線傳感器網絡； 遺傳算法； 模擬退火； 生存周期

0 引 言

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

針對無線傳感器網絡路由協議，從網絡拓撲結構來分主要有兩種路由協議：層次路由協議和平面路由協議[4]。LEACH協議[5,6]就是一種比較常用和成熟的分層路由協議。LEACH協議將整個網絡劃分成多個簇，每個簇包括一個簇首節點跟其余普通節點，周期性的輪換簇頭節點[7]。但由于LEACH算法簇頭隨機產生，沒有考慮網絡中節點的剩余能量，可能導致最后的分簇不合理，降低了網絡的生存周期。簇頭直接與基建通信，若兩者之間的距離過大，會增大整個網絡的能耗。

為了平衡無線傳感器網絡節點的能量消耗，延長無線傳感器網絡的生存周期，提出了一種遺傳模擬退火算法的無線傳感器網絡路由協議。仿真結果表明，遺傳模擬退火算法的無線傳感器網路由協議不僅可以延長網絡的生存周期，還可以提高網絡數據傳輸能力。

1 通信能耗模型與網絡模型

任意傳感器節點發送mbit的數據到距離d的位置，傳感器節點所消耗的能量為

(1)

(2)

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

2 改進遺傳算法的路由協議

2.1 簇的建立階段

一般情況下，無線傳感器網絡會被分成多個大小不同的簇，每個簇中包括一個簇頭節點跟多個普通節點。由于簇頭節點不僅要負責接收、融合、傳輸簇內節點的數據而且還要負責轉發其他簇頭節點傳輸的數據，因此，簇頭節點的選擇應考慮傳感器節點的剩余能量。本文在選擇簇頭節點的時候，綜合考慮傳感器節點的剩余能量，首先計算整個無線傳感器網絡節點的能量平均值Eavg，然后再計算每一個傳感器節點的剩余能量，如果該傳感器節點能量低于Eavg則退出簇首節點的選擇。對于每一個傳感器節點，如果被選中當簇頭節點，那么該節點向整個無線傳感網廣播自己的信息，其他傳感器節點根據自己與簇頭節點的距離加入相應的簇。

2.2 數據傳輸階段

設無線傳感器網絡的簇頭集合為S=(s1,s2,…,skopt)，其中，skopt表示最優簇頭數本文采用遺傳模擬退火算法選擇最佳數據傳輸路徑。

1)個體編碼方式

個體編碼采用整數編碼方式，每個基因表示經過的簇頭節點，比如當經過的簇頭節點數目為5，染色體為[2,3,4,1,5]，表示簇頭節點遍歷從2開始經過3，4，1，最后到5，從而完成遍歷。

2)適應度函數確定

為了延長無線傳感器網絡生命周期，盡量減少數據傳輸過程中的時間延時，適應度函數可以描述如下

(3)

式中 ei為簇頭節點消耗的能量，t為時間延遲，a,b為權重系數，且a+b=1。

3)選擇操作

選擇的目的是盡量保留種群的最優化個體，首先將最優的個體保留到下一代，其他個體采用輪盤賭的方法，個體適應度值越大，被選擇作為下一代父代的概率越大。根據個體適應度值計算其被選擇的概率，每個個體被選中的概率為

(4)

式中 fi為個體適應度值，f為平均適應度值。

4)交叉操作

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

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

5)變異操作

變異操作時為了提高種群的適應能力，保證種群的多樣性。具體操作方式如下：隨機選擇一個個體中的傳感器節點xk，然后選擇一個新的傳感器節點xl代替xk。

6)模擬退火操作

3 仿真與結果分析

3.1 仿真環境

在邊長100m×100m的正方形區域內，隨機分布100個傳感器節點，仿真采用Matlab2013b模擬，仿真具體環境設置如表1。

表1 實驗參數設置 Tab 1 Experimental parameters settings

3.2 結果與分析

在不同的工作次數下，遺傳算法與本文算法相比，第1個節點死亡、第40個死亡、最后一個節點死亡時間如表2所示。

表2 傳感器節點死亡時間Tab 2 Time of death of sensor nodes

無線傳感網絡生存周期如圖2所示。

圖2 節點剩余數對比Fig 2 Contrast of node number of remaining

從圖2中可以看出，本文采用的無線傳感器路由協議可以延長整個網絡的生命周期，這主要由于本文算法在選擇簇頭節點的時候充分考慮了網絡中傳感器節點自身的剩余能量，同時也考慮了數據傳輸過程中節點與基站之間的跳數。

4 結束語

為了延長無線傳感器網絡的生存周期，提出一種基于遺傳模擬退火算法的無線傳感器網絡路由協議。仿真對比實驗說明：本文提出的算法不僅可以延長網絡的生存周期還可以提升網絡的數據傳輸能力。

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

[2] 畢 冉,李建中.無線傳感器網絡關鍵技術研究[J].智能計算機與應用,2014(6):54-56,60.

[3] 唐 宏,謝 靜,獸玉芬,等.無線傳感器網絡原理及應用[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] 任豐原,黃海寧,林 闖.無線傳感器網絡[J].軟件學報,2003,14(7):1282-1291.

[7] 盧建剛,樂紅兵.基于節點相對密度的無線傳感器網絡成簇算法[J].傳感技術學報,2011(4):587-592.

[8] 李成法,陳貴海,葉 懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報,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

國家自然科學基金資助項目(61272098);上海市科委科研計劃重點支撐資助項目(1251050200)

TP 393

A

1000—9787(2016)07—0032—03

崔小勇(1990-)，男，江蘇鹽城人，碩士研究生，主要研究領域為嵌入式系統開發、無線傳感器網絡。