移動(dòng)AdHoc網(wǎng)絡(luò)基于蟻群需求的分群路由算法研究

劉軍華，蔡衛(wèi)紅，雷超陽(yáng)

(湖南郵電職業(yè)技術(shù)學(xué)院，長(zhǎng)沙 410015)

移動(dòng)AdHoc網(wǎng)絡(luò)基于蟻群需求的分群路由算法研究

劉軍華，蔡衛(wèi)紅，雷超陽(yáng)

(湖南郵電職業(yè)技術(shù)學(xué)院，長(zhǎng)沙 410015)

針對(duì)移動(dòng)Ad Hoc網(wǎng)絡(luò)因受帶寬和電量等因素影響而造成封包遺失機(jī)率較高的現(xiàn)象，提出了一種移動(dòng)Ad Hoc網(wǎng)絡(luò)基于螞蟻算法的需求式群集路由算法．該路由算法利用弱連接支配集群概念，從每個(gè)群集廣播給其它群集節(jié)點(diǎn)，算法中網(wǎng)絡(luò)上的狀態(tài)信息通過(guò)前行的螞蟻獲得，回退的螞蟻采用偽隨機(jī)比例選擇策略并根據(jù)節(jié)點(diǎn)剩余電量、網(wǎng)絡(luò)平均剩余電量以及路徑平均剩余電量來(lái)評(píng)估從源節(jié)點(diǎn)到目的地節(jié)點(diǎn)的最佳路徑．仿真結(jié)果表明：隨著網(wǎng)絡(luò)信息流量的增加，AOCR路由算法在封包抵達(dá)率、延遲時(shí)間均比AODV和AntSence算法有較大改善，因此，基于蟻群需求的群集路由算法在網(wǎng)絡(luò)效能上比基于距離矢量路由AODV算法及傳統(tǒng)的蟻群路由算法效率更高．

移動(dòng)網(wǎng)絡(luò)；Ad Hoc網(wǎng)絡(luò)；分群；路由算法

Ad Hoc網(wǎng)絡(luò)是一種當(dāng)通信終端附近無(wú)BS時(shí)也能借由其它通信設(shè)備橋梁來(lái)進(jìn)行信息的傳送，間接地將信息傳送給接收裝置的一種網(wǎng)絡(luò)環(huán)境[1].Ad Hoc網(wǎng)絡(luò)因?yàn)椴恍枰揽烤W(wǎng)絡(luò)基礎(chǔ)架構(gòu)及無(wú)中心管理特性，其應(yīng)用環(huán)境可不受 BS的限制，從而可應(yīng)用于無(wú)法建立 BS通信的環(huán)境，如深山、海底、戰(zhàn)場(chǎng)等特殊區(qū)域通信環(huán)境[2]．移動(dòng)Ad Hoc網(wǎng)絡(luò)就屬于這種可不受通信基礎(chǔ)環(huán)境相關(guān)因素影響的無(wú)基礎(chǔ)網(wǎng)絡(luò)架構(gòu)，因受限于有限的帶寬、電量等影響，其網(wǎng)絡(luò)信息的傳送無(wú)固定的路徑，因此封包的遺失機(jī)率較高．Ad Hoc網(wǎng)絡(luò)如何能跟隨網(wǎng)絡(luò)的變化快速找出一條傳輸路徑非常重要．

1 相關(guān)路由算法

1.1 AntSense蟻群路由算法

圖1 蟻群路由算法示意圖

蟻群路由算法是一種啟發(fā)式算法，常用來(lái)解決組合最佳化問(wèn)題．其原理是模擬蟻群尋找食物的行為來(lái)在網(wǎng)絡(luò)上尋找最佳路由[3]．如圖 1所示，圖中有兩個(gè)螞蟻分別從較短路徑A及較長(zhǎng)路徑B走過(guò)并放置費(fèi)洛蒙以備食物尋找，通過(guò)短路徑A的螞蟻會(huì)先找到食物并沿原路返回，并繼續(xù)留下費(fèi)洛蒙來(lái)增加路徑A的費(fèi)洛蒙濃度，因路徑A的費(fèi)洛蒙濃度比路徑B高，因此走路徑B的螞蟻會(huì)有較大概率被費(fèi)洛蒙濃度高的A路徑所吸引而走路徑A返回去并也沿路留下費(fèi)洛蒙，如此周而復(fù)始，路徑 B會(huì)因越來(lái)越少螞蟻?zhàn)哌^(guò)而逐漸消失，而路徑A會(huì)因越來(lái)越多的螞蟻?zhàn)哌^(guò)而逐漸形成主要的路徑，即找到了1條最佳(短)路徑．Ad Hoc網(wǎng)絡(luò)依據(jù)其原理來(lái)決定從來(lái)源節(jié)點(diǎn)到目的地節(jié)點(diǎn)的最短路由，但其路由算法最優(yōu)路徑上信息素積累不夠迅速，且局部最優(yōu)容易造成網(wǎng)路擁塞．

1.2 AODV路由算法

AODV(Ad Hoc On-demand Distance Vector)路由算法是一種無(wú)線Ad Hoc基于距離矢量算法的反應(yīng)式路由算法．節(jié)點(diǎn)只有向目的節(jié)點(diǎn)發(fā)送封包時(shí)，源節(jié)點(diǎn)才會(huì)在網(wǎng)絡(luò)中發(fā)送控制封包發(fā)起路由查找過(guò)程，也就是只有當(dāng)某節(jié)點(diǎn)有連接建立需求時(shí)，才廣播1個(gè)連接建立的請(qǐng)求[4]．其它收到連接請(qǐng)求的AODV節(jié)點(diǎn)馬上轉(zhuǎn)發(fā)這個(gè)請(qǐng)求消息，并記錄源節(jié)點(diǎn)以及回到源節(jié)點(diǎn)的臨時(shí)路由，直到某個(gè)收到連接請(qǐng)求的節(jié)點(diǎn)知道到達(dá)目的節(jié)點(diǎn)的路由時(shí)，就把這個(gè)路由信息按照先前記錄的回到源節(jié)點(diǎn)的臨時(shí)路由發(fā)回源節(jié)點(diǎn)，源節(jié)點(diǎn)就開(kāi)始使用這個(gè)具有最短路徑的路由，當(dāng)鏈路斷掉時(shí)，錯(cuò)誤的信息被回傳至源節(jié)點(diǎn)，源節(jié)點(diǎn)再重新發(fā)起路由查找．該算法高效、擴(kuò)展性能良好，但因其路徑選擇僅以最短路徑及最快響應(yīng)為準(zhǔn)則，不考慮節(jié)點(diǎn)能量狀態(tài)及負(fù)載等情況，故其選擇的路徑非最優(yōu)，在高負(fù)載及高移動(dòng)速率下性能下降快，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變后，鏈路修復(fù)性能差，數(shù)據(jù)傳輸延遲大，路由重建時(shí)間長(zhǎng)．

2 AOCR路由算法

AOCR(Ad Hoc On-demand Clustering Routing)算法是一種以蟻群算法為基礎(chǔ)的需求式群集路由算法，是主動(dòng)式群集分配與被動(dòng)式群集間溝通的混合式路由算法[5-6]．當(dāng)有節(jié)點(diǎn)需傳送信息包時(shí)，它會(huì)先檢查路由表中是否有路徑可達(dá)到目的地節(jié)點(diǎn)，如沒(méi)有就進(jìn)入路徑搜尋階段，并發(fā)送Forward-Ant，當(dāng)1個(gè)節(jié)點(diǎn)收到Forward-Ant時(shí)首先會(huì)檢查是否有重復(fù)收到同樣編號(hào)的封包，若有即棄掉這個(gè)封包，反之，則進(jìn)入下一階段[7]．

為計(jì)算出螞蟻封包所要放置的費(fèi)洛蒙值，首先需要計(jì)算出路徑的健康值，其計(jì)算公式為

前1個(gè)節(jié)點(diǎn)i到現(xiàn)在節(jié)點(diǎn)j的路徑健康值Gij是前1個(gè)節(jié)點(diǎn)i所計(jì)算出的路徑健康值的和，cP表示現(xiàn)節(jié)點(diǎn)j接收封包需消耗的功率值，而Mij表示對(duì)現(xiàn)節(jié)點(diǎn)j所測(cè)量到的剩余電量合并得到的電量測(cè)量值，其計(jì)算公式為

式中Ej表示節(jié)點(diǎn)j的剩余電量，Ejmin表示是Forward-Ant從來(lái)源節(jié)點(diǎn)走到節(jié)點(diǎn)j的這段路上所記錄到的最小節(jié)點(diǎn)剩余電量，其計(jì)算公式為

測(cè)量完路徑健康值之后，節(jié)點(diǎn)會(huì)根據(jù)公式(6)更新費(fèi)洛蒙表里的費(fèi)洛蒙值，

式中ρ表示費(fèi)洛蒙蒸發(fā)率，△τij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j所需更新的費(fèi)洛蒙值，將其有的費(fèi)洛蒙值τij乘上(1-ρ)成為蒸發(fā)過(guò)后的費(fèi)洛蒙值后再加上欲增加的費(fèi)洛蒙值即為節(jié)點(diǎn)i到節(jié)點(diǎn)j的新費(fèi)洛蒙值，欲增加的費(fèi)洛蒙值計(jì)算公式為

式(5)可知電量的測(cè)量值與路徑健康值成反比，因此需將路徑健康值取倒數(shù)才符合螞蟻算法中剩余電量越多費(fèi)洛蒙值會(huì)越多，而費(fèi)洛蒙值越多則可吸引越多的螞蟻?zhàn)哌@條路以達(dá)到最佳化．

更新完費(fèi)洛蒙表后，接著節(jié)點(diǎn)將檢查是否已抵達(dá)目的地節(jié)點(diǎn)，如是則發(fā)送Backward-Ant至源節(jié)點(diǎn)，反之則根據(jù)此節(jié)點(diǎn)是否cluster-head來(lái)決定是要轉(zhuǎn)傳給該群集的 cluster-head還是廣播Forward-Ant給其它的cluster-head．

當(dāng)目的地節(jié)點(diǎn)收到Forward-Ant封包后，會(huì)把Forward-Ant封包刪除并產(chǎn)生一個(gè) Backward-Ant封包，按圖1流程來(lái)發(fā)送與接收Backward-Ant封包，收到Backward-Ant封包的節(jié)點(diǎn)會(huì)先更新其路由表，接著判斷是否回到源節(jié)點(diǎn)，若沒(méi)有則繼續(xù)轉(zhuǎn)傳 Backward-Ant出去，在發(fā)送 Backward-Ant封包之前，將根據(jù)偽隨機(jī)比例選擇策略來(lái)判斷下一個(gè)節(jié)點(diǎn)，其判斷方法如式(8)所示．

式中Pj表示0~1之間的一個(gè)隨機(jī)數(shù)，P0表示0~1之間的常數(shù)，當(dāng)Pj小于P0時(shí)直接在節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)當(dāng)中選擇出費(fèi)洛蒙值最大的節(jié)點(diǎn)j作為下一個(gè)跳點(diǎn)．如果Pj大于P0的話則根據(jù)

的機(jī)率決定出下一個(gè)跳點(diǎn)，式中Pis表示節(jié)點(diǎn)i會(huì)選出下一個(gè)跳點(diǎn)S的機(jī)率．其原理類(lèi)似如一個(gè)俄羅斯轉(zhuǎn)盤(pán)，轉(zhuǎn)盤(pán)每一個(gè)區(qū)域的大小取決于費(fèi)洛蒙值的大小，值越大的節(jié)點(diǎn)就越有機(jī)率會(huì)被選中．每個(gè)收到Backward-Ant封包的節(jié)點(diǎn)都會(huì)按此策略直到Backward-Ant封包抵達(dá)源節(jié)點(diǎn)為止，一旦源節(jié)點(diǎn)收到Backward-Ant封包并更新路由表后，網(wǎng)絡(luò)路徑探索即完成了．

3 模擬仿真

3.1 模擬仿真參數(shù)設(shè)置

為對(duì)以上3種路由算法各主要性能作比較，搭建移動(dòng)AdHoc網(wǎng)絡(luò)的MATLAB仿真環(huán)境，對(duì)網(wǎng)路各主要參數(shù)的設(shè)置情況見(jiàn)表1．

表1 模擬環(huán)境參數(shù)設(shè)置

3.2 仿真結(jié)果

根據(jù)前面仿真參數(shù)設(shè)置，模擬AODV算法、螞蟻算法AntSense及本文所提出的AOCR算法，在不同信息流量的情況下觀察并比較它們封包達(dá)到率、網(wǎng)絡(luò)實(shí)際資料吞吐量、平均點(diǎn)對(duì)點(diǎn)延遲．

3.2.1 AODV、AntSence及AOCR算法封包抵達(dá)率比較

圖2的模擬結(jié)果顯示 AODV、AntSence及AOCR的PDR都會(huì)隨著信息流量的增加而降低，這是因?yàn)榫W(wǎng)絡(luò)變得越來(lái)越擁塞所致．但AntSence算法最為明顯，這是因?yàn)锳ntSence算法持續(xù)不斷地發(fā)送螞蟻封包，且以隨機(jī)的方式選取一個(gè)方向去尋找路徑．而AOCR算法因?yàn)閃CDS網(wǎng)絡(luò)架構(gòu)能夠有效率地傳送封包，使得其PDR即使在信息流量增大的情況下也不會(huì)下降很多，而AODV在整體性能上與AOCR相差并不多，但因其僅僅

圖2 動(dòng)態(tài)網(wǎng)絡(luò)下AODV、AntSence及AOCR算法封包抵達(dá)率比較圖

考慮最短路徑而沒(méi)有建立任何架構(gòu)，因此當(dāng)信息流量變大時(shí)有時(shí)其PDR甚至?xí)陀贏OCR．

3.2.2 AODV、AntSence及AOCR算法網(wǎng)絡(luò)實(shí)際信息吞吐量比較

圖3的模擬結(jié)果顯示AODV與AOCR兩種算法的實(shí)際信息吞吐量都會(huì)隨著信息流量的增加而增加，但AntSence算法的實(shí)際信息吞吐量當(dāng)信息流量增加到50 packets/s后即開(kāi)始下降．

圖3 動(dòng)態(tài)網(wǎng)絡(luò)下AODV、AntSence及AOCR算法網(wǎng)絡(luò)實(shí)際信息吞吐量比較圖

這是因AOCR與AODV兩種算法的目的地節(jié)點(diǎn)實(shí)際收到的信息封包都可隨著信息流量增加而增加，而 AntSence算法當(dāng)信息流量超過(guò) 50 packets/s后對(duì)持續(xù)送螞蟻封包負(fù)擔(dān)過(guò)重，使得網(wǎng)絡(luò)擁塞過(guò)重，最終導(dǎo)致達(dá)到目的地節(jié)點(diǎn)的信息封包反而減少．

3.3.3 AODV、AntSence及AOCR算法平均點(diǎn)對(duì)點(diǎn)延遲比較

當(dāng)網(wǎng)絡(luò)上的封包流量越來(lái)越多時(shí)會(huì)容易造成網(wǎng)絡(luò)的擁塞，進(jìn)而使得封包抵達(dá)目的地節(jié)點(diǎn)的時(shí)間變長(zhǎng)．從圖4模擬結(jié)果可知AOCR算法有著最小延遲時(shí)間．

圖4 動(dòng)態(tài)網(wǎng)絡(luò)下AODV、AntSence及AOCR算法平均點(diǎn)對(duì)點(diǎn)延遲比較圖

這是因?yàn)?AOCR算法能在事先建立好的WCDS架構(gòu)讓封包能快速且有效地傳送到目的地節(jié)點(diǎn)．且 AntSence有著最大的延遲時(shí)間，因?yàn)锳ntSence持續(xù)不斷地發(fā)送螞蟻封包尋找目的地節(jié)點(diǎn)，從而導(dǎo)致網(wǎng)絡(luò)擁塞的情況發(fā)生，尤其是當(dāng)信息流量為50 packets/s時(shí)，延遲時(shí)間上升的情況特別明顯．

4 總結(jié)

本文提出的AOCR算法基于區(qū)域分配演算法WCDS群架構(gòu)思想,使得封包相當(dāng)于在網(wǎng)絡(luò)上的cluster-head之間做溝通而非網(wǎng)絡(luò)上的每個(gè)節(jié)點(diǎn)，能有效率地尋找一條適當(dāng)?shù)穆窂降诌_(dá)目的地節(jié)點(diǎn)，因此能夠迅速地將封包傳送到網(wǎng)絡(luò)的每個(gè)角落．從模擬結(jié)果可知，無(wú)論是封包抵達(dá)率、信息吞吐量，還是點(diǎn)對(duì)點(diǎn)延遲時(shí)間，AOCR算法都比基于距離矢量路由算法及傳統(tǒng)的蟻群路由算法效率更高，可讓整個(gè)網(wǎng)絡(luò)的效能獲得較大的改善．

[1]黃浩軍, 尹浩, 陳和平, 等．無(wú)線Ad Hoc網(wǎng)絡(luò)能量感知地理路由協(xié)議研究進(jìn)展[J]. 軟件學(xué)報(bào), 2014, 25(5): 1061-1084.

[2]薛亮, 關(guān)新平, 袁亞洲. 無(wú)線傳感器網(wǎng)絡(luò)中事件驅(qū)動(dòng)的能量均衡多流聚合路由算法[J]. 控制與決策, 2012, 27(2): 227-231.

[3]胡青松, 吳立新, 張申, 等. 協(xié)作WSN路由算法的能耗及其影響因素研究[J]. 華中科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 2013, 41(2):81-85.

[4]張志協(xié), 曹陽(yáng). 基于改進(jìn)型蟻群算法的最優(yōu)路徑問(wèn)題求解[J].計(jì)算機(jī)系統(tǒng)應(yīng)用, 2012, 21(10): 76-80.

[5]夏亞梅, 程渤, 陳俊亮, 等. 基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(2): 270-281.

[6]戴天虹, 李昊. 基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)路由的優(yōu)化[J]. 計(jì)算機(jī)測(cè)量與控制, 2016, 24(2): 321-324

[7]周治辰, 費(fèi)樹(shù)岷. 基于退火蟻群混合算法的裁剪分配優(yōu)化系統(tǒng)的研究[J]. 工業(yè)控制計(jì)算機(jī), 2014, 27(11): 39-41.

(責(zé)任編校：蔣冬初)

Research of Clustering Routing Arithmetic Based on Ant Colony Demand for Mobile AdHoc Network

LIU Jun-hua,CAI Wei-hong,LEI Chao-yang
(Hunan Post and Telecommunication Vocational College, Changsha, Hunan 410015, China)

For mobile Ad Hoc networks due to affected by factors such as bandwidth and power phenomenon of packet loss probability higher, a mobile Ad Hoc network demand type clustering routing algorithm based on ant algorithm is proposed. The routing algorithm uses weak links to dominate the cluster concept, from each cluster broadcast to other cluster nodes, the state information of the network access arithmetic through the forward ants, regression of ants using pseudo random proportional selection strategy according to the residual energy and network average residual energy and average residual energy to evaluate from the path the best path to the source node to the destination node. The simulation results show: With the increase of network traffic, the AOCR routing algorithm in packet arrival rate, delay time than AODV and AntSence algorithm are greatly improved, so the cluster routing algorithm in the network performance requirements of ant colony based on distance vector routing AODV algorithm and the traditional ant colony routing algorithm based on higher efficiency.

mobile network; Ad Hoc network; clustering; routing arithmetic

TP393

A

10.3969/j.issn.1672-7304.2017.02.0013

1672–7304(2017)02–0059–04

2017-02-20

湖南省教育科學(xué)規(guī)劃課題(XJK013CZY055)；湖南省教育廳科研項(xiàng)目(14C0834)

劉軍華(1979-)，男，湖南衡陽(yáng)人，副教授，碩士，主要從事移動(dòng)互聯(lián)網(wǎng)應(yīng)用技術(shù)和軟件工程研究，E-mail: 38474478@qq.com．