基于列生成法的无线供电传感网最大化系统吞吐

徐志伟，裴清福

（陕西铁路工程职业技术学院电气与信息工程系，陕西渭南714000）

在无线传感网中，传感器节点消耗的能量来自于携带的有限能源如电池等。但它们的生命周期受有限能源的约束，不得不以低速率通信传输[1，2]。然而，无线频谱能量传输技术的出现可以有效解决能源约束的问题。基站和无线供电站都可提供无线频谱信号，在915 MHz，距离1 W基站0.6 m和11 m的传感器节点可分别接收来自基站提供的3.5 mW和1μW能量[3]。无线信号能量传输技术已经被用于嵌入式系统中[4-7]。随着无线信号能量传输技术的发展，在下一代无线传感网络中，无线能量传输技术将被广泛的应用。

由于无线信号可同时携带能量和信息，很多文献对如何同时进行无线信息传输和能量收获的问题进行了研究[8-10]。然而，无线传感网络大量的通信数据集中在上行通信。因此，另一类叫做无线供能传感网络的研究成为了研究者广泛关注的热点[11-13]。无线供能传感网络是指在下行通信中基站对传感器节点进行能量供应，传感器节点利用接收到的能量进行上行的通信传输。在文献[14]中，作者首次提出了无线供能和信息传输的概念，并提出了“先获取能量后传输”的协议，规定了无线供能通信网络中，上行的接到方式为TDMA，有效地消除了共享信道干扰，并提出了如何最大化系统吞吐的策略。在文献[15]中，作者基于文献[14]提到的协议，分析了通信链路丢失概率对吞吐的影响，提出了两种方法解决最大化吞吐问题。然而基于TDMA的通信方式，无线供能传感网络在上行的同一时刻只能有一个传感器节点发送信号。这种方式不能充分地利用无线频谱。为了提高频谱利用率和系统吞吐，可采用多信号同传方式。然而，这种方式会造成传输信号间的互干扰。为了消除互干扰对吞吐性能的影响，基于相继干扰消除的多信号检测技术被广泛关注。相继干扰消除技术是一种操作方便而且鲁棒性很强的干扰消除方法[16]。

文中结合相继干扰消除方法，考虑无线供能传感网络中最大化吞吐问题。对问题进行了数学建模，通过分析，给出了快速求解问题的方法。并通过仿真，发现吞吐量相比较无相继干扰消除时，提升了至少30%。

1 系统模型

如图1所示，一个基站和多个传感器节点构成了一个无线供能传感网络。基站通过下行广播的无线信号为传感器节点提供能量。传感器节点将获得的能量用于上行数据通信。基站在上行通信中通过相继干扰消除技术对接收到的多个传感器节点传输的信息进行依次解码。

图1 无线功能传感网络示意图

假定基站有无限的能量来源，传感器节点安装有可充电的电池，下行收获的能量存储在电池中作为唯一的能量源。li表示传感器节点和基站间形成的链路。Ν表示所有链路子集形成的集合。激活的传感器节点i等同于链路li被激活。我们假定在一个时间块T中，上行和下行的信道状态保持不变。gi0和gi1分别表示传感器节点i和基站之间上行和下行的信道增益。在不同的时间块中，信道状态可以不同。分别用P0和Pi表示基站和传感器节点i的传输功率。则传感器节点i在下行通信时间获得的由基站传输的能源可用下式表示。

其中ζi表示传感器节点i的能源转换效率，0＜ζi＜1,i=1,...,N。ηi表示传感器节点i用于信息传输的能量占收获能量的比值。假定所有的能量都用于信息传输。因此，ηi=1，i=1,2,...,N，tdown是时间块中的下行通信时间。

传感器节点在下行通信时间tdown结束后，开始上行数据传输。由于硬件的要求，启用连续干扰消除基站的解码能力是有限的。假定干扰消除解码能力为L，换言之，基站在一个时间槽内解码的信号数量不能超过L。上行通信时间被划分成多个时间槽，受解码能力限制，每个时间槽内不超过L个传感器节点可处于激活状态，其余传感器节点则进入睡眠状态。用C表示N个链路的子集组成的集合，这些子集包含的元素不超过L。用c表示C中的成员。组c表示c中的所有链路在同一时间槽内处于激活。因此链路li1的信号干扰噪声比SINRi可表示为。

其中δ2表示噪声功率。在连续干扰消除过程中，已解码的信号对后续解码信号不被视为干扰。s(i)表示传感器节点的一个子集，子集中的传感器节点发送的信号先于传感器节点i的信号解码。则组c中的传感器节点i可靠的最大速率可表示vi=Wlog(1+SINRi)，W为带宽，log为二进制对数。则组c的总速率vc可表示为。

由式（3）得，组c的传输速率不会随信号解码的顺序不同而改变。tc表示组c在上行通信中的运行时间。所有tc之和为上行通信总时间tup。Pjc表示传感器节点在组c激活时的传感器节点j的传输功率。如果链路lj1是组c的一个元素，则Pjc=Pj，否则Pjc=0。将时间块T标准化为单位时间。不失一般性，确保每个传感器节点能分配到上行时间和基站进行通信，用ε表示每个传感器节点最小的上行通信时间。则最大化吞吐问题可以建立为如下模型。

目标函数是求系统最大吞吐，约束条件式（4）保证总的传输时间和能量收获时间不大于单位时间。约束条件式（5）中的第j个不等式限制了传感器节点传输的总能量不能大于下行的收获能量。约束条件式（6）保证至少每个传感器节点的上行通信时间占总的上行时间的比例不小于阈值ε。其中tc和tdown都为非负变量。

尽管模型为线性规划模型，但时间复杂度跟传感器节点的数量有关。当传感器节点数量很大时，很难用现有的求解软件进行计算。列生成方法是一种有效解决大规模问题的方法。我们利用列生成方法对[M1]进行了有效求解。

2 列生成方法的基本原理

列生成方法的主要思想：对含有大规模线性规划问题，将原问题划分为主问题和子问题。主问题只通过解含有已知部分列的约束矩阵的规划模型。通过主问题的求解可以获得原问题的一个可行解。但这个可行解并不一定为原问题的最优解。检验主问题所得到的可行解是否为最优解或是否能产生新的进基列，需要对子问题进行求解。若子问题能够找到改进原问题当前解的进基列，则进行主问题和子问题的循环迭代，直到无法找到进基列为止。

2.1 主问题

用Q表示已知的列集，q∈Q≜{1,2,...,Q}，表示集合中每列的索引号。则最大化吞吐问题的主问题可由[M2]模型表示。

模型[M2]与[M1]类似，目标函数为最大化吞吐。求解[M2]，可得原问题的一个可行解。然而当前的可行解是否为原问题的最优解，需通过计算其余备选列c∈C/Q的判别数大小确定是否为最优解。如果备选列中每一列的判别数大小都为负，则当前的解为最优解，否则不是。备选列c的判别数大小可由下式表示。

通过式（7）确定当前解是否为最优。然而需要每次迭代都搜寻一遍全部的备选列。为了更快更有效的确定当前解是否为最优解以及是否备选列中存在可以改善当前解的进基列，可通过子问题来解决此问题。

2.2 子问题

子问题的目标是找一个具有正判别数的列，如果在备选列中可以找到，则主问题的当前解不是原问题的最优解，且可以找到一个进基列继续改进原问题解的质量。

为了建立子问题的模型，我们引入N个二元变量rj∈{0,1}，∀j∈N。如果lj1激活，rj为1，否则为0，子问题可被表示成如下形式

目标函数为最大化判别数。约束式（19）保证激活的链路数不大于最大解码数L。求解模型，找到判别数最大的列，若最大列的判别数为负，则整个备选列不存在判别数为正的，当前解为最优解。模型为非线性规划，实际中求解非线性规划模型非常困难。利用启发式算法可以有效快速的求解子问题。

2.3 启发式算法

启发式算法的主要核心思想是相继添加链路到一个空集合S中，其添加的顺序按照判别数大小进行选择。每一次选择，分别添加所有链路到S中，计算对应的S的判别数大小，选取其中一个对应S判别数最大的链路。直到S不能再添加链路为止。启发式算法的伪代码如图2所示。

图2 启发式算法伪代码

每一次迭代中（第2行到第10行），添加备选集合A中的每个链路进入集合S并计算相应的判别数。如果判别数大于下界，则更新下界（第7行）。经过一次迭代后，选择出一条链路。然后，将链路添加到集合S中并将其从集合A中撤销掉。当前集合S的判别数大小可通过第5行求出。算法结束于第12行或16行，当没有链路可以改变下界或L次循环完成。显然，启发式算法的复杂度在最坏情况下为O(NL)。

3 仿真及结果分析

假定N个传感器节点随机地分布在以基站为圆心和半径为10 m的圆内。设定基站的传输功率和传感器节点的传输功率分别为30 dBm和-10 dBm。带宽设置为10 MHz。噪声功率δ2为-50 dBm。假定信道小尺度衰落服从瑞利分布，则信道增益可表示为。是一个均值为1服从指数分布的随机变量。α为路径丢失指数。能源收获的效益ζ=ζi，i=1,2,...,N设为0.5。传感器节点i和基站的距离di=max{1,d}。假定1 m参考信号的平均信号衰减为30 dB。每次仿真运行50个实例。

用“MT-OPT”，“MT-TDMA”和“MT-SIC”分别表示[M1]，无连续干扰消除，基于连续干扰消除的列生成算法的解。

首先，设定干扰消除能力为5，传感器节点的数目分别为{5，10，15，20，25}。系统的吞吐性能与节点数目的关系如图3所示，加入连续干扰消除与无干扰消除的时间多分复用接入比较，可增加约30%的吞吐。基于启发式的列生成算法解与最优解相差小于0.7%。说明列生成算法有非常好的鲁棒性。随着传感器节点的增加，加入连续干扰消除相比无干扰消除最大可以增大吞吐达60%。因此，在密集型传感器网络中，采用连续干扰消除对系统吞吐影响更大。

其次，设定传感器数目为20，考虑连续干扰消除的解码能力对吞吐的影响，设定L={1，2，3，4，5}。如图4所示，增大L使得更多的传感器节点可以在同一时间槽内激活，即使连续干扰消除解码能力为2，平均吞吐相比解码能力为1（无干扰消除的时间多分复用方式）增大72%，随着解码能力L每增大1，提升的吞吐可达50%。

图3 传感器节点数目与吞吐量关系示意图

图4 吞吐量与解码能力关系示意图

4 结 论

文中研究了无线供电传感网络的最大化吞吐问题，对问题建立了线性模型。并提出了利用列生成算法对模型进行了有效求解。针对列生成算法中子问题的整数规划模型，提出了可快速求解子问题的启发式算法。最后通过仿真发现，加入连续干扰消除能够增大系统吞吐。基于启发式的列生成算法在求解此问题中，具有很好的鲁棒性和求解能力。

参考文献：

[1]张明.具有能量收集功能的无线传感器网络最优传输策略研究[D].南京：南京邮电大学，2014.

[2]韩建辉，亓东欣，张威，等.近场无线能量传输系统的效率研究[J].电子科学与工程，2012，5（4）:381-386.

[3]Qian Sun，Gang Zhu，Chao Shen，et al.Joint beamforming design and time allocation for wireless powered communication networks[J].IEEE Communications Letters，2014，18（3）:1089-7798.

[4]Wu Q，Tao M，D W.K Ng，et al.Energy-efficient resource allocation for wireless powered communication networks[J].IEEE Trans.Wireless Commun.，2016，15（3）:2312-2327.

[5]Hadzi-Velkov Z，Nikoloska I，Karagiannidis G，et al.Wireless networks with energy harvesting and power transfer:Joint power and time allocation[J].IEEE Signal Process.Lett.，2016，23（1）:50-54.

[6]Chen X，Zhang Z，Chen H，et al.Enhancing wireless information and power transfer by exploiting multi-antenna techniques[J].IEEE Commun.Mag.，2015，53（4）:133-141.

[7]Timotheou S，Krikidis I，Zheng G，et al.Beamforming for MISO interference channels with QoS and RF energy transfer[J].IEEE Trans.Wireless Commun.，2014，13（5）:2646-2658.

[8]Mohammadi M，Chalise B K，Suraweera H，et al.Throughput analysis and optimization of wirelesspowered multiple antenna full-duplex relay systems[J].IEEE Trans.Commun.，2016，64（4）:1769-1785.

[9]Ding Z.Application of smart antenna technologies in simultaneous wireless information and power transfer[J].IEEE Commun.Mag.，2015，53（4）:86-93.

[10]Yuan Y，Ding Z.The application of non-orthogonal multiple access in wireless powered communication networks[C]//in Proc.IEEE 17th Int.Workshop Signal Process.Adv.Wireless Commun.（SPAWC），2016：1-5.

[11]Huang K，Lau V.Enabling wireless power transfer in cellular networks:architecture，modeling and deployment[J].IEEE Trans.Wireless Commun.，2014，13（2）:902-912.

[12]Lee S，Zhang R，Huang K.Opportunistic wireless energy harvesting in cognitive radio networks[J].IEEE Trans.Wireless Commun.，2013，12（9）:4788-4799.

[13]Wu X，Xu W，Dong X，et al.Asymptotically optimal power allocation for massive MIMO wireless powered communications[J].IEEE Wireless Commun.Lett.，2016，5（1）:100-103.

[14]JuH，ZhangR.Throughputmaximizationin wireless powered communication Networks[J].in IEEE Trans.Wireless Commun.，2014，13（1）:418-428.

[15]Sun Q，Zhu G，Shen C，et al.Joint beamforming design and time allocation for wireless powered communication networks[J].IEEE Communications Letters，2014，18（10）:1089-7798.

[16]Timotheou S，Krikidis I.Fairness fornonorthogonal multiple access in 5G systems[J].IEEE Signal Process.Lett.，2015，22（10）:1647-1651.