無線傳感網(wǎng)絡(luò)中基于DSC的記憶式算法研究*

顏 源,宰文姣

(1.湛江師范學(xué)院基礎(chǔ)教育學(xué)院,廣東 湛江 524048;2.四川師范大學(xué)工學(xué)院,成都 610101)

?

無線傳感網(wǎng)絡(luò)中基于DSC的記憶式算法研究*

顏 源1*,宰文姣2

(1.湛江師范學(xué)院基礎(chǔ)教育學(xué)院,廣東 湛江 524048;2.四川師范大學(xué)工學(xué)院,成都 610101)

網(wǎng)絡(luò)壽命是影響無線傳感網(wǎng)絡(luò)WSN(Wireless Sensor Network)應(yīng)用最關(guān)鍵因素之一,受到廣泛關(guān)注。將所有傳感節(jié)點劃分為不相交的傳感節(jié)點覆蓋(Sensor covers)子集,致使每個cover能夠覆蓋所有目標(biāo)節(jié)點,并且所有cover輪流工作,這是延長網(wǎng)絡(luò)壽命的有效方案。因此,可通過最大化cover數(shù)提高網(wǎng)絡(luò)壽命,即求解不相交覆蓋集DSC(Disjoint Set Cover)問題。為此,提出基于IMA(Improved Memetic Algorithm)算法求解DSC問題。IMA算法先建立初始矩陣Initial Population,再經(jīng)優(yōu)化Optimizer階段、改進(jìn)Improver階段,形成最大化covers。仿真結(jié)果表明,與其他啟發(fā)式算法和進(jìn)化算法相比,提出的IMA算法能夠形成最大化的covers。

無線傳感網(wǎng)絡(luò);網(wǎng)絡(luò)壽命;不相交覆蓋集;記憶式算法;上限逼近值

由傳感節(jié)點組建的無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)被廣泛應(yīng)用,如棲息地監(jiān)控、環(huán)境監(jiān)控[2-3]以及監(jiān)視系統(tǒng)等[4]。實際上,傳感節(jié)點是一個微型設(shè)備,有4個基礎(chǔ)模塊組成:從物理環(huán)境收集數(shù)據(jù)的感測模塊、數(shù)據(jù)處理的處理模塊、數(shù)據(jù)存儲的記憶模塊以及數(shù)據(jù)傳輸?shù)臒o線通信模塊。此外,傳感節(jié)點利用電池作為能量進(jìn)行工作,但是,電池屬于有限能量,并且在WSNs中不能給傳感節(jié)點切換電池(當(dāng)電池耗盡時)。在這種情況下,傳感節(jié)點只能利用有限的能量(電池)進(jìn)行長期的監(jiān)測目標(biāo)的任務(wù)。因此,對于所有傳感節(jié)點而言,優(yōu)化能量效率是至關(guān)重要[5]。WSN實施過程中,能量利用效率被認(rèn)為是一個重要問題。

合理調(diào)度傳感節(jié)點工作是一個有效的節(jié)省能量的策略。傳感節(jié)點在工作和休眠模式進(jìn)行合理的切換,致使傳感節(jié)點以最小能量消耗能夠覆蓋(cover)所有目標(biāo)節(jié)點。覆蓋指的是網(wǎng)絡(luò)目標(biāo)至少能被一個傳感節(jié)點監(jiān)控,即每個目標(biāo)至少在一個傳感節(jié)點監(jiān)測區(qū)域范圍內(nèi)。

在保證所有目標(biāo)被覆蓋的前提條件下,采用有效算法節(jié)省傳感節(jié)點能量,最大化網(wǎng)絡(luò)壽命被廣泛研究。如最大限制最小約束啟發(fā)式算法混合整數(shù)規(guī)劃MIP(Mixed Integer Programming)[6]、Greedy-MSC啟發(fā)式算法[7]和基于最大覆蓋集問題的啟發(fā)式算法[8]等。尋找最大覆蓋集等價于最大化不相交集合。即在特定時間,在保證能監(jiān)測目標(biāo)節(jié)點的前提下,僅一個傳感節(jié)點覆蓋區(qū)域需要工作,而其他傳感節(jié)點的覆蓋區(qū)域進(jìn)入休眠模式,從而在不影響監(jiān)測目標(biāo)節(jié)點的情況下,節(jié)省傳感節(jié)點能量。這種模式就是不相交集覆蓋DSC(disjoint Set Cover)問題。

目前,有多種方案求解DSC問題,如貪婪Greedy[9]、IGA(Integer Genetic Algorithm)[10]、MA(Memetic Algorithm)[11]等。此外,文獻(xiàn)[7]提出利用線性規(guī)劃和Greedy混合算法求解DSC問題。首先,利用整數(shù)規(guī)劃和非線性限制計算最大覆蓋集,然后,再利用線性限制將些問題轉(zhuǎn)化為線性規(guī)劃。Ding等[6]還證實了DSC問題是NP-complete。

與其他算法相比,文獻(xiàn)[10]采用的IGA算法是最好的。然而,IGA算法適用小型網(wǎng)絡(luò)。IGA算法的劣勢在于它需要網(wǎng)絡(luò)覆蓋集上限值才能計算網(wǎng)絡(luò)覆蓋集數(shù)。一旦達(dá)到上限值后,每個傳感節(jié)點隨機(jī)加入覆蓋集(Cover Sets)中。如果一個傳感節(jié)點覆蓋了所有目標(biāo)節(jié)點,那它獨自形成一個Cover。一些傳感節(jié)點集不能覆蓋所有目標(biāo)節(jié)點,即使聯(lián)合其他傳感節(jié)點,也未必能覆蓋所有目標(biāo)節(jié)點,不能形成Cover。此外,傳感節(jié)點是隨機(jī)性地加入覆蓋集,未能以優(yōu)化Cover數(shù)角度有選擇性地加入覆蓋集。為此,文獻(xiàn)[11]提出MA(Memetic Algorithm)算法。MA算法采用了Genetic算法,并使用局部優(yōu)化算法提高算法性能。文獻(xiàn)[12]提出Learning Automat技術(shù)解決DSC問題。每個傳感節(jié)點向鄰居節(jié)點廣播廣告數(shù)據(jù)包,其包含節(jié)點位置、覆蓋信息。

為此,本文以識別傳感節(jié)點的覆蓋Cover,監(jiān)控整個目標(biāo)節(jié)點為目的,提出基于MA的改進(jìn)IMA(Improver MA)算法。與MA算法相比,IMA算法從全局考慮,將所有傳感節(jié)點劃分為子集,子集覆蓋cover所有目標(biāo)節(jié)點,然后每個子集輪流工作,實施監(jiān)控所有目標(biāo)節(jié)點,進(jìn)而最大化Cover的數(shù)量。即采用了基于IMA算法求解DSC問題,通過這種方式,提高傳感節(jié)點能量效率,延長網(wǎng)絡(luò)壽命。

1 系統(tǒng)模型及問題描述

設(shè)S={S1,S2,…,Sn}為n個傳感節(jié)點集,在區(qū)域內(nèi)隨機(jī)分布,監(jiān)控m個目標(biāo)節(jié)點T={T1,T2,…,Tm}。每個傳感節(jié)點Si的坐標(biāo)表示為(xi,yi),且通信范圍為R。每個目標(biāo)節(jié)點Tj的坐標(biāo)表示為(xj,yj)。若(xi,yi)與(xj,yj)滿足式(1),則認(rèn)為傳感節(jié)點Si覆蓋目標(biāo)節(jié)點Tj。

(xi-xj)2+(yi-yj)2≤R2,1≤i≤n,1≤j≤m

(1)

目標(biāo)節(jié)點Tj可能有一個或多個傳感節(jié)點所覆蓋,但是,實際上只要有一個傳感節(jié)點覆蓋就足夠。如果所有傳感節(jié)點同時覆蓋同一個目標(biāo)節(jié)點[13],就產(chǎn)生不必要的損耗。為了克服此問題,需利用DSC將所有傳感節(jié)點劃分為子集,子集覆蓋所有目標(biāo)節(jié)點,然后每個子集輪流工作,實施監(jiān)控所有目標(biāo)節(jié)點,通過這種方式,提高傳感節(jié)點能量效率,延長網(wǎng)絡(luò)壽命。

設(shè)C={c1,c2,…,ck},且ci?S,i=1,2,…,k,表示覆蓋集。每個coverci包含一些傳感節(jié)點,由這些傳感節(jié)點聯(lián)合覆蓋,實現(xiàn)覆蓋所有目標(biāo)節(jié)點。|ci|表示ci的傳感節(jié)點數(shù)。

每個傳感節(jié)點必須位于一個且只有一個cover內(nèi),即ci∩cj=φ,i,j=1,2,…,k,且i≠j。

圖1 n=6、m=4的無線傳感網(wǎng)絡(luò)及覆蓋范圍

圖1顯示了6個傳感節(jié)點覆蓋4個傳感節(jié)點的示意圖。利用式(1),識別每個傳感節(jié)點的覆蓋區(qū)域。傳感節(jié)點S1覆蓋了兩個目標(biāo)節(jié)點T1、T2,表示為S1={T1,T2},類似地,S2={T3}、S3={T1,T2,T3,T4}、S4={T1}、S5={T4}以及S6={T2,T3,T4}。

定義矩陣A描述傳感節(jié)點對目標(biāo)節(jié)點的覆蓋情況。如果Si覆蓋目標(biāo)節(jié)點Tj,相應(yīng)矩陣元素Aij的值為1,否則為0,如式(2)所示。

(2)

因此,以圖1所示的傳感網(wǎng)絡(luò)為例,形成的矩陣A:

式中:行表示傳感節(jié)點、列表示目標(biāo)節(jié)點。例如,第1行,S1覆蓋了兩個目標(biāo)節(jié)點T1、T2,因此,T1、T2兩列的值為1,其余列為0。

假定目標(biāo)節(jié)點Tj由k個傳感節(jié)點覆蓋,這些節(jié)點可以構(gòu)成k個covers。這k個covers可作為WSN的網(wǎng)絡(luò)壽命的上限(upper bound)。因此,upper bound ub:

(3)

從矩陣A可知,每列元素和分別為[3 3 3 3]。最小值為3。因此,圖1所述的網(wǎng)絡(luò)結(jié)構(gòu)的上限ub=3。這個數(shù)據(jù)說明,目標(biāo)節(jié)點最少由3個傳感節(jié)點數(shù)所覆蓋,這就意味著該網(wǎng)絡(luò)最多可以形成3個cover,從而保證每個cover能夠覆蓋所有目標(biāo)節(jié)點[14]。以圖1網(wǎng)絡(luò)為例,形成的3個cover分別是c1={S3}、c2={S4,S6}以及c3={S1,S2,S5}。每一個cover均覆蓋所有目標(biāo)節(jié)點。其中,c1由一個傳感節(jié)點S3覆蓋,c2、c3由多個傳感節(jié)點聯(lián)合覆蓋所有目標(biāo)節(jié)點。

本文,需要解決的問題就是:針對網(wǎng)絡(luò),計算網(wǎng)絡(luò)的上限,找到可形成cover,保證每個cover能夠覆蓋所有目標(biāo)節(jié)點。

2 IMA算法

2.1 MA算法

MA算法采用了Lamarckian理論,即子孫后代offspring能夠繼承它們父輩的知識或特性,并且MA算法采用隨機(jī)加入Cover,并沒有從優(yōu)化Cover數(shù)的角度,有目的性地選擇傳感節(jié)點加入Cover。而提出的IMA算法采用了提高算子Operators、改進(jìn)算子Improver以及優(yōu)化算子Optimizer,通過這3個階段,最大化Cover數(shù),解決DSC問題,提高網(wǎng)絡(luò)壽命。

如果一個傳感節(jié)點或多個傳感節(jié)點聯(lián)合覆蓋所有目標(biāo)節(jié)點,能形成一個cover。依據(jù)mating pool,計算每個矩陣中總的cover數(shù)。以矩陣A為例,第1行(傳感節(jié)點S1)覆蓋了兩個目標(biāo)節(jié)點,因此,其需要與一個或多個傳感節(jié)點聯(lián)合,形成一個cover。假定S1隨機(jī)性地選擇傳感節(jié)點S2聯(lián)合,可形成c1=[1 1 0 0]∪[0 0 1 0]=[1 1 1 0]。但是,并沒有覆蓋所有目標(biāo)節(jié)點(目標(biāo)節(jié)點T4未覆蓋),需繼續(xù)聯(lián)合操作,直到能覆蓋所有目標(biāo)節(jié)點。為此,c1繼續(xù)與傳感節(jié)點S3聯(lián)合,即c1=[1 1 1 0]∪[1 1 1 1]便形成一個cover。類似地,第4行(傳感節(jié)點S4)不能獨自形成cover,需聯(lián)合其他傳感節(jié)點(傳感節(jié)點S5、S6)形成cover,即c1=[1 0 0 0]∪[0 0 0 1]∪[0 1 1 1]=[1 1 1 1]。因此,若采用MA方式,矩陣A所形成的cover數(shù)等于2。

依據(jù)MA方案,只產(chǎn)生了兩個cover,而實際上矩陣A對應(yīng)的傳感網(wǎng)絡(luò)的上限ub=3,即可以形成3個cover。為此,提出MA的改進(jìn)算法IMA。

2.2 MA的改進(jìn)算法IMA

提出的IMA算法先產(chǎn)生initial population矩陣,然后,對其進(jìn)行變換,在initial population矩陣選取最優(yōu)的行加入到另一個矩陣,從而形成子矩陣。隨后進(jìn)入優(yōu)化Optimizer階段、改進(jìn)Improver階段,最終形成最大化的cover。接下來,描述IMA的具體過程。

2.2.1 Initial population

IMA先對網(wǎng)絡(luò)內(nèi)傳感節(jié)點數(shù)隨機(jī)排列,并結(jié)合式(2)形成Initial population矩陣I。將Initial population矩陣I稱為父矩陣,其類似于傳感節(jié)點覆蓋矩陣A,然后再從父矩陣中篩選覆蓋了所有目標(biāo)節(jié)點的傳感節(jié)點所在的行,并從I中移除該行,形成兩個矩陣I′和I″。最初,矩陣I′中存儲覆蓋了所有目標(biāo)節(jié)點的傳感節(jié)點,稱為子矩陣。若矩陣I中不存在覆蓋所有目標(biāo)節(jié)點的傳感節(jié)點,那么就從矩陣I中選擇覆蓋目標(biāo)節(jié)點數(shù)最多的傳感節(jié)點移到矩陣I′中。I″中存儲未能覆蓋所有目標(biāo)節(jié)點的傳感節(jié)點,仍稱為父矩陣。

考慮圖1所示的WSNs為例,6個傳感節(jié)點分布于網(wǎng)絡(luò)區(qū)域內(nèi),假定6個傳感節(jié)點的隨機(jī)排列數(shù)為[6 3 1 4 2 5]?；谶@個隨機(jī)數(shù)(第6個傳感節(jié)點在第1行、第3個傳感節(jié)點在第2行,以此類推),產(chǎn)生的Initial population矩陣I:

從矩陣I可知,有些傳感節(jié)點獨自覆蓋所有目標(biāo)節(jié)點,如傳感節(jié)點S3(矩陣I的第2行)。為此,IMA算法從父矩陣I中先移除覆蓋所有目標(biāo)節(jié)點的傳感節(jié)點所有行,形成兩個矩陣I′和I″,如式(4)所示。

(4)

接下來,進(jìn)一步對矩陣I′和I″進(jìn)行變換。

①優(yōu)化Optimizer階段

獲取了矩陣I′和I″后,進(jìn)入優(yōu)化Optimizer階段,目的在于:在矩陣I″中,通過聯(lián)合一個或多個傳感節(jié)點,形成一個Cover。首先從矩陣I″中,選擇行值最大所對應(yīng)的傳感節(jié)點加入I′,通過式(5)計算。

(5)

矩陣I″包含的所有傳感節(jié)點中沒有覆蓋所有目標(biāo)節(jié)點。為此,在Optimizer階段,從矩陣I″中選擇一個傳感節(jié)點,插入矩陣I′中的尾行。

仍以圖1所示的WSNs為例,矩陣I″中,第1行的行值最大,即選擇S6加入矩陣I″中,插入矩陣I′中,如式(5)所示。隨后,進(jìn)入Improver階段。

(6)

②改進(jìn)Improver階段

Improver階段的目的在于選擇最佳傳感節(jié)點,使之能夠覆蓋矩陣I′的尾行未能覆蓋的目標(biāo)節(jié)點,加入I′矩陣,形成一個cover。

首先,檢測在Optimizer階段選擇插入矩陣I″的傳感節(jié)點是否包含所有目標(biāo)節(jié)點,沒有包含,則需要找到該傳感節(jié)點未覆蓋的目標(biāo)節(jié)點。利用式(7)要找到剛插入I′尾行對應(yīng)的傳感節(jié)點S′未覆蓋目標(biāo)節(jié)點。

(7)

式中:i表示該傳感節(jié)點S′在I′所在的行。m表示目標(biāo)節(jié)點總數(shù)。傳感節(jié)點S′未覆蓋的目標(biāo)節(jié)點個數(shù)等于矩陣b中非零的個數(shù),非零的數(shù)的大小表示第幾個目標(biāo)節(jié)點未覆蓋。

仍以圖1所示的WSNs為例,矩陣I′的尾行S6未覆蓋目標(biāo)節(jié)點T1。例如,剛在矩陣I′插入S6,其在第2行,即i=2。因此

={-1(0-1),-2(1-1),-3(1-1),-3(1-1)}

={1,0,0,0}

(8)

依式(8)可知,矩陣b中只有一個非零數(shù),則表明只有一個目標(biāo)節(jié)點未被覆蓋,并且該非零數(shù)等于1,而表明第1個目標(biāo)節(jié)點未被覆蓋,即j=1。

找到未覆蓋的目標(biāo)的節(jié)點后,需從矩陣I″中尋找一個傳感節(jié)點,其能覆蓋該目標(biāo)節(jié)點Tj。提出的IMA算法采用式(8)尋找符合條件的傳感節(jié)點:

cbk={lI″lbk},l=1,2,…,m

(9)

式中:bk表示一維矩陣b的第k個元素,m為矩陣I″的行數(shù)。

cbk中非零的數(shù)h表示矩陣I″中第h行所在的傳感節(jié)點能夠覆蓋Tj。

以式(6)為例,可得cb1={1 0 3 0},如式(10)所示。

cb1={1I″112I″213I″314I″41}

={1×1 2×0 3×1 4×0}

={1 0 3 0}

(10)

cb1={1 0 3 0}則表明矩陣I″中第1行、第3行所在的傳感節(jié)點能夠覆蓋第1個目標(biāo)節(jié)點T1。

綜上所述可知,通過這種方式能夠找到矩陣b中未被覆蓋的目標(biāo)節(jié)點Tj,并能夠從矩陣I″找到能夠覆蓋Tj的傳感節(jié)點。

注意式(7),只有一個非零數(shù),意味著只有一個目標(biāo)節(jié)點未被覆蓋。若出現(xiàn)多個目標(biāo)節(jié)點未被覆蓋時,需要從矩陣I″找到能夠覆蓋所有未被覆蓋的目標(biāo)節(jié)點的傳感節(jié)點。為此,可利用式(11)找到這類傳感節(jié)點。

d=∩cbk

(11)

若d=φ,則表明矩陣I″中沒有能夠覆蓋矩陣b中所有未被覆蓋的目標(biāo)節(jié)點的傳感節(jié)點。在這種情況下,退優(yōu)尋其次,尋找能夠覆蓋矩陣b中最多未被覆蓋的目標(biāo)節(jié)點的傳感節(jié)點。

仍以上事例為例,矩陣b中只有一個目標(biāo)節(jié)點未,d={1,3}表明第1個傳感節(jié)點、第3個傳感節(jié)點能夠覆蓋該目標(biāo)節(jié)點。

最后,IMA算法需要從d中選擇一個覆蓋的目標(biāo)節(jié)點數(shù)最少的傳感節(jié)點數(shù):

e=minimum target(d)

(12)

以d={1,3}為例,依據(jù)式(12)選擇第3個傳感節(jié)點,即e=3。因為第1個傳感節(jié)點覆蓋了兩個目標(biāo)節(jié)點([1 1 0 0]),而第3個傳感節(jié)點覆蓋了只有一個傳感節(jié)點([1 0 0 0])。

確定了e=3值后,將從I″中選擇該傳感節(jié)點插入矩陣I′,如式(12)所示。

(13)

從式矩陣I′、I″可知,共形成了3個cover,如式(14)所示。每個cover覆蓋了所有目標(biāo)節(jié)點。

(14)

若選擇第1個傳感節(jié)點插入,即e=1:

這樣的話,可能形成兩個cover,如式(15)所示。

(15)

通過這個事例表明提出的IMA算法能夠提高cover的個數(shù)。

整個IMA算法的步驟如下:

①隨機(jī)排列傳感節(jié)點,依據(jù)式(2)產(chǎn)生Initial population矩陣I,并將矩陣I中移除覆蓋所有目標(biāo)節(jié)點所對就的行,形成I′和I″。

②進(jìn)入Optimizer階段:依據(jù)式(5),從矩陣I″中移出覆蓋目標(biāo)節(jié)點最多的傳感節(jié)點,并插入矩陣I′尾行,形成新的矩陣I′和I″;

④利用式(9)cbk={lI″lbk},計算I″中能夠覆蓋目標(biāo)節(jié)點Tj的傳感節(jié)點所在行。

⑤利用式(11)計算d=∩cbk;

⑥利用式(12)計算e=minimum target(d);

⑦從I″中選擇e行插入矩陣I′。最后矩陣I′和I″的傳感節(jié)點能夠形成最大的cover數(shù)。

3 仿真及性能分析

考慮網(wǎng)格區(qū)域進(jìn)行仿真,采用MATLAB軟件評估IMA算法性能,并與MA[11]、IGA[9]和MCMCC[15]、MC-MIP[6]進(jìn)行比較。引用Upper bound是cover的最大數(shù)。如果算法達(dá)到Upper bound,則說明其是最優(yōu)的算法。因此,作歸一化處理,將各算法的cover數(shù)除以Upper bound,稱為上限逼近值,值越大,說明越接近上限值,性能越好。當(dāng)?shù)扔?時,說明等于上限值,達(dá)到最優(yōu)。每次實驗重復(fù)進(jìn)行20次,取平均值作為最終的仿真數(shù)據(jù)。

①通信范圍的影響

圖2描述了n=90、m=10網(wǎng)絡(luò)的內(nèi)各算法的上限逼近值。從圖2可知,3個算法(IMA、IGA、GA)在通信范圍R小于300時,上限逼近值為1,達(dá)到上限值。當(dāng)大于300時,上限逼近值開始下降。然而,與IGA、GA、MCMCC算法相比,提出的IMA算法下降很少,從圖2的第1個子圖可知,最小值為0.99。而GA、MCMCC的最小值達(dá)到0.97。

圖2 通信范圍R對cover數(shù)的影響曲線

②目標(biāo)節(jié)點個數(shù)m的影響

本次仿真考查目標(biāo)節(jié)點個數(shù)m對cover數(shù)的影響,并兩類場景:90個傳感節(jié)點的網(wǎng)絡(luò)(n=90)、300個傳感節(jié)點的網(wǎng)絡(luò)(n=300)。

圖3描述了n=90、通信范圍R=200的無線傳感網(wǎng)絡(luò)的cover數(shù)隨目標(biāo)節(jié)點個數(shù)m的變化情況,其中目標(biāo)節(jié)點數(shù)m從10、20、30、40、50、75、100、150、200、250和300變化。從圖3可知,MA和IGA算法在90個傳感節(jié)點的小型網(wǎng)絡(luò)環(huán)境下最優(yōu),上限逼近值均等于1,提出的IMA算法的上限逼近值在0.9982附近。其中,MCMCC算法方案最差,上限逼近值在0.975 3附近。

圖3 目標(biāo)節(jié)點個數(shù)m對cover數(shù)的影響曲線

圖4描繪n=300、通信范圍R=200時無線傳感網(wǎng)絡(luò)的cover數(shù)隨目標(biāo)節(jié)點個數(shù)m的變化情況,其中目標(biāo)節(jié)點數(shù)m從10、20、30、40、50、75、100、150、200、250和300變化。從圖4可知,提出的IMA算法最優(yōu),而MA和IGA算法性能開始下降,這些數(shù)據(jù)表明MA、IGA算法只適合小型傳感網(wǎng)絡(luò),而IMA適合較大型網(wǎng)絡(luò)。

圖4 目標(biāo)節(jié)點個數(shù)m對cover數(shù)的影響曲線

③傳感節(jié)點個數(shù)n的影響

圖5描述了傳感節(jié)點個數(shù)n對m=10、通信范圍為200的網(wǎng)絡(luò)環(huán)境的cover數(shù)的影響曲線。如圖5可知,提出的IMA算法最優(yōu),除了個別值不等1之外,其余均等于1。而MA、IGA和MCMCC均隨著傳感節(jié)點數(shù)增加,上限逼近值下降,MCMCC算法下降最快,低至0.965。

此外,為了更充分地分析IMA算法在形成cover數(shù)優(yōu)勢,在n=90、通信范圍R=200的無線傳感網(wǎng)絡(luò)環(huán)境,測試IMA、IGA、MC-MIP以及MCMCC在20次的重復(fù)仿真中cover數(shù)的最大數(shù)、平均數(shù),結(jié)果如圖6、圖7所示。

從圖6和圖7可知,提出的IMA算法的cover的最大數(shù)與IGA相近,并遠(yuǎn)遠(yuǎn)優(yōu)于MC-MIP和MCMCC,并且IMA算法的cover的平均數(shù)最大,比MCMCC算法提高了近4個。

圖5 傳感節(jié)點個數(shù)n對cover數(shù)的影響曲線

圖6 cover的最大數(shù)(n=90、R=200)

圖7 cover的平均數(shù)(n=90、R=200)

通過上述仿真數(shù)據(jù)可知,提出的IMA算法能夠有效解決DSC問題,并使得網(wǎng)絡(luò)內(nèi)的cover數(shù)達(dá)到最大,逼近上限值,從而有效提高傳感節(jié)點的能量利用率,提高網(wǎng)絡(luò)壽命。

4 總結(jié)

本文采用IMA算法求解DSC問題,進(jìn)而延長WSN的網(wǎng)絡(luò)壽命。IMA算法先依據(jù)WSN的拓?fù)浣Y(jié)構(gòu)建立初始矩陣Initial populationI,隨后從I篩選能夠覆蓋所有目標(biāo)節(jié)點的傳感節(jié)點,形成矩陣I′和I″,再經(jīng)優(yōu)化Optimizer階段、改進(jìn)Improver階段,形成最大化covers,每個cover覆蓋所有目標(biāo)節(jié)點。每個cover輪流工作,節(jié)省傳感節(jié)點能量,最終,實現(xiàn)延長網(wǎng)絡(luò)壽命的目的。仿真結(jié)果表明,與啟發(fā)式算法相比,提出的IMA算法能夠逼近cover上限。

[1]Fatme M,Eric T,Guoliang X. Maximizing Network Topology Lifetime Mobile Node Rotation[J]. IEEE Transactions on Parallel and Distributed Systems. 2013,34(5):1-14.

[2]Zitterbart D,Wienecke B,Butler J,et al. Coordinated Movements Prevent Jamming in an Emperor Penguin Huddle. PLoS One,2011,6(6):202-216.

[3]Xu H,Huang L,Zhang Y,et al. Energy-Efficient Cooperative Data Aggregation for Wireless Sensor Networks[J]. J Parallel Distrib Comput,2010,70(9):953-961.

[4]El-Moukaddem F,Torng E,Xing G. Maximizing Data Gathering Capacity of Wireless Sensor Networks Using Mobile Relays[C]//IEEE MASS,2010:312-321.

[5]夏韻,陳志剛,曾鋒. 無線傳感器網(wǎng)絡(luò)中基于MDS-MCC問題的啟發(fā)式算法研究[J]. 計算機(jī)工程與科學(xué),2013,35(4):53-58.

[6]Mihaela Cardei,Ding-Zhu Du. Improving Wireless Sensor Network Lifetime through Power Aware Organization[J]. Wireless Networks,2005,1(3):333-340.

[7]Mihaela Cardei,Thai M T,Yingshu Li,et al. Energy Efficient Target Coverage in Wireless Sensor Networks[J]. IEEE INFOCOM,2005:1976-1984.

[8]Mihaela Carde. Energy Efficient Coverage Problems in Wireless Ad-Hoc Sensor Networks[J]. Computer Communications,2006,29(4):413-420.

[9]Zoe Abrams,Ashish Goel,Serge Plotkin. Setk-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks. IPSN’04,2004:424-432.

[10]Chih-Chung Lai,Chuan-Kang Ting,Ren-Song Ko. An Effective Genetic Algorithm to Improve Wireless Sensor Network Lifetime for Large-Scale Surveillance Applications[C]//proceedings of the 2007 Congress on Evolutionary Computation. 2007:3531-3538.

[11]Chuan-Kang Ting,Chien-Chih Liao. A Memetic Algorithm for Extending Wireless Sensor Network Lifetime[J]. Information Sciences,2010,180(24):4818-4833.

[12]Mostafaei H,Meybodi M R. Maximizing Lifetime of Target Coverage in Wireless Sensor Networks Using Learning Automata[J]. Wireless Personal Communications,2013,71(2):1461-1477.

[13]王銓,黃戰(zhàn)華,蔡懷宇,等. 高精度分劃自動對焦評價函數(shù)研究[J]. 傳感技術(shù)學(xué)報,2013,26(1):49-53.

[14]吳曉平,談士力. 基于半定規(guī)劃的無線傳感網(wǎng)絡(luò)定位算法的性能分析[J]. 傳感技術(shù)學(xué),2012,25(12):1731-1738.

[15]Sasa Slijepcevic,Miodrag Potkonjak. Power Efficient Organization of Wireless Sensor Metworks[J]. IEEE International Conference on Wireless Communications,2001:472-476.

Research of Memetic Algorithm Based on DSC Problem in Wireless Sensor Networks*

YANYuan1*,ZAIWenjiao2

(1.College of Foundation Studies,Zhanjiang Normal University,Zhanjiang Guangdong 524048,China;2.Institute of Engineer,Sichuan Normal University,Chengdu 610101,China)

A critical aspect of applications in wireless sensor network(WSN)is its lifetime. This issue has received increased attention due to the recent advances in affordable and efficient integrated electronic devices. One approach to extend the wireless sensor network lifetime is to divide the deployed set of all sensors into disjoint subsets of sensor covers,such that each sensor cover can cover all targets and get activated one after another. The sensor network lifetime can be increased by identifying the maximum number of covers and it can be identified through disjoint set cover(DSC). In this paper,a novel improved memetic algorithm(IMA)is proposed to give a better solution to the DSC. In IMA algorithm,firstly establish the initial population,then optimize process,improve process,finally maximize the numbers of covers. Simulation results show that the proposed IMA can maximize the total number of covers compared with several heuristic and evolutionary algorithm.

wireless sensor networks;network lifetime;disjoint set cover;memetic algorithm;upper bound

顏 源(1980-),女,四川西昌人,碩士,講師,主要研究方向為WSN同步技術(shù)與應(yīng)用、物聯(lián)網(wǎng)視頻感知與識別技;

宰文姣(1979-),女,湖北武漢人,工學(xué)碩士,副教授,研究方向為智能控制、電機(jī)調(diào)速等。

項目來源:四川省教育廳自然科學(xué)基金項目(13ZB0163);國家自然科學(xué)基金項目(61373162);國家科技計劃支撐項目(2012BAH76F01)

2014-10-24 修改日期:2014-12-14

C:7110

10.3969/j.issn.1004-1699.2015.03.023

TPT393

A

1004-1699(2015)03-0430-07