延迟容忍的移动传感网络路由算法研究

摘要

随着无线传感网络研究的不断深入，越来越多的应用要求网络中的节点部分甚至全部具有移动性。例如，用于野生动物监控和追踪的无线传感网络、水下无线传感网络等等。在移动传感网络中，由于节点的移动使得网络拓扑动态变化，网络中没有稳定的端到端传输路径。而传统的有线网络或无线Adhoc网络路由算法都是基于网络中具有稳定的传输路径这一假设前提的，在移动传感网络中则不能有效工作。因此，如何在网络拓扑动态变化的情况下，实现有效地端到端数据传输是移动传感网络中首要解决的关键问题之一，具有重要的研究意义。 另一方面，近年来在无线网络领域出现了延迟容忍网络的新兴概念，泛指那些没有稳定端到端传输路径的无线网络。其应用涵盖了太空网络、乡村网络、移动传感网络、Adhoc网络等等。目前，在延迟容忍网络路由算法方面已取得了许多具有代表性的研究成果。由于移动传感网络正是一种典型的延迟容忍网络，可以在延迟容忍网络体系结构下来研究移动传感网络的路由问题。因此，本文在国家863项目和自然科学基金项目的支持下，开展了延迟容忍的移动传感网络路由算法研究。 具体的研究内容及创新点如下： 1)本文首先考虑了一种半确定移动模型下的延迟容忍移动传感网络路由问题。在这一网络模型中，假设节点根据一些先验知识或历史纪录已归纳出每个节点在单位时间内访问各个网络区域的概率，在此基础上考虑以延迟最小为优化目标的单副本报文传输路由问题，并提出了一个基于区域访问概率的延迟容忍移动传感网络路由算法PROAREA。 PROAREA算法的主要创新之处在于：已有的基于概率的延迟容忍网络路由算法认为节点的相遇概率越高则越可能尽快地将报文传输给对方，并利用这一思想定性地指导路由选择，而PROAREA算法则利用节点间的相遇概率，直接推导出了节点间的期望传输延迟，并以此定量地指导路由选择。实验结果表明，PROAREA算法比已有的算法在选择转发节点时更具有针对性，能够提高传输成功率并降低传输延迟。 2)本文还进一步地考虑了节点传输容量受限的延迟容忍移动传感网络路由问题。假设网络中节点的传输容量有限，当报文传输的最优传输路径出现流量饱和时，应该等待再传输还是策略性地选择其它路径进行传输，采用什么样的策略才能使得总的传输延迟最小。本文则针对这一优化问题进行了研究，并提出了PROAREA-LC算法。PROAREA-LC算法的主要创新之处在于：该算法将容量受限的延迟容忍移动传感网络路由问题模型化为一个费用流问题，并利用最小费用最大流算法成功地求解了该问题。实验结果表明，与相关算法相比，PROAREA-LC算法能够进一步地降低端到端数据传输延迟。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.1.1移动传感网络概述

1.1.2延迟容忍网络概述

1.2论文的选题意义

1.3论文的主要贡献和结构

第二章延迟容忍网络路由算法

2.1概述

2.2 DTN路由算法的性能评价标准

2.3常用的网络模型

2.4 DTN网络中的路由算法

2.4.1基于复制策略的路由算法

2.4.2基于转发策略的路由算法

2.5本章小结

第三章基于区域访问概率的延迟容忍传感网络路由算法

3.1概述

3.2基于各个区域单元(Cell)的移动模型介绍

3.3路由算法设计

3.3.1几个重要定义

3.3.2基于区域概率的算法

3.3.3算法性能分析

3.4实验模拟

3.4.1传输成功率

3.4.2平均传输延迟

3.4.3计算负担比较

3.5本章小结

第四章容量受限的延迟容忍移动传感网络路由算法

4.1概述

4.2问题描述

4.3算法描述

4.3.1构建初始费用流图

4.3.2构建虚拟多边费用流图

4.3.3计算满足流量需求的路径

4.3.4按路径转发报文

4.4模拟实现

4.4.1节点发包频率对平均传输延迟的影响

4.4.2链路容量对平均传输延迟的影响

4.5本章小结

第五章结束语

5.1本文总结

5.2下一步的工作

参考文献

致谢

在读期间发表的学术论文与完成的项目