能耗約束的無線傳感器網絡的目標覆蓋和路由分配研究*

陸星家,陳志榮

(寧波工程學院理學院,浙江 寧波 315211)

?

能耗約束的無線傳感器網絡的目標覆蓋和路由分配研究*

陸星家*,陳志榮

(寧波工程學院理學院,浙江 寧波 315211)

針對現有目標覆蓋算法未充分考慮能量消耗和路由分配的不足,提出一種基于目標覆蓋的能耗約束路由分配算法,該算法能夠確保所有目標被完全覆蓋,并降低數據傳輸能耗。首先,通過貪婪啟發式策略獲取最大集合覆蓋。然后在集合覆蓋基礎上,通過協同進化機制對網絡生存周期和時延等目標進行評價。利用適應度評估、輪盤賭選擇、交叉、變異和記憶等進化機制改良目標的可行解。實驗結果表明,提出的算法可以降低基于路由分配的目標覆蓋算法的能量消耗,延長網絡生存周期,降低網絡傳輸時延。

無線傳感器網絡;目標覆蓋;路由分配;能耗約束;最大集合覆蓋算法;協同進化機制

無線傳感器網絡(WSN)是指具有一定自主性,能夠從環境中收集數據,同時發送到數據處理中心的自組織網絡。無線傳感器網絡通常是由許多小的,獨立的和能量有限的傳感器節點構成[1]。隨著無線傳感器網絡技術的不斷完善,其在軍事和民用領域也有廣泛的應用,如動物棲息地監測,地震預報,車輛跟蹤系統和醫療保健等。在以上應用環境中,無線傳感器使用自帶電源感知目標,如果其電量耗盡,節點將停止工作,因此如何降低無線傳感器網絡的能量消耗,延長網絡生存期一直是其研究的重點。

目標覆蓋是無線傳感器網絡的核心應用,該問題指傳感器節點感知進入網絡監測范圍的目標,并將感知數據傳輸到數據中心的過程。覆蓋模型最早是由Cardei提出,該問題已被證明是一個NP-Hard問題[2]。非相交覆蓋集和相交覆蓋集是目標覆蓋最主要的兩種研究方法:其中非相交覆蓋集指節點的覆蓋范圍沒有重疊;相交覆蓋集指節點覆蓋范圍可以重疊。Cardei利用相交覆蓋集和Lingo線性規劃模塊對其優化,限制了實際場合中的應用[2]。Zobra利用相交和非相交覆蓋集研究目標覆蓋,兩種方法對比發現,使用相交覆蓋集可以有效地延長網絡覆蓋時間[3]。Chaudhry利用進化算法研究了傳感器節點的布設問題,進而優化網絡的數據傳輸[4]。林祝亮提出一種基于粒子群算法的無線傳感器網絡布局優化方案[5],該算法主要針對節點在區域中的布局問題展開研究,如果節點位置調整后依然存在較多的感知重疊區域,仍然會產生不必要的能耗;顧曉燕在林祝亮的基礎上,通過感知范圍調整減少感知盲區和重疊區,首先研究傳感器節點的布置,然后調整節點的感知范圍,但是未能考慮傳感器節點之間的相互通訊[6]。Sengupta利用多目標進化算法研究目標覆蓋問題,通過與NSGA-II和CPLEX算法的對比研究,但是其目標覆蓋算法未采用相交覆蓋集,因此缺乏與其他算法對比的依據[7]。

傳感器網絡的能耗不僅包括目標覆蓋能耗,也包括數據傳輸的能耗,但是其能耗優先級低于目標覆蓋。Fonoage M研究無線傳感器網絡在數據傳輸時的擁塞問題,但未考慮擁塞問題對節點能耗的影響[8]。Heinzelman提出的LEACH算法采用層次聚類的方法傳輸數據,采用隨機選舉的方法獲得簇頭,其提出的節點能耗模型被廣泛采用,但LEACH算法未考慮目標覆蓋問題[9]。Deng J提出基于能耗的多跳-直接的路由算法,通過將傳輸路徑的分割成多條路徑降低網絡能耗,但是該算法的前提是網絡節點分布稠密[10]。Jin W在此基礎上研究了網絡傳輸跳數與能耗的關系[11]。侯惠峰提出基于地理信息的無線傳感器網絡路由算法采用分布式的路由決策[12]。Marta研究了多Sink點下的靜態網絡的能耗問題,通過多Sink節點克服網絡數據傳輸過程的分區問題[13]。Olariu研究了無線傳感器網絡能耗的變化與覆蓋范圍之間的變化規律,探討了網絡傳輸中的能量漏洞問題,提出如果節點傳輸范圍和Sink節點固定,能量漏洞將無法避免[14]。

國內外較多的學者分別研究了無線傳感器網絡的目標覆蓋以及數據傳輸過程中的能耗問題,但是并未根據應用場合考慮兩者間的關系,在無線傳感器網絡的主要應用中,目標覆蓋是優先考慮的問題,即在保證目標覆蓋能耗的前提下考慮網絡傳輸的能耗。彭鐸等在LEACH協議的基礎上,提出一種非均勻分簇路由協議對簇間負載進行分析,但未考慮簇間重疊問題[15]。馮亞超等對PEADG(Power Efficient Algorithm for Data Gathering)協議進行優化,但是未結合目標覆蓋[16]。Akhtar等對網狀無線傳感器網絡的能耗和路由問題進行研究,但其傳感器網絡節點只考慮均勻分布[17]。

本文針對節點感知距離可調的無線傳感器網絡,提出一種基于協同進化算法,利用相交集覆蓋目標,平衡目標覆蓋和數據傳輸的節點能耗。首先通過相交集覆蓋目標,通過貪心算法優化覆蓋集的調度,提高節點的電量利用率和目標覆蓋質量;然后在保證目標覆蓋的前提下,利用協同進化算法優化數據傳輸路徑和網絡時延,進一步減少傳輸節點的能耗,降低網絡能耗,延長網絡壽命。

1 目標覆蓋

目標覆蓋,即尋找最優的目標覆蓋組合,通過調度不同相交集或不相交集,延長網絡的生存周期。在目標覆蓋中,由于節點直接覆蓋目標,因此可以忽略目標覆蓋過程的數據傳輸時延。

1.1 節點定義

傳感器節點通常被部署在一個兩維空間,每個傳感器需要獲取部署后的節點的經緯度。通過節點的經緯度可以計算任意兩個傳感器節點之間歐幾里德距離。假設每個傳感器節點使用全方向天線,即一個傳感器節點發射的信號可以在任何角度上接收。由于傳感器節點的空間距離較近,不會受到地球曲率的影響,不需要轉化為曲面距離。

圖1 無線傳感器網絡的目標覆蓋

圖1中有3個傳感器節點和10個需要覆蓋的目標。S1號節點在第一時間段覆蓋10個目標,如果下一時間段是S2號節點,或者S3號節點覆蓋10個目標,則構成一個非相交覆蓋集;如果下一時間段是S1號、S3號節點覆蓋,則產生相交覆蓋集。在S1號節點覆蓋10個目標時,S2號、S3號節點處于休眠狀態,功耗可以忽略。圖2顯示3個節點的通信過程,2號節點發送數據包,1號節點和3號節點接受數據包,3號節點接收到數據包之后,繼續廣播發送數據。1號節點如果在廣播范圍內沒有后續節點,將不轉發數據包。

圖2 無線傳感器網絡的節點通信

定義1 節點的能耗模型,節點的能量消耗與傳輸數據、感知目標的距離有關[8,15],節點傳輸數據、接收數據和感知目標的能耗分別是Et、Er和Es,k表示傳輸數據的位數,Eelec和εamp表示傳感器節點的數據處理和信號發射系數,Esen表示傳感器節點的感知系數,d表示節點間距離。

(1)

定義2 網絡傳輸時延模型,D(s0,si)表示從s0節點傳輸到si節點的時間延遲。主要包括每個節點在傳輸數據時的數據排隊延時dq,傳輸延遲dt和廣播延遲dp,n(s0,si)表示數據傳輸起始節點s0到數據處理節點si的轉發跳數。

(2)

1.2 最大覆蓋集

給定一組含有m個傳感器節點S={s1,s2,…,sm}和n個目標集合R={r1,r2,…,rn}的集合。si∈C表示節點屬于目標覆蓋集合。最大覆蓋集算法的目標函數如式(3),求p的最大值,xij=1表示第i節點能夠覆蓋第j目標。約束條件1表示i節點分配的覆蓋時間不能超過1,即每個節點覆蓋目標的最大時長為p,約束條件2表示在網絡生存期內,任意時刻至少有一個傳感器節點能夠覆蓋所有目標。

(3)

wherexij=0,1(xij=1if?si∈Sj)

由于在式(3)沒有明確的最小時間間隔,我們在式(3)中引入最小時間間隔Δt,即目標覆蓋的最短時間單位,同時引入節點能耗si(e),式(3)轉變為式(4)。

(4)

wherexij=0,1(xij=1if?si∈Sj)

tj=Δt,ei=si(Esen·d·Δt)

目標覆蓋即保證網絡中所有目標都能夠被傳感器節點覆蓋。

①目標覆蓋轉化為合取范式(CNF),CNF由分句和詞構成,其中詞是最基本的單位,詞與詞之間通過析取式連接(OR),分句由詞構成,分句與分句之間通過合取式連接(AND)。

②根據目標覆蓋的要求,即構建一個{c1}∧…∧{cj},其中j表示目標數量,在任意時刻k,每一個目標都要被覆蓋,{c1}由{x11∨x21∨…∨xi1}組成。則該問題被轉化為3-SAT問題,因此目標覆蓋集是NP-Complete。根據目標覆蓋的合取范式(CNF),提出覆蓋集算法(算法1),傳感器節點集S、目標集R作為輸入,輸出是覆蓋集,首先建立節點和目標之間的距離矩陣,如果距離超過設定的閾值,即節點不能覆蓋目標;然后構建每個目標被節點覆蓋的鏈表,最后通過鏈表構建覆蓋集。

算法1 覆蓋集算法

輸入:傳感器集S={s1,s2,…,sm}和目標集R={r1,r2,…,rn}

輸出: 相交覆蓋集C={c1,c2,…,ck}

獲取目標和節點之間的距離矩陣

構建 完全覆蓋集合ck,并將ck添加到C中

算法1在目標覆蓋集基礎上,構建最大集合覆蓋,其優化目標是使網絡生存期最大,即滿足式(4)。最大集合覆蓋算法主要有ILP算法(IntegerLinearProgramming)和貪心算法,貪心算法具有收斂速度快的優勢,因此在本文中選用貪心算法對最大集合覆蓋進行優化,即首先選擇能耗最小的{c1}∧…∧{cj}的覆蓋集合,通過選擇能耗不斷遞增的覆蓋集合完成目標覆蓋時長的最優方案。

算法2是基于貪心策略的最大覆蓋集合算法,相交覆蓋集C作為輸入,輸出是最大覆蓋集序列,首先根據相交覆蓋集的能耗選擇能耗最小的覆蓋集。當最小覆蓋集cj節點電量耗盡,C刪除cj中的節點。

算法2 最大覆蓋集合算法

輸入: 相交覆蓋集C={c1,c2,…,ck}

輸出: 覆蓋集序列Seq={ct1,ct2,…,ctp}

While(1)

cj=argmin{c1,c2,…,ck}

If (si<(Esen·d·Δt),?si∈cj)

ThenC=C-{cj}

Elsecj→Seq

EndWhile

1.3 實例分析

圖3顯示在100m×100m的區域內,10個Sensor和10個目標被隨機部署,每個傳感器節點的初始電量為100mAh,Esen=0.000 5,Δt的最小切換時間間隔為分鐘。通過最大集合覆蓋算法可以獲得9個覆蓋集,其中包含2個相交覆蓋集合7個非相交覆蓋集。

圖4顯示在9個覆蓋集中,覆蓋集的調用次序是{{s2},{s6},{s4},{s2,s7,s8},{s9},{s1,s2,s7},{s5},{s10},{s7}},當十個傳感器節點的電量完全耗盡時,網絡的生存周期是258h。

圖3 目標覆蓋集合(10個Sensors和10個目標)

圖4 10個傳感器節點覆蓋能耗變化圖

2 多路徑分配

在節點完成目標覆蓋之后,網絡需要將采集的目標數據發送到數據處理中心。覆蓋節點作為數據傳輸的起點,Sink節點作為數據傳輸的終點。無線傳感器網絡需要考慮目標覆蓋,網絡傳輸能耗以及傳輸時延。由于覆蓋節點需要不斷地調度以延長網絡生命周期,因此,覆蓋節點與數據中心間的數據鏈路也要相應地進行優化調度。在數據傳輸過程中,數據傳輸受到節點能耗和網絡傳播時延的影響。協同進化算法是一種多目標優化算法,該算法通過生成多個初始個體和進化機制改善解,相對與ILP、貪心算法而言,協同進化算法可以減少多個目標間的局部競爭,通過協同機制,保證解的全局最優性,提高算法的收斂速度。該算法包括5步驟:①染色體編碼和初始化;②染色體選擇;③雜交和突變;④可行解評價;⑤種群更新和記憶。

算法3 協同進化算法

輸入: Ppop:產生初始種群

PGen:迭代次數

PC:設定解的上界和下界

Step 1: 染色體初始化:產生解。

Step 2: 染色體選擇:驗證解的可行性。

Step 3: 雜交和變異:隨機選擇位點,兩個染色體進行基因交換,通過隨機數在位點進行變異操作。

Step 4: 通過目標函數的評價,獲取支配解。

Step 5: 存儲記憶庫:選擇優良個體,保存到記憶庫中。

Step 6: 更新:更新記憶庫和種群。

Step 7: 判斷是否滿足迭代條件,如果不滿足,進入Step 2,否則退出迭代。

相對于與面向數值解問題的進化算法,協同進化算法在產生染色體之后,需要檢查染色體是否具有連通性,如果產生的染色體不具有從目標覆蓋節點到數據處理中心的數據鏈路,即將該染色體作為非可行解,重新生成染色體。同時為了防止進化算法的退化,采用協同機制,只有可行解在t時刻的適應度(覆蓋能耗、傳輸能耗(式(1))和時延(式(2)))超過t-1時刻的適應度時,才替換原有的染色體。

2.1 目標函數

目標覆蓋和數據傳輸的目標函數如式(5)和(6)所示,其中式(5)主要包括目標覆蓋的能耗;式(6)包括網絡傳輸能耗和數據傳輸時延,其中網絡傳輸能耗的優先級高于網絡傳輸時延,因此,將網絡時延作為式(6)的一個約束條件。在協同進化算法中,目標覆蓋能耗(5)的優先級高于數據傳輸(6),在染色體中包含目標覆蓋和數據傳輸可行解,目標覆蓋解是數據傳輸解的支配解。

(5)

wherexij=0,1(xij=1if?si∈Sj)

tj=Δt,ei=si(Esen·d·Δt)

(6)

wherexij=0,1(xij=1if?si∈Uj)

tj=Δt,ei=si(2Eelec·kd+εampkd2)

minimize(D(s0,sk))ti

2.2 種群初始化

種群初始化首先需要建立網絡路徑的編碼規則,由于路徑選擇問題中,不同路徑的長度會存在差異,我們選擇字符串編碼。在初始化過程中,種群中染色體的個數為30,每個染色體代表一個解,需要判斷解是否是可行解,即染色體是否具有可達性,如果是非可行解,丟棄解,重新初始化,直到獲得可行解。

2.3 染色體選擇

在獲得可行解的種群之后,為了進一步進行解得雜交,需要選擇不同的染色體,根據目標函數(5)和(6),我們采用輪盤賭策略選擇染色體,對種群中的可行解進行評價。

(7)

染色體的適應度包括解的目標覆蓋能耗、路由能耗和網絡時延,其中目標覆蓋能耗的優先級高于路由能耗,路由能耗優先級高于網絡時延,p(i)表示每個染色體被選擇的概率,適應度較高的染色體被選中的概率較大,被選中的染色體(Best)個數為偶數,以滿足雜交操作的要求。

2.4 雜交和變異

在完成染色體的選擇之后,對染色體進行雜交,兩個染色體進行配對,然后在隨機的位點斷裂,相關交換各自的染色體片段。在進化算法中,雜交率一般設定為0.7～0.8范圍。在完成染色體的雜交之后,可行解的隨機位點發生變異,染色體的變異率為0.01。

2.5 協同進化

為了保證協同進化算法的收斂,防止子個體在下一次篩選過程中的退化,采用協同進化機制,將函數適應度較高的個體保存到記憶庫(Memorypool)中。

3 實驗與分析

本文首先對目標覆蓋問題進行實驗,實驗平臺是MATLAB7.0,IntelCore2 3.0GHz,傳感器節點數據為25、35、45、55和65個,傳感器節點位置符合二維均勻分布,目標節點為5、10、15個,Esen=5μJ/bit,k=10kbyte,仿真場景為300m×300m。

3.1 目標覆蓋

圖5顯示節點感知范圍Srange=40時,傳感器節點從25到65時,網絡生存期與目標覆蓋的關系。隨著覆蓋目標的增多,覆蓋節點的生存期逐漸減少。在傳感器節點為55和65時,10個目標和15個目標的網絡生存期較為接近,分別相差4小時和5小時,主要是由于能夠覆蓋目標的傳感器數量較為接近。圖6顯示不同感應距離SR對覆蓋節點生存期的影響,當SR=60時,覆蓋節點的生存期最長,SR=40時,覆蓋節點的生存期最短。網絡生存期與感應距離的關系是隨著節點感應距離的增大,覆蓋節點的生存期逐漸增加。

圖5 目標覆蓋節點生存期

圖6 目標覆蓋集合示意圖

3.2 路徑分配

在路徑選擇中,針對不同數量目標m=5,m=10和m=15開展分析,節點間的通訊范圍UR=60,節點的數據傳輸系數、天線的功率放大系數、初始電量、數據排隊時延、廣播時延以及處理時延如表1所示。

表1 無線傳感器網絡的傳輸系數

圖7顯示了25個傳感器節點、5個目標覆蓋和數據傳輸的過程,在第一時間段,目標覆蓋算法選擇節點(3,5)構成覆蓋集,覆蓋5個目標,然后通過數據鏈路將目標狀態傳輸到Sink節點,隨著(3,5)節點電量的不斷下降,覆蓋節點由(3,5)節點轉變為(1,2,6)節點,目標覆蓋算法不斷進行覆蓋集的調度,延長目標覆蓋時間。

圖7 路徑分配(5個目標)

在完成目標覆蓋之后,需要將目標的狀態信息傳輸到Sink節點,通過協同進化算法選擇傳輸能耗、傳輸時延較小的路徑,傳輸能耗目標相對傳輸時延是支配集,即傳輸能耗的優先級高于傳輸時延。協同進化算法的雜交率為0.75,變異率為0.01,為了防止解的退化,采用記憶機制,保留優良個體。圖8顯示在切換目標覆蓋節點之后,利用協同進化算法計算的新的目標傳輸路徑。

圖8 路徑分配(5個目標)

圖9 路徑選擇的收斂趨勢(65個節點)

針對不同數量(5、10、15)目標,選擇不同節點數量(25、35、45、55、65)的傳感器網絡進行網絡生存期、網絡實驗的測試。圖9顯示了65個節點、15個目標條件下,協同進化算法的收斂情況,在2 500次迭代之后,數據的傳輸路徑逐漸收斂到最優路徑。

圖10是不同節點數量的無線傳感器網絡的生存周期變化趨勢圖。網絡的能耗隨著節點數量的增加而延長,當目標數量為5時,網絡的生存周期要高于目標數量為10和15時的生存期。圖11顯示了網絡數據傳輸時延的變化趨勢,節點數量從25增加到65時,網絡的傳輸時延逐漸增加,主要是由于節點數量增長會造成傳輸路徑的長度增加,進而造成了時延。同時為了驗證本文算法對網絡生存期和能耗的優化效果,將貪心-協同進化算法與ILP-協同進化算法進行對比,其中目標數量m=10,通訊范圍UR=60,圖12顯示兩種算法對網絡生存期的影響趨勢,采用貪心-協同進化算法優化后網絡生存期要長于ILP-協同進化算法。

圖10 網絡生存期(25節點到65個節點)

圖11 網絡時延變化趨勢

圖12 兩種算法的網絡生存期對比

4 結論

本文提出了一個基于協同進化策略的無線傳感器網絡目標覆蓋和路由選擇算法。網絡的生存期和網絡傳輸延時實驗結果表明,通過設定不同的感知范圍和通信距離,可以延長網絡的生存期,究其原因是感知范圍和通信距離的擴大可以增加目標覆蓋和數據傳輸節點的數量,進而增大網絡的生存期。在數據傳輸中實驗中,本文僅考慮固定Sink節點和數據的情況,在下一步工作中,通過引入時變數據和可變Sink節點,分析網絡能耗的變化和數據傳輸時延。

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al. Wireless Sensor Networks:A Survey[J]. Compututer Network,2002,38(4):393-422.

[2] Cardei M,Wu J. Energy-Efficient Coverage Problems in Wireless Ad-hoc Sensor Networks[J]. Computer Communications,2006,29(4):413-420.

[3] Zorbas D,Glynos D,Kotzanikolaou P,et al. Solving Coverage Problems in Wireless Sensor Networks Using Cover Sets[J]. Ad Hoc Networks,2010,8(4):400-415.

[4] Chaudhry S B,Hung V C,Guha R K,et al. Pareto-Based Evolutionary Computational Approach for Wireless Sensor Placement[J]. Engineering Applications of Artificial Intelligence,2011,24(3):409-425.

[5] 林祝亮,馮遠靜,俞立. 無線傳感網絡覆蓋的粒子進化優化策略研究[J]. 傳感技術學報,2009,22(6):873-877.

[6] 顧曉燕,孫力娟,郭劍. 一種無線傳感器網絡覆蓋能耗平衡優化策略[J]. 傳感技術學報,2010,23(11):1627-1632.

[7] Sengupta S,Das S,Nasir M,et al. An Evolutionary Multiobjective Sleep-Scheduling Scheme for Differentiated Coverage in Wireless Sensor Networks[J]. Systems,Man,and Cybernetics,Part C:Applications and Reviews,IEEE Transactions on,2012,42(6):1093-1102.

[8] Fonoage M,Cardei M,Ambrose A. A QoS Based Routing Protocol for Wireless Sensor Networks[C]//Performance Computing and Communications Conference(IPCCC),2010 IEEE 29th International. IEEE,2010:122-129.

[9] Heinzelman W R,Chandrakasan A,Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//System Sciences,Proceedings of the 33rd Annual Hawaii International Conference on.IEEE,2000,2:10-17.

[10] Deng J. Multi-hop/Direct Forwarding(MDF)for Static Wireless Sensor Networks[J]. ACM Trans Sens Netw,2009,5(4):1-25.

[11] Jin W,Jinsung C,Sungyoung L,et al. Hop-Based Energy Aware Routing Algorithm for Wireless Sensor Networks[J]. IEICE Transactions on Communications,2010,93(2):305-316.

[12] 侯惠峰,劉湘雯,于宏毅. 一種基于地理位置信息的無線傳感器網最小能耗路由算法[J]. 電子與信息學報,2007(1):177-181.

[13] Marta M,Cardei M. Improved Sensor Network Lifetime with Multiple Mobile Sinks[J]. Pervasive and Mobile Computing,2009,5(5):542-555.

[14] Olariu S,Stojmenovic I. Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting[C]//INFOCOM,2006:1-12.

[15] 彭鐸,黎鎖平,楊喜娟. 一種能量高效的無線傳感器網絡非均勻分簇路由協議[J]. 傳感技術學報,2014,27(12):1687-1691.

[16] 馮亞超,賀康,楊紅麗. 一種無線傳感器網絡數據收集協議的研究與優化[J]. 傳感技術學報,2014,27(3):355-360.

[17] Akhtar A M,Nakhai M R,Aghvami A H. Power Aware Cooperative Routing in Wireless Mesh Networks[J]. Communications Letters,IEEE,2012,16(5):670-673.

陸星家(1979-),男,工學博士,寧波工程學院理學院講師,美國俄亥俄州立大學(OSU)訪問學者,主要研究方向為無線傳感器網絡,數據挖掘等,shlxj800@gmail.com;

陳志榮(1981-),女,理學博士,寧波工程學院理學院副教授,澳大利亞科廷大學訪問學者,主要研究方向為智能系統,智能決策與分析,地理信息系統等,chenzr29@gmail.com。

Research of Energy Efficient Target Coverage and RoutingAssignment in Wireless Sensor Networks*

LUXingjia*,CHENZhirong

(School of Science,NingBo University of Technology,Ningbo Zhejiang 315211,China)

Due to the shortage of the existing target coverage algorithms in Wireless Sensor Networks(WSNs),it doesn’t consider the relationship between routing assignment,energy efficiency and target coverage. However,the robust algorithm doesn’t exist that considers the energy efficient routing assignment of WSNs dominated by targets coverage. We propose an energy efficient algorithm for target coverage and routing assignment that satisfy all the targets are covered completely. First,the maximum sets cover was constructed based on greedy heuristic strategy. Then,the proposed algorithm obtained the optimal path based on different cover sets and performed the co-evolution through operators such as fitness evaluation,wheel roulette,crossover,mutation,and memory mechanism. The lifetime and time delay of WSNs are also evaluated. The results showed that our algorithm extended the lifetime and decrease the time delay of WSNs.

wireless sensor networks;targets cover;routing assignment;energy efficiency;maximum set cover algorithm;Co-evolutionary mechanism

項目來源:國家自然科學基金項目(40901241);浙江省哲學社會科學規劃基金項目(15NDJC077YB);寧波市軟科學項目(2014A10013);浙江省公益技術應用研究計劃項目(2015C31154)

C:6150P

10.3969/j.issn.1004-1699.2015.06.021

TP393.1

A

1004-1699(2015)06-0900-07

2015-02-07 修改日期:2015-05-12