袁利永， 林飞龙， 王 晖, 曾令国

(1.浙江师范大学 行知学院,浙江 金华 321004；2.浙江师范大学 数学与计算机科学学院,浙江 金华 321004)

0 引 言

无线传感器网络(WSN)由许多传感器节点组成，用于收集数据，已经在诸多领域得到了广泛应用.在传统的WSN中，节点一般采用能量有限的电池供电，其工作时间和数据速率都受到节点电池能量的制约，这给WSN应用于数据速率较高的领域带来许多困难.最近，能量捕获无线传感器网络(EH-WSN)受到了越来越多的关注.EH-WSN中的节点装备了能量捕获模块和可充电电池，能够从环境中获取能量，使得传感器节点可以免受电池能量的制约，大幅度延长节点及其网络的工作时间.在一些EH-WSN应用中(如环境、建筑等监测应用)，所有节点都被要求以相同的收集速率向sink节点汇报感知数据[1].把网络中所有节点能够共同支持的最大数据采集速率称为网络共同收集速率.提高网络共同收集速率有助于提高传感器网络的监测精度，因此，高速率的数据收集方案是许多EH-WSN应用者(如多媒体传感器网络)的追求目标之一.

人们对EH-WSN网络共同收集速率最大化问题进行了不少研究.文献[2-4]研究了使用移动sink节点场景下的网络共同收集速率最大化问题，但它们的研究成果并不适用于sink节点不能移动的网络场景;文献[1,5-7]研究了EH-WSN中非树型数据收集策略下的网络共同收集速率最大化问题，其研究成果也不能直接应用于基于收集树的网络.收集树路由因具有计算简单、无需路由表等优点，能够适应传感器节点计算能力弱、存储空间少的特点[8]，被广泛地应用于EH-WSN中.

目前，专门研究基于收集树的EH-WSN网络共同收集速率最大化问题的文献还很少.文献[1]研究了收集树给定情况下的网络共同收集速率最大化问题，并提出了一种名为DLEX的分布式算法来求解网络的最大共同收集速率.然而，给定一个EH-WSN网络拓扑，可以生成很多棵不同的数据收集树，不同的收集树将导致不同的网络共同收集速率.所以，根据EH-WSN中节点的捕获能量情况寻找一棵最优数据收集树是提高网络共同收集速率的有效手段.然而，这方面的研究也非常少.文献[9]提出了基于马尔可夫决策过程的父节点切换方法来平衡节点的能量消耗，从而保持EH-WSN收集树能量的可持续性，然而其优化目标不是最大化网络共同收集速率.

当节点在某一时段内捕获的能量具有高可预测性时，EH-WSN网络共同收集速率最大化问题等价于传统WSN在节点数据采集速率相同情况下的网络寿命最大化问题.人们对基于收集树优化的WSN网络寿命最大化问题进行了很多研究.绝大多数文献将WSN的寿命定义为第一个失效节点的生命周期.文献[10-13]研究了收集树节点具有数据融合能力的WSN网络寿命最大化问题;文献[14]提出了基于能耗最小生成树和信息摆渡相结合的方法来延长网络生命周期;文献[15]证明了在节点无数据融合功能的WSN中构建最大网络寿命收集树是一个NP难问题，提出了优化网络寿命的启发式收集树构建方法MNL;文献[16]把WSN的最大网络寿命收集树问题表示为最小最大权重生成树问题，并提出了构建最大网络寿命收集树的迭代算法MITT.实验结果显示,基于迭代优化思想的MITT算法优于PEDAP-PA[17]、MNL等启发式构造算法.文献[18]提出了名为RaSMaLai的最大网络寿命收集树寻找算法，但它对网络规模和拓扑的适应性不如MITT算法;文献[19]把最大网络寿命收集树的构建问题建模为混合整数线性规划问题，但该方法仅适合于小规模网络.

显然，借鉴上述算法的思想可以设计出相应算法来寻找具有最大网络共同收集速率的收集树.然而，收集树路由存在一个比较大的缺点，那就是某个节点的失效会导致其子树无法向sink节点传输数据.为了解决这一问题，人们提出了IEEE 802.15.5标准[20].IEEE 802.15.5标准让每个节点在保存收集树信息的基础上维护若干跳邻居的链路信息，从而形成mesh网络.mesh网络不仅保留了树路由的优点，而且节点之间存在多条路径,提高了网络的可靠性，使得部分数据能够绕过收集树中的瓶颈节点，从而提高了整个网络的最大共同收集速率.遗憾的是，目前还没有文献对基于mesh路由优化的网络共同收集速率最大化问题进行研究.

本文针对节点无数据融合功能的EH-WSN网络共同收集速率最大化问题，研究基于收集树优化和mesh路由优化的EH-WSN网络共同收集速率最大化方法，主要贡献如下：

1)提出了一种启发式构造和迭代优化相结合的最大网络共同收集速率收集树寻找算法hybridMCRT.

2)针对收集树中存在的瓶颈节点问题，提出了以最大网络共同收集速率收集树为导向的mesh路由算法MCRToMesh.

3)提出了基于MCRToMesh路由算法的网络共同收集速率最大化方法，通过把基于MCRToMesh路由的网络共同收集速率最大化问题建模为线性规划问题，求解出最大网络共同收集速率及每个节点最优的mesh路由转发目标及转发比率.

4)通过大量实验仿真验证了本文算法的有效性.

1 基于mesh路由的高速率数据收集方案

1.1 网络模型

本文对研究的网络作如下假设：传感器节点一旦部署，其位置不会发生改变；sink节点具有充足的能量，其他节点从环境中捕获能量，并配备有较大容量可充电电池，且其在某一时段的捕获能量具有高可预测性；每个传感器节点与sink节点之间至少存在一条路径，即网络中不存在孤立节点.

用无向图G(V,A)表示能量捕获传感器网络，其中V是节点集合，包括sink节点(以s0表示)，A是链路集合.d0表示节点的无线电覆盖半径，〈u,v〉和d(u,v)分别表示节点u,v之间的通信链路和距离.于是，A={〈u,v〉|d(u,v)≤d0,u,v∈V}.此外，用N(u)表示节点u的一跳邻居;T(VT,AT)表示图G(V,A)中一棵以s0为根的生成树;VT表示生成树T中的节点集合;AT表示生成树T中的链路集合;用pv表示节点v的父节点;TL(v)表示节点v在树T中的层数，并设s0位于第0层，即TL(s0)=0.另外，分别用DNv和ANv表示节点v的子孙节点集和祖先节点集;以mv表示DNv的元素个数.

(1)

(2)

给定一个网络拓扑，可以生成很多棵不同的收集树，而不同的收集树具有不同的网络共同收集速率，笔者把网络共同收集速率最大的那一棵收集树称为最大网络共同收集速率收集树.由文献[15]可知，寻找最大网络共同收集速率收集树是一个NP难问题.笔者提出启发式构造和迭代调整优化相结合的最大网络共同收集速率收集树寻找算法hybridMCRT.

1.2 hybridMCRT算法

hybridMCRT算法的基本思想如下：首先利用启发式方法构造一棵最大网络共同收集速率收集树，然后再利用迭代调整方法不断对该收集树进行优化，最后对收集树进行调整以消除“路由绕行”问题.

通过借鉴和改进MNL算法思想，提出了名为iMNL-based MCRT的最大网络共同收集速率收集树启发式构造算法，其算法思想如下：从sink节点(s0)开始，每次选择一个使网络共同收集速率下降最小的节点加入到收集树中，直到网络中的所有节点加入收集树.在此过程中，当有多个节点能使网络共同收集速率下降最小时，优先选择捕获能量多的节点加入收集树，这就是iMNL-based MCRT算法对MNL算法思想的改进之处.iMNL-based MCRT算法的详细步骤如下：

算法1iMNL-based MCRT(G){

VT={s0},AT=Ø,VL=V-{s0},TL(s0)=0

WhileVL≠Ø Do

maxR=0

For eachu∈VLDo //遍历剩余节点

For eachv∈VTDo //遍历树中节点

If (〈u,v〉∈A){

Ttemp=(VT∪{u},AT∪{〈u,v〉})

If(NCR(Ttemp)>maxR)

maxR=NCR(Ttemp),〈u*,v*〉=〈u,v〉

Else If(NCR(Ttemp)=maxR&&

〈u*,v*〉=〈u,v〉

EndIf

EndIf

EndFor

EndFor

VT=VT∪{u*},AT=AT∪{〈u*,v*〉}

VL=VL-{u*},TL(u*)=TL(v*)+1

EndWhile

ReturnT(VT,AT)

}

用iMNL-based MCRT算法生成最大网络共同收集速率收集树后，hybridMCRT算法需要再用迭代调整算法对该收集树进行优化.文献[16]把WSN的最大网络寿命收集树问题表示为最小最大权重生成树问题，并提出了通过迭代调整收集树来优化网络寿命的MITT算法，该算法从任意一棵收集树开始，迭代地让最大权重节点的子孙节点关联至具有更小权重的邻居节点来不断降低收集树的权重，从而不断优化网络寿命.在EH-WSN中，当节点在某一时段内捕获的能量具有高可预测性时，网络共同收集速率最大化问题等价于传统WSN在节点采集速率相同情况下的网络寿命最大化问题.因此，笔者提出了基于MITT算法思想的最大网络共同收集速率收集树迭代优化算法MITT-based MCRT.MITT-based MCRT算法与MITT算法基本相同，唯一的差异就是MITT-based MCRT算法赋予了节点权重和收集树权重不同的含义.下面给出MITT-based MCRT算法中用到的节点权重和收集树权重的定义.

定义1节点权重：收集树T中的节点v(v∈VT-{s0})的权重定义为

(3)

式(3)中，w(T,v)表示节点v为每个子树节点转发1比特数据所消耗的能量之和与其捕获能量的比值.比值越大，表明它能够为每个子树节点转发的数据量越少.

定义2收集树T的权重定义为

(4)

收集树的权重越大，意味着在t时段内，网络中所有节点能够共同支持的最大数据采集量越小，即网络共同收集速率越小.为了提高基于收集树T的网络共同收集速率，需要不断降低收集树的权重w(T)，即收集树中瓶颈节点的权重.MITT-based MCRT算法的总体策略与MITT算法一样，就是迭代地把瓶颈节点的子孙节点关联至具有较小权重的其他子树节点来逐渐降低收集树的权重.因此，只需用式(3)和式(4)分别代替MITT算法中的节点权重和收集树权重，即可得到MITT-based MCRT算法.MITT算法的详细介绍可参阅文献[16]，在此不再赘述.

通过实验发现，基于hybridMCRT算法得到的收集树存在如图1(a)所示的“路由绕行”问题.例如：节点F基于收集树路由向sink节点传递数据的路径为F→A→B→sink，而实际上，节点B既是节点F的祖先节点，又是它的一跳邻居，因此，节点F的数据不必绕行节点A，可以直接通过节点B流向sink节点.节点E也存在类似的问题.

图1 收集树“路由绕行”问题

“路由绕行”问题不仅浪费节点能量，而且会增加数据传输跳数，从而影响端到端的通信时延.为了解决“路由绕行”问题，笔者提出了收集树调整算法RegulateRoutingTree来消除“路由绕行”问题，其步骤如算法2所示.

算法2RegulateRoutingTree(T){

For eachvinVT-{s0} do

If (u≠pv)

pv=u,TL(v)=TL(u)+1

updateTreeLevelinSubTree(v)

EndIf

EndFor

ReturnT

}

其中，函数updateTreeLevelinSubTree(v)用于更新节点v所有子孙节点的树层，其代码如下：

Function updateTreeLevelinSubTree (v){

For eachxin {x|px=v,x∈N(v)} do

TL(x)=TL(v)+1

updateTreeLevelinSubTree(x)

EndFor

}

不难证明，在经算法2调整的收集树中，任意节点在其一跳邻居中的最早祖先节点就是其父节点.图1(b)是经算法2调整后的收集树.

1.3 以收集树为导向的mesh路由算法

为了进一步提高基于收集树的网络共同收集速率，提出了以收集树为导向的mesh路由算法MCRT-oriented mesh(简称MCRToMesh).其基本思想是通过mesh路由让部分数据有机会绕开瓶颈节点并最终到达sink节点，从而提高整个网络的最大共同采集速率.mesh网络的形成过程与IEEE 802.15.5类似，即节点在保存收集树拓扑信息的基础上，维护两跳邻居的相关信息，从而形成mesh网络.

步骤1：若当前节点c是sink节点的邻居节点，则直接把数据包转发给sink节点；否则转步骤2；

步骤2：在当前节点c的一跳邻居中找出数据包源节点s的最早祖先节点，然后将该祖先节点的父节点指定为锚节点(用anchor表示)，转步骤3；

步骤3：在当前节点c和锚节点anchor的共同邻居集CN(c,anchor)中，根据在当前节点c中存储的数据转发比率{φ(c,x,anchor)|x∈CN(c,anchor)}选择一个节点作为中继节点，并把数据包转发给中继节点.

MCRToMesh路由与IEEE 802.15.5 mesh路由的区别主要有两点：IEEE 802.15.5mesh路由总是选择与目标节点树路由距离最近的两跳邻居节点作为锚节点，而MCRToMesh则是选择数据包源节点在当前节点一跳邻居中的最早祖先节点的父节点作为锚节点；IEEE 802.15.5 mesh路由从当前节点和锚节点之间的共同邻居中随机选择某一节点作为中继节点，而MCRToMesh路由则根据优化的转发比率选择中继节点(每个节点的转发目标和转发比率通过1.4节的方法进行识别和优化).

下面通过一个例子说明MCRToMesh路由采用上述锚节点选择策略的原因.在图2所示的网络中，节点的大小代表捕获能量的多少，黑色箭头线表示收集树路由，虚线表示节点之间的邻接关系.以节点I把源自节点H的数据传递给sink节点为例进行说明.如图2(a)所示，若采用IEEE 802.15.5 mesh路由，则节点I会选择sink节点作为锚节点，从而选择节点F作为中继节点，也就是说来自节点H的数据都将沿着曲线箭头所示的路径流向sink节点，这就加重了节点F的流量负担，有可能导致它所捕获的能量不能支持相应的流量负载，从而降低整个网络的最大共同采集速率.而在图2(b)所示的MCRToMesh路由过程中，数据总是有机会沿着收集树路由到达sink节点，即在最坏情况下，基于MCRToMesh路由的网络共同收集速率不会低于基于收集树路由的网络共同收集速率.

图2 IEEE 802.15.5 mesh路由和MCRToMesh路由

1.4 基于MCRToMesh路由的网络共同收集速率最大化方法

根据MCRToMesh路由机制，当前节点首先根据数据包的源地址确定锚节点，然而通过它们的共同邻居向锚节点转发数据.当锚节点与当前节点之间有多个共同邻居(称为中继节点)时，当前节点按一定的比率(称为转发比率)选择中继节点.显然，节点不同的转发比率分配方案将导致中继节点具有不同的数据转发负载，这会影响整个网络的最大共同采集速率.因此，提出对网络中所有树层大于1的节点的转发比率进行优化来最大化网络共同收集速率(树层为1的节点直接把数据转发给sink节点，无需其他节点进行中继转发).

设kt(u,x,v)表示节点u在t时段内选择节点x作为中继节点向节点v转发的数据量，则在t时段内节点u选择节点x作为中继节点向节点v转发数据的比率可表示为

因此，在t时段内，基于节点转发比率优化的网络共同收集速率最大化问题等价于基于节点转发数据量优化的网络共同收集速率最大化问题.

为了实现对网络共同收集速率的优化，首先需要根据MCRToMesh路由机制识别出网络中每个节点(除sink节点)的转发流，它们是网络共同收集速率最大化问题的优化变量，笔者称之为转发流变量.sink节点的邻居节点收到数据后，直接把数据转发给sink节点，无需其他节点进行中继转发.把所有树层为1的节点的转发流变量集合表示为Ft={ft(x,s0)|x∈N(s0)}，其中ft(x,s0) 表示节点x在t时段内发送给s0的数据变量.

当树层大于1的节点收到数据时，首先根据数据包的源地址确定锚节点，然后向当前节点与锚节点的共同邻居转发数据.根据MCRToMesh路由策略，节点需要转发的数据有2类：一类是自己产生的数据和源自子孙节点的数据;另一类则源自其他节点并需要它进行中继转发的数据.任意节点u为转发自己产生的数据和源自子孙节点的数据，会选择其祖父节点(即父节点的父节点，用g(u)表示)作为锚节点.因此，需要通过节点u进行中继转发的邻居节点集可表示为Nin(u)={v|v∈N(u),g(v)∈N(u)}.根据MCRToMesh路由策略，节点u为转发源自x∈Nin(u)及其子孙节点的数据，会在其一跳邻居中找到节点x的最早祖先节点，然后将该祖先节点的父节点作为锚节点.因此，节点u为转发数据所要用到的全部锚节点可表示为

Λ(u)=g(u)∪

根据MCRToMesh路由策略，节点u的所有转发流变量表示为Kt(u)={kt(u,x,v)|x∈CN(u,v),v∈Λ(u)}.所有树层大于1的节点的全部转发流变量用Kt表示，即

下面说明图3所示实例中各节点的转发流变量(用带箭头虚曲线表示).节点H唯一的锚节点是C，而节点E和节点F是节点H和节点C的共同邻居，因此节点H会把一部分数据转发给节点E(用转发流变量kt(H,E,C)表示)，把另一部分数据转发给节点F(用转发流变量kt(H,F,C)表示).节点F为了转发源自节点H和节点E的数据会选择sink作为锚节点，由于节点F与sink节点之间只有一个共同邻居(即节点A)，节点F将源自节点H和节点E的数据全部转发给A(用转发流变量kt(F,A,S)表示)；另外，节点F为了转发源自节点J的数据会选择节点B作为锚节点，由于节点F与节点B之间只有一个共同邻居(即节点D)，所以节点F将源自节点J的数据全部转发给节点D(用转发流变量kt(F,D,B)表示).

图3 MCRToMesh路由实例

以网络共同收集速率最大化为目标，对所有的转发流变量进行优化时，必须服从下面2个约束：能量约束，即每个节点转发数据消耗的能量不能超过它所捕获的能量；流量平衡约束，即流出节点的数据量应等于流入节点的数据量加上它自己产生的数据量.根据上述分析，基于MCRToMesh路由的网络共同收集速率最大化问题可表示为如下优化问题：

maximizeσ;

w.r.t.σ,Ft,Kt

s.t.:

σ≥0;

(5)

kt(u,v,w)≥0, ∀kt(u,v,w)∈Kt;

(6)

ft(v,s0)≥0, ∀v∈N(s0);

(7)

∀v∈VT-{s0};

(8)

∀y∈Λ(v), ∀v∈VT,TL(v)>1;

(9)

∀v∈VT,TL(v)=1.

(10)

式(9)中,bv,y表示为

式(5)表示每个节点的数据采集量不能小于0，式(6)和式(7)表示每个流变量不能小于0；式(8)表示节点的能量约束，本文只考虑节点的数据收发能耗，而忽略计算、数据感知等能耗[1]；式(9)和式(10)表示节点流量平衡约束，式(9)适用于树层大于1的节点，表示节点指向某一锚节点的流出数据量应等于流入该节点并指向同一锚节点的流入数据量(若锚节点是当前节点的祖父节点，则流出数据量=流入数据量+采集数据量σ)，而式(10)适用于树层为1的节点，表示所有流入节点的数据量加上自己的采集数据量σ应等于流向sink节点的数据量.

∀u∈VT,TL(u)>1.

(11)

2 实验仿真及结果分析

为了验证本文提出的相关算法，笔者模拟了节点密度相同但节点数量不同、以及节点数量相同但节点密度不同的多种网络设置(节点密度定义为邻居节点的数量).对于每种网络设置随机产生200个网络拓扑(下面所示结果均为200个网络拓扑实验结果的平均值)，并随机设置sink节点的位置.对于每一个网络拓扑分别实现了以下5种最大网络共同收集速率收集树寻找算法：MNL-based MCRT算法(借鉴MNL算法思想的算法，简称MNL)、iMNL-based MCRT算法(借鉴和改进MNL算法思想的算法，简称iMNL)、MITT-based MCRT算法(借鉴MITT算法思想的算法，简称MITT)、MITT-based MCRT with MNL算法(NML和MITT相结合的算法，简称hybrid MCRT1)、MITT-based MCRT with iMNL(iNML和MITT相结合的算法，简称hybrid MCRT2).仿真实验所用相关参数如表1所示.

表1 仿真实验所用参数

首先，对基于iMNL算法和MNL算法的网络共同收集速率进行了比较，比较结果如图4所示.从图4不难发现，iMNL算法优于MNL算法，且其性能随着网络规模和节点密度的增大而提高.这是因为随着网络规模和节点密度的增大，在收集树的生长过程中，就有更多的机会出现存在多个候选生长节点使得收集树最大共同采集速率具有最小下降量的情况，与MNL不同，iMNL总是从多个候选生长节点中选择能量最多的节点加入收集树，使得新得到的收集树具有更多的能量，从而增加后续生成的收集树具有更大共同采集速率的可能性.

然后，对hybrid MCRT1算法、hybrid MCRT2算法和MITT算法的性能进行比较，比较结果如图5所示.从图5不难发现，hybrid MCRT1算法、hybrid MCRT2算法均优于MITT算法，hybrid MCRT2算法又优于hybrid MCRT1算法，这一实验结果表明：初始收集树的好坏对MITT算法的性能具有十分重要的影响，同时也验证了hybird MCRT算法的有效性.

MCRToMesh方法和hybrid MCRT2算法的性能比较如图6所示.从图6(a)可以看出，在节点密度相同的情况下，MCRToMesh方法的性能随着网络规模的增大而变小，这是因为随着网络规模的增大，其瓶颈节点的个数也会随之增多，至少存在一个瓶颈节点得不到邻居节点帮助(或得到较少帮助)的概率也会增加，从而使得MCRToMesh方法的性能也随之下降.从对图6(b)的观察可知，在网络规模相同节点密度不同的情况下，MCRToMesh方法的性能随着节点密度的增大而提高，这是因为随着邻居节点的增多，使得瓶颈节点得到邻居节点帮助的概率也随之增加，从而使得MCRToMesh方法的性能也随之提高.

(a)不同网络规模 (b)不同节点密度

3 结 语

本文研究了基于mesh路由的能量捕获传感器网络高速率数据收集方案，首先提出了一种启发式构造和迭代优化相结合的最大网络共同收集速率收集树寻找算法，并以此为基础提出了收集树导向的mesh路由算法MCRToMesh，采用线性规划技术优化了基于MCRToMesh路由的网络共同收集速率.本文所提方法不仅可用于求解EH-WSN网络共同收集速率最大化问题，也同样适用于WSN在节点采集速率相同情况下的网络寿命最大化问题.