葉　李

(中國西南電子技術(shù)研究所，成都 610036)

?

分布式網(wǎng)絡(luò)中CKNN查詢的BORA優(yōu)化匯聚

葉李

(中國西南電子技術(shù)研究所，成都 610036)

摘要：針對時空數(shù)據(jù)庫中，移動對象軌跡的連續(xù)K近鄰查詢(continuousKnearest neighbor query，CKNN)的查詢效率較低的問題，以及在分布式的移動對象數(shù)據(jù)庫(moving objects databases，MOD)環(huán)境下，提升對應(yīng)查詢結(jié)果的數(shù)據(jù)匯聚效率問題進行了研究。在CKNN查詢中，設(shè)計優(yōu)化了查詢海灘線的更新算法，通過在軌跡數(shù)據(jù)結(jié)構(gòu)中增加更新標志位，減少了軌跡線段參與的判定運算；同時在假設(shè)的類網(wǎng)格覆蓋的分布式空間環(huán)境下，利用基于Bresenham覆蓋的路由匯聚(Bresenham-based overlay for routing and aggregation，BORA)方法，進行查詢結(jié)果的匯聚；并針對不同近鄰參數(shù)、軌跡數(shù)目、移動對象速度、匯聚方式等對查詢時間的影響進行了仿真實驗；仿真結(jié)果表明，不同參數(shù)數(shù)值的增加延長了處理時間，基于BORA的匯聚方式比一般的匯聚方式節(jié)省了更多的處理時間，提高了系統(tǒng)查詢及處理的效率。

關(guān)鍵詞：移動對象數(shù)據(jù)庫；連續(xù)K近鄰查詢；查詢匯聚；BORA算法

0引言

在基于定位系統(tǒng)的移動對象相關(guān)應(yīng)用中，作為基礎(chǔ)技術(shù)的移動對象數(shù)據(jù)庫 (moving objects databases, MOD)得到了廣泛應(yīng)用[1-3]。目前，移動對象數(shù)據(jù)庫的研究和應(yīng)用主要集中在高效的數(shù)據(jù)存儲、管理、時空數(shù)據(jù)的獲取以及各種數(shù)據(jù)查詢的處理等方面。大部分的研究工作都基于存在一個中心服務(wù)器，進行集中處理的假設(shè)，這實際上限制了移動對象數(shù)據(jù)庫的應(yīng)用范圍。本文在前期工作的基礎(chǔ)上[4]，針對分布式處理環(huán)境條件下，基于典型類網(wǎng)格結(jié)構(gòu)下的移動對象數(shù)據(jù)服務(wù)進行研究。

在類網(wǎng)格結(jié)構(gòu)的傳感器網(wǎng)絡(luò)條件下，每個網(wǎng)格存在一個基站(base station ,BS)。基站所對應(yīng)的移動對象數(shù)據(jù)由基站所配備的移動對象數(shù)據(jù)庫服務(wù)保存?；局g的通信由相鄰節(jié)點彼此連接，各個基站負責的通信范圍包括2個方面，一是在基站范圍內(nèi)的所有移動對象用戶，其次是基站對應(yīng)的相鄰節(jié)點?；靖鶕?jù)需要與相鄰基站建立通信鏈接并傳輸數(shù)據(jù)，并且基站將處理對應(yīng)網(wǎng)格范圍內(nèi)所提交的時空數(shù)據(jù)查詢。在類網(wǎng)格條件下的查詢處理中，移動對象數(shù)據(jù)庫中的對象移動軌跡在所提交的查詢時間范圍條件下通?？赡芸缭搅硕鄠€網(wǎng)格。因此，彼此相鄰的基站所返回的查詢結(jié)果通常包含了冗余數(shù)據(jù)。為了提高通信性能，查詢結(jié)果在向目的基站傳輸?shù)耐局袑⒆裱欢ǖ穆酚珊蛥R聚策略。一個理想的路由匯聚策略必須包含以下特性，首先能實現(xiàn)查詢結(jié)果的部分匯聚，其次是保留一定程度上的并行處理能力以避免過于頻繁的數(shù)據(jù)匯聚[4]。

在基于Bresenham覆蓋的路由匯聚方法(Bresenham-based overlay for routing and aggregation，BORA)的前期工作中[4]，包含多個網(wǎng)格的范圍查詢結(jié)果通過BORA算法在全局范圍內(nèi)數(shù)據(jù)匯聚與傳輸?shù)男阅苌先〉昧孙@著效果。實驗中，一個網(wǎng)格內(nèi)的范圍查詢結(jié)果是全部查詢結(jié)果的一部分，多個部分查詢結(jié)果沿著查詢節(jié)點到匯聚節(jié)點的Bresenham路徑進行數(shù)據(jù)的匯聚操作，通過數(shù)據(jù)匯聚消除了冗余，實際上在數(shù)據(jù)傳輸過程中減少了數(shù)據(jù)傳輸量，節(jié)省了傳輸時間。

就連續(xù)K近鄰查詢來說，BORA算法的應(yīng)用在操作中與范圍查詢并不一樣。本文就連續(xù)K近鄰查詢結(jié)果在類網(wǎng)格模式下的BORA匯聚方式進行了研究，確認具體的匯聚方式，并通過實驗結(jié)果驗證了BORA算法對連續(xù)K近鄰查詢結(jié)果在匯聚與傳輸方面起到提高性能的作用，并確定了相關(guān)的影響因素。

1相關(guān)工作

分布式移動對象數(shù)據(jù)庫就架構(gòu)設(shè)計而言，并行計算與分布式數(shù)據(jù)庫系統(tǒng)是其發(fā)展的兩個基礎(chǔ)技術(shù)，這也是數(shù)據(jù)庫系統(tǒng)中兩個重要的研究領(lǐng)域。隨著技術(shù)的發(fā)展，移動對象數(shù)據(jù)庫系統(tǒng)與應(yīng)用得到了越來越多的關(guān)注。近年來，許多的研究工作都集中在移動對象數(shù)據(jù)庫中關(guān)于數(shù)據(jù)查詢的有效性處理方面。這些查詢都基于不同的運動模型，一種是有關(guān)于定位和時間的序列更新數(shù)據(jù)[5-6]，另一種是在前一種的基礎(chǔ)上增加了運動的速度信息[7]。關(guān)于移動對象數(shù)據(jù)庫的主要研究工作集中在數(shù)據(jù)的有效存儲、時空數(shù)據(jù)的獲取以及不同的數(shù)據(jù)查詢處理方面。大部分研究工作都假設(shè)存在一個包含移動對象數(shù)據(jù)庫的集中處理環(huán)境，即存在一個中心服務(wù)器處理相關(guān)的數(shù)據(jù)查詢和其他的對應(yīng)操作。

與之相對應(yīng)的分布式環(huán)境中，文獻[8-9]研究了授權(quán)的移動用戶方對時空查詢的部分結(jié)果進行保存和相關(guān)維護的技術(shù)，另外增加查詢-認知技術(shù)的航位推算更新策略[5]也將顯著節(jié)省通信成本。但就這種方式而言，這種近似移動對象數(shù)據(jù)庫的處理能力也是假設(shè)為中心集成式的。項目MobiEyes[8-9]研究了服務(wù)器與一系列移動客戶端之間，在最小化全局通信下的負載平衡問題。在這個項目中，其運動模型包含了定位、時間和速度，并且航位推算策略也擴展為包含了保存和維護連續(xù)查詢結(jié)果的技術(shù)。在傳感器網(wǎng)絡(luò)環(huán)境下，關(guān)于路由樹生成和部分查詢結(jié)果匯聚技術(shù)已經(jīng)得到了一定的應(yīng)用[10-11]。匯聚的主要目的在于減少參與節(jié)點的能耗，延長整個網(wǎng)絡(luò)的生存周期并保證數(shù)據(jù)質(zhì)量。文獻[12]就傳感器網(wǎng)絡(luò)環(huán)境中的并行和并發(fā)數(shù)據(jù)傳輸問題進行了研究，以節(jié)能為主要目的，解決了最小化包碰撞和丟棄的問題。

在與相關(guān)的網(wǎng)絡(luò)通信問題方面，項目ECO[13]對給定網(wǎng)絡(luò)下建立通信模式，以實現(xiàn)有效的數(shù)據(jù)并發(fā)應(yīng)用這一問題進行了研究。本文通過運用與文獻[13]類似的簡單網(wǎng)絡(luò)架構(gòu)模型，來驗證在分布式環(huán)境下，基于BORA算法的連續(xù)K近鄰查詢的匯聚方式及其對性能產(chǎn)生影響的相關(guān)因素。

另外，近鄰查詢一直是近十多年來時空數(shù)據(jù)庫研究中的核心問題。隨著移動定位服務(wù)(mobile location services, MLS)的發(fā)展，針對歷史軌跡數(shù)據(jù)的K近鄰查詢已成為數(shù)據(jù)分析的重要手段，在此基礎(chǔ)上對服務(wù)進行改進或提出新的服務(wù)模式。文獻[14]就歷史軌跡數(shù)據(jù)中的近鄰查詢進行了廣泛細致的分析，確定了基本的查詢分類和算法；文獻[15-16]就歷史軌跡數(shù)據(jù)中的軌跡的連續(xù)近鄰查詢進行了更深入的分析，設(shè)計了BFTKNN算法。但他們的主要工作都集中在減少類R樹(R-tree-like)結(jié)構(gòu)中的節(jié)點訪問次數(shù)及對最優(yōu)遍歷和最深遍歷算法的研究上，主要目的是減少主存和CPU耗用。但就迭代更新查詢結(jié)果的優(yōu)化問題上，并沒有得到深入的研究。本文針對類R樹的數(shù)據(jù)結(jié)構(gòu)中保存的移動對象歷史軌跡數(shù)據(jù)連續(xù)K近鄰查詢進行了研究，主要的工作集中在迭代更新查詢結(jié)果的優(yōu)化問題上。

2CKNN查詢及優(yōu)化

一般情況下，連續(xù)最近鄰查詢的結(jié)果保存在一個鏈表中，表示為NodeList。鏈表NodeList中存儲的數(shù)據(jù)結(jié)構(gòu)表示為Node，每個Node包含了軌跡ID、運動參數(shù)、開始時間、結(jié)束時間、最大距離、最小距離及更新標志。為了加快查詢速度，每個NodeList對象中還包含了整個鏈表的最大距離和最小距離值。連續(xù)K近鄰查詢的結(jié)果是多個NodeList構(gòu)成的列表，記為NodeTable。

鏈表NodeList通常包含多個Node，每個Node對應(yīng)不同的軌跡數(shù)據(jù)，與查詢軌跡之間的距離根據(jù)時間變化成拋物線模式。在實際的幾何形狀上看來，整個NodeList的數(shù)據(jù)表現(xiàn)為一條海灘線，具體的一個例子如圖1中的虛線OldLine所示。在多近鄰查詢的情況下，當?shù)乱粭l對應(yīng)的NodeList時，對應(yīng)海灘線上的每一段拋物線都需要通過距離比較判定軌跡對應(yīng)的拋物線，以確定更近鄰節(jié)點段，最后生成新的海灘線，如圖1中的NewLine所示。如果對NodeTable中每層NodeList中的每段Node都進行類似的判定比較，則更新算法的速度必定非常緩慢。

由圖1可知，判定軌跡的拋物線線段A完全取代了線段1成為更近鄰，在這種情況下，原存在的各層近鄰節(jié)點實際上逐層升高成為上一層近鄰，而線段A成為最近鄰；類似的情況也存在線段C上，形成的最近鄰海灘線如圖1中紅色線段所示，包括了線段A、線段2的右半邊和線段3的左半邊及線段C；關(guān)于線段B，由于并不能確定該線段成為第2層近鄰，所以必須跟下一層NodeList進行判定。按此方式依次進行逐層檢測判定，直至完成NodeTable的更新。隨著層次的增加，所需進行判定的拋物線線段也逐層減少。

為了優(yōu)化K近鄰查詢效率，提高迭代更新近鄰列表的速度，文中在判定軌跡對應(yīng)的NewNode結(jié)構(gòu)中增加更新標志位。通過標志位的布爾開關(guān)，決定該部分軌跡線段是否參與主要耗時的判定運算。初始判定時，設(shè)置標志位初值為真，根據(jù)NewNode替代NodeList中的Node節(jié)點成為更近鄰的不同情況，將NewNode節(jié)點根據(jù)需要拆分，成為更近鄰的部分線段時其標志位設(shè)置為假，未成為更近鄰部分線段時對應(yīng)的標志位設(shè)置為真。

圖1　近鄰海灘線的更新Fig.1　Update of nearest neighbor beach line

優(yōu)化更新K近鄰NodeTable結(jié)構(gòu)的算法UpdateKNNTable如算法1所示。在基于類R樹的數(shù)據(jù)結(jié)構(gòu)上的最優(yōu)或最深遍歷的基礎(chǔ)上，確定需要判定的軌跡節(jié)點，作為算法的輸入?yún)?shù)。算法首先將該軌跡數(shù)據(jù)初始化成一近鄰鏈表NodeList，其中，僅有包含該軌跡信息的一個節(jié)點。然后根據(jù)NodeTable的大小，從最近鄰開始，調(diào)用算法UpdateBeachLine，更新逐層對應(yīng)的NodeList。UpdateBeachLine接收傳入?yún)?shù)，是該層對應(yīng)的K-NodeList和更新鏈表NodeList，返回布爾變量bupdate和新生鏈表NewNodeList。在UpdateBeachLine的執(zhí)行中，實際上將K-NodeList和NodeList中對應(yīng)的節(jié)點在根據(jù)距離遠近的情況下進行了拆分和互換。布爾變量bupdate實際上是更新后的NodeList中各節(jié)點更新標志的或值，如果該值為假，則表示NodeList作為一個新對象取代了原來的K近鄰鏈表，因此將其值插入到(K+1)-NodeList之前。如果該值為真，說明NodeList中至少存在一個節(jié)點包含需要判定的軌跡節(jié)點，因此將經(jīng)過UpdateBeachLine更新后的NodeList作為下一次調(diào)用的傳入?yún)?shù)，迭代更新海灘線(K+1)-NodeList。

算法1: UpdateKNNTable

Input: 判定軌跡Trajectory

Output: 更新后的NodeTable

1將Trajectory數(shù)據(jù)初始化成一NodeList對象；

2如果NodeTable的大小為0，則將NodeList加入到NodeTable對象中；返回。

3否則循環(huán)，從NodeTable的最近鄰鏈表開始，掃描各層K對應(yīng)的K-NodeList；

4如果NodeList的最小距離大于K-NodeList的最大距離，繼續(xù)循環(huán)；

5否則UpdateBeachLine(K-NodeList, NodeList)，接收返回值bupdate以及更新后鏈表NodeList；

6如果bupdate為假，將NodeList插入在(K+1)-NodeList之前；跳出循環(huán)；

7否則更新后的NodeList作為傳入?yún)?shù)，繼續(xù)下一層循環(huán)；

8如果NodeTable中鏈表數(shù)目小于K，將NodeList插入到NodeTable最后一行；大于K則將最后一行刪除。

更新海灘線的具體操作如算法2所示。首先按時間順序查找NodeList中更新標志為新的Node節(jié)點，得到Node節(jié)點的時間信息后，在K-NodeList中確定對應(yīng)時間段的節(jié)點K-Node，進行比較判別。具體的情況可大致分為6類，如圖2所示。圖2a對應(yīng)算法2中2-3行，這是最簡單的情況，其余的判定都需要根據(jù)兩軌跡間距離方程的Delta數(shù)值進行判定。當Delta小于0，即兩拋物線沒有交點的情況，對應(yīng)圖2b和算法2中的5-7行。Delta等于0的情況對應(yīng)圖2c和算法2中8-10行。比較復(fù)雜的情況是當Delta大于0時，這時又需要分為多種情形進行判定。第1種情形是兩交點對應(yīng)的時間點t1和t2不在節(jié)點對應(yīng)時間段[Ts,Te]，如圖2d所示，主要存在A,B,C3種模式，但可直接通過判別節(jié)點在對應(yīng)時間段的最大值方式確定交換與否，對應(yīng)算法2中12-14行；第2種情形即t1和t2都在對應(yīng)時間段[Ts,Te]，則需要將Node和K-Node都根據(jù)t1和t2拆分成3段，進行拼接，如圖2e所示，對應(yīng)算法2中15-17行；最后的一種情形則是僅有一個交點對應(yīng)的時間點在[Ts,Te]，如圖2f所示，對應(yīng)算法2中18-20行，Node和K-Node根據(jù)交點時刻拆分成2段后進行拼接。

圖2　近鄰軌跡的比較Fig.2　Comparison of nearest neighbor trajectory

通過Node和K-Node的拆分拼接或交換操作，提高了K近鄰更新操作的效率。而Node結(jié)構(gòu)中增加更新標志位的方式，使得每層NodeList更新操作時需要檢查的節(jié)點降低到最少。

算法2: UpdateBeachLine

Input:K-NodeList, NodeList

Output: bupdate及更新后鏈表NodeList

1循環(huán)，查找NodeList中更新標志為真的Node，確定在K-NodeList對應(yīng)時間段的K-Node，進行判別；

2如果Node的最大值小于K-Node的最小值，在K-NodeList和NodeList中的對應(yīng)時間段內(nèi)，互換節(jié)點，Node的更新標志設(shè)置為假；

3另外如果K-Node的最大值小于Node的最小值，循環(huán)繼續(xù)；

4其他情況下根據(jù)兩軌跡段間的距離方程，確定其Delta數(shù)值；

5Delta小于0時：

6如果Node的最大值小于K-Node的最大值，互換節(jié)點，Node的更新標志設(shè)置為假；

7否則，循環(huán)繼續(xù)；

8Delta等于0時：

9如果Node的最大值小于K-Node的最大值，互換節(jié)點，Node的更新標志設(shè)置為假；

10否則，循環(huán)繼續(xù)；

11Delta大于0時：

12如果兩個交點對應(yīng)的時間點t1和t2都不在節(jié)點對應(yīng)的時間段內(nèi)：

13如果Node的最大值小于K-Node的最大值，互換節(jié)點，Node的更新標志設(shè)置為假；

14否則，循環(huán)繼續(xù)；

15如果兩個交點對應(yīng)的時間點t1和t2都在節(jié)點對應(yīng)的時間段內(nèi)，將Node和K-Node根據(jù)t1和t2分別拆分成三段；

16如果Node的最小值大于K-Node的最小值，將K-Node原本對應(yīng)的節(jié)點用t1前的k-Node，t1到t2時刻的Node(對應(yīng)更新標志設(shè)置為假)，t2后的K-Node形成的鏈表代替；而Node對應(yīng)的節(jié)點用t1前的Node，t1到t2時刻的K-Node，t2后的Node形成的鏈表代替；

17否則將k-Node原本對應(yīng)的節(jié)點用t1前的NewNode(對應(yīng)更新標志設(shè)置為假)，t1到t2時刻的K-Node，t2后的NewNode(對應(yīng)更新標志設(shè)置為假)形成的鏈表代替；而NewNode對應(yīng)的節(jié)點用t1前的K-Node，t1到t2時刻的NewNode，t2后的K-Node形成的鏈表代替；

18如果兩個交點對應(yīng)的時間點僅存在一個時間點t在節(jié)點對應(yīng)的時間段內(nèi)，則將Node和K-Node根據(jù)t分別拆分成兩段；

19如果Node在t時刻的值大于K-Node，將K-Node原本對應(yīng)的節(jié)點用t時刻前的K-Node，t后的Node(對應(yīng)更新標志設(shè)置為假)形成的鏈表代替；而Node對應(yīng)的節(jié)點用t時刻前的Node，t后的K-Node形成的鏈表代替；

20否則將K-Node原本對應(yīng)的節(jié)點用t時刻前的Node(對應(yīng)更新標志設(shè)置為假)，t后的K-Node形成的鏈表代替；而Node對應(yīng)的節(jié)點用t時刻前的K-Node，t后Node的形成的鏈表代替；

21更新布爾變量bupdate，其值取決于NodeList中所有節(jié)點更新標志或的結(jié)果。

3網(wǎng)絡(luò)設(shè)置及BORA匯聚

一般來說，移動對象的軌跡定義為一個序列的點的集合，表示為Tr={(x1,y1,t1), (x2,y2,t2),…,(xn,yn,tn)}，當(i移動。對數(shù)據(jù)查詢、對象跟蹤以及其他相關(guān)應(yīng)用來說，移動對象向管理對應(yīng)覆蓋移動區(qū)域的服務(wù)器傳輸其地址及時間信息，實際上就是對應(yīng)的軌跡線段信息。在本文的設(shè)定中，每個MOD服務(wù)器僅僅管理其對應(yīng)網(wǎng)格區(qū)域內(nèi)的對象軌跡信息，而各個網(wǎng)格也是對應(yīng)BS所覆蓋的區(qū)域，負責移動對象在此區(qū)域內(nèi)通過時的通信；每個網(wǎng)格內(nèi)也存在服務(wù)器處理針對對象軌跡的時空查詢。

在網(wǎng)絡(luò)通信方面，本文所設(shè)定的類網(wǎng)格網(wǎng)絡(luò)中，各網(wǎng)格中對應(yīng)的服務(wù)器也假設(shè)通過相鄰節(jié)點進行通信的彼此連接。為了計算和評估實際的通信容量，需要考慮多方面的因素，包括通信鏈接的容量、往返時延(round-trip time,RTT)、發(fā)送/接收窗口大小、數(shù)據(jù)包的錯誤率或丟失率等[13]。在本文的研究工作中，為了評估2臺服務(wù)器之間通信性能，設(shè)定傳輸n個數(shù)據(jù)包所消耗的時間的計算方式為：t1+t2×n，其中，t1表示在服務(wù)器之間建立鏈接的往返時延；t2表示單位數(shù)據(jù)包接收所消耗的時間，可近似計算為：接收窗口大小/RTT。

針對路由和結(jié)果匯聚的BORA算法是基于Bresenham直線算法的思想來處理在類網(wǎng)格覆蓋的分布式空間環(huán)境下，查詢區(qū)域向匯聚中心如何匯聚與傳輸查詢結(jié)果的問題[2]。Bresenham直線算法是用來描繪由2點所決定的直線的算法，它會算出一條線段在n維光柵上最接近的點。這個算法只會用到較為快速的整數(shù)加法、減法和位元移位，常用于繪制計算機畫面中的直線，是計算機圖形學中最先發(fā)展出來的算法[12]。

BORA算法通過各查詢區(qū)域與匯聚中心的Bresenham路徑構(gòu)建BORA樹。通常在給定的一個查詢范圍，其區(qū)域為一個任意的多邊形，表示為R；在網(wǎng)絡(luò)中，與R相交的網(wǎng)格區(qū)域節(jié)點都將參與此給定范圍查詢的運算，所有參與運算的節(jié)點表示為CR={C1,C2,…}；而節(jié)點查詢結(jié)果所匯聚向的對象節(jié)點表示為Cd。通過Cd和所有CR成員之間的Bresenham路徑的網(wǎng)格節(jié)點都將是參與查詢或結(jié)果匯聚的節(jié)點。各個節(jié)點通過執(zhí)行BORA樹的構(gòu)造算法建立了一個虛擬的BORA匯聚樹，BORA樹以匯聚中心為根，Bresenham路徑上節(jié)點為各中間節(jié)點，CR中的節(jié)點為葉節(jié)點。由于對象節(jié)點相對查詢區(qū)域而言存在有多種可能位置，BORA樹的根節(jié)點可能擁有1—8個子節(jié)點。這些特殊情況包括對象節(jié)點與查詢區(qū)域的凸包的2個頂點共線或者就在查詢區(qū)域內(nèi)等。在BORA樹構(gòu)造完成后，各個節(jié)點服務(wù)器上在獲取本地查詢結(jié)果的基礎(chǔ)上進行部分匯聚操作。在基于BORA樹的匯聚方案中，向父節(jié)點傳輸?shù)牟樵兘Y(jié)果是傳輸節(jié)點和其所有子樹的查詢結(jié)果的匯聚結(jié)果。查詢命令是通過遞歸式的從上至下的發(fā)布，而查詢結(jié)果是從下至上的匯聚。每個網(wǎng)格服務(wù)器按算法執(zhí)行BORA樹的構(gòu)造和數(shù)據(jù)的傳輸，直到給定查詢的處理完成。

對于類網(wǎng)格模式下對應(yīng)軌跡的某節(jié)點CKNN查詢的NodeTable，其每層NodeList的首尾兩節(jié)點與相鄰節(jié)點對應(yīng)的NodeList的尾首節(jié)點可能存在相同的對應(yīng)近鄰軌跡ID，對應(yīng)近鄰時間段相連的情況。這種情況下將對應(yīng)兩節(jié)點合并成一個節(jié)點，時間段屬性對應(yīng)拓展，這也是在匯聚操作中處理，以進一步減小數(shù)據(jù)傳輸量。

4實驗分析

文中就基于BORA匯聚的CKNN查詢進行了各項實驗評估其各項參數(shù)對性能的影響。對每一項K近鄰查詢結(jié)果，通過基于BORA方式和Na?ve方進行比較評估其性能。試驗中關(guān)于移動對象的歷史信息存儲在類似R-tree的數(shù)據(jù)結(jié)構(gòu)中，通過公開的程序庫Spatial Index Library實現(xiàn)具體功能。Spatial Index Library提供了空間數(shù)據(jù)索引的一個通用框架，定義了通用的接口，簡化了主存和存儲設(shè)備的管理，實現(xiàn)了R*-tree, MVR-tree以及TPR-tree等數(shù)據(jù)結(jié)構(gòu)。實驗是在Pentium Intel Core2 Duo 2.26 GHZ，3 GB內(nèi)存，Cygwin平臺下運行的，主要的實驗參數(shù)和內(nèi)容如下。

1)設(shè)定對象移動范圍為100×100 km的正方形區(qū)域，劃分為50×50的等距網(wǎng)格。

2)移動對象的軌跡是改進后的RWP(random way-point model)生成的模擬數(shù)據(jù)，使得各段采集數(shù)據(jù)的速度在設(shè)定范圍內(nèi)隨機變化?？偣采? 000條軌跡，軌跡的起始點和移動方向都是在移動范圍內(nèi)隨機生成，速度在15-120 km/h；路徑中任意一線段對應(yīng)的最大移動速度隨機設(shè)定為速度的70%-100%。每條軌跡已預(yù)先按照路徑存儲在通過的網(wǎng)格MOD中。軌跡的總長在15-120 km，軌跡包括的線段數(shù)目呈正態(tài)分布，1 km的長度通常包括4-8個線段。

3)就K近鄰查詢而言，隨機選擇查詢時間的起始和終止值，查詢時間的長度隨機不定。

4)通信方式是各個網(wǎng)格MOD節(jié)點向目的節(jié)點逐節(jié)傳送的，每個網(wǎng)格對應(yīng)的MOD服務(wù)器負責對應(yīng)區(qū)域內(nèi)的數(shù)據(jù)接收和傳輸，速率假設(shè)為128 kbit/s。

首先，實驗就軌跡數(shù)目在不同匯聚方式下，對各匯聚方式處理時間的影響進行評估。為了準確評估軌，實驗選擇了不同的軌跡數(shù)目，每個網(wǎng)格選擇了100到1 000條不等。而其他影響因素，都假設(shè)為一個固定值：如對象的移動速度都假設(shè)在80 km/h左右，并且對象運動軌跡段中心到匯聚中心的距離被設(shè)定為整個移動區(qū)域的對角線長度的60%。圖3顯示了不同軌跡數(shù)目對處理時間的影響?？梢钥闯?，基于BORA的方法比Na?ve的方法節(jié)省了更多的時間；而隨著軌跡數(shù)目的增加，節(jié)省時間的總量也在增加。分析其原因，是因為隨著軌跡數(shù)目的增加，所查詢軌跡的最近鄰結(jié)果包含更多記錄的可能性也隨之增加，因此各種匯聚方式都增加了所需要傳輸?shù)臄?shù)據(jù)。

圖3　軌跡數(shù)目對不同匯聚方式處理時間的影響Fig.3　Influence of trajectories number

接下來，就移動對象的速度對處理時間的影響進行評估。實驗中，軌跡的運行速度假設(shè)為15—120 km/h，在每個網(wǎng)格中的軌跡數(shù)目設(shè)定為800。圖4顯示了對象移動速度對處理時間的影響?？梢钥闯?，隨著對象移動速度的增加，處理時間近似線性增加。這也是因為隨著軌跡運動速度的增加，所查詢軌跡的最近鄰結(jié)果包含更多記錄的可能性也隨之增加，從而增加了總體的處理時間。

圖4　移動對象速度對處理時間的影響Fig.4　Influence of moving object velocity

關(guān)于K近鄰查詢中參數(shù)K對處理時間的影響由圖5可以看出，其中每個網(wǎng)格的軌跡數(shù)目設(shè)定為400。圖5中顯示了最近鄰，2-NN和4-NN查詢在對象不同移動速度下對處理時間的影響。結(jié)果表明，隨著參數(shù)K和移動速度的增加，所需傳輸?shù)臄?shù)據(jù)增加，使得各匯聚方式所需的處理時間增加。但不管何種情況下，基于BORA的匯聚方式總是優(yōu)于Na?ve方式。

圖5　近鄰參數(shù)K對處理時間的影響(軌跡數(shù)目400)Fig.5　Influence of K (400 trajectories)

最后，就匯聚距離對處理時間的影響進行分析。匯聚距離指的是軌跡段的中心與匯聚節(jié)點位置的距離。試驗中在給定匯聚節(jié)點的條件下，假設(shè)每個網(wǎng)格的軌跡數(shù)目為400條，對象移動速度為60 km/h。各個軌跡段中心到匯聚節(jié)點的距離根據(jù)與設(shè)定的移動范圍的對角長度的相對比例轉(zhuǎn)換為百分比，然后根據(jù)其對應(yīng)的百分比平均到10%到100%。實驗結(jié)果比較了Na?ve和BORA的匯聚方式，根據(jù)圖6可以看出，其處理時間上都基于匯聚距離的長度呈線性增加。

圖6　匯聚距離對處理時間的影響(軌跡數(shù)目400)Fig.6　Influence of aggregate distance (400 trajectories)

5結(jié)論

在過去的10年中，關(guān)于移動對象連續(xù)K近鄰查詢技術(shù)得到了廣泛關(guān)注。但在分布式的移動對象數(shù)據(jù)庫環(huán)境下，相關(guān)查詢的優(yōu)化、結(jié)果的匯聚問題還沒有得到解決。在實驗室設(shè)定的類網(wǎng)格覆蓋的分布式空間網(wǎng)絡(luò)環(huán)境下，每個網(wǎng)格由一個基站負責處理相關(guān)的通信問題，還配備服務(wù)器擁有移動對象數(shù)據(jù)庫，保存對應(yīng)網(wǎng)格區(qū)域內(nèi)的移動對象相關(guān)的軌跡信息，處理對應(yīng)的查詢操作；并通過與相鄰節(jié)點的鏈接，協(xié)同處理跨網(wǎng)格的相關(guān)查詢操作與結(jié)果匯聚。BORA匯聚基于Bresenham算法的思想，沿著查詢節(jié)點到匯聚節(jié)點的Bresenham路徑進行查詢結(jié)果的匯聚操作，在保留一定程度的并行能力和查詢結(jié)果的匯聚上實現(xiàn)了較好的平衡。

本文在前期工作的基礎(chǔ)上，在連續(xù)K近鄰查詢中，通過在軌跡數(shù)據(jù)結(jié)構(gòu)中增加更新標志位的方法，避免了在更新連續(xù)K近鄰查詢結(jié)果的操作中，頻繁重復(fù)檢查已確定節(jié)點的問題。將BORA算法應(yīng)用到各節(jié)點查詢結(jié)果的匯聚操作中，這比一般情形的匯聚方式更加優(yōu)越。通過實驗結(jié)果可以看出，隨著參數(shù)K、軌跡數(shù)目以及對象運動速度的增加，BORA算法節(jié)省了更多的處理時間，提高了系統(tǒng)處理效率。

參考文獻：

[1]陳瑛, 陳釗瀅, 葉小平. M-相點數(shù)據(jù)索引SPindex[J]. 計算機科學, 2015, 42(1): 206-209.

CHENG Ying, CHENG Zhaoying, YE Xiaoping. SPindex:Spatial Index Based on M-phase Points[J]. Computer Science, 2015, 42(1):206-209.

[2]金培權(quán), 汪娜, 張曉翔,等. 面向室內(nèi)空間的移動對象數(shù)據(jù)管理[J]. 計算機學報, 2015(9):1777-1795.

JIN Peiquan, WANG Na, ZHANG Xiaoxiang, et al. Moving Object Data Management for Indoor Spaces [J] . Chinese Journal of Computers, 2015(9):1777-1795.

[3]G¨UTING R H, SCHNEIDER M. Moving Objects Databases[M]. Burlington USA: Morgan Kaufmann, 2005.

[4]TRAJCEVSKI G, DING H, SCHEUERMANN P, et al. BORA: Routing and Aggregation for Distributed Processing of Spatio-Temporal Range Queries [C]//Proceedings of the 2007 International Conference on Mobile Data Management. [s.l.]:IEEE, 2007:36-43.

[5]MOKBEL M, XIONG X, AREF W. Sina: Scalable incremental processing of continuous queries in spatio-temporal databases [C]//In ACM SIGMOD Internation Conference on Management of Data. New York, NY, USA :ACM, 2004:623-634.

[6]XING X, MOKBEL M, AREF W, et al. Scalable spatio-temporal continuous query processing for location-aware services [C]//In International Conference on Scientific and Statistical Database Management (SSDBM).[s.l.]:IEEE, 2004:317-326.

[7]WOLFSON O,SISTLA A P,CHAMBERLAIN S,et al.Updating and querying databases that track mobile units[J].Distributed and Parallel Databases,1999,7(3):257-387.

[8]GEDIK B, LIU L. Mobieyes: Distributed processing of continuous queries on moving objects in a mobile system [C]//In International Conference on Extending the Database Technology (EDBT). Berlin Heidelberg: Springer, 2004:67-87.

[9]GEDIK B, LIU L. Mobieyes: A distributed location monitoring service using moving location queries [J]. IEEE Transactions on Mobile Computing, 2006,5(10):67-87.

[10] BOULIS A, GANERIWAL S, SRIVASTAVA M. Aggregation in sensor networks: Energy-accuracy trade offs

[J]. Ad Hoc Network, 2003s, 1 (2-3):317-331.

[11] YOUSSEF M, YOUNIS M, ARISHA K. A constrained shortest-path energy-aware routing algorithm for wireless sensor networks [C]//In IEEE-WCNC. [s.l.]:IEEE, 2002:794-799.

[12] ZADOROZHNY V, CHRYSANTHIS P. Network-aware wireless sensor data management [C]// In MDM. Japan: Conference Publication, 2006.

[13] LOWEKAMP B, BEGUELIN A. Eco: Efficient collective operations for communication in heterogeneous networks [C]∥In IPPS. Honolulu, HI:IEEE, 1996:399-405.

[14] FRENTZOS E,GRATSIAS K,PELEKIS N,et al.,Algorithms for nearest neighbor search on moving object trajectories[J].Geoinformatica,2007,11(2):159-193.

[15] GAO Y J, LI C, CHEN G C, et al. Efficient k-nearest-neighbor search algorithms for historical moving object trajectories [J]. Journal of Computer Science and Technology, 2007, 22( 2): 232-244.

[16] GAO Y J, LI C, CHEN G C, et al. Efficient algorithms for historical continuous k nn query processing over moving object trajectories [M].[s.l.]: Advances in Data and Web Management, 2007:188-199.

BORA optimized aggregation of CKNN query in distributed settings

YE Li

(Southwest China Institute of Electronic Technology, Chengdu 610036, P.R.China)

Abstract:In spatial and spatio-temporal databases and distributed settings of MOD(moving objects databases), the problem of lack of efficiency of continuousKnearest neighbor query about moving object trajectories, and that of query optimization and results aggregation were researched. TheKNearest Neighbor query efficiency is promoted by adding the update flag in trajectory data structure. And in assumed grid-like coverage of spatial universe of discourse, the aggregation problem of continuousKnearest neighbor is resolved by revised BORA (Bresenham-based overlay for routing and aggregation) algorithm. The influence of different parameters, such asK, number of trajectories, moving velocity and aggregation method were demonstrated in experiments. It can be seen that the increase of different parameter prolongs the processing time, but the BORA based aggregation saved more processing time and improved the efficiency of system.

Keywords：moving objects database; continuousKnearest neighbor query; query aggregation; BORA algorithm

DOI：10.3979/j.issn.1673-825X.2016.03.026

收稿日期：2016-03-18

修訂日期：2016-05-05通訊作者：葉李forefell@sohu.com

基金項目：國家自然科學基金項目(61379159)；重慶市科委自然科學基金項目(cstc2014jcyjA1350)

Foundation Items：The National Natural Science Foundation of China(61379159)；The Natural Science Foundation Project of CQ CSTC (cstc2014jcyjA1350)

中圖分類號：TP3

文獻標志碼：A

文章編號：1673-825X(2016)03-0435-08

作者簡介：

葉李(1977-)，男，四川達州人，工程師，博士，主要研究方向為偵察對抗總體設(shè)計。E-mail:forefell@sohu.com。

(編輯：魏琴芳)