无线传感器网络中的自适应2-不相交多路径路由算法

摘要

随着微电子技术、计算技术以及无线通信技术的进步，低功耗多功能的传感器得到了快速的发展，而且无线传感器网络已经被广泛地应用。传感器网络中的路由问题是无线传感器网络研究和应用的关键性基础问题，直接影响着整个网络的性能。
　　颜色树（红树和蓝树），是为了解决多路径路由问题而提出的2-不相交多路径路由算法，可用来在无线传感器网络中，为任何一个传感器节点路由数据到sink构建两条满足点不相交约束条件的路径，这样可以提高网络的健壮性和吞吐量。本文提出了一种基于层次的2-不相交多路径路由算法，该算法可以只利用本地信息创建颜色树多路径路由结构，而且可以减小构建过程中的通信负载，从而在一定程度上节省节点通信的能量消耗。在大规模网络中部署多个基站（sink）节点不但可以有效地减少传感器节点和sink之间的平均路径长度从而延长网络生命周期，而且可以应对某个sink节点失效的情形。为了在多基站传感器网络环境下建立颜色树多路径路由结构，我们将算法扩展到了多基站环境下，即为每个传感器节点构建两条路径分别路由到两个不同的sink且两路径满足点不相交约束条件。
　　无线传感器网络是自组织网络，新的节点可能随时会加入到网络中，而且在复杂恶劣的应用环境中传感器节点失效情形是经常发生的，这就要求路由算法具有较强的自适应能力与扩展性。所以，我们在后面的章节中给出了上文算法的自适应策略，在节点失效和有新节点加入网络的情形下，可以高效地维护并重建颜色树路由结构。
　　通过理论和实验分析，本文提出的算法不但能够满足O(N)的线性时间复杂性，而且和传统的颜色树构建算法相比，可以减少构建过程中的通信负载50％，在节点失效情况下路由结构的维护代价减小60%左右，在有节点加入网络情况下颜色树结构的维护代价将减小77.2%，最坏情况下所构建的颜色树在平均路径长度这个指标上也不会比传统的算法差。

目录

无线传感器网络中的自适应2-不相交多路径路由算法

ADAPTIVE 2-DISJOINT MULTIPATH ROUTING ALGORITHMS IN WIRELESS SENSOR NETWORKS

摘要

Abstract

第1章 绪论

1.1 课题背景及研究意义

1.2 国内外的研究现状

1.3 主要研究工作

1.4 论文的结构安排

第2章 预备知识

2.1 无线传感器网络中的数据可靠传输方法

2.2 颜色树路由算法

2.3 传感器间歇性失效问题

2.4 本章小结

第3章基于分层思想的颜色树构造算法

3.1 引言

3.2 基础知识

3.3 分布式颜色树构造算法

3.4 算法的理论分析与证明

3.5 实验评价

3.6 本章小结

第4章适用于网络拓扑动态变化的自适应路由策略

4.1 引言

4.2 RCT算法描述及工作原理

4.3 NA算法描述及工作原理

4.4 多sink网络环境下的自适应策略

4.5 自适应策略的正确性分析和维护代价分析

4.6 实验评价

4.7 本章小结

结论

参考文献

攻读学位期间发表的学术论文

哈尔滨工业大学硕士学位论文原创性说明

哈尔滨工业大学硕士学位论文使用授权书

致 谢