WSN中一種改進的節點部署方案

張 凱

(武漢理工大學信息工程學院，湖北武漢 430070)

0 引言

無線傳感器網絡是近年來受到國內外廣泛關注的研究熱點。在工作過程中節點會不斷地感知到周邊環境的數據，并將通過無線天線將數據以多跳的方式發送給遠方的Sink節點(或稱為基站)進行處理，節點的部署方案將直接影響數據收集和網絡生存期等性能。因此，如何有效地對節點進行部署［1］成為無線傳感網進行數據收集和處理的關鍵。

1 相關工作

目前，對于無線傳感網的節點部署研究工作較多，文獻［2］針對傳感器網絡節點部署時首要考慮的是覆蓋問題，提出一種可以滿足不同覆蓋率要求的節點優化部署算法，在提高節點覆蓋性能的同時優化節點數量，降低網絡的配置代價。仿真結果證明，該算法可最大化節點的覆蓋效率;文獻［3］為提高無線傳感器網絡的節點覆蓋度，提出一種目標關聯覆蓋算法，利用節點間的關聯性和動態分組調整覆蓋區域，利用貪心算法對覆蓋區域進行優化，以保證所關注的目標節點被傳感器節點均勻覆蓋，同時提高網絡資源的利用率。在每個周期內喚醒部分節點，輪流進行工作，以均衡網絡能量消耗。實驗結果表明，該算法適應性更強，并且能有效降低網絡能耗，提高網絡性能;文獻［4］針對現有的節點調度算法不能同時保證工作節點均勻分布，使網絡能耗不均衡的問題，提出了一種與節點位置無關的無線傳感器網絡覆蓋協議(EBLCP)。EBLCP在虛擬坐標的基礎上建立臨時集，節點只需與鄰居中少量節點通信，比較這些節點的剩余能量從而競選工作節點。實驗結果表明，EBLCP能保證較高的覆蓋率，并延長網絡生存時間。然而，以上的部署算法都是建立在節點的感知范圍無邊界或者邊界效應可以忽略的假設上。事實上，在實際的場景中，邊界的存在對于網絡的連通覆蓋具有重大的影響，而現有的“修補”方法雖然可以保證連通覆蓋薄弱區域，但是卻提高了網絡部署的成本，并會造成節點分布不均勻的狀況。針對以上問題，提出了一種改進的無線傳感器節點部署算法，理論分析和仿真實驗表明，所提出的方案是有效的。

2 相關定義與建模分析

2.1 相關定義

令CN表示節點N的覆蓋范圍，⊙N表示節點N覆蓋圓的圓周。A，B，C，D，E 為凸邊形的頂點，如圖1所示。

圖1 凸角多邊形abcde的定義

定義1 內分點(IPD):指凸多邊形的內部任一頂點中，位于其他頂點的內角平分線上且與其他頂點的歐式距離為d的點，d∈［0，rN］。如圖1中點A1，B1，C1，D1，E1。

定義2 邊界線(BL):指從一個內分點到另一個內分點所做的平行于邊界的直線。

定義3 邊界點(BP):指位于邊界線上除內分點以外的其他所有頂點。

定義4 邊角交點(IPF):角點的感應圓圈與邊點線的交點。

2.2 網絡模型

將監測區域π模擬為二維平面內的不規則凸角多邊形δ，邊界信息已知，凸角多邊形其邊界頂點位置依據順時針方向標記為 {a，b，c…}。這里假設無線傳感網具有以下性質:

①所有節點部署后保持靜止，不再移動;

②所有節點以自身為圓心，在其感知范圍為進行感知，所有節點的感知半徑一致，均為rsame;

③ 對于任意節點x，y而言，僅當d(x，y)≤rsame時，則認為節點x被節點y覆蓋。d(x，y)表示2個節點間的歐式距離。

3 改進的部署方案

本文提出的改進的節點部署方案命名為IDS。它主要由2個部分組成:首先，對于感知區域進行邊界的部署，達到保證全連通和覆蓋的效果，然后在感知區域內，通過凸多邊形生成算法來不斷地進行內部部署，遞歸調用知道整個感知區域被覆蓋。

3.1 邊界部署

邊界部署的主要目的是保證部署后的節點能夠覆蓋整個感知區域的邊界。部署過程如下:①根據δ的頂點信息，確定對應δ每個凸角的角度和角點;②確定與每個內分點對應的邊界線;③依據式(1)和式(2)來確定每條邊界線上的邊界點［1］。

3.2 新凸邊形的生成

邊界部署完成后，δ并沒有被完全覆蓋，生成了多個邊角交點IPF，如圖2所示。

圖2 邊界的生成

由于現在未被覆蓋區域的邊界形狀變得更加復雜，因此GRLD算法的第2部分旨在生成新的邊界，形成新的凸多邊形區域。思想如下:過每個IPF做平行于對應邊界的平行線，以這些平行線的交點為新的頂點，順時針連接形成新的凸角多邊形。

3.2.1 算法2:新凸邊形生成算法

3.2.2 算法3:改進后的部署算法

結合算法1和算法2遞歸調用，即得到本文提出的IDS算法如下:

4 仿真實驗

這里使用MATLAB2011對IDS進行仿真實驗，并與目前較為典型的部署方案(六邊形點陣和四邊形點陣)進行了性能比較分析。實驗過程中，節點的感應半徑設定為5 m，通信半徑設為10 m。實驗結果如圖3(a)所示。

實驗結果是當感應區域為三角形、四邊形、六邊形和任意形狀時，使用IDS、六邊形點陣和四邊形點陣進行部署時，所需要使用到的節點個數比較。結果表明，就達到完全覆蓋效果上來看，IDS使用的節點個數是最少的。這主要是因為，IDS方案從邊界開始布點，克服了部署后“修補”薄弱區域所需要的節點，從而大大減少了節點感應區域的疊加，增大節點的有效覆蓋面積，使得浪費減少。

圖3 不同部署方案的節點個數變化

圖3(b)表示的是放感知區域面積變化時，使用IDS、六邊形點陣和四邊形點陣部署的節點個數變化情況，從中可以看出，當δ的面積從4320 m2增大到67500 m2時，IDS所需的節點個數的增幅為1500個，六邊形點陣下所需的節點個數的增幅為2100，四邊形點陣下的節點增幅為2400個。即IDS只需要增加較少數量的節點就能達到和六邊形點陣有更小的節點增幅，說明其相對于四邊形點陣、四邊形點陣一樣的覆蓋效果，因此本文的方法更容易擴展，穩定性更好。

5 結束語

如何有效地部署傳感網節點對于提高無線傳感網的數據傳輸質量以及延長網絡生命周期具有重要的影響。在傳統的部署算法上，進一步考慮了邊界效應對于網絡連通和覆蓋的影響，提出了一種改進的節點部署方案IDS。理論分析和仿真實驗表明，本文方法是有效的，相比于六邊形點陣和四邊形點陣的部署效果而言，IDS所需使用的節點個數也更少，且算法更容易擴展。下一步的工作是對現有的部署方案進行拓展，研究三維區域內的確定性部署方案。 ■

［1］LIAO Z，WANG J，WANG X，et al.GRLD:A Seamless Growth Rings like Deployment of Sensors Avoiding Boundary Effects in WSNs［C］∥Wireless Communications and Networking Conference(WCNC)，IEEE，2010:1 －6.

［2］孫澤宇，邢蕭飛，魏 巍.無線傳感器網絡中的目標關聯覆蓋算法［J］.計算機工程，2011，37(9):138 －140.

［3］朱繼華，武 俊，陶 洋.基于覆蓋率的傳感器優化部署算法［J］.計算機工程，2011，36(3):94 －96.

［4］孫澤宇，邢蕭飛，魏 巍.無線傳感器網絡中的目標關聯覆蓋算法［J］.計算機工程，2011，37(9):138 －140.

［5］ZHANGH，HOU J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］.Ad Hoc ＆Sensor Wireless Networks，2005，1(1):89 －124.

［6］IYENGARR，KAR K，BANERJEE S.Low-coordination Topologies for Redundancy in Sensor Networks［C］∥The 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2005:332 －342.

［7］BAIX，XUAN D，YUN Z，etal.Complete Optimal Deployment Patterns for Full-coverage and k-connectivity(k≤6)［C］∥The 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2008:401－410.

［8］WANG X，SUN F，KONG X.Research on Optimal Coverage Problem of Wireless Sensor Networks［C］∥International Conference on Communications and Mobile Computing，2009:548－551.