三维水声传感器网络中数据流的突发检测算法

摘 要：针对三维水声传感器网络中数据流突发检测的多源性和异质性，对描述突发异常的特征和属性进行形式化定义和建模；然后，提出一种基于进化博弈论的突发检测算法，通过滑动窗口大小的优化选择与配置提高突发检测模型的处理速度与检测性能。仿真实验结果表明，基于进化博弈论的突发检测算法在数据分布、突发概率或者最大滑动窗口大小相同的情况下，处理时间少于传统的突发检测算法。

关键词：

水声传感器网络；三维；进化博弈论；突发检测

中图分类号： TP393

文献标志码：A

Burst detection algorithm for data streams in

three dimensional under water acoustic sensor networks

XU Ming1， 2*，LIU Guang-zhong1

1.College of Information Engineering， Shanghai Maritime University，Shanghai 201306， China；

2.Shanghai Key Laboratory of Intelligent Information Processing， Fudan University，Shanghai 200433， China

Abstract：

Considering the multi-sourcing and heterogeneous data streams in three Dimensional UnderWater Acoustic Sensor Networks （3D UWASN）， this paper gave out a formalized definition and modeling for describing the characters and attributes of burst and presented an evolutionary game theory based burst detection algorithm for reducing processing time and improving detection performance through the optimization selection in the size of slide window. The simulations demonstrate that the burst detection algorithm consumes less processing time than traditional algorithms under the same conditions of data distribution， burst probability or maximum slide window size.

英文关键词　Key words：

UnderWater Acoustic Sensor Network （UWASN）； three dimensional； evolutionary game theory； burst detection

0 引言

水声传感器网络（UnderWater Acoustic Sensor Network，UWASN）接收到的数据是一组持续不断到达的、带有时间标签的元素序列，因此需要用数据流挖掘的方法进行处理。数据流的本质特征在于其变化性及不可预测性。作为数据流的一种基础且重要的数据分析方法，数据流突发检测能够及时检测到特定元素数量的异常变化，因此在许多领域有着广泛的应用，包括监测宇宙中高能光子伽玛射线的爆发、检测金融领域异常波动以及监控互联网中分布式拒绝服务攻击[1-3]。针对数据流中的突发检测问题，研究人员已经提出了一些方法：文献[4]采用偏移小波树（Shifted Wavelet Tree， SWT）来表示数据流滑动窗口中所有的元素，并解决弹性窗口问题，但是搜索效率有待提高；文献[5]通过偏移二叉树（Shifted Binary Tree， SBT）实现对数级复杂度内多滑动窗口数据流序列的突发检测；文献[6]提出一种偏移聚合树（Shifted Aggregation Tree， SAT）的数据结构，可以根据应用场景的不同灵活选择聚合塔的层数以及每层中子节点的个数，减少详细搜索的次数以降低时间复杂度；文献[7]提出了一种基于平均似然比的突发检测方法，该方法利用平均似然比对突发信号做贝叶斯检测，解决了以往提出的突发检测方法要求最佳定时采样的问题；文献[8]提出了一种聚合数据流中基于小波的突发检测算法，利用聚合向量对原始数据流的窗口和观测数据进行压缩处理；文献[9]分析了基于迁移小波树的突发检测算法，在突发定义的基础上，设定适当的阈值，并利用迁移小波树的结构，有效地定位突发。

然而，由于水声传感器网络自身的特殊性和局限性，使得水声传感器网络中数据流突发检测研究工作面临严峻的挑战。首先，声波在水中的传播速度比无线电波在空气中的传播速度低5个数量级，因此水声传感器网络数据传输效率低下的问题较为突出。其次，由于水声通信带宽窄，通信覆盖范围通常只有几百米至几千米，因此单个水声传感器网络的规模以及节点的数量都受到严格的限制。最后，水声传感器节点采集到的数据流逐渐呈现出多源性和异质性，主要表现在：第一，水声传感器网络的拓扑结构从静态二维网络发展到静态三维网络以及带有自主式水下航行器（Autonomous Underwater Vehicle，AUV）、无人水下潜航器（Unmanned Undersea Vehicles，UUV）的动态三维网络[10]。第二，水声传感器节点的功能也逐步从单一化向多样化方向发展，并且可以在一个水声传感器节点上同时使用多种类型的传感器来获取各种水下物理、化学和生物数据[11-12]。传统的数据流突发检测技术都是针对单一数据流设计单一突发检测算法来进行的，因此无法适用于水声传感器网络环境下多源异质数据流的突发检测。首先，由于无法预测突发时间的长短，因此在基于滑动窗口模型的突发检测中很难确定滑动窗口的大小以及同时对多个滑动窗口大小进行突发检测；其次，针对水声传感器网络中不同的应用场景需要采用相应的数据模型表示多源异质数据流以确保能够高效进行突发检测；最后，采用何种度量方式评估是否达到突发以及阈值的设定问题有待解决。进化博弈论（Evolutionary Game Theory， EGT）把一个静态的决策过程赋予了动态演变的思想，推动了生物进化理论的发展，并成为经济学、社会学以及计算机等学科中的一个重要理论技术[13]。本文针对水声传感器网络中多源异质数据流的特性提出一种基于进化博弈论的突发检测算法，通过滑动窗口大小的优化选择与配置提高突发检测模型的处理速度与检测性能。