随着我国无线通信行业的蓬勃发展，无线传感器网络被广泛用于改善基层医疗、环境卫生、公共交通等重要民生问题[1-2]．无线传感器网络利用固定位置的传感器为用户提供服务，其中每个传感器s可服务的区域是以其空间位置为中心、r(s)为半径的圆盘D(s，r(s))，此圆盘的半径与分配给传感器的能量密切相关且满足p(s)=r(s)α，其中α≥1为衰减因子．如果一个用户在传感器s的圆盘D(s，r(s))内，那么这个用户被视为被传感器s覆盖．因此，研究一种能够覆盖用户群体的传感器最小能量分配方案(最小圆盘覆盖问题)对降低无线传感器网络的运营成本具有重要意义．当α1时，最小圆盘覆盖问题是NP-难的[3]．Bilò等[4]给出了一个多项式时间近似方案(PTAS)．为保障大多数用户的利益，无线传感器网络没有必要全面覆盖所有用户，仅覆盖部分用户的最小圆盘部分覆盖问题[5]成为研究热点．利用原始对偶方法，Li等[6]设计了一个3α-近似算法，刘晓非等[7]设计了一个5⋅2α-近似算法，Dai等[8]设计了一个O(α)-近似算法．在现实中，每个用户的重要性可能不同，为了最大限度地保障重要用户的利益，通过定义每个用户的覆盖收益，带收益限制的最小圆盘覆盖问题受到广泛关注．此问题试图寻找一种最小能量分配方案，以便被覆盖的用户总收益至少为B，其中B为一个给定的常数．对于任意的ε0，Dai等[9]设计了一个4⋅3α-1+ε-近似算法．为了控制无线传感器网络的总运营成本，即可分配的总能量不超过某个上界，学者们研究带能量限制的最大圆盘覆盖问题．在平面上，给定包含n个用户的集合U，包含m个传感器的集合S，一个可分配能量的上界P∈R+，以及一个用户覆盖收益函数w:U→R+，能量受限的最大圆盘覆盖问题试图找到一种传感器能量分配方案p:S→R+，使得分配能量之和不超P，在满足该条件下覆盖用户总收益最大．假设圆盘的边界上至少有一个用户，每个传感器至多分配n个不同的能量，定义这些圆盘的集合为𝒟={D|p(D)≤P且D∈𝒟s,s∈S}，其中𝒟s={Ds0}⋃{Dsu|u∈U}，Dsu为以s为圆心且以s到u的欧式距离为半径的圆盘，Ds0为半径为0的圆盘．为了方便描述，针对任意一个圆盘D∈𝒟，使用c(D)，r(D)，p(D)和U(D)分别代表圆盘D的圆心、半径、需要分配的能量和可以覆盖的用户集合，不难得到p(D)=r(D)α．次模函数是一种具有边界效益递减性质的集合函数，对于任意两个集合𝒟',𝒟''∈𝒟，均有f(𝒟')+f(𝒟'')≥f(𝒟'⋃𝒟'')+f(𝒟'⋂𝒟'')成立．对于任意圆盘集合𝒟'⊆𝒟，定义其收益和分配能量分别为w(𝒟')=∑u:u∈𝒟'w(u)和p(𝒟')=∑s:s∈Smax{p(D)|c(D)=s}，可以证明w和p均为次模函数．因此，该问题是带次模背包限制的最大化次模函数问题的特例．对于该问题，Iyer和Bilmes[10]设计了一个1/n-近似算法，而Bian等[11]提出了一个进化算法，并证明在期望多项式时间内，其输出值至少为(1/2)(1-1/e)倍近似最优解目标函数值，其中近似最优解为背包限制稍小的该问题最优解．另外，能量受限的最大圆盘覆盖问题也是带分组限制的最大化次模函数问题[12]的特例．基于随机线性规划取整技术，Guo等[12]设计了一个指数时间的(1-1/e)-近似算法．对于带能量限制的最大圆盘覆盖问题，本研究首先介绍基于贪婪策略的多项式时间(1/2)(1-1/e)-近似算法，并将该算法推广至更一般的问题；然后通过定义代理函数，设计一个分组进化算法，当循环次数的期望E(T)≤emn2(2n+1)时，该算法的近似比可以达到(1/2)(1-1/e)；最后通过实验验证算法的实际性能．1 (1/2)(1-1/e)-近似算法本节介绍能量受限的最大圆盘覆盖问题的一个多项式时间近似算法．在该算法里，每一次迭代从候选集中选择单位增加能量下覆盖收益增量最大的圆盘．当选择圆盘集合的总能量超过P时，迭代停止．基于选择的圆盘集合，构造该问题的可行解，即先移除最后选择的圆盘，然后仅保留同圆心圆盘中最大的．比较该可行解与覆盖收益最大的圆盘，并将收益较大的作为输出解，具体见算法1．算法1 贪婪算法输入 U，𝒟，P，w:U→R+输出 𝒟'Let 𝒟'=∅，Dmax=argmaxD∈𝒟∑u:u∈U(D)w(u)；while p(𝒟')≤P doD'=argmaxD∈𝒟\𝒟'w(𝒟'∪{D})-w(𝒟')p(𝒟'∪{D})-p(𝒟')；𝒟'=𝒟'∪{D'}；end while𝒟'=𝒟'\{D'}；for s∈S do𝒟s={D∈D'|c(D)=s}；Ds=argmaxD∈𝒟sp(D)；𝒟'=𝒟'\𝒟s∪{Ds}；end forreturn 𝒟'=argmax{w(𝒟'),w({Dmax})}定理1 算法1是一个(1/2)(1-1/e)-近似算法，其时间复杂性为O(n2m)．证明 令D1,D2,⋯,Dk+1为算法1中while循环依次选择出的圆盘．依据while循环的停止条件，可得p(𝒟k)≤P和p(𝒟k+1)≥P，其中，对于任意整数i∈{1,2,⋯,k}，𝒟i={D1,D2,…，Di}且𝒟0=∅，有Di+1=argmaxD∈𝒟\𝒟iw(𝒟i∪{D})-w(𝒟i)p(𝒟i∪{D})-p(𝒟i)．定义𝒟*={D1*,D2*,…,Dj*}为问题的最优解，其覆盖的收益为      w*=w(𝒟*)≤w(𝒟*⋃𝒟i)≤w(𝒟i)+(w(𝒟i∪{D1*})-w(𝒟i))+(w(𝒟i∪{D2*})-w(𝒟i))+⋯+(w(𝒟i∪{Dj*})-w(𝒟i))≤w(𝒟i)+∑D:D∈𝒟*\𝒟i(p(𝒟i∪{D})-p(𝒟))⋅w(𝒟i∪{Di+1})-w(𝒟i)p(𝒟i∪{Di+1})-p(𝒟i)≤w(𝒟i)+∑D:D∈𝒟*p(D)w(𝒟i+1)-w(𝒟i)p(𝒟i+1)-p(𝒟i). (1)整理式(1)可得      w*-w(𝒟i)≤∑D:D∈𝒟*p(D)p(𝒟i+1)-p(𝒟i)(w(𝒟i+1)-w(𝒟i))≤∑D:D∈𝒟*p(D)p(𝒟i+1)-p(𝒟i)(w*-w(𝒟i)-(w*-w(𝒟i+1))). (2)整理式(2)可得      w*-w(𝒟i+1)≤1-p(𝒟i+1)-p(𝒟i)∑D:D∈𝒟*p(D)⋅(w*-w(𝒟i))≤(w*-w(𝒟i))⋅exp-p(𝒟i+1)-p(𝒟i)∑D:D∈𝒟*p(D). (3)基于1-r≤e-r，不等式(3)成立．可得      w*-w(𝒟k+1)≤(w*-w(𝒟0))⋅exp-∑i=1k+1(p(𝒟i+1)-p(𝒟i))∑D:D∈𝒟*p(D)≤w*⋅exp-p(𝒟k+1)∑D:D∈𝒟*p(D)≤w*e-1. (4)基于𝒟0=∅和∑i=1k+1p(Di)P，不等式(4)成立．根据Dmax的定义，可得      w(𝒟k)+w(Dmax)≥w(𝒟k)+w(Dk+1)≥w(𝒟k+1)≥(1-1/e)w*,即max{w(𝒟k),w(Dmax)}≥(1/2)(1-1/e)w*．定义1 带分组限制和次模背包限制的最大化次模函数问题的一个实例由全集U、U的一个分组U1,U2,⋯,Uk、次模收益函数f、容量次模函数w和背包限制P组成．若每个分组Ui中的元素均有一个顺序ui1,ui2,⋯,ui|Ui|满足∀U'⊆U\Ui具有f(U'∪{ui1})≤f(U'∪{ui2})≤⋯≤f(U'∪{ui|Ui|})，则称该实例具有自包含性．基于以上定理1的证明，不难得到如下推论．推论1 算法1是具备自包含性的带分组限制和次模背包限制的最大化次模函数问题的一个(1/2)(1-1/e)-近似算法．2 分组进化算法对于任意一个可行的圆盘集合𝒟'⊆𝒟，它可以由一个向量x={{0}⋃{d(s,u)|u∈U}}s∈S表示，其中第s个分量xs=d(s,u)代表以s为圆心且以s到u欧式距离d(s,u)为半径的圆盘Dsu．特别地，xs=0代表该圆盘集合中没有以s为圆心的圆盘或圆盘Ds0在𝒟'中．为了方便，使用x代替𝒟'，并定义：w(x)=w(𝒟');p(x)=p(𝒟');I(x)=∑D:D∈𝒟'U(D).定义2(进化运算Mutation) 给定一个向量x，进化运算将x按一定概率进化成一个新向量x'，其进化过程为x上的每一个分量xs独立地按概率1/(m(|𝒟s|-1))进化为xs'，其中𝒟s={0}⋃ {d(s,u)|u∈U}，xs'∈𝒟s\{xs}，即xs=xs    (概率1-1/m);xs'    (概率1/(m(|𝒟s|-1)).受EAMC算法[11]启发，构造代理函数g(x)=0    (|x|=0);w(x)1-exp(-p(x)/P)    (|x|0),显然函数g(⋅)的值与覆盖收益成正比且与使用的能量成反比．分组进化算法初始化X={{0}s∈S}．每次循环从X中等概率选取一个向量x，使用进化运算得到一个新向量x'．如果p(x')≤P，那么x'须要和集合bI(x')={x∈XI(x)=I(x')}中的向量比较，并更新uI(x')和vI(x')，其中uI(x')和vI(x')为函数g和w下覆盖用户数目为I(x')且覆盖收益最大的向量．如果bI(x')=∅，那么将x'加入X，并且令uI(x')=x'和vI(x')=x'；否则，x'与集合bI(x')中的两个向量uI(x')和vI(x')比较，并保留覆盖收益大的向量．当循环次数为T时，算法停止．分组进化算法见算法2．算法2 分组进化算法输入 U，𝒟，P，w:U→R+，T输出 zlet u0=v0=x={0}s∈S，X={x}，t=0while tT doselect x from X uniformly at random；generate x' by applying mutation to x；if p(x')≤P thenbI(x')={x∈XI(x)=I(x')}；if bI(x')=∅ thenX=X∪{x'}，uI(x')=vI(x')=x'；elseif g(uI(x'))g(x') thenuI(x')=x'；end ifif w(vI(x'))w(x') thenvI(x')=x'；end ifX=X \bI(x')∪{uI(x'),vI(x')}，end ifend ift=t+1，end whilereturn z:=argmaxx'∈Xw(x')基于定理1的证明，容易得到如下引理．引理 对于任意一个总能量不超过P的圆盘集合𝒟'⊆𝒟，即p(𝒟')≤P，令D':=argmaxD∈𝒟\𝒟'w(𝒟'∪{D})-w(𝒟')p(𝒟'∪{D})-p(𝒟')，那么w(𝒟'∪{D'})-w(𝒟')(w*-w(𝒟'))≥p(𝒟'∪{D})-p(𝒟')P.定理2 当循环次数的期望E(T)≤emn(n+1)(2n+1)时，算法2输出的向量z是可行的且满足w(z)≥(1/2)1-1/ew*．证明 向量z的可行性是显然的．令Imax=max{I(x)|x∈X:g(x)≥w*}，显然，Imax在算法运行中均不会变小．下面证明若循环次数的期望E(T)≤emnXmax，则Imax≥1，其中Xmax为算法停止时X中包含向量的数目．根据引理2，圆盘D1'=argmaxD∈𝒟w({D})p(D)满足w(D1')≥p(D1')w*/P≥[1-exp(-p(D1')/P)]w*，即g(x1')≥w*，其中x1'为圆盘集合{D1'}对应的向量．因为{0}s∈S∈X，所以从X中选取{0}s∈S并通过进化运算得到x1'的概率至少为1Xmax1m(|𝒟s1|-1)1-1mm-1≥1emnXmax，式中s1为圆盘D1'的圆心．因此，出现x1'的期望循环数至多为emnXmax．当x1'出现，由于D1'∈𝒟，可以得到p(x1')≤P，因此x1'进入if判定循环．如果x1'被加入X，基于g(x1')≥w*且I(x')≥1，可以得到Imax≥I(x')≥1；否则，在bI(x')中一定存在一个向量x''满足g(x'')≥g(x1')，即Imax≥I(x'')=I(x')≥1．下面证明若Imax≥1，则在期望循环次数E(T)≤emnXmax的情况下，xImax'满足g(xImax')≥w*且I(xImax')Imax．令x'为在X中满足g(x')≥w*且Imax=I(x')的向量，𝒟'为x'对应的圆盘集合，D':=argmaxD∈𝒟\𝒟'w(𝒟'∪{D})-w(𝒟')p(𝒟'∪{D})-p(𝒟')．令xImax'为圆盘集合𝒟'∪{D'}对应的向量，可得I(xImax')Imax．基于引理可得      w(xImax')≥[(p(𝒟'∪{D})-p(𝒟'))/P]⋅(w*-w(x'))+w(x')=[(p(xImax')-p(x'))/P]⋅w*+{1-[(p(xImax')-p(x')/P)]}w(x')≥[(p(xImax')-p(x'))/P]w*+{1-[(p(xImax')-p(x'))/P]}(1-exp(-p(x')/P))w*={1-{1-[(p(xImax')-p(x'))/P]}exp(-p(x')/P)}w*≥{1-exp[-(p(xImax')-p(x'))/P]⋅exp(-p(x')/P)}w*={1-exp(-p(xImax'))}w*. (5)基于g(x')=w(x')1-exp(-p(x')/P)≥w*和1-r≤e-r，不等式(5)成立．综上可得g(xImax')≥w*．基于D'的定义，xImax'与x'仅在对应的传感器c(D')处的坐标不同．因为x'∈X，所以从X中选取x'并通过进化运算得到xImax'的概率至少为1Xmax1m(|𝒟s'|-1)1-1mm-1≥1emnXmax，式中s'为圆盘D'的圆心．即出现xImax'的期望循环数至多为emnXmax．如果p(xImax')P，根据不等式(5)，收益w(xImax') ≥ (1-exp( -p(xImax') / P))w*≥ (1-e-1)w*，且w(xImax')≤w(x')+w({D'})．令xD''为圆盘集合{D'}对应的向量，类似上面证明，出现xD''的期望循环数至多为emnXmax．当xD''出现时，由于D'∈𝒟，可以得到p(xD'')≤P，因此xD''进入if判定循环，那么在b|I(xD'')|中一定存在一个向量x''满足f(x'')≥f(x')．即x''和x'均在X中，那么算法输出解的覆盖收益满足      w(z)≥max{w(x'),w(x'')}≥max{w(x'),w(xD'')}≥(1/2)w(xImax')≥(1/2)1-1/ew*,否则，即p(xImax')≤P，xImax'进入if判定循环．若X加入xImax'，基于g(xImax')≥w*且I(xImax')Imax，则Imax将变大至I(xImax')；否则在bI(xImax')中一定存在一个向量x''满足g(x'')≥g(xImax')≥w*，即Imax≥I(x'')，此结论与Imax矛盾．重复上面的过程，当Imax=n时，算法2的输出解z满足w(z)≥(1/2)(1-1/e)w*．下面分析循环次数的期望．首先Imax从0到Imax≥1所需要的期望轮数至多为emnXmax；然后Imax从1~n需要的期望轮数至多为(n-1)emnXmax；最后出现xD''所需要的期望轮数至多为emnXmax．对于任意j∈{1,2,…,n}，在bj中最多含有两个向量，即Xmax≤2n+1．综上，循环次数的期望至多为emnXmax(n+1)(2n+1)．3 实验实验使用python3.8，系统参数为AMD Ryzen7 5800H，3.20 GHz，16 GiB RAM，Windows11运行．为展示分组进化算法(EAMC)的性能，每一个实例都将与贪婪算法(Greedy)、修正贪婪算法(Greedy+)、论文[11]中的算法(线性规划+整数取整)与CPLEX(最优值)计算的输出解比较．分组进化算法的循环次数设置为mn2，并运行250次取平均值作为分组进化算法的输出值．实验实例的用户与传感器的位置随机产生在一个边长为100单位正方形平面上．图1(a)为在n=50，m=40，α=1的情况下，考虑能量P=40，60，80，100的情况；图1(b)为在n=50，m=20，P=70的情况下，考虑衰减因子α=1，1.5，2.0，2.5的情况；图1(c)为在n=50，P=70，α=1的情况下，考虑传感器个数m=20，30，40，50的情况；图1(d)为在m=50，P=70，α=1的情况下，考虑用户数目n=50，100，150，200的情况．实验表明：多数情况下分组进化算法的输出值优于其他测试算法，且与实例的最优值几乎相同．10.13245/j.hust.240207.F001图1实验结果4 结语本研究提出了能量受限的最大圆盘覆盖问题，该问题旨在寻找一个传感器网络的能量分配方案，在满足能量约束的情况下使得覆盖用户的总收益最大．针对该问题，基于贪婪策略，设计了一个(1/2)∙(1-1/e)-近似算法；然后设计了一个进化算法，并证明在期望多项式时间内，该算法具有相同近似比．基于随机实例的实验结果，分组进化算法的输出解目标函数值与最优值几乎相同．