劉永攀，王 然

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

定向傳感器網(wǎng)絡(luò)(Directional Sensor Networks，DSN)[1-4]在生活中具有廣泛的應(yīng)用，包括目標(biāo)監(jiān)視、入侵檢測、環(huán)境監(jiān)測、目標(biāo)檢測、目標(biāo)跟蹤等。定向傳感器的監(jiān)測范圍由傳感器的監(jiān)測半徑、監(jiān)測夾角和監(jiān)測方向共同決定，這使得DSN的應(yīng)用比全向傳感器網(wǎng)絡(luò)的應(yīng)用更為復(fù)雜。在無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)中，傳感器節(jié)點(diǎn)由能量有限的電池供電。如果傳感器不能充電，則需要部署額外的傳感器或頻繁更換電池以保證網(wǎng)絡(luò)正常工作。早期研究大多沒有考慮能量補(bǔ)充[5-7]。隨著能量獲取技術(shù)的出現(xiàn)，傳感器可以從其周圍的環(huán)境中捕獲各種可再生能源[8-9]，例如太陽能、風(fēng)能和熱能，來延長WSN的生命周期。然而，在實(shí)踐中，傳感器的能量消耗率通常要高于充電速率[10]。因此，傳感器節(jié)點(diǎn)需要通過能量平衡操作才能實(shí)現(xiàn)網(wǎng)絡(luò)的持續(xù)運(yùn)行[10-12]。不同地點(diǎn)可能會(huì)因?yàn)榻ㄖ系K物、樹蔭等因素而導(dǎo)致能量采集率各不相同[13]。因此，高效低成本地利用外部能源為傳感器充電來保證網(wǎng)絡(luò)的永久運(yùn)行是一個(gè)重要的研究課題。

目前，使用太陽能充電的目標(biāo)覆蓋問題已經(jīng)引起了人們的關(guān)注。部分研究人員探究了不考慮連通性的太陽能充電的目標(biāo)覆蓋問題[11，13-15]。文獻(xiàn)[11]將最少節(jié)點(diǎn)部署問題表述為一個(gè)整數(shù)線性規(guī)劃，并提出了3種近似算法來求解。文獻(xiàn)[13]考慮了將太陽能充電和無線充電技術(shù)結(jié)合，通過兩者優(yōu)勢互補(bǔ)來提高監(jiān)測的覆蓋質(zhì)量。在實(shí)際應(yīng)用中，采集到的數(shù)據(jù)需要傳輸?shù)交?，因此保證網(wǎng)絡(luò)的連通性就顯得至關(guān)重要。一些研究探討了滿足目標(biāo)覆蓋要求和在網(wǎng)絡(luò)連通性的前提下，部署能量采集WSN。文獻(xiàn)[12]考慮了能量收集定向傳感網(wǎng)絡(luò)中目標(biāo)覆蓋的最佳部署問題。該研究將問題定義為混合整數(shù)線性規(guī)劃問題，并提出3種啟發(fā)式方法，最后根據(jù)每個(gè)位置的能量消耗計(jì)算出所需太陽能板的面積。文獻(xiàn)[10]將監(jiān)測區(qū)域劃分為網(wǎng)格，提出滿足能量平衡情況下最少傳感器的0/1全向覆蓋問題。此外，該研究還提出了基于貪心的啟發(fā)式算法來生成候選點(diǎn)集合，并利用直接搜索算法和貪心搜索算法來確定傳感器放置的最終位置。上述研究采用的都是單一類型傳感器，但是使用單一類型傳感器進(jìn)行部署缺乏靈活性且部署成本較高，而在網(wǎng)絡(luò)中同時(shí)部署多種類型的方向傳感器可更有效地節(jié)省部署成本[16]。

本文考慮能量收集異構(gòu)定向傳感網(wǎng)絡(luò)中的最小成本目標(biāo)覆蓋問題。異構(gòu)指網(wǎng)絡(luò)由監(jiān)測半徑、監(jiān)測夾角和價(jià)格均不同的可捕獲太陽能的定向傳感器節(jié)點(diǎn)組成。本文給定一組隨機(jī)的候選部署位置和一組需要被監(jiān)測的目標(biāo)，通過從候選部署位置中選取合適的位置部署最佳的定向傳感器類型和監(jiān)測方向來滿足所有目標(biāo)的覆蓋要求。此外，本文選擇合適的位置部署中繼節(jié)點(diǎn)來滿足網(wǎng)絡(luò)的連通性，并通過能量平衡操作來保證網(wǎng)絡(luò)的永久運(yùn)行，使得能量收集定向傳感網(wǎng)絡(luò)的部署成本最小化。能量平衡操作是指通過多個(gè)傳感器輪流工作來保證該位置總的獲取消耗率不低于能量消耗率，處于休眠狀態(tài)下時(shí)則會(huì)保存能量和獲取能量。

1 模型以及問題描述

1.1 監(jiān)測模型

本文的監(jiān)測區(qū)域是一個(gè)矩形，里面隨機(jī)分布若干目標(biāo)T={t1，…，tN}，存在可部署傳感器的候選點(diǎn)集合O={o1，…，oM}和一個(gè)基站oM+1。

圖1 定向傳感器模型

σi，j，k，l=

(1)

1.2 能耗模型

WSN中傳感器的類型可分為兩類：監(jiān)測節(jié)點(diǎn)(Sensor Nodes，SNs)和中繼節(jié)點(diǎn)(Relay Nodes，RNs)。SNs在監(jiān)測目標(biāo)時(shí)會(huì)持續(xù)地產(chǎn)生監(jiān)測數(shù)據(jù)，并通過RNs將數(shù)據(jù)傳輸?shù)交?。在整個(gè)數(shù)據(jù)傳輸過程中存在3類能耗：監(jiān)測能耗、接收能耗和傳輸能耗。本文用μ(單位為bit·s-1)表示監(jiān)測單個(gè)目標(biāo)時(shí)單位時(shí)間產(chǎn)生的數(shù)據(jù)量。傳感器中單位比特?cái)?shù)據(jù)的監(jiān)測能耗為Es，傳輸能耗為Et，接收能耗為Er，能耗單位是Joule·bit-1。從路由結(jié)構(gòu)的角度來看，中繼節(jié)點(diǎn)的放置模型可以分為兩類：單層和雙層[17]。在單層中繼節(jié)點(diǎn)布局中，SNs和RNs都轉(zhuǎn)發(fā)報(bào)文；在雙層模型中，只有RNs轉(zhuǎn)發(fā)報(bào)文，SNs僅限于數(shù)據(jù)收集和將數(shù)據(jù)傳輸給RNs(或者直接與基站通信)。本文采用雙層模型，因?yàn)樗?jié)能，并能夠保護(hù)SNs有限的資源。

(2)

其中，Zi表示部署節(jié)點(diǎn)oi所能監(jiān)測的目標(biāo)集合；Ni表示所有與oi通信的部署節(jié)點(diǎn)的集合；fih表示從部署節(jié)點(diǎn)oi到oh的數(shù)據(jù)傳輸率。

1.3 能量收集

部分應(yīng)用要求傳感器能夠?qū)崿F(xiàn)對目標(biāo)的永久覆蓋[10，12]。文獻(xiàn)[12]為傳感器定制太陽能電池板以實(shí)現(xiàn)永久覆蓋。電池板的大小與該位置的能量獲取率有關(guān)，但該研究中定制太陽能電池板的方式不符合實(shí)際需求。本文采用固定大小的太陽能電池板。太陽能能量獲取模型[12]包括太陽能電池板、充電電路和1個(gè)超級(jí)電容器。部署節(jié)點(diǎn)oi處的能量獲取率為

Γ=ξ1ξ2χiA

(3)

式中，ξ1表示太陽能電池板能量轉(zhuǎn)化率；ξ2表示電池板的充電效率；χi表示部署節(jié)點(diǎn)oi處的平均太能光照強(qiáng)度，單位為W·m-2；A表示太陽能設(shè)備的表面積。

由于光強(qiáng)隨時(shí)間而改變，部分研究中使用平均值來表示光強(qiáng)，本文也采用這種方式。不同的地方由于地勢和障礙物的阻擋會(huì)有不同的平均光照強(qiáng)度，當(dāng)所選取位置上部署的傳感器單位時(shí)間能量消耗不大于單位時(shí)間獲取的能量時(shí)，就可以達(dá)到連續(xù)覆蓋的效果。文中使用的傳感器具有相同大小的太陽能電池板，所以單位時(shí)間的能量獲取只與當(dāng)前位置的光照強(qiáng)度有關(guān)。

不同位置的能量收集率會(huì)限制部署在當(dāng)前位置傳感器的傳輸能力。如果單位時(shí)間補(bǔ)充的電量無法滿足消耗，當(dāng)前位置的就要多放置一個(gè)或者多個(gè)傳感器，否則當(dāng)前位置部署的節(jié)點(diǎn)最終能量還是會(huì)耗盡，導(dǎo)致通信失效。

1.4 問題定義

定義1能量收集異構(gòu)定向傳感網(wǎng)絡(luò)的最小成本目標(biāo)覆蓋問題(Minimum Cost Deployment of Energy-Harvesting Heterogeneous Directional Sensor Networks for Target Coverage，MCEH)。在給定的L×H區(qū)域中，有目標(biāo)集合T={t1，t2，…，tN}，候選點(diǎn)集合O={o1，o2，…，oM}，基站為oM+1，不同位置的能量獲取率為R={R1，R2，…，RM}。從傳感器集合H={H1，H2，…，HZ}中選擇合適的傳感器類型放置在O上。本文的目標(biāo)是放置傳感器，使得目標(biāo)ti都能夠達(dá)到覆蓋要求qi，即目標(biāo)ti至少需要被qi個(gè)傳感器覆蓋。監(jiān)測節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)能夠通過中繼節(jié)點(diǎn)傳輸?shù)交?，并且每個(gè)傳感器節(jié)點(diǎn)能夠保持能量均衡。為滿足上述要求，本文需要為每個(gè)部署位置選擇合適的傳感器類型、合適的監(jiān)測方向以及最佳的通信路徑，并且在同一個(gè)部署節(jié)點(diǎn)放置多個(gè)相同類型的傳感器，使得當(dāng)前位置能量消耗不會(huì)多于獲取的能量總和，最終使部署整個(gè)傳感器網(wǎng)絡(luò)總成本最小。

接下來本文給出MCEH的優(yōu)化目標(biāo)和約束

(4)

約束條件為

(5)

(6)

(7)

(8)

xi，j，l∈{0，1}，?i∈O，?j∈Dl，?l∈H

(9)

1.5 NP-hard問題證明

定向覆蓋集DCS問題被證明是NP-hard[18-19]，通過證明MCEH是DCS的一種特殊情況即可完成證明。

文獻(xiàn)[18]研究了定向傳感網(wǎng)絡(luò)的最大生命周期問題。DCS問題指為每個(gè)定向傳感器選擇一個(gè)工作方向以達(dá)到給定目標(biāo)能夠至少被一個(gè)傳感器覆蓋。本文的簡化操作如下：

(1)前面定義了qk為目標(biāo)ti的覆蓋要求，假設(shè)所有的傳感器僅監(jiān)測一個(gè)目標(biāo)，即q1=q2=…=qN=1；

(3)假設(shè)傳感器的種類數(shù)Z=1；

(4)假設(shè)所有的傳感器不存在能耗，即Es=Et=Er=0。

簡化之后的MCEH就轉(zhuǎn)化成DCS問題。因?yàn)镈CS是NP-hard，所以本文提出的MCEH問題也是NP-hard問題。

2 算法設(shè)計(jì)

針對MCEH問題，本節(jié)提出了啟發(fā)式二階段選擇算法(Heuristic Two-stage Selection Algorithm，HTS)，該算法分為4個(gè)步驟：

步驟1構(gòu)建高效候選點(diǎn)；

步驟2監(jiān)測節(jié)點(diǎn)的選擇；

步驟3收縮范圍及撤銷冗余；

步驟4路由的選擇及更新。

2.1 構(gòu)建高效候選點(diǎn)

當(dāng)網(wǎng)絡(luò)規(guī)模增大且定向傳感器類型多樣時(shí)，直接從候選點(diǎn)集合O={o1，o2，…，oM}中挑選位置來放置傳感器會(huì)增加算法的時(shí)間復(fù)雜度。由于可選的位置有N種，每種位置有Z種傳感器可選，而每種傳感器又有K個(gè)工作方向，則可選的部署方式有(NZ)k種情況。通過保留高效候選點(diǎn)可以有效地減小選點(diǎn)的時(shí)間復(fù)雜度。通常情況下，傳感器的能量消耗率要高于充電速率，所以需要在同一個(gè)部署節(jié)點(diǎn)放置多個(gè)相同類型的傳感器才能保證能量平衡。當(dāng)某個(gè)候選位置的能量采集率比較高或者覆蓋的目標(biāo)數(shù)比較多時(shí)，則在該點(diǎn)保持能量平衡所需的傳感器個(gè)數(shù)就相對較少。本文定義能量采集率較高或者能夠覆蓋的目標(biāo)數(shù)較多的位置為高效候選點(diǎn)。

圖2舉例說明了在O={o1，o2，…，o10}中進(jìn)行兩輪選取的過程。根據(jù)上述流程，經(jīng)歷第一輪之后可得到Ω1={o2，o4，o7，o9}，然后從O中移除Ω1，繼續(xù)選取得到Ω2={o1，o3，o6，o8}。構(gòu)建候選點(diǎn)的算法見HTS構(gòu)建候選點(diǎn)集合。

(a)

HTS構(gòu)建候選點(diǎn)集合Input:O={o1,o2,…,oM}; R1, R2,…,RM; T={t1, t2,…,tN};1. r′=max{rl|Hl∈H}; α′ = 2π;2. for oi∈O, ti∈T do3. if di,k> r′;O = O - oi ;4. end for5. Ω =?; T ′ = T;6. while epoch>0 do7. k = k+1;8. Ωk=?;9. while T ′ ≠? do10. i?= arg max Ri|Zi|;11. if Z?i= ? break;12. Ωk= Ωk∪{i?}13. T = T ′- Z?(i);14. end while15. if T ′ ≠ ? break; 16. Ω = Ω∪Ωk; T ′=T; epoch = epoch-1;17. end while18. reindex Ω to O={o1,o2,…,o|Ω|};

2.2 監(jiān)測節(jié)點(diǎn)的選擇

(10)

新的增益同時(shí)考慮了上述4個(gè)因素，-λFi，O(M+1)對增益有擾動(dòng)效果。在保證覆蓋質(zhì)量變動(dòng)不大的情況下，Ri|Ti，j，l∩T′|/pl比值變化不大，gi，j，l會(huì)隨著λFi，O(M+1)的增大而增大，從而保證每個(gè)部署節(jié)點(diǎn)覆蓋質(zhì)量相差不多的情況下，優(yōu)先考慮較遠(yuǎn)的部署點(diǎn)。這樣操作可充分利用共享路由，節(jié)省部署成本。

有了增益gi，j，l的定義，每一輪選擇增益最大的部署方式ρi*j*l*，然后遍歷ρi*j*l*能夠覆蓋的剩余目標(biāo)集合Ti*j*l*∩T′，將該集合中每個(gè)目標(biāo)的覆蓋要求數(shù)減少一個(gè)單位，即qi-1。如果目標(biāo)的覆蓋要求已達(dá)到，則從剩余目標(biāo)集合T′中剔除。將該節(jié)點(diǎn)i*加入監(jiān)測集合C，并且更新oi*處的監(jiān)測能耗。當(dāng)T′=? 時(shí)，完成監(jiān)測節(jié)點(diǎn)的選擇。最后還需要保證監(jiān)測節(jié)點(diǎn)的能量均衡。

2.3 收縮范圍及撤銷冗余

當(dāng)部署完監(jiān)測節(jié)點(diǎn)之后，還需要判斷所有監(jiān)測節(jié)點(diǎn)的傳感器能否收縮監(jiān)測范圍甚至撤銷該部署節(jié)點(diǎn)。圖3(a)展示了部署完監(jiān)測節(jié)點(diǎn)之后，需要收縮監(jiān)測范圍的情況。假設(shè)所有目標(biāo)的覆蓋要求都是2，按照監(jiān)測節(jié)點(diǎn)的選擇流程，依次在o1、o2、o3處部署合適類型的傳感器。由于選擇傳感器的過程基于貪心策略，所以在o2處部署傳感器時(shí)，無法得知t3會(huì)被o3處的傳感器覆蓋。如果可以使用半徑更小，或者夾角更小的傳感器替代o2處的傳感器，則可以進(jìn)一步節(jié)省成本。圖3(b)和圖3(c)是圖3(a)調(diào)整監(jiān)測半徑和監(jiān)測夾角之后的圖例。節(jié)點(diǎn)可撤銷的情況是指部署完監(jiān)測節(jié)點(diǎn)之后，移除存在某些部署節(jié)點(diǎn)位置的傳感器仍然能夠保證所有的目標(biāo)達(dá)到覆蓋要求。如圖3(d)所示，在圖3(a)的條件下，為了覆蓋t5，在o4處部署一個(gè)傳感器，此時(shí)t4也被覆蓋到，那么移除o3位置的傳感器，傳感器t1～t4仍然能夠達(dá)到覆蓋要求。

(a)

為了解決上述兩種情況，具體的處理流程如下：遍歷所有的監(jiān)測節(jié)點(diǎn)，對于每一個(gè)監(jiān)測節(jié)點(diǎn)而言，首先嘗試移除該位置的傳感器，并判斷該位置監(jiān)測范圍內(nèi)的所有的目標(biāo)是否仍然滿足覆蓋要求。如果仍滿足要求則移除并繼續(xù)判斷下一個(gè)節(jié)點(diǎn)，如果不滿足則嘗試縮小監(jiān)測半徑或者監(jiān)測夾角；其次，從可選的傳感器中分別找到能夠滿足覆蓋要求的具有最小監(jiān)測半徑、最小監(jiān)測夾角的傳感器，使用成本最小的傳感器替換當(dāng)前位置的傳感器，然后繼續(xù)判斷下一個(gè)節(jié)點(diǎn)。

2.4 路由的選擇及更新

接下來是通信路徑的選擇。如果僅為每個(gè)監(jiān)測節(jié)點(diǎn)執(zhí)行Dijkstra最短路徑算法，那么每個(gè)中繼節(jié)點(diǎn)的剩余能量就無法充分被利用，也無法考慮每個(gè)位置的能量獲取率。對于這部分能量，本文給出結(jié)余能量的定義，見定義3。如果能讓通信路徑共用部分中繼節(jié)點(diǎn)，就可以利用結(jié)余能量，減少中繼成本。初始狀態(tài)下可通信的兩個(gè)節(jié)點(diǎn)邊的權(quán)重wi，j=1，遍歷每一個(gè)監(jiān)測節(jié)點(diǎn)，求得到達(dá)匯點(diǎn)的最短路徑之后，更新路徑上每個(gè)節(jié)點(diǎn)的能量消耗，更新所有指向oj的邊的權(quán)重(Dj.r%Rj)/Rj。Dj.r表示部署在節(jié)點(diǎn)oj處的中繼能量消耗率。求得所有監(jiān)測節(jié)點(diǎn)的通信路徑后，計(jì)算總成本。

綜上所述，HTS算法的偽代碼如下所示。

3 模擬實(shí)驗(yàn)

本文進(jìn)行了大量的仿真實(shí)驗(yàn)，將HTS算法與現(xiàn)有相關(guān)文獻(xiàn)中基于太陽能的定向傳感網(wǎng)絡(luò)中最小成本部署策略進(jìn)行對比。實(shí)驗(yàn)結(jié)果證實(shí)了本文提出的HTS算法性能要優(yōu)于其他對比算法。

3.1 參數(shù)設(shè)置

為了驗(yàn)證HTS算法的性能，本文對不同參數(shù)進(jìn)行了模擬實(shí)驗(yàn)。每組數(shù)據(jù)為50次實(shí)驗(yàn)結(jié)果的平均值。仿真參數(shù)及其數(shù)值見表1。

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

3.2 對比實(shí)驗(yàn)

本節(jié)將HTS與SRIGH兩個(gè)算法進(jìn)行對比。文獻(xiàn)[12]在能量收集定向傳感網(wǎng)絡(luò)中尋找滿足目標(biāo)覆蓋的最小成本部署方案，通過SRIGH算法每次找到效用最高的傳感器，并迭代出通信路徑，通過計(jì)算每個(gè)點(diǎn)的能耗來確定需要的太陽能電池板面積。與本文網(wǎng)絡(luò)模型不同，文獻(xiàn)[12]中使用的是單一類型傳感器。本文對SRIGH算法進(jìn)行改進(jìn)，選用多種類型的傳感器進(jìn)行部署。在默認(rèn)情況下，候選點(diǎn)個(gè)數(shù)為200，目標(biāo)的個(gè)數(shù)是25，傳感器類型有4種。實(shí)驗(yàn)結(jié)果顯示，HTS算法要優(yōu)于SRIGH算法。

圖4中給出了兩種算法的網(wǎng)絡(luò)部署成本與目標(biāo)數(shù)量之間的關(guān)系。相比SRIGH，HTS的部署成本降低了5%左右。因?yàn)镠TS算法綜合考慮了部署節(jié)點(diǎn)能夠覆蓋的目標(biāo)數(shù)、能量收集率、價(jià)格和到匯點(diǎn)的跳數(shù)4個(gè)因素，在部署監(jiān)測節(jié)點(diǎn)的同時(shí)考慮了后續(xù)中繼節(jié)點(diǎn)的部署，并且中繼節(jié)點(diǎn)能夠復(fù)用之前的通信路徑，因此節(jié)省了中繼成本。而SRIGH算法在得到監(jiān)測節(jié)點(diǎn)時(shí)直接求出到匯點(diǎn)的最短路徑，并未考慮已經(jīng)求得的中繼路徑，某些點(diǎn)可能剩余了較多的可用能量。

圖4 目標(biāo)數(shù)量和部署成本關(guān)系

圖5中給了兩種算法的網(wǎng)絡(luò)部署成本與候選點(diǎn)個(gè)數(shù)的關(guān)系。從圖中可知，隨著候選點(diǎn)個(gè)數(shù)的增多，HTS和 SRIGH均先小幅下降后趨于平穩(wěn)，但HTS的部署成本始終低于SRIGH。相比SRIGH，HTS的部署成本降低了7%左右。這是因?yàn)镠TS隨著候選個(gè)數(shù)的增多會(huì)選擇更多更優(yōu)秀的部署節(jié)點(diǎn)以節(jié)省網(wǎng)絡(luò)成本，而SRIGH對候選點(diǎn)的特點(diǎn)挖掘不充分，不能有效利用節(jié)點(diǎn)位置信息。

圖5 候選點(diǎn)個(gè)數(shù)和部署成本關(guān)系

圖6給出了部署成本和傳感器類型數(shù)量之間的關(guān)系。從圖中可以看出，相比SRIGH，HTS降低了10%～18%左右的部署成本。HTS充分利用了傳感器的異構(gòu)性，在部署完監(jiān)測節(jié)點(diǎn)之后，會(huì)嘗試收縮監(jiān)測節(jié)點(diǎn)的監(jiān)測范圍甚至撤銷該部署節(jié)點(diǎn)，因此能夠更好地節(jié)省部署成本。圖7中給出了網(wǎng)絡(luò)部署成本與傳輸半徑之間的關(guān)系。從圖中可以看出，HTS相比SRIGH降低了10%左右的成本。綜上所述，當(dāng)傳感器的類型較多樣化時(shí)，本文提出的算法能夠降低10%～18%的部署成本。

圖6 傳感器類型數(shù)量和部署成本關(guān)系

圖7 傳輸半徑和部署成本關(guān)系

4 結(jié)束語

本文研究了能量采集異構(gòu)定向傳感網(wǎng)絡(luò)的最小成本目標(biāo)覆蓋問題，并針對該問題設(shè)計(jì)了啟發(fā)式算法HTS。該算法通過構(gòu)建高效候選點(diǎn)降低了算法的時(shí)間復(fù)雜度，并設(shè)計(jì)效用函數(shù)評(píng)價(jià)每一種部署方式，更有效地平衡了各種影響因素。此外，該算法在初步確定監(jiān)測節(jié)點(diǎn)的部署方式之后通過消除冗余節(jié)點(diǎn)以及收縮監(jiān)測范圍進(jìn)一步節(jié)省了部署成本。本文通過仿真實(shí)驗(yàn)將HTS算法與同類型算法進(jìn)行了對比，實(shí)驗(yàn)結(jié)果表明，本文提出的HTS算法能夠有效降低部署成本。