移動(dòng)群智感知中收益最大化的用戶(hù)招募算法

郭會(huì)東,黃劉生,高國(guó)舉 ,徐宏力

1(中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230027) 2(中國(guó)科學(xué)技術(shù)大學(xué) 蘇州研究院,江蘇 蘇州 215123)

1 引 言

近年來(lái),隨著微電子技術(shù)和無(wú)線(xiàn)通信技術(shù)的發(fā)展,智能手機(jī)的功能越來(lái)越豐富,性能也得到很大提高.一臺(tái)智能手機(jī)集成了各類(lèi)資源:強(qiáng)大的計(jì)算存儲(chǔ)資源(CPU/GPU,本地存儲(chǔ)/云端存儲(chǔ)),多種通信接口(3G/4G,藍(lán)牙,WiFi等),各種嵌入式傳感器(相機(jī),GPS,陀螺儀,噪聲傳感器等),大容量的電池,豐富的應(yīng)用軟件等[1,2].在很多場(chǎng)合,智能手機(jī)已經(jīng)可以代替?zhèn)鹘y(tǒng)無(wú)線(xiàn)傳感器的角色,采集、分析各種環(huán)境數(shù)據(jù).得益于技術(shù)和經(jīng)濟(jì)的發(fā)展,智能手機(jī)已經(jīng)得到廣泛應(yīng)用,成為人們生活和工作中不可或缺的隨身攜帶設(shè)備.數(shù)以?xún)|計(jì)的智能手機(jī)用戶(hù)分布各地,通過(guò)網(wǎng)絡(luò)連接,構(gòu)成了一張無(wú)處不在的移動(dòng)無(wú)線(xiàn)傳感網(wǎng)絡(luò),為新技術(shù)的發(fā)展提供支撐和保障.

借助這張強(qiáng)大的無(wú)線(xiàn)傳感網(wǎng)絡(luò),移動(dòng)群智感知(Mobile CrowdSensing,MCS)技術(shù)也得到迅速發(fā)展,并廣泛應(yīng)用于公共交通、空氣質(zhì)量監(jiān)測(cè)、噪聲監(jiān)控等領(lǐng)域[3].在移動(dòng)群智感知中,一組移動(dòng)用戶(hù)通過(guò)他們攜帶的智能手機(jī)在城鎮(zhèn)環(huán)境中協(xié)同執(zhí)行一項(xiàng)大規(guī)模的感知工作.其中,如何招募合適的移動(dòng)用戶(hù)來(lái)協(xié)作完成這項(xiàng)工作是一個(gè)重要的問(wèn)題,也是當(dāng)前的研究熱點(diǎn).當(dāng)前的工作主要研究在位置相關(guān)的場(chǎng)景下,如何招募用戶(hù)和分配感知任務(wù).目前已經(jīng)有許多學(xué)者在這一問(wèn)題上進(jìn)行了探索分析,取得了不少成果,并給出了不少具有創(chuàng)新性的解決方案[4-13].

在本文中,我們主要研究在預(yù)算受限的移動(dòng)群智感知中,平臺(tái)收益最大化的用戶(hù)招募問(wèn)題(Profit-Maximizing User Recruitment problem,PUR).更具體地講,一個(gè)移動(dòng)群智感知平臺(tái)上包含許多感知任務(wù),每項(xiàng)任務(wù)完成后,平臺(tái)可以獲得相應(yīng)的收益.平臺(tái)通過(guò)移動(dòng)社交網(wǎng)絡(luò)將這些感知任務(wù)信息發(fā)布給廣大移動(dòng)用戶(hù),每個(gè)移動(dòng)用戶(hù)從中選擇他們可以執(zhí)行的任務(wù),并告知平臺(tái),同時(shí)也把自己的報(bào)酬要價(jià)發(fā)回給平臺(tái).接下來(lái),平臺(tái)從這些有協(xié)作意向的移動(dòng)用戶(hù)中,通過(guò)合適的篩選辦法,選出一部分來(lái)執(zhí)行這些感知任務(wù),從而達(dá)到總收益的最大化.同時(shí),在招募用戶(hù)時(shí),平臺(tái)需要保證招募總開(kāi)銷(xiāo)不超過(guò)給定的預(yù)算.不同于已有的研究,我們認(rèn)為每個(gè)移動(dòng)用戶(hù)能處理的任務(wù)是確定的,因此,本文的研究重點(diǎn)集中在用戶(hù)的選擇問(wèn)題上,而不是對(duì)用戶(hù)的任務(wù)分配[4,5].此外,每個(gè)感知任務(wù)可以被多個(gè)用戶(hù)執(zhí)行,但是每個(gè)任務(wù)的收益是固定不變的,這也使得我們的工作不同于簡(jiǎn)單的0-1背包問(wèn)題[14].

1.首先介紹了移動(dòng)群智感知中的用戶(hù)招募問(wèn)題,并形式化為數(shù)學(xué)模型.模型中每個(gè)感知任務(wù)可以被多個(gè)用戶(hù)執(zhí)行,但是單個(gè)任務(wù)的收益是固定的.平臺(tái)的目標(biāo)是最大化這些感知任務(wù)的總收益,同時(shí)招募用戶(hù)的總開(kāi)銷(xiāo)不超過(guò)給定預(yù)算;

3.為了評(píng)估算法的性能,進(jìn)行了實(shí)驗(yàn)仿真.結(jié)果表明,相比其他算法,gPUR算法具有更好的性能表現(xiàn).

本文接下來(lái)的內(nèi)容組織如下:首先在第2節(jié)中引入模型,并形式化最優(yōu)解問(wèn)題.第3節(jié)中提出貪心算法gPUR,并做性能分析.接下來(lái)在第4節(jié)中通過(guò)實(shí)驗(yàn)仿真驗(yàn)證算法的正確性,比較不同算法的性能.最后在第5節(jié)中回顧當(dāng)前的相關(guān)研究,并在第6節(jié)總結(jié)全文.

2 模型和問(wèn)題形式化

2.1 模型

另一方面,系統(tǒng)中還有大量的移動(dòng)社交網(wǎng)絡(luò)用戶(hù),每個(gè)用戶(hù)可以執(zhí)行集合X中的部分任務(wù).需要注意的是,在本文中僅討論那些愿意參與群智感知的移動(dòng)用戶(hù).我們假設(shè)共有m名移動(dòng)用戶(hù),并使用集合U={u1,u2,…,uj,…,um}來(lái)表示.由于移動(dòng)用戶(hù)所攜帶設(shè)備的本地資源有限,每個(gè)用戶(hù)只能執(zhí)行部分任務(wù),我們將用戶(hù)uj能執(zhí)行的任務(wù)集合表示為Sj(Sj?X),并將所有用戶(hù)的可執(zhí)行任務(wù)的集族表示為S={S1,S2,…,Sj,…,Sm}.如果某個(gè)用戶(hù)uj被平臺(tái)招募,他會(huì)執(zhí)行Sj中的每一個(gè)感知任務(wù),并通過(guò)移動(dòng)社交網(wǎng)絡(luò)將感知結(jié)果返回給平臺(tái).

同時(shí),在任務(wù)的執(zhí)行過(guò)程中,每個(gè)移動(dòng)用戶(hù)需要消耗一定的本地資源,包括CPU資源、本地存儲(chǔ)、電池以及時(shí)間.因此,每個(gè)被招募的用戶(hù)uj會(huì)要求平臺(tái)支付一定的開(kāi)銷(xiāo),我們用Cj來(lái)表示.在該模型中,我們假定每個(gè)移動(dòng)用戶(hù)都是誠(chéng)實(shí)可信的,也就是說(shuō)他們不會(huì)惡意篡改他們的真實(shí)開(kāi)銷(xiāo).

如前所述,移動(dòng)群智感知平臺(tái)有一個(gè)給定的預(yù)算限制,用B表示,也即招募用戶(hù)的總開(kāi)銷(xiāo)不能超過(guò)B.因此,我們首先假定招募單個(gè)用戶(hù)的開(kāi)銷(xiāo)不會(huì)超過(guò)B,因?yàn)槟切╅_(kāi)銷(xiāo)超過(guò)B的用戶(hù)將被平臺(tái)直接過(guò)濾掉,不予考慮.

最終的目標(biāo)就是從集合U中選擇部分用戶(hù)(也即找到一個(gè)子集族Ω?S),使得這些用戶(hù)覆蓋的任務(wù)帶來(lái)的總收益最大化,同時(shí)保證招募用戶(hù)的總開(kāi)銷(xiāo)C(Ω)不超過(guò)預(yù)算B.

2.2 問(wèn)題形式化

本文中,我們聚焦于預(yù)算受限的移動(dòng)群智感知中,收益最大化的用戶(hù)招募問(wèn)題(后文稱(chēng)之為PUR問(wèn)題).我們使用一個(gè)集族Ω來(lái)表示用戶(hù)招募策略,其中Sj∈Ω表示用戶(hù)uj(uj∈U)已經(jīng)被平臺(tái)招募.PUR問(wèn)題可以形式化描述如下:

Max:P(Ω)=∑Sj∈ΩP(Sj)=∑xi∈∪Sj∈ΩSjpi

(1)

s.t.

Ω?S

(2)

(3)

?xi∈X,?Sj∈S

(4)

其中,不等式(3)表示招募用戶(hù)的總開(kāi)銷(xiāo)不會(huì)超過(guò)給定的預(yù)算B.需要再次注意的是,對(duì)任意的Sj,Sj′∈S,有P(Sj)+P(Sj′)=P(Sj∪Sj′),這也使得我們的問(wèn)題不同于簡(jiǎn)單的0-1背包問(wèn)題[14].

為了方便參考,我們將本文中常用的符號(hào)含義總結(jié)如表1所示.

3 算法設(shè)計(jì)與分析

在本節(jié)中,我們首先證明PUR問(wèn)題是一個(gè)NP難問(wèn)題,然后在分析典型的貪心算法[16]的基礎(chǔ)上,提出一個(gè)改進(jìn)的貪心算法gPUR來(lái)解決這個(gè)問(wèn)題,并分析了算法的時(shí)間復(fù)雜度和空間復(fù)雜度.最后,通過(guò)數(shù)學(xué)推導(dǎo)給出算法的近似比[15].

3.1 NP難問(wèn)題

首先,我們證明除非P=NP,否則本文提出的PUR問(wèn)題不可能有多項(xiàng)式時(shí)間的最優(yōu)解.有如下定理:

定理1.PUR問(wèn)題是一個(gè)NP難問(wèn)題.

證明:為了證明PUR問(wèn)題是一個(gè)NP難問(wèn)題,我們首先考慮如下0-1背包問(wèn)題:

表1 主要符號(hào)含義描述
Table 1 Description of major notations

符 號(hào)含 義n；m感知任務(wù)數(shù)；移動(dòng)用戶(hù)數(shù)X；U感知任務(wù)的集合；移動(dòng)用戶(hù)的集合pi；Cj任務(wù)xi的收益；招募用戶(hù)uj的開(kāi)銷(xiāo)Sj；SS；用戶(hù)uj可以執(zhí)行的任務(wù)集；全部用戶(hù)可以執(zhí)行的任務(wù)集族；Ω(Ω?SS)平臺(tái)的用戶(hù)招募策略P(Sj)；P′(Sj)任務(wù)集Sj帶來(lái)的總收益；Sj單獨(dú)覆蓋的任務(wù)帶來(lái)的收益P(Ω)；C(Ω)感知平臺(tái)的總收益；用戶(hù)招募的總開(kāi)銷(xiāo)

Max:p1x1+p2x2+…+pnxn,

s.t.w1x1+…+wnxn≤S,

x1,…,xn∈{0,1}.

其中,pi和wi分別是第i件物品的價(jià)值和重量,S表示背包的容量,xi指示第i件物品是否放入背包中.

然后,考慮PUR問(wèn)題的一種特例:每個(gè)用戶(hù)可以執(zhí)行的感知任務(wù)集是互斥的,也即對(duì)任意Sj,Sj′∈S且Sj≠Sj′,有Sj∩Sj′=?.由此,我們可以將每個(gè)用戶(hù)看做0-1背包問(wèn)題中的一項(xiàng)物品,并使用P(Sj)和Cj分別表示每個(gè)人的價(jià)值和重量.因此,我們的PUR問(wèn)題可以形式化描述如下:

Max:

∑Sj∈ΩP(Sj)

s.t.

∑Sj∈Ω?SCj≤B.

將0-1背包問(wèn)題中的pi,wi和S分別映射為本文PUR問(wèn)題中的P(Sj),Cj和B,可以得出這兩個(gè)問(wèn)題是等價(jià)的.也就是說(shuō),我們的PUR問(wèn)題的特例是一個(gè)典型的0-1背包問(wèn)題.而0-1背包問(wèn)題是NP難的[14],因此PUR問(wèn)題也至少是NP難的.

3.2 算法設(shè)計(jì)

我們首先分析典型的貪心算法[16],該算法近似比無(wú)界.算法執(zhí)行過(guò)程的每一次迭代都選擇一個(gè)用戶(hù)任務(wù)集Sj,使得P′(Sj)/Cj最大,直到招募總開(kāi)銷(xiāo)超過(guò)給定預(yù)算或可選任務(wù)集族為空.我們考慮一個(gè)只包含2個(gè)感知任務(wù)X={x1,x2}和兩個(gè)移動(dòng)用戶(hù)U={u1,u2}的場(chǎng)景,其中,p1=θ(θ>1),p2=1,Sj={xj}(j=1,2),C1=θ+1,C2=1,B=θ+1.根據(jù)貪心策略,每次迭代應(yīng)該選擇使得P′(Sj)/Cj最大的那個(gè)集合,因此我們得到用戶(hù)招募策略Ω={S2},總收益為P(S2)=1.但是,顯然最優(yōu)解應(yīng)該是Ω={S1},總收益為P(S1)=θ.本例子中的近似比為θ,因此該算法是無(wú)界的.

為此,本文采用了一種改進(jìn)的貪心算法來(lái)解決上述PUR問(wèn)題,我們稱(chēng)之為gPUR算法,具體步驟如算法1所示.在該算法中,我們首先找到一個(gè)集合的集族Ω,集族中的每個(gè)任務(wù)集Sj都是基于貪心策略挑選出來(lái)的,即每次挑選都使得P′(Sj)/Cj最大化.然后,從所有用戶(hù)的任務(wù)集中找出某個(gè)收益最大的集合Sj′,即P(Sj′)是最大的.最后,通過(guò)比較Ω和Sj′這兩個(gè)結(jié)果,選擇總收益最大的那一個(gè),并作為最終的招募策略輸出.

算法1.gPUR算法

Output:Ω

1.Ω=?,S′=S;

2.repeat

3. SelectSj∈S,that maximizesP′(Sj)/Cj;

4.ifP′(Sj)/Cj>0andC(Ω)+Cj≤Bthen

5.Ω=Ω∪{Sj};

6. S=S{Sj};

7.untilS=?orC(Ω)≥B

8. SelectSj′∈S′ that maximizesP(Sj′);

9.ifP(Ω)

10.Ω={Sj′};

11.returnΩ

3.3 算法的復(fù)雜度分析

在算法1中,可看到主要的計(jì)算開(kāi)銷(xiāo)由第3行產(chǎn)生.為了尋找P′(Sj)/Cj最大的任務(wù)集Sj,對(duì)每一個(gè)Sj∈S,需要先驗(yàn)證Sj中的每一個(gè)任務(wù)xi是否已經(jīng)被當(dāng)前招募策略覆蓋,也即對(duì)任意xi∈Sj,是否已經(jīng)存在Sj′∈Ω,使得xi∈Sj′.如果采用逐一比對(duì)的方法,第3行的計(jì)算開(kāi)銷(xiāo)為O(m2n2).但是,如果我們采用以空間換時(shí)間的思想,使用一個(gè)大小為n的布爾數(shù)組來(lái)指示每個(gè)任務(wù)是否已經(jīng)被當(dāng)前招募策略所覆蓋,則可以將第3行的計(jì)算開(kāi)銷(xiāo)降低至O(mn).而上述貪心選擇過(guò)程(第2-7行)最多重復(fù)m次,從而算法的時(shí)間復(fù)雜度為O(m2n).此外,由于需要大小為n的臨時(shí)存儲(chǔ)空間,因此算法的空間復(fù)雜度為O(n).這是可以接受的多項(xiàng)式時(shí)間和空間復(fù)雜度.

3.4 算法的性能分析

引理1.在每次迭代tk后(k=1,2,…,l+1),有:

證明:由算法1可知,在第k次迭代tk前,都會(huì)選擇一個(gè)使得P′(Sk)/Ck最大的集合,因此對(duì)于ΩoptΩk-1中的每一個(gè)集合,收益-開(kāi)銷(xiāo)比最大為P′(ωk)/Ck.而ΩoptΩk-1中的集合的總開(kāi)銷(xiāo)由預(yù)算Β限定,因此,由集族ΩoptΩk-1所覆蓋,但不被集族Ωk-1所覆蓋的感知任務(wù)帶來(lái)的總收益最多為Β×(P′(ωk)/Ck).因此,我們有:

(5)

同時(shí),根據(jù)P′(ωk)的定義,有如下等式:

P′(ωk)=P(Ωk)-P(Ωk-1)

(6)

將等式(6)的右邊帶入等式(5)中,即得到上述引理中的不等式,從而證明引理1成立.

基于引理1,進(jìn)一步推導(dǎo)可以得到如下引理:

引理2.在每次迭代tk后(k=1,2,…,l+1),有:

證明:可以使用數(shù)學(xué)歸納法證明這個(gè)引理.

1.對(duì)于k=1,有(PΩk)=P(ω1)=P′(ω1).根據(jù)算法1,在所有集合中P′(ω1)/C1最大,且總開(kāi)銷(xiāo)被限定在B以?xún)?nèi).有:

2.假設(shè)對(duì)于迭代t1,t2,…,tk-1,引理2都成立,通過(guò)下面的公式推導(dǎo),我們可以證明在迭代tk后,引理2也成立:

P(Ωk)=P(Ωk-1)+(P(Ωk)-P(Ωk-1))

(7)

(8)

(9)

(10)

(11)

引理1和引理2給出了貪心算法的一些基本性質(zhì),為后續(xù)分析gPUR算法的近似比提供了基礎(chǔ).下面的定理給出近似比:

證明:在分析算法近似比之前,我們先給出一些在后面的證明中將要用到的基礎(chǔ)知識(shí):

接下來(lái),基于引理2,對(duì)于迭代tl+1,有:

(12)

(13)

(14)

(15)

其中,不等式(13)表示將ωl+1加入到Ωl中將會(huì)超出系統(tǒng)平臺(tái)的預(yù)算Β,因此C(Ωl+1)=C(Ωl)+Cl+1≥Β;不等式(14)則是基于上面介紹的基礎(chǔ)知識(shí)推導(dǎo)而來(lái).然后,我們得到下面的公式:

(16)

在我們的gPUR算法中,P′(ωl+1)最大不會(huì)超過(guò)任意單個(gè)用戶(hù)的任務(wù)集的總收益.換言之,P′(ωl+1)的最大值是算法1中第8步得到的結(jié)果,也即P(Sj′).因此,可以得到:

P(Ωl)+P(Sj′)≥P(Ωl)+P′(ωl+1)

(17)

4 仿真實(shí)現(xiàn)與分析

為了驗(yàn)證gPUR算法的正確性和性能,我們還需要通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證.為此,我們?cè)O(shè)計(jì)并實(shí)現(xiàn)了兩種不同的對(duì)比算法作為參照,然后對(duì)實(shí)驗(yàn)參數(shù)的選擇和設(shè)置進(jìn)行了簡(jiǎn)單說(shuō)明,最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了比較和定性分析.

4.1 對(duì)比算法

為了評(píng)估本文提出的算法,需要使用一些其他算法作為對(duì)比.但是,由于本文第2節(jié)中提出的問(wèn)題場(chǎng)景不同于現(xiàn)有的研究工作,因此,以往的用戶(hù)招募算法不能直接應(yīng)用在我們的問(wèn)題場(chǎng)景中.為此,基于現(xiàn)有的貪心算法,針對(duì)該場(chǎng)景實(shí)現(xiàn)了兩種不同的用戶(hù)招募算法:MPSU(Maximum Profits of Single User)和MRPC(Maximum Ratio of Profits to Cost).MPSU和MRPC算法被設(shè)計(jì)成基于不同標(biāo)準(zhǔn)的貪心策略而選擇用戶(hù).具體來(lái)講,MPSU算法每次迭代選出一個(gè)用戶(hù),由這個(gè)用戶(hù)單獨(dú)覆蓋的任務(wù)的總收益最大,也即P′(Sj)最大,重復(fù)挑選用戶(hù)的過(guò)程直到總開(kāi)銷(xiāo)超過(guò)預(yù)算或可選用戶(hù)集為空.MRPC算法則是基于0-1背包問(wèn)題[14]的基本思想而設(shè)計(jì),也就是算法每次迭代都選出一個(gè)用戶(hù)使得P(Sj)/Cj值最大,直到總開(kāi)銷(xiāo)超過(guò)預(yù)算或可選用戶(hù)集為空.

4.2 參數(shù)設(shè)置和度量

為了評(píng)估算法的性能,進(jìn)行了一系列仿真實(shí)驗(yàn),這些實(shí)驗(yàn)考慮了4個(gè)不同的參數(shù):移動(dòng)用戶(hù)數(shù)目,每個(gè)用戶(hù)可以處理的感知任務(wù)數(shù)量,每個(gè)用戶(hù)的開(kāi)銷(xiāo),平臺(tái)預(yù)算.

首先,假定模型中共有1000個(gè)感知任務(wù),其中每個(gè)感知任務(wù)的收益從區(qū)間(0,10]內(nèi)隨機(jī)生成.并設(shè)定移動(dòng)用戶(hù)數(shù)目(即m)分別取50,100,150,200,250,預(yù)算Β則分別取200,300,400,500,600.用參數(shù)β來(lái)控制招募用戶(hù)的平均開(kāi)銷(xiāo),每個(gè)用戶(hù)的招募開(kāi)銷(xiāo)從區(qū)間[β,5β]內(nèi)隨機(jī)生成,其中β分別取值2,4,6,8,10.用參數(shù)δ來(lái)控制用戶(hù)可執(zhí)行任務(wù)的平均數(shù)量,每個(gè)用戶(hù)能處理的任務(wù)數(shù)從區(qū)間(0,2δ]隨機(jī)生成,δ分別取值5,10,15,20,25.

在PUR問(wèn)題中,已經(jīng)明確最終目標(biāo)是使得招募用戶(hù)所覆蓋的感知任務(wù)的總收益最大,自然而然地,感知平臺(tái)的總收益是仿真中最重要的度量標(biāo)準(zhǔn).

4.3 仿真結(jié)果與分析

在評(píng)估4.1節(jié)中的三個(gè)算法時(shí),我們分別考慮了如下四個(gè)參數(shù)的變化:移動(dòng)用戶(hù)數(shù)m、預(yù)算Β、用戶(hù)能執(zhí)行的平均任務(wù)數(shù)量δ、每個(gè)用戶(hù)的開(kāi)銷(xiāo)系數(shù)β.使用控制變量法,當(dāng)評(píng)估某一個(gè)參數(shù)下的性能時(shí),固定其他三個(gè)參數(shù),比較三個(gè)算法的總收益.更進(jìn)一步的,為了消除隨機(jī)因素帶來(lái)的影響,針對(duì)同一個(gè)參數(shù)進(jìn)行100次仿真,取平均值作為最后的結(jié)果.仿真結(jié)果如圖1-圖4所示,總體而言,從圖中可以看到,在這三個(gè)算法中,gPUR具有最好的性能表現(xiàn).

圖1 總收益與移動(dòng)用戶(hù)數(shù)關(guān)系(Β=400,δ=10,β=10)Fig.1 Profits vs.number of users (Β=400,δ=10,β=10)

圖2 總收益與預(yù)算關(guān)系(m=200,δ=10,β=10)Fig.2 Profits vs.Budget(m=200,δ=10,β=10)

具體來(lái)講,在圖1中,隨著系統(tǒng)中移動(dòng)用戶(hù)數(shù)量m的增長(zhǎng),平臺(tái)的總收益也隨之增長(zhǎng),這是因?yàn)樵诮o定預(yù)算下,越多的移動(dòng)用戶(hù)帶來(lái)越多的可選方案,平臺(tái)可以從中選擇收益更高的解決方案.正如圖2所示,當(dāng)我們?cè)龃箢A(yù)算B時(shí),平臺(tái)可以招募更多的用戶(hù)來(lái)執(zhí)行感知任務(wù),因而總收益也增大.在圖3中,隨著每個(gè)用戶(hù)能執(zhí)行的任務(wù)數(shù)的變化,總收益呈現(xiàn)小幅度的波動(dòng),且三個(gè)算法都是在δ=10時(shí),取得最大總收益.如圖4表示的是用戶(hù)的招募開(kāi)銷(xiāo)與總收益的關(guān)系,隨著每個(gè)用戶(hù)的招募開(kāi)銷(xiāo)的增大,總收益減小,這是符合常理推斷的:由于用戶(hù)的開(kāi)銷(xiāo)增大,而預(yù)算是固定的,因此平臺(tái)能招募的用戶(hù)數(shù)量必然減小,用戶(hù)覆蓋的感知任務(wù)也就減少,這也就導(dǎo)致總收益的減小.在四個(gè)參數(shù)中,gPUR算法的性能都是最好的,而且,隨著用戶(hù)數(shù)量、預(yù)算的增大,gPUR算法與其他兩個(gè)算法的優(yōu)勢(shì)擴(kuò)大,這說(shuō)明我們的算法具有更優(yōu)越的性能表現(xiàn).這些實(shí)驗(yàn)結(jié)果都驗(yàn)證了前面理論分析的正確性.

圖3 總收益與參數(shù)δ關(guān)系圖4 總收益與參數(shù)β關(guān)系(m=200，B=400，β=10)(m=200，B=400，δ=10)Fig．3 Profitsvs．ParameterδFig．4 Profitsvs．Parameterβ(m=200，B=400，β=10)(m=200，B=400，δ=10)

5 相關(guān)工作

在移動(dòng)群智感知中,大量移動(dòng)用戶(hù)被感知平臺(tái)招募過(guò)來(lái),協(xié)同完成一項(xiàng)復(fù)雜的工作[3].在本文中,我們聚焦于移動(dòng)群智感知中的用戶(hù)招募問(wèn)題.目前已經(jīng)有很多工作在研究這一問(wèn)題,針對(duì)不同場(chǎng)景提出了不同的解決方案[6-13].

從招募預(yù)算的角度,可以將現(xiàn)有的研究分為預(yù)算不受限和預(yù)算受限的用戶(hù)招募模型.

在預(yù)算不受限模型中,招募開(kāi)銷(xiāo)沒(méi)有限定值,優(yōu)化目標(biāo)通常正好是平臺(tái)招募開(kāi)銷(xiāo)的最小化或用戶(hù)總體消耗的最小化.例如文獻(xiàn)[6]使用一個(gè)次模目標(biāo)函數(shù),將移動(dòng)用戶(hù)選擇問(wèn)題形式化為一個(gè)最小成本集合覆蓋問(wèn)題.文獻(xiàn)[7]提出了一種多任務(wù)的用戶(hù)招募框架,將用戶(hù)選擇問(wèn)題轉(zhuǎn)化為最小開(kāi)銷(xiāo)最大流模型.

在預(yù)算受限的場(chǎng)景中,招募用戶(hù)的開(kāi)銷(xiāo)是不能超過(guò)給定預(yù)算的,問(wèn)題優(yōu)化的目標(biāo)一般是任務(wù)數(shù)量的最大化或是感知平臺(tái)的收益最大化,可以采用線(xiàn)性規(guī)劃或近似算法求解[8-12].文獻(xiàn)[8]在招募車(chē)輛時(shí),限定開(kāi)銷(xiāo)不能超過(guò)預(yù)算,尋求車(chē)輛覆蓋區(qū)域的最大化,并形式化為整數(shù)線(xiàn)性規(guī)劃問(wèn)題求解.文獻(xiàn)[9]則限定招募用戶(hù)的有效人數(shù),可以看作是一種開(kāi)銷(xiāo)相等的預(yù)算受限模型,使用0-1整數(shù)規(guī)劃和分治思想分別設(shè)計(jì)了集中式和分布式算法.文獻(xiàn)[10]則使用近似算法求解問(wèn)題,在限定預(yù)算的前提下,最大化招募用戶(hù)覆蓋質(zhì)量,并證明了算法的近似比.文獻(xiàn)[11]在招募用戶(hù)時(shí)考慮了時(shí)間和空間的可用性,研究在預(yù)算受限下的時(shí)空可用性最大化問(wèn)題.

與現(xiàn)有工作不同的是,我們考慮的場(chǎng)景中,用戶(hù)能處理的任務(wù)是確定的.研究聚焦于限定預(yù)算下的用戶(hù)招募問(wèn)題,目標(biāo)在于最大化所有招募用戶(hù)覆蓋的任務(wù)的總收益.模型中的單個(gè)感知任務(wù)可以被多個(gè)移動(dòng)用戶(hù)執(zhí)行,但是它為平臺(tái)帶來(lái)的收益是固定的,這也使得我們的問(wèn)題不同于經(jīng)典的0-1背包問(wèn)題.

6 總 結(jié)

[1] Conti M,Das S K,Bisdikian C,et al.Looking ahead in pervasive computing:Challenges and opportunities in the era of cyber-physical convergence[J].Pervasive and Mobile Computing,2012,8(1):2-21.

[2] Xiong Ying,Shi Dian-xi,Ding Bo,et al.Survey of mobile Sensing[J].Computer Science,2014,41(4):1-8.

[3] Ganti R K,Ye F,Lei H.Mobile crowdsensing:current state and future challenges[J].IEEE CommunicationsMagazine,2011,49(11):32-39.

[4] Cheung M H,Southwell R,Hou F,et al.Distributed time-sensitive task selection in mobile crowdsensing[C].Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing,ACM,2015:157-166.

[5] Du Yang,Huang He,Sun Yu-e,et al.A location-based task assignment mechanism for mobile phone sensing[J].Journal of Computer Research and Development,2014,51(11):2374-2381.

[6] Karaliopoulos M,Telelis O,Koutsopoulos I.User recruitment for mobile crowdsensingover opportunistic networks[C].IEEE Conference on Computer Communications (INFOCOM),2015:2254-2262.

[7] Liu Y,Guo B,Wu W,et al.Poster:Towards a multitask worker recruitment framework for mobile crowdsensing[C].Proceedings of the 14th Annual International Conference on Mobile Systems,Applications,and Services Companion,ACM,2016:51-51.

[8] Hamid S A,Abouzeid H,Hassanein H S,et al.Optimal recruitment of smart vehicles for reputation-aware public sensing[C].IEEE Wireless Communications and Networking Conference (WCNC),IEEE,2014:3160-3165.

[9] Han Y,Luo T,Li D,et al.Competition-based participant recruitment for delay-sensitive crowdsourcing applications in d2d networks[J].IEEE Transactions on Mobile Computing,2016,15(12):2987-2999.

[10] Xiong H,Zhang D,Chen G,et al.Crowdtasker:Maximizing coverage quality in piggyback crowdsensing under budget constraint[C].Pervasive Computing and Communications (PerCom),2015 IEEE International Conference on.IEEE,2015:55-62.

[11] He Z,Cao J,Liu X.Highquality participant recruitment in vehicle-based crowdsourcing using predictable mobility[C].IEEE Conference on Computer Communications (INFOCOM),IEEE,2015:2542-2550.

[12] Liu Y,Li X.Heterogeneous participant recruitment for comprehensive vehicle sensing[J].PloS one,2015,10(9):e0138898.

[13] Wang H,Wang Y,Wang J.A participant recruitment framework for crowdsourcing based software requirement acquisition[C].IEEE 9th International Conference on Global Software Engineering,IEEE,2014:65-73.

[14] Martello S,Pisinger D,Toth P.New trends in exact algorithms for the 0-1 knapsack problem[J].European Journal of Operational Research,2000,123(2):325-332.

[15] Khuller S,Moss A,Naor J S.The budgeted maximum coverage problem[J].Information Processing Letters,1999,70(1):39-45.

[16] Hochbaum D S,Pathria A.Analysis of the greedy approach in problems of maximum k-coverage[J].NavalResearch Logistics,1998,45(6):615-627.

附中文參考文獻(xiàn)：

[2] 熊 英,史殿習(xí),丁 博,等.移動(dòng)群體感知技術(shù)研究[J].計(jì)算機(jī)科學(xué),2014,41(4):1-8.

[5] 杜 揚(yáng),黃 河,孫玉娥,等.地理位置相關(guān)移動(dòng)感知系統(tǒng)任務(wù)分配問(wèn)題研究[J].計(jì)算機(jī)研究與發(fā)展,2014,51(11):2374-2381.