面向移動對象間狀態(tài)查詢優(yōu)化算法的研究與實現(xiàn).pdf

1、隨著無線通信技術(shù)和智能移動終端的廣泛應用，基于位置的服務(Location-basedService，LBS)得到飛速發(fā)展與普及，并廣泛應用于軍事、交通、物流、醫(yī)療及民生等領(lǐng)域。基于位置服務通過移動終端利用各種定位技術(shù)獲得當前位置信息，并使用移動對象管理技術(shù)索引和查詢這些位置信息，為用戶提供個性化的服務。近年來，移動對象管理的查詢領(lǐng)域中典型的查詢包括范圍查詢、最近鄰查詢、反最近鄰查詢、最遠鄰查詢、連續(xù)最近鄰查詢、連續(xù)反最近鄰查詢等。這些

2、查詢服務由于歷經(jīng)多年的研究，已經(jīng)取得了優(yōu)秀的研究成果，相關(guān)技術(shù)也非常成熟。但是隨著基于位置信息服務的快速發(fā)展，出現(xiàn)了一些現(xiàn)有查詢不能解決的服務，這些服務關(guān)注移動對象間距離變化。為了更好的滿足用戶的查詢需求，對移動對象間狀態(tài)查詢的研究也變得越來越重要。
　　移動對象間運動趨勢分為不同的類（即移動對象間狀態(tài)），移動對象間狀態(tài)查詢就是通過兩個移動對象的距離信息判斷兩移動對象屬于哪個狀態(tài)的過程。目前，針對移動對象間狀態(tài)查詢的概念，已分別提

3、出樸素的和基于ELM的兩種移動對象間狀態(tài)查詢算法。在兩種算法基礎上，本文主要做了如下優(yōu)化:針對樸素狀態(tài)查詢算法時間性能低下的問題，本文提出一種基于最大最小值的新算法，用第一時刻距離和距離最大最小值的關(guān)系區(qū)分不同類;對基于ELM的算法查詢準確率不夠理想的問題，本文不但提出更有區(qū)分度的特征，還采用先樸素的分大類再用ELM分小類的策略對算法進行優(yōu)化。實驗對比表明:基于最大值最小值的算法將原算法的時間性能提高了將近一半;基于ELM的優(yōu)化算法不但

4、在查詢精確度方面較原算法提高了3％，查詢時間也是原算法的一半。
　　在此研究基礎上，本文進一步對連續(xù)的狀態(tài)查詢建模，并提出三種移動對象間連續(xù)狀態(tài)查詢算法。其一，是一種基于距離比較的查詢算法，當新時刻來臨時將新時刻距離與以前時刻做比較并更新存儲信息的矩陣;其二，是一種基于優(yōu)先隊列的查詢算法，用優(yōu)先隊列維護當前時間窗口內(nèi)距離的最值;其三，針對基于優(yōu)先隊列算法在處理最值丟失問題上的不足，引入最值候選序列的概念，有效地避免了最值丟失。三種