加速度差分有限状态机计步算法*

王革超，梁久祯，陈　璟，朱向军江南大学 物联网工程学院，江苏 无锡 214122

加速度差分有限状态机计步算法*

王革超+，梁久祯，陈璟，朱向军
江南大学 物联网工程学院，江苏 无锡 214122

WANG Gechao,LIANG Jiuzhen,CHEN Jing,et al.Step counting algorithm based on finite state machine using acceleration differential.Journal of Frontiers of Computer Science and Technology,2016,10(8)：1133-1142.

摘要：在用户行为无法预知的实际计步应用中，如何保持计步算法的准确性和稳定性是一个极具挑战的问题。传统的计步算法利用阈值设定和峰值检测，并不能解决计步算法的普适性和稳定性。针对上述问题，提出了基于加速度差分作为特征的有限状态机（acceleration differential based on finite state machine，AD-FSM）计步算法。该算法将原始加速度取平方和，并通过卡尔曼滤波去除噪声干扰，最后使用加速度差分有限状态机实现计步检测。实验结果表明，该算法在正常和干扰情况下能够提供精确的计步结果，误差分别为1.12%、4.00%，验证了该计步算法在降低状态机复杂度的同时具有较强的稳定性和鲁棒性，更能适应复杂的应用场景。

关键词：室内定位；计步；抗干扰；有限状态机；加速度差分

1　引言

步行作为人类活动中最基础、最普及、最重要的运动形式，使得深入地研究计步器具有重要的意义[1]。在过去的十年里，智能手机在计算能力、内存大小和微机电传感器（如加速计、磁力计、陀螺仪）数量方面有着极大的改善，而其性能可靠、低成本、不受外界环境限制等特点，使得基于手机内置传感器的应用方案得到了广泛关注和研究。其中室内定位技术因在商业、公共安全以及军事等诸多领域中的广泛应用需求，成为信息技术领域重点研究对象之一。

近年来，国内外学者提出了很多室内定位技术和算法，主要有基于红外线、超声波、RFID（radio frequency identification）和LED[2]等技术。在基于手机惯性传感器的计步方案中[3-6]，个人航位推测（personal dead reckoning，PDR）方案已成为当前室内定位的新热点[7]。PDR技术运用步数-步长模型[8-9]，结合初始已知位置的位移和方向信息，使用惯性传感器来计算室内行人的位移量，因此需要计步器进行距离量测。

加速度传感器可以检测人体运动过程中加速度的变化，对加速度值进行处理判断后输出运动人员的累计步数[10]。目前，计步方案中基于加速度传感器的计步算法成为研究热点。文献[11]的实验表明，基于加速度传感器的计步算法具有高鲁棒性和低复杂度的优势，这对智能手机有限的计算能力、内存大小和续航能力极为重要。

当前计步算法主要分为以下4类：

（1）设定阈值

文献[12]提出在用户脚上安装惯性传感器，通过一个加速度方差阈值的滑动窗口过滤加速度数据，然后对其判断是否达到两个预设定的阈值。该方法依赖高精度加速度计，不适用于手机内置的加速度传感器。文献[13]提出的基于加速度的计步算法引入了校正因子，用于修正幅值检测的阈值，提高了检测精度。文献[14]提出在用户脚踝安装惯性传感器进行计步检测，当加速度值达到设定阈值时，步数累加，该算法也依赖高精度传感器和静态阈值。自适应调整阈值能够提高该计步方法的精度。

（2）峰值检测

文献[15]提出的行走时的水平加速计值和垂直加速计值变化曲线可以被近似认为正弦波，通过识别正弦波进行计步判定。文献[16]的零交叉法对加速度信号低通滤波后，由加速度信号正向过零的次数进行计数。零交叉法对于噪声较少的信号工作良好，然而正常情况下，加速度信号更为复杂，且不按周期分布。因而对于零交叉法，难以精确地确定步数。文献[17]首先通过低通滤波器对加速计数据过滤噪声，然后检测两个局部最小值之间选取局部最大值，根据最小值与最大值之差是否大于预设定阈值进行计步检测。峰值检测算法的复杂度比较低，但当用户遇到干扰时，同样会达到峰值，检测到多余的步数。

（3）零速率修正

文献[18-19]使用零速率修正（zero velocity update，ZUPT）方法进行步数检测，对加速度积分获得垂直位移，并通过几何计算得出步长信息。该方法需要将传感器装置固定在腰上，对噪声的抗干扰能力较差。文献[20]提出一种粒子滤波框架下利用建筑物结构先验知识对ZUPT算法计算的轨迹进行修正的算法，提高了定位精度。

（4）算法融合

文献[21]针对之前算法对手机摆放位置和使用习惯等限制，提出了一种精确的计步算法。该算法第一阶段从智能手机的加速度计获取线性加速度值和重力值。然后，获取线性加速度值的水平分量，并且确定线性加速计数据的周期波动的起始点。第二阶段采用相关系数的概念，对采集的传感测量值判断是否符合相似波形趋势并计算步数。相比之前算法，该算法针对手机不同摆放位置的处理具有明显的优势。

Alzantot等人[22]通过使用有限状态机（finite state machine，FSM）与阈值进行计步检测，根据步态变化调整相应阈值。Yim[23]在此算法基础上，对有限状态机增加一个状态，更好地屏蔽噪声数据，提高了计步精度。有限状态机对加速度正弦波检测效果较好且复杂度小，但Alzantot和Yim的算法没有对数据进行预处理操作，实验结果也表明其抗干扰能力较弱。

以上计步算法[12-23]大多在理想情况下采集数据，极少考虑复杂的现实应用环境对加速度采集数据造成的噪声干扰。对此，本文提出一种使用加速度差分作为特征的有限状态机计步算法，称为加速度差分状态机计步算法（acceleration differential based on finite state machine，AD-FSM）。与现有算法相比，本文计步算法具有以下特点：（1）以加速度差分为特征；（2）阈值设定与步频、采样频率相关；（3）屏蔽噪声机制，可以有效地屏蔽异常情况，提供精确的计步结果。

2　加速度差分状态机计步算法

Alzantot和Yim设计的FSM在正常情况下，对如图1所示的正弦波检测效果较好。在异常情况下，如手机震动来电，手动模拟行走等情况下，加速度变化如图2所示。此前FSM算法对符合阈值的正弦波进行步数判定，没有考虑干扰情况下正弦波周期的异常变化，因而得出偏差较大的结果。针对干扰情况下出现的异常数据，本文使用加速度差分作为特征的有限状态机计步算法。

Fig.1　Acceleration signal under normal environment图1　正常情况下的加速度变化

Fig.2　Acceleration signal under interference environment图2　干扰情况下的加速度变化

2.1数据预处理

手机内置的加速度传感器一般都是三轴的，可以测得手机发生运动时的前向加速度、侧向加速度和垂直加速度，如图3所示。实际应用中，用户携带手机的方式多种多样，为了使计步算法能够适用于不同位置上手机的摆放，一般采取的方法是对三轴加速度值的平方求和得到总的加速度，如式（1）所示，结果如图4所示。

Fig.3　Raw signals from accelerometer图3 原始加速度值

Fig.4　Acceleration after combination图4　合成后的加速度值

2.2卡尔曼滤波

现代多数的智能手机配置的传感器由于噪声以及伴随时间的衰退，经常会产生错误的数据，不能精确地测量数值。因此，需要算法对原始数据进行矫正和过滤。

卡尔曼滤波器用于估计离散时间过程的状态变量x∈ℜn[24]。这个离散时间过程由式（2）离散随机差分方程描述：

定义观测变量z∈ℜn，得到测量方程式（3）：

其中，随机信号ωk和vk分别表示过程激励噪声和观测噪声，Q和R分别是其服从的正态分布的参数；μk为控制函数，矩阵B表示控制输入μ∈ℜl的增益；矩阵A表示将上一时刻状态线性映射到当前时刻状态的增益；矩阵H表示状态变量xk对测量变量zk的增益。

根据卡尔曼滤波原理可以建立加速度信号的卡尔曼滤波模型。由于加速度信号为一维信号，并假设加速度信号间是相互独立的，可以将式（2）和（3）简化为如下形式：

卡尔曼滤波过程包括两步：首先根据历史数据使用线性随机差分方程生成一个当前的预测值，然后根据观测值对预测值进行更新，并生成新的误差协方差。简化后的卡尔曼滤波模型如图5所示[24]。

Fig.5　Process of Kalman filter图5　卡尔曼滤波器原理

卡尔曼滤波在消减噪声和平滑数值方面具有非常好的效果，能够较好地还原加速度变化趋势，用于分析运动步态的周期性。从图6中可以看到，经过卡尔曼滤波后，噪声有了极大的收敛，显著提高了计步的准确性。

Fig.6　Signal after performing Kalman filter图6　卡尔曼滤波后的波形

2.3加速度差分

由图7单步的波形变化可知，单步的加速度变化[24]可分解为正向加速度变化和负向加速度变化，并对加速度变化趋势进行累加，当正向加速度变化量和负向加速度变化量都达到某个特定阈值后，即为完成一步。本文设定当加速度前向差分大于阈值T，正向差分累计量Din加1；当加速度逆向差分大于阈值，负向差分累计量Dde加1。具体公式如式（6）所示。

Fig.7　An example of state transitions during one step detection图7 单步的波形变化

其中，差分阈值T用来抑制缓慢噪声，最优值T通过数值实验选取。

2.4有限状态机

该有限状态机主要有S0、S1、S2这3个状态，分布如图7所示。S0表示平稳状态，即人开始行走和行走结束的状态；S1表示峰值状态，用户迈步，加速度达到了最大值；S2表示谷值状态，用户收脚，加速度减少到最小值。

为了描述该状态机流程，引入如下符号：

Thr：加速度起始阈值；

De_Thr：干扰阈值；

In_Peek_Thr：在一个采样周期内，正向加速度变化量能达到的最大值；

De_Peek_Thr：在一个采样周期内，负向加速度变化量能达到的最大值。

状态机流程图如图8所示，具体描述如下：

Fig.8　Flow chart ofAD-FSM图8AD-FSM流程图

开始在S0状态，当加速度小于Thr阈值后，进入S1峰检测状态，将Din和Dde置0。

在S1状态时，增加噪声屏蔽机制。当遇到噪声干扰时，因加速度波形会在极短的时间内剧烈波动，Dde会和Din一起增加，但因为De_Thr的值小于或等于In_Peek_Thr，所以Dde会首先满足De_Thr的条件，返回起始状态S0，重新开始检测，以此过滤异常数据。只有在正常步行下，Din增加至In_Peek_Thr同时Dde小于De_Thr，进入S2谷值检测状态。

在S2状态时，Dde增加至De_Peek_Thr，状态机返回S0状态，步数加1。

Fig.9　States ofAD-FSM under normal environment图9正常情况下的AD-FSM状态变化

图9和图10分别为正常步行和干扰条件下步行，加速度值与AD-FSM的状态机状态变化。从图9中可以看到，在未行走时段，状态机在S0状态与S1状态反复，并未进入S2状态。当用户开始行走，状态机从S0到S1至S2状态正常切换，完成计步。图10验证了AD-FSM在遇到异常干扰时，状态机由于S1的噪声检测机制，可以较好地过滤异常数据。

Fig.10　States ofAD-FSM under interference environment图10干扰情况下的AD-FSM状态变化

AD-FSM完整算法如下所示。

3　实验及结果分析

本文实验对算法阈值和算法性能进行分析。算法阈值实验使用剑桥大学[11]的数据集，该数据集由27个人，130次实验，6种摆放位置组成。通过该数据集对算法中使用到的阈值进行校准与分析。第二部分实验使用2台Android智能手机（MEIZU MX4/100 Hz，SAMSUNG N7100/100 Hz）和1个Fitbit智能手环，智能手机预装Noom Walk计步APP。

一般来讲，计步精度评估分为平均有向相对误差δ和平均相对误差ε，其计算公式如式（7）和式（8）所示。其中Cest(i)为算法对第i个样本得到的估算计步结果，Cgt(i)为算法对第i个样本得到的真实计步结果。平均有向相对误差δ反映阈值变化影响测量值与真实值的偏差程度，而平均相对误差ε衡量计步方案的精度。

3.1算法阈值分析

实验开始阶段，通过算法分析对各阈值进行初始化，初始值设置见表1。将数据集记录的数据输入到程序中，其他阈值保持初始值不变的情况下，多次改变设定值，通过对比实验结果，选取最优阈值。

Table 1　Initial value of thresholds表1 阈值设定初始值

3.1.1差分阈值

差分阈值T是判断加速度变化的标准，直接影响加速度差分累积量的结果。由图11中可以看出，当T=0.047时，平均相对误差最小。基于本文算法对T值进行如下分析：当T值设置得越大，Din和Dde的变化量就越小，加速度变化量就越难达到累计量，测量结果比实际数少，平均相对误差增大。T值设置得越小，Din和Dde的变化就越大，加速度变化量就越易达到累计量，测量结果比实际数多，平均相对误差也会增大。只有当T值设定在一个合理的范围内，平均相对误差才能达到最小值。

Fig.11　Relationship betweenTandε图11　T值与平均相对误差的关系

3.1.2加速度起始阈值

AD-FSM算法中状态机的Thr决定S0到S1的起始点，即Din起始累加位，由图7单步波形变化可以看出，Din的起始位应在9.0之上。图12的实验结果也证明了上述观点，当Thr=9.6时，状态机转换效果最好。

Fig.12　Relationship betweenThrandε图12　Thr值与平均相对误差的关系

3.1.3差分累计值

每个人的步频因身高、年龄、性别的不同而有所差异，本文假设最大步频SF为180 bpm，则单步周期Cs，由式（9）计算出为1/3 s。峰值In_Peek_Thr和谷值De_Peek_Thr为加速度变化量最大值，当加速度变化量全为正或负时，加速度变化量最大值等于一个步频内采样点总数，则由式（10）计算可得In_Peek_ Thr=De_Peek_Thr=8。

当干扰屏蔽阈值De_Thr设置较小时，因无法过滤噪声干扰，造成检测结果偏大；设置较大时，则因过滤正常值，造成检测结果偏小。

分析表2实验结果，验证由公式计算得到的In_ Peek_Thr和De_Peek_Thr为最优累计值，且De_Thr等于3时，平均相对误差和平均有向相对误差最小。当De_Thr大于3时，检测结果偏大，反之，检测结果偏小，验证以上分析。

Table 2　Relationship between Peek_Thr, De_Thr andε,δ表2　Peek_Thr、De_Thr与平均相对误差、平均有向相对误差的关系

分析以上实验结果，不合适的阈值可能会导致以下两种现象：无法过滤噪声干扰和有些区段或被遗漏，这都会影响计步结果的精确度。基于测试结果，认定以下数值：当SAF=5时，T=0.047，Thr=9.6，In_Peek_Thr=8，De_Peek_Thr=8，De_Thr=3。在计步时，根据用户步态自适应地分配阈值，是有可能实现的，也是将来的工作。

3.2算法性能分析

Noom Walk APP、Fitbit手环和Android传感器API提供的Step Counter传感器，是目前市场上几类成熟的计步方法。Noom Walk是当前Android应用市场下载量居首的计步软件。Fitbit手环是一款内置计步功能的可穿戴健康腕带。Android系统提供的Step Counter传感器，供开发者多在非计步器APP中使用。

本实验环节共有7名测试者（4男3女）参与，每名测试者在实验过程中携带两部相同的手机和佩戴运动手环，分别标记为主机和副机。要求每名测试者分别进行4组不同步数和不同测试场景的测试。

该实验阶段共分为两种情况：首先分析在正常行走条件下，计步算法的准确性和稳定性；然后通过分析在干扰情况下的计步结果来验证计步算法的鲁棒性。

3.2.1正常情况下步行

表3为在不同步数情况下，各计步方案的平均相对误差结果。由表3结果可以看出，在步数为17时，其误差率在5%左右。当步数为500时，大部分计步算法误差率低于1%。Noom Walk APP和Android Step Counter检测步数的敏感性较低。因此，在大多数情况下，两者计步结果往往小于实际步数。同时，Fitbit、UPTIME和Modified FSM-Based方法具有较高的敏感性，但是一个微小的晃动（上或下）可能会导致其计步。

实验表明，数据量越大，提供的有效信息越多，计步算法的准确度越高。本文算法的平均误差在1.12%，优于其他方案。实验对比所用到的计步方案平均误差在2.80%，说明大部分计步方案在只包含静止和走路的正常活动中可以可靠地进行计步。

Table 3　Performance of step detection algorithms under normal environment表3　正常行走几种计步方案的平均相对误差结果对比

3.2.2干扰情况下步行

接下来，测试人员在以下干扰环境下行走并采集数据：

场景1行走过程中，手持采集设备行走100步，采集其间晃动手机进行干扰；

场景2手持采集设备行走100步，采集其间来电震动10 s进行干扰；

场景3手机置于桌子，来电震动10 s干扰；

场景4手动晃动采集设备10 s。

表4为在不同测试场景下，各计步方案的平均计步结果，其中数值均为步数。

分析实验结果，在场景1中，运动造成的干扰对其他计步方案均有影响，且未考虑干扰情况的FSM算法计步结果较差；在场景2和场景3中，Noom Walk、Android Step Counter和AD-FSM均能够屏蔽噪声的干扰；但在场景4中，只有本文AD-FSM算法能够很好地屏蔽干扰。

由表3和表4的对比结果来看，本文算法在两种情况下的计步结果更加逼近真值，误差率均小于平均误值，反映出本文算法的稳定性和健壮性。

4　结束语

对已有计步算法实验分析可知，阈值设定和抗干扰处理能力都会影响计步精度，而现有算法很少关注这一问题。对此，本文使用加速度差分作为特征的有限状态机计步算法进行计步检测。首先通过对原始加速度平方和求值，使算法结果与手机摆放方向无关，然后利用卡尔曼滤波去除噪声干扰。最后，使用基于加速度差分的有限状态机进行计步检测。实验结果表明，当用户以常规方式进行步数检测时，所设计的方案优于其他方案，但差别不大。在数据采集遇到人为或意外干扰情况下，本文方案较其他方案有着极大的准确度优势。本文计步算法结合运动状态分析动态调整阈值，并融合方向等其他数据进行室内定位系统的开发，也是下一步的研究方向。

Table 4　Performance of step detection algorithms under interference environments表4　干扰条件下几种计步方案的计步结果对比

References:

[1]Cayir Y,Aslan S M,Akturk Z.The effect of pedometer use on physical activity and body weight in obese women[J]. European Journal of Sport Science,2015,15(4):351-356.

[2]Wu Nan,Wang Xudong,Hu Qingqing,et al.Multiple LED based high accuracy indoor visible light positioning scheme [J].Journal of Electronics and Information Technology,2015, 37(3):727-732.

[3]Harle R.A survey of indoor inertial positioning systems for pedestrians[J].IEEE Communications Surveys&Tutorials, 2013,15(3):1281-1293.

[4]Youssef M,Yosef M A,El-Derini M.GAC:energy-efficient hybrid GPS-accelerometer-compass GSM localization[C]// Proceedings of the 2010 IEEE Global Telecommunications Conference,Miami,USA,Dec 6-10,2010.Piscataway,USA: IEEE,2010:1-5.

[5]Constandache I,Choudhury R R,Rhee I.Towards mobile phone localization without war-driving[C]//Proceedings of the 2010 International Conference on Computer Communications,San Diego,USA,Mar 14-19,2010.Piscataway,USA: IEEE,2010:1-9.

[6]Li Fan,Zhao Chunshui,Ding Guanzhong,et al.A reliable and accurate indoor localization method using phone inertial sensors[C]//Proceedings of the 2012 ACM Conference on Ubiquitous Computing,Pittsburgh,USA,Sep 5-8,2012. New York,USA:ACM,2012:421-430.

[7]Ojeda L,Borenstein J.Personal dead-reckoning system for GPS-denied environments[C]//Proceedings of the 2007 IEEE International Workshop on Safety,Security and Rescue Robotics,Roma,Sep 27-29,2007.Piscataway,USA:IEEE,2007:1-6.

[8]Shih W Y,Chen L Y,Lan K C.Estimating walking distance with a smart phone[C]//Proceedings of the 2012 5th International Symposium on Parallel Architectures,Algorithms and Programming,Taipei,China,Dec 17-20,2012.Piscataway, USA:IEEE,2012:166-171.

[9]Subramanian S P,Sommer J,Zeh F P,et al.PBIL PDR for scalable bluetooth indoor localization[C]//Proceedings of the 2009 3rd International Conference on Next Generation Mobile Applications,Services and Technologies,Cardiff,UK, Sep 15-18,2009.Piscataway,USA:IEEE,2009:170-175.

[10]Zhao N.Full-featured pedometer design realized with 3-axis digital accelerometer[J].Analog Dialogue,2010,44(6):1-5.

[11]Brajdic A,Harle R.Walk detection and step counting on unconstrained smartphones[C]//Proceedings of the 2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing,Zurich,Switzerland,Sep 8-12,2013.New York, USA:ACM,2013:225-234.

[12]Jimenez A R,Seco F,Prieto C,et al.A comparison of pedestrian dead-reckoning algorithms using a low-cost MEMS IMU[C]//Proceedings of the 2009 IEEE International Symposium on Intelligent Signal Processing,Budapest,Hungary, Aug 26-28,2009.Piscataway,USA:IEEE,2009:37-42.

[13]Oner M,Pulcifer-Stump J A,Seeling P,et al.Towards the run and walk activity classification through step detection—an Android application[C]//Annual International Conference of the IEEE Engineering in Medicine and Biology Society, San Diego,USA,2012:1980-1983.

[14]Hu Weiya,Lu Jialiang,Jiang Sheng,et al.WiBEST:a hybrid personal indoor positioning system[C]//Proceedings of the 2013 IEEE Wireless Communications and Networking Conference,Shanghai,China,Apr 7-10,2013.Piscataway,USA: IEEE,2013:2149-2154.

[15]Jang H J,Kim J W,Hwang D H.Robust step detection method for pedestrian navigation systems[J].ElectronicsLetters,2007,43(14):749-751.

[16]Beauregard S,Haas H.Pedestrian dead reckoning:a basis for personal positioning[C]//Proceedings of the 3rd Workshop on Positioning,Navigation and Communication,Hannover,Germany,Mar 16,2006:27-35.

[17]Wang He,Sen S,Elgohary A,et al.No need to war-drive: unsupervised indoor localization[C]//Proceedings of the 10th International Conference on Mobile Systems,Applications,and Services,Low Wood Bay,UK,Jun 25-29,2012. New York,USA:ACM,2012:197-210.

[18]Lan K C,Shih W Y.Using simple harmonic motion to estimate walking distance for waist-mounted PDR[C]//Proceedings of the 2012 IEEE Wireless Communications and Networking Conference,Shanghai,China,Apr 1-4,2012. Piscataway,USA:IEEE,2012:2445-2450.

[19]Lo C C,Chiu C P,Tseng Y C,et al.A walking velocity update technique for pedestrian dead-reckoning applications [C]//Proceedings of the 2011 IEEE 22nd International Symposium on Personal,Indoor and Mobile Radio Communications,Toronto,Canada,Sep 11-14,2011.Piscataway,USA: IEEE,2011:1249-1253.

[20]Gu Yang,Song Qian,Li Yanghuan,et al.A particle filter method for pedestrian navigation using foot-mounted inertial sensors[J].Journal of Electronics&Information Technology,2015,37(2):484-488.

[21]Pan M S,Lin H W.A step counting algorithm for smartphone users:design and implementation[J].IEEE Sensors Journal,2015,15(4):2296-2305.

[22]Alzantot M,Youssef M.UPTIME:ubiquitous pedestrian tracking using mobile phones[C]//Proceedings of the 2012 Wireless Communications and Networking Conference, Shanghai,China,Apr 1-4,2012.Piscataway,USA:IEEE,2012: 3204-3209.

[23]Yim J.A smartphone indoor positioning method[J].International Journal of Smart Home,2013,7(5):9-18.

[24]Welch G,Bishop G.An introduction to the Kalman filter, TR 95-041[R].University of North Carolina at Chapel Hill, 1995.

附中文参考文献：

[2]吴楠,王旭东,胡晴晴,等.基于多LED的高精度室内可见光定位方法[J].电子与信息学报,2015,37(3):727-732.

[20]谷阳,宋千,李杨寰,等.基于惯性鞋载传感器的人员自主定位粒子滤波方法[J].电子与信息学报,2015,37(2):484-488.

WANG Gechao was born in 1990.He is an M.S.candidate at Jiangnan University,and the member of CCF.His research interests include wireless sensor networks and indoor location,etc.

王革超（1990—），男，河南郑州人，江南大学硕士研究生，CCF会员，主要研究领域为无线传感器网络，室内定位等。

LIANG Jiuzhen was born in 1968.He is a professor and M.S.supervisor at Jiangnan University,and the senior member of CCF.His research interests include artificial intelligence and pattern recognition,etc.

梁久祯（1968—），男，山东泰安人，江南大学教授、硕士生导师，CCF高级会员，主要研究领域为人工智能，模式识别等。

CHEN Jing was born in 1977.She is a lecturer at Jiangnan University,and the member of CCF.Her research interests include wireless sensor networks and bioinformatics,etc.

陈璟（1977—），女，工学博士，江南大学讲师，CCF会员，主要研究领域为无线传感器网络，生物信息学等。

ZHU Xiangjun was born in 1991.He is an M.S.candidate at Jiangnan University,and the member of CCF.His research interests include wireless sensor networks and indoor location,etc.

朱向军（1991—），男，江苏徐州人，江南大学硕士研究生，CCF会员，主要研究领域为无线传感器网络，室内定位等。

*The National Natural Science Foundation of China under Grant Nos.61170121,71503103(国家自然科学基金). Received 2015-10,Accepted 2016-01.

CNKI网络优先出版:2016-01-04,http://www.cnki.net/kcms/detail/11.5602.TP.20160104.0953.004.html

文献标志码：A

中图分类号：TP212

doi:10.3778/j.issn.1673-9418.1510006

Step Counting Algorithm Based on Finite State Machine Using Acceleration Differentialƽ

WANG Gechao+,LIANG Jiuzhen,CHEN Jing,ZHU Xiangjun
School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China +Corresponding author:E-mail:wanggechao@gmail.com

Abstract:In the application of step counting,how to keep the stability and accuracy of step counting algorithm is a challenging problem.The traditional approach using fixed thresholds and peak detection can not solve the problem of stability and adaptability.In response to these problems,this paper proposes a step counting algorithm based on finite state machine using acceleration differential as a feature(AD-FSM).Firstly,AD-FSM uses the sum of squared acceleration to orientation-independent and applies Kalman filtering to eliminate noise.Then,AD-FSM counts steps by finite state machine.The experimental results show that the proposed algorithm can provide accurate counting results in the normal and interference situations,the errors are only 1.12%and 4.00%.This highlights the ability of the proposed algorithm to provide stability,robustness,and efficient counting in complex scenarios with fewer complications.

Key words:indoor location;step counting;anti-interference;finite state machine;acceleration differential