移動群智感知中預(yù)算受限的用戶招募問題研究.pdf

1、隨著智能手機等移動電子設(shè)備的廣泛使用，移動群智感知技術(shù)也得到發(fā)展，應(yīng)用前景廣闊。在移動群智感知中，感知平臺需要招募大量用戶來協(xié)同完成一項包含眾多感知任務(wù)的復(fù)雜工作。如何恰當(dāng)、高效地招募合適的用戶是我們需要解決的首要問題。
　　本文主要研究移動群智感知中預(yù)算受限的用戶招募問題。不同于以往研究，本文中每個感知任務(wù)都是不可再分的，并且可以被多個用戶執(zhí)行，但是單個任務(wù)的收益是固定的，這使得我們的問題不同于0-1背包問題。此外，現(xiàn)有的工作主

2、要研究預(yù)算不受限的招募問題，用戶的開銷是固定的，優(yōu)化目標(biāo)大多是總開銷的最小化;本文中用戶的開銷根據(jù)執(zhí)行任務(wù)的數(shù)量而定，感知平臺的總開銷不能超過給定預(yù)算，同時尋求總收益的最大化。為此，我們針對不同的場景，研究了兩種不同的用戶招募模型，并提出了相應(yīng)的用戶招募解決方案和算法:
　　1.集中式確定型的用戶招募問題。其中，用戶的可執(zhí)行任務(wù)集由自己決定，其開銷則取決于可執(zhí)行任務(wù)數(shù)，感知平臺知曉全部用戶的可執(zhí)行任務(wù)集和開銷。為此，我們對預(yù)算受限

3、的收益最大化用戶招募問題建立數(shù)學(xué)模型，證明了其NP-難解性，提出了一個集中式的貪心算法gPUR來求解該問題，并通過數(shù)學(xué)推導(dǎo)分析了該算法的性能保證，證明了該算法具有常數(shù)近似比。
　　2.機會式概率型的用戶招募問題。在該問題中，由于任務(wù)消息數(shù)據(jù)量大、蜂窩網(wǎng)絡(luò)不可用等原因，集中式招募方案不適用。為此，我們首先設(shè)計了一種基于機會網(wǎng)絡(luò)分發(fā)任務(wù)、利用歷史概率信息招募用戶的通用解決方案OTDURS。然后建立用戶招募模型，并證明了問題的NP-難解

4、性，最后設(shè)計了兩種機會式概率型的用戶招募算法，并分析了算法的計算復(fù)雜度。其中，離線招募算法FUR完全基于歷史概率信息，執(zhí)行貪心迭代，輸出一個離線招募策略。而在線招募算法NUR中，感知平臺利用D2D機會網(wǎng)絡(luò)分發(fā)任務(wù)的同時招募用戶。每次遇見一個新用戶，都基于當(dāng)前相遇用戶的確定信息和其他用戶的歷史概率信息，執(zhí)行招募算法，輸出一個臨時招募策略，并根據(jù)當(dāng)前用戶是否在臨時招募策略中，即時決定是否招募該用戶。
　　我們對上述算法分別進行了大量的