一種基于偏離度的移動(dòng)導(dǎo)航服務(wù)回歸測(cè)試優(yōu)先方法

成靜, 張濤, 張景波, 王海鵬, 許勤

1．西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西西安710021; 2．西北工業(yè)大學(xué)軟件與微電子學(xué)院，陜西西安710072

移動(dòng)導(dǎo)航服務(wù)是一種基本的移動(dòng)位置服務(wù)，能夠?yàn)橛脩敉扑]兩個(gè)地理位置點(diǎn)之間的導(dǎo)航路徑。現(xiàn)代移動(dòng)導(dǎo)航服務(wù)基于移動(dòng)計(jì)算、云計(jì)算和大數(shù)據(jù)等新興技術(shù)，為用戶提供實(shí)時(shí)、智能化的移動(dòng)導(dǎo)航服務(wù)。而隨著移動(dòng)導(dǎo)航服務(wù)的日益復(fù)雜，對(duì)其測(cè)試驗(yàn)證也極為困難和復(fù)雜。面臨的主要挑戰(zhàn)與困難如下：

1)移動(dòng)導(dǎo)航服務(wù)測(cè)試工作量巨大

移動(dòng)導(dǎo)航服務(wù)是提供兩個(gè)地理位置點(diǎn)之間的路徑導(dǎo)航，其地理位置區(qū)域極其廣袤。即使在有限區(qū)域內(nèi)，也存在成百上千的導(dǎo)航位置點(diǎn)和導(dǎo)航路線。因此，如何為移動(dòng)導(dǎo)航服務(wù)生成、選擇、優(yōu)先測(cè)試數(shù)據(jù)，是移動(dòng)導(dǎo)航服務(wù)測(cè)試的難點(diǎn)。

2)移動(dòng)導(dǎo)航服務(wù)測(cè)試結(jié)果難以評(píng)估

移動(dòng)導(dǎo)航服務(wù)結(jié)果會(huì)受到眾多因素影響，例如道路堵塞、交通事故、交通管制等。即使相同的測(cè)試數(shù)據(jù)，在不同時(shí)間和場(chǎng)景下，也可能會(huì)獲得不同的導(dǎo)航結(jié)果。因此，傳統(tǒng)的“正確與否”的軟件測(cè)試結(jié)果評(píng)估方法不適用于移動(dòng)導(dǎo)航測(cè)試服務(wù)，如何評(píng)估移動(dòng)導(dǎo)航服務(wù)測(cè)試結(jié)果是其另一個(gè)難題。

3)移動(dòng)導(dǎo)航服務(wù)需要持續(xù)、敏捷的測(cè)試

移動(dòng)導(dǎo)航市場(chǎng)競(jìng)爭(zhēng)激烈，移動(dòng)導(dǎo)航服務(wù)商需要不斷完善地理基礎(chǔ)數(shù)據(jù)，更新優(yōu)化導(dǎo)航算法，以提高導(dǎo)航的準(zhǔn)確性和用戶滿意度。例如，“高德地圖”大約每7～10天發(fā)布一個(gè)新的軟件版本。因此，移動(dòng)導(dǎo)航服務(wù)需要持續(xù)化、敏捷的測(cè)試方法，以適應(yīng)其版本的快速更新。

目前，學(xué)術(shù)界開展了移動(dòng)位置服務(wù)測(cè)試的研究與探索。Gao等[1]分析了移動(dòng)位置服務(wù)測(cè)試的問題與挑戰(zhàn)。Akutif等[2]分析了移動(dòng)位置服務(wù)的功能測(cè)試需求，提出了一種基于圖模型的位置服務(wù)功能測(cè)試方法。Zhai等[3]提出了一種“興趣點(diǎn)敏感”的位置服務(wù)回歸測(cè)試用例優(yōu)先算法。Morla等[4]提出了一種混合的位置服務(wù)測(cè)試與評(píng)估環(huán)境。Nilsson[5]設(shè)計(jì)了一種位置服務(wù)測(cè)試平臺(tái)。張濤等[6]則提出了一種位置服務(wù)測(cè)試對(duì)象模型，描述了位置服務(wù)測(cè)試對(duì)象，以及其相互關(guān)系。白曉穎等[7]應(yīng)用模擬退火算法和貝葉斯分類器方法，生成位置服務(wù)的測(cè)試數(shù)據(jù)。

與上述研究不同，本文針對(duì)移動(dòng)導(dǎo)航服務(wù)測(cè)試的問題與挑戰(zhàn)，探索基于偏離度的導(dǎo)航服務(wù)回歸測(cè)試優(yōu)先方法。該方法基于假設(shè)：如果用戶實(shí)際導(dǎo)航有較多偏離推薦路徑，則導(dǎo)航服務(wù)存在故障的概率較高。方法通過分析導(dǎo)航服務(wù)日志，統(tǒng)計(jì)導(dǎo)航偏離度，優(yōu)先選擇具有較高偏離的回歸測(cè)試數(shù)據(jù)。

1 移動(dòng)導(dǎo)航服務(wù)測(cè)試模型

首先給出移動(dòng)導(dǎo)航服務(wù)測(cè)試模型的相關(guān)概念的基本定義。

定義1一個(gè)地理位置點(diǎn)Pi定義為其在地球表面的經(jīng)緯度坐標(biāo),即定義為:Pi=(li,ti)。

定義2導(dǎo)航區(qū)域D定義為包括其起點(diǎn)Pi、終點(diǎn)Pj和搜索半徑R的矩形區(qū)域,即D(Pi,Pj,R)。

定義3在導(dǎo)航區(qū)域D(Pi,Pj,R)內(nèi),對(duì)于某個(gè)位置點(diǎn)Ps,如果至少存在一條到起點(diǎn)Pi或者終點(diǎn)Pj的路線,則稱Ps是導(dǎo)航區(qū)域D(Pi,Pj,R)內(nèi)的可達(dá)位置點(diǎn)。

定義4由2個(gè)位置端點(diǎn)(Pi和Pj)確定的線段稱為路段,記為Si(Pi,Pj)。這里路段是閉合的,即單個(gè)路段中沒有其他岔路。

定義5如果某個(gè)路段Si(Pi,Pj)的2個(gè)端點(diǎn)Pi或者Pj是導(dǎo)航區(qū)域D(Pi,Pj,R)的可達(dá)位置點(diǎn),則稱該路段是導(dǎo)航區(qū)域的可達(dá)路段。

定義6如果若干個(gè)路段S1,S2,…,Sk有公共端點(diǎn)Px,則稱這些路段是交叉路段,其交叉點(diǎn)為Px,記為Px=S1∧S2∧…∧Sk。交叉點(diǎn)Px的交叉度CP(Px)定義為在該交叉點(diǎn)上相互交叉的路段數(shù)量,即CP(Px)=|{S1,S2,…,Sk}|。

如果某個(gè)端點(diǎn)不是交叉點(diǎn),則其交叉度為1。

定義7路線Li定義為由1組m個(gè)依次相連的路段組成,記為L(zhǎng)i=(S1,S2,…,Sm)。線路中所含的路段數(shù)記為NS(Li)=|{S1,S2,…,Sm}|。由于組成路線中的路段是相連的,即前一個(gè)路段的終點(diǎn)是下一個(gè)路段的起點(diǎn),所以路線Li還可以記為L(zhǎng)i=(P0,P1,P2,…,Pm,Pm+1)。這里P0是第一個(gè)路段S0的起點(diǎn),而Pm+1是最后一個(gè)路段Sm的終點(diǎn)。

定義8在導(dǎo)航區(qū)域D(Pi,Pj,R)內(nèi),若某條線路Li是以Pi為起點(diǎn),以Pj為終點(diǎn),則稱該線路為區(qū)域內(nèi)的一條可達(dá)路線。

在圖1的導(dǎo)航示意圖中,導(dǎo)航區(qū)域?yàn)閳D中虛線部分。在該區(qū)域內(nèi),包括交叉節(jié)點(diǎn)14個(gè){P1,P2,…,P14};導(dǎo)航路段20個(gè),例如路段:(P1,P5)、(P5,P6)和(P6,P7);導(dǎo)航路線25條,例如:(S,P5,P6,P7,P8,E),(S,P10,P11,P12,P13,E)。

圖1 移動(dòng)導(dǎo)航區(qū)域示意圖

2 基于偏離度的回歸測(cè)試

移動(dòng)導(dǎo)航服務(wù)的用戶數(shù)量龐大,積累了海量的用戶導(dǎo)航服務(wù)日志數(shù)據(jù)。通過對(duì)導(dǎo)航服務(wù)日志數(shù)據(jù)的挖掘分析,能夠發(fā)現(xiàn)用戶的實(shí)際運(yùn)動(dòng)軌跡與導(dǎo)航推薦路徑之間的偏離,即用戶實(shí)際路徑與推薦路徑的偏離。路徑偏離的原因眾多,例如因道路維修或交通事故等造成的導(dǎo)航路徑的不可達(dá)、用戶錯(cuò)過交叉路口等。通過對(duì)用戶路徑日志的分析,統(tǒng)計(jì)交叉路口偏離度,有助于發(fā)現(xiàn)可能存在的導(dǎo)航路徑推薦錯(cuò)誤,優(yōu)先選擇導(dǎo)航服務(wù)回歸測(cè)試數(shù)據(jù),提高移動(dòng)導(dǎo)航服務(wù)測(cè)試效率和質(zhì)量。

偏離度包括2個(gè)度量指標(biāo):偏離率和偏離次數(shù)。兩者共同描述了移動(dòng)導(dǎo)航服務(wù)出現(xiàn)路線推薦錯(cuò)誤的可能性。其中,偏離率反映了導(dǎo)航路線偏離的概率,即存在導(dǎo)航服務(wù)錯(cuò)誤的可能概率;偏離次數(shù)則反映了存在導(dǎo)航偏離的置信度。

1) 導(dǎo)航點(diǎn)偏離度

在移動(dòng)導(dǎo)航服務(wù)中,假設(shè)某次導(dǎo)航服務(wù)推薦路線為L(zhǎng)j,用戶實(shí)際通行的路線為L(zhǎng)k,2條路線在某個(gè)交叉點(diǎn)Px后偏離,則該交叉點(diǎn)Px稱為導(dǎo)航偏離點(diǎn),記作:Px=Div(Lj,Lk)。

將某個(gè)時(shí)間段T內(nèi),在某個(gè)交叉點(diǎn)Px上用戶路線偏離導(dǎo)航推薦路線的次數(shù)稱為導(dǎo)航偏離次數(shù),記作Ndp(Px)T。

在導(dǎo)航過程中,通過統(tǒng)計(jì)時(shí)間段T內(nèi)在某個(gè)交叉點(diǎn)Px的偏離次數(shù)和導(dǎo)航推薦次數(shù),即可按下列公式,計(jì)算該交叉點(diǎn)在時(shí)間T的偏離率:

(1)

式中,Nrp(Px)T是交叉點(diǎn)Px在時(shí)間段T內(nèi)被推薦的導(dǎo)航次數(shù)。

2) 導(dǎo)航路線偏離度

導(dǎo)航路線偏離度描述了在導(dǎo)航推薦路線中,存在路徑偏離的風(fēng)險(xiǎn)程度。假設(shè)導(dǎo)航推薦路線為L(zhǎng)i=(P1,P2,…,Pm)。其中,P1,P2,…,Pm是導(dǎo)航推薦路線上的交叉點(diǎn)。導(dǎo)航路線在時(shí)間段T內(nèi)的偏離次數(shù)Ndl(Li)T可由下式計(jì)算:

(2)

導(dǎo)航路線在時(shí)間段T內(nèi)的偏離率Pdl(Li)T為:

(3)

3) 導(dǎo)航區(qū)域偏離度

假設(shè)在導(dǎo)航區(qū)域D(Ps,Pe,R)范圍內(nèi),包含的交叉點(diǎn)集為{P1,P2,…Pk,…Pm},則導(dǎo)航區(qū)域的偏離次數(shù)Ndz(D)T由下式計(jì)算:

(4)

導(dǎo)航區(qū)域的偏離率Pdz(D)T由下式計(jì)算:

(5)

上述導(dǎo)航偏離度指標(biāo)可以用于評(píng)估移動(dòng)導(dǎo)航測(cè)試數(shù)據(jù)發(fā)現(xiàn)導(dǎo)航服務(wù)錯(cuò)誤的概率。通常,偏離度越高,則測(cè)試數(shù)據(jù)發(fā)現(xiàn)故障的幾率越高。

3 實(shí)驗(yàn)驗(yàn)證

本節(jié)將以一個(gè)測(cè)試實(shí)例,驗(yàn)證所提出的基于偏離度的移動(dòng)導(dǎo)航服務(wù)回歸測(cè)試方法的有效性,判斷該方法是否有助于提高移動(dòng)導(dǎo)航服務(wù)回歸測(cè)試效率和測(cè)試質(zhì)量,以及所提出的偏離度度量指標(biāo),是否具有相同的效果,或者哪個(gè)指標(biāo)效果更優(yōu)。

1) 實(shí)驗(yàn)方法與過程

在實(shí)驗(yàn)中,通過與某地圖導(dǎo)航公司合作,由其提供該公司在西安市區(qū)的導(dǎo)航測(cè)試數(shù)據(jù)集,以及在西安市區(qū)1個(gè)月的汽車導(dǎo)航服務(wù)數(shù)據(jù)集。導(dǎo)航測(cè)試數(shù)據(jù)集共計(jì)包含2 000條測(cè)試數(shù)據(jù),在其中248條測(cè)試數(shù)據(jù)中,總共發(fā)現(xiàn)缺陷56項(xiàng)。導(dǎo)航服務(wù)數(shù)據(jù)集包括:用戶導(dǎo)航服務(wù)請(qǐng)求數(shù)據(jù),導(dǎo)航推薦路徑數(shù)據(jù),用戶實(shí)際行駛數(shù)據(jù),西安市區(qū)地圖數(shù)據(jù)等,上述導(dǎo)航服務(wù)數(shù)據(jù)集共計(jì)約150萬(wàn)條。

在導(dǎo)航服務(wù)數(shù)據(jù)集中,首先根據(jù)用戶標(biāo)識(shí)對(duì)導(dǎo)航推薦路徑數(shù)據(jù)與用戶實(shí)際行駛數(shù)據(jù)進(jìn)行匹配,僅保留能與之匹配的導(dǎo)航服務(wù)數(shù)據(jù)。然后,比較導(dǎo)航推薦路徑與用戶實(shí)際路徑,確定偏離點(diǎn),并統(tǒng)計(jì)各個(gè)偏離點(diǎn)的導(dǎo)航次數(shù)、偏離次數(shù)和偏離度。偏離度是基于對(duì)歷史導(dǎo)航數(shù)據(jù)統(tǒng)計(jì)得到,準(zhǔn)確性依賴于大量統(tǒng)計(jì)數(shù)據(jù)集。因此,在實(shí)驗(yàn)中需要首先清除偏離次數(shù)小而偏離率高的數(shù)據(jù)。

城市道路情況更為復(fù)雜,本次實(shí)驗(yàn)中,選擇測(cè)試城市市區(qū)內(nèi)的導(dǎo)航服務(wù)情況。由于城市道路密集,通過分析所提供的測(cè)試數(shù)據(jù)的推薦路徑范圍,設(shè)定搜索半徑R為2.5公里,計(jì)算測(cè)試數(shù)據(jù)的復(fù)雜性。

然后,分別根據(jù)導(dǎo)航線路偏離度、導(dǎo)航區(qū)域偏離度生成兩個(gè)測(cè)試數(shù)據(jù)優(yōu)先隊(duì)列,計(jì)算所生成優(yōu)先隊(duì)列的測(cè)試效率,并與隨機(jī)測(cè)試數(shù)據(jù)隊(duì)列的測(cè)試效率進(jìn)行對(duì)比分析研究。為了分析測(cè)試數(shù)據(jù)集規(guī)模對(duì)測(cè)試結(jié)果的影響,實(shí)驗(yàn)中測(cè)試數(shù)據(jù)集的大小分別設(shè)定為:128,256,512,1 024。并且對(duì)不同大小的數(shù)據(jù)集,分別采樣和重復(fù)實(shí)驗(yàn)10次。

2) 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

常用的測(cè)試數(shù)據(jù)優(yōu)先評(píng)價(jià)指標(biāo),主要包括:故障發(fā)現(xiàn)調(diào)和均值(harmonic mean of fault detection,Hmfd)和平均故障發(fā)現(xiàn)率(average percentage of fault detection,Apfd)。

Hmfd是一種與測(cè)試數(shù)據(jù)集大小無關(guān)的度量指標(biāo)。這里,假設(shè)T是一組測(cè)試數(shù)據(jù)集,包含n個(gè)測(cè)試數(shù)據(jù)。F是由測(cè)試數(shù)據(jù)集T所發(fā)現(xiàn)的故障集,故障數(shù)量為m。Tfi是測(cè)試數(shù)據(jù)集T中第一個(gè)發(fā)現(xiàn)故障i的測(cè)試數(shù)據(jù)的序號(hào)。于是,Hmfd的計(jì)算公式為:

(6)

Hmfd可以用于評(píng)估測(cè)試數(shù)據(jù)優(yōu)先方法的有效性,其值越低,則測(cè)試數(shù)據(jù)集發(fā)現(xiàn)故障的效率越高。Hmfd同樣可以用于評(píng)估方法的有效性。

Apfd是一種基于算術(shù)平均值統(tǒng)計(jì)測(cè)試數(shù)據(jù)集的故障發(fā)現(xiàn)效率。Apfd的計(jì)算公式如下:

(7)

顯然,平均故障發(fā)現(xiàn)率Apfd受測(cè)試數(shù)據(jù)集大小和其所包含故障數(shù)的影響。并且其值越大,則表示測(cè)試數(shù)據(jù)發(fā)現(xiàn)故障效率越高。

例如,假設(shè)有一組測(cè)試數(shù)據(jù)集,共包含10個(gè)測(cè)試,總共發(fā)現(xiàn)了3個(gè)故障,并且這3個(gè)故障分別是在前3個(gè)測(cè)試數(shù)據(jù)中被發(fā)現(xiàn)。則其Hmfd和Apfd分別計(jì)算如下:

(8)

(9)

在實(shí)驗(yàn)中,將分別采用Hmfd和Apfd,評(píng)估所提出優(yōu)先方法的有效性。并對(duì)比在不同規(guī)模的測(cè)試數(shù)據(jù)集下,所提出優(yōu)先選擇方法的故障發(fā)現(xiàn)效率。

3) 實(shí)驗(yàn)結(jié)果分析

在隨機(jī)生成128、256、512、1 024規(guī)模的測(cè)試數(shù)據(jù)集下,分別按照最短路線偏離次數(shù)、最短路線偏離率、導(dǎo)航區(qū)域偏離次數(shù)、導(dǎo)航區(qū)域偏離率進(jìn)行排序。再分別計(jì)算其優(yōu)先排序后,測(cè)試數(shù)據(jù)隊(duì)列的故障發(fā)現(xiàn)調(diào)和均值Hmfd和平均故障發(fā)現(xiàn)率Apfd。并與隨機(jī)排序方法實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析。

表1則對(duì)比了不同數(shù)據(jù)集下的故障發(fā)現(xiàn)調(diào)和均值Hmfd。表2則對(duì)比了不同數(shù)據(jù)集下的平均故障發(fā)現(xiàn)率Apfd。圖2和圖3分別顯示了在不同大小測(cè)試數(shù)據(jù)集下,基于偏離度優(yōu)先指標(biāo)的故障發(fā)現(xiàn)調(diào)和均值Hmfd和平均故障發(fā)現(xiàn)率Apfd的變化情況。

表1 故障發(fā)現(xiàn)調(diào)和均值Hmfd表

表2 平均故障發(fā)現(xiàn)率Apfd表

圖2 基于偏離度優(yōu)先的Hmfd圖

圖3 基于偏離度優(yōu)先的Apfd圖

實(shí)驗(yàn)結(jié)果表明，根據(jù)所提出的基于偏離度的優(yōu)先指標(biāo)排序的測(cè)試數(shù)據(jù)集，其故障發(fā)現(xiàn)調(diào)和均值Hmfd和平均故障發(fā)現(xiàn)率Apfd均明顯優(yōu)于隨機(jī)算法生成的測(cè)試數(shù)據(jù)集，說明上述優(yōu)先指標(biāo)均是有效的。基于路線偏離度優(yōu)先的實(shí)驗(yàn)結(jié)果與基于導(dǎo)航區(qū)域偏離度優(yōu)先的實(shí)驗(yàn)結(jié)果相近，表明這2種優(yōu)化指標(biāo)相近。由于在實(shí)驗(yàn)中，已經(jīng)過濾了低支撐度的偏離數(shù)據(jù)，基于偏離次數(shù)和偏離率優(yōu)化，其效果相近。

4 結(jié) 論

由于現(xiàn)代移動(dòng)導(dǎo)航服務(wù)的智能化、個(gè)性化、開放性、實(shí)時(shí)性等特征，使得其測(cè)試驗(yàn)證尤為困難。本文探索基于偏離度的移動(dòng)導(dǎo)航服務(wù)回歸測(cè)試方法，通過對(duì)導(dǎo)航日志數(shù)據(jù)的統(tǒng)計(jì)，分析導(dǎo)航區(qū)域、交叉點(diǎn)的偏離度，然后基于偏離度優(yōu)先選擇測(cè)試數(shù)據(jù)，提高回歸測(cè)試效率，更早發(fā)現(xiàn)軟件故障。下一步，將研究如何從海量導(dǎo)航日志數(shù)據(jù)中，自動(dòng)分析識(shí)別真實(shí)導(dǎo)航偏離和虛假導(dǎo)航偏離。

[1] Gao Jerry, Bai X, Tsai W T, et al. Mobile Application Testing: A Tutorial[J]. IEEE Computer, 2014, 47(2): 26-35

[2] Aktouf O E, Zhang Tao, Ga Jerry, Tadahiro Uehara. Testing Location-Based Function Services for Mobile Applications[C]∥Proc of the IEEE Symposium on Sewsces-Orented System Engineering, 2015: 564-572

[3] Zhai Ke, Jiang Bo, Chan W K. Prioritizing Test Cases for Regression Testing of Location-Based Services: Metrics, Techniques, and Case Study[J]. IEEE Trans on Services Computing, 2014, 7(1): 54-67

[4] Morla R, Davies N. Evaluating a Location-Based Application: a Hybrid Test and Simulation Environment[J]. IEEE Pervasive Computing, 2004, 3(3): 48-56

[5] Nilsson J. A Platform for Testing and Evaluating Location Based Services[D]. Lule?, Sweden Lule? University of

Technology, 2005

[6] Zhang Tao, Gao Jerry, et al. Test Model and Coverage Analysis for Location Based Mobile Services[C]∥Proc of the 27th International Conference on Software Engineering and Knowledge Engineering, 2015: 348-356

[7] 侯可佳, 黃軍, 白曉穎, 等. 一種位置服務(wù)測(cè)試數(shù)據(jù)生成技術(shù)研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2016,39(11):1-15

Hou Kejia, Huang Jun, Bai Xiaoying, et al. Geographical Data Generation for Testing Location-Based Services[J].Chinese Journal of Computers,2016,39(11):1-15 (in Chinese)