覆蓋模型的傳感器網絡壽命問題建模及其求解

趙海軍，賀春林，蒲 斌，陳毅紅

1.西華師范大學 計算機學院，四川 南充637009

2.物聯網感知與大數據分析南充市重點實驗室，四川 南充637009

目前，無線傳感器網絡中的能量優化極為重要，因為與傳統的Ad-hoc 網絡相比，它們在功耗、計算能力和存儲容量方面都受到一定限制。因此，無線傳感器網絡中的最優化能量消耗已成為最重要的性能指標。

傳感器節點一般只能配備有限的電源/電池（本文稱為初始能量供給）。在某些應用場合，電源的補給是不可能的。正如文獻[1]所指出，電池的能量密度每5～20 年僅增加1 倍，這表明能量管理是傳感器網絡的關鍵。

傳感器網絡中傳感器節點的主要任務是監控事件，即收集數據和快速執行本地數據匯聚，然后傳送數據。因此，能量消耗體現在三方面：感知、數據匯聚和通信。數據匯聚的能量實際上不受監測調度的影響，對于文獻[6]提出的分布式自組織調度來說，沒有考慮相關的能量損失和增加的通信開銷。文獻[7]提出了一種用網格數據結構來表示一個區域上的傳感器節點覆蓋，構成一個×陣列來分割區域，然后為每個點確定出覆蓋傳感器圓盤形的子集。在這種模型中，如果網格點較少，則要覆蓋的區域就不好確定，如果網格非常精細，則計算開銷就相當大，因此這種模型很難適合實際的傳感器網絡覆蓋。文獻[8-9]把網絡覆蓋問題簡化為不相交集覆蓋問題，即假設任何傳感器不能參與其他不同的傳感器覆蓋，這樣，每個傳感器只能從休眠模式轉換為活躍模式才能覆蓋相應的區域，從而造成覆蓋孔洞和能量的巨大消耗。文獻[10]針對柵格統計法的不足，提出了一種基于圓弧并面積的幾何覆蓋率算法。這種算法盡管提高了覆蓋率，但沒有對參與覆蓋的傳感器節點的能量消耗和通信開銷加以考慮，在傳感器數量較大且并發傳輸的情況下可能造成網絡中斷。文獻[11]基于網格點的區域覆蓋算法未考慮網絡的固有特征，導致算法存在近似及復雜度偏高等問題，提出了基于改進的粒子群算法和特征點集優化的區域覆蓋算法。這種算法一方面僅考慮了傳感器網絡的區域最佳覆蓋，而未對整個網絡的覆蓋壽命加以考慮，另一方面則是著重于減少覆蓋算法的復雜度，因此不太適合實際應用。文獻[12]針對有向傳感器網絡全覆蓋問題，基于有向傳感器節點概率感知模型提出了一種有向傳感器節點部署結構，并引入標準工作方向的概念，使用奈曼-皮爾森準則數據融合方式，以最少的傳感器節點實現目標區域全覆蓋。但這種覆蓋感知模型需要傳感器節點強大的數據處理能力和通信能力，從而造成網絡大量的能量消耗，進而縮短傳感器網絡的壽命，同時也增加了網絡部署的成本。文獻[13]提出了一種定向功率管理技術操作系統來提高傳感器節點的能量效率，但是這種技術的復雜性造成了覆蓋部署的難度和可操作性。文獻[14-15]的模型假設無線傳感器網絡的大多數能量消耗來自于尋由的流量，而不是監測，從而減少網絡生存壽命。

基于現有算法關于傳感器網絡壽命問題（sensor network life problem，SNLP）研究的側重點不同以及存在的某些不足，本文提出了一種新的傳感器網絡覆蓋模型及其數據結構，并在此基礎上把SNLP 等效為它的對偶問題——最小權值傳感器覆蓋問題；然后把SNLP 構建為一個包裝的線性規劃，分別提出了求解它的集中式算法和分布式算法。仿真實驗結果表明，本文提出的基于傳感器網絡覆蓋模型和數據結構的SNLP 及其求解算法，能夠使得模型和求解算法在質量、可擴展性和靈活性方面表現出較好的優勢。

1 傳感器網絡覆蓋模型及其數據結構

1.1 傳感器網絡的建模

為了研究傳感器網絡的壽命問題，首先對要研究的傳感器網絡進行建模。假設傳感器部署在需要監測的區域上，且每個傳感器p有它自己的監測區域（或稱覆蓋區域）R，即p無需借助于任何其他傳感器，可以收集來自R的可信數據。還假設每個傳感器p具有一定的初始能量供給b，由于能量消耗可以與時間消耗對應起來，即一個傳感器的初始能量越大，可以消耗的時間就越長，因此也可把能量用時間來度量（為簡便起見，本文的時間一律是指歸一化單位時間）。同時還假設實際部署的傳感器數量超過監測區域所需要的傳感器數量，這樣才有可能把一些傳感器置于空閑模式，以節省它們的能量來延長網絡壽命，傳感器可以多次切換它們的模式。主要的限制條件就是監測區域（或指定的部分區域）必須完全在任何時刻被活躍的傳感器覆蓋。目標就是使感知能量消耗最小化，從而使得傳感器網絡壽命最大化。

首先給出能量保存調度問題的形式化定義。

把一組覆蓋的傳感器集合稱為傳感器覆蓋，則一個監測調度就是(,),(,),…,(C,t) 的對集合，這里C是一個傳感器覆蓋，t是C有效的覆蓋時間。

傳感器網絡壽命問題（SNLP）：

給定一個監測區域，一組傳感器,,…,p和每個傳感器p的監測區域R以及初始能量供給b，尋找一個具有最大時間長度++…+t的監測調度(,),(,),…,(C,t)，其中=1,2,…,，以使對于任意傳感器p來說，總的活躍時間不超過b。

圖1 給出了一個實例來說明多模式交換的優勢。實例中有3 個傳感器，各自具有圓盤形的監測區域、和，任意兩個傳感器都可以覆蓋監測區域，但任意單個傳感器都不能覆蓋。

圖1 3 個具有圓盤形監測區域傳感器監測方形區域Fig.1 Three sensors with disc monitored regions monitoring square region

假設它們監測內部的一個方形暗區，每個傳感器有2 個時間單位的初始能量供給，只存在一個不相交的傳感器覆蓋，它可以持續2 個時間單位；顯然，調度({,},1),({,},1),({,},1) 是可行的且持續3個時間單位。

為了求解SNLP，需要找到可行的傳感器覆蓋，即把求解SNLP 的問題變成求解它的對偶問題——最小權值傳感器覆蓋問題。可以把這個對偶問題表述為：

給定一個監測區域，一組傳感器,,…,p和對于任意傳感器p的監測區域R以及權值w，尋找具有最小總權值的傳感器覆蓋。

1.2 傳感器覆蓋的數據結構

把監測區域用一個平面圖形=(,)來表示，其中頂點集對應于全部傳感器覆蓋區域（如圓盤形）的邊界的交叉連接點，邊集連接沿著傳感器圓的邊界的相鄰交叉點的對點。如圖2 所示，平面圖形=(,)有10 個頂點，21 個邊和13 個面。

圖2 具有圓盤形監測區域的4 個傳感器的數據結構Fig.2 Data structure for 4 sensors with disc monitored regions

可以看出，圖的面即是通過邊使分割后的有限個平面部分。如果一個面的至少一個內部點被一個傳感器覆蓋，那么整個面就被相同的傳感器所覆蓋，因此必須高效地找到所有的面。

令為全部傳感器的監測區域的邊界交叉點的數目，則圖中的面數目最多為+2。

證明基于平面圖形的歐拉公式。因為=(,)是一個平面圖形，故||-||+||=2，其中、和分別是的頂點集、邊集和面集。如果幾個邊界線相交在同一點上，那么通過稍微改變邊界線，就可以增加面的數目。因此，為了計數起見，可以假定每個點可以是至多兩個監測區域的邊界線的交叉點，則圖的每個頂點有4 個度。如果把全部頂點的度加起來，則計算每個邊2 次，因此||=2||，這樣，||-2||+||=2，且面的數目等于||=||+2=+2。

如果監測區域是凸的，則任意兩個邊界可以最多相交2 次，也就是說，至多有(-1)個交叉點。

給定個傳感器，每個傳感器具有凸的監測區域，則圖的面數目至多為(-1)+2。

顯然，只要找到傳感器覆蓋區域的全部交叉點，就能在()的時間內高效地找到全部的面。

2 SNLP 的集中式求解

為了采用集中式算法求解SNLP，把SNLP 構建為一個包裝的線性規劃（linear programming，LP）。在找到滿足傳感器網絡約束的不同傳感器覆蓋后，通過為每個傳感器覆蓋分配時間來使傳感器網絡壽命最大化。從形式上，對于來自一組={,,…,c}的每個傳感器覆蓋c來說，就是需要找到時間變量t。構建矩陣C，其行=1,2,…,代表每個傳感器（為簡化起見，這里用來代替任意傳感器p），其列=1,2,…,代表每個覆蓋，于是有：

式中，b為傳感器的初始能量供給，如果傳感器不在覆蓋集中，則C=0，否則C=1。

2.1 SNLP 的Garg-Konemann 算法求解

上面的線性規劃其實是一個包裝的LP。一般來說，一個包裝的LP 定義為：

式中，、和有正的元素，把的維數表示為×大小。在本文情況下，的列數不能太大（一般與傳感器數量成指數關系），而且采用(1+)近似的Garg-Konemann（龍格-庫塔）算法，算法假設LP 通過一個向量∈R和一個尋找使其長度最小化的的列的算法隱含給出。在式（2）中，列關于LP 的長度對于任意正的向量定義為：

采用(1+)近似Garg-Konemann 算法求解最小長度列的實現偽代碼如算法1 所示。

(1+)近似Garg-Konemann 算法

輸入：向量∈R,＞0 和尋找包裝的LP max{|≤,≥0}的最小列長度A問題的(1+)近似Garg-Konemann算法。

1.初始化:=(1+)((1+)),對于=1,2,…,,()←/(),←,=0

2.While＜1

采用-近似GK 算法尋找列A,計算和具有最小()/A()的行的指標

當采用Garg-Konemann算法求解本文式（2）的LP時，即求解最小權值傳感器覆蓋問題，其中的權值與向量的元素成比例，即對于每個節點=1,2,…,來說，其權值()=1/y。這意味著：對于任意的＞0，網絡壽命問題可以采用算法1 的(1+) 近似的Garg-Konemann 算法在因子(1+)內近似。

2.2 部分傳感器覆蓋問題的求解

本節研究最小加權傳感器集部分覆蓋監測區域的問題。

部分-覆蓋問題：給定一個常數∈[0,1]，具有面積大小為的監測區域和一組傳感器，尋找傳感器子集,,…,p，以使：

式中，是總的監測區域，S是傳感器p的監測區域。

問題（4）可以重新表述如下：

集合-覆蓋問題：給定一個有限元素集合，每個元素有成本（每個元素的對應一個面的面積）：→R且的系列子集S?，每個子集有權值：S→R且∈[0,1]，尋找的最小權值子系列覆蓋子集?，使得被中的集合覆蓋的元素的總成本至少為?()，這里：

2.3 考慮通信成本的SNLP 求解

假設傳感器節點的通信范圍至少是其感知范圍的2 倍，節點可以處于4 種狀態：感知、轉發、連接到中心站和空閑狀態。每種狀態每個時間單位有不同的能量消耗，分別為、、和0。在實際中，≤≤，因為感知節點必須轉發它們自己的數據，并使用最多的能量連接到中心站。

一個三元組=(,,)表示由連接到中心站的節點集、中繼節點集和感知節點集構成。如果子集是一個覆蓋集（也可以是部分覆蓋集），則三元組就是可行的，而且中的每個節點要么是中的節點，要么在通信圖中通過?中的節點連接到中的節點。這時，SNLP 就成為下列具有多變量的包裝的線性規劃：

式中，t代表三元組使用的時間，=((),(),())，b是節點的初始能量供給。

式（6）實際上是一個加權連接覆蓋問題，可以重新表述如下：

也可以采用Garg-Konemann 算法得到這個加權連接覆蓋問題的一個近似解，這里采用一個常數近似算法來求解（對該算法稍微進行改變也可以用于當要求為完全覆蓋時的情形），算法求解具體過程如下：

3 SNLP 的分布式調度算法求解

傳感器網絡壽命還可以通過采用智能自組織的監測調度策略（即分布式調度算法）從本質上得到提高。對此，本文提出一種分布式算法來求解SNLP，算法具有以下優勢：（1）更高級的監測區域表示；（2）每個傳感器能量供給的動態考慮；（3）可以使活躍傳感器集最小化。

為此，進一步假設每個傳感器可以與共享面的全部傳感器通信。基于1.2 節的數據結構，構建分布式求解算法（自組織監測調度）原理如下：

（1）每個傳感器廣播自己的id 和地理位置給它的鄰居；

（2）每個傳感器確定出在它的監測區域內的全部的面，并與覆蓋該面的全部傳感器的id 的每個面相關聯。

采用這種分布式的自組織監測調度，需要解決兩個主要問題：（1）每個節點決定是打開還是關閉自己的規則是什么？（2）節點何時作出這樣的決定？

首先來描述每個節點的狀態和轉換規則。

在本文所提出的分布式自組織監測調度算法中，每個傳感器在任何時刻為以下3 種狀態之一：（1）活躍的，即傳感器監測其監控的區域；（2）空閑的，即傳感器監聽其他傳感器，但不監測它的區域；（3）中間脆弱狀態，即傳感器監測其區域，但應當盡快變換它的狀態到活躍的或空閑的狀態。每個傳感器都知道它的全部鄰居處在哪個狀態，即任何狀態轉換都必須立即廣播給鄰居，連同目前的能量供給。

每個節點的狀態轉換通過下面的規則來描述：

（1）當一個傳感器處于中間脆弱狀態時，則它應將其狀態改變為：

①如果存在一個不被任何其他活躍的或中間脆弱狀態的傳感器覆蓋的面，則將其狀態改變為活躍狀態；

②如果它的全部面被具有更大能量供給的活躍或中間脆弱狀態的兩類傳感器中的一種所覆蓋，則將其狀態改變為空閑狀態。

（2）當一個傳感器處于活躍或空閑狀態時，如果任意相鄰傳感器變成中間脆弱狀態，那么它就應該進入到中間脆弱狀態。

一旦任何傳感器變成中間脆弱狀態，則中間脆弱狀態在整個網絡上傳播，最終每個傳感器都處于空閑的或活躍的狀態。

把上述過程稱為全局重組。每個全局重組需要2（為節點數）次廣播，而且得到的全部活躍傳感器集構成一個最小的傳感器覆蓋。

現在來描述全部節點的狀態和轉換規則，并決定應當何時發生全局重組。顯然，幾乎完全耗盡能量供給應該是觸發事件之一，更準確的調度也需要更頻繁的重組，但這又意味著通信成本的增加。本文提出當一個傳感器的初始能量供給下降到預先確定的某個閾值時，就啟動一個重組，重組觸發閾值越小，則執行重組越頻繁，將導致更平衡的調度；如果傳感器節點間的通信比感知需要更多的能量，則選擇局部重組，即把中間脆弱狀態的傳播限制到觸發重組的傳感器的某個鄰域。算法2 為分布式調度算法實現的偽代碼。

分布式調度算法

為了將本文的分布式調度算法與文獻[6]的自組織監測調度算法進行比較，還需要在相同情形下進行，即實現無需任何重組的分布式自組織監測調度算法。為此，在實現算法時，一旦傳感器節點變成活躍狀態，就讓它一直活躍，直到耗盡它的全部能量供給。當一個傳感器節點幾乎完全耗盡其全部能量供給時，就讓它向鄰居廣播。這時，使得空閑傳感器的一個最小子集變得活躍起來，以覆蓋即將被耗盡能量的傳感器所拋棄的面。把這個稍作改進的分布式自組織監測調度算法稱為一直活躍分布式調度算法。

4 SNLP 及其求解算法的仿真研究

對本文提出的求解SNLP 的全部算法采用C++實現，并使用GPP-O2 優化編譯，在Sun 工作站Ultra-60 上運行，仿真實驗在隨機生成的測試用例上進行。

仿真實驗中取傳感器面積為1 000 m×1 000 m，監測面積為800 m×800 m；實驗中的傳感器節點數分別采用100、200、300、400、500 和1 000 個，每個傳感器節點的感知范圍為100～150 m，傳感器節點的位置隨機分布在傳感器區域內；覆蓋面積分別取100%(=1)和90%(=0.9)；對每個傳感器節點采用統一分配初始能量供給10（歸一化單位時間，下同）和在10～20 之間隨機分配；取=0.1，以確保近似Garg-Konemann解的質量；作為比較，仿真實驗中給出了近似Garg-Konemann 算法、整數線性規劃求解程序CPLEX 算法、分布式調度算法、一直活躍分布式調度算法和文獻[6]的自組織監測調度算法的網絡壽命比較。

在得到近似Garg-Konemann 算法的傳感器覆蓋后，就可以通過CPLEX 為每個傳感器覆蓋分配最佳時間來找到最優調度，約束條件是滿足傳感器節點的電池需求和使總壽命最大化。

還給出了采用不同重組觸發閾值時的分布式算法的通信開銷和網絡壽命之間的關系。

表1 所示為對于不同感知范圍和不同傳感器節點數時的面數和近似Garg-Konemann 算法、CPLEX解以及分布式調度算法尋找相同面數時的運行時間。從表1 可見，面的數目隨節點數量和/或感知范圍的增大而增大，而且找到同樣的面數分布式調度算法的運行時間要小于兩種集中式算法即近似Garg-Konemann 算法和CPLEX 的運行時間。

表1 不同算法找到相同面數的運行時間Table 1 Running time of finding same number of faces for different algorithms

圖3 所示為CPLEX 算法、近似Garg-Konemann 算法、分布式調度算法、一直活躍分布式調度算法和文獻[6]的自組織監測調度算法分別在感知范圍為100 m，初始能量供給為10 和=1.0 時，感知范圍為150 m，初始能量供給在10～20和=1.0時和感知范圍為100 m，初始能量供給為10 和=0.9 時對于不同傳感器節點數時的網絡壽命。從圖3 可見，CPLEX 解算法是最優的，因為CPLEX 解是在得到近似Garg-Konemann算法的傳感器覆蓋后，為每個傳感器覆蓋分配最佳時間來找到最優調度。當必須覆蓋整個監測區域(=1.0)時，從圖3（a）和（b）可見，分布式調度算法非常接近集中式的近似Garg-Konemann 算法，但當約束條件為僅覆蓋監測區域的90%(=0.9)時，從圖3（c）可見，兩種分布式調度算法明顯比集中算法要差，但本文提出的分布式調度算法總是優于文獻[6]的自組織監測調度算法。

圖3 不同算法的網絡壽命比較Fig.3 Comparison of network life of different algorithms

表2 所示為對于不同重組觸發閾值，分布式調度算法在網絡壽命時間和通信開銷之間的關系。實驗中的感知范圍為100 m，初始能量供給在10～20 隨機分配。從表2 可見，增大重組觸發閾值會降低通信開銷，但同時也降低了網絡壽命。

表2 分布式算法的網絡壽命和通信開銷之間的關系Table 2 Relationship between network life and communication overhead for distributed algorithms

5 結束語

本文構建了一種最大傳感器網絡壽命問題的傳感器網絡覆蓋模型及其數據結構，并提出了幾種集中式和分布式算法來求解這個問題；還研究了監測區域需要部分覆蓋時和考慮通信成本時的情形；最后通過仿真實驗檢驗了本文提出的基于傳感器網絡覆蓋模型和數據結構的SNLP 及其求解算法，能夠獲得較好的運行時間、網絡壽命和網絡開銷。