WSNs中路由与能量收集速率的联合优化*

蒋紫东， 冯 辉， 杨 涛， 胡 波

(复旦大学 电子工程系，上海 200433)

WSNs中路由与能量收集速率的联合优化*

蒋紫东， 冯 辉， 杨 涛， 胡 波

(复旦大学 电子工程系，上海 200433)

针对带有能量收集装置的无线传感器网络(WSNs)，提出了一种路由与能量收集速率联合优化的算法。通过规划节点能量收集装置的规格和网络路由，使WSNs在满足预算约束下达到最大的数据采集速率。算法将问题建模为一个组合优化问题，并通过凸松弛和变量离散化算法，得到一组次优结果，避免了高复杂度的穷举遍历。仿真结果表明:在不同的网络规模下，该算法性能均优于对比算法。

无线传感器网络； 能量收集； 网络路由； 联合优化； 采集速率

0 引 言

无线传感器网络(WSNs)通常会在目标区域中放置大量节点来完成数据的采集，传输与处理等工作。在传统场景中，节点由电池供能，而更换电池可能需要很大的开销，所以,在有限的电量下最大化网络寿命是一项重要的工作。尽管文献[1]总结了很多延长网络寿命的方法，但是节点最终还是会电量耗尽。近年来提出的能量收集技术[2～4]使节点可以将外界环境中的太阳能、风能、动能等转换为电能。理论上，如果各节点的能量收集速率大于消耗速率就可以实现能量可持续性，使网络达到无限的寿命。这时主要目标将由最大化网络寿命转变为在能量可持续性下最大化工作量[5,6]。在周期采样的WSNs中，工作量可以由传感器节点采集速率来表示，即单位时间产生的数据量。

在有Sink节点的多跳网络中，路由策略决定了节点间的能耗分布。一些针对能量收集场景的路由策略被提出以最大化工作量[7～9]。文献[8,9]提出的R-MF算法实现了路由的离线计算，它将WSNs建模为流网络，并用扩展的Ford-Fulkerson算法来计算最大流。实际工作中，选择一条边上发送数据的概率正比于该边上的最大流。R-MPRT[9]以节点因发送数据而消耗的能量的恢复时间作为权重，从而得到最短路径路由。

上述算法均是在节点的能量收集速率已知的情况下进行的。在很多应用中，设计WSNs时可以规划不同节点的能量收集设备[10]，不同规格的能量收集设备会导致不同的能量收集速率。以太阳能电池板为例，在相同光照条件下，面积和转换效率都会影响最终的收集速率。由于预算有限，给所有节点配置最高规格的设备是不可能的，这就需要给节点分配不同规格的设备。因此,可以在设计WSNs时同时规划节点能量收集设备的规格和路由，使网络在它们的共同作用下达到更高的采集速率。

本文首先提出了路由和能量收集速率的联合优化，使WSNs在满足一定的预算约束下采集速率最大。由于节点可选的能量收集设备规格有限，本文将该问题建模为一个组合优化问题，并提出了联合最大化采集速率(joint maximum sampling rate,JMS)算法来求解。仿真表明：JMS算法的性能优于现有算法。

1 系统模型

本文考虑的WSNs由N个静态节点和一个Sink节点组成。静态节点包括传感器节点和路由节点，它们的集合分别表示为Ns和Nr。2种节点都能接收数据并转发，传感器节点还以固定周期采样并产生数据，采集速率为Skbit/s。距离小于最大传输半径dmax的节点互为邻居，记节点i的邻居集合为Ni。假设在所有传感器节点和Sink节点之间总存在通路，那么所有采集的数据最终通过多跳路由传输到Sink节点。路由可以看成是一种网络流r∈RN×(N+1)， 其中,rij代表了节点i到j的流速率，单位是k bit/s。

节点配备了能量收集装置，可以将外界环境中的能量转换为电量。实际上能量收集速率会随着环境变化而变化，系统会为每个节点配置合适容量的可充电电池作为缓冲来补偿这种变化[11]。本文只考虑平均能量收集速率，单位是mJ/s。共有M种能量收集装置供节点选择，按平均能量收集速率排序λM>…>λ1=0，即节点单位时间从环境中收集的平均能量为Λi∈{λ1,λ2…,λM},∀i∈N。

假设节点仅当发送数据时消耗能量。定义节点i发送数据到节点j消耗的能量为EijmJ/kbit。为了满足WSNs可持续工作的要求，每个节点都需要满足能量可持续性的条件，即

(1)

这样在给定网络拓扑的情况下，对r，S和Λ进行联合优化，优化问题如下

Λi∈{λ1,λ2,…,λM},∀i∈N,

rij≥0,∀i∈N,∀j∈Ni,

S≥0.

(2)

由于Λ取离散值，问题(2)是组合优化问题，一般需要穷举遍历来得到最优解，需要很大的计算量。所以，之后本文提出一个次优但是高效的JMS算法来求解问题(2)。

2 联合最大化采集速率算法

2.1 凸松弛

首先将离散约束Λi∈{λ1,λ2,…，λM}松弛为连续约束0≤Λi≤λM,同时将能量持续性约束式(1)改为等式约束

(3)

这个改变不影响连续约束下的最优值，但是可以保证对收集能量的完全利用，便于之后离散化算法的提出。所以,问题(2)变为

0≤Λi≤λM,∀i∈N,

rij≥0,∀i∈N,∀j∈Ni,

S≥0.

(4)

这是一个线性规划，可以用现有的工具包高效求解，比如:Matlab的CVX。规化(4)的最优解为{Sc,rc,，Λc},上标c表示这属于变量松弛后的连续优化问题。

2.2 能量收集速率离散化算法

本节提出能量收集速率离散化算法(energy harvesting rate discretization algorithm,ERDA)，使连续的Λc离散化为Λd，并分析其性能。上标d为该变量取离散值。已知节点共有M种能量收集装备可选择，设节点i选择的编号为wi，wi∈{1,…,M}，对应的充电速率λwi。

引理1：在{Sc,rc,Λc}的基础上保持路由不变，节点分配了能量收集装备后，最大采集速率为

(5)

(6)

3)预先计算节点能量收集装置“退化”到下一个更小收集速率后，网络的最大采集速率

(7)

5)停止。

引理2：ERDA中步骤(3)的结果就是节点退化后WSNs的最大采集速率。

证明：由引理1知，证明引理2只需证明式(8)成立

(8)

通过引理2，可以得到下面的定理1来说明ERDA的特性。

定理1:经过ERDA离散化后的Λd是在路由确定下最优的能量收集装置分配方案。

证明:构建一张列表，将所有可能的MN种能量收集装置分配方案下的采集速率按降序排列。步骤(1)的初始松弛保证了初始的采集速率高于最优值，而引理2和步骤(4)保证了一次退化后，采集速率会下降为列表中的下一个或者保持不变(不同的分配对应相同的采集速率)。所以,ERDA使采集速率以最小跨度单调下降，总能从初始状态到达最优分配下的采集速率，得证。

2.3 算法流程

ERDA得到离散的Λd。最后在能量收集速率确定的情况下，对路由进行优化。完整的JMS流程如下:

1)松弛问题(2)为线性规划式(4)，求解得到{Sc,rc,Λc}；

2)在rc确定的路由下，利用ERDA将Λc离散化为Λd；

3) 取ΛJMS=Λd，代入问题(2)，重新优化路由，得到rJMS和对应的网路寿命SJMS。

{SJMS,rJMS,ΛJMS}就是JMS对问题(2)的最终结果。注意到ERDA只是在给定路由下的最优离散化算法，得到的Λd与路由并不是联合最优的。JMS避免了对于能量收集装置的穷举遍历，步骤(1)与步骤(3)都是求解线性规划问题，ERDA只需要简单的代数运算，所以,JMS是高效的次优算法。

3 仿真分析

图1是一个JMS的示例。在边长为90 m的正方形区域中，51个节点构成了传感器网络。其中方点表示传感器节点，圆点表示路由节点，五角星表示Sink节点。网络中最大传输半径是20 m。有5种能量收集速率供节点选择，为{0，5,10,20,30}mJ/s，能量收集装置预算约束Λtotal=500 mJ/s。经过JMS规划后，图1的边的线宽与流大小呈正比，数字表示节点的能量收集速率。注意到能量收集速率为0的点也是孤立的点，表示这些节点没有数据收发的任务，无需安放。

图1 JMS下的WSNs示例Fig 1 WSNs example of JMS

JMS使图1的WSNs达到最大采集速率为13.6 kbit/s。对同样的拓扑，如果不采用联合优化，而是给节点分配相同的能量收集装置，Λi=10 mJ/s，R-MF，R-MPRT和最小跳数路由(minimum hop routing,MH)能达到的最大工作量分别为8.4，3.4,2.3 kbit/s，性能对于JMS下降了38 %，75 %,83 %。

为了得到更普遍的结果，本文之后测试不同的网络规模下算法的性能。节点数N为10～100，50 %节点为传感器节点，预算约束与区域面积随节点变化，保持Λtotal=10N mJ/s和节点密度为0.008个/m2，最大传输半径为3 m。其他条件与之前相同。每组参数进行100次随机拓扑的仿真，并对结果求平均。

图2显示仿真结果，从中可以看出网络规模变大后，为了满足Sink周围节点的能量可持续条件，最大采集速率减小。但在各种网络规模下，性能上均有JMS>R-MF>R-MPRT>MH成立。这是因为JMS考虑了能量收集速率和路由的联合优化，而其他3种只考虑了路由策略。相较于启发式算法R-MPRT，R-MF对路由进行了优化，故性能较好，而MH只考虑跳数，没有考虑节点能耗，故性能不佳。

图2 不同网络规模下的算法性能比较Fig 2 Performance comparison of algorithm in different network scales

4 结 论

在配备能量收集装置的WSNs中，为了在满足预算约束和能量可持续性约束下最大化传感器的采集速率，本文提出将路由与节点的能量收集速率进行联合优化，并提出JMS算法求解。仿真显示：在不同网络规模下，JMS算法具有很好的性能，始终优于现有算法。

[1] Anastasi G,Conti M,Di Francesco M,et al.Energy conservation in wireless sensor networks:A survey[J].Ad Hoc Networks,2009,7(3):537-568.

[2] Sudevalayam S,Kulkarni P.Energy harvesting sensor nodes:Survey and implications[J].IEEE Communications Surveys & Tutorials,2011,13(3):443-461.

[3] Roseveare N,Natarajan B.A structured approach to optimization of energy harvesting wireless sensor networks[C]∥Proceedings of Consumer Communications and Networking Conference (CCNC),IEEE,2013:420-425.

[4] 张华良,王 军,于海斌,等.一个能量收集无线传感器网络路由协议[J].小型微型计算机系统,2011,32(7):1277-1280.

[5] 马 宁,李开宇,吴 寅,等.基于最大流的能量采集型无线传感器网络路由算法[J].传感器与微系统,2013,32(1):131-134.

[6] Peng S,Low C P.Energy neutral routing for energy harvesting wireless sensor networks[C]∥Proceedings of Wireless Communications and Networking Conference (WCNC),IEEE,2013:2063-2067.

[7] Hasenfratz D,Meier A,Moser C,et al.Analysis,comparison,and optimization of routing protocols for energy harvesting wireless sensor networks[C]∥Proceedings of Sensor Networks,Ubiquitous,and Trustworthy Computing(SUTC),IEEE,2010:19-26.

[8] Bogliolo A,Lattanzi E,Acquaviva A.Energetic sustainability of environmentally powered wireless sensor networks[C]∥Procee-dings of the International Workshop on Performance Evaluation of Wireless Ad-hoc,Sensor and Ubiquitous Networks,ACM,2006:149-152.

[9] Lattanzi E,Regini E,Acquaviva A,et al.Energetic sustainability of routing algorithms for energy-harvesting wireless sensor networks[J].Computer Communications,2007,30(14):2976-2986.

[10] Zhang S,Seyedi A.Analysis and design of energy harvesting wireless sensor networks with linear topology[C]∥Proceedings of the International Conference on Communications,IEEE,2011:1-5.

[11] Bogliolo A,Delpriori S,Lattanzi E,et al.Self-adapting maximum flow routing for autonomous wireless sensor networks[J].Cluster Computing,2011,14(1):1-14.

[12] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

Joint optimization of routing and energy harvesting rate in WSNs*

JIANG Zi-dong, FENG Hui, YANG Tao, HU Bo

(Department of Electronic Engineering,Fudan University,Shanghai 200433,China)

Propose an algorithm to jointly optimize routing and energy harvesting rate in wireless sensor networks(WSNs) with energy harvesting devices.By designing size and network routing of node energy harvesting devices,aiming at maximizing data sampling rate under the budget constraint.The algorithm models the problem as a combination optimization probles and by convex relaxation and variable discretization algorithm,and get a group of suboptimal solution avoid high complexity exhaustive search.The simulation results illustrate that performance of the algorithm is better than comparative algorithms in different network scales.

wireless sensor networks(WSNs); energy harvesting;network routing; joint optimization; sampling rate

2014—01—16

国家教育部博士点基金资助项目(20120071110028)

TP 393

A

1000—9787(2014)04—0017—04

蒋紫东(1989-)，男，浙江定海人，硕士研究生，研究方向为无线传感器网络。