陳友榮,陸思一,任條娟,,楊海波

(1.浙江樹人大學(xué)信息科技學(xué)院,杭州 310015;2. 常州大學(xué)信息科學(xué)與工程學(xué)院,江蘇 常州 213164)

一種無線傳感網(wǎng)的Sink節(jié)點移動路徑規(guī)劃算法研究*

陳友榮1,2*,陸思一2,任條娟1,2,楊海波1

(1.浙江樹人大學(xué)信息科技學(xué)院,杭州 310015;2. 常州大學(xué)信息科學(xué)與工程學(xué)院,江蘇 常州 213164)

為尋找傳感節(jié)點均勻分布時Sink節(jié)點的最優(yōu)移動路徑和最大網(wǎng)絡(luò)生存時間,提出一種無線傳感網(wǎng)的Sink節(jié)點移動路徑規(guī)劃算法(MPOA)。在MPOA算法中,將Sink節(jié)點的數(shù)據(jù)收集范圍分解成多個圓環(huán),將監(jiān)測區(qū)域分解成多個網(wǎng)格。根據(jù)Sink節(jié)點的停留位置和多跳通信方式,采用數(shù)學(xué)公式表示每一個網(wǎng)格的單位節(jié)點能耗,從而獲得Sink節(jié)點移動的網(wǎng)絡(luò)生存時間優(yōu)化模型。采用修正的混合粒子群算法求解該優(yōu)化模型,獲得網(wǎng)絡(luò)生存時間、Sink節(jié)點的停留位置和移動路徑的最優(yōu)方案。仿真結(jié)果表明:MPOA算法可尋找到Sink節(jié)點的最優(yōu)移動路徑,從而平衡網(wǎng)絡(luò)能耗,提高網(wǎng)絡(luò)生存時間。在一定的條件下,MPOA算法比Circle,Rect和Rand算法更優(yōu)。

無線傳感網(wǎng);移動Sink節(jié)點;路徑規(guī)劃;粒子群算法

無線傳感網(wǎng)WSNs(Wireless Sensor Networks)由空間分布的自主傳感節(jié)點和Sink節(jié)點組成,可協(xié)同監(jiān)測溫度、聲音、振動、壓力、運(yùn)動等物理和環(huán)境參數(shù),在戰(zhàn)場監(jiān)控、戰(zhàn)場損傷評估、工業(yè)過程監(jiān)控、機(jī)器運(yùn)行狀況監(jiān)控、家庭自動化、交通監(jiān)控等軍事、工業(yè)和民用領(lǐng)域上具有較大的應(yīng)用價值和市場潛力[1-2]。

在無線傳感網(wǎng)中,能量效率是無線傳感網(wǎng)的最重要問題之一。由于傳感節(jié)點的電池能量有限而且其電池更換需要花費(fèi)較多的時間和精力,因此無線傳感網(wǎng)需要在無人干預(yù)下自行運(yùn)行足夠長的時間。但是在靜態(tài)Sink節(jié)點的無線傳感網(wǎng)中,由于多跳路由具有熱點且數(shù)據(jù)流量集中,靠近Sink節(jié)點的傳感節(jié)點消耗較多的能量且失效較早。這個問題被稱為無線傳感網(wǎng)的熱點問題[3]。熱點問題可惡化無線傳感網(wǎng)的網(wǎng)絡(luò)連接和生存時間,甚至使無線傳感網(wǎng)不能正常工作。為克服熱點問題,很多學(xué)者研究Sink節(jié)點的移動。移動Sink節(jié)點可提供負(fù)載均衡,讓其周圍的熱點發(fā)生變化且出現(xiàn)在網(wǎng)絡(luò)的各個區(qū)域,這有助于實現(xiàn)統(tǒng)一的能量消耗,從而延長網(wǎng)絡(luò)生存時間。

在Sink節(jié)點移動的無線傳感網(wǎng)中,需要確定Sink節(jié)點的停留位置和移動路徑,因此Sink節(jié)點的移動路徑選擇問題是其急需解決的問題之一。目前,相關(guān)路徑選擇算法的研究取得一定的成果。文獻(xiàn)[4]考慮飛行器作為Sink節(jié)點,移動收集傳感節(jié)點的存儲數(shù)據(jù)。根據(jù)其移動特性重構(gòu)基于TSP(traveling salesman problem)算法的移動路徑,并根據(jù)數(shù)據(jù)收集時間調(diào)整路徑,使其數(shù)據(jù)傳輸時延最小。但是該算法沒有考慮傳感節(jié)點的能耗和網(wǎng)絡(luò)生存時間的優(yōu)化問題。有些學(xué)者考慮Sink節(jié)點的單跳數(shù)據(jù)收集,研究Sink節(jié)點的移動路徑選擇算法。如文獻(xiàn)[5]基于傳感節(jié)點的位置信息,采用范圍約束分簇算法確定每一個簇頭的位置,即Sink節(jié)點的停留位置,利用TSP算法尋找遍歷所有停留位置的路徑。文獻(xiàn)[6]建立權(quán)衡網(wǎng)絡(luò)生存時間和Sink節(jié)點移動路程的優(yōu)化模型,采用遺傳算法求解該優(yōu)化模型,獲得可將傳感節(jié)點分成多個簇的停留位置和移動路徑。文獻(xiàn)[7]根據(jù)節(jié)點的位置等信息,建立Sink節(jié)點移動單跳收集數(shù)據(jù)下的網(wǎng)絡(luò)生存時間優(yōu)化模型,并構(gòu)建決策樹求解該優(yōu)化模型,獲得Sink節(jié)點的移動路徑。文獻(xiàn)[8]將監(jiān)測區(qū)域分解成多個三角形,獲得經(jīng)過三角形的3個頂點的圓。每一個圓心作為Sink節(jié)點的停留位置。Sink節(jié)點采用貪婪算法確定下一個停留位置。但是由于Sink節(jié)點的單跳數(shù)據(jù)收集范圍有限,為保證能收集到所有傳感節(jié)點的數(shù)據(jù),其移動路徑較長且數(shù)據(jù)傳輸時延較大。另一些學(xué)者考慮Sink節(jié)點的多跳數(shù)據(jù)收集,研究相關(guān)Sink節(jié)點的移動路徑選擇算法。如文獻(xiàn)[9]建立優(yōu)先級高且移動距離不小于閾值的虛擬點集合,采用TSP算法求解能遍歷該集合內(nèi)所有虛擬點的最短路徑。文獻(xiàn)[10]將監(jiān)測區(qū)域分成多個大小相同的圓盤。計算每一個圓盤內(nèi)Sink節(jié)點的停留位置,采用量子遺傳算法獲得最短移動路徑。文獻(xiàn)[11]利用分簇技術(shù)將傳感節(jié)點分成通信半徑相同的簇,選擇剩余能量相對充足的傳感節(jié)點作為簇頭。根據(jù)簇頭的位置,利用TSP算法構(gòu)建一條盡可能短的移動路徑。文獻(xiàn)[12]選擇權(quán)值較高的傳感節(jié)點作為RP點(Rendezvous Point),建立點集合,尋找能訪問所有RP點且不超過最大數(shù)據(jù)傳輸時延的路徑。文獻(xiàn)[13]考慮傳感節(jié)點網(wǎng)格分布和鄰居傳感節(jié)點的剩余能量變化,提出一種Sink節(jié)點移動的分布式啟發(fā)算法,尋找其停留位置。但是在文獻(xiàn)[9-13]中,假設(shè)所有傳感節(jié)點都能獲知自身位置坐標(biāo)。為保證定位精度,需要安裝GPS或北斗定位模塊,這增加了節(jié)點能耗和系統(tǒng)硬件成本。且Sink節(jié)點在路徑選擇前需要獲知傳感節(jié)點的位置、能量等信息。文獻(xiàn)[14]提出圓形移動路徑(CIRCLES),但是該算法只考慮傳感節(jié)點的定位,沒有考慮Sink節(jié)點的數(shù)據(jù)收集。

文獻(xiàn)[8-13]可尋找到Sink節(jié)點的若干個停留位置,獲得其移動路徑,從而達(dá)到節(jié)約傳感節(jié)點能耗,提高網(wǎng)絡(luò)生存時間的目的。但是這些移動路徑是否具有已經(jīng)達(dá)到最大提高網(wǎng)絡(luò)生存時間的效果,仍需要進(jìn)一步研究,而且很多移動路徑需要傳感節(jié)點的位置、能量等信息。因此在上述文獻(xiàn)的基礎(chǔ)上,提出了一種無線傳感網(wǎng)的Sink節(jié)點移動路徑規(guī)劃算法MPOA(Movement Path Optimization Algorithm of Sink Node for Wireless Sensor Networks)。MPOA算法不需要獲知傳感節(jié)點的位置、能量等信息,只考慮傳感節(jié)點均勻分布和Sink節(jié)點的多跳數(shù)據(jù)收集,研究Sink節(jié)點的移動對整個監(jiān)測區(qū)域能耗分布的影響。將Sink節(jié)點的數(shù)據(jù)收集范圍分解成多個圓環(huán)和內(nèi)圓,外層圓環(huán)內(nèi)傳感節(jié)點只發(fā)送給其鄰居內(nèi)層圓環(huán)或鄰居內(nèi)圓。根據(jù)上述多跳數(shù)據(jù)收集的特點,提出了Sink節(jié)點移動的網(wǎng)絡(luò)生存時間優(yōu)化模型。采用修正的混合粒子群算法求解該優(yōu)化模型,獲得最優(yōu)方案——Sink節(jié)點的移動路徑、停留位置和網(wǎng)絡(luò)生存時間。該算法可尋找到一條最大化網(wǎng)絡(luò)生存時間的移動路徑,并為其他移動路徑選擇算法提供參考。

1 算法原理

在MPOA算法中,假設(shè):無線傳感網(wǎng)的長方形監(jiān)測區(qū)域內(nèi)存在多個傳感節(jié)點和1個Sink節(jié)點。當(dāng)存在多個Sink節(jié)點時,將監(jiān)測區(qū)域分成與Sink節(jié)點數(shù)量相同的子區(qū)域,每一個Sink節(jié)點負(fù)責(zé)其中一個子區(qū)域,則多個Sink節(jié)點的數(shù)據(jù)收集問題轉(zhuǎn)換成多個單一Sink節(jié)點的數(shù)據(jù)收集問題;監(jiān)測區(qū)域內(nèi)傳感節(jié)點均勻分布;Sink節(jié)點可移動到監(jiān)測區(qū)域的任一位置;所有傳感節(jié)點的能量有限,且具有統(tǒng)一的通信范圍、初始節(jié)點能量等特點,是同構(gòu)的傳感節(jié)點。雖然Sink節(jié)點的能量也有限,但是可通過人工方式進(jìn)行更換。

如圖1所示,Sink節(jié)點停留在某一個位置時,采用多跳通信的方式收集以自身位置為圓心和以d為半徑的圓內(nèi)傳感節(jié)點的數(shù)據(jù),即其數(shù)據(jù)收集范圍是一個圓形。將該圓分成一個半徑為r的內(nèi)圓和厚度均為r的n-1個圓環(huán),其中n=d/r,且d遠(yuǎn)大于r。外層圓環(huán)內(nèi)傳感節(jié)點只轉(zhuǎn)發(fā)給其鄰居內(nèi)層圓環(huán)或內(nèi)圓內(nèi)傳感節(jié)點。根據(jù)上述的假設(shè),當(dāng)Sink節(jié)點的位置固定且傳感節(jié)點隨機(jī)均勻分布時,Sink節(jié)點數(shù)據(jù)收集范圍內(nèi)傳感節(jié)點能耗也基本確定。為方便計算分布在監(jiān)測區(qū)域內(nèi)某一個位置的傳感節(jié)點能耗,如圖2所示,將方形監(jiān)測區(qū)域分成大小相同的矩形網(wǎng)格,按照從左到右,從上到下的原則對每一個網(wǎng)格進(jìn)行編碼,并計算每一個網(wǎng)格中心的位置坐標(biāo)。當(dāng)Sink節(jié)點沿著某一個路徑移動時,根據(jù)每一個網(wǎng)格中心的位置,計算所有網(wǎng)格的單位節(jié)點能耗,其中網(wǎng)格的單位節(jié)點能耗定義為當(dāng)Sink節(jié)點沿著某一個路徑移動且傳感節(jié)點在該網(wǎng)格中心上時,傳感節(jié)點轉(zhuǎn)發(fā)其他傳感節(jié)點數(shù)據(jù)和發(fā)送自身傳感節(jié)點數(shù)據(jù)的單位時間能耗,則可獲得整個監(jiān)測區(qū)域內(nèi)單位節(jié)點能耗的分布情況、單位節(jié)點能耗最大的網(wǎng)格和網(wǎng)絡(luò)生存時間。

圖1 Sink節(jié)點的數(shù)據(jù)收集

圖2 監(jiān)測區(qū)域的網(wǎng)格劃分

但是MPOA算法仍需要解決以下二個問題:一是當(dāng)Sink節(jié)點沿著某個路徑移動時,如何運(yùn)用數(shù)據(jù)公式表達(dá)每一個網(wǎng)格的單位節(jié)點能耗和網(wǎng)絡(luò)生存時間,建立網(wǎng)絡(luò)生存時間的優(yōu)化模型。二是如何采用修正的混合粒子群算法求解該優(yōu)化模型,獲得Sink節(jié)點的最優(yōu)移動路徑。這二個問題的具體解決如下。

1.1 優(yōu)化模型的建立

令Sink節(jié)點的當(dāng)前停留位置坐標(biāo)為(xs,ys),網(wǎng)格中心i的位置坐標(biāo)為(xi,yi)和監(jiān)測區(qū)域的長和寬為(Lx,Ly),則經(jīng)過Sink節(jié)點和網(wǎng)格中心i的直線方程為

(1)

Sink節(jié)點到網(wǎng)格中心i的有向射線與監(jiān)測區(qū)域的邊界交點為(fx(xs,ys,xi,yi),fy(xs,ys,xi,yi)),即(xc,yc)。假設(shè)監(jiān)測區(qū)域為長方形,則邊界交點坐標(biāo)的計算方法如下:

當(dāng)xs=xi且ys=yi時,則兩點重合,令yi=yi+0.1,則xc=xi,yc=Ly。

當(dāng)xs=xi且ys>yi時,則xc=xi,yc=0;

當(dāng)xs=xi且ys

當(dāng)xs>xi且ys=yi時,則xc=0,yc=yi;

當(dāng)xs

當(dāng)xs≠xi且ys≠yi時,則需要判斷該點出現(xiàn)在哪個三角形內(nèi)。如圖3所示,如果xsxi,yi≤ysxi/xs時,則(xi,yi)在三角形2內(nèi),將yc=0代入式(1),可得xc=-yi(xs-xi)/(ys-yi)+xi,yc=0。如果xs(ys-Ly)(xi-Lx)/(xs-Lx)+L或xs>xi,yi>(ys-Ly)xi/xs+Ly時,則點(xi,yi)在三角形4內(nèi),可得xc=(Ly-yi)(xs-xi)/(ys-yi)+xi,yc=Ly。如果xs>xi,ys(xi)/xs≤yi≤(ys-Ly)xi/xs+Ly時,則點(xi,yi)在三角形1內(nèi),可得xc=0,yc=-xi(ys-yi)/(xs-xi)+yi。

圖3 邊界交點的計算

根據(jù)直線與監(jiān)測區(qū)域的邊界交點和Sink節(jié)點的多跳數(shù)據(jù)收集方式,計算邊界交點(xc,yc)經(jīng)過網(wǎng)格中心i到Sink節(jié)點的最大跳數(shù)Ni,max為

(2)

式中:?x」表示大于或等于x的最小整數(shù)。計算網(wǎng)格中心i所在位置到Sink節(jié)點的跳數(shù)Ni為

(3)

Sink節(jié)點停留在某一個位置時,網(wǎng)格中心i的單位節(jié)點能耗由接收和發(fā)送該位置到邊界交點區(qū)域內(nèi)傳感節(jié)點的單位時間能耗和該位置上發(fā)送自身數(shù)據(jù)的單位時間能耗組成,即為

(4)

式中:((Ni,maxr)2-π(Nir)2)ρ表示自身傳感節(jié)點所在圓環(huán)到最外層圓環(huán)的傳感節(jié)點個數(shù),[π(Nir)2-π(Nir-r)2]ρ表示自身傳感節(jié)點所在圓環(huán)的傳感節(jié)點個數(shù),ρ表示傳感節(jié)點的密度,Si表示傳感節(jié)點的感知數(shù)據(jù)速率,Er表示傳感節(jié)點接收單位bit數(shù)據(jù)的能耗,ε表示傳感節(jié)點發(fā)送單位bit數(shù)據(jù)的能耗系數(shù)。由式(4)可知,網(wǎng)格中心i的單位節(jié)點能耗與傳感節(jié)點的密度無關(guān)。

當(dāng)Sink節(jié)點沿著某一路徑P=[p1,p2,…,pm]移動且在m個停留位置上收集傳感節(jié)點的數(shù)據(jù)時,該移動路徑下網(wǎng)格中心i的總單位節(jié)點能耗,即該網(wǎng)格的單位節(jié)點能耗為

(5)

則網(wǎng)絡(luò)生存時間為

T=min(Einital/Ei),?i∈V

(6)

式中:V表示所有網(wǎng)格中心集合,Einital表示初始能耗。根據(jù)上述分析,考慮Sink節(jié)點移動距離和停留位置個數(shù)有限,建立網(wǎng)絡(luò)生存時間的優(yōu)化模型。

(7)

式中:num(P)表示移動路徑P的停留位置個數(shù),NP表示允許的最大停留位置個數(shù),Lenth(P)表示移動路徑P的路程,LP表示允許的最大移動路程。

1.2 模型的求解

標(biāo)準(zhǔn)粒子群算法雖然可以求解優(yōu)化模型(7),且操作簡單,但是隨著迭代次數(shù)的不斷增加,有可能收斂到局部最優(yōu)解?；旌狭Ｗ尤核惴ㄞ饤壛藗鹘y(tǒng)粒子群算法中的通過跟蹤極值更新粒子群的方法,而是引入遺傳算法的交叉和變異操作,可較好的搜索最優(yōu)解。因此采用修正的混合粒子群算法求解優(yōu)化模型(7)。但是在模型求解過程中,如果盲目尋找Sink節(jié)點的停留位置,則仍容易陷入局部最優(yōu)解,很難尋找到Sink節(jié)點的全局最優(yōu)位置。因此,需要考慮Sink節(jié)點的停留位置選擇規(guī)則。

選擇監(jiān)測區(qū)域長和寬均為200 m,網(wǎng)格數(shù)量為20×20個。如圖4所示,當(dāng)Sink節(jié)點停留在監(jiān)測區(qū)域的中心位置(100 m,100 m)時,監(jiān)測區(qū)域的單位節(jié)點能耗呈山峰狀分布,即Sink節(jié)點停留位置周圍網(wǎng)格的單位節(jié)點能耗較高,并隨著到Sink節(jié)點停留位置的距離增加,網(wǎng)格的單位節(jié)點能耗變小。如果Sink節(jié)點的停留位置集中在監(jiān)測區(qū)域的幾個相鄰位置時,則其周圍的網(wǎng)格單位節(jié)點能耗較大,網(wǎng)絡(luò)生存時間較小,因此Sink節(jié)點的停留位置應(yīng)圍繞監(jiān)測區(qū)域的中心位置,出現(xiàn)在監(jiān)測區(qū)域的各個方向,從而降低網(wǎng)格單位節(jié)點能耗和提高網(wǎng)格生存時間。

圖4 Sink節(jié)點停留在網(wǎng)格中心位置時的單位節(jié)點能耗分布圖

當(dāng)Sink節(jié)點的停留位置個數(shù)為NP時,根據(jù)角度將監(jiān)測區(qū)域分成NP個子區(qū)域,每一個子區(qū)域內(nèi)只能出現(xiàn)一個Sink節(jié)點的停留位置。如圖5所示,將監(jiān)測區(qū)域分成8個三角形子區(qū)域,每一個三角形中頂點為監(jiān)測區(qū)域中心位置的角度數(shù)相同。修正混合粒子群算法的基本原理如下。

圖5 Sink節(jié)點停留位置選擇的子區(qū)域劃分圖

1.2.1 個體編碼

優(yōu)化模型中要求Sink節(jié)點的停留位置個數(shù)不超過最大值NP,且Sink節(jié)點的停留位置較多時,平衡網(wǎng)格單位節(jié)點能耗的效果較好,因此選擇NP×2維數(shù)組表示Sink節(jié)點的移動位置。依次經(jīng)過該數(shù)據(jù)中每個元素,則可構(gòu)成Sink節(jié)點的移動路徑,即粒子P=[p1,p2,…,pNp]。

1.2.2 適應(yīng)度值

根據(jù)每一個粒子的移動路徑,采用式(8)計算粒子適應(yīng)度值。粒子的適應(yīng)度表示Sink節(jié)點按照該粒子方案移動時的網(wǎng)絡(luò)生存時間。網(wǎng)絡(luò)生存時間越高,粒子適應(yīng)度值越高,其移動方案越好。

(8)

1.2.3 交叉操作

粒子通過與個體極值粒子和群體極值粒子進(jìn)行交叉操作,更新自身粒子。隨機(jī)產(chǎn)生交叉位(c1,c2),1≤c1

1.2.4 變異操作

產(chǎn)生一個[0 1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)。當(dāng)該隨機(jī)數(shù)小于變異因子b1時,該粒子發(fā)生變異,計算粒子中元素到監(jiān)測區(qū)域中心位置的平均距離dave,對粒子中每一個元素進(jìn)行以下變異操作:產(chǎn)生一個[0 1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù),當(dāng)該隨機(jī)數(shù)小于變異因子b2時,在該元素所在的子區(qū)域內(nèi),產(chǎn)生到監(jiān)測區(qū)域中心位置距離在區(qū)間[0.6dave,1.4dave]內(nèi)均勻分布的隨機(jī)位置,替換原來元素。

1.2.5 路徑修正操作

當(dāng)粒子的移動路徑長度超過允許的最大移動路程LP時,采用式(9)和式(10)修正該粒子。

Px=(Px-Lx/2)LP/Lenth(P)+Lx/2

(9)

Py=(Py-Ly/2)LP/Lenth(P)+Ly/2

(10)

式中:Px表示移動路徑P中所有元素的橫坐標(biāo),Py表示移動路徑P中所有元素的縱坐標(biāo)。Lx和Ly分別表示監(jiān)測區(qū)域的長和寬。

圖6 MPOA算法的工作流程圖

2 算法實現(xiàn)

如圖6所示,MPOA算法的具體實現(xiàn)步驟如下:

步驟1 初始化算法的各種參數(shù):迭代次數(shù)初值m1=1,當(dāng)前粒子m2=1,監(jiān)測區(qū)域的長Lx和寬Ly,圓環(huán)厚度r,網(wǎng)格數(shù)量,允許的最大停留位置個數(shù)Np,允許的最大移動路程LP,變異因子b1和b2,最大迭代次數(shù)M1,粒子個數(shù)M2等;

步驟2 初始化粒子群。將監(jiān)測區(qū)域分成NP個子區(qū)域,并重復(fù)執(zhí)行M2次以下操作可獲得初始粒子群:在每一個子區(qū)域內(nèi)隨機(jī)產(chǎn)生一個Sink節(jié)點的停留位置,構(gòu)成具有Np個停留位置的粒子。當(dāng)該粒子的移動路徑長度超過允許的最大移動路程LP時,通過式(9)和式(10)執(zhí)行路徑修正操作;

步驟3 依次選擇粒子m2中元素,循環(huán)執(zhí)行以下操作計算每一個網(wǎng)格的單位節(jié)點能耗:根據(jù)網(wǎng)格中心位置和元素位置,計算最大跳數(shù)Ni,max,通過式(4)計算該網(wǎng)格的單位節(jié)點能耗。通過式(8)獲得網(wǎng)絡(luò)生存時間,與歷史極值比較,更新個體極值粒子和全局極值粒子。m2=m2+1。如果m2大于M2,則可獲得每一個粒子的適應(yīng)度值,獲得個體極值和全局極值,m2=1,跳到步驟4,否則重新跳到步驟3;

步驟4 粒子m2分別與個體極值粒子和全局極值粒子進(jìn)行交叉和變異操作;

步驟5 當(dāng)該粒子的移動路徑長度超過允許的最大移動路程LP時,通過式(9)和(10)執(zhí)行路徑修正操作。m2=m2+1,如果m2大于M2,則跳到步驟4,否則跳到步驟6;

步驟6m1=m1+1,如果m1大于M1,則結(jié)束算法,輸出最優(yōu)移動路徑和最大網(wǎng)絡(luò)生存時間,否則跳到步驟3。

循環(huán)執(zhí)行關(guān)鍵步驟3～6,則可獲得優(yōu)化模型(7)的一個最優(yōu)解,即Sink節(jié)點的最優(yōu)停留位置和移動路徑,從而達(dá)到提高網(wǎng)絡(luò)生存時間的目的。

分析MPOA算法的時間復(fù)雜性。如圖6所示,MPOA算法主要是M1M2個粒子進(jìn)行適應(yīng)度計算、交叉操作和變異操作。每一個粒子都需要根據(jù)其位置元素,計算每一個網(wǎng)格的單位節(jié)點能耗,即每一個粒子計算的時間復(fù)雜度是Θ(NpNgrid),其中Ngrid表示劃分的網(wǎng)格數(shù)量。因此MPOA算法的時間復(fù)雜度是Θ(M1M2NpNgrid)。雖然MPOA算法采用混合粒子群算法,其時間復(fù)雜度相對較高,但是MPOA算法只需要在Sink節(jié)點部署前進(jìn)行一次計算,且可事先通過計算機(jī)完成,再將最優(yōu)移動方案通過無線、串口等方式傳輸給Sink節(jié)點,因此MPOA算法對時間復(fù)雜度的要求不高。

3 算法仿真

3.1 仿真參數(shù)選擇

根據(jù)上述算法分析,在算法仿真中,采用MATLAB2014a仿真軟件,選擇以下參數(shù)計算Sink節(jié)點的移動路徑和網(wǎng)絡(luò)生存時間:監(jiān)測區(qū)域的長和寬均為200 m,變異因子b1為0.5,變異因子b2為0.5,粒子個數(shù)為40,迭代次數(shù)為100,傳感節(jié)點的感知數(shù)據(jù)速率Si為1 000 bit/s,傳感節(jié)點接收單位bit數(shù)據(jù)的能耗Er為50×10-9J/bit,傳感節(jié)點發(fā)送單位bit數(shù)據(jù)的能耗系數(shù)ε為100×10-12J/(bit·m2),初始能量Einital為1 000 J,網(wǎng)格大小為20×20。

3.2 仿真結(jié)果分析

選擇圓環(huán)厚度r集合{10 m,20 m,30 m,40 m,50 m},Sink節(jié)點的停留位置個數(shù)num(P)集合{4,8,12,16,20}和移動路程Lenth(P)集合{100 m,200 m,300 m,400 m,500 m,600 m}中任一元素,計算網(wǎng)絡(luò)生存時間最優(yōu)值和其移動路徑,并以某一參數(shù)的仿真結(jié)果為例說明MPOA算法的性能特點。

首先,分析MPOA算法的性能特點。選擇迭代次數(shù)200,r=10 m,num(P)=12,Lenth(P)=400 m和3.1節(jié)內(nèi)其他參數(shù),計算每次迭代的網(wǎng)絡(luò)生存時間,獲得MPOA算法的收斂圖(圖7)、Sink節(jié)點的移動路徑圖(圖8)和網(wǎng)格的單位節(jié)點能耗圖(圖9)。如圖7所示,當(dāng)?shù)螖?shù)小于80時,MPOA算法根據(jù)與最優(yōu)極值粒子的交叉和變異、路徑修正等操作,不斷尋找最優(yōu)值,其網(wǎng)絡(luò)生存時間不斷增加。當(dāng)?shù)螖?shù)大于80時,MPOA算法尋找到最優(yōu)值,其網(wǎng)絡(luò)生存時間收斂于最優(yōu)值,因此MPOA算法是收斂的。

圖7 MPOA算法的收斂圖

如圖8所示,Sink節(jié)點的移動路徑圍繞監(jiān)測區(qū)域的中心位置(100 m,100 m),在每一個方向上尋找到一個較優(yōu)的停留位置,形成類似圓的移動路徑。該移動路徑分散在監(jiān)測區(qū)域的各個方向,達(dá)到平衡網(wǎng)絡(luò)負(fù)載和提高網(wǎng)絡(luò)生存時間的效果。

圖8 Sink節(jié)點的移動路徑圖

圖9 網(wǎng)格的單位節(jié)點能耗圖

當(dāng)Sink節(jié)點沿著如圖8所示的移動路徑移動收集傳感節(jié)點的數(shù)據(jù)時,MPOA算法計算Sink節(jié)點在每一個停留位置時每一個網(wǎng)格的單位節(jié)點能耗,累加每一個網(wǎng)格的12個單位節(jié)點能耗,獲得單位節(jié)點能耗圖(圖9)。如圖9所示,Sink節(jié)點移動路徑內(nèi)網(wǎng)格單位節(jié)點能耗基本相同,呈圓柱狀分布。該能耗分布沒有出現(xiàn)某個網(wǎng)絡(luò)單位節(jié)點能耗異常突出的情況,可平衡網(wǎng)格單位節(jié)點能耗,從而提高了網(wǎng)絡(luò)生存時間。

其次,以固定常數(shù)的移動路程或Sink節(jié)點的停留位置個數(shù)為例,分析另一參數(shù)對網(wǎng)絡(luò)生存時間的影響。選擇Sink節(jié)點的停留位置個數(shù)為12和3.1節(jié)中仿真參數(shù),計算網(wǎng)絡(luò)生存時間,獲得仿真結(jié)果(圖10)。如圖10所示,當(dāng)移動路程為100 m,200 m和300 m時,不管r的取值,其網(wǎng)絡(luò)生存時間隨著移動路程的增加而增加。當(dāng)移動路程為400 m時,與移動路程為300 m的網(wǎng)絡(luò)生存時間比較,除了r=40 m時,其他網(wǎng)絡(luò)生存時間增加。當(dāng)移動路程為500 m和600 m時,與移動路程為400 m的網(wǎng)絡(luò)生存時間比較,r=10 m,20 m和40 m時的網(wǎng)絡(luò)生存時間略微增加,r=30 m時的網(wǎng)絡(luò)生存時間略微減少,r=50 m時的網(wǎng)絡(luò)生存時間起伏,即其網(wǎng)絡(luò)生存時間在某一個參數(shù)值間起伏變化?？傊?當(dāng)移動路程較少時,其網(wǎng)絡(luò)生存時間隨著移動路程的增加而增加。當(dāng)移動路程大于閾值時,隨著r的增加,其網(wǎng)絡(luò)生存時間在某一個值上下起伏。這是因為,當(dāng)移動路程較少時,Sink節(jié)點靠近監(jiān)測區(qū)域的中心位置移動,限制了Sink節(jié)點移動的優(yōu)勢,當(dāng)移動路程增加時,擴(kuò)大了其移動范圍,較好平衡網(wǎng)格單位節(jié)點能耗,因此提高了網(wǎng)絡(luò)生存時間。當(dāng)移動路程達(dá)到一個閾值后,隨著移動路程的增加,Sink節(jié)點的停留位置有可能出現(xiàn)在監(jiān)測區(qū)域的邊界和4個頂點周圍,這提高了網(wǎng)格單位節(jié)點能耗,降低了網(wǎng)絡(luò)生存時間。因此合理的移動路程可較好提高網(wǎng)絡(luò)生存時間。

圖10 移動路程對網(wǎng)絡(luò)生存時間的影響

圖11 Sink節(jié)點的停留位置個數(shù)對網(wǎng)絡(luò)生存時間的影響

選擇移動路程400 m和3.1節(jié)中仿真參數(shù),獲得仿真結(jié)果圖(圖11)。如圖11所示,當(dāng)Sink節(jié)點的停留位置個數(shù)為4,8和12時,不管r的取值,隨著停留位置個數(shù)的增加,網(wǎng)絡(luò)生存時間增加。當(dāng)Sink節(jié)點的停留位置個數(shù)為16和20時,其網(wǎng)絡(luò)生存時間與Sink節(jié)點的停留位置個數(shù)12時的網(wǎng)絡(luò)生存時間相差不大。這是因為,停留位置個數(shù)過少,平衡網(wǎng)絡(luò)能耗的效果不理想,當(dāng)停留位置個數(shù)達(dá)到一定的值后,其移動路徑范圍內(nèi)的網(wǎng)格單位節(jié)點能耗基本相同,停留位置個數(shù)的增加反而略微提高或降低了網(wǎng)格的單位節(jié)點能耗,因此合理數(shù)量的停留位置個數(shù)可較好平衡網(wǎng)格單位節(jié)點能耗,提高網(wǎng)絡(luò)生存時間。

最后,比較Circle[14],Rect,Rand和MPOA算法的網(wǎng)絡(luò)生存時間。其中,Circle是以監(jiān)測區(qū)域中心位置為圓心,周長為移動路程Lenth(P)的圓。Rect是以監(jiān)測區(qū)域中心位置為中心點,周長為Lenth(P)的正方形。Rand是40個隨機(jī)路徑的網(wǎng)絡(luò)生存時間平均值。根據(jù)上述分析,選擇移動路程400 m和Sink節(jié)點的停留位置個數(shù)12,獲得仿真結(jié)果圖(圖12)。如圖12所示,MPOA算法的網(wǎng)絡(luò)生存時間最優(yōu)。當(dāng)r值為10 m,20 m和30 m值,MPOA算法的網(wǎng)絡(luò)生存時間略微大于Circle、Rect和Rand算法。當(dāng)r值為40 m和50 m時,MPOA算法的網(wǎng)絡(luò)生存時間明顯提高,遠(yuǎn)大于其他算法。這是因為,當(dāng)r值較少時,MPOA算法的最優(yōu)移動路徑類似圓,其網(wǎng)絡(luò)生存時間略大于Circle算法,當(dāng)r值較大時,多數(shù)網(wǎng)格到Sink節(jié)點的跳數(shù)是1～2跳,此時Circle和Rect算法中,周長為400 m的移動路徑上部分停留位置到監(jiān)測區(qū)域的邊界小于r,此停留位置不能較好平衡網(wǎng)絡(luò)能耗。Rand算法基本不考慮r值的變化,其移動路徑較差。MPOA算法可根據(jù)r值自動尋找到最優(yōu)路徑,因此MPOA算法的網(wǎng)絡(luò)生存時間大于Circle、Rect和Rand算法。

圖12 網(wǎng)絡(luò)生存時間比較圖

4 總結(jié)

考慮均勻分布的傳感節(jié)點和Sink節(jié)點的多跳數(shù)據(jù)收集,提出一種無線傳感網(wǎng)的Sink節(jié)點移動路徑規(guī)劃算法。首先,該算法將Sink節(jié)點的數(shù)據(jù)收集范圍分解成多個圓環(huán)和內(nèi)圓,將監(jiān)測區(qū)域分解成多個網(wǎng)格。其次,考慮Sink節(jié)點在某一個位置上停留,采用數(shù)學(xué)公式表示每一個網(wǎng)格的單位節(jié)點能耗,從而獲得Sink節(jié)點移動下的網(wǎng)絡(luò)生存時間優(yōu)化模型。接著,采用混合粒子群算法求解該優(yōu)化模型,獲得網(wǎng)絡(luò)生存時間最優(yōu)值和其移動路徑。最后給出算法的仿真參數(shù),仿真說明MPOA算法的有效性,Sink節(jié)點的移動路程和停留位置個數(shù)對網(wǎng)格生存時間的影響,仿真比較Circle,Rect,Rand和MPOA算法的網(wǎng)絡(luò)生存時間。

總之,當(dāng)傳感節(jié)點均勻分布時,MPOA算法只需要根據(jù)監(jiān)測區(qū)域的形狀,可尋找到Sink節(jié)點的最優(yōu)移動路徑,從而平衡網(wǎng)絡(luò)能耗,提高網(wǎng)絡(luò)生存時間。但是MPOA算法只是考慮傳感節(jié)點均勻分布的情況,沒有考慮傳感節(jié)點存在空洞、泊松分布等非均勻分布情況,因此下一階段目標(biāo)是考慮傳感節(jié)點存在空洞、泊松分布等非均勻分布情況,研究Sink節(jié)點移動的網(wǎng)絡(luò)生存時間優(yōu)化模型和Sink節(jié)點的最優(yōu)移動路徑。

[1] Zhu C S,Shu L,Hara T,et al. A Survey on Communication and Data Management Issues in Mobile Sensor Networks[J]. Wireless Communications and Mobile Computing,2014,14(1):19-36.

[2] 高潔,吳延紅,白建俠,等. 無線傳感器網(wǎng)絡(luò)最小覆蓋能量優(yōu)化算法[J]. 傳感技術(shù)學(xué)報,2016,29(9):1435-1440.

[3] Tunca C,Isik S,Donmez M Y,et al. Distributed Mobile Sink Routing for Wireless Sensor Networks:A Survey[J]. IEEE Communications Surveys and Tutorials,2014,16(2):877-897.

[4] Wichmann A,Korkmaz T. Smooth Path Construction and Ddjustment for Multiple Mobile Sinks in Wireless Sensor Networks[J]. Computer Communications,2015,72(72):93-106.

[5] Kumar A K,Sivalingam K M,Kumar A. On Reducing Delay in Mobile Data Collection Based Wireless Sensor Networks[J]. Wireless Network,2013,19(3):285-299.

[6] 王章權(quán),陳友榮,尉理哲,等. 優(yōu)化網(wǎng)絡(luò)生存時間的Sink節(jié)點移動路徑選擇算法[J]. 傳感技術(shù)學(xué)報,2014,27(3):80-87.

[7] 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(2):128-143.

[8] Ghosh N,Banerjee I. An Energy-Efficient Path Determination Strategy for Mobile Data Collectors in Wireless Sensor Network[J]. Computers and Electrical Engineering,2015,48(10):417-435.

[9] 郜帥,張宏科. 時延受限傳感器網(wǎng)絡(luò)移動Sink路徑選擇方法研究[J]. 電子學(xué)報,2011,39(4):742-747.

[10] 郭劍,孫力娟,許文君,等. 基于移動Sink的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案[J]. 通信學(xué)報,2012,33(9):176-184.

[11] 汪林云,劉文軍. 無線傳感器網(wǎng)絡(luò)中帶有移動匯點的能量高效的數(shù)據(jù)收集協(xié)議[J]. 傳感技術(shù)學(xué)報,2012,25(5):678-682.

[12] Salarian H,Chin K W,Naghdy F. An Energy-Efficient Mobile-Sink Path Selection Strategy for Wireless Sensor Networks[J]. IEEE Transactions on Vehicular Technology,2014,63(5):2407-2419.

[13] Lee K,Kim Y H,Kim H J,et al. A Myopic Mobile Sink Migration Strategy for Maximizing Lifetime of Wireless Sensor Networks[J]. Wireless Networks,2014,20(2):303-318.

[14] Huang R,Gergely V Z. Static Path Planning for Mobile Beacons to Localize Sensor Networks[C]//Proceedings of the Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops. 2007:323-330.

StudyontheMovementPathOptimizationAlgorithmofSinkNodeforWirelessSensorNetworks*

CHENYourong1,2*,LUSiyi2,RENTiaojuan1,2,YANGHaibo1

(1.College of Information Science and Technology,Zhejiang Shuren University,Hangzhou 310015,China;2.School of Information Science and Engineering,Changzhou University,Changzhou Jiangsu 213164,China)

To find the optimal movement path of Sink node and maximum network lifetime when sensor nodes were uniformly distributed,movement path optimization algorithm(MPOA)of Sink node for mobile sensor networks was proposed. In the MPOA algorithm,data collection range of Sink node was divided into multiple rings,and the monitoring area was divided into multiple grids. According to positions of Sink node and multi-hop communication,unit node energy consumption of each grid was expressed by mathematical formula,and network lifetime optimization model with mobile Sink node was obtained. Modified hybrid particle swarm optimization algorithm was adopted to solve the optimization model. Optimal scheme of network lifetime,sojourn positions and movement path of Sink node was obtained. Simulation results show that MPOA algorithm can find the optimal movement path of Sink node,balance network energy consumption and prolong network lifetime. Under certain conditions,MPOA algorithm outperforms Circle,Rect and Rand algorithms.

mobile sensor networks;mobile Sink node;path optimization;particle swarm optimization

10.3969/j.issn.1004-1699.2017.12.025

項目來源:國家自然科學(xué)基金項目(61501403);浙江省自然科學(xué)基金項目(LY15F030004);浙江省公益性技術(shù)應(yīng)用研究計劃項目(2016C33038,LGF18F010005);浙江省重大科技專項計劃項目(2015C01033)

2017-04-29修改日期2017-08-09

TP393

A

1004-1699(2017)12-1933-08

陳友榮(1982-),男,博士,浙江蒼南人,浙江樹人大學(xué)信息科技學(xué)院副教授,常州大學(xué)信息科學(xué)與工程學(xué)院碩士生導(dǎo)師,主要研究方向為無線傳感網(wǎng)、物聯(lián)網(wǎng)。