0 引言

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

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

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

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

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

1 背景知識

1.1 三維感知模型

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

1.2 覆蓋效率

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

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

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

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

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

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

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

2 算法描述

2.1 基本假設(shè)

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

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

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

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

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

2.2 問題描述

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

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

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

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

2.3 基本思想

2.3.1 網(wǎng)格劃分

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

2.3.2 虛擬力算法

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

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

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

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

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

    由上文可知，水下傳感器網(wǎng)絡(luò)采用體心立方格形式進(jìn)行部署，所以網(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)格進(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ù)。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)格邊長設(shè)定為將所有網(wǎng)格進(jìn)行編號。

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

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

3 實驗仿真

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

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

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

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

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

4 結(jié)論

    本文針對三維水下傳感器網(wǎng)絡(luò)的應(yīng)用要求，提出了一種基于網(wǎng)格劃分和虛擬力的網(wǎng)絡(luò)部署策略。該策略的特點是基于三維空間填充多面體問題，將三維水下傳感器網(wǎng)絡(luò)部署問題簡化為二維水平面預(yù)部署問題，套用成熟的二維傳感器網(wǎng)絡(luò)部署模型，引入傳統(tǒng)的二維傳感器網(wǎng)絡(luò)虛擬力算法，完成水平面?zhèn)鞲衅鞴?jié)點的預(yù)處理。通過控制水平面節(jié)點在垂直方向的移動，生成Voronoi分割單元為截角八面體的體心立方格水下監(jiān)視網(wǎng)絡(luò)。在實現(xiàn)網(wǎng)絡(luò)全覆蓋的同時，本文部署策略使用的節(jié)點數(shù)目更少，有效地減少了網(wǎng)絡(luò)的搭建成本。下一步工作將針對水下傳感器網(wǎng)絡(luò)受水流、水生物影響更易失效的特點，在如何引入移動節(jié)點，提高網(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é)報，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] 夏娜，鄭語晨，杜華爭，等.剛性驅(qū)動水下傳感器節(jié)點自組織布置[J].計算機學(xué)報，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ò)移動算法研究[J].計算機應(yīng)用研究，2010，27(10)：3926-3931.

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

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

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

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