王新 劉永山 朱代春

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

關鍵詞：蟻群算法；Qos；計算機仿真；網絡教學

中圖分類號：TP391 文獻標識碼：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

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

1 Qos網絡路由模型的建立

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

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

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

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

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

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

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

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

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

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

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

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

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

1.5 負載均衡的Qos路由

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

2 計算機仿真與結果分析

計算機仿真實驗采用文獻[8]中使用的網絡拓撲結構。

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

3 結論

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

參考文獻：

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

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

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

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

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

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

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

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

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