Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2007年 第44卷 第6期    出版日期:2007-06-15
论文
一种面向动态异构网络的容错非对称DHT方法
张三峰 吴国新
2007, 44(6):  905-913. 
摘要 ( 417 )   HTML ( 0)   PDF (586KB) ( 468 )  
相关文章 | 计量指标
设计具有更优的“度-直径”折衷关系,并能更好地适应动态、异构的Internet环境的DHT方法是结构化P2P技术研究的重点.提出一种容错、非对称的DHT方法:A-DHT. A-DHT根据接入延迟、带宽和用户行为把节点分成胖节点和瘦节点两类,并以Hyper-de Bruijn图为基础构建非对称的网络拓扑. A-DHT充分利用胖节点的消息转发能力实现了更优的、“平均度-直径”折中.同时,A-DHT又利用瘦节的冗余边得到了比各种基于字母表的DHT方法更好的容错性.介绍了A-DHT的静态拓扑结构、路由算法以及基于A-DHT构建P2P网络的若干算法.理论分析和实验证明,A-DHT在低网络负载条件下能够有效降低路径长度和延迟,在高网络负载条件下能够有效避免胖节点的过载,同时具有较好的容错特性.
一种基于无效链路的分布式故障诊断一致性协议
董 剑 左德承 刘宏伟 杨孝宗 任 潇
2007, 44(6):  914-923. 
摘要 ( 480 )   HTML ( 0)   PDF (684KB) ( 470 )  
相关文章 | 计量指标
故障诊断一致性(fault diagnosis agreement, FDA)是高可靠容错分布式系统的性能和完整性的重要保障.目前,大部分FDA协议还是只考虑单一故障组件的简单网络,而对于实际的分布式应用、故障节点和故障链路并存的系统假设更加有意义.但是,在此假设下,对恶意(拜占庭故障)组件的诊断是不可能满足FDA的.为此,首先提出了一种无效链路(invalid link)故障模型,可以更加准确地描述恶意组件的故障行为对系统的影响,有效提高故障诊断的覆盖率.在此模型基础上,提出了一个基于证据的故障诊断协议——PLFDA,可以同时对恶意节点和恶意链路进行检测和定位,并且能够满足故障诊断一致性要求.
移动自组织网络中一种基于多点中继策略的优化泛洪广播算法
施 韦 李善平 杨朝晖
2007, 44(6):  924-931. 
摘要 ( 314 )   HTML ( 0)   PDF (449KB) ( 492 )  
相关文章 | 计量指标
多点中继(multipoint relaying,MPR)是一种有效的移动ad hoc网络即时泛洪广播策略.选择尽量少的邻节点以覆盖2跳(2-hop)范围内所有节点是MPR策略的关键.然而现有的基于MPR策略的泛洪算法忽视了转发节点之间所存在的共有邻接关系对结果的影响.在分析转发节点之间连接拓扑关系的基础上,发现尚未被覆盖的2跳节点集合的势(cardinality)可以进一步压缩,从而进一步减少冗余的转发节点.同时,讨论了利用自裁减(self-pruning)提升MPR性能的可能性.据此提出了基于共有邻接关系消除的自裁减辅助MPR优化泛洪广播算法(ECARSP).理论分析和实验结果表明,ECARSP在转发节点数量和网络负载等方面均要优于现有的移动ad hoc网络MPR泛洪算法.
基于圆周运动的自组网移动模型研究
王 伟, 蔡皖东, 王备战, 李勇军, 田广利,
2007, 44(6):  932-938. 
摘要 ( 386 )   HTML ( 0)   PDF (448KB) ( 464 )  
相关文章 | 计量指标
自组网仿真研究大多基于特定的移动模型,而移动模型中节点空间概率分布是研究和评价自组网性能的理论基础.然而,现有的自组网移动模型存在诸多缺陷(如不现实的移动场景、节点的非均匀分布等).在分析和比较现有移动模型的基础上,提出一种基于圆周运动的移动模型,推导出移动节点的二维概率密度函数公式.理论分析和仿真实验表明,该模型能够克服现有移动模型的这些缺陷,为仿真和评估自组网的性能提供了精确的理论模型.
冗余最小化的IPv6拓扑发现方法
杨 柳, 李振宇, 张大方, 谢高岗,
2007, 44(6):  939-946. 
摘要 ( 441 )   HTML ( 0)   PDF (494KB) ( 514 )  
相关文章 | 计量指标
随着网络技术的高速发展,网络管理的重要性越来越突出,正确的网络拓扑是进行网络管理的基础. IPv6是公认的下一代互联网协议,其庞大的地址空间和独特的特征为拓扑发现带来了新的挑战.目前,基于ICMP的拓扑发现分为分布式和集中式两种,其主动探测的特征不可避免地产生探测冗余.分布式拓扑发现方法布署困难并且成本高.更重要的是在冗余减少上存在由探测点间冗余引起的诸多限制,因此它不能以网络友好的方式发现拓扑.由于IPv6路由器对源路由的支持,集中式的拓扑发现方法能够发现交叉链路以保证覆盖率.测量了IPv6环境下单个探测源产生的冗余,提出了冗余最小化的集中式拓扑发现方法.在引入减少冗余的后退算法基础上提出了实际网络环境下的改进算法,说明了集中式拓扑发现在IPv6环境下的可行性.实验结果表明对靠近探测点的节点减少了高达两个数量级的冗余,并能够保证令人满意的覆盖率.
一种通用访问控制管理模型
李晓峰 冯登国 徐 震
2007, 44(6):  947-957. 
摘要 ( 394 )   HTML ( 0)   PDF (549KB) ( 499 )  
相关文章 | 计量指标
目前的访问控制管理模型都是针对某种特定的访问控制模型提出的,不能适应多访问控制模型共存于一个大型系统的情况,一个管理模型不能同时适用于多访问控制模型的主要原因是管理者管理范围定义包含了某种访问控制模型中特有的组件.通过使用各种访问控制模型中共有的主体和权限来定义管理模型中的管理范围,将管理模型与访问控制模型之间的关系抽象为一个用于计算策略相关管理范围的函数,提出了一种能够用来管理不同访问控制模型的通用访问控制管理模型,为了便于模型实际使用,在模型中引入管理空间的概念与实际组织结构相对应,形成分布式访问控制管理结构,同时模型严格区分了管理空间的直接管理者和间接管理者在管理权限上的不同,使得管理者具有一定的自治性.最后讨论了管理模型中的管理规则和语义,证明了模型的完备性,并讨论和分析了针对不同访问控制模型的policy\+*算法.
主动良性蠕虫和混合良性蠕虫的建模与分析
周翰逊, 赵 宏,
2007, 44(6):  958-964. 
摘要 ( 332 )   HTML ( 0)   PDF (399KB) ( 514 )  
相关文章 | 计量指标
自从1988年Morris蠕虫爆发以来,网络蠕虫就在不断地威胁着网络的安全.传统防范措施已不再适用于蠕虫的防治,使用良性蠕虫来对抗蠕虫正成为一种新的应急响应技术.良性蠕虫的思想就是将恶意的蠕虫转化成良性的蠕虫,而且该良性蠕虫还可以运用相同的感染机制免疫主机.这种方法可以主动地防御恶意蠕虫并且在没有传统的蠕虫防御框架下仍具有潜在的部署能力.首先,分别将主动良性蠕虫和混合良性蠕虫划分成3个子类;然后,基于两因素模型分别对主动良性蠕虫和混合良性蠕虫的3个子类进行建模,推导了在有延迟以及无延迟的情况下6类良性蠕虫的传播模型;最后,通过仿真实验验证了传播模型.更进一步,基于仿真结果讨论了每种良性蠕虫抑制恶意蠕虫的效果,并且得到如下结论:在相同的感染条件下,复合型的混合良性蠕虫抑制蠕虫传播的效果最好.
基于虚拟力的混合感知网节点部署
周 彤 洪炳NFDD, 朴松昊
2007, 44(6):  965-972. 
摘要 ( 383 )   HTML ( 0)   PDF (468KB) ( 550 )  
相关文章 | 计量指标
感知网一般是由静态的或移动的节点组成,为保证感知网的感知功能,节点应该有自部署和自修复能力.然而全部由移动传感器组成的感知网的成本太高,为保证感知网的覆盖功能和低成本,提出了一种在静态传感器节点中加入移动传感器节点的混合感知网形式.为了更好地部署这些节点,最大化覆盖待感知区域,提出了一种基于节点间虚拟力的移动节点部署方法,利用静态节点和移动节点以及移动节点之间的虚拟人工势场产生的作用力来控制移动节点的运动,使移动节点能够在较短的时间内,以较少的能量消耗到达自己合适的位置.在理论上分析了算法的可行性,用仿真实验验证了此算法的有效性,并和其他3种类似算法进行了性能比较.
具有时变时滞的递归神经网络的渐近稳定性分析
张 忠 李传东
2007, 44(6):  973-979. 
摘要 ( 394 )   HTML ( 0)   PDF (412KB) ( 666 )  
相关文章 | 计量指标
当神经网络应用于最优化计算时,理想的情形是只有一个全局渐近稳定的平衡点,并且以指数速度趋近于平衡点,从而减少神经网络所需计算时间.研究了带时变时滞的递归神经网络的全局渐近稳定性.首先将要研究的模型转化为描述系统模型,然后利用Lyapunov-Krasovskii稳定性定理、线性矩阵不等式(LMI)技术、S过程和代数不等式方法,得到了确保时变时滞递归神经网络渐近稳定性的新的充分条件,并将它应用于常时滞神经网络和时滞细胞神经网络模型,分别得到了相应的全局渐近稳定性条件.理论分析和数值模拟显示,所得结果为时滞递归神经网络提供了新的稳定性判定准则.
一个基于智能的MAS模型及其方法论
李超明 苏开乐
2007, 44(6):  980-989. 
摘要 ( 438 )   HTML ( 1)   PDF (569KB) ( 430 )  
相关文章 | 计量指标
为了得到好的体系结构模式来将模式驱动的方法用于多智能体系统(MAS)的设计,必须有形式上抽象但是技术上细化的方法论.基于智能思想的提出,使得以智能作桥梁将AO,PO和OO的优点融合,并以此提出一种覆盖了从事务分析到Agent组织系统实现全过程而又比较技术化的方法论IB. 同时提出一个基于智能的智能系统模型(MIBIS),通过模型的构造过程来叙述方法论.因为模型以及构造过程的形式化和整个过程的技术化,所以使得该模型和方法论能够被用于体系结构模式的归纳,也能用于工程的实用.而且该模型所表达的结构有良好动态组织性、实用性、实时性、扩展性和重用性.
Skyline查询处理数据立方体代数
黄震华 汪 卫
2007, 44(6):  990-999. 
摘要 ( 660 )   HTML ( 0)   PDF (608KB) ( 396 )  
相关文章 | 计量指标
维空间的Skyline查询处理技术是近年来数据库技术领域的一个研究重点和热点.目前所有的研究工作都是直接在原始数据表上执行关系查询代数操作来获得最终的结果集,然而,随着原始数据表的数据量和维目标个数的增大,这些研究工作将不再适用.基于此,首次研究Skyline集合上的查询代数操作,使得Skyline查询处理的输入数据来自于小规模的Skyline结果集,而非海量的原始数据表.并且,首次给出一个集成多维对象集合和该对象集合上的Skyline结果集的形式化模型,该模型适合目前Skyline查询计算的应用,并在该模型的实例上研究Skyline集合的查询代数操作.同时,给出查询代数体系的代价评估模型.实验表明,给出的数据模型和查询代数体系具有有效性和实用性.
基于最小生成树的数据流窗口连接优化算法
钱江波, 徐宏炳, 董逸生, 王永利, 刘学军, 杨雪梅,
2007, 44(6):  1000-1007. 
摘要 ( 406 )   HTML ( 0)   PDF (524KB) ( 492 )  
相关文章 | 计量指标
与传统关系数据库不同,数据流管理系统主要处理并发的连续查询.由于查询可能随时增删,所以其主要关注适合查询增删的并发连续查询优化,而不是单条查询优化.提出适合频繁增删查询环境下的数据流窗口连接优化算法.对于新注册的查询以类似最小生成树算法写出数据流的探测序列,然后在不更改其他查询探测序列顺序的情况下尽量合并,减少重复计算.注册或删除查询并不影响其他的查询计划,不需要执行繁琐的查询计划迁移.理论分析和实验证明,该算法简单,优化性能在可接受的范围内,尤其适合查询更新频率较高的系统.
一种基于城市交通网络的移动对象全时态索引
陈继东 胡志智 孟小峰 王 凌
2007, 44(6):  1008-1014. 
摘要 ( 341 )   HTML ( 0)   PDF (406KB) ( 470 )  
相关文章 | 计量指标
高效地管理移动对象以支持查询是一个重要课题.为了支持在城市交通网络上的移动对象过去、现在和将来位置查询,提出了一种新的索引技术.首先提出基于模拟预测的位置表示模型来改进对移动对象将来运动轨迹的预测精度;其次根据城市交通网的特征,设计了一种全新的动态结构自适应单元(AU),将其开发为一个基于R树的索引结构(current-AU);最后在AU的基础上进行扩展(past-AU)使其支持移动对象历史轨迹查询并且避免了大量的死空间.实验证明,AU索引优于传统的TPR树和TB树索引.
面向移动对象的高效预测范围聚集查询方法
廖 巍 景 宁 钟志农 陈宏盛
2007, 44(6):  1015-1021. 
摘要 ( 326 )   HTML ( 0)   PDF (420KB) ( 448 )  
相关文章 | 计量指标
预测范围聚集查询是移动对象数据库中重要的查询类型之一.提出了一种PRA树高效预测范围聚集查询索引,对速度域进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶中,针对每个速度桶,提出了一种聚集TPR树索引,通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价. PRA树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性.提出了一种增强预测范围聚集查询EPRA算法,采用更精确的剪枝搜索准则,减少了查询所需要访问的节点代价.实验结果与分析表明,基于PRA树索引的EPRA查询算法具有良好的查询性能,优于通用的TPR\+*树索引.
一种基于梯度的健壮的指纹方向场估计算法
梅 园 孙怀江 夏德深
2007, 44(6):  1022-1031. 
摘要 ( 594 )   HTML ( 2)   PDF (1424KB) ( 1023 )  
相关文章 | 计量指标
作为指纹的全局特征,指纹方向场在自动指纹识别系统中发挥了非常重要的作用.提出了一种基于梯度的健壮的指纹方向场估计算法,新算法首先归一化点梯度向量并计算块梯度向量及相应的块一致性;然后估计噪声区域;最后采用基于迭代的方法,重新估计所有块梯度向量并将梯度向量场转化为方向场.实验结果表明,与已有基于梯度的指纹方向场估计算法相比,新算法具有更高的准确性及抗噪性能,并能较好地估计大块噪声内的方向场,是一种较为健壮的指纹方向场估计算法.
带局部形状参数的三次均匀B样条曲线的扩展
徐 岗 汪国昭
2007, 44(6):  1032-1037. 
摘要 ( 375 )   HTML ( 0)   PDF (367KB) ( 464 )  
相关文章 | 计量指标
带形状参数的B样条曲线的构造已成为计算机辅助几何设计中的热点问题.为了使形状参数具有局部修改功能,给出了两类带局部形状参数的调配函数,它们都是三次均匀B样条基函数的扩展.基于给出的调配函数,定义了两种带局部形状参数的分段多项式曲线.可以通过改变局部形状参数的取值对曲线进行局部调整.调整形状参数可使三次多项式曲线在三次均匀B样条曲线远离控制多边形的一侧摆动,而四次多项式曲线在三次均匀B样条曲线的两侧摆动.最后讨论了它们在曲线设计及曲线插值中的应用.造型实例表明,该类曲线在计算机辅助几何设计中具有重要的应用价值.
面向移动计算终端的渐进几何简化方法
罗笑南 林谋广 姬长波 李志勇
2007, 44(6):  1038-1043. 
摘要 ( 405 )   HTML ( 1)   PDF (347KB) ( 462 )  
相关文章 | 计量指标
在移动计算终端上进行移动三维图形计算是一个重要的课题.针对移动计算终端屏幕小、计算能力低、无线网络带宽受限等特点,研究如何进行移动三维图形的渐进显示具有十分重要的意义.提出了利用Kobbelt四边形细分算法的逆过程迭代地进行简化的方法,通过迭代地把模型分割为奇点和作为简化模型的偶点,实现了对四边形网格几何模型的渐进式简化;提出了渐进显示的模式,通过把每一层的奇点作为可添加的细节信息,可以支持在终端上渐进显示不同细节模型并实现原模型的无损还原.完整的简化方法简单快速,可以高效地实现移动三维图形的渐进简化显示.最后在型号为Mio 336的PDA上的实验结果表明,研究成果在移动计算终端上进行实时交互等方面具有很好的应用前景.
个性化领域知识支持的用户主导需求获取方法
舒风笛, 赵玉柱, 王继NB0,7, 李明树,
2007, 44(6):  1044-1052. 
摘要 ( 427 )   HTML ( 0)   PDF (539KB) ( 522 )  
相关文章 | 计量指标
应用软件的需求获取与应用领域的特征密切相关,用户的参与日益受到重视,然而用户对系统的认识通常模糊且不完整,且对于多用户系统,需要拥有局部需求的多用户进行协同,才能得到完整、一致的需求.提出一种用户主导的需求获取方法,根据用户特征及其上下文环境,为用户进行需求定义提供个性化的领域知识支持,包括领域需求资产推荐和对多用户协同需求获取的建议.应用实例说明了该方法的可行性,且对于提高用户参与程度、改进领域知识重用效果,从而最终提高需求获取的质量具有积极意义.
基于一种新的边权编码方案的中国邮递员问题的DNA计算模型
韩爱丽, 朱大铭,
2007, 44(6):  1053-1062. 
摘要 ( 323 )   HTML ( 0)   PDF (584KB) ( 510 )  
相关文章 | 计量指标
权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G′=(V′,E′).图G的每条边e\-i被分别映射为图G′的一个顶点v′\-i. 若G中e\-i与e\-j邻接,则连接G′中v′\-i和v′\-j. 若G中v\-i为奇顶点,则在与v\-i关联的边对应的G′的顶点上添加自环.用于编码顶点v′\-i的DNA串s\-i的长度等于边e\-i的权值.用于编码边v′\-iv′\-j的DNA串s\-\{ij\}为s\-i的后半部分与s\-j的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围.
基于分治的背包问题DNA计算机算法
李肯立, 姚凤娟, 李仁发, 许 进,
2007, 44(6):  1063-1070. 
摘要 ( 378 )   HTML ( 0)   PDF (489KB) ( 551 )  
相关文章 | 计量指标
如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2\+\{q/2\}),其中q为背包问题的维数.与最近文献结论进行的对比分析表明:算法将求解背包问题所需的DNA链数从O(2\+q)减少至O(2\+\{q/2\}),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.
一种面向对象的Internet存储服务系统Granary
胡进锋, 洪春辉, 郑纬民,
2007, 44(6):  1071-1079. 
摘要 ( 448 )   HTML ( 0)   PDF (492KB) ( 365 )  
相关文章 | 计量指标
Granary是一个Internet存储服务系统.和其他已有类似系统相比,Granary具有如下两个特点: ①面向对象的数据管理,支持属性级的数据查询,这一点极大地方便了上层应用系统的开发; ②对于系统环境的自适应性,无论在怎样的系统规模下,组成结点的动态性如何,也无论这些结点的能力分布如何,Granary都可以自动调节,取得当前系统环境下的最优性能.阐述了Granary的体系结构及主要模块的设计方法. Granary的系统实现已经完成,并在实验室范围内投入使用.计划将融入China Grid提供广域存储服务.
LS CSIMD配置存储器组织及管理算法研究
周国昌 沈绪榜
2007, 44(6):  1080-1087. 
摘要 ( 349 )   HTML ( 0)   PDF (476KB) ( 327 )  
相关文章 | 计量指标
通过对LS CSIMD体系结构的深入研究,提出了一种支持扩展配置存储器寻址空间的配置存储器组织结构(配置指令采用立即数寻址),该结构通过增加配置存储器容量,可以有效地降低配置延迟.同时,针对LS CSIMD配置存储器的组织结构,提出了一种基于任务核频率和容量的配置数据管理算法.该算法根据配置任务序列特征,动态产生静态区容量,并根据任务核频率和容量进行调度,有效地减少了重复取入片上的配置数据总量,从而降低了配置延迟.实验结果表明,该算法不但时间复杂度低(最好情况下O(n)),而且当任务核数较多且任务核之间容量相差较小时可得最优解,其他情况下可得到次优解.