劉天悅,楊麗娜,池天河,彭 玲

(1.中國(guó)科學(xué)院遙感與數(shù)字地球研究所,北京100101;2.中國(guó)科學(xué)院大學(xué),北京100049)

一種適合于室內(nèi)疏散對(duì)象的混合位置更新策略

劉天悅1,2,楊麗娜1,池天河1,彭 玲1

(1.中國(guó)科學(xué)院遙感與數(shù)字地球研究所,北京100101;2.中國(guó)科學(xué)院大學(xué),北京100049)

當(dāng)建筑物內(nèi)發(fā)生突發(fā)事件時(shí),為更好地跟蹤疏散對(duì)象,減少位置更新頻率,提出一種基于疏散對(duì)象速度、方向?qū)傩院褪覂?nèi)地標(biāo)單元拓?fù)?、語(yǔ)義結(jié)構(gòu)相結(jié)合的混合位置更新策略。當(dāng)疏散對(duì)象速度范圍和地標(biāo)單元兩者中有一項(xiàng)發(fā)生變化,并滿足鄰接單元關(guān)系時(shí)將位置更新到服務(wù)端,既保證對(duì)象在擁堵處或地標(biāo)單元處更新,又避免由于室內(nèi)定位不確定性產(chǎn)生的少數(shù)錯(cuò)誤更新。實(shí)驗(yàn)結(jié)果表明,與已有的基于固定時(shí)間或安全區(qū)域的更新策略相比,該策略能夠在保證疏散對(duì)象位置精確度的情況下,以較小的通信代價(jià)持續(xù)跟蹤疏散對(duì)象的詳細(xì)位置信息和擁擠狀態(tài)。

疏散對(duì)象;位置更新;室內(nèi)空間;地標(biāo)單元;速度范圍;服務(wù)端

1 概述

隨著基于位置服務(wù)(Location-based Service, LBS)相關(guān)的行業(yè)應(yīng)用逐漸走向?qū)嵱没?LBS將在緊急救援、安全監(jiān)控、安全調(diào)度和地圖導(dǎo)航等諸多方面發(fā)揮更重要的作用。在緊急情況下,LBS系統(tǒng)被用于定位求助者的位置,便于快速實(shí)施救援,比如美國(guó)的E911系統(tǒng)和歐洲的E112系統(tǒng)［1］。隨著LBS應(yīng)用需求的發(fā)展,需要在電子地圖中同時(shí)跟蹤多個(gè)目標(biāo)對(duì)象,通過(guò)查詢處理引擎訪問(wèn)移動(dòng)對(duì)象數(shù)據(jù)庫(kù)［2］。隨著不斷增加的位置大數(shù)據(jù),研究如何減少位置更新代價(jià)已成為L(zhǎng)BS系統(tǒng)位置管理的一個(gè)熱點(diǎn)問(wèn)題。針對(duì)建筑物內(nèi)突發(fā)事件,一個(gè)有效的位置更新策略是通過(guò)選擇合適的更新方式,降低移動(dòng)對(duì)象位置的不確定性、不精確性與系統(tǒng)資源的占用率,并保證查詢結(jié)果具有一定的準(zhǔn)確性［3］。在室內(nèi)定位系統(tǒng)的支持下,移動(dòng)端將疏散對(duì)象當(dāng)前位置和速度等信息不斷地傳送到該服務(wù)端數(shù)據(jù)庫(kù)中,目的是為了便于查

詢得到最新的信息。然而,頻繁的更新會(huì)大量增加服務(wù)器負(fù)載,因此,位置精確性和服務(wù)器通信代價(jià)之間顯然存在一種折中關(guān)系［4］。

針對(duì)移動(dòng)對(duì)象的位置更新問(wèn)題,一些學(xué)者已提出多種解決方法。其中,基于時(shí)間和距離更新移動(dòng)對(duì)象信息是2種最常見(jiàn)的方法?；跁r(shí)間的更新,比如基于固定時(shí)間的更新;時(shí)間更新還有基于查詢結(jié)果更新,它是一種自適應(yīng)的更新方法,基于對(duì)象的運(yùn)動(dòng)預(yù)測(cè)其更新的時(shí)間閾值［5］;基于距離的更新,如概略化軌跡更新,它是一種基于網(wǎng)絡(luò)受限移動(dòng)對(duì)象的動(dòng)態(tài)概略化軌跡,將索引空間劃分成等距格柵,僅需要在軌跡跨越當(dāng)前格柵單元時(shí)才進(jìn)行索引更新［6］;距離更新還有一種基于查詢目標(biāo)的安全區(qū)域的方法,在安全區(qū)域內(nèi),若查詢目標(biāo)沒(méi)有發(fā)生改變不需要更新［7］。

除此之外,文獻(xiàn)［8］在航行信息更新中采用向量的更新方法;文獻(xiàn)［9-10］也分別提出了根據(jù)移動(dòng)對(duì)象所在路網(wǎng)的幾何形狀或者邊界拓?fù)潢P(guān)聯(lián)實(shí)現(xiàn)狀態(tài)更新。但這些更新策略大都局限于室外空間或路網(wǎng),很少有結(jié)合室內(nèi)空間語(yǔ)義、拓?fù)浣Y(jié)構(gòu)進(jìn)行設(shè)計(jì),也沒(méi)有結(jié)合突發(fā)事件時(shí)疏散對(duì)象的速度范圍進(jìn)行劃分,很難反映室內(nèi)擁堵?tīng)顟B(tài)。

本文從室內(nèi)應(yīng)急角度出發(fā),采用疏散對(duì)象移動(dòng)速度范圍和室內(nèi)地標(biāo)單元相結(jié)合的混合位置更新策略,在保證位置查詢精確度的基礎(chǔ)上,降低服務(wù)端更新代價(jià)。

2 室內(nèi)地標(biāo)單元

室內(nèi)空間位置不需要像室外那樣采用精確的坐標(biāo)位置(x,y),室內(nèi)樓層空間有單元的概念,可劃分為房間單元(或功能分區(qū)等)和走廊單元(前室、大廳等)2類(lèi)單元結(jié)構(gòu)。現(xiàn)實(shí)中尺度較大的房間很可能被劃分成多個(gè)尺度較小的房間或者分區(qū),如果單獨(dú)使用單元表達(dá)對(duì)象在室內(nèi)空間的位置仍不夠準(zhǔn)確。室內(nèi)地標(biāo)能夠用來(lái)進(jìn)一步描述室內(nèi)單元空間,因此,本文提出利用室內(nèi)地標(biāo)和室內(nèi)單元之間的拓?fù)潢P(guān)系共同構(gòu)建更加微觀的室內(nèi)地標(biāo)單元二維結(jié)構(gòu)(單元,地標(biāo)),它是在室內(nèi)單元基礎(chǔ)上,包含房門(mén)(東門(mén)、南門(mén)等)、出口標(biāo)志或感興趣點(diǎn)等更為準(zhǔn)確的特征信息。在室內(nèi)空間,可通過(guò)其實(shí)際輪廓線(墻體)確定唯一房間單元,尺度大的房間可以借助多個(gè)房門(mén)或者感興趣點(diǎn)劃分;走廊空間狹長(zhǎng)并且連通,可以根據(jù)走廊內(nèi)各種地標(biāo)對(duì)疏散對(duì)象的實(shí)際影響范圍分割來(lái)表達(dá)對(duì)象的詳細(xì)位置。

定義1室內(nèi)空間S由多個(gè)室內(nèi)地標(biāo)單元(Ci,Mj)(i,j=1,2,…,n)構(gòu)成,即S={(C1,M1),(C2,M2),…,(Cm,Cn)},m∈i,n∈j。其中,Ci表示房間或走廊單元;Mj表示房門(mén)、疏散標(biāo)志等室內(nèi)地標(biāo)。在Ti時(shí)刻,疏散對(duì)象Oi的室內(nèi)位置表示為一個(gè)室內(nèi)地標(biāo)單元,即Loc(Oi,Ti)(Ci,Mi)。

定義2 假設(shè)P={O1,O2,…,On}為室內(nèi)空間的一組移動(dòng)對(duì)象,EDist(Oi,Oj)和RDist(Oi,Oj)分別表示Oi與Oj之間的歐幾里得距離(如圖1的①所示)和實(shí)際距離(如圖1的②所示);CDist(Oi,Oj)表示從Oi到Oj所經(jīng)過(guò)的室內(nèi)單元個(gè)數(shù),即CDist(Oi,Oj)={C1,C2,…,Cn}-1,其中,Oi在C1,Oj在Cn,且C1∝C2∝Cx∝Cn。

定義3 在室內(nèi)空間,假設(shè)對(duì)象O2是對(duì)象O1最近的對(duì)象,則CDist(O1,O2)＜CDist(O1,Oj),J≠2。

圖1表示室內(nèi)地標(biāo)單元空間,假設(shè)有3個(gè)對(duì)象O1,O2和O3,在T1時(shí)刻,對(duì)象O1,O2在C2單元,O3在C6單元。距O2最近的地標(biāo)是房門(mén)M1,故Loc(O2,T1)=(C2,M1)。O2與O3間的歐氏距離比與O2距O1的要短,即EDist(O2,O3)＜EDist(O2,O1)。但O2距O3的實(shí)際距離比O2距O1的要長(zhǎng),即RDist(O2,O3)＞RDist(O2,O1)。因此,歐式距離在室內(nèi)實(shí)際距離不再適用。

圖1 室內(nèi)地標(biāo)單元空間

圖1的鄰接單元矩陣如圖2所示。CDist(O2,O3)= |sum{C2,C1,C4,C6}-1|=3,CDist(O2,O1)=|sum {C2}-1|=0,由于CDist(O2,O3)＞CDist(O2,O1),適用鄰接單元距離,距O2最近的對(duì)象是O1不是O3,因此采用鄰接單元距離CDist(Oi,Oj)能夠近似表達(dá)疏散對(duì)象間的實(shí)際距離。

圖2 鄰接單元矩陣

由于室內(nèi)定位具有偏差和不確定性,比如說(shuō)疏散對(duì)象實(shí)際在走廊上行走,當(dāng)前任何定位方式都有可能錯(cuò)誤地將其定位到相鄰的房間內(nèi),而通過(guò)室內(nèi)地標(biāo)單元的鄰接單元矩陣可減少由于位置不確定性造成的錯(cuò)誤更新。因此,構(gòu)建以室內(nèi)地標(biāo)單元為基礎(chǔ)的室內(nèi)空間信息不僅能給人以各種復(fù)雜環(huán)境的直觀展示,同時(shí)也作為疏散對(duì)象位置更新的過(guò)濾條件。

3 位置更新策略

室內(nèi)疏散對(duì)象需要更新的數(shù)據(jù)包括室內(nèi)定位技術(shù)計(jì)算的位置數(shù)據(jù)和慣性測(cè)量單元測(cè)得的速度、方向數(shù)據(jù)。本文提出一種新型的基于速度范圍和室內(nèi)地標(biāo)單元的混合位置更新策略,它是當(dāng)移動(dòng)對(duì)象速度范圍發(fā)生變化或者地標(biāo)單元變化后,并滿足單元鄰接關(guān)系后才向服務(wù)端進(jìn)行位置更新,這樣可以舍去大量不必要的位置數(shù)據(jù)和少數(shù)漂移位置數(shù)據(jù)。

3.1 速度范圍規(guī)則

速度范圍規(guī)則(以下簡(jiǎn)稱(chēng)速度規(guī)則)指移動(dòng)端判斷疏散對(duì)象當(dāng)前所在速度范圍是否發(fā)生變化。當(dāng)對(duì)象進(jìn)入某個(gè)速度范圍時(shí)進(jìn)行一次更新,直到離開(kāi)這個(gè)速度范圍才進(jìn)行下一次更新。滿足該規(guī)則,則直接進(jìn)入鄰接單元規(guī)則判斷,否則,跳過(guò)當(dāng)前位置進(jìn)行室內(nèi)地標(biāo)規(guī)則判斷。通過(guò)速度范圍變化引起的位置更新,能夠?qū)崟r(shí)監(jiān)控室內(nèi)單元的擁堵?tīng)顟B(tài)。根據(jù)文獻(xiàn)［11］的研究,定義了疏散對(duì)象4個(gè)速度范圍及擁擠狀態(tài),如表1所示。

表1 疏散對(duì)象速度范圍及擁擠狀態(tài)

3.2 室內(nèi)地標(biāo)規(guī)則

室內(nèi)地標(biāo)規(guī)則(以下簡(jiǎn)稱(chēng)地標(biāo)規(guī)則)是指移動(dòng)端獲取的疏散對(duì)象方向?qū)傩耘c所在室內(nèi)地標(biāo)單元的語(yǔ)義或拓?fù)潢P(guān)系相比較。每當(dāng)疏散對(duì)象經(jīng)過(guò)室內(nèi)地標(biāo)處,定位終端判斷其是否滿足地標(biāo)規(guī)則,若滿足,則進(jìn)入鄰接單元規(guī)則階段判斷;否則,跳過(guò)當(dāng)前時(shí)刻位置進(jìn)行下一位置判斷。隨著時(shí)間推移,前一個(gè)地標(biāo)可能會(huì)不準(zhǔn)確,但隨著終端碰到下一個(gè)地標(biāo),從而不斷糾正它的位置。該規(guī)則的算法流程如圖3所示。以每一個(gè)對(duì)象當(dāng)前位置做圓心,半徑為r的圓形緩沖區(qū)作為對(duì)象的位置不確定區(qū)域,緩沖區(qū)半徑r由室內(nèi)水平定位精度決定。首先,查詢緩沖區(qū)內(nèi)所有相交單元個(gè)數(shù)ncell,若ncell=0,則舍棄該點(diǎn);若ncell= 1,直接進(jìn)入鄰接單元規(guī)則階段;若ncell＞1,則判斷緩沖區(qū)內(nèi)有哪些地標(biāo)(nmark表示所有地標(biāo)點(diǎn)的個(gè)數(shù))與之相交,然后進(jìn)入地標(biāo)規(guī)則進(jìn)行過(guò)濾。地標(biāo)規(guī)則包括2種,一種是地標(biāo)拓?fù)湟?guī)則,另一種是地標(biāo)方向規(guī)則。

圖3 室內(nèi)地標(biāo)規(guī)則算法流程

3.2.1 地標(biāo)拓?fù)湟?guī)則

室內(nèi)地標(biāo)單元具有拓?fù)溧徑雍屯負(fù)浒瑢傩?比如說(shuō)房間單元和門(mén)地標(biāo)是拓?fù)溧徑雨P(guān)系;走廊單元和走廊地標(biāo)之間存在拓?fù)浒P(guān)系。如果更新地標(biāo)與對(duì)象所在當(dāng)前單元存在拓?fù)溧徑踊蛲負(fù)浒P(guān)系,則滿足地標(biāo)拓?fù)湟?guī)則,然后進(jìn)入地標(biāo)方向規(guī)則進(jìn)行判斷。反之,進(jìn)行緩沖區(qū)內(nèi)下一個(gè)地標(biāo)的判斷。

3.2.2 地標(biāo)方向規(guī)則

地標(biāo)方向以方向字段作為疏散對(duì)象位置更新的過(guò)濾規(guī)則。比如房門(mén)地標(biāo)方向主要用于判斷對(duì)象是否從房間進(jìn)入走廊;走廊地標(biāo)的方向用于判斷對(duì)象是否在走廊單元內(nèi)行走。若疏散對(duì)象的方向與滿足地標(biāo)拓?fù)湟?guī)則后的地標(biāo)方向相差在X度內(nèi)(X由電子羅盤(pán)的誤差水平?jīng)Q定),則滿足規(guī)則2進(jìn)入下一個(gè)鄰接單元規(guī)則階段。

3.3 鄰接單元規(guī)則

考慮疏散對(duì)象位置具有不確定性,無(wú)論網(wǎng)絡(luò)、硬

件或相關(guān)定位算法如何改進(jìn)或優(yōu)化,定位精度總存在不同程度的偏差,極少數(shù)點(diǎn)可能定位到錯(cuò)誤的室內(nèi)單元甚至到樓宇之外。因此,需要第3個(gè)規(guī)則——鄰接單元規(guī)則(以下簡(jiǎn)稱(chēng)單元規(guī)則)對(duì)疏散對(duì)象位置做進(jìn)一步的過(guò)濾。它指當(dāng)對(duì)象進(jìn)入某個(gè)地標(biāo)單元(單元,地標(biāo))時(shí)進(jìn)行一次更新,直到離開(kāi)這個(gè)地標(biāo)單元或者經(jīng)過(guò)新的地標(biāo)單元處時(shí)并滿足鄰接單元拓?fù)潢P(guān)系時(shí)才進(jìn)行下一次更新。突發(fā)事件發(fā)生時(shí),房門(mén)和走廊出口是比較容易產(chǎn)生擁堵的地方,也更容易發(fā)生漂移現(xiàn)象。因此,采用鄰接單元矩陣進(jìn)行約束和過(guò)濾,保證更新后的房間單元或者走廊單元是正確的,該規(guī)則的算法流程如圖4所示。

圖4 鄰接單元規(guī)則算法流程

(1)當(dāng)鄰接單元距離CDist(Clast,Ccurrent)＞1時(shí):滿足地標(biāo)規(guī)則的當(dāng)前單元Ccurrent與服務(wù)端前一個(gè)單元Clast不相鄰接,則舍棄當(dāng)前位置;

(2)當(dāng)鄰接單元距離CDist(Clast,Ccurrent)=0時(shí):滿足地標(biāo)規(guī)則的當(dāng)前單元Ccurrent與服務(wù)端前一個(gè)單元Clast相同,并且當(dāng)前地標(biāo)Mcurrent和前一個(gè)地標(biāo)Mlast相同則不更新,反之,更新當(dāng)前位置;

(3)當(dāng)鄰接單元距離CDist(Clast,Ccurrent)=1時(shí):滿足地標(biāo)規(guī)則的當(dāng)前單元Ccurrent與服務(wù)端前一個(gè)單元Clast相鄰接,則更新當(dāng)前位置。

3.4 實(shí)例說(shuō)明

定義4 混合位置更新策略(H)由速度規(guī)則(V)、地標(biāo)規(guī)則(M)和單元規(guī)則(C)共同組成,即:

H=(V∩M)∪C

當(dāng)H值為true時(shí),則更新;反之,則不更新。假設(shè)對(duì)象O1有8條位置記錄,如圖5所示,其中Vi(i=0～7)表示疏散對(duì)象速度,i表示時(shí)刻?；旌衔恢貌呗缘母虏襟E如下:

(1)T0時(shí)刻:對(duì)象O1開(kāi)始移動(dòng),對(duì)象初始位置均更新,故更新位置為O1(C2,null,T0);

(2)T1時(shí)刻:對(duì)象O1雖不滿足速度規(guī)則,但滿足地標(biāo)規(guī)則和單元規(guī)則,故更新位置為O1(C2,M1,T1);

(3)T2時(shí)刻:對(duì)象O1不滿足速度規(guī)則和地標(biāo)規(guī)則任何一個(gè),故不需要再判斷單元規(guī)則,不更新;

(4)T3時(shí)刻:對(duì)象O1滿足速度規(guī)則(速度范圍發(fā)生變化)和單元規(guī)則,故更新位置為O1(C2,M2,T3);

(5)T4～T6時(shí)刻:對(duì)象O1不滿足速度規(guī)則和地標(biāo)規(guī)則兩者之一,故不更新;

(6)T7時(shí)刻:對(duì)象O1滿足速度規(guī)則(速度范圍發(fā)生變化)和單元規(guī)則,故更新位置為O1(C2,M2,T7)。

圖5 混合位置更新策略舉例

表2所示是混合更新策略與其他幾種更新策略的更新過(guò)程比較。混合更新策略在速度發(fā)生顯著變化或者進(jìn)入新的地標(biāo)單元時(shí)才更新(更新4次);固定時(shí)間(1 s)策略每1秒中更新一次,服務(wù)端負(fù)載大(更新8次);固定時(shí)間(3 s)每3秒中更新一次,服務(wù)端負(fù)載減少(更新3次),但是無(wú)法反映速度變化及地標(biāo)單元的變化;安全距離策略雖反映單元變化,且服務(wù)端負(fù)載小(更新2次)但是沒(méi)有反映經(jīng)過(guò)的地標(biāo)及擁堵信息。

表2 更新策略的更新過(guò)程

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

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境是一臺(tái)PC機(jī),它的配置是英特爾酷睿i5-2450m處理器,2.5 GHz的主頻和4 GB內(nèi)存。程序基于Java語(yǔ)言實(shí)現(xiàn),終端數(shù)據(jù)庫(kù)選用Spatiallite。實(shí)驗(yàn)數(shù)據(jù)有模擬分析數(shù)據(jù),也有終端設(shè)備在現(xiàn)場(chǎng)采集的真實(shí)定位數(shù)據(jù)。實(shí)驗(yàn)場(chǎng)地是中國(guó)天津的一家會(huì)議酒店,選擇該酒店的主要原因有2個(gè):(1)該樓宇位于基站的覆蓋范圍內(nèi),移動(dòng)通信基站信號(hào)較好,室內(nèi)定位精度高;(2)該樓宇有詳細(xì)的建筑藍(lán)圖供參考,圖6是樓宇第4樓層建筑平面圖,作為主要實(shí)驗(yàn)區(qū)。

圖6 試驗(yàn)樓層室內(nèi)地標(biāo)單元

假設(shè)試驗(yàn)樓層所有地標(biāo)的權(quán)重一致,即不同地標(biāo)的影響范圍是一樣的。圖6的Ci為室內(nèi)地標(biāo)單元的表示符號(hào)。選擇文獻(xiàn)［12］提出的室內(nèi)軌跡增量索引(Indoor Trajectories Deltas,ITD)和移動(dòng)對(duì)象時(shí)間戳索引(Moving Objects Timestamping,MOT)包含的更新策略進(jìn)行比較。選擇這2種策略的原因是它們分別代表了2種典型的更新機(jī)制,ITD通過(guò)固定時(shí)間的閾值更新,MOT基于安全區(qū)域的距離更新。

18人開(kāi)始真實(shí)模擬小范圍的疏散情景,每人攜帶一臺(tái)終端,分2組,每組9人。按照預(yù)先計(jì)劃的移動(dòng)路線①和路線②進(jìn)行,如圖7所示。2組人分別從單元號(hào)為C15和C14的2個(gè)會(huì)議室同時(shí)開(kāi)始移動(dòng),終點(diǎn)都是C1樓梯間。為了能更好地模擬突發(fā)事件發(fā)生時(shí)可能產(chǎn)生的室內(nèi)擁堵現(xiàn)象,假設(shè)M15,M14和M33個(gè)地標(biāo)任一時(shí)刻都只能允許一個(gè)人通過(guò)。具體參數(shù)和數(shù)值如表3所示。

圖7 實(shí)際疏散路線

表3 參數(shù)和對(duì)應(yīng)數(shù)值

4.2 結(jié)果分析

本研究采用單元置信度和位置更新頻次評(píng)價(jià)混合策略和其他策略。

(1)單元置信度:表示移動(dòng)對(duì)象的真實(shí)單元和計(jì)算單元保持一致的概率,用ICF表示。C(T)和C′(T)分別表示移動(dòng)對(duì)象在同一時(shí)刻T的真實(shí)單元和計(jì)算單元。計(jì)算公式如下:

(2)位置更新頻次:表示隨時(shí)間推移移動(dòng)對(duì)象的位置更新次數(shù),它也代表對(duì)象位置更新的通信及計(jì)算代價(jià)。

從圖8中可以看出,固定時(shí)間(1 s)的單元置信度最高,混合策略和固定時(shí)間(3 s)次之,安全區(qū)域策略最差。固定時(shí)間(1 s)比混合策略提供了最準(zhǔn)確的位置,但也具有最高的信息成本。盡管混合策略的置信度不是最高,比固定時(shí)間(1 s)略低,但是高于其他更新策略,主要原因有2個(gè):(1)混合策略通過(guò)室內(nèi)地標(biāo)單元拓?fù)浣Y(jié)構(gòu)舍去了錯(cuò)誤的位置更新;(2)混合策略采用走廊單元內(nèi)的地標(biāo)作為觸發(fā)更新的條件,地標(biāo)大多在走廊單元的中心處,不容易產(chǎn)生單元偏離;而固定時(shí)間策略的更新時(shí)間不確定;安全區(qū)域策略則是剛進(jìn)入單元后更新,很容易產(chǎn)生單元偏離。

圖8 單元置信度

圖9是實(shí)際疏散后的人員定位軌跡與室內(nèi)地標(biāo)單元疊加后的結(jié)果,2條路線①和路線②共生成455個(gè)軌跡點(diǎn),采用固定時(shí)間(1 s)策略更新,即所有定位點(diǎn)均更新到服務(wù)器中,需更新455次;采用固定時(shí)間(3 s)策略更新,需更新157次;采用安全區(qū)域策略更新,需更新105次;采用混合策略更新,需更新118次,見(jiàn)表4。

圖9 實(shí)際疏散定位軌跡

表4 更新前后通信代價(jià)對(duì)比

對(duì)于運(yùn)動(dòng)速度變化快的移動(dòng)對(duì)象來(lái)說(shuō),固定時(shí)間策略無(wú)法及時(shí)反映移動(dòng)對(duì)象運(yùn)動(dòng)速度的變化及其位置的變化,將導(dǎo)致服務(wù)端產(chǎn)生嚴(yán)重的誤差。如果設(shè)置太小,如固定時(shí)間(1 s)策略則會(huì)產(chǎn)生過(guò)多的位置更新次數(shù),給服務(wù)端帶來(lái)較大的更新負(fù)擔(dān)［13］,如果設(shè)置太大則無(wú)法保證服務(wù)端移動(dòng)對(duì)象位置信息存儲(chǔ)的精確度,如固定時(shí)間(3 s);安全區(qū)域策略的更新次數(shù)雖然比固定時(shí)間策略少,但是沒(méi)有考慮移動(dòng)對(duì)象本身速度等屬性,并且無(wú)法查詢什么時(shí)間、什么單元處于擁堵?tīng)顟B(tài)?？傊?混合策略的更新次數(shù)明顯減少,實(shí)現(xiàn)成本的顯著降低。另外,混合策略的各種規(guī)則耗費(fèi)的時(shí)間都在毫秒級(jí)別,遠(yuǎn)低于位置更新1次的時(shí)間。因此,耗費(fèi)時(shí)間可忽略不計(jì)。

5 結(jié)束語(yǔ)

國(guó)內(nèi)外移動(dòng)對(duì)象數(shù)據(jù)庫(kù)方面的研究已經(jīng)趨于成熟,但在城市應(yīng)急領(lǐng)域的應(yīng)用仍缺乏探索。本文旨在深度挖掘疏散對(duì)象本身特征和室內(nèi)空間信息,以建立一個(gè)滿足突發(fā)事件時(shí)應(yīng)急擁擠狀態(tài)查詢和鄰接對(duì)象位置查詢要求的混合位置更新策略。該策略是在室內(nèi)地標(biāo)單元的語(yǔ)義結(jié)構(gòu)和拓?fù)浣Y(jié)構(gòu)基礎(chǔ)上,結(jié)合對(duì)象本身速度、方向?qū)傩孕畔?保證疏散對(duì)象只在擁擠處或新的地標(biāo)單元處更新,減少大量不必要的和少數(shù)錯(cuò)誤的服務(wù)端位置更新次數(shù)。真實(shí)模擬場(chǎng)景實(shí)驗(yàn)表明,相比基于固定時(shí)間的策略和安全區(qū)域的策略,混合位置更新策略的單元置信度較高,并且位置更新頻次大幅減少,較好地解決了位置精確性和服務(wù)器通信代價(jià)矛盾的問(wèn)題。

［1]Jiang Bin,Yao Xiaobai.Location-based Services and GIS in Perspective［J］.Computers,Environmentand Urban Systems,2006,30(6):712-725.

［2]周傲英,楊 彬,金澈清,等.基于位置的服務(wù):架構(gòu)與進(jìn)展［J］.計(jì)算機(jī)學(xué)報(bào),2011,34(7):1155-1171.

［3]何云斌,樊守德,郝忠孝.基于MOST模型的移動(dòng)對(duì)象全軌跡建模［J］.計(jì)算機(jī)工程,2008,34(16):41-43.

［4]金培權(quán),岳麗華.移動(dòng)對(duì)象數(shù)據(jù)庫(kù)［M］.北京:高等教育出版社,2005.

［5]Cheng R,Lam K Y,Prabhakar S,et al.An Efficient Location Update Mechanism for Continuous Queries over Moving Objects［J］.Information Systems,2006, 32(4):593-620.

［6]丁治明.一種適合于頻繁位置更新的網(wǎng)絡(luò)受限移動(dòng)對(duì)象軌跡索［J］.計(jì)算機(jī)學(xué)報(bào),2012,35(7):1448-1461.

［7]Khalidi H A,Taniar D,Betts J,et al.On Finding Safe Regions for Moving Range Queries［J］.Mathematical and Computer Modelling,2012,58(5/6):1449-1458.

［8]李方亮,楊智應(yīng).基于移動(dòng)對(duì)象數(shù)據(jù)庫(kù)的航行信息更新機(jī)制［J］.上海海事大學(xué)學(xué)報(bào),2012,33(3):22-25.

［9]唐 蔚,張棟梁,范媛媛.移動(dòng)計(jì)算環(huán)境下路網(wǎng)上移動(dòng)對(duì)象的位置更新［J］.計(jì)算機(jī)科學(xué),2011,38(12): 106-109.

［10]王芙蓉,涂 來(lái),張 帆,等.移動(dòng)通信網(wǎng)中的一種邊界關(guān)聯(lián)位置更新策略［J］.電子學(xué)報(bào),2012,34(4): 684-689.

［11]Korhonen T,Hostikka S.Fire Dynamics Simulator with Evacuation:FDS+Evac.Technical Reference and User’s Guide［EB/OL］.(2009-04-03).http://www.vtt.fi/inf/pdf/workingpapers/2009/W119.pdf.

［12]Alamri S,Taniar D,Safar M,et al.Spatiotemporal Indexing for Moving Objects in an Indoor Cellular Space［J］.Neurocomputing,2013,122:70-78.

［13]張 旭,朱立東,吳詩(shī)其.低軌衛(wèi)星系統(tǒng)中結(jié)合時(shí)間和移動(dòng)的位置更新策略［J］.電訊技術(shù),2008,48(2): 57-60.

編輯 顧逸斐

A Hybrid Location Update Strategy for Indoor Evacuation Objects

LIU Tianyue1,2,YANG Lina1,CHI Tianhe1,PENG Ling1
(1.Institute of Remote Sensing and Digital Earth,Chinese Academy of Sciences,Beijing 100101,China;
2.University of Chinese Academy of Sciences,Beijing 100049,China)

When emergencies occur in the buildings,in order to monitor the evacuation objects and reduce location updates frequency,a hybrid location update strategy is proposed enriched by the velocity,direction properties of the evacuation objects and the topological,semantic structure of the indoor landmark unit.This strategy guarantees that the object is updated in crowded or landmark unit,and it reduces a few positioning errors due to indoor positioning uncertainty.As demonstrated by the experiments,compared with existing update strategies based on the fixed time or safety area,under the premise of meeting the location accuracy,this strategy keeps track of evacuated objects’detailed positioning information and crowded conditions with less communication cost.

evacuation object;location update;indoor space;landmark unit;velocity range;server-side

劉天悅,楊麗娜,池天河,等.一種適合于室內(nèi)疏散對(duì)象的混合位置更新策略［J］.計(jì)算機(jī)工程, 2015,41(3):292-297.

英文引用格式:Liu Tianyue,Yang Lina,Chi Tianhe,et al.A Hybrid Location Update Strategy for Indoor Evacuation Objects［J］.Computer Engineering,2015,41(3):292-297.

1000-3428(2015)03-0292-06

:A

:TP311

10.3969/j.issn.1000-3428.2015.03.055

國(guó)家青年基金資助項(xiàng)目“基于蜂群算法和多智能體的多目標(biāo)空間位置優(yōu)化搜索和并行計(jì)算研究”(1201397);科技部政策引導(dǎo)基金資助項(xiàng)目“國(guó)家遙感應(yīng)用工程技術(shù)開(kāi)發(fā)”(2011FU125Z24)。

劉天悅(1987-),男,博士,主研方向:時(shí)空數(shù)據(jù)庫(kù),地理信息系統(tǒng);楊麗娜,博士;池天河,研究員、博士生導(dǎo)師;彭 玲,研究員。

2014-02-18

:2014-04-21E-mail:liuty@radi.ac.cn