《节点信息重要程度耦合能耗联合判断机制的WSN关键点裁决算法.doc》由会员分享，可在线阅读，更多相关《节点信息重要程度耦合能耗联合判断机制的WSN关键点裁决算法.doc（21页珍藏版）》请在三一文库上搜索。
1、节点信息重要程度耦合能耗联合判断机制的WSN关键点裁决算法 摘 要： 针对现有的无线传感网络的关键点裁决过程中指标判定单一，判断过程复杂，难以改善区域内数据传输和汇聚性能的不足，提出节点信息重要程度耦合能耗联合判断机制的WSN关键点裁决算法。利用无线传感节点之间的层次关系，通过节点信息重要程度实现对节点与邻居节点的信息交互，获取该节点信息对整个网络关键程度的估计计算，并得到数字特征值；随后根据当前节点的能耗水平及节点与下层节点之间的关联，设计了能耗联合判断机制，结合数字特征值及节点发送数据的能耗增加量，最终获取关键点裁决因子，通过排序实现了传感网内关键点的准确判断。仿真实验表明，与当前WSN关
2、键点裁决算法相比，该算法挖掘了更多的裁决关键点数量，降低了对网络运行的性能影响，其网络拥塞发生时间更低，网络数据汇聚带宽总利用率与稳定运行时间更高 关键词： 无线传感网络； 关键点裁决； 节点信息重要程度； 数字特征值； 能耗联合判断机制； 裁决因子 中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2016）21?0015?06 WSN key point decision algorithm based on node information importance degree and energy consumption joint judg
3、ment mechanism ZHANG Jicheng1， HUANG Xiangdang2， YANG Qiuling2 （1. Yangtze University College of Technology & Engineering， Jingzhou 434020， China； 2. College of Information Science and Technology， Hainan University， Haikou 570228， China） Abstract： Since the key point decision of the available wirele
4、ss sensor network （WSN） has unified decision indicator and complex decision process， and it is difficult to improve the insufficient of data transmission and convergence performance in the region， a new WSN key point decision algorithm based on node information important degree and energy consumptio
5、n joint judgment mechanism is proposed. The hierarchical relationship among the wireless sensor nodes and node information important degree are used to realize the information interaction of current node and neighbor node. The node information is acquired to estimate and calculate the criticality of
6、 the whole network， and obtain the numerical character value. According to the energy consumption level of current node and correlation between current node and underlayer node， the energy consumption joint judgment mechanism was designed. In combination with the energy consumption increment of node
7、 sending data and numerical character value， the key point decision factor is acquired. The sensor network key point is judged accurately with sorting. The results of simulation experiment show that， in comparison with the available WSN key point decision algorithm， the proposed algorithm mined more
8、 key point quantity for decision， reduced the performance influence on network operation and network congestion occurrence time， and improved the whole bandwidth utilization of network data aggregation and stable running time. Keywords： wireless sensor network； key point decision； node information i
9、mportant degree； numerical character value； energy consumption joint judgment mechanism； decision factor 0 引 言 随着无线传感技术的不断发展，无线传感网广泛地运用于工业生产、环境监控、应急管理等领域，发挥了良好的社会及经济效益1。然而，无线传感网技术也存在很多的局限性，特别是因节点能量受限或因环境恶劣而导致节点失效时，整个网络的运行质量会受到很大的影响2。为降低这种现象的发生，通过一定的算法和检测技术对无线传感网中关键性节点进行判断裁决，并且对这些节点进行重点保障，能够有效地提升网络的运
10、行质量，降低网络因节点失效而出现运行不畅的现象3?4 对此，研究者提出了很多基于能量调控机制的WSN网络关键点裁决算法，常用的指标有精密程度与度量连通度等裁决指标，在网络性能良好时能够有效地对关键点进行裁决。如文献5提出了一种基于聚类思想的中心评估裁决算法，通过对网络中节点的信息收发性能及功率裁决，实现了对网络关键点的初步裁决，其精度达到了很高的水平。但是，该算法由于没有考虑到节点能量受限情况，在网络节点收发强度较大时，其裁决收敛性能较差，容易导致节点失效。文献6提出了一种基于等级质量递归的节点裁决机制，通过对网络中全部节点建立等级信息表，优先保障等级质量较高的节点，实现了对关键点的迅速裁决，
11、裁决的时间成本很低。然而引入周期轮询机制后，由于需要按周期对网络中全部节点进行轮询，并对先前轮询的结果进行更新，当网络节点采集频率较高时，裁决的精确度也会随之降低。杨国宁等提出了一种基于能量阈值控制的WSN关键点裁决算法7，通过网络中节点的能量剩余消耗周期来评估其关键，对于选取的节点而言，能够高效地将该节点从节点集合中选取出来。但是，由于单纯采取能量阈值的机制对节点能量进行评估，容易将一些休眠节点作为关键点加入需要维护的关键集合中，形成大量的误判节点，增加了网络的维护开支 为解决上述难题，考虑到单纯使用一种指标进行裁决将存在较大的弊端，本文提出了基于节点信息重要程度及节点能耗联合判断机制的WS
12、N关键点裁决算法，通过综合考虑当前节点的能耗水平及节点与节点信息之间的影响程度，得到关键点的详细数字特征，并综合能耗增加因素进行关键点裁决，从而实现了对网络中关键点的判定。最后通过NS2仿真平台对本文算法进行仿真实验 1 网络拓扑结构模型及能量传输模型 由于WSN网络节点之间的通信采用无线射频信号进行信息传输及数据传输，因此，对于某个节点而言，其通信范围内能影响的节点数目越大，则其在网络中的重要程度也就越高。此外，由于WSN网络节点属于一次性部署，一旦节点能量耗尽，则不但自身失效，同时与之相关的节点也都会受到很大影响8。现有基于单一重要程度裁决的算法中仅仅考虑自身能量的限制因素，当节点性能受限
13、时，容易导致裁决缺失的现象发生，因此需要综合能量及其他节点信息的情况实现关键点的裁决9 1.1 网络拓扑结构模型 由于无线传感网均采用大规模节点部署方式进行传感数据的采集、汇聚、上传，最终传输到sink节点中进行数据处理，其中除了sink节点外，其他节点的能量均受限制；网络节点按照sink节点中保存的路由表跳数进行层次划分，传感数据通过各层节点的汇聚，实现传感数据的分层汇聚10，如图1所示 为方便研究，本文做如下的模型假设： （1） 除第一层传感节点外，其余传感节点均需要通过其他节点的汇聚实现数据的传输，且各个传感节点在不同的时间内，对周围环境数据的采集频率、强度、功率均有所不同； （2） s
14、ink节点除了可以将全部的传感数据汇聚到自身缓存中之外，还可以保存任意一个传感节点详细的坐标信息； （3） 每一个层次的传感节点在进行数据汇聚过程中不具备独立性，当前某个传感节点一旦因节点能量耗尽而难以正常工作时，对该节点所处层次的上下各层节点的数据汇聚均有显著的影响 1.2 能量传输模型 由于无线传感网的传感节点是通过无线射频信号方式进行数据传输，因此其能量的消耗主要用于数据的接收和发送11。本文采用的能量模型为简单收发模型，对于第i层传感节点而言，发送数据所消耗的能量大小Ei（k）为： Ei（k）=Psend+kR3Pnest （1） 式中：Pnest为第i-1层中负责汇聚的节点在当前时刻
15、接收数据的功率；Psend为第i层传感节点在当前时刻发送数据时的功率；R为第i层传感节点的最大通信半径；k为该时刻发送数据的节点发射的数据总量，单位为bit 则第i-1层中负责汇聚的节点在当前时刻接收数据消耗的能量Ei（k，i-1）为： Ei（k，i-1）=R3Pnest （2） 从模型（1）和模型（2）中可知，基于分层结构的WSN网络在进行数据汇聚时，发射节点的能量消耗与接收节点的能量消耗均呈现一定的三次方关系； 因传感节点的射频信号在空间中以球面传播形式进行传播，信号的衰减也呈现三次方关系。对于发射节点而言其能量的消耗还与其负责发送的数据量有关，数据量越大消耗的能量也就越大。此外，对于发射
16、节点和接收节点而言，其相应的发射功率和接收功率与当前发送的数据特别是网络控制信息及写入缓存的数据信息等有密切的关系。因此，在实际中可以通过一定的能量处理机制，对节点在收发信息时的能量进行调整，以便降低节点在收发信号时的功率水平，从而达到降低节点能耗的目的 2 本文WSN关键点裁决算法设计 根据前面提及的网络拓扑结构模型及能量传输模型，本文提出了一种基于区域数据及能耗判断机制的WSN关键点裁决算法（Point Decision Algorithm based on Regional Data and Energy Consumption，RDEC算法），整个算法通过节点信息及能耗判断，综合得出节
17、点相对于整个网络的关键程度，从而实现对关键点的精确裁决，整个算法过程由节点信息重要程度判断、能耗程度判断、关键点裁决三个部分构成，如图2所示。 2.1 节点信息重要程度判断 在判断某个关键点对于网络是否重要时，该节点与周围节点的信息交互情况是非常重要的决策因素12。对于某个节点而言，其节点信息的重要程度主要由三个因素决定：一级连通程度，即当前节点与周围节点的连接程度；二级连通程度，即周围节点与其他节点的连通程度；信息交互度，即当前节点与其他节点在除数据汇聚之外尚有其他信息交互时的信息交互程度。通过综合考虑上述三种因素，得到节点信息重要程度的数字特征，即节点信息裁决因子 对于任意无线传感网拓扑结
18、构图G=，其中V为图G的节点集合，E为图G的边集合。显然，对于任意节点i而言，其连通度数为与之发生信息交互关系的节点个数，同时也是该节点的一级连通程度，设该个数为i，则i满足如下的关系： i=vVvij （3） 其中v为V中任意一个节点 此外vij满足如下的关系： vij=1 （4） 当仅当节点i与节点j间存在无向边时，模型（4）成立 通过i可知，与节点i发生信息交互的节点个数越多，节点i的重要程度也就越高；但是，由于该项指标无法准确反映与节点i相邻的其他节点的状况，而相邻节点的运行状况对节点i也会有重要影响，因此单独的i无法准确地对节点重要程度进行评估，需要综合节点i的相邻情况进行修正 设i
19、j为节点i相邻的全部节点j的度数，并设j为j的一级连通程度，则： ij=jj （5） 综合模型（3）与模型（5），可得节点i的总连通程度i满足如下的表达式： i=i+ij （6） 节点i的总连通程度反映了节点i与周围节点的联系情况，特别是在一级连通程度基础上修正后的二级连通程度，不仅能反映节点i将数据汇聚到其他节点的情况，而且能够体现其他与节点i相邻的节点进行数据汇聚的情况。从图论13角度而言，模型（6）仅仅反映了各个节点之间的边集合关系，难以反映节点间的紧密程度，故本文定义节点i的紧密系数i为： i=Ei_maxi （7） 式中：i的定义同模型（3）；Ei_max表示节点i所属层次的节点最大
20、的一级连通程度，Ei_max可以通过模型（3）的定义，不断递归第i层节点而计算得到，当节点i的层次已定时，Ei_max为一个常数。显然i的数值越小，则节点i与相邻节点的紧密程度更高 综合模型（3）和模型（7）可形成同时反映节点i连通程度及紧密程度的数字特征值i： i=ii （8） 在模型（8）中，紧密系数i越大，则i越大，节点的总连通程度i越大，则i也就越大；且i与i呈现明显的正相关关系。通过模型（8）可知，某个节点i对整个网络的重要程度，通过数字特征值i不但可以裁决出连通程度很高的关键点，还可以将本身连通程度不高，但紧密程度非常高的关键点裁决出来，判断过程中不需要对网络整体进行评估，仅需要对
21、节点相邻的区域内的全部节点进行评估，即可得到该关键点的数字特征，在进行网络保障过程中，选取数字特征值较大的节点进行重点保障，即可以达到增强网络数据传输性能的目的 2.2 能耗联合判断机制 由于整个网络中传感节点进行数据汇聚采用层层汇聚的方式，当某个节点i因能量消耗殆尽而导致无法上传数据时，其他需要通过节点i进行数据汇聚的节点就需要根据2.1节所示的节点信息重要程度判断的方式，通过再次计算相应的数字特征值获取关键点。与采用原有节点i进行汇聚相比，在选取过程中，获取的新数据汇聚路径的能耗会增加，显然该增加部分越大，说明原节点i的重要程度越高 当节点i暂时无法正常工作时，其下级的各个节点就需要重新在
22、节点i对应的层次中重新寻找其他节点作为替代，以便进行数据汇聚传输。因此，本文将节点i作为汇聚节点，其需要被替代的概率Pr（i）定义为： Pr（i）=Elast（i）Eall（i）i （9） 式中：i的定义同模型（3）；Elast（i）表示节点i的剩余能量大小；Eall（i）表示节点i在初始时刻的总能量大小 若节点i的剩余能量越大，且连通程度越小，则i继续承担数据汇聚功能的可能性也就越大。设节点j为节点i的下层节点，据模型（9）可知，节点j需要重新选择汇聚节点的概率Pr（i）为： Pr（i）=Pr（i）kiPr（k） （10） 式（10）反映了第i个节点在出现故障时，综合考虑其他同层节点的归一化
23、因素以后被替代的概率，其中k表示与节点i处于同一层节点的全部其他节点 设节点i在t时刻失效，则当前时刻其下层节点传输l比特数据消耗的能量E（l，t）为： E（l，t）=Ei（l）i=1MPr（i）i=t （11） 式中：Pr（i）i=t表示t时刻时Pr（i）的数值；M表示节点i的全部同层节点的集合（i除外） 根据模型（11）可知，当节点i下一时刻（即t+t时刻）失效时，其下层节点在发送l比特数据时，额外需要增加的能量大小E（l，t）满足： E（l，t）=E（l，t+t）-E（l，t） （12） 将上述模型简化为： E（l，t）=Ei（l）i=1MPr（i）i=t+t-i=1MPr（i）i=t
24、（13） 模型（13）反映了当某个汇聚节点i失效后，该节点在能耗上对网络的重要程度，该数值越大，则说明节点i的重要程度越高 2.3 关键点裁决 综合评估某个节点的重要程度时，仅仅以某一方面的重要程度作为裁决该节点是否隶属于关键节点会存在较大的不足。因此，需要结合节点信息重要程度及能耗重要程度进行综合判断。本文算法在关键点裁决的过程中，综合上述两个因素，给出的关键点裁决因子f（i）为： f（i）=（i）m1E（l，t）m2 （14） 其中，m1+m2=1，m1和f（i）为裁决因子，介于01之间 将模型（8）和模型（12）代入模型（14），则关键点裁决因子为： f（i）=（ii）m1Ei（l）i=
25、1MPr（i）i=t+t-i=1MPr（i）i=tm2 （15） 在进行关键点裁决时，可以根据关键点裁决因子f（i）的大小进行升序排序，数值越大者，其关键程度越高，需要给予重点保障 本文算法流程如图3所示，步骤如下： Step1：首先进行网络初始化，根据距离sink的跳数多少，从大到小对节点进行层次排序，相同大小跳数的节点归入同一层。进行完层次排序之后，各个节点将自身路由信息发送至sink节点进行信息备份； Step2：每个节点依次按照模型（3）（6），计算自身的总连通程度，并结合模型（7）计算得到的数字特征值； Step3：得到数字特征后，每个节点依次对下级的各个节点进行统计汇总，按照模型（
26、9）（13）计算得到自身的能耗重要程度； Step4：通过Step3，Step4 得到相关参数，代入模型（15）进行关键点裁决因子计算； Step5：再对各个节点的关键点裁决因子进行排序，并将结果发送到sink节点中进行保存，数值越大的节点其重要程度越高，网络维护时，将重点保障这些节点的稳定可靠运行 3 仿真实验 由于无线传感网中各个节点是采取分层结构进行组织的，上一层节点均承担下一层节点的数据汇聚任务。其中各个层次的关键点需要承担更多的数据汇聚任务，当这些关键点因故障无法正常工作时，整个网络的运转也将受到极大的影响。因此本文仿真实验主要从关键点裁决数量、网络拥塞发生时间、网络数据汇聚带宽总利
27、用率、网络稳定运行时间四个指标出发，同当前广泛用到的ENCAST算法14、CNDBE算法15进行对比，以便验证本文算法的优势。本文仿真采取NS2仿真平台，详细仿真参数见表1 3.1 关键点裁决数量 在不同网络节点分层数量情况下，三种算法的关键点裁决数量测试结果，如图4所示。由图4可知，随着网络节点最大分层数量的不断增加，网络结构逐渐复杂，本文算法在裁决关键点的数量上始终优于ENCAST算法、CNDBE算法。这是因为传感网络关键点的数量与结构复杂程度密切相关，随着网络结构的逐渐复杂，网络中关键点的数量也逐渐增加。而本文算法采取基于节点信息重要程度及节点能耗联合判断机制，因此能够有效地从网络中筛选
28、出关键点，随着网络结构逐渐复杂，能够筛选出的关键点数量也就越来越多。而ENCAST算法、CNDBE算法仅仅从单一方面进行筛选，对于其他不同类型关键程度的节点容易遗漏 3.2 网络拥塞发生时间 在网络节点密度不断增加的情况下，三种关键点裁决算法的网络拥塞发生时间测试结果，如图5所示。由图5可知，随着网络节点密度的不断增加，ENCAST算法、CNDBE算法的网络拥塞发生时间也不断增加，而本文算法的网络拥塞时间处于相对稳定的状态。这是因为随着网络节点密度的增加，传感节点采集的数据量也呈现出不断增加的态势，使得每层节点向上汇聚的数据量也不断增加。而本文算法是综合信息重要程度及节点能耗两个方面同时对承担
29、汇聚功能的关键点进行裁决，在进行网络维护时，能够根据裁决因子的高低对最容易发生故障的关键点进行重点维护，且能够裁决出的关键点数量要高于单一裁决因素时的数量，因此能够有效防止承担汇聚功能的关键点发生的故障，从而降低了网络拥塞发生的频率，延缓了网络拥塞发生时间 3.3 网络数据汇聚带宽总利用率 在网络节点分层数量不断增加的情况下，本文算法、ENCAST算法、CNDBE算法的网络数据汇聚带宽总利用率测试结果，如图6所示。由图6可知，随着网络节点分层数量的不断增加，本文算法的网络数据汇聚带宽总利用率始终优于ENCAST算法、CNDBE算法。这是因为无线传感网的汇聚带宽是由各个关键点汇聚的总带宽决定的，
30、当关键点上出现拥塞现象导致网络数据汇聚受阻时，网络数据汇聚带宽总利用率也会不断下降。而本文算法从信息重要程度及节点能耗两个方面入手，通过提高对关键点的裁决程度，在裁决出承担汇聚功能的各个关键点的同时，对这些节点进行排序，从而做到重点保障数据汇聚节点的正常汇聚，最终降低了网络数据汇聚带宽总利用率的减缓程度。而ENCAST算法、CNDBE算法由于无法高效裁决出关键点，当这些关键点因故障不能发挥作用时，因其未能检测到这些关键点而无法按关键点的保障标准对这些节点进行保障，导致这些节点在发生故障后无法正常的进行修复，从而导致网络数据汇聚受阻，使其带宽总利用率下降幅度也随之扩大 宽总利用率测试结果 3.4
31、 网络稳定运行时间 在网络节点密度不断增加的情况下，本文算法与ENCAST算法、CNDBE算法的网络稳定运行时间测试结果，如图7所示。由图7可知，随着网络节点密度的不断增加，ENCAST算法、CNDBE算法对应的网络稳定运行时间呈现不断下降的趋势，而本文算法对应的网络稳定运行时间始终处于基本稳定不变的态势。这是因为无线传感网主要承担数据采集和汇聚工作，特别是当数据汇聚过程受阻时，网络处于拥塞状态，从而导致网络稳定运行时间下降。本文算法由于能够将承担汇聚工作的各个关键点裁决出来，且裁决出的关键点数量要高于对照组算法（见图4），因此，本文算法能够尽可能多的将关键点裁决出来并保障其运行，当网络出现拥
32、塞现象时，能够更多地实现对故障点的覆盖，因此大大降低了因拥塞等发生而导致的网络难以稳定运行的情况。而ENCAST算法、CNDBE算法是单纯从某个方面对网络中关键点进行裁决，导致关键点裁决出的数量过少，当剩余未被裁决出来的关键点因故障而无法工作时，由于sink信息表中没有这些关键点的信息，因而难以对这些关键点进行保障，从而导致网络因故障因素影响到网络稳定运行时间，出现时间不断下降的现象。 4 结 语 本文提出了一种基于节点信息重要程度及节点能耗联合判断机制的WSN关键点裁决算法，主要通过综合评估节点信息重要程度及节点能耗来判断某个节点对整个网络的关键程度，当网络进行初始化之后，对于任意一个网络节
33、点，均根据其与周围节点的信息交互程度及其他下层节点在该节点出现故障而不能工作时的能量开销增加值来进行裁决因子的计算，且通过排序对其数值最大值的节点进行重点保障，从而实现对网络中关键点尽量多的全覆盖。仿真实验表明，与常用的ENCAST算法、CNDBE算法相比，本文提出的算法能够在同一传感网络中尽量多的挖掘出关键点，且对网络各项性能指标有明显的改善，具有较好的实践价值 注：本文通讯作者为黄向党 参考文献 1 JENKINS R， BURTON A M. A survey of 100% energy accuracy in WSN J. Autonomous robots， 2013， 451（3
34、1）： 435?441. 2 CHEN D， L? L， SHANG M S， et al. Identifying influential nodes in complex networks J. Fuel & energy abstracts， 2012， 391（4）： 1777?1787. 3 RUSEK F， PERSSON D， LAU B K. Scaling up WSN：opportunities and challenges with very large arrays J. IEEE signal process magazine， 2012， 30（1）： 40?46.
35、 4 ZHANG X， ZHU J， WANG Q， et al. Identifying influential nodes in complex networks with community structure J. Knowledge?based systems， 2013， 42： 74?84. 5 WANG J S， WU X P， YAN B， et al. Improved method of node importance evaluation based on node contraction in complex networks J. Proscenia enginee
36、ring， 2011， 15（8）： 1600?1604. 6 GAO C， LAN X， ZHANG X G， et al. A bio?inspired methodology of identifying influential nodes in complex networks J. PloS One， 2013， 8（6）： 1?11. 7 杨国宁，冯秀芳，樊刘娟.一种基于最优融合集的多传感器数据融合算法J.软件学报，2012，23（2）：134?140. 8 邬厚民.无线传感网络中能量和距离改良的LEACH分簇算法J.中国测试，2012，38（5）： 62?66. 9 WANG L
37、， GENG X. A community?driven hierarchical message transmission scheme in opportunistic networks J. Smart computing review， 2011， 1（1）： 85?94. 10 AMMARI H M， DAS S. A study of k?coverage and measures of connectivity in wireless sensor networks J. IEEE transactions on computers， 2010， 59（2）： 258?267.
38、11 CHEN A， KUMAR S， LAI T H. Local barrier coverage in wireless sensor networks J. IEEE transactions on mobile computing， 2010， 9（4）： 491?504. 12 方富贵.图论的算法和应用研究J.计算机与数字工程，2012，8（2）：52?57. 13 刘建国，任卓明.复杂网络中节点重要性排序的研究进展J.物理学报，2013，62（17）：178?184. 14 HAO X C， JIA N， LIU B. Multi?path optimizing routing protocol based on predicting congestion for wireless sensor network J. Journal of electronics & information technology， 2011， 33（5）： 1261?1265. 15 刘彬，王文吉，李雅倩，等.基于能量因素的无线传感网络关键节点判定算法J.电子与信息学报，2014，36（7）：1728?1734.