基于中繼狀態(tài)調(diào)度的無線傳感網(wǎng)絡(luò)低能量算法

聶韶華

(臨沂大學(xué) 計算機學(xué)院，山東 臨沂 276000)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)通過多個小型的低成本傳感器節(jié)點組成，可以以投放等方式隨機部署在地形復(fù)雜的區(qū)域，節(jié)點在有限的感測范圍內(nèi)采集數(shù)據(jù)，并以多跳的方式將數(shù)據(jù)匯聚到終端[1,2]。由于節(jié)點的感測半徑有限，為了擴(kuò)展無線傳感器網(wǎng)絡(luò)的覆蓋面積，并在能量有限的條件下盡可能地延長網(wǎng)絡(luò)的工作壽命，在目前的傳感器網(wǎng)絡(luò)研究中，人們采用了中繼傳輸方式，將網(wǎng)絡(luò)的部分節(jié)點作為中繼節(jié)點，中繼節(jié)點作為鄰近節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)站點，負(fù)責(zé)與其它中繼節(jié)點通信或與匯聚端直接通信，保證各節(jié)點采集到的數(shù)據(jù)傳送至匯聚端。中繼節(jié)點在鄰近節(jié)點所構(gòu)成的集群中充當(dāng)著簇頭的作用[3,4]。由于集群中的節(jié)點只需要與中繼節(jié)點保持通信，不需要與其它多個節(jié)點保持通信，因此加入中繼節(jié)點后，每個集群的覆蓋面積得到了提升，而且數(shù)據(jù)聚合的方式節(jié)省了集群中節(jié)點更多的傳輸能耗。由于節(jié)點投放的環(huán)境復(fù)雜，一般采用電池供電，因此對節(jié)點進(jìn)行能量控制很有必要[5,6]。在中繼網(wǎng)絡(luò)中，中繼節(jié)點相比集群內(nèi)的傳感器節(jié)點具有更大的能量消耗量，因此在本文中對能耗控制研究主要集中在中繼節(jié)點，本文提出的能量感知協(xié)議對中繼節(jié)點進(jìn)行狀態(tài)調(diào)度，根據(jù)任務(wù)要求使得中繼節(jié)點在運行和休眠狀態(tài)中切換，根據(jù)能量消耗最小化為目標(biāo)，自適應(yīng)地調(diào)度中繼節(jié)點的動作狀態(tài)。

對于中繼無線傳感器網(wǎng)絡(luò)能量問題的研究，關(guān)注中繼節(jié)點選擇方式的算法較多，這些算法在提升中繼無線網(wǎng)絡(luò)的能量效率上取得了一定成果，例如Sheng等[7]提出的一種中繼無線多媒體網(wǎng)絡(luò)節(jié)能中繼選擇算法，該算法的特點是通過優(yōu)化協(xié)同傳輸?shù)淖g碼和轉(zhuǎn)發(fā)來減少總能耗，對于中繼節(jié)點的選擇采用的是一種節(jié)能中繼選擇規(guī)則，該規(guī)則主要考慮節(jié)點的功率效率方面，雖然會帶來額外的帶寬開銷，但在均衡節(jié)點能耗上具有一定優(yōu)勢。Lee等[8]提出的一種基于能量感知的多接口無線傳感器網(wǎng)絡(luò)中繼選擇和路由算法，該算法的特點是采用了一種高性價比的中繼節(jié)點選擇方式，選擇的中繼節(jié)點能夠在數(shù)據(jù)傳輸所需的最低能量限度下，以較短的時間期限完成數(shù)據(jù)傳輸任務(wù)。雖然選擇的路由可能使得個別節(jié)點的能量負(fù)擔(dān)加大，但在網(wǎng)絡(luò)的能量效率上得到了進(jìn)一步的提升。本文在實驗部分將與這兩種算法進(jìn)行能量性能的對比，進(jìn)一步評估基于中繼狀態(tài)調(diào)度的方法在提高網(wǎng)絡(luò)能量效率上的有效性。

1 系統(tǒng)模型

圖1 雙層系統(tǒng)模型

圖2 節(jié)點i的時間幀t

根據(jù)各狀態(tài)給定的功率值和持續(xù)時間，每一個中繼節(jié)點i在時間幀內(nèi)所消耗的能量值為

(1)

(2)

由于狀態(tài)調(diào)度的目的是最小化能量成本，本文采用二次成本函數(shù)來表示狀態(tài)調(diào)度問題，得到單位幀內(nèi)中繼節(jié)點的最小化總能量方程

(3)

由于網(wǎng)絡(luò)的衰落信道隨時間而變化，因此考慮到信道增益λi是一個隨機變量，時間幀是相對于λi的期望，本文將中繼節(jié)點的最小化總能量方程轉(zhuǎn)化為

(4)

式中：Υλi是相對于λi的期望。

2 基于能量最小化的中繼狀態(tài)調(diào)度算法

式(4)是包含了對中繼節(jié)點狀態(tài)和時間幀的聯(lián)合優(yōu)化調(diào)度，為了尋找整體的解決方案，在本節(jié)中采用雙分解來解決聯(lián)合優(yōu)化問題[10]，首先形成式(4)的拉格朗日函數(shù)

(5)

式中：C表示原始變量，a≥0，b≥0，ω是拉格朗日乘子，相對于原始變量C的優(yōu)化會產(chǎn)生一個對偶函數(shù)

(6)

該函數(shù)為尋找式(4)的最佳解決方案提供了一個下限，該下限可以通過對偶問題得到

(7)

對式(5)、式(6)采用表達(dá)式分解轉(zhuǎn)化為

(8)

(9)

其中，Hi(a,b,ω)的表達(dá)式為

(10)

(11)

(12)

(13)

(14)

(1)Initialization:t=0,a0,b0,ωi,0，i∈N

(2)Whilet∈Tdo

(3)fori∈Ndo

(5)nodeiupdatesωi,t

(6)end for

(7)Sink updatesatandbtand then broadcast to nodei

3 實驗結(jié)果

為了驗證中繼狀態(tài)調(diào)度算法在無線傳感器網(wǎng)絡(luò)能量效率上所表現(xiàn)出的性能，實驗部分主要采用對比分析的方法來進(jìn)行算法性能評估，并對算法的性能進(jìn)行了定量的比較和分析，其中，對統(tǒng)計量的定義有如下幾個方面：

(15)

式中：Ej表示節(jié)點j的能耗，用M表示網(wǎng)絡(luò)的節(jié)點數(shù)，Crec表示匯聚節(jié)點成功接收到的數(shù)據(jù)分組數(shù)量。

(2)數(shù)據(jù)包丟失率。用φ表示

(16)

式中：CV——源節(jié)點發(fā)送的數(shù)據(jù)分組總數(shù)量。

(3)網(wǎng)絡(luò)壽命。由于節(jié)點死亡會對網(wǎng)絡(luò)鏈路造成影響，影響網(wǎng)絡(luò)的正常運行，因此在本文實驗中以第一個節(jié)點的死亡時間減去網(wǎng)絡(luò)初始運行的時間作為網(wǎng)絡(luò)的生命壽命。

算法的軟件仿真平臺采用的是OPNET14.5，其它仿真參數(shù)見表1，仿真過程中各算法的仿真環(huán)境一致。

表1 仿真環(huán)境參數(shù)

在圖3所進(jìn)行的實驗中，隨著網(wǎng)絡(luò)節(jié)點個數(shù)的增加，網(wǎng)絡(luò)的數(shù)據(jù)分組平均能耗量也逐漸提升。與節(jié)能中繼選擇算法和基于能量感知的中繼選擇算法相比，采用中繼狀態(tài)調(diào)度算法時網(wǎng)絡(luò)的數(shù)據(jù)分組平均能耗有所降低。以該實驗中參與仿真的網(wǎng)絡(luò)節(jié)點個數(shù)為60個為例，采用中繼狀態(tài)調(diào)度算法時，數(shù)據(jù)分組平均能耗量對比另外兩種算法分別減少了(0.000513J-0.000472J)/0.000513J≈8.0%、(0.000563J-0.000472J)/0.000563J≈16.2%。節(jié)能中繼選擇算法雖然通過譯碼減少了轉(zhuǎn)發(fā)量，中繼的優(yōu)先選擇也減少了傳輸能耗，但中繼狀態(tài)調(diào)度算法在保證數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)正常執(zhí)行的條件下最小化了節(jié)點的活躍期，使節(jié)點在網(wǎng)絡(luò)壽命期間用于發(fā)送/接收的能耗更小?；谀芰扛兄闹欣^選擇算法雖然縮短了單個數(shù)據(jù)任務(wù)的傳輸時間，但隨著網(wǎng)絡(luò)節(jié)點的增多，網(wǎng)絡(luò)的數(shù)據(jù)流量相應(yīng)提升，單位時間內(nèi)的任務(wù)完工時間越短，意味著單位時間內(nèi)處理的數(shù)據(jù)分組數(shù)量越多，節(jié)點的平均能耗相比前兩種算法就更大。

圖3 數(shù)據(jù)分組平均能耗量比較

圖4顯示了3種算法的數(shù)據(jù)分組丟失率隨著網(wǎng)絡(luò)節(jié)點數(shù)的不同而變化的情況?？梢钥闯觯?種算法都保持著較低的數(shù)據(jù)分組丟失率，整個仿真過程中都低于1.25%。其中，中繼狀態(tài)調(diào)度算法隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增多，其數(shù)據(jù)分組丟失率并不會產(chǎn)生較大的變化，由于算法包含了單位時間內(nèi)接收數(shù)據(jù)位的平均數(shù)量約束，因此當(dāng)網(wǎng)絡(luò)總數(shù)據(jù)量增多時，數(shù)據(jù)包碰撞概率仍然較低。節(jié)能中繼選擇算法由于傳送的控制分組數(shù)量明顯提升，在信道競爭激烈的情況下數(shù)據(jù)分組的丟失率逐漸升高。

圖4 數(shù)據(jù)分組丟失率比較

圖5顯示了3種算法的網(wǎng)絡(luò)壽命隨著網(wǎng)絡(luò)節(jié)點數(shù)的不同而變化的情況。從圖中可以看出，節(jié)能中繼算法的平均網(wǎng)絡(luò)壽命最長，以該實驗中參與仿真的網(wǎng)絡(luò)節(jié)點個數(shù)為60個為例，網(wǎng)絡(luò)壽命達(dá)到了3952 s，中繼狀態(tài)調(diào)度算法達(dá)到了3875 s，基于能量感知的中繼選擇算法達(dá)到了3712 s。由于節(jié)能中繼算法在選擇中繼節(jié)點時是以節(jié)點能量剩余量作為一個重要的選擇指標(biāo)，因此節(jié)點的能量均衡程度更好，節(jié)點的存活時間更長。但當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)量增加到100個時，采用中繼狀態(tài)調(diào)度的方法可以得到更長的網(wǎng)絡(luò)壽命，由于節(jié)點數(shù)量的增多帶來了更多的網(wǎng)絡(luò)數(shù)據(jù)流量，即使節(jié)能中繼算法能夠使得節(jié)點能量均衡，但總能耗增多的條件下每個節(jié)點的能量負(fù)載都會增大。因此，當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)量較多時，網(wǎng)絡(luò)總能耗越低，對提高網(wǎng)絡(luò)壽命來說越有利。

圖5 網(wǎng)絡(luò)壽命比較

4 結(jié)束語

在研究無線傳感器網(wǎng)絡(luò)的能量問題上，本文以能量消耗最小化為目標(biāo)，采用一種中繼狀態(tài)調(diào)度的方法來減少中繼節(jié)點在空閑階段所消耗的能量，提升節(jié)點的能量利用效率。該方法在優(yōu)化節(jié)點能量上所體現(xiàn)出的重要特點，是最大化地延長了空閑節(jié)點的休眠期，盡可能地減少了節(jié)點能量的流失。從實驗部分各算法的數(shù)據(jù)分組平均消耗能量、數(shù)據(jù)包丟失率和網(wǎng)絡(luò)壽命的對比情況來看，基于中繼狀態(tài)調(diào)度的無線傳感器網(wǎng)絡(luò)在提高節(jié)點能量效率和網(wǎng)絡(luò)壽命、提高傳輸數(shù)據(jù)的穩(wěn)定性上具有較好效果。在接下來的工作中，我們將進(jìn)一步研究移動中繼網(wǎng)絡(luò)的能量問題，為實現(xiàn)更低功耗的移動傳感器網(wǎng)絡(luò)創(chuàng)造條件。