基于等概率路由模型的传感器网络负载均衡研究LoadBala

第32卷第5期电子与信息学报Vol.32No.52010年5月JournalofElectronics&InformationTechnologyMay2010基于等概率路由模型的传感器网络负载均衡研究解文斌鲜明陈永光(国防科技大学电子科学与工程学院长沙410073)摘要：无线传感器网络的能耗效率与流量负载分布密切相关。论文从微观角度研究了无线传感器网络的负载均衡问题。基于等概率路由模型，分析了拓扑传输结构对于感知数据流量的分流作用。根据分析结果，提出了多对一传输模式下任意节点负载密度的定义和算法。分析了节点的负载密度与传感器网络生命期的关系，进一步论证了在多对一的多跳传感器网络中不能实现完全的负载均衡，但是通过设计合理的拓扑结构可以实现准负载均衡。仿真结果说明，从微观角度得到的节点负载密度可以准确描述无线传感器网络的流量负载分布，由此得到的准负载均衡条件也能实现绝大多数节点的负载均衡。关键词：无线传感器网络；负载均衡；网络生命期；等概率路由中图分类号：TP393文献标识码：A文章编号：1009-5896(2010)05-1205-07DOI:10.3724/SP.J.1146.2009.00201LoadBalancingforWirelessSensorNetworksBasedonanEquiprobableRoutingModelXieWen-binXianMingChenYong-guang(SchoolofElectronicScienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073,China)Abstract:Theefficiencyofenergyconsumptioninwirelesssensornetworksiscloselyrelatedtothetrafficofeachnode.Inthispaper,theissueofloadbalancinginwirelesssensornetworksisresearchedonthemicroscopicscale.Basedonanequiprobableroutingmodel,therelationshipbetweentopologystructureanddatatrafficdistributionisestablished.Basedontheanalyticalresults,thedefinitionandthedistributedalgorithmofloaddensityofanynodeinmany-to-onesensornetworksareproposed.Basedonthefirstorderradiomodel,therelationshipbetweenloaddensityandnetworklifetimeisanalyzed.Inspiteofthefactthatcompleteloadbalancinginwirelesssensornetworkisunreachable,suboptimalloadbalancingispossibleifthetopologystructureiswell-designed.Simulationresultsshowthattheloaddistributionofwirelesssensornetworkscanbedescribedaccuratelybyloaddensity,andloadbalancingofmostnodesispossibleiftopologystructuremeetssuboptimalconditions.Keywords:Wirelesssensornetworks;Loadbalancing;Networklifetime;Equiprobablerouting1引言无线传感器网络的能耗效率与流量负载分布密切相关。多对一是无线传感器网络数据传输的一种典型结构[1]，具有独特的流量分布特点。在从源节点到sink节点的多对一传输中，只要不进行数据聚合，无论采用何种路由协议，都会使大量的数据拥挤到sink周围。某些中间节点除了发送自身的感知数据，还消耗大量的能量转发数据，导致某些节点的能量快速耗尽，出现“能量空洞”，从而影响整个网络的生命期。这种现象也称为“漏斗效应(funnelingeffect)”[2]，“sink邻居问题(sinkneighborhoodproblem)”[3]或“中心拥挤效应(crowdedcenter2009-02-20收到，2010-02-22改回通信作者：解文斌[e-mail])”[4]。文献[5]研究了由于设备故障和电池能量耗尽而引起的节点衰变(aging)效应，说明了节点到sink的跳数对于节点能耗和网络连通性具有重要影响。文献[6]假设节点均匀分布在一个半径为R的圆形区域内，给出了单路径和多路径路由机制下的节点流量负载公式。文献[7]在节点密集分布和理想的负载均衡昀短路径路由假设条件下，给出了当基站处于昀优位置时各个传感器节点的平均流量负载，通过解析表达式说明了数据流量迅速向基站集中的现象。通过改变数据的传输结构，文献[8-15]给出了解决负载不均衡问题的思路。文献[8,9]提出了一种节点非均匀分布的策略，以实现节点的次优能耗均衡。针对密集的多跳无线网络，文献[10-12]把负载均衡问题形式化为在所有源-目标节点对之间寻找昀小的标量报文量(流量负载)的连续曲线(路线)问1206电子与信息学报第32卷题，说明了可以通过单路径路由获得昀优的负载分布[10]。文献[13]在网络非常密集的约束条件下，模拟几何光学里的光线折射定律，从宏观角度研究了无线网络的昀优路由问题。文献[4]中通过把昀优的路由路径模拟为几何光学里的光线传播，给出了连续网络模型下流量负载的概率密度公式，得到了负载平衡的路由算法，但是计算难度很大。文献[14]针对1维的线性网络拓扑，提出了根据节点与sink之间的距离确定传输功率的方法。其中，文献[4,6,10-12]假设所有源-目标节点对均匀分布于给定圆形区域内，因此得到的是sink遍历该区域的平均负载分布。而文献[7]假设sink节点位于传感器网络的质心位置，得到的是特殊条件下多对一的流量负载分布。此外，文献[4-7,10-14]中都采用了文献[15]中引入的连续拓扑模式。该模式在网络密集条件下，用连续的流体代替网络连接和节点，从源节点到目标节点的昀短路径就成为连续的线段。通过把网络抽象为一个连续的空间，便于利用电磁学、几何光学等理论和微积分工具进行分析，因此该模式近年来被广泛应用。采用连续空间假设不需要考虑每一个节点的具体分布位置，忽略节点之间的拓扑结构，结果是对网络流量分布的宏观描述，可以得到距离sink越近的节点越容易快速耗尽能量的直观感受。然而，宏观描述的缺点是不够精确，当不满足节点密集分布的条件时，不能采用连续拓扑模式。而且，模拟电磁场和光学等方法所涉及的微积分方程的计算较为复杂，难以适应传感器网络实际应用的要求。本文在微观层面上研究了网络拓扑结构对于无线传感器网络数据流量的分流作用，以及由此导致的负载不均衡和能耗不均衡效应。基于等概率路由模型，分析了拓扑传输结构对于感知数据流量的分流作用。针对多对一的网络数据传输模式，提出了任意节点负载密度的定义和分布式算法。根据能耗模型分析了节点的负载密度与传感器网络生命期的关系。进一步论证了在多对一的多跳传感器网络中不能实现完全的负载均衡，但是通过设计合理的拓扑结构可以实现准负载均衡。昀后通过仿真实验说明了从微观角度得到的节点负载密度是有效的，可以准确描述无线传感器网络的流量负载分布，由此得到的准负载均衡条件也能实现绝大多数节点的负载均衡。本文提出的方法不需要对传感器节点的分布情况和密度进行任何假设，对于密集或稀疏分布都适用。2网络模型和假设假设无线传感器网络由N个随机分布的节点组成，用无向图(,)GVE表示，其中2VR⊂，表示欧氏平面上的节点集，2EV⊂表示边的集合，N=||V。假设所有节点具有相同的通信半径R，当且仅当节点u,v之间的距离(,)duvR≤时，边(,)uvE∈。本文中假设一种时间驱动的多对一的传感器网络数据传输场景，即所有传感器节点都能产生感知数据，每一轮次都参与数据传输过程。中继节点不对数据进行压缩或聚合，即不改变数据大小，也不产生计算能耗。采用等概率的路由模型，去除任何有偏好的路径选择因素，即认为每一条链路的指标都是相同的。这样从源节点到sink节点的路由开销只与跳数有关。对于任意节点，从直连的上层父节点集中任选一个转发数据，其代价和选择概率都是相同的。通过等概率选择昀小跳数路径，便于分析数据传输拓扑对节点流量分布的影响。实际上，文献[5-9]中也采用了等概率选择路由的隐含假设。实际上，在节点密集分布的假设下推导流量负载分布也隐含了采用昀短路径路由，如文献[4,6,7]。在从源节点到目标节点的多跳传输中，源节点的数据将沿一条曲折的路径流向目标节点。当网络变得越来越密的时候，这些曲折的路径将越来越接近直线，从而可以把网络视为一个连续的空间，源节点和目标节点之间沿一条直线进行通信[4]。所不同的是，在Adhoc网络中目标节点不是固定的，而无线传感器网络中的目标节点就是sink，执行的是多对一的多跳通信。3多对一网络的流量负载分析3.1任意节点的流量负载构成源-目标节点对之间的通信路径是由网络的拓扑结构决定的。如图1所示，在所有节点数据向sink流动的过程中，不同节点的负载差异仅取决于从子节点接收的数据。假设每一个节点在每一轮数据收集过程中产生Lbit数据，则节点u在每一轮需要传输的总流量为图1多对一的传感器网络数据收集拓扑第5期解文斌等：基于等概率路由模型的传感器网络负载均衡研究12071cuNcccuuuvvLLNLLLϕ=⎛⎞⎟⎜⎟⎜=+=⋅++⎟⎜⎟⎜⎟⎝⎠∑(1)其中1cuNcccuuvvLNLL==⋅+∑为节点u从其子节点集接收的流量，cuN为节点u的子节点数，cvL为子节点v从其子节点集接收的流量。在数据路由过程中，拓扑结构对于数据的分流具有重要作用。基于等概率路由模型，对于网络中的任意节点v，其父节点数为pvN，若以概率1/pvN随机选择父节点，则经过T轮后，节点v的数据将依概率p平均发送到pvN个上层节点，lim1Tp→∞→。节点v的父节点以同样的方式继续向上层节点分流数据，一直持续到所有数据都到达sink时。因此，网络中任意节点的流量负载就是从其子节点集中接收的数据加上自己产生的数据。经过T轮数据收集过程后，任意节点u的总流量负载为11()()()TTcuuuttTtLtLTΦϕ====+⋅∑∑(2)在等概率选择父节点的条件下，有1()lim()()TcuuTtvDuLtLTvξ→∞=∈=⋅⋅∑∑(3)其中()Du表示节点u所有子孙节点的集合，()uvξ表示节点v的流量依概率分配到节点u的部分流量。因此，网络中任意节点u在每一轮中的平均流量负载为()()lim1()uuuTvDuTLvTΦϕξ→∞∈⎛⎞⎟⎜⎟⎜==⋅+⎟⎜⎟⎜⎟⎝⎠∑(4)由N个传感器节点组成的传感器网络每一轮将产生LN⋅bit数据。因此，对于多对一传输的传感器网络，可以得到离散空间的节点负载密度。定义1节点的负载密度：对于采用多对一传输模式的网络，任意节点u的负载密度定义为()1()uuuvDuvLϕρξ∈==+∑(5)其物理意义是，若传感器节点在每一轮数据收集过程中产生1bit数据，则在每一轮新产生的1N×bit数据中，有uρbit数据是从节点u流向sink节点的。其中，有1bit是由节点u自己产生的，其他的()()uvDuvξ∈∑bit是由节点u的子孙节点通过节点u流向sink的。从式(5)可以看出，计算节点负载密度的关键是得到()()uvDuvξ∈∑。它是由多对一的拓扑传输结构决定的，