多算法协同定位（共7篇）
多算法协同定位 篇1
0 引 言
数据融合技术是结合有关先验信息, 综合不同处理方法和技术的优点对不同类型的数据进行融合, 从而获得比单一处理方法和技术更优数据输出的技术[1]。目前, 一些研究者已经在基于JDL数据融合模型上面做了很多的工作[2,3,4,5]。文献[2,3,4,5]包括有综合利用到TOA, TDOA, AOA三种测量值来进行融合技术, 但是由于要进行不同参数的测量, 限制了这些方法的实用化;文献[6]虽然单独利用TDOA进行融合, 实现容易, 但对于移动台某一个确定位置, 其定位结果有较大的误差。
由于基于TDOA的定位方法不需要基站与移动台之间严格的同步, 因此在基于蜂窝网的移动台定位技术中, 大部分无线定位算法都是基于TDOA的, 其中比较经典的算法有Chan算法和泰勒序列展开法。在不同的信道环境中他们各自具有其特有的优点, 同时也存在局限性。为了提高移动台的定位准确度, 将综合这两种算法, 并且结合了简单的残差加权算法, 构造先验信息, 对Kleine-Ostmarm数据融合模型[7,8]进行改进, 提出一种无需先验信息的, 利用Chan算法和泰勒序列展开法定位结果进行融合的算法协同定位模型。由于在数据融合过程中需要利用简单的残差加权算法, 因此下面先对之进行较为详细的介绍。
1 简单的残差加权算法
设参与定位的基站个数为M≥4, 待定位的移动台坐标为 (x, y) , (xi, yi) 为第i个基站发射机的已知位置。根据测量得到的TDOA测量值可以得到下式:
式中:xi, 1=xi-x1;yi, 1=yi-y1;Ki = x
所有的残差平方和为:
对所有的
2 融合方法
各种算法都有其自身的优缺点, Chan算法和泰勒序列展开法都需要先验信息, 在无法知道先验信息的情况下, 都假设TDOA测量值的协方差矩阵为单位矩阵。因此, 先用简单的残差加权法构造TDOA测量值的协方差矩阵[9] (见式 (5) ) , 代入这两种基本算法中, 以减少NLOS误差。此外, 对于泰勒序列展开法, 先通过其他算法进行初始定位, 再将定位结果作为初始值代入其中进行定位计算。本文提出的多算法协同定位的数据融合模型, 如图1所示, 该模型特点如下。
(1) 因为没有任何有关TDOA测量值的先验信息, 所以Chan算法和泰勒序列展开法中的TDOA测量值的协方差矩阵Q是未知的。可以由前面定义的残差函数, 将MS位置初始估计值
将构造后的Q值代入Chan算法和泰勒序列展开法中作为TDOA的协方差矩阵。文献[9]中对此做了详细的分析, 且结果表明, 将与真实位置比较接近的初始值代入残差函数, 构造TDOA的协方差矩阵, 可以有效改善NLOS误差对定位带来的不利影响。
(2) 对于TDOA测量值, 分别采用简单残差加权法、Chan算法、泰勒序列展开法、第一层数据融合和第二层数据融合, 产生五种定位估计, 其中泰勒序列展开法的初值由简单残差加权法产生。
(3) 第一层数据融合
对于同一组TDOA测量值分别采用简单残差加权法、Chan算法和泰勒序列展开法进行定位估计, 每种算法的加权系数Rk, 则:
式中:
式中:K为算法数目。
(4) 第二层数据融合
该层依旧采用加权方式进行数据融合, 在这层进行融合的定位估计有3种, 设每种的加权系数为Rk′, 则定义:
式中:
(5) 第四层数据融合
该层数据融合采用文献[10]方法进行加权处理, 假定Chan算法、泰勒序列展开法、第一层数据融合和第二层数据融合的定位估计值的均值和方差分别为Xcm, Xtm, X1m, X2m和σ2c, σ
3 算法仿真及性能讨论
采用标准7基站/小区蜂窝网络, 小区半径为3 000 m。其中第一个基站为服务基站, 如图2所示。
信道模型采用C0ST259, 环境分别为闹市区、一般市区、郊区和远郊。由于该算法主要是为了减少非视距对定位精度的影响, 因此这里主要对在闹市区的情况进行较为详细的分析。为了验证该模型的性能, 在服务基站的第一扇区内随机选择了12个待定位点, 这12个点随机分布在相邻距离为200 m的同心圆上, 每个点重复仿真200次, 将数据融合各层定位结果定位均方根误差和均值误差与融合结果比较, 以及将数据融合各层误差小于150 m和小于300 m的概率进行比较, 最后比较本融合结果与传统的Chan算法比较。
如图3所示, 得到:经过融合以后, 融合结果相对于参与融合的各层, 其定位均方根误差有明显的减小, 但均值误差并不是最低, 这是因为决策层是用基于最小均方误差的最优线性融合的方法来进行融合的。它只能保证融合后的结果比参与融合各层的均方根误差都小, 而无法保证定位的均值误差也比各层的都小。
如图4所示, 得到, 在定位误差小于150 m概率比较时, 第一层和第二层融合出现了融合结果的概率小于Chan算法。这是因为这两层都是利用线性加权的方法进行融合的, 如果有一个或者若干基站的定位结果较差, 那么就会导致这层融合结果较差。当初始值定位较差时候, 也可能会导致泰勒序列展开法在闹市环境下比Chan算法差。
从图5可以看到, 融合结果无论在定位误差均值还是在均方根误差指标上都比传统的Chan算法优越。在较为严重的非视距环境下, 该算法具有较好的适应性。第一层和第二层都是采用的残差融合方法可以对非视距影响较大的估计分配较小的加权因子, 因而也可以减小非视距的影响, 并且非视距影响越大, 这种效果就越明显。因此本融合模型的定位精度要比Chan算法高, 具有一定的实用性。
4 结 语
在蜂窝网络定位系统中, 由于基于单个测量值的定位方法以及单个算法的定位精度有限, 因此Kleine-Ostmann提出了一种基于JDL的三层定位数据融合模型。为了在没有任何信道环境先验信息的情况下, 融合不同TDOA定位算法的优点, 讨论了一种针对不同TDOA定位算法融合的新型数据融合模型, 利用简单的残差加权算法得到第一步定位估计值, 构造TDOA协方差矩阵和作为泰勒序列展开法的初始值, 并且利用线性加权和贝叶斯推论等融合方法, 得到最好定位结果。仿真结果表明, 在非视距环境下, 该模型有效提高了移动台的定位精度, 且不需要先验信息。
参考文献
[1]Ostmann T Kleine, Bell A.A Data Fusion Architecture forEnhanced Position Estimation in Wireless Networks[J].IEEE Communication Letters, 2001, 5 (8) :343-345.
[2]杜海兵, 王民北.数据融合技术在无线移动定位中的应用[J].计算机工程与应用, 2005 (16) :153-155, 161.
[3]孙国林, 郭伟.基于数据融合的蜂窝无线定位算法研究[J].通信学报, 2003, 24 (1) :137-142.
[4]刘军民, 张展, 刘石.基于数据融合技术的TDOA移动台定位方法[J].大连理工大学学报, 2005, 45 (1) :138-141.
[5]陈朝, 昂志敏.一种基于数据融合的蜂窝无线定位算法模型[J].国外电子测量技术, 2008, 27 (3) :27-30.
[6]邓平, 刘林, 范平志.移动台定位估计数据融合增强模型及其仿真研究[J].通信学报, 2003, 24 (11) :165-17.
[7]范平志, 邓平, 刘林.蜂窝网络无线定位[M].北京:电子工业出版社, 2002.
[8]袁登科.蜂窝网络消除非视距传播误差影响的定位算法研究[D].成都:西南交通大学, 2005.
[10]李启虎.独立观测资料的最佳线性数据融合[J].声学学报, 2000, 25 (5) :385-388.
多算法协同定位 篇2
移动计算器件的发展和无线局域网技术的前进, 为移动定位技术的发展奠定了坚实的基础;同时, 由于无缝定位需求的日益增加, 对定位技术尤其是室内定位技术提出了更高的要求;此外, 物联网在国内外引起广泛关注, 作为物联网的核心产业的无线传感器网络也得到了前所未有的蓬勃发展, 而在无线传感器网络的各种应用中, 节点位置信息的获取至关重要。作为IT业下一个"金矿"的射频识别技术 (RFID) 具有读取速度快、存储空间大、工作距离远、穿透性强、外形多样、工作环境适应性强和可重复使用等多种优点, 成为IT业界的研究热点。
根据定位过程是否需要用到阅读器与标签之间的距离, 定位算法可分为测距算法和非测距算法[1]。测距算法依据阅读器与标签之间的几何关系建立定位模型 (包括圆周模型和双曲线模型) 而后进行求解, 常见的测距算法包括Taylor级数展开算法、Chan算法、Fang算法、SI和SX算法、三边测量算法等。非测距算法的一般原理是在定位空间选取若干参考点, 建立参考标签的信号强度矢量与位置的数据库, 获取到目标标签的信号强度矢量后, 采取一定的方法对数据库处理来估测标签位置。根据处理方法的不同, 非测距算法可分为模式匹配法、概率统计法、神经网络法、支持向量机等。图 1显示的是测距和非测距算法的几种常用模型的示意图, 其中圆圈代表阅读器, 三角形代表目标位置, 菱形代表参考标签。
(a) 圆周模型 (b) 双曲线模型 (c) 非测距模型
最近邻居算法[2]属于非测距算法, 采用模式匹配法对数据进行处理, 定位效果较稳定但精度较低。Chan算法[3]属于测距算法, 是一种求解双曲线方程组的非递归算法, 计算量小但定位精度不理想, 图 2给出了RFID系统中应用Chan算法定位的一般流程。Taylor级数展开算法[4]也属于测距算法, 是基于泰勒级数展开的最小二乘估计递归算法, 定位精度较高但计算复杂度较大且需要初始位置信息。在实际应用中通常将上述三种算法加以综合, 优势互补。
在已有的算法融合中, 通常的做法是: (1) 将Chan算法的结果作为Taylor级数算法的初始值[6]; (2) 将KN算法的结果作为Taylor级数算法的初始值[7]。在定位空间范围较小时, 初始位置对Taylor级数算法的影响并不明显, 因此, 本文尝试Chan算法与KN算法的结果进行加权求和, 以期在计算复杂度、定位精度和算法稳定性达到最优化。
3 阅读器排布对最近邻居算法的影响
3.1 原有仿真环境的布局
为了满足定位算法仿真的需求, 本文对定位空间中阅读器进行如下安排, 如图 3所示: (1) 采用四个阅读器。二维空间定位至少需要三个阅读器, 阅读器越多, 冗余信息也越多, 定位精度也越高; (2) 阅读器均匀分布在矩形定位空间的四个角。采用最常见的矩形分布, 可以将该定位空间作为一个细胞结构, 方便进行扩展; (3) 定位空间均匀地分布着十六个采样点。通过分析这16个采样点在不同定位算法中的定位结果, 可以对各个定位算法定位性能进行比较;同时, 采用均匀分布能够较完整地反映整个空间定位效果。
定位空间为长宽均为20m的矩形, 参与定位的四个阅读器的坐标依次为 (0, 0) , (20, 0) , (0, 20) , (20, 20) 。文中采用对数距离损耗模型[5]将信号强度值与距离值进行转化, 如公式1所示:
其中n是路径损耗指数, 表示路径损耗随距离增长的速率, 它依赖于周围环境和建筑物类型;Xα是遮蔽因子, 它是均值为μ, 方差为σ2的正态随机变量, Xα与传播距离无关。实验选取了如下参数值:路径损耗n为2.7, 参考距离定位1m, 此处的信号衰减值为-40dBm。
为了评价不同噪声对定位算法的影响, 设置如下两种仿真环境:
仿真环境1:在四个阅读器到标签的信号传输路径上叠加方差为4的高斯白噪声, 来模拟噪声较小且分布均匀的定位空间;
仿真环境2:在标签到阅读器的信号传输路径上叠加高斯白噪声, 方差分别为16, 36, 64, 100, 来模拟噪声分布不均匀且噪声干扰较大的定位空间。
目标标签的位置是由若干参考标签位置加权相加得到的, 同时各个权值之和为1, 因此估测的目标标签的位置只可能出现在由外围参考标签构成的凸多边形的内部区域, 即图3中的灰色区域中。显而易见, 这种阅读器排布方式会使目标标签的估测结果在阅读器附近出现较大误差, 会形成几个定位盲区, 对定位精度的整体提高带来较大困难。
3.2 改进布局
通过对最近邻居算法定位精度的分析, 先采用如图 4所示的改进的空间布局。
由于最近邻居算法目标标签的位置是各参考标签位置的加权和, 因此, 图 3和图 4中的阴影区表示当前布局下, 目标标签可被准确表示的范围。改变阅读器和标签的布局后, 使盲点区域减少, 从而提高了整体的定位精度。图 5显示的是在仿真环境1中, 采用加权KN算法, 5*5参考标签分布下的阅读器变动前后的定位精度的比较曲线。可以清楚看到, 阅读器位置变动后, 定位精度整体提高, 采样区内的定位误差均在0.9m以内, 明显改善了之前因为盲点区域存在而造成的盲区及盲区附近采样点定位精度明显恶化的现象, 很好地解决了盲区问题。
4 最近邻居算法和Chan算法的结合
第2部分优化了定位空间, 使得由阅读器和标签分布对定位算法的精度的影响降到最低。下面将介绍最近邻居算法与Chan算法的协同定位算法的具体内容。
4.1 权值的确定
最近邻居算法定位精度较稳定, 但定位精度差强人意;Chan氏算法流程简洁, 计算量小, 且精度稍高于KN算法, 现尝试将两者进行融合, 以期得到更好的定位精度。
硬件平台的搭建采用多个参考标签, 阅读器同时接收参考标签和目标标签的信号强度值。在对某个采样点位置上的目标标签定位时, 分别计算最近邻居算法和Chan算法的定位估计结果, 并按照以下公式进行加权:预测位置=p*Chan 算法结果 + (1-p) *最近邻居结果。
图 6显示了在不同权值p下, 16个采样点定位误差的三个统计参量的比较结果, 纵坐标分别代表:均值、最小值、方差, 横坐标代表权值。通过观察发现, 权值取0.7时, 各项指标达到最优, 因此, 权值选择为0.7。
4.2 KN-Chan算法和KN-Taylor算法定位效果比较
图 7是在仿真环境1下, 最近邻居算法分别与Chan算法和Taylor级数展开算法相融合的结果。图 7上面一组曲线为将KN算法作为Taylor级数展开算法的初值的定位估值结果。图 7下面一组曲线为KN算法与Chan算法在权值p=0.7的叠加结果。
通过分析图 7, 可得到如下结论:
(1) 将Chan算法与最近邻居算法融合, 得到的定位精度要优于KN算法和Chan算法。
(2) 最近邻居算法与Taylor级数算法相融合的策略在本实验设定的仿真环境下并不适用, 定位结果较差。
4.3 KN-Chan定位结果分析
在改进的阅读器重新分布的定位空间, 最近邻居算法与Chan氏算法的融合大大提高了现有的定位精度。图 8与图 9是两种仿真环境下改进算法的定位效果, 评价指标采用均方误差 (RMSE) 和误差累计分布曲线 (CDF) 。
在仿真环境1下, 算法表现出很好的性能, 定位误差均在0.4m以内, 大大提高了定位精度, 而在仿真环境2下, 定位精度相对于单纯的最近邻居算法和Chan算法有提高, 60%的采样点定位精度在0.4m以内。
5 结论
文中提出的最近邻居算法与Chan氏算法相结合的协同定位算法, 结合了非测距算法的稳定性和测距算法的定位精度高的优点, 在阅读器重新排布的改进的小范围定位空间中, 定位效果表现优良。论文提出的改进算法适用于小范围低噪声定位空间, 定位精度可控制0.4m。
参考文献
[1]郭菲菲.基于贝叶斯学习的RFID室内定位方法的研究[D].哈尔滨工业大学, 2008.
[2]韩下林, 赵卫东, 季军, 卫刚, 柳先辉.基于RFID技术的室内定位算法及其改进[J].计算机工程.2008, 22 (34) , 266-269.
[3]段凯宇.一种改进的TOA无线定位算法[J].科技信息.2010 (26) :5-6.
[4]郭明涛, 李文元, 龚福春, 林旺.室内环境内的改进型Taylor级数定位算法[J].无线通信技术.2009 (1) :17-21.
[5]徐日明, 庄长远, 俞斌.基于RSSI的动态修正室内无线定位算法[J].电脑知识与技术.2010, 6 (3) , 686-688.
[6]刘林, 邓平, 范平志.基于Chan氏算法和Taylor级数展开算法的协同定位方法[J].电子与信息学报, 2004, 1 (20) , 41-43.
多算法协同定位 篇3
科学研究和工程实践中往往存在着一些多目标优化问题 (Multi-objective Optimization Problem, MOP) , 早在1967年, R.S.Rosenberg就在其博士论文中提到了使用遗传算法解决单目标问题, 20世纪80年代中期David Schaffer设计了历史上第一个多目标优化算法。多目标优化算法发展至今已产生很多优秀的算法, 例如, Fonseca、Fleming和Horn等[2,3,4]人提出Multiobjective Genetic Algorithm (MOGA) 、Non-Dominated Sorting Genetic Algorithm (NSGA) 以及Niched Pareto Genetic Algorithm (NPGA) 。Zitzler与Thiele等[5,6,7]人提出Strength Pareto Evolutionary Algorithm (SPEA) 、Pareto Archived Evolution Strategy (PAES) 和Micro-Genetic Algorithm (Micro-GA) 。2003年, Wiegand和De Jong[8]对Cooperative Algorithms进行了深入分析。
协同进化最早由Ehrlich与Raven讨论植物和食植昆虫进化的相互影响而提出。Hillis[9]在1991年提出寄生的协同进化算法模型, 用于协同进化分类网络的设计。1995年, Rosin等[10]提出了竞争协同进化算法模型, 用于研究偷窃的博弈问题。
近年来, 对于基于协同进化的的多目标优化算法研究取得了大量成果, 如文献[11]是设置n个子种群分别独立的基于已有多目标优化算法问题。文献[12]是设置一个目标对应一个子种群, 根据生态种群密度竞争方程调整各子种群的规模, 用于描述多个目标之间的关系。文献[13]是依据在进化过程中获取的信息划分搜索空间, 该方法的不足之处是划分搜索空间后可能产生大量的子种群, 导致计算量过大。
与多目标优化算法相比, 协同进化多目标算法的均匀性与分布性较差。本文提出了基于聚集密度的协同进化多目标算法, 并且数值实验结果以及图示对新算法的均匀性与分布性做了测评。
1 多目标优化问题的相关概念
1.1 多目标优化问题的基本概念
多目标优化问题的基本形式为:
其中, x为决策向量, F (x) 为目标函数, gi (x) ≥0, hi (x) ≥0为约束条件。
多目标问题的最优解组成的集合叫Pareto最优解集, Pareto最优解集包含了所有的Pareto最优解, 下面给出Pareto最优解的定义。
定义1若xA、xB是两个可行解, 且:
则称xA相比xBPareto占优, 也称xA支配xB, 记为xAxB。
定义2 (Pareto最优解) 一个可行解被称为Pareto最优解, 当且仅当x*满足如下条件:
则称x*为Pareto最优解。
1.2 多目标优化问题最优解集的评价标准
多目标优化算法中最优解的确定是一个非常重要而且困难的研究课题, 对于找到的可行解集, 不仅要考虑得到该解集算法的复杂性, 而且要考虑该解集在目标空间的均匀程度和它们的收敛情况。
在最优化算法发展早期, 研究者们主要通过对解集边界的观察来评价解集的好坏, 这样得出来的结果不仅存在着很大的不确定性, 还受到主观因素的影响。
常用的量化评价指标有:
(1) 世代距离 (Generation Distance, GD)
其中, n为算法所得解集前端PFknown中向量个数, di为PFknown中每一维向量到解集前端PFtrue中最近向量的距离[10]。
GD主要反映PFknown对PFtrue的逼近程度。
(2) 错误率 (Error Ration, ER)
其中, n为PFknown中的向量个数, 且PFknown={X1, X2, …, Xn}, ei定义如下:
ER体现的是PFknow对PFtrue的覆盖程度, ER越小, 说明解集的正确性越高。
(3) 分布性 (Spaing, SP)
其中, n为算法产生解集中解的个数, di为第i个解到它的最近解距离, 表示di的平均值, SP即为di的均方差。根据方差的含义, SP反映的是解集分布的均匀情况。
2 协同进化多目标优化算法
协同进化算法考虑个体之间和个体与环境之间的关系, 种群中个体的进化受其它个体和环境的影响。协同进化算法可以在一定程度上克服早熟现象, 并且更适合复杂问题的计算。根据个体与其它个体之间交互方式的不同可将协同进化算法分为竞争型协同进化算法和合作型协同进化算法。
1997年, Potter在其博士学位论文中对合作型协同进化算法模型进行了深入研究, 针对已有算法需要人参与的缺陷, 给出了一种新型合作协同进化算法结构。
由于合作型协同进化遗传算法的进化效率较高, 并且计算的复杂性较小, 因此我们下面的讨论围绕合作型协同进化展开。合作型协同进化算法首先将优化问题决策变量分组, 然后对分组后的每个少变量决策变量分别编码, 产生初始子种群, 接着各子群独立进化。合作型协同进化算法中的各种群个体适应度是通过将其与其它各物种中随机选取的个体一起组成一个完整的解, 计算这个完整解的目标函数值来作为个体的适该个体的适应度。对某种群个体的评价是依据它与其它种群进化到当前代最优个体组合的好坏来进行, 它们组成的完整解的好坏决定着该个体的适应度。各种群在每代执行过程中通过适应度比较找出当前代最优个体, 各种群当前代最优个体的组合即为当前代的可行解, 这样代代下去搜寻最优解。
将多目标优化问题的决策变量分为几个部分, 既可以将其中几个决策变量作为一个部分, 另外几个决策变量作为另一部分, 剩下的决策变量再作为一个部分。每个部分对应一个种群, 每个种群的个体适应度是通过和其它种群的个体组成完整解再评价得到, 该个体的适应度是由其与其它种群个体组合中最优决定组合。具体步骤如下:
(1) 设置一个超级个体集合P为空集。
(2) 初始化。将所有决策变量分成m组, 初始化m个子种群, 其中每个子种群分别对应各个决策变量。
(3) 求适应度。某个体与其它子种群组合, 根据最优组合求出其适应度。
(4) 遗传操作。使用选择、交叉、变异算子分别对各子种群进行遗传操作。
(5) 更新超级集合P。
(6) 重复 (3) — (5) , 直到满足一定代数, 将当前最优解与P中解进行比较, 留下较好的解, 并且保证P中解有较好的分布性。
(7) 重复 (2) — (6) , 直到P中个体达到一定数目。
3 基于聚集密度的协同进化多目标优化算法
协同进化多目标算法在一定程度上克服了早熟现象, 但是解的分布性和均匀性较差, 对于如何提高协同进化多目标算法的均匀性和分布性已提出了不少方法。耿焕同、朱海峰将均衡分布性与收敛性用于该算法以改善解的分布性与收敛速度;张远淑将均匀设计用于该算法以提高解的多样性和分布性。
协同多目标优化算法分布性欠佳的主要原因在于算法在更新精英集时没有考虑粒子的多样性和分散性。考虑到聚集密度可反映群体的多样性和分散性, 本文提出在协同进化多目标优化算法中引入了聚集密度以进行精英集的更新, 其具体步骤为:
(1) 计算每个种群中各个体的聚集密度。
(2) 依据目标函数值和聚集密度值定义一个偏序集, 该集合中的元素有个体的目标函数值和聚集距离两个属性。
(3) 依据一定的比例, 依次从偏序集中选择个体, 更新P。
由此可以得到基于聚集密度的协同进化多目标优化算法, 具体如下: (1) 设置一个超级个体集合P为空集; (2) 初始化。将所有决策变量分成m组, 初始化m个子种群, 其中每个子种群分别对应各个决策变量; (3) 求适应度。某个体与其它子种群组合, 根据最优组合求出其适应度; (4) 遗传操作。使用选择、交叉、变异算子分别对子种群进行遗传操作; (5) 计算每个粒子的目标向量, 当迭代次数小于最大迭代次数时, 根据聚集密度方法更新P; (6) 重复 (3) — (5) , 直到满足一定代数, 将当前的最优解与P中解进行比较, 留下较好的解, 并且保证P中解有较好的分布性; (7) 重复 (2) — (6) , 直到P中个体达到一定数目。
4 数值实验与算法性能评测
下面用基于聚集密度的协同进化多目标算法对两个标准测试函数DTLZ1和Deb2进行数值计算, 并将计算结果与普通协同进化多目标算法的计算结果进行比较, 从而检验改进算法的性能。
图1—图4分别是用改进算法和常规算法求出DTLZ1和Deb2的Pareto最优边界。可以很直观地看出, 改进算法在解的分布性和均匀性方面均明显优于常规算法。
为了更进一步定量地评价改进算法的性能, 给出改进算法和常规算法的世代距离、错误率和分散性指标的对比数据。考虑到计算结果的随机性, 表中给出的是20次实验结果的平均值。
从表1和表2中可以很清楚地看出, 改进算法和常规算法的GD指标相差无几, 但改进算法的ER和SP指标与常规算法相比明显占优。
多算法协同定位 篇4
在数据流形式上,基于终端协同的多流并行传输即将业务数据划分为不同的子流,在若干终端间通过短距离传输能力为某个终端转发,并最后在此终端汇聚。业务数据的多路径分流传输是多终端协同的研究重点,而由文献[5]的多终端协同分流传输的研究可知,接入信道的终端数目将会极大影响WLAN系统容量和服务率,从而影响协同传输系统的性能 (时延、吞吐量)。因此,在终端协同分流算法中,要综合考虑终端以及其接入网的特性。
文献[6]研究了在蜂窝网中对下载文件通过终端协同进行分流传输的算法,但算法未考虑网络的异构性。文献[7]研究了视频流在无线网络中基于终端协同的分流传输算法,但此算法未考虑各终端以及其接入网络的特性,将视频流在各协同终端中平均分配传输。文献[8]对终端协同中的能耗问题进行了研究,但对于各终端间的分流也只是简单地平均分配,未体现终端性能的不同。文献[9]提出了异构网络下基于传输时间以及基于层次分析的终端协同分流算法,但由于层次分析法的判断矩阵受决策者判断水平及个人喜好主观因素影响,使分流算法具有主观随意性。因此,本文提出一种多属性决策的终端协同分流算法。在该算法中,在考虑终端用户主观喜好的基础上,同时考虑各终端及其接入网络之间的客观差异。由于目前绿色通信、节能环保受到越来越多的关注[10],在本文提出的终端协同分流算法中还考虑了终端的能耗问题。
1系统模型
1.1应用场景
图1为多终端协同分流传输的应用场景。在图1中,处于泛在环境下的用户终端两类无线接口,一种用于用户短距离通信(Short Range,SR),另外一种用于长距离通信(Long Range,LR),并假设SR通信的数据速率将远远大于LR通信链路之间的速率。其中有一个称为主终端Master,其周围存在着一些可被选择进行协同分流传输的终端即从终端Slaver。Master与Slaver之间通过短距离通信技术进行通信,终端通过广域网接口与应用服务器连接。当主终端发起业务时,依据各终端以及其接入网的特性,以实现效用函数最大为目标,确定协同分流传输方案,服务器对数据进行分流,分别通过不同的路径到达从终端,最后分流数据通过短距离无线通信技术在主终端汇聚,完成整个业务的传输。令MT0表示主终端,M={1,2,⋯,M} 表示泛在环境下候选的从终端集合。令N={1,2,⋯,N} 表示接入网络。接入到网络n中的终端MTm称为虚拟终端 (m,n) 。假设终端只能同时接入到一个网络中,则从终端以及其接入网络共有M×N种组合。用M×N阶矩阵S表示表示虚拟终端的可用性。若 (m,n) 可用,则Smn= 1 ,否则,Smn= 0 。即
其中,1 ≤ m≤ M,1 ≤ n ≤ N 。
对可用的虚拟终端集合,即Smn= 1的虚拟终端,用子集a S表示。
1.2系统模型
此处只研究无线链路部分,对有线链路不做研究,则可得系统模型如图2所示。
本文所提算法综合考虑终端及接入网网络性能、运营商喜好、用户喜好以及业务特点。其中,终端及接入网网络性能通过终端接入网的下载速率、链路时延以及终端能耗来体现;运营商喜好通过代价来体现。令Bi表示网络i的总带宽,RBi为网络i的可用带宽。设总的数据比特率为R ,数据包长度为Lp,则总的业务到达率为 λ = R Lp。令 λk表示分配给链路k的业务数据的到达率,则。 μk表示终端k从接入网所获得的系统服务率。由文献[11]可知,当排队系统处于稳态时,每条链路的时延为1( μk- λk)。用Em表示终端m在终端协同中的能耗,能耗的计算采用文献[12]中的方法,即对于实时业务,Em= Pm,其中,Pm为终端m的发射功率(W);对于非实时业务,Em= PmBn,其中Bn为终端m的接入网n的带宽。定义M×N阶矩阵Q为Qo S评估矩阵。
2基于终端协同的分流优化算法
本文提出的多属性决策的终端协同分流传输速率分配算法通过计算终端接入网的下载速率、链路时延、用户代价以及终端能耗4个因子的权重,得到协同终端及其接入网的性能值,从而进行速率分配。
2.1权重确定
2.1.1层次分析法
在层次分析法中,权重的确定可体现用户的主观喜好以及业务要求。权重可通过以下3个过程确定。
1)标准化终端及其接入网络属性
在本文所提算法中,考虑终端的下载速率、链路时延、用户代价以及终端能耗4个因子,其权重表示为
将测量到的属性值用矩阵Fi来表示
式中 :Fimn表示终端m在网络n中的第i个属性值 , 1 ≤ i ≤4 。
由于这些属性值没有统一标准,故应该对其进行标准化。设。对于用户而言,这些属性可分为越大越好型和越小越好型。对于属于越大越好型的下载速率属性而言,标准化公式为
对于属于越小越好型的链路时延属性、代价属性以及终端能耗属性,标准化公式为
从而可得一个新的标准化属性矩阵如
2)建立判断矩阵
将终端接入网的下载速率、链路时延、用户代价以及终端能耗4个属性进行两两比较,并按照重要程度排列等级。比较结果用判断矩阵为
3)权重确定
此处,权重的确定采用文献[13]中的方法,即通过对判断矩阵中的元素求几何平均值来得到各因子的权重
进行归一化,可得
经过上述3个过程,通过层次分析法可得4个因子的权重向量
2.1.2熵值分析法
由于层次分析法的判断矩阵受决策者判断水平及个人喜好主观因素的影响,使分流算法具有主观随意性。因此, 在本文提出的多属性决策的终端协同分流算法中,在考虑终端用户主观喜好的基础上,也考虑各终端及其接入网络之间的客观差异,即基于信息熵理论,求解各因子所占的权重。
fmni的概率为
fmni的信息熵为
由信息论知识可知,某一属性在不同终端及接入网络间的差异越大,则信息熵越小,此时此因子的权重就越大。
用Di表示因子i在不同终端及接入网络间的差异,则有
则可得因子i的权重为
利用熵值 分析法所 得的各因 子的权证 向量为
为综合考虑终端用户主观喜好以及各终端及其接入网络之间的客观差异,需将上述两个方法得到的权重进行分配,即得综合权重
其中,0 < α < 1。
2.2终端选择
为评估所选终端及其接入网的性能,构造效用函数如
在终端协同中,设候选终端的个数为y ,但网络并不一定有y个,因为可能有多个终端接入到同一个网络中。协同终端算法主要分为两部分,即终端选择和速率分流。
终端选择的具体步骤为:
1)列出所有虚拟终端的组合,从而得到虚拟终端组合矩阵S ;
2)测量得到所有虚拟终端的4个属性值,即矩阵Fi;
3)更新所有可用虚拟终端矩阵a S ;
4)由式(15)计算所有可用终端的效用函数值Umn;
5)对终端m接入到不同网络的效用值从大到小进行排列,最大值对应的终端及其接入网记为Max Umn,同时令Smt= 0, 1 ≤t ≤ N ,且t ≠ n ,以防止相同的终端进行重复选择;
6)Max Umn对应的所有可用虚拟终端即进入候选终端集合。
2.3速率分配
此时,候选终端在前文已经选出。设选出的协同终端的个数为c ,则1 ≤ c ≤ y 。
速率分配的具体步骤为:
1)将候选终端的效用函数值按照从大到小的顺序进行排列,记为o MT={o MT1,o MT2,···,o MTy} ;
2)初始化协同终端数目,即令c = 1;
3) 令m= 1 , 则1 ≤ m≤ c。 按照公式Pre Ratem={o MTm/∑o MTm}×Rate对c条无线链路进行速率预分配Pre Ratem;
4)更新可用带宽RBm;
5)判断Pre Ratem≤ RBm是否成立。若成立,再判断m= c是否成立;否则,令c = c + 1;
6)判断1 ≤ c ≤y是否成立。若成立,跳转到步骤2); 否则更新候选终端集合,重新进行速率分配;
7)若m= c成立,速率分配结束;否则,跳转到步骤3)继续。
多流速率分配算法流程如图3所示。
3算法性能分析
在此部分,通过假设一些网络参数以及终端参数,根据系统模型进行仿真,从而对所提算法进行性能分析,并与其他算法进行性能比较。
3.1仿真参数设定
假设系统网络环境由UMTS、WLAN1、WLAN2三种网络组成,其编号为1~3,终端个数为10,并进行编号1~10。假设有4个终端只分布在UMTS网络中,3个终端可同时接入到UMTS和WLAN1中,剩余3个终端可同时接入到UMTS和WLAN2中,具体网络参数如表1所示。另外,假设终端在UMTS中下载速率在0~200 kbit/s随机分配,在WLAN1中下载速率在300~600 kbit/s随机分配,在WLAN2中下载速率在500~800 kbit/s随机分配。
为了验证所提算法的性能,与如下两种算法进行性能比较:
DOS(Delay-only Selection)算法,进行从终端选择时以系统时延最小为目标来进行选择。
AHP算法,进行从终端的选择时只考虑用户喜好,并不考虑网络以及终端间的客观差异。
根据前文描述,本文在进行仿真验证时以实时业务为例进行算法性能分析,并建立实时业务的网络属性判断矩阵
由此判断矩阵可得实时业务在AHP算法中的权重因子为 ω'=(0.250 7,0.598 1,0.096 8,0.054 4)。本文算法中计算所得的权重因子为 ω =(0.390 6,0.438 0,0.103 1,0.068 3)。
由式(9)、(13)、(14)可计算得出AHP方法的权重以及本文提出算法的权重,然后由式(15)得到所有可用终端的效用值,并进行从大到小的排列。
3.2性能分析
在进行业务传输时,利用多终端协同对系统性能的影响就是可提高资源整合能力,从而提供系统的吞吐量,降低系统时延。此部分通过此算法的系统效用、系统时延、系统能耗以及系统负载4个方面进行分析。
本文算法以系统效用最大为目标,对选出候选终端效用由大到小进行排列,即得候选终端组合((8,3),(6,2),(7, 2),(10,3),(9,3),(1,1),(5,2),(2,1),(3,1),(4,1))。 AHP算法只考虑用户主观喜好,其候选终端组合顺序为 ((10,3),(6,2),(8,3),(9,3),(5,2),(1,1),(2,1),(7,2), (4,1),(3,1))。DOS算法以系统时延最小为目标,其选出的候选终端组合顺序为((9,3),(10,3),(8,3),(10,3),(6,2), (7,2),(5,2),(2,1),(4,1),(4,1),(3,1))。
由图4可知,随着从终端数目的增加,系统效用并未增加。因为本文算法中候选终端组合的效用是从大到小进行排列的,在进行终端协同时,优先选用效用最大的终端进入虚拟终端系统,因此,随着从终端数目的增加,系统效用反而是下降的。由于在系统效用的表示中,本文算法综合考虑了终端的下载速率、网络的时延、用户代价以及能耗等因素,而AHP算法仅考虑用户主观喜好,刚开始选择的从终端并非效用最大,因此,当效用值较大的从终端进入虚拟终端系统时, 其系统效用会增加。DOS算法也是同样原理,由于WLAN2网络中终端时延相同,其在终端8~10中随机选择,因此DOS算法的系统效用先增大后减小。由图3可知与AHP算法以及DOS算法相比,在从终端数目较少时,本文算法具有很大优势。但随着从终端数目的增加,3种算法的差距并不明显。但本文算法的系统效用仍然是最大的。
由图5可知,随着从终端数目的增加,系统时延是减少的。此处的时延考虑的是业务请求的接入等到时延。但随着协同终端的增加,时延的下降变得平缓。在图5中,DOS算法的时延最小,因为此算法只关心时延,并不考虑能耗等其他性能,优先选择时延小的终端进入虚拟终端系统。但由图6可知,其能耗最大。
图6给出了采用不同协同终端数目下的协同能耗。与不采用多流传输的方式相比,基于终端协同的多流传输将会极大地减少能耗,但随着协同终端数目的增加,SR通信接口所需的能耗增加,将导致整个系统的能耗也随着增加,但仍低于传统的传输方式的能耗。
通过图5的时延以及图6的能耗的比较可知,在进行终端选择时,不能只根据网络或终端性能的某一项指标实现局部最优选择,要综合权衡多方面的因素,才能使得系统效用最大。
以业务速率R=15 Mbit/s为例,分析各网络采用不同终端数目时其负载状况,由图7所示。在本文算法中,通过比较终端所分配速率以及网络可用带宽,进行速率调整。假设在此业务请求之前各网络为空载状态,则由图7可知,在M=1时无法响应业务请求,故通过速率调整,令M=2再进行速率分配。由图7还可知,当M=3时也需要进行速率调整方可满足网络带宽约束以及用户需求。
图8给出了R=15 Mbit/s时采用不同协同终端数目时各终端所分配的速率。由图8的走势可知,随着协同终端数目的增多,各终端间分配的速率差异越来越小。这样并不能充分发挥出效用值较大的终端的优势,因此,随着协同终端数目的增加,图5中时延的减少越来越不明显。在图8的速率分配中可看出,当由多个终端进行协同多流传输时,是根据选择的虚拟终端的性能按比例进行速率分配的,并非根据接入网络的可用带宽进行阶梯分配。此种分配方式保证了不同用户间的公平性,让所有用户都有机会利用最优的虚拟终端。
由上面的仿真图4~8可知,采用本文所提出的从终端选择算法以及本文的速率分配算法时,在满足用户需求的前提下,所选择的从终端越少,系统效用越好。同时,终端的干扰范围会随着协同终端个数按比例扩大,有可能会影响到无线网络的空间频分复用。因此,在满足业务Qo S要求的同时,应尽量减少协同终端的数目以减少干扰范围。
4结论
为充分利用用户周围的网络资源以及终端资源,为用户提供更优质的用户体验,终端协同成为研究热点。本文针对终端协同时的多流并行传输问题,提出了一种多流速率分配算法。此算法在实现从终端选择的同时完成了各协同终端之间的速率分配。通过仿真所做出的性能分析表明,在算法中所提出的速率调整,不仅能够充分利用优势网络的资源, 还可满足网络资源的约束,同时也能满足用户业务体验。
摘要：为充分利用用户周围的网络资源以及终端资源,为用户提供更优质的用户体验,终端协同成为研究热点。针对基于终端协同的多流并行传输问题,提出了一种多属性决策的并行多流速率分配算法。进行从终端选择时,通过多属性决策算法综合考虑终端用户主观喜好,以及各终端及其接入网之间的客观差异。在速率分配的过程中,以各网络资源为约束,不断地进行速率调整。此算法在实现从终端选择的同时完成了各协同终端之间的速率分配。通过仿真后的性能分析表明,所提算法不仅能够充分利用优势网络的资源,还可满足网络资源的约束以及减少能耗,同时也能满足用户业务体验。
多算法协同定位 篇5
随着人工智能技术在交通管理中的应用,智慧交通的建设受到了极大的关注。对车牌的正确识别是建设智慧交通的基石,因此车牌识别成为当前研究的热门领域。目前车牌识别技术已经被运用到违章检测(电子警察)、停车场不停车收费、车辆检测等领域。
车牌定位是车牌识别的关键和重要前提。从复杂的背景中正确定位车牌位置,是成功识别车牌的重要成功率,直接影响最终车牌识别的效果。在车牌定位方面,国内外学者都做了大量的研究,并提出了一些多车牌定位的算法。比较常用的算法有以下几种:
1)基于纹理的分割方法,主要利用车牌区域水平方向的纹理特征进行分割,包括小波纹理、水平梯度差分纹理等[1]。该方法定位成功率不高,因为车牌图像中很可能不止一个区域具有车牌区域的纹理特征,难以准确找到车牌位置;而且对车牌倾斜度有要求,当倾斜度过大时,车牌定位效果明显下降。
2)基于边缘检测的分割方法通过检测车牌字符的边缘特征定位车牌[2]。由于许多汽车前脸栅栏有很多垂直或水平边缘,因此会影响定位成功率。
3)基于神经网络的方法,选取训练样本,将图像的灰度序列采用BP算法进行训练,获得有效的网络权值[3]。该方法用BP网络对灰度图像进行感知,能够获得较好定位效果。
4)基于数学形态算法的方法,利用开运算和闭运算对图像进行处理,得到多个区域,再对这些区域进行判断,找到车牌正确位置[4]。
以上算法在背景不太复杂的情况下,对于单车牌都有比较好的定位成功率。但对于复杂背景下的多车牌定位,则需要综合多种定位方法,排除更多的干扰因素来确定车牌的定位。
基于以上分析,本文采用基于颜色检测、边缘检测与支持向量机相结合的定位方法现多车牌定位。首先针对基于颜色检测车牌候选区域的方法进行改进,并引入了边缘检测的方法来定位,通过颜色与宽高比来选取车牌候选区域,最后基于支持向量机(SVM)完成车牌的精确定位和截取。通过对不同多车牌图片的车牌定位,验证算法的有效性。
2 基于多算法融合的多车牌定位方法
在日常生产生活中,最常见的有小型汽车号牌、大型汽车号牌、警用汽车号牌等。2007年发布的《中华人民共和国公共安全行业标准》(GA36-2007)对我国机动车号牌标准做了详尽规定。小型汽车号牌是蓝底白字白框线的车牌;大型汽车号牌前车牌是黄底黑字黑框线的车牌;警用汽车车牌是白底黑字,红“警”字黑框线车牌。它们的尺寸大小都是440mm×140mm。本文所研究的多车牌定位方法主要是针对小型汽车号牌和大型汽车号牌进行定位。
本文对多车牌定位的流程如下:首先进行车牌候选区的定位;其次进行车牌候选区域的去噪和倾斜校正;最后基于SVM进行车牌精确定位和提取。
2.1 基于颜色和Sobel边缘检测的车牌粗定位方法
RGB颜色模型和HSV颜色模型是数字图像处理中常用的两个颜色模型。RGB彩色模型中,各像素值是由R(红色)、G(绿色)和B(蓝色)三种颜色分量的亮度值叠加来表示。而这三种颜色的亮度值对环境的光照强度比较敏感。当光照强度变化时,这三种亮度值会随之变化。所以,在RGB颜色模型下,很难完成基于颜色的车牌定位。
在HSV颜色模型中,一个像素的颜色特征分别用H(色度)、S(饱和度)和V(亮度)三个分量来表示。亮度分量仅表示亮度信息,不包含颜色信息。如果不考虑亮度分量的信息,使用H和S两个分量就可以实现在各种光照条件下对车牌区域进行初步定位。
2.1.1 RGB模型到HSB模型的转换
普通的车牌图像都是RGB颜色模型,因此需要先将图像从RGB模型转换到HSV模型。
设r,g,b分别是一个像素的红、绿、蓝三个分量的值,它们的值是在0到1之间的实数,max为r,g,b中的最大值,min为这些值中的最小值[5]。则从RGB到HSV的转换公式可用公式表示:
2.1.2 车牌颜色阈值的选择
在我国,常见的车牌底色共有蓝色和黄色两种。在HSV颜色空间中使用H分量能识别出这两种颜色。黄色和蓝色的HSV阈值范围如表1所示。分别用于识别小型汽车和大型汽车的车牌区域。例如,通过蓝色模板的阈值对图片中的像素进行逐个匹配,当图片中的像素能匹配颜色模板的数值时,则置该像素的灰度值设为255,将不匹配的像素灰度值设为0。匹配完成后得到一张包含多个车牌信息的二值图。
2.1.3 基于Sobel边缘检测的车牌候选区方法
在二值图的基础上,通过边缘检测可以得到图片中的所有边缘的信息。本文采用Sobel算子对灰度图进行水平方向的边缘检测。该方法以某一个像素为中心点,对它的周围的八个点的像素值进行加权运算,判断该点是否处于极值状态,若该点处于极值状态,则该点为图像边缘。
车牌存在垂直方向与水平方向的边缘,通过边缘检测,能得到车牌字符的边缘信息。采用Sobel算子对水平方向进行求导,从而得到垂直方向的边缘信息。
2.2 车牌候选区的形态学和矫正操作
形态学运算包括腐蚀、膨胀、开运算和闭运算。腐蚀一种消除边界点,使边界向内部收缩的过程。膨胀是将与物体接触的所有背景点合并到该物体中,使边界向外部扩张的过程。先腐蚀后膨胀的过程称为开运算,用来消除小物体、在纤细点处分离物体、平滑较大物体的边界,同时并不明显改变其面积。先膨胀后腐蚀的过程称为闭运算,用来填充物体内细小空洞、连接邻近物体、平滑其边界,同时并不明显改变其面积。
为了实现更准确的车牌定位和截取,本文对基于颜色和Sobel边缘检测得到的车牌候选区域做闭运算处理,使原本不连续的车牌区域变成一块连同区域。
闭运算处理具体算法如下:
1)设有图像A,B是一个合适的结构元素,先利用公式(4)实现A被结构元素B膨胀,再利用公式(5)实现A对B进行腐蚀操作,这两步的目的是将目标周围的噪声去除。
2)为了将目标内部的噪声去除继续,利用B对A进行腐蚀操作,最后利用B对A进行膨胀操作[6]。
经过闭运算处理之后,车牌的区域能大致从图片中定位出来,但是定位车牌的角度可能会有较大的倾角,这一步需要对图片的倾斜角度进行矫正,以便获取角度正常的字符进行字符的识别处理。
对车牌候选区域进行倾斜矫正的步骤如下:
(1)首先,通过闭运算处理之后的二值图,逐个求出图中连通区域最大外接矩形,并计算最大外接矩形的倾斜角度。
(2)对倾斜角度在-5度到5度之间的图片,可以直接输出。
(3)对倾斜角度在5度到50度,或者-5度到-50度的车牌,需要先调整图片角度。
()调整角度后,判断车牌区域是否为平行四边形。
()如果不是平行四边形,则可以直接输出。
(6)如果是一个平行四边形的区域,再获取平行四边形三个顶点的坐标,通过仿射变换将平行四边形矫正成一个矩形,调整完成,将结果输出。
在输出结果时,需要将图片进行归一化处理,变成宽150像素,高40像素的图片。
2.4 基于SVM的车牌精确定位方法
由于基于颜色的定位会受到与车牌颜色相近的物体的干扰(如图1(a)所示),基于边缘检测的定位会受到汽车车灯等一些边缘信息与车牌相近的物体干扰(如图1(b)所示),影响最终的定位效果。因此引入支持向量机(SVM)来对上面粗选出的候选车牌区域进行判别。
支持向量机是一种基于统计学习理论的机器学习算法,其采用结构风险最小(Sructural Risk Minimization,简称SRM)原则替代传统的经验风险最小(Empirical Risk Minimization,简称ERM)原则进行分类,从而保证了算法具有较强的泛化能力。
SVM的训练过程等价于求解一个线性约束的二次规划问题,其目标是在训练样本集中寻找一个最优的超平面,将样本数据最大限度地分开,使两类数据之间的边界最大且分类误差最小,且能保证得到的解为全局最优解。
在本文中使用图像的直方图特征作为支持向量机的输入特征,输入的特征维度是190。直方图特征的特征量丰富,适用于支持向量机分类,有利于车牌的准确定位。
1)首先,将输入的图像进行二值化处理。
2)统计图像中一行元素中为1的数目,输入的图像共40行,得到40个数据.
3)再统计图像中一列元素中为1的数目,输入图像有150列,得到150个数据。
4)将第二步与第三步得到的这些数据作为SVM的输入特征,输入特征维度为190。
本文使用1000个车牌图像及500个非车牌图像对支持向量机进行训练。
3 实验结果
为了检测本文方法的有效性,本文分别选取了含有两个车牌和三个车牌的图像进行了多车牌定位测试。
经过颜色检测、边缘检测、形态学操作、车牌矫正与SVM筛选等步骤之后,对两个车牌的图像(图2)截取出车牌图片如图3所示。对三个车牌的图像(图4)截取出车牌图片如图5所示。实验表明,本文算法能对包含多车牌图像中车牌的定位的准确率能达到95%以上。
4 结束语
本文提出基于颜色检测、边缘检测和支持向量机(SVM)的多车牌定位综合方法,能从复杂背景中将待识别的多个车牌较准确的定位和截取。该方法首先使用颜色检测和Sobel边缘检测两种方法粗选车牌候选区域,其次对车牌候选区域进行形态学和倾斜矫正处理,最后提取车牌候选区域特征信息利用SVM精确定位车牌区域。实验结果表明,本文所用综合方法能排除背景干扰,多车牌定位效果和成功率较高。
摘要：为了提高多车牌定位和识别效率,本文提出基于颜色检测、边缘检测和支持向量机(SVM)的多车牌定位方法。首先使用颜色检测和Sobel边缘检测两种方法粗选车牌候选区域,其次对车牌候选区域进行形态学和倾斜矫正处理,最后提取车牌候选区域特征信息,采用SVM精确识别和定位车牌区域。实验结果表明,该方法能排除背景干扰,多车牌定位效果和成功率较高。
关键词：多车牌定位,颜色检测,边缘检测,支持向量机
参考文献
[1]郭捷,施鹏飞.基于颜色和纹理分析的车牌定位方法[J].中国图象图形学报,2002,7(5):472-476.
[2]李文举,梁德群,张旗,等.基于边缘颜色对的车牌定位新方法[J].计算机学报,2004,27(2):204-208.
[3]张燕,任安虎.多特征与BP神经网络车牌识别系统研究[J].科学技术与工程,2012,12(22):5644-5648.
[4]戴青云,余英林.一种基于小波与形态学的车牌图像分割方法[J].中国图象图形学报,2000,5(5):411-415.
[5]谭同德,王三刚.基于Open CV的车牌定位方法[J].计算机工程与设计,2013,8(34):2816-2820.
多算法协同定位 篇6
1 威胁评估算法
1.1 威胁评估体系模型的建立和敌机空战能力指数的计算
1.2 空战态势威胁因子的计算
1.2.1 角度威胁因子C1
――我机前置角, 是我机速度偏离我机—目标连线延长线的角度。
――双机进入角, 是敌机速度偏离我机—目标连线延长线的角度。
1.2.2距离威胁因子C2
1.2.3 能量威胁因子
1.3 态势威胁因子权值计算方法
1.3.1请专家根据“标度含义定义”对态势因素两两之间打分
标度定义:1两因素一样重要;3一个比另一个稍微重要;5一个比另一个明显重要;7一个比另一个绝对重要;9一个比另一个重要的多得多;2~8处于上述的中间值;倒数:元素i与j比较是hij, 则j与i是hji=1/hij。
1.3.2进行H阵“一致性”验证
1.3.3 H阵的“一致性调整算法”
本文采用构造矩阵法, 该方法如下:
2 威胁评估算法仿真
仿真:我方有2架Su27飞机, 敌方有3架分别是F15E, F16C, F5E。双机空战能力和态势如表1-3所示。由专家对飞机的各个底层指标进行打分, 按照公式 (1) 计算敌机的空战能力。将表2的参数带入式 (2) , 将表1和2的参数带入式 (3) , 将表3中的参数带入式 (4) , 分别求得角度因子C1、距离因子C2、能量指数C3。计算结果如表4所示。
即c1=0.1676, c2=0.4535, c3=0.3789。选择b1=0.3, b2=0.7, 得到威胁矩阵A:
3 结论和展望
本文对多机协同多目标空战中的威胁评估算法进行研究, 提出一套切实有效的威胁评估算法, 并对其仿真。在现代智能火控系统中, 威胁评估是目标分配算法的前提, 后续将着重开展目标分配算法的研究工作。
摘要：现代空战需要先进的火控计算, 目标威胁评估是其重要的组成部分。文章通过建立威胁评估体系模型, 再提出威胁因子及权值计算方法, 从而构建了一套完整的目标威胁评估算法。最后针对一个多机协同多目标攻击态势, 利用建立的算法进行威胁矩阵的计算, 计算结果表明该方法是有效可行的。
关键词：威胁评估,多机协同多目标攻击,火控
参考文献
[1]宋翔贵, 张新国.电传飞行控制系统[M].北京:国防工业出版社, 2003.
[2]朱宝鎏, 朱荣昌, 熊笑非.作战飞机效能评估[M].北京:航空工业出版社, 1993.
[3]李延杰.导弹武器系统的效能及其分析[M].北京:国防工业出版社, 2000.
[4]雷蕾, 李研俊, 陶晓娟.改进AHP在导弹武器系统作战效能中的应用[J].火力与指挥控制, 2009 (5) :89-91.
一种高精度运动多站无源定位算法 篇7
运动多站无源时差定位技术凭借多定位平台的运动特性, 受地球曲率及建筑、高山的遮挡影响小, 可实现对空中、地面和海面目标的协同高精度定位[1,2,3]。此外, 随着无人机技术的快速发展, 机动灵活的多机协同侦察定位逐渐受到重视, 因此研究运动多站无源定位技术具有重要的应用价值。
在运动多站无源定位的研究中, 文献[4]分析了多机时差定位的单次解算算法, 利用定位精度的几何稀释[5,6] ( Geometrical Dilution of Precision, GDOP) 对其定位精度进行了分析, 但是, GDOP只能描述某一时刻多机平台对某一区域的定位精度, 而无法直观描述机载平台运动过程中对某特定目标定位精度的变化情况。文献[7]研究了三机平台时差定位的扩展卡尔曼滤波 ( Extended Kalman Filter, EKF) 算法, 但并未利用理论精度对其性能进行衡量, 也未提及EKF算法的初始值设定问题。
针对单次解算法定位精度较差及滤波算法受初值影响较大的问题, 本文提出一种单次定位解算和EKF相结合的多次测量定位滤波算法, 并利用CRLB对其性能进行了衡量。所提算法避免了传统EKF算法在实际应用中的初始值选取问题, 并充分利用了多次观测的时差信息, 定位收敛速度更快, 定位精度更高。
1多次 TDOA 测量的定位模型及算法
1. 1定位模型
不失一般性, 考虑二维平面时差定位情况, 假设观测站S i 在k时刻的位置为 ( xk i , yk i ) , 其中i = 0, 1, 2 , 辐射源M的位置为 ( x, y) , 运动多站无源定位系统示意图如图1所示。设S 0 站为定位主站, 则目标信号到达主站S 0 与目标信号分别到达辅站S 1 和S 2 的时间差 ( TDOA) 为:
式中, c为电磁波传播速度。对于二维定位, 利用3个观测站可以得到2条时差曲线, 它们的交点即为目标的位置。
1. 2单次定位算法
根据TDOA方程 ( 1) 有:
ri2 - r02= ( x - xi ) 2+ (y - yi ) 2- (x - x0 ) 2- (y - y0 ) 2, i = 1, 2。 ( 2)
由于Δr i = r i - r 0 , 有ri + r0 = 2r0 + Δri , 因此有
(2r 0 + Δri ) ·Δri = ri2 - r02 。 ( 3)
移项、整理可得:
(x0 - xi) x + (y0 - yi) y = r 0 ·Δri+ 1/2[Δri2 + (x02 +y02 ) - (xi2 + yi2 ) ] , i = 1, 2 。 ( 4)
如果令
ki=1/2 [Δri2 + ( x02 +y02 ) - (xi2 + yi2 ) ], i = 1, 2 , ( 5)
则式 ( 4) 可简化为:
( x0 - x i ) x + ( y0- yi) y = r 0 ·Δri + ki , i = 1, 2 。 ( 6)
写成矩阵形式, 即
Ax = F 。
式中,
如果观测站满足可观测条件则矩阵A可逆, 故得x = A-1F , 则有
将其代入r0 2 = (x - x0) 2+ (y - y0 ) 2表达式, 得 到
式中,
至此, 算法的求解转变为求目标与主站之间的距离r 0 , 式 ( 9) 为关于r 0 的一元二次方程 ( 就r 0 求解的几种情况, 这里不再详述) , 解出r 0 后, 将其代入式 ( 7) 得到目标的位置解。
1. 3多次测量滤波定位算法
运动多站无源定位系统, 由于定位站的位置以及定位站与目标的位置关系处于不断变化之中, 因此随着定位站的运动, 可连续观测到一系列变化的时差值。单次定位算法由于只利用了某一时刻的时差测量, 而没有利用到前后时刻测量值之间的联系, 所以定位精度有限。为了提高运动多站无源定位的精度, 本文充分利用多个观测时刻的时差测量, 使用扩展卡尔曼滤波实现对目标位置的序贯估计。为了解决EKF算法中初始值难以选取的实际问题, 将单次定位与EKF相结合, 把单次测量解算的结果作为EKF的初始估计值, 然后再用EKF对多次连续观测值进行序贯处理, 从而得到更为精确的目标估计值。
设目标第k时刻的估计值为Xk = [x k , y k ]T, 固定目标的状态方程为:
观测方程为:
Z k = h ( X k ) + u k 。 ( 11)
式中, h ( Xk ) = [cτ1 k , . . . , cτm k ]T, u k ~ N ( 0 m×1 , Rm×m ) , R为测量噪声协方差。
设由第一时刻测量时差解算出的目标估计值为, 则将其作为EKF的初始估计值, 即, 同时设定初始协方差P1 , 将式 ( 10) 和式 ( 11) 的状态方程和观测方程直接代入EKF中, 即可以得到目标位置的估计结果。
2理论定位精度推导与分析
CRLB表征了无偏估计量所能达到的最小误差协方差阵, 为任何无偏估计量的方差确定了一个下限, 这为比较 无偏估计 量的性能 提供了一 个标准[9]。
现推导基于CRLB的运动多站无源时差定位的理论定位精度。
①测量数据的概率密度函数 ( PDF) :
②似然函数:
③构造Fisher矩阵J :
式中,
④求J - 1 :
⑤由式 ( 15) 可得到矢量参数X = [x, y]T所能达到的误差下限为, 其中tr (·) 表示矩阵迹运算。
3计算机仿真试验
3. 1仿真试验 1: 固定基线构型
所谓固定基线构型是指运动多站间不存在相对运动, 即随着定位站的运动, 主站到辅站的基线是固定不变的。假定定位场景如图2所示, 目标的真实位置为 ( 300 km, 0) , 定位主站的起始位置为 ( 0, 0) , 辅站1的初始位置为 ( 6. 90 km, 25. 76 km) , 辅站2的初始位置为 ( 6. 90 km, -25. 76 km) , 主站—辅站1基线与主站—辅站1基线夹角150°, 基线长度26. 67 km, 三运动站的速度均为 ( 150 m / s, 0) 。时差测量误差60 ns, 采样率为1/T, T为测量时间间隔。假设蒙特卡罗试验的次数为50次, 位置误差按相对定位误差方式进行统计。相对定位误差定义为:
式中, L为目标与主站间的距离;和为目标估计值。
考虑T =0. 5 s和T =1 s两种情况下的定位性能比较。
固定基线构型的定位结果如图3所示。由图3可以看出, 随着定位站的运动单次定位结果大致维持在0. 6%R ~ 1% R之间, 而本文算法的最终定位精度可达0. 05%R; 与CRLB比较可知, 本文算法可很好地逼近运动多站无源定位的理论下界; 采样时间间隔T = 1 s时, 本文算法在第52 s达到低于0. 2% R的定位精度, 采样时间间隔T = 0. 5 s时, 本文算法在第29 s达到低于0. 2%R的定位精度。
3. 2仿真试验 2: 动态基线构型
所谓动态基线构型是指运动多站间存在相对运动, 即随着定位站的运动, 主站与辅站的基线在不断变化。辅站以20 m/s的速度沿基线飞行, 三站间的基线夹角保持不变, 其余仿真条件同试验1。动态基线构型的定位场景图如图4所示。
动态基线构型的定位结果如图5所示。可以看出, 随着定位站的运动, 单次定位结果大致维持在0. 4% R ~1% R之间, 而本文算法的最终定位精度可达0. 03% R; 在动态基线构型下, 本文算法也能很好地逼近运动多站无源定位的理论下界; 采样时间间隔为1 s时 ( 图5 ( a) ) , 本文算法在第49 s达到低于0.2%R的定位精度, 采样时间间隔为0.5 s时 ( 图5 ( b) ) , 本文算法在第24 s达到低于0.2%R的定位精度。
仿真结果表明: 本文算法大大提升了运动多站的定位精度, 从最终定位精度来看, 定位能力提升约10倍以上。
此外, 由以上仿真结果还可知, 定位站基线的动态变化以及采样率的加快, 有助于改善所提算法的收敛速度和定位精度。
4结束语
充分利用运动多站可连续获得不同时差观测量的特性, 推导了基于CRLB的运动多站无源定位的理论定位精度, 提出单次定位和EKF相结合的多次测量定位算法。该算法避免了初始化问题, 计算量小、定位收敛速度快, 可满足工程化实用要求, 可为运动多站无源定位系统提供技术支撑与参考。
参考文献
[1]刘学, 焦淑红, 蓝晓宇.拟蒙特卡罗聚合重采样粒子滤波无源定位算法[J].西安电子科技大学学报, 2012, 39 (5) :154-160.
[2]潘琴格, 严盟, 廖桂生.多站时差和多普勒频差联合定位技术[J].雷达科学与技术, 2005, 3 (6) :332-335.
[3]郭福成, 李腾.基于时差和频差的固定多站定位方法及分析[J].系统工程与电子技术, 2011, 33 (9) :1 954-1 958.
[4]邢益临.机载无源雷达组网定位技术研究[D].长沙:国防科学技术大学研究生院, 2005:13-30.
[5]邢翠柳, 陈建民.多站无源时差定位精度分析[J].无线电工程, 2012, 42 (2) :32-34.
[6]赵琨, 何青益.基于GDOP的三站时差定位精度分析[J].无线电工程, 2012, 42 (5) :15-17.
[7]王翰.机载多平台时差无源定位系统若干关键技术研究[D].长沙:国防科学技术大学研究生院, 2006:12-34.