莫文杰，鄭 霖

(1.廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))，廣西 桂林 541004；2.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

(*通信作者電子郵箱gwzheng@gmail.com)

優(yōu)化網(wǎng)絡(luò)生命周期和最短化路徑的WSN移動(dòng)sink路徑規(guī)劃算法

莫文杰1,2，鄭 霖1,2*

(1.廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))，廣西 桂林 541004；2.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

(*通信作者電子郵箱gwzheng@gmail.com)

為了緩解無線傳感器網(wǎng)絡(luò)(WSN)中傳感器節(jié)點(diǎn)分布不均勻、傳感器節(jié)點(diǎn)感知數(shù)據(jù)量不同而造成能耗不均衡、“熱區(qū)”等問題，提出一種優(yōu)化網(wǎng)絡(luò)生命周期和最短化路徑的WSN移動(dòng)sink路徑規(guī)劃算法(MSPPA)。首先，通過監(jiān)測區(qū)域網(wǎng)格化，在每個(gè)網(wǎng)格內(nèi)分布若干個(gè)移動(dòng)sink候選訪問站點(diǎn)，sink在每個(gè)網(wǎng)格中選擇一個(gè)站點(diǎn)停留收集網(wǎng)格中節(jié)點(diǎn)數(shù)據(jù)；然后，分析所有傳感器節(jié)點(diǎn)的生命周期與sink站點(diǎn)選擇的關(guān)系，建立權(quán)衡網(wǎng)絡(luò)生命周期和sink移動(dòng)路徑的優(yōu)化模型；最后，使用雙鏈遺傳算法規(guī)劃移動(dòng)sink遍歷網(wǎng)格的順序和選擇每個(gè)網(wǎng)格中移動(dòng)sink訪問站點(diǎn)，得到移動(dòng)sink節(jié)點(diǎn)遍歷所有網(wǎng)格收集數(shù)據(jù)的路徑。仿真結(jié)果顯示，與已有的低功耗自適應(yīng)分簇(LEACH)算法與基于移動(dòng)sink節(jié)點(diǎn)與集合節(jié)點(diǎn)(RN)的優(yōu)化LEACH分簇算法(MS-LEACH-RN)相比，MSPPA在網(wǎng)絡(luò)生命周期方面提高了60%，且具有良好的能耗均衡性。實(shí)驗(yàn)結(jié)果表明，MSPPA能有效緩解能量不均衡、“熱區(qū)”問題，延長網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò)；移動(dòng)sink；數(shù)據(jù)收集；雙鏈遺傳算法；路徑規(guī)劃；網(wǎng)絡(luò)生命周期

0 引言

當(dāng)前，基于移動(dòng)sink節(jié)點(diǎn)的數(shù)據(jù)收集優(yōu)化是無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)研究的關(guān)鍵問題之一[1]。WSN引入移動(dòng)sink節(jié)點(diǎn)不僅可均衡節(jié)點(diǎn)流量負(fù)載，還可以平衡節(jié)點(diǎn)能量消耗，從而可以有效避免“熱區(qū)”問題并延長網(wǎng)絡(luò)的生存時(shí)間[2-3]。但是使用移動(dòng)sink節(jié)點(diǎn)收集數(shù)據(jù)也帶來了新的挑戰(zhàn)：一是sink位置更新問題，頻繁泛洪sink位置信息將過多消耗節(jié)點(diǎn)能量；二是由于sink移動(dòng)，網(wǎng)絡(luò)拓?fù)漕l繁改變，這會(huì)加劇網(wǎng)絡(luò)拓?fù)錁?gòu)建的開銷[4-5]。因此，優(yōu)化基于移動(dòng)sink節(jié)點(diǎn)的路由協(xié)議以及規(guī)劃移動(dòng)sink軌跡的算法受到學(xué)術(shù)和應(yīng)用領(lǐng)域的廣泛關(guān)注。根據(jù)sink移動(dòng)模型，Gu等[6]將基于移動(dòng)sink的路由協(xié)議分成四類：不可控移動(dòng)模型、路徑限制移動(dòng)模型、站點(diǎn)限制移動(dòng)模型和不限制移動(dòng)模型。基于上述四種sink移動(dòng)模型，下面分別介紹國內(nèi)外研究者提出的有關(guān)基于移動(dòng)sink的路由協(xié)議。

不可控移動(dòng)模型是指sink節(jié)點(diǎn)安裝在移動(dòng)單元上(如動(dòng)物)，故其位置、速度和軌跡都未知?；诖四Ｐ?，Lin等[7]提出了基于分簇的分層數(shù)據(jù)傳輸(Hierarchical Cluster-based Data Dissemination, HCDD)協(xié)議，使用K-means算法將網(wǎng)絡(luò)劃分成簇，簇頭處于較高層，負(fù)責(zé)收集簇內(nèi)傳感器節(jié)點(diǎn)數(shù)據(jù)和轉(zhuǎn)發(fā)數(shù)據(jù)。當(dāng)sink駐留在其中一個(gè)簇時(shí)，該簇的簇頭通知其他簇頭sink的位置，各個(gè)簇頭以其他簇頭為中繼節(jié)點(diǎn)多跳將數(shù)據(jù)傳輸?shù)絪ink節(jié)點(diǎn)。Hamida 等[8]提出了基于虛擬線的數(shù)據(jù)傳輸(Line-Based Data Dissemination, LBDD)協(xié)議，該協(xié)議在網(wǎng)絡(luò)中央構(gòu)建一條寬度為w的虛擬線(virtual line)，虛擬線內(nèi)的傳感器節(jié)點(diǎn)負(fù)責(zé)收集和緩存虛擬線外節(jié)點(diǎn)的數(shù)據(jù)，并將sink感興趣的數(shù)據(jù)以多跳方式傳輸給隨機(jī)游走的sink節(jié)點(diǎn)。文獻(xiàn)[7-8]采用了sink節(jié)點(diǎn)不可控移動(dòng)模型，能很好地解決隨機(jī)移動(dòng)sink位置更新問題，但是無論是HCDD協(xié)議的簇頭，還是LBDD協(xié)議的虛擬線內(nèi)節(jié)點(diǎn)，都存在較高的控制開銷與路由開銷，其縮短了網(wǎng)絡(luò)生命周期。

路徑限制模型是指sink節(jié)點(diǎn)被安置在路徑被約束的移動(dòng)單元上(如公交車)?；诖四Ｐ停琈ottaghi等[9]結(jié)合移動(dòng)sink節(jié)點(diǎn)、低功耗自適應(yīng)分簇(Low-Energy Adaptive Clustering Hierarchy, LEACH)算法[10]和集合節(jié)點(diǎn)(Rendezvous Node，RN)，提出一種基于移動(dòng)sink節(jié)點(diǎn)與集合節(jié)點(diǎn)RN的優(yōu)化LEACH分簇算法(optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes, MS-LEACH-RN)。該協(xié)議在網(wǎng)絡(luò)中央構(gòu)建一條寬度為w的虛擬線，移動(dòng)sink在線內(nèi)作往返直線移動(dòng)，然后設(shè)置一個(gè)簇頭到sink節(jié)點(diǎn)的距離閾值d0，當(dāng)簇頭到sink節(jié)點(diǎn)的距離小于d0時(shí)，虛擬線外以LEACH協(xié)議選取的簇頭直接將簇內(nèi)收集到的數(shù)據(jù)發(fā)送到sink節(jié)點(diǎn)，否則，將數(shù)據(jù)發(fā)送到最近的虛擬線內(nèi)RN，最后RN將數(shù)據(jù)傳輸給靠近的移動(dòng)sink節(jié)點(diǎn)。Bhatti等[11]提出一種基于虛擬網(wǎng)格與移動(dòng)sink節(jié)點(diǎn)的動(dòng)態(tài)路由調(diào)整方案，該方案將正方形監(jiān)測區(qū)域劃分成多個(gè)大小一致的網(wǎng)格，sink節(jié)點(diǎn)在正方形區(qū)域外移動(dòng)，網(wǎng)格內(nèi)選取頭節(jié)點(diǎn)負(fù)責(zé)收集網(wǎng)格數(shù)據(jù)，并以其他頭節(jié)點(diǎn)為中繼多跳傳輸給移動(dòng)sink節(jié)點(diǎn)。該方案以維護(hù)sink最新位置的次優(yōu)路由來達(dá)到最小化路由重構(gòu)開銷的目的。梁青等[12]提出基于二分法與移動(dòng) sink 的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議，該協(xié)議將網(wǎng)絡(luò)分為面積相等的兩個(gè)子域，子域交線為移動(dòng)sink的軌跡，隨節(jié)點(diǎn)死亡率的增加，對(duì)子域內(nèi)部進(jìn)行二分，確定并改變移動(dòng)sink的軌跡。移動(dòng)sink與固定 sink并存，簇頭收集簇內(nèi)興趣事件并發(fā)送至距自己跳數(shù)最小的sink。文獻(xiàn)[9，11-12]采用了移動(dòng)sink路徑限制模型，都存在關(guān)鍵性節(jié)點(diǎn)(如文獻(xiàn)[8]的RN與簇頭和文獻(xiàn)[10]的網(wǎng)格頭節(jié)點(diǎn))能耗過大問題，導(dǎo)致其快速死亡。

站點(diǎn)限制移動(dòng)模型是指移動(dòng)sink節(jié)點(diǎn)只能停留在某些固定位置收集數(shù)據(jù)?；诖四Ｐ?，Yun等[13]提出了一種延遲容忍最大化生命周期的單移動(dòng)sink路由協(xié)議。該協(xié)議將網(wǎng)絡(luò)區(qū)域分成多個(gè)子區(qū)域，在每個(gè)子區(qū)域布置一個(gè)固定的sink駐留站點(diǎn)，移動(dòng)sink遍歷所有站點(diǎn)收集數(shù)據(jù)；然后采用線性規(guī)劃(Linear Programming, LP)優(yōu)化移動(dòng)sink每輪駐留在每個(gè)站點(diǎn)的時(shí)間，從而最大化網(wǎng)絡(luò)生命周期。林德鈺等[14]提出移動(dòng)與靜態(tài)sink相結(jié)合的節(jié)能策略，該策略使靜態(tài) sink節(jié)點(diǎn)位于檢測區(qū)域的中心采用單跳傳輸方式收集區(qū)域中心處節(jié)點(diǎn)的數(shù)據(jù)，移動(dòng)sink位于距離靜態(tài)sink節(jié)點(diǎn)一定距離處作快速移動(dòng)，到達(dá)固定站點(diǎn)后停留并采集區(qū)域外圍節(jié)點(diǎn)數(shù)據(jù)。王章權(quán)等[15]提出一種移動(dòng)無線傳感網(wǎng)絡(luò)的sink節(jié)點(diǎn)移動(dòng)路徑選擇算法，在該算法中，sink節(jié)點(diǎn)采用分布式最短路徑樹算法收集傳感節(jié)點(diǎn)的相關(guān)信息和感知數(shù)據(jù)，采用虛擬力理論計(jì)算所有虛擬力的合力， 根據(jù)停留次數(shù)、合力大小和方向等信息計(jì)算當(dāng)前網(wǎng)格中心的停留時(shí)間和下一個(gè)停留網(wǎng)格中心。文獻(xiàn)[13-15]采用站點(diǎn)限制移動(dòng)模型，故其單跳通信傳輸方式使遠(yuǎn)離移動(dòng)sink站點(diǎn)的傳感器節(jié)點(diǎn)能耗較大，易出現(xiàn)“熱區(qū)”現(xiàn)象。

不限制移動(dòng)模型是在不限制sink移動(dòng)路徑與停留站點(diǎn)的情況下規(guī)劃sink移動(dòng)路徑?；诖四Ｐ停琍avithra等[16]基于集合點(diǎn)(Rendezvous Point, RP)提出一種加權(quán)集合規(guī)劃算法，該協(xié)議基于源節(jié)點(diǎn)到固定sink的數(shù)據(jù)轉(zhuǎn)發(fā)路由，計(jì)算每個(gè)傳感器節(jié)點(diǎn)的權(quán)重(其轉(zhuǎn)發(fā)數(shù)據(jù)量與其到固定sink的跳數(shù))動(dòng)態(tài)選擇節(jié)點(diǎn)作為集合點(diǎn)，sink遍歷所有集合點(diǎn)收集數(shù)據(jù)。王薇等[17]提出了一種基于二次柵格劃分的可變長編碼單親遺傳算法的最佳路徑構(gòu)建方法。該算法首先在網(wǎng)絡(luò)區(qū)域中使用粗粒度柵格進(jìn)行劃分，并利用可變長度編碼的單親遺傳算法獲得最佳途經(jīng)柵格，從而構(gòu)造出初始最佳路徑；然后對(duì)于每一個(gè)途經(jīng)柵格再次使用細(xì)粒度柵格進(jìn)行劃分以優(yōu)化收集路徑。于志博等[18]針對(duì)sink移動(dòng)速度限制從而導(dǎo)致時(shí)延較大的問題，提出了時(shí)延約束下的移動(dòng) sink 路徑優(yōu)化策略，根據(jù)時(shí)延和網(wǎng)絡(luò)能耗之間的關(guān)系設(shè)計(jì)了可調(diào)節(jié)的節(jié)點(diǎn)權(quán)重，通過模擬退火遺傳算法得到最優(yōu)節(jié)點(diǎn)權(quán)重，并依據(jù)此權(quán)重通過迭代得到匯聚節(jié)點(diǎn)和最佳移動(dòng)路徑。

許多研究者都考慮到了節(jié)點(diǎn)不均勻分布與 “多對(duì)一”路由負(fù)載不均衡帶來的“熱區(qū)”問題，但大多數(shù)移動(dòng)sink路由協(xié)議都沒有考慮節(jié)點(diǎn)數(shù)據(jù)分布不均勻問題(節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生速率非恒定)。在WSN現(xiàn)實(shí)情況中，節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生速率非恒定也是“熱區(qū)”問題產(chǎn)生的原因之一。而上述文獻(xiàn)中都存在“熱區(qū)”問題，縮短了網(wǎng)絡(luò)生命周期。本文根據(jù)WSN節(jié)點(diǎn)不均勻分布、節(jié)點(diǎn)數(shù)據(jù)分布不均勻以及移動(dòng)sink收集數(shù)據(jù)路徑長短不同等因素，提出了優(yōu)化網(wǎng)絡(luò)生命周期與最短化路徑的WSN移動(dòng)sink路徑規(guī)劃算法MSPPA(Path Planning Algorithm of Mobile Sink)。將網(wǎng)絡(luò)分成多個(gè)網(wǎng)格，在每個(gè)網(wǎng)格中分布多個(gè)候選站點(diǎn)，根據(jù)上述造成“熱區(qū)”問題的因素，建立權(quán)衡網(wǎng)絡(luò)生命周期和sink移動(dòng)路徑的優(yōu)化模型。使用雙鏈遺傳算法對(duì)該優(yōu)化模型進(jìn)行求解，得到移動(dòng)sink節(jié)點(diǎn)遍歷所有網(wǎng)格收集數(shù)據(jù)最優(yōu)路徑。該算法均衡了全網(wǎng)數(shù)據(jù)收集的能耗開銷，顯著緩解了網(wǎng)絡(luò)“熱區(qū)”問題，延長了網(wǎng)絡(luò)生命周期。

1 系統(tǒng)模型

1.1 優(yōu)化目標(biāo)與模型假設(shè)

針對(duì)sink節(jié)點(diǎn)移動(dòng)軌跡可控的無線傳感器網(wǎng)絡(luò)，本文提出的MSPPA綜合考慮了網(wǎng)絡(luò)生命周期和sink節(jié)點(diǎn)移動(dòng)路徑長短兩項(xiàng)指標(biāo)。算法具體包含以下兩個(gè)優(yōu)化目標(biāo)：1)最大化網(wǎng)絡(luò)的生命周期；2)在目標(biāo)1)的基礎(chǔ)上，使sink移動(dòng)距離最短化。

在MSPPA中，假設(shè)：1)所有傳感器節(jié)點(diǎn)隨機(jī)分布在二維的監(jiān)測區(qū)域中，傳感器節(jié)點(diǎn)位置固定不變，但是sink節(jié)點(diǎn)可在監(jiān)測區(qū)域中移動(dòng)并且停留收集數(shù)據(jù)；2)所有傳感器節(jié)點(diǎn)具有相同的性能(如通信半徑、初始能量、能耗模型等)，但節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生速率非恒定，即節(jié)點(diǎn)感知數(shù)據(jù)不均勻；3)所有節(jié)點(diǎn)可安裝全球定位系統(tǒng)(Global Positioning System, GPS)模塊或采用其他定位方法獲知自身的位置坐標(biāo)；4)sink節(jié)點(diǎn)能量不受限制，但是每個(gè)傳感器節(jié)點(diǎn)的能量有限且不能補(bǔ)充。

1.2 優(yōu)化模型

如圖1所示，將監(jiān)測區(qū)域分成G個(gè)大小一致的網(wǎng)格，網(wǎng)格邊長為L(L

圖1 網(wǎng)絡(luò)模型Fig. 1 Network model

本文采用的無線通信能量消耗模型與文獻(xiàn)[20-21]相似，由于只考慮傳感器節(jié)點(diǎn)發(fā)送數(shù)據(jù)到sink節(jié)點(diǎn)的單跳路由，故節(jié)點(diǎn)i單位時(shí)間內(nèi)發(fā)送1 bit數(shù)據(jù)到sink節(jié)點(diǎn)的能耗如下：

(1)

定義節(jié)點(diǎn)生命周期Tnet為其能量耗盡所經(jīng)過的時(shí)間，故節(jié)點(diǎn)i的生存時(shí)間[22-23]為：

(2)

根據(jù)上述分析，本文方法的目的是既要最大化網(wǎng)絡(luò)生命周期，又要最小化sink移動(dòng)路徑長度[24]，故本文提出的優(yōu)化模型可公式化為：

(3)

(4)

(5)

Ti>0,di→ms≥0;i=1,2,…,n

(6)

2 模型求解

本文問題模型中包含移動(dòng)sink站點(diǎn)選址問題與移動(dòng)sink遍歷網(wǎng)格問題(即旅行商問題)，但是無論選址問題，還是TSP，都是NP-hard問題，求解存在困難，故采用雙鏈遺傳算法對(duì)本文模型進(jìn)行求解。

2.1 染色體編碼和解碼

移動(dòng)sink節(jié)點(diǎn)在每個(gè)網(wǎng)格中選取一個(gè)站點(diǎn)停留收集該網(wǎng)格中的傳感器節(jié)點(diǎn)數(shù)據(jù)，并以此遍歷所有網(wǎng)格，采用雙鏈遺傳算法對(duì)此問題進(jìn)行編碼。在此雙鏈染色體編碼中，一條基因鏈包含sink遍歷所有網(wǎng)格的順序，如{3,1,6,4,5,2}，另一條是使用0-1編碼方式標(biāo)記sink節(jié)點(diǎn)在網(wǎng)格中選取的站點(diǎn)，如{010,100,010,001,001,100}，則染色體和子鏈之間的關(guān)系[25]如圖2所示。這兩條子鏈組合成染色體，染色體的每一個(gè)基因由一個(gè)網(wǎng)格和其內(nèi)站點(diǎn)組合而成，代表移動(dòng)sink節(jié)點(diǎn)從網(wǎng)格中選取其中一個(gè)站點(diǎn)停留收集數(shù)據(jù)。子鏈一可得到移動(dòng)sink節(jié)點(diǎn)遍歷所有網(wǎng)格的順序，子鏈二可得到子鏈一對(duì)應(yīng)網(wǎng)格中sink選取的停留站點(diǎn)，這樣，通過對(duì)每個(gè)基因進(jìn)行相應(yīng)的解碼，就可以得到移動(dòng)sink節(jié)點(diǎn)遍歷網(wǎng)格收集數(shù)據(jù)的最優(yōu)路徑。

圖2 子鏈、染色體關(guān)系Fig. 2 Relationship between sub-chain and chromosome

2.2 雙鏈遺傳算法求解過程

如圖3所示，雙鏈遺傳算法求解優(yōu)化模型(3)～(6)，迭代執(zhí)行染色體評(píng)估、選擇、交叉、變異等步驟[24]，最終獲得優(yōu)化網(wǎng)絡(luò)生命周期的sink移動(dòng)路徑選擇方案。

圖3 MSPPA流程Fig. 3 Flow chart of MAPPA

令C表示染色體數(shù)量，c表示染色體操作數(shù)，α1表示交叉概率，α2表示變異概率，g表示迭代次數(shù)。根據(jù)優(yōu)化模型，雙鏈遺傳算法的適應(yīng)度函數(shù)為：

(7)

根據(jù)適應(yīng)度函數(shù)，采用以下步驟求解優(yōu)化模型。

步驟1 初始化。初始化C個(gè)雙鏈染色體，迭代次數(shù)g=0，染色體操作數(shù)c=0，算法中α1、α2等參數(shù)。

步驟2 染色體評(píng)估。計(jì)算所有染色體的適應(yīng)度，直接選擇適應(yīng)度最大的染色體繼承到下一代種群中。

步驟3 選擇。根據(jù)輪盤賭策略選擇需要交叉的2個(gè)染色體。

步驟4 交叉。產(chǎn)生一個(gè)0～1的隨機(jī)數(shù)，如果其大于α1，對(duì)已選擇的2個(gè)染色體進(jìn)行交叉操作。交叉操作采用部分匹配交叉法，先隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，定義這兩點(diǎn)的區(qū)域?yàn)槠ヅ鋮^(qū)域，并交換兩個(gè)父代的匹配區(qū)域，如圖4所示。

對(duì)TEMP A、TEMP B中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行替代，匹配關(guān)系為{6?1, 4?5}，產(chǎn)生子代A、子代B，如圖5所示。

步驟5 變異。產(chǎn)生一個(gè)0～1的隨機(jī)數(shù)，如果其大于α2，對(duì)已交叉的2個(gè)染色體進(jìn)行變異操作。隨機(jī)產(chǎn)生兩個(gè)變異位，交換染色體兩個(gè)變異位的基因，再對(duì)子鏈二(sink站點(diǎn)鏈)的變異位相應(yīng)的值進(jìn)行位變異，如圖6所示。

圖4 父代匹配區(qū)域交換Fig. 4 Exchange of parental matching regions

圖5 匹配關(guān)系替代圖Fig. 5 Substitution map of matching relationship

圖6 變異操作Fig. 6 Mutation operation

步驟6 返回或結(jié)束。c=c+1，如果c

3 仿真實(shí)現(xiàn)和分析

3.1 仿真參數(shù)設(shè)置

為了方便比較算法性能，網(wǎng)絡(luò)生命周期與LEACH協(xié)議[10]相似，使用移動(dòng)sink數(shù)據(jù)采集輪數(shù)計(jì)量。如表1所示，選擇表中參數(shù)，在Matlab軟件上編程實(shí)現(xiàn)MSPPA、 MS-LEACH-RN和LEACH算法。LEACH算法是典型的分簇?cái)?shù)據(jù)收集協(xié)議，而MS-LEACH-RN[9]是基于移動(dòng)sink節(jié)點(diǎn)與集合節(jié)點(diǎn)RN的優(yōu)化LEACH分簇算法。將100個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在120 m×160 m的監(jiān)測區(qū)域，通信半徑60 m，節(jié)點(diǎn)感知數(shù)據(jù)量變化范圍為0～8 000 bit，節(jié)點(diǎn)的初始能量為0.2 J。最后將監(jiān)測區(qū)域劃分成12個(gè)均等的網(wǎng)格，每個(gè)網(wǎng)格中以網(wǎng)格中心點(diǎn)、網(wǎng)格中節(jié)點(diǎn)分布密度重心和網(wǎng)格中數(shù)據(jù)分布質(zhì)心為sink站點(diǎn)，仿真分析MSPPA的收斂性，并比較MSPPA、MS-LEACH-RN和LEACH算法。

表1 仿真參數(shù)Tab. 1 Simulation parameters

3.2 MSPPA收斂性仿真分析

為了驗(yàn)證MSPPA的收斂性，對(duì)MSPPA的最大適應(yīng)度值和平均適應(yīng)度值進(jìn)行仿真計(jì)算，其收斂速度、尋優(yōu)結(jié)果如圖7所示。從圖中最優(yōu)解和平均解的對(duì)比，可知MSPPA具有較好的收斂性。

圖7 MSPPA收斂性Fig. 7 Convergence of MSPPA

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

3.3.1 網(wǎng)絡(luò)生命周期性能分析

為了比較MSPPA和MS-LEACH-RN、LEACH算法的網(wǎng)絡(luò)生命周期性能，在仿真區(qū)域內(nèi)隨機(jī)分布50、100、150、200、250、300個(gè)傳感器節(jié)點(diǎn)，并假設(shè)網(wǎng)絡(luò)生命周期為網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡對(duì)應(yīng)的輪數(shù)。如圖8所示，MSPPA的網(wǎng)絡(luò)生命周期是MS-LEACH-RN的1～2倍，是LEACH算法的8倍，可見MSPPA能延長網(wǎng)絡(luò)生存時(shí)間。

3.3.2 存活節(jié)點(diǎn)數(shù)量性能分析

圖9對(duì)比了上述三種算法的網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)量隨著仿真輪數(shù)的變化情況。LEACH協(xié)議中sink節(jié)點(diǎn)固定，簇頭的負(fù)載過大，故在400輪時(shí)節(jié)點(diǎn)全部死亡；MS-LEACH-RN協(xié)議中sink移動(dòng)軌跡固定在網(wǎng)絡(luò)額度中線，在sink移動(dòng)軌跡附近存在集合節(jié)點(diǎn)(RN)，RN雖然減小了一部分簇頭節(jié)點(diǎn)能耗，但是遠(yuǎn)離sink移動(dòng)軌跡的簇頭能耗沒有降低多少，故此類簇頭節(jié)點(diǎn)過早死亡，網(wǎng)絡(luò)壽命較短；MSPPA在800～950輪死亡的傳感器節(jié)點(diǎn)驟然增加，可見其網(wǎng)絡(luò)能量較為均衡，所以MSPPA在延長網(wǎng)絡(luò)生命周期方面優(yōu)于其他兩個(gè)算法。

圖8 網(wǎng)絡(luò)生命周期Fig. 8 Network lifetime

圖9 節(jié)點(diǎn)存活數(shù)量Fig. 9 Number of surviving nodes

3.3.3 節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差分析

無線傳感器網(wǎng)絡(luò)中，全網(wǎng)所有節(jié)點(diǎn)所有能量的標(biāo)準(zhǔn)差是評(píng)價(jià)能量均衡路由協(xié)議的一個(gè)非常明了的指標(biāo)。標(biāo)準(zhǔn)差反映了各節(jié)點(diǎn)剩余能量的分布狀況，如果網(wǎng)內(nèi)所有節(jié)點(diǎn)的能量水平相當(dāng)，即它們之間的能量差異很小，則節(jié)點(diǎn)剩余能量的標(biāo)準(zhǔn)差較??；若標(biāo)準(zhǔn)差的值較大，則表示網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)的能量情況差異較大，有些節(jié)點(diǎn)有充足的能量，而有些節(jié)點(diǎn)則因?yàn)槟芎倪^快而過早死亡，縮短了網(wǎng)絡(luò)壽命。因此，節(jié)點(diǎn)剩余能量的標(biāo)準(zhǔn)差(Standard Deviation)越小，網(wǎng)絡(luò)中能量的分布越均勻，說明能量均衡路由協(xié)議的性能也越好。節(jié)點(diǎn)剩余能量的標(biāo)準(zhǔn)差σE的計(jì)算公式[26]如下：

(8)

如圖10所示，在仿真150輪時(shí)，LEACH、MS-LEACH-RN和MSPPA傳感器節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差的斜率分別約為0.08/150，0.35/150和0.01/150，故MSPPA節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差的斜率要遠(yuǎn)小于LEACH與MS-LEACH-RN，所以MSPPA在能量均衡方面優(yōu)于其他兩個(gè)算法。

3.3.4 “熱區(qū)”情況分析

圖11為MSPPA與LEACH和MS-LEACH-RN在仿真300輪時(shí)的節(jié)點(diǎn)能量消耗圖，該圖描繪了網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)的能耗分布。盡管LEACH算法采用自適應(yīng)簇頭選取機(jī)制(選擇剩余能量大的節(jié)點(diǎn)充當(dāng)簇頭)，稍微均衡了網(wǎng)絡(luò)能耗，但是由于其簇內(nèi)采用“多對(duì)一”通信，簇內(nèi)所有數(shù)據(jù)都通過簇頭傳輸?shù)絪ink節(jié)點(diǎn)，導(dǎo)致簇頭負(fù)載較大，如圖11(a)所示，許多節(jié)點(diǎn)已耗盡0.2 J能量，“熱區(qū)”效應(yīng)嚴(yán)重。MS-LEACH-RN集合了移動(dòng)sink節(jié)點(diǎn)、LEACH分簇算法、集合節(jié)點(diǎn)的優(yōu)點(diǎn)，大大縮短了簇頭節(jié)點(diǎn)到sink節(jié)點(diǎn)的通信距離，降低了簇頭的能耗，但是網(wǎng)絡(luò)邊界的簇頭由于距離移動(dòng)sink軌跡較遠(yuǎn)，故其傳輸數(shù)據(jù)能耗較大，所以網(wǎng)絡(luò)邊界易出現(xiàn)“熱區(qū)”，如圖11(b)所示，網(wǎng)絡(luò)邊界節(jié)點(diǎn)能耗已達(dá)到0.1～0.14 J，出現(xiàn)“熱區(qū)”效應(yīng)。而MSPPA根據(jù)網(wǎng)絡(luò)壽命動(dòng)態(tài)選取每個(gè)網(wǎng)絡(luò)中移動(dòng)sink停留站點(diǎn)，故傳感器節(jié)點(diǎn)與sink節(jié)點(diǎn)的通信距離不固定，能更好地均衡網(wǎng)絡(luò)能耗，緩解“熱區(qū)”效應(yīng)，如圖11(c)所示，網(wǎng)絡(luò)還沒出現(xiàn)“熱區(qū)”現(xiàn)象，故可得出MSPPA在緩解“熱區(qū)”問題上優(yōu)于另外兩個(gè)算法。

圖10 節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差Fig. 10 Residual energy standard deviation of nodes

圖11 “熱區(qū)”情況對(duì)比Fig. 11 Hotspot situation comparison

4 結(jié)語

本文針對(duì)節(jié)點(diǎn)分布不均勻、節(jié)點(diǎn)感知數(shù)據(jù)非均勻而造成能耗不均衡、“熱區(qū)”能量空洞問題，設(shè)計(jì)了面向延長網(wǎng)絡(luò)壽命和最短路徑的WSN移動(dòng)sink路徑規(guī)劃算法(MSPPA)。該算法將WSN監(jiān)測區(qū)域劃分成網(wǎng)格，根據(jù)網(wǎng)絡(luò)實(shí)際情況，在每個(gè)網(wǎng)格中定義若干個(gè)sink候選站點(diǎn)(如網(wǎng)格中心點(diǎn)、網(wǎng)格中節(jié)點(diǎn)分布密度重心、網(wǎng)格中數(shù)據(jù)分布質(zhì)心等)，使用雙鏈遺傳算法規(guī)劃移動(dòng)sink遍歷網(wǎng)格的順序和選擇每個(gè)網(wǎng)格中移動(dòng)sink訪問站點(diǎn)，得到移動(dòng)sink節(jié)點(diǎn)遍歷所有網(wǎng)格收集數(shù)據(jù)的移動(dòng)路徑。該算法在能耗均衡性與緩解“熱區(qū)”效應(yīng)等方面，均表現(xiàn)良好，其網(wǎng)絡(luò)生命周期優(yōu)于LEACH和MS-LEACH-RN。

References)

[1] XING G, WANG T, XIE Z, et al. Rendezvous planning in wireless sensor networks with mobile elements [J]. IEEE Transactions on Mobile Computing, 2008, 7(12): 1430-1443.

[2] CHATZIGIANNAKIS I, KINALIS A, NIKOLETSEAS S. Efficient data propagation strategies in wireless sensor networks using a single mobile sink [J]. Computer Communications, 2008, 31(5): 896-914.

[3] KHAN A W, ABDULLAH A H, ANISI M H, et al. A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks [J]. Sensors, 2014, 14(2): 2510-2548.

[4] SUN W, YANG Z, ZHANG X, et al. Energy-efficient neighbor discovery in mobile Ad Hoc and wireless sensor networks: a survey [J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1448-1459.

[5] 張惠麒,林志貴,李敏,等.基于移動(dòng)sink節(jié)點(diǎn)的路由協(xié)議的比較與分析[J].計(jì)算機(jī)科學(xué),2014,41(S1):276-280. (ZHANG H Q, LIN Z G, LI M, et al. Comparison and analysis of routing protocol based on mobile sink [J]. Computer Science, 2014, 41(S1): 276-280.)

[6] GU Y, REN F, JI Y, et al. The evolution of sink mobility management in wireless sensor networks: a survey [J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 507-524.

[7] LIN C-J, CHOU P-L, CHOU C-F. HCDD: hierarchical cluster-based data dissemination in wireless sensor networks with mobile sink [C]// IWCMC ’06: Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing. New York: ACM, 2006: 1189-1194.

[8] HAMIDA E B, CHELIUS G. A line-based data dissemination protocol for wireless sensor networks with mobile sink [C]// ICC ’08: Proceedings of the 2008 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2008: 2201-2205.

[9] 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.

[10] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocols for wireless microsensor networks [C]// HICSS ’00: Proceedings of the 33rd Hawaii International Conference on Systems Sciences. Washington, DC: IEEE Computer Society, 2000, 8: 8020.

[11] BHATTI R, KAUR G. Virtual grid based energy efficient mobile sink routing algorithm for WSN [C]// Proceedings of the 11th International Conference on Intelligent Systems and Control. Piscataway, NJ: IEEE, 2017:30-33.

[12] 梁青,焦峰.WSN中基于二分法與移動(dòng)Sink的數(shù)據(jù)收集協(xié)議[J].計(jì)算機(jī)工程,2016,42(12):39-43. (LIANG Q, JIAO F. Data collection protocol for WSN based on dichotomy and mobile sink [J]. Computer Engineering, 2016, 42(12): 39-43.)

[13] YUN Y, XIA Y. Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications [J]. IEEE Transactions on Mobile Computing, 2010, 9(9): 1308-1318.

[14] 林德鈺,王泉,劉伎昭.無線傳感網(wǎng)的移動(dòng)與靜態(tài)sink相結(jié)合的節(jié)能策略[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2016,48(11):162-168. (LIN D Y, WANG Q, LIU J Z. Energy-saving strategy by combining mobile and static sink schemes for wireless sensor networks [J]. Journal of Harbin Institute of Technology, 2016, 48(11): 162-168.)

[15] 王章權(quán),陳友榮,任條娟,等.數(shù)據(jù)傳輸時(shí)延和跳數(shù)受限的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(4):583-592. (WANG Z Q, CHEN Y R, REN T J, et al. Sink node moving path selection algorithm limited by data transmission delay and hops [J]. Chinese Journal of Sensor and Actuators, 2016, 29(4): 583-592.)

[16] PAVITHRA H, SHIVASHANKAR, POORNIMA G R. An efficient mobile sink path selection approach for WSN’s [C]// Proceedings of the 2016 IEEE International Conference on Recent Trends in Electronics Information Communication Technology. Piscataway, NJ: IEEE, 2016: 151-155.

[17] 王薇,史浩山,黃鵬宇,等.基于二次柵格劃分的移動(dòng)sink最小路徑構(gòu)建算法[J].西北工業(yè)大學(xué)學(xué)報(bào),2016,34(6):1016-1021. (WANG W, SHI H S, HUANG P Y, et al. A constructing mobile path minimal path algorithm based on quadratic grid [J]. Journal of Northwestern Polytechnical University, 2016, 34(6): 1016-1021.)

[18] 于志博,孔祥雪,裴金金.移動(dòng)Sink的傳感器網(wǎng)絡(luò)路徑優(yōu)化策略[J].傳感器與微系統(tǒng),2016,35(11):44-46. (YU Z B, KONG X X, PEI J J. Mobile sink-based path optimization strategy in wireless sensor networks [J]. Transducer and Microsystem Technologies, 2016, 35(11): 44-46.)

[19] 陶志勇,蔣守鳳.基于簇首移動(dòng)的無線傳感器網(wǎng)絡(luò)路由算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(5):75-78. (TAO Z Y, JIANG S F. Clustering algorithm for wireless sensor networks with mobile cluster heads [J]. Computer Engineering and Applications, 2016, 52(5): 75-78.)

[20] SHI Y, HOU Y T. Theoretical results on base station movement problem for sensor network [C]// INFOCOM 2008: Proceedings of the 27th Conference on Computer Communications. Piscataway, NJ: IEEE, 2008:1-5.

[21] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, 2000, 1(4): 660-670.

[22] TASHTARIAN F, MOGHADDAM M H Y, SOHRABY K, et al. ODT: optimal deadline-based trajectory for mobile sinks in WSN: a decision tree and dynamic programming approach [J]. Computer Networks, 2015, 77: 128-143.

[23] TASHTARIAN F, HOSSEIN Y M M, SOHRABY K, et al. On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks [J]. IEEE Transactions on Vehicular Technology, 2015, 64(7): 3177-3189.

[24] 王章權(quán),陳友榮,尉理哲,等.優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(3):409-415. (WANG Z Q, CHEN Y R, YU L Z, et al. Mobile path selection algorithm of sink node for optimizing network lifetime [J]. Chinese Journal of Sensor and Actuators, 2014, 27(3): 409-415.)

[25] 曾又姣,金燁.基于遺傳算法的貼片機(jī)貼裝順序優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng),2004,10(2):205-208. (ZENG Y J, JIN Y. Optimization of placement order of placement machine based on genetic algorithm [J]. Computer Integrated Manufacturing Systems, 2004, 10(2):205-208.)

[26] ZENG K, REN K, LOU W, et al. Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply [J]. Wireless Networks, 2009, 15(1): 39-51.

This work is partially supported by the National Natural Science Foundation of China (61371107), the Foundation of Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (GXKL061501).

MOWenjie, born in 1990, M. S. candidate. His research interests include wireless sensor network, routing protocol.

ZHENGLin, born in 1973, Ph. D., professor. His research interests include wireless UWB communication, wireless sensor network, mobile communication, adaptive signal processing, spread spectrum communication, packet wireless network.

Pathplanningalgorithmformobilesinkwithoptimizednetworklifetimeandshortestpathinwirelesssensornetwork

MO Wenjie1,2, ZHENG Lin1,2*

(1.GuangxiKeyLaboratoryofWirelessWidebandCommunicationandSignalProcessing(GuilinUniversityofElectronicTechnology),
GuilinGuangxi541004,China；2.SchoolofInformationandCommunication,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)

In order to alleviate the problem of the imbalance energy consumption and hotspot due to the uneven distribution of nodes and the different amount of perception data in the Wireless Sensor Network (WSN), a Path Planning Algorithm of Mobile Sink named MSPPA was proposed to optimize network lifetime and shortest path in WSN. Firstly, by defining the grids in the network area, several candidate sites of mobile sink were distributed in each grid, and then sink node selected a site for sojourning and collecting data of nodes in each grid. Secondly, based on the relationship between network lifetime and the selection of sink sites, an optimization model was established to weigh network lifetime and mobile journey of sink. Finally, the double-stranded genetic algorithm was proposed to plan the order of mobile sink traversing grids and selecting site of the mobile sink in each grid, then the optimal path of mobile sink was obtained. The simulation results show that, compared with Low-Energy Adaptive Clustering Hierarchy (LEACH) algorithm and optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes (MS-LEACH-RN), the network lifetime of MSPPA was increased by 60%. The proposed MSPPA has a good balance of energy consumption as well. The experimental results indicate that the proposed MSPPA can effectively alleviate the imbalance of energy consumption and the hotspot problems, prolonging the network lifetime.

Wireless Sensor Network (WSN); mobile sink; data collection; double-stranded genetic algorithm; path planning; network lifetime

TN926

A

2017- 02- 08;

2017- 02- 26。

國家自然科學(xué)基金資助項(xiàng)目(61371107)；廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目(GXKL061501)。

莫文杰(1990—)，男，廣西柳州人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)、路由協(xié)議； 鄭霖(1973—)，男，廣西桂林人，教授，博士，主要研究方向：無線超寬帶通信、無線傳感器網(wǎng)絡(luò)、移動(dòng)通信、自適應(yīng)信號(hào)處理、擴(kuò)頻通信、分組無線網(wǎng)絡(luò)。

1001- 9081(2017)08- 2150- 07

10.11772/j.issn.1001- 9081.2017.08.2150