[發(fā)明專利]用于生成數(shù)據(jù)集結(jié)構(gòu)的方法以及用于向移動(dòng)設(shè)備提供基于位置的服務(wù)的方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201380053698.7
• 申請(qǐng)日: 2013-04-09
• 公開（公告）號(hào): CN104854885B
• 公開（公告）日: 2019-06-28
• 發(fā)明（設(shè)計(jì)）人: D·多布瑞;N·F·維埃拉多斯桑托斯
• 申請(qǐng)（專利權(quán)）人: NEC實(shí)驗(yàn)室歐洲有限公司
• 主分類號(hào): H04W4/021
• 分類號(hào): H04W4/021;G06F16/29;G06F16/22;H04L29/08
• 代理公司: 中科專利商標(biāo)代理有限責(zé)任公司 11021
• 代理人: 王波波

本發(fā)明公開了一種用于生成數(shù)據(jù)集結(jié)構(gòu)的方法，所述方法包括以下步驟：將地理區(qū)域分割成多個(gè)優(yōu)選為尺寸相等的區(qū)塊，其中所述地理區(qū)域包括多個(gè)興趣區(qū)域，將所述區(qū)塊與多個(gè)服務(wù)器相關(guān)聯(lián)，其中每個(gè)區(qū)塊根據(jù)一致性哈希函數(shù)與所述服務(wù)器中的至少一者相關(guān)聯(lián)，針對(duì)每個(gè)區(qū)塊生成包括與所述區(qū)塊相交的興趣區(qū)域的第一數(shù)據(jù)集，其中所述第一數(shù)據(jù)集的所述興趣區(qū)域由所述區(qū)塊的邊緣修整或者完全包含在所述區(qū)塊中，針對(duì)每個(gè)區(qū)塊生成包括溢出部分的第二數(shù)據(jù)集，其中所述溢出部分中的每一者均是第一數(shù)據(jù)集的興趣區(qū)域的一部分，由所述區(qū)塊的邊緣修整并且位于所述區(qū)塊的外部，以及針對(duì)每個(gè)區(qū)塊將所述第一數(shù)據(jù)集和所述第二數(shù)據(jù)集存儲(chǔ)在與所述區(qū)塊相關(guān)聯(lián)的服務(wù)器處。此外，還公開了一種用于提供基于位置的服務(wù)的方法和系統(tǒng)。

本發(fā)明的第一方面涉及一種用于針對(duì)基于位置的服務(wù)生成數(shù)據(jù)集結(jié)構(gòu)的方法。本發(fā)明的第二方面涉及一種使用通過根據(jù)本發(fā)明第一方面的方法生成的數(shù)據(jù)集結(jié)構(gòu)在地理區(qū)域內(nèi)向移動(dòng)設(shè)備提供基于位置的服務(wù)的方法和系統(tǒng)。

在移動(dòng)性越來越高的世界中，源自移動(dòng)設(shè)備的大量信息都可供應(yīng)用程序開發(fā)人員利用。然而，對(duì)原始數(shù)據(jù)的訪問幾乎都是不夠的，并且可能顯得過于繁瑣。尤其是在基于位置的服務(wù)(LBS)方面，對(duì)原始位置數(shù)據(jù)的處理可能復(fù)雜而龐大，使得這種處理不應(yīng)由資源有限的移動(dòng)設(shè)備來執(zhí)行。通常，應(yīng)用程序開發(fā)人員依賴于對(duì)數(shù)據(jù)提供某種預(yù)處理的框架，從而實(shí)現(xiàn)了更高水平的抽象以及更豐富的應(yīng)用。

地理圍欄就是一種這樣的更高水平的抽象。考慮到兩次連續(xù)位置更新PL(先前位置)和CL(當(dāng)前位置)，地理圍欄問題在于，確定在兩個(gè)位置之間退出的興趣區(qū)域集合以及進(jìn)入的興趣區(qū)域集合以便生成與這些進(jìn)入和退出的區(qū)域有關(guān)的動(dòng)作。

圖1示出了地理圍欄問題的基本概念。在第一位置更新時(shí)，移動(dòng)設(shè)備位于區(qū)域1內(nèi)的先前位置PL處。在于第一位置更新之后執(zhí)行的第二位置更新時(shí)，移動(dòng)設(shè)備位于區(qū)域2內(nèi)的當(dāng)前位置CL處。這就意味著，移動(dòng)設(shè)備已從PL移動(dòng)到CL并且從區(qū)域1移動(dòng)到區(qū)域2。地理圍欄系統(tǒng)將以正被退出的形式觸發(fā)區(qū)域1并且以正被進(jìn)入的形式觸發(fā)區(qū)域2。

一種用于計(jì)算退出和進(jìn)入的地理圍欄的簡(jiǎn)單算法是，首先獲得其中包含先前位置PL的地理圍欄集合(先前集合)以及其中包含當(dāng)前位置CL的地理圍欄集合(當(dāng)前集合)。退出和進(jìn)入集合(是指退出和進(jìn)入的地理圍欄)可以如下方式確定：

這就意味著，進(jìn)入集合包含當(dāng)前集合的不包含在先前集合中的每個(gè)地理圍欄。

隨著利用地理標(biāo)記數(shù)據(jù)的基于位置的服務(wù)激增，以及啟用這些服務(wù)的移動(dòng)設(shè)備的數(shù)量與日俱增，需要采用策略來處理所涉及的大量數(shù)據(jù)。此外，必須生成對(duì)大量查詢的響應(yīng)。地理標(biāo)記數(shù)據(jù)編索引的現(xiàn)有技術(shù)采用了某種分區(qū)機(jī)制來更好地分配數(shù)據(jù)和平衡負(fù)荷。

Jinbao Wang et al.“Indexing multidimensional data in a cloud system”(SIGMOD 10，2010)(王金寶等人，“在云系統(tǒng)中對(duì)多維數(shù)據(jù)編索引”，數(shù)據(jù)管理專業(yè)委員會(huì)會(huì)議，2010年)中公開了一種方法，這種方法使用基于RT-CAN(CAN中基于R樹的索引)的方法。將全局索引散布到被組織為基于邏輯CAN(內(nèi)容可尋址網(wǎng)絡(luò))的疊加網(wǎng)絡(luò)的不同群集服務(wù)器。使用多種算法(其中之一為動(dòng)態(tài)算法)來優(yōu)化系統(tǒng)，從而降低查詢和索引維護(hù)成本。

在地理圍欄系統(tǒng)中，當(dāng)跨不同服務(wù)器來對(duì)不同區(qū)域分區(qū)時(shí)，算法要求所有服務(wù)器計(jì)算當(dāng)前集合和先前集合，并且然后對(duì)這兩個(gè)集合進(jìn)行運(yùn)算以分別計(jì)算進(jìn)入的和退出的區(qū)域(如先前兩個(gè)公式所詳述)。這就意味著，要么由不同服務(wù)器將這兩個(gè)集合轉(zhuǎn)發(fā)到負(fù)責(zé)減去這些集合的第三服務(wù)器，要么集合在隨后執(zhí)行減法的兩個(gè)服務(wù)器之間自己交換。這就引起高延遲以及在服務(wù)器之間要交換大量消息。

LBS目前是非常熱門的話題，自然利用了越來越多地“連接的”世界的本質(zhì)，在這個(gè)世界中存在各種各樣的移動(dòng)設(shè)備。US 7,848,765 B2公開了涉及LBS的多種方法和系統(tǒng)。然而，其內(nèi)容并未提供與降低延遲或減少所交換的消息數(shù)量有關(guān)的任何幫助。