基于區(qū)域覆蓋的分組移動對象的區(qū)域偏離監(jiān)視算法的研究與實現.pdf

1、隨著無線通訊技術和全球定位技術的快速發(fā)展，基于位置信息的服務(LocationBased Service，LBS)受到廣泛關注。它在民用和軍用方面等諸多領域展現了廣泛的應用前景。而支持LBS設備（如PDA，手機）的普及促使人們對于LBS的需求更加公眾化、多樣化，對分組移動對象的區(qū)域偏離監(jiān)視服務就是其中之一。用戶可以借助此項服務隨時了解每組中的移動對象是否離該組中心對象過遠，即超出了以該組中心對象為中心、指定距離為半徑的圓的區(qū)域，例如，某

2、景區(qū)的大量旅游團，可以借助此項服務來監(jiān)視旅游團內是否有游客離導游過遠，幼兒園的老師帶領學生出外郊游時可以通過它來判斷是否有學生離老師過遠等。盡管LBS的研究工作已經有很多成果，但大多數的研究集中在查詢點和被查詢點中至少有一個是靜止的情況，同時與大規(guī)模移動對象監(jiān)視直接相關的研究成果很少。分組移動對象區(qū)域偏離監(jiān)視是查詢點和被查詢點都處于運動之中的應用，現有的研究成果無法被直接利用。這就需要考慮新的索引結構與算法，本文中對這方面問題進行了深入

3、研究。
　　本文首先根據分組移動對象的分布及運動特點，設計了基于區(qū)域覆蓋的帶有分組信息的虛擬網格四分樹(Grouped Virtual Grid Quadtree，GVGQ)索引結構來管理帶有分組信息的移動對象，GVGQ通過索引移動對象所在的區(qū)域而非移動對象本身來減少由于移動對象位置改變而引起的索引結構的頻繁更新，并且在索引結構中存儲移動對象的分組信息以更方便地支持對指定組的移動對象進行相關查詢等操作。其次，基于GVGQ索引結構，

4、本文提出了兩種算法來對分組移動對象提供區(qū)域偏離監(jiān)視服務，算法RQMonitor利用GVGQ在每組移動對象的近似安全區(qū)域外圍做范圍查詢來主動查找該組偏離的對象，通過索引樹結點中的組信息以及結點與查詢范圍的包含關系來快速地找到可能包含偏離對象的結點，提高區(qū)域偏離監(jiān)視速度。進一步的，算法DPMonitor同樣采用在安全區(qū)域外圍查找偏離對象的思路，所不同的是，它利用索引中的結點到中心對象的最大距離和最小距離來對不可能包含偏離對象的結點進行剪枝，