基于重疊社區檢測的跟蹤區列表管理方法

王維鵬,林強強,涂山山,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劃分的影響。