无线传感器网络最大生命期聚合树路由算法*

薛 明， 高德民

(1.南京邮电大学 计算机学院，江苏 南京 210003;

2.南京林业大学 信息科学技术学院，江苏 南京 210037)

0 引 言

无线传感器网络生命期通常被定义为最先因为电池能量耗尽而失效的传感器节点的生命期[1]。网络最大生命期问题可以被归结为一棵最小Steiner生成树的问题[2]，其中, MEGA(minimum energy gathering algorithm)[3]是基于最小功率生成树模型，算法通过编码树选择数据融合点，采用了有向图中的最短生成树获取问题的解。为达到负载均衡，可以将负载过重节点的能耗因素均衡到其它节点上以达到延长节点寿命的目的。LEACH算法[4]利用节点周期性轮流担任簇头策略，将节点的数据集中到邻近的簇头进行融合转发，虽然没有考虑功率调节作用，但是使全簇节点能耗消耗均衡。在以网络生命期为最优化模型中，根据数据能耗限制和数据流量不变性建立以生命期为最优值的线性规划模型[1]得到广泛应用，将网络最小能耗作为次优化因素[5]，既考虑了生命期问题，也考虑了网络能耗因素。该类模型通常是基于最优化理论模型，最终可以收敛到网络生命期的上界。文献[6,7]在多物流线性规划模型上提出一个启发式算法，从节点容量限制角度考虑数据流在节点处汇聚情况，通过数据流权函数模型，网络流延权函数梯度层向下游转发，节点可以实现数据转发最大化。在数据融合算法中，MLR算法[8]采用地理位置路由，数据被分类为原始数据和融合数据，2种数据都按照一定比例被分发到邻居节点，并通过最优化方法对最优比例进行求解以最大化网络生命期。该类算法可以平衡节点能量消耗，将负载过重节点能耗均衡到整个网络中，延长网络的生命期。研究实验表明:上述路由算法在一定程度提高了无线传感器网络的传输性能，但当网络规模不断扩大和传感器的分布更加复杂时，传感器节点有限的计算能力远不能满足复杂路由计算的需求。

本文根据能量等限制条件建立线性规划模型，考虑到网络最大生命期是NP难问题，将网络最大生命期问题转化为网络最小归一化负载问题，建立一棵最优网络归一化负载数据融合树，数据以较低能耗延融合树向基站转发，最终实现网络生命期最大化。

1 系统模型

1.1 系统模型

网络被抽象为一个无向图G(V,A)，其中，V表示节点和基站的集合，A表示链路集合。节点i∈V的邻居节点集合记为Si，链路集合为{(i,j)∈A|i,j∈V,j∈Si}。假设节点i平均在t时间内产生的数据字节数为Gt，产生速率为Gi=Gt/t，在每隔1/Gi时间内产生一个数据字节，假设一个数据包的大小为k个字节，新字节被附在数据包末端以不大于包容量被传送。时间间隔为τ=k/Gi，本文以τ作为系统的单位时间。

1.2 问题描述

假设网络生命期为Tτ，如果τ作为网络系统单位时间，网络生命期可以看作为T,T为所有节点的最小生命期,则节点i在T时间内的能量消耗不会超过当前能量Ei

(1)

源节点s发送到基站的数据经过边(i,j)的数据量为fs(i,j)，本文为网络中每一个s-t通信建立线性规划数学模型为

maxT

∀i=1,2,…,nandi≠t,

0≤fs(i,j)≤U(i,j),

∀i=1,2,…,nand ∀j=1,2,…,n,t,

(2)

其中，f(i,k)表示节点i在T时间内发送给下游节点的数据流总量。

式(2)中条件1表示节点i的能量消耗也不会超过当前能量E，条件2表示源节点转发的流量等于接收到的融合数据流量；条件3表示源节点s的本身产生的生命期为T，s在传输数据流时，发送的数据流为接收数据流和自身数据流的融合；条件4表示源节点s在某一链路中的数据流量不超过网络最大吞吐量；条件5表示为源节点s产生的数据流总和一定为T。

2 最大生命期数据融合树生成算法

2.1 算法描述

根据式(2)限制，本文在每一次迭代中建立一棵融合树。网络在每个τ时间单位内，形成一棵网络数据融合树，以基站t为根节点，向下延伸到所有的传感器节点，融合树表示为H。数据从叶子节点经中间节点融合后最终到达基站。无线传感器网络最大生命期为T，即一定存在T棵融合树。假设在网络中总共可能存在Ω棵融合树，则无线传感器网络最大生命期算法即寻找生命期最大T棵树。

2.2 节点负载量化模型

在某τ时间单位内，存在数据融合树集合为Ω，其中一棵数据融合树表示为H，归一化负载为W(H)，H*为最大归一化负载融合树,H*∈Ω，归一化负载为W(H*)。因为H*为最大归一化负载融合树，所以，|S(H*)|≥|S(H)|。根据二叉树算法

亦即

(3)

定义1 在τ时间单位内，存在1棵数据融合树H，归一化负载为W(H)，定义满足式(4)的节点为负载较重节点

(4)

由式(3),式(4)可以得到

定义满足式(5)的节点为负载合理节点

(5)

2.3 融合树生成算法实现

在建立的数据融合树中，需要从树中移走节点集合R，使得负载较重节点成为孤立离散节点集合S(H)，重新选择其他路径将孤立节点再次链接到树中，直到使得节点负载满足式(5)。数据融合树生成算法如下

Start:H:Initial an aggregate data tree

Executive:

fori=1 toNdo

Calculate every node’s load:Wi(H)

end for

i=1

whilei≤Ndo

then

The nodeiis removed fromHand

create a set of disconnected componentsS(H),j=1,Li(H)

forj≤Li(H) do

end for

else break;

end if

end while

2.4 最大生命期数据融合树生成算法实现

按照2.3节融合树生成算法，在某τ时间开始，网络产生一棵以Sink为根的H*树，树中节点均满足式(5)要求，假设该树稳定工作时间T1(H*)后，树中存在不再满足式(5)要求的节点，称该树的生命期为T1(H*)，也即产生的数据流f1=T1(H*)。

定义2： 如果网络G存在m棵独立的H*树，生命期分别为T1(H*),T2(H*),…,Tm(H*)，那么网络的最大流量为fmax=T1(H*)+T2(H*)+…+Tm(H*) ，网络的最大生命期为Tmax=fmax。

图1 无线传感器网络数据融合树结构调整模型

当树结构负载不符合式(5)时，树结构进行调整，调整模型如图1所示，图1(a)中，融合树在工作T1(H*)时间后，出现2个负载过重节点，节点i从树中去除，形成离散孤立节点集合S(H)={x}，x链接到j后。树结构调整到下一个树结构，网络重新在合理负载下运行。

当运行T2(H*)时间后，图1(b)树结构出现其它负载过重节点。节点k从网络中断开，形成孤立节点集合S(H)={i,j}，节点i,j,k可以经过3条链路链接，如图2(a)所示，图2(b)为当前链接负载过重情形，节点链接经过调整后存在图2(c),(d)2种情况。经过重新调整后，网络到达状态如图1(c)。从图中可以看出：经过调整后，个别节点负载过重的部分被转移到其它节点上，负载在一定程度上得到平衡。

图2 节点负载调整模型

3 仿 真

仿真在NS—2环境中实现，随机产生40～120个普通传感器节点，节点随机分布在100 m×100 m的平面区域，节点最大传输距离半径R=15 m，在传输距离内的任意2个节点可以互相直接通信，传感器节点的初始能量Estart=1 kJ，接收单位数据能耗系数ρ=50 nJ/b，m=4。本文采用高斯随机场模型作为数据相关模型,其中,参数α的取值范围为0.01/m2≤α≤0.01/m2(α越小,数据相关程度越高)。

本文将所提算法ML—MFA(maximum lifetime and maximum flow algorithm)与MEGA和MLR算法进行比较。图3为3种对比算法中网络数据流与时间的关系。节点数量分别为40，80，从图3中可以明显看出：本文所提算法在数据量采集量上明显优于其它2种算法。本文所提算法由于不断调整节点负载，相当于在所有节点上均衡负载压力，节点生命期得到延长，τ的倍数也最大，MEGA虽然没有考虑相关性，数据字节数会比MLR稍大，但是节点在转发数据时，将耗费更多的资源，生命期会小于MLR。

图3 数据流与时间的关系

图4显示了在不同节点数量、不同α值情况中网络生命期的对比情况。α取值分别为0.001，0.01/m2。从图4中可以看出:ML—MFA随着网络规模的增大，网络生命期呈现逐渐上升的趋势，而MEGA和MLR算法的网络生命期缓慢下降。这是因为网络的数据负载与节点数量呈正比，节点数量越多，产生的数据量越大，造成了网络整体能耗增加，网络生命期下降。但是，节点数据增多使得网络节点密度加大，节点与邻居节点通信能耗下降，同时节点密度变大后，数据相关性增大，更多的冗余数据被清除。

图4 网络生命期

4 结 论

本文的目标是在实现网络最大生命期的同时达到采集数据的最大化，根据能量等限制条件建立线性规划模型，考虑到网络最大生命期是NP难问题，本文将网络最大生命期问题转化为网络最小归一化负载问题，通过重新安排负载较重节点的链路边集合，调整负载较重节点的数据转发压力，最终建立一棵最优网络归一化负载数据融合树,实现了网络生命周期的最大化。仿真实验对所提路由算法的性能进行了验证和分析，结果表明:该算法可以使得网络达到网络最大数据流,并可以有效地提高了网络节点的生命期。

参考文献:

[1]Xu Ning.On maximum lifetime routing in wireless sensor networks[C]∥IEEE Conference on Decision and Control and 28th Chinese Control Conference, Shanghai, 2009:3757-3762.

[2]Krishnamachari B,Estrin D,Wicker S.The impact of data aggregation in wireless sensor networks[C]∥Proc of the Int’l Conf on Distributed Computing Systems Workshops,Vienna: IEEE Computer Society,2002:575-578.

[3]Rickenbach Von P,Wattenhofer R.Gathering correlated data in sensor networks[C]∥Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC’04:New York, NY, USA:ACM Press, 2004：60-66.

[4]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor network-s[C]∥Proc of the Conf on System Science, Istanbul: IEEE Communications Society,2000: 223-228.

[5]Madan R,Lall S.Distributed algorithms for maximum lifetime routing in wireless sensor networks[J].IEEE Transactions on Wireless Communications, 2006, 8:2185- 2193.

[6]Liu Z Sankar.Maximum lifetime routing in wireless Ad Hoc networks[C]∥IEEE Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies,INFOCOM 2004: Hongkong,2004:1089-1097.

[7]Padmanabh Kumar.Multicommodity flow based maximum lifetime routing in wireless sensor network[C]∥IEEE Conference on Parallel and Distributed Systems,Minneapolis,MN,US，2006:187-194.

[8]Hua C,Yum T P.Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks[J].IEEE Trans on Networking, 2008, 16(4):892-903.