基于位置服務(wù)上的信息發(fā)布/訂閱數(shù)據(jù)建模研究

張素智，徐家興，魏萍萍

（鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，鄭州450002）

基于位置服務(wù)上的信息發(fā)布/訂閱數(shù)據(jù)建模研究

張素智，徐家興，魏萍萍

（鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，鄭州450002）

目前，基于內(nèi)容、主題在線發(fā)布/訂閱系統(tǒng)的數(shù)據(jù)建模和匹配算法缺乏面向LBS的支持，因此提出基于LBS服務(wù)的信息發(fā)布/訂閱數(shù)據(jù)建模。在該建模中，用戶只需要訂閱感興趣的信息，就能夠在當(dāng)前所在位置接收訂閱信息，這有效地解決現(xiàn)有的發(fā)布/訂閱系統(tǒng)中數(shù)據(jù)匹配的冗余和低精度的問(wèn)題。通過(guò)仿真實(shí)驗(yàn)，將數(shù)據(jù)模型應(yīng)用于城市信息發(fā)布平臺(tái)系統(tǒng)中。測(cè)試結(jié)果表明，該模型提高準(zhǔn)確度，減少數(shù)據(jù)冗余，適合大規(guī)模發(fā)布/訂閱應(yīng)用需求。

查詢處理；索引；信息發(fā)布；位置定位

0　引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展和普及，特別是隨著移動(dòng)計(jì)算、網(wǎng)格計(jì)算、云計(jì)算等新的網(wǎng)絡(luò)計(jì)算模式的興起，分布式應(yīng)用系統(tǒng)的范圍和規(guī)模都發(fā)生了很大變化，分布式計(jì)算已成為構(gòu)建大型信息發(fā)布系統(tǒng)的主流技術(shù)。這就需要一個(gè)更加機(jī)動(dòng)的通信和互動(dòng)機(jī)制，以反映系統(tǒng)中動(dòng)態(tài)的和松散耦合等特點(diǎn)，并發(fā)布/訂閱模型使功能上能夠滿足上述要求，這種機(jī)制受到越來(lái)越多科學(xué)家的關(guān)注。典型的發(fā)布/訂閱系統(tǒng)的基本模型，如圖1所示，其中包括發(fā)布、訂閱和事件代理。

圖1　發(fā)布/訂閱模型

1　數(shù)據(jù)建模

LBS發(fā)布/訂閱數(shù)據(jù)模型包括：概念模型、發(fā)布事件模型，和訂閱事件［1］模型。

1.1概念模型

在城市信息發(fā)布平臺(tái)中，使用本體建立一個(gè)概念模型。本體［2］是一個(gè)特定于域的概念，是概念之間的關(guān)系和概念定義關(guān)系應(yīng)該遵循的約束條件。概念模型［3］清楚地定義一個(gè)字段的約束以及它們之間的應(yīng)遵循的關(guān)系等。發(fā)布內(nèi)容的事件必須滿足限制的概念和關(guān)系，即內(nèi)容必須定義在一個(gè)概念模型中，必須有存在概念模型中定義的事件；當(dāng)事件模型接收到一個(gè)事件，它必須接觸事件內(nèi)容和概念模型，并進(jìn)行解決；用戶發(fā)布訂閱必須滿足定義和概念模型的約束。因此，概念模型是整個(gè)系統(tǒng)的基礎(chǔ)，并發(fā)揮著重要的作用。

定義1：一個(gè)概念模型可以使用six-tuples O=（C、P、CR、PR、X、L）：

（1）C表示一組概念類(lèi)的應(yīng)用程序域，每個(gè)實(shí)體屬于一個(gè)或多個(gè)類(lèi)。例如在基于網(wǎng)絡(luò)圖的信息發(fā)布平臺(tái)中，類(lèi)層次結(jié)構(gòu)之間的關(guān)系如圖2所示。

圖2　類(lèi)和信息平臺(tái)的關(guān)系

（2）P表示一組屬性。每個(gè)類(lèi)都有一個(gè)或多個(gè)屬性?；诰W(wǎng)絡(luò)圖的在城市信息發(fā)布平臺(tái)，例如，一些屬性之間的關(guān)系如圖3所示。

圖3　屬性和關(guān)系的信息平臺(tái)

（3）CR是一組概念之間的關(guān)系，RP是一組相關(guān)的更多屬性。概念及其屬性關(guān)系主要是繼承、相交、平行等。

（4）X代表一組約束之間的概念和屬性，描述為每個(gè)類(lèi)允許哪些屬性存在，屬性的屬性值為空，是什么類(lèi)型的信息等。

（5）L表示一組區(qū)域信息，包括一些地理區(qū)域，它的大小并不是固定的，但是根據(jù)相關(guān)性劃分。每個(gè)消息都有相應(yīng)的位置信息。

這是一個(gè)訂閱條件，和一個(gè)實(shí)體類(lèi)B，A到B的子類(lèi)或間接父類(lèi)，那么這兩個(gè)可以匹配。同樣，如果P1屬性訂閱和事件數(shù)據(jù)的屬性P2和P1，P2的子類(lèi)或間接父類(lèi)，這兩個(gè)也可以匹配。例如，某人的訂閱條件shopType=“餐館、茶館”，在一個(gè)事件數(shù)據(jù)shopType=“餐館、茶館”，那么事件和訂閱條件相匹配。

1.2事件模型

城市信息發(fā)布平臺(tái)使用RDF語(yǔ)言［4］來(lái)描述事件模型，與triple-tulles（主題、屬性、對(duì)象）的形式表達(dá)每個(gè)triple-tulle稱為語(yǔ)句的事實(shí)。其中，主題是說(shuō)對(duì)資源URI引用，屬性代表屬性URI引用，對(duì)象代表價(jià)值或URI引用，或者文字值。商家發(fā)布信息，并將改變概念模型到事件模型，最后統(tǒng)一到RDF格式。最后，事件服務(wù)代理將發(fā)送一個(gè)RDF-formatted事件到所有相匹配的用戶，這在一定程度上，解決異構(gòu)結(jié)構(gòu)的問(wèn)題。

定義2：使用RDF eight-tuples事件模型：

（1）V代表一個(gè)組中的所有節(jié)點(diǎn)的事件模型圖。節(jié)點(diǎn)包括URI引用節(jié)點(diǎn)，文本節(jié)點(diǎn)，或者一個(gè)空白的節(jié)點(diǎn)。

（2）A代表一個(gè)弧的所有事件模型圖，和弧是URI引用。

（3）LV表示一組標(biāo)簽中的所有節(jié)點(diǎn)事件模型。

（4）LA表示一組標(biāo)簽所有弧事件模型。

（5）θ表示一組映射函數(shù)從節(jié)點(diǎn)到節(jié)點(diǎn)的標(biāo)簽，即vθ-LV。

（6） 表示一組電弧弧標(biāo)簽的所有映射函數(shù)，即v -LV。

（7）X表示一組約束事件模型。

（8）L表示一組區(qū)域信息的概念。

圖4顯示了我們，在城市的信息發(fā)布平臺(tái)，李寧專(zhuān)賣(mài)店，東風(fēng)5號(hào)公路附近賣(mài)籃球鞋，他們的價(jià)格是1000至2000元人民幣。商家發(fā)布的信息，事件模型統(tǒng)一格式的事件模型。

1.3訂閱模式

用戶的訂閱［5］是由幾個(gè)”和“操作的“報(bào)表模式”。模式每個(gè)語(yǔ)句描述的事件發(fā)表聲明，并且每個(gè)訂閱可以表示為一系列的5個(gè)元素。

定義3：訂閱聲明為5個(gè)元素（主體、客體、價(jià)值、過(guò)濾器（主題）、過(guò)濾器（對(duì)象）），主體和客體提供訂閱的主題和對(duì)象的語(yǔ)句，它可以表示為一個(gè)特定的值，或者也可以使用變量來(lái)表示，每個(gè)變量”？”作為前綴，如？l，？2，等等?；∵B接到主體和客體的屬性代表，其中每個(gè)屬性代表一個(gè)類(lèi)型。

過(guò)濾器（主題）和過(guò)濾器（對(duì)象）代表頂點(diǎn)，綁定可以是空的。在事件圖中，每個(gè)頂點(diǎn)都有一個(gè)特定的值，但是在訂閱圖中，我們?cè)试S的對(duì)象和對(duì)象都之間是約束和不受約束的變量，它可以在事件中的匹配任何值，約束變量只能匹配約束的值。過(guò)濾器可以被表示為一個(gè)約束（？x，op，v）？x是一個(gè)變量，op是運(yùn)營(yíng)商，v代表一個(gè)變量值。例如，（？1＞100）描述這個(gè)變量節(jié)點(diǎn)只能有一個(gè)匹配的值大于100的節(jié)點(diǎn)圖。過(guò)濾操作符作為一元運(yùn)算符，即：＞、＜、=、≥≤，≠，和∈。

圖4　示例事件模型圖

如果一個(gè)人現(xiàn)在在鄭州輕工業(yè)大學(xué)附近（東風(fēng)路5號(hào)）想買(mǎi)一雙李寧的籃球鞋，它的價(jià)格在1000～2000元之間，對(duì)應(yīng)的訂閱聲明可以被描述為：

（_R，rdf：位置？1、null（？1、∈的東風(fēng)5號(hào)路附近）

（_R目標(biāo)？2、null（？2='籃球鞋'））

（_R、名稱？3、null（？3=“LiNing”））

（_R、價(jià)格？4、null（？4＞＜1000～2000））

每個(gè)訂閱事件可以表示為一個(gè)訂閱圖，如圖5所示：

圖5　訂閱模型圖的例子

2　模型應(yīng)用

2.1匹配算法

匹配算法的實(shí)質(zhì)是給定一個(gè)訂閱集S和發(fā)布事件P，找到滿足訂閱集S的所有發(fā)布事件集合的過(guò)程，暴力匹配方法匹配［6］算法是最典型的方法，它會(huì)將所有的發(fā)布事件的元素P組與訂閱信息匹配，匹配算法需要每個(gè)屬性來(lái)比較，這樣用戶等待時(shí)間太長(zhǎng)，并且會(huì)產(chǎn)生大量的重復(fù)匹配，大大減少匹配的效率。為了解決匹配效率低下等問(wèn)題，結(jié)合基于LBS的信息數(shù)據(jù)模型［7］，設(shè)計(jì)多個(gè)屬性索引的快速匹配算法。算法描述如下：

（1）建立一個(gè)索引表的訂閱集，過(guò)濾器的過(guò)濾條件下（主題）和過(guò)濾器（對(duì)象）在相應(yīng)的分類(lèi)和排序，即每個(gè)訂閱報(bào)表需要分類(lèi)和排序操作。如果運(yùn)算符“＞”和“＞=”，按照升序排序；如果它是“＜”和“＜=”，在降序排列。當(dāng)一個(gè)序列中的值滿足要求，之后的一切屬性的值對(duì)應(yīng)值來(lái)滿足需求，價(jià)值不符合上述標(biāo)準(zhǔn)將不再找到匹配，這可以極大地減少匹配。

步驟2：根據(jù)操作符的類(lèi)型，事件模型屬性設(shè)置匹配約束，發(fā)現(xiàn)和綁定在一個(gè)位置，其屬性權(quán)重增加，附近的位置信息，找到匹配的位置。使用Haversin算法：

地球的半徑R，理想的平均6371公里；代表兩個(gè)緯度，θ1θ2代表兩個(gè)經(jīng)度不同；Δφ代表經(jīng)度差異，讓?duì)?= θ2then Δφ=rcsin（sin（d/2R））/cosθ弧度轉(zhuǎn)換：dlng= Δφ*180/π，讓?duì)う?0，Δθ=d/R弧度轉(zhuǎn)換得：dlat= Δθ*180/π。最后，我們可以得到4點(diǎn)：左上角：（lat+dlat，lng-dlng），右上角：（lat+dlat，lng+dlng），左下角：（latdlat，lng-dlng），右下角：（lat dlat，lng+dlng）。

（3）根據(jù)操作符尋找匹配，如果“=”操作符，則直接匹配模型的產(chǎn)權(quán)約束，否則覆蓋的集合中的原有操作符，包括匹配的屬性，將滿足需求訂閱信息收集到臨時(shí)TempList集合，然后在臨時(shí)集合templist中的第二屬性作為第一屬性匹配方法匹配，重復(fù)第三步依次類(lèi)推，直到這一事件模型的所有屬性完全匹配。

（4）臨時(shí)返回結(jié)果集TempList，其中結(jié)果之一是匹配成功的訂閱消息。

2.2實(shí)驗(yàn)結(jié)果

圖6　不同的數(shù)據(jù)模型來(lái)匹配精度的影響

圖7　訂閱數(shù)量匹配速度的影響

實(shí)驗(yàn)I：測(cè)試不同的數(shù)據(jù)模型來(lái)匹配精度的影響，如圖6。

結(jié)果表明，傳統(tǒng)在訂閱模式匹配的準(zhǔn)確性隨著訂閱數(shù)量增多不斷減少，并且在相同訂閱數(shù)量的情況下，基于LBS的訂閱系統(tǒng)在準(zhǔn)確度上一直占有優(yōu)勢(shì)，該圖表明，滿足用戶需求的結(jié)果所占的比例越來(lái)越少；基于LBS的準(zhǔn)確發(fā)布訂閱模型匹配的變化不明顯，且精度更高，更接近用戶需求。隨著需求的不斷增長(zhǎng)，新的訂閱模型更利于滿足用戶的訂購(gòu)。

實(shí)驗(yàn)II：測(cè)試的影響訂閱的數(shù)量匹配速度，如圖7。

結(jié)果表明，傳統(tǒng)的算法隨著訂閱數(shù)量的增多，消耗時(shí)間越來(lái)越長(zhǎng)，與多屬性索引匹配算法相比較，在最初訂閱數(shù)量少時(shí)，還擁有較好的匹配效率，當(dāng)訂閱數(shù)量過(guò)多時(shí)，新算法明顯優(yōu)于傳統(tǒng)的算法。由于提出的算法支持排序、適應(yīng)多屬性索引、選擇連續(xù)、減少比較次數(shù)，從而減少了匹配時(shí)間，提高了匹配效率，因此多屬性索引匹配算法更適合于大量的訂閱過(guò)程。

3　結(jié)語(yǔ)

近年來(lái)，隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，特別是移動(dòng)網(wǎng)絡(luò)，發(fā)布/訂閱模型［8］逐漸增多并得到廣泛應(yīng)用。模型的關(guān)鍵是如何實(shí)現(xiàn)信息和訂閱之間的匹配效率。相對(duì)于基于主題/內(nèi)容的發(fā)布/訂閱系統(tǒng)模型，我們提出一個(gè)新的基于LBS發(fā)布/訂閱模型數(shù)據(jù)模型。它使用邏輯算子的特點(diǎn)來(lái)實(shí)現(xiàn)精確、快速和高效的匹配，因此基于LBS的定位系統(tǒng)更適用于大規(guī)模分布式發(fā)布-訂閱系統(tǒng)?？傊?，實(shí)驗(yàn)表明數(shù)據(jù)模型匹配的準(zhǔn)確性比其他方法有更大的進(jìn)步。

［1］Jiangang Ma，Tao Huang.Underlying Techniques for Large-Scale Distributed Computing Oriented Publish/Subscribe System［J］.Jiangang Ma.Beijing：Journal of Software，2006：134-147.

［2］Jing An.Design of Information Service System Based on LBS［C］.Jing An.Zhejiang：Digital Technology and Application，2014：164.

［3］Xi-wei Feng，Jian-hua Wang，Yao Feng，Pei-guang Lin.Semantic Web-Based Matching Algorithm for Publish/Subscribe System［J］. Xiwei Feng.Beijing：Journal of University of Science and Technology Beijing，2013：544-550.

［4］Xiao Zheng，Jun-zhou Luo，Jiu-xin Cao，Ai-bo Song.A Publish Subscribe Based Information Dissemination Model for QoS of Web Services［J］.Xiao Zheng.Beijing：Journal of Computer Research and Development，2010：56-69.

［5］Guo-yan Xu，Zhi-jian Wang，Xiao-fang Li.Research on Publish/Subscribe Model Based on Web Services［J］.Guoyan Xu.Nanjing：Microelectronics&Computer，2009：29-60.

［6］Zhi-wen Zou，Qiao Li.Subscription Partition Based Multi Index Parallel Matching Algorithm［J］.Zhiwen Zou.Jiangsu：Journal of Huazhong University of Science and Technology（Natural Science Edition），2013（S2）.

［7］Yong-feng Li，Hui-lin Wang.Indexing and Filtering Metadata for Content Based Publish/subscribe System［J］.Yongfeng Li.Beijing：Computer engineering and design，2013：10-32.

［8］Qiang Zhang，Jian-hua Li.Real-Time Performance Analysis of Information Sharing Based on a Publish/Subscribe Model［J］.Qiang Zhang.Beijing：Military Operations Research and Systems Engineering，2013：33-35.

Research on Data Modeling of Information Publish/Subscribe Based on LBS

ZHANG Su-zhi，XU Jia-xing，WEI Ping-ping
（School of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450002）

At present，the content-based，theme-based publish/subscribe system currently has short of supporting LBS in data modeling and matching algorithm，so proposes a data modeling of information publish/subscribe based on LBS，and applies the traditional pattern of the publish/subscribe to LBS in the information service.In the model，users only need to subscribe your interested information，and then receive subscription information near your current location，and effectively solve the existing publish/subscribe system in the data matching redundancy and low accuracy of the results.Through simulation experiment，the data modeling is applied to the city information publishing platform system.The test results show that the model has a great improvement in the accuracy of matching results and reduces the data redundancy，which is suitable for large scale publish/subscribe application requirements.

Query Processing；Index；Information Release；Position Location

國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目（No.61201447）

1007-1423（2016）23-0027-05DOI：10.3969/j.issn.1007-1423.2016.23.007

張素智（1965-），男，教授，博士，研究方向?yàn)閃eb數(shù)據(jù)庫(kù)、分布式計(jì)算和異構(gòu)系統(tǒng)集成

徐家興（1990-），男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與集成

魏萍萍（1990-），女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與集成

2016-05-24

2016-08-10