0 引言

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

1 HMM實現Ad網絡問題處理

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

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

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

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

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

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

    (1)初始化

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

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

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

1.2 移動節點觀察模型的設計

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

    假設M為此時AR的鄰居子網數，對于離散參數的HMM初始值只有一個，即統一分布，所以，模型的初始值的設置方法可以表述成MN按照等概率的方式從一狀態切換成另一種鄰近的狀態，以獲得λ_ij=(A_ij，B_ij，π)，1≤i，j≤M，A、B、π分別代表狀態轉移概率矩陣、符號輸出概率矩陣、初始狀態分布。在進入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作為中心，在其徑向上的各狀態范圍內進行等間隔區域的劃分，同時，將中心信號的強度值作為觀察符號空間中的符

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

2 設計模型的抗毀性分析

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

2.1 信道抗毀性

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

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

2.2 網絡的連通度

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

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

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

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

3 結論

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

參考文獻

[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].智能系統學報，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.