位置计算:无线网络定位与可定位性
图书简介

无线通信技术的高速发展使得以手机、平板电脑、笔记本电脑、甚至小型无线传感器节点为代表的移动计算终端迅速普及,目前已超越传统的台式电脑成为互联网最主要的终端设备形态。移动终端随着使用者的移动或网络部署的变化而随时变换位置,其位置信息对于近些年来在移动计算领域大放异彩的位置服务具有重要意义。本书源自作者十年来在无线定位领域科研工作的总结,包含无线定位的基础知识、技术特点、解决方案、以及前沿研究成果。本书按照物理测量、位置计算、数据处理这条主线来安排内容,着重讨论了物理测量、单跳位置估计、基于测距的多跳定位、基于非测距的多跳定位、移动连续定位、误差控制、可定位性、室内定位、位置隐私等技术。本书面向所有对定位技术感兴趣的读者。特别地,本书可以作为本领域科研人员的参考、研究生专业课程的教材、大学本科高年级学生的扩展阅读。

本书荣获第四届“中国大学出版社图书奖”优秀学术著作二等奖。

前言

无线通信技术的高速发展使得以手机、平板电脑、笔记本电脑、甚至小型无线传感器节点为代表的移动计算终端迅速普及,目前已超越传统的台式电脑成为互联网最主要的终端设备形态 。移动终端随着使用者的移动或网络系统的部署而随时变换位置,其位置信息对于无线通信技术本身、以及近些年来在移动计算领域大放异彩的位置服务(Location-based Services)具有重要意义。因此,无线定位技术成为人们关心的兴趣点、工业界的应用重点、以及学术界的研究热点。

本书的作者曾撰写《Location, Localization, and Localizability》,该书由施普林格出版社(Springer)于2010年在纽约出版。一转眼三年过去了,随着无线通信技术与嵌入式技术的飞速发展,特别是以iPhone为代表的智能手机的流行,无线定位技术取得了长足的发展,许多新技术和新方法将无线定位提升到更广阔的应用舞台。于是我们有了将这个领域的最新研究与应用成果出版一本中文著作的想法。

本书的写作过程也是我们学习和重新学习的过程。许多精巧的设计、高效的算法、出众的性能、实用的系统让我们感叹这一领域的丰富成果以及更广阔的未探索区域。本书的部分内容来自于同行公开发表的研究成果,部分来自于我们科研团队的工作。定位技术所涉及的内容跨越多个学科,而我们的研究工作只限于其中几个方面,因此本书的写作参考了许多相关方面的著作、论文和技术报告,在此向这些参考文献的作者表示衷心的感谢。在本书中,我们尝试根据自己的理解去组织、描述和评价现有的工作,争取通过本书勾绘出无线定位技术的发展前沿。

本书按照物理测量、位置计算、数据处理这条主线来安排内容。具体来讲,本书第二章讨论了物理测量的方法,包括测量无线信号的传播距离、到达角度、覆盖区域、网络邻近关系等等。物理测量是定位的基础,定位的精度受限于物理测量的精度。第三章分析了在物理测量基础上的单跳位置计算方法,无论是无线自组网定位还是无线室内定位都以单跳位置计算为核心。第四章和第五章分别介绍了网络定位中基于测距的和基于非测距的多跳定位方法。第六章描述了利用移动信息的特殊定位方法,网络终端的移动性既为定位带来了难度,也带来了更强的位置时空关联性。第七章讨论了当物理测量出现误差或者异常的时候,如何在数据层面保证定位的精度。解决方案包括降低异常数据的权重或者直接剔除异常数据。在没有真实数据的情况下,实现这个解决方案并不容易。在第八章中,我们关注的重点转变为判断物理测量所获得的观测信息是否充分,以保证可以计算出目标的位置。对于单跳定位的系统,其可定位性判断相对直观;当应用场景从单跳定位升级为网络定位后,可定位性的判定变得更加复杂。第九章讨论了相对成熟但发展依旧迅速的无线室内定位技术,相对于以GPS及类似系统占主导地位的室外定位技术,室内定位技术从思想到方法、再到系统都是百花齐放的。在第十章中,我们描述了定位技术带来的“隐患”,提高定位服务质量与保护用户位置隐私似乎总是一对矛盾。以GPS为代表的卫星定位技术以及机器人定位导航技术在本书中没有涉及。

本书面向所有对定位技术感兴趣的读者。特别地,本书可以作为本领域科研人员的参考、研究生专业课程的教材、大学本科高年级学生的扩展阅读。本书前三章讲述了无线定位基础知识,对传感网定位的读者可以重点阅读第四章到第八章,对室内定位感兴趣的读者可以重点阅读第九章和第十章。本书整体上是通俗易懂的,我们尽量保持这样一个风格,但为了内容的严谨,部分章节需要读者掌握基本的优化方法、数值计算方法、以及图论相关的知识。

对于本书的完成,我们首先要感谢清华大学孙家广院士、王建民教授、顾明教授、香港科技大学倪明选教授、陈雷教授、美国伊利诺伊理工学院李向阳教授,还有很多在国内和国外的同事和同行,他们包括李默、韩劲松、何源、刘克彬、王继良、毛续飞、赵弋洋、杨磊、惠维、王小平、陈涛、简丽荣等。在本书的写作过程中,我们还得到清华大学和香港科技大学的多位研究生的帮助,他们包括刘峻良、周子慕、上官龙飞、孙伟、张幸林、徐涵、魏红亮、熊曦、林琼政、段春晖等。本书的完成得到了国家自然科学基金项目(编号61171067、61190110、61125202)、国家高技术发展研究计划(863)项目(编号2011AA010100)、国家重点基础研究发展计划(973)项目(编号2012CB316200)的资助。清华大学出版社的张民老师为本书的出版提供了大力支持。在此一并表示感谢。

人生是一个不断学习的过程,这本书可以作为我们科研工作的阶段总结。希望大家不吝赐教,我们的电子邮件地址是hmilyyz@gmail.com。

第一章 无线室内定位概述

位置,位置,位置。——佚名

西方谚语说一个便利店的成功取决于三个因素:位置、位置、还是位置。在中国,军事家用“天时地利人和”将地理信息置于影响战争的三要素之一。位置是人或物体在物理世界中的自然属性,也是生活中人们非常关心的信息,小到“超市在哪里”,大到“拉登在哪里”,都和位置有关。

位置信息有多重要?例子太多了,人们第一个想起的可能是“不教胡马度阴山”的飞将军李广。据《史记》记载,李广死于汉朝与匈奴的决定性战役漠北之战中,但并非死于敌人的弓箭长矛,而是自刎身亡。元狩四年(公元前119年),李广任前将军,因迷失道路,未能参战,愤愧自杀。李广的遗言“广结发与匈奴大小七十余战,今幸从大将军出接单于兵,而大将军又徙广部行回远,而又迷失道,岂非天哉!且广年六十余矣,终不能复对刀笔之吏”让王勃感叹“冯唐易老,李广难封”。古往今来许多人分析了“李广难封”的原因,性格、战法、时势等不一而足。我们认为位置信息缺失也是其中一个主要原因。茫茫大漠中行军作战,发现自己以及敌人的位置是赢取战争的先决条件,李广的战法又何尝不受限于当时的定位技术。

定位不一定要通过特殊的定位技术。生活中我们找人、找物、找商场、找饭店都采用了各种朴素的定位方法。通俗来讲,定位就是通过观察测量确定一个物体的位置。这个位置可以是物理世界中的坐标,例如GPS提供的以地球为参照系的经纬度坐标;也可以是逻辑位置,例如室内定位中依据建筑内部结构图给出的房间号。采用不同的技术,定位的精度从毫米到千米都有可能,适用于不同的应用场景。

要定位一个物体总少不了对这个物体的观测。“众里寻他千百度,蓦然回首,那人却在灯火阑珊处”,这是以可见光为观测手段的定位;“姑苏城外寒山寺,夜半钟声到客船”,这是以声波为观测手段的定位。无论是可见光还是声波,广义上讲都是无线信号,在此基础上的定位技术都可以归为无线定位。然而以人为主体的眼观耳听毕竟有局限,自上世纪开始,人们开始使用无线电作为信号。最早的应用大都是军事用途,例如雷达定位、卫星定位,依赖于专业人员、专业设备以及保密的技术。

无线定位技术第一次与人们日常生活的亲密接触要归功于GPS的普及。GPS是全球定位系统(Global Positioning System)的简称,已成为目前世界上最常用的卫星导航系统。GPS计划开始于1973年,1989年正式开始发射GPS工作卫星,1994年第24颗工作卫星的发射,标志着GPS卫星组网的完成,从此GPS正式投入使用,为地球表面绝大部分地区(98%)提供准确的定位。2000年5月1日,美国总统克林顿命令取消GPS系统在民用上的诸多限制,从此民用GPS信号可以达到几米到十几米的精度,大大拓展了GPS的可用性。十几年来,GPS已成为室外定位的龙头老大,从轮船汽车到手机手表,都可以配备上GPS定位模块,完成定位和导航的功能。GPS定位的基本原理很简单,首先测量接收机与多个GPS卫星之间的距离,然后通过三点定位方式确定接收机的位置。与GPS类似的系统还包括俄罗斯的GLONASS全球卫星导航系统、我国的北斗一号区域性卫星导航系统、以及欧盟的伽利略定位系统。我国目前正在建设自主研发的北斗二号全球卫星导航系统,届时将可提供全球范围的信号覆盖。

GPS是室外定位的龙头老大,但到了室内就力不从心了。由于建筑物对卫星信号的遮蔽,GPS终端在室内或者建筑物密集的室外很难搜索的卫星信号,同样的道理,森林和地下环境也是GPS的软肋。在这种情况下,定位技术由室外拓展到室内的接力棒就交给了以WiFi定位为代表的室内定位技术。WiFi定位的流行完全可以归功于WiFi作为无线接入技术的流行。WiFi网络基础设施和终端的普及使得WiFi定位变得十分方便且成本低廉。主流的WiFi定位技术是基于信号指纹的,其过程分为训练和运行两个阶段。在训练阶段,工程师现场勘测室内区域内每个位置的无线信号指纹(通常表示为该位置可侦测到的多个网络接入点的信号强度所构成的向量),这些指纹及其相应的位置最终形成由二元组<指纹,位置>构成的指纹数据库,供下一步查询使用。在运行阶段,用户将其所在位置的指纹作为关键字查询指纹数据库,定位系统根据特定算法将指纹数据库中最匹配的指纹所对应的位置作为用户的定位结果。当然,用户的历史位置和运动信息能进一步提高定位精度。WiFi定位可以实现房间级别(或米级)的精度,可用于人员、资产的定位和管理,例如医生在哪个病房,打印机在会议室的哪个角落。如果需要更高精度的定位,例如厘米级的精度,单纯凭借WiFi指纹就不够了。

随着无线定位技术的普及,“基于位置的服务”(Location Based Service,简称LBS)正向我们展现出广阔的市场前景。广义上说,位置信息不只是空间信息,应该包括所处的地理位置、处在该地理位置的时间、处在该地理位置的对象(人,或设备)。也就是说,位置信息承载了“时间”、“空间”、“人物”三大关键信息。利用这些信息,我们不仅可以“因地制宜”,提供所在地附近的相关服务,还可以根据时间“见机行事”,提供时效性更佳的服务,更可以“因人而异”,提供个性化的定制服务。什么时候提供什么样的服务取决于用户的位置,到了饭馆周围提供当日特价菜,到了电影院周围提供影讯,到了教学楼提供附近教室课程信息等等,这些信息不仅避免了广告的盲目性,反而给用户贴心的感觉。LBS广告利用位置信息将线上流量导入到线下商店,成为未来具有竞争优势的广告投放模式,最热门的行业是餐饮类,也包括快消零售类、金融银行类、汽车类、日化类等其他行业。值得注意的是,定位技术也是把双刃剑,位置信息丰富的内涵使得越高精度的定位技术就越让我们置身于更大的安全风险之中。不法分子可以利用我们的位置信息,推测出各种各样关于我们个人的隐私信息。如何在使用LBS的同时做好位置隐私保护的工作是LBS面临的重要挑战。

无论是WiFi还是GPS,其网络结构都是单跳的,终端设备(GPS中是接收机、WiFi中是无线网卡)直接与基站通信(GPS中是卫星、WiFi中是接入点),形成以基站为中心的星形网络。随着以传感网、物联网为代表的无线自组织网络技术的发展,定位技术也相应地从基站定位(单跳定位)升级为网络定位(多跳定位)的方式:网络中少量节点(一般称为信标节点或者锚节点)通过手工设置或GPS拥有全局位置信息,其余大量节点先获取与邻居节点的相对位置关系,再通过无线网络交换数据相互配合进而获得全局位置。这种定位方式还有合作定位、迭代定位等其它名称,这些名称的共性都强调当被定位的终端不能与信标直接通讯时,需要其它终端的配合确定与信标的相对位置。在无线自组织网络中,位置与无线网络的关系不再是单一的通过无线网络计算位置,位置同样也可以反作用于网络:不仅使感知数据具有地理意义,还能辅助其他网络功能和管理,例如路由、拓扑控制、边界发现等等。

……

查看全文
图书目录

1. 无线定位概述

2. 物理测量

2.1. 距离测量

2.2. 角度测量

2.3. 区域测量

2.4. 跳数测量

2.5. 邻居测量

2.6. 小结

3. 单跳位置估计

3.1. 基于距离的定位方法

3.2. 基于到达时间差的定位方法

3.3. 基于到达角度的定位方法

3.4. 基于信号指纹的定位方法

3.5. 小结

4. 基于测距的多跳定位

4.1. 计算组织方式

4.2. 集中式定位算法

4.3. 分布式定位方法

4.4. 小结

5. 基于非测距的多跳定位

5.1. 基于跳数的定位

5.2. 各向异性网络中基于跳数算法的改进

5.3. 基于相邻性的定位算法

5.4. 小结

6. 移动连续定位

6.1. 概述

6.2. 蒙特卡罗定位

6.3. 凸近似定位

6.4. 移动基线定位

6.5. 小结

7. 误差控制

7.1. 测量误差

7.2. 误差特征

7.3. 定位歧义性

7.4. 位置精化

7.5. 抗异常值定位

7.6. 小结

8. 可定位性

8.1. 网络可定位性

8.2. 图刚性理论

8.3. 构造全局刚性图的一般方法

8.4. 节点可定位性

8.5. 小结

9. 室内定位

9.1. 室内定位的特点

9.2. 室内定位技术

9.3. 新方法与新挑战

10. 位置隐私

10.1. 位置隐私概述

10.2. 位置隐私面临的威胁

10.3. 位置隐私保护策略

10.4. 基于匿名的隐私保护

10.5. 小结

查看详细图书目录