一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题，设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息，可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网，从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明，文中提出的算法求得的连通支配集小，能较好地应用于一般网络以及移动自组网络中。  

一种延时约束费用最小分布式动态组播路由算法

多媒体应用一般包含多个组播成员,它消耗大量的网络资源且有严格的端端延时约束.针对这个问题,提出了一种延时约束费用最小的分布式动态组播路由启发算法DDDDCLCMR(distributeddynamicdelay-constrainedleast-costmulticastroutingalgorithm).在DDDDCLCMR算法中,组播源点很少或根本不参与路由计算;即使组播成员发生改变,组播树变化也很小,算法扩展性好.实验结果表明，无论组播成员改变与否,DDDCLCMR算法都能获得满足延时约束且费用很低的组播树.  

FIR滤波器的FPGA实现及其仿真研究

本文提出了一种采用现场可编程门阵列器件FPGA实现FIR字滤波器硬件电路的方案,该方案基于只读存储器ROM查找表的分布式算法。并以一个十六阶低通FIR数字滤波电路在ALTERA公司的CYCLONE系列FPGA芯片上的实现为例说明了设计过程。所设计电路通过软件验证和硬件仿真,结果表明电路工作正确可靠,满足设计要求,性能优于用DSP和传统方法实现的FIR滤波器。  

分布式序列模式发现算法的研究

提出算法FDMSP(fast distributed mining of sequential patterns),以解决分布式环境下的序列模式挖掘问题.首先对分布式环境下序列模式的性质进行了分析.算法采用前缀投影技术划分模式搜索空间,利用序列模式前缀指定选举站点统计序列的全局支持计数,利用局部约减、选举约减、计数约减等方法减少候选序列数,同时将算法分为3个子过程异步运行,使得算法具有较低的I/O开销、内存开销和通信开销,从而高效地生成全局序列模式.实验结果显示,在具有海量数据的局域网环境中,FDMSP算法的性能优于将数据集中后采用GSP算法68.5%～99.5%,并且FDMSP算法具有良好的可伸缩性.  

分布式系统的时间同步算法研究及应用

实现分布式系统时间同步的方法有两种：一是将外部时间基准引入分布式系统的绝对时间同步，二是仅在分布式系统内部使用算法实现同步的相对时间同步。本文详细讨论了适用于局域网的各种时间同步算法，并对部分算法的应用结果进行了分析。  

基于FPGA流水线分布式算法的FIR滤波器的实现

提出了一种采用现场可编程门阵列器件(FPGA)并利用窗函数法实现线性FIR数字滤波器的设计方案,并以一个十六阶低通FIR数字滤波器电路的实现为例说明了利用Xilinx公司的Virtex-E系列芯片的设计过程。对于在FPGA中实现FIR滤波器的关键———乘加运算,给出了将乘加运算转化为查找表的分布式算法。设计的电路通过软件进行了验证并进行了硬件仿真,结果表明:电路工作正确可靠,能满足设计要求。  

分布式存储的并行串匹配算法的设计与分析

并行串匹配算法的研究大都集中在PRAM(parallel random access machine)模型上,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多.该文采用将最优串行算法并行化的技术,利用模式串的周期性质,巧妙地将改进的KMP(Knuth-Morris-Pratt)算法并行化,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法,其计算复杂度为O(n/p+m),通信复杂度为O(ulogp相似文献

基于FPGA的实时图像滤波及边缘检测方法

图像滤波和边缘检测是视觉导航系统中道路检测和障碍物检测等复杂视觉处理的关键步骤,其性能和处理时间直接影响了后续图像处理的性能及视觉系统的整体响应时间.为此,提出了一种基于FPGA的实时图像模板滤波及边缘检测方法,将LoG模板分解为两个一维模板的卷积和,从而降低了算法运算量.并充分利用FPGA的并行机制及片内丰富的RAM资源,采用分布式算法,用查找表代替乘法器进行乘法运算.实验表明该方法满足视觉导航系统中实时性需求,且又适用于其他基于模板运算的图像处理算法.  

有向传感器网络最大覆盖调度算法

与传统的全向传感器不同,有向传感器可以切换到不同的方向,并且每个方向覆盖有限角度的感应范围.针对有向传感器网络的区域覆盖问题,研究了“最大有向区域覆盖”MDAC(maximum directional area coverage)问题,期望通过调度传感器的工作方向,最大化覆盖区域面积.首先给出了MDAC 的问题定义,使用整数线性规划描述MDAC 问题,并且证明其是NP 完全的.然后提出一种分布式贪心算法DGreedy(distributed greedy algorithm)解决MDAC 问题.在此基础上,通过计算可能的覆盖贡献比例来反映网络拓扑信息.还提出了一种增强的算法PGreedy(distributed probability-enhanced greedy algorithm)使覆盖区域更大.证明了所提算法的收敛性,并通过详细的模拟实验验证了其有效性.  

一种蓝牙分散网拓扑结构创建和网络路由分布式算法

蓝牙分散网潜在的广阔应用前景使它逐渐成为自组网络研究热点之一。蓝牙分散网所具有的特殊限制和特性给有效创建分散网络拓扑结构和网络路由带来了挑战。提出和分析了一种分布式蓝牙分散网拓扑结构创建算法和以此为基础的网络路由算法。它是一种简单有效的可递归算法，具有良好的扩展性。文章假定通信距离内的两结点间能建立物理连接。通过数学证明和仿真试验，算法具有以下性能：时间复杂度为O（log N)，消息复杂度为O（N），分散网网络直径为O（log N)。利用特殊的地址表示法，运行简单的路由算法可实现单播和广播路由。