面向海量物联网的数据处理技术.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date面向海量物联网的数据处理技术面向海量物联网的数据处理技术 数据库新技术课 程 报 告题 目： 面向物联网的海量数据处理研究 学 院： 数学与计算机科学学院 专 业： 计算机软件与理论 年 级： 2012级1班 学 号： 120320042 姓 名： 贾福运 成 绩： 摘要 物联网近年来受到人们的广泛关注 伴随各种感知技术的综合应用，物联网所处理的数据量较之以往的任何网络都巨大，呈现真正意义上的海量特征，如何高效 自动智能化地处理这些数据是物联网亟待解决的关键技术之一 提出一种基于多级数据处理的嵌入式中间件系统的体系结构，采用数据分级和分布式处理技术，实现实时信息处理的负载均衡，并提出当今流行的多种数据降维算法,从而尽可能多地保留原始信息的基础上，减少信息处理的数据量，从而提高物联网应用系统的整体效率.关键词：物联网；海量数据；分级处理；降维处理1 引言物联网(The Internet of Things，IoT)的概念是1999年提出的。简单来讲就是把各类物品通过射频识别(RFID)、传感器件与设备、全球定位系统等种种装置与互联网结合起来而形成一个巨大的网络，实现智能化的识别与管理，进而实现各类物品的远程感知和控制，由此生成一个更加智慧的生产和生活体系1根据丁明治,高需等人的分析, 物联网的以下4个特点对数据处理技术形成了巨大的挑战1：（1）首先物联网数据的海量性物联网系统通常包含着海量的传感器结点。其中，大部分传感器(如温度传感器、GPS传感器、压力传感器等)的采样数据是数值型的，但也有许多传感器的采样值是多媒体数据(如交通摄像头视频数据、音频传感器采样数据、遥感成像数据等)每一个传感器均频繁地产生新的采样数据，系统不仅需要存储这些采样数据的最新版本，且在多数情况下，还需要存储某个时间段(如1个月)内所有的历史采样值，以满足溯源处理和复杂数据分析的需要可以想象，上述数据是海量的，对它们的存储、传输、查询以及分析处理将是一个前所未有的挑战(2)传感器结点及采样数据的异构性在同一个物联网系统中，可以包含形形色色的传感器，如交通类传感器、水文类传感器、地质类传感器、气象类传感器、生物医学类传感器等，其中每一类传感器又包括诸多具体的传感器如交通类传感器可以细分为GPS传感器、RFID传感器、车牌识别传感器、电子照相身份识别传感器，交通流量传感器(红外、线圈、光学、视频传感器)、路况传感器、车况传感器等这些传感器不仅结构和功能不同，而且所采集的数据也是异构的这种异构性极大地提高了软件开发和数据处理的难度(3)物联网数据的时空相关性与普通互联网结点不同，物联网中的传感器结点普遍存在着空间和时间属性每个传感器结点都有地理位置，个数据采样值都有时间属性，而且许多传感器结点的地理位置还是随着时间的变化而连续移动的，如智能交通系统中，每个车辆安装了高精度的GPS或RFID标签，在交通网络中动态地移动与物联网数据的时空相关性相对应，物联网应用中对传感器数据的查询也并不仅仅局限于关键字查询很多时候，我们需要基于复杂的逻辑约束条件进行查询，如查询某个指定地理区域中所有地质类传感器在规定时间段内所采集的数据，并对它们进行统计分析由此可见，对物联网数据的空间与时间属性进行智能化的管理与分析处理是至关重要的(4)物联网数据的序列性与动态流式特性在物联网系统中，要查询某个监控对象在某一时刻的物理状态是不能简单地通过对时间点的关键字匹配来完成的，这是因为采样过程是间断进行的，查询时间与某个采样时间正好匹配的概率极低为了有效地进行查询处理，需要将同一个监控对象的历次采样数据组合成一个采样数据序列，并通过插值计算的方式得到监控对象在指定时刻的物理状态采样数据序列反映了监控对象的状态随时问变化的完整过程，因此包含比单个采样值丰富得多的信息此外，采样数据序列表现出明显的动态流式特性随着新采样值的不断到来和过时采样值的不断淘汰，采样数据序列是不断的动态变化的针对物联网海量数据管理所面临的上述挑战，目前尚没有有效的解决方法.本文提出处理这些海量数据的两种方法：(1)对这些数据进行分级处理；（2）对这些数据进行降维处理.分级处理可以有效的减轻系统的负荷；降维处理可以有效的压缩数据量，并且降维处理是处理一些数据必须进行的步骤，降维处理已经在大规模的图像处理算法中得到应用.2 物联网的海量数据分级处理策略2.1 海量数据分级的必要性2010年JiKui Wang论证并提出了数据分级存储的必要性4.他认为：如左图所示，通常40%或者更多的企业数据是非活跃的，但是这些非活跃的数据却：（1） 消耗了昂贵的存储空间（2） 不得不如同活跃数据一样需要一些不必要管理，备份，复制等操作（3） 有严重的法律风险（4） 不得不在DR方案中进行一些不必要的恢复操作 由此，我们可以把2000年的292TB的总数据可以分为：（1）115TB的活跃数据（2）77TB的非活跃数据截止到2010年，JiKui Wang得出如下图所示的活跃数据与非活跃数据之间的关系：分级与具体的环境相关，比如说，它与下面的几个方面相关：（1） 服务属性质量，速率，可靠性（2） 分级可以被专业化，比如合规存档（3） 分级可以无硬盘存储，比如用CDR,磁带存储等如下图所示则很好地处理了数据分级处理问题：2.2 海量物联网数据分级处理2.2.1海量物联网数据分级模型海量物联网分级存储系统是针对基于服务需求和成本构建的层次存储系统。 它由具有不同性能、可用性和单位价格等指标的存储级别构成, 数据存放在不同的存储级别中(固态磁盘、光纤盘阵、IDE盘阵、SATA盘阵和磁带库)。该系统可满足海量数据存储的高性能、大容量和低成本等要求。分级存储系统的核心是数据迁移技术。该技术在不同存储层次之间迁移数据, 同时保证迁移过程中数据访问的一致性。数据迁移分为离线迁移和在线迁移两种。 离线迁移需要将应用停止服务后再进行迁移,它避免了迁移过程中对数据一致性的维护。由于目前企业级应用都要求7*24h在线, 离线迁移已不适合大规模存储系统的需要, 因此在线迁移成为迁移技术的研究热点. 目前, 已有的在线数据迁移技术都存在如下缺陷:（1）迁移条件缺乏自适应机制。一些分级存储系统的迁移策略是由管理员预先制定好的。如在生命周期管理的体系结构STEPS中,具体迁移策略由管理员手工设定,文件在创建时就按照一定的放置策略放入不同的存储池中, 在文件的生命周期内,由预先设定好的迁移策略将文件在不同存储池之间迁移。 该迁移方法简单易操作, 但不能很好地适应动态变化的负载。（2）迁移代价高。如基于Lustre的分级存储管，理系统中,文件从离线设备迁移到在线设备都是由访问缺失触发的, 因此造成一次访问缺失的代价很大,且不支持文件的在线迁移。 （3）传统的文件迁移方法的升级策略都是on-demand类型。如果被访问的文件没有在高端存储系统中命中，则将其从低端存储系统迁移到高端存储系统中。 该方法的缺点是没有考虑文件的其他信息,比如文件大小、访问间隔等,造成升级的文件过多。具有代表性的两种文件迁移为:(1)LRU(least-recently-used), 优先将最近最不常使用的文件进行替换。LRU的缺陷在于平等地对待全部文件，没有考虑到文件的大小而文件大小决定了文件的迁移代价。（2）GreedyDualSize,基于文件的recency,size和migrationcost对文件进行替换。该方式升级迁移的数据量大，而且文件升级前需要通过降级来替换文件，增加了文件访问响应时间。针对已有在线数据迁移技术存在的不足,清华大学敖莉，于得水等人提出了一种高效的数据迁移方法 CuteMig【2】,该方法采用基于升级成本和升级收益的文件分级策略, 动态地考虑了文件大小和文件访问频度,将升级成本与收益比值满足条件的文件进行迁移, 既保证了升级必要的热点文件达到较高的命中率，也解决on-demand升级方式迁移数据量大的问题。同时CuteMig采用基于剩余空间的文件自适应降级选择策略,根据高端存储系统的剩余空间情况主动地选取文件来降级,保证了高端存储系统中始终有剩余空间, 解决了传统替换策略在升级前必须先执行DEMOTE操作进行替换的问题。在CuteMig迁移方法的基础上,他们为一种物理数值模拟的海量数据存储, 设计并实现了一个分级存储系统TH-TS, 该系统基于并行文件系统PVFS2, 采用增量扫描的方式获取文件访问频度信息,建立升级和降级队列管理迁移任务, 减少了迁移决策的开销, 提高了系统的迁移效率. 评测结果表明, TH-TS可以根据文件访问频度在不同数据服务器之间有效地迁移数据,同时CuteMig迁移方法和传统迁移方法LRU和GreedyDualSize相比, 升级迁移量下降了32%和59%; 降级迁移量下降了47%和66%, 且CuteMig 的平均IPO响应时间比LRU最多可降低10%, 比GreedyDualSize最多可降低39%。THTS体系结构的硬件结构按功能划分，包括客户端，元数据服务器和数据服务器3部分，如图1所示：在图1中, 元数据服务器和客户端之间的通路称为元数据路径,数据服务器和客户端之间的通路称为数据路径.元数据服务器负责把位于不同数据服器上的数据文件组织成统一的文件系统视图,为客户端软件提供元数据操作服务, 同时执行文件扫描、数据分级、迁移决策和迁移速率控制等操作,实现对迁移操作的单点管理;数据服务器保存每个文件分片后的数据文件, 为客户端软件提供文件IPO操作,同时执行元数据服务器发来的文件迁移指令;文件系统客户端软件实现虚拟文件系统层和MPI-IO层的各种文件操作.THTS体系结构的软件体系结构包括3部分客户端软件,元数据服务器软件和数据服务器软件。客户端软件分为应用层、系统接口层、任务管理层和网络通信层。元数据服务器是整个TH-TS系统中负责迁移和数据管理的主控节点,其设计主要包括: 1)获取数据服务器的文件访问频度信息; 2)管理并调度迁移任务;3)与数据服务器交互来控制迁移的执行. 为了现以上功能, 元数据服务器软件设计了文件迁移决策模块,它包含了增量扫描器,文件访问表管理器以及迁移调度控制器3个子模块.数据服务器负责向客户端软件提供IPO服务记录数据文件的访问频度信息、执行元数据服务器发来的迁移请求. 数据服务器软件的设计主要包括:1) 数据分片. 为了提高IPO性能, 文件数据按照一定分片规则分布在不同数据服务器上. 数据服务器需要保证客户端软件和元数据服务器软件按照分布信息可以获取正确的数据.2) 记录数据文件的访问频度信息. 数据服务器软件需定时记录数据文件的访问频度信息, 并在收到元数据的扫描指令后把数据文件的访问频度信息返回给元数据服务器.3) 数据服务器不仅在收到元数据服务器的迁移指令后开始执行迁移, 而且还需把要迁移的数据文件写入目标数据服务器的数据文件中, 以完成迁移任务.为了实现以上3个技术点,数据服务器软件设计了数据分片策略、IPO记录模块和迁移执行模块来完成其功能2.2.2 CuteMig数据迁移分级存储系统中数据迁移是核心技术. 为提高分级存储系统的IPO性能,达到高的IPO命中率及少的数据迁移量, 我们设计了CuteMig数据迁移方法, 主要包括以下3种关键技术。2.2.2.1基于升级成本和升级收益的文件分级策略基于升级成本和升级收益的文件分级策略是根据文件大小和文件访问频度信息分别计算文件升级的成本和升级后的收益, 使用二者的比值对文件进行分级, 并根据文件分级结果决定是否对文件升级,以提高系统的整体性能.1) 文件升级的成本定义为升级需要传送的数据量:Cost = filesize (1)传送数据过程增大了高端和低端存储系统的IPO负载, 也通过竞争带宽资源增大了前端应用的响应时间, 文件越大迁移过程对前端应用的影响也越大.2) 文件升级后的收益定义为文件升级后被访问的吞吐率. 其计算过程包括如下两个步骤:步骤1. 计算文件的平均访问时间间隔:其中文件的当前访问间隔为current_interval = current _access_time- last_access_time. (3)式(2)中, 如果文件以前没有被访问过, 它的平均访问时间间隔INFINITE; 如果文件是第2次被访问, 将它的平均访问间隔就是当前访问间隔,否则按遗忘因子A将当前访问间隔和旧的平均访问间隔加权求和, 得到新的平均访问间隔. 该方法既考虑了文件当前的访问间隔,也通过遗忘因子A把文件过去的访问间隔信息反映到平均访问间隔中.步骤2. 计算文件的升级收益. 设access_num,access_bytes,filesize, avg_interval分别表示文件的总访问次数、总访问字节数、文件大小和文件的平均访问间隔, 文件升级后经过T时间的升级收益表示为（4）T/g_interval 表示文件在T 时间内的预期访问次数cess_bytes/ccess_num表示文件每次访问的平均字节数. 式(4)中升级收益是随着时间T 不断累积的, 因此平均收益为 由于access_num, access_bytes, avg_interval 都是文件的历史访问特征, 可近似认为文件的访问特征在短时间内不会发生变化, 因此Benef it 是根据文件历史访问特征预测的文件近期内的平均收益.为保证升级热点文件提高访问性能的同时, 尽量降低迁移的数据量, 我们使用迁移成本和收益的比值表示文件的迁移优先级MigLaziness, 即该优先级越小文件被升级的概率越大. 每当文件被访问, 即更新平均访问间隔、总访问大小、总访问字节数等迁移相关信息, 计算升级迁移的优先级值. 该值越小说明升级的成本越小, 而且升级后的收益越大, 如果文件的迁移优先级小于升级阈值, 即对该文件执行升级操作.2.2.2.2基于剩余空间的文件自适应降级选择策基于剩余空间的文件自适应降级选择策略根据文件的访问情况和高端存储设备的剩余空间, 主动地选择需要降级的文件, 以保证高端存储系统中始终有剩余空间. 该方法解决了传统替换策略在升级前必须先执行DEMOTE操作进行替换的问题.1) 维护一个LRU栈. 所有升级到高端存储系统上的文件都放入该LRU栈中. 每当高端存储系统上的文件访问完成后, 则将其放入LRU栈的MRU端, 同时检查LRU栈中LRU端的文件, 根据该文件的上次访问时间和当前时间来计算它的未访问时间2) 根据文件未访问时间与降级阈值的比值进行降级判断. 如果它的未访问时间大于降级阈值Demotion_threshold, 那么将其放入降级候选队列中, 由降级调度程序处理. 降级阈值在初始化时被赋值为初始值Init_demotion( 该值为可变参数) ,之后自适应地变化: 每当降级候选队列中的文件被访问, 把该文件重新放入LRU栈,同时把降级阈值设置为该文件的本次访问和上次访问的时间间隔, 作为对降级阈值的惩罚; 每当降级线程从降级候选队列中成功降级了一个文件, 把降级阈值设置为LRU栈中LRU端文件的未访问时间,为对降级阈值的奖励, 以使LRU栈中更多的文件进入到降级候选队列中来3) 降级频率. 如图5所示降级后候选队列保存了LRU栈中大于降级阈值的文件. 每隔时间T, 调度程序从降级候选队列的队首取出降级候选文件执行降级操作. T 的计算公式如下:式(7)中K是可调参数, f reeratio是高端存储系统的剩余空间占其总空间的例, 取值范围是 0, 1 ,因此T 的取值范围是 0, Demotion_threshold . 降级的频率根据Demotion_threshold和f reeratio 自适应化。因此该策略是一个反馈过程, 最终降级阈值和高端存储系统的剩余空间都会稳定在一个范围内。2.2.2.3 移调度控制为了避免迁移过程影响前端应用, TH-TS采用了迁移调度控制, 按照迁移目标的不同, 将迁移任务分为升级迁移和降级迁移, 并用双候选队列技术, 使用升和降级队列分别管理调度这两种迁移任务.这种迁移任务区分的方法保证了紧迫的升级任务可以迅速执行, 同时不紧迫的降级任务在负载较轻时才执行。TH-TS把迁移任务分成两类: 将数据从低端存储系统迁移到高端存储系统的过程称为升级迁移;将数据从高端存储系统迁移到低端存储系统的过程称为降级迁移. 这两类迁移的目标不同: 升级迁移是为了把热点数据迁移到高端存储系统中, 以提高系统的访问性能; 降级迁移是为了把非热点数据迁移到低端存储系统中, 以使高端存储系统拥有足够的剩余空间, 来保存后续可能升级的热点文件.3 海量物联网的降维处理随着物联网技术的应用，人们将会不分时间和地点，可以方便的获得大量的信息，人们获得的数据量将以指数形式快速增长，这些数据具有快速更新，数据维数更高，非结构化等特点。从大规模的海量数据发现和探索新的知识是人类获取信息的主要目标之一。 目前人们对这些数据的处理还没有形成相应的有效方法，传统的数据分析方法在处理这些数据集合时，往往效果并不好，甚至在某些情况下失效，蕴含在数据中的知识和规律我们无法得知，将会导致 数据灾难问题。因此人们就迫切希望去认识和探索这些数据之间的奥秘 如何能有效的利用这些高维数据是面临的基本问题。近年来, 数据降维在物联网海量数据领域起着越来越重要的作用。通过数据降维可以减轻维数灾难和高维空间中其他不相关属性,从而促进高维数据的分类、可视化及压缩。所谓数据降维是指通过线性或非线性映射将样本从高维空间映射到低维空间,从而获得高维数据的一个有意义的低维表示的过程。数据降维的数学描述如下: a)X= XiNi=1是D维空间中的一个样本集,Y= YINi=1是d(d< <D)维空间中的一个数据集; b)降维映射,M:X->Y, x->y=M(x), 称y为x的低维表示。目前，在很多情况下，首先将数据的维数将到一个合理的大小，同时尽可能多的保留原始的信息，然后再将降维处理后的数据送入信息处理系统，这样的做法是非常有用的 同时降维算法也是一些机器学习，数据挖掘方法的组成部分 对数据降维处理，结合一些具体的业务需求，是一个行之有效对海量数据进行处理的方法 降维算法主要分为线性降维算法和非线性降维算法 降维的实质就是寻找投影变换：从高维空间到低维空间变换 现在有一种最小量嵌入算法，在保持局部等距和角度不变的约束条件下，能很好的揭示数据内在的流形结构.针对海量物联网高维数据目前已经提出了许多降维方法, 主要包括主成分分析( PCA)、多维尺度分析(multidimensional scaling, MDS)以及近年来提出的基于流形学习的算法, 如Isomap、局部线性嵌入( LLE)、拉普拉斯特征映射( LaplacianEigenmaps)等。对现有的降维方法, 可以从不同角度进行分类。从待处理的数据的性质角度考虑可分为线性和非线性的;从算法执行的过程可分为基于特征值求解的方法和迭代方法;从几何结构的保留角度考虑可分为全局方法和局部方法。本文依据降维方法间的主要区别, 将现有的降维方法进行了系统的分类, 如图1所示,并对几种典型的线性和非线性降维方法进行了详细的阐述,最后对这些降维方法进行了系统的分析比较。3.1典型的降维方法3.1.1线性降维方法1) PCAPCA是通过对原始变量的相关矩阵或协方差矩阵内部结构的研究, 将多个变量转换为少数几个综合变量即主成分,从而达到降维目的的一种线性降维方法。这些主成分能够反映原始变量的绝大部分信息,它们通常表示为原始变量的线性组合。2)LDAFisher在1936年提出著名的Fisher准则, 对于二类(分别称为正类和负类)问题,希望投影后得到的y=wTx能够使得J(w)最大：其中: m1、m2分别是正、负样本在投影方向上的均值; ，是正、负样本在投影方向上方差。可将其推广到多类问题, 此时希望找到的优化方向是使得在低维空间中同类数据尽量靠近,而非同类数据尽量分离, 从而保留丰富的辨别信息, 使投影后的数据具有最大的可分性。3.1.2非线性降维方法1)核主成分分析(KPCA)核方法是一系列非线性数据处理技术的总称,它们的共同特征是这些数据处理方法均用到了核映射。近几年,使用核函数对线性方法的重建提出一些成功方法如支持向量机回归、核PCA、核Fisher分析等。核PCA是线性PCA的推广, 主要思想是把输入数据x经由一个非线性映射A(x)映射到特征空间F,然后在特征空间F上执行线性PCA。2)MDSMDS是保留数据点间相似性或距离的一种非线性降维方法。MDS可分为度量性MDS和非度量性MDS。度量MDS利用数据点间的距离或相似性获得数据的低维几何表示,而非度量MDS仅利用原始数据点间的顺序信息来获得其低维表示。前者将距离平方阵转换为内积阵,通过求内积阵的特征值和特征向量获取低维表示;后者采用迭代方法。3) IsomapTenenbaum等人提出的Isomap算法是对经典MDS的一种推广。但MDS是基于欧式距离的且没有考虑邻近数据点的分布。假如高维数据点分布或近似分布于一个弯曲的流形上, 如Swiss-roll数据集, MDS可能将两个数据点看做是近邻点, 然而它们沿着流形的距离要远远大于它们的输入距离。Isomap的基本思想是首先使用最近邻图中的最短路径得到近似的测地线距离(图2),代替不能表示内在流形结构的Eucl-idean距离, 然后应用MDS算法,进而发现嵌入在高维空间的低维坐标。测地线距离是两点之间沿着流形的距离.4)LLE局部线性嵌入( LLE)是与Isomap相似的一种局部降维方法。但与Isomap不同的是, Isomap中建立了数据点的邻接图表示, 而LLE只试图保留数据点的局部性质, 这使它对短环路问题没有Isomap敏感。此外, 局部性质的保留允许非凸流形的成功嵌入。其基本思想是假设每个数据点与它的邻近点位于流形的一个线性或近似线性区域中,将全局非线性转换为局部线性, 而相互重叠的局部邻域能够提供全局结构的信息。5)LaplacianEigenmapsLaplacian Eigenmaps是由Belki等人于2001年提出的。类似于LLE, Laplacian Eigenmaps也是通过保留流形的局部特性发现数据低维表示的一种数据降维方法。Laplacian Eigenmaps寻求一个能在平均意义下保持流形局部特性的映射, 而其局部特性基于每对邻近点间的距离。6)Local tangent space alignment(LTSA)2004年, 浙江大学的张振跃等人根据非线性流形的全局非线性结构来自于局部线性分析和局部线性信息的全局整合这一思想提出了局部切空间排( LTSA)算法。LTSA具体可概括为两点,即投影和整合。算法通过逼近每个样本点的切空间来构建低维流形的局部几何,观测数据点在局部切空间的投影获得局部低维坐标,交叠的局部低维坐标被局部仿射变换后获得全局低维嵌入坐标。4 小结物联网的大规模应用会产生海量的数据，为了减轻系统的负荷，可以对数据的分级处理和降维处理，本文提出了提出了一种基于数据分级处理的数据迁移的有效方案，从而提高数据处理的效率和准确性；智能化是物联网的一个特征，要使物联网充满智能，必须结合一些智能信息处理的方法进行应用层的设计，而降维处理是一些智能算法的必要步骤，本文详细给出了多种数据降维方法，我们可以根据不同的数据特点择优选用。这两种思路对解决大规模物联网应用中的数据处理问题具有一定意义。参考文献1丁志明，高需，面向物联网海量传感器采样数据管理的数据库集群系统框架，计算机学报，20122敖莉，于得水，舒继武，薛巍，一种海量数据分级存储系统TH-TS,计算机研究与发展，20113吴晓婷，闫德勤，数据降维方法分析与研究，计算机应用研究，20094 ILM_Tiered_Storage_and_the_Need_for_DATA_Classification EBPOL. USA: Storage Networking Industry Association, 2010-03-30.http: PPwww. snia. orgPaboutPresourcesPDMF-ILM_and Tiered_Storage_20060221. pdf -