连接算法（精选7篇）
连接算法 篇1
0 引言
分布式环境下的连接查询优化是当今数据库理论研究的一个热点问题。由于分布式数据库中数据的冗余性和数据分布的复杂性，全局查询往往涉及多个站点上的关系或关系片段，此时不仅要考虑站点之间数据传输所产生的通信代价，还要兼顾基于站点的局部处理代价，这无疑增加了查询处理和优化技术的难度。为了有效地处理分布式连接操作，国内外文献提出了多种算法，通常分为半连接算法和直接连接算法。典型的半连接算法有SDD-1算法[1]、AHY算法[2]、双向半连接算法[3,4]等，这些算法通过半连接操作缩减站点间数据的传输量，但由于需要二次数据传输，当二次数据传输的总量不小于传输站点上某个关系或关系片段的数据量时，算法将失效。典型的直接连接算法有R*算法[5,6]、利用站点依赖信息（Placement Dependency,PD）的算法[7]等。R*算法直接处理连接操作，通过穷举所有可能的连接策略，将全局连接操作分解为每个站点上的局部连接操作，最后选择一个最优的连接策略作为执行策略，但穷举的计算方法耗时长，且要传输的关系或关系片段的数据量大时该算法的处理效率将不理想。PD算法弥补了R*算法的不足，该算法有效利用了局部查询的本地化特征，在一个设计精良的分布式数据库中可以实现全局连接查询的零数据传输处理。但如果全局连接操作引用的关系片段在不同站点中存在相关联的元组时，该算法将失效。
本文借鉴了PD算法在并行处理方面的优越性，提出了基于连接依赖信息（Join Dependency,JD）的连接查询优化算法。该算法利用连接依赖信息判断基于多站点的数据分布是否符合站点依赖，以降低远程访问的次数，对于不满足连接依赖的站点数据，则采用片段复制方法重新分布数据，确保其适用站点依赖算法。站点间关系或者关系片段的复制时间开销是该算法的惟一通信代价，但是这种代价会被站点间多线程的高度并行所弥补。
1 站点依赖与分片复制算法的原理
1.1 基于PD算法的特性分析
在分布式数据库系统中，关系或者关系的某个片段总是分布在不同的站点上，当两个关系做连接操作时，如果在数据传输量最小甚至无数据传输方式下得到正确的结果，此时可获得最佳的性能。
假定两个关系R1和R2的水平分片分别存放在站点S1和S2上，数据分布的初始状态如表1所示。
在关系R1和R2的公共属性A上作连接操作R1∞R2，如果其结果可以通过合并同一站点上两个关系片段的连接操作的结果集得到，即R1∞R2=(R11∞R21)∪(R12∞R22)，则该策略是一种有效的策略。在该策略中，由于连接操作所涉及的片段总能在本站点找到可关联的元组，因此连接操作可以在站点间不发生数据传输的情况下进行，而且还可以利用本地站点中数据片段的索引信息提升局部处理的性能。
定义1两个关系Ri和Rj在公共属性A上满足条件Ris∞Rjt=Φ，则称Ri和Rj在属性A上站点依赖[8]，即Ri∞ARj=∪(Fis∞Fjs)适用于关系所在的所有站点[9]。
其中：s,t表示不同的站点；符号∞A是在属性列A上的连接操作。
推论1若关系Ri和Rj在属性A上站点依赖，且关系不同站点中的Rj和Rk在属性B上站点依赖，则Ri∞ARj∞BRk=∪(Ris∞Rjs∞Rjs)，其中s为所有包含关系Ri,Rj和Rk的片段的任一站点。
基于上述定义和推论，可以构造站点依赖算法Placement＿Dependency(Q,P,S)[10]，其中：Q是针对关系集合R={R1,R2，…，Rn}的等值连接查询；P是站点依赖信息；S是查询Q引用的满足站点依赖的最大关系集合。该算法的核心思想是利用站点依赖信息P确定查询Q能否零数据传输执行，如果S=R，则查询Q可以零数据传输处理。由于某个站点上的关系片段通常只与该站点的SQL应用密切相关，因此基于站点依赖的连接查询在很多分布式应用中都能得到正确的结果。
1.2 片段复制算法的原理
如果基于多个站点的关系或者关系的一个片段的连接查询不能以零数据传输方式执行，那么可以采用“片段复制算法”弥补其不足。如果R11（或R12）中的元组m与R22（或R21）中的元组n在公共属性列上满足连接条件，那么可以保持R1在站点S1和S2上的片段分布，然后将R21复制到站点S2并与R22合并为R2的一个副本。同样，将R22复制到站点S1并与本地片段合并得到R2的另一个副本。数据复制过程如图1所示。
数据复制结果如表2所示。
此时基于关系R1和R2的连接操作可以转化为片段R11和R12与各自站点上R2的副本的连接，即R1∞R2=(R11∞R2)∪(R12∞R2)。进而推导出，多个站点上与关系R1和R2等值连接等价的代数形式为：
其中∪i操作取遍存放R1片段的站点Si。
由于关系R1的片段R1i远小于R1，因此基于各站点的连接处理代价要远小于两个关系直接连接。另外，操作R1i∞R2可以在独立站点上并行执行，有利于获得良好的响应性能。
2 基于JD的算法设计
2.1 算法描述
设有关系R1,R2和R3，其数据片段分布如表3所示。假定关系R1和R2在公共属性A上站点依赖，关系R2和R3存在公共属性B。
考察上述三个关系的连接操作R1∞AR2∞BR3。根据站点依赖算法，R1∞AR2可以零数据传输方式执行。结合片段复制算法，R1∞AR2的连接结果与各站点上关系R3的副本连接也会在零数据传输方式下执行并得到正确的结果，即：
如果关系Ri和Rj在公共属性A上站点依赖或者关系Ri（或Rj）的副本存放在关系Rj（或Ri）各片段所在的站点上，则称关系Ri和Rj在公共属性A上连接依赖。
构造利用连接依赖信息J对基于多站点上的连接查询Q的连接依赖算法Jion＿Dependency(Q,J,S）。其中：Q是针对关系集合R={R1,R2,…,Rn}的连接查询；J是连接依赖信息；S是查询Q引用的满足连接依赖的最大关系集合。
(1）初始状态：S=Φ；R={R1,R2,…,Rn}；
(2）如果存在一对关系Ri和Rj在属性A上站点依赖，且Ri∞CRj包含在Q中，其中C包含A，那么将Ri和Rj放入S，并在R中删除；否则，该算法终止，返回S。
(3）如果Rk∈R且Rk∈S，循环做如下操作：如果S中的关系Rj与R中的关系Rk在公共属性B上站点依赖，且Rj∞BRk在Q中或可由Q导出，那么可将Rk放入S，并在R中删除。
(4）直到R=Φ或者R中的关系Ri在包含S的每个站点中都存在，则Q可以零数据传输处理。否则，将关系集合R中的关系Ri复制到包含S的各站点中。
2.2 算法的代价
2.2.1 查询代价的估算方法
在分布式数据库中，假定一个查询计划生成代价为QC，则QC主要包括查询的局部处理代价LT和站点之间的通信代价CT，即：
通信代价CT可用如下公式估算：
其中：C0为一次通信初始化产生的时间开销，在硬件条件固定、网络环境稳定的情况下，可作为常量处理，以s为单位；C1为站点间数据传输率，即单位数据传输所产生的时间开销，以s/bit为单位；X为站点间数据的传输量，以bit为单位。
局部处理代价LT包括I/O代价、存储代价（包括存储介质和存储技术的选择）和连接操作的计算代价。由于I/O代价和存储代价依赖于具体的计算机系统，本文仅考虑查询的计算代价对局部处理代价的影响。
2.2.2 基于连接依赖信息算法的查询代价分析
假定关系集合R={R1,R2,…,Rn}在站点集合S={S1,S2,…,Sm}上的数据分布如表4所示，且不同站点上的片段连接操作均不满足连接依赖，为关系集合R的全局连接查询设计一个简单的查询代价估算方法。
首先，选定一个关系Ri(i=1,2，…，n），使其保持各站点上的分片状态，然后将连接操作涉及的其他关系的片段复制到Ri所在的各站点，并通过各站点上数据的合并与连接获得正确的结果。由于在分布式体系结构中，不同站点的局部连接操作可以并行执行，所以在关系Ri保持分片状态下的全局连接查询的计划生成代价可由如下表达式给出：
通过计算上述i种策略的代价值QCi max，从中选取最低代价估算值的关系作为保持分片状态的关系，即：
选取关系Rk保持分片状态的策略为算法的最优执行策略。
上述算法的实现过程描述如下：
2.2.3 基于定量特征的查询代价估算
定义描述关系定量特征的相关信息，以便对上述策略的查询代价进行定量分析。设关系集合R={R1,R2,…,Rn}中关系与片段的定量信息如下：
(1）每个关系Ri在不同站点Sj上的片段表示为Rij。
(2）关系Ri中一个元组的长度，即所占用的字节数，表示为Size(Ri）。那么，各站点中关系Ri片段（水平分片）中元组的长度也为Size(Ri）。
(3）每个关系的元组数表示为Card(Ri），每个关系片段的元组数表示为Card(Rij）。
(4）关系Ri中属性A上不同值的个数表示为Val(A[Ri]）。
根据上述描述，关系集合Ri(i=1,2，…，n）向某个站点Sj(j=1,2，…，m）的通信代价CTj可以表示为如下形式：
由于Sj站点的局部处理代价主要为关系Ri各片段在该站点的数据合并连接的计算代价，因此在不考虑关系是否能引用快速存储路径或索引的情况下，局部处理代价依赖于连接操作中片段或关系的大小。采用Rasha Osman中提出的n个关系的连接操作代价评估模型[11]，构建分布式环境下站点Sj上的局部处理代价模型LTj:
其中：k=1,2，…，n，且k≠i;C为关系集合R中各个关系的公共属性集合。
由上述表达式可知，在关系Ri保持分片状态（即第i种策略）下，全局连接查询计划生成代价为：
在同一系统中同时考虑通信代价和局部处理代价时不能对其进行简单相加，需要根据具体应用环境对各种开销进行加权。p和q表示权值，且p+q=1。
3 实验设计与实验结果分析
实验使用的硬件环境为Intel®CoreTMi5-3230M CPU@2.60 GHz(2 600 MHz），内存为4 GB,SCSI硬盘1 TB，转速为10 000 r/min。操作系统为GNU/Linux，开发环境为JDK1.6，在实验环境中，采用上述所列配置Hadoop集群工作站，共计3台，其中1台为MapReduce主节点，作为HDFS名称节点，另外2台为MapReduce从节点，作为HDFS数据节点。
使用LUBM工具分别生成50,150,300所大学的测试数据，并在Hadoop集群工作站中部署测试数据，使测试数据的分布满足站点依赖。分别从LUBM的14个标准查询中选取其中6个查询语句进行测试实验。LUBM数据集文件大小如表5所示。
本实验重点比较PD算法、JD算法和R*算法在数据集LUBM(50）、LUBM(150）和LUBM(300）上的查询性能。通过比较6个标准查询的计划生成代价和查询响应时间，验证算法的有效性。每个算法执行5次，取其均值。对比实验结果如表6～表8所示。
从实验对比结果可见，在数据量较小的情况下，基于JD算法的计划生成代价稍劣于PD算法，但要优于R*算法。随着数据量的增加，基于R*算法的查询计划生成代价值呈指数级增长，查询性能急剧恶化，而JD算法的计划生成代价仍近似于PD算法。这是由于R*算法不考虑站点依赖问题，需要将各站点的关系或者关系的片段分别复制到指定站点执行局部处理，然后选择总代价最小的策略作为最优策略，站点间的通信代价和局部处理代价随着数据量增加而急剧上升，查询效率急剧下降。
下面对三种算法在数据集LUBM(300）上的查询响应时间进行对比分析，实验进行5次，取平均值，实验结果如图2所示。
由图2可以看出，JD算法具有较好的查询响应时间，在大数据量环境下，与PD算法的响应时间差别不大，但明显优于R*算法。因此，本文提出的基于连接依赖信息的连接查询优化算法是可行的，具有较好的寻优效果和实际价值。
4 结语
本文在分析利用站点依赖信息的算法和分片复制算法特性的基础上提出了利用连接依赖信息的分布式连接查询优化算法。算法的测试与结果表明，在基于多站点的连接查询中，该算法可极大地缩减网络的通信代价和局部计算代价。尤其当基于连接查询的大部分元组都能在本地站点找到，仅有少量元组需要从远程站点获取时，该算法可获得最佳性能。反之，该算法将退化为R*算法。
由于本文提出的算法的查询优化过程没有考虑查询结果向目标站点的传输代价，因此在连接操作返回的元组数较大的情况下，将产生额外的通信开销，从而给该算法带来负面影响。
参考文献
[1]赵光亮.基于半连接算法的分布式数据库系统查询优化技术[D].杭州:浙江工业大学,2013.
[2]钱磊,于洪涛.改进的半连接查询优化算法[J].燕山大学学报,2012,36(2):178-182.
[3]魏士伟,黄文明,康亚娜,等.分布式数据库中基于半连接的查询优化算法研究[J].计算机应用,2007,27(6):34-39.
[4]仝武宁,冉崇善,李宏斌.半连接查询优化算法的研究[J].计算机工程与设计,2011,32(3):972-975.
[5]陈钟,叶雪梅,青宪,等.一种改进的分布式数据库查询优化算法[J].计算机应用,2008,28(2):233-237.
[6]FAN Y Y,MI X F.Distributed database system query optimization algorithm research[C]//Proceedings of 2010 3rd IEEE International Conference on Computer Science and Information Technology.Chengdu,China:IEEE,2010:657-660.
[7]KUMAR T V,VIKRAM S,AJAY K V.Distributed query processing plans generation using genetic algorithm[C]//Proceedings of 2010 International Conference on Data Storage and Data Engineering.Bangalore:IEEE,2010:38-45.
[8]邵佩英.分布式数据库系统及其应用[M].3版.北京:科学出版社,2012:123-127.
[9]龚浩.分布式数据库查询处理和优化算法的研究[D].重庆:重庆大学,2005.
[10]张瑞芳.分布式数据库的查询优化方法设计与实现[D].成都:电子科技大学,2010.
[11]OSMAN R,KNOTTENBELT W J.Database system performance evaluation models:a survey[J].Performance evaluation,2012,69(10):471-493.
基于分块的连接算法实现 篇2
1 技术背景
当前计算机缓存Cache容量是十分有限的,假设两个表的两列A和B在做哈希连接(Hash Join),小表的列为A,在B列上建哈希,连接过程第一步是先将A、B两列数据加载到内存中,一般讲内存是够用的,将A的部分数据加入Cache中,遍历A在Cache中的每条数据,与B中数据哈希值进行比较,如果哈希值跳跃比较大,会导致哈希值频繁在Cache中被换入换出,就导致花费大量时间,根据一定的规则和算法把哈希值相近的数据放在一块就能避免这种问题发生[1]。
2 设计与实现
2.1 分块连接算法设计思想
分块连接(Partition Join)算法基于当前计算机的体系结构以及计算机的工作原理进行设计优化,采用分块策略与一般的Hash Join算法比较,性能有了大幅提升。
该算法是通过提高Join操作的内存访问性能来获取性能,哈希连接算法是现在最流行的一种算法,其为了找到内部关系的值,采用了一个对哈希表的随机访问模型,建哈希表的那个表称为内部关系,外部关系就是被顺序扫描的那个表。内存访问只有在内存能够缓存下内部关系和其哈希表时才能更高效地处理,如果内部关系和其哈希表没有被缓存在Cache中,它们的访问就会出现缓存失效(Cache Miss)问题,这样大部分的执行时间就被由于缓存失效而导致的换入换出时间所占用[2]。
分块连接算法的核心思想是减少上面所讲的缓存失效情况发生,其利用内存的有序化和额外的CPU工作来减少缓存失效次数,该算法提供了这样一种新型访问方式,首先由于内存的容量有限就要进行局部连接,对内外关系进行分块,这是有必要的,这样缓存就能容纳相对于表来说小得多的块,接着就是要找到内外关系中相匹配的块,在相应的块上执行哈希连接。一般来讲,Cache Line的大小是分块时分块大小的参考,一般不应大于Cache Line的大小,如果一个表很大的话,分块的个数也会比较大,如果按通常想的分块方法假设将一个表分成A块,在分块的过程中需要A个缓存空间,然后遍历这个表,将表中每一行插入到相应的缓存空间,这样A个临时的输出指针也是必要的,而且它们就在内存中。但是,当A非常大缓存不够用时,输出指针就不会被缓存,出现大量缓存失效情况,降低了效率,分块算法的性能下降,分块连接算法性能也不会很高。采用多趟扫描分块的方法可以解决这个问题,一般来讲,分块是采用哈希值的后面N位进行计算的,N位相同的为一块,采用多趟扫描分块算法后,由于每一遍只处理少数的块缓存,这样缓存指针的缓存失效次数就会大大降低[3]。
2.2 分块算法实现
2.2.1 分块算法描述
Radix Cluster算法[4]就是要描述的分块算法,它是通过多次分块完成的,首先基于给定的趟数(Passe)将一个表划分成K个块(Cluster),比如表T1和T2都通过2趟被分成了8块,假设按一列Hash值的第B位分块,趟数为P,每一趟按Bp位从左边开始分块(B1+…+Bp=B),最终分成的块数为K1*K2*…*Kp=K,其中每经过一趟每一块还会再分为Kp=2Bp个新块,这种类似于分裂的算法,在开始时,整个表被看作一个块处理,并且被细分成K1=2B1个块,最终经过2趟分裂成8块。
首先将这两个表T1和T2看作是两两个独立的块,选取位数(Cluster Bit)为3,趟数为2,这样卫门就按哈希值的后3位分块并且要进行2次,如果第一趟按2位计算,第二趟按1位计算的话,首先要计算表T1的哈希值的后3位,第一趟按2位取,即哈希值的后两位,这样就分成了4块,它们的哈希值尾数为00、10、01和11。第二趟对第一趟结果的所有块按第3位进行划分,这样每一个块又被一分为二,类似的对表T2也做同样的操作。接下来,就要对T1和T2分块后的结果做哈希连接,这时不需要对所有的进行哈希连接,只要对应的块之间做即可,最终的结果就是所有分块连接后的集合。
2.2.2 基数和趟数的选取原则
假设分块位数(Radix Bits)为B,也就是说能将该表分成的块数为H=2B,用P来表示分块的趟数,Bp表示每趟分块位数,为了评估该分块算法的性能,尤其是分块所用的趟数和位数,及其每一个趟所对应的位数,给出了一个该算法的指导准则,用不同的位数、趟数和块大小作为参数对内存相关的事件,如缓存失效、内存换入换出、TLB失效等来进行评估,CPU的耗时包括在总体执行时间内。根据前面讲的计算机结构等原则,分块的大小应为一个合理的值,太小和太大的的话都和没有分块没什么区别。基于程序顺序访问速度比较快的原则,为了避免数据间大范围移动,采取了多次分块的方法,同时考虑数据量和Cache Line的大小关系,分块太多有时会影响性能,一般应遵守下面的原则:(1)每块大小等于一个Cache Line大小;(2)趟数根据具体的数据量应为1~13,最优的分块策略目前还没有特别好的办法去计算,只能通过实验不断尝试,得出最优块数及对应的位数和趟数。
2.2.3 Radix Cluster算法实现
实现Radix Cluster算法描述如下:
2.3 哈希连接算法实现
哈希连接是大数据集连接时常用的方式,该算法核心功能分为两个,一个是哈希值的计算,另一个就是哈希值冲突问题的解决。一般的,桶链是解决哈希冲突的有效方法,其中空间优化问题也是值得讨论的,在连接时使用循环比较哈希值的方法.
一般的哈希连接算法实现要经过下面几步,首先计算内存评估值,用于建哈希,然后根据评估值的大小申请内存空间,结果就存在申请的内存空间中,接着对小表上某一列建哈希值,大表上相应列上的每条数据和小表上对应列进行比较,如果哈希值一样,就将数据放到结果空间上,如果结果空间不够用,还需要扩展空间,然后再插入数据。
2.4 分块连接算法实现
分块连接算法首先是一个分块算法,其次是在分块基础上的哈希连接算法,它是基于现代计算机体系结构特点对哈希连接算法的一种优化。
2.4.1 分块算法空间优化
需要分配空间用于存放分的每一个块,该分配多少空间,多大空间才比较合理,需要特别考量,如果分配的空间不合理,过小的话不够放,过大的话不仅会增加内存的开销,而且会引入更多内存的换入唤出,通常为了获取合理的内存空间采用动态调整分配内存的方法。
假设一个表关系的大小是100兆,分块连接算法需要将表分成5块,分块时首先根据表的大小申请一个100兆的内存空间,然后将申请的100兆空间平均分配给每一个块,这样每个块占有20兆的内存空间。假设块1只用了10兆还余下10兆,就将余下的空间挪给下一个块即块2使用,块2就有30兆可以使用,如果30兆正好够块2使用,假设现在块3的大小是30兆,显然开始分配的空间不够用的,这时又需要向下一个块做动态调整。这时向块4借用10兆的内存空间,块3就拥有30兆的内存空间,满足了要求、这样以此类类推,根据块的大小和初始分配的内存大小,将多余的内存分给下个块或向下一个块借用内存空间,这种内存分配策略就是动态内存分配策略,可以大大节省内存空间,而且这种动态调整方法只涉及指针调整不需要额外的临时空间,开销很小。
2.4.2 分块连接算法的实现
分块算法就是先分块然后再做哈希连接,分块是对左右两列关系都要进行的,分块趟数和位数决定了分块的具体情况和整个算法的性能状况,前面的分块算法中已详细阐述过,接下来就要对在内存中的分块进行哈希连接了,针对左右两边相关分块(根据Hash值决定哪些是相关的分块)进行哈希连接,哈希连接算法的实现原理和过程前面已描述过。
实现分块连接算法简单描述如下:
3 结语
通过深入理解现代计算机体系结构特点及工作机制,基于对Hash Join算法的分析研究和理解,对Hash Join算法进行优化,针对Hash Join算法目前存在的性能瓶颈,以现代计算机存储结构作为基础,提出并实现了一种基于Prtition(分片)的连接算法。
参考文献
[1]A Ailamaki,DJ Dewitt,MD Hill,et al.DBMSs on a Modern Processor:Where Does Time Go?[A]//Proceedings of 25th International conference on Very Large Data Bases(VLDB'99)[C].Edinburgh:Morgan Kaufmann,1999:266-277.
[2]KC Yeager.The MIPS R10000 Superscalar Microprocessor[J].IEEE Micro,1996,16(2):28-41.
[3]S Manegold,P Boncz,N Nes,et al.Cache-Conscious Radix-Decluster Projections[A]//Proceedings of Thirtieth International Conference on Very Large Data Bases(VLDB'04)[C].Toronto:Morgan Kaufmann,2004:684-695.
环切刀轨无跳刀过渡连接算法 篇3
计算机辅助制造(CAM)技术在口腔医学领域中的应用越来越广泛。将CAM技术引入口腔修复领域,利用CAM技术高效率、高精度的特点可大幅提高修复体制作的效率,明显缩短治疗周期,充分保证修复体的精度[1]。目前世界上最先进的口腔CAM系统完成一个全冠的制作,全程最快只需5min左右,患者只需就诊一次就可以完成治疗。在口腔修复体整个加工过程中,粗加工占用大部分时间,因此提高粗加工加工效率是关键,在由加工区域最外边界(外环)和加工区域内岛屿边界(内环)构成的连通域内环切刀具轨迹主要由刀轨环轨迹[2,3,4,5,6,7]和轨迹环之间过渡连接[8,9,10,11,12,13,14,15]两部分组成。环切刀轨环计算完成后相互独立,直接加工会产生大量对实际加工没用的走刀(如快速抬刀、快速下刀、快速移动),影响加工效率,并且刀具频繁的跳刀与突进会在被加工模型的切削表面留下刀痕,影响加工质量。因此,刀轨环轨迹之间的过渡连接质量好坏对提高修复体的加工效率和质量非常重要。
目前国内外对环切刀轨环的过渡连接作了一定的研究,解决方式大体上可分为两种:①基于刀轨树结构过渡连接刀轨环。Guyder[8]提出了环切刀轨过渡连接应该满足的基本准则,这些准则比较符合实际加工情况,但是文中算法把环过渡连接问题过于简化为刀轨环的排序。Park等[9]构建了多根节点刀轨树结构,通过遍历刀轨树实现子轨迹的无跳刀连接,但当加工区域边界个数为n时,会造成n-1次跳刀。Park等[10]在文献[9]的研究基础上把由刀轨环组成的多根节点树结构转化为单根节点结构实现无跳刀连接,当刀轨树根节点数目较多时转化工作需要大量额外计算,并且还会出现无法转化的情况,这样会增加算法的复杂度。Kim[13]根据刀轨环计算时建立的父子关系构建刀轨环关系树,计算具有父子关系的两个环之间距离最小的点,然后把两个环连接起来,把环切刀轨的连接简单看作是遍历刀轨环树,但此方法并不能总是实现无跳刀。Hao等[14]提出的算法同样是基于刀轨环关系树的,但是其算法中刀轨环父子关系不能在轨迹计算过程中获得,需要额外计算。张鸣等[15]构建了一种称之为区域树的树形数据结构,能够显著减少跳刀次数但并不能总是实现无跳刀。②把环过渡问题转化为其他算法数学模型。Castelino等[11]把环过渡问题转化为解决TSP问题以缩短空走刀时间,但是不能实现无跳刀。Hinduja等[12]基于Voronoi图提出环切刀轨连接算法,根据不同的过渡准则(减少跳刀、避免重复切削、减少开槽加工等)对刀轨环进行过渡连接,并对生成的刀轨作了对比分析,该算法可以有效减小刀具路径长度。与①相比,方式②不仅没有充分利用刀轨环之间的潜在拓扑关系,而且增加了计算复杂度。
根据上述研究,本文提出了基于单根节点刀轨环树结构的环切无跳刀刀轨过渡连接算法,该方法通过对刀轨环树的拓扑分解实现对刀轨环的编组,不仅获得了无跳刀刀轨,而且还使尽量多数目的刀轨环之间的过渡连接线段位于同一直线方向上。最后通过仿真实验说明了本文算法的有效性。
1 定义
为了系统地描述算法,对相关的概念术语进行定义。
定义1 刀轨环。当前加工层所在的水平面与被加工模型的刀位面的交线,即加工区域的初始边界,如图1a中外环L[0-1],内环I[0-1]、I[0-2]。经过m次等距计算后得到n个有效加工轨迹环,每个有效加工轨迹环为刀轨环(tool path loop, TPL),记为L[m-k](0≤k≤n) (内环等距形成的刀轨环记为I[m-k] (0≤k≤n))。内/外环的初始等距计算次数为0。例如,在图1b中,L[1,2]表示经过2次等距计算。
定义2 刀轨环父/子关系。刀轨环L[m-i]是由上次计算得到的刀轨环L[(m-1)-j]和内环I[0-k]的等距环组成,则L[m-i]的父环(L[m-i])Farther=L[(m-1)-j],L[(m-1)-j]的一个子环是L[m-i]。内环I[0-k]只与由部分I[0-k]等距环组成的刀轨环建立父子关系,则(I[0-k])Farher=L[m-i]。如图1b所示,L[1,2]和I[0-2]等距后得到刀轨环L[1,2]和L[2],则(L[1,2])Son={L[1,2],L[2]},L[1,2]和L[2]的父环均为L[1,2];L[1,2]和L[2]均为部分由I[0-2]的等距环组成,所以I[0-2]的父环可为两个环中的一个,例如(I[0-2])Farther=L[1,2]。
本文中算法在计算刀轨环时内环只向外等距一次,外环连续向内等距,在刀轨环计算的同时建立环之间的父子关系,所以当所有刀轨环计算完成后可以建立单根刀轨环关系树。图1c中的单根刀轨树结构是建立在图1b中刀轨环父子关系的基础上的。
定义3 过渡点、虚过渡点、过渡点对。具有父/子关系的两刀轨环Li/Lj上存在两点Pi和Pj,并且Pi和Pj之间的距离为刀轨行间距δ,则称Pi/Pj分别为Li/Lj上的过渡点(图2)。在过渡点Pi之后插入P′i,并且P′i=Pi,则称P′i为Li上与Pi相对应的虚过渡点。Pi、P′i、Pj、P′j组成过渡点对(Pi,P′j)和(Pj,P′i),如图2b所示建立过渡点对元素之间连接关系,L[1]上过渡点P2与父环L[0-1]的虚过渡点P′1具有连接关系,(P2)Farther=P′1,与子环L[1,2]上虚过渡点P′3具有连接关系,(P2)Son=P′3;对于虚过渡点P′2,则(P′2)Farther=P1,(P′2)Son=P3,构成过渡点对集合Γ={(P1,P′2),(P2,P′1),(P2,P′3),(P3,P′2)}。
2 刀轨环编组
数控加工过程既是几何过程又是物理过程,刀轨环的计算除了依据几何运算来构建外,还要考虑到轨迹之间的过渡连接对实际加工的影响。“无跳刀”刀轨不仅要提高加工效率,而且还要考虑到环之间的过渡连接对实际加工的影响。如图3所示,图3a中的刀轨环之间的过渡线段位于不同直线上,类似台阶式,不仅增加了走刀过渡路径,还会造成刀具在实际加工中频繁地沿着不同方向从父刀轨环进入子环或是从子环返回父环引起机床的振动。文献[10]指出不恰当的过渡连接可能造成重复走刀,而图3b中的刀轨环之间的过渡线段位于同一直线方向上,可以避免上述缺点。因而有必要使尽量多的刀轨环之间过渡线段方向相同。
2.1 刀轨环树拓扑分解
刀轨环的组成属性有三种:①完全由外轮廓的等距环构成;②完全由内轮廓环的等距环构成;③由内/外轮廓环的等距环复合构成。前两种能够保持环之间等距信息的连续性,而③会阻断这种等距连续性,称之为“分界环”,其对应刀轨环树中的节点为“分界节点”。如图4a所示,刀轨环L[1,2]组成属性为③,其对应刀轨环树中的分界节点如图4b所示,刀轨环L[1,4]和L[1]之间不能用一条直线段连接,只能连接L[1,4]、L[2,3]、L[1,2],如图4c所示。
文献[10]中指出一种特殊情况,内环等距后可能构成“内包”等距环,如图5a、图5b中内环I[0-1]等距形成内包环I[1],由于L[1,2]和L[2]部分由I[0-1]的等距环I[1,2]组成,则I[0-1]的父环是L[1,2]或L[2]。内包环只与构成该内包环的内环之间存在等距的连续信息,因此内环可以阻断等距的连续性,也是“分界环”。由上述可知,内环和由内环等距环构成的刀轨环均是“分界环”,如图5c所示。
根据分界环对应的分界节点,对刀轨环树进行拓扑分解,分解为一系列拓扑子树(sub tree,ST),进而对刀轨环进行编组,提取出可以用一条直线段相互连接的编组环集合Ω,使最多数目的刀轨环直线过渡连接。步骤如下:
(1)查找层数最大的并且没有被访问过的叶子节点环作为初始节点环(inital loop)LI,设当前刀轨环(current loop)为LC,LC←LI,若LI存在,则转步骤(2),否则转步骤(6)。
(2)If (LC)Parent是根节点,转步骤(5);
(3)标记LC为已访问,保存LC,LC←(LC)Parent,转步骤(2)。
(4)标记LC为已访问,保存LC和(LC)Parent,转步骤(1)。
(5)标记LC和(LC)Parent为已访问,保存LC和(LC)Parent,转步骤(1)。
(6)刀轨环树拓扑分解结束。
以图5c中含有分界节点的刀轨环树为例,刀轨环树拓扑分解结果如图6所示。刀轨环节点I[0-1]、L[1,2]、L[2]为分界环,第一次拓扑分离的初始环为I[1],其父环I[0-1]为边界环,则标记I[1]为已访问,保存I[0-1]和I[1]为一个拓扑子树ST-1。拓扑子树ST-2、ST-3、ST-4、ST-5的提取与ST-1类似,当ST-6分离计算时,初始环为L[2],其父环L[1]在拓扑子树ST-5提取时已经被访问过,则保存L[2]和L[1]后提取结束。
2.2 环集合过渡线段
编组环集合Ω中有n个刀轨环元素,由于环集合保留了等距连续信息,所以环集合中最内/外层环LIM/LOM上存在点PIM/POM,并且线段PIMPOM的长度为(n-1)δ,则PIMPOM即为该环集合的过渡线段LSeg。如图7a所示,编组环集合为L[1,2]、L[1]、L[0-1],n=3,LIM=L[1,2],LOM=L[0-1],环集合过渡线段长度
2.3 构造过渡点对
根据定义3,编组环集合Ω中的每一个刀轨环元素和其过渡线段LSeg的交点为过渡点。如图7b所示,过渡点P1、P2、P3为LSeg分别和L[0-1]、L[1]、L[1,2]的交点,P′1、P′2、P′3为虚过渡点,构成过渡点对集合Γ={(P1,P′2),(P2,P′1),(P2,P′3),(P3,P′2)}。
3 环切无跳刀刀轨生成
根据过渡点对建立父子刀轨环之间的连接关系实现无跳刀刀轨的提取,令外环为顺时针方向,内环为逆时针方向,具体提取步骤如下:
图8所示为上述刀轨提取流程,在刀轨环L[0-1]上选择点Q作为刀轨提取初始点PI,PC←PI;由于PC不是过渡点转向步骤(3),沿着刀轨环L[0-1]遍历至过渡点P1,PC←P1,转向步骤(4);过渡点(P1)Farther为空,进入子环的指针(P1)Son非空,并且P′2没有被访问过,则转向步骤(5)进入子环L[1],PC←P′2,沿着刀轨环L[1]遍历至过渡点P4;P4与P1情况相同,则PC←P′5,进入L[2]后遍历至P6,然后进入L[1,3]遍历至P7;由于(P7)Son为空则返回其父环L[2],按照图8b所示依次遍历刀轨环。当遍历至过渡点P3时,(P3)Son为空,并且与P3组成过渡点对的父环上的虚过渡点P′2已经被访问过,则在步骤(6)中PC←P2;(P2)Son为空,但是(P2)Son已经被访问过,则返回环L[0-1],PC←P′1,沿着刀轨环L[0-1]遍历至初始点Q,刀轨提取结束。
4 实例验证
本文算法已应用于南京航空航天大学开发的DentalEngineer软件中。图9所示加工对象为三维桥体牙齿模型(31mm×13mm×11mm), 当前加工层所在的水平面和被加工牙齿模型刀位面的交线的最外轮廓为刀具走刀的最大区域。图10所示为在图9加工区域内应用本文算法规划的环切刀轨,可以看出所有的刀轨环之间建立了连接关系,只有一次进刀和一次跳刀,在加工过程中无跳刀,并且没有重复切削。实例刀具轨迹仿真结果如图11所示,轮廓的加工质量较好。
在数控加工中,粗加工阶段常用的走刀方式有单向行切(Zig)、双向行切(Zig-Zag) 、环切和螺旋线切等方式,在实例1的加工区域内用上述走刀方式实现的走刀刀具轨迹如图12所示,其中图12中的环切刀轨指的是各个刀轨环之间没有进行过渡的刀轨。
表1中的时间数据是在德国imes-icore公司生产的型号为CORiTEC 340i的面向齿科修复体加工的专用机床上统计得到的。加工参数为:进给速度2000mm/min、刀轨路径间距0.4mm。加工刀具为直径2mm的球头刀。从表1中的对比数据可以看出,本文算法生成的环切刀轨由于在加工过程中没有跳刀,使G00路径长度显著缩短,同时总的走刀路径长度也缩短了,从而缩短了加工时间,提高了加工效率,该走刀方式要明显优于单向行切、双向行切、环切三种走刀方式。尽管螺旋刀轨连续性较好,走刀平稳,适用于高速加工,可以在一定程度上减少刀具的跳刀次数,但一般适用于没有岛屿的加工区域,由于牙齿修复体有牙尖、牙窝等表面形态特征,所以加工区域常常存在多个岛屿,表1中的数据也说明了在牙齿修复体加工中应用本文算法生成的刀轨在加工效率方面要优于螺旋线刀轨。
5 结论
(1)刀轨树结构构建简单。采用特殊的等距策略,充分利用刀轨环等距计算建立刀轨环之间的父子关系,构建单根节点刀轨树避免了多根树向单根树的转化,简化了计算复杂度。整个算法的数据结构清晰,便于在程序中实现。
(2)刀轨树拓扑分解得到的编组环集合元素之间过渡直线方向相同不仅提高模型的加工质量,而且提高加工时走刀的稳定性,减少机床的振动。
(3)实现了跳刀次数为零,并且没有重复切削。
(4)正如Park等[10]和Hinduja等[12]所述,刀轨环的过渡连接需要满足一些符合实际加工的准则,比如避免重复切削、减少开槽加工、减少跳刀次数、刀轨路径长度最短等,但是,要找到能够同时满足这些条件的过渡连接方式比较困难,因为有些技术条件是相互矛盾的,如避免重复切削和减少开槽加工,所以可以根据实际加工条件选用恰当的刀轨连接策略。例如本文中算法应用于口腔修复加工中的粗加工阶段,减少跳刀次数和避免重复切削可以显著地缩短加工时间。鉴于牙齿修复体加工时切削量小,少量的开槽加工对刀具磨损和整体加工质量影响较小,因此本文算法以减少跳刀次数和避免重复切削为主要准则。
连接算法 篇4
关键词：多连接查询优化,免疫遗传算法,抗体浓度,免疫接种
1 引言
随着Internet技术与信息管理系统的发展与普及, 基于数据库、数据仓库的联机事务处理和联机分析处理已成为银行、企业、政府等部门最为重要的计算机应用之一。在这些应用中, 多连接查询操作在各种数据库操作中所占比重非常大, 而且, 执行多连接查询操作时, 运算先后次序不同, 查询请求响应的时间就不同。多连接查询优化就是对于由N个 (N>10) 关系的连接操作构成的一个查询请求, 在合理的时间内找到一个最佳的查询执行计划。一个好的查询计划往往可以使程序性能提高数十倍。然而, 在大规模数据库、数据仓库、联机分析处理的环境下, 参与多连接查询运算的表的数目较大, 导致多连接查询优化的计算复杂性非常大。因此, 多连接查询优化对获得好的查询性能至关重要[1]。
多连接查询优化问题是一个NP问题, 高效的优化算法是提高查询性能的关键问题。目前, 已有一些算法解决这个问题, 这些方法在某些方面提高或改进了查询性能。文献[2]利用增量启发式信息来初始化种群, 提高了遗传算法的收敛速度。文献[3]在遗传算法的过程中加入了模拟退火操作, 有利于保持物种的多样性。文献[4]在查询优化中, 结合哈希过滤方法, 减少查询执行计划的计算代价, 从而提高多连接查询效率。文献[5]结合遗传算法和模拟退火算法提出了一种混合算法, 并将其应用到多连接优化问题, 改进了获得最佳查询计划的性能。本文的主要内容是将免疫思想和遗传算法相结合, 设计一个多连接查询优化算法, 在保持遗传算法优良特性的前提下, 加入抽取疫苗、接种疫苗、疫苗选择等免疫算子, 抑制优化过程中出现的退化现象, 提高算法的寻优能力。
2 多连接查询优化问题
多连接查询优化问题可以描述为合理时间内在搜索空间中找到一个最好或者近似最好的关系连接次序问题。搜索空间常采用左线性树空间, 并根据关系代数的等价变换规则, 利用“选择操作下移、投影操作尽量先做、避免笛卡尔积”等启发式信息。多连接查询优化问题可简化为一个带约束的组合优化问题, 求解该问题的数学模型如下。
上述模型中, C表示多连接查询的代价, ti表示左线性树中的内部结点, r和s是ti的左右子结点 (即ti是r与s连接后的中间结果) , n (ti) 表示关系ti的元组个数, n (r) 和n (s) 分别表示关系r和s的元组个数, R是关系r和s的公共属性, V (A, r) 为关系r中属性A的不同取值的个数。
对于某个具体的多连接查询, 假设X为全部可能查询执行计划的集合, X中每个成员x都有其代价C (x) , 则需要找出X中的某个查询执行计划q (q∈X) , 使得q满足:
多连接查询优化的目标是优化时间与找到的查询执行计划x的执行时间之和最小。
3 免疫遗传算法的基本思想
免疫遗传算法是借鉴生物免疫机制提出的一种改进的遗传算法。它模拟生物抗体浓度自适应调节过程, 在算法中加入免疫记忆功能, 提高了算法的收敛速度。由生物免疫原理可知, 生物免疫系统对入侵生命体的抗原通过细胞的分裂和分化作用自动产生相应的抗体来抵御, 其中部分抗体作为记忆细胞保存下来。当相似抗原再次侵入时, 记忆细胞将被激活并迅速产生大量抗体, 体现了免疫系统的记忆功能。抗体与抗原结合后会通过一系列的反应而破坏抗原。同时, 算法根据抗体与抗原的亲和力和抗体的浓度进行选择操作, 亲和力高且浓度小的抗体选择概率大, 这样就抑制了群体中浓度高的抗体, 保持了群体的多样性, 体现了免疫系统的自我调节功能[6]。免疫遗传算法的流程如图1。
4 多连接查询优化的免疫遗传算法设计
本文吸取免疫遗传算法的思想, 结合多连接查询优化的特点, 将它用于求解多连接查询优化问题。首先, 将免疫遗传算法中涉及的基本概念与多连接查询优化的基本概念进行对照, 它们之间的对应关系如表1所示。
4.1 初始抗体的产生、编码、适应度、亲和度和抗体浓度
初始抗体的产生可以先从记忆细胞库中搜索该问题的记忆抗体, 从而生成初始抗体, 不足的抗体则在解空间中随机产生。这个初始抗体产生的方法提高了初始种群中抗体的适应度, 更快的找到全局最优解。
抗体的评价主要用抗体与抗原的适应度以及抗体和抗体的亲和度来表示。适应度函数由 (1) 、 (2) 、 (3) 式计算出cost值, 再求其倒数。抗体v的适应度函数:
适应值越大, 被选择的概率就越大。
抗体v和抗体w的亲和度函数:
其中E (2) 为v和w的平均信息熵。通过这些平均信息熵可以实现抗体的多样化。
抗体v的浓度计算函数如下:
其中, qv表示和抗体v有较大亲和度的抗体个数, N表示全局抗体个数。通过 (8) 式能有效地抑制抗体的过分相似。
4.3 选择算子、交叉算子、变异算子的设计
选择算子采用最优保存策略和基于抗体浓度选择策略相结合。最优保存策略使得适应值最好的抗体尽可能保留到下一代群体中, 以免交叉和变异运算破坏种群中的优秀解, 保证了算法的收敛。群体的浓度定义为群体中相似抗体所占的比率。基于抗体浓度选择策略原理是, 群体更新时, 亲和度高的抗体不断提高, 到达一定的值时则抑制这种抗体的产生。也就是说, 抗体集合中与抗体x基因相似的抗体越多, 则抗体x被选中的概率就越小;反之, 与抗体x基因相似的抗体越少, 抗体x被选中的概率就越大。基于抗体浓度选择策略不仅能有效地抑制浓度过高的抗体繁殖, 保证抗体的多样性, 避免算法陷入局部最优值, 而且使含有有效进化基因的低适应值个体也可获得繁殖的机会。
交叉操作时通过交换两个父个体的一部分来产生新的子个体, 该操作要根据一定的概率进行。
变异操作时以一定的概率随机地改变个体中某个基因, 以提供初始群体中不存在的基因或找回选择过程中丢失的基因, 为群体提供新的内容。变异算子将个体的基因链的各个基因按某个概率进行变异。变异本身是一种局部随进搜索, 与选择算子结合在一起, 保证了免疫遗传算法的有效性, 使得免疫遗传算法具有局部的随机搜索能力, 同时, 也使得免疫遗传算法保持种群的多样性, 以防止出现不成熟收敛。变异算子采用单点基因换位法。
4.4 疫苗接种、免疫选择
首先, 根据多连接查询问题的特征信息和先验知识得到该问题的疫苗。个体接种疫苗的概率取0.6, 接种疫苗包括对于个体x接种疫苗, 对群体接种疫苗两个步骤。第一步, 按照先验知识来修改个体x的某些基因位上的基因或其分量, 使所得个体以较大的概率具有更高的适应度。第二步, 对群体进行接种疫苗, 从种群中随机抽取Nα个个体进行接种。为了使个体接种疫苗后满足约束条件, 作如下处理:设接种疫苗前, 个体的某基因位上取值为vi, 接种疫苗后取值为vi′, 则将原个体基因位上取值为vi的基因与取值为vi′的基因对换。免疫选择对加强接种算子有积极作用, 消除其负面影响, 防止群体的退化, 具有较强的鲁棒性。
免疫选择操作分两步完成。第一步是免疫检测, 即对接种了疫苗的个体进行检测, 若其适应度不如父代, 说明在交叉、变异的过程中出现了严重的退化现象。这时保留父代个体。如果子代适应度优于父代, 则选择子代。
5 总结
免疫遗传算法已经在一些领域的优化计算中取得了很好的效果。本文结合多连接查询优化问题的实际特点, 提出应用免疫遗传算法解决多连接查询优化问题。免疫遗传算法在遗传算法的基础上引入了基于浓度的抗体抑制和促进的免疫算子, 能有效地抑制浓度过程的抗体繁殖, 保证抗体的多样性, 避免算法陷入局部最优值;根据先验知识保存最优抗体, 有效提高初始种群的质量;疫苗接种使得问题的特征信息能注入抗体, 保证算法的快速有效收敛。
参考文献
[1]玄萍, 李金宝.基于机群系统的并行多连接查询优化算法[J].黑龙江大学自然科学学报, 2006, 23 (6) :821-826.
[2]董红斌, 梁意文, 康立山, 等.利用启发式信息优化多连接查询的遗传算法[J].武汉大学学报 (自然科学版) , 1999, 45 (5) :743-746.
[3]杨艺, 李延东.退火遗传算法的多连接查询应用[J].计算机工程与应用, 2004, 34:190-192.
[4]王果, 徐仁佐.结合哈希过滤的一种改进多连接查询优化算法[J].计算机工程, 2004, 30 (7) :57-59.
[5]闫晓慧, 董丽丽, 张慧娜.基于混合遗传算法的关系数据库多连接查询优化策略[J].微电子学与计算机, 2008, 25 (11) :181-183.
连接算法 篇5
目前异构数据层集成方案中, 异构数据库集成是为用户提供一个统一的查询接口, 用户不必关心数据库的位置、数据库类型以及数据的存储格式, 就像在本地查询一样, 数据层中的查询是将用户基于全局模式提交的查询动态分解为子查询到各异构数据库执行。
2 异构数据层与半连接
2.1 异构数据层集成中的查询
在面向服务的信息集成系统中, 每个数据源都是独立自治的, 其查询过程如下:用户提交的基于全局视图的查询, 由分解器分解为针对每个数据源的子查询, 然后按一定调度规则, 顺序执行子查询, 提交给每个数据源执行, 最后每个数据源将执行结果返回给中集成器, 其查询调度过程如图1。
2.2 半连接操作
半连接 (semi-join) 操作是由投影和连接操作导出的一种关系代数操作, 假定有两个关系R和S, 在属性R.a-S.b上作半连接操作可表示为:
R∞a-bS=R∞a-b (πb (S) ) 或S∞a=bR=S∞a=b (πa (R) )
站点1的关系R与站点2的关系S在属性R.a和S.b上的连接操作用半连接来实现的具体执行过程共5个步骤 (图2) :
(1) 在站点2的关系S属性b上做投影操作得到πb (S) ;
(2) 把πb (S) 送到站点1;
(3) 在站点1进行半连接, 得到半连接结果R′= (R∞α=b (πb (S) ) ) ;
(4) 再把R1从站点1传送到站点2;
(5) 在站点2执行连接操做R′∞=S得到最终的结果。
由半连接的执行过程可知, 采用半连接实现连接操作需要两次数据传输:连接属性投影结果πb (S) 和半连接结果R′。但在通常情况下, 这两次数据传输的总量要远远小于整个R关系的数据量, 所以选择半连接方法优化连接。
3 多关系半连接优化算法
普通半连接查询方法是按照关系间的连接顺序执行半连接, 其优点是处理简单, 不足之处是没有考虑到如何优化子查询的半连接顺序来进一步减少网络通信的代价。本文的基于多关系半连接查询优化算法是针对普通多关系半连接查询方法的不足之处而提出的, 即通过代价估算和半连接, 在如何进一步减少子查询的网络代价问题上进行了改进。
3.1 查询优化算法
由于半连接操作不具有对称性 (R∞a-bS≠S∞a-bR) , 所以选择合适的半连接方案能使连接的代价最小。半连接就是多个连接进行时根据半连接最优执行方案所构成的反映关系间优先级的。半连接反映了执行半连接操作的关系之间的优先级关系, 这种优先级执行关系针对单个连接操作, 减少了网络通讯代价。
3.2 算法性能分析
由于采用了半连接方法, 并优化了半连接操作执行的优先级关系, 降低了网络上的数据传输量, 从而节省了传输开销, 降低了网络代价。影响算法性能的另一个主要因素是全局查询响应时间。通过上述链式连接及星型连接的实验, 证明了基于多关系半连接的查询优化算法明显地减少了中间结果数据量, 降低了网络通信总代价。实验证明在分布式查询优化中, 与普通的多关系半连接算法比较, 基于多关系半连接的查询优化算法的优化效益更高。
假设16个连接操作所用时问分别为t1, t2, t3, …, t15, t16。优化前执行所有连接操作所用时间T=t1+t2+t3+…+t15+t16优化后9条路径并行执行连接操作所用时间分别为T1 (R1-R2-R3) =t2+t6, T2 (R1-R3-R5-R7) =t3+t8+t9, T3 (R1-R3-R7) =t3+t7, T4 (R1-R3-R8) =t3+t10, T5 (R1-R4-R5) =t1+t5, t6 (R1-R12) =t4, T7 (R9-R10-R12) =t12+t14, T8 (R9-R11-R6-R8) =t13+t15+t16, T9 (R9-R12) =t11。
由于9条路径并行执行, 所以执行所有连接所用时间为其中执行时间最长的一条路径的执行时间, 由于Ti
参考文献
[1]代宇, 程瑶, 刘莉.数字化校园网格信息集成方案研究[J].重庆邮电大学学报 (自然科学版) , 2008, 增刊:70-72.
连接算法 篇6
针对上述缺点,设计了一种可以实现酒店智能终端系统负载均衡的自动连接方法。该方法将现有的手动设置连接固定服务器的连接方式改进为能够开启终端设备后自动搜寻当前周期系统服务端综合负载最轻的服务器进行连接,避免了用户访问量集中于一台或某几台服务器而另外存在空闲服务器的情况。此外,酒店在部署智能系统时无需进行手动设置连接服务器,酒店客户只需打开终端机顶盒设备即可自动连接上当前最佳服务器为其提供最优质服务。该项技术的核心采用的是一种经过改进的基于加权最小连接数调度的负载均衡算法,实现了平衡系统负载和整体处理能力的提高,为用户带来了满意的服务质量。
1 问题的提出及研究现状
涉及的酒店智能终端系统由嵌入式Linux云分支服务器与酒店智能终端机顶盒构成,其中嵌入式Linux是将Linux操作系统进行裁剪修改,使之能在嵌入式计算机系统上运行的一种操作系统。服务器与机顶盒接入到同一局域网内,通过路由器接入互联网。如图1 所示为该系统网络结构。
现有的负载均衡技术根据其实现方式不同,主要分为静态负载均衡和动态负载均衡两种。静态负载均衡根据服务器现有任务况和负载特性,通过调度算法预先制定一个分配策略来分配、执行任务[1,2]。动态负载均衡需要在系统运行过程中实时监测负载信息,动态地计算负载情况并分配,以达到整个系统的负载平衡。
1. 1 加权最小连接数算法
加权最小连接调度算法在把新的连接请求分配到当前连接数最小的服务器[3,4]的同时,加入权值来表示服务器的处理性能并可以动态地调整其权值。这种算法在调度新连接时会将请求分配给当前连接数与权值之比最小的服务器[5]。虽然这种算法解决了服务器性能差异问题,但仍是基于连接数的负载判断方式,没有考虑集群服务器实际的资源消耗,无法正确反映出当前真实的处理能力。
1. 2 加权轮转算法
加权轮转调度算法采用相应的权值表示服务器的处理性能,考虑到集群中各服务器处理能力之间的差异,为每个服务器分配指定权重的连接[6]。通过这种权值与轮询相结合的方式来使高性能的服务器优先收到访问请求,从而获得较多的连接。但该算法仍是一种无状态调度,在集群服务器具有较大处理时长的情况下,依然会负载失衡。
综上所述,需要全面考虑反映服务器集群负载情况的负载因子[7],使得终端设备可以自动选取最优服务器进行连接,最终达到实现整个酒店智能终端系统的负载均衡。因此,提出了一种在加权最小连接调度算法基础上进行改进的动态负载均衡算法,将连接数作为负载因子同CPU、内存等一起进行综合考虑并为其分配合理的权值,避免了原有算法中相同的连接数无法代表相同的负载的问题。
2 改进的基于加权最小连接调度的负载均衡算法
2. 1 系统模型
酒店智能系统模型采用4 台服务器、14 台机顶盒。每个机顶盒开启一定的线程数,与服务器进行数据的交互。本模型建立了四种不同的情况,即多终端数-多线程数、多终端数-少线程数、少终端数-少线程数、少终端数-多线程数。表1 为上述四种情况对应的具体数值。
如图2 所示为该系统模型示意图。
2. 2 负载因子
提出的改进的负载均衡算法需要解决如下问题: 1 以多大频率进行因子的采集; 2 采集什么参数可以准确地反映系统性能; 3 如何采集这些因子; 4 如何进行判决。下面介绍该算法使用的负载因子和计算方式并确定负载的权值向量。
对于嵌入式云分支服务器而言,为了使酒店智能系统能够达到负载平衡,选取如下动态负载因子作为判决条件: CPU利用率Ucpu、内存使用率Umem、网络带宽利用率Unetwork、服务器所连接的机顶盒数num。将num也作为负载因子考虑进去是因为从酒店服务质量出发,需要保证在有新的终端用户连接请求完成后对整体酒店用户不造成大面积影响,确保整个酒店系统的负载均衡与稳定。
嵌入式云分支服务器对于服务器性能参数的采集通过使用proc文件系统。它以文件系统的方式为访问系统内核数据的操作提供接口。程序可以通过proc获得系统信息且可以改变内核参数。
2. 2. 1 获取CPU利用率
在Linux的内核中,有一个全局变量: Jiffies。Jiffies代表时间,单位是1 /100 s。CPU的利用率就是用执行用户态加系统态的Jiffies除以总的Jifffies来表示。
在Linux系统中,通过采集/proc /stat文件的第一行记录,能够得到CPU的用户态,系统态,空闲态等状态下的不同的Jiffies。获取CPU使用情况通过输入命令: cat /proc /stat。
CPU利用率的计算方法为取间隔一段时间的两个采样点计算差值。
CPU利用率:
式中 Δuser表示一段时间内用户态的差值,Δsystem表示一段时间内系统态的差值,Δ( user + system +idle + nice) 表示一段时间内总的CPU占用的差值。
2. 2. 2 获取内存使用率
在Linux系统中,通过采集/proc /meminfo文件前四行记录,能够得到内存使用情况。获取内存使用情况通过输入命令: cat /proc /meminfo。
内存利用率:
2. 2. 3 获取网络带宽使用率
在Linux系统中,通过采集/proc /net/dev文件第四行记录,能够得到带宽使用情况。获取带宽使用情况通过输入命令: cat /proc /net/dev。
统计一段时间内Receive和Tramsmit的bytes数的变化,获得网口传输速率,再除以网口的带宽即为带宽的使用率。
网络带宽利用率:
其中,totalbindwidth为网口带宽,云分支服务器采用eth0 网口,带宽为100 Mbps。
2. 2. 4 获取当前服务器所连接的机顶盒个数
通过读取服务器数据库来获取当前所连接的机顶盒数。
2. 3 酒店智能终端系统负载均衡的判决
定义服务器性能向量Ui与权值向量α。
服务器性能向量
权值向量
综合负载值
系统中设计了一个采集负载因子程序运行于服务器上,该程序每隔10 s采集服务器的负载信息并以广播的形式发送出去。广播的格式为: ip_num_Ucpu_Umem_Unetwork。在每个采集周期,服务器发送的广播中的信息都能精确的反应出该服务器的负载性能。根据经验分析,1 min内系统平均有3. 3 个新用户申请访问,负载性能参数的采集周期定为10 s,则系统可以均匀地将负载分配到每个服务器上,实现动态的负载平衡,同时也可尽快发现故障节点,进行目标重定向,实现系统的高效性。
对应地,系统中的客户端也设计了一个程序运行于机顶盒上,该程序用于接收服务端的四台服务器循环发送出的广播数据并在1 min[8]中内将数据解析分析得出判决。根据公式( 3) ,找出最优服务器进行连接。公式( 3) 中权值向量的初始值均为1,本设计根据系统运行的实际情况加大或减小其中的某个权值以强调或减弱某方面的负载性能,从而实现整个酒店智能系统的负载均衡。
3 实验搭建
3. 1 嵌入式云分支服务器
云分支服务器是基于Linux的嵌入式服务器。硬件以Hi3716C芯片为核心,提供1. 5 GHz双CPU,2 G内存,4 Gflash,ARM开发板提供了SATA接口,可扩展2 T硬盘空间用以存储资源。软件上,云分支服务器的开发板上搭建了web服务器,支持usbwifi、文件管理、网页访问、vod点播以及直播、ETHERNET等。相较于市场上的服务器,基于ARM架构的云分支服务器降低了耗电量且更易于管理,减少了成本并简化了解决方案[9]。
3. 2 智能终端机顶盒
实验所需的智能终端机顶盒采用的是基于Android系统的数字机顶盒,内置Hi3716M芯片,该芯片采用ARM公司先进的Cortex A9 架构的处理器,高速处理能力可以满足酒店的多种需求。内置2 路以太网和2 路USB接口,提供灵活的连接方案。如图3 所示为实验所用机顶盒。
3. 3 实验环境的搭建
实验测试系统硬件环境如图4 所示。
为了验证算法的有效性,建立了一套系统模型。该系统中的服务端同时运行四台嵌入式云分支服务器,每台服务器的网口带宽为100 Mb /s,四台服务器各自间隔10 s采集一次负载信息并通过广播的方式循环发送。作为系统中的客户端,分别有3 台、1 台、5 台、5 台机顶盒连接四台服务器,并运行如表1 所示的线程数。此时测试新加入系统的机顶盒能否选取最优服务器进行连接从而实现整个系统的负载均衡并保持良好的稳定性。
4 结果分析
在实验中,选取负载个数、CPU利用率、内存利用率、网络带宽利用率作为服务器性能向量Ui=[num( Si) ,Ucpu( Si) ,Umem( Si) ,Unetwork( Si) ]。 根据文献[10]所提出的算法及其理论,初步选取权值向量 α =[0. 3,0. 25,0. 25,0. 2],该向量根据实验中的情况做动态调整,最终得出表2 所列结果。
在设计系的统模型中,使用方差来衡量新加入终端设备后负载的波动大小,方差越小,偏离均值的的程度越小,整个系统越稳定[11]。实验测试结果如表3 所示。
表3 中的第二列表示在新设备加入系统之前,系统中当前四台服务器的负载值大小。第三、四、五、六列列出了新加入系统的终端设备在分别连接服务器A、B、C、D后,四台服务器负载值的变化。其中,服务器A的IP为192. 168. 1. 34、B为192. 168. 1. 35、C为192. 168. 1. 28、D为192. 168. 1. 21。第5、6 行列出了四种连接方式对应的四台服务器的均值和方差。通过表3 数据可以看出,在连接服务器A后,系统的方差最小,为174. 4,意味着波动小,系统最稳定。经过实验验证,利用本文算法使得新加入的终端设备另整个系统更加稳定且实现了负载均衡。
5 结束语
通过分析现有的负载均衡算法,提出一种改进的加权最小连接数算法的动态负载均衡算法。该方法结合了多种算法的优势,将终端连接数作为影响因子与服务器各项性能参数做综合分析。较对比算法而言,策略选择由系统客户端进行判决,无需固定各个服务器负载的权重,系统服务端实时更新性能参数广播,充分考虑到了多云分支服务器的动态实时负载变化,算法最终确定了各项负载因子的权重向量,合理的分配了终端用户的连接请求,实现了整个酒店智能终端系统的负载均衡。
参考文献
[1]郑洪源,周良,吴家祺.WEB服务器集群系统中负载平衡的设计与实现.南京航空航天大学学报,2006;38(3):348—349Zheng Hongyuan,Zhou Liang,Wu Jiaqi.Design and implementation of load balancing in WEB server cluster system.Transactions of Nanjing University of Aeronautics&Astronautics,2006;38(3):348—349
[2] 蔡嵩,张建明,陈继明,等.云计算环境中基于朴素贝叶斯算法的负载均衡技术.计算机应用,2014;34(2):360—361Cai Song,Zhang Jianming,Chen Jiming,et al.Load balancing technology based on Naive Bayesian algorithm in cloud computing environment.Journal of Computer Applications,2014;34(2):360—361
[3] 买京京,龚红艳,宋纯贺.集群系统中的动态反馈负载均衡策略.计算机工程,2008;34(16):114—115Mai Jingjing,Gong Hongyan,Song Chunhe.Dynamic feedback load balancing strategy in cluster system.Computer Engineering,2008;34(16):114—115
[4] 刘道谱,涂海宁,顾嘉.电力信息系统负载均衡调度算法的研究.大电机技术,2015;3:60—61Liu Daopu,Tu Haining,Gu Jia.Research on load balancing scheduling algorithm for power information system.Large Electric Machine and Hydraulic Turbine,2015;3:60—61
[5] 张慧芳.基于动态反馈的加权最小连接数服务器负载均衡算法研究.上海:华东理工大学,2012Zhang Huifang.Research on server load balancing algorithm based on dynamic feedback weighted least-connections.Shanghai:East China University of Science and Technology,2012
[6] 罗拥军,李小乐,孙如祥.负载均衡算法综述.科技情报开发与经济,2008;18(23):134—135Luo Yongjun,Li Xiaole,Sun Ruxiang.Overview of load balancing algorithm.Sci-Tech Information Development&Economy,2008;18(23):134—135
[7] 孙峻文.基于退火算法的动态负载均衡研究.计算机科学,2013;40(5):89—90Sun Junwen.Dynamic load balancing based on annealing algorithm.Computer Science,2013;40(5):89—90
[8] Chang C J,Lin P C,Chen J M.Study on optimal queue-lengththreshold scheduling policy for an ATM mutiplexer with finite buffers and batch possion arrivals.Computer Networks and ISDN Systems,1994;2:524—540
[9] 王莉,周伟.基于ARM的嵌入式Web服务器设计.计算机工程与应用,2012;48(14):90—91Wang Li,Zhou Wei.Design of embedded Web server based on ARM.Computer Engineering and Application,2012;48(14):90—91
[10] 田绍亮,左明,吴绍伟.一种改进的基于动态反馈的负载均衡算法.计算机工程与设计,2007;28(3):572—573Tian Shaoliang,Zuo Ming,Wu Shaowei.An improved load balancing algorithm based on dynamic feedback.Computer Engineering and Design,2007;28(3):572—573
连接算法 篇7
由于数字视频信号在这些接口中采用纯数字格式的传输连接,当信号传输时很容易被计算机或者一些非法的器件复制下来。复制下来的数据是无损的,用户可以对这些数据进行任意次的无损复制、播放甚至编辑,严重损害了高清晰视频提供者/发行者的利益。因此,需要一个安全可靠的保护措施来保证这些高附加值的数字信号安全地通过从制作到传输再到播放的每一个接口。出于此目的,Inter组织制定了HDCP规范用于HDMI接口,为高带宽数字内容保护规范[1,2]。
2 HDCP系统的弱点
2.1 认证算法弱点
由于HDCP设计上不具备与第三方通信的功能,认证算法完全基于设备中存放的密钥对,通过验证发送端和接收端上的密钥对是否匹配来排队认证是否通过。HDCP密钥对是基于Blom's Scheme算法的,通过把矩阵D作为核心机密,利用随机种子向量和D做矩阵乘法,来生成HDCP密钥。
对于该认证算法方法,有很多破解方法,比如窃听认证数据;复制一个设备的密钥大量分发;利用现有的多个合法密钥计算出新的密钥;取消屏蔽列表的屏蔽功能,甚至篡改HDCP的密钥。
2.2 密钥管理模型
理论上HDCP的认证密钥是在足够安全的情况下生成并发放给设备生成厂商的,厂商将密钥写入设备的一次性存储器(OTP Memory),然后将产品出售。实际应用中,设备生产厂商和内容制作商,并不是利益共同体。设备生产厂商的利益在于售出更多的设备,而内容制作上的利益在于内容的安全性得到保护,没有非法传播。设备生产厂商可以将一个HDCP密钥多次利用,生产多个设备,严重违背了HDCP设计的本意。
3 新的连接保护系统设计
针对上述弱点以及实际应用,设计了新的连接保护系统,具有以下功能:支持认证中心(CA)对设备的管理,设备采用证书系统来实现公钥的安全交换,认证过程中使用基于RSA算法的双线性映射来实现证书的验证和加密密钥的相互交换。
3.1 RSA算法
RSA算法是基于公钥系统的加密算法[3],由Ron Rivest,Adi Shamir和Leonard Adleman发明,作为一个非对称算法,可以被用来加密和数字签名。RSA算法的安全性依赖于大整数的质因数分解,目前的加密系统中,需要至少1 024位的密钥长度来保证算法的安全性。
下面是RSA算法的基本流程:
1)选择2个数值相近的大质数p和q,计算n=p×q,φ(n)=(p-1)×(q-1);
2)选择1个整数e,满足1
3)计算d满足扩展欧几里德的模运算:e×d≡1mod(φ(n));
4)(e,n)作为公钥发布,而(d,n)作为私钥保存,p,q和φ(n)不再使用;
5)对于一个加密操作,明文消息为m,使用公钥(e,n)对明文进行加密,则密文消息为c=me(mod n),解密后的明文消息为m=cd(mod n)。
3.2 基于证书和挑战应答协议的认证
数字证书是由一个权威机构认证中心CA(Certification Authority)颁发。证书包含有:由CA提供给请求方的临时身份、请求方的公钥、证书的有效期限、CA用自己的私钥对前几项内容连接成的二进制串运算得到的数字签名等[4,5]。
在认证和密钥协商前,发送端A和接收端B都有各自的设备ID,记作IDA,IDB。另外设备还拥有认证中心颁发的公钥证书CertA和CertB,但没有对方的公钥证书。公钥证书通常在设备在生产的过程中预先存放好,证书包括用于认证的设备的公钥,以及用CA私钥做的签名。相应的,设备中存放CA的公钥以及设备的私钥。设备和CA的公私钥对都采用RSA算法生产,记作PKA,PKB,SKA,SKB,PKCA,PKCA。
发送端A和接收端B都有一个的散列算法(Hash)模块,H(S)代表由S生成的消息摘要。IDA||R0代表IDA和R0在序列上的连接,PKB(S)代表使用接收端B的公钥PKB加密S序列。对于合法的证书,应当满足f(IDA)=f(IDB),f为一个简单匹配函数,匹配函数的安全性取决于非对称密码技术的安全性,即破解该函数的难度等效于破解相应的非对称算法,在这个系统中,相当于破解RSA算法。
具体的认证过程分为两步,交换证书和挑战—应答协议,证书交换的流程如下:
1)发送端A将证书发送给接收端B;2)接收端B使用CA的公钥验证CertA的合法性,如果通过验证,可以得到A的公钥PKA,如果不能通过验证,则中止认证;3)接收端B将证书发送给发送端A;4)接收端B使用CA的公钥验证CertB的合法性,如果通过验证,可以得到B的公钥PKB,如果不能通过验证,则中止认证。
所有合法设备,都存放有CA的公钥用来验证证书的合法性。证书由组成证书主体部分和签名组成,可以记为Cert||Sign,其中Sign=SKCA(H(Cert))。进行验证时计算a=H(Cert),b=PKCA(Sign),如果a=b,则可以认为对方的证书确实是由CA签名的,并且证书内容保持完整。
挑战—应答协议用于验证对方设备是否真的拥有和证书对应的私钥。当该协议通过验证之后,可以确定对方设备的合法性:1)发送端计算K=f(IDA),接收端计算K′=f(IDB),有K=K′;2)发送端A生成一个随机数R0,计算a=H(K||R0),用PKB加密b=PKB(a||R0)并发送给接收端B;3)接收端B计算SKB(b),解密得到a和R0。计算c=H(K′||R0),验证c=a,若相等,则可认证发送端A的合法性,如果不相等,则中断认证;4)接收端B生成另一个随机数R1,计算d=H(K′||R0||R1),用PKA加密e=PKA(d||R1)。将e传发送端A;5)发送端A计算SKA(e),解密得到d和R1。计算f=H(K||R0||R1),验证f=d,如果相等,则可以认证接收端B的合法性。
基本的认证流程如图1所示。
3.3 加密密钥种子的生成与交换
对于一个加密解密系统,解密模块需要安全可靠地接收到加密模块发送的密钥用于数据的解密。这个过程称为密钥交换。在内容的加密运算中,需要经常对加密密钥或者种子进行改变,改变之后的密钥需要安全交换。本系统中,密钥交换不单独进行,而是依赖于定时的重复认证。系统为了确保连接的设备是合法的,而不是认证之后进行非法更换,会定时进行再次认证。
认证过程中2个设备间接的交换ID,发送端和接收端在收到对方ID之后进行数学计算得到2个数值,如果都是合法设备,这2个数值应当相等,经过交换确认之后即表示认证成功。本系统中,由于K=K′,而且没有公开传输,可以将K和K′作为密钥种子。
3.4 流加密模块设计
HDMI接口传输的是高速的非压缩音视频信号,必须采用受速度限制较小的流加密算法,每个像素对应1个加密密钥,密钥实时更新进行加密。
图2给出了流加密算法的工作原理。本系统中,发送端和接收端有2个相同的密钥序列生产器。在完成密钥种子的交换之后,流加密模块开始工作,两端生成完全相同并且与加密数据同步的加密密钥序列,密钥序列对明文序列(空白数据)进行一次异或运算生成密文序列(加密数据)。接收端再用相同的密钥序列进行一次异或运算,即完成了解密。
流加密模块的安全性取决于密钥序列的随机特性,周期越长,加密模块的功能是生成随机性尽可能好的密钥序列,该模块包括带有钟控的线性反馈移位寄存器、序列变换模块、自同步模块。图3给出了加密模块的结构。
本系统中,带有钟控的线性反馈移位寄存器(LF-SR_CC)的种子数为128,设计12个LFSR,位数分别为9,9,9,10,10,11,11,11,11,12,12,13(共128位),每个LFSR都选取对应阶次的本原多项式作为其特征多项式。根据定窗口法,可以生成与12个LFSR阶次对应的本原多项式。
图4给出了一个LFSR结构图的例子,对应的多项式为x9+x6+x5+x3+1。
系统自带3个128位的LFSR_CC模块,每个产生8 bit随机序列,每个LFSR_CC模块有12个LFSR,长度和抽头位置有所变化,保证3个LFSR_CC生成的8 bit随机序列互相线性无关。
钟控模块用于控制各个LFSR是否移位,增加序列的非线性特性,是A5系列流密码的核心。这种方法所生成密钥序列的线性复杂度与生成器输入参数间具有指数的关系,且这类序列易于由硬件实现。当加入钟控模块之后,由于系统非线性特性提高,密钥流周期将变得更大,随机统计特性更好。将12个LFSR分为4组,每组3个单独进行控制。钟控模块各个LFSR的抽头在最中间的一位,同时钟控函数应当保证这个时刻这组至少有一半以上的LFSR在进行移位。
每个LFSR模块生成8 bit的序列,但是这8 bit是相关的。序列模块采用矩阵映射算法将3个模块输出的24 bit序列打乱,每个时钟周期都对应不同的位数,这样可以得到相关性很低的24 bit密码序列。该模块由一个24 bit LFSR、24 bit寄存器和12个S-Box组成,进行变换。序列变换模块的24 bit LFSR带有密钥恢复(Rekey)功能,能够重置LFSR和寄存器。Rekey操作将在视频信号的每一帧传输完成之后进行,重新计算下一帧信号的密钥。这样新的密钥与当前寄存器中的数据以及上一帧数据无关,避免差错的累加传输。
自同步模块可以使密钥流不仅和密钥本身相关,还和已经产生的固定位数的密文字符有关。这样一种有记忆能力的序列密码,由于密钥流和密文有关,增加了密钥序列的随机性,同时无法从密钥序列分析出前端的结构。和普通的流加密模块相比,多了一个密钥生成器,将前端生成的初始密钥和已经产生的8个时钟周期的密文数据进行一个简单的运算,产生用于加密的密钥,该密钥与密文数据相关。图5显示了一个自同步模块的工作原理,截取前8个时钟生成的密文流和初始密钥一起,通过密钥生成器生成加密密钥。采用的密钥生成器的计算公式为:Key2=S(8)⊕S(6)⊕S(5)⊕S(3)⊕S(2)⊕S(1)⊕Key1。
4 系统安全性分析
4.1 系统结构安全性
系统结构的安全性,主要在于结构设计以及商业运营模型上有没有明显漏洞。本系统作为DRM系统的一部分,在商业运营模型上采用标准的模式。由于设备证书的发放和撤销由认证中心来完成,认证中心和内容发布者处于利益共同体,证书的发放不再会有HDCP中“掩耳盗铃”的现象。
4.2 认证协议安全性
本系统采用的挑战—应答协议可以抵抗多种攻击,包括常见的重放攻击,中间人攻击,暴力破解攻击也需要破解RSA算法。当然这个协议需要一个安全的方法来互相向对方传输设备的公钥,而本系统采用CA统一颁发证书并签名的方法,很好地解决了公钥安全传输的问题。
4.3 内容加密算法的安全性
本系统对于数据采用流加密算法进行加密运算,而流加密的安全特性主要取决与密钥序列的随机性,越是接近随机序列,安全性越好。下面对加密模块生成的密钥序列进行一些序列的基本检测:
1)密钥序列周期估算,加密模块分3部分。第1部分为带有钟控的线性反馈移位寄存器,LFSR部分可以生成的序列长度约为29+10+11+12+13=255,钟控可以增加序列随机性,将同一截数的LFSR周期分散,输出的序列周期约为2128。第2部分序列加扰,不改变序列的周期,只是削弱线性相关。第3部分是自同步模块,由于加密密钥与前8位的密文有关,而密文序列的周期可以是无限长的;
2)1 bit频数检测,统计200 000 bit随机序列中“0”和“1”的个数,结果为:N(0)=99 679,N(1)=100 321;
3)8 bit频数检测,将200 000 bit伪随机流每8位为1节,对应0~255间的一个十进制数。对256个十进制数出现的频数进行统计,得到图6所示的分布图。
4)游程检测,游程是序列的一个字串,由连续的“0”或“1”组成,并且其前导和后继元素都与其本身的元素不同。游程检验主要检验序列中游程总数是否符合随机性要求。20 000个密钥序列中长度为1,2,3,4,5的游程数目如表1所示。
5 小结
本文设计的系统针对HD-CP现有的不足做了一定的改进。由于该系统工作在HDMI接口上,部分算法受到实际硬件的限制,比如内容加密不得不采用高速但是相对安全性较低的流加密算法,如果移植到低速的信道上,则可以考虑安全性更高的分组加密算法。此外,关于相应的认证算法部分,条件成熟的话可以用椭圆曲线加密算法ECC等代替,ECC相对RSA有相同安全等级下,密钥位数更低,运算速度更快等优点。
摘要：目前,HDMI接口上唯一可用的连接保护算法HDCP在系统结构和认证协议部分有安全性的缺陷。针对现有的缺陷以及实际应用需求设计了新的连接保护系统,认证部分采用证书系统结合RSA算法,加密模块种子扩展到128位,大大提高了该接口的安全性。
关键词：HDMI,连接保护,RSA算法,数字版权管理
参考文献
[1]CROSBY S,GOLDBERG I,JOHNSON R,et al.A Cryptanalysis of the High-bandwidth Digital Content Protection System[EB/OL].[2009-05-20].http://apache.dataloss.nl/～fred/www.nunce.org/hdcp/hd-cp111901.htm.
[2]LEE W B,CHANG C C.Authenticity of public keys in asymmet-ric cryptosystems[EB/OL].[2009-05-20].http://www.ingentaconnect.com/content/els/01403664/1998/00000021/00000002/art00176.
[3]张建明,文学军.数字版权管理系统的原理与应用[J].现代图书情报技术,2004(2):20-24.
[4]王建明.流密码的设计与分析[D].北京:北京工业大学,2006.