[發明專利]一種基于改進布谷鳥搜索算法的微云部署方法

有效

• 申請號: 202010773132.3
• 申請日: 2020-08-04
• 公開（公告）號: CN111885493B
• 公開（公告）日: 2022-03-29
• 發明（設計）人: 金小敏;高楓;王忠民;陳彥萍
• 申請（專利權）人: 西安郵電大學
• 主分類號: H04W4/02
• 分類號: H04W4/02;H04W4/70;H04W16/18;H04W72/04
• 代理公司: 西安鼎邁知識產權代理事務所(普通合伙) 61263
• 代理人: 李振瑞

本發明提出了一種基于改進布谷鳥搜索算法的微云部署方法。本發明將離散布谷鳥搜索算法和離散差分進化算法結合在一起，第一階段通過離散化萊維飛行機制，更新布谷鳥種群的位置，將每一代種群中適應度最大的個體直接保留到下一代，避免它被交叉和變異操作破壞；第二階段對布谷鳥算法的丟巢操作通過離散差分進化算法進行改進，對第一階段的少部分劣質基因個體通過變異算子與優秀的父基因進行進化，在保留種群的優秀基因和增加種群的多樣性的同時，加快算法的收斂速度。本發明算法求解速度快，能在大規模的物聯網網絡中使用較短時間求解出微云的永久部署位置，大幅度提高微云在網絡中的使用效率和生存壽命。

技術領域

本發明屬于云計算技術領域，涉及邊緣計算與優化領域，具體設計一種基于改進布谷鳥搜索算法的微云部署方法。本發明可短時求解出微云的永久部署位置，大幅度提高微云在網絡中的使用效率和生存壽命。

背景技術

隨著萬物互聯時代的到來，線性增長的集中式云計算能力無法匹配網絡邊緣側終端所產生數據的指數增長需求，網絡邊緣側的海量數據訪問云計算中心將消耗非常大的網絡帶寬和產生很高的網絡延遲。面對該困境，邊緣計算作為一種新的計算模式，架起了物聯網設備和數據中心之間的橋梁，數據在產生的源頭附近得到及時有效地處理。

微云框架作為一種新興的技術，正被應用到物聯網網絡中。微云是一個具有相對豐富計算資源的可信主機，并且部署在網絡的邊緣側，與互聯網相連接，可以被移動設備訪問并提供一定的服務。在物聯網網絡中使用微云作為無線局域網的補充，可以緩解大量邊緣數據上傳至云中心造成的網絡擁塞，能夠滿足邊緣設備的關鍵響應要求。由于云服務器與邊緣設備兩者之間距離遙遠，邊緣移動設備訪問遠程云中心會產生無法預測的通信時延。為了降低移動設備和云之間的通信時延并改善用戶體驗，將微云部署在與移動設備更近的地方是至關重要的。因此在物聯網網絡中的大量無線接入點中確定數量有限的微云的位置就變的十分重要。

在邊緣計算系統中，微云的部署是將有限個微云合理的部署在大規模物聯網網絡中的無線接入點上，以實現對邊緣數據的及時處理。微云的最優部署是實現最優時延，保障服務質量，保證負載均衡以及節省經濟成本。最優時延是指在時延閾值的約束下，從邊緣計算系統中第一個任務開始，直到最后一個任務執行完成過程中所消耗的時間，時間跨度越短則證明部署策略越好。時延是微云部署中重要且常見的目標，因此，實現最優時延是用戶和微云提供商的共同目標。

在微云部署過程中，最優部署方案的求解過程是一個離散型組合優化問題。近年來，眾多科研人員提出或優化了很多算法應用于選址部署問題，例如遺傳算法、模擬退火算法、粒子群優化算法等。雖然這些算法可以從某個角度提高選址部署的效率，但是也存在其局限性，例如在平衡局部搜索與全局搜索上效果不理想，很難跳出局部最優解。相比較而言，布谷鳥搜索算法是一種比較新穎的群體智能啟發式優化算法，其利用Lévy(萊維)飛行機制隨機游動和偏好隨機游動來共同構成平衡算法的局部搜索和全局搜索的步驟，能通過Lévy飛行機制較快地尋找到全局最優解。國內外的一些學者在此方面做了一些研究，但鮮有將此算法應用于求解部署微云的位置上。此外，現有的布谷鳥搜索算法在進化后期容易造成早熟，易陷入局部最優解，導致無法搜索出全局最優解，也限制了其在微云部署的應用。

發明內容

為有效解決布谷鳥搜索算法自身的技術缺陷，克服微云部署面臨的技術問題，本發明提供一種基于改進布谷鳥搜索算法的微云部署方法。本發明涉及的方法，其技術思路是將布谷鳥搜索算法和差分進化算法結合起來，首先利用離散化Lévy飛行機制的隨機游動和偏好隨機游動來共同構成平衡算法的局部搜索和全局搜索，然后結合二進制差分進化算法改進布谷鳥搜索算法的丟巢操作。本發明符合進化的思想，保留原有種群的優勢特征，提高了算法的搜索速度和搜索質量。