基于重叠社区检测的跟踪区列表管理方法

王维鹏,林强强,涂山山,2b,肖创柏

(1.北京机电工程研究所,北京 100074; 2.北京工业大学 a.信息学部; b.可信计算北京市重点实验室,北京 100124)

0 概述

移动通信系统的位置管理是无线资源管理的一个重要方向[1-2]。为了在跟踪区列表(Tracking Area List,TAL)网络中降低信令开销,将整个网络覆盖区域划分为多个互不重叠的跟踪区(Tracking Area,TA)。其中,每个跟踪区由至少一个蜂窝小区组成,每个小区只能属于一个TA。当用户移动到某一小区时就会被分配到相应的TA。用户从一个TA移动到另一个TA时会进行位置更新,并将当前位置上报给核心网络的移动性管理实体(Mobile Management Entity,MME)[3-4]。用户在TA内移动时不需要进行位置更新操作,当产生网络寻呼时,核心网络会在当前所属TA内的所有蜂窝小区发送寻呼消息。

传统TA的概念在最小化寻呼开销方面具有优势,但仍存在一些不足。由于乒乓效应可能产生更多的位置更新信令开销,因此用户在属于不同TA的2个相邻小区之间跨越所产生的位置更新,在密集部署的蜂窝环境下会更加频繁。同时,在大量用户具有类似行为,如同时从一个TA移动到另一个TA时,会引起移动性信令拥塞。此外,TA的使用具有对称性限制,如果2个蜂窝小区在同一TA中,则两者都不能在任何其他TA中。

为了解决上述问题,研究者们在3GPP R8中引入TAL的概念[5]。TAL由一个或多个TA组成且TAL之间可以相互重叠,用户在TAL中移动时不需要发起跟踪区更新(Tracking Area Update,TAU)操作,而当用户移动到一个不属于之前配置的TAL 的TA中时,需进行位置更新操作,核心网络重新配置新的TAL并将其发送给用户。TAL越大则TAU操作次数越少,网络寻呼会在整个TAL所包含的TA中进行,增加了额外的网络寻呼负荷。因此,位置管理需要一种合理的TAL管理配置策略,以降低网络的信令开销。

近年来,博弈论已被广泛应用于无线通信网络的设计中[6]。博弈论是研究具有竞争或斗争性现象的理论,该理论考虑了团体中的个体实际行为和预测行为,并研究其相应的优化策略。文献[7]利用博弈论检测复杂网络中的社区,受此启发,本文将TAL划分看成基于博弈论的社区检测问题,提出一种基于重叠社区的跟踪区列表管理方法。

1 相关工作

目前,研究者们已经从不同角度对各种跟踪区列表设计方法进行了研究[8-9],其可以大致分为基于用户状态信息的方法和独立于用户状态信息的方法2类。

1.1 基于用户状态信息的方法

文献[10]提出一种基于网络寻呼和切换的最小化信令开销TAL方法,其主要特点是网络分配的TAL随着上一个用户注册的TAL的变化而变化。文献[11]基于rule of thumb进行TAL管理,该方法在具体实现上较为简单便捷。文献[12]提出一种基于时间记录的TAL方法,其适用于用户移动规律性较强的跟踪区域。文献[13]提出一种基于本地用户的TAL方法,该方法同样针对用户移动规律性较强的跟踪区域进行研究,但是不适用于部署密集的小蜂窝环境以及具有密集用户的热点地区。

1.2 独立于用户状态信息的方法

文献[14]提出一种基于运动量的TAL方法,通过测量用户移动和寻呼特性来获取运动量门限值,并分配相应的跟踪区列表。文献[15]提出一种基于自组织的TAL方法,通过监督用户运动行为来调整TAL大小。

上述位置管理方法大多基于不同移动用户产生不同的TAL,在海量的小蜂窝部署环境下,其计算效率会急剧降低。因此,需要研究更加快速、高效的位置管理方案,降低位置管理所带来的信令开销成本。

2 基于跟踪区列表的位置管理方法

蜂窝网络可以看作一个复杂网络,其中的社区由多个节点组成,社区是包含紧密连接的节点群。将TAL划分建模为复杂网络中的社区检测问题,然后采用基于博弈论的社区检测算法进行快速检测。

2.1 基于图论的TAL建模方法

如图1所示,给定网络图G(V,E)表示要进行TAL规划的蜂窝网络,其中顶点集合V={v1,v2,…,vn}表示不同的TA,n表示TA的数量,边集E表示TA之间的邻接关系,H表示网络图的邻接矩阵,H中的每一项hij表示用户从TAi移动到TAj的跨区次数(需要注意的是,hij与hji是不同的,hij表示从TAi移动到TAj的用户数,hji表示从TAj移动到TAi的用户数)。P={p1,p2,…,pn}为图中顶点的权重集合,权重值pi表示在TAi内发生的用户寻呼请求次数。跟踪区列表TAL结构表示为Γ={S1,S2,…,Sk},k为TAL数量,元素Si至少包含一个TA。使用二进制参数ail表示TAi是否在TALl中,若在则ail=1。此外,cu和cp分别表示进行一次位置更新和寻呼操作的信令开销,α表示在同一时间段内每个用户被寻呼的次数,ui表示在同一时间段内TAi的用户数。

图1 基于图论的TAL建模示意图

TAU和寻呼开销的最小化问题建模如下:

(1)

(2)

(3)

(4)

式(1)表示TAL划分的目的是最小化位置更新和寻呼总信令开销。式(2)对网络中每2个不同TA之间的位置更新信令开销进行约束计算。式(3)则计算网络中每个TA的寻呼开销。式(4)约束确保TALl的长度不超过Ntolmax,Ntolmax是TAL中允许包含TA的最大数量。

2.2 跟踪区列表管理

复杂网络具有自组织、自相似、无标度等性质。对于热点地区,蜂窝部署具有随机性,这与复杂网络的性质极为相似。社区结构是复杂网络中的重要特征,图2给出重叠社区划分示例。在基于TAL的位置管理方法中,本文将TA看作复杂网络中的节点,将TAL的设计看作复杂网络中重叠社区的检测问题,不同的TAL(即不同的社区)可以包含相同的TA(即社区中的重叠节点)。本文受文献[7]的启发,对复杂网络中的社区检测算法进行探索,提出一种基于重叠社区检测的TAL划分算法,并利用博弈论进行社区检测。

图2 重叠社区结构划分示例

2.2.1 基于博弈论的重叠社区检测

基于博弈论的重叠社区检测,主要思想是将重叠社区作为联盟构建博弈模型,将网络中的个体作为理性参与者,通过与网络中的其他参与者形成联盟来改善整个团体的效用。只要合并操作有利于联盟效用的增加,就允许参与者加入联盟。联盟的效用函数定义为增益函数和成本函数的组合,其中,增益函数评测联盟内参与者之间的相互作用程度,而成本函数表示联盟中的参与者与不属于该联盟的其他参与者之间的相互作用程度。通过基于博弈论的重叠社区检测算法在位置更新与寻呼开销之间寻找更优的平衡点,以进一步优化网络总信令开销。

2.2.2 效用函数

设集合S表示V的一个子集,称为联盟,e(S)表示联盟S内节点之间的连接总边数的权重和(即TAL包含所有TA之间的用户切换总次数),p(S)表示联盟S内节点的权重和(即TAL包含所有TA内发生的寻呼请求总数),v(S)表示联盟S的效用函数(即TAL集合的效用函数)。对于任意联盟S1,S2⊆V,令e(S1,S2)表示联盟S1与联盟S2之间连接边的权重和。令Sij表示联盟Si与联盟Sj的合并,令Γ表示一个社区结构(即TAL划分结构),即Γ={S1,S2,…,Sk},k代表TAL结构的数量,则效用函数如式(5)所示。

(5)

2.2.3 联盟合并的条件

当满足以下3个条件时,联盟之间进行合并操作:

条件1v(S1+S2)>v(S1)&v(S1+S2)>v(S2)。该条件表明,通过合并操作可增加联盟S1与联盟S2的效用,确保由合并操作形成的联盟具有比其子集更大的效用。

条件2e(S1,S2)≠0。该条件表明,当e(S1,S2)=0时,联盟S1不与联盟S2合并,即2个没有联系的联盟不能合并成一个更大的联盟。

2.2.4 基于重叠社区检测的跟踪区列表管理算法

基于重叠社区检测的跟踪区列表管理算法是通过一种贪婪聚类方法识别TAL结构,主要思想是以网络中所有TA为单独的联盟(即TAL),并将效用增量最高的联盟迭代合并为更大的联盟,从而改善整体的效用,直到不能执行合并操作为止。具体流程如算法1所示。

算法1基于重叠社区检测的跟踪区列表管理算法

输入经TA规划之后的TA集合V={v1,v2,…,vn},网络的边权重矩阵H=(hij)n×n,i,j∈V,网络的节点权重集P={p1,p2,…,pn}

输出TAL规划结果Γ={S1,S2,…,Sk}

1.初始化

1.1 每个TA形成单独的TAL,为集合V0

1.2 初始化k=0为循环检测次数,集合Vk为第k次循环检测出的TAL结构

2.重复以下步骤,直至Vk=Vk+1:

2.1 初始化集合copyV,令copyV=Vk

2.2 k=k+1

2.3 Vk=∅

2.4 重复以下步骤,直至copyV=∅:

2.4.2 copyV=copyV-{MaxV}

2.4.3 初始化集合canV,该集合是一组联盟合作候选者,与集合MaxV之间至少有一条边相连;令canV(MaxV)={S|∃H(i,j)≠0,i∈MaxV,j∈S,S∈Vk-1}

2.4.4 重复以下步骤,直至canV(MaxV)=∅:

2.4.4.2 判断集合MaxV和opV*是否满足2.2.3节所述的3个条件

2.4.4.3 如果满足,则:

MaxV=MaxV+opV*

canV=canV-{opV*}

canV(MaxV)=canV(MaxV)-{opV*}+(canV(opV*)-{MaxV})

2.4.4.4 如果不满足,则:

canV(MaxV)=can(MaxV)-{opV*}

2.5 Vk=Vk+{MaxV}

3.返回集合Vk

步骤1是初始化:每个TA形成一个TAL,并形成集合V0;步骤2.4.4循环为集合Vk+1创建联盟;步骤2.4的循环为集合Vk+1创建所有联盟;步骤2循环检测TAL结构,步骤2.5输出检测出的TAL结构。在最坏情况下,该算法的时间复杂度为O(|V|lb|V|)。

3 实验结果与分析

本节分析网络TAL划分之后的信令开销,并给出位置管理方法的性能评价指标。为了说明本文算法的优势,引入以下2种基于TAL规划的位置管理方法进行对比:

1)TAs-to-TALs分配方案[16],简称TAL-1方案。该方案使用讨价还价游戏来确保LU与寻呼信令开销之间的公平权衡。

2)cell-to-TAL动态配置方案[17],简称TAL-2方案。该方案直接将单独的峰窝动态划分到TAL中,省略了cell-to-TA的步骤,分配效率较高。

3.1 TAL信令开销计算分析

假设网络经过TA规划之后的TA集合用V={v1,v2,…,vn}表示,n表示TA数量,跟踪区列表TAL集合表示为Γ={S1,S2,…,Sk},k表示TAL数量,则每个TA所属的TAL可以表示成t={t1,t2,…,tn},其中ti表示跟踪区i所属的跟踪区列表,跟踪区列表的设计t可以用一个N×N矩阵F(t)表示。矩阵中每个元素Fij(t)表示TAi与TAj是否在同一个跟踪区列表内,其计算过程如下:

(6)

信令开销计算如下:

(7)

CTAU=cuhij(1-Fij(t))

(8)

Cpaging=αcpuiFij(t)

(9)

其中,cu和cp分别表示进行一次跟踪区更新和寻呼的信令开销,cu和cp之间的比例关系取决于无线电资源的消耗,hij表示从TAi移动到TAj的用户数,α表示在同一时间内每个用户被寻呼的次数,ui表示在同一时间内的用户数。式(7)前半段表示用户从TAi移动到TAj产生的跟踪区更新信令开销,后半段表示用户在TAj内的额外寻呼信令开销。

3.2 结果分析

本文通过以下3个指标来评估方案性能:

1)总信令开销:由寻呼和LU而产生的总开销,计算过程如式(7)所示。

2)TAU信令开销:用户在访问新TAL时生成TAU消息的开销,计算过程如式(8)所示。

3)寻呼信令开销:在呼叫建立期间从MME发送的用于定位用户的寻呼消息而产生的信令开销,计算过程如式(9)所示。

本文方法是在TA规划的基础上进行的,因此,首先通过实验将蜂窝基站按照PPP点过程[18]部署在1 500 m×1 500 m的区域内,并按照文献[19]将其划分为一组TA。用户的移动性根据随机路点移动模型[20]来建模,其中暂停时间设置为0。本文最初将用户随机部署在TA中,在评估期间,每个用户在部署区域内随机选择目的地(TA)并以[avgSpeed-Δ,avgSpeed+Δ]之间均匀分布的速度向目的地移动,其中,avgSpeed是不同用户的平均速度,Δ是用户速度的变化范围。

为了评估本文方法的性能,通过调整用户平均移动速度来观察对网络信令开销的影响。增大用户平均移动速度相当于减小用户在TA中的逗留时间,即减小蜂窝的覆盖范围。表1给出本文实验的模拟参数值。

表1 模拟参数值

图3给出3种方法寻呼信令开销的对比,可以看出,随着平均速度的增大,3种方法的寻呼开销趋于稳定,这是由于本文将系统呼叫到达率设置为固定数值,因此平均速度对寻呼开销影响不大。同时,本文方法的寻呼开销稳定在82 000左右,TAL-1与TAL-2方法的寻呼开销分别稳定在60 000和45 000左右,本文方法的寻呼开销高于其他2种方法。这是由于TAL方法将TA组织成更大范围的TAL,额外增加了系统的寻呼开销。

图3 3种方法的寻呼信令开销对比

图4给出3种方法TAU信令开销的对比。由图4可知,随着平均速度由2 m/s提高至14 m/s,3种方法的TAU开销均逐渐增大。这是由于用户移动速度增大,其在TA之间频繁切换并造成大量的位置更新信令开销。本文方法的TAU信令开销较低,而TAL-2方法的TAU信令开销较高,这是因为本文方法将访问频繁的TA划分到不同的TAL中,减少了用户位置更新的次数。

图4 3种方法的TAU信令开销对比

图5给出3种方法总信令开销的对比,可以看出,总信令开销随平均速度变化的趋势与图4类似,这是由于在用户移动速度增大时,影响网络信令开销的主要因素是用户频繁跨越TA所带来的位置更新信令开销。相比于TAL-1与TAL-2方法,本文方法的总信令开销分别降低22.4%和27.1%左右,说明在用户平均移动速度变化的情况下,本文方法在降低网络总信令开销方面具有优势。

图5 3种方法的总信令开销对比

综上所述,基于跟踪区列表管理方法的关键是在TAU和寻呼信令开销间寻找平衡点,进一步降低网络总信令开销成本。通过与TAL-1、TAL-2方法的对比可知,本文方法在用户平均移动速度较高的情况下,仍然能够有效降低网络总信令开销成本。因此,本文的位置管理方法适用于蜂窝基站超密集组网的环境。

4 结束语

未来蜂窝网络应用的一个重要挑战是应对位置管理带来的信令开销,尤其是在热点区域密集部署蜂窝基站时,其网络信令开销可能会大幅增加。本文提出一种基于重叠社区检测的跟踪区列表管理方法,在TA规划的基础上,应用基于博弈论的重叠社区检测算法进行TAL划分。实验结果表明,在用户平均移动速度变化的情况下,该方法能够有效降低网络总信令开销,同时,由于其针对整个热点区域的用户进行跟踪管理,因此在一定程度上提高了网络效率和服务质量。然而,该方法没有对具体用户进行位置管理,其所产生的TAL不一定是最优的。因此,下一步将在各种部署场景中详细分析用户移动对TAL划分的影响。