无线传感器网络中基于延迟与能量平衡的背压调度算法*

王彬彬,周继鹏

(暨南大学信息科学技术学院,广州 510632)

无线传感器网络WSN(Wireless Sensor Network)[1]是一种现代网络技术,主要由一些传感节点和基站构成。传感节点既能够读取数据,又可以发送数据到基站。基站则发挥了收集和整理获取的数据的作用。无线传感器网络最早开始应用于战场上的某些侦察活动。随后,无线传感器网络逐渐成为一种能够应用于多学科和多领域的新兴技术。研究者相继提出了一系列与之相关的通信协议和诸多类型的拓扑结构。有效应用于森林火灾的检测,天气预报等特定情景。作为无线网络中一种没有固定基站的动态网络,无线传感器网络路由协议在某些细节上区别于Ad hoc网络路由协议。Ad hoc网络路由最重要的功能是决定源节点与目的节点之间的路径。当节点间传输范围超过一跳距离时,将需要通过中继节点的支持。从源节点到目的节点的数据包的传输有3种类型的协议。分别为先验式路由协议[2],反应式路由协议[3],以及混合路由协议[4]。此外,传感器网络面临的最大问题是能量受限。这是由传感节点的体积小,内存小,电池小,以及微处理器等结构因素造成。

由于无线媒介的共享属性,无线网络中资源分配是十分复杂的。背压算法BP(Backpressure)作为一种特殊的资源分配算法,最早在文献[5]中提出。背压算法是基于李雅普诺夫漂移理论(Lyapunov Drift theory),且涉及到协议栈中的MAC层和路由层。背压算法中最显著的属性是吞吐量最优化(Throughput-optimal)。也就是说,通过背压算法获得的调度策略能够支持任何到达的传输速率。而且对于网络拓扑的随机变化具有很强的鲁棒性。背压算法的性能在很低的网络负载条件下表现的很糟糕,因为数据包可能在网络中出现不断的循环。背压算法为了稳定整个系统将会尽可能应用网络中所有可能的路径。这个机制的后果是会增加延迟和中继节点能量的消耗。在这种类型的网络中,数据包的传输和调度的根本目标是完成预定的服务质量QoS(Quality of Service)。服务质量主要通过数据包的平均延迟和节点能量来度量。延迟和能量又是内部相关的,数据包在网络系统中存在的平均时间越小,意味着数据包到达终点的跳数越小,也就是说,总的能量消耗的减少。本文将主要研究延迟与能量之间更加具体的内在联系。

1 相关工作

原始的背压概念引起了随后在这个领域的广泛研究。文献[6]对已有的相关背压算法作出了比较综合的分析。背压算法有很多优异的特性,例如吞吐量最优化,能够实现的可适应资源分配,支持敏捷的负载感知路由和简单化。但是,背压算法在实际场景地应用中仍然存在一些亟待解决的问题,包括集中式控制模式,糟糕的延迟性能,极高的计算复杂度和队列复杂度。并将现有主要的研究领域划分为三类,怎样实现预期的延迟性能,怎样减小节点的队列复杂度和怎样完成有效的跨层设计。文献[7],利用背压类型的算法处理延迟效率问题。文中提出两种算法,一种是VoBP,减轻数据包调度的乒乓效应。另一种是LBP,将节点分层,运用层的标号进行背压调度实现将数据包传送到目的节点的目标。文献[8],在无线多跳网络中,对于支持有效的背压调度,主要实现了显著的延迟性能的优化。通过提出一个基于背压调度的虚拟梯度(VBR),在网络中提前建立虚拟队列梯度和使得每个节点在进行调度决策时进行考虑这个虚拟队列。结果显示,VBR就在传送率和平均的端到端延迟方面能够完成明显的性能提升。文献[9],提出一个基于延迟的背压调度(DBP)方案,这是一个在多跳无线网络中带有固定路由的算法。引入一个适应于多跳流量的延迟度量。在队列长度和延迟之间建立线性关系。DBP围绕最后包问题提供了一个简单的方式,避免流没有数据包的问题。因此,在基于队列的背压算法下,某些流经历的过度的长的延迟将会消除,而且没有任何吞吐量的丢失。文献[10],主要是通过提出一个基于背压的有效网络编码算法(NBP)。NBP引进内部流网络编码去提高传统的背压算法的性能,当被用作调度数据包传输。并且,证明了它的稳定性。结果表明,NBP在延迟性能和传送队列长度带有低的额外存储代价上相对于传统的背压算法性能更优越。文献[11],提出了EBP。这是一个对于传感器网络的能量有效的背压路由和调度算法。其中,设计了一个新的链路权计算方法。在这个新的方法中,链路权大小不仅由节点的队列长度决定,而且要考虑它们的能量状态。在EBP中,数据包将会被更多的传送到更多剩余能量的节点,同时,背压算法的吞吐量最优化依然能够保证。

Ad hoc网络领域中,存在大量关于Backpressure算法的学术研究。其中,大多数焦点都集中在网络节点端到端的延迟,队列结构的复杂度等主要方面。同样,在无线传感器的研究领域中,研究的方向倾向于关注能量的消耗。文献[12]通过设计一种基于分区的关于能耗均衡路由协议,使得网络中的节点能耗达到了均衡的目的,从而增强了网络的稳定性。算法比较全面考虑节点剩余能量、簇内的节点的能量均衡和簇内的总的能耗3个因素。实验结论表明该算法能够比较好地均衡节点的能耗和增强网络的稳定性。在这样的背景下,我们希望在某种情况下,能够在保持在数据包吞吐量最大化的前提下,确保端到端的延迟最小化,同时通过能量的有效利用,保证网络系统寿命的最大化。因此我们提出基于延迟和能量平衡的改进的背压调度算法BBP(Balanced Delay and Energy on Backpressure Scheduling Algorithm)。

本文的主要贡献包括:①提出一种新的延迟和能量相关的改进背压调度算法。在一定程度上提高了现有相关算法的性能。②对所提出的算法进行了实验仿真。

本文的剩余部分组织如下。第2部分将描述系统模型。第3部分首先回顾了原始背压算法。然后提出了我们自己改进的算法。第4部分,我们将仿真提出的算法。总结将在最后一部分完成。

本文使用的符号如表1所示。

表1 符号表

2 系统模型

我们假定一个无线网络G=(V,L),其中G代表有向图,V是图中所有节点的集合,L代表图中的所有链路集合。节点是无线传输和接收器。节点是静止的,通信链路是双向的,并且以多跳形式进行通信。在直接通信的情况下,链路是节点之间的无线信道。所有节点的配置都是相同的,例如能量值,能量消耗因素等。时间是分时,t是每个时隙的值。当节点正在发送数据包时,位于其通信范围内的所有节点都不能从其他节点接收数据包。在系统[10]中的一跳干扰模型被使用,即当两个链路彼此干扰时,它们将处于一跳范围内。一个节点不能够同时发送和接收数据包。数据包具有平均到达率λ。每个数据包的源节点是在所有节点中随机选择,目的节点是确定的。

3 算法描述

3.1 原始背压算法

在原始背压算法中[7,13],每个节点根据数据包去往目的地的不同来分别维持一个队列。通过计算两个节点之间的队列长度的差值,可以决策出拥有相对更大的权值的链路将会被调度。因此,背压调度是一个链路调度而不是数据包调度。至于这个算法为什么称之为背压,是因为它拥有可以被调度的最大流权,就好像数据包是被压力推到目的地。

在一个有N个节点的多跳无线网络中,网络系统是分时的。背压算法的调度和路由操作在每个时隙中完成。完整的背压操作如下所示。

①计算链路权值

首先,对于链路(m,n),在m,n节点之间计算队列值差,d是目的节点。m和n节点是网络系统中任意的两个邻居节点,网络流的方向是从m到n。

(1)

(2)

②选择调度链路

其次,完成如下的优化,

(3)

在式(3)中,其中Γ表示在一跳干扰模型下的可调度链路集合。μmn是传输速率。μ*(t)是最优的传输链路的集合。

③选择路由路径

④举例说明

如图1所示,是一个简单的无线多跳网络。A,B,C,D是网络中的4个节点,网络的方向如箭头指向所示。数值(商品中的值)是节点在此时维护的队列长度,分别为Qfull(t),Qstripe(t)和Qblank(t)。通过上述的步骤,我们可以得到三条链路(A,B),(A,C),(A,D)的权值,如下:

假定,链路(A,B),(A,C),(A,D)的传输速率分别为μAB(t)=2,μAC(t)=4,μAD(t)=1。同时,在时隙t,链路集{(A,C)}内部链路集合不会相互干扰。相似的,{(A,C)},{(A,D)} 与{(A,B)}有相同的属性。接下来,计算 Σμ(t)w(t):

图1 一个简单的无线多跳网络

3.2 算法设计

BBP算法设计并应用于无线传感器网络。在无线传感器网络中,数据包流都移动到汇聚节点。因此,汇聚节点就是目的节点。根据原始背压算法的设计,在这个网络系统中将只会有一条流。网络系统流的复杂度相对小一点。在网格网络系统中,网络中的数据包将会记录最近一次经过的节点的信息。每个节点的队列将会通过参数维护两个信息。一个是剩余能量的信息,另一个是数据包浏览该节点邻居节点的记录。通过考虑这两个参数,得到我们的调度算法。

我们设计调度算法的最初目的是确保最佳的系统吞吐量,并希望数据包花费最少的时间通过节点到达目的地。而且我们要求路径简单,同时网络系统是合理的利用节点能量,尽可能实现延迟成本与能量使用之间的平衡。也就是说,为了保证延迟效果的前提,并且不会出现太多的死节点。我们一直致力于这两个方面,尽我们最大的努力取得最好的效果。

我们参考文献[7],这给了我们很大的启发。在我们的BBP算法中,我们使每个数据包能够记录上次访问的节点信息。我们收集这个信息是用于阻止数据包在调度阶段在网络中出现回环。在无线传感器网络中,每个节点仅仅维护一个队列。因为数据包是根据其到达的目的地来划分,正如上述提到的汇聚节点,所有的节点将会被传送至汇聚节点。每一个节点的队列形成一个计数器C相对其所有的邻居节点。举个例子,节点m根据其要到达的目的节点d形成一个队列,该队列将会用计数器Cmnd记录它的邻居节点n的信息。也就是说,节点m的队列会根据不同的邻居节点维护多个计数器C。这个计数器与我们随后的调度算法有关。计数器具体操作如下。当一个数据包p从节点m经过节点n去往目的节点d。两个节点m和n的计数器将会改变。当数据包在节点n时,Cnmd(此时,m是节点n的一个邻居节点)在节点n将会加1。在节点m的计数器Cmnd将会减1。数据包同样会更新和记录它最近一次浏览过的节点。BBP算法在每个时隙执行以下步骤。我们假定节点n是节点m的其中一个一跳范围内的邻居节点。节点m是网络系统中任意一个节点。Ne是节点m的一跳范围内所有邻居节点的集合。首先,队列选择一个最坏的邻居节点Bmnd,这是节点m所有邻居节点Ne中Cmnd最大的值。根据,

(4)

在式(4)中,Bmnd是最坏的邻居节点的值。随之,参数αmnd形成,

(5)

在式(5)中,α是一个常量,我们将其设置为2,是通过大量的仿真结果。αmnd受到约束条件的限制。

其中,参数αmnd的形成过程如下:

参数αmnd:

1.节点m根据到达的目的节点d维护其邻居节点n一个计数器Cmnd

2.数据包p到达节点n时,节点n的计数器Cnmd加1;节点m的计数器Cmnd减1

3.根据式(4),选择一个最坏的邻居

4.式(5)则为参数αmnd

每一个节点有一个固定的初始能量Efull(除了汇聚节点,汇聚节点的能量是无限的。),一个节点的剩余能量是Eresidual。我们同样使得在网络中的每个节点的队列维护一个计数器Dmnd对于它的相应的邻居节点集合Ne中的每一个节点,记录剩余能量。具体的操作如下,节点m将会记录它的邻居节点n的Dmnd。

(6)

在式(6)中,我们设置k=3。常数k的选择需要大量的实验决定,正如参数α的值。

我们使,

(7)

在式(7)中,βmnd是另一个关于我们调度算法的参数。Ne是节点m的邻居节点的集合。其中剩余能量率v是,

(8)

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

其中,参数βmnd的形成过程如下,

参数βmnd:

1.每个节点维护一个计数器Dmnd对于相应的邻居节点

2.根据式(6),节点m记录邻居节点n的Dmnd

3.根据式(7),得到βmnd

我们描述了如上在BBP算法中两个参数αmnd和βmnd。得到我们的调度算法的权值计算公式,

(9)

式(9)是我们BBP算法的公式。通过这个公式,可以选择路由路径通过新的链路调度算法。我们做一个简单的分析,当

(10)

也就是说,节点n不是一个坏节点。在条件(10)中,βmnd的值越大,链路(m,n)被选择的概率就越高。也就是,节点剩余越多的能量,节点被选择的概率就越大。

BBP调度算法的伪代码描述如下,

算法BBP:

while(m,n)在L中

Output:从节点m到节点n以速率μmn传输商品d

进入时隙t+1(下一个时隙)

end while

end while

4 仿真结果

文献[14]比较了一些常用的仿真工具,我们选择了NS3(https://www.nsnam.org/)来对提出的算法进行仿真。文献[15]很详细地描述了原始背压算法的实现过程,这给了我们的实验完成提供了很大的帮助。NS3是一个基于离散事件的网络仿真工具,其主要的目的是用于科学研究和教学。NS3是一个自由开放源码的软件,基于GNU GPLv2许可,可以公开的获取用于研究,开发和使用。

我们的实验是基于ns-3.25的开发环境。测试网络是一个5×5的网格网络,有25个网络节点。实验的环境即为中小型网络,更大型的网络将是下一步的研究内容。仿真时间为1 000个时隙。链路容量为1packet/slot。通过比较传统背压算法(BP)与VOBP,EBP,BBP的吞吐量,平均延迟和剩余能量率。我们得到如下图所示的结果。我们设置到达速率λ为0.6,0.8,1.0,1.2,1.4 packets/slot来比较吞吐量和剩余能量率的性能。设置到达速率为[0,0.6]packets/slot来比较BP与其他3个优化算法的平均延迟。其中,传感节点的初始能量为300 J。每处理一个数据包节点消耗能量1.5 J。

比较吞吐量的性能可以得到图2,结果可以看出随着到达速率λ的不断增加,3个改进BP算法的网络吞吐量性能都略优于原始BP算法。3个改进的BP算法都能够确保最优的吞吐量。但是吞吐量性能在不同的λ时都有可能更优。这是由于改进后的背压算法都能保持原始背压算法的特性,即吞吐量最优化。但是当包含其他特性,如延迟改进等会增加一点吞吐量量性能的不稳定性。实验结果满足我们的要求,也就是无线传感器网络的吞吐量最优化。

图2 吞吐量性能比较

比较平均延迟的性能得到图3,3个改进的BP算法的性能在不同的到达速率λ时明显优于原始BP算法。BBP算法在某些λ时与VOBP算法的性能差不多。造成这种现象的原因是VOBP算法是小型网络延迟性能比较突出的算法。所以BBP算法中延迟部分细节参考VOBP。但是同时BBP算法又考虑了能量的消耗问题,所以延迟效果不会比VOBP算法优化太多。系统必须将能量因素考虑在内,因为能量与延迟的平衡是极其重要的。但是BBP算法的延迟性能是优于EBP算法的。这是因为EBP延迟没有考虑到延迟部分。

图3 平均延迟性能比较

图4 剩余能量率性能比较

比较剩余能量率性能得到图4,在4个背压算法间比较了整个系统的剩余能量率。从结果中可以得到,BBP和EBP比其他两个算法的性能更优。同时,在我们的仿真中BBP比EBP表现的更好。这是因为VOBP,BP没有考虑能量的利用,所以能量消耗的较多。从图中可以知道,BBP的剩余能量率在不同的λ时,都大于其他3个背压算法。

最后,可以得出结论,在某种程度上,即中小型网络下,BBP不仅减小了延迟,延迟效果优于EBP,VOBP算法。同时又有效的利用能量,能量利用优于VOBP,EBP算法。但是两个因素之间又相互制约,达到某种程度的平衡。

5 总结

本文在无线传感器网络的环境下,提出一种改进的背压算法。我们的实验结果表明,BBP算法的提出在特定的场景即中小型网络下可以确保吞吐量最优化的同时,能够减少延迟和保证能量的合理运用。至于,能否适用于其他不同的环境和进一步算法优化将是我们下一步的工作。

[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] 翟春杰,徐建闽,刘永桂. 基于分区的能耗均衡路由协议[J]. 传感技术学报,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.