Ad Hoc网络模型下的边不相交路径选择算法

摘要

本文主要研究的是在点和边都不可靠的AdHoc网络模型下，使用边不相交路选择算法来提高网络通信的可靠性问题。 在典型的AdHoc网络中，网络拓扑结构频繁的变化会引起传输路径变化。这种路径变化对信息传输的可靠性产生很大的影响，而且网络中节点本身也存在可靠性问题。为了更好的研究基于网络可靠性路由算法对网络性能的影响。本文研究点和边都不可靠的网络模型下基于可靠性优化的搜索边不相交路启发式算法。首先介绍AdHoc网络的来源、发展、应用及重要的一些路由协议，尤其是DPSP协议。对网络的拓扑结构做了总结，给出了本文所使用的点和边都不可靠的网络模型；并且对于网络可靠性的计算给出了多种方法，针对本文的边不相交路算法给出了相应的计算可靠性的方法。然后给出了边不相交路选择算法的设计思想和算法的过程。本算法包括两个子算法，第一个子算法是使用最短路径算法经过迭代找到网络中的多条可靠路径。第二个子算法则是对第一个子算法找到的路径集进行改进，使路径集的可靠性得到进一步的提高。此算法的时间复杂性是多项式时间的。此算法找到的传输路径是多条不相交路径的集合，因为两点间的多条不相交路径对于AdHoc网络是非常重要的，它可以平衡网络负载、减少路由开销。本文还给出了具体的实例，使用边不相交路选择算法得到的网络可靠性有了很大的提高。同时与其他的算法作了相应的比较，证明了该算法在提高路径网路可靠性方面具有优势。 本文主要的工作是在新模型即点和边都不可靠的模型下使用边不相交路径选择算法，提高了网络通信的可靠性；以及对此算法进行了改进，使它更简洁。

目录

文摘

英文文摘

大连海事大学学位论文原创性声明和使用授权说明

第1章 绪论

1.1 Ad Hoc网络

1.1.1 Ad Hoc网络来源及发展

1.1.2Ad Hoc网络的特征

1.1.3 Ad Hoc网络的应用

1.2Ad Hoc网络的路由协议

1.2.1几种重要的Ad Hoc路由协议

1.2.2单路由协议与多路由协议

1.2.3一种新的路由协议(DPSP)

1.3本文的主要工作和篇章结构

第2章网络模型及可靠性的计算

2.1网络可靠性的来源及发展

2.2网络模型

2.2.1网络拓扑结构

2.2.2 Ad Hoc网络可靠性的模型

2.3网络可靠性的计算

2.3.1完全状态枚举法[21]

2.3.2容斥原理算法[1.26-32]

2.3.3不交和算法

2.3.4因子分解算法

2.3.5可靠度近似算法

2.4边不相交的Ad Hoc网络可靠性的计算

2.5本章小节

第3章边不相交路径选择算法(DPSP)

3.1算法的基本设计思想

3.2边不相交路选择算法的设计

3.2.1第一个子算法

3.2.2第二个子算法

3.2.3主算法：边不相交路径选择算法(DPSP)

3.3算法的时间复杂性分析

3.4本章小结

第4章实例与仿真

4.1具体的例子

4.2与其他算法的比较

4.3本章小结

第5章结束语

参考文献

附 录

攻读学位期间公开发表论文

致谢

研究生履历