[0043] 下面结合附图对本发明作进一步说明。
[0044] 无线可充电传感网络中的路过时空部分充电方法，流程如图1所示：
[0045] 步骤(1)构造无线可充电传感网络WRSN充电模型；包括：
[0046] (1‑1)如图2，传感网络中存在一组传感器集合S＝{s1,s2...sN}，N个完全相同的传感器随机部署在二维平面区域中，一个能量有限的移动充电车MC,一个能够为MC更换电池的仓库s0，一个用于收集传感器信息的基站；传感网络中具有一个路由协议用于传感数据收集，该路由协议通过中继节点将传感数据从传感器传输到基站；传感器在执行传感数据、传输数据和接收数据时都会消耗能量；由于每个传感器的监测任务不同，能量消耗率也不同。
[0047] (1‑2)假设MC、传感器电池容量为BM、Bs，eci和 分别表示si的能量消耗率和第k轮的剩余能量，si的剩余寿命可表示为 当传感器si的剩余电量小于报警阈值θ时，即 它会向基站发送一个充电请求 其中t表示发出
请求的时间，si表示发出请求的传感器标识， 表示当前周期剩余电量。REQi会被加入到全局等待队列Q中，Q中的请求会按照剩余寿命从小到大排序。假设在一段时间内，整个充电任务会被划分为Ntask个充电周期来完成。对于第k个充电周期，取Q中前ξ＝min{ξ,|Q|}个请求加入到任务队列 然后根据调度策略重新调整 接下来基站会根据 中的顺序以每个传感器所在位置为停靠点，为MC构建一个充电路径。随后MC从仓库离开，沿着充电路径移动，同时为每个停靠点的传感器充满预分配的电量再离开。注意MC一次只能对一个传感器充电，并且完成一个充电周期之前不会响应其他充电请求。MC会在耗尽能量之前返回仓库，然后更换电池并为下一个充电周期充电。
[0048] (1‑3)在一个充电周期中，MC的总能量消耗包括机械运动消耗的能量、传感器获得的能量、充电过程中的能量损失；
[0049] 第k个充电周期的充电计划表示成一个三元组集合Ck：
[0050] τik表示在第k个充电周期k
中MC到达si的时间和为si充电的时间，i＝1,2,…,ξ；C中每个的元组的含义等价于(传感器k
的标识ID，MC到达该传感器的时间，MC为该传感器充电的时间)。C的排列顺序与传感器的充电顺序一致，并且起始于仓库s0和终止于仓库s0；其中，
[0051] v为MC的恒定移动速度，d0,1为传感器s1与仓库s0之间的距离；
[0052] di‑1,i为传感器si‑1与传感器si之间的距离；
[0053] η为充电效率，qc为MC的充电功率为(J/s)；
[0054] MC在第k个充电周期总的活动时长 n表示第k个充电周期的充电节点数。
[0055] (1‑4)MC对每个传感器执行部分充电，即MC传递给传感器si的能量范围是0到而不是一次为其充满。
[0056] MC每次对传感器至少要充电量Δ的最佳取值Ntask表示完成的充电任务数，Dk表示第k个充电周期中死亡的节点个数；定义Δ为基本充电单元，MC传递给传感器的能量范围是Δ到 的连续空间，将MC每次传递的能量值离散化为 是一个整数，p和q为正整数，如p＝10；最大能
量需求Δmax取值为第1个充电周期中待充电传感器的最大能量需求，即 Q
为全局等待队列。
[0057] 步骤(2)在对充电队列 中的节点进行充电之前，需要先删除充电路径中的无效节点，以保证 能够顺利执行部分充电。
[0058] 为了保证 能够顺利执行部分充电策略，需要将那些无效节点INs从 中移除。删除无效节点的具体策略是尝试为每个传感器充Δ的能量。如果传感器sj在MC未到达时死亡则尝试将其逆序插入到序列{s1,s2...sj‑1}中。如果序列{s1,s2...sj,sj‑1}中的所有节点都能及时被充电则将si插入对应的位置以拯救该节点，否则将sj从 移除并插入到Q的末尾等待将来被调度。如图3所示， {s1,s2,s3}的预计充电量均为Δ，判断到
s4无法及时充电。则尝试将s4插入到s2、s3中间位置，若失败则继续尝试插入s1、s2中间位置，若成功则停止向前遍历。为方便描述后续步骤，假设在该步骤中删除了无效节点s4。
[0059] 步骤(3)删除无效节点会导致充电队列长度不足指定长度时，需要使用考虑时空因素的补齐队列策略以保证整体充电效率不会下降。
[0060] 如果 中删除了部分无效节点INs，那么本周期的MC的充电任务数就会变少。如果充电任务数减少，那么网络整体充电性能就会下降。所以需要将充电队列长度补充至最佳队列长度ξ(根据实验来确定)来避免性能下降。这里考虑向 中插入有效插入节点EIN以增加服务节点个数，从而提升充电效率。
[0061] EIN插入优先级：在选取EIN过程中会优先考虑将高优先级的节点插入到充电路径中。影响节点优先级的三个因素：a)剩余寿命，寿命越小紧急程度越高应当优先考虑。b)与其对应边的垂直距离，距离越近移动能耗越少应当优先考虑。c)考虑到系统的稳定性，时间优先级所占权重比空间优先级更高。
[0062] MC在第k个充电周期路过si的优先级 di′表示MC将si作为插入节点充电时会额外行走的路程，δ和β是设定系数。
[0063] 有效插入节点EIN(Effective Insertable Node)为满足以下两个条件的节点：条件①，以MC行走路径中的每条边为直径画圆，该节点的位置位于圆周内；条件②，如将该节点插入到充电队列中，插入位置之后的所有节点能够被及时充电，同时保证MC的电量能够回到基站。k
[0064] MC的移动路径表示为Π＝{E1,2,E2,3,...En,0}，Ei,i+1表示 中si与si+1的连线；Ci,i+1能够覆盖的节点集合Ωi,i+1中的所有节点都存在一个插入优先级，Ci,i+1表示以Ei,i+1为直径的圆。
[0065] 如图4中，E6,7表示s6、s7的连线，MC的移动路径Πk＝{E1,2,E2,3,E3,5,E5,6,E6,7,E7,0}，注：这里假设在步骤2中删除了无效节点s4。以Ei,i+1为直径的圆用Ci,i+1表示，Ci,i+1能够覆盖的节点集合为Ωi,i+1，Ωi,i+1中的所有节点都存在一个插入优先级。
[0066] 如图4所示，以s6、s7为直径画圆，该圆能够覆盖s11、s12，即Ω6,7＝{s11、s12}，则s11、s12是潜在的EIN。
[0067] 插入EIN的流程如下：反向遍历Πk，对于边Ei,i+1计算其对应的Ωi,i+1中每个节点的插入优先级，选取Ωi,i+1中优先级最高的节点，并尝试插入到 中si、si+1的中间。如图4，反k向遍历Π ＝{E1,2,E2,3,E3,5,E5,6,E6,7,E7,0}，E7,0对应的Ω7,0为空，然后继续判断E6,7对应的Ω6,7计算Ω6,7＝{s11、s12}中s6、s7的插入优先级。假设s11的优先级更高，那么就先尝试将s11插入任务序列 中，则
[0068] 接下来判断 中的所有节点是否能够以最低充电边界充电并且判断MC的电量是否能够回到基站，若不满足则说明该点不适合插入，继续尝试Ωi,i+1中的次优节点，如图4中的s12，直到找到有效的节点或者Ωi,i+1遍历完毕。然后继续为Ei‑1,i选取合适的节点插入。当k插入的节点个数多于 或者Π遍历完毕时算法停止。
[0069] 步骤(4)执行部分充电策略，并为移动充电器规划到达时间、停留时间、充电顺序。
[0070] 为方便描述，先给出一些关键词的定义。
[0071] 最佳削减节点:如果任务队列 中存在传感器si无法及时被充电，则需要从si之前的序列 中找到一个节点削减△充电量。为了综合考虑当前节点的剩余电量和能量消耗率。将选取 中削减△充电量之后剩余寿命最长的那个节点定义为最佳削减节点sopt。这样对整体网络而言影响相对更小。最佳削减节点表达式如下：
[0072] 其中， 表示MC对传感器sj充电量削减的部分。
[0073] 最晚结束时间(Latest Finishing Time，LFT)：是指MC回到仓库时不能超过的时间点。在对当前充电队列 中节点规划充电任务时，除了要考虑 中所有节点能够存活和MC有剩余能量返回仓库两个条件，还需要保证MC能够及时到达下一个充电周期(k+1)的第一个节点。这里假设第(k+1)周期中调度的第一个节点为该周期中寿命最小的节点(虽然它不一定是第(k+1)周期调度过程中第一个)，用sξ+1表示。
[0074] 则最晚结束时间
[0075] 执行部分充电策略的具体流程如下：遍历充电队列 如果 中存在传感器si无法及时被充电，则需要找到si之前最佳削减节点sopt。然后将MC对sopt的充电量削减△，即然后将MC对sopt的充电量削减△，即 判断si是否能及时充电：如果可以，则停止削减 中节点的充电时间，否则继续寻找最佳削减节点直到si能够及时被充电。因为步骤2已经删除了无效节点，所以通过不断削减 中节点的电量一定能够让si及时被充电。重复上述步骤直至 中的所有节点能够及时充电。图5展示了中s5无法及时充电时的一个处理过程。当s5无法及时充电时则找
到最佳削减节点s2，将s2的充电量减去一个Δ＝Bs/5(削减的电量用虚线方框表示)，如果s5仍然无法及时充电，则继续寻找到最佳削减节点s3将其充电量减去Δ，随后s5能够及时充电，此时停止削减电量。
[0076] 当确定 中的节点都能及时充电之后还需要确保MC回到仓库的时间小于最晚结束时间，即 具体的做法和上述过程类似，仍然是通过不断削减 中节点的电量来达到 当 中的所有节点都以最低充电边界充电时，如果仍无法满足 则放k k
弃削减并以最低充电边界的充电量去给所有的传感器充电。最后为MC生成充电计划C 。C中每个的元组的含义等价于(传感器的标识ID，MC到达该传感器的时间，MC为该传感器充电的k
时间)。C的示例如下：
[0077]
