无线可充电传感器网络能耗分级充电策略*

吴宝瑜,万 鹏,王高峰,程瑜华

(杭州电子科技大学电子信息学院,杭州 310018)

无线传感器网络是由大量具有传感、数据处理和无线通信能力的传感器节点组织成为的一个网络结构[1]。网络通过传感器采集所需要的物理信息,发送给基站中心进行数据处理,进而传输给信息采集者。大部分的传感器采用电池提供能量,为了传感器网络能够持续有效地工作,必须定期地对电池进行更换,避免因电池能量耗尽后导致传感器失效。但有些传感器网络的部署环境较恶劣,导致传感器的电池更换不方便。在一些研究中,为延长无线传感网的网络寿命,对传感器网络采用更好的组网方式和能量均衡算法[2],尽可能地减少能量消耗,但这些方式只是减缓了能量耗尽的过程,并不能从根本上解决能量不足的问题。为应对这一问题,具有无线充电功能的传感器网络,即无线可充电传感器网络应运而生[3-5]。对于无线可充电传感器网络,当前采用的无线充电方式可分为静态充电方式[6-7]和动态充电方式[8-14]两种。对于静态充电方式,可以看作充电源是固定不动的,传感器接收来自固定充电源的电磁能量,但由于现有远距离电磁辐射充电技术本身的局限性,很难克服因距离远所带来的能量传输衰减问题。随着磁耦合谐振充电技术的快速发展,近距离快速高效地给传感器无线充电技术越来越成熟[15-17]。通过配备高容量电池的移动小车移动至传感器附近给传感器充电的动态充电方式受到了很多人的关注。文献[8]提出了一种移动充电小车的协作调度算法,该算法是一种时空计费调度算法,通过调整传感器的充电优先顺序,减少死亡节点的个数,来保证整个传感器网络的有效运行;文献[9]提出在大规模无线传感网中,根据不同传感器节点的能量需求,优化充电小车的个数,尽可能地减少充电小车的数量使其达到最优;文献[10]提出充电吞吐量的概念和一种新的充电范例,为移动充电小车找到最佳的充电闭合路径,使其包括最多的传感器节点数量,即小车在周期T的时间内,能够给尽量多提出充电要求的节点进行充电。文献[11]将小车的路径规划问题论述为一个旅行商问题TSP(Traveling Salesman Problem),并进行分析建模。文献[12]基于充电小车能量有限的前提,将整个传感器网络分为不同的充电区域,充电小车通过给不同区域的传感器进行充电,对整个传感器网络进行能量补充。文献[13]结合传感器网络中的通信抗干扰技术和能量补给策略,对传感器网络进行分簇,由于簇头节点能量消耗较大,先对簇头节点进行能量补充,再对一般节点进行能量补充,能够使得传感器网络更好地维持其生命周期。文献[14]提出一种虚拟骨干网的移动能量补给策略,给特定骨干节点进行充电的方式补充能量消耗较大的传感器节点。以上的动态充电算法规划中,无论是增加充电小车的数量还是考虑时空关系,都是为了解决传感器能耗特别大导致其生命周期很短,或者是传感器网络规模较大导致单个充电小车满足不了充电需求的问题。但有研究表明,传感器的能耗一般很低,传感器的生命周期相对较长,对于充电时效性并无非常苛刻的要求,而且实际的传感器网络中传感器的能耗值差异较大[18]。本文着重研究在传感器网络能耗分布不均的情况下,通过对传感器能耗进行分级,结合蚁群算法[19]对路径的计算,优化充电小车移动总路径,从而减小充电小车的损耗,提高经济性。

1 问题描述

1.1 模型建立

在一个L×L大小的二维空间中,部署了一个无线可充电传感器网络,其中包括N个无线可充电传感器、一个移动无线充电小车、网络中心位置的基站服务站。网络模型如图1所示。整个无线可充电传感器网络构成一个无向图G=(V,E),V={v0,v1,v2,…vN}表示基站和传感器集合,v0表示基站位置,vi表示传感器位置,E表示传感器两两之间的链路集合。

每个传感器的能耗值各不相同,用Pi表示。在无线传感器网络中,无线传感器的能量消耗功率Pi是与传感器数据的发送量和接收量以及信息采集直接相关的,模型如图2所示[11]。

图2 传感器能量消耗模型

图2中,假设在t时刻,i传感器向j传感器发送数据的速率为gij(t)bit/s,发送数据的功率因子为Cij,单位为J/bit,那么对于节点i来说,t时刻用于发送数据的功率Ps(t)由式(1)表示,同样的在t时刻,节点i接收k节点发送来的数据的速率为gki(t)bit/s,相应的功率因子为ρ,单位为J/bit,那么在t时刻接收数据的功率Pr(t)由式(2)表示,Pc(t)为传感器采集信息的能量消耗功率,则在t时刻,i传感器的能量消耗功率Pi(t)由式(3)表示:

(1)

(2)

Pw(t)=Ps(t)+Pr(t)+Pc(t)

(3)

从上文的传感器能量消耗模型可知,每个传感器由于发送与接收数据量并不都是一致的,会产生不同的能量消耗率,则每个传感器的能量状态都是不同的,具有不同的能量补充需求。

为避免传感器能量耗尽导致网络失效,充电小车需定时地给网络中能量小于阈值ETH的传感器进行一对一的能量补充。若用ES表示传感器当前电池容量,则传感器生命周期为Ti,易得Ti=(ES-ETH)/Pi。传统的传感器网络小车充电方式为遍历全部的传感器节点,根据实际的需求进行选择性充电。但考虑到实际传感器网络中传感器能耗值的差异,可选择能耗值相近的传感器作为一个集合,将整个传感器网络分为若干个包含不同能耗级别传感器的集合,充电小车每次给不同传感器节点集合进行充电。图3为充电小车给某一能耗级的传感器充电的示意图。

图3 小车给某一能耗级传感器充电示意图

1.2 问题定义

我们研究的问题为一个充电小车周期性充电问题:在一个周期性的时间T内,根据传感器能量的需求,分不同的轮数给传感器进行能量补充,直至能量需求最小的传感器节点都被补充过一遍能量。其中充电周期T的定义由式(4)得到。

T=Tp+Tvac+Tc

(4)

式中:TP表示小车充电中移动消耗的总时间;Tvac表示充电小车停靠在服务站时间;Tc表示停留在传感器节点充电的时间,优化的目标为最大化驻站时间比Tvac/T。文献[11]证明了最大化驻站时间比就是最小化移动时间,假定充电小车的移动速度是一定的,忽略充电时间,则最终就是优化移动路径使其最小的问题。总移动路径用LTSP来代替,那么问题就转化为TSP问题[20],即小车在对传感器节点进行充电过程的路径规划问题,式(4)转变为式(5):

T=TTSP+Tvac+Tc

(5)

式中:TTSP为充电小车在充电过程中移动的时间。于是,在一个充电周期内,保证每个传感器节点都能够得到能量补充的情况下。由于充电小车并不是一次性遍历完所有的传感器节点,因此每一次遍历的过程都可看作一个TSP问题,总移动路径即为每次遍历路径的总和。最小化充电小车的移动总路径LTSP成为主要优化目标。

在小车移动时间TTSP内,传感器也会进行能量消耗的过程。为了保证没有传感器出现能量耗尽的情况,将前文的能量阈值ETH的确定进行充电约束,即保证在小车移动时间内,每个传感器的能量阈值生命周期能够大于总充电移动时间。如式(6)所示:

ETH/Pi>TTSP

(6)

2 算法分析和设计

2.1 算法思想

充电小车对传感器网络进行路径规划的传统算法优化中,小车通常会一次性遍历所有传感器节点,进而根据节点的充电需求决定是否对节点进行能量补充,这种按需充电的方式会大大增加小车不必要的移动能量消耗。而在实际的传感器网络中,能耗分布是很不均衡的。基于此,在相同的时间周期内(即所有传感器节点都补充过一遍能量的时间内),将能量补充路径分成多个部分进行,可使得小车遍历路径值有较优的计算结果。根据传感器网络的各传感器的能耗差异,给传感器网络分为能耗级别不同的集合,基于此,本文提出非固定周期算法和固定周期转移算法两种算法。对于非固定周期算法,充电小车根据每个能耗级别中传感器最小的周期进行充电,充电小车每次出动的时间间隔是不固定的。针对非固定周期算法出动频数较多的劣势,进一步提出一种固定周期算法,充电小车每次出动的时间是固定的。本文在固定周期算法中,又创新性地提出了将部分能耗级别低的传感器向能耗高级别高的传感器集合转移的优化算法,称为固定周期转移算法,优化总充电小车遍历路径值。

2.2 算法设计

2.2.1 能耗分级

给定传感器集合V之后,给出对应每个传感器的能耗值Pi,则每个传感器的生命周期Ti=(ES-ETH)/Pi,找出其中最大值Tmax和最小值Tmin,计算(Tmax-Tmin)/Tmin的值,并向上取整可得待充电的传感器集合的分级数,记为k。由此可得能耗分级后的传感器集合VV={VV1,VV2,…,VVk},VVk表示集合V中生命周期值在kTmin和(k+1)Tmin之间的传感器节点。

2.2.2 非固定周期算法

在进行能耗分级之后,找出网络中具有最小剩余生命周期传感节点所在的能耗级,充电小车对此能耗级中的所有传感器采用蚁群算法[19]进行充电路径计算。第i个传感节点的剩余生命周期定义为(Ei-ETH)/Pi,其中Ei为能耗级中第i个传感节点的剩余电池能量。在充电小车完成一次充电后,算法将更新网络中各传感节点的剩余生命周期,并重新寻找具有最小剩余生命周期传感节点的能耗级,然后进行充电。算法过程描述如下:

输入:{v0,v1,v2,…vN},Pi,ES

输出:LTSP

①根据(ES-ETH)/Pi计算生命周期;

②计算(Tmax-Tmin)/Tmin的值,并向上取整,求得能耗分级数k,以及相应的能耗分级后的传感器集合VV={VV1,VV2,…VVk};

③根据(Ei-ETH)/Pi求得每个传感节点的剩余生命周期;

④找出具有最小剩余生命周期传感节点的能耗级VVi并给其中的传感器充电;

⑤用蚁群算法ACATSP(VVi)计算每次充电路径值;

⑥重复步骤③,④,⑤直至全部的节点都被补充过一遍能量;

⑦求小车总遍历路径LTSP=∑ACATSP(VVi)

算法中每次选取的VVi是根据具体能耗级的最小剩余生命周期确定的。从能耗级最低的VV1开始,直到能耗级最高的VVk被充电的过程中,有些VVi可能被多次充电,即出现充电小车的出动次数较多,导致充电移动资源浪费的问题。为减小这种移动资源的浪费,提出了固定周期转移算法,进一步优化小车总移动路径。

2.2.3 固定周期转移算法

第1阶段算法描述如下:

输入:{v0,v1,v2,…vN},Pi,ES

输出:LTSP

①根据(ES-ETH)/Pi计算生命周期;

②计算(Tmax-Tmin)/Tmin的值,并向上取整,求得能耗分级数k,以及相应的能耗分级后的传感器集合VV={VV1,VV2,…,VVk};

③求得小车每次遍历的集合VX={VX1,VX2,…,VXk};

第2阶段:遍历一遍VX集合中的各个VV变量,找出只出现一次的VV集合,假设有M个,按照VVi的下标值从小到大排列并依次由集合C′1,C′2,…,C′M来代替,随后按下标从大到小地进行集合间传感器节点转移。具体过程如下:初始化i=1,将C′M中的传感器元素每次转移i个到C′M-1中,每转移一次,计算一次遍历的总路径值LTSP,将路径值减小的转移节点记录下来;令i=i+1,在路径值减小的转移节点中每次转移i个到C′M-1中,同样计算每次遍历的总路径值;这样,直到找到最小路径值对应的最优转移节点及个数。

然后对C′M-1和C′M-2进行上述类似的转移过程,直至得到最优路径下的最优转移节点及个数;最后,直到完成C′2到C′1的转移过程。取最优的转移组合以及在这个转移组合下的最优转移节点,将此时的最优路径数LTSP作为最终算法优化后的路径数。

第2阶段算法描述如下:

输入:VX

输出:LTSP

①找出VX集合中只出现一次的VV变量,个数记为M;将每个变量值从小到大排序并由C′1,C′2,…,C′M代替;

②初始化i=1,将C′M中的元素每次i个转移到C′M-1中,每转移一次计算一次LTSP值,记录路径值减小的转移节点;

③令i=i+1,从路径减小的元素里每次转移i个节点,直到找出最小路径值下的最优节点转移数;

④对C′M-1和C′M-2重复步骤2和步骤3的过程,得到最优节点转移数,直到计算完C′2和C′1;

⑤对比每个转移组合下的路径值,选取最优转移组合下的转移节点数;

⑥更新VX集合,得到此集合下最小值LTSP。

这里要说明的一点是,倘若经过第2阶段算法的转移规则之后,并不能使小车的路径数有所减少,不进行第2阶段的转移过程。

为了便于理解第2阶段的转移过程,下面用一个具体的例子来说明节点转移算法的转移过程:

无线可充电传感器网络中有一个位于中心的基站服务站和10个传感器节点v1～v10,根据能耗值的不同,将整个传感器网络分成了3个能耗级别VV1,VV2,VV3。3个能耗级别所对应的充电周期为T,2T,3T,于是对于充电小车每次遍历的路径集合分别为VX1=VV1,VX2=VV1∪VV2,VX3=VV1∪VV3,如图4所示为不同能耗级传感器集合,图5(a)～(c)为一个周期内总共3次不同的遍历路径示意图。

图4 不同能耗分级图

图5 小车充电遍历路线示意图

图6(a)～(c)为进行第2阶段算法的转移规则之后得到的路径遍历示意图。转移之后的节点,由于能耗小于集合中其他的传感器节点,即生命周期大于其他的节点,则不影响其本身的能量补充过程。从图中可以看出,由于v7特别靠近v3v4,将原属于VV3的v7节点转移到VV2中,可以减小路径值。图5(a)和图6(a)路径相同,图5(b)和图6(b)差距很小,转移前与转移后的路径值主要为图5(c)和图6(c)的大小比较,很明显后者较小,即转移后的路径值会变小。当传感器节点数较多时,可以使用节点转移规则找出最适合的转移方式。

图6 转移节点后小车充电遍历路线示意图

2.3 算法复杂度分析

本文研究的问题本质是一个NP-hard问题。能耗分级阶段,主要是根据能耗进行分类,只要计算完传感器节点的个数即可,算法时间复杂度为O(1)。在求解TSP问题阶段,时间复杂度很大,采用蚁群算法,能够较好地解决TSP问题,但是算法的复杂度并没有降低,其复杂度为O(2n·n2)[20]。但是在此过程中由于采用了分级策略,减小了每次的n值,能够减小算法的计算量。在节点转移过程中,只考虑上一级向下一级逐级转移的节点转移方式,由于是k级的能耗分级,规则定义可转移所有节点,则所需的时间复杂度为O(n2)。

3 仿真实验与结果分析

为验证本文所提出的非固定周期算法和固定周期转移算法的有效性,这里将它们与传统周期遍历算法[14]进行了比较。参照文献[14]中对传感器网络中的参数设置,将传感器网络布置在1 000 m×1 000 m 大小的正方形区域内,传感器的电池容量为10 kJ,基站服务站的位置和小车的初始位置为中心位置,坐标为(500 m,500 m)。在仿真的过程中,通过改变传感器的个数,传感器的能耗值范围,比较算法的路径值。

在上文中的多种传感器个数以及能耗范围设置下的仿真实验中,由于TSP问题的复杂度与传感器个数n相关,考虑到计算量,这里选取了一组能耗级别为3级,传感器个数为20的路径遍历仿真结果。

图7为传统周期遍历算法小车充电路径图。

图7 传统周期遍历算法路径图

图8(a)～(c)为非固定周期算法小车充电路径图。

图8 非固定周期算法充电路径图

图9(a)～(c)为固定周期转移算法小车充电路径图。

图9 固定周期转移算法充电路径图

由图7、图8和图9可以看出,固定周期转移算法在一个周期T内只需要出动3次,总的路径值最少;传统周期遍历算法也出动3次,但每次遍历所有传感器节点,所以路径值最多;非固定周期算法每次遍历传感器的路径值较少。由于非固定周期算法的特点,图8(a)的移动方式需要2次的充电过程,加上(b)、(c)各1次,小车总的出动频数为4次,计算得到的总路径值比固定周期算法得到的总路径值多。

图10和图11进一步给出了在不同传感器数量、不同能耗分级下算法的有效性。图10为各节点能耗在0.1 J/s～0.3 J/s(对应能耗分级为3级)范围内随机取值,三种算法在传感器个数为20,25,30,35时,相同时间内(由于传感器最小能耗都为0.1 J/s,则每个传感网络的生命周期都相同)小车遍历的充电路径值。图11为在保证传感器网络的个数为30时,在0.1 J/s～0.3 J/s,0.075 J/s～0.3 J/s,0.06 J/s～0.3 J/s,0.05 J/s～0.3 J/s(分别对应能耗分级为3级,4级,5级,6级)四种能耗分布下(每个传感器网络的最小能耗都不同,则每个传感器网络都具有不同的生命周期)三种算法小车遍历的充电路径值。从图10和图11可以看出,本文提出的2种算法都要比传统的算法的路径值要小。

图10 小车总路径与传感器数图

图11 小车总路径与分级数图

图12给出了3种算法在不同能耗分级数下小车出动频数的比较,可以看到,在相同的时间周期内,固定周期转移算法与传统周期遍历算法的出动频数是一样的,出动频数都为能耗级数的值,而非固定周期算法的小车出动频数较多,随着能耗分级的增加,次数增加更加明显。

图12 小车出动频数比较图

固定周期转移算法在相同的周期时间内,小车遍历的路径值是最少的;传统周期遍历算法由于要遍历全部的传感器节点,必然浪费了大量的移动能量消耗;非固定周期算法由于较多的出动频数,即使每次遍历节点较少,相对于固定周期转移算法,同样会增加不必要的移动能量消耗。综上所述,固定周期转移算法无论在充电移动总路径上,还是小车出动频数上,较其他两种算法都具有优势。

4 结束语

本文基于无线可充电传感器网络的能耗差异,提出两种能耗分级的充电规划算法。一种是非固定周期算法,另一种是结合节点转移规则得到的固定周期转移算法。与传统的周期性小车充电算法不同,两种算法能够根据传感器网络的能耗状态,给传感器网络分级充电。在与传统算法比较的过程中,在相同的参数条件下,能够减小充电小车遍历路径值。其中,固定周期转移算法能够得到更小的路径值。仿真结果表明算法在求解最优路径值上的优异性能。在以后的研究中,可以寻找最优的能耗分级数以及更有效的节点转移方法,进一步优化遍历路径值。