,, ,

(1.湖北大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，武漢 430062； 2.北京理工大學(xué) 信息與電子學(xué)院，北京 100081)

0 引言

無線傳感器網(wǎng)絡(luò)[1]由大量隨機(jī)部署在空間中的傳感器節(jié)點(diǎn)組成，主要廣泛的應(yīng)用在工程領(lǐng)域[2]中，如：海洋環(huán)境探測(cè)、森林火災(zāi)監(jiān)控、空氣污染監(jiān)控等。由于節(jié)點(diǎn)的能量和通信范圍有限，所以引入移動(dòng)Sink[3]對(duì)簇頭數(shù)據(jù)進(jìn)行收集[4]，減少簇內(nèi)的通信成本，從而延長了無線傳感器網(wǎng)絡(luò)的使用生存周期[5]。LEACH[6]是流行的分層路由協(xié)議之一，該協(xié)議主要以形成集群和選擇簇頭來減少簇內(nèi)節(jié)點(diǎn)的能量消耗。路由協(xié)議設(shè)計(jì)的宗旨是最大限度地降低能耗和延長使用壽命[7]。在實(shí)際設(shè)計(jì)中，傳統(tǒng)LEACH協(xié)議是簇頭收集的數(shù)據(jù)融合直接發(fā)送給基站，而修改后的LEACH協(xié)議是簇頭將收集的數(shù)據(jù)發(fā)送給MS，MS運(yùn)行一個(gè)周期將所有的數(shù)據(jù)發(fā)送給基站。

Mottaghi等[8]提出了基于sink節(jié)點(diǎn)與集合節(jié)點(diǎn)優(yōu)化的LEACH算法，該算法建立一條寬為ω的虛擬路徑，sink節(jié)點(diǎn)只能在此區(qū)域來回移動(dòng)，然而只有部分簇頭與sink通信的距離減少，并沒有解決所有的簇頭與sink的通信距離。林志貴等[9]在WSN中結(jié)合sink節(jié)點(diǎn)延長無線傳感器網(wǎng)絡(luò)的生命周期，提出了移動(dòng)中繼的WSN節(jié)能移動(dòng)路由算法，可以避免因局部突發(fā)事件造成網(wǎng)絡(luò)過早失效；該算法在網(wǎng)絡(luò)運(yùn)行中普通節(jié)點(diǎn)需要判斷是否將數(shù)據(jù)直接傳給sink還是發(fā)送給簇頭，節(jié)點(diǎn)需要與簇頭和sink多次通信，才能將數(shù)據(jù)傳送出去。劉林鋒等[11]在改進(jìn)傳統(tǒng)的LEACH協(xié)議算法中引入sink收集數(shù)據(jù)，采用蟻群算法搜尋移動(dòng)sink的最優(yōu)路徑。但是蟻群算法在路徑規(guī)劃時(shí)容易陷入局部最優(yōu)，導(dǎo)致路徑規(guī)劃并不是最優(yōu)路徑。盧先領(lǐng)[12]等提出了時(shí)延受限的移動(dòng)sink數(shù)據(jù)收集算法，該算法通過時(shí)延限制了sink的移動(dòng)速度和移動(dòng)軌跡，該算法固定了MS的運(yùn)動(dòng)軌跡，但未固定簇頭，當(dāng)簇頭被重新選取，MS收集數(shù)據(jù)的路徑并不是最優(yōu)。

上述文獻(xiàn)都考慮了簇頭將數(shù)據(jù)發(fā)送給MS，然而并沒有真正解決簇頭與MS通信成本達(dá)到最小，本文提出了基于LEACH算法引入MS收集簇的數(shù)據(jù)，并與蟻群遺傳算法(ACGA)相結(jié)合獲得MS移動(dòng)最短路徑并與簇頭近距離通信，以解決簇頭能量消耗過快、數(shù)據(jù)傳輸比率低、網(wǎng)絡(luò)生命周期短的問題，通過實(shí)驗(yàn)數(shù)據(jù)分析WSNs能量利用率提高了50%、數(shù)據(jù)傳輸比率提高到24.5%、網(wǎng)絡(luò)生命周期提高了60%。

1 無線傳感器網(wǎng)絡(luò)數(shù)據(jù)模型

1.1 LEACH算法分析

LEACH[6]算法以循環(huán)隨機(jī)的方式選取簇頭節(jié)點(diǎn)并采用單跳路由的方式通信，如果某個(gè)節(jié)點(diǎn)的隨機(jī)數(shù)小于閾值,則該節(jié)點(diǎn)成為簇頭。[6]的計(jì)算公式如下為：

(1)

p是網(wǎng)絡(luò)中簇頭所占的百分比，r為當(dāng)所運(yùn)行的選舉輪數(shù)；G是最近1/p輪不是簇頭的節(jié)點(diǎn)集。

節(jié)點(diǎn)的通信過程如圖1所示。

圖1 簇頭與節(jié)點(diǎn)間的通信

節(jié)點(diǎn)收發(fā)送數(shù)據(jù)的能耗[11 ]模型如下：

ETX=mEelec+mεdχ

(2)

簇頭接收簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)時(shí)能量消耗如下：

ERX=wmEelec

(3)

簇頭一個(gè)周期內(nèi)消耗的能耗為：

Qk(t)=wEDA(t)+wERX(t)

(4)

1.2 WSN中MS的訪問路徑規(guī)劃模型

在呈現(xiàn)路徑規(guī)劃之前，我們應(yīng)該考慮WSN模型；在一個(gè)惡劣的環(huán)境中隨機(jī)部署N個(gè)初始能量為的節(jié)點(diǎn)，并且部署之后靜止不動(dòng)(MS不用考慮)。同時(shí)，MS通過廣播告知每一個(gè)節(jié)點(diǎn)，通過每一個(gè)節(jié)點(diǎn)返回的消息，MS確定每一個(gè)簇頭的位置并路徑規(guī)劃，可以確定最佳的移動(dòng)路徑。在此采集信息過程中，當(dāng)存活節(jié)點(diǎn)的個(gè)數(shù)低于總數(shù)的15%，則宣布WSNs生命周期結(jié)束。

為了盡可能的使WSNs生命周期變長，MS的速度和路徑對(duì)網(wǎng)絡(luò)生命周期有很大的影響。當(dāng)確定了最佳路徑后，MS將以最佳的速度去接收每一個(gè)簇頭的數(shù)據(jù)。假設(shè)在一片區(qū)域內(nèi)隨機(jī)部署了N=30個(gè)節(jié)點(diǎn)如圖2所示，從形成簇的結(jié)構(gòu)來看，可以將其分成為6個(gè)相等的區(qū)域，每一個(gè)單獨(dú)區(qū)域就是一個(gè)簇，通過隨機(jī)部署每一個(gè)簇的普通節(jié)點(diǎn)數(shù)都不一樣，在此通過LEACH協(xié)議選取的簇頭，簇頭將傳送自己的信息可以確定每一個(gè)簇頭的位置，從而可以確定最佳的移動(dòng)路徑，達(dá)到最小的能量消耗。

圖2 sink移動(dòng)軌跡

在此場(chǎng)景中，將呈現(xiàn)出最佳的路徑算法和花費(fèi)最短的時(shí)間收集數(shù)據(jù)，引入最短時(shí)間周期進(jìn)行如下證明：

(5)

為了有效的收集數(shù)據(jù)，當(dāng)普通節(jié)點(diǎn)收集到的數(shù)據(jù)采用TDMA傳送到簇頭，為了防止簇頭收集到的數(shù)據(jù)溢出而導(dǎo)致數(shù)據(jù)丟失，應(yīng)及時(shí)將數(shù)據(jù)傳送給MS，每一個(gè)周期ξ由每一個(gè)簇頭傳送數(shù)據(jù)的時(shí)間和移動(dòng)sink移動(dòng)σ決定的。則如下為：

(6)

如果簇內(nèi)有w個(gè)普通節(jié)點(diǎn)，每一個(gè)普通節(jié)點(diǎn)傳輸m bit消息。傳輸?shù)男畔⒌乃俾蕿镽，則移動(dòng)sink收集簇頭內(nèi)的信息所需要的時(shí)間如下為：

(7)

當(dāng)確定最佳路徑之后，MS以為最佳路徑運(yùn)行，此時(shí)，MS的速度為v，則移動(dòng)的時(shí)間如下為：

(8)

每一次收集數(shù)據(jù)的一個(gè)周期為是由MS移動(dòng)的路徑和采集簇頭數(shù)據(jù)的時(shí)間決定。

2 基于蟻群遺傳算法的路徑規(guī)劃

2.1 蟻群算法的改進(jìn)

蟻群算法[12]與其他優(yōu)化算法都有自己的局限性，容易陷入到局部的最優(yōu)解，通過引入遺傳算法[13]的選擇、變異和交叉算子，改變蟻群算法易陷入局部解后不再更新路徑，并增加了算法的多樣性，避免了算法過早結(jié)束而未達(dá)到最優(yōu)解。所謂的交叉算子是根據(jù)生物學(xué)中的兩個(gè)父代個(gè)體的部分染色體交叉互換產(chǎn)生新的染色體傳遞給下一代，并通過交叉分析產(chǎn)生新的有益基因。

蟻群算法中的每一只螞蟻個(gè)體都具有良好的粒子性，將其轉(zhuǎn)化為粒子群算法的思維：所有的粒子都由一個(gè)優(yōu)化的函數(shù)來決定適應(yīng)函數(shù)值。而每一個(gè)粒子的速度可以改變粒子的方向和決定他們行駛的距離，此時(shí)粒子將會(huì)在空間內(nèi)搜尋最優(yōu)解，通過每一次的迭代，粒子通過跟蹤兩個(gè)極值用來更新自己的位置，兩個(gè)極值分別是個(gè)體極值pbest,另外一個(gè)是整個(gè)種群的最優(yōu)極值gbest。按照遺傳算法的交叉變異操作如下：

vk+1=c0vk+c1r1(pbestk-xk)+

c2r2(gbestk-xk)

(9)

式中，c0vk項(xiàng)可以作為遺傳算法的變異操作，c1r1(pbestk-xk)項(xiàng)轉(zhuǎn)化為遺傳的交叉操作，c2r2(gbestk-xk)項(xiàng)轉(zhuǎn)化為遺傳的選擇操作；每一次的都可以讓螞蟻的當(dāng)前解與個(gè)體最優(yōu)解和全局最優(yōu)解進(jìn)行交叉運(yùn)算，同時(shí)解出新的最優(yōu)解，最后通過新的最優(yōu)解計(jì)算出最短距離。

2.2 蟻群遺傳算法實(shí)現(xiàn)

當(dāng)簇頭選取之后，確定簇頭的位置，并尋找最佳路徑收集數(shù)據(jù)，假設(shè)MS是一只螞蟻，從而選取一個(gè)簇頭的位置進(jìn)行開始，通過蟻群算法的“隨機(jī)比例規(guī)則”選擇下一個(gè)簇頭。則MS轉(zhuǎn)移概率Pij(t)為：

(10)

通過MS在每一條路徑上留下的信息素濃度，由信息素濃度的強(qiáng)度選擇下一個(gè)簇頭，此時(shí)可以在求解最短路徑時(shí)產(chǎn)生m個(gè)初始解。設(shè)其中經(jīng)過的路徑(i,j)的初始解有s個(gè)，每一個(gè)路徑長度為L1,L2,...LK然而路徑上的初始信息量如下為：

(11)

當(dāng)每一個(gè)MS走完一步或者完成一次循環(huán)，要對(duì)殘留的信息進(jìn)行更新處理，每次迭代完成后，各路徑上的信息素都需要更新，其公式如下:

(12)

m只螞蟻獲得的所有路徑中當(dāng)前路徑的長度已經(jīng)小于上一次迭代路徑長度的最短距離時(shí)，則終止本次尋找最短路徑，此時(shí)所獲得的路徑為最短路徑。

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

通過Matlab對(duì)LEACH協(xié)議中加入MS，與原有的LEACH協(xié)議對(duì)比能量消耗、數(shù)據(jù)傳輸和網(wǎng)絡(luò)壽命等；改變?cè)泄潭ú蛔兊幕?，從而使用MS收集數(shù)據(jù)傳給基站和采用的ACGA算法對(duì)MS的路徑進(jìn)行規(guī)劃。簇頭的能量消耗減少以至于增加WSNs網(wǎng)絡(luò)生命周期。將300個(gè)節(jié)點(diǎn)隨機(jī)部署在400 m*400 m的正方形內(nèi)，BS的坐標(biāo)為(0,0)。主要分析WSNs能量消耗、網(wǎng)絡(luò)壽命和數(shù)據(jù)傳輸。WSNs主要參數(shù)如表1所示：

表1 網(wǎng)絡(luò)仿真參數(shù)

通過實(shí)驗(yàn)對(duì)比分析，與沒有MS進(jìn)行轉(zhuǎn)接數(shù)據(jù)相比，提高了無線傳感器的數(shù)據(jù)傳輸，并增加了簇頭的選取。從而增加的WSNs生命周期和能量利用率。圖3展現(xiàn)了使用MS加大了數(shù)據(jù)的傳輸量，當(dāng)傳輸率增加時(shí)，節(jié)點(diǎn)傳輸完數(shù)據(jù)后提前進(jìn)入休眠狀態(tài)并減小能量的損耗；圖4對(duì)比原有的LEACH協(xié)議生命周期，LEACH協(xié)議80%的節(jié)點(diǎn)死亡接近1 500輪，而本文采用的算法80%的節(jié)點(diǎn)死亡接近3 700輪，通過實(shí)驗(yàn)對(duì)比，整個(gè)網(wǎng)絡(luò)周期平均提高了60%。圖5顯示了加入MS之后提升了數(shù)據(jù)傳輸率的同時(shí)網(wǎng)絡(luò)能量消耗減小，最終能量利用率也提高；從圖6看出LEACH算法工作輪數(shù)在1 600所有的節(jié)點(diǎn)死亡，加入MS之后工作輪數(shù)在3 800所有的節(jié)點(diǎn)死亡?？傮w來看根據(jù)引入MS提高了節(jié)點(diǎn)能量的利用率和延長的網(wǎng)絡(luò)生命周期。

圖3 數(shù)據(jù)傳輸對(duì)比 圖4 死亡節(jié)點(diǎn)數(shù)對(duì)比

圖5 網(wǎng)絡(luò)能量消耗對(duì)比 圖6 剩余能量對(duì)比

在仿真中，采用路徑規(guī)劃分析MS移動(dòng)的是否路徑最短。通過實(shí)驗(yàn)比較三種算法進(jìn)行最佳的移動(dòng)軌跡；為了證明MS軌跡，將采用了100/150/200/250/300個(gè)節(jié)點(diǎn)部署進(jìn)行分析，根據(jù)協(xié)議選取簇頭確定路徑，并采用蟻群算法、遺傳算法、蟻群遺傳算法進(jìn)行分析，由于簇頭選取占節(jié)點(diǎn)的10%，選取α=1，β=5，信息素增加強(qiáng)度系數(shù)Q=100，信息揮發(fā)系數(shù)ρ=0.95，螞蟻個(gè)數(shù)為50，最大運(yùn)行次數(shù)為1 000，并在同一臺(tái)機(jī)器上、各參數(shù)設(shè)置同等的情況下進(jìn)行計(jì)算比較。圖7顯示了3個(gè)算法進(jìn)行路徑規(guī)劃時(shí)最短距離的比較，從圖中可以看出節(jié)點(diǎn)數(shù)相對(duì)較少時(shí)路徑規(guī)劃沒有明顯的優(yōu)勢(shì)，當(dāng)達(dá)到較多的節(jié)點(diǎn)部署時(shí)，則路徑規(guī)劃明顯顯現(xiàn)出來，并帶入公式(8)可以證明MS移動(dòng)使用的時(shí)間最短，然而每一個(gè)簇頭傳送數(shù)據(jù)采用的TDMA的時(shí)間間隔相同,LEACH-sink總收集數(shù)據(jù)的時(shí)間低于原有的算法，則公式(7)被證明，最終可以證明公式(5)在此應(yīng)用中成立。圖8為LEACH協(xié)議與引入MS之后同一節(jié)點(diǎn)數(shù)進(jìn)行對(duì)比，網(wǎng)絡(luò)壽命比原有的LEACH算法的網(wǎng)絡(luò)生命增大了很多，可以看出MS在此過程減小了WSNs能量消耗。通過實(shí)驗(yàn)對(duì)路徑綜合進(jìn)行比較，產(chǎn)生最短距離的算法為ACGA算法，可見在蟻群算法中融入遺傳算法可以更好的選擇路徑。同時(shí)收集數(shù)據(jù)時(shí)可以減少簇頭等待sink時(shí)間過長.達(dá)到時(shí)間最小化。

圖7 最短路徑對(duì)比 圖8 網(wǎng)絡(luò)生命對(duì)比

為了證明系統(tǒng)具有良好的穩(wěn)健性，需要討論所有節(jié)點(diǎn)的覆蓋均勻程度，然而簇中的節(jié)點(diǎn)數(shù)不同會(huì)導(dǎo)致不同簇之間數(shù)據(jù)的容量不同和簇的生存周期，因此簇的負(fù)載平衡程度也是衡量整個(gè)系統(tǒng)的重要標(biāo)準(zhǔn)之一，負(fù)載平衡因子的計(jì)算如下：

(13)

由負(fù)載平衡因子公式比較改進(jìn)后的算法負(fù)載均衡度明顯比原有的好，而且基本處于穩(wěn)定如圖9。再次對(duì)系統(tǒng)多次進(jìn)行實(shí)驗(yàn)并分析穩(wěn)健性，隨機(jī)提取10次WSN生命周期進(jìn)行分析如圖10，可以看出此數(shù)據(jù)的平均值為3 355、極差為47、標(biāo)準(zhǔn)方差為14.57，最大的生命周期與最小的生命周期沒超過5%，可以推論系統(tǒng)具有良好的穩(wěn)定性。

圖9 負(fù)載均衡度 圖10 系統(tǒng)的穩(wěn)健性

4 結(jié)論

本文主要針對(duì)無線傳感器網(wǎng)絡(luò)延長生命周期進(jìn)行研究，采

用LEACH分層協(xié)議引入MS收集簇頭的數(shù)據(jù)減少簇頭通信距離。在MS運(yùn)動(dòng)軌跡中提出了ACGA算法，加快了數(shù)據(jù)的收集和提高了能量利用率。同時(shí)本文優(yōu)化了蟻群算法并結(jié)合了蟻群粒子化經(jīng)過遺傳算法產(chǎn)生新的算法，提高了蟻群算法的全局搜索能力，彌補(bǔ)了蟻群算法陷入局部最優(yōu)化。減少了簇內(nèi)成員的通信開銷，提升了網(wǎng)絡(luò)的生命周期。本文的不足沒考慮MS移動(dòng)的動(dòng)態(tài)速度。后期將對(duì)無線傳感器MS移動(dòng)速度結(jié)合數(shù)據(jù)壓縮解決能耗問題，并減少數(shù)據(jù)傳輸和提高網(wǎng)絡(luò)生命周期。

[1] Jennifer Y, Biswanath M, Dipak G.Wirelesssensor network survey[J].Computer Networks,2008,2292-2330.

[2] KuAakowskihg P, Calle E, &Marzo J L. Performance study of wireless sensor and actuatornetworks in forest fire scenarios[J]. International Journal of Communication Systems, 2013,26(4), 515-529.

[3] Hoc Thai Nguyen, Linh Van Nguyen, and HaiXuan Le. Efficient Approach for Maximi-zing Lifespan in Wireless Sensor Networks by Using Mobile Sinks[J]. ETRI Journal,2017.

[4] Ilkyu Ha 1,MamurjonDjuraev, ByoungchulAhn. An Optimal Data Gathering Method for Mobile Sinks in WSNs[J].Wireless PersCommun (2017) 97:1401-1417.

[5] Bhattacharya I,Ghosh S ,Kundu S. Maximizing lifetime of Wireless Sensor Network through extended LEACH Algorithm[M].Advances in Computer Science and Information Technology. Computer Science and Information Technology. 2012：377-386.

[6] 王振興，熊偉麗，徐保國.基于LEACH的簇樹網(wǎng)絡(luò)路由算法研究[J].計(jì)算機(jī)測(cè)量與控制，2008,16(11)：1735-1737.

[7] Soua R, Minet P. A survey on energy efficient techniques in wireless sensor networks[A]. In:IEEE Conference on Wireless and Mobile Networking[C]. 2011,12:1-9.

[8] Mottaghi S,Zahabi M R. Optimizing LEACH clustering algorithm with mobile sink and rendezvous nodes[J]．AEU International Journal of Electronics and Communications，2015,69 (2):507-514.

[9] 林志貴，張 煒，孫有為，等．帶移動(dòng)中繼的WSN移動(dòng)路由算法[J] ．西北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015,45(5)：727-732.

[10] 劉林鋒,郭 平,趙 娟,等.無線傳感器網(wǎng)絡(luò)中一種基于改進(jìn)的LEACH協(xié)議的數(shù)據(jù)收集方案[J].計(jì)算機(jī)科學(xué)，2015,42(6A)299-302.

[11] 盧先領(lǐng)，王瑩瑩．時(shí)延受限的移動(dòng)sink數(shù)據(jù)收集算法[J]．通信學(xué)報(bào),2014，35(10)： 107-116．

[12] TarunpreetBhatia,SimmiKansal, ShivaniGoel , A.K. Verma . A genetic algorithm based distance-aware routing protocol for wireless sensor networks[J]. ComputersandElectricalEngineering,2016:441-445.

[13] Liu J H, Yang J G, Liu H P, et al. improved ant colony algorithm for robot path planning[J].MethodologiesandApplication,2017,21(19):5829-5839.