一種適合于室內疏散對象的混合位置更新策略

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

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

一種適合于室內疏散對象的混合位置更新策略

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

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

當建筑物內發生突發事件時,為更好地跟蹤疏散對象,減少位置更新頻率,提出一種基于疏散對象速度、方向屬性和室內地標單元拓撲、語義結構相結合的混合位置更新策略。當疏散對象速度范圍和地標單元兩者中有一項發生變化,并滿足鄰接單元關系時將位置更新到服務端,既保證對象在擁堵處或地標單元處更新,又避免由于室內定位不確定性產生的少數錯誤更新。實驗結果表明,與已有的基于固定時間或安全區域的更新策略相比,該策略能夠在保證疏散對象位置精確度的情況下,以較小的通信代價持續跟蹤疏散對象的詳細位置信息和擁擠狀態。

疏散對象;位置更新;室內空間;地標單元;速度范圍;服務端

1 概述

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

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

針對移動對象的位置更新問題,一些學者已提出多種解決方法。其中,基于時間和距離更新移動對象信息是2種最常見的方法。基于時間的更新,比如基于固定時間的更新;時間更新還有基于查詢結果更新,它是一種自適應的更新方法,基于對象的運動預測其更新的時間閾值［5］;基于距離的更新,如概略化軌跡更新,它是一種基于網絡受限移動對象的動態概略化軌跡,將索引空間劃分成等距格柵,僅需要在軌跡跨越當前格柵單元時才進行索引更新［6］;距離更新還有一種基于查詢目標的安全區域的方法,在安全區域內,若查詢目標沒有發生改變不需要更新［7］。

除此之外,文獻［8］在航行信息更新中采用向量的更新方法;文獻［9-10］也分別提出了根據移動對象所在路網的幾何形狀或者邊界拓撲關聯實現狀態更新。但這些更新策略大都局限于室外空間或路網,很少有結合室內空間語義、拓撲結構進行設計,也沒有結合突發事件時疏散對象的速度范圍進行劃分,很難反映室內擁堵狀態。

本文從室內應急角度出發,采用疏散對象移動速度范圍和室內地標單元相結合的混合位置更新策略,在保證位置查詢精確度的基礎上,降低服務端更新代價。

2 室內地標單元

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

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

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

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

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

圖1 室內地標單元空間

圖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最近的對象是O1不是O3,因此采用鄰接單元距離CDist(Oi,Oj)能夠近似表達疏散對象間的實際距離。

圖2 鄰接單元矩陣

由于室內定位具有偏差和不確定性,比如說疏散對象實際在走廊上行走,當前任何定位方式都有可能錯誤地將其定位到相鄰的房間內,而通過室內地標單元的鄰接單元矩陣可減少由于位置不確定性造成的錯誤更新。因此,構建以室內地標單元為基礎的室內空間信息不僅能給人以各種復雜環境的直觀展示,同時也作為疏散對象位置更新的過濾條件。

3 位置更新策略

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

3.1 速度范圍規則

速度范圍規則(以下簡稱速度規則)指移動端判斷疏散對象當前所在速度范圍是否發生變化。當對象進入某個速度范圍時進行一次更新,直到離開這個速度范圍才進行下一次更新。滿足該規則,則直接進入鄰接單元規則判斷,否則,跳過當前位置進行室內地標規則判斷。通過速度范圍變化引起的位置更新,能夠實時監控室內單元的擁堵狀態。根據文獻［11］的研究,定義了疏散對象4個速度范圍及擁擠狀態,如表1所示。

表1 疏散對象速度范圍及擁擠狀態

3.2 室內地標規則

室內地標規則(以下簡稱地標規則)是指移動端獲取的疏散對象方向屬性與所在室內地標單元的語義或拓撲關系相比較。每當疏散對象經過室內地標處,定位終端判斷其是否滿足地標規則,若滿足,則進入鄰接單元規則階段判斷;否則,跳過當前時刻位置進行下一位置判斷。隨著時間推移,前一個地標可能會不準確,但隨著終端碰到下一個地標,從而不斷糾正它的位置。該規則的算法流程如圖3所示。以每一個對象當前位置做圓心,半徑為r的圓形緩沖區作為對象的位置不確定區域,緩沖區半徑r由室內水平定位精度決定。首先,查詢緩沖區內所有相交單元個數ncell,若ncell=0,則舍棄該點;若ncell= 1,直接進入鄰接單元規則階段;若ncell＞1,則判斷緩沖區內有哪些地標(nmark表示所有地標點的個數)與之相交,然后進入地標規則進行過濾。地標規則包括2種,一種是地標拓撲規則,另一種是地標方向規則。

圖3 室內地標規則算法流程

3.2.1 地標拓撲規則

室內地標單元具有拓撲鄰接和拓撲包含屬性,比如說房間單元和門地標是拓撲鄰接關系;走廊單元和走廊地標之間存在拓撲包含關系。如果更新地標與對象所在當前單元存在拓撲鄰接或拓撲包含關系,則滿足地標拓撲規則,然后進入地標方向規則進行判斷。反之,進行緩沖區內下一個地標的判斷。

3.2.2 地標方向規則

地標方向以方向字段作為疏散對象位置更新的過濾規則。比如房門地標方向主要用于判斷對象是否從房間進入走廊;走廊地標的方向用于判斷對象是否在走廊單元內行走。若疏散對象的方向與滿足地標拓撲規則后的地標方向相差在X度內(X由電子羅盤的誤差水平決定),則滿足規則2進入下一個鄰接單元規則階段。

3.3 鄰接單元規則

考慮疏散對象位置具有不確定性,無論網絡、硬

件或相關定位算法如何改進或優化,定位精度總存在不同程度的偏差,極少數點可能定位到錯誤的室內單元甚至到樓宇之外。因此,需要第3個規則——鄰接單元規則(以下簡稱單元規則)對疏散對象位置做進一步的過濾。它指當對象進入某個地標單元(單元,地標)時進行一次更新,直到離開這個地標單元或者經過新的地標單元處時并滿足鄰接單元拓撲關系時才進行下一次更新。突發事件發生時,房門和走廊出口是比較容易產生擁堵的地方,也更容易發生漂移現象。因此,采用鄰接單元矩陣進行約束和過濾,保證更新后的房間單元或者走廊單元是正確的,該規則的算法流程如圖4所示。

圖4 鄰接單元規則算法流程

(1)當鄰接單元距離CDist(Clast,Ccurrent)＞1時:滿足地標規則的當前單元Ccurrent與服務端前一個單元Clast不相鄰接,則舍棄當前位置;

(2)當鄰接單元距離CDist(Clast,Ccurrent)=0時:滿足地標規則的當前單元Ccurrent與服務端前一個單元Clast相同,并且當前地標Mcurrent和前一個地標Mlast相同則不更新,反之,更新當前位置;

(3)當鄰接單元距離CDist(Clast,Ccurrent)=1時:滿足地標規則的當前單元Ccurrent與服務端前一個單元Clast相鄰接,則更新當前位置。

3.4 實例說明

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

H=(V∩M)∪C

當H值為true時,則更新;反之,則不更新。假設對象O1有8條位置記錄,如圖5所示,其中Vi(i=0～7)表示疏散對象速度,i表示時刻。混合位置策略的更新步驟如下:

(1)T0時刻:對象O1開始移動,對象初始位置均更新,故更新位置為O1(C2,null,T0);

(2)T1時刻:對象O1雖不滿足速度規則,但滿足地標規則和單元規則,故更新位置為O1(C2,M1,T1);

(3)T2時刻:對象O1不滿足速度規則和地標規則任何一個,故不需要再判斷單元規則,不更新;

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

(5)T4～T6時刻:對象O1不滿足速度規則和地標規則兩者之一,故不更新;

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

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

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

表2 更新策略的更新過程

4 實驗及結果分析

4.1 實驗環境

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

圖6 試驗樓層室內地標單元

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

18人開始真實模擬小范圍的疏散情景,每人攜帶一臺終端,分2組,每組9人。按照預先計劃的移動路線①和路線②進行,如圖7所示。2組人分別從單元號為C15和C14的2個會議室同時開始移動,終點都是C1樓梯間。為了能更好地模擬突發事件發生時可能產生的室內擁堵現象,假設M15,M14和M33個地標任一時刻都只能允許一個人通過。具體參數和數值如表3所示。

圖7 實際疏散路線

表3 參數和對應數值

4.2 結果分析

本研究采用單元置信度和位置更新頻次評價混合策略和其他策略。

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

(2)位置更新頻次:表示隨時間推移移動對象的位置更新次數,它也代表對象位置更新的通信及計算代價。

從圖8中可以看出,固定時間(1 s)的單元置信度最高,混合策略和固定時間(3 s)次之,安全區域策略最差。固定時間(1 s)比混合策略提供了最準確的位置,但也具有最高的信息成本。盡管混合策略的置信度不是最高,比固定時間(1 s)略低,但是高于其他更新策略,主要原因有2個:(1)混合策略通過室內地標單元拓撲結構舍去了錯誤的位置更新;(2)混合策略采用走廊單元內的地標作為觸發更新的條件,地標大多在走廊單元的中心處,不容易產生單元偏離;而固定時間策略的更新時間不確定;安全區域策略則是剛進入單元后更新,很容易產生單元偏離。

圖8 單元置信度

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

圖9 實際疏散定位軌跡

表4 更新前后通信代價對比

對于運動速度變化快的移動對象來說,固定時間策略無法及時反映移動對象運動速度的變化及其位置的變化,將導致服務端產生嚴重的誤差。如果設置太小,如固定時間(1 s)策略則會產生過多的位置更新次數,給服務端帶來較大的更新負擔［13］,如果設置太大則無法保證服務端移動對象位置信息存儲的精確度,如固定時間(3 s);安全區域策略的更新次數雖然比固定時間策略少,但是沒有考慮移動對象本身速度等屬性,并且無法查詢什么時間、什么單元處于擁堵狀態。總之,混合策略的更新次數明顯減少,實現成本的顯著降低。另外,混合策略的各種規則耗費的時間都在毫秒級別,遠低于位置更新1次的時間。因此,耗費時間可忽略不計。

5 結束語

國內外移動對象數據庫方面的研究已經趨于成熟,但在城市應急領域的應用仍缺乏探索。本文旨在深度挖掘疏散對象本身特征和室內空間信息,以建立一個滿足突發事件時應急擁擠狀態查詢和鄰接對象位置查詢要求的混合位置更新策略。該策略是在室內地標單元的語義結構和拓撲結構基礎上,結合對象本身速度、方向屬性信息,保證疏散對象只在擁擠處或新的地標單元處更新,減少大量不必要的和少數錯誤的服務端位置更新次數。真實模擬場景實驗表明,相比基于固定時間的策略和安全區域的策略,混合位置更新策略的單元置信度較高,并且位置更新頻次大幅減少,較好地解決了位置精確性和服務器通信代價矛盾的問題。

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

［2]周傲英,楊 彬,金澈清,等.基于位置的服務:架構與進展［J］.計算機學報,2011,34(7):1155-1171.

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

［4]金培權,岳麗華.移動對象數據庫［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]丁治明.一種適合于頻繁位置更新的網絡受限移動對象軌跡索［J］.計算機學報,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]李方亮,楊智應.基于移動對象數據庫的航行信息更新機制［J］.上海海事大學學報,2012,33(3):22-25.

［9]唐 蔚,張棟梁,范媛媛.移動計算環境下路網上移動對象的位置更新［J］.計算機科學,2011,38(12): 106-109.

［10]王芙蓉,涂 來,張 帆,等.移動通信網中的一種邊界關聯位置更新策略［J］.電子學報,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]張 旭,朱立東,吳詩其.低軌衛星系統中結合時間和移動的位置更新策略［J］.電訊技術,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

劉天悅,楊麗娜,池天河,等.一種適合于室內疏散對象的混合位置更新策略［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

國家青年基金資助項目“基于蜂群算法和多智能體的多目標空間位置優化搜索和并行計算研究”(1201397);科技部政策引導基金資助項目“國家遙感應用工程技術開發”(2011FU125Z24)。

劉天悅(1987-),男,博士,主研方向:時空數據庫,地理信息系統;楊麗娜,博士;池天河,研究員、博士生導師;彭 玲,研究員。

2014-02-18

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