传感器网络瓶颈节点识别算法及其实现

摘  要

无线传感器网络中的“瓶颈节点”是指那些由于随机部署的原因而不得不成为连接两个或多个区域的孤立的节点。由于这些节点处于特殊的位置，区域间传送数据都必须经过这些节点，以致其寿命大大小于其它的节点，一旦这些节点死亡，网络将被割裂成不连通的分支，造成网络不能正常工作，网络寿命的终结，因此研究这类“瓶颈节点”有十分重要的意义。由于传感器节点计算和存储能力有限，“瓶颈节点”很难计算出来。于是[1]中提出一种新的概念“准瓶颈节点”，并使用分布式算法寻找到这些节点。
经过本文分析，这个寻找“准瓶颈节点”算法并非是优化的，算法执行的结果包含相当数量的非瓶颈节点，这类节点并不是连接两个或多个区域的孤立节点。本文将分析这类非瓶颈节点的特点，并将其称为“伪瓶颈节点”，在此基础上，分析“准瓶颈节点”算法的缺陷，随后本文将根据这些特点提出“二跳准瓶颈节点”定义，新的定义将消除“伪瓶颈节点”的影响。然后根据新定义提出与之相对应的算法用于寻找这些“二跳准瓶颈节点”，并且证明该算法在时间复杂度不超过 的情况下找到的节点更加关键和优化。本次毕业设计还将实现一个简单的模拟器，用于对两种算法的性能做比较，并测量能量消耗速度，最后得出结论：在无线传感器网络中二跳准瓶颈节点具有最快的能量消耗速度。 内容来自think58 [资料来源：http://think58.com]
2.2.4 定义瓶颈节点
由于部署的原因，一般存在一些连接数个区域的孤立节点，这些孤立节点独立转发区域间的数据而没有邻居节点的支援，使得这些节点的工作时间明显的大于处于其它位置的节点，又因为网络的是寿命是网络被分裂的时间，而这些孤立的节点的死亡最可能使得网络被割裂。
因此，“瓶颈节点”可以定义为[1]：在一个随机部署的无线传感器网络中，那些由于它们的死亡而造成整个网络被割裂成两个或多个不相连的区域，并且由于收集数据的基站和监测目标不在同一个区域中，从而造成整个网络生存期结束的最少数目的节点。
2.4 准瓶颈节点算法
准瓶颈节点的分布式算法[1]分为三个阶段：
1) 邻居发现阶段：当网络部署完毕后，每个节点通过发送“HELLO”探测包来通知获得邻居信息；
2) 连接信息交换阶段：当节点获得邻居信息后，它和自己的每个邻居交换连接信息；
3) 自判断阶段：获得邻居节点的连接信息后，每个节点现在知道自己一跳距离内的拓扑情况，这是运行下面的算法来判断自己是否为“准瓶颈节点”
Put all neighbors into set ;
Choose a neighbor randomly, remove it from set , and put it into set ;
For neighbor i in 
Begin think58 [资料来源：www.THINK58.com]
For neighbor j in 
Begin
If i is j’s neighbor, then put i into set ; Remove f from set ;
Else nothing happens;
End
End
If(set  is empty)then
I am not a “quasi-Bottleneck Node”;
Else
I am a “quasi—Bottleneck Node”.
设节点的邻居节点数为n，则该算法执行的时间复杂度为 。
在无线传感器网络中，大多数路由协议和分簇协议需要每个节点知道自己邻的信息，因此算法的第一和第二阶段所需要发送的“HELLO”探测包可以在路由和分簇时随带发送出去，而不单独占用额外的发送时间。这样执行算法的能量消耗主要集中在第三阶段的计算上，由于计算的能量消耗远远小于发送数据的能量消耗，因此算法不会给网络带来太多额外的负担。

内容来自think58 [版权所有：http://think58.com]

3.2 二跳准瓶颈节点的概念
相对于之前所述的准瓶颈节点，新的概念称为二跳准瓶颈节点。其定义为：一个节点为二跳准瓶颈节点，当且仅当其邻居被分割成不交的节点集，且这些不相交的节点集的邻居集合也不相交。
现证明二跳准瓶颈节点的定义可以满足准瓶颈节点的定义并且不包含伪瓶颈节点。要证明这个结论，只需二跳准瓶颈节点的不具备有伪瓶颈节点的第二特征，即只要证明在边长为4的圈上，任何的节点都不可能成为二跳准瓶颈节点。
think58.com [版权所有：http://think58.com]