楊小漫,李曉宇
(鄭州大學(xué) 信息工程學(xué)院,河南 鄭州450001)
隨著無線通信技術(shù)、移動(dòng)互聯(lián)網(wǎng)和智能移動(dòng)終端的迅速發(fā)展,基于位置的服務(wù) (location based services,LBS)在軍事、交通、物流等諸多領(lǐng)域得到了廣泛應(yīng)用,并為人們?nèi)粘I顜砹撕艽髱椭?。?jù)統(tǒng)計(jì),在人們?nèi)粘I钪?,?0%的信息與位置相關(guān)。為了查找某個(gè)人、某個(gè)地點(diǎn),常常耗去人們大量的精力。因此,為適應(yīng)節(jié)奏越來越快的社會(huì)生活加,省時(shí)、快速、高效的位置信息查詢將成為一種普遍的追求[1]。結(jié)合無線通信技術(shù)的即時(shí)性和互聯(lián)網(wǎng)豐富信息的全球共享性,LBS使隨時(shí)隨地的信息溝通和處理成為可能[2,3]。然而,由于移動(dòng)網(wǎng)絡(luò)的不穩(wěn)定性和移動(dòng)終端資源的有限性,目前LBS應(yīng)用出現(xiàn)查詢反應(yīng)慢等諸多問題。現(xiàn)有的LBS領(lǐng)域的研究多集中在無線網(wǎng)絡(luò)的傳輸和LBS應(yīng)用層面的擴(kuò)展,在服務(wù)器端很多學(xué)者引入云計(jì)算,但在LBS系統(tǒng)中的應(yīng)用云計(jì)算還比較少,要真正實(shí)現(xiàn)LBS的廣泛應(yīng)用,還應(yīng)解決數(shù)據(jù)的收集和處理問題。在移動(dòng)客戶端和服務(wù)器端頻繁斷接情況下,結(jié)合移動(dòng)終端較高的處理能力和存儲(chǔ)能力等優(yōu)點(diǎn),本文提出基于數(shù)據(jù)預(yù)處理策略的“預(yù)取”模式,以此來縮短查詢等待時(shí)間、改善斷接時(shí)查詢的有效性,并運(yùn)用智能學(xué)習(xí)策略提高數(shù)據(jù)預(yù)處理后的命中率,從而提高LBS應(yīng)用率。
LBS涉及到地理信息服務(wù)、計(jì)算機(jī)應(yīng)用互操作、無線通訊、用戶終端、定位技術(shù)、系統(tǒng)構(gòu)架和相關(guān)軟件等技術(shù),屬于空間信息、計(jì)算機(jī)網(wǎng)絡(luò)協(xié)同計(jì)算交叉學(xué)術(shù)領(lǐng)域。LBS是將移動(dòng)用戶不斷變化的位置和對(duì)應(yīng)的地理位置信息相聯(lián)系,并在移動(dòng)通信設(shè)備上,面向用戶提供基于空間信息的相關(guān)服務(wù)總稱。當(dāng)移動(dòng)用戶需要基于位置的信息服務(wù)時(shí),終端通過定位設(shè)備 (如GPS)獲得當(dāng)前的位置數(shù)據(jù),并實(shí)時(shí)地通過無線通信把數(shù)據(jù)上傳送到服務(wù)中心,然后服務(wù)中心服務(wù)器根據(jù)位置和服務(wù)要求進(jìn)行分析、決策,進(jìn)而再下傳到移動(dòng)終端?;谖恢梅?wù)的巨大魅力正是在正確的時(shí)間、正確的地點(diǎn)把正確的信息發(fā)送給正確的人。
近年來,隨著越來越繁華的大規(guī)模商業(yè)區(qū)的出現(xiàn),購(gòu)物已不再是件容易的事情。當(dāng)移動(dòng)用戶進(jìn)入毫不熟悉的商業(yè)熱區(qū)時(shí),急需知道 “我在哪里?附近是什么?附近哪些商店最受歡迎?最省時(shí)最簡(jiǎn)便的到達(dá)路線是?”等信息。攜帶基于LBS購(gòu)物導(dǎo)航的用戶則能隨時(shí)隨地獲取當(dāng)前的地理位置及其附近各種場(chǎng)所的LBS資訊,讓購(gòu)物變得即省時(shí)又省力。這種購(gòu)物導(dǎo)航不僅為用戶購(gòu)物提供便利而且還能提高商業(yè)區(qū)的銷售量。
基于LBS的購(gòu)物導(dǎo)航所提供的功能:顯示用戶當(dāng)前位置;顯示附近興趣點(diǎn) (POI)及其詳細(xì)信息;依據(jù)用戶偏好提供推薦列表;提供最佳路徑。如圖1所示。
首先,當(dāng)移動(dòng)用戶通過定位系統(tǒng)確定自己當(dāng)前的精確位置后,以用戶的位置偏移量為觸發(fā)條件,依照設(shè)置的搜索條件 (包括搜索范圍和所屬類別)搜索,動(dòng)態(tài)更新移動(dòng)終端的服務(wù)信息。其次,通過以往經(jīng)驗(yàn)進(jìn)行知識(shí)學(xué)習(xí),并依據(jù)用戶時(shí)空位置和偏好提供個(gè)性化的推薦列表。然后,用戶參考推薦列表,通過多方面比較選定目標(biāo)點(diǎn),購(gòu)物導(dǎo)航依據(jù)交通方式 (步行、公交、開車等)提供最佳行程路線。因此,攜帶基于LBS購(gòu)物導(dǎo)航的移動(dòng)用戶能夠?qū)γCI虡I(yè)區(qū)的信息了如指掌,讓用戶體驗(yàn)一個(gè)輕松愉快的購(gòu)物旅程。
基于LBS購(gòu)物導(dǎo)航的請(qǐng)求流程如下:移動(dòng)客戶端首先發(fā)送相關(guān)位置查詢請(qǐng)求到服務(wù)器端;服務(wù)器端接收到請(qǐng)求后進(jìn)行服務(wù)器端數(shù)據(jù)庫查詢,并返回查詢結(jié)果,客戶端顯示附近POI位置;若移動(dòng)用戶繼續(xù)查看某POI的詳細(xì)信息時(shí),需再次發(fā)送查詢請(qǐng)求給服務(wù)器;服務(wù)器再次依據(jù)請(qǐng)求執(zhí)行數(shù)據(jù)庫查詢,返回結(jié)果給客戶端[4,5]。如圖2所示。
圖2 LBS請(qǐng)求流程
從圖2中可看出,用戶每查看一次就發(fā)送一次請(qǐng)求,服務(wù)器端也隨之不斷地查詢服務(wù)器端數(shù)據(jù)庫,并返回查詢結(jié)果。由于無線網(wǎng)絡(luò)的不穩(wěn)定特性和帶寬有限性,這種策略不但繁瑣、查詢時(shí)間慢、浪費(fèi)用戶等待時(shí)間,而且消耗客戶端能量資源、加重服務(wù)器端負(fù)載。本文對(duì)此作出改進(jìn),提出基于查詢數(shù)據(jù)預(yù)處理的 “預(yù)取”模式,改善LBS的查詢效率。
2.1.1 LBS中數(shù)據(jù)預(yù)處理策略分析
本文是通過對(duì)服務(wù)器端和移動(dòng)終端的查詢數(shù)據(jù)預(yù)處理,來改進(jìn)繁瑣的查詢請(qǐng)求所帶來的查詢遲緩問題。在服務(wù)器端實(shí)現(xiàn)一次查詢所有,即:查詢到POI的同時(shí)也一并把相應(yīng)的詳細(xì)信息查詢出來,并生成推薦列表;在移動(dòng)終端上,對(duì)接收到的查詢結(jié)果集進(jìn)行本地移動(dòng)數(shù)據(jù)庫存儲(chǔ)。當(dāng)移動(dòng)用戶查詢某興趣點(diǎn)的詳細(xì)信息時(shí),實(shí)際上是查詢本地?cái)?shù)據(jù)庫,或在服務(wù)器端的查詢結(jié)果中匹配要查詢的信息[6]。
改進(jìn)的請(qǐng)求流程如圖3所示。
圖3 “預(yù)取”模式中的請(qǐng)求流程
從圖3中可明顯看出,改進(jìn)的基于數(shù)據(jù)預(yù)處理模式可明顯減少無線網(wǎng)絡(luò)中查詢請(qǐng)求次數(shù)及傳輸次數(shù),進(jìn)而提高查詢效率。
2.1.2 提高命中率策略
在改進(jìn)的 “預(yù)取”模式中,服務(wù)器端是在未再次接收請(qǐng)求之前而采取預(yù)取策略,那么就涉及到預(yù)取的信息是否滿足移動(dòng)用戶的當(dāng)前需要,即預(yù)取策略能否提高查詢命中率。目前大部分LBS研究都處于為移動(dòng)用戶提供信息的階段,缺乏對(duì)信息的智能化推理過程。本文采用基于經(jīng)驗(yàn)的智能學(xué)習(xí),服務(wù)器端通過對(duì)歷史時(shí)空路徑數(shù)據(jù)學(xué)習(xí),以最大概率查詢出滿足移動(dòng)用戶當(dāng)前需求的信息,生成推薦列表,確保在正確地點(diǎn)、正確時(shí)間為用戶提供正確的、個(gè)性化服務(wù)[7]。從而提高服務(wù)器端推送信息的命中率,進(jìn)而使LBS應(yīng)用更人性化、更貼近人們的生活。
2.1.3 可行性分析
本文 “預(yù)取”模式的關(guān)鍵是服務(wù)器端在再次接收查詢請(qǐng)求之前預(yù)先查詢出有關(guān)詳細(xì)信息和服務(wù)推薦信息,并在客戶端本地移動(dòng)數(shù)據(jù)庫中存儲(chǔ)這些信息。這種策略是以犧牲數(shù)據(jù)傳輸量和移動(dòng)客戶端的存儲(chǔ)量來換取查詢響應(yīng)時(shí)間。目前,移動(dòng)設(shè)備迅速發(fā)展,性能得到很大提高,移動(dòng)終端(如智能手機(jī))的計(jì)算能力和存儲(chǔ)能力已逐漸接近計(jì)算機(jī)性能,因此這種基于數(shù)據(jù)預(yù)處理的改進(jìn)策略對(duì)目前市場(chǎng)流行的移動(dòng)智能終端來說是可行的。
另外,預(yù)查詢的推薦信息是服務(wù)器端通過大量移動(dòng)用戶歷史時(shí)空路徑經(jīng)驗(yàn)進(jìn)行知識(shí)學(xué)習(xí),依據(jù)所形成的智能策略選擇令用戶滿意的POI信息。它改變了傳統(tǒng)固定排名壟斷的現(xiàn)象,提供給移動(dòng)用戶基于環(huán)境的個(gè)性化推薦,因此推薦信息命中率也將會(huì)有所提高。
2.2.1 操作步驟
(1)當(dāng)移動(dòng)終端成功從定位系統(tǒng)獲取當(dāng)前精確位置后,移動(dòng)終端采用主動(dòng)請(qǐng)求連接方式與服務(wù)器端建立無線網(wǎng)絡(luò)連接,由客戶端發(fā)送網(wǎng)絡(luò)連接請(qǐng)求,服務(wù)器端做連接回應(yīng);
(2)移動(dòng)用戶設(shè)置定位觸發(fā)規(guī)則和搜索程序觸發(fā)規(guī)則(包括搜索范圍、商品類別、用戶偏好等信息)。依據(jù)設(shè)置的觸發(fā)條件和搜索條件對(duì)用戶附近進(jìn)行相應(yīng)的搜索,即:當(dāng)用戶位移量超過某范圍時(shí),重新定位搜索,動(dòng)態(tài)更新終端的服務(wù)信息;
(3)移動(dòng)客戶端發(fā)送附近信息查詢請(qǐng)求給服務(wù)器端。其中發(fā)送的請(qǐng)求數(shù)據(jù)包含步驟2中所設(shè)置的信息;
(4)服務(wù)器端執(zhí)行查詢請(qǐng)求。在服務(wù)器端數(shù)據(jù)庫中查詢用戶周圍的POI及相應(yīng)的詳細(xì)信息,同時(shí)依據(jù)智能策略在結(jié)果集中生成推薦列表,然后通過無線網(wǎng)絡(luò)把這些信息數(shù)據(jù)都發(fā)送到移動(dòng)客戶端;
(5)移動(dòng)客戶端接收到服務(wù)器端的查詢結(jié)果集,將POI位置標(biāo)示在電子地圖上,并向用戶推薦最佳列表;同時(shí)把搜索到的結(jié)果集作為添加數(shù)據(jù)存儲(chǔ)到本地移動(dòng)數(shù)據(jù)庫中;
(6)當(dāng)用戶點(diǎn)擊POI查看其詳細(xì)信息時(shí),這時(shí)的查詢請(qǐng)求會(huì)在本地移動(dòng)數(shù)據(jù)庫中執(zhí)行[8,9],若查詢不到結(jié)果就在服務(wù)器端的查詢結(jié)果集中匹配;
(7)查看多個(gè)詳細(xì)信息,經(jīng)過比較后,選定某一興趣點(diǎn)作為目標(biāo)點(diǎn),這時(shí)基于LBS的購(gòu)物導(dǎo)航就依據(jù)交通方式為顧客提供最佳路徑。
2.2.2 算法實(shí)現(xiàn)算法1:移動(dòng)客戶端過程算法
算法2:服務(wù)器端算法
在對(duì)查詢數(shù)據(jù)做預(yù)處理后,用戶點(diǎn)擊某POI查看詳細(xì)信息時(shí),這時(shí)在移動(dòng)客戶端的查詢有兩種情況:
(1)查看的詳細(xì)信息在本地移動(dòng)數(shù)據(jù)庫中。查詢結(jié)果已從服務(wù)器端傳送并存儲(chǔ)到本地移動(dòng)數(shù)據(jù)庫中,這時(shí)客戶端只需要查詢本地?cái)?shù)據(jù)庫即可。這種情況下,即使移動(dòng)終端與服務(wù)器斷接也能查詢到結(jié)果。另外,本地移動(dòng)數(shù)據(jù)庫查詢響應(yīng)相當(dāng)迅速而且查詢結(jié)果無需網(wǎng)絡(luò)傳輸,因而降低了對(duì)不穩(wěn)定無線網(wǎng)絡(luò)的依賴性、縮短了查詢時(shí)間。
(2)查看的詳細(xì)信息不在本地移動(dòng)數(shù)據(jù)庫中。由于數(shù)據(jù)的傳輸時(shí)延,服務(wù)器端所查詢到的詳細(xì)信息還未來得及傳輸?shù)娇蛻舳吮镜匾苿?dòng)數(shù)據(jù)庫中。這種情況下,客戶端發(fā)送查看請(qǐng)求,服務(wù)器端執(zhí)行請(qǐng)求并返回結(jié)果。這樣的查詢貌似沒什么改進(jìn),但實(shí)際上它減少了查詢時(shí)間。因?yàn)榉?wù)器已經(jīng)在用戶思考和網(wǎng)絡(luò)傳輸請(qǐng)求的這段時(shí)間中查詢到了詳細(xì)信息,只是沒來得及返回給客戶端而已。這時(shí)服務(wù)器端只需在服務(wù)器端查詢結(jié)果中匹配不需要再次查詢,與傳統(tǒng)的LBS查詢相比,節(jié)省了服務(wù)器端數(shù)據(jù)庫查詢時(shí)間。
因此,無論是哪種情況,這種改進(jìn)的 “預(yù)取”模式都能提高傳統(tǒng)LBS的查詢響應(yīng)時(shí)間,改善無線網(wǎng)絡(luò)的不穩(wěn)定性給LBS應(yīng)用帶來的查詢遲緩問題,同時(shí)減少了由于網(wǎng)絡(luò)問題引起的數(shù)據(jù)錯(cuò)誤和重發(fā)。
以三星I9250(android智能手機(jī))作為移動(dòng)客戶端,它自帶SQLite數(shù)據(jù)庫作為L(zhǎng)BS的移動(dòng)數(shù)據(jù)庫。以CPU是Pentium (R)、主頻是3.20GHz、內(nèi)存是1.96GB的PC機(jī)做Web服務(wù)器端,并安裝Tomcat 6.0和服務(wù)器端數(shù)據(jù)庫MySql 5.0。 用 JSP 做 頁 面 處 理、Servlet響 應(yīng) 客 戶 端請(qǐng)求[10-12]。
圖4橫軸為移動(dòng)終端的個(gè)數(shù),縱軸為多次成功的數(shù)據(jù)訪問所花費(fèi)的平均時(shí)間。圖中共有5條曲線,其中 “未處理”圖線代表未做數(shù)據(jù)預(yù)處理,移動(dòng)終端直接查詢服務(wù)器數(shù)據(jù)庫的平均訪問時(shí)間?!懊新省贝硪苿?dòng)終端訪問的數(shù)據(jù)恰好是經(jīng)過預(yù)處理之后在移動(dòng)終端的本地緩存中可以找到備份數(shù)據(jù)的概率。其余四條圖線分別是命中率為90%、80%、70%、60%時(shí)的移動(dòng)終端查詢數(shù)據(jù)的平均訪問時(shí)間。
圖4 平均訪問時(shí)間——移動(dòng)終端數(shù)目
實(shí)驗(yàn)結(jié)果表明,做了數(shù)據(jù)預(yù)處理之后,移動(dòng)終端查詢數(shù)據(jù)庫的平均訪問時(shí)間明顯降低,甚至在命中率僅僅剛剛超出一半的情況 (命中率60%)下仍然如此??梢姅?shù)據(jù)預(yù)處理技術(shù)可以有效地提高在基于位置的購(gòu)物導(dǎo)航中移動(dòng)終端的訪問效率。事實(shí)上,考慮到現(xiàn)實(shí)中大部分顧客的購(gòu)物興趣是趨向一致的,例如大商場(chǎng)、口碑好的商店等往往是絕大部分顧客共同的優(yōu)先選擇,因此通過對(duì)顧客購(gòu)物歷史數(shù)據(jù)做簡(jiǎn)單的智能學(xué)習(xí)就可以得到最優(yōu)的推薦排名,而語句預(yù)處理中排名靠前的商店的信息是優(yōu)先做預(yù)處理的。所以,現(xiàn)實(shí)中移動(dòng)終端查詢時(shí)命中率達(dá)到80%~90%并不困難。換句話說,本文的數(shù)據(jù)預(yù)處理模型在現(xiàn)實(shí)中可以大大提高終端用戶的訪問效率,節(jié)約用戶的時(shí)間。
另外,注意到隨著移動(dòng)終端數(shù)目的增長(zhǎng),雖然用戶的平均訪問時(shí)間在增加,但是預(yù)處理之后的訪問時(shí)間相對(duì)未作預(yù)處理的訪問時(shí)間的差距仍維持穩(wěn)定,并未明顯縮小??梢姳疚牡幕跀?shù)據(jù)預(yù)處理的模型具有較好的穩(wěn)定性,能夠在移動(dòng)終端數(shù)目較多的時(shí)候仍然保持可觀的效率收益,具有較好的實(shí)用價(jià)值。
最后,在無線網(wǎng)絡(luò)斷開時(shí),基于數(shù)據(jù)預(yù)處理的模型還能以一定的概率在終端的本地?cái)?shù)據(jù)庫中查詢到用戶需要的數(shù)據(jù),而傳統(tǒng)的模型則不能,這說明基于數(shù)據(jù)預(yù)處理的模型能夠減少對(duì)無線網(wǎng)絡(luò)的依賴性,提高購(gòu)物導(dǎo)航的可靠性。
隨著移動(dòng)智能終端的快速升級(jí),基于位置的服務(wù)在人們的生活中越來越被廣泛應(yīng)用。本文結(jié)合移動(dòng)網(wǎng)絡(luò)和移動(dòng)數(shù)據(jù)庫的特點(diǎn)提出了數(shù)據(jù)預(yù)處理技術(shù)。在基于LBS購(gòu)物導(dǎo)航中,經(jīng)實(shí)驗(yàn)驗(yàn)證這種基于數(shù)據(jù)預(yù)處理技術(shù)對(duì)不同命中率情況下的數(shù)據(jù)訪問,能有效縮短查詢時(shí)間,并且在移動(dòng)終端和服務(wù)器斷接情況下,基于數(shù)據(jù)預(yù)處理的模型依然能實(shí)現(xiàn)有效查詢,同時(shí)運(yùn)用智能學(xué)習(xí)策略提高推薦列表命中率,提供基于環(huán)境的個(gè)性化推薦。因此,這種基于數(shù)據(jù)預(yù)處理的模型能有效改善查詢效率、減少對(duì)不穩(wěn)定無線網(wǎng)絡(luò)的依賴性,具有較好的穩(wěn)定性,對(duì)基于位置的服務(wù)應(yīng)用具有潛在的實(shí)用價(jià)值。
[1]WANG Shuai,LIU Houquan,CHENG Shuangshuang.The research and application of LBS in mobile guide system [J].Micro Computer Information,2010,26 (21):97-153 (in Chinese).[王帥,劉厚泉,程雙雙.LBS在移動(dòng)導(dǎo)游系統(tǒng)中的應(yīng)用與研究 [J].微計(jì)算信息,2010,26 (21):97-153.]
[2]ZHOU Aoying,YANG Bin,JIN Cheqing,et al.Locationbased services:Architecture and progress [J].Chinese Journal of Computer,2011,34 (7):1156-1167 (in Chinese).[周傲英,楊彬,金澈清,等.基于位置的服務(wù):架構(gòu)與進(jìn)展 [J].計(jì)算機(jī)學(xué)報(bào),2011,34 (7):1156-1167.]
[3]GUO Ying.Research and implementation of a 3G-based LBS system architecture[J].Information Security and Technology,2011 (5):39-43 (in Chinese).[郭盈.一種3G網(wǎng)絡(luò)下的LBS架構(gòu)研究及實(shí)現(xiàn) [J].信息安全與技術(shù),2011(5):39-43.]
[4]YANG Yuyao,ZHAO Fang,LUO Haiyong,et al.A geolocation-based social network model for mobile internet[J].Journal of Computer Research and Development,2011,48 (z2):307-313(in Chinese).[楊煜堯,趙方,羅海勇,等.一種基于地理位置信息的移動(dòng)互聯(lián)網(wǎng)社交模型 [J].計(jì)算機(jī)研究與發(fā)展,2011,48 (z2):307-313.]
[5]WANG Lepeng,LI Chunli,WANG Ying.The foursquare model and explore in the development of Chinas countermeasures [J].Science & Technology Informatio,2010 (23):90-91 (in Chinese).[王樂鵬,李春麗,王穎.Foursquare模式及在中國(guó)的發(fā)展對(duì)策探討 [J].科技信息,2010 (23):90-91.]
[6]ZHANG Degan,WANG Dong.Research on service matching method for LBS[J].Computer Science,2012,39 (3):19-61(in Chinese).[張德干,王冬.面向LBS的服務(wù)匹配方法研究[J].計(jì)算機(jī)科學(xué),2012,39 (3):19-61.]
[7]YE Qian.The individual continuous path prediction based on path pattern mining [D].Hangzhou:Zhejiang University Thesis,2008(in Chinese).[葉謙,基于路徑模式挖掘的個(gè)人連續(xù)路徑預(yù)測(cè) [D].杭州:浙江大學(xué)碩士論文,2008.]
[8]HU Xiaohong,SHEN Hesong.Data query in embedded mobile database[J].Microcontrollers & Embedded Systems,2009(3):14-16 (in Chinese).[胡曉宏,沈賀嵩.嵌入式移動(dòng)數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)查詢 [J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用,2009(3):14-16.]
[9]LI Dong,YE You,XIE Fangyong.Optimization technology of query trimming in semantic caching [J].Application Research of Computers,2008,25 (12):3606-3609 (in Chinese).[李東,葉友,謝芳勇.語義緩存查詢裁剪優(yōu)化 [J].計(jì)算機(jī)應(yīng)用研究,2008,25 (12):3606-3609.]
[10]WU Yafeng,SUO Yina.The android core technologies and explain examples [M].Beijing:Publishing House of Electronics Industry,2010 (in Chinese).[吳亞峰,索依娜.Android核心技術(shù)與實(shí)例詳解 [M].北京:電子工業(yè)出版社,2010.]
[11]Reto Meier.Android advanced programming[M]Beijing:Qinghua University press,2010 (in Chinese).[Reto Meier.Android高級(jí)編程 [M].北京:清華大學(xué)出版社,2010.]
[12]GENG Xiangyi,ZHANG Yueping.JSP practical tutorial[M].Beijing:Tsinghua University Press,2007 (in Chinese). [耿祥義,張躍平.JSP實(shí)用教程 [M].北京:清華大學(xué)出版社,2007.]