基于蟻群算法的無線自組網絡能量控制路由研究*

宋軍全，周 凱*，華驚宇

(1.浙江工業大學理學院，杭州 310023；2.東南大學移動通信國家重點實驗室，南京 210096)

無線自組網絡MANET(Mobile Ad Hoc Network)是一種具有全新的信息獲取、信息處理與傳輸技術的通信網絡，具有組網快捷、靈活，且不受有線網絡約束的優點，可用于緊急搜索、災難救助、軍事、醫療等環境中，具有廣泛的應用前景。MANET已經引起了學術界和工業界的高度重視，被稱為是21世紀最有發展前景的技術之一［1］。

MANET環境下，節點間的無線鏈路及由此而形成的網絡拓撲結構隨節點的位置分布和移動、信道的變化等因素呈現出動態變化的特性，網絡的路由技術面臨挑戰。近年來，國際上對MANET路由協議的研究日趨活躍，除了表驅動路由協議和按需路由選擇協議，信息理論學者還提出了合作分集路由，認為傳統路由并不是最好的路由。合作分集通過多個中繼采用廣播傳輸發送信息，目的節點選擇許多中繼信號中最好的，或者將多個中繼信號進行組合處理。這種路由方案必須對同一個信號經過多個路徑傳播后的同步和定時進行嚴格處理，或者對每一條中繼的無線信道進行處理，網絡節點計算非常復雜。傳統的以節點為中心的分布式MANET網絡路由復雜且每個分布式節點計算量龐大，造成網絡傳輸的實時性、吞吐量、端到端延時、網絡服務質量QoS(Quality of Service)等性能下降，不適合MANET。從而探索一種新型的路由協議，對MANET網絡技術的研究具有重要的意義［2］。為此，很多研究者提出使用啟發式算法進行路由搜索，如遺傳算法、神經網絡、Grover搜索算法、蟻群算法等［3］。

蟻群算法是近年來提出的一種源于大自然的仿生類算法，對于解決組合優化問題和通信網絡問題有很好的應用前景。它主要通過螞蟻在尋路過程中與環境之間的信息交換，實現螞蟻群體間的信息傳遞，并最終達到尋找最優路徑的目的。蟻群算法通過信息素的不斷更新，實現最終收斂于最優路徑的目的。蟻群算法是一種正反饋機制，同時具有隨機性、自適應性和分布式等特點，適合并行計算和求精確解。因此，本文沿用了蟻群算法思想，并將其融入MANET路由設計方案，以更好地解決路由的能量控制問題，提高網絡生存時間，最終實現合理有效利用網絡資源的目的。

1 網絡節點特性數學模型

MANET節點之間是靠無線電進行通信，可以建立網絡節點一階能量消耗模型，如圖1所示。發送數據能量消耗包括發射電路耗能、放大電路耗能兩部分，接收數據只有接收電路消耗能量。一階能量消耗模型數學模型可以表示如下［4］:

圖1 MANET網路節點一階能量消耗模型

其中，ETx表示發送者能量消耗，ERx表示接收者能量消耗，Eelec表示發射電路和接收電路的能耗，l表示發送數據包包含的比特數，d表示傳輸距離，εfs是常數。上述參數典型值為:Eelec=50 nJ/bit，εfs=10 pJ/(bit·m2)［5］。

網絡中所有節點處于動態移動狀態，本節將描述網絡節點的運動狀態以及節點間的連通狀況。節點i在時刻t的位置、速率和運動方向可以依次表示為(xi(t)，yi(t))、vi(t)、θi(t)。因此，節點運動特性可以用下式描述［6－7］:

在時刻t，節點i和節點j之間的距離可以表示為式(3):

在MANET中，兩節點間直接通信距離為R。如果兩點間的距離小于R，則兩節點可以直接通信；否則兩節點間需要通過中間節點轉發才可以進行通信。定義節點連通性矩陣D(t)=(dij(t))N×N。如果元素為“1”，表示兩點間可以直接通信，如果元素為“0”，表示兩節點間不能直接通信。因此，矩陣中的元素應滿足如下條件:

在時刻t，節點i的節點度Degreei(t)表示與此相連接的節點數量，可以表示如下:

2 基于能量控制的蟻群優化算法

根據網絡節點特性分析，本節將結合蟻群算法思想，建立基于能量控制的蟻群路由算法。該算法的基本原理是:當進行路由搜索時，上一跳節點i需要考慮以下兩方面進行路由選擇:與之相鄰節點j組成的鏈路剩余能量τij(t)；與之相鄰節點j的度數Degreej(t)。通過以上兩個方面，從而確定節點j作為下一跳節點的概率。

鏈路的剩余能量是由組成這條鏈路的兩端節點的最少剩余能量所決定，當其中一端節點因能量消耗而退出網絡時，此條鏈路也就失效。因此，鏈路剩余能量τij(t)的計算方式可以如下所示:

其中，Ei(t)表示節點i在時刻t的剩余能量。通過以上分析，可以給出相鄰節點j被選擇作為下一跳節點的概率 pij(t)表示如下［8－9］:

其中，α和β兩個參數分別反映數據在網絡傳輸過程中所積累的剩余能量信息和節點度數信息在路由選擇過程中的相對重要性，α+β=1。

本文提出的基于能量控制蟻群路由模型，其具體算法如下:

Step 1:當需要進行網絡數據傳輸時，首先確定源節點標號s和目的節點標號k。尋找源節點一跳范圍內的節點j，形成節點集合J{j|dsj(t)=1}。比較目標節點標號k是否在集合J中:如果是，則終止計算，選擇節點k進行信息傳輸；如果不是，則進行節點概率計算［10－11］。

Step 2:尋找上一跳節點i一跳范圍內的節點j，形成節點集合J{j|dij(t)=1}，將判斷目標節點標號k是否在集合J中或者跳數是否超過上限。如果在集合J中或者跳數超過上限，則終止計算；否則，根據式(7)，計算每個一跳范圍內節點j的被選擇pij(t)，選擇高概率的節點作為下一跳節點。節點m被選擇作為下一跳節點的條件如下所示:

Step 3:完成節點概率計算，確定下一跳節點進行數據轉發后，循環進行Step 2，直到目標節點標號k出現在下一跳的集合J中或者跳數達到上限為止［12］。

綜上所述，基于能量控制的蟻群路由算法模型框架圖，如圖2所示。

圖2 基于能量控制的蟻群路由算法模型框架圖

3 網絡仿真

為了進一步分析提出的基于蟻群優化思想的路由協議的性能，本節建立了網絡仿真模型對協議進行分析。在一個1 000 m×1 000 m的網絡中，散落著80個節點，這些節點在網絡中隨機移動。移動的速度在［0，5 m/s］之間變化，運動角度在［0，2π］之間隨機變化，變化概率服從均勻分布。當節點在下一時刻將要運動至邊界時，進行反向運動。在網絡中假設每個節點的一跳通信范圍是100 m。在初始時刻，節點的位置分布如圖3所示。

為了說明基于蟻群優化思想的路由協議的優越性，本文定義網絡中最后一個節點退出網絡的時間為表示網絡生存時間的指標，最后退出網絡的節點被稱為瓶頸節點。最后一個節點退出網絡的時間越遲，說明網絡的生存時間越長。動態源路由協議DSR(Dynamic Source Routing)是一種典型的按需驅動路由協議，許多路由協議都在DSR協議上發展而成。本節采用Matlab軟件進行網絡仿真，每個節點最初時的能量為“1”。在基于能量控制的蟻群路由算法中，參數 α=β=0.5，ρ=0.5。對網絡的兩種協議(DSR路由協議與蟻群算法路由協議)進行仿真，得到瓶頸節點能量的仿真圖如圖4所示。由圖可見，基于蟻群優化思想的路由協議能夠提供保障網絡能量，從而提高網絡生存時間。

圖3 網絡節點位置分布圖

圖4 兩種算法協議下的瓶頸節點能量變化圖

為了分析α和β兩個參數對于網絡剩余能量所產生的影響，對不同的參數組合進行網絡仿真，仿真圖如圖5所示。由圖可見，基于蟻群優化思想的路由協議下，不同的參數α能夠提供不同的網絡能量保障。

圖5 各種參數下網絡能量仿真圖

4 結束語

在深入分析無線自組網絡路由協議之后，提出了一種基于蟻群優化思想的路由算法。在這種方法中，首先系統地分析網絡節點能量變化特性；然后基于蟻群能量優化思想建立節點選擇概率函數；最后選擇高概率的節點進行數據轉發。仿真結果表明:該文提出的路由算法能夠提供能量保障、延長網絡生存時間等特點，彌補了已有算法的不足。

［1］任敬安，涂亞慶，張敏，等.基于蟻群優化的Ad Hoc網絡生存時間和其他網絡性能平衡路由協議［J］.計算機工程與科學，2011，33(11):15－24.

［2］曲大鵬，王興偉，黃敏，等.移動自組織網絡下的基本蟻群路由算法［J］.計算機應用，2011，31(5):1166－1169.

［3］王鎮，劉學軍.WSN中基于蟻群算法的Qos路由協議［J］.傳感技術學報，2011，24(11):1625－1631.

［4］周少瓊，徐祎，田上成，等.基于蟻群算法的Ad hoc網絡節點信息感知路由研究［J］.探測與控制學報，33(1):75－79.

［5］梁淑萍，毛力，馬亦先.基于蟻群算法的Ad Hoc網絡QoS組播路由研究［J］.微電子學與計算機，28(7):28－33.

［6］胡彧，王靜.基于蟻群算法的LEACH協議研究［J］.傳感技術學報，2011，24(5):747－751.

［7］陳鳳超，李融林.基于路由代價的無線傳感器網絡蟻群路由算法［J］.華南理工大學學報(自然科學版)，2011，39(5):36－43.

［8］莫桂江.蟻群－遺傳算法的無線傳感器網絡路徑優化［J］.微電子學與計算機，2011，28(9):54－59.

［9］黃如，苗澎，陳志華.基于預測模式蟻群優化的傳感網節能路由機制究［J］.傳感技術學報，2010，23(5):701－707.

［10］Liao W H，Kao Y，Fan C M.Data Aggregation in Wireless Sensor Networks Using Ant Colony Algorithm［J］.Networks and Computer Applications，2008，31(4):387－401.

［11］鄭慧君，張巍，滕少華.基于改進蟻群的無線傳感器網絡路由［J］.計算機應用研究，2010，27(1):99－100.

［12］Kallapur，Pranesh V Chiplunkar，Niranjan N.Toplogy Aware Mobile Agent for Efficient Data Collection in Wireless Sensor Networks with Dynamic Deadlines［C］//Advances in Computer Engineering(ACE)，2010 International Conference on Bangalore，Karnataka，India，2010:352－356.