秦寧寧,許 健,金 磊

(江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 無(wú)錫 214122)

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

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

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

1 問題陳述

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

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

1.2 閉合性

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

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

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

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

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

1.3 柵欄覆蓋的分類

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

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

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

2 庫(kù)恩匹配(KM)

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

2.1 基本概念

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

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

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

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

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

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

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

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

3.2 匹配約束

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

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

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

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

(1)

則頂標(biāo)修改法則為:

(2)

3.3 KM匹配

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

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 計(jì)算slack,更新T1和T2對(duì)應(yīng)序號(hào)處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,對(duì)R-path取反可以使得匹配邊數(shù)量增加1條。因此,滿足n～R-path=m-1的R-path取反,即為最優(yōu)匹配。u_all表示輸出參與匹配的邊權(quán)值總和。篇幅原因?qū)ふ以鰪V路徑函數(shù)Search_R-path的搜索過(guò)程不做描述,詳細(xì)過(guò)程可參閱文獻(xiàn)[7-8]。

3 KSDE算法

3.1 基本思路

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

3.2 選擇框的設(shè)計(jì)

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

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

3.3 bar_alter位置的選擇

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

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

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

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

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

定義13(孤立節(jié)點(diǎn)) 在給定select_box(k,t)內(nèi),與節(jié)點(diǎn)縱坐標(biāo)均值的距離大于選擇框?qū)挾鹊囊话氲墓?jié)點(diǎn)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é)點(diǎn)分布情況,對(duì)于不存在孤立節(jié)點(diǎn)的select_box(k,t),其bar_alter的位置可以采用節(jié)點(diǎn)坐標(biāo)均值法進(jìn)行確定。而對(duì)于存在孤立節(jié)點(diǎn)的select_box(k,t),其bar_alter的位置計(jì)算可描述如下:

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

接著,基于節(jié)點(diǎn)與模糊位置的垂直距離,取距其最近的n_slot個(gè)傳感器節(jié)點(diǎn)遞減重排,采用指數(shù)平滑法對(duì)模糊位置進(jìn)行精確調(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)計(jì)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)向上步進(jìn)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用來(lái)存放各分區(qū)最終采用的匹配對(duì)應(yīng)關(guān)系。u_part用來(lái)存儲(chǔ)各個(gè)分區(qū)節(jié)點(diǎn)最小移動(dòng)距離和。u_best_average為參與算法的節(jié)點(diǎn)的平均移動(dòng)距離。根據(jù)MATCH選擇節(jié)點(diǎn)進(jìn)行移動(dòng),將剩下的節(jié)點(diǎn)置于休眠狀態(tài),實(shí)現(xiàn)以少量節(jié)點(diǎn)完成弱柵欄覆蓋,得到匹配效果展示如圖4所示。

圖4 KSDE匹配效果圖

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

4.1 實(shí)驗(yàn)說(shuō)明

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

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

4.2 對(duì)比分析-節(jié)點(diǎn)平均移動(dòng)

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

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

圖5 節(jié)點(diǎn)數(shù)目對(duì)平均移動(dòng)距離的影響

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

4.3 對(duì)比分析-閉合性

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

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

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

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

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

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

節(jié)點(diǎn)在r的不同取值時(shí)的平均移動(dòng)距離情況如圖7所示。

圖7 節(jié)點(diǎn)半徑對(duì)平均移動(dòng)距離的影響

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

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

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

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

圖8 select_width對(duì)節(jié)點(diǎn)平均移動(dòng)距離的影響

5 總結(jié)

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