节点定位算法范文

2024-08-01

节点定位算法范文（精选8篇）

节点定位算法第1篇

粒子群优化算法[7]PSO(Particle Swarm Optimization)早期是模拟一些简单的社会群落生物,如鸟群、鱼群等模型,是一种基于群体的演化算法。PSO算法简单,易于实现,需调参数少,是解决非线性连续优化、组合优化等问题的有效工具。

参考文献[8]将粒子群优化算法应用到无线传感器网络的节点定位过程中,根据节点间的测距信息构成目标函数,将节点自定位转化成非线性优化问题,用粒子群优化算法对其进行求解,并且指出在定位精度方面要优于多边定位法、模拟退火算法等。参考文献[9]根据离散线性系统的稳定性理论,推出了保证粒子群优化算法收敛性的参数设置区域,参考文献[10-12]对粒子群优化算法的惯性权重进行了改进,分别提出了线性递减、非线性递减以及反馈动态调节的惯性权重取值策略,提高了算法寻优精度以及收敛速度。本文根据惯性权重对粒子搜索能力的影响,并结合节点间连通性对惯性权重的设置进行改进,使其更加适应无线传感器网络节点定位。

1 粒子群优化算法

PSO算法在一定区域中随机选取一组位置坐标,作为粒子群的初始粒子。粒子通过代入目标函数来计算适应度,从而得到粒子本身所找到的最优位置Ppbest和整个种群目前找到的最优位置Pgbest,通过更新迭代,最终获得满足要求的最优目标位置。

以二维空间为例,向量xi=(xi,yi)表示第i个粒子位置坐标,粒子速度可表示为vi=(vi1,vi2),Pipbest、Pgpbest分别为粒子群的个体最优位置和群体最优位置,则粒子更新公式可表示为:

式中rand1、rand2表示两个0~1之间的随机数,c1、c2是加速度系数,w为惯性权重,k为优化迭代次数。

将粒子群优化算法应用到WSN节点定位算法,设定目标函数:

其中,ri表示未知节点到第i个锚节点的测距值,适应度f(xi,yi)表示第i粒子到每个锚节点之间的距离与测距结果的平均误差值,最大适应度是粒子群优化算法中重要的判决参数,决定着算法的循环次数和定位精度,其值的大小与测距误差有关。

PSO算法的描述如下:

(1)设置群体规模,在节点布设范围内随机设定每个粒子的初始位置、初始速度。选取合适的目标函数,设定c1、c2、w、最大迭代次数kmax、最大适应度ε等参数;

(2)将每个粒子代入目标函数计算适应度,如果第i个粒子的适应值优于Pipbest对应的适应值,将Pipbest更新为当前粒子位置,将当前最优的适应度值与其Pgbest处的适应度值进行比较,取最优位置作为群体最新的Pgbest;

(3)将Pgbest代入目标函数计算适应度,如果f(Pgbest)<ε或者k≥kmax,则执行步骤(5),否则执行步骤(4);

(4)分别将Pgbest、Pipbest代入式(1)和式(2),更新粒子的速度和位置。然后转到(2);

(5)停止迭代,输出当前的Pgbest作为所求的未知节点坐标。

2 算法改进

从以上PSO算法流程中可以看到,粒子的初始位置是所有节点的布设区域,在粒子寻优过程中可能会陷入局部最优解,并且在布设区域较大时会影响粒子的收敛速度,造成迭代次数的增加。为了使粒子群优化算法更加适应WSN节点定位的特点,本文从两个方面入手对其进行了改进:(1)利用节点间的连通性构造对未知节点坐标加以约束,缩小未知节点存在的可能区域,为粒子群的初始化和粒子的更新范围提供可靠的约束依据;(2)根据未知节点存在区域,对粒子群优化算法的惯性权重进行改进。

2.1 缩小未知节点存在的可能区域

假设节点的最大通信距离都为R,未知节点坐标为X=[x,y]T,在其通信范围内有m个锚节点,记作Xi=[xi,yi]T,i=1,2,…,m,因此得知未知节点存在于以最大通信距离为半径,以其相应锚节点为中心的圆内,表示如下:

为了计算方便,对约束区域进行适当的放大,将式(4)转化为线性约束形式:

将所有邻居锚节点坐标代入以上约束条件,得到未知节点存在的可能区域,如图1所示。

在传统的粒子群优化算法中,未知节点可能存在的区域是根据所有节点布设的范围来估计的,粒子在该区域内初始化并且不断更新,搜索最优位置,对粒子更新提供的约束信息非常有限,经过上述对节点间连通度的利用,很大程度上缩小了未知节点可能存在的区域,为粒子群的初始化、个体最优位置Pipbest和群体最优位置Pgbest的更新提供了更加精确的范围限制。改进后算法的粒子种群可以在相交区域内随机选取,利用区域Φ的中心坐标作为Pgbest,在粒子的更新阶段,相交区域可以为粒子更新速度提供约束条件,要求更新后粒子不应跳出相交区域。

2.2 改进惯性权重设置

惯性权重w的大小体现了对粒子当前速度继承的程度。参考文献[10]指出较小的w可加强局部搜索能力,而较大的w则有助于在全局范围内搜索,并且将惯性权重w设计为随迭代次数线性递减的函数,在算法的初期使用较大惯性权重以跳出局部最优解,而在后期则使用较小惯性权重,提高局部搜索能力以加快收敛速度。即:

式中wmax和wmin分别表示惯性权重w的最大和最小值,kmax为最大迭代次数,参考文献[10]将其分别取值为0.9和0.4。

根据节点连通性的约束,在一定程度上缩小了未知节点可能存在的区域。在比较小的区域内利用粒子群优化算法估计未知节点坐标,选用较大的w可能使粒子跳出有效区域,此时更加倚重较小的w来加强局部搜索能力,而式(6)的惯性权重下降速率是恒定的,不利于更快速准确地获得最优位置估计。因此本文将w设计成前期较大的惯性权重下降速率较快、较小的惯性权重下降速率较慢的非线性递减函数。

根据以上对于惯性权重的设计分析,其函数表达式可以用二次曲线表示为:

其中,a、b、c为待确定抛物线系数,根据参考文献[10]对wmax、wmin、kmax的设置,得到:

由于每个未知节点的连通性不同,对未知节点可能存在的区域的缩小程度也有所差异,因此利用节点连通性获得的相交区域大小应成为影响惯性权重函数设置的重要因素。具体表现为:当相交区域相对于布设区域比例λ(0<λ≤1)越小时,w的变化幅度越大,函数的曲率取值越大;反之,w的变化幅度越小,函数的曲率取值越小。用数学模型表示:

结合式(8),可以得到:

则惯性权重函数表达式为:

由于对称轴≥kmax,则

3 仿真

本文利用Matlab软件对上述算法进行仿真,并对仿真结果进行比较分析。在200 m×200 m区域内随机布设100个传感器节点,节点通信半径为50 m,假设测距误差服从均值为0、方差为3的高斯分布,则c1=c2=1.494、初始惯性权重wmax=0.9、最终惯性权重wmax=0.4、最大迭代次数kmax=200、最大适应度ε=2 m、初始速度vi=0,h取最大值。仿真的实现流程如图2所示。

平均定位误差p=

其中,xi,yi为第i个节点的真实位置,为第i个节点的估计位置,m为已定位的未知节点个数,R为通信半径。

为了表述方便,将本文提出的改进后粒子群优化算法记作PSO-U,并与前文提到的PSO、多边定位法[2]等位置估计算法进行性能比较。图3是在锚节点密度设定为30%,通过调节节点通信距离来控制平均连通度变化的情况下,对三种算法平均定位误差的比较。图中随着节点平均连通度的增大,各算法的平均定位误差逐渐下降,其中PSO-U算法的下降幅度最小,相对于另外两种算法受平均连通度变化的影响较小,在较小连通度的情况下就可以达到比较高的定位精度。图4是在平均连通度设定为13,锚节点密度从20%线性增加的情况下,对三种算法平均定位误差的比较。图中各算法的平均定位误差随着锚节点密度的增大而逐渐变小,相对于平均连通度的变化,锚节点密度对平均定位误差的影响较小。

粒子群优化是一种迭代搜索方法,迭代次数是该算法计算量的重要体现,以下对改进后粒子群优化算法的迭代次数进行仿真分析。图5是锚节点密度分别取20%、30%、40%的条件下,PSO-U和PSO的平均迭代次数比较。从两图中可以看出,本文提出的PSO-U算法的平均迭代次数明显小于PSO算法。但是综合分析改进前后的粒子群优化算法,PSO-U算法需要对相交区域进行估算,这相对于PSO算法是额外的计算量,并且惯性权重在形式上要更为复杂。因此,整体来看,本文提出的PSO-U算法在定位精度上有明显的优势,但在算法复杂度上有所增加,适用于对精度要求较高的WSN应用中。

本文将粒子群优化算法应用到节点定位过程中,通过对惯性权重的分析,对基于粒子群优化的节点定位算法进行了改进。首先利用节点间的连通性估计未知节点可能存在的约束区域,然后对粒子群优化算法的惯性权重的设置进行了优化。通过仿真比较,改进后算法在定位精度方面有明显改善,并且受节点分布的影响较小。由于粒子群优化算法通过迭代方式搜索未知节点的最优位置,在测距误差较大、参数设置不理想等情况下,其计算量会有比较明显的增加。

参考文献

[1]KRISHNAMACHARI B.Networking wireless sensors[M].New York:Cambridge University Press,2005.

[2]孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005.

[3]TIAN H,CHENGDU H,BRIAN M B,et al.Range-freelocalization schemes in large scale sensor networks[A].In:Proceedings of the 9th annual international conferenceon mobile computing and networking(MobiCom’03)[C],San Diego,California,USA,2003:81-95.

[4]NIEULESEU D,NATH B.DV based positioning in ad hocnetworks[J].Journal of Telecommunica-tion Systems,2003,22(1):267-280.

[5]BULUSU N,JOHN H,ESTRIN D.GPS-less Low costoutdoor localization for very small devices[J].IEEE Journalof Personal Communications,2000,7(5):28-34.

[6]DOHERTY L,PISTER K S J,GHAOUI L E.Convex pos-ition estimation in wireless sensor networks-[A].In:Pro-ceedings of the IEEE INFOCOM 2001[C],2001(3):1655-1663.

[7]KENNEDY J,EBERHART R C.Particle swarm optimiz-ation[C].Proceedings of IEEE International Conference onNeural Networks,Perth,Australia,1995:1942-1948.

[8]GOPAKUMLAR A,JACOB L.Localization in wireless sen-sor networks using particle swarm optimization[C].IET In-ternational Conference on Wireless,Mobile and MultimediaNetworks,2008(1):227-230.

[9]林卫星,陈炎海.一种快速收敛的改进粒子群优化算法[J].系统仿真学报,2011,23(11):2406-2411.

[10]SHI Y H,EBERAHRT R C.Parameter selection in part-icle swarm optimization[J].Lecture Notes in ComputerScience,1998,47(14):591-600.

[11]CHATTERJEE A,SIARRY P.Nonlinear inertia weightvaria tion for dynamic adaptation in particle swarm optimi-zation[J].Computers&Operations Research,2006,33(3):859-871.

节点定位算法第2篇

FlexRay总线作为下一代汽车内部的主干网络，其良好的性能尤其是高速、精确和容错的特点，能够满足未来汽车高速控制应用的需要［1-3］。FlexRay总线精确的时钟基准是其可靠运行的关键因素之一，而网络中的时钟同步是总线时基精确的重要保证，因此研究FlexRay时钟同步问题具有重要的现实意义。

文献［4］提出了一种基于分析模式的FlexRay时钟同步算法，可以不通过测量而直接通过计算得出任意两个节点之间的时钟偏差。文献［5］对FlexRay总线时钟同步进行了分析，建立了同步算法数学模型，理论上说明了FlexRay时钟同步具有较强的容错性和适用性。文献［6］指出FlexRay时钟同步所用容错中值(Fault-tolerant midpoint，FTM)算法每轮对网络修正后存在±ε（ε为传送延时）漂移。

FlexRay协议要求网络中至少包含3个同步节点进行时钟同步，上述文献都是建立在这个基础上进行讨论的。当节点数目较少时，这种限制将对网络的性能产生影响。针对这种情况，文献［7］结合IEEE 1588提出了一种同步节点数目少于3个的同步方法，但是没有解决同步过程中的同步节点容错问题。一旦同步节点出现故障，整个网络将无法正常工作，造成消息的延误［8］。

本文在上述研究的基础上，提出了一种FlexRay的单节点容错同步算法。该方法只需要一个同步节点并且无需额外的硬件支持，即可在保证FlexRay安全性和可靠性的前提下完成时钟同步。

1 FlexRay时钟同步

1.1 同步周期的基本概念

FlexRay总线协议中，簇内所有的节点都应有相同的“时间观”，遵守一个标准的全局时间。但是这并不意味着节点间具有完全严格的同步时间，只要节点间的时间差保持在允许的误差范围内即可。在一个通讯周期内分为4个时间层次，从最低层到最高层分别依次为：最小时间节拍层、最大时间节拍层、仲裁网格层和通讯周期层。

时钟同步过程设置三种模式：（1）备用模式（STANDBY），（2）非同步模式（NOSYNC），（3）同步模式（SYNC）。在STANDBY模式中时钟同步过程被停止，在NOSYNC模式中节点执行时钟同步但不发送同步消息，在SYNC模式中节点发送同步消息并执行时钟同步［9］。

FlexRay协议中节点在静态段完成同步测量，以获得各节点的时间偏差值，运用FTM算法［9］对每一组时间偏差值进行处理，所获得的值即为时钟同步算法的校正值。FlexRay同步机制运用两种类型的校正：相位校正和速率校正。相位校正值是各非同步节点与同步节点的时间偏差值，每周期进行计算并在奇数周期末尾完成校正。速率校正值是两个连续周期同一节点同一时刻的时间偏差值，偏差的计算结果在每个奇数周期完成计算，在下一个周期开始时生效，在最大时间节拍形成过程中实行。

1.2 同步时间测量

为了计算同步帧发送节点与同步帧接收节点之间的时间偏差，就必须分别测量同步帧发送端和同步帧接收端的触发点时刻。但是由于传输起始序列截断影响，同步帧接收节点接收到传输起始序列1/0跳变沿的时间并不是同步帧接收节点的触发点时刻。因此在FlexRay总线协议中需要测量首个字节起始序列中的1/0跳变沿，用该时刻减去解码修正量和延时补偿量倒推得到接收端传输起始序列的开始时刻。解码修正量中包含传输起始序列、帧起始序列和字节起始序列，延时补偿量中包含有收发器延迟、星型耦合器延迟和电缆长度的传输延迟［10］。

图1为时间偏差值测量过程，其中点 a表示发送端静态时间槽行动点，即发送端开始发送帧的时刻；点b表示第二时间参考点，位于首个字节起始序列的第二位频闪点；点c表示主时间参考点，由第二时间参考点减去解码修正量和延时补偿量得来；pDecodingCorrection为解码修正量，pDelayCompensation为延时补偿量，TSS为传输起始序列，FSS为帧起始序列，BSS为字节起始序列。由图1可知，点c与点a之间的差值为同步帧发送节点与同步帧接收节点之间的时间差（时钟偏差值）。

2 单节点容错同步算法研究

2.1 基本思想

针对FlexRay协议中同步节点数目不能小于三个的情况，本文采用单节点容错算法来实现时钟同步，为了解决单节点失效的问题，在时钟同步过程中增加一个同步节点优先级表。表的结构见表1，其中NODE_ID为节点的ID号，值越小优先级越高；NODE_NM为节点的名称；MES_ID为该节点发送同步消息所在的静态时间槽的ID；NODE_STA为节点状态标志，表示该节点是否失效。

表1 同步节点优先级表

在网络启动或者有新节点加入网络时，网络中各节点根据其他节点提供的信息建立或者更新自身的同步节点优先级表。当前同步节点失效时，根据此表优先级与其他节点协商决定同步节点。

在FlexRay协议中，各非同步节点在触发点接收同步消息，在超过触发点偏移量之后仍然没有收到同步报文，就认为该同步节点发生了故障，本文亦采用该方法判断节点是否发生故障。如果故障发生次数达到设定值，则认为该同步节点失效，在同步节点优先级表中选择优先级最高的节点替代同步节点，在周期动态段部分发出选择消息(Vote)。各节点收到 Vote消息后，扫描信息表，若与己选同步节点相同，发送确认消息，启动候选同步节点。

2.2 时间偏差值计算

FlexRay协议中为了测量同步节点和非同步节点之间的偏差，需要测量第二时间参考点并计算解码修正量和延时补偿量的值，这样不仅增加了计算开销，还增大了误差。为了减小开销和误差，本文基于文献［11］的方法来计算时间偏差值，图2为相应的通信过程。同步节点在T1时刻发送Sync消息，同步节点和非同步节点接收端分别测量接收到该报文的第二时间参考点时刻，分别记为T2和T3，同步节点在T4时刻发送一个包含时间戳T2的Follow_up消息。

本文时间偏差值计算过程中采用如下假设［7，11］：

（1）帧到达各节点的延时是定值，即网络必须是广播型网络，延迟时间可以接近于0，或是一个常值。

（2）节点接收器能够接收到该节点发送器发送的帧。

设Toffset为时间偏差，单位为最小时间片个数，该值可以为正也可以为负；Lmaxoffset为时间偏差允许上限，根据情况预先设置；u为解码修正量，ν为延时补偿量。那么，可以得到同步节点和非同步节点之间的等式：

由于同步节点的发送端和接收端在同一节点上，认为它们之间的偏差为0，那么可以得到同步节点发送端和接收端的等式：

由假设（1）可知式，（1）（2）中解码修正量和延时补偿量的值相等，即 u1=u2，ν1=ν2，因而由（2）和（1）可得：

式（3）中的Toffset就是同步节点与非同步节点的时间偏差值，因此由T3和T2即可得到Toffset，而T3和T2可以从Sync消息和Follow_up消息中获取。

2.3 单节点容错算法

基于上述机制的单节点容错算法，算法流程图如图3所示，具体步骤如下：

步骤1：初始化FlexRay网络中各节点控制器和寄存器，错误计数器M清零。根据在同步节点优先级表中预先的设置，将表中优先级最高的节点设为同步模式，其他节点设为非同步模式。

步骤 2：在第 i（i≤63）个通信，同步节点向总线上各节点发送Sync消息。

步骤3：各节点（包括同步节点）接收到Sync消息，并记录各自的接收时刻。

步骤4：同步节点向各节点发送一个Follow_up消息，非同步节点通过公式（3）可以计算各节点本地时钟的偏差 Toffset，当∣Toffset∣＞Lmaxoffset时，启动错误计数器令 M=M+1，令 Toffset=Lmaxoffset。

步骤5：因为网络可能出现错误，造成部分Sync消息不能被所有节点成功接收。如果节点超过触发点偏移量仍然没有收到Sync消息，启动错误计数器令 M=M+1，同时令 Toffset=Lmaxoffset。

步骤6：若某节点错误计数 M≥3则判定同步节点失效，扫描数据表选择下一顺序节点为候选同步节点，并在动态段中发送广播选择消息（Vote）。

步骤7：各节点收到 Vote消息后扫描信息表，若与已选同步节点相同，则在动态段中发送确认消息。Vote消息的发送节点收到确认后，将原同步节点的模式改为备用模式，所选同步节点的模式改为同步模式，各节点错误计数器清零。若规定时间内未收到确认消息，判定该非同步节点故障，原同步节点继续运行，错误计数器清零。

步骤8：若该周期结束，则i=i+1。如果i≤63，则返回步骤2，否则返回步骤1。

图4a中表示了一个周期内上述时钟同步的过程。在一个周期静态段内，同步节点在发送Sync消息和Follow_up消息后预留了两个静态时间片，在第五个静态时间片开始发送普通数据帧。图4b中表示了FlexRay协议时钟同步过程，四个同步节点分别发送四个Sync消息之后，在第五个静态时间片开始发送普通数据帧。从图4可以看出，在保证相同可靠性的前提下，本文所提同步算法不影响静态段的长度以及周期长度。而且本文同步算法不需计算解码修正量和延时补偿量就可以直接计算时间偏差值，精简了测量步骤同时也减少了由于计算解码修正量和延时补偿量值而造成的误差。

3 仿真验证

本文利用CANoe和DaVinci Network Designer软件对本文所提单节点容错同步算法进行仿真实验。

实验中选取4个节点，记为ECU_1、ECU_2、E CU_3和ECU_4，每个节点均有两组工作消息需要发送。在单节点容错同步算法中，考虑容错需要，令ECU_1为初始同步节点，ECU_2为候选同步节点；在FlexRay协议原有同步算法中，ECU_1、ECU_2和ECU_3为同步节点。在DaVinci Network Designer软件中完成FlexRay数据库建立，并在CANoe软件中建立仿真系统，如图5所示。

在正常通信过程中，当初始同步节点ECU_1断开，候选同步节点ECU_2能够代替ECU_1成为下一同步节点，图6为上述过程的trace图。

4 结束语

本文在对FlexRay协议时钟同步算法研究的基础上，提出了FlexRay总线的单节点容错同步算法，只需要1个同步节点即可完成时钟同步，减少了时钟同步的测量步骤和计算量。该算法引入同步节点优先级表，在同步节点出现故障的情况下，可以根据同步节点优先级表选择新的同步节点。最后在CANoe中进行仿真，结果表明该算法可以在保证安全可靠的前提完成通信，并提高同步精度。

［1］罗峰，陈智琦，刘矗，等.基于FlexRay的车载网络系统开发［J］.电子测量与仪器学 2009（增刊 1）：289-295.

［2］顾嫣，张凤登.FlexRay动态段优化调度算法研究［J］.自动化仪表，2009，30（12）:25-29.

［3］周跃钢.基于LabVIEW和J1939协议的CAN总线通讯平台构建［J］.汽车科技，2011，06:18-22.

［4］Jan Sobotka，Jiri Novak，Jan Malinsky.Analytic Model of FlexRay Synchronization Mechanism ［J］.The 6th IEEE In ternational Conference on Intelligent Data Acquisition and Advanced Computing Systems，2011:969-974.

［5］陈涛，秦贵和.FlexRay时钟同步分析［J］.计算机工程，2010，14（36）：235-237.

［6］Bruno Dutertr.the Welch Lynch Clock Synchronization Algorithm［R］.1998，5.

［7］Jin Ho Kim，Suk Hyung Seo，Jung Hoon Chun，Jae Wook Jeon.Distributed Clock Synchronization Algorithm for Industrial Networks［J］.The 8th IEEE International Workshop on Factory Communication Systems.2003.

［8］J.H.Kim，S.H.Seo，T.Y.Moon，K.H.Kwon，J.W.Jeon，S.H.Hwang.A method of Task Synchronization in a distributed system using FlexRay［J］.The IEEE Interational Conference on In-dustrial Informatics，2008:1149-1153.

［9］FlexRay Consortium.FlexRay Communications System Protocol Specfication ［S］.2005（12）.

［10］杨福宇.FlexRay时钟同步的同向漂移［J］.单片机与嵌入式应用，2011，4:3-6.

基于RSS的多目标节点定位算法第3篇

关键词：定位,GMM,信号传播模型

引言

无线传感器网络节点定位是传感器网络研究的热点, 如何利用简单廉价的设备得到精确的定位结果一直是传感器节点定位研究的重点和难点。

在目前已有的定位算法中, 基于RSS的节点定位算法与基于AOA、TOA或TDOA的节点定位算法相比, 具有成本低、适用范围广等优点, 但定位精度不高[1,2]。为此, 研究人员利用统计模型提高定位算法的健壮性和精确度[3,4,5,6,7,8]。另外, 很多定位算法假设待估节点数量已知, 或者假设RSS发射节点的ID可识别, 但在大多数情况下, 上述假设都是不可预知的, 很难在实际环境中使用, 因而算法实用性不强。

为节约成本, 提高算法实用性和精度, 本文提出一种新颖的基于RSS的定位算法——多目标高斯混合模型定位算法 (Multi-target Localization Based on Gaussian Mi xture Model, MTL-GMM) , 使用单一移动信标节点[8,9]采集信息, 用最小化已知条件估算传感器节点的数量和位置信息。仿真实验和实测实验均证明了本文提出算法的有效性和准确性。

多目标高斯混合模型

基本假设

M T L-G M M算法用一个移动信标节点 (RSS-collector, RC) 采集信息做为已知条件。RC在定位区域内移动, 采集周围传感器节点发射的RSS信号, 并记录收到每个RSS时R C自身的位置坐标。其中, R C采集的R S S信号序列用12{, , ..., }nR=r r r表示, n为序列中R S S信号的数量, 其相应的位置坐标序列用1122nnRCLoc={ (x, y) , (x, y) , ..., (x, y) }表示。

信号传播模型

信号传播的路径损耗模型描述了RSS取值和信号传播距离的关系, 本文使用对数距离路径损耗模型[10], 如式 (1) 所示。

其中, r和t分别为接收和发射信号强度, 单位为d B;d为信号收发节点间距离;0l为在参考距离d0处的路径损耗;γ为与环境相关的路径损耗指数, 反应路径损耗随距离增长的速率;S为对数正态阴影。

高斯信道模型

大量实验证明, 收发距离不变的情况下, 无线信号的路径损耗服从高斯分布[10]。也就是说, 假设传感器节点A向节点B发送信号, 若节点A和B之间距离不变, 则节点B收到的由节点A发射的RSS服从高斯分布。

下面给出了高斯分布的概率密度函数:

γ为随机变量, 表示RSS;m为γ的均值;σ为γ的标准差。

GMM描述

在实际环境中, 信标节点RC接收到的RSS信号通常来自多个发射节点, 而节2.2所述的高斯概率密度函数仅能描述单一发射节点的RSS信号序列分布, 所以, 需要一种有限混合模型[11]综合描述多个概率分布。本文使用高斯混合模型描述RC采集的来自多个发射节点的RSS信号序列R, 如式 (3) 所示。

γ为随机变量, 表示RSS;M为高斯分量的数量, 表示发射节点的数量;Wj、mj、σj为第j个高斯分量的权重、均值和标准差, 且jM∑=1wj=1and∀j:wj≥0;g (r|mj, sj2) 为第j个高斯分量的概率密度函数。

本文混合序列R的联合高斯概率密度函数可以表示为:

MT-GM M算法依赖模型的极大似然估计值估计模型参数。极大似然值越大时, 模型参数取值越接近真实值。为方便估计, 对公式 (3) 两侧取对数, 得出公式 (4) :

模型参数的判定

为判定定位区域内传感器节点的数量和位置, 我们采用贝叶斯信息准则 (Bayesian Information Criterion, BIC) [12,13]进行模型选择。BIC考虑到待估参数的数量和RSS信号序列R的大小对估计结果造成的影响, 如公式 (5) 所示。

其中, k表示GMM模型中待估自由参数的数量;等式右边第二项是惩罚项, 该项考虑样本集R的大小对估计结果造成的影响。在节2.3所述高斯混合模型中, 传感器节点的位置坐标为待估自由参数, 故k=2M。

GMM模型的极大似然值越大, 模型越接近真实, 我们选取BIC最大时的模型参数做为传感器节点数量和位置的估计值。

MTL-GMM算法

MTL-GMM算法将定位区域划分成大小相同的网格, 首先粗略定位传感器节点所在的网格, 根据粗略定位结果缩小定位区域和网格尺寸, 迭代运行Grid L (Grid Localization) 算法, 实现精确定位。具体步骤如下:

Step1:初始化定位区域;

Step2:定义网格尺寸;

Step3:运行Grid L算法, 若定位误差<=阈值, 输出结果, 若定位误差>阈值, 转step4;

Step4:调整定位区域, 转step2;

定位区域的计算

1) 定位区域初始化

2) 迭代过程中定位区域的调整

假设上一步运行G r i d L算法, 算出节点数量为M, 坐标为q={ (x 1, y 1) , ..., (x i, y i) , ..., (xM, yM) }。则当前迭代的定位区域包括M个等面积的正方形区域, 其中, 第i个区域中心坐标为 (x i, y i) , 边长可以根据实际情况设置。本文后续实验中, 正方形区域边长取值为上一步运行Grid L时网格边长的4倍。

Grid L算法描述

图1给出了Grid L算法的伪代码。表1给出了Grid L算法使用的符号及其解释。MT-GMM算法嵌套了内外两层循环。外层循环即算法第4行到第29行, 用来估计节点数量。假设节点数量M从1开始取值, 并随循环逐次递增, 根据 (M-1) 个节点坐标估计第M个节点坐标。当节点数量增加, 但模型BIC取值不增加时, 算法结束。内层循环即算法第11行到第20行, 用来调整外层循环确定的M个节点的位置坐标。当模型BIC取值最大时, 获得节点数量为M时的位置坐标。

算法第13行的函数find BIC (R, j) 根据前j个节点的位置坐标, 估计第 (j+1) 个节点的位置坐标。该函数分别假设第 (j+1) 个节点在定位区域内的每个网格中, 并分别计算相应的BIC取值, BIC取值最大时对应的网格坐标就是第 (j+1) 个节点的坐标。

实验

本文用仿真实验和实测实验分别验证算法的有效性和准确性, 使用Matlab 7.0来实现MTL-GMM算法。

实验使用的信道传播模型的参数取值如表2所示。实验用平均定位误差衡量算法的性能, 如公式 (6) 所示。

其中, M为节点数量, 节点i的实际坐标为Pri= (x ri, y ri) , 节点i的估计坐标为Pei= (x ei, yei) , 且i∈M。

仿真实验

我们用NCTUns v5.0[14]模拟实验场景, 将8个传感器分别放置在180m×300m的区域里, 将一个可移动的传感器做为信标节点RC, 如图2所示。图中叉号表示传感器节点所在的位置, 曲线表示RC的移动路径, 圆圈表示估计的传感器位置。传感器节点的通信半径设为100米。RC采集的RSS序列长度为300。

第一次迭代的网格边长为5米, 第二次为1米。表3给出了仿真实验的数据结果, 两次迭代估计的节点数量均为8个, 与实际相符, 节点坐标的定位误差由第一次迭代时的3.86米减小到第二次迭代时的0.93米。

实测实验

我们将4个Access Point (AP) 分布在学校实验室大楼二层, 将带有无线网卡的笔记本做为信标节点, 采集从AP发来的RSS, 同时记录笔记本移动的路线坐标。图3给出了AP的位置 (叉号表示) 和笔记本的移动路线 (实线表示) , 圆圈表示估计的节点位置。AP的通信半径为30米, 笔记本采集的RSS序列长度为120。

第一次迭代的网格边长为2米, 第二次为1米。表4给出了实测实验结果, 两次迭代估计的节点数量均为4个, 与实际相符, 节点坐标的定位误差由第一次迭代时的2.99米减小到第二次迭代时的1.83米。

结语

节点定位算法第4篇

无线传感器网络作为物联网的核心技术,是目前信息科学的前沿研究方向[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

节点定位算法第5篇

位置信息是无线传感器网络( WSN) 应用中需要的一项重要内容,它是地理路由和网络管理等系统功能的必要基础信息。在紧急医疗救助和战场态势侦测等应用中,位置信息对这些应用的实施效果起到至关重要的作用。比如在突发性灾难发生时,灾难现场区域广大,现场混乱,如果能够在救助中明确伤患者的位置并进行显示,一方面有利于快速、便捷地对伤患者进行紧急救治,另一方面有利于救援整体情况的查看和把握,使调度人员能够实时地了解现场状况,合理决策,精准调度。

鉴于位置信息的重要性,当前已经有很多关于定位算法的研究。这些研究中,根据定位对象的不同,主要分为WSN自身定位和WSN目标定位两类。前者关注于WSN部署后,根据其中某些已知位置的节点( 锚节点) 来求得其他需要定位的节点( 未知节点) 的位置。这一类的定位问题一般也是WSN目标定位的依据和基础。

已有的WSN自身定位算法可以根据不同的方式进行分类。依据定位所需信息的粒度可将定位算法和系统分为细粒度定位和粗粒度定位两类,前者根据信号强度或时间等参数来度量未知节点与锚节点的相对位置,结果较精准,但所需的代价和运算量较大; 后者根据与已知位置的接近度来度量,结果往往是一个范围,但所需代价较少,较著名的有Active Badge[1]和凸规划[2]等。在很多应用中,获知节点所在范围已经能够满足分簇、位置路由等操作的位置信息需求,且代价较小,有助于延长网络寿命。另外,根据定位算法是否需要进行测距,可以分为基于测距技术( range-based) 的定位和无须测距技术( range-free) 的定位两类[3],前者通过RSS( received signal strength)[4]、TOA( time of arrival)[5]等测距技术,运用三边测量、三角测量和最大似然估计等定位法求得节点位置[6],一般定位精度较高,但这些算法中多采用多次测量和循环定位求精等[7],导致大量计算和通信开销; 后者无须距离和角度信息,仅根据网络连通性等信息来实现,开销大大减少,更适用于低功耗和低成本的应用领域。但目前基于TOA测距的算法对TOA受设备计时精度的影响讨论较少,无法明确利用无线信号的TOA测距的限制。

1 普通节点定位算法流程

普通节点( N-Nds) 的定位是利用RSS值,通过基于模糊逻辑算法实现的。N-Nd定位算法流程如图1 所示。在A-Nd定位阶段,所有的A-Nd依靠自身装备的GPS模块确定自身位置。由于节点的部署区域是以固定的六边形网格方式进行划分的[8],A-Nd在确定自身位置后能够判断自身处于哪个网格。在N-Nd定位阶段,A-Nd周期性广播N-Nd定位信号。所有的N-Nd接收N-Nd定位信号,并通过基于模糊逻辑的粗粒度定位算法估算自身的大概位置。该算法将在下节进行详细介绍。上述流程重复进行若干次,从而减少由于信号传播受到的干扰带来的误差。

2 基于模糊逻辑的粗粒度定位算法

在N-Nd定位阶段,A-Nd周期性广播N-Nd定位信号[9]。设一个普通节点C可收到A1、A2…ANf共Nf个锚节点广播的内部定位信号,如图2 所示,锚节点的坐标( xA 1,yA 1) ,( xA 2,yA 2) …,( xA Nf,yA Nf) ,( xO,yO) 均为已知,且它们的自身坐标均包含在其广播的N-Nd定位信号中。此外,N-Nd定位信号中还包含该信号的发射功率值。

可以证明下述定理:

定理1: 在一个区域内,某个点对应于3 个以上非共线的信标节点所形成的RSS向量唯一地对应于该点坐标。

证明: 在如图2 所示情况中,取Nf= 2,即3 个信标节点,A1、A2、A3与C的距离为dA 1、dA 2和dA3。

取无线信号传播的对数- 常态分布模型:

式中,n为路径损耗指数,范围在2 ~ 6 之间; d0为近地参考距离,通过测试获得; Xσ为表示误差的均值为0 的高斯随机变量。另外有:

式中,PT为发射功率,节点i接收到N-Nd定位信号,由于发射功率和接收功率为已知,因此可据发射和接收功率的差值求出这些信号的RSS值,根据RSS值可求出节点C和A-Nd之间距离的估计值:

通过C接收到的相应的内部定位信号RSS值,利用式( 3) 可得到方程组:

可知当A1、A2和A3非共线时,方程组( 4) 的解唯一,且当Nf> 2 时,得到的超定方程组解也唯一。定理1 得证。

在本算法中,所有节点根据前述过程,可以求得自身的粗略位置,据此可以对自身所处的网格进行初步判断,节点可大致估计出自身所处网格区域,将该网格区域及其n级相邻的网格区域作为一个定位区域,将这些网格区域的6 个顶点及中心点作为参照点,根据预先定义的六边形网格半径r,可求出这Ns个参照点的坐标。n级相邻节点与某个网格区域之间相邻间隔的大小,以图2 中的0 号区域为例,其1 级相邻区域为与其直接相邻的1 ~ 6 号区域,2 级相邻区域增加了与1 ~ 6 号直接相邻的7 ~ 18 号区域。

n的取值根据网格区域划分中确定的网格大小,即r值确定,关系如下:

由n可求得定位区域的网格数目Ns:

取n = 1,则Ns= 31,不同参照点处收到的来自信标节点的内部定位信号RSS组成的向量均不相同[10],所有参照点的RSS向量组成向量表:

式中,RSSINs Aj的求法如下:

首先根据参照点i的坐标( xi,yi) ,求得i与信标节点Aj的距离:

再根据式( 1) 和式( 2) 求得RSSIi A j。

C收到的来自A1、A2、…ANf、O的内部定位信号RSS组成向量:

根据模糊数学中的测度贴近度计算方法[11],利用最大值、最小值贴近度公式计算贴近度:

式中,“∧”为取小运算,“∨”为取大运算。求得C与各个参照点的贴近度序列:

之后对S进行排序,并取其中贴近度最大的3 个参照点坐标。可以证明,这3 个参照点其质心位置为C的定位结果:

进行M次迭代后,得到M个定位结果,求这些结果的平均值,得到最终定位结果。

3 算法复杂度和精度分析

整个计算过程中没有出现高次方程求解,只有一些简单的大小比较计算,计算复杂度为O( MNs) 。

节点定位精度受网格区域的大小和参照点数量的影响。精度定义 ρ 如下:

式中,derr为所有节点定位位置与真实位置间的平均距离。当干扰一定时,参照点数目NS越大,定位精度越高[12]。而根据式(5)和式(6)可知,r减小时,n缓慢增加,而NS会随n而急剧增加。在干扰较小的情况下,当NS=66时,精度可稳定在0.995 9。当相邻级别n=2时,可求得NS=72,因此一般取n≤2即可满足大部分定位需求,因此一般至少取r=rmax/2。

4 结束语

提出了一种基于RSS和模糊逻辑算法的WSN节点自定位方法。相比其他定位算法,本算法利用合适的六边形网格划分,采集所有信标节点位置信息和RSS,结合使用模糊数学中的测度贴近度计算方法,利用基于模糊逻辑的粗粒度定位算法估算自身的大概位置。理论分析证明,所提算法降低了计算复杂度,减少了计算开销,节约了成本,提高了定位精度,增强了算法的实用性。

参考文献

[1]Want R,Hopper A,Falcao V,et al.The Active Badge Location System.ACM Trans.on Information Systems[J].1992,10(1):91-102.

[2]Doherty L.Algorithms for Position and Data Recovery in Wireless Sensor Networks[MS.Thesis].Berkeley:University of California,2000.

[3]左冬梅.无线传感器网络安全定位技术研究[D].哈尔滨:哈尔滨工程大学,2011,30-35.

[4]Girod L,Bychovskiy V,Elson J,etal.Locating tiny Sensors in Time and Space:A Case Study[C]∥In:Werner B,ed.Proc.of the 2002 IEEE Int’l Conf.on Computer Design:VLSI in Computers and Processors.Freiburg:IEEE Computer Society,2002:214-219.

[5]Harter A,Hopper A,Steggles P,Ward A,Webster P.The Anatomy of a Context-aware Application[C]∥In:Proc.of the 5th Annual ACM/IEEE Int’l Conf.on Mobile Computing and Networking.Seattle:ACM Press,1999:59-68.

[6]王琰,王喆.无线传感器网络节点定位算法研究[J].无线电通信技术,2011,37(5):21-23,27.

[7]王辉,熊飞,谷源涛.移动Mesh网络定位系统研究[J].无线电通信技术,2012,38(1):12-15.

[8]任明明,谢志军,金光,等.传感网络中基于移动信标的网格扫描定位算法[J].无线电通信技术,2014,40(2):4-6,59.

[9]杨小勇,杨荣,李彬.一种新型无线传感器网络分布式定位算法[J].无线电通信技术,2012,38(3):14-17.

[10]郭龙,熊伟,李牧东.一种基于WSN的机器人三维精确定位算法[J].无线电工程,2012,42(8):5-7.

[11]Janusz Kacprzyk,Fuzzy reasoning in decision making and optimization[M].Berlin Heidelberg:SpringerVerlag,2002.

节点定位算法第6篇

无线传感器网络的应用中, 位置信息是节点采集数据时不可缺少的部分, 没有位置信息的监测信息通常是毫无意义的。确定事件发生的位置或采集数据的节点位置是无线传感器网络最基本的功能之一。为了能够提供有效的位置信息, 随机布置的传感器节点在网络部署完成后必须能够确定自身所在的位置。一般的定位算法分类为基于距离定位算法和距离无关定位算法。基于距离的定位能够实现节点的精确定位, 但往往对节点的硬件要求较高。出于硬件成本、能耗等方面的考虑, 使用距离无关 (Range-free) 的节点定位技术可不需要测量节点之间的绝对距离或者方位, 降低了对节点的硬件要求, 但定位误差相应有所增加。

无线传感器网络的节点定位策略通常使用少量位置已知的信标节点, 其它位置未知的普通节点从它们接收到的信息估计自己所处的位置。现有节点定位方法大多采用上述策略, 典型的Range-free定位算法主要包括:质心定位、Amorphous、SPA (self-positioning algorithm) 、凸规划、APS (ad hoc positioning system、APIT等。然而这些方法都没有考虑节点 (包括普通节点和信标节点) 具有位置移动性的网络情形。节点的移动性会导致定位过程变得更加困难而且复杂。本文使用Monte Carlo定位 (MCL) 算法来解决节点具有移动性的无线传感器网络的节点定位问题, 并针对MCL算法的一些应用限制进行了改进。

1 MCL定位算法

MCL算法的核心思想是利用一系列加权采样值表示可能位置的后验概率分布, 目的在于确定节点所在可能位置的后验概率分布。算法每一步都包括位置预测和位置更新两个阶段。位置预测阶段是利用m个加权采样值对后验概率分布进行描述的过程, 位置更新阶段则是通过重要性采样操作对其进行及时不断更新, 采样值的权重值从0和1中取值。

MCL定位算法的基本步骤:

1.1位置估计

无线传感器网络节点的移动定位问题可以在如下状态空间内描述。以t表示离散时间, lt表示t时刻节点的位置分布, ot表示节点在t-1时刻到t时刻之间接收到的来自信标节点的观测值。转换方程p (lt|lt-1) 表示基于节点先前位置对其当前所在位置的估计, 观测方程p (lt|ot) 表示在给定观测值的情况下节点位于位置lt的概率。算法的目标是对节点位置的滤波分布p (lt|o0, o1, …, ot) 随时间进行反复估计。用一组采样值Lt (N个) 表示节点的位置分布lt, 而且每一时间段内算法要对采样序列进行反复计算, 由于Lt-1是对先前所有观测值的一个集中反映, 因此仅使用Lt-1和ot就可以计算出lt。

位置估计算法的实现流程:

(1) 初始化。节点最初不具备任何关于其自身所在N个位置的先验知识, 需要对其进行初始化操作 (N表示算法执行过程中所要维持的采样数) 。

L0=[节点部署区域内随机选择的N个可能位置]

(2) 循环计算。根据Lt-1、上一时间段内节点的可能位置序列以及新的观测值ot计算出节点新的可能位置Lt。

在算法起始阶段节点对其所在的位置没有任何先验知识, 因此可由质心算法估计初始位置。质心算法的核心思想是:普通节点以所有在其通信范围内的信标节点的几何质心作为自己的估计位置。其实现过程非常简单:信标节点向邻居节点广播一个信标信号, 信号中包含有信标节点自身的ID和位置信息。当位置未知的普通节点接收到来自信标节点的信标信号数量超过某一个预设的门限值后, 该节点认为与此信标节点连通, 并将自身位置确定为所有与之连通的信标节点所组成的多边形的质心。

初始位置确定后的每一时间段内, 位置序列都会根据节点的运动和新的观测信息进行更新。节点位置的估计可以通过计算集合Lt内节点的所有可能位置的平均值获得。

1.2位置预测

在MCL算法位置预测阶段, 节点从前一阶段计算出的一组可能位置Lt-1开始, 对每个采样值应用节点移动模型从而获得一组新的采样值Lt。假设节点的移动速度和方向未知, 而只知道其速度值小于vmax;那么, 如果lundefined是节点的一个可能位置, 那么节点所在的当前可能位置则位于以lundefined为圆心、半径为vmax的圆形区域内。如果用d (l1, l2) 表示两点l1和l2之间的欧几里德几何距离, 而且节点的移动速度在区间[0, vmax]上服从均匀分布, 那么节点基于先前位置的当前位置估计的概率分布可以通过以下均匀分布的形式给出。

因此, 在预测阶段计算出的节点可能位置序列R就是以点集Lt-1中的任意一点为圆心且半径为vmax的圆形区域。

1.3位置滤波

在滤波阶段, 节点需要根据所获得的新观测值滤除不可能的位置信息。为了便于描述和分析, 假设在t时刻每个位于信标节点无线射程范围内的节点都可以侦听到来自信标节点的位置信息广播。在实际的网络部署情况下, 需要考虑网络冲突并解决消息丢失的问题。

如图1, 节点在t0时刻由位置l0开始移动, 并在t1时刻到达位置l1, 节点离开区域Ⅰ并到达区域Ⅱ, 但始终在区域Ⅲ内。到达节点和离开节点都为节点的位置估计提供信息, 节点知道在t0时刻位于以l0为圆心且半径为r的圆形区域内的信标节点, 在t1时刻并不在l1为圆心且半径为r的圆形区域内。

图2描述了节点的位置滤波条件。图中, S表示节点N能侦听到的所有信标节点分组, T表示节点N的邻居节点可以侦听到而节点N本身无法侦听到的全部信标节点。因此, 节点位置l的滤波条件可以由式 (2) 表示。

filter (l) =∀s∈S, d (l, s) ≤r∧∀s∈T, r

如果滤波条件为假, 那么节点位置的概率分布p (lt|ot) 值为零, 否则p (lt|ot) 将符合均匀分布, 这样, 就可以从节点的所有可能位置集合中去除那些与观测值不一致的位置。经滤波后, 节点剩余的可能位置也许会少于N个。预测过程和滤波过程将不断重复进行, 并结合已经发现的节点可能位置, 直至获得节点的至少N个可能位置。

1.4重要性采样

算法的最终目标是估计节点可能位置的后验概率分布p (lt|o0, o1, …, ot) 。首先, 通过一个标准化重要性采样函数π获得一系列相互独立的节点位置采样值;然后, 对每个采样值的权重值进行调整并且使用这些权重值对节点所在可能位置的后验概率分布作出估计。算法采用了下列递归式重要性函数。

undefined. (3)

undefined. (4)

undefined. (5)

式 (3) 表示节点的位置预测, 节点借助先前所在的可能位置预测其当前的可能位置。式 (4) 表示节点的位置更新, 节点根据获得的观测值对新的采样值不断进行权重值更新与调整。然后, 通过式 (5) 对权重值undefinedundefined进行归一化处理得到wundefined, 利用权重值序列 (lundefined, wundefined) 对节点位置的后验概率分布作出估计。通过式 (3) 和式 (4) 的反复计算, 很容易地确定概率值p (lk|lk-1) 和p (lt|ot) 的大小。

2 MCL算法优化

传感器节点在计算资源与存储资源等方面一般比较紧缺, 可通过多边形内点测试法首先近似确定节点的运行方向, 该方法完全基于节点间的连通性, 仅需要信标节点的跳数位置广播信息, 因此对节点没有额外的功耗和硬件需求。图3为多边形内点测试法的一种情况, 如图3 (a) 假设M获得与A之间的跳数为4, 则节点1与A之间的跳数为3, 节点2与A之间跳数为5;M获得与B之间的跳数为3, 则节点2与B之间的跳数为2, 节点1与B之间的跳数为4。当M移动到节点1位置, 则可以得出节点M靠近了节点A远离了节点B, 可以得出节点M不能同时靠近或远离三个顶点, 必定在三角形内部, 当节点M同时靠近或远离三个顶点, 必定在三角形外部。对图3 (b) 当节点M从三角形ABC内离开进入三角形ABD中时, 即可得到节点的大致运行方向。则式 (2) 的滤波条件可简化为

filter (l) =∀s∈S, d (l, s) ≤r∧∀s∈T′, r

此处的T′为节点N在区域ABD内的邻居节点可以侦听到而节点N本身无法侦听到的全部信标节点。

对节点运行方向的估计可大大减少MCL算法的位置预测和位置滤波阶段的计算量, 节省了节点的能耗。并且更加容易滤除与观测值不一致的位置, 提高定位精度。

(a) 三角形内点测试法节点位置 (b) 三角形内点测试法节点方向

3算法性能评价

在一定的通讯开销和硬件配置条件下, 评价一种节点定位方法优劣的重要标准是位置估计精度的高低。通过仿真对MCL定位算法、改进后的MCL定位算法和质心定位 (Centroid) 算法进行了比较。

仿真实验过程中, 无线传感器网络、节点以及算法的相关参数都是不断变化的。节点随机部署在一个500 m×500 m的矩形区域内, 而且假定信标节点与普通节点的无线传输距离为恒定值r (r=50 m) , 节点的位置信息广播之间的时间间隔为固定值tu并且以节点在每一时间段tu内移动的距离r表示节点移动速度。

由图4 (a) 可以看出, MCL定位算法的精度在初始阶段会随着时间变化提升很快并进入稳定阶段, 在稳定阶段, 节点新的观测值 (位置滤波器) 与由于节点移动带来的不确定性对定位精度的影响达到某种平衡, 位置估计误差将最终稳定在一个最小值上下波动。可以看出MCL算法的定位精度与质心定位算法相比有着相当大的优势。

图4 (b) 中可以看出改进后的MCL定位算法能够更快的达到稳定, 并且定位精度也有了少许提升。

4结语

本文提出了将MCL算法应用于无线传感器网络节点定位中, 在节点随机运动的情况下, 不需要配备额外的硬件设施, 就可以获得较高的定位精度, 解决了具有移动性的无线传感器网络中的节点定位问题。并在算法初始阶段结合质心算法进行定位, 通过估计节点方向来简化算法, 优化了MCL算法的定位性能。

摘要：介绍了Monte Carlo (MCL) 定位算法在无线传感网络节点定位中的应用, 对MCL算法的位置估计、位置预测、位置滤波等方面进行了详细说明, 针对算法中存在的初始位置不确定的问题进行了改进, 并对算法进行了简化。

关键词：MCL,无线传感网络,节点定位

参考文献

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

[2]孔凡天.无线传感器网络节点定位与数据融合技术研究及实现[D].武汉:华中科技大学, 2006.

[3]Doucet A, Freitas De J, Gordon N.Sequential MonteCarlo Methods in Practice[M].NewYork:Springer, 2000.

节点定位算法第7篇

无线传感器定位可分为基于测距的定位算法和无需测距的定位算法,其主要区别在于是否需要距离信息。基于测距的定位算法中节点需使用测距技术获得距离信息,优点是定位精度高但需要额外的硬件设备,常用的测距技术有接收信号强度RSSI、信号到达时间TOA、信号到达时间差TDOA及信号到达角度AOA等; 无需测距的定位算法仅依靠相邻节点间的连通关系进行定位,无需基础网络设施的支持,但定位精度较低［4］。

传统的节点定位算法常采用最小二乘法求解非线性方程组,很容易受到测距误差的影响。为了进一步提高定位精度,笔者将自适应策略引入到粒子群优化节点定位算法中,有效地克服了粒子群优化( Particle Swarm Optimization,PSO) 算法容易产生种群的趋同效应,出现早熟收敛、易陷入局部极值、在搜索后期停滞不前而导致种群的优化性能不佳的问题。

1 粒子群优化算法

粒子群优化( Particle Swarm Optimization,PSO) 算法是由Kennedy和Eberhart在1995 年提出的。PSO算法是一种模拟鸟群迁徙和觅食行为的群体智能全局随机优化计算方法,通过种群中个体间的竞争与协调,搜索复杂空间的最优解。PSO算法将种群中的每个个体看成一个质量和体积都为零的粒子,粒子根据自身历史最优位置和种群历史最优位置不断更新自身的速度和位置,从而实现进化［5］。

在PSO算法中,种群中共有N个粒子,每个粒子可以看成优化问题在D维搜索空间的一个潜在解。每一个粒子都有一个由目标函数决定的适应度值,该值的大小决定了粒子的优劣程度。通过所有粒子的适应度值可以判定出每个粒子的自身最佳位置和全局最佳位置,同时每个粒子还有一个决定其飞行方向和距离的速度。所有的粒子以一定的规则在搜索空间中搜索最优解。每次迭代时,粒子通过局部极值和全局极值来更新自己的信息。局部极值就是粒子本身到目前为止所找到的最优位置,而全局极值就是整个种群到目前为止所找到的最优位置。假设一个种群有N个粒子随机地分布在D维搜索空间中,其中第i个粒子在搜索空间中的位置向量可表示为:

第i个粒子的飞行速度向量可表示为:

第i个粒子到目前为止搜索的局部极值表示为:

整个种群的全局极值可表示为:

每个粒子按如下公式更新自己的速度向量和位置向量:

式中c1、c2———加速因子,根据经验通常都取2;

k ———迭代次数;

rand( ) ———在( 0,1) 范围内的随机数;

ω ———惯性权重。

式( 5) 右边可分为3 个部分,第一部分称为“惯性部分”,反映粒子维持先前速度的程度; 第二部称为“认知部分”,反映粒子本身历史最佳位置对现在的影响; 第三部分称为“社会部分”,反映种群对粒子的影响,粒子有向全局最佳位置靠拢的趋势。为了防止粒子飞出搜索空间,通常对粒子的速度进行一定的限制。

在PSO算法中存在粒子向种群全局历史最佳位置和自身局部历史最佳位置聚集时容易产生种群趋同效应的现象,并导致早熟收敛、易陷入局部极值、在搜索后期停滞不前而导致种群的优化性能不佳的问题,同时,PSO算法的优化性能还依赖于参数的取值情况。为克服这些不足,文献[6]提出了用指数变化的惯性权重取值方法来优化复杂的非线性方程组,笔者在此基础上进一步简化算法,提出了一种基于自适应策略的粒子群优化节点定位算法,该算法从惯性权重和全局最优位置两个方面对原有的PSO算法进行改进,实现了在不增加额外硬件的条件下对无线传感器网络节点定位在定位精度和计算耗时上的进一步优化。

2 自适应策略

笔者提出的基于自适应策略的改进算法主要包括两个方面: 一是惯性权重的自适应取值方法;二是从适应度值进行改进的全局最优位置的自适应变异操作。

2. 1 惯性权重的自适应取值方法

惯性权重 ω 是PSO算法中最重要的改进参数,其反映了粒子先前的飞行速度对现在值的影响。当其取值较大时,全局搜索能力强,收敛速度快,但缺点是得到的解精度不够; 当取值较小时,局部搜索能力强、得到的解的精度高,但存在收敛速度较慢且可能陷入局部极值的缺点。合适的 ω值能够平衡算法的全局搜索能力和局部搜索能力,从而得到最佳的优化解。

笔者提出的自适应的惯性权重取值方法,其设计思想主要有两个过程: 在定位算法迭代前期ω 取较大值,实现快速收敛到最优解附近,后期则取较小值求高精度解; 同时该算法在适应度值越大时全局搜索能力越高,从而加快向全局最优位置的聚集速度,粒子适应度值较小时局部搜索能力越高,从而得到高精度的解。笔者提出的惯性权重的自适应取值公式如下:

其中当 ω2> ω1时,一般取 ω1= 0. 3、ω2=0. 8,T为当前迭代次数,Tmax为最大迭代次数。为了防止 ω( i) 在迭代后期取值过小,笔者对 ω( i)的值设置了下限0. 2,当 ω ( i) 低于下限值时ω( i) = 0. 2。f( i) 为第i个粒子的适应度值,fmax、fmin为所有种群中粒子适应度值的最大值和最小值,相应的粒子速度更新公式变为下式:

2. 2 全局最优位置的自适应变异操作

粒子的适应度值可以反映粒子当前位置的优劣程度,把种群所有粒子的当前适应度值看作一个样本,这个样本的方差就可以用来定量描述整个种群的聚集程度。种群越密集,表明整个种群的群居搜索能力变差,此时就需要对全局最优位置进行变异操作,保证整个种群能跳出当前的搜索区域。粒子群的种群适应度值方差 δ2的计算公式为:

其中favg为种群中所有粒子适应度值的平均值; F为归一化因子,通常F = max ( 1,| f( i) -favg| ) 。其全局最优位置发生变异的概率计算公式如下:

其中pmax、pmin分别为gbest进行变异操作概率的最大值和最小值,通常取pmax= 0. 4,pmin= 0. 3。全局最优位置变异操作的公式为:

通过增加一个随机扰动来对gbest进行变异操作,其中gbest_k是gbest的第k维分量。

2. 3 基于自适应策略的节点定位流程

假设未知节点K( x,y) 有3 个以上的邻居连通锚节点Ki( xi,yi) ,其中i = 1,2,…,n。采用RS-SI测距方法测得未知节点到锚节点的距离为di。另,距离其中( x',y') 为未知节点的估计位置。定义适应度值函数为:

其值越小,对该点的定位就越精确。节点定位的具体流程如下:

a. 在搜索空间( 目标区域) 随机部署一定数目的锚节点和未知节点,节点启动后锚节点以周期T向相邻节点发送自己的信息( 主要包括节点ID、位置信息) ;

b. 未知节点根据邻居连通锚节点的相关信息和RSSI模型公式计算出自身到锚节点间的距离;

c. 存在邻居连通锚节点的未知节点在自身处运行笔者改进后的PSO算法,计算自身定位结果。

3 实验仿真

在MATLAB R2008a中对基于自适应策略的粒子群优化节点定位算法的性能进行验证,并与常用的极大似然估计( Maximum Likelihood,ML)进行对比分析。

在本实验中,假设无线传感器节点部署在100m × 100m的二维平面区域中,在此区域内随机分布5 个传感器节点,其中4 个为锚节点,其坐标分别为A ( 22. 23,48. 64) 、B ( 62. 48,2. 46) 、C( 44. 60,80. 42) 、D( 85. 22,70. 48 ) ,未知节点的实际坐标为E( 82. 24,46. 32) 。

基于自适应策略的粒子群优化定位算法中的参数设置为: ω1= 0. 3、ω2= 0. 8,pmax= 0. 4,pmin=0. 3,ω ( i)min= 0. 2,c1= c2= 2。种群粒子总数大小N = 30,总的迭代次数T = 100,粒子每维最大位置为100m,最大速度为10m/s。为了减少实验中随机误差的干扰,进行100 次定位实验得到最终的实验数据。在无线传感器节点定位过程中,测距误差直接决定着定位的进度和稳定度。因此,本实验以测距误差作为实验的前提条件,在不同测距误差的条件下比较ML算法和笔者算法的性能优劣。在引入相同测距误差的条件下,分别对两种算法做100 次的定位运算,并在不同测距误差的情况下,重复进行上述定位运算。两种算法定位结果分别见表1、2。

图1、2 分别反映了测距误差对平均定位误差和定位方差的影响,图3 为适应度值与迭代次数的关系。

通过实验数据可以得到:

a. 从图1 可看出,在给定的5 种测距误差条件下,笔者算法的平均定位误差要比ML算法小,说明该算法的定位精度要高于ML算法的。从图2 可以看出,笔者算法的定位方差要比ML算法小,说明该算法的稳定性要高于ML算法的。

b. 从图1、2 可以进一步发现,当系统测距误差较小时,两种定位算法的性能相差无几,但随着距离误差变大,笔者算法的优良定位性能就凸显出来,说明该算法在一定程度上可以减轻测距误差对定位精度的影响。

c. 图3 是笔者算法在测距误差为5% 时的一次定位过程,从图中可以看出算法在迭代不到10 次时就可以收敛到一个精度较高的优化解,收敛速度较快,能耗较低,适合应用在对能耗有较高要求的无线定位系统中。

4 结束语

节点定位算法第8篇

1. TNS架构包括:

(1) 故障节点集合Λ; (2) 告警节点集合Μ; (3) 症状节点集合S={s_node1, s_node2, …, s_nodem}, 其中s_nodei表示症状节点i, (4) 故障集合与症状集合之间的相关矩阵Dm, n。为了方便算法的描述, 本文对上述TNS架构做出两点假设, 一是故障节点集合Λ中的各个节点之间相互独立;二是故障节点和症状节点之间因果强度不变, 即矩阵Dm, n中元素的大小不发生改变。为此, 可以得出故障定位在本架构中的数学表示式, 即在故障节点集Λ中获取一个故障诊断队列, 使得该队列在告警发生时的概率p (β|Μ) 最大, 也即该故障队列的置信度最高。

2. 算法TNSFLA的设计和实现:

算法TNSFLA的故障定位过程分为两个阶段, 故障诊断队列创建阶段和诊断队列元素选择阶段。其中, 第一个阶段创建能够解释网络系统接收到的告警节点集对应的症状集合的故障子集;第二个阶段对阶段一中创建的故障诊断队列的各个元素, 计算各个故障发生的置信度, 从中选出置信度最大的故障诊断元素作为最终的结果。

2.1 其中诊断队列最优解的具体选取过程:

(1) 首先来计算队列中各个子集元素的置信度, 比较这些置信度的大小, 并选择发生概率最大的一个作为最终结果。 (2) 若其中有两个以上的元素置信度相同, 则继续对这些子集元素内包含的故障节点和虚假故障节点进行比较, 首先比较故障节点的个数, 选取故障节点个数最少的那个子集作为最终解。 (3) 若仍然有两个以上子集故障节点个数相同, 则比较他们内部虚假故障节点的个数, 选择虚假故障节点最少的那个子集作为最终解。

2.2 算法T N S F L A的执行过程示例:

假设系统依次接收到了告警集合Μ={e_node1, e_node2, e_node4, e_node5, e_node6}, 设max_true_fault=3, max_false_fault=2.算法的处理过程如下:

(1) 初始化故障集合队列β=Φ, 根据网络故障系统接收到的告警节点集Μ得到对应的症状节点集S={s_node1, s_node2, s_node4s_node5, s_node6};

(2) 求得症状节点s_node1, 对应的故障子集F1={f_node1, f_node2if_node1}, 创建β1={{f_node1}, {f_node2}, {if_node1}};

(3) 求得症状节点s_node2, 对应的故障子集F2={f_node2, f_node3if_node2}, 由于β1中故障节点元素{f_node2}可以解释症状节点s_node2, 所以将{f_node2}直接加入到队列集合β2中, 然后遍历集合β1-β2中的其它元素, 根据算法TNSFLA的3点启发性判断能否将故障加入。

(4) 依次处理症状s_node4, s_node6;处理完所有事件后, 得到能够解释系统告警即{e_node1, e_node2, e_node4, e_node5, e_node6}的故障子集为{{f_node2, f_node4}, {if_node1, f_node3, f_node4, }, {f_node1f_node2, if_node6}, {f_node2, if_node4, if_node6}, {f_node1, f_node3if_node6}}。最后根据最优解选取的方法, 分别求取这些故障诊断子集的置信度, 获取最终的故障原因。

3. 仿真结果与分析:

将仿真场景中网络节点的数目设置为1～100个, 通过不同数目节点的设置构建不同的网络实验场景。同时对穷举法 (ES, Exhaustive Search) 、基于拉格朗日松弛法的故障定位算法 (LRA, Lagrangian Relaxation Algorithm) 进行了实现, 将其作为本文算法的对比方案。仿真结果表明, 当网络系统中存在告警丢失和虚假故障的情况下, 该算法在故障检测率、误检率以及定位时间方面体现出极大的优越性。

摘要：网络故障管理技术是通信系统中网络管理的核心, 是维持网络高效运行的关键因素, 而故障定位检测作为网络故障管理的关键功能之一, 其技术、算法实现的好坏将决定整个网络自动化的成败。本文即针对目前网络系统中由于不同程度的告警丢失和虚假告警的情况, 造成故障检测精确度降低、无法快速诊断的问题, 提出了相应的解决方案。

关键词：网络故障管理,故障定位,分层诊断,TNSFLA

参考文献

[1]潘朝阳, 曾劲柏, 黎连业等.计算机网络故障诊断与排除.北京:清华大学出版社, 2007

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【节点定位算法】相关文章：

移动节点定位06-20

节点部署算法07-17

基于移动汇聚节点的分团路由算法的设计01-19

基于粒子群——蚁群混合算法的薄板件定位策略优化01-17

感知节点05-07

“节点”把握05-16

节点数据05-28