一種無線傳感網的Sink節點移動路徑規劃算法研究*

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

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

一種無線傳感網的Sink節點移動路徑規劃算法研究*

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

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

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

無線傳感網;移動Sink節點;路徑規劃;粒子群算法

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

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

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

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

1 算法原理

在MPOA算法中,假設:無線傳感網的長方形監測區域內存在多個傳感節點和1個Sink節點。當存在多個Sink節點時,將監測區域分成與Sink節點數量相同的子區域,每一個Sink節點負責其中一個子區域,則多個Sink節點的數據收集問題轉換成多個單一Sink節點的數據收集問題;監測區域內傳感節點均勻分布;Sink節點可移動到監測區域的任一位置;所有傳感節點的能量有限,且具有統一的通信范圍、初始節點能量等特點,是同構的傳感節點。雖然Sink節點的能量也有限,但是可通過人工方式進行更換。

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

圖1 Sink節點的數據收集

圖2 監測區域的網格劃分

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

1.1 優化模型的建立

令Sink節點的當前停留位置坐標為(xs,ys),網格中心i的位置坐標為(xi,yi)和監測區域的長和寬為(Lx,Ly),則經過Sink節點和網格中心i的直線方程為

(1)

Sink節點到網格中心i的有向射線與監測區域的邊界交點為(fx(xs,ys,xi,yi),fy(xs,ys,xi,yi)),即(xc,yc)。假設監測區域為長方形,則邊界交點坐標的計算方法如下:

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

當xs=xi且ys>yi時,則xc=xi,yc=0;

當xs=xi且ys

當xs>xi且ys=yi時,則xc=0,yc=yi;

當xs

當xs≠xi且ys≠yi時,則需要判斷該點出現在哪個三角形內。如圖3所示,如果xsxi,yi≤ysxi/xs時,則(xi,yi)在三角形2內,將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內,可得xc=(Ly-yi)(xs-xi)/(ys-yi)+xi,yc=Ly。如果xs>xi,ys(xi)/xs≤yi≤(ys-Ly)xi/xs+Ly時,則點(xi,yi)在三角形1內,可得xc=0,yc=-xi(ys-yi)/(xs-xi)+yi。

圖3 邊界交點的計算

根據直線與監測區域的邊界交點和Sink節點的多跳數據收集方式,計算邊界交點(xc,yc)經過網格中心i到Sink節點的最大跳數Ni,max為

(2)

式中:?x」表示大于或等于x的最小整數。計算網格中心i所在位置到Sink節點的跳數Ni為

(3)

Sink節點停留在某一個位置時,網格中心i的單位節點能耗由接收和發送該位置到邊界交點區域內傳感節點的單位時間能耗和該位置上發送自身數據的單位時間能耗組成,即為

(4)

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

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

(5)

則網絡生存時間為

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

(6)

式中:V表示所有網格中心集合,Einital表示初始能耗。根據上述分析,考慮Sink節點移動距離和停留位置個數有限,建立網絡生存時間的優化模型。

(7)

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

1.2 模型的求解

標準粒子群算法雖然可以求解優化模型(7),且操作簡單,但是隨著迭代次數的不斷增加,有可能收斂到局部最優解。混合粒子群算法摒棄了傳統粒子群算法中的通過跟蹤極值更新粒子群的方法,而是引入遺傳算法的交叉和變異操作,可較好的搜索最優解。因此采用修正的混合粒子群算法求解優化模型(7)。但是在模型求解過程中,如果盲目尋找Sink節點的停留位置,則仍容易陷入局部最優解,很難尋找到Sink節點的全局最優位置。因此,需要考慮Sink節點的停留位置選擇規則。

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

圖4 Sink節點停留在網格中心位置時的單位節點能耗分布圖

當Sink節點的停留位置個數為NP時,根據角度將監測區域分成NP個子區域,每一個子區域內只能出現一個Sink節點的停留位置。如圖5所示,將監測區域分成8個三角形子區域,每一個三角形中頂點為監測區域中心位置的角度數相同。修正混合粒子群算法的基本原理如下。

圖5 Sink節點停留位置選擇的子區域劃分圖

1.2.1 個體編碼

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

1.2.2 適應度值

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

(8)

1.2.3 交叉操作

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

1.2.4 變異操作

產生一個[0 1]區間內均勻分布的隨機數。當該隨機數小于變異因子b1時,該粒子發生變異,計算粒子中元素到監測區域中心位置的平均距離dave,對粒子中每一個元素進行以下變異操作:產生一個[0 1]區間內均勻分布的隨機數,當該隨機數小于變異因子b2時,在該元素所在的子區域內,產生到監測區域中心位置距離在區間[0.6dave,1.4dave]內均勻分布的隨機位置,替換原來元素。

1.2.5 路徑修正操作

當粒子的移動路徑長度超過允許的最大移動路程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中所有元素的橫坐標,Py表示移動路徑P中所有元素的縱坐標。Lx和Ly分別表示監測區域的長和寬。

圖6 MPOA算法的工作流程圖

2 算法實現

如圖6所示,MPOA算法的具體實現步驟如下:

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

步驟2 初始化粒子群。將監測區域分成NP個子區域,并重復執行M2次以下操作可獲得初始粒子群:在每一個子區域內隨機產生一個Sink節點的停留位置,構成具有Np個停留位置的粒子。當該粒子的移動路徑長度超過允許的最大移動路程LP時,通過式(9)和式(10)執行路徑修正操作;

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

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

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

步驟6m1=m1+1,如果m1大于M1,則結束算法,輸出最優移動路徑和最大網絡生存時間,否則跳到步驟3。

循環執行關鍵步驟3～6,則可獲得優化模型(7)的一個最優解,即Sink節點的最優停留位置和移動路徑,從而達到提高網絡生存時間的目的。

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

3 算法仿真

3.1 仿真參數選擇

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

3.2 仿真結果分析

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

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

圖7 MPOA算法的收斂圖

如圖8所示,Sink節點的移動路徑圍繞監測區域的中心位置(100 m,100 m),在每一個方向上尋找到一個較優的停留位置,形成類似圓的移動路徑。該移動路徑分散在監測區域的各個方向,達到平衡網絡負載和提高網絡生存時間的效果。

圖8 Sink節點的移動路徑圖

圖9 網格的單位節點能耗圖

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

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

圖10 移動路程對網絡生存時間的影響

圖11 Sink節點的停留位置個數對網絡生存時間的影響

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

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

圖12 網絡生存時間比較圖

4 總結

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

總之,當傳感節點均勻分布時,MPOA算法只需要根據監測區域的形狀,可尋找到Sink節點的最優移動路徑,從而平衡網絡能耗,提高網絡生存時間。但是MPOA算法只是考慮傳感節點均勻分布的情況,沒有考慮傳感節點存在空洞、泊松分布等非均勻分布情況,因此下一階段目標是考慮傳感節點存在空洞、泊松分布等非均勻分布情況,研究Sink節點移動的網絡生存時間優化模型和Sink節點的最優移動路徑。

[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] 高潔,吳延紅,白建俠,等. 無線傳感器網絡最小覆蓋能量優化算法[J]. 傳感技術學報,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] 王章權,陳友榮,尉理哲,等. 優化網絡生存時間的Sink節點移動路徑選擇算法[J]. 傳感技術學報,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] 郜帥,張宏科. 時延受限傳感器網絡移動Sink路徑選擇方法研究[J]. 電子學報,2011,39(4):742-747.

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

[11] 汪林云,劉文軍. 無線傳感器網絡中帶有移動匯點的能量高效的數據收集協議[J]. 傳感技術學報,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

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

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

TP393

A

1004-1699(2017)12-1933-08

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