传感器网络中频繁移动模式挖掘算法研究

Algorithm for Mining Frequent Moving Patterns in Sensor Networks

针对传感器网络中包括目标位置和时间的二维属性频繁移动模式挖掘问题,建立一种新的树状结构OMP-tree(OMP:Object Moving Pattern),OMP-tree可以压缩存储大量的原始移动模式.提出一种条件搜索算法,使用该算法可以大大减少满足条件的前缀模式数量.基于OMP-tree和条件搜索算法,设计一种新的挖掘目标的频繁移动模式的算法OMP-mine,该算法基于模式增长思想,直接递归地从条件模式基中得到频繁的前缀模式,然后连接后缀,达到模式增长的目的.仿真结果表明所提出的OMP-mine算法可以有效挖掘出传感器网络中具有二维属性的频繁的移动模式,并较好地降低了算法的时间和空间复杂度.

Aiming at the issue of mining frequent moving patterns with two dimensional attributes including locations and time in sensor networks, a novel algorithm named OMP-mine （OMP： Object Moving Pattern）is proposed in this paper, OMP-mine is based on a novel data structure named OMP-tree and a scheme of conditional search, which are also presented in the paper. The OMP-tree can efficiently store large numbers of original moving patterns compactly and the method of conditional search can efficiently narrow the search space. OMP-mine adopts the idea of pattern growth, recursively fetches frequent prefix patterns from the conditional pattern bases directly, and joins the suffix to make a pattern grow. Simulation results show OMP-mine can efficiently discover frequent moving patterns with two dimensional attributes in sensor networks and decreases its time complexity and space complexity simultaneously.