传统的传感器节点由能量有限的电池驱动,导致网络的整体寿命受到限制.为了解决这一问题,许多工作提出了能量节省^[1]和能量汲取^[2]的方法,但均不能从本质上解决这一问题.能量节省方法只能有限地延长网络寿命,网络最终还是会因节点耗尽能量而死亡.能量汲取办法允许节点从周边环境中汲取诸如太阳能、风能等多种形式的能量,但汲取效率深受环境因素的影响,具有高度不可预测性等缺点,导致传感器节点不能持续和可靠地工作.最近几年兴起的无线电能传输技术^[3]为彻底解决无线传感器网络寿命受限问题带来了希望.无线电能传输技术允许能量由充电器无线传输到如RFID^[4]、传感器^[5]、手机^[6]、笔记本电脑^[7]等终端设备中.在无线传感器领域,该技术已被用于改善多种应用场景中传感器的监测性能,如动物信息采集^[8]、数据中心监测^[9]等.由于无线电能传输技术使用的方便性和提供能量的稳定性,受到了科研界和工业界的广泛关注.根据最新报导,到2015年,无线电能传输技术的市场规模有望增至237亿美元^[10].

可以由无线充电器充电的传感器网络也称为无线可充电传感网(wireless rechargeable sensor networks,简称WRSNs)^{[11, 12, 13, 14]}.无线可充电传感网中的一个关键问题是无线充电器的布置问题.由于无线充电器的价格不菲(例如Powercast公司的无线充电器TX91501^[15]价格约为300美元),在区域内布置数目较多甚至冗余的充电器并不现实.但另一方面,传感器的充电功率大小对其工作性能有至关重要的影响.因此,如何有效地布置无线充电器,使得传感器网络整体的充电性能最大化,是一个亟待解决的问题.

目前,研究无线充电器布置问题的工作并不多见,且存在诸多局限性.如文献^[16]研究了如何布置全向的充电器网络,使得位于该网络内的静止或移动的标签(tag)可以接收到足够大的功率维持正常的工作.但该文中仅讨论了充电器网络为传统的等距三角形布置的情况,其研究目标仅是尽可能减少三角形布置的边长.文献^{[17, 18]}将区域划分为网格,并选择网格布置充电器,充电器的覆盖区域均为圆形区域.以上这些工作的不足之处主要有以下两点:一是充电器只能布置在三角形顶点或网格顶点处,布置的位置受限,而实际情况中,充电器一般都可布置在区域内任何一处;二是充电器的覆盖区域均被假设为圆形,而实际充电器的覆盖区域通常为扇形.这是因为在工程实践中,带有向天线的充电器与采用全向天线的充电器相比可提供更为均匀的功率覆盖、更低的能量消耗以及更高的可靠性^[19].基于这一考虑,Powercast公司的无线充电器TX91501就被设计为内置有向天线,其充电的覆盖区域近似为一个60°的扇形区域.

为了克服以往工作的缺点,本文的目标是如何在给定区域内不受限制地布置M个有向充电器,即,如何设置M个充电器的位置和朝向,使得区域内传感器网络的充电效用最大化.基于现实的考虑,定义传感器的充电效用与其充电功率大小成正比,并在充电功率超过一个给定阈值后即变为常数.由于目前没有可用的有向充电模型,本文在实际测量数据的基础上,首次建立了有向充电的经验模型.本文考虑的问题具有非常大的挑战性,这是因为:(1)每个传感器的充电功率与到充电器的距离有比较复杂的数学关系,并且空间中某点处的接收功率为各个充电器在此点充电功率的叠加;(2)由于有向充电器的位置和朝向可以连续变换,理论上可选的解空间为无限大.本文提出了一系列创新方法对该问题进行处理,并在此基础上设计了一种高效的近似算法——CDG (chargerdeployment-greedy)算法.此外,虽然本文工作与传统的有向传感器布置有相似之处,但一方面,目前所有的关于有向传感器网络的工作均未考虑在给定传感器的数目时,如何一般化地布置传感器来最大化覆盖目标或覆盖效用,因此本文无法直接借鉴这些已有工作;另一方面,有向传感器网络中的覆盖问题从本质上来说可以抽象为简单的几何问题,而本文考虑的功率覆盖问题中每个传感器的充电功率与它到充电器的距离有比较复杂的数学关系,并且空间中某点处的接收功率为各个充电器在此点充电功率的叠加.这些因素使得本文考虑的问题与传统的有向传感器覆盖问题截然不同,更具挑战性.本文的贡献如下:

·首次通过实测数据建立有向充电模型,并也是首次考虑有向无线充电器平面一般布置问题;

·证明了有向无线充电器的布置问题是NP难问题,并提出了一种近似比为(1-1/e)/(1+ε)的高效近似算法——CDG算法.具体而言,本文提出了两种创新方法,即,平面区域离散化和覆盖支配集抽取,将无限解空间等价变换为有限解空间;之后对问题进行了重构,并证明了重构问题具有子模性,相应地提出近似算法CDG并证明其近似比;

·通过深入仿真实验,对得到的理论结果进行了验证.实验结果表明了近似算法的有效性,并且其性能与提出的其他两种随机算法——RPRO(randomposition and random orientation)算法和RPDO (random position and discretized orientation)算法相比提高了约300%和100%.

本文第1节对现有相关工作进行简介.第2节介绍与问题相关的模型,并给出问题的形式化定义.第3节给出CDG算法的详细描述及性能分析.第4节给出CDG算法的仿真与比较结果.第5节对全文进行总结.

1 相关工作

近些年,无线充电器的布置问题逐渐受到了学术界和工业界的重视,一些已有工作对其进行了深入的研究.文献^[16]研究了如何布置全向的充电器网络,使得位于该网络内的静止或移动的标签(tag)可以接收到足够大的功率以维持正常的工作.但该文仅讨论了充电器网络为传统的等距三角形布置的情况,其研究目标仅是尽可能减少三角形布置的边长.文献^[17]将区域划分为网格,并选择格点布置全向充电器.该文主要考虑如何在对终端传感器的移动模式有预先了解的情况下,进一步优化全向充电器的布置.文献^[18]假设每个充电器布置在场景中H高度的平面上,并且类似于文献^[17],将可布置的平面划分为网格,充电器只能布置在格点上,可充电传感器位于充电器下方区域内.文献^[18]假设充电器的覆盖区域为圆锥,因而充电器在传感器所在平面内覆盖区域为圆形.该文的目标是布置尽可能少的充电器来覆盖所有的传感器,并允许充电器进行睡眠调度,以减少能耗.值得注意的是,文献^[18]并没有建立明确的充电模型,而是用实时测量得到的充电功率值作为算法的输入.此外,其采用的充电器覆盖区域为圆锥的假设也缺乏实验验证,并且在实际处理过程中,充电器的覆盖区域仍作为圆形区域来处理,这使得文献^[18]的工作与基于全向充电器的工作并无实质上的不同.综上所述,已有的研究无线充电器布置方面的工作均未考虑一般场景中的布置问题,即,无线充电器可以布置在区域内任意一个位置.另外,他们也没有考虑覆盖区域为扇形的一般有向充电器的布置问题.

与本文相关的工作还包括有向传感器网络中的覆盖问题.文献^{[20, 21, 22]}通过将区域划分为网格,从而把有向传感器的布置问题建模成为整数线性规划问题.每一个格点都代表了一个可能的布置位置.这些文献使用了一个简单的可视模型,即,将有向传感器的可见范围定义为一个三角形.文献^[23]考虑了在给定传感器的情况下,如何在二维平面上布置尽量少的有向传感器来覆盖所有的传感器,同时保证有向传感器之间相互连通,并且提出一种近似算法来解决此问题.文献^[24]研究了在有向传感器和传感器的位置均已确定的情况下,如何挑选出尽量少的有向传感器,并设置其朝向,以保证覆盖所有的传感器.此外,文献^[24]还讨论了一个类似的问题,即,如何设置所有的有向传感器的朝向,使得覆盖的传感器数量最大化.对于这两类问题,文献^[24]都提出了近似算法,并证明了其近似比.文献^[25]同时考虑了有向传感器和基站的布置问题,以及如何在给定的位置点中选定位置布置传感器和基站,使得在满足覆盖和连通性的前提下最小化网络的整体开销.总而言之,目前所有的关于有向传感器网络的工作均未考虑在给定传感器的数目时,如何一般化地布置传感器来最大化覆盖目标或覆盖效用,因此,本文无法直接借鉴这些已有工作.另一方面,有向传感器网络中的覆盖问题从本质上来说是一种简单的几何覆盖问题,而本文考虑的功率覆盖问题中每个传感器的充电功率与其到充电器的距离有比较复杂的数学关系,并且空间中某点处的接收功率为各个充电器在此点充电功率的叠加.这些因素使得本文考虑的问题与传统的有向传感器覆盖问题截然不同,更具挑战性.

2 问题描述 2.1 网络模型

假设有N个可充电传感器分布在一个二维区域Ω中,标记为O={o₁,o₂,…,o_N},传感器的位置都是已知的.有待布置的M个有向无线充电器,标记为S={s₁,s₂,…,s_M}.每个充电器都可以布置在区域Ω中任何一点处,并且可以任意设置朝向.假设每个充电器的充电区域覆盖了传感器O的某个子集,相邻的充电器可以覆盖共同的传感器,因此,这意味着某个传感器可能被多个充电器同时覆盖充电.

2.2 充电模型

据目前所知,绝大部分已有工作均采用全向充电模型,即:在与充电器相同距离处,传感器接收的功率相同.此外,考虑到实际情况中接收功率会随距离不断衰减,在某个距离之外的功率几乎可以忽略不计,因此,不少工作^{[16, 17, 18]}都假设充电器覆盖的充电区域是一个以充电器为中心的圆,在此圆覆盖范围之外的区域充电功率为0.与以往文献不同的是,本文中采用的是更实际的有向充电模型,即,无线充电器的充电覆盖区域为一扇形.这样假设的依据是,目前有不少公司的无线充电器使用的是有向天线,如Powercast公司^[15]的无线充电器TX91501在水平面处的充电范围为60°的扇形区域.此外,这些公司之所以采用有向天线而非全向天线,是因为布置带有向天线的充电器与采用全向天线的充电器相比能提供更为均匀的功率覆盖、更低的能量消耗以及更高的可靠性^[19].

图 1(a)展示了实地测量Powercast公司无线充电器TX91501在随距离和角度发生变化时的充电功率变化的场景;可充电传感器是搭载有Powercast公司生产的P2110功率接收器的传感器;传感器接收功率并测量其大小,将数据发送给连接笔记本电脑的AP,然后,笔记本电脑通过串口收集AP发送的数据(实际测量时,电脑和AP距离充电器和传感器较远以减少电磁干扰,图 1(a)中距离设置得很近,仅为了展示方便).测量时,充电器朝向对准0°度位置.测量角度变化范围为0°~360°,且每次测量间隔为10°.测量距离为30cm~70cm.由图 1(b)所示测量结果中可以发现,充电器只有在位于其正前方约60°范围内时才有较强的充电功率(单位为mW).虽然在其他角度,甚至充电器背后180°处都有功率泄露,但其相对于正前方的功率可以近似忽略.此外,接收功率随距离的增大迅速衰减.当其从30cm增大到70cm时,接收功率减少了将近4倍.根据现场实验,在距离大于150cm时,传感器接收功率低于1mW,可以忽略不计.

基于这一观察,本文采用如图 2所示的有向充电模型.充电器s_i充电覆盖扇形区域的圆心角为A,半径为D. 此外,$\overrightarrow F $为充电器s_i与某一传感器o_j构成的向量,$\overrightarrow {{1_{{\vartheta _i}}}} $为代表充电器朝向θ_i的单位矢量.

类似于文献^[26],判断一个target是否位于有向传感器覆盖区域内部的Target In Sector(TIS)测试,可用如下函数判断传感器o_j是否位于扇形区域覆盖角度范围内:

$J({s_i},{\vartheta _i},{o_j}) = \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ }}\overrightarrow F \cdot \overrightarrow {{1_{{\vartheta _i}}}} \;\; - \;||\overrightarrow F |{|_2}\cos \left( {\frac{A}{2}} \right) \ge 0}\\ {0,{\rm{ }}\overrightarrow F \cdot \overrightarrow {{1_{{\vartheta _i}}}} \;\; - \;||\overrightarrow F |{|_2}\cos \left( {\frac{A}{2}} \right) < 0} \end{array}} \right.$

(1)

当J(s_i,J_i,o_j)=1时,充电器s_i的充电功率为

${P_r}(d({s_i},{o_j})) = \left\{ {\begin{array}{*{20}{l}} {\frac{\alpha }{{{{(d({s_i},{o_j}) + \beta )}^2}}},{\rm{ }}d \le D}\\ {0,{\rm{ }}d > D} \end{array}} \right.$

(2)

其中,$\alpha = \frac{{{G_s}{G_r}\eta {P_0}}}{{{L_p}}}{\left( {\frac{\lambda }{{4\pi }}} \right)^2},$P₀为充电器功率,G_s为充电器天线增益,G_r为传感器天线增益,L_p为极化损失,λ为波长, η为整流器效益;β为调节短距离传输情况下,Friis自由空间方程的补偿参数^[16].$d\left( {{s_i},{o_j}} \right)$代表充电器s_i与传感器o_j的距离.当J(s_i,$\vartheta $_i,o_j)=0时,充电功率为0.即,传感器o_j接收的充电器s_i充电功率可用J(s_i,$\vartheta $_i,o_j)×P_r(d(s_i,o_j))表示.

当一个传感器o_i被多个有向充电器覆盖时,其接收到的总功率为各个有向充电器充电功率之和.文献^[16]通过现场实验对此假设进行了验证,但其使用的是全向充电器.为此,本文通过实验对有向充电器这一假设进行验证,在多次测量中发现,其实际值与理论值的误差不超过7.5%,具体可参考文献^[27].因此,传感器o_i接收到的总功率可以表示为

${P_r}(i) = \sum\nolimits_{j \in M} {J({s_j},{\vartheta _j},{o_i}){P_r}(d({s_j},{o_i}))} .$

为方便起见,将本文中用到的所有符号列在表 1中.

2.3 充电效用模型

目前为止,并未比较通用的充电效用模型.为此,本文采用如下简单的充电效用模型:

$U({P_r}(i)) = \left\{ {\begin{array}{*{20}{l}} {{c_p} \cdot {P_r}(i),{\rm{ }}{P_r}(i) \le {P_w}}\\ {{c_p} \cdot {P_w},{\rm{ }}{P_r}(i) > {P_w}} \end{array}} \right.$

(3)

其中,c_p和P_w为预先设置的常数.由公式(3)可见:充电效用在接收总功率P_r(i)未达到预设的某个阈值P_w时正比于P_r(i);而在P_r(i)超过阈值P_w之后,则保持为常数.该设定与许多实际应用相吻合.例如,现实中传感器经常要求接收的充电功率尽可能地达到其正常工作所需功率,这样才能保障其持久的工作^{[12, 16]};但当接收功率超过其工作功率时,多余的能量将无法存储而浪费掉,因此,充电效用不再增加.此外,还有一些应用要求在某个时间段内将传感器充满所需的能量^[13],这可等价地将这段时间内所需的平均充电功率视为阈值P_w.

不失一般性,本文假设所有传感器具有相同的充电效用模型,即,参数c_p和P_w具有相同的数值.值得强调的是,本文所有的理论分析和结果都能直接推广到传感器充电效用模型参数不同的情况.

2.4 问题定义

在给出上述模型之后,本节给出问题的形式化定义.本文研究的问题是如何在给定二维平面Ω上布置M个有向充电器,以最大化网络的整体充电效用.由公式(1)~公式(3),有向充电器的布置问题可以形式化为

(P1):

$\left\{ \begin{array}{l} \begin{array}{*{20}{l}} {\max {\rm{ }}\sum\nolimits_{i \in N} {U({P_r}(i))} }\\ {{\rm{s}}{\rm{.t}}{\rm{. }}{P_r}(i) = \sum\nolimits_{j \in M} {J({s_j},{\vartheta _j},{o_i}){P_r}(d({s_j},{o_i}))} } \end{array}\\ {\rm{ }}({x_j},{y_j}) \in \Omega ,\;0^\circ \le {\vartheta _j} \le 360^\circ ,j \in M \end{array} \right.$

(4)

其中,(x_j,y_j)为充电器s_j的坐标,θ_j为充电器朝向.

虽然上述有向充电器布置问题形式上非常简单,实际上却具有相当大的挑战性:首先是因为其目标函数是非线性的;其次是由于有向充电器的位置和朝向的解空间是连续的,因此有无限多种可能的组合.

下面的定理阐述了有向充电器布置问题的复杂度.

定理2.1. 有向充电器布置问题(P1)是NP难问题.

为了节省篇幅,这里略去详细证明过程,仅阐述其大概思路.因为有向充电器布置问题(P1)的约束为非线性约束,所以它属于非线性规划问题(non-linear program).而文献^[28]指出了通常非线性规划问题是NP难问题,可由此规约得出有向充电器布置问题也是NP难的.

3 近似算法

如之前章节所述,本文需要同时选取和确定多个充电器的位置和朝向来最大化充电效用.这项工作非常具有挑战性:一是因为充电器候选位置和朝向有无限多种选择;二是由于传感器的充电效用是由覆盖它的多个充电器共同决定的,所以各个充电器的位置和朝向的选择具有相当的关联性.

本节提出了一种近似算法,且其近似比达到(1-1/e)/(1+ε).算法的核心步骤分为3步:首先,将平面区域离散化为多个子区域,在子区域内,近似认为充电器的充电功率为某一常数值;其次,通过对各个子区域内部点进行分析,找出覆盖支配集(dominant coverage set,简称DCS,具体定义参考第3.2节);最后,利用问题的子模性,设计一种能达到上述近似比的贪心算法.

3.1 平面区域离散化

考虑到平面上充电器候选点的个数为无限多个,无法进行有效处理,本节利用类似于文献^[29]中提出的方法,将平面区域离散化为有限个子区域,从而将无限多个候选点降为有限多个,以方便后续处理.平面区域离散化的目标是:保证离散化后的各个子区域内的接收功率可以近似为常数值,且近似误差不大于给定的常数ε.

首先需要对充电模型中的接收功率对距离离散化.具体而言,任意给定某个常数ε,按L(1),L(2),…,L(K)划分距离,并对接收功率作如下近似:

${\widetilde P_r}(d) = \left\{ {\begin{array}{*{20}{l}} {{P_r}(L(1)),{\rm{ }}0 \le d \le L(1)}\\ {{P_r}(L(k)),{\rm{ }}L(k - 1) \le d \le L(k)\;(k = 2,...,K)}\\ {0,{\rm{ }}d > L(n)} \end{array}} \right.$

(5)

并且,

$\frac{{{P_r}(L(K - 1))}}{{{P_r}(L(K))}} \le 1 + \varepsilon ,\frac{{{P_r}(L(k - 1))}}{{{P_r}(L(k))}} = 1 + \varepsilon (k = 2,...,K)$

(6)

因此即有:

$\frac{{{P_r}(d)}}{{{{\widetilde P}_r}(d)}} \le 1 + \varepsilon (d \le D)$

(7)

换言之,与之前给出的充电模型相比,近似功率将[L(k-1),L(k)]区间内的功率均近似成为P_r(L(k))(对区间[0, L(1)],功率近似为P_r(L(1)));更重要的是,在各个区间内最大近似误差都不会大于ε.图 3给出了功率近似的一个示例.原来的代表接收功率的曲线被图中分段的虚线所替代,对应地,充电器的覆盖区域被划分为图中所示的3个子区域.在每个子区域,接收功率均被视为常数值.显而易见,按这种方式划分的充电区域个数为

$K = \left\lceil {\frac{{\ln ({P_r}(0)/{P_r}(D))}}{{\ln (1 + \varepsilon )}}} \right\rceil $

(8)

接下来考察接收功率离散化后对充电器布置问题的影响.

如图 3所示,以每一个传感器为中心,以L(1),L(2),…,L(K)为半径划分同心圆.为方便起见,用L⁽ⁱ⁾(k)标记传感器i的半径为L(k)的同心圆.这样划分同心圆的依据在于:在每一个相邻同心圆,如L⁽ⁱ⁾(k-1)和L⁽ⁱ⁾(k),构成的圆环内任意一点处,如果某个充电器设置的旋转角度正好覆盖传感器i,则传感器i接收到的该充电器的功率可近似认为是常数P_r(L(k)).

通过划分同心圆,整个平面区域被离散化为Z个子区域.以图 4为例,整个平面区域被6个同心圆划分为16个子区域(包括最外侧接收功率为0的子区域).在某个子区域内的任意位置,充电器对各个传感器的充电功率均可认为不变(前提是该传感器被充电器所覆盖).如在子区域F_i内任意一点,传感器1~传感器3接收到的功率均可近似为P_r(L(2));而在子区域F_j内,传感器2、传感器3接收到的功率仍为P_r(L(2)),而传感器1接收到的功率则为0.

在经过平面离散化之后,各个传感器的接收功率,即${P_r}(i) = \sum\nolimits_{j \in M} {J({s_j},{\vartheta _j},{o_i}){P_r}(d({s_j},{o_i}))} ,$可近似为

${\widetilde P_r}(i) = \sum\nolimits_{j \in M} {J({s_j},{\vartheta _j},{o_i}){{\widetilde P}_r}(d({s_j},{o_i}))}$

(9)

由公式(7)可知,其近似误差满足:

$\frac{{{P_r}(i)}}{{{{\widetilde P}_r}(i)}} = \frac{{\sum\nolimits_{j \in M} {J({s_j},{\vartheta _j},{o_i}){P_r}(d({s_j},{o_i}))} }}{{\sum\nolimits_{j \in M} {J({s_j},{\vartheta _j},{o_i}){{\widetilde P}_r}(d({s_j},{o_i}))} }} \le 1 + \varepsilon $

(10)

接下来分析子区域的数目.显然,平面中所有同心圆的个数为NK,而由公式(8)可推出K=O(ε^-1).另一方面,由文献^[30]的结论可知,平面中由NK个圆分割成的子区域个数Z满足:

Z≤(NK)2-NK+2

(11)

因此有:

Z=O(N2ε-2)

(12)

通过上述处理,充电器布置点由无限多个减少为有限多个.然而,由于充电器在某一点处可以任意选择朝向(0°~360°),而朝向不同会导致其覆盖传感器的集合也不同,从而对最终充电整体效用造成影响.在下一节中,会讨论如何处理这一问题.

值得强调的是,本文采用同心圆对区域进行离散化,而非在以往文献中比较常见的网格离散化,这是因为前者可以保证区域离散化之后在各个子区域内传感器接收功率的近似误差,如公式(10)所示,而网格离散化则不可能保证近似误差.此外,文献^{[17, 18, 20, 21, 22]}虽然使用了网格离散化,但却人为限制了充电器或传感器只能布置在格点上,这使得它们与本文提出的一般布置方法有本质的区别,实际应用也受到限制.

3.2 覆盖支配集抽取

上节对平面离散化处理后得到有限多个子区域,本节讨论在得到的各个子区域中如何进一步得到所有可能的充电器覆盖的极大的传感器集合(在后文中定义为覆盖支配集).

首先定义如下两个概念:

定义3.1. 给定充电器覆盖的传感器集合O_i和O_j,如果O_i⊂O_j,则称集合O_j支配(dominate)集合O_i.

定义3.2. 给定某个子区域及其内充电器覆盖的传感器集合O_i,如果在该子区域内不存在任何其他覆盖传感器集合支配O_i,则称集合O_j为覆盖支配集(coverage dominant set,简称CDS).

显而易见,在给定某个子区域内,只需求得所有的覆盖支配集即可,而无需计算所有可能的覆盖集合.这是因为根据平面离散化之后的结果,传感器被某个子区域内的任意位置充电器覆盖时其接收功率都相同,所以选择覆盖支配集一定优于选择其支配的任何可能集合.

作为后续讨论的基础,首先考察当充电器位于某个固定点时,通过选取不同朝向所能覆盖的所有覆盖支配集CDS.正式地,将覆盖支配集求取过程称为覆盖支配集的抽取.固定点时覆盖支配集的抽取算法如算法1所示.注意,这里输入参数中的传感器集合并不包括所有的传感器O,而可能只是O的一个子集O_i.O_i仅是充电器在位于该子区域内,通过调整朝向所有可能覆盖到的传感器节点的集合.

算法1. 输入参数为充电器及其所有可能覆盖的传感器集合O_i的位置;

输出参数为所有覆盖支配集CDS.

Step 1. 选定某一参考角度,计算所有传感器相对于充电器的夹角θ_j(0°≤θ_j≤360°);

Step 2. 将所有传感器按夹角从小到大排序.为方便起见,不妨设排序后夹角为θ₁≤θ₂≤…≤θ_p,其对应传感器为o₁,o₂,…,o_p;

Step 3. 令O_c记录当前覆盖集合,θ_min,θ_max分别记录当前覆盖集合O_c中传感器相对于充电器的最小和最大夹角;初始化令θ_min=θ_max=θ₁;O_c={o₁};

Step 4. j=2;

Step 5. While充电器能覆盖θ_min到角度θ_j的范围,即θ_j-θ_min≤A;

Step 6. θ_max=θ_j;

Step 7. 添加o_j到O_c;

Step 8. j=(j+1) mod p;

Step 9. EndWhile

Step 10. 添加当前覆盖集合O_c到覆盖支配集记录;

Step 11. θ_max=θ_j,添加o_j到当前覆盖集合O_c;

Step 12. While充电器不能覆盖θ_min到角度θ_max范围,即θ_max-θ_min>A;

Step 13. 从O_c中去除夹角最小的传感器,并更新θ_min为O_c集合中传感器具有的最小夹角;

Step 14. 如果θ_min=θ₁,算法终止;

Step 15. EndWhile

Step 16. GotoStep 5;

算法1本质上是一种贪心算法,算法的执行过程可以理解为不断旋转充电器的朝向来考察覆盖传感器集合的变化情况.算法的Step5~Step 9是在旋转过程中尽可能地添加新的传感器,直到存在有已覆盖的传感器不能被覆盖为止.记录临界时的覆盖传感器集合为覆盖支配集.Step 12~Step 15为依次去除当前覆盖集合中最小夹角的传感器,直到当前集合能再次被覆盖为止.算法在遇到记录的最小夹角等于初始化的最小夹角时终止,此时意味着充电器正好已经旋转了一周.

图 5展示了算法1执行的一个例子.如图 5(a)所示:算法从传感器o₁开始,依次添加o₂和o₃;当添加o₄时发现超出覆盖范围,于是记录当前覆盖集合{o₁,o₂,o₃}为覆盖支配集.之后,算法从当前覆盖集合中去除{o₁,o₂}以使得较大夹角的传感器o₄能被覆盖,如图 5(b)所示.接下来添加o₅时又发生不能覆盖的情况,记录{o₃,o₄}为覆盖支配集;添加o₅后去除传感器o₃.以此类推,算法相继确定集合{o₄,o₅},{o₆,o₁}亦为覆盖支配集.在旋转一周后终止程序.最终抽取的所有覆盖支配集为{o₁,o₂,o₃},{o₃,o₄},{o₄,o₅}和{o₆,o₁}.

下面考察当充电器的可选位置为一子区域时,如何抽取覆盖支配集.一个重要的观察是:尽管在给定区域内,充电器的可选位置和朝向的组合有无限多种,但其所有可能的覆盖传感器的组合是有限的,这意味着多种组合是完全等价的.对于所有等价的位置和朝向组合,只需挑选其中一个分析即可.更进一步地,如果某种位置和朝向组合覆盖的传感器集合支配现有的位置和朝向组合覆盖的传感器集合,则只需考虑前者即可.因此,接下来的任务即是如何挑出这些组合.

为了阐述方便,用两元组<p,θ>记录充电器的位置和朝向的组合,并定义如下概念:

定义3.3. 给定充电器位置和朝向组合<p₁,θ₁>和<p₂,θ₂>,如果两种组合覆盖的传感器集合O₁和O₂相同,则称<p₁,θ₁>和<p₂,θ₂>等价.

定义3.4. 给定充电器位置和朝向组合<p₁,θ₁>和<p₂,θ₂>及其覆盖的传感器集合O₁和O₂,如果O₁支配O₂,则称<p₁,θ₁>支配<p₂,θ₂>.

接下来定义如下3种位置和朝向的变换:

定义3.5(投影变换,projection). 给定充电器位置和朝向组合<p,θ>,投影变换是将充电器从位置p沿参考线反方向移动到边界某点p'处,而朝向不变,从而组合变为<p',θ>.

定义3.6(旋转变换,rotation). 给定充电器位置和朝向组合<p,θ>,旋转变换是将充电器朝向旋转至一个新的角度q ',而位置不变,从而组合变为<p,θ '>.

定义3.7(平移变换,translation). 给定充电器位置和朝向组合<p,θ>,平移变换是将充电器从位置p移动到另一点p'处,而朝向不变,从而组合变为<p',θ>.

显然,投影变换是平移变换的一种特例.

图 6展示了3种变换的示例.

对于投影变换有如下引理:

引理3.1. 设充电器位置和朝向组合<p,θ>经过投影变换后为<p',θ>,则有<p',θ>支配<p,θ>.

证明:首先需要指出的是:假设充电器位置和朝向组合<p,θ>覆盖传感器集合O₁,则对O₁内任意一个传感器而言,点p所在的子区域必位于以该传感器为中心的两个相邻同心圆的区域内.这是因为平面上所有的子区域都是由各个传感器对应的同心圆簇划分出来的.另一方面,若点p所在的子区域位于某个传感器D距离之外,则<p,θ>不可能覆盖该传感器,它也不在集合O₁内.

由于几何对称性,传感器集合O₁也必位于以点p为圆心的两个相邻同心圆的区域内.因此,无论充电器位置点p在子区域内如何移动,只要保证其朝向(可以想象成半径为无穷大的扇形区域)覆盖传感器集合O₁内的传感器,充电器也必覆盖该传感器.显而易见,在经过投影变换之后,<p',θ>的朝向可以保证一定覆盖之前<p,θ>朝向覆盖的所有传感器集合O₁.此外,<p',θ>朝向还有可能覆盖<p',θ>朝向所不能覆盖的新的传感器,如图 6(a)所示,在经过投影变换后,位于新位置的充电器不仅能够覆盖之前位置处所能覆盖的传感器o₁和o₂,而且还覆盖了新的传感器o₃.因此,<p',θ>覆盖的传感器集合${O'_1}$必包含O₁,即有<p',θ>支配<p,θ>.证毕. □

由引理3.1能马上推出如下结论:

推论3.1. 选取子区域边界作为充电器候选位置点可以抽取出所有该区域的覆盖支配集.

推论3.1说明子区域的内部无需考虑,因此接下来将重点分析区域边界的位置和朝向组合.

给出任意一个子区域边界的位置与朝向组合<p,θ>,可作如下调整:

首先固定位置p,做旋转变换(逆时钟旋转)调整组合为<p,θ'>,使得至少有一个传感器,不妨假设为o₁,正好落在参考线顺时针方向的半径边界上.如图 6(b)所示,经过旋转后覆盖区域边界正好经过传感器o₁.显然,变换后的组合<p,θ '>支配原始的组合<p,θ>.

接下来令充电器在子区域边界上移动并可调整朝向,即令<p,θ '>不断地做平移变换和旋转变换,但须保证如下两个条件:一是调整后的位置与朝向组合<p',θ²>必须等价于或支配组合<p,θ'>;二是覆盖区域参考线顺时针方向的半径边界必须经过o₁.换言之,在充电器调整过程中,之前<p,θ'>覆盖的任何传感器均不能“跑出”覆盖区域,并且可以等价认为调整过程中覆盖区域的顺时针方向半径边界绕“轴”o₁旋转.可以推测,充电器调整过程中只会碰到如图 7所示的3种可能的结果.

(a)在边界某点p'处有<p,θ '>覆盖的某个传感器(图 7(a)中为o₂)与o₁均位于顺时钟方向半径边界上;

(b)在边界某点p'处有<p,θ '>覆盖的某个传感器(图 7(b)中为o₃)位于逆时针方向半径边界上;

(c)遍历子区域边界不存在图 7(a)或图 7(b)所示的情况(如图 7(c)所示).

本质上来说,图 7(a)和图 7(b)刻画的是两种临界情况,即:在调整过程中,即将有<p,θ'>覆盖的传感器“跑出”覆盖区域.而图 7(c)描述的则是另一种情形,即:当充电器位于边界上任何一点p'时,<p',θ²>均等价于或支配组合<p,θ '>.

利用临界情况时的特征,即可逆向推断出覆盖支配集.注意,这种思路与算法1中通过考察有传感器不能被覆盖的临界状态来确定覆盖支配集的思路是一致的.

算法2描述了覆盖支配集抽取细节,图 8展示了其重要步骤.

算法2. 输入参数为充电器所在子区域边界,所有可能覆盖的传感器集合O_i位置;

输出参数为所有覆盖支配集CDS.

Step 1. Forall 传感器集合O_i中的传感器对,如o₁和o₂;

Step 2. 连接o₁和o₂并延长与区域边界相交于若干个交点;依次取各个交点(如图 8(a)中交点p'和p²)所示作为充电器位置;o₁和o₂连线方向作为覆盖区域顺时针方向的半径边界,从而确定充电器朝向(如图 8(a)所示),计算当前位置和朝向组合覆盖的传感器集合,添加到候选覆盖支配集中;

Step 3. 计算与o₁,o₂夹角为固定值A的点的轨迹(如图 8(b)中所示的两端圆弧)与区域边界的所有交点;依次以每个交点为当前位置、o₁,o₂与当前位置连线作为当前覆盖区域的半径边界,从而确定充电器朝向,计算所能覆盖的传感器集合,添加到候选覆盖支配集中;

Step 4. EndFor

Step 5. 任取区域边界上一点p_ref作为固定点位置,执行算法1获得p_ref处所有可能的覆盖支配集,添加到候选覆盖支配集中(如图 8(c)所示).

下面对算法2进行解释.算法中:Step 2对应充电器调整过程中碰到的可能情况(a),另外注意需要分析所有交点处的位置和朝向组合,虽然图 8(a)中交点p'';对应的<p'',θ²>支配更近交点p'对应的<p',θ''>,但此情况仅在A≤180°时才成立;Step 3对应可能情况(b);Step 5则对应可能情况(c),注意,此时只需对任选的一个点p_ref进行算法1中的分析,即可获得满足情况(c)的所有可能的覆盖支配集.最后,即获得了所有的覆盖支配集和其对应的充电器位置和朝向组合,设其为Γ.

对算法2及其输出结果Γ有如下重要的定理:

定理1. 算法2的时间复杂度为O(n⁴),输出的覆盖支配集个数为O(n³),这里,n为位于子区域内充电器所能覆盖到的传感器个数,即|O_i|;子区域内任意位置和朝向组合都等价于算法2输出结果G内的某一组合,或被其所支配.

证明:显然,算法2中For循环执行次数为O(n²).因为子区域内充电器所能覆盖的传感器个数为n,所以组成子区域边界的圆弧个数最多为2n.因此,Step 2中任意一对传感器连线与子区域交点个数最多也不超过2x2n= 4n;类似地,Step3中任意一对传感器对应的两段圆弧与子区域交点个数最多不超过2x2x2n=8n.而对Step 2或Step3,给定交点和朝向来确定有哪些传感器被覆盖均需要O(n)步操作.综上,算法2中For循环时间复杂度为O(n²)x(4n+8n)xO(n)=O(n⁴),而获得的覆盖支配集个数为O(n²)x(4n+8n)=O(n³).另外,Step5的时间复杂度为O(n),获得覆盖支配集个数为O(n),相比之下可以忽略.因此,算法2整体时间复杂度为O(n⁴),抽取的覆盖支配集个数为O(n³).

另外,对子区域内任一位置和朝向组合,都可利用之前提到的调整方法调整为3种结果之一.由引理3.1可知,将区域内部的任何一点做投影变换到边界上时,获得新组合等价于或支配原有组合;之后在边界上做第1步旋转变换后,结果同样如此.接下来做的一系列平移变换和旋转变换也同样保证了调整后的新组合必等价于或支配调整前的组合.这样可以推出经过上述调整方法得到的新组合必等价于或支配最原始的组合.另一方面,算法2的输出集合Γ包含了所有可能的经过调整后的3种结果,因此子区域内任意位置和朝向组合都等价于算法2输出结果Γ内的某一组合,或被其所支配.证毕. □

考虑到得到的候选覆盖支配集Γ中可能存在被支配的集合,可以对Γ作进一步的检查以去除这些集合.但这一步骤并不是本文考虑的重点,限于篇幅不作过多介绍.

3.3 问题重构和近似算法

本节介绍如何在通过离散化平面区域和对各个子区域进行覆盖支配集抽取后获得的所有位置和朝向组合中,继续遴选组合来布置充电器,以最大化网络整体充电效用.具体而言,本节首先对问题进行了重构,然后证明了重构问题的子模性,并且提出了一种具有(1-1/e)/(1+ε)近似比的算法.

在经过抽取覆盖支配集之后,可获得位置和朝向组合的集合Γ.对每种组合,都可计算出在某个充电器按此位置和朝向布置时,每个传感器所接收到的功率.注意,此功率值是经过第3.1节离散化之后的近似值.不妨设第i种位置和朝向的组合对应的传感器j接收功率为${\widetilde P_{ji}},$此值可预先计算获得.令x_i为指示是否选择第i种组合的二进制变量(值为1时选中,为0则不选).于是有向充电器布置问题(P1)可重构为

(P2):

$\left\{ {\begin{array}{*{20}{l}} {\max {\rm{ }}\sum\nolimits_{i \in N} {U({{\widetilde P}_r}(i))} }\\ \begin{array}{l} {\rm{s}}{\rm{.t}}{\rm{. }}{\widetilde P_r}(i) = \sum\nolimits_{j \in M} {{x_j}{{\widetilde P}_{ji}}} ,j \in \;|\Gamma |\\ {\rm{ }}{x_j} \in \{ 0,1\} ,j \in \;|\Gamma | \end{array} \end{array}} \right.$

(13)

为了解决重构后的问题,首先给出一些与问题相关的定义.

定义3.8^[31]. 令S为有限集合,当且仅当分别满足下述条件时,实函数f:2^S↦R是归一化、非单调递减的子模(也称其为边际收益递减)函数:

(1)f(∅)=0;

(2)对任意A⊆ B⊆ S,有f(A)≤f(B),或者等价地,对任意A⊆ S和e∈S\A,有f(A∪{e})-f(A)≥0;

(3)对任意A⊆ B⊆ S且e∈S\B,有f(A∪{e})-f(A)≥f(B∪{e})-f(B).

定义3.9^[31]. 拟阵M是元组M=(S,L),其中,S是有限集合,L⊆ 2^S是独立集的集合,则有:

(1)∅∈L;

(2)若X⊆ Y∈L,则X∈L;

(3)如果X,Y∈L,且|X|<|Y|,那么对任意y∈Y\X,有X∪{y}∈L.

定义3.10^[31]. 给定有限集合E,正整数k,均匀拟阵M=(S,L)且L={X⊆ E:|X∩E|≤k}.根据上述定义,可以进一步将重构后的问题(P2)写成如下形式:

(P3):

$\left\{ {\begin{array}{*{20}{l}} {\max {\rm{ }}f(X) = \sum\nolimits_{i \in N} {U({{\widetilde P}_r}(i))} = \sum\nolimits_{i \in N} {U\left( {\sum\nolimits_{j \in X} {{{\widetilde P}_{ji}}} } \right)} }\\ \begin{array}{l} {\rm{s}}{\rm{.t}}{\rm{. }}X \in L,\\ {\rm{ }}L = \{ X \subseteq \Gamma :\;|X \cap \Gamma | \le M\} \end{array} \end{array}} \right.$

(14)

引理3.2. 优化问题(P3)中的目标函数f(X)是单调子模函数,约束为均匀拟阵约束.

证明:根据上面子模函数的定义,只需检查子模函数的3个条件是否对f(X)成立.

·首先,当布置的充电器个数为0时,所有传感器接收到的充电功率都为0,即有f(∅)=0,子模函数的第1个条件成立;

·其次验证f(X)的单调性:

假设有集合A⊆ Γ和元素e∈Γ\A,即,A为选取的某些位置和朝向组合的集合,且e为不属于A的一种新

组合,则有:

$\begin{array}{l} f(A \cup \{ e\} ) - f(A) = \sum\nolimits_{i \in N} {U\left( {\sum\nolimits_{j \in A \cup \{ e\} } {{{\widetilde P}_{ji}}} } \right)} - \sum\nolimits_{i \in N} {U\left( {\sum\nolimits_{j \in A} {{{\widetilde P}_{ji}}} } \right)} \\ {\rm{ }} = \sum\nolimits_{i \in N} {\left( {U\left( {\sum\nolimits_{j \in A \cup \{ e\} } {{{\widetilde P}_{ji}}} } \right) - U\left( {\sum\nolimits_{j \in A} {{{\widetilde P}_{ji}}} } \right)} \right)} \ge 0 \end{array}$

(15)

上式中,最后一项不等式成立是因为充电效用函数U(·)为非单调递减函数,且

$\sum\nolimits_{j \in A \cup \{ e\} } {{{\widetilde P}_{ji}}} \ge \sum\nolimits_{j \in A} {{{\widetilde P}_{ji}}} ({\widetilde P_{ji}} \ge 0,j \subseteq \Gamma ).$

·最后验证f(X)的边际收益递减性质:

假设有集合A⊆ B⊆ Γ和元素e∈Γ\B,则有:

$\begin{array}{l} (f(A \cup \{ e\} ) - f(A)) - (f(B \cup \{ e\} ) - f(B))\\ = \sum\nolimits_{i \in N} {\left( {\left( {U\left( {\sum\nolimits_{j \in A \cup \{ e\} } {{{\widetilde P}_{ji}}} } \right) - U\left( {\sum\nolimits_{j \in A} {{{\widetilde P}_{ji}}} } \right)} \right) - \left( {U\left( {\sum\nolimits_{j \in B \cup \{ e\} } {{{\widetilde P}_{ji}}} } \right) - U\left( {\sum\nolimits_{j \in B} {{{\widetilde P}_{ji}}} } \right)} \right)} \right)} \\ \ge 0 \end{array}$

(16)

最后一项不等式成立是因为充电效用函数U(·)为非单调递减函数,且

$\sum\nolimits_{j \in A \cup \{ e\} } {{{\widetilde P}_{ji}}} - \sum\nolimits_{j \in A} {{{\widetilde P}_{ji}}} = \sum\nolimits_{j \in B \cup \{ e\} } {{{\widetilde P}_{ji}}} - \sum\nolimits_{j \in B} {{{\widetilde P}_{ji}}} = {\widetilde P_{ei}}$

(17)

其中,${\widetilde P_{ei}}$为组合对应的传感器j接收功率.

综上所述,可知f(X)为单调子模函数.

此外,根据上述定义,(P3)的约束显然为均匀拟阵约束.证毕. □

通常来说,如果一个优化问题的目标函数是子模的,则其对应的贪婪算法往往能达到较好的且有理论保障的性能.具体来说,此贪婪算法的近似比往往依赖于子模函数约束的类型,例如,根据文献^[31],受限于均匀拟阵约束的单调子模函数最大化问题的贪心算法近似比为1-1/e.在定理2的证明中可以看到,证明(P3)为受均匀拟阵约束的单调子模函数最大化问题将有助于推导全局算法的近似比.

接下来,本节提出了一种贪心算法来选取充电器位置与朝向组合.算法3中给出了该算法的细节.可以看到:该算法中的每一步都会为当前集合X加上一个使得增量值最大的元素e^*,直到|X|=M,即,M个充电器全部布置完为止.

算法3. 输入参数为充电器数量M,候选充电器位置与朝向组合集合Γ,优化目标函数f(X);输出参数为位置和朝向组合的集合X.

Step 1. X=∅;

Step 2. While|X|≤M;

Step 3. e^*=argmax_e∈Γ\Xf(X∪{e})-f(X);

Step 4. X=X∪{e^*};

Step 5. EndWhile

最后,将求解充电器布置位置和朝向的算法归纳如下.

算法4. 输入参数为充电器数量M,传感器集合O位置,充电模型和效用模型参数α,β,A,D,c_p,P_w;输出参数为各个充电器的位置和朝向.

Step 1. 用第3.1节介绍的方法离散化平面区域;

Step 2. 对每个离散化后得到的子区域执行算法2,获得候选充电器位置与朝向组合集合Γ;

Step 3. 执行算法3获得M个位置和朝向组合,此即为解.

此算法也简称为CDG(charger deployment-greedy)算法.接下来分析上述算法的性能.

定理2. CDG算法的近似比为(1-1/e)/(1+ε),且其时间复杂度为O(M²N⁶ε^-2).

证明:不妨令${\widetilde P_r}(i)$为按本文算法输出的结果布置充电器时,传感器o_i总接收功率的近似值,而P_r(i)为其对应的实际值;$P_r^{OPT}(i)$为原始问题(P1)最优解对应的o_i总接收功率,$\widetilde P_r^{OPT}(i)$为其近似值;$\widetilde P_r^*(i)$为重构问题(P2)(或(P3))最优解对应的o_i总接收功率的近似值,而其实际值为$P_r^*(i).$

因为${P_r}(i) \ge {\widetilde P_r}(i),$故有:

$\sum\nolimits_{i \in N} {U({P_r}(i))} \ge \sum\nolimits_{i \in N} {U({{\widetilde P}_r}(i))} $

(18)

根据文献^[31],受限于均匀拟阵约束的单调子模函数最大化问题的贪心算法近似比为1-1/e.另一方面,由引理3.2可知,问题(P2)最终可以建模为受限于剖分拟阵约束的子模函数最大化问题.因此,算法3的近似比为1-1/e,即有:

$\sum\nolimits_{i \in N} {U({{\widetilde P}_r}(i))} \ge (1 - 1/e)\sum\nolimits_{i \in N} {U(\widetilde P_r^*(i))} \ge (1 - 1/e)\sum\nolimits_{i \in N} {U(\widetilde P_r^{OPT}(i))} $

(19)

注意,最后一个不等式成立是因为$\widetilde P_r^*(i)$为重构问题(P2)的最优解.

由公式(10),有$\widetilde P_r^{OPT}(i) \ge \frac{1}{{1 + \varepsilon }}P_r^{OPT}(i).$此外,由充电效用函数性质易得:

$U\left( {\frac{1}{{1 + \varepsilon }}P_r^{OPT}(i)} \right) \ge \frac{1}{{1 + \varepsilon }}U(P_r^{OPT}(i))$

(20)

因此即有:

$\sum\nolimits_{i \in N} {U(\widetilde P_r^{OPT}(i))} \ge \sum\nolimits_{i \in N} {U\left( {\frac{1}{{1 + \varepsilon }}P_r^{OPT}(i)} \right)} \ge \frac{1}{{1 + \varepsilon }}\sum\nolimits_{i \in N} {U(P_r^{OPT}(i))} $

(21)

综合公式(18)、公式(19)、公式(21)即有:

$\sum\nolimits_{i \in N} {U({P_r}(i))} \ge \frac{{1 - 1/e}}{{1 + \varepsilon }}\sum\nolimits_{i \in N} {U(P_r^{OPT}(i))} $

(22)

故而,CDG算法的近似比为(1-1/e)/(1+ε).

下面分析CDG算法的时间复杂度.

CDG算法第1步可以通过考虑每次添加一个圆后,计算新圆与现有圆的交点及新切分的区域来实现,其时间复杂度为O(N²).由公式(12)可知:经过CDG算法的Step 1平面离散化之后,得到的子区域个数为Z=O(N²ε^-2).由定理1,每个子区域抽取覆盖支配集的时间复杂度为O(n⁴)≤O(N⁴).因此,Step 2需时Z=O(N⁶ε^-2).CDG算法的第3步就是执行算法3.而算法3的While循环共有M次,每次需要对所有属于Γ\X的位置与朝向组合计算f(X∪{e})和f(X)(Step 3),每次计算需时O(MN).另外,由定理1可知,每个子区域抽取的覆盖支配集个数为O(n³),因此,所有子区域抽取的覆盖支配集个数|Γ|=O(n³×Z)≤O(N⁵ε^-2),进一步有|Γ\X|≤O(N⁵ε^-2).算法3所需总时间为

O(M×N5ε-2×MN)=O(M2N6ε-2).

综上所述可知,CDG算法的时间复杂度为O(M²N⁶ε^-2).证毕. □

值得一提的是,本文提出的CDG算法由于其目标是最大化网络的整体充电效用,在Step 3执行算法3贪婪选取覆盖支配集的过程中,可能会出现有某些节点不会被覆盖的情况.例如,有多个节点虽已被充电器覆盖,但充电功率尚未达到阈值P_w,而同时有单个节点从未被覆盖到,此时,算法3会倾向于选择继续覆盖前面这些节点以最大化充电效用的增量.这样,未被覆盖的单个节点无论初始时刻剩余能量有多大,最终都会耗尽存储的能量而死掉,导致传感器网络出现覆盖空洞.我们将在后续工作中对这种情况作更深入的探讨和分析.

4 仿真实验

本节通过仿真实验来验证提出算法的性能.具体而言,提出了两种随机算法与本文提出的算法进行比较,并且研究了这3种算法所能达到的充电效用随给定的平面区域离散化误差阈值ε、充电器数目M、有向充电器充电范围的角度A以及充电效用模型参数P_w的变化情况.

4.1 参数设置

在仿真中除了特别指出外,使用如下的默认参数设置:传感器和充电器所在区域范围为150mx150m,可充电传感器的数目N=100,可布置的无线充电器数目M=40(考虑充电器的价格因素,实际情况中布置的充电器密度可能相对较小).充电模型中的参数α=100,β=40,D=20,A=π/2.充电效用模型中的P_w=40mW,c_p=1/(NP_w).c_p的设置是为了将充电总效用归一化.另外,平面区域离散化的误差阈值设为ε=0.1.

4.2 基线算法

本文采用如下两种基线算法用于性能的比较:

·一是RPRO(randomposition and random orientation)算法,此算法将M个充电器随机布置到感兴趣的区域内,并随机地设置其朝向;

·二是RPDO(randomposition and discretized orientation)算法,此算法与RPRO算法的不同点在于:在随机布置完充电器之后,每个充电器的朝向都可以选择0,π/2,π和3π/2这4个角度,这样即可得到一共4M组充电器可能的布置位置和朝向,然后用类似于本文算法3的方法依次从4M个候选位置朝向组合中贪心挑选出M个组合,即,每一次挑选出来的组合均可使得整体充电效用的增量最大化.

RPDO的特点是充电器的朝向可以从离散化的候选角度中选取,这一设定类似于文献^{[32, 33, 34, 35, 36]}中的虚拟节点设定.显然,RPRO和RPDO本质上都是随机算法.在之后的所有实验中,RPRO和RPDO的每个数据点都代表了执行500次RPRO算法和RPDO算法之后得到的结果的平均值.

4.3 实验结果 4.3.1 算法结果示例

首先,图 9展示了3种算法得到的充电器布置结果的例子.

由图 9(a)可见,CDG算法得到的布置方案覆盖了所有的传感器,并且有很多传感器被多个充电器所覆盖,因此它们的充电效率得到进一步提高.CDG算法获得的整体充电效用为0.989 7.作为对比,图 9(b)和图 9(c)中,RPRO算法和RPDO算法对应的布置方案分别只能覆盖38个传感器和75个传感器,其整体充电效用分别为0.361 7,0.631 6.注意,这里RPDO算法的充电器候选位置与RPRO算法相同,但RPDO算法可以为每个充电器选择4个不同的朝向,因此其性能平均而言要优于RPRO算法.

4.3.2 误差阈值ε的影响

本节研究误差阈值ε对充电总效用的影响.假设ε在0.2~1.2之间发生变化,由图 10可见:RPRO算法和RPDO算法不受ε的影响,其值分别为0.113 1和0.246 8.注意,此值为执行500次RPRO算法和RPDO算法后得到的平均值.图 10还展示了CDG算法得到的近似的充电总效用值和真实的充电总效用值.由图 10可见:真实充电总效用值约为0.56,且总大于近似功率值,后者不超过0.5,这是由平面区域离散化时功率近似算法决定的.此外,充电总效用值并不一定随误差阈值ε的增大而减小.虽然ε的增大会导致离散化得到的子区域数目减少,从而也减少了CDG算法的候选覆盖集数目,但CDG算法的贪心本质不能保证得到最优解,因此可能导致从较少候选覆盖集中选取的集合优于从较多候选覆盖集中选取的集合.

4.3.3 充电器数目的影响

接下来分析充电器数目对充电总效用的影响.直觉上,充电器数目增加时会有更多的传感器被覆盖,因此,充电总效用必然会有所增加.图 11的结果很好地验证了这一点.

可以发现,3种算法得到的充电总效用总是随着充电器数目的增加而增大.此外,CDG算法总是优于RPRO算法和RPDO算法.当充电器数目从5~40变化时,CDG算法相对于RPRO算法的平均性能提升有324%,相对于RPDO算法的平均性能提升有83.3%.当充电器数目大于或等于30时,CDG算法得到的充电总效用等于1.而RPRO算法和RPDO算法从严格意义上来讲其充电总效用都只可能小于1,这是因为RPRO算法和RPDO算法本质上都是随机算法.对RPRO算法而言,由于其位置和朝向都是随机选取的,因此无论充电器的数目有多大,总可能会出现传感器不被充电器覆盖的情形;对RPDO算法而言,虽然其朝向是从0,π/2,π和3π/2这4个角度中选定的,但其位置仍然是随机选取的,这同样可能导致有传感器不会被覆盖到.综上所述,RPRO算法和RPDO算法的充电总效用总小于1.

4.3.4 有向充电器角度的影响

本节评估有向充电器角度A对充电总效用的影响.假设有向充电器角度A在45°~360°之间发生变化,由图 12可见:3种算法获得的充电总效用均随角度A的增大而增加,并且CDG算法均优于其他两种算法.具体而言,从平均意义上来说,CDG算法相对RPRO算法和RPDO算法有352.7%和137.5%的性能优势.另外,从图中还可以看到:RPRO算法和RPDO算法的差距随角度A的增大而不断减小,在A=360°时,两种算法达到相同效用值.这是因为,在角度A增大时,RPDO算法中每个位置处充电器4个朝向相应的覆盖传感器集合和充电效用的差别也随之减小;当A=360°时,4种朝向实际上是完全等价的,但是因为RPDO算法可选的布置方法仍为RPRO的4倍,即,在某个位置处可以布置1,2,3或4个充电器,因此RPDO算法的性能仍优于RPRO算法.

4.3.5 充电效用模型参数P_w的影响

接下来研究充电效用模型参数P_w对充电总效用的影响.显然,当P_w增大时,即便充电器对传感器的充电功率不变,其充电效用也会等价地减少.事实上,CDG算法和RPDO算法的充电器放置策略都会随P_w的增大而改变,因此,各个传感器的接收功率也会相应变化;相反,RPRO算法的充电器放置策略不受P_w改变的影响.如图 13所示,3种算法获得的充电总效用均随P_w的减小而下降,且CDG算法获得的效用平均比RPRO算法和RPDO算法高386.2%和136.3%.并且,CDG算法的性能变化显著,当P_w从0.0.1增至0.1时,其效用从0.7降至0.32,降幅达54.3%.作为对比,RPRO算法仅下降了20.2%.

5 结束语

本文首次基于实际测量数据对有向无线充电器的充电模型进行建模,并研究了二维平面上的一般布置问题,及如何有效地布置充电器并设置其朝向,使得网络整体的充电效用最大化.本文提出一系列创新的分析方法,包括平面区域离散化和覆盖支配集抽取,有效地降低了问题的复杂性,最后得到近似比为(1-1/e)/(1+ε)的高效近似算法——CDG算法.仿真实验结果验证了CDG算法的性能,并且展示了与其他两种随机算法相比,CDG算法有巨大的性能优势.

本文考虑的目标仅仅是最大化网络的整体充电效用.然而在实际的应用场景中,传感器通常被用来执行某项任务,如监测突发事件等,用户最终关心的可能是传感器网络执行该项任务的性能,而非具体的网络整体充电效用.基于这一现实考虑,在未来的工作中将研究传感器网络的充电功率与传感器网络执行任务性能之间的具体关系,并以此作为布置充电器的重要依据.另一方面,单纯考虑优化整体充电效用会导致有些传感器未被覆盖到,此时无论传感器初始时刻剩余能量有多少,终将会耗尽节点能量而死掉,导致传感器网络出现覆盖空洞.为了解决这一问题,我们也会在未来的工作中将传感器网络覆盖率纳入考虑范围,这样同时也可以保证对传感器充电的公平性.