0 引言

    上世紀(jì)70年代，研究人員開始了對無線移動(dòng)自組織（Ad hoc）網(wǎng)絡(luò)技術(shù)的開發(fā)，當(dāng)時(shí)是因美國出于軍事需要而開始研究無線網(wǎng)，讓其能適應(yīng)戰(zhàn)場的需要進(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í)。上述問題急需對其移動(dòng)的方位完成評估及確定所需鏈接的路由器，這樣即可讓移動(dòng)節(jié)點(diǎn)時(shí)刻做好發(fā)生切換的預(yù)備工作，進(jìn)而縮短或避免中斷，并做好延時(shí)，爭取時(shí)間^[4]。處理這一問題的廣泛處理方式是采用人工神經(jīng)網(wǎng)絡(luò)，然而人工網(wǎng)絡(luò)模型固然可構(gòu)造出相對更精確的分類界面，但仍需非常多的訓(xùn)練數(shù)據(jù)才可做參數(shù)估計(jì)，并且運(yùn)算相對復(fù)雜，收斂較慢^[5]。本文針對上述問題，進(jìn)行了一種對移動(dòng)節(jié)點(diǎn)的路徑新預(yù)測模型設(shè)計(jì)，采用了隱馬爾科夫模型（HMM）處理，這一研究對于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è)對應(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)算難度相對高，所以就會(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所覆蓋的無線信號區(qū)域內(nèi)移動(dòng)，可定期對信號強(qiáng)度等有關(guān)移動(dòng)路徑的信息進(jìn)行測量。假設(shè)MN處在離散時(shí)間nΔt(n=1，2，…)時(shí)，能夠測得與AR之間的信號強(qiáng)度，還能夠得到按照信號強(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ì)影響觀察位置的確定；其二，由于存在噪音、測量方式的錯(cuò)誤等原因，會(huì)導(dǎo)致觀察值存在誤差；其三，即使MN會(huì)按照某種路徑移動(dòng)，可移動(dòng)在某種程度上還是隨機(jī)的。

    假設(shè)M為此時(shí)AR的鄰居子網(wǎng)數(shù)，對于離散參數(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)移概率矩陣、符號輸出概率矩陣、初始狀態(tài)分布。在進(jìn)入AR時(shí)，對于之前屬于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ù)測模型的預(yù)測過程，通過Baum Welch算法求解訓(xùn)練過程，若觀察序列就是因已經(jīng)指定的模型而形成的，那么這種算法的效果是能夠達(dá)到的，這在多個(gè)領(lǐng)域(如語音識別)已被證實(shí)，所以，模型訓(xùn)練所采用的是Baum Welch算法。MN移動(dòng)預(yù)測模型的預(yù)測判別方法主要是找出一個(gè)模型λ_x，使得P(O|λ_x)最大。

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

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

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

    在Ad網(wǎng)絡(luò)系統(tǒng)中，抗毀性是一個(gè)最為關(guān)鍵的特點(diǎn)，抗毀性強(qiáng)弱所體現(xiàn)的是對某些節(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)行對應(yīng)的信道模型方案的結(jié)果表述，如圖3、圖4所示。

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

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

參考文獻(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.