在資料廣播環境中進行最短路徑查詢之研究

A Study of Shortest Path Query in Data-Broadcasting Environments

謝耘東(Yun-Tung Hsieh)

指導教授 ： 劉傳銘

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

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

摘要

近年來由於全球定位系統、及無線通訊技術的進步與普及化。使人們能在任何時間、任何地點取得與其位置相關之服務。在這種無線環境之中，以資料廣播提供資訊服務之相關議題近年來受到廣泛的討論，包括範圍查詢、點查詢及鄰近點查詢等等。在這種環境中常會考慮到兩項效能指標，查詢經歷時間(Latency)及聽取時間(Tuning Time)。查詢經歷時間為用戶發出服務要求，直至收到完整回應所經過的時間。聽取時間為查詢過程客戶端實際聽取廣播頻道的時間。本論文研究如何以資料廣播的方式提供最短路徑查詢服務，並以查詢經歷時間及聽取時間兩方面探討其效能。在無線環境中，伺服器端我們探討如何將圖形分割並排程於廣播頻道之中；在客戶端則探討如何在此排程之中利用伺服器附加於頻道的資訊進行最短路徑查詢。實驗結果發現我們所提出的方法在查詢經歷時間及聽取時間上都有不錯的表現。在磁碟環境中，我們研究圖形叢集(Graph Clustering)策略對路徑查詢時分頁存取效率的影響，提出一個遞迴式空間叢集方法(Recursive Spatial Clustering)並進行相關的實驗模擬。

關鍵字

資料廣播 ； 空間叢集 ； 階層式圖形 ； 記憶體限制 ； 全球定位系統

並列摘要

With the emerging of technologies on Global Positioning Systems and wireless communications, it is possible for people to access information related to their locations any time any where. In such a wireless mobile environment, data-broadcasting provides an effective way to disseminate information to a large group of users. Two measurements are usually considered when applying data-broadcasting to provide services, the latency and the tuning time. The latency is the time between the issuing and completion of a query and stands for the quality of service. The tuning time measures the actual time when a client listens to the broadcast and presents the power consumption. In this paper, we consider to use data-broadcasting to provide the shortest path service in wireless mobile networks. We consider that the mobile clients have the memory and bandwidth restrictions. In our approach, the mobile client does not need to store the entire road network and can derive the shortest path by selectively tuning into the broadcast to save energy. On the server side, we study how to partition graphs into clusters and schedule on channel for path query. It allows the client to filter unnecessary portion when executing the shortest path query. On the client side, we provide a heuristic to compute the shortest path by listening to the broadcast. As the experimental results show, it performs well in terms of the latency and tuning time and is plausible when the client has only limited memory. In disk-based environments, we study disk page I/O performance in different graph clustering strategies while processing path queries. We also propose an alternative graph clustering strategy to compare with existing approaches.

並列關鍵字

Data Broadcasting ； Spatial Clustering ； Hierarchical Graph ； Memory Restriction ； Global Positioning System

參考文獻

[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.

[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.