摘要:随着社会和技术发展的需要,无线定位问题,无论室外定位还是室内定位,都越来越受到人们的重视,GPS定位系统在室外具有良好的性能,但由于建筑物遮挡,GPS不能进行室内定位,而且定位成本过高。射频识别 (Radio Frequency Identification, RFID)应用于室内定位和小范围内低成本定位,表现出良好性能。RFID和其他技术相结合,例如:图论、树、模糊数学、概率论等,产生了很多相关的定位算法,该文主要论述了RFID定位问题及其与其他相关的技术结合形成的各种算法,并结合RSS与TDOA定位思想,提出一种新的定位思想,利用多个接入点接收到的RSS信号差值对目标物体进行定位,并讨论了WIFI网络和Ad-hoc等网络中的定位问题。
关键词:无线网络;射频识别;无线网络定位;接受信号强度;图论;树;概率论;模糊数学;接收信号强度差
中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)
19-5211-04
Indoor Location Technology Wireless Network
YUE Ming1, ZHANG Guo-ying2
(1.Information Engineering College, Shanghai Maritime University, Shanghai 200135, China; 2.Vehicle and Power Engineering Institute, Henan University of Science&Technology,Luoyang 471003, China)
Abstract: With the social and technological development, wireless positioning, whether outdoor or indoor location positioning, are more and more has been paid attention, GPS positioning system with good performance in outdoor, but because the building block, GPS positioning can not be positioning indoors and positioning high cost. Radio Frequency Identification (RFID) applying to indoor and small-scale, low-cost location, makes good performance. RFID combined with other technologies, for example: graph theory, trees, fuzzy mathematics, probability theory, etc., produces many relavent positioning location algorithm, this paper discusses the RFID positioning and integrating with other related to technologies forming of the various algorithms and furthermore discuss the location in WIFI network and Ad-hoc network.
Key words: wireless networks; Radio Frequency Identification (RFID); wireless network location; Received Signal Strength(RSS); graph theory; trees; probability theory; fuzzy mathematics; Received Difference of Signal Strength(RDSS)
无线网络逐步进入咖啡馆、大学校园、机场,由于许多应用都需要知道人或物体的位置,人们对定位问题做了很多的研究,已经相继建立了各种定位服务体系。位置估计即定位,通常也涉及移动物体在物理空间位置问题。虽然位置估计是研究热点,很多解决方法由于成本、复杂性、准确性或实现的可行性而难以应用到实际中。无论室内定位还是室外定位,在技术方面都面临严重的挑战。
使用室内定位系统(Indoor Positioning Systems, IPS)来估计无线设备(例如:笔记本电脑、手持设备等)的位置。典型的应用属性包括从接入点收到的接收信号强度(Received Signal Strength, RSS),信号到达的角度(Angle of Arrival, AOA), 到达时间(Time of Arrival, TOA),到达时间差(Time Difference of Arrival, TDOA)。所有这些属性中,RSS是目前唯一价格合理的硬件可以测量的属性[2]。在实验室环境下,RSS信号的衰减与距离的对数呈线性关系,在二维空间,利用3个接入点的RSS信号进行三角测量可以确定一个标签的位置。在实际中,建筑物的物理特性例如:墙、电梯、家具以及人们的活动都会给RSS信号带来影响。
距离是确定位置的根本,因此必须选择适当的测量距离方法。一般有两种方法,传输时间 (Time of Flight, TOF)和信号衰减(Signal Attenuation)。
传输时间为无线电波从A点到B点传输使用的时间。无线电波以光速进行传播,据此我们可以通过测量传输时间,很容易地计算出两点之间的距离。由于时钟频率的有限性,数字电子测量的时间是离散的单位时间。由于光的传播速度很高,为了得到准确的测量距离,需要高分辨率的时钟测量时间。无线电波的反射可能引起问题,现在人们还不能分辨直接传播过来的无线电波和反射回来的无线电波的差异。但是,通过多种测量方法,尽可能消除这种问题或将这种问题的影响降至最低应。
在一定距离内,信号强度与距离成反比,并且信号衰减与距离的对数成反比。路径损耗是由于传输导致信号的强度减弱,其中的一部分损耗就是由于障碍物和其他环境因素造成的。另一部分是自由空间路径损耗,就是空间损耗,而不是障碍或其它干扰因素。
无线网络中位置估测技术大致可分为用于建模的方法和监督学习方法。对于建模方法,多数技术覆盖全部区域并收集来自所有可见的一个或多个接入点信号强度的样本采样点。每个点映射到一个信号强度矢量或信号强度的概率分布。这种技术在数据收集方面需要大量的工作。另外,它使用参数模型,计算与建筑物有关的信号传播物理衰减详细情况来获取相关区域内长期变化的详细地图。
监督学习方法,训练阶段数据包括信号强度向量,每个向量代表一个已知位置。向量维数等于接入点的数量。其相应的位置可能是一维、二维和三维。收集位置信息劳动量非常大,需要测量相对于参考物体(例如:墙体)的物理距离。在模型建立阶段,建立了信号强度向量到物理位置的预测模型。
收集大量的训练数据和必要的物理位置测量需要巨额的前期成本和部署工作。而且,即使在普通的办公室环境下,改变环境、建筑物和室内情况都会影响到信号传播,需要重新采集数据以维持无线电测量的准确性。因此,最大限度地减少训练观察次数,充分配置一个特定的网络,应该尽量减少对墙体、地板等的依赖。
1 通常的无线定位系统
全球定位系统(GPS)是美国政府的卫星导航系统,该系统24颗卫星组成,它们位于距地表20 200km的上空, 均匀分布在6个轨道面上,每一个卫星周期是12小时。因此,从地球上的任何一点可以看见8-12颗卫星。 每颗卫星广播扩频信号在1575.42 MHz和1227.6MHz。信号包含两个部分:时间代码和导航信息。GPS导航系统的基本原理是测量出已知位置的卫星到用户接收机之间的距离,然后综合多颗卫星的数据就可知道接收机的具体位置。
GPS和无线电技术是有效的定位技术。虽然GPS是广泛的定位技术,但由于成本、功率要求以及不能在某些特定环境工作,例如室内、地下室和城市峡谷地带,现今市场上可以运用GPS定位的设备还是有限的。
由微软开发的RADAR系统利用无线电频率的定位系统。它通过测量多个基站的信号强度,这些信号强度与信号强度数据库相比,以确定目标物体距离,然后计算的目标物体的位置。通过记录和处理多个基站的信号强度,RADAR系统得以运行,在相关区域,这些基站信号重叠。这有两个优点:只需要有三,四个基站,可以安放很容易地基础设施,无线局域网WLAN可以非常容易地设置。然而,信号强度很容易受环境干扰。
无线射频识别(Radio Frequency Identification, RFID)技术利用无线射频信号自动识别目标物体或者对目标无图进行定位,通常主要由阅读器、电子标签和天线组成,以无线收发器为标签(Tag)来标志目标物体,标签上携带关于这个对象的数据信息。标签无线电收发器通过无线电波将这些数据发射到阅读器(Reader)。阅读器对这些数据进行收集,并通过计算机处理它们。射频识别技术的特点:不受空间限制,可快速进行物体追踪和数据交换,可实现批量读取和远程读取。近年来,电子产品码 (Electronic Product Code, EPC)和物联网(Internet of Thing)不断宣传,加之沃尔玛、美国国防部等对RFID的应用,RFID已经成为科技界的热点之一,被逐渐应用于物流仓储、商品销售、工业制造、资产管理、交通运输、动物识别、军事航空和防卫防盗等各个领域。
2 无线网络定位的相关理论
2.1 树理论(Tree)
聚类(Cluster)分析是由若干模式组成的,通常,模式是一个度量向量,或者是多维空间中的一个点。聚类分析以相似性为基础,在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。
网格空间被分成聚类,决策树用来查询每个聚类,联合聚类技术利用聚类的位置图和概率分布进行无线定位。聚类,代表离线阶段测量的一个接入点的位置以及对不同的访问点的信号强度的联合概率分布。实时定位阶段,从某些接入点集合接收到信号强度(RSS),这些接受信号强度(RSS)是用来确定群集搜索可能的位置,电子地图和贝叶斯理论用来搜索用户在集群中最可能的位置。利用接入点选择的接受信号强度(RSS)决定哪个簇是目标物体的可能位置。聚类和决策树的方法(CADET),在无线区域中无线接入点集合显示出良好性能,对噪声数据有很好的抗干扰性[2]。
此算法的性能主要取决于决策树的结构,建立一颗决策树可能只要对数据库进行几遍扫描之后就能完成,需要的计算资源较少;树的搜索过程是一个在结点内搜索和沿着某一条路径向下一层搜索交替进行的过程。因此,树的搜索时间与树的阶数和树的高度有关。搜索成功所需要的时间取决于关键码所在的树的层次,搜索不成功所需要的时间取决于树的高度,关键字节点的数目,取决于网格空间划分的粒度,必须加以权衡。
2.2 图论(Graph)
图形化模式是一种多元统计模型集合,并融合了环境无关性技术。图模型中所有变量都是离散的变量,图中的顶点对应的随机变量和边缘编码关系,边对应变量之间的关系。迄今为止,大多数图模型针对有向无环图,不含环的无向图,连锁图,图中可以含有有向边和无向边但不能有环。
文献[2]讨论了有向无环图(acyclic digraphs,ADGs),图中包含连续性随机变量。在ADGs中,所有的边都是有向边,用箭头表示。如果有向无环图中不含回路,则它是非循环的。图中每一个顶点代表一个随机变量,包含样本空间的位置信息。在一个有向无环图中,父节点的有向边指向其子节点,某节点直接指向的节点为其子女节点。如果有从节点v到节点w的有向边,则节点w是节点v的子节点。节点v的父节点(可能有多个父节点)是v的唯一影响因素,因此节点v相对于自己的非父节点是独立的。
由于图中所有的变量是离散的,Spiegelhalter和Lauritzen(1990)提出了贝叶斯分析并说明独立的Dirichlet先验分布,当数据到达后进行局部更新,形成后验分配。Heckerman, Geiger和Chickering(1995)提出了相应的完整的数据概似函数封闭形式表达式和后验概率模型。Madigan 和 York(1995年)描述了相应的贝叶斯模型平均程序。在Bayesian框架下,模型参数为随机变量,用图中顶点表示;顶点之间的联系用图中的边表示[2]。
2.3 模糊数学(Fuzzy Math)
人与计算机相比,一般来说,人脑具有处理模糊信息的能力,善于判断和处理模糊现象。各门学科,尤其是人文、社会学科及其它“软科学”的数学化、定量化趋向把模糊性的数学处理问题推向中心地位。尤其是,随着电子计算机、控制论、系统科学的迅速发展,要使计算机能像人脑那样对复杂事物具有识别能力,就必须研究和处理模糊性。
模糊数学又称FUZZY数学。“模糊”二字译自英文“FUZZY”一词。模糊数学是研究和处理模糊性现象的一种数学理论和方法。经典的集合论明确地规定:每一个集合都必须由确定的元素所构成,元素对集合的隶属关系必须是明确的。对模糊性的数学处理是以将经典的集合论扩展为模糊集合论为基础,对模糊现象的数学处理就是在这个基础上展开的。
接受信号强度(RSS)的不确定性可以抽象化为模糊集。所谓模糊概念是指这个概念具有不确定性,或者说它的外延是不清晰的,是模糊的。模糊理论是以模糊集合(fuzzy set)为基础,其基本精神是接受模糊性现象存在的事实,而以处理概念模糊不确定的事物为其研究目标,并将其严格量化成计算机可以处理的信息。离线阶段,建立无线电地图并用来模糊推理系统实验,有6个RSS信号值的模糊集:优秀,非常好,好,低,极低,和无。目标设备对定位区域的隶属度和位置,用RSS信号的模糊度来估计[1]。
2.4 概率论(Probabilistic)
由J.Pearl(1988)提出将概率论应用于不确定性推理,利用数学和计算机将不同的信息来源和各种不确定性因素结合,是人工智能、概率论、图论相结合的产物,已被广泛应用于预测、分类、因果分析等工程领域[2]。
无线定位技术一般分为确定性和概率性。确定性技术基于确定的范围或临近关系。确定范围的技术使用信道特性,例如接受信号强度(Received Signal Strength, RSS),计算目标物体和无线接入点(Access Point,AP)之间的距离。神经网络,特别是一个广义回归神经网络(General regression neural network, GRNN),已被用作匹配的地理定位系统的算法。该算法用于模式匹配算法,在训练阶段,神经网络的输入每一个测量RSS信号的接入点和接入点相应的无线电地图网格位置。有一个隐藏的GRNN的层和一个输出层,输出层两个神经元对应电子地图x、y坐标。实时定位阶段,GRNN网输入一组相应的RSS值,输出的是在栅格地图中估计的用户位置的X和Y坐标。在移动设备上运行位置估计算法需要一个无线电地图备份,运行在目标设备上的算法的优点是用户的隐私保护和改善可扩展性[1]。
在室内无线环境中,概率论方法具有不确定性,构建不同地点信号强度分布的无线电地图并使用的概率推理方法定位。概率定位,在相关的领域构建条件概率分布,来确定目标物体在一些特定时间点的位置的可能性。概率技术比确定性技术有很高的计算复杂性但同时也具备较高的精确性。这些技术通常由离线训练阶段和实时定位阶段组成。有些位置估测技术由相关领域可达位置的RSS值在离线阶段建立电子地图。室内区域由多个接入点覆盖,系统收集在不同地点接入点的信号强度,并构造一个基于直方图的电子图。然后,系统读取从任意位置收到的信号强度,从电子地图上估计与实际距离最接近的值,运用直方图进行位置估计更加细致的量化接收信号强度(RSS),不仅可以提高定位的精确性还可以无线信道中的噪音[6]。
但是,使用概率论方法进行位置估计有一些缺点。首先,这些方法都需要大量的训练模型准确标记的数据。在现实中,数据收集是一个耗时的过程。在室内的环境中收集和标记信号强度数据,前期测试花费很多时间。其次,由于非线性原因,建立物理空间和无线信号之间的联系是非常困难的。因此,即使有很多的收集数据,两个空间之间的直接映射可能并不能正常工作。第三,许多概率技术采用的分类的方法,把相关场所看做离散量来分类。然而,这种方法忽略了物理上的邻近地点属性相似的重要属性。
2.5 DV-hop算法
DV-hop算法不使用所有的距离信息,仅仅基于拓扑信息。DV - Hop基本上由两个阶段。在第一阶段,节点获得位置和到锚节点最小跳数。第二个是需要将校准波转换成距离。这种转换包括乘以平均跳数的距离。每当利用锚A1推断另一个锚A2在校准波的位置时,需要计算它们之间的距离,并把它们之间的距离划分成了多跳并计算出A1和A2之间的平均每跳的距离。当校准的时候,系统知道所有的锚,锚节点收到额外的锚信息,重复校准程序。但只有第一个锚节点转发校准信息,从而降低了网络中的信息量。
当通过多跳传播距离信息时,会产生累积误差。一些大型网络中,即使通过很少的锚节点(长距离)或小范围传播的硬件等,此累积误差变得尤为显著。这种定位方法依赖于网络拓扑结构,网络拓扑结构不规则时,定位精度严重下降。
3 无线定位网络
3.1 贝叶斯网络定位
贝叶斯网络又称信度网络,是一种概率网络,基于概率推理和有向图网络结构描述,贝叶斯公式是这个概率网络的基础,直观地表达变量联合概率分布及其条件独立性。所谓概率推理就是通过一些变量的信息来获取其他的概率信息的过程,基于概率推理的贝叶斯网络(Bayesian network)是为了解决不定性和不完整性问题而提出的,其关键是确定节点的联合概率分布,它对于解决复杂设备不确定性和关联性引起的问题有很大优势。不同贝叶斯网络模型的区别在于他们以不同的方式求解该概率分布[2]。
贝叶斯网络有定性部分(有向无环图表示网络拓扑结构)和定量部分(条件概率表)组成,用N=
贝叶斯网络基本推理任务是给定一个变量集合的观测值,计算出另一个被调查的变量集合的后验概率分布。贝叶斯网络推理主要利用贝叶斯网络对变量联合概率分布的表达式计算待求概率值的过程,是贝叶斯网络应用的基础。利用分层贝叶斯模型融合重要的先验信息和物理模型特性建立逼真的复杂定位模型,有两种定位方法:第一种,基于客户端模型,客户端测量接收到各个接入点发射来的信号强度,利用这些信息来确定自己的位置,这种定位方法,目标设备上需要有电子地图的拷贝,在目标设备上运行算法既保证了用户隐私的保密性又提高了可扩展性。但是对客户端要求较高,必须考虑到客户端对能量的需求;第二种基于框架的模型,系统利用所谓的嗅觉器监测客户端发出的信号强度,这种方法要事先设置探测器,并已知探测器的位置,将分层贝叶斯模型与先前的Wi-Fi信号特性相融合,在没有任何物理位置信息的情况下,进行精确定位[2]。
3.2 Wi-Fi网络定位
基于IEEE802.11b的Wi-Fi无线网络基础设施包括许多无线客户端和接入点,接入点作为无线网络和有线网桥梁,Wi-Fi是一种短程无线传输技术。能够访问Wi-Fi网络的地方被称为热点。Wi-Fi或802.11b在2.4Ghz频段工作,所支持的网速最高达11Mbps。标准Wi-Fi网络设置包括一个或多个接入点为用户终端,通过无线电波联网,常见的是无线路由器,在无线路由器的电波覆盖的有效范围都可以采用Wi-Fi连接方式进行联网。
Wi-Fi网络在不增加额外的硬件情况下,轻松应用于位置估计,可以被更多的人使用。在Wi-Fi网络环境中,通过分析接入点相对于无线网络设备信号强度或者信噪比来推断目标物体的位置[4]。客户端使用或“连接”到一个接入点,此接入点提供最强的RSS信号。客户端漫游,它定期检查信号强度,以确定最佳的接入点。通过信号测量,可以得到客户端的位置。
WIFI适配器使用扩频技术,遍及多个频率的信号。通过这种方法,一个频率的信号受到干扰不会影响整个无线电信号。信号本身传播方式复杂多变。当无线电波遇到障碍物,引起反射、吸收、衍射,会随机改变信号强度。其他各种因素,如噪音、物理干涉和不同信道之间的干扰也会影响信号。水的共振频率为2.4 GHz,人体70%是水,因此,人体也吸收无线电波信号和影响信号强度。这一切的后果是,接收信号强度随地点改变而改变并且在同一个地点随时间改变而改变。但是,位置空间相邻的信号形状相似,虽然存在各种外部变化,无线电信号形状在短距离内仍相似,而且,在小范围区域无线电信号强度随时间变化很小,信号衰减大致与距离的对数成反比[12]。
3.3 Ad-hoc网络定位
Ad Hoc网络是一种没有有线基础设施支持的移动网络,网络中的节点均由移动主机构成。移动IP网络中移动主机不具备路由功能,只是一个普通的通信终端,而Ad hoc网络中的主机同时也相当于路由器,具有路由功能,主要完成发现和维持到其他节点的路由。移动IP网络中移动主机从一个区移动到另一个区时并不改变网络拓扑结构,而Ad Hoc网络中移动主机的移动将会导致拓扑结构的改变。由于Ad-hoc网络是自组织网络,所以Ad-hoc网络中的定位均依赖于网络的拓扑结构进行定位,即Ad-hoc网络的定位不依赖于基于距离的定位技术。比如利用DV-hop算法进行无线定位。
分布式算法可大规模应用于Ad hoc传感器网络。这种算法应该是:自组织(即不依赖于周围环境的基础设施)、稳健(即可以允许的范围内节点失败和错误)和节省能源(即几乎不需要计算,特别是通信)。
Ad hoc网络的应用包括:交互式演讲、共享信息的会议、无线接入网、战场上信息中继及防汛抗洪等紧急通信需要。网络既可以作为一种独立的网络运行,也可以作为当前具有固定设施网络的一种补充形式,生存性较强的后备网络。也使用于没有有线通信的地方,如没有建立硬件通信设施或有线通信设施遭到破坏的地方,很适合灾难救助、偏远地区通信等应用[11]。
Ad Hoc网络最初应用于军事领域,起源于战场环境下分组无线网数据通信项目,该项目DARPA由资助,其后,又在1983年和1994年进行了抗毁可适应网络(Surveivable Adaptive Network, SURAN)和全球移动信息系统(Global Information System, GIoMo)项目的研究。由于无线通信和终端技术的不断发展,Ad Hoc网络在民用环境下也得到了发展,如需要在没有有线基础设施的地区进行临时通信时,可以很方便地通过搭建Ad Hoc网络实现。
通过对以上定位思想的简要概述,接下来,我们提出了一种改进的无线定位思想:
4 接收信号强度差(Received Difference of Signal Strength, RDSS)
在各种定位系统中,RSS是唯一价格合理的硬件可以测量的特性,还有很多研究用飞行时间来测量目标物体的位置,由于无线电波飞行速度很快,所以,需要严格的时间同步,TDOA的思想是:通过各个接收点接收到的无线电信号到达时间差来进行位置估计;和TDOA相类似,这里用多个接入点而不是一个接入点来估计目标物体的位置,RSS是利用接入点接收到的信号强度进行定位,但是无线电信号会受到各种干扰因素的影响,不同的时间,接收点接收的无线电信号也会不同,从而影响定位精度。我们提出一种算法的思想就是:利用多个接入点接收无线电信号,对于目标物体的定位算法,不是直接利用RSS值进行计算,而是通过数据库中事先建立的各个接入点的无线电信号差值与定位区域中各位置的对应关系即各个点的位置和信号强度差值关系的离线数据库,当然这个算法前期也需要也要做许多数据收集方面的工作;用多个接入点接收到的信号差值与数据库中事先建立起的对应关系来查找目标物体应该处于的位置。由于RSS信号受到其他因素干扰,如果一个接入点接收到的信号受到干扰,其他接入点也应该受到相应的干扰,但如果目标物体的位置没有发生变化,各个接入点的无线电信号干扰差值变化应该具有某种规律,应用这种规律定位,应该可以减少信号衰减对无线电定位的影响。这种方法不需要额外的硬件开销,各个接入点接收的还是RSS信号,RSS信号差值可以通过软件计算,数据库中也要做相应的改进,不是单单存储RSS信号与物理位置的对应关系而是存储多个接入点的RSS信号差值与物理空间各位置的对应关系。
5 结论
本文简要介绍了无线网络中定位问题的相关理论,简要介绍了GPS、微软的RARDAR系统和RFID系统,然后介绍了无线定位中应用的相关理论,接下来简要介绍了Bayesian网络、WIFI网络和Ad hoc网络定位。最后,结合RSS定位与TOOA定位,提出了一种改进的定位方法——接收信号强度差(RDSS)定位技术。
参考文献:
[1] Derr K,Manic M.Wireless Indoor Location Estimation Based on Neural Network RSS Signature Recognition[C].3rd IEEE Conference on Industrial Electronics and Applications,2008.
[2] Madigan D,Ju Wen-hua,Krishman P,et al.LOCATION ESTIMATION IN WIRELESS NETWORKS: A BAYESIAN APPROACH[M].Rutgers University and Avaya labs Research,2005.
[3] Mallinson H.An Overview of Location and Identity Technologies[D].Auto-ID Center, University of Cambrige,2005.
[4] Castro P,Chiu P,Kremenek T,et al.A Probabilistic Room Location Service for Wireless Networked Environments[D].UCLA,USA,FX Palo Alto Laboratory,USA.
[5] Gibson D,Adriaens J.CS/RADAR: Indoor Location Discovery and Tracking[D].University of Wisconsin-Madison.
[6] Youssef M A,Agrawala A,Shankar A U,et al.A Probabilistic Clustering-based Indoor Location Determination System, University of Maryland, March, 2002.
[7] Langendoen K,Reijers N.Distributed Location Algorithms[D].Delft University of Technology.
[8] Albowicz J,Chen A,Zhang Lixia.Recursive Position Estimation in Sensor Networks[D].UCLA Internet Research Laboratory.
[9] Youssef M A,Agrawala A,Shankar A U.WLAN Location Determination via Clustering and Probability Distributions[D].University of Maryland College Park, Maryland.
[10] Pan J J,Kwok J T,Yang Q,et al.Accurate and low-cost Location Estimation Using Kernels.Department of Computer Science[D].The Hong Kong University of Science and Technology,Hong Kong,Institute of Computer Technology, Chinese Academy of Science, China.
[11] Agre J,Akinyemi A,Ji L,et al.A Layered Architecture for Location-based Services in Wireless Ad Hoc Networks[D].Fujitsu Laboratory of America.
[12] Bartels S.WIFI Location System Investigation.Technical report[R].The University of Waikato,2005.