1.无线可充电传感网中基于动态功率分配的充电调度方法,其特征在于:所述方法包括如下步骤:步骤1,针对无线可充电传感网中基于动态功率分配的总充电效用最大化问题,构建基于充电完成时间和充电服务费用约束的整数规划模型;
所述步骤1的具体过程如下:
步骤11,设无线可充电传感网中部署了m个充电站S={s1,...,sm},其中每个充电站配置了一个全向无线充电器,且每个充电站有d档离散的充电功率P1,…,Pd实现动态调节,P1
所有的充电站由一个充电服务提供商CSP进行部署和运营;所有可充电的传感器设备V={v1,…vn}由用户静态部署在网络中;每隔一定的运行周期,网络将会进行一次充电调度;
步骤12,定义充电完成时间为从第一个充电站开始提供充电服务到最后一个充电站结束充电服务的时间,所有充电站同时开始充电服务,充电完成时间表达为对网络中的充电完成时间进行限制;定义充电服务费用为用户向CSP支付的获取充电服务的总费用,即 定义网络充电效用为所有传感器设备接收充电服务的效用之和,用U表示网络充电效用,即其中Qi、Ei和wi分别表示设备vi的电容、当前剩余电量和效用权重,prijk表示当充电站sj以充电功率Pk提供充电服务时设备vi的充电接收功率;
步骤13,给定充电完成时间上限T和充电服务费用预算上限C,建立面向充电站的充电调度策略以最大化网络充电效用,则该目标问题建模成如下的整数规划模型:maxU
tjk∈{0,...,T},for all j=1,…,m and k=1,…,d其中,约束 保证任意充电站sj提供充电服务的时间不超过给定的充电完成时间上限T;约束 保证用户向CSP支付的获取充电服务的总费用不超过给定的充电服务费用预算上限C;
步骤2,通过构造非负且单调非递减的子模函数,将目标问题转换为等价的基于预算约束的子模函数最大化问题;
其中,首先建立充电服务的任务集合,进而得到其子集的充电调度策略,并根据策略的充电服务时间与充电完成时间上限判断策略是否可行;然后将不可行策略转换为子策略;
最终设定基于是否可行策略判断条件的子模函数,将步骤1中的整数规划模型转换为子模函数最大化问题;
步骤3,基于步骤2构造的子模函数,利用贪婪策略得到各个充电站的充电策略,从而得到最终的解决方案;
其中,首先对于充电服务的任务集合,选择出集合势为1或2时并且满足预算约束的子模函数最大的子集;然后,对于集合势为3时并且满足预算约束的子集,通过基于最大边际收益值的贪婪策略进行更新,得到相应的子模函数最大的子集;最终比较上述得到的两个子集,得到最优子集,即为最优充电调度策略。
2.根据权利要求1所述的无线可充电传感网中基于动态功率分配的充电调度方法,其特征在于:步骤11中,对于周期性运行的充电调度,具体地说,用户基站将定期向网络中的所有设备发起一个充电命令,每个设备将在接收到充电命令后立即向基站报告其当前的剩余电量;用户基于接收到的剩余电量信息和设备位置的系统参数,根据优化目标在基站计算出充电站的协同充电调度策略,然后将该策略发送给CSP请求充电服务;在收到用户的充电服务请求后,CSP立即将该面向充电站的充电调度策略广播给所有充电站,以分配每个充电站的充电功率和对应充电服务时间;定义tjk为充电站sj以Pk的充电功率提供的充电服务时间;对于任意一个充电站sj,通过执行所收到的充电调度策略{
3.根据权利要求1所述的无线可充电传感网中基于动态功率分配的充电调度方法,其特征在于:所述步骤2的具体过程如下:k 1
步骤21,定义一个集合E={ej (t)|j=1,…,m&k=1,…,d&t=1,…,T},即E={e1
1 2 2 d d 1 1 d
(1),…,e1 (T),e1 (1),…,e1 (T),……,e1 (1),…,e1 (T),e2 (1),…,e2 (T),……,emd k(1),…,em (T)},其中任意一个元素ej (t)表示充电站sj以Pk的充电功率提供1个单位时间k y y的充电服务;对于任意子集 定义Mj ={ex (z)|ex (z)∈M&x=j&y=k&z∈{1,...,M M MT}},则子集M表达为一个充电调度策略SM={S1 ,S2 ,…,Sm},其中任意充电站sj的充电调度M 1 2 d子策略Sj ={
M
步骤22,针对不可行策略SM中的任意一个子策略Sj={
步骤23,给定集合E={ej (t)|j=1,…,m&k=1,…,d&t=1,…,T},对于任意子集定义一个函数F(M)如下:*
其中U通过执行步骤22得到;函数F(M)是一个非负且单调非递减的子模函数,步骤13中建模的目标问题等价于如下的基于预算约束的子模函数最大化问题:s.t.∑e∈Mc(e)≤C
k k
其中对于任意ej(t)∈M,定义c(ej(t))=ck。
4.根据权利要求3所述的无线可充电传感网中基于动态功率分配的充电调度方法,其特征在于:步骤22中,子策略转换的流程为:*
当k=d时,tjk=min{tjk,T};
*
当k∈{1,...,d‑1}时,如果 则tjk=0;如果 则*
如果 则tjk =tjk;对每一个子策略经过上述转化后,不可行* M* M* M* M* * *
策略SM转换为一个可行策略SM={S1 ,S2 ,…,Sm },其中Sj ={
5.根据权利要求3所述的无线可充电传感网中基于动态功率分配的充电调度方法,其特征在于:所述步骤3的具体过程如下:k
步骤31,针对集合E={ej(t)|j=1,…,m&k=1,…,d&t=1,…,T},枚举出E中所有势为
1或2且满足约束∑e∈Mc(e)≤C的子集,并通过比较找出其中F(·)函数值最大的一个子集M1,即步骤32,对于E中任意一个势为3且满足约束∑e∈Mc(e)≤C的子集M,初始地设置E'=E\M并且定义函数g(M)=M,然后执行基于最大边际收益值的贪婪策略;
步骤33,对E中每一个势为3且满足约束∑e∈Mc(e)≤C的子集M分别执行步骤32的贪婪策略得到相应的g(M),定义 通过比较F(·)函数值得到子集
步骤34,通过比较M1和M2的F(·)函数值得到最优子集Mopt:根据步骤21中的定义,将最优子集Mopt转换为最优充电调度策略 若得到的最优策略 是不可行策略,则采用步骤22中的方法将其转换为一个可行策略
6.根据权利要求5所述的无线可充电传感网中基于动态功率分配的充电调度方法,其特征在于:步骤32中,基于最大边际收益值的贪婪策略具体为,对于E'中每一个元素e'∈E'计算得到其边际收益值(F(g(M)∪{e'})‑F(g(M)))/c(e'),并通过比较找出E'中一个具有最大边际收益值的元素e”∈argmax{(F(g(M)∪{e'})‑F(g(M)))/c(e'):e'∈E'};判断c(e”)+∑e∈Mc(e)≤C是否成立,如果是,则更新g(M)=g(M)∪{e”}以及E'=E'\{e”};否则仅更新E'=E'\{e”};接着重复执行上述操作,直到 为止。