无线可充电传感器网络中的充电桩部署

胡 亮,孙杨燕,任 祝

(浙江理工大学 信息学院，浙江 杭州 310018)

0 引言

如今，在无线传感器网络中，电池是传感器的主要能量来源[1-2]，但是电池容量限制了传感器的使用寿命，也影响了传感器网络的整体表现[3]。无线可充电传感器网络可被视为一种通过引入无线能量传输技术的新型传感器网络[4]，其中，充电桩以电磁辐射的形式将能量传输到传感器网络中，而可充电的传感器节点将通过配置的天线来接收射频能量[5]。这种新型传感器网络因为其方便易行和使用寿命长已被广泛使用，包括智能电网[6]、医疗保健[7]和环境监控[8]等。

目前，研究无线传感器网络中的静态充电桩部署较为稀少，且存在许多限制[9]。例如，文献[10]研究了如何部署全向充电桩，使得网络中静态或动态的传感器节点能够获得足够的能量维持正常工作，但是其仅仅讨论了传统的等距三角形部署，主要目的是尽可能减小三角形的边长；文献[11]将传感器区域划分为网格，充电桩的覆盖区域为圆形，文中充电桩仅能放在网格顶点中，但实际上，充电桩可能部署在传感器区域中的任何位置，而且该文中的充电桩覆盖范围不合理。在传感器区域中传感器位置固定的情况下，为了尽可能减少部署充电桩的数量，无需确保区域中每个位置接收到的能量都能满足传感器的消耗，只需要保证传感器所在位置的能量能够维持传感器运行即可。

本文主要针对能量受限的无线传感器网络，利用整数规划研究充电桩的分布问题[12]，根据已有的传感器位置分布研究如何进行充电桩的部署，尽可能用最少数目的充电桩使得每一个传感器都能够获得足够的能量维持自身运行，从而优化无线可充电传感器网络。

1 系统模型

假设无线可充电传感器网络区域Ω是一个二维平面，有M个可充电传感器随机分布在这块区域上，并且用S={s1,s2,…,sm}表示这些传感器，另外用C={c1,c2,…,cn}表示N个可用来部署充电桩的位置。下面需要决定是否在这些位置部署充电桩为该区域的所有传感器提供足够能量，使它们能够正常持续的工作。

对于单个充电桩对传感器的充电模型，用文献[15]中已经得到验证的充电公式来描述：

(1)

式中，d(si,cj)为传感器si和充电桩cj的距离，Pr(d)为传感器接收到的能量。

对于二维平面区域Ω的充电桩部署模型，用下面的公式来描述：

(2)

2 充电桩部署策略

2.1 充电桩位置固定

假设在可充电传感器网络区域中，随机分布着M个传感器用来采集信息，同时该区域中有N个固定的位置用来部署充电桩为传感器提供能量，如图1所示。目标是从N个充电桩可以部署的位置中找到最佳的位置来部署充电桩，最大限度地减少整个区域中充电桩的数量并确保所有传感器正常工作。

图1 充电桩位置固定示意图

2.1.1 问题转化

对于任意传感器si，总共接收到区域中所有充电桩的能量为：

(3)

(4)

2.1.2 充电桩位置固定部署算法

2.2 充电桩位置不固定且不受限

前面描述了充电桩位置固定的情形，但是一些情况下，充电桩可以部署的位置并不固定。如图2所示，假设传感器区域中随机分布着M个传感器，但是并没有给出充电桩可以部署的地点，需要在该区域中部署最少的充电桩来维持传感器的正常工作。

因为位置不固定，需要将整个区域进行网格化，每个网格的顶点都可以当作一个部署位置，这样问题将会转化为充电桩位置固定的问题，且随着划分的不断加密，所需要的充电桩个数将会减少到一个稳定的最小值。

图2 充电桩位置不固定且不受限示意图

2.2.1 问题转化

(5)

2.2.2 充电桩位置不固定且不受限部署算法

2.3 充电桩位置不固定且受限

在实际环境中，充电桩的部署可能会受到区域限制，即充电桩只能部署在传感器区域的某个地方或不能部署在传感器区域的某个地方，比如，区域中存在一些建筑物、交通要道或者水域等等。由于这2种限制比较相似，只考虑充电桩不能部署在区域中的某些地方的这种情形，如图3所示，A1,A2区域将禁止部署充电桩。

图3 充电桩位置不固定且受限示意图

2.3.1 问题转化

得到如下新的目标函数和约束条件：

(5)

(X,Y)∉(A1∪A2),

2.3.2 充电桩位置不固定且受限部署算法

3 仿真结果

3.1 充电桩位置固定

如图4所示，黑色圆点表示在传感器区域中随机分布的传感器，黑色矩形框表示可以部署充电桩的位置，黑色三角形表示需要在该位置部署充电桩。如图4(a)和图4(b)所示，2幅图的传感器分布一致，由于可以部署的8个位置不同，需要的充电桩总数可能不同。在图4(a)的部署位置分布下，需要至少4个充电桩才能维持该传感器网络的正常工作，而在图4(b)的部署位置分布下，只需要3个充电桩就可以维持传感器网络的正常工作。

图4 充电桩位置固定时的最佳部署

3.2 充电桩位置不固定且不受限

对于充电桩位置不固定且不受限的情形，设置长度为30 m的正方形区域，随机分布着20个传感器，其余参数与位置固定时保持一致，如图5所示。

图5 充电桩位置不固定且不受限时的部署

在图5(a)中，整个传感器网络区域被划分为5×5的网格，划分间隔为6 m。在这种划分情形下，找不到一个可行解使得所有传感器能够持续正常的工作，即在36个可以部署充电桩的网格顶点中找不到足够的位置来部署充电桩。

在图5(b)中，将划分间隔缩小为3 m，即将整个区域划分为10×10的网格。因此可以得到121个可以用来部署充电桩的位置。相比于图5(a)，在这种划分情形下，可以部署至少16个充电桩来为整个网络提供能量。

在图5(c)中，划分间隔进一步被缩小到1 m。由于划分更加密集，因此相比于图5(b)，只用15个充电桩就可以满足所有传感器的能量需求。随着划分间隔不断缩小，整个网格将近似覆盖整个区域，所需要的充电桩将减少到一个稳定的最小值。

在图5(d)中，充电桩个数已达到一个稳定的最小值，即随着划分密度的增加，充电桩的个数将不会减少，为了便于分析图中划分间隔设为0.5 m，最终整个区域所需要的最少充电桩为14个。与图5(c)相比，整体的部署趋势没有发生改变，在传感器较密集的地方，所需要的充电桩也会比较多，一些远离群体的节点将会单独需要一个充电桩来满足自身的能量需求。

3.3 充电桩位置不固定且受限

对于充电桩位置不固定且受限的情形，同样设置一个长度为30 m的正方形区域，但是在左上角存在一个受限的矩形区域，右下角存在一个受限的圆形区域，整个正方形区域随机分布着20个传感器，分布位置与充电桩位置不固定且不受限时一致，其余参数与充电桩位置固定时相同,如图6所示。

图6 充电桩位置不固定且不受限时的部署

在图6(a)中，传感器网络区域任意被划分成25个小区域，而所有的传感器位置保持不变，左上角矩形区域和右下角圆形区域均不能部署传感器。与图5(a)相比，在同样的划分条件下，部署区域有了更多的限制，因此，在这种划分下也找不到一个可行解。

在图6(b)中，传感器网络区域被以间隔为3 m进行划分，在这种划分情形下，部分顶点落在了左上角和右下角的不可部署区域内。从图中可以看出，在有限制的条件下，至少需要21个充电桩才能满足需要，而图5(b)在同样划分情况下只需要16个。

在图6(c)中，划分间隔被进一步缩小到了1 m，因此只需要17个充电桩就可以满足传感器的能量需求，比图6(b)少了4个，但是要比图5(c)多用2个。

在图6(d)中，充电桩的数量已经减小到一个稳定值。即整个有限制区域最少需要的充电桩的数量为16个，比没有限制的图5(d)要多用2个。观察分布图可以发现，在有限制的区域，充电桩一般会沿着限制区域的边界进行分布。

4 结束语

针对无线可充电传感器网络中的静态充电桩的部署，对于可部署位置无穷的情况，创新性地利用网格分割方法将传感器区域离散化处理，极大地简化了充电桩的部署问题。然后利用Intlinprog函数分别给出了在3种情形下的部署算法，并且通过Matlab仿真显示，与已有的蜂窝型部署相比，本文方法减少了所需充电桩的数量。