楊桂松，江文成，何杏宇

1(上海理工大學 光電信息與計算機工程學院，上海 200093)

2(上海理工大學 出版印刷與藝術設計學院，上海 200093)

E-mail：xy_he@usst.edu.cn

1 引 言

近年來，隨著物聯(lián)網(wǎng)應用的需求增強、移動智能終端的快速普及和群智計算模式的出現(xiàn)，一種稱為“移動群智感知”(MCS，Mobile Crowd Sensing)的特殊眾包形式已成為一種新型感知模式[1].移動群智感知實際上是將群智計算模式從互聯(lián)網(wǎng)環(huán)境推廣到物聯(lián)網(wǎng)環(huán)境.在移動群智感知中，一組攜帶智能手機的移動用戶可以完成一些例如空氣質量[2]，移動廣告[3]，噪聲檢測[4]等單個用戶無法處理的大規(guī)模感知任務.

通常，MCS由3方組成：任務請求者，平臺和參與者.任務請求者將感知任務及預算提交到平臺，MCS平臺根據(jù)感知任務的特定要求以及有限的預算內招募參與者.例如，請求者希望在收集某城市的氣溫情況，以便預測未來的天氣狀況.在眾多注冊的參與者中，每個參與者以不同的能力和成本執(zhí)行每個任務，則在預算約束下，如何招募合適數(shù)量的參與者執(zhí)行任務成為一個挑戰(zhàn).

現(xiàn)有的大多數(shù)文獻致力于解決這個挑戰(zhàn)[5-8]，其中文獻[5，6]假設每個參與者完成每個任務的能力是事前已知的，然后通過約束條件下使任務質量最大化或成本最小化來招募參與者.文獻[7，8]中，使用了一組與設備相關的參數(shù)評估了參與者完成任務的能力，從而在預算內選擇最合適的參與者.在招募參與者之后，感知活動將開始，參與者完成感知活動后，將感知報告發(fā)送回MCS系統(tǒng)，感知報告經(jīng)過MCS平臺分析匯總，發(fā)回給任務請求者.

由于最終的感知結果是參與者感知報告的匯總形式[9]，因此基于個人的招募系統(tǒng)可能會存在以下兩個缺陷.首先，僅以參與者可用性招募參與者，而不考慮參與者地理位置以及自身素質等因素，可能增加過多的數(shù)據(jù)報告，而過多的冗余報告不一定會改善結果的整體質量.文獻[10]中分析出，在感知區(qū)域內參與者達到一定程度的覆蓋率后，再增加參與者不會過多改善結果，反而會增加成本.其次，由于參與者存在的信譽問題，個人提交的高質量數(shù)據(jù)報告與低質量數(shù)據(jù)報告匯總時，重要性可能下降.MCS固有的大規(guī)模群體性質意味著它的成功嚴格取決于參與者發(fā)送信息的可靠性.一方面，參與者可以自愿提交不可靠的信息.例如，參與者模擬GPS對Waze網(wǎng)站進行干擾，造成了持續(xù)了數(shù)小時交通擁堵的假象，這種惡意攻擊服務器的行為影響到其他用戶，從而使上萬的駕駛者偏離路線[11].另一方面，參與者可能會無意中提交不準確的數(shù)據(jù)，如檢測區(qū)域噪聲質量時，將手機放入背包中，導致噪聲檢測不準確；在天氣監(jiān)視應用程序中，參與者可以將其設備放在壁爐旁邊或冰箱內[12].無論是哪種情況，這些行為都會導致感知報告的質量下降.

因此，對于群智感知的參與者招募問題，本文提出了移動群智感知中基于群組的參與者招募機制.群組招募機制對招募過程進行了不同的處理，不再以個人為參與者選擇標準，而是基于集體評估所形成的參與者群組進行選擇.為了解決參與者空間覆蓋，提出了群組覆蓋率的概念，通過群組內參與者的個人覆蓋范圍以及地域分布來衡量整個群組的覆蓋率.另外，為解決參與者信譽問題，提出群組信譽的概念，通過計算整個群組內參與者信譽的標準差衡量群組信譽，從而找到一組信譽差異較小的高信譽參與者.另外，本文還考慮參與者的積極性，以便招募對于任務有高積極性的群組.進一步地，為提高群組的感知能力(SA，Sensing Ability)，在平臺給定預算的限制下，本文提出了一種基于遺傳算法的群組招募算法(GR，Group Recuitment algorithm)招募感知能力最大的群組.總而言之，本文的主要貢獻如下：

1)根據(jù)參與者特征對招募過程進行改變，招募不再以單個參與者為標準，而是以群組的形式進行招募，并根據(jù)感知能力對群組進行評估.

2)為了招募最大感知能力的參與者群組，我們提出了一種基于遺傳算法的群組招募算法對招募過程進行了優(yōu)化.

2 相關工作

在移動群智感知中，最常見的問題之一就是參與者招募機制的設計，選擇合適的參與者是完成感知任務的前提.目前流行的選擇參與者方式主要是考慮參與者個體的各種參數(shù)，如參與者時空可用性、參與者信譽等.在本節(jié)中，簡要討論現(xiàn)有的招募系統(tǒng)，重點是選擇標準和評估指標.

參與者的時空可用性是招募時的主要參數(shù)之一.部分文獻中提出了幾種量化候選參與者的時空可用性和覆蓋感知區(qū)域范圍的方法.例如，通過用戶日常工作提供的歷史移動軌跡可以估計用戶在某些區(qū)域的可用性.Hu[13]等人利用強化學習提出了一個新框架，通過逐步積累個體參與者的移動軌跡精準預測參與者的位置，從而選擇合適的參與者.Hao等人[14]收集，分析參與者移動軌跡，并使用訓練過的系統(tǒng)預測未來移動性，將具有相似流動性的參與者分組，從小組中選擇一名參與者執(zhí)行任務，其余的成員作為備選，避免緊急情況下丟失感知數(shù)據(jù).在另一項研究中[15]，根據(jù)數(shù)據(jù)收集任務的時空粒度要求將感知區(qū)域劃分成多個相同大小的子區(qū)域，需要在每個區(qū)域多次測量數(shù)據(jù)樣本，當參與者自己在感知區(qū)域內收到感知任務時，平臺會根據(jù)其當前的GPS位置和剩余能量水平進行招募.Song等人[16]提出在選擇最合適參與者的同時，需要滿足覆蓋范圍問題，在這種情況下，將感知區(qū)域劃分成多個子區(qū)域，通過收集每個子區(qū)域參與者的軌跡來預測未來該參與者的移動范圍，達到以最小的激勵和預算實現(xiàn)任務的覆蓋范圍.Yang等人[17]通過模糊邏輯控制得到不同時空下的參與者密度，以計算出特定時空下任務所需的樣本數(shù)量.文獻[18]中提出一種覆蓋率最大化算法，該算法記錄參與者的軌跡，并選擇其活動軌跡與任務覆蓋率約束相匹配的參與者.文獻[19]中針對參與者優(yōu)選方法，通過參與者完成任務數(shù)量以及空間移動的距離來優(yōu)化選擇參與者，以實現(xiàn)成本最小化.

感知結果是大規(guī)模參與者感知并上傳結果匯總，因此必須保證感知報告的可信度.可以根據(jù)參與者自身的素質，例如，參與者的信譽，專業(yè)知識等來衡量感知報告的可信度.這些素質都是平臺根據(jù)參與者歷史執(zhí)行感知活動行為進行的評估.最流行的評估策略使用信譽和信任框架，文獻[20]中，定義信譽為平臺對參與者行為值得是否信任的意見，由此評估參與者感知任務結果的準確性，從而構建可靠的參與感測系統(tǒng).文獻[21]對移動群智激勵機制的基礎上，提出一種信譽模型的用戶參與激勵機制，通過對參與者評估信譽，在分配任務時，選擇信譽度較高的參與者處理任務，從而提高任務的處理效率.其他研究通過跟蹤參與者隨時間的可靠性來估計感知報告的可靠性，如為每個設備計算信譽分數(shù)以反映感知數(shù)據(jù)的可信度[22].為了減輕惡意或不可靠參與者的影響，可以使用有限數(shù)量的高信任參與者以安全的方式建立信譽，從而解決惡意和不可靠的行為[23].但招募高信譽的參與者相應的花費也會提高.我們希望能夠在保證提交數(shù)據(jù)質量的同時，最小化參與者招募的花費.

招募系統(tǒng)根據(jù)列舉的評估指標從個人角度來選擇參與者進行招募，但在移動群智感知中，根據(jù)群組集體的感知結果來進行參與者招募的研究很少，文獻[24]中，移動眾包平臺通過專業(yè)知識、社交關系，在預算內招募一組參與者共同完成復雜任務，但沒有考慮任務的時空覆蓋率.文獻[25]通過評估參與者空間覆蓋率、剩余能量等提出基于穩(wěn)定性的連續(xù)感測小組招募系統(tǒng)以選擇參與者群體，并可以動態(tài)添加和刪除參與者，實現(xiàn)預期的感知結果，但沒有考慮參與者的信譽問題.文獻[26]所提出的群組更關注于平臺預算，提出一種基于預測的參與者招募，通過將參與者分為兩組，以應對不同預算時的招募.文獻[27]中，展示了一個與位置相關的群智協(xié)作的任務分配問題，通過多人協(xié)作完成平臺分配的復雜任務，但更專注于任務的分配以及調度.本文的工作是綜合考慮參與者的空間覆蓋率、參與者信譽以及預算，區(qū)別于個人招募系統(tǒng)，而是以參與者群組的形式進行招募.

3 系統(tǒng)模型

在本節(jié)中提出的系統(tǒng)模型考慮了一個實際場景，即任務請求者發(fā)布任務，感知平臺從大量候選參與者中選擇合適的參與者執(zhí)行任務，得到結果反饋給請求者.移動群智感知系統(tǒng)基本要素包括任務請求者，系統(tǒng)平臺和大量的移動感知網(wǎng)絡中的參與者，由于候選參與者人數(shù)較多，如何選定合適數(shù)量的參與者是必須要考慮的問題，因此招募參與者的過程以群組形式招募，而不是以單個參與者進行招募.具體過程如圖1所示.

圖1 系統(tǒng)模型Fig.1 System model

首先，任務請求者將任務提交給系統(tǒng)平臺，系統(tǒng)平臺會根據(jù)參與者上傳的位置信息以及個人執(zhí)行任務的歷史信息對參與者進行評估.然后，系統(tǒng)平臺根據(jù)任務信息(例如任務的感知內容以及任務的感知區(qū)域)招募合適的參與者.之后，系統(tǒng)平臺通過考慮參與者的地理位置、信譽、參與者的積極性以及參與者所攜帶的傳感器組，生成所有符合任務條件的參與者群組，在預算條件下通過遺傳算法找出感知能力最大的群組進行招募.進一步地，系統(tǒng)平臺將這些任務分配給參與者群組.最后，當群組完成感知任務之后，參與者群組應將感知數(shù)據(jù)上傳到系統(tǒng)平臺，然后系統(tǒng)平臺處理該數(shù)據(jù)并將結果反饋給任務請求者.

假設P={p1，p2，…pi，…pn}是包含n個參與者的集合，T={t1，t2，…tj，…tm}是包含m個任務的集合，在我們的模型中，將感知任務T定義為一個二元組tj={Sj，Kj}，其中，Sj代表任務tj的感知范圍，Kj代表任務tj所需的傳感器類型，即任務類型，將參與者定義為一個六元組pi={Li，Ri，Repi，Pos，Ai，Costi}，每個參與者的特征在于其本身的素質，如信譽、積極性以及設備相關(如參與者所持設備的一組傳感器).平臺根據(jù)任務的感知區(qū)域以及任務類型選擇某區(qū)域的大量參與者，根據(jù)以上特征對參與者進行評估，使用這些參數(shù)，可以計算參與者群組G的感知能力.

Li代表參與者的地理位置.

Ri代表參與者個人最大活動范圍半徑.在任務發(fā)布時，將參與者當前位置以半徑為Ri的區(qū)域作為個人感知范圍.

Repi代表參與者的信譽，用于確定群組的信譽標準差.

Posi代表參與者的積極性，用來衡量群組執(zhí)行任務的意愿程度，積極性越高，群組執(zhí)行任務的意愿越強.

Ai代表參與者所攜帶智能設備的傳感器種類集合，其決定參與者是否能夠接受任務.

Costi是平臺招募參與者pi所需成本.

如前所述，移動群智感知平臺有一個給定的預算限制，用B表示，即招募參與者的總開銷不能超過B.首先假定招募單個參與者的開銷不會超過B，開銷超過B的參與者將會被平臺直接過濾掉，不予考慮.目的是在該區(qū)域內選擇一組參與者在約束下形成參與者群組協(xié)作執(zhí)行感知任務.基于以下特征評估參與者群組G.

定義1.覆蓋率(Coverg)，由于移動群智感知中任務質量受時空覆蓋的影響，我們根據(jù)感知區(qū)域內參與者自身的感知范圍評估每個參與者，然后根據(jù)組內所有參與者在區(qū)域內的感知范圍C以及分布D衡量小組的覆蓋率，表示為：

(1)

首先根據(jù)組內所有參與者的感知范圍確定群組覆蓋面積，每個參與者的感知范圍是以自身最大活動范圍R為半徑的圓.群組覆蓋面積為所有參與者感知范圍的總和，表示為：

(2)

(3)

其中，S代表任務的感知區(qū)域范圍，si代表每個參與者個人感知范圍.

其次，需要衡量群組內參與者的分布D.我們使用玻爾茲曼熵來衡量參與者的分布情況，在熱力學里，熵代表系統(tǒng)內分子熱運動的無序性的量度，熵越大，代表系統(tǒng)越無序.舉例來說，空氣中的分子分布越分散，它的熵越大，空氣中分子越無序.在本文中，根據(jù)區(qū)域內群組成員的地理位置分布情況確定其熵，從而得到群組內參與者的分布，熵越大，代表群組成員在感知區(qū)域內越分散.圖2展示了在某個感知任務的區(qū)域內，參與者群組成員的覆蓋與分布.

圖2 參與者群組覆蓋Fig.2 Participant group coverage

群組內參與者的分布D定義如下：

(4)

(5)

為了更進一步說明群組的分布D，我們用圖3展示兩種參與者群組的分布情況.

圖3 群組分布Fig.3 Group distribution

圖3(a)中，N=5，M=2，ρ1=3，ρ2=2，D=0.13，圖3(b)中，N=5，M=5，ρ1=ρ2，…，ρ5=2，D=0.34.根據(jù)公式(4)和公式(5)可以計算出，圖3(b)群組的分布要比圖3(a)群組分布更均勻.

定義2.信譽(Repg)，為了確保參與者群組提交任務的感知質量，需要評估群組的整體信譽，在群組信譽均值達到任務所需閾值的前提下，組內成員的信譽越接近，群組執(zhí)行任務的效率越高.因此我們用組成員信譽的標準差衡量參與者群組的整體信譽.根據(jù)時效性、可靠性[28]和數(shù)據(jù)完整性對每個參與者的信譽進行綜合評估，以參與者pi具體分析如下：

時效性ri：我們使用“時效性”一詞表征參與者pi完成任務的及時程度.在指定的時間段內，根據(jù)參與者提交任務的時效性評估參與者的信譽.時效性取決于任務響應時間和任務期限d.在最近的h次任務聯(lián)系中系統(tǒng)平臺對參與者pi的時效性評估為：

(6)

(7)

可靠性di：參與者在接受任務前會向平臺提交相關執(zhí)行任務的歷史信息，信息包含參與者pi在h次執(zhí)行任務聯(lián)系中，每個任務的開始時間si和結束時間ei.可靠性di定義為參與者執(zhí)行任務所花費的時間與平臺要求總完成任務時長的比值.該值越大，表明參與者在過去執(zhí)行任務時花費了更多的時間完成任務，因此可靠性相應的也越大，可靠性定義為：

(8)

其中，D表示整個任務過程的截止時間.di的取值范圍為[0，1].

(9)

根據(jù)平臺對參與者時效性，可靠性和數(shù)據(jù)完整性的評估，可以得出參與者pi的信譽Repi：

(10)

為了綜合評估參與者群組的信譽，我們采用組內參與者信譽的平均值以及信譽的標準差來衡量.目的是招募到一群高信譽且信譽相近的參與者來組成群組.群組的信譽定義如下：

(11)

(12)

定義3.積極性(Posg)，參與者的積極性是平臺根據(jù)參與者pi以往參與感知任務的次數(shù)評以及該參與者是否努力完成分配給他們的任務.積極性定義為組內參與者積極性的平均值：

(13)

(14)

其中，Complete(m)代表參與者pi完成的任務總數(shù)，Accpet(m)代表該參與者接受的任務總數(shù).CTi為參與者pi的積極性，Posg表示參與者群組的積極性.

(15)

即組內成員必須滿足任務所必須的傳感器類型，如果組內參與者均執(zhí)行不了任務，則為0.

定義5.參與者群組預算Cost(g)，一個參與者群組的費用可以簡單計算為群組成員所需的成本之和：

Cost(g)=∑i∈gCost(i)

(16)

其中Cost(i)為平臺需要給參與者群組g中參與者pi的成本.

因此，參與者群組的感知能力SA，為：

(17)

我們的目的是在約束條件下找到最大感知能力的參與者群組：

(18)

s.t.：

Cost(g)

4 參與者群組的構建

為了最大化SA，我們使用基于遺傳算法的群組招募算法(GR，Group Recuitment algorithm)來選擇一組參與者，這些群組內的參與者數(shù)量沒有先前確定.從任意一個參與者群組開始生成，一直到預算內可供選擇的所有群組，該算法將在感知任務的約束范圍內選擇SA最大的群組.對于每個符合條件的參與者群組，運行算法，并記錄當前具有最大SA的群組以及該組參與者人數(shù)規(guī)模，這稱為一個階段.每個階段我們通過計算每個群組輸出的一組當前最大SA的成員，與其他群組進行交叉和變異，通過篩選參與者進入群組，視為下個階段.最后，每個階段將參與者添加到群組中之后，將選擇獲得最高SA的群組.在下文中，我們將更詳細地介紹用于選擇給定大小的最佳群體的遺傳算法.

1)仿真一個參與者數(shù)據(jù)集，參與者的ID將隨機排列并記錄該參與者的信譽，在預算內形成多組一定規(guī)模大小的參與者群組，該群組的集合將稱為總體.

2)根據(jù)適應度函數(shù)對第一步中形成的群組進行評估，即在這種情況下評估總體中所有群組預期的SA.

3)將根據(jù)感知平臺確定的參與者群組感知能力約束檢查每個群組，若群組有至少一項違反限制條件，如信譽達不到任務所需閾值，群組接受度達不到任務所需，則認為該組不具備執(zhí)行感知任務的能力，同時將該組排除在選擇之外.

4)根據(jù)適應度值和群組是否滿足約束條件，設置輪盤賭并旋轉輪盤，旋轉次數(shù)等于參與者群組的規(guī)模，即參與者群組總數(shù).這樣做使得更有可能選擇具有較高適應度的組而不是選擇較低適應度的組.

5)從上一步選擇的群組中，根據(jù)交叉概率對組內參與者進行進行交叉操作，將參與者添加到群組中，生成具有新SA的群組，對于每個交叉操作，必須確定交叉點，并且該交叉點是隨機的.然后依次執(zhí)行對每一對的交叉操作，即將不同群組內的參與者交換.

6)將根據(jù)突變概率對新生成種群中的某些群組成員進行突變，這將確定將執(zhí)行多少次突變操作.這些群組以及要替換的成員的編號將隨機生成.不需要突變的組將原樣復制到下一代.

7)將評估所有群組中各個群組的適應度值.

8)檢查是否有任何群組違反任何約束.

9)重復5)～9)，直到某一群組達到可能最大的SA，或達到最大迭代次數(shù)為止，當最大的SA在一定的迭代次數(shù)中保持不變時，就會發(fā)生收斂.

算法1說明群組招募算法的執(zhí)行過程.

算法1.群組招募算法(GR)形成過程

1.輸入：參與者集P，任務集T，預算B

2.輸出：SA

3.Repeat

4.forP≠?do

5.ifCost(g)

6. find All Groups from

7.forall Groupsdo：

8. 評估群組的SA

9. 檢查群組是否符合要求

10.ifdissatisfy；

11. remove group

12.endif

13. 組內參與者交叉

14. 組內參與者變異

15.ifcurrentGroup>bestGroup：

16. bestGroup=currentGroup

17. bestSA=currentSA

18.endif

19.endfor

20.Return最大SA

5 實驗分析

5.1 實驗設置

為了進一步說明所提出的模型和算法的優(yōu)勢，我們在Python中對任務分配的性能進行了實驗.仿真實驗的主要參數(shù)在表1中給出.

表1 仿真參數(shù)Table 1 Simulation parameters

為了與提出的GR算法進行比較，將其他兩種算法(基于貪婪的參與者招募算法(BUR)[29]和最優(yōu)效用參與者招募算法(TopK)[30]作為基線，并針對在不同預算、參與者數(shù)量和任務數(shù)量上的情況進行比較.

基于貪婪的參與者招募算法(BUR)-在BUR中，所有參與者根據(jù)所需信譽進行排序，BUR采用貪婪的思想，首先招募信譽最高的參與者，同時這些參與者要滿足約束條件，即參與者攜帶傳感器種類符合任務所需.

最優(yōu)效用參與者招募算法(TopK)-在TopK中，參與者根據(jù)信譽以及積極性計算出每個參與者的效用，在預算內招募個滿足約束條件的參與者，計算參與者總體感知能力.

5.2 實驗設置

為了評估所提出的模型有效性，提出執(zhí)行效率、平均任務質量、任務完成率和招募人數(shù)四個指標進行評估.當平臺根據(jù)預算招募到參與者后，將發(fā)布的任務分配給這些參與者，以任務的執(zhí)行效率、平均任務質量和任務完成率評估各個算法的優(yōu)缺點.

a)任務執(zhí)行效率

總執(zhí)行時間=感知能力×單個任務執(zhí)行時間×任務數(shù)學

我們將任務執(zhí)行效率定義為在任務期限內，完成任務的剩余時間與任務期限的比值.根據(jù)參與者感知能力計算出執(zhí)行任務時間，通過計算在某一段時間內，參與者執(zhí)行任務的效率來評估招募算法.

b)平均任務質量

感知質量=感知能力×執(zhí)行任務理論質量-質量誤差

由于參與者存在傳感器類型標準不一、設備能量不足等情況，執(zhí)行任務的質量可能與感知任務的所需的理論質量有差異，因此，平均任務質量是根據(jù)參與者感知能力計算出執(zhí)行任務的理論感知質量減去誤差后，與任務所需質量的比值.

c)任務完成率

完成任務數(shù)量與參與者的感知能力以及等待時間相關，其中感知能力與參與者的覆蓋以及傳感器種類進行計算，以一定的預算條件下，根據(jù)算法招募到參與者的任務完成率來評估算法.

d)招募人數(shù)

招募人數(shù)=預算-∑信譽×參與者報價

根據(jù)預算和招募參與者所需的花費確定招募人數(shù)，其中，參與者所需花費根據(jù)參與者自身的信譽決定，信譽越高的參與者，所需花費越多.

5.3 性能評價

5.3.1 任務執(zhí)行效率

圖4顯示任務數(shù)量對任務完成率的影響.在任務數(shù)量一定時，隨著預算的增加，BUR算法和GR算法招募到參與者的任務執(zhí)行效率升高，而TopK算法增幅很小.其中，在預算低于400時，TopK算法與GR算法相差不大，且高于BUR算法，因為當預算較少時，TopK算法招募到的參與者是最優(yōu)參與者，所以執(zhí)行效率較高，而GR算法所招募的群組可選參與者較少，因此沒有足夠的參與者形成感知能力較高的群組.當預算高于400時，GR算法任務執(zhí)行效率明顯優(yōu)于其他兩個算法.其原因是，在預算較高時，GR算法招募群組的選擇更多，且感知能力SA隨著群組的規(guī)模擴大而增強，執(zhí)行任務時間減少，因此GR算法所招募的參與者執(zhí)行效率更高，在預算達到2000時，執(zhí)行效率達到最高，為1.而BUR算法和TopK算法隨著預算的增多，執(zhí)行效率提升較慢，其原因是招募的參與者感知范圍較小，執(zhí)行任務的時間較長，因此執(zhí)行效率上升較慢.

圖4 預算對任務執(zhí)行效率的影響Fig.4 Effect of budget on task execution efficiency

5.3.2 平均任務質量

圖5顯示預算對平均任務質量的影響.當預算增多時，GR算法和BUR算法的平均任務質量先上升后穩(wěn)定，TopK算法先穩(wěn)定后下降.當預算在200-1000時，GR算法招募的群組的感知能力和覆蓋率在升高，BUR算法所招募的參與者覆蓋率也在升高，因此感知質量增大，在任務數(shù)一定時，平均任務的感知質量會上升，TopK由于招募參與者時只考慮參與者效用，因此質量變化較小.當預算在1000-2000時，GR招募的群組和BUR算法招募的參與者由于感知區(qū)域大小以及參與者數(shù)量影響，空間覆蓋不會有太大變化，因此平均任務質量維持在一定數(shù)值，TopK招募的參與者人數(shù)增多的同時未考慮參與者自身的空間覆蓋，因此可能會出現(xiàn)招募的參與者已在其他參與者感知范圍內，從而影響感知質量下降.

5.3.3 任務完成率

圖6顯示任務數(shù)量對任務完成率的影響.預算為1000時，隨著任務數(shù)量的增加，等待時間變長，任務完成會減慢，GR算法的任務完成率先穩(wěn)定后下降，BUR算法和TopK算法逐漸下降.當任務數(shù)量小于300時，GR算法招募的群組會保持一定感知能力，在任務所需時間內可以有效完成任務.當任務數(shù)量上升時，由于參與者數(shù)量受預算影響，在不增加預算的前提，3個算法的任務完成率均會下降，但GR算法下降趨勢慢，原因為群組內的參與者在感知區(qū)域內分布均勻，區(qū)域內參與者完成任務數(shù)量盡管在減少但下降緩慢.

我們不僅考慮任務數(shù)量對任務完成率的影響，還考慮任務的性質與分布.任務性質代表任務所需的傳感器種類，當任務較為復雜時，需要多個傳感器收集數(shù)據(jù)完成任務，用傳感器種類代表任務的復雜程度.如圖7所示，預算為1000，任務數(shù)量為200時，GR算法的任務完成率穩(wěn)定在0.5左右，BUR算法和TopK算法逐漸下降.因為GR算法中群組感知能力中參與者接受度決定了組內參與者可以執(zhí)行需多個類型傳感器的復雜任務才可以形成群組，而BUR算法和TopK算法任務完成率會因為招募到的部分參與者個人能力不足，完成不了復雜任務而逐漸下降.

任務分布用參與者在區(qū)域內的覆蓋率衡量，當任務在區(qū)域的分布稀疏時，即分布任務較少時，候選參與者在該區(qū)域內的覆蓋率低.當任務在區(qū)域的分布密集時，候選參與者在區(qū)域內覆蓋率較高.如圖8所示，預算為1000，任務數(shù)量為200時，GR算法的任務完成率平緩上升，BUR算法和TopK算法逐漸上升.因為GR算法群組感知能力中參與者的覆蓋率是通過均勻分布決定的，因此群組招募即使人數(shù)較少，也可以覆蓋整個區(qū)域.而BUR算法和TopK算法任務完成率只有當在招募到的參與者覆蓋較高的情況下，才可以完成規(guī)模較大、分布密集的任務.

圖8 任務分布對任務完成率的影響Fig.8 Effect of distribution of tasks on the task completion rate

5.3.4 招募人數(shù)

圖9為預算對招募人數(shù)的影響.在參與者總人數(shù)為200時，BUR和TopK算法隨預算的增加所需的參與者數(shù)量也增加，而GR算法所需的群組人數(shù)呈現(xiàn)出先上升后平穩(wěn)的趨勢.原因為BUR和TopK都是在預算內找到信譽最優(yōu)的參與者和效用最高的參與者，所以人數(shù)會隨著預算的增加而上升.而GR算法是以群組的方式找到一組參與者，直到在預算內達到最高的感知能力的群組，因此在預算一定時，當群組感知能力達到最大，再增加人數(shù)也不會改變感知能力，因此群組招募的參與者數(shù)量較少.圖4的任務執(zhí)行效率和圖5的平均任務質量中，當預算超過1000時，群組的任務執(zhí)行效率仍在增長，而平均任務質量增長緩慢，同時，招募人數(shù)較少，花費較多.可以看出，在參與者數(shù)量一定的情況下，增加過多的預算盡管會提升任務執(zhí)行效率，但平均任務質量提升較小，也會增加招募花費.

圖9 預算對招募人數(shù)的影響Fig.9 Effect of budget on the number of participants recruited

6 總 結

在本文中，提出了移動群智感知中一個基于群組的招募機制.與先前文獻中提出的參與者選擇機制不同，我們提出了一種新的評估方法，招募是基于參與者群組提供的最高感知能力.實驗證明，基于個人的參與者選擇存在一些缺陷，這些缺陷已經(jīng)由我們提出的群組招募系統(tǒng)解決，如考慮參與者在感知區(qū)域內的覆蓋以及參與者信譽，同時以群組感知能力為指標招募合適的參與者群組.群組的感知能力由群組覆蓋率、信譽、積極性以及參與者群組接受度組成.選擇最大感知能力的群組執(zhí)行平臺發(fā)布的任務，通過仿真數(shù)據(jù)集，證明該招募機制在任務執(zhí)行效率、任務完成率、平均任務質量上要優(yōu)于現(xiàn)有的個人招募機制.至于將來的工作，應更多考慮感知任務的特殊性、緊急性以及參與者自身的時間可用性、工作負載能力等屬性對參與者群組招募的影響.