劉建娟

（河南工業(yè)大學(xué)電氣工程學(xué)院，河南南陽(yáng)450001）

基于改進(jìn)螢火蟲(chóng)群優(yōu)化的無(wú)線自組網(wǎng)路由算法*

劉建娟*

（河南工業(yè)大學(xué)電氣工程學(xué)院，河南南陽(yáng)450001）

針對(duì)無(wú)線自組網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)多變、網(wǎng)絡(luò)生存時(shí)間受限及數(shù)據(jù)包分組傳輸效率低下等問(wèn)題，借鑒螢火蟲(chóng)群優(yōu)化算法，提出了一種改進(jìn)螢火蟲(chóng)群優(yōu)化的無(wú)線自組網(wǎng)絡(luò)路由算法。路由算法將螢火蟲(chóng)優(yōu)化算法中的熒光素強(qiáng)度更新與無(wú)線自組網(wǎng)絡(luò)中的節(jié)點(diǎn)移動(dòng)速度、擁塞程度、節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)間距離等因素進(jìn)行相互映射，同時(shí)改進(jìn)螢火蟲(chóng)群優(yōu)化算法中的搜索螢火蟲(chóng)、駐留螢火蟲(chóng)及回溯螢火蟲(chóng)用于完成無(wú)線自組網(wǎng)絡(luò)中路由協(xié)議的路由發(fā)現(xiàn)、路由選擇及路由維護(hù)等過(guò)程，整個(gè)協(xié)議無(wú)須傳送大量的控制分組，即可實(shí)現(xiàn)無(wú)線自組網(wǎng)絡(luò)的穩(wěn)定傳輸。仿真實(shí)驗(yàn)結(jié)果表明，與AODV及基于蟻群優(yōu)化的路由算法AntRouting協(xié)議相比，本文所提出的路由算法在端到端延時(shí)、分組數(shù)據(jù)傳輸率及網(wǎng)絡(luò)生存時(shí)間上均有良好的性能。

無(wú)線自組網(wǎng)絡(luò)；路由協(xié)議；螢火蟲(chóng)群優(yōu)化算法；網(wǎng)絡(luò)生存；節(jié)點(diǎn)能耗

傳統(tǒng)的通信網(wǎng)絡(luò)對(duì)基礎(chǔ)設(shè)施的依賴程度很高，被毀后恢復(fù)費(fèi)用高、網(wǎng)絡(luò)重建時(shí)間周期長(zhǎng)。而無(wú)線自組織網(wǎng)絡(luò)可以根據(jù)業(yè)務(wù)需求和網(wǎng)絡(luò)情況進(jìn)行快速組網(wǎng)，其網(wǎng)絡(luò)的節(jié)點(diǎn)既是移動(dòng)終端也是路由器，這使得無(wú)線自組網(wǎng)在荒野探測(cè)、水下監(jiān)測(cè)等方面擁有廣泛的應(yīng)用前景。由于節(jié)點(diǎn)的任意移動(dòng)性，無(wú)線自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)變化頻繁，路由協(xié)議一直是無(wú)線自組網(wǎng)的研究重點(diǎn)。無(wú)線自組網(wǎng)路的路由協(xié)議主要考慮節(jié)點(diǎn)移動(dòng)及節(jié)點(diǎn)能量等不確定因素，其中節(jié)點(diǎn)能耗是路由協(xié)議的關(guān)鍵［1］。大多數(shù)無(wú)線自組網(wǎng)的路由選擇依據(jù)采用單一標(biāo)準(zhǔn)。單一標(biāo)準(zhǔn)的路由協(xié)議對(duì)下一跳路由的選擇上是基于一種規(guī)則，比如動(dòng)態(tài)源路由DSR［2］和目的地序列距離向量路由DSDV［3］都是選擇跳數(shù)最少的路由，按需距離向量路由協(xié)議AODV則選擇序列號(hào)最新的作為路由。單一標(biāo)準(zhǔn)的路由選擇設(shè)計(jì)較為簡(jiǎn)單，控制分組的大小和數(shù)量一定，但其無(wú)法滿足無(wú)線自組網(wǎng)拓?fù)浣Y(jié)構(gòu)多變、無(wú)線信道易受干擾等問(wèn)題。研究學(xué)者為了改進(jìn)單一標(biāo)準(zhǔn)路由協(xié)議的弊端，利用綜合指標(biāo)來(lái)選擇路由。例如文獻(xiàn)［4］利用名聲、可用帶寬和最小跳數(shù)作為路由選擇標(biāo)準(zhǔn)進(jìn)行多量考核以選擇合適的路由；文獻(xiàn)［5］通過(guò)考慮跳數(shù)、時(shí)延、節(jié)點(diǎn)擁塞程度等因素來(lái)選擇合適的路由路徑，以實(shí)現(xiàn)多路徑平衡網(wǎng)絡(luò)負(fù)載；文獻(xiàn)［6］提出了一種基于路徑選擇和拒絕應(yīng)答算法的PS-AODV協(xié)議，以解決高負(fù)載網(wǎng)絡(luò)，節(jié)約網(wǎng)絡(luò)節(jié)點(diǎn)能耗。雖然多指標(biāo)路由協(xié)議能在一定程度上解決單一標(biāo)準(zhǔn)路由協(xié)議的弊端，但往往以增加控制分組大小和數(shù)量、增大網(wǎng)絡(luò)均衡負(fù)擔(dān)等為前提，這樣就不可避免的造成無(wú)線自組網(wǎng)絡(luò)穩(wěn)定性低、可靠性差等。

螢火蟲(chóng)算法作為一種新興的群智能優(yōu)化方法，具有參數(shù)少、宜于并行處理、收斂速度快及魯棒性強(qiáng)等優(yōu)點(diǎn)，已經(jīng)在諸多領(lǐng)域取得了較好的應(yīng)用［7-10］。文獻(xiàn)［11］提出了一種加速螢火蟲(chóng)優(yōu)化算法，對(duì)螢火蟲(chóng)算法搜索過(guò)程進(jìn)行改進(jìn)，減少螢火蟲(chóng)個(gè)體的隨機(jī)移動(dòng)；文獻(xiàn)［12］提出了一種新的模糊螢火蟲(chóng)優(yōu)化算法，以增強(qiáng)算法的局部探索和全局搜索能力；文獻(xiàn)［13］引入螢火蟲(chóng)個(gè)體行為狀態(tài)表，記錄每個(gè)螢火蟲(chóng)個(gè)體的詳細(xì)行為，平衡個(gè)體的跳轉(zhuǎn)能力，使搜索能力較差的螢火蟲(chóng)跳轉(zhuǎn)到新的位置，以提高算法找到最優(yōu)解的概率。這些改進(jìn)都是為了增強(qiáng)螢火蟲(chóng)算法的搜索能力，優(yōu)化最優(yōu)解；文獻(xiàn)［14］中提出了通過(guò)引入隨迭代而線性減小的慣性權(quán)重，調(diào)節(jié)每次迭代對(duì)下一次迭代的影響，從而提高算法的搜索能力，提高搜索精度；文獻(xiàn)［15］提出了實(shí)數(shù)二進(jìn)制編碼的螢火蟲(chóng)優(yōu)化算法，用于解決網(wǎng)絡(luò)可靠性問(wèn)題；文獻(xiàn)［16］對(duì)螢火蟲(chóng)算法的個(gè)體進(jìn)行了改進(jìn)，使其帶有量子行為，設(shè)計(jì)出了新的螢火蟲(chóng)個(gè)體移動(dòng)方式，對(duì)螢火蟲(chóng)的路徑選擇提出了新的思路?？v觀螢火蟲(chóng)群優(yōu)化算法可知：螢火蟲(chóng)種群的初始分布猶如無(wú)線自組網(wǎng)絡(luò)中的路徑節(jié)點(diǎn)，路由路徑的選擇形成就類似于螢火蟲(chóng)的移動(dòng)求解。這種優(yōu)良的分布式特性和在組合優(yōu)化問(wèn)題中的表現(xiàn)與無(wú)線自組網(wǎng)的路由選擇較為相似［13-20］?；诖?，本文借鑒螢火蟲(chóng)優(yōu)化算法的原理，提出了一種基于螢火蟲(chóng)優(yōu)化算法的無(wú)線自組網(wǎng)絡(luò)路由協(xié)議，路由協(xié)議用螢火蟲(chóng)優(yōu)化算法的熒光素強(qiáng)度的更新規(guī)則與無(wú)線自組網(wǎng)絡(luò)中的節(jié)點(diǎn)移動(dòng)速度、擁塞程度、節(jié)點(diǎn)剩余能量及節(jié)點(diǎn)間的距離等因素相互映射，從而對(duì)路由的自適應(yīng)選擇進(jìn)行控制。

1 螢火蟲(chóng)優(yōu)化算法

1.1 螢火蟲(chóng)優(yōu)化算法簡(jiǎn)述

人工螢火蟲(chóng)群優(yōu)化算法GSO（Glowworm Swarm Optimization）是模仿螢火蟲(chóng)發(fā)光行為構(gòu)造出的仿生物智能群優(yōu)化算法［21］。在人工螢火蟲(chóng)群優(yōu)化算法的構(gòu)思中，每個(gè)個(gè)體都有自己的動(dòng)態(tài)決策范圍，并根據(jù)自身決策范圍內(nèi)鄰居個(gè)體信號(hào)的強(qiáng)弱決定其移動(dòng)方向，這與螢火蟲(chóng)通過(guò)釋放熒光素來(lái)吸引同伴的原理是相似的。GSO算法主要包括熒光素更新、移動(dòng)概率更新、移動(dòng)位置更新和鄰居范圍更新等4個(gè)階段［22］。達(dá)到一定的迭代次數(shù)后，所有的螢火蟲(chóng)個(gè)體都將聚集在問(wèn)題求解空間的最優(yōu)解位置［23］。在算法實(shí)現(xiàn)過(guò)程中，xi(t)表示t時(shí)刻第i只螢火蟲(chóng)的位置，f(x)為適應(yīng)度評(píng)價(jià)函數(shù)，li(t)表示t時(shí)刻第i只螢火蟲(chóng)的熒光素濃度［24］：

式中：ρ為螢光素?fù)]發(fā)系數(shù)，γ為螢光素增強(qiáng)因子，設(shè)rs表示螢火蟲(chóng)感知范圍，表示t時(shí)刻第i只螢火蟲(chóng)的決策范圍，更新動(dòng)態(tài)決策域半徑：

式中：β表示決策域變化率，ni表示鄰居閾值，Ni(t)表示t時(shí)刻第i只螢火蟲(chóng)的鄰居集合：

式中：li(t)表示t時(shí)刻第i只螢火蟲(chóng)的熒光素值，根據(jù)螢火蟲(chóng)鄰居集合中各螢火蟲(chóng)的熒光素濃度來(lái)決定螢火蟲(chóng)的移動(dòng)方向，Pij(t)表示表示t時(shí)刻第i只螢火蟲(chóng)向鄰居節(jié)點(diǎn)終第j只螢火蟲(chóng)靠近的概率：

根據(jù)移動(dòng)概率Pij(t)，設(shè)移動(dòng)步長(zhǎng)為s，t+1時(shí)刻第i只螢火蟲(chóng)的位置更新為：

1.2 無(wú)線自組網(wǎng)絡(luò)參數(shù)

為了利用螢火蟲(chóng)優(yōu)化算法來(lái)進(jìn)行無(wú)線自組網(wǎng)的路由選擇，設(shè)Q=(V,E)為含有n個(gè)節(jié)點(diǎn)的全連接無(wú)向圖，V是頂點(diǎn)集合且n=|V|，E是邊的集合。用兩個(gè)節(jié)點(diǎn)vi、vj的歐式距離dij表示節(jié)點(diǎn)間邊的權(quán)值，并且dij=dji。尋找全連接無(wú)向圖Q中源節(jié)點(diǎn)vi到目的節(jié)點(diǎn)vd的最優(yōu)路徑即轉(zhuǎn)化為螢火蟲(chóng)優(yōu)化算法的最優(yōu)求解。

在無(wú)線自組網(wǎng)中，某一時(shí)刻t節(jié)點(diǎn)vi需要存儲(chǔ)并維護(hù)當(dāng)前時(shí)刻鄰居節(jié)點(diǎn)信息表和路由信息的路由表，對(duì)應(yīng)的駐留螢火蟲(chóng)Ri則帶攜帶節(jié)點(diǎn)vi的熒光素值Li(t)。其中每個(gè)節(jié)點(diǎn)存儲(chǔ)的鄰居節(jié)點(diǎn)信息表項(xiàng)主要包括：鄰居節(jié)點(diǎn)vj、時(shí)間t、vj駐留螢火蟲(chóng)Rj熒光素值Lj(t)。為了均衡網(wǎng)絡(luò)負(fù)擔(dān)，路由表按需建立。路由表項(xiàng)包括：目的節(jié)點(diǎn)vd、下一跳節(jié)點(diǎn)vj、vi通過(guò)vj到vd的熒光素概率Pij(t)。當(dāng)需要進(jìn)行路由構(gòu)建時(shí)，節(jié)點(diǎn)vi根據(jù)需要?jiǎng)?chuàng)建搜索螢火蟲(chóng)Fe。搜索螢火蟲(chóng)Fe根據(jù)鄰居節(jié)點(diǎn)駐留螢火蟲(chóng)Rj熒光素值Lj(t)及兩個(gè)節(jié)點(diǎn)vi、vj的歐式距離dij計(jì)算節(jié)點(diǎn)vj作為下一跳的概率Pij(t)。設(shè)vi在t時(shí)刻所有一跳鄰居節(jié)點(diǎn)的集合為Qi(t)，則：

式（6）通過(guò)調(diào)節(jié)α和β來(lái)調(diào)整兩個(gè)相鄰節(jié)點(diǎn)的熒光素差值和節(jié)點(diǎn)間的歐式距離以影響搜索螢火蟲(chóng)對(duì)下一跳節(jié)點(diǎn)的選擇。按照上式選定下一跳節(jié)點(diǎn)vj后，移動(dòng)搜索螢火蟲(chóng)到節(jié)點(diǎn)vj，更新當(dāng)前位置并和鄰域半徑并將鄰域集合更新為Qj(t)。

每個(gè)節(jié)點(diǎn)vi的熒光素值Li(t)的更新公式如下：

式中：Li(t+1)為時(shí)刻t+1時(shí)節(jié)點(diǎn)vi上vj駐留螢火蟲(chóng)Ri的熒光素值。為熒光素值揮發(fā)系數(shù)，用?表示熒光素值增強(qiáng)系數(shù)，J[fi(t+1)]為t+1時(shí)刻vi的適應(yīng)度函數(shù)值。

2 基于螢火蟲(chóng)優(yōu)化算法的路由協(xié)議

無(wú)線自組網(wǎng)絡(luò)在沒(méi)有任何網(wǎng)絡(luò)基礎(chǔ)的情況下動(dòng)態(tài)獨(dú)立的臨時(shí)性網(wǎng)絡(luò)。路由協(xié)議是決定網(wǎng)絡(luò)性能的核心影響因素。由于無(wú)線自組網(wǎng)絡(luò)的特殊性，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)隨網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)而改變，傳統(tǒng)的網(wǎng)絡(luò)路由協(xié)議已不再適用。自組網(wǎng)絡(luò)中路由協(xié)議受節(jié)點(diǎn)能量、節(jié)點(diǎn)擁塞程度以及節(jié)點(diǎn)移動(dòng)速度的影響。節(jié)點(diǎn)能量越大的節(jié)點(diǎn)越適宜作為路由節(jié)點(diǎn)，因?yàn)槠溆凶銐虻哪芰客瓿尚畔⒌膫鬏?，保證自組網(wǎng)絡(luò)的壽命；節(jié)點(diǎn)越擁塞側(cè)面反映節(jié)點(diǎn)的處理能力不足，這間接會(huì)降低數(shù)據(jù)包收發(fā)的準(zhǔn)確率；節(jié)點(diǎn)的移動(dòng)速度對(duì)路由協(xié)議的影響是最直接的，節(jié)點(diǎn)移動(dòng)越快，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化越快，路由協(xié)議需要相應(yīng)的改變。

2.1 路由協(xié)議影響參數(shù)

①節(jié)點(diǎn)能量剩余參數(shù)λen在無(wú)線自組網(wǎng)中節(jié)點(diǎn)以電池供電。電池的電量隨著時(shí)間的延續(xù)會(huì)慢慢減少，節(jié)點(diǎn)路由只有剩余足夠多的能量才能完成尋找合適的路徑和轉(zhuǎn)發(fā)分組數(shù)據(jù)，這樣才能延長(zhǎng)無(wú)線自組網(wǎng)絡(luò)的壽命。用Ei表示節(jié)點(diǎn)vi的最大能量，用Ei′表示當(dāng)前節(jié)點(diǎn)vi的剩余能量，則參數(shù)λen=Ei′/Ei衡量節(jié)點(diǎn)vi能量剩余性能。節(jié)點(diǎn)能量剩余參數(shù)λen越大說(shuō)明節(jié)點(diǎn)vi的適應(yīng)度函數(shù)值J(fi(t))越大，對(duì)熒光素值Li(t)增量的貢獻(xiàn)越大。

②節(jié)點(diǎn)擁塞程度參數(shù)λco節(jié)點(diǎn)MAC層接口隊(duì)列緩存情況一定程度上反映了節(jié)點(diǎn)的擁塞程度。這里將節(jié)點(diǎn)vi的MAC層接口隊(duì)列緩存容量用Vi表示，MAC層接口隊(duì)列緩存分組數(shù)用Vi′表示。則節(jié)點(diǎn)擁塞程度參數(shù)λco=Vi′/Vi表示節(jié)點(diǎn)vi當(dāng)前的擁塞程度。若節(jié)點(diǎn)擁塞程度參數(shù)λco超出一定的閾值，表明節(jié)點(diǎn)vi陷入擁塞狀態(tài)，數(shù)據(jù)處理能力下降，對(duì)后續(xù)數(shù)據(jù)包進(jìn)行丟棄。節(jié)點(diǎn)擁塞程度參數(shù)值λco越大，說(shuō)明節(jié)點(diǎn)vi的適應(yīng)度函數(shù)值J[fi(t)]越小，對(duì)熒光素值Li(t)增量的貢獻(xiàn)越小。

③節(jié)點(diǎn)的移動(dòng)速度λsp無(wú)線自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)受節(jié)點(diǎn)移動(dòng)速度的影響，節(jié)點(diǎn)移動(dòng)速度越快，拓?fù)浣Y(jié)構(gòu)變化越快，路由更新越快，源節(jié)點(diǎn)發(fā)起路由發(fā)現(xiàn)頻率加快。因此，節(jié)點(diǎn)移動(dòng)速度λsp越大，說(shuō)明節(jié)點(diǎn)vi的適應(yīng)度函數(shù)值J[fi(t)]越小，對(duì)熒光素值Li(t)增量的貢獻(xiàn)越小。

2.2 路由發(fā)現(xiàn)

基于螢火蟲(chóng)優(yōu)化算法的路由發(fā)現(xiàn)過(guò)程如下：

①當(dāng)源節(jié)點(diǎn)vh要向目的節(jié)點(diǎn)vd發(fā)送數(shù)據(jù)時(shí)，節(jié)點(diǎn)vh先查看本地路由表是否有到達(dá)節(jié)點(diǎn)vd的路由，若有則發(fā)起路由路徑，路由發(fā)現(xiàn)算法終止。若沒(méi)有執(zhí)行第2步；

②源節(jié)點(diǎn)vh會(huì)向每個(gè)鄰居節(jié)點(diǎn)發(fā)送搜索螢火蟲(chóng)Fe。每個(gè)搜索螢火蟲(chóng)Fe都有分組編號(hào)Seq，并且源節(jié)點(diǎn)vh將到達(dá)目的節(jié)點(diǎn)vd過(guò)程中經(jīng)歷的所有節(jié)點(diǎn)信息保存到自身數(shù)據(jù)棧data中；

③中間節(jié)點(diǎn)vi′收到來(lái)搜索螢火蟲(chóng)Fe后，根據(jù)Fe數(shù)據(jù)棧的節(jié)點(diǎn)信息中有無(wú)當(dāng)前節(jié)點(diǎn)vi′，判斷是否出現(xiàn)環(huán)路，若是丟棄Fe；

④根據(jù)分組編號(hào)Seq判斷Fe是否為來(lái)自不同路徑的重復(fù)分組，若是則丟棄；

⑤查看當(dāng)前節(jié)點(diǎn)vi′的路由表是否有到達(dá)目的節(jié)點(diǎn)vd的路由，若沒(méi)有就對(duì)搜索螢火蟲(chóng)Fe進(jìn)行廣播；若有就執(zhí)行下一步；

⑥若當(dāng)前節(jié)點(diǎn)vi′路由表中有到目的節(jié)點(diǎn)vd的路由，則搜索螢火蟲(chóng)Fe利用路由表項(xiàng)中熒光素概率Pij(t)根據(jù)式（8）選擇下一跳節(jié)點(diǎn)vj；

⑦搜索螢火蟲(chóng)Fe移動(dòng)到節(jié)點(diǎn)vj后，對(duì)Fe數(shù)據(jù)棧data中所有節(jié)點(diǎn)駐留螢火蟲(chóng)的熒光素值按式（12）更新，對(duì)vj的其他鄰居節(jié)點(diǎn)的駐留螢火蟲(chóng)熒光素值按公式（13）進(jìn)行更新，并對(duì)vj的路由表進(jìn)行更新；

⑧以此類推，直至到達(dá)目的節(jié)點(diǎn)vd，搜索螢火蟲(chóng)Fe實(shí)效，并在目的節(jié)點(diǎn)vd創(chuàng)建回溯螢火蟲(chóng)Fr，F(xiàn)r根據(jù)搜索螢火蟲(chóng)Fe中的路徑信息反方向追溯到源節(jié)點(diǎn)vh；

⑨回溯螢火蟲(chóng)Fr到達(dá)源節(jié)點(diǎn)vh后實(shí)效，源節(jié)點(diǎn)vh到目的節(jié)點(diǎn)vd的路由建立。

式（8）中：φ為隨機(jī)數(shù)且φ∈[0,1]，φ0為系統(tǒng)定義常數(shù)且φ0∈[0,1]同時(shí)P(φ≤φ0)?P(φ＞φ0)。也就是說(shuō)在大多數(shù)情況下搜索螢火蟲(chóng)Fe會(huì)向熒光素值高的鄰居節(jié)點(diǎn)駐留螢火蟲(chóng)Rj移動(dòng)，極個(gè)別情況下搜索螢火蟲(chóng)Fe會(huì)隨機(jī)選擇下一跳節(jié)點(diǎn)，以避免陷入局部最優(yōu)解。若vj的路由表中沒(méi)有到目的節(jié)點(diǎn)vd的路由表項(xiàng)，節(jié)點(diǎn)vj會(huì)廣播搜索螢火蟲(chóng)Fe。但次數(shù)不超過(guò)3次。

在式（7）中，J[fi(t+1)]為節(jié)點(diǎn)vi的適應(yīng)度函數(shù)值，也可看為節(jié)點(diǎn)vi在t+1時(shí)的熒光素值增量，則有：

式中：ΔM為熒光素增量常量：

式中：ηen+ηco=1，σ、δ和θ均為不小于1的調(diào)整參數(shù)，通過(guò)三個(gè)參數(shù)調(diào)整可改變節(jié)點(diǎn)能量、節(jié)點(diǎn)擁塞程度及節(jié)點(diǎn)的移動(dòng)速度對(duì)路由選擇的影響，從而對(duì)路由進(jìn)行優(yōu)化。將式（10）和式（11）代入式（7）可得：

搜索螢火蟲(chóng)Fe移動(dòng)到下一跳節(jié)點(diǎn)vj后，對(duì)Fe數(shù)據(jù)棧data中所有節(jié)點(diǎn)駐留螢火蟲(chóng)的熒光素值按式（12）進(jìn)行更新，對(duì)vj其他鄰居節(jié)點(diǎn)駐留螢火蟲(chóng)的熒光素值按式（13）進(jìn)行更新：

搜索螢火蟲(chóng)Fe由節(jié)點(diǎn)vi轉(zhuǎn)移到下一跳節(jié)點(diǎn)vj后，數(shù)據(jù)棧data中路徑節(jié)點(diǎn)為data.node={v1,v2,v3,..., vn,vi}，更新vj路由表中通過(guò)vi到達(dá)v1,v2,v3,...,vn節(jié)點(diǎn)的Pij(t),j∈data.node-{vi}。

到達(dá)目的節(jié)點(diǎn)vd后創(chuàng)建回溯螢火蟲(chóng)Fr。Fr根據(jù)搜索螢火蟲(chóng)Fe中data.node的內(nèi)容，以相反的方向追溯到源節(jié)點(diǎn)vh。當(dāng)回溯螢火蟲(chóng)Fr通過(guò)vj移動(dòng)到節(jié)點(diǎn)vi后，同樣以式（12）和式（13）對(duì)節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)駐留螢火蟲(chóng)熒光素值進(jìn)行更新，并對(duì)vi的路由表進(jìn)行更新。回溯螢火蟲(chóng)Fr到達(dá)vi后經(jīng)過(guò)的路徑為Fr.node={vj,...vn,v2,v1}，更新vi路由表中通過(guò)vj到達(dá)vi,...vn,v2,v1節(jié)點(diǎn)的Pji(t),i∈Fr.node-{vj}。

2.3 路由維護(hù)

無(wú)線自組網(wǎng)節(jié)點(diǎn)vi上Ri每隔時(shí)間周期T向鄰居節(jié)點(diǎn)發(fā)送Hello數(shù)據(jù)包來(lái)維護(hù)路由的連通性。若鄰居節(jié)點(diǎn)的駐留螢火蟲(chóng)Rj在時(shí)間周期內(nèi)收到Ri的Hello數(shù)據(jù)包，則Rj認(rèn)為vi是vj的鄰居節(jié)點(diǎn)，將該節(jié)點(diǎn)的信息添加到Rj鄰居節(jié)點(diǎn)信息表及路由表中。若在時(shí)間周期內(nèi)沒(méi)有收到Hello數(shù)據(jù)包，則認(rèn)為vi不是vj的鄰居節(jié)點(diǎn)，Rj會(huì)將節(jié)點(diǎn)vi的信息從vj的鄰居節(jié)點(diǎn)信息表中刪除并更新路由表，將vj路由表中下一跳節(jié)點(diǎn)為vi的相關(guān)路由表項(xiàng)刪除。

在源節(jié)點(diǎn)vh向目的節(jié)點(diǎn)vd傳輸信息的過(guò)程中，若中間結(jié)點(diǎn)vi上駐留螢火蟲(chóng)Ri發(fā)現(xiàn)由于自身的移動(dòng)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化而出現(xiàn)網(wǎng)絡(luò)路由鏈接斷裂，無(wú)法按照原有的路由轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，則Ri會(huì)向原有路由的上游節(jié)點(diǎn)發(fā)送路由錯(cuò)誤信息RERR。當(dāng)鄰居節(jié)點(diǎn)vj上的駐留螢火蟲(chóng)Rj收到Ri發(fā)送的RERR數(shù)據(jù)包時(shí)，vj節(jié)點(diǎn)即刪除vi節(jié)點(diǎn)所對(duì)應(yīng)的鄰居節(jié)點(diǎn)表項(xiàng)和路由表項(xiàng)，并在vj路由表中查找是否有到vd的冗余路由。若有則按式（8）選擇下一跳節(jié)點(diǎn)并按式（12）和式（13）對(duì)vj路由表進(jìn)行更新；若不存在，則vj上的駐留螢火蟲(chóng)Rj繼續(xù)向vj上游節(jié)點(diǎn)發(fā)送路由錯(cuò)誤信息RERR，直到找到可用路由。若源節(jié)點(diǎn)vh上的搜索螢火蟲(chóng)Fe收到路由錯(cuò)誤信息RERR，則重新進(jìn)行路由發(fā)現(xiàn)。

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證本文所提出的基于螢火蟲(chóng)優(yōu)化的無(wú)線自組網(wǎng)絡(luò)路由協(xié)議的性能的性能，將本文路由協(xié)議與 AODV［25］（Ad hoc On-demand Distance Vector Routing）及基于蟻群優(yōu)化的路由算法AntRouting［26］在NS2模擬平臺(tái)上進(jìn)行仿真，通過(guò)設(shè)置兩個(gè)場(chǎng)景對(duì)以上三個(gè)路由協(xié)議從數(shù)據(jù)包分組傳送率、端到端時(shí)延及網(wǎng)絡(luò)生存時(shí)間等三個(gè)方面評(píng)價(jià)進(jìn)行性能分析。

仿真場(chǎng)景1：網(wǎng)絡(luò)節(jié)點(diǎn)傳輸半徑為300 m，并且60個(gè)移動(dòng)節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m的區(qū)域內(nèi)，節(jié)點(diǎn)移動(dòng)模型采用自組網(wǎng)Random Waypoint模型，自組網(wǎng)絡(luò)的物理層選用Two-raygroundreflection無(wú)線傳輸模型，MAC層采用IEEE802.11協(xié)議的DCF模式，鏈路帶寬為2 Mbit/s。移動(dòng)節(jié)點(diǎn)的速度均勻分布0～30 m/s間。采用512 byte的定長(zhǎng)數(shù)據(jù)包進(jìn)行仿真通信，隨機(jī)選擇25個(gè)CBR（Constant Bit-Rate）信源，每個(gè)CBR發(fā)包速率為1packet/s，通過(guò)改變移動(dòng)節(jié)點(diǎn)停頓時(shí)間來(lái)仿真不同的自組網(wǎng)絡(luò)移動(dòng)性，仿真時(shí)間統(tǒng)一設(shè)置為400 s。

仿真場(chǎng)景2：其他參數(shù)與仿真場(chǎng)景一相同，移動(dòng)節(jié)點(diǎn)的停頓時(shí)間為50 s，將CBR發(fā)包速率從1 packet/s逐步增加為5 packet/s，模擬不同的網(wǎng)絡(luò)負(fù)載。

這里設(shè)置無(wú)線自組網(wǎng)絡(luò)中節(jié)點(diǎn)的最大能量值為100 J100J。根據(jù)文獻(xiàn)［27］對(duì)IEEE802.11b協(xié)議接口功耗的研究，本文僅考慮自組網(wǎng)中節(jié)點(diǎn)發(fā)送和接收數(shù)據(jù)包時(shí)能量消耗，節(jié)點(diǎn)的發(fā)送數(shù)據(jù)包消耗的能量為1.3 W，接收數(shù)據(jù)包消耗的能量為0.9 W。經(jīng)過(guò)多次實(shí)驗(yàn)本文各參數(shù)取值如下：α=1,β=2,η=0.5,?=0.3, φ0=0.8,ΔM=10,σ=3,δ=θ=1,ηen=0.4,ηco=0.6。

場(chǎng)景1的仿真結(jié)果如圖1所示。

從圖1的結(jié)果可以看出，隨著節(jié)點(diǎn)停頓時(shí)間的增加，三種路由協(xié)議端到端的延時(shí)越來(lái)越小，但本文算法較明顯優(yōu)于其他兩種路由算法；數(shù)據(jù)分組傳送率隨著節(jié)點(diǎn)停頓時(shí)間的增加呈現(xiàn)遞增的態(tài)勢(shì)，網(wǎng)絡(luò)生存時(shí)間隨著節(jié)點(diǎn)停頓時(shí)間的增加，其他兩種路由算法呈小幅降低的趨勢(shì)，而本文路由協(xié)議下的網(wǎng)絡(luò)生存時(shí)間有小幅平穩(wěn)上升的趨勢(shì)。這是由于隨著節(jié)點(diǎn)停頓時(shí)間的增加，節(jié)點(diǎn)的移動(dòng)性降低，從而使網(wǎng)絡(luò)拓?fù)渥兓瘻p緩，路由的重建及數(shù)據(jù)分組重傳的次數(shù)明顯降低，從而使端到端時(shí)延減少，數(shù)據(jù)分組傳送率升高，網(wǎng)絡(luò)生存時(shí)間進(jìn)一步延長(zhǎng)。但當(dāng)節(jié)點(diǎn)移動(dòng)性發(fā)生變化時(shí)，本文路由協(xié)議和文獻(xiàn)［26］路由協(xié)議比AODV路由算法有更好的性能。這是因?yàn)楸疚穆酚蓞f(xié)議和文獻(xiàn)［26］路由協(xié)議的節(jié)點(diǎn)路由表維護(hù)多條路徑信息，當(dāng)某條路徑失效時(shí)，可以選擇其他的替代路徑，避免了頻繁的路由發(fā)現(xiàn)。而但是本文路由協(xié)議考慮到節(jié)點(diǎn)的移動(dòng)速度、擁塞程度、能量對(duì)于熒光素變化的影響，使得搜索螢火蟲(chóng)Fe總向移動(dòng)速度慢、擁塞程度低、能量較高及距離近的節(jié)點(diǎn)移動(dòng)，所以本文路由協(xié)議受到網(wǎng)絡(luò)拓?fù)渥兓挠绊懽钚?，較文獻(xiàn)［26］路由協(xié)議更能適應(yīng)自組網(wǎng)絡(luò)的動(dòng)態(tài)變化。

圖1 場(chǎng)景一的仿真結(jié)果對(duì)比

從圖2可以看出，隨著CBR信源發(fā)包速率的逐步增加，三種路由協(xié)議端到端延時(shí)逐步增大，分組數(shù)據(jù)包傳送比率下降，網(wǎng)絡(luò)生存時(shí)間也隨之降低，這是由于CBR信源發(fā)包速率的增大，導(dǎo)致網(wǎng)絡(luò)負(fù)載隨之增大造成的。相比其他兩種路由協(xié)議，本文所改進(jìn)的路由算法獲得了更好的性能。這是因?yàn)楸疚乃倪M(jìn)的路由協(xié)議和文獻(xiàn)［26］的路由協(xié)議都采取了主動(dòng)路由維護(hù)機(jī)制，即在路由發(fā)現(xiàn)階段，目的節(jié)點(diǎn)會(huì)向源節(jié)點(diǎn)發(fā)送信息以對(duì)路由信息進(jìn)行確認(rèn)及維護(hù)，保證了節(jié)點(diǎn)所存儲(chǔ)路由表能夠更及時(shí)更新，因而兩在網(wǎng)絡(luò)負(fù)載增大的情況下均優(yōu)于AODV協(xié)議。而本文所改進(jìn)的路由協(xié)議在路由發(fā)現(xiàn)及維護(hù)階段，總是尋求移動(dòng)速度慢、擁塞程度低、能量較高、距離較近的路由，因此本文所改進(jìn)的路由協(xié)議性能更穩(wěn)定，更能適應(yīng)網(wǎng)絡(luò)負(fù)載的變化，比文獻(xiàn)［26］的路由協(xié)議有更好的靈活性。

圖2 場(chǎng)景二的仿真結(jié)果對(duì)比

4 結(jié)論

本文提出了一種基于螢火蟲(chóng)群優(yōu)化的Ad Hoc網(wǎng)絡(luò)路由協(xié)議，協(xié)議用螢火蟲(chóng)優(yōu)化算法的熒光素強(qiáng)度的更新規(guī)則與無(wú)線自組網(wǎng)絡(luò)中的節(jié)點(diǎn)移動(dòng)速度、擁塞程度、節(jié)點(diǎn)剩余能量及節(jié)點(diǎn)間的距離等因素相互映射，通過(guò)駐留螢火蟲(chóng)、搜索螢火蟲(chóng)及回溯螢火蟲(chóng)進(jìn)行按需路由的優(yōu)化選擇，無(wú)須額外傳送大量的控制分組，即可實(shí)現(xiàn)無(wú)線自組網(wǎng)絡(luò)的穩(wěn)定。每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)維護(hù)多條雙向冗余路徑，提高了路由協(xié)議的自適應(yīng)性及可靠性。仿真實(shí)驗(yàn)結(jié)果表明，在不同移動(dòng)性和網(wǎng)絡(luò)負(fù)載下，本文所提出的路由協(xié)議在端到端延時(shí)、數(shù)據(jù)分組傳輸率和網(wǎng)絡(luò)生存時(shí)間等3個(gè)方面較其他兩種路由算法有更高的穩(wěn)定性和適應(yīng)性。α,β,η,?,φ0,ΔM,σ,δ,θ,ηen,ηco等參數(shù)因子的選取過(guò)于簡(jiǎn)單，下一步需要對(duì)各參數(shù)取值進(jìn)行深入的理論研究，確定參數(shù)因子對(duì)本文路由協(xié)議性能的影響，以進(jìn)一步對(duì)本文所提出的路由協(xié)議進(jìn)行優(yōu)化。

［1］宋軍全，周凱，華驚宇.基于蟻群算法的無(wú)線自組網(wǎng)絡(luò)能量控制路由研究［J］.傳感技術(shù)學(xué)報(bào)，2012，25（12）：1722-1725.

［2］Johnson D B，Maltz D A，Broch J.DSR：The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc.Ad Hoc Networking［M］.Boston，MA.USA：Addison-Wesley，2001：139-172.

［3］Perkins C E，Bhagwat P.Highly Dynamic Destination-Sequenced Distance-Vector Routing（DSDV）for Mobile Computers［C］//Proceedings of the Conference on Communications，Architectures，Protocols and Applications（SIGCOMM 1994）.London，England，UK，1994.234-244.

［4］藺紹良，龍海南.Ad Hoc網(wǎng)絡(luò)路由協(xié)議綜述［J］.電子設(shè)計(jì)工程，2013，21（9）：141-144.

［5］周德榮.基于蟻群算法改進(jìn)的AODV路由協(xié)議研究［J］.西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，39（11）：75-80.

［6］王鈺，田杰，徐磊.一種基于負(fù)載均衡的移動(dòng)Ad Hoc網(wǎng)絡(luò)AODV協(xié)議改進(jìn)［J］.電信科學(xué)，2011，27（11）：123-127.

［7］Younes M，Khodja E，Kherfane R L.Multi-Objective Economic Emission Dispatch Solution Using Hybrid FFA（Firefly Algorithm）and Considering Wind Power Penetration［J］.Energy，2014，67：596-606.

［8］Tuba M，Bacanin N.Artificial Bee Colony Algorithm Hybridized with Firefly Algorithm for Cardinality Constrained Mean-Variance Portfolio Selection Problem［J］.Applied Mathematics&Information Sciences，2014，8（6）：2831-2844.

［9］Grewal N S，Rattan M，Patterh M S.A Linear Antenna Array Failure Correction with Null Steering Using Firefly Algorithm［J］.Defence Science Journal，2014，64（2）：136-142.

［10］Rahmani A，MirHassani S A.A Hybrid Firefly-Genetic Algorithm for the Capacitated Facility Location Problem［J］.Information Sciences，2014，283：70-78.

［11］Baghlani A，Makiabadi M H，Rahnema H.A New Accelerated Firefly Algorithm for Size Optimization of Truss Structures［J］.Scientia Iranica，2013，20（6）：1612-1625.

［12］Hassanzadeh T，Kanan H R.Fuzzy Fa：A Modified Firefly Algorithm［J］.Applied Artificial Intelligence，2014，28（1）：47-65.

［13］Bidar M，Kanan H R.Jumper Firefly Algorithm［J］.Proceedings of the 3rd International Conference on Computer and Knowledge Engineering（Iccke 2013），2013：267-27.

［14］Tian Y F，Gao W M，Yan S.An Improved Inertia Weight Firefly Optimization Algorithm and Application［J］.2012 International Conference on Control Engineering and Communication Technology（Iccect 2012），2012：64-68.

［15］Chandrasekaran K，Simon S E.Network and Reliability Constrained Unit Commitment Problem Using Binary Real Coded Firefly Algorithm［J］.International Journal of Electrical Power&Energy Systems，2012，43（1）：921-930.

［16］Manju A，Nigam M J.Firefly Algorithm with Fireflies having Quantum Behavior［J］.2012 International Conference on Radar，Communication and Computing（Icrcc），2012：117-119.

［17］Yang X，Hosseini S，Gandomi A.Firefly Algorithm for Solving Non-Convex Economic Dispatch Problems with Value Loading Effect［J］.Applied Soft Computing，2012，12（3）：1180-1186.

［18］劉長(zhǎng)平，葉春明.一種新穎的仿生群智能優(yōu)化算法：螢火蟲(chóng)算法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3295-3297.

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

［20］周少瓊，徐祎，姜麗，等.蟻群優(yōu)化算法在Ad Hoc網(wǎng)絡(luò)路由中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2011，31（2）：159-165.

［21］劉洲洲，王福豹，張克旺.基于改進(jìn)螢火蟲(chóng)優(yōu)化算法的WSN覆蓋優(yōu)化分析［J］.傳感技術(shù)學(xué)報(bào)，2013，26（5）：675-677.

［22］朱文超，許德章.一種基于人工螢火蟲(chóng)群優(yōu)化的改進(jìn)粒子濾波算法［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（10）：2920-2925.

［23］李詠梅，周永權(quán)，韋軍.用于函數(shù)優(yōu)化的層次結(jié)構(gòu)螢火蟲(chóng)群算法［J］.應(yīng)用科學(xué)學(xué)報(bào)，2012，30（4）：391-396.

［24］張軍麗，周永權(quán).一種用Powell方法局部?jī)?yōu)化的人工螢火蟲(chóng)算法［J］.模式識(shí)別與人工智能，2011，24（5）：680-685.

［25］Perkins C，Belding-Royer E，Das S.RFC 3561，Ad Hoc on-Demand Distance Vector（AODV）Routing［S］.2003.

［26］李波波，龍昭華.基于蟻群優(yōu)化的Ad Hoc網(wǎng)絡(luò)QoS路由［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2016，37（1）：12-17.

［27］Feeney L M.Investigating the Energy Consumption of an IEEE 802.11 Network Interface［C］//Technical Report Sics T.2000.

劉建娟（1978-）女，漢族，博士，副教授，碩士生導(dǎo)師。2007年3月畢業(yè)于南京東南大學(xué)儀器科學(xué)與工程系，獲工學(xué)博士學(xué)位。先后參與總裝型號(hào)項(xiàng)目1項(xiàng)，總裝預(yù)研項(xiàng)目2項(xiàng)，973項(xiàng)目1項(xiàng)；國(guó)家自然科學(xué)基金3項(xiàng)，河南省科技攻關(guān)項(xiàng)目2項(xiàng)，河南省自然科學(xué)基金1項(xiàng)。近年來(lái)，在《航天控制》、《電氣傳動(dòng)》、《傳感技術(shù)學(xué)報(bào)》、《中國(guó)慣性技術(shù)學(xué)報(bào)》、等雜志上發(fā)表學(xué)術(shù)論文20余篇，其中EI檢索3篇，ISTP檢索1篇。主要研究方向：智能控制技術(shù)、多傳感器信息融合技術(shù)、測(cè)控技術(shù)及儀器等方面，liujianjuan1978@sina.com。

Ad Hoc Networks Routing Algorithm Based on Improved Glowworm Swarm Optimization*

LIU Jianjuan*
（College of Electrical Engineering Henan University of Technology，Nanyang He’nan450001，China）

For wireless ad hoc network topology changing，network lifetime is limited and low packet packet transmission efficiency and other issues，we propose a wireless ad hoc network routing algorithm based on the swarm optimization algorithm.The routing algorithm will be based on the fluorescence intensity of the firefly optimization algorithm and wireless ad hoc networks in the node mobility，congestion，node residual energy，the distance between the nodes and other factors to map each other，at the same time improve glowworm swarm optimization algorithm in search of fireflies，reside fireflies and back firefly used to complete the wireless AD hoc network centre found by routing protocol，routing and routing maintenance process，this agreement do not need to send a great deal of control group，the stability of the wireless AD hoc network transmission can be realized.Simulation results show that compared with AODV and AntRouting protocols，the proposed routing algorithm has better performance in end to end delay，packet data transmission rate and network lifetime.

Ad Hoc network；routing method；glowworm swarm optimization；network survivability；node energy consumption

TP393

A

1004-1699（2016）12-1905-07

??6150P；7230

10.3969/j.issn.1004-1699.2016.12.021

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（61304259）；河南省重點(diǎn)科技攻關(guān)項(xiàng)目（122102210044）

2016-07-26修改日期：2016-10-08