探討使用Network Voronoi Diagram在資料廣播環境中進行道路網路最短路徑查詢的方法

Exploring the Shortest Path Query on Road Network using Network Voronoi Diagram in Data Broadcasting Environments

郭柏辰(Bo-Chen Guo)

指導教授 ： 劉傳銘

國立臺北科技大學/電資學院/資訊工程系研究所/碩士(2014年)

https://doi.org/10.6841/NTUT.2014.00679

摘要

近年來行動裝置以及無線網路的普及化，使得行動裝置上出現眾多衍生服務，其中的適地性服務為最常見也最被廣泛使用的服務之一。使用者得以藉著行動裝置進行以地理資訊方面的查詢，其中最短路徑查詢方法為一個重要的項目。隨著地圖資料越來越龐大，在行動裝置的計算能力以及記憶體容量受限的狀況下，如何提供一個有效率的最短路徑查詢方法為一個值得討論的議題。在無線網路環境下，資料廣播提供複數使用者同時接收資料，且不會隨著使用者的增減對伺服器造成影響，適合解決上述問題的。在資料廣播環境下的兩項效能指標：查詢經歷時間及聽取時間。從客戶端在開始查詢到結束查詢結束這段時間稱為查詢經歷時間；而聽取時間則是實際擷取資料的時間之加總。伺服端提供處理過後的資訊於廣播頻道中，使用者端依照廣播內容自行接收相關資料。本論文研究探討伺服端如何有效運用NVD的結構，觀察使用者端執行最短路徑查詢時在經歷時間以及聽取時間上的影響。

關鍵字

資料廣播 ； 最短路徑 ； 查詢時間 ； 聽取時間 ； Network Voronoi Diagram

並列摘要

The mobile device and the condition of the wireless mobile network are popular in recent year, and the router problem also solved as quick as possible when we use the services with mobile device. In the above describe, the service are compute the shortest path for response answer to user. It has a serious issue with the wireless mobile environment is the service performance will be decreasing with service user increasing. 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 the service provided for user, the server has to partitions the data for channel to broadcast. In this paper, we observe the effect of the performance on the different road networks, partition method, packet size, and broadcasting methods. Finally, use experiments to prove the performance of tuning time and access latency.

並列關鍵字

Data Broadcasting ； Shortest Path ； Access Latency ； Tuning Time ； Network Voronoi Diagram

參考文獻

[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, pp. 344-351, 2006.

[9] S. Hambrusch, C.-M. Liu, W. Aref and S. Prabhakar. “Efficient Query Execution on Broadcasted Index Tree Structures”, Data and Knowledge Engineering, 60(3):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,32(8): 870-886, 2006.