（计算机科学与技术专业论文）移动自组网的组移动位置服务.pdf

国防科学技术大学研究生院硕士学位论文 摘要 移动自组网m a n e t 因具有不依赖基础设施、易于组建和无中心抗毁能力强 等特点受到了广泛关注，尤其适用于作战分队之间的通信、灾后救援中救灾小组 之间的通信等对组建时间和抗毁能力有很高要求的场合。m a n e t 的移动特性使得 传统基于拓扑结构的路由协议控制十分复杂，可扩展性不好，很难满足大规模 m a n e t 的需求。而基于位置信息的路由协议通过节点位置信息进行路由，而不是 采用拓扑信息，消除了节点拓扑维护的开销，被广泛认为是一种可扩展的大规模 m a n e t 路由解决方案。 基于位置信息的路由协议必然依赖于可扩展的位置服务，因此位置服务是基 于位置信息的路由协议的基础，也是大规模移动自组网的基础，对m a n e t 的应 用和发展起着至关重要的作用。由于m a n e t 中节点移动速度较快，位置服务研 究仍面临众多亟待解决的问题，如网络划分方式、位置更新方式和位置查询方式 等。针对这些问题，本文利用了m a n e t 中存在节点成组移动的现象，研究和设 计符合体现组移动特性m a n e t 的位置服务。 针对m a n e t 中节点成组移动的现象我们提出组移动位置服务g m l s 。在组 移动中，一组节点之间距离较小、运动的方向基本一致、相互之间的位置变化不 大。g m l s 首先采用节点的位置和速度刻画相似度，利用相似度定义组，并以组 划分网络。这种划分方式利用了网络的基本特性，相对于机械的将网络划分为方 格的传统方法更为合理，符合网络划分的目的。另外，同组节点速度相近，移动 过程中节点相对位置变化不大，我们将节点相对位置作为位置更新依据和内容， 降低位置更新频率，减小了位置维护的开销，提高了位置服务的效率。本文通过 数学方法分析了g m l s 的性能，与g l s 等已有位置服务相比，在位置维护和位置 查询方面都有较大提高。最后，通过实验的方法验证了g m l s 有较高的性能，更 适合于具有群组移动性的大规模m a n e t 环境。 主题词：移动自组网，位置服务，组移动 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t p a c t m o b i l ea dh o cn e t w o r k s ( m a n e t ) a r e s e l f - o r g a n i z i n g ，r a p i d l yd e p l o y a b l ea n d d y n a m i c a l l yr e c o n f i g u r a b l en e t w o r k s ，w h i c ha r ef o r m e db ym o b i l en o d e sw i t hn o p r e e x i s t i n g i n f r a s t r u c t u r e s s o m e t y p i c a la p p l i c a t i o n s o f 僵a 全t e ti n c l u d e c o m m u n i c a t i o ni nb a t t l ef i e l da n dd i s a s t e rr e l i e fs c e n a r i o d u et ot h eh i g h l yd y n a m i c t o p o l o g yo ft h en e t w o r kt r i g g e r e db yn o d em o b i l i t y ，t h et r a d i t i o n a lt o p o l o g y b a s e d r o u t i n gp r o t o c o li sn o ta p p l i c a b l e ，w h i l et h ep o s i t i o n - b a s e dr o u t i n gp r o t o c o lc a ns c a l e w e l li n 【a n e t p o s i t i o n b a s e dr o u t i n gp r o t o c o l sd e p e n do ns c a l a b l el o c a t i o ns e r v i c e ，s ol o c a t i o n s e r v i c ei st h ef o u n d a t i o no fp o s i t i o n b a s e dr o u t i n ga n di ti st h ef o u n d a t i o no fm a n e t l o c a t i o ns e r v i c ep l a y sa ni m p o r t a n tr o l ei nman e t ，w h i c hm a k e si tah o tp o i n to f s c i e n t i f i cr e s e a r c h u n t i ln o wt h e r ea r es t i l ls o m ei m p o r t a n ti s s u e st os o l v e s u c ha st h e p a r t i t i o no fn e t w o r k sa n dt h em a i n t a i n i n gf u c t i o no fp o s i t i o n i na l l u s i o nt oa l lt h o s e p r o b l e m s ，t h i st h e s i sm a k e su s eo fg r o u p - m o b i l i t yo ft h en e t w o r k st op r e s e n t san o v e l l o c a t i o ns e r v i c e ：g r o u p m o b i l i t yb a s e dl o c a t i o ns e r v i c e ( g m l s ) t h em o b i l i t yo fn o d e si nm a n e tm a k e si tc o s t l yt om a i n t a i nt h el o c a t i o ns e r v i c e w h i c ha l s om a k e st h ee x i s t i n gl o c a t i o ns e r v i c eu n s e a l a b l e h o w e v e r , g m l sc a ns c a l e w e l li nt h i sc i r c u m s t a n c ef o rg m l su s e st h ea d v a n t a g eo fg r o u p m o b i l i t y n o d e si n g r o u pa r ec l o s et oe a c ho t h e r ，m o v ew i t hs i m i l a rp a t t e ma n dt h er e l a t i v el o c a t i o no f e a c h o t h e rc h a n g e ss l o w l y g m l sp u t sf o r w a r dt h ec o n c e p to fs i m i l a r i t yb yt h ep o s i t i o na n d v e l o c i t yo fn o d ea n dp a r t i t i o nt h en e t w o r k sb a s e do ni t c o m p a r et ot h et r a d i t i o n a l n e t w o r kp a r t i t i o nm e t h o d p a r t i t i o nt l l en e t w o r ki n t og r i d o u r si sm o r er e a s o n a b l e i n a d d i t i o n ，w em a k eu s eo ft h es c e n a r i oo fg r o u pm o b i l i t yt oi m p r o v et h ee f f i c i e n c yo f l o c a t i o ns e r v i c eb ym a i n t a i n i n gt h er e l a t i v el o c a t i o na m o n gn o d e st or e d u c et h eu p d a t e i j r e q u e n c ya n dc o s to fl o c a t i o ns e r v i c e t h e o r e t i c a la n a l y s i sa n dp e r f o r m a n c ee v a l u a t i o n s h o wt h a tg m l ss c a l eb e t t e rc o m p a r et oe x i s t i n gp r o t o c o l s k e yw o r d s ：m a ne t ，l o c a t i o ns e r v i c e ，g r o u p - m o b i l i t t y 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表1 1m a n e t 与蜂窝网、有线网络特点比较2 表4 1 常见符号说明。4 2 表4 2g l s 和g m l s 的性能对比4 8 表5 1 仿真参数5 2 第1 i i 页 国防科学技术大学研究生院硕士学1 1 ) = 论文 图1 1 图1 2 图1 3 图1 4 图1 5 图1 6 图1 7 图1 8 图2 1 图2 2 图2 3 图2 4 图目录 m a n e t 结构图2 蜂窝网结构图2 m a n e t 常见应用图3 m a n e t 路由分类4 l a r 期望区域5 l a r 改进型期望区域5 g p s r 原理图6 m a n e t 在战场上的应用。7 位置服务分类一1 3 g l s 原理图一1 5 s l u r p 原理图16 s l a l o m 原理图17 图2 5 研l s 网络划分18 图3 1 平面结构网络2 5 图3 2 分级结构网络2 5 图3 3 组生成算法步骤2 7 图3 4 节点位置分布图2 8 图3 5 节点速度分布图2 8 图3 6 多层网络下的组结构图2 9 图3 7 组成员表结构图3l 图3 8 组维护流程图3 2 图3 9 组相对位置示意图一3 3 图3 1 0 组相对速度示意图3 3 图3 1l 组相对位置维护策略3 4 图3 1 2 基于相对位置的位置更新3 5 图3 13 组内查询算法。3 6 图3 1 4 组外查询算法3 7 图3 1 5 位置查询算法3 7 图3 1 6 位置查询流程3 8 图4 1f 计算原理4 4 图4 2t - = 0 时节点分布一：4 5 第1 v 页 国防科学技术大学研究生院硕+ 学位论文 图4 3t = 3 0 时节点分布4 6 图5 1使用n s 2 进行网络模拟的过程一5 0 图5 2g m l s 类图一5l 图5 3 仿真结果5 2 图5 4 维护开销随节点数增多的变化趋势5 4 图5 5 维护开销随节点速度增大的变化趋势5 4 图5 6 随机通信模式下的位置查询开销5 5 图5 7 组通信模式下的位置查询开销5 5 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：整邈宜鱼圈鲍堑整边焦置腿签 学位论文作者签名： 皿墨美一一一日期：铆7 年忽月z 。日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印，缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：整边自堑圈鲍塑整麴焦星腿签 学位论文作者签名： 蒸】墨筮 作者指导教师签名： 徊 日期：。砷年z 月2p 日 日期：砷年易月彻日 国防科学技术大学研究生院硕士学位论文 第一章绪论 近年来，便携设备和无线通信技术的广泛应用与发展极大地推动了对m a n e t 的研究和应用，在军用和民用领域m a n e t 越来越受到人们的重视。m a n e t 可 以帮助人们在不能利用或不便于利用固定网络基础设施的情况下进行有效的通 信。例如，在战场上实现高动态环境下的分队间的协同作战、在偏远地区科考队 探险工作和抢险救灾过程中的成员之间通信联络等。观察这些应用可以发现 m a n e t 具有的诸多特性，比如网络结构复杂、节点类型多样、通信能力有限、节 点移动频繁、网络拓扑动态变化等。m a n e t 这些特性使得传统的有线网络和无线 蜂窝中技术不能直接应用于其中，所以发展面临众多挑战，其中路由技术面临的 挑战就是一个典型【2 j 。已有理论和实践证明基于拓扑的路由不适用于m a n e t ，为 解决m a n e t 的路由问题，学术界提出了多种方案，到目前为止基于位置信息的 路由被理论证明是m a n e t 路由的最佳选择1 3 j ，实际应用中也取得了很好的效果。 基于位置信息的路由的一个关键技术就是位置信息的获取，即位置服务问题。本 章首先简要介绍了m a n e t 的特点和常见应用，接着介绍m a n e t 中基于位置信 息的路由协议，阐明了位置服务的重要性和面临的挑战。位置服务的挑战之一是 由m a n e t 移动模型带来的，本章介绍了常见的m a n e t 移动模型，着重介绍其 中存在的组移动模型。本章最后阐明了课题的研究内容和主要创新点，给出了论 文的结构。 1 1 1 m a n e t 特点及应用 1 1 研究背景 移动无线通信网络通常是以蜂窝网的形式出现的，其中移动终端借助固定基 站才能完成通信需求。蜂窝网的特点是在网络中有中心控制设备，终端和交换机 路由器分工明确。终端是移动的，它们需要固定网络的支持，也需要类似基站或 访问服务点这样的中心控制设备。这些特点使现有移动通信系统在特殊场合并不 适用，如在野外环境临时通信或应急状态下要求快速建立的通信。 m a n e t 是针对这样的需求而产生的一种网络形式，可以在任何时刻、任何地 点不需要现有基础网络设施的支持，快速构建起一个移动通信网络，是一个多跳 的临时性自治系统1 2 】，网络中的节点同时具备主机与路由器两种功能。任意时刻， 节点可向任意方向以任意速度运动，因此对于不同时刻的网络，其拓扑结构也会 随之发生变化。当通信双方在彼此的传输范围内时，m a n e t 中的两个通信设备之 间可直接进行无线通信，当通信双方不在彼此的传输范围内时，则必须经过其它 第1 页 国防科学技术大学研究生院硕士学位论文 中间节点转发。也就是说节点1 1 j j 的通信可能要经过多个中间节点的转发，即经过 多跳( m u l t i h o p ) ，这是m a n e t 和其他移动网络的最根本区别，因此它也被称为 多跳无线网。蜂窝网和m a n e t 的结构对比如图1 1 和图1 2 所示。 图1 1m a n e t 结构图 图1 2 蜂窝网结构图 m a n e t 的网络结构不同于常规蜂窝网络的结构，主要有以下一些特点： ( 1 ) 自组织的终端节点：每个移动终端节点都具有自组织能力，它们可以同 时扮演路由器和终端的角色。 ( 2 ) 分布式操作：m a n e t 中没有负责中心控制的骨干网，对于网络的控制和 管理是分布到各个网络节点的。 ( 3 ) 多跳路由：当数据发送方和接收方不在单跳范围内时，必须经由其它单 个或多个节点的中继才能完成数据的传输。 ( 4 ) 动态连接质量：相对有线通信，无线通信的丢包率和错误率更高，噪声、 信号衰减和干扰以及低带宽都使得节点间的连接呈现不稳定、低质量的态 势。 ( 5 ) 动态网络拓扑：由于m a n e t 中的节点可以是移动的，且节点间的无线连 接状况也是动态变化的，使得整个网络的拓扑结构呈现出高动态性。 表1 1m a n e t 与蜂窝网、有线网络特点比较 m a n e t 蜂窝网有线网络 中心 无有有 规模较小较大 很大 拓扑变化较快较慢很慢 通信方式终端可相互通信终端只与基站通信终端只与路由器通信 和有线网络和蜂窝网络对比，m a n e t 特殊的网络结构和网络特性有很大不 同，如表1 1 所示。m a n e t 的特性导致其有很多潜在的应用，主要可以分为以下 几类：( 1 ) 战场上应用；( 2 ) 抢险救灾中应用；( 3 ) 办公室中的应用：( 4 ) 第2 页 国防科学技术人学研究生院硕士学位论文 家庭生活中的应用；( 5 ) 购物场所中的应用：( 6 ) 汽车之间的移动通信；( 7 ) 移动协作应用：( 8 ) 基于位置或内容的移动服务。 - r 十， - 竹n f 黑j ，。j 一! l 烹- 蕾一烹、， - i i 蕾1 图i3m a n e l 常应用固 e 一 【 v 1 0 4 下面具体说明其中的几种常见应用。 ( i ) 战场上的应用：在现代化的战场上，要求多种形式的稳定可靠的通信。 各种军事车辆之间、士兵之间、士兵与军事车辆之间都需要保持密切的联系，以 完成集中指挥、协调作战。由于战场上不可能存在固定的基础设施，所以m a n e t 成为战场上随机建立的通信的最佳选择。战争中的另一种m a n e t 应用是无线传 感器网络，无线传感器可以迅速的搜集信息并且周期性的把这些信息发送回控制 中心，控制中心利用这些信息进行作战的部署。传感器传输能力受限，它们之间 的通信必须是多跳才能完成，这样的通信网络是一种典型的m a n e t 。 ( 2 ) 抢险救灾中应用：地震或者水灾之后，蜂窝网的基础设施和有线网的 线路通常会遭到破坏，为了实现救灾队员之间的通信，要求队员所携带的设备必 须能够完成直接的相互通信。同时由于便携设备传输距离有限，距离较远的队员 之间需要中自j 节点的转发才能完成通信。科考探险队的通信也存在同样的问题， 北极或者南极这样的地区没有基础设施可用，也体现出对m a n e t 应用需求。 ( 3 ) 办公室中的应用：在办公室中，工作团体的所有成员可以通过m a n e t 的方式组成一个临时网络来协同完成某一项任务。 ( 4 ) 其他商业应用：未来装备m a n e t 收发设备的登机系统可以自动地与 乘客携带的个人无线m a n e t 设备通信，完成目前的换登机牌等手续。商场内商 品标签可以通过无线接口由m a n e t 设备动态刷新。顾客若携带手持无线设备可 以很容易地找到某种商品和价格，诸如此类的应用已经在商业领域出现，随着技 术的发展必将拥有更加广阔的前景。 第3 页 r i晰 一 国防科学技术大学研究生院硕士学位论文 1 1 2m a n e t 路由协议 m a n e t 设计中的一个关键问题是开发能够在两个节点之间提供高质量高效 率通信的路由协议。m a n e t 网络节点的移动性使得网络拓扑结构不断变化，传统 的因特网的路由协议无法适应这些特性，需要有专门的应用于m a n e t 的路由协 议。目前m a n e t 中的路由协议主要存在两种：基于拓扑结构信息的路由和基于 位置信息的路由，分类如图1 4 所示。 图i 4m a n e t 路由分类 早期针对m a n e t 提出过很多种路由方式主要是基于拓扑信息的，包括主动 式路由( o l s r 4 、d s d v 5 】等) 和按需路由( d s r 6 1 、a o d v ( 7 】等) 。基于拓扑信 息的路由，不管是主动路由或是按需路由，都利用网络链路状态和拓扑信息来决 定数据传递的路由，不能很好的解决m a n e t 节点移动带来的网络结构动态性大 的问题。各移动节点依靠路由发现和数据包在转发过程中收集到的路由信息建立 路由表，然后依据这个路由表来指导后续数据包的转发。m a n e t 的移动性使得抽 象的拓扑图具有很高的动态性，从而引起路由协议性能的降低以及冗余信息的重 发和传输冲突。理论分析和各种实验表明，基于拓扑信息的路由协议不适用于高 速移动的m a n e t ，必须寻找一种新的路由协议替代它【3 j 。 基于位置信息的路由是近年来出现的新的路由，位置信息的引入使得分布式 m a n e t 路由具有一定的方向性，提高了路由的性能，消除了基于拓扑结构信息的 路由协议中存在的一些不足之处。通常，每个节点都通过使用g p s 或者其他类似 的定位装置来取得自己的位置信息，源节点至目的节点的数据传输只需要知道目 的节点的位置和每次数据转发时下一跳节点的位置就可以实现，而不需要其他的 第4 页 国防科学技术大学研究生院硕士学位论文 拓扑信息。这种以位置信息为基础的路由在整个数据传输中不需要建立和维护路 由，能显著减少主机路由的开销，具有更好的可扩展性。主要代表协议有：位置 辅助路由( l o c a t i o na i d e dr o u t i n g ，l a r ) 、移动距离效应路由( d i s t a n c er o u t i n g e f f e c ta l g o r i t h mf o rm o b i l i t y ，d r e a m ) 、贪婪型转发和沿周边转发路由协议 ( g r e e d yp e r i m e t e rs t a t e l e s sr o u t i n g ，g p s r ) 等。 l a r 8 j 通过引入期望区域( e x p e c tz o n e ) 和请求区域( r e q u e s tz o n e ) 的概念提 高了路由的效率，期望区域和请求区域的概念如图1 5 和图1 6 所示。期望区域是 根据目标节点的当前位置和网络中节点的平均速度或最大速度计算得到的，是以 目标节点为圆心、节点速度和传输最大时间乘积为半径的圆。请求区域是根据源 节点和目标节点的位置得到的，是以源节点为矩形一角顶点、包含期望区域的最 小矩形。 r e q u e s tz o n e 图1 5l a r 期望区域图1 6l a r 改进型期望区域 l a r 通过期望区域和请求区域的提出，限制对目标节点信息路径寻找过程中 泛洪的范围，减小了路由开销。d r e a m t 州的思想也很简单，每个节点通过维护一 个到网络中所有节点的位置信息表来决定路由的方向。当源节点想向目标节点发 送数据时，首先根据自身的位置信息表确定目标节点的方向，然后选择该方向上 的所有一跳内节点转发数据，路径上的所有节点根据同样的策略转发数据。 g p r s 1 0 】在d r e a m 的基础上进行改进，节点不再维护网络中所有节点的位 置信息，只需知道自身位置、目标节点位置和一跳内节点的位置即可完成路由。 g p r s 原理如图1 7 所示，当节点想向目标节点发送数据时，则在一跳范围内的节 点中选择距离目标节点最近的节点发送数据，其他中间节点在转发数据时采取同 样的策略。g p r s 不需要像d r e a m 那样维护网络中所有节点的位置信息，大大降 低了路由开销。 第5 页 国防科学技术大学研究生院硕士学位论文 ， r 。 fx ? ? 埔夕i 。- 。t 。1 基于位置信息的路由协议已经在m a n e t 中有了很好的应用，得到了人们的 肯定，是当前m a n e t 研究的热点。基于位置信息的路由协议在发送数据前首先 要确定目的节点的位置，一般这个工作通过一个称为位置服务的组件完成，因此 位置服务是基于位置信息的路由协议的基础，对m a n e t 的应用和发展起着至关重 要的作用。 1 1 3 位置服务面临的挑战 已有基于位置信息的路由协议提出了一些位置服务的策略。在l a r 协议中， 当某节点需要查询目的节点的位置信息时，它将在整个网络中泛洪位置查询信息； 而在d r e a m 协议中，网络中每个节点都维护一个储存了其它所有节点位置信息 的数据库，且所有节点周期性地广播包含其当前位置信息的控制分组，更新其它 节点中维护的位置信息。这两种方法以泛洪作为解决问题的方法，基于泛洪的位 置服务策略简单，但由于泛洪本身的特点，使得在较大规模的网络中，算法的开 销较大，可扩展性不好。 针对泛洪导致的开销过大的问题，位置服务研究领域提出了很多非泛洪的位 置服务，一定程度上减小了开销。但是，这些位置服务单纯在网络的划分、位置 服务器选择、位置维护和查询策略等方面考虑问题，没有充分的利用m a n e t 的 移动特性，随着网络规模的增大，已有位置服务的可扩展性仍然有限。 事实上，要提供可扩展地位置服务是一个本质上的难题，这是因为当一个节 点查询其他节点的位置信息时，它只知道目的节点的标识符( i d ) ，而不知道任 何其他关于目的节点的信息。由于m a n e t 中的节点具有移动性，在节点的标识 符与它的位置之间没有一个静态的关系，从而不能由节点的标识符推断出它的当 前位置。另外，由于节点移动的随机性假设，无法根据已有的节点位置信息的历 史信息推算节点的当前位置，尤其在节点移动速度较快的应用中，位置信息很快 第6 页 国防科学技术 学研究生院硕士学位论文 1 2m a n e t 中组移动 已有位置服务研究将研究范围局限在网络划分、位置服务器选择策略、位置 维护策略和位置查询策略等范围内，没有考虑m a n e t 节点移动特性可能给位置 服务带来的影响，同时也没能很好的利用这些特性改善位置服务麓略。本文观察 移动自组网的主要应用场景，分析其中体现的节点成组移动特性，将组移动的概 念引入到位置服务当中，发掘组移动带来的特性，并将这些特性应用到位置服务 策略设计。 21 m a n e t 中常见组移动应用 m a n e t 的主要应用包括战场上作战分队之间的协同通信、抢险救灾中的应用 和科考探险队的通信等。以作战分队之间的协同通信为例，我们分析m a n e t 中 存在的组移动特性。 耐 r ，e 。 j 一 u e 图i8m a n e t 在战场上的应用 m a n e t 在战场上的应用如图l8 所示。在战场上，士兵、战车、坦克等会组 成一个作战分队，显然各个分队中的节点( 士兵、战车等) 的移动不是随机的， 是由整个分队的作战意图决定的。这些节点可能会以分队指挥单元为参考点，以 一定的规律在指挥单元周围移动，并且体现出一定的目的性、方向性。这样的应 用中的节点往往目的相同、距离较近、移动速度相似，我们称这样的一组节点的 共同移动为组移动。 组移动不只存在于战场上的作战分队，抢险救灾、科考探险和车载网中豹 m a n e t 应用都体现出明显的组移动特性。这些应用中节点移动速度较快、范围较 第7 页 国防科学技术大学研究生院硕士学位论文 大，给m a n e t 中各种策略带来了很大挑战。同时，组移动中节点移动具有一定 的规律性，也给m a n e t 中各种策略的设计带来了机遇。 1 2 - 2 组移动带来的挑战与机遇 m a n e t 中组移动节点的移动速度较快，但是节点之间的相互距离较近、相对 速度较小、相互之间的位置变化较慢。这既给位置服务设计带来挑战，也指明了 位置服务设计的新方向。 因为已有位置服务以节点移动的距离作为位置更新的依据，即位置更新的时机 选择在节点移动了一定的距离时，所以节点移动速度较快必然会导致节点频繁更 新位置信息。组移动中的节点不但移动速度可能很快，同时节点之间的速度相近， 位置更新可能经常同时发生，这给已有的位置服务策略带来的很大的挑战。 然而，通过分析我们发现，在组移动中即使节点的移动速度都很快，但是节点 之间的相对速度较小，即节点之间的相对位置变化较慢。如果我们采用节点之间 的相对位置变化作为位置更新的依据，即以节点相对于组中的某节点或是组的逻 辑中心的位置变化为依据，那么节点进行位置更新的频率将大大降低，位置维护 的开销也必然随之减小。本文正是以这个思想为出发点，提出了移动自组网的组 移动位置服务g m l s 。 1 3 课题主要研究内容 m a n e t 发展的很快，但也面临着众多挑战，其中节点移动性造成网络拓扑动 态变化，往往使得目前基于静态网络提出的路由协议无法适用。基于位置信息路 由充分利用了位置信息获取带来的好处，提高了网络传输的效率，成为m a n e t 路由协议的最佳选择。基于位置信息的路由协议必然依赖位置服务为其提供节点 的位置信息，所以位置服务是基于位置信息路由的基础，受到广泛的重视，发展 较快。 尽管学术界提出了很多位置服务策略，但是针对具体的应用场景仍面临众多 急需解决的问题。针对这样的现象，本文利用m a n e t 中存在的节点成组移动的 特性，提出了移动自组网的组移动位置服务g m l s 。g m l s 由三个部分组成：网 络划分策略、位置维护策略和位置查询策略，其中网络划分策略是基础。本文首 先讨论m a n e t 的移动模型，在此基础上给出了组移动模型的定义并讨论如何利 用组划分网络，进而提出了基于组相对位置的位置维护策略以及与之相适应的位 置查询策略。总结起来，本文的主要工作和贡献包括： ( 1 ) 相似度s i ，i 的概念已经被应用于m a n e t 的移动模型中，本文首次将其引 入到m a n e t 的位置服务设计中，利用其定义组，并以组的方式对网络进 第8 页 国防科学技术大学研究生院硕士学何论文 行划分。相对于传统的按地理位置信息进行的固定网格划分，按组划分网 络一定程度上体现了m a n e t 的本质特性，为更好的进行位置服务策略设 计奠定了基础。 一组节点之间速度相近，移动过程中节点相对位置变化不大，我们将节点 相对位置作为位置更新依据和内容，相对于已有的以绝对位置作为位置更 新依据的位置更新方式，采用相对位置可以降低位置更新频率，减小位置 维护开销。 以组作为位置维护的单位，引入组成员表和组相对位置信息表，位置查询 过程中通过组成员表和组相对位置信息表的查询得到目的节点的位置信 息。 利用已有的数学方法从理论角度分析了组移动位置服务的性能，包括不同 移动模型下的位置维护开销和不同通信模型下位置查询开销，对比已有的 位置服务的结果，证明了组移动位置服务在体现成组移动特性的m a n e t 中的高效性。 在n s 2 中设计并实现了g m l s ，实验表明与已有的位置服务相比，g m l s 在体现组移动特性的网络中效率较高，验证了理论分析的结果。 1 4 论文结构 本文共为六章，章节主要内容如下： 第一章为绪论，指出课题的研究背景、研究意义和研究内容。介绍了m a n e t 的基本概念、产生、应用及特点及发展方向，提出了m a n e t 中存在的节点成组 移动的现象，阐明了组移动给位置服务设计带来的挑战和启示。 第二章首先介绍了m a n e t 中位置服务协议的相关概念以及提出的依据，给 出了位置服务的分类方式，介绍了已有的多种位置服务协议的策略方法、特点以 及它们共有的不足。m a n e t 的移动性给位置服务协议设计带来了很大的挑战，本 章介绍了m a n e t 中常见的移动模型，着重描述了组移动模型及其对位置服务策 略的影响。 第三章详细描述了m a n e t 中组移动位置服务g m l s ，包括该协议的基本思 想、基本过程，并深入讨论了相关问题，如网络划分方式、位置更新策略和查询 策略问题。 第四章从理论角度分析了组移动位置服务的性能，与已有的位置服务对比， 得到g m l s 的优势以及存在的不足。 第五章在n s 2 中实现并模拟了g m l s ，并将模拟实验得到的结果与g l s 比较 分析，与第四章中的理论分析对比，验证g m l s 在体现组移动特性的网络中的高 第9 页 ) ) ) ) 2 3 4 5，k_，k，l 国防科学技术大学研究生院硕士学位论文 效性。 第六章总结了本文工作，并展望m a n e t 中基于移动模型的位置服务研究的 下一步工作。 第l o 页 国防科学技术大学研究生院硕士学位论文 第二章相关工作 弟一早 1 1 日大上作 位置服务在m a n e t 领域有基础性的作用，一出现即成为学术界研究的热点， 目前为止已经出现了多种位置服务。本章我们将对已有位置服务进行详细介绍， 分析它们的特点并按照这些特点为之分类，讨论各类位置服务的优缺点。已有位 置服务均假设网络中的节点是随机移动的，并没有考虑节点的移动模型可能给位 置服务带来的影响。本文针对已有位置服务共有的不足，在进行位置服务设计中 考虑了节点移动模型带来的影响，利用节点的移动特性解决了已有位置服务存在 的问题。所以本章在介绍了位置服务的产生、发展和面临的挑战后，对已有的m a n e t 移动模型进行简要的介绍。 2 1 无线通信网络中的位置服务 位置服务的产生与发展的主要动力来自主观驱动和客观条件两个方面。客观 方面，全球定位系统( g p s ) 、传感定位系统等定位技术的产生和发展使位置服务 的应用成为可能。主观方面是需求的驱动，如前文所述基于位置信息的路由的出 现产生了对位置服务的需求，而且近年来基于位置信息的服务越来越多，也促进 了位置服务的发展。 2 1 1定位技术的发展与应用 全球定位系统是美国国防部部署的一种卫星无线电定位、导航与报时系统， 简称g p s l 32 。g p s 由导航卫星、地面基站和用户定位设备三部分组成，2 4 颗g p s 卫星在离地面1 万2 千公里的高空上，以1 2 小时的周期环绕地球运行，使得在任 意时刻，在地面上的任意一点都可以同时观测到4 颗以上的卫星。由于卫星的位 置我们可得到卫星到接收机的距离，利用3 颗卫星，就可以组成3 个距离公式， 解出观测点的位置( x ，y ，z ) 。考虑到卫星的时钟与接收机时钟之间的误差，实际 上有4 个未知数，x 、y 、z 和钟差，因而需要引入第4 颗卫星，形成4 个方程式 进行求解，从而得到观测点的经纬度和高程。经过2 0 余年的实践证明，g p s 系统 是一个高精度、全天候和全球性的无线电导航、定位和定时的多功能系统，民用 定位技术的定位精度为1 0 0 米，军用定位精度可达到1 0 米以内。作为先进的测量 手段和新的生产力，g p s 已经融入了国民经济建设、国防建设和社会发展的各个 应用领域。 手机定位是利用g s m 移动通信网的蜂窝技术来实现位置信息的查询，g s m 无线通信网是由许多像蜜蜂蜂窝一样的小区构建而成的，每个小区都有自己的编 第1 1 页 国防科学技术大学研究生院硕士学位论文 号，通过手机所在小区的识别号就可以知道手机所在区域。目自i 手机小区定位技 术尚在完善之中，市区精度范围大致在2 0 0 米左右，郊区精度范围大致在1 0 0 0 米 - 2 0 0 0 米左右，随着移动公司技术的不断发展，相信精度会进一步提高到5 0 米范 围内。 室内的定位系统由多个无线传感器构成【1 1 1 。这些传感器被固定在墙上、门上、 天花板等地方。传感器发送的信号中包含有自己的i d ，接收机收到信号就知道该 信号是哪个传感器发送的。然后，节点利用这些信号的强度、相位等信息，计算 自己在这个空间的位置。 定位技术的发展成熟使位置服务的发展和应用成为可能，客观上促进了位置 服务研究的发展。位置服务只有达到一定的精度才有意义，早期的定位精度较低， 制约了位置服务的发展，近年来随着定位精度的提高位置服务也迅速发展起来， 所以说定位技术是位置服务发展的先决条件，起着基础性作用。 2 1 2 基于位置信息的服务 基于位置信息的服务( l b s ，l o c m i o nb a s e ds e r v i c e s ) 是由移动通信网络和卫 星定位系统结合在一起提供的一种增值业务，通过一组定位技术获得移动终端的 位置信息( 如经纬度坐标数据) ，提供给移动用户本人或他人的通信系统，实现 各种与位置相关的业务。实质上是一种概念较为宽泛的与空间位置有关的新型服 务业务。 关于l b s 的定义有很多。1 9 9 4 年，美国学者s c h i l i t 首先提出了l b s 的三大 目标：你在哪里( 空间信息) 、你和谁在一起( 社会信息) 、附近有什么资源( 信 息查询) 。这也成为了l b s 最基础的内容。2 0 0 4 年，r e i c h e n b a c h e r 将用户使用 l b s 的服务归纳为五类：定位( 个人位置定位) 、导航( 路径导航) 、查询( 查 询某个人或某个对象) 、识别( 识别某个人或对象) 、事件检查( 当出现特殊情 况下向相关机构发送带求救或查询的个人位置信息) 。从技术的角度，l b s 实际 上是多种技术融合的产物 当前，基于个人消费者需求的智能化，l b s 将伴随g p s 和无线上网技术的发 展而呈大幅度增长趋势。l b s 不但可以提升企业运营与服务水平，也能为车载g p s 的用户提供更多样化的便捷服务。加拿大的b e l l 移动公司可谓l b s 业务的市场领 袖，率先推出了基于位置的娱乐、信息、求助等服务，2 0 0 3 年1 2 月，b e l l 移动的 m y f i n d e r 业务已占尽市场先机。b e l l 移动还不断推陈出新，2 0 0 4 年9 月，b e l l 移 动发布全球首款基于g p s 的移动游戏s w o r d f i s h ，利用移动定位技术，把地球微缩 成了一个可测量的鱼塘。在l b s 业务创新方面，走在世界最前端的是韩国移动运 营商。2 0 0 4 年7 月，韩国最大的移动运营商s k 电讯率先推出全球首项保障儿童 第1 2 页 国防科学技术大学研究生院硕士学位论文 安全的网络定位服务i 鼬d s ，用柬确认孩子当前的位置和活动路径，一旦孩子的活 动超出设置的范围，就会自动发出报警短信。中国移动在2 0 0 2 年1 1 月首次开通 l b s ，如移动梦网品牌下面的业务“我在哪里”、“你在哪里”、“找朋友”等；2 0 0 3 年， 中国联通在其c d m a 网上推出“定位之星”业务，用户可以在较快的速度下体验下 载地图和导航类的复杂服务：而中国电信和中国网通似乎也看到了l b s 诱人前景， 启动在p h s ( 小灵通) 平台上的l b s 业务。 到2 0 0 8 年初，全球支持g p s 的手机已经占到手机总销售量的2 5 以上，l b s 相关应用更是五花a l - j ，随着技术的发展，l b s 的应用会体现在越来越广的方面。 当前l b s 的位置信息主要由运营商提供，为了高效提供位置服务，国内外各大运 营商都投入很多精力在位置服务上，必将进一步促进位置服务的发展。 2 2 位置服务的分类 由于定位技术和l b s 的发展，位置服务的研究已经非常丰富。在大量查阅国 内外有关m a n e t 中位置服务协议方面文献的基础上，本文对部分已存在位置服 务协议进行了分析，指出了各种位置服务协议特点，并按照这些特点对已有位置 服务进行分类介绍。 已有的文献中主要把位置服务协议按两种原则分类。参考文献【1 2 】根据位置信 息更新时位置信息的传送方式的不同