資源描述：
《面向路網的移動對象間的連續(xù)狀態(tài)查詢算法的研究與實現》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、萬方數據分類號UDC密級學位論文面向路網的移動對象間的連續(xù)狀態(tài)查詢算法的研究與實現作者姓名：喬偉指導教師：王波濤教授東北大學信息科學與工程學院申請學位級別：碩士學科類別：工學學科專業(yè)名稱：計算機軟件與理論論文提交日期：2014年6月論文答辯日期：2014年6月21日學位授予日期：2014年7月答辯委員會主席：喬建忠教授評閱人：吳剛副教授張大波教授東北大學2014年6月萬方數據AThesisinComputerSoftwareandTheoryResearchandImplementationofContinuousStateQueryAlgor
2、ithmsbetweenMovingObjectsinRoadNetworksByQiaoWeiSupervisor：ProfessorWangBotaoNortheasternUniversityJune2014萬方數據獨創(chuàng)性l聲明本人聲明，所呈交的學位論文是在導師的指導下完成的。論文中取得的研究成果除加以標注和致謝的地方外，不包含其他人己經發(fā)表或撰寫過的研究成果，也不包括本人為獲得其他學位而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意。學位論文作者簽名：名詁日期：多．五鏟學位論文版權使用授權書本
3、學位論文作者和指導教師完全了解東北大學有關保留、使用學位論文的規(guī)定：即學校有權保留并向國家有關部門或機構送交論文的復印件和磁盤，允許論文被查閱和借閱。本人同意東北大學可以將學位論文的全部或部分內容編入有關數據庫進行檢索、交流。作者和導師同意網上交流的時間為作者獲得學位后：半年口一年口一年半口學位論文作者簽名：云鉑簽字日期：∥．砂≯兩年囤／導師簽名：7-．認紀哥簽字日期：2p／爭，石，2爭萬方數據查I墾盤堂塑±鱟焦迨塞揎璺面向路網的移動對象間的連續(xù)狀態(tài)查詢算法的研究與實現摘要隨著基于用戶位置的服務(Location．BasedService，LB
4、S)研究的日益深入，用戶對LBS的需求日趨豐富。例如在智能交通領域，自動駕駛技術不僅需要解決普通的位置定位技術，更重要的是要持續(xù)監(jiān)測車與周圍車輛以及道路上其他物體之間的距離遠近關系，保證安全行駛。現有的查詢處理技術，如范圍查詢、最近鄰查詢和連續(xù)范圍查詢等，僅僅關注某一時刻查詢點與被查詢點之間的位置關系，無法滿足用戶對移動對象之間的連續(xù)狀態(tài)查詢服務的需求。移動對象間狀態(tài)查詢是指移動對象查詢自身與周圍其他移動對象之間越來越遠或者越來越近的位置關系。已有的移動對象間狀態(tài)查詢算法主要包括樸素的狀態(tài)查詢算法與移動對象間的連續(xù)狀態(tài)查詢算法，均是基于歐氏空間
5、，難以直接應用于路網環(huán)境。本文提出了面向路網的移動對象間連續(xù)狀態(tài)查詢中的關鍵算法。針對大規(guī)模的移動對象的應用場景，移動對象間的連續(xù)狀態(tài)查詢算法面臨著兩大挑戰(zhàn)：一方面如何快速地對海量移動對象定位；另一方面如何在路網環(huán)境下高性能地計算海量移動對象間的距離。針對上述問題，本文做了以下兩方面工作：針對快速定位移動對象位置的問題，本文提出了三種移動對象定位算法。基于路段劃分的移動對象定位算法通過對較長路段進行劃分，對子路段構造MBRs，建立R樹索引，有效地減少了MBRs之間的重疊區(qū)域和MBRs對無效區(qū)域的覆蓋?；诰W格R樹的移動對象定位算法將網格定位的高
6、效性與R樹搜索的高效性結合起來?；诼肪W拓撲的移動對象定位算法，利用了路網拓撲結構與基于網格R樹的移動對象定位算法相結合。實驗對比表明：三種定位算法的性能均優(yōu)于基于R樹的移動對象定位算法。路網環(huán)境下，大規(guī)模移動對象間的距離計算成為制約移動對象間的連續(xù)狀態(tài)查詢的瓶頸。因此，本文從工程角度提出基于距離查詢表的移動對象間距離序列計算算法(calculatingdistancesequencebasedonDistanceQueryTable，DQT)，滿足了移動對象間的連續(xù)狀態(tài)查詢處理的實時性要求。針對距離查詢表需要內存空間較大的問題，對距離查詢表進
7、行了空間優(yōu)化，提出了基于空間受限距離查詢表的移動對象間距離序列計算算法(calculatingdistancesequencebasedonLimitedSpaceDistanceQueryTable，LSDQT)。實驗對比表明：兩種算法時間性能均優(yōu)于基于最短路徑算法移動對象間距離序列計算算法。算法LSDQT雖然在計算速度上比DQT算法慢了一個數量級，但空間受．II．萬方數據壅j墾盤堂亟±鱟焦逾塞抽堊限距離查詢表所需的內存空間僅為距離查詢表的1％，LSDQT算法對移動對象間的狀態(tài)計算精確度接近DQT算法，趨近于100％。關鍵詞：移動對象間狀態(tài)查
8、詢；連續(xù)查詢；路網；移動對象定位；最短路徑．．III．．萬方數據盤I墾盤芏塑±鱟焦逾塞△壘§!!壘叢ResearchandImplementation
