徐忠明，譚 勵(lì)，楊朝玉，唐小江

(北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京 100048) (*通信作者電子郵箱tanli@th.btbu.edu.cn)

有向異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋率優(yōu)化算法

徐忠明，譚 勵(lì)*，楊朝玉，唐小江

(北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京 100048) (*通信作者電子郵箱tanli@th.btbu.edu.cn)

針對(duì)有向異構(gòu)節(jié)點(diǎn)部署存在覆蓋漏洞多、局部部署不均勻等問(wèn)題，提出一種有向異構(gòu)傳感器網(wǎng)絡(luò)目標(biāo)路徑覆蓋的精確部署算法(DHPSA)。自主部署過(guò)程分為兩個(gè)階段：首先，節(jié)點(diǎn)在鄰居節(jié)點(diǎn)的虛擬作用力和指定路徑虛擬引力的合力作用下實(shí)時(shí)選擇最優(yōu)路線部署到目標(biāo)路徑；然后，節(jié)點(diǎn)在鄰居節(jié)點(diǎn)的組合虛擬力作用下通過(guò)自主旋轉(zhuǎn)和自主移動(dòng)實(shí)現(xiàn)位置的微調(diào)，繼而實(shí)現(xiàn)對(duì)目標(biāo)路徑的精確覆蓋。通過(guò)仿真實(shí)驗(yàn)對(duì)比分析，所提算法比基于虛擬力的精確部署算法(VFPSA)在覆蓋率方面提高約4.4%、重疊率方面下降約3.4%，移動(dòng)距離方面減少約2.1%及部署時(shí)間減少約4.3%。仿真實(shí)驗(yàn)結(jié)果表明該部署算法更能有效地增大覆蓋率，減小重疊率，降低能耗。

有向異構(gòu)；精確部署；虛擬力；節(jié)點(diǎn)旋轉(zhuǎn)；路徑覆蓋

0 引言

無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)部署的質(zhì)量直接影響到網(wǎng)絡(luò)的性能，部署問(wèn)題作為無(wú)線傳感器網(wǎng)絡(luò)中研究的基本問(wèn)題[1]，反映了傳感器網(wǎng)絡(luò)所能提供的感知服務(wù)質(zhì)量。目前，對(duì)于傳感器網(wǎng)絡(luò)部署問(wèn)題的研究，多數(shù)是以全向同構(gòu)傳感器作為研究對(duì)象[2-4]。全向同構(gòu)傳感器網(wǎng)絡(luò)簡(jiǎn)化了節(jié)點(diǎn)模型，但應(yīng)用領(lǐng)域卻受到了限制，通常適用于檢測(cè)如溫度、濕度等簡(jiǎn)單的環(huán)境數(shù)據(jù)。有向傳感器網(wǎng)絡(luò)在人們的生產(chǎn)、生活中的應(yīng)用更為普遍，由于感知角度受限，只需感知來(lái)自某一方向的信息，且感知角度范圍通常存在差異，需要針對(duì)性地進(jìn)行研究。

近年來(lái)針對(duì)有向傳感器網(wǎng)絡(luò)部署問(wèn)題的研究越來(lái)越多。文獻(xiàn)[5]針對(duì)無(wú)線傳感器網(wǎng)絡(luò)部署問(wèn)題提出有向傳感器網(wǎng)絡(luò)方向感知模型,沒(méi)有對(duì)異構(gòu)節(jié)點(diǎn)部署進(jìn)行針對(duì)性研究。文獻(xiàn)[6]通過(guò)物理學(xué)中虛擬勢(shì)場(chǎng)的作用，提出了一種基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法(Potential Field-based Coverage Enhancing Algorithm, PFCEA)，該算法中節(jié)點(diǎn)間的作用力同樣基于質(zhì)心點(diǎn)模型，與本文算法區(qū)別主要在于節(jié)點(diǎn)移動(dòng)到目標(biāo)路徑后會(huì)通過(guò)自主旋轉(zhuǎn)和移動(dòng)增大覆蓋率等。文獻(xiàn)[7]針對(duì)重點(diǎn)區(qū)域覆蓋不足的問(wèn)題，提出了一種改進(jìn)的非均勻有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署方法，該方法的使用場(chǎng)景主要在當(dāng)需要覆蓋重點(diǎn)區(qū)域時(shí)，使用傳統(tǒng)方法不能有效突出重點(diǎn)區(qū)域；但研究對(duì)象仍然為有向同構(gòu)節(jié)點(diǎn)，而異構(gòu)節(jié)點(diǎn)更符合實(shí)際需求。文獻(xiàn)[8]針對(duì)復(fù)雜區(qū)域的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題，使用以扇形節(jié)點(diǎn)圍繞質(zhì)心點(diǎn)轉(zhuǎn)動(dòng)的節(jié)點(diǎn)模型，提出一種基于虛擬勢(shì)場(chǎng)的復(fù)雜區(qū)域覆蓋優(yōu)化算法(Coverage Optimization Algorithm for directional sensor network in Complex Area, COACA)，通過(guò)減小節(jié)點(diǎn)的旋轉(zhuǎn)面積實(shí)現(xiàn)部署優(yōu)化，該算法的研究對(duì)象是有向同構(gòu)節(jié)點(diǎn)；而本文的研究對(duì)象為異構(gòu)節(jié)點(diǎn)，更具有實(shí)際應(yīng)用價(jià)值。文獻(xiàn)[9]提出了一種無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋算法，通過(guò)調(diào)整目標(biāo)覆蓋區(qū)域幾何邊界，協(xié)同調(diào)度無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)，從而實(shí)現(xiàn)目標(biāo)區(qū)域無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋；該算法用于解決動(dòng)態(tài)覆蓋問(wèn)題，不適合解決異構(gòu)節(jié)點(diǎn)部署。文獻(xiàn)[10]針對(duì)多跳無(wú)線傳感器網(wǎng)絡(luò)中數(shù)據(jù)采集只采用單目標(biāo)優(yōu)化策略帶來(lái)的問(wèn)題，提出一種基于多目標(biāo)優(yōu)化的可移動(dòng)sink節(jié)點(diǎn)部署模型；該算法模型以傳感器網(wǎng)絡(luò)部署能耗最低為主要目標(biāo)，而本文算法模型除以能耗為目標(biāo)還考慮節(jié)點(diǎn)覆蓋率、重疊率等指標(biāo)。文獻(xiàn)[11]針對(duì)高大規(guī)模密集部署的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋率，提出一種基于虛擬力的節(jié)點(diǎn)分簇動(dòng)態(tài)部署策略；該算法以打破網(wǎng)絡(luò)中部節(jié)點(diǎn)受力平衡、降低部署過(guò)程中簇間干涉、提高節(jié)點(diǎn)覆蓋率為目的，但沒(méi)有考慮到節(jié)點(diǎn)的異構(gòu)特性，僅僅針對(duì)有向同構(gòu)節(jié)點(diǎn)進(jìn)行研究。文獻(xiàn)[12]針對(duì)覆蓋空洞、節(jié)點(diǎn)分布不均勻問(wèn)題，通過(guò)邊界部署保證邊界上的完全覆蓋和連通；通過(guò)該算法部署不需要額外探測(cè)和修復(fù)成本，算法僅僅是基于傳統(tǒng)算法模型上作了些改進(jìn)，并沒(méi)有考慮節(jié)點(diǎn)異構(gòu)性。文獻(xiàn)[13]在含有移動(dòng)節(jié)點(diǎn)的混合無(wú)線傳感器網(wǎng)絡(luò)中，采用更符合實(shí)際情況的基于誤警率的概率探測(cè)感知模型；該算法針對(duì)有同構(gòu)節(jié)點(diǎn)能提高檢測(cè)區(qū)域的覆蓋率，但針對(duì)異構(gòu)節(jié)點(diǎn)效果并不理想。

現(xiàn)有的部署算法大多數(shù)以同構(gòu)節(jié)點(diǎn)作為研究對(duì)象，而異構(gòu)性更符合實(shí)際需求。本文以異構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)作為研究對(duì)象，提出了有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的感知模型、虛擬作用力模型，在此基礎(chǔ)上提出了一種適于有向異構(gòu)傳感器網(wǎng)絡(luò)目標(biāo)路徑覆蓋的精確部署算法(Directional and Heterogeneous Precision Self-deployment Algorithm， DHPSA)，從而達(dá)到精確部署的目的，并且增大覆蓋率、減小重疊率。

1 DHPSA模型

1.1 假設(shè)與定義

首先作出如下假設(shè)與定義。

假設(shè)1 每個(gè)節(jié)點(diǎn)自身當(dāng)前的位置可以通過(guò)全球定位系統(tǒng)(Global Positioning System， GPS)或相關(guān)算法計(jì)算出，并得到確定的坐標(biāo)信息。

假設(shè)2 節(jié)點(diǎn)的通信半徑為Rc，當(dāng)兩個(gè)節(jié)點(diǎn)間的直線距離Dij小于或等于節(jié)點(diǎn)本身的通信半徑Rc時(shí)，這兩個(gè)節(jié)點(diǎn)互為彼此的鄰居節(jié)點(diǎn)，互相之間可以通信。

假設(shè)3 節(jié)點(diǎn)在通信半徑Rc內(nèi)能量連續(xù)，通信半徑外通信能量為0。

定義1 在監(jiān)控區(qū)域內(nèi)，若某個(gè)節(jié)點(diǎn)與其鄰接節(jié)點(diǎn)的覆蓋區(qū)域存在重疊，則稱重疊部分為這兩個(gè)節(jié)點(diǎn)的覆蓋重疊區(qū)域。

1.2 有向異構(gòu)節(jié)點(diǎn)感知模型

傳感器感知能力是指?jìng)鞲衅鞲兄Ｐ透采w范圍的大小，異構(gòu)傳感器網(wǎng)絡(luò)主要體現(xiàn)在傳感器感知能力的不同，通過(guò)簡(jiǎn)單的抽象，可以得到異構(gòu)有向傳感器節(jié)點(diǎn)的二維感知表示，如圖1所示。

有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的二維感知模型為如圖2中實(shí)線所示的扇形，用三元組〈R,V,α〉表示。其中：R是扇形的半徑，表示節(jié)點(diǎn)最大感知距離；V是單位向量，位于扇形的中軸線上，表示傳感器的感知方向；α是該扇形的張角，表示傳感器的感知角度，稱為視場(chǎng)。特別地，當(dāng)α=2π時(shí)，即為二維全向傳感器。

圖1 有向異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)

圖2 有向異構(gòu)傳感器感知模型

判斷監(jiān)測(cè)區(qū)域內(nèi)位于T位置的目標(biāo)點(diǎn)是否被位于P位置的傳感器節(jié)點(diǎn)i〈Ri,Vi,αi〉覆蓋，可以使用如下方法：如圖2所示，如果‖TP‖≤Ri且TP*Vi≥‖TP‖ cos(αi/2)，則目標(biāo)節(jié)點(diǎn)被覆蓋，否則不被覆蓋。

1.3 有向異構(gòu)傳感器網(wǎng)絡(luò)作用力模型

理想狀態(tài)下，無(wú)線傳感器節(jié)點(diǎn)在自動(dòng)部署過(guò)程中通常受到兩種類型的作用力，分別是節(jié)點(diǎn)之間虛擬作用力和路徑所產(chǎn)生的虛擬引力。本文節(jié)點(diǎn)間作用力引入了斥力半徑作為受力平衡位置，引入節(jié)點(diǎn)質(zhì)心作為節(jié)點(diǎn)受力點(diǎn)。而路徑對(duì)節(jié)點(diǎn)的引力引入了節(jié)點(diǎn)到路徑的垂足點(diǎn)，節(jié)點(diǎn)每次移動(dòng)都是沿著垂足點(diǎn)方向移動(dòng)，從而減小能量的消耗。與文獻(xiàn)[14]提出的基于虛擬力的精確部署算法(Virtual Force-based Precision Self-deployment Algorithm, VFPSA)不同，本文提出的DHPSA策略為當(dāng)節(jié)點(diǎn)移動(dòng)到路徑后，節(jié)點(diǎn)通過(guò)受到鄰居節(jié)點(diǎn)的合力來(lái)調(diào)整節(jié)點(diǎn)位置或旋轉(zhuǎn)方向，通過(guò)不斷地移動(dòng)和旋轉(zhuǎn)使覆蓋率逐漸變大，重疊率逐漸變小。

1.3.1 節(jié)點(diǎn)作用力模型

節(jié)點(diǎn)間作用力的模型是基于物理學(xué)中電場(chǎng)的概念，將傳感器節(jié)點(diǎn)看作是電場(chǎng)中的某個(gè)帶電荷的粒子，由于電場(chǎng)中存在引力和斥力，節(jié)點(diǎn)之間也存在引力和斥力的作用，其中節(jié)點(diǎn)距離和受力關(guān)系如圖3所示。

由以上建立的距離和受力模型可建立如下作用力關(guān)系式。

其中，引力和斥力的作用范圍都是[0，Rc]，其中Rc指節(jié)點(diǎn)的通信范圍。假設(shè)存在Rk(Rc>Rk)，當(dāng)節(jié)點(diǎn)Pi和Pj的距離0Dij>Rk時(shí)，節(jié)點(diǎn)Pi和Pj表現(xiàn)為引力，并且引力大小隨著距離增大而減??；當(dāng)節(jié)點(diǎn)Pi和Pj的距離Dij=Rk時(shí)，節(jié)點(diǎn)Pi和Pj之間作用力為零，即最理想平衡狀態(tài)。在通信范圍內(nèi)節(jié)點(diǎn)之間總是存在引力或斥力使得節(jié)點(diǎn)之間收斂于Rk，最終達(dá)到平衡狀態(tài)。

節(jié)點(diǎn)A和B所受的作用力(包括引力和斥力)關(guān)系式如下：

F(A,B)=

(1)

其中：正號(hào)表示引力；負(fù)號(hào)表示斥力；Dij表示節(jié)點(diǎn)間距離；Rk表示平衡時(shí)距離；Rc表示通信半徑；α、β、θ、k1表示為增益系數(shù)。

圖3 節(jié)點(diǎn)距離和受力關(guān)系

1.3.2 路徑作用力模型

為了實(shí)現(xiàn)節(jié)點(diǎn)對(duì)目標(biāo)路徑的有效覆蓋，提出“引力曲線”的概念，即目標(biāo)路徑會(huì)對(duì)每一個(gè)節(jié)點(diǎn)產(chǎn)生引力，在此引力的作用下使得節(jié)點(diǎn)自主向目標(biāo)路徑移動(dòng)，實(shí)現(xiàn)對(duì)目標(biāo)路徑的覆蓋。對(duì)任意節(jié)點(diǎn)A，總能夠找到一條到達(dá)目標(biāo)路徑的最短路徑，其最短距離定義為D。最短路徑所對(duì)應(yīng)的目標(biāo)路徑上的垂足點(diǎn)，定義為節(jié)點(diǎn)在曲線上的投影點(diǎn)P。投影點(diǎn)P與節(jié)點(diǎn)A間存在引力作用，且引力由投影點(diǎn)P指向節(jié)點(diǎn)A，使得節(jié)點(diǎn)在移動(dòng)過(guò)程中能夠始終沿“最短路徑”不斷接近目標(biāo)路徑，最終完成對(duì)目標(biāo)路徑的覆蓋，如圖4所示。

圖4 目標(biāo)路徑對(duì)節(jié)點(diǎn)作用力示意圖

節(jié)點(diǎn)受到引力曲線的引力可以用如式(2)所示：

(2)

其中：i為傳感器節(jié)點(diǎn)，j為節(jié)點(diǎn)在指定路徑的垂足點(diǎn)，dij表示節(jié)點(diǎn)與垂足點(diǎn)間距離，0表示節(jié)點(diǎn)已經(jīng)到達(dá)路徑且路徑對(duì)節(jié)點(diǎn)作用力為0。

1.3.3 節(jié)點(diǎn)旋轉(zhuǎn)模型

與文獻(xiàn)[14]提出的精確部署算法相比，該算法節(jié)點(diǎn)間的作用力同樣基于斥力模型，區(qū)別主要在于節(jié)點(diǎn)到達(dá)路徑后，會(huì)受到鄰居節(jié)點(diǎn)作用合力來(lái)進(jìn)行移動(dòng)和旋轉(zhuǎn)，通過(guò)移動(dòng)和旋轉(zhuǎn)角度增大覆蓋率與減小重疊率，如圖5所示。

圖5中：S表示傳感器節(jié)點(diǎn)；V表示節(jié)點(diǎn)的感知方向的單位矢量；F合1和F合2分別表示節(jié)點(diǎn)受鄰居節(jié)點(diǎn)的矢量合力，位于節(jié)點(diǎn)感知方向的不同兩側(cè)；若合力如F合1所示，則節(jié)點(diǎn)將逆時(shí)針旋轉(zhuǎn)一個(gè)步長(zhǎng)，若合力如F合2所示，則節(jié)點(diǎn)順時(shí)針旋轉(zhuǎn)一個(gè)步長(zhǎng)，直到節(jié)點(diǎn)受力完全達(dá)到平衡狀態(tài)。

圖5 節(jié)點(diǎn)旋轉(zhuǎn)模型

2 DHPSA過(guò)程描述

基于前面建立的模型，實(shí)現(xiàn)DHPSA，該算法是一個(gè)分布式算法，即所有待部署節(jié)點(diǎn)都并發(fā)地執(zhí)行該算法。算法主要步驟如下。

1)初始化。首先對(duì)節(jié)點(diǎn)初始位置和感知方向初始化，關(guān)聯(lián)其他節(jié)點(diǎn)，構(gòu)建每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合。初始化節(jié)點(diǎn)合力為零時(shí)暫停的時(shí)間長(zhǎng)度、節(jié)點(diǎn)的移動(dòng)步長(zhǎng)及到達(dá)路徑后的旋轉(zhuǎn)角度。

2)移動(dòng)過(guò)程中。節(jié)點(diǎn)與其鄰居節(jié)集合內(nèi)的所有節(jié)點(diǎn)依次判斷之間的距離，通過(guò)距離來(lái)計(jì)算每個(gè)鄰居節(jié)點(diǎn)對(duì)當(dāng)前節(jié)點(diǎn)產(chǎn)生的作用力，最終得出鄰居節(jié)點(diǎn)的合力；目標(biāo)路徑會(huì)對(duì)當(dāng)前節(jié)點(diǎn)產(chǎn)生引力作用，計(jì)算出當(dāng)前節(jié)點(diǎn)到目標(biāo)路徑投影點(diǎn)距離從而計(jì)算出引力大??；最終求出當(dāng)前節(jié)點(diǎn)受到的合力從而確定移動(dòng)的方向和距離。

3)移動(dòng)到路徑后。節(jié)點(diǎn)移動(dòng)到目標(biāo)路徑后將只會(huì)受到路徑節(jié)點(diǎn)的作用力。首先，設(shè)置一個(gè)信號(hào)量變量sign，通過(guò)信號(hào)量來(lái)控制節(jié)點(diǎn)是移動(dòng)優(yōu)先還是旋轉(zhuǎn)優(yōu)先；其次，計(jì)算出當(dāng)前節(jié)點(diǎn)受到鄰居節(jié)點(diǎn)合力，將合力與節(jié)點(diǎn)感知方向比較，若合力在感知方向左側(cè)，則節(jié)點(diǎn)將向左移動(dòng)或旋轉(zhuǎn)，若在右側(cè)將向右側(cè)移動(dòng)或旋轉(zhuǎn)，節(jié)點(diǎn)移動(dòng)和旋轉(zhuǎn)通過(guò)信號(hào)量控制進(jìn)行選擇，在旋轉(zhuǎn)能減少重疊的情況下優(yōu)先選擇旋轉(zhuǎn)。

4)穩(wěn)定狀態(tài)。重復(fù)步驟1)至3)直到整個(gè)網(wǎng)絡(luò)部署達(dá)到滿足要求的覆蓋率及重疊率。

算法偽代碼描述如下：

初始化節(jié)點(diǎn)部署初期位置Pi(x,y)，Vi； 初始化時(shí)間步長(zhǎng)Δt，移動(dòng)步長(zhǎng)stepLength，旋轉(zhuǎn)角度Δθ；

部署算法流程如圖6所示。

圖6 DHPSA主要流程

算法核心部分分析如下。

1)搜索鄰居節(jié)點(diǎn)。

for (i=0;i

}

//構(gòu)建鄰居節(jié)點(diǎn)

復(fù)雜度分析 整個(gè)網(wǎng)絡(luò)中存在m個(gè)傳感器節(jié)點(diǎn)，系統(tǒng)循環(huán)搜索所有個(gè)節(jié)點(diǎn)，依次計(jì)算每個(gè)節(jié)點(diǎn)是否屬于該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，若是鄰居節(jié)點(diǎn)將放入鄰居節(jié)點(diǎn)集合中。循環(huán)次數(shù)為節(jié)點(diǎn)個(gè)數(shù)，因此時(shí)間復(fù)雜度為O(m)。

2)向路徑移動(dòng)過(guò)程。

for (i=0;i

}

復(fù)雜度分析 當(dāng)前節(jié)點(diǎn)每作一次移動(dòng)將會(huì)搜索鄰居節(jié)點(diǎn)并計(jì)算所有鄰居節(jié)點(diǎn)作用力。由于搜索的時(shí)間復(fù)雜度為O(m)，計(jì)算鄰居節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)，所以最終復(fù)雜度為O(m*n)。

3 實(shí)驗(yàn)仿真與性能分析

3.1 部署質(zhì)量評(píng)價(jià)

無(wú)線傳感器網(wǎng)絡(luò)的部署效果與性能評(píng)價(jià)指標(biāo)對(duì)于分析該部署的可用性與有效性至關(guān)重要，通常評(píng)價(jià)無(wú)線傳感器網(wǎng)絡(luò)的覆蓋質(zhì)量有以下幾種指標(biāo)：覆蓋率、重疊率、平均移動(dòng)距離、部署時(shí)間。

1)覆蓋率。

覆蓋率通常定義為所有傳感器覆蓋的總面積與目標(biāo)區(qū)域總面積的比值，其中節(jié)點(diǎn)覆蓋的總面積取集合概念中的并集。如果節(jié)點(diǎn)Si的覆蓋區(qū)域?yàn)锳i，區(qū)域總面積為A，則覆蓋率為：

(3)

其中節(jié)點(diǎn)覆蓋總區(qū)域取每個(gè)節(jié)點(diǎn)區(qū)域的并集，顯然區(qū)域的總覆蓋率小于或等于1。

2)重疊率。

重疊率是指區(qū)域中所有節(jié)點(diǎn)的有效覆蓋面積的并集占所有節(jié)點(diǎn)覆蓋面積之和的百分比，用來(lái)衡量節(jié)點(diǎn)覆蓋范圍的有效性，計(jì)算公式如式(4)所示：

(4)

在有向節(jié)點(diǎn)覆蓋問(wèn)題中，網(wǎng)絡(luò)的重疊率不可能為0，重疊率反映了節(jié)點(diǎn)覆蓋的重疊程度，重疊率越高表示當(dāng)前節(jié)點(diǎn)間的覆蓋重疊越嚴(yán)重；反之亦然。

3)平均移動(dòng)距離。

平均移動(dòng)距離是指所有節(jié)點(diǎn)移動(dòng)的距離之和的平均值，用來(lái)衡量節(jié)點(diǎn)能量消耗大小，計(jì)算公式如式(5)所示：

(5)

其中：di為節(jié)點(diǎn)i移動(dòng)的總距離，n為節(jié)點(diǎn)數(shù)量。

4)部署時(shí)間。

部署時(shí)間是指所有節(jié)點(diǎn)都達(dá)到穩(wěn)定狀態(tài)后所需要的時(shí)間，部署時(shí)間短所需要的能量少，反之亦然。

3.2 實(shí)驗(yàn)仿真

本實(shí)驗(yàn)是基于The ONE仿真模擬器，實(shí)驗(yàn)中以節(jié)點(diǎn)為單位，其中仿真器中每個(gè)扇形表示不同的節(jié)點(diǎn)，實(shí)驗(yàn)中異構(gòu)節(jié)點(diǎn)分為3組，具有3種不同的感知角度，分別為60°、90°、120°，感知半徑相同，通信半徑也相同。

本次實(shí)驗(yàn)在模擬曲線路徑(8×160)隨機(jī)拋灑150個(gè)節(jié)點(diǎn),每隔一段時(shí)間記錄節(jié)點(diǎn)移動(dòng)軌跡及其對(duì)應(yīng)的覆蓋率和重疊率的變化情況，如圖7所示記錄了節(jié)點(diǎn)移動(dòng)軌跡，其中t為以節(jié)點(diǎn)運(yùn)動(dòng)開(kāi)始為基準(zhǔn)的時(shí)間增加值。

從節(jié)點(diǎn)部署軌跡可以看出，該算法能達(dá)到精確部署的目的，節(jié)點(diǎn)質(zhì)心在鄰居節(jié)點(diǎn)合力的作用下進(jìn)行移動(dòng)和旋轉(zhuǎn)，從而覆蓋整條路徑。

圖7 節(jié)點(diǎn)移動(dòng)軌跡

3.3 算法對(duì)比分析

基于實(shí)驗(yàn)結(jié)果，本節(jié)將本文算法與文獻(xiàn)[14]提出的VFPSA進(jìn)行對(duì)比分析。兩種算法在同等實(shí)驗(yàn)條件(如表1所示，其中dip指仿真環(huán)境中界面中節(jié)點(diǎn)的坐標(biāo)位置)下進(jìn)行，比較兩種算法下隨著部署時(shí)間的變化網(wǎng)絡(luò)的覆蓋率、重疊率、節(jié)點(diǎn)行走總距離及部署時(shí)間。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

3.3.1 對(duì)比算法描述

文獻(xiàn)[14]提出的基于虛擬力的精確部署算法(VFPSA)用于實(shí)現(xiàn)移動(dòng)傳感器網(wǎng)絡(luò)的自動(dòng)化精確部署。該算法研究的是基于全向傳感器節(jié)點(diǎn)模型，能實(shí)現(xiàn)精確部署，但只考慮了節(jié)點(diǎn)的移動(dòng)沒(méi)考慮旋轉(zhuǎn)；而本文研究的是針對(duì)有向異構(gòu)節(jié)點(diǎn)，不僅考慮節(jié)點(diǎn)移動(dòng)還同步考慮節(jié)點(diǎn)的旋轉(zhuǎn)。

3.3.2 覆蓋率對(duì)比

兩種算法在同等實(shí)驗(yàn)參數(shù)(如表1所示)下，通過(guò)式(3)得出不同時(shí)刻的覆蓋率變化軌跡如圖8所示。

從圖8可以看出，本文提出的算法在實(shí)現(xiàn)精確部署的同時(shí)，覆蓋率比VFPSA提升4.4%，主要因?yàn)槭枪?jié)點(diǎn)通過(guò)旋轉(zhuǎn)使覆蓋更為合理。

3.3.3 重疊率對(duì)比

兩種算法在同等實(shí)驗(yàn)參數(shù)(如表1所示)下，通過(guò)式(4)得出不同時(shí)刻的重疊率，如圖9所示，其中，時(shí)間坐標(biāo)0刻度以節(jié)點(diǎn)都移動(dòng)到指定路徑后為基準(zhǔn)。

圖8 覆蓋率比較

圖9 重疊率比較

從圖9可以看出，本文算法在達(dá)到精確部署的同時(shí)節(jié)點(diǎn)的重疊率比VFPSA平均下降了3.4%，主要原因是節(jié)點(diǎn)通過(guò)旋轉(zhuǎn)微調(diào)，使重疊進(jìn)一步減少。

3.3.4 平均移動(dòng)距離對(duì)比

兩種算法在同等實(shí)驗(yàn)參數(shù)(如表1所示)下，通過(guò)式(5)得出不同時(shí)刻的距離平均值。以時(shí)間為基準(zhǔn)的網(wǎng)絡(luò)節(jié)點(diǎn)行走總距離平均值的變化軌跡，如圖10所示。

圖10 行走距離比較

從圖10可以看出，部署第一階段(節(jié)點(diǎn)未移動(dòng)到路徑中)兩種算法行走的總距離相差不大，進(jìn)入第二階段(節(jié)點(diǎn)已經(jīng)移動(dòng)到路徑中)后本文算法的行走距離要比對(duì)比算法的短，減少2.1%，主要原因是因?yàn)椴捎昧诵D(zhuǎn)優(yōu)先策略，在出現(xiàn)重疊的情況下，優(yōu)先通過(guò)旋轉(zhuǎn)解決重疊。由于移動(dòng)相比旋轉(zhuǎn)會(huì)消耗更多的能量，所以本算法最終要消耗的能量要少。

3.3.5 部署時(shí)間對(duì)比

兩種算法在同等實(shí)驗(yàn)參數(shù)(如表1所示)下，通過(guò)隨機(jī)拋灑不同的節(jié)點(diǎn)數(shù)量對(duì)比各自部署所需要的時(shí)間。以節(jié)點(diǎn)數(shù)量為基準(zhǔn)的部署時(shí)間的變化軌跡，如圖11所示。

從圖11可以看出，本文提出的算法在不同規(guī)模節(jié)點(diǎn)數(shù)量的情況下相比VFPSA需要更少的部署時(shí)間，平均減少4.3%。主要原因是在部署過(guò)程中，節(jié)點(diǎn)只通過(guò)移動(dòng)方式進(jìn)行部署會(huì)在虛擬力邊界出現(xiàn)局部最小問(wèn)題，節(jié)點(diǎn)來(lái)回震蕩無(wú)法平衡穩(wěn)定，DHPSA通過(guò)旋轉(zhuǎn)優(yōu)先，減少了只移動(dòng)節(jié)點(diǎn)帶來(lái)的不穩(wěn)定問(wèn)題。

圖11 部署時(shí)間比較

4 結(jié)語(yǔ)

針對(duì)有向異構(gòu)傳感器網(wǎng)絡(luò)精確部署問(wèn)題，本文提出了一種基于虛擬力實(shí)現(xiàn)節(jié)點(diǎn)移動(dòng)和旋轉(zhuǎn)的精確部署算法，通過(guò)信號(hào)量控制節(jié)點(diǎn)的移動(dòng)和旋轉(zhuǎn)，從而達(dá)到更高的覆蓋率及更低的重疊率。實(shí)驗(yàn)仿真結(jié)果表明，該算法能夠?qū)崿F(xiàn)精確部署且與VFPSA相比在覆蓋率、重疊率、移動(dòng)距離及部署時(shí)間具有更優(yōu)的性能，下一步工作將圍繞三維空間有向異構(gòu)傳感器網(wǎng)絡(luò)部署問(wèn)題進(jìn)行深入研究。

References)

[1] CARDEI M, WU J. Energy-efficient coverage problems in wireless Ad-Hoc sensor networks [J]. Computer Communications, 2006, 29(4): 413-420.

[2] THAI M T, WANG F, DU D H, et al. Coverage problems in wireless sensor networks: designs and analysis [J]. International Journal of Sensor Networks, 2008, 3(3): 191-200.

[3] CHOW K Y, LUI K S, LAM E Y. Wireless sensor networks scheduling for full angle coverage [J]. Multidimensional Systems & Signal Processing, 2009, 20(2): 101-119.

[4] LI Y, GAO S. Designingk-coverage schedules in wireless sensor networks [J]. Journal of Combinatorial Optimization, 2008, 15(2): 127-146.

[5] MA H D, LIU Y H. On coverage problems of directional sensor networks [C]// Proceedings of the 2005 International Conference on Mobile Ad-Hoc and Sensor Networks. Berlin: Spring, 2005: 721-731.

[6] 陶丹，馬華東，劉亮.基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].軟件學(xué)報(bào)，2007，18(5):1152-1163.(TAO D, MA H D, LIU L. A virtual potential field based coverage-enhancing algorithm for directional sensor networks [J]. Journal of Software, 2007, 18(5): 1152-1163.)

[7] 譚勵(lì)，楊朝玉，楊明華,等.改進(jìn)的有向傳感器網(wǎng)絡(luò)多中心部署算法[J].計(jì)算機(jī)應(yīng)用與研究,2016,33(12):3797-3800.(TAN L, YANG C Y, YANG M H, et al. Covering research to directional sensor networks based on deployment of multi-center [J]. Application Research of Computers, 2016, 33(12): 3797-3800.)

[8] 譚勵(lì),陳玉程.復(fù)雜區(qū)域的有向傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].計(jì)算機(jī)工程,2015,41(4):14-18.(TAN L, CHEN Y C. Coverage optimization algorithm for directional sensor network in complex area [J]. Computer Engineering, 2015, 41(4): 14-18.)

[9] 劉志強(qiáng),沈廼桐,毛強(qiáng),等.無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋的CVT算法[J].傳感器與微系統(tǒng),2015,34(6):115-118.(LIU Z Q, SHEN N T, MAO Q, et al. A dynamic coverage algorithm for wireless sensor networks based on CVT [J]. Transducer and Microsystem Technologies, 2015, 34(6): 115-118.)

[10] 方芳,陳世平.無(wú)線傳感器網(wǎng)絡(luò)中多目標(biāo)優(yōu)化節(jié)點(diǎn)部署模型[J].計(jì)算機(jī)應(yīng)用研究,2015,32(4):1166-1168.(FANG F, CHEN S P. Node deployment model of multi-objective optimization in wireless sensor networks [J]. Application Research of Computers, 2015, 32(4): 1166-1168.)

[11] 金仁成,韋寧,徐浩,等.基于虛擬力的無(wú)線傳感器網(wǎng)絡(luò)分簇部署策略[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,35(5):640-644.(JIN R C, WEI N, XU H, et al. Clustering dynamic deployment strategy based on virtual force in wireless sensor networks [J]. Journal of Northeastern University (Natural Science), 2014, 35(5): 640-644.)

[12] 王學(xué)軍.一種改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署方案[J].計(jì)算機(jī)工程,2012,38(19):82-84.(WANG X J. An improved node deployment scheme in wireless sensor network [J]. Computer Engineering, 2012, 38(19): 82-84.

[13] 黃月,吳成東,張?jiān)浦?等.基于移動(dòng)節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,33(2):165-168.(HUANG Y, WU C D, ZHANG Y Z, et al. Coverage optimization of wireless sensor networks based on mobile nodes [J]. Journal of Northeastern University (Natural Science), 2012, 33(2): 165-168.)

[14] 楊明華,曹元大,譚勵(lì),等.一種移動(dòng)傳感器網(wǎng)絡(luò)精確部署算法[J].北京理工大學(xué)學(xué)報(bào),2009,29(1):27-31.(YANG M H, CAO Y D, TAN L, et al. A precision deployment algorithm in mobile sensor network [J]. Transaction of Beijing Institute of Technology, 2009, 29(1): 27-31.)

[15] ZOU Y, CHAKRABARTY K. Uncertainty-aware and coverage-oriented deployment for sensor networks [J]. Journal of Parallel & Distributed Computing, 2004, 64(7): 788-798.

This work is partially supported by the Beijing Natural Science Foundation (4132025), the National Natural Science Foundation of China (61402022), the Beijing Philosophy Social Science Planning Project (14JGB033).

XUZhongming, born in 1993, M. S. candidate. His research interests include wireless sensor network.

TANLi, born in 1980, Ph. D., professor. Her research interests include wireless sensor network, intelligent information network, machine learning.

YANGChaoyu, born in 1990, M. S. candidate. Her research interests include wireless sensor network.

TANGXiaojiang, born in 1994, M. S. candidate. His research interests include wireless sensor network.

Nodecoverageoptimizationalgorithmindirectionalheterogeneouswirelesssensornetwork

XU Zhongming, TAN Li*, YANG Chaoyu, TANG Xiaojiang

(SchoolofComputerandInformationEngineering,BeijingTechnologyandBusinessUniversity,Beijing100048,China)

Concerning covering loopholes and uneven local deployment, a Directional and Heterogeneous Precision Self-deployment Algorithm (DHPSA) was proposed. Autonomous deployment process was divided into two stages. Firstly, a node moved to the destination path by choosing the optimal route in real-time under virtual forces of neighbor node and specified path. Then, through autonomous rotation and autonomous moving, the location of the node was finely tuned under joint virtual force of neighbor nodes and the accurate coverage of the target path was realized finally. The contrast experiments show that, compared with the VFPSA (Virtual Force-based Precision Self-deployment Algorithm), the coverage rate of the proposed algorithm is increased by about 4.4 percent, the overlapping rate is decreased by about 3.4 percent, moving distance is reduced by about 2.1 percent and deployment time is reduced by about 4.3 percent. The simulation experiment results show that the proposed deployment algorithm can effectively increase the coverage rate, decrease the overlap rate and reduce energy consumption.

directional heterogeneity; precise deployment; virtual force; node rotation; path coverage

TP212.9

:A

2016- 12- 22;

:2017- 02- 05。

北京市自然科學(xué)基金資助項(xiàng)目(4172013)；國(guó)家自然科學(xué)基金青年項(xiàng)目(61402022)；北京市哲學(xué)社會(huì)科學(xué)規(guī)劃項(xiàng)目(14JGB033)。

徐忠明(1993—)，男，江西景德鎮(zhèn)人，碩士研究生，主要研究方向：無(wú)線傳感器網(wǎng)絡(luò)； 譚勵(lì)(1980—)，女，廣西南寧人，教授，博士，CCF會(huì)員，主要研究方向：無(wú)線傳感器網(wǎng)絡(luò)、智能信息網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)； 楊朝玉(1990—)，女，山東梁山人，碩士研究生，主要研究方向：無(wú)線傳感器網(wǎng)絡(luò)； 唐小江(1994—)，男，甘肅慶陽(yáng)人，碩士研究生，主要研究方向：無(wú)線傳感器網(wǎng)絡(luò)。

1001- 9081(2017)07- 1849- 06

10.11772/j.issn.1001- 9081.2017.07.1849