基于泛洪区域限定的改进DSR

张渊博

（中铁第一勘察设计院集团有限公司，陕西西安 710043）

动态源路由(Dynamic Source Routing,DSR)是移动Ad hoc 网 络(Mobile Ad hoc Network,MANET)[1-2]的典型路由，其主要有路由发现和路由维护两个阶段[3-4]。在路由发现阶段，源节点通过广播RREQ，构建连通目的节点的路由。

然而，若盲目地泛洪RREQ 包，增加了网络开销，也容易引起广播风暴问题[5]。针对这些问题，研究人员提出不同的泛洪改进算法，如N 跳泛洪[6]、概率泛洪[7-8]。

该文针对源路由的RREQ 的泛洪问题，提出区域的路由发现机制的DSR 路由(Zone-based Route Discovery Mechanism,ZRDM)。ZRDM 路由通过限定泛洪RREQ 的区域，减少RREQ 包重传的次数，进而控制开销，提高数据包传递率。仿真结果表明，提出的ZRDM 路由降低了路由开销，提高了数据包传递率。

1 ZRDM路由

ZRDM 路由主要由三个阶段构成：1）邻居节点分类；2）RREQ 泛洪区域的选定；3）路由发现。

1.1 邻居节点分类

令R表示节点的传输范围。依据信号强度[9-10]将其划分为三个子区域：1）最外区域(OutSide Area,OSA)；2）中间区域(InterMediate Area,IMA)；3）最内区域(InSide Area,ISA)，如图1 所示。将半径R至3R/4内的环形区域作为OSA 区域；将半径3R/4 至的环形区域作为IMA；将半径的圆形区域作为ISA区域。

图1 传输范围的区域划分

令γi←j表示源节点si从其邻居节点sj接收的信号强度，可通过式(1)计算γi←j：

式中，Pt表示发射功率；λ为控制参数；α表示衰减因素；d表示源节点si与邻居节点sj之间的距离。

1.2 RREQ泛洪区域

传统的DSR 路由采用泛洪方式[11-12]传输RREQ包,如图2 所示。通过不断地传递RREQ，直到目的节点接收到RREQ。由于RREQ 包中携带了其传输路径，目的节点可从RREQ 获取连通源节点的路径信息，目的节点再沿此路径向源节点传输回复包(Route Reply,RREP)。最终，通 过RREQ 和RREP 的传输构建了路由[13-14]。

图2 DSR路由发现阶段

为了更好地减少控制开销，将源节点传输方向划分为四个象限。令(xi,yi)表示源节点si的位置坐标，将源节点si的传输区域划分为Q1、Q2、Q3和Q4，如图3 所示。

图3 泛洪区域的划分

对于任意邻居节点sj∈Ni，如果xj＞xi且yj＞yi，则邻居节点sj位于Q1，如式（3）所示：

如果满足式（4），则邻居节点sj位于Q2：

若满足式（5），则邻居节点sj位于Q3：

若满足式（6），则邻居节点sj位于Q4：

为了避免形成路由循环，减少路由跳数，源节点泛洪RREQ 区域内至少包含一个邻居节点；若未能包含一个邻居节点，就选择其他区域传输RREQ 包。

1.3 路由发现策略

首先，源节点（假定为节点si）先产生RREQ 数据包，其包含自己的序列号、目的地址和源节点的地址。如果目的节点在源节点一跳范围，则源节点就直接将RREQ 包传输至目的节点。接收RREQ 后，目的节点就向源节点传输RREP 包，如图4 所示。

图4 传输RREQ的流程

若目的节点不在自己一跳传输范围内，源节点就需向邻居节点泛洪RREQ 包。但与DSR 路由不同，ZRDM 路由为了减少参与传输RREQ 包和接收RREQ 包的节点数，ZRDM 路由并非向所有区域泛洪RREQ 包，而是依据算法1 设置泛洪RREQ 包的区域。

1.4 算法1

算法1 完成泛洪RREQ 子区域的选择。令表示节点si的泛洪RREQ 的区域。DSR 是将OSA、IMA 和ISA 三个子区域都作为泛洪RREQ 的区域，即ΩFi={O SA,IMA,ISA} 。但是ZRDM 路由并不是固定地将OSA、IMA 和ISA 三个子区域作为泛洪RREQ 的区域，而是依据节点的分布情况，有目的性地选择泛洪RREQ 的区域，如算法1 所示：

算法1：选择泛洪RREQ 的区域

如果节点si的四个区域(Q1、Q2、Q3和Q4)内均有节点，就只选节点si的OSA 区域作为泛洪区域。具体而言，若满足式（7），则将OSA 子区域作为泛洪RREQ 的区域：

若不满足式（7），为了保证构建稳定路由，先将OSA 作为泛洪RREQ 的区域，然后，再考虑是否将IMA 区域作为泛洪区域。如果IMA 区域内四个象限区域均有节点，就将IMA 区域作为泛洪区域。即再判断是否满足式（8）。若满足式（8），则将IMA 和OSA 区域共同作为泛洪RREQ 的区域：

若既不满足式（7）也不满足式（8），就将OSA、IMA 和ISA 三个子区域都作为泛洪RREQ 的区域,即={O SA,IMA,ISA} 。在这种情况下，ZRDM 路由与DSR 路由一样，向所有区域泛洪RREQ 包。

一旦确认了泛洪RREQ 包的子区域，源节点si就将区域的节点加入广播重传邻居列表(Neighbors to Rebroadcast RREQ,NRR)。只有NRR列表内的节点才可以转发RREQ 包。

1.5 选择泛洪区域的示例

为了更好理解算法1 所选择的泛洪RREQ 区域，图5 给出示例说明。接下来分别考虑了三种情况：Case1、Case2 和Case3。

图5 泛洪RREQ包的区域示例(Case1)

Case1：节点密度较高，如图5 所示。OSA 区四个象限内均有邻居节点。在这种情况，就只将OSA 区域作为泛洪区域；只在OSA 区内泛洪RREQ 包。

Case2：节点密度不高，如图6 所示。并非OSA区的四个象限内均有邻居节点，而IMA 区的四个象限内都有邻居节点。在这种情况，只在OSA 区和IMA 内泛洪RREQ 包。

图6 泛洪RREQ包的区域示例(Case2)

Case3：节点密度稀疏，如图7 所示。OSA 和IMA区域内的Q4象限内没有邻居节点。在这种情况下，为了提高建立可靠路由，将OSA、IMA 和ISA 三个区作为泛洪RREQ 的区域。

图7 泛洪RREQ包的区域示例(Case3)

1.6 邻居节点接收RREQ的处理策略

一旦收到RREQ 包后，邻居节点从RREQ 包中提取NRR 的信息，并判断自己是否在NRR 内。若不在NRR 列表内，就直接丢失RREQ 包；若在NRR 列表内，就继续判断是否为目的节点。若是目的节点，就直接向该目的节点传输RREQ 包。若不是目的节点，就利用算法1 选择泛洪RREQ 包区域。处理RREQ 包的流程如图8 所示。

图8 接收RREQ包后的处理流程

2 数值分析

2.1 仿真场景

通过NS3 仿真软件建立仿真平台[15]。N个节点随机分布于300 m×1 500 m 区域，节点的传输范围为250 m。具体的仿真参数如表1 所示。

表1 仿真参数

为了更好地分析ZRDM 路由性能，选择文献[3]提出的可靠DSR 路由(DSR)作为参照，并分析数据包传递率和归一化的吞吐量。

2.2 数据包传递率

首先，分析节点数的变化对数据包传递率的影响，其中，数据包传递率等于目的节点成功接收了的数据包数与源节点发送的数据包数之比。

从图9 可知，在节点数从20 至40 变化，ZRDM 路由与DSR 路由的数据包传递率相近，它们的数据包传递率分别约为88%、86%。原因在于：当节点数较少，节点密度分布较低时，DSR 和ZRDM 路由一样，都采用OSA、IMA 和ISA 区作为泛洪RREQ 包区。

图9 数据包传递率

然而，随着节点数的增加，ZRDM 路由的数据包传递率逐步优于DSR 路由。这主要是因为节点数的增加，使OSA 区域内的四个象限均有节点的概率增加，从而实现了只在OSA 区域内泛洪RREQ 包，这就减少了节点传递RREQ 包的次数，降低了拥塞的概率，增加了数据包传递率。当节点数增加至140时，相比于DSR 路由，ZRDM 路由的数据包传递率提高约2.78%。

2.3 归一化路由开销

分析归一化路由开销随节点数的变化情况，如图10 所示。

图10 归一化路由开销

从图10 可知，相比于ZRDM 路由，DSR 路由产生更多的RREQ 包。原因在于每个节点都接收RREQ的复本。如当节点数为80 个时，DSR 路由的归一化路由开销近11.93%，而ZRDM 路由的归一化路由开销近8.10%，比DSR 路由下降近3.83%。

2.4 节点移动速度对数据包传递率的影响

分析节点移动速度对数据包传递率的影响,其中节点移动速度从5 m/s变化至35 m/s，如图11所示。

图11 节点移动速度对数据包传递率的影响

从图11 可知，ZRDM 路由和DSR 路由的数据包传递率均随节点移动速度增加而下降。原因在于：节点移动速度越快，网络拓扑变化加快，降低了链路的连通时间。相比于DSR 路由，提出的ZRDM 路由提高了数据包传递率。例如，当节点移动速度增加至10 m/s，ZRDM 路由的数据包传递率达到98%，而DSR 路由的数据包传递率约为88%，提高了近10%。原因在于节点移动速度的增加,加剧了链路断裂数,这影响了DSR 路由的数据包传递率。而构建ZRDM路由时考虑了链路的可靠性。

当节点移动速度提高至15 m/s 时，ZRDM 路由的数据包传递率约为83.1%,而DSR 路由的数据包传递率只有50.1%。相比于DSR 路由,ZRDM 路由将数据包传递率提升了约65.9%。当节点移动速度分别提高至20 m/s、25 m/s、30 m/s、35 m/s，ZRDM 和DSR 路由的数据包传递率迅速下降。但是ZRDM 路由的数据包传递率的下降速度低于DSR 路由。

2.5 节点移动速度对平均端到端时延的影响

分析节点的移动速度对端到端传输时延的影响，其中，节点移动速度从5 m/s至35 m/s变化，如图12所示。

图12 节点移动速度对平均端到端时延的影响

从图12 可知，在节点移动速度为10 m/s、20 m/s、25 m/s 和35 m/s 时,提出的ZRDM 路由的平均端到端时延低于DSR 路由的时延。例如，在节点移动速度为10 m/s 时，ZRDM 路由的平均端到端时延约为7.45 ms，而DSR路由的平均端到端时延达到18.13 ms。相比于DSR 路由，ZRDM 路由的平均端到端时延下降了10.68 ms，并且随着移动速度的提升，ZRDM 路由在时延性能方面的优势越明显。

2.6 节点移动速度对归一化路由开销的影响

分析节点移动速度对归一化路由开销的影响，其中节点移动速度从5 m/s 至35 m/s 变化，如图13所示。

图13 节点移动速度对归一化路由开销的影响

当节点移动速度为5 m/s 时,ZRDM 路由的归一化路由开销为8.44%，而DSR 路由的归一化路由开销达到17.73%。相比之下，ZRDM 路由将归一化路由开销下降了52.40%。当节点移动速度增加，链路断开的概率也随之增加，这就增加消息传输失败的次数。一旦消息传输失败，就需要源节点重新构建新的路由，这就增加了路由开销。而ZRDM 路由通过限定RREQ 的传输区域，降低了路由开销。

3 结论

针对DSR 盲目地泛洪RREQ 包问题，提出基于区域的路由发现机制ZRDM。ZRDM 路由先依据信号强度将邻居节点划分为三个子区域，并依据每个子区域的节点分布情况，选择泛洪RREQ 包的区域，进而控制重播RREQ 的次数。仿真结果表明，提出的ZRDM 路由降低了开销，并提高了数据包传递率。