0 引言

    上世紀(jì)70年代,，研究人員開始了對(duì)無線移動(dòng)自組織（Ad hoc）網(wǎng)絡(luò)技術(shù)的開發(fā),，當(dāng)時(shí)是因美國出于軍事需要而開始研究無線網(wǎng)，讓其能適應(yīng)戰(zhàn)場(chǎng)的需要進(jìn)行數(shù)據(jù)通信,。Ad hoc網(wǎng)絡(luò)與以往的無線網(wǎng)格有著明顯的不同,，它的網(wǎng)絡(luò)結(jié)構(gòu)是隨意的、非固定的,。與此同時(shí)，它也不需專門固定的基站或路由器當(dāng)做管理中心,。到了上世紀(jì)末,，研究無線移動(dòng)自組織網(wǎng)絡(luò)的工作就已經(jīng)在世界各國開始陸續(xù)展開，并且從無線通信領(lǐng)域里的一個(gè)分支,，慢慢擴(kuò)大到一個(gè)單獨(dú)的領(lǐng)域,。當(dāng)前關(guān)于Ad hoc網(wǎng)絡(luò)的學(xué)術(shù)會(huì)議越來越多。由于移動(dòng)自組網(wǎng)絡(luò)的任意一節(jié)點(diǎn)都能隨機(jī)移動(dòng),，因此組網(wǎng)非常靈活,，那么相應(yīng)的網(wǎng)絡(luò)開發(fā)的難度就大大增加了^[1]。當(dāng)前研究^[2-3]中遇到了Ad hoc網(wǎng)絡(luò)發(fā)展瓶頸：移動(dòng)節(jié)點(diǎn)在子網(wǎng)中進(jìn)行切換過程中,，基本上無法避免通信中斷,，而且還會(huì)帶來很大的延時(shí)。上述問題急需對(duì)其移動(dòng)的方位完成評(píng)估及確定所需鏈接的路由器,，這樣即可讓移動(dòng)節(jié)點(diǎn)時(shí)刻做好發(fā)生切換的預(yù)備工作,，進(jìn)而縮短或避免中斷，并做好延時(shí),，爭取時(shí)間^[4],。處理這一問題的廣泛處理方式是采用人工神經(jīng)網(wǎng)絡(luò)，然而人工網(wǎng)絡(luò)模型固然可構(gòu)造出相對(duì)更精確的分類界面，但仍需非常多的訓(xùn)練數(shù)據(jù)才可做參數(shù)估計(jì),，并且運(yùn)算相對(duì)復(fù)雜,，收斂較慢^[5]。本文針對(duì)上述問題,，進(jìn)行了一種對(duì)移動(dòng)節(jié)點(diǎn)的路徑新預(yù)測(cè)模型設(shè)計(jì),，采用了隱馬爾科夫模型（HMM）處理，這一研究對(duì)于Ad hoc網(wǎng)絡(luò)實(shí)際應(yīng)用的拓展具有一定的價(jià)值,。

1 HMM實(shí)現(xiàn)Ad網(wǎng)絡(luò)問題處理

1.1 3個(gè)基本問題的求解實(shí)現(xiàn)

    在確定HMM模型情況下,，需要實(shí)現(xiàn)以下3個(gè)關(guān)鍵問題才可以較好地運(yùn)用在實(shí)際項(xiàng)目中：(1)如果指定的一組觀察序列O=O₁，O₂,，…,，O_T、模型λ=(A,，B,，π)，在此條件下,，怎樣科學(xué)合理地運(yùn)算出概率P(O|λ),；(2)條件與(1)相同，怎樣選取一個(gè)對(duì)應(yīng)的狀態(tài)序列S=q₁,，q₂,，…，q_T,，S可以非常明晰地闡述O,；(3)怎樣調(diào)整模型參數(shù)λ=(A，B,，π),，能夠滿足P(O|λ)最大。通常情況下,，這3個(gè)問題都是在一個(gè)實(shí)際項(xiàng)目的應(yīng)用中被總結(jié)出的,。

    解決問題(1)的方法：若直接做運(yùn)算，即：

    若按照該方法直接運(yùn)算,，就會(huì)用到全部可能的狀態(tài)序列,，復(fù)雜度以及指數(shù)巨大，運(yùn)算難度相對(duì)高,，所以就會(huì)采用前向的方法進(jìn)行運(yùn)算,。前向算法做運(yùn)算，首先要定義前向變量α_t(i)：

    在已知的模型λ前提下,，從最初時(shí)刻到時(shí)刻t局部的觀察序列O₁O₂…O_t,，和時(shí)刻t狀態(tài)S_i形成的概率為α_t(i),。解決問題(2)的方法：使用Viterbi Algorithm方法是一個(gè)比較好的選擇。這里,，將Viterbi變量定義為：

    δ_t(i)是已知的觀察序列,，從最初時(shí)刻到t時(shí)刻，同時(shí)最大概率狀態(tài)序列的狀態(tài)是S_i,。其中,，φ_t(i)是概率最大途徑中此刻狀態(tài)的之前狀態(tài)。求解問題(2)的步驟是：

    (1)初始化

    解決問題(3)的方法：實(shí)質(zhì)上即是求解HMM模型參數(shù)做優(yōu)化處理的問題,。如今已有的大量算法都能夠解決該問題,，本文通過使用Baum Welch算法，同時(shí)將變量定義成：

    按照上述的運(yùn)算方式,，即可推出：

    把新模型參數(shù)當(dāng)做是現(xiàn)存模型參數(shù),，重復(fù)前面的步驟，一直到能獲得最優(yōu)的HMM模型參數(shù),，這樣問題就迎刃而解,。

1.2 移動(dòng)節(jié)點(diǎn)觀察模型的設(shè)計(jì)

    若有一移動(dòng)節(jié)點(diǎn)MN，它在與自己已建立無線連接的接入路由器AR所覆蓋的無線信號(hào)區(qū)域內(nèi)移動(dòng),，可定期對(duì)信號(hào)強(qiáng)度等有關(guān)移動(dòng)路徑的信息進(jìn)行測(cè)量,。假設(shè)MN處在離散時(shí)間nΔt(n=1，2,，…)時(shí),，能夠測(cè)得與AR之間的信號(hào)強(qiáng)度，還能夠得到按照信號(hào)強(qiáng)度為觀察值的觀察序列O₁,，O₂,，…，O_T,。若Δt很小，則可看成該時(shí)間段里,，MN移動(dòng)的速度是一個(gè)不變的值,。可將該定值用v_n(n=1,，2…)來表示,。為使移動(dòng)預(yù)估目標(biāo)MN進(jìn)入子網(wǎng)，所以會(huì)將AR涉及到的范圍區(qū)域分塊成一些子域,，見圖1,。此外，還要使得每個(gè)子區(qū)域所包涵的范圍都滿足r₁=r₂=…=r_N,。還將該子區(qū)域當(dāng)成MN移動(dòng)的過程中的每一種狀態(tài)Qi,，i=1,，2，…,，N,。若MN按照其中一路徑進(jìn)行移動(dòng)，那么可以得到其觀察序列是O=O₁,，O₂,，…，O_T,，如圖1所示,。因?yàn)橐恍┮蛩貢?huì)使得觀察序列是隨機(jī)的。其一,，是在觀察的最初時(shí)間就不具備確定性,，MN移動(dòng)速度的隨機(jī)性也會(huì)影響觀察位置的確定；其二,，由于存在噪音,、測(cè)量方式的錯(cuò)誤等原因，會(huì)導(dǎo)致觀察值存在誤差,；其三,，即使MN會(huì)按照某種路徑移動(dòng)，可移動(dòng)在某種程度上還是隨機(jī)的,。

    假設(shè)M為此時(shí)AR的鄰居子網(wǎng)數(shù),，對(duì)于離散參數(shù)的HMM初始值只有一個(gè)，即統(tǒng)一分布,，所以,，模型的初始值的設(shè)置方法可以表述成MN按照等概率的方式從一狀態(tài)切換成另一種鄰近的狀態(tài)，以獲得λ_ij=(A_ij,，B_ij,，π)，1≤i,，j≤M,，A、B,、π分別代表狀態(tài)轉(zhuǎn)移概率矩陣,、符號(hào)輸出概率矩陣、初始狀態(tài)分布,。在進(jìn)入AR時(shí),，對(duì)于之前屬于AR的哪個(gè)鄰居子網(wǎng)，MN是可以知道的,，假設(shè)是子網(wǎng)Θ,，通過AR,，MN可以得到HMM模型集{λ_Θj|1≤Θ≤M，j=1,，2,，…，M},。如果MN得到了觀察序列,，則按照以下公式進(jìn)行計(jì)算：

    此時(shí)，j為AR的鄰居子網(wǎng),，也就是MN接下來要進(jìn)入的子網(wǎng),。訓(xùn)練、觀察,、判別是以上預(yù)測(cè)模型的預(yù)測(cè)過程,，通過Baum Welch算法求解訓(xùn)練過程，若觀察序列就是因已經(jīng)指定的模型而形成的,，那么這種算法的效果是能夠達(dá)到的,，這在多個(gè)領(lǐng)域(如語音識(shí)別)已被證實(shí)，所以,，模型訓(xùn)練所采用的是Baum Welch算法,。MN移動(dòng)預(yù)測(cè)模型的預(yù)測(cè)判別方法主要是找出一個(gè)模型λ_x，使得P(O|λ_x)最大,。

    離散HMM訓(xùn)練樣本及其可取值空間并不是無限的,，但上面提到在一定范圍內(nèi)，MN移動(dòng)預(yù)測(cè)HMM模型中的觀察值任意取值,，所以一定要先將觀察序列在觀察符號(hào)空間進(jìn)行量化,，再對(duì)觀察值與觀察符號(hào)輸出概率之間的關(guān)系進(jìn)行確定。圖2是觀察符號(hào)空間與量化的過程圖,。觀察符號(hào)空間的確定所采取的是徑向劃分法,，也就是將AR作為中心，在其徑向上的各狀態(tài)范圍內(nèi)進(jìn)行等間隔區(qū)域的劃分,，同時(shí),，將中心信號(hào)的強(qiáng)度值作為觀察符號(hào)空間中的符

    雖然在量化過程中會(huì)有一定的誤差，但經(jīng)過量化的觀察值對(duì)應(yīng)的狀態(tài)和符號(hào)輸出概率是不變的,，所以，量化誤差對(duì)于與MN將連接的AR的預(yù)測(cè)并無太大影響,。

2 設(shè)計(jì)模型的抗毀性分析

    在Ad網(wǎng)絡(luò)系統(tǒng)中,，抗毀性是一個(gè)最為關(guān)鍵的特點(diǎn)，抗毀性強(qiáng)弱所體現(xiàn)的是對(duì)某些節(jié)點(diǎn)之間的通信進(jìn)行中斷所需破壞的鏈接數(shù),。主要從兩個(gè)角度來分析抗毀性,，即黏聚度與連通度,。這里僅分析去掉部分節(jié)點(diǎn)后的網(wǎng)絡(luò)連通度。通常情況下,，網(wǎng)絡(luò)的連通度越好,，其抗毀性就越強(qiáng)，反之則亦然,。

2.1 信道抗毀性

    通過計(jì)算機(jī)的幫助可獲得區(qū)域劃分方式,，采用有湖與無湖兩種劃分方式進(jìn)行對(duì)應(yīng)的信道模型方案的結(jié)果表述，如圖3,、圖4所示,。

    圖3、圖4可得,，此時(shí)最小半徑相加所得總和分別為4034.4,、4213.5。研究表明,，只需要最小半徑相加小于10 000,，則Ad網(wǎng)絡(luò)的連通性是良好的，即抗毀性較強(qiáng),。圖中結(jié)果表明了模型的抗毀性優(yōu)勢(shì),。

2.2 網(wǎng)絡(luò)的連通度

    定量原理：假設(shè)有一無向圖G，那么G為k的連通圖的充分必要條件是：G的定點(diǎn)數(shù)不小于k+1,。在任一通信區(qū)域中,，假設(shè)這個(gè)區(qū)域有M個(gè)節(jié)點(diǎn)，k是其連通度,，那么區(qū)域連通的充要條件是：M不小k+1,；926是正方形通信區(qū)域附表中所定的節(jié)點(diǎn)數(shù)，那么其連通的充要條件是：

    只要節(jié)點(diǎn)的連通度不超過925,，通信網(wǎng)絡(luò)就是連通的,。根據(jù)數(shù)學(xué)概率理論可將網(wǎng)絡(luò)節(jié)點(diǎn)的連通概率計(jì)算出來。隨機(jī)將節(jié)點(diǎn)集合中的2%,、5%,、10%、15%等數(shù)量的節(jié)點(diǎn)去掉,，由設(shè)計(jì)模型可得到當(dāng)前網(wǎng)絡(luò)的連通度,，那么網(wǎng)絡(luò)節(jié)點(diǎn)的連通概率也就可以計(jì)算出來了。表1所描述的是其抗毀性算法應(yīng)用的節(jié)點(diǎn)數(shù),。

    由表1可見,，節(jié)點(diǎn)的數(shù)量與抗毀性的強(qiáng)度是成正比的，相交面積大小與抗毀性的強(qiáng)度成反比,。同時(shí)由原理可知,，設(shè)計(jì)模型的Ad Hoc網(wǎng)絡(luò)具有較強(qiáng)的抗毀性,。

    由以上分析可知，節(jié)點(diǎn)最多的是公共區(qū)域,，其網(wǎng)絡(luò)連通性比較強(qiáng),，設(shè)計(jì)模型的Ad Hoc網(wǎng)絡(luò)具有較強(qiáng)的抗毀性，同樣解決了Ad Hoc網(wǎng)絡(luò)的延時(shí)問題,。

3 結(jié)論

    作為一種隨機(jī)概率模型,，HMM表示的是與時(shí)間序列有關(guān)聯(lián)的有效模型，所涉及的知識(shí)包括概率與統(tǒng)計(jì)學(xué),，目的是對(duì)參數(shù)不同的短時(shí)平穩(wěn)信號(hào)段進(jìn)行識(shí)別,，并實(shí)現(xiàn)信號(hào)之間的轉(zhuǎn)化，該模型應(yīng)用中的一切實(shí)際問題均能以HMM模型中的3個(gè)問題來表示,。在這里,，采取仿真對(duì)HMM預(yù)測(cè)移動(dòng)進(jìn)行了可行性研究，在訓(xùn)練樣本以及初始模型參數(shù)已知的前提下,，采取新的數(shù)據(jù)來檢驗(yàn)?zāi)Ｐ?，從而確定模型預(yù)測(cè)的準(zhǔn)確度。由仿真結(jié)果可知,，該模型是可行的,，且抗毀性具有一定的優(yōu)勢(shì)。

參考文獻(xiàn)

[1] Wang Hao,，Liu Nan,，Li Zhihang，et al.A unified algorithm for mobility load balancing in 3GPP LTE multi-cell networks[J].Science China(Information Sciences),，2013,，56(2)：118-128.

[2] Zhang Zhongshan，Huang Fuwei,，Long Keping,，et al.On the　designing principles and optimization approaches of bio-in-spired self-organized network: a survey[J].Science China(Information Sciences)，2013,，56(7)：5-32.

[3] Dan Yangqin,，Hong Weili，Lin Ma,，et al.An ant colony algorithm based congestion elusion routing strategy for mobile　ad hoc networks[J].Journal of Harbin Institute of Technology,，2013，20(3)：99-103.

[4] WAKAMIYA N,，LEIBNITZ K,，MURATA M.Biologically　inspired self-organizing networks[J].智能系統(tǒng)學(xué)報(bào)，2009，4(4)：369-375.

[5] 李曦.Always-optimally-coordinated candidate selection algorithm for peer-to-peer files sharing system in mobile self-organized networks[J].High Technology Letters,，2009，15(3)：281-287.