羅 強(qiáng)，潘仲明

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

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

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

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

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

1 感知模型

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

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

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

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

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

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

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

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

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

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

2 基于虛擬力的水下部署

2.1 虛擬力模型

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

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

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

2.2 基于水下無線傳感器網(wǎng)絡(luò)的改進(jìn)模型

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

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

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

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

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

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

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

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

2.3 算法流程

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

步驟2設(shè)t為部署次數(shù)——全部節(jié)點(diǎn)都移動一次;令最大部署次數(shù)為T;從t=1開始部署，當(dāng)t=T時，強(qiáng)制終止計算。

步驟3分別計算先驗的優(yōu)先覆蓋區(qū)域、障礙區(qū)域?qū)Φ趉個節(jié)點(diǎn)的作用力，即

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

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

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

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

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

步驟7令t=t+1。當(dāng)t=T時，轉(zhuǎn)到步驟8，否則，轉(zhuǎn)到步驟3。

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

3 仿真分析

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

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

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

覆蓋率:整個節(jié)點(diǎn)網(wǎng)絡(luò)的覆蓋面積與整個目標(biāo)區(qū)域面積的比值。

覆蓋效率:(網(wǎng)絡(luò)的覆蓋面積)與(單個節(jié)點(diǎn)感知面積×節(jié)點(diǎn)總數(shù))的比值。

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

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

圖4 初始覆蓋

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

圖5 經(jīng)過FVFA算法部署的覆蓋

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

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

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

4 結(jié)語

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

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

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

［3］溫俊.能量高效的無線傳感器網(wǎng)絡(luò)覆蓋控制研究技術(shù)［D］:［博士學(xué)位論文］.長沙:國防科技大學(xué)，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］蔣鵬，陳峰.基于概率的三維無線傳感器網(wǎng)絡(luò)K－覆蓋控制方法.傳感技術(shù)學(xué)報.2009，22(5):706－711.

［14］閻新芳，朱玉芳，安娜，等.無線傳感器網(wǎng)絡(luò)中一種分級簇的優(yōu)化算法.傳感技術(shù)學(xué)報，2009，22(3):401－406.