分簇拓撲下Backpressure算法的延遲性改進研究

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

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

分簇拓撲下Backpressure算法的延遲性改進研究

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

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

Backpressure算法是一種自適用的路由調度算法，它從理論上解決throughput-optimal問題，但是在實際網絡部署中，存在節(jié)點維護數據隊列的數量繁多和數據路由繁長問題，致使數據傳輸延遲較長。針對這一問題，把Backpressure算法應用到分簇拓撲上，使用Shadow算法實現Backpressure算法下的路由調度，采用LIFO策略調度隊列，同時又對路徑選擇做了優(yōu)化。仿真結果表明，數據傳輸的延遲性大大降低。

分簇拓撲;Backpressure算法;Shadow算法;LIFO調度

1 Backpressure算法描述

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

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

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

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

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

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

每條鏈路上的數據傳輸速率必須滿足下式

任意節(jié)點i上的數據傳輸速率滿足下式

式中的節(jié)點i≠ef，當i=ef時，lbf=i=1，否則，其值為0。

Backpressure算法根據式（1）～式（3）的約束條件，從擁塞控制和科學調度上分配網絡資源，提高網絡資源利用的公平性。

1）擁塞控制，實現數據的輸入速率控制。在時隙t起始階段，根據式（4）計算出流f的最佳瞬時速率xf（t）

2）網絡資源分配和調度，實現數據在節(jié)點間的路由和轉發(fā)速率。在時隙t的起始階段，節(jié)點i根據（5），為每個數據包的發(fā)送選出路徑和速率

式中:π*（t）就是網絡中所有可被調度速率和相應鏈路的集合，當不滿足式（5）時，接收到的數據包就緩存到節(jié)點的數據隊列中，等待下一時隙的計算。

2 分簇拓撲結構下Backpressure算法的改進

Backpressure算法的優(yōu)勢在理論上是可行的，但是其需要集中式的控制信息，網絡資源開銷及計算復雜度較大，并且當網絡負載較輕時，會導致數據傳輸盲目而無序，都使得較數據傳輸的延遲較長，很難在實際中應用。本文對此算法進行分布式改進。就是把Backpressure算法擴展到分簇拓撲結構上，文獻［10］也提出了類似的改進，但是它只注重減少每個節(jié)點維護的數據隊列，沒有考慮數據傳輸的延遲問題。

2.1 網絡拓撲分簇分析

選用科學的分簇算法，能夠節(jié)省網絡的能耗，進而延長網絡壽命。因為本文的重點是對Backpressure算法的改進和應用，就省略網絡的成簇過程?，F在假設網絡利用高效的分簇算法，把N個節(jié)點均勻分布成K個簇組，如圖2所示。

圖2 節(jié)點分簇拓撲

每個簇首節(jié)點最多只要維護本簇內的（N/K-1）個簇內節(jié)點和（K-1）個簇首的Backressure信息，每個簇內節(jié)點只要維護本簇內（N/K-1）節(jié)點的Backpressure信息，而傳統(tǒng)Backpressure算法下每個節(jié)點維護都要維護其他（N-1）個節(jié)點的Backpressure信息。可知，分簇后每個節(jié)點所要維護的其他節(jié)點數量由理論上的（N-1）變?yōu)椋∟/K-1）（簇內節(jié)點）和（K-1）（簇頭）。

2.2 節(jié)點通信

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

2.2.1 Shadow算法下的Backpressure調度

Shadow算法就是利用一組虛擬的隊列維護網絡的數據流控制和資源分配，這個虛擬隊列實際上就是節(jié)點中的每個實際隊列的計數值。這些計數值充當網絡通信的令牌（token），控制數據包的接收和轉發(fā)。此算法最初是由文獻［8］應用到無線網絡中，用來提高多播網絡的效益，但是并沒有應用到數據傳輸的延遲問題上。本文主要用以解決無線網絡數據傳輸的延遲問題。

當網絡分簇后，網絡通信分兩部分:簇內通信和簇間通信。其中簇內通信注重簇內節(jié)點的調度，簇間通信還涉及到路由和轉發(fā)。因此Shadow算法下的Backpressure調度分上述兩部分進行。

簇內Shadow算法下的Backpressure調度:簇內節(jié)點維護一個LIFO隊列用來緩存采集的數據，和一個相應的Shadow隊列，簇頭節(jié)點分別為與之直接通信的節(jié)點（包括簇內節(jié)點和相鄰的簇頭節(jié)點）維護單獨的Shadow隊列。在時隙起始階段，根據下式

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

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

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

式中:fn表示由簇頭n轉發(fā)過來的數據流，當滿足式（7）中時，則Shadow隊列和真實數據隊列就以此鏈路和相應的速率進行路由/調度。

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

2.2.2 LIFO隊列調度策略

LIFO調度策略能夠很好地解決數據包傳輸的延遲問題［11］。假設在一個時隙系統(tǒng)中，t∈1，2，…，N，時隙為T。任意節(jié)點i所維護的隊列qi（t）滿足下式

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

在FIFO調度策略下，總共傳輸的隊列總長度為L（L?M×r），則每個數據包的平均延遲為

當L→∞時，式（9）結果為（M+1）T。

因為（M+1）T≥T，所以當應用LIFO調度策略時，只需要犧牲較小的代價，就可以換回較短的延遲效果。

3 實驗仿真

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

仿真結果如圖3所示，通過傳統(tǒng)Backpressure和Backpressure+Cluster的仿真比較還能發(fā)現，當Backpressure算法應用到分簇拓撲上時，使得進行路由的簇頭內的數據隊列能夠在較短時間內達到Backpressure算法下數據積壓值的要求，可以有效地解決網絡輕載情況下的路由調度問題，提高了網絡傳輸的效率。同時隨著數據流達到率的增高、網絡負荷的提高，本文提出的改進策略對數據傳輸延遲減小的優(yōu)勢逐漸表現出來。

圖3 端到端平均時延

4 小結

Backpressure算法在無線多跳網絡的應用能夠兼顧到整體網絡資源分配問題，達到吞吐量最大化目標。本文把Backpressure算法應用到分簇拓撲上，減少了每個節(jié)點所要維護的信息量;采用Shadow算法實現Backpressure算法的路由/調度，減輕了每個節(jié)點的Backpressure控制信息的計算;用LIFO隊列代替FIFO隊列，加快了數據隊列的調度;提出的路由優(yōu)化，避免了包的不必要的傳輸路徑。以上幾個方面分別從計算復雜、路由調度、路徑選擇上減少了包的延遲。通過仿真證明本文提出的改進方法大大降低了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

【本文獻信息】彭超，劉玉英，王飛，等.分簇拓撲下Backpressure算法的延遲性改進研究［J］.電視技術，2013，37（3）.

徐州市科技計劃項目（XX10A001）

彭 超，碩士生，主要研究方向為無線傳感器網絡;

劉玉英，碩士生導師，主要研究方向為無線通信技術等;

王 飛，碩士生，主要研究方向為數據挖掘。

責任編輯:任健男

2012－09－20