基于层次拓扑的无线传感网络的数据融合算法

陈志国 滕桂法

关键词： 无线传感网; 数据融合; 可信度; 层次拓扑; 权重; 传输时延

中图分类号： TN711?34; TP393                 文献标识码： A                    文章编号： 1004?373X（2018）24?0061?05

Level topology based data aggregation algorithm for wireless sensor networks

CHEN Zhiguo， TENG Guifa

（School of Information Science and Technology， Hebei Agricultural University， Baoding 071000， China）

Abstract： The data authenticity is not considered in the current data aggregation algorithm， and it is possible for sensing nodes to generate wrong sensing measured data in the actual environment. Therefore， a level topology based data aggregation （LTDA） algorithm is proposed for WSNs. In the LTDA algorithm， the confidence level of the sensing measured data is estimated， and only the data whose confidence level is higher than the threshold is allowed to be transmitted. The high?level node with the maximum weight is selected to be the next?hop forwarding node when transmitting data from nodes to the base station. The node weight contains information of distance， residual energy and link quality. The simulation data shows that the proposed LTDA algorithm can reduce the average energy consumption， data packet loss rate and end?to?end transmission time delay.

Keywords： WSN; data aggregation; confidence level; level topology; weight; transmission time delay

0  引  言

無线传感网络 （Wireless Sensor Networks， WSNs）已广泛应用于各类领域[1]，用于各类事件的检测，如森林防火、水温检测、康复医疗。部署环境中的传感节点实时地感测数据，然后将感测传输到基站[2?3]。这个过程就是数据融合问题。

由于传感节点属于微型节点，能量受限。因此，通常密集部署传感节点，进而防止覆盖空洞。然而，密集型部署节点会导致多个节点同时感测同一个异常事件，形成大量的数据。而实际上，这些数据存在一定冗余。同时，有些节点也可能会感测错误的数据[4]。这些特性影响了数据融合的性能。 此外，传感节点需要以有效的方式将感测数据传输基站，即路由问题。换而言之，数据融合[5]问题涉及到数据可信和数据传输两个问题。

目前针对数据融合问题，研究人员提出多类策略。典型的有文献[3]提出的可靠数据的融合算法（Reliable Data Aggregation Algorithm，RDAA）算法。RDAA算法考虑了数据包转发前的时间问题，同时采用组播方式转发数据包[6]。每个节点在转发数据包前均需等待一定时间，为数据融合提供时间。尽管组播方式提高了数据传输效率，但加大了能耗[7?8]。而文献[9]也提出非结构的能耗均衡的数据融合（Structure?Free and Energy?Balanced Data Aggregation，SEDA）算法。SEDA算法将每一类异常事件分配唯一号，然后将同一类号的感测数据进行融合。

然而，这些算法并没有考虑到数据的真实性。在实际环境中，传感节点可能会产生错误的感测数据。例如，受外界噪声或者硬件故障等问题，会引起传感节点感测错误的数据。

为此，提出基于层次拓扑的无线传感网络的数据融合（Level Topology based Data Aggregation，LTDA）算法。LTDA算法首先将网络划分为多个子区域，并且每个子区域的监测权重不同。然后，计算数据的可信性，并且将可信度低于阈值的数据排除。在转发感测数据时，依据距离、剩余能量和链路质量信息选择转发节点，进而提高数据传输效率。仿真数据表明，提出的LTDA算法能够有效地降低能耗，并降低数据传输时延。

1  LTDA算法

LTDA算法主要由可信数据转发和转发节点的选择两部分组成。其中，可信数据转发是指只转发真实的感测数据，不转发不可信的数据。通过可信数据转发机制降低冗余数据，也能降低网络开销。而转发节点的选择是指选择最合适的节点传输数据，提高数据传输效率。

1.1  可信数据转发

部署WSNs的根本目的在于监测目标区域。目标区域一旦发生异常事件，所感测到的异常事件的节点就将感测数据传输至基站，再由基站传输至控制中心处理。通常，整个目标区域面积非常宽广，并且目标区域内不同子区域发生异常事件的概率不同，或者说对不同子区域进行不同等级的监测。例如，基于WSNs的森林防火监测。常将整个森林区域划分为不同监测等级的子区域，珍贵树种区域重点监测，而对普通树种区域并非重点关注。因此，本文将整个区域划分为多个子区域，这些子区域的监测等级不同。假定整个区域划分为成[M]个子区域，每个子区域的监测等级为[l]。即第[i]个子区域的监测等级表示为[li]，且[1≤i≤M]。不同等级的监测子区域如图1所示。

整个感测区域划分成多个子区域，有的区域监测等级达到91%，即[l=95]，而有的区域低至64%。

LTDA算法不仅对监测区域进行等级划分，还对传感节点所感测的数据进行判断，检测其可信性。并依据不同子区域，设置不同的可信阈值。只有感测数据的可信度高于阈值，该数据才允许被转发。

通常，离异常事件发生地越近的传感节点，它们所感测的数据越可信。反之，离事件发生地越远，其感测的数据越偏离真实性。为此，给感测数据定义可信度，其定义如下：

[kidata=Ri-de100]             （1）

式中：[Ri]表示节点[i]的感测半径;[de]表示事件的发生地;[kidata]表示节点[i]所感测数据的可信度。只有当节点[i]的[kidata]值大于它所在子区域的可信阈值，才传输它所传输的感测数据。假定节点[i]在第[j]个子区域，该子区域的可信阈值表示为[Kj]，其定义如下：

[Kj=100-lj100]             （2）

1.2  转发节点的选择

为了缩短数据传输路径，LTDA算法对网络内的节点进行层次划分。将离基站跳数最少，且相同的节点称为第一层。换而言之，离基站一跳距离的节点称为一层节点，离基站二跳距离的节点称为二层节点，依次类推。层级数越小，级别越高。即位于一层节点的级别高于二层节点。当低层次节点需要向基站传输数据时，它首先从高层次中择优选择节点。

为了更好地建立路由，LTDA算法引用基于层次的拓扑。因此，引用控制包HELLO消息。首先由基站以广播方式传输HELLO消息。当一层节点接收HELLO消息后，设定定时器，定时时间随机。当定时时间定时完毕后，接收节点将自己的ID号、节点位置和能量、离基站跳数嵌入HELLO，再转发HELLO消息，其格式如图2所示。

图中：Position表示节点的位置;Res_en表示节点剩余能量;Hop_count表示节点离基站的跳数。基站广播时，Hop_count值设为零。然后，每次节点转发HELLO消息，Hop_count值就加1。 图3显示基站广播HELLO消息的示意图，S4，S1，S2，S3节点首先接收HELLO消息，它们属于一层次节点。

然后，一层次节点再对HELLO消息内的字段值进行更新，再向低层次节点传输。图4显示一层次节点传输HELLO消息的过程。

依次类推。每个层次的节点转发HELLO消息，直至所有节点接收了HELLO消息，进而构建基于层次的网络拓扑结构，如图5所示。

值得注意的是，在交互HELLO消息过程中，一个节点可能接收到来自不同层次转发的HELLO消息。这些HELLO消息内的Hop_count值不同。为此，当接收多条HELLO消息时，节点就从中选择跳距值最小的HELLO消息，其他HELLO消息丢弃。

1.3  转发节点的选择

选择合适的节点转发数据，有利于提高路由性能。为此，LTDA算法引用节点权重指标，并通过节点权重选择下一跳的转发节点。节点权重指标隐含了节点离基站的距离、节点剩余能量，并且反映了链路信息。

假定当前数据包的携带节点为节点[i]，它需要从更高层次节点中选择一个节点作为数据包下一跳的转发节点。若节点[i]位于第[k]层，则节点[i]就从第[k-1]层中选择一个节点作为转发节点。假定第[k-1]层内的N个节点，这N个节点所组成的节点集为[Φk-1]。

首先，计算[Φk-1]中每个节点的权重。以节点[j∈Φk-1]为例，它的权重表示为[λj]，定义为：

[λj=Erej+Qlinkijdij]          （3）

式中：[Qlinkij]为由节点[i]与节点[j]构建链路的质量;[dij]为节点[i]与节点[j]的距離，[dij=xi-xj2+yi-yj2]，其中[xi，yi]，[xj，yj]分别表示节点[i]、节点[j]的坐标;[Erej]表示节点[j]的剩余能量。

节点的剩余能量等于节点的初始能量减去所消耗的能量。假定每个节点的初始能量相同，且表示为[Einit]。而节点所消耗的能量取决能量消耗模型。为此，引用如图6所示的能量消耗模型[10]。

具体而言，当节点传输[q] bit数据，且传输距离为[d]时，所消耗的能量为：

[Etxq，d=qEelec+qεmpd4]      （4）

式中：[Eelec]为传输单一比特数据时发射器所消耗的能量;[εmp]为双径传播模型条件下的功率放大器所消耗的能量[11]。

相应地，节点接收[q] bit数据所消耗的能量表示为：

[Erxq，d=qEelec]             （5）

因此，节点[j]的剩余能量[Erej]可按式（6）計算。假定节点[j]共传输了[B] bit，接收了[A] bit数据。

[Erej=Einit-EtxB，d-ErxA，d]      （6）

此外，LTDA算法引用信号接收强度指标（Received Signal Strong Index， RSSI）反映链路质量。假定节点[i]与节点[j]的链路质量[Qlinkij]可表示为：

[Qlinkij=RSSIijNbits]           （7）

式中：[RSSIij]表示节点[j]接收来自节点[i]数据包的信号强度;[Nbits]表示数据包的比特数。

当节点[i]计算了每个节点的权重后，再从中选择具有最大权重的节点作为转发节点，如式（8）所示：

[pnext=hmax1≤h≤Nλh，h∈Φk-1]         （8）

1.4  数据传输过程

提出的LTDA路由算法主要由数据可信估计和转发节点的选择两个阶段构成。LTDA算法的流程如图7所示。具体而言，首先通过传输HELLO消息，建立基于层次的拓扑结构，然后，传感节点实时地感测异常事件。一旦感测了数据，就估计数据的可信度。再将数据可信度与阈值进行比较。只有大于阈值的数据[12]才允许被传输。最后，通过选择转发节点，作为下一跳传输节点，进而完成数据包的传输。

2  性能仿真

2.1  仿真环境

为了更好地分析LTDA路由性能，利用NS软件建立仿真平台。400个传感节点随机分布于[400 m×400 m]区域，节点的初始能量为70 J。[Eelec=50 nJ/bit]，[εmp=0.001 3 pJ/bit]。所有节点的感测半径为50 m。网络内发生异常事件的频率为[13]。

此外，同时选择RDAA和SEDA作为参照，并分析它们的数据包传递率、数据传输时延以及能耗。每次实验独立重复30次，取30次的平均值作为最终实验数据。

2.2  仿真数据分析

首先，分析数据包产生率和节点数对能耗的影响，如图8、图9所示。从图8可知，数据率的增加提高了平均能量消耗。原因在于：数据率越大，网络内滞留的数据包数就越多，需要更多的节点参与数据包的传输或者转发，加大网络能耗。与RDAA和SEDA算法相比，LTDA算法的平均能耗得到有效的控制。例如，当数据率在65 packets/s时，LTDA算法的能耗为0.06 J，而RDAA算法、SEDA算法的能耗达到0.093 J，0.08 J。

图9显示了节点数对平均能量消耗的影响。从图可知，平均能耗随节点数的增加而上升，而提出的LTDA算法的能耗得到下降。这主要是因为LTDA算法有选择性转发数据，降低了节点转发负担。

接下来，分析数据包丢失率的性能。图10、图11分别显示了数据包产生率、节点数对数据包丢失率的影响。

从图10可知，数据率的增加提高了数据包丢失率，原因在于数据率的增加，加大了网络负担，降低数据包传输的流畅性，最终导致数据包的丢失。但相比于RDAA算法和SEDA算法，提出的LTDA算法的数据包丢失率得到有效的下降。这要归功于LTDA算法在选择下一跳转发节点时，充分考虑了节点的能量、链路质量信息，提高了路由稳定性。

从图11可知，节点数的增加提高了数据包丢失率。节点数的增加降低了数据包丢失率的性能。但是，LTDA算法能够应对节点数的增加，对数据包丢失率进行有效控制。

最后，分析了路由算法的传输时延性能，如图12、图13所示。

从图12可知，提出的LTDA路由有效地控制端到端传输时延，远低于RDAA算法的时延。众所周知，数据包的端到端传输时延取决于路径的连通性和稳定性。而提出的LTDA算法在选择下一跳转发节点时，充分考虑了节点稳定性和链路的稳定性。与图12类似，图13显示了节点数对端到端传输时延的影响。从图13可知，节点数的增加提高了数据包传输的平均时延。原因在于尽管节点数的增加提高网络连通率，但是也加大对网络资源的竞争率，必然增加路由断裂的概率。路由一旦断裂，就需要重建，最终增加传输时延。

3  结  语

针对WSNs的数据融合问题提出LTDA算法。LTDA算法通过HELLO消息的交互，将网络内传感节点划分为不同的层次，同时将网络划分为不同子区域，且每个子区域的监测权重不同。并且从数据可信和数据传输两个角度，提出数据融合性能问题。仿真数据表明，提出的LTDA算法降低了能耗，并且减少了传输时延。后期，将进一步优化算法，将基于簇结构引入算法，提高算法的性能。

注：本文通讯作者为滕桂法。

参考文献

[1] KANSAL A， HSU J， ZAHEDI S， et al. Power management in energy harvesting sensor networks [J]. ACM transactions on embedded computing systems， 2007， 6（4）： 1?40.

[2] MURUGANATHAN S D， MA D C F， BHASIN R I， et al. A centralized energy?efficient routing protocol for wireless sensor networks [J]. IEEE communications magazine， 2005， 43（3）： 8?13.

[3] YOUSE? H， YEGANEH M H， ALINAGHIPOUR N， et al. Structure?free real?time data aggregation in wireless sensor networks [J]. Computer communications， 2012， 35（9）： 1132?1140.

[4] 陈东海，李长庚.基于簇头功能分化的无线传感器网络成簇算法[J].传感技术学报，2015，28（2）：244?248.

CHEN Donghai， LI Changgeng. A function decomposition algorithms for cluster head for WSNs [J]. Chinese journal of sensors and actuators， 2015， 28（2）： 244?248.

[5] VURAN M C， AKAN O B， AKYILDIZ I F. Spatio?temporal correlation： theory and applications for wireless sensor networks [J]. Computer networks， 2004， 45（3）： 245?259.

[6] 徐晓斌，张光卫，孙其博，等.一种误差可控传输均衡的WSN数据融合算法[J].电子学报，2014，42（6）：1205?1209.

XU Xiaobin， ZHANG Guangwei， SUN Qibo， et al. Precision configurable data aggregation algorithm in WSNs [J]. Acta Electronica Sinica， 2014， 42（6）： 1205?1209.

[7] 宋三华.基于节点度?限制的数据融合树构建算法[J].传感技术学报，2018，31（1）：119?124.

SONG Sanhua. Degree?constrained?based data aggregation tree constructing algorithm in wireless sensor networks [J]. Chinese journal of sensors and actuators， 2018， 31（1）： 119?124.

[8] 黄海平，陈九天，王汝传，等.无线传感器网络中基于数据融合树的压缩感知算法[J].电子与信息学报，2014，36（10）：2364?2369.

HUANG Haiping， CHEN Jiutian， WANG Ruchuan， et al. Compressed sensing algorithm based on data fusion tree in wireless sensor networks [J]. Journal of electronics & information technology， 2014， 36（10）： 2364?2369.

[9] CHAO C M， HSIAO T Y. Design of structure?free and energy?balanced data aggregation in wireless sensor networks [J]. Journal of network and computer applications， 2014， 37： 229?239.

[10] 高翔，甘昕艳，秦川.基于信任评价的低能耗的数据聚融算法[J].计算机工程与设计，2018，39（4）：1047?1052.

GAO Xiang， GAN Xinyan， QIN Chuan. Trust evaluation based low consumption data fusaggregation algorithm for wireless sensor networks [J]. Computer engineering and design， 2018， 39（4）： 1047?1052.

[11] LIAO Y， QI H， LI W. Load?balanced clustering algorithm with distributed self?organization for wireless sensor networks [J]. IEEE sensors journal， 2013， 13（5）： 1498?1506.

[12] 许建，杨庚，陈正宇，等.基于二次独立集的数据融合调度算法[J].通信学报，2014，35（1）：62?71.

XU Jian， YANG Geng， CHEN Zhengyu， et al. Data aggregation scheduling algorithm based on twice maximum independent set [J]. Journal on communications， 2014， 35（1）： 62?71.