朱剑, 李佳政
东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
收稿日期：2017-03-06
基金项目：中央高校基本科研业务费专项资金资助项目(N150404011)；教育部重大科技创新项目(N161608001)。
作者简介：朱剑(1981-)，男，江苏镇江人，东北大学讲师，博士。

摘要：在以往的移动无线传感器网络(mobile wireless sensor network, MWSN)中, 热点分配问题没有得到很好的解决, 网络利用率较低.通过预测移动节点的轨迹可以优化网络结构, 提出结合加速度进行轨迹预测的算法MTPA:首先对节点的运动状态进行建模; 其次建立了一步运动状态概率转移矩阵; 最后以马尔可夫链为基础设计多步概率转移矩阵计算算法.为了验证算法性能, 在STM32F407平台上进行了实验, 结果表明, MTPA算法相比于传统的匀速预测算法与频率统计算法, 预测准确度具有一定的优势, 相关研究成果可以为MWSN提供基础.
关键词：运动趋势马尔可夫链概率矩阵轨迹预测嵌入式
An Algorithm for Predicting Nodes Movement Based on Markov Chain in MWSN
ZHU Jian, LI Jia-zheng
School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: ZHU Jian, E-mail: zhujian@ise.neu.edu.cn
Abstract: In existing MWSN(mobile wireless sensor network), the problem of hot spot allocation was not solved well, and the utilization rate of network was low. It is possible to optimize the network structure by predicting the trajectory of mobile nodes. A trajectory prediction algorithm named MTPA combined with acceleration was proposed. Firstly, modeling the motion state of the node was established. Secondly, a step motion state probability transfer matrix was done. Finally, Markov chain based multi-step probabilistic transfer matrix algorithm was presented. In order to verify the performance of the algorithm, experiments were carried out on the STM32F407 platform, the experimental results show that comparing with traditional uniform prediction algorithms and frequency statistics algorithms, the prediction accuracy of MTPA has certain advantages, and relevant research results can be used in MWSN.
Key Words: movement trendMarkov chainprobability matrixtrajectory predictionembedded
移动无线传感器网络能够广泛应用于各类场合, 近些年倍受国内外关注.移动是移动无线传感器网络中节点的一个重要属性, 准确地对节点的运动轨迹进行预测, 能够为上层协议的设计提供基础.在过去的一段时间里, 国内外众多研究人员在移动无线传感器研究领域内进行了研究, 并形成了大量的研究成果:文献[1]提出了HAND4MAC算法, 即移动节点在多个sink节点之间进行网络切换, 通过发送数据量和接收数据量两个参数来判断是否需要切换网络, 解决了实时切换网络的问题; 文献[2]提出了MOO算法, 通过优化拓扑结构的方法, 以达到局部性能最优, 解决了网络生命周期与覆盖范围上的问题; 文献[3]在城市交通问题上, 对移动对象的位置进行有效预测, 提出结合交通网络特征与统计, 利用加权马尔可夫链轨迹预测解决未来位置预测的问题; 文献[4]提出了一种基于高斯混合模型的轨迹预测算法GMTD, 针对不同运行状态描述了未来所有可能运动轨迹的概率分布.
与之前研究不同, 本文从运动状态本身分析, 由于加速度是改变运动状态的重要参数, 如何利用加速度, 成为了本文算法的关键之处, 也是创新之处.基于此, 本文提出了一种基于马尔可夫链模型与加速度的算法模型MTPA(movement trajectory prediction by acceleration), 可以有效地预测运动轨迹.
1 MTPA算法设计1.1 基于高斯分布的节点运动状态建模MWSN中的轨迹预测主要与速度有关, 而速度影响因素单一, 根据中心极限定理, 加速度随机情况下, 速度分布能够与高斯分布模型很好地拟合^[5], 所以在解决实际问题中, 高斯模型得到广泛应用, 下面讨论所建立的高斯分布模型的相关参数.
1) 期望:预测模型关于当前速度v对称, 所以均值μ=v.
2) 方差:为了简化研究, 本文假设:当预测步长t选取足够小的情况下, 加速度的预测值只有0和当前加速度值a两个可能, 故分布方差S²=(v-(v+at))²=(at)².
如果没有当前速度值和加速度值, 预测nt时刻后的速度取值问题则成为一个完全随机问题, 而获取当前速度值和加速度值后, 基于匀速运动和匀变速运动趋势^[6], 可以对运动轨迹进行比较有效的预测.可知, v_p~N(v, (at)²).
1.2 一步概率转移矩阵预测算法设计参数定义:v_p为一步t后的预测速度；X_n为节点n与节点(n-1)之间出网位置的位移变化量, 则n为2, 3, …，N, 其中N为节点数；A为1×N的位移矩阵, 用于记录节点间相对位移.
v_p服从高斯分布v_p~N(v, (at)²), P{c < x≤d}=∫_cf^d(x)dx, 其中c, d为预测速度区间的下限与上限.根据标准高斯分布N(0, 1²), 得.网络切换的有效位移X应为已知量, 由位移与速度时间的公式, 其中，v为当前速度, 得, , c, d的值就是一步t后到达某一节点的速度范围^[7].图 1框内为当前人物所在位置, 那么t时刻后进入到节点2网络中的位移变化范围为X₁≤X≤(X₁+X₂), 则c, d的值分别为, , 则t时刻后到达节点2网络范围内的概率为.计算出t时刻后到达网络中各节点的概率, 结合当前位置矩阵, 就可以得出最终预测结果, 根据实际情况不断修正当前状态与预测结果.
图 1(Fig. 1)

图 1 起始点在t时刻后的可能位置Fig.1 Possible location of the starting point after the t moment

P_s是一个1×N的矩阵, 其中P_i为从当前节点开始一步t后到达节点i的概率值;
L是一个1×N的矩阵, L∈R^1×N, 其中L_i如果为1, 代表当前在节点i的网络下, 为0则不在节点i的网络下;
P_T是一个N×N矩阵, 为概率转移矩阵, 其中P_T[i, j]的意义为当前运动状态下, 一步t后由节点i运动到节点j的概率值.如图 1中的例子，其结果为
其中，
1.3 基于马尔可夫链的k步运动轨迹预测算法设计马尔可夫链(Markov chain)描述了一种状态序列, 其每个状态值取决于前面有限个状态.故设随机序列{X(n), n=0, 1, 2，…}的离散状态空间为V, V即为本移动网络下可接入节点的集合.

(1)

其中i，k为非负数, n_i+k代表n_i经过kt时刻后的状态, 则称{X(n), n=0, 1, 2, …}为马尔可夫链.由式(1)可知, 马尔可夫链对于预测未来k步后的状态, 即n_i+k只与当前节点的状态有关, 与之前的状态变换无关, 而在本实验研究的WMSN中, 移动节点的运动趋势也只与当前状态和加速度的变化量有关, 符合马尔可夫特性, 可以依照马尔可夫链建立数学模型对未来运动趋势进行预测.
在建立概率模型时, 预测步长t影响着预测的准确度^[8], 当t过大时, 加速度无法认为只取值0或a, 所以只能缩短t的长度.同时带来一个问题, 步长t如果小于预测要求时长时, 需要进行k步预测, 所以本文提出一种基于马尔可夫链的k步预测算法MTPA.对一步t后的运动状态可以认为有两种情况:
① 在k较小的情况下, 此时运动状态的起止点变化不明显, 可认为运动参数不变;
② 在k较大的情况下, 此时运动状态的起止点变化明显, 需要根据不同的运动物体的“速度-加速度”运动曲线来调整下一步预测的初始状态^[9], 包含速度、加速度的信息.
k步预测方法的缺陷是计算量过大, 由于每步计算都会产生(N+2)个状态, 则k步将产生(N+2)^k个状态, 移动传感器网络在接入节点比较多的情况下, 实时性完成得不够理想.由于运动因素影响单一, 所以下面结合高斯分布特性提出改进方案.如果能够恰当选取单步时长t, 使概率分布比较集中且k值不会过于大的情况下, 均值附近的速度预测概率相对于其他的速度值具有绝对概率优势, 在预测中占据主导作用, 所以提出一种贪婪算法, 对一个或多个节点进行取值预测, 可以减少每步预测后产生的状态数量, 从而减少计算量.
参数定义:T矩阵为1个1×N的矩阵, T∈R^1×N，T_i为T矩阵的第i个元素，用于暂存上一步的结果, 且由于选取的部分节点概率和不一定为1, 所以对暂存概率矩阵进行归一化处理, 作为下一步预测的基础.为了简化研究, 运动状态在预测过程中可认为不发生改变, 概率转移矩阵P_T沿用上次即可^[10].
当选取从m到n的节点区间时, 由于概率和不为1, 所以调整T矩阵节点概率值后, 得到贪心概率计算公式:
每步预测后需要调整当前位置矩阵与概率转移矩阵.当选取的时间序列和kt大于预测要求时长时, 预测结束.在取步长t足够小时, 在当前运动状态下加速度只能取0或a, 在运动趋势符合高斯分布的基础上, 计算出相应的概率转移矩阵, 以此完成MTPA算法的计算过程.上述计算过程描述了单步与k步预测运算规则，由单步预测方式扩展至任意的预测时长, 采用k步预测方式与马尔可夫链特性, 提出两个分支描述概率转移矩阵计算规则, 并由此计算出最终结果P_s.考虑到在MWSN中, 要求预测实时性, 即降低算法时间复杂度, 所以提出贪心MTPA算法, 采取少数几个绝对优势节点来代替全部状态的计算, 达到快速收敛的目的.
1.4 MTPA算法流程输入:
Location L；//位置记录矩阵
X∈R^1×N; //可加入节点相对位移矩阵
n; //可加入节点个数
输出:
LOOP:
Result=Location×Probability; //矩阵乘法, 复杂度为O(n²).
????IF t < T_s THEN
????????Set_Component(t);
????????//调整t=t+Δt, 找到概率绝对大的节点, 设置Location, v, 计算Probability
????????Change_X(); //调整当前位置与各节点距离
????ELSE
????????RETURN Result;
????ENDIF
ENDLOOP
e= deviation(); //到达T_s时段后与预测结果比较, 计算误差
2 实验评估与分析2.1 实验环境及平台设定网络硬件平台由Sink节点、移动节点构成.
节点硬件配置为STM32F4系列的单片机+AT86rf233系列的射频芯片+ LSM6DS0加速度计.实验环境为走廊内多人测量.
2.2 实验设计节点按照直线排列, 共计5个节点, 排列方式如图 2所示, 其中X₁=6 m, X₂=6 m, X₃=6 m, X₄=6 m, 并规定由节点1向节点5运动为正方向.t取经验值为1 s, k取值从2至24, 取值间隔为2.
图 2(Fig. 2)

图 2 实验过程Fig.2 Experiment process

测试设计:测试人携带移动节点在5个sink节点间进行多次随机移动测试, 实验过程如图 2所示(节点未拍摄完全).
实验1:测试人速度1 m/s, 匀速运动(加速度为0 m/s²), 初始接入节点1.重复实验50次, 精度与时延取均值.
实验2:测试人速度1 m/s, 以加速度1 m/s²运动1 s后, 匀速运动, 初始接入节点2.重复实验50次, 精度与时延取均值.
实验3:测试人速度2 m/s, 以加速度-1 m/s²运动1 s后, 匀速运动, 初始接入节点4.重复实验50次, 精度与时延取均值.
预处理:为进一步减少运行时刻计算量, 可以将位置、速度、加速度分别取l个离散值, 由3个元素组合可以得到l³个概率转移矩阵, 运行时采取查表策略即可.
2.3 实验数据分析由图 3可知, 在跳数k较小的情况下, 可以看出预测性能明显好于随机预测, 预测结果达到理想水平, 随着k的增大, 预测时间的延长, 预测准确度趋近于随机预测, 预测结果不够理想, 和天气预报预测结果类似, 目前天气预报也只能比较准确地预测7 d的天气, 之后的预测结果无法达到要求, 符合预期结果.
图 3(Fig. 3)

图 3 准确率与k的关系Fig.3 Relationship between accuracy and k

由图 4可以看出, 时间延迟曲线主要影响因素为概率矩阵的乘法运算, 所以曲线与接入节点数N的时间复杂度近似符合O(N³), 节点较多的情况下, 预测延迟仍然较小, 对实验最终结果影响不明显.
图 4(Fig. 4)

图 4 时间延迟与可接入节点数关系Fig.4 Relationship between time delay and AC count

2.4 性能仿真仿真实验基于NS2平台, 场景设定为30个节点, 随机放在长200 m的线段区域, 采用shadowing无线传播模型.设置初始速度为0, 考虑加速度与速度对算法运行性能的影响, 进行1 000次仿真实验取平均值.
在加速度服从高斯分布的情况下, 速度上下摆动, 测量速度与预测精度的关系, 见图 5.在实际情况中, 速度较大的情况下, 由于有减速趋势, 所以预测精度有所下降.
图 5(Fig. 5)

图 5 速度与预测精度Fig.5 Velocity and prediction accuracy

从图 6可以看出, 由于预测时与仿真时加速度拟合程度很高, 所以预测精度提升, 且精度也近似符合高斯分布.
图 6(Fig. 6)

图 6 加速度与预测精度Fig.6 Acceleration and prediction accuracy

3 结语本文提出一种基于加速度的MTPA轨迹预测算法, 主要解决了判断节点脱离网络与接入网络趋势的问题, 相比以往的算法具有准确度高、适应性强的优点, 并在相关嵌入式平台进行编程应用.研究成果能够为上层网络协议的设计提供基础, 在有限带宽内尽可能接入更多节点传输数据.今后的研究目标延伸为二维, 不仅结合加速度参数, 同时获取GPS等信息, 抽取移动特征, 考虑到多种复杂情形、热点放置覆盖范围等问题, 优化网络协议调整速度, 减少计算量.
参考文献

[1]	Caldeira J M L P, Rodrigues J J P C, Lorenz P. Mac layer handover mechanism for continuous communication support in healthcare mobile wireless sensor networks[J].Telecommunication Systems, 2015, 60(1): 119–132.DOI:10.1007/s11235-014-9926-z
[2]	Attea B A, Khalil E A, Cosar A. Multi-objective evolutionary routing protocol for efficient coverage in mobile sensor networks[J].Methodologies and Application, 2014, 19: 2983–2995.
[3]	彭曲, 丁治明, 郭黎敏. 基于马尔可夫链的轨迹预测[J].计算机科学, 2010, 37(8): 189–193. ( Peng Qu, Ding Zhi-ming, Guo Li-min. Trajectory prediction based on Markov chain[J].Computer Science, 2010, 37(8): 189–193.)
[4]	乔少杰, 金琨, 韩楠, 等. 一种基于高斯混合模型的轨迹预测算法[J].软件学报, 2015, 26(5): 1048–1063. ( Qiao Shao-jie, Jin Kun, Han Nan, et al. Trajectory prediction algorithm based on Gaussian mixture model[J].Journal of Software, 2015, 26(5): 1048–1063.)
[5]	Heo N, Varshney P K. A distributed self spreading algorithm for mobile wireless sensor networks[J].Wireless Communications and Networking, 2003(3): 1597–1602.
[6]	Fang W, Song X, Wu X, et al. Novel efficient deployment schemes for sensor coverage in mobile wireless sensor networks[J].Information Fusion, 2017, 41: 25–36.
[7]	Wu H, Wang J, Ananta R R, et al. Prediction based opportunistic routing for maritime search and rescue wireless sensor network[J].Journal of Parallel & Distributed Computing, 2017, 111: 56–64.
[8]	Azim A, Islam M M. A dynamic round-time based fixed low energy adaptive clustering hierarchy for wireless sensor networks[C]// IEEE 9th Malaysia International Conference on Communications. Kuala Lumpur, 2009: 922-926.
[9]	Sawant T, Sirsikar S. A comparative study of various routing technique for wireless sensor network with sink and node mobility[C]//Intelligent Communication and Computational Technologies. Singapore: Springer, 2018: 227-236.
[10]	乔少杰, 李天瑞, 韩楠, 等. 大数据环境下移动对象自适应轨迹预测模型[J].软件学报, 2015, 26(11): 2869–2883. ( Qiao Shao-jie, Li Tian-rui, Han Nan, et al. Self-adaptive trajectory prediction model for moving objects in big data environment[J].Journal of Software, 2015, 26(11): 2869–2883.)