物联网环境下海量多源异构数据的存储算法

侯戌非

(铜陵职业技术学院 信息工程系，安徽 铜陵 244000)

物联网作为一种新型网络，利用通信网络的数据交互，可以实现智能识别、跟踪和监控，在制造业、工业和农业等领域得到了广泛应用[1-2].物联网环境下的数据具有多源异构、规模大和冗余度高等特点，当前物联网信息服务系统在多维数据查询和检索等方面获得一些研究成果，但处理海量多源异构数据时，仍然存在存储能耗大和耗时长等问题[3].在这种情况下，如何高效存储这些海量多源异构数据成为物联网领域亟待解决的重点问题[4].

为了提高海量多源异构数据存储质量，降低多源异构数据存储过程中系统的能量消耗，研究人员得出了一些研究成果.林志贵[5]提出一种新的蛇形时隙数据存储算法，该算法先确定待存储的数据优先级，依据优先级判断存储位置与查询节点网格的距离，定义节点存储阈值，确定数据存储时隙分配，当存储节点均达到阈值时，将该数据划分至与其相同优先级的邻域内.该算法可以解决网络节点能量不均问题，但当网络中的数据具有多源和异构特性，且数据量较大时，导致数据存储时间响应慢、占用内存空间较大.钱伟强[6]提出一种基于调度机制的数据存储算法，该算法利用周期性调度及梯度优化形式，且考虑到多源异构数据存储中最小传输粒度特征，对数据存储过程中的指纹梯度进行优化，并将其代入数据传输过程中，完成海量数据存储.该算法存储难以将重复的异构数据滤除，且存储过程中存在严重的负载不均衡问题.

在物联网环境下，针对当前海量多源异构数据存储方法存在的不足，提出一种基于多种群协同进化的海量多源异构数据存储算法.采用该算法有效节约了系统在存储处理海量多源异构数据时的内存空间，提高了负载均衡度.

1 基于多种群协同进化的海量多源异构数据存储算法

1.1 构建多源异构数据存储调度目标函数

建立多源异构数据副本模型，对网络中重复的数据构造数据指纹索引，搜索到重复的异构数据用布隆过滤器将重复的异构数据滤除，给出多源异构数据存储调度目标函数，将滤除后的数据存储任务调度问题抽象为最优解问题.

存储在物联网环境中的海量多源异构数据Cs都会被分解，以数据块的形式存储在表格table中，表格table可以跨多个网络服务器.设定由k个协调器构成的节点矩阵集群中，F表示节点矩阵集群中存储的某一个多源异构文件，bs表示多源异构数据集的大小，则F的大小为n×bs，F含有n×m个多源异构数据块存储在协调器中，可将Fn×m矩阵表征为异构数据文件的分块，用{b11,…,bn1}表示原始数据文件F的数据块，n表示文件的原始数据块，则该多源异构数据文件的副本可用矩阵Fn×(m-1)表示.

(1)

其中，bnm表示某一矩阵元素.当节点矩阵集群获得用户上传的海量多源异构数据时，多源异构数据块b11存储在表格table中，异构数据b12将作为b11的副本，存储在b11不同的备份服务器中，同样b12为b11的副本，也存储在与b12同类的机架，但是却在不同的备份服务器中，假设m为异构数据副本系数且满足m>3，则其他的多源异构数据块会存储至b11、b12和b13之外的备份服务器中.在数据存储节点矩阵中设定MD5索引[7]，重复查找当前内存中重复的多源异构数据，用布隆过滤器对这些重复数据过滤.

(2)

(3)

(4)

其中，nτ和mτ表示已覆盖的异构数据，τ∈u表示过滤强度.

设定多源异构数据文件冗余率为r%，通过公式(2)对重复覆盖的异构数据进行过滤，滤出的异构数据块大小为a，则滤出的多源异构数据所占的内存空间可利用下式表示.

(5)

假设，SUMOM表示物联网环境下内存存储的海量多源异构数据文件占有的内存空间，通过重复覆盖物联网环境下内存中存储的多源异构数据后，现有存储的多源异构数据文件所占有的内存空间SUMMem可利用下式表示为

(6)

(7)

其中，p(bais)表示系统存储区多源异构数据可用概率，QoSa表示该异构数据的可用性服务需求.

1.2 协同进化算法求解存储任务调度目标函数

采用协同进化算法求解公式(7)给出的目标函数，依据目标函数对数据存储任务数量进行编码，通过多次迭代求解获得最优解，编码过程如下.

编码采用自然数和长度完成海量多源异构数据存储子任务量，根据维度可计算出需要处理的异构数据存储任务数量.协同进化算法[9]种群进化过程中的粒子编码，主要针对待存储异构数据存储任务数量，Pj(j=1,2,…,k)用于描述某个微粒群，该群中含有的粒子数量为Xi.

Xi={ρj,xi1,…,xin},

(8)

其中，ρj表示Pj位置分量，xin用于描述微粒i在Pj处的位置分量，优胜阈Iij表示i，j相应的阈值.

Iij=[Iij,μij]={xij|lij≤xij≤μij,xij∈R},

(9)

其中，i表示微粒，j表示分量，Iij和μij分别用于描述阈值的上下界，在选取协同进化算法的种群适应度过程中，假设选取微粒i的阈值为Iij，该阈值Iij作用于μij，则可获得以下规则

(10)

(11)

(12)

(13)

完成协同进化算法个体评价后，采用优胜阈值[10]确定种群的每个子群是否发生突变，并在突变后接收新微粒，该微粒可取代迭代前的微粒，将这个过程表征为

(14)

假设，ETC表示海量多源异构数据存储子任务运行时间，ETC(τ,η)表示数据存储任务τ转向环区域η上存储数据消耗的时间，依据ETC即可在种群微粒解码过程中，求解获得完成数据存储调度任务耗费的时间，利用下式计算

(15)

全部的海量多源异构数据存储结束，即全部的网络环区域均结束了各自的多源异构数据存储任务，此时可计算获得全部海量多源异构数据存储所需时间，即

FTime(η)=maxETC(τ,η).

(16)

当种群内部所有微粒完成每次迭代后，会更新微粒当前搜索信息，最后对微粒群编码结果进行离散化处理，即

(17)

2 实验结果与分析

为了验证本文算法的有效性，仿真实验选择在MATLAB环境下进行，操作系统为CentOS6.5，Hadoop版本为2.6.0.为了评估所提基于协同进化的数据存储算法的存储性能，将其与基于存储阈值的数据存储算法以及基于海量存储云调度机制的数据存储算法进行仿真实验对比.物联网仿真时间为32 h，海量多源异构数据传输速率不低于4 M.不同传输速率下不同方法存储时间响应测试结果如图1所示.

图1 不同传输速率下不同方法存储时间响应测试

图1表示在数据存储节点功率不断提升的情况下，基于多种群协同进化的数据存储算法与对比算法存储时间响应(ms)的仿真结果.由图1可知，随着数据存储节点功率的不断增加，基于协同进化的数据存储算法与其他对照组算法的存储时间响应都呈现扩大的趋势，与其他算法相比，基于协同进化的数据存储算法的数据存储时间响应延迟增加幅度较小，始终比其他两种算法低.这是由于所提算法综合考虑了物联网环境下的海量多源异构数据的存储处理情况，可在数据存储节点功率不断增大的情况下，过滤出重复数据，具有更快的响应速度.基于存储阈值的数据存储算法以设定的数据存储阈值，决定是否执行下一次数据分配，一旦网络中的数据发生量突增情况，该算法无法动态更新存储阈值，导致数据存储时间响应慢.

针对不同数据存储算法对其负载均衡度进行对比，各个数据存储任务上的负载大小之和与总负载之比为负载均衡度(%).对比结果如表1所示，U、X、K分别表示基于协同进化的数据存储算法、基于存储阈值的数据存储算法以及基于海量存储云调度机制的数据存储算法.

表1 不同算法负载均衡度对比

分析表1可知，随着多源异构数据量的不断增加，3种算法相应的数据存储负载均衡度均呈上升趋势，当数据量为200 MB时，所提算法负载均衡度为42.58%，基于存储阈值的数据存储算法的负载均衡度为25.58%，基于海量存储云调度机制的数据存储算法的负载均衡度34.36%，所提算法相比两种算法分别提升了7%和8.22%.基于海量存储云调度机制的数据存储算法仅考虑到多源异构数据存储中最小传输粒度特征，没有考虑到重复的冗余数据对数据存储过程的影响，导致数据存储负载均衡度较低.

通过实验，获得不同存储算法占有的空间内存(KB)对比结果，如表2所示.U、X和K分别表示基于协同进化的数据存储算法、基于存储阈值的数据存储算法以及基于海量存储云调度机制的数据存储算法.

表2 不同算法存储占用的空间内存对比

分析表2可以看出，本文所提基于协同进化的数据存储算法在不同数据大小下，占用的空间内存相比其他两种算法较小，主要原因在于文中所提算法为了有效提升海量多源异构数据存储精度，采用协同进化算法，针对需要完成的多源异构数据任务数量进行粒子编码，通过多次迭代获取最优数据存储任务调度方案，使得所提算法拥有更好的负载均衡度.

3 结论

物联网环境下存在数据的多源、异构、冗余度高等特性，在此背景下，现行数据存储算法在进行数据存储过程中有占用内存空间大、负载不均衡、时间响应慢等不足.针对这些不足，提出一种基于协同进化的海量多源异构数据存储算法.将海量多源异构数据存储任务调度问题抽象为最优解问题，采用协同进化算法对微粒群进行迭代搜索，以最终获得的最优调度方案完成海量多源异构数据存储.经过实验验证，所提算法相比当前数据存储算法，在存储和处理海量多源异构数据时，响应速度更快，有效节省了系统的内存空间，提高了负载均衡度.