有向移動(dòng)傳感器網(wǎng)絡(luò)三維空間目標(biāo)自主覆蓋算法

譚 勵(lì),楊朝玉,楊明華,唐小江

(1.北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,北京 100068; 2.火箭軍裝備研究院,北京 100094)

0 概述

覆蓋問題是無線傳感器網(wǎng)絡(luò)領(lǐng)域研究中的重點(diǎn)之一,主要涉及部署環(huán)境、節(jié)點(diǎn)感知模型和部署算法等,通常需要對多個(gè)要素的綜合考慮才能實(shí)現(xiàn)傳感器網(wǎng)絡(luò)的全覆蓋。與常規(guī)二維平面環(huán)境下的部署問題相比,針對三維空間環(huán)境的部署問題雖然實(shí)現(xiàn)的復(fù)雜度大幅度增加,但更貼近于現(xiàn)實(shí)應(yīng)用環(huán)境,因此,研究工作也更有實(shí)際意義。近年來,各類危及社會(huì)公共安全的突發(fā)性事件頻繁發(fā)生,急需一種有效手段能夠第一時(shí)間獲取事故現(xiàn)場數(shù)據(jù)。例如對火災(zāi)地震等災(zāi)情的快速探測、對輪船飛機(jī)等大型載人設(shè)備發(fā)生事故后的人員搜救,處理此類具有突發(fā)性和破環(huán)性的事件對應(yīng)急反應(yīng)速度有極高的要求。空中傳感器網(wǎng)絡(luò)可以根據(jù)任務(wù)需要攜帶不同類型的傳感器模塊,以自主部署的形式在短時(shí)間內(nèi)完成對特定區(qū)域、特定目標(biāo)的全面覆蓋和信息采集,對于提高對突發(fā)事件的應(yīng)急處置能力具有重要意義。

空中有向傳感器網(wǎng)絡(luò)是由配備如攝像機(jī)、紅外等具有方向特性的傳感器模塊以及可自主留空飛行的傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò),針對其覆蓋問題主要的影響因素有節(jié)點(diǎn)感知方向、感知和通信距離、節(jié)點(diǎn)移動(dòng)帶來的能耗以及覆蓋目標(biāo)的特征。本文在此基礎(chǔ)上研究當(dāng)監(jiān)測對象為部署區(qū)域內(nèi)三維立體目標(biāo)時(shí)的均勻覆蓋問題。通過構(gòu)建空間目標(biāo)部署基準(zhǔn)曲面和提出不均衡虛擬勢場方法,得到傳感器節(jié)點(diǎn)的最優(yōu)部署路線和部署區(qū)域。

1 相關(guān)工作

近年來相關(guān)的研究工作主要集中在全向覆蓋、有向覆蓋和三維空間覆蓋3個(gè)方面。

1.1 全向覆蓋

文獻(xiàn)[1]提出了三維自部署(3D Self-Deployment,3DSD)算法,通過引入?yún)f(xié)商策略來確保網(wǎng)絡(luò)的連通性,同時(shí)使用密度控制策略用于平衡節(jié)點(diǎn)分布。該算法可在有障礙物的三維空間內(nèi)實(shí)現(xiàn)更快、更均勻的節(jié)點(diǎn)自動(dòng)化部署。文獻(xiàn)[2]認(rèn)為雖然全覆蓋對于無線傳感器網(wǎng)絡(luò)中監(jiān)測和監(jiān)控應(yīng)用非常重要,然而由于各種原因覆蓋空洞的出現(xiàn)是不可避免的,文中使用空心圓屬性評估方法識(shí)別出現(xiàn)的覆蓋空洞。文獻(xiàn)[3]根據(jù)節(jié)點(diǎn)密度采用分布式覆蓋盲區(qū)修復(fù)算法解決傳感器網(wǎng)絡(luò)中由于節(jié)點(diǎn)死亡造成的覆蓋問題。全向覆蓋研究從各角度考慮了對傳感器網(wǎng)絡(luò)覆蓋的性能優(yōu)化,但由于在算法和仿真中采用的是理想化的全向節(jié)點(diǎn)感知模型,因此未能考慮到傳感器感知視角的局限性對覆蓋結(jié)果造成的影響。

1.2 有向覆蓋

文獻(xiàn)[4]提出有向傳感器網(wǎng)絡(luò)中基于約束人工魚群的覆蓋增強(qiáng)算法,建立二維平面節(jié)點(diǎn)模型,引入“感知質(zhì)心”將其作為人工魚,通過模擬魚群高度覓食一致性行為在解空間中尋找最優(yōu)解。文獻(xiàn)[5]結(jié)合遺傳算法和模擬退火算法,提出一種多媒體有向傳感器網(wǎng)絡(luò)的覆蓋增強(qiáng)算法,在提高覆蓋率的同時(shí)降低了迭代計(jì)算次數(shù)。文獻(xiàn)[6]基于Voronoi圖和傳感器方向可調(diào)的特性,提出一種分布式貪婪算法,進(jìn)一步提高了有向傳感器網(wǎng)絡(luò)的有效區(qū)域覆蓋。文獻(xiàn)[7]討論區(qū)域內(nèi)監(jiān)視攝像機(jī)傳感器具有的有向感知性,總結(jié)有向傳感器的感知屬性和行為,基于柵欄覆蓋的研究成果給出解決方案。文獻(xiàn)[8]指出可視化傳感器網(wǎng)絡(luò)(Visual Sensor Network,VSN)中攝像機(jī)如何判斷其視域最大化覆蓋目標(biāo)是一個(gè)NP難問題,并提出分層算法,根據(jù)傳感器網(wǎng)絡(luò)規(guī)模的大小采用不同的集中式和分布式解決方案,對于有向覆蓋部署則采用有向節(jié)點(diǎn)感知模型,很好地考慮到傳感器節(jié)點(diǎn)的有向感知能力。文獻(xiàn)[9-11]是二維平面環(huán)境下的相關(guān)研究,尚未針對三維空間下的覆蓋部署作進(jìn)一步展開。

1.3 三維空間覆蓋

文獻(xiàn)[12]引入移動(dòng)傳感器網(wǎng)絡(luò)用以解決隨機(jī)空中部署的覆蓋問題,考慮到山區(qū)地形的物理特征,如斜率、高度、半徑,設(shè)計(jì)三維螺旋模型控制節(jié)點(diǎn)移動(dòng),實(shí)現(xiàn)節(jié)點(diǎn)在山區(qū)地形的全覆蓋。文獻(xiàn)[13]針對不規(guī)則地形建立一個(gè)數(shù)字估計(jì)模型(Digital Elevation Model,DEM),使用地區(qū)等高線估計(jì)相關(guān)區(qū)域的預(yù)計(jì)覆蓋率。上述研究考慮了實(shí)際環(huán)境對傳感器網(wǎng)絡(luò)部署的影響,從地形的角度構(gòu)建有針對性的節(jié)點(diǎn)部署模型,但都以全區(qū)域覆蓋為目的進(jìn)行考量,未針對監(jiān)測區(qū)域內(nèi)特殊目標(biāo)的覆蓋要求展開研究。

在實(shí)際應(yīng)用中,被監(jiān)測對象通常會(huì)是空間中的三維立體目標(biāo)[14],如一幢失火的樓房或一座發(fā)生雪崩的雪山,對于空中有向傳感器網(wǎng)絡(luò),如何快速高效地實(shí)現(xiàn)對三維立體目標(biāo)的全覆蓋,是實(shí)現(xiàn)災(zāi)情感知、人員救援的前提。根據(jù)現(xiàn)有資料表明,類似研究主要集中在全向覆蓋、二維有向覆蓋和區(qū)域覆蓋方面,針對有向移動(dòng)傳感器網(wǎng)絡(luò)對三維空間立體目標(biāo)表面的覆蓋部署問題,現(xiàn)有研究成果在節(jié)點(diǎn)模型、算法實(shí)現(xiàn)、計(jì)算復(fù)雜度等方面大多都有不適用性。

2 基于虛擬力的三維空間立體目標(biāo)覆蓋模型

針對覆蓋目標(biāo)為建筑物等立體目標(biāo),考慮到算法實(shí)時(shí)性強(qiáng)、復(fù)雜度低的現(xiàn)實(shí)需要,本文基于虛擬力方法提出一種三維空間下的立體目標(biāo)自主覆蓋方法,將有向移動(dòng)傳感器網(wǎng)絡(luò)自主部署過程轉(zhuǎn)化為節(jié)點(diǎn)在特定虛擬力場中受虛擬力作用而自主移動(dòng)、自主轉(zhuǎn)動(dòng)的過程。

2.1 有向傳感器節(jié)點(diǎn)感知模型

目前針對三維空間覆蓋的研究所采用的節(jié)點(diǎn)感知模型為三維全向感知模型,對節(jié)點(diǎn)的有向感知屬性普遍仍采用平面模型加以輔助說明。該方法不能很好地體現(xiàn)三維空間內(nèi)有向傳感器的部署情況。為此,本文建立面向三維空間環(huán)境的有向傳感器節(jié)點(diǎn)感知模型,參考節(jié)點(diǎn)質(zhì)心原理,以球體為節(jié)點(diǎn)框架,對傳感器節(jié)點(diǎn)以球心為基準(zhǔn)進(jìn)行移動(dòng)和視角變換。

設(shè)有向移動(dòng)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的感知范圍為一個(gè)圓錐體,節(jié)點(diǎn)位于圓錐體錐頂,感知范圍可以在空間平移,也可以以錐頂為中心進(jìn)行旋轉(zhuǎn),如圖1所示。

圖1 有向移動(dòng)傳感器節(jié)點(diǎn)感知模型

節(jié)點(diǎn)感知模型用一個(gè)八元組〈P,θ,C,Rattr,Rrep,CT,RT,S〉表示。其中:P表示三維空間中的有向移動(dòng)傳感器節(jié)點(diǎn)P的位置坐標(biāo);θ表示節(jié)點(diǎn)的有向傳感器的感知角度;Rattr表示節(jié)點(diǎn)最大通信距離,即節(jié)點(diǎn)間產(chǎn)生虛擬引力的最大距離;Rrep表示產(chǎn)生虛擬斥力的最大距離,Rout≤Rrep≤Rattr;Rout為外接球半徑,計(jì)算公式如式(1)所示;C表示節(jié)點(diǎn)P的感知范圍的外接球的球心坐標(biāo);CT表示被監(jiān)測的目標(biāo)的外接球球心;RT表示被監(jiān)測的大目標(biāo)的外接球半徑;S表示節(jié)點(diǎn)P的鄰居節(jié)點(diǎn)集合,所謂鄰居節(jié)點(diǎn)是指與節(jié)點(diǎn)P之間的距離小于等于最大通信距離Rattr的節(jié)點(diǎn)。

(1)

在部署過程中,節(jié)點(diǎn)之間根據(jù)距離的遠(yuǎn)近產(chǎn)生虛擬引力或者虛擬斥力或者沒有虛擬作用力。由于傳統(tǒng)虛擬力方法嚴(yán)格按牛頓定律定義,無法避免局部最小點(diǎn)問題,從而導(dǎo)致覆蓋漏洞的出現(xiàn)。事實(shí)上,構(gòu)建虛擬物理系統(tǒng)并不需要嚴(yán)格按物理理論進(jìn)行直接映射。本文根據(jù)有向移動(dòng)傳感器節(jié)點(diǎn)特點(diǎn)提出不均衡虛擬勢場的概念,每個(gè)節(jié)點(diǎn)產(chǎn)生獨(dú)立的不均衡虛擬勢場:以節(jié)點(diǎn)作為引力中心點(diǎn),以節(jié)點(diǎn)感知模型中外接球球心,作為斥力中心點(diǎn),即引力中心與斥力中心不重疊。由相互偏離的2個(gè)虛擬力中心點(diǎn)分別對其監(jiān)測對象和鄰近節(jié)點(diǎn)施加虛擬作用力,從而克服均衡虛擬勢場設(shè)計(jì)容易產(chǎn)生的覆蓋重疊和覆蓋空洞問題。不均衡虛擬勢場示例如圖2所示。

圖2 節(jié)點(diǎn)不均衡虛擬勢場分布示意圖

設(shè)當(dāng)前節(jié)點(diǎn)為Pn,節(jié)點(diǎn)Pn所有鄰居節(jié)點(diǎn)集合S={P1,P2,…},節(jié)點(diǎn)Pn對應(yīng)的外接球球心Cn,每一個(gè)鄰居節(jié)點(diǎn)對應(yīng)的外接球的球心集合C={C1,C2,…}。當(dāng)前節(jié)點(diǎn)Pn與每一鄰居節(jié)點(diǎn)Pm∈S之間的距離為:

(2)

當(dāng)前節(jié)點(diǎn)Pn的外接球球心Cn與每一鄰居節(jié)點(diǎn)Pm∈S的外接球的球心Cm之間的距離為:

(3)

對于節(jié)點(diǎn)的運(yùn)動(dòng)規(guī)律,本文采用近似牛頓運(yùn)動(dòng)定律重新定義節(jié)點(diǎn)的作用力方程。根據(jù)2個(gè)節(jié)點(diǎn)之間以及節(jié)點(diǎn)與監(jiān)測目標(biāo)之間的距離,以相距Rout、Rrep和Rattr作為分界線,分別計(jì)算當(dāng)節(jié)點(diǎn)遠(yuǎn)離監(jiān)測目標(biāo)時(shí)受到的虛擬引力、節(jié)點(diǎn)到達(dá)部署范圍時(shí)與其他節(jié)點(diǎn)之間的虛擬作用力以及節(jié)點(diǎn)進(jìn)入目標(biāo)內(nèi)區(qū)域時(shí)受到的虛擬斥力。當(dāng)前節(jié)點(diǎn)Pn的所有相鄰節(jié)點(diǎn)Pm∈S對節(jié)點(diǎn)Pn的虛擬力計(jì)算公式如下:

(4)

其中,krep、λrep為斥力系數(shù),kattr、λattr為引力系數(shù),α(n,m)為單位向量,分別表示由節(jié)點(diǎn)Pn指向鄰居節(jié)點(diǎn)Pm∈S的引力方向,以及由節(jié)點(diǎn)Pn的外接球球心Cn指向鄰居節(jié)點(diǎn)Pm∈S的外接球球心Cm的斥力方向。

節(jié)點(diǎn)Pn所受所有鄰居節(jié)點(diǎn)虛擬引力和斥力的合力計(jì)算公式如下:

(5)

2.2 三維空間立體目標(biāo)覆蓋模型

實(shí)際情況中三維空間立體目標(biāo)的體積和形狀存在多種情況,為了降低問題復(fù)雜度,本文將該目標(biāo)的覆蓋問題分解為對多個(gè)具有一定體積(少量有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)無法完成覆蓋)且表面積連續(xù)的單一目標(biāo)的覆蓋,如圖3所示。

圖3 三維空間立體目標(biāo)覆蓋模型

部署完畢后應(yīng)最大限度覆蓋目標(biāo)的表面積。設(shè)目標(biāo)的所有外凸點(diǎn)集合Sa={S1,S2,…,Sk},目標(biāo)的質(zhì)心為CT,計(jì)算公式如下:

(6)

其中,k表示目標(biāo)外凸點(diǎn)的數(shù)目。

設(shè)外凸點(diǎn)與質(zhì)心點(diǎn)的最大距離為RT,計(jì)算公式如下:

(7)

以質(zhì)心CT為球心、RT為半徑確定目標(biāo)外接球,作為部署的基準(zhǔn)曲面。

設(shè)當(dāng)前節(jié)點(diǎn)為Pn,其根據(jù)與目標(biāo)的距離遠(yuǎn)近產(chǎn)生虛擬引力或者虛擬斥力。設(shè)節(jié)點(diǎn)Pn對應(yīng)的外接球球心為Cn,Pn與目標(biāo)外接球球心CT的距離為:

(8)

針對傳感器節(jié)點(diǎn)與監(jiān)測目標(biāo)之間的虛擬作用力計(jì)算,同樣采用近似牛頓運(yùn)動(dòng)定律,以相距RT為臨界點(diǎn)。目標(biāo)外接球球心CT對節(jié)點(diǎn)Pn的虛擬作用力計(jì)算公式為:

(9)

其中,α(n,T)為單位向量,表示由節(jié)點(diǎn)Pn的外接球球心Cn指向目標(biāo)外接球球心CT的作用力方向。

為保證節(jié)點(diǎn)方向始終指向目標(biāo),設(shè)節(jié)點(diǎn)Pn指向其外接球球心Cn的單位向量為v,設(shè)由當(dāng)前節(jié)點(diǎn)Pn指向目標(biāo)外接球球心CT的單位向量為t,v與t的夾角為α,計(jì)算如式(10)所示。

(10)

若β≤π,節(jié)點(diǎn)順時(shí)針轉(zhuǎn)動(dòng)β,否則逆時(shí)針旋轉(zhuǎn)2π-β。

3 三維空間立體目標(biāo)全覆蓋算法

3.1 問題假設(shè)與需求

基于上述節(jié)點(diǎn)感知模型與目標(biāo)覆蓋模型,做如下假設(shè):

假設(shè)1傳感器網(wǎng)絡(luò)的監(jiān)測區(qū)域?yàn)槔硐霠顟B(tài)空間,排除一切可能影響部署結(jié)果的環(huán)境因素。

假設(shè)2監(jiān)測區(qū)域內(nèi)出現(xiàn)的所有傳感器節(jié)點(diǎn)均由同等規(guī)格的設(shè)備構(gòu)建,因此,具有相同的感知范圍、通信距離等節(jié)點(diǎn)屬性。

假設(shè)3傳感器節(jié)點(diǎn)均認(rèn)為設(shè)備完好,因此,不考慮因節(jié)點(diǎn)軟硬件故障引發(fā)的部署失敗、部署錯(cuò)誤等問題。

設(shè)定在某一指定三維空間環(huán)境內(nèi),存在體積遠(yuǎn)大于傳感器個(gè)體的監(jiān)測目標(biāo)(即僅靠單一節(jié)點(diǎn)無法完成對該目標(biāo)的監(jiān)測任務(wù))。傳感器集群隨機(jī)拋灑入環(huán)境后,要求以最優(yōu)部署狀態(tài)完成對大型監(jiān)測目標(biāo)的完全覆蓋和全面監(jiān)測,而非區(qū)域性覆蓋。本文針對上述需求,設(shè)計(jì)以監(jiān)測目標(biāo)為中心的三維傳感器節(jié)點(diǎn)自主覆蓋算法TOSA。

3.2 覆蓋算法

算法將有向移動(dòng)傳感器網(wǎng)絡(luò)協(xié)同自主部署過程轉(zhuǎn)化為節(jié)點(diǎn)在虛擬力場中受虛擬力作用而自主移動(dòng)、自主轉(zhuǎn)動(dòng)的過程。此算法為分布式算法,每個(gè)節(jié)點(diǎn)并行執(zhí)行以下步驟完成自主覆蓋:

1)初始化。節(jié)點(diǎn)獲得需要部署到的目標(biāo)外凸點(diǎn)集合,計(jì)算目標(biāo)的質(zhì)心點(diǎn),并由此得到以質(zhì)心點(diǎn)為球心,以距離集合內(nèi)外凸點(diǎn)最遠(yuǎn)距離為半徑的目標(biāo)外接球作為節(jié)點(diǎn)部署的基準(zhǔn)曲面。

2)目標(biāo)與節(jié)點(diǎn)間虛擬力的計(jì)算。為使節(jié)點(diǎn)能夠在不與目標(biāo)發(fā)生碰撞的情況下盡可能接近目標(biāo)基準(zhǔn)曲面,根據(jù)節(jié)點(diǎn)與目標(biāo)之間的距離,目標(biāo)對節(jié)點(diǎn)產(chǎn)生虛擬作用力:目標(biāo)的外接球的球心產(chǎn)生引力使節(jié)點(diǎn)能夠向目標(biāo)匯聚,目標(biāo)的外接球邊界(基準(zhǔn)曲面)產(chǎn)生虛擬斥力使靠近目標(biāo)的節(jié)點(diǎn)受到斥力作用不致碰撞目標(biāo)。

3)節(jié)點(diǎn)間虛擬力的計(jì)算。為了防止部署過程中發(fā)生節(jié)點(diǎn)間的碰撞,節(jié)點(diǎn)間產(chǎn)生虛擬作用力:節(jié)點(diǎn)間產(chǎn)生引力使可能離散的節(jié)點(diǎn)相互靠攏,節(jié)點(diǎn)間產(chǎn)生斥力使可能發(fā)生碰撞的節(jié)點(diǎn)相互遠(yuǎn)離。

4)節(jié)點(diǎn)受到來自鄰居節(jié)點(diǎn)和目標(biāo)的虛擬力的合力,沿合力方向移動(dòng)一個(gè)單位步長。

5)節(jié)點(diǎn)方向與目標(biāo)外接球球心方向的角度偏差的計(jì)算,即計(jì)算節(jié)點(diǎn)的有向傳感器方向與節(jié)點(diǎn)指向目標(biāo)外接球球心方向之間的角度偏差。

6)調(diào)整節(jié)點(diǎn)的有向傳感器的方向,使有向傳感器方向指向大目標(biāo)外接球球心。

7)返回步驟2)繼續(xù)執(zhí)行。

4 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)采用MATLAB仿真環(huán)境,監(jiān)測區(qū)域設(shè)為30 m×30 m×40 m的三維空間,覆蓋目標(biāo)為三維空間內(nèi)長寬高均為10 m的立方體。在監(jiān)測區(qū)域內(nèi)隨機(jī)部署300個(gè)傳感器節(jié)點(diǎn),節(jié)點(diǎn)初始參數(shù)如表1所示。

表1 傳感器節(jié)點(diǎn)參數(shù)

節(jié)點(diǎn)部署過程示意圖如圖4所示。初始時(shí)300個(gè)節(jié)點(diǎn)以設(shè)定的三維空間為邊界隨機(jī)分布于空間內(nèi)(如圖4(a)所示)。在部署過程中,所有節(jié)點(diǎn)向目標(biāo)移動(dòng)且監(jiān)測方向指向目標(biāo)中心點(diǎn)(如圖4(b)所示)。最終所有節(jié)點(diǎn)在算法的驅(qū)動(dòng)下完成對目標(biāo)的全覆蓋(如圖4(c)和圖4(d)所示)。

圖4 節(jié)點(diǎn)部署過程示意圖

在相關(guān)研究中,比較接近且較新的研究成果,如文獻(xiàn)[15-16],其中提到為使傳感器網(wǎng)絡(luò)在盡可能全覆蓋的同時(shí)延長生命周期,可將三維空間以同等規(guī)格的多面體進(jìn)行劃分,使節(jié)點(diǎn)部署在每個(gè)多面體的中心點(diǎn)來達(dá)到最佳覆蓋和連接效果。本文比較TOSA算法和空間劃分算法的如下指標(biāo):

1)覆蓋率,評估傳感器網(wǎng)絡(luò)性能的重要指標(biāo)之一,反映了傳感器網(wǎng)絡(luò)對監(jiān)測對象的全面監(jiān)測能力。

2)平均移動(dòng)距離,指整個(gè)部署過程中平均每個(gè)節(jié)點(diǎn)移動(dòng)的距離,同等時(shí)間內(nèi)移動(dòng)距離越小,顯示傳感器網(wǎng)絡(luò)的能耗越低。

3)為進(jìn)一步觀察部署算法能耗的使用情況,比較了2種算法在完成相同覆蓋率使用的部署時(shí)間和已達(dá)到部署范圍的節(jié)點(diǎn)數(shù)量,若能在更短的時(shí)間內(nèi)用更少的節(jié)點(diǎn)達(dá)到指定的覆蓋率,則表示該傳感器網(wǎng)絡(luò)在部署過程中更節(jié)約能耗。

上述性能指標(biāo)的對比結(jié)果如圖5所示。

圖5 2種部署算法的性能比較

根據(jù)對比結(jié)果可知,各項(xiàng)性能指標(biāo)TOSA算法整體均要優(yōu)于空間劃分算法?？臻g劃分算法中目標(biāo)的外接球部署區(qū)域被劃分為多個(gè)子分區(qū),每一個(gè)子分區(qū)的中心點(diǎn)都會(huì)影響到節(jié)點(diǎn)的移動(dòng),可能產(chǎn)生多個(gè)節(jié)點(diǎn)向同一個(gè)子分區(qū)集中的現(xiàn)象,造成節(jié)點(diǎn)的覆蓋冗余和覆蓋率的降低。同時(shí),節(jié)點(diǎn)在部署初期受到子分區(qū)中心點(diǎn)影響而產(chǎn)生的移動(dòng)也增加了節(jié)點(diǎn)移動(dòng)的距離和能耗。TOSA算法中所有節(jié)點(diǎn)的移動(dòng)只根據(jù)目標(biāo)中心點(diǎn)移動(dòng),越靠近目標(biāo)的部署范圍,節(jié)點(diǎn)之間越可能由于部署距離過近而進(jìn)行調(diào)整。由于節(jié)點(diǎn)部署的移動(dòng)調(diào)整主要集中在目標(biāo)周邊,能夠在更快到達(dá)部署范圍的前提下移動(dòng)距離更短,因此TOSA算法相比空間劃分算法在節(jié)約能耗和提高覆蓋率方面性能均有較大提高。

5 結(jié)束語

針對現(xiàn)實(shí)環(huán)境中面向大型建筑物等三維空間立體目標(biāo)的監(jiān)測需求,本文提出一種有向移動(dòng)傳感器網(wǎng)絡(luò)三維空間目標(biāo)自主覆蓋算法。采用基于外凸點(diǎn)集合計(jì)算三維目標(biāo)質(zhì)心的方法構(gòu)建部署基準(zhǔn)曲面,給出不均衡虛擬勢場的概念,通過目標(biāo)與節(jié)點(diǎn)、節(jié)點(diǎn)與節(jié)點(diǎn)之間的虛擬作用力,實(shí)現(xiàn)傳感器網(wǎng)絡(luò)的自主部署。下一步將對本文算法進(jìn)行優(yōu)化,使其能夠適應(yīng)節(jié)點(diǎn)異構(gòu)等更復(fù)雜的部署條件。

[1] MIAO C,DAI G,ZHAO X,et al.3D Self-deployment algorithm in mobile wireless sensor networks[C]//Proceedings of CWSN’14.Berlin,Germany:Springer,2014:27-41.

[2] LI W,ZHANG W.Coverage hole and boundary nodes detection in wireless sensor networks[J].Journal of Network and Computer Applications,2015,48:35-43.

[3] SAHOO P K,LIAO W.HORA:a distributed coverage hole repair algorithm for wireless sensor networks[J].IEEE Transactions on Mobile Computing,2015,14(7):1397-1410.

[4] TAO D,TANG S,LIU L.A coverage enhancement algorithm based on constrained artificial fish-swarm in directional sensor networks[J].Journal of Internet Technology,2014,15(1):43-52.

[5] ZHANG K,DUAN C,JIA H.Genetic simulated annealing-based coverage-enhancing algorithm for multimedia directional sensor networks[J].International Journal of Communication Systems,2015,28(9):1598-1609.

[6] SUNG T,YANG C.Voronoi-based coverage improvement approach for wireless directional sensor networks[J].Journal of Network and Computer Applications,2014,39:202-213.

[7] TAO D,WL T.A survey on barrier coverage problem in directional sensor networks[J].IEEE Sensors Journal,2015,15(2):876-885.

[8] MUNISHWAR V P,ABU-GHAZALEH N B.Coverage algorithms for visual sensor networks[J].ACM Transactions on Sensor Networks,2013,9(4):1-36.

[9] WANG H,ROMAN H E,YUAN L,et al.Connectivity,coverage and power consumption in large-scale wireless sensor networks[J].Computer Networks,2014,75:212-225.

[10] SONG Y,WANG B,SHI Z,et al.Distributed algorithms for energy-efficient even self-deployment in mobile sensor networks[J].IEEE Transactions on Mobile Computing,2014,13(5):1035-1047.

[11] 朱繼華,武 俊,陶 洋.基于覆蓋率的傳感器優(yōu)化部署算法[J].計(jì)算機(jī)工程,2010,36(3):94-96.

[12] KIM K.Mountainous terrain coverage in mobile sensor networks[J].IET Communications,2015,9(5):613-620.

[13] LIU L,MA H.On coverage of wireless sensor networks for rolling terrains[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(1):118-125.

[14] NAZARZEHI V,SAVKIN A V,BARANZADEH A.Distributed 3D dynamic search coverage for mobile wireless sensor networks[J].IEEE Communications Letters,2015,19(4):633-636.

[15] ALAM S M N,HAAS Z J.Coverage and connectivity in three-dimensional networks with random node deploy-ment[J].Ad Hoc Networks,2015,34(C):157-169.

[16] 鐘永信,黃建國,韓 晶.三維傳感器網(wǎng)絡(luò)部署、覆蓋和連接問題研究[J].控制與決策,2011,26(10):1447-1451.