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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

1.1 基本定義

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

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

(1)

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

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

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

(2)

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

(3)

解之得

(4)

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

(5)

證畢。

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

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

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

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

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

(6)

經(jīng)計算

(7)

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

證畢。

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

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

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

(8)

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

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

(9)

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

(10)

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

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

(11)

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

dR=σdx

(12)

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

(13)

證畢。

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

(14)

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

(15)

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

(16)

解之得

(17)

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

證畢。

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

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

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

(18)

由覆蓋期望公式可得

(19)

(20)

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

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

(21)

證畢。

2 算法描述與分析

2.1 能量轉(zhuǎn)換

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

(22)

接收端能量消耗模型為

(23)

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

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

2.2 EBPCC算法描述

EBPCC算法實現(xiàn)過程主要分為7個步驟。

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

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

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

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

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

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

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

2.3 復雜度分析

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

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

3 體系評估

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

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

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

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

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

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

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

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

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

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

4 總 結(jié)

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

[1] 魏全瑞, 劉俊, 韓九強. 改進的無線傳感器網(wǎng)絡(luò)無偏距離估計與節(jié)點定位算法 [J]. 西安交通大學學報, 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ǎ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ǎng)絡(luò)中能量高效的Top-k監(jiān)測算法 [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)國, 王換招, 等. 無線傳感器網(wǎng)絡(luò)基于參數(shù)可調(diào)增強型覆蓋控制算法 [J]. 電子學報, 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ǎng)絡(luò)連通性覆蓋協(xié)議 [J]. 電子學報, 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。 作者簡介:孫澤宇(1977—),男,博士生,副教授;伍衛(wèi)國(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(U1304603);國家高技術(shù)研究發(fā)展計劃資助項目(2014AA01A302);河南省重點科技攻關(guān)計劃資助項目(142102210471,1621002210113);河南省教育廳自然科學基金重點資助項目(14B520099)。

時間:2016-06-27

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

TP393

A

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