无线传感网中瓶颈节点的局部探测及其关键性的量化

吴院，马永强

（西南交通大学 信息科学与技术学院，成都610031）

吴院（硕士研究生），研究方向为计算机网络与信息系统；马永强（教授），研究方向为网络与信息系统、基于视频图像的监测技术、嵌入式系统及其应用。

引 言

无线传感网是由大量能量资源有限的自组织传感器节点密集部署而成［1］。所有节点的能量消耗并不是统一的，那些处在关键位置的节点会消耗更多的能量，这些关键节点的移除会导致网络的断裂［2］。为了实现节点的低成本，通常节点上都不会带有GPS定位装置，这样节点就不知道其在网络中的准确位置，也不能用定位方法去识别网络中的瓶颈节点。本文提出了一种通过关键性来探测其是否为瓶颈节点的局部方法。

瓶颈节点示例如图1所示。由于随机部署的原因，连接两个或多个区域的瓶颈节点必须承担两个区域之间大量数据包的转发工作，因为在它的周围没有其他节点可以分担他的负载。因此，其能量消耗速度比其他普通节点更快，这些节点的移除或死亡，会造成整个网络的割裂［3］。

本文的目的就是要研究一种局部算法，用来识别瓶颈节点以及它们的关键性等级。节点的关键性等级会影响它们在网络中数据包转发工作的分配。通常，在基于节点的剩余能量确定其关键性时，假设对所有的节点来说，移除任意一个节点造成整个网络被割裂的概率是相等的。

1 节点能耗假设

图2和图3分别表示存在关键节点与不存在关键节点的传感网中所有节点的能耗分布［4］。图2是不理想的节点能耗直方图，可明显知道网络中确实存在瓶颈节点，一些节点因邻居节点少而承担少量的数据转发工作，而其他拥有较多邻居节点的节点会经常用来转发数据，以至能量几乎消耗殆尽，本文的目的就是要找出此类节点。图3是理想的节点能耗直方图。尽管两者的总能耗量是相同的，但图3中节点的能耗显然要比图2的均衡，这样它的网络生存期也相应会长些。

图1 瓶颈节点示例

图2 不理想的节点能耗直方图

图3 理想的节点能耗直方图

研究中，假设所有节点都是静止的，网络拓扑不发生变化，没有基础设施支持，且任何两个位于对方通信半径内的节点都能互发消息。

2 局部探测算法

这里将所有的节点分为两部分：一部分为根节点，它们在网络初始阶段以泛洪方式传送消息；其他所有节点负责转发各根节点的独特消息。所有选出来的根节点必须保证网络的大部分区域能被监控到。这些根节点有一个重要的特征：相比于其他普通节点，它们拥有较少数量的邻居节点。因为这样它们就很可能位于网络的边界处。通过邻居节点的数量，就能选出最合适的根节点，也就能知道网络的边界节点。所以在节点部署完成后，通过节点的通信半径来计算它们的邻居节点数。

网络拓扑中关键节点［5］的探测分两步进行。

（1）寻找根节点

每个节点中都有一个可复位的定时器。如果超时，节点的等级标识值就会成为无穷大，没有任何泛洪数据包［6］，成为一个孤立的节点。同样，每个节点也有一个发送定时器，每个发送周期过后，它都会被重置。在每个发送定时器周期里，泛洪消息传送都会发生。发送定时器的重要性不及可复位定时器。

节点部署完后，每个节点都会发送一个PⅠNG消息，在其传输半径内的邻居节点都会收到它。接收到消息的节点都会回复一个ACK消息，并且每个节点都会把它的邻居节点信息保存下来［7］。邻居节点的数量将成为判断节点是否能成为根节点的依据。在一个节点分布密集的传感网中，这些根节点很显然会位于网络拓扑的边界处。

有一点必须要注意的是，被选出的任何两个根节点不能位于彼此的通信半径之内。这样是为了避免造成对瓶颈节点错误的探测。

每个节点将其邻居节点的数量发送给它的每一个邻居节点，这样每个节点就能知道它自己和每个邻居节点的邻居节点数。只有一个邻居节点的节点将被判别为根节点。被选出来的根节点会发送泛洪数据包给其邻居节点，然后每个邻居节点会依次向更远处转发收到的泛洪消息［8］。如果所有的节点都有多个邻居，这样将没有根节点。一旦超时，并且没有收到泛洪消息，每个节点会重置它的发送定时器，并且增大用来作为根节点判断依据的邻居节点数这一阈值。

值得注意的是，为了能更好地估算出邻居节点数，节点的通信半径须取其最大可能值。这样选出来的根节点位于网络边界的几率最大。

（2）探测关键节点

假设整个网络拓扑中有n个根节点，这些等级为0的节点开始发送泛洪消息，收到从0等级节点发送来的泛洪请求的邻居节点会将它们自身等级标记为1，并向远处传播泛洪消息。其后依次进行。n个根节点就会在网络中传播n种不同的泛洪消息。每个节点会继续转发收到的泛洪消息，只要这个消息能使当前节点等级更高，否则，就丢弃这个消息［9］。

如果节点能同时收到两个不同根节点发送来的消息，这个节点就是关键节点。如果这个关键节点或其子节点又收到另一根节点发送来的消息，那么它将比先前的关键节点更关键，因为这个节点连接着3个根节点。依此类推，节点的关键度取决于其所收到的不同泛洪消息的数量。这样，在进行实际的数据传输之前，每个节点就能知道它的关键度。对于这一步，需选取最适宜的通信半径来节省节点能量，并且不能有孤立节点存在。

3 性能分析与仿真

本节通过Matlab仿真说明网络中瓶颈节点所占的比例，并将其归类，最高类的瓶颈节点最关键。

仿真平台采用Matlab。仿真时，假设160个节点随机分布在一块1 000m×1 000m的区域内，每个节点的传输半径为185m，初始等级为无穷大，并用ⅠD号标识。选择出的根节点分别位于方形区域的各个角落。

在任一拓扑网络［10］中，感知数据的传输大多数时间都会穿越整个网络，这样可利于各节点关键度的探测，并通过采取合适的路由策略来延长网络的生存期。每个根节点的关键度等级设为0，它们在网络中广播带ⅠD编号的泛洪消息，其收到消息的邻居节点的等级将被指派为1。当节点能收到两个不同消息时，它就属于第1类瓶颈节点，并且其所有子节点也将是瓶颈节点，因为它们必须通过父节点才能与各根节点相连。如果任何一个第1类瓶颈节点又收到来自第3个根节点的消息，那么它和它所有的子节点将属于第2类瓶颈节点。这里的子节点是指所有与其相连而未收到任何根节点消息的节点。如果有n个根节点，则最多有（n－1）类瓶颈节点，第（n－1）类最关键，因为它们与n个根节点都存在通路，可能承担整个网络的数据转发工作。

表1列出了任一拓扑网络中各类瓶颈节点的百分比。此仿真中，选取了4个根节点，所以总共有3类瓶颈节点，其中第3类最关键。

表1 瓶颈节点的百分比

图4中黑色圆点表示随机部署在网络中的传感器节点。图5表示根节点的选取，其中用矩形圈住的圆点为根节点。在图6中，被矩形圈住的星状点为第1类瓶颈节点，被三角形圈住的星状点为第2类瓶颈节点，被圆形圈住的星状点为最关键的第3类瓶颈节点。

图4 传感器节点的部署

图5 选取根节点

图6 瓶颈节点的探测

4 结 论

本文提出了一种传感网中瓶颈节点的局部探测算法，并对其关键性进行量化。理论分析与仿真实验表明，此算法对网络中关键节点检测的准确度较高，在每个节点进行实际的数据传输之前，就能知道它的关键度，从而减少关键节点的能量消耗，延长网络的生存期，提高整个网络的连通性和覆盖率［11］，节省网络维护的成本。

［1］Ⅰ Akyildiz，W Su，Y Sankarasubramaniam，et al.A Survey on Sensor Networks［J］.ⅠEEE Communications Magazine，2002，40（8）：102－114.

［2］J S Hartmut Ritter，Rolf Winter.A Partition Detection System for Mobile Ad－hoc networks［C］／／Sensor and Ad Hoc Communications and Networks（ⅠEEE－SECON），2004：489 497.

［3］Tian Le，Xie Dongliang，Han Bing，et al.Study on bottleneck nodes in wireless sensor networks［J］.Journal of Software，2006，17（4）：830－837.

［4］C Schurgers，M B Srivastava.Energy Efficient Routing in Wireless Sensor Networks［C］／／Military Communications Conference（ⅠEEE－MⅠLCOM），2001：357－361.

［5］Milenko Jorgic，Ⅰvan Stojmenovic.Localized Algorithms for Detection of Critical Nodes and Links for Connectivity in Ad Hoc Networks［C］／／20th Ⅰnternational Conference on Advanced Ⅰnformation Networking and Applications Volume 2（AⅠNA＇06），2006：336－340.

［6］张少军.无线传感器网络技术及应用［M］.北京：中国电力出版社，2010.

［7］李磊，李凤荣，黄河清.无线传感器网络局部瓶颈节点的分布式检测算法［J］.西南交通大学学报，2011（3）.

［8］马震.关于无线传感器网络节能的若干关键问题研究［D］.北京：北京交通大学，2009.

［9］Li Jiandong，Tian Ye，Sheng Min，et al.Partition detection for large scale ad hoc networks［J］.Journal of Communications，2008，29（9）：54－61.

［10］Gou Haosong，Yoo Younghwan.Distributed Bottleneck Node Detection in Wireless Sensor Network［C］／／10thⅠEEE Ⅰnternational Conference on Computer and Ⅰnformation Technology，2010.

［11］孙利民，李建中，等.无线传感器网络［M］.北京：清华大学出版社，2005.