基于分簇的无线多媒体传感器网络数据聚合方案研究

张军强 王汝传 黄海平



基于分簇的无线多媒体传感器网络数据聚合方案研究

张军强①④王汝传*①②③黄海平①②③

①(南京邮电大学计算机学院 南京 210003)②(江苏省无线传感网高技术研究重点实验室 南京 210003)③(宽带无线通信与传感网技术教育部重点实验室 南京 210003)④(南京工业大学信息学院 南京 210009)

该文提出了一种基于分簇的无线多媒体传感器网络(WMSNs)数据聚合方案(Cluster-based Data Aggregation Algorithm, CDAA)。利用新的分簇方法和数据聚合策略，CDAA可以有效延长网络生命期。根据多媒体节点数据采集的方向性和节点剩余能耗，该文提出新的无线多媒体传感器网络的分簇方法，并基于该分簇方法进行网内多媒体数据聚合。仿真结果表明，该方法能够有效减少冗余数据的传送，与LEACH, PEGASIS等传统WSNs路由协议和针对WMSNs的AntSensNet协议相比，在能耗均衡和节能方面表现出更好的性能。

无线多媒体传感器网络(WMSNs)；分簇；数据聚合；网络生命期

1 引言

无线传感器网络(WSNs)中基于分簇的路由协议设计具有扩展性好，易于实现网内数据融合等特点。分簇路由协议将无线传感器网络划分为若干簇，每个簇由一个簇头节点和多个簇内成员组成，簇内成员负责采集数据，而簇头节点负责管理簇内成员节点，并进行簇内节点信息的采集、融合及转发。低功耗自适应分层算法(LEACH)[1]是无线传感器网络中经典的分层协议之一，其基本思想是周期性等概率得随机选择簇头，使网络中节点的能量消耗相对均衡，从而延长网络生命期。但是，LEACH协议中簇头是随机选取的，难以保证簇头在网络中的均匀分布，且没有考虑节点的剩余能量，也没有对簇内数据进行聚合或融合。能量高效的数据采集协议(PEGASIS)[2]是一种典型的链状结构的路由协议，根据节点的地理位置形成一条相邻节点间距离最短的链。与LEACH协议相比，减少了在簇重构过程中所产生的开销，降低了能量的消耗，提高了网络的生存期。其缺点在于簇首节点失效会导致路由失败，且成链算法要求知道其它节点位置，也增加了开销。LEACH协议关注网络的最后节点死亡时间(Last Node Dies, LND)，一些稳定选举协议(Stable Election Protocol, SEP)关注初始节点死亡时间(First Node Dies, FND)，文献[3]综合最后节点死亡时间和初始节点死亡时间，提出了一种基于进化算法的节能路由协议，期望在网络的稳定性和网络的生命期间取得平衡。以地理位置信息为辅助的路由算法(GAF)[4]将整个区域划分为若干个格(grid)，其大小须保证相邻格子中任何一对节点可直接通信。在每个格子中只选择一个节点作为当前活动节点，而其它节点则进入睡眠状态。但GAF算法没有考虑网络覆盖，并且要解决等价节点的确定等问题。考虑到无线多媒体传感器网络(WMSNs)具有传输数据量大，同具体应用相关的服务质量(QoS)保障要求等特点，传统WSNs路由协议不一定适合WMSNs网络。文献[5]提出了支持QoS服务的基于蚁群算法的服务感知路由协议(ASAR)，针对不同类型的业务，选择合适的路由以满足相应的QoS要求，从而提高了网络性能，其设计目标主要是适应网络的动态变化及支持多参数的QoS路由。文献[6]提出了基于地理位置的多路径传输协议(TPGF)，可以找到多条路径来传输数据，能够避免网络能耗不均的问题，提供了数据传输时绕开空洞的方法，找到时延最小的最短路径。文献[7]针对WMSNs网络节能与QoS感知问题，提出了能量高效的多媒体路由协议(PEMuR)。PEMuR协议结合了能量感知的分层路由协议与智能化的数据包调度算法，实现了网络的负载均衡，减少了视频数据传输率。文献[8]提出基于蚁群算法的多QoS路由保障协议(AntSensNet)，该算法对网络进行分层后，通过建立多QoS参数的数学模型，利用蚁群算法找出目标函数值最大的路径。AntSensNet可以满足多类型QoS服务，提高网络利用率，实现较好的网络覆盖。文献[5-8]对于多类型QoS服务进行了研究，但未对网内数据聚合进行充分讨论。

传统WSNs节点感知模型主要为全向感知模型(isotropic sensing model)，即节点的感知范围是一个以节点为圆心，感知距离为半径的圆域[9]。有向感知模型是WMSNs网络中一种典型的感知模型，如视频传感器、超声波传感器和红外传感器等，其感知能力局限于某个视角范围(Field of View, FoV)。现有的路由协议分簇方法大多基于全向感知模型，针对WMSNs网络的有向感知模型需要设计新的分簇方法。

对于WMSNs网络，由于图像或视频的数据量大，且数据间往往具有一定的相关性，因此，在传输数据时，应首先进行网内数据处理，消除冗余信息，即进行数据聚合。数据聚合包括3方面问题，即聚合点的选择，聚合时机的选择和聚合策略[10]。文献[11]提出了一种基于估计代价的数据聚合树生成算法，在建立从事件区域源节点到sink节点数据聚合路径时，中间节点使用估计代价来决定下一个聚合节点。文献[12]在保证网络覆盖的前提下，通过激活网络中尽可能少的节点来最小化覆盖重叠区域，以减少WMSNs网络的冗余数据。文献[13]提出了一种基于分簇的无线传感器网络聚合策略，以节省能量消耗和延长网络寿命。文献[14]使用数据聚合的方法来减少数据的时空相关性。将数据聚合的决策置于网络层和数据链路层之间，不需要修改网络层或MAC层协议，从而减少了传输时延。文献[15]为了减少WMSNs网络中的数据传输，提出了节能的数据压缩方法，以延长网络生命期。文献[16]提出了基于分簇的无线传感器网络数据汇聚传送协议，通过均衡能耗的分簇方法及数据预测传送机制，减少数据传输量。文献[10-16]对网内数据聚合进行了研究，但未对WMSNs网络中节点感知的方向性和同一监测区域内数据的相关性进行讨论。

本文内容组织如下：第2节对网络模型进行描述并提出问题；第3节给出基于分簇的数据聚合算法(CDAA)的分簇方法及数据聚合方法的详细设计；第4节对算法性能进行分析与模拟验证；最后总结全文。

2 网络模型和问题描述

2.1 网络模型

(1)节点采用有向感知模型，如图1(a)所示。每个节点的感知区域是以节点为圆心，最大感知半径为，感知视角为的扇形。

(2)网络节点分布模型为均匀分布。

(3)节点独立工作，即每个节点的感知范围和感知任务不依赖其它节点。

(4)各节点可获知其地理位置和感知方向信息，感知方向不可调。

(5)所有节点是同构的，具有相同的初始能量。

(7)任意节点的通信范围覆盖其所在监测区域及相邻监测区域。

(8)各个节点周期性采集数据，并对采集到的数据进行处理以决定是否转发该数据；簇头收到各节点数据后根据需要来决定是否进行融合处理及转发。

定义3 信息熵[11]：香农定义信息的数学期望为信息熵，即信源的平均信息量，定义式如式(2)。

相对信息熵表现了两组概率分布之间的差异程度，对于两组不同的概率分布和，计算其相对信息熵以及，这两个值越小表明两组概率分布越近似，即数据冗余则越大。当 时，两组概率分布完全相等。

2.2 问题描述

如前所述，传统的WSNs网络分簇方法大多针对全向感知模型，而WMSNs是有向感知模型，多媒体节点数据采集的方向性强，有些传感节点的物理位置虽然靠近，但采集数据可能相差很大，为了使后续处理中簇内的数据相关性强且聚合策略有效，这样的节点并不适宜划为同一分簇，需要设计新的分簇方法。

在WMSNs网络中，设计分簇算法应考虑以下问题：

(1)使用分布式的分簇算法，以节省网络能耗，提高网络可扩展性。

(2)应考虑多媒体传感节点的有向性，增强簇内感知数据的相关性。

(3)为了实现节点能耗的均衡，网络中簇头分布应尽可能均匀，否则会造成某些节点能量消耗过快，导致感知空洞。

(4)按照传感器网络的具体应用与QoS保障要求，根据感知数据在时间或空间上的相关性进行数据聚合与融合，减少冗余数据的传送。

当前，大多数无线传感器网络的分簇算法针对全向感知模型，对多媒体传感节点的有向性及感知数据的相关性涉及较少。根据多媒体传感节点的有向性和感知数据的相关性以及节点的能耗均衡，本文提出了一种新的分簇算法，并以此为基础提出了一种网内数据聚合方案。

3 基于分簇的WMSNs网络数据聚合方案

3.1 计算节点覆盖面积进行分簇

(1)整个监测区域内重点监测目标或区域的设置；每个虚拟监测区域应当包含一个或几个重点监测目标或区域。

图2 虚拟监测区域划分

(2)节点的个数及位置分布情况；每个虚拟监测区域应当包含若干个节点。

(3)节点的有效传感半径；虚拟监测区域的个数设置与节点的有效传感半径成反比，节点的有效传感半径越大，虚拟监测区域的个数设置应当越少，反之亦然。

(4)节点的通信半径；同一虚拟监测区域内任意两个节点之间应可靠通信，相邻虚拟监测区域内任意两个节点之间应可靠通信。

图3 节点覆盖面积示意图

3.2 簇头选择

在基于分簇的无线传感器网络中，簇头的能耗远大于一般节点，在簇头选举阶段，应考虑节点的剩余能量，选举剩余能量多的节点作为簇头节点。

本算法采用与LEACH协议相同的能量衰减模型。根据文献[1]可知，发送数据和接收数据的无线通信模型为

3.3 数据聚合方案

对于WMSNs网络，由于图像或视频的采集数据量大，并且某些节点的感知数据相关性强，因此，在数据采集的过程中将每个节点的感知数据全部传输是不适宜和不必要的。大数据量的传输使整个网络消耗过多能量，导致网络生命期缩短。采集数据应首先进行网内数据处理，消除冗余信息。数据聚合是指利用传感器节点的本地处理能力，对采集到的或接收到的多个数据进行网内处理，消除冗余信息，减少数据传输量，减小分组冲突概率，如图4所示[10]。

图4 数据聚合示意图

在多媒体节点采集数据时，同一节点的感知数据通常是时间相关的。如果不同节点的传感域存在重叠，则其采集的数据具有一定的空间相关性。

在CDAA协议中，根据节点角色不同分别进行如下的数据聚合处理。

(3)对于簇头节点，当其收到簇内成员发送的数据时，若该数据属于高优先级，则立即发送，否则等到簇内所有节点数据到达后，按照节点间相关度对节点数据进行融合后再发送。

4 仿真实验

网络生命期指的是网络开始运行到第1个节点死亡之间的时间长度[17]。从图5可以看出，当节点个数为100时，CDAA协议的网络生命期比PEGASIS和LEACH分别提高了52%和154%，比AntSensNet提高了8%。当节点个数为200时，CDAA协议的网络生命期比PEGASIS和LEACH分别提高了41%和124%，比AntSensNet提高了11%。对比4种算法的生存轮数，CDAA明显优于PEGASIS协议和LEACH协议，比AntSensNet协议略高。相比传统的WSNs网络，WMSNs的生存轮数要少很多，主要原因是WMSNs网络中的图像数据量大，发送的次数多，能量的消耗大，因此节点的生存轮数较少。在网络节点总数为100，节点的死亡率为50%时，随机抽取15组节点进行剩余能量数据对比，10次实验结果的平均值如表1所示。

表1 4种算法的剩余能量对比(J)

表1中，CDAA算法的剩余能量的标准差约为0.65，剩余能耗为40.4 J，而PEGASIS协议和LEACH协议的剩余能量的标准差约为0.8和0.98，剩余能耗分别为30.9 J和26.1 J, AntSensNet协议的剩余能耗为32 J，标准差为0.64。表1表明，CDAA算法在均衡能耗方面要优于PEGASIS协议和LEACH协议，同AntSensNet协议相当，但在节能方面要优于AntSensNet。

本节在其它实验参数不变，只改变虚拟监测单元设置的情况下对CDAA协议进行模拟仿真。监测区域的设置分为3种情形：

(1)整个监测范围划分为16个虚拟监测单元，每个区域的范围为50 m×50 m。

(2)整个监测范围划分为25个虚拟监测单元，每个区域的范围40 m×40 m。

(3)整个监测范围划分为40个虚拟监测单元，每个区域的范围20 m×50 m。

实验仿真过程进行10次，取其平均值作为实验结果，如图6所示。从图6中可以看出，虚拟监测单元为16时，总体性能最好。监测单元数增加到25时，网络性能稍有下降。当监测单元数增至40时，网络性能下降明显。监测单元数增加至40时，同一监测区域内节点数变小，使得监测区域内数据冗余度降低，同一簇内数据相关性减弱，数据融合操作得不到充分体现，导致网络性能降低。监测单元的设置同网络内节点的个数、分布、覆盖范围也有密切联系，在进行监测单元设置时，应结合具体应用，综合考虑上述因素，进行合理的监测单元设置。

以上分析可以看出，本文提出的基于分簇的数据聚合方案的在能耗均衡和节能方面较传统的WSNs网络协议PEGASIS和LEACH有明显的改进，略优于AntSensNet协议。CDAA协议中的分簇方法和数据聚合方案使得网络节点能耗分布均匀，同一簇内数据相关性增强，通过对数据传输进行优化，能够减少冗余数据的发送，显著减少网络平均能耗。

5 结束语

在WMSNs网络信息收集过程中，节点之间采集的数据通常存在冗余，大量数据的传输使整个网络消耗了过多能量，缩短了网络生命期。本文提出了新的分簇方法与数据聚合方案，分簇方法平衡了节点能耗，增强了簇内数据相关性，并在此基础上，通过数据聚合减少了冗余数据的传输，延长了网络寿命。理论分析与仿真实验证明了CDAA协议具有良好的性能。

下一步的工作重点是在考虑网络节点非均匀分布模型下，完善分簇算法，使得网络中的分簇更合理；考虑网络的全覆盖问题；研究在多媒体节点的采集方向可调及存在障碍物的情况下，如何进行分簇与数据聚合；并根据网络的具体应用与QoS要求，采用合适的数据聚合策略，减少数据聚合导致的延迟，提高通信效率。

图5 网络生命期

图6 虚拟监测单元对网络生命期的影响

[1] Heinzelman W B, Chandrakasan A P, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]., 2002, 1(4): 660-760.

[2] Lindsey S and Raghavendra C S. PEGASIS: power efficient gathering in sensor information system[C]. Proceedings of the IEEE Aerospace Conference, Montana, USA, 2002: 1125-1130.

[3] Khalil Enan A and Attea Bara’a A. Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks[J].2011, 1(4): 195-203.

[4] Xu Y, Heidemann J, and Estrin D. Geography-informed energy conservation for ad hoc routing[C]. Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, Rome, Italy, 2001: 70-84.

[5] Sun Yan, Ma Hua-dong, Liu Liang,.. ASAR: an ant-based service-aware routing algorithm for multimedia sensor networks[J]., 2008, 3(1): 25-33.

[6] Shu Lei, Zhang Yan, Yang L T,.. Geographic routing in wireless multimedia sensor networks[C]. Proceedings of Second International Conference on Future Generation Communication and Networking, FGGN’08, Hainan Island, China, 2008: 68-73.

[7] Kandris D, Tsagkaropoulos M, and Pllitis I. Energy efficient and perceived QoS aware video routing over wireless multimedia sensor networks[J]., 2011, 9(4): 591-607.

[8] Cobo L, Quintero A, and Pierre S. Ant-based routing for wireless multimedia sensor networks using multiple QoS metrics[J]., 2010, 54(17): 2991-3010.

[9] 马华东, 陶丹. 多媒体传感器网络及其研究进展[J]. 软件学报, 2006, 17(9): 2013-2028. Ma Hua-dong and Tao Dan. Multimedia sensor network and its research progresses[J]., 2006, 17(9): 2013-2028.

[10] 于宏毅, 李欧, 张效义. 无线传感器网络理论、技术与实现[M]. 北京: 国防工业出版社, 2010: 190-203.

[11] 叶宁, 王汝传. 传感器网络中一种基于估计代价的数据聚合树生成算法[J]. 电子学报, 2007, 35(5): 806-810. Ye Ning and Wang Ru-chuan. A tree formation algorithm for data aggregation based on estimate cost in sensor networks [J]., 2007, 35(5): 806-810.

[12] Newella A and Akkaya K. Distributed collaborative camera actuation for redundant data elimination in wireless multimedia sensor networks[J].2011, 9(4): 514-527.

[13] 张强, 卢潇, 崔晓臣. 基于分簇的无线传感器网络数据聚合方案研究[J]. 传感技术学报, 2010, 23(12): 1778-1782. Zhang Qiang, Lu Xiao, and Cui Xiao-chen. Research on the scheme of data aggregation based on clustering for wireless sensor networks[J].. 2010, 23(12): 1778-1782.

[14] He T, Blum B M, Stankovic J A,AIDA: Adaptive application independent data aggregation in wireless sensor networks[J]., 2004, 3(2): 426-457.

[15] Sun En-yan, Shen Xuan-jing, and Chen Hai-peng. A low energy image compression and transmission in wireless multimedia sensor networks[J].2011, 15: 3604-3610.

[16] 杨军, 张德运, 张云翼, 等. 基于分簇的无线传感器网络数据汇聚传送协议[J]. 软件学报, 2010, 21(5): 1127-1136. Yang Jun, Zhang De-yun, ZhangYun-yi,.. Cluster-based data aggregation and transmission protocol for wireless sensor networks[J]., 2010, 21(5): 1127-1136.

[17] Chang J H and Tassiulad L. Maximum lifetime routing in wireless sensor networks[J]., 2004, 12(4): 609-619.

张军强： 男，1976年生，博士生，讲师，研究方向为无线传感器网络、数据融合.

王汝传： 男，1943年生，教授，博士生导师，主要研究方向为无线传感器网络、计算机软件、计算机网络、信息安全、移动代理等.

黄海平： 男，1981年生，博士，副教授，硕士生导师，研究方向为无线传感器网络、多媒体传感器网络、物联网和信息安全.

Research on Cluster-based Data Aggregation for Wireless Multimedia Sensor Networks

Zhang Jun-qiang①④Wang Ru-chuan①②③Huang Hai-ping①②③

①(,210003,)②(,210003)③(,210003,)④(,210009,)

A Cluster-based Data Aggregation Algorithm (CDAA) for Wireless Multimedia Sensor Networks (WMSNs) is proposed. CDAA extends effectively the network life cycle by a new clustering method and a data aggregation scheme based on the clustering method. According to the orientation feature and the residual energy of an individual multimedia sensor node, a new clustering method is proposed. Furthermore, a scheme of data aggregation is applied based on the clustering method. Compared with LEACH, PEGASIS and AntSensNet protocols, simulation results show that CDAA can decrease the number of data transmission in WMSNs, balance energy consumption and prolong the networks lifetime.

Wireless Multimedia Sensor Networks (WMSNs); Cluster; Data aggregation; Network lifetime

TP393

A

1009-5896(2014)01-0008-07

10.3724/SP.J.1146.2012.00933

2012-07-19收到，2013-10-08改回

国家自然科学基金(61170065, 61202355)，江苏省自然科学基金(BK2012436)，江苏省科技支撑计划项目(BE2010197, BE2011844)，江苏省属高校自然科学研究重大项目(12KJA520002)，高校科研成果产业化推进工程项目(JHB2012-7)和江苏高校科技创新计划项目 (CXZZ12_0479)资助课题

王汝传 wangrc@njupt.edu.cn