RFEHWSN中满足节点吞吐量需求的负载均衡基站部署方案*

周卫元,陈立建,,徐欣晨,毛科技*

(1.浙江广播电视大学萧山学院,杭州 311200;2.浙江工业大学计算机科学与技术学院,杭州 310032)

无线传感器网络WSN(Wireless Sensor Networks)是由传感器节点、汇聚节点(Sink node)和终端等3个部分组成的一种自组织网络,由于应用场合的特殊性,传感器节点一般由电池供电,电池更换比较困难或者花费代价比较高[1-2]。所以直接能从环境中捕获能量的WSN被广泛的进行了研究与应用,能从环境中捕获的能量包括太阳能、热能、射频能量、振动能量、机械能等等[3-4]。射频能量捕获无线传感器网络RFEHWSN(Radio Frequency Energy Harvesting Wireless Sensor Network)可以通过不同物理环境和不同需要条件如时间、频率、能量源的发送能量功率等维度上进行充分的控制,稳定性较强[5-6]。RFEHWSN 一般由能量源ET(Energy Transmitter)、基站BS(Base Station)和无线传感器节点组成。

目前在RFEHWSN的研究进展有,文献[7]给出了射频能量捕获无线传感网中占空比最佳的能量源布置方法。文献[8]描述了射频能量捕获异构无线传感网的能量源最少化布置方法。文献[9-11]对无线传感网络的射频能量收集器,能量源移动路径约束下时延最小化供电方案,射频能量收集芯片等进行了研究。文献[12]的模型也是点对点的平坦衰落信道下的无线系统,由于时变同信道信号干扰的存在,单天线接收方不仅要考虑如何收集发射机发射的干扰信号或者特定信号作为节点的能量供应,还要考虑如何解码信息。文献[13]提出了一种动态功率拆分的分配方案,即接收器接收到的信号一部分用以电池的供能,一部分用以信息解码。在RFEHWSN的基站部署方面,文献[14]研究了 RFEHWSN 中满足节点吞吐量需求的基站最少化部署问题,提出一种低复杂度的启发式部署算法和一种复杂度略高的基于遗传算法的部署算法。文献[15]以最少化基站和能量源数目为目标,研究了基站和能量源的联合部署,满足每个节点的平均能量捕获功率比所需数据发送功率至少高出一个预定的阈值作为约束条件。本文考虑在异构射频能量捕获传感网中,确定出满足所有传感器节点吞吐量所需求的最少基站个数,将其作为初始化部署,给定多于初始化部署所需个数的基站(如1.5倍的初始化基站个数),在不同基站数目下,部署基站满足负载均衡,从而使节点的传输速率和网络吞吐量满足一个较优的水平。

1 系统模型

本节介绍满足节点吞吐量需求的负载均衡基站部署的异构RFEHWSN模型。

1.1 网络模型

(1)

(2)

1.2 能量捕获模型

(3)

1.3 信息传输模型

(4)

式中:λ2为数据传输信号波长。节点向基站传输信息,节点接入该基站。基站的接入量,也称负载量,定义为接入该基站的节点数目(基站服务节点数)。根据信噪比公式,基站Bn从节点Sk处接收的信号的信噪比为

(5)

式中:no是高斯白噪声的功率谱密度,W是信号带宽。根据香农公式,可以得到节点Sk的实际吞吐量Ck为:

Ck=Wlog2(1+SNRk),k=1,2,…,K

(6)

综上以上公式可得:

(7)

2 吞吐量较优的满足负载均衡的基站部署方法

基于以上分析,最优基站部署问题可建模为优化如下问题:

目标:均衡各个基站的服务节点数量

变量:各个基站位置

满足全部节点的吞吐量需求的负载均衡基站部署方案为可行基站部署方案。在所有可行基站部署方案中,负载量最均衡的基站部署方案为最优基站部署方案。

由于基站数N是整数取值且节点的吞吐量表达式不是凸函数,该问题实际上是研究一个非线形和非凸优化问题,不能用凸优化理论解决。本文提出高效的启发式基站部署方案,值得说明的是,该问题与ETs部署问题都属于拓扑优化问题,但是由它们对应的数学优化问题可以知道,ETs部署问题中约束函数涉及的节点能量捕获表达式与基站部署问题中约束函数涉及的节点吞吐量表达式有着显著的不同。在ETs部署问题中,每个ETs位置的改变会影响所有节点所捕获的功率,而在基站部署问题中,每个基站位置的改变只影响其周边少数节点。因此,ETs部署问题的已有部署方案不适用于基站部署问题。此外,该问题与最小化基站问题也有着不同,最小化基站问题并不考虑每个基站的负载量,目的是基站数目最小。而在负载均衡基站部署中,需要优化的是每个基站的位置和接入量,基站数目的多少影响着整个网络的基站负载量。

3 基站部署方法

本文定义以下几个在基站部署方案中涉及的概念和定义。

(8)

由式(7)、式(8)可知,距离基站越近的节点可以达到的吞吐量越高。

定理1在可行基站部署方案中,任意一个节点的需求圆内至少部署一个基站。

证明:通过反证法来证明。对于某个可行基站部署方案,假设一个节点的需求圆内没有基站,那么该节点到最近基站的距离大于需求半径,那么该节点达不到其吞吐量需求。因此,这与可行基站部署方案的定义相矛盾。证明结束。

定义2(最糟糕基站) 全网中服务节点数目最多的基站。

定理2存在一个最优部署方案,每个基站都是在最小覆盖长方形内。

证明:通过反证法来证明。假设每个最优基站布置方案都有基站部署在最小覆盖长方形外。任意挑一个最优基站布置方案,如图1所示,有个基站部署在最小覆盖长方形ABCD外的E点。现将该基站从E点沿着垂直于AD边的线路上移动直至到达AD边上的F点。易知,任一原先接入该基站的节点,到该基站的距离变得更短,因此该新基站部署方案仍为可行方案。证明成立。

图1 部署示意图

在给定基站个数N和节点个数K时,平均基站服务节点数Bavg为

Bavg=K/N

(9)

每个基站的服务节点数越接近平均数,则部署方案越优。为了使本文的部署方案能更好地反映均衡性,本文采用基站负载量方差这个参数σ2来衡量。

定义基站负载量方差为

(10)

Bload是每个基站的负载量,方差越小,方案越优。

本文在初始化部署中,基站的部署方案要满足约束条件,使每个节点满足各自的吞吐量需求;在负载均衡部署中,始终满足吞吐量约束条件基础上对基站进行接入量的优化。

3.1 初始化部署

给定节点和ETs的位置和个数情况下,根据式(3)计算出节点的能量捕获功率。给定各个节点的吞吐量要求下,再根据式(8)计算出各个节点的需求半径和需求圆。

初始化部署方案满足每个节点的吞吐量需求,所以我们可以执行某个已有的部署方案,将所需最小基站数目部署在网络中,并将节点接入相应的基站。具体步骤如下:

第2步 由节点的发送功率和最低吞吐量需求计算出各个节点的需求半径rk. 和需求圆。

第3步 执行某个已有的部署方案(本文的方案)来将Nmin个基站部署到网络中并将节点接入到这些基站。

第4步 确定剩余基站数N′=N-Nmin。

3.2 负载均衡优化部署

本文部署的主要目标是让最糟糕基站达到负载均衡的效果,所以基站的接入量是唯一衡量指标,分别从两个维度——节点和其余基站以均衡糟糕基站。对于节点而言,若其需求圆内基站个数大于1,节点进行信息传输基站的选择就有很多种,为了满足负载均衡,节点可以切换接入负载量较轻的基站进行信息传输。对于基站而言,若它原来所有的节点都已经切换到其余基站时,该基站可作为一个待移动基站,在性质上与未部署基站是一样的(即此时接入量为0),该基站可以部署在最糟糕基站位置上,有效降低最糟糕基站的接入量。

因此,优化方案可分为4个部分:给定节点的切换优化、给定基站接入节点的切换优化、单个待移动基站的挑选和全网节点接入优化。

①给定节点的切换优化Node-Switch

当节点的需求圆内部署了不止一个基站时,为了满足负载均衡,该节点就有选择切换基站进行信息传输的权利。若节点当前传输信息的基站接入量相比较其他圆内基站更大,则该节点可以切换至接入量较小的基站上。在该模块中,执行以下步骤:

第1步:对于给定的节点Sk,该节点的需求圆内的基站数目(记为I)大于1,即I>1,则节点进入准备切换状态,当前接入的基站记为Bnow。

第2步:值得注意的是节点只会切换至负载量小于P的基站。在节点需求圆内找到负载量最低的基站B1。

第3步:判断基站B1是否为Bnow。若不是,则节点切换至B1,否则继续执行。

第4步:完成该模块。

②给定基站接入节点的切换优化Nodes-Switch in BS

对于某个基站Bn下所有接入的节点,进行一个优化接入Node-Switch。具体步骤如下:

第1步 给定某个基站B,记此时基站负载量为P。

第2步 记录接入该基站B的所有节点Sp(p=1,2…P)。

第3步 初始化p=1。

第4步 判断p<=P是否成立,若成立,继续向下执行,若不是,执行第8步。

第5步 对于节点Sp,判断该节点的需求圆内是否有多个基站。

第6步 若该节点的需求圆内只有一个基站B,则该节点只能接入该基站B,执行第7步。否则,调用执行模块Node-Switch。

第7步p=p+1,执行第4步。

第8步 完成该模块。

③单个待移动基站的挑选Single Moving BS Selection

在这一模块中,由于基站的负载量越低,其相应节点切换的复杂度越低,所以依次按照负载量从低到高的顺序,尝试从所有已经部署的基站中挑选出一个待移动的基站。当接入某个基站的节点可以全部切换到其他基站后,此时该基站的负载量为0,那么该基站就是待移动的基站,它可以去均衡负载量更重的基站。具体步骤如下。

第1步:基站负载量进行从低到高排序,记为B1,Bi,…,BI,(1

第2步:判断i

第3步:给定基站Bi,此时基站负载量记为P,记录接入该基站Bi的所有节点Sp(p=1,2,…,P)。

第4步:判断当前基站Bi下所有的节点Sp的需求圆内是否都存在至少两个基站,只要存在一个节点的需求圆内只有一个基站,则Bi不能成为待移动基站,执行第7步。否则当所有的节点的需求圆内是否都存在至少两个基站,继续执行。

第5步:在所有的节点Sp的需求圆内将基站Bi标记可悬空。

第6步:节点Sp接入其需求圆内负载量最小的基站,执行第8步。

第7步:i=i+1,执行第2步。

第8步:退出。

④全网节点接入优化All Nodes Optimization

在该模块中,主要目标是均衡最糟糕基站的负载量,使得全网节点的信息传输相对较均衡。伪代码如下:

All Nodes Optimization

1. while(true)

2. 挑出当前最糟糕基站,执行将其一半的接入节点切换走;

3. if(Nodes-Switch in BS没有进行任何节点接入的切换)

4. break;

5. end while

基于以上分析,优化部署的总体伪代码如下:

负载均衡优化部署方案

Output:所需基站物理位置

Main procedures

①初始化部署

2. 将最小覆盖长方形区域分割成p×q个小网格,并将这些网格标上序号,每个网格的中心记

为基站可能放置的位置。

3. 由节点的发送功率和最低吞吐量需求计算出各个节点的需求半径rk。

4. 执行某个已有的基站部署方案(比如本文前面所提方案)来将Nmin个基站部署到网络中,将

节点接入这些基站。

②负载均衡优化部署

1. if(N>Nmin)

2. for(i=1;i<=N-Nmin;i++)

3. 从剩余基站中挑出一个,部署到最糟糕基站上;

4. 执行All Nodes Optimization进行全网节点优化;

end for

end if

5. while(true)

6. 执行Single Moving BS Selection尝试挑出一个待移动的基站;

7. if(Single Moving BS Selection挑出了基站)

将其放在最糟糕基站边上;

8. else

return;

9. 执行All Nodes Optimization进行全网节点优化;

end while

4 实验仿真

本文仿真实验的场景是10 m×10 m的区域内随机部署了K个传感器节点,均匀部署了4个ETs,每个ET的发送功率Pt=0.1 W。能量捕获模型和信息传输模型的相关参数如下[16]:η=0.3,Gs=8 dBi,Gr=2 dBi,Lp=3 dB,λ1=0.33 m,λ2=0.66 m,ε=0.2316 m,α=0.8。每种情况下的拓扑模拟1 000次。

采用的对比方案一,随机对比法,即相同初始化部署后,如果还有基站未使用,则将剩余全部基站随机放置在节点需求圆覆盖范围内,接着节点按照1/2的概率选择是否进行基站切换;如果基站已经使用完,那么方案结束。

对比方案二,接入一半法,即相同初始化部署后,如果还有基站未使用,则每次将基站放置在全网最糟糕的基站旁,分担其一半的接入量,直到所有基站全部部署;如果基站已经使用完,那么方案结束。

图2 不同节点数下3种方案的平均最糟糕基站负载量(N=1.5Nmin)

4.1 最糟糕基站负载量比较

图2给出了当给定基站是满足初始化部署所需基站(即满足所有节点吞吐量需求的基站)的1.5倍,即N=1.5Nmin时候,3种方案在节点不同情况下,最糟糕基站的负载量对比。第2个图是在第1个图的基础上,画出的最糟糕基站降低量对比,更能直观地看出所提算法的优势。由图中可以看出,所提方案在最糟糕基站负载量上均比两个方案要优。

图3直观地反映了所提方案在最糟糕基站负载量上都比对比方案分别低,在随机部署法对比中降低率在50%上下,在接入一半法对比中降低率在10%左右至20%左右,效果十分明显。

图3 不同节点数下3种方案的平均最糟糕基站负载降低量(N=1.5Nmin)

原因如下:随机部署法存在十分大的偶然性,在初始化部署之后,剩余的基站随机放置在节点需求圆覆盖的区域内,不会非常准确地正好落在最糟糕的基站旁边,所以该方案的最糟糕基站负载量较大。接入一半法与所提方案在初始化部署和全网节点接入优化All Nodes Optimization前半部分一样,在满足节点吞吐量需求后,将剩余基站轮次放置在最糟糕基站旁边,分担一半的接入节点。由图可知,将剩余基站放置在最糟糕的基站旁边,能有效地降低负载量。相比较随机部署法,接入一半法和所提方案的最糟糕负载量明显下降。而在本文所提方案有全网均衡的效果,不仅可以通过剩余基站降低负载,也可以通过已经部署好的基站来分担最糟糕基站的负载量,所以所提方案还要比接入一半法在最糟糕基站负载量少。

图4 不同基站数下接入一半法与所提方案最糟糕基站降低量对比,K=40

图4给出了在节点数为40,给定不同基站下,即N=aNmin,a∈. {1,1.2,1.4,1.6,1.8,2}的情况下,所提方案与接入一半方案在最糟糕基站下的降低量对比。降低量先降低后上升再降低,但是始终所提方案的结果要更优。

在a={1,1.2}时,降低量降低,原因如下:在a=1时,接入一半法即为初始化部署,最糟糕的基站位置必然是全网节点需求圆重叠最高的区域,且重叠部分的节点都将接入该基站。而所提方案会在初始化部署基础上进行优化接入,将最糟糕基站的负载量均衡到其他基站,所以在a=1降低量较高。当基站数目上升时,接入一半法存在剩余基站开始均衡最糟糕基站,与所提方案相差减少,所以降低量下降。

在a={1.2,1.4 1.6}时,降低量上升,原因如下:假设节点数40的情况下,最少需要4个基站,即Nmin=4,初始化部署基站分别接入21、8、8、3,最糟糕基站负载量为21。在接入一半法下,a=1.2,N=5,将剩余的一个基站放在最糟糕基站旁边,均衡一半负载,此时所有5个基站部署结束,基站负载量为11、10、8、8、3,最糟糕基站负载量此时为11。当a=1.4,N=6,基站再增加一个,基站负载量分别为5、6、10、8、8、3,最糟糕基站负载量此时为10。当a=1.6,N=7,基站再增加一个,最后结果为5、6、5、5、8、8、3,最糟糕基站负载量此时为8。在所提方案中,初始化部署与接入一半法基站接入相同:21、8、8、3,最糟糕基站负载量为21。当a=1.2,N=5,将剩余的一个基站放在最糟糕基站旁边,均衡一半负载,然后进行全网优化,基站负载量为10、10、8、8、4,最糟糕基站负载量此时为10。当a=1.4,N=6,基站再增加一个,优化后基站负载量分别为9、8、5、6、7、5,最糟糕基站负载量此时为9。当a=1.6,N=7,基站再增加一个,优化后放置最后结果为7、7、5、5、6、5、5,最糟糕基站负载量此时为7。为直观起见如表1所示。

表1 负载量比较表

然而随着基站数目的不断增加,新增加的基站几乎都覆盖接入了所有接入量较大的基站,所以两个方案中每个基站接入量介于平均,所以降低量减少。

4.2 方差比较

如图5,在a=1.5,N=1.5Nmin时,即给定的基站是满足节点吞吐量需求下基站数目的1.5倍,可以从图中清楚地看到,所提方案的方差σ2明显优于两个对比方案,方差越小,说明负载越均衡,且所提方案的方差均能保持在1以下,说明每个基站的负载量越均衡,也满足了每个节点的吞吐量需求。

随着节点数目的增加,本文的算法与随机部署法方差降低量都维持在90%左右,如图6所示。

图5 不同节点数下3种方案的方差对比(N=1.5Nmin)

图6 不同节点数下3种方案的方差降低量对比(N=1.5Nmin)

当节点数为30,即K=30,给定不同基站数目,即N=aNmin,a∈{1,1.2,1.4,1.6,1.8,2}下的3种方案方差对比。一方面,基站越多,所有方差都呈现下降趋势;另一方面,本文所提方案均能保持一个较低的方差值,如图7所示。

图7 不同基站数下3种方案的方差对比(K=30)

图8 不同基站数下所提方案与接入一半法的方差降低量对比(K=30)

图8是图7的更直观表示,更有区分度地反映了所提方案与接入一半法在这种情况下方差的降低量,即使在给定最小基站数目两倍的基站情况下,降低量依然能保持在10%以上。

5 总结

本文提出了如何在获得最小化基站个数并且满足每个节点的吞吐量需求不少于一个门限值条件下,优化每个基站的负载量的方案,引入最糟糕基站的负载量和网络基站负载量的方差作为优化指标。该方案分为两部分:初始化部署和优化部署。初始化部署用最小的基站数目以满足节点的吞吐量需求,优化部署的主要目的是达到负载均衡。其中,优化部署分为4个模块,分别为:给定节点的切换优化、给定基站接入节点的切换优化、单个待移动基站的挑选和全网节点接入优化。节点可以通过切换需求圆内的基站以优化每个基站的接入量,负载量小的基站可以分担负载量大的基站节点,同时网络中也可以通过方差来判断是否可以挑选出可以移动的基站来均衡全网最糟糕的基站。通过这些步骤优化部署,既要满足每个节点吞吐量限制,也要让每个基站负载量尽可能小。仿真结果表明,通过节点的优化接入能够有效降低网络基站负载量方差,达到负载均衡的效果。