對無線感測器網路感知能力動態調整演算法研究論文

　　摘要：為了增強無線感測器網路的監測質量和提高網路可靠性，通常將感測器節點大規模、高密度地部署在感興趣的目標區域內，這就導致網路中大量節點的覆蓋區域相互交迭。這種覆蓋冗餘會直接導致採集、傳輸資料的冗餘以及通道的干擾，從而導致不必要的能量消耗，提出了一種感測半徑的動態調整演算法，在保證網路覆蓋性的前提下，透過對節點感測半徑的調整，來降低網路的覆蓋冗餘，從而大大減少冗餘資料採集和傳輸所造成的能量浪費和網路衝突。模擬結果證明演算法取得了良好的效果。

　　關鍵詞：感測半徑；覆蓋冗餘；動態調整

　　1 引言

　　1.1 網路模型

　　假設個感測器節點和一個Sink節點隨機分佈在一個的二維正方形區域內，並假設該感測器網路具有如下性質：

　　* 節點同構，各節點具有相同的計算、通訊能力和初始能量水平，且節點能量不能再補充。其中Sink節點例外，它的計算、通訊能力和能量不受限制；

　　* 節點間的通訊是相互的。節點A能夠與B通訊，則B也可以與A通訊；

　　* 節點具有相同的最大感知範圍，且感知範圍能夠自調整；

　　* 節點能獲知其位置資訊。感知節點可以利用定位演算法或 GPS方式獲知自己所在的位置；

　　1.2 感知模型

　　採用無線感測器網路研究中常用的二元感知模型(Binary sensing model)即在二維平面上，感測器節點的覆蓋範圍是一個以節點為圓心，半徑為的圓形區域稱為感測器節點的“感知圓盤(Sensing Disk)”。稱為感測器節點的感測半徑，假設節點的座標為。在二元感知模型中，對於平面上任意一點，節點檢測到點處發生的事件的機率為

　　2 感測器感知能力動態調整演算法

　　2.1 演算法相關定理

　　節點集，若區域內的任一點都不能被內的節點所感知到，則這樣的區域稱為的覆蓋盲區。可以注意到，覆蓋盲區有兩種型別閉合型與開放型，若組成開放型盲區區域的圓弧之間有交點，則交點也稱為盲區頂點。

　　若一個節點的感知圓的某段圓弧被其任何一個鄰居節點的感知圓包含，則稱這段圓弧為約束圓弧，否則稱為自由圓弧。

　　【定理1】有一圓心為半徑為的圓和頂點為的凹曲邊形，設為到的最大距離，即，若滿足，則圓必覆蓋該凹曲邊形區域。

　　證明：欲證圓覆蓋凹曲邊形，只需證明圓覆蓋順次連線的相鄰頂點所形成的n多邊形。設點為n多邊形內的任意一點，連線並延長則必交的一邊於點,記該條邊為，如下圖所示。在內易知，又因所以，因此，從而凹曲邊形內任意一點到圓心的距離均不大於圓半徑，即該圓覆蓋凹曲邊形，定理得證。

　　【定理2】若有盲區區域均是感測器節點的鄰居集的閉合型覆蓋盲區，其頂點分別為，，，，且是的感知圓內的所有閉合型盲區，節點的感測半徑等於其最大感測半徑，為節點到，，，的最大距離。如果的感知圓不存在自由圓弧，則的感測半徑在由調整為的過程中不會產生集合的覆蓋盲區。

　　證明：因的感知圓不存在自由圓弧，易知在的感知圓內必不存在的鄰居集的開放型覆蓋盲區區域部分，則的感知圓內僅存在閉合型盲區區域，由定義4可知均為凹曲邊形。又由定理1可知，當時的感知圓覆蓋，又因故當時必覆蓋，即在的感測半徑在由改變為的過程中不會產生的覆蓋盲區。定理得證。

　　2.2 感測器感知能力動態調整演算法描述

　　(一)演算法思想概述

　　節點首先根據鄰居資訊判斷其感知圓是否具有自由圓弧，若具有自由圓弧，則感測半徑保持不變，仍為最大感測半徑，以儘可能多的覆蓋其鄰居集的覆蓋盲區區域。若不存在自由圓弧，則計算節點所有鄰居節點感知圓在該節點感知圓內彼此兩兩相交所構成的交點的集合，將集合中交點的被覆蓋次數判斷盲區頂點和普通交點，若不存在盲區頂點，則鄰居節點能夠完全覆蓋感知區域，此時，感測半徑可以調整為零，否則說明感知圓內包含有鄰居集的閉合型盲區,可根據定理2對感測半徑進行調整。

　　(二)演算法步驟

　　具體演算法步驟如下：

　　1) 首先查詢鄰居節點集NBS的資訊，獲得所有鄰居節點的圓心座標、當前感測半徑等。

　　2) 檢查鄰居節點的個數NBS.count 是否小於1，若是則轉步驟7，否則轉3。

　　3) 依照判斷是否存在自由圓弧的演算法判斷該節點的感知圓是否存在自由圓弧，若存在則轉到步驟7，否則轉到4。

　　4) 計算所有鄰居節點的感知圓在本圓內的交點，若不存在交點，即轉到步驟6；否則，轉到5。

　　5) 從第4步中獲取的交點集合中按查詢本圓內盲區頂點集合HolePointsList，若不存在，則轉步驟6；若存在，則找出離該節點最遠的點到該點的距離d，感測半徑調整為，轉步驟7；其中為誤差控制引數，以免去因誤差導致的覆蓋盲區。

　　6) 將節點感測半徑調整為零。因此時節點的感知範圍區域已被鄰居所覆蓋。

　　7) 演算法結束。

　　2.3 鄰居集的選取

　　在感測器感知能力動態調整演算法中定義感測器節點A的鄰居節點集為，其中為B到A的距離，為A的最大感測半徑，為鄰居範圍控制因子。在進行感測半徑調整時，要保證演算法中節點的鄰居的感知圓和本節點的感知圓是非相離關係，因為相離關係的兩個節點不會相互影響到對方的覆蓋範圍，則只需保證其鄰居到該節點的距離不大於該節點2倍最大感測半徑，即的取值應滿足下式：

　　當時，這時節點在感測器感知能力動態調整演算法中考慮到了所有能對自己的最大覆蓋範圍能造成影響的節點，感測器感知能力動態調整演算法可以充分利用鄰居的資訊，調整能得到最佳的效果。

　　當時，此時，部分節點的感知區域可以覆蓋該節點感知區域的一部分，因為這部分節點不包含在該節點的鄰居集內，會出現節點感知區域內實際上不存在盲區，但是節點會誤認為其感知圓記憶體在盲區，感測半徑調整後出現部分監測區域的重複覆蓋現象，這時的調整效果不及。

　　實驗結果顯示，當時的調整效果最好，時的效果最差，產生大量不必要的冗餘覆蓋。

　　3 模擬與分析

　　為了檢驗感測器感知能力動態調整演算法的有效性，論文主要從調整效果、能量消耗和覆蓋冗餘度三個方面對演算法進行了模擬實驗和分析。首先對本文所用模擬程式做簡單的介紹。

　　3.1 覆蓋冗餘度

　　覆蓋冗餘度是用來衡量監測區域中被感測器節點覆蓋區域的覆蓋次數。定義為區域中所有節點覆蓋範圍之和與區域中所有節點的覆蓋範圍的並集之比值。覆蓋冗餘度的計算公式為

　　其中，表示節點的覆蓋範圍，覆蓋冗餘度反映了節點對監測區域覆蓋的冗餘程度，覆蓋冗餘度越低，節點利用率越高，反之節點利用率越低。

　　隨機佈置節點數N分別取{800，1000，1200，1300，1400}五個值時，節點最大感測半徑從10變化到30時，調整前和調整後覆蓋冗餘度的對比情況。

　　實驗結果表明感測器感知能力動態調整演算法前，網路的覆蓋冗餘度會隨著最大感測半徑的'增大而急劇增大，加入感測器感知能力動態調整演算法之後，網路的覆蓋冗餘度隨著節點最大感測半徑的增大而增大甚少，感測器感知能力動態調整演算法應用在具有不同最大感測半徑的感測器網路中，對覆蓋冗餘度的控制也能保持較好的成效。

　　3.2 能量消耗

　　本節只分析感測器節點的感測模組的能量消耗，暫時不考慮通訊和計算的能耗。假設感測器節點的感測半徑調整為零時認為該節點消耗能量也為零。感測器節點的感知模組的耗能與感測半徑成正比，，為常量，可看作能量消耗係數。

　　所有節點的有效覆蓋面積即所有節點的覆蓋範圍的並集為

　　則調整感測半徑前，覆蓋區域的平均能量消耗為

　　而調整感測半徑後，覆蓋區域的平均能量消耗為

　　前文已經證明，節點在感測半徑調整的過程中不會產生盲區，所以感測半徑調整前後，所有節點的有效覆蓋面積在理論上是保持不變的。

　　表1列出了在的區域內隨機佈置800個節點，各個節點的最大感測半徑為15m時，節點感測半徑調整前後網路覆蓋區域的平均能量消耗。

　　感測半徑調整前後區域平均能量消耗統計

　　實驗次數

　　調整前平均耗能

　　調整後平均耗能

　　3.6463

　　0.6875

　　3.6092

　　0.7189

　　3.6487

　　0.7054

　　3.6389

　　0.7311

　　從表中實驗資料可以看出，感測半徑調整後，平均能量消耗比原來減少了大約80%，說明感測器感知能力動態調整演算法能夠大大減少感測器節點的能量消耗。

　　4.小結

　　針對無線感測器網路節點高密度隨機部署時，網路的覆蓋冗餘度過大，大量冗餘資訊的被感知及其在網路中的傳輸，會極大浪費網路能量的特點，本文提出了一種能夠保證網路覆蓋的分散式感測器感知能力動態調整演算法。各節點只根據其鄰居節點的資訊來調整自身的感測半徑。演算法側重於保證網路的原始覆蓋和連通，在此前提下，儘量減少網路的冗餘覆蓋，所以感測半徑調整後對網路的路由協議的設計不會產生任何影響。

　　參考文獻：

　　IEEE Aerospace and Electronic Systems Magazine, 1994, 10(4): 102-113.