- 學位論文
無限廣播系統多頻道環境下對K個最近鄰居以及反向最近相鄰者搜尋之探討
A Study on KNN and RNN Searches in Multi-channel Broadcast Environment
摘要
在無線通訊網路環境下，以資料廣播的方式能有效散播資料給大量的行 動用戶端。很多種資訊服務都能使用廣播系統來加以應用，包含了適地性服 務(Localtion-Based Service, LBS)。在適地性服務之中，K個最近鄰居和反向最近 相鄰者搜尋是其中重要的搜尋方式，K個最近鄰居搜尋是支援行動用戶端查詢在 他們目前位置附近所需的相關物件，反向最近相鄰者搜尋是反過來尋找行動用戶 是哪個物件的最近鄰居。在此篇論文中，我們將傳統廣播系統的頻道數量從單一 頻道增加到數個頻道之多，並因應這種變動提供了數種多頻道機制來和以往的單 一頻道廣播排程做比較，以延遲時間(Latency)與查詢時間(Tuning Time)作為衡量 的標準下，我們提出一個使用廣播方式來搜尋KNN以及RNN的方法。在伺服器端 我們探討如何產生廣播排程，而且探討產生的排程以怎樣的順序放置在多個頻道 上；在行動用戶端則探討如何在此廣播排程下有效執行查詢。為了有效節省查詢 時間，我們所提出的方法是利用額外的附帶資訊來取代一般索引方式。另一方 面，我們進一步針對排程中使用空間填充曲線與否會不會影響延遲時間和查詢時 間做討論。最後我們對所有提出的做法皆進行大量的實驗模擬，而實驗結果符合 我們的預期。
並列摘要
Data broadcasting is an e ective way to disseminate information to a large amount of mobile clients in wireless mobile environments. Many information ser- vices can use such a technique to serve the clients, including Location-Based Service (LBS). K nearest neighbor (kNN) search and Reverse nearest neighbor (RNN) search are the two of the important location-based services. KNN search allows clients to get the points of interests around them, and RNN search is to determine a set of data points, where the query point is the nearest neighbor of each data point re- spectively, in a given data set. In this thesis, we consider to use multiple channels to broadcast the data, and provide several scheduling algorithms for multi-channel to compare with the ones for single channel using latency and tuning time as the measurements. In the proposed broadcast, we use some addition information in the broadcast data instead of an index to save the tuning time and latency. We farther discuss the tuning time and latency when di erent space- lling curves are applied in the schedules. Finally, we discuss the performance and present our ndings through a large number of experiments