基于GA和LEACH的WSN引入交通層路徑優(yōu)化算法

李玉霞，徐永鑫，何 磊，張向秀

(1. 電子科技大學(xué)自動化工程學(xué)院 成都 611731；2. 成都理工大學(xué)國土資源部地學(xué)空間信息技術(shù)重點實驗室 成都 610059；3. 電子科技大學(xué)光電信息學(xué)院 成都 610054；4. 成都信息工程大學(xué)軟件工程學(xué)院 成都 610225)

基于GA和LEACH的WSN引入交通層路徑優(yōu)化算法

李玉霞1,2，徐永鑫3，何 磊4，張向秀3

(1. 電子科技大學(xué)自動化工程學(xué)院 成都 611731；2. 成都理工大學(xué)國土資源部地學(xué)空間信息技術(shù)重點實驗室 成都 610059；3. 電子科技大學(xué)光電信息學(xué)院 成都 610054；4. 成都信息工程大學(xué)軟件工程學(xué)院 成都 610225)

針對WSN節(jié)點中分層分簇路由算法存在能耗不均衡、簇首能耗高的問題，提出了一種基于GA和LEACH的WSN引入交通層路徑優(yōu)化算法。該算法基于ZigBee協(xié)議引入了新的拓?fù)浣Y(jié)構(gòu)，并優(yōu)化了基于距離和能量因素的閾值函數(shù)，從而對WSN進(jìn)行優(yōu)化。仿真結(jié)果表明，在增加9%整體耗能的前提下，減少了關(guān)鍵簇首95%的通信能耗，有效地提高了WSN能耗均勻性，并延長了WSN 1～3倍的整體工作壽命。

遺傳算法; 交通層; 無線傳感網(wǎng)絡(luò); ZigBee協(xié)議

無線傳感網(wǎng)絡(luò)(WSN)是目前國內(nèi)外的前沿和熱門研究方向，在工業(yè)監(jiān)測和控制、家居自動化和安全、軍事監(jiān)控和追蹤等方面有著廣泛的應(yīng)用[1]。因WSN節(jié)點有效運行的時間有限，所以如何減少能耗是WSN應(yīng)用和研究中的關(guān)鍵難題。ZigBee是一套常用、自適應(yīng)、減少能耗的WSN路由協(xié)議[2]，它主要使用Cluster-tree協(xié)議[3]和AODV(Ad hock on-demand distance vector)協(xié)議[4]來構(gòu)建系統(tǒng)。在Cluster-tree協(xié)議中通過分簇選取簇首的方式收集簇內(nèi)信息，簇首間用ADOV協(xié)議相互搜索自適應(yīng)基站通信。Clustertree的問題在于簇首的能耗遠(yuǎn)遠(yuǎn)高于普通節(jié)點，使簇首的壽命大大減少，而簇首節(jié)點失效將導(dǎo)致該簇上的所有節(jié)點與基站失去聯(lián)系。AODV的缺陷主要有根據(jù)自適應(yīng)路由協(xié)議尋找的路徑可能不是最優(yōu)路徑、實時性不足、能耗高、系統(tǒng)能耗均勻性差等。

針對上述存在的問題，文獻(xiàn)[5]在LEACH協(xié)議中考慮了能耗因子，從而有效延長了WSN的運行周期，但沒有探討距離因素。文獻(xiàn)[6]研究表明了遺傳算法在WSN路徑優(yōu)化中的有效性，找到了優(yōu)化路徑并成功避開了能耗低的節(jié)點，但未對具體能耗情況進(jìn)行深入分析，并且在距離方面也討論不足。文獻(xiàn)[7]在WSN中引入了中間層從而達(dá)到了均勻能耗的效果，但是只根據(jù)距離因素采用動態(tài)路由方式對路徑進(jìn)行構(gòu)建，一定程度上忽略了能量因素以及拓?fù)浣Y(jié)構(gòu)的優(yōu)化研究。本文針對ZigBee的Cluster-tree以及AODV路由協(xié)議現(xiàn)有的不足，通過引入新的拓?fù)浜椭虚g節(jié)點(下面稱為交通層)，及與之匹配的綜合考慮能量與距離因素的優(yōu)化算法，來均勻簇首能耗，從根本上解決簇首能耗大的問題以及WSN整體能耗均勻性問題。

1 GA算法和LEACH算法

1.1 GA算法

遺傳算法(GA)是一種基于自然選擇原理和自然遺傳機(jī)制的搜索(尋優(yōu))算法。在GA算法中，染色體某一位置上具有相同位值的染色體的子集合通常稱為基因模式(schemata)。在遺傳算法中，模式階次指基因模式中定義位置(即為0或l)的個數(shù)，而模式定義長度則為基因模式中兩個最外定義位置之間的距離。模式階次O(H)和定義長度σ(H)是量化基因模式?；诖硕x，由已知的第n代群體中基因模式H的數(shù)目m(H,n)，可得到n+1代群體中基因模式H的期望數(shù)下界為：

式中，f(H)為基因模式H的適應(yīng)度；l為染色體C的位串長度；fav為群體所有染色體的平均適應(yīng)度；cP為雜交概率；Pm為突變概率。

那么，實現(xiàn)GA算法基本流程為：1) 初始群體的產(chǎn)生；2) 求每一個個體的適應(yīng)度；3) 根據(jù)適者生存的原則，選擇優(yōu)良個體；4) 被選出的優(yōu)良個體兩兩配對；5) 通過隨機(jī)交叉和變異某些染色體的基因，生成下一代群體。按此方法使群體一代代的進(jìn)化，直到滿足進(jìn)化的終止條件。

具體實現(xiàn)方法：根據(jù)具體問題確定可行解域和編碼方法，用字符串或數(shù)值串表示可行解域的每一個解。選取適應(yīng)度函數(shù)為每一個解的度量依據(jù)。適應(yīng)度函數(shù)為非負(fù)函數(shù)，本文選取GA的適應(yīng)度函數(shù)為：

式中，d為節(jié)點間的距離；n為選擇的節(jié)點個數(shù)；π為編碼方法。

確定進(jìn)化參數(shù)群體規(guī)模M、交叉概率cP、變異概率Pm、進(jìn)化終止條件。

本文選用自適應(yīng)方法選取雜交概率，有:

本文采取自適應(yīng)方法選取變異概率，有:

式中，

1.2 LEACH算法

LEACH算法采用隨機(jī)方式選取簇首，在LEACH協(xié)議中，WSN執(zhí)行過程是周期的，系統(tǒng)更新一次稱為一輪，一輪包括簇的建立和穩(wěn)定運行階段。在簇的建立階段，簇首會換屆選舉，即對節(jié)點n隨機(jī)選擇一個值，若該值小于一個閾值，則節(jié)點n成為本輪的簇首節(jié)點。閾值的表達(dá)式為：

式中，p是簇首節(jié)點占總節(jié)點的百分比；r是當(dāng)前輪次。本文根據(jù)式(5)選舉簇首。

2 WSN引入交通層路徑優(yōu)化算法

通過本文設(shè)計的如圖1所示算法流程對WSN引入交通層路徑進(jìn)行算法優(yōu)化：

1) WSN的初始分簇

WSN在工作后首先建立網(wǎng)絡(luò)，各節(jié)點用浮點編碼表示[8]，根據(jù)相互距離通過GA算法進(jìn)行分簇[9]，得到一個最優(yōu)的初始簇首情況。

2) WSN選舉出簇首

在同一簇的WSN中，本文在LEACH算法中引入能量與距離因素，每一輪中通過一個優(yōu)化的閾值對同簇的WSN進(jìn)行選舉，選出最合適的簇首。

在LEACH算法中式(6)的r為當(dāng)前輪次，為一固定的值。本文用剩余能量值和與交通層的距離d對r值進(jìn)行修正。

節(jié)點剩余能量的計算為：

式中，RemEng代表節(jié)點剩余能量；PktT代表發(fā)送數(shù)據(jù)包數(shù)量；TEng代表發(fā)送一次數(shù)據(jù)包所消耗的能量；PktR代表接收數(shù)據(jù)包的數(shù)量；REng代表接收一次數(shù)據(jù)包需要的能量。

最終r修正的表達(dá)式為：

式中，d為簇首與待選交通層的距離。

圖1 引入交通層的總程序流程圖

3) WSN引入交通層

簇首選舉完后，簇首收集一輪簇內(nèi)數(shù)據(jù)[10-12]，并對簇首與基站之間建立交通層，即引入中間節(jié)點與基站通信。根據(jù)簇首節(jié)點的實際分布情況，可以利用GA算法對其進(jìn)行最優(yōu)的初始化設(shè)計，這使路徑設(shè)計最優(yōu)化。通過調(diào)整交通層的個數(shù)，便可以根據(jù)需求獲得所需的WSN的工作距離，具有很好的適應(yīng)性。圖2為交通層拓?fù)鋱D。

根據(jù)WSN簇首的分布情況，結(jié)合能量和距離因素式(7)對不同的情況采用不同的拓?fù)湓O(shè)計，分別為共用拓?fù)?、平行拓?fù)湟约皬?fù)合拓?fù)洹?/p>

① 共用拓?fù)洌憾鄠€簇首節(jié)點共享一個交通層與基站進(jìn)行通信。在工作量較少、信息傳輸要求較低的區(qū)域，這種設(shè)計有利于提高資源利用率。② 平行拓?fù)洌簡蝹€簇首節(jié)點通過特定的交通層與基站進(jìn)行通信。在工作量較高、信息傳輸要求較高的區(qū)域，這種設(shè)計有助于增強(qiáng)WSN傳輸?shù)膶崟r性。③ 復(fù)合拓?fù)洌捍厥着c交通層之間綜合使用共用拓?fù)浜推叫型負(fù)浣Y(jié)構(gòu)，形成一對多、多對一、多對多的復(fù)雜結(jié)構(gòu)來滿足實際應(yīng)用中的需求。

圖2 交通層的拓?fù)浣Y(jié)構(gòu)

網(wǎng)絡(luò)復(fù)雜程度越高，交通層的設(shè)計越精細(xì)，WSN的性能也就更接近實際的需求。本文利用GA算法對簇首接入交通層的拓?fù)溥M(jìn)行基于能耗與距離情況的實時優(yōu)化更新，其具體操作方式如圖3所示。

圖3 共用拓?fù)浣Y(jié)構(gòu)

在每一輪簇的建立階段之后，要對簇首接入交通層的拓?fù)湫问竭M(jìn)行更新，本文對GA算法的初始適應(yīng)度函數(shù)進(jìn)行了優(yōu)化，其中初始適應(yīng)度函數(shù)為：

式中，d為簇首與待選交通層的距離。

根據(jù)WSN簇首在實際運用中簇首工作量的不同，引入一個實時變化的權(quán)值η描述各個節(jié)點的忙碌程度，其表達(dá)式為：式中，RemEng為節(jié)點剩余的能量；InitEng為初始總能量。系統(tǒng)會優(yōu)先對η值較高的簇首進(jìn)行分配。同理引入μ值對交通層忙碌程度進(jìn)行描述，有：

式中，k為交通層中第k個節(jié)點；n代表共有n個簇首接入這個節(jié)點中；iη對應(yīng)第i個接入交通層的當(dāng)前能耗大小。最終GA算法的適應(yīng)度函數(shù)優(yōu)化為：

由式(7)、式(8)和式(10)可知，節(jié)點能耗越高，距離交通層越遠(yuǎn)，被選為簇首的概率越小。

4) 簇首換屆交換交通層鑰匙

在簇首換屆選舉之后，上屆簇首發(fā)送一個數(shù)據(jù)包給下屆簇首告知對應(yīng)的交通層節(jié)點的地址，而本身遺忘交通層地址，這種設(shè)計相對于AODV協(xié)議的自適應(yīng)找尋方式的優(yōu)勢在于只需要發(fā)送一次數(shù)據(jù)包便可以完成路徑的建立，有效減少了AODV自適應(yīng)過程的通信能耗和延遲時間。同時這種密匙交換的方法，降低了WSN節(jié)點記憶性能要求，可以減少能耗和降低成本。

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

圖4 仿真程序流程圖

本文基于MATLAB，首先使用GA算法對WSN的節(jié)點進(jìn)行初始分布的最優(yōu)化設(shè)計，使用LEACH算法選舉第一屆簇首，然后對沒有引入交通層和引入交通層分別進(jìn)行了仿真和研究，仿真程序流程如圖4所示，并對結(jié)果進(jìn)行了可視化顯示。其中對于優(yōu)化LEACH算法式(9)，仿真數(shù)值由表1所示。

表1 仿真模擬參數(shù)

3.1 可視化分布結(jié)果

圖5 WSN分布可視化顯示

WSN分布可視化顯示結(jié)果如圖5所示，對其耗能情況進(jìn)行了顯示，圖中的圖例代表了產(chǎn)生的能耗大小。本文發(fā)現(xiàn)簇首能量遠(yuǎn)大于普通節(jié)點，簇首內(nèi)部耗能也不均勻，同時耗能最多的為AODV協(xié)議中比較重要的節(jié)點。而引入交通層后普通節(jié)點和簇首之間能耗差別減小，簇首內(nèi)部也相對均衡，且分布情況也優(yōu)于AODV路由協(xié)議。

3.2 簇首能耗情況

簇首能耗情況在實際應(yīng)用中尤為關(guān)鍵，本文對每個簇首的能耗進(jìn)行了跟蹤記錄，結(jié)果如圖6所示。

圖6 各個簇首耗能情況仿真圖

仿真數(shù)據(jù)表明，AODV協(xié)議中能耗最多的節(jié)點在本文算法仿真結(jié)果中減少了約95%的通信能耗，其他關(guān)鍵節(jié)點也有較大的減少。少部分節(jié)點對整體能耗有9%左右增加。

3.3 簇首能耗均勻性情況

對比圖6中的仿真結(jié)果可知，在AODV協(xié)議中，簇首之間的能耗隨著時間增加而呈現(xiàn)發(fā)散關(guān)系，簇首之間耗能也極為不均，關(guān)鍵節(jié)點耗能過大。在100輪后，簇首通信能耗的最高和最低值相差10倍。這是AODV協(xié)議設(shè)計所決定的必然現(xiàn)象，離基站較近簇首的能耗遠(yuǎn)大于離基站較遠(yuǎn)簇首的能耗，并且兩者隨著時間的增加而差距越來越大，使得能耗高的簇首壽命大大降低。

在引入交通層拓?fù)涞膬?yōu)化算法中，簇首只需負(fù)責(zé)收集簇內(nèi)節(jié)點信息與交通層通信，節(jié)省了AODV算法自適應(yīng)的通信能耗。距離基站的遠(yuǎn)近對簇首能耗情況不再有影響，能耗均勻性相對AODV協(xié)議有了很大程度上的提高。仿真結(jié)果顯示，簇首之間能耗雖然略有差距，但在100輪內(nèi)，已無明顯的發(fā)散現(xiàn)象，發(fā)現(xiàn)簇首之間能耗幾乎相等，均勻性十分理想。

3.4 簇首壽命情況

引入交通層的優(yōu)化協(xié)議相對于AODV協(xié)議，簇首提高1～3倍的壽命。在AODV協(xié)議中能耗越高的節(jié)點，其在引入交通層之后壽命提高得越多。

4 結(jié)論與探討

本文研究通過引入交通層對AODV自適應(yīng)算法進(jìn)行優(yōu)化，利用GA算法完成簇首與交通層的復(fù)雜拓?fù)涞膶崟r設(shè)計，發(fā)現(xiàn)對完全自適應(yīng)的整體加入復(fù)雜實時的固定的優(yōu)化因素，會將其整體性能向所期望的優(yōu)化方向轉(zhuǎn)化。本文所研究的新型WSN拓?fù)浣Y(jié)構(gòu)以及根據(jù)能耗與距離因素的分配方法有效提升了WSN總體壽命，減少了大部分WSN簇首的能耗(往往這些簇首處于比較關(guān)鍵的位置)，對WSN的性能進(jìn)行了很大的提升。而本文的優(yōu)化設(shè)計不足在于新節(jié)點的引入增加了WSN的整體的一定能耗，也使WSN之間的協(xié)議關(guān)系相對比較復(fù)雜。所以在不引入新的節(jié)點的情況下，對WSN整體性能進(jìn)行優(yōu)化是一個非常有價值的命題，討論也更加的復(fù)雜而有意義。

本文的研究工作得到了成都市科技局項目(2014-HM01-00122-SF)的資助，在此表示感謝！

[1] HESHAM A, YANG S H. Dynamic cluster head for lifetime efficiency in WSN[J]. International Journal of Automation and Computing, 2009, 6(1): 48-54.

[2] YOUNIS O, FAHMY S. Distributed clustering in Ad-hoc sensor networks: a hybrd, energy-efficient approach[C]// Proc 13th Joint Conf on IEEE Computer and Communications Societies. [S.l.]: IEEE Computer and Communications Societies, 2004.

[3] 李劍, 景博. 自適應(yīng)遺傳算法在多邊議題協(xié)商中的應(yīng)用[J]. 北京郵電大學(xué)學(xué)報, 2008, 31(6): 67-70.

LI Jian, JING Bo. Adaptive genetic algorithm and its application in multi-lateral multi-issue negotiation[J]. Journal of Beijing University of Posts and Telecommunications, 2008, 31(6): 67-70.

[4] SHARMA R, LOBIYAL D K. Proficiency analysis of AODV, DSR and TORA Ad-hoc routing protocols for energy holes problem in wireless sensor networks[J]. Procedia Computer Science, 2015, 57: 1057-1066.

[5] 饒皓, 袁健. 基于節(jié)點生存時間的WSN節(jié)能路由算法[J].計算機(jī)工程, 2012, 38(10): 99-101.

RAO Hao, YUAN Jian. Energy efficient routing algorithm in WSN based on node survival time[J]. Computer Engineering, 2012, 38(10): 99-101.

[6] 雷霖, 李偉峰, 王厚軍. 基于遺傳算法的無線傳感器網(wǎng)絡(luò)路徑優(yōu)化[J]. 電子科技大學(xué)學(xué)報, 2009, 38(2): 227-230.

LEI Lin, LI Wei-feng, WANG Hou-jun. Path optimization of wireless sensor network based on genetic algorithm[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(2): 227-230.

[7] 呂林濤, 范永林. 能量均衡的WSN非均勻分簇路由算法[J]. 計算機(jī)工程, 2009, 35(21): 117-119.

Lü Lin-tao, FAN Yong-lin. Energy-balanced WSN uneven clustering zouting algorithm[J]. Computer Engineering, 2009, 35(21): 117-119.

[8] 楊挺, 孫雨耕, 楊郁, 等. 無線傳感器網(wǎng)絡(luò)中一種節(jié)省資源的快速重路由算法[J]. 傳感技術(shù)學(xué)報, 2005, 18(3): 445-448.

YANG Ting, SUN Yu-geng, YANG Yu, et al. A resourceefficient fast rerouting for wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2005, 18(3): 445-448.

[9] YI Y K, KIM H. Agent-based geometry optimization with genetic algorithm (GA) for tall apartment’s solar right[J]. Solar Energy, 2015, 113: 236-250.

[10] 陳擁軍, 袁慎芳. 無線傳感器網(wǎng)絡(luò)最小能耗拓?fù)淇刂蒲芯縖J]. 電子科技大學(xué)學(xué)報, 2012, 41(4): 568-573.

CHEN Yong-jun, YUAN Shen-fang. Minimum energy consumption topology control for wireless sensor networks [J]. Journal of University of Electronic Science and Technology of China. 2012, 41(4): 568-573.

[11] MEDAGLIANI P, MARTALò M, FERRARI G. Clustered zigbee networks with data fusion: characterization and performance analysis[J]. Ad Hoc Networks, 2011, 9: 1083-1103.

[12] 王瑞錦, 秦志光, 王佳昊.. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議分析[J]. 電子科技大學(xué)學(xué)報, 2013, 42(3): 400-405.

WANG Rui-jin, QIN Zhi-guang, WANG Jia-hao. Analysis of wireless sensor network cluter routing protocol[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 400-405.

編 輯 漆 蓉

Path Optimization Method in Transportation Layer of WSN Based on Genetic Algorithm and LEACH

LI Yu-xia1,2, XU Yong-xin3, HE Lei4, and ZHANG Xiang-xiu3

(1. School of Automation Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. Key Laboratory of Geoscience Spatial Information Technology of Ministry of Land and Resources, Chengdu University of Technology Chengdu 610059; 3. School of Optoelectronic Information, University of Electronic Science and Technology of China Chengdu 610054. 4. College of Software Engineering, Chengdu University of Information Technology Chengdu 610225)

To solve the problems of unbalanced energy consumption and the high energy consumption of header cluster effectively in the wireless sensor networks (WSN), the paper proposes an optimized transportation layer algorithm which is based on the genetic algorithm (GA), low energy adaptive clustering hierarchy (LEACH) algorithm, and ZigBee protocol. The algorithm introduces a new type of topological structure and improves the threshold function based on distance and energy consumption for WSN. The simulation results show that the proposed algorithm can achieve a 95% reduction of communication energy consumption of key cluster head with 9% increase of overall energy consumption, thus effectively improving the uniformity of the energy consumption of WSN, and extending 1～3 times working life of the whole WSN.

genetic algorithm; transportation layer; wireless sensor networks (WSN); ZigBee protocol

TP274.1

A

10.3969/j.issn.1001-0548.2017.03.012

2016 ? 03 ? 16；

2016 ? 12 ? 06

國家自然科學(xué)基金(60841006, 4157133)；國土資源部地學(xué)空間信息技術(shù)重點實驗室開放基金(KLGSIT2016-08)

李玉霞(1979 ? )，女，副教授，主要從事定量遙感及其應(yīng)用、無人機(jī)圖像處理、空間信息提取等方面的研究.