一种适合于室内疏散对象的混合位置更新策略

刘天悦,杨丽娜,池天河,彭 玲

(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