1. 引言
无线传感器网络(WSN)由大量传感器节点和数据中心构成,具备数据收集、处理以及传输三个功能,在日常生活中得到广泛应用。但传感器节点与数据中心之间的距离越长,数据转发任务越多,节点的通信负荷也越高 [1]。因此,一些传感器节点会因为能量耗尽而提前停止工作。从这个角度出发,研究人员提出了不同的延长整个网络寿命的方法。
一般来说,要解决这个问题有三种方法。其中一种方法是节能,通过设计低功耗的路由协议来延长无线传感器网络的生命周期,但这会对网络性能产生不容忽视的影响,而且没有从实质上改变有限的生命周期对传感器稳定高效工作的影响。此外,一些学者致力于转换大自然的能量为无线传感器网络提供能量,例如太阳能 [2] 及热能 [3] 等。但所转换能量的稳定性和可控性成为制约无线传感器网络稳定工作的关键因素。第三种方法中,可移动充电车(Mobile Charging Vehicle, MCV)应用于无线传感器网络组成了无线可充电传感器网络(WRSN),低成本的可移动充电车能够及时补充能量以满足传感器的需求,成为解决传感器能耗瓶颈问题的又一重要途径。
在无限可充电传感器网络中,按照充电车的工作时间可以将充电方式分为按需充电和周期充电两种。按需充电考虑了传感器网络中能量消耗的不平衡性,每轮只对最需要充电的几个传感器进行充电,一般应用在小规模的只包含单个充电车的传感器网络 [4]。周期性充电 [5] 是指充电车每次充电方案的总时间和充电顺序保持不变,每个节点定期进行能量补充,保证每个节点的能量变化也是周期性的,目前该充电方式应用较广泛。
在无线传感器网络中,每个节点的能量是有限的,并且节点的位置是固定的。为了保证网络的持续运行,需要一辆或几辆移动充电车为传感器节点补充能量。因此,我们将面临一个重要的研究问题:充电车将按照什么顺序工作,从而使充电车的充电效率更高。
2. 问题描述
本文以由
个移动充电车和m个传感器节点的无限可充电传感器网络为研究对象,并假定所有的移动充电车初始状态均位于数据中心。四个充电车路途总能耗最小的充电路线最优规划,可以使充电车的充电效率最高,使WRSN的实用性更强。
为方便研究,本文将整个网络的充电流程简化。在无线传感器网络中,传感器节点的能量是有限的,其主要工作是数据传输。在工作过程中,这些有限的能量E0会逐渐消耗掉,每个节点都有不同的耗能率Pi。原则上,充电车本身的能量远大于节点的初始能量,因此充电车将为节点提供节点所需的能量。下面是一个简单的充电过程示例(如图1)。
Figure 1. Multi-MCV charging route plan
图1. 多MCV充电路线规划示意图
3. 数学模型的建立
3.1. 优化目标的确定
可以将传感器网络看作是一个具有n个顶点的加权图G,网络中各边权重以各节点间的距离
表示。将四个移动充电器看作四个旅行商,传感器网络中的所有传感器以及数据中心看作城市,那么多MCV总充电路线规划即在加权图G中求顶点集V的划分
,将G分成4个连通的子图 [6],每个子图中寻找一条包含数据中心的回路,并达到四条回路的总边权值之和最小。
传感器节点间的距离矩阵
已知条件下,为表示各段路程的累加,首先通过定义0-1变量来表示各MCV是否从某一传感器到另一传感器:
则第k个移动充电器经过传感器的路径之和
,充电路线规划的目标就是使这4个MCV充电的总路径最小:
(1)
3.2. 约束条件分析
MCV从数据中心
出发,除数据中心外其余传感器仅被某一个MCV访问一次,数据中心是四个MCV的起点和终点,由数据中心必须被访问4次来约束:
(2)
为了保证每个MCV的充电路线都能形成一个圈,无向图中每个终点传感器只能有一个起点传感器和它相连;每个起点传感器只能有一个终点传感器和它相连:
(3)
规划过程中,因为三角形两边之和大于第三边,易得四个MCV中只派出一个MCV工作,而剩余MCV在数据中心闲置是充电总路线距离最短的情况(见图2)。为保证每个MCV均正常工作,即每个MCV都必须访问非数据中心外的至少一个节点,可以通过式(2)和式(3)条件相结合达成约束。
Figure 2. Single-MCV is better than multi-MCV in total distance
图2. 总距离上单MCV优于多MCV示意图
每个传感器集合的子集中都不能产生不与数据中心相连的支路,比如传感器集合
产生闭路
,其中并没有与数据中心
相连,因此
作为支路被消除 [7]。消除图中其他支路的条件可表示为:
(4)
3.3. 多MCV移动充电路径优化模型
综合目标函数和约束条件的讨论,我们得到多MCV移动充电路径规划的0-1规划模型如下:
目标函数:
(5)
4. 算例分析
数据来源于2020年深圳杯B题附件一和附件二,其中,附件一给出了数据中心和传感器的经纬度坐标,附件二给出数据中心和传感器经纬度坐标外,还给出了每个传感器的能量消耗速率。为确定传感器网络的边权值,首先将数据中传感器网络节点的经纬度坐标转换成三维坐标,得到任意两个传感器节点及数据中心与各传感器之间的直线距离 [8]。
附件一中给出的各点经纬度坐标用有序数对(u,v)表示,u为经度,v为纬度。以地心O为坐标原点,赤道平面为xOy平面,0度经线圈所在的平面为xOz平面建立三维直角坐标系 [8],则数据中心和各传感器的三维坐标为:
(6)
其中,地球半径R = 6370 km。
据解析几何相关知识,传感器网络中任意两节点
,
间的实际距离为:
充电路线的起点和终点都是数据中心,为了便于表示,不妨将数据中心看作0号传感器,将数据中心与所有的传感器记为一个节点集合
。
是两个传感器i与j之间的距离,据求得的节点间距离,得到数据中心与传感器之间、各个传感器之间的距离矩阵D:
在掌握实例数据后,根据前文建立的数学模型,考虑到多MCV充电路径方案数量大,一般算法收敛速度慢,因此通过MATLAB软件利用模拟退火算法求解多MCV的最短充电路径,算法流程图如图(如图3)。
由图4可知,经过313次迭代得到最大耗电量的稳定值,即得到最优解,计算出MCV最短的充电路线总路程为12.756 km,各MCV的传感器访问路径如下(如图5)。
Figure 3. Flow chart of simulated annealing algorithm
图3. 模拟退火算法流程图
Figure 4. Iterative results of simulated annealing algorithm
图4. 模拟退火算法迭代结果
Figure 5. Results of Multi-MCV charging route plan
图5. 多MCV充电路线规划结果
5. 结论
本文研究了无线可充电传感器网络中多充电车周期充电最优路径的优化问题,为使充电车路途能耗最低,建立了0-1整数规划模型,利用启发式算法中的模拟退火算法进行求解,经过313次迭代得到最优解。从实际应用角度来说,本文所提出模型对MRSN的充电问题具有重要的参考价值,对增强传感器网络实用性大有裨益,本文对实际问题向MTSP问题的转换为其他实际问题求解提供了思路。
基金项目
2020年山东省大学生创新训练项目(项目编号S202010429197);2020年山东省本科教学改革研究重点课题(Z2020045);2021年全国大学生创新训练项目(项目编号202110429213)资助。
NOTES
*通讯作者。