0 引言

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

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

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

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

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

1 背景知識

1.1 三維感知模型

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

1.2 覆蓋效率

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

其中A_i為節點S_i的覆蓋范圍。

1.3 三維最優填充

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

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

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

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

2 算法描述

2.1 基本假設

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

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

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

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

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

2.2 問題描述

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

    假定有三維水下目標區域R，傳感器節點集合S={s₁，s₂，s₃…s_n}，傳感器節點數目為n，傳感器節點感知半徑為r_s。

    如果對于則目標區域R被節點集合S完全覆蓋。

    所以，問題可描述為：設計水下傳感器網絡部署策略，使得實現目標水域完全覆蓋所用的傳感器節點數n最少。

2.3 基本思想

2.3.1 網格劃分

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

2.3.2 虛擬力算法

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

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

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

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

2.3.3 節點下降深度計算

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

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

2.4 算法流程

    (1)目標水域進行網格劃分，網格邊長設定為將所有網格進行編號。

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

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

3 實驗仿真

3.1 網絡權重的比較

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

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

3.2 網絡覆蓋效率的比較

    部署節點數目由120到240（每隔20取一次）。每次部署運行10次仿真，取均值。圖9顯示了隨著節點數目的遞增，隨機部署策略和本文部署策略的網絡覆蓋效率變化對比情況。可知在本文的部署策略下，網絡的覆蓋效率明顯高于隨機部署，在節點數目在200以上時基本實現全覆蓋，而隨機部署240個節點時，覆蓋效率也僅達到90%，由此可見，本文策略實現了使用較少的節點達到更高的網絡覆蓋效率。

4 結論

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

參考文獻

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

[2] Li Shiwei，Wang Wenjing，Zhang Juwei.An underwater sensor 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] 夏娜，鄭語晨，杜華爭，等.剛性驅動水下傳感器節點自組織布置[J].計算機學報，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] 曾斌，鐘德歡，姚路.考慮水流影響的水下傳感器網絡移動算法研究[J].計算機應用研究，2010，27(10)：3926-3931.

[10] 王長生.水下傳感器網絡節點布置方法研究[D].合肥：合肥工業大學，2011.

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

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

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