无线传感网络中基于时延感知的背压路由∗

章万静

(1.江苏省软件测试工程技术研究开发中心，江苏 淮安 223003；2.江苏电子信息职业学院计算机与通信学院，江苏 淮安 223003)

无线传感网络(Wireless Sensor Networks，WSNs)已广泛应用于环境检测、康复医疗等应用领域[1－2]。 WSNs 中的节点具有感测数据、传输数据的能力。 传感节点先感测数据，然后将数据传输基站。因此，数据传输成为WSNs 研究热点之一。

近期，背压(Backpressure，BP)路由受到广泛关注[3]。 原始的 BP 算法起源于 Tassiulas 和Ephremides 提出的无线数据包多跳网络[4]。 BP 通过lyapunov drift 理论最大化网络效益，优化了吞吐量。

BP 路由就是通过节点间数据包队列的拥塞剃度处理路由流量。 与其他路由机制不同，BP 路由并不构建从源节点至目的节点间的具体路径，只是构建在每个时隙时的队列积压差。 BP 路由就是依据积压差决策路由，进而传输数据包。

相比于按需距离矢量路由(Ad hoc On-Demand Vector， ADOV) 和目的序列距离矢量路由(Destination Sequence Distance Vector，DSDV)等路由，BP 路由是通过节点间的数据包队列积压差决策路由，其存在以下优势:①最大化网络吞吐量；②对于拓扑变化的网络具有强的鲁棒性。 然而，尽管BP路由优化吞吐量，但是也存在时延、路径冗长问题。BP 路由最初需消耗一定时间形成队列积压梯度，这增加了数据包的传输时延。

文献[5]提出基于驻留时间的BP 改进路由。利用队列长度和数据传输时延计算数据包的驻留时间。 数据包在队列中驻留时间越长，数据包被优先传输的概率越高。 即优先传输驻留时间长的数据包，减少数据包在队列里的停留时间，进而降低数据传输时延。 文献[6]针对智能化WSNs，提出链路反转算法协助的BP 路由，进而降低数据包的传输时延。 文献[7]提出基于虚拟梯度的BP 路由，利用虚拟梯度缩短时延。 此外，文献[8]针对大型紧急物联网，提出基于最短路径的BP 改进路由，优先传输紧急数据包。

为此，针对BP 路由算法的传输时延问题，提出基于时延感知的背压路由 ( Delay-Aware Backpressure Routing，DABR)。 DABR 路由依据队列积压差计算链路权值，并优先激活权值大的链路，然后再优先传输驻留时间长的数据包，缩短数据传输时延。 仿真结果表明，提出的DABR 路由缩短数据传输时延，并提升了数据包传输成功率。

1 传统BP 路由不足及系统模型

1.1 BP 路由不足

图1 队列积压差示例

然而，只依据队列积压差决策路由有两个弊端:①节点需消耗较长时间形成数据包队列积压梯度；②若在在长时间内无法形成数据包队列积压梯度，节点就无法传输数据包。 在决策路由时，并没有考虑数据包在队列内驻留时间。

如图2 所示，图中有三个节点a，b，c。 在时隙t＝8 时，节点a，b，c 的队列内已存的数据包数分别为7，5、4。 若需要在链路(a，c)和(b，c)间选择一条链路传输数据包，它们的数据包队列积压差分别为2 和1。 依据传统的BP 路由，优先激活链路(a，c)。

图2 第一个数据包入队时间

这个过程并没有考虑到数据包在队列的驻留时间。 假定在节点a 队列中第一个数据包入队的时隙thead＝3；在节点b 队列中第一个数据包入队的时隙thead＝1。 显然，节点b 队列内的数据包驻留的时间更长。 但是传统的BP 路由并没有考虑到此问题。这就会增加数据包传输时延。

1.2 系统模型

将网络操作时间划分多个时隙，即t∈{0，1，2，…}。 在每个时隙t，DABR 路由就激活一条链路。利用有向图G＝(N，L)表示无线多跳网络，其中N表示节点集，L表示链路集。 位于源节点的数据包需贯穿多条链路[10]，并通过多跳通信才能达到目的节点。 用(i，j)表示节点i与节点j构成的链路。 流量fc表示流向目的节点c的流量。 而Qfci表示在节点i的流量队列。

2 DABR 路由

2.1 数据包的队列积压差

仍以图3 为例，节点i与节点j间的wi，j(t)＝6。

图3 无线多跳网络(t＝8)

2.2 数据包入列的驻留时间

式中:k表示数据包类型。 图3 给出了节点i三类数据包(1，2，3)的驻留时间，依据式(4)可得Qi(2)＝5。

2.3 链路权值

节点i依据式(5)计算一跳邻居节点集Ni内每个节点j∈Ni的链路权值:

式中:wi，j(t)μi，j值越大，链路单个时隙内能够传输的数据包数越大；μi，j表链路(i，j)的速率；选择具有最大链路权值的节点作下一跳转发节点，即优先激活最大链路权值的链路。

郑州航院乃至河南省的二本高校若要圆满实现中外合作办学的培养目标，培养更多高水平的国际化人才助力中原经济快速发展，英语是其无法避开的关键一环。中外合作办学的英语教学不仅要提高学生的语言学习效率、帮助学生取得语言通行证，而且还要培养学生适应国际化学习的能力、提升其跨文化沟通能力；同时也要调动教师的积极性，使项目内学生英语运用能力和专业学习能力的培养和发展得到保证。因此，在课程设置和课程建设方面与国际接轨势在必行。全面学习、重点借鉴美国高校针对母语非英语国家留学生的强化英语课程设置以及其课程建设对我省高校中外合作办学项目的英语教学十分有益。

2.4 数据包的传输

依据式(5)选择下一跳转发节点后，就激活此链路。 然后，节点i就依据式(4)选择队列中最长驻留时间的数据包传输。

2.5 传输数据包的示例

仍以图3 为例，阐述传输数据包的过程。 依据式(2)，可得表1 所示的链路的数据包队列积压差。假定μi，j＝4 packets/slot，μi，ℓ＝2 packets/slot。 首先选择活具有最大权值的链路，即链路(i，j)被激活，然后传输第二类数据包(k＝2)，如图3 所示。

表1 链路权值及驻留时间

2.6 基于BP 路由算法的实现

依据图4 所示的模块实现基于BP 路由，主要由数据包队列管理、邻居节点管理和下一跳节点选择三个模块组成。 数据包队列管理模块是用于调度数据包，包括入列和出列。

图4 路由算法的实现模块

而邻居节点管理是主要由邻居表的构建和Hello 消息的管理两个模块组成。 邻居表内包含节点的当前状态信息，如IP 地址和它所的拥有队列的长度。 而Hello 消息的管理负责Hello 消息的传输。

下一跳节点选择是依据节点拥有数据包的紧急程度，决策下一跳的传输。 DABR 路由是依据具有最大权值的节点作为下一跳传输节点。

3 性能分析

3.1 仿真环境

利用NS－3[12]仿真软件建立平台。 作为开源的离散事件网络仿真工具，NS－3 广泛应用于科学研究。 在μ＝1 packets/slot 网格内部署36 个节点，如图5 所示。 节点的通信半径为250 m。 具体的仿真参数如表2 所示。

图5 网格拓扑结构

表2 仿真参数

选择文献[13]提出的基于最短路径的背压路由(Shortest-path-based back-pressure routing，SPPR)和文献[14]提出的低时延多播背压路由(Lowlatency Multicast back-pressure Forwarding，LMPF)作为参照，并对比分析它们的数据包传递率、吞吐量和传输时延。

此外，通过类图实现了路由，如图6 所示，其主要包括以下四个类:①Routing Protocol 类:该类用于管理出列和入列的数据包，以及内部关联的其他类函数；②Queue 类:该类属队列管理模块，用于管理数据包的出列或入列；③NextHopDecide 类:用于选择下一跳转发节点并负责对邻居节点的管理；④HelloSend 类:用于管理Hello 消息的传输以及邻居节点的管理。

图6 路由实现的类函数

3.2 吞吐量

首先分析数据包到达率对吞吐量的影响，考虑μ＝1 packets/slot 和μ＝3 packets/slot 两种情况。 从图7 可知，吞吐量随数据包到达率的增加呈上升趋势。 原因在于:数据包到达率越大，单位时间内拥有的数据包数就越多。 这必然增加了网络的提高了吞吐量。 但当数据包达到率增加至1 packets/slot 后，吞吐量随数据包到达率的增加而上升的速度变缓。

图7 吞吐量

相比于SPPR，DABR 路由有效地提升的吞吐量。 这主要是因为:SPPR 路由是采用最短路径决策路由，并没有依据链路容量决策路由。 此外，DABR 路由与LMPF 路由的吞吐量相近，DABR 路由的优势并不明显。 原因在于:LMPF 路由采用多播策略。 多播路由有利于提高吞吐量，尤其是在低数据包到达到率时，其吞吐量高于DABR 路由。 当数据包到达率较大时，LMPF 路由的吞吐量逐渐下降。

此外，对比于图7(a)与图7(b)可知，链路速率的增加提升了吞吐量。 例如，在数据包到达到率为1.6 packets/slot 时，μ＝1 packets/slot 时的DABR 路由的吞吐量为0.6，当μ＝3 packets/slot 时，DABR 路由的吞吐量达到0.63。 链路速率对吞吐量的影响并不大。

3.3 数据传输时延

数据传输时延是指将数据包从发送节点传输至接收节点的平均时间，其是衡量路由性能的重要指标。 图8 给出了μ＝1 packets/slot 和μ＝3 packets/slot 两种情况下的数据包传输时延。

从图8 可知，数据包到达率的增加，增加了数据传输时延。 原因在于:数据包到达率越大，网络内存储的数据包数越多，队列积压越严重，这就增加了时延。 相比于LMPF 和SPPR 路由，DABR 路由有效地控制了数据包传输时延。 这归功于:DABR 路由不仅考虑队列积压差，还考虑了数据包驻留时间，优先传输驻留时间长的数据包，这就缩短了传输时延。

相比于LMPF 路由，SPPR 路由降低了其数据传输时延。 原因在于:SPPR 路由采用最短路径策略决策路由，其缩短了数据传输的路径。 此外，对比图8(a)和图8(b)不难发现，链路速率的增加降低了传输时延。 这符合预期:链路速率越大，单位时间内传输的数据包数越多，队列积压数就越少，减少了数据传输时延。

图8 数据传输时延

3.4 数据包传输成功率

最后，分析数据包到达率对数据包传输成功率的影响，如图9 所示。

图9 数据包传输成功率

从图9 可知，数据包到达率的增加，降低了数据包传输成功率。 原因在于:数据包到达率的增加，增加了网络内的数据包数量，这就加大网络负担，最终降低了数据包传输成功率。

相比于LMPF，DABR 路由的数据包传输成功率较低，尤其是在数据包到达率较低时。 随着数据包到达率的增加，DABR 路由与LMPF 路由的数据包传输成功率的差距逐步缩小。 原因在于:当数据包到达率较大时，多播策略容易导致网络拥塞。 一旦拥塞，就会降低数据包传输的成功率。 对比图9(b)和图9(a)可知，链路速率的增加，提升了数据包传输成功率，但是提升的幅度并不大。

4 总结

针对背压路由的时延问题，提出时延感知的背压路由DABR。 DABR 路由在决策路由时不仅考虑队列积压差，还考虑了数据包在队列中的驻留时间，缩短数据传输时延。 通过分析DABR 路由的吞吐量、数据包传输成功率和数据传输时延性能，分析结果表明:DABR 路由在缩短传输时延的同时，并没有降低吞吐量的数据包传输成功率。 后期，将一步分析DABR 路由的复杂度以及能耗问题，这将是后期的研究工作。