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

王維鵬,林強強,涂山山,2b,肖創(chuàng)柏

(1.北京機電工程研究所,北京 100074; 2.北京工業(yè)大學 a.信息學部; b.可信計算北京市重點實驗室,北京 100124)

0 概述

移動通信系統(tǒng)的位置管理是無線資源管理的一個重要方向[1-2]。為了在跟蹤區(qū)列表(Tracking Area List,TAL)網(wǎng)絡中降低信令開銷,將整個網(wǎng)絡覆蓋區(qū)域劃分為多個互不重疊的跟蹤區(qū)(Tracking Area,TA)。其中,每個跟蹤區(qū)由至少一個蜂窩小區(qū)組成,每個小區(qū)只能屬于一個TA。當用戶移動到某一小區(qū)時就會被分配到相應的TA。用戶從一個TA移動到另一個TA時會進行位置更新,并將當前位置上報給核心網(wǎng)絡的移動性管理實體(Mobile Management Entity,MME)[3-4]。用戶在TA內移動時不需要進行位置更新操作,當產生網(wǎng)絡尋呼時,核心網(wǎng)絡會在當前所屬TA內的所有蜂窩小區(qū)發(fā)送尋呼消息。

傳統(tǒng)TA的概念在最小化尋呼開銷方面具有優(yōu)勢,但仍存在一些不足。由于乒乓效應可能產生更多的位置更新信令開銷,因此用戶在屬于不同TA的2個相鄰小區(qū)之間跨越所產生的位置更新,在密集部署的蜂窩環(huán)境下會更加頻繁。同時,在大量用戶具有類似行為,如同時從一個TA移動到另一個TA時,會引起移動性信令擁塞。此外,TA的使用具有對稱性限制,如果2個蜂窩小區(qū)在同一TA中,則兩者都不能在任何其他TA中。

為了解決上述問題,研究者們在3GPP R8中引入TAL的概念[5]。TAL由一個或多個TA組成且TAL之間可以相互重疊,用戶在TAL中移動時不需要發(fā)起跟蹤區(qū)更新(Tracking Area Update,TAU)操作,而當用戶移動到一個不屬于之前配置的TAL 的TA中時,需進行位置更新操作,核心網(wǎng)絡重新配置新的TAL并將其發(fā)送給用戶。TAL越大則TAU操作次數(shù)越少,網(wǎng)絡尋呼會在整個TAL所包含的TA中進行,增加了額外的網(wǎng)絡尋呼負荷。因此,位置管理需要一種合理的TAL管理配置策略,以降低網(wǎng)絡的信令開銷。

近年來,博弈論已被廣泛應用于無線通信網(wǎng)絡的設計中[6]。博弈論是研究具有競爭或斗爭性現(xiàn)象的理論,該理論考慮了團體中的個體實際行為和預測行為,并研究其相應的優(yōu)化策略。文獻[7]利用博弈論檢測復雜網(wǎng)絡中的社區(qū),受此啟發(fā),本文將TAL劃分看成基于博弈論的社區(qū)檢測問題,提出一種基于重疊社區(qū)的跟蹤區(qū)列表管理方法。

1 相關工作

目前,研究者們已經從不同角度對各種跟蹤區(qū)列表設計方法進行了研究[8-9],其可以大致分為基于用戶狀態(tài)信息的方法和獨立于用戶狀態(tài)信息的方法2類。

1.1 基于用戶狀態(tài)信息的方法

文獻[10]提出一種基于網(wǎng)絡尋呼和切換的最小化信令開銷TAL方法,其主要特點是網(wǎng)絡分配的TAL隨著上一個用戶注冊的TAL的變化而變化。文獻[11]基于rule of thumb進行TAL管理,該方法在具體實現(xiàn)上較為簡單便捷。文獻[12]提出一種基于時間記錄的TAL方法,其適用于用戶移動規(guī)律性較強的跟蹤區(qū)域。文獻[13]提出一種基于本地用戶的TAL方法,該方法同樣針對用戶移動規(guī)律性較強的跟蹤區(qū)域進行研究,但是不適用于部署密集的小蜂窩環(huán)境以及具有密集用戶的熱點地區(qū)。

1.2 獨立于用戶狀態(tài)信息的方法

文獻[14]提出一種基于運動量的TAL方法,通過測量用戶移動和尋呼特性來獲取運動量門限值,并分配相應的跟蹤區(qū)列表。文獻[15]提出一種基于自組織的TAL方法,通過監(jiān)督用戶運動行為來調整TAL大小。

上述位置管理方法大多基于不同移動用戶產生不同的TAL,在海量的小蜂窩部署環(huán)境下,其計算效率會急劇降低。因此,需要研究更加快速、高效的位置管理方案,降低位置管理所帶來的信令開銷成本。

2 基于跟蹤區(qū)列表的位置管理方法

蜂窩網(wǎng)絡可以看作一個復雜網(wǎng)絡,其中的社區(qū)由多個節(jié)點組成,社區(qū)是包含緊密連接的節(jié)點群。將TAL劃分建模為復雜網(wǎng)絡中的社區(qū)檢測問題,然后采用基于博弈論的社區(qū)檢測算法進行快速檢測。

2.1 基于圖論的TAL建模方法

如圖1所示,給定網(wǎng)絡圖G(V,E)表示要進行TAL規(guī)劃的蜂窩網(wǎng)絡,其中頂點集合V={v1,v2,…,vn}表示不同的TA,n表示TA的數(shù)量,邊集E表示TA之間的鄰接關系,H表示網(wǎng)絡圖的鄰接矩陣,H中的每一項hij表示用戶從TAi移動到TAj的跨區(qū)次數(shù)(需要注意的是,hij與hji是不同的,hij表示從TAi移動到TAj的用戶數(shù),hji表示從TAj移動到TAi的用戶數(shù))。P={p1,p2,…,pn}為圖中頂點的權重集合,權重值pi表示在TAi內發(fā)生的用戶尋呼請求次數(shù)。跟蹤區(qū)列表TAL結構表示為Γ={S1,S2,…,Sk},k為TAL數(shù)量,元素Si至少包含一個TA。使用二進制參數(shù)ail表示TAi是否在TALl中,若在則ail=1。此外,cu和cp分別表示進行一次位置更新和尋呼操作的信令開銷,α表示在同一時間段內每個用戶被尋呼的次數(shù),ui表示在同一時間段內TAi的用戶數(shù)。

圖1 基于圖論的TAL建模示意圖

TAU和尋呼開銷的最小化問題建模如下:

(1)

(2)

(3)

(4)

式(1)表示TAL劃分的目的是最小化位置更新和尋呼總信令開銷。式(2)對網(wǎng)絡中每2個不同TA之間的位置更新信令開銷進行約束計算。式(3)則計算網(wǎng)絡中每個TA的尋呼開銷。式(4)約束確保TALl的長度不超過Ntolmax,Ntolmax是TAL中允許包含TA的最大數(shù)量。

2.2 跟蹤區(qū)列表管理

復雜網(wǎng)絡具有自組織、自相似、無標度等性質。對于熱點地區(qū),蜂窩部署具有隨機性,這與復雜網(wǎng)絡的性質極為相似。社區(qū)結構是復雜網(wǎng)絡中的重要特征,圖2給出重疊社區(qū)劃分示例。在基于TAL的位置管理方法中,本文將TA看作復雜網(wǎng)絡中的節(jié)點,將TAL的設計看作復雜網(wǎng)絡中重疊社區(qū)的檢測問題,不同的TAL(即不同的社區(qū))可以包含相同的TA(即社區(qū)中的重疊節(jié)點)。本文受文獻[7]的啟發(fā),對復雜網(wǎng)絡中的社區(qū)檢測算法進行探索,提出一種基于重疊社區(qū)檢測的TAL劃分算法,并利用博弈論進行社區(qū)檢測。

圖2 重疊社區(qū)結構劃分示例

2.2.1 基于博弈論的重疊社區(qū)檢測

基于博弈論的重疊社區(qū)檢測,主要思想是將重疊社區(qū)作為聯(lián)盟構建博弈模型,將網(wǎng)絡中的個體作為理性參與者,通過與網(wǎng)絡中的其他參與者形成聯(lián)盟來改善整個團體的效用。只要合并操作有利于聯(lián)盟效用的增加,就允許參與者加入聯(lián)盟。聯(lián)盟的效用函數(shù)定義為增益函數(shù)和成本函數(shù)的組合,其中,增益函數(shù)評測聯(lián)盟內參與者之間的相互作用程度,而成本函數(shù)表示聯(lián)盟中的參與者與不屬于該聯(lián)盟的其他參與者之間的相互作用程度。通過基于博弈論的重疊社區(qū)檢測算法在位置更新與尋呼開銷之間尋找更優(yōu)的平衡點,以進一步優(yōu)化網(wǎng)絡總信令開銷。

2.2.2 效用函數(shù)

設集合S表示V的一個子集,稱為聯(lián)盟,e(S)表示聯(lián)盟S內節(jié)點之間的連接總邊數(shù)的權重和(即TAL包含所有TA之間的用戶切換總次數(shù)),p(S)表示聯(lián)盟S內節(jié)點的權重和(即TAL包含所有TA內發(fā)生的尋呼請求總數(shù)),v(S)表示聯(lián)盟S的效用函數(shù)(即TAL集合的效用函數(shù))。對于任意聯(lián)盟S1,S2?V,令e(S1,S2)表示聯(lián)盟S1與聯(lián)盟S2之間連接邊的權重和。令Sij表示聯(lián)盟Si與聯(lián)盟Sj的合并,令Γ表示一個社區(qū)結構(即TAL劃分結構),即Γ={S1,S2,…,Sk},k代表TAL結構的數(shù)量,則效用函數(shù)如式(5)所示。

(5)

2.2.3 聯(lián)盟合并的條件

當滿足以下3個條件時,聯(lián)盟之間進行合并操作:

條件1v(S1+S2)>v(S1)&v(S1+S2)>v(S2)。該條件表明,通過合并操作可增加聯(lián)盟S1與聯(lián)盟S2的效用,確保由合并操作形成的聯(lián)盟具有比其子集更大的效用。

條件2e(S1,S2)≠0。該條件表明,當e(S1,S2)=0時,聯(lián)盟S1不與聯(lián)盟S2合并,即2個沒有聯(lián)系的聯(lián)盟不能合并成一個更大的聯(lián)盟。

2.2.4 基于重疊社區(qū)檢測的跟蹤區(qū)列表管理算法

基于重疊社區(qū)檢測的跟蹤區(qū)列表管理算法是通過一種貪婪聚類方法識別TAL結構,主要思想是以網(wǎng)絡中所有TA為單獨的聯(lián)盟(即TAL),并將效用增量最高的聯(lián)盟迭代合并為更大的聯(lián)盟,從而改善整體的效用,直到不能執(zhí)行合并操作為止。具體流程如算法1所示。

算法1基于重疊社區(qū)檢測的跟蹤區(qū)列表管理算法

輸入經TA規(guī)劃之后的TA集合V={v1,v2,…,vn},網(wǎng)絡的邊權重矩陣H=(hij)n×n,i,j∈V,網(wǎng)絡的節(jié)點權重集P={p1,p2,…,pn}

輸出TAL規(guī)劃結果Γ={S1,S2,…,Sk}

1.初始化

1.1 每個TA形成單獨的TAL,為集合V0

1.2 初始化k=0為循環(huán)檢測次數(shù),集合Vk為第k次循環(huán)檢測出的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,該集合是一組聯(lián)盟合作候選者,與集合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節(jié)所述的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循環(huán)為集合Vk+1創(chuàng)建聯(lián)盟;步驟2.4的循環(huán)為集合Vk+1創(chuàng)建所有聯(lián)盟;步驟2循環(huán)檢測TAL結構,步驟2.5輸出檢測出的TAL結構。在最壞情況下,該算法的時間復雜度為O(|V|lb|V|)。

3 實驗結果與分析

本節(jié)分析網(wǎng)絡TAL劃分之后的信令開銷,并給出位置管理方法的性能評價指標。為了說明本文算法的優(yōu)勢,引入以下2種基于TAL規(guī)劃的位置管理方法進行對比:

1)TAs-to-TALs分配方案[16],簡稱TAL-1方案。該方案使用討價還價游戲來確保LU與尋呼信令開銷之間的公平權衡。

2)cell-to-TAL動態(tài)配置方案[17],簡稱TAL-2方案。該方案直接將單獨的峰窩動態(tài)劃分到TAL中,省略了cell-to-TA的步驟,分配效率較高。

3.1 TAL信令開銷計算分析

假設網(wǎng)絡經過TA規(guī)劃之后的TA集合用V={v1,v2,…,vn}表示,n表示TA數(shù)量,跟蹤區(qū)列表TAL集合表示為Γ={S1,S2,…,Sk},k表示TAL數(shù)量,則每個TA所屬的TAL可以表示成t={t1,t2,…,tn},其中ti表示跟蹤區(qū)i所屬的跟蹤區(qū)列表,跟蹤區(qū)列表的設計t可以用一個N×N矩陣F(t)表示。矩陣中每個元素Fij(t)表示TAi與TAj是否在同一個跟蹤區(qū)列表內,其計算過程如下:

(6)

信令開銷計算如下:

(7)

CTAU=cuhij(1-Fij(t))

(8)

Cpaging=αcpuiFij(t)

(9)

其中,cu和cp分別表示進行一次跟蹤區(qū)更新和尋呼的信令開銷,cu和cp之間的比例關系取決于無線電資源的消耗,hij表示從TAi移動到TAj的用戶數(shù),α表示在同一時間內每個用戶被尋呼的次數(shù),ui表示在同一時間內的用戶數(shù)。式(7)前半段表示用戶從TAi移動到TAj產生的跟蹤區(qū)更新信令開銷,后半段表示用戶在TAj內的額外尋呼信令開銷。

3.2 結果分析

本文通過以下3個指標來評估方案性能:

1)總信令開銷:由尋呼和LU而產生的總開銷,計算過程如式(7)所示。

2)TAU信令開銷:用戶在訪問新TAL時生成TAU消息的開銷,計算過程如式(8)所示。

3)尋呼信令開銷:在呼叫建立期間從MME發(fā)送的用于定位用戶的尋呼消息而產生的信令開銷,計算過程如式(9)所示。

本文方法是在TA規(guī)劃的基礎上進行的,因此,首先通過實驗將蜂窩基站按照PPP點過程[18]部署在1 500 m×1 500 m的區(qū)域內,并按照文獻[19]將其劃分為一組TA。用戶的移動性根據(jù)隨機路點移動模型[20]來建模,其中暫停時間設置為0。本文最初將用戶隨機部署在TA中,在評估期間,每個用戶在部署區(qū)域內隨機選擇目的地(TA)并以[avgSpeed-Δ,avgSpeed+Δ]之間均勻分布的速度向目的地移動,其中,avgSpeed是不同用戶的平均速度,Δ是用戶速度的變化范圍。

為了評估本文方法的性能,通過調整用戶平均移動速度來觀察對網(wǎng)絡信令開銷的影響。增大用戶平均移動速度相當于減小用戶在TA中的逗留時間,即減小蜂窩的覆蓋范圍。表1給出本文實驗的模擬參數(shù)值。

表1 模擬參數(shù)值

圖3給出3種方法尋呼信令開銷的對比,可以看出,隨著平均速度的增大,3種方法的尋呼開銷趨于穩(wěn)定,這是由于本文將系統(tǒng)呼叫到達率設置為固定數(shù)值,因此平均速度對尋呼開銷影響不大。同時,本文方法的尋呼開銷穩(wěn)定在82 000左右,TAL-1與TAL-2方法的尋呼開銷分別穩(wěn)定在60 000和45 000左右,本文方法的尋呼開銷高于其他2種方法。這是由于TAL方法將TA組織成更大范圍的TAL,額外增加了系統(tǒng)的尋呼開銷。

圖3 3種方法的尋呼信令開銷對比

圖4給出3種方法TAU信令開銷的對比。由圖4可知,隨著平均速度由2 m/s提高至14 m/s,3種方法的TAU開銷均逐漸增大。這是由于用戶移動速度增大,其在TA之間頻繁切換并造成大量的位置更新信令開銷。本文方法的TAU信令開銷較低,而TAL-2方法的TAU信令開銷較高,這是因為本文方法將訪問頻繁的TA劃分到不同的TAL中,減少了用戶位置更新的次數(shù)。

圖4 3種方法的TAU信令開銷對比

圖5給出3種方法總信令開銷的對比,可以看出,總信令開銷隨平均速度變化的趨勢與圖4類似,這是由于在用戶移動速度增大時,影響網(wǎng)絡信令開銷的主要因素是用戶頻繁跨越TA所帶來的位置更新信令開銷。相比于TAL-1與TAL-2方法,本文方法的總信令開銷分別降低22.4%和27.1%左右,說明在用戶平均移動速度變化的情況下,本文方法在降低網(wǎng)絡總信令開銷方面具有優(yōu)勢。

圖5 3種方法的總信令開銷對比

綜上所述,基于跟蹤區(qū)列表管理方法的關鍵是在TAU和尋呼信令開銷間尋找平衡點,進一步降低網(wǎng)絡總信令開銷成本。通過與TAL-1、TAL-2方法的對比可知,本文方法在用戶平均移動速度較高的情況下,仍然能夠有效降低網(wǎng)絡總信令開銷成本。因此,本文的位置管理方法適用于蜂窩基站超密集組網(wǎng)的環(huán)境。

4 結束語

未來蜂窩網(wǎng)絡應用的一個重要挑戰(zhàn)是應對位置管理帶來的信令開銷,尤其是在熱點區(qū)域密集部署蜂窩基站時,其網(wǎng)絡信令開銷可能會大幅增加。本文提出一種基于重疊社區(qū)檢測的跟蹤區(qū)列表管理方法,在TA規(guī)劃的基礎上,應用基于博弈論的重疊社區(qū)檢測算法進行TAL劃分。實驗結果表明,在用戶平均移動速度變化的情況下,該方法能夠有效降低網(wǎng)絡總信令開銷,同時,由于其針對整個熱點區(qū)域的用戶進行跟蹤管理,因此在一定程度上提高了網(wǎng)絡效率和服務質量。然而,該方法沒有對具體用戶進行位置管理,其所產生的TAL不一定是最優(yōu)的。因此,下一步將在各種部署場景中詳細分析用戶移動對TAL劃分的影響。