第三章 個(gè)體移動(dòng)預(yù)測(cè)

1、個(gè)體移動(dòng)過程中終端切換技術(shù)研究隨著新型業(yè)務(wù)與應(yīng)用的不斷出現(xiàn)，異構(gòu)網(wǎng)絡(luò)下的終端融合已成為信息與通信技術(shù)發(fā)展的必然趨勢(shì)，是支撐現(xiàn)代服務(wù)業(yè)應(yīng)用與發(fā)展的前提與基礎(chǔ)。根據(jù)多接入、多終端環(huán)境的要求，如何構(gòu)建智能終端，實(shí)現(xiàn)虛擬終端系統(tǒng)內(nèi)終端的有效預(yù)測(cè)切換，減小切換失敗概率和分組丟失率，成為亟待解決的關(guān)鍵問題。有關(guān)異構(gòu)網(wǎng)絡(luò)選擇和切換的研究目前已經(jīng)非常廣泛，并已取得了不少成果。文獻(xiàn)8提出基于Elman神經(jīng)網(wǎng)絡(luò)的自適應(yīng)網(wǎng)絡(luò)選擇算法，其將用戶數(shù)量、帶寬成本、用戶的移動(dòng)速度作為代價(jià)函數(shù)，選擇最佳的接入方式訪問當(dāng)前的網(wǎng)絡(luò)。文獻(xiàn)9提出了基于模糊邏輯的網(wǎng)絡(luò)選擇算法，其考慮的因素包括接收信號(hào)強(qiáng)度、用戶移動(dòng)速度和網(wǎng)絡(luò)吞吐量等，

2、但面臨網(wǎng)絡(luò)參數(shù)全面性、模糊數(shù)據(jù)配置量大、需要較長(zhǎng)的學(xué)習(xí)過程等問題。選最好的網(wǎng)絡(luò)實(shí)際上是一個(gè)典型的多目標(biāo)決策過程。通常采用多屬性決策（Multiple Attribute Decision Making，MADM）方法，例如SAW10、GRA11、ELECTRE12、TOPSIS13、AHP14、WMC15等。采用多屬性決策理論計(jì)算網(wǎng)絡(luò)參數(shù)的權(quán)重，然后從多個(gè)可用的網(wǎng)絡(luò)中選擇最優(yōu)網(wǎng)絡(luò)。然而每個(gè)接入網(wǎng)絡(luò)所有屬性不可能同時(shí)達(dá)到最優(yōu)，一個(gè)無線網(wǎng)絡(luò)的所有屬性可以通過權(quán)重設(shè)置來達(dá)到目標(biāo)的總體性能最優(yōu)的狀態(tài)。已有算法針對(duì)單個(gè)終端穿越多個(gè)網(wǎng)絡(luò)時(shí)，選擇一個(gè)最佳的網(wǎng)絡(luò)用于垂直切換。（開題報(bào)告）但是終端選擇切換的研究

3、還相對(duì)較少，因?yàn)榇蟛糠值漠悩?gòu)網(wǎng)絡(luò)環(huán)境假設(shè)用戶只有一個(gè)終端?，F(xiàn)有的研究多考慮基于終端位置或電池供電的終端接口選擇問題。文獻(xiàn)16提出了一個(gè)終端切換的方案，即其解決的是異構(gòu)網(wǎng)絡(luò)環(huán)境中不同用戶終端的選擇問題，而不是單個(gè)用戶的多終端管理。文獻(xiàn)17提出一種基于端到端的可重構(gòu)系統(tǒng)的動(dòng)態(tài)閾值的聯(lián)合負(fù)載控制方法，但方案的選擇是實(shí)現(xiàn)小區(qū)內(nèi)或網(wǎng)絡(luò)內(nèi)用戶終端的選擇。（開題）文獻(xiàn)293031都對(duì)切換觸發(fā)時(shí)間選擇問題進(jìn)行了研究，然而它們只考慮了用戶終端接收到當(dāng)前服務(wù)網(wǎng)絡(luò)信號(hào)強(qiáng)度的影響，在網(wǎng)絡(luò)覆蓋狀況變化的環(huán)境下，它們并不能實(shí)現(xiàn)為用戶選擇最佳切換觸發(fā)時(shí)間的目的。本文中，我們綜合考慮用戶多終端接收到當(dāng)前服務(wù)網(wǎng)絡(luò)和切換目標(biāo)網(wǎng)絡(luò)

4、的信號(hào)強(qiáng)度，在采用馬爾科夫模型預(yù)測(cè)的基礎(chǔ)上，提出了一種基于馬爾科夫模型移動(dòng)預(yù)測(cè)的切換觸發(fā)時(shí)間選擇方法。（Y-M）場(chǎng)景描述與系統(tǒng)架構(gòu)場(chǎng)景描述根據(jù)實(shí)際情況，我們構(gòu)建這樣一個(gè)場(chǎng)景（如圖3.1所示）：用戶隨身攜帶幾臺(tái)終端，如Pad、移動(dòng)電話、照相機(jī)等，用戶要體驗(yàn)?zāi)撤N在線業(yè)務(wù)，并且用戶處于低速移動(dòng)狀態(tài)，當(dāng)用戶位置變化時(shí)，各終端的所接收到的信號(hào)強(qiáng)度也在變化，如果能夠提前預(yù)測(cè)用戶移動(dòng)信息，選擇最佳觸發(fā)切換時(shí)間，那么將會(huì)大大減小切換失敗率和丟包率，為用戶提供更好的服務(wù)。圖3.1 單個(gè)用戶多個(gè)終端組成虛擬終端系統(tǒng)示意圖系統(tǒng)模型為了使研究簡(jiǎn)單化，我們假設(shè)GSM是網(wǎng)絡(luò)1，WiMAX是網(wǎng)絡(luò)2，用戶攜帶兩個(gè)終端，也就是

5、該虛擬終端系統(tǒng)有兩個(gè)單模終端組成，終端TG接入GSM網(wǎng)絡(luò)，終端TW接入WiMAX網(wǎng)絡(luò)。用戶以恒定的速度v離開BS1點(diǎn)向BS2點(diǎn)移動(dòng)，系統(tǒng)模型架構(gòu)如圖3.2所示。圖3.2 用戶移動(dòng)過程中終端接收網(wǎng)絡(luò)信號(hào)強(qiáng)度示意圖在個(gè)體用戶移動(dòng)過程中，各個(gè)終端所在網(wǎng)絡(luò)覆蓋狀況在不停地變化，終端之間往往需要進(jìn)行切換來保證個(gè)體用戶正在進(jìn)行業(yè)務(wù)的連續(xù)性。此外，當(dāng)用戶的需求發(fā)生變化時(shí)，終端之間也需要進(jìn)行相應(yīng)的切換。與接入網(wǎng)絡(luò)選擇不同，切換機(jī)制的研究主要解決切換目標(biāo)網(wǎng)絡(luò)選擇和切換觸發(fā)時(shí)間選擇等問題，即如何在保證成功切換的前提下使用戶業(yè)務(wù)的分組丟失最小化。因此，我們對(duì)切換觸發(fā)時(shí)間選擇做最優(yōu)化建模：min Pploss(t)

6、（3.1）s.t. Phft=0（3.2）其中，Pploss(t)是用戶業(yè)務(wù)在t時(shí)刻觸發(fā)切換時(shí)的分組丟失率，Phft是在t時(shí)刻觸發(fā)切換時(shí)切換失敗的概率。假設(shè)用戶在t時(shí)刻與BS1的距離為d1，與BS2的距離為d2，BS1和BS2之間距離為l，則d2=l-d1，此外，為了評(píng)估切換算法性能，應(yīng)該考慮信道模型和移動(dòng)模型。在分析架構(gòu)中，采用典型的Log-linear路徑損耗模型。終端TG和TW接收到2個(gè)網(wǎng)絡(luò)的信號(hào)強(qiáng)度值RSS（dB）分別為 RSSgt=Pgd1+fg,1=Pgvt+fg,1 （3.3）RSSwt=Pwd2+fw,2=Pwl-vt+fw,2 （3.4）其中，Pgd1為終端TG與BS1距離為

7、d1時(shí)接收到網(wǎng)絡(luò)1的平均功率；Pwd2為終端TW與BS2距離為d2時(shí)接收到網(wǎng)絡(luò)2的平均功率；fg,1和fw,2為零均值，標(biāo)準(zhǔn)方差分別為1和2的高斯隨機(jī)變量，代表陰影衰落。我們定義接收靈敏度為終端在該網(wǎng)絡(luò)下可以接收到并仍能正常工作的最低信號(hào)強(qiáng)度，它是一個(gè)功率電平，通常用dBm表示。假設(shè)終端TG在GSM中的接收靈敏度為Pgth,終端TW在WiMAX中的接收靈敏度為Pwth， 兩個(gè)終端執(zhí)行切換所需要的時(shí)間為Th。如果不考慮陰影衰落等因素造成的接收信號(hào)強(qiáng)度波動(dòng)，即fg,1=fw,2=0。那么RSSgt為單調(diào)遞減函數(shù)，RSSwt為單調(diào)遞增函數(shù)。又上圖可知，為了避免終端之間切換失敗，終端TG和TW必須在T

8、1=TLG-Th和T2=TLW-Th之間觸發(fā)切換，其中，TLG為終端TW接收到網(wǎng)絡(luò)2的信號(hào)強(qiáng)度值恰好上升到Pwth的時(shí)間，TLW為終端接收到網(wǎng)絡(luò)1的信號(hào)強(qiáng)度值恰好下降到Pgth的時(shí)間。即切換觸發(fā)時(shí)間t必須滿足T1tT2 （3.5）用戶業(yè)務(wù)的分組丟失是由于終端接收到網(wǎng)絡(luò)的信號(hào)強(qiáng)度小于終端的接收靈敏度所導(dǎo)致的。在網(wǎng)絡(luò)1中，終端TG接收到的信號(hào)強(qiáng)度值為RSSgt=Pgvt+fg,1，由于fg,1服從均值為0、標(biāo)準(zhǔn)方差為1的正態(tài)分布，因此RSSgt<Pgth的概率為PRSSgt<Pgth=-Pgth-Pgvte-x221212dx （3.6）同理有PRSSwt<Pwth=-Pwth-

9、Pwl-vte-x222222dx （3.7）為了保證成功切換，兩個(gè)終端需要在T1,T2之間觸發(fā)切換，此時(shí)用戶業(yè)務(wù)丟失由兩部分組成：網(wǎng)絡(luò)1中切換完成前的分組丟失和網(wǎng)絡(luò)2中切換完成后的分組丟失。假設(shè)終端TG和TW在t時(shí)刻觸發(fā)切換，用戶的分組丟失概率可以表示為：Pplosst=T1t+Th-Pgth-Pgvye-x221212dxdy+ t+ThT2-Pwth-Pwl-vye-x222222dxdy T2-T1（3.8）所建立的最優(yōu)化模型可轉(zhuǎn)化為min Pplosst=T1t+Th-Pgth-Pgvye-x221212dxdy+ t+ThT2-Pwth-Pwl-vye-x222222dxdy T2

10、-T1（3.9）s.t. tT1 （3.10）tT2 （3.11）算法設(shè)計(jì)將目標(biāo)函數(shù)對(duì)t求導(dǎo)可得：dPplosstdt=1T2-T1×-Pgth-Pgvt+The-x221212dx -Pwth-Pwl-vt+The-x222222dx （3.12）繼續(xù)對(duì)t求導(dǎo)可得：d2Pplosstdt2=1T2-T1e-Pgth-Pgvt+Th221212-dPgvt+Thdt-1T2-T1e-Pwth-Pwl-vt+Th222222-dPwl-vt+Thdt （3.13）由于已假設(shè)用戶速度v是恒定的，所以Pgvt+Th是關(guān)于t的單調(diào)遞減函數(shù)，Pwl-vt+Th是關(guān)于t的單調(diào)遞增函數(shù)，在上述式子

11、中，dPgvt+Thdt<0，dPwl-vt+Thdt>0，那么d2Pplosstdt2>0恒成立。由凸優(yōu)化理論可知上述最優(yōu)化問題是一個(gè)凸問題。那么我們令dPplosstdtt=ttri=0，其中ttri為理論上最佳切換觸發(fā)時(shí)間，則根據(jù)式（3.12）可得：-Pgth-Pgvttri+The-x221212dx =-Pwth-Pwl-vttri+The-x222222dx 此外，考慮到網(wǎng)絡(luò)1和網(wǎng)絡(luò)2是相鄰網(wǎng)絡(luò)，那么地理環(huán)境對(duì)它們影響也基本相同，終端TG和TW分別接收到其對(duì)應(yīng)網(wǎng)絡(luò)基站信號(hào)強(qiáng)度受到陰影衰落影響基本相同，故可以假設(shè)認(rèn)為1=2，可得Pgth-Pgvttri+Th=Pwt

12、h-Pwl-vttri+Th（3.15）由圖3.2可知，終端TW在TLU時(shí)刻接收到網(wǎng)絡(luò)2的信號(hào)強(qiáng)度值恰好上升到Pwth，也恰好是該網(wǎng)絡(luò)的接收靈敏度，那么有Pwl-vTLU=Pwth，而此時(shí)終端TG還在網(wǎng)絡(luò)1的覆蓋范圍內(nèi)，同理有PgvTLUPgth。因?yàn)镻gvt是t的單調(diào)遞減函數(shù)，Pwl-vt是t的單調(diào)遞增函數(shù)，綜合式（3.15）可以證明ttri+ThTLU，同理，可以得到ttri+ThTLW，又因?yàn)門LU=T1+Th，TLW=T2+Th，結(jié)合以上三式可得T1ttriT2。那么滿足原優(yōu)化問題（3.9）、（3.10）、（3.11）的最佳觸發(fā)切換時(shí)間ttri必定滿足下式：Pgvttri+Th-Pwl

13、-vttri+Th=Pgth-Pwth （3.16）在實(shí)際無線泛在網(wǎng)絡(luò)環(huán)境中，終端接收到的網(wǎng)絡(luò)信號(hào)強(qiáng)度受到陰影衰落和路徑損耗影響，上述式子可轉(zhuǎn)化為如下的最優(yōu)化條件：RSSgttri+Th-RSSwttri+Th-Pgth-Pwth （3.17）其中，是一個(gè)很小的正數(shù)。根據(jù)以上的分析，為了能夠準(zhǔn)確的預(yù)測(cè)最佳切換觸發(fā)時(shí)間，首先我們需要計(jì)算出終端切換所需要的時(shí)間Th，然后采用馬爾科夫預(yù)測(cè)模型對(duì)兩個(gè)終端接收到的相應(yīng)網(wǎng)絡(luò)的信號(hào)強(qiáng)度分別進(jìn)行預(yù)測(cè)， 如果預(yù)測(cè)值滿足式（3.18），那么t時(shí)刻就是最佳的切換觸發(fā)時(shí)間預(yù)測(cè)值，即ttri=t。RSSgt+Th-RSSwt+Th-Pgth-Pwth （3.18）其中，

14、RSSgt+Th為終端TG在t時(shí)刻預(yù)測(cè)其在t+Th時(shí)刻接收到網(wǎng)絡(luò)1信號(hào)強(qiáng)度值，RSSwt+Th為終端TW在t時(shí)刻預(yù)測(cè)其在t+Th時(shí)刻接收到網(wǎng)絡(luò)2信號(hào)強(qiáng)度值。切換時(shí)延分析無線泛在網(wǎng)絡(luò)環(huán)境中切換耗時(shí)分析網(wǎng)絡(luò)架構(gòu)及切換類型的差異導(dǎo)致不同類型的切換所需的時(shí)間各不相同，同時(shí)不同業(yè)務(wù)類型對(duì)切換時(shí)延的敏感度也不一致 因此，為了能夠及時(shí)有效的產(chǎn)生 LGD信號(hào)，保證用戶實(shí)現(xiàn)無縫切換，就必須對(duì)用戶的切換耗時(shí)進(jìn)行估計(jì)，在文獻(xiàn)27的基礎(chǔ)上，結(jié)合無線泛在網(wǎng)絡(luò)下虛擬終端系統(tǒng)框架，我們對(duì)異構(gòu)網(wǎng)絡(luò)環(huán)境下的切換耗時(shí)進(jìn)行分析（閆）。異構(gòu)網(wǎng)絡(luò)環(huán)境切換耗時(shí)在異構(gòu)網(wǎng)絡(luò)環(huán)境切換過程中，兩個(gè)終端分別使用不同的網(wǎng)絡(luò)接口進(jìn)行通信，因此當(dāng)終端T

15、W在與新網(wǎng)絡(luò)基站建立鏈路的過程中，終端TU繼續(xù)使用與原網(wǎng)絡(luò)基站之間的鏈路進(jìn)行數(shù)據(jù)傳輸，當(dāng)終端TW緩沖好了以后，再將業(yè)務(wù)傳輸給TU。異構(gòu)網(wǎng)絡(luò)終端切換的耗時(shí)可以分為原接口耗時(shí)（Thp）、新接口耗時(shí)（Thn）和終端之間建立連接耗時(shí)（Thc）。原接口耗時(shí)由以下幾部分組成：鏈路層獲取目標(biāo)網(wǎng)絡(luò)信息時(shí)間（Thp-nbr）、切換告知時(shí)間（Thp-ind）和網(wǎng)絡(luò)層切換時(shí)間（TFH），從而可得：Thp=Thp-nbr+Thp-ind+TFH （3.19）新接口耗時(shí)包括：掃描目標(biāo)網(wǎng)絡(luò)時(shí)間（Thn-scn）、切換執(zhí)行時(shí)間（T*），從而有：Thn=Thn-scn+T* （3.20）對(duì)于不同的網(wǎng)絡(luò)，切換步驟不同，切換執(zhí)行

16、時(shí)間T*也各不相同，例如WiMAX 切換執(zhí)行包括搜索和同步、關(guān)鍵信息交互和授權(quán)、注冊(cè)；WLAN 切換執(zhí)行包括鑒權(quán)和連接時(shí)間；GSM 切換執(zhí)行則包括時(shí)間頻率同步、鑒權(quán)、位置注冊(cè)。各網(wǎng)絡(luò)切換執(zhí)行時(shí)間如下：T*=Trng+Tcap+Tkey+Treg ，for WiMAX Tauth+Tassc ，for WLANTsyn+Tauth+Treg ，for GSM （3.21）其中，Trng、Tcap、Tkey和Treg分別為WiMAX 網(wǎng)絡(luò)的同步和搜索、基本能力協(xié)商、關(guān)鍵信息交互和鑒權(quán)、注冊(cè)時(shí)間；Tauth和Tassc分別為WLAN網(wǎng)絡(luò)的鑒權(quán)和連接時(shí)間；Tsyn、Tauth和Treg分別為GSM網(wǎng)絡(luò)

17、的時(shí)間頻率同步、鑒權(quán)、位置注冊(cè)時(shí)間。藍(lán)牙終端發(fā)現(xiàn)延時(shí)主要包括以下方面：查詢掃描時(shí)由于主從設(shè)備不在同一頻率產(chǎn)生的掃描延時(shí)、從設(shè)備掃描到查詢信號(hào)產(chǎn)生的隨機(jī)延時(shí)以及從設(shè)備掃描主設(shè)備發(fā)出的呼叫信號(hào)產(chǎn)生的延時(shí)。由于掃描延時(shí)和呼叫延時(shí)產(chǎn)生原因均是由于主從設(shè)備不在同一頻率上，因此我們假定該兩種延時(shí)時(shí)間相同，稱為頻率同步延時(shí)(FSD: frequency synchronization delay)，從設(shè)備隨機(jī)產(chǎn)生的延時(shí)稱為隨機(jī)向后延時(shí)（RBD: Random Back-off Delay）。對(duì)于尋呼階段，由于已經(jīng)獲得了需要連接的設(shè)備的時(shí)鐘和ID信息，所以尋呼設(shè)備直接以被尋呼設(shè)備的頻率發(fā)送尋呼包，尋呼掃描設(shè)備

18、收到后立即響應(yīng)，因此尋呼階段延遲相對(duì)固定而且非常小34，從而我們以查詢階段的延遲來估計(jì)整個(gè)連接過程的延遲。（湖大）故終端之間建立連接耗時(shí)包括：頻率同步延時(shí)（Thc-fsd）和隨機(jī)向后延時(shí)（Thc-rbd），從而有：Thc=2*Thc-fsd+Thc-rbd （3.22）由于虛擬終端系統(tǒng)中有多個(gè)終端，在執(zhí)行切換過程中，多個(gè)終端網(wǎng)絡(luò)接口可以同時(shí)工作，所以總的切換時(shí)延是：Th=Thp-nbr+Thn-scn+maxThp-ind+TFH，T*+Thc （3.23）如下圖所示，用戶從GSM網(wǎng)絡(luò)向WiMAX網(wǎng)絡(luò)切換過程中，各部分耗時(shí)估計(jì)值分別為：Thp-nbr=2(+HNN+) （3.24）Thp-in

19、d=2(+HMR+) （3.25）Thn-scn=2() （3.26）T*=Trng+Tcap+Tkey+Treg （3.27）其中，表示無線鏈路中可能存在傳輸碰撞等導(dǎo)致的時(shí)間開銷，表示單位信息在相鄰物理實(shí)體之間的傳輸延遲，表示相鄰功能實(shí)體間的傳輸時(shí)延。HNN表示管理兩個(gè)網(wǎng)絡(luò)的網(wǎng)絡(luò)重構(gòu)管理器（NRM）之間的跳數(shù)，HMR表示GSM網(wǎng)絡(luò)的移動(dòng)交換中心（MSC）與WiMAX網(wǎng)絡(luò)路由之間的跳數(shù)，其中網(wǎng)絡(luò)層切換時(shí)延TFH要根據(jù)所采用的具體切換協(xié)議而定，藍(lán)牙設(shè)備發(fā)現(xiàn)時(shí)間延遲Thc也要根據(jù)所采用的具體連接延時(shí)算法而定。Markov預(yù)測(cè)模型獲得了切換耗時(shí)估計(jì)結(jié)果以后，我們采用混合Markov預(yù)測(cè)模型分別對(duì)終端

20、TG接收到當(dāng)前網(wǎng)絡(luò)信號(hào)強(qiáng)度和TW接收到切換目標(biāo)網(wǎng)絡(luò)的信號(hào)強(qiáng)度進(jìn)行預(yù)測(cè)，終端以Tsamp為間隔對(duì)其接收到的網(wǎng)絡(luò)的信號(hào)強(qiáng)度進(jìn)行采樣，將得到采樣值X=xn,xn-1,x(n-p+1)作為輸入的歷史信息。由于終端在短時(shí)間間隔內(nèi)采樣得到的信號(hào)強(qiáng)度會(huì)有比較大的波動(dòng)，為預(yù)測(cè)帶來一定的難度，因此采用加權(quán)平滑（WMPM）12方法對(duì)采樣得到的信號(hào)強(qiáng)度進(jìn)行處理，具體如下：an=an-1+1-x(n)其中，(01)為平滑系數(shù)，an為加權(quán)平滑后的信號(hào)強(qiáng)度值。在移動(dòng)預(yù)測(cè)問題上，多階Markov模型和以多階Markov模型為基礎(chǔ)的回退模型已經(jīng)被驗(yàn)證是比較符合移動(dòng)用戶的移動(dòng)規(guī)律、預(yù)測(cè)比較準(zhǔn)確的一種方法。下面簡(jiǎn)要介紹混合馬爾科

21、夫移動(dòng)預(yù)測(cè)模型。馬爾可夫過程1馬爾可夫過程的定義馬爾可夫過程31是具有以下特性的隨機(jī)過程：當(dāng)過程在時(shí)刻 tk所處的狀態(tài)為已知的條件下，過程在時(shí)刻 t（t>tk）的狀態(tài)只與過程在tk時(shí)刻的狀態(tài)有關(guān)，而與過程在時(shí)刻tk以前所處的狀態(tài)無關(guān)?；蛘哒f，馬爾可夫過程的“將來”只與“現(xiàn)在”有關(guān)，而與“過去”無關(guān)。這種特性稱為“無后效性”或稱為“馬爾可夫性”。定義：設(shè)Xt,t0,+)是一個(gè)隨機(jī)過程，如果對(duì)于任意n，0<t1<t2<<tnT，過程Xt，t0,+)在t1，t2，tn-1的取值分別為x1，x2，xn-1并且一下概率等式成立：PXtnxnXt1=x1,Xt2=x2,Xtn

22、-1=xn-1=PXtnxn|Xtn-1=xn-1則稱隨機(jī)過程Xt,t0,+)為馬爾科夫過程。2.連續(xù)時(shí)間馬氏鏈如果馬爾可夫過程Xt,tT的狀態(tài)空間S是離散的，則這個(gè)馬爾可夫過程稱為馬爾可夫鏈。根據(jù)時(shí)間的連續(xù)與否，馬爾可夫鏈可進(jìn)一步分類為“連續(xù)時(shí)間馬爾科夫鏈”和“離散時(shí)間馬爾科夫鏈”。定義：設(shè)Xt，t0,+)是時(shí)間連續(xù)狀態(tài)分散的隨機(jī)過程，狀態(tài)空間S=0,1,2,，如果對(duì)任意正整數(shù)n和t1<t2<<tn<tn+10,+)，有r1,r2,rn,jS，使得： PXtn+1=jXt1=r1,Xt2=r2,Xtn=rn=PXtn+1=j|Xtn=rn則稱Xt，t0,+)為狀態(tài)空間

23、S上的連續(xù)時(shí)間馬爾科夫鏈。條件概率PXt+s=jXs=i,t>0,s0稱為連續(xù)時(shí)間馬爾科夫鏈在s時(shí)刻從狀態(tài)i進(jìn)入到狀態(tài)j的轉(zhuǎn)移概率函數(shù)，記為Pij(s,s+t)。二階的 Markov 預(yù)測(cè)器二階Markov預(yù)測(cè)器假定移動(dòng)用戶的位置變量X是一個(gè)隨機(jī)變量，且隨機(jī)變量序列Xi（1in1）構(gòu)成一個(gè)時(shí)齊Markov過程。對(duì)于二階Markov預(yù)測(cè)器，即要求隨機(jī)變量序列Xi滿足以下要求：PXn+1=aX1,n=L=PXn+1XnXn-1=anan-1PXn+1=aXnXn-1=anan-1=PXk+1=aXkXk-1=anan-1式中ak代表抽樣的一個(gè)網(wǎng)絡(luò)信號(hào)強(qiáng)度的采樣值，L=a1a2an代表了網(wǎng)絡(luò)信

24、號(hào)采樣序列。二階Markov預(yù)測(cè)器的目的是根據(jù)終端當(dāng)前的RSS采樣值以及上一個(gè)RSS采樣值去預(yù)測(cè)下一個(gè)可能的RSS值，從而根據(jù)各個(gè)終端的RSS值判斷是否需要切換以及選擇最佳切換觸發(fā)時(shí)刻，它的核心是建立轉(zhuǎn)移概率矩陣M 。該矩陣的行元素表示長(zhǎng)度為2的RSS上下文，列元素表示下一個(gè)RSS值，矩陣元素表示行元素代表的當(dāng)前狀態(tài)下，終端接收到信號(hào)列元素代表的RSS的概率。二階Markov預(yù)測(cè)器的應(yīng)用就是根據(jù)用戶當(dāng)前狀態(tài)找到M中的相應(yīng)行，該行中最大的元素值對(duì)應(yīng)的列所代表的RSS即為預(yù)測(cè)結(jié)果，用公式表示如下Xp=MaxXn+1(P(Xn+1|C)其中Xp表示預(yù)測(cè)結(jié)果，C表示當(dāng)前RSS上下文。但是，多階 Mar

25、kov 模型，尤其是高階 Markov 模型，在算法的復(fù)雜度方面存在較大問題。它的狀態(tài)空間隨著采樣值的數(shù)目增加而呈爆炸式增長(zhǎng)，給模型的實(shí)際應(yīng)用造成比較大的困難。針對(duì)上述狀態(tài)空間膨脹問題，雖然研究人員提出了一些新的解決方案，但是效果并不明顯。針對(duì)這個(gè)問題，通過對(duì)數(shù)據(jù)集M中大量用戶的跟蹤文件的分析發(fā)現(xiàn)，在很多情況下，用RSSpre的信息來預(yù)測(cè)RSSnext也能達(dá)到一個(gè)比較好的效果。根據(jù)本章實(shí)際需要，我們提出一個(gè)二步 Markov 模型預(yù)測(cè)器。二步 Markov 模型在假定用戶移動(dòng)模式滿足式（2.1）、（2.2）的前提下，有下面兩式成立：PXn+1=aX(1,n)=L=PXn+1=aXn-1=an-

26、1PXn+1=aXn-1=b=PXk+1=aXk-1=bX(1,n)以及L的定義同上面相同。二步Markov預(yù)測(cè)器的核心任務(wù)是建立一個(gè)與一階Markov預(yù)測(cè)器的轉(zhuǎn)移概率矩陣同規(guī)模的轉(zhuǎn)移概率矩陣。矩陣的行元素代表RSSpre，矩陣的列元素代表RSSnext。通過該矩陣就可以根據(jù)移動(dòng)用戶上一個(gè)的RSS采樣值來預(yù)測(cè)其下一步即將接收的RSS值。一階和二步Markov預(yù)測(cè)器，相對(duì)于二階Markov預(yù)測(cè)器而言，各自缺失了一些信息，其預(yù)測(cè)性能比二階Markov預(yù)測(cè)器差是必然的。所以聯(lián)合一階和二步Markov預(yù)測(cè)器，用比二階Markov預(yù)測(cè)器小得多的代價(jià)獲得與二階Markov預(yù)測(cè)器相近的性能是不錯(cuò)的選擇?；旌?/p>

27、 Markov 預(yù)測(cè)器模型一階和二步馬爾科夫預(yù)測(cè)器的轉(zhuǎn)移概率矩陣根據(jù)大數(shù)定律計(jì)算得到，但是在預(yù)測(cè)時(shí)，終端接收到的下一個(gè)可能RSS預(yù)測(cè)值不再僅僅取決于一階轉(zhuǎn)移概率矩陣或二步轉(zhuǎn)移概率矩陣，而是綜合兩個(gè)轉(zhuǎn)移概率矩陣的信息選擇最有可能RSS預(yù)測(cè)值。具體的模型如下： pan+1anan-1=1pan+1an+2pan+1an-11+2=1 （1）式（1）中的1和2分別為一階模型和二步模型的混合系數(shù)?；旌夏Ｐ偷年P(guān)鍵就是根據(jù)極大似然定理求出1和2。參數(shù)求解過程：模型的似然函數(shù)如下：L1,2=j=2n-1paj+1ajaj-1 （2）其對(duì)應(yīng)的對(duì)數(shù)似然函數(shù)為：L1,2=j=2n-1logpaj+1ajaj-1

28、（3）式(2)和式（3）中的 n 均表示選取用來求極大似然的連續(xù)一段終端的歷史 RSS采樣值信息D的長(zhǎng)度。把式（1）代入式（3）得到：L1,2=j=2n-1logpaj+1ajaj-1=j=2j=n-1log1paj+1aj+2paj+1aj-1 (4)要根據(jù)式（4）直接來求1和2是困難的。這里我們?cè)谀Ｐ椭幸肓穗[變量，即把式（1）看作一個(gè)含隱變量Zj=Z1j,Z2j的模型，其中Zij0,1，且Z1j+Z2j=1。Z1j=1表示在第 j 步混合時(shí)取一階模型作為預(yù)測(cè)器； Z2j=1表示在第 j 步混合時(shí)取二步模型作為預(yù)測(cè)器。因此，式（4）可改寫為：Lc1,2=i=12j=2n-1zijlogi+C （5）式（5）中的 C 為與1和2無關(guān)的常量。通過引入隱變量 Zj，可以在式（4）采用 EM 算法來求解1和2。為描述方便，取向量=1,2。具體的求解算法如下：1、 給向量=1,2賦任意初值，即給向量0賦值；2、 Zijk=EkZijD=PkZij=1D，又PkZij=1D=PkDZij=1×PkZij=1PkD記p1j=paj+1aj 、p2j=paj+1aj-1，則有PkZij=1D=ikpij1kp1j+2kp2j Zijk=ikpij1kp1j+2kp2j3、 根據(jù)上述1k、2k以及