摘要:软件缺陷预测技术从20世纪70年代发展至今,一直是软件工程领域最活跃的内容之一,在分析软件质量、平衡软件成本方面起着重要的作用.研究和讨论了软件缺陷预测技术的起源、发展和当前所面临的挑战,对主流的缺陷预测技术进行了分类讨论和比较,并对典型的软件缺陷的分布模型给出了案例研究.

摘要:对堆上数据的频繁访问是Java程序的主要开销,为此,研究者们通过虚拟机收集堆上数据访问的信息,而后采用预取或垃圾收集来改进内存性能.常用的收集方法有采样法和插桩法,但二者无法同时满足细粒度和低开销的要求.针对这两个要求,提出基于插桩分析的虚拟机自适应预取框架,该框架通过插桩收集信息,并根据程序运行时的反馈自适应地调整插桩并进行预取优化.实验结果表明,自适应预取优化在Pentium 4上对SPEC JVM98和Dacapo有不同程度的提高,最高的达到了18.1%,而开销控制在4.0%以内.

摘要:发布/订阅系统技术具有异步、松散耦合和多对多通信的特点,有着广阔的应用前景.但是,已有的发布/订阅系统技术不能满足动态环境下有延迟需求的应用要求.针对时间约束问题,扩展了发布/订阅系统的语法,建立了延迟模型,提出了一种基于收益机制的分布式发布/订阅系统时间约束保障技术和使系统获益最大化的调度算法MTEP(maximum total earning priority),其特点是能够满足订阅者和发布者指定延迟约束的需求,通过与订阅者商定的价格和违约成本信息来有效地利用网络带宽,适应网络环境的动态变化.实验结果表明,该调度策略和FCFS(first come first service)、最短时间优先和固定优先级等传统策略相比,可使订阅者接收到的有效事件明显增多,并使系统收益显著改善.

摘要:基本块重排是一类通过重新排布基本块在存储中的位置,以减少转移开销和指令cache失效率的编译优化技术.介绍了一种基于子结构分析的基本块重排算法.该算法通过统计剖视信息中控制流图的边执行频率,基于处理器转移预测策略构建转移开销模型和基本块排布收益模型.算法采用局部子结构优化的策略,改善基本块在存储中的排列顺序,从而减少转移开销,并提高指令cache的使用率,改善程序的总体性能.在UniCore处理器平台上进行了实验.实验结果表明,与其他基本块重排算法相比,该基本块重排算法在更大程度上减少转移开销和指令cache失效率的同时,其时间复杂度保持为O(n(logn).

摘要:热力学遗传算法(thermodynamical genetic algorithms,简称TDGA)借鉴固体退火过程中能量与熵的竞争模式来协调GA中"选择压力"和"种群多样性"之间的冲突.然而TDGA目前极高的计算代价限制了其应用.为了提高TDGA的计算效率,首先定义一种等级熵(rating-based entropy,简称RE)度量方法,它能以较小的计算成本度量种群中个体适应值的分散程度.然后引入分量热力学替换规则(component thermodynamical replacement,简称CTR),有效地降低了替换规则的复杂度.同时也证明了CTR规则具有驱动种群自由能近似最速下降的能力.在0-1背包问题上的实验结果表明,RE方法和CTR规则在保持TDGA良好的性能与稳定性的同时,极大地提高了其计算效率.

摘要:人体动作识别是计算机视觉中一个流行而且重要的研究课题.当观察视角发生变化时,动作识别变得格外困难.至今为止,关于动作识别和手势识别的大多数研究工作都是围绕着视角相关的表达展开的.有一小部分利用了视角不变的表示开展研究,可是它们大多数存在一些缺陷,比如缺少用于识别的足够信息,依赖鲁棒的语义特征点的检测或者是点对应.为了解决这个问题,实现视角无关、动作人无关的动作识别,提出了"包容形状"的表示,这种表示不依赖于特定视角.在人体动作识别中,人的身体旋转通常是引起视角变化的主要原因.包容形状充分利用了两个正交摄像机拍摄的轮廓信息以去除由人的身体旋转产生的影响.从来自两个正交的摄像机拍摄的外轮廓,可以很容易计算得到包容形状.利用包容形状的体态表示和隐马尔可夫模型,取得了非特定人、任意视角下动作识别的很好的实验结果.这些实验结果也表明了包容形状包含有足够区分度的信息.同时提出了包容形状的扩展表示,以便在两个摄像机并不完全正交的更为一般的摄像机配置条件下也可以应用,这极大地加强了其实用价值.

摘要:提出了一种针对三维医学图像已知诊断对象区域的形状自适应小波编码方法.该算法仅对对象区域内的像素应用形状自适应小波变换去相关,变换后,对象在变换域中的系数个数与图像域的像素保持相同.为了实现快速无损变换,提出一种基于提升的形状自适应小波变换方法.通过分析形状自适应变换后无效系数的位置,又提出一种改进的OB-3DSPECK(object-based set partitioned embedded block coder)算法,取消了对象区域外无效块或系数的符号输出,即只输出两种符号码流到自适应算术编码器.对于三维医学图像的对象区域,该算法能够提供有损到无损的渐进编解码.实验结果表明,该算法平均SNR比OB-3DSPECK提高0.5dB.此外,由于减少了一种符号输出,使得算术编码过程可选.

摘要:在agent结构中,主动目标是一个功能上自含且有自己独立控制流的实体.给出了主动目标相关的语法定义以及主动目标运行的操作语义,而且主动目标驱动下的BDI agent结构也被形式化地定义出来.区别于以往的一些BDI agent结构,目标不是隐含地表示而是作为实体显式地表示在agent结构中,使agent结构很自然地支持并行的目标,这被认为是agent理性行为的一个重要方面.此外,对目标的显式定义也为agent在动态的环境中对承诺的重新考虑带来了方便.

摘要:针对在线手绘图符识别中样本训练存在的"收集足够数量模板或样本并保持其区分度"的难点,提出了一种适合于手绘图符识别的基于检测器生成的克隆选择算法及其评价方法.该算法采用r-连续位不变规则和p-受体编辑生成初始检测器,使算法具有更广泛的搜索空间并不致陷入局部收敛.以手写文字作为实验对象,评价该算法各参数对个体训练的影响,实验结果验证了该算法对手绘图符样本训练及分类的改进.

摘要:局部线性嵌入是最有竞争力的非线性降维方法,有较强的表达能力和计算优势.但它们都采用全局一致的邻域大小,只适用于均匀分布的流形,无法处理现实中大量存在的非均匀分布流形.为此,提出一种邻域大小动态确定的新局部线性嵌入方法.它采用Hessian局部线性嵌入的概念框架,但用每个点的局部邻域估计此邻域内任意点之间的近似测地距离,然后根据近似测地距离与欧氏距离之间的关系动态确定该点的邻域大小,并以此邻域大小构造新的局部邻域.算法几何意义清晰,在观察数据稀疏和数据带噪音等情况下,都比现有算法有更强的鲁棒性.标准数据集上的实验结果验证了所提方法的有效性.

摘要:提出了一种恢复高质量稠密视差图的立体视觉合作算法.该算法采用基于形态学相似性的自适应加权方法,迭代地进行局部邻域的自适应聚合和抑制放大,实现高效率和高质量稠密视差图计算.将该算法推广到三目摄像机立体匹配系统中,通过重建摄像机坐标系实现图像校正,并根据连续性假设和唯一性假设,建立视差空间中的支持关系和三目摄像机之间的抑制关系.实验结果表明,三目立体合作算法能够得到精确的场景视差映射,并可以实现多基线方向的遮挡检测.该算法特别适用于由多个廉价摄像机组成的立体视觉系统,在几乎不增加软件和硬件资源的情况下,就可以得到高质量的稠密视差图.

摘要:K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.

摘要:EPON(Ethernet-based passive optical network)作为基于光纤的宽带网络接入技术,已经成为下一代接入网络的关键技术之一,但是IEEE 802.3ah EPON的Polling机制存在带宽使用率不高的问题,其DBA(dynamic bandwidth allocation)算法产生UWR(unused window remainder),USR(unused slot remainder),UQR(unused queue remainder)和UPR(unused package remainder),浪费了许多带宽资源.IPACT(interleaved polling with adaptive cycle time) EPON提出了一个带宽使用率较高的新的Poling机制,但没有解决DBA算法存在的缺点.在IPACT基础上,提出了一个基于效用的分布式EPON DBA实现机制,实现了对不同SLA(service level agreement)用户的相同业务类应用的差分处理.通过一种集中递归效用算法,有效地消除了再生UWR,通过一种分布式递归效用算法,有效地消除了UQR,通过一个分布式UPR消除机制,减少了UPR.提出了一个基于交织接力棒的USR消除机制,提高了消除USR条件满足的概率,通过将交棒者的USR追加到接棒者的授权中,提高了带宽的使用效率.仿真结果很好地验证了该机制的优点.

摘要:在总结现有实体随机移动模型优、缺点的基础上,提出一种能够较好地反映现实节点运动规律的参数独立可控性比较强的平滑高斯-半马尔可夫实体随机移动模型(smooth Gauss-semi-Markov mobility model,简称SGM),并利用马尔可夫过程及更新过程理论证明了该模型具有平均速率时间平稳和点空间分布均匀的特性,适用于移动无线传感器网络的模拟仿真研究.

摘要:作为对基于密码体系的安全手段的重要补充,信任管理在解决WSNs(wireless sensor networks)中的内部攻击,识别恶意节点、自私节点及低竞争力节点,提高系统安全性、可靠性和公平性等方面有着显著优势.综述了WSNs环境下信任管理的特点、分类方法、框架设计、脆弱性分析、攻击模型及对策,在此基础上介绍了WSNs下的典型信任管理系统.以信任计算模型为中心的WSNs环境下信任管理框架的设计是信任管理系统的核心,从信任要素、信任计算模型和信任值的应用这3个方面对其进行了深入讨论.最后,总结了WSNs环境下信任管理的研究现状,提出了值得参考的研究发展方向.

摘要:针对无线移动通信的特点,提出了一种在移动IPv6网络中保障用户通信服务质量的资源预留新方案Fast RSVP.该方案采用跨层设计的思想,将两个不同层次的模块:移动IPv6模块和RSVP模块结合起来,通过在两个模块之间增加一些原语使得二者配合工作以保证移动用户的通信业务质量.Fast RSVP方案引入了邻居隧道提前资源预留、优化路径资源预留、切换预留、路径融合等一系列新机制.仿真实验结果表明,与其他移动环境中的RSVP扩展方案相比,该Fast RSVP方案在支持无线移动通信方面具有如下优势:(1) 能够实现移动节点带有服务质量保证的快速切换;(2) 能够避免移动IP切换过程中三角路由和重复预留造成的资源浪费;(3) 能够区分不同类型的切换预留请求,在保证网络整体性能的前提下显著降低因为切换而导致的服务中断率.

摘要:下一代互联网NGI(next generation Internet)需要提供服务质量QoS(quality of service)路由能力.由于NGI网络状态难以精确测量与表达,因此,QoS路由基于的信息应该是模糊的.随着网络运营的渐趋商业化,付费上网要求实现QoS计费,而网络提供方与用户的利益冲突要求实现效用双赢.设计了一种基于模糊积分和博弈论的QoS组播路由机制.该机制由边评判、博弈分析和组播路由树建立算法组成,基于模糊积分和适合隶属度函数对边进行模糊综合评判,通过博弈分析确定网络提供方与用户在边上的效用能否达到Nash均衡,通过组播路由树建立算法使得在建立的组播路由树上不仅用户QoS要求得到满足,而且网络提供方效用与用户效用达到或接近Nash均衡下的Pareto最优.仿真结果表明,与QoSMIC等机制相比,该机制具有较好的性能.

摘要:2005年,王晓明等人把多重指定验证人签名与门限代理签名结合起来,提出了一个门限代理多重指定验证人签名(Wang-Fu).同年,陈伟东等人也提出了一个指定验证人的数字签名方案(Chen-Feng-Tan).证明Wang-Fu方案中指定验证人集合的管理者可以直接伪造签名.为此,每个验证人对在验证阶段使用私钥产生的部分数据必须进行零知识证明.CFT方案不满足非传递性,即指定验证人可以向第三方证明其拥有的签名是由签名人签署的.其原因在于,该方案直接利用了Schnorr签名技巧,指定验证人很容易把拥有的签名转化为关于原始签名人公钥参数的一个普通签名.

摘要:从计算难解性的角度重新考察Paillier的陷门单向函数,并提出多一次Paillier求逆问题这一关于Paillier求逆问题的推广问题.从计算难解性的角度考察了多一次Paillier求逆问题与Bellare等人提出的多一次RSA求逆问题之间的关系,并证明了在计算难解性的意义上,多一次Paillier求逆问题等价于多一次RSA求逆问题.以此为基础,进而提出一种新的鉴别方案,并证明在多一次Paillier求逆问题的难解性假设下这一鉴别方案具备并发安全性.

摘要:提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r+n^0.5),这里,n为模型的点数,r为凹边数.实验结果表明,与目前国际上常用的"切割分裂"方法相比,新方法的速度提高了14～120倍,空间下降至"切割分裂"方法的1/2.3～1/7.4,而新增加的点数则最多为"切割分裂"方法的1/28,甚至有些情况下无须增加新点就能完成凸剖分.新方法剖分出的凸多面体绝大多数是四面体,多于"切割分裂"方法所得凸多面体数量.但是,很多应用是要求多面体被剖分为四面体的.如果进一步将凸多面体四面体化,则新方法的结果个数将明显少于"切割分裂"方法,因为新方法的剖分过程中所增加的新点要少很多.新方法还能方便地处理包含空洞的多面体,甚至是包含孤立面、孤立边和孤立点的非流形多面体.

摘要:提出了一种空间动态可变材质的交互式全局光照明绘制算法.如果在绘制过程中允许用户对物体的材质作修改,并且对一个物体的不同部分的材质作不同的修改,则称为空间动态可变材质.由于最终出射的辐射亮度和材质呈非线性关系,因此现有许多交互式全局光照明算法不允许用户修改物体的材质.如果一个物体各部分的材质可以不相同,那么材质对最终的出射的辐射亮度的影响更为复杂,目前没有任何交互式全局光照明绘制算法能够在绘制过程中对一个物体不同部分的材质作不同的修改.将一个空间动态可变材质区域划分成许多子区域来近似模拟,每个子区域内部材质处处相同.光在场景传播过程中可能先后被不同的子区域反射,并以此将最终出射的辐射亮度分为许多部分.用一组基材质来线性表示所有的材质,这组基材质被赋予场景中的所有子区域,从而得到不同的基材质的分布.预计算所有这些基材质分布下的各部分最终出射的辐射亮度.绘制时根据各子区域材质在基材质上的系数组合相应的预计算数据,就能交互式绘制全局光照明效果.

摘要:由二维工程图重建三维形体是一种快速的形体造型方法,已成为计算机图形学和人工智能领域的重要研究方向.立足于基于工程图的三维重建问题,分类总结了形体重建方法的研究成果,着重介绍了典型的重建算法.在比较了典型算法的适用范围的基础上,剖析了目前形体重建研究所面临的问题.最后,指出了基于工程图的三维重建算法进一步的研究方向.

摘要:首先推导与归纳了图像三维变换中像素深度场的变换规律,同时提出了基于深度场和极线原则的像素可见性别方法,根据上述理论和方法,提出一种基于深度图像的建模与绘制(image-based modeling and rendering,简称IBMR)技术,称为虚平面映射.该技术可以基于图像空间内任意视点对场景进行绘制.绘制时,先在场景中根据视线建立若干虚拟平面,将源深度图像中的像素转换到虚平面上,然后通过对虚平面上像素的中间变换,将虚平面转换成平面纹理,再利用虚平面的相互拼接,将视点的成像以平面纹理映射的方式完成.新方法还能在深度图像内侧,基于当前视点快速获得该视点的全景图,从而实现视点的实时漫游.新方法视点运动空间大、存储需求小,且可以发挥图形硬件的纹理映射功能,并能表现物体表面的三维凹凸细节和成像视差效果,克服了此前类似算法的局限和不足.

摘要:提出了一种简单、快速、高效的基于草绘设计的概念模型创建方法.该方法模仿传统的纸笔草绘设计方式,允许用户自由地在笔式用户界面上勾画特征笔划,然后根据笔划的形状和位置关系采用基于特征的实体建模方法构造不同的扫描特征体素.在此基础上,采用了基于意图捕捉的特征添加及切削机制创建复杂的实体模型,给出了一些关键算法的实现过程.实验结果表明,该方法能够较好地应用到联机三维概念模型快速创建过程中.

摘要:在论述负载均衡技术相关工作的基础上,基于IP报文头多域分类方法,提出自适应负载均衡算法MSF(minimum sessions first),通过动态调整TCP流数目最少的流束,能够在各处理节点间保持动态负载均衡的同时维持会话的完整性.模拟结果表明,MSF算法具有设计简洁、负载均匀度好、重映射破坏度小、会话完整性破坏度小等优点,对不同负载具有良好的综合性能.该算法已经成功地应用在国防科学技术大学计算机学院研制的高速网络安全设备中,在保持较好的负载均衡效果的前提下保证了会话的完整性,提高了网络安全设备的性能.

摘要:针对当前弱硬实时调度算法无法保证超过窗口长度的执行序列的满足率达到一定比例的问题,基于(m,p)弱硬实时约束,提出了一种基于裁剪的调度算法(cut-down based scheduling,简称CDBS).由于判断(m,p)约束是否满足需要遍历任务的整个执行序列,因此判断复杂度很大.为此,提出一种高效的裁剪执行序列的算法,同时证明其正确性,并利用适当的数据结构,使得计算复杂度与序列长度无关,通过实验说明其降低计算复杂度的有效性.进一步与其他经典实时调度算法(EDF(earliest deadline first),DBP(distance-based priority),DWCS(dynamic window constraint schedule))进行比较,验证该算法与其他算法具有相当的性能.

摘要:调度算法设计对于网络路由设备实现区分服务(DiffServ)模型的单跳行为(per hop behavior,简称PHB)至关重要.现有支持DiffServ模型的调度算法普遍基于输出排队(output queued,简称OQ)或是输入排队(input queued,简称IQ)交换结构进行设计,均无法在高速环境下提供高性能的调度.基于联合输入/交叉节点排队(combined input-crosspoint-queued,简称CICQ)交换结构提出一种支持DiffServ模型的全分布式调度算法DDSS (distributed DiffServ supporting scheduling),并通过理论分析对其公平性进行了验证.DDSS算法采用基于预约带宽的逐级流量控制机制实现所有预约带宽在快速转发(expedited forwarding,简称EF)业务与确保转发(assured forwarding,简称AF)业务之间的分配,采用优先级调度机制为EF业务提供低延迟服务,算法复杂度为O(log N).仿真结果表明,DDSS算法具有良好的时延性能和公平特性,与现有算法相比,能够更好地支持DiffServ模型.

摘要:调度策略是核心路由交换设备性能的重要保证.针对联合输入交叉节点排队(combined input and cross-point queuing,简称CICQ)交换结构现有调度策略在复杂度或性能方面存在的缺陷,深入探讨了CICQ交换结构调度策略设计的基本准则,并提出了CICQ下虚拟通道的概念.基于基本准则和虚拟通道概念,提出一种简单、高效和公平服务的动态轮询调度策略——FDR(fair service and dynamic round robin).其算法复杂度为O(1),具有良好的可扩展性;并依据虚拟通道的状态为其分配调度份额,具有良好的动态实时性能,能够适应流量负载非均衡的网络环境.SPES(switching performance evaluation system)仿真结果表明,该算法具有良好的时延、吞吐量和抗突发性能.