IP定位技术,简而言之,是通过设备的IP地址来确定其地理位置.近年来,基于地理位置的网络应用层出不穷,主要包括定向广告(targeted advertisement)、社交网络、网络安全、性能优化等^{[ 1, 2, 3, 4 ]}.许多研究机构和学者围绕IP定位技术从定位精度、隐私保护以及应用等不同角度展开了研究.著名的Internet测量组织CAIDA在美国国土安全部的资助下,对各种IP定位算法进行了分析^{[ 5 ]}.IETF成立了专门的工作组来讨论Internet定位技术的标准、隐私保护等相关问题,并提出了相应的草案^{[ 6 ]}.国际互联网组织W3C更是在下一代网络标准中将定位服务作为一个标准接口写入了HTML5规范^{[ 7 ]}.

IP定位的基本原理是,利用IP设备的名字、注册信息或时延信息等来估计其地理位置.定位算法设计的基本原则是:在保证定位精度的前提下,尽量减少测量开销,同时兼具良好的扩展性,并能保护用户隐私.最初的定位算法通过向DNS服务器查询或者挖掘隐含在主机名中的信息来推测IP设备的地理位置^{[ 8, 9, 10 ]}.之后,一些定位算法根据时延与地理距离之间的线性关系来估测主机位置,并通过拓扑信息来减小定位误差^{[ 11, 12, 13 ]}.近年来,基于概率的定位算法重新成为一个研究热点,通过寻找时延与地理距离的分布规律来进行定位^{[ 14, 15, 16, 17 ]}.虽经不断改进,但这两类算法都不能精确地定位,因此,一些综合的定位算法使用了上述两类方法来进行交叉验证以提高精度^{[ 1,13 ]}.

IP定位算法可以按照是否需要客户端的支持、定位原理等不同标准进行分类,本文将其分为独立于客户端的定位算法和基于客户端的定位算法.这两类算法各有优劣:独立于客户端的定位算法主要借助推测、网络测量等方法推断目标主机位置;基于客户端的定位算法精度较高,但是往往要借助GPS、蜂窝基站、WiFi接入点等基础设施.如今,伴随着社交网络的流行,用户地理位置被公布出来,一方面促进了好友间的交流,另一方面也带来用户对于隐私泄露的担忧.此外,IPv6网络的大面积部署和位置标识/身份标识分离协议(locator/ID separation protocol,简称LISP)等新型协议的提出,也为IP定位技术的发展带来了新的机遇和挑战.

本文第1节对IP定位技术进行概述.第2节、第3节对典型的独立于客户端的定位算法和基于客户端的定位算法进行详细分析.第4节分析隐私保护技术以及网络新技术对定位的影响.第5节综合分析各种IP定位算法和面临的挑战.第6节总结全文.

1 IP定位概述 1.1 基本概念

简单地说,IP定位技术就是为确定IP设备地理位置所采用的技术.在IP定位系统或算法中,一般包括4个要素:定位服务器、测量节点、待定位节点和基础设施,如图 1所示.

· 定位服务器:通过协调测量节点对待定位节点进行定位,并收集、处理定位信息向最终用户提供定位服务;

· 测量点:在定位服务器的控制下,通过网络测量或信息查询来获得待定位节点的时延、路由、位置信息等,并提交给定位服务器;

· 待定位节点是具有IP地址的设备,包括计算机、手机、路由器等;

· 基础设施:泛指用于定位的协议和设备,如网络协议、服务接入点、GPS定位系统、蜂窝基站等.

IP定位的基本过程就是通过设备的IP地址测量获得其属性信息,在分析属性信息的基础上获得IP设备的地理位置.这个属性信息既可以是主机的名字、IP地址本身,也可以是IP设备与已知定位位置IP设备的时延以及连接关系等.

按照是否需要客户端的支持,IP定位技术可以分为独立于客户端的定位算法和基于客户端的定位算法.按照定位原理,可以分为基于推测的定位算法、基于时延的定位算法以及同时使用这两类技术综合定位算法这3类.基于推测的定位方法通过网络注册信息、主机名等信息来推测IP地址的地理信息;基于测量的定位系统或方法通过时延与地理之间线性关系来估测主机的位置,并通过拓扑信息来提高预测精度;综合的定位方法则使用上述两种方法来综合提高预测精度.为了描述方便,本文主要按照是否需要客户端的支持对现有定位算法进行分类,对于算法较多的非基于客户端的定位算法,进一步按照定位原理再分类讨论.

1.2 IP定位技术的应用

目前,IP定位技术的应用主要分为4类:网络性能优化、网络安全、社交网络和定向广告.

基于IP定位的网络性能优化主要是通过定位服务为用户选择通信距离最短的链路,从而达到减小网络开销、提升网络性能的目的.如在P2P网络中,通过为对等节点选择地理位置近的节点通信,以减少跨域流量提高下载速度^{[ 18 ]}.Cheng等人利用地理位置信息来控制地理距离短的移动设备进行通信,从而减少数据传输中能量的损失^{[ 19 ]}.

基于IP定位的网络完全应用主要是通过用户的位置信息来对其身份进行验证,可以应用于入侵检测和用户访问控制.在入侵检测中,通过将用户的IP地址和地理位置相关联,在一定程度上减少IP哄骗攻击.在用户接入控制中,则可以根据分析用户身份的真实性并依据访问控制策略,响应或拒绝用户的通信请求^{[ 20 ]}.

基于IP定位的社交网络主要是通过将社交网络成员的位置或者运动轨迹与他们的活动、兴趣进行关联,向用户进行好友推荐或提供特色服务.如,Facebook就可以为用户上传的图片自动提供位置信息^{[ 21 ]};而QQ、飞信、微信等通信工具则会依据地理位置推荐好友.

定向广告是指网络服务商利用网络追踪技术(如Cookies)搜集整理用户信息,按年龄、性别、职业、爱好、收入、地域分类储存用户的IP地址,然后向不同类型的用户发送内容不同的广告.由于这类广告针对性强、更加有效,许多浏览器和内容提供商都提供这项服务,如FireFox、Facebook、亚马逊、腾讯等.

在上述4类应用中,前两类属于经典应用,已得到了较好的研究和应用.伴随着社交网络的不断发展和网络服务越来越重视用户的体验,后两者将得到继续发展.在这一过程中,网络服务提供者需要得到更加准确的用户位置信息,而用户在希望得到好的服务的同时尽可能地隐藏自己的真实身份和位置信息.这一矛盾将推动IP定位技术围绕定位准确性和隐私保护两个方面进行发展.

1.3 IP定位技术与其他定位技术的关系

定位技术是一个重要的研究领域,它广泛地应用于军事、通信、科研、交通等各个领域.目前,常见的定位技术主要有GPS卫星定位、蓝牙定位、WiFi网络定位、GPRS/CDMA移动通信技术定位、雷达定位技术、无线传感器定位等.这些定位技术的基本原理是:探测设备直接向待定位的目标发射电磁波,在客户端的协作或非协作下,通过测量与目标的时延来解算目标的位置信息.

相对于上述定位技术,IP定位技术的应用场景更为复杂.在Internet中,迂回路径和时延抖动普遍存在,使得测量点无法采用前面的定位方法直接进行定位,而必须考虑Internet的特点.IP定位技术不仅具有其独特性,同时它又是一种综合的定位技术,前述的定位技术可以作为IP定位技术的一部分或者辅助手段.

2 独立于客户端的定位算法

独立于客户端的定位算法根据其定位原理可以分为基于推测的定位算法、基于时延的定位算法以及综合定位算法这3类.

2.1 基于推测的定位算法

基于推测信息的定位算法一般通过查询Whois数据库等来获取该IP地址的主机名,所在街道或者通过IP地址段地理位置来推测该IP设备的位置,典型的算法有IP2LL^{[ 9 ]},NetGe^{[ 10 ]},GeoTrack^{[ 11 ]},VisualRoute^{[ 22 ]},Neotrace^{[ 23 ]},GTrace^{[ 24 ]},Quova^{[ 25 ]},MaxMind^{[ 26 ]},EdgeScape^{[ 27 ]},TraceWare^{[ 28 ]},Software77^{[ 29 ]},IPligence^{[ 30 ]},HostIP^{[ 31 ]},IPInfoDB^{[ 32 ]}等.这类算法大致可以分为3类:第1类是直接查询Whois数据库来推测主机位置信息;第2类是通过测量主机名并结合数据库信息来推断主机地理位置;第3类是通过网络结构和数据库信息来推断主机地理位置.

在上述3类定位算法中,第1类算法提出的最早也最为简单,代表算法包括IP2LL^{[ 9 ]}和NetGeo^{[ 10 ]}等.这类算法准确性差,主要是由以下两个方面造成的:首先,Whois数据库中的地址信息非常不准确或已经过时,同时,多个服务器对同一个IP地址块的地理位置记录可能不一致;其次,一个大的地址块可能会被分配给一个具有广泛地理位置分布的组织,而服务器只会为整个IP地址块记录一个地理位置.

基于主机名来推断地理位置的定位算法包括GeoTrack^{[ 11 ]},VisualRoute^{[ 22 ]},GTrace^{[ 24 ]},Neotrace^{[ 23 ]}等,以GeoTrack为例,Venkata等人认为,在主机名字中可能包含了不同粒度的地理位置信息.如,corerouter1. SanFrancisco.cw.net表明该主机位于San Francisco,www.state.ca.us表明主机位于美国的加利福尼亚州.因此,通过挖掘这些信息可以推断主机的位置.该算法共分为3步:首先,采用Traceroute工具确定测量主机与被测主机之间的网络路径,尽可能地测量出中间节点的DNS名字;然后,按照路径依次提取出中间节点的位置信息,从而推断到达被测节点的地理路径;最后,GeoTrack将路径上最靠近被测主机的可识别路由器的位置作为主机的位置.显然,该算法的精度主要取决于路由器DNS名字的定位精度以及目标主机与最后一跳路由器的距离.

GeoCluster^{[ 11 ]}是通过网络结构和数据库信息来推断主机地理位置的典型定位算法.在Internet中,地址划分和路由是按照层次结构组织的,因此,路由器中的IP前缀(address prefix,简称AP)信息可以作为拓扑簇划分依据.然而,一个大的ISP或组织可能覆盖很大一个区域,为了进行准确定位,需要进一步将大的IP簇划分为粒度更加适合的簇.为此,GeoCluster引入了一个阈值,如果位于同一个簇内的IP地址数目大于阈值,则成为一个簇;否则,将这个IP地址块平均划分成两块,依此不断迭代,从而将IP地址块划分为不可再分的IP地址簇集合.假设有一个IP地址簇为128.127.126.0/24网段,根据映射信息得知:有10个IP地址位于西雅图,而另一个IP地址位于波士顿,故可以推断整个簇的地理位置位于西雅图.在GeoCluster算法中,最为重要的是IP地址到地理位置的映射,而这些信息可以从Hotmail,bCentral,FooTV等网站的注册信息中获得.

Quova,MaxMind,EdgeScape,TraceWare,Software77,Ipligence,HostIP,IPInfoDB等基于数据库的商业定位系统出于商业利益的需要,没有公开其技术细节.这些系统综合各种方法来收集、获得用户信息,甚至通过购买商业网站中的注册信息、ISP网络拓扑结构和路由策略来获得用户的位置信息,因而具有相对较高的定位精度.

总体来说,基于推测的定位方法不需要大量测量,具有计算开销较小、定位速度快的特点,但是对于一个大型的ISP或者地域分散的组织,这种方法的定位精度不高.因此,基于推测的定位算法适用于定位精度要求不高的网络应用.

2.2 基于时延的定位算法

基于时延的定位方法通过测量目标主机到测量点的时延来估测主机位置,为了提高定位精度,往往结合网络拓扑信息来进行定位,典型的定位算法和系统有Geoping^{[ 11 ]},Shortest Ping^{[ 3 ]},Constraint-based Geolocation (CBG)^{[ 12 ]},Topology-based Geolocation (TBG)^{[ 3 ]},NBIGA^{[ 14 ]},Posit^{[ 33 ]},Geo-RX^{[ 34 ]},Spotter^{[ 17 ]}等.与基于推测的定位算法相比,这类定位算法具有较为完善的数学基础,可分为基于空间理论的定位算法和基于概率估计的定位算法两类.

2.2.1 基于空间理论的定位算法

基于空间理论的定位算法利用时延与地理距离的线性映射关系来估计地理距离的远近.按照算法提出的时间顺序,依次分析Geoping,Shortest Ping,CBG,TBG,Geo-RX^{[ 34 ]}这5种算法的基本思想和原理.

Geoping算法的基本假设是:到同一组主机时延相近的主机,其地理位置也相近.该算法将所有网络节点划分为目标主机T={T₁,T₂,…,T_n}、测量点V={V₁,V₂,…,V_n}和基准节点L={L₁,L₂,…,L_n}这3类.

为确定目标主机的位置,所有的测量点首先向基准节点发起测量,获得由时延构成的一组时延向量= (d₁,d₂,…,d_n)作为指纹信息.在确定某台主机T_i的地理位置时,所有的测量点向目标主机发起主动测量,获得其时延向量,然后比较与的相似性,选择时延向量与最接近节点的地理坐标作为主机T_i的地理位置.

在匹配中,向量之间的相似度是通过N维时延空间中的欧氏距离来比较的:

(1)

图 2中给出了Geoping算法的一个实例,包括3个测量节点、2个基准节点和一个目标主机.通过比较可以看出:主机T₁与L₁十分接近,因此可以采用L₁的坐标近似作为主机T₁的坐标.

Shortest Ping算法的思想是:通过测量基准节点到被测节点的时延,用到被测主机时延最小的基准节点位置作为被测主机的地理位置.可以视为对Geoping算法的一种近似和简化,然而其预测精度和许多比它复杂的算法精度相差不大^{[ 3 ]}.Geoping与Shortest Ping两种算法的精度都受到基准节点数目及其位置的影响,基准节点距离被测节点越近,则其预测误差越小.Hu等人^{[ 35 ]}发现:只有当基准节点与被测节点距离较近时,才能获得较高的定位精度,因此提出了选择邻近节点对Shortest Ping和CBG算法进行改进.

与Geoping不同的是,CBG不用基准节点的地理位置来近似主机的位置,而是采用一种类似于三角定位的方法来确定被测主机的位置.CBG假设时延与地理距离之间存在一种线性关系,如公式(2)所示:

d_i=m_i×x+b_i (2)

其中,d_i代表基准节点L_i到被测节点的地理距离,x代表两种节点之间的时延,b_i代表基准节点的某种本地时延(如拥塞时延等).这样就可以概率地估计被测主机到基准节点的距离,当基准节点的数目大于3时,则可以形成一个交叠区域,从而确定被测主机的位置,如图 3所示.

从定位原理上看:Geoping是用基准节点位置信息来近似代替待定位节点的位置;而CBG算法则是由基准节点再发起测量,将待定位节点缩小到一个更小的范围内,其精度要高于Geoping算法.然而测量结果表明:在Internet中,时延与地理距离的线性关系并不明显.考虑到时延抖动的影响,要提高预测精度,需要进一步改进算法.

Ethan等人^{[ 3 ]}发现:基于基准节点的定位算法,其定位精度并不比简单的定位算法精度高出很多;而基准节点与待定位节点的远近,则对于定位精度影响较大.结合传感器网络定位的原理,他们提出了基于拓扑的定位算法(topology-based geolocation,简称TBG).该算法将测量的网络路径信息作为约束目标主机和中间节点位置的约束条件,然后确定待定位节点和中间节点所在的位置区间.

设待定位节点集为X=[x₁,x₂,…,x_m],基准节点集为L=[l₁,l₂,…,l_n],则所有待定位节点与基准节点的时延必须符合以下两个约束:

(1) 时延强约束

d(l_i,x_j)≤c_ij (3)

即,如果已知待定位节点x_j到基准节点l_i的往返时延,则两者d(l_i,x_j)必须小于光在光纤中经过往返时延所传输的距离c_ij,称其为时延强约束,将所有强约束条件表示为C_d.

(2) 链路时延弱约束

d(x_i,x_j)=h_ij+e_ij (4)

在TBG算法中,通过测量相邻两个节点间的时延来估测它们的距离h_ij,但是由于各种因素的影响,h_ij并不准确,将其与真实距离之间的误差表示为e_ij,则称为链路时延弱约束,所有的弱约束条件表示为C_l.

显然,e_ij越小,则表示定位精度越高.TBG定位算法将定位问题转化为一个带约束的非凸优化问题.TBG算法的优点是:① 充分利用了距离基准节点越近则定位越准确的优点;② 利用中间节点地理位置来检验到目标节点路径的正确性;③ 允许通过迭代达到全局的一致性.以Abilene和Sprint网络为例,TBG可以消除平均误差分别为40%和70%,其平均预测精度为22miles.然而,与其他基于时延的定位算法一样,该算法无法避免时延与地理距离非线性关系对定位精度的影响.

与上述三者不同的是,Geo-RX^{[ 9 ]}算法通过建立准确的时延模型来提高定位精度.它将时延分为传播时延D_pg、传输时延D_tr、排队时延D_q、处理时延D_pc以及应用层响应测量的时延D_g.同时,该模型还考虑到测量中正向路径H_fw与逆向路径H_bw的差异,如公式(5)所示:

(5)

最终,通过传播时延来确定主机的位置.为了提高预测精度,对全局还进行了优化.

这种算法虽然精度高于Geoping,但是计算复杂度较高.

2.2.2 基于概率估计的定位算法

基于概率估计的定位算法通过统计时延大小与地理距离的分布关系来进行定位.这种定位方法在网络状况稳定的情况下,可以不受时延与地理距离非线性关系的影响,典型的算法包括NBIGA^{[ 14 ]},Posit^{[ 31 ]},Spotter^{[ 17 ]}等.

Eriksso等人^{[ 14 ]}认为,CBG等算法的误差主要是由不同地区的测量密度差异而引起的.因此,他们提出了一种基于贝叶斯估计的定位算法(naive Bayes IP geolocation algorithm,简称NBIGA),通过使用更多的测量数据来降低由于测量数据不足以及不规则网络路径引起的误差,从而将IP定位转化为机器学习的分类问题.其基本思想是,将每个待定位的IP主机依据测量结果划分为不同的地理位置集合.NBIGA算法从基准节点向待定位节点发起测量,获得跳数和时延M=[m₁,m₂,…,m_n],而将所有节点划分的目标集合为C=[c₁,c₂,…,c_n],而定位则是将IP划分为其中的一类,如公式(6)所示:

(6)

假设各个测量点的测量结果是独立的,根据贝叶斯理论,可以将公式(6)表示为公式(7):

P(M|c)=P({m₁,m₂,…,m_n}|c)=P(m₁|c)×P(m₂|c)×…×P(m_n|c) (7)

概率P(m_i|c)则是通过一维核密度来进行估计的.由于测量的同时也获得了路径跳数和时延,因此两者通过加权平均来计算P(m_i|c).与待定位节点距离越近,则权值越大,将其代入可得公式(8),即定位分类器:

(8)

其中,,l_hop,l_popg_hop,g_lat分别表示路径跳数、城市人口以及时延的加权系数.由公式(8)则可以估计出待定位IP所在的地理位置.该算法计算复杂度较小,同时具有较高精度.实验结果表明,其精度略高于CBG算法.

Posit同样是对CBG算法的一种改进,它将所有节点分为3类:测量节点(M)、基准节点(N)和待定位节点(T),其中,测量节点和基准节点的地理坐标已知.首先,分别测量待定位节点与测量节点、基准节点之间的时延,通过训练获得时延与地理位置的分布函数;然后,在一个阈值l_lat下,选取较小的时延计算其L₁范数来作为距离;最后,使用最大似然估计来预测待定位节点的位置.

Laki等人^{[ 17 ]}通过测量发现:时延与距离之间存在一个统一的分布规律,而且这个分布规律与基准节点的位置无关,各个分布之间彼此独立.在此基础上,提出了Spotter算法.在Spotter算法中,假设时间与地理距离之间符合标准正态分布,如公式(9)所示:

(9)

其中,m(d),s(d)分别表示时延分布的均值和方差,可以由参数估计的方法获得.在多个节点的情况下,时延的分布就表示为独立正态分布的联合概率.由于正态分布的参数估计方法较为简单,因此Spotter算法的开销较小.Arif等人^{[ 36 ]}采用相同思路设计了一种定位算法,所不同的是,他们用最大似然估计法来推测主机的位置,取得了更高的定位精度.

基于概率模型的定位算法主要受到概率模型的影响,因此,用于学习样本数目的多少和代表性是影响定位精度的一个重要因素.如何选择具有普遍适应性的概率模型,并准确地估计模型参数,已成为近年来定位算法的一个研究方向.

2.3 综合定位算法

上述任何一种方法都不能单独地对主机进行准确定位,为此,一些研究人员提出了综合的定位方法,典型的有Octant^{[ 1 ]},TTG^{[ 13 ]},GeoWeight^{[ 34 ]}.这些定位算法同时运用上述2~3种算法对待定位主机进行定位,然后进行交互验证以确定主机位置.

Octant框架^{[ 1 ]}综合使用各种信息来对目标主机进行定位,它将所有的信息分为用正和负两类约束条件,以缩小预测区域从而提高定位精度.正约束条件是指通过主动测量来获得被测主机可能位于的区域,而负约束条件是指计算机不可能条件.它不将被测主机的位置定位于一个具体坐标,而将其可能的位置表示为一个贝赛尔曲线(Béziercurve)所决定的曲面.由于网络时延并不符合理想的时延传输模型,Octant引入了一个“height”维来表示最后一跳的接入时延.具体说,Octant分为如下3个步骤:

(1) 测量基准节点到目标节点往返时延;

(2) 归纳出强约束条件和弱约束条件,并进行排序;

(3) 使用强约束条件进行迭代,然后使用弱约束条件进行验证.

Arif MJ等人^{[ 34 ]}对该算法进行了改进,进一步将预测的区域划分为更小的子区域,并为每个区域赋于不同的概率,概率越大,则节点出现的几率越高.

Yong等人^{[ 13 ]}发现:网络绝对时延不能精确地对主机进行定位,而只能提供较粗粒度上的定位,而许多组织网站上提供详细的地理位置,因此提出了一种3层定位算法(three-tiered geolocation algorithm,简称TTG).

TTG算法基本上分为3步:① 在第1层,使用网络时延来确定大尺度的地理位置,采用了CBG的改进算法;② 在第2层,使用大量基于网站的基准节点将IP定位到一个较小的范围内,通过测量点分别向基准节点和被测节点发起traceroute测量,通过寻找路径中的最近共同路由器来估测被测节点与基准节点间的时延,依次来确定被测主机的位置范围.由于不同的路由器到达相同被测主机的路径并不相同,TTG算法在众多的测量结果中选择最小的时延作为两者之间的时延;③ 在第3层,基于第2层的定位信息来选择更多的通过增加基于网站基准节点的数目来选择最近基准节点以获得准确的位置(如图 4所示).

影响TTG算法精度的因素是:① 基准节点的密度;② 人口密度,人口越多,越容易获得基准节点,从而能够提高精度;③ 网络接入方式,算法精度对于最后一跳时延变化较大的网络接入方式影响较大.

总体上,综合定位算法的精度最高,计算开销最大,也是定位算法的发展方向.未来定位算法的设计需要根据用户不同定位精度的需求来进行设计,从而在计算开销与定位精度之间获得一个平衡.

3 基于客户端的定位算法

基于客户端的定位算法需要在主机或者设备上安装额外的定位装置,将定位装置提供的位置信息作为主机或设备的位置信息报告给定位系统.一般地,这些系统将GPS、WiFi、蜂窝基站、Zigbee、射频识别(radio frequency identification,简称RFID)、线性调频扩频技术(chirp spread spectrum,简称CSS)等无线定位系统作为信源^{[ 35, 36, 37, 38, 39, 40, 41 ]}.

基于GPS的定位系统需要在主机或设备上安装GPS模块,主机或设备通过驱动与GPS模块进行交互^{[ 36 ]}.定位服务启动后,首先读取GPS模块的位置信息,然后根据其服务器报告其所在的位置;否则,服务器无法得知其位置所在.这种定位方式广泛地应用于移动电话、计算机以及各种嵌入式系统中,定位精度是最高的.除GPS外,俄罗斯的Glonass和我国自主研发的北斗定位系统也有一定范围的应用.

基于蜂窝、蓝牙、WiFi、RFID、Zigbee和CSS的定位算法可以归纳到基于时间的系统和基于信号强度的系统两类,而且这两类系统具有一定的共性,如图 5所示^{[ 35, 36, 37, 38, 39, 40 ]}.无线定位系统一般由锚节点、待定位节点和定位服务器组成,其中,锚节点的准确地理位置已知,待定位节点为定位目标,而定位服务器则提供位置查询服务或者用户位置的解算.其中,基于蜂窝、蓝牙、WiFi、RFID和Zigbee的定位算法通过测算节点之间连接信号强度(received signal strength indication,简称RSSI),利用无线信号的空间传输衰减模型估算出节点间传输距离^{[ 42 ]}.RSSI由于采用信号衰减进行测量,理论测量的精确距离范围在80m以内,80m以外甚至将无法获得距离信息.实际使用时,由于环境等因素的影响,在10m~20m范围内定位精度可达3m左右.典型的基于蜂窝和WiFi的定位算法有谷歌公司的My Location^{[ 43 ]}和Skyhook^{[ 44 ]}.

CSS采用802.15.4a标准,通过SDS-TWR的测量方法获取双向传输时延,进而获取节点距离.该算法运用窄脉冲进行精确的到达时间差(time difference of arrival,简称TDOA)运算^{[ 45 ]},根据定位基站的已知坐标,确定移动标签在定位场景中的位置.由于CSS基于时间测量机制,在测量精度3ns~4ns的情况下,无线电检测精度将达到1m~1.2m.而实际使用中,由于受到前端多路径到达波检测、时间偏差等原因影响,误差可以控制在1m~3m.

然而,这种方法存在两个问题:第一,采用这些定位方法要取得较高的精度,就必须提供尽可能多的基站等基础设施或与拥有这些设施的ISP进行合作,这是一般的服务提供商所无法实现的;第二,由于需要增加额外的硬件模块,会导致设备成本增加,为大面积应用带来阻力.

4 相关技术 4.1 隐私保护技术

在网络运营商和内容提供商尽量获得用户准确IP地址的同时,许多用户则不想暴露自己的准确地理位置而以避免隐私泄露.然而,有时只有向服务商提供地理位置才能获得用户想要的服务,这就需要设计某种机制来达到一个折中.隐私保护技术可以视为对IP定位技术的扩展,在用户通过独立于客户端的定位算法或基于客户端的定位算法获得准确位置后,用户使用隐私保护技术将自己的位置向定位服务器注册自己的位置.当前的隐私保护技术大致可分为两类:一类是通过伪造或者修改用户的地理位置来防止用户信息泄露^{[ 21, 46, 47, 48, 49 ]},另一类是通过策略控制用户地理位置的可见性^{[ 50 ]}.

Kido等人提出了一种方法,在用户的真实地址基础上生成多个虚假地址,将其发送给定位服务提供商(location based services,简称LBS).由于这些虚假的地理位置彼此很相近,位置服务提供商也不能区别地址的真伪,从而实现对用户隐私的保护^{[ 46 ]}.另外一种常见的隐私保护方法就是采用k-anonymity方法,对用户的行踪进行伪装,这种方法既能保证用户的地理位置信息具有一定的准确性,又能保证用户隐私不被泄露,如图 6所示.k-anonymity的基本思想是:在LBS和用户之间设置一个受双方信任的代理,当它收到用户的IP地址后,它会调整用户的坐标生成一个覆盖地址,而在这个区域内至少有k-1个其他用户.因此,在覆盖区域内的广播信息中无法确认用户的具体位置^{[ 51 ]}.同时,Beresford等人^{[ 48 ]}通过不断改变用户的名字来保护用户的隐私.但是在用户数据区分不大的情况下,可以通过某些方法对用户的位置进行推断^{[ 47 ]}.Liu等人采用博弈论的方法分析了用户在使用k-anonymity方法时的行为,并对k-anonymity方法进行了分布式改进^{[ 21 ]}.

在第2类算法中,最简单的方法是对用户发布的位置信息采用基于组的访问控制,用户可以设置自己的朋友圈或家人看到自己位置,如Facebook,Google+等.如今,一般的手机则只能设定用户位置可见或不可见^{[ 50 ]},隐私控制粒度较粗.Li等人提出一种隐私位置查询协议(privacy-preserving location query protocol,简称PLQP),从不同粒度和层次对用户访问权限进行设定.其基本思想如下:访问粒度通过条件对用户进行过滤;将用户的地址分层进行加密,最高层为用户的确切地址,其余层为用户非确切地址,不同权限的用户可以对其进行解密;对协议传输过程中的所有请求和响应报文进行加密,因此,服务器也无法看到用户的确切位置.

4.2 网络新技术对IP定位的影响

如今Internet已成为人类社会重要的基础设施,但是由于Internet存在IP地址不足、缺乏安全机制等问题,严重制约了其发展.为此,研究者提出了许多新的协议和解决方案以弥补现有Internet的不足.新协议改变了原有网络的结构,甚至有的协议提出了定位方法,这些新的变化对互联网IP定位技术产生了重大影响.

近年来,IPv6网络基础设施建设稳步推进,商用网络部署发展迅速,用户规模成倍增长.过去两年,全球IPv6网络的商用部署均以超过50%的增速在增长^{[ 52 ]}.许多用户期望IPv6网络中可以提供定位服务,然而IPv6与IPv4一样,不提供定位服务^{[ 53 ]}.IPv6的地址分配中,是否将地理因素作为地址分配的因素,取决于网络运营商和互联网管理机构的决策,因此,IPv6网络中的主机定位仍需采用额外的定位方法,而不由网络本身提供.

位置标识/身份标识分离协议(locator/ID separation protoco1,简称LISP)是近年来提出的一种数据包路由方法^{[ 54 ]}.LISP将网络地址分为标识符(identifier)和定位符(locator)两部分.标识符是两台主机通信会话的整个生存期内使用的位串,用于对其中一台主机相对于另一台主机进行标识.定位符是用于对某个特定包必须交付的位置进行标识的位串.在Internet协议中,标识符和定位符统一使用IP标识,这使得网络核心的路由越来越复杂.LISP在核心路由不变的情况下,尽可能地保持了端系统的不变,用端系统的IP地址作为端系统的身份标识,而使用另外的路由器ID(RLOC)作为定位符,并在路由器之间转发报文时利用这个新的RLOC.在这种情况下,如果路由器的地理位置可以准确定位,则用以近似确定用户的地理位置.该方法的精度与Shortest Ping相近.

与LISP相近的另一种方案是主机标识协议(host identifier protocol,简称HIP)^{[ 55,56 ]},该协议将现有域名空间进行扩展,通过全称域名(fully qualified domain name,简称FQDN)来命名不同的主机,以实现端系统标识符和定位符的分离.HIP层位于传输层和网络层之间,完成主机标识与IP地址的双射.在HIP协议中,用户的地理位置可以通过域名中的信息进行推断,其定位精度和方法与GeoTrack类似.LISP与HIP协议都可以用来对用户进行定位,但是并不能提供准确的位置,其定位精度取决于接入路由器的覆盖范围或用户提供的位置信息的精度.这主要是由于网络寻址中的定位主要是为了标识主机通信中的数据交付位置而不是物理位置所致.

HTML5是用于取代1999年所制定的HTML 4.01和XHTML 1.0标准的HTML(标准通用标记语言下的一个应用)标准版本^{[ 7 ]}.在HTML5中,地理位置相关的主要对象是navigator.geolocation,它有一些方法和属性检测浏览器对HTML5地理位置的支持性.这个API只定义了一个高层应用的服务接口,而不关心底层采用何种定位方法.换言之,如果用户要实现定位功能就需要在主机上安装GPS模块或者WiFi等其他硬件模块,或者采用独立于客户端的定位算法获得自己的位置,然后将定位结果提供给浏览器,才能实现定位.

5 定位技术综合分析

前面已对各种典型的IP定位算法进行了详述,在本节中,我们将结合IP定位算法的典型评价指标对算法性能进行综合分析^{[ 57, 58, 59, 60 ]}.

· 算法复杂度,复杂度是衡量算法计算开销的重要指标,开销越小,则算法速度越快,越易实现和部署;

· 定位精度,定位精度是衡量定位算法优劣的最重要的指标,不同粒度的定位精度,决定了算法的应用范围;

· 主动测量,主动测量会给网络产生扰动,从而影响定位精度;而被动测量或查询的方式则对网络影响较小;

· 扩展性,主要从定位系统是否存在中心化设施、部署成本以及是否容易增量部署几个方面进行衡量.分为差、中、较好3个层次;

· 部署方式,在定位过程中,算法的设计确定了定位系统的部署方式.采用集中式部署借助于服务器能够提高系统的收敛速度,但是不易于扩展;而分布式系统则无需基础设施的支持,具有较好的扩展性.

表 1给出了各种定位技术的综合对比情况.

从整体上看,IP定位技术的发展趋势如下:

(1) 定位算法的设计已经由单纯的经验主义引入了更多的科学方法.最初的定位算法依靠从主机名中隐藏的信息或查询Whois数据库来获得主机位置,后来通过时延与地理距离来估测主机位置,在TBG和Posit等算法中,则引入了规划理论与概率估计来计算主机的位置.在未来的研究中,寻找更加合适的数学方法或建立更为准确的模型,才是提高定位精度的科学途径;

(2) 定位算法考虑了更多的网络因素,模型变得更加细致、准确.由于网路中迂回路径的存在,无法直接依靠时延与地理距离的线性关系来进行定位,因此,算法的设计过程中引入了更多的网络拓扑和路由信息,如CBG,TBG等算法.在未来的算法设计过程中,要考虑时延抖动、测量开销以及路径的非对称性等因素;

(3) 从单一的定位模式向复合定位技术转变.研究表明,任意一种单一定位技术都存在其局限性,无法适用于所有的InternetIP设备.因此,只有各种定位方法相互验证才能提高定位精度.在设计复合定位算法或系统时应考虑定位精度的需求,采用分层设计思想,在满足用户需求的同时,尽量减少定位过程中产生的测量开销;

(4) 在提高定位精度的同时,要兼顾到用户的隐私.由于定位服务提供商尽可能地提高定位精度,而用户则希望在满足需求的情况下尽可能地隐藏自己的真实位置,未来的算法要在这两者之间达到一种平衡.

6 结束语

伴随着云计算和社交网络等新型Internet应用的不断发展,IP定位技术受到越来越多的关注,商用定位系统层出不穷,定位服务已成为W3C标准的一部分.研究表明:简单地利用时延与地理距离之间的线性关系和网络路径以及注册信息,任何一种技术所获得的定位精度都是有限的.综合定位方法的精度虽然较高,但是测量开销也较大,而且需要较为复杂的步骤.在设计定位算法时,不仅要追求高定位精度,同时还要充分保护用户隐私,才能取得定位服务商和用户的双赢.未来,定位算法或系统应根据不同用户的需求提供不同精度的定位服务和隐私保护,在定位复杂精度和计算开销之间达到一种平衡,并得到更多用户的支持.