臺灣博碩士論文加值系統

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

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Orienteering Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Research Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.1 Detour Planning Problem . . . . . . . . . . . . . . . . . . . . . . 2
1.3.2 Multi-users Detour Planning Problem . . . . . . . . . . . . . . . 3
1.4 Contributions of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Related Work 5
2.1 Crowdsourcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Crowdsensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Detour Planning Problem 7
3.1 Formulate the Detour Planning Problem . . . . . . . . . . . . . . . . . . 7
3.2 Detour Planning Algorithm: DP . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Approximation Algorithm: DPA . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Multi-users Detour Planning Problem 23
4.1 Formulate the Multi-users Detour Planning Problem . . . . . . . . . . . . 23
4.2 Multi-users Detour Planning Algorithm: MDP . . . . . . . . . . . . . . . 24
4.3 Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5 Conclusion and FutureWork 33
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

[1] C. Bassem and A. Bestavros. Mechanism design for spatio-temporal request satisfaction in mobile networks. Technical report, Boston University, February 2012.
[2] I. Boutsis and V. Kalogeraki. Crowdsourcing under real-time constraints. In Proc. of IEEE International Symposium on Parallel Distributed Processing (IPDPS’13), pages 753–764, Boston, May 2013.
[3] I. Boutsis and V. Kalogeraki. On task assignment for real-time reliable crowdsourcing. In Proc. of IEEE International Conference on Distributed Computing Systems (ICDCS’14), pages 1–10, Madrid, Spain, June 2014.
[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.
[5] Z. Feng, Y. Zhu, Q. Zhang, L. Ni, and A. Vasilakos. Trac: Truthful auction for location-aware collaborative sensing in mobile crowdsourcing. In Proc. of IEEE International Conference on Computer Communications (INFOCOM’14), pages 1231–1239, April 2014.
[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.
[8] B. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics, 34(3):307–318, 1987.
[9] D. Hasenfratz, O. Saukh, S. Sturzenegger, and L. Thiele. Participatory air pollution monitoring using smartphones. In Proc. of International Workshop on Mobile Sensing (in conjunction with ACM/IEEE IPSN), Beijing, China, April 2012.
[10] T. Hou, J. Lin, C. Hsu, Y. Chung, and C. King. OCI: A middleware framework for optimal context inference on smartphones. Technical report, 2013. http://nmsl.cs.nthu.edu.tw/dropbox/oci.pdf.
[11] T.-F. Hou. Optimizing mobile middleware for coordinated sensor activations. Master’s thesis, National Tsing Hua University, Taiwan, 2014.
[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.
[13] K. Lai and M. Goemans. The knapsack problem and fully polynomial time approximation schemes (FPTAS). http://math.mit.edu/˜goemans/18434S06/knapsack-katherine.pdf, 2006.
[14] Z. Li, H. Shen, G. Liu, and J. Li. SOS: A Distributed Mobile Q&A System Based on Social Networks. In Proc. of the IEEE International Conference on Distributed Computing Systems (ICDCS’12), pages 627–636, Macau, China, June 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.
[16] C. Liao and C. Hsu. A detour planning algorithm in crowdsourcing systems for multimedia content gathering. In Proc. of ACM International Workshop on Mobile Video (MoVid’13), pages 55–60, Oslo, Norway, February 2013.
[17] E. Martins and M. Pascoal. A new implementation of Yen’s ranking loopless paths algorithm. 4OR: A Quarterly Journal of Operations Research, 1(2):121–133, June 2003.
[18] R. Montemanni., D. Weyland, and L. Gambardella. An enhanced ant colony system for the team orienteering problem with time windows. In Proc. of IEEE International Symposium on Science and Society (ISCCS’11), pages 381–384, Kota Kinabalu, Malaysia, July 2011.
[19] G. Righini and M. Salani. Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers and Operations Research, 36(4):1191–1203, April 2009.
[20] Roamler, 2011. http://www.roamler.com/services.aspx.
[21] M. Schilde, K. F. Doerner, R. F. Hartl, and G. Kiechle. Metaheuristics for the biobjective orienteering problem. Swarm Intelligence, 3(3):179–201, September 2009.
[22] W. Sherchan, P. Jayaraman, S. Krishnaswamy, A. Zaslavsky, S. Loke, and A. Sinha. Using on-the-move mining for mobile crowdsensing. In Proc. of IEEE International Conference on Mobile Data Management (MDM’12), pages 115–124, Bengaluru, Karnataka, India, July 2013.
[23] H. Shibo, S. Hoon, Z. Junshan, and C. Jiming. Toward optimal allocation of location dependent tasks in crowdsensing. In Proc. of IEEE International Conference on Computer Communications (INFOCOM’14), pages 745–753, Toronto, Canada, April 2014.
[24] Taipei travel net, October 2012. http://www.taipeitravel.net/en/.
[25] M. Talasila, R. Curtmola, and C. Borcea. Improving location reliability in crowd sensed data with minimal efforts. In Proc. of Joint IFIP/IEEE Wireless and Mobile Networking Conference (WMNC’13), pages 1–8, Dubai, United Arab Emirates, April 2013.
[26] Vancouver landmarks, October 2012. http://www.hotels.com/de169712-la/all-landmarks-in-vancouver-canada/.
[27] P. Vansteenwegena, W. Souffriaua, G. Berghe, and D. Oudheusden. A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research, 196(1):118–127, July 2009.
[28] P. Vansteenwegena, W. Souffriaua, and D. Oudheusden. The orienteering problem: A survey. European Journal of Operational Research, 209(1):1–10, February 2011.
[29] Y. Wang, D. Burgener, M. Flores, A. Kuzmanovic, and C. Huang. Towards streetlevel client-independent ip geolocation. In Proc. of USENIX Conference on Networked Systems Design and Implementation (NSDI’11), pages 365–379, 2011.
[30] B. Wong, I. Stoyanov, and E. Sirer. Octant: A comprhensive framework for the geolocalization of internet hosts. In Proc. of USENIX Conference on Networked Systems Design and Implementation (NSDI’07), pages 313–326, 2007.
[31] Y. Xiao, P. Simoens, P. Pillai, K. Ha, and M. Satyanarayanan. Lowering the barriers to large-scale mobile crowdsensing. In Proc. of ACM International Workshop on Mobile Computing Systems and Applications (HotMobile’13), pages 9:1–9:6, Jekyll Island, Georgia, 2013.
[32] T. Yan, B. Hoh, D. Ganesan, K. Tracton, T. Iwuchukwu, and J.-S. Lee. Crowdpark: A crowdsourcing-based parking reservation system for mobile phones. Technical report, University of Massachusetts Amherst, 2011.
[33] D. Yang, G. Xue, X. Fang, and J. Tang. Crowdsourcing to smartphones: Incentive mechanism design for mobile phone sensing. In Proc. of ACM International Conference on Mobile Computing and Networking (Mobicom’12), pages 173–184, New York, 2012.
[34] M. Yuen, L. Chen, and I. King. A survey of human computations systems. In Proc.of IEEE Symposium on Social Computing Applications (SCA’09), pages 723–728, Vancouver, Canada, October 2009.
[35] M. Yuen, I. King, and K. Leung. A survey of crowdsourcing systems. In Proc. of IEEE International Conference on Social Computing (SocialCom’11), pages 766–773, Boston, MA, October 2011.
[36] M. Yuen, I. King, and K. Leung. Task matching in crowdsourcing. In Proc. of IEEE International Conference on Internet of things, and Cyber, Physical and Social Computing(iThings/CPSCom’11), pages 409–412, Dalian, China, October 2011.