馬永強(qiáng)，陳曉萌，于自強(qiáng)*

（1.自然資源部城市國土資源監(jiān)測與仿真重點(diǎn)實驗室，廣東 深圳 518034；2.煙臺大學(xué) 計算機(jī)與控制工程學(xué)院，山東 煙臺 264005）

0 引言

移動對象查詢問題近年來被廣泛研究［1］。本文研究的移動對象連續(xù)范圍查詢是指給定一個移動對象集合O、一個查詢點(diǎn)qi及其查詢范圍sqi，查詢范圍內(nèi)的移動對象，并隨著移動對象和查詢點(diǎn)的不斷移動，對qi的查詢結(jié)果進(jìn)行連續(xù)更新。大規(guī)模移動對象的連續(xù)范圍查詢是許多基于位置服務(wù)的核心問題。例如，打車軟件為查找附近的出租車，此時用戶和出租車可以分別被視為查詢點(diǎn)和移動對象?，F(xiàn)實中，打車軟件通常需要為移動的用戶持續(xù)更新周圍的出租車，其本質(zhì)是以用戶為查詢點(diǎn)的移動對象連續(xù)范圍查詢。

近年來，盡管移動對象范圍查詢已經(jīng)被大量研究，但仍存在以下問題亟待解決。

在索引結(jié)構(gòu)方面，已有工作通常設(shè)計基于R-tree 索引結(jié)構(gòu)或網(wǎng)格索引結(jié)構(gòu)的移動對象范圍查詢算法。R-tree 索引［2-3］結(jié)構(gòu)雖然能夠有效支持移動對象范圍查詢，但是由于樹型結(jié)構(gòu)整體性較強(qiáng)，且維護(hù)代價較高，難以直接部署到服務(wù)器集群的分布式計算環(huán)境中。網(wǎng)格索引結(jié)構(gòu)［4-8］雖然易于部署到基于服務(wù)器集群的分布式計算環(huán)境中，但是面對范圍查詢時，剪枝能力有待加強(qiáng)，主要體現(xiàn)在處理與范圍查詢部分重疊的單元格時，仍然需要對該單元格內(nèi)所有移動對象進(jìn)行判斷以確定它們是否被查詢范圍覆蓋。當(dāng)并發(fā)查詢數(shù)量大、單元格內(nèi)移動對象較多時，處理大量類似單元格將消耗大量的計算資源。例如，圖1（a），查詢qi的查詢范圍與8 個單元格部分相交，此時就需要對8 個單元格內(nèi)所有移動對象進(jìn)行遍歷，查詢效率有待提高。

在計算模式方面，已有絕大多數(shù)范圍查詢相關(guān)工作［9-12］都是針對單個計算節(jié)點(diǎn)設(shè)計的集中式查詢算法，然而，現(xiàn)實中基于位置服務(wù)通常需要在短時間內(nèi)處理大量并發(fā)的移動對象范圍查詢。此時，集中式查詢算法受限于單個計算節(jié)點(diǎn)的計算資源，難以高效處理大規(guī)模并發(fā)的移動對象范圍查詢，而本文設(shè)計基于服務(wù)器集群的分布式查詢算法（Distributed Search Algorithm，DSA）是解決這一問題的有效方案。

針對上述問題，本文研究分布式環(huán)境下移動對象范圍查詢算法。目前，已有相關(guān)工作對分布式環(huán)境下的移動對象范圍問題進(jìn)行研究［13-15］，這些工作是將移動對象看作移動重點(diǎn)，通常是將每個移動對象看作一個移動計算終端，這些移動終端和數(shù)據(jù)中心構(gòu)成一個偏向邊緣計算的分布式計算環(huán)境，這與本文基于服務(wù)器集群的分布式計算環(huán)境截然不同。首先，這種偏向邊緣計算的分布式模式是將大量的計算分配到移動終端，移動終端與數(shù)據(jù)中心較大的通信代價是衡量系統(tǒng)性能的主要指標(biāo)；本文的分布式計算模式是將同一查詢的計算任務(wù)均衡地分配給多個服務(wù)器并行處理，服務(wù)器之間的通信代價較小，計算代價是主要考慮的性能因素。其次，偏向邊緣計算的分布式計算模式要求移動終端具有較強(qiáng)的計算算力，一定限度上限制了該算法在現(xiàn)實中一些低計算性能終端（如車載GPS）上的應(yīng)用；本文的分布式計算模式僅要求移動對象能夠發(fā)送當(dāng)前位置即可，絕大多數(shù)移動對象均具備這一功能。

針對上述問題，本文首先提出一種由網(wǎng)格索引和動態(tài)四叉樹索引構(gòu)成的移動對象分布式動態(tài)索引（Distributed Dynamic Index，DDI）結(jié)構(gòu)。該索引結(jié)構(gòu)首先將整個查詢區(qū)域劃分為n×n個大小相等的單元格，每個單元格記錄它所包含的移動對象；每個單元格相互獨(dú)立，可以部署到多個不同物理計算節(jié)點(diǎn)上。為增強(qiáng)網(wǎng)格索引的剪枝能力，當(dāng)一個單元格內(nèi)的移動對象數(shù)量超過閾值α，則為該單元格構(gòu)建一棵動態(tài)四叉樹。動態(tài)四叉樹的構(gòu)建原則是將整個單元格看作根節(jié)點(diǎn)，當(dāng)一個節(jié)點(diǎn)內(nèi)的移動對象數(shù)量大于α?xí)r，則為該節(jié)點(diǎn)增加4 個孩子節(jié)點(diǎn)，單元格內(nèi)的移動對象保存在四叉樹的葉子節(jié)點(diǎn)中；若具有同一父節(jié)點(diǎn)的4 個葉子節(jié)點(diǎn)的移動對象數(shù)量之和小于α，則刪除該4 個葉子節(jié)點(diǎn)，其父節(jié)點(diǎn)變?yōu)楹⒆庸?jié)點(diǎn)。隨著移動對象的位置變化，每個單元格的四叉樹深度動態(tài)調(diào)整，從而獲得合適的索引粒度。本文提出的DDI 結(jié)構(gòu)能夠有效增強(qiáng)針對范圍查詢的剪枝效力。圖1（b）中，查詢qi的查詢范圍覆蓋單元格c7，可直接將c7內(nèi)所有移動對象作為qi的部分查詢結(jié)果；對于查詢qi所涉及的其他單元格（除c7以外），則遍歷每個單元格對應(yīng)的四叉樹索引結(jié)構(gòu)。此時，查找這些單元格中被查詢qi覆蓋的移動對象時，不必再遍歷這些單元格中所有移動對象，而是對每個單元格對應(yīng)四叉樹中不同層級的節(jié)點(diǎn)進(jìn)行搜索，即可快速得到被查詢范圍覆蓋的移動對象，顯著提高查詢效率。

圖1 DDI結(jié)構(gòu)Fig.1 DDI structure

由于DDI 結(jié)構(gòu)中各個單元格之間相互獨(dú)立，因此整個索引結(jié)構(gòu)易于部署到采用Master-Worker 架構(gòu)的分布式計算環(huán)境中?；贒DI 結(jié)構(gòu)，本文進(jìn)一步提出了一種針對范圍查詢的分布式查詢算法（DSA）。該算法將每個范圍查詢分解為多個單元格上的子查詢，這些子查詢可以由多個計算節(jié)點(diǎn)并行計算，從而提高查詢效率。對范圍查詢進(jìn)行連續(xù)搜索時，DSA 盡可能利用該查詢上一時刻已有結(jié)果增量計算當(dāng)前時刻最新結(jié)果。此外，每個計算節(jié)點(diǎn)采取一種共享計算機(jī)制，對其處理的涉及相同查詢區(qū)域的多個并發(fā)范圍查詢共享計算結(jié)果，進(jìn)一步降低計算代價。

本文的主要工作如下：

1）提出一種基于網(wǎng)格索引和彈性四叉樹的移動對象分布式動態(tài)索引結(jié)構(gòu)DDI，它易于部署到分布式計算環(huán)境下，并且能夠根據(jù)移動對象的分布密度動態(tài)調(diào)整每個單元格的索引粒度，具有更強(qiáng)的剪枝能力。

2）提出一種面向大規(guī)模移動對象并發(fā)范圍查詢的分布式搜索算法DSA，并設(shè)計了面向連續(xù)范圍查詢的增量搜索和共享計算策略，該算法具有良好的可擴(kuò)展性。

3）將所提算法部署到流數(shù)據(jù)分布式計算平臺Storm 上，并在實驗中與NS（Naive Search）、GI（Grid Index）和分布式混合索引（DHI）進(jìn)行對比，評估本文所提出方法的性能。

1 相關(guān)工作

移動對象的范圍查詢作為基于位置服務(wù)領(lǐng)域的基本問題被廣泛研究，本文根據(jù)已有工作所采用的移動對象索引結(jié)構(gòu)、查詢場景和計算模式對其進(jìn)行梳理和介紹如下。

移動對象網(wǎng)格索引被廣泛應(yīng)用于移動對象查詢［4-9］。Kalashnikov 等［4］指出基于網(wǎng)格索引的查詢性能相較于其他索引結(jié)構(gòu)更加優(yōu)越，并提出一種基于排序的優(yōu)化方法以提高緩存命中率；Dong 等［5］和董天陽等［6］建立移動對象網(wǎng)格索引，可根據(jù)方向感知道路網(wǎng)絡(luò)以確定向查詢點(diǎn)移動的移動對象；薛忠斌等［7］提出一種基于內(nèi)存的高吞吐量移動對象范圍查詢算法，可一次執(zhí)行多個查詢，實現(xiàn)了查詢間的并行；Yu等［8］提出了一種基于網(wǎng)格對移動對象高效索引的可伸縮算法，可以提高查詢性能和對移動對象密集分布的魯棒性。

此外，文獻(xiàn)［10-12］中引入了“安全區(qū)”的概念來解決移動對象查詢問題?！鞍踩珔^(qū)”是根據(jù)查詢范圍邊界內(nèi)部/外部的最近移動對象到查詢邊界的距離計算的查詢移動區(qū)域，在該區(qū)域中，查詢點(diǎn)的移動不會導(dǎo)致查詢結(jié)果發(fā)生變化。Al-Khalidi等［11-12］研究了一種靜態(tài)近似距離搜索算法，該算法可以快速確定“安全區(qū)”上/下界限近似范圍，使指定安全區(qū)內(nèi)的查詢避免重復(fù)計算。

隨著室內(nèi)位置服務(wù)的日益普及，室內(nèi)移動對象的距離感知查詢研究在過去的幾年里受到了一些學(xué)者［16-18］的重視。Wang 等［17］根據(jù)不同距離的邊界擁有不同查詢評估，對不確定室內(nèi)距離的移動對象關(guān)系進(jìn)行了定義和分類。Shao 等［18］指出，室內(nèi)空間的特性未被現(xiàn)有的索引和查詢技術(shù)充分利用，因此，他們在充分考慮室內(nèi)場地特性的基礎(chǔ)上提出了室內(nèi)分區(qū)樹（Indoor Partitioning Tree，IP-Tree）和生動的室內(nèi)分區(qū)樹（Vivid IP-Tree，VIP-Tree）兩種新的索引結(jié)構(gòu)。

上述大多數(shù)算法是集中式算法，受限于單個節(jié)點(diǎn)的計算能力，難以應(yīng)對大規(guī)模的并發(fā)查詢。為此，Silvestri 等［19］采用一種基于CPU 和GPU 混合使用的并行算法處理大規(guī)模移動對象范圍查詢。此外，一些工作研究了面向移動對象范圍查詢的分布式搜索算法。其中文獻(xiàn)［13-15］采用邊緣計算的思想進(jìn)行范圍查詢，這類算法通常要求移動終端具有較強(qiáng)的計算能力，使得該類方法的適用性受限；與之不同的是，文獻(xiàn)［3，20-21］中采用基于服務(wù)器集群的分布式計算思想。其中：馮鈞等［20］提出一種靜態(tài)范圍查詢算法，對查詢點(diǎn)相鄰的路段進(jìn)行遞歸，以更新查詢范圍內(nèi)路段上的移動對象；但在處理大規(guī)模并發(fā)查詢時，創(chuàng)建多個索引表會給系統(tǒng)帶來巨大的額外負(fù)載。針對上述問題，徐江峰等［21］則提出了一個多維索引框架New-grid，該框架采用基于Hilbert 曲線的線性化技術(shù)解決此問題，同時指出網(wǎng)格索引在分布式環(huán)境下具有良好的可擴(kuò)展性；但在處理與范圍查詢有交集的候選單元格時，這些算法仍需遍歷候選單元格內(nèi)所有移動對象。Yu等［3］提出了基于網(wǎng)格索引和R-tree 的混合分布式索引結(jié)構(gòu)用于解決該問題。但當(dāng)移動對象位置發(fā)生變化時，該索引結(jié)構(gòu)的每個單元格對應(yīng)的R-tree 自底向上不斷更新，需要進(jìn)行頻繁維護(hù)，導(dǎo)致整個索引的維護(hù)代價較大；此外，該算法未考慮多個并發(fā)范圍查詢之間的共享計算問題，本文認(rèn)為對涉及相同區(qū)域的多個并發(fā)范圍查詢，共享計算能夠有效提高查詢效率。

2 相關(guān)定義

表1 是本文擬采用的符號與含義說明。

表1 符號及其含義Tab.1 Symbols and their meanings

定義1移動對象。移動對象被表示為一個三元組oi={IDi，tc，(xi，yi)}，即oi的唯一標(biāo)識IDi在tc時刻的位置為(xi，yi)。

定義2連續(xù)范圍查詢。連續(xù)范圍查詢是指給定查詢點(diǎn)qi及查詢范圍sqi，從查詢qi初始時刻計算位于sqi范圍內(nèi)的移動對象集合然后隨著查詢點(diǎn)和移動對象位置的變化，不斷地更新移動對象集合Oquery，直到查詢終止時間。

本文中，查詢qi的查詢范圍sqi可以是任意多項式表示的形狀。為便于表述，本文假設(shè)sqi為圓形。

定義3單元格。本文將整個搜索區(qū)域劃分為若干相同大小的單元格。每個單元格ci采用OLi、FLi和PLi這3 個列表分別記錄它所包含的移動對象、查詢范圍完全覆蓋ci的查詢點(diǎn)以及查詢范圍部分覆蓋ci的查詢點(diǎn)。

定義4候選單元格。對于范圍查詢qi，如果單元格ck完全或部分被sqi覆蓋，那么ck是查詢qi的候選單元格。ck?sqi表 示ck被sqi完全覆 蓋，ck?sqi表 示ck被sqi部 分覆蓋。

3 移動對象分布式索引結(jié)構(gòu)

3.1 分布式索引結(jié)構(gòu)模型

本文提出的移動對象分布式動態(tài)索引（DDI）結(jié)構(gòu)由網(wǎng)格索引以及動態(tài)四叉樹兩部分構(gòu)成。

3.1.1 網(wǎng)格索引結(jié)構(gòu)

網(wǎng)格索引將整個查詢區(qū)域劃分為大小相同的單元格。每個單元格ci維護(hù)OLi、FLi和PLi這3個列表，分別記錄它所包含的移動對象、查詢范圍完全覆蓋ci的查詢點(diǎn)以及查詢范圍部分覆蓋ci的查詢點(diǎn)。當(dāng)單元格ci記錄的移動對象數(shù)量達(dá)到閾值α?xí)r，單元格ci則會構(gòu)建一棵動態(tài)四叉樹Ti作進(jìn)一步索引。

3.1.2 動態(tài)四叉樹索引結(jié)構(gòu)

首先，四叉樹的每個葉子節(jié)點(diǎn)nf維護(hù)一個移動對象列表NLf，記錄被該葉子節(jié)點(diǎn)覆蓋移動對象的唯一標(biāo)識（ID）。四叉樹的每個非葉子節(jié)點(diǎn)ni維護(hù)一個查詢列表QLi，記錄查詢范圍sqi能夠完全覆蓋該節(jié)點(diǎn)的查詢ID。每個葉子節(jié)點(diǎn)nf也維護(hù)一個查詢列表QLi，記錄查詢范圍完全覆蓋該葉子節(jié)點(diǎn)或者與該葉子節(jié)點(diǎn)部分相交的查詢ID。隨著移動對象的變化，Ti可根據(jù)移動對象的分布密度動態(tài)調(diào)整樹的深度。具體而言，如果Ti中某個葉子節(jié)點(diǎn)中移動對象數(shù)量大于等于指定的移動對象數(shù)量閾值α，則該葉子節(jié)點(diǎn)進(jìn)行遞歸分裂，直至每個葉子節(jié)點(diǎn)內(nèi)移動對象數(shù)量小于閾值α；如果Ti中具有同一父節(jié)點(diǎn)的一組葉子節(jié)點(diǎn)中移動對象數(shù)量之和小于閾值α，則該組葉子節(jié)點(diǎn)將被刪除，所包含的移動對象將由其父節(jié)點(diǎn)保存。

圖2 給出了單元格ci對應(yīng)的四叉樹索引結(jié)構(gòu)。圖2（a）給出單元格ci對應(yīng)四叉樹的構(gòu)建過程。其中，設(shè)定α=4，由于單元格ci中移動對象數(shù)量多于α，則將單格ci看作根節(jié)點(diǎn)，為其添加4 個孩子節(jié)點(diǎn)（n1、n2、n3、n4）。由于n1、n2中的移動對象數(shù)量大于α，則進(jìn)一步為其分別增加孩子節(jié)點(diǎn)，直至所有葉子節(jié)點(diǎn)的移動對象數(shù)量小于α，對應(yīng)的四叉樹索引結(jié)構(gòu)如圖2（b）所示。對于查詢q1，其查詢范圍sq1完全覆蓋n1、n11，故將q1插入到n1、n11的查詢列表；由于sq1與葉子節(jié)點(diǎn)n3、n4、n9、n10、n12部分相交，故將其插入到n3、n4、n9、n10、n12的查詢列表。

圖2 動態(tài)四叉樹索引Fig.2 Dynamic quadtree index

網(wǎng)格索引中引入動態(tài)四叉樹索引結(jié)構(gòu)的目的是處理與某單元格部分相交的范圍查詢時，避免對該單元格中所有移動對象進(jìn)行遍歷。具體而言，如果單元格ci包含大規(guī)模移動對象且與查詢范圍sqi部分相交，那么查找屬于ci且被sqi覆蓋的移動對象需要遍歷ci中所有移動對象，耗時較大。每個單元格中引入動態(tài)四叉樹后，可以對該單元格內(nèi)的移動對象進(jìn)行不同粒度索引，查詢算法只需遍歷四叉樹的部分節(jié)點(diǎn)就能得到準(zhǔn)確查詢結(jié)果，有效降低計算代價。

由于DDI 結(jié)構(gòu)每個單元格作為一個獨(dú)立的索引單元，可以部署到分布式集群的任意物理計算節(jié)點(diǎn)。每個計算節(jié)點(diǎn)可以根據(jù)自身負(fù)載維護(hù)任意數(shù)量的網(wǎng)格索引，從而使得DDI結(jié)構(gòu)具有良好的可擴(kuò)展性。

3.2 DDI結(jié)構(gòu)的構(gòu)建

構(gòu)建DDI 結(jié)構(gòu)是指將移動對象和連續(xù)范圍查詢插入到不同的單元格及其對應(yīng)的四叉樹中。

3.2.1 移動對象的插入

算法1 給出將移動對象oi插入算法的偽代碼。首先識別當(dāng)前oi所在的單元格cj，隨后將oi添加到單元格cj的移動對象列表OLj，最后將且oi插入到cj對應(yīng)的四叉樹Ti中。在插入四叉樹過程中，先從Ti的根節(jié)點(diǎn)逐層向下掃描，確定覆蓋oi(xi，yi)的葉子節(jié)點(diǎn)nf，再將oi添加至nf的移動對象列表NLf（4）～8）行）。如果該葉子節(jié)點(diǎn)nf中移動對象數(shù)量達(dá)到閾值α，則進(jìn)行分裂行成新的葉子節(jié)點(diǎn)，其中所有移動對象分別插入到對應(yīng)的新葉子節(jié)點(diǎn)中（9）～10）行）。

算法1 中，給定移動對象oi(xi，yi)，分別根據(jù)橫坐標(biāo)xi和縱坐標(biāo)yi確定oi所在單元格所需時間為T(2n)。設(shè)所插入單元格對應(yīng)四叉樹的節(jié)點(diǎn)數(shù)量為m，確定oi所在四叉樹葉子節(jié)點(diǎn)所需時間為T(log4m)，因此，算法1 的時間復(fù)雜度為O(n+log4m)。

算法1 添加移動對象至四叉樹。

3.2.2 插入連續(xù)范圍查詢

算法2 給出將連續(xù)范圍查詢qi插入到DDI 的偽代碼。首先確定與范圍查詢qi相關(guān)的單元格：對于被查詢范圍sqi完全覆蓋的單元格cj，qi被直接添加到單元格cj中的查詢列表FLj；對于被查詢范圍sqi部分覆蓋的單元格cl，對該單元格中四叉樹Tl從上至下進(jìn)行層次遍歷，查找被sqi完全覆蓋的四叉樹節(jié)點(diǎn)ni，在節(jié)點(diǎn)ni中記錄qi，并停止對ni孩子節(jié)點(diǎn)的處理（4）～9）行）。如果四叉樹Tl中某節(jié)點(diǎn)nj與查詢范圍sqi部分相交，則進(jìn)一步遍歷nj的孩子節(jié)點(diǎn)，直至葉子節(jié)點(diǎn)（11）～14）行）。根據(jù)qi的插入原則，在四叉樹Tl中記錄qi的所有節(jié)點(diǎn)中，只有葉子節(jié)點(diǎn)可能與sqi部分相交。因此，如果Tl的某個非葉子節(jié)點(diǎn)記錄qi，則該節(jié)點(diǎn)區(qū)域內(nèi)所有移動對象均被sqi覆蓋。

算法2 中，確定與查詢qi相交的r個單元格所需時間為T(2n)。假設(shè)r個單元格分布在不同的物理計算節(jié)點(diǎn)，那么查詢qi插入到每個單元格對應(yīng)的四叉樹則可以并行執(zhí)行，此時，查詢qi插入DDI 結(jié)構(gòu)的時間等于單個單元格的最大插入時間。因此，算法2 的時間復(fù)雜度可以表示為O(n+(i∈[1，r])。其中，log4mi表示將查詢qi插入單元格ci對應(yīng)四叉樹的時間復(fù)雜度，四叉樹的節(jié)點(diǎn)數(shù)量為mi。

算法2 添加范圍查詢至四叉樹。

3.3 DDI結(jié)構(gòu)的維護(hù)

隨著移動對象和范圍查詢點(diǎn)的位置變化，需要對DDI 進(jìn)行實時維護(hù)，下面本文分別從移動對象的維護(hù)和范圍查詢的維護(hù)這兩種角度進(jìn)行討論。

3.3.1 移動對象的維護(hù)

需要注意的是，上述過程中在更新單元格ci對應(yīng)的四叉樹Ti時，需要根據(jù)以下情況進(jìn)行處理：

1）若因oj的移動導(dǎo)致包含(xj，yj)的葉子節(jié)點(diǎn)與其兄弟節(jié)點(diǎn)的移動對象數(shù)量之和小于閾值α?xí)r，則該組葉子節(jié)點(diǎn)的所有移動對象由其父節(jié)點(diǎn)保存，隨后刪除該組葉子節(jié)點(diǎn)，其父節(jié)點(diǎn)變?yōu)樾碌娜~子節(jié)點(diǎn)。

2）若因oj的移動導(dǎo)致包含的葉子節(jié)點(diǎn)中移動對象數(shù)量達(dá)到指定的閾值α，則該葉子節(jié)點(diǎn)進(jìn)行遞歸分裂，直至每個葉子節(jié)點(diǎn)內(nèi)移動對象數(shù)量小于閾值α。

3.3.2 范圍查詢的維護(hù)

假設(shè)查詢點(diǎn)qi經(jīng)過移動后，范圍查詢區(qū)域sqi變?yōu)?。此時，需要對sqi和相關(guān)的單元格內(nèi)的查詢列表根據(jù)以下情況進(jìn)行處理：

1）如果sqi覆蓋ci且與ci不相交，則將qi從ci的列表FLi刪除。

2）如果sqi覆蓋ci且與ci相交，則將qi從FLi刪除，并插入單元格ci的列表PLi。

3）如果sqi與ci相交且與ci不相交，則將qi從PLi刪除。

4）如果sqi與ci不相交且sq′i覆蓋ci，則將qi插入FLi。

5）如果sqi與ci相交且覆蓋ci，則將qi從PLi刪除，并插入FLi。

6）如果sqi與ci不相交且與ci相交，則將qi插入PLi。

上述單元格ci的維護(hù)過程相較于單元格ci相應(yīng)的四叉樹Ti的維護(hù)而言，僅維護(hù)了Ti的根節(jié)點(diǎn)。而四叉樹Ti的維護(hù)需要自上而下判斷查詢范圍能否覆蓋每個節(jié)點(diǎn)，并重新插入范圍查詢，以維護(hù)查詢列表QLi。

3.4 DDI結(jié)構(gòu)的分布式部署

DDI 結(jié)構(gòu)部署于Master-Worker 范式的分布式計算環(huán)境下，該分布式集群由一個EntranceWorker 計算節(jié)點(diǎn)、多個IndexWorker 計算節(jié)點(diǎn)和多個QueryWorker 計算節(jié)點(diǎn)組成。DDI 結(jié)構(gòu)的分布式部署框架如圖3 所示。首先，在EntranceWorker 計算節(jié)點(diǎn)部署一個全局網(wǎng)格索引（Global Grid Index，GGI）。GGI記錄每個單元格的邊界以及所有單元格與IndexWorker 的對應(yīng)關(guān)系。一旦移動對象或者范圍查詢到達(dá)EntranceWorker節(jié)點(diǎn)，該節(jié)點(diǎn)將根據(jù)GGI確定移動對象和范圍查詢相關(guān)的單元格，并將其分發(fā)至對應(yīng)的IndexWorker。相對于GGI，IndexWorker 計算節(jié)點(diǎn)部署一個局部網(wǎng)格索引，對負(fù)責(zé)區(qū)域的單元格、四叉樹及其中移動對象索引。每個IndexWorker 根據(jù)移動對象和范圍查詢的插入算法將其插入對應(yīng)的單元格及其四叉樹索引中，并將計算結(jié)果發(fā)送至QueryWorker，由QueryWorker返回最終結(jié)果。

4 面向移動對象范圍查詢的分布式查詢算法

本章首先描述面向移動對象范圍查詢的DSA，然后介紹面向并發(fā)查詢的共享計算優(yōu)化策略，最后闡述移動對象和范圍查詢位置在連續(xù)變化情況下的分布式增量查詢算法。

4.1 面向范圍查詢的分布式查詢算法流程

面向移動對象范圍查詢的DSA是基于DDI結(jié)構(gòu)提出的，算法流程如圖3 所示。對于查詢qi，EntranceWorker 節(jié)點(diǎn)首先根據(jù)GGI結(jié)構(gòu)確定查詢qi的候選單元格集合Gi，并將查詢qi和集合Gi發(fā)送至QueryWorker，其中查詢qi被插入有效查詢列表。此后，由該QueryWorker維護(hù)查詢qi。然后，EntranceWorker 節(jié)點(diǎn)通知維護(hù)候選單元格的多個IndexWorker并行查找各自負(fù)責(zé)單元格中被qi的查詢范圍sqi所覆蓋的移動對象。在該查找過程中，如果某個候選單元格被sqi覆蓋，則該單元格內(nèi)所有移動對象均屬于qi的查詢結(jié)果；否則，自上而下遍歷候選單元格所對應(yīng)的四叉樹，可快速找到與sqi相交的區(qū)域，并計算得到該單元格內(nèi)屬于qi的移動對象。每個IndexWorker計算得到自身負(fù)責(zé)的候選單元格中屬于qi的移動對象后，將查詢結(jié)果發(fā)送至QueryWorker，QueryWorker只接收有效查詢列表維護(hù)查詢的部分查詢結(jié)果。QueryWorker每收到一個計算節(jié)點(diǎn)發(fā)送的部分查詢結(jié)果，就根據(jù)集合Gi判斷是否所有候選單元格的結(jié)果均已收到。如果均已收到，則返回qi的最終查詢結(jié)果。

圖3 DDI結(jié)構(gòu)的分布式部署框架Fig.3 Framework of distributed deployment of DDI structure

4.2 并發(fā)查詢共享計算優(yōu)化計算策略

1）傳輸代價優(yōu)化。眾所周知，分布式環(huán)境下相同規(guī)模數(shù)據(jù)的網(wǎng)絡(luò)傳輸開銷遠(yuǎn)遠(yuǎn)大于CPU 計算代價。當(dāng)IndexWorker獲得不同查詢的查詢結(jié)果后，需要將查詢結(jié)果發(fā)送到維護(hù)這些查詢的QueryWorker。此時，QueryWorker 數(shù)量越多，網(wǎng)絡(luò)傳輸代價越大。為解決這個問題，本文采取的策略是將查詢范圍重疊較多的多個范圍查詢路由至同一個QueryWorker 進(jìn)行處理，即負(fù)責(zé)處理這些范圍查詢的IndexWorker 需要將查詢結(jié)果發(fā)送至同一個QueryWorker。具體而言，對于兩個范圍查詢qi和qj，EntranceWorker 計算節(jié)點(diǎn)根據(jù)GGI 計算qi和qj的候選單元格集合分別為Gi和Gj，然后計算集合Gi和Gj的Jaccard 相似度如果δ大于等于指定的閾值，則將qi和qj發(fā)送至同一個QueryWorker 處理，否則將qi和qj發(fā)送至不同的QueryWorker 處理。

2）查詢代價優(yōu)化。對于與單元格cj部分相交的范圍查詢qi，在遍歷單元格cj對應(yīng)的四叉樹Tj計算qi的查詢結(jié)果時，一旦發(fā)現(xiàn)四叉樹Tj的某個非葉子節(jié)點(diǎn)被qi對應(yīng)的查詢范圍sqi完全覆蓋，為得到屬于該節(jié)點(diǎn)的移動對象，仍需繼續(xù)向下遍歷，直至葉子節(jié)點(diǎn)。由于同一單元格很可能與多個范圍查詢部分相交，范圍查詢需要對同一四叉樹進(jìn)行多次遍歷。這不僅需要做大量重復(fù)計算而且耗時較大。為解決這一問題，本文在每個單元格中引入一個基于“二分圖”的查詢結(jié)果索引（Bipartite Graph Index，BGI）結(jié)構(gòu)。

如圖4（a）所示，BGI 的結(jié)構(gòu)包含查詢集合Qs、四叉樹節(jié)點(diǎn)集合Ns以及每個四叉樹節(jié)點(diǎn)對應(yīng)的移動對象集合Os。對于新到達(dá)的查詢qi，從單元格cj對應(yīng)四叉樹Tj的根節(jié)點(diǎn)開始遍歷，假定Tj的某個節(jié)點(diǎn)ni被sqi完全覆蓋，如果該節(jié)點(diǎn)查詢列表QLf已有查詢qj，則在BGI 的Qs集合中查找qj，然后根據(jù)qj在Ns集合中所對應(yīng)的節(jié)點(diǎn)中尋找ni。此時，ni的移動對象集合Os已確定，無需遍歷ni的孩子節(jié)點(diǎn)；否則，繼續(xù)遍歷ni的孩子節(jié)點(diǎn)，獲得ni的移動對象集合Os。然后，將qi添加至Qs集合，ni添加至Ns集合。此后，若某個查詢的查詢范圍覆蓋節(jié)點(diǎn)ni，則可直接從BGI 的Ns集合中獲取ni的移動對象。

具體而言，如圖4（b）所示，假定已有范圍查詢sq1覆蓋節(jié)點(diǎn)n1，n8，且查詢點(diǎn)q1、所覆蓋四叉樹節(jié)點(diǎn)以及其中移動對象集合已插入BGI。此時，新的范圍查詢sq2與sq1覆蓋同一節(jié)點(diǎn)n8，則查詢q2關(guān)于n8的查詢結(jié)果可以從Ns集合中取得。而sq2覆蓋節(jié)點(diǎn)n2及其所對應(yīng)的移動對象集合在計算結(jié)果后存儲于BGI 中（如圖4（a）所示）。

圖4 BGI結(jié)構(gòu)Fig.4 BGI structure

4.3 分布式增量查詢算法

對于已經(jīng)計算得到初始結(jié)果的連續(xù)范圍查詢，本文需要根據(jù)移動對象和查詢點(diǎn)位置的變化，每隔Δt時間段，對其查詢結(jié)果進(jìn)行更新，直至查詢失效。為此，本文提出一種增量查詢策略，在充分利用已有結(jié)果的基礎(chǔ)上，對查詢結(jié)果進(jìn)行增量更新。下面分三種情況對增量查詢策略進(jìn)行討論。

1）移動對象位置變化而查詢點(diǎn)固定不變。經(jīng)過Δt時間，位置變化的若干移動對象會向EntranceWorker 節(jié)點(diǎn)報告移動前的位置和當(dāng)前最新位置，根據(jù)GGI，EntranceWorker 節(jié)點(diǎn)確定需要對其所屬移動對象進(jìn)行更新的單元格集合G，并通知對應(yīng)的IndexWorker。由IndexWorker 對單元格集合G中的移動對象進(jìn)行更新。如果一個移動對象是在同一單元格cm中發(fā)生位置變化，那么對FLm列表中的查詢并無影響，僅需要對PLm中的查詢進(jìn)行更新。在對PLm中的查詢進(jìn)行更新的過程中，可根據(jù)單元格cm中的BGI 索引結(jié)構(gòu)，對PLm中的多個查詢同時更新。也就是說，在移動對象位置變化而查詢點(diǎn)固定不變的情況下，若BGI 索引結(jié)構(gòu)中Ns集合中任意節(jié)點(diǎn)ni的移動對象集合發(fā)生變化，則根據(jù)ni的查詢列表QLi，對BGI 查詢集合Qs中查詢點(diǎn)的查詢結(jié)果進(jìn)行更新。

2）移動對象位置固定而查詢點(diǎn)位置變化。假設(shè)查詢qi經(jīng)過移動后，查詢范圍由sqi變 為。當(dāng)qi到 達(dá)EntranceWorker 節(jié)點(diǎn)后，EntranceWorker 節(jié)點(diǎn)分別根據(jù)sqi和計算qi上一時刻和當(dāng)前時刻的候選單元格集合Gl和Gc。如果單元格ck屬于Gl但不屬于Gc，則維護(hù)ck的IndexWorker（IWk）通知負(fù)責(zé)qi的QueryWorker（QWi）從qi上一時刻查詢結(jié)果中刪除屬于ck的移動對象；如果單元格ck不屬于Gl但屬于Gc，則IWk通知QWi將屬于ck的移動對象添加至qi上一時刻的查詢結(jié)果中；如果單元格ck既屬于Gl又屬于Gc，則根據(jù)以下規(guī)則對ck進(jìn)行處理。

如果(sqi?ck) &&(?ck)，qi查詢范圍一直覆蓋單元格ck，無需做任何更新。

如果(sqi?ck) &&(?ck)，將qi從PLk刪除并插入FLk。IWk根據(jù)四叉樹Tk計算(ck-(ck∩sqi))區(qū)域的移動對象，并將這些移動對象發(fā)送給QWi，QWi則將這些移動對象添加至qi的查詢結(jié)果。

如果(sqi?ck) &&(?ck)，將qi從FLk刪除并插入PLk。IWk基于四叉樹Tk計算(ck-(ck∩))區(qū)域的移動對象，并將這些移動對象發(fā)送給QWi，QWi則將這些移動對象從qi的查詢結(jié)果中刪除。

如果(sqi?ck) &&(?ck)，IWk則基于四叉樹Tk分別計算被區(qū)域(sqi-(sqi∩))和(-(sqi∩))分別覆蓋的移動對象集合Od和Oa，然后通知QWi從qi上一時刻的查詢結(jié)果中刪除集合Od中的移動對象，并添加集合Oa的移動對象。

4.4 移動對象和查詢點(diǎn)位置變化的增量查詢語義。

根據(jù)位置不斷變化的移動對象和查詢點(diǎn)，對查詢結(jié)果進(jìn)行增量更新時，EntranceWorker 創(chuàng)建兩個隊列分別緩存位置變化的移動對象和查詢點(diǎn)。當(dāng)移動對象和查詢點(diǎn)位置發(fā)生變化后，將被分別插入到移動對象緩存隊列和查詢點(diǎn)緩存隊列。如果查詢緩存隊列非空，則每隔Δt時間，處理該隊列中的查詢。在處理查詢時，基于當(dāng)前DDI 結(jié)構(gòu)中移動對象的快照增量更新查詢結(jié)果；在查詢處理過程中，暫停處理緩存隊列中位置變化的移動對象。待查詢處理完成后，再對緩存隊列中位置更新的移動對象進(jìn)行處理，更新DDI 結(jié)構(gòu)。在此過程中，如果有新的查詢或者位置變化的查詢到達(dá)，則被插入緩存隊列，待移動對象處理完成后，在下一個Δt時刻，對新到達(dá)的查詢進(jìn)行處理。根據(jù)該語義，當(dāng)移動對象和查詢點(diǎn)的位置同時發(fā)生變化時，本文將其看作兩個獨(dú)立的事件并在時間維度上將其序列化，兩個事件被序列化的先后順序并不會對查詢結(jié)果產(chǎn)生實質(zhì)性影響。然后，將位置變化的移動對象和查詢點(diǎn)分別插入兩個緩存隊列，便可根據(jù)上述給定的查詢語義進(jìn)行處理。

4.5 查詢算法時間復(fù)雜度

對于查詢范圍為sqi的查詢qi，其處理過程包含初始查詢和增量查詢兩個階段，現(xiàn)分別分析初始查詢的時間復(fù)雜度和增量查詢的時間復(fù)雜度。

在初始查詢階段，假設(shè)與sqi部分相交的候選單元格數(shù)量為r，且這些候選單元格分布在不同的物理計算節(jié)點(diǎn)。根據(jù)本文的分布式查詢思想，可以并行搜索每個候選單元格。此時，初始查詢時間等于單個單元格的最大搜索時間。為便于表述，假設(shè)候選單元格ci對應(yīng)四叉樹的節(jié)點(diǎn)數(shù)量為mi，確定被sqi完全覆蓋和與sqi部分相交的四叉樹節(jié)點(diǎn)的時間為T(log4mi)。進(jìn)一步假設(shè)被sqi完全覆蓋的四叉樹節(jié)點(diǎn)數(shù)量為，則與sqi部分相交的四叉樹節(jié)點(diǎn)數(shù)量為（），且均為葉子節(jié)點(diǎn)。對于每個被sqi完全覆蓋的四叉樹節(jié)點(diǎn)，它所包含的移動對象全部被sqi覆蓋，故處理該部分四叉樹節(jié)點(diǎn)的時間為T(m′i)；對于與sqi部分相交的每個四叉樹葉子節(jié)點(diǎn)，需要遍歷其包含的所有移動對象以判斷被sqi覆蓋的移動對象，故搜索該部分葉子節(jié)點(diǎn)的時間為T(*no)，no為每個葉子節(jié)點(diǎn)包含移動對象的平均數(shù)量。因此，一個單元格搜索時間為，而初始階段的時間復(fù)雜度為

增量查詢分為：

1）移動對象位置變化而查詢點(diǎn)位置固定。由于每個候選單元格中被sqi覆蓋的個四叉樹節(jié)點(diǎn)、與sqi相交的個四叉樹節(jié)點(diǎn)已確定，因此，只需要搜索與sqi相交的每個四叉樹節(jié)點(diǎn)中新增的移動對象被sqi覆蓋即可，所需時間為為新到達(dá)與sqi相交的每個四叉樹節(jié)點(diǎn)中移動對象的平均數(shù)量。因此，該情形下增量查詢的時間復(fù)雜度為

2）查詢點(diǎn)位置變化而移動對象位置固定。由于查詢點(diǎn)位置變化，需要重新確定候選單元格，時間為T(2n)。此時，假設(shè)與sqi部分相交的候選單元格數(shù)量仍為r，則該情形下的時間復(fù)雜度為雖然該情形下的時間復(fù)雜度與初始查詢的時間復(fù)雜度相同，但是此時m′i和m″i的值要明顯小于其在初始查詢時的值，故查詢效率仍有明顯提高。

5 實驗與結(jié)果分析

5.1 實驗配置

本文選擇移動對象不同分布的數(shù)據(jù)集進(jìn)行實驗來評估DDI結(jié)構(gòu)?；诘聡肪W(wǎng)模擬3個移動對象數(shù)據(jù)集：均勻分布（Uniform Distribution，UD）數(shù)據(jù)集、高斯分布（Gaussian Distribution，GD）數(shù)據(jù)集、齊普夫分布（Zipf）數(shù)據(jù)集。為了模擬這些數(shù)據(jù)集，首先將覆蓋每個路網(wǎng)的二維空間歸一化為一個1×1的正方形區(qū)域，并將其劃分成100×100個大小相同的單元格，然后根據(jù)每個單元格移動對象出現(xiàn)的概率密度分布函數(shù)計算每個單元格所分配的移動對象數(shù)量，最后令每個單元格內(nèi)的移動對象在對應(yīng)的局部路網(wǎng)上以速度vo移動。下面以GD為例闡述數(shù)據(jù)集的生成過程。由于GD 中的移動對象oi坐標(biāo)(xi，yi)在x維與y維都滿足高斯分布，因此，移動對象oi位于(xi，yi)的概率為即所有移動對象在整個查詢區(qū)域的概率密度分布函數(shù)，其中μ1、μ2、σ1、σ2、ρ分別設(shè)為0.5、0.5、0.2、0.2、0。此時，一個移動對象位于第i行、第j列單元格的概率為f(i，j)=0.08π exp[2(xi-0.2)2+2(yi-0.2)2]，其中i，j滿足0 ＜i≤100，0 ＜j≤100 且為正整數(shù)。假設(shè)移動對象總數(shù)為No，那么第i行、第j列單元格中的移動對象數(shù)量應(yīng)為f(i，j)*No。然后，在該單元格中產(chǎn)生對應(yīng)數(shù)量的移動對象，令其在該單元格覆蓋的局部路網(wǎng)上連續(xù)移動。

本文引入了3 種分布式算法作為基準(zhǔn)方法，以對比評價DSA 的性能。第1 個基準(zhǔn)算法NS（Naive Search）不使用任何索引，每個計算節(jié)點(diǎn)包含所有移動對象，每個查詢被隨機(jī)分配給所有計算節(jié)點(diǎn)；第2 個基準(zhǔn)算法GI（Grid Index）是構(gòu)建一個面向移動對象的分布式網(wǎng)格索引，基于分布式網(wǎng)格索引將給定的查詢分配到相應(yīng)的計算節(jié)點(diǎn)，進(jìn)而多個計算節(jié)點(diǎn)并行計算給定查詢的查詢結(jié)果；第3 個基準(zhǔn)算法分布式混合索引（Distributed Hybrid Index，DHI）是Yu 等［3］提出的一種全局網(wǎng)格和R-tree 結(jié)構(gòu)組成的混合索引，該算法在分布式網(wǎng)格索引的基礎(chǔ)上，以移動對象初始位置為葉子節(jié)點(diǎn)建立R-tree，并通過改變?nèi)~子節(jié)點(diǎn)大小調(diào)整索引粒度。

實驗的服務(wù)器集群是由阿里云租賃的20 個彈性云服務(wù)器（Elastic Cloud Server，ECS）計算節(jié)點(diǎn)構(gòu)成，每臺服務(wù)器為4核16 GB 內(nèi)存。實驗中，DDI 與DSA 所涉及的參數(shù)如表2所示。

表2 實驗中所涉及的參數(shù)以及含義Tab.2 Related parameters and their meanings in experiments

5.2 移動對象DDI的性能評估

5.2.1 移動對象數(shù)量對DDI構(gòu)建時間的影響

在該組實驗中，設(shè)置一個用以緩存待處理移動對象的隊列Qo，將移動對象一次性輸入其中，并統(tǒng)計為這些移動對象構(gòu)建DDI 結(jié)構(gòu)的時間，結(jié)果如圖5（a）所示?？梢钥闯?，DDI構(gòu)建時間與移動對象數(shù)量基本呈同比例增長。此外，處理GD 和Zipf 分布移動對象的時間略高，原因是當(dāng)移動對象分布密集時，集群中的某些服務(wù)器需要處理比其他服務(wù)器更多的移動對象，導(dǎo)致這些服務(wù)器的負(fù)載偏高，影響DDI 結(jié)構(gòu)的整體性能。

5.2.2 閾值α對DDI構(gòu)建時間的影響

閾值α對DDI 構(gòu)建時間的影響如圖5（b）所示?？梢钥闯?，無論移動對象符合哪種分布，隨著閾值α增加，索引DDI的構(gòu)建代價明顯減少。原因是閾值α與四叉樹的層數(shù)直接相關(guān)，隨著閾值α增大，四叉樹分裂子節(jié)點(diǎn)的可能性越低，進(jìn)而四叉樹層數(shù)減少，使得DDI 的構(gòu)建代價越少。

圖5 不同參數(shù)對DDI構(gòu)建時間的影響Fig.5 Influence of different parameters on DDI building time

5.2.3 移動對象的移動速率對DDI維護(hù)時間的影響

該組實驗首先為5×107個移動對象建立DDI 結(jié)構(gòu)，然后隨機(jī)選擇5×106個移動對象，令這些被選擇的移動對象以不同速率（vo）移動5 次，測試DDI 的平均維護(hù)時間，實驗結(jié)果如圖6 所示。可以看出，隨著移動對象速率的增加，維護(hù)成本明顯增加。這是因為當(dāng)移動速率較低時，移動對象的上一次位置和當(dāng)前位置有可能位于四叉樹的同一葉子節(jié)點(diǎn)中，此時不需要對四叉樹索引結(jié)構(gòu)進(jìn)行調(diào)整；但當(dāng)移動對象的移動速率較高時，四叉樹節(jié)點(diǎn)需頻繁調(diào)整移動對象數(shù)量，導(dǎo)致維護(hù)代價增大。

圖6 vo對DDI維護(hù)時間的影響Fig.6 Influence of vo on DDI maintenance time

5.2.4 DDI的吞吐量

對DDI 的吞吐量測試結(jié)果如圖7 所示。該組實驗中，設(shè)置一個隊列Qo緩存待處理的移動對象，其容量設(shè)置為5×104，令移動對象以不同的速率進(jìn)入隊列Qo，經(jīng)過一段時間后，檢測隊列Qo中的移動對象數(shù)量（No）。在速率小于4×106移動對象（Objects Per Second，OPS）時，隊列Qo內(nèi)移動對象數(shù)量保持平緩。在速率達(dá)到4×106OPS 時，隊列Qo內(nèi)移動對象數(shù)量迅速增加，即DDI 的吞吐量約為4×106OPS。這說明DDI 可以勝任大規(guī)模移動對象的范圍查詢工作。

圖7 DDI的吞吐量Fig.7 Throughput of DDI

5.3 DSA的性能評估

5.3.1 閾值α對DSA查詢時間的影響

本組實驗測試閾值α的同一組查詢的查詢時間，實驗結(jié)果如圖8（a）所示?？梢钥闯?，隨著閾值α的增加，搜索時間先減少后增長，閾值α為15 時效果最優(yōu)。當(dāng)閾值α過小時，四叉樹索引粒度普遍減小，遍歷時間開銷相對較大，導(dǎo)致整個查詢代價增大；反之，當(dāng)閾值α過大時，四叉樹的索引粒度普遍增大，剪枝效力下降，導(dǎo)致查詢時間增長。

5.3.2 搜索范圍對DSA查詢時間的影響

本組實驗首先建立100×100 的DDI（這里定義每個單元格的大小為0.01×0.01），隨后評估了DSA 的性能與查詢的搜索范圍之間的關(guān)系，結(jié)果如圖8（b）所示?？梢钥闯?，查詢范圍的大小對DSA 的性能有一定的影響。一個查詢點(diǎn)的查詢半徑（r）越大，所涉及的候選查詢單元格數(shù)量越多，即使DSA 能夠利用多個計算節(jié)點(diǎn)對候選單元格的移動對象進(jìn)行并行查詢，隨著候選單元格數(shù)量的增大，系統(tǒng)需要處理的計算節(jié)點(diǎn)數(shù)量也相應(yīng)增多，而這些計算節(jié)點(diǎn)都需要與QueryWorker 進(jìn)行通信，最終導(dǎo)致DSA 的查詢時間增大。

圖8 不同參數(shù)對查詢時間的影響Fig.8 Influence of different parameters on query time

5.4 四種分布式算法的比較

5.4.1 不同數(shù)量的范圍查詢時間比較

本組實驗設(shè)定不同數(shù)量的范圍查詢，以測試4 種算法的查詢時間，實驗結(jié)果如圖9（a）所示?？梢钥闯?，DSA 的性能總是優(yōu)于NS、GI 以及DHI。這是因為NS 在處理每個查詢時，所有服務(wù)器都使用暴力搜索模式，這使得其查詢時間隨著連續(xù)范圍查詢的數(shù)量呈線性增長趨勢；GI 在處理同一組連續(xù)范圍查詢時，由于缺少四叉樹索引的支持，需要比DSA檢測更多的移動對象；DHI 在處理查詢過程中，由于沒有考慮查詢區(qū)域重合率較高的查詢存在，可能將其分配到了不同的服務(wù)器，造成額外的計算開銷；而DSA 不僅考慮了傳輸代價優(yōu)化，而且采用BGI 結(jié)構(gòu)使得多個范圍查詢無需對四叉樹底層遍歷。

5.4.2 大規(guī)模移動對象的查詢時間比較

本組實驗設(shè)定不同數(shù)量的移動對象，以測試4 種算法性能所受影響。在該組實驗中，一次性向Qq輸入104個連續(xù)范圍查詢，4 種算法處理所有查詢的時間如圖9（b）所示。隨著查詢數(shù)量的增加，NS 的查詢時間呈線性增長，而GI、DSA 以及DHI 的性能幾乎不受影響。這是因為NS 需要掃描所有移動對象來處理每次查詢，而GI、DSA 以及DHI 可以有效地對搜索空間進(jìn)行修剪，即使移動對象的數(shù)量急劇增長，也只需要處理有限的移動對象數(shù)量。DSA 與DHI 性能明顯優(yōu)于GI，這是因為DSA 與DHI 分別引入了四叉樹索引和R-tree 索引，能進(jìn)一步提高索引效率，有效處理大規(guī)模移動對象范圍查詢。

圖9 4個算法的初始查詢時間的比較Fig.9 Comparison of initial query time among four algorithms

5.4.3 增量連續(xù)查詢的處理時間比較

本組實驗中，向Qq一次性輸入2 000 個范圍查詢，令其隨機(jī)移動，然后測試4 種方法的增量查詢時間，實驗結(jié)果如圖10 所示。在實驗中，記錄了在5 個連續(xù)的時間點(diǎn)上用4 種方法處理這些查詢的時間。可以看到DSA 的性能優(yōu)于其他3 種方法，尤其是在最后4 個時間點(diǎn)上。NS 和GI 把每次范圍查詢作為新的查詢，增量查詢時間基本不變；DHI 未考慮多個并發(fā)范圍查詢之間的共享計算問題，從而進(jìn)行冗余的計算；而DSA 每次只需計算每個查詢的增量結(jié)果，有效降低了增量查詢時間。

圖10 增量查詢時間比較Fig.10 Comparison of incremental query time

5.4.4 不同算法的吞吐量比較

本組實驗通過計算連續(xù)范圍查詢的初始結(jié)果來評估3種查詢方法的吞吐量。在該組實驗中，查詢點(diǎn)以不同的速率進(jìn)入系統(tǒng)，然后更新緩存在Qq中的查詢點(diǎn)數(shù)量，設(shè)置緩存隊列Qq容量為104。圖11 是DSA、GI、NS 的吞吐量實驗結(jié)果。從圖11（a）中可以看出，當(dāng)速率（vq）不大于4 000 OPS 時，Qq的占用容量一直較小，但當(dāng)速率（vq）達(dá)到5 000 OPS 時，其占用容量開始明顯增加。因此，DSA 的吞吐量約為4 000 OPS。從圖11（b）、（c）中可以看出，GI 和NS 的吞吐量分別約為3 000 OPS 和1 000 OPS，均小于DSA。這說明DSA 能夠很好地在分布式集群上處理大規(guī)模移動對象連續(xù)范圍查詢。

圖11 DSA、GI、NS的吞吐量Fig.11 Throughput of DSA，GI，NS

6 結(jié)語

本文提出了一種由網(wǎng)格索引與彈性四叉樹組成的移動對象分布式索引結(jié)構(gòu)DDI，該結(jié)構(gòu)能夠提供高效的剪枝效力，具有較低的維護(hù)代價且易于部署到分布式服務(wù)器集群，具備良好的可擴(kuò)展性?；谠撍饕Y(jié)構(gòu)，本文進(jìn)一步提出了分布式增量連續(xù)查詢算法，該算法設(shè)計了面向高并發(fā)查詢的共享計算策略以及面向連續(xù)范圍查詢的增量查詢策略，能有效降低查詢代價。最后，通過大量實驗對本文方法的性能進(jìn)行了充分驗證。

本文提出的移動對象分布式索引結(jié)構(gòu)DDI 主要處理基于歐氏距離的范圍查詢，未來將進(jìn)一步研究基于路網(wǎng)的移動對象分布式范圍查詢算法。