韓春延

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院, 江蘇 無錫 214122)

邊緣節(jié)點的自適應(yīng)半徑調(diào)整算法

韓春延

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院, 江蘇 無錫 214122)

降低覆蓋冗余度是提高無線傳感器網(wǎng)絡(luò)覆蓋度的一種措施．在DCAC(Dynamic adaptive coverage adjusting scheduling)的算法的基礎(chǔ)上,給出了邊緣節(jié)點和局部全約束狀態(tài)的定義,并且提出了邊緣節(jié)點的自適應(yīng)半徑調(diào)整的算法．與DCAC算法進(jìn)行比較其仿真結(jié)果表明,無線傳感器網(wǎng)絡(luò)的覆蓋冗余度相對降低,提高了網(wǎng)絡(luò)的覆蓋度,并且活躍節(jié)點的個數(shù)相對減少．

覆蓋冗余度; 邊緣節(jié)點; 半徑調(diào)整; 無線傳感器網(wǎng)絡(luò)

0 引言

無線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價傳感器節(jié)點組成的多跳自組織網(wǎng)絡(luò)系統(tǒng)． 無線傳感器網(wǎng)絡(luò)在許多地方得到廣泛的應(yīng)用, 例如軍事、醫(yī)院監(jiān)控、工業(yè)生產(chǎn)中的安全監(jiān)控、自然環(huán)境的檢測等[1-4]． 根據(jù)傳感器節(jié)點是否有移動能力,無線傳感器網(wǎng)絡(luò)覆蓋可以分為靜態(tài)網(wǎng)絡(luò)覆蓋和動態(tài)網(wǎng)絡(luò)覆蓋． 靜態(tài)網(wǎng)絡(luò)覆蓋又分為區(qū)域覆蓋、點覆蓋和柵欄覆蓋[5,6]． 區(qū)域覆蓋研究的是對目標(biāo)區(qū)域的檢測問題．Bai等人[7]研究了區(qū)域覆蓋,提出了計劃部署模型,漸近達(dá)到最優(yōu)覆蓋,但是需要精確部署節(jié)點,因此應(yīng)用范圍相對有限; 點覆蓋研究的是對離散目標(biāo)點的覆蓋問題;柵欄覆蓋研究的是運(yùn)動物體穿越部署區(qū)域被檢測到的概率問題,Kumar等人[8]提出了弱柵欄覆蓋的概念,并推導(dǎo)出了其存在和不存在的臨界條件, Liu等[9]提出強(qiáng)柵欄覆蓋與區(qū)域長寬比的直接關(guān)系,即隨著長寬比的增大,穿越路徑的存在可能性趨近為1．

為達(dá)到應(yīng)用要求,無線傳感器網(wǎng)絡(luò)的覆蓋需要在保證服務(wù)質(zhì)量的條件下,使得對監(jiān)測區(qū)域的覆蓋范圍達(dá)到最大化．無線傳感器節(jié)點體積微小,靠能量十分有限的電池工作．由于傳感器分布區(qū)域較大,而且部署區(qū)域的環(huán)境復(fù)雜,有時人員無法到達(dá)更換電池．所以,很多的應(yīng)用為了保證網(wǎng)絡(luò)的服務(wù)質(zhì)量要求網(wǎng)絡(luò)的覆蓋度kgt;1．無線傳感器網(wǎng)絡(luò)在大片的監(jiān)測區(qū)域內(nèi)通常密集部署,而且由于節(jié)點的數(shù)量較多,一般采用隨機(jī)播撒的方式．這樣就造成有的區(qū)域節(jié)點過多,出現(xiàn)覆蓋冗余的現(xiàn)象,而有的區(qū)域則由于節(jié)點過少造成覆蓋盲區(qū)．韓志杰等提出了一種基于區(qū)域覆蓋的自適應(yīng)傳感器半徑調(diào)整算法[10]．該算法通過節(jié)點自適應(yīng)選擇最佳的覆蓋半徑,消除覆蓋盲區(qū),減少覆蓋冗余,從而減少節(jié)點能量虛耗,提高覆蓋效率．但是在k覆蓋傳感半徑調(diào)整算法中,如果監(jiān)測區(qū)域較大,節(jié)點較多,導(dǎo)致邊緣節(jié)點增加,由于邊緣節(jié)點大部分屬于非全約束狀態(tài),則根據(jù)算法可知節(jié)點的半徑增加到最大半徑,從而造成區(qū)域邊緣覆蓋冗余度增大,能耗增加． 因此本文針對邊緣節(jié)點提出了邊緣節(jié)點半徑調(diào)整算法,降低網(wǎng)絡(luò)的覆蓋冗余度．

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

1) 假設(shè)節(jié)點的感知模型為布爾模型[1]．在布爾模型中,節(jié)點P的感知半徑為R,對于檢測區(qū)域內(nèi)的任一點s,節(jié)點P感知到點s處事件信息的概率可以用下列公式表示為:

(1)

其中,d(P,s)是節(jié)點P到區(qū)域內(nèi)點s的歐式距離．從(1)式中可以看出,當(dāng)監(jiān)控對象存在于節(jié)點的感知區(qū)域內(nèi)時,節(jié)點監(jiān)測到對象的概率則恒為1;當(dāng)監(jiān)控對象不存在于節(jié)點的感知區(qū)域內(nèi),則被監(jiān)測到的概率恒為0．

2) 假設(shè)節(jié)點是靜止的,可以通過裝置GPS確定自身的位置,并且節(jié)點可以通過自身的位置信息計算距自己最近的檢測邊界的距離．

3) 假設(shè)所有的傳感器節(jié)點同構(gòu),即具有相同的計算通信能力、初始能力和存儲能力．傳感器節(jié)點都有相同的最大傳感半徑Rmax,且傳感器半徑可以根據(jù)需要進(jìn)行調(diào)整.

4) 假設(shè)監(jiān)測區(qū)域的邊界可以通過數(shù)學(xué)表達(dá)式進(jìn)行描述.

2 算法相關(guān)定義和定理

處于監(jiān)測區(qū)域邊緣的節(jié)點具有共同的特點[10]．一是節(jié)點的感知范圍有一部分無法在監(jiān)測區(qū)域內(nèi);二是節(jié)點大部分處于非全約束狀態(tài);三是節(jié)點到監(jiān)測邊界的垂直距離絕對不會大于感知半徑．根據(jù)文獻(xiàn)[10]中邊緣節(jié)點的特點給出邊緣節(jié)點的定義．

定義1[10]在一個監(jiān)測區(qū)域內(nèi),假設(shè)節(jié)點P的半徑為r,節(jié)點P到最近監(jiān)測區(qū)域邊界的垂直距離為d,若d≤r,則節(jié)點為P邊緣節(jié)點,如圖1所示．

圖1 邊緣節(jié)點P的參考圖

圖2為邊緣節(jié)點的幾種位置圖．圖2a中節(jié)點P在監(jiān)測區(qū)域的感知范圍不能被鄰居節(jié)點覆蓋,且節(jié)點在P監(jiān)測范圍內(nèi)的感知的圓弧上的點被鄰居節(jié)點全部覆蓋． 圖2b中節(jié)點在P監(jiān)測區(qū)域內(nèi)的感知范圍不能被鄰居節(jié)點覆蓋,且節(jié)點P在監(jiān)測區(qū)域內(nèi)的感知圓的圓弧上的點不能被鄰居節(jié)點全部覆蓋．圖2c中節(jié)點P在監(jiān)測區(qū)域的感知圓感知范圍內(nèi)的每一個點都能被鄰居節(jié)點覆蓋．

圖2 邊緣節(jié)點P的位置圖

根據(jù)上述3種情況,基于文獻(xiàn)[10]中的約束圓弧和全約束狀態(tài)的定義對邊緣節(jié)點感知圓圓弧在監(jiān)測區(qū)域內(nèi)的約束性和邊緣節(jié)點在監(jiān)測區(qū)域的約束狀態(tài)進(jìn)行定義．

定義2 邊緣節(jié)點的有效約束圓弧:若一個邊緣節(jié)點在監(jiān)測區(qū)域內(nèi)的感知圓部分的某段圓弧被其任何一個鄰居節(jié)點的感知圓覆蓋,則稱這段圓弧為有效約束圓?。?/p>

定義3 邊緣節(jié)點的局部全約束狀態(tài): 一個邊緣節(jié)點在監(jiān)測區(qū)域內(nèi)的感知圓部分的圓弧全部為有效約束圓弧時的狀態(tài)為邊緣節(jié)點的局部全約束狀態(tài)．

基于文獻(xiàn)[10]中普通節(jié)點的對覆蓋盲區(qū)覆蓋的定理以及節(jié)點在覆蓋過程中為全約束狀態(tài)并不會產(chǎn)生新的盲區(qū)的定理的證明可得定理同樣適用于邊緣節(jié)點．定理可以如下表述．

定理1 設(shè)邊緣傳感器節(jié)點為P,傳感半徑為r,節(jié)點P的鄰居節(jié)點和監(jiān)測邊界的覆蓋盲區(qū)的盲區(qū)頂點分別為A1,A2,…,An,若存在maxd(P,Ai)≤r,則必P覆蓋盲區(qū),其中d(P,Ai)是邊緣節(jié)點P和Ai的歐式距離,如圖3所示．

圖3 節(jié)點P在監(jiān)測區(qū)域內(nèi)的覆蓋盲區(qū)

定理2 設(shè)邊緣傳感器節(jié)點為P,傳感半徑為r,節(jié)點P的鄰居節(jié)點和監(jiān)測邊界的覆蓋盲區(qū)的盲區(qū)頂點分別為A1,A2,…,An,節(jié)點P為局部全約束狀態(tài),將節(jié)點P的半徑從r調(diào)整到r′,且r′=maxd(P,Ai),i=1,2,…,n,則節(jié)點P在半徑調(diào)整過程中一直處于局部全約束狀態(tài)．

定理3 若在監(jiān)測區(qū)域內(nèi)邊緣節(jié)點P的感知圓半徑由r調(diào)整到r′的過程為局部全約束變化過程,則邊緣節(jié)點P的傳感半徑由r調(diào)整為r′不會產(chǎn)生新的覆蓋盲區(qū)．

從上述3個定理得知,對于監(jiān)測區(qū)域內(nèi)的邊緣節(jié)點在監(jiān)測區(qū)域內(nèi)的半徑調(diào)整為全約束變化,并且半徑調(diào)整后可以覆蓋在監(jiān)測區(qū)域內(nèi)的覆蓋盲區(qū),并且半徑調(diào)整的過程中不產(chǎn)生新的覆蓋盲區(qū)．本文的算法只是研究在監(jiān)測區(qū)域內(nèi)的覆蓋盲區(qū),在監(jiān)測區(qū)域內(nèi)的邊緣節(jié)點的感知圓部分,并不考慮監(jiān)測區(qū)域外的邊緣節(jié)點感知圓部分．

3 邊緣節(jié)點的半徑調(diào)整算法

3.1 算法分析

1) 確定邊緣節(jié)點．根據(jù)定義1中的要求,比較節(jié)點P的半徑r和節(jié)點到監(jiān)測邊界的垂直距離d,若d≤r,則節(jié)點P為邊緣節(jié)點,否則,則不是邊緣節(jié)點．

2) 判斷邊緣節(jié)點感知圓在監(jiān)測區(qū)域內(nèi)是否為局部全約束狀態(tài)．判斷在監(jiān)測區(qū)域內(nèi)的邊緣節(jié)點的感知圓圓弧能否被節(jié)點的μ鄰居覆蓋,若能覆蓋,則為局部全約束狀態(tài),否則不是．若邊緣節(jié)點不是局部全約束狀態(tài),則以最大能力覆蓋μ鄰居的覆蓋盲區(qū)區(qū)域．若邊緣節(jié)點是局部全約束狀態(tài),則求出節(jié)點P的所有鄰居節(jié)點的感知圓在該節(jié)點的感知圓內(nèi)彼此相交的交點以及在該節(jié)點感知圓內(nèi)的鄰居節(jié)點與監(jiān)測邊界的交點,分別表示為A1,A2,…,An．

3) 若邊緣節(jié)點為局部全約束狀態(tài),但不存在A1,A2,…,An,則可知節(jié)點P的感知區(qū)域被其鄰居節(jié)點全部覆蓋,則將節(jié)點P的感知半徑調(diào)整為零．若存在A1,A2,…,An,則設(shè)其被鄰居節(jié)點覆蓋的次數(shù)為β,并且保證達(dá)到k覆蓋．當(dāng)β≤k+1時,Ai為盲區(qū)頂點;否則為普通圓內(nèi)交點．

4) 若A1,A2,…,An中不存在盲區(qū)頂點,說明邊緣節(jié)點P的鄰居節(jié)點能夠完全覆蓋該節(jié)點的感知區(qū)域,因此邊緣節(jié)點P的傳感半徑調(diào)整為零.

5) 若A1,A2,…,An中存在盲區(qū)頂點,說明邊緣節(jié)點P在監(jiān)測區(qū)域內(nèi)存在覆蓋盲區(qū)．根據(jù)定理1～定理3,則將邊緣節(jié)點P的半徑從r調(diào)整到r′,且r′=maxd(P,Ai),i=1,2,…,n,此過程為局部全約束變化,不會產(chǎn)生新的覆蓋盲區(qū)．

3.2 算法步驟

begin 對每個節(jié)點ni

begin 監(jiān)測區(qū)域的函數(shù)

if 節(jié)點到邊界的最短距離d≤r

則節(jié)點為邊緣節(jié)點

調(diào)用PtlnRegion函數(shù)判斷邊緣節(jié)點是否為局部全約束狀態(tài)

if 邊緣節(jié)點為局部全約束狀態(tài)

if 邊緣節(jié)點不存在覆蓋盲區(qū)

r調(diào)整為0

else if 邊緣節(jié)點的覆蓋盲區(qū)存在盲區(qū)定點,r調(diào)整為0

else r調(diào)整為r′

else 邊緣節(jié)點為非局部全約束狀態(tài),r調(diào)整為rmax

end

end

end

end

end

end

4 仿真分析

為了驗證邊緣節(jié)點加入算法后的性能,分別從覆蓋冗余度,活躍節(jié)點,能力消耗進(jìn)行了模擬實驗,并與自適應(yīng)半徑調(diào)整算法進(jìn)行了比較．

4.1 覆蓋冗余度的比較

覆蓋冗余度:監(jiān)測區(qū)域內(nèi)的所有節(jié)點覆蓋面積之和與區(qū)域中所有節(jié)點的覆蓋范圍的并集的比值[1]．可以用下式表示．

(2)

其中,Si表示節(jié)點i的感知圓覆蓋面積．由覆蓋冗余度表達(dá)式可以看出,覆蓋冗余度越低,節(jié)點的感知區(qū)域重疊越小,節(jié)點的利用率越高．

在200m×200m的區(qū)域內(nèi),隨機(jī)撒入800個節(jié)點,最大半徑為10m,分別用自適應(yīng)半徑調(diào)整算法、及在自適應(yīng)半徑調(diào)整算法后加入邊緣節(jié)點算法的進(jìn)行調(diào)度,并計算出各自分別在1次覆蓋,2次覆蓋和3次覆蓋時的覆蓋冗余度，并用表1表示. 仿真結(jié)果表明,加入邊緣節(jié)點算法后,監(jiān)測區(qū)域的覆蓋冗余度降低,說明加入邊緣節(jié)點算法后,監(jiān)測區(qū)域的節(jié)點利用率提高．

表1 不同覆蓋次數(shù)下的覆蓋冗余度比較

4.2 活躍節(jié)點個數(shù)的比較

活躍節(jié)點是指監(jiān)測區(qū)域處于工作狀態(tài)的節(jié)點．對于一定的監(jiān)測區(qū)域,在保證網(wǎng)絡(luò)覆蓋要求的前提下,活躍節(jié)點的個數(shù)越少,休眠的節(jié)點越多,節(jié)約的網(wǎng)絡(luò)能量更多,網(wǎng)絡(luò)的生存時間越長．在200m×200m的區(qū)域內(nèi),節(jié)點的最大感知半徑為20m,隨機(jī)部署的節(jié)點個數(shù)分別取(900,1000,1100,1200,1300,1400,1500)．仿真對不同的部署參數(shù)分別進(jìn)行了10次實驗,然后取其平均值作為最后的結(jié)果．在自適應(yīng)半徑調(diào)整算法,及在自適應(yīng)半徑算法結(jié)果后加入邊緣節(jié)點算法調(diào)度后的活躍節(jié)點個數(shù)比較仿真結(jié)果如圖4所示．由圖4的活躍節(jié)點比較可知,自適應(yīng)半徑調(diào)整算法的結(jié)果后加入邊緣節(jié)點算法后的調(diào)度結(jié)果顯示活躍節(jié)點個數(shù)減少,說明改進(jìn)后的算法調(diào)度后,網(wǎng)絡(luò)的性能更好．

4.3 能量消耗的比較

傳感器節(jié)點體積微小,只能攜帶能力有限的電池．由于傳感器節(jié)點個數(shù)多,而且部署區(qū)域的環(huán)境復(fù)雜,有些區(qū)域人員不能到達(dá),所以傳感器節(jié)點更換電池的方式來補(bǔ)充電源很難實現(xiàn)．如何減少傳感器節(jié)點的能力消耗是傳感器網(wǎng)絡(luò)面臨的重大挑戰(zhàn)．

傳感器半徑調(diào)整會消耗計算能量,發(fā)送和接受數(shù)據(jù)消耗能量．由于計算能量消耗較少,因此可以忽略不計．傳感器節(jié)點的感知模塊的能量消耗可以表示為E=ur2,u為消耗系數(shù),為常量．

覆蓋區(qū)域的平均能耗[11,12]為

(3)

其中Ei為節(jié)點i的感知能量消耗,Si為節(jié)點i的感知圓覆蓋面積,ri為節(jié)點i的感知半徑．

在150m×150m區(qū)域內(nèi)分別部署的節(jié)點個數(shù)(800,1000,1200,1400,1600,1800,2000)．節(jié)點的最大感知半徑為10m,在自適應(yīng)半徑調(diào)整算法,自適應(yīng)半徑調(diào)整算法結(jié)果再運(yùn)用邊緣節(jié)點算法調(diào)度后的覆蓋區(qū)域的平均能耗比較如圖5所示．

圖4 活躍節(jié)點個數(shù)的比較

圖5 平均能耗的對比

從圖5的結(jié)果中可以看出,加入邊緣節(jié)點算法后,覆蓋區(qū)域的平均能耗減少,延長了節(jié)點的使用時間,從而延長了無線傳感器網(wǎng)絡(luò)的生存時間,提高了網(wǎng)絡(luò)性能．

5 總結(jié)

本文提出了邊緣節(jié)點的半徑調(diào)整算法,并將算法加入DACA算法的應(yīng)用中．該算法對監(jiān)測區(qū)域的邊緣節(jié)點進(jìn)行了研究,改變了邊緣節(jié)點在非全約束狀態(tài)下半徑調(diào)節(jié)到最大半徑的情況,讓邊緣節(jié)點針對自身的覆蓋盲區(qū)的情況進(jìn)行半徑調(diào)整,盡可能的降低網(wǎng)絡(luò)的覆蓋冗余度．為了驗證DACA算法加入邊緣節(jié)點半徑調(diào)整算法后的性能,主要從覆蓋冗余度,活躍節(jié)點個數(shù)和平均能量消耗三個方面進(jìn)行了模擬仿真實驗和分析．實驗結(jié)果表明,邊緣節(jié)點半徑調(diào)整算法和DACA算法結(jié)合后,調(diào)度后的結(jié)果表明,網(wǎng)絡(luò)的覆蓋冗余度降低,減少了活躍節(jié)點的個數(shù)和節(jié)點能耗,提高了網(wǎng)絡(luò)的覆蓋率,延長了網(wǎng)絡(luò)的生存時間,從而提高了網(wǎng)絡(luò)的覆蓋性能．由于邊緣節(jié)點半徑調(diào)整算法需要知道監(jiān)測區(qū)域的數(shù)學(xué)表達(dá),因此只能應(yīng)用與一些較簡單的監(jiān)測區(qū)域．

[1] 孫利民, 李建中, 陳渝. 無線傳感器網(wǎng)絡(luò)[M]. 北京: 清華大學(xué)出版社, 2005.

[2] 馬祖長, 孫怡寧, 梅濤. 無線傳感器網(wǎng)L絡(luò)綜述[J]. 通信學(xué)報, 2004, 25(4):114-124.

[3] 王汝傳, 孫麗娟, 黃海平,等. 無線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用[M]. 人民郵電出版社. 2011.

[4] David E C, Wei H, Wireless sensor networks[J]. Communications of ACM, 2004, 47(6): 30-33.

[5] Bonnet P, Gehrke J, Seshadri P. Querying the physical world[J]. IEEE Personal Communication, 2007, 7(5): 10-15.

[6] Akyildiz I F, Su W, Sankarasubramaniam Y. Wireless sensor Networks: a Survey[J]. Computer Networks,2002,38(4):393-422.

[7] Bai X L, Kumars, Xuan D, et al. Deploying wireless sensors to achieve both coverage and connectivity[M].//Proc of the 7th ACM International Symposium on Mobile Ad hoc Networking and Computing. New York: Association for Computing Machinery, 2006: 131-142.

[8] Kumars, Laith, Arora A. Barrier coverage with wireless sensors[M].//Proc of the 11th Annual International Conference on Mobile Computing and Networking. New York: Association for Computing Machinery, 2005: 284-298.

[9] Liu B Y, Dousseo, Wang J. et al. Strong barrier coverage of wireless sensor networks[M].//Proc of the 9th ACM International Symposium on Mobile Ad hoc Netwoking and Computing. New York: Association for Computing Machinery, 2008: 411-420.

[10] 韓志杰, 吳志斌, 王汝傳, 等. 新的無線傳感器網(wǎng)絡(luò)覆蓋控制算法[J]. 通信學(xué)報, 2011, 32(10): 174-184.

[11] Woehrlem, Brockhoffd, Hohmt, et al. Investigating Coverage and Connectivety Trade Offs in Wireless Sensor Netwoks: the Benefits of MOEAS, TIK Report 294[R]. Zurich: Computer Engineering and Networks Lab, ETH Zurich, 2008.

[12] Hefeedam, Bagherim. Efficient K-Coverage Algorithms for Wireless Sensor Networks[D]. Vancouver: Simon Fraser University, 2006.

AdaptiveRadiusAdjustmentAlgorithmforEdgeNodes

HAN Chun-yan

(School of IoT Engineering, Jiangnan University, Wuxi Jiangsu 214122, China)

The lower coverage redundancy is a kind of measures to improve the wireless sensor network coverage. In this paper, the edge nodes and local full constraint condition are defined.At the same time, this paper put forward the edge nodes adaptive radius adjustment algorithm based on the algorithm of DACA(Dynamic adaptive coverage adjusting scheduling).Finally, the algorithm of DACA joins in the algorithm of this paper and then compared with the DACA algorithm.The simulation results show that coverage redundancy of the wireless sensor network relatively lower, the network coverage improved and the number of active nodes relatively less.

coverage redundancy; edge nodes; radius adjustment; wireless sensor network

2013-03-15

韓春延(1988-), 女, 山東聊城人, 碩士研究生, 研究方向為無線傳感器網(wǎng)絡(luò)覆蓋控制．

TP393

A

1671-6876(2013)02-0129-06

[責(zé)任編輯蔣海龍]