臺灣博碩士論文加值系統

隨著無線網路技術的快速發展，車載隨意網路（Vehicular Ad Hoc Network, VANET）的技術漸趨成熟，同時雲端運算技術（Cloud Computing）亦成為近來熱門趨勢，透過車載網路技術與雲端運算的結合，可增進各類車輛應用的效能及可用性。然而，在車載隨意網路中，由於車輛的高移動性，將產生如拓樸頻繁改變、IP位址重新配置、連線頻繁中斷等諸多挑戰，使得整體服務效能下降。本文透過隱藏式馬可夫模型（Hidden Markov Model, HMM）分析行動用戶的移動軌跡，並考量車輛的高移動性，提出一適用於都會環境中的行動預測機制，利用雲端進行預測程序並進行連線資源預先配置，藉此降低行車之間連線頻繁中斷所造成的影響，並改善行動用戶透過基礎建設取得雲端服務時的處理效率與服務品質，同時減少不必要的連線重設。透過模擬驗證本文所提出之行動預測機制對於減少連線重設次數、換手次數、換手乒乓效應、平均封包傳輸延遲時間、封包抵達率以及控制成本消耗上確實有良好的表現。

With the rapid development of Vehicular Ad Hoc Network (VANET) technologies, variety of applications and services become available. To enhance the availability, include data processing, storage, and computing capabilities can be improved by next generation networking technologies which cloud computing. However, due to the high mobility of vehicles, changing network topology, address migration, and frequent connection interruption, the overall service performance degradation. Therefore, knowing the future location of VANET users is helpful to reduce the impact of frequent connection interruption. The proposed mobility prediction scheme uses Hidden Markov Model (HMM) to analyze the movement trajectory of mobile users, and predict future location of VANET users in urban environment. Through the mobility prediction, the cloud assists connection pre-configuration and resources reservation. As shown in simulation results, the proposed mobility prediction scheme can decrease the number of reconnection and handover, shorten the average end-to-end delay time, increase packet delivery rate, reduce signaling overhead, and reduce the impact of Ping-Pong effect. Consequently, by reducing the number of unnecessary reconnection, the performance of cloud services delivery is apparently improved.

第1章 緒論 1
1.1 研究動機 2
1.2問題描述 2
1.3研究目標 2
1.4論文架構 3
第2章 相關研究 4
2.1 VANET 4
2.2 雲端運算 4
2.3 行動預測技術 5
2.3.1 行動預測背景 5
2.3.2 行動預測技術分類 6
2.3.3 行動預測機制 7
2.4 適用於資料遞送之路由協定 17
2.4.1 AOMDV 17
2.4.2 AODV+ 18
2.5 隱藏式馬可夫模型（HMM） 19
2.5.1 HMM模型概述 19
2.5.2 HMM模型元素定義 20
第3章 研究方法 22
3.1 系統架構 22
3.2 方法流程 25
3.2.1 訊息交遞流程 25
3.3 The Proposed Mobility Prediction Scheme 31
3.3.1 Mobility Model與Mobile Trace 31
3.3.2 預測模型元素定義 33
3.3.3 預測模型建立 34
3.3.4 Mobility Prediction in HMM 36
第4章 效能分析 41
4.1 模擬環境與參數設定 41
4.1.1 行動預測程序模擬 41
4.1.2 網路效能模擬 43
4.2 效能測量項目定義 45
4.3 行動預測準確率實驗 46
4.3.1 不同車速下的預測準確率 46
4.3.2 不同模擬時間下的預測準確率 47
4.3.3 轉彎次數對預測準確率的影響 47
4.3.4 轉彎方向與未來AP的預測準確率 48
4.4 連線重設與換手次數實驗 50
4.4.1 不同車速下的連線重設次數 50
4.4.2 不同模擬時間下的連線重設次數 51
4.4.3 不同車速下的換手次數 52
4.5 資料傳遞平均延遲時間實驗 53
4.5.1 不同車速下的平均延遲時間 53
4.5.2 不同Traffic Load下的平均延遲時間 54
4.5.3 預測方法與真實表現之平均延遲時間比較 58
4.6 封包抵達率實驗 59
4.6.1 不同車速下的封包抵達率表現 59
4.6.2 不同Traffic Load下的封包抵達率 60
4.7 控制訊息成本實驗 62
第5章 結論 64
5.1論文貢獻 64
5.2未來工作 64
參考文獻 66

[1]T. Yasser, et.al, “Vehicle Ad Hoc Networks-Applications and Related Technical Issues,” IEEE Communications Surveys and Tutorials Magazine, Vol. 10, No. 3, pp. 74-88, 2008.
[2]B. Abderrahim, B. Saman, and A. Chadi, “An Efficient Routing Protocol for Connecting Vehicular Networks to the Internet,” IEEE Journal Selected Areas in Communications, Vol. 29, No. 3, pp. 559-570, 2011.
[3]J. Blum, A. Eskandarian, and L. Hoffmman, “Challenges of Inter-Vehicle Ad hoc Networks,” IEEE Transactions on Intelligent Transportation Systems, Vol. 5, No. 4, pp. 347-351, Dec. 2004.
[4]M. L. Sichitiu and M. Kihl, “Inter-Vehicle Communication Systems: a Survey,” IEEE Communications Surveys and Tutorials Magazine, Vol. 10, No. 2, pp. 88-105, 2008.
[5]H. Moustafa and Y. Zhang, “Vehicular Networks-Techniques, Standards, and Applications,” 2009.
[6]Cloud Computing, http://searchcloudcomputing.techtarget.com/sDefinition.html/, Nov. 2009.
[7]ZD net, “Google to Go Carbon Neutral by 2008,” http://news.zdnet.co.uk/internet.htm/, Jun. 2007.
[8]B. S. Belz, et.al, “Intelligent Brokering of Tourism Services for Mobile Users,” Proceedings of Federation on Information Technology in Tourism, Jan. 2002.
[9]D. Ashbrook and T. Starner, “Learning Significant Locations and Predicting User Movement with GPS,” Proceedings of Wearable Computers, pp. 101-108, Oct. 2002.
[10]N. Marmasse and C. Schmandt, “A User-Centered Location Model,” Personal and Ubiquitous Computing, Vol. 6, pp. 318-321, Dec. 2002.
[11]N. Samaan, “A Mobility Prediction Architecture Based on Contextual Knowledge and Spatial Conceptual Maps,” IEEE Transactions on Mobile Computing, Vol. 4, pp. 537-551, 2005.
[12]M. S. Sricharan, V. Vaidehi, and P. P. Arun, “An Activity based Mobility Prediction Strategy for Next Generation Wireless Networks,” IFIP International Conference on Wireless and Optical Communications Networks, pp. 1-5, Aug. 2006.
[13]P. S. Prasad, et.al, “A Generic Framework for Mobility Prediction and Resource Utilization in Wireless Networks,” IEEE International Conference on Communication Systems and Networks, pp. 1-10, Jan. 2010.
[14]鍾享材, “A Light-Weight Moving Preferences Based Dynamic Location Management Scheme Using Road Map and GPS,” 中央大學資訊工程研究所碩士論文, 2004.
[15]M. H. Khaledi, et al. “Mobility Aware Distributed Topology Control in Mobile Ad-Hoc Networks Using Mobility Pattern Matching,” IEEE International Conference on Wireless and Mobile Computing, 2009.
[16]Y. Yuan, et.al, “A Novel Mobility Prediction Mechanism in Heterogeneous Networks,” IEEE International Conference on Communications and Mobile Computing (CMC), pp. 536-540, Apr. 2010.
[17]P. S. Prasad, et.al, “Mobility Prediction for Wireless Network Resource Management,” IEEE Southeastern Symposium on System Theory, pp. 98-102, Mar. 2009.
[18]G.P. Pollini and C. Lin, “A Profile-based Location Strategy and Its Performance,” IEEE Journal on Selected Areas in Communications, Vol. 15, pp. 1415-1424, Oct. 1997.
[19]M. H. Jin, E. H. Kuang and J. T. Horng, “Location Query based on Moving Behavior,” International Conference on Computer Communications and Networks, pp. 268-273, Oct. 2002.
[20]H. K. Wu, et.al, “Personal Paging Area Design based on Mobile's Moving Behaviors,” Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 1, pp. 21-30, Apr. 2001.
[21]W. S. Soh and H. S. Kim, “QoS Provisioning in Cellular Networks based on Mobility Prediction Techniques,” IEEE Communications Magazine, pp. 86-92, Jan. 2003.
[22]W. S. Soh and H. S. Kim, “Dynamic Bandwidth Reservation in Cellular Networks Using Road Topology Based Mobility Predictions,” IEEE International Conference, Mar. 2004.
[23]J Zhao, “VADD: Vehicle-assisted Data Delivery in Vehicular Ad Hoc Networks,” IEEE Transactions on Vehicular Technology, 2008.
[24]H. Ghazale et.al, “Application of Mobility Prediction in Wireless Networks Using Markov Renewal Theory,” 2009.
[25]S. M. Mousavi, et.al, “Mobility Aware Distributed Topology Control in Mobile Ad-Hoc Networks with Model Based Adaptive Mobility Prediction,” IEEE International Conference on Wireless and Mobile Computing, pp. 86-86, Oct. 2007.
[26]Z. Mir, et.al, “Mobility Aware Distributed Topology Control for Mobile Multi-hop Wireless Networks,” Springer Lecture Notes in Computer Science, pp. 257-266, 2006.
[27]D. Son, A. Helmy, B. Krishnamachari, “The Effect of Mobility-induced Location Errors on Geographic Routing in Mobile Ad Hoc Sensor Networks: Analysis and Improvement Using Mobility Prediction,” IEEE Transactions on Mobile Computing, Vol. 3, No. 3, pp. 233-245, Aug. 2004.
[28]W. Su, et.al, “Mobility Prediction and Routing in Ad hoc Wireless Networks,” International Journal of Network Management, Vol. 11, No. 1, pp.3-30, 2001.
[29]F. Bai, et.al, “The Important Framework for Analyzing the Impact of Mobility on Performance of Routing Protocols for Adhoc Networks,” Elsevier Journal of Ad Hoc Networks, pp. 383-403, 2003.
[30]T. Camp, et.al, “A Survey of Mobility Models for Ad Hoc Network Research,” Wireless Communication and Mobile Computing, Vol. 2, No. 5, pp. 483-502, 2002.
[31]S. M. Mousavi, et.al, “MobiSim: A Framework for Simulation of Mobility Models in Mobile Ad-Hoc Networks,” IEEE international Conference on Wireless and Mobile Computing, Oct. 2007.
[32]“MATLAB - The Language Of Technical Computing,” http://www.mathworks.com/ products /matlab/
[33]Y. L. Tang, “Dividing Sensitive Ranges based Mobility Prediction Algorithm in Wireless Networks,” 2010.
[34]M. Chegin, et.al, “Optimized Routing based on Mobility Prediction in Wireless Mobile Adhoc Networks for Urban Area,” IEEE International Conference on Information Technology, pp. 390-395, Apr. 2008.
[35]IEEE 802.21 (Media Independent Handover Services), http://www.ieee802.org/21/
[36]S. Bellahsene and L. Kloul, “A New Markov-Based Mobility Prediction Algorithm for Mobile Networks,” Computer Performance Engineering, Vol. 6342, pp. 37-50, 2010.
[37]S. Bo and L. Yun, “Movement Prediction Model Based on HMM and Simulations,” Journal of System Simulation, Vol. 19, No. 18, 2007.
[38]徐振煒, “以隱藏式馬克夫模型預測行動通訊使用者的移動樣式,” 逢甲大學資訊電機工程研究所碩士論文, 2009.
[39]M. K. Marina and S. R. Das, “On-Demand Ad hoc Multi-Path Distance Vector Routing Protocol,” Proceedings of IEEE International Conference, 2001.
[40]A. Hamidian, “Performance of Internet Access Solutions in Mobile Ad Hoc Networks,” 2005.
[41]C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing,” Network Working Group, RFC 3561, Jul. 2003.
[42]R. Durbin, et.al, “Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids,” Cambridge University Press, 1999.
[43]L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition,” Proceedings of the IEEE, Vol.77, No. 2, pp. 257-286, Feb. 1989.
[44]N. Shokhirev, “Hidden Markov Models,” http://www.shokhirev.com/nikolai/abc/alg/ hmm /hmm.html/, 2010.
[45]F. Bai, N. Sadagopan, and A. Helmy, “IMPORTANT: a Framework to Systematically Analyze the Impact of Mobility on Performance of Routing Protocols for Ad Hoc Networks,” Proceedings of IEEE Information Communications Conference, Vol. 2, pp. 825-835, Apr. 2003.
[46]W. J. Hsu and A. Helmy, “MobiLib: Community-wide Library of Mobility and Wireless Networks Measurements (Investigating User Behavior in Wireless Environments),” http://nile.cise.ufl.edu/MobiLib, Aug. 2005.
[47]G. D. Forney, “The Viterbi Algorithm,” Proceedings of the IEEE, Vol. 61, No.3, pp.268-278, Mar. 1973.
[48]The Network Simulator (NS-2), http://www.isi.edu/nsnam/ns, release 2.1b9a, Jul. 2002.