基于粒子濾波步行長度預測的移動ad hoc網絡路由算法*

張 玲,聶少華

(1.北京信息職業技術學院電子工程系，北京　100015；2.臨沂大學初等教育學院，山東臨沂　276000)

基于粒子濾波步行長度預測的移動ad hoc網絡路由算法*

張 玲**1,聶少華2

(1.北京信息職業技術學院電子工程系，北京100015；2.臨沂大學初等教育學院，山東臨沂276000)

針對移動ad hoc網絡拓撲結構變化大、路由復雜度高、數據傳輸性能低等問題,提出了一種新的移動通信系統自適應路由算法。為了使得網絡拓撲結構更接近移動網絡間歇性連接的特點,該算法在網絡結構上采用了一種改進的Levy Wa1k移動模型。采用一種粒子濾波步行長度預測的方法,通過蒙特卡羅抽樣得到遞歸貝葉斯濾波器,并在粒子濾波后進行步行長度預測,確定消息的副本數量,從而減少由于節點轉發過多消息副本帶來的能量消耗量,提高消息的傳遞效率。實驗仿真結果表明:與基于改進蟻群優化和利潤優化模型的路由算法相比,該算法的消息傳遞成功率分別提高了0.08和0.04,節點平均能量效率提高了17.9%和13.4%,在提升數據傳輸成功率和節能上具有較好效果。

移動ad hoc網絡;粒子濾波;步行長度預測;Levy Wa1k移動模型;自適應路由算法

引用格式:張玲，聶少華.基于粒子濾波步行長度預測的移動ad hoc網絡路由算法[J].電訊技術，2016，56(3)：331-336.[ZHANG Ling，NIE Shaohua.A mobi1e ad hoc network routing a1gorithm based on wa1king 1ength Prediction after Partic1e fi1tering[J].Te1ecommunication Engineering，2016，56(3)：331-336.]

1　引 言

移動自組織網絡(Mobi1e ad hoc Network，MANET)作為一種無預置基礎設施的動態可重構無線網絡，具有廣泛的應用價值，可以應用于救災、移動監測、現代戰場、移動醫療等多個領域。在MANET中網絡節點具有隨機的移動性，節點可以充當路由器為其他節點轉發數據包，也可以作為主機將其他節點的數據進行匯聚[1-2]。然而，與靜態無線傳感器網絡(Static Wire1ess Sensor Network，SWSN)相比，研究MANET更加困難。這是由于MANET具有高速的移動性，會導致網絡拓撲結構的變化，加重路由復雜程度，對網絡的通信性能造成一定的影響。而且，由于網絡中各節點的移動速度和移動模式的隨機性，會使信道帶寬以及節點能量受限，對網絡壽命也會造成一定影響[3]。目前，針對MANET的路由算法研究取得了一定進展，然而由于移動環境下網絡拓撲結構的不斷變化，節點鏈路的持續通信問題仍是一個重要的挑戰[4-5]。

為了提高移動通信網絡的穩定性，唐夲等[6]提出了一種MANET多參數加權分簇算法，綜合考慮了節點剩余能量、鄰居節點數和節點移動性，針對隨機步行移動網絡設計不同的節點穩定性參數，并基于約束規則和節點穩定性參數加權準則，有效提高了網絡簇結構的穩定性。雖然該方法可通過更穩定的簇結構提高數據傳輸成功率，但節點通信量增多，能量消耗量增大。夏輝等[7]提出了MANET中基于鏈路穩定性預測的組播路由協議，將一種新穎的鏈路穩定性預測模型應用于傳統組播路由協議中，而且基于反應式方式建立一棵高效的穩定組播樹以更好地適應網絡拓撲變化，能夠顯著地提高分組投遞率，降低分組端到端平均傳輸延時，且控制開銷較小，但對鏈路環境的考慮過于理想，鏈路干擾情況會影響預測結果。陳麗等[8]提出一種車載ad hoc網絡中基于移動網關的數據傳輸技術，運用馬爾可夫決策方法建立了一種基于MG轉發的I2V數據傳輸優化模型，并使I2V傳輸延遲最小的路口節點作為數據包與目的車輛的最優匯聚節點，以最優概率轉發序列向目標節點轉發數據包，能夠獲得最小傳輸延遲期望，然而該方法使得路口節點具有較大的能量負擔。Shubhajeet等[9]提出一種基于改進蟻群優化的MANET增強型動態源路由算法，可以降低數據包投遞過程中的端到端延遲和能源消耗，采用蟻群算法依靠信息素濃度搜索路線的啟發式方法，選擇平均信息素水平最高的最佳路線用于數據分組傳送。但該方法需要較多的迭代次數來選擇鏈路，影響算法對現實情況的反應時間。Chao等[10]提出一種MANET跳頻多通道MAC協議，該協議是一個多會合協議，解決接收數據的丟失問題，可以避免交換控制消息，具有較低的信令開銷并能實現較高的吞吐量，但網絡拓撲的變化會對算法性能造成較大影響。Chu等[11]提出一種利潤優化模型的MANET路由協議，采用了經濟學領域的一種數學模型利潤優化模型(凱利公式)，并引入到節點的移動性路由的選擇問題，將能耗、延遲等多種服務質量(Qua1ity of Service，QoS)指標作為路由的利潤問題，從而選擇QoS指標最優的路由。但該方法對網絡的移動模型并沒有進行更深入地分析，而現實中節點的移動方式會對路由的選擇帶來較大影響。

針對網絡拓撲變化對ad hoc網絡路由帶來的影響，本文受Levy Wa1k流動模型的啟發，提出了一種反映移動網絡間歇性連接的移動模型，能更加真實地反映節點移動軌跡和節點流動性，并根據粒子濾波的步行長度預測提出自適應路由算法。

2　網絡模型假設

在移動自組織網絡中，有研究顯示，采用單信息副本路由將一個信息傳遞到目的地，往往會導致較低的成功傳遞率并伴隨較高的傳輸延遲，而轉發太多的信息副本會降低信息傳遞效率。因此，針對間歇連接的移動網絡[12-13]，本文提出的自適應路由算法將主要研究三個方面的問題：如何最小化傳輸的信息數目；盡可能地降低傳輸延遲；實現較高的數據包成功投遞率。

在進行路由算法的討論之前，本文假設網絡模型具有如下特點：

(1)m個節點在面積為L×L的區域內隨機分布，并且獨立隨機移動；

(3)用vms表示信息的傳輸速度，vn表示節點的移動速度，并且消息的傳輸速度比一個節點的移動速度要快得多；

(4)節點之間的鏈路是雙向的，所有的數據包的大小相同，并且節點具有相同的傳輸速率；

(5)從一個源節點到一個目的節點的方向和距離仍未知。

3　Levy Walk移動模型

大多數MANET的路由協議和延遲容忍網絡的路由協議都是采用隨機或功能性的節點流動模型，在這些流動模型中，移動節點大多數時間都是與相鄰節點通信，從源節點將數據轉發到目的地需要較長的時間。因此，在本文算法中采用Levy Wa1k移動模型。Levy Wa1k移動模型的移動節點可以具有更長的移動長度，這增加了與多個遠程節點進行通信的機會，并提高了信息轉發至目的地的機會，并且Levy Wa1k移動模型更接近移動網絡間歇性連接的特點，具有更加真實的移動軌跡和節點流動性。文獻[16]已證明了1evy wa1k模型在表征移動網絡路由性能上的重要性[16]。

根據Levy Wa1k的統計特性，行走長度可分為長步行長度和短步行長度。短步行長度反映地域的限制作用，長步行長度反映節點想快速到達一些目的地的主觀意圖，具有更多的真實性。在Levy Wa1k移動模型中有4個重要的變量，行走長度l、方向角度θ、行走時間t和暫停時間tT。行走長度l和暫停時間tT可以從Levy分布的概率密度函數中隨機選擇。Levy分布的表達函數如下：

當λ=1時，Levy分布是一個柯西分布；當λ=2時是高斯分布；當λ＜2時，函數近似為

根據Levy分布，行走長度l可以被描述為

同樣地，行走時間t可以描述為

為了使Levy Wa1k移動模型更加適應間歇性連接的網絡，本文在節點步長上引入了最短和最長步長lmin、lmax。因此，新的步長模型可以描述為

式中：lmin、lmax分別由網絡節點中最小和最大的速度測量值所決定。對于暫停時間tT，定義為在一個較小的范圍內均勻分布：

方向角度θ的取值為(0°，360°)。

4　基于粒子濾波步行長度預測的路由算法

在提出Levy Wa1k移動模型后，接下來是將該移動模型與路由策略進行結合，通過節點的移動距離來確定消息的副本數量。因此，需要了解每個路由步驟的節點行走長度。本文采用了粒子濾波的方法來實現步行長度預測，而粒子濾波的方法是通過蒙特卡羅抽樣來得到一種遞歸貝葉斯濾波器。

本文先將節點的行走長度建模為一個狀態變量lk，根據狀態轉移方程可描述為

狀態轉移方程反映從狀態(k) -1到狀態k的概率。xk表示測量變量，可以得到測量公式為

式中：h(xk)表示測量函數，可以表示狀態變量lk和測量變量xk之間的關系。動態系統模型可以表示為

式中：lk表示在第k步的狀態值；lk-1表示在第k-1步的狀態值；uk是測量值輸入；pk是不可測量的值；ξk是測量誤差；a、b和c都表示函數系數。

由于動態系統模型很難描述在步驟(k-1，) k之間的行走長度的關系，因此本文采用的方法是間接地預測行走長度。首先建立一個函數來反映在第k步和k-1步中節點的步行長度總和之間的關系，接著在第k步中預測的步行長度的值將通過計算兩個總和之間的差值來得到。令Sk表示第k步的狀態測量值矢量，Sk=(x1，x2，…，xk)。為了獲得準確的狀態值，本文首先進行預測操作：

預測結果是基于先前k-1個觀測量，然后添加第k個觀測量來更新結果：

對于后先驗結果，本文使用了一組樣本或粒子來表示后驗概率：

并得到近似密度q(l)為

式中：φi的表達方程式為其中：Q(li)是重要性密度函數。

求出近似密度q(l)之后，將進行步行長度預測。下面給出具體流程。

式中：1＜Ne＜NTh；當所有的粒子具有相同的權重時Ne=NTh，并且當所有的概率集中在一個粒子時Ne= 1。閾值NTh設定為

Step 5 令k=k+1，并返回SteP 2。

lk表示粒子第k步的步行總和，lk-1表示粒子第k-1步的步行總和。

通過基于粒子濾波的方法得到步行長度l之后，本文提出了一個分段函數來確定消息發送的副本數量：

式中：M是消息的副本數量；l表示步行長度；α、β和γ都表示相應的變換系數。當確定了消息副本的數量N后，本文所制定的路由規則如下：

(1)為每一個消息副本建立一個存活時間T，一旦一個消息的存活時間達到T時，這個消息副本將被丟棄；

(2)每個傳感器節點都有對應的路由表記錄其自身的ID，當兩個節點滿足通信距離的要求時，它們首先檢查每個人的信息表，如果有消息副本是它們沒有共同擁有的，則一個傳感器會將消息副本轉發給沒有該消息副本的傳感器節點；

(3)一旦消息副本順利到達目的地，則目的節點將發送一個確認消息，當其他傳感器節點接收到該確認消息，將會刪除掉存留的該消息副本。

5　實驗仿真及分析

為了驗證本文提出的基于粒子濾波步行長度預測的移動通信系統自適應路由算法的性能，本文在實驗中采用Mat1ab 7.1仿真軟件對算法進行編程仿真?？紤]到移動通信節點在部署區進行數據監測時并不僅限于單一的移動方向，因此在實驗過程中采用的Levy Wa1k移動模型沒有節點移動的方向限制，移動角度范圍0°～360°，閾值NTh=10保證樣本的有效數量達到一定條件不出現較大的隨機概率。由于測量值、不可測量和測量誤差對節點步行的狀態值都具有一定的影響程度，在本實驗中將動態系統模型的函數系數設置為a=b=c=1，粒子濾波步行長度預測模型的變換系數設置為

在實驗條件不另外說明的條件下，仿真實驗中默認的隨機部署節點有50個，節點的移動速度取值范圍為(2 m/s，10 m/s)，節點隨機均勻分布在500 m×500 m的矩形區域，通信半徑為50 m。其中環境參數的設置參考了對比算法的實驗仿真條件，使得仿真結果的可對比性更高。每次的仿真實驗數據是進行50次仿真后所得結果的平均值，這可以將實驗數據結果的隨機性大大減小，并且該仿真次數下所得的平均值隨著仿真次數的增多而變化的情況非常小。

對于ad hoc網絡路由算法的性能評價，本文算法與文獻[9]中Shubhajeet等提出一種基于改進蟻群優化的方法以及文獻[11]中Chu等提出的基于利潤優化模型的方法進行對比。圖1顯示了在消息存活時間從50 s變化到400 s的過程中路由算法的消息成功投遞率，從圖中可以看出，隨著消息存活時間的增加，消息的成功投遞率也會增加。因為從源節點轉發數據到目的節點需要一定的時間，這個時間受到節點移動速度、節點數量等的影響，但消息的存活時間越長，則轉發到目的地的成功率也就更大。在圖1中，本文算法的消息成功投遞率最高達到了0.85，而基于改進蟻群優化的路由方法只達到了0.77，基于利潤優化模型的路由方法則為0.81。因此，相比之下本文的路由算法在傳遞消息時具有更大的成功率。這是由于在消息的存活期間，本文所制定的路由規則能夠確定出所需要的消息副本數量，防止節點轉發過多消息副本，提高消息的傳遞效率，而另外兩種方法對消息副本數并沒有達到數量上的控制，節點轉發多余的消息副本，影響了數據的傳輸效率。

大學生在返鄉就業創業過程中面臨的問題很多，除其自身就業創業能力不足外，更主要的是社會對大學生返鄉就業創業的支持力度不夠，特別是在政策、資金、教育等方面的支持還存在很多不足。

圖1　消息成功投遞率Fig.1 Successfu1 de1ivery rate of messages

圖2為算法的節點平均能量消耗的對比情況，可見隨著節點數量的增長，節點的平均能量消耗量都逐漸下降，但下降幅度逐漸變小。由于節點數量的增多使得帶有消息的節點將消息轉發給下一個節點時的傳輸距離變小，因此花費在傳輸能耗上的代價變低，節點的平均能量消耗量隨之減小。節點能量是維持傳感器網絡正常運作的生命力，因此常作為評價路由算法的重要指標之一。本文算法的平均能量消耗量在80個節點時可以降到0.67 J，而文獻[9]和文獻[11]算法則分別為0.79 J和0.76 J。因此，相比這兩種算法，采用本文方法可以使每個節點分別減少0.12 J和0.09 J的能量。由于目的節點接收到消息副本后會發送確認消息給其他節點，防止相同的消息副本繼續在節點之間進行傳輸，節省了一定的傳輸能耗，而其他算法在目的節點接收數據后并沒有對相同的消息副本進行刪除處理，無法減少多余的消息副本帶來的能量流失。

圖2　節點平均能量消耗Fig.2 Average energy consumPtion of nodes

圖3顯示了消息傳遞延遲的對比情況，可見消息的傳遞延遲時間越長，則網絡的數據傳輸效率越低。從圖中可以看出，隨著節點個數的增多，每個節點轉發消息的距離越短，帶來的消息傳遞延遲相應縮短。本文提出的算法在節點個數少于35個時消息傳遞延遲大于基于利潤優化模型的方法，但在節點個數大于35時消息傳遞延遲相比另外兩種算法更短。這是由于本文在實現節點的步行長度預測時需要一定的節點數量來確定后驗概率，因此節點數量較少時不利于預測精度的提升，步行長度較大或較短時都會使源節點傳輸數據到達目的節點的延遲時間變長。最終當節點個數增加到80個時延遲時間僅為9.4 ms，而另外兩種算法分別為15.7 ms和13.3 ms，相比之下分別縮短了6.3 ms和3.9 ms。因此，采用本文算法可以在網絡傳遞數據時帶來更少的延遲時間。

圖3　消息傳遞延遲Fig.3 Message de1ivery de1ay

6　結束語

本文提出了一種基于粒子濾波步行長度預測的移動通信系統自適應路由算法，采用了改進的Levy Wa1k移動模型，可以更加真實地表征網絡節點的移動軌跡和節點流動性；接著采用粒子濾波的方法來實現步行長度預測，通過預測粒子的行走長度來確定消息的副本數量，并通過制定的路由規則來傳遞消息。實驗仿真和對比分析表明，本文算法的消息成功投遞率可以達到85%，高于基于改進蟻群優化和利潤優化模型的路由算法，并且本文的方法相比這兩種對比算法分別可以使每個節點的能量消耗量減少0.12 J和0.09 J，在提高移動通信系統的數據傳輸效率和節能方面表現出了更好的效果。該算法的不足之處在于進行步行長度預測時需要一定的節點數量來提升預測精度，因此在今后的研究中會重點關注這個問題，使得在移動節點較少的網絡場景中本文算法仍能保持較高的數據傳輸效率。

[1] LEE S B，WONG S H Y，LEE K W，et a1.Content management in a mobi1e ad hoc network：beyond oPPortunistic strategy[J].Internationa1 Journa1 of Communication Networks&Distributed Systems，2013，10(2)：266-270.

[2] JANARTHANAN S，VICTOIRE T A A.Qua1ity of service routing issues in mobi1e ad hoc network-review[J].Internationa1 Journa1 of Scientific Engineering and Techno1ogy，2013，2(5)：431-437.

[3] AGGARWAL P，AGGARWAL H.Energy-efficiency based ana1ysis of routing Protoco1s in mobi1e ad-hoc networks(MANETs)[J].Internationa1 Journa1 of ComPuter APP1ications，2014，96(15)：15-23.

[4] TAILOR R，BARIA J.The study of wormho1e attack in mobi1e ad hoc network[J].Internationa1 Journa1 of Com-Puter APP1ications，2014，87(18)：20-25.

[5] GULATI M K，KUMAR K.Performance comParison of mobi1e ad hoc network routing Protoco1s[J].Internationa1 Journa1 of ComPuter Networks&Communications，2014，6(11)：77-84.

[6] 唐夲，劉改霞，鐘汶娟.移動ad hoc網絡多參數加權分簇算法[J].重慶大學學報，2014，37(2)：107-112.

TANG Tao，LIU Gaixia，ZHONG Wenjuan.Mobi1e ad hoc network is a mu1ti Parameter weighted Points c1ustering a1-gorithm[J].Journa1 of Chongqing University，2014，37 (2)：107-112.(in Chinese)

[7] 夏輝，賈智平，張志勇，等.移動ad hoc網絡中基于鏈路穩定性預測的組播路由協議[J].計算機學報，2013，36(5)：927-936.

XIA Hui，JIA ZhiPing，ZHANG Zhiyong，et a1.Mu1ticast routing Protoco1 based on 1ink stabi1ity Prediction in mobi1e ad hoc networks[J].Journa1 of ComPuter Science，2013，36(5)：927-936.(in Chinese)

[8] 陳麗，李治軍，姜守旭，等.車載ad hoc網絡中基于移動網關的數據傳輸[J].計算機學報，2012，35(3)：454-463.

CHEN Li，LI Zhijun，JIANG Shouxu，et a1.Data transmission based on mobi1e gateway in hoc ad networks[J]. Journa1 of ComPuter Science，2012，35(3)：454-463. (in Chinese)

[9] CHATTERJEE S，DAS S.Ant co1ony oPtimization based enhanced dynamic source routing a1gorithm for mobi1e Ad -hoc network[J].Information Sciences，2015，295 (295)：67-90.

[10] CHAO C M，TSAI H C.A channe1-hoPPing mu1tichanne1 MAC Protoco1 for mobi1e ad hoc networks[J].IEEE Transactions on Vehicu1ar Techno1ogy，2014，63(9)： 4464-4475.

[11] WANG C，DING J，CHEN T.A routing Protoco1 for mobi1e ad-hoc networks using the Profit oPtimization mode1 [J].Internationa1 Journa1 of Communication Systems，2014，27(11)：2851-2869.

[12] UPADHYAY S，JOSHI P，KUMARI N G A A.ComParison and Performance ana1ysis of reactive tyPe DSR，AODV and Proactive tyPe DSDV routing Protoco1 for wire1ess mobi1e ad-hoc network using NS-2 simu1ator [J].Journa1 of Engineering and ComPuter Innovations，2012(2)：36-47.

[13] RAHMAN M A，ANWAR F，NAEEM J，et a1.A simu1ation based Performance comParison of routing Protoco1 on mobi1e ad-hoc network(Proactive，reactive and hybrid) [C]//Proceedings of 2010 IEEE Internationa1 Conference on ComPuter and Communication Engineering. Kua1a LumPur：IEEE，2010：1-5.

[14] HABBAL A M M，HASSAN S.Loss detection and recovery techniques for TCP in mobi1e ad hoc network [C]//Proceedings of Second Internationa1 Conference on Network APP1ications Protoco1s and Services.Kedah：IEEE，2010：48-54.

[15] ROCHI M H B，DANA A，ZIYAEE M，et a1.A new source routing mechanism in mobi1e ad-hoc network [C]//Proceedings of 2011 13th Internationa1 Conference on Advanced Communication Techno1ogy.Seou1：IEEE，2011：948-952.

[16] RHEE I，SHIN M，HONG S，et a1.On the 1evy-wa1k nature of human mobi1ity[J].IEEE/ACM Transactions on Networking，2011，19(3)：630-643.

張 玲(1979—)女，山東平度人，2008年于北京郵電大學獲碩士學位，現為北京職業技術學院講師，主要研究方向為圖形圖像處理、信號傳輸、媒體設備應用、電子技術、編解碼算法研究等；

ZHANG Ling was born in Pingdu，Shandong Province，in 1979.She received the M.S.degree from Beijing University of Posts and Te1ecommunications in 2008.She is now a 1ecturer.Her research concerns imaging Processing，signa1 transmission，media equiPment aPP1ication，e1ectronics and coding a1gorithms.

聶韶華(1972—)男，山東費縣人，2008年于哈爾濱理工大學獲碩士學位，現為講師，主要研究方向為計算機科學于技術、教育信息技術。

NIE Shaohua was born in Feixian，Shandong Province，in 1972.He received the M.S.degree from Harbin University of Techno1ogy in 2008.He is now a 1ecturer.His research concerns comPuter science and education information.

A Mobile ad hoc Network Routing Algorithm Based on Walking Length Prediction after Particle Filtering

ZHANG Ling1，NIE Shaohua2
(1.DePartment of E1ectronic Engineering，Beijing Information Techno1ogy Co11ege，Beijing 100015，China；2.E1ementary Education Co11ege，Linyi University，Linyi 276000，China)

For the Prob1ems of mobi1e ad hoc network(MANET)such as big change of toPo1ogy structure，high routing comP1exity，and 1ow data transmission Performance，this PaPer ProPoses a new mobi1e communication system using an adaPtive routing a1gorithm.In order to make the network toPo1ogy c1oser to the characteristics of the mobi1e network intermittent connection，an imProved Levy Wa1k Mobi1ity Mode1 is adoPted in the network structure.And then，a Partic1e fi1tering wa1king 1ength method Prediction is used to get a recursive Bayesian fi1ter throush Monte Car1o samP1ing，and the wa1king 1ength is Predicted after Partic1e fi1tering to determine the number of coPies of message，thereby reducing the energy consumPtion for node forwarding a coPy to bring too many messages and imProve the message de1ivery efficiency.Simu1ation resu1ts show that comPared with two routing a1gorithms of ant co1ony-based oPtimization and Profit oPtimization-based mode1，the ProPosed a1gorithm imProves the message Passing success rate of 0.08 and 0.04，node average energy efficiency of 17.9%and 13.4%，resPective1y.So it achieves better resu1ts in imProving the success rate of data transfer and saving energy.

mobi1e ad hoc network；Partic1e fi1tering；wa1king 1ength Prediction；Levy Wa1k mobi1ity mode1；adaPtive routing a1gorithm **

TN915

A

1001-893X(2016)03-0331-06

10.3969/j.issn.1001-893x.2016.03.017

2015-06-22;

2015-10-13 Received date:2015-06-22;Revised date:2015-10-13通信作者:zhang1ing-n@bitc.edu.cn Corresponding author:zhang1ing-n@bitc.edu.cn