基于列生成法的無線供電傳感網(wǎng)最大化系統(tǒng)吞吐

徐志偉，裴清福

（陜西鐵路工程職業(yè)技術(shù)學(xué)院電氣與信息工程系，陜西渭南714000）

在無線傳感網(wǎng)中，傳感器節(jié)點(diǎn)消耗的能量來自于攜帶的有限能源如電池等。但它們的生命周期受有限能源的約束，不得不以低速率通信傳輸[1，2]。然而，無線頻譜能量傳輸技術(shù)的出現(xiàn)可以有效解決能源約束的問題。基站和無線供電站都可提供無線頻譜信號，在915 MHz，距離1 W基站0.6 m和11 m的傳感器節(jié)點(diǎn)可分別接收來自基站提供的3.5 mW和1μW能量[3]。無線信號能量傳輸技術(shù)已經(jīng)被用于嵌入式系統(tǒng)中[4-7]。隨著無線信號能量傳輸技術(shù)的發(fā)展，在下一代無線傳感網(wǎng)絡(luò)中，無線能量傳輸技術(shù)將被廣泛的應(yīng)用。

由于無線信號可同時攜帶能量和信息，很多文獻(xiàn)對如何同時進(jìn)行無線信息傳輸和能量收獲的問題進(jìn)行了研究[8-10]。然而，無線傳感網(wǎng)絡(luò)大量的通信數(shù)據(jù)集中在上行通信。因此，另一類叫做無線供能傳感網(wǎng)絡(luò)的研究成為了研究者廣泛關(guān)注的熱點(diǎn)[11-13]。無線供能傳感網(wǎng)絡(luò)是指在下行通信中基站對傳感器節(jié)點(diǎn)進(jìn)行能量供應(yīng)，傳感器節(jié)點(diǎn)利用接收到的能量進(jìn)行上行的通信傳輸。在文獻(xiàn)[14]中，作者首次提出了無線供能和信息傳輸?shù)母拍?，并提出了“先獲取能量后傳輸”的協(xié)議，規(guī)定了無線供能通信網(wǎng)絡(luò)中，上行的接到方式為TDMA，有效地消除了共享信道干擾，并提出了如何最大化系統(tǒng)吞吐的策略。在文獻(xiàn)[15]中，作者基于文獻(xiàn)[14]提到的協(xié)議，分析了通信鏈路丟失概率對吞吐的影響，提出了兩種方法解決最大化吞吐問題。然而基于TDMA的通信方式，無線供能傳感網(wǎng)絡(luò)在上行的同一時刻只能有一個傳感器節(jié)點(diǎn)發(fā)送信號。這種方式不能充分地利用無線頻譜。為了提高頻譜利用率和系統(tǒng)吞吐，可采用多信號同傳方式。然而，這種方式會造成傳輸信號間的互干擾。為了消除互干擾對吞吐性能的影響，基于相繼干擾消除的多信號檢測技術(shù)被廣泛關(guān)注。相繼干擾消除技術(shù)是一種操作方便而且魯棒性很強(qiáng)的干擾消除方法[16]。

文中結(jié)合相繼干擾消除方法，考慮無線供能傳感網(wǎng)絡(luò)中最大化吞吐問題。對問題進(jìn)行了數(shù)學(xué)建模，通過分析，給出了快速求解問題的方法。并通過仿真，發(fā)現(xiàn)吞吐量相比較無相繼干擾消除時，提升了至少30%。

1 系統(tǒng)模型

如圖1所示，一個基站和多個傳感器節(jié)點(diǎn)構(gòu)成了一個無線供能傳感網(wǎng)絡(luò)。基站通過下行廣播的無線信號為傳感器節(jié)點(diǎn)提供能量。傳感器節(jié)點(diǎn)將獲得的能量用于上行數(shù)據(jù)通信?；驹谏闲型ㄐ胖型ㄟ^相繼干擾消除技術(shù)對接收到的多個傳感器節(jié)點(diǎn)傳輸?shù)男畔⑦M(jìn)行依次解碼。

圖1 無線功能傳感網(wǎng)絡(luò)示意圖

假定基站有無限的能量來源，傳感器節(jié)點(diǎn)安裝有可充電的電池，下行收獲的能量存儲在電池中作為唯一的能量源。li表示傳感器節(jié)點(diǎn)和基站間形成的鏈路。Ν表示所有鏈路子集形成的集合。激活的傳感器節(jié)點(diǎn)i等同于鏈路li被激活。我們假定在一個時間塊T中，上行和下行的信道狀態(tài)保持不變。gi0和gi1分別表示傳感器節(jié)點(diǎn)i和基站之間上行和下行的信道增益。在不同的時間塊中，信道狀態(tài)可以不同。分別用P0和Pi表示基站和傳感器節(jié)點(diǎn)i的傳輸功率。則傳感器節(jié)點(diǎn)i在下行通信時間獲得的由基站傳輸?shù)哪茉纯捎孟率奖硎尽?/p>

其中ζi表示傳感器節(jié)點(diǎn)i的能源轉(zhuǎn)換效率，0＜ζi＜1,i=1,...,N。ηi表示傳感器節(jié)點(diǎn)i用于信息傳輸?shù)哪芰空际斋@能量的比值。假定所有的能量都用于信息傳輸。因此，ηi=1，i=1,2,...,N，tdown是時間塊中的下行通信時間。

傳感器節(jié)點(diǎn)在下行通信時間tdown結(jié)束后，開始上行數(shù)據(jù)傳輸。由于硬件的要求，啟用連續(xù)干擾消除基站的解碼能力是有限的。假定干擾消除解碼能力為L，換言之，基站在一個時間槽內(nèi)解碼的信號數(shù)量不能超過L。上行通信時間被劃分成多個時間槽，受解碼能力限制，每個時間槽內(nèi)不超過L個傳感器節(jié)點(diǎn)可處于激活狀態(tài)，其余傳感器節(jié)點(diǎn)則進(jìn)入睡眠狀態(tài)。用C表示N個鏈路的子集組成的集合，這些子集包含的元素不超過L。用c表示C中的成員。組c表示c中的所有鏈路在同一時間槽內(nèi)處于激活。因此鏈路li1的信號干擾噪聲比SINRi可表示為。

其中δ2表示噪聲功率。在連續(xù)干擾消除過程中，已解碼的信號對后續(xù)解碼信號不被視為干擾。s(i)表示傳感器節(jié)點(diǎn)的一個子集，子集中的傳感器節(jié)點(diǎn)發(fā)送的信號先于傳感器節(jié)點(diǎn)i的信號解碼。則組c中的傳感器節(jié)點(diǎn)i可靠的最大速率可表示vi=Wlog(1+SINRi)，W為帶寬，log為二進(jìn)制對數(shù)。則組c的總速率vc可表示為。

由式（3）得，組c的傳輸速率不會隨信號解碼的順序不同而改變。tc表示組c在上行通信中的運(yùn)行時間。所有tc之和為上行通信總時間tup。Pjc表示傳感器節(jié)點(diǎn)在組c激活時的傳感器節(jié)點(diǎn)j的傳輸功率。如果鏈路lj1是組c的一個元素，則Pjc=Pj，否則Pjc=0。將時間塊T標(biāo)準(zhǔn)化為單位時間。不失一般性，確保每個傳感器節(jié)點(diǎn)能分配到上行時間和基站進(jìn)行通信，用ε表示每個傳感器節(jié)點(diǎn)最小的上行通信時間。則最大化吞吐問題可以建立為如下模型。

目標(biāo)函數(shù)是求系統(tǒng)最大吞吐，約束條件式（4）保證總的傳輸時間和能量收獲時間不大于單位時間。約束條件式（5）中的第j個不等式限制了傳感器節(jié)點(diǎn)傳輸?shù)目偰芰坎荒艽笥谙滦械氖斋@能量。約束條件式（6）保證至少每個傳感器節(jié)點(diǎn)的上行通信時間占總的上行時間的比例不小于閾值ε。其中tc和tdown都為非負(fù)變量。

盡管模型為線性規(guī)劃模型，但時間復(fù)雜度跟傳感器節(jié)點(diǎn)的數(shù)量有關(guān)。當(dāng)傳感器節(jié)點(diǎn)數(shù)量很大時，很難用現(xiàn)有的求解軟件進(jìn)行計算。列生成方法是一種有效解決大規(guī)模問題的方法。我們利用列生成方法對[M1]進(jìn)行了有效求解。

2 列生成方法的基本原理

列生成方法的主要思想：對含有大規(guī)模線性規(guī)劃問題，將原問題劃分為主問題和子問題。主問題只通過解含有已知部分列的約束矩陣的規(guī)劃模型。通過主問題的求解可以獲得原問題的一個可行解。但這個可行解并不一定為原問題的最優(yōu)解。檢驗主問題所得到的可行解是否為最優(yōu)解或是否能產(chǎn)生新的進(jìn)基列，需要對子問題進(jìn)行求解。若子問題能夠找到改進(jìn)原問題當(dāng)前解的進(jìn)基列，則進(jìn)行主問題和子問題的循環(huán)迭代，直到無法找到進(jìn)基列為止。

2.1 主問題

用Q表示已知的列集，q∈Q?{1,2,...,Q}，表示集合中每列的索引號。則最大化吞吐問題的主問題可由[M2]模型表示。

模型[M2]與[M1]類似，目標(biāo)函數(shù)為最大化吞吐。求解[M2]，可得原問題的一個可行解。然而當(dāng)前的可行解是否為原問題的最優(yōu)解，需通過計算其余備選列c∈C/Q的判別數(shù)大小確定是否為最優(yōu)解。如果備選列中每一列的判別數(shù)大小都為負(fù)，則當(dāng)前的解為最優(yōu)解，否則不是。備選列c的判別數(shù)大小可由下式表示。

通過式（7）確定當(dāng)前解是否為最優(yōu)。然而需要每次迭代都搜尋一遍全部的備選列。為了更快更有效的確定當(dāng)前解是否為最優(yōu)解以及是否備選列中存在可以改善當(dāng)前解的進(jìn)基列，可通過子問題來解決此問題。

2.2 子問題

子問題的目標(biāo)是找一個具有正判別數(shù)的列，如果在備選列中可以找到，則主問題的當(dāng)前解不是原問題的最優(yōu)解，且可以找到一個進(jìn)基列繼續(xù)改進(jìn)原問題解的質(zhì)量。

為了建立子問題的模型，我們引入N個二元變量rj∈{0,1}，?j∈N。如果lj1激活，rj為1，否則為0，子問題可被表示成如下形式

目標(biāo)函數(shù)為最大化判別數(shù)。約束式（19）保證激活的鏈路數(shù)不大于最大解碼數(shù)L。求解模型，找到判別數(shù)最大的列，若最大列的判別數(shù)為負(fù)，則整個備選列不存在判別數(shù)為正的，當(dāng)前解為最優(yōu)解。模型為非線性規(guī)劃，實際中求解非線性規(guī)劃模型非常困難。利用啟發(fā)式算法可以有效快速的求解子問題。

2.3 啟發(fā)式算法

啟發(fā)式算法的主要核心思想是相繼添加鏈路到一個空集合S中，其添加的順序按照判別數(shù)大小進(jìn)行選擇。每一次選擇，分別添加所有鏈路到S中，計算對應(yīng)的S的判別數(shù)大小，選取其中一個對應(yīng)S判別數(shù)最大的鏈路。直到S不能再添加鏈路為止。啟發(fā)式算法的偽代碼如圖2所示。

圖2 啟發(fā)式算法偽代碼

每一次迭代中（第2行到第10行），添加備選集合A中的每個鏈路進(jìn)入集合S并計算相應(yīng)的判別數(shù)。如果判別數(shù)大于下界，則更新下界（第7行）。經(jīng)過一次迭代后，選擇出一條鏈路。然后，將鏈路添加到集合S中并將其從集合A中撤銷掉。當(dāng)前集合S的判別數(shù)大小可通過第5行求出。算法結(jié)束于第12行或16行，當(dāng)沒有鏈路可以改變下界或L次循環(huán)完成。顯然，啟發(fā)式算法的復(fù)雜度在最壞情況下為O(NL)。

3 仿真及結(jié)果分析

假定N個傳感器節(jié)點(diǎn)隨機(jī)地分布在以基站為圓心和半徑為10 m的圓內(nèi)。設(shè)定基站的傳輸功率和傳感器節(jié)點(diǎn)的傳輸功率分別為30 dBm和-10 dBm。帶寬設(shè)置為10 MHz。噪聲功率δ2為-50 dBm。假定信道小尺度衰落服從瑞利分布，則信道增益可表示為。是一個均值為1服從指數(shù)分布的隨機(jī)變量。α為路徑丟失指數(shù)。能源收獲的效益ζ=ζi，i=1,2,...,N設(shè)為0.5。傳感器節(jié)點(diǎn)i和基站的距離di=max{1,d}。假定1 m參考信號的平均信號衰減為30 dB。每次仿真運(yùn)行50個實例。

用“MT-OPT”，“MT-TDMA”和“MT-SIC”分別表示[M1]，無連續(xù)干擾消除，基于連續(xù)干擾消除的列生成算法的解。

首先，設(shè)定干擾消除能力為5，傳感器節(jié)點(diǎn)的數(shù)目分別為{5，10，15，20，25}。系統(tǒng)的吞吐性能與節(jié)點(diǎn)數(shù)目的關(guān)系如圖3所示，加入連續(xù)干擾消除與無干擾消除的時間多分復(fù)用接入比較，可增加約30%的吞吐?；趩l(fā)式的列生成算法解與最優(yōu)解相差小于0.7%。說明列生成算法有非常好的魯棒性。隨著傳感器節(jié)點(diǎn)的增加，加入連續(xù)干擾消除相比無干擾消除最大可以增大吞吐達(dá)60%。因此，在密集型傳感器網(wǎng)絡(luò)中，采用連續(xù)干擾消除對系統(tǒng)吞吐影響更大。

其次，設(shè)定傳感器數(shù)目為20，考慮連續(xù)干擾消除的解碼能力對吞吐的影響，設(shè)定L={1，2，3，4，5}。如圖4所示，增大L使得更多的傳感器節(jié)點(diǎn)可以在同一時間槽內(nèi)激活，即使連續(xù)干擾消除解碼能力為2，平均吞吐相比解碼能力為1（無干擾消除的時間多分復(fù)用方式）增大72%，隨著解碼能力L每增大1，提升的吞吐可達(dá)50%。

圖3 傳感器節(jié)點(diǎn)數(shù)目與吞吐量關(guān)系示意圖

圖4 吞吐量與解碼能力關(guān)系示意圖

4 結(jié) 論

文中研究了無線供電傳感網(wǎng)絡(luò)的最大化吞吐問題，對問題建立了線性模型。并提出了利用列生成算法對模型進(jìn)行了有效求解。針對列生成算法中子問題的整數(shù)規(guī)劃模型，提出了可快速求解子問題的啟發(fā)式算法。最后通過仿真發(fā)現(xiàn)，加入連續(xù)干擾消除能夠增大系統(tǒng)吞吐。基于啟發(fā)式的列生成算法在求解此問題中，具有很好的魯棒性和求解能力。

參考文獻(xiàn)：

[1]張明.具有能量收集功能的無線傳感器網(wǎng)絡(luò)最優(yōu)傳輸策略研究[D].南京：南京郵電大學(xué)，2014.

[2]韓建輝，亓東欣，張威，等.近場無線能量傳輸系統(tǒng)的效率研究[J].電子科學(xué)與工程，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.