基于DL-DSR的无线自组网路径表达优化方法

肖 品， 唐子安， 陆 倩， 姜胜明

（上海海事大学信息工程学院，上海 201306）

0 引言

无线自组网（Wireless Ad hoc Network，WANet）不依赖网络基础设施，终端间就可以直接通信，它的自组织和自愈能力使得它容易适应动态和不稳定的网络环境［1］。

在WANet中，网络节点移动，无线信道的衰落、干扰等因素造成网络结构的频繁变化，使得路由问题比固定网络要复杂很多。路由协议必须采用分布式操作，支持单向链路，同时应避免环路现象。由于网络节点的移动性、动力资源的有限性，路由协议还应尽量简单，支持节点的休眠操作以节省电源，考虑到WANet的应用环境，路由协议还应提供安全性保护机制。

在WANet路由协议之中，相比主动路由协议，按需路由协议在分组投递成功率和路由开销方面均有着更好的表现。在按需路由协议中，使用源路由机制进行分组转发的动态源路由（Dynamic Source Routing，DSR）协议能使源节点获取更多的到达目的节点的路由［2］，极大地保证了数据分组在动态变化的WANet络中也能被成功交付。

源路由，指的是DSR路由协议中的源节点所发送的每个数据分组头部都会携带从源节点到达目的节点经过的所有中间节点IP地址［3］。正因此，若将DSR路由协议直接应用于资源珍贵、传输能耗大的WANet，头部分组所包含完整的路由信息的路径表达方式会对珍贵的自组网网络资源造成极大的浪费［4］。如何减小头部路径表达的带宽消耗成为了优化DSR协议的重要问题［5］。

1 基于动态标签的动态源路由协议

基本思想和设计思路

基于对DSR路由协议的分析［6-7］，提出一种基于动态标签的源路由协议（Dynamic Label-based Source Routing，DL-DSR）用于优化DSR路由协议。DL-DSR路由协议的基本思想是通过DL-DSR协议的邻居发现策略的启动，在网络中发现通信节点，与此同时在节点内建立起邻居表和标签表，通过将IP地址、邻居表、标签表之间的关系进行映射，在路径表达字段中便可以用8 bit动态标签代替原有的32 bit的IP地址，以此来减小转发分组头部携带完整路由信息的开销［8］。

标签表存放邻居节点IP地址以及邻居节点为自身节点分配的标签号的对应关系［9］，通过此对应关系，可在路由请求阶段逐步以标签号构造出路径表达字段。邻居表存放邻居节点的IP地址与自身节点为其分配的标签的对应关系，通过此对应关系可在转发阶段找到下一跳的IP地址。通过这种方式，便可根据路径表达中的标签号而不是IP地址来进行路径选择。图1所示为DL-DSR路由协议的基本思路示意图。

图1 DL-DSR基本思路示意图

2 路由表的建立

2.1 DL-DSR邻居表的建立

DL-DSR路由协议的邻居表和标签表的建立都是基于邻居发现的过程，标签表的建立是基于邻居表的建立。当DL-DSR路由协议的邻居发现过程启动后，节点会广播hello消息分组将自身节点地址和邻居发现开始的时间告知其邻居节点。

hello数据分组包含了IP地址、启动时间两条信息。IP地址：发送节点自身的IP地址；启动时间：开始发送hello消息分组的时间，即邻居发现过程启动的时间。

当节点收到hello消息分组后，首先取出hello消息分组中的IP地址，在邻居表中查找是否已经存在此IP地址，若存在，则将此IP地址对应的时间戳比较并更新；否则，将IP地址和时间戳一同插入一处空闲的存储空间。若邻居信息丢失或过期，则应该删除相应的存储空间信息。DL-DSR路由协议的邻居表如图2所示。

图2 邻居表结构

邻居信息包含标签号、IP地址和时间戳3个条目。标签：节点为其邻居节点分配的标签号；IP地址：邻居节点地址；时间戳：hello消息分组中携带的时间或邻居表更新时间。

2.2 DL-DSR标签表的建立

DL-DSR路由协议标签表是建立在邻居表的基础上。在节点收到hello消息分组并成功将分组中的邻居信息存储到邻居表后，节点会向hello消息发送方回复hello_reply消息分组，告知发送方本节点的IP地址和本节点为发送方所分配的标签号。

hello_reply数据分组包含IP地址、标签和标识符3条信息。IP地址：hello_reply分组发送节点自身的IP地址；标签：发送节点为hello消息分组来源节点分配的标签号；标识符：若是收到hello消息分组后发送的标识符为0，若是邻居表更新后发送的则为1。根据收到的hello_reply消息分组，网络中的每个节点将收到的邻居IP地址以及邻居节点为自己分配的标签号存入自身的标签表之中，依此完成标签表的建立。标签表结构如图3所示。

图3 标签表结构

标签表信息包含IP地址和标签两个条目。IP地址：邻居节点的IP地址；标签：邻居节点为自己分配的标签号。

2.3 路由表建立示意

图4描述了以S、A、B、C、D为节点的网络标签表建立阶段，同一颜色表示数据的同一映射关系。图4中节点A在成功处理S节点发来的hello消息后回复S节点hello_reply消息，消息中包含节点A自己的ip地址“ip_A”、自己为节点S分配的标签号“1”以及标识符“0”，当节点S收到此消息后，将“ip_A”和“1”写入自己的标签表内。

图4 标签表建立示意图

3 路由请求和应答过程的优化方案

当源节点有数据要发送时，首先会查找节点本地的路由缓存（cache）中是否存在能到达目的节点的路由。如果存在，且这条路由是有效的，就根据这条路由将数据分组发送出去。若不存在，源节点则产生一个路由请求（Route Requset，RREQ）分组［4］，启动路由请求阶段。RREQ请求分组格式如图5所示。

图5 RREQ分组格式

当节点收到一个RREQ分组时，首先判断自己是否已经接收过这个RREQ分组，若是已经收到过这个RREQ分组，就丢弃。否则判断自己是否是目的节点，若是，则向源节点回复RREP（Route Reply）分组启动路由应答（分组格式如图6所示），若不是，继续判断路由缓存中是否存在能到达目的节点的路由信息，若存在，就回复RREP分组启动路由应答，若不存在，就将本节点标签号加到路径中，并向邻居转发更新后的RREQ分组。

图6 RREP分组格式

DL-DSR路由协议规定在向前转发一个RREQ分组前，先会根据上一跳节点的IP地址从当前的标签表中找到对应的标签号，填充到RREQ分组头部的路径表达中，再向周围邻居节点广播出去。依次方式，会逐步建立起一条完整的路径表达［10-11］。路由请求应答流程如图7所示。

图7 路由请求应答流程图

此外，网络中每个节点还维护着一个路由缓存，其中存有该节点在以前路由发现中得到的路由。当源节点收到RREP分组时，便将分组中携带的路径存入路由缓存中，依此建立起路由缓存。路由缓存既能减小路由发现的延迟，又能很好地应对路由失效问题。DL-DSR协议中路由缓存的索引是目标地址，当路由缓存中存在不止一条到达同一个目的地址的路径时，缓存信息的读取是找到最短的一条路径，即跳数最少的一条路径。如果出现路由失效现象，源节点便利用路由缓存中的备选路由代替失效路由发送数据分组。

如图8所示，节点S为源节点，节点D为目的节点，当S节点检查自己路由缓存发现无到达目节点的路径，便产生了一个RREQ分组，启动路由请求发给自己的邻居节点A、B。以A节点为例，当A收到S发出的RREQ，A节点会检查自己的路由缓存也无目标节点的路径，于是查找自己标签表，找到上一跳的ip地址，也就是S节点的ip地址“IP_S”对应的标签号“1”，将“1”写入RREQ路径表达中，并向邻居节点S、C转发更新后的RREQ请求。当S收到此RREQ后根据请求序列号发现自己收到过，于是丢弃；当C点收到后按协议规则继续处理。最终到达目标节点D，D节点将完整的路径“1→2→2”填入生成的RREP消息分组中，以倒序路径回传给S节点。S节点收到此RREP消息后，将其中的路径表达取出存入自己的路由缓存中，路由请求结束，进行以S为源节点D为目标节点的数据转发时便可以使用这一路径。路由请求和应答过程的示意如图8所示。

图8 路由请求应答过程示意图

4 仿真与分析

4.1 仿真场景

将DL-DSR路由协议方案进行仿真分析，使用EXata网络仿真软件。仿真之前，需要先在EXata上面搭建一个仿真的WANet场景［12］。仿真主要参数：区域大小为6 km×6 km；仿真时长为1 h；节点移动模型和速度分别为随机路点（RandomWaypoint）和0～30m/s；能量消耗模型为通用型（Generic）；应用层业务流为恒定比特率（CBR）；邻居发现周期800 ms；有效数据长度为64～512 Byte；路径跳数为4～32跳［13］。

4.2 仿真结果分析

4.2.1 网络负载与路径中节点跳数

图9（a）、（b）分别为有效数据长度在64和512 Byte的节点网络负载（单位Kb/s）和路径中节点跳数的关系。

图9 网络负载和路径中节点跳数的关系

由仿真结果可见，在有效数据长度相同、跳数相同的情况下，DL-DSR协议的网络负载均小于DSR协议的网络负载，并随着中节点跳数增大，两者的传输负载差值越来越大，DL-DSR协议的网络负载增长缓慢，明显低于DSR协议。

4.2.2 端到端平均时延与路径中节点跳数

图10（a）、（b）分别为有效数据长度在64和512 Byte的节点平均端到端时延与路径中节点跳数之间的关系。

图10 平均时延与路径中节点跳数的关系

由仿真结果可见，在有效数据长度相同的情况下，DL-DSR协议和DSR协议端到端时延随着路径中节点跳数的增加而增大；当路径中节点跳数相同时，DLDSR协议节点间平均端到端时延都比DSR协议小。说明DL-DSR协议减小路径表达占用的带宽的方式，在一定程度上的确减小数据传输的端到端时延。

4.2.3 节点平均能耗与路径中节点跳数

图11（a）、（b）分别为有效数据长度在64和512 Byte的节点平均能耗与路径中节点跳数的关系。

图11 平均能耗与路径中节点跳数的关系

由仿真结果可见，在有效数据长度一定的情况下，节点平均能耗会随着路径中节点跳数的增大而增大，DL-DSR协议节点平均能耗是明显低于DSR协议的。对于能耗增长速度，特别是当路径中节点跳数增大时，DL-DSR协议节点平均能耗增长速度比DSR协议的节点平均能耗增长速度慢。

5 结语

通过对WANet中的DSR路由协议进行分析研究，发现其数据分组头部所携带的完整路由IP地址列表会对网络性能带来影响，提出一种基于动态标签源路由（DL-DSR）协议，DL-DSR协议通过采用动态标签代替节点IP地址来表示数据分组头部的路由路径的方式来解决此问题。

通过对仿真结果的分析：在跳数为32、有效数据长度为512 Byte的仿真场景中，DL-DSR路由协议相比于DSR路由协议，网络负载降低约15%，平均时延降低约10%，平均能耗降低约10%；在有效数据长度为64 Byte的仿真场景中，DL-DSR路由协议相比DSR路由协议，网络负载降低约40%，平均时延降低约15%，平均能耗降低约18%。

综上，DL-DSR协议在网络负载、端到端时延、头部开销和节点能耗方面都具有一定优势，特别是当源节点距目的节点较远需要经过较多跳数才能将数据分组交付时，DL-DSR协议相较于DSR协议，有着更低的网络负载、更低的端到端时延和更低的节点能耗，表现出更好的网络性能。