标题 | 无线传感器网络定位算法研究 |
范文 | 解皓++梁建国++程涛 摘 要:质心与DVHop定位算法节点可信度研究,对分析质心和DVHop混合定位算法有着重要的指导意义。提出了研究质心和DVHop定位节点可信度的算法,并用MATLAB进行了仿真实验。实验结果表明,在相同节点分布密度以及网络连通度的条件下,在锚节点数量少于20时,DVHop算法比质心算法节点可信度高,在锚节点数量大于20以后,质心算法将接近并超过DVHop算法的可信度。 关键词:可信度;概率分布;质心算法;DVHop算法 DOIDOI:10.11907/rjdk.151354 中图分类号:TP312 文献标识码:A 文章编号文章编号:16727800(2015)009008003 0 引言 在无线传感器网络(Wireless Sensor Network,WSN)研究中,节点定位一直是热点问题,因为节点定位对无线传感器网络的有效性起着至关重要的作用[ 1 ]。目前,无线传感器网络已经广泛应用于智能物流、智能交通、智能家居以及智能农业等场合,而在这些应用场合中,对信息来源的精准定位至关重要,否则获取的信息将失去意义。 目前,节点定位算法根据是否需要测量节点间的信息,划分为基于测距定位算法和无需测距定位算法[ 2 ]。基于测距技术定位算法定位精度高,但对硬件依赖性高,不适合低功耗、低成本的无线传感网应用领域。无需测距定位算法通过交换相邻节点间的信息确定未知节点的位置,其定位精度较低,但对硬件依赖性不高,并且能满足多数无线传感器网络的定位要求,因此对其研究和改进有着重要意义[ 3 ]。目前无需测距定位算法主要有质心算法、凸规划算法、DVHop算法和APIT 算法等[ 4 ]。本文在质心和DVHop算法的基础上,提出了检测质心和DVHop算法节点可信度特征的算法,并对该算法进行了仿真测试。 1 质心与DVHop算法 1.1 质心算法 质心定位算法由南加州大学Nirupama Bulusu 等学者提出,它是一种无需测距的室外定位算法[ 5 ]。质心定位算法的基本思想是在一定通信范围内,通过计算包围未知节点的锚节点构成的多边形质心来估计未知节点的位置。质心算法的伪代码如下: beginEach anchor node broadcasts its position. Each sensor node listens for beacons (Xi ,Yi) from anchors and computes a connectivity metric, for each anchor node Ai it has received beacons from. This metric is defined as follows: CMk,Ai=Nrecv(Ai,t)Nsent(Ai,t); /*在时间t内,Nrecv(Ai,t)为从锚节点处接收到的信标总数,Nsent(Ai,t)为锚节点Ai发送的信标数目。*/ if(CMk,Ai≥M) then /*M是门限*/ (X,Y)=∑ni=1Xin,∑ni=1Yin ;end 质心算法的优点就是简单、计算量小,缺点是要达到较高的精确度,需要较多的锚节点数量[ 6 ]。 1.2 DVHop算法 DVHop算法由美国Rutgers大学的Niculescu提出[ 7 ]。DVHop算法的核心思想分为3个阶段:①计算未知节点与锚节点之间的最小跳数;②估算平均每跳的距离;③使用跳段距离代替实际距离计算未知节点的定位坐标。DVHop算法流程如图1所示。 DVHop算法的特点是:在节点分布均匀时,定位误差率低;而当节点分布不均匀时,由于计算距离过程中误差累积较大,因此定位误差率高。 图1 DVHop定位算法流程 2 节点可信度特征分析算法设计 在相同的节点分布密度以及网络连通度情况下,质心与DVHop算法的可信度研究主要通过落在规定范围内的概率大小来反映, 接下来将着重介绍如何设计概率分布检测规则。 2.1 概率分布检测规则设计 概率分布检测规则的主要思想有:①分别用质心和DVHop算法对同一未知节点进行定位,并分别记录其值;②分别计算未知节点与两种算法计算值之间的距离;③判断其距离与通信半径关系,记录落在规定范围内的概率,分别以2倍、1倍和0.5倍半径进行讨论。规则中之所以对2倍、1倍和0.5倍通信半径所围成的圆进行讨论,是因为先以1倍半径为参照,然后对讨论的范围适当进行放大和缩小,如果目标节点落在了2倍半径之外,说明估算值误差大,如果目标节点落在了0.5倍半径内,说明估算值误差小。 图2 以A为基准节点的概率分布检测规则 图2给出了判断质心算法概率分布检测规则。其中A为目标结点,r为节点通信半径距离、D、D′、D′′为使用质心算法估算的目标节点可能存在的位置。以A为圆心,AB之间的距离为节点通信半径来讨论估算出的目标节点是否落在其围成的圆内。落在圆内,则进行记录,否则不记录。由于估算出的目标节点可能落在大于以A为圆心、AB之间的距离为半径的圆内D′的位置,也可能落在小于以A为圆心、AB之间的距离为半径的圆内D″的位置。为此,还要研究以A点为圆心、两倍的AB距离为半径和以A点为圆心、1/2的AB距离为半径这两种情况下,目标节点落在范围内的概率分布。DVHop算法的概率分布检测规则与上相同。 假设目标节点Ai的位置为(xi,yi),通过质心算法估算出的目标节点位置为Di,坐标为(pi,qi),则AiDi之间的距离为d(Ai,Di)=(xi-pi)2+(yi-qi)2,r为节点通信半径距离,质心与DVHop算法概率检测公式为: Cxy(Di)=1,d(Ai,Di)≤α×r0,其它 (1) 其中α为常量,其值为2、1或者0.5。 2.2 节点可信度检测仿真算法 节点可信度检测仿真算法实现步骤:①产生节点均匀随机分布的网络拓扑;②分别用质心和DVHop算法估算出目标节点的位置;③用两点距离公式计算目标位置与估算出的目标位置之间的距离;④用概率检测公式(1)检测质心算法估算的目标节点是否落在规定范围内;⑤用概率检测公式(1)检测DVHop算法估算的目标节点是否落在规定范围内;⑥分别计算两种情况下的概率分布情况,计算公式为: ∑ni=1Cxy(Di)/(N-M)(2) 其中n为落在规定范围内的个数,N为节点总数,M为锚节点个数。 3 仿真结果及分析 本文采用MATLAB 7.0对提出的算法进行仿真,仿真参数设置见表1,并对仿真结果进行比较分析,得到图3、图4、图5的结果。 表1 仿真参数 网络范围(m2)[]网络节点总数[]锚节点个数[]节点通信半径(m) 100×100[]100个[]5,10,15,20,25,30[]30 图3 以AB为半径的概率分布(节点通信半径为30m) 图4 以两倍AB为半径的概率分布(节点通信半径为30m) 图5 以1/2 AB为半径的概率分布(节点通信半径为30m) 图3、图4、图5为节点通信半径为30m,质心和DVHop算法概率分布随锚节点数量变化及检测范围分布图。试验结果表明,质心定位算法在锚节点数量少于20时,3种检测范围下其落在规定范围内的概率都较低,这说明质心算法在锚节点数量较少的情况下其可信度低于DVHop算法,同时也表明其定位误差率比DVHop算法大,但是随着锚节点数量的增加,特别是锚节点数量增加到25以后,其特性正好相反。 参考文献参考文献: [ 1 ] CHEN MIN XIOU, WANG YIN DIN. An efficient location tracking structure for wireless sensor networks[ J ]. Computer Communications,2009(32):14951504. [ 2 ] QINBIN HE, FANGYUE CHEN, SHUIMING CAI,et al. An efficient rangefree localization algorithm for wireless sensor networks[ J ].SCIENCE CHINA Technological Sciences,2011,54(5):10531060. [ 3 ] NIU YC, ZHANG SD, XU XY, et al.An enhanced DVhop localization algorithm for irregularly shaped sensor networks[ C ]. LNCS 4864,2007:694704. [ 4 ] NICULESCU DS. Forwarding and positioning problems in Ad hoc networks [ M ]. New Jersey: State University of New Jersey, 2004:2933. [ 5 ] 白进京.基于加权质心和DVHop混合算法WSN定位方法研究[ J ]. 计算机应用研究,2009,26(6):22482250. [ 6 ] 石为人,贾传江,梁焕焕.一种改进的无线传感器网络DVHop定位算法[ J ].传感技术学报,2011,24 (1):8387. [ 7 ] B M QIAO. Improved DVHOP localization based on better weighted leastsquare method[ J ].Information Technology Journal.2010,9(6):11721177. 责任编辑(责任编辑:杜能钢) |
随便看 |
|
科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。