基于多生成树和子网-节点度联合权重的MCDS构造算法

提出了一种基于多生成树和子网-节点度联合权重的静态无线网络极小连通支配集MCDS构造算法SWNMCDS。算法首先设定一个概率p,每个节点随机生成一个概率并与p对比后决定是否成为候选根节点。两跳范围内的候选根节点相互交换信息,确定最终的根节点。每个根节点基于节点权重的连通树生成算法生成多棵连通树。最后基于子网-节点度联合权重选择连通节点,将多棵连通树连成极小连通支配集。经分析,SWNMCDS算法近似比上限为2β(2+H(Δ)),时间复杂度为O(Δ2),消息复杂度为O(Δ2)(Δ为最大一跳邻居节点集合的大小,β为生成树数目)。仿真实验表明,与经典MCDS算法比较,SWNMCDS所构造的连通支配集具有较小的规模。     

基于连通支配集的虚拟骨干网构造算法

针对无线传感器网络中缺少骨干网络的问题,提出一种基于连通支配集的虚拟骨干网构造算法。该算法利用图论中的极大独立集和连通支配集构造一个虚拟骨干网络,运用修剪规则去除冗余节点,通过优先选择能量多、距离近的节点使网络寿命更长、延迟更小。实验结果表明,该算法在单位圆图中产生的连通支配集至多为7.6opt+1.4,消息复杂度和时间复杂度为O(n)。     

分布式最小连通支配集启发式算法

针对AdHoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7．60pt＋1．4,时间复杂度为O（△^2）,消息复杂度为O（n）,比同类算法优秀。     

无线网络中一种简单的弱连通支配集构造策略

通过构造边支配集,提出了求解无线网络中弱连通支配集的集中式构造算法,该算法的时间复杂度为O（|N|+|E|）。同时在保证支配集的支配性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性,并通过仿真验证了算法的有效性。与已有结果相比,该算法可以产生规模更小的弱连通支配集。     

连通支配集一种集中式近似算法

简单无向图的最小连通支配集问题是NP完全问题,目前还没有成熟解法。提出了一种用有序袁构建独立集求解连通支配集的算法,算法从图中度最大的顶点开始将顶点加入到有序表中,并在加入过程中构建独立集,同时加入其他节点连接独立集使其成为连通集当图中所有节点处理完成,有序表中标记为独立集的节点和连接节点就形成了一个连通支配集。实验表明算法生成的支配集较小,运行时间复杂度比较低。     

连通支配集一种集中式近似算法

简单无向图的最小连通支配集问题是NP完全问题,目前还没有成熟解法。提出了一种用有序表构建独立集求解连通支配集的算法,算法从图中度最大的顶点开始将顶点加入到有序表中,并在加入过程中构建独立集,同时加入其他节点连接独立集使其成为连通集。当图中所有节点处理完成,有序表中标记为独立集的节点和连接节点就形成了一个连通支配集。实验表明算法生成的支配集较小,运行时间复杂度比较低。     

一种新的自组网极小连通支配集生成算法

自组网通过节点的自组织,构造成一种不需要任何基础设施的新型无线网络,基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足,基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS(Coloring Based-Minimum Connected Dominating Set)。CB-MCDS算法仅需要一跳邻居节点的拓扑信息,就能快速地构造出虚拟主干网,理论分析表明整个算法的时间和消息复杂度分别为O(△)和O(n△),该性能明显优于已有的算法。     

一种新的自组网极小连通支配集生成算法

自组网通过节点的自组织，构造成一种不需要任何基础设施的新型无线网络，基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足，基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS（Coloring Based—Minimum Connected Dominating Set）。CB-MCDS算法仅需要一跳邻居节点的拓扑信息，就能快速地构造出虚拟主干网，理论分析表明整个算法的时间和消息复杂度分别为O（A）和O（n△），该性能明显优于已有的算法.     

一种基于反向CDS树的异构WSNs拓扑构建方法

在无线传感器网络中,拓扑控制是节约能源、延长生命周期的一项关键技术。现有拓扑控制方法的研究主要集中在同构网络,对此,面向异构网络提出了一种低信息复杂度的基于反向连通支配集树的分布式拓扑构建算法。基于最小连通支配集构建虚拟骨干树,改进了A3G算法中节点的适应度函数和算法流程,优化了产生的连通支配集的规模和通信开销,进一步降低信息复杂度,在保证连通性的同时关闭网络冗余节点以降低能耗。理论分析和仿真实验证明,算法能够以较小的时间和通信代价构建拓扑,延长网络生命周期。     

一种新型的Ad Hoc网络虚拟主干网构造技术

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。本文对现存基于连通支配集算法的提出背景和应用环境作了简单介绍,由于在无线自组网中搜索主干节点和群首类似于图论中的最小连通支配集和最小支配集问题的求解,在此基础上提出了一种性能较好的虚拟主干网的构造技术--基于图着色思想提出的一种极小连通支配集的构造算法,并从理论上证明了该算法的正确性和高效性,通过分析,算法的时间和消息复杂度明显优于其他已知算法。     

线性复杂度为2n-2m-1的2n-周期二元序列的k-错线性复杂度*

线性复杂度和k-错线性复杂度是研究流密码稳定性的两个重要概念。当改变序列某几位时不会使得序列的线性复杂度急剧减少,说明该序列的稳定性良好。运用Chan-Games给出了当k=4或5时,F2上固定线性复杂度为2n-2m-1的2n-周期二元序列的k-错线性复杂度所有可能值,LCk(s)=0或LCk(s)=2n-2m-2r+1+c,LCk(s)=2n-2r+1+c。这一结果对流密码稳定性的研究有重要的应用价值。     

Quantum image matching

Quantum image processing (QIP) means the quantum-based methods to speed up image processing algorithms. Many quantum image processing schemes claim that their efficiency is theoretically higher than their corresponding classical schemes. However, most of them do not consider the problem of measurement. As we all know, measurement will lead to collapse. That is to say, executing the algorithm once, users can only measure the final state one time. Therefore, if users want to regain the results (the processed images), they must execute the algorithms many times and then measure the final state many times to get all the pixels’ values. If the measurement process is taken into account, whether or not the algorithms are really efficient needs to be reconsidered. In this paper, we try to solve the problem of measurement and give a quantum image matching algorithm. Unlike most of the QIP algorithms, our scheme interests only one pixel (the target pixel) instead of the whole image. It modifies the probability of pixels based on Grover’s algorithm to make the target pixel to be measured with higher probability, and the measurement step is executed only once. An example is given to explain the algorithm more vividly. Complexity analysis indicates that the quantum scheme’s complexity is \(O(2^{n})\) in contradistinction to the classical scheme’s complexity \(O(2^{2n+2m})\), where m and n are integers related to the size of images.     

第一寄存器小Qubit量子计算攻击RSA研究

提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于 Shor 算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。     

一种基于正交视图的三维模型多特征匹配算法

针对现今多数三维检索算法在匹配精度、检索速度以及算法复杂度三者难以相互兼顾的问题,文中提出一种基于正交视图的三维模型多特征匹配算法。首先对被检索三维模型的6个正视角进行投影,获得6个正视图像;接着分别用灰度级图像来描述各个正视图特征,并根据投影后模型各面的分布情况填补顶点与面片之间的间隙;然后动态提取每个灰度级图像的投影直方图特征和Zernike矩特征;最后在分析各特征的优缺点的基础上,融合多个特征来匹配三维模型的相似度。与传统LFD算法和D2算法进行对比实验,结果表明,文中算法能较好地提高对三维模型检索的查全率与查准率,具有计算量小、匹配精度高、运行速度快的优点。     

基于幂律分布的网络用户快速排序算法

随着网络论坛、博客、微博的发展,引出社会网络中的用户排序问题。将在线网络论坛中用户映射为节点,用户评论过程中形成的回复关系映射为有向关联图,其节点度符合幂律分布。且论坛中用户的主题发布行为和回复关系符合Pagerank算法的互增强和随机游走特性,因此选用Pagerank算法排序用户影响力。该文提出的研究问题 如何提高用户排序应用中数据的存储和运行效率。天涯网络论坛中80%以上用户入度为0,据此,根据入度是否为0划分为两个集合,对入度为0集合按出度构造链接表,设计了基于集合划分的高效排序算法SD-Rank。SD-Rank时空复杂性为O(V′),V′为入度非0节点集。对天涯网络论坛真实用户数据的实验结果表明 SD-Rank算法时空复杂性优于Pagerank算法。     

一种新的删除AA-树结点的算法

Andersson的删除AA-树结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AA-树结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Andersson的算法相比,新算法不涉及辅助栈的使用。设n是AA-树的内部结点的个数,执行新算法时进行O（lbn）次旋转,新算法的时间复杂性是O（lbn）,与Andersson的算法的时间复杂性相同。实验结果表明新算法的平均执行时间比Andersson的算法的平均执行时间短。新算法的空间复杂性是O（1）,比Andersson的算法的空间复杂性低。     

基于DFP校正拟牛顿法的傅里叶神经网络

针对傅里叶神经网络采用最速下降法导致局部极小、学习速度慢以及泛化能力差的问题,提出一种基于DFP校正拟牛顿法的新学习算法。该算法计算复杂度低,能保证网络具有良好的泛化能力和全局最优性。通过2个数值算例检验该算法,同时和BP神经网络以及另外2种傅里叶神经网络作比较。结果表明,该算法计算复杂度约为最速下降法的5%,为最小二乘学习算法的80%,具有较好的泛化 能力。     

双中心粒子群优化算法

粒子群优化(PSO)算法是一种新兴的群体智能优化技术,由于其原理简单、参数少、效果好等优点已经广泛应用于求解各类复杂优化问题.而影响该算法收敛速度和精度的2个主要因素是粒子个体极值与全局极值的更新方式.通过分析粒子的飞行轨迹和引入广义中心粒子和狭义中心粒子,提出双中心粒子群优化(double center particle swarm optimization,DCPSO)算法,在不增加算法复杂度条件下对粒子的个体极值和全局极值更新方式进行更新,从而改善了算法的收敛速度和精度.采用Rosenbrock和Rastrigrin等6个经典测试函数,按照固定迭达次数和固定时间长度运行2种方式进行测试,验证了新算法的可行性和有效性.     

线性复杂度为2n-2m的2n-周期序列的k-错线性复杂度*

线性复杂度和k-错线性复杂度是衡量密钥序列随机性的两个重要标准,运用Chan-Games算法,得到线性复杂度为2n-2m的2n-周期二元序列的k-错线性复杂度的所有可能的值,LCk(s)=0或2n－2m－2r+1+c,2n-2r+1+c。这一结果对于进一步探讨流密码密钥序列的安全性有重要的应用价值。     

超图划分问题的元胞自动机模型及算法研究

对超图划分问题运用元胞自动机理论进行分析建模,提出一种元胞自动机模型以及基于该模型的赋权超图划分优化算法。在该模型中,元胞对应于赋权超图中的结点,邻接元胞对应于邻接超边所包含的结点,元胞的状态对应于所在的划分子集。引入二维辅助数组存储每条超边在划分子集中的结点个数,给出快速的元胞收益值和划分割切值的计算方法,从而避免遍历超边中的结点。实验结果表明,与赋权图划分算法和迁移方法相比,该算法可以取得更优的划分,且时间复杂度和空间复杂度较低。