邊緣節(jié)點的自適應半徑調整算法

韓春延

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

邊緣節(jié)點的自適應半徑調整算法

韓春延

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

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

覆蓋冗余度; 邊緣節(jié)點; 半徑調整; 無線傳感器網絡

0 引言

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

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

1 網絡模型

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

(1)

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

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

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

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

2 算法相關定義和定理

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

定義1[10]在一個監(jiān)測區(qū)域內,假設節(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)測范圍內的感知的圓弧上的點被鄰居節(jié)點全部覆蓋． 圖2b中節(jié)點在P監(jiān)測區(qū)域內的感知范圍不能被鄰居節(jié)點覆蓋,且節(jié)點P在監(jiān)測區(qū)域內的感知圓的圓弧上的點不能被鄰居節(jié)點全部覆蓋．圖2c中節(jié)點P在監(jiān)測區(qū)域的感知圓感知范圍內的每一個點都能被鄰居節(jié)點覆蓋．

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

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

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

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

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

定理1 設邊緣傳感器節(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ū)域內的覆蓋盲區(qū)

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

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

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

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

3.1 算法分析

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

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

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

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

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

3.2 算法步驟

begin 對每個節(jié)點ni

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

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

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

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

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

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

r調整為0

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

else r調整為r′

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

end

end

end

end

end

end

4 仿真分析

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

4.1 覆蓋冗余度的比較

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

(2)

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

在200m×200m的區(qū)域內,隨機撒入800個節(jié)點,最大半徑為10m,分別用自適應半徑調整算法、及在自適應半徑調整算法后加入邊緣節(jié)點算法的進行調度,并計算出各自分別在1次覆蓋,2次覆蓋和3次覆蓋時的覆蓋冗余度，并用表1表示. 仿真結果表明,加入邊緣節(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ū)域,在保證網絡覆蓋要求的前提下,活躍節(jié)點的個數(shù)越少,休眠的節(jié)點越多,節(jié)約的網絡能量更多,網絡的生存時間越長．在200m×200m的區(qū)域內,節(jié)點的最大感知半徑為20m,隨機部署的節(jié)點個數(shù)分別取(900,1000,1100,1200,1300,1400,1500)．仿真對不同的部署參數(shù)分別進行了10次實驗,然后取其平均值作為最后的結果．在自適應半徑調整算法,及在自適應半徑算法結果后加入邊緣節(jié)點算法調度后的活躍節(jié)點個數(shù)比較仿真結果如圖4所示．由圖4的活躍節(jié)點比較可知,自適應半徑調整算法的結果后加入邊緣節(jié)點算法后的調度結果顯示活躍節(jié)點個數(shù)減少,說明改進后的算法調度后,網絡的性能更好．

4.3 能量消耗的比較

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

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

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

(3)

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

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

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

圖5 平均能耗的對比

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

5 總結

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

[1] 孫利民, 李建中, 陳渝. 無線傳感器網絡[M]. 北京: 清華大學出版社, 2005.

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

[3] 王汝傳, 孫麗娟, 黃海平,等. 無線傳感器網絡技術及其應用[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] 韓志杰, 吳志斌, 王汝傳, 等. 新的無線傳感器網絡覆蓋控制算法[J]. 通信學報, 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-), 女, 山東聊城人, 碩士研究生, 研究方向為無線傳感器網絡覆蓋控制．

TP393

A

1671-6876(2013)02-0129-06

[責任編輯蔣海龍]