基于加權(quán)的無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化覆蓋算法

張 品，沈 政，董志遠(yuǎn)，鄭 立

(杭州電子科技大學(xué)通信工程學(xué)院，杭州310018)

無(wú)線傳感器網(wǎng)絡(luò)覆蓋［1－2］是指在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量、無(wú)線網(wǎng)絡(luò)通信帶寬、網(wǎng)絡(luò)計(jì)算處理能力等資源普遍受限的情況下，通過(guò)具有感知能力的節(jié)點(diǎn)的位置分布和節(jié)點(diǎn)調(diào)度，使感知、監(jiān)視、傳感、通信等各種服務(wù)質(zhì)量得到提高，最終使無(wú)線傳感器網(wǎng)絡(luò)資源得到優(yōu)化分配［3］。但由于實(shí)際應(yīng)用的特殊性，傳感器網(wǎng)絡(luò)一般被部署在沙漠、戰(zhàn)場(chǎng)等工作人員不可達(dá)到的環(huán)境中，需要利用節(jié)點(diǎn)的高度冗余來(lái)保證網(wǎng)絡(luò)的容錯(cuò)性和數(shù)據(jù)的精確性。目前，在處理節(jié)點(diǎn)冗余延長(zhǎng)網(wǎng)絡(luò)生命周期和均衡節(jié)點(diǎn)能量方面有很多的研究，文獻(xiàn)［4－5］通過(guò)采用節(jié)點(diǎn)“休眠”和“活躍”輪換的方式，在滿足覆蓋要求的條件下，通過(guò)最大化輪換節(jié)點(diǎn)集合的數(shù)目來(lái)保證大規(guī)模網(wǎng)絡(luò)環(huán)境下傳感節(jié)點(diǎn)的有效使用。文獻(xiàn)［6］進(jìn)一步提出一種集中式、利用節(jié)點(diǎn)分組工作的DSC(disjoint set covers)算法，該算法將問(wèn)題抽象成最大流圖問(wèn)題，并對(duì)節(jié)點(diǎn)進(jìn)行任務(wù)集分配，通過(guò)各個(gè)節(jié)點(diǎn)任務(wù)集輪流工作均衡了各節(jié)點(diǎn)能耗。但由于該算法分組固定，一旦某節(jié)點(diǎn)能量耗盡或有新節(jié)點(diǎn)加入網(wǎng)絡(luò)，將導(dǎo)致工作節(jié)點(diǎn)無(wú)法對(duì)自身所處分組進(jìn)行自適應(yīng)調(diào)節(jié)。文獻(xiàn)［7］為了解決固定分組導(dǎo)致工作節(jié)點(diǎn)無(wú)法自適應(yīng)調(diào)節(jié)的問(wèn)題提出了一種PEAS算法，該算法通過(guò)探測(cè)鄰居節(jié)點(diǎn)的工作狀態(tài)來(lái)判斷自身節(jié)點(diǎn)工作狀態(tài)，能夠減小工作節(jié)點(diǎn)數(shù)，節(jié)約能耗，但該算法容易出現(xiàn)部分節(jié)點(diǎn)一直處于工作狀態(tài)直到節(jié)點(diǎn)能量耗盡才更換其它節(jié)點(diǎn)工作，導(dǎo)致網(wǎng)絡(luò)的穩(wěn)定性和網(wǎng)絡(luò)節(jié)點(diǎn)能量均衡性較差。文獻(xiàn)［8－9］在PEAS算法的基礎(chǔ)上進(jìn)一步考慮到傳感節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系(一個(gè)傳感節(jié)點(diǎn)可以感知多個(gè)目標(biāo)節(jié)點(diǎn)以及一個(gè)目標(biāo)節(jié)點(diǎn)處于多個(gè)傳感節(jié)點(diǎn)的覆蓋范圍內(nèi))，通過(guò)數(shù)據(jù)挖掘技術(shù)建立傳感節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的關(guān)聯(lián)準(zhǔn)則，根據(jù)關(guān)聯(lián)準(zhǔn)則調(diào)度節(jié)點(diǎn)輪換工作來(lái)均衡網(wǎng)絡(luò)節(jié)點(diǎn)之間的能量，但該算法在關(guān)聯(lián)準(zhǔn)則下僅通過(guò)簡(jiǎn)單的比較傳感節(jié)點(diǎn)能量大小來(lái)選取工作節(jié)點(diǎn)，可能導(dǎo)致部分節(jié)點(diǎn)調(diào)度不合理，從而造成資源浪費(fèi)。

本文首先考慮到傳感節(jié)點(diǎn)采用休眠和活躍機(jī)制分集合輪換覆蓋目標(biāo)節(jié)點(diǎn)，可以有效地延長(zhǎng)網(wǎng)絡(luò)生命周期，但固定分組對(duì)于集合中某些節(jié)點(diǎn)的死亡無(wú)法自適應(yīng)調(diào)節(jié)，因而新算法只對(duì)最小頻繁項(xiàng)的目標(biāo)采用分集合覆蓋，考慮到PEAS算法對(duì)節(jié)點(diǎn)能夠自適應(yīng)調(diào)節(jié)，但PEAS算法只是隨機(jī)選取工作節(jié)點(diǎn)，可能會(huì)不合理的調(diào)度節(jié)點(diǎn)工作，所以對(duì)邊緣未覆蓋的目標(biāo)節(jié)點(diǎn)采用加權(quán)［10－11］覆蓋，通過(guò)權(quán)值來(lái)選擇工作節(jié)點(diǎn)，可以減少每輪的工作節(jié)點(diǎn)數(shù)和改善網(wǎng)絡(luò)節(jié)點(diǎn)間能耗的均衡性。

1 PEAS算法概述

1.1 問(wèn)題描述

為了更好地表述問(wèn)題，假設(shè)無(wú)線傳感器網(wǎng)絡(luò)的覆蓋情況如下，網(wǎng)絡(luò)中存在M個(gè)傳感節(jié)點(diǎn)hi∈H(i=1，2，3，…，M)分布在 L×L 二維正方形區(qū)域內(nèi)，對(duì)N 個(gè)目標(biāo)節(jié)點(diǎn) kj∈K(j=1，2，3，…，N)實(shí)現(xiàn)監(jiān)控。為了實(shí)現(xiàn)對(duì)目標(biāo)節(jié)點(diǎn)更準(zhǔn)確的監(jiān)測(cè)，通常需要在監(jiān)測(cè)目標(biāo)區(qū)域拋撒比較多的傳感節(jié)點(diǎn)，使得目標(biāo)節(jié)點(diǎn)周圍有高度冗余的傳感節(jié)點(diǎn)對(duì)其實(shí)現(xiàn)覆蓋。目標(biāo)節(jié)點(diǎn)通常會(huì)被兩個(gè)或兩個(gè)以上的傳感節(jié)點(diǎn)覆蓋，而傳感節(jié)點(diǎn)可能覆蓋多個(gè)目標(biāo)節(jié)點(diǎn)(如表1)。如圖1所示，由于覆蓋目標(biāo)節(jié)點(diǎn)的傳感節(jié)點(diǎn)都存在冗余，所以監(jiān)測(cè)區(qū)域的目標(biāo)頻繁項(xiàng)大于等于2。

圖1 無(wú)線傳感器網(wǎng)絡(luò)覆蓋圖

表1 傳感節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的關(guān)系

1.2 PEAS 算法

PEAS算法是一種分布式的狀態(tài)自確定的算法，在PEAS算法中傳感節(jié)點(diǎn)有三種狀態(tài)(如圖2所示):覆蓋質(zhì)量探測(cè)(Probing)、感知工作狀態(tài)(Working)和適應(yīng)性休眠狀態(tài)(Sleeping)。工作開(kāi)始后，網(wǎng)絡(luò)中各傳感節(jié)點(diǎn)首先進(jìn)入覆蓋質(zhì)量探測(cè)狀態(tài)，通過(guò)廣播探測(cè)包給鄰居工作節(jié)點(diǎn)，鄰居工作節(jié)點(diǎn)通過(guò)收集覆蓋范圍內(nèi)的目標(biāo)信息并向發(fā)送探測(cè)包的傳感節(jié)點(diǎn)發(fā)送回復(fù)消息，傳感節(jié)點(diǎn)通過(guò)回復(fù)消息來(lái)判斷其周邊覆蓋區(qū)域內(nèi)的監(jiān)控目標(biāo)是否已完全能夠被鄰近的工作節(jié)點(diǎn)所感知，若存在尚未被感知的目標(biāo)，則該節(jié)點(diǎn)進(jìn)入感知工作狀態(tài);否則，該傳感節(jié)點(diǎn)關(guān)閉通信和感知方式，進(jìn)入能量消耗較少的適應(yīng)性休眠狀態(tài)。但休眠節(jié)點(diǎn)并不是一直處于休眠狀態(tài)，它每隔一段時(shí)間后都會(huì)被喚醒，傳感節(jié)點(diǎn)會(huì)再次向鄰居工作節(jié)點(diǎn)發(fā)送探測(cè)包對(duì)該節(jié)點(diǎn)周邊覆蓋區(qū)域內(nèi)的感知情況進(jìn)行探測(cè)，根據(jù)鄰居節(jié)點(diǎn)的回復(fù)消息確定下一輪該傳感節(jié)點(diǎn)的工作狀態(tài)。

圖2 PEAS算法傳感節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換圖

在傳感節(jié)點(diǎn)高冗余的環(huán)境下，PEAS算法通過(guò)探測(cè)監(jiān)聽(tīng)機(jī)制來(lái)確定傳感節(jié)點(diǎn)的狀態(tài)，能夠有效地調(diào)度傳感節(jié)點(diǎn)的工作與休眠，減少工作節(jié)點(diǎn)的數(shù)目，但PEAS算法在工作開(kāi)始之前，隨機(jī)地選取工作節(jié)點(diǎn)，然后根據(jù)已工作的鄰居節(jié)點(diǎn)的覆蓋信息來(lái)判斷自身節(jié)點(diǎn)是否進(jìn)入休眠狀態(tài)，因而傳感節(jié)點(diǎn)的利用率相對(duì)較低。另外，PEAS算法未考慮節(jié)點(diǎn)剩余能量對(duì)傳感網(wǎng)絡(luò)的影響。在PEAS算法中，當(dāng)傳感器節(jié)點(diǎn)一旦被選為工作節(jié)點(diǎn)后，則其將一直處于工作狀態(tài)直到節(jié)點(diǎn)的能量耗盡，工作節(jié)點(diǎn)在能量較低的情況下仍處于工作狀態(tài)，必然會(huì)導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)間的能量均衡性以及網(wǎng)絡(luò)的穩(wěn)定性變差。

2 基于加權(quán)的優(yōu)化覆蓋算法

2.1 基本定義

定義1 節(jié)點(diǎn)感知半徑r

傳感節(jié)點(diǎn)所能感知目標(biāo)的最大范圍即節(jié)點(diǎn)感知半徑 r。

定義2 目標(biāo)頻繁項(xiàng)

對(duì)于目標(biāo)節(jié)點(diǎn)kj同時(shí)處于多少傳感節(jié)點(diǎn)hi的感知范圍之下，目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)傳感節(jié)點(diǎn)的數(shù)目即為目標(biāo)頻繁項(xiàng)。最小頻繁項(xiàng)是指目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)最少的傳感節(jié)點(diǎn)數(shù)目。

定義3 覆蓋度A

定義4 節(jié)點(diǎn)關(guān)聯(lián)強(qiáng)度Q

傳感節(jié)點(diǎn)hi、hk在感知范圍內(nèi)所覆蓋目標(biāo)節(jié)點(diǎn)的集合分別為Bi、Bk，則定義關(guān)聯(lián)強(qiáng)度為 Q=Bi∩Bk。Q越大關(guān)聯(lián)強(qiáng)度越大，Q為0表示兩傳感節(jié)點(diǎn)不相關(guān)。

2.2 算法思想

基于加權(quán)優(yōu)化覆蓋算法首先考慮的是網(wǎng)絡(luò)中最小頻繁項(xiàng)目標(biāo)對(duì)應(yīng)的傳感節(jié)點(diǎn)工作狀態(tài)對(duì)網(wǎng)絡(luò)周期的影響。由于最小頻繁項(xiàng)目標(biāo)處在最少傳感節(jié)點(diǎn)的覆蓋下，如果讓最小頻繁項(xiàng)目標(biāo)對(duì)應(yīng)的傳感節(jié)點(diǎn)同時(shí)工作，勢(shì)必會(huì)導(dǎo)致網(wǎng)絡(luò)的生存周期下降，所以本文對(duì)最小頻繁項(xiàng)目標(biāo)采用劃分集合的方式進(jìn)行覆蓋，盡量將最小頻繁項(xiàng)目標(biāo)對(duì)應(yīng)的傳感節(jié)點(diǎn)劃分到不同的集合中，保證每個(gè)傳感節(jié)點(diǎn)集合能夠獨(dú)立覆蓋所有最小頻繁項(xiàng)目標(biāo)，如果在劃分過(guò)程中發(fā)現(xiàn)有集合不能覆蓋最小頻繁項(xiàng)目標(biāo)，則去除該集合。由于劃分好的各集合都能夠獨(dú)立覆蓋所有最小頻繁項(xiàng)目標(biāo)，所以新算法采用輪換的工作機(jī)制，讓其中一個(gè)集合中的節(jié)點(diǎn)處于工作狀態(tài)，其它集合中的節(jié)點(diǎn)處于休眠狀態(tài)，每隔一段時(shí)間，更換工作節(jié)點(diǎn)集合，以實(shí)現(xiàn)對(duì)最小頻繁項(xiàng)目標(biāo)的優(yōu)化覆蓋。對(duì)于最小頻繁項(xiàng)目標(biāo)以外未被覆蓋的目標(biāo)節(jié)點(diǎn)，考慮到讓覆蓋目標(biāo)多的傳感節(jié)點(diǎn)優(yōu)先選為工作節(jié)點(diǎn)可以減少工作節(jié)點(diǎn)的數(shù)目，但讓覆蓋目標(biāo)多的傳感節(jié)點(diǎn)一直處于工作狀態(tài)也會(huì)導(dǎo)致該節(jié)點(diǎn)過(guò)早的死亡，使得網(wǎng)絡(luò)的穩(wěn)定性變差。為了避免某些節(jié)點(diǎn)持續(xù)處于工作狀態(tài)，需要考慮節(jié)點(diǎn)剩余能量對(duì)網(wǎng)絡(luò)穩(wěn)定性的影響，在節(jié)點(diǎn)調(diào)度過(guò)程中，盡量不讓能量低的傳感節(jié)點(diǎn)繼續(xù)工作，所以對(duì)邊緣未被覆蓋的目標(biāo)采用加權(quán)覆蓋，其權(quán)值跟傳感節(jié)點(diǎn)覆蓋目標(biāo)節(jié)點(diǎn)的數(shù)目和傳感節(jié)點(diǎn)的剩余能量有關(guān)。由于每輪各節(jié)點(diǎn)所處的狀態(tài)不同，所以各節(jié)點(diǎn)的能耗不同，各節(jié)點(diǎn)的權(quán)值也會(huì)發(fā)生不同程度的下降。在每輪結(jié)束后需要重新計(jì)算各傳感節(jié)點(diǎn)的權(quán)值，然后將權(quán)值大的傳感節(jié)點(diǎn)選為工作節(jié)點(diǎn)。歸一化后的權(quán)值計(jì)算公式如下:

其中a1、a2是加權(quán)系數(shù)，根據(jù)網(wǎng)絡(luò)環(huán)境不同可選取不同的加權(quán)系數(shù)，并且其滿足約束條件:a1+a2=1。Gi表示傳感節(jié)點(diǎn)hi所包含目標(biāo)節(jié)點(diǎn)數(shù)目，Gmax表示本輪中單個(gè)傳感節(jié)點(diǎn)所包含的最多目標(biāo)節(jié)點(diǎn)數(shù)，Ei表示傳感節(jié)點(diǎn)的剩余能量，Emax表示本輪中傳感節(jié)點(diǎn)剩余的能量最大值。

2.3 新算法的偽代碼

輸入:傳感器節(jié)點(diǎn)集 H={h1，h2，L，hn}，節(jié)點(diǎn)數(shù)為 n，目標(biāo)節(jié)點(diǎn)集 K={k1，k2，L，ks}，目標(biāo)數(shù)為 s，網(wǎng)絡(luò)環(huán)境目標(biāo)最小頻繁項(xiàng)數(shù)N≥2。

輸出:實(shí)現(xiàn)節(jié)點(diǎn)之間覆蓋監(jiān)測(cè)目標(biāo)的節(jié)點(diǎn)集集合Gi里的節(jié)點(diǎn)處于工作狀態(tài)時(shí)能實(shí)現(xiàn)對(duì)所有目標(biāo)的覆蓋;

2.4 算法具體實(shí)現(xiàn)過(guò)程

表2 傳感節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的關(guān)系

步驟1:選取頻繁項(xiàng)等于最小頻繁項(xiàng)N的目標(biāo)，將目標(biāo)頻繁項(xiàng)等于N的目標(biāo)節(jié)點(diǎn)放入最小頻繁項(xiàng)的目標(biāo)節(jié)點(diǎn)集M中(對(duì)應(yīng)于算法偽代碼的第一步)。

表3 最小頻繁項(xiàng)目標(biāo)與關(guān)聯(lián)節(jié)點(diǎn)的關(guān)系

步驟2:首先將集合M中各目標(biāo)節(jié)點(diǎn)依次取出，然后將各覆蓋該目標(biāo)的傳感節(jié)點(diǎn)按照能量高低依次放入覆蓋監(jiān)測(cè)目標(biāo)的節(jié)點(diǎn)集 G1，G2，…，GN，并判斷覆蓋該目標(biāo)的傳感節(jié)點(diǎn)存放是否導(dǎo)致G1，G2，…，GN獨(dú)立覆蓋前面的目標(biāo)，如果是，則N=N－1(即使覆蓋監(jiān)測(cè)目標(biāo)的節(jié)點(diǎn)集G1，G2，…，GN減少一個(gè))并跳至步驟2進(jìn)行重新劃分;否則，跳至步驟3(對(duì)應(yīng)算法偽代碼第二步)。

表4 節(jié)點(diǎn)更新后傳感節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的關(guān)系

步驟3:計(jì)算各個(gè)未加入集合 G1，G2，…，GN的傳感節(jié)點(diǎn)hi的權(quán)值Wi，選擇權(quán)值最大的節(jié)點(diǎn)hj先工作，將hj加入集合Gi，判斷Gi中的傳感節(jié)點(diǎn)能否覆蓋所有目標(biāo)，如果能，則結(jié)束;否則，跳至步驟3繼續(xù)選取新節(jié)點(diǎn)加入(對(duì)應(yīng)于算法偽代碼第三步)。

過(guò)程分析:以表2為例(表2由圖1生成)，表2中目標(biāo)節(jié)點(diǎn)的最小頻繁項(xiàng)為2，其中頻繁項(xiàng)為2的目標(biāo)節(jié)點(diǎn)有 5、6、7、9、10、11、14 將其加入 M 中(如表3)，假設(shè)目標(biāo)節(jié)點(diǎn)5對(duì)應(yīng)的傳感節(jié)點(diǎn)1能量高將其放入G1中，為了避免最小頻繁項(xiàng)目標(biāo)對(duì)應(yīng)的傳感節(jié)點(diǎn)同時(shí)工作，則傳感節(jié)點(diǎn)2就必須放入G2中，對(duì)于目標(biāo)6中含有傳感節(jié)點(diǎn)1，由于傳感節(jié)點(diǎn)1放在G1中，為了實(shí)現(xiàn)G1和G2獨(dú)立覆蓋目標(biāo)1、6，則目標(biāo)6對(duì)應(yīng)的傳感節(jié)點(diǎn)5必須放入G2中，同理，可以得到傳感節(jié)點(diǎn)4、9放入G1中，傳感節(jié)點(diǎn)7放入G2中，對(duì)于目標(biāo)10我們選擇能量高的傳感節(jié)點(diǎn)8放入G1，傳感節(jié)點(diǎn)3放入 G2，集合劃分完畢，G1={1，4，8，9}，G2={2，3，5，7}能夠分別完全覆蓋目標(biāo)節(jié)點(diǎn)5、6、7、8、9、10、11、14。并更新目標(biāo)節(jié)點(diǎn)與傳感節(jié)點(diǎn)的關(guān)系表(表2)得到新的目標(biāo)節(jié)點(diǎn)與傳感節(jié)點(diǎn)的關(guān)系表(表4)，計(jì)算目標(biāo)節(jié)點(diǎn)12對(duì)應(yīng)的權(quán)值最大的傳感節(jié)點(diǎn)6放入G1(假設(shè)傳感節(jié)點(diǎn)6權(quán)值最大傳感節(jié)點(diǎn)12權(quán)值最小)傳感節(jié)點(diǎn)11放入G2，判斷G1和G2是否能夠覆蓋所有節(jié)點(diǎn)，發(fā)現(xiàn)G1和G2能夠覆蓋所有目標(biāo)節(jié)點(diǎn)，此輪結(jié)束。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證上述算法的有效性，本文將新算法和PEAS算法進(jìn)行了仿真比較。實(shí)驗(yàn)環(huán)境:在win7系統(tǒng)下采用matlab2010作為仿真平臺(tái)。在40×40區(qū)域內(nèi)，隨機(jī)分布25個(gè)目標(biāo)節(jié)點(diǎn)，并且在目標(biāo)區(qū)域部署40個(gè)傳感節(jié)點(diǎn)。傳感器節(jié)點(diǎn)的感知半徑r為6。傳感節(jié)點(diǎn)的初始能量為［100 mJ，110 mJ］上的隨機(jī)數(shù)。加權(quán)系數(shù)可以根據(jù)不同網(wǎng)絡(luò)環(huán)境選取不同的加權(quán)系數(shù)，如果傳感節(jié)點(diǎn)的初始能量的變化范圍較大時(shí)，可以適當(dāng)?shù)奶岣吣芰康臋?quán)值系數(shù)a2來(lái)均衡網(wǎng)絡(luò)中節(jié)點(diǎn)能量，本實(shí)驗(yàn)中由于傳感節(jié)點(diǎn)初始能量的變化范圍較小，因而本文選取加權(quán)系數(shù)a1、a2分別為0.5、0.5。節(jié)點(diǎn)的能耗模型參照文獻(xiàn)［8、12］，傳感節(jié)點(diǎn)處于工作狀態(tài)時(shí)單位時(shí)間內(nèi)能耗為1.7 mJ，休眠狀態(tài)時(shí)單位時(shí)間內(nèi)能耗為0.3 mJ。5個(gè)單位時(shí)間作為一輪，工作節(jié)點(diǎn)集每輪結(jié)束后交換一次，當(dāng)傳感節(jié)點(diǎn)的能量小于50 mJ時(shí)判定節(jié)點(diǎn)死亡。實(shí)驗(yàn)主要對(duì)網(wǎng)絡(luò)生存周期，工作節(jié)點(diǎn)數(shù)、以及網(wǎng)絡(luò)能耗進(jìn)行研究和比較。圖3首先給出了覆蓋度與節(jié)點(diǎn)工作時(shí)間的關(guān)系圖，網(wǎng)絡(luò)生命周期為目標(biāo)節(jié)點(diǎn)覆蓋度為1的時(shí)間長(zhǎng)度。從圖3上可以看到節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)生命周期只有7輪左右即35個(gè)單位時(shí)間左右網(wǎng)絡(luò)已經(jīng)不能維持全覆蓋，而PEAS算法采用根據(jù)其自身周邊覆蓋區(qū)域的被感知質(zhì)量決定自身狀態(tài)的方式，使得網(wǎng)絡(luò)的生命周期達(dá)到了60個(gè)單位時(shí)間，網(wǎng)絡(luò)生命周期相對(duì)于隨機(jī)部署算法延長(zhǎng)了71.43%。本文提出的新算法的網(wǎng)絡(luò)生存周期達(dá)到了75個(gè)單位時(shí)間，它相對(duì)于PEAS算法又提高了25%，其原因是由于PEAS算法采用隨機(jī)選取工作節(jié)點(diǎn)的方式，使得部分目標(biāo)對(duì)應(yīng)的某些關(guān)鍵的傳感節(jié)點(diǎn)經(jīng)常同時(shí)工作，使得網(wǎng)絡(luò)生命周期下降。

圖3 網(wǎng)絡(luò)覆蓋度與工作時(shí)間的關(guān)系

圖4是網(wǎng)絡(luò)工作節(jié)點(diǎn)數(shù)與工作時(shí)間的關(guān)系圖，從圖上可以清晰的看出隨機(jī)部署的工作節(jié)點(diǎn)在網(wǎng)絡(luò)生存周期里所需要的工作節(jié)點(diǎn)數(shù)最多，PEAS在網(wǎng)絡(luò)生存周期里所需要的工作節(jié)點(diǎn)數(shù)為10，而新算法的工作節(jié)點(diǎn)數(shù)在網(wǎng)絡(luò)生存周期內(nèi)工作節(jié)點(diǎn)的數(shù)目主要在區(qū)間［6，8］上變動(dòng)，最大只需要8個(gè)，顯然低于PEAS算法在網(wǎng)絡(luò)生存周期內(nèi)的工作節(jié)點(diǎn)數(shù)。

圖4 網(wǎng)絡(luò)工作節(jié)點(diǎn)數(shù)與工作時(shí)間的關(guān)系

圖5是網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量與工作時(shí)間的關(guān)系圖，從圖上可以看到隨機(jī)部署的算法網(wǎng)絡(luò)剩余能量下降的最快，所以隨機(jī)部署算法在工作過(guò)程中每輪消耗的能量最多，而PEAS算法網(wǎng)絡(luò)剩余能量下降的坡度相對(duì)比較平緩，所以PEAS算法每輪的能耗比較小，最后看到新算法的曲線在PEAS算法和隨機(jī)部署的曲線之上，可以說(shuō)明新算法在工作過(guò)程中的能耗最少，網(wǎng)絡(luò)剩余能量最大。

圖5 網(wǎng)絡(luò)能耗與工作時(shí)間的關(guān)系

圖6是節(jié)點(diǎn)能量標(biāo)準(zhǔn)差與工作節(jié)點(diǎn)的關(guān)系圖，從圖上可以看到PEAS算法節(jié)點(diǎn)能量標(biāo)準(zhǔn)差在整個(gè)工作過(guò)程中最大，說(shuō)明PEAS算法的網(wǎng)絡(luò)節(jié)點(diǎn)能量均衡性最差，而新算法能量標(biāo)準(zhǔn)差相對(duì)較小，說(shuō)明新算法的網(wǎng)絡(luò)節(jié)點(diǎn)能量均衡性相對(duì)于PEAS算法有了進(jìn)一步的改善。

圖6 節(jié)點(diǎn)能量標(biāo)準(zhǔn)差與工作時(shí)間的關(guān)系

4 結(jié)論

本文提出了一種基于加權(quán)的無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化覆蓋算法。該算法根據(jù)目標(biāo)頻繁項(xiàng)大小把目標(biāo)劃分成最小頻繁項(xiàng)目標(biāo)和非最小頻繁項(xiàng)目標(biāo)，然后對(duì)最小頻繁項(xiàng)目標(biāo)和非最小頻繁項(xiàng)目標(biāo)分別采用劃分集合的方式和加權(quán)的方式進(jìn)行優(yōu)化覆蓋。仿真結(jié)果表明:新算法相比PEAS算法，能夠有效地減少每輪的工作節(jié)點(diǎn)數(shù)、均衡網(wǎng)絡(luò)節(jié)點(diǎn)間的能量和延長(zhǎng)網(wǎng)絡(luò)的生命周期。

［1］ Rahman M D，Sajid A H.Uniformity and Efficiency of a Wireless Sensor Network’s Coverage Advanced Information Networking and Applications［C］//AINA，07.2007:506_510.

［2］ Seapahn M，F(xiàn)arinaz K.Worst and Best-Case Coverage in Sensor Networks［C］//IEEE Transactions on Mobile Computing.2005，4(1):84－92.

［3］ 任彥，張思東，張宏科.無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法［J］.軟件學(xué)報(bào)，2006，17(3):422－433.

［4］ Slijepcevic S，Potkonjak M.PowerEfficientOrganization of Wireless Sensor Networks［C］//Proc.of the IEEE Int’l Conf.on Communications(ICC).Helsinki:IEEE Press，2001.472－476.

［5］ Tian D，Georganzs N D.A Node Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks［J］.Wireless Communications and Mobile Computing，2003，3(2):271－290.

［6］ Cardei M，Du D Z.Improving Wireless Sensor Network Lifetime Through Power Aware Organization［J］.Wireless Networks，2005，11(3):333－340.

［7］ Ye Fan，Zhong G，Lu S，et al.PEAS:A Robust Energy Conserving Protocol for Long-Lived Sensor Network［C］//Proceedings of 10th IEEE InternationalConferenceon Network Protocols.Paris，F(xiàn)rance，2002:200－201.

［8］ 劉麗萍，張強(qiáng)，孫雨耕.無(wú)線傳感器網(wǎng)絡(luò)多目標(biāo)關(guān)聯(lián)覆蓋［J］.天津大學(xué)學(xué)報(bào)，2009，42(6):483－489.

［9］ 孫喜策，曹峰，王智.一種面向多目標(biāo)關(guān)聯(lián)覆蓋的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)優(yōu)化調(diào)度算法［J］.信息與控制，2009，38(1):29－36.

［10］張品，姜亞光，陳磊.基于加權(quán)優(yōu)化選取兩級(jí)簇頭的WSN路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2011，24(3):447－451.

［11］張品，徐智福，孫巖.一種新的基于簇頭優(yōu)化的WSN路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2009，7(22):1013－1017.

［12］ Chen H H，Yang Y.Network Coverage and Routing Schemes for Wireless Sensor Networks［J］.Computer Communications，2007，30(14－15):2697－2698.