vc传感器网络瓶颈节点识别算法及其实现毕业论文

目       录
1 绪论 1
1.1 课题背景及目的 1
1.2 国内外研究状况 1
1.3 课题研究方法 2
1.4 论文构成及研究内容 2
2 瓶颈节点 3
2.1 瓶颈节点概述 3
2.2 概念定义 3
2.2.1定义信宿 3
2.2.2定义多跳 3
2.2.3定义网络寿命 4
2.2.4定义瓶颈节点 4
2.3 准瓶颈节点概念 5
2.4 准瓶颈节点算法 6
3 二跳准瓶颈节点概念和算法 8
3.1 准瓶颈节点算法的缺陷分析 8
3.2 二跳准瓶颈节点的概念 9
3.3 二跳准瓶颈算法的提出 10
3.4 二跳准瓶颈节点的时间复杂度分析 11
4 算法性能比较 13
4.1 模拟环境介绍 13
4.2 改进后算法性能对比 15
4.3 能量消耗速度对比 17
5 结论 18
致谢 18
参考文献 18
附录 18
附录A 一跳准节点算法实现 18
附录B 二跳准瓶颈节点算法的实现 18
附录C TopDisc三色算法实现 18 本文来自think58 [资料来源：www.THINK58.com]

2 瓶颈节点
2.1 瓶颈节点概述
无线传感器网络是近代新兴的技术，因此很多概念和协议都没有成型，大多数的协议和算法还处在学术研究阶段，而没有在应用于实际。由于是不成熟的技术，在无线传感器网络中还需要不断的发掘新的概念，新的理论，新的算法。“瓶颈节点”这个术语原本只是用在计算机网络internet中[6,7]，用于表示在大网络带宽突然遇到窄带时，造成数据的拥塞，丢包现象。如今这个术语又被用在无线传感器网络中，但性质也随之而发生了变化，在无线传感器网络中，由于传感器节点使用的是不可再生和不可永久供应能量的电池作为电源，当部分节点的能量消耗怠尽时，网络的寿命也宣告结束，因此网络中最宝贵的资源已经不是带宽资源，而是能量资源。因此在无线传感器网络中，“瓶颈节点”代表的是由于节点所处的特殊位置使得其能量消耗速度大与其它节点的节点。
无线传感器网络条件下瓶颈节点的研究已有一些初步的成果，如Sink节点附近环境区域能量模型的建立[8,9]，准瓶颈概念[1]的提出等等。通过这些初步成果，给在无线传感器网络条件下“瓶颈节点”的研究开拓的一个新的方向，本课题就是在研究前人的成果上，分析“瓶颈节点”的特点并提出新的概念，新的算法。
2.2 概念定义

2.2.1 定义信宿
在前面的论述中，我们已经提到到了信宿这个概念，既Sink节点。现给出信宿的定义，信宿是接受信息的实体，她可以是一个传感器节点，手持PDA或地面基站。信宿的作用是接受来自网络的数据，将采集的数据永久存储下来或转发到另外的一个大型的网络，本文中所用的Sink节点是地面的基站，它有持续的能量供应，因此不会因能量消耗殆尽而死亡。
2.2.2 定义多跳
无线网络的特性和传感器功率的限制，使得传感器只能在有限的距离内通讯，因此信源和信宿之间不能简单的发射信号进行直接通讯，特别是在覆盖区域很广，或区域间有很多障碍物时，信源和信宿的直接通讯几乎是不可能的。
在实际应用中，常常使用中继站的方式进行连接，从信源发出的分组通过若干个中继到达信宿，我们称采用这种连接方式通讯的网络为多跳网络[2]，由于传感器节点本身就可以担当中继节点，因此在WSN（wireless sensor network 下同）中并不需要额外的设备担当中继器，所以多跳网络特别适用于WSN。
2.2.3 定义网络寿命
WSN网络的寿命是指在一定初始能量储备的情况下，网络持续工作的时间，由于WSN网络使用的场景不同，网络寿命的定义也随之不同，一般的有以下一些定义[2]：
1) 第一个节点失效的时间。网络中出现第一个节点停止工作之前网络工作的时间。

[来源：http://www.think58.com]

2) 网络半衰期。网络中一半的节点能量耗尽的时间。
3) 分裂时间。网络被分割成几个不同的连通分支的时间，这个时间可以早到网络中第一个节点失效的时间（这个节点处于关键位置），也可能由于网络很健壮，大多数节点失效后才开始分裂。
在本篇论文中，我们使用第三种定义。
2.2.4 定义瓶颈节点
由于部署的原因，一般存在一些连接数个区域的孤立节点，这些孤立节点独立转发区域间的数据而没有邻居节点的支援，使得这些节点的工作时间明显的大于处于其它位置的节点，又因为网络的是寿命是网络被分裂的时间，而这些孤立的节点的死亡最可能使得网络被割裂。
因此，“瓶颈节点”可以定义为[1]：在一个随机部署的无线传感器网络中，那些由于它们的死亡而造成整个网络被割裂成两个或多个不相连的区域，并且由于收集数据的基站和监测目标不在同一个区域中，从而造成整个网络生存期结束的最少数目的节点。
2.3 准瓶颈节点概念
在2.1.3中，我们已经陈述了瓶颈节点的定义，也初步论述了瓶颈节点对网络寿命的重大影响，因此，寻找到这些瓶颈节点，进而可以采取一些措施减少瓶颈节点所带来的影响。
寻找这些瓶颈节点实际上是寻找无线传感器网络拓扑的一个点割集，因此可以采用图论中寻找点割集[3]的算法寻找这些瓶颈节点。然而这个看起来完美的方案并不可行，因为在实际的无线传感器网络中，每个节点的能量，计算能力，存储能力都是非常有限的，由单个节点保存整个WSN的拓扑信息，并使用集中式算法计算出点割集并不可行。因此，我们必须找到一种分布式算法，使得单个节点在有限的空间和时间内判断出自己是否处在关键位置上，既是否为瓶颈节点。

内容来自think58

由于寻找瓶颈节点是个代价很高的过程，于是[1] 根据“瓶颈节点”的特点，提出一种“准瓶颈节点”的概念，并证明这类“准瓶颈节点”中大部分的节点对网络的影响类似瓶颈节点对网络的影响。
“准瓶颈节点”的定义：一个节点为准瓶颈节点，当且仅当其所有邻居被分为不相交的集合。
经[1]证明，单个节点成为“准瓶颈节点”的概率如图2.2所示。由图2.2可以看出即使当节点有10个邻居时，该节点仍有很大的概率成为准瓶颈节点。因此，找到这些准瓶颈节点，并提出相应的解决方案消除这些准瓶颈节点所带来的影响具有重要的意义。

本文来自think58

[资料来源：www.THINK58.com]

[资料来源：www.THINK58.com]