單志龍，胡 燕

(華南師范大學計算機學院，廣州 510631)

水下無線傳感器網(wǎng)絡UWSN(Underwater Wireless Sensor Network)可用于海洋學數(shù)據(jù)收集、污染監(jiān)測、近海探測、災難防御以及協(xié)助海軍進行戰(zhàn)術跟蹤等領域。與其他水下探測工具相比，UWSN節(jié)點成本低，體積小，適合大范圍部署和長時間監(jiān)測，因此越來越受到國內外眾多研究機構和企業(yè)的關注［1］。

水下無線傳感器網(wǎng)絡與地面無線傳感器網(wǎng)絡TWSNs(Terrestrial Wireless Sensor Networks)存在一些相同的特征，如大量的節(jié)點和有限的能量等［2］。同時，UWSNs又有自己獨特的方面。首先，由于水的鹽堿度對無線電信號傳輸產(chǎn)生干擾，無線電通信的方式在水下不能很好地工作，之后有人提出聲波通信，但聲波信道通常有較大的傳播遲延、低帶寬和多徑效應嚴重［3］。其次，水下傳感器節(jié)點可能會受到水流或其他因素影響從而產(chǎn)生位置移動。因此，原本適用于TWSN中的定位協(xié)議并不能很好地應用于UWSN。

現(xiàn)有的UWSN定位技術主要有GPS智能浮標［4－5］、USP［6］、SLMP［7］、水下 APS 定位系統(tǒng)［8］、AHLoS-3C(Ad Hoc Localization System)［9－10］定位系統(tǒng)等幾種方案。文獻［11］利用節(jié)點自組織過程中用到的數(shù)據(jù)傳輸算法，也提出了一種分布式的水下節(jié)點自定位算法。在這些方案中，有的是依賴于節(jié)點的密度，有的依賴于GPS或特殊節(jié)點等，相應就存在了傳感器節(jié)點定位代價大和精度低等問題。

本文針對UWSN中傳統(tǒng)定位協(xié)議的定位效率受限于節(jié)點密度的問題，提出了一種適用于節(jié)點稀疏(未知節(jié)點鄰居節(jié)點數(shù)小于3)網(wǎng)絡下的基于相交環(huán)的兩跳定位算法IR2H(Intersect Rings 2-Hops location scheme)，并通過實驗仿真驗證了算法的性能。

1 AHLoS-3C水下定位算法

經(jīng)典的三圓相交定位(AHLoS-3C)算法［12］思想是在對未知節(jié)點進行定位時，利用速度和已知節(jié)點與未知節(jié)點數(shù)據(jù)包傳輸時間分別求得節(jié)點間距離。如圖1所示，若未知節(jié)點D收到三個已知節(jié)點A1、A2和A3發(fā)出的定位信息數(shù)據(jù)包，則D的坐標可以通過三邊定位法求得。當D求得自身坐標后，成為已知節(jié)點并將自身坐標信息廣播出去，其它未知節(jié)點若能收到至少三個已知節(jié)點的定位信息，則可以使用同樣的方法計算自身坐標，全網(wǎng)通過遞歸方式實現(xiàn)對未知節(jié)點的自定位。

利用AHLoS-3C定位算法進行水下節(jié)點的定位過程較簡單且易于實現(xiàn)，定位算法收斂速度較快，適用于移動節(jié)點網(wǎng)絡，但在錨節(jié)點稀疏情況下，即未知節(jié)點周邊沒有三個以上的錨節(jié)點時，未知節(jié)點則無法獲得定位信息。

圖1 AHLoS-3C定位算法

2 基于相交環(huán)的兩跳定位算法

IR2H算法針對網(wǎng)絡中錨節(jié)點極其稀疏，未知節(jié)點無法得到足夠錨節(jié)點位置信息來實現(xiàn)定位的情況下，借助其他未知節(jié)點來轉發(fā)信息，從而增加未知節(jié)點獲得的定位信息量，使得未知節(jié)點有可能依靠兩跳的信息來完成定位。

2.1 單環(huán)的定義和同心環(huán)裁剪

圖2 單圓環(huán)

如圖2所示，節(jié)點A為錨節(jié)點，B和C均為未知節(jié)點，且C在A的通信半徑之外。假設水聲速度為v0。A發(fā)出的定位信息經(jīng)B轉發(fā)到達C，則C可獲得信息＜xA，yA，dAB，tB＞，其中xA和yA是A的坐標，dAB表示A與B的距離，tB表示B發(fā)出該數(shù)據(jù)包的時刻，則節(jié)點C在tC時刻接收到數(shù)據(jù)包時，節(jié)點B和C之間的距離dBC=v0·(tC－tB)。由于B可能出現(xiàn)在以A為圓心、dAB為半徑的圓周上的任意一點，C可能出現(xiàn)在以B為圓心、dBC為半徑的圓周上的任意一點，因此C可能出現(xiàn)在圖2單圓環(huán)陰影部分中的任一位置上，其位置可由式(1)表示:

若節(jié)點C同時收到節(jié)點B和D的兩個信息:＜xA，yA，dAB，tB＞和＜xA，yA，dAD，tD＞，如圖 3，則節(jié)點C經(jīng)過同心環(huán)裁剪后，必處于兩環(huán)相交陰影區(qū)域內，其位置可由式(2)表示:

圖3 同心環(huán)裁剪

顯然，節(jié)點C的中繼節(jié)點越多，則環(huán)的厚度有可能越薄，這樣有利于縮小節(jié)點C的位置區(qū)域。設節(jié)點C收到節(jié)點A經(jīng)不同中繼節(jié)點轉發(fā)的兩跳定位信息集為IAC，則有＜xA，yA，dAi，ti＞∈IAC，其中i為任一中繼節(jié)點。取rA=max{dAi}，RA=min{dAi+diC}，則節(jié)點C處在以A為圓心的環(huán)形區(qū)域內:

2.2 相交環(huán)和節(jié)點定位

如圖4所示，若節(jié)點C收到兩個一跳距離錨節(jié)點A4和A3的定位信息，則其位置可能是C1或C2。若節(jié)點C此時又收到來自兩跳距離的錨節(jié)點A1、A2的定位信息，則利用同心環(huán)裁剪的方法可獲得節(jié)點C必處于兩環(huán)相交區(qū)域內，且C1點即為C的位置。

圖4 兩錨節(jié)點多環(huán)定位

若節(jié)點C只收到來自一跳距離的錨節(jié)點A3的定位信息，且收到兩跳距離錨節(jié)點A1和A2的定位信息，如圖5所示，C必處于弧P1P2的某處，取弧P1P2的中點作為C的位置，此時定位精度為|P1P2|/2。

圖5 單錨節(jié)點兩環(huán)定位

如圖6所示，若節(jié)點C一跳范圍內不存在任何錨節(jié)點，只能通過式(4)多環(huán)相交確定其大致的區(qū)域，然后未知節(jié)點的坐標由區(qū)域的質心獲得。

圖6 多環(huán)相交定位

2.3 IR2H算法流程圖

IR2H定位算法有效地解決了稀疏錨節(jié)點情況下AHLoS-3C的有效定位率低或者完全無法定位的問題，提高了定位率，其算法流程如圖7所示。

圖7 IR2H算法流程圖

3 仿真分析

3.1 水聲模塊介紹

本文采用NS2水聲協(xié)議模塊模擬水下環(huán)境，對IR2H算法和AHLoS-3C算法進行了仿真分析。該模塊可分為4個部分:水聲傳輸模型、水聲信道模型、物理層模型和調制解調模型。水聲傳輸過程因受環(huán)境影響產(chǎn)生的總衰減A(d，f)等于擴展損耗與吸收損耗之和［12］:

其中d為傳輸距離，a為吸收系數(shù)，k為衰減系數(shù)，一般取1到2，a(f)［13］是根據(jù) Thorp近似計算得到的吸收損耗，單位為dB/km:

水下環(huán)境噪聲N(f)主要包括湍流噪聲、航船噪聲、風成噪聲和熱噪聲［14］，接收節(jié)點處的信噪比為:

其中Pt為發(fā)送功率，則接收功率為:

一般情況下水聲速度假設為恒定值v0=1 500 m/s，若考慮聲波水下傳輸過程受深度、溫度和鹽度等環(huán)境因素的影響，水聲速度可以近似計算為［12］:

其中t為水體溫度，z為水深，S為水的鹽度。

水聲傳輸模型使用式(5)計算傳輸過程總衰減，用式(7)計算接收節(jié)點處的信噪比SNR，在此基礎上用式(8)計算接收信號強度。水聲信道模型調用傳輸模型進行沖突檢測和傳輸錯誤發(fā)現(xiàn)，并計算有效帶寬。物理層調用傳輸模型和信道模型，并利用式(9)計算傳輸時間和總延遲，并調用調制解調模型計算誤碼率［15］。

如圖8所示，紅色十字標記表示節(jié)點實際位置，藍色實心圓標記表示錨節(jié)點。綠色標記表示節(jié)點通過定位算法計算獲得的位置，黑色線條表示節(jié)點實際位置與計算位置之間的偏差。節(jié)點的布置是隨機分布在大小為10 000 m×10 000 m場景區(qū)域中，總節(jié)點數(shù)為300，錨點數(shù)為4，節(jié)點通信半徑為1 650 m。

由于錨節(jié)點之間間距的遠近直接影響到未知節(jié)點是否可以被準確定位，所以在進行仿真時，我們將通過對錨節(jié)點間距遠近情況的討論來分析兩種算法的性能。

3.2 錨節(jié)點間距較遠

如圖8所示，當采用AHLoS-3C單跳定位算法時，因為錨節(jié)點之間距離大于節(jié)點的通信直徑，未知節(jié)點不能從至少3個相距較遠的錨節(jié)點獲取距離信息，因此將會出現(xiàn)未知節(jié)點無法定位的情況。而用IR2H算法對節(jié)點進行定位時，如圖9所示，由于使用了兩跳相交環(huán)輔助定位技術，因此可以有效解決在錨節(jié)點間距離大于節(jié)點的通信直徑情況下的定位問題，從而提高錨節(jié)點部署稀疏且相距較遠情況下的定位率。

圖8 節(jié)點分布場景及AHLoS-3C算法(錨節(jié)點遠)

圖9 IR2H定位算法(錨節(jié)點距離遠)

3.3 錨節(jié)點間距較近

圖10和圖11展示了錨節(jié)點間距離較近情況下，在用兩種定位算法進行一次定位估計時的直觀定位效果。圖10采用AHLoS-3C算法，被定位節(jié)點數(shù)274，其中被錯誤定位節(jié)點數(shù)為13，所有被錯誤定位節(jié)點的平均定位誤差為101.18 m。圖11采用IR2H算法，被定位節(jié)點數(shù)283，其中被錯誤定位節(jié)點數(shù)為6，所有被錯誤定位節(jié)點的平均定位誤差為43.44 m。從兩個圖中可以看出，在節(jié)點覆蓋區(qū)域的邊緣，使用AHLoS-3C算法時，有不少節(jié)點的真實位置和實際位置之間存在較大差異，而使用IR2H算法時，這種差異下降比較明顯。為了更好地比較兩個算法，在仿真時，對仿真數(shù)據(jù)取50次運算后的均值來比較有效定位率、平均定位誤差和定位耗時上的差異。

圖10 AHLoS-3C算法(錨節(jié)點距離近)

圖11 IR2H算法(錨節(jié)點距離近)

(1)有效定位率［16］

有效定位率指的是全網(wǎng)已被正確定位節(jié)點數(shù)占總節(jié)點數(shù)的百分比。隨著節(jié)點總數(shù)的增加，兩種定位算法的有效定位率均有所提高，IR2H的有效定位率最終穩(wěn)定在80%左右，而AHLoS-3C的有效定位率穩(wěn)定為75%，如圖12所示，可見IR2H比AHLoS-3C在大范圍定位過程中能保持較高的有效定位率。

(2)平均定位誤差

平均定位誤差指的是已定位節(jié)點的位置與實際位置的平均誤差。從圖13可知，總體上兩種定位算法的定位誤差隨著節(jié)點數(shù)量的增加逐漸減少，但由于節(jié)點位置坐標是隨機生成的，因此有可能增加定位算法的不穩(wěn)定性，即少部分節(jié)點可能產(chǎn)生較大的定位誤差，圖像的波動情況也正說明了這個現(xiàn)象。IR2H采用兩跳定位方法，有助于抑制定位誤差的積累和傳遞，因此總體定位誤差優(yōu)于AHLoS-3C。

圖12 有效定位

圖13 平均定位誤差

(3)定位耗時

定位耗時指的是完成一次全網(wǎng)定位所用時間。由圖14可知，兩種算法的完成一次全網(wǎng)定位所需時間比較相近，隨著節(jié)點數(shù)的增加，兩種算法的耗時都明顯有增大趨勢，且IR2H相對耗時稍大一點。一方面是由于隨著節(jié)點數(shù)的增加，爭用信道造成某些節(jié)點處于等待狀態(tài)增加耗時，另一方面是因為節(jié)點密度增加，增加了定位率，從而加大了計算量，造成總耗時增大。

圖14 定位耗時

4 結論

為了降低網(wǎng)絡定位代價，減少水下網(wǎng)絡節(jié)點定位對錨節(jié)點數(shù)的依賴性，本文提出了一種能夠在錨節(jié)點數(shù)稀疏的情況下實現(xiàn)節(jié)點自定位的新算法IR2H，該算法利用同心環(huán)的裁剪來縮小未知節(jié)點的定位區(qū)域，并通過兩跳來定位節(jié)點。仿真實驗表明，較AHLoS-3C算法，IR2H算法能夠提高了定位精度、降低了網(wǎng)絡代價和提高了節(jié)點定位率。在此過程中，相應地付出了時延增多的代價。

［1］王福豹，史龍，任豐原.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法［J］.軟件學報，2005，16(5):857－868.

［2］John Heidemann，Wei Ye，Jack Wills，et al.Research Challenges and Applications for Underwater Sensor Networking［C］//Proc.of the IEEE Wireless Communications and Networking(WCNC)，Las Vegas，2006:228－235.

［3］劉玉梁，潘仲明.水下無線傳感器網(wǎng)絡能量路由協(xié)議的仿真研究［J］.傳感技術學報，2011，24(6):905－908.

［4］SavvidesA，Han CC，Srivastava Mb.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors［C］//ACM MOBICOM，2001:166－179.

［5］杜曉旭，宋保維，胡海豹，等.AUV拖曳GPS浮標系統(tǒng)仿真研究［J］.西北工業(yè)大學學報，2008，26(1):88－92.

［6］Xie P，Lao L，Cui J H.VBF:Vector-Based Forwarding Protocol for Underwater Sensor Networks［J］.Lecture Notes in Computer Science，2006，3976:1216－1221.

［7］Zhou Z，Jun-Hong C，Amvrossios B.Scalable Localization with Mobility Prediction for Underwater Sensor Networks［C］//IEEE Infocom，2008:2198－2206.

［8］Dragos，Niculescu，Badri Nath.Ad Hoc Positioning System(APS)Using AOA［C］//IEEE Infocom，2003:1734－1743.

［9］Cheng X，Thaeler A，Xue G，et al.TPS:A Time-Based Positioning Scheme for Outdoor Wireless Sensor Networks［C］//IEEE Infocom，2004:2685－2696.

［10］Savvides A，Han C C，Srivastava M B.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors［C］//ACM Mobicom，2001:16－21.

［11］梁玥，劉忠，夏清濤.水下聲學傳感器網(wǎng)絡節(jié)點定位算法及自組織過程研究［J］.傳感技術學報，2011，24(3):402－406.

［12］Urick R.PrinciplesofUnderwaterSound［M］.McGraw-Hill，1983.

［13］Berkhovskikh L，Lysanov Y.Fundamentals of Ocean Acoustics［M］.New York:Springer，3rd Edition，2002.

［14］Coates R.Underwater Acoustic Systems［M］.Wiley，1989.

［15］Harris A F，Zorzi M.Modeling the Underwater Acoustic Channel in Ns2［C］//Proc.of the 2nd International Conference on Performance Evaluation Methodologies and Tools(NSTools’07)，Nantes，F(xiàn)rance，2007.

［16］Zhong Zhou，Jun-Hong Cui，Amvrossios Bagtzoglou.Scalable Localization with Mobility Prediction for Underwater Sensor Networks［C］//IEEE Infocom，2008:2198－2206.