ICMN中路由算法及其性能的研究

摘要

ICMN(Intermittently Connected Mobile Network)泛指端节点间的链路连接时断时续的网络。随着自组织概念的渗入,ICMN主要涉及具有自主组网能力的无线网络。这些网络中,节点间的无线信道干扰、节点的分组传输对部分无线媒介的独占性使用、节点的有效生命期、节点的移动等因素,都会导致ICMN节点间及边界网络间链路的通断性变化显著。
　　 本文以“提高ICMN网络的路由效率、预测已建立的多跳路由的存活时间以及设计网络吞吐量最大化的链路调度算法”为研究目标,主要关注ICMN网络中多分组副本的路由算法、端到端连接路径的性能、分组传输独占性使用无线媒介的调度算法,也即干扰模型的建立等。
　　 在详细分析现有的ICMN路由算法与协议的基础上,本文提出了一种高效的ICMN网络路由算法,该算法根据节点间的迁移可测度建立逐跳的端到端路由,回避了普通的基于流行病毒散播原理的多分组泛洪策略,改进了基于本地最优可达信息进行单分组中转的路由策略；同时,该算法结合组合收益理论,对待选的多分组中继路由策略进行组合与评判,并从中求出可行解；它在保持较高的端到端分组到达率的同时,能使整个ICMN网络内的分组副本数目(即网络开销)得到有效控制。
　　 ICMN网络多跳路由的连接通路一旦建立,端到端连接通路的可用时间与可用性将体现建立于当前通路之上的端到端路由存活时间。本文使用布朗运动移动模型描述节点的移动规律,从二维拓扑平面上单跳无线链路的可用性入手,分析多跳中继路由的路径可用性及期望可用时间。仿真实验证明,本文建立的路径可用性模型能动态地体现节点间的链路连接状况,较为准确地评测多跳路由端到端连接路径的稳定性。它为ICMN网络提供了一个较好的量度,可作为ICMN协议设计的辅助工具。
　　 在ICMN网络中,干扰模型的建模,以及节点发送分组时对无线媒介占用的调度算法可被看作ICMN网络路由的基础设施,它是影响网络性能的关键所在。本文针对ICMN网络的特点,对节点分布相对固定的网格拓扑结构和由于节点移动而产生的随机拓扑结构进行建模,分析了网络流量、链路长度、无线信号衰减对最优协议干扰模型的影响,给出了两类干扰模型实例化过程中链路可靠性和网络吞吐量间的权衡关系。针对最优干扰模型的选择问题,本文分析了协议干扰模型和物理干扰模型性能差异的主要因为,并提出了PRK干扰模型,该模型更加适合于分布式协议的设计,它既拥有物理干扰模型的高可靠性,又拥有协议干扰模型的本地性。
　　 通过理论证明、实际试验床的部署与测试、仿真实验的进一步验证,本文对PRK模型和基于SINR干扰模型的调度算法进行了比较。实验表明,当以链路可靠性为优化约束目标时,基于PRK模型的调度能获得近似于基于SINR调度的最高网络吞吐量(在所有研究的场景中,准确率至少可达到95％)。

目录

文摘

英文文摘

论文插图索引

论文表格索引

论文缩略语索引

第一章 绪论

1.1 研究背景

1.2 研究目标和研究思路

1.3 研究内容和研究方法

1.4 论文的主要贡献

1.5 论文的组织结构

第二章 ICMN网络路由算法的设计

2.1 引言

2.2 路由算法的相关研究

2.2.1 RBR类路由算法

2.2.2 CBR类路由算法

2.3 基于迁移可测度的路由算法

2.3.1 迁移可测度及其组合概念

2.3.2 单指数的引入

2.3.3 仿真实验

2.4 本章小结

第三章 ICMN中多跳路由的路径可用性

3.1 引言

3.2 移动模型

3.3.1 实体移动模型

3.3.2 群组移动模型

3.3.2 混合移动模型

3.3 端到端连接路径的可用性

3.3.1 单跳链路的可用性

3.3.2 多跳路由的路径可用性

3.3.3 仿真实验与验证

3.4 本章小结

第四章 ICMN干扰模型的比对与实例化:PRK VS.SINR

4.1 引言

4.2 预备知识

4.3 RATIO-K干扰模型的实例化

4.3.1 ratio- K 模型下的网络性能

4.3.2 数值分析

4.3.3 PRK模型

4.4 PRK模型的进一步讨论

4.4.1 PRK模型中的吞吐量丢失

4.4.2 数值分析

4.5 基于PRK和SINR模型的调度算法在传感器试验床中的验证

4.5.1 实验设定及部署

4.5.2 调度算法

4.5.3 实验结果

4.6 仿真实验

4.6.1 有限TelosB传感器网络中的仿真

4.6.2 UWB网络中的仿真

4.7 与主流研究成果的综合比较

4.8 本章小结

第五章 结束语

5.1 论文工作总结

5.2 进一步的研究工作

参考文献

附录

附录 A:网格拓扑中基于RATIO-K模型调度的干扰分析

附录 B:网络拓扑中最大空间可重用性(MAXIMUM-SPACIAL-REUSE)的流量模式证明

致谢

作者在攻读博士学位期间发表的学术论文

作者在攻读博士学位期间参加的科研项目