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

石 拓，李建中

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

0 引言

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

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

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

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

1.1 全覆蓋算法

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

1.2 部分覆蓋算法

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

1.3 k－覆蓋算法

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

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

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

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

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

3 結(jié)束語

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