—148—无线传感器网络数据融合路由算法的改进周琴1,戴佳筑1,蒋红2(1.上海大学计算机工程与科学学院,上海200072;2.贵州广播电视大学计算中心,贵阳550004摘要:无线传感器网络能量有限,数据融合能通过合并冗余数据减少传输数据量,但其本身的代价不可忽略。针对该问题,研究数据融合代价和数据传输代价对数据融合路由的影响,在基于决策数据融合技术AFST中,对直传数据采用动态最短路径(DSPT算法,动态识别网络环境和数据特征变化,以最小的代价调整路由。实验与分析结果表明,当网络结构发生变化时,DSPT算法比SPT算法效率更高、更节能。关键词:无线传感器网络;数据融合;动态最短路径树;路由ImprovementofRoutingAlgorithmforDataAggregationinWirelessSensorNetworkZHOUQin1,DAI激a-zhu1,JIANGHong2(1.SchoolofComputerEngineeringandScience,ShanghaiUniversity,Shanghai200072,China;2.ComputingCenter,GuizhouRadioandTVUniversity,Guiyang550004,China【Abstract】EnergyislimitedinWirelessSensorNetwork(WSN,anddataaggregationisusedinWSNtosaveenergybyaggregatingredundantdatatoreducethedatasizebeingtransmitted.Buttheaggregationcostitselfisnon-neglectable.FocusingonminimizingthetotalenergycostoftheWSN,thispaperimprovestheAdaptiveFusionSteinerTree(AFSTbysubstitutingtheDynamicShortestPathTree(DSPTroutingalgorithmfortheShortestPathTree(SPTroutingalgorithmtoadapttothechangesofnetworkenvironmentanddatasize.ExperimentalandanalysisresultsshowthatusingtheDSPTroutingalgorithmfordirectlyrelayeddatahasabetterperformanceinenergysavingandefficiencythanSPTroutingalgorithmwhendatasizechanges.【Keywords】WSN;dataaggregation;DynamicShortestPathTree(DSPT;routing计算机工程ComputerEngineering第36卷第19期Vol.36No.192010年10月October2010·网络与通信·:1000—3428(201019—0148—03文献标识码:A:TP3931概述由于无线传感器网络中节点的能量十分有限,因此在设计各种网络协议时必须考虑节能。采用网内数据处理技术是降低能耗的重要手段,而数据融合与数据路由相结合是实现网内数据处理的重要方法[1-3]。数据融合能减少数据传输量,降低网络负载,但传统的数据融合方法只考虑了传输代价,忽略了融合过程本身的能量代价。在实际网络中,数据融合的代价有时会大于因融合而节省的传输代价,此时从节能角度而言数据融合失去意义。文献[3]提出一种基于决策数据融合的路由算法AFST(AdaptiveFusionSteinerTree,它通过权衡融合代价与传输代价,动态决定数据相遇点是否进行数据融合,可以进一步减少网络的能耗代价,延长系统的生命周期。但该方法不适合网络结构变化快的传感器网络,因为它没有考虑网络结构发生变化的情况,包括每条链路上的融合代价和传输代价是可变的、节点的分布是随机的、数据间相关性的变化导致融合后数据包的大小变化等,此时,当数据不融合而沿原最短路径直传给sink节点的路径就未必是真正的最短路径了,会导致能量浪费。针对上述问题,本文提出新的动态最短路径算法(DynamicShortestPathTree,DSPT,只对发生变化而受影响的节点重新计算最短路径,不仅可以适应网络结构的动态变化,而且能将算法最优化。当网络拓扑很大时,可以极大减少计算量,比原来算法中SPT路由算法更能适应网络结构变化,且更节能。2预备知识2.1网络模型和能量模型无线传感器网络用图表示,其中,V表示所有节点的集合;E表示所有节点间可以通信链路的集合。信息源点集合SV,⊂包含k个传感器节点,它们将以反向组播树的形式周期性地向sinktV∈报告采集到的数据。从每个节点v流出的数据量大小用(wv表示。每条边(,euv=,u为起点,v为终点,边的权值((wewu=。传输代价与每个节点流出的数据量有关,融合代价与每个节点流入的数据量有关。每条边上的单位传输代价用(ce表示,单位融合代价用(qe表示,则边e上的传输代价为(te=((wece。如果在节点v对u、v的数据进行融合,v点的数据量在融合前后会改变,以i(wv和(wv分别表示数据融合前后节点v的数据量。uvx∈0,1}表示边(,euv=上是否进行数据融合(1融合,0不...