移動(dòng)群智感知中基于納什討價(jià)還價(jià)博弈的多任務(wù)分配策略

摘 要：在移動(dòng)群智感知網(wǎng)絡(luò)多個(gè)并發(fā)任務(wù)的情況下，如何根據(jù)用戶資源以及任務(wù)的質(zhì)量需求實(shí)現(xiàn)多任務(wù)的有效分配問題，利用納什議價(jià)解模型在資源分配方面的優(yōu)勢，提出了一種基于納什議價(jià)解的多任務(wù)分配策略。該策略將多個(gè)用戶對多個(gè)任務(wù)根據(jù)不同目標(biāo)以及質(zhì)量需求的選擇問題映射為一個(gè)多方納什議價(jià)博弈模型，并采用空間距離的方法有效求得此多方納什議價(jià)博弈的最優(yōu)解。感知平臺根據(jù)此解對多個(gè)任務(wù)進(jìn)行統(tǒng)一分配，將每個(gè)任務(wù)分配給最適合的用戶去執(zhí)行。該策略可以實(shí)現(xiàn)用戶整體得益的最大化，在保障數(shù)據(jù)質(zhì)量的同時(shí)，減少同一任務(wù)執(zhí)行用戶的數(shù)目，有效降低感知平臺的激勵(lì)成本。實(shí)驗(yàn)結(jié)果表明，所提策略比現(xiàn)有任務(wù)分配策略具有更好的整體效用與任務(wù)質(zhì)量滿意度。

關(guān)鍵詞：移動(dòng)群智感知；納什討價(jià)還價(jià)模型；任務(wù)質(zhì)量；任務(wù)分配；空間距離

中圖分類號：TP393.01"" 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2025）04-030-1191-07

doi： 10.19734/j.issn.1001-3695.2024.07.0319

Multi-task allocation scheme based on Nash bargaining model in mobile crowdsensing network

Li Li1， Zhong Xiaoxiong2

（1.School of Computer Science amp; Software， Shenzhen Institute amp; Information Technology， Shenzhen Guangdong 518172， China; 2. Dept. of New Networks， Peng Cheng Laboratory （PCL）， Shenzhen Guangdong 518055， China）

Abstract：In order to realize the effective multi-task allocation based on user resources and task quality requirements for multiple concurrent tasks of mobile crowdsensing network， this paper exploited the advantage of Nash bargaining model in resource allocation， and proposed a multi-task assignment strategy based on Nash bargaining solution. This strategy mapped multiple users’selection problems of different heterogeneous tasks according to different objectives and quality requirements into a multi-player Nash bargaining game model， and used the space distance method to effectively obtain the optimal solution of this multi-player Nash bargaining game. Based on this solution， the sensing platform uniformly allocated multiple heterogeneous tasks， and assigned each task to the most suitable user. The strategy can maximize the overall profit of the user， reduce the number of users executing the same task while ensuring the quality of the data， and effectively reduce the incentive cost of the sensing platform. The experimental results show that the proposed strategy has better performances than the existing task allocation strategies in terms of overall utility and task quality satisfaction.

Key words：mobile crowdsensing network; Nash bargaining model; task quality; task allocation; space distance

0 引言

隨著感知技術(shù)和傳感器技術(shù)等信息技術(shù)的快速發(fā)展，人們可以通過已有的移動(dòng)設(shè)備形成交互式的、參與式的感知網(wǎng)絡(luò)，并將感知任務(wù)發(fā)布給網(wǎng)絡(luò)中的個(gè)體或群體來完成，從而幫助專業(yè)人員或公眾收集數(shù)據(jù)、分析信息和共享知識。而任務(wù)分配對數(shù)據(jù)采集的全面性、任務(wù)完成率和數(shù)據(jù)采集質(zhì)量等都具有重要的影響，所以感知任務(wù)的分配問題也成為移動(dòng)群智感知研究中的關(guān)鍵挑戰(zhàn)之一。

目前，大多研究工作是針對群智感知中單任務(wù)的分配問題。而在大數(shù)據(jù)時(shí)代，大型的群智感知平臺通常會(huì)有大量并發(fā)出現(xiàn)的感知任務(wù)，針對多個(gè)感知任務(wù)，如何實(shí)現(xiàn)有效的分配，既可以保障任務(wù)的完成質(zhì)量又減少平臺的激勵(lì)成本是亟待解決的問題。因此，設(shè)計(jì)一種高效的群智感知任務(wù)分配策略，是非常必要的。

在移動(dòng)群智感知中，激勵(lì)機(jī)制與任務(wù)分配相輔相成，激勵(lì)是為了保證更好的任務(wù)分配，而合理高效的分配策略可使參與者和平臺各取所得，促進(jìn)用戶參與的積極性。在采取了一定的激勵(lì)措施之后，平臺可以確定參與感知的用戶，而此時(shí)平臺對多個(gè)并發(fā)任務(wù)進(jìn)行有效分配也成為一個(gè)關(guān)鍵的問題。對于感知平臺而言，為了降低系統(tǒng)成本，需要最小化參與者的激勵(lì)成本；而對于參與用戶來說，希望最大化各自的收益，即在任務(wù)數(shù)目一定的情況下，選擇最少的參與者完成任務(wù)。

He等人[1]研究了群智感知中位置獨(dú)立的任務(wù)分配問題，考慮感知任務(wù)的地理特征以及移動(dòng)用戶的時(shí)空移動(dòng)性，并將此問題進(jìn)行數(shù)學(xué)抽象，證明其是一個(gè)NP-hard問題。通過設(shè)計(jì)一個(gè)有效的近似算法LRBA來解決任務(wù)分配問題。文獻(xiàn)[2，3]主要考慮固定預(yù)算下的任務(wù)分配問題。文獻(xiàn)[2]提出了一種任務(wù)分配方法BudgetFix，用于確定相互依賴的微任務(wù)的數(shù)目以及固定預(yù)算下每個(gè)任務(wù)的支付價(jià)格，并且在實(shí)際群智感知平臺Amazon Mechanical Turk 上進(jìn)行了實(shí)驗(yàn)，證明所提算法在支付成本和準(zhǔn)確性方面能取得更好的成果。為了均衡用戶完成感知任務(wù)的移動(dòng)距離以及完成任務(wù)的質(zhì)量，文獻(xiàn)[3]提出了一種QoI （quality of information） 感知的任務(wù)分配策略。該策略利用在線學(xué)習(xí)的方法獲得不同參與者所提供信息的質(zhì)量。Wang等人[4]提出了一種任務(wù)分配方法 CCS-TA。該方法結(jié)合了先進(jìn)的壓縮感知技術(shù)、貝葉斯推理以及主動(dòng)學(xué)習(xí)技術(shù)，能夠動(dòng)態(tài)地選擇最小數(shù)目的子區(qū)域進(jìn)行任務(wù)分配。Xiong等人[5]提出了一種參與者選擇算法，該算法的目的是在激勵(lì)預(yù)算有限的情況下最大化感知任務(wù)的覆蓋質(zhì)量。文獻(xiàn)[6]對文獻(xiàn)[5]做了進(jìn)一步的深入研究，定義了一種新的時(shí)空覆蓋指標(biāo)，并且考慮了能量因素，提出了一種移動(dòng)群智感知任務(wù)分配方案，目標(biāo)是確保在固定預(yù)算的情況下最大化時(shí)空覆蓋，或者保證時(shí)空覆蓋的情況下最小化總預(yù)算。Cheung等人[7]提出了一種異構(gòu)分布式的參與者選擇和任務(wù)分配算法，優(yōu)化目標(biāo)是參與用戶。文獻(xiàn)[8]針對移動(dòng)群智感知多個(gè)任務(wù)發(fā)起者以及任務(wù)參與者都想最大化各自的效用，利用瓦爾拉斯均衡理論，在任務(wù)提供者、感知平臺以及參與用戶三者之間達(dá)到一個(gè)瓦爾拉斯均衡。針對空間眾包平臺，文獻(xiàn)[9]提出了一種在線微任務(wù)分配方法。但這些研究工作考慮的任務(wù)分配不是針對多個(gè)并發(fā)任務(wù)的。

針對多任務(wù)分配問題，考慮到任務(wù)需求者和參與者都具有不斷移動(dòng)性，為了減少任務(wù)的平均完成時(shí)間，Xiao 等人[10]提出了一種離線任務(wù)分配算法（FTA）和一種在線任務(wù)分配算法（NTA），兩種算法都采用貪心任務(wù)分配策略。Song 等人[11]提出了基于多任務(wù)的參與者選擇策略，來選出最小參與用戶子集以滿足當(dāng)前任務(wù)的質(zhì)量要求并且不超過總預(yù)算限制。針對多任務(wù)分配中的兩種特殊情況，即較少參與用戶較多任務(wù)（FPMT），以及較多參與用戶較少任務(wù)（MPFT），Liu等人[12]分別提出了基于最小代價(jià)最大流的優(yōu)化算法（針對FPMT），以及基于多目標(biāo)優(yōu)化理論的算法（針對MPFT）?？紤]到任務(wù)分配中用戶的不誠實(shí)行為會(huì)增加總體的開支，Karger等人[13]給出了一種最優(yōu)預(yù)算的任務(wù)分配方法。針對大數(shù)據(jù)環(huán)境下的空間眾包平臺，Gu等人[14]提出了一種可信任務(wù)分配策略。其可以將受限的空間任務(wù)分配給大量的動(dòng)態(tài)用戶，并且考慮了參與用戶的可信度，但是并未給出如何計(jì)算可信度的方法。Wang 等人[15]研究了質(zhì)量保障的多任務(wù)分配策略，采用貪心方法從所有用戶任務(wù)對中逐漸剔除對總效用影響最小的用戶任務(wù)對，在保障質(zhì)量的同時(shí)可以使得總體效用最大。針對現(xiàn)有的多任務(wù)分配方法大多集中在同構(gòu)任務(wù)上，文獻(xiàn)[16]提出并形式化了移動(dòng)群智感知系統(tǒng)中一個(gè)重要的異構(gòu)多任務(wù)分配問題，在所提優(yōu)化問題上，盡量提高數(shù)據(jù)質(zhì)量和盡量減少總激勵(lì)預(yù)算。在異構(gòu)任務(wù)中通過利用因素之間的隱含時(shí)空相關(guān)性，提出了一種兩階段問題解決方法，可以有效地處理多個(gè)并發(fā)任務(wù)共享資源池。最后，為了提高任務(wù)搜索效率，提出了一種分解組合框架設(shè)計(jì)用于適應(yīng)大規(guī)模問題場景。針對移動(dòng)群智感知中帶有時(shí)間有效性的多任務(wù)分配問題，文獻(xiàn)[17]提出了一個(gè)具有時(shí)間約束的多任務(wù)分配問題，研究了時(shí)間約束對多任務(wù)的影響分配，旨在最大限度地提高平臺的效用，并采用兩個(gè)進(jìn)化算法來解決這個(gè)問題。在基于位置的任務(wù)分配算法中，分配遠(yuǎn)離工人目的地的任務(wù)可能會(huì)造成不便?？s短剩余距離以提高工人的出行便利性，但這可能會(huì)對平臺的實(shí)用性產(chǎn)生負(fù)面影響。為了在這兩個(gè)目標(biāo)之間取得平衡，文獻(xiàn)[18]為它們分配不同的權(quán)重，將它們轉(zhuǎn)換為一個(gè)單目標(biāo)優(yōu)化問題，并采用基于遺傳算法的出行便利自適應(yīng)算法來解決目標(biāo)優(yōu)化問題。針對現(xiàn)有以純粹最大化社會(huì)效用為目標(biāo)的多任務(wù)分配工作可能會(huì)導(dǎo)致這個(gè)問題分配不平衡，可能損害公平性，文獻(xiàn)[19]設(shè)計(jì)激勵(lì)機(jī)制時(shí)引入比例公平，首次提出了一種新的公平意識激勵(lì)機(jī)制，將多任務(wù)分配的交互建模為在群智感知中作為多請求者多工作者的Stackelberg博弈，然后轉(zhuǎn)換公平感知的多任務(wù)分配問題轉(zhuǎn)換為公平意識激勵(lì)機(jī)制設(shè)計(jì)問題，并證明存在一個(gè)Stackelberg平衡。針對目前大多數(shù)研究工作都假設(shè)只有一個(gè)服務(wù)平臺，文獻(xiàn)[20]提出了面向多個(gè)服務(wù)平臺的用戶質(zhì)量感知的多任務(wù)分配算法，建立了多平臺合作任務(wù)質(zhì)量最大化問題的框架并建模為一個(gè)0-1整數(shù)線性規(guī)劃（ILP）問題。它包括兩個(gè)階段：第一階段在平臺之間建立穩(wěn)定的合作關(guān)系，同時(shí)尊重各自的合作意愿，基于此，作者提出了一種跨平臺合作關(guān)系構(gòu)建算法；第二階段主要設(shè)計(jì)在線任務(wù)分配算法。針對現(xiàn)有的研究工作中，由于所選擇的組沒有考慮其存在的時(shí)長因素，相應(yīng)的任務(wù)將被丟棄或以較差的質(zhì)量執(zhí)行問題，文獻(xiàn)[21]提出了面向群體的協(xié)同人群感知三階段方法解決社交移動(dòng)中的多協(xié)作任務(wù)分配問題。這種方法利用社交網(wǎng)絡(luò)中的現(xiàn)實(shí)生活關(guān)系來形成兼容的群體，從而改進(jìn)了任務(wù)通過小組合作實(shí)現(xiàn)覆蓋，同時(shí)實(shí)現(xiàn)良好的任務(wù)合作質(zhì)量。針對用戶可能會(huì)報(bào)告虛假成本以獲得更多利潤的問題，文獻(xiàn)[22]假設(shè)用戶的信息是已知的，將單輪用戶招募問題轉(zhuǎn)換為min-cut問題，并提出了一種基于圖論的算法來尋找近似解。然后，在多輪場景中為了平衡探索和開發(fā)之間的權(quán)衡，他們提出基于組合多臂老虎機(jī)模型的預(yù)算約束下的多輪用戶招募策略和一種基于圖的支付策略，以實(shí)現(xiàn)用戶的真實(shí)性和個(gè)體合理性?，F(xiàn)有針對單個(gè)任務(wù)的群智感知任務(wù)分配方法，難以適用于多任務(wù)實(shí)時(shí)并發(fā)的現(xiàn)實(shí)場景，而且往往需要實(shí)時(shí)獲取用戶位置，不利于保護(hù)參與者隱私。針對上述問題，文獻(xiàn)[23]提出了一種面向用戶區(qū)域的分布式多任務(wù)分配方法。該方法采用貪心啟發(fā)算法與基于空間關(guān)聯(lián)性的Q-learning算法進(jìn)行分簇和構(gòu)成任務(wù)路徑?；诖耍O(shè)計(jì)了基于歷史信譽(yù)記錄的貪心算法，選擇合適的參與者進(jìn)行任務(wù)分配。為了解決群智感知中隱私泄露和多任務(wù)分配的問題，文獻(xiàn)[24]提出了一種邊緣輔助群智感知位置隱私保護(hù)多任務(wù)分配機(jī)制，利用改進(jìn)的模糊聚類算法及同態(tài)加密保障隱私需求?；诖?，作者提出了一種基于蟻群算法多任務(wù)分配優(yōu)化方案，所提機(jī)制在保護(hù)位置隱私的前提下提高了任務(wù)完成率，降低了系統(tǒng)的感知成本和用戶移動(dòng)成本。文獻(xiàn)[25]基于工人信譽(yù)指數(shù)和任務(wù)熟練指數(shù)，設(shè)計(jì)了工人和平臺兩方面的異構(gòu)效用機(jī)制，并提出一種雙種群競爭的多目標(biāo)進(jìn)化算法來獲得最優(yōu)的工人和平臺異構(gòu)效用。該算法首先通過隨機(jī)貪婪初始化種群，然后使用二元競標(biāo)賽算法將種群劃分為勝者種群和敗者種群，并針對每個(gè)種群采用不同的進(jìn)化策略。

對上面關(guān)于群智感知任務(wù)分配方面的研究工作進(jìn)行總結(jié)與分析，可以發(fā)現(xiàn)多任務(wù)分配已取得的一些研究成果，這為以后研究提供了基礎(chǔ)及導(dǎo)向。但這些研究工作仍然存在一些局限，尤其是在多個(gè)并發(fā)異構(gòu)任務(wù)的環(huán)境下，還有許多問題有待于解決，主要體現(xiàn)在：移動(dòng)平臺無法有效利用參與者的資源，可能造成用戶資源浪費(fèi)，并且增加任務(wù)的完成時(shí)間；在提供高質(zhì)量的感知數(shù)據(jù)的同時(shí)，如何減少參與感知用戶的數(shù)目，降低感知平臺的激勵(lì)成本。這些都是多任務(wù)分配中有待解決的主要問題。

為解決上述問題，本文提出了一種基于博弈論的任務(wù)分配策略。該策略利用納什議價(jià)博弈，將群智感知中多任務(wù)分配映射為多個(gè)博弈方對多個(gè)任務(wù)的博弈模型，以實(shí)現(xiàn)多個(gè)任務(wù)在多個(gè)參與用戶之間的有效分配。將任務(wù)分配給最適合的用戶執(zhí)行，在有效降低激勵(lì)成本的同時(shí)可以使得整體效用最大化。

1 系統(tǒng)模型設(shè)計(jì)

1.1 系統(tǒng)建模

在多個(gè)并發(fā)異構(gòu)任務(wù)的環(huán)境下，移動(dòng)平臺無法有效利用參與者的資源，可能造成用戶資源浪費(fèi)，這會(huì)導(dǎo)致增加任務(wù)的完成時(shí)間；在提供高質(zhì)量的感知數(shù)據(jù)的同時(shí)，如何減少參與感知用戶的數(shù)目，降低感知平臺的激勵(lì)成本。首先，構(gòu)建系統(tǒng)模型及給出相關(guān)假設(shè)。假設(shè)以一定的時(shí)間為限制，對該時(shí)間段內(nèi)發(fā)布的任務(wù)視為并發(fā)任務(wù)，用集合T={t1，t2，…，tm}表示在某一時(shí)間段內(nèi)所發(fā)布的所有感知任務(wù)的集合，在這一段時(shí)間內(nèi)參與的用戶，定義為有效參與用戶，用N={1，2，…，n}表示。平臺為了激勵(lì)這些有效用戶順利完成感知任務(wù)，會(huì)根據(jù)所發(fā)布任務(wù)的質(zhì)量要求和用戶完成的難易程度給不同數(shù)目的報(bào)酬，稱為回報(bào)，用集合R={r1，r2，…，rm}表示。

假設(shè)每個(gè)用戶都是理性和誠實(shí)的。每個(gè)用戶如果參與感知任務(wù)，則會(huì)在平臺注冊，并向平臺反饋?zhàn)约核鶕碛械馁Y源情況，比如設(shè)備能量、緩存資源以及所處的位置等信息。系統(tǒng)平臺收到這些信息后對m個(gè)任務(wù)在n 個(gè)用戶之間利用納什議價(jià)解模型進(jìn)行分配。用戶再根據(jù)分配結(jié)果完成相應(yīng)的感知任務(wù)，而感知平臺則會(huì)反饋給用戶一定的報(bào)酬。整體系統(tǒng)模型如圖1所示。最終目標(biāo)是最小化平臺代價(jià)的同時(shí)有效利用參與用戶的資源，使其能為最適合的任務(wù)進(jìn)行服務(wù)。

1.2 多任務(wù)分配的目標(biāo)

1.2.1 影響多任務(wù)分配的因素

多種因素都可以影響到群智感知任務(wù)分配。首先，參與用戶的資源情況，因?yàn)閰⑴c用戶完成感知任務(wù)需要花費(fèi)自己的資源，并且完成不同的任務(wù)所需的資源不盡相同，用戶必須保證有足夠的資源能完成所承擔(dān)的任務(wù)；其次，參與者能提供消息的質(zhì)量也是影響任務(wù)分配的一個(gè)因素；最后，參與用戶與所完成任務(wù)之間的距離也是一個(gè)重要因素，距離越遠(yuǎn)，完成此任務(wù)所花費(fèi)的代價(jià)也就越大。

下面給出用空間距離的方法實(shí)現(xiàn)最優(yōu)任務(wù)分配步驟。

a）參與用戶i 計(jì)算所有任務(wù)的空間距離Di，tj，并將任務(wù)按空間距離從小到大的順序排序，并依次從小到大編號，表示為集合{1，…，m}，此編號只代表用戶對所有任務(wù)空間距離大小的一個(gè)順序，并非實(shí)際任務(wù)編號。

b）根據(jù)此順序用戶i再計(jì)算每個(gè)任務(wù)的效用-空間距離積ωi，tj，并對其進(jìn)行前項(xiàng)加后項(xiàng)的累加，并將此累加和用ak表示，ak=ak－1+ωi，tj，a0=0，k∈{1，…，m}。

c）用戶i 計(jì)算劃分點(diǎn)σi，將滿足條件ak≤σi的k個(gè)任務(wù)劃分給用戶i。

d）每個(gè)用戶重復(fù)計(jì)算上面步驟，最終完成全部任務(wù)的劃分。

e）每個(gè)用戶會(huì)將劃分結(jié)果反饋給感知平臺，感知平臺根據(jù)此結(jié)果將對應(yīng)的任務(wù)分配給相應(yīng)的用戶執(zhí)行，從而實(shí)現(xiàn)多個(gè)任務(wù)在多個(gè)用戶之間的有效分配。

圖3是基于納什議價(jià)博弈的多任務(wù)分配整體流程。由于將納什議價(jià)解的求解轉(zhuǎn)換為上述空間距離的方法，所以所得到的最終劃分結(jié)果即為納什議價(jià)解，也就是使得所有博弈方效用得益乘積最大化時(shí)的解。所提方法可以實(shí)現(xiàn)用戶整體得益最大化，并且將任務(wù)分到最適合的用戶執(zhí)行，間接減少了感知平臺的激勵(lì)成本。

綜上所述，通過上述將多個(gè)任務(wù)的分配問題映射為多方納什議價(jià)博弈模型，并求得最優(yōu)解，可以實(shí)現(xiàn)多個(gè)任務(wù)在多個(gè)用戶之間的有效分配，該方法可以使用戶盡最大能力完成最適合的任務(wù)，從而有效利用用戶資源，并提高用戶所提供數(shù)據(jù)的質(zhì)量，減少平臺的代價(jià)花費(fèi)。

4 仿真實(shí)驗(yàn)結(jié)果

為了評估本文所提多任務(wù)分配策略的性能，對所提策略進(jìn)行了仿真驗(yàn)證。采用公開的真實(shí)數(shù)據(jù)集 Gowalla，它有196 591名用戶在 1 280 956 個(gè)地點(diǎn)登記的6 264 203 次的記錄。實(shí)驗(yàn)軟硬件環(huán)境為 Windows 11、英特爾酷睿Ultra7-155H、內(nèi)存32 GB和編程語言 Python。

由于本文研究多個(gè)并發(fā)任務(wù)的分配，所以實(shí)驗(yàn)設(shè)定在某一特定的時(shí)間內(nèi)（1 h），感知任務(wù)大量并發(fā)出現(xiàn)，任務(wù)數(shù)目選取為200～500，參與感知的用戶數(shù)目選取為50～100，每個(gè)感知任務(wù)的總預(yù)算設(shè)置為75，權(quán)重因子ρ=0.35。

1）比較方法

a）隨機(jī)分配（random）。此方法可以隨機(jī)地分配任務(wù)給每個(gè)參與用戶，優(yōu)化目標(biāo)最大化每個(gè)工人的任務(wù)數(shù)。因?yàn)楣と说竭_(dá)的順序可能會(huì)對實(shí)驗(yàn)產(chǎn)生很大的影響，所以可以用隨機(jī)順序生產(chǎn)工人，并重復(fù)隨機(jī)分配任務(wù)20次，取效用值最大的為最終結(jié)果。

b）單純基于效用上升的貪心任務(wù)分配 （NAIVE-AG）。此方法首先選擇能使總體效用值增值最大的單個(gè)任務(wù)-工作者對，然后，依次按照相同的規(guī)則，選擇另外的任務(wù)-工作者，并結(jié)合第一步已經(jīng)選擇的對能使總體效用增值最大，將其加入到相應(yīng)的任務(wù)-工作者對集合中。重復(fù)用上述步驟，選擇并添加新的任務(wù)-工作者對到集合中，直到每個(gè)用戶被分配的任務(wù)數(shù)量達(dá)到其上限。

c）考慮任務(wù)質(zhì)量的多任務(wù)分配方法 （MTasker） [15]。此方法不同于上面的方法之處，采用基于效用下降的貪心算法，算法首先在所有任務(wù)工作者對的全集中，選擇單任務(wù)-工作者對，使得總效用的下降最小。在采用迭代的貪心過程重復(fù)上述選擇過程，最終實(shí)現(xiàn)多個(gè)任務(wù)的分配。

d）考慮合作能力的多任務(wù)分配方法 （UCB-L） [20]。此方法是面向用戶質(zhì)量感知的多任務(wù)分配算法，建立了基于合作任務(wù)質(zhì)量最大化問題的框架并設(shè)計(jì)在線多任務(wù)分配算法。為了與所提算法對比，采用文章所提的基于UCB-L的多任務(wù)分配算法。

2）評估性能指標(biāo)

a）整體效用（overall utility）。本文采用文獻(xiàn)[15]計(jì)算總體效用。

b）信息質(zhì)量滿意度（satisfaction ratio）。本文定義Stj=∑i∈NSi，tj/n，n∈N為任務(wù)tj的信息質(zhì)量滿意度。

c）任務(wù)預(yù)算公平度。本文用z表示通過tj來計(jì)算任務(wù)預(yù)算公平度。

3）結(jié)果分析

首先，評估了四種多任務(wù)分配策略隨著網(wǎng)絡(luò)中任務(wù)數(shù)目增加的整體效用，在仿真中將用戶數(shù)目固定為70。從圖4可以得知，隨著任務(wù)數(shù)量的增加，所有分配策略的整體效用都下降，這是因?yàn)橘Y源有限，用戶數(shù)目也有限，當(dāng)任務(wù)數(shù)目增多，競爭性更大，所以整體效用會(huì)下降。但是本文所提基于博弈論的分配策略整體效用優(yōu)于其他三種，這是因?yàn)閞andom方法是隨機(jī)選擇任務(wù)并隨機(jī)分配給用戶，NAIVE-AG是采用貪心方法，可以實(shí)現(xiàn)局部當(dāng)前的最優(yōu)，MTasker策略也是采用貪心方法，但是這些方法都沒有綜合考慮多個(gè)影響任務(wù)分配的因素，并且難以實(shí)現(xiàn)系統(tǒng)所有用戶整體效用的最大化。UCB-L策略采用的是基于局部更新的合作任務(wù)分配算法，難以實(shí)現(xiàn)系統(tǒng)所有用戶整體效用的最大化。而本文采用納什議價(jià)解模型，并且考慮了距離、質(zhì)量、資源和回報(bào)等多個(gè)因素，對所有任務(wù)在所有用戶之間根據(jù)它們的適合度進(jìn)行統(tǒng)一分配，所以整體效用相對其他幾種更好。

其次，評估四種多任務(wù)分配策略隨參與用戶數(shù)目增加的整體效用性能變化情況，如圖5所示，任務(wù)數(shù)目固定在200。從圖5可以得知，隨著任務(wù)數(shù)量的增加，所有分配策略的整體效用都增加。這是因?yàn)殡S著參與者數(shù)目增加，更適合執(zhí)行任務(wù)的用戶也隨之增加，所以整體效用都會(huì)增加。但是從圖5可以看出，本文所提任務(wù)分配策略仍然能取得較好的性能，尤其在參與用戶數(shù)目較小的情況下，比其他幾種方法的性能更加優(yōu)越。這是因?yàn)楸疚牟呗岳枚喾郊{什議價(jià)博弈對多任務(wù)進(jìn)行分配，實(shí)現(xiàn)了整體最優(yōu)，可以根據(jù)用戶執(zhí)行適合度，將任務(wù)分配給更適合執(zhí)行的用戶，所以參與用戶數(shù)目小時(shí)，其總體效用性能較其他幾種策略的更好。

接下來，評估任務(wù)預(yù)算的大小對任務(wù)預(yù)算使用的公平度的影響情況。從理論方面，根據(jù)上述定義，本文策略是基于空間距離的納什議價(jià)模型，可以更合理地協(xié)同分配系統(tǒng)中的任務(wù)，可以在確定均衡點(diǎn)（如式（14）所示）時(shí)減少其計(jì)算代價(jià)。同時(shí)，從實(shí)驗(yàn)結(jié)果方面，如圖6所示，本文比較了本文策略與隨機(jī)分配兩種情況。從圖6可以看出，當(dāng)預(yù)算逐漸增大時(shí)，執(zhí)行任務(wù)的用戶數(shù)目也有所增加，因此預(yù)算使用公平度整體處于一種下降的趨勢，但由于隨機(jī)方法選擇的分散度很高，所以隨機(jī)方法的感知任務(wù)預(yù)算使用公平性更低。

最后，評估任務(wù)預(yù)算的變化對感知任務(wù)信息質(zhì)量滿意度的影響情況。從理論方面，根據(jù)上述定義，本文策略是基于空間距離的納什議價(jià)模型，可以更合理地協(xié)同分配系統(tǒng)中的任務(wù)。在進(jìn)行任務(wù)分配時(shí)，對用戶執(zhí)行每個(gè)任務(wù)的質(zhì)量進(jìn)行了嚴(yán)格的約束，并且選擇距離更近、資源更充足的用戶來執(zhí)行任務(wù)，從而也可以更有效地保障用戶所提供信息的質(zhì)量，增加任務(wù)信息的滿意度。另外，實(shí)驗(yàn)結(jié)果如圖7所示，從圖7得知，隨著任務(wù)預(yù)算的增大，本文策略和隨機(jī)分配方法對應(yīng)的信息質(zhì)量滿意度都呈現(xiàn)出平滑增長的趨勢，相對于隨機(jī)分配算法，本文策略表現(xiàn)出更高的任務(wù)信息質(zhì)量滿意度。

綜上，雖然本文策略在感知任務(wù)的預(yù)算使用公平性方面不如隨機(jī)方法，但是在任務(wù)的質(zhì)量滿意度方面明顯高于隨機(jī)方法，這也說明本文策略可以有效地保障任務(wù)的完成質(zhì)量，并且可以在總體效用上取得較好的性能。

5 結(jié)束語

針對群智感知網(wǎng)絡(luò)中多任務(wù)分配問題，本文提出了一種基于納什議價(jià)博弈的多任務(wù)分配策略。在該策略中，首先刻畫了用戶對任務(wù)的執(zhí)行適合度，然后將多任務(wù)分配映射到多方納什議價(jià)博弈模型中，通過證明所構(gòu)建效用空間符合納什議價(jià)博弈效用空間的特性，從而得出所映射的納什議價(jià)博弈存在唯一的最優(yōu)解。并且求出此最優(yōu)解便是一組可以使用戶總體得益最大化的任務(wù)分配方案。之后，采用仿真實(shí)驗(yàn)驗(yàn)證了所提策略的性能，實(shí)驗(yàn)結(jié)果顯示所提策略在整體效用以及任務(wù)質(zhì)量滿意度方面具有更好的性能。本文所提任務(wù)分配策略是將每個(gè)任務(wù)視為一個(gè)相互獨(dú)立的整體，然而隨著移動(dòng)群智感知中任務(wù)數(shù)量和復(fù)雜程度的增加，任務(wù)不再獨(dú)立，多個(gè)任務(wù)之間存在相互依存的關(guān)系。如有時(shí)間先后或執(zhí)行邏輯前后依賴關(guān)系約束的任務(wù)，如何設(shè)計(jì)高效的任務(wù)分配機(jī)制以提升MCS平臺的在線任務(wù)處理能力是未來值得研究的方向。

參考文獻(xiàn)：

[1]

He Shibo， Shin D H， Zhang Junshan， et al. Near-optimal allocation algorithms for location-dependent tasks in crowdsensing [J]. IEEE Trans on Vehicular Technology， 2017， 66（4）： 3392-3405.

[2]Tran-Thanh L， Huynh T D， Rosenfeld A， et al. BudgetFix： budget limited crowdsourcing for interdependent task allocation with quality guarantees [C]// Proc of Adaptive Agents and Multi-Agent Systems. New York： ACM Press， 2014： 477-484.

[3]Zhou Chongyu， Tham C K， Motani M. QOATA： QoI-aware task allocation scheme for mobile crowdsensing under limited budget [C]// Proc of the 10th IEEE International Conference on Intelligent Sensors， Sensor Networks and Information Processing. Piscataway， NJ： IEEE Press， 2015： 1-6.

[4]Wang Leye， Zhang Daqing， Pathak A，et al. CCS-TA： quality-guaranteed online task allocation in compressive crowdsensing [C]// Proc of ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM Press， 2015： 683-694.

[5]Xiong Haoyi， Zhang Daqing， Chen Guanling， et al. CrowdTasker： maximizing coverage quality in Piggyback Crowdsensing under budget constraint [C]// Proc of IEEE International Conference on Pervasive Computing and Communications. Piscataway， NJ： IEEE Press， 2015： 55-62.

[6]Xiong Haoyi， Zhang Daqing， Chen Guanling， et al. iCrowd： near-optimal task allocation for piggyback crowdsensing [J].IEEE Trans on Mobile Computing，" 2016， 15（8）： 2010-2022.

[7]Cheung M H， Southwell R， Hou Fen， et al. Distributed time-sensitive task selection in mobile crowdsensing [C]// Proc of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM Press， 2015： 157-166.

[8]He Shibo， Shin D H， Zhang Junshan， et al. An exchange market approach to mobile crowdsensing： pricing， task allocation， and walrasian equilibrium [J].IEEE Journal on Selected Areas in Communications，" 2017， 35（4）： 921-934.

[9]Tong Yongxin， She Jieying， Ding Bolin， et al. Online mobile micro-task allocation in spatial crowdsourcing [C]// Proc of the 32nd International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2016： 49-60.

[10]Xiao Mingjun， Wu Jie， Huang Liusheng，et al. Multi-task assignment for crowdsensing in mobile social networks [C]// Proc of IEEE Conference on Computer Communications. Piscataway， NJ： IEEE Press， 2015： 2227-2235.

[11]Song Zheng， Liu C H， Wu Jie， et al. QoI-aware multitask-oriented dynamic participant selection with budget constraints [J]. IEEE Trans on Vehicular Technology， 2014， 63（9）： 4618-4632.

[12]Liu Yan， Guo Bin， Wang Yang，et al. TaskMe： multi-task allocation in mobile crowd sensing [C]// Proc of ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM Press， 2016： 403-414.

[13]Karger D R， Oh S， Shah D. Budget-optimal task allocation for reliable crowdsourcing systems [J].Operations Research，" 2014， 62（1）： 1-24.

[14]Gu Liqiu， Wang Kun， Liu Xiulong，et al. A reliable task assignment strategy for spatial crowdsourcing in big data environment [C]// Proc of IEEE International Conference on Communications. Piscataway， NJ： IEEE Press， 2017： 1-6.

[15]Wang Jiangtao， Wang Yasha， Zhang Daqing， et al. Multi-task allocation in mobile crowd sensing with individual task quality assurance [J].IEEE Trans on Mobile Computing，" 2018， 17（9）： 2101-2113.

[16]Wang Liang， Yu Zhiwen， Zhang Daqing，et al. Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation [J].IEEE Trans on Mobile Computing，" 2019， 18（1）： 84-97.

[17]Li Xin， ZhangXinglin. Multi-task allocation under time constraints in mobile crowdsensing [J].IEEE Trans on Mobile Computing，" 2021， 20（4）： 1494-1510.

[18]Zeng Hongjian， Xiong Yonghua， She Jinhua. An evolutionary multi-task assignment method adapting to travel convenience in mobile crowdsensing [J].Journal of Network and Computer Applications，" 2023， 220： 103734.

[19]Lu Jianfeng， Liu Haibo， Jia Riheng，et al. Incentivizing proportional fairness for multi-task allocation in crowdsensing [J]. IEEE Trans on Services Computing， 2024， 17（3）： 990-1000.

[20]Peng Shuo， Zhang Baoxian， Yan Yan， et al. A multiplatform-cooperation based task assignment mechanism for mobile crowdsensing [J].IEEE Internet of Things Journal，" 2023， 10（19）： 16881-16894.

[21]Tan Wenan， Zhao Lu， Li Bo，et al. Multiple cooperative task allocation in group-oriented social mobile crowdsensing [J]. IEEE Trans on Services Computing， 2021， 15（6）： 3387-3401.

[22]Wang Hengzhi， Yang Yongjian， Wang En，et al. Truthful user recruitment for cooperative crowdsensing task： a combinatorial multi-armed bandit approach [J]. IEEE Trans on Mobile Computing， 2023， 22（7）： 4314-4331.

[23]韓俊櫻， 張振宇， 孔德仕. 移動(dòng)群智感知中面向用戶區(qū)域的分布式多任務(wù)分配方法[J]. 計(jì)算機(jī)應(yīng)用， 2020， 40（2）： 358-362. （Han Junying， Zhang Zhenyu， Kong Deshi. Distributed multi-task allocation method for user area in mobile crowd sensing [J].Journal of Computer Applications，" 2020， 40（2）： 358-362.）

[24]敖山， ?，F(xiàn)， 王輝， 等. 邊緣輔助群智感知位置隱私保護(hù)多任務(wù)分配機(jī)制 [J].計(jì)算機(jī)應(yīng)用研究， 2024， 41（4）： 1208-1213. （Ao Shan， Chang Xian， Wang Hui， et al. Edge-assisted crowdsensing location privacy protection multi-task allocation mechanism [J].Application Research of Computers，" 2024， 41（4）： 1208-1213.）

[25]傅彥銘， 陸盛林， 祁康恒， 等. 面向異構(gòu)效用的移動(dòng)群智感知多目標(biāo)任務(wù)分配 [J].計(jì)算機(jī)應(yīng)用研究， 2024， 41（1）： 159-164， 169. （Fu Yanming，" Lu Shenglin， Qi Kangheng， et al. Multi-objective task assignment towards heterogeneous utilities in mobile crowdsensing [J].Application Research of Computers，" 2024， 41（1）： 159-164， 169.）

[26]Nash J F. The bargaining problem [J]. Econometrica， 1950， 18（2）： 155-162.

[27]Peters H J M. Axiomatic bargaining game theory [M]. Dordrecht： Springer Netherlands， 1992.