本文關(guān)鍵詞： 移動群智感知 用戶招募 預(yù)算受限 收益最大化 貪心算法 機(jī)會式招募離線算法 在線算法　出處：《中國科學(xué)技術(shù)大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著智能手機(jī)等移動電子設(shè)備的廣泛使用,移動群智感知技術(shù)也得到發(fā)展,應(yīng)用前景廣闊。在移動群智感知中,感知平臺需要招募大量用戶來協(xié)同完成一項包含眾多感知任務(wù)的復(fù)雜工作。如何恰當(dāng)、高效地招募合適的用戶是我們需要解決的首要問題。本文主要研究移動群智感知中預(yù)算受限的用戶招募問題。不同于以往研究,本文中每個感知任務(wù)都是不可再分的,并且可以被多個用戶執(zhí)行,但是單個任務(wù)的收益是固定的,這使得我們的問題不同于0-1背包問題。此外,現(xiàn)有的工作主要研究預(yù)算不受限的招募問題,用戶的開銷是固定的,優(yōu)化目標(biāo)大多是總開銷的最小化;本文中用戶的開銷根據(jù)執(zhí)行任務(wù)的數(shù)量而定,感知平臺的總開銷不能超過給定預(yù)算,同時尋求總收益的最大化。為此,我們針對不同的場景,研究了兩種不同的用戶招募模型,并提出了相應(yīng)的用戶招募解決方案和算法:1.集中式確定型的用戶招募問題。其中,用戶的可執(zhí)行任務(wù)集由自己決定,其開銷則取決于可執(zhí)行任務(wù)數(shù),感知平臺知曉全部用戶的可執(zhí)行任務(wù)集和開銷。為此,我們對預(yù)算受限的收益最大化用戶招募問題建立數(shù)學(xué)模型,證明了其NP-難解性,提出了一個集中式的貪心算法gPUR來求解該問題,并通過數(shù)學(xué)推導(dǎo)分析了該算法的性能保證,證明了該算法具有常數(shù)近似比。2.機(jī)會式概率型的用戶招募問題。在該問題中,由于任務(wù)消息數(shù)據(jù)量大、蜂窩網(wǎng)絡(luò)不可用等原因,集中式招募方案不適用。為此,我們首先設(shè)計了一種基于機(jī)會網(wǎng)絡(luò)分發(fā)任務(wù)、利用歷史概率信息招募用戶的通用解決方案OTDURS。然后建立用戶招募模型,并證明了問題的NP-難解性,最后設(shè)計了兩種機(jī)會式概率型的用戶招募算法,并分析了算法的計算復(fù)雜度。其中,離線招募算法FUR完全基于歷史概率信息,執(zhí)行貪心迭代,輸出一個離線招募策略。而在線招募算法NUR中,感知平臺利用D2D機(jī)會網(wǎng)絡(luò)分發(fā)任務(wù)的同時招募用戶。每次遇見一個新用戶,都基于當(dāng)前相遇用戶的確定信息和其他用戶的歷史概率信息,執(zhí)行招募算法,輸出一個臨時招募策略,并根據(jù)當(dāng)前用戶是否在臨時招募策略中,即時決定是否招募該用戶。我們對上述算法分別進(jìn)行了大量的驗證,并詳細(xì)分析和比較了實驗結(jié)果。結(jié)果表明,我們的算法相比多個參照算法具有更好的性能表現(xiàn)。
[Abstract]:With the wide use of mobile electronic devices such as smart phones, mobile group intelligence perception technology has been developed, and has a broad application prospect. Perception platform needs to recruit a large number of users to cooperate to complete a complex task involving a large number of perceptual tasks. The most important problem we need to solve is to recruit suitable users efficiently. This paper focuses on the problem of user recruitment with budget constraints in mobile swarm intelligence perception, which is different from previous research. Each perceptual task in this article is inseparable and can be performed by multiple users, but the benefits of a single task are fixed, which makes our problem different from the 0-1 knapsack problem. The existing work mainly studies the recruitment problem with unlimited budget. The user's cost is fixed, and the optimization goal is mostly to minimize the total cost. In this paper, the cost of users depends on the number of tasks performed, the total overhead of the aware platform can not exceed a given budget, while seeking to maximize the total revenue. For this reason, we aim at different scenarios. In this paper, two different user recruitment models are studied, and the corresponding solutions and algorithms of user recruitment are proposed: 1. The centralized deterministic user recruitment problem, in which the user's executable task set is determined by himself. The overhead depends on the number of executable tasks, and the aware platform knows the executable task set and the cost of all users. Therefore, we establish a mathematical model for the problem of maximizing the revenue of users with budget constraints. This paper proves its NP-insolvability, proposes a centralized greedy algorithm (gPUR) to solve the problem, and analyzes the performance guarantee of the algorithm by mathematical derivation. It is proved that the algorithm has a constant approximation ratio. 2. The opportunistic probabilistic user recruitment problem. In this problem, due to the large amount of task message data, the cellular network is not available. The centralized recruitment scheme is not applicable. To this end, we first designed an opportunity-based network distribution task. Using historical probability information to recruit users, a universal solution called OTDURS.Then, the model of user recruitment is established, and the NP-intractability of the problem is proved. Finally, two opportunistic probabilistic user recruitment algorithms are designed, and the computational complexity of the algorithm is analyzed. Among them, the offline recruitment algorithm FUR is based entirely on historical probability information and executes greedy iteration. An offline recruitment strategy is outputted. In the online recruitment algorithm NUR, the perceptual platform uses D2D opportunities to distribute tasks at the same time and recruits users at the same time, and meets a new user each time. Based on the information of the current meeting user and the historical probability information of other users, the recruitment algorithm is executed, a temporary recruitment strategy is output, and the current user is in the temporary recruitment strategy according to whether or not the current user is in the temporary recruitment strategy. Whether to recruit the user or not is immediately decided. We have carried out a large number of verification of the above algorithm, and analyzed and compared the experimental results in detail. The results show that. Our algorithm has better performance than multiple reference algorithms.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TN929.5;TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 徐晉暉;石純一;;多Agent系統(tǒng)中的聯(lián)盟形成[J];計算機(jī)科學(xué);1999年04期

2 楊羽,鄢伶俊;多機(jī)異構(gòu)相關(guān)任務(wù)集的調(diào)度優(yōu)化研究[J];計算機(jī)學(xué)報;1993年09期

3 孟新;楊震;;空間科學(xué)探測任務(wù)集同論證平臺[J];科研信息化技術(shù)與應(yīng)用;2011年03期

4 尹翔;蔣建國;夏娜;常傳文;;多任務(wù)多聯(lián)盟并行生成:模型與求解[J];系統(tǒng)工程理論與實踐;2008年04期

5 陳庭貴;肖人彬;;基于內(nèi)部迭代的耦合任務(wù)集求解方法[J];計算機(jī)集成制造系統(tǒng);2008年12期

6 徐敏,王行仁，，馮勤;同構(gòu)型分布式計算機(jī)系統(tǒng)的啟發(fā)式任務(wù)分配算法[J];計算機(jī)學(xué)報;1994年02期

7 陳宇;熊光澤;楊春;;非精確任務(wù)集的容錯單調(diào)比率調(diào)度[J];計算機(jī)科學(xué);2002年01期

8 王濤;劉大昕;;單調(diào)速率任務(wù)分配算法利用率的界限分析[J];計算機(jī)應(yīng)用;2006年09期

9 錢光明;;平滑而快速地插入新任務(wù)[J];湖南文理學(xué)院學(xué)報(自然科學(xué)版);2008年02期

10 李婷;王海瑞;張繼燕;;混合任務(wù)集的層次調(diào)度方案[J];電腦知識與技術(shù);2008年35期

相關(guān)博士學(xué)位論文 前2條

1 趙慶玲;混合關(guān)鍵度CPS系統(tǒng)中的資源共享協(xié)議和設(shè)計優(yōu)化[D];浙江大學(xué);2015年

2 張易;基于區(qū)間劃分的實時系統(tǒng)節(jié)能調(diào)度[D];華中科技大學(xué);2015年

相關(guān)碩士學(xué)位論文 前10條

1 張?zhí)煊?基于TDM的分層實時調(diào)度算法的研究[D];東北大學(xué);2013年

2 趙清偉;多核混合關(guān)鍵度實時系統(tǒng)中任務(wù)劃分及實現(xiàn)[D];華中科技大學(xué);2015年

3 郭會東;移動群智感知中預(yù)算受限的用戶招募問題研究[D];中國科學(xué)技術(shù)大學(xué);2017年

4 姜輝;基于EDF算法的任務(wù)最早插入時間研究[D];湖南師范大學(xué);2012年

5 陳湘華;一種基于EDF的運行時模型研究[D];湖南師范大學(xué);2012年

6 肖柱;多任務(wù)飛行控制系統(tǒng)中調(diào)度算法與可靠性控制研究[D];電子科技大學(xué);2012年

7 錢杰;DVS節(jié)能技術(shù)與EDF調(diào)度結(jié)合的節(jié)能算法[D];浙江大學(xué);2007年

8 李學(xué)輝;異構(gòu)多核系統(tǒng)中面向細(xì)粒度任務(wù)集的調(diào)度算法研究[D];湖南大學(xué);2011年

9 問翠梅;多Agent系統(tǒng)中聯(lián)盟形成問題的研究[D];蘭州大學(xué);2009年

10 劉莉;基于實時Linux的調(diào)度方法研究[D];沈陽工業(yè)大學(xué);2006年

本文編號：1472250