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

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

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

2.物聯(lián)網感知與大數(shù)據(jù)分析南充市重點實驗室，四川 南充637009

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

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

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

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

1 傳感器網絡覆蓋模型及其數(shù)據(jù)結構

1.1 傳感器網絡的建模

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

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

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

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

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

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

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

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

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

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

1.2 傳感器覆蓋的數(shù)據(jù)結構

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

圖2 具有圓盤形監(jiān)測區(qū)域的4 個傳感器的數(shù)據(jù)結構Fig.2 Data structure for 4 sensors with disc monitored regions

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

令為全部傳感器的監(jiān)測區(qū)域的邊界交叉點的數(shù)目，則圖中的面數(shù)目最多為+2。

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

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

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

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

2 SNLP 的集中式求解

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

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

2.1 SNLP 的Garg-Konemann 算法求解

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

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

采用(1+)近似Garg-Konemann 算法求解最小長度列的實現(xiàn)偽代碼如算法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時，即求解最小權值傳感器覆蓋問題，其中的權值與向量的元素成比例，即對于每個節(jié)點=1,2,…,來說，其權值()=1/y。這意味著：對于任意的＞0，網絡壽命問題可以采用算法1 的(1+) 近似的Garg-Konemann 算法在因子(1+)內近似。

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

本節(jié)研究最小加權傳感器集部分覆蓋監(jiān)測區(qū)域的問題。

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

式中，是總的監(jiān)測區(qū)域，S是傳感器p的監(jiān)測區(qū)域。

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

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

2.3 考慮通信成本的SNLP 求解

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

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

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

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

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

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

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

為此，進一步假設每個傳感器可以與共享面的全部傳感器通信?；?.2 節(jié)的數(shù)據(jù)結構，構建分布式求解算法（自組織監(jiān)測調度）原理如下：

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

（2）每個傳感器確定出在它的監(jiān)測區(qū)域內的全部的面，并與覆蓋該面的全部傳感器的id 的每個面相關聯(lián)。

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

首先來描述每個節(jié)點的狀態(tài)和轉換規(guī)則。

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

每個節(jié)點的狀態(tài)轉換通過下面的規(guī)則來描述：

（1）當一個傳感器處于中間脆弱狀態(tài)時，則它應將其狀態(tài)改變?yōu)椋?/p>

①如果存在一個不被任何其他活躍的或中間脆弱狀態(tài)的傳感器覆蓋的面，則將其狀態(tài)改變?yōu)榛钴S狀態(tài)；

②如果它的全部面被具有更大能量供給的活躍或中間脆弱狀態(tài)的兩類傳感器中的一種所覆蓋，則將其狀態(tài)改變?yōu)榭臻e狀態(tài)。

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

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

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

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

分布式調度算法

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

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

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

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

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

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

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

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

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

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

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

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

5 結束語

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