基于介数中心性重要节点的能量均衡机制*

2017-10-16耿鹏，柳艳

火力与指挥控制 2017年9期

关键词：介数瓶颈生命周期

耿鹏，柳艳

（南京工程学院，南京 211167）

基于介数中心性重要节点的能量均衡机制*

耿鹏，柳艳

（南京工程学院，南京 211167）

针对无线传感器网络中瓶颈节点和准瓶颈节点对网络影响的特例性问题，将重要节点的概念推广到对节点介数的研究，提出了基于介数中心性重要节点的能量均衡机制。该机制将介数值大于网络平均介数值的节点判定为重要节点，并利用重要节点的邻居节点建立缓冲机制来减少其数据的转发次数，在牺牲较少数据传输延时的情况下节省了介数中心性重要节点的能量消耗。仿真实验表明该机制能够较好地均衡无线传感器网络中的节点能耗，提高了网络生命周期。

无线传感器网络，瓶颈节点，介数中心性，生命周期

Abstract：In wireless sensor networks，the problem of the influence of the bottleneck node and the quasi bottleneck node on the network is a special case.The concept of important nodes to the study of the betweenness centrality of nodes is extended.An energy balance mechanism based on betweenness centrality important nodes is proposed.In this mechanism，we determine the node is important node which the value of betweenness centrality is more than the average value of the network.Then a buffer mechanism is established on neighbor nodes of important nodes which can reduce data forwarding times.The mechanism saves the energy consumption of important nodes in the case of less data transmission delay.Simulation results show that the proposed mechanism can well balance the energy consumption of nodes in wireless sensor networks，and improve the network lifetime.

Key words：wireless sensor networks，bottleneck node，betweenness centrality，lifetime

0 引言

无线传感器网络［1］（WSN，Wireless Sensor Networks）通常应用在一些特殊环境之中，如军事、环境监测、地质勘探和气候预测等领域。在这些环境下进行节点部署具有随机性、不可移动性、较大冗余性和能量有限性等特点［2］，当网络中某个节点能量耗尽时，进行能量补充是很困难的［3］。在现实网络中，总是存在一些负荷较大的重要节点，例如网关节点，当此类节点出现异常时，对整个网络的影响是非常大的。对于可进行能量补充的网络中重要节点的研究主要集中在如何避免信息拥塞和提高吞吐量上；对于常常无法进行能量补充的无线传感器网络，应该将研究重点放在如何减少重要节点的能耗，以尽量延长网络生命周期上［4-5］。

设计一定的拓扑控制机制和路由算法，使得网络节点能耗更加均衡、网络生命周期更长，是目前研究无线传感器网络的重要方向之一［6-9］。然而当前的研究更多的是将网络节点统一看待，较少考虑不同位置节点在网络中的重要性也不同的现象。本文通过分析瓶颈节点和准瓶颈节点对网络影响的特例性问题，基于介数中心性［10］（BC，Betweenness Centrality）的概念分析了无线传感器网络重要节点的一般性特征，并对重要节点进行了能量均衡处理，使得网络整体性能加以提高。

1 瓶颈节点与准瓶颈节点

自文献［11］提出无线传感器网络中的瓶颈节点和准瓶颈节点概念开始，陆续出现了考虑网络中节点承担数据流角色的文章。文献［12］通过网络仿真证实了瓶颈节点的定义；文献［13］提出了一种分布式瀑布型移动方案，通过移动一定数量的普通节点到瓶颈节点处以减轻其通信负荷；文献［14］从准瓶颈节点的概念出发，提出了基于连通关系的聚类划分方法，并利用多路径的路由方法减轻了瓶颈节点和准瓶颈节点的负荷；文献［15］将对瓶颈节点的研究推广到对瓶颈区域的研究，提出了一种让瓶颈区域节点采用网络编码的优化策略，减少了瓶颈区域节点的数据包转发次数。

瓶颈节点定义为：在一个随机部署的无线传感器网络中，那些由于它们的死亡而造成整个网络被割裂成两个或多个不相连的区域，并且由于收集数据的基站和监测目标不在同一个区域中，从而造成整个网络生存期结束的最少数目的节点。如图1中的节点1～节点3所示，此3个节点的死亡会将整个网络分割成2个互不连通的独立区域，造成网络生命周期结束，将这3个节点的集合称为网络中的瓶颈节点。很显然，图1中瓶颈节点的共同特点是：其邻居节点集合可以划分成两个或两个以上的互不相交的子集，且子集中的任意节点不属于其他子集中节点的邻居节点，这便是对准瓶颈节点的描述。文献［11-14］对无线传感器网络中的准瓶颈节点进行能量均衡处理，以提高网络的生命周期。

图1 瓶颈节点示意图

由于瓶颈节点本身的特殊性，决定了网络中此种节点数量是十分有限的，与其对应的优化方案对网络性能的影响也是局部的。无线传感器网络中能量消耗较大的节点并不局限于瓶颈节点，因此，有必要将瓶颈节点的概念进行推广，分析网络中承担通信较多的重要节点的一般特征。

2 介数中心性重要节点

准瓶颈节点的定义是按照图的概念加以描述的，能量均衡处理时考虑的路由机制是最短路径算法，即信息总是按照源节点与目标节点之间的最少跳数进行传输，而介数中心性则考虑的是那些承担较多流量的节点。介数的概念最早是由Freeman在研究社会网络的过程中提出的［10］，文献［16］在描述复杂网络的重要节点过程中对之进行了较为详细的描述。介数在复杂网络和无线传感器网络中的应用研究仍为重要方向之一，文献［17］给出了复杂网络中介数中心性和平均最短路径长度的整合近似算法；文献［18］提出了一种基于最短路径介数及节点中心接近度的重要节点发现算法，通过最短路径介数的方法确定全网内的重要节点，利用中心接近度分析重要节点的重要性；文献［19］提出了一种基于节点介数的拥塞感知路由算法；文献［20］基于网络结构熵，结合无线传感器网络自身特性，给出了介数熵测度模型，用以衡量网络的抗毁性。

2.1 介数中心性定义

图2 介数中心性描述

考虑图2所示的情况，节点H的邻居无法被划分成两个互不相交的子集，它不是准瓶颈节点。但在最短路径算法条件下，相对其他节点而言，节点H所承担的通信量是最大的，也需要对其进行能量均衡处理。用经过某节点的最短路径数目来刻画此节点重要性的指标就叫作介数中心性，简称介数（BC）。

可以将按图进行描述的准瓶颈节点推广到按通信量进行描述的介数中心性重要节点。显然，图1中的节点1～节点3既为准瓶颈节点又为介数中心性重要节点。无线传感器网络的介数中心性重要节点包含了准瓶颈节点。

无线传感器网络节点i的介数定义为：

其中，gst为节点s到节点t的最短路径数目，为节点s到节点t的最短路径中经过节点i的数目。显然，介数的定义刻画了网络中某个节点对按照最短路径传输信息的控制能力。介数越高的节点其重要性也越大，去除这些节点后对网络传输的影响也越大。

2.2 介数计算步骤

无线传感器网络节点对被探测区域进行数据采集，然后通过多跳方式传输到汇聚节点（Sink），在考虑Sink节点唯一，采用平面路由机制的情况下，网络中所有普通节点信息传输的目的节点是确定的，即式（1）中的节点t为Sink节点。下面描述节点介数的计算方法。

步骤1：随机部署一定数目节点，包括Sink节点在内的所有节点通过发送“Hello”信息获知邻居节点信息；

步骤2：用矩阵的行数表示节点编号，列数表示邻居节点的编号，若两个节点互为邻居，则矩阵对应元素为1，否则为0，这样便形成了邻接矩阵（Adjacency Matrix）；

步骤3：Sink节点在邻接矩阵中查找自己的邻居节点，各个邻居节点再查找自己的邻居节点（排除前期已查找出的节点），依次下去，直到邻接矩阵查找完毕。最终形成以Sink节点为根的树状图；

步骤4：每个普通节点根据步骤3所形成的树状图来维护自身到Sink节点的最短路径信息，再根据式（1）计算节点介数。

下面进行仿真实例说明，在200*200M的区域内，随机撒下50个节点，每个节点的通信半径为40m，Sink节点部署在区域中心，即可形成如图3所示连接状况，其中节点50为Sink节点，节点0-49为普通节点。根据邻接矩阵获得图3中以Sink节点为根的树状图。根据普通节点到Sink节点的最少跳数将节点分类成第k跳节点集合。由于gst中的节点t一定（Sink节点），到达Sink节点的最短路径数目一定，因此，判断某一k跳节点的介数相对大小，只需统计与之存在路径的k跳以上节点数目之和即可。如节点1、节点2的相对介数值为8和5。尽管节点2位于第1跳，节点1位于第2跳，但判断节点1比节点2更重要，因此，并不一定越靠近Sink节点，其能量消耗得越快。

图3 随机部署网络图

3 介数中心性重要节点的处理

可将无线传感器网络的平均相对介数值作为评价标准，所有相对介数值大于平均相对介数值的节点可被看作介数中心性重要节点。网络中的节点可划分为：Sink节点、介数中心性重要节点和普通节点3类。

3.1 介数中心性重要节点能量均衡

网络中某节点为介数中心性重要节点，意味着经此节点的最短路径数相对较多，若不采取任何措施，此类节点能量消耗也是最快的，且对其他节点的影响也较为广泛。在不考虑节点计算能耗的条件下，无线传感器网络节点能耗主要包含三大部分：发送信息产生的能耗、接收信息产生的能耗和感知信息产生的能耗。由于网络中所有节点均需要感知信息并发送出去，且能耗一致，所以介数中心性重要节点和普通节点的能耗区别在于接收来自其他节点的信息并发送出去（转发）的次数。减少介数中心性重要节点对信息转发的次数，是网络能量均衡的有效办法。一种方案是移动另一节点到重要节点处作为支援节点；另一种方案是重要节点的邻居节点将信息暂存在缓冲区中进行聚集，缓冲区满后再转发给重要节点。对于部署在特殊环境下的无线传感器网络而言，节点的移动往往较为困难，第2种方案是可行的。

假设网络路由按照最短路径算法进行，每个节点均可计算自身的相对介数值，通过与平均相对介数值的比较即可判定自身是否为重要节点，并可将此信息发送给邻居节点。当邻居节点需要发送信息给重要节点时，会采用缓冲并聚集的方法来减少重要节点的转发次数。此方案在牺牲较少数据传输延时的情况下，延长了网络生命周期。

3.2 仿真分析

仿真基于Java平台，作如下假设：节点随机部署，Sink节点能量无限，每个节点的发射功率一定，节点一旦撒下，其位置固定，不可移动。节点发送1 bit数据所消耗的能量为：；接收1 bit数据所消耗的能量为：。其中r为节点通信半径，Eamp为发送放大器的消耗能量，其他仿真参数如表1所示。部署完毕的初始状态如图4所示。以与Sink节点相连的活动节点数目小于90%视为网络生命周期的结束，可仿真研究采用判断介数中心性重要节点并进行能量均衡时网络生命周期的改善情况。

表1 仿真参数设置

图4 节点部署初始状态

图5 活动节点数随时间变化

将节点缓冲区大小设置为数据包长的5倍，可以得到如图5所示的仿真结果。可以看出，在没有利用缓冲机制的情况下，网络运行到1 000 s之后与Sink节点存在通信的节点数少于90%。在利用缓存机制来减少介数中心性重要节点转发次数之后，网络运行到1 200 s才会使得与Sink节点存在通信的节点数少于90%，网络生命周期提高了20%。另外，采用发现介数中心性重要节点并进行能量均衡机制时，活动节点数量的减少速度明显更加缓慢。

4 结论

在最短路径传输协议下，无线传感器网络中能量消耗最快的节点并不一定是距离Sink节点最近的节点。瓶颈节点与准瓶颈节点虽然能量消耗较大，但此类节点仅代表一种特殊情况，其概念不具备一般性。本文利用复杂网络理论中的介数中心性理论，指出了网络中节点之所以能量消耗较大，本质原因在于其转发数据的次数较多。因此，提出了基于介数中心性重要节点的能量均衡机制，该机制将介数值大于网络平均介数值的节点判定为重要节点，并利用重要节点的邻居节点建立缓冲机制来减少其数据的转发次数，节省了介数中心性重要节点的能量消耗。仿真表明，利用该机制可将网络生命周期提高约20%。

［1］YICK J，MUKHERJEE B，GHOSAL D.Wireless sensor network survey ［J］.Journal of Computer Networks，2008，52（12）：2292-2330.

［2］顾德.无线传感器网络拓扑边界与瓶颈辨识［D］.杭州：浙江大学，2012.

［3］GOLDSMITH A J，WICHER S W.Design challenges for energy-constrained ad hoc wireless networks ［J］.IEEE Wireless Communications Magazine，2002，9（4），8-27.

［4］CARDEI M，WU J.Energy-efficient coverage problems in wireless ad-hoc sensor networks ［J］.Computer Communications，2006（29）：413-420.

［5］HEFEEDA M，AHMADI H.Energy-efficient protocol for deterministic and probabilistic coverage in sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21（5）：579-593.

［6］ZHU C，ZHENG C，SHU L.A survey on coverage and connectivity issues in wireless sensor networks［J］.Journal of Network and Computer Applications（Impact Factor：2.23），2012，35（2）：619-632.

［7］QURESHI H K，RIZVI S.Evaluation and improvement of CDS-based topology control for wireless sensor networks［J］.Wireless Netw，2013（19）：31-46.

［8］FIAZ M，YOUSAF R，HANFI M.Adding the Reliability onTree Based Topology Construction Algorithms for Wireless Sensor Networks ［J］.Wireless Pers Commun，2014，74：989-1004.

［9］RAMALAKSHMI RAMAR，RADHAKRISHNAN SHANMUGASUNDARAM.Connected k-Coverage Topology Control for Area Monitoring in Wireless Sensor Networks［J］.Wireless Pers Commun，2015，84：1051-1067.

［10］LC Freeman.A Set of Measures of Centrality Based on Betweenness［J］.Sociometry，1977，40（1）：35-41.

［11］TIAN L，XIE D L，ZHANG L.Quasi-Bottleneck Nodes：a potential threat to the lifetime of wireless sensor networks［C］//Proceeding of APWeb 2006 International Workshops：XRA，IWSN，MEGA，and ICSE.Harhin，China，2006，241-248.

［12］罗自强，李德毅.无线传感器网络的概率统计分析［J］.探测与控制学报，2007，29（2）：16-19.

［13］邓亚平，吴川平.基于移动节点的无线传感器网络中的瓶颈节点［J］.计算机应用，2011，31（7）：1939-1943.

［14］底欣，张百海.无线传感器网络瓶颈节点判断及路由方法研究［J］.仪器仪表学报，2011，32（9）：1973-1980.

［15］田贤忠，阳胜.基于网络编码的无线传感器网络瓶颈区域生存时间优化策略［J］.计算机学报，2016，39（5）：1039-1050.

［16］汪小帆，李翔，陈关荣.网络科学导论［M］.北京：高等教育出版社，2012：159-161.

［17］何宇，赵洪利，姚曜等.介数中心性和平均最短路径长度整合近似算法［J］.复杂系统与复杂性科学，2011，8（3）：44-53.

［18］张珍，张振宇，宋蔓蔓.一种基于最短路径介数的重要节点发现算法［J］.计算机工程与应用，2013，50（21）：98-100.

［19］安莹，黄家玮，罗熹，王建新.延迟容忍网络中一种基于节点介数的拥塞感知路由算法［J］.小型微型计算机系统，2014，35（9）：2062-2067.

［20］王灿，吴雪，罗小娟.基于介数中心性的无线传感器网络抗毁性评价方法［J］.传感器与微系统，2015，34（5）：19-21.

Energy Balance Mechanism Based on Betweenness Centrality Important Nodes

GENG Peng，LIU Yan
（Nanjing Institute of Technology，Nanjing 211167，China）

TP393