臺灣博碩士論文加值系統

在無線通訊網路環境下，以資料廣播的方式能有效散播資料給大量的行
動用戶端。很多種資訊服務都能使用廣播系統來加以應用，包含了適地性服
務(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

1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Major Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 PRELIMINARIES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Wireless Broadcast Environments . . . . . . . . . . . . . . . . . . . . 9
2.2 Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Nearest Neighbor Searches . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Reverse Nearest Neighbor Searches . . . . . . . . . . . . . . . . . . . 18
2.5 Related RNN methods . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Space Filling Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6.1 Hilbert Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6.2 Z-curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6.3 Gray Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6.4 KD-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 PROBLEM DEFINITION . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1 The Multi-Channel Broadcasting . . . . . . . . . . . . . . . . . . . . 26
iv
3.2 The KNN and RNN Search in the Wireless Broadcast Environment . 27
4 Multi-Channel Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . 29
4.1 Server Schedules Processing . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Client Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.1 KNN Search Protocol . . . . . . . . . . . . . . . . . . . . . . . 32
4.2.2 RNN Search Protocol . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 MULTI-CHANNEL BROADCASTING SIMULATION . . . . . . . . . . 39
5.1 KNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.1.1 Tuning Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.1.2 Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2 RNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2.1 Tuning Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2.2 Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6 CONCLUSIONs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen. Ap-
proximate line nearest neighbor in high dimensions. In Proceedings of the twen-
tieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 293{301,
2009.
[2] S. Berchtold, D. A. Keim, H.-P. Kriegel, and T. Seidl. Indexing the solution
space: A new technique for nearest neighbor search in high-dimensional space.
IEEE Transactions on Knowledge and Data Engineering, 12(1):45{57, 2000.
[3] Yunjun Gao, Baihua Zheng, Wang-Chien Lee, and Gencai Chen. Continuous
visible nearest neighbor queries. In Proceedings of the 12th International Con-
ference on Extending Database Technology, 2009.
[4] Bugra Gedik, Aameek Singh, and Ling Liu. Energy e cient exact knn search
in wireless broadcast environments. In Proceedings of the 12th annual ACM in-
ternational workshop on geographic information systems, pages 137{146, 2004.
[5] Haibo Hu and Dik Lun Lee. Range nearest-neighbor query. IEEE Transactions
on Knowledge and Data Engineering, 18(1):78{91, 2006.
[6] T. Imieli nski, S. Viswanathan, and B. R. Badrinath. Data on air: Organization
and access. IEEE Transactions on Knowledge and Data Engineering, 9(3):353{
372, 1997.
[7] James M. Kang, Mohamed F. Mokbel, Shashi Shekhar, Tian Xia, and Donghui
Zhang. Continuous evaluation of monochromatic and bichromatic reverse near-
est neighbors. Proceedings of the International Conference on Data Engineering.
[8] Flip Korn and S. Muthukrishnan. In
uence sets based on reverse nearest neigh-
bor queries. In Proceedings of the 2000 ACM SIGMOD international conference
on Management of data, pages 201{212, 2000.
[9] Der-Tsai Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE
Transactions on Computing, 31(6):478{487, 1982.
[10] Chuan-Ming Liu and Shu-Yu Fu. E ective protocols for knn search on broadcast
multi-dimensional index trees. Information Systems, 33(1):18{35, 2008.
[11] Chuan-Ming Liu, Kai-Yun Ho, and Wei-Chih Yeh. A knn search protocol using
a voronoi diagram in wireless broadcast environments. In Proceedings of the
2009 IEEE WiNA International Workshop on Wireless Network Algorithm and
Theory, 2009.
[12] Chuan-Ming Liu, Li-Chun Wang, Lei Chen, and Chung-Ju Chang. On-demand
data disseminating with considering channel interference for e cient shortest-
route service on intelligent transportation system. In Proceedings of the 2004
IEEE International Conference on Networking, Sensing and Control, pages
701{706, 2004.
54
[13] Dimitris Papadias, Qiongmao Shen, Yufei Tao, and Kyriakos Mouratidis. Group
nearest neighbor queries. In Proceedings of the 20th International Conference
on Data Engineering, 2004.
[14] Hanan Samet. K-nearest neighbor nding using maxnearestdist. IEEE Trans-
actions on Pattern Analysis and Machine Intelligence, 30:243{252, 2008.
[15] Frederic Paik Schoenberg, Thomas Ferguson, and Cheng Li. Inverting dirichlet
tessellations. Computer Journal, 46, 2003.
[16] Yufei Tao, Dimitris Papadias, and Xiang Lian. Reverse knn search in arbitrary
dimensionality. In Proceedings of the Thirtieth international conference on Very
large data bases, 2004.
[17] Tian Xia and Donghui Zhang. Continuous reverse nearest neighbor monitoring.
In Proceedings of the 22nd International Conference on Data Engineering, 2006.
[18] Baihua Zheng, Wang-Chien Lee, and Dik Lun Lee. Spatial queries in wireless
broadcast systems. Wireless Networks, 10(6), 2004.
[19] Baihua Zheng, Jianliang Xu, Wang-Chien Lee, and Dik Lun Lee. Grid-partition
index: a hybrid method for nearest-neighbor queries in wireless location-based
services. The Very Large Data Bases Journal, 15(1):21{39, 2006.