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

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

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

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

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

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

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

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

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

1.1 AntSense蟻群路由算法

圖1 蟻群路由算法示意圖

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

1.2 AODV路由算法

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

2 AOCR路由算法

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

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

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

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

測量完路徑健康值之后，節(jié)點(diǎn)會根據(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ā)過后的費(fèi)洛蒙值后再加上欲增加的費(fèi)洛蒙值即為節(jié)點(diǎn)i到節(jié)點(diǎn)j的新費(fèi)洛蒙值，欲增加的費(fèi)洛蒙值計算公式為

式(5)可知電量的測量值與路徑健康值成反比，因此需將路徑健康值取倒數(shù)才符合螞蟻算法中剩余電量越多費(fèi)洛蒙值會越多，而費(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來決定是要轉(zhuǎn)傳給該群集的 cluster-head還是廣播Forward-Ant給其它的cluster-head．

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

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

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

3 模擬仿真

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

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

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

3.2 仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

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

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

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

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

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

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

[7]周治辰, 費(fèi)樹岷. 基于退火蟻群混合算法的裁剪分配優(yōu)化系統(tǒng)的研究[J]. 工業(yè)控制計算機(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)；湖南省教育廳科研項目(14C0834)

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