臺灣博碩士論文加值系統

近年來由於行動裝置的普及化，使得以空間為基礎上的服務越來越多元，其中的適地性服務往往會使用到相關最短路徑查詢方法，例如路況導航。然而地圖資料越來越龐大，在計算能力以及記憶體容量受限的行動裝置上，如何提供有效率的最短路徑查詢為一個值得討論的議題。在無線行動環境下，資料廣播是一個可以解決上述問題的方法，在這個方法底下有兩項效能的指標：查詢經歷時間(Access Latency)及聽取時間(Tuning Time)。從客戶端在開始查詢到結束查詢中間的這段時間稱為查詢經歷時間；而聽取時間則是實際擷取資料廣播頻道上的資料所花的時間。伺服端主要提供地圖圖資於廣播頻道中，而使用者端則依照廣播內容自行接收相關資料。本論文之研究在探討伺服端如何有效處理圖資並進行不同廣播排程的，觀察使用者端執行最短路徑查詢時在經歷時間以及聽取時間上的影響。除此之外，基於上面的資料廣播環境下之最短路徑方法，在考量路況的情形下，提出一個針對伺服端進行最短路徑之維護方法以因應隨時間改變的路況資訊，使用者因而能夠得到相對於現今路況的最短路徑。最後，我們透過大量實驗去驗證與比較所有方法的效能。

Real-time traffic condition communication technique and dynamic navigation computation have already existed in most of the vehicle-navigation system. Shortest path computation is one of the most common queries in navigation system. In such a wireless mobile environment, it is an important issue for handling large road network data efficiently. Data-Broadcasting is a proper structure to solving the problem. Under this consideration, the performance factors considered are tuning time and access latency. Tuning time is the number of the packets of the data from server that is necessary for the query. Access latency is the time between the client query and the time when all the required data are received. Before user querying, the server starts partitioning the road network to many sub-graphs, creating the index structure, and push the sub-graphs and index to the broadcasting cycle. In this paper, we observe the effect of the performance on the different road networks, partition method, packet size, and broadcasting methods. On the other hand, in the real road network, there are many conditions according to the time. The paper also presents the shortest path method in the dynamic road network of data-broadcasting environment. Finally, use experiments to prove the performance of tuning time and access latency.

摘 要 i
ABSTRACT ii
誌謝 iii
目 錄 iv
圖目錄 v
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 4
1.3 論文架構 4
第二章 文獻探討 5
2.1 資料廣播環境 5
2.2 非廣播環境底下搜尋最短路徑方法 6
2.3 廣播環境底下搜尋最短路徑方法 7
第三章 現有廣播方法之比較與討論 11
3.1 廣播環境底下搜尋最短路徑方法 11
3.2 廣播環境底下各種影響的因素 14
第四章 在廣播環境下動態路徑維護 15
4.1 在權重值上升邊之最短路徑維護方法 15
4.2 動態圖中提供查詢服務與相關問題 18
第五章 模擬實驗 22
5.1 環境設定 22
5.2 相同分割方法下各種廣播方法之表現 23
5.3 相同廣播方法下各種分割方法之表現 28
5.4 不同分割區塊數下各種廣播方法之表現 34
5.5 各種封包大小下各種廣播方法之變化 41
5.6 動態環境下資料廣播方法之表現 44
第六章 結論 46
參考文獻 47

[1]E. Kaplan and C. Hegarty. Understanding GPS: Principles and Applications Second Edition, Artech House, 2006.
[2]J. Spinney, A brief history of LBS and How OpenLS Fits Into the New Value Chain, Location-Based Services ESRI, 2003.
[3]S. Acharya, R. Alonso, M. Franklin and S. Zdonik, “Broadcast Disk: Data Management for Asymmetric Communication Environments”, In Proceeding of the 1995 ACM SIGMOD International Conference on Management of Data, Pages 199-210, 1995.
[4]S. Acharya, R. Alonso, M. Franklin and S. Zdonik, “Balancing Push and Pull for Data Broadcasts”, In Proceedings of the ACM SIGMOD International Conference on Management of Data, Pages 183-194, 1997.
[5]C.-M. Liu, Broadcasting and Blocking Large Data Sets with an Index Tree, PhD thesis, Purdue University, West Lafayette, 2002.
[6]K.-F. Lin and C.-M. Liu, “Efficient Scheduling Algorithms for Disseminating Dependent Data in Wireless Mobile Environments”, In Proceedings of the IEEE International Conference on Wireless Networks, communications and Mobile Computing, 2005.
[7]K.-F. Lin and C.-M. Liu, “Schedules with Minimized Access Latency for Disseminating Dependent Information on Multiple Channels”, In Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, Pages 344-351, 2006.
[8]T. Imielinski, S. Viswanathan and B.R. Badrinath, “Data on Air: Organization and Access”, IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 3, Pages 353-372, 1997.
[9]S. Hambrusch, C.-M. Liu, W. Aref and S. Prabhakar. “Efficient Query Execution on Broadcasted Index Tree Structures”, Data and Knowledge Engineering, Vol. 60, No. 3, Pages 511-529, 2007.
[10]S. Hambrusch, C.-M. Liu and S. Prabhakar. “Broadcasting and Querying Multi-dimensional Index Trees in a Multi-channel Environment”, Information System, Vol. 32, No. 8, Pages 870-886, 2006.
[11]T. Imielinski, S. Viswanathan, and B.R. Badrinath, “Power efficient filtering of data on air”, In Proceedings of the 4th International Conference on Extending Database Technology on Advances in Database Technology, Pages 245-258, 1994.
[12]W.-C. Lee and D.L. Lee. “Using Signature Techniques for Information Filtering in Wireless and Mobile Environments”, Distributed and Parallel Databases, Vol. 4, No. 3, Pages 205-227, 1996.
[13]Dijkstra E. W., “A Note on Two Problems in Connection With Graphs”, Numerische Mathematik, Pages 269-271, 1959.
[14]I. Phol, “Bi-Directional Search”, Machine Intelligence, Pages 127-170, 1971.
[15]R. Sedgewick and J.S. Vitter, “Shortest Paths in Euclidean Graphs”, Algorithmica, Vol. 1, No. 1, Page 31-48, 1986.
[16]R. Agrawal and H.V. Jagadish, “Materialization and Incremental Update of Path Information”, In Proceedings of the Fifth International Conference Data Engineering, Pages 374-383, 1989.
[17]Y.-W. Huang, N. Jing and E. A. Rundensteiner, “A Semi-Materialized View Approach for Route Maintenance in Intelligent Vehicle Highway Systems”, In Proceeding of the Second ACM Workshop Geographic Information Systems, Pages 144-151, 1994.
[18]S. Shekhar, A. Kohli and M. Coyle, “Path Computation Algorithms for Advanced Traveler Information System”, In Proceedings of the Ninth International Conference of Data Engineering, Pages 31-39, 1993.
[19]S. Jung and S. Pramanik, “HiTi Graph Model of Topological Road Maps in Navigation Systems”, In Proceedings of the 12th International Conference Data Engineering, Pages 76-84, 1996.
[20]Y.-W. Huang, N. Jing and E. A. Rundensteiner, “Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Type”, In Proceeding of the Third ACM Workshop Geographic Information Systems, Pages 93-100, 1995
[21]N. Jing, Y.-H. Huang and E. A. Rundensteiner, “Hierarchical Optimization of Optimal Path Finding for Transportation Application”, In Proceeding of the Fifth International Conference on Information and Knowledge Management, Pages 261-268, 1996.
[22]E. W. Dijkstra. “A note on two problems in connexion with graphs”, In Proceeding of NUMERISCHE MATHEMATIK, Pages 269-271, 1959.
[23]P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths”, In Proceeding of IEEE Transactions on Systems, Science, and Cybernetics, Pages 100-107, 1968
[24]EKKehard Kohler, Rolf H. Mohring, and Heiko Schilling*, “Fast Point-to-Point Shortest Path Computations with Arc-Flags”, In Proceedings of 9th DIMACS Implementation Challenge - Shortest Paths, 2007.
[25]A. V. Goldberg and C. Harrelson, “Computing the Shortest Path : A* search meets graph theory”, In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Pages 156- 165, 2005.
[26]Georgios Kellaris, Kyriakos Mouratidis, “Shortest Path Computation on Air Indexes”, In Proceedings of the VLDB Endowment, Vol. 3, No. 1, Pages 747-757, 2010.
[27]T.-C. Su, Y.-T. Hsieh, and C.-M. Liu, “Shortest Path Queries in Mobile Broadcast Environments”, In Proceeding of the 17th International Conference on Geoinformatics, 2009.
[28]Y.-W. Huang, N. Jing and E. A. Rundensteiner, “Efficient Graph Clustering for Path Queries in Digital Map Databases”, In Proceedings of International Symposium on Algorithms and Computation, 1999.
[29]R. H. Mohring, H. Schilling, B. Schutz, D. Wagner, and T. Willhalm, “Partitioning graphs to speedup Dijkstra’s algorithm”, In Journal of Experimental Algorithmics, Volume 11, 2006.
[30]交通路網數值地圖, http://www.iot.gov.tw, (view available: July, 2008)