计算机系统与计算机网络中的动态优化：模型、求解与应用
摘要：动态优化是计算机系统与计算机网络中进行资源分配与任务调度等方面研究所采用的主要理论工具之一.目前,国内外已开展大量研究,致力于深化动态优化的理论研究与工程应用.文中从模型、求解与应用3个角度,对马尔可夫决策过程动态优化理论模型进行了综述,并重点介绍了将动态优化理论与随机Petri网理论相结合的马尔可夫决策Petri网和随机博弈网模型,详细讨论了这些模型的建模方法、求解算法与一些应用实例.最后,对全文进行了总结,并对未来可能的研究方向进行了展望.多射频无线Mesh网络组播端到端时延建模与优化
摘要：针对802.11多射频无线Mesh网络（MR-WMN）不能有效支持端到端低时延组播的问题,首先围绕MAC层传输时延和Mesh层排队时延建模分析,并提出低时延组播路由模型MR-MED（Multi-Radio Multicast End-to-End Delay）.其次证明全局流干扰最小化问题是一个NP完全问题且全局流干扰和网络密度的数学关系符合dPlN分布,在此基础上提出有效减小MAC层流内和流间干扰的DCA算法.最后提出流量自适应的组播多径路由方案MMRA,有效减小Mesh层排队时延.仿真与常见算法的比较表明,提出的模型准确刻画了MR-WMN的组播时延,且联合运用DCA和MMRA有效降低了端到端时延.Ad Hoc网络中一种基于防策略支付模型的安全激励合作算法
摘要：Ad Hoc网络中节点之间的正常通信都是通过节点相互合作来进行中继转发.但是,Ad Hoc网络由于受到自身能量、可用带宽和计算能力的限制,节点往往表现出自私性,因此激励节点合作转发的积极性成为当前AdHoc网络的研究热点.该文基于算法机制设计中的思想,对Ad Hoc-VCG模型进行具体分析,指出其存在的问题,提出了一种防策略和防共谋攻击的支付模型,设计了一种包含路由建立和数据包转发过程的安全激励合作算法ICTP.最后,通过仿真实验来验证该算法的有效性,并与Ad Hoc-VCG、COMMIT和LMOCP算法进行了性能对比.仿真结果表明：ICTP算法较其它3种算法在性能上有了显著的改善.基于联合信道特征的中继物理层安全传输机制
摘要：针对中继节点不可信的问题,提出了一种基于联合信道特征的中继物理层安全传输机制.首先将中继前后的两个信道等效合并为一个,得到联合信道特征.然后在联合信道特征的零空间中,增加人工噪声,使参与转发的中继节点无法获得有效信息量.仿真结果表明：当增加的人工噪声处于合法接收者信道特征的零空间时,可以提高协作中继系统的保密容量,合法接收者的误码率要远低于不可信中继;保密容量随中继数量增加的变化趋势与窃听者的分布相关.基于量子逻辑的图灵机及其通用性
摘要：基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机（简称量子图灵机）及其一些变形,给出了包括非确定型量子图灵机l-VTM,确定型量子图灵机l-VDTM以及相应类型的多带量子图灵机,并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式,证明了这两种定义方式在量子逻辑意义下是不等价的.进一步证明了l-VTM、l-VDTM与相应类型的多带量子图灵机之间的等价性.其次,给出了量子递归可枚举语言及量子递归语言的定义,并给出了二者的层次刻画,证明了l-VTM与l-VDTM不等价,但两者作为量子递归语言的识别器是等价的.最后,文中讨论了基于量子逻辑的通用图灵机的存在性问题,给出了一套合理编码系统,证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在,而在其所取值的正交模格有限时是存在的.模糊知识的三种否定及其集合基础
摘要：对于模糊知识中＂否定＂的认知与处理,文中从概念层面上区分模糊知识中的矛盾否定关系与对立否定关系,研究发现了模糊知识中存在一规律：一对对立的概念为模糊概念,则它们之间必然存在＂中介＂的模糊概念;反之,如果一对对立的概念之间存在中介的模糊概念,则对立的概念必然是模糊概念.因此,作者提出在模糊知识的否定关系中存在三种不同的否定关系,即矛盾否定关系、对立否定关系和中介否定关系,并给出它们的形式定义.为了能够刻画这些关系的内在性质与联系,作者提出了一种新的具有矛盾否定、对立否定和中介否定的模糊集FSCOM,并讨论了FSCOM的特征、FSCOM的基本运算与性质以及FSCOM与Zadeh模糊集的关系等.在后续文中将表明,FSCOM是一种处理实际中的模糊知识及其各种否定的有效方法.（l,d）-模体识别问题的遗传优化算法
摘要：转录因子结合位点识别在基因表达调控过程中起着重要的作用.文中提出了一种贝叶斯模型驱动的模体识别的遗传优化算法GOBMD（Genetic Optimization with Bayesian Model for Motif Discovery）.GOBMD首先使用一个基于位置加权散列的投影过程,将输入序列中的l-mers投影到k维（k量子搜索算法的多相位关系研究
摘要：假设给定一个总数为N的无序数据库,极其复杂的计算使得几乎不可能建立一个精确的数学公式来描述这个结论：在二维复子空间中,对于一个等幅分布的初始态,存在两个定义在实数域上的相位旋转角集合以使得唯一的目标态能以100%的成功概率找到;文中采取了一种近似的计算方法,通过归纳法推导出了多相位匹配方程.倘若其中一个相位旋转角集合中的元素个数j相对于N（N足够大）较小,则该方程就能保证唯一的目标态以较高的成功概率找到.接着,通过文中推导出的一个递推关系式,对任意给定的j〉2,分析了Long算法的计算复杂性.最后,通过一些数值模拟的实例进一步验证了多相位匹配方程的有效性.一种适合于频繁位置更新的网络受限移动对象轨迹索引
摘要：移动对象索引是支持海量移动对象管理的一项关键技术.目前的移动对象时空轨迹索引方法如STR-Tree、TB-Tree、FNR-Tree、MON-Tree等均直接以轨迹单元作为基本的索引记录单位,在位置更新时需要频繁地在索引中插入新的记录,从而严重地影响了数据库的总体性能.为了解决上述问题,文中提出一种网络受限移动对象的动态概略化轨迹R树索引（DSTR-Tree）.DSTR-Tree将索引空间划分成等距格栅,并通过格栅单元对每一条移动对象轨迹进行概略化,然后以概略化轨迹单元为基本索引记录单位建立R树索引.由于概略化轨迹的粒度大大粗于原始轨迹,因此移动对象不需要在每次位置更新的同时触发索引更新,而仅需要在轨迹跨越当前格栅单元时才进行索引更新,从而显著地降低了索引更新的代价.实验结果表明,DSTR-Tree在移动对象数据库频繁位置更新的实际运行条件下,提供了良好的索引维护及总体查询处理性能.HybridHP：一种轻型的内核完整性监控方案及其形式化验证
摘要：虽然传统的虚拟化监控方法可以在一定程度上保障操作系统安全.然而,虚拟监控器VMM中管理域Domain0的存在以及操作系统级的切换所带来的性能损失是很多具有大型应用的操作系统所不能接受的.注重硬件虚拟化技术的监控能力而摒弃其不必要的虚拟化能力,提出了一个新型的通用的虚拟化监控框架HybridHP,并实现其原型.HybridHP将管理域和虚拟机监控机制两者整合到被监控操作系统的地址空间,具有很好的获取被监控系统操作语义的能力.利用Isabelle/HOL形式化辅助证明工具验证HybridHP的隔离性、安全性和监控能力.最后对HybridHP进行了攻击实验和性能评估,结果显示HybridHP提供了和传统的虚拟化监控方案相同的安全保障,并具有很好的系统性能.对等点播系统中节点搜索机制研究
摘要：对等点播系统（P2P-VoD）中的跳转操作需要高效的节点搜索,如何快速查找到＂合适＂的节点是个挑战.＂合适＂包含两方面因素：（1）内容匹配;（2）物理性能匹配.而传统的方法大部分只涉及对前者的研究.文中提出了一种层次化的搜索模型（简称Mediacoop）,不仅可以让搜索到的节点在内容上满足要求,而且在物理性能上也能满足要求.具体而言,Mediacoop首先利用播放距离来索引全部节点,再利用延迟特征优选内容上已经符合要求的节点.在NS2模拟器上的实验表明,Mediacoop在用户体验和系统开销上均优于传统的方法.同时,在实际系统CoolFish中的部署和运行也验证了Mediacoop的实用性.面向互动式网络场景再现的流速控制系统与方法
摘要：互动式网络场景再现是一种重要的真实网络流量产生方法.然而,由于流量产生过程的复杂性,基于精确的数学模型对该过程产生流速进行控制是一个较为困难的新问题.文中设计实现了一个面向互动式网络场景再现的流速控制系统,并将网络场景再现过程中的流速控制问题转化为目标跟踪控制问题进行求解.该系统采用一种基于函数近似器的流速控制方法,利用函数近似器对系统的输入输出关系进行描述,通过动态调整系统输入流量来对回放过程输出流量进行跟踪.最后,利用真实网络流量实验考察了文中系统和方法在不同丢包、传输延迟以及会话阻断环境下的实际控制效果,并从收敛时间、产生输入输出、控制误差等角度对系统的控制性能进行了分析.一种缩短下载时间优先的自适应BitTorrent激励协议
摘要：BitTorrent激励机制的目标是保证节点上传和下载之间的公平性,但相比公平性而言,实际应用中的节点更优先考虑的是文件下载时间,据此文中提出了一种缩短文件下载时间优先的自适应BitTorrent激励协议AIPS.文中首先基于Markov模型对BitTorrent现有激励机制的效果给出了定量分析,分析了激励机制下的文件传输结构,并用概率分析方法给出了该传输结构下最小化文件下载时间的条件.应用分析结果文中定义了一个以缩短文件下载时间为效用的博弈,在该博弈达到Nash平衡时各节点采用的策略就是激励协议AIPS.模拟实验表明文中提出的AIPS较现有的BitTorrent激励协议能明显提高文件共享系统性能,提高文件下载效率.基于Vague集相似度量的图像隐写系统安全性测度
摘要：由于图像隐写所引起的各种统计特征变化是不确定的,文中将Vague集相似度量引入隐写系统的安全性评价中.从图像的一阶统计特征和二阶统计特征两方面,定义了基于载体数据及载密数据相关Vague集相似度量的隐写系统一阶和二阶安全性测度,证明了该安全性测度的有界性,对称性和一致性.在假设图像满足独立同分布的条件下,证明了所提出的两种安全性测度是等价的.结果表明,所提出的二阶安全性比一阶安全性能更好地反映隐写引起的载体统计分布变化.与确定模式下的安全性测度相比,当嵌入率低于0.5比特/像素,新的测度可更好地度量隐写系统安全性,因此该测度对小容量的隐写及隐写分析算法设计具有更好的指导作用.覆盖表生成的遗传算法配置参数优化
摘要：覆盖表生成是组合测试的关键问题,很多数学方法、贪心算法以及演化搜索方法等被应用于生成各种覆盖表.针对演化搜索方法的性能受到方法本身配置参数影响很大这一实际问题,文中以二维覆盖表生成为实例,系统地对典型的演化搜索方法——遗传算法的种群规模、进化代数、交叉概率、变异概率以及遗传算法的变种算法等因素进行探索,设计了pair-wise法、Base choice法和爬山法3条实验路线探索遗传算法的这些配置参数及其相互作用对算法生成二维覆盖表效果的影响,并回答两个问题：对于特定二维覆盖表生成问题,是否存在遗传算法的最优参数配置;对于一般的二维覆盖表生成问题,是否存在通用的遗传算法最优参数配置.基于类型预测的甚块预测器
摘要：高性能的甚块预测器是保证EDGE体系结构性能的关键手段.为研究性能更好的甚块预测器,文中通过仿真实验发现甚块的出口类型独立于甚块的出口个数和甚块的动态执行结果而存在.以此为据,提出了基于类型预测的甚块预测器.该预测器摈弃了甚块出口号,直接对甚块出口类型进行预测.随后,根据对甚块出口类型可预测性的分析,通过实验证明甚块出口类型与历史和路径信息相关.仿真结果显示,与经典的基于出口预测的甚块预测器相比,文中提出的基于类型预测的甚块预测器能够将每千条指令误预测次数平均降低约10%.直接匿名证言协议的性能估算新方法
摘要：性能问题是阻碍DAA推广和应用的首要问题.为了进一步优化该协议的性能,找出性能瓶颈,定量地分析和测量DAA中各个实体的性能负荷分布是一个十分重要且必须的工作.文中详细分析了DAA的协议流程,提出了以机器周期为基本性能单位的性能负荷分布测量方法——归一化统计法（Normalized Statistics,NS）.该方法需要首先分析DAA协议中的各种复杂运算,针对不同的运算选用当前性能较好的算法,然后统计各个算法中大整数单精度乘法、单精度加法、读内存、写内存等基本运算的数目,最后通过汇总并转换得出DAA协议中各实体以机器周期为单位的性能负荷分布和总性能负荷.比较分析表明,该方法不仅能相对准确、精细、有效地定量计算出DAA协议中各实体的性能负荷和总的性能负荷,而且测出的性能负荷具有平台无关性.最后为了说明该方法的有效性,将NS方法应用于有关可信计算匿名证明的一个典型方案的性能负荷估算.