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

羅 強，潘仲明

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

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

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

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

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

1 感知模型

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

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

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

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

圖1 節(jié)點的感知半徑

圖2 節(jié)點的概率檢測模型

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

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

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

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

2 基于虛擬力的水下部署

2.1 虛擬力模型

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法流程

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

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

步驟3分別計算先驗的優(yōu)先覆蓋區(qū)域、障礙區(qū)域對第k個節(jié)點的作用力，即

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

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

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

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

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

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

步驟8輸出節(jié)點部署結果。

3 仿真分析

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

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

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

覆蓋率:整個節(jié)點網絡的覆蓋面積與整個目標區(qū)域面積的比值。

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

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

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

圖4 初始覆蓋

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

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

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

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

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

4 結語

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

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

［2］劉麗萍，王智，孫優(yōu)賢.無線傳感器網絡部署及其覆蓋問題研究［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］閻新芳，朱玉芳，安娜，等.無線傳感器網絡中一種分級簇的優(yōu)化算法.傳感技術學報，2009，22(3):401－406.