摘要:为解决从多数据流挖掘演化事件这一难题,提出了一种多数据流上的谱聚类算法SCAM(spectral clustering algorithm of multi-streams),其相似矩阵基于耦合度构造,而耦合度衡量了两个数据流的动态相似性.提出了算法EEMA(evolutionary events mining algorithm),该算法基于聚类模型的演变挖掘多数据流的演化事件.定义了聚类模型凝聚度,用以衡量聚类的紧凑程度,并证明了凝聚度的上界.基于到上界的距离和规范化相似矩阵的特征间隙,定义了聚类模型质量,并作为EEMA的优化目标自动地确定聚簇数k.设计了O-EEMA作为EEMA的优化实现,其时间复杂度为O(cn²/2).在合成和真实数据集上的实验结果表明,EEMA和O-EEMA是有效的、可行的.

摘要:已有的稀疏编码模型采用误差的平方和作为信息保持的客观评价标准,但最近的研究表明,人眼视觉系统的主要功能是从视觉区域提取图像和视频中的结构化信息.引入结构相似度来衡量信息保持的程度,通过对改进的目标函数进行优化,获得与初级视皮层中具有局部性、朝向性和带通性的感受野相类似的基函数集.实验结果表明,改进后的稀疏编码模型更符合人眼视觉系统特性.

摘要:采用密度敏感距离作为数据相似性度量,并基于多智能体进化的思想提出了一种密度敏感的多智能体进化聚类(density sensitive based multi-agent evolutionary clustering,简称DSMAEC)算法.算法设计了一种基于连接的编码方式,通过解码过程可直接得到最终的聚类结果,无需事先确定聚类类别数,有效地克服了对领域知识的依赖.针对聚类问题,设计了3个有效的进化算子来模拟智能体间的竞争、合作和自学习行为,共同完成智能体的进化,最终达到对数据聚类的目的.分别对人工数据集、UCI数据集以及合成纹理图像进行仿真,实验结果表明,该算法不但可以自动确定聚类类别数,而且能够应付不同结构的数据,适应不同的聚类要求,具有较强的实用价值.

摘要:针对Web服务因缺少有效的组织和管理机制而产生的应用瓶颈问题,引入基于概念覆盖度函数的扩展概念格,通过构建基于输入和输出参数的Web服务集的扩展概念格模型,给出了Web服务间等价、替代和流关系的离线挖掘算法以及增量和减量的在线更新算法.在真实Web服务集上的测试结果表明,扩展概念格模型是Web服务集的一种有效的组织形式,可用于Web服务关系的自动挖掘和维护,从而为Web服务的选择、优化和组合提供智能支持.

摘要:大量无类别标签的数据具有对分类有用的信息,有效地利用这些信息来提高分类精确度,是半监督分类研究的主要内容.提出了一种基于流形距离的半监督判别分析(semi-supervised discriminant analysis based on manifold distance,简称SSDA)算法,通过定义的流形距离,能够选择位于流形上的数据点的同类近邻点、异类近邻点以及全局近邻点,并依据流形距离定义数据点与其各近邻点之间的相似度,利用这种相似度度量构造算法的目标函数.通过在ORL,YALE人脸数据库上的实验表明,与现有算法相比,数据集通过该算法降维后,能够使基于距离的识别算法具有更高的分类精确度.同时,为了解决非线性降维问题,提出了Kernel SSDA,同样通过实验验证了算法的有效性.

摘要:介绍了基于关系数据库的关键词查询问题的研究背景;阐述了解决该问题的两大类方法,即基于数据图的方法和基于模式图的方法,并详细介绍了各种方法的原理以及各自的优缺点;最后展望了未来的研究方向.

摘要:很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.

摘要:What-If分析能够提供比传统的OLAP(on-line analysis processing)分析更加有意义的决策支持信息.基于历史数据的应用场景假设分析需要更加有效的what-if数据视图生成机制的支持.在传统的delta表合并算法的基础上,提出了基于内存记录指针的deltaMap算法来提高what-if数据视图的合并性能.根据OLAP分析的应用特点,提出了pre-merge算法来处理支持分布式计算的聚集运算.根据不同的假设更新类型,对查询重写算法和△cube算法作了详细的性能测试并进行了全面的性能分析对比,在此基础上提出了what-if分析的代价模型,以应用场景模式、假设更新率、假设更新复杂度、查询结果集的基数作为参数,有效地描述系统what-if查询处理策略,为what-if分析的解决方案提供了一个可行的框架结构.

摘要:软子空间聚类是高维数据分析的一种重要手段.现有算法通常需要用户事先设置一些全局的关键参数,且没有考虑子空间的优化.提出了一个新的软子空间聚类优化目标函数,在最小化子空间簇类的簇内紧凑度的同时,最大化每个簇类所在的投影子空间.通过推导得到一种新的局部特征加权方式,以此为基础提出一种自适应的k-means型软子空间聚类算法.该算法在聚类过程中根据数据集及其划分的信息,动态地计算最优的算法参数.在实际应用和合成数据集上的实验结果表明,该算法大幅度提高了聚类精度和聚类结果的稳定性.

摘要:全球路由表的高速膨胀,使互联网路由系统的可扩展性面临着严峻的挑战.为了缩减路由表,很多研究提出了新的路由解决方案.在介绍了互联网路由系统现状之后,从较高层次上将存在的解决方案分为短期方案、路由架构和可扩展路由算法3部分.着重介绍了路由算法和路由架构这两类工作,对经典的可扩展路由算法和路由架构进行了深入的分析和比较.最后讨论了有待解决的关键问题和未来的研究方向.

摘要:机会路由通过充分利用无线信道的广播特性,可以大大提高无线多跳网络的性能.从阐述机会路由的基本思想开始,介绍了机会路由协议的主要特点、适用环境和影响机会路由性能的重要因素.在此基础上,对重要机会路由协议进行了综述,讨论不同协议的工作机制及其优缺点.最后,探讨了机会路由的一些未来发展方向,以期为这一领域的发展提供一些有意义的借鉴.

摘要:作为一种新型的端到端存储转发网络体系结构,容迟与容断网络(delay and disruption tolerant network)具有间歇连接、频繁割裂、时延极高、非对称的数据速率、较高的误码率、异构互连等特点,传统的Internet、移动Ad Hoc网络和传感网的路由协议难以有效应用在容迟与容断网络中,容迟与容断网络路由面临新的挑战.在简要介绍了容迟与容断网络的基本特性和路由协议设计挑战之后,提出了路由协议评估指标.然后从单播路由、组播路由和选播路由3个方面介绍了容迟与容断网络路由协议的研究进展,最后对主要路由协议进行了综合比较,并指出了未来的研究方向.

摘要:由于人们对网络流量规律的认识还不够深入,大型高速网络流量的异常检测仍然是目前测量领域研究的一个难点问题.通过对网络流量结构和流量信息结构的研究发现,在一定范围内,正常网络流量的IP、端口等具有重尾分布和自相似特性等较为稳定的流量结构,这种结构对应的信息熵值较为稳定.异常流量和抽样流量的信息熵值以正常流量信息熵值为中心波动,构成以IP、端口和活跃IP数量为维度的空间信息结构.据此对流量进行建模,提出了基于流量信息结构的支持向量机(support vector machine,简称SVM)的二值分类算法,其核心是将流量异常检测转化为基于SVM的分类决策问题.实验结果表明,该算法具有很高的检测效率,还初步验证了该算法的抽样检测能力.因此,将该算法应用到大型高速骨干网络具有实际意义.

摘要:在如今的互联网中,网络管理员要想及时地发现前缀劫持事件非常困难.考虑到互联网域间路由系统中存在的自治特性,提出了在多个自治系统之间协作监测前缀的思想,并由此设计了一个实时检测前缀劫持的新方法——Co-Monitor机制.在Co-Monitor中,每个参与者与其他参与者交换自定义的前缀-源自治系统映射信息,同时,利用所学到的前缀-源自治系统映射信息实时地监测本地BGP(border gateway protocol)路由更新.一旦某个参与者发现了不一致就立刻通知相关的参与者,从而可帮助参与者及时、有效地发现前缀劫持.给出了Co-Monitor机制的详细设计,评估了该机制的检测能力,并讨论了几个相关的问题.实验结果表明,只需精心选择60个参与者,就可确保Co-Monitor系统检测前缀劫持的漏检率和误检率都为0%.

摘要:快速而准确地提取蠕虫特征对于有效防御多态蠕虫的传播至关重要,但是目前的特征产生方法在噪音干扰下无法产生正确的蠕虫特征.提出基于彩色编码的特征自动提取算法CCSF(color coding signature finding)来解决有噪音干扰情况下的多态蠕虫特征提取问题.CCSF算法将可疑池中的n条序列分成m组,然后运用彩色编码对每组序列进行特征提取.通过对每组提取出来的特征集合进行过滤筛选,最终产生正确的蠕虫特征.采用多类蠕虫对CCSF算法进行测试,并与其他蠕虫特征提取方法进行比较,结果表明,CCSF算法能够在有噪音干扰的条件下准确地提取出多态蠕虫的特征,该特征不包含碎片,易于应用到IDS(intrusion detection system)中对多态蠕虫进行检测.

摘要:故障定位问题理论上已经证明为NP-Hard问题.为了降低计算复杂度,以概率加权的二分图作为故障传播模型,提出了一种基于贝叶斯疑似度的启发式故障定位算法(Bayesian suspected degree fault localization algorithm,简称BSD).引入贝叶斯疑似度,对所有故障仅计算一遍;同时采用增量覆盖方式,使算法具有较低的计算复杂度O(|F|×|S|).仿真实验结果表明,BSD算法具有较高的故障检测率和较低的故障误检率,即使在部分告警无法观察、告警丢失和虚假等情况下,算法依然具有较高的故障检测率.BSD算法具有多项式计算复杂度,可以满足大规模通信网故障定位的要求.

摘要:提高文件的查找定位效率是无结构的P2P网络一个重要的研究内容.泛洪法和随机查找法虽然简单和易于实现,但是前者会较大地增加网络负载,而且搜索的深度不能太大;后者虽然可以降低网络负载和适当增加搜索深度,但却以牺牲搜索的广度和增加响应时间为代价.提出一个无结构P2P内容分发网络的内容定位和查找请求路由方案.它利用社会网络的基本原理,通过模拟社会网络的特征,发挥节点的能动性,可以在有限的搜索深度和广度内快速查找定位文件.模拟实验结果表明,在相同的硬件环境支持下,P2P网络文件平均定位时间可以缩短50%以上.

摘要:利用冗余复制技术,BQS(Byzantine quorum system)系统在异步信道上提供了能容忍f台服务器拜占庭失效的存储服务.COCA系统和CODEX系统设计了一种结合门限签名方案和BQS系统的服务器协议,完成了TSS-BQS(threshold signature schemes-BQS)系统.与普通BQS系统相比,具有更易于支持Proactive Recovery,简化客户端密钥管理和客户端通信的优点.基于相同的系统模型和信道假设,提出了一种新的服务器协议,满足TSS-BQS系统的安全要求;而且与已有协议相比,该协议只需更少的通信轮数,在读/写并发情况下执行效果 更优.

摘要:数据包公平抽样通过牺牲长流的包抽样率以换取更高的短流包抽样率,因而比均匀随机包抽样更能保证数据流之间的公平性.现有的公平抽样算法SGS(sketch guided sampling)存在空间效率低、短流估计误差大的问题.提出了一种空间高效的数据包公平抽样算法SEFS(space-efficient fair sampling).SEFS算法的新颖之处在于采用多解析度抽样统计器对数据流流量作近似估计,各个统计器由d-left哈希表实现.采用在OC-48和OC-192骨干网采集的真实流量数据,在数据流流量测量以及长流检测的应用背景下,对SEFS算法和SGS算法的性能进行了比较.实验结果表明,与SGS算法相比,SEFS算法在空间复杂度降低65%的前提下,仍具有更高的估计精度.特别是对于占网络数据流绝大多数的短流而言,SEFS算法估计精度高的优势更为明显.

摘要:网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.

摘要:解决ad hoc网络中隐藏节点问题、暴露节点问题的最终目的是减少节点间的冲突,提高网络空间复用率,从而提高网络吞吐量.现有MAC协议在解决隐藏节点问题时着重于彻底消除网络中的隐藏节点,忽略了网络空间复用率,即使能够彻底解决隐藏节点问题,也不能有效提高网络吞吐量.同样,现有协议在解决暴露节点问题时着重于如何允许暴露节点并行发送数据,忽略了暴露节点接收数据的问题,也影响了网络空间复用率.提出了一种高效的MAC协议e-MAC,协议采用两种方法提高网络空间复用率:首先,协议中接收节点根据接收到发送节点的信号强度动态调整忙音发射功率,使忙音恰好覆盖所有的隐藏节点,在彻底解决隐藏节点问题的同时,提高网络空间复用率;其次,隐藏节点接收到RTS消息后,通过判断RTS消息信号强度与信道中干涉信号的强度之比来决定是否接收数据,允许满足信噪比要求的接收节点接收数据,进一步提高网络空间复用率.仿真结果验证了协议的有效性,在任意拓扑结构下,e-MAC协议的平均吞吐量比DUCHA(dual channel access)协议高87%.

摘要:在移动自组网络中,节点的移动或是无线连接的中断会引起频繁的网络分割.因此,访问节点并获取相应的数据是相当困难的.通过理论和统计分析得到特定运动模型对应的网络分割模式,建立了网络分割模式与数据复制有效性之间的联系,推导出了理想复制方法在特定网络环境下能够获得的数据可用性的上限,也指出纯随机复制方法可提高数据可用性.基于上述分析,提出了一种新的数据复制方法RICMAN(replication in intermittently connected mobile ad hoc networks)来提高断续性连接移动自组网络的数据可用性.该方法将所需数据以副本的形式复制到一系列拓扑结构相对稳定和资源充足的特定节点上,为处于同一分区的节点提供数据服务.副本的分布和更新基于半概率性数据分发协议实现.此协议能够识别可能的跨越多个网络分区的运动节点,由这些节点传播数据及其更新,从而在断续性连接网络中最大化数据传输.为了保持副本的一致性,该方法使用一种弱一致性模型——最终一致性模型,以确保所有的更新最终在有限的延迟内传送到所有的副本处.仿真结果显示,RICMAN方法能够以较小的开销获取较高的数据可用性,经过优化后,数据可用性仅比理想上限低10%～15%.

摘要:为了在移动ad hoc网络中有效利用无线信道资源,提出一种基于ID的信道预约(ID-based channel reservation,简称IDBCR)多址接入协议.该协议在公共信道上发送Request-To-Send/Clear-To-Send(RTS/CTS)分组实现握手,采用基于节点ID的信道选择方案选择无冲突的业务信道传输数据分组,目的节点成功接收完数据分组后在另一个公共信道上回复acknowledgment(ACK)分组,有效避免了暴露终端问题.最后,仿真实现了IDBCR协议,并与CAM-MAC(cooperative asynchronous multi-channel MAC)多信道协议比较.结果表明,在总信道利用率、平均信道利用率和平均分组延迟性能上,IDBCR多址接入协议明显优于CAM-MAC协议.