HMM改進Ad hoc網(wǎng)絡(luò)延時的模型及抗毀性研究*

吳勇翀，周艷華

（江西科技學(xué)院，江西 南昌 330098）

0 引言

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

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

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

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

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

式中：O=O1，O2，…，OT，Q=q1，q2，…，qT；P(Q|λ)=πq1aq1q2 aq2q3…aqT-1qT；P(O|Q，λ)=bq1(O1)bq2(O2)…bqT(OT)。

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

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

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

(1)初始化

(2)傳遞公式

(3)最后數(shù)據(jù)結(jié)果

(4)返回路徑

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

假設(shè)已有的模型參數(shù)為 λ=(A，B，π)，那么經(jīng)過改進后的模型參數(shù)為，這里有：

按照上述的運算方式，即可推出：

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

1.2 移動節(jié)點觀察模型的設(shè)計

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

圖1 模型的狀態(tài)劃分與觀察序列

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

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

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

圖2 觀察符號空間與量化

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

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

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

2.1 信道抗毀性

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

圖3 無湖劃分方式及其信道安排方案

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

圖4 有湖劃分方式及其信道安排方案

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

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

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

表1 模型的抗毀性算法應(yīng)用

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

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

3 結(jié)論

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

[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-inspired 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é)報，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.