秦寧寧，陳家樂(lè)，丁志國(guó)

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫 214122；2.江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫 214122；3.紐卡斯?fàn)柎髮W(xué)電氣電子和計(jì)算機(jī)工程系，英國(guó)紐卡斯?fàn)朜E17RU）

覆蓋率均衡區(qū)域覆蓋算法*

秦寧寧1，2*，陳家樂(lè)1，丁志國(guó)2，3

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫 214122；2.江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫 214122；3.紐卡斯?fàn)柎髮W(xué)電氣電子和計(jì)算機(jī)工程系，英國(guó)紐卡斯?fàn)朜E17RU）

為了進(jìn)一步實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)生命周期的最大化，針對(duì)網(wǎng)絡(luò)中能量均勻且均衡覆蓋問(wèn)題展開研究，提出覆蓋率均衡區(qū)域覆蓋算法BRACA（Balanced Rate Area Coverage Algorithm）。該算法引入覆蓋率均衡思想，將各傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域覆蓋率的均衡性與節(jié)點(diǎn)剩余能量的均衡性作為篩選因子，且通過(guò)調(diào)節(jié)傳感器節(jié)點(diǎn)的剩余能量與其平均覆蓋率的比例關(guān)系，篩選出最大不相關(guān)且代價(jià)最小的網(wǎng)絡(luò)覆蓋子集，以盡可能少的節(jié)點(diǎn)實(shí)現(xiàn)對(duì)區(qū)域的覆蓋。經(jīng)對(duì)比實(shí)驗(yàn)驗(yàn)證，算法BRACA具有更高的計(jì)算效率，所生成的ε-覆蓋子集，以更少且更均衡的能量消耗，保證了網(wǎng)絡(luò)覆蓋率≥90%，有效地延長(zhǎng)了網(wǎng)絡(luò)生命周期。

無(wú)線傳感器網(wǎng)絡(luò)；覆蓋率均衡；ε-覆蓋；覆蓋子集

在目標(biāo)區(qū)域內(nèi)，大量隨機(jī)布撒微型傳感器節(jié)點(diǎn)可以實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域的監(jiān)測(cè)。通常這些傳感器節(jié)點(diǎn)以能量有限的電池為供給。一方面，以此來(lái)提高網(wǎng)絡(luò)覆蓋的靈活性；但另一方面，如何高效利用能量、延長(zhǎng)網(wǎng)絡(luò)生命周期［1-3］的問(wèn)題也伴隨而來(lái)。通過(guò)調(diào)度部分傳感器節(jié)點(diǎn)［4-5］對(duì)監(jiān)測(cè)區(qū)域進(jìn)行覆蓋，合理地均衡節(jié)點(diǎn)的能量損耗，擴(kuò)展網(wǎng)絡(luò)生命周期，是目前主要解決方式。

區(qū)域覆蓋［6］是無(wú)線傳感器網(wǎng)絡(luò)熱點(diǎn)研究方向之一，側(cè)重于實(shí)現(xiàn)解決給定區(qū)域內(nèi)的全覆蓋問(wèn)題。從微觀角度而言，區(qū)域覆蓋中的目標(biāo)區(qū)域內(nèi)存在無(wú)窮多的目標(biāo)點(diǎn)，將無(wú)限目標(biāo)點(diǎn)轉(zhuǎn)化為有限目標(biāo)點(diǎn)是實(shí)現(xiàn)區(qū)域覆蓋的關(guān)鍵。Xing［7］曾將目標(biāo)區(qū)域劃分為有限個(gè)網(wǎng)格，保證每個(gè)網(wǎng)格頂點(diǎn)的覆蓋率，以此來(lái)達(dá)到整個(gè)區(qū)域覆蓋。該方法作為近似覆蓋求解，在一定程度上降低了計(jì)算復(fù)雜度，但不適用于更精確的網(wǎng)格劃分和覆蓋要求且實(shí)際上僅保證網(wǎng)格頂點(diǎn)的覆蓋率無(wú)法正真保證區(qū)域覆蓋。文獻(xiàn)［8］基于概率感知模型下，提出激活部分傳感器節(jié)點(diǎn)近似構(gòu)成若干個(gè)等邊三角形的頂點(diǎn)，相鄰傳感器節(jié)點(diǎn)的間距近似為2倍的感知距離，以此覆蓋整個(gè)區(qū)域。但該算法不適于隨機(jī)布撒情形，無(wú)法保證激活的傳感器節(jié)點(diǎn)都形成近似三角形。文獻(xiàn)［9］提出ε-覆蓋算法，研究了相鄰兩節(jié)點(diǎn)概率間的數(shù)學(xué)關(guān)系。目標(biāo)區(qū)域任意錨點(diǎn)pj的覆蓋率為εeKRj，那么以錨點(diǎn)為中心，Rj為半徑的圓內(nèi)，任意目標(biāo)點(diǎn)的覆蓋率不低于ε。由此將無(wú)限點(diǎn)的區(qū)域覆蓋問(wèn)題轉(zhuǎn)化為對(duì)有限點(diǎn)覆蓋的點(diǎn)覆蓋問(wèn)題，實(shí)現(xiàn)目標(biāo)區(qū)域ε-覆蓋。該文中采用貪婪算法思想激活傳感器節(jié)點(diǎn)，保證每一個(gè)錨點(diǎn)的覆蓋率。該方法在對(duì)每個(gè)錨點(diǎn)覆蓋率間的均衡性問(wèn)題考慮有所欠缺，導(dǎo)致目標(biāo)區(qū)域會(huì)存在非均衡覆蓋、大量節(jié)點(diǎn)冗余且相關(guān)、節(jié)點(diǎn)間能量消耗非均衡、網(wǎng)絡(luò)生命周期略短。

基于此，本文提出了覆蓋率均衡區(qū)域覆蓋算法BRACA（Balanced Rate Area Coverage Algorithm），解決目標(biāo)區(qū)域內(nèi)有限個(gè)錨點(diǎn)部署與錨點(diǎn)覆蓋率間的均衡性以及傳感器節(jié)點(diǎn)間剩余能量的均衡性問(wèn)題，以此實(shí)現(xiàn)目標(biāo)區(qū)域均衡覆蓋，延長(zhǎng)網(wǎng)絡(luò)壽命。該算法引入覆蓋率均衡思想，結(jié)合各個(gè)傳感器節(jié)點(diǎn)的剩余能量，同時(shí)考慮節(jié)點(diǎn)能量的均衡性和節(jié)點(diǎn)間的相關(guān)性，進(jìn)一步降低節(jié)點(diǎn)間冗余性，保證目標(biāo)區(qū)域覆蓋率盡量均衡，以有效地延長(zhǎng)網(wǎng)絡(luò)的生命周期。

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

1.1 網(wǎng)絡(luò)描述

假設(shè)目標(biāo)區(qū)域A為二維平面，在該區(qū)域上隨機(jī)投放NS個(gè)物理性能均一的傳感器節(jié)點(diǎn)和均勻設(shè)置NI個(gè)錨點(diǎn)位置，所有節(jié)點(diǎn)坐標(biāo)已知，且傳感器的感知半徑為r，通信半徑均為Rc，為保證網(wǎng)絡(luò)覆蓋同時(shí)兼顧通信連通性，設(shè)置通信半徑Rc為感知半徑r的兩倍，即Rc=2r［10］。則傳感器節(jié)點(diǎn)集為：S=｛s1，s2，…，si，…，sNS｝，其中si=｛xSi，ySi，r｝表示節(jié)點(diǎn)坐標(biāo)（xSi，ySi）為圓心，探測(cè)半徑為r；錨點(diǎn)集：P=｛p1，p2，…，pj，…，pNI｝。

傳感器網(wǎng)絡(luò)的運(yùn)行時(shí)間（生命周期）劃分為TS個(gè)單位時(shí)間片刻tS，顯然網(wǎng)絡(luò)的生命周期為TStS。不產(chǎn)生歧義的情況下，以單位時(shí)間片刻tS的總個(gè)數(shù)TS為網(wǎng)絡(luò)的生命周期。在每個(gè)單位時(shí)間片刻tS內(nèi)，處于激活狀態(tài)的傳感器節(jié)點(diǎn)消耗固定的能量，休眠傳感器節(jié)點(diǎn)能量消耗忽略不計(jì)。

1.2 節(jié)點(diǎn)代價(jià)

傳感器節(jié)點(diǎn)si的權(quán)重值為其能量消耗的代價(jià)ci，該值隨著節(jié)點(diǎn)能量消耗的增長(zhǎng)而增加［11］，故ci可定義如下：

式中：k為傳感器的一個(gè)特征常量且k∈（0，1）。ER，i代表傳感器節(jié)點(diǎn)si的剩余能量。

在給定單位時(shí)間片刻tS內(nèi)，調(diào)度算法遞歸地選擇出滿足覆蓋精度、目標(biāo)區(qū)域覆蓋率均衡且代價(jià)和最小的傳感器集合H。顯然，為了實(shí)現(xiàn)能量代價(jià)最小、生命周期最長(zhǎng)的目標(biāo)，調(diào)度時(shí)應(yīng)優(yōu)先激活剩余能量多且不相關(guān)的傳感器節(jié)點(diǎn)，以構(gòu)成集合H。

1.3 ε-覆蓋

1.4 覆蓋模型與判決

傳感器節(jié)點(diǎn)采用概率感知模型。目標(biāo)pj被傳感器節(jié)點(diǎn)si探測(cè)到的概率為：

式中：d（si，pj）=d（i，j）為傳感器節(jié)點(diǎn)si與目標(biāo)pj之間的無(wú)向歐式距離。令rs=r-re，re為傳感器節(jié)點(diǎn)在感應(yīng)目標(biāo)過(guò)程中不確定度量值，a是根據(jù)d（i，j）變化時(shí)，傳感器感應(yīng)質(zhì)量的衰減系數(shù)［12］。

錨點(diǎn)pj被若干個(gè)傳感器節(jié)點(diǎn)同時(shí)感應(yīng)到的概率為：

式中：Sj為覆蓋到錨點(diǎn)pj的傳感器節(jié)點(diǎn)子集，顯然Sj?S。其中ε'（pj）=εeKRj為目標(biāo)區(qū)域錨點(diǎn)覆蓋率閾值。只要滿足式（4），錨點(diǎn)pj就認(rèn)定為被傳感器網(wǎng)絡(luò)所覆蓋［13］，且目標(biāo)區(qū)域覆蓋率不低于ε。

1.5 問(wèn)題描述

傳感器網(wǎng)絡(luò)均衡覆蓋問(wèn)題可描述為：在目標(biāo)區(qū)域中，選取不相關(guān)且盡可能小的代價(jià)、能量均衡的傳感器節(jié)點(diǎn)構(gòu)成網(wǎng)絡(luò)覆蓋子集，以盡可能長(zhǎng)的生命周期均衡地覆蓋目標(biāo)區(qū)域，即滿足：

式中：αij=-ln（1-λsi（pj））。xi代表傳感器節(jié)點(diǎn)si是否被激活，激活則取值為1，反之為0。參數(shù)δ與覆蓋率閾值 ε'（pj）相關(guān)，存在 δ=-ln（1-ε'（pj））。式（6）描述了每個(gè)錨點(diǎn)在滿足給定的網(wǎng)絡(luò)覆蓋率的情況下，所需最少傳感器節(jié)點(diǎn)數(shù)目［11，14］。即目標(biāo)區(qū)域任意點(diǎn)的覆蓋率不低于ε精度下，需要激活最少傳感器節(jié)點(diǎn)的數(shù)目。

2 BRACA算法

2.1 個(gè)數(shù)板

在一個(gè)單位時(shí)間片刻tS，假設(shè)已知當(dāng)前NI個(gè)錨點(diǎn)被若干個(gè)傳感器節(jié)點(diǎn)同時(shí)感應(yīng)的聯(lián)合覆蓋率λ（pj），將其與閾值ε'（pj）對(duì)比分析，求出下一輪次欲激活傳感器節(jié)點(diǎn)理想的錨點(diǎn)覆蓋率增量分布趨勢(shì)。即上一輪中，聯(lián)合覆蓋率較高的錨點(diǎn)將在下一輪中獲得較低的聯(lián)合覆蓋率增量；而上一輪中，聯(lián)合覆蓋率較低的錨點(diǎn)將在下一輪中獲得較高的聯(lián)合覆蓋率增量，以此達(dá)到目標(biāo)區(qū)域均衡的覆蓋率。假設(shè)下一輪次需覆蓋率增量較大的NM個(gè)錨點(diǎn)集合PA= ｛pj，pj+1，…，pj+n，…，pj+NM-1｝，下一輪次需覆蓋率增量較小的錨點(diǎn)集PB=｛pjj，pjj+1，…，pjj+n，…，pjj+NM-1｝。處于休眠狀態(tài)的傳感器節(jié)點(diǎn)將其對(duì)PA集合各個(gè)錨點(diǎn)的覆蓋率與PB集合各個(gè)錨點(diǎn)的覆蓋率對(duì)應(yīng)做差，定義差值大于0的個(gè)數(shù)總和為個(gè)數(shù)板，如下：

式中：xn+1的值代表傳感器節(jié)點(diǎn)si對(duì)集合PA中錨點(diǎn)pj+n的覆蓋率是否大于對(duì)集合PB中錨點(diǎn)pjj+n的覆蓋率。若大于，則xn+1=1，反之，xn+1=0。且S'為休眠傳感器節(jié)點(diǎn)集合，顯然S'?S。

2.2 質(zhì)量素

以質(zhì)量素概念表征傳感器節(jié)點(diǎn)的價(jià)值。設(shè)當(dāng)前為第TS個(gè)時(shí)間片刻，每個(gè)傳感器節(jié)點(diǎn)si的質(zhì)量素ΓS，i（TS）=ρS，i（TS）·ER，i（TS）τ，其中ρS，i（TS）是指在第TS個(gè)時(shí)間片刻時(shí)，個(gè)數(shù)板NB（i）＞0的傳感器節(jié)點(diǎn)si所對(duì)應(yīng)集合PA中NM個(gè)錨點(diǎn)的平均覆蓋率。ER，i（TS）為在第TS個(gè)時(shí)間片刻，傳感器節(jié)點(diǎn)si的剩余能量。參數(shù)τ用于調(diào)節(jié)剩余能量在質(zhì)量素中所占比例，τ越大，相應(yīng)節(jié)點(diǎn)的剩余能量在網(wǎng)絡(luò)中發(fā)揮的作用越大。

2.3 錨點(diǎn)部署與覆蓋半徑

根據(jù)ε-覆蓋定義可知，若錨點(diǎn)位置確定且任意錨點(diǎn)的覆蓋率都不低于ε'（pj），則目標(biāo)區(qū)域內(nèi)任意點(diǎn)的覆蓋率不低于ε，因此錨點(diǎn)的部署是解決問(wèn)題的關(guān)鍵。根據(jù)各個(gè)錨點(diǎn)覆蓋率閾值ε'（pj）是否均一，可將錨點(diǎn)分為同構(gòu)錨點(diǎn)和異構(gòu)錨點(diǎn)。

圖1 同構(gòu)錨點(diǎn)部署

圖2 異構(gòu)錨點(diǎn)部署

2.4 新算法流程

傳感器網(wǎng)絡(luò)的生命周期劃分為TS個(gè)時(shí)間片刻。在每個(gè)時(shí)間片刻初始時(shí)，NS個(gè)傳感器節(jié)點(diǎn)處于休眠狀態(tài)，假設(shè)存在MP個(gè)選手各自獨(dú)立地在各自時(shí)間片內(nèi)選擇節(jié)點(diǎn)激活。各選手結(jié)合個(gè)數(shù)板和質(zhì)量素，依據(jù)目標(biāo)區(qū)域覆蓋率均衡原則，每輪激活一個(gè)傳感器節(jié)點(diǎn)。若干輪次后，所有錨點(diǎn)均衡地滿足給定的網(wǎng)絡(luò)覆蓋率（式（6）），即達(dá)到區(qū)域覆蓋精度，由此確定當(dāng)前時(shí)間片刻各選手的網(wǎng)絡(luò)覆蓋子集。

每個(gè)時(shí)間片刻內(nèi)，哪個(gè)選手選取的網(wǎng)絡(luò)覆蓋子集代價(jià)最小，則為本時(shí)間片刻傳感器網(wǎng)絡(luò)區(qū)域覆蓋最佳方案。若每個(gè)時(shí)間片刻節(jié)點(diǎn)能量消耗固定，則可用各個(gè)選手手中的傳感器網(wǎng)絡(luò)所能支撐的時(shí)間片刻數(shù)目TS，表征傳感器網(wǎng)絡(luò)的生命長(zhǎng)度。具體新算法流程如表1所示。

表1 BRACA算法偽代碼

3 仿真分析

3.1 仿真環(huán)境

利用MATLAB仿真軟件環(huán)境，設(shè)定目標(biāo)區(qū)域A 為100 m×100 m的正方形區(qū)域，在同構(gòu)錨點(diǎn)部署下，劃分單位為1 m×1 m，而在異構(gòu)錨點(diǎn)部署下，其劃分單位為10 m×10 m子區(qū)域。傳感器節(jié)點(diǎn)隨機(jī)布撒在這些網(wǎng)格中。傳感器網(wǎng)絡(luò)采用概率感知模型，每個(gè)傳感器節(jié)點(diǎn)初始能量均為1 J，每個(gè)時(shí)間片刻激活的傳感器節(jié)點(diǎn)均消耗0.1 J能量，即每個(gè)傳感器最多能維持10個(gè)時(shí)間片刻，網(wǎng)絡(luò)覆蓋率不低于90%。

為了證實(shí)BRACA——覆蓋率均衡區(qū)域覆蓋算法的有效性，將新算法與傳統(tǒng)粒子群算法（Particle Swarm Optimization）［15］、JOA（Jenga-Inspire Optimization Algorithm）［16］算法，在不同場(chǎng)景中進(jìn)行性能比較與分析。各算法參數(shù)如表2所示。

表2 3種算法參數(shù)

3.2 拓?fù)浣Y(jié)構(gòu)分析

圖3 為BRACA在傳感器節(jié)點(diǎn)NS=200時(shí)，同構(gòu)錨點(diǎn)和異構(gòu)錨點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。如圖3所示，同構(gòu)錨點(diǎn)在目標(biāo)區(qū)域內(nèi)均勻部署，而異構(gòu)錨點(diǎn)的部署間距與有效區(qū)域內(nèi)傳感器節(jié)點(diǎn)的個(gè)數(shù)及其平均剩余能量成正比，即有效區(qū)域內(nèi)節(jié)點(diǎn)的個(gè)數(shù)越多，平均剩余能量越大，錨點(diǎn)部署越稀疏；反之，有效區(qū)域內(nèi)節(jié)點(diǎn)的個(gè)數(shù)越少，平均剩余能量越小，錨點(diǎn)部署越密集。

圖3 NS=200下同構(gòu)和異構(gòu)錨點(diǎn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3.3 激活傳感器數(shù)分析

圖4為BRACA在7種不同傳感器節(jié)點(diǎn)NS場(chǎng)景下運(yùn)行1000次后，激活的傳感器節(jié)點(diǎn)數(shù)目。從實(shí)驗(yàn)結(jié)果可知，7個(gè)場(chǎng)景下，激活傳感器節(jié)點(diǎn)的平均數(shù)目徘徊在22左右，且激活傳感器節(jié)點(diǎn)的中位數(shù)均在10～22之間。在NS=100，150，200場(chǎng)景中，激活傳感器節(jié)點(diǎn)數(shù)呈上升趨勢(shì)；在NS=200場(chǎng)景下，激活傳感器節(jié)點(diǎn)數(shù)目達(dá)到巔峰值98。該場(chǎng)景下，傳感器節(jié)點(diǎn)資源利用率較低；在NS=250場(chǎng)景后，激活傳感器節(jié)點(diǎn)數(shù)整體呈下降趨勢(shì)。因?yàn)锽RACA算法在小規(guī)模傳感器網(wǎng)絡(luò)（即NS=250之前）中處于適應(yīng)階段，激活傳感器節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)規(guī)模呈正比，而在大規(guī)模傳感器網(wǎng)絡(luò)（即NS=250之后）中，新算法處于穩(wěn)定成熟階段，激活傳感器節(jié)點(diǎn)數(shù)的均值較小，新算法更適用于大規(guī)模傳感器網(wǎng)絡(luò)。

3.4 剩余能量分析

本實(shí)驗(yàn)統(tǒng)計(jì)了PSO、JOA與BRACA 3種智能算法在NS=200場(chǎng)景中，獨(dú)立運(yùn)行100次后，生命周期內(nèi)各個(gè)時(shí)間片刻的網(wǎng)絡(luò)平均剩余能量。如圖5所示，新算法BRACA在生命周期和能量消耗上，表現(xiàn)出明顯的優(yōu)越性。由于PSO將節(jié)點(diǎn)的剩余能量作為適應(yīng)度函數(shù)的因子，因此在平均剩余能量上，呈現(xiàn)出較為平緩的下降趨勢(shì)。JOA算法同時(shí)考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)間的生命素（即節(jié)點(diǎn)的剩余能量與節(jié)點(diǎn)覆蓋目標(biāo)點(diǎn)的個(gè)數(shù)的乘積），比PSO算法擁有更長(zhǎng)的生命周期。而BRACA提出質(zhì)量素ΓS，i（TS），引入覆蓋率均衡思想，通過(guò)合理地調(diào)節(jié)節(jié)點(diǎn)的平均覆蓋率及其剩余能量間的比例關(guān)系，間接地篩選出最大化不相關(guān)網(wǎng)絡(luò)覆蓋子集，有效地降低節(jié)點(diǎn)間能耗。由于大于100的生命周期為低概率事件，因此在100次獨(dú)立實(shí)驗(yàn)中該低概率引發(fā)了對(duì)整個(gè)網(wǎng)絡(luò)的剩余能量取平均擬合時(shí)，在圖中呈現(xiàn)出過(guò)度的不平滑，顯然該折滑不影響新算法在能量保持上的有效性。

圖5 NS=200場(chǎng)景中平均剩余能量分析

3.5 生命周期分析

3.5.1 3種算法生命周期對(duì)比分析

圖6統(tǒng)計(jì)了PSO、JOA、BRACA 3種智能算法的平均生命周期。實(shí)驗(yàn)表明：在不同的傳感器節(jié)點(diǎn)NS下，新算法BRACA比其他算法具有更長(zhǎng)的生命周期，尤其在大規(guī)模傳感器網(wǎng)絡(luò)（即NS=300以上）中，網(wǎng)絡(luò)壽命優(yōu)勢(shì)明顯。原因在于：新算法不僅引入覆蓋率均衡因素，還考慮傳感器節(jié)點(diǎn)的剩余能量，通過(guò)調(diào)節(jié)兩者間的比例關(guān)系，最大化篩選不相關(guān)且能量均衡的傳感器節(jié)點(diǎn)，保證了網(wǎng)絡(luò)壽命。

圖6 3種算法的生命周期分析

3.5.2 同構(gòu)和異構(gòu)錨點(diǎn)生命周期對(duì)比分析

圖7為新算法BRACA在NS=200場(chǎng)景中，同構(gòu)錨點(diǎn)和異構(gòu)錨點(diǎn)的網(wǎng)絡(luò)拓?fù)湓诓煌^點(diǎn)數(shù)下的生命周期。如圖7所示，傳感器網(wǎng)絡(luò)的生命周期與錨點(diǎn)數(shù)目呈正比，即隨著錨點(diǎn)數(shù)目的增加而增長(zhǎng)。且在同等錨點(diǎn)NI下，即相同計(jì)算復(fù)雜度，異構(gòu)錨點(diǎn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)比同構(gòu)錨點(diǎn)網(wǎng)絡(luò)拓?fù)渚哂懈L(zhǎng)的生命周期，原因在于異構(gòu)錨點(diǎn)網(wǎng)絡(luò)拓?fù)湟罁?jù)各子區(qū)域內(nèi)傳感器節(jié)點(diǎn)的個(gè)數(shù)及其剩余能量等因素來(lái)定義該子區(qū)域的覆蓋精度和錨點(diǎn)部署情況，進(jìn)一步合理地分配、利用網(wǎng)絡(luò)資源，延長(zhǎng)網(wǎng)絡(luò)壽命。

圖7 同構(gòu)與異構(gòu)對(duì)比分析

3.6 平均計(jì)算時(shí)間分析

圖8統(tǒng)計(jì)了不同傳感器節(jié)點(diǎn)NS下，PSO、JOA 和BRACA，3種算法的平均計(jì)算時(shí)間，以此考察各算法的運(yùn)行效率。顯而易見，JOA比PSO、BRACA算法具有更短的平均運(yùn)行時(shí)間。由于JOA算法的參數(shù)MP=4和NT=10，即4個(gè)選手各進(jìn)行10次遞歸篩選網(wǎng)絡(luò)覆蓋子集，因此該算法的復(fù)雜度一定程度上低于其他算法。PSO算法的運(yùn)行效率最低，新算法居中，主要是因?yàn)镻SO時(shí)間復(fù)雜度與種群大小、迭代次數(shù)以及每次迭代的運(yùn)算時(shí)間密切相關(guān)，且為3個(gè)算法中最高。而新算法BRACA時(shí)間復(fù)雜度與MP個(gè)選手、個(gè)數(shù)板NB（i）、質(zhì)量素ΓS，i（TS）、覆蓋率方差密切相關(guān)，并且后三者間層層遞進(jìn)，同時(shí)設(shè)置了參數(shù)αij的上限閾值，避免了無(wú)窮值之間的計(jì)算，減少了計(jì)算時(shí)間消耗。

圖8 多場(chǎng)景下的平均計(jì)算時(shí)間分析

4 結(jié)束語(yǔ)

本文提出覆蓋率均衡區(qū)域覆蓋算法，應(yīng)用于同構(gòu)錨點(diǎn)部署和異構(gòu)錨點(diǎn)部署兩種情形，實(shí)現(xiàn)目標(biāo)區(qū)域均衡高效覆蓋。該算法主要引入覆蓋率均衡思想，以最小代價(jià)覆蓋子集為目標(biāo)，將各傳感器節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域覆蓋率的均衡性影響作為篩選因子，結(jié)合各個(gè)傳感器節(jié)點(diǎn)的剩余能量，同時(shí)考慮節(jié)點(diǎn)能量的均衡性和節(jié)點(diǎn)間的相關(guān)性，降低節(jié)點(diǎn)間的冗余性，保證目標(biāo)區(qū)域覆蓋率盡量均衡。且在異構(gòu)錨點(diǎn)部署下，將目標(biāo)區(qū)域劃分為若干個(gè)子區(qū)域，各個(gè)子區(qū)域的覆蓋半徑與該區(qū)域內(nèi)傳感器的個(gè)數(shù)及其剩余能量相關(guān)，最大化地合理分配、利用傳感器節(jié)點(diǎn)，進(jìn)一步延長(zhǎng)網(wǎng)絡(luò)的生命周期。實(shí)驗(yàn)結(jié)果表明在保證不低于90%的覆蓋率下，BRACA新算法將維持更長(zhǎng)的傳感器網(wǎng)絡(luò)生命周期，實(shí)現(xiàn)資源的有效利用。

［1］ Sengupta S，Das S，Nasir M D，et al.Multi-Objective Node Deployment in WSNs：In Searchof anOptimal Trade-off Among Coverage，Lifetime，Energy Consumption，and Connectivity［J］. Engineering Applications of Artificial Intelligence，2013，26（1）：405-416.

［2］ 張品，沈政，董志遠(yuǎn).基于加權(quán)的無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化覆蓋算法［J］.傳感技術(shù)學(xué)報(bào)，2012，25（7）：993-998.

［3］ Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Networks：A Survey［J］.Computer Networks，2002，38（4）：393-422.

［4］ Anastasi G，Conti M，Di Francesco M.Extending the Lifetime of Wireless Sensor Networks through Adaptive Sleep［J］.IEEE Transactions on Industrial Informatics，2009，5（3）：351-365.

［5］ 張蕾.無(wú)線傳感器網(wǎng)絡(luò)中多重覆蓋算法的研究［J］.傳感技術(shù)學(xué)報(bào)，2014，27（6）：802-806.

［6］ Kasbekar G S，Bejerano Y，Sarkar S.Lifetime and Coverage Guarantees through Distributed Coordinate-Free Sensor Activation［J］. IEEE/ACM Transactions on Networking，2011，19（2）：470-483.

［7］ Xing G，Lu C，Pless R，et al.Co-Grid：an Efficient Coverage Maintenance Protocol for Distributed Sensor Networks［C］//Proc of the 3rd International Symposium on Information Processing in Sensor Networks，ACM，2004：414-423.

［8］ Hefeeda M，Ahmadi H.Energy-Efficient Protocol for Deterministic and Probabilistic Coverage in Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21（5）：579-593.

［9］ Yang Q，He S，Li J，et al.Energy-Efficient Probabilistic Full Coverage in Wireless Sensor Networks［C］//Global Communications Conference（GLOBECOM），2012 IEEE.Anaheim，2012：591-596.

［10］Zhu C，Zheng C L，Shu L，et al.A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks［J］.Journal of Network and Computer Applications，2012，35（2）：619-632.

［11］Chen J M，Li J K，He S B，et al.Energy-Efficient Coverage Based on Probabilistic Sensing Model in Wireless Sensor Networks［J］. IEEE Communications Letters，2010，14（9）：833-835.

［12］秦寧寧，蔣敏峰，熊偉麗，等.傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)感應(yīng)模型與相關(guān)工作的比較［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（9）：3480-3483.

［13］Huang J W，Hung C M，Yang K C，et al.Energy-Efficient Probabilistic Target Coverage in Wireless Sensor Networks［C］//Proc of the 2011 17th IEEE International Conference on Networks.IEEE Computer Society，Singapore，2011：53-58.

［14］Altunnel í K，Aras N，Güney E，et al.Binary Integer Programming Formulation and Heuristics for Differentiated Coverage in Heterogeneous Sensor Networks［J］.Computer Networks，2008，52（12）：2419-2431.

［15］Chen J，Li J，He S，et al.Energy-Efficient Coverage Based on Probabilistic Sensing Model in Wireless Sensor Networks［J］.IEEE Communications Letters，2010，14（9）：833-835.

［16］Lee J W，Lee J Y，Lee J J.Jenga-Inspired Optimization Algorithm for Energy-Efficient Coverage of Unstructured WSNs［J］.IEEE Wireless Communications Letters，2013，2（1）：34-37.

秦寧寧（1980-），女，江南大學(xué)副教授，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)覆蓋，ningning801108@163.com；

丁志國(guó)（1979-），男，江南大學(xué)教授，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)，z.ding@newcastle.ac.uk。

陳家樂(lè)（1988-），男，江南大學(xué)碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)覆蓋，jiangnanedu@live.com；

Balanced Rate Area Coverage Algorithm*

QIN Ningning1，2*，CHEN Jiale1，DING Zhiguo2，3
（1.School Of Internet of Things Engineering，Jiangnan University，Wuxi Jiangsu 214122，China；2.Key Laboratory of Advanced Process Control for Light Industry Ministry of Education，Jiangnan University，Wuxi Jiangsu 214122，China；3.Department of Electric Electron and Computer Engineering，School of Computing，Newcastle University，NE1 7RU，England）

In order to maximize lifetime of Wireless Sensor Networks（WSNs），a balanced rate area coverage algorithm（BRACA）is presented，which aims at the problem of energy uniformity and balanced coverage.This algorithm introduces the idea of balanced coverage rate.And it considers the sensors'balance about target area coverage rate and the residual energy as filtering factors.By adjusting the ratio of sensor's residual energy to its average coverage rate，we can find a sensor subset with maximum uncorrelation and minimum cost，which achieves area coverage using nodes as few as possible.Experimental results show that BRACA has better computational efficiency.The εcoverage sensor subset can prolong network lifetime effectively due to consuming the less and balanced energy in the premise of ensuring the network coverage of no less than 90%in the WSNs.

wireless sensor networks；balanced coverage rate；ε-coverage；subset of coverage EEACC：6150P

TP393

A

1004-1699（2015）04-0578-07

10.3969/j.issn.1004-1699.2015.04.021

項(xiàng)目來(lái)源：江蘇省“六大人才高峰”第十一批高層次人才項(xiàng)目（DZXX-026）；2014年國(guó)家公派高級(jí)研究學(xué)者及訪問(wèn)學(xué)者（含博士后）項(xiàng)目；國(guó)家自然科學(xué)基金項(xiàng)目（61304264）；江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目；江蘇省儀器平臺(tái)分析測(cè)試新技術(shù)新方法研究項(xiàng)目（蘇科儀辦［2014］1號(hào)）

2014-09-09 修改日期：2015-01-23