WSNs中一種尋找最小工作節(jié)點(diǎn)集的覆蓋算法

王愛民,劉永強(qiáng),張 婧,劉衍珩

(1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林長(zhǎng)春 130012; 2.吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,吉林長(zhǎng)春 130012)

WSNs中一種尋找最小工作節(jié)點(diǎn)集的覆蓋算法

王愛民1,2,劉永強(qiáng)1,張 婧1,劉衍珩1,2

(1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林長(zhǎng)春 130012; 2.吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,吉林長(zhǎng)春 130012)

針對(duì)現(xiàn)有覆蓋算法存在的很多冗余節(jié)點(diǎn),提出了尋找最小工作節(jié)點(diǎn)集的覆蓋算法.該算法分為兩個(gè)階段:第1階段運(yùn)行已有的覆蓋算法;第2階段運(yùn)行節(jié)點(diǎn)替換算法,它用更少的節(jié)點(diǎn)替換更多的工作節(jié)點(diǎn),如此循環(huán)迭代使工作節(jié)點(diǎn)數(shù)不斷減少.仿真實(shí)驗(yàn)表明,該算法比其他覆蓋算法能獲得更多的休眠節(jié)點(diǎn),使工作節(jié)點(diǎn)數(shù)減少10%左右,從而延長(zhǎng)了網(wǎng)絡(luò)生命周期.

無線傳感器網(wǎng)絡(luò);覆蓋;睡眠調(diào)度算法;休眠順序

傳感器技術(shù)、微機(jī)電系統(tǒng)、現(xiàn)代網(wǎng)絡(luò)和無線通信等技術(shù)的進(jìn)步,推動(dòng)了無線傳感器網(wǎng)絡(luò)的產(chǎn)生和發(fā)展.無線傳感器網(wǎng)絡(luò)能應(yīng)用于軍事國(guó)防、環(huán)境監(jiān)測(cè)、醫(yī)療護(hù)理和危險(xiǎn)區(qū)域遠(yuǎn)程控制等諸多領(lǐng)域[1-2],在大多數(shù)應(yīng)用場(chǎng)景中節(jié)點(diǎn)都是隨機(jī)部署的,這樣會(huì)導(dǎo)致部署的節(jié)點(diǎn)數(shù)遠(yuǎn)大于所需的節(jié)點(diǎn)數(shù),當(dāng)這些節(jié)點(diǎn)都工作時(shí),將會(huì)存在大量的冗余節(jié)點(diǎn),如果不對(duì)這些節(jié)點(diǎn)進(jìn)行休眠調(diào)度,不僅增加了整體能量的消耗,還增加了數(shù)據(jù)的沖突.為此,人們已經(jīng)在這方面進(jìn)行了大量的研究[3-12].文獻(xiàn)[6]提出的算法把區(qū)域劃分成方格,1個(gè)方格只有1個(gè)節(jié)點(diǎn)工作,該算法并沒有考慮到網(wǎng)絡(luò)覆蓋的問題.文獻(xiàn)[7]提出了滿足覆蓋的休眠調(diào)度的Ottawa算法,該算法通過扇形來計(jì)算鄰居節(jié)點(diǎn)對(duì)1個(gè)節(jié)點(diǎn)的覆蓋,由于只考慮了節(jié)點(diǎn)感知區(qū)域內(nèi)的鄰居節(jié)點(diǎn),所以該算法并沒有判斷出所有的冗余節(jié)點(diǎn).文獻(xiàn)[8]改進(jìn)了文獻(xiàn)[7]提出的算法,對(duì)覆蓋進(jìn)行了更精確的計(jì)算.文獻(xiàn)[9]提出了覆蓋配置協(xié)議(Coverage Configuration Protocol,CCP)算法,該算法判斷冗余節(jié)點(diǎn)的方法是通過判斷節(jié)點(diǎn)感知區(qū)域內(nèi)所有交點(diǎn)的覆蓋度是否都大于K.該算法在部署節(jié)點(diǎn)較多時(shí)不會(huì)產(chǎn)生盲點(diǎn).文獻(xiàn)[10]提出的算法對(duì)周邊界覆蓋給出了充要條件,得出更精確的結(jié)果.文獻(xiàn)[11]提出的算法,首先基于歐拉距離選出能全覆蓋整個(gè)監(jiān)測(cè)區(qū)域的節(jié)點(diǎn)集,然后選擇離每個(gè)節(jié)點(diǎn)最近的K-1個(gè)節(jié)點(diǎn)來滿足K覆蓋.文獻(xiàn)[12]提出了基于虛擬正方形網(wǎng)格的覆蓋算法(Virtual Square Grid-based Coverage Algorithm,VSGCA),該算法把每個(gè)節(jié)點(diǎn)的感知區(qū)域劃分成小方格,然后計(jì)算每個(gè)鄰居節(jié)點(diǎn)對(duì)這些小方格的覆蓋.該算法雖然在休眠節(jié)點(diǎn)數(shù)上沒有文獻(xiàn)[9]提出的算法好,但是它的復(fù)雜度比文獻(xiàn)[9]提出的算法低很多.

1　網(wǎng)絡(luò)模型和問題描述

1.1假設(shè)及定義

下面給出一些假設(shè)和定義.假設(shè)若干同構(gòu)節(jié)點(diǎn)隨機(jī)部署在L×W的區(qū)域A,節(jié)點(diǎn)的感知模型和通信模型都是圓形,且感知半徑R與通信半徑Rc滿足Rc≥2R(這樣在滿足覆蓋的同時(shí)也滿足連通[9]).

定義1 部署在區(qū)域A中的節(jié)點(diǎn)集合稱為節(jié)點(diǎn)集,即S={u1(x1,y1),u2(x2,y2),u3(x3,y3),…,uk(xk, yk),…}.

定義2 節(jié)點(diǎn)ui(xi,yi)的感知區(qū)域?yàn)辄c(diǎn)的集合,即D(ui)={p(x,y)∈A|(x-xi)2+(yyi)2≤R2}.

定義3 節(jié)點(diǎn)ui的鄰居節(jié)點(diǎn)集,即N(ui)={uj∈S|(xj-xi)2+(yj-yi)2≤

定義4 假休眠狀態(tài)節(jié)點(diǎn)指一個(gè)節(jié)點(diǎn)不執(zhí)行監(jiān)測(cè)任務(wù),但是能接收和發(fā)送消息,預(yù)休眠狀態(tài)和預(yù)工作狀態(tài)是狀態(tài)轉(zhuǎn)換中的兩個(gè)臨時(shí)狀態(tài),表示準(zhǔn)備休眠和工作的節(jié)點(diǎn),它們都能接收和發(fā)送消息.預(yù)休眠狀態(tài)是從工作狀態(tài)轉(zhuǎn)換過來的,而預(yù)工作狀態(tài)是從假休眠狀態(tài)轉(zhuǎn)換過來的.

1.2問題描述

上文介紹的覆蓋算法都能使大部分節(jié)點(diǎn)休眠,但是節(jié)點(diǎn)感知區(qū)域之間仍存在很多重疊區(qū)域,它們的平均覆蓋度都大于等于2.觀察其運(yùn)行結(jié)果,有些點(diǎn)的覆蓋度為1,有些點(diǎn)為2,有些點(diǎn)為3,甚至更大.有些區(qū)域1個(gè)節(jié)點(diǎn)就可以覆蓋,但是它們卻用了兩個(gè)或者更多的節(jié)點(diǎn)覆蓋,而且對(duì)相同的網(wǎng)絡(luò)拓?fù)?每次運(yùn)行生成的工作節(jié)點(diǎn)個(gè)數(shù)都不一樣,且差距很大.

假設(shè)在監(jiān)測(cè)區(qū)域中有一子區(qū)域如圖1所示,子區(qū)域A1,傳感器節(jié)點(diǎn)集S1(包括所有部署在區(qū)域邊界的邊界節(jié)點(diǎn),部署在區(qū)域中心的傳感器節(jié)點(diǎn)a,以及區(qū)域內(nèi)其他兩個(gè)傳感器節(jié)點(diǎn)b和c).要滿足子區(qū)域A1的全覆蓋,有兩種覆蓋方案:①全部的邊界節(jié)點(diǎn)及節(jié)點(diǎn)b和c;②全部的邊界節(jié)點(diǎn)及節(jié)點(diǎn)a.第1種方案比第2種方案的工作節(jié)點(diǎn)個(gè)數(shù)多1.由此可知,工作節(jié)點(diǎn)個(gè)數(shù)與節(jié)點(diǎn)的休眠順序有關(guān).若a節(jié)點(diǎn)先休眠,則b和c不能休眠;若b或者c先休眠,則a節(jié)點(diǎn)不能休眠.當(dāng)監(jiān)測(cè)區(qū)域非常大,且部署節(jié)點(diǎn)非常多時(shí),每次生成的工作節(jié)點(diǎn)個(gè)數(shù)都不一樣,且差距很大.文中提出的覆蓋算法解決了上述情況,使得每次運(yùn)行結(jié)果一樣,并且得到的工作節(jié)點(diǎn)個(gè)數(shù)也是最少的,工作節(jié)點(diǎn)個(gè)數(shù)能減少10%,且隨著監(jiān)測(cè)區(qū)域的擴(kuò)大和部署節(jié)點(diǎn)的增多,工作節(jié)點(diǎn)的個(gè)數(shù)減少得會(huì)越多.文中算法運(yùn)行于圖1拓?fù)浣Y(jié)構(gòu),得到的工作節(jié)點(diǎn)為所有的邊界節(jié)點(diǎn)和節(jié)點(diǎn)a.

圖1　節(jié)點(diǎn)部署圖

圖2　理想的節(jié)點(diǎn)部署圖

2　與休眠順序無關(guān)的覆蓋算法

2.1討 論

這里給出一種比較理想的節(jié)點(diǎn)部署情況.如圖2所示.4個(gè)圓(半徑為感知半徑的大小為R)相交于一點(diǎn),節(jié)點(diǎn)之間重疊的區(qū)域非常少,每個(gè)節(jié)點(diǎn)的覆蓋范圍可看做是一個(gè)正方形,邊長(zhǎng)為21/2R,這些節(jié)點(diǎn)的位置可表示為

定義5 若一個(gè)位置p(x,y)屬于C集合,則稱該點(diǎn)為最佳位置.

2.2算法描述

該算法由兩個(gè)階段組成,第1階段是運(yùn)行已有的覆蓋算法,獲得工作節(jié)點(diǎn)集;第2階段是對(duì)第1階段獲得的工作節(jié)點(diǎn)集進(jìn)行優(yōu)化處理,用更少的工作節(jié)點(diǎn)集替換它們.

2.2.1第1階段

該階段得到初始的工作節(jié)點(diǎn)集,可使用已提出的算法,由于CCP算法能得到較少的工作節(jié)點(diǎn),故使用CCP作為第1階段算法.在運(yùn)行該算法時(shí),所有應(yīng)該休眠的節(jié)點(diǎn)都進(jìn)入假休眠狀態(tài),在第2階段這些節(jié)點(diǎn)就能發(fā)送消息,并且能接收其他節(jié)點(diǎn)發(fā)送的消息.這樣當(dāng)?shù)?階段結(jié)束時(shí),所有的節(jié)點(diǎn)只有兩種狀態(tài):工作狀態(tài)或假休眠狀態(tài).

2.2.2第2階段

第2階段算法思想是先讓一個(gè)假休眠節(jié)點(diǎn)ui為暫時(shí)的工作節(jié)點(diǎn),然后計(jì)算有多少個(gè)工作節(jié)點(diǎn)可以休眠,若可以休眠的工作節(jié)點(diǎn)個(gè)數(shù)大于1,則讓該假休眠節(jié)點(diǎn)成為工作節(jié)點(diǎn),可以休眠的工作節(jié)點(diǎn)成為休眠節(jié)點(diǎn).若可以休眠的工作節(jié)點(diǎn)個(gè)數(shù)等于1,且該假休眠節(jié)點(diǎn)ui比可以休眠的工作節(jié)點(diǎn)更接近最佳位置(定義5),則讓該假休眠節(jié)點(diǎn)成為工作節(jié)點(diǎn),可以休眠的工作節(jié)點(diǎn)成為休眠節(jié)點(diǎn);否則,不讓假休眠節(jié)點(diǎn)ui成為工作節(jié)點(diǎn).

第2階段的詳細(xì)過程如下:

(1)開始時(shí),為避免消息發(fā)送沖突,每個(gè)假休眠節(jié)點(diǎn)ui都等待一段隨機(jī)時(shí)間;然后,發(fā)送測(cè)試消息,并修改自己的狀態(tài)為預(yù)工作狀態(tài),同時(shí)設(shè)定一個(gè)定時(shí)器.

(2)工作節(jié)點(diǎn)收到該消息時(shí),先判斷自己是否已經(jīng)收到其他假休眠節(jié)點(diǎn)發(fā)送的測(cè)試消息,如果收到,則拋棄該消息;否則,跳轉(zhuǎn)到下一步.其他狀態(tài)的節(jié)點(diǎn)接收到該消息都拋棄.

(3)保存發(fā)送節(jié)點(diǎn)ui的身份標(biāo)識(shí)號(hào)碼(IDentity,ID),在鄰居狀態(tài)表中把該鄰居節(jié)點(diǎn)ui的狀態(tài)改為預(yù)工作狀態(tài),然后運(yùn)行CCP覆蓋算法,若運(yùn)行結(jié)果為非冗余節(jié)點(diǎn),則不進(jìn)行任何處理;若為冗余節(jié)點(diǎn),則修改自己的狀態(tài)為預(yù)休眠狀態(tài),并向節(jié)點(diǎn)ui發(fā)送預(yù)休眠消息,表示自己可以休眠,然后跳轉(zhuǎn)到下一步.

(4)當(dāng)一個(gè)預(yù)工作節(jié)點(diǎn)ui(即剛才發(fā)送測(cè)試消息的節(jié)點(diǎn))收到預(yù)休眠消息時(shí),首先判斷該消息是否是發(fā)送給自己的,若是,則記錄該預(yù)休眠消息;若不是,則拋棄.循環(huán)處理這一步直到節(jié)點(diǎn)的定時(shí)器超時(shí),然后轉(zhuǎn)到下一步.

(5)預(yù)工作節(jié)點(diǎn)ui計(jì)算接收到的預(yù)休眠消息的個(gè)數(shù)為n,若n≥2,則轉(zhuǎn)步驟(6)處理;若n=1,設(shè)發(fā)送預(yù)休眠消息的節(jié)點(diǎn)為uj,則判斷自己ui和節(jié)點(diǎn)uj哪一個(gè)更接近最佳位置(定義5表示的);若ui更接近,則轉(zhuǎn)步驟(6)處理;否則,轉(zhuǎn)步驟(7)處理;若n=0,則轉(zhuǎn)步驟(7)處理.

(6)預(yù)工作節(jié)點(diǎn)ui向鄰居節(jié)點(diǎn)廣播確認(rèn)消息,表示此次測(cè)試成功,修改自己的狀態(tài)為工作狀態(tài),然后轉(zhuǎn)到步驟(8).

(7)預(yù)工作節(jié)點(diǎn)ui向鄰居節(jié)點(diǎn)廣播取消消息,表示此次測(cè)試失敗,把自己的狀態(tài)修改回假休眠狀態(tài),然后轉(zhuǎn)到步驟(8).

(8)當(dāng)一個(gè)預(yù)休眠或工作節(jié)點(diǎn)收到確認(rèn)消息時(shí),首先判斷發(fā)送該消息的節(jié)點(diǎn)ID是否是自己記錄的節(jié)點(diǎn)ID,若不是,則不進(jìn)行處理;若是,則判斷自己的狀態(tài),若為工作狀態(tài),則不進(jìn)行處理;若為預(yù)休眠狀態(tài),則修改自己的狀態(tài)為假休眠狀態(tài),并告知鄰居節(jié)點(diǎn)自己的狀態(tài).若一個(gè)預(yù)休眠或工作節(jié)點(diǎn)收到取消消息時(shí),同樣先判斷發(fā)送該消息的節(jié)點(diǎn)是否是自己記錄的節(jié)點(diǎn),若不是,則不進(jìn)行處理;若是,則判斷自己的狀態(tài);若為工作狀態(tài),不進(jìn)行處理;若為預(yù)休眠狀態(tài),則修改自己的狀態(tài)為工作狀態(tài),并告知鄰居節(jié)點(diǎn)自己的狀態(tài).

(9)至此,1次迭代過程完成,在一段時(shí)間后,則繼續(xù)以上步驟迭代,如此循環(huán),直到所指定的時(shí)間為止.最后把所有的假休眠節(jié)點(diǎn)的狀態(tài)改為休眠狀態(tài),整個(gè)算法結(jié)束.

在步驟(3)中,如果兩個(gè)鄰居節(jié)點(diǎn)同時(shí)判斷為冗余節(jié)點(diǎn),并且讓這兩個(gè)節(jié)點(diǎn)休眠,則有可能產(chǎn)生盲點(diǎn).因?yàn)槊總€(gè)節(jié)點(diǎn)在進(jìn)行冗余判斷時(shí)都假設(shè)對(duì)方是工作節(jié)點(diǎn).為解決這個(gè)問題,需在步驟(3)引入回退機(jī)制.該回退機(jī)制與CCP算法的回退機(jī)制相同.

2.3狀態(tài)轉(zhuǎn)換

圖3只列出了算法第2階段出現(xiàn)的狀態(tài),第1階段結(jié)束后節(jié)點(diǎn)只有兩種狀態(tài):工作狀態(tài)和假休眠狀態(tài).在第2階段節(jié)點(diǎn)的狀態(tài)有工作狀態(tài)、假休眠狀態(tài)、預(yù)工作狀態(tài)、預(yù)休眠狀態(tài)和休眠狀態(tài).當(dāng)算法結(jié)束時(shí),節(jié)點(diǎn)只有兩種狀態(tài):工作狀態(tài)和休眠狀態(tài).狀態(tài)轉(zhuǎn)換如圖3所示.

圖3　狀態(tài)轉(zhuǎn)換

2.4時(shí)間復(fù)雜度

文中算法是由兩階段組成的,第1階段運(yùn)行CCP算法,第2階段運(yùn)行節(jié)點(diǎn)替換算法.CCP算法的時(shí)間復(fù)雜度為O(n3)(n表示感知區(qū)域內(nèi)的鄰居節(jié)點(diǎn)數(shù))[9].在第2階段,對(duì)于工作節(jié)點(diǎn),當(dāng)它接收測(cè)試消息時(shí),使用CCP算法判斷自己是否為冗余節(jié)點(diǎn),由于此時(shí)網(wǎng)絡(luò)中的平均覆蓋度為一個(gè)常數(shù),與初始部署節(jié)點(diǎn)數(shù)無關(guān).所以,在節(jié)點(diǎn)的感知半徑不變的情況下,工作節(jié)點(diǎn)的鄰居工作節(jié)點(diǎn)數(shù)也為常數(shù),因此,1次冗余判斷的時(shí)間復(fù)雜度為O(1).又由于它有n個(gè)鄰居節(jié)點(diǎn),需要判斷n次,故工作節(jié)點(diǎn)在第2階段的時(shí)間復(fù)雜度為O(n),而假休眠節(jié)點(diǎn)在第2階段只是對(duì)接收信息的判斷及變量的設(shè)置,所以它的時(shí)間復(fù)雜度為O(n),故文中算法的時(shí)間復(fù)雜度為O(n3)).

3　實(shí)驗(yàn)結(jié)果及分析

這里使用仿真實(shí)驗(yàn)實(shí)現(xiàn)提出的無線傳感網(wǎng)尋找最小工作節(jié)點(diǎn)集(Finding the Minimum working sets in Wireless Sensor networks,FMWS)算法,并與其他算法(Ottawa算法、CCP算法和VSGCA算法)在工作節(jié)點(diǎn)數(shù)、覆蓋度和是否有盲點(diǎn)等方面進(jìn)行比較.實(shí)驗(yàn)中,假設(shè)監(jiān)測(cè)區(qū)域是150 m×150 m的矩形區(qū)域,節(jié)點(diǎn)的感知半徑為10 m,傳輸半徑為20 m.

3.1盲 點(diǎn)

衡量區(qū)域覆蓋算法一個(gè)主要的指標(biāo)是該算法是否產(chǎn)生盲點(diǎn).由于在文中算法的第2階段步驟(3)和步驟

(4)使用CCP算法來判斷節(jié)點(diǎn)是否為冗余節(jié)點(diǎn),當(dāng)部署節(jié)點(diǎn)很多時(shí),CCP算法不產(chǎn)生盲點(diǎn),所以當(dāng)部署節(jié)點(diǎn)比較多時(shí),文中提出的算法也不會(huì)產(chǎn)生盲點(diǎn).在圖4中,比較了不同算法產(chǎn)生的盲點(diǎn)數(shù).隨著部署節(jié)點(diǎn)的增加,盲點(diǎn)個(gè)數(shù)越來越少,當(dāng)部署節(jié)點(diǎn)數(shù)到達(dá)一定個(gè)數(shù)時(shí),所有算法都不產(chǎn)生盲點(diǎn).

圖4　算法的盲點(diǎn)數(shù)比較曲線圖

3.2工作節(jié)點(diǎn)

由于工作節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)生命期成反相關(guān)關(guān)系,在滿足覆蓋的情況下,工作的節(jié)點(diǎn)數(shù)越少,網(wǎng)絡(luò)生命期越長(zhǎng),故工作節(jié)點(diǎn)數(shù)能很好反映網(wǎng)絡(luò)生命期.在圖5中顯示了工作節(jié)點(diǎn)數(shù)與部署節(jié)點(diǎn)數(shù)的關(guān)系,該實(shí)驗(yàn)要求的覆蓋度為1,可看出,文中算法生成的工作節(jié)點(diǎn)數(shù)比其他算法的都要少,其中,Ottawa算法產(chǎn)生的工作節(jié)點(diǎn)數(shù)大概是其他算法的3倍多,而且隨著部署節(jié)點(diǎn)數(shù)的增多,工作節(jié)點(diǎn)數(shù)不斷增多,而其他算法產(chǎn)生的工作節(jié)點(diǎn)數(shù)保持在一定范圍不變.觀察文中算法產(chǎn)生的工作節(jié)點(diǎn)數(shù)可知,隨著部署節(jié)點(diǎn)不斷增多,工作節(jié)點(diǎn)數(shù)則不斷減少.為更精確地比較文中算法與CCP算法生成的工作節(jié)點(diǎn)數(shù),表1顯示了這兩個(gè)算法產(chǎn)生的工作節(jié)點(diǎn)個(gè)數(shù).從表1可知,文中算法產(chǎn)生的工作節(jié)點(diǎn)數(shù)比CCP算法大概少10%左右,而且隨著部署節(jié)點(diǎn)個(gè)數(shù)的增加,文中算法產(chǎn)生的工作節(jié)點(diǎn)數(shù)不斷減少.分析文中算法可知,部署節(jié)點(diǎn)越多,在最佳位置的節(jié)點(diǎn)越多,生成的工作節(jié)點(diǎn)感知區(qū)域重疊越少,所以工作節(jié)點(diǎn)數(shù)就越少.當(dāng)部署節(jié)點(diǎn)無限多時(shí),文中算法產(chǎn)生的節(jié)點(diǎn)數(shù)則達(dá)到圖2所示的比較理想的情況.

3.3平均覆蓋度

圖6比較了各算法的平均覆蓋度.顯示了在部署節(jié)點(diǎn)個(gè)數(shù)不同情況下各算法的平均覆蓋度,部署節(jié)點(diǎn)個(gè)數(shù)從350依次遞增到800.除Ottawa算法的平均覆蓋度在不斷增長(zhǎng)外,其他算法的平均覆蓋度在2.0左右.還能看到,文中算法的平均覆蓋度在不同的部署節(jié)點(diǎn)下都比其他算法要低,并且隨著部署節(jié)點(diǎn)的不斷增多,平均覆蓋度在不斷減小.當(dāng)部署節(jié)點(diǎn)很多時(shí),文中算法要優(yōu)于其他算法.

表1　工作節(jié)點(diǎn)

圖5　算法的工作節(jié)點(diǎn)數(shù)比較曲線圖

圖6　算法的平均覆蓋度比較曲線圖

4　結(jié)束語

筆者提出了尋找最小工作節(jié)點(diǎn)集的覆蓋算法,該算法包括兩階段:第1階段可以運(yùn)行任一覆蓋算法,文中選擇CCP算法作為第1階段運(yùn)行的算法,在第1階段運(yùn)行完以后節(jié)點(diǎn)只有兩種狀態(tài):工作節(jié)點(diǎn)狀態(tài)和假休眠節(jié)點(diǎn)狀態(tài).在第2階段對(duì)工作節(jié)點(diǎn)進(jìn)行替換,它通過循環(huán)迭代使工作節(jié)點(diǎn)數(shù)不斷減少.這樣文中算法得到的工作節(jié)點(diǎn)數(shù)不比第1階段工作節(jié)點(diǎn)數(shù)多.由實(shí)驗(yàn)可知,文中算法在工作節(jié)點(diǎn)數(shù)及平均覆蓋度方面都要優(yōu)于其他算法,且隨著部署節(jié)點(diǎn)的增多,工作節(jié)點(diǎn)及平均覆蓋度在不斷趨近于理想情況.雖然文中算法能得到更少的工作節(jié)點(diǎn)數(shù),但是還沒有達(dá)到最理想情況,特別是在部署節(jié)點(diǎn)少的情況下.下一步將對(duì)該覆蓋算法作進(jìn)一步的研究,提出一個(gè)在部署節(jié)點(diǎn)不是很多的情況下能產(chǎn)生更少工作節(jié)點(diǎn)數(shù)的算法,讓更多的節(jié)點(diǎn)休眠,最大限度地延長(zhǎng)網(wǎng)絡(luò)生命周期.

[1]ALI R A,HOSSEIN Y M,MASOUD R A.Optimized Congestion Management Protocol for Healthcare Wireless Sensor Networks[J].Wireless Personal Communications,2014,75(1):11-34.

[2]GHASEMIGOL M,GHAEMI-BAFGHI A,YAGHMAEE-MOGHADDAM M H,et al.Anomaly Detection and Foresight Response Strategy for Wireless Sensor Networks[J].Wireless Networks,2015,21(5):1425-1442.

[3]ANJU S,PAL S R.Survey on Coverage Problems in Wireless Sensor Networks[J].Wireless Personal Communications,2015,80(4):1475-1500.

[4]齊小剛,陸贊贊,鄭耿忠,等.一種低能耗低時(shí)延的睡眠調(diào)度算法[J].西安電子科技大學(xué)學(xué)報(bào),2015,42(1): 124-129. QI Xiaogan,LU Zanzan,ZHENG Gengzhong,et al.Low-power and Low-delay Sheep Scheduling Algorithm Based on the Data Aggregation Tree[J].Journal of Xidian University,2015,42(1):124-129.

[5]KHAN J A,QURESHI H K,IQBAL A.Energy Management in Wireless Sensor Networks:a Survey[J].Computers &Electrical Engineering,2015,41:159-176.

[6]XU Y,HEIDEMANN J,ESTRIN D.Geography-informed Energy Conservation for Ad Hoc Routing[C]//Proceedings of the Annual International Conferece on Mobile Computing and Networking.New York:ACM,2001:70-84.

[7]TIAN D,GEORGANAS N D.A Coverage-preserving Node Scheduling Scheme for Large Wireless Sensor Networks [C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.New York:ACM,2002:32-41.

[8]BOUKERCHE A,FEI X,ARAUJO R B.An Optimal Coverage-preserving Scheme for Wireless Sensor Networks Based on Local Information Exchange[J].Computer Communications,2007,30(14):2708-2720.

[9]XING G L,WANG X R,ZHANG Y F,et al.Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J].ACM Transactions on Sensor Networks,2005,1(1):36-72.

[10]LIU Y H,PU J H,ZHANG S,et al.A Localized Coverage Preserving Protocol for Wireless Sensor Networks[J]. Sensors,2009,9(1):281-302.

[11]YU J G,DENG X,YU D X,et al.CWSC:Connected k-coverage Working Sets Construction Algorithm in Wireless Sensor Networks[J].AEU-International Journal of Electronics and Communications,2013,67(11):937-946

[12]LIU Y H,SUO L X,SUN D Y,et al.A Virtual Square Grid-based Coverage Algorithm of Redundant Node for Wireless Sensor Network[J].Journal of Network and Computer Applications,2013,36(2):811-817.

(編輯:齊淑娟)

Coverage algorithm for finding the minimum working sets in WSNs

WANG Aimin1,2,LIU Yongqiang1,ZHANG Jing1,LIU Yanheng1,2
(1.College of Computer Science and Technology,Jilin Univ.,Changchun 130012,China;2.Key Lab. of Symbolic Computation and Knowledge Engineering of Ministry of Edu.,Jilin Univ.,Changchun 130012,China)

Since the existing coverage algorithm has a lot of redundant nodes,a coverage algorithm for finding the minimum working sets in WSNs(FMWS)is proposed.The algorithm is divided into two phases:the first phase runs an existing coverage algorithm;the second phase runs an algorithm that uses fewer working nodes to replace more working nodes,with the number of working nodes continuously decreasing through iteration. Simulation shows that the proposed algorithm can obtain more sleep nodes than other algorithms.It can make the number of working nodes reduce around 10%,so as to prolong the network life.

wireless sensor networks;coverage;sleep scheduling;sleep order

TP393

A

1001-2400(2016)04-0141-06

10.3969/j.issn.1001-2400.2016.04.025

2015-04-13 網(wǎng)絡(luò)出版時(shí)間：2015-10-21

國(guó)家自然科學(xué)基金資助項(xiàng)目(61073164)

王愛民(1970-),男,副教授,博士,E-mail:wangam@jlu.edu.cn.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.050.html