摘要:在回顾了现有的开放式频谱系统中的动态频谱分配算法后,基于快速收敛和公平性两方面的性能因素并兼顾系统总带宽性能,提出了两种易于实现且具有良好收敛性能的启发式频谱动态分配算法——兼顾最大化系统总带宽的快速收敛算法(fast convergency algorithm with maximum bandwidth,简称FCMB)和兼顾最大化系统总带宽的启发式公平性分配算法(heuristic fairness algorithm with maximum bandwidth,简称HFWB).通过大量的仿真实验,就系统总带宽、公平性以及收敛性能3个方面,与现有的协调式最大化系统总带宽(collaboration max-sum-bandwidth,简称CMSB)算法、随机分布式算法(randomized distributed algorithm,简称RAND)以及以最大化系统总带宽为目标的理论最优(theoretical max-bandwidth optimal,简称OPTL)算法进行了比较,并针对主、次用户数目变化、系统中信道数目以及次用户干扰区域半径大小变化等不同系统参数情况下各种算法的性能进行了对比分析.仿真结果表明,在综合考虑系统总带宽的基础上,FCMB算法和HFWB算法在快速收敛和兼顾系统带宽的公平性能上分别表现突出,尤其是FCMB算法,其在收敛速度上远远优于其他算法(和与其在系统吞吐性能上表现相近的CMSB算法相比,在收敛性能上至少有300%的提高).

摘要:介绍了一种基于复制结点的消除线路交叉的模型.该模型提出了一个优化问题,就是最小化结点复制的数量.同时提出一个自定义问题——"最大简单共享问题",并证明最小化结点复制的数量与最大共享问题是等价的.证明了最大简单共享问题是NP-hard的,给出了一种简单的贪心算法,并证明该贪心算法的近似度为3.引入一个"最大互斥简单共享问题",该问题是最大简单共享问题的2-近似.将其转化为在一系列图上的完美匹配问题,使该问题可以在多项式时间内得到完美解决.最后,在最大互斥简单共享的基础上,用局部搜索的方法将近似度提高到12/7.

摘要:证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figueroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2^p)减小为O(m·(n-p+1)·2^p),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2^p)减小为O(m·2^p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.

摘要:合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF_≥k是子句长度大于或等于k的CNF公式子类,判定问题LSA(≥k)的NP-完全性与LCNF(≥k)中是否含有不可满足公式密切相关.即LSAT_≥k的NP-完全性取决于LCNF_≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF_≥3和LCNF_≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF_≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.

摘要:逃逸分析(escape analysis)是一种可以有效减少Java程序中同步负载和内存堆分配压力的跨函数全局数据流分析算法.此前绝大多数逃逸分析的实现都基于一个所谓"封闭世界(closed world)"的前提:所有可能被执行的方法在做逃逸分析前都已经得知,并且,程序的实际运行不会改变它们之间的调用关系.但当真实的Java程序运行时,这样的假设并不成立.Java程序拥有的许多特性,例如动态类加载、调用本地函数以及反射程序调用等等,都将打破所谓"封闭世界"的约定.这样的真实运行环境被称为"开放世界".在开放世界中,实现逃逸分析将面临许多重要的问题,例如,能否正确、全面地捕捉动态载入的类和方法,并分析它们与原有程序的关系;逃逸分析算法的复杂性是否能够得以控制,以保证即时编译器的重新分析时间不会过长,等等.提出一个新的逃逸分析架构,它可以有效地处理上述开放世界所面临的问题.该分析架构将增量分析Java程序,动态捕获新载入和调用的类及方法,同时,在复杂性和精度之间进行权衡,正确、有效地降低程序的运行负载.该分析架构已经在Intel的开放式Java虚拟机系统ORP中实现,经过实际测试,可以有效地消除一些主要基准测试程序,如SPECjbb2000和SPECjvm98的db中70%～94%的同步操作,大幅度地提高15%～31%的程序的运行速度.

摘要:提出了一种基于组织实体能力的软件过程建模方法(organizational entity capabilities based software process modeling method,简称OEC-SPM),针对软件过程的特殊性,将具有确定能力的组织实体定义为建模过程中的核心要素和基本单元——过程Agent(过程主体).过程Agent根据其自身的目标、知识、经验和能力,在确定的项目目标和约束环境下,通过主动和自治的行为推理,生成具体的软件开发过程和生产过程,为软件项目开发提供正确的决策和有效的支持.该方法由于在建立软件过程时充分考虑过程执行者完成目标的能力,使建立的过程具有良好的可预见性,具备过程稳定执行的前提,因此从根本上解决了软件过程不稳定、难以控制等问题.

摘要:针对服务组合过程中生成复杂业务所涉及的用户个性化、动态生成等问题,提出了一种基于服务关系本体的交互式服务生成方法.该方法从3个视点对服务的关系进行分析,构建了服务关系本体,进而在服务生成中,通过挖掘服务的动态语义,获取用户意图,结合服务关系本体以引导后继服务的匹配.该方法可以灵活地适应用户及业务提供者的需求变化,获得较优的服务匹配结果,同时还提高了服务组合的效率.最后,实现并给出了支持该方法的原型系统以及实验结果,表明了该方法的可行性与有效性.

摘要:提出一种基于判别模型的拼写校正方法.它针对已有拼写校正系统Aspell的输出进行重排序,使用判别模型Ranking SVM来改进其性能.将现今较为成熟的拼写校正技术(包括编辑距离、基于字母的n元语法、发音相似度和噪音信道模型)以特征的形式整合到该模型中来,显著地提高了基准系统Aspell的初始排序质量,同时性能也超过了一些商用系统(如Microsoft Word 2003)的拼写校正模块.此外,还提出了一种在搜索引擎查询日志链中自动抽取拼写校正训练对的方法.基于这种方法训练的模型获得了基于人工标注数据所得结果相近的性能,它们分别将基准系统的错误率降低了32.2%和32.6%.

摘要:从动机、理论和实现三方面系统地阐述了粒度粗糙理论体系.分析了构建粒度粗糙理论的3点动机:1) 通过显式编码语义上下文的信息表示模型,强调粗糙性的表示语义;2) 通过半结构化思想设计表示模型,扩展粗糙性方法适用的信息源;3) 通过构建纯粹总分学关系上的粗糙性,描述丰富的信息结构应用语境,扩展粗糙性方法到总分学推动的领域,并展示结合总分学和计算机科学创建新型跨学科方法学的潜力.理论上定义了粒度表示演算,使其兼具一般信息源和粗糙性方法底层表示系统的双重功能,在此基础上构造内核、外壳及主体信息颗粒,分别对应粗糙性的下界近似、边界区域及上界近似概念.实现上,提出了通过"实体-属性-值"模型开源系统进行粒度粗糙理论快速原型化的思路,从而提供实验平台验证理论的正确性,同时,更自然地对临床数据进行粗糙性分析.作为总结,阐述了粒度粗糙理论的意义、未解决问题及未来的研究方向.

摘要:对诊断问题的分解进行研究,给出了候选诊断的分解与组合定理.在此基础上,提出了利用分步求解方法实现诊断分解的算法,并对算法的正确性、完备性和复杂性进行了证明.实验结果表明,分步求解方法明显提高了包含多个输出的系统的诊断效率.与利用变量假定例化值分解诊断问题的方法相比,该算法能提高了效率并且扩大了适用范围.

摘要:分析了一般术语公理下推理的主要难点:在模糊解释中的隶属度不是离散值,而是区间[0,1]上的连续值.为解决该难点,提出了模糊描述逻辑FALCN下的模糊解释离散化方法,从而使解释中的隶属度都属于一个特殊的有限离散集合.基于该离散化方法,给出一般术语公理下FALCN推理问题的离散Tableau推理技术,包括离散Tableau的定义以及离散Tableau的构造算法,并证明了算法的正确性、完备性和复杂度.

摘要:以自治计算的研究为背景,利用可废止逻辑理论的非单调知识表征和推理机制,提出一种能够动态接受规则变更、灵活处理实时发生的规则冲突,并进行高效的非单调推理的柔性Agent模型.这种Agent既是自主的,又是可控的,而且可以在开放、动态的环境中通过合同与其他Agent进行协同工作.

摘要:应用最大-最小相似度(maximum-minimum similarity,简称MMS)学习方法,对基于高斯混合模型的文本区域提取方法中的有关参数进行优化.该学习方法通过最大化正样本相似度和最小化反样本相似度获得最佳分类能力.根据这种判别学习思想,建立了相应的目标函数,并利用最速梯度下降法寻找目标函数最小值,以得到文本区域提取方法的最优参数集合.文本区域提取实验结果表明:在用期望最大化(expectation maximization,简称EM)算法获得参数的极大似然估计值后,使用最大-最小相似度学习方法,使文本提取综合性能明显提高,开放实验的召回率和准确率分别达到98.55%和93.56%.在实验中,最大-最小相似度学习方法的表现还优于常用的判别学习方法——最小分类错误(minimum classification error,简称MCE)学习方法.

摘要:分析了文本分类过程中存在的混淆类现象,主要研究混淆类的判别技术,进而改善文本分类的性能.首先,提出了一种基于分类错误分布的混淆类识别技术,识别预定义类别中的混淆类集合.为了有效判别混淆类,提出了一种基于判别能力的特征选取技术,通过评价某一特征对类别之间的判别能力实现特征选取.最后,通过基于两阶段的分类器设计框架,将初始分类器和混淆类分类器进行集成,组合了两个阶段的分类结果作为最后输出.混淆类分类器的激活条件是:当测试文本被初始分类器标注为混淆类类别时,即采用混淆类分类器进行重新判别.在比较实验中采用了Newsgroup和863中文评测语料,针对单标签、多类分类器.实验结果显示,该技术有效地改善了分类性能.

摘要:对于空间中的任一子集,通过基本邻域信息粒子进行逼近,由此提出了邻域信息系统和邻域决策表模型.分析了该模型的性质,并且基于此模型构造了数值型属性的选择算法.利用UCI标准数据集与现有算法进行了比较分析,实验结果表明,该模型可以选择较少的特征而保持或改善分类能力.

摘要:在分析了基于遗传原理的公式发现方法的优势与不足的基础上,根据免疫原理和MHC(major histocompatibility complex)在免疫系统中的调控作用,提出了一种应用于公式发现领域的算法IFDA(immune formula discovering algorithm)来解决公式进化中优良结构不易保护的问题.该算法将公式翻译成树状图,并按深度优先的编码方法形成抗体的恒定区和可变区代码,把公式片段编码成为MHC代码,借鉴MHC调控原理指导抗体进化,寻找出数据集合中蕴涵的规律,并用公式的形式表示.通过对多组基准数据的实验说明,此方法在公式复杂度和收敛速度方面比基因表达式算法有更好的性能.

摘要:提出一种半监督聚类算法,该算法在用seeds集初始化聚类中心前,利用半监督分类方法Tri-training的迭代训练过程对无标记数据进行标记,并加入seeds集以扩大规模;同时,在Tri-training训练过程中结合基于最近邻规则的Depuration数据剪辑技术对seeds集扩大过程中产生的误标记噪声数据进行修正、净化,以提高seeds集质量.实验结果表明,所提出的基于Tri-training和数据剪辑的DE-Tri-training半监督聚类新算法能够有效改善seeds集对聚类中心的初始化效果,提高聚类性能.

摘要:分析了中英文混合环境下多模式匹配的特点,以及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法.该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提出的算法在匹配中无需复杂的哈希运算,不需要回溯匹配指针,在中英文混合环境下能够进行正确、高效的匹配,而且不存在空间膨胀问题,具有较低的空间与时间复杂度,有较大理论与应用价值.

摘要:首先对网状网容量估计与优化理论的技术难点进行分析,总结了其中的研究意义.根据国内外的研究现状,对干扰模型和调度模型进行总结与归纳,并对典型的优化模型进行了介绍.对目前容量优化算法常用的数学模型——规划模型、信息论模型、组合优化和随机过程模型进行了总结,提出了算法评价准则,对现有模型进行了点评.最后对未来的发展趋势提出了自己的观点.

摘要:僵尸网络是一种从传统恶意代码形态进化而来的新型攻击方式,为攻击者提供了隐匿、灵活且高效的一对多命令与控制机制,可以控制大量僵尸主机实现信息窃取、分布式拒绝服务攻击和垃圾邮件发送等攻击目的.僵尸网络正步入快速发展期,对因特网安全已造成严重威胁,对中国大陆造成的危害尤为严重.介绍了僵尸网络的演化过程和基本定义,深入剖析了僵尸网络的功能结构与工作机制,讨论了僵尸网络的命令与控制机制和传播模型,并归纳总结了目前跟踪、检测和防御僵尸网络的最新研究成果,最后探讨了僵尸网络的发展趋势和进一步的研究方向.

摘要:分析了无线传感器网络功率控制机制,归纳总结了设计原则和分类方法,详细介绍了当前典型功率控制算法的核心机制,并比较分析了这些算法的类别、特点和性能差异.最后结合领域内的研究现状,指出了限制无线传感器网络实用化的问题所在,提出了基于实验研究和统计分析方法建立自适应功率控制模型与实现策略的重要性.

摘要:综述了路由器缓存的作用.基于随机服务理论,分析了长相关流量模型和短相关流量模型输入路由器系统时的各种缓存分析结论,着重论述了基于TCP协议模型的各种最新缓存需求研究成果,包括经验法则、小缓存法则、基于丢包率的缓存法则和极小缓存法则.总结了以往缓存研究的不足,并提出了下一步的研究方向.

摘要:覆盖网协同缓存(overlay cooperative caching,简称OCC)聚集客户节点的资源来提供可扩展、经济有效的缓存服务.在典型的OCC系统中,节点的异构性和工作负载的不对称,容易造成节点资源使用的不平衡,形成一些负载过重的"热点"节点.但对于这一问题,已有的OCC系统缺乏有效的负载平衡机制.针对多媒体内容分发服务,设计了一种无热点的OCC策略——HFOCC(hotspots free overlay cooperative caching).通过将"热点"对象复制到低负载节点,分散服务请求,达到消除热点的目的.为了提高缓存空间的利用率, HFOCC将一个节点的缓存空间动态地划分为home cache和replica cache两部分,并实施统一的缓存管理策略;基于一种"软"副本生命期控制机制,当工作负载发生变化时,冗余副本被及时删除,系统表现出了良好的自适应性.实验证明,HFOCC有效地提高了系统吞吐率和资源利用率.

摘要:在缺乏集中控制的无线自组网络中,节点在转发过程中所表现出的自私行为将严重影响其网络服务的可靠性.在节点理性假设的基础上,针对自组网络节点的预期收益及其协作交互过程建立了一个重复博弈模型,提出了一个激励一致性条件,在此条件下,节点将迫于惩戒机制威慑而自愿采取合作策略;并分析了节点对将来利益重视程度、机制参数和作弊检测效率对协作效果的影响.仿真结果表明,通过合理选择惩戒机制参数,能够有效抵御网络规模的增长及节点合作意愿、作弊检测效率的降低所导致的协作性削弱,进而提高存在自私节点时的整体网络性能.

摘要:多播提高了链路的传输效率,但易于造成网络拥塞.因此,在网络中实施多播拥塞控制至关重要.然而,由于Ad Hoc网络的两个本质特点,为Internet设计的多播拥塞控制不适合Ad Hoc网络:(1) 无线多跳连接引起了信息流之间在时间域和空间域的竞争;(2) 节点频繁移动导致了网络状态不断变化.首先提出了链路干扰集的概念来描述信息流竞争的特点,将网络状态不变的小时间段内的多速率多播拥塞控制问题表达成一个非线性优化问题,联合运用罚函数法和次梯度法获得此问题的优化解,相应地提出了一种有效的分布式迭代算法.在此算法基础上,针对网络状态的时变性,设计了一种基于状态检测和滚动优化的自适应多速率多播拥塞控制策略——AC²M².仿真结果表明,分布式算法能够快速收敛到最优解;AC²M²(adaptive congestion control strategy for multirate multicast sessions)策略对网络状态的变化具有较好的自适应能力,所获得的网络性能比TCP-Reno要优越得多.