多目標(biāo)的跟蹤區(qū)域列表動態(tài)優(yōu)化算法摘要移動網(wǎng)絡(luò)要適應(yīng)多樣化和不斷增加的用戶設(shè)備（ＵＥ），應(yīng)對終端巨大的位置管理信令開銷是實(shí)現(xiàn)這一目標(biāo)的重要保障。文中提出了一種多目標(biāo)算法優(yōu)化跟蹤區(qū)域列表（ＴｒａｃｋｉｎｇＴＡＬ）的策略，目的是尋找中跟蹤區(qū)（ＴｒａｃｋｉｎｇＴＡ）的最優(yōu)分布以及如何將分配給ＵＥ，以最小化位置管理中沖突的跟蹤區(qū)更新（Ｔｒａｃｋｉｎｇ和尋呼信令開銷。在本地側(cè)利用多目標(biāo)粒子群優(yōu)化算法實(shí)現(xiàn)的最優(yōu)分布，網(wǎng)絡(luò)側(cè)根據(jù)不同的移動特性來分配大小合適的通過仿真驗(yàn)證，所提方案可以在和尋呼開銷之間取得妥協(xié)，并在節(jié)省總位置管理開銷方面得到了大幅度改善。關(guān)鍵詞：位置管理；位置更新和尋呼；跟蹤區(qū)域列表；多目標(biāo)粒子群優(yōu)化；馬爾科夫鏈Ａｄｙｎａｍｉｃｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｍｕｌｔｉ?ｔａｒｇｅｔｔｒａｃｋｉｎｇａｒｅａｌｉｓｔｓ(Ｃｈｉｎａ)（ＵＥ），ａ（．（ＴＡ）ＵＥ．（）：ｌｉｓｔ（ＴＡＬ）；在目前移動通信網(wǎng)絡(luò)快速發(fā)展的背景下，網(wǎng)絡(luò)ＬＵ）和尋呼（Ｐａｇｉｎｇ）流程，ＬＵ是指當(dāng)移出當(dāng)前需要適應(yīng)越來越多的用戶設(shè)備（注冊區(qū)域時請求網(wǎng)絡(luò)分配新的注冊區(qū)域，而尋呼流ＵＥ）的接入［１－２］，在５Ｇ網(wǎng)絡(luò)中采用微小區(qū)的策略來程是指網(wǎng)絡(luò)定位的過程［４］。應(yīng)對的大規(guī)模接入問題，然而高密度微小區(qū)的在位置管理策略中，３ＧＰＰ將整個網(wǎng)絡(luò)覆蓋域引入會導(dǎo)致核心網(wǎng)定位的信令開銷急劇增劃分為若干個跟蹤區(qū)（ＴｒａｃｋｉｎｇＡｒｅａ，ＴＡ），每個大［３］。位置管理包括位置更新（由若干個小區(qū)組成，而多個又組成一個跟蹤區(qū)域列表（ＴｒａｃｋｉｎｇＬｉｓｔ，ＴＡＬ）［５］。當(dāng)在內(nèi)移動時，不會發(fā)起過程，只有移出邊，實(shí)現(xiàn)從本地側(cè)產(chǎn)生的概率分界小區(qū)時，此時會發(fā)現(xiàn)基站廣播的跟蹤區(qū)域標(biāo)識布矩陣中選擇一個大小適合當(dāng)前移動特點(diǎn)的（ＴｒａｃｋｉｎｇＩｄｅｎｔｉｔｙ，ＴＡＩ）不屬于存儲的。仿真分析，在減小位置管中，將發(fā)起跟蹤區(qū)更新流程（請求核心網(wǎng)重新，如相比算法分配ＴＡＬ。當(dāng)核心網(wǎng)有用戶的業(yè)務(wù)請求時，會向。整個廣播尋呼消息來定位目標(biāo)ＵＥ。因此，位置管理開銷包括ＵＥ發(fā)起的位置更新開銷和網(wǎng)絡(luò)１系統(tǒng)模型定位ＵＥ的尋呼開銷，而兩者之間根據(jù)大小不１．１模型假設(shè)同呈現(xiàn)矛盾關(guān)系，如當(dāng)規(guī)劃過大，雖然ＵＥ會

假設(shè)網(wǎng)絡(luò)中有Ｎ個ＴＡ，編號為Ｎ＝｛１，２，…，長期停留在內(nèi)不發(fā)起過程，可以有效減小位置更新開銷，但同時網(wǎng)絡(luò)尋呼區(qū)域變大，造成尋呼開銷的增加，ＴＡＬ過小則存在相反的問題［６］。為了對進(jìn)行最優(yōu)規(guī)劃以減小位置管理開Ｎ｝，每個又可以由若干個小區(qū)組成［１３］。而由Ｎ組成的所有為集合Γ，并記Γｉ為包含ＴＡｉ的那么有Γ＝∪ｉ∈ＮΓｉ。下面以如圖１所示的網(wǎng)絡(luò)拓?fù)鋱D說明。銷，目前提出了大量的研究方法。首先，考慮重疊的設(shè)計方法，相鄰包含部分重疊的以避免在邊界小區(qū)來回移動產(chǎn)生大量的開銷，即“乒乓效應(yīng)”現(xiàn)象［７］。文獻(xiàn)［８］提出了一種針對于火車運(yùn)動場景的規(guī)劃方案，因火車上的乘客擁有相同的移動特點(diǎn)，重疊的設(shè)計有效避免了信道擁塞問題。文獻(xiàn)［９］將重疊設(shè)計拓展到二維環(huán)境中，通過極小化極大算法來優(yōu)化信令開銷圖１簡單網(wǎng)絡(luò)模型問題，分別以最小化位置更新開銷和尋呼開銷作為兩個獨(dú)立的優(yōu)化對象，但實(shí)際上不能在總開銷上實(shí)Ｎ＝｛ＴＡＡ，ＴＡＢ，ＴＡＣ｝現(xiàn)最小化。Ａ＝｛｛ＴＡＡ｝，｛ＴＡＡ，ＴＡＢ｝，｛ＴＡＡ，ＴＡＣ｝，｛ＴＡＡ，Γ因此，出現(xiàn)了多目標(biāo)優(yōu)化算法解決位置管理開ＴＡＢ，ＴＡＣ｝｝銷問題，同時將位置更新開銷和尋呼開銷作為優(yōu)化Ａ｝，｛ＴＡＢ｝，｛ＴＡＣ｝，｛ＴＡＡ，ＴＡＢ｝，Γ＝｛｛ＴＡ對象，通過動態(tài)調(diào)整的大小，以使兩者之間實(shí)現(xiàn)最優(yōu)妥協(xié)，最小化總信令開銷［１０］。文獻(xiàn)［１１］提出一種基于種群分解策略的演進(jìn)多目標(biāo)算法（ＥｖｏｌｕｔｉｏｎａｒｙＭｕｌｔｉ?Ｏｂｊｅｃｔｉｖｅ，ＥＭＯ），文獻(xiàn)［１２］提出了一種自組織網(wǎng)絡(luò)（Ｓｅｌｆ?ＯｒｇａｎｉｚｉｎｇＮｅｔｗｏｒｋ，ＳＯＮ）｛ＴＡＡ，ＴＡＣ｝，｛ＴＡＢ，ＴＡＣ｝，｛ＴＡＡ，ＴＡＢ，ＴＡＣ｝｝１．２問題描述本地側(cè)。尋找網(wǎng)絡(luò)中每個的集合Γｉ的分配比例，以得到使位置管理開銷最小的概率分布矩陣，用Ｓ表示。其中Ｓｉｊ表示在ＴＡｉ中ｊ的分的動態(tài)規(guī)劃模型，兩個算法均是依據(jù)間的移動頻率來劃分本文提出了一種基于多目標(biāo)粒子群優(yōu)化（Ｍｕｌｔｉ?進(jìn)行最優(yōu)規(guī)劃的方案，目的是在配置與分，來。該方案分為本地側(cè)和網(wǎng)，本地側(cè)實(shí)現(xiàn)中的最優(yōu)分布，每個通過馬爾科夫鏈模型建模位置更新和尋呼產(chǎn)生的信令開銷，分別將其作為算法的一個目標(biāo)函數(shù)，當(dāng)算法收斂時找到每個中。布概率，且有∑Ｓｉｊ＝１。這一步通過算法ｊ∈Γｉ實(shí)現(xiàn)，將在第３節(jié)進(jìn)行介紹。網(wǎng)絡(luò)側(cè)。只需要根據(jù)用戶移動特性選擇合適大小的分配給ＵＥ，本文基于概率選擇策略為假設(shè)在網(wǎng)絡(luò)中用戶發(fā)生的概率記為τ１，τ２，…，τ｜Ω｜｝，尋呼概率為λ１，λ２，…，－：｛τ－：｛λ－：｛τ－：｛λλ｜Ω｜｝，其中τｕ、λｕ分別表示ＵＥｕ在當(dāng)前網(wǎng)絡(luò)中發(fā)生位置更新和尋呼的概率，Ω為用戶集。定義ＵＥｕ的移動尋呼比為γｕ＝σＰａｇｉｎｇλｕσＰａｇｉｎｇλｕ＋σＴＡＵτｕ（１）式中，σ為用戶發(fā)生一次消耗的信令數(shù)，表１ＴＡＡ的ＬＡ和ＰＡσｕ∈Ｐａｇｉｎｇ為完成一次尋呼所消耗的信令數(shù)［１４］。γ１２３４［０，１］，其值越小代表此越容易發(fā)生ＴＡＵ，為了ＬＡＡ，Ｂ，ＣＡ，ＢＡ，ＣＡ減小位置更新開銷，網(wǎng)絡(luò)側(cè)應(yīng)該分配較大的反之，其值越大，為了減少尋呼開銷應(yīng)分配較小的ＰＡ（ｊ）０．５０．２０．１０．２ΣＰＡ（ｊ）０．５０．７０．８１．０這一步將在第２節(jié)介紹。１．３多目標(biāo)算法相關(guān)概念定義１多目標(biāo)優(yōu)化問題：在ｎ維搜索空間中，ｕ＝?定義ρ１」為泊松過程的均值，記泊松γｕ最小化多目標(biāo)函數(shù)向量化公式為Ｆρｕ（ｘ），不同均值下Ｆρｕ（ｘ）ｍｉｎｆ（ｘ）＝［ｆ１（ｘ），ｆ２（ｘ），…，ｆｎ（ｘ）］ｓ．ｔ．ｇｉ（ｘ）≤０ｉ＝１，…，ｌ變化規(guī)律如圖２所示。當(dāng)ρｕ較小時，Ｆρ（ｘ）的取值ｕ在ｘ很小時就趨近于１，而當(dāng)ρｕ較大時，Ｆρ（ｘ）的ｕｘ很大時才能趨近于１。因此本文利用

ｈｊ（ｘ）＝０ｊ＝１，…，ｐ（２）這一特點(diǎn)來選擇分配，網(wǎng)絡(luò)在選擇分配之

式中，ｘ＝［ｘ１，ｘ２，…，ｘｎ］為ｎ維搜索向量，前隨機(jī)產(chǎn)生一個在［０，５０］服從均勻分布的變量ｘ，

ｇｉ（ｘ）、ｈｊ（ｘ）分別表示不等式和等式約束條件，多目標(biāo)問題就是尋找一個向量ｘ?＝［ｘ?，ｘ２，…，?ｘ?間相互沖突，所以不可能搜索到一個全局最優(yōu)解，需要由定義求出最優(yōu)解集再從解集中挑２Ｐａｒｅｔｏ，選符合條件的解。定義帕累托支配如果向量２（Ｐａｒｅｔｏ）：ａ＝［ａ，ａ，…，ａ］在所有目標(biāo)函數(shù)下取值都不大于Ｔ１２ｎ向量的取值且至少存在一個ｂ＝［ｂ，ｂ，…，ｂ］，Ｔ１２ｎ目標(biāo)函數(shù)使得向量的值嚴(yán)格小于如式ａｂ，（３）所示。ｆ（ａ）≤ｆ（ｂ）?ｉ∈｛１，２，…，ｋ｝ｉｉｆ（ａ）＜ｆ（ｂ）?ｉ∈｛１，２，…，ｋ｝（３）ｉｉ并通過定義式（４）的規(guī)則在Ｌｉ中選擇ｌ－１ｌ∑（ｘ）≤∑Ｐｉ（ｊ）（４）ｉ（ｊ）＜ＦρＰｕｊ＝１ｉ＝１那么稱向量ａ支配于向量ｂ，記為ａ?ｂ。圖２泊松過程的累積分布函數(shù)圖引理若向量ａ沒有被其他向量所支配，稱ａ為非支配解（Ｐａｒｅｔｏ最優(yōu)解），所有非支配解的集合

如當(dāng)前的γｕ較大，那么均值ρｕ就小，表示稱為帕累托前沿（Ｐａｒｅｔｏ最優(yōu)解集）。當(dāng)前移動速度慢，即尋呼過程的開銷為位置管２ＴＡＬ分配策略理開銷的主要部分，所以網(wǎng)絡(luò)側(cè)應(yīng)該盡量規(guī)劃較小的以節(jié)省信令開銷。如γｕ＝０．５，那么ρｕ＝２，本節(jié)介紹當(dāng)發(fā)起后，網(wǎng)絡(luò)側(cè)如何根據(jù)每個用戶的移動尋呼比在Γｉ中選擇大小合適的Ｆρｕ（ｘ）取值為１的概率約為０．９５，由式（４）會在Ｌｉ中選擇ΣＰＡ（ｊ）較大的ｊ，即包含數(shù)量較分配。少的可見此策略實(shí)現(xiàn)了按用戶的移動尋呼比由第１節(jié)分析可知，Γｉ中包含的數(shù)量在集合中選擇大小合適的且實(shí)現(xiàn)較為可能不同，記Ｌｉ表示按從大到小排序后的集

容易。合。并用概率Ｐｉ（ｊ）表示在Ｌｉ中ｊ的概率，其值等于Ｓｉｊ。以圖１中的ＴＡＡ舉例說明，假設(shè)本地側(cè)算３ＴＡＬ最優(yōu)規(guī)劃策略法輸出的概率分配向量ＬＢ如表１所示，如用戶移動傳統(tǒng)的多目標(biāo)算法規(guī)劃時，幾乎都是將位到ＴＡＡ中時發(fā)起此時網(wǎng)絡(luò)側(cè)選擇１＝置更新和尋呼開銷通過加權(quán)和的方式轉(zhuǎn)化為單目標(biāo)｛ＴＡＡ，ＴＡＢ，ＴＡＣ｝分配的概率為０．５。算法解決，并不能在兩沖突目標(biāo)之間取得平衡，達(dá)到最優(yōu)［１１－１２］。所示。本節(jié)介紹利用算法分別將開銷和ｘｉ，ｊ（ｔ）＝ｖｉ，ｊ（ｔ）＋ｘｉ，ｊ（ｔ－１）（７）尋呼開銷作為目標(biāo)函數(shù)，尋找使兩目標(biāo)之間妥協(xié)的步驟４更新局部最優(yōu)解。由定義２計算當(dāng)前最優(yōu)概率分布矩陣Ｓ。候選解與歷史最優(yōu)解之間的支配關(guān)系，若ｘｉ，ｊ（ｔ）?３．１算法原理ｘｉ，ｊ（ｔ）＝ｅｓｔ（ｔ－１），則有ｘｐｂｅｓｔｉ，ｊ（ｔ）＝ｘｉ，ｊ（ｔ），否則ｘｐｂｅｓｔ粒子群算法（ＰａｒｔｉｃｌｅＳｗａｒｍｘｅｓｔ（ｔ－１）。ＰＳＯ）是一種啟發(fā)式算法，最初是受到鳥群在自然

循環(huán)２環(huán)境中的社交行為鼓舞而誕生的［１５］。在ＰＳＯ算

５更新外部檔案。利用此次迭代產(chǎn)生的法中，每次粒子更新位置（候選解）時，通過自身的

Ｐａｒｅｔｏ最優(yōu)解集更新外部檔案，如果解數(shù)量超過歷史最優(yōu)位置和種群的全局最優(yōu)位置來調(diào)整粒子ＮＲ，則粒子密度較大的網(wǎng)格中篩除掉多余粒子。當(dāng)前的位置，以使候選解朝著最優(yōu)解進(jìn)化。為了

循環(huán)１避免粒子在搜索過程中陷入局部最優(yōu)解，依據(jù)文

６生成Ｐａｒｅｔｏ前沿。迭代次數(shù)達(dá)到Ｉｔ以獻(xiàn)［１６］提出的自適應(yīng)網(wǎng)格劃分法，通過此方法管

后，此時外部檔案中的解即為Ｐａｒｅｔｏ前沿。理每個網(wǎng)絡(luò)中非支配解的數(shù)量，如果超過閾值就

３．１．２篩選最優(yōu)解篩選出多余的粒子。當(dāng)算法迭代結(jié)束后，會生成一組Ｐａｒｅｔｏ３．１．１算法流程最優(yōu)解集（Ｐａｒｅｔｏ前沿），在如圖３所示二維目標(biāo)空（１）初始化。初始化種群大小為Ｎｐ、外部檔案間中，曲線上的點(diǎn)表示Ｐａｒｅｔｏ最優(yōu)解，其在前沿上移閾值為ＮＲ、算法最大迭代次數(shù)為Ｉｔ。在目標(biāo)空間動必然會導(dǎo)致一個目標(biāo)函數(shù)減小，另一個目標(biāo)函數(shù)中隨機(jī)生成ＮＰ個初始粒子，包括粒子的位置向量增加，如Ａ點(diǎn)向Ｂ點(diǎn)移動，會使ｆ２（ｘ）減小，ｆ１（ｘ）ｘｉ＝（ｘｉ，１，ｘｉ，２，…，ｘｉ，Ｐ）Ｔ、速度向量ｖｉ＝增加。（ｖｉ，１，ｖｉ，２，…，ｖｉ，Ｐ）Ｔ，其中Ｐ代表每個粒子的參數(shù)個數(shù)，位置向量ｘｉ也被稱為候選解。（２）主程序。尋找Ｐａｒｅｔｏ最優(yōu)解集。循環(huán)１迭代次數(shù)小于Ｉｔ。循環(huán)２更新種群中的粒子。步驟１篩選全局最優(yōu)解：在外部檔案中，從密度較小的網(wǎng)格中隨機(jī)選擇一個Ｐａｒｅｔｏ最優(yōu)解作為全局最優(yōu)解。步驟２更新粒子的速度，如式（５）所示。ｖｉ，ｊ（ｔ）＝ｗ（ｔ）ｖｉ，ｊ（ｔ－１）＋ｃ１ｒａｎｄ１（ｘｉ，ｊ（ｔ－１）－ｘｉ，ｊ（ｔ－１））＋ｐｂｅｓｔ圖３帕累托最優(yōu)前沿及其支配關(guān)系圖ｃ２ｒａｎｄ２（ｘｉ，ｊ（ｔ－１）－ｘｉ，ｊ（ｔ－１））（５）ｇｂｅｓｔ由于本文后面計算位置管理開銷同為二維目標(biāo)空間，且需要在Ｐａｒｅｔｏ前沿上找到使得ｆ１（ｘ）＋

式中，ｖｉ，ｊ（ｔ）表示粒子ｉ在第ｔ次迭代中的速度，ｊ∈Ｐ；ｗ（ｔ）表示慣性權(quán)重因子，為了使粒子群收斂，則２（ｘ）最小的點(diǎn)。本文定義式（８）、式（９）選擇“最優(yōu)ｆ權(quán)重因子應(yīng)該小于１，本文定義ｗ（ｔ）如式（６）所示，

”，計算每個Ｐａｒｅｔｏ解的最佳妥協(xié)解因子ξｍ，式中ｗ（ｔ）∈［ｗｍｉｎ，ｗｍａｘ］；ｘｉ，ｊ（ｔ－１）表示粒子ｉ的ｐｂｅｓｔｍ∈｛１，２，…，Ｍ｝，Ｍ表示解集大小。，ｘｉ，ｊ（ｔ－１）為步驟１篩選的全局最優(yōu)ｇｂｅｓｔ解；ｃ１為局部最優(yōu)解學(xué)習(xí)因子，ｃ２為全局最優(yōu)解學(xué)ξｉｆｉａｘ（ｘ）－ｆｉ（ｘｍ）ｉ∈｛１，２，…，ｋ｝（８）ｆｍａｘｍｉｎｉ（ｘ）－ｆｉ（ｘ）習(xí)因子；ｒａｎｄ１、ｒａｎｄ２為［０，１］中的隨機(jī)數(shù)，以保證種群進(jìn)化中的多樣性。?ｗ（ｔ）＝ｗｍａｘ－?èｔ×（ｗｍａｘ－ｗｍｉｎ）?÷（６）Ｉ?ｔξｍ＝ｋ∑ｉξｍｉ＝１ｍ∈｛１，２，…，Ｍ｝（９）Ｍｋ∑∑ｉξｍｍ＝１ｉ＝１步驟３更新粒子的位置（候選解），如式（７）式中，ｋ表示目標(biāo)函數(shù)個數(shù)，在圖３中ｋ＝２；ｆｉ（ｘ），ｍａｘｆｉｉｎ（ｘ）表示在前沿上各個目標(biāo)函數(shù)的最大值和最通過算法搜索Ｓｏｐｔ的偽代碼如算法１小值（邊界解）。最終取ξｍ值最大的解為最佳妥協(xié)解Ｓｏｐｔ，如圖３中的Ｃ點(diǎn)。３．２實(shí)現(xiàn)的最優(yōu)規(guī)劃本節(jié)將介紹本地側(cè)如何利用算法尋找各個中的分布概率，算法輸出將產(chǎn)生一個概率分布矩陣Ｓ。所示。初始化時隨機(jī)生成一組滿足約束條件的候選解向量，每個候選解對應(yīng)一個概率矩陣Ｓ。算法迭代結(jié)束生成Ｐａｒｅｔｏ前沿，此時前沿上有多個滿足條Ｓ，此時通過式（８）、式（９）計算妥協(xié)解因子選出最大的作為算法輸出，即ｆ１（Ｓ）＋ｆ２（Ｓ）最小的解向量Ｓｏｐｔ。算法１基于的最優(yōu)規(guī)劃算法為了便于目標(biāo)函數(shù)表示，引入兩個假設(shè)。１：ｘｉ、ｖｉ，ｉ∈Ｎｐ假設(shè)１：由ＴＡｉ移動到ＴＡｊ的數(shù)量為ｈｉｊ，記Ｈ表示不同間移動的用戶數(shù)，ｈｉｊ的值可以通過統(tǒng)計不同基站或移動管理實(shí)體（ＭＭＥ）之間的２：ｍ＝１：Ｉｔ３：ｉ＝１：Ｎｐ４：ｘｇｂｅｓｔｉ，ｊ（ｍ－１）：５：ｖｉ，ｊ（）、ｘｉ，ｊ（）：（５，７）切換消息獲得［１７］。假設(shè)２：所有用戶的呼叫率相同，均為λｃ。６：ｆ１（ｘｉ）、ｆ２（ｘｉ）：（１０，１１）７：ｘｉｊｅｓｔ（）：８：在上文的分析中，位置更新開銷和尋呼開銷是９：一對隨大小不同呈現(xiàn)相互沖突的目標(biāo)，因此可１０：（ＮＲ）分別作為兩個目標(biāo)函數(shù)進(jìn)行優(yōu)化。根據(jù)矩陣Ｓ，定１１：１２：義粒子候選解向量為ｘｉ＝［Ｓ１，Ｓ２，…，ＳＮ］Ｔ＝［ｘｉ，１，ｘｉ，２，…，ｘｉ，Ｐ］Ｔ為Ｐ＝Ｎ｜Γ｜維的向量，其中１４：ξｍ，ξｍ，ξｍ：（８～９）２Ｓｉ＝［Ｓｉ，１，Ｓｉ，２，…，Ｓｉ，｜｜］，ｉ∈Ｎ為Ｓ的行向量，表示１５：Ｓｏｐｔ，ξｍ４模型分析ＴＡｉ中各個的分配概率。算法中，目標(biāo)函數(shù)及約束條件分別定義為目標(biāo)函數(shù)：ｆｊｉＳｊｌ１（Ｓ）＝σＴＡＵ∑∑(∑ｉｊＳｉｌ＋∑)ｈｈ１（Ｓ）＝σＴＡＵ∑∑(∑ｉｊＳｉｌ＋∑)ｌ∈ｉｌ?ｊｌ∈ｊｌ?ｉｉ∈Ｎｊ∈Ｎｉ≠ｊ（１０）ｆＳη２（Ｓ）＝λｃσＰａｇｉｎｇ∑∑ｉｌηｉ＋∑)２（Ｓ）＝λｃσＰａｇｉｎｇ∑∑ｉｌηｉ＋∑)ｊｌ∈ｉｉ∈Ｎｊ∈ｌｉ≠ｊ（１１）約束條件：｜ｉ｜?ｉ∈Ｎ，∑Ｓｉｌ＝１（１２）ｌ＝１在本節(jié)中，將通過馬爾科夫鏈模型分析二維網(wǎng)絡(luò)結(jié)構(gòu)中的位置管理開銷。假設(shè)在不同ＴＡｊ中的駐留時間ｔＴＡｊ，滿足均值為１／τｊ的指數(shù)分布［１３］，記為ｔＴＡｊ～ＥＸＰ（τｊ）。假設(shè)每個在兩次呼叫間隔時間ｔｃ滿足均值為１／λｃ的指數(shù)分布［１８］，記為ｔｃ～ＥＸＰ（λｃ）。其次，認(rèn)為通過基站或已經(jīng)知道了ＴＡｉ到ＴＡｊ的移動數(shù)量，那么可以計算出從ＴＡｉ移動到ＴＡｊ的概率為ｐｉ，ｊ＝ｈｉｊ∑ｈｉｊｊ∈Ｎ，ｊ≠ｉ（１５）?ｌ∈Γ，?ｉ∈Ｎ∩ｌ≤Ｓｉｌ≤１（１３）?ｌ∈Γ，?ｉ?Ｎ∩ｌ，Ｓｉｌ＝０（１４）４．１馬爾科夫鏈分析，考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖４所示，圖中所有可能的有（１０）表示整個網(wǎng)絡(luò)中，用戶在不同間移Γ＝｛｛ＴＡ１｝，｛ＴＡ２｝，｛ＴＡ３｝，｛ＴＡ１，ＴＡ２｝，動時產(chǎn)生的總開銷，其中ｌ∈ΓｉΛｌ?Γｊ表示用｛ＴＡ１，ＴＡ３｝，｛ＴＡ２，ＴＡ３｝，｛ＴＡ１，ＴＡ２，ＴＡ３｝｝戶從ＴＡｉ移動到ＴＡｊ，且兩個不屬于同一按順序編號為１～７。那么本地側(cè)概率分布矩陣式（１１）表示在整個網(wǎng)絡(luò)中尋呼不同中的用戶所Ｓ為１２３４５６７，其中ηｉ表示在ＴＡｉ中包含的小區(qū)個數(shù)，括號內(nèi)為尋呼ＴＡｉ的用戶時會向其所在的整個發(fā)起尋呼。式（１２）～（１４）表示矩陣Ｓ中的概率約束條件。Ｓ＝ＴＡ１ＴＡ２ＴＡ３éùＳ００ＳＳ０Ｓêúê０Ｓú０Ｓ０ＳＳêúêú００Ｓ０ＳＳＳ??α，ＴＡｘ→ＴＡｙ，ｘ，ｙ，ｗ＝Ｐｒ（ｔｃ＞ｔｘＴＡｘ∈ＴＡＬｗ，ＴＡｙ∈ＴＡＬｗ）＝Ｐｒ（ｔｘ，ｙＳｙｗ（１７）ｃ＞ｔ）ｐｘβｘ，ｙ，ｗ＝Ｐｒ（ｔｃ＞ｔ，ＴＡｘ→ＴＡｙ，ｘＴＡｘ?ＴＡＬｗ，ＴＡｙ∈ＴＡＬｗ）＝Ｐｒ（ｔｃ＞ｔ）ｐｘ，ｙＳｙｗ（１８）ｘγｘ＝Ｐｒ（ｔｃ＜ｔ）（１９）ｘ其中圖馬爾科夫鏈模型分析用例４在馬爾科夫鏈中，用狀態(tài)Ｋｘ，ｗ表示處于Ｐｒ（ｔｃ＞ｔ）＝ｘτｘτｘ＋λｃＴＡＬｗ內(nèi)的ＴＡｘ中，ｘ∈｛１，２，３｝，ｗ∈｛１，２，…，７｝。記Ｋ為狀態(tài)空間Ｐｒ（ｔｃ＜ｔ）＝ｘλｃτｘ＋λｃ（２０）Ｋ＝｛Ｋ１，１，Ｋ１，４，Ｋ１，５，Ｋ１，７，Ｋ２，２，Ｋ２，４，記πＫｙ，ｗ為狀態(tài)Ｋｙ，ｗ的穩(wěn)態(tài)概率，那么根據(jù)式Ｋ２，６，Ｋ２，７，Ｋ３，３，Ｋ３，５，Ｋ３，６，Ｋ３，７｝（１６）（１７）～（１９）３種狀態(tài)轉(zhuǎn)移概率，得到Ｋｘｗ狀態(tài)中的有兩種情況會發(fā)生狀態(tài)。（１）從ＴＡｘ移動到ＴＡｙ（ｘ≠ｙ）。此時如果ＴＡｙ∈ＴＡＬｗ，進(jìn)入狀態(tài)Ｋｙｗ；如果πＫｙ，ｗ＝γｙπＫｙ，ｗ＋∑ｘ，ｙ，ｗ∑Ｋｘ，ｖ＋∑βπαｘ，ｙ，ｗπｘ，ｗＳｘｗ＝０，ＳｘｖＳｘｗｐｘ，ｙＳｙｖ＝０ｐｘ，ｙｘ≠ｙｘ≠ｙＴＡｙ∈ＴＡＬｖ（ｖ≠ｗ），進(jìn)入狀態(tài)Ｋｙｖ。（２）移出（２１）所以可寫出狀態(tài)空間Ｋ的穩(wěn)態(tài)概率轉(zhuǎn)移矩陣。用αｘｙｗβｘｙｗγｘ。ＰＫ為Ｋ１，１Ｋ１，４Ｋ１，５Ｋ１，７Ｋ２，２Ｋ２，４Ｋ２，６Ｋ２，７Ｋ３，３Ｋ３，５Ｋ３，６ＫＰＫ＝ＫＫＫＫＫＫＫＫＫＫＫＫéùγ１０００β０β０β０β０êú０γ１００βαβ０β０β０êúêú００γ１０β０β０βαβ０êú０００γ１β０βαβ０βαêúêβ０β０γ２０００ββ００úêúβαβ００γ２００ββ００êúêβ０β０００γ２０ββα０úêúβ０βα０００γ２ββ０αêúββ００ββ００γ３０００êúêúββα０ββ０００γ３００êúββ００ββα０００γ３０êúêúββ０αββ０α０００γ３??定義πＫ表示狀態(tài)空間Ｋ的穩(wěn)態(tài)概率向量，有在狀態(tài)空間Ｋ中期望尋呼數(shù)為Ｋ＝πＫＰＫ，∑πＫｘ，ｗ＝１（２２）πＫｘ，ｗ∈Ｋ４．２信令開銷分析Ｐａｇｉｎｇ，ｔｃ＝∑(ｘ∑)（２４）ｊＮπＫｘ，ｗγηＫｘ，ｗ∈Ｋｊ∈ｗ式中ηｊ表示在ＴＡｊ中所包含的小區(qū)個數(shù)。由前面分析可知，只有當(dāng)用戶移出邊界時所以，位置管理總開銷為才會發(fā)起過程，所以在狀態(tài)空間Ｋ中的Ｃｔ＝ＮＴＡＵ，ｔσ＋ＮＰａｇｉｎｇ，ｔσＰａｇｉｎｇ（２５）ｃｃ期望次數(shù)為，σＴＡＵ、σＰａｇｉｎｇ分別為側(cè)完成一次和尋＝∑(Ｋｘ，ｖ∑)（２３）Ｎπβｘ，ｙ，ｗＫｘ，ｖ∈ＫＫｙ，ｗ∈Ｋ，ｗ≠ｖ，ｘ≠ｙ呼過程所消耗的信令數(shù)。５性能仿真與分析其次，本文尋呼策略為并行尋呼，即網(wǎng)絡(luò)側(cè)每次呼叫會向整個的所有小區(qū)發(fā)起尋呼消息，所以本文仿真從兩方面評估所提方案的性能，其一是驗(yàn)證算法是否在開銷和尋呼信令開Ｐａｇｉｎｇ，并與式（２３）和式（２４）推導(dǎo)的理論值進(jìn)行比Ｎ銷之間得到妥協(xié)，這一步通過與單目標(biāo)優(yōu)化算法進(jìn)較，其中誤差值表示理論值與分析值的絕對差值與行比較驗(yàn)證；其二是分析本文方案在減少信令開銷理論值的百分比，通過表３可知，誤差值均小于２％，上的優(yōu)勢。仿真時采用如圖４所示的拓?fù)鋱D，并設(shè)驗(yàn)證了本文公式理論推導(dǎo)的合理性。不同間的移動概率為Ｐ＝éù００．１０．９êúêú０．５００．５êú??０１０其次的移動速度通過尋呼移動比τ／λｃ模擬，即的呼叫率和駐留時間均值的比值，如果τ／λｃ越小，表示移動性較弱，發(fā)生概率較小，反之認(rèn)為移動性較強(qiáng)。其他仿真參數(shù)如表２所示。表２移動性管理中的仿真參數(shù)圖５迭代次的最優(yōu)解搜索圖σＴＡＵσＰａｇｉｎｇ１ηＮｐＮＲＩｔｃ１、ｃ２２ｗｍｉｎ０．４ｗｍａｘ０．９圖５是在τ／λｃ＝１０，Ｉｔ＝時算法在圖６迭代次的帕累托最優(yōu)解集圖開銷和尋呼開銷兩個目標(biāo)之間的搜索圖，從圖中可以看出，算法輸出Ｐａｒｅｔｏ最優(yōu)解是一簇點(diǎn)，驗(yàn)證了兩者之間的矛盾關(guān)系，其中紅點(diǎn)表示在Ｐａｒｅｔｏ前表３ＮＴＡＵＮＰａｇｉｎｇ的理論值與分析值對比ＮＴＡＵＮＰａｇｉｎｇ６７３．１５１１０３．７１（８）和式（９）篩選出的最優(yōu)妥協(xié)解Ｓｏｐｔ。６６４．５０１０８２．４５在Ｉｔ＝時，Ｐａｒｅｔｏ前沿上解的數(shù)量只有個，且誤差／％１．３０１．９６，通過實(shí)驗(yàn)當(dāng)設(shè)置Ｉｔ＞時，算法輸ＮＲ，圖６是在Ｉｔ＝時的Ｐａｒｅｔｏ５．１妥協(xié)性分析前沿，可見算法已經(jīng)穩(wěn)定。本節(jié)通過與文獻(xiàn)［９］中的極小化極大算法作比為了驗(yàn)證本文公式推導(dǎo)的正確性，這里采用蒙較，其中優(yōu)化開銷的算法記為Ｆ?ＴＡＵ，優(yōu)化尋特卡洛仿真方法模擬用戶在中的移動特呼開銷的算法記為Ｆ?Ｐａｇｉｎｇ，且網(wǎng)絡(luò)尋呼開銷和性［１２］通過生成Ｍ１個隨機(jī)數(shù)模擬不同的ＵＥ，并針開銷上限約束均設(shè)為４×１０４。依次生成Ｍ２個隨機(jī)數(shù)模擬沿不在圖７中，討論不同τ／λｃ下信令開銷之間的差

Ｍ２次，本文?。停薄ⅲ停簿鶠椋埃埃?，以模別由圖７（ａ）可見開銷隨τ／λｃ遞增，這是因?yàn)閿M出在不同之間的移動率。表３是在在式（１８）中，隨著τ／λｃ增大，βｘ，ｙ，ｗ變大，那么式τ／λｃ＝２５、η＝時，通過比較蒙特卡洛仿真計算出（２３）中開銷將增大。其次可見在減小

的呼叫時間間隔內(nèi)的位置更新數(shù)ＮＴＡＵ、尋呼消息數(shù)開銷上性能最好，因其規(guī)劃的較大。由圖時，ＭＯＰＳＯ算法的性能接近于Ｆ?ＴＡＵ，可見該算法始終處于兩種單目標(biāo)優(yōu)化算法的折中位置。所以用戶在不同移動場景下，本文算法能夠在位置更新和尋呼信令開銷之間取得很好的妥協(xié)，驗(yàn)證了本文算法的有效性。圖８為本文各信令開銷隨τ／λｃ的變化趨勢，由圖可見，總信令開銷先遞減后遞增，因?yàn)樵讦樱耍爿^小時，尋呼開銷較大開銷較小，而隨著τ／λｃ增大，尋呼開銷減小，ＴＡＵ開銷變成總信令開銷的主要部分。圖８速度對模型中信令開銷的影響５．２總開銷性能對比圖９表示本文算法和文獻(xiàn)［１１］的算法和文獻(xiàn)［１２］的算法的總信令開銷對比。算法強(qiáng)調(diào)的是將自然環(huán)境中移動行為弱的區(qū)域劃分到不同中，以減小開銷，從而使總開銷最小。但對的過分考慮，以及欠缺重疊設(shè)計，會使尋呼開銷呈現(xiàn)負(fù)優(yōu)化的作用，由圖９可見，相比算法在不同τ／λｃ下，總開銷減少約２６．６２％～３６．９１％。算法將開銷和尋呼開銷利用加權(quán)和的方式轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，同時將移動性圖７速度對信令開銷的影響７（ｂ）可見尋呼開銷隨τ／λｃ遞減，在式（１９）中τ／λｃ在增大，γ在變小，所以式（２４）中的尋呼開銷必然減小。其次Ｆ?Ｐａｇｉｎｇ在減小尋呼開銷上性能最好，因?yàn)樗惴ㄝ敵鰰r包含的數(shù)較少。由圖７（ｃ）可見，在τ／λｃ≤時，ＭＯＰＳＯ算法的總信令開銷性能接近于Ｆ?Ｐａｇｉｎｇ，而在τ／λｃ＞圖９本文算法和其他算法的總信令開銷比較較強(qiáng)的小區(qū)規(guī)劃到同一中，可以最大化地減小在τ／λｃ≤總信令開銷減小約１１．５４％～１８．７５％，而τ／λｃ＞。ｕｓｅｒｓ［Ｊ］．２９０－３０４．［７］ＳＳ，Ｍ，ＱＱ，ａｌ