算法优化与应用


参数计算理论

一个问题如何被有效地求解一直是计算机科学的核心问题。按照经典的NP-完全性理论,一旦一个问题被证明是NP-难的,就意味着这个问题是难解的,即目前很难找到能够有效求解它的算法。然而在实际工程应用中遇到的许多问题都是NP-难的。为此,人们提出了许多求解方法,这其中包括多项式近似算法、随机算法和启发式算法等。

参数计算和复杂性理论是近些年才发展起来的一种求解NP-难问题的新方法。它基于这样一个观察:通常来源于实际应用中的问题实例伴随着一个或若干个小参数,如果能够充分利用这些小参数,仍然有可能获得求解这些问题实例的有效算法,尽管这些问题在理论上可能是难解的。在参数理论中,若一个问题存在一个时间复杂度为f(k)nO(1)的参数算法,那么当k<<n,这个参数算法是有效的,并称这个问题是固定参数可解的。

本课题组将同时从参数问题的固定参数可解性、固定参数不可解性和固定参数枚举复杂性三方面进行研究。在固定参数可解性方面,我们将从实际应用出发,研究设计快速参数算法的新技术。在固定参数不可解性方面,我们将从结构理论出发,研究W[1]难解性的实质。在固定参数枚举复杂性方面,我们将研究枚举理论和实用枚举算法技术。另外许多有用的参数算法设计技术都还没有具体的软件实现。我们将着重从实用性出发,研究这些技术物理实现的思路和方法,设计出实用有效的软件,拓宽这些技术实用的领域范围。


算法在网络优化中的应用

由于网络应用的多样性与实际需求的驱动,网络应用中存在很多人们密切关心的设计和优化问题,例如,无线网络中最小能量路由问题、最大生命周期问题和能量高效的数据采集问题等。然而网络中相当一部分问题是NP-难解的,因此提出有效的算法求解网络中的优化问题在理论上和实际中都有十分重要的意义。

网络中的优化问题大多数是NP-难解的,基于传统算法理论的大量计算方法在处理这些计算NP-难问题时效果会变得很差(时间为指数级),想精确的解决这些问题是不可能的。目前网络中多采用启发式算法和近似算法来解决实际问题。

本课题组对网络中的一些问题进行深入研究,在已有模型的基础上或对问题重新进行数学描述,以提出更为实际有效的启发式算法和近似算法。但启发式和近似算法都有一定的局限性,无法得到问题的最优解。参数计算理论与技术是处理NP-难解问题的新思路、新手段,其根据网络的实际应用情况,将所给出的问题参数化,而所取参数在实际应用中只在一个小的范围内变化,从而充分利用“小参数”这一特性。

本研究小组充分利用我们在参数算法设计和分析研究中所取得的经验和优势,以深厚的理论研究为基础,研究参数化网络计算问题的特殊性,设计新的更快的更可靠的参数化算法,提高其在实际网络应用的效率。同时,我们也采用参数计算中的有效技术来降低问题的时间或空间复杂度,使算法更有效。 本研究小组提出的“基于color coding的蠕虫特征自动提取算法”,就是采用参数中的彩色编码技术降低问题的搜索空间来减少计算量,大大提高了算法的效率。参数计算理论及技术将成为解决网络中NP-难解问题的一种有效方法,促进网络研究的进一步发展。




生物信息学


生物信息学是在生命科学的研究中,以计算机为工具对生物信息进行储存、检索和分析的科学。它是当今生命科学和自然科学的重大前沿领域之一,同时也将是21世纪自然科学的核心领域之一。在生物信息学中存在大量的难解问题,如何有效地求解这类问题是生物信息学领域的关键问题。

传统的算法理论的大量计算方法需要在指数时间级求解这些问题,这使得精确的解决这些问题是不可能。此外,巨大的计算量、复杂的噪声模式、海量的时变数据给传统的计算分析带来了巨大的困难。目前,求解这些问题的计算方法大多是近似算法和启发式算法。

在对实际问题的研究中发现,在许多难解问题中存在一定的参数,如果能有效利用这些参数,仍然可以有效地解决这些问题。本课题组正是以参数理论为基础,建立生物计算中基础问题的参数化计算模型。在参数求解方法的基础上,结合计算智能、数据挖掘等技术对生物问题进行系统研究,提出有效求解问题的理论、模型及算法。具体研究内容包括个体单体型重建、蛋白质网络和代谢网络的功能模块挖掘、蛋白质功能预测、关键蛋白质分析、基序查找等具体生物问题。目前已经取得了阶段性的研究成果,在Bioinformatics、BMC Bioinformatics、Algorithmica、计算机学报、软件学报等知名的国际和国内期刊上发表学术论文三十余篇。本课题小组的研究成果将为生物信息学中关键与热点问题提供新的理论基础与研究方法,以推动我国生物信息学研究以及计算机基础理论研究的发展。



网络理论、安全与软件


网络编码

网络编码技术是一种不同于传统转发的技术,允许网络中的节点对需要转发的多个信息采用一定的编码系数进行计算,将计算后的结果进行转发,接收节点依 据相关的编码系数进行解码,得到所需要的信息。网络编码本身的传输特点对信息保密和可靠性有着明显的优势:由于每个节点都对输入数据流进行了编码,使得编 码节点的入出数据流在表示上是不同的,这使得跟踪者和窃听者较难直接得到或关联数据本身;采用多路径的编码传输方法,信息内容在传输时是分散的,这些特征 与安全性、可靠性的要求是吻合的,有利于避免单故障点造成的不可靠性、也有利于避免单泄密点获取完整信息的可能;网络编码译码算法在计算量上要远低于加密 解密的计算量等等,这些基本特征都非常有利于研究基于网络编码技术的网络安全性和可靠性机制。

本小组主要研究网络编码在无线网络优化方面的应用,开展了将网络编码技术结合到无线网络可靠性和安全性方面的研究。具体的优化目标包括无线传输的效 率、可靠性和安全性,在此基础上提出适用于无线网络环境的能完成多重优化目标的网络编码方案。具体的研究方向包括编码优化算法的研究、编码数据传输保密性 和完整性研究、无线网络编码算法性能衡量与测试方法研究、结合网络编码的无线网络协议的研究等等,相关研究成果发表在globecom等知名国际会议和软 件学报、电子学报等国内一级刊物上,目前该项研究获得了国家自然科学基金的支持。


高速网络

针对原有的TCP传输控制协议在高速网络中严重吞吐量下降、带宽利用率低下、流量抖动频繁等问题,项目组对TCP传输控制协议的拥塞控制机制、瓶颈路由器缓存和路由器主动队列管理算法等进行了深入的研究,在传输控制协议方面我们进行了以下研究:

(1)针对高速网络中TCP协议传输效率低下的问题,提出了一种基于多种反馈机制的协同工作的拥塞控制协议—C3P。C3P通过源端检测RTT延时 信息和路由器反馈的1bit显式预测信息来判断网络拥塞状态,自适应的调节拥塞窗口,从而以一种较为简单的形式结合了网络中的丢包、延时以及显式反馈信息 动态调整C3P 源端的发送速率。

(2)为了解决现有传输控制协议在高速网络传输中稳定性和收敛性方面的不足,提出了一种基于路由器显式速率分配的拥塞控制机制—ARROW TCP。理论分析表明:ARROW TCP实现了网络的全局稳定和与链路带宽大小无关的指数收敛速度。同时,由于ARROW TCP能够单调收敛到公平速率,避免了带宽超调行为,实现了无排队延时、零瞬态丢包和零稳态丢包的理想拥塞控制性能。ARROW TCP协议中采用的链路“价格”机制,使得协议能够有效地工作在复杂多瓶颈链路网络拓扑环境下,实现了网络资源的max-min公平分配。

队列管理对传输控制协议的性能起到了至关重要的作用,因此对高速网络中主动队列管理算法展开了以下的研究:

(1)针对现有主动队列管理算法不能适应动态的网络流量环境的问题,提出了一种自适应的简单比例控制器AOPC。AOPC通过测量链路的分组丢失 率,并基于二阶系统最优化模型和自适应计算方法来实时调节控制器参数,适应瞬息万变的网络环境。AOPC在队列稳定性、响应性、延时和利用率等性能指标上 获得了大幅提升。

(2)针对无线传输出现的通信时延较大的问题,提出了一种用于大时滞网络拥塞控制的主动队列管理算法IMC-PID。IMC-PID采用内模控制技 术,设计了用于时滞补偿的PID控制器,达到消除网络时延对拥塞控制系统稳定性的负面影响。IMC-PID克服了已有AQM算法在大时延网络环境下队列震 荡不稳定而出现的链路利用率急剧下降的问题,在很大时延范围的网络环境中能够稳定队列长度到期望值附近,从而提高了链路利用率。


网络安全

由于网络应用越来越普及,信息化的社会已经呈现出越来越广阔的前景,可以肯定地说,在未来的社会中电子支付、电子银行、电子政务以及多方面的网络信 息服务将深入到人类生活的方方面面。同时,随之面临的信息安全问题也日益突出,非法访问、信息窃取、甚至信息犯罪等恶意行为导致信息的严重不安全。因此, 如何保证网络应用的安全、保护人们的个人隐私等网络安全问题已由原来的军事国防领域扩展到了整个社会,研究涉及网络安全应用的关键技术具有重要的理论意义 和应用价值。

本小组主要从事匿名通信,无线网络安全、web安全技术等方面的研究,完成了国家自然科学基金项目“匿名通信理论、方法与关键技术”以及“Web服 务器安全软件开发”等应用项目。在匿名通信方面,针对匿名通信理论与关键技术,研究匿名性能衡量标准、高性能的匿名机制、P2P匿名机制的可扩展性和激励 机制、无线网络匿名通信、匿名通信系统结构等等,相关研究成果得到了国内外研究人员的关注和认同,并发表在国际知名会议ICC、GLOBECOM和软件学 报等国内知名刊物上。在Web安全方面,针对Web文件保护技术和防注入攻击技术等展开研究,设计和实现相应的Web安全监测软件,获得了良好的社会效益 和经济效益。

1、新的网络模型和感知模型下,最优数据收集及最佳覆盖问题;

2、协作通信、网络编码等技术在无线传感器网络中的应用;

3、无线传感器网络跨层传输协议的研究;

4、多种攻击模型下,有效的虚假数据信息过滤及密钥分发机制的研究;

5、利用完全、部分、不精确或相对位置信息改善网络性能的研究;

6、完善测试平台,丰富协议组件。


无线传感器网络组

无线传感器网络有着丰富的应用场景,传统的应用包括环境监测、桥梁安全、财产保护、目标追踪等,随着技术的不断进步,无线传感器网络同时支持多应用并提供 更大的带宽成为可能,在这种意义上来说,除了仍然有较严苛能量和处理器能力限制外,它已经成为了一种无线多媒体网络。正是这些丰富应用场景提出了大量的开 放性问题,需要研究人员们逐步解决。

我们的研究主要围绕湖南省杰出青年基金项目《服务于铁路货车安全监测系统的无线传感器网络关键技术研究》进行,2009年7月结题,被评为优秀项 目。铁路货车安全监测网络是一种特殊的传感器网络,它有超多跳和直线等特点,这给体系结构和通信协议设计带来很大挑战。我们对网络中相关的一些基本问题进 行了研究,设计出了一系列超多跳直线网络的通信协议,并且采用IRIS通信模块搭建了测试平台对这些协议的性能进行了测试。本项目的完成为我们今后的研究 打下坚实的基础,并且还衍生了一些新的有意义的问题,我们将对这些问题进行重点研究:

1、新的网络模型和感知模型下,最优数据收集及最佳覆盖问题;

2、协作通信、网络编码等技术在无线传感器网络中的应用;

3、无线传感器网络跨层传输协议的研究;

4、多种攻击模型下,有效的虚假数据信息过滤及密钥分发机制的研究;

5、利用完全、部分、不精确或相对位置信息改善网络性能的研究;

6、完善测试平台,丰富协议组件。


延迟容忍网络组

在延迟容忍网络(DTN)中,由于节点预先安排的周期性运动、无周期性频繁的移动或者节点稀疏分布,造成网络经常处于分割的状态。DTN网络通常具有源节 点和目的节点之间经常不存在端到端的路径、数据传输延时比较长、节点的资源有限等特点,传统的网络技术在这种环境中不能有效的工作。

我们对DTN网络研究的主要工作是,当网络间歇性的连接或者网络连通性经常中断时,扩展现有的协议或者设计新的协议来增强网络的通信能力,主要包括:

(1)研究节点的行为和运动模式,利用可获得的网络状态,采取自学习与启发式算法来设计路由。

(2)如何权衡网络的性能与开销来进行路由设计。

(3)在网络全局信息不完整的情况下,提供有效的节点缓存管理策略优化网络的性能。

(4)基于社会网络的路由算法和相关理论的研究。

(5)DTN网络组播和广播路由算法和相关理论的研究。

这些研究将为灾难恢复、军事战争、野外跟踪、个人移动设备信息交换等特殊情况中网络的运行和性能优化提供理论基础,并极大增强未来无线网络通信在各种极限环境下的可用性。


网络软件开发

随着互联网的迅猛发展,TCP/IP协议已经不能满足各种各样的网络应用的高带宽低延时的性能要求。广域网逐渐成为性能瓶颈,面向网络应用的广域网优化加速已经成为一个热门的研究课题。

网络软件组主要从事网络协议优化、网络应用加速等研究以及相关软件开发,于2008初承接了深信服公司的Exchange邮件传输加速项目,于2009年 7月获得中南大学研究生创新项目基金支持。目前主要的研究课题为广域网加速技术的研究与实现。其中包括两个大的方面:网络协议优化和网络软件系统设计,致力于将理论研究成果转化为实际应用。

目前,网络协议优化研究主要涉及到基于传输控制协议优化和应用层协议优化的有线网络加速策略研究、基于跨层协议优化的无线网络加速策略研究。网络软件系统 设计主要包括支持数据的拦截、处理和转发,支持加速模块的动态加载的广域网加速网关平台的设计、基于并行TCP的网间加速网关的设计。主要发表了《广域网 加速技术研究综述》、《广域网中RPC应用加速网关设计与实现》、《并行TCP的研究及应用》等论文。




虚拟实验环境


随着计算机信息技术的不断发展,计算机应用已经渗透到了我们工作和生活的各个领域,极大的提高了工作效率并且令生活变得数字化和信息化。随着信息化 进程的不断深入,越来越多的院校开设了计算机课程。和传统课程教学相比较,计算机课程有着实践性极强的特点,学生要学习好这些课程不但要认真学习好理论基 础,还需要大量的实践练习。虚拟实验室应运而生。

1:C语言虚拟实验室

C语言课程的学习,只有真正动手编写大量的程序,才能真正掌握程序设计的思维和方法。在传统的程序语言的教学方式中,多数院校还是基本采用传统笔试 来做水平考核或以FTP,Email的方式来提交编程作业,然后老师需要对这些提交上来的代码一一审核、批阅,这一传统方式需要花费老师和学生很多精力和 时间,低效是显而易见的。

开发一个针对程序语言学习的Online Judge平台,能改进上述传统教学的一些弊端。通过本系统,学生可以自行提交代码,然后系统能对提交的代码进行编译,检查有无语法错误;能验证程序是否 能得到正确的结果,以及测算程序在时间和空间上的开销。在教师端,教师可对系统参数做出设置,限制学生提交的代码类型,限制时间、空间的开销。本系统的运 用,极大的提高了师生双方面效率,不但减轻教师在教学管理的负担,也给学生提供了一个自助的实践平台。

2:操作系统虚拟实验室

以Linux0.11版本内核为基础,深入剖析了一般操作系统各项功能的实现机制,如进程调度与通信、内存管理、文件系统等等,开发了一个操作系统源代码 级的教学实践平台。该系统采用Java语言实现,具有良好的平台无关性。依据Linux内核的体系结构及其实现的功能将Linux0.11内核源码划分为 一个个大小适宜、功能相对独立的小模块,模块之间的复杂关系通过图形的方式清晰的展示给系统用户。模块关系图按照Linux内核的体系结构分层显示,如内 存管理模块包含分页机制、内存分配、地址转换等功能相对独立的模块,这些小模块之间的依赖关系在内存管理下一级显示,最底层的模块图对应其实现的 Linux源代码。系统提供了一个良好的帮助用户学习操作系统理论知识与进行内核源码编程的工程环境,用户可以通过本系统方便有效的理解操作系统各项功能 的具体实现机制,还可以进一步对自己感兴趣的功能模块进行修改或编写替换算法,经过编译后,在虚拟机或模拟器上运行新内核,观察运行效果。系统实现了图形 化显示操作系统模块之间的复杂依赖关系、图文并茂地展示内核模块功能的实现机制等功能,为操作系统教学和内核开发人员提供了一个方便实用的学习实验平台。 该系统是从源代码的角度来解析操作系统的实现机制,对用户的能力要求较高,在今后的研究中,迫切需要开发一个可以图形化显示操作系统内部运行机制的虚拟实 验室,使用户不必经过源码学习就可以轻松直观地理解与掌握操作系统的各项功能。

3:计算机组成原理虚拟实验室

计算机组成原理虚拟实验平台是一个仿真计算机硬件实验的虚拟实验平台,它将虚拟集成电路芯片通过虚拟线路组成相关的实验,具有可视化、全交互、仿真程度高 等特点。其中每一个可视化的二维物体代表一个实验设备,用户通过鼠标的点击以及拖拽,完成选定设备、连线等简单操作,进而开展各种实验,观察实验的结果。 虚拟芯片是平台当中最小的实验单元,学生通过选择,连接芯片来搭建实验,通过观察芯片上数据的变化来理解实验。采用组件技术对其进行构建和封装,从而达到 虚拟芯片的可重用性,使得虚拟芯片的研究变得比较简单,易于扩充。并在此系统的基础上设计开发了CPU组装设计平台。该平台为国际上第一个将CPU组装实验予以软件实现,为学生提供了一个学习计算机组成原理和CPU基本原理的实验环境。

利用此平台,学习者可以先在CPU虚拟实验平台上单独选取组件来搭建CPU中的功能部件(如运算器、微控制器等)实验,并验证其功能,并在此基础上逐步开 展CPU实验,开发出CPU实验所需的芯片组件,使学习者能够自己设计搭建CPU实验,微程序控制器与内存组件在设计上要留有接口,使学习者能设计出自己 的微程序系统来替换系统原有的微程序系统,并能输入相应的机器指令来予以验证,充分调动学习者的主观能动性,满足学习者个性化的学习需求。

通过Internet向校内外学生提供了一个不受时空限制的虚拟实验平台。我们已经搭建了我们虚拟实验室系统的网站,并免费向国内外用户开放。无论校内还 是校外学生均可以通过Internet访问我们网站,来进行多门课程的实验,从而解决了实验场地和设备不足的问题,也为学生开展课外自选实验提供了一个很 好的平台。

《计算机组成原理》虚拟实验室系统已经应用到了中南大学计算机专业多个年级的实验教学中,为学生提供了一个进行创新性、研究性的实验平台。受到了老师和学 生的广泛好评,并获得2007年中南大学校级教改成果一等奖。同时值得一提的是,由于仿真实验效果良好,广州商学院等已正式引进计算机组成原理虚拟实验室 平台,建立学生虚拟实验室。

附:虚拟实验室平台以及以该平台为基础开发的虚拟实验室系统近年获得了如下奖项:

1、湖南省科学技术进步二等奖 (基于构件服务的虚拟实验平台)

2、湖南省高等教育省级教育成果三等奖 (信息类创新人才培养模式及综合实践教学体系的研究与改革)

3、中南大学高等教育校级教学成果一等奖? (软件工程类研究生工程管理与实践能力的培养)

4、中南大学校级实验技术成果一等奖 (基于Internet的数字通信原理虚拟实验的开发与应用)

5、中南大学校级实验技术成果二等奖 (基于Internet的数字图像处理虚拟实验的研究与开发

6、中南大学校级实验技术成果一等奖

4:数字图像处理虚拟实验室

数字图像处理虚拟实验平台自1991年,由中南大学虚拟实验室开始开发,经过不断的改进,已经成为一个成熟的虚拟实验平台。它对计算机数字图像处理 实验进行仿真,提供了一种不受时间、地点以及实验设备限制的虚拟实验平台。在这个实验平台上,数字图像处理中不同的处理图像方法,被封装为一个个可视化构 件;每一个可视化构件就代表了一个虚拟实验设备,这些构件就组成了基本的虚拟设备库。数字图形处理虚拟实验平台中,提供给用户图形化的实验环境。用户通过 鼠标的点击与拖拽,来选定不同的虚拟设备,平台会将选定的虚拟设备进行动态组装,以适应不同的实验需要,进而组合为完整的实验流程,最终完成实验。

虚拟的实验设备经过组件技术的构建和封装,具有很好的可重用性,并且用户依据指定的规则,可以利用自己熟悉的工具,比如Java,C++,MATLAB 等,定制自己的虚拟实验设备。这样以来,用户可以设计自己的数字图像处理虚拟设备,并验证其功能。充分的调动了用户的主观动能性,满足了用户个性化的学习 需求。

中南大学虚拟实验室通过Internet向校内外同学免费提供了这个平台。同学们可以通过我们的网站,访问数字图像处理虚拟实验平台,进行自己的个性化学习,节约学习时间,提高学习效率,让我们为你的进步保驾护航。