高宏-感知大数据获取与计算42

感知大数据获取与计算高宏哈尔滨工业大学CNCC2014大数据高峰论坛二零一四年十月二十三日报告内容一、无线传感网应用广泛二、感知大数据处理困难三、一些探索及部分结果无线传感网无线传感网应用广泛智能尘埃：监控敌人活动环境/灾害监测煤矿监测：地下矿井监测与导航系统海洋监测：海底泥沙堆积监测系统智能交通智能医疗与健康监护智能建筑建筑健康监测飞机引擎监测感知大数据处理困难随着新型传感器节点的出现及传感网研究的深入，传感网应用逐渐呈现规模化：感知节点千万级以上多样化：感知内容、形式多种多样复杂化：环境复杂、网络异构感知大数据处理困难例如：智慧城市、智慧国家城市拥有海量的传感器，路的、水的、电的、空气质量以及个人等方面的传感器例如，在路灯内加装多个传感器，可以监测城市的空气质量温湿度、风力、噪声分贝等，还可以计算周围人流量移动健康监测：牙齿内嵌传感器、皮下血液测试传感器感知大数据处理困难1.变化频繁传感网中的感知数据每秒发生成千上万次变化，其变化频率远远超出查询的变化频率。2.模态多样感知数据的类型越来越丰富，既包含温度、湿度、光强等标量型感知数据，也包括速度、加速度等矢量数据=nxxx21x=mnmmnnyyyyyyyyy212222111211Y感知大数据特点感知大数据处理困难不精确低精度传感器及环境干扰造成感知数据不精确。不完整传感器采样频率有限、传感器节点失效率高、数据丢失率高，故无法在任意时刻获得全部传感器节点的实时感知数据。不一致传感网的异构性和部署环境的复杂性造成大量感知数据不一致。不及时大规模传感网数据传输延迟较大，很多感知数据是过时的。22.3℃23℃22.5℃24.5℃23℃NULL23℃失效不一致0t5t+5感知大数据特点3.质量低劣挑战问题挑战问题1：如何高效处理数量大、速度快、变化频的感知数据？研究问题：频繁变化感知数据的高精度获取满足给定时间约束的感知数据获取与计算支持TB/PB量感知数据的高效计算研究问题：多模态感知数据的表示多模态感知数据的存储以多模态感知数据为输入，求解各种查询、分析与挖掘问题的算法设计与分析挑战问题挑战问题2：如何支持多模态感知数据融合计算？=nxxx21x=mnmmnnyyyyyyyyy212222111211Y研究问题：如何自动发现并修复感知数据中各种错误，使之成为正确的数据,支持精确计算；如果错误不能被完全发现并修复，则数据变为弱可用数据，如何在其上执行满足误差要求的近似计算。挑战问题挑战问题3：如何支持低质量感知数据上高效计算？报告内容一、无线传感网应用广泛二、感知大数据处理困难三、一些探索及部分结果感知大数据传输获取计算存储研究工作传输计算存储研究工作支持物理世界精准重现的数据获取理论与算法；面向多应用的数据获取的理论和方法;基于样条函数、小波、分段线性近似的压缩算法;同时考虑链路质量和时延的实时数据获取方法；低占空比WSN中实时数据传输方法具有通信延迟约束的强连通广播树构造算法基于模型的自适应数据感知方法;提高可靠性的多路径路由算法具有抗攻击能力和容错的安全路由算法确保跟踪信息高质量感知的节点选择算法;……获取感知大数据计算存储研究工作获取传输感知大数据最大化流量的异构多通信网络优化组网技术;通信网络多任务调度的理论与算法;通信网络的聚集计算调度的理论与算法;保证加权公平性的网络拥塞控制理论与算法;基于图的通信网行为监控的理论与算法；最小化失败概率的数据包传输方法;支持无线传感网远程重编程的数据发布方法;通信网络中的可信节点定位方法支持实时数据处理的实时路由算法实时低能耗广播树构造算法支持与节点ID无关查询的地理路由算法具有抗攻击能力和容错的安全路由算法分布式单向链路检测和路由算法……传输计算研究工作获取存储感知大数据基于随机图的数据整合与分布式存储方法;支持多粒度查询的数据自适应存储方法;基于样条函数、小波、分段线性近似的压缩算法;基于圆形区域的节点群存储方法基于环的分布式负载平衡数据存储方法“多版本”感知数据分布式存储方法稀疏感知数据的分布式索引技术基于时间的感知数据分布式索引技术……获取传输存储研究工作计算感知大数据WSN中主数据获取与计算地理位置敏感的近似极值点查询；多对象近似计数查询基于模型拟合的可信近似查询处理算法传感器网络中奇异点发现算法(ε,δ)-近似聚集和加权聚集查询处理ε-近似聚集查询模式;Top-k、Join等感知数据查询的理论和算法;在不确定性WSN系统中跟踪目标的算法;基于模式匹配与多节点相关分析的事件检测；网内极值区域查询处理算法感知数据探测查询处理算法感知数据缺失值估计方法不确定网络拓扑图挖掘算法……多模态感知数据融合计算基于多模态感知数据的事件融合模型；基于多模态事件模型的节点最优覆盖;基于多模态模型的事件感知与检测算法;……弱可用感知数据计算量质融合的感知数据模型不一致数据的错误发现与修复方法；数据时效性错误发现与修复方法；基于区间集的不完整数据上的分类算法;基于信息论的不完整数据上的分类算法；噪声数据上的分类算法；……部分研究结果(一)支持物理过程高精度重现的数据获取与计算Why？支持物理过程高精度重现的数据获取连续过程离散化网内数据计算都可能产生误差！！现有绝大多数感知数据计算方法：1.仅考虑第二阶段的误差2.均假设等频数据采集可精确地描述物理过程等频数据采集可准确描述物理过程吗？问题？曲线失真，大量关键点丢失！支持物理过程高精度重现的数据获取加大等频数据采集的频率可行吗？问题？加大数据采集频率意味着：1.消耗更多的能量2.产生庞大的感知数据3.加重数据存储与传输的负担变频数据采集是否可行？支持物理过程高精度重现的数据获取基于变频采样的O(ε)-可近似的感知数据获取真实物理过程曲线近似物理过程(感知)曲线支持物理过程高精度重现的数据获取基于Hermit插值的变频数据采集算法将时间轴分成时间区间在每个区间内调整采样频率基于三次样条插值的变频数据采集算法思想：一段时间调整一次数据采集频率若干时间区间构成一个时间窗口一个时间窗口内进行等频采样，不同窗口间调整采样频率…两种数据采集算法：…H-Based算法S-Based算法输出曲线的光滑度一阶光滑、二阶间断点多一阶光滑、二阶间断点少一阶导数误差二阶导数误差数据采集次数计算复杂度H-based算法S-Based算法精确度较高较低通信能耗较大较小计算量大计算量小理论分析结果实验结果部分研究结果(三)无线传感网ε-DominantDataset获取与计算Why？尽管感知数据的规模极其庞大，然而数据之间存在着极强的时空相关性冗余信息量大一个小数据子集即可保证携带整个数据集的主要信息DoMorewithLess!ε-DominantDataset获取与计算现有的DoMorewithLess方法SamplingbasedAlgorithms只能支持特定的简单计算(e.gaggregation.etc)无法恢复原始数据信息CompressionAlgorithms大多数分布式压缩方法仅考虑如何减少数据收集过程中的能耗需要解压才能进行计算增加额外开销TemporalandSpatial-CorrelationbasedAlgorithmsDataReductionAlgorithms数据信息不完整无法度量信息丢失率考虑新的DoMorewithLess途径，使其：既能够支持原始数据恢复，又能够支持无解压计算！ε-DominantDataset获取与计算ε-DominantDataset获取与计算关键问题？什么是关键数据集？如何定义和刻画？如何利用网络中感知节点的时空相关性来计算关键数据？节点数据变化频繁，如何低能耗地动态维护节点之间相关性？节点相关性随着感知数据流的变化而变化RawSensoryData可能是不同量纲的如何分布式地解决第2、3问题？提出了ε-DominantDataset概念及其计算方法ε-DominantDataset获取与计算问题描述网络中n个感知节点，每个节点连续采集数据，假设任意滑动窗口[Tif,Tis]大小为m；节点i在第w个滑动窗口内采集的数据记为：Si(w)=(Sit1(w),Sit2(w),……,Sitm(w))T所有节点在第w个滑动窗口内采集的数据记为：S(w)=(S1(w),S2(w),……,Sn(w))，S(w)是一个大小为m×n的矩阵。我们希望找到一个子空间[U1,U2,……,Up](p≪n)，使得S(w)投影到该空间后能够获得一个较小的数据集，同时最小化信息丢失率。ε-DominantDataset获取与计算问题定义目标：寻找ε-子空间及ε-主数据集合(任意ε=0)ε-DominantDataset获取与计算解决思路问题的难度？计算感知节点的相关系数矩阵C(w)计算相关系数矩阵的特征值及特征向量根据特征值和特征向量得到最小ε-子空间计算原始感知数据集在最小ε-子空间上的投影，得到最小ε-Dominantdatasetε-DominantDataset获取与计算理论结果与核心算法问题的难度证明了该问题是P问题解决该问题的时间下界为O(n3)相关系数矩阵的计算与维护基于滑动窗口的相关系数矩阵增量式维护算法基于抽样的相关系数矩阵近似计算算法ε-DominantDataset获取与计算理论结果与核心算法ε-主数据集中式获取与计算基于矩阵的特征值与特征向量计算方法所构建的优点：给出精确解，复杂度为O(n3)，主数据规模最小缺点：需要把网内任意两点的相关系数集中式的收集起来，能量消耗巨大ε-主数据分布式计算基于Lanczos方法所构建的优点：结果满足ε-主数据定义，复杂度为O(1)，主数据规模近似最优，能量消耗小ε-DominantDataset获取与计算部分实验结果主数据集合仅用了6.55%的数据量就能保证了原始数据集合所携带的95%信息能够保留.ε-DominantDataset获取与计算部分实验结果分布式算法所抽取的主数据集合大小十分接近最优部分研究结果(二)面向多应用共享的区间数据获取Why?面向多应用共享的区间数据获取收集数据进行多任务共享可以有效减少数据传输量，从而减少通信开销多应用共享的感知数据获取面向多应用共享的区间数据获取输入：n个任务T={T1,T2,…,Tn}，Ti=bi,ei,li，其中bi表示任务的起始时间，ei表示任务的终止时间，(bi,ei)表示采样窗口，li表示需要采集数据的时间长度，输出：任务Ti的数据采集时间区间Ii，使得采集数据的总时间长度最少，即：满足：面向多应用共享的区间数据获取多应用共享的感知数据获取问题问题复杂性：非线性非凸规划问题当结果取值为整数时，多应用共享的连续感知数据采集问题是非线性整数规划问题寻求近似的解法面向多应用共享的区间数据获取求解最优采集策略很难(非线性非凸问题)给出一个近似比为2的贪心算法当所有任务需要的数据采集时间相同可多项式时间求解给出一个动态规划算法求解最优解当数据采集任务陆续到达时给出三个在线算法面向多应用共享的区间数据获取li大小对采集数据量的影响较短采集长度较长采集长度谢谢！