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

(大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，大連 116024)

?

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

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

(大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，大連 116024)

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

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

引言

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

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

1問題描述

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

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

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

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

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

1.2感知模型

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

2算法構(gòu)建

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3仿真結(jié)果

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

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

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

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

結(jié)語(yǔ)

參考文獻(xiàn)

[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é)點(diǎn)部署算法[J].傳感器與微系統(tǒng),2008(4):15-17.

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

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

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

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

[8] 馮秀芳,關(guān)志艷,全欣娜.基于虛擬力的異構(gòu)節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].計(jì)算機(jī)工程,2009(5):103-105.

(責(zé)任編輯：薛士然收修改稿日期：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

中圖分類號(hào):TP393.17

文獻(xiàn)標(biāo)識(shí)碼:A

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