分簇拓扑下Backpressure算法的延迟性改进研究

彭 超，刘玉英，王 飞，王 鹤

（中国矿业大学信息与电气工程学院，江苏徐州 221116）

分簇拓扑下Backpressure算法的延迟性改进研究

彭 超，刘玉英，王 飞，王 鹤

（中国矿业大学信息与电气工程学院，江苏徐州 221116）

Backpressure算法是一种自适用的路由调度算法，它从理论上解决throughput-optimal问题，但是在实际网络部署中，存在节点维护数据队列的数量繁多和数据路由繁长问题，致使数据传输延迟较长。针对这一问题，把Backpressure算法应用到分簇拓扑上，使用Shadow算法实现Backpressure算法下的路由调度，采用LIFO策略调度队列，同时又对路径选择做了优化。仿真结果表明，数据传输的延迟性大大降低。

分簇拓扑;Backpressure算法;Shadow算法;LIFO调度

1 Backpressure算法描述

网络效益是评价网络性能最重要的标准。由于无线网络的资源受限特点，使得在设计阶段首要考虑的就是网络资源分配问题。Backpressure算法是由Tassiulas and Ephremides提出的一种资源分配算法［1］，并从理论上证明此算法可以实现throughput-optimal问题。经过多年的研究，此算法从局部的网络资源优化应用到全局资源优化的跨层（传输层到MAC层）设计［2-4］上。

Backpressue在无线网络的应用中，通过一系列的资源分配策略，可以在所有可用路径上为每个节点的数据传输选用最佳的路径。但是在实际实施过程中的实用性、有效性问题仍有待解决［5-7］。因为每个节点要为每个数据流维护单一的数据队列，当部署的网络规模绞大，传输数据量较大时候，节点开销和计算复杂度都会曾大。同时，Backpressure算法在数据传输的路径选择上会出现“环形”路径和冗长路径（见图1）。这些都会使数据传输的延迟增大。本文针对上述问题，对此算法进行改进，降低节点的资源开销和优化路由路径，减少数据传输延迟为目的。

图1 环形和冗长路径

Backpressure算法是一种在Lyapunov drift theory下所实现的系统稳定调度策略基础上，用来提高整体网络性能的算法［8］。它的运行条件就是源节点到目的节点之间的节点的数据积压差呈层次性的变小，这些积压差值可以转换为网络的效用和惩罚信息。根据这些惩罚信息（数据积压差分值和链路状态），节点可以自适用地控制数据流速率、包的路由和转发［9］。

算法具体实现过程:一个离散随机系统，N代表节点集合，F代表数据流集合，L代表链路集合，r（i，j）代表链路（i，j）上的传输速率，rf（i，j）代表链路（i，j）上流f的传输速率，C（i，j）代表链路（i，j）上的最大传输能力，qfi（t）代表节点i上的流f的队列长度，b（f）代表流f的源节点，ef代表流f的目的节点，x（f）代表流f在源节点上输入速率，Uf（xf）代表网络的效益函数。

系统中任意节点i的队列qi（t）必须满足下式

每条链路上的数据传输速率必须满足下式

任意节点i上的数据传输速率满足下式

式中的节点i≠ef，当i=ef时，lbf=i=1，否则，其值为0。

Backpressure算法根据式（1）～式（3）的约束条件，从拥塞控制和科学调度上分配网络资源，提高网络资源利用的公平性。

1）拥塞控制，实现数据的输入速率控制。在时隙t起始阶段，根据式（4）计算出流f的最佳瞬时速率xf（t）

2）网络资源分配和调度，实现数据在节点间的路由和转发速率。在时隙t的起始阶段，节点i根据（5），为每个数据包的发送选出路径和速率

式中:π*（t）就是网络中所有可被调度速率和相应链路的集合，当不满足式（5）时，接收到的数据包就缓存到节点的数据队列中，等待下一时隙的计算。

2 分簇拓扑结构下Backpressure算法的改进

Backpressure算法的优势在理论上是可行的，但是其需要集中式的控制信息，网络资源开销及计算复杂度较大，并且当网络负载较轻时，会导致数据传输盲目而无序，都使得较数据传输的延迟较长，很难在实际中应用。本文对此算法进行分布式改进。就是把Backpressure算法扩展到分簇拓扑结构上，文献［10］也提出了类似的改进，但是它只注重减少每个节点维护的数据队列，没有考虑数据传输的延迟问题。

2.1 网络拓扑分簇分析

选用科学的分簇算法，能够节省网络的能耗，进而延长网络寿命。因为本文的重点是对Backpressure算法的改进和应用，就省略网络的成簇过程。现在假设网络利用高效的分簇算法，把N个节点均匀分布成K个簇组，如图2所示。

图2 节点分簇拓扑

每个簇首节点最多只要维护本簇内的（N/K-1）个簇内节点和（K-1）个簇首的Backressure信息，每个簇内节点只要维护本簇内（N/K-1）节点的Backpressure信息，而传统Backpressure算法下每个节点维护都要维护其他（N-1）个节点的Backpressure信息。可知，分簇后每个节点所要维护的其他节点数量由理论上的（N-1）变为（N/K-1）（簇内节点）和（K-1）（簇头）。

2.2 节点通信

传统Backpressure算法中的每个节点为每个数据流维护一个单独的数据队列。而本文中的每个簇内节点只维护一个接收源数据的队列，每个簇头节点维护一个接收源数据的队列和接收从其他簇头节点转发的数据的各个单独的队列，也就是说每个簇首节点最多维护K（簇组数）个数据队列。这样可以减少每个节点所要维护的数据队列量，减少节点的开销和调度复难度。每个队列采用LIFO调度策略，它可以直接运用到Backpressure算法上，不需要对此作任何修改，同时使用Shadow算法实现Backpressure算法下的LIFO数据队列的路由/调度。

2.2.1 Shadow算法下的Backpressure调度

Shadow算法就是利用一组虚拟的队列维护网络的数据流控制和资源分配，这个虚拟队列实际上就是节点中的每个实际队列的计数值。这些计数值充当网络通信的令牌（token），控制数据包的接收和转发。此算法最初是由文献［8］应用到无线网络中，用来提高多播网络的效益，但是并没有应用到数据传输的延迟问题上。本文主要用以解决无线网络数据传输的延迟问题。

当网络分簇后，网络通信分两部分:簇内通信和簇间通信。其中簇内通信注重簇内节点的调度，簇间通信还涉及到路由和转发。因此Shadow算法下的Backpressure调度分上述两部分进行。

簇内Shadow算法下的Backpressure调度:簇内节点维护一个LIFO队列用来缓存采集的数据，和一个相应的Shadow队列，簇头节点分别为与之直接通信的节点（包括簇内节点和相邻的簇头节点）维护单独的Shadow队列。在时隙起始阶段，根据下式

式中:S（j）代表以节点j为簇头的簇群集合，C（j）代表网络内簇头的集合，～qi（t）代表节点i上的Shadow队列长度。当一个簇头节点满足式（8），簇内节点i首先向簇头节点j进行Shadow信息交换，如果i中的Shadow队列长度小于～ri，j（t），则把i中的Shadow队列清空，然后i中的真实LIFO队列往j中的LIFO队列中传输同样多的数据包。

簇间Shadow算法下的Backpressure路由/调度:簇间通信不同与簇内通信，簇间通信是多跳的，需要路径的优化。文献［6］和文献［11］用到Shadow算法进行Backpressure多跳路由/调度，但是并没有考虑路由过程中的环路优化问题，难免产生环路和较长路径现象，增加数据传输的延迟。

在网络成簇过程中，为每个簇群的所有节点生成一个相同的常量Hi（i∈S（j）），表示簇群j内的数据传输到Sink最少跳数。当一个簇头的Hi=1时，接收到的数据就直接发送到Sink，不需要缓存到LIFO队列中。Shadow算法的执行过程中，把Hi作为一个参数进行Backpressure路由/调度，只选取离Sink更近的簇头作为下跳节点，可以有效地解决环形和较长路径的路由问题。计算公式如下

式中:fn表示由簇头n转发过来的数据流，当满足式（7）中时，则Shadow队列和真实数据队列就以此链路和相应的速率进行路由/调度。

上述的调度策略相比传统的Backpressure算法，需要额外维护Shadow队列，但是Shadow队列仅是实际队列的统计值，Shadow队列的收发过程只是这些统计值的相加减，从而降低了所要维护真实数据队列的复杂度。在执行过程中，只是在每个时隙的开始阶段或者结束阶段进行Shadow信息交换。式（7）又对传输路径进行了优化处理，这些都可以减少端到端的延迟时间。

2.2.2 LIFO队列调度策略

LIFO调度策略能够很好地解决数据包传输的延迟问题［11］。假设在一个时隙系统中，t∈1，2，…，N，时隙为T。任意节点i所维护的队列qi（t）满足下式

理想条件下Ai（t）=ui（t）=r，且qi（t）满足式（1），假设一个节点初始状态的队列长度是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个簇内节点。任一节点的数据到达速率是一个参数为λ的泊松流。假设每个激活的链路每个时隙只能传输一个数据包。簇内节点到簇头和簇头之间采用半双工方式传输。用不同的λ值下的数据包的平均延迟评价本文算法的的优劣，仿真时间是500 s。

仿真结果如图3所示，通过传统Backpressure和Backpressure+Cluster的仿真比较还能发现，当Backpressure算法应用到分簇拓扑上时，使得进行路由的簇头内的数据队列能够在较短时间内达到Backpressure算法下数据积压值的要求，可以有效地解决网络轻载情况下的路由调度问题，提高了网络传输的效率。同时随着数据流达到率的增高、网络负荷的提高，本文提出的改进策略对数据传输延迟减小的优势逐渐表现出来。

图3 端到端平均时延

4 小结

Backpressure算法在无线多跳网络的应用能够兼顾到整体网络资源分配问题，达到吞吐量最大化目标。本文把Backpressure算法应用到分簇拓扑上，减少了每个节点所要维护的信息量;采用Shadow算法实现Backpressure算法的路由/调度，减轻了每个节点的Backpressure控制信息的计算;用LIFO队列代替FIFO队列，加快了数据队列的调度;提出的路由优化，避免了包的不必要的传输路径。以上几个方面分别从计算复杂、路由调度、路径选择上减少了包的延迟。通过仿真证明本文提出的改进方法大大降低了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