基于目標分層和路徑分割策略的掃描覆蓋算法

張景昱,劉京菊,葉春明

(國防科技大學 電子對抗學院,合肥 230037)

0 概述

目前,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)在醫(yī)療、工業(yè)以及軍事領(lǐng)域得到廣泛應用,覆蓋問題是無線傳感器網(wǎng)絡(luò)研究中最重要的問題之一,常用的覆蓋問題模型有區(qū)域覆蓋、柵欄覆蓋和掃描覆蓋[1]。區(qū)域覆蓋通過在整個區(qū)域內(nèi)部署傳感器節(jié)點,使得區(qū)域所有位置均處于傳感器節(jié)點的感知范圍內(nèi)。區(qū)域覆蓋雖然可以滿足許多場景的需求,但由于其對傳感器數(shù)量和感知能力存在硬性要求,在多數(shù)目標確定的情境下會造成極大的資源浪費。柵欄覆蓋通常應用于區(qū)域內(nèi)的入侵者檢測,其屬于一種靜態(tài)覆蓋模型,不能對特定目標進行監(jiān)視[2]。

掃描覆蓋的概念最早來源于機器人的路徑規(guī)劃問題,在路徑規(guī)劃過程中,機器人需要經(jīng)過預先設(shè)定的一系列目的地,使得所有目的地都包含在最終設(shè)定的路徑中,同時使得總路徑最短。由于存在不同的目標和限制條件,使得路徑規(guī)劃方法不能直接應用于無線傳感器網(wǎng)絡(luò)的覆蓋問題研究中?？紤]到現(xiàn)有硬件技術(shù)可以使得傳感器節(jié)點具有移動能力,同時需要覆蓋的目標也具有一定的時間容忍性,研究人員即提出掃描覆蓋的概念。如今,掃描覆蓋已經(jīng)被應用于很多場景中,例如,在森林火災的監(jiān)控過程中,通過提前勘察等手段獲得整個森林可能發(fā)生火災的區(qū)域,在這些位置部署移動傳感器節(jié)點以周期性地對區(qū)域進行感知,從而極大程度地提高森林火災的預警能力。

近年來,學者們提出了多種關(guān)于掃描覆蓋問題的算法,此類算法的實現(xiàn)大多集中在以最少傳感器節(jié)點數(shù)量、最短掃描周期、最短掃描路徑等為目標的場景中。研究人員將需要覆蓋的目標抽象化為興趣點(POI)點集,將掃描覆蓋問題抽象化為TSP問題進行求解,并設(shè)計合適的算法策略使其滿足場景監(jiān)視的需求[3-4]。

在實際應用場景中,不同的POI對應不同的重要程度。例如在戰(zhàn)場環(huán)境中,敵方的關(guān)鍵基地和關(guān)鍵兵種的監(jiān)視相較于其他位置而言更加重要,對這種重點位置應考慮增加監(jiān)視時間。因此,需要給POI賦予不同的權(quán)重值進行區(qū)分,同時為其分配不同的掃描覆蓋時間。但是,目前針對權(quán)重節(jié)點掃描覆蓋策略研究較少,基本上將權(quán)重節(jié)點所在掃描路徑的數(shù)量作為其權(quán)重值進行處理。此種方法雖然可以增加對權(quán)重節(jié)點的掃描時間,但是也會增加許多無效路徑,使得部署代價過高。在掃描路徑的規(guī)劃過程中,掃描路徑、路徑的覆蓋效率等也需要根據(jù)實際場景進行設(shè)計。

本文在權(quán)重目標條件中加入返回基站的時間限制,提出一種帶有權(quán)重目標和返回時間約束的掃描覆蓋問題WTSC,并證明其為NP-hard問題。針對該問題,本文設(shè)計一種目標分層策略用以區(qū)分權(quán)重POI,同時部署基站的位置。針對每個層級的POI,提出基于貪婪策略的TSP路徑計算方法,獲取每個層級的初始路徑并針對初始路徑設(shè)計一種環(huán)路分割策略,以得到所有移動傳感器的部署位置。

1 相關(guān)研究

近年來,學者們關(guān)于掃描覆蓋問題進行了較多的研究。文獻[5]較早提出掃描覆蓋的概念,其設(shè)計M-WSN中最少感知節(jié)點的掃描覆蓋問題并計算滿足需求的最少移動感知節(jié)點數(shù)量。該文證明了掃描覆蓋問題是一個NP-hard問題,提出集中式算法CSweep和分布式算法DSweep 2種解決方法,但是這2種方法的應用場景過于理想,路徑利用效率較低。文獻[6]分析得出,CSweep算法難以應用于POI需求不同的情況,而Dsweep算法雖然靈活,但是由于其策略原因使得一部分節(jié)點長期被忽視?，F(xiàn)有研究通常只關(guān)注對POI對的訪問,對于獲取到POI數(shù)據(jù)后如何進行匯總分析并未說明。因此,文獻[6]將上述兩方面問題相結(jié)合,對比車輛路徑問題,提出一種基于聚類的掃描覆蓋算法FCSC。該算法先通過聚類將位置近的POI進行分類,然后使用啟發(fā)式算法生成掃描路徑。

文獻[7]研究動態(tài)傳感器和靜態(tài)傳感器同時運行實現(xiàn)掃描覆蓋的問題,并提出2個問題模型。第1個問題命名為t-Gsweep coverage,表示使用動、靜傳感器相結(jié)合的方法實現(xiàn)覆蓋,并針對其中傳感器與POI一一對應的特殊情況提出了更高效的解決方法。第2個問題是在移動傳感器能量上限已知條件下以傳感器節(jié)點數(shù)量最小為目標實現(xiàn)掃描覆蓋。文獻[8]分析了覆蓋問題中的覆蓋率,由于覆蓋的重疊區(qū)域不規(guī)則、覆蓋率很難計算,傳統(tǒng)的網(wǎng)格點方式并未考慮實際目標的分布情況,因此對于動態(tài)特征區(qū)域會耗費過多資源。文獻[8]通過定義特征點集,將傳統(tǒng)的區(qū)域覆蓋問題轉(zhuǎn)換為基于特征點集的優(yōu)化問題,針對WSNs分布式的特點,提出并行算法IWPSO,改善了傳統(tǒng)算法容易陷入局部最優(yōu)的不足。

文獻[9]提出了MinExpand和Osweep 2種方法解決掃描覆蓋問題。MinExpand方法不停添加新的POI到當前路徑中,直至路徑不能再添加新的POI,在添加過程中只將距離當前點最近的點作為候選點,再創(chuàng)建新的路徑,直至所有POI被添加至路徑中。Osweep方法是針對CSweep的一種改進,在掃描周期限制下,其將整個路徑分割成一定數(shù)量的環(huán)路。文獻[10]提出PPA算法,根據(jù)不規(guī)則網(wǎng)格分割區(qū)域算法(TIDA)的啟發(fā),分析每個網(wǎng)格內(nèi)POI的個數(shù),通過判定提前設(shè)定的平均周期、周期閥值和當前周期三者間的關(guān)系,對各個網(wǎng)格內(nèi)POI的數(shù)量進行微調(diào),以形成不同的環(huán)路并實現(xiàn)掃描覆蓋。文獻[11]將覆蓋POI目標定為線條,將線條視為點,構(gòu)建最小生成樹抽象連接圖,再將各個點之間的連接關(guān)系抽象成線段分割,增加新的分割點,對新圖分配傳感器實現(xiàn)掃描覆蓋。文獻[12]研究距離限制的掃描覆蓋問題(MinSDCSC),其算法通過將掃描路徑分割成k個部分,每個部分設(shè)置1個基站,以實現(xiàn)限制距離最短、節(jié)點數(shù)量較少的掃描覆蓋。

文獻[13]針對掃描覆蓋中掃描周期最短的問題,研究其中3種不同的情況并設(shè)計3種對應算法。CycleSplit算法解決了每個傳感器沿著預定軌跡周期運動情況下的掃描周期最短問題,HeteroCycleSplit算法解決了在傳感器節(jié)點速度不同條件下的掃描覆蓋問題,PathSplit算法解決了覆蓋目標為路徑情況下的掃描覆蓋問題。文獻[14]以掃描周期最短為目標設(shè)計了M3SR算法,該算法分別通過貪婪算法和二分算法對POI和路徑進行處理,選出滿足條件的掃描路徑。文獻[15]以掃描路徑最短為目標,提出3種不同情境下的算法。其中,cyclesplit算法解決了所有傳感器在各自環(huán)路內(nèi)單獨運行的問題,降低了OSweep算法的復雜度,Cocycle算法解決了傳感器之間協(xié)同覆蓋多目標的問題,augprim算法解決了傳感器必須返回基站傳遞消息情況下的掃描覆蓋問題。文獻[16]以傳感器節(jié)點數(shù)量最少為目標,提出PDBA算法,該算法在每條路徑上增加盡量多的POI。文獻[17]將掃描覆蓋問題轉(zhuǎn)化為TSP問題,通過將TSP問題分成2個階段進行處理實現(xiàn)了對sweep覆蓋問題的優(yōu)化求解,同時設(shè)計平衡參數(shù)解決了各個節(jié)點之間負載不均衡的問題。

帶有權(quán)重目標的掃描覆蓋研究主要針對權(quán)重點的權(quán)重值處理問題展開。文獻[18]研究了針對擁有不同權(quán)重值的目標實現(xiàn)掃描覆蓋的問題,同時保證所有節(jié)點掃描周期趨于平衡。算法設(shè)置每個傳感器的掃描周期,計算平均周期和標準差,并將權(quán)重POI的權(quán)重數(shù)值視為每個掃描周期內(nèi)的訪問次數(shù)。對于多個權(quán)重節(jié)點的情況,算法每次針對權(quán)重最大的節(jié)點進行迭代,對節(jié)點所在路徑實現(xiàn)平均分割,直至所有節(jié)點被分割完畢。文獻[19]研究了有時間限制和權(quán)重節(jié)點限制的掃描覆蓋問題,首先根據(jù)POI權(quán)重確定初始路徑,然后根據(jù)路徑數(shù)量確定傳感器數(shù)量、路徑和初始位置,隨后計算每個傳感器的速度以保證掃描周期的穩(wěn)定。同時,文獻[19]算法設(shè)計了不同的時間片段,以保證各個POI在相同時段內(nèi)不會被重復覆蓋。文獻[20]分別以節(jié)約能量和節(jié)點數(shù)量最少為目標設(shè)計掃描覆蓋算法。針對節(jié)點數(shù)量最少的問題,選擇動態(tài)與靜態(tài)節(jié)點相結(jié)合的策略,首先根據(jù)邊的長度和權(quán)重設(shè)計生成一顆最小生成樹,通過對樹進行分割處理設(shè)計動態(tài)節(jié)點路徑和靜態(tài)節(jié)點的位置。針對能量有限的問題,通過設(shè)定每個節(jié)點掃描周期內(nèi)的能量上限和能量消耗參數(shù),生成路徑的最小森林,通過每一個樹生成掃描路徑。文獻[21]針對文獻[5]算法實際運行過程中存在的缺陷進行改進,使其能在擁有權(quán)重POI情況下使用。此外,針對不同POI需要不同的處理時間和掃描周期的問題,文獻[21]提出了一種解決方法,該方法分為2個階段,第1階段確定節(jié)點數(shù)量,第2階段確定移動策略和周期。

2 問題描述

本文問題描述為:對于POI已知的區(qū)域,在不同權(quán)重POI的覆蓋需求和移動傳感器返回基站的時間約束下,以盡量小的代價實現(xiàn)一種滿足不同掃描時間要求的帶時間約束的掃描覆蓋算法。

上述問題與現(xiàn)有研究的假設(shè)相同,即當一個POI被覆蓋時當且僅當移動傳感器節(jié)點到達了此POI的位置。傳感器節(jié)點都具有相同的感知能力和運動屬性,節(jié)點之間可以構(gòu)成無線傳感器網(wǎng)絡(luò)。在將實際場景轉(zhuǎn)化為POI點集時,任何2個POI之間的距離由實際場景中兩目標之間往返實際距離決定。POI之間構(gòu)成的虛擬路徑擬定為直線路徑,路徑代價與實際最小路徑代價相同。

在掃描覆蓋問題中,最常使用的模型是t-掃描覆蓋(t-sweep coverage)模型。假設(shè)有n個移動傳感器節(jié)點,節(jié)點集合為S={s1,s2,…,sn},整個區(qū)域中有m個POI節(jié)點,節(jié)點集合為H={h1,h2,…,hm}。任意2個POI節(jié)點hi和hj之間的歐式距離di,j表示hi和hj之間的路徑代價,所有移動傳感器都以相同的速度v運動。在每個設(shè)定的間隔之間,一個POI被覆蓋當且僅當一個移動傳感器節(jié)點移動到了此POI的位置。掃描覆蓋與傳統(tǒng)覆蓋之間的差別是其不需要提供對目標的連續(xù)性覆蓋。在掃描覆蓋模型中,移動傳感器節(jié)點只需要對POI在設(shè)定的時間間隔內(nèi)至少覆蓋一次,這樣就能保證所有活動都能夠在一定的延遲范圍內(nèi)被檢測到。基于上述假設(shè),t-掃描覆蓋模型定義如下:

定義1(t-掃描覆蓋模型) 一個POI滿足t-掃描覆蓋,當且僅當此POI每隔t時間被策略F規(guī)劃下的移動傳感器節(jié)點至少覆蓋一次。

在定義1中,策略F即為移動傳感器的路徑規(guī)劃策略,它規(guī)劃了移動傳感器節(jié)點在某一恒定速率下移動,并保證在整個運行過程中所有POI均能滿足t-掃描覆蓋。當一個POI滿足t-掃描覆蓋時,時間間隔t就被定為這個POI的掃描周期。在實際過程中,每個POI可能具有不同的掃描周期,只要所有ti均在統(tǒng)一設(shè)定的最大掃描周期Tmax內(nèi),就可認為所有的POI實現(xiàn)了t-掃描覆蓋。

設(shè)定每個POI均有權(quán)重值,權(quán)重集合為W={w1,w2,…,wm},wmax和wmin分別表示POI的最大權(quán)重值和最小權(quán)重值。同時,整個場景中至少設(shè)置一個基站(sink node)用來處理每個周期內(nèi)移動傳感器收集到的POI信息。移動傳感器在掃描周期內(nèi)至少需要經(jīng)過1次基站,即每個移動傳感器都具有一個返回基站時間約束。因此,帶有權(quán)重和返回時間約束的t-掃描覆蓋(Weighted and Time-constrainedt-Sweep Coverage,WTSC)模型定義如下:

在WTSC模型下,需要設(shè)計一種移動節(jié)點的運行策略F來解決掃描覆蓋問題,而在策略的設(shè)計過程中,需要在滿足覆蓋要求的前提下盡可能縮短掃描路徑長度,以減少移動傳感器節(jié)點的數(shù)量。

WTSC為一個NP-hard問題,其問題證明可以類比于多人旅行商問題(MTSP)。

3 算法設(shè)計

針對帶有權(quán)重和返回時間限制的掃描覆蓋問題,本文提出一種基于目標分層和路徑分割的掃描覆蓋算法TLPS,該算法的設(shè)計思路可以類比于MTSP問題的解決方法,首先通過將權(quán)重POI進行分層處理,將每一層的初始路徑計算視為一個TSP路徑計算,而且各個初始路徑之間互相獨立,將路徑進行匯總即可得到MTSP問題的一種解決方法。同時,需要考慮掃描覆蓋問題自身的限制,如傳感器節(jié)點的移動速度、掃描周期和返回時間等因素,因此,TLPS算法可以分為3個部分:目標分層策略,基于貪心策略的TSP路徑計算,環(huán)路分割策略。

3.1 目標分層策略

目標分層策略主要實現(xiàn)對基站位置的計算以及權(quán)重POI的分層處理。

1)基站位置的計算。在現(xiàn)有研究中,基站通常放置于權(quán)重值最高的POI位置處,這樣設(shè)置的優(yōu)點是無需額外計算掃描路徑到達基站的位置。但是,此種設(shè)計也存在一些缺陷,在權(quán)重值最高處放置POI會使得所有的掃描路徑均經(jīng)過該位置,雖然會使該位置獲得較大的覆蓋時間,但是當權(quán)重值較高的一些POI相對于此位置過于分散時,會導致其他POI只能往返于當前位置和基站之間,并不能訪問其他位置,從而產(chǎn)生極大的能量消耗,導致路徑利用率較低。

針對上述問題,本文算法將所有POI位置信息和對應的權(quán)重值相結(jié)合,計算所有POI的加權(quán)位置并作為基站位置,加權(quán)位置信息計算公式如下:

(1)

式(1)中W=∑wi為所有權(quán)重之和,基站坐標(x,y)為所有權(quán)重POI坐標的加權(quán)平均值。

(1)獲取當前POI的權(quán)重最值wmin和wmax。

(2)設(shè)置當前層的權(quán)重wcurrent=wmin,從最小權(quán)重值wmin開始,將所有權(quán)重值滿足wi≥wcurrent的POI加入到當前的權(quán)重分層中。

(3)增大wcurrent并重復第2步,直至權(quán)重分層到達wmax。

目標分層策略的具體流程如算法1所示。

算法1目標分層策略

輸入所有POI的位置和權(quán)重

輸出基站位置,POI分層

1.根據(jù)輸入,計算基站位置:

2.獲取權(quán)重最值wmin和wmax

3.令wcurrent=wmin,從wmin開始,將權(quán)重大于wcurrent的POI加入當前的權(quán)重分層中

4.得到POI分層

3.2 基于貪心策略的TSP路徑計算

本節(jié)對已經(jīng)分層完畢的各層POI設(shè)計初始化掃描路徑。針對每一層POI,初始化路徑是指包括該層所有POI位置和基站的環(huán)路?？梢詫⒁苿觽鞲衅饕暈橐晃宦眯猩?層內(nèi)所有POI視為目的地城市,而基站則為旅行商的出發(fā)城市和最終返回城市。因此,初始化掃描路徑問題可以視為多個TSP問題。

由于上述問題是一個NP-hard問題,因此不存在多項式時間內(nèi)解決該問題的算法。為了簡便計算,本文擬使用貪心策略解決此問題,每次選擇距離最近的POI作為下一目標位置,具體過程如算法2所示。

算法2基于貪心策略的TSP路徑計算算法

輸入基站位置,POI分層

輸出初始化路徑

1.計算所有POI之間的路徑代價以及所有POI到達基站的代價,得到代價矩陣WPOI

2.針對每一層POI:

3.從基站位置出發(fā),每次選擇一個當前層內(nèi)的POI,直至所有POI被訪問完畢,返回基站

4.在每次選擇下一個POI時,僅選擇當前剩余的所有層內(nèi)與當前POI之間路徑代價最小的POI作為下一位置

5.end

6.返回每一層路徑總代價和POI訪問順序,訪問順序即為初始化路徑

經(jīng)過上述基于貪心策略的TSP算法計算,可以得出所有POI的初始化掃描路徑,此部分計算得到了目標分割策略中每一層的TSP路徑,路徑之間互相獨立,將所有路徑匯總即可視為WTSP問題的一種解法。但是,上述路徑并未考慮移動傳感器速度、掃描周期以及返回時間等因素,難以解決WTSC問題,因此,需要對該掃描路徑進行進一步處理。

3.3 環(huán)路分割策略

本節(jié)對上節(jié)中得到的每一層掃描路徑進行分割處理。在現(xiàn)有研究中,對于較長的掃描路徑分割一般有2種解決方案:

2)第2種解決方案是對路徑上所有點構(gòu)建最小生成樹,通過斷開某些邊使得斷開的各個部分構(gòu)成合適大小的連通分量,對連通分量進行處理構(gòu)建環(huán)路。此種方法分割出的環(huán)路路徑利用效率高,但是對于帶有權(quán)重的POI分割效果并不理想。

本文在第2種解決方案中加入權(quán)重POI分割策略,提出一種環(huán)路分割策略,具體描述如下:

首先,計算單個移動傳感器節(jié)點在單個掃描周期內(nèi)的最大路徑代價Pmax=vt,以此作為是否分割的一個判斷參數(shù);接著,針對每一個層級的初始化路徑,以Pmax為標準,從當前路徑中權(quán)重最大的POIi開始將其作為初始分割點,判斷當前POIj的權(quán)重與當前權(quán)重層的權(quán)重值的大小關(guān)系,若當前POIj的權(quán)重大于當前權(quán)重層權(quán)重,則選擇在此處斷開,以保證當前權(quán)重節(jié)點可以滿足對應于其權(quán)重的覆蓋次數(shù),若此位置不需要斷開,則分別計算從此點開始到路徑順序中下一點以及到達基站的路徑代價length,計算公式為:

length=lengthi,j+lengthi,node+lengthj,node

(2)

其中,lengthi,j為初始分割點與當前點之間的距離,lengthi,node和lengthj,node分別為這兩點與基站間的距離。根據(jù)計算結(jié)果判斷當前l(fā)ength與Pmax的關(guān)系,若length≤Pmax,則當前點從POIj前進到路徑中下一個位置POIk;若length>Pmax,則當前點從POIj返回至路徑中上一個位置,并在此位置斷開,將此位置作為一個分割點,與上一分割點和基站之間構(gòu)成環(huán)路。若在訪問過程中所有POI都已經(jīng)被訪問過,則返回最初POI位置。最后,將從開始位置POIi到斷點位置POIj再到基站最后返回開始位置的環(huán)形路徑保存為一個分割路徑,并將當前斷點位置作為下一條環(huán)路的起始位置,沿著當前層初始路徑按照上述步驟進行分割,直至當前層所有POI均在某一條環(huán)路中。環(huán)路分割策略流程如算法3所示。

算法3環(huán)路分割策略

輸入POI分層,初始化路徑

輸出環(huán)路和移動傳感器分配結(jié)果

1.計算Pmax=vt

2.針對每一層:

3.判斷當前POIj與當前層間的權(quán)重關(guān)系

4.從權(quán)重最大的POIi位置分割,計算length

5.判斷l(xiāng)ength與Pmax的關(guān)系

6.在斷點POIj位置構(gòu)建環(huán)路,并作為下一環(huán)路的起點

7.end

按照上述方法分割完所有的路徑,得到一系列的環(huán)路,每條環(huán)路上部署一個移動傳感器節(jié)點對該路徑上的POI進行掃描覆蓋,在該覆蓋方法下,所有POI均滿足WTSC模型要求。

4 實驗驗證

4.1 實驗參數(shù)配置

在Matlab下進行實驗以驗證本文TLPS算法的性能。實驗環(huán)境為500 m×500 m的正方形區(qū)域,所有POI隨機均勻分布在此正方形區(qū)域內(nèi),POI節(jié)點權(quán)重值隨機產(chǎn)生。移動傳感器的移動速率相同,均為v,每個POI的掃描周期為相同的時間t,基站位置根據(jù)所有POI位置及權(quán)重共同計算得到。每次實驗取100次結(jié)果的平均值作為最終結(jié)果。算法性能評估參數(shù)如下:

1)平均掃描周期:所有路徑實際掃描周期的平均值。

2)移動傳感器數(shù)量:在滿足當前覆蓋要求的條件下,算法部署在整個區(qū)域的傳感器數(shù)量。

3)路徑有效率:移動傳感器實際運行路徑與理論最大運行距離之間的比值,其反映當前路徑被有效利用的程度,計算公式為:

(3)

其中,lengthmax=vt,為移動傳感器的速度與掃描周期的乘積。

4.2 實驗結(jié)果分析

本次實驗將CSweep、MinExpand、OSweep和tcwtp作為對比算法。CSweep算法通過將所有節(jié)點劃入同一條最短路徑中,分割路徑保證所有POI均可以被移動傳感器覆蓋;MinExpand算法根據(jù)當前設(shè)定的最高代價,不斷添加新的POI到當前路徑中以實現(xiàn)路徑規(guī)劃;OSweep在CSweep的基礎(chǔ)上,將整條路徑視為一條環(huán)路,不分割路徑;tcwtp算法將POI的權(quán)重視為該位置所經(jīng)過路徑的數(shù)量,以此設(shè)計所有路徑。由于上述算法均可以在相同的場景中應用且具有一定的優(yōu)化效果,因此本文選擇此4種算法作為對比算法。在實驗過程中,所有移動傳感器節(jié)點的性能相同。

在所有POI位置和權(quán)重相同的條件下,5種對比算法在移動傳感器節(jié)點速度不同時的平均掃描周期對比如圖1所示。其中,POI數(shù)量設(shè)定為100,最小權(quán)重值設(shè)置為1,高權(quán)重的節(jié)點數(shù)量為當前權(quán)重節(jié)點數(shù)量的10%,傳感器節(jié)點的移動速度為唯一變量,由0逐步增加到30。從圖1可以看出,隨著移動傳感器節(jié)點速度的增加,所有算法的平均掃描周期均下降。由于OSweep算法不對路徑進行分割,所有節(jié)點均在原路徑上運動,路徑的利用率最高,因此其掃描周期相對于其他算法最短。相較于CSweep、MinExpand和tcwtp算法,本文TLPS算法平均掃描周期更短,原因是本文算法在對初始路徑進行分割時充分考慮了單個傳感器節(jié)點的最大路徑代價。TLPS算法的平均掃描周期更短,因此,在移動傳感器節(jié)點速度相同的情況下,每個傳感器在掃描周期內(nèi)移動的距離也更短,即每個移動傳感器的能耗更少。

圖1 5種算法的平均掃描周期對比Fig.1 Comparison of average sweep period of five algorithms

在POI數(shù)量固定的情況下,平均移動傳感器節(jié)點數(shù)量隨掃描周期的變化情況如圖2所示。其中,POI數(shù)量和權(quán)重設(shè)定與上一次實驗相同,移動傳感器節(jié)點移動速度設(shè)定為20,掃描周期為唯一變量,從5逐步增加到25。從圖2可以看出,隨著掃描周期的增大,所有算法的傳感器節(jié)點數(shù)量均減少,這是由于單個傳感器節(jié)點的移動路徑增大,可以覆蓋更多的POI,因此可以減少部分傳感器節(jié)點數(shù)量。而在掃描周期相同的情況下,TLPS算法相對于不考慮權(quán)重節(jié)點的覆蓋算法而言節(jié)點數(shù)量較多,但是相對于tcwtp算法而言節(jié)點數(shù)量較少。這是由于TLPS算法在部署時對已存在的最短路徑進行分割,分割時盡可能選擇權(quán)重節(jié)點位置,這樣會降低路徑的代價,間接減少移動傳感器的數(shù)量,此外,相對于不考慮權(quán)重節(jié)點的覆蓋算法而言節(jié)點數(shù)量較多是由于其覆蓋了較多權(quán)重更高的POI,相對于其他算法,本文算法的權(quán)重節(jié)點有效覆蓋率更高。

圖2 5種算法的平均移動傳感器數(shù)量對比Fig.2 Comparison of average number of moving sensors of five algorithms

對比分析5種算法部署傳感器后的路徑有效率,在本次實驗中,POI的數(shù)量為唯一變量,從50逐步增加到250,高權(quán)重節(jié)點數(shù)量占當前權(quán)重節(jié)點數(shù)量的10%,移動傳感器的速度設(shè)定為20,掃描周期設(shè)定為15。從圖3和表1可以看出,OSweep算法的路徑有效率最高,這是由于其所有的移動傳感器均在一條路徑上移動,多余路徑最少。而TLPS算法的路徑有效率相對其他3種算法更高,這是由于該算法在分割每條路徑時參考當前路徑長度和單個傳感器最大路徑之間的關(guān)系,盡可能在每次分割時都保證路徑有效率相對更高。同時隨著POI數(shù)量的增加,TLPS算法依然能保持較高的路徑有效率,間接降低了節(jié)點部署的代價。

圖3 5種算法的路徑有效率對比Fig.3 Comparison of path efficiency of five algorithms

表1 5種算法的平均路徑有效率Table 1 Average path efficiency of five algorithms

5 結(jié)束語

本文提出一種帶有權(quán)重和返回時間限制的區(qū)域覆蓋問題,并證明其為一個NP-hard問題,針對該問題設(shè)計一種基于目標分層和環(huán)路分割的區(qū)域覆蓋算法TLPS。TLPS算法對區(qū)域內(nèi)的所有POI進行權(quán)重分層,并根據(jù)POI的位置和權(quán)重設(shè)置基站的位置。將各層路徑規(guī)劃問題轉(zhuǎn)化為TSP問題,基于貪心策略設(shè)計初始化路徑。在此基礎(chǔ)上,根據(jù)權(quán)重要求和路徑長度限制,提出環(huán)路分割策略對初始化路徑進行分割,構(gòu)建相對應的環(huán)路以部署移動傳感器。實驗結(jié)果表明,相比CSweep、MinExpand和tcwtp算法,TLPS算法在增加少量移動傳感器數(shù)量的條件下平均掃描周期更短,目標覆蓋率與路徑有效率更高。下一步將針對三維空間中的覆蓋優(yōu)化問題進行研究。