位置指纹定位技术

位置指纹定位技术 位置指纹定位技术 山西电子技术 2007年第5期 综述 位置指纹定位技术 套晏 (桂林电子科技大学信息与通信学院,广西桂林541004) 摘要:在室内利用无线网络对移动目标定位,可用的技术有基于波达时间(T0A/ 『DIrjA),基于波达角度 (AOA),以及基于接收信号强度(RSS)的技术等.比较而言,基于接收信号强度(RSs) 的位置指纹(LF)技术更适合 于复杂的室内环境.对该技术目前的研究情况进行比较全面和详细的介绍. 关键词:室内;定位;位置指纹 中图分类号:TN92文献标识码:A 0引言 作为移动通信和个人通信服务的一部分,位置服务变得 越来越重要了.要提供位置服务,首先必须获得目标的位 置.利用GPS定位在室外能提供令人满意的精度,但是在 室内并不适用,因为其功率电平太低,在环境噪声或是多径 干扰的影响下几乎不能工作;而专门使用室内定位系统又存 在人员,频谱和资金方面的问题,所以最好利用现有的系统 和设施. 现有的定位系统主要有三种定位:1)三角测量法: OA/TDOA技术,至少需要3个不同的固定基站;2) 使用T 角度测量法:使用AOA技术,至少需要2个不同的固定基 站;3)信号强度测量法:使用基于RSS的传输损耗或位置指 纹技术,可以只用1个基站.由于室内严重的多径环境,无 论测量对间还是测量角度都会引起较大的误差,要想减少这 种误差需要显着提高算法复杂度或是增加相当规模的额外 设备.与此不同的是,基于测量RSS的技术着眼于利用而 不是消除多径带来的影响. 基于RSS的技术主要有两种:传输损耗(RFPL,Radio FrequencyPropagationk)ss)定位法和位置指纹(LF,Location Fingerprint)定位法.前者将信号传输模型和建筑的地理信 息转换成距离测量值,这样做很简单,但是受很多方面的影 响,比如距离,信号穿透墙壁时的损耗,多径传输等,所以难 以建立正确的数学模型.后者则可以应付NLOS和多径传 输的状况,但是建立和维护数据库比较麻烦-3j. 1位置指纹(I)定位技术 信号的多径传播对环境具有依赖性,呈现出非常强的特 殊性,对于每个位置而言,该位置上信道的多径结构是惟一 的,终端发射的无线电波经过反射和折射,产生与周围环境 密切相关的特定模式的多径信号,这样的多径特征可以认为 是该位置的"指纹".基站天线阵列检测信号的幅度和相位 等特性,提取多径干扰特征参数,将该参数与预先存储在数 据库中的指纹数据进行匹配,找出最相似的结果来进行定 收稿日期:2007—03—20作者李昊男27岁硕士研究生 位. 1,1位置指纹定位的两个阶段 位置指纹定位的实施一般可以分为两个阶段:第一阶段 为训练/N线阶段,主要工作是采集所需定位区域各参考节 点(RP,ReferencePoint)位置的信号特征参数,例如信号场 强,多径相角分量功率等,将一组指纹信息对应一个特定的 位置形成位置指纹数据库.第二阶段为定位/-ff线阶段,利 用接收机测定接收信号的参数,采用匹配算法来确定与数据 库中哪一组数据相匹配,从而得出用户的实际位置. 1.2位置指纹定位的特点 指纹定位的优点是一个基站即可实现定位,定位精度比 较高;可以充分利用现有的设施,不需要改变移动设备的硬 件,系统无需或仅增加极少的额外设备;升级和维护对用户 影响小.其缺点是前期工作量大,以及不适合环境变化太快 的区域.指纹定位的定位精度取决于数据库的大小,要提高 测量精度,需要先对定位区域做详细的测量,建立庞大的数 据库,且数据库必须定期或不定期进行更新,因为没有数据 的区域将无法提供定位服务. 1.3隐私权问题 如果由基站或网络发起定位,则用户的隐私权可能受到 侵犯,因为有时用户并不想让基站或网络测量其位置.这可 以改为由用户发起定位,不但改善了隐私权的问题,也降低 了网络的持续计算量…. 1.4最小间隔 将需定位区域划分为若干网格,网格的大小影响到定位 的精度.间距太小会使数据库增大许多,但是对提高精度贡 献不大,因为各种参数变化都很小;而间距太大则精度大幅 度下降.性能与时延的折衷程度较好的一种划分是:较 空旷的区域(如走廊)用10英尺*10英尺的网格,房间内用 5英尺*5英尺的网格…. 2数据库的生成【3J 第5期李昊:位置指纹定位技术 2.1普通的数据库生成法 依次接收并测量每个RP的RSS,与RP的位置一一对 应后记录入数据库.当RP按区域的大小和形状整齐排列 成网状时定位效果较好.RP的排列接近均匀分布时,其间 距可以指征定位精度.RP增加时很有可能(但不一定)改善 精度,若间距小于某一阈值后就几乎没有效果了.当RP均 匀分布时,其节点间距: g=~/_(1) 式中:S是区域总面积,N是RP的个数. 2.2利用空间相关建立数据库 如果需要建立数据库的区域很大,采用普通方法不仅费 时费力,而且数据库庞大,维护起来比较麻烦.要是能用较 少的RP数据以插值的方法生成数据库,就可以减轻这方面 的负担.文献[3]中介绍了两种插值的方法:加权距离反转 法(WDI,WeightedDistanceInverse)和克里金法(kriging). WDI是比较简单的插值方法,是以周围位置z()估计 的未抽样位置37o的变量z的值,即 ,, (×Z() Z(黝)=—一 Z : . 1 ad (2) 式中d是位置37o到位置之间的距离. kriging以变化图为基本工具来验证观测值的空间关系. 它是最佳线性无偏估计(BLUE,BestLinearUnbiasedEstlma tion),有两个特点:一是根据无偏准则和最小偏差准则,该估 计是带权重计算的关于数据的线性函数;二是由描述函数族 结构的变化图唯一决定一个线性方程组的系数,该线性方程 组的解就是权重.krig~ng法的一个主要好处是比其它插值 法更灵活,因为它是基于空间上函数的变化,而不是基于只 适用于某些情况的人为制定的准则;另一个好处是它能提供 估计误差量级的手段. 3定位算法及其比较 3.1最近邻法(YN,NearestNeighborhcod)[3J 最近邻法是最基本的算法,该方法首先计算测量所得的 RSS矢量与数据库中各矢量之间的距离,选取最小距离对应 的数据库矢量,以其所代表的位置坐标作为结果输出.定义 广义距离为 Lq=(?1s—S})1/q(3) i:1 其中s是测量所得的RSS矢量,S是数据库中的矢量.q= 1和2时分别是曼哈顿(Manhattan)和欧几里德(Euclidian) 距离,实验表明q增大并不一定能增加精度. 3.2K近邻法(KNN.KNearestNeighborhc~t)【0?J 这是最近邻法的改进型算法,其区别在于不是选取最小 距离对应的那一个数据库矢量,而是从最小距离开始选取K (K?2)个最接近的数据库矢量,再计算它们的平均坐标作 为待测目标的位置输出. 设Sff是第i个基站中的第个样值,S是在线阶段第i 个基站的一个观测值,i=1,2,…,m,J=1,2,…,,z,m是基 站个数,是样值数据的数目.Si与数据S"之间的距离 r———————一 = ??(sf—s)J=12",,z(4) 从结果中从小到大选取K个样值,以式(5)计算它们位 置坐标的均值作为结果输出. (三,;)=去()(5) 式中(37,Yi)是第i个被选取的样值所对应的坐标. 3.3K加权近邻法(KWNN.KWeightedNearestNeighbor— hcod,[0】 该方法与K近邻法的不同之处在选取了K(K?2)个数 据库矢量后,不是计算它们的平均坐标作为待测目标的位置 输出,而是给每个数据库矢量对应的坐标乘上了一个加权系 数,最后的位置输出 户=(赤P)(6) 其中L是测量所得的RSS矢量与第i个数据库矢量之间 的距离,e是很小的正常数以防除数为0,是第i个数据库矢 量对应的坐标. 3.4概率算法[.1 设有n个位置oAl,oA2,…,oA,在离线阶段这n个位置上 的设备会测量附近基站的RSS.设s是在线阶段测量得到 得RSS,则根据公式(7)选取后验概率最大的OA: P(I;)>P(叫I;)i,J=1,2,…,,z,j#i(7) 由贝叶斯公式可得: l;)=堕(8) 当P(OAi)和P(;)都不变时,判定准则由后验概率准则 变为似然准则: P(;IOAf)>P(;I)i,J=1,2,…,,z,j#i(9) 设似然函数为高斯分布,可以算出其均值和方差,再设 各基站是独立的,则总位置参数为m个基站似然函数的乘 积: P(;I(sO)=P(SlIOOi)×P(S2I(sO)×…×P(I(sO)(10) 最后以后验概率为权重,可以估算出比较精确的位置估值: L (37,)=(P(ooiI?)?(,Y,oi ))(11) 式中(,)是第(sO个位置的坐标. 3.5神经网法 这是非线性输入一输出映射最有效的方法.整个神经 网络由一系列感知单元组成的输入层,一个或多个隐蔽的计 算单元以及一个输出层组成.它采用指导学习算法,信号在 层间前向传递,第m层的第i个单元的输出为: J, '6n .一 - 1 ai(m)=ooo(m)oj(m一1)+Oi(m)(12) Of(m):,((m))(13) 啦(m)和o(m)是第m隐蔽层中第i单元的激活与输出(所 谓"激活"是指第(m一1)层的单元的输出与偏置条件的加权 86山西电子技术2007年 和).()是连结第(—1)层第J单元的输出到第层 第i单元输入的加权值.厂(?)是平滑非线性函数,通常是s 型函数: 1 f():_『?(14)上十e 或是双曲正切函数: ,1一一T f():tanh(告)=(15)厶上1_ 4实验及其结果 文献_3J中进行的实验发现q接近l时误差最小.一般 地,KNN/KWNN法比NN法要好,但RP间距比较大时NN 法比某些较复杂的算法要好;KNN/KWNN法当K取3或4 时效果最好.基本上RP增加时定位精度会改善,不过RP 密度很大时,精度上升的速率会下降. 利用空间相关的方法也能改善定位精度.用WDI法 时,若RP数量少于门限值,性能比原始数据库要好;但RP 数量大于66以后还不如原始数据库.这说明WDI法不能 充分利用已知数据.kriging法则几乎在所有情况下都能达 到最佳效果. 最后的结论是:1)k~ging法可以有效地利用RSS的信 息来生成高质量的数据库,即使只有少数RP可用,也能达 到可以接受的效果;2)RP达到一定密度时,kriging法的精 度无法再提高.反过来说,采用kriging法就不必测量大量 的RP来获得较好的性能,这意味着训练阶段可以明显缩 短,即使应用区域改变,也能很快生成新的数据库. 文献_4J对下面五个方面的性能作了分析比较: 1)精度 用平均距离误差作为性能标尺,结果表明KNN法最 好,约为lm,在抽样位置多测几次或改变K值只能增加一 点点精度.概率法一般,约1.1m,l,6m,增加每点测值数 时精度有所改善,因为高斯分布的均值和方差更精确了.神 经网法最差,约l,3m,2.8m,每点测值数为40时效果最 好,增加隐蔽层元数目只能稍微改善精度. 2)误差分布 分析累积概率函数的结果是:KNN法仍是最好的,80% 的误差小于lm;概率法80%的误差小于2m;神经网法80% 的误差在2m--2.5m之间,其大小取决于隐蔽层元的数目. 3)算法复杂度 表1三种算法的计算时间 定位算法在线计算时问 概率法2秒 KNN法(每点测100次)10秒 KNN法(每点测10次)1秒 神经网法0.25秒 因为移动设备的CPU功率和电池电量有限,所以以在 线计算时间为比较标准.如表l所示,每点测100次时, KNN法耗时最长,神经网法最短.值得注意的是,KNN法 的计算时间强烈依赖每点的测值数目,而其它两种方法不是 这样.若将每点测值数目减少到10,KNN法的计算时间就 只有约1秒,而且精度也还可以接受. 4)健壮性 好的算法应当可以应付下列两种意外情况:一是某些采 样值从未出现过;二是某些基站突然失效.对于第一种情 况,概率法工作正常,因为高斯分布是连续的;KNN法可以 用任意采样值进行计算,这不算什么问题;神经网有自我调 整的能力,也可以应付.对于第二种情况,设第U个基站失 效,它的RSS是Su,对于概率法,只要简单的令P(SJ)= 1,则对于所有候选位置来说,式(10)不受影响;对于KNN 法来说没有影响;对于神经网法,即使给Su分配一个比其它 值小得多的值,算法仍然工作正常,但是在选取典型值时要 小心. 5)系统扩展性 一 个基站的覆盖范围有限,大的区域可能需要许多基 站,当需要定位的区域扩大时,算法也应该可以使用原来的 数据.设共有M个基站,在线时可以收到m个基站的信号. 对概率法,若某个位置不在这m个基站的覆盖范围之 内,则令后验概率P(fS)=0,即认为移动台不会去位置 ~Oi;对于KNN法,只选用包括这m个基站数据的数据子集; 对于神经网法,由于需要固定的基站来进行测试和训练,只 能将大区域划分为若干个小区,每个小区由一组基站覆盖. 在每个小区内和训练一个神经网络,定位时先判断移动 台属于哪个小区,再由该小区的神经网络来完成定位. 比较的结论是:KNN法的精度和误差分布最好,在复杂 度降低到一定程度时精度仍然较好,而且无需或只需很少改 动就能解决在系统健壮性和扩展性方面的问题. 5结束语 有效的室内无线定位方法能够提供具有吸引力的服务, 基于TOA/TIX)A和AOA的技术由于各种原因并不适合在 室内环境下进行定位,而基于RSS的位置指纹(LF)技术能 够适应复杂的室内环境.本文介绍了一些建立数据库的方 法和定位算法,但是该技术还有很多问题尚未解决,比如在 给定精度的情况下怎样确定网格大小和参考节点的数目,怎 样组织数据库以缩小存储空间和减少搜索时间,系统性能与 建筑物结构如何关联,如何对系统建模以及如何设计,配置 系统等等. 参考文献 [jjPrasithsangareeP.,KrishnamurthyP.,ChrysanthisP.. OnIndoorPositionLtmationwithWirelessLS.Per— sonal,IndoorandMobileRadioCommunications,2002. The13thIEEEInternationalSymposiumonVolume2, l5—18Page(S):720—724. [2]KwonJ.,DundarB.,VaraiyaP..HybridAlgorithmfor IndoorPositioningUsingWirelessL.VehicularTech— nologyConference(VTC2004一Fal1),2004IEEE60th Volume7,26—29,Page(s):4625—4629. [3]LiB.,WangY.,ImeH.K.,eta1.MethodforYielding aDatabaseofLocationFingerprintsinWLAN.Commu— 第5期李昊:位置指纹定位技术 [4] [5] nications,IEEProceedings,Oct.2005,Volume152, Issue5,7Page(s):580—586. Tsung-NanLin,Po-ChiangLin.PerformanceCompari— sonofIndoorPositioningTechniquesBasedonLocation FingerprintinginWirelessNetworks,WirelessNet— works,CommunicationsandMobileComputing,2005 Internationa1ConferenceonVolume2,13—16Page(s): 1569—1574. KaemarungsiK.,KrishnamurthyP..ModelingofIn— doorPositioningSysu~sBasedonLocationFingerprint— ing.INF~_A)M2004.Twenty—thirdannua1JointCon— ferenceoftheIEEEComputerandCommunicationsSoci— etiesonVolLime2,7—11Page(s):1012—1022. [6]KaemarungsiK..EfficientDesignofIndoorPositioning SystemsBasedonLocationFingerprinting,WirelessNet— works,CommunicationsandMobileComputing,2005 InternationalConferenceonVolume1,13—16Page(s): 】81—186. IndoorPositionTechniquesBasedonLocationFingerprint LiI-Iao (CollegeofInformationandCommunication,GulinUniversityofElectronicTechnology,G uilinGuangxi541004,China) Abstract:ForindoortxJsitioningwithwirelessnetworks,thetechnologyCODbeusedarethet imeofarrival(TOA),thetimedif- ferenceofarrival(TIX)A),theangleofarrival(AOA),andthereceivedsignalstrength(RSS)s chemes.Comparedwithotherpod— tionlocationtechniques,locationfingerprint(LF)technique,whichbasedonRSS,ismoresui tableforcomplicatedindoorenviron— ments.TheaimofthispaperistointroducetheresearchprogressofLFtechnique. Keywords~indoor;position;locationfingerprint (上接第82页) 响.对目前在DSP中使用的这种蝶型译码器和MATLAB 库函数所提供的译码器进行比较,测试帧数为450,打孔速 率为1/3,仿真结果如图4. ViterbiPerformance ? 图4DSP译码器与MATLAB库函数的比较 从仿真图4中,我们可以看到:这种蝶型运算译码器的 性能与MATLAB库函数的译码性能基本一致.由于信道环 境考虑比较简单,所以当信噪比SNR到达ldB以上时,误码 率可以降低到10以下.由此可见,这种蝶型运算方法可 以运用并简化DSP编程. 4结束语 本文主要介绍了TD-SCDMA系统中一种方便DSP编 程实现的Viterbi蝶型译算法,并且把它和MATLAB库函数 进行了仿真比较,证明了它的性能能够满足实际情况的需 要,为DSP的Viterbi译码编程实现提供了方便.TD-SCD— MA技术能为人们提供更好的服务,满足未来个人通信的发 展要求,是我国通信史上的一座里程碑.Viterbi译码只是 TIMSCDMA系统中很小的一个模块.为了让TD-SCDMA 更快更好的发展,还有很多模块等待开发和优化. 参考文献 [1]李小文,李贵勇.第三代移动通信系统信令及实现 [M].北京:人民邮电出版社,2003—1. [2]张宗橙.纠错编码原理和应用[M].北京:电子工业出 版社.2003—4. [3]3GPP"IS25.222:Multiplexingandchannelcoding (TDD).[EB/OL].[2002—12]. [4]ErLiu.ConvolutionalCoding&ViterbiAlgorithm.IEEE S一72.333PostgraduateSeminaronRadioCommunica— tions,2004,11—16. [5]HenryHendrix.ViterbiDecodingTechniquesinthe TMS320C54xFamily.SPRA071.June1996. RealizationandAnalyzeofPerformanceonViterbiButterflyDecoderAlgorithm XuLing?yanLiDing-zhi (CQUPT,3GInstitute,,ChongqingChongyouInformationTechnologyCo.Ltd.,Chongqing400065,China) Abstract:TheapplicationofViterbibutterflydecoderalgorithmofc~nvolutioncoderinTD-SCDMAsystemisstudiedinthispa— per,andisoomparedwiththefunctionofViterbidecoderinMATLbytheresultofsimulation.Basingontheresultofsimulation. itanalyzestheperformanceofbutterflydecoderalgorithmandprovesitsfeasibility. Keywords:TD.SCDMA;c~nvolutioncode;Viterbidecoder;butterflyalgorithm