武成岗 , 张兆庆 , 乔如良 , 冯晓兵 , 高琳 , 石学林 , 蒋弘山 , 崔慧敏
2004, 15(4):475-486.
摘要:传统语言COBOL从诞生至今已有近50年历史,现存约有1 000亿行代码是用COBOL编写的.维护这些遗产代码的一个有效方法是将其翻译成现代语言,例如Java.其中将COBOL语言中GOTO和PERFORM语句及其复合控制结构消除是翻译过程中的一个关键步骤.提出一种利用switch,while语句来消除GOTO和PERFORM复合控制结构的方法,实现了程序的等价变换.该方法不改变程序的控制结构,保持其可读性,并将代码膨胀率控制到2倍左右.该方法已在所开发的"C2J翻译系统"中进行应用,通过了400万行实际商用程序的测试,结果证明,该方法是正确、有效的.
2004, 15(4):487-496.
摘要:开放计算环境下的实时与非实时任务不确定并发,以及多种实时约束混合的复杂约束系统,即开放混合实时系统的需求越来越广泛.通过引入接收控制、调度服务器、自适应调节机制,提出一种开放环境下的自适应实时系统调度架构--OARtS(open adaptive real-time scheduling).它能适应开放计算环境的不确定性,有控制地接受实时任务运行;可根据系统空闲计算带宽变化,自适应地调节任务的实时等级,使得系统运行在最优的实时性能上;对于软实时任务,可根据其计算带宽需求变化,自适应地调节其计算带宽分配,以适应任务执行时间时变引起的实时不确定性.
2004, 15(4):497-503.
摘要:摘 要:现有的分布式实时协作系统多采用操作转换的方法来提供并发控制服务,但是在系统数据量很大时,系统性能不高.为解决这一问题,提出了一种新的并发控制方法madOPT:该方法利用对象所定义的操作的语义进行冲突解析,集数据对象的动态载入、数据传输和操作转换功能为一体.madOPT改进了dOPT(distributed operation transformation)算法在操作转换过程中对操作日志的遍历以提高并发控制效率,并将对象属性作为并发控制的粒度,使之支持对图形、图像对象的并发操作;同时结合组播代理,提高数据传输率,使系统整体性能得到改善.
2004, 15(4):504-511.
摘要:异构分布式系统已被广泛应用在实时嵌入式系统中,而调度算法是在进行嵌入式系统综合时,确保系统实现性能目标的一个关键问题,这是一个NP-完全问题.现有的算法主要是启发式算法,性能还有待提高.提出了一个异构分布式系统的动态BLevel优先(dynamic BLevel first,简称DBLF)算法,算法选择就绪任务中动态BLevel值最大的任务进行调度,用插入法为任务分配处理器,遵循以下3个插入原则:满足任务先后顺序关系;任务的最早完成时间(earliest-finish-time,简称EFT)最小;在EFT相等时,优先分配到利用率较低的处理器上.与现有算法比较可以看出,DBLF算法可以有效降低调度长度.
2004, 15(4):512-521.
摘要:从建构agent角度出发,提出了一个基于关系结构的包括agent意向、信念以及目标等认知状态的框架.在此框架中,实现目标的意向形成了两维序结构,其中一维表示意向间的时序关系,另一维表示意向间的相干关系,在此基础上,研究了信念、意向和目标的相互关系.因为摒弃了传统的用模态算子来刻画agent的意向的方法,所以在构建agent时,可以直接采用意向库以及意向间的时序、相干关系来表示agent的意向,从而缩小了agent理论模型与实际agent结构之间的差异,为agent结构的建立提供了必要的理论基础.
2004, 15(4):522-530.
摘要:提出了一种基于图像颜色和空间信息的彩色图像分割算法.该算法首先根据所提出的颜色粗糙度概念对图像进行颜色量化,并在此基础上使用增量式的区域生长算法发现颜色相近的像素之间的空间连通性,形成图像的初始分割区域.然后,根据融合了颜色和空间信息的区域距离,对初始分割区域进行分级合并,直到系统满足了所提出的停止区域合并的准则.最后,利用形态学的有关算法对分割区域的边缘进行平滑.实验证明,算法的分割结果与人的主观视觉感知具有良好的一致性.
2004, 15(4):531-536.
摘要:合成孔径雷达(synthetic aperture radar,简称SAR)通过对地面目标的多次照射来提高方位向上的目标分辨能力,由此使现有的SAR目标检测算法通常是一个基于SAR图像的"后处理"过程.在分析各种成像算法和现有的一些典型SAR目标检测算法的基础上,提出了一种在非成像状态下进行海岸线提取的新方法,把成像处理与目标检测问题有机地结合起来.通过真实星载SAR回波数据应用实验,证明了直接利用SAR回波对海岸线检测的有效性.
2004, 15(4):537-544.
摘要:近些年,多主体系统的理论及应用得到了人们的广泛关注,并得以迅速发展.研究者提出了很多基于多主体系统理论的模型,用于求解各种问题.AER(Agent-environment-rules)模型正是一个用于求解约束满足问题较为成功的例子.但是,主体的静态策略选择在一定程度上限制了模型的求解性能.将模拟退火算法与多主体系统思想相结合,并赋予主体更为高效的动态策略选择的能力,提出了SAAER模型(simulated annealing based AER model).基于约束满足问题经典实例--N-Queen问题和染色问题的实验表明,改进后的模型较之原模型获得了更高的效率和稳定性.对于N=10000的大规模N-Queen问题,能在200s左右的时间求得精确解.
2004, 15(4):545-549.
摘要:对于许多网络应用而言,精确的网络链路实际使用带宽的监测非常重要.首先,为了减少监测过程对实际网络带宽的影响提出一个网络链路实际使用带宽的监测模型.然后,证明求该模型最优解的问题是NP完全的.最后,通过进一步挖掘流量约束扩展该模型以进一步减少监测过程的影响.
2004, 15(4):550-560.
摘要:TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中.
2004, 15(4):561-570.
摘要:重路由技术是匿名通信系统中采用的主要技术手段之一.目前典型的匿名系统中大多采用随机重路由的策略,即在所有中转代理中随机选择一个进行转发的策略,随机转发策略要求每个中转代理知道系统中所有其他代理.随着系统的扩大,一方面中转代理数增加使得系统维护代价增加,另一方面由于部分中转代理之间距离很远,重路由带来的延迟增加.提出了一种新的重路由策略--距离优先分组重路由,实现了短距离优先转发的策略,重路由时在近距离分组中进行随机转发.分别将距离优先分组策略应用在随机概率转发和有限路长限制的重路由算法中,数学分析和模拟测试结果表明,新的重路由策略在一定分组成员数情况下能保持与非分组重路由算法相当的匿名性能,同时明显地降低了服务延迟.新的策略中每个中转代理只需知道就近分组中的代理,这为匿名系统的扩展性研究提供了一定的基础.
2004, 15(4):571-583.
摘要:在诸如文件共享等无中心的Peer-to-Peer环境中,资源共享是用户自愿的行为.在这类系统中,由于用户不为自身的行为担负(法律)责任,因而节点间的信任关系往往很难通过传统的信任机制建立.一种更合理的考虑是参考人际网络中基于推荐的信任关系建立方法.现有的模型不能很好地解决模型的迭代收敛性问题,同时缺乏对诸如冒名、诋毁等安全性问题的考虑.针对上述问题,在节点推荐的基础上提出了一种基于Peer-to-Peer环境的信任模型,并给出了该模型的数学分析和分布式实现方法.分析及仿真表明,该信任模型较已有模型在迭代的收敛性、模型的安全性等问题上有较大改进.
2004, 15(4):584-593.
摘要:延迟是评价网络性能的重要指标,也是进行其他网络性能指标测量的基础.基于全球定位系统(GPS)的端到端(end-to-end)时钟同步是测量网络单向指标的常用方法,但是其代价昂贵且缺乏灵活性.在无端到端时钟同步机制下进行网络单向延迟指标测量的关键是消除时钟偏差效应的影响.基于对时间序列分段技术的分析,提出了一种新的时间序列分段标准与改进的分段算法,实现序列的自动聚类,其时间复杂度为O(N2).将该算法应用于检测端到端时钟的动态性,识别测量过程中时钟跳变和时钟频率调整位置,实现对网络单向延迟的测量,弱化了同类工作中对时钟动态性的严格假设.同时提出了基于滑动窗的在线实时时钟动态性检测算法.实际测试实验表明,该算法是行之有效的.
2004, 15(4):594-603.
摘要:描述了一种基于多路径移动自组网络按需路由策略.在移动自组网络,由于网络节点的移动性及拓扑结构的易变性,路由成为最受关注的问题.在以前的移动自组网络路由算法中,主要采用的是传统的单路径方式.最近,多路径方式也逐渐出现,因为相对单路径路由而言,多路径为移动自组网络提供的QoS支持更可行、更高效.鉴于现有的移动自组网络多路径策略未能为源节点提供充分的信息,提出了一种新型的移动自组网络多路径路由算法.该算法可以将路由信息保存在源节点中,并依此在源节点中采用替换路径或多路径并发的方式进行数据传输.
2004, 15(4):604-615.
摘要:研究了无线局域网IEEE802.11协议的DCF(distributed coordination function)接入方式,在建模基础上进行算法改进,提出了一种新的节点自适应链路碰撞的退避算法NSAD(new self-adaptive DCF algorithm).大量的仿真实验表明,所提出的算法在吞吐量、公平性、丢包等方面较原DCF协议都有显著提高.
2004, 15(4):616-623.
摘要:随着家庭网络中的多媒体服务器和实时数据库服务器这类应用对实时的灵活性的要求不断增加,传统实时基于最长执行时间(WCET)的调度算法已经不能满足它们对性能优化的要求.因此,产生了一些软实时的调度算法来解决这些问题.提出了一种由反馈环节控制的实时调度算法,该算法用于调度能使用不精确计算模型描述的进程.算法可以在各种负载条件下,通过在调度过程中引入的反馈控制,在计算精度和计算时间上直接取得折衷,将进程错过时限的比例控制在预定范围内.
2004, 15(4):624-632.
摘要:针对分开-合并方法分割纹理图像存在的纹理特征不规则性的问题,提出了一种新的基于四分树的分开-扩张的区域分割方法.通过对各类别的不同测量区域的纹理样品进行监督分类,确定分割的初始区域和终止区域,并把样品分类的精度作为各测量区域的纹理特征的权值,根据是否满足一致性属性和区域的性质进行分开或扩张.该方法较好地处理了不同测量区域的纹理特征可信度不一致的问题,扩张的过程可提高分割的精度并避免小区域纹理特征的不稳定.实验结果表明,分开-扩张方法能有效地分割纹理图像,其分割精度优于分开-合并方法.