顧及外連通性的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傳感器對空間中行人數量監測的功能缺陷,導致無法準確預估軌跡的數量,通過算法分析能在一定程度上還原傳感器網絡上的軌跡走向。本文引入傳感器外連通性,能識別并處理更多的記錄,提高了傳感器響應數據處理的完備性與結果一致性,也為二值傳感器研究提供了新思路。本文方法有待改進之處在于:①在軌跡重構中使用響應記錄依次延伸軌跡,未能通過后續的軌跡走向對先前軌跡中的不確定問題進行優化,也不能判斷復雜分布場景中的軌跡數量;②需改進軌跡重構中延伸軌跡的條件,針對不同傳感器分布的局部特征使用不同的判斷規則;③通過考慮傳感器感應區域的外連通關系,結合重構軌跡的分布特征,從而判斷傳感器分布區域內通道的暢通情況,也是方法改進的一個方向。