改进粒子群优化算法在TDOA定位中的应用.pdf

2 0 1 3年 第3 2卷 第 4期 传感器与微系统 T r a n s d u ce r a n d M icr o s y s t e m T e ch n o lo g ie s 1 4 5 改进粒子群优化算法在 T D OA定位中的应用 翟彦蓉 黄 欢 张 申 马秀萍 刘 伟 游春 霞 中国矿业大学 物联网 感知矿 山 研究中心 江苏 徐 州 2 2 1 0 0 8 摘要 针对 T D O A定位估计 中的非线性最优 化问题 提 出 了一种基 于改进 粒子群 优化 的 T D O A定位 算 法 该算法在 自适应粒子群优化算法的基础上 引入禁忌搜索策略 有效地解决了粒子群优化算法容易陷 入局部最优的问题 使算法快速收敛到全局最优解 仿真结果表明 该算法性能稳定 定位精度高 关键词 到达时间差 非线性优化 禁忌搜索 粒子群优化算法 自适应 中图分类号 T P 3 1 2 文献标 识码 A 文章编号 1 0 0 0 9 7 8 7 2 0 1 3 0 4 0 1 4 5 0 4 Ap plica t io n o f im p r o v e d p a r t icle s wa r m o p t imiz a t io n a lg o r it h m in TDOA po s it io ning ZHAI Ya n r o ng HUANG Hu a n ZHANG S he n MA Xiu pi ng LI U W e i YOU Ch u n x ia I n t e r n e t o f T h in g s S e n s o r Mi n e R e s e a r ch C e n t e r Xu z h o u 2 2 1 0 0 8 C h i n a Ab s t r a ct A n e w t i m e d i f f e r e n ce o f a r r i v a l T D O A p o s i t i o n in g a lg o ri t h m b a s e d o n i mp r o v e d p a r t i cle s w a r m o p t im i z a t i o n P S O is p r o p o s e d f o r n o n l in e a r o p t im i z a t io n o f T D O A p o s i t i o n in g e s t im a t i o n T h e a lg o rit h m u s e s t a b u s e a r ch s t r a t e g y b a s e d o n a d a p t iv e P S O a lg o r it h m e f f e ct iv e ly r e s o lv e s t h e p r o b le m t h a t P S O al g o r it h m e a s y t o f a ll in t o lo ca l o pt imum a n d t h e p r o p o s e d a lg o r it hm co n v e r g e s t o g lo ba l o p t imum f a s t ly S imu la t io n r e s ult s v e ri f y t h a t t h e a lg o r it hm p e r f o r ms s t a bly wit h h ig h po s it io n in g pr e cis io n K e y wo r d s t i m e d i f f e r e n ce o f a r r i v a l T D O A n o n l in e a r o p t im i z a t i o n t a b u s e a r ch T S p a r t i cl e s w a r m o p t im i z a t io n P S O a l g o r i t h m a d a p t iv e 0 引 言 移 动 目标 的定位在安全 生产 和生 活 中都 具有 非常 重 要的作用 相关技术 的研究是当前多个领域的热点之一 到达时间差 t im e d i f f e r e n ce o f a r r iv a l T D O A 作为一种非常 有前景的定位技术 通过检测信号到达 2个基站的时间差 来确定移动 台的位置 已经广泛用于蜂窝移动 网络 但是 现有的T D O A通常需要通过求解非线性的双曲线方 程组 计算量大 时间长 为此 许 多学 者提 出了相 应的 改 进算法 比如 F a n g S X S I T a y lo r 级数展开法和 C h a n算 法 J 不过这些算法不能利用冗余测量数据提高测量精 度 难以求得最优解 同时对初始解要求较高 最优解在测 量 噪声较大的情况下性 能恶 化 比较 严重 此外 上 述定 位 算法一般都假设 T D O A的测量误差服从高斯分布 并且可 以得到似然函数的解析表达式 从而可以利用最大似然法 求解 粒子群优化 p a r t i cl e s w a r m o p t i mi z a t i o n P S O 算法 是一种模拟生物在 自然界的遗传与进化而形成的一种随机 收稿 日期 2 0 1 3 0 2 0 1 搜索方法 非常适用于T D O A方程组求解这种非线性 多峰 值的复杂优化问题 收敛性能较好 虽然粒子群算法容易 陷入局部最优 但是可以利用禁忌搜索 t a b u s e a r ch T S 算 法较强的 爬 山 能力 和记 忆能力来克服 本 文分析 了 T D O A定位 问题 中的非 线性 函数优 化问题 的基础 上 利用 禁忌搜索算法与自适应粒子群算法进行联合优化 提出了 一 种 自适应的 T D O A求解 方法 仿 真表 明 其性 能有 较大 提升 1 定位模 型 为了叙述简便 本文仅考虑二维平面情况 但文中的算 法很容易推广到三 维情况 假设 有 M 3 个基 站分 布 在 同一平面上 基 站 i 的坐标为 Y 移 动 台坐 标为 Y 设基站 i到移动台的距离为 移动台到基站 i i 1 和基站 l 之间 的距离差为 根 据基 站和移动台之 间的关 系可 以得到 r ct 一r 1 cn i 2 3 1 1 1 4 6 传 感 器 与 微 系 统 第3 2卷 其中 t i 2 3 一1 为到达时间差测量值 c 为 无线电波传播速度 可以认为 2 3 1 是独 立同分布 且均值为零 方差为D r 的高斯白噪声 所以有 ri 1 V 二 cn f l 2 记 月 1 2 l 1 3 l lj 1 T M 1 R r 2 r 3 r M T 一 1 l R 1 r 1 r 1 r 1 T M 1 l N n 2 1 n 3 l n M 1 T M 1 1 由式 1 式 2 得 R R c cN 3 根据前面的假设可知 A R中的元素均为独立同分布的 高斯随机变量 其均值为 一 r 方差为 C 2 o r 因此 似然函 数为 珥M I 唧 M 1 唧 4 求似然函数最大的坐标值 相当于求解式 5 的目标函 数 Y a r g m i n A R R R 1 A R 5 从式 4 可以看出 该 式 中包 含很复杂 的非线性 函数 使用传统的求导方法求解非常困难 从 目标函数式 5 可 以看出 搜索峰值对应坐标也可以求得最大似然估计值 但 直接搜索的计算量非常巨大 为此 利用 P S O对寻优函数 基本没有限制的特点 在整个潜在的解空间中搜索最优解 确定移动台的位置 2 T S自适应 P S O 算法 2 1 自适应 P S O算法 P S O算法首先初始化一群随机粒子 然后通过迭代找 到最优解 算法执行时 首先随机初始化粒子的位置和速 度 然后进行迭代寻优过程 在每一次迭代中 粒子通过跟 踪2个极值来更新 自己的速度和位置 一个极值是粒子本 身找到的最优解 即个体极值p b e s t 另一个极值是整个种群 目前找到的最优解 即全局极值 g b e s t 粒子寻优根据以下 基本公式来更新 自己的速度和位置 r 扎 d c1 r 1 p 一 t c2 r 2 p t一 td 6 c d 式中i 1 2 N t 为迭代次数 惯性权重因子 W取值范 围在 0 1 0 9之间 学习因子 c c 一般取值为 2 r r 是 0 1 之间的随机数 动态 惯性权重 因子 W也可 以表示为进化速度 h和 聚集 度 5 的函数 即 厂 h s 7 其中 鲁 c 8m ax F g bset F g best 一 一 0 9 一 S l I J m F g b s e t F r 一 式中F g 6 e s t 一 为上一次迭代的全局最优值 F g b e s t 为当前迭代的全局最优值 F 为所有粒子当前适应度值的 平均值 参数 h 反映了粒子群进化速度 参数 S 反映了所 有粒子当前的聚集程度 同时在一定程度上也反映出粒子 的多样性 当s 1时 粒子群中的所有粒子具有同一性 如果此时算法陷入局部最优 则结果不容易跳出该局部极 点 随着粒子的进化速度因子 h的降低而减小 随着聚 集度 因子 S 的增大 而增大 如式 1 0 W h W s 1 0 式中 为 W的初始值 一般 W 取值为 1 W 和 W 分别 为 h和 s 的比例 因子 的取值范围一般在 0 4 0 6之 问 W 的取值范围一般在0 0 5 0 2之间 2 2 T S算法 T s 算法最早是由G lo v e r F提出的一种模拟人思维的 智能搜索算法 它是对局部领域搜索的一种扩展 是一种全 局逐步 寻优算 法 是对人 类智力过程 的一 种模拟 T S算法 在搜索的过程中可以接受劣解 具有很强的 爬山 能力 但 接受劣解可能陷入局部最优 因此 T S 算法中要建立禁忌表 对已经进行的优化过程进行记录和选择 指导下一步的搜索 方向 同时 T s 算法存在对初始解依赖性较强和非并行搜索 的缺点 影响全局最优解的搜索 2 3 T S自适应 P S O算法 鉴于2种算法的特点 为 了利用 T s算法和自适应 P S O 算法各自的优点而回避其缺点 本文将 T s的思想引入到自 适应 P S O算法中 自适应 P S O算法先进行前期搜索 当满 足 T s开始准则 即搜索到最优解可能出现的区域后 自适 应 P S O算法停止搜索 此后利用 T s 算法进行局部搜索 同 时建立禁忌表 将 p b e s t 放到禁忌表中 如果当前解连续几 次没有更新 利用当前解的邻域函数产生一定数 目的邻域 解进行 T s 并遵循特赦准则 更新全局最优解和禁忌表 第 4期 翟彦蓉 等 改进粒子群优化算法在 T D O A定位中的应用 1 4 7 本算法在得到 P S O算法提供的较好的初始解的情况下 可 以减少由于多次调用 T s算法带来 的大量计算 并且利用 T S 算法较强的 爬山 能力 快速收敛到全局最优解 3 基 于 T S自适应 P S O 的 T D OA定位算法 3 1 参数定义 将 T s的 P S O算法用于 T D O A T S P S O 估计中的非线 性函数优化问题 需要对其中一些参数进行定义 1 粒子定义 由于每个粒子都表示 目标函数的可能解 因此 本文将 粒子定义为移动台估计位置进行分析 2 T s 算法开始准则 在前期全局搜索时 如果粒子群在最近 代内的适应 度值的相对变化率小于设定的阈值 s 停止粒子群搜索 启 用 T S进行局部搜索 一 1 1 其中 C为当前迭代次数 f C 为种群 当前的适应度 值 C T 为种群 代前的适应度值 3 禁忌表 禁 忌长度 是一个很 重要 的关键参 数 它决定 禁忌对 象 的任期 其大小直接影响整个算法的搜索进程和行为 禁忌 表长度太小 搜索工程可能陷入死循环 禁忌表长度太大 太多的当前最优解被禁忌 可能会错过好的解 本文禁忌 长度 L 6 禁忌 表 按 照 队列 先进 先 出 fir s t in f ir s t o u t F I F O 原则进行更新 4 特赦准则 如果某个 被禁 忌 的候 选解 的适应 度 高 于历 史最 优 状 态 则解禁该候选解并更新 当前历史最优状态 5 适应度 函数 适应度函数是 T S P S O算法指导搜索方向的依据 本算 法中 取适应值 fi t Z i 1 2 粒 子坐标矢量为 Z i Y 1 3 式 中 Y 为待估计 的坐标 设移动台坐标 Y 的范围为服务基站的覆盖范围 即 一 1 4 Y y y 其中 X m a x 为基站覆盖区域横坐标的最小值和最大 值 Y Y m a x 为基站覆盖区域纵坐标的最小值和最大值 3 2 算法步骤 主要参数定义之后 所提算法步骤如下 1 初 始化粒子 的位 置 向量 速 度 向量 全局最 优值 个 体最优值和禁忌长度 初始化 W h和 S 分别为 W 1 h 0 S 0 禁忌 表置空 2 计算粒子的适应度 3 对粒子群 中的所有粒子相继执行更新粒 子速度和位 置 计算粒子的适应度 更新粒子的全局最优值和个体最优 值 4 根据式 7 式 8 和式 1 O 分别计算 h s 和 W 5 如果 满足 T s开始准则 执行步 骤 6 否则 执行步 骤 2 6 利用当前解的邻域函数产生一定数 目的邻域解 进 行 T s 并从中选取适应度最高的若干候选解 7 如果候选解满足特赦准则 则用此候选解代替 当前 解 按 F I F O原则更 新禁 忌表 执 行 步骤 8 否则 执 行 步 骤 6 8 如果算法收敛准则满足或达到最大迭代次数 执行 步骤 9 否则 执行步骤 2 9 输出 g b e s t 即移动台的位置 算法结 束 为 了检验所提算法 的性能 图 1给出了 5 O次实验 的平 均均方根误差 r o o t m e a n s q u a r e e r r o r R M S E 进 化 曲线 从 图 中曲线可 以看 出 自适应粒 子群 优化算 法在 迭代 次数 为 l0次时 进入收敛状态 算法后期陷入局部最优 T S P S O算 法在迭代次数为 3 0 6 0次时 R MS E有 1 5 0m的降低 改善 较大 因此 所提算 法能够 跳 出局部 比最优 从 而获 得近 似 全局最优解 迭代次数 图 1 均方根误差与迭代次数的关 系 F ig 1 Re la t io n s hip o f RM S E a n d nu mbe r o f it e r a t io ns 4仿真与分析 4 1 仿真条件 为 了测试算 法的可行性 与实 际性能 通 过 M a t l a b仿 真 软件对该算法在多径环境下 就不同的基站个数 测量误 差 小区半径和不 同噪声 下 对本 文算法 进行 了仿 真 并 与 其他传统定位算法的性能做了对比 采用 7 个小区组成的 典 型蜂 窝结 构 它们 的位置如 图 2所示 假设移 动 台均匀 分 布在图2阴影部分的 1 1 2小区内 选取其中 1 0 0 0个位置进行仿真分析 T D O A系统的测 量误差为独立同分布的均值为0 标准差为0 1 s 约3 0 m 的高斯 随机变量 移动台与所有基站之 间均为非视距 传输 n o t l in e o f s ig h t N L O S 1 4 8 传 感 器 与 微 系 统 第3 2卷 I 2 o 2 7 0 o 1 X 一 弋 墨 c墨 尺 v 二尺 一 一 一 3 尺 图 2 基站与移动台分布图 F ig 2 Dis t r ib u t io n o f b a s e s t a ti o n s a n d mo b ile s t a ti on s 4 2 仿真结果与分析 1 基站个数对 定位 性能的影 响 图3分析了基站个数对定位性能的影响 从仿真的结 果来看 随着基站个数的增加 3种算法的定位性能均有一 定的改善 这是由于基站个数的增加从而增加了更多的冗 余信息 使得定位性能得到相应的提高 本文算法和 T a y lo r 算法随着基站个数的增加定位性能改善不大 说明这 2种 算法对基站个数不敏感 从定位效果上看 在不同基站数 目情况下 本 文算法 的定位性 能均 明显优 于 T a y l o r 算法 和 C h a n算法 基 站 个 数 图 3 基站个数对定位性 能的影响 F ig 3 Effe cto f b a s e s t a t io n nu mbe r O R po s iti o nin g p e r f o r m a n ce 2 T D O A测量误差对定位性能的影响 图 4分析 了高斯 环境 下 T D O A测 量设 备 的测 量 误差 对定位性 能 的影 响 图 4表 明 在 不 同 T D O A 测 量误 差 下 本 文算法 的定 位误差 明显小 于其他的定 位算法且 定位 性能变化不 大 因此 本文 算法 的定 位效 果很 明显优 于其 他算法 3 小区半径对定位性能的影响 图5分析了小区半径对定位性能的影响 从图5可以 看出 无论 T a y l o r 算法 C h a n 算法 还是 P S O算法 随着小 区半径的增 大 定 位的均 方根误差 随之 增大 其原 因是 由 于 N L O S的存在引起的误差 而且 N L O S 误差随着距离的增 大而增大 随着小区半径的增大 移动台与基站之间的距 离会有所增大 导致 了 N L O S误差的增大 定位精度的下 2 2 0 2 0 0 1 80 1 60 1 4 0 1 20 1 O 0 80 60 4 0 20 0 1 0 0 1 5 0 2 0 0 2 5 0 3 0 0 3 5 0 4 O 0 4 5 0 5 0 测量误 差 m 图 4 测量误差对定位性能的影响 F ig 4 Effe ct o f me a s ur e m e n t e r r o r o n po s itio n in g p e rfo rma n ce 降 从图5中还可以看到在存在 N L O S条件下 粒子群算法 的定位性能明显优于 C h a n算法和 T a y l o r 算法 1 6 O 1 4 0 1 2 O l0 O 8 0 6 0 4 0 2 O 1 小 区半 径 m 图 5 小 区半径对定位性能的影响 Fig 5 Effe c t o f c e ll r a d ius o n po s it io n in g p e rfo r ma n c e 4 噪声对定位性能的影响 图6分析了噪声对定位性能的影响 在不同的噪声条 件下 1 0 l o g c d B 对各种定位算法进行定位仿真 得到 的定位误差与噪声 的关 系如 图 6所示 从 图 中可看 出 在 相同的噪声情况下 本文算法的定位误差有了很明显的减 小 并且随着噪声的不断增大 C h a n算法和T a y l o r 算法的误 差有逐渐变大的趋势 本文算法的误差变化不大 原因是本 文算法直接针对由最大似然法而来的方程 5 进行解的搜 索 噪声对其影响很小 因此 在抗噪声方面 本文算法性 能更加优越 蓦 虿 0 8 0 7 O 6 O 5 0 4 0 3 0 2 0 1 0 噪声 1 0 1 o g co d B 图 6 噪声对定位性 能的影响 Fig 6 Effe ct o f n o is e o n p o s it io n in g p e rfo r m a n ce 5 结束语 本文详细描述了移动台定位系统 T D O A双曲线数学模 型以和 自适 P S O算法 将禁忌 自适应 P S O算法应用 于 T D O A定位之中 仿真结果表明 该算法 在解决 T D O A定 位估计时 具有定位精度好 计算速度快 性能稳定等优点 因此 利用改进后的 P S O算法对 目标进行定位 能有效地获 取目标的位置 同时 该方法对移动通信等其他定位问题 也具有一定的应用 价值 下转第 1 5 2页 g 丑 葛 1 5 2 传 感 器 与 微 系 统 第3 2卷 趔 趟 富 墓 置 镫 9 6 O 9 5 5 9 5 0 9 4 5 9 4 0 9 3 5 9 3 0 9 2 5 9 2 0 0 5 lU l5 ZU 2 5 3 U 测试输入样本点 图4 B S OA L S S V M 模型预测结果 Fig 4 Pr e d ict io n r e s ult o f BS OA LS S VM mo d e l 从表2和图2一图4可以看出 无论是化验值与预测值 的拟合程度 还是模型的预测精度与泛化能力 基于 B S O A 进行参数优化建立的 L S S V M软测量模型均优于标准 P S O 和 B F O A优化 的模 型 究其 原因 一方 面对 于实 际工业 过 程而言 变 量间多 存在 复杂 的非 线性 关 系 而采 用 L S S V M 建模 可以有效解决小样本 非线性 问题 另一方面 混 合算 法融合 P S O算法 B F O A的优点 能更好地寻优模型参数 提高了模型的预测精度和泛化能力 4结论 本文在深入分析基本 B F O A与 P S O两种算法优缺点的 基础上 将 P S O较快的收敛速度与 B F O A较好的全局优化 能力相结合 提出了一种 B S O A混合优化算法 混合算法 有效提高了标准 P S O和 B F O A的优化性能 并在一定程度 上克服了P S O易陷入局部最优和 B F O A收敛速度慢等缺 陷 将本方法用于成品油调和研究法辛烷值的软测量建模 中 预测结果表 明 基于 B S O A L S S V M的软测量 模型 泛化 性能好 预测精度高 为炼油企业生产过程中某些难以在线 测量 的关键变量提供 了一种有效的实时测量方法 参考文献 1 俞金寿 软测量技术及其应用 J 自动化仪表 2 0 0 8 2 9 1 1 6 2 K a d l e c P G a b r y s B D a t a d r i v e n s o f t s e n s o r s i n t h e p r o ce s s i n d u s t r y J C o mp u t e r s a n d C h e mi ca l E n g i n e e rin g 2 0 0 9 3 3 7 9 5 8 1 4 3 P a s s in o K M B i o mi m i c o f b a ct e ria l f o r a g i n g f o r d i s t rib u t e d o p t i m iz a t i o n a n d co n t r o l J I E E E C o n t r o l S y s t e m s Ma g a z i n e 2 0 0 2 2 2 5 2 6 7 4 T r ip a t h y M Mi s h r a S B a ct e ria f o r a g i n g b a s e d t o o p t i mi z e b o t h r e a l p o w e r l o s s a n d v o l t a g e s t a b i li t y l im i t J I E E E T r a n s a ct i o n s o n P o w e r S y s t e m s 2 0 0 7 2 2 1 2 4 0 2 4 8 5 V a i s a k h k P r a v e e n a P S o l v i n g d y n a m i c e co n o mi c d i s p a t ch p r o b le m wit h s e cu r i t y co n s t r a in t s u s in g b a ct e ri a l f o r a g in g P S O DE a l g o r i t h m J E le ct r i ca l P o w e r a n d E n e r g y S y s t e m s 2 0 1 2 3 9 5 6 9 7 6 崔 静静 孙延 明 改进 细菌 觅食 算 法求 解车 间作 业 调度 问 题 J 汁算机应用研究 2 0 1 1 1 8 9 3 3 2 4 3 3 2 6 7 周雅 兰 细菌觅食优化算法 的研究 与应用 J 计算 机工程与 应用 2 0 1 0 4 6 2 O 1 6 2 1 8 L i u Y P a s s in o K M B i o n fimi cry o f s o ci a l f o r a g i n g b a ct e r i a f o r d i s t r ib u t e d o p t imiz a t io n Mo de ls p ri n c ip le s a n d e me r g e n t b e h a v io r S J J O p t i m iz a t i o n T h e o r y A p p li ca t 2 0 0 2 1 1 5 3 6 0 3 6 2 8 9 K e n n e d y J E b e r h a R C P a r t icl e s w a r m o p t i mi z a t i o n C P r o e o f I EEE I n t 1 C o n f o n Ne u r a l Ne t wo r k s P e n h W A Au s t r a lia 1 9 9 5 1 9 4 2 1 9 4 8 1 0 M o h a mm e d E l A b d P e r f o r ma n ce a s s e s s me n t o f f o r a g i n g a l g o r i t h m s e v o l u t i o n a r y a l g o r i t h m s J I n f o rma t i o n S cie n ce s 2 0 1 2 1 8 2 2 4 3 2 6 3 作者简介 李炜 1 9 6 3一 女 陕西西 安人 教授 博导 研 究方 向为工 业过程先进控制 动态系统的故障诊断与容错控制 t p t p 上接第 1 4 8页 参考文献 1 G u J i e He F a n g G o n g Y a o h u a n W C D M A w i r e l e s s ce l l u l a r l o ca t i o n a n d t r a ck i n g b a s e d o n Ma r k o v mo d e ls c P r o ce e d i n g o f t h e I EEE I n t e r n a t io n al C o n f e r e n c e o n C o mmu n ica t io n s 2 0 0 2 2 3 4 2 3 7 2 张令 文 谈 振辉 基 于泰 勒级 数展 开 的蜂 窝 T D O A定位 算 法 J 通信学报 2 0 0 7 2 8