基于相遇位置预测的移动传感器网络能量补充方法研究

邹英华,冯 勇,戴斌辉,王成栋

(昆明理工大学云南省计算机技术应用重点实验室,昆明 650500)

由于无线移动传感器网络中的传感器具有移动能力,能够完成动态跟踪等任务,被应用于气体源定位[1]、灾难救助[2]等方面。因此逐渐受到了学术界和工业界的关注[3-4]。

目前,传感器网络主要是由电池进行供电,而且在特殊的环境下人为地更换电池难以实现,能量问题便成为限制移动传感器网络广泛应用的重要约束和挑战,所以有研究工作者提出了节省能量的办法[5],但是此方法不能从根本上解决问题,它只能有限的延长网络寿命,当有传感器的电量耗尽后,将有可能导致整个网络无法正常工作。从周围的环境中获取能量也是一种办法[6],但能量获取过程具有高度的不可预测性和不可控性等缺点。无线充电技术[7]能主动提供高效、及时的充电服务。因此有研究工作者提出了利用固定充电站[8]给传感器进行能量补充的方法,此方法需要传感器额外地移动得到能量补充,使得其当前的任务不能及时完成。

利用移动充电装置MC(Mobile Charger)给移动传感器进行能量补充是一种十分有效的方法。MC主要使用了无线能量传输技术,例如电感耦合技术[9]、全向/定向电磁辐射技术[10]等。此技术可以给移动传感器提供可靠、持续的能量补充。有研究者提出使用多个MC给传感器进行能量补充[11-12],但由于MC价格不菲,在固定的区域中布置过多的MC给传感器充电并不现实,所以如何合理、有效地规划MC的充电路径,成为一个非常棘手的问题。对此本文通过预测移动传感器和MC的相遇位置使得传感器在最短的时间内得到能量补充,并且MC可以独立地完成充电任务。在保证传感器工作效率的同时此方法还缩短了充电延迟,提高了充电效率。

1 相关工作

相对节能方法的有限性和能量收集方法的不可预测性,无线充电方法可以有效地保证充电的及时性。与部属静态的充电站相比,使用MC可以增强充电过程的灵活性和可控性。

文献[13]提出了一种基于虚拟骨干网环境下的移动能量补充策略。此策略根据待充电传感器当前的通信量计算优先级,给优先级最大的传感器充电。文献[14]提出了一种基于传感器最大可容忍充电延迟的饥饿避免移动能量补充算法。由于静态传感器网络与移动传感器网络组成成分的相似性,上述静态传感器网络能量补充方法给了本文很多启发。

文献[15]提出分层团队的方法,侧重于支持多个机器人和MC对接进而补充能量。MC不断优化其位置,减少团队额外移动成本。虽使用了MC给机器人充电,但机器人需要中断当前的任务来补充能量。文献[16]中,当机器人的能量值达到阈值时,便会停止移动,等待MC给其充电。此方法虽不需要机器人额外地移动但不能从根本上解决机器人的工作效率得不到保证的问题。由于这些限制,将以上三种方法用在移动传感器网络能量补充方面也存在同样的问题。因而又有研究者提出利用MC独立地与传感器会合进行能量补充的方法。

文献[17]提出了机会主义的无线充电方式,通过相遇时间等信息在传感器中选出锚点,这些锚点定期地回基站进行补充能量,并且在与剩余的传感器相遇时给其补充能量。文献[18]中,使用The Best-Effort Charging Schedule确定了MC和每个提出充电请求的机器人传感器可能相遇的位置及可能的充电完成位置后,构造了一颗加权旅行树。按旅行树的单源最短路径给传感器充电,使得到的充电成本能尽可能小。并与算法The Best-Effort Charging Schedule做了对比,在充电成本方面有一定的优势。

因此本文预测到MC和传感器的相遇位置并对传感器得到能量补充的优先级进行了深入的研究,在考虑了移动传感器得到充电请求响应公平性问题的前提下,提出了一种相遇时间优先的能量补充策略。

2 网络模型与问题陈述

2.1 网络模型

在整个无线传感器网络中有I个移动的传感器,S={s1,s2,si,…,sI},si代表编号为i的传感器、一个MC、一个初始位置、M个目标位置,L={l1,l2,lm,…,lM},lm代表编号为m的目标位置。MC是一个具有自主移动能力和计算、通信能力的机器人,配有大容量的电池,并作为整个移动传感器网络中的能量传输者。每个传感器配备有一个具有快速充电能力的可充电电池,和一个无线能量接收装置,接收来自MC的能量。

移动传感器部署在m×m的区域内以速度vs执行其任务。一辆MC以速度vc(vc>vs)给传感器补充能量。令Einitial代表传感器的总能量,θ代表剩余能量阈值,当其自身的剩余能量低于θEinitial时,便会发送充电请求,R={r1,r2,rn,…,rN}(N

图1 网络模型图

本文提出的能量补充算法特别提出以下两点:①MC在和传感器相遇时会自动降低速度和传感器同步移动进行能量补充;②在充电过程中,MC可以独立地完成充电任务。

2.2 问题陈述

使用MC和传感器相配合的方式给传感器补充能量在紧急搜救等关键任务中也会造成不可逆转的损失。MC独立地与传感器会合是一种更合适的能量补充方式。例如The Tree-based Charging Schedule方法中,MC根据单源最短路径依次给相应的传感器补充能量。其中MC是按传感器提出充电请求的顺序给其补充能量的,此种方式缺少一定的灵活性和实时性。从而增加了整体的充电延迟和充电成本。如图2(a)MC是按照传感器提出充电请求的顺序给传感器补充能量的,首先和第一个提出充电请求且距离较远的传感器1在B点相遇,C点充电完成,接着与传感器2在D点相遇,E点充电完成。如图2(b)MC优先选择相遇时间短的传感器2在B′点相遇,C′点充电完成,接着与传感器1在D′点相遇,E′点充电完成,可以看出2(b)中的方式对缩短充电成本有一定的优势。但始终选择相遇时间短的传感器不免会导致有些传感器由于长时间得不到充电而失效。因此在考虑了移动传感器得到充电请求响应公平性问题的前提下,提出了一种相遇时间优先的能量补充算法。此算法综合考虑了整体充电延迟和充电公平性两方面因素。本文中所使用的符号见表1。

图2 充电成本对比图

参数符号参数意义N网络中移动传感器的总数目Einitial→i移动传感器的初始能量Ew工作状态下每秒消耗的能量Es休眠状态下每秒消耗的能量Eresidual→i(t)i的剩余能量cMC的充电速度vcMC的移动速度vs移动传感器的移动速度ri(t)传感器i的能量消耗率Tα→i,Tβ→iMC移动到传感器i所需要的时间

3 相遇时间优先的充电算法

3.1 系统工作过程

移动传感器剩余能量小于阈值时,向MC发送充电请求的消息包括:传感器i的标识、剩余能量及传感器的位置。

MC拥有一个可以接收充电请求的服务池。当它接收到充电请求后发现服务池中没有来自该传感器的请求,则增加一条记录,若已有则更新其信息。初始时MC为空闲状态,一旦MC和传感器相遇,开始充电,其状态将转换为繁忙状态。在空闲状态,若有得到能量补充的优先级更高的传感器请求充电,那么抢断发生。只有空闲状态才可发生抢断,繁忙状态不可被抢断,待充电结束后MC重新切换为空闲状态,选择下一个充电目标,如此往复。

3.2 相遇位置的预测

若相遇位置在传感器的移动轨迹上,在传感器不中断当前任务的前提下,MC和传感器刚好相遇的位置为最佳位置。介绍以下预测MC和传感器相遇位置的方法。

图3 MC和移动传感器相遇情况示意图

图3中定义MC的位置为C(xc,yc),传感器的位置为S(xs,ys),目标位置为M(xm,ym),初始位置为O(xo,yo),MC与传感器相遇位置为Eδ(xδ,yδ)或Eε(xε,yε)。若只有一个传感器提出充电请求,MC就会向相遇位置移动。首先判断传感器的状态为0(传感器向目标位置移动的状态)还是为1(传感器向初始位置移动的状态)。如图3(a),当传感器的状态为0时,得到cosα为:

(1)

如图3(b),当传感器的状态为1时,得到cosβ为:

(2)

此时根据式(1)和式(2)可以计算出当传感器的状态为0或1时,MC和提出充电请求的传感器相遇所需要的时间分别为:

(3)

(4)

其中vs为传感器的移动速度;vc为MC的移动速度(vc>vs)。

如图3(a)中的星型和3(b)中的星型所示,当传感器的状态为0或1时,根据式(3)和式(4)得到MC与传感器的相遇位置分别为:

(5)

(6)

此时MC会移动向传感器的相遇位置Eδ(xδ,yδ)或Eε(xε,yε)与传感器会合,进而补充能量。

3.3 确定下一个得到充电服务的传感器

若只有一个传感器提出充电请求,MC会与该传感器在相遇位置汇合补充能量。但当有多个传感器提出充电请求时,MC和传感器的相遇时间越短,该传感器得到充电服务的优先级越高,这样的充电方式可以缩短充电延迟。但是如果单纯的优先考虑给所有传感器中相遇时间最短的传感器充电,也会导致有些剩余能量很少并且和MC相遇时间较长的传感器得不到及时的充电而失效,因此我们考虑了缺电移动传感器得到充电请求响应的公平性问题,具体提出以下解决方案。下一个得到充电传感器的选择算法步骤如下。

第一步:如果服务池中存在且只有一个传感器提出充电请求,MC来得及给该传感器充电则向与该传感器汇合的位置移动,为其充电。否则转向第二步。

第二步:如果服务池中有多个传感器,则计算每个传感器与MC的相遇时间,将相遇时间从小到大对应的传感器排序。此时按序遍历服务池中的传感器,若MC与传感器相遇所需时间大于传感器当前的生存时间,即MC优先移动向该传感器相遇位置也避免不了该传感器失效,则从服务池中将该传感器删除。表达式如下:

(7)

ts为传感器提出充电请求时的时间,t为当前时间,Eresidual→i(t)为传感器的剩余能量,ri(t)为传感器i的能量消耗率,st为移动传感器的状态。

第三步:从服务池中第一个传感器开始,优先给当前传感器充电,将其余传感器作为下一个充电传感器时,若其等待充电的时间大于当前生存时间,则会导致其余传感器停止工作。其中下一个充电传感器需要等待的时间为:

(8)

(9)

Einitial→i为传感器初始能量,c为充电速度,tm为给当前传感器充电完成到与下一个传感器相遇的时间。接着遍历服务池,直到不满足上述条件,即给当前传感器充电完成后不会导致其余传感器能量耗尽而失效。此时MC会选择当前传感器给其充电。当前传感器即为下一个得到充电服务的传感器。在极端情况下,遍历完整个服务池都没有符合条件的充电传感器,则转向第四步。

第四步:此时MC选择相遇时间最短的传感器为下一个得到充电服务的传感器。

如图4,有7,2,5号三个传感器依次请求充电,按相遇时间从小到大给相应的传感器排序5,2,7。即使MC优先给7号充电也避免不了7号的失效,则不考虑给7号传感器充电。因此判断优先给5号充电,由于2号剩余能量过少,给五号传感器充电完成后则会导致2号停止工作,所以也暂时先不给5号充电。再判断优先给2号充电,此时不会导致其余传感器停止工作,MC便选择优先给2号传感器充电。

图4 下一个需要充电传感器的选择

图5 下一个需要充电传感器的选择算法

3.4 Tα→i为下一个得到充电传感器i的最短相遇时间的证明

若已确定传感器i为下一个得到充电服务的传感器,在传感器i的移动路径上传感器i和MC有多个可能相遇的位置和对应的相遇时间。而传感器i与MC的相遇时间Tα→i(Tβ→i)是影响充电策略性能的主要的因素,尤其是对平均充电延迟的影响。若Tα→i(Tβ→i)为最短相遇时间,那么就可以证明此充电策略在充电延迟方面较以往的充电策略有一定的优势。下面对定理1进行理论证明。

定理1已确定移动传感器i为下一个得到充电服务的传感器,在不影响传感器i执行任务的前提下,传感器i(1≤i≤n)和MC的最短相遇时间为Tα→i(Tβ→i)。

证明:首先假设移动传感器i和MC在传感器i移动T1(0≤T1≤LMS/vs)时间后的位置相遇,而此时MC到达此位置的时间为T′1,路程为S。可由以下公式得到MC路程的表达式:

(10)

(11)

得到T′1的表达式后,可以将问题转化为不等式的证明问题,比较T1和T′1的大小,得到当且仅当T1=Tα→i时,T1为传感器i和MC的最短相遇时间。

(12)

(13)

(14)

又因为F(Tα→i)=0 (Tα→i>0)可以得到以下结论:

(0

(15)

(16)

4 仿真实验

本文中建立了这样一个仿真环境,建立200 m×200 m的区域,并随机布置10到100个目标位置和10到100个移动传感器。我们使用C++实现了本文基于非顺序性的最短相遇时间的充电方法NTP(Non-sequence and Shortest Meeting Time Charging Programme)与TBS(The Tree-based Charging Schedule)方法、BCS(The Best-Effort Charging Schedule)方法的对比,在仿真实验中我们表2列出了所有的默认参数。

表2 仿真参数

4.1 传感器失效率

传感器失效率:因能量耗尽而失效的传感器数目占网络中所有传感器总数的百分比。失效传感器比例是可充电移动传感器网络最重要的指标之一,该比例越低说明系统的充电策略越公平高效。

图6(a)中,随着充电速度越快,传感器的失效率越来越低。这是由于随着充电的速度越快,MC给单个传感器的充电时间就会越少,充电器可以在一定的时间内为更多的缺电传感器补充能量,从而降低传感器的失效率。如图6(b),随着传感器数目增多,系统运行一段时间后,多个缺电传感器同时提出充电请求,请求充电的传感器数目也就更多。充电器的能力有限,传感器失效率随之变高。如图6(c),随着传感器的速度越快,MC与传感器相遇的时间变长,单位时间内移动传感器得到MC充电服务的个数就会越少,导致传感器失效率越高。可以看出NTP算法在降低传感器失效率方面更加公平。

图6 不同情况下的传感器失效率

NTP算法在传感器失效率方面均比TBS算法和BCS算法更有优势,这是因为本文考虑了缺电移动传感器得到充电请求响应公平性问题,使得剩余能量很少,并且其得到能量补充的优先级始终不高的传感器也能在关键时刻得到MC的充电服务,减少了传感器的失效率。

4.2 平均充电延迟

平均充电延迟:所有提出充电请求的传感器从发出充电请求到MC与传感器相遇进行能量补充的时间总和比上总的充电次数。平均充电延迟可以反应系统的响应速度。

图7(a)中,当充电速度从200增加到400时,每一个缺电传感器从开始充电到充电完成的时间就越短,MC节省出时间为更多的传感器提供充电服务。下一个得到充电的传感器等待的时间越小,平均充电延迟随之下降。图7(b)中,由于充电器能力有限,优先度越低的传感器等待的时间越长,平均充电延迟呈上升趋势。如图7(c),当传感器速度增加时,传感器失效率升高,提出充电请求的传感器越少,传感器等待充电的时间越短,充电延迟越小。

图7 不同情况下的充电延迟

NTP算法在平均充电延迟方面均比TBS算法和 BCS算法更有优势,这是因为TBS算法和BCS算法都是按照传感器提出充电请求的顺序进行充电的,会增加MC在充电过程中往复的移动距离,其整体的充电延迟会比较大,并且TBS算法在加权旅行树中选择单源最短路径的过程中会增加MC和传感器相遇的时间。而NTP算法中,MC与传感器相遇的时间越短得到充电请求的优先级相对越高,因此MC每次都选择相遇时间短的传感器补充能量,减少了MC在充电过程中往复的移动距离,降低充电延迟。

4.3 充电成本

充电成本:MC在给传感器补充能量的过程中移动的距离总和,即MC与传感器相遇前移动的距离与相遇后降低速度给传感器补充能量移动的距离之和。

图8 不同情况下的充电成本

如图8(a),充电速度变大充电成本虽然呈下降趋势,但趋势并不明显,这是因为充电过程中MC的移动距离仅仅占充电成本中的一小部分,而决定充电成本的主要因素是MC在和传感器相遇的过程中移动的距离。图8(b)中,随着传感器数目的增加,在充电器能力范围内,可以为更多的传感器补充能量,移动的距离越长其充电成本也越大。但当传感器的数目大于70时,充电成本的增长率呈下降趋势,这是因为传感器数目变多,单位时间内得到能量补充的缺电传感器数目有限,所以充电成本增长率呈下降趋势。如图8(c),随着传感器的速度越快,单位时间内移动的距离越长,由于传感器充满电所需要的时间都是固定的,因此充电成本越大。

NTP算法在充电成本方面和TBS算法基本持平,但比BCS算法更有优势。这是因为TBS算法在加权旅行树中选择一条单源最短路径使得整体的充电成本变小,在充电成本方面有很大的优势。而BCS是按充电请求的顺序给传感器补充能量的,并且没有综合考虑充电成本的因素。因此NTP算法比BCS算法在充电成本方面更有优势。

5 总结

本文探讨了一种相遇位置预测的能量补充算法。预测得到MC和传感器的相遇位置,相遇时间短的传感器相对相遇时间长的传感器得到能量补充的优先级相对较高。而后在保证移动传感器得到充电请求响应公平性的前提下,筛选出能量补充优先级最高的传感器为下一个充电传感器。通过大量的仿真实验对算法进行了分析。实验结果表明,本文提出的充电方案能够较好地缩短充电延迟、提高充电效率。