面向群组移动的轻型位置服务研究

摘 要： 针对现实应用中大规模MANET网络节点呈现的群组移动特性，提出了面向群组移动的轻型位置服务协议G?HLLS。G?HLLS协议将HLLS协议框架与分簇机制相结合，从而保证位置更新及请求机制适应群组移动特性。基于OPNET的仿真实验，从负载、服务成功率、存储开销多个方面对G?HLLS协议性能进行了分析，验证了G?HLLS协议在大规模群组移动网络中表现出的优越性能。

关键词： MANET； G?HLLS； HLLS； OPNET

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）18?0075?06

Research on group mobility oriented HLLS

DU Hui， FAN Xiao?jing

（1. Shaanxi Open University， Xi’an 710068， China； 2. Fujitsu Research & Development Center， Beijing 100025， China）

Abstract： Group mobility oriented HLLS （G?HLLS） is proposes in this paper， according to the group mobility property of large?scale MANET nodes in many actual applications. G?HLLS combines the protocol frame of history information based light location service （HLLS） with clustering mechanism to ensure the location update and request mechanism to adapt the property of group mobility and reduce the storage cost of HLLS. With the simulation based on OPNET， the protocol performance of G?HLLS is analysed in terms of loading， service success ratio， overhead and storage costs. The resulsts show that G?HLLS has good scalability in MANET with group mobility.

Keywords： MANET； G?HLLS； HLLS； OPNET

移动Ad Hoc网络（Mobile Ad Hoc Network，MANET）在国民经济的多个领域都有着十分广阔的应用前景。可扩展性路由协议的设计多年来一直是MANET研究中的一项关键内容。基于地理位置的路由协议具有良好的可扩展性能，而地理位置路由必需位置服务协议支持，因此可扩展位置服务协议的研究成为近年来MANET领域内学者们普遍关注的重点和热点。

1 国内外现状

国外学者较早开展针对位置服务协议的研究，并已经进入一定的深度，主要分为基于洪泛和基于团体两大类。早期的研究成果多为基于洪泛的，DLS[1]是这一类的代表。近期的研究多为基于团体类型，GLS[2]、XYLS[3]、GHLS[4]是三个典型代表，当前很多位置服务协议都从中借鉴了一些思想。总体来说，基于团置服务器的设计核心在于研究位置服务器的征召算法，上述各协议的根本区别也在于此。优秀的征召算法能够保证节点征召较少的位置服务器，就能够达到较好的位置服务成功率及准确率。

国内对于位置服务协议的研究相对较少，大部分研究成果是在已有经典协议的基础上做改进扩充。如MHRLS[5]（MultipleHome Regions based Location Service）、GrLS[6]、HFPT[7]（Hierarchical Forwarding Pointer with Thresholds）。还有学者独创性地利用分簇机制在可扩展性方面的优势解决位置服务问题[8?9]，如KCLS[8]。

国内外目前已经出现了针对不同应用环境的多种形态位置服务。但是这些位置服务大多在传统服务模式之上改进而来，在可扩展性方面并未取得明显的突破，当网络规模增大时，协议的性能将恶化。主要存在的问题可以归结为：

（1） 协议机制过于复杂；

（2） 位置更新负载重；

（3） 网络负载极度不平衡；

（4） 大部分位置服务协议都未考虑节点群组移动的特点。

2 基于历史信息的轻型位置服务协议HLLS简介

HLLS[10?11]（History information based Light Location Service）打破了上述位置服务算法传统格局，创新地基于历史信息对接点位置进行追踪。在HLLS中，一个节点可以征召任意节点为自身的位置服务器，并且为每一条位置信息关联时间戳，记录该信息被更新的时间。因此对于某单个节点，在其移动过程中，向沿途遇到的任意其他节点更新自身当前位置信息，并保存当前位置记录时间，从而使得不同节点所保存的位置信息新鲜程度不同。当其他阶段需要请求该节点位置信息时，则沿着位置信息的时间梯度，由较为陈旧的位置信息开始逐渐追踪到该节点的最新位置信息，完成最终的位置请求。位置更新的过程利用邻居节点之间周期发送的Hello包完成（邻居节点周期交换Hello包被大部分MANET网络采用，用于维护网络连通），因此HLLS算法开销很小，并且位置服务准确度高。

3 面向群组移动的位置服务协议

HLLS协议设计没有针对任何特殊的场景，但是群组移动的特性广泛存在于灾后救援、战场通信等大规模移动Ad Hoc网络应用场景[6]，为了提高位置服务协议在大规模群组移动性MANET中的可扩展性，利用分簇机制管理群组，在基于历史信息的轻型位置服务框架中引入群组移动特性，设计出面向群组移动的位置服务协议（Group mobility oriented HLLS，G?HLLS）。

3.1 网络模型

3.1.1 G?HLLS协议位置信息定义

在G?HLLS协议设计中，网络节点划分为簇首、簇成员两种类型，因此位置信息也分为两种类型。簇首节点位置信息包括：位置坐标、速度、时间戳、成员列表4项元素。簇成员节点的位置信息包括：位置坐标、时间戳。

3.1.2 G?HLLS协议群组移动模型定义

在G?HLLS协议所针对的群组移动中，全部网络节点划分为多个群组，每个群组中存在一个群首节点。同一群组中的节点共同移动，群首节点决定移动的方向和速度，群组中其他成员移动速度、方向与群首相同，因此同一群组具有相似的位置轨迹。具体定义如下：

群首节点：执行Random Waypoint移动模型的算法，即从初始位置开始，在网络区域随机选定一个目标位置，在[1，Vmax] m/s之间随机选取一个移动速率，然后以选定的速率向目标位置移动。但到达目标位置后需要等待同一群组成员均到达预定目标，然后再进行下一轮目标选择。

普通节点：从初始位置开始，在以群首目标位置为圆心、λR为半径的圆域内，随机选取一点为目标位置，以群首速率为移动速率，向选定的目标位置移动。到达目标后等待，直至同群组的全部节点到达预设目标后，再进行下一轮目标选取。此外普通节点还需要周期性更换簇首。

3.2 面向群组移动的轻型位置服务协议

3.2.1 G?HLLS协议思想概述

G?HLLS依赖HELLO包进行位置更新，位置请求机制核心也采用基于历史信息追踪对目的节点的追踪形式，但由于单个节点维护的信息量减少，位置更新、位置请求的具体机制在HLLS算法的基础上改进。图1显示了G?HLLS协议的主要思想。G?HLLS协议将面型群组移动的位置服务与分簇机制相结合，同一移动群组的节点组成一个簇，并且该移动群组的群首节点作为本簇的簇首，负责收集维护簇内成员的位置信息。

图1 G?HLLS协议思想示意图

在G?HLLS协议中，每个节点本地位置数据库只保存各簇首的位置信息，如图1所示灰色节点，颜色越深节点所保存的信息时间戳越新。因此对簇首节点的位置请求，可以直接基于分布式簇首位置数据库中的历史位置信息对其进行追踪。但是对簇成员节点的位置请求需要转化为对其所在簇簇首节点的追踪，并由簇首节点将位置请求包转交给被请求成员。但簇成员节点可能更换簇，因此对簇成员的位置请求过程，需要随时检查该节点是否已经离开原簇、加入新簇，这一过程称作双指针追踪。图1举例显示了对Dn节点的位置请求路径（图中省略了与本次位置请求无关的网络节点）。Dn原本属于簇首C1所在簇，后加入簇首C2所在簇。源节点Sn发起对Dn的位置请求，根据本地存储历史信息认为Dn属于C1所在簇，因此将位置请求包发往簇首C1，这一阶段按照基于历史信息的目标追踪策略转发位置请求包。节点Pn曾经与簇首C2在L0位置相遇，获知Dn已经加入C2所在簇，因而当节点Pn转发位置请求包时，不会再向C1发送，转而发往C2的历史位置L0。诸如Pn这样的节点称作簇指针节点，能够指示目的节点的簇首变更情况。从Pn发往C2这一阶段，继续遵照基于历史信息的目的追踪策略转发位置请求包，其中参与了请求包的转发并且能够指示目的簇首新位置坐标的节点称作簇首位置指针节点，类似于HLLS协议中的指针节点。跟随簇首位置指针节点的引导，位置请求包被发送给簇首C2，C2再转交给目的节点Dn，Dn将其当前位置信息通过贪婪路由直接返回给源节点Sn，最终完成此次位置请求及响应。

为了支持上述G?HLLS服务机制，簇首及簇成员节点需要保存并维护一定的信息，下面分类具体介绍。

（1） 簇首节点需要维护：

① 邻居列表（NT），保存当前邻居ID及位置信息；

② 本地位置数据库（LLDB），保存网络中全部簇首ID及位置信息；

③ 簇成员列表（MT），保存本簇当前全部成员ID及位置信息。

（2） 簇成员节点需要维护：

① 邻居列表（NT），保存当前邻居ID及位置信息；

② 本地位置数据库（LLDB），保存网络中全部簇首ID及位置信息。

G?HLLS协议主要分为四个部分：首先执行协议初始化机制在各节点建立LLDB；然后对LLDB 进行日常位置更新；当源节点需要请求目的位置信息时触发位置请求及响应机制；位置请求失败则转入请求恢复机制。

3.2.2 协议初始化

G?HLLS协议初始化机制的任务是保证全部网络节点建立起本地位置数据库LLDB，其中保存了网络中全部簇首节点ID及簇首位置信息，因此每个簇首节点需要将自身信息散布全网。为了实现该目标，G?HLLS基于传染病算法思想实现低负载、可靠的多播，每个簇首节点将自身的ID及位置信息散布给其他簇首。

在G?HLLS协议初始化过程中，每个节点（无论簇首还是簇成员）首先通过簇首节点在直接邻居范围内广播的HELLO包收集簇首位置信息，即如果收到簇首节点发来地HELLO包，则将其中的位置信息插入LLDB。当LLDB中新增记录数目超过Ngossip之后，则将新增记录的簇首ID形成列表作为Gossip信息捆绑在HELLO包中广播出去，同样把这种特殊的HELLO包称作HELLO_GP。邻居节点收到HELLO_GP则检查其中是否存在本地LLDB还未保存的簇首ID，如果有，则单播发送缺失请求包MREQ包给HELLO_GP源节点，从而请求缺失的簇首信息；HELLO_GP源节点收到MREQ，则单播返回MREP，返回被请求的簇首位置信息。这一过程在全网范围内以分布式的方式重复，则最终每个簇首位置信息能散布到网络中其他簇首并被保存。

3.2.3 位置更新机制

G?HLLS协议的位置更新机制包括两部分：局部位置更新、全局位置更新。局部位置更新限制在簇内，即簇首对本簇成员的位置信息维护。全局位置更新主要任务是对各节点LLDB进行更新，即在全网范围内更新簇首节点的位置信息。

（1） 局部位置更新

根据群组移动模型的定义，每个群组成员（即簇成员节点）在选择下一移动目标时已知群首（即簇首节点）的目标位置及移动速度，并且所有节点采用匀速直线运动向着移动目标靠近。簇成员节点能够根据匀速直线运动公式计算任意时刻本簇首的位置坐标，因此局部位置更新的任务仅为实现簇首对全部簇成员的位置信息实时可知。

局部位置更新要求在每个簇内，簇成员节点周期性地向簇首节点单播发送成员位置更新包（Member Location Update Packet，MLUP）。MLUP中包含簇成员自身ID及位置信息二元组（即当前位置坐标、时间戳），MLUP的路由通过贪婪转发方式实现。簇首节点收到位置更新包，则将其中包含的ID及位置信息插入或更新本地成员列表。

（2） 全局位置更新

全局位置更新的任务是实时更新全网范围内各节点的LLDB。G?HLLS协议借助HELLO包、DATA包及LRP包中的位置信息对LLDB进行捎带更新。具体说明如下，任意节点在以下三种情况下进行全局位置更新：

① 当节点收到HELLO包，如果源节点为簇首节点，则利用HELLO包携带的簇首ID及位置信息四元组对本地LLDB及邻居列表NT同时进行更新；如果源节点是簇成员，则仅利用HELLO包携带的成员ID及位置信息二元组更新NT。

② 当节点收到DATA包，如果源、目的节点至少有一个为簇首节点，则利用相应的簇首ID及位置信息四元组对本地LLDB进行更新，然后将DATA包转发出去；如果源、目的节点都为簇成员，则不做更新，直接转发出去。

③ 当节点收到LRP包，如果包中源信息为簇首节点，则利用该簇首节点的ID及位置信息对本地LLDB进行更新，然后将LRP转发出去；如果源信息不是簇首，则不做更新，直接转发出去。

LLDB的具体更新算法为，利用HELLO/DATA/LRP包中簇首ID搜索本地LLDB，找到该ID所对应记录，对比包中簇首位置信息时间戳与找到记录的时间戳，如果包中信息的时间戳较新，则用包中簇首位置信息代替找到的本地记录，否则不操作。

3.2.4 位置请求及响应机制

G?HLLS协议初始化及位置更新机制在全网范围内的LLDB建立起簇首节点的分布式位置数据库，并且其中的位置信息呈现梯度的时间戳。基于这样的分布式簇首位置数据库，能够直接利用HLLS协议的基于历史信息的追踪机制实现对簇首节点的位置请求，而对簇成员节点的位置请求将由其所在簇簇首，转化为对其簇首的位置请求。为了实现上述过程，需要请求源节点发起位置请求包（Location Query Packet，LQP），将LQP发送至被请求的目的节点；目的节点收到LQP则发起位置响应包（Location Reply Packet，LRP），将自身当前位置信息返回给请求源节点。任意节点对簇首节点的位置请求可以按照HLLS协议的位置请求算法执行，下面详细介绍对簇成员节点的位置请求算法。

同样以一对请求源、目的节点为例进行说明，Snode为网络中任一请求源节点，Dnode为被请求的目的节点，且Dnode为簇成员节点，对Dnode的位置请求算法步骤如下：

Step1： Snode生成LQP包，将自身ID及位置信息填入LQP作为源节点信息，根据Dnode的ID搜索LLDB找到Dnode所属簇首位置信息记录，将Dnode的ID、其簇首ID及位置四元组填入LQP，目的节点位置信息字段不填写，然后将LQP发往目的簇首，利用目的簇首位置根据贪婪转发机制计算路由下一跳。

Step2： 任意节点i收到LQP包，利用Dnode的ID搜索本地LLDB，检查Dnode是否更换簇首：

（1） 如果更换，则将Dnode新簇首ID、位置信息四元组填入LQP，然后根据贪婪转发机制计算路由下一跳，将LQP发往新簇首；

（2） 如果没有更换，则对比LLDB中的Dnode簇首信息与LQP包中簇首信息时间戳；

（3） 如果LLDB中簇首信息时间戳较新，则将LLDB中找到的Dnode簇首位置四元组填入LQP，然后根据贪婪转发机制计算路由下一跳，继续将LQP发往目的簇首；

（4） 如果LQP包中簇首信息时间戳较新，则用LQP包中簇首位置四元组更新LLDB的记录，然后根据贪婪转发机制计算路由下一跳，继续将LQP发往目的簇首；

（5） 重复Step2，直至LQP的目的簇首ID字段所指示节点接收到LQP，则转Step3。

Step3： LQP的目的簇首ID字段所指示节点接收到LQP，则用Dnode的ID检索本地成员列表，检查自身是否为Dnode当前所属簇首：

（1） 如果是，则将成员列表中Dnode位置信息二元组填入LQP包的目的节点位置信息字段，通过贪婪路由直接将LQP发往Dnode；

（2） 如果不是，则转Step2。

Step4： Dnode收到LQP包，则生成LRP包，将自身ID及当前位置信息二元组填入LRP包作为源信息，将LQP所携带Snode节点ID及位置信息填入LRP作为目的信息，然后根据贪婪转发机制计算路由下一跳，将LRP直接发往Snode。

Step5： 任意节点i收到LRP，Dnode为簇成员节点故不做捎带更新，直接根据贪婪转发机制计算路由下一跳，将LRP发送出去，重复Step5，直至LRP被Snode接收。

Step6： Snode接收到LRP，获得LRP所携带Dnode位置信息二元组，则完成此次位置请求及响应。

3.2.5 位置请求恢复机制

在上述G?HLLS位置请求机制中也可能出现追踪困境，即LQP已经到达目的簇首位置字段所指示区域，且在转发节点本地LLDB无法找到目的簇首更新的历史位置，则无法继续转发。G?HLLS协议的簇首位置信息包含了四个元素：位置坐标、速度、时间戳和成员列表。因而可以利用簇首的历史位置坐标、速度及时间戳对目的簇首的新位置进行预测，然后将LQP通过贪婪路由发往目的簇首的预测位置，在这一过程中可以继续重复第3.2.4节位置请求算法步骤中的Step2，恢复对目的簇首的追踪。

4 G?HLLS节点存储开销分析

从上述G?HLLS协议说明可以看出，只有簇首节点位置信息参与协议初始化、全局位置更新，与HLLS协议相比，有效削减了单个节点维护信息，降低了节点存储开销。为了验证G?HLLS对HLLS协议存储开销的优化效果，本节将对G?HLLS、HLLS协议平均存储开销进行理论分析；同时参与分析的还包括GLS及GREASE，进一步将G?HLLS、HLLS的存储开销与其他位置服务进行对比。在以下分析中，假设网络中包含N个节点。

在HLLS协议中，每个节点需要保存网络中其他全部节点的位置信息，因此本地位置数据库中需要包括网络所有节点的记录，存储开销为O（N）。

在G?HLLS协议中，假设群组移动模型中各群组规模为a。本地位置数据库LLDB中包含全部簇首节点位置信息，记录数目为[Na]。簇成员节点只需维护LLDB，但簇首节点同时需要维护LLDB及簇成员列表MT，MT包含本簇全部成员位置信息，记录数目为a。因此，G?HLLS协议平均每个节点需要维护位置信息记录数目用公式表示为：

[NaN-Na+Na+aNaN=Na+1]

则G?HLLS协议平均节点存储开销为O（[Na]+1 ）。在GLS协议中，每个节点的位置信息记录需要保存在3log4 （N）个位置服务器之上[4]。并且GLS协议选举位置服务器采用的分层哈希函数保证了位置服务任务在各节点之间均衡分布，即每个节点保存的位置信息记录数目均衡，因此GLS协议节点平均存储开销[11]为O（log N）。

在GREASE协议中，每个节点保存曾经与自身相遇的其他节点位置信息，在网络节点整体移动性较弱的情况下，每个节点只能遇到较少数目的节点，相应地节点存储开销也较小；反之存储开销较大。在存储开销最大的情况下，每对节点曾经相遇并相互保存位置信息，则GREASE平均节点存储开销为O（N）。但实际GREASE存储开销越大，其位置服务成功率越高。

从表1可以看出，GLS协议存储开销较小，G?HLLS协议存储开销中等，HLLS及GREASE协议存储开销较大。但存储开销对服务协议性能的影响相对较小，与其他几个协议相比，HLLS及G?HLLS协议的低负载、高位置服务成功率使得它们具有更优的可扩展性，综合性能相对较好。

表1 位置服务存储开销比较表

5 G?HLLS协议性能的仿真分析

本小节基于OPNET仿真，将G?HLLS协议与HLLS协议性能进行了对比分析，分析G?HLLS协议对HLLS协议的改进情况，从而证明G?HLLS协议在大规模群组移动MANET中具有更好的可扩展性。

首先介绍了仿真参数及性能评价参数。以公平对比为原则，所有仿真实验采用仿真参数如表2所示。为了分析对比G?HLLS协议与HLLS协议的可扩展性，将这两个协议分别运行在不同的网络规模下，网络规模从500个节点变化到1 600个节点，同时保持网络密度不变，即保持平均节点度为7，则正方形的网络区域边长需要根据网络规模而相应变化。在实验过程中，主要统计的性能参数为平均位置请求成功率：即成功接收的位置响应包数目与发起的位置请求包数目比值。为了对比公平性，位置请求不会重传，位置服务成功率均为第一次服务成功率。

表2 仿真实验参数表

图2显示了位置服务成功率随网络规模变化的情况。随着网络规模的扩大，G?HLLS协议与HLLS协议位置位置服务成功率都呈下降趋势，但G?HLLS协议位置服务成功率的下降速率明显比HLLS协议更缓慢。当网络规模小于1 000个节点时，G?HLLS协议位置服务成功率比HLLS协议较低。因为网络规模小于1 000个节点时，初始化负载对HLLS协议的负面影响不明显。

图2 位置服务成功率随网络规模变化实验图

初始化结束之后，除利用HELLO包进行全局位置更新，G?HLLS协议还需要额外进行簇内局部更新，G?HLLS协议的日常负载比HLLS协议稍大；并且G?HLLS的本地位置数据库信息量明显小于HLLS协议，位置信息的散布较HLLS协议不够充分，上述多方面原因使得G?HLLS位置服务成功率在规模较小的网络中低于HLLS协议。但随着网络规模增长大于1 000节点，HLLS协议初始化负载过大的问题暴露，拥塞冲突等原因使得本地位置数据库建立不完备，即节点可能丢失一些其他节点的初始位置信息，并且网络范围较大，这些节点长时间不会相遇进行位置更新，位置信息缺失较多造成位置服务成功率明显下降。但G?HLLS协议本地位置数据库需要保存的信息较HLLS协议明显减少，初始化负担不会过重，因此位置服务成功率缓慢下降，持续保持较高的服务成功率。

6 结 语

为了适应大规模MANET网络呈现的群组移动特性，同时从降低协议存储开销和初始化负载的角度对HLLS协议进行优化，本文提出了面向群组移动的轻型位置服务协议G?HLLS。G?HLLS将HLLS协议框架与分簇机制相结合，照顾群组移动性的同时，将位置服务协议分层执行。簇首节点负责局部位置更新，将大量簇成员的位置更新限制在较小范围，有效削减了本地位置数据库的存储开销；在位置请求阶段，簇首节点作为被请求簇成员的，执行基于历史信息的双指针位置追踪。基于OPNET仿真实验对G?HLLS和HLLS进行了性能对比分析，验证了G?HLLS协议能够以较低的存储开销、控制负载保持较高的位置服务成功率，在大规模群组移动网络中表现出优越性能。

参考文献

[1] BASAGNI S， CHLAMTAC I， SYROTIUK V R， et al. A distance routing effect algorithm for mobility （DREAM） [C]// Proceedings of The 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking （MOBICOM）. Dallas， USA： ACM Press， 1998： 76?84.

[2] LI J， JANNOTTI J， DE COUTO D S J， et al. A scalable location service for geographic Ad Hoc routing [C]// Proceedings of The 6th Annual ACM International Conference on Mobile Computing and Networking （MOBICOM）. Boston， USA： ACM Press， 2000： 1?11.

[3] STOJMENOVIC I， VUKOJEVIC B. A routing strategy and quorum based location update scheme for Ad Hoc wireless networks [R]. Ottawa： University of Ottawa， 1999.

[4] DAS S M， PUCHA H， HU Y C. On the scalability of rendezvous?based location service for geographic wireless Ad Hoc routing [J]. Elsevier Computer Networks， 2007， 51 （13）： 3693?3714.

[5] 王国军，蔺英俊，贾维嘉.移动自组网中一种面向群组移动性的位置服务协议[J].小型微型计算机系统， 2007， 28 （2）： 210?214.

[6] CHENG H， CAO J， CHEN H， et al. GrLS： group?based location service in mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2008， 57 （6）： 3693?3707.

[7] 李皓，李德敏，蔡元正.一种引入阈值的Ad Hoc网络分级转发指针的位置管理策略[J].传感器与微系统， 2008， 27 （1）： 33?35.

[8] LENG S， ZHANG L， FU H， et al. A novel location?service protocol based on k?hop clustering for mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2007， 56 （2）： 810?817.

[9] 阎新芳，刘爱琴，杨挺.基于极小独立支配集的MANET虚拟骨干网算法[J].电子学报，2007，35 （6）： 1134?1138.

[10] YANG Xin?yu， FAN Xiao?jing， YU Wei， et al. HLLS： a history information based light location service for MANETs [J]. Computer Networks， 2012， 56 （2）： 731?744.

[11] MAUVE M， WIDMER A， HARTENSTEIN H. A survey on position?based routing in mobile Ad Hoc networks [J]. IEEE Networks， 2001， 15 （6）： 30?39.