[發明專利]基于鯨魚算法的組播路由優化方法及其在Spark平臺上的應用

有效

• 申請號: 201711006269.0
• 申請日: 2017-10-25
• 公開（公告）號: CN107911300B
• 公開（公告）日: 2020-10-13
• 發明（設計）人: 邢煥來;周芯宇;楊慧;李可;葉佳
• 申請（專利權）人: 西南交通大學
• 主分類號: H04L12/753
• 分類號: H04L12/753;H04L12/761;H04L12/721;H04L12/751
• 代理公司: 成都宏順專利代理事務所(普通合伙) 51227
• 代理人: 李順德

本發明公開了一種基于鯨魚算法的組播路由優化方法，本發明針對具體的組播路由優化問題，在鯨魚算法上作出進一步改進以適應對組播路由優化問題的解決，本發明通過位置信息的二進制編碼把優化連續問題的鯨魚算法映射到離散的搜索空間，并在位置更新策略中引入了個體交叉、變異、味道濃度等其他算法的思想，使其更適合解決組播路由問題，由此簡化了組播路由優化過程，加快了收斂速度。本發明還公開了一種基于鯨魚算法的組播路由優化方法在Spark平臺上的應用，由此使得上述基于鯨魚算法的組播路由優化方法在Spark平臺上實現了并行化，大大加快了算法的執行速度。

技術領域

本發明涉及計算機網絡技術領域，具體而言，涉及一種基于鯨魚算法的組播路由優化方法及其在Spark平臺上的應用。

背景技術

現今高速發展的互聯網領域，各種新奇的互聯網應用層出不窮，如在線媒體、遠程會議、網絡游戲等。這些互聯應用大部分都需要較高的網絡資源、較短的響應時間，其發送方發出的數據具有大量的重復性。傳統的”一對一”傳輸無法滿足網絡應用的實時性、高帶寬等需求，組播技術的出現很好的解決了這方面的問題。組播的主要特征是，服務的發送方和多個接收方構建一個組播樹，發送發只需要發送一份數據包，組播樹的各個分支節點復制數據包并轉發到相應的接收方節點即可，有效的節省了網絡資源并提高了帶寬利用率。如何高效的尋找到一個有效的組播樹，是組播路由優化問題的關鍵。

在現今網絡規模越來越龐大、復雜的情況下，傳統的組播樹尋優算法已不再適用，元啟發式智能算法的出現使得組播路由優化問題的研究得到了突破。遺傳算法(簡稱GA)是智能算法領域比較成熟、應用最廣泛的算法，它可以在有限的時間內找到一個可行解，并隨著算法的不斷迭代計算，找到更優的解。然而，GA的算子較多，選擇、交叉、變異等操作過程較為復雜，收斂速度慢。

鯨魚算法(簡稱WOA)是2016年由澳大利亞的Seyedali Mirjalili等人提出的一種新的群智能優化算法。該算法模仿座頭鯨的狩獵行為，操作簡單，參數少，每一次的迭代中計算量少，運行速度快，全局尋優能力強。但是直接使用上述鯨魚算法還不能很好的解決組播路由優化問題。

發明內容

本發明的主要目的在于提供基于鯨魚算法的組播路由優化方法，以解決現有技術組播路由優化過程復雜，收斂速度較慢的問題。

本發明基于鯨魚算法的組播路由優化方法，1.基于鯨魚算法的組播路由優化方法，將通信子網模擬成一個無向的帶權連通圖G＝(V,E)，V＝{v₁,v₂,...,v_N}表示節點集合，E＝{e₁,e₂,...,e_M}表示連接節點之間的邊集合，N與M分別表示節點和邊的個數，S∈V是組播源節點，是組播目的節點集合，K表示目的節點個數，對每條邊e∈E，定義cost(e)為邊e的開銷，即邊e上的權值，以源節點S為根節點，包含所有目的節點集D的一棵樹T＝{V_T,E_T}，T即為組播樹，其中V_T是T中所有節點的集合，E_T是T中所有邊的集合，組播樹T是G的一個子圖，其步驟包括：

(1)輸入拓撲G＝(V,E)的節點信息和邊信息，構建網絡拓撲，輸入組播源節點S和組播目的節點集D＝{d₁,d₂,...,d_k}；

(2)初始化鯨魚種群，并在鯨魚種群中初始化各個鯨魚個體，鯨魚種群規模初始化為M，初始化鯨魚種群W＝{w₁,w₂,...,w_M}，生成的每個鯨魚個體的個體屬性包括位置和適應度值，初始化最大迭代次數MAX_T，當前迭代次數t＝1，初始化全局最優鯨魚個體gbest，令其適應度值為最大適應度MAX_FITNESS；