無(wú)線傳感器網(wǎng)絡(luò)中基于延遲與能量平衡的背壓調(diào)度算法*

王彬彬,周繼鵬

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院,廣州 510632)

無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)[1]是一種現(xiàn)代網(wǎng)絡(luò)技術(shù),主要由一些傳感節(jié)點(diǎn)和基站構(gòu)成。傳感節(jié)點(diǎn)既能夠讀取數(shù)據(jù),又可以發(fā)送數(shù)據(jù)到基站?；緞t發(fā)揮了收集和整理獲取的數(shù)據(jù)的作用。無(wú)線傳感器網(wǎng)絡(luò)最早開(kāi)始應(yīng)用于戰(zhàn)場(chǎng)上的某些偵察活動(dòng)。隨后,無(wú)線傳感器網(wǎng)絡(luò)逐漸成為一種能夠應(yīng)用于多學(xué)科和多領(lǐng)域的新興技術(shù)。研究者相繼提出了一系列與之相關(guān)的通信協(xié)議和諸多類(lèi)型的拓?fù)浣Y(jié)構(gòu)。有效應(yīng)用于森林火災(zāi)的檢測(cè),天氣預(yù)報(bào)等特定情景。作為無(wú)線網(wǎng)絡(luò)中一種沒(méi)有固定基站的動(dòng)態(tài)網(wǎng)絡(luò),無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議在某些細(xì)節(jié)上區(qū)別于Ad hoc網(wǎng)絡(luò)路由協(xié)議。Ad hoc網(wǎng)絡(luò)路由最重要的功能是決定源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的路徑。當(dāng)節(jié)點(diǎn)間傳輸范圍超過(guò)一跳距離時(shí),將需要通過(guò)中繼節(jié)點(diǎn)的支持。從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的數(shù)據(jù)包的傳輸有3種類(lèi)型的協(xié)議。分別為先驗(yàn)式路由協(xié)議[2],反應(yīng)式路由協(xié)議[3],以及混合路由協(xié)議[4]。此外,傳感器網(wǎng)絡(luò)面臨的最大問(wèn)題是能量受限。這是由傳感節(jié)點(diǎn)的體積小,內(nèi)存小,電池小,以及微處理器等結(jié)構(gòu)因素造成。

由于無(wú)線媒介的共享屬性,無(wú)線網(wǎng)絡(luò)中資源分配是十分復(fù)雜的。背壓算法BP(Backpressure)作為一種特殊的資源分配算法,最早在文獻(xiàn)[5]中提出。背壓算法是基于李雅普諾夫漂移理論(Lyapunov Drift theory),且涉及到協(xié)議棧中的MAC層和路由層。背壓算法中最顯著的屬性是吞吐量最優(yōu)化(Throughput-optimal)。也就是說(shuō),通過(guò)背壓算法獲得的調(diào)度策略能夠支持任何到達(dá)的傳輸速率。而且對(duì)于網(wǎng)絡(luò)拓?fù)涞碾S機(jī)變化具有很強(qiáng)的魯棒性。背壓算法的性能在很低的網(wǎng)絡(luò)負(fù)載條件下表現(xiàn)的很糟糕,因?yàn)閿?shù)據(jù)包可能在網(wǎng)絡(luò)中出現(xiàn)不斷的循環(huán)。背壓算法為了穩(wěn)定整個(gè)系統(tǒng)將會(huì)盡可能應(yīng)用網(wǎng)絡(luò)中所有可能的路徑。這個(gè)機(jī)制的后果是會(huì)增加延遲和中繼節(jié)點(diǎn)能量的消耗。在這種類(lèi)型的網(wǎng)絡(luò)中,數(shù)據(jù)包的傳輸和調(diào)度的根本目標(biāo)是完成預(yù)定的服務(wù)質(zhì)量QoS(Quality of Service)。服務(wù)質(zhì)量主要通過(guò)數(shù)據(jù)包的平均延遲和節(jié)點(diǎn)能量來(lái)度量。延遲和能量又是內(nèi)部相關(guān)的,數(shù)據(jù)包在網(wǎng)絡(luò)系統(tǒng)中存在的平均時(shí)間越小,意味著數(shù)據(jù)包到達(dá)終點(diǎn)的跳數(shù)越小,也就是說(shuō),總的能量消耗的減少。本文將主要研究延遲與能量之間更加具體的內(nèi)在聯(lián)系。

1 相關(guān)工作

原始的背壓概念引起了隨后在這個(gè)領(lǐng)域的廣泛研究。文獻(xiàn)[6]對(duì)已有的相關(guān)背壓算法作出了比較綜合的分析。背壓算法有很多優(yōu)異的特性,例如吞吐量最優(yōu)化,能夠?qū)崿F(xiàn)的可適應(yīng)資源分配,支持敏捷的負(fù)載感知路由和簡(jiǎn)單化。但是,背壓算法在實(shí)際場(chǎng)景地應(yīng)用中仍然存在一些亟待解決的問(wèn)題,包括集中式控制模式,糟糕的延遲性能,極高的計(jì)算復(fù)雜度和隊(duì)列復(fù)雜度。并將現(xiàn)有主要的研究領(lǐng)域劃分為三類(lèi),怎樣實(shí)現(xiàn)預(yù)期的延遲性能,怎樣減小節(jié)點(diǎn)的隊(duì)列復(fù)雜度和怎樣完成有效的跨層設(shè)計(jì)。文獻(xiàn)[7],利用背壓類(lèi)型的算法處理延遲效率問(wèn)題。文中提出兩種算法,一種是VoBP,減輕數(shù)據(jù)包調(diào)度的乒乓效應(yīng)。另一種是LBP,將節(jié)點(diǎn)分層,運(yùn)用層的標(biāo)號(hào)進(jìn)行背壓調(diào)度實(shí)現(xiàn)將數(shù)據(jù)包傳送到目的節(jié)點(diǎn)的目標(biāo)。文獻(xiàn)[8],在無(wú)線多跳網(wǎng)絡(luò)中,對(duì)于支持有效的背壓調(diào)度,主要實(shí)現(xiàn)了顯著的延遲性能的優(yōu)化。通過(guò)提出一個(gè)基于背壓調(diào)度的虛擬梯度(VBR),在網(wǎng)絡(luò)中提前建立虛擬隊(duì)列梯度和使得每個(gè)節(jié)點(diǎn)在進(jìn)行調(diào)度決策時(shí)進(jìn)行考慮這個(gè)虛擬隊(duì)列。結(jié)果顯示,VBR就在傳送率和平均的端到端延遲方面能夠完成明顯的性能提升。文獻(xiàn)[9],提出一個(gè)基于延遲的背壓調(diào)度(DBP)方案,這是一個(gè)在多跳無(wú)線網(wǎng)絡(luò)中帶有固定路由的算法。引入一個(gè)適應(yīng)于多跳流量的延遲度量。在隊(duì)列長(zhǎng)度和延遲之間建立線性關(guān)系。DBP圍繞最后包問(wèn)題提供了一個(gè)簡(jiǎn)單的方式,避免流沒(méi)有數(shù)據(jù)包的問(wèn)題。因此,在基于隊(duì)列的背壓算法下,某些流經(jīng)歷的過(guò)度的長(zhǎng)的延遲將會(huì)消除,而且沒(méi)有任何吞吐量的丟失。文獻(xiàn)[10],主要是通過(guò)提出一個(gè)基于背壓的有效網(wǎng)絡(luò)編碼算法(NBP)。NBP引進(jìn)內(nèi)部流網(wǎng)絡(luò)編碼去提高傳統(tǒng)的背壓算法的性能,當(dāng)被用作調(diào)度數(shù)據(jù)包傳輸。并且,證明了它的穩(wěn)定性。結(jié)果表明,NBP在延遲性能和傳送隊(duì)列長(zhǎng)度帶有低的額外存儲(chǔ)代價(jià)上相對(duì)于傳統(tǒng)的背壓算法性能更優(yōu)越。文獻(xiàn)[11],提出了EBP。這是一個(gè)對(duì)于傳感器網(wǎng)絡(luò)的能量有效的背壓路由和調(diào)度算法。其中,設(shè)計(jì)了一個(gè)新的鏈路權(quán)計(jì)算方法。在這個(gè)新的方法中,鏈路權(quán)大小不僅由節(jié)點(diǎn)的隊(duì)列長(zhǎng)度決定,而且要考慮它們的能量狀態(tài)。在EBP中,數(shù)據(jù)包將會(huì)被更多的傳送到更多剩余能量的節(jié)點(diǎn),同時(shí),背壓算法的吞吐量最優(yōu)化依然能夠保證。

Ad hoc網(wǎng)絡(luò)領(lǐng)域中,存在大量關(guān)于Backpressure算法的學(xué)術(shù)研究。其中,大多數(shù)焦點(diǎn)都集中在網(wǎng)絡(luò)節(jié)點(diǎn)端到端的延遲,隊(duì)列結(jié)構(gòu)的復(fù)雜度等主要方面。同樣,在無(wú)線傳感器的研究領(lǐng)域中,研究的方向傾向于關(guān)注能量的消耗。文獻(xiàn)[12]通過(guò)設(shè)計(jì)一種基于分區(qū)的關(guān)于能耗均衡路由協(xié)議,使得網(wǎng)絡(luò)中的節(jié)點(diǎn)能耗達(dá)到了均衡的目的,從而增強(qiáng)了網(wǎng)絡(luò)的穩(wěn)定性。算法比較全面考慮節(jié)點(diǎn)剩余能量、簇內(nèi)的節(jié)點(diǎn)的能量均衡和簇內(nèi)的總的能耗3個(gè)因素。實(shí)驗(yàn)結(jié)論表明該算法能夠比較好地均衡節(jié)點(diǎn)的能耗和增強(qiáng)網(wǎng)絡(luò)的穩(wěn)定性。在這樣的背景下,我們希望在某種情況下,能夠在保持在數(shù)據(jù)包吞吐量最大化的前提下,確保端到端的延遲最小化,同時(shí)通過(guò)能量的有效利用,保證網(wǎng)絡(luò)系統(tǒng)壽命的最大化。因此我們提出基于延遲和能量平衡的改進(jìn)的背壓調(diào)度算法BBP(Balanced Delay and Energy on Backpressure Scheduling Algorithm)。

本文的主要貢獻(xiàn)包括:①提出一種新的延遲和能量相關(guān)的改進(jìn)背壓調(diào)度算法。在一定程度上提高了現(xiàn)有相關(guān)算法的性能。②對(duì)所提出的算法進(jìn)行了實(shí)驗(yàn)仿真。

本文的剩余部分組織如下。第2部分將描述系統(tǒng)模型。第3部分首先回顧了原始背壓算法。然后提出了我們自己改進(jìn)的算法。第4部分,我們將仿真提出的算法。總結(jié)將在最后一部分完成。

本文使用的符號(hào)如表1所示。

表1 符號(hào)表

2 系統(tǒng)模型

我們假定一個(gè)無(wú)線網(wǎng)絡(luò)G=(V,L),其中G代表有向圖,V是圖中所有節(jié)點(diǎn)的集合,L代表圖中的所有鏈路集合。節(jié)點(diǎn)是無(wú)線傳輸和接收器。節(jié)點(diǎn)是靜止的,通信鏈路是雙向的,并且以多跳形式進(jìn)行通信。在直接通信的情況下,鏈路是節(jié)點(diǎn)之間的無(wú)線信道。所有節(jié)點(diǎn)的配置都是相同的,例如能量值,能量消耗因素等。時(shí)間是分時(shí),t是每個(gè)時(shí)隙的值。當(dāng)節(jié)點(diǎn)正在發(fā)送數(shù)據(jù)包時(shí),位于其通信范圍內(nèi)的所有節(jié)點(diǎn)都不能從其他節(jié)點(diǎn)接收數(shù)據(jù)包。在系統(tǒng)[10]中的一跳干擾模型被使用,即當(dāng)兩個(gè)鏈路彼此干擾時(shí),它們將處于一跳范圍內(nèi)。一個(gè)節(jié)點(diǎn)不能夠同時(shí)發(fā)送和接收數(shù)據(jù)包。數(shù)據(jù)包具有平均到達(dá)率λ。每個(gè)數(shù)據(jù)包的源節(jié)點(diǎn)是在所有節(jié)點(diǎn)中隨機(jī)選擇,目的節(jié)點(diǎn)是確定的。

3 算法描述

3.1 原始背壓算法

在原始背壓算法中[7,13],每個(gè)節(jié)點(diǎn)根據(jù)數(shù)據(jù)包去往目的地的不同來(lái)分別維持一個(gè)隊(duì)列。通過(guò)計(jì)算兩個(gè)節(jié)點(diǎn)之間的隊(duì)列長(zhǎng)度的差值,可以決策出擁有相對(duì)更大的權(quán)值的鏈路將會(huì)被調(diào)度。因此,背壓調(diào)度是一個(gè)鏈路調(diào)度而不是數(shù)據(jù)包調(diào)度。至于這個(gè)算法為什么稱(chēng)之為背壓,是因?yàn)樗鼡碛锌梢员徽{(diào)度的最大流權(quán),就好像數(shù)據(jù)包是被壓力推到目的地。

在一個(gè)有N個(gè)節(jié)點(diǎn)的多跳無(wú)線網(wǎng)絡(luò)中,網(wǎng)絡(luò)系統(tǒng)是分時(shí)的。背壓算法的調(diào)度和路由操作在每個(gè)時(shí)隙中完成。完整的背壓操作如下所示。

①計(jì)算鏈路權(quán)值

首先,對(duì)于鏈路(m,n),在m,n節(jié)點(diǎn)之間計(jì)算隊(duì)列值差,d是目的節(jié)點(diǎn)。m和n節(jié)點(diǎn)是網(wǎng)絡(luò)系統(tǒng)中任意的兩個(gè)鄰居節(jié)點(diǎn),網(wǎng)絡(luò)流的方向是從m到n。

(1)

(2)

②選擇調(diào)度鏈路

其次,完成如下的優(yōu)化,

(3)

在式(3)中,其中Γ表示在一跳干擾模型下的可調(diào)度鏈路集合。μmn是傳輸速率。μ*(t)是最優(yōu)的傳輸鏈路的集合。

③選擇路由路徑

④舉例說(shuō)明

如圖1所示,是一個(gè)簡(jiǎn)單的無(wú)線多跳網(wǎng)絡(luò)。A,B,C,D是網(wǎng)絡(luò)中的4個(gè)節(jié)點(diǎn),網(wǎng)絡(luò)的方向如箭頭指向所示。數(shù)值(商品中的值)是節(jié)點(diǎn)在此時(shí)維護(hù)的隊(duì)列長(zhǎng)度,分別為Qfull(t),Qstripe(t)和Qblank(t)。通過(guò)上述的步驟,我們可以得到三條鏈路(A,B),(A,C),(A,D)的權(quán)值,如下:

假定,鏈路(A,B),(A,C),(A,D)的傳輸速率分別為μAB(t)=2,μAC(t)=4,μAD(t)=1。同時(shí),在時(shí)隙t,鏈路集{(A,C)}內(nèi)部鏈路集合不會(huì)相互干擾。相似的,{(A,C)},{(A,D)} 與{(A,B)}有相同的屬性。接下來(lái),計(jì)算 Σμ(t)w(t):

圖1 一個(gè)簡(jiǎn)單的無(wú)線多跳網(wǎng)絡(luò)

3.2 算法設(shè)計(jì)

BBP算法設(shè)計(jì)并應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)。在無(wú)線傳感器網(wǎng)絡(luò)中,數(shù)據(jù)包流都移動(dòng)到匯聚節(jié)點(diǎn)。因此,匯聚節(jié)點(diǎn)就是目的節(jié)點(diǎn)。根據(jù)原始背壓算法的設(shè)計(jì),在這個(gè)網(wǎng)絡(luò)系統(tǒng)中將只會(huì)有一條流。網(wǎng)絡(luò)系統(tǒng)流的復(fù)雜度相對(duì)小一點(diǎn)。在網(wǎng)格網(wǎng)絡(luò)系統(tǒng)中,網(wǎng)絡(luò)中的數(shù)據(jù)包將會(huì)記錄最近一次經(jīng)過(guò)的節(jié)點(diǎn)的信息。每個(gè)節(jié)點(diǎn)的隊(duì)列將會(huì)通過(guò)參數(shù)維護(hù)兩個(gè)信息。一個(gè)是剩余能量的信息,另一個(gè)是數(shù)據(jù)包瀏覽該節(jié)點(diǎn)鄰居節(jié)點(diǎn)的記錄。通過(guò)考慮這兩個(gè)參數(shù),得到我們的調(diào)度算法。

我們?cè)O(shè)計(jì)調(diào)度算法的最初目的是確保最佳的系統(tǒng)吞吐量,并希望數(shù)據(jù)包花費(fèi)最少的時(shí)間通過(guò)節(jié)點(diǎn)到達(dá)目的地。而且我們要求路徑簡(jiǎn)單,同時(shí)網(wǎng)絡(luò)系統(tǒng)是合理的利用節(jié)點(diǎn)能量,盡可能實(shí)現(xiàn)延遲成本與能量使用之間的平衡。也就是說(shuō),為了保證延遲效果的前提,并且不會(huì)出現(xiàn)太多的死節(jié)點(diǎn)。我們一直致力于這兩個(gè)方面,盡我們最大的努力取得最好的效果。

我們參考文獻(xiàn)[7],這給了我們很大的啟發(fā)。在我們的BBP算法中,我們使每個(gè)數(shù)據(jù)包能夠記錄上次訪問(wèn)的節(jié)點(diǎn)信息。我們收集這個(gè)信息是用于阻止數(shù)據(jù)包在調(diào)度階段在網(wǎng)絡(luò)中出現(xiàn)回環(huán)。在無(wú)線傳感器網(wǎng)絡(luò)中,每個(gè)節(jié)點(diǎn)僅僅維護(hù)一個(gè)隊(duì)列。因?yàn)閿?shù)據(jù)包是根據(jù)其到達(dá)的目的地來(lái)劃分,正如上述提到的匯聚節(jié)點(diǎn),所有的節(jié)點(diǎn)將會(huì)被傳送至匯聚節(jié)點(diǎn)。每一個(gè)節(jié)點(diǎn)的隊(duì)列形成一個(gè)計(jì)數(shù)器C相對(duì)其所有的鄰居節(jié)點(diǎn)。舉個(gè)例子,節(jié)點(diǎn)m根據(jù)其要到達(dá)的目的節(jié)點(diǎn)d形成一個(gè)隊(duì)列,該隊(duì)列將會(huì)用計(jì)數(shù)器Cmnd記錄它的鄰居節(jié)點(diǎn)n的信息。也就是說(shuō),節(jié)點(diǎn)m的隊(duì)列會(huì)根據(jù)不同的鄰居節(jié)點(diǎn)維護(hù)多個(gè)計(jì)數(shù)器C。這個(gè)計(jì)數(shù)器與我們隨后的調(diào)度算法有關(guān)。計(jì)數(shù)器具體操作如下。當(dāng)一個(gè)數(shù)據(jù)包p從節(jié)點(diǎn)m經(jīng)過(guò)節(jié)點(diǎn)n去往目的節(jié)點(diǎn)d。兩個(gè)節(jié)點(diǎn)m和n的計(jì)數(shù)器將會(huì)改變。當(dāng)數(shù)據(jù)包在節(jié)點(diǎn)n時(shí),Cnmd(此時(shí),m是節(jié)點(diǎn)n的一個(gè)鄰居節(jié)點(diǎn))在節(jié)點(diǎn)n將會(huì)加1。在節(jié)點(diǎn)m的計(jì)數(shù)器Cmnd將會(huì)減1。數(shù)據(jù)包同樣會(huì)更新和記錄它最近一次瀏覽過(guò)的節(jié)點(diǎn)。BBP算法在每個(gè)時(shí)隙執(zhí)行以下步驟。我們假定節(jié)點(diǎn)n是節(jié)點(diǎn)m的其中一個(gè)一跳范圍內(nèi)的鄰居節(jié)點(diǎn)。節(jié)點(diǎn)m是網(wǎng)絡(luò)系統(tǒng)中任意一個(gè)節(jié)點(diǎn)。Ne是節(jié)點(diǎn)m的一跳范圍內(nèi)所有鄰居節(jié)點(diǎn)的集合。首先,隊(duì)列選擇一個(gè)最壞的鄰居節(jié)點(diǎn)Bmnd,這是節(jié)點(diǎn)m所有鄰居節(jié)點(diǎn)Ne中Cmnd最大的值。根據(jù),

(4)

在式(4)中,Bmnd是最壞的鄰居節(jié)點(diǎn)的值。隨之,參數(shù)αmnd形成,

(5)

在式(5)中,α是一個(gè)常量,我們將其設(shè)置為2,是通過(guò)大量的仿真結(jié)果。αmnd受到約束條件的限制。

其中,參數(shù)αmnd的形成過(guò)程如下:

參數(shù)αmnd:

1.節(jié)點(diǎn)m根據(jù)到達(dá)的目的節(jié)點(diǎn)d維護(hù)其鄰居節(jié)點(diǎn)n一個(gè)計(jì)數(shù)器Cmnd

2.數(shù)據(jù)包p到達(dá)節(jié)點(diǎn)n時(shí),節(jié)點(diǎn)n的計(jì)數(shù)器Cnmd加1;節(jié)點(diǎn)m的計(jì)數(shù)器Cmnd減1

3.根據(jù)式(4),選擇一個(gè)最壞的鄰居

4.式(5)則為參數(shù)αmnd

每一個(gè)節(jié)點(diǎn)有一個(gè)固定的初始能量Efull(除了匯聚節(jié)點(diǎn),匯聚節(jié)點(diǎn)的能量是無(wú)限的。),一個(gè)節(jié)點(diǎn)的剩余能量是Eresidual。我們同樣使得在網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的隊(duì)列維護(hù)一個(gè)計(jì)數(shù)器Dmnd對(duì)于它的相應(yīng)的鄰居節(jié)點(diǎn)集合Ne中的每一個(gè)節(jié)點(diǎn),記錄剩余能量。具體的操作如下,節(jié)點(diǎn)m將會(huì)記錄它的鄰居節(jié)點(diǎn)n的Dmnd。

(6)

在式(6)中,我們?cè)O(shè)置k=3。常數(shù)k的選擇需要大量的實(shí)驗(yàn)決定,正如參數(shù)α的值。

我們使,

(7)

在式(7)中,βmnd是另一個(gè)關(guān)于我們調(diào)度算法的參數(shù)。Ne是節(jié)點(diǎn)m的鄰居節(jié)點(diǎn)的集合。其中剩余能量率v是,

(8)

在式(8)中,v是剩余能量率。

其中,參數(shù)βmnd的形成過(guò)程如下,

參數(shù)βmnd:

1.每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)計(jì)數(shù)器Dmnd對(duì)于相應(yīng)的鄰居節(jié)點(diǎn)

2.根據(jù)式(6),節(jié)點(diǎn)m記錄鄰居節(jié)點(diǎn)n的Dmnd

3.根據(jù)式(7),得到βmnd

我們描述了如上在BBP算法中兩個(gè)參數(shù)αmnd和βmnd。得到我們的調(diào)度算法的權(quán)值計(jì)算公式,

(9)

式(9)是我們BBP算法的公式。通過(guò)這個(gè)公式,可以選擇路由路徑通過(guò)新的鏈路調(diào)度算法。我們做一個(gè)簡(jiǎn)單的分析,當(dāng)

(10)

也就是說(shuō),節(jié)點(diǎn)n不是一個(gè)壞節(jié)點(diǎn)。在條件(10)中,βmnd的值越大,鏈路(m,n)被選擇的概率就越高。也就是,節(jié)點(diǎn)剩余越多的能量,節(jié)點(diǎn)被選擇的概率就越大。

BBP調(diào)度算法的偽代碼描述如下,

算法BBP:

while(m,n)在L中

Output:從節(jié)點(diǎn)m到節(jié)點(diǎn)n以速率μmn傳輸商品d

進(jìn)入時(shí)隙t+1(下一個(gè)時(shí)隙)

end while

end while

4 仿真結(jié)果

文獻(xiàn)[14]比較了一些常用的仿真工具,我們選擇了NS3(https://www.nsnam.org/)來(lái)對(duì)提出的算法進(jìn)行仿真。文獻(xiàn)[15]很詳細(xì)地描述了原始背壓算法的實(shí)現(xiàn)過(guò)程,這給了我們的實(shí)驗(yàn)完成提供了很大的幫助。NS3是一個(gè)基于離散事件的網(wǎng)絡(luò)仿真工具,其主要的目的是用于科學(xué)研究和教學(xué)。NS3是一個(gè)自由開(kāi)放源碼的軟件,基于GNU GPLv2許可,可以公開(kāi)的獲取用于研究,開(kāi)發(fā)和使用。

我們的實(shí)驗(yàn)是基于ns-3.25的開(kāi)發(fā)環(huán)境。測(cè)試網(wǎng)絡(luò)是一個(gè)5×5的網(wǎng)格網(wǎng)絡(luò),有25個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。實(shí)驗(yàn)的環(huán)境即為中小型網(wǎng)絡(luò),更大型的網(wǎng)絡(luò)將是下一步的研究?jī)?nèi)容。仿真時(shí)間為1 000個(gè)時(shí)隙。鏈路容量為1packet/slot。通過(guò)比較傳統(tǒng)背壓算法(BP)與VOBP,EBP,BBP的吞吐量,平均延遲和剩余能量率。我們得到如下圖所示的結(jié)果。我們?cè)O(shè)置到達(dá)速率λ為0.6,0.8,1.0,1.2,1.4 packets/slot來(lái)比較吞吐量和剩余能量率的性能。設(shè)置到達(dá)速率為[0,0.6]packets/slot來(lái)比較BP與其他3個(gè)優(yōu)化算法的平均延遲。其中,傳感節(jié)點(diǎn)的初始能量為300 J。每處理一個(gè)數(shù)據(jù)包節(jié)點(diǎn)消耗能量1.5 J。

比較吞吐量的性能可以得到圖2,結(jié)果可以看出隨著到達(dá)速率λ的不斷增加,3個(gè)改進(jìn)BP算法的網(wǎng)絡(luò)吞吐量性能都略?xún)?yōu)于原始BP算法。3個(gè)改進(jìn)的BP算法都能夠確保最優(yōu)的吞吐量。但是吞吐量性能在不同的λ時(shí)都有可能更優(yōu)。這是由于改進(jìn)后的背壓算法都能保持原始背壓算法的特性,即吞吐量最優(yōu)化。但是當(dāng)包含其他特性,如延遲改進(jìn)等會(huì)增加一點(diǎn)吞吐量量性能的不穩(wěn)定性。實(shí)驗(yàn)結(jié)果滿(mǎn)足我們的要求,也就是無(wú)線傳感器網(wǎng)絡(luò)的吞吐量最優(yōu)化。

圖2 吞吐量性能比較

比較平均延遲的性能得到圖3,3個(gè)改進(jìn)的BP算法的性能在不同的到達(dá)速率λ時(shí)明顯優(yōu)于原始BP算法。BBP算法在某些λ時(shí)與VOBP算法的性能差不多。造成這種現(xiàn)象的原因是VOBP算法是小型網(wǎng)絡(luò)延遲性能比較突出的算法。所以BBP算法中延遲部分細(xì)節(jié)參考VOBP。但是同時(shí)BBP算法又考慮了能量的消耗問(wèn)題,所以延遲效果不會(huì)比VOBP算法優(yōu)化太多。系統(tǒng)必須將能量因素考慮在內(nèi),因?yàn)槟芰颗c延遲的平衡是極其重要的。但是BBP算法的延遲性能是優(yōu)于EBP算法的。這是因?yàn)镋BP延遲沒(méi)有考慮到延遲部分。

圖3 平均延遲性能比較

圖4 剩余能量率性能比較

比較剩余能量率性能得到圖4,在4個(gè)背壓算法間比較了整個(gè)系統(tǒng)的剩余能量率。從結(jié)果中可以得到,BBP和EBP比其他兩個(gè)算法的性能更優(yōu)。同時(shí),在我們的仿真中BBP比EBP表現(xiàn)的更好。這是因?yàn)閂OBP,BP沒(méi)有考慮能量的利用,所以能量消耗的較多。從圖中可以知道,BBP的剩余能量率在不同的λ時(shí),都大于其他3個(gè)背壓算法。

最后,可以得出結(jié)論,在某種程度上,即中小型網(wǎng)絡(luò)下,BBP不僅減小了延遲,延遲效果優(yōu)于EBP,VOBP算法。同時(shí)又有效的利用能量,能量利用優(yōu)于VOBP,EBP算法。但是兩個(gè)因素之間又相互制約,達(dá)到某種程度的平衡。

5 總結(jié)

本文在無(wú)線傳感器網(wǎng)絡(luò)的環(huán)境下,提出一種改進(jìn)的背壓算法。我們的實(shí)驗(yàn)結(jié)果表明,BBP算法的提出在特定的場(chǎng)景即中小型網(wǎng)絡(luò)下可以確保吞吐量最優(yōu)化的同時(shí),能夠減少延遲和保證能量的合理運(yùn)用。至于,能否適用于其他不同的環(huán)境和進(jìn)一步算法優(yōu)化將是我們下一步的工作。

[1] Boonsongsrikul A,Kocijancic S,Suppharangsan S. Effective Energy Consumption on Wireless Sensor Networks:Survey and Challenges[C]//Information & Communication Technology Electronics & Microelectronics(MIPRO),2013 36th International Convention on. IEEE,2013:469-473.

[2] Shenbagapriya R,Kumar N. A Survey on Proactive Routing Protocols in MANETs[C]//Science Engineering and Management Research(ICSEMR),2014 International Conference on. IEEE,2014:1-7.

[3] Patel D N,Patel S B,Kothadiya H R,et al. A Survey of Reactive Routing Protocols in MANET[C]//Information Communication and Embedded Systems(ICICES),2014 International Conference on. IEEE,2014:1-6.

[4] Cheng H,Cao J. A Design Framework and Taxonomy for Hybrid Routing Protocols in Mobile Ad Hoc Networks[J]. IEEE Communications Surveys & Tutorials,2008,10(3):62-73.

[5] Tassiulas L,Ephremides A. Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks[J]. IEEE Transactions on Automatic Control,1992,37(12):1936-1948.

[6] Jiao Z,Zhang B,Li C,et al. Backpressure-Based Routing and Scheduling Protocols for Wireless Multihop Networks:A Survey[J]. IEEE Wireless Communications,2016,23(1):102-110.

[7] Maglaras L A,Katsaros D. Delay Efficient Backpressure Routing in Wireless ad hoc Networks[J]. EAI Endorsed Transactions on Mobile Communications and Applications,2014,1(4):1-16.

[8] Zhou M,Jiao Z,Gong W,et al. Virtual Gradient Based Back-Pressure Scheduling in Wireless Multi-Hop Networks[C]//Communications(ICC),2015 IEEE International Conference on. IEEE,2015:3281-3286.

[9] Ji B,Joo C,Shroff N B. Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks[J]. IEEE/ACM Transactions on Networking(TON),2013,21(5):1539-1552.

[10] Jiao Z,Yao Z,Zhang B,et al. NBP:An Efficient Network-Coding Based Backpressure Algorithm[C]//Communications(ICC),2013 IEEE International Conference on. IEEE,2013:1625-1629.

[11] Jiao Z,Zhang B,Zhang H,et al. An Energy-Efficient Backpressure Routing and Scheduling Algorithm for Wireless Sensor Networks[C]//Global Communications Conference(GLOBECOM),2015 IEEE. IEEE,2015:1-6.

[12] 翟春杰,徐建閩,劉永桂. 基于分區(qū)的能耗均衡路由協(xié)議[J]. 傳感技術(shù)學(xué)報(bào),2016,29(1):80-87.

[13] Dhivya J,Vanithalakshmi M. A Survey of Backpressure Based Scheduling Algorithms for Delay Tolerant Networks[C]//Information Communication and Embedded Systems(ICICES),2014 International Conference on. IEEE,2014:1-5.

[14] Malhotra J. A Survey on MANET Simulation Tools[C]//Computational Intelligence on Power,Energy and Controls with Their Impact on Humanity(CIPECH),2014 Innovative Applications of. IEEE,2014:495-498.