宋軍全，周 凱*，華驚宇

(1.浙江工業(yè)大學(xué)理學(xué)院，杭州 310023；2.東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京 210096)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 網(wǎng)絡(luò)仿真

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

［9］黃如，苗澎，陳志華.基于預(yù)測(cè)模式蟻群優(yōu)化的傳感網(wǎng)節(jié)能路由機(jī)制究［J］.傳感技術(shù)學(xué)報(bào)，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］鄭慧君，張巍，滕少華.基于改進(jìn)蟻群的無(wú)線傳感器網(wǎng)絡(luò)路由［J］.計(jì)算機(jī)應(yīng)用研究，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.