戴东海,冯 辉,杨 涛,胡 波

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



无线充电WSN中低维护频率的路由与能量补充策略*

戴东海,冯 辉,杨 涛,胡 波*

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

由于传感器节点的电池容量有限,为使网络可持续运行,可利用无线能量传输技术对节点充电。在使用无线充电设备为传感器周期性充电的场景中,由于现有研究很少考虑节点的频繁充电带来的额外成本问题,以维护频率作为成本的度量,对节点实行按需维护,通过联合优化每个节点的路由和能量补充策略,使充电设备对节点的总维护频率最小。仿真结果表明,算法可以减小网络节点充电的频率,同时缩短充电设备的行驶路程,最终降低网络维护的成本。

无线传感器网络;能量优化;无线能量传输;路由策略;节点维护

无线传感器网络WSN(Wireless Sensor Network)由一系列的传感器节点组成,部署在目标区域内进行数据采集、传输和处理。许多应用场景都要求网络长期稳定运行,如环境监控、入侵检测、目标跟踪等。由于传感器的电池容量有限,WSN的能量优化问题引起了广泛关注[1]。网络的路由策略[2]决定了数据从源节点到汇聚节点的传递过程,是改善网络能耗和寿命的一个重要手段。文献[3-4]基于最大生命期路由,联合优化了路由和电池容量分配方案,进一步提高网络寿命。文献[5]提出了一种兼顾电池电量和传输可靠性的路由策略。然而,能耗与寿命的优化不能使网络长期稳定的运行,节点能量最终会耗尽。

为了使网络具备可持续运行能力,需要在网络运行过程中为传感器补充能量,对此目前主要有组件置换、能量收集和无线能量传输3种方案。组件置换[6]即人工更换低电量的传感器或其电池,其操作成本高,且在置换过程中节点必须暂停工作。能量收集技术[7]使传感器可以从环境中直接获取能量,如太阳能、风能等。文献[8]研究了能量收集场景下的一种能耗均衡的路由算法。然而,能量收集的速率与装置体积、成本之间存在矛盾,而且极度依赖于环境因素,难以保证稳定性。近年来,无线能量传输的研究取得了突破,与能量收集不同,它是一种主动的能量控制方案,不受环境影响,且不要求视距传输。Kurs等人[9]提出了基于磁共振的无线能量传输技术,并验证了中距离能量传输的可行性。为了存储无线收集的能量,传感器通常装配体积轻便、能量密度高的可充电锂电池[10]。无线能量传输已被用于各个领域,如无线充电手机、可充电式心电监护设备[11]等。当传感器被放置在森林、容器内部等场景时,无线能量传输相比另外两个方案的可实现性更大。

无线能量传输为WSN的能量补充提供了新的思路,已有不少研究提出可利用高容量的移动充电设备,为传感器进行无线充电。文献[12]优化了充电设备的调度和行程问题,并将其归结为旅行商问题。Tong等人[13]提出了一种最优节点部署和路由策略来降低能耗。文献[14]通过部署多个充电设备,并进行设备间协作来扩大充电覆盖范围。Xie等人[15]研究节点的周期性充电的问题,提出一种路由方案,使充电车的休眠时间比例最大。

现有文献很少考虑到以下事实。一方面,网络的维护需要成本,包括充电车行驶和为节点充电的能耗,而其自身携带的能量有限,所以在一个周期内维护所有节点不现实;另一方面,各节点的能耗速率差异较大,通常靠近汇聚节点的节点能耗更大,而偏远节点不必在每个维护周期内都进行充电。综上所述,传感器应该在必要时才被维护。本文的贡献是在WSN的能量补充问题中,首次考虑节点的按需维护问题。本文以充电频率作为维护成本的度量,提出一种路由与能量补充策略联合优化的方法,在网络可持续运行的条件下,最小化移动充电设备对各节点的充电频率,有效降低网络的维护成本。

1 系统模型

1.1 网络模型

考虑一个包含N个节点的传感器网络,令S={1,2,…,N}为传感器节点的集合。每个传感器都配备一个容量为Emax的可充电锂电池,若某个传感器的电池能量低于Emin,则它将无法工作。另外,网络中有一个固定位置的汇聚节点(不包括在集合S中),负责汇总并处理数据,有持续的电源供给。所有传感器节点和汇聚节点都在一个二维平面上。

每个节点i∈S以速率Ri产生数据。所有节点的数据都经过多跳路由传递到汇聚节点,宏观上表现为网络数据流。令fij为从节点i到节点j的数据流,fiB为节点i到汇聚节点B的数据流。对于每个节点,遵循以下流量平衡约束:

(1)

等式左边是节点i发送给其他节点和汇聚节点的数据流,等式右边是节点i接收到的数据流,包含它自身采集和其他节点发送的数据流。

传感器在发送、接收和采集的过程中会消耗能量。令pi为节点i消耗的总能量,能量消耗模型如下[4]:

(2)

其中,ρ是节点i接收一个比特数据消耗的能量,Cij和CiB分别为节点i发送一个比特给节点j和给汇聚节点所消耗的能量。Cij和CiB都是与距离有关的系数。例如,当两个节点距离Dij(i,j∈S)增大,Cij将服从以下非线性模型增大[17]:

(3)

其中,β1、β2、α都是模型参数。

1.2 能量补充机制

为了给节点提供无线能量传输,在网络中部署一个移动充电设备MC(Mobile Charger)。充电设备的含义包括了车辆、船只等交通工具或者工作人员。服务中心提供对MC的充能和维护,它通常与汇聚节点在同一地点或者附近。在每次充电过程中,MC首先离开服务中心,以速度V行驶,当到达节点i时,对其进行持续ti的无线充电,能量传输速率为U。之后MC将前往下一个节点。当需要充电的节点都被维护完毕后,MC回到服务中心,休息并准备下一次出发。本文引入如下术语描述此充电过程。

定义1 定义调度周期为MC相邻两次从服务站出发的间隔,记为T0。它由3部分组成:行驶时间、充电消耗时间以及在服务中心休息的时间。相应地,定义调度频率为调度周期的倒数,记为q0≡1/T0。

定义2 定义更新周期为每个传感器节点相邻两次开始充电的间隔,记为Ti,i∈S。相应地,定义更新频率为更新周期的倒数,记为qi≡1/Ti。

假设节点以均匀的间隔获得能量补充。从MC的角度,在一个调度周期内只访问部分节点。而从节点的角度,其能量经过若干个调度周期被补充一次。若某节点在每个调度周期都被充电,则其更新周期与调度周期相同。调度周期和更新周期的关系为:

Ti=miT0(i∈S,mi=1,2,3,…)

(4)

其中mi是一个正整数,表示节点i的一个更新周期内包含调度周期的个数。

图1展示了两个节点的更新周期示意图,其大小分别为T0和2T0。不失一般性,下面只考虑节点能量被充满的情况。在更新周期的开始,各节点的初始能量不相同,记为Ei。

图1 节点的更新周期示意图

为了保证能量可持续性,节点的更新周期应满足两个条件。第1,更新周期开始与结束时,节点的能量相等。换言之,更新周期内节点充入的能量应该等于消耗的能量,即

Ti·pi-U·ti=0(i∈S)

(5)

第2,在一个更新周期中,任何节点都有足够能量保持运作。实际上,节点i能量最低的时刻正是MC刚开始对其充电的时刻,记为ai,保证此时能量ei(ai)大于阈值Emin即可。对于节点i的一个更新周期,从充满能量直到下一次开始充能共经过时间(Ti-ti),期间节点的能耗速率是pi,则能量最小值为Emax-(Ti-ti)·pi。最小能量不低于阈值,得

Emax-(Ti-ti)·pi≥Emin(i∈S)

(6)

2 路由与能量补充策略

为了降低维护成本,应使节点的总更新频率最小,即在一定时间内,移动充电设备对节点的总维护次数最少。一种简单策略是先选定某种路由策略,确定各节点的能耗速率,由此算出节点各自的最小更新频率。然而,这样未必能得到最优结果,因此本文提出一种路由策略与更新频率联合优化的方法。

2.1 最小更新频率路由

本节提出最小更新频率路由MRFR(Minimum Renewal Frequency Routing),建模为优化问题。优化目标是使节点的更新频率之和最小化,优化变量为网络数据流fij与fiB、每个节点的能耗速率pi、更新周期Ti、更新频率qi、节点充电时间ti。

(7)

其中约束条件依次是流量平衡方程(1)、能耗方程(2)、更新频率定义、调度周期与更新周期的关系式(4)、节点的能量更新周期需满足的两个条件式(5)、式(6)。比例因子μ控制充电时间占据更新周期的比例,本文规定0<μ≤0.5,即充电时间不能大于耗电时间。下述定理反映了联合优化问题MRFR的最优性。

由于式(7)的约束存在变量乘积的形式,需要进行适当转换。首先,考虑到Ti=miT0中存在整数,且T0仅在这里出现,所以先忽略此约束,后续步骤将选择合适的T0并调整Ti。接着,令ηi=ti/Ti(i∈N),消去式(7)中所有的ti与Ti,并将pi用其他变量表示,得到

(8)

其中优化变量为fij与fiB,ηi和qi。

注意到式(8)中的能量阈值约束是关于ηi的二次凹不等式约束,在凸优化[16]框架下难以求解,因此我们采取分段线性逼近的方法,将二次约束转换为若干个线性约束。

(9)

(10)

(11)

(12)

2.2 充电设备的调度

相比原问题式(7),问题式(8)松弛了更新周期与调度周期是整数倍的约束式(4)。本节通过选取调度周期T0并调整式(8)求得的更新周期Ti,得到一组满足MRFR式(7)的次优解。

网络中拥有最小更新周期(即最大更新频率)的节点称为瓶颈节点,通过该节点决定移动充电设备的调度周期:

(13)

通常选择K=1,即在每一个调度周期内,瓶颈节点都会被充电。

(14)

(15)

(16)

经过离散化后,网络总更新频率将略有提高。整数K越大,意味着调度周期越小,离散与连续情况越接近。

当MC获得了每个调度周期内需维护的节点列表后,应访问相应的节点并进行能量传输,同时希望行驶路程最短以减小额外开销。因此,在一个调度周期内,MC的最佳行驶路径为服务中心与待维护节点组成的最小汉密尔顿回路,可由旅行商问题[18]求出。

3 仿真分析

3.1 路由性能

图2展示了每个节点的位置,以及MRFR算法得到的路由数据流图。其中,圆点表示普通传感器节点,中央三角形点表示汇聚节点。节点间连线的粗细程度正比于数据流的大小。表1列出了40个节点的采集速率、能量消耗速率、更新频率。其中,更新频率的单位是1/mon,即各个节点在一个月内的总维护次数。在图2和表1的测试条件下,本算法在MATLAB平台下的运行时间约为1.13 s,其中最优化问题式(9)利用MOSEK求解,线性逼近的分段数l为8,解优化问题耗时约0.73 s。

图2 路由策略示意图

表1 节点的采集速率、能耗速率、更新频率

下面将本文的路由与最大生命期路由MLR、AODV路由进行对比。图3展示了不同的网络范围(节点平均间距)下,几种路由策略所得的节点总更新频率。对比分析得:(1)对比MRFR最佳性能下界,和以K=1选取更新周期,性能的差距并不大。(2)AODV是一种分布式按需路由标准协议,其路径类似最小跳数路由,更新频率大于MRFR的结果。(3)MLR虽能使网络一次充满电后的寿命最长,然而维护频度过大,不利于可持续运行。

图3 不同网络面积下的路由性能对比

3.2 调度性能

根据MRFR所得的更新周期,可设计充电设备的调度策略,即选择每个调度周期中需要维护的节点集合。为了便于举例,我们设定更新周期与调度周期的比值只可能是{1,2,4,8}之一。MC的行驶速度V=5 m/s。

表2给出了一种可能的调度策略,每个节点等间隔地被维护,并且各个调度周期所需维护的节点个数大致相同。MC的调度周期为T0=9528.6 s=2.65 h。节点的总充电时间由各节点的能量消耗速率与更新周期共同决定。MC在一个调度周期内的总行驶时间与所选择节点、行驶路径以及行驶速度密切相关。

表2 所需维护的节点及调度性能

下面将本文与文献[15]中提出的调度策略进行对比。图4测试了两种策略在不同的网络区域边长下,MC的行驶时间占整个调度周期的比例η。根据表2,各调度周期的情况不同,所以仿真时取各周期的平均值。通过图4可发现:

(1)当网络面积增大时,η会急剧增加。一方面,节点平均间距的增大导致发送数据所需的能耗非线性地增大,因此网络维护更频繁,更新周期减小;另一方面,网络面积的增大也使MC的行驶路程和时间增加。综上,行驶时间与调度周期的比值η会显著增加。

(2)本文策略的η在不同网络面积下都优于对比文献,这是因为后者要求MC在每个周期内跑遍所有节点,而MRFR策略只需要维护部分节点,旨在降低网络的维护频率。从长期角度来看,MRFR减小了MC在各调度周期中的平均行驶路程。

图4 不同网络面积下,MC行驶时间的对比

4 结论

传统无线传感器网络的寿命受制于节点有限的电量,而无线能量传输技术为网络的可持续运行提供了新的思路。在移动充电设备周期地为节点无线充电的场景下,本文针对现有研究很少考虑的网络维护成本的问题,引入调度周期和更新周期的概念,使传感器实现按需充电。本文提出了MRFR路由策略,以最小化全网的维护频率。通过对最优化问题的合理松弛,本文算法克服了节点选择作为组合优化问题难以计算的缺陷。理论分析与仿真结果表明,MRFR相比其他文献的方法,能有效降低节点的维护频率,同时也缩短了移动充电设备的行驶路程,减小了对整个网络的维护开销。接下来的工作是将能量收集技术结合到本文无线充电的框架中,研究如何得到最优的混合式网络维护策略。

[1] Rault T,Bouabdallah A,Challal Y. Energy Efficiency in Wireless Sensor Networks:A Top-Down Survey[J]. Computer Networks,2014,67:104-122.

[2]Shah R C,Rabaey J M. Energy Aware Routing for Low Energy Ad Hoc Sensor Networks[C]//Wireless Communications and Networking Conference(WCNC). IEEE,2002(1):350-355.

[3]蒋紫东,冯辉,杨涛,等. 最大化WSN寿命的电量分配与路由联合优化策略[J]. 传感技术学报,2014,27(4):536-543.

[4]Chang J H,Tassiulas L. Maximum Lifetime Routing in Wireless Sensor Networks[J]. IEEE/ACM Transactions on Networking(TON),2004,12(4):609-619.

[5]Vazifehdan J,Prasad R V,Niemegeers I. Energy-Efficient Reliable Routing Considering Residual Energy in Wireless Ad Hoc Networks[J]. IEEE Transactions on Mobile Computing,2014,13(2):434-447.

[6]Tong B,Wang G,Zhang W,et al. Node Reclamation and Replacement for Long-Lived Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2011,22(9):1550-1563.

[7]Sudevalayam S,Kulkarni P. Energy Harvesting Sensor Nodes:Survey and Implications[J]. IEEE Communications Surveys and Tutorials,2011,13(3):443-461.

[8]姚玉坤,王冠,任智,等. 能耗均衡的自供能无线传感器网络分簇路由算法[J]. 传感技术学报,2013,26(10):1420-1425.

[9]Kurs A,Karalis A,Moffatt R,et al. Wireless Power Transfer via Strongly Coupled Magnetic Resonances[J]. Science,2007,317(5834):83-86.

[10]李向阳,石德乐,李振宇,等. 无线能量传输系统能源管理技术研究[J]. 空间电子技术,2013,10(3):61-65.

[11]Yakovlev A,Kim S,Poon A. Implantable Biomedical Devices:Wireless Powering and Communication[J]. IEEE Communications Magazine,2012,50(4):152-159.

[12]Peng Y,Li Z,Zhang W,et al. Prolonging Sensor Network Lifetime Through Wireless Charging[C]//2010 31st IEEE Real-Time Systems Symposium. IEEE Computer Society,2010:129-139.

[13]Tong B,Li Z,Wang G,et al. How Wireless Power Charging Technology Affects Sensor Network Deployment and Routing[C]//2010 IEEE 30th International Conference on IEEE Distributed Computing Systems(ICDCS). IEEE,2010:438-447.

[14]Zhang S,Wu J,Lu S. Collaborative Mobile Charging for Sensor Networks[C]//2013 IEEE 10th International Conference on Mobile Ad-Hoc and Sensor Systems. IEEE,2012:84-92.

[15]Xie L,Shi Y,Hou Y T,et al. Making Sensor Networks Immortal:An Energy-Renewal Approach with Wireless Power Transfer[J]. IEEE/ACM Transactions on Networking(TON),2012,20(6):1748-1761.

[16]Boyd S P,Vandenberghe L. Convex Optimization[M]. Cambridge University Press,2004:152-160.

[17]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.

[18]Albayrak M,Allahverdi N. Development a New Mutation Operator to Solve the Traveling Salesman Problem by Aid of Genetic Algorithms[J]. Expert Systems with Applications,2011,38(3):1313-1320.

戴东海(1990-),男,硕士研究生,研究方向为无线传感器网络,ddai12@fudan.edu.cn;

冯辉(1980-),男,讲师,主要研究方向为无线传感器网络,分布式信号处理理论及应用,hfeng@fudan.edu.cn;

杨涛(1970-),男,副教授,主要研究方向为无线通信理论与信号处理,taoyang@fudan.edu.cn;

胡波(1968-),男,教授、博士生导师,主要研究方向为数字信号处理,数字通信,bohu@fudan.edu.cn。

ARoutingandEnergyRenewalPolicywithLowMaintenanceFrequencyforWireless-RechargingWirelessSensorNetwork*

DAIDonghai,FENGHui,YANGTao,HUBo*

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

Since sensors have limited battery capacities,in order to keep the network functioning continuously,nodes can be charged with the help of wireless power transfer technology. Under the scenario that nodes are periodically charged by a mobile charger in the network,as other researches rarely consider the extra cost when maintaining the sensor nodes,we propose the criteria of maintenance frequency so that nodes are maintained only if necessary. By jointly optimizing routing policy and energy renewal policy of the nodes,we minimize the total maintenance frequency of all nodes. Simulation results show that our algorithm can minimize the charging frequency of the nodes as well as the travelling distance of mobile charger,and finally reduce the cost of network maintenance.

wireless sensor networks;energy efficiency;wireless power transfer;routing policy;node maintenance

项目来源:教育部博士点基金(20120071110028)

2014-06-14修改日期:2014-08-24

10.3969/j.issn.1004-1699.2014.10.017

TP393

:A

:1004-1699(2014)10-1394-07