水下無線傳感器網(wǎng)絡定位算法分析與研究

周啟明

(湖南科技大學計算機科學與工程學院,湘潭 411201)

水下無線傳感器網(wǎng)絡定位算法分析與研究

周啟明

(湖南科技大學計算機科學與工程學院,湘潭 411201)

位置對于水下無線傳感器網(wǎng)絡來說十分重要,但由于水下獨特的環(huán)境和水下通信方式,使得原有的定位算法已不適應,為了研究水下無線傳感器網(wǎng)絡定位算法.分析了水下無線傳感器網(wǎng)絡的特點,介紹了已有的水下無線傳感器網(wǎng)絡定位算法和測距方法,提出新的算法應主要考慮在節(jié)能方式下的迅速定位.

水下無線傳感器網(wǎng)絡;定位;測距

0 前 言

近來無線傳感器網(wǎng)絡(Wireless Sensor Networks,WSNs)對很多應用提供強有力的技術(shù)支持,如監(jiān)測、測量、監(jiān)視與控制等.而應用無線傳感器網(wǎng)絡于水下環(huán)境(稱之為水下傳感器網(wǎng)絡)已經(jīng)引起廣泛的興趣.水下無線傳感器網(wǎng)絡(Underwater Wireless Sensor Networks,UWSNs)與地面無線傳感器網(wǎng)絡(Terrestrial Wireless Sensor Networks,TWSNs)有著相同的特征,如大量的節(jié)點和有限的能量等.UWSNs又有自己獨特的方面,首先,由于水的鹽堿度,無線電(radio)通信的方式在水下不能很好的工作,取而代之的是聲波通信(acoustic).聲波信道通常有較大的傳播遲延、低帶寬和高錯誤率.其次,水下傳感器節(jié)點可能水流或其他因素移動.最后,應用環(huán)境為三維環(huán)境.因此,針對于TWSNs的協(xié)議并不適合于UWSNs,這需要對協(xié)議棧的每一層進行新的研究,并需要新的水下試驗設施進行實驗、測試并比較[1].定位對于 UWSNs來說十分重要,一方面,對于某些應用(如水中生物監(jiān)測)來說,取得與位置相關的有用信息必須依賴于定位,另外在水下地理路由[13]中也要應用到位置信息.而目前相關研究相之甚少.

1 國內(nèi)外研究現(xiàn)狀分析

三維水下無線傳感器網(wǎng)絡中的節(jié)點由于水流等因素而經(jīng)常移動,對這些移動節(jié)點的定位是非常必要的,這是因為一些應用如水下生物監(jiān)測應用需要高精度的定位,而水下監(jiān)視網(wǎng)絡則需要確定大量節(jié)點的范圍.三維水下環(huán)境、聲波傳播特征和節(jié)點的移動性給定位方案在精度或可伸縮性方面帶來巨大的挑戰(zhàn).這是因為:①水下聲波信道高分散性,TDoA測量受密集的多徑(mutilpath)影響;②因為層化(stratifcation)影響,聲波信號不按直線轉(zhuǎn)播;③聲波帶寬非常低,依賴密集數(shù)據(jù)包交換的協(xié)議是無法實現(xiàn)的;④大范圍大規(guī)模的節(jié)點部署無法用集中式的方式計算位置;⑤節(jié)點的移動使網(wǎng)絡拓撲呈動態(tài)性.國內(nèi)外學者對水下傳感器網(wǎng)絡定位的研究方興未艾.

1.1 GPS智能浮標

GIB(GPS Intelligent Buoy,GIB)簡稱 GPS(Global Position System)智能浮標[2,18],是基于水面浮標的網(wǎng)絡.每一個周期(通常為一秒),節(jié)點傳送兩種連續(xù)信號,一種用于GPS同步,另一種相應地由深度而延遲.每一個浮標分別測量兩種信號的GPS到達時間,并通過RF信號把這些信息與自己的有差別的GPS位置傳送給控制與顯示單元.由于聲波速度已知,傳播時間直接轉(zhuǎn)化為到浮標的距離.由于深度已知(由每一個浮標測得),節(jié)點的位置可以直接由三邊測量法獲得.

1.2 USP

在USP[13]方案中,深度信息對于水下節(jié)點來說是可知的,因此通過投影(project)技術(shù)可以把三維空間定位轉(zhuǎn)化為平面定位.文章證明了非退化(non-degenerative)投影能夠保持網(wǎng)絡的定位能力,同時也證明對于給定的網(wǎng)絡與常數(shù)k,所有幾何上的k邊測量定位方法是等效的.因此USP能夠保留平面定位方法的能力并在已有的三維定位技術(shù)上得到提高.如圖1所示,水下節(jié)點X要計算自己的水下三維位置,對于三個已知位置的參考節(jié)點 A(xA,yA,zA)、B(xB,yB,zB) 、C(xC,yC,zC),X 位于三個節(jié)點的通信半徑之內(nèi),X的深度已經(jīng)測得為zX.當成功接收來自三個參考節(jié)點的位置信息后,X使用一個投影函數(shù)把三個參考節(jié)點投影到自己所在的平面,得到三個位置分別為(xA,yA,zA),(xB,yB,zX),(xC,yC,zX).當且僅當沒有兩個節(jié)點的相同的x和y坐標時,投影函數(shù)是非退化的.當三個節(jié)點被投影后,任何類似三邊測量的定位方案都可以定位X.

圖1 USP的投影技術(shù)

1.3 SLMP

帶移動預測的可擴展定位算法SLMP(Scalable Localization scheme with Mobility Prediction,SLMP)[9]利用水下物體可預測移動模型來實現(xiàn)移動節(jié)點的定位.在SLMP中,節(jié)點分為兩種:錨節(jié)點與普通節(jié)點.在定位開始階段,四個或四個以上的浮標知道自己的位置,錨節(jié)點有很強的能源,能直接測量與浮標的距離.普通節(jié)點采用遞歸定位方法[16],在普通節(jié)點定位過程中引入?yún)⒖脊?jié)點(reference node)概念,參考節(jié)點為知道自身位置的節(jié)點,隨著定位過程的深入,越來越多的普通節(jié)點變成參考節(jié)點,則每一個普通節(jié)點都可以定位.在定位過程中,每個節(jié)點可以根據(jù)自己過去的位置信息預測將來的移動模型,并根據(jù)此模型估計自己將來的位置.

1.4 水下APS定位系統(tǒng)

水下APS定位系統(tǒng)[15,16]是指把APS(AD Hoc Position System)[5]定位系統(tǒng)應用到水下環(huán)境中.在文獻[16]中,節(jié)點分為水面節(jié)點、錨節(jié)點與普通節(jié)點,水面節(jié)點通過某些方式能夠知道自己的位置,而錨節(jié)點能夠與水面直接通信從而知道自己的絕對位置,錨節(jié)點能夠與普通節(jié)點通信并幫助它們定位.文章通過把歐幾里德(Euclidean)距離傳播方法[8]從2維平面擴展到3D空間,使節(jié)點可以獲知到錨節(jié)點的距離.如圖2中,普通節(jié)點E要估計自己到錨節(jié)點A的距離,它必須知道至少三個已經(jīng)估計到A距離的相鄰節(jié)點(如B、C、D).其中節(jié)點 A、B、C和D不能共面且A、B、C、D和E其中任意三個不能共線.而且,E必須知道其兩跳(two-hop)距離估計,即 E 必須知道 EB 、BA、EC、CA、ED、D A、DB、DC和BC的長度信息.其工作過程如下:首先,節(jié)點E用邊BA、CA、BC構(gòu)建基本定位平面.由于E已知DB、DA和DC的邊長,因此節(jié)點D的位置很容易估計.D的位置有兩種可能.E已知ED、EB和EC的邊長,相對于D的兩個可能的位置,E的可能位置有四個.當擁有相鄰節(jié)點到A的距離估計時,E可以通過本地投票方式有四個可能的位置中進行選擇.如E不能決定其自身位置,則到A的距離估計是不可用的,E必須從相鄰節(jié)點獲得更多信息.

圖2 三維歐幾里德估計

2 測距方法

在與距離無關的平面定位算法[22,23]中,節(jié)點主要依靠節(jié)點之間的數(shù)據(jù)包交換來獲得到已知位置節(jié)點(通常稱之為信標節(jié)點)的距離,因UWSNs的環(huán)境特征,這種方法不適應UWSNs.在與距離相關的平面定位算法中,主要考慮是如何測量節(jié)點與節(jié)點之間的實際距離,在測距的方法中有TOA、TDOA、AOA 、RSSI等.

(1)TOA:信號從一個節(jié)點傳播到另一個節(jié)點所需的時間,稱為信號到達時間(time of arrival,TOA),GPS是應用此項技術(shù)的典型,但由于設備比較昂貴,并不適合節(jié)點數(shù)目眾多的WSNs.

(2)TDOA:兩種不同速度的信號從一個節(jié)點傳播到另一個節(jié)點所需的時間差,稱為信號的到達時間差(time difference of arrival,TDOA),此項技術(shù)一般在節(jié)點上安裝超聲波和RF收發(fā)器.測距時節(jié)點同時發(fā)送兩種信號,利用聲波與電磁波在大氣中傳播速度的差異,接收節(jié)點記錄兩種信號的先后到達時間,由于兩種信號的速度已知,可直接把時間轉(zhuǎn)換成距離.已有很多定位算法[7～10]使用此測距方法.此方法要求節(jié)點之間有嚴格的時間同步,另外受超聲波傳播距離與非視線關系(NLOS)的影響,且需要大量的計算與通信開銷,因此對于資源有限的WSNs來說是不太適應的.

(3)AOA:節(jié)點收到的信號相對于自身軸線的角度,稱為信號相對接收節(jié)點的到達角度(angle of arrival,AOA),是一種估算鄰居節(jié)點發(fā)送方向的技術(shù).此項技術(shù)要求節(jié)點裝配特殊硬件(方向天線),增加了節(jié)點的成本與功耗開銷.

(4)RSSI:節(jié)點接收到無線信號的強度大小,稱為接收信號強度指示(receive signal strength indicator),在發(fā)射功率已知的情況下,接收節(jié)點測量接收功率,計算傳播耗損,使用理論或經(jīng)驗信號傳播模型將傳播損耗轉(zhuǎn)換為距離.信號主要使用RF信號,受環(huán)境等諸多因素的影響,但因其簡單,是定位技術(shù)中常用的測距方法.

對于測距方法來說,到達時間差(Time-Difference-of-Arrival,TDOA)測距是利用聲波測距的主要方法,它要求有嚴格的時間同步.TPS[16]、iTPS[17]、T TPS[15]三種方法都利用 TDOA測距并其進行改進,所以不需要時鐘同步和特殊硬件且節(jié)點之間不存在通信開銷,但它們都需要多個信標節(jié)點且只能在平面上使用.

3 總 結(jié)

現(xiàn)有的方案中有的依賴于節(jié)點的密度[7-10],有的依賴于GPS或特殊節(jié)點等[5][6][11].多數(shù)方案依賴節(jié)點之間相互通信來測距,大大增加了通信量,這對于以聲波通信為主的UWSNs是不合適的.已知的測距方法如TOA、TDoA和RSSI都不適合水下環(huán)境,TDOA中依靠兩種信號的不同傳播速度來獲得距離,但因為水下環(huán)境使得不能使用RF信號,且TDOA依賴時間同步.對于水下節(jié)點最為有力的測距方式是AOA,因為使用聲波通信而使得每一個節(jié)點都裝配了聲波天線.測距方法主要研究內(nèi)容是三維水下傳感器網(wǎng)絡中不依賴于時間同步的 TDOA方法和三維環(huán)境下的AOA方法.

三維水下傳感器網(wǎng)絡定位算法.已有的研究成果中定位算法集中在平面定位,在三維環(huán)境下定位則必須對原來的算法改進或研究新的算法,另外由于水下獨特的環(huán)境,節(jié)點必須很快更新其位置,算法的運行周期要快,因此必須對三維水下傳感器網(wǎng)絡定位算法進行研究.其研究內(nèi)容是如何在節(jié)能方式下對整個網(wǎng)絡進行迅速的定位.考慮到水下節(jié)點接收數(shù)據(jù)消耗的能量遠小于發(fā)送數(shù)據(jù)消耗的能量,新的算法研究的內(nèi)容則應該盡量減少普通節(jié)點發(fā)送數(shù)據(jù)的次數(shù),從成本的角度出發(fā)新的算法應該盡可能減少錨節(jié)點的數(shù)目.

[1]http://uwsn.engr.uconn.edu/overview.html.

[2]Bulusu N,Heidemann J,Estrin D.GPS-less Low Cost Outdoor Localization for Very Small Devices.IEEE Personal Communications Magazine,2000:28-34.

[3]He T,Huang C,Blum B M,Stankovic J A,Abdelzaher T.Range-free Localization Schemes for Large Scale Sensor Networks[C].In Proceedings of 9th Annual International Conference on Mobile Computing and Networking,2003:81-95.

[4]Wu H,Wang C,Tzeng N F.Novel self-con Gurable Positioning Technique for Multihop Wireless Networks[J].IEEE/ACM Transaction on Networking,2005:609-621.

[5]Austin T C,Stokey R P,Sharp K M.PARADIGM:A Buoy-based System for Auv Navigation and Tracking[C].In IEEE Proceedings of Oceans,2000.

[6]Bechaz C,Thomas H.GIB system:The Underwater gps Solution[C].In Proceedings of ECUA,May 2001.

[7]Garcia J E.Ad hoc Positioning for Sensors in Underwater Acoustic Networks[C].In IEEE Proceedings of O-ceans,2004.

[8]Zhang Y,Cheng L.A distributed Protocol for Multihop Underwater Robot Positioning[C].In IEEE Proceedings of International Conference on Robotics and Biomimetics,2004.

[9]Zhou Z,Jun-Hong C,Amvrossios B,Scalable Localization with Mobility Prediction for Underwater Sensor Networks[C].INFOCOM 2008.The 27th Conference on Computer Communications,IEEE2008:2198-2206.

[10]Wei C,Amin Y,Teymorian,Liran M,Xiuzhen C,Xicheng L,Zexin L, UnderwaterLocalization in Sparse 3D Acoustic Sensor Networks[C].INFOCOM 2008.The 27th Conference on Computer Communications.IEEE 2008,(13-18):236-240.

[11]Zhou Z,Cui J H,Zhou S.Localization for Large-scale Underwater Sensor Networks[R].In UCONN CSE Technical Report:UbiNet-T R06-04,2006.

[12]Akyildiz I F,Pompili D,Melodia T.Challenges for Efficient Communication in Underwater Acoustic Sensor Networks[J].SIGBED Rev.,2004,1(2).

[13]Xie P,Lao L,Cui J H.VBF:Vector-based Forwarding Protocol for Underwater Sensor Networks[C].In Proceedings of IFIP Networking,May 2006.

[14]Hahn M,Rice J,Undersea Navigation Via a Distributed Acoustic Communication Network.In Proceedings ofTurkish International Conferenceon Acoustics,2005.

[15]Liu F,Xiuzhen C,Dong H.TPSS:A Time-based Positioning Scheme for SensorNetworks with Short Range Beacons[J].Wireless Sensor Networks and Applications,ECTION II Network M anagement.Y.Li,M.Thai and W.Wu(Eds.),2005:276-304.

[16]Cheng X,Thaeler A,Xue G,Chen D,TPS:A Time-Based Positioning Scheme for Outdoor Wireless Sensor Networks[C].IEEE INFOCOM,2004.

[17]Thaeler A,Ding M,Cheng X.iTPS:An Improved Location Discovery Scheme for Sensor Networks with Long range Beacons[J].Journal of Parallel and Distributed Computing,Special Issue on Theoretical and Algorithmic Aspects of Sensor,Ad Hoc Wireless,and Peer-to-Peer Networks,2004.

[18]Savvides A,Han C C,Srivastava M b,Dynamic Fine-Grained Localization in Ad-hoc Networks of Sensors[J].ACM MOBICOM,2001:166-179.

[19]Lanbo L,Shengli Z,Jun-Hong C.Prospects and Problems of Wireless Communications for Underwater Sensor Networks[J].Accepted for Publication in Wiley Wireless Communications and Mobile Computing,Special Issue on Underwater Sensor Networks,2008,(5).

[20]Partan J,Kurose J,Levine B N.A Aurvey of Practical Issues in Underwater Networks.In WUWNet'06:Proceedings of the 1st ACM International Workshop on Underwater Networks,2006:17-24.

[21]周 偉,來鴻飛,劉 忠.水下無線傳感器網(wǎng)絡的節(jié)點精確定位[J].指揮控制與仿真,2007,29(1):50-53.

[22]Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Telecommunication Systems,2003,2(4):267-280.

[23]Niculescu D,Nath B.Ad Hoc Positioning system(APS)[R].Technical Report DCS-TR-435,Department of Computer Science,Rutgers University,2001.

Analysis and Research of Position Algorithms in Underwater Wireless Sensor Networks

ZHOU Qi-ming
(School of Computer Science and Engineering,Hunan University of Science&Technology,Xiangtan 411201,China)

Position is very important to underwater wireless sensor network,but due to the unique underwater circumstance and the underwater communication mode,the original position algorithms do not suit.In this paper,characteristics are analyzed.The existed position algorithm of underwater wireless sensor networks and the measure distance scheme are introduced,and the future work is proposed.

underwater wireless sensor network;position;measure distance

TP212;TP393

A

1671-119X(2011)02-0049-04

2011-01-17

湖南省教育廳科研資助項目(10C0692).

周啟明(1974-),男,碩士,工程師,研究方向:信息安全、無線網(wǎng)絡.