聚集算法（共6篇）
聚集算法 篇1
0 引言
科学研究和工程实践中往往存在着一些多目标优化问题 (Multi-objective Optimization Problem, MOP) , 早在1967年, R.S.Rosenberg就在其博士论文中提到了使用遗传算法解决单目标问题, 20世纪80年代中期David Schaffer设计了历史上第一个多目标优化算法。多目标优化算法发展至今已产生很多优秀的算法, 例如, Fonseca、Fleming和Horn等[2,3,4]人提出Multiobjective Genetic Algorithm (MOGA) 、Non-Dominated Sorting Genetic Algorithm (NSGA) 以及Niched Pareto Genetic Algorithm (NPGA) 。Zitzler与Thiele等[5,6,7]人提出Strength Pareto Evolutionary Algorithm (SPEA) 、Pareto Archived Evolution Strategy (PAES) 和Micro-Genetic Algorithm (Micro-GA) 。2003年, Wiegand和De Jong[8]对Cooperative Algorithms进行了深入分析。
协同进化最早由Ehrlich与Raven讨论植物和食植昆虫进化的相互影响而提出。Hillis[9]在1991年提出寄生的协同进化算法模型, 用于协同进化分类网络的设计。1995年, Rosin等[10]提出了竞争协同进化算法模型, 用于研究偷窃的博弈问题。
近年来, 对于基于协同进化的的多目标优化算法研究取得了大量成果, 如文献[11]是设置n个子种群分别独立的基于已有多目标优化算法问题。文献[12]是设置一个目标对应一个子种群, 根据生态种群密度竞争方程调整各子种群的规模, 用于描述多个目标之间的关系。文献[13]是依据在进化过程中获取的信息划分搜索空间, 该方法的不足之处是划分搜索空间后可能产生大量的子种群, 导致计算量过大。
与多目标优化算法相比, 协同进化多目标算法的均匀性与分布性较差。本文提出了基于聚集密度的协同进化多目标算法, 并且数值实验结果以及图示对新算法的均匀性与分布性做了测评。
1 多目标优化问题的相关概念
1.1 多目标优化问题的基本概念
多目标优化问题的基本形式为:
其中, x为决策向量, F (x) 为目标函数, gi (x) ≥0, hi (x) ≥0为约束条件。
多目标问题的最优解组成的集合叫Pareto最优解集, Pareto最优解集包含了所有的Pareto最优解, 下面给出Pareto最优解的定义。
定义1若xA、xB是两个可行解, 且:
则称xA相比xBPareto占优, 也称xA支配xB, 记为xAxB。
定义2 (Pareto最优解) 一个可行解被称为Pareto最优解, 当且仅当x*满足如下条件:
则称x*为Pareto最优解。
1.2 多目标优化问题最优解集的评价标准
多目标优化算法中最优解的确定是一个非常重要而且困难的研究课题, 对于找到的可行解集, 不仅要考虑得到该解集算法的复杂性, 而且要考虑该解集在目标空间的均匀程度和它们的收敛情况。
在最优化算法发展早期, 研究者们主要通过对解集边界的观察来评价解集的好坏, 这样得出来的结果不仅存在着很大的不确定性, 还受到主观因素的影响。
常用的量化评价指标有:
(1) 世代距离 (Generation Distance, GD)
其中, n为算法所得解集前端PFknown中向量个数, di为PFknown中每一维向量到解集前端PFtrue中最近向量的距离[10]。
GD主要反映PFknown对PFtrue的逼近程度。
(2) 错误率 (Error Ration, ER)
其中, n为PFknown中的向量个数, 且PFknown={X1, X2, …, Xn}, ei定义如下:
ER体现的是PFknow对PFtrue的覆盖程度, ER越小, 说明解集的正确性越高。
(3) 分布性 (Spaing, SP)
其中, n为算法产生解集中解的个数, di为第i个解到它的最近解距离, 表示di的平均值, SP即为di的均方差。根据方差的含义, SP反映的是解集分布的均匀情况。
2 协同进化多目标优化算法
协同进化算法考虑个体之间和个体与环境之间的关系, 种群中个体的进化受其它个体和环境的影响。协同进化算法可以在一定程度上克服早熟现象, 并且更适合复杂问题的计算。根据个体与其它个体之间交互方式的不同可将协同进化算法分为竞争型协同进化算法和合作型协同进化算法。
1997年, Potter在其博士学位论文中对合作型协同进化算法模型进行了深入研究, 针对已有算法需要人参与的缺陷, 给出了一种新型合作协同进化算法结构。
由于合作型协同进化遗传算法的进化效率较高, 并且计算的复杂性较小, 因此我们下面的讨论围绕合作型协同进化展开。合作型协同进化算法首先将优化问题决策变量分组, 然后对分组后的每个少变量决策变量分别编码, 产生初始子种群, 接着各子群独立进化。合作型协同进化算法中的各种群个体适应度是通过将其与其它各物种中随机选取的个体一起组成一个完整的解, 计算这个完整解的目标函数值来作为个体的适该个体的适应度。对某种群个体的评价是依据它与其它种群进化到当前代最优个体组合的好坏来进行, 它们组成的完整解的好坏决定着该个体的适应度。各种群在每代执行过程中通过适应度比较找出当前代最优个体, 各种群当前代最优个体的组合即为当前代的可行解, 这样代代下去搜寻最优解。
将多目标优化问题的决策变量分为几个部分, 既可以将其中几个决策变量作为一个部分, 另外几个决策变量作为另一部分, 剩下的决策变量再作为一个部分。每个部分对应一个种群, 每个种群的个体适应度是通过和其它种群的个体组成完整解再评价得到, 该个体的适应度是由其与其它种群个体组合中最优决定组合。具体步骤如下:
(1) 设置一个超级个体集合P为空集。
(2) 初始化。将所有决策变量分成m组, 初始化m个子种群, 其中每个子种群分别对应各个决策变量。
(3) 求适应度。某个体与其它子种群组合, 根据最优组合求出其适应度。
(4) 遗传操作。使用选择、交叉、变异算子分别对各子种群进行遗传操作。
(5) 更新超级集合P。
(6) 重复 (3) — (5) , 直到满足一定代数, 将当前最优解与P中解进行比较, 留下较好的解, 并且保证P中解有较好的分布性。
(7) 重复 (2) — (6) , 直到P中个体达到一定数目。
3 基于聚集密度的协同进化多目标优化算法
协同进化多目标算法在一定程度上克服了早熟现象, 但是解的分布性和均匀性较差, 对于如何提高协同进化多目标算法的均匀性和分布性已提出了不少方法。耿焕同、朱海峰将均衡分布性与收敛性用于该算法以改善解的分布性与收敛速度;张远淑将均匀设计用于该算法以提高解的多样性和分布性。
协同多目标优化算法分布性欠佳的主要原因在于算法在更新精英集时没有考虑粒子的多样性和分散性。考虑到聚集密度可反映群体的多样性和分散性, 本文提出在协同进化多目标优化算法中引入了聚集密度以进行精英集的更新, 其具体步骤为:
(1) 计算每个种群中各个体的聚集密度。
(2) 依据目标函数值和聚集密度值定义一个偏序集, 该集合中的元素有个体的目标函数值和聚集距离两个属性。
(3) 依据一定的比例, 依次从偏序集中选择个体, 更新P。
由此可以得到基于聚集密度的协同进化多目标优化算法, 具体如下: (1) 设置一个超级个体集合P为空集; (2) 初始化。将所有决策变量分成m组, 初始化m个子种群, 其中每个子种群分别对应各个决策变量; (3) 求适应度。某个体与其它子种群组合, 根据最优组合求出其适应度; (4) 遗传操作。使用选择、交叉、变异算子分别对子种群进行遗传操作; (5) 计算每个粒子的目标向量, 当迭代次数小于最大迭代次数时, 根据聚集密度方法更新P; (6) 重复 (3) — (5) , 直到满足一定代数, 将当前的最优解与P中解进行比较, 留下较好的解, 并且保证P中解有较好的分布性; (7) 重复 (2) — (6) , 直到P中个体达到一定数目。
4 数值实验与算法性能评测
下面用基于聚集密度的协同进化多目标算法对两个标准测试函数DTLZ1和Deb2进行数值计算, 并将计算结果与普通协同进化多目标算法的计算结果进行比较, 从而检验改进算法的性能。
图1—图4分别是用改进算法和常规算法求出DTLZ1和Deb2的Pareto最优边界。可以很直观地看出, 改进算法在解的分布性和均匀性方面均明显优于常规算法。
为了更进一步定量地评价改进算法的性能, 给出改进算法和常规算法的世代距离、错误率和分散性指标的对比数据。考虑到计算结果的随机性, 表中给出的是20次实验结果的平均值。
从表1和表2中可以很清楚地看出, 改进算法和常规算法的GD指标相差无几, 但改进算法的ER和SP指标与常规算法相比明显占优。
综合图1—图4和表1—表2, 可以得出明确结论:基于聚集密度的协同进化多目标算法的收敛性与常规协同进化多目标算法相当, 但其分布性和均匀性有明显提高。
聚集算法 篇2
1 浅析动态数据聚集算法
动态数据聚集算法中，聚类是数据挖掘中一类重要的问题，在许多领域有其应用之处。聚类的定义是：给定一个由许多数据元素组成的集合，将其分为不同的组（类、簇），使得组内的元素尽可能相似，不同组之间的元素尽可能不同[1]。在动态数据聚集算法中，其数据流具有以下特点：数据实时到达，数据到达次序独立，不受系统控制；数据量巨大，不能预知其大小；单次扫描，数据一经处理，除非特意保存，否则不能再次被处理。由于计算机数据中心数据流的特点，要求数据压缩表达，并且可以迅速、增量地处理新到达的数据，要求该算法可以快速、清晰地识别离群点。
2 计算数据中心应用动态数据聚集算法实现
对动态聚类算法中的数据流，在每一个时刻，动态聚类算法的在线部分连续地读入一个新的记录，将多维的数据放置到对应多维空间中的离散密度网格。在第一个gap时间内产生了初始簇[2]，然后，算法周期性地移除松散的网格以及调整簇，由于不可能保留原始数据，D Stream将多维数据空间分为许多密度网格，然后由这些网格形成簇，如图1所示。
文本中，假设输入的数据有d维，在计算机数据中心空间中定义数据：
在动态数据聚集中，可以将d维的空间S划分成密度网格。假设对于每一维，它的空间是Si,i=1,2,⋯,d被分为pi个部分。
这样数据空间S被分成了个密度网格。每个密度网格g是由,ji=1,2，…，pi组成，将它表示为：
一个数据记录X=(x1,x2,…,xd)可以映射到下面一个密度网格g(x):
根据网格密度变动，更新网格密度，当一个新的计算机中心数据到网格，接收数据记录，设一个网格g在时刻tn接收到一个新的数据记录，假设g接收到最后的数据记录是在时刻tl(tn>tl)，那么g的密度可以按下面的方式更新：
计算数据中心动态数据聚集算法的实现中，其最基本的计算思想是，在聚集数据的最中心对象，对n个对象给予k个划分区域；并且此代表对象也可以被称为中心点，而其他的对象为非代表对象，反复使用非代表对象替换代表对象，从而动态地找出数据中心更好的中心点，改进数据中心聚类质量。自定义一个函数：
一个非中心点代替一个中心点的总代价s
3 计算数据中心动态数据聚集算法仿真研究
3.1 仿真试验环境搭建
对于计算数据中心动态数据聚集算法，针对动态数据聚集算法实施仿真试验，在一台带有1.7 GHz CPU和256 MB内存的PC上进行，用VC++6.0以及一个Matlab图形接口实现动态聚类算法仿真。研究其算法性能及结果准确性，数据中心将10个节点存放于一个机架上，环境参数见表1。
在动态数据聚集算法仿真试验中，可以设置：Cm=3.0,Cl=0.8，λ=0.998，β=0.3，使用两个测试集。第一个就是测试数据集，也是一个真实的数据集合KDD CUP-99，它包含由MIT林肯实验室收集的网络入侵数据流。也使用人工数据集测试动态聚类算法的伸缩性。这个人工数据集包含的数据数量从35 000～85 000不等，簇的数目被设定为4，维度的数目范围[3]从2～40。在动态数据聚集算法仿真试验中，将数据集的所有属性规格化为[0,1]。每个维度被均匀地分为多个数据段，每个段的长度为len。
3.2 仿真结果评估
将评估计算数据中心的动态聚类质量与效率与传统计算数据中心的算法进行比较，本文算法能提高算法时间、空间效率，对于计算中心高速的数据流不损失聚类质量，有独特的优势，准确地识别实时数据流，并实施演化行为。计算数据中心动态聚类算法与传统数据分配算法相比，数据准确性得到提升，为98.2%，常规数据分配准确率为83.6%，有明显优势（P<0.05）。计算数据中心动态聚类算法的应用，可以提升计算数据中心系统的稳定性。
4 总结
基于计算机数据中心数据分配中，在数据中心网络技术基础上，由于数据节点可以自由移动，这样会降低数据分配进度，从而降低系统性能，导致计算机数据中心网络维护开销过高。故此，针对计算机数据中心数据分配，应该改进传统静态数据流数据方法，实现动态数据聚集，减少信息冗余，提升数据计算效率及安全性。
参考文献
[1]李文华,罗霄,张乐.飞控计算机数据模拟器的设计与实现[J].现代电子技术,2014,37(11):104-106.
[2]徐小龙,杨庚,李玲娟,等.面向绿色云计算数据中心的动态数据聚集算法[J].系统工程与电子技术,2012,34(9):1923-1929.
[3]郭建波.动态数据聚集算法探究:以绿色云计算数据中心为研究方向[J].中国信息化,2013(4):108-109.
[4]翁祖泉,张琪.基于物联网海量数据处理的数据库技术分析与研究[J].物联网技术,2014,4(6):88-90.
[5]李海涛.云计算用户数据传输与存储安全研究[J].现代电子技术,2013,36(20):24-26.
聚集算法 篇3
1 Pareto支配关系
通常一个MOP可以表示如下:
其中决策向量x∈Rm, 目标向量y∈Rn, fi (x) (i=1, 2, …, n) 是目标函数, gi (x) (i=1, 2, …, h) 是约束条件, 对MOP的非劣最优解定义如下:
定义1 (非劣最优解) :若x*是搜索空间中一点, 说x*为非劣最优解, 当且仅当不存在i使得fi (x) >fi (x*) 成立。
相应非劣最优解的目标向量称为非支配目标向量 (Non-dominator) , 由所有非支配的目标向量构成MOP的非劣最优目标域 (Pareto Front) , 也称Pareto最优前端, 由于向量间的比较是偏序关系, 所以对解之间的关系有如下定义:
定义2 (Pareto支配) :设u, v∈Rm, 说向量u支配 (Dominate) 向量v, 记为, 当且仅当:
如两个解向量u, v∈Rm间是相互不被Pareto支配的, 则称它们是Pareto无关的, 在多目标进化算法中, 近年的研究倾向于基于Pareto最优化的方法, 通过构造进化群体的非支配集, 并使非支配集不断逼近true Pareto front实现。一个进化群体的非支配集, 实际上也是当前进化群体的最优个体集合。
2 改进的聚集距离
在多目标进化算法中, 对于某些问题, Pareto最优解集 (Pareto optimal set) 可能很大, 也可能包含无穷多个解, 把所有这些解都列入到非支配集 (non-dominated set) 中有时是比较困难的, 同时也没有多少实际意义。因此, 我们有必要使非支配集 (non-dominated set的大小保持在一个合理的界限内。在此前提下保持整个的进化群体的分布度是有助于维持Pareto最优解集的完整性。
原有的聚集距离[1]如下:设有二个子目标f1和f2, 个体i的聚集距离是图中虚线四边形的长与宽之和。设P[i]distance为个体i的聚集距离, P[i].m为个体i在子目标m上的函数值, 则图中个体i的拥挤距离为:
一般情况下, 当有r个子目标时个体i的拥挤距离为:
算法1:
步骤1:初始化每个个体的拥挤距离, P[i]distance=0;
步骤2;对每个目标进行排序, 根据公式 (1) 和 (2) 计算每个个体的拥挤距离;
步骤3:将边界点赋予最大值以确保进入下一代;
步骤4:对个体的拥挤距离进行排序, 并选择拥挤距离大的个体进入下一次迭带;
拥挤距离能够较好计算个体之间的密度, 但是算法由于排序的作用, 算法选择拥挤距离较大的个体进入下一代, 而拥挤距离较小的个体被淘汰, 由于拥挤距离计算的是精英集 (非支配解集) 个体之间的拥挤距离, 存在着这样一种情况, 当一个拥挤距离较小的个体淘汰之后, 会造成其它个体的拥挤距离变化。从而不能真实的反映个体之间真实的密度关系, 如图2所示截断算法运行时存在10个Pareto解集, 对此解集进行截断, 预定大小为5, 此时由于虚线框中的个体 (a与c之间) 拥挤距离是种群中最小的, 对其进行排序, 对其中的拥挤距离较小的个体进行截断, 从而造成虚线框没有个体存在, 如图3所示, 其解集分布并不均匀。
为了解决此问题, 我们加入了一个动态的更新算子, 从而使加入外部集的个体的拥挤距离最大, 从而使种群保持较好的分布度。其算法如下所示:
算法2:
步骤1:初始化每个个体的拥挤距离, P[i]distance=0;
步骤2:对每个目标进行排序, 根据公式 (1) 和 (2) 计算每个个体的拥挤距离;
步骤3:将边界点赋予最大值以确保进入下一代;
步骤4;查找精英集中拥挤距离最小的个体P, 并将其从精英集中淘汰掉;
步骤5:重新更新个体的拥挤距离 (在此值得说明的是更新每个个体的拥挤距离大小时, 我们记录了其每个目标的最近距离) ;
步骤6:精英集满足预定大小停止, 否则转步骤4;
由于改进的算法采用了动态的更新算子, 每淘汰一个个体重新计算与其相邻的个体, 从而使拥挤距离能够真实的反映出个体之间的密度关系, 其最终的解集如图4所示。
3 数值实验
本文选取常用的测试函数Zdt4[3]与Zdt6[3]验证我们所提出的分布度算子的有效性能。
Zdt4函数
Zdt6函数
在实验中我们运行NSGA2与改进的算法如图4和图5所示, 从图中我们可以看出改进算法比原始的NSGA2能够较好的收敛于前沿面, 而采用聚集距离的NSAG2在优化Zdt4函数难以得到最优面, 对于Zdt6函数其算法所得到的最优前沿面分布不均匀, 而对于采用了变异算子的NSGA2而言, 算法能够接近于Pareto前沿, 而对于Zdt6函数算法也能够较好的收敛。这证明了我们的算法能够较好的保持分布度。
4 结论
针对多目标进化算法中聚集距离难以很好的保持进化群体的分布性, 设计了一种根据改进的聚集距离策略, 使多目标进化算法能够具有较好的分布性能, 实验验证了我们算法的有效性能。
参考文献
[1]Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, et al.A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-II[J].IEEE Trans-actions on Evolutionary Computation, April2002, 6 (2) :182-197.
[2]David W.Corne D, Joshua.Knowles and JMartin.The Pareto Envelope-based Selection Algorithm for Multiobjective Optimization[C]//Proceedings of the Parallel Problem Solving from Nature VI Conference, Springer, 2000:839-848.
[3]zitzler E, Deb K, Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results[J].Evolutionary Computation, 2000, 8 (2) :173-195.
聚集算法 篇4
关键词：聚集系数,对等网络,路由算法,搜索策略
网格计算和对等网计算是网络计算领域中最重要的研究方向，虽然两者面向的应用领域不同，但在技术上却有大量相通的地方。特别是对等计算领域中获得的大量研究成果已经被广泛应用于网格系统的设计和实现中，用于解决资源发现和系统可扩展性等问题，取得显著成效。对等网络通常简称为P2P (Peer to Peer)。对等网络作为最近几年的一种热门网络技术，在很多方面有重要应用。如：Napster、Gnutella、e Donkey、BitTorrent等P2P软件提供文件和其它内容共享;SETI@home、Avaki、Popular Power等可挖掘P2P对等计算能力和存储共享能力;JXTA、Magi、Groove、.NET My Service等软件可提供基于P2P方式的协同处理与服务共享平台;而QQ、Yahoo Messenger、Skype等是在P2P对等网络基础上开发的即时通讯软件。随着P2P应用规模的日益增大，P2P系统产生的网络流量已经超过http访问产生的网络流量，成为占据Internet带宽的首要应用。在P2P模式中，节点均离散地分布在物理网络的不同地方，P2P系统通过在应用层建立的网络 (即覆盖网Overlay Network) 将这些节点连接起来。每个节点各自存储与覆盖网中部分节点之间的路由信息，通过节点间的合作转发实现覆盖网中的消息路由，并以此为基础，为丰富多样的网络应用提供支持。
如何在庞大的分布式网络中高效地查询并有效地定位资源是P2P技术的关键与研究的热点。由于对等网络系统的可扩展性和网络节点的不确定性，设计一个良好的搜索机制比较困难。研究结果表明，基于对等网络技术的应用软件在选择通信路由时具有非常大的灵活性，它们必须克服Internet的不稳定性、多变性，并且根据网络性能，智能地选择相应的路由来通信。因此，对有效的搜索机制进行研究必然在对等网络研究领域产生巨大的推动力。
1 基于拓扑结构的路由查找算法
对等网络领域一个很重要的研究就是对路由查找算法的研究。对等网络搜索技术从结构角度出发又可以分为四类：集中式对等网络的搜索技术，结构化对等网络的搜索技术，非结构化对等网络的搜索技术，混合式对等网络的搜索技术。结构化对等网络搜索算法是一种采用纯分布式的消息传递机制和根据关键字进行查找的定位服务模型，结构化搜索方法与其覆盖网络拓扑结构、路由表结构密切相关，虽然结构化搜索策略看上去方法众多、各有所长，但本质都是采用分布式、局部性的贪心路由算法，逐步缩小当前节点与目标节点之间的ID差异。所谓非结构化就是节点之间没有任何的组织规则，完全随机的散布在网络中。非结构化对等网络路由搜索算法是建立在无结构对等网络拓扑结构的基础上，在重叠网络 (Overlay Network) 上建立随机图的方式，这些系统对结点的加入和退出没有强硬的结构限制，甚至大部分系统并没有限定的结构。非结构化对等网络路由搜索算法主要分为盲目搜索算法 (Blind Search Algorithms) 和启发式搜索算法 (Informed Search Algorithms) 两类。
另外，我们还可根据所构造网络的拓扑结构，有效地利用其中有用的统计特征，进行高效的路由。
2 具有小世界特性的路由查找算法
我们将非结构化和结构化P2P网络结合起来，构建一个包含两层节点的网络。在这种路由算法中，包含两层的结构，中心层的拓扑结构是结构化的网络，我们用CHORD算法来构建拓扑结构，外围层的拓扑结构是非结构化的网络。在外围层中，结点首先组织在一个小型的非结构化网络里，结点之间的消息是在小世界模型的基础上使用最大度搜索的启发式的洪泛算法来传递的。我们将这个小型的非结构化网络称为域。然后让域组成一个结构化的网络。每个域在中心层拓扑结构里可以看成一个结点。这个系统的结构图如图1所示。
外围层的拓扑结构是非结构化的，它具有高聚集度而低特征路径长的特征，符合小世界网络特性。其中，聚集系数 (clustering coefficient) [3,5]也称为小集团系数，或聚集度。一般的，假设网络中的一个节点i有K条边将它和其他节点相连，这K个节点就称为节点i的邻居。这K个节点之间的实际存在的边E的总和与这K个节点之间总的可能的边数K (K-1) /2之比就定义为节点i的聚类系数。即：Ci=2E/K (K-1)
平均路径长度[3,5]是指任意两节点间最短路径的边数的平均值。平均路径长度是网络的全局特征。己知一个有n个结点的无向图G，任意两节点u、v间最短路径上的边数为Duv，则其特征路径长。
根据节点的聚集度将节点划分为一个个的Clusters域。按照对等网络节点的存储能力、运算能力、带宽能力和稳定性等功能，将节点分为两类:一是普通节点，令普通结点为聚集度为C0的节点，其中C0的值大于某一规定阀值。我们把普通结点作为外围层的域的构成节点，具有本域内的资源定位能力。当域中没有所要查找的资源时，需要超级节点的帮助;二是超级节点，这种结点聚集度为本域中的聚集度的平均期望值。这种结点不仅参与本域的资源定位和共享，并且帮助域内的其他节点完成域外的资源查找操作。另外，所有超级节点之间互相协作，构成中心层。
如图1，在域1中，用户1发出查询请求，在域1内的所有普通节点中先找到离自己最近且聚集度最高的节点，聚集度最高的节点收到请求后，如果发现发现索引记录列表有所找的关键值，则将查询结果返回给用户1。如果没有，则用户1的普通结点找到离自己最近，且聚集度次高的结点。如果域中没有找到，则将请求发给超级节点。超级节点1收到请求后，如果发现索引记录列表有所找的关键值，则将查询结果返回给用户1，用户1根据返回的结果下载资源。
如果域1内的超级节点1收到请求后，发现自己的索引记录列表和查询缓冲区内并没有所找的关键值，则超级节点1在主干网中发送资源查询请求。请求经过主干网的Chord路由，到达了目标域2中的超级节点2，超级节点2查询自己的索引记录列表，发现有匹配的索引记录在用户2，发送应答消息给域的超级节点1。超级节点1将结果返回给查询节点用户1。用户1根据返回的结果链接资源所在的用户2，下载资源。如果所有域都没有查询到所需资源，则没有此资源，查询失败。
3 实验结果及分析
仿真实验在一台PC机上进行，软硬件环境如下：CPU为Intel Pentium 1.8GHz微处理器，内存512MB，运行Windows 2000 Professional操作系统。为了对upload/download系统的性能进行评估，我们把实验分为两部分：网络模拟和实际环境测试。我们选用PEERSIM来对基于聚集系数的网络 (CCN) 进行模拟。试验参数如下：结点规模最小210，最大218，群内TTL为5，域内泛洪转发邻居数为5，域个数与域内结点个数为1/10。每次试验重复20次，实验结果为平均值。
图2显示了CCN与其他两种网络的平均查询跳数对比。我们从图中可以看出，两者的信息查询跳数很接近，这说明我们的系统具有较小的查询延迟。当结点超过215时，我们所设计的系统的平均跳数小于Chord。这是因为我们的外围域内固定TTL的限制，使得我们的跳数增长速度下降，同时查询效率也是在下降的。
4 结论
本文主要通过研究现有Chord的构造特点，在其节点构造路由以及路由查找的过程中加入对结点聚集度的考虑，以获得更好的路由性能。本文首先总结对比了结构化P2P网络拓扑结构与非结构化网络拓扑结构算法的优缺点，然后提出一个建立在新的P2P的网络结构上路由搜索策略。我们设计的算法结合了泛洪和DHT两种方法，利用将结点按聚集度的方式组织成非结构化的域来加入DHT网络的方式，提高了DHT面对动荡网络时的稳定性，将DHT引入到了实用的地步。最后，我们给出了有关仿真实验的结果。经过实验分析，我们的路由策略是一个可扩展、查询效率高、稳定性好的算法。
参考文献
[1]Dejan.Milojieie, Vana Kalogerki, RajanLukose, KiranNagarajal, JimPruyne, Bruno Richehard, Sami RollinsZ, ZhichenXu[J].http://ww.hPI.hP.eoln/teehreP0rts/2002/HPL-2002-57RI.Pdf.
[2]陈贵海, 须成忠, 沈海英.一种新的常数度数的P2P覆盖网络.计算机学报, 2007, 10 (01) :1084-1095.
[3]D.J.Watts, S.H.Strogatz, Collective dynamics of‘small-world'networks, Nature393 (1998) 440-442.
[4]庄雷, 潘春建, 郭永强.Gnutella网络的连接管理.软件学报, 2005, 16 (1) :158-164.
[5]X.Li, and X.Wang, "Controlling the Spreading in Small-World Evolving Networks:Stability, Oscillation, and Topology, "IEEE Trans.Automatic Control, Vol.51, No.3, pp.534-540, 2006.
聚集算法 篇5
1 数据中心动态数据聚集算法的研发背景分析
由于信息时代的到来, 大多数人们在生活和工作中都离不开各类电子产品的应用。从现实环境来看, 在资源的利用与存储方面, 云数据中心及其服务能够满足互联网平台上的用户服务需求。从具体的实践领域来看, 现代企业或其它社会组织机构通过各种途径来获取大量的数据信息资源, 绝大多数机构欲想要在市场竞争中争取到一定的发展空间, 信息资源的获取则是最基础的内容。
现阶段, 大部分人们的生活和工作环境当中已经离不开信息的传输与共享的过程, 且人们获取信息的速度以及渠道不断的发生着变化, 各种形式的数据资源被人们储存在各类媒介之中, 并得以保存下来, 以备后期查阅与调用。当数据量激增状况出现时, 即大型数据集涌现, 让人们不得不探寻新的数据储存及处理渠道, 从而将信息资源更完整的保存下来。但在构建大型数据集计算模型的过程中, 往往会出现诸多阻碍以及技术难题, 直至大型数据集数据挖掘算法这一策略的出现, 才使得有关数据中心动态数据聚集的研究项目成为人们关注的焦点。
2 基于绿色云计算的数据中心动态数据聚集算法的各环节步骤
2.1 浅析云计算模式
云计算是一种基于互联网平台管理的新型网络化服务模式, 可以实现资源的储存以及资源的共享等职能, 具备一定权限的用户可以顺利到云计算服务平台上去下载所需要信息资源, 极为方便快捷。
2.2 在绿色云计算模式影响下的数据中心动态数据聚集算法及其步骤
在当今大数据时代背景下, 云计算服务项目得到了更为广阔的发展空间, 为现代社会生产建设助力, 其实践价值极高。绿色云计算模式则意味着通过有效的能耗管理来实现高质量的数据聚集服务, 从而使云节点能够顺利的达成轮流运转的目标, 并促使部署于云数据中心各个区域的服务设备都能够高效运行, 在大量资源的采集与处理过程中, 满足用户的差别化服务要求。
3 基于绿色云计算的数据中心动态数据聚集算法的实现
3.1 动态数据聚集算法及其能耗分析
在云计算模式的支撑下, 对于数据中心动态数据聚集而言, 需要细致温度控制来实施能耗管控, 进而有效防止资源浪费等问题的发生。在信息技术快速发展的当今社会, 在很多领域所构建的数据库的规模以及范围都在不断地扩容, 但即便是相关技术在不断更新当中, 却也无法运用传统技术来满足极快速增长的数据信息量, 这便是大型数据集的表象特征。海量数据归档的实现依赖的是数据采集及职能化分析处理模块的系统功能, 并且将数据信息进行合理的编排与归集, 以便于系统的执行者后期进行查阅与调用。
3.2 实现绿色云计算模式下的数据中心动态数据聚集算法
通过研究绿色云计算影响下的数据部署机制等内容可以了解到, 在云计算数据中心执行任务或为用户提供服务的过程中, 需要注意的问题有两点内容:
其一, 云计算数据中心的节点以及数据信息在不同时间段中的到访情形不尽相同, 主要呈现出波态分布的状况。
其二, 在新型数据部署机制的影响下, 云计算数据中心即使处在空转状态下, 其服务器能耗也维持在较高的水平, 这就给绿色云计算的出现埋下的伏笔。
其三, 数据中心存储的数据信息随着应用的普及而快速增长, 因此, 需要数据中心动态数据聚集的过程有着较强的可延展性等性能, 从而满足用户的使用需求。
4 结束语
总而言之, 为了实现数据中心动态数据处理系统的整体降耗目标, 且充分利用数据平台资源, 为客户带来优质服务, 则通过仿真实验的操作过程可以看到, 基于绿色云计算的数据中心动态数据聚集算法能够保障云数据中心的服务质量, 提高设备稳定性与经济性, 并最终实现整个系统运作的“绿色”节能降耗的目标。
参考文献
[1]叶可江, 吴朝晖, 姜晓红等.虚拟化云计算平台的能耗管理[J].计算机学报, 2012, 06 (06) :1263-1285.
[2]吴俊.面向云计算的数据中心网络体系结构设计[J].计算机光盘软件与应用, 2013, 04 (04) :234-236.
[3]张慧珍, 李长春, 周培琴等.云计算数据中心节能技术研究[J].信息系统工程, 2013, 10 (10) :79-80.
聚集算法 篇6
数据聚集(如求平均数,最大值,最小值等)是自组织网络中的一种重要数据操作[1,2],如无线传感器网络作为自组织网络的一种,用于数据聚集时需要将传感器感知的数据通过多跳传播到基站节点。对于自组织网络中的数据聚集应用,可采用网内数据聚集方法:将部分数据处理放到网内节点上,从而有效减少网内的数据传输流量。一些典型的数据聚集系统,如TinyDB[3]和Cougar[4],用于在一种自组织网络(如无线传感器网络)中管理数据聚集操作。在这些数据聚集系统中,无线传感器网络被组织成数据聚集树,用于数据向根节点的路由,路由过程中进行网内数据聚集。树状结构对于网内数据聚集是一种传输能量的有效结构,树状结构可以减少网络节点间某些无用的数据传输操作。而相对于将所有数据都传输到基站节点进行汇集的方法,网内数据聚集方法能够有效减少节点间的数据传输。
虽然上述TinyDB[3]和Cougar[4]等数据聚集系统采用了“数据路由树结构”实现数据向基站节点的路由,但该树结构只是用于实现数据向基站节点的路由,并没有为数据聚集在中间结点上的执行路径作优化。
提出一种为网内数据聚集优化的路由重构方法,该路由重构方法包含三个阶段过程,通过路由树的遍历、父节点的优化和路由树的动态维护,实现一种为数据聚集优化的动态路由树,通过沿着动态路由树进行数据聚集,实现一条动态最优的网内数据聚集执行路径。
1 网内数据聚集
在网内数据聚集中,分布在不同节点上的数据向某个基站节点汇聚,数据的聚集运算发生在数据向基站节点的路由过程中。网内数据聚集中的聚集运算满足下列两个性质:
首先,聚集函数的结构满足:<z>=f(<x>,<y>),这里f是聚集函数,x, y, z分别代表不同的数据集合。这里表示聚集函数能够在两个或多个数据集合上进行运算,产生聚集结果集。
其次,期望聚集函数满足f(x ∪ y) = g(f(x), f(y)),这里f和g分别代表不同的聚集函数,这里表示聚集函数在多个数据子集的并集上的运算可以转化为在不同节点上分别对数据子集进行聚集运算。
利用聚集函数的上述性质,可以实现一种网内数据聚集模式:该运算模式将聚集运算放在存储数据子集的节点和需要产生最终聚集结果的基站节点之间的一些中间节点上,从而实现一种数据向基站节点路由的同时进行数据聚集的运算方式,由于聚集运算可将多个大的子集聚集为一个小的数据集,这种网内数据聚集运算模式能够有效减少数据向基站节点路由过程中的数据传输量。
在下面部分,将介绍如何利用网内数据集实现数据聚集查询。
设G<Ni, B, Q, P(), Data(), f>是一个包含自组织网络节点的图,Ni表示图中的节点,B表示基站节点,用于发出聚集查询Q,并接收查询结果集,P(Ni) 表示节点Ni的父节点,Data(Ni)表示节点Ni上的数据,f表示聚集函数。当基站节点将数据聚集查询广播到所有节点后,节点Ni将数据传播到节点P(Ni)并在其上进行数据聚集操作,即z = f(Data(Ni),Data(P (Ni)),其中z表示数据聚集结果集,以上操作在中间节点上递归执行,直至聚集结果抵达基站节点B。
2 基于动态路由树的数据聚集算法
实现动态路由树可分为三个阶段: (1)路由树遍历;(2)最优父节点发现;(3)路由树维护。
在路由树遍历传播过程中,一个"Tree Travel"消息被沿着树结构路由到每个节点。当一个节点接收到"Tree Travel"消息后,他向其邻居节点广播一个"Father Discovery"消息,当该节点接收到所有邻居节点对"Father Discovery"的返回消息后,可以为自己选择一个新父节点。通过这种方式实现路由树的重构。
"Tree Travel"消息包含下述属性: <"Tree Travel", distance)>.
"Father Discovery"消息包含下述属性: <"Father Discovery",distance)>.
每个节点维护两个本地变量:father和distance。distance变量用于记录本地节点到基站节点的距离,father变量用于记录对于数据聚集最优的父节点标识。为方便算法描述,对于节点X上的这两个本地变量,分别表示为X.father和X.distance。
为创建动态路由树,首先假设网络中已存在一个数据聚集路由树,然后通过路由树的遍历和新父节点发现过程重新创建一个为数据聚集优化的路由树。这里需要指出的是,对于每一个数据聚集查询都有一个数据路由树:如果有n个数据聚集查询,则有n个不同的数据路由树。
2.1 路由树遍历
为实现路由树遍历,基站首先广播一个"Tree Travel"消息到其邻居,该消息中携带的distance属性值初始化为0,邻居节点按照表1所示操作将该消息转发到所有网络节点上:当某一节点收到"Tree Travel"消息后,若数据可本地获得,则本地的distance变量值设置为0,并将路由到本地的"Tree Travel"消息中的distance值重新初始化为0,然后继续转发到其节点;若数据无法本地获得,则将路由到本地的"Tree Travel"消息中的distance值增1,然后据此修正本地distance变量,最后向其邻居节点广播一个"Father Discovery"消息。
通过这种遍历方式,每个节点的distance值的大小由距离数据节点的远近决定,这样,每个节点可以根据邻居节点上的distance值选择最优父节点。最优父节点的具体选择过程可参考第2.2节的描述。
其中圆圈代表自组织网络中的节点,带阴影的圆圈表示存储有数据的节点,节点旁边的数字表示节点上运行路由树遍历过程后所记录的distance变量的值。
2.2 最优父节点发现
当一个节点收到"邻居节点"传来的所有"Father Discovery"的响应消息后,它开始根据这些消息重构自己的新的父节点。这里,新的父节点是返回具有最小"distance"值的响应消息的那个邻居节点。具体的最优父节点发现过程如表2所示。
按照表2所示的最优父节点发现过程,针对图1进行最优父节点发现后构造的新的路由树,如图2所示。
2.3 路由树维护
对于动态自组织网络,节点可以随时随处随机移动,同时节点可能随时进入或离开网络。对于这种情况,需要一种同台路由树维护算法,使得路由树可以实时适应当前网络拓扑结构的变化,产生最优的数据网内计算路径。路由树的维护根据下面两种情况分别进行处理:
主动路由维护:当节点X准备退出网络时,向其所有子节点发送"Father Discovery"消息,其子节点按照表2所示操作重新寻找各自的新的最优父节点。
被动路由维护:当节点X发现其父节点失败(发送"hello"消息时无响应)时,向自己发送一个新的"Father Discovery"消息,实现最优父节点的再发现(其消息处理过程见表2)。
3 性能分析
假设自组织网络中的节点数为N,路由树的遍历过程的消息传递量为O(N)。设网络密度为D,即每个节点的平均邻居个数为D,则父节点发现所需消息传递量为O(N*D),则本算法的路由树重构过程所消耗的信息传递量为O(N*(D+1))。
4 结束语
已有数据聚集系统,如TinyDB[3]和Cougar[4],使用"数据路由树结构"实现数据向基站节点的路由,但该树结构只是用于实现数据向基站节点的路由,并没有为数据聚集在中间结点上的执行路径作优化。提出一种为网内数据聚集优化的路由重构方法,该路由重构方法由三个阶段过程,通过路由树的遍历、父节点的优化和路由树的动态维护,实现一种为网内数据聚集优化的动态路由树。即通过沿着动态路由树进行数据聚集,实现一条动态最优的网内数据聚集执行路径。
提出的这种基于动态路由树的网内数据聚集算法,通过对路由数据的动态重构和维护,解决了自组织网络的节点动态变动问题,以及树结构为数据聚集操作优化的问题。
通过该算法的复杂性分析可知,本算法为进行动态路由树的维护只需付出多项式级别的节点间的消息传递,实现对自组织网络中的数据聚集路径的优化:通过中间节点上的优化的数据聚集操作,减少响应数据聚集查询所需的数据向基站节点的传输过程中的带宽占用量。
摘要：数据聚集是自组织网络(Ad-hoc network)中的一个重要的数据操作。一些用于无线传感器网络的数据聚集系统,通常在网络节点中构建一个路由树结构,用于传感器感知的数据向基站节点的路由和数据在网内节点上的处理。路由树结构是一种用于网内数据聚集的简单通用的算法,但这些数据聚集系统中的路由树结构并没有为数据聚集作优化。提出一种基于动态路由树的网内数据聚集算法,通过对路由数据的动态重构和维护,解决自组织网络的节点动态变动问题,和树结构为数据聚集操作优化的问题。性能分析表明,动态路由树的创建和维护只需多项式级别的节点间的消息传递,为自组织网络中的网内数据聚集实现执行路径的优化。
关键词：网内数据聚集,动态路由树重构,执行路径,自组织网络
参考文献
[1]Intanagonwiwat C,Estrin D,Govindan R,et al.Impact of networkDensity on Data Aggregation in Wireless Sensor Networks[C]//CDCS 0'2:Proceedings of the 22nd International Conference on Dis-tributed Computing Systems(ICDCS'02)Washington,DC,USA,2002.IEEE Computer Society,2002:457.
[2]Madden S,Szewczyk R,Franklin MJ,et al.Supporting aggregatequeries over ad-hoc wireless sensor networks[C]//WMCSA'02:Proceedings of the Fourth IEEE Workshop on Mobile Computing Sys-tems and Applications,Washington,DC,USA,2002,49.IEEEComputer Society,2001:346-356.
[3]Madden S R,Franklin MJ,Hellerstein J M,et al.Tinydb:an ac-quisitional query processing system for sensor networks[J].ACMTrans.Database Syst,2005,30(1):122-173.