基于蟻群算法的Qos技術(shù)在網(wǎng)絡(luò)教學(xué)中的應(yīng)用分析

王新 劉永山 朱代春

摘要：隨著Internet技術(shù)的發(fā)展，網(wǎng)絡(luò)化教學(xué)也逐漸進(jìn)入我們的視野。依托網(wǎng)絡(luò)化教學(xué)平臺，具有實時、同步、異地、交互的特點也越來越受到大家的歡迎。針對在教學(xué)過程中出現(xiàn)的問題，利用蟻群算法的Qos（Quality of Service）技術(shù)解決在視頻播放、視頻下載、交互溝通等過程中出現(xiàn)的延時、延時抖動、丟包率問題，尋求各個節(jié)點之間的合理優(yōu)化的路徑，滿足客戶要求，提高服務(wù)質(zhì)量。通過計算機(jī)仿真解決TSP（Travelling Salesman Problem）問題，在大量實驗結(jié)果中，分析找到滿足約束條件下，從路由源節(jié)點到目標(biāo)節(jié)點之間的最優(yōu)路徑。

關(guān)鍵詞：蟻群算法；Qos；計算機(jī)仿真；網(wǎng)絡(luò)教學(xué)

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）32-0051-03

Abstract： With the development of Internet technology， network teaching has gradually come into our vision. relying on the network teaching platform， has the characteristics of real-time， synchronization， remote， interactive， more and more popular. Aiming at the problems in the teaching process， the Quality of Service （Qos） technology is used to solve the problems such as delay， delay-jitter and packet-loss rate in the process of video playing， video download， interactive communication and so on. Travelling Salesman Problem （TSP） problem is solved by computer simulation. In a large number of experimental results， the optimal path is found to meet the constraints， from which the routing source node to the target node.

Key words： ant colony algorithm；Qos； computer simulation；network teaching

網(wǎng)絡(luò)教學(xué)[1]是從美國推出的“網(wǎng)絡(luò)日”活動而來，主要目的是爭取在2000年，教室和圖書館都可以連接internet，使公眾可以得到技術(shù)文化教育的權(quán)利。目前為止，已形成一個覆蓋全國教育機(jī)構(gòu)的網(wǎng)絡(luò)，將近100多所大學(xué)將利用Internet開展遠(yuǎn)程教育，大約70%的高等院校提供網(wǎng)絡(luò)教育。英國推出“全國學(xué)習(xí)網(wǎng)計劃” 目標(biāo)是2002年所有小學(xué)全部可以上網(wǎng)學(xué)習(xí)。同時制訂了網(wǎng)絡(luò)教育計劃和相關(guān)的實施細(xì)則。遠(yuǎn)程教育將主要依賴Internet，不僅基礎(chǔ)教育，專業(yè)培訓(xùn)也可以在網(wǎng)絡(luò)上實現(xiàn)。國內(nèi)的網(wǎng)絡(luò)教學(xué)首先清華、北郵、湖南大學(xué)、浙大四所大學(xué)開始，到2015年為止，已有90多所大學(xué)有權(quán)進(jìn)行學(xué)歷教學(xué)，實現(xiàn)60個網(wǎng)絡(luò)教學(xué)平臺，尤其最近幾年發(fā)展迅速，可以看出網(wǎng)絡(luò)教學(xué)正被公眾認(rèn)可接受。但是在網(wǎng)絡(luò)教學(xué)中也出現(xiàn)了各種問題，我們主要從網(wǎng)絡(luò)技術(shù)方面分析，提出通過Qos（Quality of Service）技術(shù)找到一條有足夠資源的可行路徑，提高網(wǎng)絡(luò)的利用率，實現(xiàn)可用資源的優(yōu)化。目前的路由采用FCFS協(xié)議，它不能滿足多媒體的數(shù)據(jù)傳輸。研究人員提出了群智能蟻群算法[2]，人工魚群算法[3]，智能水滴算法[4]等解決組合優(yōu)化問題，蟻群算法通過信息素更新規(guī)則解決了求解速度慢、收斂和停滯問題。人工魚群算法不需要特殊信息，收斂速度比較快，適合解決實時性問題。智能水滴算法應(yīng)用還不廣泛，主要用于TSP和無人機(jī)航跡方面。Qos路由分：單播、組播、廣播、選播四種，我們主要研究改進(jìn)的蟻群算法在Qos網(wǎng)絡(luò)路由中的應(yīng)用，并與基本的蟻群算法，人工魚群算法，智能水滴算法做比較。本文提到的數(shù)學(xué)模型以及網(wǎng)絡(luò)圖都是基于單播的理論基礎(chǔ)

1 Qos網(wǎng)絡(luò)路由模型的建立

網(wǎng)絡(luò)路由主要是基于數(shù)據(jù)為中心的路由和基于搜索查詢的路由[5]，我們主要討論數(shù)據(jù)為中心的路由問題。通常情況是一個節(jié)點感應(yīng)到數(shù)據(jù)后，需要向一個或幾個匯聚節(jié)點傳輸，這種數(shù)據(jù)定向的擴(kuò)散過程可以通過蟻群算法模擬。

下面我們給出網(wǎng)絡(luò)模型[G=（V，E）]，[V]是所有節(jié)點的集合，[E]是所有節(jié)點間通信鏈路的集合，我們的目的是找到一條從源點[S∈V]到目標(biāo)節(jié)點[M∈V]的最優(yōu)有效路徑，并且要滿足約束條件（如帶寬、時延、時延抖動、丟包率）。蟻群算法有兩種數(shù)據(jù)傳輸，一種是實時數(shù)據(jù)稱后螞蟻（Backward Ants）負(fù)責(zé)傳輸數(shù)據(jù)；一種是非實時數(shù)據(jù)稱前螞蟻（Forward Ants），負(fù)責(zé)尋路。在某個節(jié)點接收到數(shù)據(jù)后會產(chǎn)生[K]個前螞蟻向相鄰節(jié)點移動，它移動到下一個節(jié)點的概率。

但是蟻群算法在運算過程中有幾個問題需要解決。

1.1 初始條件下節(jié)點尋路問題

初始條件下節(jié)點尋路的選擇概率大體相同，導(dǎo)致前螞蟻尋路時間較長。我們采用基于已知位置的蟻群Qos路由算法來解決初始化問題，從而提高蟻群的收斂速度。

1.2 初始條件下螞蟻數(shù)量問題

針對蟻群算法中初始條件下前螞蟻數(shù)量較少的，導(dǎo)致前期算法收斂性、穩(wěn)定性和尋路質(zhì)量不理想的問題，我們采用提高局部信息素?fù)]發(fā)速度[4]的辦法，將公式3做如下修改。

其中[Di]表示第i只螞蟻找到的路徑時延，如不滿足Qos約束條件則不更新，反之加強(qiáng)。ANTNUM是前螞蟻數(shù)量，[Emin]是最小剩余能量節(jié)點的剩余能量，[E]是初始能量。將前螞蟻的數(shù)量引入到信息素?fù)]發(fā)因子中，目的是通過信息素?fù)]發(fā)速度提高算法的收斂性，引入剩余能量概念到信息素?fù)]發(fā)因子中，可以有效均衡能量消耗。

1.3 當(dāng)鏈路出現(xiàn)擁塞時，采用擁塞規(guī)避原則

擁塞規(guī)避[6]首先要計算數(shù)據(jù)隊列的平均長度。并且根據(jù)上限、下限的閥值來預(yù)判擁塞狀態(tài)，如果將要發(fā)生擁塞，預(yù)判到的節(jié)點馬上向所有經(jīng)過該擁塞鏈路的目標(biāo)節(jié)點發(fā)送擁塞信息，經(jīng)過此路徑的螞蟻重新尋求一條路徑以繞過該節(jié)點，同時更新節(jié)點和鏈路信息，以確保存在一條非擁塞路徑。從而實現(xiàn)流量的分散，緩解擁塞狀態(tài)。當(dāng)擁塞節(jié)點恢復(fù)狀態(tài)，再將路由切回原狀態(tài)。

1.4 信息素更新規(guī)則的調(diào)整

信息素在蟻群算法的非常重要，螞蟻在循環(huán)搜索過程中，在經(jīng)過路徑上留下的信息量的大小是尋求全局最優(yōu)解的關(guān)鍵。針對基本蟻群算法收斂速度慢，容易進(jìn)入局部最優(yōu)的問題，修改了信息素更新規(guī)則。

公式[Q']是常數(shù)，[Lk]是路徑長度，[minlength]是最短的路徑長度，R是參數(shù)。修改的目的是針對不同質(zhì)量的解，它的信息素增量是不同的，優(yōu)解的信息素增量較大，加快收斂速度，從而降低算法的花費。

1.5 負(fù)載均衡的Qos路由

目前，Qos路由算法主要是預(yù)計算和在線計算[7]。預(yù)計算根據(jù)已有的路由表，在請求到達(dá)時快速找到可行路徑，缺點路由表較大，可擴(kuò)展性不強(qiáng)。在線計算是請求到達(dá)時根據(jù)網(wǎng)絡(luò)狀態(tài)計算可行路徑，缺點延遲較高，路由器負(fù)載較大。負(fù)載均衡的Qos路由，目的就是在滿足服務(wù)質(zhì)量的前提下，提高網(wǎng)絡(luò)使用率。我們給出一個既考慮路徑的質(zhì)量還能兼顧網(wǎng)絡(luò)使用率的評估參數(shù)。

2 計算機(jī)仿真與結(jié)果分析

計算機(jī)仿真實驗采用文獻(xiàn)[8]中使用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

運行結(jié)果如表1所示，它們在相同的網(wǎng)絡(luò)結(jié)構(gòu)和約束條件下，都能找到最優(yōu)路徑，解決復(fù)雜的組合優(yōu)化問題。但是從算法的運行時間和尋找最優(yōu)路徑的成功率來看改進(jìn)的蟻群算法運行時間更短，成功率更高，路徑也合理，能夠有效地節(jié)省網(wǎng)絡(luò)資源。主要原因是改進(jìn)初始條件下前螞蟻數(shù)量和尋址概率相同的問題，提高了蟻群算法在前期的收斂速度，同時規(guī)避了圖2中基本蟻群算法在節(jié)點8和節(jié)點15出現(xiàn)擁塞現(xiàn)象，而改進(jìn)的蟻群算法負(fù)載更均衡，使用網(wǎng)絡(luò)資源更合理。

3 結(jié)論

改進(jìn)的蟻群算法有效的解決網(wǎng)絡(luò)路由問題，有很強(qiáng)的尋路能力，負(fù)載更均衡，避免了擁塞狀態(tài)。解決了網(wǎng)絡(luò)教學(xué)中視頻閃斷，傳輸中斷，因帶寬、時延導(dǎo)致的丟包率問題。將本文中討論的網(wǎng)絡(luò)技術(shù)應(yīng)用到網(wǎng)絡(luò)教學(xué)中，可以充分發(fā)揮教學(xué)和網(wǎng)絡(luò)資源結(jié)合的優(yōu)勢，提高公眾學(xué)習(xí)能力。因本文主要針對Qos單播情況下的研究，同時也為其它播放方式的研究提供了一定的基礎(chǔ)。

參考文獻(xiàn)：

[1] 寇媛媛.網(wǎng)絡(luò)教學(xué)平臺的發(fā)展現(xiàn)狀及趨勢[J].電子信息工程，2011（8）：123-125.

[2] 胡瓊瓊.群智能優(yōu)化算法在Qos網(wǎng)絡(luò)路由優(yōu)化中的應(yīng)用[D].陜西師范大學(xué)，2010：35-40.

[3] 魏星，李志遠(yuǎn)，陳艷.基于蟻群和魚群的混合優(yōu)化光網(wǎng)絡(luò)動態(tài)RWA算法[J].光通信技術(shù)，2015（3）：17-19.

[4] 趙莉，丁海軍.智能水滴算法求解TSP問題的研究[J].云南民族大學(xué)學(xué)報，2015.24（1）：62-65.

[5] 胡瓊瓊.群智能優(yōu)化算法在Qos網(wǎng)絡(luò)路由優(yōu)化中的應(yīng)用[D].陜西師范大學(xué)，2010，5：35-40.

[6] 萬博，盧昱.基于改進(jìn)的蟻群算法的擁塞規(guī)避Qos路由算法[J].計算機(jī)工程，2011，37（20）.

[7] 柯宗武.無線多媒體傳感器網(wǎng)絡(luò)QoS路由算法研究[D].武漢理工大學(xué)，2009：52-54.

[8] 古明家，宣士斌.基于自適應(yīng)變異蟻群算法的Qos路由算法[J].計算機(jī)工程，2009，35（23）：209-211.

【通聯(lián)編輯：王力】