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

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

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

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

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