无线网络位置管理中的一种用户聚合算法

赵 聪，郭 伟

(电子科技大学通信抗干扰技术国家级重点实验室 成都 611731)

在无线网络中，位置管理主要是使网络能在呼叫建立时定位用户终端的当前位置，它包含两方面内容，定位(又叫位置更新)和呼叫(又叫位置查询)。在位置更新过程中，用户周期性或当用户移动到新位置区时向系统报告其位置，使系统相关数据库及时更新该用户位置信息；在呼叫建立过程中，系统访问相关数据库以获得用户当前所在位置区，同时利用寻呼过程确定用户所在的具体位置。因此，减少位置更新的代价或减少寻呼的代价都可以提升系统的性能。但是这两者却是矛盾的：如果位置更新开销越大，用户的位置知道得越精确，寻呼开销就越低；相反，如果定位开销越低，则寻呼开销就越高。要降低系统位置管理的信令开销，需要在定位和寻呼之间达到一个最佳的折中[1-3]。

在3种基本的动态位置管理策略(基于时间[4]、基于移动[5]和基于距离[6])中，基于距离的位置管理策略已被证明是最优的[7]，很多研究都旨在对其进行实现、优化和改进。其中的一种思路是对用户终端进行分类，对不同特征(用户移动速度和呼叫到达率)的用户进行不同的管理策略，从而进一步降低位置管理的系统总开销[8-12]，但是该思路下无法运用用户之间的一些相关性，从而常进行很多重复性操作，造成了资源的浪费。另外有学者提出一种树形的全分布式位置管理数据库[13]，其结构利用了用户移动中位置区相邻的特点，但该方法在用户远距离移动时性能并不好，而且系统过于复杂，所以并没有得到很好的使用。近年来，很多学者提出了移动子网(NEMO)的解决方案，运用纵向切换、移动代理的方法[14-16]，大大提高了系统的整体性能，但该方案需要增加移动路由器等网络设备，成本投入较大，并且在用户进入和离开移动子网时系统的操作也比较复杂。

本文借鉴移动子网的一些特点，提出了一种位置管理的用户聚合算法。该算法在不改变现有网络结构的情况下，利用简单的指针处理，就可以充分利用用户之间的相关信息，大大降低了系统的重复操作，并可与已有的各种优化算法同时使用，互相不冲突，在已有的优化算法上进一步提升了系统性能。

1 传统的位置管理方法

目前广泛使用的传统位置管理方法，采用2层数据库结构和位置区划分的方式，即系统将网络分为若干位置小区，每个小区由一系列蜂窝组成，每个小区对应一个访问数据库(VLR)，存放用户当前的位置信息，系统设置一个用户归属数据库(HLR)，存放用户的所有信息，特别是指向用户属于哪个VLR的信息。当移动用户移动到新的小区后将进行位置更新，在新的VLR中进行注册，新VLR向HLR报告移动用户新位置信息，同时HLR通知旧VLR删除用户的信息；当有呼叫时，通过查找HLR中的信息，传递呼叫到用户所在的VLR，建立呼叫，如图1所示。

图1 传统位置管理方式

但是，当有很多用户的移动特征相同时，如在汽车、火车、飞机等公共交通上，用户具有相同的地理位置和移动特性，如果按照传统处理方式，所有用户的位置更新信息将是相同的，这必然带来大量冗余。在图1中，3个用户进行相同的移动就进行了3次相同的操作。

2 用户聚合算法

2.1 用户聚合算法基本思想

用户聚合算法的基本思想是：当具有相同移动特征的用户组成一个群(逻辑群)时，在群中选择一个用户作为群首，其他用户在归属数据库中写入指针指向群首。当用户群移动时，只有群首用户进行相关的位置更新处理，而其他用户不做任何处理，这样就大大减少了冗余的重复操作；当有呼叫到达，系统查询被叫用户时，通过指针指向访问群首用户的记录，然后直接寻呼被叫用户，由于被叫用户和群首用户处于同一位置，所以不会增加额外的信令开销。

2.2 群首用户

本文所提算法的核心是由选定的群首用户信息代替所有的用户信息，所有的位置管理相关操作也全部由群首用户代劳。理论上，任意选择群首用户都可以达到减少重复操作的目的，但事实上，群首用户和群的一致性越大，性能改善越明显。如果群首用户选择不当，用户入群操作和离群操作带来的额外开销，特别是群首用户离群进行的更换群首开销，甚至会高于减少的重复操作开销。所以，在具体实现时，选用公共交通工具绑定的通信终端作为群首用户，如车载或机载的终端。而这些选定的群首终端可以很容易地实现群内的小范围广播功能，方便普通用户确定何时进行入群和离群操作。

由于用户信息比较复杂，除了移动特征外，对系统性能影响比较大的参数还有呼叫到达率等，在设置群首用户的操作参数(如更新频率)时，可以将这些纳入考虑。本文为了仿真实现的方便，在对群首用户的参数选取时没有考虑呼叫到达率等参数。

2.3 用户聚合算法具体处理流程

2.3.1 入群更新过程

当用户进入群(将具有与群相同的移动特征)，收到群首用户的消息(如用户进入飞机接收到机载终端的群内广播消息)后，将向网络发起一个位置更新处理流程，在其所属的VLR中删除相关信息，然后在其HLR中写入指针，指向群首(机载终端)在HLR的位置。群首用户保持自己正常的位置管理操作，而普通用户进入群移动模式，将不再进行任何位置更新方面的操作。

2.3.2 位置更新过程

当用户群移动到一个新的位置区时，将进行位置更新过程。对于群首用户，其操作方式和传统的位置管理方法中的位置更新处理流程完全相同；而其他的非群首用户则不做任何更新处理。相比之下，用户聚合算法的位置更新处理只有一个用户进行了操作，比其传统方法所有用户都进行操作，系统开销将大大降低。

2.3.3 寻呼过程

当呼叫到达时，系统访问被叫用户的HLR，由于入群过程中写入了指针，系统可以找到群首用户所在，然后查询群首的VLR位置，并直接向群首所在位置寻呼被叫用户。由于被叫用户和群首处于同一位置，所以呼叫可以直接成功建立。与传统位置管理处理方式相比，只增加了一次HLR在本地的查询过程，代价不大。

2.3.4 离群更新过程

当用户离开群(不再具有与群相同的移动特征)后，如飞机降落后，用户离开不再收到机载终端的群内广播信息，将发起一个位置更新过程，用户在其现今所属VLR进行注册，VLR向HLR报告用户信息，同时HLR将指针删除重新写入的新的VLR信息。

2.4 用户移动模型

对于单个群来说,每隔一段距离将会到达一个“站”，沿线各站每站进出群的终端数会有所不同。对于任意终端，从某一站进群后，它有可能从任一站出群，但在每一站出群的概率不一样。设一条线有m站，其概率矩阵可以表示为[17]：

式中，pij为从第i站进，第j站出的概率。

3 场景与仿真结果

针对本文提出的算法，设置了3种网络场景。假设所有群移动的线路都比较平滑(不存在短距离往复)，用户终端在没有进入群的时候以5 km/h的速率步行前进，位置区半径为10 km。

由于用户聚合算法只对位置更新的有较大影响，而在寻呼阶段只有数据库本地多了一次查询带来的开销很小，实现该算法后整体系统性能的变化主要由位置更新时的系统开销决定，所以在仿真时，只对位置更新的性能做比较。

与现有优化算法的性能比较，采用文献[10]使用的模型，按速率将用户分成高速、中速和低速3类用户，对每类用户设置不同大小的小区半径。民航飞机场景的用户群使用高速用户的设置，长途客运场景的用户群使用中速用户的设置，市内公共交通场景的用户群使用低速用户的设置。

3.1 民航飞机场景

设置一架飞机载客200人，不考虑乘客与飞机相互干扰的情形，飞机速率900 km/h，飞行距离10 000 km，仿真结果如图2所示。

从图2可以看出，不管是传统方式还是优化方式，使用了用户聚合算法后的系统开销均远远小于未使用时，原因在于聚合算法节省了大量的重复冗余信息。而且，随着用户的增多，距离的增长，可以预见，该性能的差别将会更大。

图2 飞机场景性能比较

3.2 长途客运场景

设置一辆长途客车，汽车载客30人，汽车速率80 km/h，移动距离200 km，其中在100 km处有用户上下车，仿真结果如图3所示。

图3 长度客运场景性能比较

从图3可以看出，使用了用户聚合算法的系统处理开销分别小于传统方式和优化处理方式，并且可以在使用优化算法对系统性能进行优化后进一步提升性能。但是在用户最初进行入群操作时的开销会有一个峰值，造成其开销高于传统方式和优化方式，但总体上，依然提高了系统性能。

3.3 市内公共交通场景

设置一辆城市公交车，移动速率40 km/h，每隔1 km处有用户上下车，仿真结果如图4所示。

从图4可以看出，用户聚合算法和传统的处理方式性能相差不大，而且在一开始的时候聚合算法的系统开销还要更高一些。这主要是由于用户之间的相关性已经不大，算法节省的系统开销和新带来的额外开销相差不多。

图4 市内公共交通运输场景性能比较

4 结 论

本文充分利用用户之间的相关性，借用移动子网的思路，利用简单的指针处理，提出了一种位置管理的用户聚合算法。仿真结果表明，该算法使系统在处理过程中减少了重复操作，节省了大量的系统资源。在用户相关性不大的城市公交系统中，该算法和传统算法性能相似。但在飞机、远洋轮船、长途客车等用户移动关联性很大的情况下，该算法可以大大提升系统性能，而且随着用户数量的增多，同行距离的增大，系统性能提升将更明显。

本文算法不改变现有网络结构，并可以同时使用已有的各种优化算法，大大提升了系统性能，具有很强的工程参考价值。除了民用网络以外，对于军队战斗单元接入军事网络等场景，该算法也有一定的参考意义。

[1] 李瑾, 罗汉文, 宋文涛. 第三代移动通信系统位置管理方式[J]. 电信快报, 1999, 3: 14-17.LI Jin, LUO Han-wen, SONG Wen-tao. Location management methods in third generation mobile system[J].Telecommunications Information, 1999, 3: 14- 17.

[2] AKYILDIZ I F, MCNAIR J, WANG W. Mobility management in next-generation wireless systems[J]. Proc IEEE, 1999, 87(8): 1347-1384.

[3] 陈山枝, 时岩, 胡博. 移动性管理理论与技术[M]. 北京:电子工业出版社, 2007.CHEN Shan-zhi, SHI Yan, HU Bo. Theory and technology of mobility management[M]. Beijing: Publishing House of Electronics Industry, 2007.

[4] ROSE C. Minimizing the average cost of paging and registration: a timer-based method[J]. ACM/Baltzer J Wireless Networks, 1996, 2(2): 109-116.

[5] AKYILDIZ I F, HO J, LIN Y B. Movement-based location update and selective paging for PCS networks[J].IEEE/ACM Tram Networking, 1996, 4(4): 629-638.

[6] HO J, AKYILDIZ I F. Mobile user location update and paging under delay constraints[J]. ACM/Baltzer J Wireless Networks, 1995, 1(4): 413-425.

[7] BAR-NOY A, KESSLER L, SIDI M. Mobile users: to update or not update?[J]. Wireless Networks, 1994, 1(2):175-186.

[8] HU L, RAPPAPORT S. Adaptive location management scheme for global personal communications[J]. IEEE Proc Commun, 1997,144 (1): 54-60.

[9] WANG Liang, ZHANG Nai-tong. Dynamic location update strategy in LEO systems[C]//VCT2003. [S.l.]: IEEE, 2003:878-882.

[10] 赵聪, 郭伟. 一种新的位置管理数据库结构[J]. 计算机工程与应用, 2008, 44(5): 28-30.ZHAO Cong, GUO Wei. New database architecture for location management[J]. Computer Engineering and Applications, 2008, 44(5): 28-30.

[11] NG C K, CHAN H W. Enhanced distance-based location management of mobile communication systems using a cell coordinatess approach[J]. IEEE Transactions on Mobile Computing, 2005, 4(1): 41-55.

[12] ZHAO Cong, GUO Wei, LIU Fang. An adaptive distance-based location management of LEO system using coordinates approach[J]. The International Journal for Computation and Mathematics in Electrical and Electronic Engineering, 2010, 29(2): 468-476.

[13] WANG J Z. A fully distributed location registration strategy for universal personal communication systems[J].IEEE J Select Areas Commun, 1993, 11: 850-860.

[14] MCCARTHY, B, JAKEMAN M, EDWARDS C.Supporting nested NEMO networks with the unified MANEMO architecture[C]//IEEE 34th Conference on Local Computer Networks. [S.l]: IEEE Press, 2009: 609-616.

[15] SHAHRIAR A Z M, ATIQUZZAMAN M, IVANCIC W.Performance evaluation of NEMO in satellite networks[C]//Military Communications Conference. [S.l]: IEEE Press, 2008: 1-7.

[16] TSAI C S. Designing a novel mobility management scheme for enhancing the binding update of HMIPv6 with NEMO environment[C]//International Conference on Future Networks. [S. l]: IEEE Press, 2009: 87-91.

[17] 欧冬秀, 董德存. 地铁中的移动通信终端位置管理模型[J]. 城市轨道交通研究, 2004, 1: 29-34.OU Dong-xiu, DONG De-cun. A terminal location management model for mobile network in metro[J]. Urban Mass Transit, 2004, 1: 29-34.