基于列生成法的無線供電傳感網最大化系統吞吐

徐志偉，裴清福

（陜西鐵路工程職業技術學院電氣與信息工程系，陜西渭南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.