2018, Vol. 39
移动无线传感器网络能够广泛应用于各类场合, 近些年倍受国内外关注.移动是移动无线传感器网络中节点的一个重要属性, 准确地对节点的运动轨迹进行预测, 能够为上层协议的设计提供基础.在过去的一段时间里, 国内外众多研究人员在移动无线传感器研究领域内进行了研究, 并形成了大量的研究成果:文献[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两个可能, 故分布方差S2=(v-(v+at))2=(at)2.
如果没有当前速度值和加速度值, 预测nt时刻后的速度取值问题则成为一个完全随机问题, 而获取当前速度值和加速度值后, 基于匀速运动和匀变速运动趋势[6], 可以对运动轨迹进行比较有效的预测.可知, vp~N(v, (at)2).
1.2 一步概率转移矩阵预测算法设计参数定义:vp为一步t后的预测速度；Xn为节点n与节点(n-1)之间出网位置的位移变化量, 则n为2, 3, …，N, 其中N为节点数；A为1×N的位移矩阵, 用于记录节点间相对位移.
vp服从高斯分布vp~N(v, (at)2), P{c < x≤d}=∫cfd(x)dx, 其中c, d为预测速度区间的下限与上限.根据标准高斯分布N(0, 12), 得
|
图 1 起始点在t时刻后的可能位置 Fig.1 Possible location of the starting point after the t moment |
Ps是一个1×N的矩阵, 其中Pi为从当前节点开始一步t后到达节点i的概率值;
L是一个1×N的矩阵, L∈R1×N, 其中Li如果为1, 代表当前在节点i的网络下, 为0则不在节点i的网络下;
PT是一个N×N矩阵, 为概率转移矩阵, 其中PT[i, j]的意义为当前运动状态下, 一步t后由节点i运动到节点j的概率值.如图 1中的例子，其结果为
|
其中，
|
马尔可夫链(Markov chain)描述了一种状态序列, 其每个状态值取决于前面有限个状态.故设随机序列{X(n), n=0, 1, 2，…}的离散状态空间为V, V即为本移动网络下可接入节点的集合.
|
(1) |
其中i，k为非负数, ni+k代表ni经过kt时刻后的状态, 则称{X(n), n=0, 1, 2, …}为马尔可夫链.由式(1)可知, 马尔可夫链对于预测未来k步后的状态, 即ni+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∈R1×N，Ti为T矩阵的第i个元素，用于暂存上一步的结果, 且由于选取的部分节点概率和不一定为1, 所以对暂存概率矩阵进行归一化处理, 作为下一步预测的基础.为了简化研究, 运动状态在预测过程中可认为不发生改变, 概率转移矩阵PT沿用上次即可[10].
当选取从m到n的节点区间时, 由于概率和不为1, 所以调整T矩阵节点概率值后, 得到贪心概率计算公式:
|
每步预测后需要调整当前位置矩阵与概率转移矩阵.当选取的时间序列和kt大于预测要求时长时, 预测结束.在取步长t足够小时, 在当前运动状态下加速度只能取0或a, 在运动趋势符合高斯分布的基础上, 计算出相应的概率转移矩阵, 以此完成MTPA算法的计算过程.上述计算过程描述了单步与k步预测运算规则，由单步预测方式扩展至任意的预测时长, 采用k步预测方式与马尔可夫链特性, 提出两个分支描述概率转移矩阵计算规则, 并由此计算出最终结果Ps.考虑到在MWSN中, 要求预测实时性, 即降低算法时间复杂度, 所以提出贪心MTPA算法, 采取少数几个绝对优势节点来代替全部状态的计算, 达到快速收敛的目的.
1.4 MTPA算法流程输入:
Location L；//位置记录矩阵
X∈R1×N; //可加入节点相对位移矩阵
n; //可加入节点个数
输出:
LOOP:
Result=Location×Probability; //矩阵乘法, 复杂度为O(n2).
IF t < Ts THEN
Set_Component(t);
//调整t=t+Δt, 找到概率绝对大的节点, 设置Location, v, 计算Probability
Change_X(); //调整当前位置与各节点距离
ELSE
RETURN Result;
ENDIF
ENDLOOP
e= deviation(); //到达Ts时段后与预测结果比较, 计算误差
2 实验评估与分析 2.1 实验环境及平台设定网络硬件平台由Sink节点、移动节点构成.
节点硬件配置为STM32F4系列的单片机+AT86rf233系列的射频芯片+ LSM6DS0加速度计.实验环境为走廊内多人测量.
2.2 实验设计节点按照直线排列, 共计5个节点, 排列方式如图 2所示, 其中X1=6 m, X2=6 m, X3=6 m, X4=6 m, 并规定由节点1向节点5运动为正方向.t取经验值为1 s, k取值从2至24, 取值间隔为2.
|
图 2 实验过程 Fig.2 Experiment process |
测试设计:测试人携带移动节点在5个sink节点间进行多次随机移动测试, 实验过程如图 2所示(节点未拍摄完全).
实验1:测试人速度1 m/s, 匀速运动(加速度为0 m/s2), 初始接入节点1.重复实验50次, 精度与时延取均值.
实验2:测试人速度1 m/s, 以加速度1 m/s2运动1 s后, 匀速运动, 初始接入节点2.重复实验50次, 精度与时延取均值.
实验3:测试人速度2 m/s, 以加速度-1 m/s2运动1 s后, 匀速运动, 初始接入节点4.重复实验50次, 精度与时延取均值.
预处理:为进一步减少运行时刻计算量, 可以将位置、速度、加速度分别取l个离散值, 由3个元素组合可以得到l3个概率转移矩阵, 运行时采取查表策略即可.
2.3 实验数据分析由图 3可知, 在跳数k较小的情况下, 可以看出预测性能明显好于随机预测, 预测结果达到理想水平, 随着k的增大, 预测时间的延长, 预测准确度趋近于随机预测, 预测结果不够理想, 和天气预报预测结果类似, 目前天气预报也只能比较准确地预测7 d的天气, 之后的预测结果无法达到要求, 符合预期结果.
|
图 3 准确率与k的关系 Fig.3 Relationship between accuracy and k |
由图 4可以看出, 时间延迟曲线主要影响因素为概率矩阵的乘法运算, 所以曲线与接入节点数N的时间复杂度近似符合O(N3), 节点较多的情况下, 预测延迟仍然较小, 对实验最终结果影响不明显.
|
图 4 时间延迟与可接入节点数关系 Fig.4 Relationship between time delay and AC count |
仿真实验基于NS2平台, 场景设定为30个节点, 随机放在长200 m的线段区域, 采用shadowing无线传播模型.设置初始速度为0, 考虑加速度与速度对算法运行性能的影响, 进行1 000次仿真实验取平均值.
在加速度服从高斯分布的情况下, 速度上下摆动, 测量速度与预测精度的关系, 见图 5.在实际情况中, 速度较大的情况下, 由于有减速趋势, 所以预测精度有所下降.
|
图 5 速度与预测精度 Fig.5 Velocity and prediction accuracy |
从图 6可以看出, 由于预测时与仿真时加速度拟合程度很高, 所以预测精度提升, 且精度也近似符合高斯分布.
|
图 6 加速度与预测精度 Fig.6 Acceleration and prediction accuracy |
本文提出一种基于加速度的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. ) |