基于定向移動的水下傳感器網(wǎng)絡(luò)覆蓋算法

杜曉玉,李 輝,周 林

(河南大學(xué)a.物理與電子學(xué)院;b.民生學(xué)院;c.計算機(jī)與信息工程學(xué)院,河南開封,475004)

基于定向移動的水下傳感器網(wǎng)絡(luò)覆蓋算法

杜曉玉a,李 輝b,周 林c

(河南大學(xué)a.物理與電子學(xué)院;b.民生學(xué)院;c.計算機(jī)與信息工程學(xué)院,河南開封,475004)

覆蓋率是衡量無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的重要指標(biāo)。為提高網(wǎng)絡(luò)覆蓋率,針對水下三維傳感器網(wǎng)絡(luò)模型,提出一種基于定向移動的虛擬力算法。將虛擬力簡化為節(jié)點只受鄰居節(jié)點的斥力作用,定義當(dāng)2個鄰居節(jié)點的感知圓球相切時,其位置為相對理想位置。節(jié)點所受虛擬力大小與節(jié)點移動到相對該鄰居的理想位置所需移動的距離成正比,而節(jié)點移動的距離與節(jié)點所受到的虛擬力的合力相關(guān)。實驗結(jié)果表明,該算法能有效地對水下傳感器網(wǎng)絡(luò)的布局進(jìn)行優(yōu)化,提高網(wǎng)絡(luò)覆蓋率。

三維傳感器網(wǎng)絡(luò);覆蓋;水下傳感器網(wǎng)絡(luò);虛擬移動;定向虛擬力算法;感知圓球

1 概述

地球表面約71%被各類水體(河流、沼澤、湖泊、海洋等)覆蓋,各類水體能提供未來人類生存所需的食品、原料和生活發(fā)展空間,將成為人類可持續(xù)發(fā)展的物質(zhì)基礎(chǔ)[1]。隨著無線傳感器網(wǎng)絡(luò)的迅猛發(fā)展,水下傳感器網(wǎng)絡(luò)也受到越來越多的關(guān)注?；谔摂M力的網(wǎng)絡(luò)覆蓋算法由文獻(xiàn)[2]提出,文獻(xiàn)[3]將虛擬力算法應(yīng)用在無線傳感器網(wǎng)絡(luò)中,有限數(shù)量的傳感器節(jié)點隨機(jī)拋灑二維空間中,虛擬力算法假定節(jié)點之間存在引力和斥力2種虛擬力,虛擬力的大小和節(jié)點之間的距離相關(guān)。通過計算節(jié)點所受虛擬力的合力,確定節(jié)點移動的方向及移動的距離,重置節(jié)點的位置。經(jīng)過多次迭代計算使傳感器網(wǎng)絡(luò)的覆蓋面積達(dá)到最大化。

近幾年國內(nèi)外學(xué)者對虛擬力覆蓋算法做了大量的研究[4-7],文獻(xiàn)[4-5]對虛擬力算法進(jìn)行修改,文獻(xiàn)[4]修改了虛擬力的表達(dá)式,節(jié)點之間的虛擬力與兩點間的距離為線性關(guān)系。文獻(xiàn)[5]將節(jié)點所受的虛擬力限制在門限距離以內(nèi),對距離較遠(yuǎn)的節(jié)點所作用的虛擬力忽略不計,從而降低了算法的時間復(fù)雜度。文獻(xiàn)[6]結(jié)合虛擬力算法和差分算法,提出一種解決異構(gòu)移動無線傳感器網(wǎng)絡(luò)覆蓋的虛擬力導(dǎo)向差分優(yōu)化算法。該算法以網(wǎng)絡(luò)的有效覆蓋率為優(yōu)化目標(biāo),通過異構(gòu)節(jié)點間的虛擬力影響差分算法的位置向量更新過程,提高算法收斂速度。該算法既避免了虛擬力算法導(dǎo)致的網(wǎng)絡(luò)覆蓋率振蕩,又使差分算法有目的地向擴(kuò)大網(wǎng)絡(luò)覆蓋率的目標(biāo)進(jìn)化。文獻(xiàn)[7]結(jié)合虛擬力算法和微粒群算法,提出一種面向無線傳感器網(wǎng)絡(luò)布局的虛擬力導(dǎo)向微粒群優(yōu)化策略。該策略通過無線傳感節(jié)點間的虛擬力影響微粒群算法的速度更新過程,指導(dǎo)微粒進(jìn)化,加快算法收斂。

文獻(xiàn)[8-9]將基本的有向感知模型擴(kuò)展為方向可調(diào)感知模型,研究有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)問題。假定傳感器節(jié)點的位置不變化,但方向可調(diào),在此基礎(chǔ)上,分析了有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)問題。該算法把傳感節(jié)點的感知范圍用一個“質(zhì)心”點來替代,質(zhì)心是質(zhì)點系中一個特定的點,它與物體的平衡、運動以及內(nèi)力分布密切相關(guān)。傳感器節(jié)點的位置不變,其傳感方向的不斷調(diào)整可近似地看作是扇形感知區(qū)域的質(zhì)心點繞傳感器節(jié)點作圓周運動。將待解決問題轉(zhuǎn)化為質(zhì)心均勻分布問題,質(zhì)心在虛擬力作用下作擴(kuò)散運動,逐步消除網(wǎng)絡(luò)中感知重疊區(qū)和盲區(qū),增強(qiáng)整個網(wǎng)絡(luò)覆蓋性能。

虛擬力算法因其靈活性和穩(wěn)定性而成為目前的研究熱點,但是也存在其不足:(1)虛擬力算法需根據(jù)節(jié)點間距離計算區(qū)域中任意2個傳感器節(jié)點之間的虛擬力,計算量較大。(2)虛擬算法是一種位置的微調(diào)算法,需經(jīng)過多次迭代計算調(diào)整才可以達(dá)到網(wǎng)絡(luò)覆蓋的最優(yōu)化。

本文針對水下三維傳感器網(wǎng)絡(luò)設(shè)計定向移動的虛擬力覆蓋算法,在宏觀調(diào)控后,應(yīng)用基于定向移動的虛擬力算法對節(jié)點位置進(jìn)行微調(diào),以提高無線傳感器網(wǎng)絡(luò)的覆蓋率。

2 虛擬力算法

在傳感器網(wǎng)絡(luò)中,每一個傳感器可以看作其他傳感器節(jié)點的一個施力者,傳感器節(jié)點所受虛擬力可以分為引力和斥力2種。如果2個傳感器節(jié)點相距過近,即節(jié)點間距離小于某一門限值,它們之間的作用力為斥力,這可以確保傳感器節(jié)點之間不會過度集中而使得傳感器網(wǎng)絡(luò)的覆蓋率過低。相反如果2個節(jié)點之間的距離大于某一門限值,則2個節(jié)點之間存在引力作用,引力的作用可以使節(jié)點盡可能均勻地分布在部署區(qū)域中[3]。圖1為虛擬力算法的示意圖。

圖1 虛擬力算法示意圖

任意2個傳感器節(jié)點之間的虛擬力為:

其中,dij為節(jié)點Si和Sj之間的歐幾里得距離;dth為兩節(jié)點之間距離的門限值,由經(jīng)驗值取得;αij為節(jié)點Si到節(jié)點Sj直線的方位角;ωA和ωR為節(jié)點之間虛擬力的參數(shù)。門限值dth的大小可以控制多次迭代計算之后節(jié)點之間距離的大小。

如果無線傳感器節(jié)點的傳感模型為二元感知模型,感知半徑為r,當(dāng)相鄰2個節(jié)點之間的距離為2r時,2個節(jié)點的感知區(qū)域不重疊,這使得傳感器節(jié)點的利用率達(dá)到最大,但是會存在一些區(qū)域無法被覆蓋,無線傳感器網(wǎng)絡(luò)的覆蓋率較低。文獻(xiàn)[10]中給出證明當(dāng)d=3r時,二維平面中無線傳感器網(wǎng)絡(luò)為最優(yōu)的部署,此時為達(dá)到全覆蓋時節(jié)點間重疊的感知面積最小,因此,設(shè)定門限值時應(yīng)綜合考慮無線傳感器網(wǎng)絡(luò)的感知模型及網(wǎng)絡(luò)中節(jié)點部署的密集情況。傳感器節(jié)點的位置信息已知,并且可以自由的移動,節(jié)點根據(jù)所受的虛擬合力大小和方向確定移動的距離和移動的方向。

3 水下傳感器網(wǎng)絡(luò)模型

結(jié)合水下三維傳感器網(wǎng)絡(luò)的特點,本文提出適用于水下三維空間的模型,如圖2所示。

圖2 水下傳感器網(wǎng)絡(luò)模型

該模型有以下特點:

(1)水下傳感器節(jié)點同構(gòu),所有節(jié)點具有相同的感知節(jié)徑R,節(jié)點的覆蓋模型為二元感知覆蓋模型,傳感器的感知模型為球形;

(2)水面無線通信節(jié)點密集分布,且相互之間連通;

(3)覆蓋算法執(zhí)行之前,節(jié)點已準(zhǔn)確定位,節(jié)點位置已知[11];

(4)節(jié)點在水平面不可移動,但縱向可自由移動,并可以準(zhǔn)確移動到指定位置;

(5)覆蓋算法在網(wǎng)絡(luò)初始化時執(zhí)行,節(jié)點有充足的剩余能量移動到指定的位置。

假設(shè)節(jié)點部署在三維長方體空間中,節(jié)點位置服從均勻分布,空間中任意兩點之間的距離為空間兩點歐氏距離。相關(guān)定義如下:

定義1(感知圓球) 節(jié)點在空間的坐標(biāo)為(x,y,z),節(jié)點模型為感知半徑為R二元感知模型,則水下傳感器節(jié)點在三維空間中的覆蓋區(qū)域是一個圓心為(x,y,z),半徑為R的球體,稱為感知圓球。

定義2(鄰居節(jié)點) 節(jié)點Si和節(jié)點Sj之間的距離為dij,dij＜2R,則稱節(jié)點Si和節(jié)點Sj互為鄰居節(jié)點。

定義3(相對理想位置) 節(jié)點Sj為節(jié)點Si的鄰居節(jié)點,空間中一點為節(jié)點Si相對鄰居節(jié)點Sj的理想位置,其滿足以下2個特征:

(1)節(jié)點S可沿路徑移動至點i,并且在點時,節(jié)點Si的感知圓球與節(jié)點Sj的感知圓球相切。

(2)在節(jié)點Si的路徑上所有可以使節(jié)點Si的感知圓球與節(jié)點Sj的感知圓球相切的點中,點到節(jié)點Si的距離最短。

4 基于虛擬移動距離的水下三維覆蓋算法

通過仔細(xì)分析虛擬力算法的原理,不難發(fā)現(xiàn)虛擬力算法中虛擬力的大小與節(jié)點的距離密切相關(guān),圖3為一種簡單的傳感器部署情況,即區(qū)域中只有2個傳感器節(jié)點,此時兩節(jié)點之間虛擬力表現(xiàn)為引力作用,兩節(jié)點相向移動,直至移動至門限值位置,如圖3(b)所示。

圖3 僅受引力時節(jié)點移動示意圖

此時節(jié)點的移動對網(wǎng)絡(luò)覆蓋率沒有任何積極的影響,因此,本文對虛擬力算法做改進(jìn),并提出基于定向移動的覆蓋算法(CFD),在該算法中:(1)節(jié)點之間只存在斥力作用,不存在引力作用;(2)僅節(jié)點間距離小于門限值的2個節(jié)點之間存在虛擬力作用,大于門限值的節(jié)點之間虛擬力為0。

將定向移動的虛擬力算法應(yīng)用在水下傳感器網(wǎng)絡(luò)中,節(jié)點僅可以在垂直方向自由移動,如圖4所示。

圖4 三維定向移動示意圖

若2個節(jié)點的感知圓球相交,即dij＜2r,節(jié)點Si移動Δdij距離之后,節(jié)點Si與節(jié)點Sj的感知圓球相切:

節(jié)點所受的虛擬力為:

其中,ωR是加權(quán)值,可根據(jù)經(jīng)驗值來設(shè)定;α為方向矢量,值為(0 01),表示z軸正方向。由于沒有考慮節(jié)點間的虛擬引力作用,算法中必須考慮邊界斥力的作用,當(dāng)節(jié)點到邊界的距離小于感知半徑r時,節(jié)點受到邊界的斥力作用,但僅限上下邊界的斥力作用,如圖5所示。

圖5 邊界受力分析

節(jié)點Si到上邊界的距離為diu,diu＜r,節(jié)點受到上邊界的斥力為:

若邊界為下邊界,則節(jié)點所受到的斥力為:

節(jié)點所受的虛擬合力為:

節(jié)點Si移動的距離為:

根據(jù)di的方向和大小可計算移動之后節(jié)點Si的坐標(biāo)為:

按照節(jié)點ID號依次計算每個節(jié)點所需移動的距離和方向,從而計算出節(jié)點的新位置坐標(biāo)信息。

5 算法描述

本文算法的描述如下:

輸入水下傳感器網(wǎng)絡(luò)節(jié)點數(shù)量n,節(jié)點的位置信息Si(xi,yi,zi)(i=1,2,…,n),節(jié)點的感知半徑r,加權(quán)值ωR,ωe

輸出節(jié)點的新的位置信息newSi(xi,yi,zi) (i=1,2,…,n)

(1)初始化網(wǎng)絡(luò),根據(jù)節(jié)點發(fā)送的信息統(tǒng)計每個節(jié)點的鄰居節(jié)點信息并計算到鄰居節(jié)點的距離。

(2)對網(wǎng)絡(luò)中第i個節(jié)點Si按式(2)～式(5)計算節(jié)點的虛擬力。

(3)按式(6)～式(7)計算節(jié)點Si所受到虛擬力的合力和所需移動的距離di。

(4)更新節(jié)點的位置信息,判斷節(jié)點是否為網(wǎng)絡(luò)中最后一個節(jié)點,否則返回步驟(2)。

(5)計算本次優(yōu)化計算節(jié)點移動的平均距離d_ave,若d_ave大于門限值dth,返回步驟(1)對網(wǎng)絡(luò)進(jìn)行新的迭代優(yōu)化。

6 仿真實驗

為驗證CFD算法的有效性,本文利用Matlab進(jìn)行仿真實驗。在實驗中,無線傳感器節(jié)點隨機(jī)分布在長寬高均為80 m的水下三維的部署區(qū)域中。部署節(jié)點的總數(shù)為N,節(jié)點的最大感知半徑R為20 m。

圖6為覆蓋率隨節(jié)點數(shù)量變化時,設(shè)定門限值dth為2 m,CFD算法與隨機(jī)分布時覆蓋率對比。由該圖可見,經(jīng)過CFD算法優(yōu)化之后三維監(jiān)測區(qū)域的覆蓋率有明顯提高。

圖6 覆蓋率隨節(jié)點數(shù)量的變化

圖7為覆蓋率隨迭代次數(shù)的變化。由該圖可見,當(dāng)節(jié)點數(shù)量較少時,覆蓋率增加較為明顯,這是因為水平面節(jié)點分布不均勻,節(jié)點較多時,節(jié)點移動的空間較少,覆蓋率增加不明顯。

圖7 覆蓋率隨迭代次數(shù)的變化

圖8為網(wǎng)絡(luò)中節(jié)點在單次算法執(zhí)行過程中平均移動距離的大小。由該圖可見,平均移動距離隨迭代次數(shù)的增加而減少,最后趨于平衡。這證明隨算法迭代次數(shù)的增加,網(wǎng)絡(luò)整體趨于穩(wěn)定。

圖8 平均移動距離隨迭代次數(shù)的變化

圖9為覆蓋率隨三維水下傳感器網(wǎng)絡(luò)部署區(qū)域的深度變化情況。無線傳感器節(jié)點隨機(jī)部署三維水下空間,水面區(qū)域固定為80×80 m2,水深在60 m～150 m內(nèi)變化。由該圖可見,當(dāng)水的深度增加時,網(wǎng)絡(luò)的覆蓋率提高較為明顯,這是因為水體較深時給節(jié)點提供了較大的移動空間。

圖9 覆蓋率隨水深的變化

7 結(jié)束語

針對水下三維傳感器網(wǎng)絡(luò)模型,本文提出一種適用于定向移動的虛擬力算法,該算法將虛擬力簡化為節(jié)點只受鄰居節(jié)點的斥力作用。通過定義2個鄰居節(jié)點的相對理想位置,計算傳感器節(jié)點相對每個鄰居節(jié)點的虛擬距離,從而計算出節(jié)點受到的虛擬力大小、計算節(jié)點所受虛擬力的矢量和節(jié)點實際移動的距離和方向,更新網(wǎng)絡(luò)中節(jié)點的位置。由實驗結(jié)果可以看出,本文算法可以有效提高三維傳感器網(wǎng)絡(luò)的覆蓋率。

下一步研究方向如下:(1)建立與節(jié)點數(shù)量和三維空間體積的方程,對網(wǎng)絡(luò)的整體部署做出估計,從而解決節(jié)點在局部達(dá)到最優(yōu)、網(wǎng)絡(luò)覆蓋率較低的問題。(2)設(shè)計二維水面的節(jié)點部署優(yōu)化算法,使二維平面的節(jié)點均勻分布,再對水下節(jié)點位置進(jìn)行優(yōu)化部署。

[1] 孫力娟,劉林峰,杜曉玉,等.水聲傳感器網(wǎng)絡(luò)拓?fù)淇刂萍夹g(shù)綜述[J].南京郵電大學(xué)學(xué)報:自然科學(xué)版, 2012,32(5):20-25.

[2] Howard A,Matari C M J,Sukhatme G S.Mobile Sensor NetworkDeploymentUsingPotentialFields:A Distributed,Scalable Solution to the Area Coverage Problem[M]//Asama H,Arai T,Fukuda T.Distributed AutonomousRoboticSystems5.Fukuoka,Japan: Springer,2002:299-308.

[3] Zou Yi,Chakrabarty K.Sensor Deployment and Target Localization Based on Virtual Forces[C]//Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications.San Francisco,USA: IEEE Press,2003:1293-1303.

[4] Yu Xiangyu,Huang Weipeng,Lan Junjian,et al.A Novel Virtual Force Approach for Node Deployment in Wireless Sensor Network[C]//Proceedings of the 8th International Conference on Distributed Computing in SensorSystems.Hangzhou,China:[s.n.],2012: 359-363.

[5] 黃俊杰,孫力娟,王汝傳.基于虛擬勢場和覆蓋影響因子的三維傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].通信學(xué)報, 2010,31(9A):16-21.

[6] 李 明,石為人.虛擬力導(dǎo)向差分算法的異構(gòu)移動傳感器網(wǎng)絡(luò)絡(luò)覆蓋策略[J].儀器儀表學(xué)報,2011,5(5): 1043-1050.

[7] 王 雪,王 晟,馬俊杰.無線傳感器網(wǎng)絡(luò)絡(luò)布局的虛擬力導(dǎo)向微粒群優(yōu)化策略[J].電子學(xué)報,2007, 35(11):2038-2042.

[8] 陶 丹,馬華東,劉 亮.基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].軟件學(xué)報,2007,18(5): 1152-1163.

[9] Xiao Fu,WangJing,SunLijuan,etal.Coverage Enhancement Strategy Based on Novel Perception and Co-evolution for Multimedia Sensor Networks[J]. Chinese Journal of Electronics,2013,22(1):135-140.

[10] Pompili D,Melodia T,Akyildiz I F.Three-dimensional and Two-dimensional Deployment Analysis for Underwater Acoustic Sensor Networks[J].Ad Hoc Networks, 2009,4(7):778-790.

[11] Mo L,Peng-Jun W,Frieder O.Coverage in Wireless Ad Hoc SensorNetworks[J].IEEETransactionson Computers,2003,52(6):753-763.

編輯 金胡考

Coverage Algorithm Based on Fixed-directional Movement for Underwater Sensor Network

DU Xiaoyua,LI Huib,ZHOU Linc
(a.School of Physics and Electronics;b.Minsheng College;c.College of Computer and Information Engineering, Henan University,Kaifeng 475004,China)

The coverage is a fundamental issue and an important indicator of the service quality in Wireless Sensor Network(WSN).For three-dimensional underwater sensor network model,an virtual force algorithm based on directional movement is proposed that simplifies virtual force as the repulsion force only by neighboring nodes.This paper defines the ideal position relatively of the two nodes’position while one of sensing spheres of two neighboring nodes is tangent to the other.Virtual force is proportional to the distance moved from original position to the ideal position.The movement distance is determined by the resultant of virtual force which acts on the node.Experimental results show that the algorithm can effectively optimize the layout of underwater sensor networks and improve the network’s coverage rate.

three dimensional sensor networks;coverage;underwater sensor networks;virtual movement;fixeddirectional virtual force algorithm;sensing sphere

杜曉玉,李 輝,周 林.基于定向移動的水下傳感器網(wǎng)絡(luò)覆蓋算法[J].計算機(jī)工程, 2015,41(2):76-80.

英文引用格式:Du Xiaoyu,Li Hui,Zhou Lin.Coverage Algorithm Based on Fixed-directional Movement for Underwater Sensor Network[J].Computer Engineering,2015,41(2):76-80.

1000-3428(2015)02-0076-05

:A

:TP393

10.3969/j.issn.1000-3428.2015.02.015

河南省教育廳科學(xué)技術(shù)研究基金資助重點項目(14B510024);河南大學(xué)科研基金資助項目(2013YBZR004)。

杜曉玉(1979-),女,講師,主研方向:無線傳感器網(wǎng)絡(luò)定位及覆蓋技術(shù),陣列信號處理;李 輝,助教、碩士;周 林,副教授、博士。

2014-03-18

:2014-05-08E-mail:dxy@henu.edu.cn