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