没有合适的资源?快使用搜索试试~ 我知道了~
2020深圳杯C题.docx
3星 · 超过75%的资源 需积分: 50 68 下载量 142 浏览量
2020-09-02
20:19:24
上传
评论 10
收藏 348KB DOCX 举报
温馨提示
试读
23页
参考了许多网络上的解法,自己做的练习题,完整的论文,附录有完整的python代码,仅大家供学习参考。
资源推荐
资源详情
资源评论
C 题:无线可充电传感器网络充电路线规
划
摘要
物联网的快速发展带动了无线传感器网络 WSN 在生活中的广泛运用。无
线传感器网络中包括若干传感器以及一个数据中心,这些传感器的电池均需要
移动充电器提供能量来维持正常的工作。移动充电器的能量一方面用于传感器
的充电,另一方面用于充电路上的消耗。为减少移动充电器路上消耗,提高能
量利用率,需要合理规划移动充电器充电路线。
针对问题一,要使得能耗最小化,就要保证移动充电器行走的路程最小,
所以路线图可看成网络图,利用地球半径和各传感器的经纬度计算可以得出各
个点之间的距离,问题转化为在给定的加权网络图中寻找从数据中心开始将网
络图中所有顶点仅遍历一遍再回到数据中心使得路程最短的问题,即 TSP 问
题,运用 python 的 OR-TOOLS 的 RoutingModel,结合启发式算法,可得到
最优路线方案。
针对问题二,系统正常运行需要保证移动充电器跑完一圈的过程后各传感
器一直不低于最低电池容量,可以将此作为约束条件,若要求得每一个满足题
设条件传感器的电池容量最小值,可以等价为求传感器总电池容量的最小值,
这样就将多目标问题转化为了单目标问题,经简化计算进一步转化为线性规划
问题,合理设置充电速率 r,移动速度 v,电池容量最低值 f,通过求解我们得到
各传感器的最小电池容量;在此基础上我们考虑到巡视间隔为 1 天,保证相邻
两次巡视之间传感器的电池电量仍然满足要求,得到电池容量。
针对问题三,规划同时派出 4 个移动充电器进行充电的路线可以联系多售
货员的旅行商问题,即 VRP 问题,当 VRP 问题有到达时间的约束条件时,问
题变为 VRPTW 问题(VRP with Time Windows),基于第一问的我们得到
最优的路线方案,结合第二问进一步得到各电池最低容量。
关键词: OR-TOOLS TSP 问题 启发式算法 VRPTW 问题
1.问题重述
随着物联网的快速发展,无线传感器网络 WSN 在生活中的应用也越来越
广泛。无线传感器网络中包括若干传感器以及一个数据中心。传感器从环境中
收集信息后每隔一段时间将收集到的信息发送到数据中心。数据中心对数据进
行分析并回传控制信息。影响生命周期最重要的一个因素是能量。提供能量的
方式之一是电池供电,利用移动充电器定期为传感器的电池补充能量,这种方
式供电的网络也被称为无线可充电传感器网络。
在系统中,传感器从环境中收集信息并将收集到的信息传递给数据中心。
当一个传感器的电量低于一个阈值时便无法进行正常的信息采集工作,为了让
WRSN 正常运转,移动充电器需要定期为传感器进行充电以避免其电量低于阈
值。为了减小移动充电器在路上的能量消耗,需要合理地规划移动充电器的充
电路线。请考虑以下问题:
问题一:根据每个节点的经纬度,考虑当只派出一个移动充电器时,如何规划
移动充电路线才能最小化移动充电器在路上的能量消耗。
问题二:知道每个节点的经纬度、能量消耗速率,假设传感器的电量只有在高
于时才能正常工作,移动充电器的移动速度为 v(m/s)、移动充电器的充电速率
为,在只派出一个移动充电器的情况下,若采用问题一规划出来的充电路线,
每个传感器的电池的容量应至少是多大才能保证整个系统一直正常运行?
问题三:知道每个节点的经纬度、能量消耗速率,假设传感器的电量只有在高
于时才能正常工作,移动充电器的移动速度为 v(m/s)、移动充电器的充电速率
为,但为了提高充电效率,同时派出 4 个移动充电器进行充电,在这种情况下
应该如何规划移动充电器的充电路线以最小化所有移动充电器在路上的总的能
量消耗?每个传感器的电池的容量应至少是多大才能保证整个系统一直正常运
行?
2.问题分析与思考
2.1 问题一分析 :
问题一属于典型的旅行商问题,该问题是在寻求一个充电器由起点出发,
通过所有给定的传感器位置点之后,最后再回到原点的最小路径。问题的求解
有多种方式,我们在这里采用 python 的 OR-TOOLS 的 RoutingModel 来求
解此问题。附件一给出了 29 个传感器以及数据中心的经纬度,先将经纬度转
换为弧度,再利用地球半径计算可以得出各个点之间的距离,从而可以求得这
些点的距离矩阵,运用启发式算法,根据以上两种不同的求解方式会得出不同
的最短路径(即最优路径),再对结果进行分析比较,得到最佳路线规划方
案。
2.2 问题二分析:
若将每一个传感器的电池容量都视作一个目标,则此问题属于多目标优化
问题,在此题中,若要求得每一个满足题设条件传感器的电池容量最小值,可
以等价为求传感器总电池容量的最小值,这样就将多目标问题转化为了单目标
问题,根据题意,我们可以合理假设移动充电器的巡逻速率和频率,从而得到
约束条件:在移动充电器巡逻一个周期(即绕所有点走一圈)内,每个传感器
的电池容量最低不能低于,利用这一条件,我们可以建立不等式约束,从而进一
步将问题转化为线性规划问题,利用线性规划的求解方式解得每一传感器满足
题设条件的电池容量最小值。
2.3 问题三分析:
由于有多辆车进行运送,要是以最小化路径为目标函数,可能会造成某辆
车的运送时间过长而导致总时间并不是最短的。所以目标函数应为:若设车队
的运送时间为$T = {t_1,t_2,t_3,t_4}$,车队的运输路径长度$L = {l_1,
l_2, l_3, l_4}$。则最小化$T$中最大的值,也可以解释为最小化$T$中的最大
值。综上所述,该问为有时间窗车辆路径问题(vehicle routing problems
with time windows),题目要求同时派出 4 个移动充电器进行充电,在这种
情况下规划移动充电器的充电路线,使得移动充电器在路上总的能量消耗最
小。因此首先考虑运用 python 的 OR-TOOLS,然后进一步分组利用启发式算
法求得最短巡视路径,在第二问的解法基础上计算传感器满足题设条件的电池
容量最小值。
3. 模型假设
3.1 假设移动充电器匀速行进;
3.2 假设题目所给数据真实可靠;
3.4 假设地球是一个标准的球体,半径是 6371km;
3.5 假设移动充电器在传感器处的时间消耗仅用于充电;
3.6 假设移动充电器的电池电量足够大,且不需要在数据中心进行充电。
4.符号说明
x
i
电池容量 mA
t
tot
到达该节点时,剩余电池容量刚好为
最低要求时间 t
r
i
移动充电器充电速率 mA/s
f
电容器最低工作值 mA
v
充电器移动速率 m/s
S
t
移动充电器到传感器的距离 m
5.模型建立
剩余22页未读,继续阅读
资源评论
- A1gernon2021-06-05论文规范,代码也很完整
- xiangnanlaboratory2020-09-06假的,下就是浪费积分zengshengli7752020-09-08看不懂就别乱说好吧
zengshengli775
- 粉丝: 23
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功