0 引言

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

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

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

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

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

1 背景知識(shí)

1.1 三維感知模型

    傳感器節(jié)點(diǎn)采用布爾感知模型^[11],，感知范圍為以節(jié)點(diǎn)為球心，r_s為半徑的球體(r_s為傳感器節(jié)點(diǎn)的感知半徑),，即節(jié)點(diǎn)只覆蓋球體范圍以內(nèi)的事件,，無法感知球體范圍以外的事件。那么,，三維空間中位于點(diǎn)(a_i,，b_i，c_i)的事件e_i被位于(x_j,，y_j,，z_j)的節(jié)點(diǎn)s_j覆蓋的概率如式(1)。

1.2 覆蓋效率

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

其中A_i為節(jié)點(diǎn)S_i的覆蓋范圍,。

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

    文獻(xiàn)[12]引入了一個(gè)度量標(biāo)準(zhǔn)：體積系數(shù)（volumetric quotient）,，其計(jì)算公式如式(4)。

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

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

    由此可以推斷,，對(duì)于一個(gè)m×n×k的三維區(qū)域,，用覆蓋半徑為r的傳感器節(jié)點(diǎn)覆蓋，所需最少節(jié)點(diǎn)為N=,。由于截角八面體的外接球半徑為(b為截角八面體各邊的邊長(zhǎng)),，所以

2 算法描述

2.1 基本假設(shè)

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

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

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

    (3)節(jié)點(diǎn)間存在虛擬力(引力和斥力),，在力的作用下,，節(jié)點(diǎn)可相對(duì)運(yùn)動(dòng)。

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

2.2 問題描述

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

    假定有三維水下目標(biāo)區(qū)域R,，傳感器節(jié)點(diǎn)集合S={s₁，s₂,，s₃…s_n},，傳感器節(jié)點(diǎn)數(shù)目為n，傳感器節(jié)點(diǎn)感知半徑為r_s,。

    如果對(duì)于則目標(biāo)區(qū)域R被節(jié)點(diǎn)集合S完全覆蓋,。

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

2.3 基本思想

2.3.1 網(wǎng)格劃分

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

2.3.2 虛擬力算法

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

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

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

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

2.3.3 節(jié)點(diǎn)下降深度計(jì)算

    由上文可知,，水下傳感器網(wǎng)絡(luò)采用體心立方格形式進(jìn)行部署,，所以網(wǎng)格中的節(jié)點(diǎn)分為兩種，一種是部署在體心立方格的頂點(diǎn),，一種則部署在體心立方格的中心,。網(wǎng)格編號(hào)采用(i，j)形式,，即(1,，1)表示第一行第一個(gè)網(wǎng)格，(1,，2)表示第一行第二個(gè)網(wǎng)格,，以此類推,，(i，j)表示第i行第j個(gè)網(wǎng)格,。根據(jù)網(wǎng)格編號(hào),，將網(wǎng)格進(jìn)行分類，分為兩類,，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ù)或奇數(shù),。B類(1,，2)，(1,，4),，(1,6)，…,，(2,，1)，(2,，3),，(2,，5)，…,，(3,，2)，(3,，4),，(3，6)…,，即i和j為一奇一偶,。

2.4 算法流程

    (1)目標(biāo)水域進(jìn)行網(wǎng)格劃分，網(wǎng)格邊長(zhǎng)設(shè)定為將所有網(wǎng)格進(jìn)行編號(hào),。

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

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

3 實(shí)驗(yàn)仿真

3.1 網(wǎng)絡(luò)權(quán)重的比較

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)

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

[2] Li Shiwei,，Wang Wenjing,，Zhang Juwei.An underwater sensor network deployment algorithm based on submarine depth[J].傳感技術(shù)學(xué)報(bào)，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] 夏娜，鄭語晨,，杜華爭(zhēng),，等.剛性驅(qū)動(dòng)水下傳感器節(jié)點(diǎn)自組織布置[J].計(jì)算機(jī)學(xué)報(bào)，2013,，36(3)：494-505.

[7] ALAM S M,，HAAS Z J.Coverage and connectivity in three-dimensional 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)絡(luò)移動(dòng)算法研究[J].計(jì)算機(jī)應(yīng)用研究,，2010，27(10)：3926-3931.

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

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

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

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