彭 超，劉玉英，王 飛，王 鶴

（中國礦業(yè)大學(xué)信息與電氣工程學(xué)院，江蘇徐州 221116）

分簇拓?fù)湎翨ackpressure算法的延遲性改進(jìn)研究

彭 超，劉玉英，王 飛，王 鶴

（中國礦業(yè)大學(xué)信息與電氣工程學(xué)院，江蘇徐州 221116）

Backpressure算法是一種自適用的路由調(diào)度算法，它從理論上解決throughput-optimal問題，但是在實(shí)際網(wǎng)絡(luò)部署中，存在節(jié)點(diǎn)維護(hù)數(shù)據(jù)隊(duì)列的數(shù)量繁多和數(shù)據(jù)路由繁長問題，致使數(shù)據(jù)傳輸延遲較長。針對(duì)這一問題，把Backpressure算法應(yīng)用到分簇拓?fù)渖希褂肧hadow算法實(shí)現(xiàn)Backpressure算法下的路由調(diào)度，采用LIFO策略調(diào)度隊(duì)列，同時(shí)又對(duì)路徑選擇做了優(yōu)化。仿真結(jié)果表明，數(shù)據(jù)傳輸?shù)难舆t性大大降低。

分簇拓?fù)?Backpressure算法;Shadow算法;LIFO調(diào)度

1 Backpressure算法描述

網(wǎng)絡(luò)效益是評(píng)價(jià)網(wǎng)絡(luò)性能最重要的標(biāo)準(zhǔn)。由于無線網(wǎng)絡(luò)的資源受限特點(diǎn)，使得在設(shè)計(jì)階段首要考慮的就是網(wǎng)絡(luò)資源分配問題。Backpressure算法是由Tassiulas and Ephremides提出的一種資源分配算法［1］，并從理論上證明此算法可以實(shí)現(xiàn)throughput-optimal問題。經(jīng)過多年的研究，此算法從局部的網(wǎng)絡(luò)資源優(yōu)化應(yīng)用到全局資源優(yōu)化的跨層（傳輸層到MAC層）設(shè)計(jì)［2-4］上。

Backpressue在無線網(wǎng)絡(luò)的應(yīng)用中，通過一系列的資源分配策略，可以在所有可用路徑上為每個(gè)節(jié)點(diǎn)的數(shù)據(jù)傳輸選用最佳的路徑。但是在實(shí)際實(shí)施過程中的實(shí)用性、有效性問題仍有待解決［5-7］。因?yàn)槊總€(gè)節(jié)點(diǎn)要為每個(gè)數(shù)據(jù)流維護(hù)單一的數(shù)據(jù)隊(duì)列，當(dāng)部署的網(wǎng)絡(luò)規(guī)模絞大，傳輸數(shù)據(jù)量較大時(shí)候，節(jié)點(diǎn)開銷和計(jì)算復(fù)雜度都會(huì)曾大。同時(shí)，Backpressure算法在數(shù)據(jù)傳輸?shù)穆窂竭x擇上會(huì)出現(xiàn)“環(huán)形”路徑和冗長路徑（見圖1）。這些都會(huì)使數(shù)據(jù)傳輸?shù)难舆t增大。本文針對(duì)上述問題，對(duì)此算法進(jìn)行改進(jìn)，降低節(jié)點(diǎn)的資源開銷和優(yōu)化路由路徑，減少數(shù)據(jù)傳輸延遲為目的。

圖1 環(huán)形和冗長路徑

Backpressure算法是一種在Lyapunov drift theory下所實(shí)現(xiàn)的系統(tǒng)穩(wěn)定調(diào)度策略基礎(chǔ)上，用來提高整體網(wǎng)絡(luò)性能的算法［8］。它的運(yùn)行條件就是源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的節(jié)點(diǎn)的數(shù)據(jù)積壓差呈層次性的變小，這些積壓差值可以轉(zhuǎn)換為網(wǎng)絡(luò)的效用和懲罰信息。根據(jù)這些懲罰信息（數(shù)據(jù)積壓差分值和鏈路狀態(tài)），節(jié)點(diǎn)可以自適用地控制數(shù)據(jù)流速率、包的路由和轉(zhuǎn)發(fā)［9］。

算法具體實(shí)現(xiàn)過程:一個(gè)離散隨機(jī)系統(tǒng)，N代表節(jié)點(diǎn)集合，F(xiàn)代表數(shù)據(jù)流集合，L代表鏈路集合，r（i，j）代表鏈路（i，j）上的傳輸速率，rf（i，j）代表鏈路（i，j）上流f的傳輸速率，C（i，j）代表鏈路（i，j）上的最大傳輸能力，qfi（t）代表節(jié)點(diǎn)i上的流f的隊(duì)列長度，b（f）代表流f的源節(jié)點(diǎn)，ef代表流f的目的節(jié)點(diǎn)，x（f）代表流f在源節(jié)點(diǎn)上輸入速率，Uf（xf）代表網(wǎng)絡(luò)的效益函數(shù)。

系統(tǒng)中任意節(jié)點(diǎn)i的隊(duì)列qi（t）必須滿足下式

每條鏈路上的數(shù)據(jù)傳輸速率必須滿足下式

任意節(jié)點(diǎn)i上的數(shù)據(jù)傳輸速率滿足下式

式中的節(jié)點(diǎn)i≠ef，當(dāng)i=ef時(shí)，lbf=i=1，否則，其值為0。

Backpressure算法根據(jù)式（1）～式（3）的約束條件，從擁塞控制和科學(xué)調(diào)度上分配網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)資源利用的公平性。

1）擁塞控制，實(shí)現(xiàn)數(shù)據(jù)的輸入速率控制。在時(shí)隙t起始階段，根據(jù)式（4）計(jì)算出流f的最佳瞬時(shí)速率xf（t）

2）網(wǎng)絡(luò)資源分配和調(diào)度，實(shí)現(xiàn)數(shù)據(jù)在節(jié)點(diǎn)間的路由和轉(zhuǎn)發(fā)速率。在時(shí)隙t的起始階段，節(jié)點(diǎn)i根據(jù)（5），為每個(gè)數(shù)據(jù)包的發(fā)送選出路徑和速率

式中:π*（t）就是網(wǎng)絡(luò)中所有可被調(diào)度速率和相應(yīng)鏈路的集合，當(dāng)不滿足式（5）時(shí)，接收到的數(shù)據(jù)包就緩存到節(jié)點(diǎn)的數(shù)據(jù)隊(duì)列中，等待下一時(shí)隙的計(jì)算。

2 分簇拓?fù)浣Y(jié)構(gòu)下Backpressure算法的改進(jìn)

Backpressure算法的優(yōu)勢在理論上是可行的，但是其需要集中式的控制信息，網(wǎng)絡(luò)資源開銷及計(jì)算復(fù)雜度較大，并且當(dāng)網(wǎng)絡(luò)負(fù)載較輕時(shí)，會(huì)導(dǎo)致數(shù)據(jù)傳輸盲目而無序，都使得較數(shù)據(jù)傳輸?shù)难舆t較長，很難在實(shí)際中應(yīng)用。本文對(duì)此算法進(jìn)行分布式改進(jìn)。就是把Backpressure算法擴(kuò)展到分簇拓?fù)浣Y(jié)構(gòu)上，文獻(xiàn)［10］也提出了類似的改進(jìn)，但是它只注重減少每個(gè)節(jié)點(diǎn)維護(hù)的數(shù)據(jù)隊(duì)列，沒有考慮數(shù)據(jù)傳輸?shù)难舆t問題。

2.1 網(wǎng)絡(luò)拓?fù)浞执胤治?/h3>

選用科學(xué)的分簇算法，能夠節(jié)省網(wǎng)絡(luò)的能耗，進(jìn)而延長網(wǎng)絡(luò)壽命。因?yàn)楸疚牡闹攸c(diǎn)是對(duì)Backpressure算法的改進(jìn)和應(yīng)用，就省略網(wǎng)絡(luò)的成簇過程。現(xiàn)在假設(shè)網(wǎng)絡(luò)利用高效的分簇算法，把N個(gè)節(jié)點(diǎn)均勻分布成K個(gè)簇組，如圖2所示。

圖2 節(jié)點(diǎn)分簇拓?fù)?/p>

每個(gè)簇首節(jié)點(diǎn)最多只要維護(hù)本簇內(nèi)的（N/K-1）個(gè)簇內(nèi)節(jié)點(diǎn)和（K-1）個(gè)簇首的Backressure信息，每個(gè)簇內(nèi)節(jié)點(diǎn)只要維護(hù)本簇內(nèi)（N/K-1）節(jié)點(diǎn)的Backpressure信息，而傳統(tǒng)Backpressure算法下每個(gè)節(jié)點(diǎn)維護(hù)都要維護(hù)其他（N-1）個(gè)節(jié)點(diǎn)的Backpressure信息?？芍执睾竺總€(gè)節(jié)點(diǎn)所要維護(hù)的其他節(jié)點(diǎn)數(shù)量由理論上的（N-1）變?yōu)椋∟/K-1）（簇內(nèi)節(jié)點(diǎn)）和（K-1）（簇頭）。

2.2 節(jié)點(diǎn)通信

傳統(tǒng)Backpressure算法中的每個(gè)節(jié)點(diǎn)為每個(gè)數(shù)據(jù)流維護(hù)一個(gè)單獨(dú)的數(shù)據(jù)隊(duì)列。而本文中的每個(gè)簇內(nèi)節(jié)點(diǎn)只維護(hù)一個(gè)接收源數(shù)據(jù)的隊(duì)列，每個(gè)簇頭節(jié)點(diǎn)維護(hù)一個(gè)接收源數(shù)據(jù)的隊(duì)列和接收從其他簇頭節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)的各個(gè)單獨(dú)的隊(duì)列，也就是說每個(gè)簇首節(jié)點(diǎn)最多維護(hù)K（簇組數(shù)）個(gè)數(shù)據(jù)隊(duì)列。這樣可以減少每個(gè)節(jié)點(diǎn)所要維護(hù)的數(shù)據(jù)隊(duì)列量，減少節(jié)點(diǎn)的開銷和調(diào)度復(fù)難度。每個(gè)隊(duì)列采用LIFO調(diào)度策略，它可以直接運(yùn)用到Backpressure算法上，不需要對(duì)此作任何修改，同時(shí)使用Shadow算法實(shí)現(xiàn)Backpressure算法下的LIFO數(shù)據(jù)隊(duì)列的路由/調(diào)度。

2.2.1 Shadow算法下的Backpressure調(diào)度

Shadow算法就是利用一組虛擬的隊(duì)列維護(hù)網(wǎng)絡(luò)的數(shù)據(jù)流控制和資源分配，這個(gè)虛擬隊(duì)列實(shí)際上就是節(jié)點(diǎn)中的每個(gè)實(shí)際隊(duì)列的計(jì)數(shù)值。這些計(jì)數(shù)值充當(dāng)網(wǎng)絡(luò)通信的令牌（token），控制數(shù)據(jù)包的接收和轉(zhuǎn)發(fā)。此算法最初是由文獻(xiàn)［8］應(yīng)用到無線網(wǎng)絡(luò)中，用來提高多播網(wǎng)絡(luò)的效益，但是并沒有應(yīng)用到數(shù)據(jù)傳輸?shù)难舆t問題上。本文主要用以解決無線網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)难舆t問題。

當(dāng)網(wǎng)絡(luò)分簇后，網(wǎng)絡(luò)通信分兩部分:簇內(nèi)通信和簇間通信。其中簇內(nèi)通信注重簇內(nèi)節(jié)點(diǎn)的調(diào)度，簇間通信還涉及到路由和轉(zhuǎn)發(fā)。因此Shadow算法下的Backpressure調(diào)度分上述兩部分進(jìn)行。

簇內(nèi)Shadow算法下的Backpressure調(diào)度:簇內(nèi)節(jié)點(diǎn)維護(hù)一個(gè)LIFO隊(duì)列用來緩存采集的數(shù)據(jù)，和一個(gè)相應(yīng)的Shadow隊(duì)列，簇頭節(jié)點(diǎn)分別為與之直接通信的節(jié)點(diǎn)（包括簇內(nèi)節(jié)點(diǎn)和相鄰的簇頭節(jié)點(diǎn)）維護(hù)單獨(dú)的Shadow隊(duì)列。在時(shí)隙起始階段，根據(jù)下式

式中:S（j）代表以節(jié)點(diǎn)j為簇頭的簇群集合，C（j）代表網(wǎng)絡(luò)內(nèi)簇頭的集合，～qi（t）代表節(jié)點(diǎn)i上的Shadow隊(duì)列長度。當(dāng)一個(gè)簇頭節(jié)點(diǎn)滿足式（8），簇內(nèi)節(jié)點(diǎn)i首先向簇頭節(jié)點(diǎn)j進(jìn)行Shadow信息交換，如果i中的Shadow隊(duì)列長度小于～ri，j（t），則把i中的Shadow隊(duì)列清空，然后i中的真實(shí)LIFO隊(duì)列往j中的LIFO隊(duì)列中傳輸同樣多的數(shù)據(jù)包。

簇間Shadow算法下的Backpressure路由/調(diào)度:簇間通信不同與簇內(nèi)通信，簇間通信是多跳的，需要路徑的優(yōu)化。文獻(xiàn)［6］和文獻(xiàn)［11］用到Shadow算法進(jìn)行Backpressure多跳路由/調(diào)度，但是并沒有考慮路由過程中的環(huán)路優(yōu)化問題，難免產(chǎn)生環(huán)路和較長路徑現(xiàn)象，增加數(shù)據(jù)傳輸?shù)难舆t。

在網(wǎng)絡(luò)成簇過程中，為每個(gè)簇群的所有節(jié)點(diǎn)生成一個(gè)相同的常量Hi（i∈S（j）），表示簇群j內(nèi)的數(shù)據(jù)傳輸?shù)絊ink最少跳數(shù)。當(dāng)一個(gè)簇頭的Hi=1時(shí)，接收到的數(shù)據(jù)就直接發(fā)送到Sink，不需要緩存到LIFO隊(duì)列中。Shadow算法的執(zhí)行過程中，把Hi作為一個(gè)參數(shù)進(jìn)行Backpressure路由/調(diào)度，只選取離Sink更近的簇頭作為下跳節(jié)點(diǎn)，可以有效地解決環(huán)形和較長路徑的路由問題。計(jì)算公式如下

式中:fn表示由簇頭n轉(zhuǎn)發(fā)過來的數(shù)據(jù)流，當(dāng)滿足式（7）中時(shí)，則Shadow隊(duì)列和真實(shí)數(shù)據(jù)隊(duì)列就以此鏈路和相應(yīng)的速率進(jìn)行路由/調(diào)度。

上述的調(diào)度策略相比傳統(tǒng)的Backpressure算法，需要額外維護(hù)Shadow隊(duì)列，但是Shadow隊(duì)列僅是實(shí)際隊(duì)列的統(tǒng)計(jì)值，Shadow隊(duì)列的收發(fā)過程只是這些統(tǒng)計(jì)值的相加減，從而降低了所要維護(hù)真實(shí)數(shù)據(jù)隊(duì)列的復(fù)雜度。在執(zhí)行過程中，只是在每個(gè)時(shí)隙的開始階段或者結(jié)束階段進(jìn)行Shadow信息交換。式（7）又對(duì)傳輸路徑進(jìn)行了優(yōu)化處理，這些都可以減少端到端的延遲時(shí)間。

2.2.2 LIFO隊(duì)列調(diào)度策略

LIFO調(diào)度策略能夠很好地解決數(shù)據(jù)包傳輸?shù)难舆t問題［11］。假設(shè)在一個(gè)時(shí)隙系統(tǒng)中，t∈1，2，…，N，時(shí)隙為T。任意節(jié)點(diǎn)i所維護(hù)的隊(duì)列qi（t）滿足下式

理想條件下Ai（t）=ui（t）=r，且qi（t）滿足式（1），假設(shè)一個(gè)節(jié)點(diǎn)初始狀態(tài)的隊(duì)列長度是M×r（M≥1且M∈R+）。

在FIFO調(diào)度策略下，總共傳輸?shù)年?duì)列總長度為L（L?M×r），則每個(gè)數(shù)據(jù)包的平均延遲為

當(dāng)L→∞時(shí)，式（9）結(jié)果為（M+1）T。

因?yàn)椋∕+1）T≥T，所以當(dāng)應(yīng)用LIFO調(diào)度策略時(shí)，只需要犧牲較小的代價(jià)，就可以換回較短的延遲效果。

3 實(shí)驗(yàn)仿真

本文利用NS-2設(shè)計(jì)仿真程序。設(shè)置15×15柵格網(wǎng)絡(luò)，分成24 個(gè)簇群，其中 （i，j）/（8，8）（i，j∈2，5，8，11，14）是簇頭，（8，8）上是Sink，每個(gè)簇頭周邊有6個(gè)簇內(nèi)節(jié)點(diǎn)。任一節(jié)點(diǎn)的數(shù)據(jù)到達(dá)速率是一個(gè)參數(shù)為λ的泊松流。假設(shè)每個(gè)激活的鏈路每個(gè)時(shí)隙只能傳輸一個(gè)數(shù)據(jù)包。簇內(nèi)節(jié)點(diǎn)到簇頭和簇頭之間采用半雙工方式傳輸。用不同的λ值下的數(shù)據(jù)包的平均延遲評(píng)價(jià)本文算法的的優(yōu)劣，仿真時(shí)間是500 s。

仿真結(jié)果如圖3所示，通過傳統(tǒng)Backpressure和Backpressure+Cluster的仿真比較還能發(fā)現(xiàn)，當(dāng)Backpressure算法應(yīng)用到分簇拓?fù)渖蠒r(shí)，使得進(jìn)行路由的簇頭內(nèi)的數(shù)據(jù)隊(duì)列能夠在較短時(shí)間內(nèi)達(dá)到Backpressure算法下數(shù)據(jù)積壓值的要求，可以有效地解決網(wǎng)絡(luò)輕載情況下的路由調(diào)度問題，提高了網(wǎng)絡(luò)傳輸?shù)男?。同時(shí)隨著數(shù)據(jù)流達(dá)到率的增高、網(wǎng)絡(luò)負(fù)荷的提高，本文提出的改進(jìn)策略對(duì)數(shù)據(jù)傳輸延遲減小的優(yōu)勢逐漸表現(xiàn)出來。

圖3 端到端平均時(shí)延

4 小結(jié)

Backpressure算法在無線多跳網(wǎng)絡(luò)的應(yīng)用能夠兼顧到整體網(wǎng)絡(luò)資源分配問題，達(dá)到吞吐量最大化目標(biāo)。本文把Backpressure算法應(yīng)用到分簇拓?fù)渖?，減少了每個(gè)節(jié)點(diǎn)所要維護(hù)的信息量;采用Shadow算法實(shí)現(xiàn)Backpressure算法的路由/調(diào)度，減輕了每個(gè)節(jié)點(diǎn)的Backpressure控制信息的計(jì)算;用LIFO隊(duì)列代替FIFO隊(duì)列，加快了數(shù)據(jù)隊(duì)列的調(diào)度;提出的路由優(yōu)化，避免了包的不必要的傳輸路徑。以上幾個(gè)方面分別從計(jì)算復(fù)雜、路由調(diào)度、路徑選擇上減少了包的延遲。通過仿真證明本文提出的改進(jìn)方法大大降低了Backpressure算法的傳輸延遲特性。

:

［1］TASSIULAS L，EPHREMIDES A.Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks［J］.IEEE Trans.Automatic Control，1992，12（37）:1936-1949.

［2］SRIDHARAN A，MOELLER S，KRISHNAMACHARI B.Investigating Backpressure-based rate control protocols for wireless sensor networks［EB/OL］.［2012-06-20］.http://anrg.usc.edu/～ asridhar/papers/brcp.pdf.

［3］SRIDHARAN A，MOELLER S，KRISHNAMACHARI B.Implementing Backpressure-based rate control in wireless networks［EB/OL］.［2012-05-15］.http://www.techrepublic.com/whitepapers/implementingbackpressure-based-rate-control-in-wireless-networks/2378173.

［4］WEERADDANA P C，CODREANU M，LATVA-AHO M，et al.Resource allocation for cross-layer utility maximization in wireless networks［J］.IEEE Trans.Information Theory，2011，60（6）:2790-2809.

［5］SZWABE A，MISIOREK P.Integration of multi-path optimized link state protocol with max-weight scheduling［C］//Proc.IEEE International Conference on Information Multimedia Technology（ICIMT）.［S.l.］:IEEE Press，2009:458-462.

［6］BUI L，SRIKANT R，STOLYAR A.Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing［EB/OL］.［2012-05-15］.http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5062262&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5062262.

［7］JI B，JOO C，SHROFF N B.Delay-based back-pressure scheduling in multi-hop wireless networks［C］//Proc.IEEE INFOCOM 2011.Shanghai:IEEE Press，2011:2579-2587.

［8］BUI L，SRIKANT R，STOLYAR A.Optimal resource allocation for multicast sessions in multihop wireless networks［J］.Philosophical Transactions of the Royal Society Series A，2008，336（1872）:2059-2074.

［9］MOELLER S，SRIDHARAN A，KRISHNAMACHARI B，et al.Routing without routes:the Backpressure collection protocol［EB/OL］.［2012-05-15］.http://dl.acm.org/citation.cfm?id=1791246.

［10］YING L，SRIKANT R，TOWSLEY D.Cluster-based back-pressure routing algorithm［C］//Proc.IEEE INFOCOM.Phoenix，AZ，USA:2008:484-492.

［11］HUANG L，MOELLER S，NEELY M，et al.Lifo Backpressure achieves near optimal utility-delay tradeoff［C］//Proc.9th Int.Symposium on Modeling and Optimization in Mobile，Ad Hoc，and Wireless Networks，2011.Princeton，NJ:［s.n.］，2011:842-857.

Research on Delay Improving of Backpressure Algorithm on Cluster Topology

PENG Chao，LIU Yuying，WANG Fei，WANG He

（Information and Electronic College，China University of Mining and Technology，Jiangsu Xuzhou 221116，China）

Backpressure algorithm is an adaptive routing/scheduling algorithm，which addresses the problem of throughput-optimal theoretically.However，owing to the mount of real queues maintained at each node and the long routes，the transmissions have poor delay performance.In this paper，in order to solve for above issue，the Backpressure algorithm upon the cluster topology is implemented.Shadow algorithm is developed to achieve Backpressure schedule.LIFO policy is proposed to maintain and scheduling queues.Finally，the idea of optimizing transmission routes is explored.Simulation results show that the delay is reduced significantly.

cluster topology;Backpressure algorithm;Shadow algorithm;LIFO scheduling

TP391

A

【本文獻(xiàn)信息】彭超，劉玉英，王飛，等.分簇拓?fù)湎翨ackpressure算法的延遲性改進(jìn)研究［J］.電視技術(shù)，2013，37（3）.

徐州市科技計(jì)劃項(xiàng)目（XX10A001）

彭 超，碩士生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò);

劉玉英，碩士生導(dǎo)師，主要研究方向?yàn)闊o線通信技術(shù)等;

王 飛，碩士生，主要研究方向?yàn)閿?shù)據(jù)挖掘。

責(zé)任編輯:任健男

2012－09－20