張玉蘭　郭曉惠

【摘 要】針對無線傳感器網(wǎng)絡(luò)中能量消耗不均引起的熱區(qū)問題，提出一種基于移動(dòng)sink節(jié)點(diǎn)的WSN節(jié)能路由協(xié)議MSERP，將整個(gè)網(wǎng)絡(luò)分成若干個(gè)虛擬網(wǎng)格，根據(jù)節(jié)點(diǎn)剩余能量和到網(wǎng)格重心距離選舉簇頭。通過PSO算法來確定sink的下一個(gè)移動(dòng)位置，粒子適應(yīng)值函數(shù)由簇頭到sink節(jié)點(diǎn)的距離和sink節(jié)點(diǎn)周圍簇頭能量因素定義。仿真結(jié)果表明，該協(xié)議有效地解決了熱區(qū)問題，提高了網(wǎng)絡(luò)的生存周期。

【關(guān)鍵詞】無線傳感器網(wǎng)絡(luò)；熱區(qū)問題；移動(dòng)sink節(jié)點(diǎn)；PSO算法

中圖分類號(hào)： TP212.9 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2017）26-0010-002

Based on the Mobile Sink Node of WSN Energy-efficient Routing Protocol

ZHANG Yu-lan GUO Xiao-hui

（School of Computer Engineering，Chongqing College of Humanities， Science & Technology， Chongqing 401524， China）

【Abstract】WSN energy-efficient routing protocol based on a mobile sink node of （MSERP） was proposed in this paper. The whole network was divided into some virtual unit，which choose cluster heads according to the residual energy and the distance of a node and a virtual unit of center. The next stay the best location of the sink is determined by PSO algorithm. The definition of the fitness function of particle is based on two factors： the distance of cluster heads to sink and the energy of cluster heads around the sink. Simulation results demonstrate that the protocol can efficiently solve the hot spot problem and prolong the network lifetime.

【Key words】Wireless Sensor Networks （WSN）； Hot spot problem； A mobile sink； PSO algorithm

0 引言

傳統(tǒng)的無線傳感器網(wǎng)絡(luò)分簇算法，sink保持靜止，距離sink越近的節(jié)點(diǎn)由于需要轉(zhuǎn)發(fā)更多的數(shù)據(jù)而過早死亡，容易出現(xiàn)“熱區(qū)”問題。分簇算法中較為典型的有LEACH、HEED、PEGASIS等。為了解決“熱區(qū)”問題，延長網(wǎng)絡(luò)生存周期，提出了一系列策略，如非均勻分簇路由協(xié)議[1]。然而，由于sink節(jié)點(diǎn)保持靜止，周圍的節(jié)點(diǎn)沒有改變，不能在根本上解決該問題。針對以上情況。Luo等人[2]提出了引入移動(dòng)的sink節(jié)點(diǎn)，連續(xù)改變sink節(jié)點(diǎn)周圍的節(jié)點(diǎn)避免“熱區(qū)”。根據(jù) sink節(jié)點(diǎn)移動(dòng)路徑的確定性大致可以分為三類：隨機(jī)移動(dòng)策略[3]，sink節(jié)點(diǎn)隨機(jī)選擇下一個(gè)移動(dòng)位置，但sink節(jié)點(diǎn)頻繁的廣播位置信息，導(dǎo)致能量消耗較大；sink節(jié)點(diǎn)按照預(yù)先設(shè)定好的路徑移動(dòng)[4]，雖然降低網(wǎng)絡(luò)的能耗，但不合適大規(guī)模網(wǎng)絡(luò)的應(yīng)用；sink動(dòng)態(tài)選擇移動(dòng)路徑策略[5]，根據(jù)網(wǎng)絡(luò)中的某些參數(shù)決定sink的下一個(gè)移動(dòng)位置，但算法較為復(fù)雜。

本文提出基于移動(dòng)sink節(jié)點(diǎn)的WSN路由協(xié)議（MSERP）解決熱區(qū)問題。本協(xié)議把網(wǎng)絡(luò)劃分為若干個(gè)虛擬單元，通過PSO算法確定sink下一個(gè)移動(dòng)位置，利用sink的移動(dòng)性，從而平衡了網(wǎng)絡(luò)的能耗，延長網(wǎng)絡(luò)生命周期。

1 算法描述

1.1 PSO算法

粒子群優(yōu)化算法是一種基于群智能方法的演化計(jì)算技術(shù)。假設(shè)在D維空間中位置表示為向量第i個(gè)粒子經(jīng)歷過的最佳位置為向量Pi=（pg1，pg2，…，pgd），每個(gè)粒子飛行速度為向量Vi=（vi1，vi1，…vid），i=1，2，…，m，所有粒子經(jīng)歷的最佳位置為Pg=（pg1，pg2，…，pgd），每一代粒子根據(jù)公式（1）更新速度：

vid=wvid+c1r1（pid-xid）+c2r2（pgd-xid）（1）

式中，w為慣性系數(shù)；c1和c2為學(xué)習(xí)因子；r1和r2是[0，1]之間的隨機(jī)數(shù)。

1.2 MSERP算法

將整個(gè)無線傳感器網(wǎng)絡(luò)劃分為有唯一ID編號(hào)的虛擬單元格，即簇。選取區(qū)域的重心坐標(biāo)（Xg，Yg）擔(dān)任每個(gè)虛擬單元格節(jié)點(diǎn)簇頭。 該坐標(biāo)滿足單元格內(nèi)的任意節(jié)點(diǎn)到它的距離之和最小。

簇頭的評(píng)判模型定義為：

f=βf +φf +？酌f ，first round；？鄣f +βf +φf +？酌f ，otherwise.（2）

其中：fe反映能量對節(jié)點(diǎn)擔(dān)任簇頭的重要程度；fd反映了節(jié)點(diǎn)到網(wǎng)格重心的距離對節(jié)點(diǎn)擔(dān)任簇頭的重要程度；參數(shù)fn和fen進(jìn)一步避免網(wǎng)絡(luò)陷入“熱區(qū)”問題。

簇頭選舉具體過程如下：（1）網(wǎng)絡(luò)初始化，完成網(wǎng)絡(luò)的劃分，每個(gè)節(jié)點(diǎn)計(jì)算出所屬的網(wǎng)格號(hào)；（2）根據(jù)（5）完成簇頭的選舉。每個(gè)網(wǎng)格選擇 值最大的節(jié)點(diǎn)擔(dān)任簇頭；（3）每輪完成時(shí)，每個(gè)節(jié)點(diǎn)把剩余能量發(fā)送到簇頭，簇頭根據(jù)（5）選舉下一輪簇頭。endprint

2 sink節(jié)點(diǎn)移動(dòng)過程

網(wǎng)絡(luò)在完成分簇和簇頭的選擇后，各個(gè)簇頭發(fā)送能量信息和所在 編號(hào)到sink節(jié)點(diǎn)。接著判斷是否滿足sink節(jié)點(diǎn)的移動(dòng)條件，若滿足執(zhí)行PSO算法，確定sink節(jié)點(diǎn)的下一位置；若不滿足條件，則sink的位置保持不變。

2.1 sink節(jié)點(diǎn)移動(dòng)條件

基于每個(gè)簇頭的能量信息，sink 計(jì)算整個(gè)網(wǎng)絡(luò)所有簇頭的能量平均值。sink節(jié)點(diǎn)移動(dòng)條件：sink節(jié)點(diǎn)周圍簇頭（到sink節(jié)點(diǎn)一跳）的能量低于整個(gè)網(wǎng)絡(luò)平均簇頭的能量。

2.2 sink位置的確定

本文協(xié)議應(yīng)用PSO算法來最優(yōu)化sink節(jié)點(diǎn)位置，提高網(wǎng)絡(luò)的壽命。sink節(jié)點(diǎn)下一位置應(yīng)滿足，所有簇頭到sink節(jié)點(diǎn)的距離之和及方差最??；sink節(jié)點(diǎn)周圍簇頭能量之和最大且方差最小。

sink節(jié)點(diǎn)執(zhí)行PSO 算法確定下一個(gè)停留位置，目標(biāo)函數(shù)定義為：

cost=？鄣1f1+？鄣2f2+？鄣3f3+？鄣4f4（3）

式中：所有簇頭到sink節(jié)點(diǎn)的歐氏距離之和為f1，方差為f2；f3為當(dāng)前所有節(jié)點(diǎn)能量之和除以sink節(jié)點(diǎn)周圍簇頭的能量之和；f4為sink周圍簇頭能量方差；？鄣1+？鄣2+？鄣3+？鄣4=1。最小的函數(shù)值即為sink節(jié)點(diǎn)的下一個(gè)最佳位置。

sink移動(dòng)算法具體步驟：（1）初始化Q個(gè)粒子，每個(gè)粒子代表sink節(jié)點(diǎn)可能的下一個(gè)位置；（2）運(yùn)用式（3）-（7）計(jì)算粒子適應(yīng)值；（3）確定每個(gè)粒子最優(yōu)解和種群的的最優(yōu)解；（4）利用式（1）更新粒子的速度和位置；（5）根據(jù)上一次sink節(jié)點(diǎn)的位置調(diào)整粒子位置；（6）重復(fù)步驟（2）-（5），至最大循環(huán)次數(shù)。

2.3 sink節(jié)點(diǎn)信息發(fā)布

sink節(jié)點(diǎn)移動(dòng)到確定的位置后，發(fā)布它的位置信息到所在單元格的簇頭，然后由該簇頭轉(zhuǎn)發(fā)給其他簇頭。sink節(jié)點(diǎn)位置更新避免了洪泛過程，有效的節(jié)約了能量。穩(wěn)態(tài)階段簇頭首先完成簇內(nèi)數(shù)據(jù)采集、融合的任務(wù)，然后經(jīng)簇間多跳路由傳遞數(shù)據(jù)至sink節(jié)點(diǎn)。

3 能量模型

3.1 無線通信能耗模型

本文采用一階無線通信模型，無線通信模塊具有功率控制能力，能夠以最小的能量將數(shù)據(jù)發(fā)送給希望的接收者。在保證合理信噪比條件下，節(jié)點(diǎn)發(fā)送數(shù)據(jù)能耗如式（4）：

EIx（k，d）=E ×k+E ×k×d d

其中：k為發(fā)送的二進(jìn)制位數(shù)；d為發(fā)送距離；d0位發(fā)送距離門限值；Eelec為射頻能耗系數(shù)；Efs和Eamp為不同信道傳播模型下的功率放大電路能耗系數(shù)。節(jié)點(diǎn)接收數(shù)據(jù)能耗如式（5）：

ERx（k）=Eelec×k（5）

3.2 數(shù)據(jù)融合模型

數(shù)據(jù)融合模型假設(shè)為：簇頭接收每個(gè)節(jié)點(diǎn)發(fā)送的kbit數(shù)據(jù)，無論簇內(nèi)節(jié)點(diǎn)數(shù)目多少，均壓縮為kbit數(shù)據(jù)。數(shù)據(jù)融合的能耗設(shè)定為ED=5nJ/bit。

4 仿真分析

為了驗(yàn)證本文提出的協(xié)議的有效性，利用MATLAB生成了100節(jié)點(diǎn)隨機(jī)部署在100m×100m范圍內(nèi)。仿真中對比了EBRP，DCSR和MSERP三種協(xié)議。

圖1為這3種協(xié)議的節(jié)點(diǎn)死亡對比圖。從該圖中可以看出：MSERP協(xié)議的網(wǎng)絡(luò)壽命長于EBRP和DCSR。EBRP和EBRP協(xié)議在1000輪時(shí)開始出現(xiàn)節(jié)點(diǎn)死亡。而MSERP協(xié)議在1500附近才開始有節(jié)點(diǎn)死亡，說明本協(xié)議的能耗更加均勻。3種協(xié)議在1700輪時(shí)， MSERP協(xié)議節(jié)點(diǎn)死亡分布均勻，而EBRP和DCSR死亡節(jié)點(diǎn)集中，出現(xiàn)了“熱區(qū)”問題。在使用移動(dòng)sink節(jié)點(diǎn)3種策略中，DCSR由于協(xié)議按照固定路徑移動(dòng)，路徑附近節(jié)點(diǎn)死亡較多；EBRP由于隨機(jī)移動(dòng)，路線不夠合理，會(huì)出現(xiàn)部分節(jié)點(diǎn)過早死亡。

5 結(jié)論

本協(xié)議通過對網(wǎng)絡(luò)劃分和簇頭選擇，應(yīng)用PSO算法對sink節(jié)點(diǎn)位置進(jìn)行優(yōu)化，通過一群粒子在解空間中逐代搜索，尋找sink最優(yōu)位置。仿真實(shí)驗(yàn)證明，與EBRP和DCSR協(xié)議相比，該協(xié)議能夠有效均能網(wǎng)絡(luò)能耗，降低節(jié)點(diǎn)死亡速度，從而提高網(wǎng)絡(luò)壽命。

【參考文獻(xiàn)】

[1]黃廷輝，伊凱，崔更申，等.基于非均勻分簇的無線傳感器網(wǎng)絡(luò)分層路由協(xié)議[J].計(jì)算機(jī)應(yīng)用.2016，36（1）：66-71.

[2]Luo J，Huang J P，Joint Mobility and R-outing for Lifetime Elongation in Wir-eless Sensor Networks[C]//Pro-ceedings IEEE information 2005， Miami， FL， United- states. 2005， 3：1735-46.

[3]鐘智，羅大庸，劉少強(qiáng).具有移動(dòng)sink的無線傳感器網(wǎng)絡(luò)能量均衡分簇路由協(xié)議[J].控制與決策.2012，27（8）：1211-1115.

[4]郭劍，孫力娟，許文君.基于移動(dòng)sink的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案[J].通信學(xué)報(bào).2012，33（9）：176-184.

[5]林志貴，王璽，趙可.帶移動(dòng)sink節(jié)點(diǎn)的WSN節(jié)能路由算法[J].計(jì)算機(jī)科學(xué).2014，41（11）：199-203.