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

于廣州

?

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

于廣州

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

多類別目標(biāo)覆蓋問題是目前無線傳感器網(wǎng)絡(luò)中的研究熱點(diǎn)。針對(duì)現(xiàn)有目標(biāo)覆蓋算法在時(shí)間效率、網(wǎng)絡(luò)生命周期等方面的不足，將多類別目標(biāo)覆蓋問題建模為基于線性規(guī)劃的網(wǎng)絡(luò)生命周期最大化問題，提出一種基于分簇的目標(biāo)覆蓋算法。該算法依據(jù)節(jié)點(diǎn)的剩余能量和感應(yīng)能力，在每個(gè)簇結(jié)構(gòu)內(nèi)求解最優(yōu)覆蓋集的基礎(chǔ)上得到接近于最優(yōu)解的全局覆蓋集，進(jìn)而調(diào)度節(jié)點(diǎn)相應(yīng)的感應(yīng)模塊去覆蓋其感知范圍內(nèi)同屬性的目標(biāo)。實(shí)驗(yàn)結(jié)果表明，該算法是有效的，在網(wǎng)絡(luò)生命周期和時(shí)間效率等方面均優(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ù)、嵌入式計(jì)算技術(shù)和分布式信息處理技術(shù)，是目前國際上前沿?zé)狳c(diǎn)的研究領(lǐng)域。其中，傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋問題[1]是指保證目標(biāo)覆蓋質(zhì)量的條件下，如何調(diào)度傳感器節(jié)點(diǎn)的狀態(tài)，減少節(jié)點(diǎn)的能量消耗，最大化網(wǎng)絡(luò)生存周期。在大規(guī)模無線傳感器網(wǎng)絡(luò)中，需要被覆蓋的目標(biāo)經(jīng)常是多樣化、多類別的，如何有效地對(duì)這些目標(biāo)進(jìn)行覆蓋控制，并通過空間資源的優(yōu)化分配來滿足用戶的感知需求，將直接反映無線傳感器網(wǎng)絡(luò)對(duì)外界環(huán)境的感知服務(wù)質(zhì)量。因此，本文主要針對(duì)無線異構(gòu)傳感器網(wǎng)絡(luò)中多類型目標(biāo)覆蓋問題[2-3]進(jìn)行研究，尋求以最少的傳感器節(jié)點(diǎn)數(shù)及最佳的節(jié)點(diǎn)部署位置，實(shí)現(xiàn)目標(biāo)的監(jiān)測(cè)和數(shù)據(jù)傳輸，優(yōu)化網(wǎng)絡(luò)成本。

2 相關(guān)工作

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

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

3 問題建模

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

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

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

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

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

(1)傳感器節(jié)點(diǎn)安裝有多個(gè)感知單元模塊，這些模塊能夠分別監(jiān)測(cè)不同類型的目標(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é)點(diǎn)之間的能量消耗，本文采用時(shí)間離散化思想將網(wǎng)絡(luò)運(yùn)行時(shí)間劃分成若干個(gè)長(zhǎng)短相等的間隔，每一個(gè)時(shí)間時(shí)隔稱為了一個(gè)時(shí)間“輪”。每一個(gè)時(shí)間由初始階段和感知階段組成；在初始階段由簇頭節(jié)點(diǎn)隨機(jī)決定其成員節(jié)點(diǎn)的初始狀態(tài)，假如節(jié)點(diǎn)滿足覆蓋要求則進(jìn)入工作狀態(tài)進(jìn)行監(jiān)測(cè)目標(biāo)。網(wǎng)絡(luò)運(yùn)行的時(shí)間線結(jié)構(gòu)如圖2所示。

圖2 網(wǎng)絡(luò)運(yùn)行時(shí)間劃分

3.2 問題描述

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

(2)值最大化；

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

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

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

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

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

圖3 覆蓋示例

在這個(gè)示例中，節(jié)點(diǎn)與監(jiān)測(cè)目標(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示例對(duì)應(yīng)的覆蓋映射關(guān)系

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

4.1 算法基本思路

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

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

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

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

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

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

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

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

通過以上步驟的執(zhí)行，可以實(shí)現(xiàn)對(duì)網(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)的時(shí)間復(fù)雜度完成構(gòu)造覆蓋集對(duì)目標(biāo)覆蓋，其中，為感知區(qū)域中節(jié)點(diǎn)數(shù)量。

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖9 不同方案的時(shí)間效率比較

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

6 結(jié)束語

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

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

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

[7] 向 輝, 彭 力, 聞繼偉. 高效節(jié)能的視覺傳感器網(wǎng)絡(luò)目標(biāo)覆蓋算法[J]. 計(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é)點(diǎn)集的求解算法[J]. 東北大學(xué)學(xué)報(bào): 自然科學(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－)，男，實(shí)驗(yàn)師、碩士，主研方向：無線傳感器網(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