顾及外连通性的PIR传感器网络行为轨迹重构方法

潘 炳 煌,滕 玉 浩,钱 凌 欣,罗 文,俞 肇 元

(南京师范大学虚拟地理环境教育部重点实验室,江苏 南京 210023;江苏省地理环境演化国家重点实验室培育建设点,江苏 南京 210023;江苏省地理信息资源开发与利用协同创新中心,江苏 南京 210023)

0 引言

随着大数据与泛在信息的发展,室内环境行为轨迹分析逐渐得到重视[1]。基于高密度、低成本的热释电红外(Passive Infrared,PIR)传感器网络进行人群行为轨迹的定位与重建,是室内环境行为轨迹分析的重要手段。PIR传感器通过感知一定范围内是否有人经过输出布尔信号,能以较低成本获取人员位置信息,实现对人群行为轨迹的识别与跟踪,相比WiFi[2,3]、GPS[4]等手段的室内定位更精确,已广泛应用于室内追踪[5]、行为特征分析[6,7]等领域。

现有利用传感器数据进行行为特征提取[8]的研究可分为3类:①行为特征识别与分类。主要利用统计学方法(如Kalman滤波[9]、隐Markov链模型[10]、topic模型[11]、贝叶斯网络[12])提取人类行为,或通过样本训练对人类行为特征进行建模与识别,建模方法有神经网络[13]、支持向量机[14,15]、深度学习[16]等。②轨迹追踪[17]。通过将轨迹片段相关联实现对对象的连续追踪(如tracklets方法[18,19])。Ivanov等[20]利用tracklets图模型组织室内PIR传感器响应序列,实现轨迹分布网络构建,并借助图像传感器获得实际行人轨迹。③轨迹重构。根据传感器数据重现行为运动轨迹,如路网结构上的车辆轨迹重构方法[21-23]、传感器网络上的行人轨迹重构方法[24,25]。在PIR传感器行为轨迹重构方面,基于几何代数[26]的方法对传感器网络上的响应数据进行全局统一分析,以相邻传感器在连续时间上的响应次序重构行人在传感器网络上的行为轨迹。然而,几何代数方法没有考虑传感器的实际分布场景和相邻传感器之间距离造成的时间差异,重构结果不确定性较大;同时,该方法使用矩阵外积形式进行轨迹重建,涉及大量矩阵计算,时间复杂度较高。针对上述不足,袁林旺等[27]在几何代数轨迹重构的基础上,使用模板匹配的思路降低了轨迹重构中的计算量,提高了效率,但该方法中的四邻域模板无法匹配所有的传感器拓扑结构。

事实上,传感器网络是一个伴随着行人出入的开放系统,因此,传感器的布设环境影响轨迹分布的特征,考虑传感器的布设环境有助于提高轨迹重构的空间约束完整性和重构结果一致性。鉴于此,本文提出一种顾及传感器外连通性的PIR传感器网络行为轨迹重构方法,利用传感器网络的布设环境约束降低轨迹重构中的不确定性,从而提高轨迹重构的准确度。

1 研究方法

PIR传感器是一种检测视场内物体辐射红外光的电子器件,基于热释电效应对行人进行监测和记录,被触发时呈现高电压状态,未被触发时呈现低电压状态[28]。当行人在传感器网络的感应区域内移动时,相关传感器会在一定时间内相继响应并记录响应的起止时间。传感器的外连通性表示传感器是否直接与网络外界连通,行人能从外连通的传感器处进入或者离开传感器网络,无外连通性的传感器在环境的约束下,行人只能来自其他传感器的感应区域。由于PIR传感器只能感知是否被触发,故无法直接判断出行人的数量和运动状态,在轨迹重构中存在不确定性。如图1a所示,行人处于传感器6的感应区域内,下一时刻可能向传感器2、5、7移动,也可能在传感器6区域保持不动。当下一时刻传感器的响应状态如图1b所示时,在对行人行为进行判断时,会出现不确定的情况,即传感器7(与外界直接连通)范围内的行人可能来自传感器6,也可能来自传感器外界。因此,轨迹可能是“6→2”与“7”,也可能是“6→2”与“6→7”。综上,由于PIR传感器不支持对行人数量的判断以及运动方向的感知,因此,在传感器网络的轨迹重构中需要考虑各种影响行为轨迹的情况,通过多个传感器识别行人在空间中的运动轨迹,以提高行为识别的完备性。

图1 传感器网络上运动方向

本文研究流程包括PIR传感器网络场景模拟、轨迹重构以及重构结果检验3个步骤(图2)。①PIR传感器网络场景模拟。现有公开数据集多不包含真实轨迹,无法验证方法重构结果的准确性。因此,本文将PIR传感器网络场景模拟数据作为行为轨迹重构的数据来源,具体而言:使用PIR传感器场景模拟产生数据,模型根据MERL[29]公开的传感器分布场景构建,一共有两层,分布有213个传感器。PIR场景模拟系统通过随机生成“小球”模拟行人运动,传感器会在“小球”进入感应区域内改变颜色,并记录响应的起止时间。②轨迹重构。包括传感器网络模型构建、时空约束定义和轨迹生成3个部分(流程如图3所示),当获取到一条新的感应记录,将以两条线路对数据进行处理,第一条线路是进行拓扑判断与轨迹更新,逐个分析轨迹链表库中的轨迹,判断轨迹是否与当前处理的响应记录满足时空约束条件,满足则对当前轨迹进行延伸,同时,判断轨迹是否结束,已经结束的轨迹将被重新组织存储到轨迹存储库中;第二条线路判断当前响应传感器的外连通性,当传感器的响应时间特征满足设定条件时,从该传感器创建新轨迹。通过逐个处理响应记录,不断进行新建轨迹、轨迹更新和轨迹转储,最终得到传感器网络上的连续行为轨迹。③重构结果检验。对重构得到的轨迹数据与PIR场景模拟系统导出的真实轨迹进行对比,分析轨迹重构的精度。

图2 PIR传感器网络轨迹重构框架

图3 PIR传感器网络行为轨迹重构分析流程

1.1 传感器网络模型构建

传感器网络是轨迹重构的基础,在轨迹重构中作为空间约束。本文将传感器网络表示为图G=(V,E):V={v1,v2,…,vN}为包含N个顶点的集合,任意一个顶点可表示为vw={xw,yw,cw},其中,xw、yw为传感器的二维坐标,cw∈{0,1}表示传感器的外连通属性;E={(vr,vc),…}(vr,vc∈V)为传感器网络的边集,其中,(vr,vc)表示传感器r与传感器c的感应区域连通。

1.2 时空约束定义

对轨迹重构过程定义两个条件约束:传感器布设环境的空间约束和传感器响应的时间约束,前者可具体分为传感器网络的拓扑结构与传感器的外连通性,后者包括传感器的编号、响应的起止时间。令S={s1,s2,…}表示响应记录的数据集,其中,每条响应记录sk={vk,tk,ek},sk∈S,vk∈V,tk、ek分别表示传感器响应的起始时间、结束时间。基于响应数据进行轨迹重构实际上是找到在连续时间和相邻空间上的响应序列,则重构轨迹可用一串响应记录p=sa→sb→sc→…表示。

图4 传感器位置表示

若当前处理的响应记录对应的传感器具有外连通性,即cj=1,则需要考虑当前传感器是否为新轨迹的起点。由于传感器无法识别行人的数量,因此,本文从传感器响应的时间长度以及相邻传感器响应时间重叠上判断是否有轨迹加入。在感应区域相邻的传感器网络中,行人在经过相邻传感器的感应区域时,会存在一段两个传感器均响应的时间,记为T。如果存在行人进入传感器网络,则会出现以下3种状态:①进入网络处无其他行人,该状态可直接判断轨迹。②进入网络处有行人,两人前后行走,该状态下两个传感器共同响应时间较长,也可能是行人在传感器交界处停顿导致,此时,当传感器处外连通,会优先考虑行人进入的情况,从而得出判断条件为k1T≤tj-ei≤k2T(表示行人从传感器i运动到传感器j,k1和k2为比例因子,表示单个行人经过一个传感器感应区域的最大波动比例和行人静止的最小波动比例;当ej-tj>k2T时,认为行人静止),则认为当前传感器上有新的行人进入。③进入网络处有行人,两人并排行走。该状态无法从传感器响应的时间判断,只能作为同一轨迹处理。重构轨迹结束判断条件是传感器与外界直接连通且不存在时间相邻的响应记录,即(cj=1)∧(tj-ei>ε),其中,ε>0为时间阈值,tj为剩余所有响应记录中最早的时间。

1.3 轨迹生成

在制定好轨迹重构的时间约束后,依次处理传感器的响应记录,进而生成轨迹。假设重构轨迹的集合为P={p1,p2,…},新加入的响应记录为s={v,t,e},以τ作为响应记录是否被处理的标记量,τ=0表示未处理当前记录,以γ(p,s)判断传感器感应记录s是否满足轨迹p延伸的时空约束条件,满足时空约束输出1,否则输出0。轨迹重构过程包括:

1)轨迹新增,即对满足时空约束条件的响应记录创建轨迹并加入轨迹集合中。轨迹新增存在两种情况:一是响应记录对应的传感器具有外连通性,且满足轨迹新增的条件,可表示为(c=1)∧(k1T≤tj-ei≤k2T),此时在轨迹集合中新增一条以当前传感器位置为起始的轨迹,并将τ置为1;二是当前响应记录与轨迹集合中的任何轨迹没有时空相关性,即∀p∈P,∃γ(p,s)=1,记τ=1,否则τ=0,对集合中的轨迹逐个判断后标记量τ=0。

2)轨迹更新,在处理的响应记录与轨迹具有时空相关性时进行。分别对轨迹集合中的每条轨迹进行时空约束判断,当满足时空约束((ei≥tj)∧(ti≤tj)∧(ei≤ej))∧((vi,vj)∈E),则将感应记录信息加在轨迹的尾端,即如果存在γ(p,s)=1,则使用响应记录s的信息对轨迹p进行延伸,并将τ置为1。

3)轨迹转储,是将轨迹集合中已经结束的轨迹另外存储并从轨迹集合中剔除,以减少后续感应记录判断的次数。轨迹结束的判断条件为(cj=1)∧(tj-ei>ε),即如果存在γ(p,s)=0,则将轨迹p另外存储并从轨迹集合P中删除。

1.4 数据组织与方法实现

根据传感器响应记录处理流程特点,为数据处理中的每部分设计合适的数据结构(图5)。其中,传感器网络拓扑结构(图5a)需提前输入传感器网络的结构,并设置每个传感器的外连通性,另外存储每个传感器的编号与传感器所在的空间位置,由于此部分查询操作较多,且传感器网络为稀疏图,故用邻接表的形式组织;响应数据处理队列(图5b)接收传感器的响应数据,并将数据按传感器响应的起始时间依次加入队列中,后续按顺序处理响应数据,此部分的主要操作是插入与删除,不涉及数据的查找与更新,是标准的队列操作;轨迹处理链表(图5c)用于存储尚未重构结束的轨迹,存放每条轨迹的ID以及轨迹关联的所有传感器编号,当检测到当前轨迹已结束,则将轨迹数据转储到轨迹仓库,此处插入、删除操作较多,故用链表的形式组织,此外,对轨迹链表尾端的判断较频繁,在每条轨迹的头部存储轨迹尾端的地址;轨迹存储仓库(图5d)以轨迹ID、位置坐标、时间戳的形式存储已完成构建的轨迹数据。

图5 数据结构

根据传感器网络轨迹重构中时间连续性、传感器拓扑、传感器外连通性的3个时间约束构建传感器响应记录分析算法(算法1)。

算法1顾及外连通性的传感器路径重构算法

函数:轨迹时空判断ST(p,s),轨迹延伸PE(p,s),轨迹结束判断PD(p,s,ε),获取传感器外连通性G(v),轨迹转储PR(D,p),创建轨迹NP(P,s),判断响应记录时间长度是否触发新增轨迹条件TE(p,s)

参数说明:p表示一条轨迹,s表示传感器的一条响应记录,v表示一个传感器

输出:轨迹存储集D

FORm=1TOMDO

// 对于每一条响应记录,使用每一条轨迹与之判断

// 创建变量:z←TRUE

FORn=1TONDO

// 时间连续性判断

IFST(pn,sm)==TRUETHEN

// 传感器拓扑相邻判断

IFPD(pn,sm)==TRUETHEN

改变变量的值:z←FALSE

轨迹延伸:PE(pn,sm)

// 判断当前传感器处是否会有行人进入

IF(G(sm)==TRUE)&&(TE(pn,sm)==TRUE)THEN

创建新轨迹,存储到P:NP(P,sm)

ENDIF

ENDIF

ELSE

// 判断轨迹是否结束

IFPD(pn,sm,ε)==TRUETHEN

将轨迹转储到D:PR(D,pn)

ENDIF

ENDIF

ENDFOR

// 当前感应数据未处理

IFz=TRUETHEN

创建新轨迹,存储到P:NP(P,sm)

ENDIF

ENDFOR

2 实例验证

2.1 研究对象与数据

本文基于三菱电气研究实验室(Mitsubishi Electric Research Labs,MERL)公开的室内场景以及传感器网络分布构建PIR传感器模拟场景,该场景实现了PIR传感器的响应机制,支持对行人运动的模拟,记录运动轨迹与传感器的响应数据,响应数据格式与MERL一致。模拟场景分为两层,共布置213个PIR传感器[29],本文选择其中第二层作为研究对象,按照传感器的空间分布以及传感器之间的连通性构建网络模型并设置传感器的外连通性(图6)。在PIR模拟程序中能模拟任意数量的行人运动,导出传感器的响应记录,并将实际轨迹导出作为重构结果对比。

图6 传感器分布以及网络模型

2.2 轨迹重构

为从传感器响应序列中构建合理的轨迹,本文根据传感器网络的实际分布设置约束条件。假设普通人的行走速度范围为1～2 m/s,每个传感器的感应区域边长为2 m,则按照正常的行走速度,行人从一个传感器中心区域进入一个相邻传感器中心区域的时间约为2 s,故以2 s作为判断轨迹结束的阈值,低于2 s则认为满足时间约束条件。在设置重构约束条件后,依次处理传感器的响应记录,重构传感器网络上的行为轨迹。以对10个行人的运动轨迹进行重构为例,由真实的轨迹分布与重构结果(图7)对比可以看出,本文方法能对传感器的感应数据进行有效重构,轨迹的整体分布基本一致。由于使用时间连续的条件判断轨迹是否连续经过空间上不邻近的传感器,本文方法允许出现空间不相邻的传感器。另外,本文方法重构的轨迹在传感器分布密集处难以准确判断实际轨迹路线,导致重构轨迹比真实轨迹多。

图7 轨迹重构结果对比

2.3 精度分析

为定量对比重构轨迹与真实轨迹之间的差异,本文使用最长公共子序列(Longest Common Subsequence,LCSS)[30]计算真实轨迹A与重构轨迹B的匹配程度DLCSS,计算公式为:

LCSS(Ai,Bj)=

(1)

DLCSS=LCSS(Ai,Bj)/i

(2)

式中:LCSS(Ai,Bj)为轨迹A、B的LCSS长度,i,j分别为轨迹A、B的序列长度,γ为轨迹点相似阈值,dist(Ai,Bj)为两个轨迹点在空间和时间上的匹配程度。

由图8可知,随机构成的10条轨迹大部分能被有效识别,其中有一条由4个点构成的轨迹的匹配度为0.75,表明本文方法的重构精度较高。进一步从时间复杂度上分析,本文方法主要受传感器响应记录的数量M与轨迹处理链表中轨迹数量N的影响。如算法1所示,本文方法主要是对轨迹的尾端结点和传感器响应记录进行拓扑比较,依次取出响应记录并与轨迹处理链表中的所有轨迹相比较,其中传感器响应记录的数量M确定,轨迹处理链表中的轨迹数量N为变量,故时间复杂度为O(M×N),可见本文方法在行人较少的场景中效率较高。

图8 轨迹重构精度评估

3 结论与讨论

基于传感器数据的特征分析是室内行为研究的重要手段。PIR传感器的室内轨迹重构能在不涉及隐私的情况下分析行人的移动特征、活动范围等,在隐私保护意识不断增强的大环境下使用低成本、无接触的PIR传感器进行室内行为监控具有重要研究意义。当前在PIR传感器的行为轨迹重构中存在计算量大、考虑因素不完备等问题,本文提出的顾及外连通性的传感器网络行为轨迹重构方法将传感器的布控范围纳入轨迹重构的考虑因素中,通过设定时空约束条件降低轨迹重构过程中的不确定性,模拟实验结果表明,本文方法能有效重构行为轨迹且与真实轨迹的匹配度较高,部分轨迹重建结果与原始轨迹不完全相符,主要原因在于实验选取的时空相关性判断条件固定,面对复杂的传感器分布场景以及轨迹分布出现判断偏差。

室内场景是地理分析的重要组成部分,室内传感器网络是室内定位数据的重要来源,基于传感器网络的轨迹重构是室内运动分析的重要方法。由于PIR传感器对空间中行人数量监测的功能缺陷,导致无法准确预估轨迹的数量,通过算法分析能在一定程度上还原传感器网络上的轨迹走向。本文引入传感器外连通性,能识别并处理更多的记录,提高了传感器响应数据处理的完备性与结果一致性,也为二值传感器研究提供了新思路。本文方法有待改进之处在于:①在轨迹重构中使用响应记录依次延伸轨迹,未能通过后续的轨迹走向对先前轨迹中的不确定问题进行优化,也不能判断复杂分布场景中的轨迹数量;②需改进轨迹重构中延伸轨迹的条件,针对不同传感器分布的局部特征使用不同的判断规则;③通过考虑传感器感应区域的外连通关系,结合重构轨迹的分布特征,从而判断传感器分布区域内通道的畅通情况,也是方法改进的一个方向。