一種基于概率感知的持續目標覆蓋算法?

范興剛，廉曉聰，馬天樂，谷文婷，姜新陽，劉賈賢

(浙江工業大學之江學院，浙江 杭州 310023)

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

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

因此，本文提出高效的持續目標覆蓋算法(CtarP)，根據概率覆蓋創建單、雙目標概率覆蓋圓，確定節點優先級，設計目標概率感知方案，優化充電部署，用最少充電能耗實現高效率的持續目標覆蓋。

本文章節安排如下:第1 節描述網絡模型。第2 節進行持續目標覆蓋算法設計。第3 節通過仿真實驗對提出的算法進行性能評估。第4 節總結全文并介紹下一步工作。

1 相關模型和定義

網絡中部署了N個節點對V個目標進行檢測，單個MC 從基站出發，可在M個充電位置給節點供電，使監測目標的節點獲得能量補充，實現持續目標覆蓋。為了研究方便，假設如下:①網絡中存在一個移動充電裝置MC，多個充電位置。②忽略MC 的移動時間，且MC 的攜帶能量不受限制，充電功率保持不變。③通過節點輪換實現持續目標覆蓋，且監測過程中，節點具有相同的能耗。

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

定義1概率覆蓋圓 在以節點位置為中心的圓內，目標感知概率大于等于概率感知閾值，這樣的圓為概率覆蓋圓。

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

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

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

充電圓內節點單位時間內可獲得≥e的能量。

定義3節點優先級 根據目標覆蓋情況設定節點的優先級，覆蓋目標數最多的節點優先級最高，實現單覆蓋的節點比實現雙覆蓋的節點優先級高，以此類推，確定節點優先級。

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

定義5充電能耗貢獻值 充電功率對目標覆蓋的貢獻值＝目標數×生命期/(實際充電位置數?每個充電位置處消耗的能量)。

這個指標越高，充電效能越好。

定義6持續目標覆蓋 在規定時間內，監測目標的節點獲取的能量大于等于消耗的能量，這個目標就實現持續覆蓋。

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

在一個網絡中，部署了N個節點對V個目標進行監測，一個MC 在M個位置中移動，給節點充電。如何根據聯合概率感知優化充電部署，高效實現目標持續覆蓋，是本文主要研究的問題。

2 持續目標覆蓋算法設計

為了描述方便，相關參數定義見表1。

表1 相關參數

2.1 確定目標概率覆蓋集

概率感知下，目標的覆蓋率是多個節點聯合感知的結果。目標聯合感知概率采用參考文獻[17]中定義2 的目標聯合感知概率。當目標聯合感知概率≥Prmin，就稱這個目標實現了概率覆蓋。本文考慮兩個節點的聯合概率感知，如圖1 所示，距離節點rmin的目標得到探測概率Prmin＝0.9。其中，實線圓的半徑為rmin，稱為單概率覆蓋圓。虛線圓為事件檢測率大于0.7 的區域，稱為雙概率覆蓋圓。目標V1與節點A的距離小于rmin，則根據概率覆蓋模型，節點A實現目標V1的概率監測。目標V2距離節點A，B的距離都>rmin，單獨的節點無法實現目標V2的概率覆蓋。節點A和B對目標V2的聯合感知概率>0.91>0.9，滿足監測要求。即目標V2在節點A和B的聯合概率感知下滿足覆蓋要求。最終，得到目標概率覆蓋集如表2 所示，其中，“單覆蓋”是指單個節點就可以滿足目標的覆蓋，“雙覆蓋”是指兩個節點聯合概率感知滿足覆蓋要求。目標Vj的單覆蓋節點集合為Pj，雙覆蓋集合為Qj。

圖1 概率感知模型與概率目標覆蓋

表2 目標概率覆蓋集

2.2 構建充電半徑，確定充電節點

在一個充電周期內，MC 依次移動到充電位置給節點充電，完成所有充電任務后，回到基站補充能量。如圖2 所示，在S1，對節點A，D，G，E充電，這些節點單位時間內都可獲得大于e的能量，可以執行一個單位時間的目標監測。同理在S2對節點B，C，J充電，在S3對節點H，I充電。節點F在S1，S2，S3的充電圓之外，得不到能量補充，無法進行目標監測。

圖2 基于聯合概率感知的充電部署

2.3 確定目標的覆蓋方案，優化充電部署

2.3.1 基于單覆蓋的充電部署

根據單覆蓋集合和充電圓，設計目標的單覆蓋方案，如表3 所示。

表3 目標的單覆蓋方案

如圖2 所示，為給監控目標的節點充電，MC 需要在3 個位置停留。

根據表3，目標V1和V3都有兩種覆蓋策略，V2只有一種覆蓋策略。MC 在S1時，監測目標V1的節點A，E獲得能量補充，實現覆蓋策略1，4。監測目標V2的節點G也得到能量補充，實現覆蓋策略2。MC 在S2時，監測目標V3的節點B，J得到能量補充，實現覆蓋策略3，6。MC 在S3時，節點H，I得到能量補充。整個充電過程中，目標V2只能采用節點G進行監測，無法替換，很難實現持續目標覆蓋。

總之，最初充電部署S＝{S1，S2，S3}，3Pf的充電能耗，只有2 個目標實現了2 個單位的持續監測。由于MC 在S3時的充電能耗對目標覆蓋無貢獻，MC 可以不在S3停留，優化后的充電部署為S＝{S1，S2}，2Pf的充電能耗，只有2 個目標實現2 個單位時間的持續監測。

2.3.2 基于聯合概率感知的充電部署

根據單覆蓋集合和雙覆蓋集合確定節點優先級，依次確定整個充電周期內各單位時間的目標聯合概率感知覆蓋方案，該過程的完整流程如圖3。

圖3 確定充電周期內目標覆蓋方案流程圖

設集合Z為以優先級排序的候選節點集，Vk＝{Vk，1，…，Vk，j，…，Vk，V}為tk內的目標方案確定序列，單位時間tk內目標Vk，j的覆蓋方案為Wk，j，已選擇的節點集為Rk。

確定目標序列Vk時，優先考慮Rk可覆蓋的目標，每確定好一個目標覆蓋方案后，對Rk和Vk進行更新。首先選擇Z中優先級最高的起始節點nk，1，在Rk可覆蓋的目標中確定起始目標Vk，1。

再確定Vk，1的覆蓋方案，若節點nk，1可實現對Vk，1的單覆蓋，則確定其為Vk，1的覆蓋方案；若節點nk，1不能實現對Vk，1的單覆蓋，則需要在該目標雙覆蓋集合Qk，1中選擇優先級次高的節點nk，2與nk，1聯合實現覆蓋要求，即起始目標Vk，1的覆蓋方案為:

接著再按照Vk依次確定剩余目標覆蓋方案，且優先考慮優先級高的節點用于確定覆蓋方案。設目標Vk，j可選擇聯合節點集為Xk，j，可選擇非聯合節點集為Yk，j，Xk，j中的節點可覆蓋多個目標，Yk，j中的節點只覆蓋單個目標。

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

Case 1:若Xk，j中存在單覆蓋節點，則可在其中確定Wk，j，否則轉到Case 2；

Case 2:若Xk，j中存在兩個以上雙覆蓋節點則可在Xk，j中確定Wk，j，只存在一個雙覆蓋節點則轉到Case 3，不存在雙覆蓋節點轉到Case 4；

Case 3:若Xk，j中存在一個雙覆蓋節點且Yk，j中存在雙覆蓋節點，則選擇Xk，j與Yk，j中優先級較高的雙覆蓋節點確定為Wk，j；

Case 4:若Yk，j中存在單覆蓋節點，則在其中確定Wk，j，否則轉到Case 5；

Case 5:若Yk，j中存在兩個以上的雙覆蓋節點，則可在Yk，j中確定Wk，j，否則轉到Case 6；

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

根據表4 的目標概率覆蓋調度方案得到節點的優先級，確定充電序列為{A，B，C，G，D，E，J，H，I}。節點A優先級最高，MC 需先到達S1進行充電，節點A，D，E，G獲得能量補充，可以實現監測策略1，7，8。再對節點B進行充電，MC 達到S2，節點B，C，J獲得能量補充，可以實現監測策略2，3，4，5，6，9，從而可以實現目標V1，V2，V3的三種監測策略。MC 只需要在S1，S2停留，無需在S3停留，就可以實現持續目標覆蓋。

表4 整個充電周期的目標覆蓋方案

換句話說，在采用聯合概率感知時，2Pf的充電能耗下，3 個目標全部實現3 個單位時間的持續監測。

2.4 基于概率感知的持續目標覆蓋算法

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

2.4.1 算法具體過程

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

圖4 CtarP 算法偽代碼

Step 1:構建目標概率覆蓋圓

如圖1 所示，構建每個目標的單、雙概率覆蓋圓，確定相鄰目標雙概率覆蓋圓的公共區域，找出覆蓋目標的單、雙覆蓋集合。

Step 2:對節點排序

設定節點優先級，根據表2 中節點覆蓋目標的個數確定節點優先級。

Step 3:確定充電節點

在每個充電位置構建充電圓，確定充電節點，確定覆蓋方案時不考慮充電圓外的節點，如節點F不能作為覆蓋方案選擇節點。

Step 4:調度節點，實施目標概率覆蓋方案

根據2.3.2 確定充電周期中各單位時間內目標基于聯合概率感知的覆蓋方案，先確定各單位時間內的起始節點用于初始化Rk，根據Rk選擇起始目標并確定其覆蓋方案，再根據Vk依次確定剩余目標的覆蓋方案。

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

Step 5:優化充電部署，選定充電位置

以滿足目標持續覆蓋的能量需求為目標，選擇充電位置。

按照節點優先級從高到低的順序滿足節點充電需求，依次選擇MC 的充電位置，直到所有目標都實現了持續覆蓋。如圖2 所示，節點A優先級最高，MC 需先到達S1進行充電，再對節點B充電，MC 達到S2，此時可以實現目標V1，V2，V3的三種監測策略。MC 只需要在S1，S2停留，無需在S3停留，就可以實現持續目標覆蓋。

Step 6:移動周期充電

MC 根據確定的充電位置移動周期充電。

2.4.2 理論分析

假設節點數是N，充電位置數是M，目標數是V?M，由于每個節點需要對每個目標考核概率覆蓋，復雜度為O(NV)。針對每個充電位置，要考慮每個節點的充電情況，這一步的復雜度為O(NM)。因此，算法總復雜度為O(NV)。

3 仿真結果

本文運用MATLAB7.0 對此算法進行仿真，每組實驗數據采用重復50 次獨立實驗取平均值的方式獲得，默認參數如表5 所示。采用目標覆蓋率(coverage ratio，Cr)和充電能耗貢獻值(contribution)兩個指標。目標覆蓋率為能實現持續覆蓋的目標數/網絡中的總目標數。例如，在2.3 小節，在不采用聯合概率感知時，2Pf的充電能耗下，只有2 個目標實現了2 個單位的持續監測，這個時候的貢獻值為2×2/2 ＝2。而在2.4 小節，在采用聯合概率感知時，2Pf的充電能耗下，3 個目標全部實現3 個時間單位的持續監測，這個時候的貢獻值為3×3/2＝4.5。

表5 實驗參數

為了說明算法的性能，我們先采用文獻[2]方法，稱為感知算法(the continous target coverage scheme based on 0－1 sensing model，CtaR)，既不采用聯合感知，也不對目標點覆蓋進行優化篩選(即節點不根據目標覆蓋情況進行優先級排序)。接著采用聯合概率感知，但仍然不對目標點覆蓋進行優化篩選算法(the continous target coverage scheme based on joint probabilistic detection，CtarN)。

3.1 節點數量的影響

節點數量的影響如圖5 所示。節點數量越多，充電圓內節點越多，獲得能量的節點越多，網絡中持續覆蓋的目標越多，目標的覆蓋率越大。因此CtarN算法和CtaR 算法的目標覆蓋率隨節點數量的增加而增大。而CtarP 算法利用概率感知確定目標覆蓋方案，對每個目標點優先選取獲得覆蓋目標數最多的節點，充分利用節點的能量，目標覆蓋率較CtarN算法和CtaR 算法要大，如圖5(a)所示。

圖5 節點數量的影響

節點數量越多，每個充電位置處，可充電的節點數越多，網絡持續時間越長，充電位置選取越少，單位充電能耗對目標覆蓋的貢獻值越大。因此CtarN 算法和CtaR 算法的貢獻值隨節點數量的增加而增大，而CtarP 算法保證較高的目標覆蓋率的同時，尋找最優充電位置，用最少的充電能耗，高效實現持續目標覆蓋。因此算法CtarP 性能最優，如圖5(b)所示。

3.2 目標點數的影響

目標點數量的影響如圖6 所示。目標點數量越多，節點在概率感知范圍內的目標點數量越多，有更多的目標點可以被節點感知，獲得能量的節點在網絡中持續覆蓋目標點數量越多，目標的覆蓋率越大。三種算法的目標覆蓋率都隨目標點的增加而增大。CtarP 算法選取最優的節點對目標點進行覆蓋，使節點能夠同時完成更多目標的監測任務，能夠充分利用節點所捕獲的能量，因此CtarP 算法最優，如圖6(a)所示。

CtarP 算法在保證目標覆蓋數量最多的同時，優先選擇目標覆蓋數較多的節點確定目標覆蓋方案，相對于其他算法能充分利用節點能量，延長了網絡持續覆蓋時間，減少MC 充電位置，降低充電能耗。因此CtarP 算法在目標點數量增加時，增大單位能耗對目標覆蓋的貢獻值。CtarP 算法性能最優，如圖6(b)所示。

圖6 目標數的影響

3.3 概率閾值的影響

概率閾值的影響如圖7 所示。概率閾值越大，目標的雙概率圓的半徑越小，目標概率檢測方案越少，節點覆蓋目標點數量越少，目標覆蓋率越小。因此三個算法的目標覆蓋率隨概率閾值的增大而減小。CtarP 算法中，優先選擇覆蓋目標數多的節點，因此CtarP 算法的目標覆蓋率效果最好，如圖7(a)所示。

概率閾值越大，覆蓋的目標點數量越少，網絡持續時間越短，MC 充電位置選取越多，網絡充電能耗越大，單位能耗對目標覆蓋的貢獻值越小。CtarN算法和CtaR 算法的貢獻值隨概率閾值的增大而減少。在CtarP 算法中，概率閾值越大，增加了MC 充電停留位置，減少單位能耗對目標覆蓋的貢獻值，因此CtarP 算法的貢獻值隨概率閾值的增加而下降，如圖7(b)所示。

圖7 概率閾值的影響

3.4 充電位置數的影響

充電位置數量的影響如圖8 所示。充電位置數越多，可以得到充電的節點數量越多，可以監測目標的節點數量越多，目標的覆蓋率越大。三種算法的目標覆蓋率都隨充電位置數量的增加而提高。CtarP 算法通過節點的優先級確定目標的聯合概率感知的充電部署，選擇最優的充電位置對節點進行能量補充。因此CtarP 算法最優，如圖8(a)所示。

圖8 充電位置數的影響

CtarP 算法在保證目標覆蓋率的基礎上，選擇最優的充電位置對節點進行能量補充，延長網絡持續覆蓋時間，降低網絡充電能耗。因此CtarP 算法在充電位置數增加的同時，增大了單位能耗對目標覆蓋的貢獻值。CtarP 算法性能最優，如圖8(b)所示。

4 結束語

本文提出一種基于概率感知的持續目標覆蓋算法，首先根據聯合概率感知確定目標概率覆蓋集，接著對節點進行優先級排序，根據節點優先級確定整個充電周期內目標的覆蓋方案，最終優化單MC 充電部署，選擇高效率的充電位置滿足節點的充電需求。仿真結果表明CtarP 算法取得的目標覆蓋率優于同等條件下的其他算法，并在保證較高覆蓋率的同時，最大化充電能耗貢獻值，用最少的充電能耗實現了高效率的持續目標覆蓋。

如何在MC 攜帶能量有限的情況下，節能高效地實現持續目標覆蓋是下一步要研究的內容。