王廣超 王振榮

摘 要 在無線傳感器網(wǎng)絡(luò)中將傳感器節(jié)點(diǎn)通常部署在高密度、大規(guī)模目標(biāo)區(qū)域中，導(dǎo)致網(wǎng)絡(luò)覆蓋區(qū)域中大量節(jié)點(diǎn)相互重疊，同時網(wǎng)絡(luò)的可靠性和監(jiān)測質(zhì)量達(dá)不到預(yù)期的目標(biāo)。由于節(jié)點(diǎn)的相互重疊會導(dǎo)致數(shù)據(jù)在采集、傳輸產(chǎn)生大量冗余，從而導(dǎo)致消耗節(jié)點(diǎn)不必要的能量。為了解決此問題，提出了一種基于感知半徑調(diào)整算法ASRA（Adjustment Sensing Radius Algorithm），通過感知半徑對節(jié)點(diǎn)的調(diào)整，使網(wǎng)絡(luò)中的傳感節(jié)點(diǎn)能夠充分降低網(wǎng)絡(luò)的覆蓋冗余，盡可能地減少傳感節(jié)點(diǎn)在采集數(shù)據(jù)和傳輸過程中的能量消耗，從而延長網(wǎng)絡(luò)生存周期。

【關(guān)鍵詞】傳感器網(wǎng)絡(luò) 覆蓋控制 感知半徑調(diào)整

1 引言

無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)通常大規(guī)模、高密度部署且大量節(jié)點(diǎn)同時工作，節(jié)點(diǎn)的能量有限，這將會使節(jié)點(diǎn)的生存時間在網(wǎng)絡(luò)中變短，達(dá)不到預(yù)期的效果。因此，對節(jié)點(diǎn)合理的進(jìn)行調(diào)度是研究覆蓋控制的主要目標(biāo)。

在保證節(jié)點(diǎn)感知半徑的調(diào)整過程中對覆蓋網(wǎng)絡(luò)連通不產(chǎn)生任何影響的基礎(chǔ)上，為了有效提高節(jié)點(diǎn)的覆蓋控制提出了一種基于感知半徑調(diào)整算法ASRA（Adjustable Sensing Radius Algorithm），更大程度關(guān)閉網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)，盡可能的降低節(jié)點(diǎn)的能量消耗，讓各個節(jié)點(diǎn)相互協(xié)作，從而延長整個網(wǎng)絡(luò)的生存期。

2 感知半徑調(diào)整算法原理

在調(diào)整算法開始時，設(shè)節(jié)點(diǎn)O的最大感知半徑為R，節(jié)點(diǎn)O首先根據(jù)鄰居信息判斷感知圓是否為全約束狀態(tài)，若不是全約束狀態(tài)，則感知半徑仍為最大感知半徑，且保持不變，以盡可能的能力覆蓋μ鄰居集的覆蓋空洞區(qū)域。若具有全約束狀態(tài)，則計(jì)算出節(jié)點(diǎn)O的全部鄰居感知圓在該節(jié)點(diǎn)感知圓內(nèi)彼此兩兩相交所構(gòu)成的交點(diǎn)集合PointsSet。

若PointsSet中元素個數(shù)為零，則可判斷節(jié)點(diǎn)O的感知區(qū)域完全被其鄰居節(jié)點(diǎn)覆蓋，此時可以將節(jié)點(diǎn)O的感知半徑調(diào)整為零。當(dāng)各節(jié)點(diǎn)的最大感知半徑相等時，節(jié)點(diǎn)感知圓不具有全約束狀態(tài)且PointsSet中元素為零的情況不存在的，此處做一次判斷是為了盡可能的使算法兼顧最大感知半徑變化的情況。

若PointsSet中的元素個數(shù)不為零，則將PointsSet中的節(jié)點(diǎn)分為以下兩類：

（1）盲區(qū)頂點(diǎn)

（2）普通圓內(nèi)交點(diǎn)

如果PointsList中不存在空洞頂點(diǎn)，說明A的鄰居節(jié)點(diǎn)能夠完全覆蓋A的感知區(qū)域，此時，A的感知半徑可以調(diào)整為零。

若PointsSet中不存在盲區(qū)頂點(diǎn)，則說明O的感知區(qū)域能夠被μ的鄰居節(jié)點(diǎn)完全覆蓋，此時，O的感知半徑可以調(diào)整為零。

若PointsSet中存在盲區(qū)頂點(diǎn)，說明O的感知圓內(nèi)包含有μ鄰居集的覆蓋盲區(qū)，則可對節(jié)點(diǎn)O的感知半徑進(jìn)行調(diào)整。如圖1所示，在O的感知區(qū)域范圍內(nèi)由其鄰居集{O1，O2，O3，O4，O5，O6}形成閉合型盲區(qū)區(qū)域，記為φ，圍成φ的圓弧交點(diǎn)構(gòu)成盲區(qū)頂點(diǎn)記為P1，P2，...Pn。當(dāng)一個節(jié)點(diǎn)的感知圓處于全約束狀態(tài)即不存在自由圓弧時，可將該圓的感知半徑調(diào)整為該節(jié)點(diǎn)與內(nèi)部盲區(qū)節(jié)點(diǎn)距離中最遠(yuǎn)的距離，在此調(diào)整正中為全約束變化，不會產(chǎn)生新的覆蓋盲區(qū)。此時，節(jié)點(diǎn)O的最大感知半徑為Rmax，圓內(nèi)離O點(diǎn)最遠(yuǎn)的盲區(qū)頂點(diǎn)到O點(diǎn)的距離為d，在保證覆蓋盲區(qū)區(qū)域φ的不會導(dǎo)致新的覆蓋盲區(qū)的產(chǎn)生，可將節(jié)點(diǎn)O的感知半徑d調(diào)整為全約束狀態(tài)。在降低了網(wǎng)絡(luò)的冗余程度的同時減小了節(jié)點(diǎn)的感知半徑和能量消耗，從源頭上減少數(shù)據(jù)冗余。

3 算法詳細(xì)步驟

（1）首先搜尋μ鄰居節(jié)點(diǎn)集NBPOINTS的信息，使其節(jié)點(diǎn)信息相互交換信息，同時獲取所有μ鄰居節(jié)點(diǎn)的圓心坐標(biāo)和當(dāng)前感知半徑。

（2）查詢鄰居節(jié)點(diǎn)個數(shù)NBPOINTS.COUNT是否為零，如果為零則轉(zhuǎn)步驟7，如果不為零則轉(zhuǎn)3。

（3）判斷該節(jié)點(diǎn)的感知圓是否處于全約束狀態(tài)，如果存在則轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟3。

（4）計(jì)算在本圓內(nèi)所有鄰居節(jié)點(diǎn)的感知圓的交點(diǎn)集合PointsSet.COUNT，如果PointsSet.COUNT等于零，則轉(zhuǎn)步驟6；否則轉(zhuǎn)步驟5；

（5）在步驟4中計(jì)算本圓內(nèi)所有交點(diǎn)集合PointsSet，如果不存在盲區(qū)頂點(diǎn)，則轉(zhuǎn)步驟6；如果存在盲區(qū)頂點(diǎn)，則PointsSet.COUNT>0，則找出離該節(jié)點(diǎn)最遠(yuǎn)的點(diǎn)到該節(jié)點(diǎn)的距離d = max（d（o，p1），d（o，p2），…，d（o，pn）），并將節(jié)點(diǎn)的傳感半徑調(diào)整為d+即this.=d+（>0），則轉(zhuǎn)步驟7；若加后的值大于該節(jié)點(diǎn)的最大感知半徑，則將其感知半徑調(diào)整為最大感知半徑為Rmax，其中為誤差控制參數(shù)，以免去因誤差導(dǎo)致的覆蓋盲點(diǎn)。

（6）將節(jié)點(diǎn)的感知半徑this.r調(diào)整為零，此時節(jié)點(diǎn)的感知范圍區(qū)域被鄰居 節(jié)點(diǎn)完全覆蓋，所以將其調(diào)整為零。

（7）算法完成。

4 仿真與結(jié)果分析

本算法在OMNET++網(wǎng)絡(luò)仿真平臺上進(jìn)行模擬仿真實(shí)驗(yàn)。在200x200m2的感知區(qū)域內(nèi)隨機(jī)部署800個感知節(jié)點(diǎn)，且所有感知節(jié)點(diǎn)的最大半徑為20m，圖A顯示所有感知節(jié)點(diǎn)半徑未被調(diào)整前的網(wǎng)絡(luò)覆蓋情況；圖B顯示經(jīng)過感知半徑調(diào)整后的網(wǎng)絡(luò)覆蓋情況。

5 總結(jié)

由于無線傳感器網(wǎng)絡(luò)隨機(jī)部署大量的傳感器節(jié)點(diǎn)，從而導(dǎo)致節(jié)點(diǎn)的覆蓋冗余度太大，產(chǎn)生大量冗余信息在網(wǎng)絡(luò)中傳輸，給網(wǎng)絡(luò)能量帶來極大的浪費(fèi)，本文提出了一種基于感知半徑調(diào)整算法ASRA （Adjustment Sensing Radius Algorithm），通過μ鄰居節(jié)點(diǎn)信息來調(diào)整感知半徑，極大的降低網(wǎng)絡(luò)的覆蓋冗余和節(jié)點(diǎn)能量，詳細(xì)描述感知半徑算法調(diào)整原理，畫出感知半徑調(diào)整示意圖，通過模擬仿真對感知半徑調(diào)整效果、覆蓋冗余度實(shí)驗(yàn)分析，證明了算法對網(wǎng)絡(luò)覆蓋控制的優(yōu)越性。

參考文獻(xiàn)

[1]李海坡，杜慶偉.一種能量有效的無線傳感器網(wǎng)絡(luò)覆蓋控制算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2011（02）：233-6.

[2]唐林俊.無線傳感網(wǎng)絡(luò)中部分覆蓋與擬連通冗余節(jié)點(diǎn)的研究[J].傳感技術(shù)學(xué)報(bào)，2011（06）：895-9.

[3]蔣麗萍，王良民，熊書明，詹永照.基于感知概率的無線傳感器網(wǎng)絡(luò)k重覆蓋算法[J].計(jì)算機(jī)應(yīng)用研究，2009（09）：3484-6+9.

[4]任秀麗，教傳亮，薛建生，于海斌.與節(jié)點(diǎn)位置無關(guān)的無線傳感器網(wǎng)絡(luò)覆蓋控制算法[J].小型微型計(jì)算機(jī)系統(tǒng). 2011（01）：121-5.

[5]王換招，孟凡治，李增智.高效節(jié)能的無線傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議[J]. 軟件學(xué)報(bào)，2010（12）：3124-37.

[6]顧曉燕，孫力娟， 郭劍，肖甫.無線傳感器網(wǎng)絡(luò)覆蓋質(zhì)量與節(jié)點(diǎn)休眠優(yōu)化策略[J].計(jì)算機(jī)仿真，2011（09）：127-31.

作者簡介

王廣超（1983-），男，山東省棗莊市人。碩士研究生學(xué)歷。主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)。

王振榮（1988-），男，山西省大同市人。碩士研究生學(xué)歷。主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)。

作者單位

北方民族大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 寧夏回族自治區(qū)銀川市 750021