無線傳感器網絡中覆蓋算法研究綜述

石 拓，李建中

（哈爾濱工業大學 計算學部，哈爾濱 150001）

0 引言

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

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

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

1 基于隨機性部署的傳感器網絡中的覆蓋算法

1.1 全覆蓋算法

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

1.2 部分覆蓋算法

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

1.3 k－覆蓋算法

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

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

2 基于確定性部署的傳感器網絡中覆蓋算法

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

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

3 結束語

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