分布式融合算法在WSANs中的性能分析

伍昕宇，李才对，李亚秀，杨春曦

昆明理工大学化学工程学院，昆明 650500

分布式融合算法在WSANs中的性能分析

伍昕宇，李才对，李亚秀，杨春曦

昆明理工大学化学工程学院，昆明 650500

在无线传感器执行器中，执行器节点接收传感器节点传来的信息并执行相应的动作。为了满足执行器节点及时地采取行动，无线传感器执行器网络对时延有严格的限制。构建了一种一般性的分布式融合算法并与集中式融合算法比较。通过从网络传输时延、节点能量消耗、网络寿命、有效传输次数等方面分析了这种算法在无线传感器执行器网络中的特性。在三种典型拓扑结构下的仿真实验表明，在相同条件下，分布式融合算法比集中式融合算法具有更小的网络传输时延，更长的网络寿命，同时节点的能量消耗更加均匀。

无线传感器执行器网络；分布式融合；集中式融合

1 引言

无线传感器执行器网络[1]（Wireless Sensor and Actor Networks，WSANs）是由大量能量较少、计算能力有限的传感器节点和少量能量较多、计算能力较强的执行器节点组成的一个多跳自组织异构网络。与无线传感器网络不同的是，无线传感器执行器网络具有分布式检测、数据多跳传输和控制的功能，所以其研究的问题不仅是节能[2-3]、网络覆盖[4-5]、数据完整性[6]等，而且必须考虑数据的传输时延限制[7-9]。为了有效减小网络传输时延，通常采用分簇[10-12]的方法：以能量较多的执行器节点固定充当簇头，其他无线传感器节点围绕簇头进行数据采集与传输。

图1是一个无线传感器执行器网络结构图。在监控区域中，圆点代表能量有限、计算能力有限和通信范围有限的传感器节点，三角形代表能量较多、计算能力较强和通信范围较大的执行器节点。传感器节点与执行器节点自组织成为包含多条链路结构的簇状网络，并由能量多、计算能力强和通信范围大的执行器节点充当簇头。

无线传感器执行器网络工作时，大量分布在监控区域的传感器节点检测环境数据，并把数据沿链路传递直至执行器节点（即Sink节点）。执行器节点根据传感器节点检测到的数据并及时作出反应，从而达到控制的目的。

图1 WSANs网络模型

来自不同无线传感器节点的数据在传输过程中被叠加了大量干扰，甚至同一时刻采样的数据传输到执行器节点不完整。数据融合的目的在于删除冗余、无效、可信度差的数据，减少网络数据传输量，从而减少节点能量消耗，延长网络寿命。融合按照结构的不同，分为集中式融合和分布式融合。集中式融合是将所有信息进行一次融合计算完成，其优点是能够选择合适的融合算法进行最优融合。缺点是采集的数据受干扰影响较大，融合所需的计算能力较强，能量消耗较大，所需时间较长[13]；分布式融合把信息分散到传感器各自的处理器进行多次融合完成，其优点是各节点能量消耗较均匀，采集的数据就近融合，受干扰较少。缺点是节点能量和计算能力有限，不能采用较复杂的融合算法，同时因为采取局部融合的方法，导致不容易得到全局最优值。近年来，在数据融合策略方面已有大量研究[14-16]，但这些研究均未考虑到在WSANs中的应用特点。

为定量比较分布式融合算法与集中式融合算法在WSANs中的动态特性，本文采用MATLAB构建了一般性的分布式融合算法和集中式融合算法各一种，以三种典型的拓扑结构为对象，从网络传输时延、节点能量消耗、缓存位数、网络寿命和传输过程中的失败概率五个方面分析了两种融合算法在网络中的差异，为后续的WSANs融合算法研究奠定了基础。

2 理论基础

2.1 定义

（1）有效传输：所有节点同一个周期内采集的数据都成功发送至执行器节点，称为一次有效传输。

（2）有效时延：各个传感器节点在同一个周期Tm采集的所有数据，最后一包数据发送至执行器节点的周期为Tn，则时间间隔(Tn-Tm)称为有效时延。

（3）平均时延：在一段采样时间内，所有有效时延之和除以有效传输次数称为平均时延。

（4）网络寿命：网络中出现任意一个节点能量消耗完毕时的网络所经历的周期数为网络寿命。

（5）失败概率：由于不确定因素的影响，导致两个节点不能正常通信的随机概率（这里随机概率服从均匀分布）。

2.2 算法分析

（1）分布式融合

①每个采样周期T可以发送p轮数据（这里取p= 3），记为Ti1、Ti2和Ti3，其中周期数i=1，2，3，4…。

②周期Ti开始，Ti1时刻，各节点同时采集当前数据并放入缓存的第一位，上游节点首先发送第一位缓存中的数据至相邻的节点，与相邻节点中的数据融合后再发送至下游节点，依次进行至执行器节点，若其中某个节点中的数据没有发送成功，则放入当前节点的缓存。

③Ti2时刻，节点首先发送缓存中的数据至相邻的节点，发送和融合过程如Ti1时刻。若此节点缓存的第一位不为空，则发送第一位缓存中的数据，若此节点缓存的第一位为空，则发送下一位缓存中的数据，依次类推，若此节点缓存都为空，则不发送数据，若其中某个节点中的数据没有发送成功，则放入当前节点的缓存。

④Ti3时刻，重复Ti2时刻的过程，完毕后，周期Ti结束。

⑤周期Ti+1开始，循环上述过程至所有周期结束。

（2）集中式融合

①每个采样周期T可以发送z轮数据（这里取z= 3），记为Ti1、Ti2和Ti3，其中周期数i=1，2，3，4…。

②周期Ti开始，Ti1时刻，各节点同时采集当前数据并放入缓存的第一位，数据通过相邻节点依次发送第一位缓存中的数据至执行器节点，若其中某个节点中的数据没有发送成功，则放入当前节点的缓存。

③Ti2时刻，数据通过相邻节点依次发送缓存中的数据至执行器节点，发送过程如Ti1时刻。若此节点缓存的第一位不为空，则发送第一位缓存中的数据，若缓存的第一位为空，则发送下一位缓存中的数据，依次类推，若此节点缓存都为空，则不发送数据，若其中某个节点中的数据没有发送成功，则放入当前节点的缓存。

④Ti3时刻，重复Ti2时刻的过程，所有节点的数据都成功发送至执行器节点时进行集中式融合，周期Ti结束。

⑤周期Ti+1开始，循环上述过程至所有周期结束。

3 仿真比较

3.1 条件假设

（1）所有节点的初始状态相同，初始能量为E（执行器节点也不例外），传感器节点具有简单的数据融合功能，所有节点均不发生移动。

（2）若节点上游没有其他节点，则此节点只发送不接收数据，执行器节点只接收不发送数据。

（3）每个节点只与相邻节点通信，数据通过相邻节点发送至执行器节点，该节点拥有较强的计算能力和较大的存储空间。

（4）每一位缓存的容量正好存放一次传感器采集的数据，缓存采用后进先出的堆栈方式存取数据。

（5）为便于计算，忽略节点的唤醒和睡眠的时间延迟和能量消耗。

（6）为研究方便，取相邻节点间的数据传输失败概率相同，均服从均匀分布。

3.2 网络模型

本节以7个节点所组成的三种不同的拓扑结构作为网络模型，即：一字拓扑模型、复合拓扑模型和树形拓扑模型。数据按照箭头指向从左至右依次传递，如图2所示。

图2 三种拓扑模型示意图

3.3 能耗模型

一个典型的传感器节点由数据处理单元、微型传感器、电源和无线电通信单元组成。本文使用W.B. Heinzelman论文中的能耗模型[17]，如图3所示。

图3 能耗模型

传输l比特信息到距离d的节点，发送端消耗的能量为：

接收端消耗的能量为：

其中，电路消耗能量Eelec与数字编码、调制、滤波和信号传播情况有关。放大器消耗能量εfsd2或εmpd4取决于与接收器的距离和误码率。d0为临界距离。数据融合所需要的能量为EDA。

3.4 仿真参数

仿真各主要参数如表1所示。

表1 仿真参数表

3.5 仿真结果

本文采用MATLAB软件进行仿真，通过平均时延、节点能量消耗、网络寿命、有效传输次数等方面定量比较分布式融合算法和集中式融合算法在网络中的传输效果。

图4表示三种拓扑结构在节点发送5 000次数据且节点间具有相同失败概率0.4的条件下，缓存位数对分布式融合和集中式融合有效传输次数的影响。对于分布式融合，缓存位数较少时，一字拓扑结构的有效传输次数最小。但随着缓存位数的增大，三种拓扑模型的有效传输都趋于100%。对于集中式融合，树形拓扑模型和复合拓扑模型的有效传输次数有较大差异，这主要是因为树形拓扑模型的分支节点较多，在节点5处造成数据的丢失，从而降低了有效传输次数。随着缓存位数的增加，三种拓扑模型的有效传输趋向值也有较大差异。可见集中式融合的有效传输次数不仅与拓扑模型的链路长度有关，还受分支节点多少影响。

图4 有效传输次数随缓存位数变化比较图

图5表示三种拓扑结构在节点发送5 000次数据且节点缓存为10位的条件下，失败概率对于网络平均时延的影响。对于分布式融合，由于一字拓扑结构的链路长度的不同，故其平均时延远大于其他两种拓扑模型的平均时延。对于集中式融合，一字拓扑结构的链路长度依然最大，故其平均时延最大；同时，受分支节点数的影响，树形拓扑模型导致的平均时延大于复合拓扑模型。

图5 平均时延随失败概率变化比较图

图6表示三种拓扑结构在节点发送5 000次数据、节点缓存为4位且节点间的失败概率都为0.3的条件下，各节点剩余能量分布的情况。对于分布式融合，一字拓扑模型的每个节点只需与其相邻的前一节点数据进行融合，故节点2到节点6间的节点剩余能量分布非常均衡；树形拓扑模型的节点5需与节点1到节点4的数据进行融合，能量消耗最严重；对于复合拓扑模型，节点5和节点6都需要与两个节点的数据融合，能量消耗相近，节点4只需与节点3中数据融合，能量消耗少。对于集中式融合，无论是哪种拓扑模型，当节点需要转发的数据越多，该节点消耗的能量也越多。

图6 节点能量分布图

图7表示三种拓扑结构在节点发送5 000次数据且节点的缓存都为2位的条件下，失败概率对分布式融合和集中式融合有效传输次数的影响。对于分布式融合，随着失败概率在区间0.3～0.7内增长，三种拓扑模型的有效传输次数均大幅度减少。对于集中式融合，随着失败概率在区间0.2～0.5内增长，三种拓扑模型的有效传输次数也大幅度减少。这表明，在恶劣的环境下，分布式融合算法比集中式融合算法有更好的鲁棒性。

图7 有效传输次数随失败概率变化比较图

图8表示缓存位数和失败概率对网络寿命的影响，其中下面的曲面代表集中式融合算法的网络寿命，上面的曲面代表分布式融合算法的网络寿命。表面上看，对于集中式融合，随着失败概率的增加，网络的寿命也随之增加，但这是由于失败概率太大导致数据大量丢失使得节点能量消耗降低，实际意义不大。对于分布式融合，随着失败概率的增加，网络寿命大体上随之降低。在失败概率大于0.8时，曲面出现“翘尾”现象，其原因也是由于失败概率太大导致数据大量丢失使得节点消耗降低。在缓存为1、失败概率为0.8附近时，曲面出现“卷边”现象，这是因为在数据大量丢失的情况下，节点的数据无法发送至相邻节点，相邻节点的数据在没有融合时无法发送，后续节点也无法发送，网络寿命获得了“暂时性”提高，需要指出的是，这种网络寿命的提高是以数据的大量丢失为代价的。

图8 网络寿命比较图

4 结束语

为了比较分布式融合算法和集中式融合算法在无线传感器执行器网络的传输效果，本文构建了一种一般性的分布式融合算法，其核心思想是把采集的数据分散到各个节点进行融合，从而减少了网络的传输量，降低了节点能量消耗，延长了网络寿命。通过对分布式融合算法和集中式融合算法在三种不同的网络拓扑模型下进行仿真实验，得出如下结论：

（1）同等条件下，分布式融合算法的有效传输次数明显高于集中式融合的有效传输。

（2）分布式融合算法使节点能量消耗更加平均，从而延长了网络寿命。

（3）在失败概率较大的情况下，分布式融合算法的平均时延远小于集中式融合的平均时延。

（4）同等条件下，分布式融合算法的有效传输次数和平均时延主要受到链路长度的影响，而集中式融合算法的有效传输次数和平均时延与链路长度和分支节点数两个因素相关。

（5）在分布式融合算法下，节点能量消耗的差异是由于融合数据包数量的不同，而在集中式融合算法下，节点能量消耗的差异是由于转发数据包的不同。

（6）在实际应用中，每个簇单元应尽量减少终端节点到执行器节点间链路过长和分支节点数过多的情况出现。

总体上看，分布式融合算法比集中式融合算法具有更小的网络传输时延，更长的网络寿命，同时节点的能量消耗更加均匀。综合以上几点，分布式融合算法更加适用于WSANs。

[1]Akyildiz I F，Kasimoglu I H.W ireless sensor and actor networks：research challenges[J].Ad Hoc Netw orks，2004，2（4）：351-367.

[2]李方敏，徐文君，刘新华，等.无限传感器/执行器网络中能量有效的实时分簇路由协议[J].计算机研究与发展，2008，45（1）：26-33.

[3]Sankarasubramaniam Y，Akyildiz I F，M cLaughlin S W. Energy efficiency based packet size optimization in wireless sensor networks[C]//2003 IEEE International Workshop on Sensor Network Protocols and Applications，2003：1-8.

[4]任彦，张思东，张宏科.无限传感器网络中覆盖控制理论与算法[J].软件学报，2006，17（3）：422-433.

[5]蒋杰，方力，张鹤颖，等.无线传感器网络最小连通覆盖问题求解算法[J].软件学报，2006，17（2）：175-184.

[6]曹远福，孙星明，王保卫，等.基于关联数字水印的无线传感器网络数据完整性保护[J].计算机研究与发展，2009，46 （Suppl）：71-79.

[7]杨春曦，关治洪，黄剑，等.时延加权融合技术的无线传感器网络控制[J].控制理论与应用，2011，28（2）：157-165.

[8]杨春曦，黄剑，张金龙.具有马尔科夫时变时延的REM拥塞算法局部稳定性[J].华中科技大学学报，2010，38（6）：19-22.

[9]Gungor V C.Real-time and reliable communication in wireless sensor and actor networks[D].Georgia：School of Electrical and Computing Engineering，2007.

[10]戴志诚，冉启月，汪秉文.带执行器节点的无线传感器网络的分簇算法[J].计算机工程与应用，2007，43（10）：145-147.

[11]陈闻杰，陈迅，高丽强，等.无线传感网网络成簇算法研究[J].小型微型计算机系统，2008，29（2）：219-225.

[12]沈波，张世永，钟亦平.无线传感器网络分簇路由协议[J].软件学报，2006，17（7）：1588-1600.

[13]叶宁，王汝传.无线传感器网络数据融合模型研究[J].计算机科学，2006，33（6）：58-60.

[14]尹慧琳，王磊，冯占军.无线传感器网络节点分布式信息融合算法研究[J].计算机工程与应用，2007，43（17）：18-20.

[15]黄旗明，刘笑.基于博弈理论的无线传感器网络融合路由研究[J].传感器学报，2008，21（11）：1905-1908.

[16]王天荆，杨震，胡海峰.基于遗传算法的无线传感器网络自适应数据融合路由算法[J].电子与信息学报，2007，29 （9）：2244-2247.

[17]Heinzelman W B，Chandrakasan A P，Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1（4）：660-670.

WU Xinyu,LI Caidui,LI Yaxiu,YANG Chunxi

Faculty of Chemical Engineering,Kunming University of Science and Technology,Kunming 650500,China

Wireless Sensor and Actor Networks（WSANs）employ actor nodes that can collect data from sensors and perform application specific actions.To meet the demand of taking actions promptly,minimizing the time of gathering data is desirable.A general distributed fusion algorithm is proposed to com pare with a general centralized fusion algorithm. This paper analyzes its features in transmission delay,node energy consumption,network lifetime and the probability of transmission failure.The simulation results on three different typical topological structures indicate that the distributed fusion algorithm can achieve less transmission delay,longer network lifetime and distribute energy dissipation more evenly throughout the sensors than the centralized fusion algorithm under the same conditions.

wireless sensor and actor networks;distributed fusion;centralized fusion

A

TP393

10.3778/j.issn.1002-8331.1208-0484

WU Xinyu,LI Caidui,LI Yaxiu,et al.Performance analysis of distributed fusion algorithm in W SANs.Computer Engineering and Applications,2014,50（16）：118-122.

国家自然科学基金（No.610040330）；云南省自然科学基金（No.2010ZC035）。

伍昕宇（1989—），男，硕士研究生，主要研究方向为无线传感器执行器网络；杨春曦（1976—），通讯作者，男，博士，副教授，主要研究方向为网络控制系统，鲁棒控制，无线传感器网络。E-mail：ycx@kmust.edu.cn

2012-09-05

2012-10-26

1002-8331（2014）16-0118-05

CNKI网络优先出版：2012-11-21，http://www.cnki.net/kcm s/detail/11.2127.TP.20121121.1103.043.htm l