0 引言

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

1 HMM實現Ad網絡問題處理

1.1 3個基本問題的求解實現

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

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

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

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

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

    (1)初始化

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

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

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

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

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

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

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

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

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

2 設計模型的抗毀性分析

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

2.1 信道抗毀性

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

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

2.2 網絡的連通度

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

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

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

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

3 結論

    作為一種隨機概率模型,，HMM表示的是與時間序列有關聯的有效模型,，所涉及的知識包括概率與統(tǒng)計學，目的是對參數不同的短時平穩(wěn)信號段進行識別,，并實現信號之間的轉化,，該模型應用中的一切實際問題均能以HMM模型中的3個問題來表示。在這里，采取仿真對HMM預測移動進行了可行性研究,，在訓練樣本以及初始模型參數已知的前提下,，采取新的數據來檢驗模型，從而確定模型預測的準確度,。由仿真結果可知,，該模型是可行的，且抗毀性具有一定的優(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-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)學報,，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.