路網(wǎng)中移動(dòng)對(duì)象最近鄰及反向最近鄰查詢處理研究.pdf

1、無線廣播技術(shù)高速發(fā)展和移動(dòng)通信設(shè)備的不斷普及使得位置相關(guān)服務(wù)(location-based services，LBSs)越來越走進(jìn)我們的日常生活。而位置相關(guān)查詢處理(location-based queries，LBQs)作為位置相關(guān)服務(wù)的支持性技術(shù)之一，已經(jīng)成為一個(gè)研究熱點(diǎn)問題。近年來，研究者們對(duì)位置相關(guān)查詢，特別是最近鄰查詢和反向最近鄰查詢進(jìn)行了深入的研究，提出了許多有效的查詢處理方法。但是，在最近鄰查詢方面，目前尚無人提出路網(wǎng)中可

2、變速移動(dòng)對(duì)象的連續(xù)k近鄰查詢處理算法；在反向最近鄰方面，目前尚無人提出徹底的、對(duì)象和查詢點(diǎn)均可連續(xù)移動(dòng)的、路網(wǎng)中連續(xù)反向k近鄰處理算法。目前位置相關(guān)查詢處理的主要形式都是基于傳統(tǒng)的按需訪問（on-demand access）模式。按需訪問方式只適合于無線信道和服務(wù)器處理容量都充足的輕負(fù)載系統(tǒng)。當(dāng)客戶量大、客戶發(fā)起的移動(dòng)查詢量大時(shí)，服務(wù)器的處理能力和無線信道的帶寬都會(huì)影響到查詢處理的效率和速度。近年來，人們開始關(guān)注數(shù)據(jù)廣播環(huán)境下的位置查詢

3、處理的研究，也提出了一些研究成果。但是到目前為止，這些研究只是局限于歐氏空間。歐氏空間環(huán)境下的相關(guān)算法是不能通過簡(jiǎn)單的修改而應(yīng)用到路網(wǎng)環(huán)境下的，所以研究數(shù)據(jù)廣播環(huán)境下路網(wǎng)中位置查詢處理算法是非常迫切、必要的。
　　首次討論了路網(wǎng)中反向k近鄰查詢連續(xù)監(jiān)控問題(CRkNN)，分析了路網(wǎng)中移動(dòng)對(duì)象連續(xù)反向k近鄰查詢的關(guān)鍵技術(shù)。提出了一種全新的稱為DLM樹的數(shù)據(jù)結(jié)構(gòu)來索引CRkNN查詢的監(jiān)控范圍，從而將CRkNN查詢問題的處理簡(jiǎn)化為監(jiān)控幾

4、個(gè)多路樹，而不必在位置更新發(fā)生時(shí)重新計(jì)算查詢結(jié)果。提出了統(tǒng)一解決單色數(shù)據(jù)集和雙色數(shù)據(jù)集上反向k(≥1)近鄰查詢的框架和相應(yīng)算法；為進(jìn)一步提高算法的效率，給出了有關(guān)引理以盡可能地削減查詢空間，并提出一些優(yōu)化技術(shù)以高效地處理與查詢結(jié)果有關(guān)的位置更新。模擬實(shí)驗(yàn)表明所提出的算法是有效的。
　　討論了路網(wǎng)中不定速移動(dòng)對(duì)象連續(xù)k近鄰查詢(CUkNN)的處理問題，分析目前現(xiàn)有的路網(wǎng)中移動(dòng)對(duì)象連續(xù)k近鄰查詢算法的局限性。提出了一種不確定路網(wǎng)距離計(jì)

5、算模式以計(jì)算路網(wǎng)中不定速移動(dòng)對(duì)象和移動(dòng)查詢點(diǎn)之間的距離。基于這種距離模式，提出了兩種CUkNN的連續(xù)監(jiān)控算法，即CUkNN PLS和CUkNN Mean。在CUkNN PLS算法中，引入了可能距離區(qū)域和可能距離線段(PLS)的概念，以簡(jiǎn)化對(duì)象o成為查詢q的kNN之一的概率值的計(jì)算。在CUkNN Mean算法中，為了進(jìn)一步簡(jiǎn)化概率的處理，我們沒有計(jì)算每個(gè)候選對(duì)象的成為查詢q的kNN之一、確切的概率值，而是提出了一種有效的方法來將所有可能成

6、為查詢q的kNN結(jié)果之一的對(duì)象按照其概率值遞減的順序進(jìn)行排列，選擇排在前k位的對(duì)象構(gòu)成最終的kNN結(jié)果集。此外，提出了一種處理對(duì)象速度超出界限和對(duì)象移動(dòng)方向發(fā)生改變的方法，以維持查詢結(jié)果持續(xù)有效。通過用一種新穎、規(guī)整的方法組織有關(guān)數(shù)據(jù)結(jié)構(gòu)，擴(kuò)展所提出的CUkNN算法以高效地、低磁盤訪問代價(jià)地處理大路網(wǎng)中的CUkNN查詢。模擬實(shí)驗(yàn)驗(yàn)證了所提出算法的有效性和可擴(kuò)展性。
　　首次討論了無線廣播環(huán)境下路網(wǎng)中連續(xù)最近鄰查詢處理問題(CNBN

7、N)。通過用屬性obj_dom來標(biāo)記路網(wǎng)上每一條邊，以表明該邊屬于某個(gè)特定對(duì)象的voronoi多邊形，提出了NVD結(jié)構(gòu)以保留NVD圖的特性。提出了一種稱之為NVD四分劃分的路網(wǎng)劃分方法，將路網(wǎng)劃分為一系列網(wǎng)格單元。特別地，各網(wǎng)格單元占據(jù)大致相同的存儲(chǔ)空間，而且具有較好的局部性保留性能。然后，提出了一種稱為NVD-DI的分布式索引結(jié)構(gòu)以支持CNBNN查詢處理。基于這種NVD-DI索引結(jié)構(gòu)，提出了一種有效的CNBNN查詢處理算法。CNBNN