基于定向移動的水下傳感器網絡覆蓋算法

杜曉玉,李 輝,周 林

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

基于定向移動的水下傳感器網絡覆蓋算法

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

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

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

三維傳感器網絡;覆蓋;水下傳感器網絡;虛擬移動;定向虛擬力算法;感知圓球

1 概述

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

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

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

虛擬力算法因其靈活性和穩定性而成為目前的研究熱點,但是也存在其不足:(1)虛擬力算法需根據節點間距離計算區域中任意2個傳感器節點之間的虛擬力,計算量較大。(2)虛擬算法是一種位置的微調算法,需經過多次迭代計算調整才可以達到網絡覆蓋的最優化。

本文針對水下三維傳感器網絡設計定向移動的虛擬力覆蓋算法,在宏觀調控后,應用基于定向移動的虛擬力算法對節點位置進行微調,以提高無線傳感器網絡的覆蓋率。

2 虛擬力算法

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

圖1 虛擬力算法示意圖

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

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

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

3 水下傳感器網絡模型

結合水下三維傳感器網絡的特點,本文提出適用于水下三維空間的模型,如圖2所示。

圖2 水下傳感器網絡模型

該模型有以下特點:

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

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

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

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

(5)覆蓋算法在網絡初始化時執行,節點有充足的剩余能量移動到指定的位置。

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

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

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

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

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

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

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

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

圖3 僅受引力時節點移動示意圖

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

將定向移動的虛擬力算法應用在水下傳感器網絡中,節點僅可以在垂直方向自由移動,如圖4所示。

圖4 三維定向移動示意圖

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

節點所受的虛擬力為:

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

圖5 邊界受力分析

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

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

節點所受的虛擬合力為:

節點Si移動的距離為:

根據di的方向和大小可計算移動之后節點Si的坐標為:

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

5 算法描述

本文算法的描述如下:

輸入水下傳感器網絡節點數量n,節點的位置信息Si(xi,yi,zi)(i=1,2,…,n),節點的感知半徑r,加權值ωR,ωe

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

(1)初始化網絡,根據節點發送的信息統計每個節點的鄰居節點信息并計算到鄰居節點的距離。

(2)對網絡中第i個節點Si按式(2)～式(5)計算節點的虛擬力。

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

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

(5)計算本次優化計算節點移動的平均距離d_ave,若d_ave大于門限值dth,返回步驟(1)對網絡進行新的迭代優化。

6 仿真實驗

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

圖6為覆蓋率隨節點數量變化時,設定門限值dth為2 m,CFD算法與隨機分布時覆蓋率對比。由該圖可見,經過CFD算法優化之后三維監測區域的覆蓋率有明顯提高。

圖6 覆蓋率隨節點數量的變化

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

圖7 覆蓋率隨迭代次數的變化

圖8為網絡中節點在單次算法執行過程中平均移動距離的大小。由該圖可見,平均移動距離隨迭代次數的增加而減少,最后趨于平衡。這證明隨算法迭代次數的增加,網絡整體趨于穩定。

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

圖9為覆蓋率隨三維水下傳感器網絡部署區域的深度變化情況。無線傳感器節點隨機部署三維水下空間,水面區域固定為80×80 m2,水深在60 m～150 m內變化。由該圖可見,當水的深度增加時,網絡的覆蓋率提高較為明顯,這是因為水體較深時給節點提供了較大的移動空間。

圖9 覆蓋率隨水深的變化

7 結束語

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

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

[1] 孫力娟,劉林峰,杜曉玉,等.水聲傳感器網絡拓撲控制技術綜述[J].南京郵電大學學報:自然科學版, 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] 黃俊杰,孫力娟,王汝傳.基于虛擬勢場和覆蓋影響因子的三維傳感器網絡覆蓋增強算法[J].通信學報, 2010,31(9A):16-21.

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

[7] 王 雪,王 晟,馬俊杰.無線傳感器網絡絡布局的虛擬力導向微粒群優化策略[J].電子學報,2007, 35(11):2038-2042.

[8] 陶 丹,馬華東,劉 亮.基于虛擬勢場的有向傳感器網絡覆蓋增強算法[J].軟件學報,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

杜曉玉,李 輝,周 林.基于定向移動的水下傳感器網絡覆蓋算法[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

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

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

2014-03-18

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