引言

Ad Hoc[1]网络具有无中心控制节点、路由多跳、拓扑动态等特点，可以用于不能预设网络设施的场合和需要快速自动组网的场合，例如：战场、无人烟山区、救灾现场等[2]。因此 Ad Hoc 网络在当今社会具有非常广泛的应用场景。

动态源路由协议(Dynamic Source Routing)[3]是一种按需路由协议，是十分适用于 Ad Hoc 网络的路由协议。在 DSR 协议中，路由表的表项都是按需建立的。路由过期或链路断开，表项就失去作用了。为减少路由不断建立而产生的网络开销，按需建立的路由都由源节点存储，用于与目的节点通信[4]。因此 DSR 协议的核心是管理各节点之间通信的路由表项。

目前，国内外针对 Ad Hoc 网络的研究大多是基于软件的，使用的软件平台有 NS2、GloMoSim、OPNET 等。因此，DSR 协议的核心功能——路由表项管理，也是基于软件完成的。目前为止，还未有基于 FPGA 实现 DSR 路由表项管理的先例。

使用硬件实现 DSR 协议功能将减少功耗和延迟时间，延长移动设备的电池使用时间[5]。Ad Hoc 网络中，通过硬件与嵌入式芯片联系在一起，使得操作速度的增加与功耗降低，处理时间还可以用于其他操作[6]。此外，使用硬件实现 DSR 协议可以更快地建立呼叫和更改动态拓扑[7]。因此，使用 FPGA 实现 DSR 路由表项管理具有很好的实际用途。

本文为在 FPGA 中支持 DSR 协议的路由表项管理功能，设计一种基于有限状态机[8]的实现方法。本文的设计中，状态机包含一个初始状态和 3 个功能状态。有限状态机的 3 个功能状态一起联合实现路由存储、路由查找、路由删除的功能。有限状态机使得硬件代码符合时序电路的风格。此外，综合后的代码在电路物理实现时使得时延特性与功耗更加优化[9]。

1 DSR 路由表项管理的实现

1.1 总体方案

总体方案如图 1 所示，设计分为两个部分：路由管理有限状态机模块以及路由管理模块。有限状态机根据需求跳转到不同的功能状态，生成不同的操作使能，用以驱动路由管理模块对路由表项进行添加、查找、删除。路由管理模块完成对路由表项的操作后，有限状态机从现有状态跳转回初态。

1.2 路由管理有限状态机

路由管理有限状态机的设计是基于 DSR 协议，有限状态机的状态跳转如图 2 所示。若需要查找一条路由时，状态机从 IDLE 状态跳转到路由查找状态并生成路由查找使能，当状态机收到查找操作结束信号时，状态机跳转到 IDLE 状态；若需要删除路由时，状态机从 IDLE 状态跳转到路由删除状态并生成路由删除使能，当状态机收到删除操作结束信号时，状态机跳转到 IDLE 状态；若需要存储一条路由时，状态机从 IDLE 状态跳转到路由缓存状态并生成路由存储使能给路由管理模块，当状态机收到路由存储操作结束信号时，状态机跳转回 IDLE 状态。

1.3 路由管理模块

路由管理模块具体细化为 4 个模块：生存周期模块、路由写模块、路由读模块、路由删除模块。路由管理模块对路由表项的管理是通过对路由 BD(Buffer DescripTIon)以及它的地址进行操作完成的。BD 包含路由的某些信息，例如：该路由所导向目的节点 IP 地址、路由长度、路由表项存储单元的起始地址。根据一个 BD 就可以读取一条完整路由。

(1)路由写模块存储路由与生成该路由的 BD。需要存储一条路由时，模块将该路由存储于 RT 表一个空条目（条目容量为 16 个周期数据长度）。同时生成一个新 BD 存入 BD 表。

(2)路由读模块完成两个功能：①读取一条有效路由；②查收所有包含断开链路的有效路由并反馈给路由删除模块。

(3)生存周期模块包含 256 个计数器(网络只支持 256 个节点)，为每个新 BD 设置生存周期。

(4)路由删除模块维护一个有效 BD 地址的单向链表。路由存储时，将包含新 BD 地址的表项插入链表；路由查找时，查找一个有效 BD 地址；路由过期时，从链表中删除该条路由的有效 BD 地址表项；路由删除时，删除包含断开链路的路由有效 BD 地址的表项。

路由存储时，将路由存于 RT 表一个空条目。同时生成一个对该条目进行描述的 BD 并存于 BD 表中；它的地址被插入链表中，并为它设定生存周期。

路由管理原理如图 3 所示。查找路由时，首先读取链表尾条目，根据有效 BD 地址读取 BD 表一个有效 BD，比对目的节点地址。若匹配，根据 RT 长度与有效 RT 地址读取 RT 表一条完整的路由。若不匹配，则根据链表指针读取链表的前一个条目，然后重复上面所述的操作，直到目标路由或者查完链表。路由过期即路由的 BD 过期，将包含该 BD 地址的条目从链表中删除。路由删除时，需要重复路由查找过程，读取全部有效路由，并逐条比对是否包含断开链路。将包含断开链路的 BD 地址条目从链表中剔除。删除操作完成后，更新后一个条目的链表指针，使得链表完整。

实验仿真与分析

2.1 总体功能仿真

图 4 是路由存储仿真结果。标号①是存储的路由信息，store_route_en 是路由存储的使能，hop[31:0]路由数据周期数，did[31:0]目的节点地址，data_route[31:0]是路由数据。

图 5、图 6 是路由查找仿真结果。did_to_rd_rt[31:0]是目的节点地址。标号③与标号④分别是存储与读取的路由数据，两者是一样的，故路由查找结果正确。

图 7 与图 8 是路由删除仿真结果。标号①是存储的路由，标号③是需要删除路由包含的前端节点 ID1 与后端节点 ID2 地址。标号②是路由存储时插入链表的有效 BD 地址，标号④是路由删除后链表释放的 BD 地址。两者的数据一致，路由删除结果正确。

2.2 总体性能仿真与分析

表 1 是一条路由存储的时延随周期变化的情况。由表 1 可知，随着存储的路由周期变长，模块路由存储的时延均在 166.4 ns 左右。

若路由不过期，每条路由固定长度且每次查找第一条存储路由，表 2 是长度为 2 周期的路由查找时延随着条数变化情况。表 3 是长度为 8 周期的路由查找时延随着条数变化情况。

由表 2、表 3 可知，路由周期固定，随着存储条数增加查找路由的时延快速增加。在路由表中存储路由条数固定情况下，路由查找时延随着路由长度的增加缓慢增加。路由查找的时延在 ns 级，说明查找速度很快。

表 4 是长度为 2 周期的路由删除时延随着条数变化情况。表 5 是长度为 8 周期的路由删除时延随着条数变化情况。

由表 4、表 5 可知，在存储周期固定的路由情况下，随着存储条数增加，删除路由的时延快速增加，几乎是 2 倍的速率。在路由表中存储路由条数固定情况下，路由删除时延随着路由长度的增加缓慢增加。 但路由删除的时延还在μs 级以下，说明删除速度依然很快。从路由存储、查找、删除的结果分析上来说，路由管理模块工作效率是非常高的。

模块设计使用 vivado2015.2 平台，开发板采用 Xilinx 的 VC707，使用的设备是 XC7VX485T。片上总功耗为 28.379 W，模块功耗为 11.755 W。片上各部分资源使用情况如表 6 所示。

由表 6 可见，使用硬件实现 DSR 路由表项管理所占用的硬件资源非常少，功耗十分小。

 结论

本文针对在 FPGA 中支持 DSR 路由协议的核心内容路由表项管理提出了一种基于有限状态机的设计与实现方法。建立实现模型，使用 vivado2015.2 平台进行仿真，仿真结果很好地验证了预期目标。通过实验分析，发现使用 FPGA 实现 DSR 路由表项管理时延非常低，资源占用十分少，功耗很小。