無線傳感器網絡K重覆蓋節點部署與研究

◆張 帆

（國家新聞出版廣電總局573臺 北京 102209）

無線傳感器網絡K重覆蓋節點部署與研究

◆張 帆

（國家新聞出版廣電總局573臺 北京 102209）

本文對無線傳感器網絡K重覆蓋進行研究，運用Voronoi圖實現K重覆蓋，提出基于Voronoi圖的K重覆蓋節點自定位估算方案，通過仿真運行，驗證了節點自定位估算方案的可靠性。

無線傳感器網絡；K重覆蓋；Voronoi圖；節點自定位估算

0 前言

k重覆蓋就是當覆蓋區內每個節點至少被一個以上的傳感器節點監測到，即在坐標上，任意點x被兩個或者兩個以上的傳感器節點覆蓋住。Voronoi圖，又稱泰森多邊形或Dirichlet 圖，它是由一系列連接兩個鄰節點的直線的垂直平分線兩兩相交成的連續多邊形組成。N 個在平面不同的點，在平面上按照最鄰近原則劃分；面上的所有點都與它的最近鄰區域相關聯。

1 運用Voronoi圖實現k重覆蓋

定理1：在Voronoi圖中，節點is與同一圖中任意一個頂點的距離都相同，公式可以表示為：

定義1：（Voronoi單元的完全覆蓋）由定理1知，當一個Voronoi單元里每一個頂點都被圖中的傳感器節點is覆蓋，則稱就是Voronoi被完全覆蓋，即：

定理2：根據定義1，假設覆蓋區每一個Voronoi單元都被相應的傳感器節點完全覆蓋，那么稱這種覆蓋是一重覆蓋。

圖1 節點的邊界覆蓋

定理4：同時還反映出了節點與鄰節點之間的關系，得出一種節點之間的最優距離關系，為接下來的一重覆蓋和多重覆蓋提供了論述依據。

在實際應用中，由于邊界的的情況并不像覆蓋區，所以通常都要考慮監測區域的邊界的存在。假設覆蓋區內傳感器節點通過布爾感知模型覆蓋感知邊界，邊界外并無傳感器。如圖1所示，傳感器節點4s監測邊界，并把邊界上的1o點作為邊界節點，節點4s得出1o的坐標位置。如圖3b，節點4s與邊界的交點分別命名為好，繼而推出1o的坐標為。根據定理3，如果兩個相鄰節點直接的距離不大于，那么覆蓋就會出現盲區，而我們假設1o是在邊界的一個節點，所以節點4s到1o的距離也要不大于才能保證傳感器網絡在邊界也能實現全覆蓋。

但是如果不考慮邊界的影響，假設為完美邊界，那么覆蓋區內每個節點的覆蓋面積均為，那么二維平面中的節點密度為，由定理3知，為完全覆蓋所需要的最少節點數，則

由定理3可知，一重覆蓋時，網絡中的最大覆蓋面積實際上就是多個六邊形的面積相加起來的面積，而每個節點的有效覆蓋面積為，因此有效覆蓋率即六邊形的面積除以感知圓盤面積為。

在WSN的應用中，我們可以假設多重覆蓋是由多個單重覆蓋的子集集合而成，所以在k重覆蓋中，網絡的節點密度為k?。在這里，本文提出虛擬感知半徑vR的概念。運用vR可以將K重覆蓋問題轉換成單重覆蓋問題，用公式表示為：

由上式子可知，節點的密度和覆蓋重數的二次方成反比，可以退出虛擬感知半徑跟覆蓋重數K的關系，也即，由單重覆蓋變成多重覆蓋，k值變大，那么虛擬感知半徑將變小，也就意味著節點密度變大。引入虛擬半徑的方法可以將K重覆蓋問題轉化為單重覆蓋問題，通過推導公式可以簡化運算流程。

2 基于Voronoi圖的K重覆蓋節點自定位估算方案

2.1 條件設定

本文以的無線傳感器網絡由移動傳感器節點組成，在覆蓋區域的實現K重覆蓋，并將無線傳感器網絡與本文所提出的節點自定位估算方案相結合，對以下覆蓋區內的參數以及條件進行假設：

①覆蓋區域為二維無障礙物的矩形平面空間；

②傳感器節點具有移動能力，能事先通過某種定位方案，迅速對自身作出確的定位，并能準確移動至計算出的最佳位置；

③為了保證網絡的連通性，規定傳感器節點的通信半徑CR大于或等于其感知半徑sR的2倍；

④傳感器節點通過布爾感知模型（1/0感知模型），在其感知半徑內能監測網絡的邊界，并將邊界視作鄰居節點，假設其CR和均為零。

2.2 k重覆蓋節點自定位估算方案

圖2 鄰居節點對傳感器節點s的映射位置

根據應用Voronoi圖實現K重覆蓋的方法，我們可以按照自定位的的方案，將移動傳感器移動到最合適的位置上來實現想要得到的覆蓋，從一重覆蓋知，虛擬半徑變小，那么要實現K重覆蓋，節點的距離從到，所以實際上移動傳感器節點的感知半徑不變只不過是節點之間的距離變小了，它們相互靠近，從使得覆蓋重數增加。實現一重覆蓋或者多重覆蓋，事實上就是改變節點之間距離的變化——分散或者匯聚。

由上得知，把覆蓋區內需要移動的節點S移動1S，且1S坐標為：

為了避免移動傳感器節點移動過程中所有節點無序性和不必要的能量損失，確保自定位估算方案的收斂性，提高效率，需要設定一個無線傳感器節點移動的限制值即門限參數為，也就是節點的原位置到優化位置之間的距離大于門限值時才被允許移動至新位置。如圖3所示，在自定位方案中，為了避免無線傳感器網絡不同步而出現的不必要移動，必須在部署之初設置隨機時間間隔，所有節點之間相互感應并收集鄰節點之間的信息，并周期性地像鄰節點發送信息。最后，每個節點通過計算與最優位置坐標的之間的距離并與門限值比較，決定節點是否需要移動。

在k重的無線傳感器網絡中，根據前文的推論和門限值的設定，每個節點可能移動的最大距離為，平均移動距離為。在自定位估算方案中，傳感器節點在覆蓋區內會由節點密度高的地方向密度低的地方移動來實現均勻分布，因此實現K重覆蓋的復雜度為()On。實際上，在方案中，每一個傳感器節點一般會發現個鄰節點并且計算出最優位置。其時間復雜度為。

圖3 k重覆蓋的節點自定位估算方案

3 仿真結果及其分析

3.1 仿真參數

假設無線傳感器網絡的覆蓋區域是一個無障礙物的二維平面的矩形區域，即為FLL=×（L為覆蓋區域的邊長），其中覆蓋區內所有的節點都是采用布爾感知模型且都具有相同的感知半徑和通信半徑都相同，并隨機的均勻分布在真個區域。使用到的參數如表1。

表1 仿真參數

3.2 仿真過程

（1）在100m×100m 的監測區域中隨機投放k*|S|個節點（其中|S|由公式（3）算出，k可取1，2，3，4等）。在二維平面矩形區域隨機部署傳感器節點，節點的位置坐標可表示為：（2）得出隨機投放傳感器節點后的覆蓋面積，并求出其覆蓋率。（3）對于每一個傳感器節點，定義位于其通信半徑范圍內的所有節點為鄰節點，并按公式（6）求出鄰節點的個數sn并按照公式計算出各鄰節點的映射坐標，在根據公式（7）求出節點的最優位置。

（4）求出節點的原位置與最優位置坐標之間的距離temp，并將其與閾值比較大小，如果大于閾值，則節點就移動至最優位置。

（5）求出傳感器節點經過移動部署后的覆蓋面積，并求出覆蓋率。

（6）增加傳感器節點的數目，節點移動前和移動后均增加相同數目的節點數目，對比不同數目時候的節點覆蓋率。

3.3 結果與分析

以下是k=1，2，3，4重覆蓋的仿真過程的實現圖片，S為覆蓋的最少節點數目。

（1）k=1，S=56

圖4 a 一重覆蓋節點移動前后圖

圖4 b 一重覆蓋覆蓋面積圖

（2）K=2，S=112

圖5 a 二重覆蓋節點移動前后圖

圖5 b 二重覆蓋節點移動前后的覆蓋圖

（3）K=3，S=168