任務(wù)分配與資源分配問題研究的國內(nèi)外文獻綜述隨著社會科技的發(fā)展，人們需要處理的信息量愈發(fā)龐大。傳統(tǒng)的人工匹配方法便變得耗時耗力。在分布式系統(tǒng)中，如何合理進行資源匹配，解決資源利用不夠充分、匹配度不夠高的問題，一直是研究的熱點。合理的任務(wù)分配與資源匹配策略能夠有效提高分布式系統(tǒng)的性能。在考慮擬調(diào)度的任務(wù)數(shù)、任務(wù)所需資源量、可用資源總量及分布情況確定的情況下，針對多個任務(wù)執(zhí)行節(jié)點的合理任務(wù)分配問題，國內(nèi)一般使用基于合同網(wǎng)的任務(wù)分配方法、二分圖最優(yōu)匹配算法和基于匈牙利算法的匹配方法等。合同網(wǎng)算法模仿“管理者-工作者”的市場機制，通過進行多個個體之間的任務(wù)協(xié)商和通信，在個體最優(yōu)的前提下追求全局最優(yōu)或者次優(yōu)，以達到任務(wù)分配的目的。田興鵬等人綜合考慮任務(wù)時延和能耗，提出了一種基于KM（Kuhn-Munkres）算法的分布式無限網(wǎng)絡(luò)中的任務(wù)分配方法，系統(tǒng)中每個節(jié)點可與周圍的節(jié)點通過無線連接組成一個協(xié)作網(wǎng)絡(luò)，共同完成各個節(jié)點產(chǎn)生的任務(wù)。通過利用周圍節(jié)點的空閑資源，來降低所有節(jié)點處理任務(wù)的總時延或總能耗[[]田興鵬,朱曉榮,朱洪波.基于KM算法的分布式無線節(jié)點任務(wù)分配方法[J].北京郵電大學學報,2020,43(06):96-102.]。韓曉陽等人針對虛擬網(wǎng)絡(luò)映射算法存在的資源利用率低、費用高的問題，提出一種基于二分圖最優(yōu)匹配的虛擬網(wǎng)絡(luò)映射算法。此算法將虛擬節(jié)點和物理節(jié)點的映射問題轉(zhuǎn)化為二分圖最優(yōu)匹配模型，并利用KM算法求解二分圖最優(yōu)匹配。不僅保持了較高的映射成功率，同時也提高了長期收益開銷比[[]韓曉陽,孟相如,康巧燕,蘇玉澤.基于二分圖最優(yōu)匹配的虛擬網(wǎng)絡(luò)映射算法[J].系統(tǒng)工程與電子技術(shù),2019,41(12):2891-2898.]。崔麗珍等人針對無線傳感網(wǎng)絡(luò)應(yīng)用中常遇到的覆蓋空洞問題，提出一種基于二分圖最優(yōu)匹配KM算法的空洞修復(fù)策略，利用權(quán)值平衡移動節(jié)點與虛擬節(jié)點的個數(shù)，得到最優(yōu)匹配方案。該策略不僅能夠保證網(wǎng)絡(luò)覆蓋率，同時通過減少修復(fù)節(jié)點的開銷來延長網(wǎng)絡(luò)壽命[[][]田興鵬,朱曉榮,朱洪波.基于KM算法的分布式無線節(jié)點任務(wù)分配方法[J].北京郵電大學學報,2020,43(06):96-102.[]韓曉陽,孟相如,康巧燕,蘇玉澤.基于二分圖最優(yōu)匹配的虛擬網(wǎng)絡(luò)映射算法[J].系統(tǒng)工程與電子技術(shù),2019,41(12):2891-2898.[]崔麗珍,李曉宇,路靜超,史明泉.二分圖最優(yōu)匹配算法的WSN覆蓋空洞修復(fù)策略[J].小型微型計算機系統(tǒng),2018,39(04):820-824.[]魏恩偉,李偉華,張之涵,鄭杰.基于改進匈牙利算法的非侵入式負荷匹配方法[J].電測與儀表,2019,56(22):58-64.陳澤亞等人針對在項目和專家網(wǎng)絡(luò)中都存在的高聚類和小世界現(xiàn)象，量化項目和專家間的關(guān)聯(lián)性，利用二分圖網(wǎng)絡(luò)流模型，組合兩種貪心匹配策略與一種傳統(tǒng)最大流匹配策略，提出一種項目和專家的多重匹配算法。每次匹配時先調(diào)用兩種貪心匹配策略，在極端情況下貪心步驟無法完成匹配時，再調(diào)用最大流多重匹配策略。通過與傳統(tǒng)網(wǎng)絡(luò)流算法的對比實驗，證明了該策略在計算耗時和匹配結(jié)果上的高效性[[][]陳澤亞,王慶,郭靜,陳晰,王晶華.基于二分圖網(wǎng)絡(luò)的項目與專家多重匹配策略[J].小型微型計算機系統(tǒng),2016,37(03):545-550.李炯等人提出一種基于改進進化匈牙利的多目標跟蹤算法。利用廣度優(yōu)先搜索算法劃分二分圖序列，對進化匈牙利算法進行改進，解決了遮擋物跟蹤困難以及距離較近容易誤匹配的問題[[][]李炯,李建市,馮明月,朱愿.基于改進進化匈牙利的多目標跟蹤算法研究[J].軍事交通學院學報,2019,21(06):78-85.張夢穎等人綜合考慮協(xié)商效率和通信頻率，對無人機群協(xié)同實施任務(wù)的分配問題，提出一種改進合同算法，將傳統(tǒng)合同算法改進成招標者參與投標和引入并發(fā)機制。仿真結(jié)果證明改進合同網(wǎng)算法能夠有效提高協(xié)商效率并減少通信頻率。但此種合同改進算法仍未考慮到通信范圍和通信演示的問題[[][]張夢穎,王蒙一,王曉東,宋勛.基于改進合同網(wǎng)的無人機群協(xié)同實時任務(wù)分配問題研究[J].航空兵器,2019,26(04):38-46.Janusz等人提出將匈牙利算法應(yīng)用于求解旅行商問題，并給出了算法在樹中的應(yīng)用實例[[]J.Czopik.AnApplicationoftheHungarianAlgorithmtoSolveTravelingSalesmanProblem[J].AmericanJournalofComputationalMathematics,2019,(9):61-67.]。XiangmingZHENG等人提出一種基于改進KM算法的無人機路徑規(guī)劃策略，作者在搜索空間上建立了三維實時概率圖，用于修改KM算法的權(quán)值，從而優(yōu)化無人機的路徑[[]X.M.Zheng,C.Y.Ma.AnintelligenttargetdetectionmethodofUAVswarmsbasedonimprovedKMalgorithm[J].ChineseJournalofAeronautics,2020.[]J.Czopik.AnApplicationoftheHungarianAlgorithmtoSolveTravelingSalesmanProblem[J].AmericanJournalofComputationalMathematics,2019,(9):61-67.[]X.M.Zheng,C.Y.Ma.AnintelligenttargetdetectionmethodofUAVswarmsbasedonimprovedKMalgorithm[J].ChineseJournalofAeronautics,2020.[]P.A.C.Lopes,S.S.Yadav,A.Ilic,S.K.Patra.FastblockdistributedCUDAimplementationoftheHungarianalgorithm[J].JournalofParallelandDistributedComputing,2019,130(8):50-62.Yin等人考慮不同任務(wù)的執(zhí)行需要不同類型的資源，將網(wǎng)絡(luò)中的節(jié)點進行分簇，提出了一種基于兩階段的應(yīng)用程序分配算法，將任務(wù)依次在集群間和集群內(nèi)進行分配。該算法在能耗和負載均衡方面均具有優(yōu)異的性能，能夠延長網(wǎng)絡(luò)的存活時間[[]YinXiang,ZhangKaiquan,LiBin,etal.Ataskallocationstrategyforcomplexapplicationsinheterogeneouscluster-basedwirelesssensornetworks[J].InternationalJournalofDistributedSensorNetworks,2018,14(8):.]。Pu等人提出一種完全分布式的自組織網(wǎng)絡(luò)中的任務(wù)分配方法，由于自組織網(wǎng)絡(luò)中是無中心控制，每個節(jié)點都要與周圍的節(jié)點頻繁的交換信息，所以通信能耗較大[[[]YinXiang,ZhangKaiquan,LiBin,etal.Ataskallocationstrategyforcomplexapplicationsinheterogeneouscluster-basedwirelesssensornetworks[J].InternationalJournalofDistributedSensorNetworks,2018,14(8):.[]PuLingjun,ChenXu,MaoGuoqiang,etal.Anenergy-efficientanddeadline-awarehybridedgecomputingframeworkforvehicularcrowdsensingapplications[J].IEEEInternetofThingsJournal,2019,6(1):84-99.匈牙利算法的核心是使用深度優(yōu)先遍歷的辦法找到一條增廣路徑。KM算法中使用匈牙利算法進行輔助運算，并且通過控制可行頂標的策略來達到完美匹配。KM算法相對于匈牙利算法，考慮到頂點之間并不相同，對頂點增加了權(quán)重，是匈牙利算法的改進。匈牙利算法用于解決二分圖的最大匹配問題，KM算法一般用于解決帶權(quán)二分圖的最優(yōu)完備匹配問題。改進合同網(wǎng)算法針對傳統(tǒng)合同網(wǎng)算法的任務(wù)分配不合理、資源利用率低的問題，將算法改進成招標者參與投標且引入并發(fā)機制，不僅提高了協(xié)商效率，且有效減少通信頻率，滿足