能耗約束的無線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋和路由分配研究*

陸星家,陳志榮

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

?

能耗約束的無線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋和路由分配研究*

陸星家*,陳志榮

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

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

無線傳感器網(wǎng)絡(luò);目標(biāo)覆蓋;路由分配;能耗約束;最大集合覆蓋算法;協(xié)同進化機制

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

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

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

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

本文針對節(jié)點感知距離可調(diào)的無線傳感器網(wǎng)絡(luò),提出一種基于協(xié)同進化算法,利用相交集覆蓋目標(biāo),平衡目標(biāo)覆蓋和數(shù)據(jù)傳輸?shù)墓?jié)點能耗。首先通過相交集覆蓋目標(biāo),通過貪心算法優(yōu)化覆蓋集的調(diào)度,提高節(jié)點的電量利用率和目標(biāo)覆蓋質(zhì)量;然后在保證目標(biāo)覆蓋的前提下,利用協(xié)同進化算法優(yōu)化數(shù)據(jù)傳輸路徑和網(wǎng)絡(luò)時延,進一步減少傳輸節(jié)點的能耗,降低網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)壽命。

1 目標(biāo)覆蓋

目標(biāo)覆蓋,即尋找最優(yōu)的目標(biāo)覆蓋組合,通過調(diào)度不同相交集或不相交集,延長網(wǎng)絡(luò)的生存周期。在目標(biāo)覆蓋中,由于節(jié)點直接覆蓋目標(biāo),因此可以忽略目標(biāo)覆蓋過程的數(shù)據(jù)傳輸時延。

1.1 節(jié)點定義

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

圖1 無線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋

圖1中有3個傳感器節(jié)點和10個需要覆蓋的目標(biāo)。S1號節(jié)點在第一時間段覆蓋10個目標(biāo),如果下一時間段是S2號節(jié)點,或者S3號節(jié)點覆蓋10個目標(biāo),則構(gòu)成一個非相交覆蓋集;如果下一時間段是S1號、S3號節(jié)點覆蓋,則產(chǎn)生相交覆蓋集。在S1號節(jié)點覆蓋10個目標(biāo)時,S2號、S3號節(jié)點處于休眠狀態(tài),功耗可以忽略。圖2顯示3個節(jié)點的通信過程,2號節(jié)點發(fā)送數(shù)據(jù)包,1號節(jié)點和3號節(jié)點接受數(shù)據(jù)包,3號節(jié)點接收到數(shù)據(jù)包之后,繼續(xù)廣播發(fā)送數(shù)據(jù)。1號節(jié)點如果在廣播范圍內(nèi)沒有后續(xù)節(jié)點,將不轉(zhuǎn)發(fā)數(shù)據(jù)包。

圖2 無線傳感器網(wǎng)絡(luò)的節(jié)點通信

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

(1)

定義2 網(wǎng)絡(luò)傳輸時延模型,D(s0,si)表示從s0節(jié)點傳輸?shù)絪i節(jié)點的時間延遲。主要包括每個節(jié)點在傳輸數(shù)據(jù)時的數(shù)據(jù)排隊延時dq,傳輸延遲dt和廣播延遲dp,n(s0,si)表示數(shù)據(jù)傳輸起始節(jié)點s0到數(shù)據(jù)處理節(jié)點si的轉(zhuǎn)發(fā)跳數(shù)。

(2)

1.2 最大覆蓋集

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

(3)

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

由于在式(3)沒有明確的最小時間間隔,我們在式(3)中引入最小時間間隔Δt,即目標(biāo)覆蓋的最短時間單位,同時引入節(jié)點能耗si(e),式(3)轉(zhuǎn)變?yōu)槭?4)。

(4)

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

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

目標(biāo)覆蓋即保證網(wǎng)絡(luò)中所有目標(biāo)都能夠被傳感器節(jié)點覆蓋。

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

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

算法1 覆蓋集算法

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

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

獲取目標(biāo)和節(jié)點之間的距離矩陣

構(gòu)建 完全覆蓋集合ck,并將ck添加到C中

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

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

算法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的區(qū)域內(nèi),10個Sensor和10個目標(biāo)被隨機部署,每個傳感器節(jié)點的初始電量為100mAh,Esen=0.000 5,Δt的最小切換時間間隔為分鐘。通過最大集合覆蓋算法可以獲得9個覆蓋集,其中包含2個相交覆蓋集合7個非相交覆蓋集。

圖4顯示在9個覆蓋集中,覆蓋集的調(diào)用次序是{{s2},{s6},{s4},{s2,s7,s8},{s9},{s1,s2,s7},{s5},{s10},{s7}},當(dāng)十個傳感器節(jié)點的電量完全耗盡時,網(wǎng)絡(luò)的生存周期是258h。

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

圖4 10個傳感器節(jié)點覆蓋能耗變化圖

2 多路徑分配

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

算法3 協(xié)同進化算法

輸入: Ppop:產(chǎn)生初始種群

PGen:迭代次數(shù)

PC:設(shè)定解的上界和下界

Step 1: 染色體初始化:產(chǎn)生解。

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

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

Step 4: 通過目標(biāo)函數(shù)的評價,獲取支配解。

Step 5: 存儲記憶庫:選擇優(yōu)良個體,保存到記憶庫中。

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

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

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

2.1 目標(biāo)函數(shù)

目標(biāo)覆蓋和數(shù)據(jù)傳輸?shù)哪繕?biāo)函數(shù)如式(5)和(6)所示,其中式(5)主要包括目標(biāo)覆蓋的能耗;式(6)包括網(wǎng)絡(luò)傳輸能耗和數(shù)據(jù)傳輸時延,其中網(wǎng)絡(luò)傳輸能耗的優(yōu)先級高于網(wǎng)絡(luò)傳輸時延,因此,將網(wǎng)絡(luò)時延作為式(6)的一個約束條件。在協(xié)同進化算法中,目標(biāo)覆蓋能耗(5)的優(yōu)先級高于數(shù)據(jù)傳輸(6),在染色體中包含目標(biāo)覆蓋和數(shù)據(jù)傳輸可行解,目標(biāo)覆蓋解是數(shù)據(jù)傳輸解的支配解。

(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 種群初始化

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

2.3 染色體選擇

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

(7)

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

2.4 雜交和變異

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

2.5 協(xié)同進化

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

3 實驗與分析

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

3.1 目標(biāo)覆蓋

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

圖5 目標(biāo)覆蓋節(jié)點生存期

圖6 目標(biāo)覆蓋集合示意圖

3.2 路徑分配

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

表1 無線傳感器網(wǎng)絡(luò)的傳輸系數(shù)

圖7顯示了25個傳感器節(jié)點、5個目標(biāo)覆蓋和數(shù)據(jù)傳輸?shù)倪^程,在第一時間段,目標(biāo)覆蓋算法選擇節(jié)點(3,5)構(gòu)成覆蓋集,覆蓋5個目標(biāo),然后通過數(shù)據(jù)鏈路將目標(biāo)狀態(tài)傳輸?shù)絊ink節(jié)點,隨著(3,5)節(jié)點電量的不斷下降,覆蓋節(jié)點由(3,5)節(jié)點轉(zhuǎn)變?yōu)?1,2,6)節(jié)點,目標(biāo)覆蓋算法不斷進行覆蓋集的調(diào)度,延長目標(biāo)覆蓋時間。

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

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

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

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

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

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

圖10 網(wǎng)絡(luò)生存期(25節(jié)點到65個節(jié)點)

圖11 網(wǎng)絡(luò)時延變化趨勢

圖12 兩種算法的網(wǎng)絡(luò)生存期對比

4 結(jié)論

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

[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] 林祝亮,馮遠(yuǎn)靜,俞立. 無線傳感網(wǎng)絡(luò)覆蓋的粒子進化優(yōu)化策略研究[J]. 傳感技術(shù)學(xué)報,2009,22(6):873-877.

[6] 顧曉燕,孫力娟,郭劍. 一種無線傳感器網(wǎng)絡(luò)覆蓋能耗平衡優(yōu)化策略[J]. 傳感技術(shù)學(xué)報,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] 侯惠峰,劉湘雯,于宏毅. 一種基于地理位置信息的無線傳感器網(wǎng)最小能耗路由算法[J]. 電子與信息學(xué)報,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] 彭鐸,黎鎖平,楊喜娟. 一種能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 傳感技術(shù)學(xué)報,2014,27(12):1687-1691.

[16] 馮亞超,賀康,楊紅麗. 一種無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議的研究與優(yōu)化[J]. 傳感技術(shù)學(xué)報,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-),男,工學(xué)博士,寧波工程學(xué)院理學(xué)院講師,美國俄亥俄州立大學(xué)(OSU)訪問學(xué)者,主要研究方向為無線傳感器網(wǎng)絡(luò),數(shù)據(jù)挖掘等,shlxj800@gmail.com;

陳志榮(1981-),女,理學(xué)博士,寧波工程學(xué)院理學(xué)院副教授,澳大利亞科廷大學(xué)訪問學(xué)者,主要研究方向為智能系統(tǒng),智能決策與分析,地理信息系統(tǒng)等,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

項目來源:國家自然科學(xué)基金項目(40901241);浙江省哲學(xué)社會科學(xué)規(guī)劃基金項目(15NDJC077YB);寧波市軟科學(xué)項目(2014A10013);浙江省公益技術(shù)應(yīng)用研究計劃項目(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