无线传感器网络的充电方法及装置

摘要

本发明提供了一种无线传感器网络的充电方法及装置，通过对无线传感器网络中的各传感器进行分类，从中选出第一类传感器和第二类传感器，并以各第一类传感器为节点构建哈密尔顿回路，在哈密尔顿回路上确定各第二类传感器的充电位置。最后遍历哈密尔顿回路以对第一传感器和第二传感器进行充电。使MC在一轮充电任务中，可以同时对第一传感器和第二传感器进行充电，使MC中携带的电量得到充分的利用，避免电量过多浪费在线路上，节约了电量。

权利要求

1.一种无线传感器网络的充电方法，其特征在于，包括：S1，根据无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期，从所有传感器中选取第一类传感器和第二类传感器；

S2，根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，构建以所有第一类传感器所在的位置为节点的哈密尔顿回路；

S3，根据每一第二类传感器与所述哈密尔顿回路上任意位置之间的距离，在所述哈密尔顿回路上确定每一第二类传感器的充电位置；

S4，遍历所述哈密尔顿回路，以对每一第一类传感器和分别移动至对应的充电位置上的每一第二类传感器进行充电；

其中，S2具体包括：

S21，根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，计算所述任意两个第一类传感器之间的线路权重；

S22，计算所述线路权重对应的两个第一类传感器之间的电量节约值，并得到节约值矩阵；

S23，根据所述节约值矩阵，基于节约算法构建以所述第一类传感器为节点的哈密尔顿回路；

S3具体包括：

在所述哈密尔顿回路上分别寻找距每一第二类传感器最近的位置，并将所述最近的位置确定为对应的第二类传感器的充电位置。

2.根据权利要求1所述的充电方法，其特征在于，所述第一充电周期具体为：所述无线传感器网络中每一传感器的电量由电池满电量降至预设电量阈值所需要的时间。

3.根据权利要求2所述的充电方法，其特征在于，所述每一传感器的剩余工作时间和每一传感器的第一充电周期通过如下方法计算：S01，获取无线传感器网络中每一传感器发送的充电请求信息；

S02，根据所述充电请求信息，分别向对应的传感器发送电量采集请求，以供所述对应的传感器分别根据所述电量采集请求发送电量信息；

S03，分别获取每一传感器发送的所述电量信息，并计算每一传感器的剩余工作时间和每一传感器的第一充电周期。

4.根据权利要求1-3中任一项所述的充电方法，其特征在于，S1具体包括：S11，选取所有传感器的第一充电周期中的最小值作为第二充电周期，所述第二充电周期为所述无线传感器网络的充电周期；

S12，分别比较每一传感器的剩余工作时间和所述第二充电周期的大小；

S13，将小于所述第二充电周期的剩余工作时间所对应的传感器作为所述第一类传感器；

S14，将大于或等于所述第二充电周期的剩余工作时间对应的传感器作为所述第二类传感器。

5.根据权利要求1-3中任一项所述的充电方法，其特征在于，S4具体包括：遍历所述哈密尔顿回路，在所述哈密尔顿回路的每一节点处为对应的第一类传感器充电；在所述哈密尔顿回路上的充电位置上为对应的第二类传感器充电。

6.根据权利要求5所述的充电方法，其特征在于，所述在所述哈密尔顿回路上的充电位置上为对应的第二类传感器充电前还包括：每一第二类传感器分别以各自的设定速度移动至对应的充电位置。

7.一种无线传感器网络的充电装置，其特征在于，包括：传感器分类模块，用于根据无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期，从所有传感器中选取第一类传感器和第二类传感器；

哈密尔顿回路构建模块，用于根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电量，构建以所有第一类传感器所在的位置为节点的哈密尔顿回路；

充电位置确定模块，用于根据每一第二类传感器与所述哈密尔顿回路上任意位置之间的距离，在所述哈密尔顿回路上确定每一第二类传感器的充电位置；

充电模块，用于遍历所述哈密尔顿回路，以对每一第一类传感器和分别移动至对应的充电位置上的每一第二类传感器进行充电；

其中，所述哈密尔顿回路构建模块具体用于：

根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，计算所述任意两个第一类传感器之间的线路权重；

计算所述线路权重对应的两个第一类传感器之间的电量节约值，并得到节约值矩阵；

根据所述节约值矩阵，基于节约算法构建以所述第一类传感器为节点的哈密尔顿回路；

所述充电位置确定模块具体用于：

在所述哈密尔顿回路上分别寻找距每一第二类传感器最近的位置，并将所述最近的位置确定为对应的第二类传感器的充电位置。

8.根据权利要求7所述的充电装置，其特征在于，还包括：参数计算模块；

所述参数计算模块用于获取无线传感器网络中每一传感器发送的充电请求信息；根据所述充电请求信息，分别向对应的传感器发送电量采集请求，以供所述对应的传感器分别根据所述电量采集请求发送电量信息；分别获取每一传感器发送的所述电量信息，并计算每一传感器的剩余工作时间和每一传感器的第一充电周期。

说明书

无线传感器网络的充电方法及装置

技术领域

[0001] 本发明涉及传感器网络技术领域，更具体地，涉及无线传感器网络的充电方法及装置。

背景技术

[0002] 在现代信息社会中，信息获取最主要的方式之一就是使用传感器进行信息采集。目前，无线传感器网络已广泛应用于电力系统监测、生态监测、海洋监测和交通监测等各类信息监控和获取之中。例如：无线传感器网络具有无线通讯、自组织、节点冗余等特性，可以很好的解决传统的电力监测系统在恶劣环境下不能长时间工作的缺陷。还可将无线传感器网络应用于变电站自动化、电能质量监测、配电网设备监控与故障定位以及输电线路实时监测等监测任务中。在这些监测任务中，都要求传感器网络有较高的续航性能。为了保证传感器网络能够持续高效的工作，需要对无线传感器网络的能量进行研究和优化。

[0003] 无线传感器网络的能量问题主要体现在以下三个方面：(1)对于在一些自然环境恶劣的偏远地方进行的检测工作，人力较难到达，因此对于传感器的充电维护需要很久才能进行一次；(2)在使用无线传感器网络进行监测任务时，为保证监测的连续完整，需要使其满足覆盖性等约束，这对传感器节点的能量维持也有一定的要求；(3)由于传感器节点一般体积较小，能够携带的电池等能量有限。

[0004] 针对无线传感器网络的能量供应问题，现有技术中为急需供电的传感器构造哈密尔顿回路，无线传感器网络中的各急需供电的传感器均位于哈密尔顿回路的节点上，同时保证充电节点遍历整个哈密尔顿回路后，使哈密尔顿回路上的所有急需供电的传感器均得到充电。

[0005] 此方法中，充电节点遍历一次哈密尔顿回路只对急需供电的传感器进行充电，极有可能在对急需供电的传感器完成充电后充电节点还有剩余电量可以利用，而此时却选择返回至充电节点的基地，再第二次遍历哈密尔顿回路。整个过程中，充电节点的很多电量均耗费在哈密尔顿回路的线路上，而不是为传感器进行充电，极大的浪费了电能。

发明内容

[0006] 为克服上述问题或者至少部分地解决上述问题，本发明提供了无线传感器网络的充电方法及装置。

[0007] 一方面，本发明提供了一种无线传感器网络的充电方法，包括：S1，根据无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期，从所有传感器中选取第一类传感器和第二类传感器；S2，根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，构建以所有第一类传感器所在的位置为节点的哈密尔顿回路；S3，根据每一第二类传感器与所述哈密尔顿回路上任意位置之间的距离，在所述哈密尔顿回路上确定每一第二类传感器的充电位置；S4，遍历所述哈密尔顿回路，以对每一第一类传感器和分别移动至对应的充电位置上的每一第二类传感器进行充电。

[0008] 优选地，所述第一充电周期具体为：所述无线传感器网络中每一传感器的电量由电池满电量降至预设电量阈值所需要的时间。

[0009] 优选地，所述每一传感器的剩余工作时间和每一传感器的第一充电周期通过如下方法计算：S01，获取无线传感器网络中每一传感器发送的充电请求信息；S02，根据所述充电请求信息，分别向对应的传感器发送电量采集请求，以供所述对应的传感器分别根据所述电量采集请求发送电量信息；S03，分别获取每一传感器发送的所述电量信息，并计算每一传感器的剩余工作时间和每一传感器的第一充电周期。

[0010] 优选地，S1具体包括：S11，选取所有传感器的第一充电周期中的最小值作为第二充电周期，所述第二充电周期为所述无线传感器网络的充电周期；S12，分别比较每一传感器的剩余工作时间和所述第二充电周期的大小；S13，将小于所述第二充电周期的剩余工作时间所对应的传感器作为所述第一类传感器；S14，将大于或等于所述第二充电周期的剩余工作时间对应的传感器作为所述第二类传感器。

[0011] 优选地，S2具体包括：S21，根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，计算所述任意两个第一类传感器之间的线路权重；S22，计算所述线路权重对应的两个第一类传感器之间的电量节约值，并得到节约值矩阵；S23，根据所述节约值矩阵，基于节约算法构建以所述第一类传感器为节点的哈密尔顿回路。

[0012] 优选地，S3具体包括：在所述哈密尔顿回路上分别寻找距每一第二类传感器最近的位置，并将所述最近的位置确定为对应的第二类传感器的充电位置。

[0013] 优选地，S4具体包括：遍历所述哈密尔顿回路，在所述哈密尔顿回路的每一节点处为对应的第一类传感器充电；在所述哈密尔顿回路上的充电位置上为对应的第二类传感器充电。

[0014] 优选地，所述在所述哈密尔顿回路上的充电位置上为对应的第二类传感器充电前还包括：每一第二类传感器分别以各自的设定速度移动至对应的充电位置。

[0015] 另一方面，本发明提供了一种无线传感器网络的充电装置，包括：传感器分类模块、哈密尔顿回路构建模块、充电位置确定模块和充电模块。

[0016] 其中，传感器分类模块用于根据无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期，从所有传感器中选取第一类传感器和第二类传感器；哈密尔顿回路构建模块用于根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电量，构建以所有第一类传感器所在的位置为节点的哈密尔顿回路；充电位置确定模块用于根据每一第二类传感器与所述哈密尔顿回路上任意位置之间的距离，在所述哈密尔顿回路上确定每一第二类传感器的充电位置；充电模块用于遍历所述哈密尔顿回路，以对每一第一类传感器和分别移动至对应的充电位置上的每一第二类传感器进行充电。

[0017] 优选地，所述充电装置还包括：参数计算模块；所述参数计算模块用于获取无线传感器网络中每一传感器发送的充电请求信息；根据所述充电请求信息，分别向对应的传感器发送电量采集请求，以供所述对应的传感器分别根据所述电量采集请求发送电量信息；分别获取每一传感器发送的所述电量信息，并计算每一传感器的剩余工作时间和每一传感器的第一充电周期。

[0018] 本发明提供的无线传感器网络的充电方法及装置，通过对无线传感器网络中的各传感器进行分类，从中选出第一类传感器和第二类传感器，并以各第一类传感器所在的位置为节点构建哈密尔顿回路，在哈密尔顿回路上确定各第二类传感器的充电位置。最后遍历哈密尔顿回路以对第一传感器和第二传感器进行充电。使MC在一轮充电任务中，可以同时对第一传感器和第二传感器进行充电，使MC中携带的电量得到充分的利用，避免电量过多浪费在哈密尔顿回路的线路上，节约了电量。

附图说明

[0019] 图1为本发明一实施例提供的一种无线传感器网络的充电方法流程图；

[0020] 图2为本发明一实施例提供的一种无线传感器网络的充电方法中各传感器的剩余工作时间和第一充电周期的计算方法流程图；

[0021] 图3为图1中从所述传感器中选取第一类传感器和第二类传感器的方法流程图；

[0022] 图4为图1中基于节约算法构建以所述第一类传感器为节点的哈密尔顿回路的方法流程图；

[0023] 图5为图4中根据所述节约值矩阵，基于节约算法构建以所述第一类传感器为节点的哈密尔顿回路的方法流程图；

[0024] 图6a为本发明一实施例提供的一种无线传感器网络的充电方法中选择各第二类传感器的充电位置的示意图；

[0025] 图6b为本发明一实施例提供的一种无线传感器网络的充电方法中选择各第二类传感器的充电位置的示意图；

[0026] 图6c为本发明一实施例提供的一种无线传感器网络的充电方法中选择各第二类传感器的充电位置的示意图；

[0027] 图7为本发明另一实施例提供的一种无线传感器网络的充电方法示意图；

[0028] 图8为本发明又一实施例提供的一种无线传感器网络的充电装置结构图。

具体实施方式

[0029] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0030] 如图1所示，本发明的一实施例提供了一种无线传感器网络的充电方法，其特征在于，包括：S1，根据无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期，从所有传感器中选取第一类传感器和第二类传感器；S2，根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，构建以所有第一类传感器所在的位置为节点的哈密尔顿回路；S3，根据每一第二类传感器与所述哈密尔顿回路上任意位置之间的距离，在所述哈密尔顿回路上确定每一第二类传感器的充电位置；S4，遍历所述哈密尔顿回路，以对每一第一类传感器和分别移动至对应的充电位置上的每一第二类传感器进行充电。

[0031] 具体地，无线传感器网络(Wireless Sensor Networks，WSN)是一种分布式传感网络，它的末梢是可以感知和检查外部特定参数的传感器。WSN中的传感器通过无线方式通信，因此网络设置灵活，传感器的位置可以随时更改，还可以与互联网进行有线或无线方式的连接。WSN的快速发展也使得WSN的充电方法得到了快速发展。目前对WSN的充电方法包括：电感耦合技术(Inductive Coupling)、电磁辐射技术(Electromegnetic Radiation)及磁耦合谐振技术(Magnetic Resonant Coupling)等。

[0032] 本发明实施例中主要是对无线传感器网络中的传感器的充电方法进行改进，即确定充电节点(Mobile Charge，MC)对传感器充电的先后顺序，以使得传感器可以得到及时充电，并使MC在遍历整个无线传感器网络时可节约电能。对于传感器的通信方式和MC对传感器的充电过程均属现有技术，本发明对此不做限定，也不再赘述。本发明实施例中均以充电节点(Mobile Charge，MC)作为执行主体，充电节点中具有处理器，可以实现分析和计算的功能。以下对无线传感器网络中的传感器的充电方法进行具体说明。在此设定MC从基地Sink出发，最后回到Sink完成一轮充电任务，且MC携带有充足的电量以完成一轮充电任务。

[0033] S1，MC根据无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期，从所有传感器中选取第一类传感器和第二类传感器。

[0034] 具体地，第一充电周期是指无线传感器网络中传感器的电量由传感器的电池满电量降至预设电量阈值需要的时间。电池满电量是指传感器充满电时的电量，预设电量阈值是指传感器需要充电时的剩余电量，传感器若不高于第二电量阈值时将需要进行充电。另一方面，第一充电周期也就是传感器两次充电的时间间隔。

[0035] 本发明实施例中第一类传感器和第二类传感器的分类标准为传感器是处于急需用电还是处于可等待较长一段时间后再进行充电。第一类传感器和第二类传感器之间的分类界限为充电节点为无线传感器网络进行两轮充电的时间间隔，第一类传感器是指剩余电量能够供应的时间小于时间间隔，即急需用电的传感器；第二类传感器是指剩余电量能够供应的时间大于或等于时间间隔，但小于2倍的时间间隔，即可等待充电节点第二次为无线传感器网络充电时再进行充电的传感器。

[0036] S2，MC根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，构建以所有第一类传感器所在的位置为节点的哈密尔顿回路。

[0037] 具体地，采用节约算法构建以所有第一类传感器所在的位置为节点的哈密尔顿回路。节约算法又称C-W算法，其基本思想是：构造一个回路，使整个方案相比于没有构造回路时更节约，这个节约可以是节约时间、节约费用或者节约能量。例如，节点B1和B2分别与源点A相连，分别构成1条仅含一个节点的线路。小红从A出发，到达B1后返回至A，再从A出发，到达B2后再返回至A的总费用为从A到B1、B2的费用之和的两倍；而如果从A出发，依次经过B1和B2之后回到A，根据三角形中两边之和大于第三边的原理可知，经过A、B1和B2回到A的总费用要小于前一种行走线路，即体现了费用的节约。

[0038] 本实施例中，MC将各第一类传感器的位置作为节点，以MC为所有第一类传感器充电所需消耗的电量为指标，基于节约算法构建哈密尔顿回路，使MC遍历整个哈密尔顿回路为所有第一类传感器充电所耗费的电量最少。

[0039] MC为第一类传感器充电所需消耗的电量包括MC在线路上移动时消耗的电量和MC为每个第一类传感器充电时消耗的电量。MC在线路上移动时消耗的电量可通过MC每移动单位距离所消耗的电量与各第一类传感器之间的欧氏距离的乘积计算得到，MC为每个第一类传感器充电时所消耗的电量则根据每一个第一类传感器需要的电量进行求和计算得到。

[0040] S3，MC根据每一第二类传感器与所述哈密尔顿回路上任意位置之间的距离，在所述哈密尔顿回路上确定每一第二类传感器的充电位置。

[0041] 具体地，为保证自身携带的电量可以得到充分的利用，MC在遍历哈密尔顿回路的过程中，还可以为第二类传感器充电。此时，为保证MC可以及时为各第一类传感器充电，MC通常不能移动至哈密尔顿回路外，所以要在S2确定的哈密尔顿回路上确定各第二类传感器的充电位置，使各第二类传感器移动至对应的充电位置等待MC为自身充电。

[0042] 在哈密尔顿回路上确定各第二类传感器的充电位置的方法是：根据各第二类传感器与哈密尔顿回路上任意位置的距离，在哈密尔顿回路上分别寻找距各第二类传感器最近的位置，此位置即为对应的第二类传感器的充电位置。这里对各第二类传感器的充电位置不做限定，特殊的，可以与某一第一类传感器位置重合。各第二类传感器在MC到达对应的充电位置前或与MC同时到达对应的充电位置，使得MC可在充电位置对第二类传感器进行充电，各第二类传感器充电后均分别返回至原来位置。作为优选方案，各第二类传感器与MC同时到达对应的充电位置，防止各第二类传感器离开原来位置的时间过长，延误各第二类传感器的工作。

[0043] S4，遍历所述哈密尔顿回路，以对每一第一类传感器和分别移动至对应的充电位置上的每一第二类传感器进行充电。

[0044] 由S2构建哈密尔顿回路，由S3在哈密尔顿回路上确定各第二类传感器的充电位置，此时MC从Sink出发，遍历哈密尔顿回路，在哈密尔顿回路的每一节点处为对应的第一类传感器充电；在哈密尔顿回路上的每一第二类传感器的充电位置为对应的第二类传感器充电，最后回到Sink进行电量补充，为下一轮充电做准备。

[0045] 本实施例中，通过对无线传感器网络中的各传感器进行分类，从中选出第一类传感器和第二类传感器，并以各第一类传感器为节点构建哈密尔顿回路，在哈密尔顿回路上确定各第二类传感器的充电位置。最后由MC遍历哈密尔顿回路以对第一传感器和第二传感器进行充电。使MC在一轮充电任务中，可以同时对第一传感器和第二传感器进行充电，使MC中携带的电量得到充分的利用，避免电量过多浪费在哈密尔顿回路的线路上，节约了电量。

[0046] 在上述实施例的基础上，如图2所示，无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期通过如下方法计算：S01，获取无线传感器网络中每一传感器发送的充电请求信息；S02，根据所述充电请求信息，分别向对应的传感器发送电量采集请求，以供所述对应的传感器分别根据所述电量采集请求发送电量信息；S03，分别获取每一传感器发送的所述电量信息，并计算每一传感器的剩余工作时间和每一传感器的第一充电周期。

[0047] 具体地，这里的充电请求信息由无线传感器网络中需要供电的传感器发送至MC，MC获取充电请求，并根据充电请求向发出充电请求的传感器发送电量采集请求。传感器接收到MC发送的电量采集请求后便向MC发送电量信息。这里的充电请求信息是在传感器的剩余电量不高于第二电量阈值发出的，即剩余电量占传感器的电池容量的百分比不高于预设比例时向MC发出充电请求。其中，预设比例是指是否需要充电的临界值，若剩余电量占传感器的电池容量的百分比高于预设比例，则不需向MC发出充电请求，即不需进行充电。

[0048] 这里需要说明的是，由于无线传感器网络中各传感器的实际工作内容或性能、作用不同，对应的预设比例也不相同。因此，即使传感器因剩余电量占电池容量的百分比不高于预设比例而向MC发出充电请求，也可将传感器分为第一类传感器和第二类传感器。预设比例可根据需要选择不同的值，例如10％、5％等，但不限于此。

[0049] 传感器向MC发送的电量信息包括：传感器的电池容量、预设比例和单位时间能耗。电量信息内携带有传感器所处的位置，以供MC明确哪一位置的传感器需要充电。MC则获取传感器发送的电量信息，并计算传感器的剩余工作时间和第一充电周期。

[0050] 例如：MC接收到无线传感器网络中第i个传感器si发送的电量信息，具体包括电池容量bi，预设比例a，单位时间耗能ei，则计算传感器的剩余工作时间为ti＝bi*a/ei；第一充电周期为Ti＝bi*(1-a)/ei。

[0051] 在上述实施例的基础上，如图3所示，S1具体包括：S11，选取所有传感器的第一充电周期中的最小值作为第二充电周期，所述第二充电周期为所述无线传感器网络的充电周期；S12，分别比较每一传感器的剩余工作时间和所述第二充电周期的大小；S13，将小于所述第二充电周期的剩余工作时间所对应的传感器作为所述第一类传感器；S14，将大于或等于所述第二充电周期的剩余工作时间对应的传感器作为所述第二类传感器。

[0052] 具体地，设无线传感器网络中共有N个传感器向MC发送充电请求，分别标记为s1、s2、…、si、…、sN，对应的位置为S1、S2、…、Si、…、SN，对应的第一充电周期分别为T1、T2、…、Ti、…、TN，对应的剩余工作时间分别为t1、t2、…、ti、…、tN。若第一充电周期中的最小值为Tmin，则将Tmin作为第二充电周期。这里的第二充电周期即指整个无线传感器网络的充电周期。Tmin满足如下公式：

[0053]

[0054] 其中，Ti表示第i个传感器si对应的第一充电周期，i的取值范围为1～N。

[0055] 将计算得到的各传感器的剩余工作时间ti和第二充电周期Tmin进行比较。若比较结果为ti

[0056] 本实施例中，MC将发送充电请求的传感器分为第一类传感器和第二类传感器，为后续MC部署充电回路做准备。

[0057] 在上述实施例的基础上，如图4所示，S2具体包括：S21，根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电能，计算所述任意两个第一类传感器之间的线路权重；S22，计算所述线路权重对应的两个第一类传感器之间的电量节约值，并得到节约值矩阵；S23，根据所述节约值矩阵，基于节约算法构建以所述第一类传感器为节点的哈密尔顿回路。

[0058] 具体地，设MC每移动单位距离消耗的电量为eC，任意两个第一类传感器之间的欧氏距离为d(Si，Sj)，Si和Sj表示任意两个不同的第一类传感器所在的位置，即i≠j。Si和Sj之间的线路权重为Dij＝d(Si，Sj)*eC，即MC由Si移动至Sj消耗的电能。根据计算得到的线路权重计算MC由Si移动至Sj的电量节约值CSij。

[0059] 电量节约值CSij的计算方法如下：MC要想为充电，有两种移动线路，一种是从Sink出发至Si后返回至Sink，再从Sink出发至Sj后返回至Sink；另一种是MC从Sink出发，依次经Si、Sj或Sj、Si(以下均以依次经Si、Sj为例，由于i、j表示第一类传感器的标号，令i

[0060] 将计算得到的电量节约值分别填入矩阵，构成节约值矩阵W，矩阵有n-1行、n-1列，以i作为行标，以j作为列标，则有1≤i

[0061]

[0062] 基于节约算法构建以所有第一类传感器所在位置为节点的哈密尔顿回路。

[0063] 在上述实施例的基础上，构建哈密尔顿回路的具体方法如图5所示。

[0064] S231，连接所述节约值矩阵中的最大电量节约值对应的两个所述第一类传感器以构成线路，并删除所述节约值矩阵中所述最大电量节约值所在的行和列的电量节约值，形成新的节约值矩阵；

[0065] S232，若判断获知所述新的节约值矩阵中最大电量节约值对应的两个所述第一类传感器均不在已构成的线路上，连接两个所述第一类传感器所在的位置以构成新的线路，执行S233；

[0066] 若判断获知所述新的节约值矩阵中最大电量节约值对应的两个所述第一类传感器均在已构成的不同线路上，且均不与所述基地位置直接相连，则连接两个所述第一类传感器所在的位置以构成新的线路，执行S233；

[0067] 若判断获知所述新的节约值矩阵中最大电量节约值对应的两个所述第一类传感器中仅一个所述第一类传感器在已构成的线路上，且不与所述基地位置直接相连，则连接两个所述第一类传感器所在的位置以构成新的线路，执行S233；

[0068] 否则，执行S234；

[0069] S233，计算遍历已构成的所有线路需要的必需电能，若充电节点的电池容量小于所述必需电能，执行S234；

[0070] S234，删除所述节约值矩阵中所述最大电量节约值所在的行和列的所有电量节约值，形成新的节约值矩阵；

[0071] S235，重复执行S232-S234，直至所述新的节约值矩阵为空，得到的线路即为哈密尔顿回路。

[0072] 具体地，假设节约值矩阵中的最大电量节约值为Dmn，与之对应的两个第一类传感器分别为sm和sn。执行S231，连接Sm和Sn以构成线路Rmn，并删除节约值矩阵中m行和n列的电量节约值，即除去由Sm到除Sn外的其他位置的线路，以及除去由除Sm外的其他位置到Sn的线路。除去m行和n列的电量节约值后可得到新的节约值矩阵。此时MC的基地位置(即Sink)和已构成的线路Rmn可构成充电回路(即Sink-Sm-Sn-Sink)。

[0073] 通过S232提供的条件选择后续执行的步骤，设新的节约值矩阵中的最大电量节约值为Dm’n’，对应的两个第一类传感器分别为sm’和sn’。若判断获知sm’和sn’均不在已构成的线路上，连接Sm’和Sn’以构成新的线路，执行S233；若判断获知sm’和sn’均在已构成的线路上，且Sm’和Sn’均不与Sink直接相连，则连接Sm’和Sn’以构成新的线路，执行S233；若判断获知sm’和sn’中仅有一个在已构成的线路上，且在已构成的线路上的传感器所在的位置不与Sink直接相连，则连接Sm’和Sn’以构成新的线路，执行S233；除此之外，若判断获知sm’和sn’在已构成的同一条线路上，则执行S234。

[0074] 通过S232中条件的判断，后续执行S233或S234。

[0075] 具体地，S233，MC从Sink出发，遍历已构成的所有线路，计算需要的必需电能。这里所说的必需电能包括MC在所有线路上移动时所需的电能和，以及MC为所有线路上的各第一类传感器充电时需要的电能和。当MC的电池容量小于必需电能时，即MC在执行一轮充电任务时，不能完成充电任务。此时执行S234。

[0076] S234，删除节约值矩阵中最大电量节约值Dm’n’所在的行m’和列n’的所有电量节约值。

[0077] S235，重复执行上述S232-S234，直至新的节约值矩阵为空，此时得到的线路即为哈密尔顿回路。

[0078] 在上述实施例的基础上，S3具体包括：在所述哈密尔顿回路上分别寻找距每一第二类传感器最近的位置，并将最近的位置确定为对应的第二类传感器的充电位置。

[0079] 在上述实施例的基础上，S4具体包括：遍历所述哈密尔顿回路，在所述哈密尔顿回路的每一节点处为对应的第一类传感器充电；在所述哈密尔顿回路上的每一第二类传感器的充电位置为对应的第二类传感器充电。

[0080] 在上述实施例的基础上，MC在所述哈密尔顿回路上的充电位置上为对应的第二类传感器充电前还包括：每一第二类传感器分别以各自的设定速度移动至对应的充电位置。

[0081] 具体地，设第一类传感器有p个，即s1、s2、…、si、…、sp，对应的位置为S1、S2、…、Si、…、Sp。为与第一类传感器区分，设第二类传感器有q个，p与q可相等也可不相等，是相对独立的。将第二类传感器分别标记为2s1、2s2、…、2si、…、2sq，对应的位置为2S1、2S2、…、2Si、…、2Sq。

[0082] 第二类传感器有可能位于哈密尔顿回路的内部或者哈密尔顿回路的外部，特别地，还有可能位于哈密尔顿回路的线路上。第二类传感器有可能位于哈密尔顿回路的内部或者哈密尔顿回路的外部时，第一类传感器固定不动，在MC运行至适当位置时第二类传感器由原来位置以设定速度移动至哈密尔顿回路上的充电位置，以使第二类传感器与MC同时到达充电位置。在充电位置由MC为对应的第二类传感器充电。各第二类传感器在充电位置完成充电后返回至原来位置，并继续执行任务。当第二类传感器位于哈密尔顿回路的线路上时，在MC执行一轮充电任务时第一类传感器和第二类传感器的位置均固定。

[0083] 这里的设定速度是指保证第二类传感器在MC到达对应的充电位置前或与MC同时到达对应的充电位置，使得MC可在充电位置对第二类传感器进行充电，且MC不会产生等待时间。

[0084] 以下分别从三种情况进行说明，如图6a、图6b和图6c所示。

[0085] 图6a中，假设在哈密尔顿回路上两个相邻的第一类传感器sl-1和sl之间的线路上方存在一个第二类传感器2si，由于2si到sl-1和sl所在的直线的最短距离为2si向直线引的垂线段的长度，且垂足在线路R(l-1)l上，所以以垂足点作为2si的充电位置2Spi。通过2Si与充电位置2Spi之间的距离，以及MC的移动速度，可计算2si的出发时间和2si的移动速度，以保证MC和2si可同时到达2Spi或2si先于MC到达2Spi。2si的移动速度即为设定速度。

[0086] 图6b中，假设在哈密尔顿回路上两个相邻的第一类传感器sl-1和sl之间的线路外靠近sl的一个位置2Si存在一个第二类传感器2si，由于2si到sl-1和sl所在的直线的最短距离2
为si向直线引的垂线段的长度，但这种情况下垂足并不在线路R(l-1)l上，所以不能以垂足点作为2si的充电位置，而是以离2si最近的第一类传感器sl所在的位置作为2si的充电位置
2Spi。2Si与充电位置2Spi之间的距离即2si与sl之间的距离，通过2Si与充电位置2Spi之间的距离，以及MC的移动速度，可计算2si的出发时间和2si的移动速度，以保证MC和2si可同时到达
2 2 2 2
Spi或si先于MC到达Spi。si的移动速度即为设定速度。

[0087] 图6c中，假设在哈密尔顿回路上两个相邻的第一类传感器sl-1和sl之间的线路外靠近sl-1的一个位置2Si存在一个第二类传感器2si，由于2si到sl-1和sl所在的直线的最短距离为2si向直线引的垂线段的长度，但这种情况下垂足并不在线路R(l-1)l上，所以不能以垂足2 2 2
点作为 si的充电位置，而是以离si最近的第一类传感器sl-1所在的位置作为 si的充电位置2Spi。2Si与充电位置2Spi之间的距离即2si与sl-1之间的距离，通过2Si与充电位置2Spi之间的距离，以及MC的移动速度，可计算2si的出发时间和2si的移动速度，以保证MC和2si可同时到达2Spi或2si先于MC到达2Spi。2si的移动速度即为设定速度。

[0088] 本发明的另一实施例中，提供了一种无线传感器网络的充电方法，假设有如图7所示无线传感器网络，根据各传感器的剩余工作时间和第一充电周期，从中得到5个第一类传感器(分别为图7中的s1、s2、s3、s4和s5)，以及4个第二类传感器(分别为图7中的2s1、2s2、2s3、和2s4)。基于节约算法构建以5个第一类传感器为节点的哈密尔顿回路，如图7中虚线构成的回路。确定哈密尔顿回路后，分别计算4个第二类传感器到哈密尔顿回路的最小距离，并确定各第二类传感器的充电位置分别为2Sp1、2Sp2、2Sp3和2Sp4。

[0089] 确定哈密尔顿回路和各第二类传感器的充电位置后，MC从Sink出发，沿哈密尔顿回路开始执行充电任务，即依次经Sink-S1-2Sp1-S2-2S2-S3-2Sp3-S4-S5-2Sp4-Sink。当MC经线路Ro1移动至S1位置时，为给第一类传感器s1充电，充电完成后，MC沿线路R12移动，在移动过程中，经过充电位置2Sp1时为在充电位置处的第二类传感器2s1充电，充电完成后，2s1返回原来位置，MC则继续沿线路R23移动到S2并给s2充电。然后，以相同的方法沿哈密尔顿回路依次给2s2、s3、2s3、s4、s5和2s4充电，最终返回至Sink补充电量。

[0090] 如图8所示，本发明的又一实施例提供了一种无线传感器网络的充电装置，包括：传感器分类模块81、哈密尔顿回路构建模块82、充电位置确定模块83和充电模块84。

[0091] 其中，传感器分类模块81用于根据无线传感器网络中每一传感器的剩余工作时间和每一传感器的第一充电周期，从所有传感器中选取第一类传感器和第二类传感器；哈密尔顿回路构建模块82用于根据任意两个第一类传感器之间的欧氏距离和充电节点每移动单位距离所消耗的电量，构建以所有第一类传感器所在的位置为节点的哈密尔顿回路；充电位置确定模块83用于根据每一第二类传感器与所述哈密尔顿回路上任意位置之间的距离，在所述哈密尔顿回路上确定每一第二类传感器的充电位置；充电模块84用于遍历所述哈密尔顿回路，以对每一第一类传感器和分别移动至对应的充电位置上的每一第二类传感器进行充电。

[0092] 在上述实施例的基础上，上述充电装置还包括：参数计算模块；所述参数计算模块用于获取无线传感器网络中每一传感器发送的充电请求信息；根据所述充电请求信息，分别向对应的传感器发送电量采集请求，以供所述对应的传感器分别根据所述电量采集请求发送电量信息；分别获取每一传感器发送的所述电量信息，并计算每一传感器的剩余工作时间和每一传感器的第一充电周期。

[0093] 本实施例中的具体操作流程与上述方法类实施例一一对应，在此不再赘述。

[0094] 本实施例中，通过传感器分类模块对无线传感器网络中的各传感器进行分类，从中选出第一类传感器和第二类传感器，并通过哈密尔顿回路构建模块以各第一类传感器为节点构建哈密尔顿回路，由充电位置确定模块在哈密尔顿回路上确定各第二类传感器的充电位置。最后由充电模块中的MC遍历哈密尔顿回路以对第一传感器和第二传感器进行充电。使MC在一轮充电任务中，可以同时对第一传感器和第二传感器进行充电，使MC中携带的电量得到充分的利用，避免电量过多浪费在哈密尔顿回路的线路上，节约了电量。

[0095] 最后，本发明的方法仅为较佳的实施方案，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。