WSN中正三角形剖分的異構節點靜態部署算法*

金仁成，朱明，車志平，李應琛

(大連理工大學 遼寧省微納米技術及系統工程重點實驗室，大連 116024)

?

WSN中正三角形剖分的異構節點靜態部署算法*

金仁成，朱明，車志平，李應琛

(大連理工大學 遼寧省微納米技術及系統工程重點實驗室，大連 116024)

摘要:針對無線傳感器網絡異構節點靜態部署問題，提出了一種基于正三角形剖分的異構節點部署算法。將監測區域進行正三角形網格劃分，利用網格單元頂點及中心位置信息，在正三角形網格單元的頂點處部署感知半徑較大的節點，在中心部署感知半徑較小的節點，使不同感知半徑的節點得到充分利用，保證了監測區域的覆蓋率要求。

關鍵詞:無線傳感器網絡；靜態部署；異構；正三角形剖分

引言

無線傳感器網絡(WSN)節點部署，是在指定的監測區域內，適當布置傳感器節點以滿足特定需求。傳感器節點布置的好壞直接決定了WSN所能提供的“感知”服務質量[1]。通常有2種傳感器節點部署策略：確定性部署和隨機部署。確定性部署一般用于監測環境簡單的情形，借助人工在區域內手動部署節點以滿足特定的覆蓋要求；而隨機部署則更多用于監測環境復雜多變的情況，隨機部署后，借助節點的移動能力，采用一些部署算法來實現監測區域的良好覆蓋。

針對異構傳感器網絡節點部署問題，本文以節點感知半徑作為異構問題的研究對象，提出了一種基于正三角形剖分的異構節點靜態部署算法。運用算法對監測區域進行網格劃分，在正三角形網格的頂點處部署感知半徑較大的傳感器節點，在中心部署感知半徑較小的傳感器節點，充分利用異構節點不同的感知能力，實現監測區域的良好覆蓋。

1問題描述

1.1相關假設

針對本文的研究，做出以下假設：

① 所有的傳感器節點具有相同的通信、計算以及移動能力等，只有節點的感知半徑存在異構特性。

② 所有傳感器節點不可移動，處于同一平面，并且節點的感知范圍和通信范圍都是理想的圓形。

③ 在異構節點靜態部署策略實施后，各類節點之間能夠實現良好的通信。

1.2感知模型

為了簡化問題研究，作為二元感知模型傳感器節點的模型。當點si與P之間的距離在節點的感知范圍內時，節點能采集到P點信息的概率為1；當點si與P之間的距離在感知范圍外時，節點能采集到P點信息的概率為0，如下所示：

2算法構建

2.1基于正三角形網格的同構節點部署模型

圖1　相鄰的3個節點　呈正三角形結構

如圖1所示，3個感知半徑相同的同構節點呈現正三角形結構(圖中未畫出)時，節點的覆蓋率達到82.7%，此時網絡的覆蓋率最高，節點冗余最小。

2.2基于正三角形剖分的異構節點部署模型

依據參考文獻[2]的思想，參考文獻[7]對如圖1所示的結構進行了變形，并進一步提出了兩種感知半徑的傳感器節點動態部署模型。如圖2所示，將圖1中的正三角形的邊長擴大，圖中的節點隨正三角形頂點位置的變化而變化。由于節點的感知半徑不變，節點位置發生變化時，正三角形的中心必定出現空隙，因此形成覆蓋空洞，如圖2右側所示，如果在中心處小圓表示的覆蓋空洞處另外部署一個感知半徑較小的節點，那么覆蓋空洞的問題就可迎刃而解。

圖2　相鄰的3個節點隨正三角形頂點位置變化而出現覆蓋空洞

(1) 異構節點區域覆蓋建模

圖3　異構節點區域覆蓋建模

圖2只在直觀上對呈正三角形結構部署的節點間距離變化造成的空洞進行了展示，并單純地加入一個感知半徑較小的節點來解決覆蓋空洞問題。這里，通過建立異構節點區域覆蓋模型，來探討這兩類節點之間的數量關系。假設圖3所示的一種節點的感知半徑為R1，另一種感知半徑為R2，并且R1>R2，R1/R2=k。這里，設R1=r，R2=r/k。

由圖3所示幾何關系可知:

從而可知，三角形的面積為：

兩種感知半徑的4個節點的覆蓋率為：

(2) 確定異構節點最佳感知半徑比例

借助Matlab可以得到覆蓋率與感知半徑之比k之間的關系圖，如圖4所示。

圖4　覆蓋率與感知半徑之比之間的關系

(3) 監測區域異構節點部署

經過以上分析，確定了覆蓋率取得最大值時兩種異構節點感知半徑之比。借助參考文獻[2]的網格劃分思想，針對本文討論的異構節點部署，對監測區域進行網格劃分。以正三角形作為網格劃分單元，在網格單元的頂點處部署感知半徑較大的節點，在中心部署感知半徑較小的節點。

3仿真結果

為了更加詳細地展示本文的思想，借助Matlab對上述算法進行仿真實驗。在實驗中，選取兩種感知半徑的傳感器節點，A類節點的感知半徑Ra=4，B類節點的感知半徑Rb=0.72，在50×50的監測區域內部署。

首先對監測區域進行三角形網格劃分，得到如圖5所示的結構。然后，在圖5所示的正三角形網格單元的頂點部署A類節點，在中心處部署B類節點。顯然，由部署后的結果可知，只在監測區域內的網格單元頂點和中心處部署節點不能滿足全覆蓋要求，部分區域會出現空洞，因此，需要對部分區域的節點部署位置進行微調，得到如圖6所示的結構，其中，圓形節點是在圖7的基礎上新增加的節點。

圖5　異構節點在監測區域內的部署結構圖

圖7　在正三角形網格單元的頂點及中心部署兩種異構節點

結語

參考文獻

[1] Li J H,Yu M.Sensor coverage in wireless ad hoc sensor networks[J].International Journal of Sensor Networks,2007,2(3-4):218-229.

[2] 曹峰,劉麗萍,王智.能量有效的無線傳感器網絡部署[J].信息與控制,2006,35(2):147-153.

[3] 凡志剛,郭文生,桑楠.一種基于蜂窩網格的傳感器節點部署算法[J].傳感器與微系統,2008(4):15-17.

[4] 周彤,洪炳.基于虛擬力的混合感知網節點部署[J].計算機研究與發展,2015,44(6):965-972.

[5] 冀文娟,石為人,李明,等.異構無線傳感器網絡中多目標優化節點部署策略[J].傳感器與微系統,2012(3):29-31,35.

[6] 俞黎陽,王能,張衛.異構無線傳感器網絡中異構節點的部署與優化[J].計算機科學,2008(9):48-51.

[7] 陳杰,杜慶偉,李曉禹,等.概率模型下異構傳感器網絡部署算法的研究[J].小型微型計算機系統,2012(1):49-53.

[8] 馮秀芳,關志艷,全欣娜.基于虛擬力的異構節點網絡覆蓋增強算法[J].計算機工程,2009(5):103-105.

(責任編輯：薛士然收修改稿日期：2016-01-14)

Heterogeneous Nodes Static Deployment Algorithm Based on Equilateral Triangle Partition in WSN

Jin Rencheng,Zhu Ming,Che Zhiping,Li Yingchen

(Key Laboratory for Micro/Nano Technology and System of Liaoning Province,Dalian University of Technology,Dalian 116024,China)

Abstract：Aiming at the problem of heterogeneous nodes static deployment of the wireless sensor network,a deployment algorithm based on the equilateral triangle partition is proposed.Firstly,the sensing field is drawn into lots of equilateral triangle grids.Then using the location information of each equilateral triangle’s center and vertex,the nodes with bigger sensing range are deployed in the vertex of equilateral triangle grids and the nodes with smaller sensing range in the center of it.Lastly,the nodes with different sensing range can be fully used and the coverage requirement of the sensing field can be ensured at the same time.

Key words:wireless sensor network;static deployment;heterogeneous;equilateral triangle partition

中圖分類號:TP393.17

文獻標識碼:A

* 基金項目：國家重點基礎研究發展計劃(973計劃)資助項目(2009CB320300)；國家“十二五”科技支撐計劃資助項目(2011BAG05B02)。