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

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

中圖分類號：TP393.01"" 文獻標志碼：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ā)展，人們可以通過已有的移動設(shè)備形成交互式的、參與式的感知網(wǎng)絡(luò)，并將感知任務(wù)發(fā)布給網(wǎng)絡(luò)中的個體或群體來完成，從而幫助專業(yè)人員或公眾收集數(shù)據(jù)、分析信息和共享知識。而任務(wù)分配對數(shù)據(jù)采集的全面性、任務(wù)完成率和數(shù)據(jù)采集質(zhì)量等都具有重要的影響，所以感知任務(wù)的分配問題也成為移動群智感知研究中的關(guān)鍵挑戰(zhàn)之一。

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

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

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

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

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

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

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

1.1 系統(tǒng)建模

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實驗結(jié)果

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

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

1）比較方法

a）隨機分配（random）。此方法可以隨機地分配任務(wù)給每個參與用戶，優(yōu)化目標最大化每個工人的任務(wù)數(shù)。因為工人到達的順序可能會對實驗產(chǎn)生很大的影響，所以可以用隨機順序生產(chǎn)工人，并重復(fù)隨機分配任務(wù)20次，取效用值最大的為最終結(jié)果。

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

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

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

2）評估性能指標

a）整體效用（overall utility）。本文采用文獻[15]計算總體效用。

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

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

3）結(jié)果分析

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

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

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

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

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

5 結(jié)束語

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

參考文獻：

[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]韓俊櫻， 張振宇， 孔德仕. 移動群智感知中面向用戶區(qū)域的分布式多任務(wù)分配方法[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)， 王輝， 等. 邊緣輔助群智感知位置隱私保護多任務(wù)分配機制 [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)效用的移動群智感知多目標任務(wù)分配 [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.