一种基于综合空间位置索引模型的移动位置计算方法
2013-02-28孔勇平张玉良钟致民杨广龙
孔勇平,张玉良,钟致民,杨广龙
(中国电信股份有限公司广州研究院 广州510630)
1 引言
随着移动互联网的快速发展,位置成为移动互联网业务的重要需求,是移动互联网的基础技术和核心概念。各类移动互联网应用大多已成为了广义上的基于位置的服务(location based service,LBS),应用通过使用位置信息,可为用户提供更好的体验、拓展新的业务模式等。如何获取或感知移动用户的位置,是移动互联网业务应用需要解决的首要问题之一。
目前,GPS(global positioning system,全球定位系统)芯片已经逐步成为智能移动终端的标准配置,用户可以通过GPS很方便地获取其所在的位置。虽然GPS服务免费、定位精度较高,但是GPS定位却存在以下两个重要缺陷,限制了其应用范围:一是GPS耗电量较大,一般手机持续打开GPS定位时,电池只能坚持使用几个小时;二是GPS对定位环境要求较高,在定位卫星被遮蔽的情况下不能定位,不具有环境的普适性。为了解决GPS定位的不足,后来逐步发展了基于无线网络的定位技术,即通过无线网络来确定移动用户的位置。移动网络定位技术的基本原理是通过移动用户接收的基站、Wi-Fi等信号的设备位置来计算移动用户的位置,其定位误差和基站或Wi-Fi设备的分布相关,一般在100~5 000 m。
在各类实际的应用环境中,位置的概念和需求是有区别的,位置不只是一个具有高精度的物理位置坐标,而与用户的行为、目标和所在环境紧密相关。例如:在高速公路、风景区等地方,在GPS定位受限时,由于基站或Wi-Fi的分布比较稀疏,而且往往只有1个服务基站信号覆盖,缺乏三角定位所需的足够多的基站信息,因此定位精度常常较低,只能确定用户所在的几百米到几公里的区域,用户体验不好。因此,本文提出了一种适合移动互联网应用的基于综合空间位置索引模型的移动位置计算方法。
2 位置索引
2.1 移动互联网应用对位置的需求
在不同的移动互联网应用中,用户对定位精度的需求是有差别的。例如在“周边搜”应用中,用户的需求是能够查找周边的商场、餐馆、酒店等POI(point of interesting,兴趣点)信息,对位置的精度要求不是特别高,一般误差在几百米之内即能够满足用户需求;而在“步行导航”这种应用中,则必须知道准确的起点、终点以及步行过程中的精确位置,以此来计算“步行”路径,实现精确导航,这种应用场景对位置的精度要求较高。定位服务的覆盖应该是连续的,即不论用户处于何种环境下(至少具备使用数据网络的条件),均可使用相应的服务。通过识别用户所处的不同场景,并以合理的代价提供满足应用精度要求的位置信息具有现实的意义。
移动互联网应用在定位(非GPS定位)时,主要依赖周边的基站、Wi-Fi等无线信号,但是由于受周边环境的影响,无线信号在传输过程中会发生折射、反射、多路径传输现象,使得这些无线信号具有很大的随机性,导致定位结果有较大的误差。一般情况下,在基站和Wi-Fi信号覆盖的交叠区域会发生严重的小区域信号涨落现象,移动终端接收到的基站或Wi-Fi信号会频繁切换,导致终端接收的无线信号处在一个动态变化过程中,体现在移动互联网应用中是出现位置的“跳跃”。例如当用户在连续定位过程中,即使用户位置还未发生较大的变化,但是受无线参数随机性变化的影响,也将导致定位结果相差较大,出现定位结果随机“跳跃”的现象。因此,需要寻找一种相对更合理稳定的定位方法,使定位结果尽可能趋于稳定,避免“跳跃”。
基于以上两种情况,可以通过对一个“小区域”位置建立多种位置索引描述的方法,计算位置信息。位置索引既能够满足不同应用对位置精度的需求,又能够保证在部分参数发生随机变化的情况下,通过参数之间的相关性,计算出比较准确的结果,避免出现较大的跳跃。
2.2 移动互联网应用中位置的定义
狭义的位置(location)指的是地理上的一个物理坐标或区域,一般采用经纬度坐标(longitude,latitude)来表示。在移动互联网中,基于无线网络的定位方法是通过基站、Wi-Fi等无线信号运算获得位置信息的。由于基站、Wi-Fi等无线信号具有一定的覆盖区域,而并不是一个准确的点位置,因此定位结果往往采用基站或Wi-Fi的中心点坐标和信号覆盖半径来表示其位置,本文采用P(X,Y,R)来表示。其中,X表示经度,Y表示纬度,R表示信号覆盖半径(即误差范围,单位是m)。
由于用户的位置与其生活环境是紧密相关的,因此用户的生活环境对用户的位置具有很大的约束作用。例如,在城市内,道路、商业中心、写字楼、广场和生活小区等一般是人们的活动区域,人们一般不会出现在河道、绿地和湖面等区域;在城市外,旅游景点、道路和乡村居民点等一般是人们的活动区域,而农田和山坡等一般不是人们的主要活动区域(在田地中劳作一般不是移动互联网应用的使用场景)。基站在市区的覆盖范围在几百米到1 000 m,Wi-Fi的覆盖范围在300 m以内。单纯以基站和Wi-Fi的位置来确定用户位置,很难满足用户对位置合理性的要求,因此需要结合用户活动的路网和周边POI等信息进一步提高用户位置的合理性和精准度。
基于以上对移动互联网应用位置的定义分析,本文采用基站、Wi-Fi、道路和POI作为索引确定一个位置,并采用一个四元组来表示:
其中,C表示移动通信基 站,W表示Wi-Fi热点,R表示道路,P表示POI。
2.3 综合位置索引
本文中采用四元组
C:基站编号(CID)、基站坐标(X,Y)、覆盖半径(R);
W:Wi-Fi地址(MAC)、覆盖半径(R);
R:道路编号(RID)、名称、城市区位码、宽度、等级、道路坐标串(X1,Y1;X2,Y2;…;Xn,Yn);
P:POI编号(PID)、名称、城市区位码、类型、坐标(X,Y)。
在以上4类位置索引数据对象中,每一类数据对象都有确定的地理坐标,能够确定一个具体的地理位置,但是,其在定位技术实现中的意义和使用是完全不同的。基站信号和Wi-Fi信号是移动终端能够获得的无线参数,既是移动终端与环境交互的媒介,也是计算移动终端理论位置的基础信息;道路和POI是对环境的描述,能够更合理地推算出用户的实际位置。
综上所述,基站、Wi-Fi、道路、POI是对一个小区域位置的综合性描述,可以通过它们的相对关系来确定移动用户具体的位置。因此,可根据基站、Wi-Fi、道路、POI构成的位置综合空间索引四元组来对定位基础数据进行构造和组织。
图1 位置合理性示意
3 位置计算
3.1 位置计算策略
在移动互联网应用中,在难以获得准确的高精度位置信息的情况下,获取更合理的位置信息显得颇为重要(误差450 m比误差500 m并不一定更有优势)。所谓合理性,是指定位结果与用户所在的生活环境具有相容性,能与人的正常生活环境相关联。如图1所示,A点是用户的真实位置,B点是通过普通的定位算法计算的结果(公园内人迹罕至的小树林),C点是通过综合空间位置索引的移动位置计算方法计算的结果。从地图上可以看出,B点距离用户真实位置A点更近,从物理上来说B点的精度比C点的精度更高,但是从用户的角度来看,C点与用户在道路上的感知体验是一致的,位置基本感觉不到偏差,而B点会明显感觉到偏差,因此C点比B点更趋合理。
因此,本文提出的基于综合空间位置索引的移动位置计算方法中,采用以下两个位置计算策略。
·由粗到细逐步求精策略。在位置空间索引四元组中,基站的覆盖范围远远大于Wi-Fi的覆盖范围,覆盖半径可看作定位结果的误差,因而基站定位的误差远大于Wi-Fi定位误差,因此用户位置确定顺序采用基站到Wi-Fi的优先顺序。
·位置计算合理性优先策略。在用户周边往往同时存在多条道路和多个POI,不同道路具有不同的等级、宽度等,不同的POI也同样具有不同的类型、大小等,这些属性反应了位置合理性的大小,通过不同权重的设置可反映位置的合理性。
图2为位置计算策略示意。
3.2 索引权重设置
权重设置主要是设置道路和POI的权重。一般情况下,道路和POI权重更能反映用户位置的合理性。本方法的权重包含静态权重和动态权重两部分。道路和POI具有一些静态属性,如道路的等级、宽度、POI的类型、大小等,这些静态属性都会影响用户位置的合理性,因此把这些属性设置的权重称为静态权重;另外,由于基站、Wi-Fi计算出来的用户位置(X,Y)与附近各道路和POI之间具有不同的距离,在不同的时间,人们在道路和POI内的概率会有所不同。因此,把这些距离、时间等具有随机性的因素称为动态权重。
·静态权重:道路和POI可以按类型和等级两个属性设置权重。
·动态权重:道路和POI按照距离设置权重,采用二次函数计算距离的权重,如式(2)所示。本文暂不考虑时间权重。
图2 位置计算策略示意
其中,a、c是调节因子,d为距离。
3.3 定位算法及流程设计
基于无线网络的定位技术,采用两步计算方法:通过基站和Wi-Fi计算出用户位置坐标,通过这个坐标与周边的道路和POI进行比较,计算出最终用户的合理位置。
图3为定位算法流程示意。
(1)坐标计算
如果扫描到Wi-Fi信号参数,则使用Wi-Fi算法计算用户位置坐标,多个Wi-Fi参数用户位置坐标计算式如式(3)和式(4)所示,否则使用基站计算用户位置坐标。
图3 定位算法流程示意
其中,Wix为Wi-Fi的经度坐标,W1y为Wi-Fi的纬度坐标。
(2)位置计算
通过步骤(1)计算出的坐标(X,Y)检索周边500 m(可调整)道路和POI数据,对每一个道路和POI数据根据权重设置计算其得分,得分最高者为最终用户位置,道路是用户坐标(X,Y)到道路的垂直位置,POI是POI坐标位置。
4 实验结果
文章的实验设计如下,采用配置了GPS模块的智能手机,在不同区域采集基站和Wi-Fi数据,并同时记录下当前位置的GPS坐标,数据记录格式:<基站ID,W1,W2,…,Wn,X,Y>。然后采用本文提出的定位模型和算法,使用收集的基站与Wi-Fi热点作为参数进行位置计算,最后计算定位结果与GPS坐标之间的距离,作为实际定位误差,并与没有路网、POI参与的单纯基站和Wi-Fi定位结果相比较。本次试验在不同区域共采集了测试数据10 000条,测试结果如图4所示,从图中可看出70%以上的定位结果误差小于100 m。
从测试结果可明显看出,采用本文的定位模型和算法,不只是定位结果的合理性增强,定位精度同样可明显提高。
5 结束语
本文提出了一种基于基站、Wi-Fi、道路和POI的综合空间位置索引的移动位置计算方法,在目前的定位技术中,首先提出了位置合理性概念,并给出了基于合理性设计的位置计算策略和方法。经实验表明,采用本文提出的定位方法得到了较好的定位结果。同时,本文对行为空间索引数据的基站、Wi-Fi、道路和POI等数据对象作了适当的简化,如基站和Wi-Fi的信号强度等;对道路和POI的权重设置同样采用的是经验模型。为了进一步提高定位的精确性和为用户提供更良好的体验,接下来将进一步研究可以采用机器学习等智能化大数据处理算法,给出更精确的模型。
图4 定位测试结果
1 Chen G L,Kotz D.A Survey of Context-Aware Mobile Computing Research.Dartmouth Computer Science Technical Report TR2000-38,2000
2 斯托林斯.无线通信与网络.何军等译.北京:清华大学出版社,2005
3 Jiang C,Steenkiste P.A hybrid location model with a computable location identifier for ubiquitous computing.UbiComp 2002:Ubiquitous Computing,Goteborg,Sweden,2002
4 Becker C,Dürr F.On location models for ubiquitous computing.Personal and Ubiquitous Computing,2005(1)
5 Smailagic A,Small J,Siewiorek D P.Determining User Location for Context Aware Computing Through the Use of a Wireless LAN Infrastructure.Institute for Complex Engineered,2000
6 Hightower J,Borriello G.A survey and taxonomy of location systems for ubiquitous computing.IEEE Computer,2001(18)