一種移動對象近鄰檢測的方法

2023-05-30 20:30:06 9

專利名稱：一種移動對象近鄰檢測的方法
技術領域：
本發明屬於計算機應用技術領域，涉及一種移動對象近鄰檢測的方法，特別適用於大規模移動對象的數據處理，例如在線位置服務、在線網路遊戲中的用戶近鄰檢測等。
背景技術：
在日常生活中，隨著GPS和無線通信網絡的普及，基於位置的服務 LBS(location-based services)已經成為現實。在眾多的LBS服務中，有一種關鍵的服務即路網環境中移動對象的近鄰檢測是許多應用的基礎，這些應用例如交通網絡的路由服務，流量監測，出行模式數據挖掘等。另外在虛擬世界，大規模多方在線遊戲環境中的相鄰夥伴提示也是近鄰檢測一個重要應用，其使用的技術與真實路網環境中的類似。因此近鄰檢測技術的提升具有重要意義。給定一組用戶U，一個路網環境G，以及某移動對象朋友對{Ui, u)的近鄰距離標準hj，近鄰檢測問題被定義為尋找這樣的朋友對{Ui, I)，首先~ ~是相鄰的，其次是~ Uj之間的歐幾裡德距離DistanceOUhi.)) ^ Uj。在一個路網環境中的近鄰檢測問題就是DistanceD ({up u)) ( ￡ 其中DistanceD表示兩個節點之間的Di jkstra最短距離。在大規模連續的近鄰檢測過程中，歐幾裡德距離和Dijkstra最短距離的計算容易成為系統的瓶頸。因此降低近鄰檢測的計算複雜度具有很大的迫切性。

發明內容
本發明的目的是在於克服現有技術中的不足，針對路網環境中近鄰距離計算的特點，提供一種適用於分布式環境中的近鄰檢測方法。本發明的方法具體步驟如下
步驟(I)、移動對象朋友關係的索引和移動範圍更新；
所述移動對象是指具有GPS定位和無線通信能力的智能計算終端。移動對象的朋友關係採用一種兩層的優先級隊列來保持。所述的兩層的優先級隊列的結構具體如下
對於每個移動對象維護一個本地的朋友列表優先級隊列，按照觸發時間的大小進行排序。每個移動用戶本地隊列中最早觸發時間的朋友對進入一個全局優先級隊列。當移動用戶Ui位置更新到達後，更新本地的優先級隊列，刪除全局優先級隊列中用戶Ui的相應節點，將本地隊列首節點插入。系統周期性的掃描優先級隊列，對觸發時間到期的朋友對進行近鄰判斷和通告處理。兩層的優先級隊列降低了算法的複雜度，從而優化系統的處理性能。移動對象在每一個更新周期都會採用GPS對自身位置進行定位，採集移動速度和位置信息。取得上一次發往伺服器的預測PrediCtB0X=(G t, LB, LV)。其中tr是預測區域的引用時間，G是預測區域的過期時間，Zi 是對象在這一時間段內的物理移動範圍，是根據當前位置信息和移動速度計算的矩形框，ZK是對象的當前移動速度。
首先判斷當前時間是否已經超過te ;然後判斷當前位置與預測位置的距離是否位於安全區域，也就是是否在預測的物理移動範圍以上任何一種條件滿足，移動用戶都會向伺服器發送一個新的預測。如果兩種情況都不是，移動用戶就等待下一個更新周期。步驟(2)、對移動對象進行索引；
伺服器中移動用戶的索引使用時間參數化的R樹(TPR-tree, time-parameterizedR-tree) 0時間參數化的R樹能夠有效地對移動用戶的當前位置進行索引，並且帶有對象的速度等信息，因此可以對移動用戶進行位置預測。時間參數化的R樹中每個非葉子結點都由多個最小包含矩形框MBR (MBR,minimumbounding rectangles)及指向子節點的指針組成。非葉子結點最小包含矩形框MBR為包含每個非葉子結點孩子當前的最小邊界矩形。葉子結點由最小包含矩形框MBR和移動用戶的指針組成。葉子結點MBR為包含對應移動用戶的最小邊界矩形，通過移動用戶的指針可以得到對象的詳細信息。移動用戶的詳細信息包含當前位置信息，以及速度和最近的移動範圍更新信息PB。步驟(3)、對移動對象進行基於近鄰框的近鄰檢測；
伺服器對於每個超限安全區域更新進行近鄰檢測。超限安全區域更新指的是移動對象移動範圍超越預測區域，其真實位置在預測區域外，移動對象向伺服器發送位置更新信息。本申請的移動對象之間具有相互的朋友關係，但是不同對象可以定製不同近鄰標準，也即不同對象可能具有不同的近鄰標準。設&是的朋友，那麼也是~的朋友，但是他們具有不同的近鄰標準.和e 伺服器接收到移動用戶的PB消息後，更新其索引節點。它同時維護一個移動用戶鄰近朋友的列表。伺服器先對列表中的所有朋友進行近鄰檢測，檢測過程使用用戶Ui的近鄰標準e u，更新用戶U1的近鄰朋友列表。接著，伺服器對列表中所有朋友針對Ui進行近鄰檢測，使用其朋友的近鄰。對於移動對象的近鄰距離標準為e LJ。在某一時刻檢測其朋友列表中的用戶~是否在其近鄰範圍內，基於近鄰框的近鄰檢測就是判斷他們的坐標關係是否滿足k..
X-Uf x\ ^ ￡ JJ 且 I Ui. y-Uj. ,I < itj。由於在伺服器中保留是用戶的移動區域預測，對於近鄰關係判斷需要考慮用戶在其安全域區內具體位置的不確定性。給定一個長寬分別為A、B的預測區域，兩個用戶
Uj之間的XY軸方向距離關係有
MaxDX {up Uj) =max {| Ui. x_uf x | _u」 k~Uj. A, 0}
MinDX {up Uj) = I Ui. x_uf x | +u」 k+Uj. A MaxDY {up Uj) = max {| Ui. y_uf y | -Ui. B-W7-. B, 0}
MinDY {up Uj) = | Ui. y_uf y | +U1. B+w, B Up 之間確定具有近鄰關係的條件是 MaxDX {up Uj) ^ L j 且 MaxDY {up Uj) ^ L j Ui, 之間確定不具近鄰關係的條件是 MinDX (.U1, Uj) > ￡ irJ 且 MinDY (.U1, u) > ￡ irJ 由於~具有相互的朋友關係，在對&進行近鄰檢測以後，還需要對~進行近鄰檢測。為了簡化這一過程，首先對兩個用戶的近鄰框大小進行判斷，先行檢測較小的近鄰框。如果對於較小的近鄰框，移動用戶Ui, ~都具有近鄰關係，那麼對於另外一個用戶來說顯然也具有近鄰關係。反之，就需要進一步判斷對於較大近鄰框的移動用戶是否具有近鄰關係。檢測完成後，用戶U1的朋友就分為了三類。在近鄰框以外的，他們就不具有近鄰關係，在近鄰框以內的就具有近鄰關係。由於伺服器保持的是某個用戶的安全區域，通過其速度只能粗略確定其所在位置。當用戶安全區域剛好跨越用戶Ui的近鄰框時，系統就不能判斷他們兩者的近鄰關係。這個時候就需要向該用戶發送查詢信息，通過其最新的安全區域預測了解當前的位置信息，進行近鄰與否檢測，並進行近鄰關係觸發事件的計算。基於近鄰框的檢測過程僅通過判斷兩個移動用戶的坐標關係，在x、y兩個軸向任何一個方向距離超過用戶的近鄰標準定義即停止檢測。顯然，相比歐幾裡德距離和Dijkstra最短距離簡化了系統的計算開銷。步驟(4)、近鄰關係的索引和觸發事件的計算
採用步驟(I)中所述的兩層的優先級隊列對移動對象的近鄰關係以及觸發時間進行管理。 兩個移動用戶的觸發時間T {up Uj) , T {up Uj)是指Uj移動進入Ui近鄰框的最早時間。假設( .心Ui. y)和(W7 X, Uf y)是在當前時間tc後的某個t時刻Ui和Uj的位置，那麼
T (up Uj) =min、t\t > t c f\ \u i. I c x~uf z | < e Lj八 l"i-( ￡
設用戶Hi在t時刻的位置為
IfX = Ite X +vte. xXt
hy = Ke
在基於近鄰框的檢測中，計算Ui, Uj觸發時間就需要計算不等式組
I (.U1. Ite X-Uf Ite X) + (U1. Ffe- X-Uf Vte x) Xt/ ^ e且 I (.U1. Itf, y~uf Itf, y) + (U1. v 時 y~uf Ffe. y) Xt/ ^ e LJ
對觸發時間的過濾是指僅處理下次更新之前可能會發生近鄰位置關係變化的朋友對。t的計算結果分兩種情況對於"最近的一次位置更新PB，(t+t)的值可能大於b也即在下一次位置更新前，",不會進入的近鄰框。另一種情況是{t+t、的值小於(e，即在&下一次位置更新前，已經進入"i的近鄰框。其中用戶離開近鄰框的過程類似。顯然，只需要對第二種情況的觸發時間進行索引，到該時間點再行處理。步驟(5)、近鄰關係的通告和展示
伺服器在得到移動對象+的檢測結果後，將其近鄰範圍內的所有其朋友ID、當前位置以增量方式通告給移動對象同時也將結果通告給用戶相關的朋友。增量方式通告也即僅通告移動對象近鄰關係的變化，而對沒有變化的近鄰關係不予重複通告。移動對象接收到伺服器的近鄰列表更新信息後，根據用戶的設置進行近鄰展示。如果用戶設置的是基於近鄰框的檢測，就直接展示伺服器的通告信息。如果用戶設置的是顯示基於歐幾裡德距離的近鄰或Dijkstra最短距離近鄰，則需要進一步對伺服器返回的近鄰列表結合地圖信息進行重新篩選和展示。本發明的有益效果本發明方法輸入多個移動對象的朋友關係，移動對象的當前位置，通過計算相鄰兩移動對象的坐標關係，而不是歐幾裡德距離和Dijkstra最短距離，得到兩者的近鄰關係，從而提高計算過程的效率。


圖I本發明的TPR-tree構造的示意 圖2本發明的近鄰索引示意 圖3本發明基於近鄰框的近鄰檢測示意圖。
具體的實施方式
圖I是一棵TPR-tree構造的示意圖，其中(士，u2, ...u10) 10個移動用戶按照空間位置的相似性，遞歸的分為四組，NI, N2, N3, N4, NI和N2又歸結為N5, N3和N4又歸結為N6, N5和N6構成根節點。因為TPR-tree插入、刪除算法其基本過程如下
結點(葉子結點和非葉子結點)的數據項要包含移動對象的標識和包圍其子樹根結點的最小矩形。把包含移動對象的矩形稱為數據矩形；把非葉子結點索引項對應的索引空間稱為目錄矩形。兩種矩形都允許重疊，
查找查找一個移動對象是否存在於索引範圍。對於查找，TPR-tree需要在其結構中查找所有MBR與移動對象PB區域重疊的索引數據。從根節點開始，遞歸搜索MBR與移動對象PB區域重疊的節點項；在到達葉子節點後，測試該葉子節點索引項的MBR是否與移動對象PB區域重疊，返回結果。刪除刪除是插入操作的逆過程。在刪除一個移動對象時，首先確定移動對象所在的葉子節點，然後從該葉子節點中刪除移動對象；如果刪除後節點中的記錄項個數少於規定的閾值，就進行節點的合併，沿TPR-Tree向上，直至到達根節點；最後對各節點對應的MBR進行調整，使得各MBR緊密地包含其下層各個對應的MBR節點。插入插入操作時，新的索引移動對象被加入到葉子節點，如果節點溢出則進行分裂，分裂沿著TPR-Tree向上，直至完成。插入移動對象時，首先需要確定新記錄應該插入到的葉子節點，選擇插入的標準是插入導致的MBR面積增長量最小；隨後，移動對象被插入到相應的葉子節點。如果插入後節點沒有溢出，則不需要進行分裂操作，反之需要進行分裂最後還需要對插入路徑中的MBR進行調整，使得各MBR包含關係緊密。圖2本發明的近鄰索引的基本過程
第一對每個移動用戶的所有朋友建立隊列。第二 標識每個朋友的近鄰關係，根據檢測結果分為三類在未來的某個時間段t內，具有近鄰關係，不具有近鄰關係，在即將到來的某個時刻t』，t』 <t將具有近鄰關係。第三對所有朋友的近鄰關係按照時間進行排序。第四將本地隊列首節點插入全局優先級隊列。圖3本發明基於近鄰框的近鄰檢測的基本過程，即判斷兩移動對象是否位於預先定義的近鄰框範圍之內。本發明所選用的具體實施例如下
步驟(I)、移動對象朋友關係的索引和移動範圍更新；
本發明所指移動對象指具有GPS定位和無線通信能力的智能計算終端。移動對象的朋友關係採用一種兩層的優先級隊列來保持。所述的兩層的優先級隊列的結構具體如下對於每個移動對象維護一個本地的朋友列表優先級隊列，按照觸發時間的大小進行排序。每個移動用戶本地隊列中最早觸發時間的朋友對進入一個全局優先級隊列。當移動用戶Ui位置更新到達後，更新本地的優先級隊列，刪除全局優先級隊列中用戶Ui的相應節點，將本地隊列首節點插入。系統周期性的掃描優先級隊列，對觸發時間到期的朋友對進行近鄰判斷和通告處理。兩層的優先級隊列降低了算法的複雜度，從而優化系統的處理性能。移動對象在每一個更新周期都會採用GPS對自身位置進行定位，採集移動速度和位置信息。取得上一次發往伺服器的預測PrediCtB0X=(G t, LB, LV)。其中其中tr是預測區域的引用時間，G是預測區域的過期時間，Zi 是對象在這一時間段內的物理移動範圍，是根據當前位置信息和移動速度計算的矩形框，ZK是對象的當前移動速度。首先判斷當前時間是否已經超過te ;然後判斷當前位置與預測位置的距離是否位於安全區域，也就是是否在預測的物理移動範圍以上任何一種條件滿足，移動用戶都會 向伺服器發送一個新的預測。如果兩種情況都不是，移動用戶就等待下一個更新周期。步驟(2)、對移動對象進行索引；
伺服器中移動用戶的索引使用TPR-tree (time-parameterized R-tree)。它能夠有效地對移動用戶的當前位置進行索引，並且帶有對象的速度等信息，因此可以對移動用戶進行位置預測。TPR-tree 樹中每個非葉子結點都由多個 MBR(minimum bounding rectangles)及指向子節點的指針組成。MBR為包含其孩子當前的最小邊界矩形。葉子結點由MBR和移動用戶的指針組成。其中MBR為包含對應移動用戶的最小邊界矩形，通過移動用戶的指針可以得到對象的詳細信息。在本發明中，移動用戶的詳細信息包含當前位置信息，以及速度和最近的移動範圍更新信息PB。附圖I對TPR-tree的結構做了詳細說明。步驟(3)、對移動對象進行基於近鄰框的近鄰檢測；
伺服器對於每個超限安全區域更新進行近鄰檢測。超限安全區域更新指的是移動對象移動範圍超越預測區域，其真實位置在預測區域外，移動對象向伺服器發送位置更新信息。本申請的移動對象之間具有相互的朋友關係，但是不同對象可以定製不同近鄰標準，也即不同對象可能具有不同的近鄰標準。例如Uj是Ui的朋友，那麼Ui也是Uj的朋友，但是他們具有不同的近鄰標準.和e P。伺服器接收到移動用戶《的PB消息後，更新其索引節點。它同時維護一個移動用戶《鄰近朋友的列表。伺服器先對列表中的所有朋友進行近鄰檢測，檢測過程使用用戶Ui的近鄰標準e 更新用戶Ui的近鄰朋友列表。接著，伺服器對列表中所有朋友針對^進行近鄰檢測，使用其朋友的近鄰，例如對進行檢測時，就使用標準e J i0對於移動對象的近鄰距離標準為Si jo在某一時刻檢測其朋友列表中的用戶~是否在其近鄰範圍內，基於近鄰框的近鄰檢測就是判斷他們的坐標關係是否滿足k..
X-Uf JTI 彡 ￡■ LJ,且 Iwi. y-Uj. f \ ^ ￡ LJO由於在伺服器中保留是用戶的移動區域預測，對於近鄰關係判斷需要考慮用戶在其安全域區內具體位置的不確定性。給定一個長寬分別為A、B的預測區域，兩個用戶
Uj之間的XY軸方向距離關係有
MaxDX {up Uj) =max {| Ui. x_uf x | _u」 k~Uj. A, 0}MinDX {up Uj) = I Ui. x_uf x | +Oi. k+Uj. A MaxDY {up Uj) = max {| Ui. y_uf y | -Ui. B-W7-. B, 0}
MinDY {up Uj) = I Ui. y_uf y | +Ui. Β+ 7·. B Up Wy之間確定具有近鄰關係的條件是
MaxDX {up Uj) ^ ε ハ ノ 且 MaxDY {up Uj) ^ ε L ノUi, 之間確定不具近鄰關係的條件是MinDX (.Ui, Uj) > ε 且 MinDY {.uir u) > ε
本申請中Ui, Uj具有相互的朋友關係，在對Ui進行近鄰檢測以後，還需要對Uj進行近鄰檢測。為了簡化這ー過程，發明中首先對兩個用戶的近鄰框大小進行判斷，先行檢測較小的近鄰框。如果對於較小的近鄰框，移動用戶Ui, ~都具有近鄰關係，那麼對於另外ー個用戶來說顯然也具有近鄰關係。反之，就需要進ー步判斷對於較大近鄰框的移動用戶是否具 有近鄰關係。檢測完成後，用戶Ui的朋友就分為了三類。在近鄰框以外的，他們就不具有近鄰關係，在近鄰框以內的就具有近鄰關係。由於伺服器保持的是某個用戶的安全區域，通過其速度只能粗略確定其所在位置。當用戶安全區域剛好跨越用戶Ui的近鄰框時，系統就不能判斷他們兩者的近鄰關係。這個時候就需要向該用戶發送查詢信息，通過其最新的安全區域預測了解當前的位置信息，進行近鄰與否檢測，並進行近鄰關係觸發事件的計算。基於近鄰框的檢測過程僅通過判斷兩個移動用戶的坐標關係，在X、y兩個軸向任何ー個方向距離超過用戶的近鄰標準定義即停止檢測。顯然，相比歐幾裡德距離和Dijkstra最短距離簡化了系統的計算開銷。步驟(4)、近鄰關係的索引和觸發事件的計算
採用步驟(I)中所述的兩層的優先級隊列對移動對象的近鄰關係以及觸發時間進行管理。兩個移動用戶的觸發時間T {up Uj)，在本文中是指Uj移動進入Ui近鄰框的最早時間。假設( .心Ui. y)和{uナX, Uf y)是在當前時間tc後的某個t時刻Ui和Uj的位置，那麼
T Kui, Uj) =min ( | > ic Λ \ui. Ic x_uf z I く ε Lj
Λ |も.4ァ-"ァんァ| ( ￡it)
例如用戶Ui在t時刻的位置為
h X ニ し X +Vte-
しy = Ke
在基於近鄰框的檢測中，計算Ui, Uj觸發時間就需要計算不等式組
I KUi. Ite X-Uf Ite X) + (U1. Ffe- X-Uf vte X) Xt/ ^ ε且 I (.U1. Itf, y~uf Itf, y) + ( . V 時 y~uf Ffe. y) Xt/ ^ ε LJ
對觸發時間的過濾是指僅處理下次更新之前可能會發生近鄰位置關係變化的朋友對。t的計算結果分兩種情況對於",.最近的一次位置更新PB，(t+t)的值可能大於し也即在",.下一次位置更新前，~不會進入め.的近鄰框。另ー種情況是{t+t、的值小於し即在め下一次位置更新前，A已經進入"i的近鄰框。其中用戶離開近鄰框的過程類似。顯然，只需要對第二種情況的觸發時間進行索引，到該時間點再行處理。
步驟(5)、近鄰關係的通告和展示
伺服器在得到移動對象め的檢測結果後，將其近鄰範圍內的所有其朋友ID、當前位置以增量方式通告給移動對象め。同時也將結果通告給用戶め相關的朋友。増量方式通告也即僅通告移動對象近鄰關係的變化，而對沒有變化的近鄰關係不予重複通告。 移動對象接收到伺服器的近鄰列表更新信息後，根據用戶的設置進行近鄰展示。如果用戶設置的是基於近鄰框的檢測，就直接展示伺服器的通告信息。如果用戶設置的是顯示基於歐幾裡德距離的近鄰或Dijkstra最短距離近鄰，則需要進ー步對伺服器返回的近鄰列表結合地圖信息進行重新篩選和展示。
權利要求
1.一種移動對象近鄰檢測的方法，其特徵在於該方法包括以下步驟 步驟(I)、移動對象朋友關係的索引和移動範圍更新； 所述移動對象是指具有GPS定位和無線通信能力的智能計算終端； 移動對象的朋友關係採用一種兩層的優先級隊列來保持；所述的兩層的優先級隊列的結構具體如下 對於每個移動對象維護ー個本地的朋友列表優先級隊列，按照觸發時間的大小進行排序；每個移動用戶本地隊列中最早觸發時間的朋友對進入ー個全局優先級隊列；當移動用戶Ui位置更新到達後，更新本地的優先級隊列，刪除全局優先級隊列中用戶Ui的相應節點，將本地隊列首節點插入；系統周期性的掃描優先級隊列，對觸發時間到期的朋友對進行近鄰判斷和通告處理；兩層的優先級隊列降低了算法的複雜度，從而優化系統的處理性能； 移動對象在每ー個更新周期都會採用GPS對自身位置進行定位，採集移動速度和位置信息； 取得上一次發往伺服器的預測PredictBox=(らt, LBrLV);其中ら是預測區域的引用時間，も是預測區域的過期時間，ムガ是對象在這ー時間段內的物理移動範圍，是根據當前位置信息和移動速度計算的矩形框，L V是對象的當前移動速度； 首先判斷當前時間是否已經超過te ;然後判斷當前位置與預測位置的距離是否位於安全區域，也就是是否在預測的物理移動範圍ムガ；以上任何ー種條件滿足，移動用戶都會向伺服器發送ー個新的預測；如果兩種情況都不是，移動用戶就等待下ー個更新周期； 步驟(2)、對移動對象進行索引； 伺服器中移動用戶的索引使用時間參數化的R樹；時間參數化的R樹能夠有效地對移動用戶的當前位置進行索引，並且帶有對象的速度等信息，因此可以對移動用戶進行位置預測； 時間參數化的R樹中每個非葉子結點都由多個最小包含矩形框MBR及指向子節點的指針組成；非葉子結點最小包含矩形框MBR為包含每個非葉子結點孩子當前的最小邊界矩形；葉子結點由最小包含矩形框MBR和移動用戶的指針組成；其中最小包含矩形框MBR為包含對應移動用戶的最小邊界矩形，通過移動用戶的指針可以得到對象的詳細信息；移動用戶的詳細信息包含當前位置信息，以及速度和最近的移動範圍更新信息PB ； 步驟(3)、對移動對象進行基於近鄰框的近鄰檢測； 伺服器對於每個超限安全區域更新進行近鄰檢測；超限安全區域更新指的是移動對象移動範圍超越預測區域，其真實位置在預測區域外，移動對象向伺服器發送位置更新信息；移動對象之間具有相互的朋友關係，但是不同對象可以定製不同近鄰標準，也即不同對象可能具有不同的近鄰標準「受り是め的朋友，那麼Ui也是り的朋友，但是他們具有不同的近鄰標準和ヘン.；伺服器接收到移動用戶的PB消息後，更新其索引節點；它同時維護一個移動用戶鄰近朋友的列表；伺服器先對列表中的所有朋友進行近鄰檢測，檢測過程使用用戶Ui的近鄰標準fり.，更新用戶Ui的近鄰朋友列表；接著，伺服器對列表中所有朋友針對進行近鄰檢測，使用其朋友的近鄰； 對於移動對象Ui, Ui的近鄰距離標準為ε ;在某ー時刻檢測其朋友列表中的用戶Uj是否在其近鄰範圍內，基於近鄰框的近鄰檢測就是判斷他們的坐標關係是否滿足k. x-ufχ\^ ￡ i,j 且 I Ui. y-Uj.ア I ε 且 MinDY {.uir u) > ε 由幹^.，~具有相互的朋友關係，在對め進行近鄰檢測以後，還需要對り進行近鄰檢測；為了簡化這ー過程，首先對兩個用戶的近鄰框大小進行判斷，先行檢測較小的近鄰框；如果對於較小的近鄰框，移動用戶め，~都具有近鄰關係，那麼對於另外一個用戶來說顯然也具有近鄰關係；反之，就需要進ー步判斷對於較大近鄰框的移動用戶是否具有近鄰關係; 檢測完成後，用戶Ui的朋友就分為了三類；在近鄰框以外的，他們就不具有近鄰關係，在近鄰框以內的就具有近鄰關係；由於伺服器保持的是某個用戶的安全區域，通過其速度只能粗略確定其所在位置；當用戶安全區域剛好跨越用戶Ui的近鄰框時，系統就不能判斷他們兩者的近鄰關係；這個時候就需要向該用戶發送查詢信息，通過其最新的安全區域預測了解當前的位置信息，進行近鄰與否檢測，並進行近鄰關係觸發事件的計算； 基於近鄰框的檢測過程僅通過判斷兩個移動用戶的坐標關係，在X、y兩個軸向任何一個方向距離超過用戶的近鄰標準定義即停止檢測； 步驟(4)、近鄰關係的索引和觸發事件的計算 採用步驟(I)中所述的兩層的優先級隊列對移動對象的近鄰關係以及觸發時間進行管理； 兩個移動用戶的觸發時間T {up u)，T {up u)是指Uj移動進入Ui近鄰框的最早時間；假設( .心Ui. y)和{uナX, Uf y)是在當前時間tc後的某個t時刻Ui和Uj的位置，那麼T Kui, Uj) =min ( | > ic Λ \ui. Ic x_uf z I く ε Lj Λ |も.4ァ-"ァんァ| ( ￡it) 設用戶Hi在t時刻的位置為h X ニ し X +Vte- しy = Ke 在基於近鄰框的檢測中，計算Ui, Uj觸發時間就需要計算不等式組I KUi. Ite X-Uf Ite X) + (U1. Ffe- X-Uf vte X) Xt/ ^ ε且 I (.U1. Itf, y~uf Itf, y) + ( . V 時 y~uf Ffe. y) Xt/ ^ ε LJ 對觸發時間的過濾是指僅處理下次更新之前可能會發生近鄰位置關係變化的朋友對；t的計算結果分兩種情況對於",.最近的一次位置更新PB，(t+t)的值可能大於し也即在Ui下一次位置更新前，Uj不會進入Ui的近鄰框；另ー種情況是的值小於te,即在Ui下一次位置更新前，Ui已經進入A的近鄰框；其中用戶離開近鄰框的過程類似；顯然，只需要對第二種情況的觸發時間進行索引，到該時間點再行處理； 步驟(5)、近鄰關係的通告和展示 伺服器在得到移動對象め的檢測結果後，將其近鄰範圍內的所有其朋友ID、當前位置以增量方式通告給移動對象め；同時也將結果通告給用戶Ui相關的朋友；增量方式通告也即僅通告移動對象近鄰關係的變化，而對沒有變化的近鄰關係不予重複通告； 移動對象接收到伺服器的近鄰列表更新信息後，根據用戶的設置進行近鄰展示； 如果用戶設置的是基於近鄰框的檢測，就直接展示伺服器的通告信息； 如果用戶設置的是顯示基於歐幾裡德距離的近鄰或Dijkstra最短距離近鄰，則需要 進ー步對伺服器返回的近鄰列表結合地圖信息進行重新篩選和展示。
全文摘要
本發明涉及一種移動對象近鄰檢測的方法。現有的方法使用歐幾裡德距離或者使用道路網絡中的Dijkstra最短距離進行近鄰檢測，這些方法在大規模的檢測中將消耗大量的CPU計算資源。本發明使用近鄰框對移動對象進行近鄰檢測。採用一種兩層的優先級隊列來記錄索引移動對象之間的近鄰關係，使用時間參數化的R樹對移動對象進行索引。移動對象更新其位置和速度信息後，算法根據預先定義的近鄰框對移動對象的所有朋友進行近鄰檢測。最後將結果通告給相關移動對象。本發明方法輸入多個移動對象的朋友關係、對象的當前位置，由於僅計算相鄰兩移動對象的坐標關係得到近鄰關係，而不是歐幾裡德距離和Dijkstra最短距離，從而提高了計算效率。
文檔編號G01S19/52GK102665164SQ20121006606
公開日2012年9月12日 申請日期2012年3月14日 優先權日2012年3月14日
發明者徐建 申請人:杭州電子科技大學