宋軍全，周 凱*，華驚宇

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

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

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

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

1 網(wǎng)絡節(jié)點特性數(shù)學模型

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

圖1 MANET網(wǎng)路節(jié)點一階能量消耗模型

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

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

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

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

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

2 基于能量控制的蟻群優(yōu)化算法

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

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

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

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

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

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

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

Step 3:完成節(jié)點概率計算，確定下一跳節(jié)點進行數(shù)據(jù)轉發(fā)后，循環(huán)進行Step 2，直到目標節(jié)點標號k出現(xiàn)在下一跳的集合J中或者跳數(shù)達到上限為止［12］。

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

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

3 網(wǎng)絡仿真

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

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

圖3 網(wǎng)絡節(jié)點位置分布圖

圖4 兩種算法協(xié)議下的瓶頸節(jié)點能量變化圖

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

圖5 各種參數(shù)下網(wǎng)絡能量仿真圖

4 結束語

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

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

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

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

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

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

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

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

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

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

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

［11］鄭慧君，張巍，滕少華.基于改進蟻群的無線傳感器網(wǎng)絡路由［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.