一种高效强K—栅栏覆盖构建算法

K－栅栏覆盖是无线传感器网络覆盖控制的研究热点之一。本文构建了强栅栏覆盖模型,提出了分区强K－栅栏覆盖构建算法PMNSB,用最少的节点形成强栅栏。首先把监控区域分成多个子区域,通过匈牙利算法选用移动距离之和最少的网格集合为基准1－栅栏覆盖,缺少移动节点的子区域,选择附近区域的剩余移动节点修补形成1－栅栏覆盖。水平相邻的两个子区域之间构建竖直栅栏,这些1－栅栏合起来构成强K－栅栏覆盖。仿真结果证明了该方法的有效性,本文的研究对提升无线传感器网络的性能具有重要的理论与实际意义。     

基于大规模MIMO网络的低复杂度块对角化算法

在多用户MIMO系统下行链路中,块对角化（Block diagonalization, BD）预编 码算法的和速率性能要优于匹配滤波算法（Matched filter, MF）和迫零算法（Zero forc i ng, ZF）。然而,传统的BD算法利用矩阵分解来构造除当前用户的其他所有用户信道的零空 间,需要O(N2)浮点运算次数（Float point operations, FLOPs）。当 基站的天线数N趋向于大规模时,BD算法计算复杂度巨大。本文 提出一种基于投影子方法构造其他用户合成信道的零空间的BD算法,该算法仅需O( N)FLOPs。仿真表明：同传统的BD算法相比,本文所提出的低复杂度BD算法显著地降低 了实现复杂度,而和速率性能损失微小,仍然优于MF和ZF,并且当N趋 向于大规模时,它的和速率性能趋向于传统的BD算法和SVD算法。     

一种可验证的多候选人电子投票方案

电子投票相对传统投票具有安全、便捷、低成本的优势,近年来得到了广泛的关注。2012年孙培勇等人提出了基于多方求和的多候选人电子投票方案。经分析发现该方案不满足可验证性,给出了一种具有可验证性的多候选人电子投票方案,保证计票结果的不可欺骗性。     

Alternative branching rules for some nonconvex problems

Following Linderoth (A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program. 103 (2005), pp. 251–282), in this paper we show how a preliminary theoretical analysis about the quality of convex and concave envelopes over different regions may suggest branching rules alternative to the traditional ones based on boxes. For two nonconvex problems (minimization of the sum of products of affine functions and maximization of the sum of ratios of affine functions, in both cases over polytopes), we show how the indications of the theoretical analysis lead to computational results which confirm the superiority of the alternative branching rules with respect to those based on boxes.     

连通域标记并行算法在多核处理器上的设计和实现

为满足全方位视觉运动目标检测跟踪系统中检测和跟踪实时性的要求,采用多核程序设计和并行处理技术,对系统中连通域标记算法,重新进行了设计和实现。为解决由图像分割造成的连通域的分离,应用边界处的游程码,将两个不同任务块中分割处的连通域合并成一个连通域。最后通过实验证明该并行算法比传统算法在多核处理器上运行更快,更好地解决了多核处理器饥饿问题,让多核处理器发挥了更高的效率。     

网络可靠性分析方法研究

总结了进行网络可靠性分析的一般步骤,比较了传统的网络分析方法的优缺点,重点论述了一种基于有序二叉决策图的方法,在考虑失效节点的网络可靠性分析中的应用。     

无线传感网络中能量均衡的连通支配集算法

连通支配集是无线传感器网络中构建虚拟骨干网络的重要手段.由于支配集中节点的能耗相对其他节点要多,支配集中剩余能量较小的节点决定了虚拟骨干网的生命周期.现有算法或者只是关注构造较小的支配集,或者没有考虑调整能耗极快的支配节点.提出了一种能量均衡的连通支配集算法,基于节点剩余能量和连通度构造支配集,在网络运行过程中根据耗能速度,提前选择候选支配节点,分流负载过重的支配节点.仿真结果表明,新算法能以较小消息开销,有效延长网络寿命.     

求解本原多项式的快速算法

文档图像处理技术是实现对网络上以"图片化"形式发送的垃圾邮件进行检测和过滤的有效手段.该文对彩色文档图像的版面进行分析,目的是分割出图像中的特定目标,便于分析并检测出文档图像中是否含有特别字符信息,从而使得网络垃圾邮件过滤系统可以根据这些信息判断是否过滤该邮件.实验结果表明,上述方法可以在不同颜色深度和不同几何结构的彩色文档图像中进行有效的检测,具有较好的实用性和应用价值.     

一种名片图像的文字区块分割方法

(Department of Computer Science and Technology, East China Normal University, Shanghai 200062)