WSNs中满足时延要求的空洞抑制路由

刘 立，朱 弘，苏秀芝，谢英辉

（1.长沙民政职业技术学院 软件学院，长沙 410004；2.河南省电子政务内网管理中心，郑州 450003；3.湖南软件职业学院 软件与信息工程学院，湖南 湘潭 411100）

0 引言

目前，无线传感网络（wireless sensor networks,WSNs）[1-2]已在环境监测、健康医疗、灾场救援等场景中得到了广泛应用。这些应用要求传感节点感测数据，将数据传输至控制中心。这些应用对传输时延具有一定要求，而路由协议对数据传输时延有直接影响。

地理位置路由由于操作简单、开销低[3]，已经广泛地应用到WSNs中。地理位置路由只是利用邻居节点的位置信息决策路由，降低网络开销，例如，服务质量（quality of service, QoS）感知的地理机会路由（QoS aware geographic opportunistic routing, QAGOR）[4]就是一个例示。

地理位置路由常遭遇路由空洞[5-6]问题，尤其在低密度节点网络环境下更是如此。一旦遭遇路由空洞，常采用边界转发模式传输数据包。若路由空洞边界上节点都沿着边界转发，也可能会造成边界拥塞。考虑到空洞路由问题和时延要求，本文提出基于时延要求的地理位置路由（delay-guaranteed-based geographic routing, DGGR）。DGGR路由先检测路由空洞并解决路由空洞问题，在满足时延要求的条件下，合理地选择数据传输路径，平衡各路径的流量，进而避免边界拥塞。仿真数据表明，提出的DGGR路由能有效地平衡网络负载，提高数据包传递率。

1 约束条件及定义

假定网络内各个节点知道自己的位置，数据包的目的节点的位置亦为网络已知参数。

1）路由空洞（hole）。假定用连线依次连接传感节点S1,…,Sn，其构成多边形Θ。当满足以下两个条件，就形成路由空洞：①多边形区域内不含任意任何传感节点；②S1,…,Sn内相邻节点的连线距离小于传感节点的通信半径r，且相隔一个节点的连线距离大于通信半径r，其表达式为

式中：di,i+1为Si与Si+1间距离；di,i+2为Si与Si+2间距离；n为传感节点数。

2）凸包（convex hull）。对于任意一个多边形Θ，若某一个凸多边形能覆盖多边形Θ，且具有相同的顶点，则该凸多边形称为该多边形Θ的Θ凸包。

3）视点。若Q1，Q2,…,Qn为多边形Θ的顶点，节点I是多边形Θ外的一个节点。如果Qi与I连线与Θ不相交，则顶点Qi称为I的视点，如图1所示。

图1 视角和最短绕径示例

视点Qi、Qj与I连线的夹角，称为视角。由如图1（a）可以看出，节点I离空洞越远，视角越小。若足够远，则视角就趋于零。

4）最短绕径。从源节点至目的节点的最短绕径是指沿着凸包的最短折线。如图1（b）所示，源节点s至目的节点t的最短绕径为LΘ(s,t)。

5）空洞-最短绕径（hole-bypassing shortest path,HBSP）。对于任意两个空洞区域外的节点，沿着空洞区域存在顺时针、逆时针方向的最短绕径。而空洞-最短绕径是指两个最短绕径中更短的最短绕径。

以图1（b）为例，s、t为空洞区域凸包H的两个节点。而Hs1、Hs2为节点s的视点，而Ht1、Ht2为t的视点。从源节点s至目的节点t的最短绕径为：而空洞最短绕径为这者间最小值，即HBSP =min {L+Θ(s,t),L-Θ(s,t)}。

2 DGGR路由

提出 DGGR路由的目的在于抑制路由空洞，即在满足传输时延要求的条件下，避开空洞。DGGR路由主要由检测空洞、收集空洞信息、扩展转发区和转发数据等阶段构成。

2.1 检测空洞

先利用文献[7]的滕特（TENT）规则判断节点是否为空洞节点。若自己遭遇空洞，则自己为空洞节点。一旦成为空洞节点，就形成边界坐标决策信息（boundary coordinates determination, BCD），然后采用右手规则[7]，沿着边界传输 BCD信息。通过BCD信息的传输，收集空洞信息。假定传感节点Sj接收了传感节点Si发送的BCD信息（BCDi）。首先检测Xj是否小于Xi。如果Xj＜Xi，则利用右手规则转发BCDi，否则就丢失。依据这种策略限定了只有一条BCD消息沿着边界转发，而且此条BCD消息是由横坐标最大的空洞节点产生的，此节点也称为BCD的启发节点（BCD-H）。

2.2 收集空洞信息

通过收集空洞信息，完成对空洞凸包H信息的收集，即收集空洞边界节点的所有位置信息。为了控制网络开销，限定凸包H信息的传输范围。设定二值参数αmin，由αmin控制传输范围。如果αmin=π，凸包H信息的传输范围限定于凸包H区域。反之，若αmin=0，则可将凸包H信息的传输至整个网络。

一旦BCD-H获取了凸包H信息，就由BCD-H触发空洞核心信息（hole core information, HCI）的传输，HCI包含了凸包H信息。随后，BCD-H节点就向边界节点传输HCI信息。一旦接收了HCI信息，节点就计算视角θ，并与αmin进行比较。若θ＞αmin，节点就存储凸包H信息，并继续向邻居节点转发HCI信息。若不满足，就直接丢掉HCI信息。

2.3 扩展转发区及扩展因子

2.3.1 扩展转发区

扩展转发区的目的在于，在满足数据传输时延要求的前提下，增加数据转发区域，即提供更多的数据转发路径。

依据上述分析可知，当节点遭遇路由空洞时，若都沿着HBSP传输数据，能够降低传输时延，并缓解路由空洞问题。然而，若所有节点都沿着HBSP传输数据，则会形成边界网络拥塞[8]。为此，通过定义扩展转发区，使得数据包避开边界，缓解边界拥塞。考虑到数据传输时延，依据数据传输时延定义数据包的扩展转发区。扩展转发区的尺寸与数据传输时延成正比。

以图2为例，源节点s需要向目的节点t传输数据包，并且该数据包的时延不能大于15 s，必须在15 s内完成数据包的传输。假定该数据包沿着HBSP路径传输只需要10 s。

图2 扩展转发区示例

为了减少边界负载，可选择更长的路径传输数据包，只要传输时延不超过15 s。在这种情况下，可以扩展转发区。这样可将图2的扩展成

据此，将空洞凸包H进行扩展，形成扩展区域，必须满足时延要求。为此，定义扩展因子，使其控制扩展区域的尺寸。

假定ξ为扩展因子。将凸包H依据ξ的比例进行扩展，形成转发扩展区F,并满足

式中：pH为凸包H的边；LF(s,t)为沿着扩展区域从源节点s至目的节点t的路径长度；LH(s,t)为沿着凸包H从源节点s至目的节点t的路径长度。

2.3.2 扩展因子

本文依据数据包的传输时延定义扩展因子。假定源节点si需向目的节点t转发数据包，它的HBSP路径为LH(si,t)。该数据包的扩展因子为

式中：D为对该数据包的传输时延要求；Dr为已消耗的时间[9]；（r D-D）为剩余时间；dm为节点si的所有-跳邻居节点中，具有最大平均跳-跳时延（average hop-to-hop delay, AHHD）的节点，其定义为

式中：Ni为si的邻居节点集；为从节点si到节点sj的 AHHD时延，通过文献[10]所提出的时延估计算法估计出值。

2.4 数据包的传输

当节点未遭遇路由空洞时，就采用贪婪转发策略传输数据包。若遭遇路由空洞，就采用空洞绕开策略转发数据包。

2.4.1 选择转发节点

现存的协议常通过跳速（hop-to-hop speed,HTHS）决策路由，并满足数据传输时延要求。一条路由的 HTHS的值等于这条路由的距离与所需数据包的时延比值[11-12]。DGGR路由也延用HTHS概率，并依据HTHS值选择转发节点。

由于存在贪婪转发和空洞绕开转发两种模式，需分别从这两种模式下计算HTHS。若数据包采用贪婪转发，就不必计算扩展区，这时就直接计算从节点si到节点sj的HTHS值为

式中：si为数据包携带节点；sj为si的邻居节点；为si至目的节点t的距离；为sj至目的节点t的距离。

若数据包遭遇路由空洞，则需沿着扩展区域F转发数据包。与式（5）类似，在空洞绕开转发模式下，从节点si到节点sj的HTHS值为

在贪婪转发模式下，HTHSth的阈值为

若采用空洞绕开转发，则 H THSth的阈值为

将节点si将邻居节点集Ni内所节点的 HTHS值与 H THSth进行比较。如果HTHS＞ H THSth，说明能够满足数据包传输时延要求，将此节点纳入候选转发集ψi，即

一旦形成候选转发集iψ，就从中随机选择一个节点作为下一跳转发节点。这时iψ内每个节点都满足时延要求。

2.5 数据包传输

假定节点si需要向目的节点t传输数据包，源节点就传输数据包，其格式如图3所示。

图3 数据包格式

图3中：第1个字段为转发模式，占1个比特位。当ForwardingModel=0，表示贪婪转发；反之，ForwardingModel=1，则表示空洞绕开转发；第 2字段为扩展转发区的中心位置，其占1个字节；第3字段为扩展因子，占1个字节；第4字段为该数据包的传输时延[13]，即在此传输时延要求内，完成数据包的传输。第4字段为数据包的目的节点；最后1个字段为真正要传输的数据包。

一旦接收了数据包，首先判断自己是否为目的节点，若是，则直接传输。否则，就判断自己是否遭遇路由空洞，若不是，则采用贪婪转发，否则就采用空洞绕开转发模式。图4描述了数据传输的流程。

图4 DGGR路由流程

3 性能仿真

3.1 仿真参数及性能指标

通过 NS2.35[14]网络仿真软件建立仿真平台，分析DGGR路由处理路由空洞的能力。为此在1 200 m×1 200 m的仿真区域内，部署18个空洞，空洞尺寸逐步增加。图5显示了 3个网络拓扑结构的示例，白色区域表示空洞尺寸。

图5 网络拓扑示例

200个节点随机分布在1 200 m×1 200 m的范围内。50个源节点产生数据包率为0.1，且数据包大小为50字节。每个数据包的传输时延要求D从{0.2,0.5,0.8}中随机选择。仿真时间为500 s。

为了充分地分析 DGGR路由性能，选择文献[6]提出的多径多速度路由（multipath multispeed routing, MMSR） 和文献[4]提出的盖格勒（QAGR）进行同步仿真，并分析数据包传递率和均衡性能（balance index, BI）[15]，BI的定义为

式中：N为节点数，这里取N=200；pi为传感节点si传输的数据包数。依式（10）可知，BI表征了传感节点间的流量负载的均衡性。

由于 DGGR路由旨在抑制路由空洞，在仿真过程中，选择网络中的空洞数作为参数变量，空洞数的数量从1个逐步增加至18个。

3.2 数据包传递率

本次实验分析数据包传递率的影响，实验数据如图6所示。

从图6可知，不论D取何值，相比于姆姆斯勒（MMSR）和QAGR协议，提出的DGGR协议的数据包传递率最高。空洞拓扑数的增加，降低了MMSR和QAGR协议的数据包传递率，但DGGR协议的数据包并没有随空洞拓扑数变化而波动，保持稳定的数据包传递率。

图6 数据包传递率

从图6（a）可知，当D=0.2 s，DGGR路由的数据包传递率达到75%，而当D增加至0.5 s和0.8 s时，DGGR路由的数据包传递率仍达到95%。图6（b）、图6（c）具有类似的结果。DGGR路由之所以保持稳定的数据包传递率，原因在于DGGR采用边界转发，并构建了扩展转发区，在满足时延要求的前提下，提高了数据包传输的成功率。

相比于DGGR和MMSR路由，QAGR路由的数据包传递率最低。这说明 QAGR路由处理路由空洞能力极差。而MMSR路由引用回压机制处理路由空洞，具有一定的应对路由空洞的能力。但相比于DGGR路由，MMSR路由的数据包传输率仍较低。

3.3 均衡性能

接下来分析 3个路由的均衡性能。取D=0.8s，取节点数为200，实验数据如图7所示。

图7 均衡性能

从图7可知，相比于QAGR和MMSR路由，提出的 DGGR路由的 BI性能最高，这也说明DGGR路由有效地平衡流量负载。这归功于DGGR路由通过设定扩展转发区，均衡了边界转发流量。

尽管QAGR路由的数据包传递率低于MMSR路由，但是它的BI性能优于MMSR路由，但仍低于DGGR路由。

4 结束语

针对 WSNs的路由问题，提出基于时延要求的地理位置路由 DGGR。DGGR路由在满足数据包传输时延要求下，解决路由空洞问题。通过检测路由空洞，然后给遭受路由空洞的数据包定义扩展转发区，使得数据包沿着扩展转发区传输，避开路由空洞，并缓解边界转发的拥塞问题。仿真数据表明，提出的 DGGR路由能有效地提高数据包传递率，并平衡了边界节点的负载。