基于复杂网络的嵌入式互联网统计时间特征关键问题研究

摘要

近年来，随着互联网的迅猛发展，越来越多的嵌入式实时系统被接入到互联网，使得人们的感知与控制能力得到空前拓展。但是由于互联网的高复杂性与不确定性时延等因素，使得嵌入式系统在与互联网接入时无法确保系统的时间安全性。在实时系统中任何一个步骤都会有时间限制区间，一旦超限则会导致实时系统崩溃。面对当前庞大而复杂的互联网，与嵌入式系统的确定性时限要求，嵌入式系统与互联网的交互面临巨大挑战。
　　对于上述问题的解决主要有两种途径，一种是通过微观角度（路由协议再设计、拥塞控制策略设计、接入网关选择等方法）分析问题解决问题;另一种方法是通过宏观拓扑结构角度（Internet的度分布、聚集系数分布、介数分布等维度）来解析Internet的结构，获取相应的延迟特征，以指导嵌入式系统与Internet的接入。第一种角度往往针对某一个网络延迟层面，是实际Internet中导致时延不确定的因素有很多，例如数据包处理延迟、传输冲突延迟、路由器服务延迟等，这导致第一种研究角度对应的成果难以直接应用于实际。第二种角度是一个统计学角度，通过对海量Internet数据的分析，抽象出Internet的宏观拓扑结构复杂延迟特征，并依据该特征，设计相应的拓扑建模方法，为Internet实时性分析提供基础与指导。
　　本文首先利用CAIDA宏观拓扑测量项目的测量技术及其拓扑数据的获取方法，对数据进行探测合并预处理，为之后章节的分析工作提供了准确的数据支撑。其次，用核入口重整化方法粗粒度化网络，研究了Internet路由级拓扑结构的自相似分形特征。从度分布、度相关性以及聚集性等方面分析了Internet拓扑的自相似性;通过不同KC网络的度分布的幂律指数，累积邻居节点平均度值等度相关性特征的标度不变性和分形维数的计算定性定量的说明了路由级网络的部分与整体、部分与部分之间存在着自相似性。从而说明了Internet路由级拓扑具有分形特征，而网络拓扑分形复杂性对延迟产生影响，为本文延迟特征分析提供必要基础。
　　其次，采用CAIDAARK项目提供的海量数据样本对网络延迟的行为特征进行分析，发现网络延迟的传播行为特征呈现出双峰重尾分布。网络延迟传播行为特征分布随时间变化不大，有很强的自相似性，证明网络延迟受网络拓扑分形复杂性影响也具有分形特征。其次，从访问直径、网络延迟两端的实际地理距离L(km)和最大链路延迟三个侧面讨论可能影响网络延迟的因素，证明访问直径的行为分布接近于正态分布，网络延迟和访问直径没有关系。约有90％的路径最大链路延迟占网络延迟的比例达到1/3以上的瓶颈延迟。最大链路延迟是影响网络延迟的因素。同时对瓶颈延迟的演化进行分析，发现近五年内瓶颈延迟均值、网络延迟均值均呈现逐年增加的演化趋势及地理分布规律。
　　再次，本文在对Internet宏观拓扑结构复杂特性分析的基础之上，引入了k-核分解概念，对Internet宏观拓扑结构进行k-核分解。依据k-核分解的思想，设计了一种基于k-核延迟特征的建模方法——LM，通过大量实验对比分析了LM模型产生的拓扑结构复杂特性与Internet复杂特性的相似性，充分体现了Internet宏观拓扑的分形层次复杂性，从而得出LM模型的有效性与合理性。进一步介绍了LM模型与NS-2平台相结合的应用方法，为嵌入式互联网应用提供了测试平台与方法。
　　最后，考虑到支配延迟对网络的传播行为有较大影响，进一步研究了支配延迟的行为特征。解释支配延迟产生的原因以及影响支配延迟的因素，从而为嵌入式互联网应用提供依据。首先，比较了网络在不同访问时间区间上传播行为，发现访问时间相差较大的路径，其支配延迟对访问时间的比例相近，说明支配延迟对网络传播行为的影响与访问时间本身并没有必然联系，但是由于支配延迟本身在数值上相差较大，导致相近访问直径的路径其传播行为有着较大的差异，并直接表现为访问时间呈现出多峰分布特征。之后，讨论了AS自治域上的支配延迟行为特征。通过将IP级节点映射到AS自治域上，结果表明支配延迟更多地出现在AS自治域内部，并从AS自治域上的传播行为解释了支配延迟较少出现在AS自治域之间的原因。通过将产生支配延迟的IP节点对映射到实际地理位置，对支配延迟产生的主要原因进行了讨论，结果表明网络拓扑分形复杂性影响支配延迟的大小，进而给出了嵌入式设备接入互联网的交互条件。
　　本文从互联网的宏观拓扑结构着手分析了其延迟特性，所得出的结论对解决嵌入式系统与Internet接入时面临的不确定性延迟问题有着积极意义，并指导了嵌入式互联网今后的研究方向。

目录

声明

摘要

第1章 绪论

1．1 嵌入式互联网概述

1．1．1 嵌入式互联网概念

1．1．2 发展现状

1．1．3 体系结构

1．2 嵌入式互联网关键问题

1．2．1 研究重要性

1．2．2 面临关键问题

1．3 互联网宏观拓扑的延迟特征

1．3．1 宏观拓扑结构研究的重要性

1．3．2 宏观拓扑研究内容及方法

1．4 本文主要工作

1．5 本文组织结构

第2章 互联网宏观拓扑结构及分形特征

2．1 互联网拓扑分析基础

2．1．1 拓扑数据来源

2．1．2 拓扑测量技术

2．2 基本特征量定义

2．3 拓扑数据的修正处理

2．3．1 同名IP解析

2．3．2 解析结果

2．4 网络粗粒度化方法

2．4．1 算法描述

2．4．2 处理结果

2．5 路由级拓扑分形特征

2．5．1 度分布分析

2．5．2 度相关性分析

2．5．3 分形维数分析

2．6 本章小结

第3章 Internet延迟特征及复杂网络演化分析

3．1 Internet拓扑数据简介

3．1．1 Internet拓扑探测数据的来源

3．1．2 Internet拓扑延迟的研究方法

3．1．3 拓扑数据获取及初步处理

3．2 网络延迟的传播行为特征

3．2．1 同一周期不同节点网络延迟传播行为特征

3．2．2 同一节点不同时间的网络延迟传播行为演化分析

3．3 影响网络延迟因素

3．3．1 网络延迟和访问直径的关系

3．3．2 网络延迟和其端到端地理距离的关系

3．3．3 网络延迟和最大链路延迟的关系

3．4 瓶颈延迟特征参数的演化

3．4．1 瓶颈延迟基本特征量的演化

3．4．2 瓶颈延迟的ratio-hop和ratio-bot值的演化

3．5 瓶颈延迟在地理上的演化分析

3．5．1 网络延迟在地理上的演化特征

3．5．2 瓶颈延迟在地理上的演化特征

3．6 本章小结

第4章 基于复杂网络k-核延迟特征的建模

4．1 相关技术简介

4．1．1 k-核相关概念

4．1．2 Internet拓扑建模概述

4．2 层次模型相关性质的分析

4．2．1 相关定义及符号描述

4．2．2 节点分布

4．2．3 各层连接数的分布

4．3 基于k-核延迟特征的建模方法——LM

4．3．1 设计思想

4．3．2 算法描述与说明

4．4实验及分析

4．4．1 基本属性对比

4．4．2 度分布对比

4．4．3 核分布对比

4．4．4 度相关性对比

4．4．5 聚集性对比

4．4．6 富人俱乐部连通性对比

4．4．7 讨论

4．5 生成模型的可视化

4．6 嵌入式互联网仿真测试平台方法

4．6．1 相关实验平台

4．6．2 实验方法

4．7 本章小结

第5章 Internet支配延迟特征及对实时系统的影响

5．1 延迟数据处理与定义

5．1．1 延迟数据处理

5．1．2 支配延迟定义

5．1．3 支配延迟对访问时间的影响

5．2 AS自治域延迟特征分析

5．2．1 AS自治域选路策略

5．2．2 AS自治域上的链路延迟

5．2．3 支配延迟与AS自治域的关系

5．2．4 拓扑分形复杂性对支配延迟的影响

5．3 嵌入式设备接入Internet条件

5．4 本章小结

第6章 总结与展望

6．1 本文工作及贡献

6．2 不足与展望

参考文献

致谢

攻读博士期间发表的论著