法律状态公告日
法律状态信息
法律状态
2023-01-13
专利实施许可合同备案的生效 IPC(主分类):H04W64/00 专利申请号:2017109884251 专利号:ZL2017109884251 合同备案号:X2022450000522 让与人:桂林理工大学 受让人:广西长城宽带网络服务有限公司 发明名称:一种基于交流SCE-PSO算法的无线传感器网络节点三维定位方法 申请日:20171021 申请公布日:20180119 授权公告日:20200218 许可种类:普通许可 备案日期:20221229
专利实施许可合同备案的生效、变更及注销
2020-02-18
授权
授权
2018-02-13
实质审查的生效 IPC(主分类):H04W64/00 申请日:20171021
实质审查的生效
2018-01-19
公开
公开
技术领域
本发明属于无线传感器网络中的节点定位领域。
背景技术
无线传感器网络(Wireless Sensor Networks,WSN)节点的三维定位是当前的研究热点之一。根据是否需要测量节点之间的距离,无线传感器网络的节点定位方法可以划分为基于测距和基于非测距的两种方法。其中基于测距的方法,由于定位精度高在无线传感器网络节点定位中被广泛采用。基于测距的定位方法首先要测量节点之间的距离或角度,常用的测量方法有接收信号强度指示 (Received Signal Strength Indicator,RSSI)、到达时间(Time of Arrival,TOA)、到达时间不同(Time Difference of Arrival,TDOA)和到达角度(Angle of Arrival, AOA)。
获取节点之间的距离或角度信息后,基于测距的方法就可以采用一些定位方法对未知节点进行定位,其中一类方法是把获取的距离或角度信息看作约束条件,将其转化为一个目标函数,然后用各种优化算法寻找该目标函数的最小值,从而对未知节点进行定位。优化方法可分为传统的优化方法和生物启发式优化方法。
传统的优化方法基于确定的搜索策略,在满足一定的限制条件下,利用优化问题的导数、梯度等数学性质进行求解。该类方法的缺点是运算复杂度较高,并且随着问题的维数的增大其复杂度以指数倍增加,生物启发式优化方法可以有效地避免这个问题,使计算更加有效,对优化问题所对应的函数形式不做任何假设,而且不要求目标函数的连续性或可导性的假设,算法简单,易于实现。
常见的生物启发式优化算法包括:模拟退火算法(Simulated Annealing,SA)、蚁群算法(Ant Colony Optimization,ACO)、遗传算法(Genetic Algorithm,GA)、人工蜂群算法(Artificial Bee Colony,ABC)、细菌觅食算法(Bacterial Foraging Algorithm,BFA)、粒子群算法(Particle Swarm Optimization,PSO)。与其他生物启发式优化算法相比,粒子群算法具有容易执行,收敛速度比较快的优点。尤其是求解的问题维数越多,其优势越明显。因此,粒子群算法非常适用于无线传感器网络节点的三维定位。但是,在运行过程中,粒子群算法可能会陷入局部最优,出现早熟收敛现象。
针对无线传感器网络节点三维定位采用粒子群算法时,粒子在搜索过程中会陷入局部最优,出现早熟收敛,从而导致节点定位精度较低的问题,我们曾经提出SCE-PSO算法,该算法通过与SCE-UA(shuffling complex evolution-University of Arizona)算法相结合,增加了搜索过程中粒子的多样性,从而减少了粒子陷入局部最优的概率,提高了解的质量。在SCE-PSO算法中,采用粒子群算法进化每一个复合形。每一个复合形在进化过程中,其粒子的速度用下面的公式(1)更新。
vi(t+1)=w·vi(t)+c1·r1[pi-xi(t)]+c2·r2[g-xi(t)](1)
公式(1)中pi是第i个粒子自己所找到的最优解,g是该复合形中的粒子所找到的最优解;w是惯性权重,c1和c2是学习因子;r1和r2是在(0,1)区间上服从均匀分布的随机数。
SCE-PSO算法中的速度更新公式(1)有三部分组成,第一部分是粒子先前的速度,说明了粒子目前的状态,具有平衡全局和局部搜索的能力;第二部分是认知部分,表示粒子本身的思考,使粒子具有足够强的全局搜索能力,避免局部极小;第三部分为群体部分,体现了每个复合形内部的粒子间的信息共享。但是SCE-PSO算法中存在多个复合形,而公式(1)并没有体现各个复合形之间的信息交流。这就是SCE-PSO算法的缺点。
发明内容
针对SCE-PSO算法的速度更新公式没有体现各个复合形之间的信息交流的缺点,本发明提出了一种改进的SCE-PSO算法—交流SCE-PSO算法。在该算法中,用下面的公式(2)作为粒子速度更新的公式。
vi(t+1)=w·vi(t)+c1·r1[pi-xi(t)]+c2·r2[g-xi(t)]+c3·r3[e-xi(t)](2)公式(2)中,e是所有复合形中的粒子所找到的最优解。可以看出,交流SCE-PSO>
具体实现过程如下:
1.粒子群算法
粒子群优化算法的基本思想是:将优化问题的每一个解看作一个微粒,每个微粒在多维搜索空间中以一定的速度飞行,通过目标函数的适应度值衡量微粒的优劣,每个微粒能够通过自己的飞行经验以及其他微粒的飞行经验,动态地调整自己的飞行速度,从而向群体中最好的微粒位置飞行,最终搜索到优化问题的最优解。假设求解的问题为n维,粒子群算法的求解步骤如下:
(1)初始化各参数,包括加速常数c1和c2,最大迭代次数Tmax,粒子的速度范围[vmin,vmax],粒子的数目s和惯性权重的范围[ωmin,ωmax]。
(2)将迭代次数设置为t=1,随机产生初始粒子的位置
(3)将
(4)评价每一个粒子,计算每个粒子的适应度值
(5)用公式(1)更新粒子的速度,分别根据公式(3)和公式(4)更新惯性权重和粒子的位置。
在更新过程中,如果
(6)让迭代次数t=t+1,然后检验t是否小于Tmax,若条件满足转入步骤(4),否则,算法停止,此时gd就是问题的解。
2.SCE-UA算法
SCE-UA算法基本思路是将基于确定性的复合形搜索技术和自然界中生物竞争进化原理相结合,用来求解最小化问题,融合了确定性方法、随机性方法、竞争进化、复合形混合等概念,从而保证了SCE-UA算法搜索的灵活性、全局性、一致性和有效性等。假设求解的问题为n维,SCE-UA算法的主要步骤如下:
(1)初始化。选取参与进化的复合形个数p(p≥1)和每个复合形所包含的顶点数目m(m≥n+1),并计算样本点数目s=p×m。
(2)产生样本点。在可行域内随机产生s个样本点x1,x2,…,xs,分别计算每一个点xi的函数值fi=f(xi),i=1,2,…,s。
(3)样本点排序。把s个样本点(xi,fi)按照函数值的升序排列,排序后仍记为(xi,fi),i=1,2,…,s,也就是f1≤f2≤…≤fs,记D={(xi,fi),i=1,2,…,>
(4)划分复合形群体。将D划分为p个复合形A1,A2,…,Ap,每个复合形含有m个点,其中
(5)复合形进化。按照下山单纯形算法分别进化每一个复合形。
(6)复合形混合。把进化后的每个复合形的所有顶点组合成新的点集,再次按函数值fi的升序排列,排序后仍记为D,对D按目标函数的升序进行排列。
(7)收敛性判断。如果满足收敛条件则停止迭代,此时具有最小函数值的粒子的位置就是问题的解,否则回到第(4)步。
3.SCE-PSO算法和交流SCE-PSO算法
SCE-PSO算法综合了SCE-UA算法和PSO算法的优点,并且改进了SCE-UA 算法和PSO算法的缺点。在SCE-UA算法中,采用的是下山单纯形算法进化每一个复合形。但是下山单纯形算法是用多面体来逐步逼近问题的最佳值。如果待优化问题的维数比较大,其进化过程就显得比较复杂,所求出解的质量也不高,而且收敛速度也相对缓慢。而PSO算法没有选择、交叉、变异等操作,其收敛速度较快,而且收敛速度受优化问题维数的影响也比较小,因此比较适用于无线传感器网络节点的三维定位。
鉴于上述思想,在SCE-PSO算法中,用粒子群算法代替下山单纯形算法去进化SCE-UA算法中每一个复合形。这样可以克服传统SCE-UA算法的缺点,提高收敛速度,增加求解高维数问题的解的质量;同时也可以利用SCE-UA算法中的洗牌策略(复合形混合之后,再重新划分)保持粒子的多样性,从而克服粒子群算法的缺点,减少其出现早熟收敛的概率。
在粒子的搜索过程中,SCE-PSO算法的速度更新公式(1)只有每个复合形内部粒子间的信息共享,并不包含各个复合形之间的信息交流。因此,需要对 SCE-PSO算法进行改进。为此,本发明提出了交流SCE-PSO算法。
在交流SCE-PSO算法中,用公式(2)取代公式(1)作为粒子速度更新的公式。与公式(1)相比,公式(2)增加了复合形之间的信息交流,因此与SCE-PSO 算法粒子相比,在搜索的过程中,交流SCE-PSO算法中的粒子能够获取更多的信息,从而可以加快收敛速度,提高解的质量;而且交流SCE-PSO算法也继承了SCE-PSO算法的优点,其受优化问题维数的影响较小,非常适合无线传感器网络节点三维定位。
4.目标函数
使用生物启发式优化算法求解问题需要一个目标函数去评价每个候选解的质量。对于无线传感器网络节点的三维定位,假设在三维空间中,无线传感器网络中的未知节点的坐标是(x,y,z),锚节点的坐标分别为(x1,y1,z1),(x2,>2,z2),…,(xn,yn,zn),未知节点到锚节点的距离分别为d1,d2,…,dn。
由此,我们可以得出如下的公式(5)。
因此,无线传感器网络节点三维定位的目标函数可以定义为:
5.基于交流SCE-PSO的无线传感器网络节点三维定位方法的实现步骤
(1)寻找可定位的未知节点
在网络初始阶段,给每个传感器节点分配一个ID号,并对锚节点和未知节点进行标记,然后锚节点向自己一跳范围内的未知节点发送报文,报文内容包括自己的ID号和三维坐标值。未知节点将接收到的报文信息记录下来,并判断自身邻居锚节点的数目,若锚节点的数目不小于4则进行定位估计。
(2)通过无线信道模型估计未知节点与锚节点之间的距离。
(3)将节点定位估计问题转换为无约束优化问题。
(4)通过我们提出的交流SCE-PSO算法求解目标函数的极小值,获得未知节点坐标的估计值。
本发明的有益效果在于:
1.定位精度
定位精度是定位算法最重要的一个性能评价参数,通常用下式表示节点平均定位误差
式(7)中,e表示平均定位误差,N表示仿真的网络数目,(xi,yi,zi)和
图1、图2和图3分别为交流SCE-PSO、SCE-PSO、SCE-UA和PSO这四种不同的定位方法的定位精度随着锚节点数量、节点通信半径和测距噪声标准差变化的曲线。从图中可以看出,不论是锚节点数量不同、节点通信半径不同还是测距噪声标准差不同,交流SCE-PSO算法的定位精度均要优于SCE-PSO 算法、SCE-UA算法和PSO算法。
综上所述,本发明提出了一种基于交流SCE-PSO算法的无线传感器网络节点三维定位方法。该方法继承了SCE-PSO的优点,受优化问题维数影响较小,同时对SCE-PSO进行了改进,通过引入各个复合形之间的信息交流,加快了收敛速度,提高了解的质量,比较适用于无线传感器网络节点的三维定位。
附图说明
图1是不同锚节点数量下交流SCE-PSO算法、SCE-PSO算法、SCE-UA算法和PSO算法的定位精度对比图;
图2是不同节点通信半径下交流SCE-PSO算法、SCE-PSO算法、SCE-UA 算法和PSO算法的定位精度对比图;
图3是不同测距噪声标准差下交流SCE-PSO算法、SCE-PSO算法、SCE-UA 算法和PSO算法的定位精度对比图;
具体实施方式
下面结合附图及具体实施实例对本发明作进一步详细的说明。
本发明基于交流SCE-PSO算法的无线传感器网络节点三维定位方法,通过定义一个目标函数,将无线传感器网络节点的三维定位问题抽象为非线性无约束优化问题,再利用提出的交流SCE-PSO算法求解该非线性无约束优化问题,所求得的解就是无线传感器网络节点三维坐标的估计值。
本发明三维定位器依次经过以下步骤:
步骤(1)寻找可定位的未知节点
在网络初始阶段,给每个传感器节点分配一个ID号,并对锚节点和未知节点进行标记,然后锚节点向自己一跳范围内的未知节点发送报文,报文内容包括自己的ID号和三维坐标值。未知节点将接收到的报文信息记录下来,并判断自身邻居锚节点的数目,若锚节点的数目不小于4则进行定位估计。
(2)通过无线信道模型估计未知节点与锚节点之间的距离。
(3)将节点定位估计问题转换为无约束优化问题。即求目标函数公式(6) 的极小值。
(4)用交流SCE-PSO算法求解。
1)选取参与进化的复合形个数p(p≥1)和每个复合形所包含的顶点数目 m(m≥n+1),并计算样本点数目s=p×m。
2)产生样本点。在可行域内随机产生s个样本点x1,x2,…,xs,分别计算每一个点xi的函数值fi=f(xi),i=1,2,…,s。
3)样本点排序。把s个样本点(xi,fi)按照函数值的升序排列,排序后仍记为(xi,fi),i=1,2,…,s,也就是f1≤f2≤…≤fs,记D={(xi,fi),i=1,2,…,>
4)划分复合形群体。将D划分为p个复合形A1,A2,…,Ap,每个复合形含有m个点,其中
5)复合形进化。采用改进的粒子群算法分别进化每一个复合形。
6)复合形混合。把进化后的每个复合形的所有顶点组合成新的点集,再次按函数值fi的升序排列,排序后仍记为D,对D按目标函数的升序进行排列。
7)收敛性判断。如果满足收敛条件则停止迭代,此时具有最小函数值的粒子的位置就是问题的解,否则回到第4)步。
其中,第5)步中,改进的粒子群算法进化复合形的步骤为:
a)将复合形的每个顶点看作一个粒子,初始化各参数,包括加速常数c1、>2和c3,最大迭代次数Tmax,粒子的速度范围[vmin,vmax],惯性权重的范围[ωmin,ωmax]。
b)将迭代次数设置为t=1,随机产生初始粒子的初始速度
c)将
d)评价每一个粒子,用公式(6)计算每个粒子的适应度值
e)分别根据公式(2)、公式(3)和公式(4)更新粒子的速度、惯性权重和粒子的位置。
f)让迭代次数t=t+1,然后检验t是否小于Tmax,若条件满足转入步骤d),否则,算法停止。
最后应说明的是,以上实施实例仅用以说明本发明的技术方案而非限制,尽管参照较佳的实施实例对本发明进行了详细的说明,但本发明的保护范围并不局限于此,任何熟悉本技术领域的技术人员在本发明揭露的技术范围内,可轻易想到的修改或等同替换,而不脱离本发明技术方案的精神和范围,都应涵盖在本发明的保护范围之内。
机译: 基于无线传感器网络上的高效多边定位算法的无线定位方法以及其中记录有用于该方法的程序的记录介质
机译: 基于无线传感器网络上的高效多边定位算法的无线定位方法以及其中记录有用于该方法的程序的记录介质
机译: 基于接收功率测量和接收信号到达角的无线传感器网络中美国目标的三维定位方法。