黃 帥，程良倫

(廣東工業(yè)大學(xué)自動化學(xué)院，廣州510006)

隨著監(jiān)測環(huán)境的日趨復(fù)雜多變，由傳統(tǒng)傳感器網(wǎng)絡(luò)所獲取的簡單數(shù)據(jù)愈加不能滿足人們對環(huán)境監(jiān)測的全面需求，迫切需要將數(shù)據(jù)量大、內(nèi)容豐富的圖像、視頻等媒體引入到以傳感器網(wǎng)絡(luò)為基礎(chǔ)的環(huán)境監(jiān)測活動中來，實現(xiàn)細粒度，精準信息的環(huán)境監(jiān)測[1]。針對這種需求，作為傳感器網(wǎng)絡(luò)高級形式的有向傳感器網(wǎng)絡(luò)應(yīng)運而生，它主要包括視頻傳感器網(wǎng)絡(luò)和圖像傳感器網(wǎng)絡(luò)。有向傳感器網(wǎng)絡(luò)的性能主要通過在監(jiān)測區(qū)域內(nèi)部署的傳感器節(jié)點的覆蓋率來體現(xiàn)[2]，因此優(yōu)化有向傳感器網(wǎng)絡(luò)的覆蓋對于合理分配網(wǎng)絡(luò)的空間資源，更好地完成環(huán)境感知、信息獲取任務(wù)以及提高網(wǎng)絡(luò)的生存能力都具有重要的意義。但是由于有向傳感器網(wǎng)絡(luò)中傳感器節(jié)點受視場限制，不能和傳統(tǒng)傳感器網(wǎng)絡(luò)中的節(jié)點一樣采用全向感知模型，因此有向傳感器網(wǎng)絡(luò)的覆蓋問題相對于傳統(tǒng)的傳感器網(wǎng)絡(luò)的要復(fù)雜許多。

目前，國內(nèi)外已有很多學(xué)者[3－7，12]針對有向傳感器網(wǎng)絡(luò)的覆蓋增強問題作了深入的研究。Ma等人在文獻[3]中提出了一種2D感知模型并研究了有向傳感器網(wǎng)絡(luò)覆蓋完整性以及通信連通性問題。在此基礎(chǔ)上，文獻[4]進一步提出了一種基于圖論和計算幾何的集中式覆蓋增強算法，但是由于未能充分考慮到有向傳感器節(jié)點局部位置及傳感方向信息，該算法對有向傳感器網(wǎng)絡(luò)覆蓋增強的能力相對有限。文獻[5]設(shè)計了一種方向可調(diào)感知模型，并以此為基礎(chǔ)提出了一種基于虛擬勢場的有向傳感器網(wǎng)絡(luò)覆蓋增強算法，巧妙的引入“質(zhì)心”概念，將有向傳感器網(wǎng)絡(luò)的覆蓋增強問題轉(zhuǎn)化為質(zhì)心均勻分布問題，以質(zhì)心點作圓周運動代替節(jié)點傳感方向的轉(zhuǎn)動，達到消除網(wǎng)絡(luò)中感知重疊區(qū)和盲區(qū)，增強網(wǎng)絡(luò)覆蓋的目的。文獻[6]提出了一種基于虛擬勢場的路徑覆蓋增強算法，將要解決的問題轉(zhuǎn)化為質(zhì)心點－運動軌跡點，質(zhì)心點－質(zhì)心點之間的虛擬力作用情況，以較小的代價獲得了視頻傳感器網(wǎng)絡(luò)對路徑的充分覆蓋，但是存在一個問題:當(dāng)軌跡點對傳感器節(jié)點的引力和其它傳感器節(jié)點對該傳感器節(jié)點的斥力合力為零時，此時如果該傳感器節(jié)點和周圍傳感器節(jié)點存在大量共同的軌跡覆蓋點，則該傳感器節(jié)點并沒有發(fā)揮軌跡點的有效覆蓋功能，網(wǎng)絡(luò)會陷入局部最小情況。文獻[7]針對文獻[6]存在的問題提出了一種基于改進勢場的有向傳感器網(wǎng)絡(luò)路徑覆蓋增強算法，通過將相鄰傳感器節(jié)點對路徑軌跡點的共同覆蓋率引入到斥力計算中，有效引導(dǎo)節(jié)點的主感知方向調(diào)整，從而達到路徑的高效覆蓋。

傳統(tǒng)基于虛擬力的覆蓋增強算法只判斷調(diào)整方向，節(jié)點的調(diào)整量為固定值，并且沒有解決整個網(wǎng)絡(luò)進入穩(wěn)定狀態(tài)后的冗余覆蓋問題。本文在設(shè)計出方向可調(diào)感知模型后，提出一種基于虛擬力的有向傳感器網(wǎng)絡(luò)低冗余覆蓋增強算法，建立虛擬力與角度調(diào)整量之間的關(guān)系模型，根據(jù)虛擬力的大小改變節(jié)點的角度調(diào)整量;當(dāng)虛擬力小于某個閾值后，說明節(jié)點此刻進入了穩(wěn)定狀態(tài)，計算節(jié)點覆蓋子集的集合，如果存在除了此節(jié)點以外的覆蓋子集，則通知其中一個覆蓋子集中包含的節(jié)點停止調(diào)整，同時此節(jié)點進入休眠狀態(tài)。最后通過仿真實驗證明算法的有效性，提高了有向傳感器網(wǎng)絡(luò)的調(diào)整效率，并且在保證覆蓋率的前提下很好的解決了網(wǎng)絡(luò)中的覆蓋冗余問題。

1 有向傳感器網(wǎng)絡(luò)冗余覆蓋增強問題

1．1 有向傳感器節(jié)點的方向可調(diào)感知模型和覆蓋子集

如圖1所示，有向傳感器節(jié)點的方向可調(diào)感知模型采用五元組 ＜P，R，V(t)，α，β＞來表示。其中P(x，y)表示節(jié)點的位置坐標;R表示節(jié)點的有效感知半徑;V(t)=(Vx(t)，Vy(t))為節(jié)點在時刻t的感知方向;2α表示節(jié)點的有效感知角度;β表示節(jié)點感知方向的角度調(diào)整量。

圖1 有向傳感器節(jié)點的覆蓋模型

在增強過程中，網(wǎng)絡(luò)中的每個節(jié)點都明確自身的覆蓋范圍，而它所覆蓋的范圍也可能由網(wǎng)絡(luò)中的其它幾個鄰居節(jié)點所覆蓋。

定義1定義集合Coi(v)為有向傳感器節(jié)點v的一個覆蓋子集，其中UV'∈Coi(v)可以覆蓋有向傳感器節(jié)點v的覆蓋區(qū)域。

定義2定義Co(v)為覆蓋節(jié)點v覆蓋區(qū)域的所有覆蓋子集的集合。

為了計算Co(v)，需要定義4個點(三個定點以及重心)來標識節(jié)點v的覆蓋區(qū)域，如圖1(a)所示。若Coi(v)∈Co(v)覆蓋節(jié)點v所覆蓋的區(qū)域成立，當(dāng)且僅當(dāng)滿足以下條件:

(1)?v'∈Coi(v)，v'覆蓋點 d 以及{a，b，c}中至少一個點。

(2)Coi(v)可以覆蓋 a、b、c、d 四個點。

1．2 有向傳感器網(wǎng)絡(luò)低冗余覆蓋增強問題的分析

在做本文的研究之前，做出以下假設(shè):

(1)有向傳感器網(wǎng)絡(luò)中部署的所有節(jié)點均同構(gòu)，即所有節(jié)點的感知半徑、傳感夾角等參數(shù)都一樣;

(2)在進行覆蓋增強的調(diào)整過程中，所有節(jié)點位置不變，但其傳感方向可調(diào);

(3)有向傳感器網(wǎng)絡(luò)中各節(jié)點均明確其自身位置以及傳感方向，并能對自身的傳感方向進行調(diào)節(jié)，但是此調(diào)節(jié)僅限制于圍繞固定點做圓周運動。

(4)有向傳感器網(wǎng)絡(luò)中節(jié)點的受力點為其方向可調(diào)感知模型的質(zhì)心。

如圖1(b)所示，節(jié)點 v的覆蓋區(qū)域由 a、b、c、d四個點表示，可以找到滿足條件的覆蓋子集有AG={v2，v1}，BG={v3，v1}，CG={v1，v5}。根據(jù)前面提到的方法，節(jié)點v的覆蓋子集的集合為:

當(dāng)某個節(jié)點進入穩(wěn)定狀態(tài)后，計算此節(jié)點的覆蓋子集的集合，如果存在除了此節(jié)點以外的覆蓋子集，則通知其中一個覆蓋子集中包含的節(jié)點停止調(diào)整，此節(jié)點進入休眠狀態(tài)。

設(shè)Ai(t)表示節(jié)點vi在傳感向量為V(t)時的感知面積，Ai(t)∪Aj(t)表示節(jié)點vi和節(jié)點vj的感知面積進行并運算后得到的總面積。當(dāng)網(wǎng)絡(luò)中節(jié)點的傳感向量分別為(V1(t)，V2(t)，V3(t)，…，VN(t))時，有向傳感器網(wǎng)絡(luò)的覆蓋率表示如下[5]:

其中，A表示監(jiān)測區(qū)域的面積。

在一個監(jiān)測區(qū)域內(nèi)分布了N個結(jié)構(gòu)相同的有向傳感器節(jié)點，則區(qū)域覆蓋增強算法可以看作一個求最優(yōu)解的問題，即求解一組(V1(t)，V2(t)，V3(t)，…，VN(t))*，使得對于所有(V1(t)，V2(t)，V3(t)，…，VN(t))式(2)成立:

2 有向傳感網(wǎng)絡(luò)低冗余覆蓋增強算法

2．1 虛擬力的建立以及合力的計算

虛擬勢場(Potential Force)方法是解決傳感器網(wǎng)絡(luò)覆蓋控制問題的典型方法之一[5]，許多關(guān)于傳感器網(wǎng)絡(luò)覆蓋問題的文獻[6－10]都采用了這種思想，假定傳感器節(jié)點之間存在一種虛擬的斥力，而傳感器節(jié)點與監(jiān)測目標之間又存在一種虛擬的引力，通過這兩種虛擬力的抗衡達到增強網(wǎng)絡(luò)覆蓋的目的，但是只是將虛擬力的合力方向做為調(diào)整節(jié)點感知方向的依據(jù)，每次調(diào)整的角度大小不變。調(diào)整角度值設(shè)定太小，時間步長轉(zhuǎn)動較小，雖然調(diào)整準確度較高，但是推遲了整個網(wǎng)絡(luò)穩(wěn)定狀態(tài)的到來;調(diào)整角度值設(shè)定太大，調(diào)整準確度降低，還有可能造成網(wǎng)絡(luò)最終不能進入穩(wěn)定狀態(tài)。本文通過建立合力與調(diào)整角度大小之間的關(guān)系，動態(tài)改變節(jié)點感知方向的調(diào)整量，使整個網(wǎng)絡(luò)能夠更快的進入穩(wěn)定狀態(tài)。另外在實際應(yīng)用中，考慮到成本問題，監(jiān)測區(qū)域中所有的節(jié)點都具有移動能力是不現(xiàn)實的，而且也可能由于傳感器節(jié)點位置的變化引起部分節(jié)點的失效，造成整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)發(fā)生變化。因此本文假定所有節(jié)點的調(diào)整僅限于圍繞一點做旋轉(zhuǎn)運動，且這一點為節(jié)點方向可調(diào)到感知模型的頂點。

(1)虛擬力的建立

經(jīng)過前面的分析，利用虛擬視場解決有向傳感器網(wǎng)絡(luò)的區(qū)域覆蓋問題可近似等價于質(zhì)心點與質(zhì)心點的虛擬斥力作用問題。有向傳感器節(jié)點之間存在斥力，并且在2R范圍內(nèi)，節(jié)點之間的距離越近，斥力越大，反之越小。

相鄰傳感器節(jié)點vj對vi的虛擬斥力定義為:

俄羅斯國家杜馬信息政策、信息技術(shù)和通信委員會副主任亞歷山大·尤先科在人工智能論壇上指出，如今全世界都在競相發(fā)展人工智能，在這個領(lǐng)域俄羅斯不能落后，俄羅斯有IT行業(yè)優(yōu)勢，國家對人工智能立法責(zé)無旁貸，同時要立法部門和政府部門協(xié)同，學(xué)術(shù)界及社會廣泛支持。

其中，k為斥力常數(shù);aij為單位向量，由節(jié)點vj的質(zhì)心指向節(jié)點vi的質(zhì)心;‖Yi－Yj‖為節(jié)點vj與節(jié)點vi質(zhì)心之間的歐氏距離。

(2)合力的計算

定義3有向傳感器網(wǎng)絡(luò)中，當(dāng)節(jié)點vj與節(jié)點vi質(zhì)心之間的歐氏距離小于或等于節(jié)點感知半徑的2倍時，則互為友鄰節(jié)點。

假設(shè)節(jié)點vi的友鄰節(jié)點的集合為Φi，則節(jié)點vi質(zhì)心所受的合力為:Fi=∑j∈ΦiFij，vj∈Φi。由于規(guī)定有向傳感器網(wǎng)絡(luò)中的節(jié)點只能圍繞其感知模型的頂點做旋轉(zhuǎn)運動，因此節(jié)點感知方向的調(diào)整只受合力沿切線方向分量F'的影響，如圖2所示。

圖2 節(jié)點的質(zhì)心點受力合力分析

2．2 調(diào)整角度的計算

從力學(xué)的角度講，分量F'和傳感器的質(zhì)量以及節(jié)點做直線運動的加速度有關(guān)，但是由于節(jié)點只能做旋轉(zhuǎn)，因此需要將直線加速度轉(zhuǎn)化為角加速度。則有:

其中:a表示物體的直線加速度，R表示旋轉(zhuǎn)半徑，φ表示物體的角加速度，m為物體質(zhì)量。由于調(diào)整角度的大小并不受m的影響，因此將式(4)簡化為:

但在本文中，節(jié)點并不是一直在做旋轉(zhuǎn)，而是每做一次旋轉(zhuǎn)后計算分量F'以及調(diào)整角度的值再做旋轉(zhuǎn)。因此式(5)中角加速度φ可以看作和調(diào)整角度有關(guān)聯(lián)的一個量。

式(6)中α表示節(jié)點有效感知角度的一半;β表示節(jié)點感知方向的角度調(diào)整量。將式(5)與式(6)進行整合，得到:

其中，0≤β≤α。

2．3 區(qū)域覆蓋增強算法描述

輸入 節(jié)點vi及友鄰節(jié)點的狀態(tài)信息，包括:當(dāng)前位置、最大感知半徑、感知方向和最大感知角度，角度調(diào)整量初始化為0。

輸出 節(jié)點vi的最終感知方向。

(1)初始化時間步長計數(shù)器t=0;

(2)計算節(jié)點vi的方向可調(diào)感知模型的質(zhì)心坐標PVi(t);

(3)計算節(jié)點vi友鄰節(jié)點集合Φi，X為集合Φi中包含的元素數(shù)目;

(4)while(1)

3 算法仿真及分析

通過在Matlab上進行一系列的仿真實驗對本文提出的有向傳感器網(wǎng)絡(luò)低冗余覆蓋算法進行驗證。實驗環(huán)境及參數(shù)取值見表1。

表1 實驗環(huán)境及參數(shù)取值

按照表1所設(shè)定的實驗參數(shù)進行實驗，分別記錄每個時間步長網(wǎng)絡(luò)的覆蓋率以及網(wǎng)絡(luò)中處于激活狀態(tài)的節(jié)點個數(shù)。圖3為網(wǎng)絡(luò)中活躍節(jié)點個數(shù)隨時間變化曲線。圖4顯示了采用PFCEA算法與采用本文算法在初始覆蓋率為65%，其它參數(shù)一樣的情況下區(qū)域覆蓋性能增強情況。從圖3和圖4可以看出，本文的算法和和PFCEA算法相比，最終的覆蓋增強效果雖然差別不大，但是覆蓋增強的效率卻有明顯的提高，由30個時間步長縮短為25個時間步長，提高了16．7個百分點，同時利用更少的節(jié)點達到了同樣令人滿意的覆蓋增強效果。

圖3 網(wǎng)絡(luò)中活躍結(jié)點個數(shù)在覆蓋增強過程中的變化曲線

圖4 網(wǎng)絡(luò)中活躍結(jié)點個數(shù)在覆蓋增強過程中的變化曲線

圖5顯示了不同節(jié)點規(guī)模對FFLRCA算法覆蓋增強效果的影響。可以看出，當(dāng)R，2α等其它參數(shù)一定時，隨著節(jié)點規(guī)模N的增大，F(xiàn)FLRCA算法對覆蓋率的增強效果增加到一定程度后開始較少。例如N=150時，網(wǎng)絡(luò)的初始覆蓋率已經(jīng)達到了81．94%，相鄰傳感器節(jié)點之間形成覆蓋盲區(qū)的概率降低，F(xiàn)FLRCA算法的覆蓋增強性能開始消弱。

圖5 節(jié)點個數(shù)N對增強效果的影響，其它參數(shù):R=60，α =45°

圖6顯示了不同節(jié)點最大感知角度2α對FFLRCA算法覆蓋增強效果的影響。當(dāng)節(jié)點最大感知角度越小，單個節(jié)點的覆蓋區(qū)域越小，相鄰節(jié)點之間形成重疊區(qū)域的可能性就越小，F(xiàn)FLRCA算法的效果就不顯著，隨著節(jié)點感知角度的增加，N=110，R=40 m，網(wǎng)絡(luò)覆蓋率最高可提升15．1%;隨著節(jié)點感知角度的繼續(xù)增加，F(xiàn)FLRCA算法帶來的覆蓋增強效果降低。

圖6 節(jié)點最大感知角度2α對增強效果的影響，其它參數(shù):R=40，N=110

4 結(jié)束語

本文主要研究有向傳感器網(wǎng)絡(luò)中的區(qū)域覆蓋增強問題。在建立改進型的方向可調(diào)感知模型后，提出一種基于虛擬力的低冗余覆蓋增強算法。通過引入“虛擬力”以及虛擬力和調(diào)整角度之間的關(guān)系模型，利用節(jié)點之間的斥力逐漸消除網(wǎng)絡(luò)中的感知重疊區(qū)和盲區(qū)，最終實現(xiàn)節(jié)點的快速調(diào)整和區(qū)域的高效覆蓋。本文通過一系列實驗證明了FFLRCA算法的有效性，并詳細的分析了節(jié)點規(guī)模、最大感知角度對FFLRCA算法增強效果和執(zhí)行效率提高程度的影響。

[1]Rita Cucchiara．Multimedia Surveillance Systems[C]//Proc of the ACM VSSN2005，New York:ACM Press，2005:1 －10．

[2]Zou Y，Chakrabarty K．Sensor Deployment and Target Localization in Distributed Sensor Networks[J]．ACM Transactions on Embedded Computing Systems，2004，3(1):61 －91．

[3]Ma H D，Liu Y H．On Coverage Problems of Directional Sensor Networks[C]//LNCS 3794:Proc of the Int Conf on Mobile Ad-Hoc and Sensor Networks Berlin:Springer，2005:721 －731．

[4]Tao D，Ma H D，Liu L．Coverage-Enhancing Algorithm for Directional Sensor Networks[C]//Stojmenovic I，Cao JN，eds Proc of the 2nd Int’1 Conf on Mobile Ad-Hoc and Sensor Networks Berlin:Springer-Verlag，2006:256 －267．

[5]Khatib O．Real-Time Obstacle Avoidance for Manipulators and Mobile Robots Research[J]．The International Journal of Robotics Research，1986，5(1):90 －98．

[6]陶丹，馬華東，劉亮．視頻傳感器網(wǎng)絡(luò)中路徑覆蓋增強算法研究[J]．電子學(xué)報，2008，36(7):1291 －1296．

[7]肖甫，王汝傳，葉曉國，等．基于改進勢場的有向傳感器網(wǎng)絡(luò)路徑覆蓋增強算法[J]．計算機研究與發(fā)展，2009，46(12):2126－2133．

[8]李石堅，徐從富，吳朝暉，等．面向目標跟蹤的傳感器網(wǎng)絡(luò)布局優(yōu)化及保護策略[J]．電子學(xué)報，2006，34(1):71 －76．

[9]Zou Y，Chakrabarty K．Sensor Deployment and Target Localization in Distributed Sensor Networks[J]．ACM Trans on Embedded Computing Systems，2004，3(1):61 －91．

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

[11]溫俊，蔣杰，竇文華．公平的有向傳感器網(wǎng)絡(luò)方向優(yōu)化和節(jié)點調(diào)度算法[J]．軟件學(xué)報，2009，20(3):644 －659．

[12]Habib M Ammari，Sajal K Das．A Study of K-Coverage and Measures of Connectivity in 3D Wireless Sensor Networks[J]．IEEE Transactions on Computers，2010，59(2):243 －256．