基于Dubins曲線的無線傳感網(wǎng)聚類移動(dòng)數(shù)據(jù)采集算法*

張美燕,蔡文郁

(1.浙江水利水電學(xué)院電氣工程系,杭州 310018;2.杭州電子科技大學(xué)電子信息學(xué)院,杭州 310018)

對(duì)于能量敏感的無線傳感器網(wǎng)絡(luò)而言,數(shù)據(jù)收集過程的低能耗性以及能量均衡性要求更加重要?；诠潭⊿ink節(jié)點(diǎn)的靜止數(shù)據(jù)采集方式容易造成網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗不均衡,從而使得整體網(wǎng)絡(luò)過早地失效,基于移動(dòng)Sink節(jié)點(diǎn)的移動(dòng)數(shù)據(jù)采集方式可以用移動(dòng)Sink的有序巡航采集來彌補(bǔ)傳感器節(jié)點(diǎn)的能量消耗[1-3]。因此利用類車型Sink節(jié)點(diǎn)實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)的移動(dòng)數(shù)據(jù)采集,可以提高網(wǎng)絡(luò)的能耗均衡性,從而有效延長網(wǎng)絡(luò)生命周期。

近幾年來,無線傳感器網(wǎng)絡(luò)移動(dòng)Sink數(shù)據(jù)采集方式得到了研究[4-8]。陳友榮等人[4]提出了移動(dòng)無線傳感網(wǎng)的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法:Sink節(jié)點(diǎn)采用分布式最短路徑樹算法收集k+1跳通信范圍內(nèi)傳感節(jié)點(diǎn)的相關(guān)信息和感知數(shù)據(jù),根據(jù)停留次數(shù)、合力大小和方向等信息計(jì)算當(dāng)前網(wǎng)格中心的停留時(shí)間和下一個(gè)停留網(wǎng)格中心。陳友榮等人提出一種移動(dòng)傳感網(wǎng)的Sink節(jié)點(diǎn)移動(dòng)路徑規(guī)劃算法[5]:將Sink節(jié)點(diǎn)的數(shù)據(jù)收集范圍分解成多個(gè)圓環(huán),將監(jiān)測區(qū)域分解成多個(gè)網(wǎng)格,根據(jù)Sink節(jié)點(diǎn)的停留位置和多跳通信方式建立Sink節(jié)點(diǎn)移動(dòng)的網(wǎng)絡(luò)生存時(shí)間優(yōu)化模型。常捷等人[6]提出了基于最優(yōu)路徑的移動(dòng)Sink數(shù)據(jù)收集方案,根據(jù)最小權(quán)值啟發(fā)式算法得到匯聚節(jié)點(diǎn)的集合,然后求出移動(dòng)Sink的最佳駐留點(diǎn)集合。Kenneth等人[7]提出了MULE和SENMA兩種方法來實(shí)現(xiàn)單跳和多跳方式的移動(dòng)數(shù)據(jù)采集,并對(duì)傳感器節(jié)點(diǎn)構(gòu)成簇的劃分機(jī)制進(jìn)行了研究。我們前期研究提出了一種基于Bezier連續(xù)曲線的移動(dòng)Sink節(jié)點(diǎn)避障路徑規(guī)劃算法,主要針對(duì)障礙物躲避技術(shù)領(lǐng)域的研究。文獻(xiàn)[9-10]將連續(xù)的Dubins曲線規(guī)劃應(yīng)用于水下傳感器網(wǎng)絡(luò)中,針對(duì)水下傳感器網(wǎng)絡(luò)三維立體部署的特點(diǎn),將二維Dubins曲線擴(kuò)展到三維立體空間。

由于無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模一般都比較大,如果只考慮由某個(gè)或某幾個(gè)移動(dòng)Sink節(jié)點(diǎn)實(shí)現(xiàn)對(duì)所有傳感器節(jié)點(diǎn)的巡航數(shù)據(jù)采集,那么規(guī)劃的路線會(huì)非常復(fù)雜。而且,類車型移動(dòng)Sink節(jié)點(diǎn)的運(yùn)動(dòng)特征受到Kinematic約束的限制,普通的直線型路徑無法滿足高效移動(dòng)數(shù)據(jù)采集的實(shí)際需求。

針對(duì)以上問題,本文提出了一種基于聚類間Dubins曲線的移動(dòng)數(shù)據(jù)采集算法:整個(gè)無線傳感器網(wǎng)絡(luò)被劃分為多個(gè)聚類區(qū)間,聚類內(nèi)采用最小生成樹路由方法進(jìn)行無線多跳傳輸,聚類間按序規(guī)劃Dubins曲線進(jìn)行移動(dòng)數(shù)據(jù)采集,從而兼顧移動(dòng)數(shù)據(jù)采集路徑的平滑性與能耗優(yōu)化性。

1 問題描述

本文研究的無線傳感器網(wǎng)絡(luò)處于一個(gè)長寬為L×W的矩形監(jiān)測區(qū)域,N個(gè)同質(zhì)傳感器節(jié)點(diǎn)SN(Sensor Node)隨機(jī)部署。數(shù)據(jù)采集點(diǎn)DCP(Data Collection Point)根據(jù)自身位置與剩余能量從傳感器節(jié)點(diǎn)集中選舉出。普通傳感器節(jié)點(diǎn)將數(shù)據(jù)傳輸?shù)皆摼垲悈^(qū)域內(nèi)的數(shù)據(jù)采集點(diǎn),移動(dòng)Sink節(jié)點(diǎn)沿著特定的數(shù)據(jù)采集路徑從一個(gè)數(shù)據(jù)采集點(diǎn)到另一個(gè)數(shù)據(jù)采集點(diǎn)進(jìn)行傳感數(shù)據(jù)的收集。

如圖1所示,無線傳感器網(wǎng)絡(luò)被分為K=5個(gè)聚類區(qū)域,第k(k=1,…,K)個(gè)聚類區(qū)域內(nèi)有1個(gè)數(shù)據(jù)采集點(diǎn)DCPk和Nk-1個(gè)傳感器節(jié)點(diǎn)。以數(shù)據(jù)采集點(diǎn)為樹根,眾多傳感器節(jié)點(diǎn)通過最小生成樹構(gòu)造傳感數(shù)據(jù)多跳傳輸路徑,將各個(gè)傳感器節(jié)點(diǎn)的數(shù)據(jù)傳輸?shù)綌?shù)據(jù)采集點(diǎn)進(jìn)行緩存。當(dāng)移動(dòng)Sink節(jié)點(diǎn)靠近數(shù)據(jù)采集點(diǎn)時(shí),通過無線方式接收數(shù)據(jù)采集點(diǎn)緩存的聚類區(qū)域內(nèi)所有傳感器節(jié)點(diǎn)數(shù)據(jù),從而實(shí)現(xiàn)整個(gè)無線傳感器網(wǎng)絡(luò)的移動(dòng)數(shù)據(jù)采集。本文定義移動(dòng)Sink節(jié)點(diǎn)在數(shù)據(jù)采集點(diǎn)DCPk和DCPj之間的移動(dòng)曲線為Ckj,移動(dòng)曲線Ckj的長度為L(Ckj),則移動(dòng)Sink節(jié)點(diǎn)巡航整個(gè)無線傳感器網(wǎng)絡(luò)所有節(jié)點(diǎn)所行駛的路徑為:

(1)

圖1 無線傳感器網(wǎng)絡(luò)移動(dòng)數(shù)據(jù)采集框架

本文假設(shè)移動(dòng)Sink節(jié)點(diǎn)相對(duì)整個(gè)無線傳感器網(wǎng)絡(luò)而言,具有較為充足的能量,因此移動(dòng)數(shù)據(jù)采集算法設(shè)計(jì)的焦點(diǎn)主要在于降低無線傳感器網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)的能耗,同時(shí)提高網(wǎng)絡(luò)能耗的均衡性。

圖2 類車型移動(dòng)Sink節(jié)點(diǎn)運(yùn)動(dòng)模型

在直角坐標(biāo)系下,類車型移動(dòng)Sink節(jié)點(diǎn)的運(yùn)動(dòng)模型如圖2所示,假設(shè)Sink節(jié)點(diǎn)的位置為q(x,y,θ),前向速度為u,最小轉(zhuǎn)彎半徑為ρ,則類車型移動(dòng)Sink節(jié)點(diǎn)的運(yùn)動(dòng)方程[11]為:

(2)

類車型移動(dòng)Sink節(jié)點(diǎn)在一個(gè)周期T內(nèi)的運(yùn)動(dòng)軌跡長度為:

(3)

考慮到上述Kinematic約束[11],類車型移動(dòng)Sink節(jié)點(diǎn)必須沿著連續(xù)且平滑的軌跡進(jìn)行數(shù)據(jù)采集。Dubins路徑[11]考慮了類車型移動(dòng)Sink節(jié)點(diǎn)的轉(zhuǎn)彎半徑對(duì)Sink節(jié)點(diǎn)運(yùn)動(dòng)的影響,使用幾何方法討論了運(yùn)動(dòng)初始狀態(tài)和終止?fàn)顟B(tài)之間的最短曲線問題。典型Dubins曲線的6種規(guī)劃場景(LSL,RSR,RSL,LSR,RLR,LRL),其中L代表左轉(zhuǎn),R代表右轉(zhuǎn),S代表直線,如圖3所示。

圖3 Dubins曲線的6種場景(LSL/RSR/RSL/LSR/RLR/LRL)

2 基于Dubins曲線的移動(dòng)數(shù)據(jù)采集算法

本文提出的基于Dubins曲線的移動(dòng)數(shù)據(jù)采集算法主要包括以下幾個(gè)步驟:①借鑒LEACH(Low Energy Adaptive Clustering Hierarchy)分簇算法[12-13]的聚類思想將整個(gè)無線傳感器網(wǎng)絡(luò)劃分成多個(gè)聚類空間,但是采集數(shù)據(jù)點(diǎn)的選擇并沒有依據(jù)LEACH算法的簇頭選擇方案;②每個(gè)聚類空間根據(jù)近似質(zhì)心算法選取數(shù)據(jù)采集點(diǎn),其他傳感器節(jié)點(diǎn)作為普通節(jié)點(diǎn);③利用最小生成樹MST(Minimum Spanning Tree)[14]方法進(jìn)行聚類內(nèi)傳感數(shù)據(jù)收集;④各個(gè)聚類間按序規(guī)劃基于Dubins曲線的移動(dòng)數(shù)據(jù)采集路徑;⑤移動(dòng)Sink節(jié)點(diǎn)沿著規(guī)劃路徑進(jìn)行移動(dòng)數(shù)據(jù)采集。本文綜合選取了LEACH和MST等算法,主要是考慮到這些算法的通用性與魯棒性,就本文算法而言,也可以兼容其他更加復(fù)雜的分簇方法和數(shù)據(jù)多跳傳輸方法。

2.1 LEACH聚類劃分與數(shù)據(jù)采集點(diǎn)選取方法

圖4 LEACH聚類范圍內(nèi)數(shù)據(jù)采集點(diǎn)選取

2.2 基于最小生成樹的聚類內(nèi)節(jié)點(diǎn)傳感數(shù)據(jù)收集機(jī)制

根據(jù)最小生成樹建立的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是這些網(wǎng)絡(luò)節(jié)點(diǎn)之間成本最低的通信網(wǎng)絡(luò)結(jié)構(gòu)。聚類區(qū)間內(nèi)的傳感器節(jié)點(diǎn)間數(shù)據(jù)采集按照最小生成樹路由方式進(jìn)行數(shù)據(jù)傳輸,最小生成樹采用Prim算法[14]構(gòu)造,從而保證聚類內(nèi)多傳感器節(jié)點(diǎn)的最優(yōu)數(shù)據(jù)采集路徑。數(shù)據(jù)采集點(diǎn)收集聚類內(nèi)所有傳感器節(jié)點(diǎn)的數(shù)據(jù)后,先進(jìn)行緩存處理,直到移動(dòng)Sink節(jié)點(diǎn)尋訪到該數(shù)據(jù)采集點(diǎn)時(shí)將緩存數(shù)據(jù)進(jìn)行無線傳輸。采用MST方法構(gòu)建聚類內(nèi)的數(shù)據(jù)收集路徑,可以保證多跳數(shù)據(jù)傳輸?shù)哪芰績?yōu)化。

具有N=20個(gè)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)聚類內(nèi)采用MST構(gòu)造數(shù)據(jù)傳輸路徑,仿真結(jié)果如圖5所示。

圖5 基于最小生成樹的聚類內(nèi)數(shù)據(jù)傳輸路徑

2.3 基于二維Dubins曲線的聚類間移動(dòng)數(shù)據(jù)采集方法

無線傳感器網(wǎng)絡(luò)分成多個(gè)聚類區(qū)間后,聚類內(nèi)的數(shù)據(jù)采集點(diǎn)作為接收和緩存聚類內(nèi)所有傳感器節(jié)點(diǎn)的匯聚節(jié)點(diǎn),需要移動(dòng)Sink節(jié)點(diǎn)對(duì)它進(jìn)行數(shù)據(jù)采集。因此聚類間的移動(dòng)數(shù)據(jù)采集問題其實(shí)就是構(gòu)建一系列不同數(shù)據(jù)采集點(diǎn)之間的平滑Dubins曲線。

如圖6所示,RSL型Dubins曲線主要包括三段:

R、S、L,其中各種類型曲線的計(jì)算方式[11]如式(4)所示:

(4)

式中:Lγ,Rγ,Sγ分別為L、R、S3種曲線的運(yùn)算方式,γ為Dubins曲線中距離值為γ的區(qū)段。

圖6 Dubins曲線長度計(jì)算

從圖6可以計(jì)算得到RSL三段曲線的長度|L|、|R|、|S|,如式(5)所示,從而得到整個(gè)Dubins曲線的長度∮LRS=|L|+|R|+|S|[11]。移動(dòng)Sink節(jié)點(diǎn)沿著簇間數(shù)據(jù)采集點(diǎn)之間構(gòu)成的Dubins曲線,按序采集每個(gè)聚類區(qū)間內(nèi)的傳感器數(shù)據(jù)。

(5)

從上面的數(shù)學(xué)公式可知,Dubins曲線能夠滿足類車型移動(dòng)Sink節(jié)點(diǎn)的Kinematic約束。對(duì)于確定的聚類數(shù)量K以及聚類巡航數(shù)據(jù)采集順序,Dubins曲線的段數(shù)已經(jīng)確定,數(shù)據(jù)采集點(diǎn)的次序采用遺傳算法(GA)求解旅行商問題TSP(Traveling Salesman Problem)[15]的方法解決,Dubins曲線的出入角度可以根據(jù)文獻(xiàn)[11]的最優(yōu)方式組合進(jìn)行選取,從而盡量降低移動(dòng)Sink節(jié)點(diǎn)的巡航路徑消耗,提高數(shù)據(jù)采集的實(shí)時(shí)性。

4 仿真結(jié)果

4.1 仿真場景設(shè)置

圖7 Dubins曲線有限角度集(φ=λπ/3,λ=0,1,…,5)

本文采用類似于參考文獻(xiàn)[5]的場景設(shè)置,假設(shè)N=100無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署在長寬為L×W= 120×120 單元的正方形監(jiān)測區(qū)域,節(jié)點(diǎn)通信半徑為r=20 單元,類車型移動(dòng)Sink節(jié)點(diǎn)的最小轉(zhuǎn)彎半徑為10個(gè)單元。根據(jù)以上的場景設(shè)置,通過Monte Carlo數(shù)值仿真,可以統(tǒng)計(jì)出節(jié)點(diǎn)平均度數(shù)的分布在7～9左右,屬于連通性與覆蓋性較好的網(wǎng)絡(luò)節(jié)點(diǎn)分布。關(guān)于聚類數(shù)量的選擇,需要同時(shí)兼顧移動(dòng)Sink節(jié)點(diǎn)的路徑計(jì)算復(fù)雜度與聚類內(nèi)數(shù)據(jù)采集路徑的有效性。本文算法選取了聚類數(shù)量K=4和K=5兩種典型情況作為仿真比較,這兩種情況下的聚類內(nèi)節(jié)點(diǎn)平均數(shù)量大概為20～25,可以很好地兼顧以上兩個(gè)方面的因素。Dubins曲線的出入角度分為如圖7所示情況,為了降低迭代計(jì)算量,只選取了6種情況的可選擇角度。若大規(guī)模傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域尺寸遠(yuǎn)大于轉(zhuǎn)彎半徑,可以忽略非直線段數(shù)據(jù)采集曲線,本文算法從而退化為基于TSP模型的移動(dòng)Sink數(shù)據(jù)采集方法。與基于TSP模型的移動(dòng)Sink數(shù)據(jù)采集方法相比,本文方法在路徑的最短性上并不是最優(yōu)的,但是卻能保證類車型移動(dòng)Sink節(jié)點(diǎn)的Kinematic約束,這一點(diǎn)滿足了高效移動(dòng)數(shù)據(jù)采集的實(shí)際需求。

假設(shè)本文所研究的無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的初始能量設(shè)置為0.1 J,其能耗模型[16]定義如下:

(6)

(7)

為了簡單起見,傳感器節(jié)點(diǎn)能耗只考慮發(fā)送的能耗,忽略數(shù)據(jù)接收所產(chǎn)生的能耗。仿真采用周期輪數(shù)進(jìn)行時(shí)間維度上的表征,隨著仿真周期輪數(shù)的增長,傳感器節(jié)點(diǎn)的剩余能量會(huì)逐漸下降,直到某些傳感器節(jié)點(diǎn)因?yàn)槟芰亢谋M而失效。

3.2 仿真結(jié)果

利用LEACH聚類思想實(shí)現(xiàn)的不同聚類仿真結(jié)果(通過限定整體網(wǎng)絡(luò)的簇頭比例達(dá)到K=4和K=5的兩種不同聚類數(shù)量)如圖8所示,歸屬于同一個(gè)聚類的傳感器節(jié)點(diǎn)形狀相同,聚類中的數(shù)據(jù)采集點(diǎn)與其他傳感器節(jié)點(diǎn)用更大的相同形狀來區(qū)分。從圖8所示,聚類節(jié)點(diǎn)范圍分布較為均勻,區(qū)域空間聚類性明顯。聚類內(nèi)構(gòu)造MST路徑結(jié)果如圖9所示,基于 Dubins 曲線的類車型移動(dòng)Sink節(jié)點(diǎn)數(shù)據(jù)采集路徑如圖10所示,可見移動(dòng)Sink節(jié)點(diǎn)的數(shù)據(jù)采集路徑滿足類車型移動(dòng)Sink節(jié)點(diǎn)的Kinematic約束。

圖10 移動(dòng)Dubins曲線數(shù)據(jù)采集軌跡

圖8 無線傳感器網(wǎng)絡(luò)不同聚類結(jié)果

圖9 聚類內(nèi)MST構(gòu)造路徑結(jié)果

一般模型中假設(shè)Sink節(jié)點(diǎn)具有充足的能量[4-5],因此移動(dòng)Sink節(jié)點(diǎn)的能耗不計(jì)入網(wǎng)絡(luò)整體能耗。目前的移動(dòng)Sink節(jié)點(diǎn)數(shù)據(jù)收集方法一般都只考慮路徑長度、移動(dòng)速度等方面的最優(yōu)化,而本文算法保證了類車型移動(dòng)Sink節(jié)點(diǎn)的Kinematic約束。網(wǎng)絡(luò)能耗大小和能耗均衡性均與固定Sink節(jié)點(diǎn)方式進(jìn)行比較,傳感器節(jié)點(diǎn)通過MST生成樹將數(shù)據(jù)多跳傳輸至固定Sink節(jié)點(diǎn)。固定Sink節(jié)點(diǎn)放置于無線傳感器網(wǎng)絡(luò)的中心區(qū)域,坐標(biāo)為(60,60)。每輪仿真中隨機(jī)選取50%的傳感節(jié)點(diǎn)傳輸500 byte的數(shù)據(jù)到移動(dòng)Sink節(jié)點(diǎn),仿真采用多次運(yùn)行取結(jié)果平均值的方式進(jìn)行。網(wǎng)絡(luò)能耗大小表征如下:隨著仿真輪數(shù)的增長網(wǎng)絡(luò)所有傳感器節(jié)點(diǎn)的剩余能量平均值,剩余能量平均值曲線下降越平緩,說明無線傳感器網(wǎng)絡(luò)能耗性能越好。能量均衡性表征為500輪仿真之后網(wǎng)絡(luò)所有傳感器節(jié)點(diǎn)剩余能量的均方根值,剩余能量的均方值越小,說明無線傳感器網(wǎng)絡(luò)能耗均衡性越好。仿真結(jié)果比較分別如圖11(a)和11(b)所示。從圖11可以發(fā)現(xiàn),兩種場景下,K=5比K=4本文算法的能耗特性提升更為明顯,這是因?yàn)榫垲惙秶叫?聚類內(nèi)數(shù)據(jù)傳輸所經(jīng)過的路徑越短,由此所消耗的能量也越小。因此,本文設(shè)計(jì)的移動(dòng)數(shù)據(jù)采集算法與簇內(nèi)星型拓?fù)鋫鬏敽痛亻g星型拓?fù)鋫鬏數(shù)臄?shù)據(jù)采集方式相比較,網(wǎng)絡(luò)能耗明顯下降了,網(wǎng)絡(luò)能耗均衡性也得到了提高。

圖11 網(wǎng)絡(luò)數(shù)據(jù)采集能耗大小與均衡性比較

4 結(jié)語

論文提出了一種基于Dubins曲線的移動(dòng)數(shù)據(jù)采集算法,采用LEACH分簇將整個(gè)無線傳感器網(wǎng)絡(luò)劃分為多個(gè)聚類區(qū)間,聚類內(nèi)采用最小生成樹方法數(shù)據(jù)收集,聚類間按序規(guī)劃基于Dubins曲線的移動(dòng)數(shù)據(jù)采集路徑。仿真結(jié)果表明本文提出的算法可以在保證類車型移動(dòng)Sink節(jié)點(diǎn)路徑平滑連續(xù)的基礎(chǔ)上,降低傳感器節(jié)點(diǎn)的能耗,延長網(wǎng)絡(luò)生命壽命。后續(xù)工作將擴(kuò)展到多個(gè)移動(dòng)Sink節(jié)點(diǎn)條件下的優(yōu)化數(shù)據(jù)采集,同時(shí)考慮多種不同場景下的性能驗(yàn)證。