一種小規模水下無線傳感器網絡的部署算法

羅 強，潘仲明

(國防科技大學機電工程與自動化學院，長沙 410073)

在水下無線傳感器網絡的研究中，一項很重要的工作是傳感器節點的部署與覆蓋問題，即如何利用有限的傳感器節點部署在整個監測區域，以獲得由這些節點構成的傳感器網絡的最大覆蓋性［1］。

節點部署方案的優劣直接影響到傳感器網絡的覆蓋性及其使用壽命。結合水下無線傳感器網絡的應用特點，在節點部署時應考慮如下三方面的問題［2］。第一，覆蓋問題:傳感器節點對目標區域的覆蓋面積(即這些節點能夠感知目標的區域);第二，連接問題:節點間的連接狀態能否保證感知信息準確地傳遞到基站;第三，節能問題:水下無線傳感器節點通常采用電池供電，在這種情況下，如何節省傳感器節點的能耗就顯得尤為重要。

根據應用環境的不同，節點部署的方式主要分為三類:受控部署、隨機部署和移動部署。在受控部署中，節點數量、密度、位置或鄰近關系需要精確計算和巧妙安排，以獲得最優的網絡特性［3］。最早的受控部署問題是圓覆蓋問題，文獻［4－5］證明了當以半徑相同的圓來覆蓋一個平面時，三角點陣的排列方式的節點數是(漸近)最少的。在文獻［6］中，Liu給出了基于無線信道通信功率與傳輸距離成2～4次冪的關系和數據轉發模型，討論了一維線形網絡的最小化發送功率和最大化網絡覆蓋的部署問題，并得到了節點間距的約束關系，研究結論表明離信息匯聚節點越近的區域，傳感器節點之間的距離越短。由于受控部署需要人工干預，因此，盡管傳感器網絡的覆蓋面積得到優化，但是其部署效率較低。隨機均勻部署效率高，但受偶然性因素的影響大，不能保證網絡的節點最少而覆蓋面積最大。而移動部署的自主移動性可以較好地解決上述兩種部署策略的不足［7］。Howard［8］和 Heo［9］將每個可移動的機器人視為一個移動的傳感器節點，提出了一種基于人工勢場的移動自主部署方法。Zou［10－11］提出了一種基于分簇結構的VFA算法，用于自主部署節點。Wang［12］考慮了全部由可移動節點組成的無線傳感器網絡的自組織重部署問題，為了實現網絡覆蓋面積的最大化，Wang提出了三種分布式算法:VEC算法、VOR算法和Minimax算法。

在陸地和空中的節點部署中，通常采用受控部署以達到最優的覆蓋性能，而在水下無線傳感器網絡的部署中，由于傳感器節點的位置會隨著海水的移動而發生變化，節點的位置是動態變化的，因此水下無線傳感器網絡的部署應當采用基于節點位置動態調整的自組織移動部署策略。

1 感知模型

為了解決節點的部署問題和傳感器網絡的覆蓋問題，必須建立節點的感知模型。節點的感知模型描述了節點的作用半徑和檢測能力，它是由傳感器的物理特性所決定的［3］。在水下無線傳感器網絡中，節點一般采用概率感知模型，即節點在不同區域對事件有不同的檢測概率。本文對Zou［10－11］提出的檢測概率模型增加了一個約束條件，解決了原模型中檢測概率曲線的不連續性的問題。

如果令d(s，p)表示節點s到任意位置p的距離，rs表示節點的感知半徑，re(re＜rs)表示傳感器節點不確定檢測能力的一個度量(見圖1)，則節點s檢測到任意點p發生事件的概率可表示為

式中，β是傳感器節點的性能參數;λ是滿足下式的某個常數，即

圖1給出了節點感知半徑rs與re的示意圖。當rs=10，re=5時，不同的β值對應著不同的檢測概率曲線，如圖2所示。

圖1 節點的感知半徑

圖2 節點的概率檢測模型

以上是僅僅考慮單個節點的檢測概率模型。當網絡中有多個節點［13］時，對p處發生的事件的檢測概率可表示為

式中，S為多個傳感器節點的集合。

為了簡化計算，不妨令re=0，則式(2)可改寫為

上式是二元模型，即檢測概率僅取1和0值。

2 基于虛擬力的水下部署

2.1 虛擬力模型

在虛擬力模型中，每個傳感器節點都對其它節點都作用了一個“虛擬力”，表現為引力或者斥力。如前所述，d(s，p)表示兩個節點之間的距離，dth表示兩個節點間既不受到引力也不受到斥力時的距離，稱為平衡距離。如果d(s，p)＜dth，則兩個節點之間的作用力為斥力;如果d(s，p)＞dth，則節點之間的作用力為引力，當d(s，p)?dth時，引力大小可以忽略不計。

在傳感器網絡中，節點除了受到其它節點的引力和斥力之外，還受到優先區域(即重點覆蓋區域)的引力和障礙區域(即節點感知無效的區域)的斥力。現在考慮網絡對節點Si的作用力:設節點Sj對節點Si的作用力為ij;障礙區域對節點的斥力為iB，所有優先區域對節點Si的引力為iT;記節點Si受到的作用力合力為i，那么，節點Si所受到的合力可表示為

式中，括號內第一項為受力的大小，第二項為受力的方向。dij是節點Si與節點Sj的歐氏距離，wA，wR分別為引力或斥力系數，aij表示節點Si與節點Sj連線與橫軸的夾角。

2.2 基于水下無線傳感器網絡的改進模型

(1)簡化算法:對于大規模網絡而言，如果考慮單個節點受到整個區域內節點的作用力i，則公式(6)中的節點受力分析將變得非常復雜。此外，隨著|dij－dth|持續增加時，節點移動帶來的能耗是呈線性增加的，同時通信的能耗是呈指數方式增加的。為此，本文引入虛擬力區域D的概念，只有在區域D內，才考慮節點的受力情況，從而簡化了算法。引入虛擬力區域的另一個好處是可以避免遠距離移動而帶來的巨大能耗。

(2)消除振蕩:在原模型中，引力與(dij－dth)呈正比，而斥力則與dij呈反比，當dij→dth時，節點受力的不連續，即

這將引起節點在平衡位置的受力出現震蕩，進而導致節點位置的不斷調整。為解決這一問題，可令引、斥力均與|dij－dth|成正比，這樣，當dij→dth時，節點所受到引、斥力均為0，從而消除了因節點受力不連續而引起的震蕩現象。

(3)節點的移動策略:在水下無線傳感器網絡中，節點的位置將隨著海水的波動而變化，因而必須采用動態調整節點位置的部署策略。此外，如果對節點的位置精度要求太高的話，則在節點部署時就需要反復調整節點的位置，進而增加節點的能耗。事實上，節點位置的精確性與網絡的覆蓋率并沒有直接的關系。因此，本文設置了一個閾值，當節點的受力大于該閾值時，才移動該節點。在此，引入精度因子μ和移動步長λ，并將乘積μrs定義為閾值。于是，當節點的受力大于μrs時，節點移動單位步長λ;而當節點的受力小于μrs時，則不移動節點。

在此基礎上，基于虛擬力提出快速虛擬力算法FVFA(fast virtual force algorithm)可表示為

式中，為從Si到Sj的單位矢量，D為虛擬力區域，是移動矢量。

一般取dth=2rs。當dij最終將收斂于dth時，就不會出現覆蓋區域的重疊現象(見圖3)，從而實現節點的覆蓋區域的最大化。然而，從圖3可以看出，采用這種部署策略，以rs為半徑的多個圓(覆蓋區域)的交界處將出現覆蓋真空［4］。解決該問題一個的辦法是增加移動節點，動態地填補覆蓋真空。當然，這需要增加傳感器網絡的額外開支。

圖3 dth=2r時的最大覆蓋

2.3 算法流程

步驟1設置目標區域x∈［0，a］，y∈［0，b］;a，b分別為目標區域的長和寬。在該區域內隨機布撒n個節點，(xk，yk)為節點i的坐標，k=1，2，…，n。

步驟2設t為部署次數——全部節點都移動一次;令最大部署次數為T;從t=1開始部署，當t=T時，強制終止計算。

步驟3分別計算先驗的優先覆蓋區域、障礙區域對第k個節點的作用力，即

式中，T、B分別為優先區域和障礙區域的幾何中心，為節點k到T處的單位矢量，為B處到節點k處的單位矢量，wT、wB分別為優先區域的引力系數和障礙區域的斥力系數。

步驟4設置虛擬力區域D，按下式計算各個節點對第k個節點的作用力

步驟5計算作用于第k個節點的合力

步驟6計算第k個節點的移動矢量:

令(xk，yk)?(xk，yk)+(xs，ys)，k=k+1，完成第k個節點的移動。如果k=n，轉到步驟7，否則，轉到步驟3。

步驟7令t=t+1。當t=T時，轉到步驟8，否則，轉到步驟3。

步驟8輸出節點部署結果。

3 仿真分析

在虛擬力算法中，最大部署次數T內的計算次數為n(n－1)。在FVFA算法中，最大部署次數T內的計算次數為n×m，m為在隨機部署在虛擬力區域D內的節點數，m＜n。由于節點在整個區域內服從均勻分布，則

式中，rD為虛擬力區域的半徑;a，b分別為目標區域的長和寬;符號E表示期望值計算。于是，FVFA算法的計算次數的期望和虛擬力算法的計算次數的比值為πrD2/(a×b)。由此可見，目標區域的面積(a×b)越大，FVFA算法的計算量越小。下文仿真時，令a=b=100，rD=2.5rs=25，此時 FVFA 算法的計算次數僅為虛擬力算法的計算次數的19.6%。

為了評價本算法(即FVFA算法)的性能，在此給出兩個評價指標:

覆蓋率:整個節點網絡的覆蓋面積與整個目標區域面積的比值。

覆蓋效率:(網絡的覆蓋面積)與(單個節點感知面積×節點總數)的比值。

假設在100 m×100 m的矩形區域內隨機分布n個傳感器節點，傳感器的作用半徑rs為10 m。圖4給出了傳感器網絡節點數為n=20的初始覆蓋。其中，細虛線區域為障礙區域，粗虛線區域為優先區域。在給定的條件下，理論上的最大覆蓋率可按下式計算:

式中，a，b分別為目標區域的長和寬。

圖4 初始覆蓋

如果隨機布署傳感器節點，必然存在大量節點的重復覆蓋。不難計算得到圖4的覆蓋率為0.44，大量節點沒有連通。圖5給出了基于FVFA算法的節點部署后的狀態，其覆蓋率達到了0.605，接近于理論上最大覆蓋率0.628(差值僅為0.023)。這表明，本文提出的基于FVFA算法的節點部署策略，是一種趨于最大覆蓋率的策略。

圖5 經過FVFA算法部署的覆蓋

圖6 不同規模下的覆蓋率隨時間的變化情況

下面考慮覆蓋效率問題。隨著部署次數t的增加，網絡的覆蓋效率也隨之增大，如圖7所示。從圖中可以看出，節點數n越大，覆蓋效率越低，且需要更多的部署次數才能使覆蓋效率趨于穩定的值。此外，隨著節點數的增加，不同規模的節點數的覆蓋效率的差異越來越大。這說明了基于FVFA算法的部署策略不適合用于部署大規模網絡。這個問題可以通過將多個節點組成節點簇的辦法［14］加以解決:每個節點簇覆蓋一個小區域，然后，將各個節點簇都視為一個大節點，這樣就可以按本文提出的算法部署傳感器網絡。

圖7 不同規模下的覆蓋效率隨時間的變化情況

4 結語

在虛擬力方法的基礎上，本文提出了基于FVFA算法的水下傳感器網絡節點的部署策略，并通過仿真驗證了算法的有效性。與其它虛擬力算法比較，在文中給定的區域和覆蓋率的條件下，FVFA算法的計算量減少了80.4%。

［1］郭忠文，羅漢江，洪鋒，等.水下無線傳感器網絡的研究進展［J］.計算機研究與進展.2010，47(3):377－389.

［2］劉麗萍，王智，孫優賢.無線傳感器網絡部署及其覆蓋問題研究［J］.電子與信息學報.2006，28(9):1752－1756.

［3］溫俊.能量高效的無線傳感器網絡覆蓋控制研究技術［D］:［博士學位論文］.長沙:國防科技大學，2009.

［4］Kershner R.The Number of Circles Covering a Set［J］.American Journal of Mathematics.1939，61:665－671.

［5］ZHANG H，HOU J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］.Ad-Hoc and Sensor Networks，2005，1(1):89－124.

［6］P Cheng，C Chuah，X Liu.Energy-Aware Node Placement in Wireless Sensor Networks［C］//IEEE Global Telecommunications Conference，Dallas，Texas，USA，2004.3210－3214.

［7］Benyuan L，Peter B，Olivier D.Mobility Improves Coverage of Sensor Networks［C］//Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，ACM Press，Urbana-Champaign，IL，USA，2005.300－308.

［8］Howard A，Mataric M J，Sukhatme G S.An Incremental Self-Deployment Algorithm for Mobile Sensor Networks［J］.Autonomous Robots，Special Issue on Intelligent Embedded Systems，2002，13(2):113－126.

［9］Heo N，Varshney P K.A Distributed Self Spreading Algorithm for Mobile Wireless Sensor Networks［C］//Proceedings of IEEE Wireless Communications and Networking Conference(WCNC’03)，Louisiana，USA，2003.1597－1602.

［10］Zou Yi，Chakrabarty K.Sensor Deployment and Target Localization Based on Virtual Forces［C］//Proc.of 2003 IEEE INFOCOM Conference.San Francisco，USA:［s.n.］，2003.1293－1303.

［11］Zou Y，Chakraharty K.Sensor Deployment and Target Localization in Distributed Sensor Networks［J］.ACM Trans on Embedded Computing Systems，2004，3(1):61－91.

［12］Wang G，Cao G，Porta T L.Movement-Assisted Sensor Deployment［C］//Proceedings of the 23rd conf of the IEEE computer and communications society，HongKong:［s.n.］，2004.640－652.

［13］蔣鵬，陳峰.基于概率的三維無線傳感器網絡K－覆蓋控制方法.傳感技術學報.2009，22(5):706－711.

［14］閻新芳，朱玉芳，安娜，等.無線傳感器網絡中一種分級簇的優化算法.傳感技術學報，2009，22(3):401－406.