隨著行動裝置科技迅速的發展，手機配備了各種感應器並且擁有強大的運算能力，也因為這樣可以隨時得知使用者與其身邊的各種情況的資訊。然而大部分的時間手機和這些感測器都是處於空閒狀態，因此有人提出了行動群眾感測(Mobile Crowd Sensing and Computing, MCSC)這個技術，利用使用者無所不在和閒置手機感測器來感測周遭現實世界中的資料，並且及時的回覆使用者對這些資料的查詢。由於在處理MCSC查詢要求的時候，會先判斷目標物時空特性，然後形成查詢條件並且進行任務分配(Task Assignment)，找到適當的使用者群進行感測並整合回覆資訊成為結果。而這樣子的查詢處理效率顯然不易提升，因此我們提出利用快取來提升群眾感測效能的方法，並設計了幾個資料取代策略，讓整個快取空間可以更加有效的利用。由於行動群眾感測的資料是現實世界中的資料，因此這些資料也可能會隨著時間發生變動，讓快取中的資料失效。為了確保快取的有效性，我們設計了一個機制去動態調整資料有效時間以及判斷快取資料值是否需要重測的恰當機率，這個機制不但可以解決資料值的變化問題，更可以提高快取命中率。
由於快取大小有限，只能保存近期曾經查詢過的資料，因此對於久未查詢或新資料會發生miss的情況。我們另外設計了預測式快取的機制，利用資料和查詢特性分析出這筆資料是否具有足夠價值進行預測式查詢，並將感測所得到結果儲存在預測式快取中，以彌補一般快取的不足。
我們利用MongoDB在Hadoop叢集上實作我們所提出的快取和查詢處理機制，並進行多項實驗。實驗結果證實我們所提出的機制可以有效提升快取命中率和查詢效能，有效時間維護與重測機率調整機制可以有效減少不必要的重複查詢，加入預測式快取之後的命中率會提高2~10%，隨查詢特性和預測式快取占了整個快取空間的大小而有差異，平均而言一般式和預測式快取所占空間比以6:4為最佳。
由於快取大小有限，只能保存近期曾經查詢過的資料，因此對於久未查詢或新資料會發生miss的情況。我們另外設計了預測式快取的機制，利用資料和查詢特性分析出這筆資料是否具有足夠價值進行預測式查詢，並將感測所得到結果儲存在預測式快取中，以彌補一般快取的不足。
我們利用MongoDB在Hadoop叢集上實作我們所提出的快取和查詢處理機制，並進行多項實驗。實驗結果證實我們所提出的機制可以有效提升快取命中率和查詢效能，有效時間維護與重測機率調整機制可以有效減少不必要的重複查詢，加入預測式快取之後的命中率會提高2~10%，隨查詢特性和預測式快取占了整個快取空間的大小而有差異，平均而言一般式和預測式快取所占空間比以6:4為最佳。

With the rapid development of mobile device technology, mobile phones are equipped with a variety of sensors and have powerful computing power, and because of this, you can always know the information of users and their various situations. However, most of the time mobile phones and these sensors are idle, so some people have proposed Mobile Crowd Sensing and Computing (MCSC) technology, which uses users' ubiquitous and idle mobile phone sensors to sense. The data in the real world is around, and the user's query of these materials is promptly answered. Since the time and space characteristics of the target are determined first when the MCSC query request is processed, then the query condition is formed and Task Assignment is performed, and an appropriate user group is found to sense and integrate the reply information to become a result. The efficiency of such query processing is obviously not easy to improve. Therefore, we propose a method to improve the sensing performance of the masses by using cache, and design several data replacement strategies to make the entire cache space more efficient. Since the data sensed by the action masses is data in the real world, these materials may also change over time, invalidating the data in the cache. In order to ensure the effectiveness of the cache, we have designed a mechanism to dynamically adjust the effective time of the data and determine whether the cached data value needs to be retested. This mechanism can not only solve the problem of data value changes, but also improve the cache hit. rate.
Due to the limited size of the cache, only the data that has been queried recently can be saved, so there will be a miss for a long time without querying or new data. We also designed a predictive cache mechanism, using data and query characteristics to analyze whether the data has sufficient value for predictive query, and store the results of the sensing in the predictive cache to compensate for the general cache. Insufficient.
We used MongoDB to implement our proposed cache and query processing mechanism on the Hadoop cluster and conducted a number of experiments. The experimental results confirm that the proposed mechanism can effectively improve the cache hit rate and query performance. The effective time maintenance and retest probability adjustment mechanism can effectively reduce unnecessary repeated queries. The hit rate after adding the predictive cache will increase by 2~. 10%, with the query characteristics and predictive cache take up the size of the entire cache space, on average, the ratio of the general and predictive cache to 6:4 is the best.
Keyword: Resensing probability, Valid Time, Caching Replacement Policy, Predictive Caching

致謝 i
摘要 ii
Abstract iii
目錄 v
圖目錄 vii
表目錄 x
第1章 緒論 1
1.1研究背景與動機 1
1.2研究目的與方法 1
1.3研究成果 2
1.4論文架構 2
第2章 相關研究與技術 3
2.1 行動群眾感測與計算(Mobile Crowd sensing & computing) 3
2.2 行動群眾感測的查詢處理(Query Processing for Mobile Crowd Sensing) 5
2.3 行動快取(Mobile Caching) 6
2.4 預測式快取(Predictive caching ) 7
2.5 Hadoop 8
2.6 Spark 9
2.7 MongoDB 11
第3章 整體系統架構與研究議題 13
3.1整體架構圖 13
3.2系統架構與研究議題 14
3.3查詢處理與快取管理子系統架構與研究議題 15
第4章 快取管理系統與策略 17
4.1 架構圖 17
4.2問題定義 19
4.3解決策略與演算法 20
4.3.1 LRU Based Policy 20
4.3.2 Popularity Based Policy 21
4.3.3 Rareness Based Policy(稀有度) 21
4.4快取更新與重感(Resensing Probability)策略 22
第5章 預測式快取管理 25
5.1架構圖 25
5.2問題定義 26
5.3解決策略與演算法 27
第6章 系統實作與效能評估 29
6.1實驗環境 29
6.2測試資料 29
6.3實驗結果 31
6.3.1 快取大小命中率及反應時間實驗 31
6.3.2 重複關鍵字查詢比例之實驗 35
6.3.3預測式快取之實驗 36
6.4系統效能總結 51
第7章 結論與未來工作 53
7.1結論 53
7.2未來工作 54
參考文獻 55

[1]He Li, Kaoru Ota, Mianxiong Dong and Minyi Guo, "Mobile Crowdsensing in Software Defined Opportunistic Networks," in IEEE Communications Magazine, vol. 55, no. 6, pp. 140-145, June 2017.
[2]Huadong Ma, Dong Zhao, and Peiyan Yuan "Opportunities in mobile crowd sensing," in IEEE Communications Magazine, vol. 52, no. 8, pp. 29-35, Aug. 2014.
[3]Bin Guo,Zhu Wang, Yu Wang, Neil Y.Yen, Runhe Huang and Xingshe Zhou, "Mobile Crowd Sensing and Computing: The Review of an Emerging Human-Powered Sensing Paradigm," ACM Comput. Surv., vol. 48, no. 1, pp. 1-31, 2015
[4]Marco Zappatore, Antonella Longo and Mario A. Bochicchio, "Mobile Crowd-Sensing : a novel Technological Enabler for Teaching Acoustics," , Didattica Informatica 30ª edizione (DIDAMATICA 2016), 19-21, Udine, Italia,2006
[5]Charith Perera, Arkady Zaslavsky ,Peter Christen, Michael Compton and Dimitrios Georgakopoulos, "Context-Aware Sensor Search, Selection and Ranking Model for Internet of Things Middleware," 2013 IEEE 14th International Conference on Mobile Data Management, Milan, 2013, pp. 314-322.
[6]Manoop Talasila, Reza Curtmola and Cristian Borcea, "Improving location reliability in crowd sensed data with minimal efforts," 6th Joint IFIP Wireless and Mobile Networking Conference (WMNC), Dubai, 2013, pp. 1-8.
[7]Bin Guo, Zhiwen.Yu, Xingshe. Zhou and Daqing Zhang, "From participatory sensing to Mobile Crowd Sensing," 2014 IEEE International Conference on Pervasive Computing and Communication Workshops (PERCOM WORKSHOPS), Budapest, 2014, pp. 593-598.
[8]Layla Pournajaf, Li Xiong, Vaidy Sunderam and Slawomir Goryczka, "Spatial Task Assignment for Crowd Sensing with Cloaked Locations," 2014 IEEE 15th International Conference on Mobile Data Management, Brisbane, QLD, 2014, pp. 73-82.
[9]DaoJing He, Sammy Chan, and Mohsen Guizani, "User privacy and data trustworthiness in mobile crowd sensing," in IEEE Wireless Communications, vol. 22, no. 1, pp. 28-34, February 2015.
[10]Jing Li and Jianhua Wang, "A New Architecture Model of Mobile Database Based on Agent," 2009 First International Workshop on Database Technology and Applications, Wuhan, Hubei, 2009, pp. 341-344.
[11]Chu Yan, Zhang Jianpei,and Zhao Chunhui, "Data Cache Strategy Based on Colony Algorithm in Mobile Computing Environment," 2009 Fourth International Conference on Internet Computing for Science and Engineering, Harbin, 2009, pp. 235-238.
[12]Sachin R, Desai Hariram K. Chavan and D. K. Chitre , "Location Based Services Cache Replacement Policy for mobile environment," 2013 International Conference on Advances in Technology and Engineering (ICATE), Mumbai, 2013, pp. 1-6.
[13]Efstratios Rappos and Stephan Robert , "Predictive Caching in Computer Grids," 2013 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, Delft, 2013, pp. 188-189.
[14]Sourav Dutta, Ankur Narang, Souvik Bhattacherjee, Ananda S. Das and Dilip Krishnaswamy, "Predictive Caching Framework for Mobile Wireless Networks," 2015 16th IEEE International Conference on Mobile Data Management, Pittsburgh, PA, 2015, pp. 179-184.
[15]J. Dean and S. Ghemawat, "MapReduce: simplified data processing on large clusters," presented at the Proceedings of the 6th conference on Symposium on Operating Systems Design & Implementation - Volume 6, San Francisco, CA, 2004.
[16]Apache HDFS, http://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/HdfsDesign.html
[17]許國宏， "基於 Spark 架構上之漸進式循序樣式探勘".碩士論文，國立東華大學，花蓮，台灣，2017
[18]The Apache Software Foundation, Apache Spark., https://spark.apache.org
[19]Python+Spark 2.0+Hadoop機器學習與大數據分析實戰, http://pythonsparkhadoop.blogspot.com/
[20]謝祥議，"在Docker上以MongoDB實作雲端半導體測試資料庫系統”，東海大學，台中，台灣，2015
[21]黃珣，"植基於YCSB系統之叢集資料庫效能分析"，國立中山大學，高雄，台灣，2012
[22]吳秀陽(2015)。支援行動感知系統現實世界即時資訊服務之巨量資料動態粒度處理及主動式樣式探勘技術。行政院科技部專題研究計(104WFA1150040)
[23]Antonin Guttman, "R-trees: a dynamic index structure for spatial searching," presented at the Proceedings of the 1984 ACM SIGMOD international conference on Management of data, Boston, Massachusetts, 1984.
[24]Cache replacement policies,WIKIPEDIA, https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU
[25]齊夫定律 維基百科，自由的百科全書,https://zh.wikipedia.org/wiki/%E9%BD%8A%E5%A4%AB%E5%AE%9A%E5%BE%8B
[26]帕雷托分布 維基百科，自由的百科全書 https://zh.wikipedia.org/wiki/%E5%B8%95%E7%B4%AF%E6%89%98%E5%88%86%E5%B8%83