研究行動群眾感知系統下的繞行規劃問題

群眾感知系統是近年流行的一種工作外包的平台，此系統將感測或多媒體工作外包給有行動裝置的工人。在群眾感知系統中，工人使用智慧型手機來工作，這些智慧型手機具備了能夠執行感測以及多媒體工作的能力，例如偵測噪音或拍照。我們為了有效的分配感測以及多媒體工作給工人而提出了一個群眾感知系統，並且我們只專注於時空相關的工作，這種工作必須在特定的地點以及時間來被執行。每個工人會提供他的目的地以及預計到達的時間給我們的系統，並且這些工人為了最大化利潤不介意遵從我們的繞行規劃路線來執行工作。一旦工人上傳相關的資訊道系統上，工人將會收到各自的繞行規劃路線，而每條繞行規劃路線都是由一群工作組成並且有特定的順序讓工人去遵循。工人若是依循繞行規劃路線執行工作，那他將會收到他所能獲得的最大的利潤。我們稱上述的問題為繞行規劃問題，並且又提出一個更複雜的多人繞行規劃問題。這兩個問題的差別只在於繞行規劃問題每次運算繞行規劃路線時只考慮一個工人。在本篇論文中，我們提出了繞行規劃演算法(DP) 以及多人繞行規劃演算法(MDP) 去解決我們提出的兩個問題。我們使用真實資料去驅動模擬器，其模擬結果也顯示我們演算法的可行性以及效率。在未來我們將會實作此系統，以及解決其中多個困難的挑戰。

關鍵字

群眾感知；演算法

並列摘要

Crowdsensing is a popular paradigm that outsources sensory/multimedia tasks to mobile workers. In the crowdsensing systems, workers perform diverse tasks such as detecting sensory data and taking pictures by employing (using) their smartphones, which are equipped with sensing and multimedia functions. We provide a crowdsensing system to efficiently delegate sensory/multimedia tasks to mobile workers, and we focus on spatial-temporal tasks that must be conducted at specific locations and time. Each worker supplies his/her destination with a deadline to our system and does not mind taking detour paths to maximize profits. Once workers submit their profiles to our system, they will receive detour paths, which consist of tasks in particular orders. Workers execute tasks by following their detour paths and receive maximal profits. We formulate this problem as a detour planning problem, and the advanced problem is multi-users detour planning problem. The difference between these two problems is that the detour planning problem just considers a worker at a time. In this thesis, we develop a detour planning algorithm (DP) and a multi-users detour planning algorithm (MDP) to solve problems respectively. We simulate the extensive trace-driven scenarios and demonstrate the effectiveness and efficiency of our algorithms. Developing a working prototype on Android OS and addressing other challenging aspects of the considered systems are our future tasks.

並列關鍵字

Crowdsensing ； Algorithm

參考文獻

[4] G. Cardone, L. Foschini, P. Bellavista, A. Corradi, C. Borcea, M. Talasila, and R. Curtmola. Fostering participaction in smart cities: a geo-social crowdsensing platform. IEEE Communications Magazine, 51(6):112–119, June 2013.

[6] flickr, October 2012. http://www.flickr.com/.

[7] R. Ganti, F. Ye, and H. Lei. Mobile crowdsensing: Current state and future challenges. IEEE Communication Magazine, 49(11):32–39, November 2011.

[12] L. Jaimes, I. Laurens, and M. Labrador. A location-based incentive mechanism for participatory sensing systems with budget constraints. In Proc. of IEEE International Conference on Pervasive Computing and Communications (PerCom’12), pages 103–108, March 2012.

[15] C. Liao, T. Hou, T. Lin, Y. Cheng, A. Erbad, C. Hsu, and N. Venkatasubramanian. SAIS: Smartphone Augmented Infrastructure Sensing for Public Safety and Sustainability in Smart Cities. In Proc. of ACM International Workshop on Emerging Multimedia Applications and Services for Smart Cities (EMASC’14), pages 3–8, Orlando, FL, November 2014.

國際替代計量

研究行動群眾感知系統下的繞行規劃問題

全文下載

主題瀏覽