謝小軍，于 浩，陶 磊，張信明

(1.國(guó)家電網(wǎng)安徽省電力公司 信息通信分公司， 合肥 230061； 2.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230027)

可充電無(wú)線傳感網(wǎng)絡(luò)能量均衡路由算法

謝小軍1，于 浩1，陶 磊2，張信明2*

(1.國(guó)家電網(wǎng)安徽省電力公司 信息通信分公司， 合肥 230061； 2.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230027)

(*通信作者電子郵箱xinming@ustc.edu.cn)

針對(duì)可充電無(wú)線傳感網(wǎng)絡(luò)中的能量均衡路由問(wèn)題，提出在穩(wěn)定功率無(wú)線充電和監(jiān)測(cè)數(shù)據(jù)收集網(wǎng)絡(luò)場(chǎng)景下的多路徑路由算法和機(jī)會(huì)路由算法，以實(shí)現(xiàn)網(wǎng)絡(luò)的能量均衡。首先，通過(guò)電磁傳播理論構(gòu)建了無(wú)線傳感節(jié)點(diǎn)的充電和接收功率關(guān)系模型；然后,考慮網(wǎng)絡(luò)中無(wú)線傳感節(jié)點(diǎn)的發(fā)送能耗和接收能耗, 基于上述充電模型將網(wǎng)絡(luò)能量均衡的路由問(wèn)題轉(zhuǎn)化為網(wǎng)絡(luò)節(jié)點(diǎn)運(yùn)行時(shí)間的最大最小化問(wèn)題，通過(guò)線性規(guī)劃得到的各鏈路流量用以指導(dǎo)路由中數(shù)據(jù)流量分配；最后，考慮一種更加現(xiàn)實(shí)的低功耗的場(chǎng)景，并提出了一種基于機(jī)會(huì)路由的能量均衡路由算法。實(shí)驗(yàn)結(jié)果表明，與最短路徑路由(SPR)和期望周期最短路由(EDC)算法相比較，所提出的兩種路由算法均能有效提高采集能量的利用率和工作周期內(nèi)的網(wǎng)絡(luò)生命周期。

能量均衡路由；可充電無(wú)線傳感網(wǎng)絡(luò)；機(jī)會(huì)路由；低功耗傳感網(wǎng)絡(luò)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)是由大規(guī)模的微型、智能傳感器節(jié)點(diǎn)組成無(wú)線自組織網(wǎng)絡(luò)系統(tǒng)，網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)相互協(xié)作將監(jiān)測(cè)到的數(shù)據(jù)信息傳送至網(wǎng)關(guān)(sink)節(jié)點(diǎn)進(jìn)行處理。無(wú)線傳感網(wǎng)中的節(jié)點(diǎn)能量有限，為了提升節(jié)點(diǎn)的運(yùn)行時(shí)間和網(wǎng)絡(luò)壽命，為無(wú)線傳感節(jié)點(diǎn)配備能量捕獲模塊和可充電電池，稱為可充電無(wú)線傳感節(jié)點(diǎn)。當(dāng)可充電無(wú)線傳感節(jié)點(diǎn)能夠捕獲的能量有限時(shí)，節(jié)點(diǎn)在能量耗盡前進(jìn)行網(wǎng)絡(luò)中的數(shù)據(jù)采樣、接收和傳輸?shù)日２僮鳎谀芰亢谋M后進(jìn)入低功耗模式睡眠狀態(tài)，此時(shí)，能量均衡路由關(guān)系到網(wǎng)絡(luò)中節(jié)點(diǎn)的可運(yùn)行時(shí)間，即網(wǎng)絡(luò)生命周期，仍然是該網(wǎng)絡(luò)中需要關(guān)注的重要問(wèn)題。本文研究可充電無(wú)線傳感網(wǎng)絡(luò)能量均衡路由問(wèn)題。

關(guān)于能量均衡路由，文獻(xiàn)[1]提出了一種基于混合傳輸?shù)哪芰烤夥椒ū苊鉄o(wú)線傳感網(wǎng)中的能量空洞。混合傳輸指網(wǎng)絡(luò)中節(jié)點(diǎn)的無(wú)線收發(fā)器具有不同傳輸功率。在數(shù)據(jù)收集傳感網(wǎng)網(wǎng)絡(luò)中，靠近sink節(jié)點(diǎn)的無(wú)線傳感器由于接收更多的來(lái)自遠(yuǎn)處傳感節(jié)點(diǎn)的數(shù)據(jù)會(huì)更快地耗盡能量，文獻(xiàn)[1]提出增大遠(yuǎn)處的節(jié)點(diǎn)的傳輸功率，同時(shí)概率地選擇傳輸?shù)慕邮展?jié)點(diǎn)，減小離sink較近節(jié)點(diǎn)的通信負(fù)載，推遲能量空洞的出現(xiàn)，延長(zhǎng)網(wǎng)絡(luò)壽命。文獻(xiàn)[2]提出一種簇規(guī)模自適應(yīng)調(diào)節(jié)的能量均衡分簇路由協(xié)議，協(xié)議改進(jìn)了低能耗自適應(yīng)集簇分層(Low Energy Adaptive Clustering Hierarchy, LEACH)算法[3]，根據(jù)節(jié)點(diǎn)離匯聚點(diǎn)的距離、剩余能量及分布密度來(lái)構(gòu)造規(guī)模不等的簇，避免了低能量節(jié)點(diǎn)被選為簇首，達(dá)到網(wǎng)絡(luò)能量均衡。文獻(xiàn)[4]提出一種基于學(xué)習(xí)自動(dòng)機(jī)的能量均衡分簇算法：綜合考慮節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)密度,利用學(xué)習(xí)自動(dòng)機(jī)與周圍環(huán)境進(jìn)行信息交互和動(dòng)作獎(jiǎng)懲，選擇出相對(duì)較優(yōu)的簇頭；根據(jù)簇首與基站距離和其節(jié)點(diǎn)密度構(gòu)造大小非均勻的簇，實(shí)現(xiàn)不同位置不同網(wǎng)絡(luò)疏密程度下簇內(nèi)和簇間能耗互補(bǔ)均衡，構(gòu)造了基于簇首剩余能量、簇內(nèi)節(jié)點(diǎn)密度和傳輸距離的評(píng)價(jià)函數(shù)，并運(yùn)用貪婪算法選擇出最優(yōu)中轉(zhuǎn)簇首進(jìn)行多跳傳輸。文獻(xiàn)[5]構(gòu)造了一種全局能量?jī)?yōu)化函數(shù)，并考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量情況，建立路由能耗和路由剩余能量的優(yōu)化度函數(shù)來(lái)評(píng)估對(duì)目標(biāo)函數(shù)的優(yōu)化程度，通過(guò)構(gòu)造優(yōu)化度函數(shù)的評(píng)價(jià)函數(shù)來(lái)求解多目標(biāo)優(yōu)化問(wèn)題，得到能量均衡的最優(yōu)路徑。

上述工作主要考慮自組織網(wǎng)絡(luò)中的能量均衡路由問(wèn)題，另一些研究將能量均衡路由和無(wú)線傳感節(jié)點(diǎn)的可充電特性結(jié)合起來(lái)考慮，如：文獻(xiàn)[6]提出了一種移動(dòng)充電模型和路由方法實(shí)現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)的成功數(shù)據(jù)上傳和能量均衡；文獻(xiàn)[7]提出另一種數(shù)據(jù)收集模型，當(dāng)移動(dòng)sink移動(dòng)到無(wú)線傳感節(jié)點(diǎn)附近時(shí)通過(guò)單跳或多跳的方式傳輸數(shù)據(jù)，綜合考慮了路徑規(guī)劃、數(shù)據(jù)路由和能量均衡問(wèn)題提出了一種綜合解決方案。

現(xiàn)有的相關(guān)工作關(guān)于能量均衡路由算法中，基于分簇的解決方案通常采用分布式算法，無(wú)法實(shí)現(xiàn)全局最優(yōu)；同時(shí)，某些能量模型[1,5]只考慮了節(jié)點(diǎn)傳輸能耗而忽略了接收能耗；路由算法計(jì)算的是最優(yōu)路徑，忽視了多路徑路由的可能性。針對(duì)上述模型和算法中存在的問(wèn)題，本文結(jié)合考慮了一種無(wú)線能量采集場(chǎng)景，提出基于鏈路流量分配多路徑路由算法和機(jī)會(huì)路由[10-11]算法，實(shí)現(xiàn)可充電傳感網(wǎng)絡(luò)的能量均衡，主要的工作在于：

1)在可預(yù)測(cè)的能量補(bǔ)充流的基礎(chǔ)上實(shí)現(xiàn)能量均衡路由；

2)利用機(jī)會(huì)路由應(yīng)對(duì)無(wú)線傳感網(wǎng)絡(luò)信道時(shí)變和丟失特性和其天然的負(fù)載均衡特性，達(dá)到能量均衡路由的目的；

3)使用更加精確的能量模型，考慮節(jié)點(diǎn)傳輸及接收能耗；

4)能量均衡路由算法是全局最優(yōu)的。

1 網(wǎng)絡(luò)模型與能量均衡問(wèn)題

1.1 可充電無(wú)線傳感器能量傳播模型

本文研究的基于高壓電線取電的可充電無(wú)線傳感器網(wǎng)絡(luò)中，取電、能量發(fā)射和接收裝置的原理如圖1所示，其中能量接收裝置與距離能量發(fā)射的距離由無(wú)線充電的方式所決定。不同的無(wú)線充電方式的傳輸距離、功率、頻率和充電效率也不相同。本文研究基于無(wú)線電波的充電方式，其有效充電距離可達(dá)數(shù)十米，適用于分布距離較大的無(wú)線傳感器網(wǎng)絡(luò)。首先研究單個(gè)取電-充電裝置對(duì)于多個(gè)無(wú)線傳感器節(jié)點(diǎn)的充電模型。在電能發(fā)射裝置通過(guò)連續(xù)發(fā)射電磁波給節(jié)點(diǎn)無(wú)線充電的過(guò)程中，由于電磁波在空間傳播時(shí)會(huì)產(chǎn)生衰減，這種衰減與發(fā)電裝置和傳感節(jié)點(diǎn)間的距離、傳播空間環(huán)境相關(guān)。

根據(jù)電磁傳播理論中的Friis傳輸公式，可以得到電磁波在理想空間中的傳輸特性?？臻g中任意一點(diǎn)處的電磁波功率P1與電磁波發(fā)射源發(fā)射功率P0的關(guān)系式如下：

P1=G1G0P0(λ/(4πd))2

(1)

其中：G1和G0分別表示接收天線和發(fā)射天線的增益；d表示接收點(diǎn)離發(fā)射源的距離；λ是傳輸?shù)碾姶挪ǖ牟ㄩL(zhǎng)。

圖1 能量獲取和發(fā)射裝置

1.2 無(wú)線傳感網(wǎng)絡(luò)機(jī)會(huì)路由模型

機(jī)會(huì)路由是一種適用于不可靠網(wǎng)絡(luò)的路由技術(shù)，它利用多個(gè)可能提供相似傳輸質(zhì)量的下一跳節(jié)點(diǎn)，可以顯著提高網(wǎng)絡(luò)吞吐量、減少傳輸次數(shù)和網(wǎng)絡(luò)能量消耗，并具有天然的負(fù)載均衡特性[10-11]。機(jī)會(huì)路由根據(jù)介質(zhì)訪問(wèn)控制(MediumAccessControl,MAC)協(xié)議的不同實(shí)現(xiàn)方式也有所變化，但最關(guān)鍵的部分是候選集的選擇。

候選集是由算法指定的有資格轉(zhuǎn)發(fā)數(shù)據(jù)包的下一跳節(jié)點(diǎn)集合。在非低功耗場(chǎng)景下，由于候選集中的節(jié)點(diǎn)收到數(shù)據(jù)包的概率大于一個(gè)節(jié)點(diǎn)收到數(shù)據(jù)包的概率，因此機(jī)會(huì)路由可利用無(wú)線網(wǎng)絡(luò)的廣播特性來(lái)提高數(shù)據(jù)包投遞的成功概率。在低功耗場(chǎng)景下，特別是節(jié)點(diǎn)的睡眠調(diào)度周期很長(zhǎng)時(shí)[10]，節(jié)點(diǎn)很少在同一時(shí)段處于活躍狀態(tài)，此時(shí)發(fā)送方通過(guò)依次單播給候選集中的節(jié)點(diǎn)需要傳輸?shù)臄?shù)據(jù)包，直到該跳傳輸成功為止。

1.3 可充電無(wú)線傳感網(wǎng)絡(luò)模型

假設(shè)一個(gè)基于周期性數(shù)據(jù)收集可充電無(wú)線傳感網(wǎng)絡(luò)G=(N,A,R),其中：N是所有無(wú)線傳感節(jié)點(diǎn)的集合，包括N-1個(gè)常規(guī)節(jié)點(diǎn)和1個(gè)網(wǎng)關(guān)節(jié)點(diǎn)，也稱為sink節(jié)點(diǎn)用于數(shù)據(jù)匯總和上傳至互聯(lián)網(wǎng)；A是所有節(jié)點(diǎn)間鏈路的集合，稱兩個(gè)無(wú)線傳感節(jié)點(diǎn)間有一條鏈路當(dāng)且僅當(dāng)它們互相在對(duì)方的傳輸范圍內(nèi)，此時(shí)這兩個(gè)節(jié)點(diǎn)也同時(shí)稱為對(duì)方的鄰居；R是電能采集和發(fā)射設(shè)備的集合。

1.4 問(wèn)題

在上述模型描述的可充電無(wú)線傳感器網(wǎng)絡(luò)中，由于無(wú)線傳感器的位置相對(duì)固定，在給定的各充電裝置的發(fā)射功率下，各傳感節(jié)點(diǎn)在每個(gè)觀察窗口內(nèi)能夠采集的能量可以預(yù)測(cè)且相對(duì)穩(wěn)定。在這種情況下，如果對(duì)于該數(shù)據(jù)收集的傳輸路徑設(shè)置不當(dāng)，容易造成網(wǎng)絡(luò)中的無(wú)線傳感器能量失衡。本文研究可充電無(wú)線傳感網(wǎng)中的傳輸(路由)問(wèn)題，以達(dá)到網(wǎng)絡(luò)能量的均衡，其重要性體現(xiàn)在：

1) 傳輸、接收數(shù)據(jù)包所消耗的能量與從無(wú)線電波中采集的能量均衡。如果消耗的能量速率大于采集能量速率，那么節(jié)點(diǎn)將會(huì)在有限的時(shí)間內(nèi)死亡；反之，節(jié)點(diǎn)的能量將會(huì)一直處于電池容量上限，浪費(fèi)了充電設(shè)備所發(fā)射的能量。

2) 網(wǎng)絡(luò)中各無(wú)線傳感節(jié)點(diǎn)之間的能量均衡。

如果上述條件無(wú)法滿足，則考慮如何最小化節(jié)點(diǎn)間的能量?jī)粝乃俾?，延長(zhǎng)網(wǎng)絡(luò)的生存周期。

2 能量均衡分析模型和路由算法

根據(jù)1.1節(jié)的充電損耗模型式(1)，假設(shè)網(wǎng)絡(luò)內(nèi)的每個(gè)無(wú)線傳感節(jié)點(diǎn)i在同一時(shí)刻只能由同一個(gè)充電設(shè)備為其充電，并令i在每個(gè)周期t內(nèi)選擇對(duì)其充電功率最大的為其充電。記傳感節(jié)點(diǎn)i和充電發(fā)射裝置r間的距離為di,k，則i在時(shí)段t內(nèi)的充電功率可通過(guò)式(2)推導(dǎo)得到：

(2)

即節(jié)點(diǎn)i轉(zhuǎn)發(fā)的流量是自身產(chǎn)生的流量和轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的流量之和。其數(shù)據(jù)流速率的形式為：

(3)

其中候選中繼集合Si代表i轉(zhuǎn)發(fā)數(shù)據(jù)的鄰居節(jié)點(diǎn)集合。數(shù)據(jù)流量均衡模型如圖2所示。

圖2 數(shù)據(jù)流量均衡模型

本文假設(shè)無(wú)線傳感節(jié)點(diǎn)以低功耗和頻率采集監(jiān)測(cè)數(shù)據(jù)，故忽略不計(jì)節(jié)點(diǎn)的數(shù)據(jù)采集功耗，則在t內(nèi)i的能量消耗速率為：

(4)

(5)

(6)

易知問(wèn)題一是一個(gè)關(guān)于變量qji(t)具有等式約束條件的max-min線性規(guī)劃(LinearProgramming,LP)問(wèn)題，求解問(wèn)題一可以利用Matlab中現(xiàn)有的線性規(guī)劃工具fminimax。

3 低功耗傳感網(wǎng)能量均衡

在無(wú)線傳感網(wǎng)絡(luò)中，為了進(jìn)一步降低網(wǎng)絡(luò)能耗、延長(zhǎng)網(wǎng)絡(luò)生存周期，通常采用低功耗MAC協(xié)議使得節(jié)點(diǎn)在非活躍狀態(tài)關(guān)閉無(wú)線收發(fā)器以減少不必要的空閑偵聽(tīng)能耗。在可充電傳感網(wǎng)中，節(jié)點(diǎn)采用低功耗協(xié)議能夠在相同的情況下相比不采用低功耗協(xié)議的場(chǎng)景減少充電頻率。本章研究在可充電低功耗傳感網(wǎng)中的能量均衡路由問(wèn)題。

3.1 低功耗模式和機(jī)會(huì)路由

現(xiàn)有研究表明，傳感節(jié)點(diǎn)在無(wú)線通信模塊發(fā)送、接收、空閑、休眠狀態(tài)中平均消耗的能量占總耗能的80%以上[8]。低功耗模式指無(wú)線傳感節(jié)點(diǎn)能夠在空閑時(shí)段關(guān)閉無(wú)線通信模塊，進(jìn)入睡眠模式，故低功耗模式在數(shù)據(jù)傳輸非密集型的無(wú)線傳感網(wǎng)中能夠顯著減少網(wǎng)絡(luò)能量消耗。節(jié)點(diǎn)只能夠在活躍的狀態(tài)下發(fā)送、接收或監(jiān)聽(tīng)到數(shù)據(jù)包。周期性睡眠調(diào)度是指節(jié)點(diǎn)周期性、定時(shí)地睡眠、醒來(lái)，在這種睡眠調(diào)度機(jī)制下睡眠時(shí)間和調(diào)度周期的比值稱為節(jié)點(diǎn)低功耗模式的占空比。

在占空比較低的情況下，節(jié)點(diǎn)同時(shí)醒來(lái)的概率很低，發(fā)送方為了成功傳輸數(shù)據(jù)包，需要持續(xù)發(fā)送引言包直到一個(gè)接收方醒來(lái)并回復(fù)確認(rèn)包(ACKnowledgement,ACK)。如果發(fā)送方只選擇一個(gè)下一跳節(jié)點(diǎn)，那么當(dāng)該接收節(jié)點(diǎn)的一個(gè)活躍周期結(jié)束，發(fā)送方需要等待一個(gè)調(diào)度周期發(fā)送剩余的數(shù)據(jù)包，在不可靠鏈路傳感網(wǎng)中甚至需要等待多個(gè)調(diào)度周期，增加了端到端時(shí)延。機(jī)會(huì)路由允許一個(gè)發(fā)送方選擇一個(gè)鄰居候選集而不只是一個(gè)下一跳以轉(zhuǎn)發(fā)數(shù)據(jù)包，在低占空比情景下，候選集中的節(jié)點(diǎn)依次醒來(lái)，發(fā)送方按照其醒來(lái)次序分別傳送數(shù)據(jù)包直到發(fā)送成功為止。

3.2 能量均衡候選集選擇

機(jī)會(huì)路由能夠有效降低等待延時(shí)，減少成功傳輸一個(gè)數(shù)據(jù)包所需的傳輸次數(shù)。參照第2章的算法，本文嘗試?yán)昧髁糠峙湟詫?shí)現(xiàn)能量均衡路由，然而低功耗傳感網(wǎng)中睡眠調(diào)度和機(jī)會(huì)路由帶來(lái)的挑戰(zhàn)在于，當(dāng)一個(gè)發(fā)送方的候選節(jié)點(diǎn)集確定后，經(jīng)過(guò)該發(fā)送方的數(shù)據(jù)流的分配也同時(shí)確定，這與候選集中節(jié)點(diǎn)的醒來(lái)次序、發(fā)送方到候選集中各節(jié)點(diǎn)的鏈路質(zhì)量相關(guān)。因此本文研究在無(wú)法實(shí)現(xiàn)最優(yōu)能量均衡的路由策略情況下，如何為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)確定轉(zhuǎn)發(fā)候選集以達(dá)到較優(yōu)的網(wǎng)絡(luò)均衡。

首先考慮發(fā)送方需要發(fā)送一個(gè)數(shù)據(jù)包的情況，在流量分配策略中考慮多個(gè)數(shù)據(jù)包的情況。發(fā)送方s的轉(zhuǎn)發(fā)候選集按其醒來(lái)次序遞增排序記為集合fS={n1,n2,…,nK}，到候選集節(jié)點(diǎn)的鏈路質(zhì)量分別記為p1,p2,…,pK，則最終候選集中第i個(gè)節(jié)點(diǎn)的理論期望轉(zhuǎn)發(fā)概率為：

(7)

即s到前i-1個(gè)接收方的數(shù)據(jù)傳輸都沒(méi)成功并在第i個(gè)節(jié)點(diǎn)處成功傳輸。然而在實(shí)際環(huán)境中，傳感節(jié)點(diǎn)的時(shí)鐘并不同步，隨著時(shí)間增加，時(shí)鐘之間可能產(chǎn)生漂移。當(dāng)時(shí)間足夠長(zhǎng)時(shí)，可以將固定周期調(diào)度的各節(jié)點(diǎn)間的鄰居發(fā)現(xiàn)時(shí)延近似為隨機(jī)均勻分布，此時(shí)，候選集中第i個(gè)節(jié)點(diǎn)的期望被選中的概率只與發(fā)送方到自己的鏈路質(zhì)量相關(guān)[9]，有：

(8)

考慮經(jīng)過(guò)s的流量為Qs，則在s的轉(zhuǎn)發(fā)候選集策略為fs的情況下，根據(jù)式(4)，其候選集中第i個(gè)節(jié)點(diǎn)ni的期望流量為：

Qni=P(i)·Qs

(9)

此時(shí)將問(wèn)題一轉(zhuǎn)化為一個(gè)最優(yōu)求解問(wèn)題：如何在可充電無(wú)線傳感網(wǎng)絡(luò)的每個(gè)周期中為每一個(gè)節(jié)點(diǎn)i選擇一個(gè)最優(yōu)轉(zhuǎn)發(fā)候選集fi(t)，以實(shí)現(xiàn)機(jī)會(huì)路由下的最優(yōu)網(wǎng)絡(luò)能量均衡。形式化地表示該問(wèn)題為問(wèn)題二：

(10)

在問(wèn)題二中，與求解問(wèn)題一最大的不同在于問(wèn)題二中的流量分配是由機(jī)會(huì)路由下的候選集選擇、節(jié)點(diǎn)醒來(lái)時(shí)間和優(yōu)先級(jí)考慮下的流量期望決定，而不是確定的多徑路由分配。這種不確定性是由機(jī)會(huì)路由的屬性所決定的。與第2章同理，使用LP可以解決該問(wèn)題。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

本節(jié)中采用以Matlab為平臺(tái)的仿真實(shí)驗(yàn)驗(yàn)證能量均衡路由協(xié)議在普通可充電傳感網(wǎng)中和低功耗可充電傳感網(wǎng)中的效果，在500m×500m的場(chǎng)地中隨機(jī)布置n-1個(gè)可充電無(wú)線傳感節(jié)點(diǎn)，網(wǎng)關(guān)節(jié)點(diǎn)位于坐標(biāo)(0,0)，采用自由空間傳播損耗模型模擬不可靠鏈路?？紤]一種一對(duì)一的簡(jiǎn)單充電場(chǎng)景：每個(gè)充電設(shè)備位于平均高度h=20 m的高壓電線上以恒定功率在每個(gè)周期為各傳感節(jié)點(diǎn)提供能量，能量獲取由式(2)計(jì)算得出。數(shù)據(jù)包傳輸和接收單位數(shù)據(jù)包能耗計(jì)算式分別為erx=eR和etx=eT+εamp·dα。在低功耗場(chǎng)景下設(shè)置節(jié)點(diǎn)的調(diào)度周期和占空比分別為1s和50%。實(shí)驗(yàn)的具體參數(shù)設(shè)置參考表1。本文提出的能量均衡路由協(xié)議和低功耗場(chǎng)景下的分別記為能量均衡路由(EnergyBalancedRouting,EBR)和低功耗能量均衡路由(EBRforLowpowerWSN,EBR-L)，設(shè)置的實(shí)驗(yàn)對(duì)比對(duì)象分別為最短路徑路由(ShortestPathRouting,SPR)和期望周期最短路由(ExpectedDuty-Cycledwakeupsminimalrouting,EDC)[9]。在SPR中，節(jié)點(diǎn)選擇以節(jié)點(diǎn)剩余能量占電池最大電量比重倒數(shù)為基準(zhǔn)(metric)的到達(dá)網(wǎng)關(guān)節(jié)點(diǎn)的最短路徑，以實(shí)現(xiàn)能量均衡路由；在EDC中，考慮了低功耗和機(jī)會(huì)路由的影響，選擇期望時(shí)延最小的候選集。

表1 實(shí)驗(yàn)參數(shù)

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文以歸一化網(wǎng)絡(luò)生命周期為評(píng)價(jià)標(biāo)準(zhǔn)評(píng)估路由以網(wǎng)絡(luò)能量均衡為目標(biāo)的策略好壞，歸一化網(wǎng)絡(luò)生命周期定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的平均工作時(shí)長(zhǎng)和總周期長(zhǎng)度的比值(不計(jì)充電周期)，以圖3為例具體解釋：節(jié)點(diǎn)i在第一個(gè)觀察周期[0,t]的前1/3充電，電量從0升至E0，隨后進(jìn)行數(shù)據(jù)傳輸、轉(zhuǎn)發(fā)操作，在t1時(shí)間消耗完能量，提前結(jié)束了工作周期；在第二個(gè)觀察周期中，i獲得了E1能量并消耗了E1-E2能量，在此周期結(jié)束時(shí)仍有電量剩余。則i在前兩個(gè)周期的歸一化網(wǎng)絡(luò)生命周期為(t1-t/3+2t/3)/(4t/3)。

圖3 節(jié)點(diǎn)i的電池能量周期

圖4描述了網(wǎng)絡(luò)的平均歸一化生命周期隨著節(jié)點(diǎn)數(shù)目的變化，隨著節(jié)點(diǎn)數(shù)目的增加，EBR和SPR的歸一化生命周期都表現(xiàn)出遞減趨勢(shì)，這是由于節(jié)點(diǎn)數(shù)目的增加導(dǎo)致了距離網(wǎng)關(guān)節(jié)點(diǎn)更近的節(jié)點(diǎn)增加了更多的轉(zhuǎn)發(fā)任務(wù)，導(dǎo)致這些節(jié)點(diǎn)的每個(gè)周期內(nèi)工作周期減少，進(jìn)而降低了網(wǎng)絡(luò)的平均生命周期。EBR的歸一化生命周期總是優(yōu)于SPR，因?yàn)镾PR雖然選擇能量剩余多的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，在一定程度上緩解了網(wǎng)絡(luò)負(fù)載不均衡，但是EBR更多地考慮了多個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)的負(fù)載分配對(duì)于網(wǎng)絡(luò)均衡的影響而不僅僅是單個(gè)下一跳，故EBR能夠?qū)崿F(xiàn)更好的能量均衡。

4.3 結(jié)果分析

圖5描述了低功耗場(chǎng)景下的網(wǎng)絡(luò)平均歸一化生命周期隨著節(jié)點(diǎn)數(shù)目的變化，與圖4相似呈遞減趨勢(shì)。EBR-L優(yōu)于EDC的原因是后者更多地考慮了時(shí)延而非能量均衡。值得注意的是，與圖4相比，EBR-L的歸一化生命周期均優(yōu)于EBR，這是因?yàn)镋BR的場(chǎng)景從廣義上來(lái)說(shuō)是多路徑路由而不是機(jī)會(huì)路由，而在低功耗的機(jī)會(huì)路由下，EBR-L在沒(méi)有任務(wù)時(shí)可以進(jìn)入休眠狀態(tài)，從而節(jié)約了空閑偵聽(tīng)的能量。

圖4 歸一化生命周期隨節(jié)點(diǎn)數(shù)目變化

圖 5 低功耗場(chǎng)景歸一化生命周期隨節(jié)點(diǎn)數(shù)目變化

對(duì)比圖4～5，可以發(fā)現(xiàn)EBR比EBR-L在相同的配置下具有更長(zhǎng)的網(wǎng)絡(luò)生命周期，這是因?yàn)槭紫缺疚脑趯?shí)驗(yàn)中只考慮收發(fā)數(shù)據(jù)包的能耗，其次從信息論角度考慮，EBR使用全局網(wǎng)絡(luò)信息進(jìn)行優(yōu)化，而EBR-L是分布式的路由算法，前者比后者擁有更多的信息故更優(yōu)。

考慮兩種算法的復(fù)雜度，EBR采用線性規(guī)劃算法，時(shí)間復(fù)雜度為n的多項(xiàng)式級(jí)別；EBR-L在前者的基礎(chǔ)上增加了關(guān)于轉(zhuǎn)發(fā)候選集的約束條件，搜索空間大于EBR，但仍為n的多項(xiàng)式級(jí)別時(shí)間復(fù)雜度。

5 結(jié)語(yǔ)

為解決可充電無(wú)線傳感網(wǎng)絡(luò)中的能量均衡路由問(wèn)題，分別針對(duì)非低功耗場(chǎng)景和低功耗場(chǎng)景，本文提出基于多路徑路由和機(jī)會(huì)路由的路由協(xié)議。前者根據(jù)充電速率、自身電池剩余電量、接收和發(fā)送數(shù)據(jù)包的單位能耗等信息，通過(guò)全網(wǎng)的線性規(guī)劃為每個(gè)參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)的候選集規(guī)劃鏈路流量；后者為每個(gè)轉(zhuǎn)發(fā)者選擇一個(gè)能耗最優(yōu)的候選集，在機(jī)會(huì)路由框架下延長(zhǎng)網(wǎng)絡(luò)壽命。實(shí)驗(yàn)結(jié)果表明，提出的兩種路由算法能夠有效地實(shí)現(xiàn)網(wǎng)絡(luò)均衡。接下來(lái)將針對(duì)復(fù)雜移動(dòng)場(chǎng)景下的可充電無(wú)線傳感網(wǎng)絡(luò)的路由問(wèn)題進(jìn)行研究。

)

[1] 夏先進(jìn),李士寧,張羽,等.一維傳感網(wǎng)中混合數(shù)據(jù)傳輸?shù)哪芰烤鈁J].軟件學(xué)報(bào),2015,26(8):1983-2006.(XIAXJ,LISN,ZHANGY,etal.Energybalanceofmixeddatatransmissionin1Dsensornetworks[J].JournalofSoftware, 2015, 26(8): 1983-2006.)

[2] 吳華君,張自力,李衛(wèi).一種適用于煤礦井下無(wú)線傳感網(wǎng)的能量均衡路由協(xié)議[J].計(jì)算機(jī)科學(xué),2011,38(4):145-150.(WUHJ,ZHANGZL,LIW.Energy-balancedroutingprotocolforwirelesssensornetworksincoalmine[J].ComputerScience, 2011, 38(4): 145-150.)

[3]HEINZELMANWR,CHANDRAKASANA,BALAKRISHNANH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//HICSS’00:Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences.Washington,DC:IEEEComputerSociety, 2000: 8020.

[4] 曹立志,陳瑩.基于學(xué)習(xí)自動(dòng)機(jī)的無(wú)線傳感網(wǎng)能量均衡分簇算法[J].傳感技術(shù)學(xué)報(bào),2013,26(11):1590-1596.(CAOLZ,CHENY.Energybalancedclusteringalgorithmbasedonlearningautomataforwirelesssensornetwork[J].ChineseJournalofSensorsandActuators, 2013, 26(11): 1590-1596.)

[5] 米志超,周建江.一種能量均衡的無(wú)線傳感網(wǎng)絡(luò)生命期優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù),2008,30(12):2477-2480.(MIZC,ZHOUJJ.Energy-balancedoptimizationalgorithmformaximizingnetworklifetimeinwirelesssensornetworks[J].SystemsEngineeringandElectronics, 2008, 30(12): 2477-2480.)

[6]ANGELOPOULOSCM,NIKOLETSEASS,RAPTISTP,etal.Efficientenergymanagementinwirelessrechargeablesensornetworks[C]//MSWiM’12:Proceedingsofthe15thACMInternationalConferenceonModeling,AnalysisandSimulationofWirelessandMobileSystems.NewYork:ACM, 2012: 309-316.

[7]MAOSB,CHEUNGMH,WONGVWS.Jointenergyallocationforsensingandtransmissioninrechargeablewirelesssensornetworks[J].IEEETransactionsonVehicularTechnology, 2014, 63(6): 2862-2875.

[8] 杜欣.WSN低功耗算法在電力系統(tǒng)中的應(yīng)用[J].電力系統(tǒng)通信,2012,33(4):62-66.(DUX.ApplicationofWSNtechnologybasedlow-powerconsumptionalgorithmsinpowersystem[J].TelecommunicationsforElectricPowerSystem, 2012, 33(4): 62-66.)

[9]GHADIMIE,LANDSIEDELO,SOLDATIP,etal.Opportunisticroutinginlowduty-cyclewirelesssensornetworks[J].ACMTransactionsonSensorNetworks, 2014, 10(4):ArticleNo. 67.

[10]GUY,HET.Dynamicswitching-baseddataforwardingforlowduty-cyclewirelesssensornetworks[J].IEEETransactionsonMobileComputing, 2011, 10(12): 1741-1754.

[11] 趙燦明,李祝紅,閆凡,等.電力通信網(wǎng)絡(luò)中負(fù)載均衡的路由協(xié)議[J].計(jì)算機(jī)應(yīng)用,2016,36(11):3028-3032.(ZHAOCM,LIZH,YANF,etal.Loadbalancedroutingprotocolinelectricpowercommunicationnetworks[J].JournalofComputerApplication, 2016, 36(11): 3028-3032.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61379130, 61672485).

XIE Xiaojun, born in 1975, M. S., engineer. His research interests include electric power communication system.

YU Hao, born in 1975, M. S., engineer. His research interests include electric power communication system.

TAO Lei, born in 1992, Ph. D. candidate. His research interests include wireless network, smart grid.

ZHANG Xinming, born in 1964. Ph. D., professor. His research interests include wireless network, smart grid.

Energy-balanced routing algorithm in rechargeable wireless sensor networks

XIE Xiaojun1, YU Hao1, TAO Lei2, ZHANG Xinming2*

(1.DivisionofInformationCommunication,StateGridAnhuiElectricPowerCompany,HefeiAnhui230061,China; 2.SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,HefeiAnhui230027,China)

Aiming at energy-balanced routing problem in rechargeable Wireless Sensor Network (WSN), a new multi-path routing algorithm and an opportunistic routing algorithm were proposed in the scenario of wireless charging with stable power and monitoring data collection network, so as to achieve the energy balance of the network. Firstly, the relationship model between the charging power and the receiving power of wireless sensor nodes was constructed by the theory of electromagnetic propagation. Then, considering the sending and receiving energy consumptions of wireless sensor nodes in the network, the energy-balanced routing problem was transformed into the max-min optimization lifetime problem of the network nodes. The link traffic obtained by the linear programming was used to guide the data flow allocation in the routing. Finally, considering a more realistic scenario of low power WSN, an energy-balanced routing algorithm based on opportunistic routing was proposed. The experimental results show that, compared with the Shortest Path Routing (SPR) and Expected Duty-Cycled wakeups minimal routing (EDC) algorithms, the proposed two routing algorithms can effectively improve the utilization ratio of the energy collection and the network lifetime in the working period.

energy-balanced routing; rechargeable Wireless Sensor Network (WSN); opportunistic routing; low power sensor network

2016- 11- 17;

2017- 02- 04。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61379130,61672485)。

謝小軍(1975—)，男，安徽涇縣人，工程師，碩士，主要研究方向：電力通信系統(tǒng)； 于浩(1975—)，男，安徽臨泉人，工程師，碩士，主要研究方向：電力通信系統(tǒng)； 陶磊(1992—)，男，安徽和縣人，博士研究生，主要研究方向：無(wú)線網(wǎng)絡(luò)、智能電網(wǎng)； 張信明(1964—)，男，安徽天長(zhǎng)人，教授，博士，CCF高級(jí)會(huì)員，主要研究方向：無(wú)線網(wǎng)絡(luò)、智能電網(wǎng)。

1001- 9081(2017)06- 1545- 05

10.11772/j.issn.1001- 9081.2017.06.1545

TP393.03

A