[發(fā)明專利]一種移動(dòng)對(duì)象近鄰檢測(cè)的方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201210066062.3
• 申請(qǐng)日: 2012-03-14
• 公開(kāi)（公告）號(hào): CN102665164A
• 公開(kāi)（公告）日: 2012-09-12
• 發(fā)明（設(shè)計(jì)）人: 徐建
• 申請(qǐng)（專利權(quán)）人: 杭州電子科技大學(xué)
• 主分類號(hào): H04W4/02
• 分類號(hào): H04W4/02;H04W24/00;G01S19/42;G01S19/52
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 杜軍

1.?一種移動(dòng)對(duì)象近鄰檢測(cè)的方法，其特征在于該方法包括以下步驟：?

步驟(1)、移動(dòng)對(duì)象朋友關(guān)系的索引和移動(dòng)范圍更新；

所述移動(dòng)對(duì)象是指具有GPS定位和無(wú)線通信能力的智能計(jì)算終端；

移動(dòng)對(duì)象的朋友關(guān)系采用一種兩層的優(yōu)先級(jí)隊(duì)列來(lái)保持；所述的兩層的優(yōu)先級(jí)隊(duì)列的結(jié)構(gòu)具體如下：

對(duì)于每個(gè)移動(dòng)對(duì)象維護(hù)一個(gè)本地的朋友列表優(yōu)先級(jí)隊(duì)列，按照觸發(fā)時(shí)間的大小進(jìn)行排序；每個(gè)移動(dòng)用戶本地隊(duì)列中最早觸發(fā)時(shí)間的朋友對(duì)進(jìn)入一個(gè)全局優(yōu)先級(jí)隊(duì)列；當(dāng)移動(dòng)用戶u_i位置更新到達(dá)后，更新本地的優(yōu)先級(jí)隊(duì)列，刪除全局優(yōu)先級(jí)隊(duì)列中用戶u_i的相應(yīng)節(jié)點(diǎn)，將本地隊(duì)列首節(jié)點(diǎn)插入；系統(tǒng)周期性的掃描優(yōu)先級(jí)隊(duì)列，對(duì)觸發(fā)時(shí)間到期的朋友對(duì)進(jìn)行近鄰判斷和通告處理；兩層的優(yōu)先級(jí)隊(duì)列降低了算法的復(fù)雜度，從而優(yōu)化系統(tǒng)的處理性能；

移動(dòng)對(duì)象在每一個(gè)更新周期都會(huì)采用GPS對(duì)自身位置進(jìn)行定位，采集移動(dòng)速度和位置信息；

取得上一次發(fā)往服務(wù)器的預(yù)測(cè)PredictBox=(t_r,t_e,LB，LV)?；其中t_r是預(yù)測(cè)區(qū)域的引用時(shí)間，t_e是預(yù)測(cè)區(qū)域的過(guò)期時(shí)間，LB是對(duì)象在這一時(shí)間段內(nèi)的物理移動(dòng)范圍，是根據(jù)當(dāng)前位置信息和移動(dòng)速度計(jì)算的矩形框，LV是對(duì)象的當(dāng)前移動(dòng)速度；

首先判斷當(dāng)前時(shí)間是否已經(jīng)超過(guò)t_e；然后判斷當(dāng)前位置與預(yù)測(cè)位置的距離是否位于安全區(qū)域，也就是是否在預(yù)測(cè)的物理移動(dòng)范圍LB；以上任何一種條件滿足，移動(dòng)用戶都會(huì)向服務(wù)器發(fā)送一個(gè)新的預(yù)測(cè)；如果兩種情況都不是，移動(dòng)用戶就等待下一個(gè)更新周期；

步驟(2)、對(duì)移動(dòng)對(duì)象進(jìn)行索引；

服務(wù)器中移動(dòng)用戶的索引使用時(shí)間參數(shù)化的R樹；時(shí)間參數(shù)化的R樹能夠有效地對(duì)移動(dòng)用戶的當(dāng)前位置進(jìn)行索引，并且?guī)в袑?duì)象的速度等信息，因此可以對(duì)移動(dòng)用戶進(jìn)行位置預(yù)測(cè)；

時(shí)間參數(shù)化的R樹中每個(gè)非葉子結(jié)點(diǎn)都由多個(gè)最小包含矩形框MBR及指向子節(jié)點(diǎn)的指針組成；非葉子結(jié)點(diǎn)最小包含矩形框MBR為包含每個(gè)非葉子結(jié)點(diǎn)孩子當(dāng)前的最小邊界矩形；葉子結(jié)點(diǎn)由最小包含矩形框MBR和移動(dòng)用戶的指針組成；其中最小包含矩形框MBR為包含對(duì)應(yīng)移動(dòng)用戶的最小邊界矩形，通過(guò)移動(dòng)用戶的指針可以得到對(duì)象的詳細(xì)信息；移動(dòng)用戶的詳細(xì)信息包含當(dāng)前位置信息，以及速度和最近的移動(dòng)范圍更新信息PB；

步驟(3)、對(duì)移動(dòng)對(duì)象進(jìn)行基于近鄰框的近鄰檢測(cè)；

服務(wù)器對(duì)于每個(gè)超限安全區(qū)域更新進(jìn)行近鄰檢測(cè)；超限安全區(qū)域更新指的是移動(dòng)對(duì)象移動(dòng)范圍超越預(yù)測(cè)區(qū)域，其真實(shí)位置在預(yù)測(cè)區(qū)域外，移動(dòng)對(duì)象向服務(wù)器發(fā)送位置更新信息；移動(dòng)對(duì)象之間具有相互的朋友關(guān)系，但是不同對(duì)象可以定制不同近鄰標(biāo)準(zhǔn)，也即不同對(duì)象可能具有不同的近鄰標(biāo)準(zhǔn)；設(shè)u_j是u_i的朋友，那么u_i也是u_j的朋友，但是他們具有不同的近鄰標(biāo)準(zhǔn)ε_i,j和ε_j,i；服務(wù)器接收到移動(dòng)用戶的PB消息后，更新其索引節(jié)點(diǎn)；它同時(shí)維護(hù)一個(gè)移動(dòng)用戶鄰近朋友的列表；服務(wù)器先對(duì)列表中的所有朋友進(jìn)行近鄰檢測(cè)，檢測(cè)過(guò)程使用用戶u_i的近鄰標(biāo)準(zhǔn)ε_i,j，更新用戶u_i的近鄰朋友列表；接著，服務(wù)器對(duì)列表中所有朋友針對(duì)u_i進(jìn)行近鄰檢測(cè)，使用其朋友的近鄰；

對(duì)于移動(dòng)對(duì)象u_i，u_i的近鄰距離標(biāo)準(zhǔn)為ε_i,j；在某一時(shí)刻檢測(cè)其朋友列表中的用戶u_j是否在其近鄰范圍內(nèi)，基于近鄰框的近鄰檢測(cè)就是判斷他們的坐標(biāo)關(guān)系是否滿足|u_i.x-u_j.x|≤ε_i,j且|u_i.y-u_j.y|≤ε_i,j；

由于在服務(wù)器中保留是用戶的移動(dòng)區(qū)域預(yù)測(cè)，對(duì)于近鄰關(guān)系判斷需要考慮用戶在其安全域區(qū)內(nèi)具體位置的不確定性；給定一個(gè)長(zhǎng)寬分別為A、B的預(yù)測(cè)區(qū)域，兩個(gè)用戶u_i,?u_j之間的XY軸方向距離關(guān)系有:

MaxDX(u_i,u_j)=max{|u_i.x-u_j.x|-u_i.A-u_j.A,0}??

MinDX(u_i,u_j)=?|u_i.x-u_j.x|+u_i.A+u_j.A

MaxDY(u_i,u_j)=?max{|u_i.y-u_j.y|-u_i.B-u_j.B,0}?

MinDY(u_i,u_j)=?|u_i.y-u_j.y|+u_i.B+u_j.B?

u_i,u_j之間確定具有近鄰關(guān)系的條件是

MaxDX(u_i,u_j)?≤ε_i,j且MaxDY(u_i,u_j)?≤ε_i,j

u_i,u_j之間確定不具近鄰關(guān)系的條件是

MinDX(u_i,u_j)?>ε_i,j且MinDY(u_i,u_j)?>ε_i,j

由于u_i，u_j具有相互的朋友關(guān)系，在對(duì)u_i進(jìn)行近鄰檢測(cè)以后，還需要對(duì)u_j進(jìn)行近鄰檢測(cè)；為了簡(jiǎn)化這一過(guò)程，首先對(duì)兩個(gè)用戶的近鄰框大小進(jìn)行判斷，先行檢測(cè)較小的近鄰框；如果對(duì)于較小的近鄰框，移動(dòng)用戶u_i，u_j都具有近鄰關(guān)系，那么對(duì)于另外一個(gè)用戶來(lái)說(shuō)顯然也具有近鄰關(guān)系；反之，就需要進(jìn)一步判斷對(duì)于較大近鄰框的移動(dòng)用戶是否具有近鄰關(guān)系；

檢測(cè)完成后，用戶u_i的朋友就分為了三類；在近鄰框以外的，他們就不具有近鄰關(guān)系，在近鄰框以內(nèi)的就具有近鄰關(guān)系；由于服務(wù)器保持的是某個(gè)用戶的安全區(qū)域，通過(guò)其速度只能粗略確定其所在位置；當(dāng)用戶安全區(qū)域剛好跨越用戶u_i的近鄰框時(shí)，系統(tǒng)就不能判斷他們兩者的近鄰關(guān)系；這個(gè)時(shí)候就需要向該用戶發(fā)送查詢信息，通過(guò)其最新的安全區(qū)域預(yù)測(cè)了解當(dāng)前的位置信息，進(jìn)行近鄰與否檢測(cè)，并進(jìn)行近鄰關(guān)系觸發(fā)事件的計(jì)算；

基于近鄰框的檢測(cè)過(guò)程僅通過(guò)判斷兩個(gè)移動(dòng)用戶的坐標(biāo)關(guān)系，在x、y兩個(gè)軸向任何一個(gè)方向距離超過(guò)用戶的近鄰標(biāo)準(zhǔn)定義即停止檢測(cè)；

步驟(4)、近鄰關(guān)系的索引和觸發(fā)事件的計(jì)算

采用步驟(1)中所述的兩層的優(yōu)先級(jí)隊(duì)列對(duì)移動(dòng)對(duì)象的近鄰關(guān)系以及觸發(fā)時(shí)間進(jìn)行管理；

兩個(gè)移動(dòng)用戶的觸發(fā)時(shí)間T(u_i,u_j)，T(u_i,u_j)是指u_j移動(dòng)進(jìn)入u_i近鄰框的最早時(shí)間；假設(shè)(u_i.x，u_i.y)和(u_j.x，u_j.y)是在當(dāng)前時(shí)間t_c后的某個(gè)t時(shí)刻u_i和u_j的位置,那么

T(u_i,u_j)=min(t|t≥t_c∧|u_i.l_t.x-u_j.l_t.x|≤ε_i,j

∧|u_i.l_t.y-u_j.l_t.y|≤ε_i,j)

設(shè)用戶u_i在t時(shí)刻的位置為：

l_t.x?=?l_te.x?+v_te.x×t????????

l_t.y?=?l_te.y+v_te.y×t?????????????????????????????

在基于近鄰框的檢測(cè)中，計(jì)算u_i,u_j觸發(fā)時(shí)間就需要計(jì)算不等式組

??|?(u_i.l_te.x-u_j.l_te.x)?+(u_i.v_te.x-u_j.v_te.x)?×t|≤ε_i,j

且|?(u_i.l_te.y-u_j.l_te.y)?+(u_i.v_te.y-u_j.v_te.y)?×t|≤ε_i,j

對(duì)觸發(fā)時(shí)間的過(guò)濾是指僅處理下次更新之前可能會(huì)發(fā)生近鄰位置關(guān)系變化的朋友對(duì)；t的計(jì)算結(jié)果分兩種情況：對(duì)于u_i最近的一次位置更新PB，(t_c+t)的值可能大于t_e，也即在u_i下一次位置更新前，u_j不會(huì)進(jìn)入u_i的近鄰框；另一種情況是(t_c+t)的值小于t_e，即在u_i下一次位置更新前，u_j已經(jīng)進(jìn)入u_i的近鄰框；其中用戶離開(kāi)近鄰框的過(guò)程類似；顯然，只需要對(duì)第二種情況的觸發(fā)時(shí)間進(jìn)行索引，到該時(shí)間點(diǎn)再行處理；

步驟(5)、近鄰關(guān)系的通告和展示

服務(wù)器在得到移動(dòng)對(duì)象u_i的檢測(cè)結(jié)果后，將其近鄰范圍內(nèi)的所有其朋友ID、當(dāng)前位置以增量方式通告給移動(dòng)對(duì)象u_i；同時(shí)也將結(jié)果通告給用戶u_i相關(guān)的朋友；增量方式通告也即僅通告移動(dòng)對(duì)象近鄰關(guān)系的變化，而對(duì)沒(méi)有變化的近鄰關(guān)系不予重復(fù)通告；

移動(dòng)對(duì)象接收到服務(wù)器的近鄰列表更新信息后，根據(jù)用戶的設(shè)置進(jìn)行近鄰展示；

如果用戶設(shè)置的是基于近鄰框的檢測(cè)，就直接展示服務(wù)器的通告信息；

如果用戶設(shè)置的是顯示基于歐幾里德距離的近鄰或Dijkstra最短距離近鄰，則需要進(jìn)一步對(duì)服務(wù)器返回的近鄰列表結(jié)合地圖信息進(jìn)行重新篩選和展示。