WSN中正三角形剖分的異構(gòu)節(jié)點靜態(tài)部署算法*

金仁成，朱明，車志平，李應(yīng)琛

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

?

WSN中正三角形剖分的異構(gòu)節(jié)點靜態(tài)部署算法*

金仁成，朱明，車志平，李應(yīng)琛

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

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

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò)；靜態(tài)部署；異構(gòu)；正三角形剖分

引言

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

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

1問題描述

1.1相關(guān)假設(shè)

針對本文的研究，做出以下假設(shè)：

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

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

③ 在異構(gòu)節(jié)點靜態(tài)部署策略實施后，各類節(jié)點之間能夠?qū)崿F(xiàn)良好的通信。

1.2感知模型

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

2算法構(gòu)建

2.1基于正三角形網(wǎng)格的同構(gòu)節(jié)點部署模型

圖1　相鄰的3個節(jié)點　呈正三角形結(jié)構(gòu)

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

2.2基于正三角形剖分的異構(gòu)節(jié)點部署模型

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

圖2　相鄰的3個節(jié)點隨正三角形頂點位置變化而出現(xiàn)覆蓋空洞

(1) 異構(gòu)節(jié)點區(qū)域覆蓋建模

圖3　異構(gòu)節(jié)點區(qū)域覆蓋建模

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

由圖3所示幾何關(guān)系可知:

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

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

(2) 確定異構(gòu)節(jié)點最佳感知半徑比例

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

圖4　覆蓋率與感知半徑之比之間的關(guān)系

(3) 監(jiān)測區(qū)域異構(gòu)節(jié)點部署

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

3仿真結(jié)果

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

首先對監(jiān)測區(qū)域進行三角形網(wǎng)格劃分，得到如圖5所示的結(jié)構(gòu)。然后，在圖5所示的正三角形網(wǎng)格單元的頂點部署A類節(jié)點，在中心處部署B(yǎng)類節(jié)點。顯然，由部署后的結(jié)果可知，只在監(jiān)測區(qū)域內(nèi)的網(wǎng)格單元頂點和中心處部署節(jié)點不能滿足全覆蓋要求，部分區(qū)域會出現(xiàn)空洞，因此，需要對部分區(qū)域的節(jié)點部署位置進行微調(diào)，得到如圖6所示的結(jié)構(gòu)，其中，圓形節(jié)點是在圖7的基礎(chǔ)上新增加的節(jié)點。

圖5　異構(gòu)節(jié)點在監(jiān)測區(qū)域內(nèi)的部署結(jié)構(gòu)圖

圖7　在正三角形網(wǎng)格單元的頂點及中心部署兩種異構(gòu)節(jié)點

結(jié)語

參考文獻

[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] 曹峰,劉麗萍,王智.能量有效的無線傳感器網(wǎng)絡(luò)部署[J].信息與控制,2006,35(2):147-153.

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

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

[5] 冀文娟,石為人,李明,等.異構(gòu)無線傳感器網(wǎng)絡(luò)中多目標優(yōu)化節(jié)點部署策略[J].傳感器與微系統(tǒng),2012(3):29-31,35.

[6] 俞黎陽,王能,張衛(wèi).異構(gòu)無線傳感器網(wǎng)絡(luò)中異構(gòu)節(jié)點的部署與優(yōu)化[J].計算機科學,2008(9):48-51.

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

[8] 馮秀芳,關(guān)志艷,全欣娜.基于虛擬力的異構(gòu)節(jié)點網(wǎng)絡(luò)覆蓋增強算法[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

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