移動群智感知中基于群組的參與者招募機(jī)制

楊桂松，江文成，何杏宇

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

2(上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計(jì)學(xué)院，上海 200093)

E-mail：xy_he@usst.edu.cn

1 引 言

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 系統(tǒng)模型

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

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

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

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

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

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

Repi代表參與者的信譽(yù)，用于確定群組的信譽(yù)標(biāo)準(zhǔn)差.

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

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

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

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

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

(1)

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

(2)

(3)

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

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

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

群組內(nèi)參與者的分布D定義如下：

(4)

(5)

為了更進(jìn)一步說明群組的分布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)可以計(jì)算出，圖3(b)群組的分布要比圖3(a)群組分布更均勻.

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

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

(6)

(7)

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

(8)

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

(9)

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

(10)

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

(11)

(12)

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

(13)

(14)

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

(15)

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

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

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

(16)

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

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

(17)

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

(18)

s.t.：

Cost(g)

4 參與者群組的構(gòu)建

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

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

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

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

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

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

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

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

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

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

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

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

1.輸入：參與者集P，任務(wù)集T，預(yù)算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. 組內(nèi)參與者交叉

14. 組內(nèi)參與者變異

15.ifcurrentGroup>bestGroup：

16. bestGroup=currentGroup

17. bestSA=currentSA

18.endif

19.endfor

20.Return最大SA

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

5.2 實(shí)驗(yàn)設(shè)置

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

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

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

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

b)平均任務(wù)質(zhì)量

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

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

c)任務(wù)完成率

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

d)招募人數(shù)

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

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

5.3 性能評價(jià)

5.3.1 任務(wù)執(zhí)行效率

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

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

5.3.2 平均任務(wù)質(zhì)量

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

5.3.3 任務(wù)完成率

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

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

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

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

5.3.4 招募人數(shù)

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

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

6 總 結(jié)

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