無線傳感器網(wǎng)絡(luò)中覆蓋算法研究綜述

石 拓，李建中

（哈爾濱工業(yè)大學(xué) 計算學(xué)部，哈爾濱 150001）

0 引言

隨著移動通信技術(shù)和移動設(shè)備的不斷發(fā)展，物聯(lián)網(wǎng)技術(shù)也取得了長足地進(jìn)步［1－2］。無線傳感器網(wǎng)絡(luò)（Wireless Senor Network）是物聯(lián)網(wǎng)（IoT）中的重要組成部分，也是連接物理世界與信息世界的關(guān)鍵技術(shù)。一個無線傳感器網(wǎng)絡(luò)可以被部署到一個區(qū)域當(dāng)中，并對該區(qū)域中的物理信號（溫度、濕度、壓力等）進(jìn)行監(jiān)控，從而達(dá)到收集、分析該區(qū)域中的物理信息的目的。一個無線傳感器網(wǎng)絡(luò)由若干無線傳感器節(jié)點(diǎn)和sink 節(jié)點(diǎn)構(gòu)成。無線傳感器節(jié)點(diǎn)由自身配置的電池供能，并通過傳感器來獲取周圍環(huán)境中的物理信息，再通過通信模塊與其它傳感器節(jié)點(diǎn)或sink 節(jié)點(diǎn)進(jìn)行通信，sink 節(jié)點(diǎn)則會將所收集的物理世界的信息上傳到云端，供用戶進(jìn)行數(shù)據(jù)分析與處理。這樣，無線傳感器網(wǎng)絡(luò)既可以幫助人們打破物理世界與信息世界之間的信息壁壘，也為萬物互聯(lián)打下了基礎(chǔ)。由于無線傳感器節(jié)點(diǎn)的體積很小，且造價低廉，無線傳感器網(wǎng)絡(luò)可以被大規(guī)模地部署到人類很難到達(dá)的環(huán)境［3］。如：森林、山丘、戰(zhàn)場等，并在森林防火、災(zāi)情檢測、敵情偵查等方面產(chǎn)生了重要的作用。因此，通過無線傳感器網(wǎng)絡(luò)，人們幾乎可以對任意環(huán)境進(jìn)行監(jiān)控。覆蓋是傳統(tǒng)無線傳感器網(wǎng)絡(luò)中的一個重要問題，覆蓋質(zhì)量是評價網(wǎng)絡(luò)通信性能和監(jiān)控性能的重要指標(biāo)。覆蓋問題的解決，對于傳感器網(wǎng)絡(luò)的數(shù)據(jù)收集、數(shù)據(jù)聚集、數(shù)據(jù)查詢、數(shù)據(jù)挖掘等均具有重要的意義。

對于一個傳感器節(jié)點(diǎn)i，設(shè)li為i在監(jiān)控區(qū)域中的位置，rs為該節(jié)點(diǎn)的感知半徑。一般而言，若監(jiān)控目標(biāo)（單個點(diǎn)目標(biāo)，或者區(qū)域目標(biāo)）處在以li為中心，rs為半徑的圓內(nèi)，則認(rèn)為該監(jiān)控目標(biāo)被節(jié)點(diǎn)i所監(jiān)控（覆蓋）。根據(jù)覆蓋需求的不同，可以將無線傳感器網(wǎng)絡(luò)中的覆蓋方式分為3 種：全覆蓋、部分覆蓋和多覆蓋。全覆蓋是指網(wǎng)絡(luò)節(jié)點(diǎn)需要對所有監(jiān)控目標(biāo)進(jìn)行覆蓋；部分覆蓋是指網(wǎng)絡(luò)節(jié)點(diǎn)對所有監(jiān)控目標(biāo)的覆蓋達(dá)到某一給定的覆蓋率θ≤1；多覆蓋則是對于監(jiān)控區(qū)域內(nèi)的任意目標(biāo)（多指點(diǎn)目標(biāo)），在同一時刻被至少k個傳感器節(jié)點(diǎn)覆蓋（k為給定的正整數(shù)）。根據(jù)網(wǎng)絡(luò)部署方式的不同，無線傳感器網(wǎng)絡(luò)中的覆蓋問題可以分為兩類：基于隨機(jī)性部署和基于確定性部署的傳感器網(wǎng)絡(luò)中的覆蓋問題。隨機(jī)性部署是指網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)地部署到監(jiān)控區(qū)域，而確定性部署是指網(wǎng)絡(luò)節(jié)點(diǎn)的部署位置是經(jīng)過人為計算得到的。隨機(jī)性部署主要針對大規(guī)模的無線傳感器網(wǎng)絡(luò)，而確定性部署更偏重于小規(guī)模的無線傳感器網(wǎng)絡(luò)。對于基于隨機(jī)性部署的傳感器網(wǎng)絡(luò)中的覆蓋問題，主要研究如何通過合理地調(diào)度節(jié)點(diǎn)工作對網(wǎng)絡(luò)的覆蓋質(zhì)量進(jìn)行優(yōu)化；而基于確定性部署的傳感器網(wǎng)絡(luò)中的覆蓋問題，主要研究如何通過安排節(jié)點(diǎn)位置對網(wǎng)絡(luò)的覆蓋質(zhì)量進(jìn)行優(yōu)化。本文所介紹的相關(guān)工作見表1。

表1 不同覆蓋算法之間的對比Tab.1 The comparison between different coverage algorithms

1 基于隨機(jī)性部署的傳感器網(wǎng)絡(luò)中的覆蓋算法

1.1 全覆蓋算法

全覆蓋算法的目的，一般是通過調(diào)度節(jié)點(diǎn)工作以達(dá)到在對監(jiān)控目標(biāo)全覆蓋的前提下，最大化網(wǎng)絡(luò)壽命。部署在監(jiān)控區(qū)域中的傳感器節(jié)點(diǎn)數(shù)目往往是冗余的，因此，文獻(xiàn)［4－8］中的主要策略是，將網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)分為若干不相交的節(jié)點(diǎn)集合，并對不同集合中的傳感器節(jié)點(diǎn)進(jìn)行輪詢調(diào)度。當(dāng)一個集合中的節(jié)點(diǎn)處于工作狀態(tài)時，其它集合中的節(jié)點(diǎn)則處于休眠狀態(tài)。這種策略的目的是最大化網(wǎng)絡(luò)中的不相交節(jié)點(diǎn)集合的個數(shù)，從而優(yōu)化節(jié)點(diǎn)的能量消耗，最大化網(wǎng)絡(luò)壽命。文獻(xiàn)［4］中作者證明了最大化網(wǎng)絡(luò)中不相交節(jié)點(diǎn)集合問題是NP－完全的，同時不存在多項(xiàng)式時間內(nèi)的1.5 近似算法。與以上基于不相交節(jié)點(diǎn)集合策略不同，文獻(xiàn)［9－10］中通過構(gòu)造、調(diào)度相交的傳感器節(jié)點(diǎn)集合，來構(gòu)造網(wǎng)絡(luò)覆蓋。其策略是將傳感器節(jié)點(diǎn)的能量，按照單位時間內(nèi)的工作能耗進(jìn)行劃分，并根據(jù)劃分結(jié)果構(gòu)造不同的節(jié)點(diǎn)集合。因?yàn)樵谶@種劃分策略中充分考慮到了節(jié)點(diǎn)中的能量存儲，所以基于這種策略可以進(jìn)一步地延長網(wǎng)絡(luò)壽命，保證網(wǎng)絡(luò)覆蓋。在文獻(xiàn)［11］中，作者則提出了一個基于節(jié)點(diǎn)調(diào)度的網(wǎng)絡(luò)覆蓋算法。其策略是，節(jié)點(diǎn)通過“不工作準(zhǔn)則”來判斷是否需要工作?！安还ぷ鳒?zhǔn)則”是指，若該節(jié)點(diǎn)所監(jiān)控的區(qū)域已經(jīng)被其鄰居節(jié)點(diǎn)所覆蓋，則該節(jié)點(diǎn)可以選擇進(jìn)入休眠狀態(tài)。這樣，通過綜合地考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的覆蓋區(qū)域，以及鄰居節(jié)點(diǎn)之間的關(guān)系，可以有效地調(diào)度節(jié)點(diǎn)工作，合理地利用節(jié)點(diǎn)能量。同時，作者還討論了當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)感知半徑異構(gòu)時的網(wǎng)絡(luò)覆蓋算法。文獻(xiàn)［12］中作者則提出了分化監(jiān)控的策略，即在滿足全覆蓋的前提下，為較敏感、重要的監(jiān)控目標(biāo)提供更多的監(jiān)控節(jié)點(diǎn)。此外，監(jiān)控區(qū)域和監(jiān)控周期被分別劃分為不同的網(wǎng)格和時間段，傳感器節(jié)點(diǎn)則根據(jù)所處的網(wǎng)格和時間段來進(jìn)行工作調(diào)度。

1.2 部分覆蓋算法

相比于全覆蓋算法，部分覆蓋算法僅要求傳感器節(jié)點(diǎn)對網(wǎng)絡(luò)中的部分重要監(jiān)控目標(biāo)進(jìn)行覆蓋或滿足一定覆蓋率。文獻(xiàn)［13－14］中實(shí)驗(yàn)結(jié)果表明，部分覆蓋相較于全覆蓋可以顯著地提高網(wǎng)絡(luò)壽命。文獻(xiàn)［15］首次定義了傳感器網(wǎng)絡(luò)中的部分覆蓋問題，即θ－覆蓋。該問題要求在保證網(wǎng)絡(luò)連通的情況下，使得網(wǎng)絡(luò)覆蓋率至少為0≤θ≤1。作者證明了該問題為NP－難問題，并分析了在不同通信、感知半徑下，滿足θ－覆蓋的活躍傳感器節(jié)點(diǎn)數(shù)量上界?；讦龋采w的理論性質(zhì)，作者提出了時間復(fù)雜度為O（n3）的集中式啟發(fā)式算法。在初始時刻，算法隨機(jī)地選取工作的傳感器節(jié)點(diǎn)；在每一輪迭代中，則選擇處于候選路徑上具有最大收益的節(jié)點(diǎn)進(jìn)行工作。該算法迭代地進(jìn)行，直到監(jiān)控區(qū)域達(dá)到了θ－覆蓋。文獻(xiàn)［16］中也采用了這一策略，并提出了集中式和分布式兩種算法來解決部分覆蓋問題。為了能夠區(qū)別地對待不同的監(jiān)控區(qū)域，作者將監(jiān)控區(qū)域分成了不同的簇，并通過調(diào)度節(jié)點(diǎn)來對不同的簇依次進(jìn)行覆蓋。在文獻(xiàn)［17］中，作者定義了最大化傳感器網(wǎng)絡(luò)壽命問題，并提出了一個滿足傳感器網(wǎng)絡(luò)中部分覆蓋的，具有（1＋logn）近似比的集中式近似算法。根據(jù)該文中的實(shí)驗(yàn)結(jié)果，當(dāng)對傳感器網(wǎng)絡(luò)進(jìn)行90%覆蓋時，網(wǎng)絡(luò)壽命可以較全覆蓋情況下提高至少3.3 倍。文獻(xiàn)［18］中則采用了分治思想，來解決傳感器網(wǎng)絡(luò)中的部分覆蓋問題。其在基于節(jié)點(diǎn)位置信息的分布式PCCP 算法中，首先通過分治思想，將監(jiān)控區(qū)域進(jìn)行劃分，并在每一個劃分區(qū)域中對傳感器節(jié)點(diǎn)進(jìn)行合理調(diào)度，從而達(dá)到滿足網(wǎng)絡(luò)覆蓋率的要求。通過本文的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，隨著覆蓋率的逐漸遞減，網(wǎng)絡(luò)壽命隨之增加，當(dāng)覆蓋率從0.9 降為0.5 時，網(wǎng)絡(luò)壽命平均提高了75%。文獻(xiàn)［19］中提出了一個基于六邊形的部分覆蓋算法，來最大化網(wǎng)絡(luò)壽命。在文中，監(jiān)控區(qū)域被分為了若干單位六邊形，而傳感器節(jié)點(diǎn)則根據(jù)所屬的六邊形被分為若干組。文中通過提出了3 種規(guī)則，調(diào)度每組中的傳感器節(jié)點(diǎn)進(jìn)行工作。該算法可以在犧牲一部分覆蓋質(zhì)量的前提下，顯著地提高（約74%）網(wǎng)絡(luò)的壽命，但無法保證所犧牲的覆蓋質(zhì)量的界限。

1.3 k－覆蓋算法

對監(jiān)控區(qū)域進(jìn)行k－覆蓋，是傳感器網(wǎng)絡(luò)中覆蓋問題的一個重要分支。一方面，由于傳感器節(jié)點(diǎn)的不穩(wěn)定性，為了保障對監(jiān)控目標(biāo)的有效覆蓋，可以利用多個傳感器節(jié)點(diǎn)監(jiān)控同一目標(biāo)的策略，即每一個監(jiān)控目標(biāo)都被至少k個傳感器節(jié)點(diǎn)所監(jiān)控；另一方面，由于監(jiān)控區(qū)域中的監(jiān)控目標(biāo)的重要性和敏感程度的不同，對于用戶較為關(guān)心的監(jiān)控目標(biāo)，需要利用多個傳感器節(jié)點(diǎn)對其進(jìn)行監(jiān)控。文獻(xiàn)［20］首先研究了傳感器網(wǎng)絡(luò)中的k－覆蓋問題，并提出了一個基于位置信息的啟發(fā)式算法，根據(jù)不同的應(yīng)用為監(jiān)控區(qū)域提供不同程度的覆蓋，即k－覆蓋。然而，該算法無法保證所構(gòu)造覆蓋的大小，即無法保證節(jié)點(diǎn)的耗能。在文獻(xiàn)［21］中，作者則提出了一個能夠保證覆蓋大小的啟發(fā)式k－覆蓋算法，證明了算法所構(gòu)造的覆蓋的大小與最優(yōu)解大小之間存在著O（logn）的近似比。該算法的主要思想是，選擇候選路徑上具有最大收益的節(jié)點(diǎn)進(jìn)行工作。然而，以上兩種算法均只考慮了單個覆蓋的構(gòu)造，并沒有考慮如何將網(wǎng)絡(luò)中節(jié)點(diǎn)劃分成若干集合，并使得每個集合構(gòu)成一個網(wǎng)絡(luò)的k－覆蓋。在文獻(xiàn)［12］中，作者提出了能量有效的網(wǎng)絡(luò)覆蓋協(xié)議。該協(xié)議可以提供分化型監(jiān)控服務(wù)。節(jié)點(diǎn)可以通過動態(tài)地調(diào)度工作狀態(tài)，來為網(wǎng)絡(luò)提供k－覆蓋。雖然該協(xié)議可以有效地利用節(jié)點(diǎn)能量，但無法保證k ＞2 時的網(wǎng)絡(luò)覆蓋。在文獻(xiàn)［22］中，作者將覆蓋問題形式化為了一個判定問題，其目標(biāo)是判斷監(jiān)控區(qū)域中的任意一個點(diǎn)是否被至少k個傳感器節(jié)點(diǎn)所覆蓋。文中引入邊緣覆蓋層級（PCL）的概念。作者證明了整個監(jiān)控區(qū)域可以被傳感器網(wǎng)絡(luò)k－覆蓋，當(dāng)且僅當(dāng)每個監(jiān)控區(qū)域中的傳感器節(jié)點(diǎn)都被k－邊緣覆蓋。基于該工作，文獻(xiàn)［23］提出了兩個啟發(fā)式算法，來解決網(wǎng)絡(luò)的k－覆蓋問題。在算法中，網(wǎng)絡(luò)中節(jié)點(diǎn)被劃分為了若干集合，每個集合中的節(jié)點(diǎn)都可以對監(jiān)控目標(biāo)實(shí)現(xiàn)k－覆蓋，算法通過最大化劃分的集合個數(shù)來最大化網(wǎng)絡(luò)壽命。

基于隨機(jī)部署的傳感器網(wǎng)絡(luò)中覆蓋算法可以總結(jié)為，在達(dá)到延長網(wǎng)絡(luò)壽命的同時，使得網(wǎng)絡(luò)對監(jiān)控目標(biāo)實(shí)現(xiàn)一定規(guī)模的覆蓋。所有現(xiàn)存算法均著重考慮如何合理地調(diào)度節(jié)點(diǎn)，使得節(jié)點(diǎn)在監(jiān)控目標(biāo)的同時減少耗能。然而，由于傳感器節(jié)點(diǎn)自身能量受限，使得這類算法的輸出結(jié)果具有一定的限制。

2 基于確定性部署的傳感器網(wǎng)絡(luò)中覆蓋算法

當(dāng)傳感器節(jié)點(diǎn)數(shù)目較少時，可以通過合理地部署節(jié)點(diǎn)的位置來保障網(wǎng)絡(luò)覆蓋。在文獻(xiàn)［24］中，作者采用基于網(wǎng)格的節(jié)點(diǎn)部署策略，提出了一個感知模型，用來度量不同位置的感知效率。其次，文中將監(jiān)控區(qū)域劃分為不同的網(wǎng)格，并根據(jù)感知模型，來判斷需要部署節(jié)點(diǎn)的網(wǎng)格。該算法基于貪心策略，并迭代運(yùn)行。在每一輪迭代中，通過貪心策略來部署傳感器節(jié)點(diǎn)的位置，迭代在網(wǎng)絡(luò)的覆蓋目標(biāo)達(dá)成時終止。文獻(xiàn)［25］研究了水下無線傳感器網(wǎng)絡(luò)中最小化節(jié)點(diǎn)數(shù)目的全覆蓋節(jié)點(diǎn)部署算法。在這種網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)需要部署在海底，利用最少的傳感器節(jié)點(diǎn)達(dá)到最大的覆蓋，文中將監(jiān)控區(qū)域劃分成了三角網(wǎng)格，根據(jù)三角網(wǎng)格，就可以僅通過調(diào)整節(jié)點(diǎn)之間的距離關(guān)系來調(diào)整節(jié)點(diǎn)對目標(biāo)的覆蓋。作者經(jīng)實(shí)驗(yàn)證明：當(dāng)感知半徑r與三角網(wǎng)格的邊長d滿足d ＝時，則可以滿足全覆蓋的要求。文獻(xiàn)［26］的研究中，不僅考慮了部署節(jié)點(diǎn)對區(qū)域的覆蓋，同時也考慮了節(jié)點(diǎn)之間的連通關(guān)系。該文的目的是在監(jiān)控區(qū)域中部署節(jié)點(diǎn)，并在保障對監(jiān)控區(qū)域全覆蓋、網(wǎng)絡(luò)連通的前提下，最小化部署的節(jié)點(diǎn)數(shù)量。該研究中提出的算法保障了網(wǎng)絡(luò)的強(qiáng)聯(lián)通，即當(dāng)網(wǎng)絡(luò)中有節(jié)點(diǎn)死亡時，不影響網(wǎng)絡(luò)的連通性。文獻(xiàn)［27］中則考慮了當(dāng)網(wǎng)絡(luò)中存在多個sink 節(jié)點(diǎn)時的節(jié)點(diǎn)部署問題。該工作在保障網(wǎng)絡(luò)覆蓋、連通的前提下，達(dá)到最小化部署節(jié)點(diǎn)數(shù)量的目的。在該研究中，節(jié)點(diǎn)被分為兩類：一類為感知節(jié)點(diǎn)（負(fù)責(zé)感知、監(jiān)控目標(biāo)區(qū)域），另一類則為中繼節(jié)點(diǎn)（負(fù)責(zé)保障網(wǎng)絡(luò)的連通）。其算法分為兩個主要步驟：第一步，通過部署感知節(jié)點(diǎn)來保障節(jié)點(diǎn)對監(jiān)控目標(biāo)區(qū)域的覆蓋；第二步，則通過部署中繼節(jié)點(diǎn)來保障網(wǎng)絡(luò)的連通。在這兩步中，算法通過采用貪心策略和生成樹策略，來近似地減小所部署的節(jié)點(diǎn)數(shù)量。在文獻(xiàn)［28］中，作者考慮了傳感器網(wǎng)絡(luò)中的k－覆蓋m－連通問題，即通過部署傳感器節(jié)點(diǎn)，使得監(jiān)控區(qū)域中的每個監(jiān)控目標(biāo)都被至少k個傳感器節(jié)點(diǎn)所覆蓋；同時，網(wǎng)絡(luò)中的每個傳感器節(jié)點(diǎn)都與至少m個其它節(jié)點(diǎn)所連通。這一目的保障了網(wǎng)絡(luò)的穩(wěn)定性。當(dāng)網(wǎng)絡(luò)中有節(jié)點(diǎn)死亡時，因?yàn)橛腥哂喙?jié)點(diǎn)的存在，并不會影響網(wǎng)絡(luò)的功能。為了解決該問題，文中作者提出了一個基于遺傳算法的框架。

與基于隨機(jī)性部署的傳感器網(wǎng)絡(luò)中的覆蓋算法不同，在確定型部署的傳感器網(wǎng)絡(luò)中的覆蓋算法，將注意力集中在如何最小化部署的節(jié)點(diǎn)規(guī)模上。然而，如何將節(jié)點(diǎn)部署與節(jié)點(diǎn)調(diào)度想結(jié)合，研究網(wǎng)絡(luò)壽命與節(jié)點(diǎn)位置之間的潛在關(guān)系，從而進(jìn)一步地優(yōu)化傳感器網(wǎng)絡(luò)仍然是一個待解決的問題。

3 結(jié)束語

網(wǎng)絡(luò)覆蓋是無線傳感器網(wǎng)絡(luò)領(lǐng)域保證感知數(shù)據(jù)完整性和網(wǎng)絡(luò)連通性的一個重要技術(shù)，對于無線傳感器網(wǎng)絡(luò)中的諸多應(yīng)用，包括感知數(shù)據(jù)查詢處理、感知數(shù)據(jù)收集、感知數(shù)據(jù)聚集、感知數(shù)據(jù)挖掘等均具有重要的意義。研究者們在無線傳感器網(wǎng)絡(luò)中的覆蓋問題上已深耕多年，存在多種不同的覆蓋算法。本文對現(xiàn)有的無線傳感器網(wǎng)絡(luò)中的覆蓋算法按照不同的網(wǎng)絡(luò)拓?fù)?、不同的覆蓋類型進(jìn)行了總結(jié)與分析，對于這些現(xiàn)存算法進(jìn)行了總結(jié)，對現(xiàn)有工作的優(yōu)缺點(diǎn)進(jìn)行了分析，望對相關(guān)問題的進(jìn)一步研究提供了有效依據(jù)。