2. 西南民族大学 计算机科学与技术学院, 成都 610041
2. School of Computer Science and Technology, Southwest University for Nationalities, Chengdu Sichuan 610041, China
位置感知已经成为许多无线传感器网络(Wireless Sensor Network,WSN)应用的重要方面。这种应用包括位置跟踪、映射、位置辅助导航等。由于节点布置成本和能量消耗的限制,不是所有节点都能获得可靠的定位信息。因此,对WSN来说,定位系统通常采用较少的节点,这些节点都知道自己的坐标,把这些节点称为锚节点或信标节点。锚节点可以把自己的坐标信息告知给网络中的其他普通节点(也称为未知节点),从而帮助这些普通节点估计出自己的位置。
近些年来,针对WSN提出了许多定位算法[1-4]。通常,可以把这些定位算法分为两大类:一方面是基于测距的算法,通过测量节点间点到点的距离或者角度信息,使用三边测量法、三角测量法或最大似然估计法计算出节点位置。这种技术需要专用硬件来估计锚节点和未知节点之间的距离,从而可能导致非常昂贵的成本和代价。另一方面是无需测距的定位算法,即无需距离和角度信息,仅根据网络连通性等信息实现定位。这种技术不要求锚节点通过消息传递来告知其他节点关于自己的位置。在完成了与锚节点的距离估计过程之后,普通节点可以通过多种方法确定出自己的位置,如多点测量法和三角测量法。
自从无线Ad Hoc网络出现以来,定位就成为人们广泛研究的领域,关于静止和移动无线传感器网络的定位,提出了众多的算法。文献[5]基于序列蒙特卡罗(Sequential Monte Carlo,SMC)方法针对移动无线传感器网络提出了一种蒙特卡罗定位(Monte Carlo Localization,MCL)算法。文献[6]提出了一种基于测距的MCL,这种算法将基于测距和无需测距的位置信息结合起来减小估计误差。Baggio等[1]通过减少样本预测区域来提高蒙特卡罗定位算法的性能,通常把这种算法称之为蒙特卡罗Baggio(Monte Carlo Baggio,MCB)。它可以更快获得有效样本,并减少必要的迭代次数来完成样本集合,使得计算开销大大降低;但算法取决于特定的参数,如固定不变的无线传输距离。文献[7]提出了一种动态更新并利用有效成本参考信息的定位算法,而且对于普通节点接收不到充分的锚节点信息提出了灵活的解决方案。文献[8]基于简单广播机制,提出了一种采用传统的距离向量交换来保证网络中的全部节点获得与锚节点的跳距,每个节点维持一个路由表,并采用信号强度测量和逐跳传播来估计出与邻居节点间的距离。通常把这种算法称之为距离向量-跳距(Distance Vector Hop,DV-Hop)算法,它是介于全球定位系统(Global Positioning System,GPS)和距离向量路由(Distance Vector Routing,DVR)之间的一种混合算法,是一种非常经典的算法;但DV-Hop算法存在着信息流量大、节点能耗大、定位不精确等问题。文献[9]提出了一种基于移动代理的三维DV-Hop算法,将无需测距的DV-Hop算法拓展到三维空间,并在通信量、定位精度方面进行了相关改进。算法能对三维环境中的传感器节点进行有效定位,信标节点的密度和通信半径对定位误差和覆盖率的影响较小,定位精度和覆盖率相对于其他算法有明显提高。文献[10]针对DV-Hop定位算法的缺陷,提出修正平均每跳距离和估计距离来提高定位精度的改进算法,并在三种不同的节点分布环境下进行了仿真。实验结果表明,改进后的算法定位精度得到了一定的提高。文献[11] 针对三维无线传感器网络采用无需测距的DV-Hop定位算法时,由于三维空间中节点分布复杂、测距误差增大、定位准确度降低等,提出采用最小均方差来估计未知节点与已知节点之间的距离,定位结果采用粒子群算法优化,以距离误差因子加权均方误差作目标函数,并采用凹函数递减策略来提高定位准确度;但这种定位算法明显存在计算复杂度高和收敛时间变长等不足。文献[12]针对无线传感器与执行器网络(Wireless Sensor and Actor Network,WSAN)的传感器节点定位问题,提出了一种基于虚拟力的无线传感器与执行器网络测距定位算法,使用移动的执行器节点替代传统无线传感器网络定位算法中的锚节点,并将虚拟力模型引入基于信号到达时间的定位算法。该算法在利用虚拟力驱动执行器节点逼近提出定位请求的传感器节点的同时,根据信号传输时间计算节点间的距离完成节点定位。
本文针对以上算法的不足,提出了一种基于改进的洪泛广播机制和粒子滤波的定位算法。首先,采用改进的洪泛广播机制,从离它最近的锚节点得到的有效平均跳距来计算出它到它的所有邻居节点的距离。这样能够有效地抑制冗余广播和减少与节点定位相关的消息开销,从而并降低整个WSN的通信成本。而且针对跳距测量,采用了一种差分误差校正算法,以减少平均跳距中由于多跳累积的测量误差,从而实现高精度定位。其次,采用粒子滤波的思想,而且基于虚拟锚节点的位置,能够使得普通节点和其邻居节点积极协作,利用传感器信息来减少预测区域,得到更有效的粒子预测区域,从而进一步减小对普通节点位置的估计误差。仿真结果表明,本文提出的定位算法能够以相对较低的通信开销有效地实现较高精度的定位性能。
1 算法的提出为简化起见,算法考虑二维情形,可以很容易扩展到三维情形。
1.1 简单洪泛广播机制的工作原理简单洪泛广播机制的工作原理是:一方面,每个锚节点都在整个网络广播一个信标消息。信标消息包含锚节点的位置和一个初始值为0的跳数。每个接收节点与接收到来自所有信标消息的每一个锚节点保持最小跳数值,那些来自于更高跳数值的锚节点信标消息将被忽略和丢弃。另一方面,把有效的信标消息用一个递增后的跳数逐跳进行转发。这样,网络中全部节点就可以找到它们关于每个锚节点的最小跳数值。然而,这种简单的洪泛广播机制会导致过多的消息开销,从而增大通信成本,降低网络寿命。因为这种跳数定位算法在计算未知节点与每个信标节点的最小跳数时,需要两个独立的阶段:1)跳数累加;2)平均跳距计算或称为修正过程。
为此,本文提出改进的洪泛广播机制,算法将跳数累加和修正过程两个阶段结合起来,以减少信息传输。当有效跳距在洪泛过程中进行计算时,跳数同时在网络中的所有节点进行广播。这样就能够有效地减少发送消息的数量,减少用于计算节点位置花费的时间,从而降低网络的能量消耗,延长网络寿命。
1.2 改进的洪泛广播机制和跳距估计一旦一个锚节点接收到来自另一个锚节点的跳数值,它就估计出一跳的平均距离即跳距,这个跳距将被作为一个修正因子发送到整个网络。普通节点在接收到跳距后,就用跳数乘以它,来得到它们与锚节点之间实际距离的估计值。锚节点i和j之间的平均跳距计算如下:
${{H}_{i,j}}=\frac{\sum\limits_{i\ne j}{\sqrt{{{({{x}_{i}}-{{x}_{j}})}^{2}}+{{({{y}_{i}}-{{y}_{j}})}^{2}}}}}{\sum\limits_{i\ne j}{{{h}_{i,j}}}}$ | (1) |
其中:(xi,yi)、(xj,yj)分别为锚节点i和j的坐标;hi,j为它们之间的跳数。在得到跳距估计值后,就可以直接估算出锚节点i和j之间的距离:
$d_{est}^{i,j}={{H}_{i,j}}\times {{h}_{i,j}}$ | (2) |
另一方面,锚节点i和j之间的实际距离dtruei,j由式(3)给出:
$d_{true}^{i,j}=\sqrt{{{({{x}_{i}}-{{x}_{j}})}^{2}}+{{({{y}_{i}}-{{y}_{j}})}^{2}}}$ | (3) |
根据式(2)和(3),就可计算出估计距离和实际距离之间的差ei,j(即估计误差):
${{e}^{i,j}}=d_{est}^{i,j}-d_{true}^{i,j}$ | (4) |
接下来,采用式(4)的差分误差作为修正项用于最初的跳距估计式(1)。锚节点i和j之间的有效平均跳距Heffi,j定义为:
$H_{eff}^{i,j}={{H}_{i,j}}-\frac{{{e}^{i,j}}+{{e}^{i,m}}}{{{h}_{i,j}}+{{h}_{i,m}}}$ | (5) |
其中:hi,m为i和m之间的跳数;m为距离未知位置节点k的第二个最近的锚节点。
当锚节点i和m把它们与节点j之间的平均跳距广播给未知节点k时,相关的跳数值也将同时进行广播,这样就可以减少发送消息的总数量。在得到来自于i和m的消息后,节点k就采用式(4)计算出ei,j和ei,m,随后,就可以采用接收到的信标信息根据式(5)计算出有效平均跳距。基于式(5),未知节点k就可以计算出它与锚节点j之间的有效距离为:
$d_{eff}^{k,j}=H_{\text{e}ff}^{k,j}\times {{h}_{k,j}}$ | (6) |
如果i是距离k最近的锚节点,则能采用Heffi,j来更加准确地估算出k和j之间的距离。基于这个原理,对任何普通节点来说都是可以的。也就是说,一个给定的普通节点,也可以采用从离它最近的锚节点得到的有效平均跳距来计算出它到它的所有邻居节点的距离。
如图 1所示,当采用简单的洪泛方法向邻居节点提供位置信息时,就会出现较大的消息开销。因为一个节点可以接收同一个锚节点的连续信标消息,并且每个节点都会得到一个更小的跳数。这样,这个节点可能需要转发几次。图 1说明了由锚节点A发起的锚节点消息广播。从图 1可见,节点C可以在节点B之前广播A的消息,假设节点D赢得了下一次信道争用,而且节点E和F设置它们的最小跳数为3。这样,有可能节点B与节点E在信道争用时进一步失败,因此节点E在它注意到正确值之前,广播的锚消息就包含错误的最小跳数值。一旦这个顺序改变,来自于每个广播的误差就积累起来。节点E在收到来自于节点B更低的跳数信息后,只需广播另一个锚消息,但那些离锚节点更远的节点可能需要转发送几次来修正累积误差。因此,可以发现位于发送节点传输范围边界的节点有最宽的覆盖范围,可以覆盖其2跳邻居。因此,如果远离发送器的接收器有更高的优先级广播,则可以解决上述冗余问题。
基于上述分析,为了有效地抑制冗余广播和减少与节点定位相关的消息开销,本文对简单的洪泛广播机制进行改进:希望那些远离发送端的节点有更弱的接收信号强度。因此,对每个节点来说,设ISS=Pr-RXT,ISS为信号强度增加值,Pr表示接收信号功率,RXT表示成功解码一个数据包的最小信号功率。每个节点对其锚消息广播延迟的时间为ISS×单位延迟时间,这里单位延迟时间应足够大,以便能够处理MAC层的随机退避;否则,节点C可能由于赢得信道争用而仍然先于节点B广播。
如果节点B在节点A传输范围的边界上,它将在收到来自节点A的一个锚节点消息后立即广播。节点E应当按照同样的规则计算其发送延迟。为了解决循环问题,节点E应当在开始它的发送之前等待一个额外的延迟。通常而言,如果一个节点不是一个锚节点的1跳邻居,则它在转发锚信息之前应当等待一个额外的时间。假设需要广播的全部节点位于一个环内,这个环都由半径分别为α×R和R的两个圆确定,这里α由通过监听所得到的节点密度确定。例如在图 1中,如果有很多节点位于由半径分别为 0.5R和R的两个圆确定的环内,则节点C可能不需要广播。然后用一个Pr值计算额外延迟,这个Pr值希望在0.5R距离内,这样,所有节点只需广播1次。
1.3 粒子滤波定位对于定位,由于移动节点插入的位置不确定,故插入虚拟锚节点,这样就有助于限制定位误差。令(Xi,Yi)为一个虚拟锚节点的坐标,i={1,2,…,M}。这里,选取1跳或2跳邻居节点的中点作为虚拟锚节点的位置,如图 2所示。一个节点可以采用有效平均跳距以及跳距之内的跳数估算出它到一个锚节点和其他普通节点的距离。这些距离可用来限定一个较小的预测区域,然后从这个区域中提取粒子并滤波。如图 2所示,黑色矩形块就表示预测区域,从这个区域提取的粒子代表可能的位置。也可以用节点的当前移动速度来使预测区域最小化。速度信息可以从传感器数据收集得到,如传感器节点采用一个三维加速度计就可以估算出其速度。
如图 2所示,位于交叉区域中心处的普通节点k能够直接与3个1跳邻居节点通信。对于每对1跳邻居节点来说,插入一个虚拟锚节点i,和k构建一个大小为2*deffk,i的正方形,正方形的中心在锚节点i,deffk,i为i和k之间的估计距离。基于传感器节点的当前移动速度,得到的采样矩形区域块的坐标就可以计算如下:
$\left\{ \begin{array}{*{35}{l}} {{x}_{\min }}=\max (\underset{i=1}{\mathop{\overset{n}{\mathop{\max }}\,}}\,({{X}_{i}}-d_{eff}^{k,i}),{{x}_{t-1}}-{{v}_{t}}) \\ {{x}_{\max }}=\max (\underset{i=1}{\mathop{\overset{n}{\mathop{\max }}\,}}\,({{X}_{i}}+d_{eff}^{k,i}),{{x}_{t-1}}-{{v}_{t}}) \\ {{y}_{\min }}=\max (\underset{i=1}{\mathop{\overset{n}{\mathop{\max }}\,}}\,({{Y}_{i}}-d_{eff}^{k,i}),{{y}_{t-1}}-{{v}_{t}}) \\ {{y}_{\max }}=\max (\underset{i=1}{\mathop{\overset{n}{\mathop{\max }}\,}}\,({{Y}_{i}}+d_{eff}^{k,i}),{{y}_{t-1}}-{{v}_{t}}) \\ \end{array} \right.$ | (7) |
其中:(xt-1,yt-1)为粒子lt-1的坐标。如果考虑2跳邻居时,可以用普通节点k和它的2跳邻居虚拟锚节点之间的估计距离在来代替deffk,j即可。
图 3为预测区域形成系统模型图。基于图 3,令锚节点A和B之间的距离为d2,A和未知节点E之间的距离为d1,未知节点E和锚节点B
$\cos \theta =\frac{d_{2}^{2}+d_{1}^{2}-d_{3}^{2}}{2{{d}_{1}}{{d}_{2}}}$ | (8) |
类似地,在△ADE中,可以得到:
$\cos \theta =\frac{(d_{2}^{2}/4)+d_{1}^{2}-d_{0}^{2}}{{{d}_{1}}{{d}_{2}}}$ | (9) |
这样,就可以基于式(7)和(8)计算出d0的值如下:
${{d}_{0}}=\frac{\sqrt{2d_{1}^{2}+2d_{3}^{2}-d_{2}^{2}}}{2}$ | (10) |
预测阶段 如果锚节点的距离和节点当前的移动速度约束脱节,例如在初始化计算预测区域时,节点速度不在限定范围内,则预测区域就有助于在预测阶段得到有效的粒子。基于先前估计得到的一个给定位置的概率服从式(11)所示的均匀分布:
$p({{L}_{t}}\left| {{L}_{t-1}} \right.)=\left\{ \begin{matrix} 1, & {{x}_{\min }}\le {{x}_{t}}\le {{x}_{\max }}且 \\ {} & {{y}_{\min }}\le {{y}_{t}}\le {{y}_{\max }} \\ 0, & 其他 \\ \end{matrix} \right.$ | (11) |
其中:(xt,yt)为粒子lt的坐标。
滤波阶段 在预测阶段,每个节点在预测区域内生成一组均匀分布的随机值。如果得到的粒子位于每个邻居节点的通信范围内,则节点就保存这个位置作为最终估计值;否则,节点丢弃并重复预测阶段。对一个节点的整个滤波阶段可以表示如下:
$filter({{l}_{t}})=\forall a\in M,d({{l}_{t}},a)\le r+{{v}_{t}}且\forall b\in N,r-{{v}_{t}}\le d({{l}_{t}},b)\le 2r+{{v}_{t}}$ | (12) |
其中:lt为所考虑的粒子;M和N分别为1跳和2跳邻居的集合;r为节点的通信范围;d(lt,a)为粒子lt和邻居节点a之间的距离;vt为一个邻居节点当前的移动速度。在得到足够的有效粒子数量后,最后的位置估计就可以计算为粒子集的平均值。
2 算法性能评价为了评价本文算法的总体性能,这部分对本文提出的改进洪泛广播机制和简单洪泛广播机制对于每个锚节点需要广播的信标消息数量和节点所使用的锚消息平均总数量进行比较,在定位精度、节点移动速度和锚节点密度对算法定位精度的影响与DV-Hop[10]、MCB[1]和MCL[6]三种定位算法进行比较。
考虑到算法的精度、,仿真中将300个节点以随机均匀拓扑结构方式放置在一个500r×500r(r=1为单位长度)平方区域内,无线电波传播采用单位圆盘模型,辐射范围设置为50r,单位时间间隔的最大速度设置为50r,锚节点和未知节点的移动采用随机航路基准点模型,以防止平均速度衰减问题;采用50个单位样本集,对于每个参数,运行30个仿真结果,然后取其平均值。
2.1 广播机制性能的评价图 4为一个锚节点采用本文提出的改进洪泛广播机制和采用简单的洪泛广播机制时需要广播的信标消息数量来保证节点的定位,锚节点位于坐标轴的左下角。从图 4可以看到,采用简单的洪泛广播算法机制时,一些节点必须广播的信标消息达5次以上,而且离锚节点越远的节点,需要广播更多的消息来修正累积误差;相反,采用本文提出的改进洪泛广播机制时,全部节点中的每个节点只需1个信息开销即可获得其正确的最小跳数。因此,本文提出的改进洪泛广播机制有效地减少了冗余信息的数量。图 5为两种广播机制全部节点所使用的锚节点消息的平均总数量。可见,本文提出的改进洪泛广播机制随着传输范围的增大,所使用的锚节点消息的平均总数量不变,而采用简单的洪泛广播算法机制时,所使用的锚节点消息的平均总数量随着距离的增加而增大,因为越远的节点需要重新广播多次。可见,本文提出的改进洪泛广播机制能很好地扩展网络大小,并从实质上有效抑制冗余广播。
图 6为定位精度的收敛情况比较。
从图 6可见,本文提出的定位算法的估计误差不仅能较快收敛到稳定值,而且估计误差的收敛稳定值是4种定位算法中最小的,是最优的。这是由于有更小的信息开销和一个更小的采样区域采用了粒子优化滤波;DV-Hop定位算法[10]是次优的,但要重复广播,造成数据采集时延增大和估计误差增大;而其余2种定位算法由于新的锚节点加入到序列蒙特卡罗定位过程,以及更新后的位置分布和移动引入了不确定性,所以其估计误差和稳定误差收敛时间都要大于本文算法和DV-Hop定位算法[10]。
2.3 节点移动速度对定位精度的影响图 7为节点移动速度对定位精度的影响。从图 7可见,对于MCL[6]和MCB[1]定位算法来说,节点移动速度变化对定位精度影响较大,特别对于较高的速度;而对于本文提出的定位算法来说,由于普通节点可以获取更多新的锚节点信息来添加到滤波阶段,从而保证样本集的更新,故节点移动速度对定位精度影响较小;而对于DV-Hop定位算法[10],由于采样面积变大,重复采样次数较多,从而使得节点移动速度增大,也降低了算法的定位精度。
增大锚节点密度有利于普通节点提取位置信息。图 8为锚节点密度变化时四种不同定位算法的估计误差。从图 8可见,MCL算法[6]和MCB算法[1]依赖于较大的锚节点密度,因为需要更多的位置可供选择和滤波;而在DV-Hop算法情况下,锚节点密度对精度的影响可以忽略不计,因为由于重复多次广播,来自于整个网络的信息可被利用,与锚节点数量无关;而本文算法尽管也与锚节点密度有关,但优于其他三种算法,原因是更小的采样面积和更好的滤波技术。
本文针对移动无线传感器网络,提出了一种改进的洪泛广播机制和粒子滤波的协同定位算法。算法对于移动传感器网络来说是可扩展的、鲁棒的,而且具有自适应动态特性;算法通过采用差分误差修正机制,可以减小由于多跳造成的跳距估计误差累积,有效抑制冗余广播和减少通信开销;通过采用粒子滤波技术,提高了定位性能。为了进一步提高算法的节点定位精度和算法的收敛速度,下一步打算采用基于神经网络模型来实现定位算法中从离定位节点最近的锚节点得到有效平均跳距,从而得到它到它的所有邻居节点的距离。
[1] | BAGGIO A, LANGENDOEN K. Monte Carlo localization for mobile wireless sensor networks[J]. Ad Hoc Networks, 2008, 6 (5) : 718-733. doi: 10.1016/j.adhoc.2007.06.004 (0) |
[2] | 李国华.无线传感器网络高效数据传输方法[D]. 哈尔滨:哈尔滨工业大学, 2014:49-82. ( LI G H. High-efficiency data transmission methods in wireless sensornetworks[D]. Harbin:Harbin Institute of Technology, 2014:49-82. ) (0) |
[3] | 李文锋, 符修文. 无线传感器网络抗毁性[J]. 计算机学报, 2015, 38 (3) : 625-647. ( LI W F, FU X W. Survey on invulner erabilit of wireless sensor networks[J]. Chinese Journal of Computers, 2015, 38 (3) : 625-647. ) (0) |
[4] | 裴祥, 李巧君. 基于改进粒子群优化算法的无线传感器网络定位[J]. 计算机与现代化, 2015 (7) : 81-84. ( PEI X, LI Q J. Localization for wireless sensor network based on modified particle[J]. Computer and Modernization, 2015 (7) : 81-84. ) (0) |
[5] | HU L, EVANS D. Localization for mobile sensor networks[C]//Proceedings of the ACM 10th Annual International Conference on Mobile Computing and Networking. New York: ACM, 2004:45-57. http://cn.bing.com/academic/profile?id=2131152141&encoded=0&v=paper_preview&mkt=zh-cn (0) |
[6] | DIL B, DULMAN S, HAVINGA P. Range-based localization in mobile sensor networks[C]//Proceedings of the 2006 European Workshop on Wireless Sensor Networks. Berlin: Springer, 2006: 164-179. http://cn.bing.com/academic/profile?id=1608899808&encoded=0&v=paper_preview&mkt=zh-cn (0) |
[7] | HSIEH Y L, WANG K. Efficient localization in mobile wireless sensor networks[C]//Proceedings of the 2006 IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing. Piscataway, NJ: IEEE, 2006:292-297. (0) |
[8] | NICULESCU D, NATH B. Ad Hoc Positioning System (APS)[C]//Proceedings of the 2001 IEEE Global Telecommunications Conference. Piscataway, NJ: IEEE, 2001, 5:2926-2931. http://cn.bing.com/academic/profile?id=2104782624&encoded=0&v=paper_preview&mkt=zh-cn (0) |
[9] | 曹敦, 张静, 傅明. 基于移动代理的三维DV-Hop算法[J]. 计算机应用, 2012, 32 (1) : 134-138. ( CAO D, ZHANG J, FU M. Three-dimensional DV-Hop algorithm based on mobile Agent[J]. Journal of Computer Applications, 2012, 32 (1) : 134-138. ) (0) |
[10] | 胡中栋, 曹季. 改进的无线传感器网络DV-Hop定位算法[J]. 计算机与现代化, 2014 (11) : 5-8. ( HU Z D, CAO J. An improvement of DV-Hop localization algorithm for wireless sensor network[J]. Computer and Modernization, 2014 (11) : 5-8. ) (0) |
[11] | 黄霜霜, 樊春丽. 三维无线传感器网络中DV-Hop定位算法的改进[J]. 计算机与现代化, 2014 (11) : 35-39. ( HUANG S S, FAN C L. An improved DV-Hop positioning algorithm based on three-dimensional wireless sensor networks[J]. Computer and Modernization, 2014 (11) : 35-39. ) (0) |
[12] | 王浩云, 王珂, 李多, 等. 基于虚拟力的无线传感器与执行器网络测距定位算法[J]. 计算机应用, 2014, 34 (10) : 2777-2781. ( WANG H Y, WANG K, LI D, et al. Range-based localization algorithm with virtual force in wireless sensor and actor network[J]. Journal of Computer Applications, 2014, 34 (10) : 2777-2781. ) (0) |