于廣州

?

WSN中基于線性規(guī)劃的多類別目標(biāo)覆蓋算法

于廣州

(廣東海洋大學(xué)網(wǎng)絡(luò)與教育技術(shù)中心，廣東 湛江 524025)

多類別目標(biāo)覆蓋問題是目前無線傳感器網(wǎng)絡(luò)中的研究熱點。針對現(xiàn)有目標(biāo)覆蓋算法在時間效率、網(wǎng)絡(luò)生命周期等方面的不足，將多類別目標(biāo)覆蓋問題建模為基于線性規(guī)劃的網(wǎng)絡(luò)生命周期最大化問題，提出一種基于分簇的目標(biāo)覆蓋算法。該算法依據(jù)節(jié)點的剩余能量和感應(yīng)能力，在每個簇結(jié)構(gòu)內(nèi)求解最優(yōu)覆蓋集的基礎(chǔ)上得到接近于最優(yōu)解的全局覆蓋集，進(jìn)而調(diào)度節(jié)點相應(yīng)的感應(yīng)模塊去覆蓋其感知范圍內(nèi)同屬性的目標(biāo)。實驗結(jié)果表明，該算法是有效的，在網(wǎng)絡(luò)生命周期和時間效率等方面均優(yōu)于CWGC方案，接近于線性規(guī)劃最優(yōu)值。

無線傳感器網(wǎng)絡(luò)；目標(biāo)覆蓋；線性規(guī)劃；分簇；最優(yōu)解；網(wǎng)絡(luò)生命周期

1 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)綜合了無線通信技術(shù)、傳感器技術(shù)、嵌入式計算技術(shù)和分布式信息處理技術(shù)，是目前國際上前沿?zé)狳c的研究領(lǐng)域。其中，傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋問題[1]是指保證目標(biāo)覆蓋質(zhì)量的條件下，如何調(diào)度傳感器節(jié)點的狀態(tài)，減少節(jié)點的能量消耗，最大化網(wǎng)絡(luò)生存周期。在大規(guī)模無線傳感器網(wǎng)絡(luò)中，需要被覆蓋的目標(biāo)經(jīng)常是多樣化、多類別的，如何有效地對這些目標(biāo)進(jìn)行覆蓋控制，并通過空間資源的優(yōu)化分配來滿足用戶的感知需求，將直接反映無線傳感器網(wǎng)絡(luò)對外界環(huán)境的感知服務(wù)質(zhì)量。因此，本文主要針對無線異構(gòu)傳感器網(wǎng)絡(luò)中多類型目標(biāo)覆蓋問題[2-3]進(jìn)行研究，尋求以最少的傳感器節(jié)點數(shù)及最佳的節(jié)點部署位置，實現(xiàn)目標(biāo)的監(jiān)測和數(shù)據(jù)傳輸，優(yōu)化網(wǎng)絡(luò)成本。

2 相關(guān)工作

目標(biāo)覆蓋問題一直是WSN中的一大研究熱點。相繼有眾多的學(xué)者提出了一系列方法用于無線傳感網(wǎng)中目標(biāo)覆蓋的方法，如文獻(xiàn)[4]分析了目標(biāo)覆蓋中的連通性問題,首次提出針對目標(biāo)全覆蓋與維護(hù)節(jié)點集連通性關(guān)系的連通臨界條件。并針對連通性條件無法滿足的情況，提出了一個維護(hù)連通性的優(yōu)化部署方案。最后的實驗表明，該方案既能實現(xiàn)對目標(biāo)集的全覆蓋，又維護(hù)了連通性；文獻(xiàn)[5]提出一種能量有效的優(yōu)化覆蓋算法。該算法將目標(biāo)覆蓋區(qū)域節(jié)點能量構(gòu)建成正態(tài)分布的網(wǎng)絡(luò)模型，通過采集和檢索數(shù)據(jù)選擇最優(yōu)子集以及對節(jié)點狀態(tài)調(diào)度機(jī)制動態(tài)轉(zhuǎn)換，可以有效地降低網(wǎng)絡(luò)能耗，在提高節(jié)點覆蓋性能的同時優(yōu)化了節(jié)點的數(shù)量。該算法能夠以較小的代價延長整個網(wǎng)絡(luò)的生存周期，具有更好的適應(yīng)性和穩(wěn)定性；文獻(xiàn)[6]針對有向傳感器網(wǎng)絡(luò)的全目標(biāo)覆蓋問題，提出一種基于免疫算法的有向傳感器網(wǎng)絡(luò)目標(biāo)覆蓋方案。該方案采用免疫算法尋找最少數(shù)量的傳感器，覆蓋某一區(qū)域內(nèi)全部的目標(biāo)點；文獻(xiàn)[7]針對視覺傳感器網(wǎng)絡(luò)目標(biāo)覆蓋過程中因覆蓋冗余、節(jié)點剩余能量不均等原因?qū)е戮W(wǎng)絡(luò)壽命過短的問題，設(shè)計一種視覺傳感器網(wǎng)絡(luò)目標(biāo)覆蓋算法。該算法基于節(jié)點與目標(biāo)的覆蓋關(guān)聯(lián)關(guān)系，利用關(guān)系矩陣及相關(guān)運算對覆蓋頻繁目標(biāo)集進(jìn)行挖掘，進(jìn)而對工作節(jié)點進(jìn)行動態(tài)選舉，以此延長網(wǎng)絡(luò)的生存時間。該算法在保證網(wǎng)絡(luò)覆蓋質(zhì)量的前提下能夠高效地調(diào)度工作節(jié)點，均衡節(jié)點耗能，有效延長網(wǎng)絡(luò)壽命。

此外，文獻(xiàn)[8]通過使用最少數(shù)量的傳感器節(jié)點，設(shè)計了一個臨界正方形網(wǎng)絡(luò)覆蓋算法以覆蓋關(guān)鍵網(wǎng)格。算法是基于節(jié)點加權(quán)的Stenier樹而選擇網(wǎng)格點集合，在選擇的網(wǎng)絡(luò)點上部署節(jié)點而形成一個連通的無線網(wǎng)絡(luò)，從而達(dá)到覆蓋全部的關(guān)鍵網(wǎng)格；文獻(xiàn)[9]針對普通傳感器節(jié)點與網(wǎng)關(guān)節(jié)點之間的多跳覆蓋和連通問題，設(shè)計了一個基于整數(shù)線性規(guī)劃的優(yōu)化方法，它用于最小化節(jié)點部署代價和能量消耗。同時該文也提出了一個適合于大規(guī)模部署的異構(gòu)傳感器網(wǎng)絡(luò)環(huán)境的啟發(fā)式算法；文獻(xiàn)[10]針對最大化網(wǎng)絡(luò)覆蓋時間問題，提出了一個隨機(jī)部署節(jié)點環(huán)境下網(wǎng)絡(luò)覆蓋時間最優(yōu)化算法，該算法利用線性規(guī)劃方法[11]最優(yōu)化計算網(wǎng)絡(luò)節(jié)點分簇和節(jié)點之間的路由構(gòu)建，在線性時間內(nèi)解決了最大化網(wǎng)絡(luò)覆蓋時間問題。本文在現(xiàn)有工作的基礎(chǔ)上，提出一種改進(jìn)的目標(biāo)覆蓋算法，并通過仿真實驗驗證該方法的有效性。

3 問題建模

3.1 網(wǎng)絡(luò)模型

為了方便描述，首先給出如下的定義：

定義1(目標(biāo)覆蓋)任務(wù)區(qū)域的目標(biāo)至少被一個活躍節(jié)點所感知，則稱目標(biāo)被覆蓋。

定義2(網(wǎng)絡(luò)生存周期)從網(wǎng)絡(luò)正常工作運行開始，直到存在某一個監(jiān)測目標(biāo)不能被任何部署的節(jié)點所監(jiān)測覆蓋，這個時間段稱為網(wǎng)絡(luò)生存周期。

本文針對異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋問題展開研究，并基于如下的假設(shè)：

(1)傳感器節(jié)點安裝有多個感知單元模塊，這些模塊能夠分別監(jiān)測不同類型的目標(biāo)信息。部署后的網(wǎng)絡(luò)采用分簇結(jié)構(gòu)的管理模式，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 分簇結(jié)構(gòu)的網(wǎng)絡(luò)拓?fù)?/p>

(3)為平衡節(jié)點之間的能量消耗，本文采用時間離散化思想將網(wǎng)絡(luò)運行時間劃分成若干個長短相等的間隔，每一個時間時隔稱為了一個時間“輪”。每一個時間由初始階段和感知階段組成；在初始階段由簇頭節(jié)點隨機(jī)決定其成員節(jié)點的初始狀態(tài)，假如節(jié)點滿足覆蓋要求則進(jìn)入工作狀態(tài)進(jìn)行監(jiān)測目標(biāo)。網(wǎng)絡(luò)運行的時間線結(jié)構(gòu)如圖2所示。

圖2 網(wǎng)絡(luò)運行時間劃分

3.2 問題描述

(1)全部目標(biāo)能夠被每個覆蓋集所覆蓋；

(2)值最大化；

(3)覆蓋集中的每個節(jié)點所消耗的能量不能大于其初始能量。

依據(jù)上述定義，MTTC問題可被建模為：

式(4)中各個變量含義如表1所示。

表1 MTTC問題參數(shù)描述

為描述節(jié)點與目標(biāo)之間的覆蓋關(guān)系，本文給出一個示例(包含4個節(jié)點和7個目標(biāo))，如圖3所示。圖中每個節(jié)點安裝了2~3個不同功能的感知單元(模塊)，每個模塊能夠感知一種類型的目標(biāo)。

圖3 覆蓋示例

在這個示例中，節(jié)點與監(jiān)測目標(biāo)之間的覆蓋映射關(guān)系為：1＝{1,5}，2＝{1,4,6}，3＝{2,3,6}，4＝{1,2,3,5,7}，圖4表示了圖3所示例子的覆蓋映射關(guān)系。

圖4 圖3示例對應(yīng)的覆蓋映射關(guān)系

4 目標(biāo)覆蓋算法

4.1 算法基本思路

由于節(jié)點最優(yōu)覆蓋集求解是一個NP難問題[12]，不能直接求解MTTC問題。因此，本文給出一個基于分簇結(jié)構(gòu)的目標(biāo)覆蓋求解算法，將尋找全局最優(yōu)覆蓋解轉(zhuǎn)化為尋找簇內(nèi)最優(yōu)覆蓋解，從而使全局解接近最優(yōu)解，降低了解決問題的難度，其基本思想如下：

(2)簇頭節(jié)點的剩余能量和節(jié)點的感知能力的大小將其成員節(jié)點在其鏈表中位置由高到低排序，排在前面的成員節(jié)點具有更高的優(yōu)先覆蓋權(quán)。簇頭節(jié)點則根據(jù)監(jiān)測目標(biāo)是否被節(jié)點覆蓋由前到后查找其存儲的鏈表，并將符合條件的成員節(jié)點標(biāo)記。

4.2 算法實現(xiàn)步驟

為了描述方便，先給出算法中所使用的變量的說明，如表2所示。

表2 本文算法中的變量描述

算法的主要實現(xiàn)步驟如下：

(4)簇頭節(jié)點在完成步驟(3)的工作之后，簇頭節(jié)點根據(jù)監(jiān)測目標(biāo)是否被節(jié)點覆蓋由前到后查找其存儲的鏈表，并將符合條件的成員節(jié)點標(biāo)記。它包含3個子步驟：

3)當(dāng)鏈表被遍歷完成后，簇頭節(jié)點會調(diào)度最佳的成員節(jié)點覆蓋其監(jiān)測范圍內(nèi)的目標(biāo)。否則，轉(zhuǎn)到本步驟的第一個子步驟，以完成全部的覆蓋集節(jié)點選擇。

通過以上步驟的執(zhí)行，可以實現(xiàn)對網(wǎng)絡(luò)中所有的目標(biāo)的最優(yōu)覆蓋，覆蓋算法描述如下：

算法最優(yōu)覆蓋集構(gòu)造算法

j++;

} }

Step5While ( j< i){

Step6 While (k

If (CL[k].data包含在CL[j].data內(nèi)){

將重復(fù)覆蓋信息CL[k].data從CL中刪除;

}

j++;}

j++;}}

4.3 算法性能分析

定理1本文算法在最壞情況下以(n)的時間復(fù)雜度完成構(gòu)造覆蓋集對目標(biāo)覆蓋，其中，為感知區(qū)域中節(jié)點數(shù)量。

以下采用圖5所給出的覆蓋場景為例，通過節(jié)點的剩余能量變化更直觀地反映網(wǎng)絡(luò)利用最優(yōu)覆蓋集構(gòu)造算法構(gòu)造最優(yōu)覆蓋集的過程。在這個例子中，節(jié)點安裝有多個感知單元模塊，分別表示為u、u和u；在一個時間“輪”內(nèi)，這3種模塊工作時的能量消耗分別為3、4和5；節(jié)點的初始能量為50。此時，4個節(jié)點的感應(yīng)能力分別為：

在僅考慮節(jié)點感應(yīng)能量消耗的情況下，利用算法1，在每一輪中所構(gòu)造的覆蓋集如圖5所示。節(jié)點在每一輪中所消耗的能量和剩余能量變化如表3所示。從表3中可以看出該網(wǎng)絡(luò)能夠運行5個時間“輪”長的生命期。

圖5 利用最優(yōu)覆蓋集構(gòu)造算法形成的5個覆蓋集

表3 圖2示例中節(jié)點剩余能量變化(節(jié)點初始能量為50)

5 實驗結(jié)果與分析

為測試本文方案的性能，以Matlab2012為工具進(jìn)行了仿真實驗，實驗環(huán)境參數(shù)設(shè)置如表4所示。

表4 實驗環(huán)境中的參數(shù)設(shè)置

本文分別從傳感器節(jié)點個數(shù)變化、目標(biāo)個數(shù)變化以及節(jié)點所擁有的感知單元類型數(shù)量變化等3種情況分析目標(biāo)覆蓋算法的性能，通過實驗對比本文算法與線性規(guī)劃理論值(LP)、CWGC算法[1]在網(wǎng)絡(luò)生存期和算法執(zhí)行時間方面的性能。實驗結(jié)果為50次獨立實驗結(jié)果的均值。

(1)不同節(jié)點個數(shù)下網(wǎng)絡(luò)生命周期比較

該組實驗中部署了20個待監(jiān)測目標(biāo)，3種方案都采用表4所示的實驗參數(shù)，實驗結(jié)果如圖6所示。

圖6 不同節(jié)點數(shù)目下的網(wǎng)絡(luò)生命周期比較

可以看到，隨著節(jié)點數(shù)量的增加，網(wǎng)絡(luò)生命周期也呈線性增加，這是由于網(wǎng)絡(luò)有更多的節(jié)點用于輪流調(diào)度去覆蓋目標(biāo)，從而延長了節(jié)點的壽命。其中，LP方案是最優(yōu)的，這是因為LP方案是一個利用全局網(wǎng)絡(luò)信息的集中式方案，而本文方案的生命周期接近于LP，相比于CWGC，本文方案的生命周期延長了8%。這主要是因為，本文方案通過使用節(jié)點覆蓋能力的高低作為調(diào)度的依據(jù)，并依據(jù)簇頭節(jié)點的剩余能量和節(jié)點感知能力的大小來對目標(biāo)覆蓋指定優(yōu)先級，降低了同時處于活躍狀態(tài)節(jié)點的數(shù)量，延長了網(wǎng)絡(luò)生命周期。

(2)不同目標(biāo)個數(shù)下網(wǎng)絡(luò)生命周期比較

該組實驗中部署了120個傳感器節(jié)點，3種方案都采用表4所示的實驗參數(shù)，實驗結(jié)果如圖7所示。

圖7 不同目標(biāo)個數(shù)下的網(wǎng)絡(luò)生命周期比較

可以看到，隨著待監(jiān)測目標(biāo)數(shù)量的增加，網(wǎng)絡(luò)生命周期也呈下降的趨勢。對比3種方案可知，本文方案的性能要明顯好于CWGC算法，而與最優(yōu)的LP方案差別不大。

(3)不同感知單元屬性數(shù)量下的網(wǎng)絡(luò)生命周期比較

該組實驗考察了不同節(jié)點感知模塊數(shù)量對網(wǎng)絡(luò)生命周期的影響，實驗中節(jié)點數(shù)量為120個，待監(jiān)測目標(biāo)數(shù)量為20個，實驗結(jié)果如圖8所示。

圖8 不同感知單元個數(shù)下的網(wǎng)絡(luò)生命周期比較

可以看到，隨著節(jié)點的感知單元模塊數(shù)量的增加，3種方案下網(wǎng)絡(luò)的生命周期生存期不斷遞減，這主要是由于增加的感知消耗更多的能量。與前述2個實驗結(jié)果類似，本文方案的性能介于CWGC算法和LP方案之間，與最優(yōu)的LP方案差別不大。

(4)算法的執(zhí)行時間對比

設(shè)置傳感器節(jié)點數(shù)量為120個，感知單元為4個，對不同目標(biāo)個數(shù)下的覆蓋算法執(zhí)行時間效率進(jìn)行了對比，實驗結(jié)果如圖9所示。

圖9 不同方案的時間效率比較

可以看到，隨著待監(jiān)測目標(biāo)數(shù)量的增加，3種方案的執(zhí)行時間都呈上升的趨勢。其中，LP的時間效率最低，這主要是因為，LP需要利用網(wǎng)絡(luò)的全局信息來實現(xiàn)，需要進(jìn)行大量的信息傳遞，因此其執(zhí)行時間最長；而CWGC采用貪婪法來尋找最優(yōu)的覆蓋集合，算法的迭代次數(shù)隨著目標(biāo)個數(shù)的增加而增加，當(dāng)網(wǎng)絡(luò)中目標(biāo)個數(shù)較多或目標(biāo)分布不均勻時，CWGC的收斂性較差，執(zhí)行時間較長；而本文方案采用分簇技術(shù)降低了問題求解的難度，并基于整數(shù)規(guī)劃的思想，只依據(jù)成員節(jié)點的感應(yīng)能力和剩余能量大小來進(jìn)行最優(yōu)覆蓋，因此，在一個時間輪中的執(zhí)行時間是最短的，提高了算法的效率。

6 結(jié)束語

本文主要研究的內(nèi)容是異構(gòu)傳感器網(wǎng)絡(luò)的多類型目標(biāo)覆蓋算法。針對本文所提出的MTTC問題，采用分簇結(jié)構(gòu)和線性規(guī)劃相結(jié)合來求解。針對MTTC問題在全局求解方面存在的困難，提出了一種基于分簇結(jié)構(gòu)的目標(biāo)覆蓋算法；該算法依據(jù)節(jié)點的剩余能量和感應(yīng)能力，在每個簇結(jié)構(gòu)內(nèi)得到接近于最優(yōu)解的全局覆蓋集，并能覆蓋其感知范圍內(nèi)同屬性的目標(biāo)。最后通過實驗方法比較了在不同評價標(biāo)準(zhǔn)條件下所提本文算法的性能。算法能夠有效提高網(wǎng)絡(luò)節(jié)點的能量利用效率，從而延長了網(wǎng)絡(luò)生命周期。下一步研究工作的重點主要是利用壓縮感知理論，研究無線傳感網(wǎng)中的目標(biāo)覆蓋問題、連通性問題與可靠性問題。

[1] Zhao Qun, Gurusamy M. Lifetime Maximization for Connected Target Coverage in Wireless Sensor Networks[J]. IEEE/ACM Transactions on Networking, 2008, 16(6): 1378-1391.

[2] Liao Zhuofan, Zhang Shigeng, Cao Jiannong, et al. Minimizing Movement for Target Coverage in Mobile Sensor Networks[C]// Proc. of the 32nd International Conference on Distributed Computing Systems Workshops. Macau, China: [s. n.], 2012: 194-200.

[3] Kim C, Kim Y, Kang I, et al. A Scheduling Algorithm for Connected Target Coverage Under Probabilistic Coverage Model[C]//Proc. of 2012 International Conference on Information Networking. Bali, Indonesia: [s. n.], 2012: 86-91.

[4] 桂小林, 何 欣, 尹 柯. 基于目標(biāo)覆蓋的無線傳感器網(wǎng)絡(luò)的連通性優(yōu)化部署方法[J]. 小型微型計算機(jī)系統(tǒng), 2011, 32(9): 1821-1826.

[5] 孫澤宇, 丁國強(qiáng), 張永勝. 基于能量有效WSN優(yōu)化覆蓋算法的研究[J]. 計算機(jī)應(yīng)用研究, 2011, 28(6): 2261-2264.

[6] 畢曉君, 董 超, 王鵬宇. 基于免疫算法的有向傳感器網(wǎng)絡(luò)目標(biāo)覆蓋研究[J]. 計算機(jī)工程, 2011, 37(24): 83-85.

[7] 向 輝, 彭 力, 聞繼偉. 高效節(jié)能的視覺傳感器網(wǎng)絡(luò)目標(biāo)覆蓋算法[J]. 計算機(jī)工程, 2012, 38(16): 113-116.

[8] Ke W, Liu B, Tsai M. Efficient Algorithm for Constructing Minimum Size Wireless Sensor Networks to Fully Cover Critical Square Grids[J]. IEEE Transactions on Wireless Com- munications, 2011, 10(4): 1154-1164.

[9] Capone A, Cesana M, Donno D, et al. Deploying Multiple Interconnected Gateways in Heterogeneous Wireless Sensor Networks: An Optimization Approach[J]. Computer Com- munications, 2010, 33(10): 1151-1161.

[10] Shu T, Krunz M. Coverage-time Optimization for Clustered Wireless Sensor Networks: A Power-balancing Approach[J]. IEEE/ACM Transactions on Networks, 2010, 18(1): 202-215.

[11] Torshizi E S, Yousefi S, Bagherzadeh J, et al. Life Time Maximization for Connected Target Coverage in Wireless Sensor Networks with Sink Mobility[C]//Proc. of the 6th International Symposium on Telecommunications. Manchester, UK: [s. n.], 2012: 743-748.

[12] 賈 杰, 陳 劍, 常桂然, 等. 無線傳感器網(wǎng)絡(luò)中最優(yōu)覆蓋節(jié)點集的求解算法[J]. 東北大學(xué)學(xué)報: 自然科學(xué)版, 2007, 28(11): 1560-1563.

編輯 金胡考

Multi-class Target Coverage Algorithm Based on Linear Programming in Wireless Sensor Networks

YU Guang-zhou

(Network and Educational Technology Center, Guangdong Ocean University, Zhanjiang 524025, China)

The multi-class target coverage problem is currently research hot in Wireless Sensor Networks(WSN). Aiming at the disadvantage of the existing target coverage algorithms, the multi-class target coverage problem is modeled as a maximization lifetime problem based on the Linear Programming(LP). This paper proposes a target coverage algorithm based on the clustering. According to the residual energy and sensing capability of nodes, the global coverage set is obtained on the basis of solving optimal solution within the each cluster structure, which is close to the optimal solution, moreover, the algorithm dispatches the corresponding sensing module to cover the target of having the same attributes within its sensing range. Experimental results show that the performance of this algorithm is superior to the CWGC algorithms in terms of the lifetime of network and time efficiency, close to the optimal value of LP.

Wireless Sensor Networks(WSN); target coverage; Linear Programming(LP); clustering; optimal solution; lifetime of network

1000-3428(2014)03-0152-06

A

TP393

于廣州(1981－)，男，實驗師、碩士，主研方向：無線傳感器網(wǎng)絡(luò)，神經(jīng)網(wǎng)絡(luò)。

2012-12-20

2013-04-08 E-mail：1552327495@qq.com

10.3969/j.issn.1000-3428.2014.03.031