黃　玨　顏　冰

(海軍工程大學(xué)兵器工程系　武漢　430033)

?

水下三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署研究*

黃玨顏冰

(海軍工程大學(xué)兵器工程系武漢430033)

摘要在地面無線傳感器網(wǎng)絡(luò)中，一般是假設(shè)所有的傳感器節(jié)點(diǎn)都處于同一個(gè)二維平面上，而對(duì)于水下傳感器網(wǎng)絡(luò)來說，由于傳感器節(jié)點(diǎn)可以部署在不同的海深，因此也就構(gòu)建了一個(gè)三維網(wǎng)絡(luò)。論文針對(duì)水下三維傳感器網(wǎng)絡(luò)的部署問題進(jìn)行研究，分析了常用的空間填充多面體在空間部署中的特性，給出了各種空間填充多面體在空間中的部署模式，進(jìn)一步提出了在保持完全覆蓋和連通的前提下各個(gè)節(jié)點(diǎn)部署坐標(biāo)之間的相互關(guān)系，并對(duì)截頂正八面體的部署方式進(jìn)行了仿真。為三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署提供了方法。

關(guān)鍵詞三維無線傳感器網(wǎng)絡(luò); 節(jié)點(diǎn)部署; 空間填充多面體; 覆蓋性; 連通性

Class NumberTP291.1

1引言

本文針對(duì)三維網(wǎng)絡(luò)空間中傳感器節(jié)點(diǎn)位置部署問題進(jìn)行研究，對(duì)空間填充多面體進(jìn)行了分析，推導(dǎo)計(jì)算了在rc/rs為任何比值下應(yīng)用各空間填充多面體時(shí)節(jié)點(diǎn)部署坐標(biāo)的相互關(guān)系，最后對(duì)截頂正八面體的部署節(jié)點(diǎn)坐標(biāo)進(jìn)行了仿真。

2問題描述

為了更好地研究傳感器節(jié)點(diǎn)對(duì)特定空間的全覆蓋問題，作如下的假設(shè):

1) 傳感器的測量范圍為以自身位置為球心，以探測范圍rs為半徑的球形區(qū)域。

2) 傳感器的通信范圍為空間內(nèi)任何與傳感器的距離小于rc的節(jié)點(diǎn)。

3) 網(wǎng)絡(luò)中所有的傳感器都具有相同的測量和通信范圍。

4) 相比于要覆蓋的三維空間網(wǎng)絡(luò)，傳感器的測量和通信范圍非常小，邊界效應(yīng)可以忽略不計(jì)。

假設(shè)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)可以根據(jù)拓?fù)淇刂扑惴ǖ男枰渴鹪诳臻g的任意位置，為了滿足空間的完全覆蓋性，所有的節(jié)點(diǎn)都能與自身的所有相鄰節(jié)點(diǎn)保持連通性，本文所要研究的問題即為如何使用最少的傳感器節(jié)點(diǎn)對(duì)三維空間進(jìn)行覆蓋，同時(shí)部署傳感器節(jié)點(diǎn)的坐標(biāo)計(jì)算問題。

3問題分析

在前面的問題描述中，假設(shè)傳感器節(jié)點(diǎn)的通信和測量模型都是球形的，但是，由于球形不具備空間填充的性質(zhì)，定義一種空間填充多面體，這種多面體能夠以沒有空缺沒有重疊的方式緊密地填充一個(gè)三維空間。那么就可以用空間填充多面體來對(duì)網(wǎng)絡(luò)中的虛擬單元進(jìn)行建模，保證虛擬單元中心到該單元最遠(yuǎn)處的距離不超過網(wǎng)絡(luò)節(jié)點(diǎn)的測量范圍，并且相鄰兩個(gè)虛擬單元中心之間的距離不超過節(jié)點(diǎn)的通信距離。

定義(Voronoi分割):假設(shè)三維歐幾里得空間中存在一個(gè)離散發(fā)生點(diǎn)集S={c1,c2,…,cn}，對(duì)于S中的某一發(fā)生點(diǎn)ci(ci∈S′)來說，在歐幾里得空間中，所有滿足到發(fā)生點(diǎn)ci的距離小于到S中其他發(fā)生點(diǎn)距離的所有點(diǎn)組成的集合，構(gòu)成了一個(gè)凸多面體的內(nèi)部空間，我們把這個(gè)凸多面體成為發(fā)生點(diǎn)ci的Voronoi單元。S中所有發(fā)生點(diǎn)的Voronoi單元可以用來對(duì)整個(gè)三維空間進(jìn)行分割，稱為關(guān)于發(fā)生點(diǎn)集S的Voronoi分割。

立方體、正六棱柱、菱形十二面體和截頂正八面體為獨(dú)立填充三維空間的多面體，將傳感器部署在填充多面體的中心，那么填充多面體構(gòu)成對(duì)三維空間的Voronoi分割，從而對(duì)三維空間進(jìn)行了完全覆蓋。

4節(jié)點(diǎn)部署坐標(biāo)計(jì)算

對(duì)各種常見的空間填充多面體進(jìn)行分析，推導(dǎo)出各種部署模式下傳感器部署的位置坐標(biāo)。

4.1立方體

立方體是非常簡單、非常直觀的一種部署模式，在三維空間中，每個(gè)傳感器節(jié)點(diǎn)的部署位置在立方體的中心，節(jié)點(diǎn)監(jiān)測范圍所形成的Voronoi單元為其所在的立方體。

(1)

(x,y,z)=

(2)

其中，u，v，w為整數(shù)。

4.2正六棱柱

傳感器節(jié)點(diǎn)部署在正六棱柱的中心，所形成的Voronoi單元為正六棱柱，那么傳感器節(jié)點(diǎn)的部署位置為正三棱柱的頂點(diǎn)，傳感器部署情況如圖1所示。

圖1　正六棱柱部署情況

圖2　正六棱柱在xy平面上投影

(3)

(4)

(5)

------------------------------其中，u，v，w為整數(shù)。

4.3菱形十二面體

菱形十二面體具有全等的十二個(gè)菱形面，取兩個(gè)完全相同的立方體，其中一個(gè)沿四條對(duì)角線切割，形成了六個(gè)正四棱錐，將這六個(gè)四棱錐分別疊放在另一個(gè)立方體的六個(gè)面上，這樣就形成了一個(gè)菱形十二面體。將傳感器節(jié)點(diǎn)部署在菱形十二面體的中心，節(jié)點(diǎn)的Voronoi單元即為其所在的菱形十二面體。部署情況如圖3所示。

假設(shè)菱形十二面體的中心到其頂點(diǎn)的距離為R，以中心為原點(diǎn)建立空間直角坐標(biāo)系xyz，菱形十二面體在xy平面上的投影如圖4所示。

圖3　 菱形十二面體部署情況

圖4　菱形十二面體在xy平面上的投影

菱形十二面體在xz平面上的投影如圖5所示。

圖5　菱形十二面體在xz平面上的投影

(x,y,z)=

(6)

其中，u，v，w為整數(shù)。

4.4截頂正八面體

截頂正八面體是將正八面體的每個(gè)頂點(diǎn)在邊長的1/3處、沿垂直于頂點(diǎn)與中心連線的方向切割，形成了由六個(gè)正方形和八個(gè)正六邊形圍成的空間立體圖形。將傳感器節(jié)點(diǎn)部署在中心，傳感器節(jié)點(diǎn)所形成的Voronoi單元為其所在的截頂正八面體，部署情況如圖6所示。

假設(shè)中心到截頂正八面體的頂點(diǎn)的距離為R，以中心為坐標(biāo)原點(diǎn)建立空間直角坐標(biāo)系xyz，圖形在xy平面內(nèi)的投影如圖7所示。

圖7　截頂正八面體xy平面內(nèi)投影

圖6　截頂正八面體部署情況

(7)

其中，u，v，w為整數(shù)。

5基于截頂正八面體的節(jié)點(diǎn)部署坐標(biāo)實(shí)例

圖8　節(jié)點(diǎn)部署示例

這種部署方式完成了對(duì)一個(gè)平行六面體的完全覆蓋，并且保持了各節(jié)點(diǎn)之間的連通性。

6結(jié)語

本文根據(jù)常用的規(guī)則填充多面體的節(jié)點(diǎn)部署模式，在充分考慮傳感器節(jié)點(diǎn)的探測范圍和連通范圍的基礎(chǔ)上，分析計(jì)算了各種部署模式在填充時(shí)各個(gè)節(jié)點(diǎn)的部署坐標(biāo)，最后對(duì)截頂正八面體的部署模式進(jìn)行了仿真，為水下三維傳感器節(jié)點(diǎn)的部署提供了方法。

參 考 文 獻(xiàn)

[1] Watfa M,Commuri S.A coverage algorithm in 3D wireless sensor network[C]//The 1stInt Symposium on Wireless Pervasive Computing.Phuket:IEEE Press,2006:10-16.

[2] Akkaya K,Newell A.Self-deployment of sensors for maximize coverage in underwater sensor network[J].Elsevier J of Computer Communications,2009,32(7):1233-1244.

[3] Alam S N,Haas Z J,Coverage and connectivity in three-dimensional underwater sensor networks[C]//Proc of ACM MobiCom.Los Angeles:ACM Press,2006:346-357.

[4] Dario Pompili, Tommaso Melodia, Lan F.Akyildiz.Deployment Analysis in Underwater Acoustic Wireless Sensor Networks[C]//WUWNet’06,September 25,2006:48-55.

[5] S.M.Nazrul Alam, Zygmunt J. Haas. Topology Control and Network Lifetime in Three-Dimensional Wireless Sensor Network[J/OL]. http://wnl.ece.cornell.edu.

[6] Wendi B.Heinzelman, Anantha P.Chandrakasan, Hari Balakrishnan. An Application-Specific Protocol Architecture for Wireless Microsensor Netwok[C]//IEEE Transactoins on Wireless Communications,2002(4):660-670.

[7] 溫俊，竇強(qiáng)，蔣杰，等.無線傳感器網(wǎng)絡(luò)中保證覆蓋的最少節(jié)點(diǎn)部署[J].國防科技大學(xué)學(xué)報(bào)，2009,31(3):76-81.

[8] 鐘永信，黃建國，韓晶. 三維無限傳感器網(wǎng)絡(luò)部署、覆蓋和連接問題研究[J].控制與決策，2011,26(10):1447-1451.

[9] 張?jiān)浦?，吳成東，程龍，等.確定性空間的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略研究[J].控制與決策，20105(11):1625-1629.

[10] 何欣，桂小林，安健.面向目標(biāo)覆蓋的無線傳感器網(wǎng)絡(luò)確定性部署方法[J].西安交通大學(xué)學(xué)報(bào)，2010，44(6):6-15.

[11] 劉麗萍，王智，孫優(yōu)賢.無線傳感器網(wǎng)絡(luò)部署及其覆蓋問題研究[J].電子與信息學(xué)報(bào)，2006,28(9):1752-1757.

Node Deployment in Three Dimensional Under-water Wireless Sensor Networks

HUANG JueYAN Bing

(Department of Weaponry Engineering, Naval University of Engineering, Wuhan430033)

AbstractFor the on land wireless sensor network, it is often considered that all the sensors are in one plane. But for the under-water wireless sensor network, the sensors can be deployed at different depths. So the three dimensional sensor networks are built. To solve the problem of the node deployment in three dimensional under-water wireless sensor networks, the character in the space deployment of the space-filling polyhedron is analyzed. And the deployment modes of each space-filling polyhedron are provided. This method can calculate the relationship of the coordinate of each node in promise of both coverage and connectivity. In the end, the deployment of the truncated octahedron is chosen to be simulated. This method provides an effective way to solve the problem of the node deployment in three dimensional under-water wireless sensor networks.

Key Wordsthree dimensional wireless sensor networks, node deployment, space-filling polyhedron, coverage, connectivity

* 收稿日期：2015年11月24日,修回日期：2015年12月30日

作者簡介：黃玨，男，博士研究生，研究方向：軍用目標(biāo)識(shí)別及信息感知技術(shù)。顏冰，女，博士，教授，研究方向：軍用目標(biāo)識(shí)別及信息感知技術(shù)。

中圖分類號(hào)TP291.1

DOI：10.3969/j.issn.1672-9730.2016.05.039