水下三維無線傳感器網絡節點部署研究*

黃　玨　顏　冰

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

?

水下三維無線傳感器網絡節點部署研究*

黃玨顏冰

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

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

關鍵詞三維無線傳感器網絡; 節點部署; 空間填充多面體; 覆蓋性; 連通性

Class NumberTP291.1

1引言

本文針對三維網絡空間中傳感器節點位置部署問題進行研究，對空間填充多面體進行了分析，推導計算了在rc/rs為任何比值下應用各空間填充多面體時節點部署坐標的相互關系，最后對截頂正八面體的部署節點坐標進行了仿真。

2問題描述

為了更好地研究傳感器節點對特定空間的全覆蓋問題，作如下的假設:

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

2) 傳感器的通信范圍為空間內任何與傳感器的距離小于rc的節點。

3) 網絡中所有的傳感器都具有相同的測量和通信范圍。

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

假設傳感器網絡節點可以根據拓撲控制算法的需要部署在空間的任意位置，為了滿足空間的完全覆蓋性，所有的節點都能與自身的所有相鄰節點保持連通性，本文所要研究的問題即為如何使用最少的傳感器節點對三維空間進行覆蓋，同時部署傳感器節點的坐標計算問題。

3問題分析

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

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

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

4節點部署坐標計算

對各種常見的空間填充多面體進行分析，推導出各種部署模式下傳感器部署的位置坐標。

4.1立方體

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

(1)

(x,y,z)=

(2)

其中，u，v，w為整數。

4.2正六棱柱

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

圖1　正六棱柱部署情況

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

(3)

(4)

(5)

------------------------------其中，u，v，w為整數。

4.3菱形十二面體

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

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

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

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

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

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

(x,y,z)=

(6)

其中，u，v，w為整數。

4.4截頂正八面體

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

假設中心到截頂正八面體的頂點的距離為R，以中心為坐標原點建立空間直角坐標系xyz，圖形在xy平面內的投影如圖7所示。

圖7　截頂正八面體xy平面內投影

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

(7)

其中，u，v，w為整數。

5基于截頂正八面體的節點部署坐標實例

圖8　節點部署示例

這種部署方式完成了對一個平行六面體的完全覆蓋，并且保持了各節點之間的連通性。

6結語

本文根據常用的規則填充多面體的節點部署模式，在充分考慮傳感器節點的探測范圍和連通范圍的基礎上，分析計算了各種部署模式在填充時各個節點的部署坐標，最后對截頂正八面體的部署模式進行了仿真，為水下三維傳感器節點的部署提供了方法。

參 考 文 獻

[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] 溫俊，竇強，蔣杰，等.無線傳感器網絡中保證覆蓋的最少節點部署[J].國防科技大學學報，2009,31(3):76-81.

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

[9] 張云洲，吳成東，程龍，等.確定性空間的無線傳感器網絡節點部署策略研究[J].控制與決策，20105(11):1625-1629.

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

[11] 劉麗萍，王智，孫優賢.無線傳感器網絡部署及其覆蓋問題研究[J].電子與信息學報，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日

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

中圖分類號TP291.1

DOI：10.3969/j.issn.1672-9730.2016.05.039