,, ,

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

0 引言

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

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

上述文獻都考慮了簇頭將數(shù)據(jù)發(fā)送給MS，然而并沒有真正解決簇頭與MS通信成本達到最小，本文提出了基于LEACH算法引入MS收集簇的數(shù)據(jù)，并與蟻群遺傳算法(ACGA)相結(jié)合獲得MS移動最短路徑并與簇頭近距離通信，以解決簇頭能量消耗過快、數(shù)據(jù)傳輸比率低、網(wǎng)絡(luò)生命周期短的問題，通過實驗數(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)隨機的方式選取簇頭節(jié)點并采用單跳路由的方式通信，如果某個節(jié)點的隨機數(shù)小于閾值,則該節(jié)點成為簇頭。[6]的計算公式如下為：

(1)

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

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

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

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

ETX=mEelec+mεdχ

(2)

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

ERX=wmEelec

(3)

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

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

(4)

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

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

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

圖2 sink移動軌跡

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

(5)

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

(6)

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

(7)

當確定最佳路徑之后，MS以為最佳路徑運行，此時，MS的速度為v，則移動的時間如下為：

(8)

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

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

2.1 蟻群算法的改進

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

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

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

c2r2(gbestk-xk)

(9)

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

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

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

(10)

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

(11)

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

(12)

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

3 仿真實驗分析

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

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

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

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

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

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

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

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

(13)

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

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

4 結(jié)論

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

用LEACH分層協(xié)議引入MS收集簇頭的數(shù)據(jù)減少簇頭通信距離。在MS運動軌跡中提出了ACGA算法，加快了數(shù)據(jù)的收集和提高了能量利用率。同時本文優(yōu)化了蟻群算法并結(jié)合了蟻群粒子化經(jīng)過遺傳算法產(chǎn)生新的算法，提高了蟻群算法的全局搜索能力，彌補了蟻群算法陷入局部最優(yōu)化。減少了簇內(nèi)成員的通信開銷，提升了網(wǎng)絡(luò)的生命周期。本文的不足沒考慮MS移動的動態(tài)速度。后期將對無線傳感器MS移動速度結(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].計算機測量與控制，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] 林志貴，張 煒，孫有為，等．帶移動中繼的WSN移動路由算法[J] ．西北大學學報(自然科學版)，2015,45(5)：727-732.

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

[11] 盧先領(lǐng)，王瑩瑩．時延受限的移動sink數(shù)據(jù)收集算法[J]．通信學報,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.