能量收集型無(wú)線傳感器網(wǎng)絡(luò)中高效的能量調(diào)度算法

康亞威， 姚彥鑫

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100101)

0 引 言

能量收集技術(shù)使無(wú)線設(shè)備能夠從其環(huán)境中的自然資源中獲取所需的能量并儲(chǔ)存在電池中用于將來(lái)使用。這一技術(shù)使無(wú)線傳感器節(jié)點(diǎn)的使用壽命大大增加，且提高了能量的利用率[1]。現(xiàn)階段針對(duì)此技術(shù)的研究已經(jīng)成為一個(gè)新的研究熱點(diǎn)，如何高效利用儲(chǔ)存的能量成為一個(gè)亟待解決的問題。

由于能量收集具有隨機(jī)性的特點(diǎn)，能量收集通信系統(tǒng)與傳統(tǒng)的通信系統(tǒng)相比需要設(shè)計(jì)良好的能量調(diào)度策略，在隨機(jī)能量收集情況下使吞吐量最大化。傳輸過程中，可用能量不能消耗太快，否則可能會(huì)由于能量短缺使傳輸中斷。但是假如能量消耗得太慢，電池的能量會(huì)大量溢出，引起能量的浪費(fèi)以及錯(cuò)過下次能量收集機(jī)會(huì)[2-3]。此類問題在近期的文獻(xiàn)中得到了廣泛的研究。文獻(xiàn)中考慮的情形主要分為在線和離線兩部分。離線情況下，雖然現(xiàn)有的研究中提出計(jì)算最優(yōu)離線調(diào)度的算法[4-7]，但是此類算法計(jì)算量大；在線情況下，由于未來(lái)的能量到達(dá)為未知且隨機(jī)的，需要?jiǎng)討B(tài)地確定能量調(diào)度方案。

最佳的能量調(diào)度方案為傳輸功率隨時(shí)間保持恒定，同時(shí)確保不會(huì)由于電池容量有限而溢出[4]。文獻(xiàn)[5]中對(duì)于特定的馬爾科夫決策過程(Markov Decision Process, MDP)制定了最大化吞吐量的在線解決方案，文獻(xiàn)[6-7]中在此基礎(chǔ)上與動(dòng)態(tài)規(guī)劃相結(jié)合，研究了在衰落信道下吞吐量最大化的策略，但此類方案只是在特定模型下實(shí)現(xiàn)最優(yōu)，不能緊密貼合實(shí)際場(chǎng)景。而當(dāng)能量收集為全隨機(jī)模型時(shí)，文獻(xiàn)[8]中提出了一種應(yīng)用于一般遍歷的平穩(wěn)過程，證明電池趨于無(wú)窮大的漸進(jìn)最優(yōu)。文獻(xiàn)[9-10]中證明離線最優(yōu)解可以用多個(gè)不同的水位表示，并且將注水法與能量分配相結(jié)合，得出離線最優(yōu)策略。文獻(xiàn)[11]中考慮了能量傳輸成本，用凸優(yōu)化得出最優(yōu)策略，但上述策略的計(jì)算量都比較大，占用計(jì)算空間。文獻(xiàn)[12]中提出了一個(gè)更為簡(jiǎn)單的能量調(diào)度策略(Fixed Fraction Policy，F(xiàn)FP)，用于能量收集為獨(dú)立同分布(i.i.d.)時(shí)的情況，此策略被證明可以與最佳長(zhǎng)期平均吞吐量保持恒定的間隙，但此方案僅在能量到達(dá)符合獨(dú)立同分布(i.i.d.)時(shí)適用。此外，多用戶場(chǎng)景[13]以及MIMO信道預(yù)編碼策略[14]的離線優(yōu)化進(jìn)展明顯。

本文提出了一種簡(jiǎn)單高效的離線能量調(diào)度策略。假設(shè)能量到達(dá)呈周期性變化時(shí)，每個(gè)周期T看作一個(gè)傳輸階段，階段內(nèi)能量到達(dá)近似相等，各階段之間能量到達(dá)符合隨機(jī)模型。此模型近似可看作太陽(yáng)能能量收集情況，在一定時(shí)間內(nèi)太陽(yáng)能輻射近似不變，在下一時(shí)間段由于受到云層的遮擋等影響而隨機(jī)產(chǎn)生變化。本文結(jié)合了FFP算法簡(jiǎn)單高效的特點(diǎn)，針對(duì)其只適用于能量收集為(i.i.d.)的特點(diǎn)進(jìn)行了改進(jìn)。

1 系統(tǒng)模型

考慮具有能量收集的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)之間單信道的傳輸?shù)膱?chǎng)景，目標(biāo)是最大化系統(tǒng)運(yùn)行時(shí)期預(yù)期吞吐量。傳感器節(jié)點(diǎn)配備有限存儲(chǔ)容量的可充電電池。假設(shè)能量收集發(fā)生在每個(gè)時(shí)隙的開始，信道狀態(tài)保持恒定不變。每個(gè)傳輸階段共有T個(gè)時(shí)隙，每個(gè)時(shí)隙均進(jìn)行能量的收集和調(diào)度。用Ek表示在第k個(gè)階段的能量收集，且Ek在該階段的時(shí)隙保持不變。在第k階段的第i時(shí)隙結(jié)束時(shí)，數(shù)據(jù)到達(dá)發(fā)射機(jī)，發(fā)射機(jī)通過收集并存儲(chǔ)的能量進(jìn)行數(shù)據(jù)傳輸，數(shù)據(jù)通過靜態(tài)信道傳輸至接收機(jī)，如圖1所示。

圖1 具有能量收集和數(shù)據(jù)到達(dá)的EH通信系統(tǒng)

(1)

0≤Ek≤B，k=1,2,…,K

(2)

式中：W為信道的帶寬；N0為高斯信道的噪聲功率譜密度。對(duì)于策略集合P，可以定義當(dāng)總傳輸時(shí)間為N，且能量收集為E1,E2,…,EN時(shí)的總吞吐量為

則同一策略的長(zhǎng)期平均吞吐量可定義為

(3)

本文的目標(biāo)是得出最優(yōu)的離線能量調(diào)度策略以及最大吞吐量，即

(4)

2 算法實(shí)現(xiàn)

由于恒定功率傳輸數(shù)據(jù)，且能量沒有溢出時(shí)系統(tǒng)吞吐量最大，根據(jù)FFP策略的理論證明，對(duì)于時(shí)隙t中電池的現(xiàn)有能量bt取固定的比例q(q∈[0,1])的能量進(jìn)行數(shù)據(jù)傳輸可實(shí)現(xiàn)次最優(yōu)的實(shí)驗(yàn)效果，其離線策略pt表示為

pt=qbt,t=1,2,…

(5)

結(jié)合本文的模型，當(dāng)能量收集Ek

(6)

由式(6)得出在傳輸階段k內(nèi)能量溢出的限制條件為

(7)

當(dāng)滿足此條件時(shí)，可以將第k階段T時(shí)隙的電池狀態(tài)表示為

(8)

根據(jù)式(7)以及(8)可得出當(dāng)能量溢出時(shí)，能量的調(diào)度策略為

(9)

為表示方便，將Q定義為

(10)

(11)

(12)

由式(9)與(11)得出qk的表達(dá)式為

(13)

當(dāng)滿足式(13)時(shí)，qk的取值可以確定在當(dāng)前傳輸階段能量不發(fā)生溢出，即滿足式(7)的限制條件。

(14)

根據(jù)式(7)且已知能量收集分布，可以將qk取值范圍表示為

(15)

k=1,2,…,K-1

根據(jù)能量收集的分布模型，結(jié)合式(13)以及(15)建立qk的取值范圍如下：

(16)

當(dāng)進(jìn)行到傳輸最后一個(gè)階段，即第K階段時(shí)，能量溢出的條件為式(7)，則制定新的能量調(diào)度策略，將此階段按照恒定功率的策略進(jìn)行傳輸數(shù)據(jù)，其傳輸策略為：

(17)

綜上，本文的能量收集模型建立以下的能量調(diào)度策略：

(18)

3 仿真實(shí)現(xiàn)

為了驗(yàn)證文中能量調(diào)度策略的性能，將本文算法與最優(yōu)離線算法[4]和貪婪算法[15]進(jìn)行對(duì)比。為了便于表示，將改進(jìn)的FFP算法設(shè)為方法1，最優(yōu)離線算法設(shè)為方法2，貪婪算法設(shè)為方法3。

3.1 吞吐量分析

在數(shù)值分析中，使用基于IEEE802.15.4e[16]通信系統(tǒng)的參數(shù)。將傳輸階段長(zhǎng)度設(shè)定為1 h，每個(gè)階段共有T=5個(gè)時(shí)隙，每個(gè)時(shí)隙時(shí)間為12 min，可用帶寬W=1 MHz。電池容量B=36 MJ，信道的增益為H=1.655×10-13，噪聲功率密度N0=10-20.4W/Hz，則根據(jù)式(3)可計(jì)算吞吐量。能量到達(dá)分布為太陽(yáng)能輻射監(jiān)測(cè)實(shí)驗(yàn)室網(wǎng)站下載的現(xiàn)實(shí)數(shù)據(jù)，此數(shù)據(jù)近似符合本文的能量收集分布模型。將能量數(shù)據(jù)對(duì)3個(gè)算法分別進(jìn)行仿真，其太陽(yáng)能能量收集分布如圖2所示。

圖2 能量到達(dá)分布圖

將傳輸階段分為k=20個(gè)階段，在數(shù)據(jù)傳輸過程中，對(duì)能量收集的分布使用方法1與方法2進(jìn)行傳輸，兩種算法在傳輸階段內(nèi)的總吞吐量與階段數(shù)的關(guān)系如表1所示。

表1 方法1吞吐量占方法2的比例

由圖3可以清晰地得出方法1具有高效的傳輸效率，在整個(gè)傳輸階段中，方法1的吞吐量曲線緊貼方法2。當(dāng)傳輸階段k=20時(shí)，方法2的吞吐量比方法1高0.01 GB。根據(jù)表1可得出方法1在能量隨機(jī)變化的情況下，傳輸效率保持穩(wěn)定，吞吐量約占方法2的99%左右。

圖3 方法1與方法2吞吐量對(duì)比

根據(jù)圖4得出，方法1的策略整體上跟隨方法2的變化趨勢(shì)，能量利用率均為100%，但是曲線的趨勢(shì)仍有背離的部分，例如時(shí)隙t=1～10的部分，方法2保持恒定傳輸，方法1則出現(xiàn)波動(dòng)，這就是方法1與方法2吞吐量出現(xiàn)差距的原因。

圖4 方法1與方法2傳輸功率對(duì)比

其他仿真條件不變，根據(jù)能量到達(dá)分布，將方法1與方法3進(jìn)行對(duì)比，其仿真結(jié)果如圖5所示。

圖5 方法1與方法3吞吐量對(duì)比

由圖5可得，方法1相對(duì)方法3吞吐量具有明顯的提升，在傳輸階段中，雖然方法3的吞吐量曲線與方法1的軌跡大致相同，但是吞吐量差距很大。當(dāng)傳輸階段k=20 時(shí)，方法1的吞吐量比方法3提升0.178 GB。根據(jù)表2可得出方法1其吞吐量較方法3至少提升110%。

表2 方法1吞吐量較方法3吞吐量的提升

根據(jù)圖6可得兩種算法的傳輸功率趨勢(shì)大致相同，能量利用率均為100%。但是當(dāng)太陽(yáng)能能量到達(dá)為0時(shí)，方法1為恒定的非0的功率，而方法3的對(duì)應(yīng)時(shí)隙的功率則為0，此為方法1與方法3吞吐量出現(xiàn)明顯優(yōu)勢(shì)的主要原因。

圖6 方法1與方法3傳輸功率對(duì)比

圖7展示了電池電量B對(duì)預(yù)期數(shù)據(jù)傳輸總量的影響。可見，對(duì)于所提出的算法，預(yù)期數(shù)據(jù)傳輸總量隨電池容量B增加而增大。總的來(lái)說(shuō)，方法1的性能約是方法2的99%。

圖7 電池大小對(duì)吞吐量的影響

3.2 計(jì)算量分析

(2) 方法2計(jì)算量。設(shè)電池共M個(gè)狀態(tài)，即單個(gè)階段傳輸功率可有M種情況。方法2類似于用窮舉法將每個(gè)階段可能的傳輸功率情況進(jìn)行枚舉，找出在有限長(zhǎng)的傳輸階段下最優(yōu)的傳輸策略。當(dāng)傳輸階段為k=N時(shí)，方法2中加法的計(jì)算次數(shù)為2NM，乘法的計(jì)算次數(shù)為4NM，對(duì)數(shù)運(yùn)算的計(jì)算次數(shù)為NM。

(3) 計(jì)算量對(duì)比分析。相對(duì)來(lái)說(shuō)，對(duì)數(shù)運(yùn)算的計(jì)算量要大于乘法運(yùn)算，加法運(yùn)算的計(jì)算量最小。因此，只考慮乘法和對(duì)數(shù)運(yùn)算。當(dāng)電池狀態(tài)數(shù)M=4時(shí)，方法2的計(jì)算量就必定大于方法1，可以得出電池的狀態(tài)不僅僅只有4種，當(dāng)電池的狀態(tài)越多時(shí)，方法1計(jì)算量降低便會(huì)越大，大大提高了策略的時(shí)效性，節(jié)省了計(jì)算空間。

為了比較方法1與方法2在運(yùn)算時(shí)間上的差距，首先設(shè)定電池的狀態(tài)數(shù)M，而后對(duì)算法中運(yùn)算的時(shí)間進(jìn)行對(duì)比。由表3的數(shù)據(jù)分析得知，隨著電池狀態(tài)的增加，方法1運(yùn)算時(shí)間幾乎不變，而方法2的運(yùn)算時(shí)間增長(zhǎng)迅速。由此可得出，當(dāng)電池狀態(tài)越多時(shí)，方法1更加節(jié)省計(jì)算量以及運(yùn)算時(shí)間。

表3 兩種算法運(yùn)算時(shí)間 s

4 結(jié) 語(yǔ)

本文考慮了能量隨機(jī)收集的通信系統(tǒng)，其中發(fā)射機(jī)具有能量收集裝置和有限容量的電池。當(dāng)信道為靜態(tài)信道時(shí)，著力對(duì)傳輸階段總傳輸數(shù)據(jù)最大化問題進(jìn)行了研究。針對(duì)離線優(yōu)化問題，對(duì)文中所述能量收集模型的功率控制在原有FFP算法的基礎(chǔ)上進(jìn)行了改進(jìn)，確定了次最優(yōu)的傳輸策略。其性能可以達(dá)到最優(yōu)離線算法的99%，比傳統(tǒng)的貪婪策略性能至少提升約110%，并且分析了改進(jìn)的FFP算法與其他算法產(chǎn)生吞吐量差異的原因。最后，進(jìn)行了計(jì)算量與算法運(yùn)算時(shí)間的對(duì)比，下一步的研究工作是在此基礎(chǔ)上找到最優(yōu)的在線能量調(diào)度策略。