更新时间：2023-10-22 23:08
更新算法，是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制的陈旧布新。(如不合格，请明确指出参考文献的哪里不合适，并请您提供有效的参考文献进行佐证)
安全性是移动自组网络组通信的基本需求，安全、高效的组密钥更新算法是保证组通信安全的关键。在移动自组网络分布式组密钥管理框架(distributed group key management framework，简称DGKMF)的基础上，提出了一种组密钥更新算法——DGR(distributed group rekeying)算法。该算法能够利用局部密钥信息更新组密钥，适合拓扑结构变化频繁、连接短暂、带宽有限的移动自组网络。为了进一步降低算法的通信代价，通过在组密钥更新时动态生成组密钥更新簇，对DGR算法进行了改进，提出了CDGR(cluster distributed group rekeying)算法，并讨论了上述算法的安全性、正确性和完备性，分析了算法的通信代价。最后，利用ns2模拟器对算法的性能进行了分析。模拟结果显示，DGR和CDGR算法在组密钥更新成功率和延迟等方面均优于其他算法，并且由于采用簇结构，CDGR算法的更新延迟低于DGR算法。
在组通信过程中，数据的私密性通过TEK加密实现.当节点加入或退出时，组成员节点都需要更新TEK，以保证通信的后向私密性和前向私密性。
在DGKMF中，请求加入的组成员需要由离线组控制节点或门限个组成员节点为其颁发组成员资格证书。利用TEK更新算法，新加入的组成员与其邻居节点生成新的组密钥以后，用已有的组密钥加密新的组密钥，向组中所有节点广播，以更新组密钥。
组成员退出分为主动退出和强制退出两种情况。当组成员主动退出时，它向全组广播退出请求。强制退出请求由发现异常的节点广播。接到退出请求的组成员利用TEK更新算法更新组通信密钥，同时将退出组成员的资格证书加入到证书废除列表中，以防止已退出的组成员参与密钥更新过程。
高效、安全的组密钥更新算法对于安全组通信至关重要。在DGKMF的基础上，提出了两种组密钥更新算法:DGR算法和CDGR算法.这两种算法均只需利用局部密钥信息更新组密钥，避免了移动自组网络拓扑结构变化频繁、连接短暂等特点对组密钥更新的影响；其主要区别在于密钥更新的方式不同。在DGR算法中，每个节点均需要与门限个以上的邻居节点通信，以更新组密钥，局部通信代价较大。而CDGR算法在组密钥更新时动态生成组密钥更新簇，通过建立层次结构降低了组密钥更新的通信代价。
假设节点在密钥更新过程中时钟同步，节点在更新过程中安全可靠，且节点通信具有松散的同步机制支持。
模拟实验
在实际环境下，移动自组网络的连通性以及链路的可靠性难以保证.因此，为了验证算法的有效性，采用ns2网络模拟器比较了DGR算法和CDGR算法在节点加入、退出时TEK更新的成功率和更新延迟，并比较了它与组密钥管理协议CKD，GDH v2以及BD协议的性能。
模拟环境的链路可靠性为90%，节点的平均速度为10m/s，节点停等时间为5s.网络规模以节点数量表征，节要点数量是30~100，幅度10均匀变化。模拟空间随网络节点数量变化，以保证网络的连通性，协议模拟时间为1500s。
由于组密钥更新算法的性能与网络中节点的密度有密切的关系，将网络中组成员的平均邻居数量称为网络的连通强度，用D标识.当模拟时，D=5，即平均每个节点的邻居数量为5。
根据网络连通强度为5，网络中节点的数量分别为30，40， … ，100，链路可靠性为90%，节点的最大移动速度为5m/s，节点停等时间为5s.的模拟实验结果可以看出，DGR算法和CDGR算法依赖于局部通信更新组密钥，延迟在30s 左右，随着网络规模的扩大略有提高。由于组成员加入时，DGR，CDGR算法的密钥更新过程类似，均需要为新加入的节点分发共享密钥，因此算法的性能相当.在节点退出时，CDGR算法由于在组密钥更新时动态生成更新簇，利用簇首节点局部生成并分发组密钥，减少了本地通信代价，因此CDGR算法的延迟低于DGR算法.在节点加入、退出时，DGR算法和CDGR算法的TEK更新成功率均接近于100%。在相同的模拟条件下，CKD，GDH v2以及BD等组密钥管理协议和算法的更新延迟平均在80s左右，组密钥更新的成功率均低于90%，并且随着组的规模增加性能急剧下降。其密钥更新成功率和延迟均比DGR算法和CDGR算法要差。
apReduce并行关联规则增量更新算法
为解决传统关联规则挖掘算法在大数据环境下运行效率较低的问题，基于频繁模式增长(FP-growth)算法，提出一种面向大数据的并行关联规则增量更新算法。利用MapReduce编程模型与云计算平台，对FP-growth算法各步骤进行并行化处理。在增量更新挖掘过程中，使用已有的频繁项集和1-项集对新增事务集构建频繁模式树，通过扫描原始事务数据库完成频繁项集的更新。实验结果表明，与传统关联规则挖掘算法相比，该算法具有更高的挖掘效率和扩展性，适用于大量数据的关联规则增量挖掘。
PFP-growth算法是公认的高效并行关联规则挖掘算法，该算法基于FP-growth算法，采用MapReduce编程模型，对FP-growth算法各个步骤进行并行化处理。在面对大量数据时，PFP-growth算法具有较高的准确性和伸缩性，解决了FP-growth算法单机情况下面对大量数据时性能不足的问题。但由于事务数据库处于不断更新中，PFP-growth算法仍然不能利用已有挖掘结果进行增量挖掘。主要是针对关联规则的增量更新问题，提出并行关联规则增量更新算法，该算法分为2个步骤：
(1)针对原事务数据库DB进行分组，构建各映射数据库，利用MapReduce并行挖掘出频繁项集并保存，该步骤与PFP-growth算法类似；
( 2) 针对新增数据库，利用之前的挖掘结果再次进行并行挖掘，完成频繁项集的更新。
实验运行在Hadoop平台上，使用多文件输出功能以及Mahout工具实现了多个MapReduce任务的迭代运行。Hadoop平台由6个节点组成，其中，1台为Master节点； 其他5台为Slave节点。每个节点的硬件配置与单机情况下的实验相同，操作系统为Ubuntu12.0.4，Hadoop版本为Hadoop-0.20.2，jdk版本为jdk1.7.0_45。实验使用的数据集为webdocs.dat，webdocs.dat，数据大小为1.37GB，共有1692082条记录，包含5267656个不同的项，其中，最长的事务有71472项。
实验中首先将数据分为5组，选取数据集的20%作为原数据库，记做data0，每次递增20%进行并行增量挖掘，分别记做data1，data2，data3，data4，支持度为5% 。将并行化算法与Mahout开源平台所提供的PFP-growth算法、文献中的MRFUP算法进行比较，其中，算法和PFP-growth算法中的分组数均为5。
由Hadoop平台下的算法性能对比可以看出，相比PFP-growth算法，并行化算法很大程度上提高了挖掘效率，这是因为算法每次只对新增数据库的分组构建条件FP-tree，节约了每个分组构建FP-tree的时间。MRFUP算法虽然也是基于MapReduce的增量更新算法，但是算法的很多步骤仍然是在单机环境下，只有对候选集的筛选是在云计算平台下进行，因此，在数据量较大的情况下算法效率提高有限。随着数据的不断增加，并行化算法的时间开销增幅平稳，在大数据环境下能保持稳定。因此，实验结果证明了并行化算法适用于大数据环境下的增量更新。
为了验证算法的可扩展性，将数据集的80%作为原数据库，20%作为新增数据库，支持度分别设为5% ，10%和15% ，分别基于1个～5个Slave节点比较算法的运行时间，由不同Slave节点和支持度下的算法运行时间对比可以看出，在数据和支持度相同的情况下，随着Slave节点数量的增加，算法执行时间逐渐降低，这是因为Hadoop集群具有高度并行性，而在一个机架内节点之间的通信开销较小，从而程序整体运行时间不断减少。而在数据和节点相同的情况下，当支持度较大时，运行时间较少，这是因为随着支持度增加，数据的头表中的项目变少，分发数据和建立FP-tree的时间开销都会降低。