传感器网络节点重要性评价方法

摘要

本发明公开了一种传感器网络节点重要性评价方法，涉及无线传感网络通信技术领域，包括以下步骤：S1：建立传感器网络的信息传递路由表，确定传感器网络的拓扑结构；S2：根据路由表，收集所述传感器网络中所有节点的能量信息；S3：判断是否有节点的能量耗尽，若有则转至步骤S4；若没有，则根据每个节点的拓扑结构贡献和剩余能量计算每个节点的重要性，并转至步骤S2；S4：计算所述传感器网络的运行次数作为所述传感器网络的生命周期。本发明能够更准确地计算传感器网络节点重要性，从而能够通过对重要性节点的保护来提高传感器网络的抗毁性。

说明书

技术领域

本发明涉及无线传感网络通信技术领域，特别涉及一种传感器网络节点重要性评价方法。

背景技术

传感器网络是集信息采集、信息传输、信息处理于一体的综合智能信息系统，是当前信息领域研究和开发的一个热点，可实现数据的采集量化、处理融合和传输应用，可用于军事侦察、环境监测、医疗监护、空间探索、城市交通管理、仓储管理等军事和民用领域。在传感器网络的实际应用中，一般都需要部署大量的传感器节点，由于节点往往工作在恶劣的环境中，并且通常采用能量有限的电池提供能量，所以传感器网络很容易出现因为能量耗尽或者受到自然界破坏而出现部分节点失效的情况；此外，对传感器网络有目的性的破坏也会直接或间接地导致整个网络的瓦解。通过节点重要性的评价，能够在规模庞大、结构复杂的网络中准确而快速的发现网络中的重要节点，从而能够通过对重要节点的保护提高网络的抗毁性。

目前网络节点的重要性评价主要有社会网分析领域内的节点重要性排序算法和系统科学领域的节点重要性评价方法。前者基于“重要性等价于显著性”，即节点重要性等价于该节点与其他节点的连接而使其具有的显著性。后者基于“破坏性等价于重要性”，即通过度量节点或节点集被删除后对网络连通的破坏程度来定义其重要。这些研究大部分都是基于节点度、紧密度、特征向量、介数等指标或者对相关指标进行改进来评价节点的重要性。大多数研究所采用的都是单一评价指标，因此评价效果存在不确定和不全面等问题。特别是在目前的研究中，专门针对传感器网络节点重要性评价的研究几乎没有。由于传感器网络工作在一个高度复杂的网络环境中，如何提高传感器网络在复杂网络环境下的可靠性成为传感器网络研究中急需解决的主要问题。因此，对传感器网络节点重要的评价研究具有重要的实际意义和应用价值。有必要就如何建立合理的传感器网络节点重要性评价指标进行深入的探讨和研究。

由中国国家知识产权局2011年2月16日公开，公开号为CN101976245A的专利申请“网络中节点重要性的排序方法”，公开了一种网络中节点重要性的排序方法。该方法在有向网络中加入一个背景节点，并且背景节点与有向网络中的每个节点都建立双向的链接；初始时刻给每个节点一单位的资源，然后在这个含有背景节点的网络中随机游走，进行资源分配，直到达到稳态；将稳态时背景节点上的资源数加上从背景节点获得的资源数之和为该节点重要性的分数；按照重要性分数从高到低的顺序将节点排序，排在最前面的表示该节点越重要。该方法可用于网络中节点重要性的排序，如网页重要性的排序。

以上的节点重要性评价的方法分别着眼于不同的侧重点而有所利弊，主要体现在：

(1)现有的节点重要性评价方法未考虑节点剩余能量等问题，其评价方法并不适于传感器网络；

(2)现有的节点重要性评价方法大都采取单一指标的评价方法，评价效果存在不确定和不全面的问题。

发明内容

(一)要解决的技术问题

本发明要解决的技术问题是：如何更准确地估计传感器网络的节点的重要性。

(二)技术方案

为解决上述技术问题，本发明提供了一种传感器网络节点重要性评价方法，包括以下步骤：

S1：建立传感器网络的信息传递路由表，确定传感器网络的拓扑结构；

S2：根据路由表，收集所述传感器网络中所有节点的能量信息；

S3：判断是否有节点的能量耗尽，若有则转至步骤S4；若没有，则根据每个节点的拓扑结构贡献和剩余能量计算每个节点的重要性，并转至步骤S2；

S4：计算所述传感器网络的运行次数作为所述传感器网络的生命周期。

其中，所述步骤S1具体包括：

汇聚节点采用洪泛的方式向所有节点发送数据，通知节点开始收集数据，各节点收到汇聚节点发来的数据后，向汇聚节点发送应答报文，应答报文包括：节点剩余能量和所要发送的数据包大小；

汇聚节点接收到应答报文之后，根据节点剩余能量构建动态路由树；

汇聚节点通过洪泛的方式将路由树信息向传感器网络中所有节点广播；

各节点根据收到的路由树信息，建立信息传递的路由表，确定网络拓扑结构，进行数据传输。

其中，所述步骤S3中计算每个节点的重要性的方式具体为：

$M\left(i\right)=k_{1}C\left(i\right)+k_2(1-\frac{\mathrm{Re}\left(i\right)}{E})$

其中，M(i)为节点i的重要性，C(i)为：

$C\left(i\right)=\frac{\underset{j<k}{\Sigma }{g}_{\mathrm{jk}}\left(i\right)/g_{\mathrm{jk}}}{(N-1)(N-2)/2}$

表示任意其它节点之间的最短路径均经过节点i，则节点i对传感器网络拓扑结构贡献，其中，g_jk表示节点j和节点k之间的最短路径数，g_jk(i)表示节点j和节点k之间经过节点i的最短路径数，N为所述传感器网络中的节点总数；

Re(i)为节点i的剩余能量，E为节点i初始能量，k₁为拓扑贡献调节因子，k₂为剩余能量调节因子，且k₁+k₂＝1，0＜k₁＜1，0＜k₂＜1。

其中，所述步骤S3中，每次计算完所有的节点的重要性之后，还包括步骤：计算所述传感器网络受到随机打击时的重要性评价指标：

$M=\underset{i=1}{\overset{i=N}{\Sigma }}M\left(i\right)\frac{1}{N}.$

其中，所述步骤S3中，每次计算完所有的节点的重要性之后，还包括步骤：计算所述传感器网络受到蓄意打击时的重要性评价指标：

$M^{\prime }=\underset{i=1}{\overset{i=N}{\Sigma }}{(M\left(i\right)-\underset{i=1}{\overset{i=N}{\Sigma }}M\left(i\right)\frac{1}{N})}^2.$

其中，还包括步骤：按计算得到的重要性值由大到小排列在前P个的节点附近部署超级节点以延长所述传感器网络的生命周期，所述超级节点为能量大于等于3000J，节点无线电通信半径大于等于500m的节点。

(三)有益效果

本发明通过每个节点的拓扑结构贡献和剩余能量能够计算出传感器网络节点的重要性，从而能够通过对重要性节点的保护来提高传感器网络的抗毁性。

附图说明

图1是本发明实施例的一种传感器网络节点重要性评价方法流程图；

图2是节点对网络拓扑结构贡献示意图；

图3是节点剩余能量分布示意图；

图4是网络重要节点分布示意图；

图5是在网络中专门加入超级节点、随机加入超级节点、随机打击重要节点及蓄意打击重要节点情况下网络生命周期的比较曲线图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

如图1所示，本发明的传感器网络节点重要性评价方法包括：

步骤S101，建立传感器网络的信息传递路由表，确定传感器网络的拓扑结构。能量受限是传感器网络存在的最大问题，为了能有效节约节点能量，防止频繁使用同一条路径传输数据而造成该路径上节点能量消耗过快而过早失效，需要一种能够权衡节点能量和网络拓扑结构的动态路由算法来均衡数据传输过程中所消耗的网络能量，以延长传感器网络的生存时间。因此，本实施例充分考虑网络能耗和节点剩余能量，通过Dijkstra算法构建动态路由树，具体方式如下：

汇聚节点采用洪泛的方式向所有节点发送数据，通知节点开始收集数据，各节点收到汇聚节点发来的数据后，向汇聚节点发送应答报文，应答报文包括节点剩余能量和所要发送的数据包大小。汇聚节点是传感器网络中的一种特殊节点，主要负责收集其它传感器节点采集过来的信息(其中包括上述的节点剩余能量和所要发送的数据包大小)，并将采集的信息发送到互联网、卫星或其它接收系统。

汇聚节点接收到应答报文之后，根据节点剩余能量构建动态路由树。

汇聚节点通过洪泛的方式将路由树信息向网络中所有节点广播。

各节点根据收到的路由树信息，建立信息传递的路由表，确定网络拓扑结构，进行数据传输。

步骤S102，根据路由表，汇聚节点收集传感器网络中所有节点的能量信息。由于传感器网络在运行过程中，节点的能量在不断变化，不同节点的能量也有所不同。因此，每次收集到的能量信息也不同。

步骤S103，判断是否有节点的能量耗尽，若有则转至步骤S105；若没有，则转至步骤S104。

步骤S104，根据每个节点的拓扑结构贡献和剩余能量相结合的方式计算每个节点的重要性，并转至步骤S102。其中，每个节点的重要性M(i)具体计算方式如下：

$M\left(i\right)=k_{1}C\left(i\right)+k_2(1-\frac{\mathrm{Re}\left(i\right)}{E})$

其中，C(i)为：

$C\left(i\right)=\frac{\underset{j<k}{\Sigma }{g}_{\mathrm{jk}}\left(i\right)/g_{\mathrm{jk}}}{(N-1)(N-2)/2}$

表示任意其它节点之间的最短路径均经过节点i，则节点i对传感器网络拓扑结构贡献，其中，g_jk表示节点j和节点k之间的最短路径数，g_jk(i)表示节点j和节点k之间经过节点i的最短路径数，C(i)刻画了网络中的节点对于信息流动的影响力，反映了该节点在完成网络通信任务中提供最短可用路由的能力，可用来确定信息负载繁重的网络节点。N为所述传感器网络中的节点总数。

Re(i)为节点i的剩余能量，E为节点初始能量，k₁为拓扑贡献调节因子，k₂为剩余能量调节因子，且k₁+k₂＝1，0＜k₁＜1，0＜k₂＜1，在实际评价过程中，可根据实际情况选择合适的k₁和k₂。

k₁C(i)体现了节点位置对节点重要性的评价，k₁C(i)越大表示节点i拓扑结构贡献越大，即节点i在网络中所处的位置越重要(很多节点间的最短距离都经过节点i)。体现了剩余能量对节点重要性的评价，越大，节点i越重要，即剩余能量Re(i)越小，节点i越重要。实际运用中可根据需要调节k₁和k₂的大小来确定节点i的重要性。

步骤S105，计算所述传感器网络的运行次数作为所述传感器网络的生命周期，即当传感器网络中第一次出现节点的能量耗尽时，则认为传感器网络的生命周期结束。

在步骤S104中，每次计算完所有的节点的重要性之后，还包括步骤：计算所述传感器网络受到随机打击时的重要性评价指标：

$M=\underset{i=1}{\overset{i=N}{\Sigma }}M\left(i\right)\frac{1}{N}.$

其中，所述步骤S3中，每次计算完所有的节点的重要性之后，还包括步骤：计算所述传感器网络受到蓄意打击时的重要性评价指标：

$M^{\prime }=\underset{i=1}{\overset{i=N}{\Sigma }}{(M\left(i\right)-\underset{i=1}{\overset{i=N}{\Sigma }}M\left(i\right)\frac{1}{N})}^2.$

得到节点的重要性之后，就可以根据重要性对节点进行调整，按计算得到的重要性值由大到小排列在前P个的节点的附近部署增超级节点以延长所述传感器网络的生命周期，也就是说在重要节点附近部署超级节点，实际就是一种备份，当重要节点失效时，超级节点开始工作。所述超级节点为能量大于等于3000J，节点无线电通信半径大于等于500m的节点，比一般传感器节点的能量和通信半径都要大。

对本发明的方法进行了实验，实验参数如表1所示：

表1实验用的参数

  参数名称  参数设置值  目标区域  1000m×1000m  节点数目  500  节点最大发射距离  200m  节点初始能量  1000J  节点接收或发送每比特数据的能耗  50nJ/bit  放大器发送每比特数据的能耗  100pJ/bit/m²  路径损耗系数  2  节点每次发给汇聚节点的数据量  1Mb  仿真次数  100

仿真1：为评价本发明节点重要性评价指标的有效性，对步骤S101的路由算法进行仿真。通过仿真可以得到节点对拓扑结构贡献及剩余能量之间的关系，如图2和图3所示。其中，图2为某时刻网络中节点对拓扑结构贡献的示意图，从图可知网络中少部分节点对网络拓扑结构的贡献比较大，主要是因为这些节点在路由的最短路径上处于关键位置，需要经常转发数据，这在节点重要性评价综合指标M(i)的k₁C(i)部分有所体现；图3为某时刻网络中节点剩余能量分布示意图，从图3中可知在拓扑结构中贡献大的节点，由于经常转发数据，耗能比较快，因此这些节点的剩余能量相对较低，这在节点重要性评价综合指标M(i)的部分有所体现。对比图2和图3可以看出，整个网络中节点的拓扑贡献程度与其剩余能量大致成反比，这与传感器网络实际应用的情况相符。

仿真2：根据图2和图3中节点对拓扑结构贡献及剩余能量的关系及数据，结合本发明的节点重要性评价综合指标，取k₁＝0.5，k₂＝0.5，可以得到网络中重要节点的分布情况如图4所示。以标号为5和61的节点为例，从图2可知节点5和节点61对拓扑的贡献分别为0.85和0.84，从图3可知节点5和节点61的剩余能量分别为50J和40J，根据节点重要性评价指标$M\left(i\right)=k_{1}C\left(i\right)+k_2(1-\frac{\mathrm{Re}\left(i\right)}{E}),$可知$M\left(5\right)=0.5\times 0.85+0.5\times (1-\frac{50}{1000})=0.9,$$M\left(61\right)=0.5\times 0.84+0.5\times (1-\frac{40}{1000})=0.9,$因此节点5和节点61的节点重要性为0.9。从图4可知，前100个节点中，标号为5、61(从图中也可看出重要性为0.9)等节点属于网络中的重要节点。因此，对重要性较大的节点进行保护，可以提高传感器网络的抗毁性，延长传感器网络的生命周期，如：加大上述5、61等节点的初始能量，或在其附近部署超级节点。

仿真3：为进一步分析随机打击和蓄意打击时节点重要性评价指标M和M′的有效性，根据图4中网络重要节点的分布情况，对网络的抗毁性进行分析。仿真时，针对网络中的重要节点，专门加入超级节点(节点能量3000J，节点无线电通信半径为500m)、随机加入超级节点、随机打击重要节点和蓄意打击重要节点。对上述4种情况下传感器网络生命周期的变化情况进行分析。从图5可以看出，在重要节点附近加入超级节点后网络的生命周期有大幅度的提升，网络抗毁性增强；蓄意打击重要节点后网络的生命周期有较大幅度下降，网络抗毁性降低；随机加入超级节点和随机打击重要节点网络的生命周期变化不明显。上述仿真结果说明了对网络中重要节点进行保护以提高网络抗毁性的重要性，进一步验证了本发明的节点重要性评价综合指标的合理性和有效性。

以上实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由权利要求限定。