秦寧寧,許 健,金 磊

(江南大學(xué)輕工過程先進控制教育部重點實驗室,江蘇 無錫 214122)

不同于在整個網(wǎng)絡(luò)的截面處建立鏈狀覆蓋帶的柵欄覆蓋,弱柵欄是一種分區(qū)不連續(xù)的鏈狀結(jié)構(gòu)。由于初始傳感器節(jié)點分布的隨機性,需要部分傳感器節(jié)點移動至合適位置,以構(gòu)建柵欄。如何在節(jié)點的移動距離與柵欄質(zhì)量上,取得性能的折中平衡,是柵欄覆蓋中的一個關(guān)鍵問題。

在柵欄覆蓋的研究中,如何在保證閉合性的同時,最大限度地減少傳感器節(jié)點的總移動距離,研究人員提出了很多具有參考價值的方案。文獻[1]針對存在多個復(fù)雜約束的復(fù)合事件柵欄覆蓋優(yōu)化問題,提出了一種基于有效策略集的乘子法[1]ASMP(Active Set Multiplier Policy),該算法可以有效的計算閉合性,但是算法較為復(fù)雜且適用場景較少。基于經(jīng)典概率感知模型,文獻[2]通過數(shù)據(jù)融合技術(shù)構(gòu)造虛擬節(jié)點以增加節(jié)點的覆蓋范圍,雖然提高了柵欄的閉合性,但算法復(fù)雜度偏高。為了降低復(fù)雜度,毛科技等人采取分塊的模式,設(shè)計了應(yīng)用于每個分區(qū)中,且以傳感器節(jié)點偏移角為核心變量的蟻群算法[3],實現(xiàn)了分區(qū)下的K-柵欄覆蓋。作為弱柵欄研究的前身,該分區(qū)柵欄模式延長了柵欄的存在時間,保證了閉合性,但是被調(diào)度的節(jié)點移動距離較大,實時性較差。針對實時性問題,CBarrier(Centralized Barrier Algorithm)算法[4]提出:將柵欄約定為直線,以節(jié)點到直線柵欄上可能位置間的距離作為變量,構(gòu)造距離表達式。利用偏導(dǎo)來近似求解距離最小的位置,但算法對節(jié)點初始分布要求較高,普適性差。為擴展CBbarrier的應(yīng)用范圍,班東松等人提出了CBGB(Constructing Baseline Grid Barrier)[5]算法,所得柵欄的閉合性優(yōu)異,但節(jié)點移動距離的仍然較長,通信開銷的改善也不明顯。

為了在隨機部署的傳感器網(wǎng)絡(luò)中,尋找網(wǎng)絡(luò)閉合性和節(jié)點平均移動距離之間的最優(yōu)關(guān)系,論文結(jié)合最優(yōu)二分匹配中的庫恩匹配[6]KM(Kuhn Munkras),設(shè)計了一種分布式弱柵欄算法。通過將柵欄模型轉(zhuǎn)化為槽位相連的模式,將傳感器節(jié)點到槽位圓心坐標之間的距離設(shè)置為匹配權(quán)重,構(gòu)造出備選柵欄表達式,并給出KSDE(Kuhn Select-box Distribute Exponential-smoothing)算法,解決了節(jié)點及其對應(yīng)槽位點之間的最優(yōu)選擇和匹配問題,實現(xiàn)了以有效的短距離節(jié)點平均移動,取得迅速的高質(zhì)量柵欄閉合性。

1 問題陳述

1.1 網(wǎng)絡(luò)模型

在給定的被監(jiān)測的矩形區(qū)域I=B×L內(nèi),設(shè)存在N個隨機分布的同構(gòu)傳感器節(jié)點S={Sg|Sg=(xg,yg),g=1,2,3,…,N}和一個目標Target,試圖以最小被感知到的代價,穿越區(qū)域Sg。不考慮傳感器節(jié)點收發(fā)信息的能量損耗,所有節(jié)點皆為布爾感知模型,在感知半徑r內(nèi),傳感器節(jié)點都可以無差別的感知到事件發(fā)生[7]。

1.2 閉合性

閉合性是弱柵欄覆蓋的一項重要性能指標,主要考察網(wǎng)絡(luò)對直線穿越目標Target的感知能力。對幾個閉合性相關(guān)基本概念的表述,約定如下:

定義1(穿越) Target從區(qū)域I的某一邊進入,以直線的移動軌跡,抵達該邊的對邊。

定義2(點閉合性) Target以給定位置點為起點,穿越區(qū)域I,被區(qū)域內(nèi)節(jié)點感知到的概率為該起點的閉合性。

定義3(網(wǎng)絡(luò)閉合性) Target從給定邊的任意位置點出發(fā),穿越區(qū)域I,被區(qū)域內(nèi)節(jié)點感知到的概率平均值。

考慮到邊的連續(xù)性在仿真計算中實現(xiàn)困難,因此在后續(xù)的研究中,選取出發(fā)邊上具有代表性的若干位置點作為閉合性的計算樣本,近似的替代考察整個網(wǎng)絡(luò)的閉合性[8]。

1.3 柵欄覆蓋的分類

柵欄覆蓋是將傳感器節(jié)點根據(jù)要求排列成鏈狀的結(jié)構(gòu)[9]。當Target穿越區(qū)域I時,其軌跡和柵欄接觸時候,由傳感器節(jié)點及其感應(yīng)區(qū)域組成的柵欄可以完成對Target的感知。柵欄覆蓋可以分為強柵欄覆蓋和弱柵欄覆蓋兩類。

強柵欄覆蓋是由傳感器節(jié)點組成,橫跨整個網(wǎng)絡(luò)區(qū)域的鏈狀覆蓋帶。入侵的Target無論以何種軌跡試圖穿越區(qū)域I,都將被強柵欄感知。強柵欄覆蓋的特點就在于,存在至少一條柵欄完全橫跨整個區(qū)域I。如圖1(a)給出了以AB邊為起點邊,CD邊為抵達邊的強柵欄覆蓋。其AB邊上點的閉合性及其網(wǎng)絡(luò)閉合性均為1。弱柵欄覆蓋是由多條覆蓋帶組成的集合,弱柵欄覆蓋的特點在于:僅對于某些位置點,如圖1(b)中點PB1,閉合性為1,而網(wǎng)絡(luò)中由于存在穿越網(wǎng)絡(luò)而能夠不被柵欄感知的起點,因此整個網(wǎng)絡(luò)的閉合性可能小于1,如采用路線Path的點PB2。

相比于弱柵欄,強柵欄覆蓋雖然具有高閉合性,但是形成條件相對苛刻,需要調(diào)度網(wǎng)絡(luò)中節(jié)點參與移動的數(shù)目和距離更多,調(diào)度的復(fù)雜性也更高[10]。另一方面,鑒于許多應(yīng)用多集中在對熱點區(qū)域內(nèi)覆蓋性能的考量,故對網(wǎng)絡(luò)中柵欄覆蓋性能的閉合性要求,可以基于需求適當降低,因此,采用節(jié)點移動數(shù)量和平均距離更少的弱柵欄,成為了相對合理的選擇[11]。

2 庫恩匹配(KM)

KM是圖論學(xué)中解決匹配問題的一種常用的有效算法。該算法的本質(zhì),就是對兩個集合:集合M1={M11,M12,…,M1i,…,M1m}以及集合M2={M21,M22,…,M2j,…,M2m},i,j∈[1,m],各取一個元素構(gòu)成一條邊,通過定義匹配約束和邊權(quán)值,不斷尋找增廣路,以獲取具有最大權(quán)值的元素匹配方式,從而完成上述兩個等尺度集合之間的元素匹配。

2.1 基本概念

在描述算法過程之前,需要預(yù)先約定幾個必需的圖論概念如下。

定義4(匹配) 為M1和M2中滿足匹配要求的兩個元素建立聯(lián)系的過程稱為匹配。

定義5(未匹配邊) 由分別源自集合M1和M2中具有一一映射關(guān)系的兩個元素M1i和M2j組成,若M1i和M2j構(gòu)成的邊滿足匹配約束條件,但是尚未進行匹配,則該邊稱為未匹配邊。

定義6(匹配邊) 對未匹配邊進行匹配操作后,該邊被稱為匹配邊。KM算法中得到匹配邊的方法是對需要進行匹配的未匹配邊取反。給定一個一維數(shù)組Match記錄匹配邊兩邊元素的信息,如M1i和M2j構(gòu)成一組匹配邊,則Match(j)=i。

定義7(完美匹配) 若M1和M2中所有元素之間,恰好可以成對的構(gòu)成匹配邊,那么所有這樣的匹配邊組成的集合就稱為完美匹配。特別的,對于匹配邊邊權(quán)總和最大的完美匹配,被稱為最優(yōu)匹配。

定義8(交錯路) 是一條在M1和M2之間構(gòu)造的路徑C-path,且該路徑滿足匹配邊和未匹配邊交替出現(xiàn)的特點。

定義9(增廣路) 若C-path的起點元素和終點元素均未包含在匹配邊上,則該路徑被稱為增廣路,記作R-path。在R-path中,匹配邊的數(shù)量被記為nR-path,顯然nR-path=n～R-path-1。其中～R-path表示對R-path取反,即匹配邊和未匹配邊的匹配屬性互換。

定義10(頂標) 在集合M1和M2中,為每個元素定義一個特征參數(shù)作為頂標,分別記作LM1(i)和LM2(j),其中i,j∈[1,m],表示兩個集合中的各個元素。頂標通常被用在算法中,作為匹配的約束變量。

3.2 匹配約束

定義11(邊權(quán)) 定義組成邊的兩個元素M1i和M2j之間彼此的傾向程度為邊權(quán),記作u(i,j)。所有的邊權(quán)組成的集合記作u={u[i,j]|i,j∈[1,m]}。

定義12(匹配約束) 兩個集合中的元素間能進行匹配的條件。在KM中,M1和M2之間匹配約束為滿足條件LM1(i)+LM2(j)=u(i,j)。

規(guī)則1(頂標修改法則) 尋找R-path過程中,若經(jīng)過M1和M2中的元素序號集合分別為T1和T2,令:

slack=min{LM1(i)+LM2(j)-u(i,j),i∈T1,j?T2}

(1)

則頂標修改法則為:

(2)

3.3 KM匹配

KM算法實質(zhì)是按照順序遍歷M1中的每個元素,在匹配法則的約束下,為算法結(jié)束前的每一個元素,尋找一條R-path。通過判斷～R-path是否為完美匹配,以此作為算法結(jié)束標識。對于給定具有m個元素集合M1,M2及邊權(quán)u,可將KM匹配過程描述如下:

Algorithm1KM(M1,M2,u,m)

Line 1 初始化:LM1(i)=max{u(i,?)|i∈[1,m]},LM2=O1×m,R-path=?,Match=Om×1

Line 2 foro=1:m

Line 3 (R-path,T1,T2)=Search_R-path(M1(o),R-path)

Line 4 if(R-path==?)

Line 5 計算slack,更新T1和T2對應(yīng)序號處LM1與LM2的取值,即LM1(T1)和LM2(T2)

Line 6 goto Line 3

Line 7 else if(n～R-path==m-1)

Line 8 break

Line 9 else

Line 10R-path=～R-path

Line 11 continue

Line 12 end

Line 13 end

Line 14 end

Line 15R-path=～R-path

Line 16 基于～R-path,確定Match

Line 18 return Match,u_all

由于R-path的未匹配邊比匹配邊的數(shù)量多1,對R-path取反可以使得匹配邊數(shù)量增加1條。因此,滿足n～R-path=m-1的R-path取反,即為最優(yōu)匹配。u_all表示輸出參與匹配的邊權(quán)值總和。篇幅原因?qū)ふ以鰪V路徑函數(shù)Search_R-path的搜索過程不做描述,詳細過程可參閱文獻[7-8]。

3 KSDE算法

3.1 基本思路

為了兼顧網(wǎng)絡(luò)閉合性與節(jié)點平均移動成本的雙重增益,論文設(shè)計了一種分布式弱柵欄覆蓋算法KSDE。KSDE將整個區(qū)域分成n_part個長度為select_length=B/n_part子區(qū)域I(k),k∈[1,n_part]。在每個子區(qū)域I(k)內(nèi)選擇部分傳感器節(jié)點移動,構(gòu)造一條柵欄,剩下的節(jié)點進入休眠狀態(tài)。最經(jīng)濟的節(jié)點排列方式顯然為節(jié)點之間相距2r。為便于算法設(shè)計,將節(jié)點移動后的位置模擬成圓形槽位,槽位圓心坐標集為Slot,槽位半徑rs=r,則形成柵欄所需要的槽位數(shù)量為n_slot=floor(select_length/2r),其中floor為向上取整函數(shù)。算法將利用KM匹配,為每個子區(qū)域I(k)內(nèi)的節(jié)點,找出一種移動到槽位距離和最小的節(jié)點選擇策略,及其與槽位匹配的方法。算法采用分布式設(shè)計,各個子區(qū)域互不影響,并行尋找屬于自己的匹配策略,構(gòu)建自己區(qū)域內(nèi)部的柵欄。

3.2 選擇框的設(shè)計

將給定區(qū)域I劃分成若干個子區(qū)域,可以將全局搜索柵欄位置的工作,轉(zhuǎn)化成多段柵欄子段構(gòu)建的過程。對于每個子區(qū)域I(k)而言,設(shè)置一個從底部向上,寬度為select_width,且以d為步長的選擇框select_box(k,t),其中t={t|select_box(k,t)?I,t∈Z+}為步數(shù)標識,若select_box(k,t)內(nèi)包含Nsec個節(jié)點的子集Ssec={Ssec_i|1≤i≤Nsec}。分區(qū)選擇框步進過程如圖2所示。

圖2 I的分區(qū)和選擇框步進示意圖(n_part=5)

3.3 bar_alter位置的選擇

在給定的select_box(k,t)中,bar_alter的縱軸位置,直接決定著所形成柵欄的位置,關(guān)系著節(jié)點移動的距離,在不引起混淆的情況下,論文以bar_alter同時表征備選柵欄的縱坐標位置。因此bar_alter的確定應(yīng)能對節(jié)點分布具有自適應(yīng)性能,應(yīng)盡量避免個別孤立節(jié)點對bar_alter位置確定的偏離影響。如圖3所示,S1～S7可以通過較少的移動,形成一條柵欄bar_alter。如果采用節(jié)點縱軸平均法計算備選柵欄,孤立節(jié)點S8,S9,S10會導(dǎo)致bar_alter向上偏移成為bar_alter′,為構(gòu)建柵欄bar_alter′引發(fā)的節(jié)點移動距離和,明顯較構(gòu)建bar_alter有所增加。因此,需要首先對孤立節(jié)點的存在情況進行判斷。

3.3.1 孤立節(jié)點的判定

由圖3可知,孤立節(jié)點的存在直接影響bar_alter選擇的合理性。

圖3 節(jié)點不均勻分布下對備選柵欄的影響

孤立節(jié)點的定義及條件如下:

定義13(孤立節(jié)點) 在給定select_box(k,t)內(nèi),與節(jié)點縱坐標均值的距離大于選擇框?qū)挾鹊囊话氲墓?jié)點Ssec_h(xsec_h,ysec_h)。其判斷條件為:?Ssec_h(xsec_h,ysec_h)∈select_box(k,t)且滿足式(2)成立:

(3)

3.3.2 bar_alter的確定

根據(jù)內(nèi)部節(jié)點分布情況,對于不存在孤立節(jié)點的select_box(k,t),其bar_alter的位置可以采用節(jié)點坐標均值法進行確定。而對于存在孤立節(jié)點的select_box(k,t),其bar_alter的位置計算可描述如下:

首先,采用加權(quán)平均法進行宏觀定位。將select_box(k,t)分成p塊,統(tǒng)計每個塊中節(jié)點的個數(shù)Ve及節(jié)點縱坐標和Yee∈[1,p],通過加權(quán)平均得到bar_alter的模糊位置。

接著,基于節(jié)點與模糊位置的垂直距離,取距其最近的n_slot個傳感器節(jié)點遞減重排,采用指數(shù)平滑法對模糊位置進行精確調(diào)整,得到bar_alter的精確位置。

綜上,bar_alter位置的自適應(yīng)確定算法可描述為:

Algorithm2Bar_Alter(select_box(k,t),Ssec,p,a)

Line 2 基于定義13,搜索Ssec_h

Line 3 if(Ssec_h≠?)

Line 4 基于select_box(k,t)和p,統(tǒng)計Ve和Ye

Line 7 for(e=1:n_slot)

Line 9 end

Line 10 end

Line 11 return bar_alter

3.5 算法流程

Algorithm3KSDE

Line 1 參數(shù)初始化I,S,select_width,n_part,n_slot,a,d,p,r

Line 2u_part=∞n_part×1,Match=O1×n_slot,MATCH=On_part×n_slot,u_best=0,pass=0

Line 3 fork=1:n_part

Line 4t=1

Line 5 選擇框初始化select_box(k,t)

Line 6 while(select_box(k,t)?I)

Line 7 基于select_box(k,t),建立子集Ssec

Line 8 bar_alter=Bar_Alter(select_box(k,t),Ssec,p,a)

Line 11 if(|pass|

Line 12 MATCH(k)=Match

Line 13u_part(k)=|pass|

Line 14 end

Line 15 select_box(k,t)向上步進d,t++

Line 16 end

Line 18u_best_average=u_best/(n_part·n_slot)

Line 19 end

Line 20 output u_best_average,MATCH

多維數(shù)組MATCH用來存放各分區(qū)最終采用的匹配對應(yīng)關(guān)系。u_part用來存儲各個分區(qū)節(jié)點最小移動距離和。u_best_average為參與算法的節(jié)點的平均移動距離。根據(jù)MATCH選擇節(jié)點進行移動,將剩下的節(jié)點置于休眠狀態(tài),實現(xiàn)以少量節(jié)點完成弱柵欄覆蓋,得到匹配效果展示如圖4所示。

圖4 KSDE匹配效果圖

4 仿真實驗

4.1 實驗說明

論文采用了MATLAB R2016b平臺進行仿真實驗。區(qū)域設(shè)置為I=B×L,其中B=300 m,L=100 m。傳感器節(jié)點集S隨機分布在區(qū)域I內(nèi),且為連通網(wǎng)絡(luò)。其他參數(shù)在實驗中不做特殊說明時,默認設(shè)置如下:N=400,n_part=6,select_width=30 m,a=0.5,p=4,d=3 m,r=3 m。

為了驗證算法的性能,將論文提出的KSDE,文獻[2]提出的ImPCO,文獻[3]提出的CBarrier算法和基于遍歷原理的貪婪算法(Greedy)進行平均距離及閉合性的對比。Greedy遍歷精度設(shè)置如下:選擇框?qū)挾纫?1 m 為間距遍歷4 m～50 m,選擇框垂直步進步長細化到0.01 m,以近似模擬遍歷所在子區(qū)域的所有情況。鑒于實驗數(shù)據(jù)的隨機性,為保證實驗比較的公平性,所有實驗數(shù)據(jù)均采用20次獨立實驗的均值[12]。

4.2 對比分析-節(jié)點平均移動

對于傳感器網(wǎng)絡(luò)而言,節(jié)點移動的距離直接關(guān)系著網(wǎng)絡(luò)的能耗,對網(wǎng)絡(luò)壽命的影響至關(guān)重要。本實驗通過節(jié)點數(shù)量的改變調(diào)控網(wǎng)絡(luò)規(guī)模,考察在KSDE,CBarrier,ImPCO,和Greedy 4種算法中,網(wǎng)絡(luò)規(guī)模對節(jié)點平均移動距離的影響,以此間接評估算法在不同規(guī)模的網(wǎng)絡(luò)中能量消耗的有效性。實驗設(shè)定網(wǎng)絡(luò)節(jié)點的規(guī)模數(shù)為N∈[200,550],并以50作為節(jié)點數(shù)目的增長間距進行實驗。

從圖5給出的實驗數(shù)據(jù)可以看出:隨著節(jié)點數(shù)N的增加,4種算法的平均移動距離均呈現(xiàn)出下降的整體趨勢,即網(wǎng)絡(luò)以節(jié)點投入數(shù)目的增加可以換取節(jié)點平均移動距離的減小,從而降低單個節(jié)點的平均移動能耗。論文提出的KSDE與已有的CBarrier及ImPCO相比,具有更小的平均移動距離(小于6 m),能以小于0.4 m的距差,較為穩(wěn)定的逼近理想情況的Greedy算法。

圖5 節(jié)點數(shù)目對平均移動距離的影響

節(jié)點數(shù)目的投入可以贏得平均移動距離的減小,從而實現(xiàn)閉合性能的同時控制能耗,但對于大規(guī)模網(wǎng)絡(luò)(N≥350)而言,4種算法的節(jié)點平均移動距離的減小增益逐漸減弱,甚至在CBarrier算法中出現(xiàn)負增長,當N≥400時ImPCO節(jié)點的平均移動距離逐漸穩(wěn)定,說明此時對于應(yīng)用ImPCO算法的網(wǎng)絡(luò)此時已經(jīng)逐漸飽和,因此應(yīng)注意網(wǎng)絡(luò)規(guī)模與移動節(jié)點能耗之間的平衡利用。

4.3 對比分析-閉合性

網(wǎng)絡(luò)閉合性的表現(xiàn),直接決定著算法所構(gòu)建的柵欄的有效性。在給定的默認網(wǎng)絡(luò)場景中,本實驗將通過調(diào)節(jié)網(wǎng)絡(luò)分區(qū)目數(shù)n_part∈[3,10],評估基于不同數(shù)目的分區(qū)劃分下,包括KSDE,CBarrier,ImPCO 和Greedy在內(nèi)4種算法所形成的弱柵欄,能提供的網(wǎng)絡(luò)閉合性能。

實驗以網(wǎng)絡(luò)底邊作為起點邊,頂邊為終點邊。選擇起點邊的兩個端點及其中間點,分別作為測試起點,每個測試起點均引出一條射線作為閉合測試使用,并以1°為旋轉(zhuǎn)單位,掃描整個終點邊,測試射線被各子區(qū)域柵欄感知到的比率,就是該測試起點的閉合性,所有測試起點閉合性的均值為網(wǎng)絡(luò)閉合性。

分區(qū)數(shù)目在3種算法中,對網(wǎng)絡(luò)閉合性的影響情況,如圖6所示?；趯嶒灁?shù)據(jù)可見,隨著分區(qū)數(shù)目n_part的增加,4種算法的網(wǎng)絡(luò)閉合性都表現(xiàn)出整體下降的趨勢。在n_part較小時,4種算法的網(wǎng)絡(luò)閉合性隨n_part的增大逐漸降低;進一步,隨著n_part 的持續(xù)的增長,弱柵欄斷續(xù)現(xiàn)象趨于明顯,會在一定程度上削弱網(wǎng)絡(luò)的閉合性,在圖中的體現(xiàn)為:當n_part>6時,各算法閉合性的下降趨勢均出現(xiàn)不穩(wěn)定波動。由此可知,當分區(qū)數(shù)較少時,某條柵欄的位置會對整體閉合性產(chǎn)生非常大的影響,經(jīng)過后續(xù)擴充樣本試驗,既增加實驗次數(shù)后,分區(qū)數(shù)較小時網(wǎng)絡(luò)覆蓋率的曲線波動幅度明顯降低。就網(wǎng)絡(luò)閉合性曲線的整體趨勢而言,KSDE以穩(wěn)定高于80%的閉合性能,在4種算法中的表現(xiàn)最佳,且隨著分區(qū)數(shù)的增加閉合性平滑遞減,穩(wěn)定性較好;CBarrier,ImPCO及Greedy的閉合性能相對不穩(wěn)定,隨著n_part的增加,3個算法的閉合性能交替加速下降。

圖6 分區(qū)對網(wǎng)絡(luò)閉合性的影響情況

4.4 性能分析-節(jié)點半徑

節(jié)點半徑的增加會擴大覆蓋的范圍,顯然可以有效減少給定子區(qū)域內(nèi)構(gòu)建柵欄所需的節(jié)點總數(shù),但同時地會影響參與匹配的節(jié)點選擇。實驗在默認場景中,通過改變節(jié)點半徑r,分析探究節(jié)點感應(yīng)能力的變化,對節(jié)點在平均移動距離的影響。

節(jié)點在r的不同取值時的平均移動距離情況如圖7所示。

圖7 節(jié)點半徑對平均移動距離的影響

當r<4 m時,呈現(xiàn)出隨著節(jié)點感應(yīng)能力提高,節(jié)點平均移動減少的趨勢,且減小的趨勢逐漸變緩。隨著節(jié)點感應(yīng)范圍的進一步增大,節(jié)點參與匹配的偶然性隨之增大,r和平均移動距離的之間不再具有穩(wěn)定的變化關(guān)系,而出現(xiàn)齒狀曲線?？梢?對于r的設(shè)定并非越大越優(yōu),鑒于實驗數(shù)據(jù)的分析,在r∈[3 m,4 m]時,是比較合適的取值范圍。

4.5 性能分析-選擇框?qū)挾?/h3>

增加選擇框?qū)挾萻elect_width,對算法效率而言,增大的框內(nèi)區(qū)域可以更快確定分區(qū)內(nèi)柵欄,減少算法運行時間;但從算法能效而言,增大的框內(nèi)區(qū)域勢必增加更多的冗余節(jié)點參與匹配,影響備選柵欄的位置,進而擴大節(jié)點平均移動距離。本實驗在給定默認實驗場景中,通過改變select_width,分析前者對節(jié)點平均移動距離的影響。

從圖8中節(jié)點平均移動距離的變化情況可以看出,隨著select_width的增加,節(jié)點平均移動距離呈現(xiàn)出近似階梯狀的上升趨勢。根據(jù)KSDE關(guān)于柵欄的確定方式可知:距離柵欄越遠的節(jié)點對柵欄的生成影響越小,因此當select_width增大到某個值時,新進入選擇框的節(jié)點對節(jié)點匹配的影響將趨近于零。在圖中的表現(xiàn)為節(jié)點平均移動距離上升趨勢在select_width≥40后消失,此后的節(jié)點的平均移動距離不再受到select_width變化的影響并逐漸穩(wěn)定在4.28 m左右。

圖8 select_width對節(jié)點平均移動距離的影響

5 總結(jié)

針對弱柵欄覆蓋的覆蓋率和移動距離相互制約的關(guān)系,論文提出了一種分布式的弱柵欄覆蓋節(jié)點選擇算法KSDE,力求以較小的移動損耗,選擇合適的節(jié)點參與柵欄構(gòu)建,贏得更高效的網(wǎng)絡(luò)閉合性。同時進一步深入探究了傳感器節(jié)點數(shù)量、分區(qū)數(shù)等參數(shù)對平均移動距離影響關(guān)系,實現(xiàn)了在傳感網(wǎng)絡(luò)中,構(gòu)建弱柵欄覆蓋所需要傳感器節(jié)點的合理選擇。在同構(gòu)傳感網(wǎng)絡(luò)中,KSDE構(gòu)建弱柵欄覆蓋具有不錯的表現(xiàn),但在異構(gòu)傳感網(wǎng)絡(luò)中,KSDE構(gòu)建弱柵欄覆蓋的性能還需要繼續(xù)探究。