無(wú)線傳感器網(wǎng)絡(luò)中能量均衡參數(shù)可控覆蓋算法

孫澤宇,伍衛(wèi)國(guó),曹仰杰,邢蕭飛

(1.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安;2.洛陽(yáng)理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院,471023,河南洛陽(yáng);3.鄭州大學(xué)軟件與應(yīng)用科技學(xué)院,450001,鄭州;4.廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院,510006,廣州)

?

無(wú)線傳感器網(wǎng)絡(luò)中能量均衡參數(shù)可控覆蓋算法

孫澤宇1,2,伍衛(wèi)國(guó)1,曹仰杰3,邢蕭飛4

(1.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安;2.洛陽(yáng)理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院,471023,河南洛陽(yáng);3.鄭州大學(xué)軟件與應(yīng)用科技學(xué)院,450001,鄭州;4.廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院,510006,廣州)

針對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行k度覆蓋的過(guò)程中會(huì)出現(xiàn)大量數(shù)據(jù)冗余迫使網(wǎng)絡(luò)出現(xiàn)擁塞并導(dǎo)致網(wǎng)絡(luò)通信能力和覆蓋能力降低、網(wǎng)絡(luò)能量快速消耗等問(wèn)題,提出了一種能量均衡參數(shù)可控的覆蓋算法(energy balance parameters-controlled coverage,EBPCC)。該算法利用節(jié)點(diǎn)之間的位置關(guān)系構(gòu)造出覆蓋網(wǎng)絡(luò)模型,通過(guò)分析網(wǎng)絡(luò)模型給出監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)覆蓋期望值及對(duì)整個(gè)監(jiān)測(cè)區(qū)域覆蓋所需最少節(jié)點(diǎn)數(shù)的求解過(guò)程;在能耗方面給出了工作節(jié)點(diǎn)和鄰居節(jié)點(diǎn)之間的能量轉(zhuǎn)換函數(shù)比例關(guān)系,利用函數(shù)比例關(guān)系完成低能量節(jié)點(diǎn)的調(diào)度,進(jìn)而達(dá)到全網(wǎng)能量平衡。實(shí)驗(yàn)結(jié)果表明:該算法不僅可以提高網(wǎng)絡(luò)覆蓋質(zhì)量,還可以有效抑制網(wǎng)絡(luò)節(jié)點(diǎn)能量快速消耗,在相同的監(jiān)測(cè)環(huán)境下,該算法的網(wǎng)絡(luò)生存周期比能量有效的目標(biāo)覆蓋ETCA算法延長(zhǎng)了12.91%,覆蓋率比事件概率驅(qū)動(dòng)機(jī)制EPDM算法提高了7.06%。

無(wú)線傳感器網(wǎng)絡(luò);k度覆蓋;覆蓋率;網(wǎng)絡(luò)生存周期;能量均衡

無(wú)線傳感器網(wǎng)絡(luò)是由成千上萬(wàn)傳感器節(jié)點(diǎn)通過(guò)自組織方式所形成的新型網(wǎng)絡(luò)體系結(jié)構(gòu)[1-2],每個(gè)傳感器節(jié)點(diǎn)都具有一定的感知、通信、計(jì)算和存儲(chǔ)能力,被廣泛地應(yīng)用在軍事國(guó)防、智能制造、衛(wèi)生醫(yī)療、環(huán)境監(jiān)測(cè)、緊急救援、智能家居等各種工程領(lǐng)域,其行為特征主要表現(xiàn)在對(duì)所感知的物理世界以多跳方式完成數(shù)據(jù)采集與通信傳輸[3],并將物理世界與信息世界有機(jī)統(tǒng)一、融為一體,實(shí)現(xiàn)了從數(shù)據(jù)采集、存儲(chǔ)計(jì)算到通信傳輸?shù)逆準(zhǔn)骄W(wǎng)絡(luò)服務(wù)體系[4]。

覆蓋質(zhì)量和網(wǎng)絡(luò)能耗是評(píng)價(jià)無(wú)線傳感器網(wǎng)絡(luò)體系性能的兩個(gè)重要指標(biāo)[5]。覆蓋質(zhì)量?jī)?yōu)劣直接體現(xiàn)在對(duì)監(jiān)測(cè)區(qū)域節(jié)點(diǎn)部署方式上。網(wǎng)絡(luò)生存周期長(zhǎng)短直接影響整個(gè)網(wǎng)絡(luò)服務(wù)質(zhì)量,主要體現(xiàn)在部署節(jié)點(diǎn)的能量消耗方式上[6]。一般情況下,受地形地貌及環(huán)境因素等諸多條件的限制,在傳感器節(jié)點(diǎn)部署方式上往往采用隨機(jī)部署方式。在此部署過(guò)程中,由于事先無(wú)法獲知傳感器節(jié)點(diǎn)具體位置信息,就會(huì)使得對(duì)某一監(jiān)測(cè)點(diǎn)處于多重覆蓋之中,即k度覆蓋。另一種情況,由于隨機(jī)性的存在,有可能使得某一監(jiān)測(cè)區(qū)域處于覆蓋盲區(qū)[7-8]。為了達(dá)到對(duì)該點(diǎn)的有效覆蓋,只能增加更多的節(jié)點(diǎn)達(dá)到覆蓋目的[9]。上述兩種情況雖然在某種程度上可以達(dá)到對(duì)目標(biāo)的有效覆蓋,但也存在著一些不足:①由于k度覆蓋存在,在采集、計(jì)算數(shù)據(jù)過(guò)程中以及數(shù)據(jù)在通信鏈路傳輸過(guò)程中必然會(huì)產(chǎn)生大量的冗余數(shù)據(jù),這些冗余數(shù)據(jù)對(duì)數(shù)據(jù)的計(jì)算及通信必將帶來(lái)較大誤差和不確定性[10-11];②覆蓋的真正意義并不是對(duì)整個(gè)監(jiān)測(cè)區(qū)域的完全覆蓋,而是對(duì)某一個(gè)或幾個(gè)所關(guān)注的目標(biāo)節(jié)點(diǎn)進(jìn)行有效覆蓋;在不考慮關(guān)注目標(biāo)節(jié)點(diǎn)存在的情況下,對(duì)整個(gè)監(jiān)測(cè)區(qū)域進(jìn)行完全覆蓋的過(guò)程中,就會(huì)消耗大量節(jié)點(diǎn)能量,加快了整個(gè)網(wǎng)絡(luò)體系的崩潰速度;③在部署節(jié)點(diǎn)時(shí),由于隨機(jī)性的存在必然會(huì)導(dǎo)致監(jiān)測(cè)區(qū)域某個(gè)覆蓋區(qū)域節(jié)點(diǎn)密度過(guò)大,易產(chǎn)生瓶頸效應(yīng),最終將會(huì)在整個(gè)傳輸信道內(nèi)產(chǎn)生信息冗余、信道干擾,同時(shí)也降低了網(wǎng)絡(luò)擴(kuò)展性。

針對(duì)上述研究存在的不足,本文提出一種能量均衡參數(shù)可控的覆蓋算法(energy balance parameters-controlled coverage,EBPCC)。本文算法利用移動(dòng)目標(biāo)節(jié)點(diǎn)穿越監(jiān)測(cè)區(qū)域時(shí)覆蓋面所形成的扇形區(qū)域求解傳感器節(jié)點(diǎn)的覆蓋率及覆蓋的期望值。在能量方面,本文給出多點(diǎn)傳輸與單點(diǎn)傳輸求解過(guò)程。對(duì)于工作傳感器節(jié)點(diǎn)而言,在滿足一定覆蓋率的前提下,移動(dòng)目標(biāo)節(jié)點(diǎn)穿越k度覆蓋區(qū)域時(shí),通過(guò)傳感器節(jié)點(diǎn)自適應(yīng)轉(zhuǎn)換機(jī)制關(guān)閉能量介于閾值取值之內(nèi)或高于閾值上限的傳感器節(jié)點(diǎn),或?qū)鞲衅鞴?jié)點(diǎn)置于休眠狀態(tài),而其他傳感器節(jié)點(diǎn)則通過(guò)能量調(diào)度算法完成傳感器節(jié)點(diǎn)之間的能量轉(zhuǎn)換機(jī)制,以提高網(wǎng)絡(luò)生存周期。

本文貢獻(xiàn)主要體現(xiàn)在以下幾點(diǎn):①對(duì)相關(guān)知識(shí)進(jìn)行分析與總結(jié),在此基礎(chǔ)上提出了EBPCC算法的網(wǎng)絡(luò)模型;②根據(jù)隨機(jī)部署特性,分析了在監(jiān)測(cè)區(qū)域內(nèi)部署傳感器節(jié)點(diǎn)的分布形態(tài),給出了服從λ、N(s)為隨機(jī)變量的泊松分布的計(jì)算過(guò)程以及網(wǎng)絡(luò)覆蓋率求解方法;③以網(wǎng)絡(luò)模型作為研究對(duì)象,提出了計(jì)算覆蓋期望值的方法,在對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行聯(lián)合覆蓋時(shí),給出覆蓋期望值的求解過(guò)程;④最后通過(guò)仿真實(shí)驗(yàn)與能量有效的目標(biāo)覆蓋算法(energy efficient target coverage algorthm,ETCA)和事件概率驅(qū)動(dòng)機(jī)制(event probability drive mechanism,EPDM)對(duì)網(wǎng)絡(luò)生存周期和覆蓋率兩項(xiàng)性能指標(biāo)進(jìn)行了比對(duì)實(shí)驗(yàn),驗(yàn)證了本文EBPCC算法的有效性和穩(wěn)定性。

1 網(wǎng)絡(luò)模型與覆蓋質(zhì)量

為了更好地研究無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題,EBPCC算法基于以下4種假設(shè):①初始時(shí)刻傳感器節(jié)點(diǎn)均為同構(gòu)形態(tài),且感知區(qū)域均為圓盤形;②初始時(shí)刻任意節(jié)點(diǎn)均能量相等,感知半徑相同,且與時(shí)鐘同步;③傳感器節(jié)點(diǎn)隨機(jī)部署在邊長(zhǎng)為l的正方形監(jiān)測(cè)區(qū)域內(nèi),并保證節(jié)點(diǎn)的感知半徑遠(yuǎn)小于邊長(zhǎng)l,邊界效應(yīng)可以忽略;④任意節(jié)點(diǎn)無(wú)需采用某種定位方法獲取自身的位置信息。

1.1 基本定義

定義1 覆蓋質(zhì)量 在監(jiān)測(cè)區(qū)域內(nèi),所有傳感器節(jié)點(diǎn)的感知面積之和與監(jiān)測(cè)區(qū)域面積的比值,稱為覆蓋質(zhì)量。在某種程度上反映了對(duì)目標(biāo)節(jié)點(diǎn)覆蓋的程度。

定義2 聯(lián)合覆蓋 目標(biāo)集合中任意一個(gè)目標(biāo)節(jié)點(diǎn)至少被一個(gè)傳感器節(jié)點(diǎn)所覆蓋的覆蓋率為p;當(dāng)該目標(biāo)節(jié)點(diǎn)被多個(gè)聯(lián)合傳感器節(jié)點(diǎn)所覆蓋的覆蓋率稱為聯(lián)合覆蓋率

(1)

式中:pn是聯(lián)合覆蓋率;p是任意一個(gè)傳感器節(jié)點(diǎn)的覆蓋率;N是傳感器節(jié)點(diǎn)的個(gè)數(shù)[12]。

定理1 監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署節(jié)點(diǎn)服從于概率密度為λ、N(s)為隨機(jī)變量的泊松分布。

證明 設(shè)Si,area為任意傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域的覆蓋面積,S是邊長(zhǎng)為l的正方形監(jiān)測(cè)區(qū)域的面積。p1=|Si,area|/S,由二項(xiàng)式定理可知,在監(jiān)測(cè)區(qū)域內(nèi),k個(gè)工作傳感器節(jié)點(diǎn)的聯(lián)合概率為

(2)

對(duì)于整個(gè)監(jiān)測(cè)區(qū)域而言,傳感器節(jié)點(diǎn)密度λ=N/S,將λ和p代入式(2)可得

(3)

解之得

(4)

當(dāng)監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)數(shù)趨于無(wú)窮大,即N→∞時(shí)

(5)

證畢。

由定理1可以看出,隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)之間呈現(xiàn)出相互獨(dú)立且均勻分布,其傳感器節(jié)點(diǎn)數(shù)的分布服從于概率密度為λ、N(s)為隨機(jī)變量的泊松分布。

傳感器節(jié)點(diǎn)隨機(jī)部署模型主要解決傳感器節(jié)點(diǎn)分布密度問(wèn)題[13-14]。如何使用最少傳感器節(jié)點(diǎn)完成對(duì)監(jiān)測(cè)區(qū)域的有效覆蓋,取決于在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署傳感器節(jié)點(diǎn)數(shù)[15]。當(dāng)在某個(gè)監(jiān)測(cè)區(qū)域內(nèi)部署足夠多的傳感器節(jié)點(diǎn)時(shí),雖然可以達(dá)到完全覆蓋的目的,但從節(jié)點(diǎn)能耗與節(jié)點(diǎn)冗余角度來(lái)說(shuō),又不切實(shí)際。其一,當(dāng)大量的傳感器節(jié)點(diǎn)部署在監(jiān)測(cè)區(qū)域時(shí),無(wú)形中會(huì)消耗大量傳感器節(jié)點(diǎn)的能量,不利于延長(zhǎng)整個(gè)網(wǎng)絡(luò)生存周期,甚至當(dāng)某個(gè)匯聚節(jié)點(diǎn)能量耗盡,使得整個(gè)網(wǎng)絡(luò)體系快速崩潰;其二,由于大量傳感器節(jié)點(diǎn)的存在,在傳感器節(jié)點(diǎn)之間的連通過(guò)程中將會(huì)產(chǎn)生大量的冗余節(jié)點(diǎn),這些冗余節(jié)點(diǎn)的存在必然對(duì)無(wú)線信道產(chǎn)生干擾,消耗冗余節(jié)點(diǎn)能量,縮短了網(wǎng)絡(luò)生存周期。

為了克服上述兩點(diǎn)不足,更好地提高網(wǎng)絡(luò)服務(wù)質(zhì)量,最大限度延長(zhǎng)網(wǎng)絡(luò)生存周期,要求以某種方式來(lái)實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域的有效覆蓋,以便提高整個(gè)監(jiān)測(cè)區(qū)域的覆蓋率,為此本文引入推論1。

推論1 在監(jiān)測(cè)區(qū)域內(nèi),當(dāng)多個(gè)傳感器節(jié)點(diǎn)進(jìn)行聯(lián)合覆蓋時(shí),聯(lián)合覆蓋率p2=1-e-λπR2。

證明 任意目標(biāo)節(jié)點(diǎn)未被傳感器節(jié)點(diǎn)所覆蓋的覆蓋率為p3=1-(|Si,area|/S),根據(jù)式(4)和定理1可知,當(dāng)目標(biāo)節(jié)點(diǎn)處于至少k個(gè)傳感器節(jié)點(diǎn)聯(lián)合覆蓋時(shí),未被傳感器節(jié)點(diǎn)覆蓋的覆蓋率為

(6)

經(jīng)計(jì)算

(7)

因此,在監(jiān)測(cè)區(qū)域內(nèi)的聯(lián)合覆蓋率p2=1-e-λπR2。

證畢。

1.2 網(wǎng)絡(luò)模型

圖1給出了以扇形為覆蓋區(qū)域的k度覆蓋網(wǎng)絡(luò)模型,以4個(gè)傳感器節(jié)點(diǎn)以及坦克和士兵作為研究對(duì)象進(jìn)行分析,如圖1所示。

由圖1中可以看出,以l為邊長(zhǎng)的正方形作為監(jiān)測(cè)區(qū)域,對(duì)于傳感器節(jié)點(diǎn)而言,其扇面為覆蓋區(qū)域,同時(shí)也給出4個(gè)扇面的不同夾角,以弧度制表示。目標(biāo)節(jié)點(diǎn)坦克和士兵置于k=4度覆蓋中。設(shè)傳感器節(jié)點(diǎn)的感知半徑為R,其覆蓋扇面的面積為

(8)

令θ=α1+α2+α3+α4,即

胼胝體梗死臨床表現(xiàn)多樣，同時(shí)缺乏確切的定位體征，容易被忽略，近年來(lái)隨著MRI的廣泛應(yīng)用，胼胝體梗死的診斷并不困難。CT掃描可以在早期排除腦出血。MRI可以更早、更好地顯示出梗死灶。但胼胝體梗死需要與其它非梗死性疾病相鑒別，首先就是胼胝體腫瘤，包括膠質(zhì)瘤和淋巴瘤等，尤其當(dāng)病變呈團(tuán)塊狀時(shí)應(yīng)做核磁強(qiáng)化檢查除外腫瘤性疾病[15, 26]。此外還需要與胼胝體變性鑒別，如果患者存在長(zhǎng)期的飲酒史，同時(shí)出現(xiàn)急性、亞急性或慢性的神經(jīng)系統(tǒng)癥狀，則需要臨床醫(yī)師考慮到變性疾病[27]。同時(shí)胼胝體多發(fā)性硬化及外傷也需與之相鑒別。

(9)

對(duì)于邊長(zhǎng)為l的正方形監(jiān)測(cè)區(qū)域而言,當(dāng)目標(biāo)節(jié)點(diǎn)始終處于傳感器節(jié)點(diǎn)覆蓋區(qū)域時(shí),其整個(gè)網(wǎng)絡(luò)的覆蓋率為

(10)

定理2 在扇形監(jiān)測(cè)區(qū)域內(nèi),移動(dòng)目標(biāo)節(jié)點(diǎn)被傳感器節(jié)點(diǎn)聯(lián)合覆蓋的期望值為E(X)=πθ(σ2+l2)/l2。

證明 以圖1網(wǎng)絡(luò)模型作為研究對(duì)象。邊長(zhǎng)為l的正方形作為監(jiān)測(cè)區(qū)域,傳感器節(jié)點(diǎn)扇面作為有效覆蓋區(qū)域,θ是扇面夾角之和;由于傳感器節(jié)點(diǎn)的感知半徑R服從于正態(tài)分布N(l,σ2),對(duì)于正方形監(jiān)測(cè)區(qū)域來(lái)說(shuō),其覆蓋期望值為

(11)

令x=(R-l)/σ,則

dR=σdx

(12)

將式(12)代入式(11)得

(13)

證畢。

推論2 滿足一定覆蓋率的前提下,使用最少數(shù)量的傳感器節(jié)點(diǎn)完成對(duì)監(jiān)測(cè)區(qū)域的聯(lián)合覆蓋時(shí),相應(yīng)的覆蓋期望值是(1-ε)/ln(1-πθ(σ2+l2)/l2)。

(14)

若覆蓋集中存在n個(gè)工作節(jié)點(diǎn),對(duì)監(jiān)測(cè)區(qū)域內(nèi)任意目標(biāo)節(jié)點(diǎn)構(gòu)成聯(lián)合覆蓋所產(chǎn)生的期望值為

(15)

在滿足一定覆蓋質(zhì)量時(shí),必存在一個(gè)極小的數(shù)ε,使得聯(lián)合覆蓋期望值小于ε時(shí),極限存在,即

(16)

解之得

(17)

即當(dāng)完成對(duì)監(jiān)測(cè)區(qū)域有效覆蓋時(shí),最少傳感器節(jié)點(diǎn)數(shù)覆蓋期望值是ln(1-ε)/ln(1-πθ(σ2+l2)/l2)。

證畢。

定理2和推論2給出了覆蓋期望值和聯(lián)合覆蓋期望值的計(jì)算過(guò)程。一般情況下,移動(dòng)目標(biāo)節(jié)點(diǎn)所行進(jìn)的軌跡在監(jiān)測(cè)區(qū)域內(nèi)被傳感器節(jié)點(diǎn)所覆蓋時(shí)呈現(xiàn)出扇面形態(tài)。在計(jì)算覆蓋期望值時(shí),采用概率理論和數(shù)學(xué)幾何理論計(jì)算方法來(lái)完成。但是,對(duì)于移動(dòng)目標(biāo)節(jié)點(diǎn)首次進(jìn)入監(jiān)測(cè)區(qū)域時(shí),如何得到首次覆蓋期望值是必須解決的問(wèn)題。為此本文引入定理3。

定理3 傳感器節(jié)點(diǎn)首次完成對(duì)移動(dòng)目標(biāo)覆蓋時(shí),其覆蓋期望值為E(X)=[1-(1-p)M]p-1,其中M是移動(dòng)目標(biāo)節(jié)點(diǎn)完成轉(zhuǎn)移最多的次數(shù),p是傳感器節(jié)點(diǎn)的覆蓋率。

證明 根據(jù)概率理論可知,設(shè)隨機(jī)變量X為移動(dòng)目標(biāo)節(jié)點(diǎn)轉(zhuǎn)移的次數(shù),則X的可能取值范圍是X∈[1,2,3,…,M],當(dāng)X=m、且滿足1≤m≤M-1時(shí),即前M-1次移動(dòng)目標(biāo)節(jié)點(diǎn)并沒(méi)有被傳感器節(jié)點(diǎn)所覆蓋,得X的分布密度函數(shù)為

(18)

由覆蓋期望公式可得

(19)

(20)

將式(20)代入式(19)可得

[1-(1-p)M]p-1

(21)

證畢。

2 算法描述與分析

2.1 能量轉(zhuǎn)換

在正方形監(jiān)測(cè)區(qū)域內(nèi),經(jīng)過(guò)一個(gè)或多個(gè)周期后,由于工作節(jié)點(diǎn)自身能量的消耗必然會(huì)引起覆蓋面積相應(yīng)的變化。為了更好地抑制傳感器節(jié)點(diǎn)能量的消耗,最大限度地延長(zhǎng)網(wǎng)絡(luò)生存周期,采用節(jié)點(diǎn)能量模型對(duì)多邊及單邊傳輸數(shù)據(jù)所消耗節(jié)點(diǎn)能量進(jìn)行分析,其節(jié)點(diǎn)發(fā)送端能量消耗模型為

(22)

接收端能量消耗模型為

(23)

式中:l為發(fā)送端與接收端之間傳輸數(shù)據(jù)的長(zhǎng)度;εfs為自由空間能耗;εamp為多路衰減能耗;ET和ER分別表示發(fā)送與接收單位數(shù)據(jù)長(zhǎng)度所消耗的能量;d代表通信節(jié)點(diǎn)之間的歐氏距離;d0是歐氏距離上限閾值,當(dāng)通信節(jié)點(diǎn)之間的距離小于d0時(shí),能量衰減指數(shù)為2,反之衰減指數(shù)為4;E3代表通信節(jié)點(diǎn)之間接收與發(fā)送模塊所消耗的能量[15]。

EBPCC算法借助于傳感器節(jié)點(diǎn)在感知半徑范圍內(nèi)的鄰居節(jié)點(diǎn)所形成的聯(lián)盟,將所有節(jié)點(diǎn)劃分成若干個(gè)聯(lián)盟,并以節(jié)點(diǎn)能量較高、計(jì)算能力和通信能力較強(qiáng)的節(jié)點(diǎn)當(dāng)作管理員節(jié)點(diǎn),其他節(jié)點(diǎn)稱之為成員節(jié)點(diǎn)。在網(wǎng)絡(luò)初始化階段,由于節(jié)點(diǎn)屬性相同,所以任意選取一個(gè)節(jié)點(diǎn)作為管理員節(jié)點(diǎn),成員節(jié)點(diǎn)首先發(fā)送一個(gè)“Coverage”消息到管理員節(jié)點(diǎn),管理員節(jié)點(diǎn)根據(jù)自身特性開(kāi)辟一定容量的存儲(chǔ)空間,并將收集來(lái)的信息存儲(chǔ)在開(kāi)辟空間的一個(gè)鏈表CL中,其中“Coverage”消息主要包含發(fā)送節(jié)點(diǎn)自身屬性和當(dāng)前狀態(tài),例如發(fā)送節(jié)點(diǎn)的能量變化情況、ID信息以及發(fā)送節(jié)點(diǎn)對(duì)關(guān)注節(jié)點(diǎn)覆蓋情況等。經(jīng)過(guò)一輪或幾輪周期后,管理員節(jié)點(diǎn)收集了該聯(lián)盟中所有節(jié)點(diǎn)的發(fā)送信息。管理員節(jié)點(diǎn)根據(jù)所收集來(lái)的各種信息按照剩余能量和覆蓋期望值大小對(duì)所有成員節(jié)點(diǎn)進(jìn)行排序,并將其存儲(chǔ)在鏈表中,對(duì)排序的所有節(jié)點(diǎn)賦予一定權(quán)值,使排名靠前節(jié)點(diǎn)的權(quán)值高于排名靠后節(jié)點(diǎn)的權(quán)值。管理員節(jié)點(diǎn)根據(jù)對(duì)目標(biāo)節(jié)點(diǎn)覆蓋情況從鏈表中依次查找符合條件的成員節(jié)點(diǎn),并標(biāo)記符合條件的成員節(jié)點(diǎn),同時(shí)向該成員節(jié)點(diǎn)發(fā)送“Notice”消息,以調(diào)度其他成員節(jié)點(diǎn)完成相應(yīng)的覆蓋任務(wù)。

2.2 EBPCC算法描述

EBPCC算法實(shí)現(xiàn)過(guò)程主要分為7個(gè)步驟。

步驟1 首先計(jì)算每個(gè)聯(lián)盟結(jié)構(gòu)中所有成員節(jié)點(diǎn)的覆蓋期望值,記作E(X)=∪{(si,L)|siN(l,σ2)/l2}。

步驟2 管理員節(jié)點(diǎn)將收集來(lái)的成員節(jié)點(diǎn)信息存儲(chǔ)在一個(gè)CL鏈表中,其中“Coverage”消息包含了發(fā)送節(jié)點(diǎn)的ID信息、能量信息和覆蓋期望值信息等。

步驟3 經(jīng)過(guò)一輪或幾輪周期后,管理員節(jié)點(diǎn)對(duì)所有存儲(chǔ)在鏈表中的成員節(jié)點(diǎn)信息以剩余能量和覆蓋期望值大小進(jìn)行排序,并把較高的權(quán)值賦予排名靠前的成員節(jié)點(diǎn)。

步驟4 管理員節(jié)點(diǎn)對(duì)鏈表中成員節(jié)點(diǎn)是否覆蓋目標(biāo)節(jié)點(diǎn)進(jìn)行查找,并對(duì)符合條件的成員節(jié)點(diǎn)做標(biāo)記。

步驟5 管理員節(jié)點(diǎn)對(duì)鏈表中成員節(jié)點(diǎn)進(jìn)行查找,當(dāng)某個(gè)成員節(jié)點(diǎn)剩余能量高于上限閾值時(shí),則向其鄰居節(jié)點(diǎn)發(fā)送一個(gè)“Notice”消息,鄰居成員節(jié)點(diǎn)接收到“Notice”消息后,轉(zhuǎn)為啟動(dòng)狀態(tài),同時(shí)啟動(dòng)感知模塊對(duì)監(jiān)測(cè)區(qū)域進(jìn)行覆蓋。

步驟6 如果存在一個(gè)目標(biāo)節(jié)點(diǎn)同時(shí)被k個(gè)成員節(jié)點(diǎn)所覆蓋時(shí),管理員節(jié)點(diǎn)則會(huì)重新遍歷鏈表,查找滿足覆蓋要求的成員節(jié)點(diǎn),并將該成員節(jié)點(diǎn)關(guān)閉。

步驟7 管理員節(jié)點(diǎn)完成對(duì)鏈表遍歷后,通過(guò)自適應(yīng)調(diào)度機(jī)制查找滿足下一輪覆蓋條件的傳感器節(jié)點(diǎn),并利用該節(jié)點(diǎn)完成對(duì)監(jiān)測(cè)區(qū)域的下一輪覆蓋,否則轉(zhuǎn)向步驟2。

2.3 復(fù)雜度分析

定理4 在理想狀態(tài)下EBPCC算法的算法復(fù)雜度為O(n),非理想狀態(tài)下的算法復(fù)雜度為O(n2)。

證明 EBPCC算法通過(guò)發(fā)送與接收不同類型信息來(lái)完成對(duì)成員節(jié)點(diǎn)之間的能量轉(zhuǎn)換,并通過(guò)查找鏈表方式,獲取最佳節(jié)點(diǎn)完成后續(xù)覆蓋。如果EBPCC算法在一個(gè)周期內(nèi)或小于一個(gè)周期完成對(duì)監(jiān)測(cè)區(qū)域覆蓋,則其算法復(fù)雜度為O(n),當(dāng)EBPCC算法運(yùn)行時(shí)間大于一個(gè)周期或小于最大周期時(shí),則需完成n次循環(huán)覆蓋過(guò)程,即最差算法復(fù)雜度為O(n2)。證畢。

3 體系評(píng)估

為了驗(yàn)證EBPCC算法的有效性和穩(wěn)定性,本文采用Matlab7作為仿真平臺(tái),與文獻(xiàn)[14]和文獻(xiàn)[15]中的算法進(jìn)行對(duì)比。

實(shí)驗(yàn)1 在延長(zhǎng)網(wǎng)絡(luò)生存周期上,將EBPCC算法與文獻(xiàn)[14]ETCA算法進(jìn)行對(duì)比,實(shí)驗(yàn)數(shù)據(jù)是200次仿真數(shù)據(jù)的平均值,如圖2～4所示。

圖2 100 m×100 m監(jiān)測(cè)區(qū)域內(nèi)EBPCC與ETCA算法的網(wǎng)絡(luò)生存周期對(duì)比

圖3 200 m×200 m監(jiān)測(cè)區(qū)域內(nèi)EBPCC與ETCA算法的網(wǎng)絡(luò)生存周期對(duì)比

圖4 300 m×300 m監(jiān)測(cè)區(qū)域內(nèi)EBPCC與ETCA算法的網(wǎng)絡(luò)生存周期對(duì)比

實(shí)驗(yàn)1是在不同監(jiān)測(cè)區(qū)域下,EBPCC算法與ETCA算法在網(wǎng)絡(luò)生存周期上的對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)中k取不同的數(shù)值,通過(guò)改變隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)數(shù)來(lái)改變網(wǎng)絡(luò)規(guī)模。對(duì)于規(guī)模較小的監(jiān)測(cè)區(qū)域來(lái)說(shuō),隨機(jī)部署的節(jié)點(diǎn)數(shù)初始值為15,并以15作為單位基數(shù),逐步遞增。通過(guò)仿真圖3可以看出：無(wú)線傳感器網(wǎng)絡(luò)的生存周期隨著傳感器節(jié)點(diǎn)數(shù)的增加而呈線性上升趨勢(shì),主要原因是在傳感器節(jié)點(diǎn)集合中的成員節(jié)點(diǎn)通過(guò)節(jié)點(diǎn)的調(diào)度機(jī)制輪流對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行覆蓋,延長(zhǎng)了網(wǎng)絡(luò)生存周期;對(duì)于規(guī)模較小的100m×100m和200m×200m網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域來(lái)說(shuō),在相同的網(wǎng)絡(luò)參數(shù)作用下,EBPCC算法比ETCA算法的網(wǎng)絡(luò)生存周期平均延長(zhǎng)了11.71%、13.89%;對(duì)于規(guī)模較大的網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域,隨機(jī)部署的節(jié)點(diǎn)數(shù)初始值為150,并以50作為單位基數(shù),逐步遞增,網(wǎng)絡(luò)生存周期變化曲線隨著傳感器節(jié)點(diǎn)數(shù)的遞增也呈現(xiàn)出上升趨勢(shì),其上升的幅度超過(guò)小規(guī)模網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域,與ETCA算法相比,網(wǎng)絡(luò)生存周期平均提高了13.19%。綜合上述3種情況,本文算法的網(wǎng)絡(luò)生存周期平均提高了12.91%。

實(shí)驗(yàn)2 將EBPCC算法與文獻(xiàn)[15]所提出的EPDM算法在覆蓋率方面進(jìn)行對(duì)比。以200m×200m網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域?yàn)槔?實(shí)驗(yàn)數(shù)據(jù)是200次仿真數(shù)據(jù)的平均值,結(jié)果如圖5、6所示。

圖5 200 m×200 m監(jiān)測(cè)區(qū)域內(nèi)EBPCC與EPDM算法的覆蓋率對(duì)比

圖6 200 m×200 m監(jiān)測(cè)區(qū)域內(nèi)網(wǎng)絡(luò)運(yùn)行時(shí)間與覆蓋率對(duì)比圖

在圖5中,隨著傳感器節(jié)點(diǎn)數(shù)增加,其覆蓋率也呈現(xiàn)遞增變化。當(dāng)EBPCC算法覆蓋率達(dá)到99.9%時(shí)，對(duì)應(yīng)不同k值時(shí)的傳感器節(jié)點(diǎn)數(shù)分別是:k=2時(shí),N=144;k=3時(shí),N=137;k=4時(shí),N=126,而EPDM算法覆蓋率在N=126時(shí)，尚未達(dá)到99.9%,這說(shuō)明本文EBPCC算法的覆蓋率要高于EPDM算法。由圖6可以看出,初始時(shí)刻2種算法覆蓋率基本相同,但是隨著時(shí)間的推移,EBPCC算法與EPDM算法的覆蓋率均呈現(xiàn)下降趨勢(shì),主要原因是EPDM算法在網(wǎng)絡(luò)運(yùn)行時(shí)間內(nèi)采用的是對(duì)監(jiān)測(cè)區(qū)域的目標(biāo)節(jié)點(diǎn)連續(xù)覆蓋,直到該節(jié)點(diǎn)能量消耗完畢為止。在t=150s時(shí),EBPCC算法與EPDM算法的覆蓋率下降較為明顯:EBPCC算法的覆蓋率分別為k=2時(shí)的40.24%,k=3時(shí)的64.05%,k=4時(shí)的82.19%;EPDM算法覆蓋率為75.13%。可以看出,在整個(gè)網(wǎng)絡(luò)生存周期內(nèi),EBPCC算法覆蓋率明顯高于EPDM算法,驗(yàn)證了本文算法的有效性。

4 總 結(jié)

本文在對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋特性分析的基礎(chǔ)上,提出了一種能量均衡參數(shù)可控的覆蓋算法(EBPCC)。該算法給出對(duì)監(jiān)測(cè)區(qū)域內(nèi)覆蓋期望值的計(jì)算方法,并在此基礎(chǔ)上,給出使用最少傳感器節(jié)點(diǎn)完成對(duì)監(jiān)測(cè)區(qū)域的期望值的求解過(guò)程,同時(shí)對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)完成首次覆蓋時(shí)的期望值也做了相應(yīng)的計(jì)算和推導(dǎo)。在能量方面,給出了抑制節(jié)點(diǎn)能量消耗的具體步驟與算法描述過(guò)程。最后,在不同參數(shù)k值的作用下,在網(wǎng)絡(luò)生存周期以及網(wǎng)絡(luò)覆蓋率2個(gè)方面與ETCA算法和EPDM算法進(jìn)行了仿真對(duì)比實(shí)驗(yàn),驗(yàn)證了EBPCC算法的有效性和穩(wěn)定性。今后的主要工作重點(diǎn)是實(shí)現(xiàn)在非線性規(guī)則區(qū)域?qū)Χ嗄繕?biāo)節(jié)點(diǎn)的有效覆蓋以及提高對(duì)監(jiān)測(cè)區(qū)域邊界的有效覆蓋。

[1] 魏全瑞, 劉俊, 韓九強(qiáng). 改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)無(wú)偏距離估計(jì)與節(jié)點(diǎn)定位算法 [J]. 西安交通大學(xué)學(xué)報(bào), 2014, 48(6): 1-6.WEIQuanrui,LIUJun,HANJiuqiang.AnimprovedDV-hoplocalizationalgorithmbasedonunbiasedestimationforwirelesssensornetworks[J].JournalofXi’anJiaotongUniversity, 2014, 48(6): 1-6.

[2] XING Xiaofei, WANG Guojun, LI Jie. Collaborative target tracking in wireless sensor networks [J]. Ad-hoc and Sensor Networks, 2014, 23(8): 117-135.

[3] YANG Changlin, CHIN Kwanwu. Novel algorithm for complete targets coverage in energy harvesting wireless sensor networks [J]. IEEE Communications Letters, 2014, 18(1): 118-121.

[4] 李孜, 高春玲, 孫澤宇, 等. 基于概率模型的無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化覆蓋算法 [J]. 光通信研究, 2015, 32(4): 68-71. LI Zi, GAO Chunling, SUN Zeyu, et al. Probability model-based optimization coverage algorithm for wireless sensor networks [J]. Study on Optical Communications, 2015, 32(4): 68-71.

[5] 畢冉, 李建中. 無(wú)線傳感器網(wǎng)絡(luò)中能量高效的Top-k監(jiān)測(cè)算法 [J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 51(11): 2361-2373. BI Ran, LI Jianzhong. Energy efficient top-kmonitoring algorithm in wireless sensor networks [J]. Journal of Computer Research and Development, 2015, 51(11): 2361-2373.

[6] 孫澤宇, 伍衛(wèi)國(guó), 王換招, 等. 無(wú)線傳感器網(wǎng)絡(luò)基于參數(shù)可調(diào)增強(qiáng)型覆蓋控制算法 [J]. 電子學(xué)報(bào), 2015, 43(3): 466-474.

SUN Zeyu, WU Weiguo, WANG Huanzhao, et al. An enhanced coverage control algorithm for wireless sensor networks based on adjustable parameters [J]. Acta Electronica Sinica, 2015, 43(3): 466-474.

[7] AMMARI H M, DAS S K. Centralized and clusteredk-coverage protocols for wireless sensor networks [J]. IEEE Transactions on Computers, 2012, 61(1): 118-132.

[8] SEOK J H, LEE J Y, KIM W, et al. A bipopulation-based evolutionary algorithm for solving full area coverage problems [J]. IEEE Sensors Journal, 2014, 13(12): 4796-4807.

[9] YANG Changlin, CHIN K W. Novel algorithms for complete targets coverage in energy harvesting wireless sensor networks [J]. IEEE Communications Letters, 2014, 18(1): 118-121.

[10]MINI S, UDGATE S, SABAT S. Sensor deployment and scheduling for target coverage problem in wireless sensor networks [J]. IEEE Sensors Journal, 2014, 14(3): 636-644.

[11]CHENG T M, SAVKIN A V. A distributed self-deployment algorithm for the coverage of mobile wireless sensor networks [J]. IEEE Communications Letters, 2009, 13(11): 877-879.

[12]SUN Zeyu, LI Heng, CHEN Heng, et al. Optimization coverage of wireless sensor networks based on energy saving [J]. International Journal of Future Generation Communication and Networking, 2014, 7(4): 35-48.

[13]孟凡治, 王換招, 何暉. 基于聯(lián)合感知模型的無(wú)線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議 [J]. 電子學(xué)報(bào), 2011, 39(4): 772-779. MENG Fanzhi, WANG Huanzhao, HE Hui. Connected coverage protocol using cooperative sensing model for wireless sensor networks [J]. Acta Electronica Sinica, 2011, 39(4): 772-779.

[14]XING Xiaofei, WANG Guojun, LI Jie. Polytype target coverage scheme for heterogeneous wireless sensor networks using linear programming [J]. Wireless Communications and Mobile Computing, 2014, 14(8): 1397-1408.

[15]SUN Zeyu, WU Weiguo, WANG Huanzhao, et al. A novel coverage algorithm based on event-probability-driven mechanism in wireless sensor network [J]. Eurasip Journal on Wireless Communications and Networking, 2014, 2014(1): 1-17.

(編輯 武紅江)

EBPCC: Energy Balance Parameters-Controlled Covering Algorithm for Wireless Sensor Networks

SUN Zeyu1,2,WU Weiguo1,CAO Yangjie3,XING Xiaofei4

(1. School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 2. School of Computer and Information Engineering, Luoyang Institute of Science and Technology, Luoyang, Henan 471023, China; 3. School of Software and Application Science Technology, Zhengzhou University, Zhengzhou 450001, China; 4. School of Computer Science and Software Engineering, Guangzhou University, Guangzhou 510006, China)

An energy balance parameters-controlled covering algorithm for wireless sensor networks is proposed to improve the insufficiencies that network jam due to the redundant data generated during thek-coverage process of target nodes leads to the reduction in network’s capabilities of communication and coverage as well as the rapid consumption of network energy. A network coverage model is constructed by using the location relationship of nodes, and the model is then analyzed to provide the expectation value of nodes within the monitored region and the computing process of the minimum nodes required for covering the whole monitored region. The proportional relation of energy conversion functions between the working nodes and the neighboring nodes is given, and is used to dispatch nodes with low energy and to balance energy consumption of the whole network. Experimental results show that the proposedk-degree coverage algorithm improves the network’s coverage quality and cuts down the rapid network nodes energy consumption, and that in the same monitoring environment, the network lifetime with the EBPCC algorithm is 12.91% longer than that with the ETCA and the coverage rate is 7.06% larger than that with EPDM.

wireless sensor network;k-degree coverage; coverage rate; network lifetime; energy balance

10.7652/xjtuxb201608013

2016-03-23。 作者簡(jiǎn)介:孫澤宇(1977—),男,博士生,副教授;伍衛(wèi)國(guó)(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(U1304603);國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2014AA01A302);河南省重點(diǎn)科技攻關(guān)計(jì)劃資助項(xiàng)目(142102210471,1621002210113);河南省教育廳自然科學(xué)基金重點(diǎn)資助項(xiàng)目(14B520099)。

時(shí)間:2016-06-27

http:∥www.cnki.net/kcms/detail/61.1069.T.20160627.1231.004.html

TP393

A

0253-987X(2016)08-0077-07