單志龍，胡 燕

(華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州 510631)

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

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

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

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

1 AHLoS-3C水下定位算法

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

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

圖1 AHLoS-3C定位算法

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

IR2H算法針對(duì)網(wǎng)絡(luò)中錨節(jié)點(diǎn)極其稀疏，未知節(jié)點(diǎn)無(wú)法得到足夠錨節(jié)點(diǎn)位置信息來(lái)實(shí)現(xiàn)定位的情況下，借助其他未知節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)信息，從而增加未知節(jié)點(diǎn)獲得的定位信息量，使得未知節(jié)點(diǎn)有可能依靠?jī)商男畔?lái)完成定位。

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

圖2 單圓環(huán)

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

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

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

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

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

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

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

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

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

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

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

2.3 IR2H算法流程圖

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

圖7 IR2H算法流程圖

3 仿真分析

3.1 水聲模塊介紹

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

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

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

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

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

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

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

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

由于錨節(jié)點(diǎn)之間間距的遠(yuǎn)近直接影響到未知節(jié)點(diǎn)是否可以被準(zhǔn)確定位，所以在進(jìn)行仿真時(shí)，我們將通過(guò)對(duì)錨節(jié)點(diǎn)間距遠(yuǎn)近情況的討論來(lái)分析兩種算法的性能。

3.2 錨節(jié)點(diǎn)間距較遠(yuǎn)

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

圖8 節(jié)點(diǎn)分布場(chǎng)景及AHLoS-3C算法(錨節(jié)點(diǎn)遠(yuǎn))

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

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

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

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

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

(1)有效定位率［16］

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

(2)平均定位誤差

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

圖12 有效定位

圖13 平均定位誤差

(3)定位耗時(shí)

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

圖14 定位耗時(shí)

4 結(jié)論

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

［1］王福豹，史龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)能量路由協(xié)議的仿真研究［J］.傳感技術(shù)學(xué)報(bào)，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浮標(biāo)系統(tǒng)仿真研究［J］.西北工業(yè)大學(xué)學(xué)報(bào)，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］梁玥，劉忠，夏清濤.水下聲學(xué)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法及自組織過(guò)程研究［J］.傳感技術(shù)學(xué)報(bào)，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.