（通信与信息系统专业论文）蜂窝网无线定位新算法的研究与仿真.pdf

哈尔滨工程大学颈士学位论文 摘要 本文提出了一种改进的免疫算法，对蜂窝网络无线定位估计中的非线性 优化问题进行求解。在设计记忆库规模的时候，引入了帕累托法则，并使记 忆库魁的个体跟父代群体起参加生存竞争，使搜索过程减少震荡，收敛速 度加快。本论文的所有工作都是围绕着免疫算法在蜂窝网无线定位技术中的 应用展开的。 本文工作的第一大部分是本文的基础部分。我们详细阐述了蜂窝网络无 线定位原理以及相关的无线定位基本方法，建立了定位算法的数学模型。同 时，引入了一种常用于仿真评估基于时间定位技术的信道模型及定位准确率 的评价指标。本部分主要包括论文的第二、三章。 在本文工作的第二大部分，首先介绍了生物免疫系统特性，然后详细描 述了生物免疫系统原理，并给出了生物免疫系统的模型。在此基础上，本文 提出了一种改进的免疫算法，给出了该算法的实现步骤，并对改进后算法的 性能进行了仿真实验。实验证明，在种群规模不大的情况下，该算法也能稳 定快速地逼近全局最优解。本部分主要包括论文的第四章。 本文工作的第三大部分是基于第二部分提出的改进免疫算法，提出了两 种用于蜂窝网无线电定位的新算法，即基于改进免疫算法的t d o a 定位算法 和基于改进免疫算法的t d o a a o a 混合定位算法。实验证明，在高噪声环 境下，也能获得较高定位精度。同时，在考虑n l o s 的影响之后，本文又提 出了一种可以减小n l o s 影响的蜂窝网无线定位新算法。该算法运用了 t d o a t o a 平滑重构技术，并采用改进的免疫算法来进行定位估计，仿真实 验结果表明，该算法对降低平均定位误差的效果显著。本部分主要包括论文 的第五、六章。 在论文的最后对全文进行了总结，并且指出了进一步的工作展望。 关键词：免疫算法；到达时间差定位法；来波角定位法；非视距传播；最大 似然估计；记忆库；帕累托法则 堕玺鎏苫塑盔兰鎏主兰垡笙銮 a b s t r a c t a ni m p r o v e di m m u n ea l g o r i t h mi sp u tf o r w a r da n da p p l i e df o rn o n l i n e a r o p t i m i z a t i o ni n c e l l u l a rw i r e l e s sl o c a t i o n t h en u m b e ro fm e m o r yb a s ei s d e s i g n e du s i n gt h e8 0 2 0p r i n c i p l e t h e nl e tt h em e m o r yb a s ec o m p e t ew i t ht h e p a r e n tp o p u l a t i o n ，b yw h i c h ，t h es e a r c hp r o c e s sd o e s n ts h o c ka n ds p e e d su p i n t h i sp a p e r , a l lo fo u rw o r ks u r r o u n d st h ea p p l i c a t i o n so fi m m u n ea l g o r i t l 柚ai n c e l l u l a rw i r e l e s sl o c a t i o n t h ef i r s tp a r to fo u rp a p e r sw o r ki st h eb a s i co ft h ep a p e r w eg i v et h e t h e o r ya n dm e t h o d so fc e l l u l a rw i r e l e s sl o c a t i o n ，a n db u i l dt h em a t h e m a t i c a l m o d e lo fl o c a t i o n t h e n , w ei n t r o d u c eac h a n n e lm o d e lt h a ti su s e di ne v a l u a t i n g p e r f o r m a n c eo fl o c a t i o na l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a te v e ni f t h e p o p u l a t i o nw e r en o tl a r g e ，t h ea l g o r i t h mi sr o b u s ta n dc a r lf i n dt h ec o o r d i n a t e s q u i c k l y t h i sp a r ti n c l u d e sc h a p t e r2 , 3 i nt h es e c o n dp a r to fo u rp a p e r sw o r k , w ei n t r o d u c ec h a r a c t e r i s t i c sa n d p r i n c i p l eo fn a t u r a li m n u n es y s t e m ，a n dt h e np u tf o r w a r dam a t h e m a t i c a lm o d e l o fn a t u r a li m r n u n es y s t e m 。b a s e do nt h e s e ，a l li m p r o v e di n l l n u n ea l g o r i t h mi sp u t f o r w a r d i th a sah i g ha c c u r a c yi nab a dn o i s eb a c k g r o u n d t h i sp a r ti n c l u d e s c h a p t e r4 t h et h i r dp a r to fo u rp a p e r sw o r ki sb a s e do nt h es e c o n dp a r t t w on o v e l a l g o r i t h m so fc e l l u l a rw i r e l e s sl o c a t i o na r cp u tf o r w a r d ，t h a t s a ni m p r o v e d i m m u n ea l g o r i t h mf o rt d o a - b a s e dl o c a t i o na n da h y b r i dt d o a a o al o c a t i o n m e t h o db a s e do nt h ei m p r o v e di m m u n ea l g o r i t h m i th a sah j l g ha c c u r a c yi nab a d n o i s eb a c k g r o u n d m e a n w h i l e ，c o n s i d e r i n gn l o s ，w ep u tf o r w a r dar e d u c i n g n l o s sa l g o r i t h m t h ee x p e r i m e n ts h o w st h a tm u c hb e t t y l o c a t i o np e r f o r m a n c e c a r lb eo b t a i n e d t h i sp a r ti n c l u d e sc h a p t e r5 , 6 t h eg e n e r a lw o r ko ft h i s p a p e ri ss u m m a r i z e da n dt h ef u r t h e rr e s e a r c h d i r e c t i o ni sp o i n t e do u ti nt h el a s tc h a p t e r 啥尔滨工程大学硕士学位论文 k e yw o r d s ：i m m u n ea l g o r i t h m ；t d o a ；a o a ；n l o s ；m a x i m u ml i k e l i h o o d e s t i m a t e ；m e m o r yb a s e ；8 0 趁0p r i n c i p l e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文静繇有工作，。是在导筛的指辱下， 由作者本人独立完成的。有关观点、方法、数据和文献的引 用已在文中指出，并与参考文献相对应。除文中已注明引用 的内容外，本论文不包含任何其他个人或集体己经公开发表 的俘黧l 成果。对本文戆磷究微懑重要荧觳鳃个人鞠集体，均 已在文中以明确方式标明。本人完全意识到本声明的法僖结 果由本人承担。 作者( 签字) ： 刻磁。 爨期：2 0 0 5 年2 周1 8 冀 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 根据美国联邦通信委员会( f c c ) 的计划，到2 0 0 1 年1 0 月，所有蜂窝 电话、个人通信系统、专用移动无线电的移动网络许可运营商将以可定位 概率6 7 _ 9 6 、均方误差为1 2 5 m 的精度要求为请求e 一9 1 l 紧急呼叫的移动用户 提供二维的位置信息。美国f c c 的这一规定明确了提供e - 9 1 l 定位服务将 是今后各种蜂窝网络，特别是3 g 网络必备的基本功能。由于政府的强制性 要求和市场本身的驱动，各国主要大公司均就g s m 、i s 一9 5 和第三代移动通 信系统等网络开始制定各自的定位实施方案。特别是3 g p p 和3 g p p 2 上对定 位的要求更具体化，促使国际上出现了基于蜂窝网络的无线定位技术的研 究热潮。基于蜂窝网络的无线定位技术研究既可满足移动台的定位需求， 也可应用于蜂窝网络系统设计及网络资源管理，如基于移动台位置的灵活 收费策略、预防欺诈行为、车辆管理及智能运输系统等。目前，g s m 和 c d m a 2 0 0 0 网络的定位系统已经进入商用，虽然其定位精度有待于提高，手 机成本也有待于降低，但用户仍然在迅速增长( 尤其是在日本和韩国) ， 这充分说明蜂窝无线定位市场潜力巨大。 1 2 蜂窝网无线定位系统 目前，在蜂窝网络中对移动台的定位需求主要是提供移动台的位置坐 标信息及其定位精度估计、时戳等辅助信息，对速度、运动方向等信息还 没有明确要求【。定位功能的实施应充分利用蜂窝网络和g p s 等已有的系 哈尔滨工程大学硕士学位论文 统资源，并尽可能少地影响网络的原有功能，选择适当的定位系统类型、 相应的定位技术及其实施方案。 无线定位系统中对移动台的定位是通过检测移动台和多个固定位置收 发信机之间传播信号的特征参数( 如电波场强，传播时间或时间差，入射 角等) 来估计出目标移动台的几何位置 2 1 。在蜂窝网络中，根据进行定位 估计的位置、定位主体以及所采用的设备的不同可将对移动台的无线定位 方案分为三类：基于移动台的定位方案，基于网络的定位方案以及g p s 辅 助定位方案【3 】【”。基于网络的定位方案只需要对蜂窝网络设备作适当扩充、 修改，不需要对现有移动台进行任何修改，能充分利用现有各种蜂窝系统 的庞大资源，保护用户已有投资，实现相对容易，并能达到一定精度，因 而这种方案适用于现有蜂窝网络。基于同样的考虑，本文所讨论及研究的 定位算法均为基于网络的定位算法。 对于基于网络的定位方法，目前主要有：基于c e l l i d 定位和基于时问 提前量( t a ) 定位的方法、上行链路信号到达时间( t o a ) 定位方法、上行 链路信号到达时间差( t d o a ) 定位方法以及上行链路信号到达角度( a o a ) 定位方法等。其中，基于c e l l i d 定位方法易于实现，覆盖率高( 整个网 络无线覆盖范围) ，在各种无线环境中均有着良好的鲁棒性，而且对整个通 信网络没有任何影响，但是其定位精度与服务区大小成正比，在1 0 0 m 以 内( 微蜂窝) 或3 - 6 k m 以内( 郊区宏蜂窝) 。对时间提前量( t a ) 的方法， 由于使用了g s m 系统的特有参数t a ，在宏蜂窝时，其在g s m 系统中的 定位精度可以控制在5 5 0 m 以内，比c e l l i d 定位方法有较大改进，但容易 受多径、n l o s 、几何精度因子( g d o p ) 等影响大，鲁棒性较差。此外， 与t o a 和a o a 定位技术相比，t d o a 更容易实现。 i 3 蜂窝网无线定位技术的研究进展 自e 9 1 1 定位需求颁布以来，移动台定位技术在国外受到高度重视和 哈尔滨工程大学硕士学位论文 深入研究，近年来在i e e e 的有关期刊和会议，特别是v t c 上发表了大量 研究论文，也出现了不少定位技术的发明专利以及一些专门从事定位技术 的研究和开发的公司，如c e l l o c a t e ，t r u e p o s i t i o n 等。目前研究的内容涉及 了蜂窝网络移动台定位技术的方方面面，并且更侧重于基本定位方法和技 术的研究，定位算法的研究，t d o a 、a o a 检测技术的研究，抗非视距传 播、多径和多址干扰技术的研究，数据融合技术方面的研究，定位技术实 施方法的研究，定位系统的性能评估等。 在各种期刊、会议论文和其他文献中，对基于蜂窝网络移动台定位技 术研究具有代表性的有：j a m e sj c a f f e r y ，j r 在其定位技术专著“w i r e l e s s l o c a t i o ni nc d m ac e l l u l a rr a d i on e t w o r k s ”【5 】及发表的论文1 6 1 0 】中主要展 开了对c d m a 网络采用d l l 得t o a 检测技术的研究，抗非视距传播、多 径和多址干扰技术的研究，n l o s 环境下高精度定位算法的研究；p i c h u n c h e n 的博士论文“m o b i l ep o s i t i o nl o c a t i o ne s t i m a t i o ni nc e l l u l a rs y s t e m s ” 和相关论文1j 1 , 1 2 中侧重于c d m a 网络导频信号t d o a 测量技术，非视距 误差消除技术，移动台定位跟踪技术等方面的研究；y t c h a n 提出了一种 在t d o a 误差服从理想高斯分布时性能优良的t d o a 定位算法 1 3 l ； r s c h m i d t 提出了一种新型t d o a 定位算法【1 4 】；m e w y l i e 在文献【1 5 】中则 提出了一种判断及消除n l o s 误差的经典方法，目前很多针对n l o s 误差 消除的研究都是对该方法的进一步深入：e r i c s s o n 公司提出了一种对移动 台进行定位估计的信道模型【1 6 】，该模型基于实际测量结果，适用于各种蜂 窝网络信道环境；m c g u i r e 提出了一种鲁棒估计函数【 】，用于改进n l o s 环境下对移动台的定位估计，还提出了一种基于时间差测量值观测得到的 测量值非参数近似的定位估计算法【l 引，在n l o s 环境下也取得了较好的定 位性能；t h o m a s k l e i n e o s t m a n n 扩充了数据融合技术的应用范围，提出了 一种应用于移动台定位估计的数据融合模型【1 9 】，拓宽了移动台定位技术的 研究范畴；d o n g - h os h i n 对t o a 和t d o a 的误差统计特性，g p s 系统中 g d o p 、定位估计及协方差矩阵的关系进行了研究，还对无线定位系统的 哈尔滨工程人学硕士学位论文 误差统计特性进行了分析【2 0 】，其研究方法值得借鉴；m a s o 提出了适用于 信号强度测量、t o a 、t d o a 定位的采用最大似然函数的定位估计方法【2 ”， y i t e n gh u a n g 提出了一种线性修正最小二乘算法1 2 2 】，a a b r a r d o 和s s w a n g 等则对c d m a 蜂窝网络定位系统的性能进行了分析和评估 2 3 , 2 4 ， s m a n g o l d 将隐马尔可夫模型( h m m ) 的模式识别技术应用于蜂窝网络移 动台的定位估计【”l 。x u e m i ns h e n 将模糊逻辑技术应用于m s 的定位估计 2 6 1 ，m i c h e l 则在其专利2 7 1 中研究开发了在下行链路采用t d o a 、t o a 、 a o a 等多种技术对m s 进行定位估计的方法和设备。这些研究大都取得了 丰硕的成果。 1 4 本论文研究的主要内容 本论文的研究熏点是改进免疲算法在蜂窝网无线定位估计中的研究与 性能仿真，提出了鼹释基予免疫簿法的蜂窝隧无线定位舞法瞅及一静抗 n l o s 建谴算法。 本文共分六章： 第一章简要地介缨了蜂窝蹦茏线定位系统以及蜂窝网茏线定位技术的 臻究遂装，舞餐要糕括了论文工佟。 第二章对蜂窝网无线电定位撼本原理进行了简要介绍，并引入了一种 常用于仿真评估基于时间定位技术的信道模烈及定位准确率的评价指标。 第三搴蓄受建交了蜂窝瓣无绫定蹙基本舞法懿数学模凝，然矗奔缀了 三种经典的定位算法，并对这些算法的性能进行了仿真研究，并作了比较 评价。 篱菠牵是本论文煞孩心部势，首先奔缓了生物受疫系统特毪，然爨译 细描述了生物免疫系统原理，并绦出了生物免疫系统的横溅。在此基础上， 本文提出了一种改j l 的免疫算法，给出了该算法的实现步骤，并对算法的 性能进行了仿真实验。最屠，本文婚免疫算法与遗馋算法黪了魄较。 4 哈尔滨工程大学硕士学位论文 第五章基于前一章节提出的改进免疫算法，提出了两种用于蜂窝网无 线电定位的新算法，即基于改进免疫算法的t d o a 定位算法和基于改进免 疫算法的t d o a a o a 混合定位算法，并对每种算法进行了实例仿真和性 能分析。 第六章首先引出了蜂窝网无线定位中的n l o s 问题，然后对n l o s 环 境下的t d o a f f o a 误差进行了分析。在此基础上提出了种可以减小 n l o s 影响的蜂窝网无线定位新算法，最后对该算法作了仿真和性能分析。 在本论文结论部分，总结了本文所做的工作，并对未来发展方向进行 了展望。 哈尔滨工程大学硕士学位论文 第2 章蜂窝网无线定位原理 在各种无线电定位系统中，采用的基本定位方法和技术都是相同或相 似的，都是通过检测某种信号的特征测量值实现对移动台的定位估计。从 几何角度来讲，确定目标在二维平面的位置可以由两个或多个曲线在二维 平面内相交得到。 2 1 蜂窝网无线电定位基本原理 在蜂窝网络中为移动台提供的地面二维定位服务，通常可供选择的基 本定位原理有以下几种。 2 1 1 圆周定位原理 如果已知移动台到基站f 的直线距离足，则根据几何原理，移动台一定 位于以基站i 所在位置为圆心，r 。为半径的圆周上，即移动台位置k ，y o ) - 与 各基站位置g 。，弘) 之间满足如下关系： g ，一) 2 + 一y o ) 2 = 砰 ( 2 1 ) 如果已知移动台与三个基站之间的距离，以三个基站所在的位置为圆 心，移动台与三个基站的距离为半径画圆，则三个圆的交点即为目标移动 台所在的位置。 在实际无线电定位方法中，通过测量从目标移动台发出的信号以直线 到达基站i 的时间f l ( t o a ) ，可以得到目标移动台与基站的距离r ，= c ，。， 其中，c 为电磁波在空中传播速度，即c = 3 1 0 8 m s 。对于i ；1 , 2 ，3 ，联立 上述方程组，即可得到移动台坐标位置k ，) 。由于t o a 与距离r ，的关 系，三圆相交定位法又称为t o a 定位法。 6 哈尔滨工程大学硕士学位论文 在蜂窝网络中只要在移动台对前向链路多个基站发射信号进行场强测 量或在多个基站对反向链路移动台发射信号进行场强测量，再根据有关定 位算法求解测量距离方程组，就能计算出移动台的估计位置。 然而，对于c d m a 通信系统，由于特有的“远近效应”问题，系统通 常必须采用功率控制。此时，基站接收到的信号功率并不能反映基站和移 动台之间的实际距离，因为对基站而言，在达到理想功率控制时候，从各 移动台发射后到达基站的信号强度应当是相同的。 2 1 2 双曲线定位原理 当已知基站b s ，和基站b s ：与移动台之间的距离差为r ，= r ：一r 时， 移动台必定位于以两基站b s l 和b s 3 为焦点、与两个焦点的距离差恒为风 的实线双曲线对上。当同时知道基站b s a 和基站傩、与移动台之间的距离差 为r 。= r ，一马时，可以得到另一组以两基站嬲。和傩，为焦点、两个焦点 的距离差恒为r 。的实线双曲线对上。于是，两组双曲线的交点代表对移动 台位置的估计。 与t o a 定位方法类似，基站b s l 和基站嬲，与移动台之间的距离差可 以通过测量得出，即通过测量从两个基站同时出发的信号到达目标移动终 端的时间差，2 。来确定，或者测量从移动台出发到达两个基站的时间差t 。 显然，r 2 l = c x t 2 1 ，其中，c 为电磁波在空中传播速度，即c = 3 l o s 聊s 。 双曲线定位中移动台坐标位置，y 。) 和基站坐标位置g 。，y ，) ( i = 1 , 2 , 3 ) 有 如下关系： 因为方程式两边同时求平方的缘故，解上述方程组后可以得到两个解。 由于两个解中只有一个代表移动台的真实位置，故需要一些先验知识( 如 小区半径等) 来分辨出真实的解，以消除位置模糊( 解模糊) 。一些文献也 焉焉 哈尔滨工程人学硕士学位论文 将双曲线定位法称为基于电波到达时间差( t d o a ) 的定位法，即t d o a 定位法【”，它也是目前在各种蜂窝网络中主要研究和采用的定位方法。 2 1 3 方位测量定位原理 方位测量定位方法也称为信号到达角度( a o a ) 定位方法5 ，2 8 1 。本方 二怯是通过基站接收机天线或者天线阵列测量出移动台发射电波的入射角， 从而构成一根从接收机到移动台的径向连线，即方位线。利用两个或两个 以上接收机提供的a o a 测量值，按照a o a 定位算法来确定多条方位线的 交点，即为待定位移动台的估计位置。 假设基站b s l 和基站嬲，分别测量得到移动台发出信号的到达角度分 别为o l 和岛，则下式成立， t a n ) ：盟，i ：1 , 2 ( 2 3 ) y o y l 通过求解上述非线性方程，可以得到移动台位置，y 。) 。 2 1 4 混合定位原理 混合定位方法是综合利用上述两种或者多种不同类型的信号特征测量 值，如t o a a o a 、t d o a a o a 、t d o a t o a 进行定位估计7 ，2 9 1 。 例如，如果一个基站能够同时测量得到移动台发出信号以直射路径到 达基站的时间t l 和角度只，则移动台相对于基站的距离r 。= c t 。和方位角 0 1 已知，于是由下式可以解出移动台位置k ，y 。) ，即 it a n ) 。嚣 ( 2 - 4 ) 一) 2 + 以一虬) 2 = “) 2 通过对上述定位方法特点的分析比较，可以发现a o a 定位法虽然有 一定的精度，但是要求接收机具有高精度的智能天线阵列，系统设备复杂， 而且只能从反向链路定位；t d o a 和t o a 定位法在蜂窝网络中实现相对 哈尔滨工程大学硕士学位论文 皇宣i 眚i i 宣葺宣i i i 置篁宣萱羞_ 鼍_ _ - _ _ _ _ _ _ _ - 一i _ _ 置皇_ 萱皇宣i i 窜 容易一些，也能达到较高精度，因此这两种方法，特别是t d o a 定位法， 受到了更多的重视；混合定位法则能够吸收不同定位法的优点，但是需要 再提供不同的信号特征测量值。综上所述，目前在蜂窝网络中受到广泛关 注和深入研究的是t d o a 、t o a 定位法以及混合定位法。 2 2t i p i 无线定位信道模型及定位准确率评价指标 2 2 1t i p l ( c o s t 2 5 9 ) 信道模型 t 1 p 1 信道模型悬由e r i c s s o n 的个移动台斑位技术研究小组提出的， 是一种常用于仿真详估基于时闻定位技术的馈邀模型，也称为c o s t 2 5 9 绩遭模掇嬲。 t 1 p 1 信道模型中的每一种信邋环境包括一定数量的散射体，每个散射 体由平均功率q ，、越摄延时和平均到达角度表征a 每个散射体由大 量夔予浚维成，每令子渡筵瓣稳瓣，毽到达楚痍不嚣，嚣藏霉爨蕊囊每个 散射体的衰落情况。不同信道环境的具体参数如表2 1 所示。 表2 1t 1 p 1 信道模型参数 数瓣箨 平均廷薅扩 环缓 延爵t 耜对臻率只 。 震：平驽超鲎 个数 延时 o 5 1 5 x e x p 卜6 f f 。) 都带 l 2 0 乳 l ：l 毒鏊 1 o o f 。 静5 1 5 xe x p ( - 6 哆r 。) 1 ：i a 向市区a 类似但应随相对功率 市区 l 2 0 调速延时： l 。5 ：l 嚣 “七+ 允) 2 。 郊区 lo4 3 2 “ o f 。 o 1 0 4 2 ：1 乡毒|黛邦区 9 哈尔滨一l ：程大学硕士学挝论文 2 2 2 延时扩展g r e e n s t e i n 模型 t 1 p 1 模型中的延时扩展是根据g r e e n s t e i n 模型1 3 l 】( 一种基于实际测量 值的模型) 来产生的，即： f 。= 巧d 6 y ( 2 5 ) 其中，f 。，是均方根延时扩展，五是在d = 1 o n 处延时扩展的中值，s 取值 在0 5 到1 之间，y 是一个标准差为d 。的对数正态分布随机变量。不同信 道环境下的参数如表2 2 所示。 表2 2 不同环境的g r e e n s t e i n 模型参数 环境 五 占 盯y 都市区 1 o0 54 d b 一般市区0 4o 54 d b 郊区 0 _ 3 0 54 d b 远郊 0 1o 54 d b 山区 1 01 04 d b 基站a o a 测量值基于本地散射圆模型【3 2 1 ，服从具有以下标准差的高斯 分布： ( ) = 堡d ( 2 6 ) 其中，为超量延时，c 为电波传播速度，d 为m s 与b s 之间的距离。 2 2 3 定位准确率评价指标 为了正确评价各种定位算法在实际蜂窝网络环境中的定位性能，需要 首先确定评价定位准确率的指标。目前最常用的指标是定位解的均方误差 ( m s e ) 、均方根误差( r m s e ) 、累积概率分布函数【5 l ( c d f ) 等。在后面 的章节中，将主要采用以上指标对相关算法的定位精度进行讨论和评价。 1 、均方误差( m s e ) ： m s e = e b i ) 2 + t y 一力2j ( 2 _ 7 ) 1 0 哈尔滨工程人学硕士学位论文 2 、均方根误差( r m s e ) ： r m s e ：同瓦可碉 ( 2 - 8 ) 3 、累积概率分布函数( c d f ) ： c d f 是指在某个精度门限以下定位次数在总定位次数中所占比例，如 定位误差在1 2 5 m 以下的定位次数在所有定位次数中所占的百分比，通常 记为c d f 0 2 5 ) 。 2 3 本章小结 该章节是本论文的基础部分，首先对蜂窝网无线电定位基本原理进行 了简要介绍，然后引入了一种常用于仿真评估基于时间定位技术的信道模 型及定位准确率的评价指标，为以下章节的分析研究创造了良好条件。 本章的工作为后续的对蜂窝网络无线定位问题的探讨打下了一个很好 的基础。 哈尔滨工程大学硕士学位论文 第3 章蜂窝网无线定位基本方法的研究 在无线定位系统中，一旦获得t o a t d o a 的测量值，就可以得到移动 台到基站的距离或者移动台到两个基站之间的距离差。多个t o a t d o a 测量值就可以构成一组关于移动台位置的圆周曲线x 2 曲线方程组，求解该 方程组就可得到移动台的估计位置。由于圆周曲线双曲线方程组不是一组 线性方程组，因此，求解并不容易。目前，已经提出了多种具有不同精度 和计算复杂性的算法。本章将先介绍定位算法的数学模型，然后介绍相关 的算法。 3 1 定位算法的数学模型 3 1 1 定位问题的最小二乘( l s ) 表示 在无线定位系统中，对移动台进行定位估计采用最广泛的算法是最小 二乘1 2 2 , 3 3 1 ( l s ) 法则。该算法可以应用于采用t o a 、t d o a 和场强测量值 定位估计的系统。在蜂窝网络中，只要根据某种测量值建立了相应的特征 方程，就能求解出移动台的位置1 2 9 1 。 设根据测量值建立的方程： y = a x( 3 1 ) 其中，y 是已知的 1 1 维向量，x 是m x l 维未知向量，哇是h x m 阶矩 阵。如果厅 珊，则系统方程大于未知数数目，可利用最小二乘法获得z 的 最优估计。 定义”x 1 维残差向量如下： ，= a x y ( 3 2 ) 哈尔滨工程大学硕士学位论文 现在需要求的值，使得残差的平方和最小，即： ，暖) = ( 4 x y ) 2 = ( 4 z j ，y ( a 石一y ) ( 3 3 ) 其中，t 代表转置运算。对上面的方程求导并令其为零，得： d f ( x ) ：2 a7 爿x 一2 4 y ：o( 3 。4 ) d x 如果a a 是非奇异的，解工得： z = l a 7 a | i j a7 y ( 3 - 5 ) 这就是最小二乘法的解，其中 a r a 厂是辅助因子。如果m = m 而且一是 非奇异的，最小二乘法的解归结为下列唯一解： z = 爿一1 ，( 3 6 ) 以上过程只描述了权值相等的情况，在实际应用中，可以采用加权最 小二乘法，即根据每个测量值的精度( 可靠性) ，在最小二乘中采用不同的 权值，以提高定位精度。残差加权平方和函数为： ，伍) = w 2 池一】，) 2 ( 3 7 ) 其中矽为加权矩阵，合理选择可以有效地提高定位精度。理论已经 证明，当取测量值误差方差矩阵的逆阵时，可以使估计误差的方差最小。 此外，由于残差方程通常为非线性方程，往往不能直接求解，需要采用本 章中的所提到的算法进行求解。 3 1 2t d o a 双曲线模型 在撩窝两终中采琢t d o a 按零x 雩移囊台逡抒定位氆计拜孛，一登取褥菜 个t d o a 测量值，就可以得到移动螽到两个基站之间的距离麓，多个t d o a 测量值就可以构成缀关于移动螽位置的双曲线方程组，求解该双曲线方 程组裁霹毅褥羹移动螽懿 砉诗位纛。设蕊y 海m s 戆铸l 鑫诗链鬟，取，誓 为第f 个撼站发射机的已知位置，则由第二章的知识可知，m s 和第f 个撼 站发射机之间的距离【1 3 1 为： 哈尔滨工程人学硕士学位论文 r ，= ( 置一x ) 2 + 一，) 2 ( 3 - 8 ) r ? = 伍，一工) 2 + ( t l ，) 2 = k 。一2 x 。z 一2 r , y + z 2 + y 2 其中， k 。= 工f 2 + ，：2 令r i j 表示m s 与基站i 和基站1 ( 服务基站) 的距离差，则 r 坩= c d = r j - r 。= ( x 一x ) 2 + ( i y ) 2 一( x ，一工) 2 + 瓴一y ) 2 ( 3 9 ) 其中，c 为电波传播速度，d t 为t d o a 测量值。为求解该非线性方程 组可以先进行线性化处理f 3 4 】。因为： r ? = + r 1 ) 2 ( 3 - 1 0 ) 式( 3 1 0 ) 可以展开表示为： r 2 + 2 r l , i r 】+ r ? = 置一2 x t x 一2 z y + z 2 + y 2 ( 3 1 1 ) 在i = 1 时，式( 3 8 ) 为： 胄? = k t - 2 x , x 一2 y l y + x 2 + j ，2 ( 3 1 2 ) 式( 3 - 1 1 ) 减去( 3 1 2 ) 可得： 矗盎+ 2 r u r l = 墨一2 z ，1 x 一2 r 1 y k l ( 3 - 1 3 ) 式中，x u = x ，一x l ，z ，1 = r 一巧。将x ，j ，r 1 视为未知数，则式 ( 3 - 1 3 ) 成为线性方程组，求解该方程组便可以得到m s 的坐标位置。 3 2 f a n g 算法 f a n g 算法 3 5 1 利用3 个基站对m s 进行二维位置定位。为简化计算，首 先将三个基站置于以下坐标系统：基站1 ( o ，o ) ，基站2 ( x ：，o ) ，基站3 ( x ，y ，) 。 以下公式简化为： r = 厄i 再而：厢 4 x n ：x r x i = x t r 1 = y ，一k = y ， 式( 3 - 1 3 ) 可以简化为： 一2 r 2 ：r l = r i l 一工；+ 2 x 2 工 一2 r ”r l = r 列2 一口；+ 坪) + 2 2 3 x + 2 y 3 y ( 3 1 4 ) 令式( 3 1 4 ) 中两式相减( 消去最) ，可得简化结果： y = g j + h ( 3 - 15 ) 式中， g = 娅纠x ：) r ：r x ， 匕 而：扛；+ e r ”2 + 尺”r 2 ：0 一扛：r ：，。) 2 ) 2 e 将式( 3 1 5 ) 代入式( 3 1 4 ) 中的一个方程，并利用关系式曩= 岳w 可得： d x 2 + e x + ，= 0 式中， d = 一1 一伍：r ：，。) 2 ) + 9 2 e = x 2x ( 1 一伍：r ：，) 2 ) 一。2 9 x h ，：乜；。4 ) 6 一伍：r ：，。) 2 1 2 一h 2 ( 3 1 6 ) 解方程( 3 - 1 6 ) ，可得两个x 值，利用有关先验信息选择其中之一，代 入式( 3 - 1 5 ) 就能取得m s 的坐标估计y 。在蜂窝网络中上述模糊性并不 存在，有关文献的仿真结果表明：由式( 3 1 6 ) 中的根0 e + 4 而比d 确定的m s 位置通常超出服务小区的范围，因此我们只需要选择式( 3 - 1 6 ) 的根： 哈尔滨： 程大学硕士学位论文 x ：! = 壁互) ( 3 - 1 7 ) 2 d 将其代入式( 3 1 5 ) 中，即可得到m s 的估计位置g ，y ) 。 3 3c h a n 算法 c h a n 算法【1 3 1 是一种具有解析表达式解的非第归的双曲线方程组解法。 该算法的特点是计算量小，在噪声服从高斯分布的环境下，定位精度高。 但在非视距( n l o s ) 环境下1 3 1 1 ，c h a r t 算法的定位精度显著下降。 1 、 3 基站时的算法 当有效测量基站数目为3 时，可得到两个t d o a 测量值，先假定r 为 已知，则m s 位置b ，y ) 可以由式( 3 - 1 3 ) 按n n - f n 式解出： 妒隐甜1 啦弦2 小 r 托 j - k 3 + + 黜 式中， k 1 = 卜1 2 k 。= ；+ 砰 k ，= x ；+ 埒 将式( 3 - 1 8 ) 代入式( 3 - 8 ) ，令i = l ，得到一个关于旯，的二次方程，将菸 正根代回式( 3 1 8 ) ，就得到m s 的估计位置。在某些情况可能得到两个厩 攫，麓f a n g 雾法类织，这秘模凝毪虿蠢毒关燹验镶塞逶露逸择。 2 、4 个以上基站时的算法 当橱效测量基站数目为4 个以上的时候，c h a n 算法能利用网络提供的 葳鸯t d o a 测量餐势取褥更好麴诗冀结莱。藏簿t d o a 溅虽篷数曩多予 未知量的数目，困j 魄，初始菲线瞧t d o a 方程组应该首先转换为线性方程 组，然聪采用加权最小二乘( w l s ) 算法得到一个初始解，再利用第一次 褥到的镳计健置坐橡及萁辫搬变爨等已知款约寒条传进行第二次w l s 链 1 6 哈尔滨工程大学硕士学位论文 计，最后便能得到改进的估计位置。令乙：i ：r i r 为未知矢量，其中 z 。= by 】7 ，从式( 3 - 1 3 ) 中求出的具有t d o a 噪声的误差矢量为： = h - g 。z ： ( 3 1 9 ) 式中， 厅= 1 2 r i 。一x ；一y ；+ x ? + k 2 r ；，一爿；一坪+ ? + r 1 2 胄三。一r 丢一增2 + x ? + 巧2 g o = z 2 ，l1r 2 ，1 e 1r ” ，1 ，1 在此，我们定义无噪声时p ) 的表达形式为p ) o ，故d 。= d 。o + 一， r 。= r “o + c 吩，；又由于r o = r ：l + 胄? ，可以得到噪声的误差矢量为： v = c b n + 0 5 c 2 玎。甩( 3 - 2 0 ) 其中， b = 啦g 渡，r o ，r 品 式中。代表s c h u r 乘积。当s n r 高时，由广义互相关( g c c ) 检测的 t d o a 测量值通常为高斯数据，服从近似的正态分布，因此噪声矢量n 也 服从近似的正态分布，误差矢量的协方差矩阵便可以算出来。在实践中条 件c 疗。 r o 通常可以满足，因而式( 3 - 2 0 ) 中第二项可以忽略，误差矢量 y 成为具有以下协方差距阵的高斯随机矢量： 甲= e l 7 j - c 2 b q b( 3 2 1 ) 其中q 为t d o a 协方差矩阵，z 。中蜀与式( 3 - 8 ) 有关，表明式( 3 1 9 ) 仍然是以x 和j ，为变量的线性方程组。 求解该非线性方程组的时候，首先假定x ，y 和足之间无关，然后通 1 7 过w l s 算法进行第一次求解。最终结果可以通过将已知关系( r 和x ，y 之间的关系，即式( 3 - 8 ) ) 代入第一次的结果中，再进行一次w l s 计算得 出。这两步是对m s 位置的最大似然( m l ) 估计的近似。 如果假定乞的元素问互相独立，z 。的m l 估计为 z a = a ，r g m i n h - 、g a z a ) 一1 ( - g a z a ” ( 3 2 2 ) = 妊甲g 。r 1 g ；甲。h 。 该式是式( 3 - 1 9 ) 的w l s 解，目前该式还不能解出，因为b 中含有m s 与 各个基站发射机之间的距离，故甲仍然是未知量。为此，需要作进一步近 似。 当m s 距离很远的时候，群( i = 1 , 2 ，3 ，m ) 与矗o ( 定义距离) 接近， 故b * r o ，。由于y 的量纲没有什么影响，式( 3 - 2 2 ) 可以近似为： z 。= q - 1 g 。) _ 1 g r q 一1 h ( 3 2 3 ) 如果m s 距离较近，利用上式可得到一初始解用于计算b 矩阵，第一 次w l s 计算的结果可以由式( 3 - 2 2 ) 得到。 为进行第二次w l s 计算，需要首先计算估计位置z 。的协方差矩阵。该 矩阵可以通过计算= 。的期望值及z 。z 。t 得到。由于皖含有随机量r 订，直接 计算很困难，该协方差矩阵可采用扰动方法计算。在有噪声的情况下： r u = 只? l + c 疗d ( 3 - 2 4 ) 而且 g 。= g ：+ a g 。，h = h o + 舶 由于g o z ：= h o ，式( 3 - 1 9 ) 表明： y = a h a g 。z ： ( 3 - 2 5 ) 令乙= z ：+ a r 。，由式( 3 2 2 ) 可得到： 妞7 + 饼一1 ( g ：+ a g 。k ：+ a z 。) ：( g ：7 + q - 积+ ) ( 3 2 6 ) 保留线性扰动分量，再利用式( 3 2 0 ) 和式( 3 - 2 5 ) ，比及其协方差矩 哈尔滨工程大学硕士学位论文 阵为： 毛：c ( g ：7 甲。g 。0b 。0 7 v 。西t c 。v k ) ：e k 。a z f 】：妇7 旷嘭) _ 1 ( 3 2 7 ) 其中忽略了式( 3 - 2 0 ) 的平方项，式( 3 - 2 7 ) 用于计算c o v ( z 。) 。 上述有关乙的计算过程假定x ，y 和r 。是相互独立的。事实上式( 3 - 8 ) 表明它们是相关的，因此，我们能利用这种关系来改进定位估计。当t d o a 测量误差较小时，这种偏差可以忽略，矢量：。为一均值为实际值，协方差 矩阵由式( 3 - 1 8 ) 确定的随机变量，因此z 。的元素可以表示为： z 引= x o - - e 1 ，z 以2 = y o + e 2 ，z 目3 ；月? + 巳 ( 3 - 2 8 ) 其中e l , p ：，巳为z 。的估计误差。z 。的前两个元素减去x 、，k ，再对各元素求 平方可得另一个方程组： 缈= h g 。z ： ( 3 - 2 9 ) 其中， h = 飞p1 k x 2 户l ， 南| ，一f g 尚) 2 一b 一罗；) 2 这里怒义为z 。的谈差矢量。将式( 3 - 2 8 ) 代入式( 3 - 2 9 ) 中得： 以- 2 一蜀k + e ；*