一种基于混合策略的彩色编码算法

彩色编码是求解实际工程中难解问题的一种新兴而重要的技术.在应用该技术时,算法复杂度取决于彩色编码着色方案的规模,因此规模的大小将成为衡量彩色编码算法优劣的标准.彩色编码的研究在最近几年得到了许多有重要意义的结果.基于完全散列函数的PH算法产生的着色方案规模为O*(6.1kn),是目前世界上最好的确定彩色编码结果;彩色编码算法PBCC是一种利用组合思想针对n 2k的有效着色算法.文中以分治算法为基础,结合核心化技术,并利用PBCC算法求解子问题,提出了一种基于混合策略的彩色编码算法HABCC,并且证明了由HABCC算法产生的着色方案确实可以覆盖到所有子集,着色方案规模为|S(n,k)|2k.logkk-1.n.通过与PH算法的比较,说明了HABCC算法具有更小的着色方案规模,对彩色编码技术的实际应用具有重要的意义.     

基于加权分治技术的set packing精确算法

加权分治技术是算法分析中的一种新技术,该技术基于选择不同的量来描述分支子问题的大小,以求得到在最糟糕情况下最好的时间复杂度.set packing问题是一典型的NP-hard问题,广泛应用于调度、代码优化和生物信息学等领域.本文对有n个子集的set packing问题,引入符号全集变量N设计基于分支搜索策略的递归算法,并应用加权分治技术对算法加以分析,得到时间复杂度为O*(1.1686n+N) 的精确算法,当N≤n/4时,比现有最佳的算法O*(1.2209n)更加有效.     

无线传感器网络中节点的动态部署

作为无线传感器网络中节点部署的新兴技术,动态部署得到了越来越多的重视并在近年来取得了理论和应用上的一系列进展.首先介绍了动态部署的基本概念和设计难点,并根据移动主体的不同,将动态部署分为节点自主部署和机器人辅助部署两种方式.然后,依据静态和动态两种部署场景,分类论述了节点自主部署的代表性成果.接着从网络构建和网络维护两...     

无线网络中的多速率调整机制综述

目前IEEE802.11a/b/g等无线局域网的物理层均支持多速率的数据传输。无线信号在传输过程中受节点运动、时变干扰、信号衰落等因素的影响较大,因此发送节点采取何种策略预测信道状况和调整数据速率,对提高网络吞吐量有着重要影响。根据发送节点是利用历史信息预测速率还是用RTS/CTS反馈信息确定速率,可以将速率调整分为开环方式和闭环方式。综述了现有绝大部分速率调整机制的性能和特点,对起始速率设置、丢包区分和调整策略等关键问题进行了分析和对比,提出了目前存在的问题和今后主要的研究方向。     

加权3-Set Packing 的改进算法

Packing问题构成了一类重要的NP难问题.对于加权3-SetPacking问题,把问题转化成加权3-SetPacking Augmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合Color-Coding技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k).     

传感器网络中基于树的最大生命精确数据收集

在节点密集部署的多跳传感器网络中,精确数据收集使得越靠近Sink节点的传感器节点需要承担越多的数据转发量,能量消耗很快,容易造成“热区”,缩短了网络生命周期.为了最大化网络生命周期,需要构造生命周期最大的生成树,但这属于NP完全问题.无须知道节点的位置信息,提出一种算法MAXLAT来解决这个问题.算法以一棵Sink拥有最多孩子的生成树为基础,并根据节点负载的大小将树上节点分别定义为瓶颈节点、次瓶颈节点和富裕节点.然后,通过对所有节点进行着色,不断转移瓶颈节点的子孙,到富裕节点的子树上去.算法结束时,得到一     

基于多路欠采样的多分量LFM信号参数估计

针对多分量线性调频(Linear frequency modulated,LFM)信号,提出了一种基于多路欠采样的参数估计方法。采样过程由多个采样速率相同、采样时刻不同的模数转换器实现,总采样率可以低于信号的奈奎斯特采样率。基于欠采样序列乘积型模糊函数的单频特性,可以通过峰值检测实现调频斜率的估计。根据估计出的调频斜率对各路欠采样序列进行解线调处理,可得到多频正弦信号。结合矩保持问题的求解方法以及对超定方程组的求解,可以根据解线调后的各路序列估计出原始LFM信号各分量的初始频率。本文方法能够根据亚奈奎斯特采样样本实现LFM信号的参数估计,并且运算简单、易于实现。仿真实验验证了其有效性和准确性。     

数字校园统一安全接入平台的研究

文章根据数字校园应用服务多、用户群体活跃、安全管理松散等特点,提出了一个基于PKI/PMI技术的统一安全接入平台的设计方案。文中给出了系统总体设计模型图和系统的工作流程,并对此模型图中的主要功能模块进行了设计。     

结构化综合布线虚拟实验室的设计与研究

文章针对结构化综合布线实验教学需要,研究实现了结构化综合布线虚拟实验平台。根据海南师范大学的具体应用环境和虚拟实验室的要求,利用三维虚拟建模、网络虚拟交互、数据优化等关键技术,构建了一个基于Internet的交互式虚拟实验室系统。     

基于身份的密码学算法研究

为解决在有限资源下大量数字证书的管理问题,基于身份的密码学通过公钥密码仅由身份信息计算产生简化了公钥密码管理,该技术可以作为传统公开密钥基础设施的扩展安全机制以增加其便携性。