2004年 2月
第25卷 第2期
通 信 学 报
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
、b1．25 No．2
February 2004
个人通信位置管理的计时双位置算法
单志龙，韦岗
(华南理工大学 电子与信息学院，广东 广州 510640)
摘 要：提出了一种新的位置管理算法——计时双位置算法，从理论上导出了TTLA算法的总代
价函数，给出了传统 IS-41和双位置算法(TLA)的统～数学框架。通过性能分析可知，rrLA算法
能根据用户的呼叫移动比，在 IS-41和 TLA两者之间进行选择，综合性能好，且在某些情况下，
性能要超过另两种算法。
关键词：个人通信网：计时双位置算法：计时器：位置管理：位置更新；寻呼
中图分类号：TN929．53 文献标识码：A 文章编号：1000．436X(2004)02．0026—07
Time-two location algorithm for
location management in a PCS network
SHAN Zhi—long，WEI Gang
(Department of Electronics＆ Information Engineering，South China University of Technology，Guangzhou 5 10640。China)
Abstract：A novel TrLA and its cost function are proposed to get an uniform frame of the IS-41 and
TLA．The study an d the data analysis indicate that TrLA Can switch between IS-41 an d TLA according
totheCMRoftheusers andit Can outperform b0m ofthealgorithmsin some conditions．
Key words：PCS；TrLA：timer；location management；location update；paging
1 引言
在个人通信网中，移动用户的每一次通信不仅要及时准确地传送，而且要以最小的代价
完成。为给每个用户提供通信服务，系统必须跟踪每个用户的移动，以便在有通信需求时能
准确地定位该用户，因此用户的位置管理是移动通信领域中一类十分重要的问题l】～。
传统的 IS一4l和 GSM 系统引入了位置区管理方式，即一个位置区由若干个小区组成。每
次寻呼消息在该移动用户所在的位置区内广播，移动用户只有跨越位置区时，才进行位置更
新 (LU。location update)。如不作特殊说明，本文提到的区、小区指的都是位置区。
当呼叫移动比 (CMR。call—to．mobility ratio)较大，即用户移动性较小而通信业务又很多
时，由于需要及时定位用户，所以传统的方案是一个比较好的方法。文献【4】中提出了基于局
收稿 日期：2002．06-19；修订 日期：2003．09．26
基金项目：国家教育部博士点专项基金资助项 目 (20010561007)
维普资讯
第2期 单志龙等：个人通信位置管理的计时双位置算法
部区域的位置管理策略，在 CMR稍高时也表现出一定的优势。而当CMR较小，即用户业务
量较少而移动性较高时，用户每进入一个新区都进行一次更新，会产生大量冗余信息；另外，
用户在小区边界处的乒乓 (ping．pong)移动也会使得用户需要跟两个归属位置寄存器 (HLR)
不断交换信令，从而消耗了很多信令，此时应尽量避免位置更新，于是传统方法不再适用。
为此，近年来许多位置管理改进算法被提出。例如，基于两个位置区的 TLA(two location
algorithm)算法p J、利用三个位置区来减少更新的TrLA (three location area)算法【61、通过用
户和访问位置寄存器 (VLR)的协同作用使 VLR分担部分 HLR负载的 k．位置转迹算法【1 、
根据移动台的移动和呼叫情况采用不同级别的位置区的算法 】、基于分布式数据库结构的分
布式位置管理策 、利用用户移动特性来预测用户可能出现的位置的算法【l o]等等。
TLA等算法虽然在 CMR较小时优于 IS．4l算法，但当CMR较大时性能却比IS．4l算法
差。Lin指出，寻求一种算法来结合 TLA和 IS．4l，使其能根据用户的移动性来调整选择这
两种算法是以后研究的重点I 。本文提出了一个基于时间的计时双位置算法(TTLA，time．two
location algorithm)，该算法可以把TLA和 IS．4l的数学表达式统一起来，而且根据用户的移
动性可以调整选择这两种算法，在某些 CMR情况下，其性能超过了这两种算法。
2 TTLA算法描述
TLA算法中位置更新和寻呼过程的描述如图 1所示。
@ @
③一③
(no action)
(b) (c) (d)
图1 双位置算法
在图 l(d)中，当用户返回尺1时，系统根据用户 HLR中位置表信息在尺2中寻呼用户，在
尺2中找不到用户时再在尺l中寻呼，这样做会使寻呼成功率较低。为提高寻呼成功率，就要进
行位置更新，让系统知道用户已在尺1中，但频繁的更新又会使系统不堪重负。
1] A算法的基本思想是在 TLA的基础上，引入一个计时器来提高寻呼成功率。每个用
户的终端都含有一个计时器，当用户在小区间往返移动时，利用计时器来计算用户在位置区
中所待的时间。在此算法中，计时器是否开始计时、用户是否进行更新由以下几种情况决定：
1)当用户位置表与HLR位置表相同时，计时器不启动，如用户从尺1返回R2；
2)当用户位置表与 HLR中的位置表不一致时，计时器启动并开始计时，如图 l(d)所示，
用户从尺2返回尺1。
1] A算法较 TLA算法的优势在于：通过合理设置计时器定时丁，使用户在边界乒乓移
动时，可避免频繁的位置更新：而当用户返回位置区且在该位置区停留较长时间时，又可及
田 田
P
维普资讯
通 信 学 报 2004笠
时更新以避免两次寻呼。因此预设时间丁的选择就显得尤为重要。
假设预设时间最大临界值为 。对不同的丁值，给出下面的结论：
1)当 ≥ 时，此时的算法就是 TLA算法；
2)当 T--0时，此时的算法类似于IS一4l，但还是要优于 IS一4l。因为计时时间为0，所以
用户进行诸如从尺2返回尺l的移动时必须进行更新。但当用户进行诸如从尺l返回尺2的移动时，
由于没有启动定时器，所以不用更新也能准确定位；
3)当0<T<To时，在某些 CMR值的情况下，TTLA算法比另两种算法要好。
3 TTLA的模型
按照文献【5】中的约定，可以假定：
1)每进行一次基本寻呼操作和在 TLA与 TTLA系统中第一次寻呼就找到用户操作的代
价为 1；
2)每进行一次更新操作的代价为 ，其中O．2≤ ≤O．8；
3)在 TLA与 TTLA系统中，如果因为第一次没有找到用户而进行两次寻呼以找到用户
的代价为 l+(1一 )。
用 ， 和C分别表示系统更新、寻呼和总的代价函数， 为呼叫移动比。用 分别
表示在 TLA和 TTLA中第一次寻呼没找到用户的概率。在 TLA中，用缘 示用户返回位置区
的概率，从尺l返回尺2时系统不会错过用户，错过用户的概率只会出现在从 尺2回到 尺l时。假
定用户移动是随机的，分布是均匀的。因此不妨假定从尺2回到尺l和从尺l返回尺2的概率是相
等的，即缈= 。通过数值分析发现，这样的假定是合理的。在 TTLA 中，用 表示从 尺l
返回 尺2时不用更新的概率，由上面的分析可知， = ；用 ( )表示从 R2回到 RI时不用
更新的概率，它是选定时间丁的函数，不难看出o< ( )≤ ，且 ：a2(T)。 a2(T)： 0
时，所得到的丁值就是最大临界值 。
在文献【5】中已经求得IS一4l和 TLA的总代价函数为
cIs．4l= ．IS_4l+ 4l= +l (1)
P
： Cu
,
TAL+Cp．TLA：(1 +(1+(1 ) (2)
当丁=o时，用户在进行从尺l返回尺2这样的移动时没有启动定时器，所以无需更新。而
在其他情况下都要进行更新，所以，类似(1)、(2)的求法可以得到3TI'LA(T=o)的总代价函数
丌LA =
，丌IA+ 耶A=(1一导) +l (3)
当 0<T~To时，根据一个给定的T来确定02(T)的值是比较复杂的，因为这与用户的移
动性、速度和用户在小区中的逗留时间等有关。图2是一个用户进入位置区的移动模型，用
户从 A点进入，沿着线路 ABC移动， 是用户移动方向与法线方向的夹角。这里，作如下
假定：
维普资讯
第2期 单志龙等：个人通信位置管理的计时双位置算法
A
图 2 位置区移动模型
1)用尸以V=20km／h的速度作匀速直线运动，位置区是一个半径 R=3000m的圆：
2)用户在时间T内最多只进行一次往返，且 B点在AC上服从均匀分布。
由文献[1l】可知， 的概率密度函数为
，( )：
1
COS 一詈< <詈 (4)
【0 其它
因为AC=2Rcosfl，AB=x，故由假设2)可得如下条件概率密度函数
-{ 2Rcosfl 2 os (一号< < (5)
【0 其它 一 。
由式(4)和式(5)可得X和 的联合密度函数
( j去一号< <詈0<x<2Rcos (6)
l0 其它
于是，( )的概率密度函数为
-J囔 =去一 x 0<x<2R
0 其它
上式定积分上下限的取值是 由于取定移动距离为X后，夹角 所能取到的最大值满足
cos 去，即 =arcc。s 。
由假设可知，用户进入一个位置区之后所能行走的最远距离为vT，而为了使一个用户进
入一个位置区后不进行更新，则应有0< <vT／2，即不用更新的概率O2(T)应满足
c =p(o< < )= 去arcc。s去
： l+ arccos 一
4R 4R
(8)
维普资讯
通 信 学 报 2004年
式(8)中O2(T)与T的关系可由图 3给出，不难看出，O2(T)是 的增函数，而且其图形
基本上是一条直线。当 增大，检查用户从 R2回到 Rl是否 “稳定可靠”的时间增长，用户
不更新的可能性就更大。于是用户跨越边界而不用更新的总概率 = + ( )。
IUU ZUU jUU 4UU )UU
图3 (r)与T的关系图
利用求(1)、(2)的方法可以得到 TTLA算法的总代价函数为
c“．111 A=(1一(0／2+ ( )))a／p (9)
Cp
，
111 A=l+(1—8)02(T) (10)
c_下nA=c“，1frLA+cp，1．n A=(1一( ／2+ ( ))) ／ +(1+(1一 ) ( )) (11)
故式(1)、(2)、(3)和式(11)分别是IS-41、TLA、TFLA(T=0)和 TrLA(0<T~<To)的总代价函数。
4 数值比较
当 =0时，对任何P值，1rrrLA显然总是比Is一4l好；当P>28／(1一 时，不难推出
Cis_4l<c ，此时IS一41优于TLA：当P>8／(1一 时， LA<CTLA，此时1rrrLA要优于
TLA。所以，当P>8／(1一 时，1rrrLA优于Is一4l和TLA两种算法，而且相对于IS-41而言，
1rrrLA性能比TLA好时P值减少了一半。
当O<T<To时，比较式(2)和(11)可知，当P>8／(1一 时，CTrLA<c几A，1rrrLA优于TLA；
而当P值满足下式时， >c1s_4l。
D >—(8／2+8—2(T))8 (12) D>一 l lZ)
(1一 ( )
所以，当 < < 时，TTLA优于IS-4l和 TLA两种算法。
图4和图5给出了3种算法的比较图，其中1rrrLA算法分别选取时间T=0s、150s和450s。
在图 4中，0=0．75， =0．2。当P<8／(1一 =0．2／0．8=0．25时，TLA 的性能最好；当
P>2 (1一 )=0．5时，IS一41优于 TLA；而1rrrLA( =0)在P>0．25时性能好过其余四者，跟
IS一41相比其P值减少了一半。TLA 此时性能表现不出色，主要是因为 很小，即更新的代
价不高，于是 TLA更新次数少的优点表现就不是很好。
在图5中，0=0．75，8--O．8。TLA在P<8／(1一 )=0．8／0．2=4时要比IS一41和TTLA好，
由于 和0的值都比较大，系统更新的代价非常大，此时宁愿让系统进行二次寻呼也不愿进
维普资讯
第2期 单志龙等：个人通信位置管理的计时双位置算法
行位置更新，因此当 很大时，更新量最少的TLA算法是最优的。从图中也可以看出，IS一4l
的性能是最差的，因为它的更新次数是最为频繁的。而 阳 A在选取不同的值时其性能曲线
也有所不同，当时间丁的选取较大，如T--450s时，由于此时丁的选取已经接近 ，所以其
性能曲线也就比较接近 TLA的情况。所以，虽然此时TLA的性能是最优的，但是当我们选
取适当的时间丁，T】 A还是可以达到TLA算法的性能。特别是当 时，把 (丁)=0／2代
入式(11)就可以得到式(2)，此时T】 A就是TLA。
蘧
j蠹；
峨
呼叫移动比 P
图4 3种算法的性能比较(0=0．75，8=0．2)
呼叫移动比P
图5 3种算法的性能比较( =o．75，6---0．8)
当02(T) 0时，式(12)的右边 oo，即当P非常大时， <Cis 基本上都成立，此
时所得与丁=0时11LA的性能基本类似，其性能优于 IS一4l。于是 T】 A的总代价函数可以
把 IS．4l和 TLA的总代价函数统一起来，从而得到一致的函数表达式。当 O<T<To时，通过
选取不同的时间T，得到不同的02(丁)的值，从而可以根据用户的CMR在IS一41和TLA两者
之间进行切换。
维普资讯
·32· 通 信 学 报 2004住
值得注意的是，本文中02(T)的获得是基于一个假定的移动模型，当用户在小区内的移
动没有规律时，本文求解 ( )的方法将不再适用，而要通过其它途径获得。
5 总结
个人通信网中，传统的 IS一4l和TLA等位置管理算法都不能很好地满足系统要求，本文
提出了一种可以把IS一4l和TLA两者的数学结构统一起来的TTLA算法。通过对1『1rLA算法
的性能进行理论分析和数值比较表明，当选择不同的 值时，TTLA算法可以等效于或胜于
TLA和 IS一41。这样就可以在两个算法之间根据用户的移动性进行选择，且在某些 CMR值的
情况下，1TrLA算法要比另两种算法好，可以有效地减少系统的总代价。
参考文献：
【l1
【2】
【3】
【4】
【5】
【6】
【7】
【8】
【9】
【lOl
【ll】
LIVOK，QIIJXX．Personal communication systems(PCS)O1．Proceedings oftheIEEE，1995，83(9)：1210—1243．
彭峰．个人通信网中的位置管理策略【J】．电信技术，2000，5：19．22．
李瑾，罗汉文，宋文涛．第三代移动通信系统位置管理方式【J】．电信快报，1999，3：l l7．
吴晏，洪新伟，黄载禄．基于局部区域的移动性管理策略【J】．华中理工大学学报，1998，10：16-18．
LIN Y B．Reducing location apaate cost in a PCS network[J]．IEEE／ACM Trans on Networking，1997，5(1)：25—33．
ESCALLEPGGINERVC。OLTRA JM．Reducinglocationupdate andpagingCOSTSin aPCS network[11．1EEETrans Ongrtreless
Commun，2002，l(1)：200-209．
关皓，杜志涛，李承恕．终端辅助—— ．位置轨迹移动管理法【J】．电子学报，2000，28(11)：59—62．
殷蔚华，黄载禄．一种自适应位置更新方案【J】．电子学报，2000，28(1lA)：36．39．
殷蔚华，黄载禄．全分布式位置管理策略的负载和位置更新性能研究【J】．通信学报，2001，22(4)：30-38．
戎骏，裘杭萍，谢希仁．一种适应微蜂窝的移动性管理策略【J】．通信学报，2000，2l(2)：69．72．
XIE H。GOODMAN D J．Mobility models and biased sampling problem[A]．2nd Int Conf Universal Personal Commun，Ottawa
Canada[C]．1993．803—807．
作者简介：
单志龙 (1976-)，男，湖南衡
阳人，华南理工大学博士生，主要
研究方向为智能天线，移动通信等。
韦岗 (1963．)，男，广西宾阳
人，华南理工大学教授、博士生导
师，主要研究方向为通信与信号处
理，神经网络，移动通信等。
维普资讯
