无线可充电传感器网络能量源部署方法研究

於晨阳 谢志军

(宁波大学信息科学与工程学院 浙江 宁波 315211)

0 引 言

无线传感器网络[1](Wireless Sensor Network,WSN)已广泛应用于多个领域,例如智慧城市、工业系统、环境监测等[2-5]。由于大多数现有的传感器网络均由电池供电,电池能量有限,更换节点的电池既昂贵又困难,特别是在人无法进入的环境中。由此可见,无线传感器网络中能量问题是亟待解决的关键问题。由于近年来无线能量传输(Wireless Power Transmission,WPT)[6]技术的发展,提高了能量传输质量,可以利用WPT技术为传感器节点补充能量。这引起了研究者们对无线可充电传感器网络(Wireless Rechargeable Sensor Network,WRSN)的广泛关注和深入研究。

无线可充电传感器网络由能量源和可充电传感器节点组成,使用静态或者移动的能量源,利用WPT技术为可充电传感器节点补充能量从而延长网络寿命。由于静态部署能量源相比于移动能量源调度更为可靠和稳定,不少研究人员对此进行了研究。Ding等[7]研究最小化能量源的部署成本问题,他们分别考虑全向充电和定向充电两种场景,给定一组用于部署能量源的候选位置,每个位置部署成本不同,在满足网络充电效用的前提下最小化能量源的部署成本,首先证明了该部署问题是NP-Hard,然后提出了一种基于贪心算法的能量源部署方法。Zhang等[8]研究能量源放置和功率分配问题,给定一组放置能量源的候选位置,根据功率预算,找到能量源放置和相应的功率分配以最大化充电质量。He等[9]研究能量源的覆盖问题,将能量源部署在等边三角形的顶点上实现了监测区域全覆盖,并有效减少了能量源的部署数量。Yu等[10]研究了无线能量源的连接问题。给定固定数量的定向无线能量源和候选位置,在无线能量源的连接性约束下确定每个充电器的放置位置和定向角度,以使整体充电效用最大化。文献[7-8,10]中的能量源部署研究中,能量源的部署位置都是从给定的一组候选位置中选取的,而实际中候选位置未知。文献[9]采用部署能量源覆盖整个监测区域的方式,然而该方式成本要求太高并且区域中节点数量有限并不需要覆盖所有区域。区别于上述研究,本文研究候选位置未知情况下,在监测区域内寻找能量源的部署位置,旨在最大化整个网络的充电效用,将其定义为最大化充电效用能量源部署优化问题。

本文首先建模该最大化充电效用充电器部署问题,为解决该问题提供理论基础。该问题是一个非线性且非凸的优化问题,而基于群体的启发式算法能够有效地解决此类问题。存在一些研究证明[11-13]乌鸦搜索算法在许多优化领域比其他算法例如粒子群、蚁群算法等具有更好的性能。为了获得更优的充电器部署位置,本文对乌鸦搜索算法进行改进,提出一种混合乌鸦搜索算法和交叉算法的启发式部署方法HCSCSA(Hybrid Crossover Search Crow Search Algorithm)。HCSCSA改进了乌鸦搜索算法的随机跟随策略,并在乌鸦搜索算法的基础上引入水平交叉[14]选择两个不同个体在所有维度上进行算术交叉增强全局搜索能力减少无法搜索到盲点,引入垂直交叉所有个体随机选择两个维度进行算术交叉增强跳出局部最优的能力。最后,通过仿真实验证明本文算法优于其他启发式算法。

1 系统建模与问题定义

1.1 网络模型

集合S={s1,s2,…,sm}为在长度为L×L的2维监测区域内放置的用于感知数据或监测特定事件的m个静止的可充电传感器节点。E={e1,e2,…,em}为每个传感器的耗电功率。将监测区域长度作为x轴,宽度作为y轴,传感器si的坐标可以表示为(xi,yi)。能量源可以为其充电半径范围内的传感器提供能量,部署后位置无法改变。网络模型如图1所示。

图1 网络模型

1.2 充电模型

在本文中,使用基于Friis公式[15-16]改进的充电模型如下:

(1)

(2)

式中:pr为传感器端接收功率也就是充电功率;pt为能量源端发射功率;Gs为发送天线增益;Gr为接收天线增益;λ为波长;d为传感器节点与能量源之间的欧氏距离,其中传感器的坐标为(xi,yi),能量源坐标为(Xj,Yj);β为短距离传感的调节参数避免距离为零时充电功率无限大。可将式(1)简化为如下形式:

(3)

式中:a代表式(1)中其他参数的影响。当d太大时,充电功率几乎为0,式(3)可以改进为以下公式:

(4)

式中:R为能量源的充电半径。

能量源充电范围内可以存在多个传感器节点,传感器节点可以被多个能量源覆盖可以获得来自多个能量源的能量,传感器si其总充电功率可以表示如下:

(5)

式中:N为能量源个数。

1.3 充电效用模型

由于硬件限制或者实际充电需求,当传感器使用恒定功率充电时,当充电功率大于其耗电功率时多余的能量无法存储,相应的充电效用也不会增加,因此使用如下线性有界模型作为充电效用模型[10]:

(6)

式中:u(si)为传感器si的充电效用;λ为线性相关的常数。将单个传感器充电效用扩展到整个网络,全网总的充电效用为:

(7)

1.4 问题定义

本文研究最大化充电效用能量源部署问题,目标是优化能量源的部署位置,提高网络的充电效用。给定能量源数量N、传感器坐标(xi,yi)和耗电功率E,最大化充电效用U(S),可以建模为如下优化问题:

给定:N,E,S,(xi,yi),i=1,2,…,m

最大化:U(S)

变量:(Xj,Yj),j=1,2,…,N

该优化问题的解空间无限,是一个非线性和非凸的优化问题。本文提出一种混合乌鸦搜索算法和交叉算法的新启发式算法HCSCSA解决该问题。

2 基于HCSCSA的能量源部署方法

2.1 乌鸦搜索算法

(8)

(9)

2.2 HCSCSA

图2 飞行距离小于1时乌鸦的飞行路线

图3 飞行距离大于1时乌鸦的飞行路线

(10)

(11)

(12)

接下来进行垂直交叉,垂直交叉是乌鸦个体本身在不同位置维度上进行算术交叉,垂直交叉能够避免在搜索过程中陷入局部最优。选择乌鸦i根据式(13)进行垂直交叉。

(13)

HCSCSA引入了水平交叉和垂直交叉操作故对其时间复杂度分析,标准乌鸦搜索算法的复杂度为O(Cmax·v·w),水平交叉的操作复杂度为O(v·w),垂直交叉的操作复杂度为O(v),适应度计算的操作复杂度为O(v·w)。由此可知,引入的水平交叉和垂直交叉后,算法的时间复杂度还是O(Cmax·v·w),没有增加额外的计算成本。

针对本文的能量源部署位置优化问题,定义乌鸦个体Qi为N个能量源的坐标,即Q=(X1,Y1,X2,Y2,…,XN,YN),Qi的适应度函数为网络的充电效用fitness=U(S)。根据HCSCSA的优化策略寻找能量源的部署位置,最大化网络的充电效用。具体的部署过程如下:

输入:能量源数量N,节点耗电功率E,传感器坐标(xi,yi),i=1,2,…,m。

输出:充电效用U(S),能量源位置(X1,Y1,X2,Y2,…,XN,YN)。

2.为种群大小为v的每只乌鸦在监测区域中随机初始化能量源位置。

3.根据初始能量源位置计算充电效用U(S),使能量源的最佳部署位置为初始位置。

4.fori=1 toCmaxdo

5.forj=1 tovdo

6.每只乌鸦根据式(10)更新能量源位置

根据式(10)第一项等式更新能量源位置,根据式(11)、式(12)对当前能量源部署位置和最佳部署位置执行水平交叉,再次计算U(S)保留更好位置,根据Ph判断是否进行垂直交叉,如满足概率按照式(13)对能量源位置进行垂直交叉,计算U(S)保留更好位置,否则不进行垂直交叉。

8.end

9.else

10.随机生成一个能量源部署位置并计算充电效用U(S)

11.end

12.end

13.更新个体、群体最佳能量源部署位置

14.end

15.outputU(S),(X1,Y1,X2,Y2,…,XN,YN)

3 实验仿真

如图4所示为小规模部署场景下的一个可视化实例,其中:倒三角为耗电功率为0.000 1的传感器节点;星号为耗电功率为0.000 2的节点;圆点为能量源的部署位置。可以看出HCSCSA搜索能力强于其他算法,能够找到具有更优充电效用的部署位置。

(a) CUCKOO (b) MFO

(c) CSA (d) HCSCSA图4 可视化实例

表1、表2分别为小规模场景下和大规模场景下的充电效用结果,两个场景下HCSCSA的最差值、平均值、最优值皆高于其他算法表明该算法具有更优的性能。

表1 小规模场景下充电效用

表2 大规模场景下充电效用

图5所示为小规模场景下的平均充电效用迭代曲线,可以看出随着迭代进行HCSCSA的平均充电效用始终高于其他启发式算法,展现出其极强的寻优能力。迭代到16次时,HCSCSA已实现收敛,表明HCSCSA具备良好的收敛能力。

图5 小规模场景下迭代曲线

图6所示为大规模场景下的平均充电效用迭代曲线,大规模场景下由于搜索空间的扩大和传感器节点个数的增多算法极易陷入局部最优如CUCKOO算法所示,而CSA本身具备良好的跳出局部最优的能力再加上HCSCSA的增强使其具有极强的跳出局部最优的能力,如迭代50次至60次所示。HCSCSA在小规模场景和大规模场景下的充电效用均优于其他启发式算法,不仅显示了其寻优能力还表现出极强的适应性。

图6 大规模场景下迭代曲线

4 结 语

本文研究最大化充电效用能量源部署问题,给定能量源数量、传感器坐标和传感器的耗电功率,在监测区域内寻找能量源的部署位置最大化充电效用,提出一种混合乌鸦搜索算法和交叉算法的新启发式算法HCSCSA。在小规模和大规模部署场景下HCSCSA的充电效用均优于其他启发式算法。