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

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

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

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

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