面向大规模网络测量的数据恢复算法：基于关联学习的张量填充

网络应用,如网络状态跟踪、服务等级协议保障和网络故障定位等,依赖于完整准确的吞吐量测量数据.由于测量代价大,网络监控系统通常难以获得全网吞吐量测量数据.稀疏网络测量技术基于采样的方式降低测量代价,通过张量填充等算法挖掘数据内部的时空相关性,从部分网络测量数据恢复缺失数据.然而,现有研究仅考虑了单个性能指标,忽略了多个指标之间的关联信息,导致恢复精度受限且整体测量代价依然很大.本文提出了一个面向大规模网络测量的数据恢复算法——基于关联学习的张量填充（Association Learning based Tensor Completion,ALTC）.为了捕获网络性能指标之间的复杂关系,设计了一个关联学习模型,使用低测量开销的往返时延推测高测量开销的吞吐量,降低网络测量代价.在此基础上设计了一个张量填充模型,同时学习吞吐量测量数据内部的时空相关性和来自往返时延的外部辅助关联信息,最终以更高的恢复精度获取全网吞吐量数据.实验表明,在相同的吞吐量测量代价下,本文所提算法的恢复误差比目前主流方法的恢复误差降低了13%,达到了更好的恢复效果.     

基于博弈的协作路由算法

协作虚拟多输入多输出（VMIMO）传输是一种有效的无线传输性能优化技术。将物理层协作VMIMO技术和网络层路由选择技术相结合,设计跨层VMIMO路由选择方案可以利用VMIMO的分集增益,显著地降低网络传输能耗。如何设计VMIMO协作路由协议抵抗无线网络的自私节点和欺骗行为,保证高数据转发率和低传输能耗成为路由设计中的重大挑战。为了提高自私网络的VMIMO路由性能,提出了一种基于重复路由博弈的VMIMO协作路由算法。该算法将网络划分成多个Group、Group间使用VMIMO传输数据。将Group间路由选择过程建模为重复路由博弈过程。为了提高数据转发的成功率,提出适用度函数评估节点参与数据分组转发的信誉。以此为基础,提出基于适用度的路由选择子算法和路由转发子算法。理论证明所提重复路由博弈可达到帕累托最优。仿真实验结果表明本算法可以促进自私节点相互合作,可获得较高的数据转发率,较好地减少数据传输时延以及能量消耗。     

基于分簇P2P的多跳无线mesh网络资源检索与分发算法

针对多跳无线mesh网络中拓扑结构和不同类型节点的特征,将多跳无线mesh网络建模成分簇P2P结构.为了降低资源发布的开销,在进行资源共享设计时,利用布鲁姆过滤器作为资源表示和消息在网络中传输.以布鲁姆过滤器为基础,提出了一种基于资源密度敏感的多跳无线 mesh 网络资源检索和分发算法,将移动客户端的资源下载请求转发到拥有资源副本最多的P2P分簇,利用该分簇的多个资源副本备份提供资源下载服务,最大化降低节点移动性产生的资源下载中断.仿真结果表明所提出的资源检索和分发算法能有效提升资源的下载性能.     

联合多维布鲁姆过滤器查询算法

分析了现有多维布鲁姆过滤器查询算法(MDBF)工作原理,提出了一种改进的两步表示和查询的联合多维布鲁姆过滤器(CMDBF)查询算法.CMDBF新增一个用于表示元素整体的联合布鲁姆过滤器CBF,CMDBF中元素表示和查找分两步进行.将MDBF的各属性的表示和查询作为第一步,第二步联合元素所有属性域,利用CBF完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,CMDBF能够支持多维集合元素的简洁表示和查询,相比MDBF查询误判率降低明显.     

布鲁姆过滤器代数运算探讨

 本文探讨布鲁姆过滤器的代数运算和集合查询的关系,定义布鲁姆过滤器的"并","交","异或","补","差"代数运算,从理论和实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集,交集,异或集,补集,差集的元素查询关系.理论分析和实验结果表明,布鲁姆过滤器的"并","交"运算能够支持集合并集交集的元素查询,这一结论可以简化利用布鲁姆过滤器进行的系统设计.