计算机应用   2017, Vol. 37 Issue (6): 1545-1549  DOI: 10.11772/j.issn.1001-9081.2017.06.1545
0

引用本文 

谢小军, 于浩, 陶磊, 张信明. 可充电无线传感网络能量均衡路由算法[J]. 计算机应用, 2017, 37(6): 1545-1549.DOI: 10.11772/j.issn.1001-9081.2017.06.1545.
XIE Xiaojun, YU Hao, TAO Lei, ZHANG Xinming. Energy-balanced routing algorithm in rechargeable wireless sensor networks[J]. Journal of Computer Applications, 2017, 37(6): 1545-1549. DOI: 10.11772/j.issn.1001-9081.2017.06.1545.

基金项目

国家自然科学基金资助项目(61379130,61672485)

通信作者

张信明(1964-), 男, 安徽天长人, 教授, 博士, CCF高级会员, 主要研究方向:无线网络、智能电网. E-mail:xinming@ustc.edu.cn

作者简介

谢小军(1975-), 男, 安徽泾县人, 工程师, 硕士, 主要研究方向:电力通信系统;
于浩(1975-), 男, 安徽临泉人, 工程师, 硕士, 主要研究方向:电力通信系统;
陶磊(1992-), 男, 安徽和县人, 博士研究生, 主要研究方向:无线网络、智能电网

文章历史

收稿日期:2016-11-17
修回日期:2017-02-04
可充电无线传感网络能量均衡路由算法
谢小军1, 于浩1, 陶磊2, 张信明2    
1. 国家电网安徽省电力公司 信息通信分公司, 合肥 230061;
2. 中国科学技术大学 计算机科学与技术学院, 合肥 230027
摘要: 针对可充电无线传感网络中的能量均衡路由问题,提出在稳定功率无线充电和监测数据收集网络场景下的多路径路由算法和机会路由算法,以实现网络的能量均衡。首先,通过电磁传播理论构建了无线传感节点的充电和接收功率关系模型;然后,考虑网络中无线传感节点的发送能耗和接收能耗,基于上述充电模型将网络能量均衡的路由问题转化为网络节点运行时间的最大最小化问题,通过线性规划得到的各链路流量用以指导路由中数据流量分配;最后,考虑一种更加现实的低功耗的场景,并提出了一种基于机会路由的能量均衡路由算法。实验结果表明,与最短路径路由(SPR)和期望周期最短路由(EDC)算法相比较,所提出的两种路由算法均能有效提高采集能量的利用率和工作周期内的网络生命周期。
关键词: 能量均衡路由    可充电无线传感网络    机会路由    低功耗传感网络    
Energy-balanced routing algorithm in rechargeable wireless sensor networks
XIE Xiaojun1, YU Hao1, TAO Lei2, ZHANG Xinming2     
1. Division of Information Communication, State Grid Anhui Electric Power Company, Hefei Anhui 230061, China;
2. School of Computer Science and Technology, University of Science and Technology of China, Hefei Anhui 230027, China
Abstract: Aiming at energy-balanced routing problem in rechargeable Wireless Sensor Network (WSN), a new multi-path routing algorithm and an opportunistic routing algorithm were proposed in the scenario of wireless charging with stable power and monitoring data collection network, so as to achieve the energy balance of the network. Firstly, the relationship model between the charging power and the receiving power of wireless sensor nodes was constructed by the theory of electromagnetic propagation. Then, considering the sending and receiving energy consumptions of wireless sensor nodes in the network, the energy-balanced routing problem was transformed into the max-min optimization lifetime problem of the network nodes. The link traffic obtained by the linear programming was used to guide the data flow allocation in the routing. Finally, considering a more realistic scenario of low power WSN, an energy-balanced routing algorithm based on opportunistic routing was proposed. The experimental results show that, compared with the Shortest Path Routing (SPR) and Expected Duty-Cycled wakeups minimal routing (EDC) algorithms, the proposed two routing algorithms can effectively improve the utilization ratio of the energy collection and the network lifetime in the working period.
Key words: energy-balanced routing    rechargeable Wireless Sensor Network (WSN)    opportunistic routing    low power sensor network    
0 引言

无线传感器网络(Wireless Sensor Network, WSN)是由大规模的微型、智能传感器节点组成无线自组织网络系统,网络中的节点通过相互协作将监测到的数据信息传送至网关(sink)节点进行处理。无线传感网中的节点能量有限,为了提升节点的运行时间和网络寿命,为无线传感节点配备能量捕获模块和可充电电池,称为可充电无线传感节点。当可充电无线传感节点能够捕获的能量有限时,节点在能量耗尽前进行网络中的数据采样、接收和传输等正常操作,在能量耗尽后进入低功耗模式睡眠状态,此时,能量均衡路由关系到网络中节点的可运行时间,即网络生命周期,仍然是该网络中需要关注的重要问题。本文研究可充电无线传感网络能量均衡路由问题。

关于能量均衡路由,文献[1]提出了一种基于混合传输的能量均衡方法避免无线传感网中的能量空洞。混合传输指网络中节点的无线收发器具有不同传输功率。在数据收集传感网网络中,靠近sink节点的无线传感器由于接收更多的来自远处传感节点的数据会更快地耗尽能量,文献[1]提出增大远处的节点的传输功率,同时概率地选择传输的接收节点,减小离sink较近节点的通信负载,推迟能量空洞的出现,延长网络寿命。文献[2]提出一种簇规模自适应调节的能量均衡分簇路由协议,协议改进了低能耗自适应集簇分层(Low Energy Adaptive Clustering Hierarchy, LEACH)算法[3],根据节点离汇聚点的距离、剩余能量及分布密度来构造规模不等的簇,避免了低能量节点被选为簇首,达到网络能量均衡。文献[4]提出一种基于学习自动机的能量均衡分簇算法:综合考虑节点剩余能量和节点密度, 利用学习自动机与周围环境进行信息交互和动作奖惩,选择出相对较优的簇头;根据簇首与基站距离和其节点密度构造大小非均匀的簇,实现不同位置不同网络疏密程度下簇内和簇间能耗互补均衡,构造了基于簇首剩余能量、簇内节点密度和传输距离的评价函数,并运用贪婪算法选择出最优中转簇首进行多跳传输。文献[5]构造了一种全局能量优化函数,并考虑网络中节点的剩余能量情况,建立路由能耗和路由剩余能量的优化度函数来评估对目标函数的优化程度,通过构造优化度函数的评价函数来求解多目标优化问题,得到能量均衡的最优路径。

上述工作主要考虑自组织网络中的能量均衡路由问题,另一些研究将能量均衡路由和无线传感节点的可充电特性结合起来考虑,如:文献[6]提出了一种移动充电模型和路由方法实现网络中节点的成功数据上传和能量均衡;文献[7]提出另一种数据收集模型,当移动sink移动到无线传感节点附近时通过单跳或多跳的方式传输数据,综合考虑了路径规划、数据路由和能量均衡问题提出了一种综合解决方案。

现有的相关工作关于能量均衡路由算法中,基于分簇的解决方案通常采用分布式算法,无法实现全局最优;同时,某些能量模型[1, 5]只考虑了节点传输能耗而忽略了接收能耗;路由算法计算的是最优路径,忽视了多路径路由的可能性。针对上述模型和算法中存在的问题,本文结合考虑了一种无线能量采集场景,提出基于链路流量分配多路径路由算法和机会路由[10-11]算法,实现可充电传感网络的能量均衡,主要的工作在于:

1) 在可预测的能量补充流的基础上实现能量均衡路由;

2) 利用机会路由应对无线传感网络信道时变和丢失特性和其天然的负载均衡特性,达到能量均衡路由的目的;

3) 使用更加精确的能量模型,考虑节点传输及接收能耗;

4) 能量均衡路由算法是全局最优的。

1 网络模型与能量均衡问题 1.1 可充电无线传感器能量传播模型

本文研究的基于高压电线取电的可充电无线传感器网络中,取电、能量发射和接收装置的原理如图 1所示,其中能量接收装置与距离能量发射的距离由无线充电的方式所决定。不同的无线充电方式的传输距离、功率、频率和充电效率也不相同。本文研究基于无线电波的充电方式,其有效充电距离可达数十米,适用于分布距离较大的无线传感器网络。首先研究单个取电-充电装置对于多个无线传感器节点的充电模型。在电能发射装置通过连续发射电磁波给节点无线充电的过程中,由于电磁波在空间传播时会产生衰减,这种衰减与发电装置和传感节点间的距离、传播空间环境相关。

图 1 能量获取和发射装置 Figure 1 Energy access and launch device

根据电磁传播理论中的Friis传输公式,可以得到电磁波在理想空间中的传输特性。空间中任意一点处的电磁波功率P1与电磁波发射源发射功率P0的关系式如下:

${P_1} = {G_1}{G_0}{P_0}{\left( {\lambda /\left( {4{\rm{ \mathsf{ π} }}d} \right)} \right)^2}$ (1)

其中:G1G0分别表示接收天线和发射天线的增益;d表示接收点离发射源的距离;λ是传输的电磁波的波长。

1.2 无线传感网络机会路由模型

机会路由是一种适用于不可靠网络的路由技术,它利用多个可能提供相似传输质量的下一跳节点,可以显著提高网络吞吐量、减少传输次数和网络能量消耗,并具有天然的负载均衡特性[10-11]。机会路由根据介质访问控制(Medium Access Control, MAC)协议的不同实现方式也有所变化,但最关键的部分是候选集的选择。

候选集是由算法指定的有资格转发数据包的下一跳节点集合。在非低功耗场景下,由于候选集中的节点收到数据包的概率大于一个节点收到数据包的概率,因此机会路由可利用无线网络的广播特性来提高数据包投递的成功概率。在低功耗场景下,特别是节点的睡眠调度周期很长时[10],节点很少在同一时段处于活跃状态,此时发送方通过依次单播给候选集中的节点需要传输的数据包,直到该跳传输成功为止。

1.3 可充电无线传感网络模型

假设一个基于周期性数据收集可充电无线传感网络G=(N, A, R), 其中:N是所有无线传感节点的集合,包括N-1个常规节点和1个网关节点,也称为sink节点用于数据汇总和上传至互联网;A是所有节点间链路的集合,称两个无线传感节点间有一条链路当且仅当它们互相在对方的传输范围内,此时这两个节点也同时称为对方的邻居;R是电能采集和发射设备的集合。

假设网络中各无线传感节点以恒定的速率采集数据,记节点i的采集速率为ri。假设网络的整个运行生命周期时长为T,在每个观察窗口tT内,R的发射功率相对稳定,记为Pitx(t), 其中iR。节点i传输一个单位的数据包给节点j所耗费的传输能量为eijtx,同时j接收一个单位的数据包所耗费的节点能量为ejrx。同时假设节点可以采用多路径传输的方法将数据上传到sink,令qij(t)为节点it内将自身采集数据和接收到的数据通过节点j转发的数据量。

1.4 问题

在上述模型描述的可充电无线传感器网络中,由于无线传感器的位置相对固定,在给定的各充电装置的发射功率下,各传感节点在每个观察窗口内能够采集的能量可以预测且相对稳定。在这种情况下,如果对于该数据收集的传输路径设置不当,容易造成网络中的无线传感器能量失衡。本文研究可充电无线传感网中的传输(路由)问题,以达到网络能量的均衡,其重要性体现在:

1) 传输、接收数据包所消耗的能量与从无线电波中采集的能量均衡。如果消耗的能量速率大于采集能量速率,那么节点将会在有限的时间内死亡;反之,节点的能量将会一直处于电池容量上限,浪费了充电设备所发射的能量。

2) 网络中各无线传感节点之间的能量均衡。

如果上述条件无法满足,则考虑如何最小化节点间的能量净消耗速率,延长网络的生存周期。

2 能量均衡分析模型和路由算法

根据1.1节的充电损耗模型式(1),假设网络内的每个无线传感节点i在同一时刻只能由同一个充电设备为其充电,并令i在每个周期t内选择对其充电功率最大的为其充电。记传感节点i和充电发射装置r间的距离为di, k,则i在时段t内的充电功率可通过式(2) 推导得到:

$P_i^{{\rm{rec}}}(t) = \mathop {\max }\limits_{k \in R} \left\{ {{G_{{\rm{rx}}}}{G_{{\rm{tx}}}}P_k^{{\rm{tx}}}(t){{\left( {\lambda /\left( {4{\rm{ \mathsf{ π} }}{d_{i,k}}} \right)} \right)}^2}} \right\}$ (2)

由1.2节的能量模型可知,一个无线传感节点i的数据流由三个部分组成:流入i的数据流、i自身产生的数据流和流出i的数据流,分别记为Qiin(t)、ritQiout(t),其中t为一个观察周期时长。由于最后的数据都汇聚到sink,在一个流量稳定的数据收集网络中,对每个无线传感节点i满足:

$Q_i^{{\rm{in}}}(t) + {r_i}{l_t} = Q_i^{{\rm{out}}}(t)$

即节点i转发的流量是自身产生的流量和转发其他节点的流量之和。其数据流速率的形式为:

$\sum\limits_{j,i \in {S_j}} {{q_{ji}}(t) + {r_i}} = \sum\limits_{k \in {S_i}} {{q_{jk}}(t)} $ (3)

其中候选中继集合Si代表i转发数据的邻居节点集合。数据流量均衡模型如图 2所示。

图 2 数据流量均衡模型 Figure 2 Data flow balancing model

本文假设无线传感节点以低功耗和频率采集监测数据,故忽略不计节点的数据采集功耗,则在ti的能量消耗速率为:

${c_i} = e_i^{{\rm{rx}}}\sum\limits_{j,i \in {S_j}} {{q_{ji}}(t) + } \sum\limits_{k \in {S_i}} {e_{ik}^{{\rm{tx}}}{q_{ik}}(t)} $ (4)

假设i在阶段t使用在阶段t-1从电能发射装置所捕获的能量Eirec(t-1) 和在该阶段电池的剩余能量Eirem(t-1) 之和作为传输和接收数据包的总能量源,则在阶段t节点i的可运行时长为:

$\begin{array}{l} {\tau _i}(t) = \frac{{E_i^{{\rm{rec}}}(t - 1) + E_i^{{\rm{rem}}}(t - 1)}}{{{c_i}}} = \\ \quad \quad {\rm{ }}\frac{{P_i^{{\rm{rec}}}(t - 1) \cdot {t_r} + E_i^{{\rm{rem}}}(t - 1)}}{{e_i^{{\rm{rx}}}\sum\limits_{j,i \in {S_j}} {{q_{ji}}(t) + } \sum\limits_{k \in {S_i}} {e_{ik}^{{\rm{tx}}}{q_{ik}}(t)} }} \end{array}$ (5)

τi(t)>lt,说明可支持i运行的时长大于该周期的长度,即该周期内i电池的能量盈余为正;否则说明周期ti捕获的能量加上电池内剩余的能量不足以支持其消耗的能量。τi(t)和lt的大小关系决定了阶段t内节点电池剩余能量的增减,一个能量均衡的路由策略需要能够确保i在某个阶段的电池能量既不会为零,也不会超出其电池的最大设计容量Eimax。本文假设每个阶段都存在某些节点的剩余能量不足以支持其传输、接收能量消耗,需要设计能量均衡的路由协议,对于这些节点,令其上一阶段的剩余能量Eirem(t-1) 为0。定义阶段t的网络生存时间为所有参与数据监测、转发的可充电无线传感节点中可运行时长最短的节点,研究在每个观察窗口t内对每个传感节点的流量分配,达到网络能量均衡,以实现最大化网络生存生存时间的问题。形式化地,该问题可表示为问题一,具体形式如下:

$\mathop {\max }\limits_{{q_{ij}}\left( t \right)} \left\{ {\mathop {\min }\limits_i {\tau _i}(t)} \right\}$ (6)
$\begin{array}{l} {\rm{s}}.{\rm{t}}{\rm{.}}{\tau _i}(t) = \frac{{P_i^{{\rm{rec}}}(t - 1){l_{t - 1}} + E_i^{{\rm{rem}}}(t - 1)}}{{e_i^{{\rm{rx}}}\sum\limits_{j,i \in {S_j}} {{q_{ji}}(t) + } \sum\limits_{k \in {S_i}} {e_{ik}^{{\rm{tx}}}{q_{ik}}(t)} }}\\ \quad \quad \sum\limits_{j,i \in {S_j}} {{q_{ji}}(t) + } {r_i} = \sum\limits_{k \in {S_i}} {{q_{ik}}(t)} \\ \quad \quad {q_{ji}}(t) \ge 0\\ \quad \quad i,j \in N \end{array}$

易知问题一是一个关于变量qji(t)具有等式约束条件的max-min线性规划(Linear Programming, LP)问题,求解问题一可以利用Matlab中现有的线性规划工具fminimax。

3 低功耗传感网能量均衡

在无线传感网络中,为了进一步降低网络能耗、延长网络生存周期,通常采用低功耗MAC协议使得节点在非活跃状态关闭无线收发器以减少不必要的空闲侦听能耗。在可充电传感网中,节点采用低功耗协议能够在相同的情况下相比不采用低功耗协议的场景减少充电频率。本章研究在可充电低功耗传感网中的能量均衡路由问题。

3.1 低功耗模式和机会路由

现有研究表明,传感节点在无线通信模块发送、接收、空闲、休眠状态中平均消耗的能量占总耗能的80%以上[8]。低功耗模式指无线传感节点能够在空闲时段关闭无线通信模块,进入睡眠模式,故低功耗模式在数据传输非密集型的无线传感网中能够显著减少网络能量消耗。节点只能够在活跃的状态下发送、接收或监听到数据包。周期性睡眠调度是指节点周期性、定时地睡眠、醒来,在这种睡眠调度机制下睡眠时间和调度周期的比值称为节点低功耗模式的占空比。

在占空比较低的情况下,节点同时醒来的概率很低,发送方为了成功传输数据包,需要持续发送引言包直到一个接收方醒来并回复确认包(ACKnowledgement, ACK)。如果发送方只选择一个下一跳节点,那么当该接收节点的一个活跃周期结束,发送方需要等待一个调度周期发送剩余的数据包,在不可靠链路传感网中甚至需要等待多个调度周期,增加了端到端时延。机会路由允许一个发送方选择一个邻居候选集而不只是一个下一跳以转发数据包,在低占空比情景下,候选集中的节点依次醒来,发送方按照其醒来次序分别传送数据包直到发送成功为止。

3.2 能量均衡候选集选择

机会路由能够有效降低等待延时,减少成功传输一个数据包所需的传输次数。参照第2章的算法,本文尝试利用流量分配以实现能量均衡路由,然而低功耗传感网中睡眠调度和机会路由带来的挑战在于,当一个发送方的候选节点集确定后,经过该发送方的数据流的分配也同时确定,这与候选集中节点的醒来次序、发送方到候选集中各节点的链路质量相关。因此本文研究在无法实现最优能量均衡的路由策略情况下,如何为网络中的每个节点确定转发候选集以达到较优的网络均衡。

首先考虑发送方需要发送一个数据包的情况,在流量分配策略中考虑多个数据包的情况。发送方s的转发候选集按其醒来次序递增排序记为集合fS={n1, n2, …, nK},到候选集节点的链路质量分别记为p1, p2, …, pK,则最终候选集中第i个节点的理论期望转发概率为:

$P(i) = \prod\limits_{l = 1}^{i - 1} {(1 - {p_l}){p_i}} $ (7)

s到前i-1个接收方的数据传输都没成功并在第i个节点处成功传输。然而在实际环境中,传感节点的时钟并不同步,随着时间增加,时钟之间可能产生漂移。当时间足够长时,可以将固定周期调度的各节点间的邻居发现时延近似为随机均匀分布,此时,候选集中第i个节点的期望被选中的概率只与发送方到自己的链路质量相关[9],有:

$P(i) = {p_i}/\sum\limits_{l = 1}^K {{p_l}} $ (8)

考虑经过s的流量为Qs,则在s的转发候选集策略为fs的情况下,根据式(4),其候选集中第i个节点ni的期望流量为:

${Q_{{n_i}}} = P(i) \cdot {Q_S}$ (9)

此时将问题一转化为一个最优求解问题:如何在可充电无线传感网络的每个周期中为每一个节点i选择一个最优转发候选集fi(t),以实现机会路由下的最优网络能量均衡。形式化地表示该问题为问题二:

$\mathop {\max }\limits_{{f_i}(t)} \left\{ {\mathop {\min }\limits_i {\tau _i}(t)} \right\}$ (10)
$\begin{array}{l} {\rm{s}}.{\rm{t}}{\rm{.}}{\tau _i}(t) = \frac{{P_i^{{\rm{rec}}}(t - 1){l_{t - 1}} + E_i^{{\rm{rem}}}(t - 1)}}{{e_i^{{\rm{rx}}}\sum\limits_{j,i \in {S_j}} {{q_{ji}}(t) + } \sum\limits_{k \in {S_i}} {e_{ik}^{{\rm{tx}}}{q_{ik}}(t)} }}\\ \quad \quad \sum\limits_{j,i \in {f_j}} {{q_{ji}}(t) + } {r_i} = \sum\limits_{k \in {f_i}} {{q_{ik}}(t)} \\ \quad \quad {q_{ik}}(t) = {p_{ik}}/\left( {\sum\limits_{l = 1}^{\left| {{f_i}} \right|} {{p_{il}} \cdot \left( {\sum\limits_{j,i \in {f_j}} {{q_{ji}}(t) + {r_i}} } \right)} } \right)\\ \quad \quad i \in N \end{array}$

在问题二中,与求解问题一最大的不同在于问题二中的流量分配是由机会路由下的候选集选择、节点醒来时间和优先级考虑下的流量期望决定,而不是确定的多径路由分配。这种不确定性是由机会路由的属性所决定的。与第2章同理,使用LP可以解决该问题。

4 实验结果与分析 4.1 实验设置

本节中采用以Matlab为平台的仿真实验验证能量均衡路由协议在普通可充电传感网中和低功耗可充电传感网中的效果,在500 m×500 m的场地中随机布置n-1个可充电无线传感节点,网关节点位于坐标(0, 0),采用自由空间传播损耗模型模拟不可靠链路。考虑一种一对一的简单充电场景:每个充电设备位于平均高度h=20 m的高压电线上以恒定功率在每个周期为各传感节点提供能量,能量获取由式(2) 计算得出。数据包传输和接收单位数据包能耗计算式分别为erx=eRetx=eT+εamp·dα。在低功耗场景下设置节点的调度周期和占空比分别为1 s和50%。实验的具体参数设置参考表 1。本文提出的能量均衡路由协议和低功耗场景下的分别记为能量均衡路由(Energy Balanced Routing, EBR)和低功耗能量均衡路由(EBR for Low power WSN, EBR-L),设置的实验对比对象分别为最短路径路由(Shortest Path Routing, SPR)和期望周期最短路由(Expected Duty-Cycled wakeups minimal routing, EDC)[9]。在SPR中,节点选择以节点剩余能量占电池最大电量比重倒数为基准(metric)的到达网关节点的最短路径,以实现能量均衡路由;在EDC中,考虑了低功耗和机会路由的影响,选择期望时延最小的候选集。

表 1 实验参数 Table 1 Experimental parameters
4.2 评价标准

本文以归一化网络生命周期为评价标准评估路由以网络能量均衡为目标的策略好坏,归一化网络生命周期定义为网络中所有节点的平均工作时长和总周期长度的比值(不计充电周期),以图 3为例具体解释:节点i在第一个观察周期[0, t]的前1/3充电,电量从0升至E0,随后进行数据传输、转发操作,在t1时间消耗完能量,提前结束了工作周期;在第二个观察周期中,i获得了E1能量并消耗了E1-E2能量,在此周期结束时仍有电量剩余。则i在前两个周期的归一化网络生命周期为(t1-t/3+2t/3) /(4t/3)。

图 3 节点i的电池能量周期 Figure 3 Battery energy cycle of node i

图 4描述了网络的平均归一化生命周期随着节点数目的变化,随着节点数目的增加,EBR和SPR的归一化生命周期都表现出递减趋势,这是由于节点数目的增加导致了距离网关节点更近的节点增加了更多的转发任务,导致这些节点的每个周期内工作周期减少,进而降低了网络的平均生命周期。EBR的归一化生命周期总是优于SPR,因为SPR虽然选择能量剩余多的节点作为转发节点,在一定程度上缓解了网络负载不均衡,但是EBR更多地考虑了多个转发节点的负载分配对于网络均衡的影响而不仅仅是单个下一跳,故EBR能够实现更好的能量均衡。

图 4 归一化生命周期随节点数目变化 Figure 4 Change of the normalized lifetime with the number of nodes
4.3 结果分析

图 5描述了低功耗场景下的网络平均归一化生命周期随着节点数目的变化,与图 4相似呈递减趋势。EBR-L优于EDC的原因是后者更多地考虑了时延而非能量均衡。值得注意的是,与图 4相比,EBR-L的归一化生命周期均优于EBR,这是因为EBR的场景从广义上来说是多路径路由而不是机会路由,而在低功耗的机会路由下,EBR-L在没有任务时可以进入休眠状态,从而节约了空闲侦听的能量。

图 5 低功耗场景归一化生命周期随节点数目变化 Figure 5 Change of normalized lifetime with the number of nodes in low power scenario

对比图 4~5,可以发现EBR比EBR-L在相同的配置下具有更长的网络生命周期,这是因为首先本文在实验中只考虑收发数据包的能耗,其次从信息论角度考虑,EBR使用全局网络信息进行优化,而EBR-L是分布式的路由算法,前者比后者拥有更多的信息故更优。

考虑两种算法的复杂度,EBR采用线性规划算法,时间复杂度为n的多项式级别;EBR-L在前者的基础上增加了关于转发候选集的约束条件,搜索空间大于EBR,但仍为n的多项式级别时间复杂度。

5 结语

为解决可充电无线传感网络中的能量均衡路由问题,分别针对非低功耗场景和低功耗场景,本文提出基于多路径路由和机会路由的路由协议。前者根据充电速率、自身电池剩余电量、接收和发送数据包的单位能耗等信息,通过全网的线性规划为每个参与转发的节点的候选集规划链路流量;后者为每个转发者选择一个能耗最优的候选集,在机会路由框架下延长网络寿命。实验结果表明,提出的两种路由算法能够有效地实现网络均衡。接下来将针对复杂移动场景下的可充电无线传感网络的路由问题进行研究。

参考文献
[1] 夏先进, 李士宁, 张羽, 等. 一维传感网中混合数据传输的能量均衡[J]. 软件学报, 2015, 26(8): 1983-2006. ( XIA X J, LI S N, ZHANG Y, et al. Energy balance of mixed data transmission in 1D sensor networks[J]. Journal of Software, 2015, 26(8): 1983-2006. )
[2] 吴华君, 张自力, 李卫. 一种适用于煤矿井下无线传感网的能量均衡路由协议[J]. 计算机科学, 2011, 38(4): 145-150. ( WU H J, ZHANG Z L, LI W. Energy-balanced routing protocol for wireless sensor networks in coal mine[J]. Computer Science, 2011, 38(4): 145-150. )
[3] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//HICSS'00:Proceedings of the 33rd Hawaii International Conference on System Sciences. Washington, DC:IEEE Computer Society, 2000:8020.
[4] 曹立志, 陈莹. 基于学习自动机的无线传感网能量均衡分簇算法[J]. 传感技术学报, 2013, 26(11): 1590-1596. ( CAO L Z, CHEN Y. Energy balanced clustering algorithm based on learning automata for wireless sensor network[J]. Chinese Journal of Sensors and Actuators, 2013, 26(11): 1590-1596. doi: 10.3969/j.issn.1004-1699.2013.11.022 )
[5] 米志超, 周建江. 一种能量均衡的无线传感网络生命期优化算法[J]. 系统工程与电子技术, 2008, 30(12): 2477-2480. ( MI Z C, ZHOU J J. Energy-balanced optimization algorithm for maximizing network lifetime in wireless sensor networks[J]. Systems Engineering and Electronics, 2008, 30(12): 2477-2480. doi: 10.3321/j.issn:1001-506X.2008.12.046 )
[6] ANGELOPOULOS C M, NIKOLETSEAS S, RAPTIS T P, et al. Efficient energy management in wireless rechargeable sensor networks[C]//MSWiM'12:Proceedings of the 15th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems. New York:ACM, 2012:309-316.
[7] MAO S B, CHEUNG M H, WONG V W S. Joint energy allocation for sensing and transmission in rechargeable wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2014, 63(6): 2862-2875. doi: 10.1109/TVT.2013.2295603
[8] 杜欣. WSN低功耗算法在电力系统中的应用[J]. 电力系统通信, 2012, 33(4): 62-66. ( DU X. Application of WSN technology based low-power consumption algorithms in power system[J]. Telecommunications for Electric Power System, 2012, 33(4): 62-66. )
[9] GHADIMI E, LANDSIEDEL O, SOLDATI P, et al. Opportunistic routing in low duty-cycle wireless sensor networks[J]. ACM Transactions on Sensor Networks, 2014, 10(4): Article No. 67.
[10] GU Y, HE T. Dynamic switching-based data forwarding for low duty-cycle wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(12): 1741-1754. doi: 10.1109/TMC.2010.266
[11] 赵灿明, 李祝红, 闫凡, 等. 电力通信网络中负载均衡的路由协议[J]. 计算机应用, 2016, 36(11): 3028-3032. ( ZHAO C M, LI Z H, YAN F, et al. Load balanced routing protocol in electric power communication networks[J]. Journal of Computer Application, 2016, 36(11): 3028-3032. doi: 10.11772/j.issn.1001-9081.2016.11.3028 )