移动节点定位范文

2024-06-20

移动节点定位范文（精选9篇）

移动节点定位第1篇

无线传感器网络作为物联网的核心技术,是目前信息科学的前沿研究方向[1]。节点位置不仅是无线传感器网络应用的必要信息,而且还是辅助路由、跟踪等其他技术的基础。通过静态锚节点辅助定位是典型的定位思路,算法性能受锚节点数量以及布置方式的影响[2]。使用的锚节点越多,网络布设的成本越高;反之,定位精度则下降。针对这一问题,近年来,学术界提出了多种基于移动锚节点(Mobile Anchor,MA)的定位算法[3,4,5,6,7],利用1个或多个在目标区域中移动的锚节点辅助定位(锚节点按照特定模型广播自身位置,本文称之为布设虚拟锚节点),待定位节点基于典型或改进的定位计算方法[8](如:基于测距、非基于测距)进行计算,避免大量静态锚节点带来的网络硬件成本增量,降低算法定位精度对锚节点密度的依赖。在典型定位计算方法中,基于RSSI的测距定位技术虽然具有低成本、低功耗等特点,然而在很多危险/恶劣环境中,虽然地形、面积已知,却缺乏无线信道损耗模型中相关参数的先验信息,难以通过RSSI值直接计算节点间距离,也就无法应用典型的测距定位计算方法(如:Multilateration[9])。面对这样的环境,现有算法大多基于大量静态锚节点采用非基于测距计算方法进行,在定位精度与网络成本上难以均衡。

本文面向无线信道损耗模型未知环境应用特点,针对基于静态锚节点定位技术以及RSSI测距定位计算方法的缺陷,设计基于移动锚节点的粒子群优化定位算法(PSO Localization Based on Mobile Anchor, PLBMA)。基于移动锚节点周期性广播自身位置(本文称这一过程为布设虚拟锚节点)辅助定位;在此基础上将节点定位问题抽象为非线性约束优化问题,通过构建加权定位目标函数,采用粒子群优化技术估计待定位节点位置。

1粒子群优化定位策略

1.1定位模型

无线信道损耗模型未知环境指若用于表达无线信道衰减的对数常态分布模型(式(1))参数(遮蔽因子Xσ、路径损耗指数γ)未知的应用环境。

$L (\hat{d})_{d B} = L (d_{0})_{d B} + 10 γ \lg (d / d_{0}) + X σ (d B) (1)$

由于在这类环境中,γ、Xσ未知,无法通过式(1)直接求解节点间距离d。令待定位节点i位置(xi,yi)与虚拟锚节点j间满足式(2),对其进行如下处理:

${\begin{cases} L_{i j} (d)_{d B} = L_{i j} (d_{0})_{d B} + 10 γ \lg (d / d_{0}) + X σ (d B) \\ d = \sqrt{(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}} \end{cases} (2)$

其中,Lij=Lij(d)dB-Lij(d0)dB为节点i关于邻居锚节点j的无线信号衰减观测值;(xj,yj)为锚节点j的位置;L(d0)dB为d0处无线信道损耗;若节点i的邻居锚节点数为nBA,则式(2)可转换为:

$ε (θ_{i}) = \sum_{j = 1}^{n_{B A}} | L_{i j} - S_{i j} (θ_{i}) | 。$

其中:θi=(xi,yi,γ)为未知参数,Sij(θi)=10γlg(d/d0),εij(θi)=|Lij-Sij(θi)|。

因此,在无线信道损耗未知环境中,节点i定位可抽象为非线性优化问题,目标函数如式(3)。

$\begin{array}{l} f (θ) = \min (ε (θ_{i})) = \\ \min (\sum_{j = 1}^{n_{B A}} | L_{i j} - S_{i j} (θ_{i}) |) (3) \end{array}$

1.2粒子群优化定位原理

粒子群优化算法(Particle Swarm Optimization,PSO)源于对鸟群群体运动行为的研究,是一种进化计算技术。通过迭代求解适应性函数fitness(X)值,优化、更新解空间参数;是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具。由于该算法具有原理简单、易于实现、可调参数少等特点,本文利用该方法求解式(3)。

1.2.1 适应性函数构建

适应性函数表征粒子的当前位置X相对目标函数的适应程度,在定位优化中等价于式(3)所示的目标函数。由于RSSI测量值存在误差,待定位节点距离锚节点越远,其测量误差越大;距待定位节点不同距离的锚节点在定位过程中发挥的作用应有所不同[10]。因此,构建距离权值w对式(3)进行加权处理:

${\begin{cases} f (θ_{i}) = \min (ε (θ_{i})) = \min (\sum_{j = 1}^{n_{B A}} w_{i j} | L_{i j} - S_{i j} (θ_{i}) | / \sum_{j = 1}^{n_{B A}} w_{i j}) \\ w_{i j} = 1 / d_{i j}^{2} = 1 / [(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}] \end{cases} (4)$

同时,让已完成定位的普通节点参与待定位节点的定位,增加参与定位的节点数量,构建:

$ε^{'} (θ_{i}) = \sum_{u = 1}^{n_{B Ν}} w_{i u} | L_{i u} - S_{i u} (θ_{i}) | / \sum_{u = 1}^{n_{B Ν}} w_{i u}$ 。

其中:nNB为参与定位的普通节点数, wiu为其相应定位权值, wiu=1/d $_{i u}^{2}$ =1/[(xi-xu)2+(yi-yu)2]。因此,式 (4)可转换为:

$\begin{array}{l} f (θ_{i} (t)) = \min (α ε (θ_{i} (t)) + (1 - α) ε^{'} (θ_{i} (t))) = \\ \min (α (\sum_{j = 1}^{n_{B A}} w_{i j} | L_{i j} - S_{i j} (θ_{i} (t)) | / \sum_{j = 1}^{n_{B A}} w_{i j}) + \\ (1 - α) (\sum_{u = 1}^{n_{B Ν}} w_{i u} | L_{i u} - S_{i u} (θ_{i} (t)) | / \sum_{u = 1}^{n_{B Ν}} w_{i u})) (5) \end{array}$

式(5)中:t为迭代次数,α∈[0,1]为权重因子。

由于节点位置(x,y)、信道衰减系数γ都具有相应的取值范围,假设:x∈[a,b],y∈[c,d],γ∈[e,f]。因此,式(5)中的无约束优化转变为有约束优化问题:

${\begin{cases} f (θ_{i} (t)) = \min (α \cdot ε (θ_{i} (t)) + (1 - α) \cdot ε^{'} (θ_{i} (t))) \\ s . t . g_{j} (θ_{i} (t)) \geq 0 (j = 1, 2, \dots, 6) \end{cases} (6)$

式(6)中:

${\begin{cases} g_{1} (θ_{i} (t)) = θ_{i, 1} (t) - a \\ g_{2} (θ_{i} (t)) = - θ_{i, 1} (t) + b \\ g_{3} (θ_{i} (t)) = θ_{i, 2} (t) - c \\ g_{4} (θ_{i} (t)) = - θ_{i, 2} (t) + d \\ g_{5} (θ_{i} (t)) = θ_{i, 3} (t) - e \\ g_{6} (θ_{i} (t)) = - θ_{i, 3} (t) + f 。 \end{cases}$

采用外点法构建罚函数P(θ):

${\begin{cases} Ρ (θ_{i} (t)) = Μ (t) \cdot \sum_{j = 1}^{6} [\min (0, g_{j} (θ_{i} (t)))]^{2} \\ Μ (t) = β \cdot Μ (t - 1) = \dots = β^{t} \cdot Μ_{0} 。 \end{cases}$

其中t为迭代次数,β≥2,则有约束优化适应性函数(式 (6))即可转换为无约束优化适应性函数:

f(θi)=min(αε(θi)+(1-α)ε′(θi)+P(θi)) (7)

1.2.2 节点定位数学模型

基于上述适应性函数,构建基于粒子群优化的节点定位数学模型:

$\begin{array}{l} p_{i} (t) = \\ {\begin{matrix} p_{i} (t - 1) ‚ & 若 f i t n e s s (θ_{i} (t)) \geq f i t n e s s (p_{i} (t - 1)) \\ θ_{i} (t) ‚ & 若 f i t n e s s (θ_{i} (t)) < f i t n e s s (p_{i} (t - 1)) \end{matrix} (8) \end{array}$

pg(t)∈{p0(t),…,ps(t)|f(pg(t))=

min{f(p0(t))},…,f(ps(t))}} (9)

式(9)中,t为当前迭代次数。设群体中的粒子数为s,群体中所有粒子所经历过的最好位置为pg(t),即为当次迭代的全局最优解。每次迭代更新依照式(10)、式(11):

Vi(t+1)=w(t)Vi(t)+c1r1[pi(t)-θi(t)]+

c2r2[pg(t)-θi(t)] (10)

$θ_{i} (t + 1) = θ_{i} (t) + V_{i} (t + 1) (11)$

式(10)中,w(t)为惯性权重因子(满足式(12)),c1和c2为正的加速常数,r1和r2为服从均匀分布的随机数。

$w (t) = w_{\max} - \frac{w_{\max} - w_{\min}}{Τ} \cdot t (12)$

式(12)中:wmax、wmin分别为惯性权重因子的最大值和最小值,t为当前迭代次数,T为迭代总次数。

2基于网格的移动锚节点完全遍历路径

典型的移动锚节点定位算法[3,4,5,6,7]在测定锚节点和未知节点的距离、计算未知节点坐标等环节进行探索和创新。在很多移动锚节点定位算法中,都是采用基于随机移动模型的移动锚节点的路径规划,无法确保虚拟锚节点为均匀分布,易形成定位盲区,降低定位精度。

由于上文提出的基于粒子群优化的定位模型中含有3个未知参数,为确保基本定位精度,需要4个以上的不共线虚拟锚节点参与定位。本文将网络覆盖区域划分为如图1所示的网格区域,锚节点通过移动在每个网格顶点布设一个虚拟锚节点,确保网格单元中的任意节点均有至少4个虚拟锚节点参与定位,其最短路径长度满足以下关系[7]:

$d i s (Ρ_{\min} (V)) = (m n - 1) l_{g} (13)$

式(13)中, m、n分别为网络覆盖区域划分的网格顶点数量(如图1所示),lg表示网格单元边长;满足式(13)最短完全遍历路径长度的方法很多,本文采用基于扫描线的最短完全遍历路径,原理简单,便于实现,对不规则环境适应力强,如图2所示。

3算法实现

在本算法中,移动锚节点采用基于扫描线的最短完全遍历路径,在每个网格顶点布设虚拟锚节点(广播自身位置信息),待定位节点收集邻居虚拟锚节点以及已完成定位的普通节点的位置信息,基于前文提出的粒子群优化定位策略构建加权定位目标函数,进行节点定位。待定位节点按照以下步骤进行定位操作:

第一步:接收其他节点位置信息;如果接收到虚拟锚节点位置或者已完成定位的节点位置信息,则保存其信息,当接收到一定数量的虚拟锚节点位置或者已完成定位的节点位置信息后,启动粒子群优化定位流程;

第二步:为每个粒子随机设置xi(0)、vi(0)、迭代次数初值,xi(0)∈[xmin,xmax],vmax=k·xmax,vmin=k·xmin (0<k<1), vi(0)∈[vmin,vmax];

第三步:根据式(7)计算每个粒子的适应性函数:fitness(xi(0));

第四步:根据式(8)、式(9)计算pi(0) and pg(0);

第五步:根据式(10)、式(11)更新xi(t), vi(t);

第六步:根据式(8)、式(9)更新pi(t)andpg(t);

第七步:更新迭代次数;

第八步:当pg(t)-pg(t-1)>η或者迭代次数达到预设最大值,则进入第九步;否则跳至第五步;

第九步:广播自身位置信息;

第十步:结束。

4算法仿真与性能分析

本文基于MATLAB仿真平台开展仿真实验,通过与典型算法Multilateration对比分析,对本算法性能进行验证。仿真条件设置为的正方形区域,设置一个移动锚节点,待定位节点随机布置,数量可调,网格单元边长lg可调,参数设置如表1所示。每个仿真运行200次,所有仿真结果取平均值。

仿真实验中,Multilateration采用如式(1)模型进行测距(假设γ已知)。

不同连通度条件的定位精度如图3所示。Multilateration定位精度不受网络连通度影响。由于在本文算法中,已完成定位的邻居节点参与定位,随着节点连通度的增加,算法的平均定位误差逐渐减小。当连通度较大时,本文算法定位精度高于Multilateration。

遮蔽因子σ是基于RSSI测距定位的主要干扰源,对算法定位精度影响较大。从图4中可以看出, Multilateration对σ较为敏感。虽然σ对本文提出的算法定位误差随着的增大也有所增加,但是随着连通度的增加,噪声影响有所弱化,比Multilateration具有更好的环境适应性。

5小结

本文针对无线信道损耗模型参数未知的应用环境,提出基于移动锚节点的粒子群优化节点定位算法。仿真和分析结果证明,该算法定位精度较高,对环境噪声变化具有较强的适应能力。进一步将对算法执行效率、开销等方面开展深入研究与改进,提高算法实用性。

参考文献

[1] Akyildiz I F,Su Weilian,Sankarasubramaniam Y,et al.A survey onsensor networks.IEEE Communications Magazine,2002;40(8):102—114

[2] Savvides A,Han C C,Srivastava M.Dynamic fine-grained localiza-tion in ad-hoc networks of sensors.In:Proc of the 7th Annual Int’lConf.on Mobile Computing and Networking,2001:166—179

[3] Kyunghwi K,Wonjun L.MBAL:a Mobile beacon-assisted localiza-tion scheme for wireless sensor networks.In:Computer Communica-tions and Networks,2007.ICCCN 2007.Proceedings of 16th Inter-national Conference on,2007:57—62

[4] Srinath T V.Localization in resource constrained sensor networksusing a mobile beacon with in-ranging.In:2006 IFIP InternationalConference on Wireless and Optical Communications Networks,2006:5—13

[5] Kuo-Feng S,Chia-Ho O,Jiau H C.Localization with mobile anchorpoints in wireless sensor networks.IEEE Transactions on VehicularTechnology,2005;54(3):1187—1197

[6] Patwari N,Ash J N,Kyperountas S,et al.Locating the nodes:coop-erative localization in wireless sensor networks.IEEE Signal Process-ing Magazine,2005;22(4):54—69

[7]石为人,许磊,徐扬生.一种基于移动锚节点的静态无线传感器网络定位算法.仪器仪表学报,2007;28(3):385—393

[8] Priyantha N B,Chakraborty A,Balakrishnan H.The cricket location-support system.In:Proceedings of the 6th Annual International Con-ference on Mobile Computing and Networking,2000:32—43

[9] Desai J,Tureli U.Evaluating performance of various localization al-gorithms in wireless and sensor networks.In:IEEE 18th InternationalSymposium on Personal,Indoor and Mobile Radio Communications,2007:1—5

移动节点定位第2篇

面对当前各类销售行业的波动与激烈竞争，如何在危机和挑战并存的环境下，突破现有资源，占领更多的市场份额，维护和发展终端市场，是企业需要面对和深思的问题。如何让公司员工切实的执行公司的营销战略、市场一线人员真正的把营销计划落到实处、实现市场的快速扩张成为企业领导者所面临的头等问题。

基于此，北京万特锐科技有限公司联合中国移动集团总公司联合推出—中国移动位置管理平台“企效通”。

公司简介：北京万特锐科技是最早获得中国移动授权,在全国开展人员位置服务产品开发与推广的高科技企业，是中国移动集团公司位置服务（LBS）领域的最大的合作伙伴。目前已为全国数千家企业提供了基于位置的销售人员信息化管理方案.“企效通”是专门为企业销售管理工作开发的管理系统，包括位置管理系统、移动办公系统、客户管理系统、销售终端数据统计几个模块；该系统很好的解决了销售管理中存在的人员行为难以掌控、网点数据难以统计等管理难题，帮助企业实现从“销售结果管理”到“销售过程管理”的完美蜕变。

平台模块：

1.功能

2.3.4.移动办公模块：主动定位、工作日志、行程管理、通知公告、信件管理等客户管理模块：新建客户、客户跟进、客户信息管理、过往客户管理等网点数据统计：网点库存、网点订货、网点销售、现场图片上传等

平台优势：位置管理系统：包括立即定位、轨迹回放、网点标注、历史数据导出、考勤报表等

1.无需硬件投入：如此强大的管理功能都基于最基础的移动技术实现，业务人员只要

稍加培训就可以利用自己的手机用短信或wap上报数据

2.无法破坏：与其它定位方式相比，我们采用的定位技术不依赖单独的硬件设备，人

员手机开机即取得其位置，根本无法破坏，因此更加可靠稳定。（这是我们在定位方面最大的优势；卫星定位缺乏成功案例的根本原因也在于此）

3.位置管理我们更专业：公司成立七年来一直从事与人员位置管理产品的研发与推

广，目前已为全国千余家企业提供了基于位置的销售信息化管理系统。

“企效通”能为企业解决的难题：

1.可随时掌握外勤员工的位置，了解外勤人员的工作状态

2.可根据实际工作状态调整整体工作计划，从而进行人员的综合调度管理

3.可随时了解各销售网点的当天销售数量

4.可随时监控外勤人员工作计划完成进度，让人员考核更科学

5.可有效防止虚假差旅费用的产生

6.有利于塑造诚信的工作氛围。

无线传感器网络中节点定位技术研究第3篇

关键词无线传感网络节点定位定位算法物联网

中图分类号：TN929.5 文献标识码：A

0引言

无线传感器网络（Wireless Sensor Networks，简称WSN）是伴随无线通信、电子与传感技术发展起来的新兴技术，它是对传统的传感器技术、信息处理技术和网络通信技术的融合，已成为国内外各行业的研究重点，也是跨学科的研究热点。

在 WSN 的实际应用过程中，确定节点的位置十分重要，定位技术是 WSN的主要技术指标之一。在研究节点的定位时，需要考虑的因素较多：比如基础设施、网络的连通性、节点密度、锚节点密度、测距误差、通信开销和计算开销等。因此，从节点定位的方法到算法的研究再到节点定位的实现并不是一件容易的事情，需要不断的尝试和探索。

1影响节点定位的因素

影响节点定位的因素很多，如网络的连通性、节点密度、锚节点密度、测距误差、基础设施、通信开销和计算开销等。

网络的连通性与网络的连通度对于定位算法是一个很重要的影响因素。网络的连通性定义为如果节点之间可以直接互相通信，就称这对节点是连通的。联通度是形成网的连通概率的多少，定位系统达到的覆盖率能有多大。锚节点也称为信标节点、灯塔节点等，可通过某种手段自主获取自身位置的节点，它是无线传感网络节点定位的核心要素，锚节点的密度越大说明已经节点位置的节点就多，为了降低开始部署时的锚节点密度，可以考虑将已定位的未知节点升级为锚节点。预先不知道自身位置的是未知节点或待定位节点，需使用锚节点的位置信息并运用一定的算法得到估计位置的节点。基础设施是协助节点定位且已知自身位置的固定设备，如卫星基站、GPS等。测距技术是任何定位技术的核心。跳数是定位系统出现不稳定的一个很重要的原因。

2节点定位的方法

目前WSN的定位方法较多，根据传感器接收信息的方式和节点处理数据方式采取不同的定位方法。传感器接收和采集信息受距离、角度、时间和周围锚节点信息的影响，这些数据也是定位算法的计算基础。无论采用什么样的数据处理方式，其目的都是将数据转换为坐标，完成定位功能。

目前节点定位的方法主要分为三类：一是根据是否测量距离分为距离相关方法和距离无关方法。两种方法各有优缺点，在实际应用过程中经常混合使用。二是根据网络的拓扑结构和连通性分为单跳方法和多跳方法，单跳方法实现简单，但只使用于测量距离小的场合。多跳方法应用广泛，使用于传感网络结构复杂的情况。三是根据数据的处理方式可分为：集中式方法和分布式方法。集中式处理方法可以使数据在数据中心汇总，集中处理，但通信量较大。但传感器采集的信息是基于周围的节点时，分布式方法在自身的后台执行定位算法，降低了网络通信量，但是分布式算法实现复杂，在很多平台上很难开展。基于众多学者的研究，普遍认为基于距离相关和距离无关的方法更加实用。

3节点定位算法

3.1 基于距离的算法

基于距离相关的算法需要测定锚节点与未知节点之间的距离或是角度信息，再根据三边测量法、三角测量法或最大似然估计法来确定未知节点的位置。根据测量技术可以分为：基于RSSI的算法，该算法对硬件要求相对较低，功耗低，但误差大，不适用；基于 TOA/TDOA和基于AOA的算法对硬件要求较高，功耗大，误差小，适用性强。

基于距离无关的算法不需要确定节点之间的距离长度，对硬件的要求相对就较低，从而更适合用于无线传感器网。常见的有质心、DV-Hop、APIT、Amorphous、凸规划等5种定位算法。但是基于距离无关的算法多处于理论研究阶段，适应范围有一定的局限性，在實际应用过程中主要考虑基于距离相关的算法。

3.2节点定位新算法

（1）基于移动锚节点的定位算法：利用移动锚节点自身的可定位性和可移动性定位无线传感网络中的局部节点，但在设计时需要科学规划移动锚节点的路径和合理的定位机制。

（2）立体三维定位算法：从传统的二位平面结构提升到三维空间，但获取更准确的锚节点需要寻求更精确的广播周期和消息生存周期，缩减定位时间需要改进锚节点的选择和过滤机制等。

（3）智能定位算法：随着低功耗技术、微处理器技术、FPGA技术的发展，智能定位算法将在未来的定位系统中得到广泛的应用。

4小结

无线传感器节点的自身定位具有重要的意义，决定着无线传感器网络的发展。目前，节点定位技术面临着诸多问题，无论是定位方法和定位算法上都有许多需要改进的地方。随着技术的发展协作定位技术、跨层设计、移动跟踪等方法将成为研究热点。

基金项目：广东科技学院课题《无线传感技术在智能物流中的应用研究》，立项编号：GKY-2012KYYB-4

参考文献

[1] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报， 2005.16（5）： 857-868.

[2] 杜存功，丁恩杰，苗曙光.无线传感器网络改进型节点定位算法的研究[J].传感器与微系统.2010.29（1）.

[3] 李哲涛，李仁发，魏叶华.无线传感器网络中时间同步与测距协同算法[J].计算机研究与发展，2010.47（4）.

移动节点定位第4篇

关键词：无线传感器网络,移动信标,节点定位

随着传感器技术、无线通信、微电子技术以及嵌入式计算等技术的发展,无线传感器网络(Wireless Sensor Network简称WSN)得到了广泛应用,成为当今活跃的研究领域。无线传感器网络是新型的传感器网络,同时也是一个多学科交叉的领域,与当今主流无线网络技术一样,均使用802.15.4的标准,由具有感知能力、通信能力和计算能力的大量微型传感器节点组成,具有低成本、低功耗的优点和强大的数据获取和处理能力。

在无线传感器网络的众多应用中,如:国防军事、环境监测、交通管理、医疗卫生、目标跟踪、物流管理、入侵检测、交通流量监控和勘测应用等领域,监测到事件之后需要确定事件发生的位置,信息融合后得到的相关数据信息如果不包含事件位置信息将毫无意义,只有带有标识位置信息的传感数据才有实际的意义。传感器节点自身的正确定位是提供事件位置信息的前提,因此节点的精确定位基础而关键[1]。

1 无线传感器网络节点定位的分类及基本方法

节点定位是指确定传感器节点的相对位置或绝对位置,节点所采集到的数据必须结合其在测量坐标系内的位置信息才有意义。人工部署传感节点和为所有节点安装GPS接收器都会受到成本、功耗、节点体积、扩展性等方面的限制,甚至在某些应用中是根本无法实现的。通常是为部分节点配置定位装置(如GPS接收器)或事先标定其准确位置,这些节点称为信标节点(也称锚节点),再利用信标节点的相关信息采用一定的机制与算法实现无线传感器网络节点的自身定位。目前人们提出了两类节点定位算法[2]:基于测量距离的定位算法与测量距离无关的定位算法。基于距离的定位方法首先使用测距技术测量相邻节点间的实际距离或方位,然后使用三边测量法、三角测量法、最小二乘估计法等方法进行定位。与测量距离无关的定位算法主要包括:APIT、质心算法、DV-Hop、Amorphous等。

1.1 基于无线传感器网络自身定位系统的分类[1,3,4,5]

1)绝对定位与相对定位。绝对定位与物理定位类似,定位结果是一个坐标位置,如经纬度。而相对定位通常是以传感区域某点为参考,建立整个网络的相对坐标系统。

2)物理定位与符号定位。经纬度就是物理位置;而某个节点在某街道的某门牌的建筑物内就是符号位置。一定条件下,物理定位和符号定位可以相互转换。与物理定位相比,符号定位在一些特定的应用场合更加便于使用。

3)集中式计算与分布式计算定位。集中式计算是指把所需信息传送到某个中心节点,并在那里进行节点定位计算的方式;分布式计算是指依赖节点间的信息交换和协调,由节点自行计算的定位方式。

4)移动信标与固定信标定位。移动信标节点是一类装备了GPS或其它定位装置的可移动节点,它在移动的过程中周期性发布自己的位置信息。基于移动信标的未知节点定位有很多优点,如定位成本低,容易达到很高的定位精度、可实现分布式定位计算、易于实现三维定位等。而固定信标节点是一类装备了GPS或其它定位装置的不可移动节点。

1.2 基于距离的节点坐标计算基本方法

待定位节点在获得与邻近信标节点的距离信息后,通常采用下列方法计算自身的位置[3]。

1)三边测量法:利用网络中三个信标节点的位置坐标以及未知节点到这三个信标节点的距离,运用几何方法求出未知节点的坐标。

2)三角测量法:利用网络中三个信标节点的位置坐标以及未知节点为角顶点角边分别为三个信标节点的角度,运用几何方法求出未知节点的坐标。

3)最小二乘估计法:利用未知节点的相邻节点中的多个信标节点的位置坐标以及它们与未知节点的距离或角度,运用最小均方差估计方法求出未知节点的坐标。

1.3 常用的测距方法

1)信号接收强度(RSSI)测距法

已知发射功率和天线接收增益,在接收节点测量信号接收功率,计算传播损耗,使用理论或经验的无线电传播模型由传播损耗计算出信源与接收者间的距离。通常使用下列对数-常态分布模型来计算节点间的距离[1]。

其中PL(d)[d B]是经过距离d后的路径损耗,X是平均值为0的高斯分布随机变数,其标准差取为4至10,λ为取衰减因子通常为2至3.5,f是频率,取d0=1(m),这样根据上述3式可得节点间的距离。

2)到达时间测距法

到达时间(TOA)技术通过测量信号传播时间来测量距离,若电波从信标节点到未知节点的传播时间为t,电波传播速度为c,则信标节点到未知节点的距离为t×c。

3)时间差测距法

TDOA测距是通过测量两种不同信号到达未知节点的时间差,再根据两种信号传播速度来计算未知节点与信标节点之间的距离,通常采用电波和超声波组合。

4)到达角定位法

到达角(AOA)定位法采用阵列天线或多个接收器组合来获取相邻节点所处位置的方向,从而构成从接收机到发射机的方位线。两条方位线的交点就是未知节点的位置。

1.4 典型非测距算法

基于距离测量和角度测量的定位算法的缺点是对专用硬件有一定的要求,从而使传感器节点成本和体积加大,限制了它的实用性。非测距的算法不需要测量未知节点到信标节点的距离,在成本和功耗方面比基于测距的定位方法具有一定的优势,但是精度相对不足。

1)DV-hop算法

为了避免对节点间距离的直接测量,Niculescu等人提出了DV-hop算法[3]。该算法基本思想是:用网络中节点的平均每跳距离和信标到待定位节点之间的跳数乘积来表示待定位节点到信标节点之间的距离,再用三角定位来获得待定位节点的位置坐标。

2)质心法

质心法由南加州大学Nirupama Bulusu等学者提出[3],该算法是未知节点以所有可收到信号的信标节点的几何质心作为自己的估计位置,它是一种基于网络连通性的室外节点定位算法。

3)APIT算法

一个未知节点任选3个能够与之通信的信标节点构成一个三角形,并测试自身位置是在这个三角形内部还是在其外部;然后再选择另外3个信标节点进行同样的测试,直到穷尽所有的组合或者达到所需的精度。

4)Amorphous算法

Amorphous定位算法[3]采用与DV-Hop算法类似的方法获得距信标节点的跳数,称为梯度值。未知节点收集邻居节点的梯度值,计算关于某个信标节点的局部梯度平均值。Amorphous算法假定预先知道网络的密度,然后离线计算网络的平均每跳距离,最后当获得3个或更多锚节点的梯度值后,未知节点计算与每个锚节点的距离,并使用三边测量法和最大似然估计法估算自身位置。

2 基于移动信标的无线传感器网络节点定位技术

无论是距离相关还是距离无关定位算法,常采用固定信标节点方式测量距离、相对角度、传播时间差及传播时间等进行节点定位[1]。通常参与定位的固定信标节点越多,定位精度将越高。但是信标节点的成本远远高于普通节点,当定位工作完成后,信标节点将转成普通的传感器节点使用。因此信标点越多,布设整个网络的成本将会增大,定位算法的计算负荷以及通讯负荷将会增大[1],过多的信标节点将会造成较大的浪费。所以利用移动节点发出的虚拟坐标点进行辅助定位的思想将成为节点定位研究的一个重要研究方向。

假定整个WSN由静止节点以及移动节点(如撒播节点完毕的飞机、运动的车辆、移动的小型机器人或普通的能移动的传感器节点等)两种类型节点构成。根据传感器网络的规模大小,可以配置一个或者多个移动节点。各移动节点均配置一个GPS接收器用于定位移动信标节点本身,并有足够的能量自我移动或捆绑移动机器人、移动车辆或三维空间中的飞机等工具。移动节点在传感器区域内按照一定的运动路径移动,并周期性地发送坐标位置信息,待定位节点根据接收到的坐标信息与采用适当的定位算法完成定位[6]。

近几年有一些研究者对移动锚节点路径规划展开研究,提出了一些比较好的路径规划方案。移动锚节点路径规划主要有两个目标:

1)移动轨迹能够覆盖网络中的所有未知节点;

2)为未知节点定位提供质量好的信标点。

如果满足网络节点均匀分布的条件,规划路径通常采用静态规划路径,移动锚节点都按照预先规划的路径移动,不具有根据节点分布状况灵活变化的性能。文献[7]针对移动锚节点的路径规划问题利用空间填充线理论提出了SCAN、DOUBLESCAN以及HILBERT路径规划方法,分别如图1、图2和图3所示。在节点通信距离小和空间填充线密度大的条件下,SCAN路径比HILBERT路径的定位结果准确。但是在节点通信距离大、空间填充线密度较小时,HILBERT路径明显优于SCAN路径。

SCAN路径存在明显的缺点就是提供了大量共线的信标点,HILBERT路径通过增加移动路径长度解决了信标点共线性的问题,只要达到一定的密度就可以为定位提供优质的不共线信标点。为了解决信标点存在共线性的问题,文献[8]提出了圆形规划路径和S形规划路径方法,如图4和图5所示。圆形规划路径完全覆盖方形网络区域时必须增加外围大圆路径,这很大程度增加了路径的长度。而圆形的直径非常大时,在局部带来了信标点的共线性问题。S形路径通过引入S形曲线代替直线,解决了信标点共线性问题。

而对于实际环境中节点非均匀分布的情况,文献[9]提出了提出了宽度优先和回溯式贪婪算法。这种方法能够根据网络信息自适应进行路径规划,规划路径不再是规则的图形,能够充分利用节点分布信息覆盖所有节点,保证路径最短,克服了静态路径规划的缺点。文献[10]提出让一个携带GPS的移动信标采用随机移动模型的方式尽量遍历传感区域,然后采用分布式算法为未知节点定位,该方法结合了基于测距方法的优点,并且无需布置固定的信标节点,节省了成本开销,但是由于移动信标的移动模型采用随机的方式,难以让其移动范围覆盖整个传感区域,从而有些未知节点无法定位。

3 定位算法的评价标准

定位算法设计的优劣通常以下列几个评价标准[11]来评价:

1)定位精度:一般用误差值与节点无线射程的比例表示,是定位技术首要的评价指标。

2)定位覆盖率:指利用定位算法能够进行定位的节点数与总的未知节点个数之比,它是评价定位算法的另外一个重要的指标。

3)信标节点密度:信标节点占所有节点的比例或者是单位区域内信标节点的数目。

4)节点密度:节点密度通常以网络的平均连通度来表示。

5)功耗:功耗是指传感器节点在单位时间内所消耗的能源的数量。由于传感器节点不会始终在工作的,有时候会处于休眠状态,但这同样也会消耗少量的能量,因此,传感器节点的功耗一般会有两个,一个是工作时的功耗,另一个是待机时的功耗。

6)成本:包括时间、空间和费用。时间指一个系统的安装、配置和定位所需的时间。空间包括一个定位系统或算法所需的基础设施和网络节点的数量、安装尺寸等。费用则包括实现某种定位系统或算法的基础设施、节点设备的总费用。

7)鲁棒性:定位系统和算法必须具有很强的容错性和自适应性,能够通过自身调整或重构纠正错误、适应环境、减小各种误差的影响,以提高定位精度。

上述的这些评价指标不仅是评价WSN自身定位系统和算法的标准,也是其设计和实现的优化目标。

4 结束语

使用移动信标节点来完成WSN所有节点的定位,就必须要足够的时间让移动信标节点遍历完整个网络,为了减小所有节点定位所需的时间以及提高定位效率,如何进一步优化移动信标节点的运动路径将成为基于移动信标的WSN节点定位技术更研究的重要方向。

参考文献

[1]孙利民.无线传感器网络[M].北京:清华大学出版社,2005.

[2]A l-Karaki.JN,Kamal.AE.Routing Techniques in Wireless Sensor Networks:A Survey[J].In Wireless Communications,IEEE,Volume:11,Issue:6,Dec,2004:6-28.

[3]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-869.

[4]Kushwaha,M.Molnar,K.Sallai,J.Volgyesi,P.Maroti,M.Ledeczi,A.Sensor Node Localization Using Mobile Acoustic Beacons[C],Inproc.2005.IEEE International Conference on Mobile Adhoc and Sensor Systems Conference,Nov,2005.

[5]倪巍,王宗欣.基于接收信号强度测量的室内定位算法[J].复旦学报(自然科学版),2004.43(1):72-76.

[6]Mihail L.Sichitiu,Vaidyanathan Ramadurai.Localization of Wireless Sensor Networks with a Mobile Beacon[C].//IEEE 2004:174-182.

[7]Koutsonilas D,Das S M,Hu Y Charlie.Path Planning of mobile landmarks for localization in wireless sensor networks[J].ComputerCommunication.2007,30(13):2577-259.

[8]Rui Huang,Zaruba Gergely V.Static Pathplanning for mobile beaeons to localize sensor networks[C]//Proc of IEEE PerComW.Piscat-away,NJ:IEEE,2007:323-330.

[9]Hongjun Li,Jianwen Wang,Xun Li and Hongxu Ma.Real-time Path Planning of Mobile Anchor Node in Localization for Wireless Sen-sor Networks[C].//Proeeedings of the 2008 IEEE International Conference on Information and Automation,Zhangjiajie,China,June,20-23,2008.

[10]Srinath T V.Localization in Resource Constrained Sensor Networks Using a Mobile Beacon with In-Ranging[C]//IFIP InternationalConference on Wireless and Optical Communications Networks,India,2006:301-305.

一种改进的节点定位方法第5篇

无线传感器网络是21世纪最核心的关键技术之一[1],有大量低成本且具有传感能力﹑计算能力和无线通信能力的传感器节点自组织构成的网络,其主要功能是智能感知外界环境,并将处理后的信息提供给用户,被广泛地应用在环境监测、远程医疗监护、军事国防等领域[2]。通常只有确定位置的节点信息才会有意义。由于GPS设备昂贵,不可能为每个节点安装来获得位置信息,因此节点定位的研究具有重要意义。

1 相关工作

无线传感器网络静止节点的研究已经比较成熟,一些定位算法是为静止节点设计的。其中一些要求未知节点周围有高密度的锚节点,如Centroid[3]算法、APIT[4]算法等;其他的有依赖网络和规则分布的节点,如DV-HOP[5]、RSSI[6]等;将这些算法应用到移动节点则需频繁地更新节点的位置信息,会耗费大量的资源,从而减低网络的速度及影响定位的精度。

目前,提出了很多WSN的定位算法,主要分为非基于锚节点和基于锚节点的WSN定位算法。基于非锚节点的定位算法通过计算相对位置,生成一个WSN的相对位置地图,给WSN带来很大的限制。而锚节点可以预先获取自身位置的节点,锚节点的定位算法通过已知节点定位剩余节点。通过移动锚节点的运动,去获知未知节点的信息,针对移动节点如何实现、低成本、低功耗和高精度的研究,是面临的热点和挑战[7]。

人们采取各种方法来努力地提高节点的定位精度,如rang-based定位算法,使用多次测量、循环定位求精等算法,减少测距误差对定位精度的影响,但开销大,收敛的速度慢。蚁群算法[8]是一个分布式的随机搜索、自组织、离散的、容易实现的算法,但是当节点规模较大时,搜索最优解存在需要花费很长的时间、容易停滞等缺点,进而影响定位的精度。蒙特卡罗算法(MCL)[9]利用移动节点的移动性来辅助定位,给无线传感器的定位带来很多方便,很多学者在此算法基础上进行改进,得到自己的方案,如基于测距的MCL[10],把测距信息应用到MCL中提高定精度。Mixture MCL[11]算法通过限定节点的采样范围等方法过滤了阶段,进行了改进。

本文受蚁群算法和蒙特卡罗算法的启示,借助一定的移动模型预测节点的估计位置,通过节点的估计位置与邻接节点的测量距离的确定位置的修正函数,在解空间里搜索最优的解作为移动节点的位置,定位的精度更高。

2 蚁群算法及其特点

人们从用自然界蚂蚁之间的相互协调合作的工作原理及合作规则中受到启示,提出蚁群算法来解决现实生活中的一些复杂问题。蚁群算法是一种模拟进化算法,是由意大利学着M.Dorigo等人首先提出的。该算法模拟蚂蚁搜索食物的过程。蚂蚁在没有任何可见的提示下 ,找出蚁穴到食物的最短路径,并且随着环境的变化而变化地搜索新的路径,产生新的选择,为最优化问题的求解提供一种有效的工具。

蚁群中存在一种蚂蚁信息传递交流机制,蚂蚁在运动时会分泌信息素,该物质会随着时间的变化而挥发,蚂蚁选择一条路径的概率随着该路径上信息素浓度的增大而增大,当一条路径上蚂蚁的数量较少,随着时间的推移,信息素的浓度会逐渐地蒸发掉,其他蚂蚁选择该路径的概率就会减少。由于越短的路径所需的时间越短,此路径的信息素的浓度就越大,从而找到一条从蚁穴到食物的最短路径。

应用旅行商问题(n个城市的最短回路问题)来描述蚁群算法:

步骤1 初始化蚁群,将m只蚂蚁放入n个随机选取的城市中,蚂蚁K选择下一个城市的依据有两个方面,一是t时刻连接城市i和j的路径上的信息素的浓度τij;二是城市i转移到城市j的能量度ηij。蚂蚁K从城市i移动到城市j的概率为:

$Ρ_{i j} = {\begin{cases} \frac{(τ_{i j})^{α} (η_{i j})^{β}}{\sum_{u \in i j} (τ_{i u})^{α} (η_{i j})^{β}} j \in J Κ \\ 0 o t h e r w i s e \end{cases} (1)$

其中τij表示城市i和j 之间的残留信息量,ηij 为边n (i ,j)的能量度,代表路径形成的代价,该值可以增强蚁群探寻新路径、适应路径变化的能力。α和β分别表示τij和ηij的可调权重,蚁群的路径选择可以通过调整α和β的值来进行实现。JK为蚁群还未访问过的集合。

步骤2 信息素浓度的更新。蚂蚁K根据步骤1选择访问下一个城市,在走完一遍后,对剩余的信息素进行更新处理。则信息素浓度更新的方程为:

τij=(1-ρ).τij+ρ.τ(0) (2)

其中,(1-ρ)表示为信息素的衰减系数, $ρ \in [0, 1]$ 为信息素的持久行,随着时间的改变信息素会随着蒸发。τ(0)为信息素的初始值。

步骤3 当全部蚁群完成一次周游后,按以下方程对最优蚂蚁路径上的信息素进行全局的更新:

$τ_{i j} = (1 - ρ) . τ_{i j} + \sum_{k = 1}^{k} Δ τ_{i j}^{k} (3)$

其中Δ τijk为蚂蚁在其经过的边(i,j)上留下的信息量。

如果第k只蚂蚁在时刻t到t+1经过路径,则局部信息模型中的Δ τijk可以表示为:

$τ_{i j}^{k} = {\begin{cases} \frac{Q}{d_{i j}} 如果蚂蚁 k 在 t + 1 时刻经过 (i, j) \\ 0 o t h e r w i s e \end{cases} (4)$

其中Q表示蚂蚁所留轨迹数量的一个常数。

步骤4 当每只蚂蚁都完成一次上述操作,称该算法完成一次周游,循环上述步骤,直到达到终止条件。

3 蒙特卡罗定位算法

蒙特卡罗定位算法的核心思想是以贝叶斯滤波位置估计为基础,用若干个带有权重的离散采样来描述移动节点在状态空间的位置分布。本文主要研究的是如何获得一个移动节点可能位置的概率分布。

移动节点的定位问题描述如下:其中t={1,2,3,…}表示离散时间,At表示在时间t处节点的位置分布,Bt表示在t-1到t时刻间锚节点接受到的观测值,移动方程P (At ︱At-1)描述了基于t-1时刻的位置分布对t时刻进行预测,观测方程P (At ︱Bt)描述的是在t时刻给定的观测值Bt后在At处的概率,算法的目的就是节点通过t-1时刻的转移方程P (At ︱At-1)来预测t时刻的位置分布,并用t时刻的观测方程P (At ︱Bt)描述节点在t时刻的位置分布。

算法的步骤如下:

(1) 初始化阶段在未知节点的分布区域随机的获取N个样本点。

(2) 预测阶段将运动模型和运动速度结合起来预测节点的位置。假定节点的最大速度是已知的,节点根据前一时刻的位置和运动的最大速度随机采样。对于一个移动的节点,仅知道它的速度小于等于V,则t时刻节点位置At一定以t-1时刻位置At-1为圆心,以V为半径的圆内。假定该速度服从均匀分布,则有:

$Ρ (A_{t} | A_{t - 1}) = {\begin{cases} \frac{1}{π V^{2}} ∥ A_{t} - A_{t - 1} ∥ \leq V \\ 0 o t h e r w i s e \end{cases} (5)$

(3) 过滤阶段根据观测方程和感知信息(一跳和二跳锚节点的位置信息)把不符合过滤条件的样本过滤掉,用h1表示一跳锚节点集合,h2表示两跳锚节点集合,r表示通信半径,则过滤条件为:

{∀b∈h1,d(A,b)≤r}∧{∀b∈h2,r∠d(A,b)≤2r} (6)

其中,d (A, b)表示样本A和锚节点b之间的欧氏距离,当过滤条件不满足时,P (At︱Bt)=0,否则就是一个均匀分布。

如果剩余的有效样本数少于N个,则进行重采样操作,直到采集到足够的样本,最后把样本集中所有样本的均值作为节点位置的估计值。

3.1 节点移动模型

借助蒙特卡罗定位MCL的思想,通过一种移动节点运动的速度信息预测节点的位置,此运动模型在预测时会存在一定的误差,在一定的误差范围内,可以通过节点的运动约束条件来定位节点的位置,从而提高节点的定位准确度。Vi(t)表示t时刻移动节点的速度,表示方位角,Si(t) (Xi(t) ,Yi(t) )表示节点此时的位置,△T表示t-1时刻到t时刻的时间间隔。移动节点根据t-1时刻节点的状态和速度信息计算t时刻的状态,节点的移动模型如下:

$S_{i (t)} = {\begin{cases} X_{i (t - 1)} + v_{i (t - 1)} \times Δ Τ \times \cos θ_{i (t - 1)} \\ Y_{i (t - 1)} + v_{i (t - 1)} \times Δ Τ \times \sin θ_{i (t - 1)} \end{cases} (7)$

Vi(t)=HVi(t-1)+C rand (8)

其中,H为惯性权重,可以对算法的搜索能力进行调整,C为加速常数,rand为节点的方向性随机运动设定,是介于(0,1) 之间的随机数。

3.2 目标函数的确定

对于群体定位在二维平面上,至少要取得3个锚节点的位置信息才可以定位在此算法中,我们采用样本的后验概率分布估计节点的位置,消除了定位至少需要3个锚节点信息的局限性,在定位区域内选取m个锚节点,坐标E j =(xi ( t) ,y (j)),j=1,2,…,m。t时刻移动节点i 和锚节点之间的距离Dij为:

Dij=‖Si(t)-Ej‖ (9)

假定坐标Si(t)是获取的随机变量,满足均匀分布概率,并且依赖移动节点和锚节点之间的距离误差ɛ,则概率密度的公式为:

$Ρ = (S_{i (t)} | D_{i j}) = \frac{1}{\sqrt{2 π σ}} \exp [- \frac{1}{2} \frac{ε^{2}}{σ^{2}}] (10)$

此时,a=Dij-rj,rj是通过某种测量方式,如接受信号节点的强度到锚节点的跳数等获得的在t时刻移动节点和锚节点之间的测量距离,m为测量距离的误差范围。

3.3 AC-MCL算法主要步骤

步骤1 定位初始化阶段。在定位区域内随机选取N个样本点,每个样本表示节点在此定位区域的可能分布。移动节点在t时刻的位置Bi=(Xi(t) ,Yi(t) ), dij表示Bi和Bj之间的估计的距离,p(θ)为移动节点在t+1时刻到达任意位置的分布概率,推导出p(θ)的表达式为:

$Ρ (θ) = (\frac{1}{2 π Ω^{2}} e \frac{- z^{2}}{2 Ω^{2}}) π R^{2} (11)$

其中, $Ω = 6.328 \frac{R^{2}}{σ^{2}} + σ, σ$ 是高斯分布方差,R为节点通信半径。

步骤2 计算各路径上的信息量。设τij是t时刻Bi和Bj路径上残留的信息量,则路径(i,j)上的信息量为:

$τ_{i j} (t) = {\begin{cases} 1 d_{i j} \leq r \\ 0 d_{i j} ≻ r \end{cases} (12)$

其中,r=A+d(min)+B·(dmax-dmin),A、B为常量参数,dmin=min(dij),dmax=max(dij)。

步骤3 计算Bi到达Bj的概率。在t时刻蚂蚁从节点位置Bi到Bj的转移概率为:

$Ρ_{i j} (t) = \frac{τ_{i j}^{α} (t) η_{i j}^{β}}{\sum_{l \in L} τ_{i l}^{α} η_{i l}^{β}} (13)$

其中,L={l|dlj≤r,l=1,2,…,M}。L表示蚂蚁在t+1时刻可能到达的位置号。l表示移动节点到下一位置的距离小于r的所有节点的集合。M为蚂蚁移动的总位置号,ηil(t)为权重参数。

步骤4 判断如果Pij(t)≥P0,则蚂蚁从节点Bi移动到节点Bj的领域。P0为一个给定的概率值。

步骤5 根据蚂蚁下一时刻到达的某一位置的分布式概率和转移概率,得到蚂蚁t+1时刻的位置,则联合分布概率为:

P=P(θ)·Pij(t) (14)

步骤6 根据接受到的测量值rj,利用式(10)计算每个样本点的权重。

步骤7 所有样本的标准权重为:

$\bar{w_{n}^{i}} = \frac{w_{n}^{i}}{\sum_{i = 1}^{n} w_{n}^{i}} (15)$

步骤8 用收敛性较小的权重值来更新相对较大的权重值,从而获取新的样本。改变rj(锚节点的位置和距锚节点的跳数)的值,重复以上的步骤6-步骤8至结束。rj值的个数决定着定位的精度。

步骤9 输出蚂蚁t+1时刻的位置坐标:

$(X_{i (t)}, Y_{i (t)}) = (\sum_{i}^{n} x_{i (t)} \bar{w_{n}^{i}}, \sum_{i}^{n} y_{i (t)} \bar{w_{n}^{i}}) (16)$

4 实验结果与分析

为了检查算法的有效性,以MATLAB7.1为工具进行仿真实验,并与Mixture MCL算法进行性能分析和比较。

在一个无障碍200m×200m的矩形区域随机部署100个节点,节点有测距能力和判断某个节点是否在通信范围内的能力,锚节点是固定的,未知节点是移动的。

设蚂蚁的样本数量为N,依据样本之间的最大和最小距离,r=0.5+2dmin+0.64× (dmin – dmax)。α=1,β=1。τij(0)=0,转移概率P(0)=0.6,所有节点的传输半径为R=10,节点的移动速度v=R,其中锚节点的数量为50个。

图1描述了锚节点对定位误差的影响,并与文献[11]中Mixture MCL进行比较。由图可知锚节点的数量越多,定位误差越小,锚节点数量越多,布置的成本也相应地增加,但因定位时可以收到较多的锚节点信息来过滤不可能的样本,所以降低了定位误差。在锚节点所占比例较低的时候,两种算法的定位误差较大,随着锚节点比例的增加,整个曲线趋近平稳,由于Mixture MCL收集节点的信息只是在其通信半径和其邻居通信半径内锚节点的信息,不在半径范围内,很难获取更多的信息,而AC-MCL算法通过分布式概率和转移概率的引入,可以更好地限定采样范围,获得更多的节点信息,提高样本的质量,使得定位的误差更小。

图2为节点的移动速度与节点定位误差之间的关系,在节点移动的过程中,节点的平均定位误差不断减小,但随着速度的增大,样本的退化加大,定位误差变大,MCL算法由于采样区域的范围较大,节点的定位精度较低,Mixture MCL利用构建的移动模型进行运动预测、位置过滤来缩小节点的定位区域,因此节点的定位精度可以提高。AC-MCL算法通过分布式概率和转移概率来增强样本的过滤条件,并同时结合一定的移动模型,能更好地确定节点的定位区域,使节点的定位精度进一步提高。

5 结语

随着无线传感器网络的研究和应用的深入发展,其优势日益突出,而作为重要的共性支撑技术之一的节点定位问题也更为显著。本文针对蚁群算法存在的优缺点,在蚁群算法的基础上,利用蚁群算法的分布式概率和转移概率并借助一定的移动模型,结合蒙特卡罗思想,以及目标函数来确定节点可能存在的问题,仿真实验结果验证了算法的有效性,与Mixture MCL算法相比可知,在相同的条件下,该算法定位的精度更高,稳定性更好,可以为无线传感器网络的实际应用提供参考。

参考文献

[1]Tilak S,Abu-Ghazaleh N B,Heinzelman W.Ataxonomy of wireless micro-sensor network models[J].Mobile Computing and Communica-tions Review,2002,6(2):1-8.

[2]Cullar D,Estrin D,Strvastava M.Overview of sensor network[J].Computer,2004,37(8):41-49.

[3]Bu Lu Su N,He Dem Ann J,Estr In D.GPS-less low cost outdoor lo-calization for very small devices[C]//Proc Of IEEE Personal Commu-nications2000,7(5):28-34.

[4]Het,Huang C D,Blum B M.Range-free localization schemes in large scale sensor networks[C]//Proc of the9th Annual Interna-tional Con-ference on Mobile Computing and Networking(Mob Com),San Die-go,California,USA:ACM Press,2003:81-95.

[5]Nicolescu D.Ad Hoc Positioning Systems[C]//Proc of IEEE GLO-BECOM’01.[S.1.]:IEEE Press,2001.

[6]Bahl P.RADAR:An In-building RF-based User Location and Tracking System[C]//Proc of IEEE INFOCOM’00.[S.1.]:IEEE Press,2000.

[7]熊小华,等.无线传感器网络节点定位算法的研究综述[J].机电工程,2009,26(2):14-17.

[8]Dorigo M,Maniezzn V,Colorni A.The ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics Pact B,199626(1):29-41.

[9]Lee H,Dong H,Aghajan H.Robot-assisted localization techniques for wireless image sensor networks[C]//IEEE Conf.on Sensor,Mesh,and Ad Hoc Communications and Networks(SECON),2006.

[10]Dil B,Dulman S,Havinga P J M.Range Based Localization in Mobile Sensor Networks[J].Lecture Notes in Computer Science,2006,3868(2):164-179.

无线传感器网络节点定位研究第6篇

本文提出了一种基于RSSI测距技术的DV-Hop定位算法。该算法有效利用每跳的统计信息并结合RSSI测距技术,在不增加传感器节点的硬件开销的基础上有效提高定位精度和扩大定位范围。实验表明了提出的方法在不同的节点比例和节点数的情况下,定位误差和定位范围等性能与传统的定位算法相比有明显的提高,是一种有效的方法。

1 基于DV-Hop节点定位

NiculescuD等人提出了DV-Hop算法,该算法依据WSNs中节点平均每跳距离和到锚节点间的跳数乘积估计未知节点到锚节点之间的距离,然后利用极大似然估计法计算未知节点的坐标。DV-Hop算法的定位过程由三个阶段构成。DV-Hop定位算法可以分为三个步骤。第一步每个锚节点依据记录的WSNs中所有锚节点的坐标值和相距跳数值,根据如下公式:

计算平均每跳距离。

第二步,锚节点依据第一步计算得到的每跳平均距离向WSNs做一次广播,其余未知节点记录所接收到的第一个每跳平均距离,然后转发给其邻居节点。并利用公式Distancei=Hopsi×Hopsizei,把平均每跳距离与跳数相乘,从而估算出与锚节点之间的距离。

第三步,当未知节点获得与三个以上的锚节点的距离后,利用三边测量最大似然法,实现自身定位。

2 本文提出的自定位算法

算法首先锚节点发射无线信号,在其通信半径内的其余未知节点接收锚节点信号,根据接收到的信号强弱分析得到距锚节点的距离。根据信号衰减模型,距离锚节点的距离越远,信号的衰减越大,未知节点接收到的信号越弱。而距离锚节点越近的未知节点,其接收的信号越强。因此,信号强度与节点间的距离存在一种如下映射关系。

设R表示未知节点收到锚节点的信号强度为,依据一次线性模型,D軒=A+BR,计算该未知节点距锚节点的距离,记为D軒。系数A,B可由最小二乘法求得。

设有的N个观察值D1,…,Dn,R的N个观察值R1,…,Rn,得到理论曲线D軒=F(R),然后使偏差平方和为最小。

无线传感器节点随机部署在应用区域内,传感器节点一般而言是固定不动。无线传感器网络具有动态的网络拓扑结构且传感器节点的通信半径固定的。采用DV-Hop定位算法时,首先计算最小跳数和平均每跳距离,然后把乘积作为距锚节点距离的估算,最后依据估算值进行三边测量。然而,对于传感器节点间实际距离与估算距离之间存在计算误差,这也是DV-Hop算法主要的定位误差来源,同时统计得到的跳数信息并没有得到充分利用。本文针对以上问题对DV-Hop算法进行改进,基于RSSI测量技术,并有效利用统计得到的跳数信息,以便降低节点间实际距离与估算距离之间的计算误差,提高定位精度和扩大定位范围。然后根据公式(2)对于不同的锚节点求解Hop-Size的平均值:

其中,n表示锚节点数,Hop-Sizei可由公式(1)求得。最后,其余未知节点根据到信标节点的一跳距离和跳数信息求得通信距离,公式如下:

在第三步中,许多二维空间定位的模型主要依据锚节点信息进行估算。设(x,y)是源节点坐标,(xi,yi)表示第i个锚节点的坐标,di表示未知节点与第i个锚节点的距离,可由公式求得:

在DV-Hop算法中,预测物理通信距离是依据锚节点位置,采用三边测量推算估计得到最终定位信息的。在本文提出的改进型DV-Hop定位算法中,不再采用三边测量法最大似然法,而采用二维空间定位算法[6]。

基于此,本文采用一种最小平方的方法,建立一种对于启发节点高性能的预测机制[7]。

根据公式(3)和(4),可以得到如公式(5)所示关系。

其中,Ei=Xi2+Yi2,K=x2+y2。

设Zc=[x,y,K]T,则有公式(6)和(7)。

根据公式(5)可以得到如公式(8)所示关系。

依据最小平方法和公式(8),可以得到如公式(9)所示关系。

然后,对于未知节点的位置,(x,y)表示如公式(10)所示。

3 实验结果与分析

本文实验平台建立在MATLAB7.0上,对本文提出的方法进行仿真实验并进行分析。在仿真实验型中,假设一个二维WSNs中有N个节点,它们分布于一块L*L的正方形区域内,无障碍或干扰,其中锚节点坐标已知。假设节点的通信模型是以自身为中心的圆,通信半径用R表示;锚节点与未知节点的通信能力相同,通信半径均为R;节点具有对称的通信能力,发送和接收能力相同。图1给出了DV-Hop算法和本文提出的算法在不同锚节点数量的相对定位误差与锚节点数的关系。由图1可知,本文提出的改进型算法与原始的DV-Hop算法相比在定位上取得了较好的性能。定位误差随着锚节点的增加显著降低。在锚节点数比例相同的情况下,改进型DV-Hop算法在相同WSNs通信环境下定位误差明显低于原始的DV-Hop算法。

图2改表示的是本文提出的算法分别在传感器节点随机部署和统一部署两种情况下的定位误差的变化趋势。从图4可以看出,改进型DV-Hop算法能够有效地降低定位误差,扩大定位覆盖范围。例如,当传感器节点数为50时,定位覆盖范围已经达到了100%。通过锚节点,有效地利用统计得到的跳数信息以及采用RSSI测距技术,定位精度更高。表明采用该改进型DV-Hop定位算法后,WSNs可以应用在对定位精度和范围要求很高的场景中。另外当锚节点统一部署时,定位精度和范围明显高于随机部署,因此,为了保证高精度定位和大范围的定位,可以在构建WSNs之前,先对锚节点进行统一高效的部署。

4 结束语

本文提出了一种适用于无线传感网的基于RSSI的DV-Hop定位算法。该算法有效利用每跳的统计信息并结合RSSI测距技术,在不增加传感器节点的硬件开销的基础上有效提高定位精度和扩大定位范围。通过仿实际验,验证了在定位误差方面的有效性,表明该算法是一种高效且准确的定位算法。

参考文献

[1]Niculescu D,Nath B.Ad hoc positioning system(APS)using AOA[J].Proc 22nd Annual Joint Conf of the IEEE Computer andCommunications Societies(INFOCOM'2003),2003(3):1734-1743.

[2]李海涵,张丕状.水下传感器网络节点定位信号设计[J].传感器与微系统,2010(1).

[3]汪汤,黄刘生,肖明军,等.一种基于RSSI校验的无线传感器网络节点定位算法[J].小型微型计算机系统,2009,30(1).

[4]廖先林,张志伟,门云会,等.传感器网络定位扩散机制中梯度生成算法的研究[J].小型微型计算机系统,2002,8(10).

浅析移动IP节点技术第7篇

关键词：移动,IP,节点技术

1 传统网络节点的不足

计算机技术是信息科技研究的主要对象, 计算机技术发展也标志着信息时代的到来。互联网推广应用初期, 为企业及个人用户提供了虚拟操作平台, 在数据通信及共享资源传输上实现了突破。但计算机技术日趋成熟之后, 传统网络中使用的节点技术显得相对落后。主要表现:

(1) 固定性。所谓固定性, 具体是指传统网络使用的节点固定, 只限于某个区域的互联网使用, 而无法跟随用户位置的变化而正常提供网络服务。如:用户使用笔记本或台式计算机在某地登录互联网, 当笔记本转移到其它地区后则无法正常登录, 网络节点技术的这种固定性缺陷限制了网络的使用范围。

(2) 滞后性。旧网络虽然为用户提供的虚拟操作平台, 但相对于成倍增长的计算机用户, 其整改网络漫游服务的质量相对滞后。一方面, 网络用户增加对节点连接的要求更高, 旧网络显然无法满足这一要求;另一方面, 应用虚拟网传输共享资源时, 固定节点容易受到外界干扰, 影响了资源传输的效率。

2 移动IP的关键技术

从计算机应用原理来说, 移动IP技术就是让计算机在互联网及局域网中不受任何限制的即时漫游, 也称移动计算机技术。移动IP技术是移动节点 (计算机/服务器/网段等) 以固定的网络IP地址, 实现跨越不同网段的漫游功能, 并保证了基于网络IP的网络权限在漫游过程中不发生任何改变, 如图1。移动IP的关键技术如下:

(1) 代理搜索。当节点设备转移到另外一个地点, 如:台式计算机、笔记本等, 需要重新搜索新地区的互联网, 才能登陆到网络使用资源。移动IP技术具备代理搜索功能, 主要是计算节点用来判断自己是否处于漫游状态。

(2) 转交地址。在异地登陆互联网需要使用新的地址, 由于这种地址并非用户的常用地点, 只需搜寻某一个临时地址即可。移动IP中的转交地址技术, 可以使移动节点移动到外网时从外代理处得到的临时地址。

(3) 登录。访问某一网站必须事先登陆, 才能正常享有网络的服务功能。移动IP技术设置了登陆模块, 应用于移动节点到达外网时进行一系列认证、注册、建立隧道的过程, 方便了互联网络服务体系的管理。

(4) 隧道。建立双向隧道是移动IP技术的一大改革, 此项技术是家代理与外代理之间临时建立的双向数据通道。当用户在家代理隧道上无法登陆网络时, 可选择外代理服务器登陆, 保证了正常的网络使用效果。

3 移动IP技术应用的管理

为了让移动IP技术发挥最高的服务作用, 网络运营商及用户还需注意其它方面的管理, 创造相对稳定的网络使用环境。具体情况:首先, 运营商应在不同区域内为用户提供节点接口, 让笔记本、掌上电脑等硬件设备能与局域网相互连接, 如图2;其次, 用户要时刻关注节点的功能状态, 防止异常故障影响到网络运行的效率。

4 结语

积极推广移动IP技术, 可以满足用户在不同时间、不同地点对网络服务的要求, 稳定了互联网数据传输的整个过程。选用移动IP技术, 要注意节点设备的更新与管理, 保持移动网络的正常运行。

参考文献

[1]徐华中, 郑诚.移动IP隧道技术实现的研究[J].中国水运 (下半月) , 2008 (4)

[2]赵凤兰.IP Phone的概念原理及特点[J].内蒙古科技与经济, 2000 (5)

移动节点定位第8篇

定位技术是WSN的核心技术之一。WSN的定位算法,可以根据实际应用中所需定位机制的不同,分成基于测距算法( Range-based) 和无需测距算法( Range-free) 两大类。其中,基于测距的定位机制需要利用未知节点至信标点之间的距离或角度信息,采用三角测量法、三边测量法或最大似然估计法,计算未知节点位置。而无需测距的定位机制则不需要预先知道未知节点至信标点之间的距离和角度信息,只需要通过网络中节点间邻近关系或节点的连通性等信息实现节点定位。如质心、APIT( Approximate Point-in -triangulation Test) 定位、DV -Hop ( Distance Vector-Hop) 定位、Amorphous和MSD-MAP。由于无线传感器网络硬件设备的限制,无需测距的定位算法得到广大学者的关注。

DV-Hop算法的“无需测距定位法”是研究人员关注较多的算法之一。学者们针对其定位精度较低的缺点,提出了许多改进方法,但尚未达到理想效果。文献[1]采用的算法,虽然具有较高的定位精度,但通信开销和计算量都较大。如果将RSSI引入DV-Hop算法,虽然可以提高定位精度,但增加了节点的硬件开销。文献[2]采用遗传算法和模拟退火算法对DV-Hop算法进行改进,虽然降低了定位误差,但是算法复杂,能源消耗多。文献[3]提出采用粒子群优化的方法,但是该改进算法需要测量信号的方向,从而需要添加相应硬件设备,增加了节点的硬件成本。文献[4]先获得网络中信标节点之间的平均跳距,再计算每个信标节点的平均跳距,进而获得这两个平均跳距之间的误差,从而修正全网的平均跳距。文献[5]针对DV-Hop定位算法在不规则网络中的定位精度进行改进,考虑了未知节点与信标节点之间的路径可能与信标节点间的路径重合这一特性,对平均跳距进行修正,在一定程度上提高了定位精度,但是由于考虑的因素较少,所以定位精度提高的不是太明显。

本文在对DV-Hop定位算法进行研究分析的基础上,通过总结大量改进算法的优缺点之后,提出了基于邻居节点相似度的DV-Hop改进算法。通过仿真分析,结果表明: 算法可在无需增加节点硬件以及通信开销的基础上,提高节点的定位精度。

1 DV-Hop定位算法

1. 1 DV-Hop算法描述

DV-Hop算法的核心思想为将未知节点与信标节点之间的距离用信标节点间平均跳距和未知节点与信标节点之间的最小跳数的乘积来表示。然后通过三边测量法或者最大似然估计法求出未知节点的坐标。定位的过程主要分为以下3 个阶段[6]:

1) 测量未知节点与信标节点之间的最少跳数。采用经典的距离交换协议,使监测区域中所有未知节点获取与信标节点间的跳数信息。

2) 计算未知节点到信标节点的估计距离。每个信标节点获得自身到其他信标节点的跳数以及其他信标节点的坐标后,计算信标节点i平均每跳的距离,称为平均跳距di,计算公式为

式中: xi,yi为信标节点i的坐标; hij为信标节点i和j之间的最少跳数。

然后,信标节点将计算获得的平均跳距di以广播的形式通知网络中的其他节点。

3) 估计未知节点位置。未知节点利用到各个信标节点之间的最少跳数和平均跳距,求自身的估计坐标。假设( x ,y ) 是未知节点N的坐标,( xi,yi) 是第i个信标节点的坐标。未知节点N与信标节点i之间的估计距离为di,并且将未知节点N和网络中所有信标节点的估计距离表达式整合成方程组,则有

将上述n个二元二次方程,转化为AX = b的形式。其中

方程AX = b用标准最小二乘法求解得位置节点坐标为

1. 2 DV - Hop算法的不足

1) DV - Hop算法中,平均跳距是通过信标节点之间的最小跳数和信标节点之间的距离获得。实际中,信标节点之间的距离为直线距离,最小跳数的每跳不一定在同一直线上,且每跳的跳距是不同的。如图1 所示。DV - Hop算法将信标节点之间的距离和最小跳数之商作为平均跳距。这一平均跳距会由于网络中的节点稀疏程度和连通度的不同而出现不同程度的误差。

2) 用信标节点间的平均跳距与未知节点和信标节点之间的最小跳数的乘积,代替未知节点与信标节点之间的实际距离。其中未知节点和信标节点之间的最小跳数的通信路径并非呈直线分布,且节点间跳距不同。所以通过此步骤获得距离也会引入误差。

2 DV - Hop改进定位算法

2. 1 相关定义

1) 邻居节点: 在无线传感器网络中,节点都有一定的通信半径,处于此范围之内的节点称为该节点的邻居节点。

2) 邻居节点相似度: 无线传感器网络中的节点可以通过信息交换,获取自身的邻居节点ID号列表,并且和其他节点的邻居节点列表作比较,节点间的邻居节点列表中的节点ID号相同的数目越大,邻居节点的相似度越大,其值为

式中: δ 可以改变节点间邻居列表中ID号相同的节点数目对邻居节点相似度的影响; Numcom指的是节点间邻居列表中ID号相同的节点数目; Numi和Numj分别指未知节点i和j的邻居节点数目。

2. 2 改进算法要点

2. 2. 1 单跳节点处理

无线传感器网络中可以通过单跳直接和信标节点通信的未知节点。在DV - Hop中全部采用网络中邻近信标节点的平均跳距作为距离,实际中,网络中较多的未知节点可以和信标节点直接通信,如图2 所示。未知节点和信标节点的距离也不尽相同。使用平均跳距作为这些节点与信标节点的距离,从而导致信标节点的邻居节点区分度单一,而引入较大的误差。所以,本论文在此处引入修正方法。

本文提出邻居节点相似度的概念,通过网络信息交换获取节点的邻居节点列表后,根据式( 7) 可以求出节点i与节点j的邻居节点相似度 εij。

对单跳节点进行修正后的距离为

2. 2. 2 多跳节点处理

余弦定理: 已知三角形两边之长及其夹角,可以求得第三边的长度。

根据余弦定理,在节点ABC组成的三角形中,如图3所示。本文假设知道AB和BC的长度,以及∠ABC的度数 θ 。就可以根据余弦定理,求出AC的长度,这样就将节点A到节点C之间的折线通信路径转化为求直线AC的长,表达式为

未知节点间单跳跳距的修正方法,采用单跳节点处理方式,根据未知节点ABC的邻居节点列表和式( 7) 、式( 8) 求出节点A到节点B和节点B到节点C的距离。

节点间的距离越近则邻居节点的相似度越高,而节点距离越远,邻居节点的相似度越低。所以,本文将通过节点间邻居节点的相似度来调整夹角θ的度数。如图4所示,节点i和节点j恰好处于彼此的通信半径之外时,节点k通过多跳模式传递信息,当节点k距离节点i和节点j距离最远时,此时∠ikj的度数最小,且近似等于π/3。

如图5 所示,节点i,j恰好位于各自通信半径边缘处,且节点k位于此交集处。此时,节点i,k,j组成一条直线,通信夹角最大,近似为 π。节点i,j的距离最远。

则节点间的通信夹角取值范围是[π/3,π]。根据邻居节点的相似度,可以求得网络通信链路中的通信夹角θ为

式中: εij通过式( 7) 获得; γ 为邻居节点相似度所占权重值,改变其大小可以改变 γ 在通信夹角中的影响程度,γ值大小根据具体网络连通情况和节点的疏密程度而定。

无线传感器网络中的任意三个通信节点ABC,如图3所示。通过式( 8) 获得AB和BC的长度,再通过式( 10) 获取AB和BC的夹角。根据余弦定理,带入式( 9) ,方可将实际中的折线通信距离转化为求直线距离,减少了由于折线通信带来的误差。

2. 3 改进算法实现

1) 计算全网节点间的最小跳数

信标节点向邻居节点以广播的形式发送一个信标,包括位置信息字段和邻居节点列表字段。其中位置信息字段包括自身坐标、ID号和跳数值,跳数值初始化为0。邻居节点列表字段包括通信半径内的所有节点的ID和邻居节点的数目,初始化为NULL。

节点收到其他节点发来的信息后,位置信息字段更新坐标和ID号,同时跳数值加1; 邻居节点列表字段将接收到的位置信息中的ID号取出,存入邻居节点列表中,邻居节点数目加1,并继续向其他邻居节点广播,通过这种泛洪方式向整个网络传播数据。若节点收到来自同一个节点的多个信息,则比较其跳数值,只保留最小跳数值的信息,这样就保证了所得到的跳数值是到网络中所有节点的最短路径。

经过此阶段,网络中的所有节点都获得各个信标节点的坐标,以及邻近节点的ID号和个数。以及它到各节点的最小跳数。

2) 计算未知节点和信标节点的实际跳距

每个信标节点根据第一步中获取的到其他信标节点的位置信息和跳数,利用式( 1) 估计平均跳距di。

信标节点的邻居节点中的未知节点根据式( 7) 求出未知节点和信标节点的相似度 εi。并且将 εi带入到式( 8) 中修正di为d'i。

通过多跳间接和信标节点通信未知节点,距离修正处理如下:

对于和信标节点通信的节点采用两跳通信的未知节点。首先,采用式( 7) 和式( 8) 修正未知节点i与信标节点的前驱节点j之间的单跳距离d'ij,然后结合信标节点的前驱节点j和信标节点B( 即信标节点的邻居节点) 之间的修正距离d'j B。再根据式( 10) 求出未知节点i和信标节点B通过节点j通信的夹角 θi B,带入到式( 9) 中得到两跳通信修正距离d'i B。表达式为

对于通过三跳或三跳以上和信标节点通信的节点采用和两跳距离修正同样的方法,先求出两跳路径后,再相互结合,直到获取源节点到信标节点距离。通过此修正方法,使全网中的未知节点获得到各个信标节点的修正距离。

3) 计算未知节点坐标

将2) 获取的未知节点到各信标节点的修正距离,代入到式( 2) 中,使用最小二乘法,求得未知节点的坐标。

3 仿真结果极其分析

检测区的范围是100 m × 100 m的正方形区域,随机播撒100 个节点。网络中节点的通信半径为R 。δ 和 γ 根据监测区域节点分布的疏密程度和连通度分别设置为0. 9和1。未知节点坐标与实际坐标之间的相对定位误差表示为

式中: erri代表每个未知节点的误差; UN代表未知节点的个数。

通过对DV - Hop、参考文献[5]算法、参考文献[7]算法、本文算法进行仿真,并对实验结果进行比较。从而证明了本文算法的有效性与可行性,图6 ~ 图9 给出了网络中的节点通信半径不同时,随着网络中信标节点比例变化,三种算法的定位误差比较结果。

从图中可以看出在相同的通信半径下,本文改进算法和文献[5]、文献[7]的算法的定位误差距均低于DV - Hop定位算法。通信半径为30 m时,本文的改进算法比DV - Hop定位算法在相对定位误差上降低了33. 34% ~ 35. 35% 。比文献[5]、文献[7]定位算法降低了10. 06% ~ 21. 41% 。且各个算法的定位误差随着信标节点比例的增加,定位误差都不断减小,且趋于平稳。当网络中的信标节点数目一定时,随着节点的通信半径减小,节点的定位误差也随之减小。如当信标节点的比例为10% ,节点的通信半径分别为30 m时,DV - Hop定位算法获得的未知节点的相对定位误差为92. 22%[5],文献[5]定位算法获得结果为76. 26% ,文献[7]定位算法获得结果为78. 14% ,本文改进定位算法结果为58. 48% ; 在不同的通信半经中,信标节点比例小于10% 时,改进算法较DV - Hop定位算法的定位误差降低了约32% ~ 35% ,且与文献[5]和文献[7]的定位算法获得的定位误差降低了约18% ~20% 。

算法复杂度分析: 文献[1]将RSSI引入DV - Hop算法,在复杂度上增加了节点关于RSSI强度值计算的相关部分,并且算法需要额外的硬件成本。而文献[2]和文献[3]虽然采用了经典的遗传算法、模拟退火算法和粒子群优化的方法对DV - Hop算法进行改进,这样极大地增加了算法的复杂度,同时能源消耗多。同时文献[3]还需要添加硬件设备,增加了硬件成本。文献[5]主要针对未知节点与信标节点之间的路径可能与信标节点间的路径重合这一点进行修正,一定程度上提高定位精度,算法复杂度较低,但是由于考虑的因素较少,所以定位精度提高的不是太明显。本文算法通过邻居节点列表的比较,获取邻居节点相似度,并在此基础上对节点的跳距进行修正,在此处略加大算法复杂度。但是节点定位精度却得到较大的提高。

综上所述,本文的改进定位算法,无论是相当于传统的DV - Hop定位算法还是文献[5]的定位算法,均在节点的相对定位误差上都有了较大幅度的降低。

4 结论

本文针对DV - Hop定位算法在单跳通信中,处理信标节点的邻居节点距离没有区分度,统一采用平均跳数与单跳之积的形式表示,以及多跳通信中该算法没有考虑折线通信,依然采用同样的方式处理,从而导致该算法的定位精度较低的情况。同时,这一点也是文献[5]没有考虑到的。本文提出了邻居节点相似度的概念,并应用此概念分别对单跳节点( 邻居节点) 的距离进行修正,克服了DV - Hop定位算法在处理单跳节点时,采用同样的距离表示距离信标节点的距离; 在多跳通信中,结合余弦定理将DV - Hop和文献[5]中的折线距离代替实际中的直线距离,转化为求直线距离的运算,同时修正了多跳通信中每一跳的距离。使得本算法在定位过程中增加了节点跳距区分度,克服了DV - Hop定位算法和文献[5]定位算法较单一的计算。由于本算法中的邻居节点相似度综合考虑了网络的连通度和节点的疏密程度等因素,且可根据实际情况作出相应的调整。所以本算法的实际应用价值较高且具有较好的鲁棒性。

无线传感器网络节点定位技术综述第9篇

无线传感器网络(WSN, Wireless Sensor Network)是由部署在监测区域内大量微型传感器节点相互协作构成的一个多跳自组织网络,其目的是协作的感知、采集和处理网络覆盖区域内被监测对象的信息,如温度、湿度、压力、移动物体的速度等,并发送给观察者[1]。WSN具有传感器节点数量大、分布广、网络动态性强、感知数据流大、单个节点成本低廉等特点。WSN技术的出现使人们获得了一种可以持续实时监测环境的新途径,是一种“无处不在”的传感技术,可以广泛应用在环境检测、医疗健康、反恐防灾等场合。

在WSN中,位置信息对传感器网络的监测活动至关重要,确定事件发生的位置或获取消息的节点位置是传感器网络基本的功能之一,对传感器网络的有效性起着关键作用。定位信息除了用于报告事件发生的地点之外,还可用于其他用途。例如,目标实时跟踪——实时监视目标行动路线,预测目标前进的轨迹;协助路由——直接利用节点位置信息建立数据传递的地理路由协议,可以避免信息在整个网络中的扩散,并可实现定向信息查询;网络管理——利用传感器节点传回的位置信息构建网络拓扑结构,并实时统计网络覆盖情况,对节点密度低的区域及时采取必要措施;定点、定时传播——用户可在指定时间将信息传递至特定区域。总之,了解节点的位置信息,可使WSN工作的目的性更强,效率更高。

从1992年AT & T[2] Laboratories Cambridge开发出室内定位系统Active Badge至今,研究者一直致力于这一领域的研究。微软研制的RADAR2[3]系统,是基于IEEE802.11无线局域网标准,可以在楼层内实现节点的定位。加利福尼亚大学构建的AHLos(Ad-Hoc Localization System)[4]系统中,未定位节点根据周围已知位置节点的分布情况,利用迭代算法进行定位。麻省理工大学开发的Cricket系统[5]可以对位于大楼内的移动或静止节点进行定位。在试验环境较为理想的条件下,上述系统能够正常工作并为节点获得定位。但是实际应用中难以避免节点测量存在误差、实际环境(如地形、温度湿度等)对测量值影响的不确定性等问题,导致节点的定位效果大受影响,目前,学术界对无线传感器网络应用于实际环境的研究尚不完善,需提出更健壮、高效的算法,促进无线传感器网络的进一步普及。

1 节点定位的基本原理

无线传感器网络中包含大量传感器节点,通常节点的放置采用随机撒布放置方式,如果依靠人工标定来确定每个节点的位置,其工作量巨大,难以完成。另一种可直接获得节点位置的方法是为每个节点配备全球定位系统(GPS),但由于节点数目众多,考虑到价格、体积、功耗等因素的限制,通常不采取这种方案。一种较合理的方法是为部分节点事先标定好准确位置或为它们配备定位系统(如GPS),这些节点通常称为锚节点。目前节点定位的研究热点集中于如何利用这些锚节点提供的位置信息与节点间的协作,来计算非锚节点的位置。

无线传感器网络定位问题的一般前提假设是:

(1) 网络具有较高的密度;

(2) 网络内每一个节点具有全网唯一的ID;

(3) 在没有特别说明的情况下,所有节点具有相同的最大通信距离;

(4) 在定位过程中,假设节点相对位置不变。

2 节点定位的方法

2.1 无线信号测量方法

节点定位的计算通常需要一些表征几何特征的原始数据,这些信息可以通过对无线信号的某些特征进行测量来获取。以下介绍几种常用的无线信号测量方法。

测量信号到达时间(TOA. Time of Arrival)[6]——已知信号的传播速度,根据传播时间来计算距离,得到的结果精度高,但要求节点保持精确时间同步,对节点硬件和功耗提出了较高要求。

测量不同信号到达时间差(TDOA. Time Difference of Arrival)[7]——由两节点同时发送信号,待定位节点根据两信号的到达时间差来计算距离。这种技术对硬件的要求较高,但是测距误差小。使用TDOA方法发送信号易受干扰,不适合于大规模的传感器网络。

测量接收信号到达角(AOA. Angle of Arrival)[8]——通过天线阵列或多个超声波接收器感知发射节点信号的到达方向,由此获得接收节点和发射节点之间的相对方位或角度。这种技术对接收硬件要求较高。

测量节点的信号强度(RSSI. Received Signal Strength Indicator)[9]——利用信号在传递过程中的衰减特性进行距离估计。已知发射节点的发射信号强度,接收节点根据收到的信号强度,计算出信号的传播损耗,基于理论和经验的信号衰减模型将传输损耗转化为距离。该方法符合低功率、低成本的要求,但信号强度易受环境的影响。

测量节点是否在发射信号的接收范围内[10]——使用已知发射功率的信号,或者使用定向天线改变发射信号方向来检测接收节点是否在信号覆盖区域内,通过覆盖区域的重叠面积计算来确定节点的位置范围。

2.2 节点定位的计算方法

获得了检测量后,利于如下方法得到节点的定位。

三边(多边)计算法:已知平面上(空间上)三(多)点的位置A,B,C,以及D点到A,B,C的距离,利用几何方法可求出D点的坐标。

三角(多角)计算法:已知平面上(空间上)三(多)点的位置A,B,C,以及D点为角顶点,角边的端点为A,B,C的角度,可求出D点的坐标。

极大似然估计法:已知很多节点D的相邻节点坐标以及它们到节点D的距离或方位,使用最小均方差估计方法得到节点D的坐标。

利用范围重叠计算:

(1) 重叠区域质心算法[11,12]:定位算法首先确定包含未知节点的区域,计算这个区域的质心,并将其作为未知节点的位置。

(2) 凸规划算法[13]:将节点的定位问题转化为凸约束优化问题,然后使用半定规划和线性规划方法得到一个全局优化的解决方案。

(3) 跳数距离估算法[14]:计算节点之间的跳数,利用估算或者直接使用节点的通信半径得到平均每跳,再结合跳数估算距离。

(4) 变覆盖范围定位算法[10]:利用移动的锚节点周期性广播其当前位置,未知节点根据这些信息计算其位置(包括ID,位置,时间戳),该算法的理论基础是圆的任意两条不同弦的垂直平分线的交点即为圆的中心。或者通过锚节点的发送功率和定向天线的方向来产生多个覆盖区域。

(5) 模板匹配算法[3]:通过比较数据库中训练模板与接收信号模板实现定位,该方法被称为“指纹识别”,该方法中使用随机概率的方法对信号强度进行建模。

2.3 定位算法的分类

根据不同分类原则,可以将无线传感器网络中的定位算法做如下划分:

(1)集中式计算与分布式计算

集中式计算是指将需要的信息传送到某个中心节点进行定位计算。典型的集中式算法有凸规划[13],质心定位算法[11],MDS-MAP算法[10],APIT算法[12]等。

分布式计算是指依赖节点间的信息交换和协调,由节点自行计算的定位方式,典型的算法有Bounding Box1[15],DV-Hop[14],Robust Position1[16]等。

(2)基于测距技术的定位和无需测距技术的定位

基于测距技术通过得到节点间的距离或角度信息,使用三边测量、三角测量、极大似然估计等方法计算节点位置。无需测距定位,不需要距离和角度信息,仅根据网络连通范围等信息实现定位。典型的基于测距定位有AHLos,不需要测距的算法有质心定位算法,MDS-MAP算法,APIT算法等。

(3)绝对定位与相对定位

绝对定位的定位结果是一个标准的坐标位置,如经纬度。目前大部分WSN系统采用这种表示方式。相对定位通常以网络中部分节点为参考,建立整个网络的相对坐标系统。典型的相对定位算法有SPA[11](self-position algorithm)。而MDS-MAP定位算法可以根据网络配置的不同分别实现两种定位。

(4)细粒度定位(fine-grained)和粗粒度(coarse-grained)定位

根据接收信号强弱、时间、方向和信号模式匹配等完成定位的称为“细”,根据节点接近度进行定位的称为“粗”。高精度的定位技术往往要求较高的器件水平和能耗,在有些场合下,为了满足传感器网络节点的低成本、低能耗的要求,需要根据任务和需求选择适度“粗”的算法。细粒度的典型算法有质心算法、Active Badge[2]、凸规划等。粗粒度的典型算法有跳数距离估算法等。

(5)循环求精和一次计算

大部分定位算法都采用一次计算得到节点的位置。循环求精是在起始阶段得到节点位置的粗略估计,在循环阶段每个节点向其邻居节点广播它的位置估计,并根据从邻居节点接收的位置信息和节点间的测距结果重新计算自身位置,直至两次计算得到的位置估值之差小于一定的域值。典型的循环求精算法有Cooperative ranging[17]和Two-Phase Positioning[16]。

3 性能方法的评价标准

目前,文献中对WSN定位算法评价标准的研究尚不完善,以下介绍几种常用的评价标准。

(1)定位精度:

一般用误差值与节点的无线电测距射程的比例表示,例如定位精度为20%表示误差是射程范围的20%。

(2)锚节点的密度:

因为锚节点通常依赖人工部署或安装GPS等定位设备,使用成本较高。锚节点的使用数量是限制WSN规模、影响WSN成本的重要指标之一。

(3)功耗:

由于传感器节点的能量有限,控制功耗是WSN的一项重要工作。因此定位算法所需要的计算复杂度、时间复杂度、通信开销、存储开销等成为影响功耗的重要因素。

(4)规模:

不同的定位系统或算法所能定位目标的数量是一个重要的评价指标。节点数量增加带来了网络通信干扰、结构复杂度和通信复杂度的增加。规模的扩大对算法的适应性提出了考验。

(5)容错性和适应性:

实际应用场合存在着多种不确定性,例如多径传播、通信盲点,节点能量耗尽、损坏等。这要求定位系统和算法有较强的容错性和适应能力,能自动调整,减小不确定因素带来的错误和误差。