水下无线传感器网络定位算法分析与研究

周启明

(湖南科技大学计算机科学与工程学院,湘潭 411201)

水下无线传感器网络定位算法分析与研究

周启明

(湖南科技大学计算机科学与工程学院,湘潭 411201)

位置对于水下无线传感器网络来说十分重要,但由于水下独特的环境和水下通信方式,使得原有的定位算法已不适应,为了研究水下无线传感器网络定位算法.分析了水下无线传感器网络的特点,介绍了已有的水下无线传感器网络定位算法和测距方法,提出新的算法应主要考虑在节能方式下的迅速定位.

水下无线传感器网络;定位;测距

0 前 言

近来无线传感器网络(Wireless Sensor Networks,WSNs)对很多应用提供强有力的技术支持,如监测、测量、监视与控制等.而应用无线传感器网络于水下环境(称之为水下传感器网络)已经引起广泛的兴趣.水下无线传感器网络(Underwater Wireless Sensor Networks,UWSNs)与地面无线传感器网络(Terrestrial Wireless Sensor Networks,TWSNs)有着相同的特征,如大量的节点和有限的能量等.UWSNs又有自己独特的方面,首先,由于水的盐碱度,无线电(radio)通信的方式在水下不能很好的工作,取而代之的是声波通信(acoustic).声波信道通常有较大的传播迟延、低带宽和高错误率.其次,水下传感器节点可能水流或其他因素移动.最后,应用环境为三维环境.因此,针对于TWSNs的协议并不适合于UWSNs,这需要对协议栈的每一层进行新的研究,并需要新的水下试验设施进行实验、测试并比较[1].定位对于 UWSNs来说十分重要,一方面,对于某些应用(如水中生物监测)来说,取得与位置相关的有用信息必须依赖于定位,另外在水下地理路由[13]中也要应用到位置信息.而目前相关研究相之甚少.

1 国内外研究现状分析

三维水下无线传感器网络中的节点由于水流等因素而经常移动,对这些移动节点的定位是非常必要的,这是因为一些应用如水下生物监测应用需要高精度的定位,而水下监视网络则需要确定大量节点的范围.三维水下环境、声波传播特征和节点的移动性给定位方案在精度或可伸缩性方面带来巨大的挑战.这是因为:①水下声波信道高分散性,TDoA测量受密集的多径(mutilpath)影响;②因为层化(stratifcation)影响,声波信号不按直线转播;③声波带宽非常低,依赖密集数据包交换的协议是无法实现的;④大范围大规模的节点部署无法用集中式的方式计算位置;⑤节点的移动使网络拓扑呈动态性.国内外学者对水下传感器网络定位的研究方兴未艾.

1.1 GPS智能浮标

GIB(GPS Intelligent Buoy,GIB)简称 GPS(Global Position System)智能浮标[2,18],是基于水面浮标的网络.每一个周期(通常为一秒),节点传送两种连续信号,一种用于GPS同步,另一种相应地由深度而延迟.每一个浮标分别测量两种信号的GPS到达时间,并通过RF信号把这些信息与自己的有差别的GPS位置传送给控制与显示单元.由于声波速度已知,传播时间直接转化为到浮标的距离.由于深度已知(由每一个浮标测得),节点的位置可以直接由三边测量法获得.

1.2 USP

在USP[13]方案中,深度信息对于水下节点来说是可知的,因此通过投影(project)技术可以把三维空间定位转化为平面定位.文章证明了非退化(non-degenerative)投影能够保持网络的定位能力,同时也证明对于给定的网络与常数k,所有几何上的k边测量定位方法是等效的.因此USP能够保留平面定位方法的能力并在已有的三维定位技术上得到提高.如图1所示,水下节点X要计算自己的水下三维位置,对于三个已知位置的参考节点 A(xA,yA,zA)、B(xB,yB,zB) 、C(xC,yC,zC),X 位于三个节点的通信半径之内,X的深度已经测得为zX.当成功接收来自三个参考节点的位置信息后,X使用一个投影函数把三个参考节点投影到自己所在的平面,得到三个位置分别为(xA,yA,zA),(xB,yB,zX),(xC,yC,zX).当且仅当没有两个节点的相同的x和y坐标时,投影函数是非退化的.当三个节点被投影后,任何类似三边测量的定位方案都可以定位X.

图1 USP的投影技术

1.3 SLMP

带移动预测的可扩展定位算法SLMP(Scalable Localization scheme with Mobility Prediction,SLMP)[9]利用水下物体可预测移动模型来实现移动节点的定位.在SLMP中,节点分为两种:锚节点与普通节点.在定位开始阶段,四个或四个以上的浮标知道自己的位置,锚节点有很强的能源,能直接测量与浮标的距离.普通节点采用递归定位方法[16],在普通节点定位过程中引入参考节点(reference node)概念,参考节点为知道自身位置的节点,随着定位过程的深入,越来越多的普通节点变成参考节点,则每一个普通节点都可以定位.在定位过程中,每个节点可以根据自己过去的位置信息预测将来的移动模型,并根据此模型估计自己将来的位置.

1.4 水下APS定位系统

水下APS定位系统[15,16]是指把APS(AD Hoc Position System)[5]定位系统应用到水下环境中.在文献[16]中,节点分为水面节点、锚节点与普通节点,水面节点通过某些方式能够知道自己的位置,而锚节点能够与水面直接通信从而知道自己的绝对位置,锚节点能够与普通节点通信并帮助它们定位.文章通过把欧几里德(Euclidean)距离传播方法[8]从2维平面扩展到3D空间,使节点可以获知到锚节点的距离.如图2中,普通节点E要估计自己到锚节点A的距离,它必须知道至少三个已经估计到A距离的相邻节点(如B、C、D).其中节点 A、B、C和D不能共面且A、B、C、D和E其中任意三个不能共线.而且,E必须知道其两跳(two-hop)距离估计,即 E 必须知道 EB 、BA、EC、CA、ED、D A、DB、DC和BC的长度信息.其工作过程如下:首先,节点E用边BA、CA、BC构建基本定位平面.由于E已知DB、DA和DC的边长,因此节点D的位置很容易估计.D的位置有两种可能.E已知ED、EB和EC的边长,相对于D的两个可能的位置,E的可能位置有四个.当拥有相邻节点到A的距离估计时,E可以通过本地投票方式有四个可能的位置中进行选择.如E不能决定其自身位置,则到A的距离估计是不可用的,E必须从相邻节点获得更多信息.

图2 三维欧几里德估计

2 测距方法

在与距离无关的平面定位算法[22,23]中,节点主要依靠节点之间的数据包交换来获得到已知位置节点(通常称之为信标节点)的距离,因UWSNs的环境特征,这种方法不适应UWSNs.在与距离相关的平面定位算法中,主要考虑是如何测量节点与节点之间的实际距离,在测距的方法中有TOA、TDOA、AOA 、RSSI等.

(1)TOA:信号从一个节点传播到另一个节点所需的时间,称为信号到达时间(time of arrival,TOA),GPS是应用此项技术的典型,但由于设备比较昂贵,并不适合节点数目众多的WSNs.

(2)TDOA:两种不同速度的信号从一个节点传播到另一个节点所需的时间差,称为信号的到达时间差(time difference of arrival,TDOA),此项技术一般在节点上安装超声波和RF收发器.测距时节点同时发送两种信号,利用声波与电磁波在大气中传播速度的差异,接收节点记录两种信号的先后到达时间,由于两种信号的速度已知,可直接把时间转换成距离.已有很多定位算法[7～10]使用此测距方法.此方法要求节点之间有严格的时间同步,另外受超声波传播距离与非视线关系(NLOS)的影响,且需要大量的计算与通信开销,因此对于资源有限的WSNs来说是不太适应的.

(3)AOA:节点收到的信号相对于自身轴线的角度,称为信号相对接收节点的到达角度(angle of arrival,AOA),是一种估算邻居节点发送方向的技术.此项技术要求节点装配特殊硬件(方向天线),增加了节点的成本与功耗开销.

(4)RSSI:节点接收到无线信号的强度大小,称为接收信号强度指示(receive signal strength indicator),在发射功率已知的情况下,接收节点测量接收功率,计算传播耗损,使用理论或经验信号传播模型将传播损耗转换为距离.信号主要使用RF信号,受环境等诸多因素的影响,但因其简单,是定位技术中常用的测距方法.

对于测距方法来说,到达时间差(Time-Difference-of-Arrival,TDOA)测距是利用声波测距的主要方法,它要求有严格的时间同步.TPS[16]、iTPS[17]、T TPS[15]三种方法都利用 TDOA测距并其进行改进,所以不需要时钟同步和特殊硬件且节点之间不存在通信开销,但它们都需要多个信标节点且只能在平面上使用.

3 总 结

现有的方案中有的依赖于节点的密度[7-10],有的依赖于GPS或特殊节点等[5][6][11].多数方案依赖节点之间相互通信来测距,大大增加了通信量,这对于以声波通信为主的UWSNs是不合适的.已知的测距方法如TOA、TDoA和RSSI都不适合水下环境,TDOA中依靠两种信号的不同传播速度来获得距离,但因为水下环境使得不能使用RF信号,且TDOA依赖时间同步.对于水下节点最为有力的测距方式是AOA,因为使用声波通信而使得每一个节点都装配了声波天线.测距方法主要研究内容是三维水下传感器网络中不依赖于时间同步的 TDOA方法和三维环境下的AOA方法.

三维水下传感器网络定位算法.已有的研究成果中定位算法集中在平面定位,在三维环境下定位则必须对原来的算法改进或研究新的算法,另外由于水下独特的环境,节点必须很快更新其位置,算法的运行周期要快,因此必须对三维水下传感器网络定位算法进行研究.其研究内容是如何在节能方式下对整个网络进行迅速的定位.考虑到水下节点接收数据消耗的能量远小于发送数据消耗的能量,新的算法研究的内容则应该尽量减少普通节点发送数据的次数,从成本的角度出发新的算法应该尽可能减少锚节点的数目.

[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]周 伟,来鸿飞,刘 忠.水下无线传感器网络的节点精确定位[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-),男,硕士,工程师,研究方向:信息安全、无线网络.