王　軍，倪雪莉，程　勇

（1.南京信息工程大學 計算機與軟件學院，江蘇 南京210044；2.南京信息工程大學 網(wǎng)絡信息中心，江蘇 南京210044）

基于網(wǎng)格劃分和虛擬力的水下傳感器網(wǎng)絡部署策略*

王軍1，2，倪雪莉1，程勇2

（1.南京信息工程大學 計算機與軟件學院，江蘇 南京210044；2.南京信息工程大學 網(wǎng)絡信息中心，江蘇 南京210044）

針對三維水下傳感器網(wǎng)絡存在的節(jié)點部署稀疏、水下節(jié)點昂貴、網(wǎng)絡部署成本高、三維環(huán)境復雜等問題，提出了一種基于網(wǎng)格劃分和虛擬力的網(wǎng)絡部署策略。該策略研究了三維空間多面體填充問題，將水平面劃分為一定大小的網(wǎng)格，對水面上的節(jié)點運行虛擬力算法，使節(jié)點均勻擴散開，落在同一網(wǎng)格的節(jié)點通過控制浮標與節(jié)點間的纜繩長度控制節(jié)點在垂直方向的移動，形成三維水下傳感器網(wǎng)絡。仿真實驗結果表明，該策略能夠以更小的節(jié)點數(shù)目達到更高的三維空間網(wǎng)絡覆蓋效率，從而有效地減少網(wǎng)絡的部署成本。

水下傳感器網(wǎng)絡；多面體填充；網(wǎng)格劃分；虛擬力算法；三維

0　引言

隨著半導體技術、微系統(tǒng)技術、通信技術、計算機技術的飛速發(fā)展，集感知、存儲、通信功能于一體的無線傳感器網(wǎng)絡技術及相關研究工作在各個國家轟轟烈烈開展起來[1]。水下傳感器網(wǎng)絡（Underwater Sensor Networks，USN）作為傳感器網(wǎng)絡系統(tǒng)中的一個重要領域，廣泛應用于海洋資源的勘測、海水污染的監(jiān)測、海洋數(shù)據(jù)的收集以及軍事領域的水下監(jiān)視、偵查等方面[2-3]。

相較于傳統(tǒng)的陸上傳感器網(wǎng)絡，水下傳感器網(wǎng)絡有其自身的特性：水下節(jié)點較昂貴，大規(guī)模密集部署成本過高，決定了水下傳感器網(wǎng)絡具有稀疏性；水下傳感器網(wǎng)絡一般通過聲學通信，比一般網(wǎng)絡功耗更大，更要考慮能耗的均衡性[4-5]。在充分考慮水下傳感器網(wǎng)絡特殊性的前提下，如何使用最少的節(jié)點滿足網(wǎng)絡的覆蓋率、如何配置節(jié)點提高網(wǎng)絡的可靠性、防止網(wǎng)絡空洞等問題是水下傳感器網(wǎng)絡的研究熱點。

文獻[6]引入剛性理論，定義了節(jié)點域的“剛性-覆蓋值”作為水下傳感器節(jié)點所處位置的評價指標，設計了剛性驅動的節(jié)點移動策略，從而構建了完整的節(jié)點自組織布置方法。Kemal等[8]提出了一種用錨鏈固定在海底可以調節(jié)深度的節(jié)點構成的水下傳感器網(wǎng)絡，可以很容易達到部署效果，但在部署過程中節(jié)點的能耗較大，不能很好地確保網(wǎng)絡壽命。曾斌等[9]研究了水下傳感器節(jié)點的布置問題，提出的水下傳感器網(wǎng)絡移動方案中考慮了水流的作用，不僅達到了較好的部署效果，而且節(jié)約了能量。

上述方法均有一定的局限性，目前部署效率較高的方式均采用確定性部署，但由于特殊環(huán)境的不可達性及大規(guī)模水下傳感器網(wǎng)絡的應用需求，人工進行傳感器網(wǎng)絡的布置難以順利實現(xiàn)。對于隨機性部署，均采用大量布撒節(jié)點的方式，并未事先對已知區(qū)域進行一系列理論分析，休眠一些節(jié)點對于控制網(wǎng)絡成本來說，效果仍然不大。目前針對水下傳感器網(wǎng)絡隨機部署后進行優(yōu)化的問題研究并不多。

本文針對三維水下傳感器網(wǎng)絡特性，利用三維空間填充理論模型結合二維空間虛擬力算法，設計了一種基于網(wǎng)格劃分和虛擬力的網(wǎng)絡部署策略，在滿足網(wǎng)絡覆蓋率的前提下有效地減少了節(jié)點的部署數(shù)目，降低網(wǎng)絡部署成本。

1　背景知識

1.1三維感知模型

傳感器節(jié)點采用布爾感知模型[11]，感知范圍為以節(jié)點為球心，rs為半徑的球體(rs為傳感器節(jié)點的感知半徑)，即節(jié)點只覆蓋球體范圍以內的事件，無法感知球體范圍以外的事件。那么，三維空間中位于點(ai，bi，ci)的事件 ei被位于(xj，yj，zj)的節(jié)點 sj覆蓋的概率如式(1)。

其中d(ei，sj)為 ei與 sj之間的歐氏距離，如式(2)。

1.2覆蓋效率

為了衡量節(jié)點覆蓋范圍的利用率，引入網(wǎng)絡覆蓋效率CE，定義為區(qū)域中所有節(jié)點的有效覆蓋范圍的并集與所有節(jié)點覆蓋范圍之和的比值，如式(3)。

其中Ai為節(jié)點Si的覆蓋范圍。

1.3三維最優(yōu)填充

文獻[12]引入了一個度量標準：體積系數(shù)（volumetric quotient），其計算公式如式(4)。

要節(jié)點數(shù)目最小，在給定感知半徑r的情況下，Voronoi單元體積要最大，所以，要找到空間填充多面體，其體積系數(shù)最大。

文獻[12]將立方體、六棱柱、菱形十二面體、截角八面體相比較，分別算出其體積系數(shù)大小，結果表明，截角八面體的體積系數(shù)最大，為 0.683 29，所以截角八面體的Voronoi分割部署策略所需的節(jié)點數(shù)目最少。

2　算法描述

2.1基本假設

為了便于模型的建立和描述，給出以下假設：

(1)初始狀態(tài)下，節(jié)點隨機分布在水面上，忽略水平面的起伏，忽略障礙物影響。

(2)傳感器節(jié)點的感知范圍為規(guī)則球體，通信半徑為感知半徑的兩倍。

(3)節(jié)點間存在虛擬力(引力和斥力)，在力的作用下，節(jié)點可相對運動。

(4)水下傳感器節(jié)點能夠通過纜繩，在垂直方向上準確地移動到指定深度。

2.2問題描述

初始狀態(tài)下，節(jié)點由飛機、船舶等設備布撒在觀測水域，調整浮標與節(jié)點間的纜繩長度來確定節(jié)點在垂直方向上的位置，由于初始位置與纜繩長度未知，隨機部署的水下傳感器網(wǎng)絡必然存在覆蓋空洞和冗余。需要建立一定的模型，將隨機部署的節(jié)點通過一定的策略部署到相應位置，實現(xiàn)用更少的節(jié)點完成目標水域的全覆蓋。

假定有三維水下目標區(qū)域R，傳感器節(jié)點集合S= {s1，s2，s3…sn}，傳感器節(jié)點數(shù)目為 n，傳感器節(jié)點感知半徑為 rs。

如果對于?p∈R，?si∈S，使得 d(p，si)≤rs，則目標區(qū)域R被節(jié)點集合S完全覆蓋。

所以，問題可描述為：設計水下傳感器網(wǎng)絡部署策略，使得實現(xiàn)目標水域完全覆蓋所用的傳感器節(jié)點數(shù)n最少。

圖1　體心立方格

圖2　截角八面體體心立方格堆砌

2.3基本思想

2.3.1網(wǎng)格劃分

由三維空間填充理論可知，三維空間的最優(yōu)覆蓋為體心立方格覆蓋，如圖1。體心立方格的Voronoi單元為截角八面體,如圖2，其俯視圖如圖3。將體心立方格覆蓋投影到二維平面上，即形成一個正方形網(wǎng)格圖，邊長為a，節(jié)點位于網(wǎng)格的頂點和中心。換個角度，可以觀察到一張新的網(wǎng)格圖（虛線的網(wǎng)格），邊長a′為。根據(jù)幾何關系可知，截角八面體邊長為b，截角八面體兩個相對的正方形面之間的垂直距離為2b，與最初投影得到的正方形網(wǎng)格邊長a相等，由此可得b=，截角八面體的外接球半徑，即傳感半徑rs=，則。則轉換而得的新的網(wǎng)格圖邊長。即在已知水下傳感器節(jié)點感知半徑的情況下，進行平面網(wǎng)格劃分時，網(wǎng)格邊長為。

圖3　體心立方格堆砌俯視圖

2.3.2虛擬力算法

由于水下節(jié)點價格昂貴，所以無法隨機布撒大量節(jié)點，這就導致在網(wǎng)格劃分時，網(wǎng)格中節(jié)點數(shù)目相差過大，會直接影響之后的節(jié)點深度部署。

由此引入虛擬力算法[12]，節(jié)點間存在力的作用（引力和斥力）。當節(jié)點間距離很近時，為斥力；當節(jié)點間距離過大時，為引力。假設節(jié)點間最佳距離為dopt。按照一定的規(guī)則設定節(jié)點間力的作用和距離之間的關系，計算節(jié)點所受的合力，在合力的作用下節(jié)點相對運動，由此可以避免節(jié)點部署得過于集中或稀疏。圖4為節(jié)點受力分析圖。

圖4　節(jié)點受力分析

傳統(tǒng)的虛擬力算法運用在二維空間，所以假設節(jié)點間的最佳距離 dopt=2rs或即可達到應用要求[13]。但本文為水下傳感器網(wǎng)絡部署，要向三維空間擴展，水域的深度不同，水平面上每個網(wǎng)格中所需的節(jié)點數(shù)目不同。假設水域深度為 l，每個網(wǎng)格中所需節(jié)點數(shù)為l/a，即。根據(jù)所需節(jié)點數(shù)目，設置節(jié)點間最佳距離。保證網(wǎng)格中的節(jié)點數(shù)目符合應用要求，且較均衡。

同一網(wǎng)格中的節(jié)點要向水下不同深度部署，引入一個參數(shù)w表示網(wǎng)格中所需的節(jié)點數(shù)目，定義為網(wǎng)格的權重，對于一個p×q的網(wǎng)格區(qū)域，生成p行q列的矩陣。可以通過網(wǎng)格權重的變化，得知網(wǎng)格中的節(jié)點是否達到應用要求。式(7)即為網(wǎng)格的權重。

2.3.3節(jié)點下降深度計算

由上文可知，水下傳感器網(wǎng)絡采用體心立方格形式進行部署，所以網(wǎng)格中的節(jié)點分為兩種，一種是部署在體心立方格的頂點，一種則部署在體心立方格的中心。網(wǎng)格編號采用(i，j)形式，即(1，1)表示第一行第一個網(wǎng)格，(1，2)表示第一行第二個網(wǎng)格，以此類推，(i，j)表示第i行第j個網(wǎng)格。根據(jù)網(wǎng)格編號，將網(wǎng)格進行分類，分為兩類，A和B。

A類(1，1)，(1，3)，(1，5)，…，(2，2)，(2，4)，(2，6)，…，(3，1)，(3，3)，(3，5)，…，即 i和j同時為偶數(shù)或奇數(shù)。B類(1，2)，(1，4)，(1,6)，…，(2，1)，(2，3)，(2，5)，…，(3，2)，(3，4)，(3，6)…，即i和j為一奇一偶。

2.4算法流程

(2)節(jié)點由飛機、船舶等設備隨機布撒到水域平面上以后，運行虛擬力算法，避免節(jié)點過于集中或稀疏。

(4)根據(jù)網(wǎng)格編號確定網(wǎng)格類型與網(wǎng)格中節(jié)點編號N，由中心實體計算出每個節(jié)點下降深度，發(fā)送消息給水域所有節(jié)點，消息內容包括：網(wǎng)格類型、節(jié)點編號、節(jié)點下降深度。節(jié)點收到消息后，調整自身纜繩長度，部署到相應的水下深度。

3　實驗仿真

3.1網(wǎng)絡權重的比較

圖5、圖6由網(wǎng)格權重矩陣可以看出，隨機布撒的節(jié)點分布不均勻，有些區(qū)域節(jié)點過于密集，有些區(qū)域節(jié)點未達到應用要求。

圖5　隨機部署圖

圖6　隨機部署下網(wǎng)格權重圖

運行虛擬力算法后，隨機布撒在水面的節(jié)點分散均勻，節(jié)點分布圖如圖7所示，網(wǎng)格的權重矩陣如圖8。

3.2網(wǎng)絡覆蓋效率的比較

部署節(jié)點數(shù)目由120到240（每隔20取一次）。每次部署運行10次仿真，取均值。圖9顯示了隨著節(jié)點數(shù)目的遞增，隨機部署策略和本文部署策略的網(wǎng)絡覆蓋效率變化對比情況?？芍诒疚牡牟渴鸩呗韵拢W(wǎng)絡的覆蓋效率明顯高于隨機部署，在節(jié)點數(shù)目在200以上時基本實現(xiàn)全覆蓋，而隨機部署240個節(jié)點時，覆蓋效率也僅達到90%，由此可見，本文策略實現(xiàn)了使用較少的節(jié)點達到更高的網(wǎng)絡覆蓋效率。

圖7　運行虛擬力算法后節(jié)點分布圖

圖8　運行虛擬力算法后網(wǎng)格權重圖

圖9　網(wǎng)絡覆蓋率對比圖

4　結論

本文針對三維水下傳感器網(wǎng)絡的應用要求，提出了一種基于網(wǎng)格劃分和虛擬力的網(wǎng)絡部署策略。該策略的特點是基于三維空間填充多面體問題，將三維水下傳感器網(wǎng)絡部署問題簡化為二維水平面預部署問題，套用成熟的二維傳感器網(wǎng)絡部署模型，引入傳統(tǒng)的二維傳感器網(wǎng)絡虛擬力算法，完成水平面?zhèn)鞲衅鞴?jié)點的預處理。通過控制水平面節(jié)點在垂直方向的移動，生成 Voronoi分割單元為截角八面體的體心立方格水下監(jiān)視網(wǎng)絡。在實現(xiàn)網(wǎng)絡全覆蓋的同時，本文部署策略使用的節(jié)點數(shù)目更少，有效地減少了網(wǎng)絡的搭建成本。下一步工作將針對水下傳感器網(wǎng)絡受水流、水生物影響更易失效的特點，在如何引入移動節(jié)點，提高網(wǎng)絡的可靠性，防止網(wǎng)絡空洞的問題上作進一步研究。

[1]孫利民，李建中.無線傳感器網(wǎng)絡[M].北京：清華大學出版社，2005.

[2]Li Shiwei，Wang Wenjing，Zhang Juwei.An underwatersensor network deployment algorithm based on submarine depth[J].傳感技術學報，2012，25(11)：1613-1617.

[3]MARI C D.Securing underwater wireless communication networks[J].IEEE Wireless Communications，2011：22－28.

[4]ONUR E，ERSOY C，DELIC H，et al.Surveillance wireless sensor networks：Deployment quality analysis[J].IEEE Network，2007，21(6)：48-53.

[5]ONUR E，ERSOY C，DELIC H.Analysis of target detection probability in randomly deployed sensor networks[J].IEEE Communication Letters，2007，11(10)：778-780.

[6]夏娜，鄭語晨，杜華爭，等.剛性驅動水下傳感器節(jié)點自組織布置[J].計算機學報，2013，36(3)：494-505.

[7]ALAM S M，HAAS Z J.Coverage and connectivity in threedimensional networks[C].Proceedings of the 12th annual international conference on Mobile computing and networking，2006：346-357.

[8]Kemal Akkaya，Andrew Newell．Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks[J]．Computer Communications，2009(32)：1233－1244.

[9]曾斌，鐘德歡，姚路.考慮水流影響的水下傳感器網(wǎng)絡移動算法研究[J].計算機應用研究，2010，27(10)：3926-3931.

[10]王長生.水下傳感器網(wǎng)絡節(jié)點布置方法研究[D].合肥：合肥工業(yè)大學，2011.

[11]李世偉，王文敬，張聚偉.基于潛艇深度的水下傳感器網(wǎng)絡部署[J].傳感技術學報，2012，25(11)：1613-1617.

[12]田一鳴，陸陽，魏臻，等.無線傳感器網(wǎng)絡虛擬力覆蓋控制及節(jié)能優(yōu)化研究[J].電子測量與儀器學報，2009(11)：65-71.

[13]李享.基于空中傳感網(wǎng)的三維部署研究[D].太原：中北大學，2013.

Underwater sensor deployment based on grid division and virtual forces

Wang Jun1，2，Ni Xueli1，Cheng Yong2
(1.College of Computer&Software，Nanjing University of Information Science&Technology，Nanjing 210044，China；2.Network Information Center，Nanjing University of Information Science&Technology，Nanjing 210044，China)

Underwater Sensor Network(USN)has the problems including sparse node deployment,expensive nodes,great network deployment cost,complex environment.Thus,a deployment strategy based on grid division and virtual forces is designed in this paper.In this strategy,the three dimensional Space-filling polyhedron is studied,the surface of water is divided into some certain size grids,and virtual force algorithm is run on the nodes to spread evenly.Nodes which fall in the same grid adjust the rope distance between the underwater sensor node and the float node to construct a 3D underwater network.The simulation results show that the strategy can achieve higher coverage quality with smaller number of nodes,thus effectively reduce the deployment cost of the network.

Underwater Sensor Network(USN)；space-filling polyhedron；grid division；virtual force；three-dimensional space

TP393.02

A

10.16157/j.issn.0258-7998.2016.02.028

國家自然科學基金資助項目(61402236，61373064)，江蘇省農業(yè)氣象重點實驗室開放基金資助（KYQ1309），江蘇省“六大人才高峰”項目(2013-DZXX-019)，江蘇省產學研前瞻性聯(lián)合研究項目（BY2014007-2），公益性行業(yè)（氣象）科研專項（GYHY201106037）

2015-09-08)

王軍（1970-），男，碩士，教授，主要研究方向：無線傳感器網(wǎng)絡部署算法、物理信息融合。

倪雪莉（1990-），通信作者，女，碩士，學生，主要研究方向：無線傳感器網(wǎng)絡部署算法，E-mail：624711801@qq. com。

程勇（1980-），男，博士，講師，主要研究方向：無線傳感器網(wǎng)絡部署算法。

中文引用格式：王軍，倪雪莉，程勇.基于網(wǎng)格劃分和虛擬力的水下傳感器網(wǎng)絡部署策略[J].電子技術應用，2016，42 (2)：102-105，109.

英文引用格式：Wang Jun，Ni Xueli，Cheng Yong.Underwater sensor deployment based on grid division and virtual forces[J]. Application of Electronic Technique，2016，42(2)：102-105，109.