2010年11月Journal on Communications November 2010 第31卷第11期通信学报V ol.31No.11基于核函数法及马尔可夫链的节点定位算法 赵方1，罗海勇2，林权3，马严4 （1. 北京邮电大学软件学院，北京 100876；2.中国科学院计算技术研究所普适计算研究中心，北京 100190； 3.中航工业综合技术研究所，北京 100028； 4.北京邮电大学信息网络中心，北京100876） 摘要：基于贝叶斯滤波框架，提出了基于核函数法及马尔可夫链的节点定位算法，该算法采用射频指纹匹配技术，使用核函数构建似然函数，充分利用观测与多个训练样本之间的相似性，避免使用先验确定型信号分布模型产生的误差。此外，为提高移动目标的定位精度和定位实时性，该算法还使用马尔可夫链，通过利用目标的历史状态和环境布局等信息对匹配定位的网格搜索空间进行限制，剔除目标移动过程中不可能发生的位置跳变。实验证明，与高斯分布模型相比，所提定位算法具有更高的定位正确率和定位精度。 关键词：节点定位；核函数；马尔可夫链 中图分类号：TP301 文献标识码：A 文章编号：1000-436X(2010)11-0195-10 Node localization algorithm based on kernel function and Markov chains ZHAO Fang1, LUO Hai-yong2, LIN Quan3, MA Yan4 (1. School of Software Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. Research Center for Pervasive Computing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 3. Avic Aero-Polytechnology Establishment , Beijing 100028, China; 4. Information Network Center, Beijing University of Posts and Telecommunications, Beijing 100876, China) Abstract: To position indoor objects accurately and robustly, a novel node localization based on kernel function and Markov chains was presented, which employs Bayesian filter framework and radio fingerprinting technology. It uses kernel function to construct likelihood function to take full advantage of the similarity between observation and several training samples, which avoids the error brought by employing a priori determined distribution model. Furthermore, the proposed algorithm uses Markov chains to improve the localization accuracy and shorten the positioning time. It limits the search space of the matching grids with object's previous state and the environment layout, and refuses the object’s impossible position jump during the moving process. Experiments confirm that the proposed localization outperforms the algorithm with Gaussian distribution model. Key words: node localization; kernel function; Markov chain 1引言 现有无线传感器网络（WSN, wireless sensor networks）定位技术一般采用红外线、超声波、射频等传感信号。其中基于红外线、超声波的定位技术精度相对较高，不过由于需要使用专门的硬件设 收稿日期：2010-03-31；修回日期：2010-10-05 基金项目：国家科技重大专项基金资助项目（2010ZX03006-002-03）；国家自然科学基金资助项目（60873244, 60973110, 61003307）；北京市自然科学基金资助项目（4102059） Foundation Items:Important National Science & Technology Specific Projects(2010ZX03006-002-03); The National Natural Sci-ence Foundation of China (60873244, 60973110, 61003307); The Natural Science Foundation of Beijing (4102059)
马 尔可夫预测算法 综述 马尔可夫预测法以系统状态转移图为分析对象，对服从给定状态转移率、系统的离散稳定状态或连续时 间变化状态进行分析马尔可夫预测技术是应用马尔可夫链的基本原理和方法研究分析时间序列的变化规律，并预测其未来变化趋势的一种技术。 方法由来 马尔可夫是俄国的一位著名数学家 (1856—1922)，20世纪初，他在研究中发现自然界中有一类事物的变化过程仅与事物的近期状况有关，而与事物的过去状态无关。针对这种情况，他提出了马尔可夫预测方法，该方法具有较高的科学性，准确性和适应性，在现代预测方法中占有重要地位。 基础理论 在自然界和人类社会中，事物的变化过程可分为两类:一类是确定性变化过程；另一类是不确定性变化过程。确定性变化过程是指事物的变化是由时间唯一确定的，或者说，对给定的时间，人们事先能够确切地知道事物变化的结果。因此，变化过程可用时间的函数来描述。不确定性变化过程是指对给定的时间，事物变化的结果不止一个，事先人们不能肯定哪个结果一定发生，即事物的变化具有随机性。这样的变化过程称为随机过程一个随机试验的结果有多种可能性，在数学上用一个随机变量（或随机向量）来描述。在许多情况下，人们不仅需要对随机现象进行一次观测，而且要进行多次，甚至接连不断地观测它的变化过程。这就要研究无限多个，即一族随机变量。随机过程理论就是研究随机现象变化过程的概率规律性的。客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往往条件变化，状态也会发生变化状态即为客观事物可能出现或存在的状况，用状态变量表示状态： ??? ? ?????=???==,2,1,,2,1t N i i X t 它表示随机运动系统，在时刻),2,1( =t t 所处的状态为),2,1(N i i =。状态 转移：客观事物由一种状态到另一种状态的变化。设客观事物有 N E E E E ...,,321共 N 种状态，其中每次只能处于一种状态，则每一状态都具有N 个转向（包括转向自身），即由于状态转移是随机的，因此，必须用概率来描述状态转移可能性的大小，将这种转移的可能性用概率描述，就是状态转移概率。
实验报告 一．实验目的 1、掌握二维测向交叉定位方法； 2、掌握二维测向交叉定位的误差。 二．实验内容 设定两个测向站，设置其位置坐标参数，对辐射源的测向角度。分别给定出真实值和测量值（包含误差），并且分别计算出辐射源的理论位置和测量位置，二者进行比较并且计算出圆概率误差CEP和定位模糊区大小和位置误差。 三．实验原理 1.测向原理 二维平面测向定位：在已知的两个或多个不同位置上测量雷达辐射电磁波的方向，各站测得的雷达方向数据按三角测量法交会计算出雷达的位置（图1）。雷达与两个测量站的距离分别为
若已知两个侦察站的位置为11(,)x y 和22(,)x y ，由它们对辐射源E 测向，测得的方位角分别为1θ和2θ（由方位基准逆时针为正向），并得到两条位置线即等方位线，利用两条位置线相交所得的交点即可确定辐射源的坐标位置(,)e e x y 。 1111e e y y tg m x x θ-==-2 222 e e y y tg m x x θ-==- 由于11(,)x y 和22(,)x y 的两个坐标位置是已知的，而1θ和2θ是测得的，即1m 和2m 可以测量得到。则可以得到辐射源位置： 1 112211e e x m b y m b --?????? =??????-???? ?? 2. 圆概率误差为 CEP ≈= 当155θ≈ ，2125θ≈ 时，CEP 达到最小值，此时22CEP K ≈≈3. 定位模糊区 2221232112214()4() 4sin sin()sin sin sin() R R th uv h tg A θθθθθθθθθ??=== -- 当1=60θ ，2=120θ 时，A 达到最小值，此时22 22min 3 4()62()(sin 60) h tg A h tg θθ?==? 4. 位置误差 测得的位置与真实位置之间的距离r 成为位置误差。 222 22 112212123 232cos (sin )R R R R r θθθθθθ?+?+??= 2222 31211[](sin )(sin )(sin ) r h θσσθθθ=+
第18卷 第7期 中 国 水 运 Vol.18 No.7 2018年 7月 China Water Transport July 2018 收稿日期：2018-03-08 作者简介：马骁骏（1996-），男，河北张家口人，硕士生，上海理工大学 光电信息与计算机工程学院，研究方向为地图 匹配、路径规划等。 基于隐马尔可夫模型的基站定位地图匹配算法研究 马骁骏1，李 烨2 （1.上海理工大学 光电信息与计算机工程学院，上海 200093；2.上海理工大学 光电信息与计算机工程学院，上海 200093） 摘 要：在基站定位过程中，信号衰减、噪声干扰、基站群切换等因素会造成定位数据误差大、无效点多，隐马尔可夫模型若基于定位点间的大圆距离计算转移概率，可能降低最终的路段匹配准确率。文中首先去除定位数据中的不可能点，然后利用截尾均值滤波技术进行预处理；以候选点间的大圆距离替代定位点间的大圆距离、并结合相邻定位点间的时间间隔计算转移概率，利用维特比算法解得最优移动轨迹。基于OSM 实际路网数据的仿真结果表明，文中方法明显提高了基站定位数据的匹配精度。 关键词：基站定位；地图匹配；隐马尔可夫模型；维特比算法；滤波 中图分类号：TP391 文献标识码：A 文章编号：1006-7973（2018）07-0064-03 引言 如今，智能手机用户常使用基于位置的应用程序，并与服务提供商共享他们的位置数据。大量的位置数据对于智能交通系统（Intelligent Transport System，ITS）应用非常有用。例如，这些数据可用于预估道路行驶时间、交通拥堵检测和交通流量预测。但由于位置数据存在误差，这些数据只能通过与电子地图匹配后才可以应用于上述工作。 智能手机可通过多种方式生成位置数据，例如GPS 定位、Wi-Fi 定位和基站定位。不同的定位方式其定位误差差别很大。研究表明，GPS、Wi-Fi 和LBS 定位的定位误差分别可达8、74和600m [1]。虽然GPS 定位具有极好的定位精度，但是，对手机电池的消耗也比其他定位方法高近10倍[2-3]。Wi-Fi 定位主要应用于室内定位场景，不适用于道路网络上的车辆。与前两者相比，LBS 定位虽然定位精度不够高，但它的能耗和成本更低[2]。与匹配GPS 或Wi-Fi 定位数据相比，这种有噪声且误差大的LBS 定位数据的地图匹配是很困难的。为了使这种数据可以应用到智能交通系统中，需要改进现有的地图匹配算法。 本文通过对基站定位方法以及地图匹配理论的研究，提出了一种基于隐马尔可夫模型（Hidden Markov model，HMM）的地图匹配算法。首先利用α-截尾滤波器[4]对基站定位原始数据进行预处理，然后基于隐马尔可夫模型方法对问题建模，定义转移概率模型，利用维特比算法求解以获得最可能的道路序列，对原始移动轨迹进行修复。我们使用来自实际路网的LBS 位置数据来测试该方法，并与文献[5]中的HMM 算法进行比较。 一、基于基站定位的地图匹配算法研究 1．电子地图解析 使用定位数据进行地图匹配时，需要与路网数据结合，从而将定位点投影到对应的路段上面。本文采用的路网数据 来源于Open StreetMap （OSM）[6]，地图数据格式为XML （eXtensible Markup Language），地图数据处理流程如下： （1）解析路网数据，解析从OSM 下载的XML 格式的地图数据，解析出来的地图数据主要包括该块地图区域的点（node）、路（ways）、关系（relation）以及边界信息。这四种元素构成了整个地图画面。其中，node 定义为空间中节点的位置；ways 定义为路段或者区域；relation 定义为元素之间的关系。 （2）获取路网中的道路等级信息（highway）标签的值，如高速公路（motorway）、主干道（primary）、次干道（secondary）等，从而得到各个道路的速度限制以用于定位数据的速度过滤。 2．定位数据预处理 由于基站定位数据本身误差大、噪声高，直接应用基于隐马尔可夫模型的地图匹配算法不会有好的修复效果，所以在地图匹配前，需要对定位数据进行预处理，以剔除对匹配产生错误的定位点。预处理步骤如下： （1）去除不可能点。由于基站定位中非视距传播（NLOS）、噪声干扰、信号衰减以及基站群切换时产生的“乒乓效应”[6]造成定位过程中产生错误的无效数据即不可能点。车辆的速度受到很多因素的限制，包括车辆本身的最高速度和道路车速限制。因此，我们假设车辆不能超过一定的速度阈值。利用定位数据的经纬度值以及时间戳，我们可以得到任意两点间的速度值。通过其与速度阈值的比较，如果速度值大于阈值，则后面的点为不可能点； （2）α-截尾均值滤波：采用基于顺序量统计理论，针对中、长拖尾干扰噪声而设计的非线性滤波器。相比与中值滤波和均值滤波，α-截尾均值滤波器可以同时处理包含脉冲、高斯噪声的数据。
无源探测技术作业 主讲老师：成萍 作者
无源探测技术中测向交叉定位方法原理及应用 1、无源探测技术简介 现代化战争是高科技的战争。为了在战争中彻底准确摧毁敌方有生力量，瓦解敌方的战斗体系，保障我方部属安全，就需要知道敌方的准确位置。于是，定位技术成为现代战争体系中一项必不可少的关键技术，作为电子对抗的重要组成部分，一直受到人们的关注。 所谓定位是指，由单个或多个分布式的有源或无源探测器，通过探测目标（散射体或辐射体）反射或发射的信号，分析信号中的数据和有关参数，应用合适的数据处理方法，估计出目标在空间中的位置。通常，按探测器种类划分，定位可分为有源和无源两大类。有源定位指探测器自身要发射电磁波，通过接收目标的反射波和相关信息进行定位，其中最主要的就是雷达对抗技术。从最近几次高科技局部战争来看，针对传统雷达的电子干扰和抗干扰斗争愈发激烈，参战单位更注重隐身，反辐射导弹成为新宠，同时低空突防技术也获得更大发展。这些都使得传统雷达探测定位技术面临的障碍不断增加，使人们意识到必须发展新的定位技术。无源定位因此深受青睐，其发展速度一直呈上升趋势。所谓无源定位就是指，探测器自身不发射电磁波，仅利用目标本身辐射或散射第三方辐射波进行定位。相对于有源定位，其具有隐蔽性和反电子侦察能力强的突出优点，从而成为现代战争中机载对敌、对海攻击以及对付隐身目标的远程预警系统的重要组成部分，大大提高了战斗系统在电子战环境下的生存能力和作战能力。 相对于传统的有源定位系统，无源定位系统有以下四大优点： 1、最大的优点在于工作时本身不发射电磁能量，具有良好的隐蔽性，能有效地抵抗反辐射导弹和反侦察定位系统，生命力强，适应环境快。 2、无源定位技术与收发分置的双基或多基雷达系统类似，且工作在甚高频和超高频，因此能更有效地对隐身目标进行探测定位。 3、无源雷达系统自身不发射信号，省去了昂贵的高功率发射机和收发开关及相关电子设备，使系统制造和维护成本大幅降低。当前，世界上一些国家在新型功率器件方面对我国采取禁运的手段，因此此项优点对我国情况有很大吸引力。 4、外辐射源的天线都设置在贴近地面的高处，因此对低空飞行的飞机和巡航导弹有利，具有良好的抗低空突防性能。