一種基于概率感知的持續(xù)目標(biāo)覆蓋算法?

范興剛，廉曉聰，馬天樂，谷文婷，姜新陽(yáng)，劉賈賢

(浙江工業(yè)大學(xué)之江學(xué)院，浙江 杭州 310023)

為解決能量問題，采用移動(dòng)充電設(shè)備(Mobile Charger，MC)給網(wǎng)絡(luò)補(bǔ)充能量的策略越來(lái)越受到人們的關(guān)注[1－10]。MC 在傳感器網(wǎng)絡(luò)中周期性地移動(dòng)并給傳感器充電，使它們能夠執(zhí)行隨機(jī)事件捕捉任務(wù)。在此條件下，Dai 等[1]研究了目標(biāo)覆蓋下的最大QoM(Quality of Monitoring)充電調(diào)度問題，先選擇傳感器充電，并決定每個(gè)傳感器的充電時(shí)間；接著根據(jù)接收到的能量激活傳感器，最大化隨機(jī)事件捕獲的QoM。為了降低單個(gè)MC 的運(yùn)行成本，Zhou等[2]提出λ－GTSP 充電算法來(lái)確定傳感器的最佳充電數(shù)目，以保持目標(biāo)K 覆蓋率，并推導(dǎo)出MC 對(duì)其充電的最優(yōu)路徑。Dong 等[3]提出了一種能保證網(wǎng)絡(luò)長(zhǎng)時(shí)間運(yùn)行的時(shí)空聯(lián)合充電策略(Time and Space Combined Charging System，TSCCS)。Lyu 等[4]完善周期性充電規(guī)劃問題模型，設(shè)計(jì)相應(yīng)的充電規(guī)劃策略。Feng 等[5]提出一種基于混合模式的高效移動(dòng)能量補(bǔ)充方案，根據(jù)其充電等待時(shí)間動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的充電時(shí)間。為了使網(wǎng)絡(luò)效用最大化，Lan 等[6]結(jié)合數(shù)據(jù)和能量隊(duì)列約束，解決自適應(yīng)能量和數(shù)據(jù)的聯(lián)合傳輸問題。Yu 等[7]通過(guò)考慮傳感器節(jié)點(diǎn)的覆蓋貢獻(xiàn)構(gòu)建MC 充電路徑，以最大化網(wǎng)絡(luò)的監(jiān)控質(zhì)量。給大規(guī)模傳感器網(wǎng)絡(luò)充電需要使用多個(gè)MC。Ouyang 等[8]研究了多個(gè)MC 的協(xié)同充電調(diào)度問題。在移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)中，Du 等[9]研究了無(wú)人機(jī)支持的無(wú)線物聯(lián)網(wǎng)，提出一種工作流模型，優(yōu)化無(wú)人機(jī)的資源分配和服務(wù)順序，最大限度地提高無(wú)人機(jī)的資源利用率。

利用概率感知模型研究目標(biāo)覆蓋成為近年的研究熱點(diǎn)[11－17]。Zorbas 等[11]通過(guò)構(gòu)建網(wǎng)絡(luò)主連通集(CDS)，選擇目標(biāo)覆蓋集的方法實(shí)現(xiàn)目標(biāo)概率覆蓋。Shakhov 等[12]研究概率傳感模型參數(shù)估計(jì)。Debnath等[13]提出有效感知半徑(ESR)概念，研究網(wǎng)絡(luò)概率覆蓋率和入侵最早檢測(cè)時(shí)間等性能。Chen 等[14－15]提出MWBM 算法選擇節(jié)點(diǎn)構(gòu)建滿足下面兩個(gè)條件的柵欄:①構(gòu)建柵欄節(jié)點(diǎn)的權(quán)值之和最??；②這條柵欄對(duì)各種入侵者的感知概率都能達(dá)到感知閾值要求。Fan等[16]利用有向概率感知模型實(shí)現(xiàn)了有向節(jié)點(diǎn)的概率柵欄覆蓋。范興剛等[17]提出基于概率覆蓋圓的目標(biāo)覆蓋增強(qiáng)算法，構(gòu)造目標(biāo)概率覆蓋圓，選擇最優(yōu)節(jié)點(diǎn)調(diào)整感知方向，完成目標(biāo)概率覆蓋。但基于概率感知優(yōu)化充電部署還需進(jìn)一步研究。

因此，本文提出高效的持續(xù)目標(biāo)覆蓋算法(CtarP)，根據(jù)概率覆蓋創(chuàng)建單、雙目標(biāo)概率覆蓋圓，確定節(jié)點(diǎn)優(yōu)先級(jí)，設(shè)計(jì)目標(biāo)概率感知方案，優(yōu)化充電部署，用最少充電能耗實(shí)現(xiàn)高效率的持續(xù)目標(biāo)覆蓋。

本文章節(jié)安排如下:第1 節(jié)描述網(wǎng)絡(luò)模型。第2 節(jié)進(jìn)行持續(xù)目標(biāo)覆蓋算法設(shè)計(jì)。第3 節(jié)通過(guò)仿真實(shí)驗(yàn)對(duì)提出的算法進(jìn)行性能評(píng)估。第4 節(jié)總結(jié)全文并介紹下一步工作。

1 相關(guān)模型和定義

網(wǎng)絡(luò)中部署了N個(gè)節(jié)點(diǎn)對(duì)V個(gè)目標(biāo)進(jìn)行檢測(cè)，單個(gè)MC 從基站出發(fā)，可在M個(gè)充電位置給節(jié)點(diǎn)供電，使監(jiān)測(cè)目標(biāo)的節(jié)點(diǎn)獲得能量補(bǔ)充，實(shí)現(xiàn)持續(xù)目標(biāo)覆蓋。為了研究方便，假設(shè)如下:①網(wǎng)絡(luò)中存在一個(gè)移動(dòng)充電裝置MC，多個(gè)充電位置。②忽略MC 的移動(dòng)時(shí)間，且MC 的攜帶能量不受限制，充電功率保持不變。③通過(guò)節(jié)點(diǎn)輪換實(shí)現(xiàn)持續(xù)目標(biāo)覆蓋，且監(jiān)測(cè)過(guò)程中，節(jié)點(diǎn)具有相同的能耗。

概率覆蓋模型采用文獻(xiàn)[17]中定義1，其中有向感知調(diào)整為全向感知。

定義1概率覆蓋圓 在以節(jié)點(diǎn)位置為中心的圓內(nèi)，目標(biāo)感知概率大于等于概率感知閾值，這樣的圓為概率覆蓋圓。

概率感知閾值設(shè)為Prmin，得到概率半徑rmin如式(1):rs為距離閾值，k為感知強(qiáng)度衰減系數(shù)。

能量接收模型采用參考文獻(xiàn)[10]定義1，其中有向能量接收調(diào)整為全向能量接收。假設(shè)監(jiān)測(cè)目標(biāo)的節(jié)點(diǎn)單位能耗為e，充電功率Pf，得到充電半徑rp如式(2):

定義2充電圓 以MC 充電位置為圓心，rp為半徑的圓為充電圓。

充電圓內(nèi)節(jié)點(diǎn)單位時(shí)間內(nèi)可獲得≥e的能量。

定義3節(jié)點(diǎn)優(yōu)先級(jí) 根據(jù)目標(biāo)覆蓋情況設(shè)定節(jié)點(diǎn)的優(yōu)先級(jí)，覆蓋目標(biāo)數(shù)最多的節(jié)點(diǎn)優(yōu)先級(jí)最高，實(shí)現(xiàn)單覆蓋的節(jié)點(diǎn)比實(shí)現(xiàn)雙覆蓋的節(jié)點(diǎn)優(yōu)先級(jí)高，以此類推，確定節(jié)點(diǎn)優(yōu)先級(jí)。

定義4充電部署 從M個(gè)充電位置中選擇的實(shí)際充電位置集合S稱為充電部署。

定義5充電能耗貢獻(xiàn)值 充電功率對(duì)目標(biāo)覆蓋的貢獻(xiàn)值＝目標(biāo)數(shù)×生命期/(實(shí)際充電位置數(shù)?每個(gè)充電位置處消耗的能量)。

這個(gè)指標(biāo)越高，充電效能越好。

定義6持續(xù)目標(biāo)覆蓋 在規(guī)定時(shí)間內(nèi)，監(jiān)測(cè)目標(biāo)的節(jié)點(diǎn)獲取的能量大于等于消耗的能量，這個(gè)目標(biāo)就實(shí)現(xiàn)持續(xù)覆蓋。

定義7充電周期 從MC 攜帶能量離開基站，到回到基站充滿能量這段時(shí)間稱為充電周期。以一個(gè)覆蓋方案的覆蓋時(shí)間為單位，整個(gè)充電周期T分為k個(gè)時(shí)間段{t1，t2，…，tk}。

在一個(gè)網(wǎng)絡(luò)中，部署了N個(gè)節(jié)點(diǎn)對(duì)V個(gè)目標(biāo)進(jìn)行監(jiān)測(cè)，一個(gè)MC 在M個(gè)位置中移動(dòng)，給節(jié)點(diǎn)充電。如何根據(jù)聯(lián)合概率感知優(yōu)化充電部署，高效實(shí)現(xiàn)目標(biāo)持續(xù)覆蓋，是本文主要研究的問題。

2 持續(xù)目標(biāo)覆蓋算法設(shè)計(jì)

為了描述方便，相關(guān)參數(shù)定義見表1。

表1 相關(guān)參數(shù)

2.1 確定目標(biāo)概率覆蓋集

概率感知下，目標(biāo)的覆蓋率是多個(gè)節(jié)點(diǎn)聯(lián)合感知的結(jié)果。目標(biāo)聯(lián)合感知概率采用參考文獻(xiàn)[17]中定義2 的目標(biāo)聯(lián)合感知概率。當(dāng)目標(biāo)聯(lián)合感知概率≥Prmin，就稱這個(gè)目標(biāo)實(shí)現(xiàn)了概率覆蓋。本文考慮兩個(gè)節(jié)點(diǎn)的聯(lián)合概率感知，如圖1 所示，距離節(jié)點(diǎn)rmin的目標(biāo)得到探測(cè)概率Prmin＝0.9。其中，實(shí)線圓的半徑為rmin，稱為單概率覆蓋圓。虛線圓為事件檢測(cè)率大于0.7 的區(qū)域，稱為雙概率覆蓋圓。目標(biāo)V1與節(jié)點(diǎn)A的距離小于rmin，則根據(jù)概率覆蓋模型，節(jié)點(diǎn)A實(shí)現(xiàn)目標(biāo)V1的概率監(jiān)測(cè)。目標(biāo)V2距離節(jié)點(diǎn)A，B的距離都>rmin，單獨(dú)的節(jié)點(diǎn)無(wú)法實(shí)現(xiàn)目標(biāo)V2的概率覆蓋。節(jié)點(diǎn)A和B對(duì)目標(biāo)V2的聯(lián)合感知概率>0.91>0.9，滿足監(jiān)測(cè)要求。即目標(biāo)V2在節(jié)點(diǎn)A和B的聯(lián)合概率感知下滿足覆蓋要求。最終，得到目標(biāo)概率覆蓋集如表2 所示，其中，“單覆蓋”是指單個(gè)節(jié)點(diǎn)就可以滿足目標(biāo)的覆蓋，“雙覆蓋”是指兩個(gè)節(jié)點(diǎn)聯(lián)合概率感知滿足覆蓋要求。目標(biāo)Vj的單覆蓋節(jié)點(diǎn)集合為Pj，雙覆蓋集合為Qj。

圖1 概率感知模型與概率目標(biāo)覆蓋

表2 目標(biāo)概率覆蓋集

2.2 構(gòu)建充電半徑，確定充電節(jié)點(diǎn)

在一個(gè)充電周期內(nèi)，MC 依次移動(dòng)到充電位置給節(jié)點(diǎn)充電，完成所有充電任務(wù)后，回到基站補(bǔ)充能量。如圖2 所示，在S1，對(duì)節(jié)點(diǎn)A，D，G，E充電，這些節(jié)點(diǎn)單位時(shí)間內(nèi)都可獲得大于e的能量，可以執(zhí)行一個(gè)單位時(shí)間的目標(biāo)監(jiān)測(cè)。同理在S2對(duì)節(jié)點(diǎn)B，C，J充電，在S3對(duì)節(jié)點(diǎn)H，I充電。節(jié)點(diǎn)F在S1，S2，S3的充電圓之外，得不到能量補(bǔ)充，無(wú)法進(jìn)行目標(biāo)監(jiān)測(cè)。

圖2 基于聯(lián)合概率感知的充電部署

2.3 確定目標(biāo)的覆蓋方案，優(yōu)化充電部署

2.3.1 基于單覆蓋的充電部署

根據(jù)單覆蓋集合和充電圓，設(shè)計(jì)目標(biāo)的單覆蓋方案，如表3 所示。

表3 目標(biāo)的單覆蓋方案

如圖2 所示，為給監(jiān)控目標(biāo)的節(jié)點(diǎn)充電，MC 需要在3 個(gè)位置停留。

根據(jù)表3，目標(biāo)V1和V3都有兩種覆蓋策略，V2只有一種覆蓋策略。MC 在S1時(shí)，監(jiān)測(cè)目標(biāo)V1的節(jié)點(diǎn)A，E獲得能量補(bǔ)充，實(shí)現(xiàn)覆蓋策略1，4。監(jiān)測(cè)目標(biāo)V2的節(jié)點(diǎn)G也得到能量補(bǔ)充，實(shí)現(xiàn)覆蓋策略2。MC 在S2時(shí)，監(jiān)測(cè)目標(biāo)V3的節(jié)點(diǎn)B，J得到能量補(bǔ)充，實(shí)現(xiàn)覆蓋策略3，6。MC 在S3時(shí)，節(jié)點(diǎn)H，I得到能量補(bǔ)充。整個(gè)充電過(guò)程中，目標(biāo)V2只能采用節(jié)點(diǎn)G進(jìn)行監(jiān)測(cè)，無(wú)法替換，很難實(shí)現(xiàn)持續(xù)目標(biāo)覆蓋。

總之，最初充電部署S＝{S1，S2，S3}，3Pf的充電能耗，只有2 個(gè)目標(biāo)實(shí)現(xiàn)了2 個(gè)單位的持續(xù)監(jiān)測(cè)。由于MC 在S3時(shí)的充電能耗對(duì)目標(biāo)覆蓋無(wú)貢獻(xiàn)，MC 可以不在S3停留，優(yōu)化后的充電部署為S＝{S1，S2}，2Pf的充電能耗，只有2 個(gè)目標(biāo)實(shí)現(xiàn)2 個(gè)單位時(shí)間的持續(xù)監(jiān)測(cè)。

2.3.2 基于聯(lián)合概率感知的充電部署

根據(jù)單覆蓋集合和雙覆蓋集合確定節(jié)點(diǎn)優(yōu)先級(jí)，依次確定整個(gè)充電周期內(nèi)各單位時(shí)間的目標(biāo)聯(lián)合概率感知覆蓋方案，該過(guò)程的完整流程如圖3。

圖3 確定充電周期內(nèi)目標(biāo)覆蓋方案流程圖

設(shè)集合Z為以優(yōu)先級(jí)排序的候選節(jié)點(diǎn)集，Vk＝{Vk，1，…，Vk，j，…，Vk，V}為tk內(nèi)的目標(biāo)方案確定序列，單位時(shí)間tk內(nèi)目標(biāo)Vk，j的覆蓋方案為Wk，j，已選擇的節(jié)點(diǎn)集為Rk。

確定目標(biāo)序列Vk時(shí)，優(yōu)先考慮Rk可覆蓋的目標(biāo)，每確定好一個(gè)目標(biāo)覆蓋方案后，對(duì)Rk和Vk進(jìn)行更新。首先選擇Z中優(yōu)先級(jí)最高的起始節(jié)點(diǎn)nk，1，在Rk可覆蓋的目標(biāo)中確定起始目標(biāo)Vk，1。

再確定Vk，1的覆蓋方案，若節(jié)點(diǎn)nk，1可實(shí)現(xiàn)對(duì)Vk，1的單覆蓋，則確定其為Vk，1的覆蓋方案；若節(jié)點(diǎn)nk，1不能實(shí)現(xiàn)對(duì)Vk，1的單覆蓋，則需要在該目標(biāo)雙覆蓋集合Qk，1中選擇優(yōu)先級(jí)次高的節(jié)點(diǎn)nk，2與nk，1聯(lián)合實(shí)現(xiàn)覆蓋要求，即起始目標(biāo)Vk，1的覆蓋方案為:

接著再按照Vk依次確定剩余目標(biāo)覆蓋方案，且優(yōu)先考慮優(yōu)先級(jí)高的節(jié)點(diǎn)用于確定覆蓋方案。設(shè)目標(biāo)Vk，j可選擇聯(lián)合節(jié)點(diǎn)集為Xk，j，可選擇非聯(lián)合節(jié)點(diǎn)集為Yk，j，Xk，j中的節(jié)點(diǎn)可覆蓋多個(gè)目標(biāo)，Yk，j中的節(jié)點(diǎn)只覆蓋單個(gè)目標(biāo)。

覆蓋方案Wk，j(j＝2，…，V)通過(guò)式(5)、式(6)、式(7)確定，即分為以下6 種情況:

Case 1:若Xk，j中存在單覆蓋節(jié)點(diǎn)，則可在其中確定Wk，j，否則轉(zhuǎn)到Case 2；

Case 2:若Xk，j中存在兩個(gè)以上雙覆蓋節(jié)點(diǎn)則可在Xk，j中確定Wk，j，只存在一個(gè)雙覆蓋節(jié)點(diǎn)則轉(zhuǎn)到Case 3，不存在雙覆蓋節(jié)點(diǎn)轉(zhuǎn)到Case 4；

Case 3:若Xk，j中存在一個(gè)雙覆蓋節(jié)點(diǎn)且Yk，j中存在雙覆蓋節(jié)點(diǎn)，則選擇Xk，j與Yk，j中優(yōu)先級(jí)較高的雙覆蓋節(jié)點(diǎn)確定為Wk，j；

Case 4:若Yk，j中存在單覆蓋節(jié)點(diǎn)，則在其中確定Wk，j，否則轉(zhuǎn)到Case 5；

Case 5:若Yk，j中存在兩個(gè)以上的雙覆蓋節(jié)點(diǎn)，則可在Yk，j中確定Wk，j，否則轉(zhuǎn)到Case 6；

Case 6:Wk，j＝?，無(wú)法完成覆蓋要求。

根據(jù)表4 的目標(biāo)概率覆蓋調(diào)度方案得到節(jié)點(diǎn)的優(yōu)先級(jí)，確定充電序列為{A，B，C，G，D，E，J，H，I}。節(jié)點(diǎn)A優(yōu)先級(jí)最高，MC 需先到達(dá)S1進(jìn)行充電，節(jié)點(diǎn)A，D，E，G獲得能量補(bǔ)充，可以實(shí)現(xiàn)監(jiān)測(cè)策略1，7，8。再對(duì)節(jié)點(diǎn)B進(jìn)行充電，MC 達(dá)到S2，節(jié)點(diǎn)B，C，J獲得能量補(bǔ)充，可以實(shí)現(xiàn)監(jiān)測(cè)策略2，3，4，5，6，9，從而可以實(shí)現(xiàn)目標(biāo)V1，V2，V3的三種監(jiān)測(cè)策略。MC 只需要在S1，S2停留，無(wú)需在S3停留，就可以實(shí)現(xiàn)持續(xù)目標(biāo)覆蓋。

表4 整個(gè)充電周期的目標(biāo)覆蓋方案

換句話說(shuō)，在采用聯(lián)合概率感知時(shí)，2Pf的充電能耗下，3 個(gè)目標(biāo)全部實(shí)現(xiàn)3 個(gè)單位時(shí)間的持續(xù)監(jiān)測(cè)。

2.4 基于概率感知的持續(xù)目標(biāo)覆蓋算法

由以上分析可知，根據(jù)目標(biāo)聯(lián)合概率感知確定目標(biāo)的覆蓋方案，優(yōu)化充電部署，選擇節(jié)點(diǎn)充電，可實(shí)現(xiàn)高效的持續(xù)目標(biāo)覆蓋。據(jù)此，我們提出一種基于概率感知的持續(xù)目標(biāo)覆蓋算法(Continuous target coverage scheme based on probabilistic sensing model，CtarP)。其基本思想如下:根據(jù)目標(biāo)概率覆蓋集，確定節(jié)點(diǎn)優(yōu)先級(jí)，優(yōu)化覆蓋方案，找到最優(yōu)充電部署，用最少的充電能耗，實(shí)現(xiàn)高效持續(xù)目標(biāo)覆蓋。

2.4.1 算法具體過(guò)程

CtarP 算法偽代碼如圖4 所示，參數(shù)的定義如表1 所示。CtarP 算法具體步驟如下:

圖4 CtarP 算法偽代碼

Step 1:構(gòu)建目標(biāo)概率覆蓋圓

如圖1 所示，構(gòu)建每個(gè)目標(biāo)的單、雙概率覆蓋圓，確定相鄰目標(biāo)雙概率覆蓋圓的公共區(qū)域，找出覆蓋目標(biāo)的單、雙覆蓋集合。

Step 2:對(duì)節(jié)點(diǎn)排序

設(shè)定節(jié)點(diǎn)優(yōu)先級(jí)，根據(jù)表2 中節(jié)點(diǎn)覆蓋目標(biāo)的個(gè)數(shù)確定節(jié)點(diǎn)優(yōu)先級(jí)。

Step 3:確定充電節(jié)點(diǎn)

在每個(gè)充電位置構(gòu)建充電圓，確定充電節(jié)點(diǎn)，確定覆蓋方案時(shí)不考慮充電圓外的節(jié)點(diǎn)，如節(jié)點(diǎn)F不能作為覆蓋方案選擇節(jié)點(diǎn)。

Step 4:調(diào)度節(jié)點(diǎn)，實(shí)施目標(biāo)概率覆蓋方案

根據(jù)2.3.2 確定充電周期中各單位時(shí)間內(nèi)目標(biāo)基于聯(lián)合概率感知的覆蓋方案，先確定各單位時(shí)間內(nèi)的起始節(jié)點(diǎn)用于初始化Rk，根據(jù)Rk選擇起始目標(biāo)并確定其覆蓋方案，再根據(jù)Vk依次確定剩余目標(biāo)的覆蓋方案。

如圖1，集合Z初始值為{A，B，C，G，D，E，J，H，I}，在t1內(nèi)首先選擇優(yōu)先級(jí)最高的節(jié)點(diǎn)A作為起始節(jié)點(diǎn)n1，1，將該節(jié)點(diǎn)可覆蓋的目標(biāo)V1作為起始目標(biāo)V1，1，節(jié)點(diǎn)A可對(duì)V1，1實(shí)現(xiàn)單覆蓋，即W1，1＝{A}，Rk＝{A}，Vk＝{V1，V2，V3}；對(duì)于目標(biāo)V2來(lái)說(shuō)，在集合Xk，2＝{A，C}中選擇節(jié)點(diǎn)A，C對(duì)目標(biāo)V2進(jìn)行聯(lián)合概率覆蓋，即W1，2＝{A，C}，Rk＝{A，C}，Vk＝{V1，V2，V3}；對(duì)于目標(biāo)V3，在可選擇聯(lián)合節(jié)點(diǎn)集X1，3＝{A，C}中選擇節(jié)點(diǎn)A，C對(duì)目標(biāo)V3進(jìn)行聯(lián)合概率覆蓋，即W1，3＝{A，C}，Rk＝{A，C}，Vk＝{V1，V2，V3}，t1內(nèi)的覆蓋方案確定完成，此時(shí)集合Z＝{B，G，D，E，J，H，I}。類似的，依次確定t2內(nèi)目標(biāo)的覆蓋方案，更新Z＝{G，E，J，H，I}。在t3內(nèi)，先確定節(jié)點(diǎn)G為起始節(jié)點(diǎn)n3，1，目標(biāo)V2為起始目標(biāo)V3，1，得到W3，1＝{G}，Rk＝{G}，Vk＝{V2，V1}；對(duì)于目標(biāo)V1，集合X3，2＝{G}，集合Y3，2＝{G，E}，只能在集合Y3，2中選擇節(jié)點(diǎn)E滿足覆蓋要求，即W3，2＝{E}，Rk＝{G，E}，Vk＝{V2，V1，V3}；同樣對(duì)于目標(biāo)V3，在集合Y3，3＝{J}中選擇節(jié)點(diǎn)J滿足覆蓋要求，即W3，3＝{J}，Rk＝{G，E，J}，Vk＝{V2，V1，V3}，更新集合Z＝{H，I}，此時(shí)Z中的節(jié)點(diǎn)已無(wú)法滿足下個(gè)單位時(shí)間內(nèi)目標(biāo)的覆蓋要求，整個(gè)充電周期結(jié)束。在上述步驟中，確定好一個(gè)單位時(shí)間的覆蓋方案后，都需對(duì)集合Z進(jìn)行更新。

Step 5:優(yōu)化充電部署，選定充電位置

以滿足目標(biāo)持續(xù)覆蓋的能量需求為目標(biāo)，選擇充電位置。

按照節(jié)點(diǎn)優(yōu)先級(jí)從高到低的順序滿足節(jié)點(diǎn)充電需求，依次選擇MC 的充電位置，直到所有目標(biāo)都實(shí)現(xiàn)了持續(xù)覆蓋。如圖2 所示，節(jié)點(diǎn)A優(yōu)先級(jí)最高，MC 需先到達(dá)S1進(jìn)行充電，再對(duì)節(jié)點(diǎn)B充電，MC 達(dá)到S2，此時(shí)可以實(shí)現(xiàn)目標(biāo)V1，V2，V3的三種監(jiān)測(cè)策略。MC 只需要在S1，S2停留，無(wú)需在S3停留，就可以實(shí)現(xiàn)持續(xù)目標(biāo)覆蓋。

Step 6:移動(dòng)周期充電

MC 根據(jù)確定的充電位置移動(dòng)周期充電。

2.4.2 理論分析

假設(shè)節(jié)點(diǎn)數(shù)是N，充電位置數(shù)是M，目標(biāo)數(shù)是V?M，由于每個(gè)節(jié)點(diǎn)需要對(duì)每個(gè)目標(biāo)考核概率覆蓋，復(fù)雜度為O(NV)。針對(duì)每個(gè)充電位置，要考慮每個(gè)節(jié)點(diǎn)的充電情況，這一步的復(fù)雜度為O(NM)。因此，算法總復(fù)雜度為O(NV)。

3 仿真結(jié)果

本文運(yùn)用MATLAB7.0 對(duì)此算法進(jìn)行仿真，每組實(shí)驗(yàn)數(shù)據(jù)采用重復(fù)50 次獨(dú)立實(shí)驗(yàn)取平均值的方式獲得，默認(rèn)參數(shù)如表5 所示。采用目標(biāo)覆蓋率(coverage ratio，Cr)和充電能耗貢獻(xiàn)值(contribution)兩個(gè)指標(biāo)。目標(biāo)覆蓋率為能實(shí)現(xiàn)持續(xù)覆蓋的目標(biāo)數(shù)/網(wǎng)絡(luò)中的總目標(biāo)數(shù)。例如，在2.3 小節(jié)，在不采用聯(lián)合概率感知時(shí)，2Pf的充電能耗下，只有2 個(gè)目標(biāo)實(shí)現(xiàn)了2 個(gè)單位的持續(xù)監(jiān)測(cè)，這個(gè)時(shí)候的貢獻(xiàn)值為2×2/2 ＝2。而在2.4 小節(jié)，在采用聯(lián)合概率感知時(shí)，2Pf的充電能耗下，3 個(gè)目標(biāo)全部實(shí)現(xiàn)3 個(gè)時(shí)間單位的持續(xù)監(jiān)測(cè)，這個(gè)時(shí)候的貢獻(xiàn)值為3×3/2＝4.5。

表5 實(shí)驗(yàn)參數(shù)

為了說(shuō)明算法的性能，我們先采用文獻(xiàn)[2]方法，稱為感知算法(the continous target coverage scheme based on 0－1 sensing model，CtaR)，既不采用聯(lián)合感知，也不對(duì)目標(biāo)點(diǎn)覆蓋進(jìn)行優(yōu)化篩選(即節(jié)點(diǎn)不根據(jù)目標(biāo)覆蓋情況進(jìn)行優(yōu)先級(jí)排序)。接著采用聯(lián)合概率感知，但仍然不對(duì)目標(biāo)點(diǎn)覆蓋進(jìn)行優(yōu)化篩選算法(the continous target coverage scheme based on joint probabilistic detection，CtarN)。

3.1 節(jié)點(diǎn)數(shù)量的影響

節(jié)點(diǎn)數(shù)量的影響如圖5 所示。節(jié)點(diǎn)數(shù)量越多，充電圓內(nèi)節(jié)點(diǎn)越多，獲得能量的節(jié)點(diǎn)越多，網(wǎng)絡(luò)中持續(xù)覆蓋的目標(biāo)越多，目標(biāo)的覆蓋率越大。因此CtarN算法和CtaR 算法的目標(biāo)覆蓋率隨節(jié)點(diǎn)數(shù)量的增加而增大。而CtarP 算法利用概率感知確定目標(biāo)覆蓋方案，對(duì)每個(gè)目標(biāo)點(diǎn)優(yōu)先選取獲得覆蓋目標(biāo)數(shù)最多的節(jié)點(diǎn)，充分利用節(jié)點(diǎn)的能量，目標(biāo)覆蓋率較CtarN算法和CtaR 算法要大，如圖5(a)所示。

圖5 節(jié)點(diǎn)數(shù)量的影響

節(jié)點(diǎn)數(shù)量越多，每個(gè)充電位置處，可充電的節(jié)點(diǎn)數(shù)越多，網(wǎng)絡(luò)持續(xù)時(shí)間越長(zhǎng)，充電位置選取越少，單位充電能耗對(duì)目標(biāo)覆蓋的貢獻(xiàn)值越大。因此CtarN 算法和CtaR 算法的貢獻(xiàn)值隨節(jié)點(diǎn)數(shù)量的增加而增大，而CtarP 算法保證較高的目標(biāo)覆蓋率的同時(shí)，尋找最優(yōu)充電位置，用最少的充電能耗，高效實(shí)現(xiàn)持續(xù)目標(biāo)覆蓋。因此算法CtarP 性能最優(yōu)，如圖5(b)所示。

3.2 目標(biāo)點(diǎn)數(shù)的影響

目標(biāo)點(diǎn)數(shù)量的影響如圖6 所示。目標(biāo)點(diǎn)數(shù)量越多，節(jié)點(diǎn)在概率感知范圍內(nèi)的目標(biāo)點(diǎn)數(shù)量越多，有更多的目標(biāo)點(diǎn)可以被節(jié)點(diǎn)感知，獲得能量的節(jié)點(diǎn)在網(wǎng)絡(luò)中持續(xù)覆蓋目標(biāo)點(diǎn)數(shù)量越多，目標(biāo)的覆蓋率越大。三種算法的目標(biāo)覆蓋率都隨目標(biāo)點(diǎn)的增加而增大。CtarP 算法選取最優(yōu)的節(jié)點(diǎn)對(duì)目標(biāo)點(diǎn)進(jìn)行覆蓋，使節(jié)點(diǎn)能夠同時(shí)完成更多目標(biāo)的監(jiān)測(cè)任務(wù)，能夠充分利用節(jié)點(diǎn)所捕獲的能量，因此CtarP 算法最優(yōu)，如圖6(a)所示。

CtarP 算法在保證目標(biāo)覆蓋數(shù)量最多的同時(shí)，優(yōu)先選擇目標(biāo)覆蓋數(shù)較多的節(jié)點(diǎn)確定目標(biāo)覆蓋方案，相對(duì)于其他算法能充分利用節(jié)點(diǎn)能量，延長(zhǎng)了網(wǎng)絡(luò)持續(xù)覆蓋時(shí)間，減少M(fèi)C 充電位置，降低充電能耗。因此CtarP 算法在目標(biāo)點(diǎn)數(shù)量增加時(shí)，增大單位能耗對(duì)目標(biāo)覆蓋的貢獻(xiàn)值。CtarP 算法性能最優(yōu)，如圖6(b)所示。

圖6 目標(biāo)數(shù)的影響

3.3 概率閾值的影響

概率閾值的影響如圖7 所示。概率閾值越大，目標(biāo)的雙概率圓的半徑越小，目標(biāo)概率檢測(cè)方案越少，節(jié)點(diǎn)覆蓋目標(biāo)點(diǎn)數(shù)量越少，目標(biāo)覆蓋率越小。因此三個(gè)算法的目標(biāo)覆蓋率隨概率閾值的增大而減小。CtarP 算法中，優(yōu)先選擇覆蓋目標(biāo)數(shù)多的節(jié)點(diǎn)，因此CtarP 算法的目標(biāo)覆蓋率效果最好，如圖7(a)所示。

概率閾值越大，覆蓋的目標(biāo)點(diǎn)數(shù)量越少，網(wǎng)絡(luò)持續(xù)時(shí)間越短，MC 充電位置選取越多，網(wǎng)絡(luò)充電能耗越大，單位能耗對(duì)目標(biāo)覆蓋的貢獻(xiàn)值越小。CtarN算法和CtaR 算法的貢獻(xiàn)值隨概率閾值的增大而減少。在CtarP 算法中，概率閾值越大，增加了MC 充電停留位置，減少單位能耗對(duì)目標(biāo)覆蓋的貢獻(xiàn)值，因此CtarP 算法的貢獻(xiàn)值隨概率閾值的增加而下降，如圖7(b)所示。

圖7 概率閾值的影響

3.4 充電位置數(shù)的影響

充電位置數(shù)量的影響如圖8 所示。充電位置數(shù)越多，可以得到充電的節(jié)點(diǎn)數(shù)量越多，可以監(jiān)測(cè)目標(biāo)的節(jié)點(diǎn)數(shù)量越多，目標(biāo)的覆蓋率越大。三種算法的目標(biāo)覆蓋率都隨充電位置數(shù)量的增加而提高。CtarP 算法通過(guò)節(jié)點(diǎn)的優(yōu)先級(jí)確定目標(biāo)的聯(lián)合概率感知的充電部署，選擇最優(yōu)的充電位置對(duì)節(jié)點(diǎn)進(jìn)行能量補(bǔ)充。因此CtarP 算法最優(yōu)，如圖8(a)所示。

圖8 充電位置數(shù)的影響

CtarP 算法在保證目標(biāo)覆蓋率的基礎(chǔ)上，選擇最優(yōu)的充電位置對(duì)節(jié)點(diǎn)進(jìn)行能量補(bǔ)充，延長(zhǎng)網(wǎng)絡(luò)持續(xù)覆蓋時(shí)間，降低網(wǎng)絡(luò)充電能耗。因此CtarP 算法在充電位置數(shù)增加的同時(shí)，增大了單位能耗對(duì)目標(biāo)覆蓋的貢獻(xiàn)值。CtarP 算法性能最優(yōu)，如圖8(b)所示。

4 結(jié)束語(yǔ)

本文提出一種基于概率感知的持續(xù)目標(biāo)覆蓋算法，首先根據(jù)聯(lián)合概率感知確定目標(biāo)概率覆蓋集，接著對(duì)節(jié)點(diǎn)進(jìn)行優(yōu)先級(jí)排序，根據(jù)節(jié)點(diǎn)優(yōu)先級(jí)確定整個(gè)充電周期內(nèi)目標(biāo)的覆蓋方案，最終優(yōu)化單MC 充電部署，選擇高效率的充電位置滿足節(jié)點(diǎn)的充電需求。仿真結(jié)果表明CtarP 算法取得的目標(biāo)覆蓋率優(yōu)于同等條件下的其他算法，并在保證較高覆蓋率的同時(shí)，最大化充電能耗貢獻(xiàn)值，用最少的充電能耗實(shí)現(xiàn)了高效率的持續(xù)目標(biāo)覆蓋。

如何在MC 攜帶能量有限的情況下，節(jié)能高效地實(shí)現(xiàn)持續(xù)目標(biāo)覆蓋是下一步要研究的內(nèi)容。