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

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

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

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

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