0 引言

ad hoc网络^[1]具有无中心控制节点、路由多跳、拓扑动态等特点，可以适用于不能预设网络设施或需要快速自动组网的场合。设计高效、动态的路由协议成为规划无线自组网的一个挑战，路由协议必须能够适应节点移动所带来的网络拓扑结构迅速变化。

根据路由建立时机与数据发送的关系，ad hoc网络路由协议^[2]通常可分为主动路由协议和按需路由协议。主动路由协议主要有目的序列的距离矢量路由（destination sequenced distance vector routing，DSDV）^[3]、优化链路状态路由（optimized link state routing，OLSR）^[4]、鱼眼状态路由（fisheye state routing，FSR）^[5]等；按需路由协议主要有动态源路由（dynamic source routing，DSR）^[6]、按需距离矢量路由（ad hoc on-demand distance vector routing，AODV）^[7]等。按需路由是一种被动路由方式，其路由表是按需建立的，无需实时维护，一旦路由过期或者链路断开，路由表就失去作用了。

表驱动路由协议（table driven routing protocol）是一种主动路由协议，在路由过程中，每个节点分别在本地维护一个完整的路由表，当有数据需要发送时，直接根据目的节点地址查表获得下一跳需要发往的节点地址，并在每个中间节点依次查找，最终使数据以最短的路径抵达目的节点。

本文提出一种基于表驱动路由协议的路由表建立方法，并在FPGA硬件平台上进行性能验证。

1 路由协议概述

路由是指在网络中选择路径进行数据传输的过程。路由协议就是根据网络的状态信息，寻找最短的数据传输路径的网络协议。数据传输路径的选择会对网络性能产生巨大影响，因此路由协议对于网络来说十分重要。基于表驱动路由协议的路由，各节点在网络拓扑结构发生变化时发送更新信息，收到更新信息的节点更新本节点的路由表，以便及时准确地维护路由信息。不同的表驱动路由协议的区别在于拓扑更新信息在网络中传播的方式和需要存储的表的类型不同。

本文所提的表驱动路由协议的核心在于拓扑项的传输和路由项的缓存。处于网络拓扑中的节点通过无线数据传输进行通信，便可以得到本地链路（拓扑项），同时也可以通过无线数据传输将本地拓扑项转发至邻居节点。当网络拓扑结构发生变化时，网络中可以建链的各节点间互相发送各自拓扑项，并根据本地链路拓扑和接收到的网内拓扑在本地维护一个由拓扑项组成的拓扑集。

节点在更新拓扑集时，根据路由算法计算出所有的路由项，所有的路由项组成一个路由表。在传输数据时，若节点与目的节点不能直接建链通信，则根据目的节点地址查找路由表即可选出通信路径。各节点根据路由算法分布式计算节点到网内目的节点的路径。

2 拓扑集的建立

2.1 拓扑集初始化

节点拓扑集包含多个拓扑项，每个拓扑项代表一条目的节点和与其建链节点的通信链路。网内各节点在本地维护一个拓扑集，该拓扑集由本地拓扑项和接收到的网内拓扑项组成。拓扑项包含目的节点地址及与目的节点建链成功节点地址等数据项，拓扑项如表1所示。

当节点存在一条本地链路时，根据无线通信数据，可以得到链路节点的地址信息，即可建立一个本地链路对应的拓扑项（本地拓扑项），完成拓扑集初始化。

2.2 拓扑集维护

在ad hoc网络中，移动节点能以任意速度和方式在网络中移动，同时通过无线通信信道发送功率的变化、无线信道间的干扰、环境因素的影响等信息，节点间通过无线通信形成的网络拓扑结构随时会发生变化。在网络拓扑发生变化时，需要对本地拓扑集进行维护。本地拓扑集的维护主要包括：本地拓扑项的更新与发送，本地链路消息的发送与接收。

在网络运行过程中，若网络拓扑结构发生变化，节点会将根据变化产生的本地链路消息发送给所有邻居节点，其中本地链路消息包括节点地址和对应的邻居节点地址。同时节点还需要对本地拓扑项进行更新：链路状态从连接变成断开，则删除对应的拓扑项；链路状态从断开变成连接，则增加对应的拓扑项。

节点接收到本地链路消息后，解析出消息中的节点地址，将其与拓扑集中所有拓扑项的T_Last_Addr进行比较，若拓扑集中不存在该节点地址的拓扑项，则将该条链路消息发送给所有邻居节点，同时建立新的拓扑项放入拓扑集，拓扑项中T_Dest_Addr为本地链路消息中的邻居节点地址、T_Last_Addr为本地链路消息中的节点地址；若拓扑集中存在该节点地址的拓扑项，则更新拓扑项的T_Dest_Addr。

2.3 拓扑集的FPGA实现

拓扑集的FPGA实现主要是在FPGA上实现T_Dest_Addr和T_Last_Addr两个数组寄存器的缓存，其流程图如图1所示。网络节点的数据解析模块从接收的无线通信数据中解析出帧格式和发送节点地址。将解析的发送节点地址缓存至节点地址T_Last_Addr对应的T_Dest_Addr中；根据解析的帧格式，若该帧为路由信息帧，则将信息帧中的节点地址和邻居节点地址分别缓存至T_Last_Addr和T_Dest_Addr。

以6个节点的ad hoc网络为例描述拓扑集的建立过程，网络拓扑如图2所示。

在网络运行过程中，网内各节点根据网络路由协议建链，节点1与其能直接建链的节点2和节点4完成无线通信。各节点对接收到的通信数据进行解析，可得到通信节点地址和对应的节点编号，完成本地拓扑项建立，并将对应数据缓存至T_Dest_Addr和T_Last_Addr两个数组寄存器。设T_Dest_Addr[n]，T_Last_Addr[n]分别表示T_Dest_Addr和T_Last_Addr两个数组寄存器的第n个寄存器单元，其中n=0，1，···，5。具体缓存情况为：节点1地址缓存至T_Last_Addr[0]；节点2地址、节点4地址缓存至T_Dest_Addr[0]。

节点2将网络运行中得到的本地拓扑项和缓存的节点3拓扑项通过本地链路消息发送给节点1，节点1将解析出的节点地址和邻居节点地址缓存至T_Dest_Addr和T_Last_Addr两个数组寄存器。具体缓存情况为：节点2地址缓存至T_Last_Addr^[1]；节点1地址、节点3地址缓存至T_Dest_Addr^[1]；节点3地址缓存至T_Last_Addr^[2]；节点2地址、节点4地址缓存至T_Dest_Addr^[2]。

同理，节点4将本地拓扑项和缓存的节点5、节点6的拓扑项通过本地链路消息发送给节点1，节点1将解析出的节点地址和邻居节点地址缓存至T_Dest_Addr和T_Last_Addr两个数组寄存器。具体缓存情况为：节点4地址缓存至T_Last_Addr^[3]；节点1、节点3、节点5的地址缓存至T_Dest_Addr^[3]；节点5地址缓存至T_Last_Addr^[4]；节点4地址、节点6地址缓存至T_Dest_Addr^[4]；节点6地址缓存至T_Last_Addr^[5]；节点5地址缓存至T_Dest_Addr^[5]。

通过上述的解析与缓存，节点1即可获得本地拓扑集，用于路由表的计算。

3 路由表计算

3.1 路由表算法

在ad hoc网络中，每个节点都可以作为路由器来维护本地路由表。节点不仅具备数据发送和接收功能，也具备路由的选择、存储和转发功能。节点路由表由路由项组成，而路由项又由多个数据项组成，路由项如表2所示。

路由表的建立过程是网络中每个节点路由的计算过程。通过寻找以本节点为根节点的生成树方式，计算本节点到拓扑集中所有其他节点的路径。具体算法如下。

步骤1：为拓扑集中的每个T_Last_Addr等于本节点地址的拓扑项（本地链路）生成一个路由项，并将该拓扑项设为已计算。

路由项中数据项的取值方式为：路由项中的数据项R_Last_Addr等于拓扑项中本节点地址的T_Last_Addr；数据项R_Dest_Addr和R_Next_Addr等于拓扑项中本节点地址对应的T_Dest_Addr；R_Dist _Num的初始值设为1。

步骤2：为新建立的路由项（原路由项）寻找T_Last_Addr等于该路由项R_Dest_Addr且T_Dest_Addr 不等于本地链路的拓扑项（一个原路由项可对应多个拓扑项），为这些拓扑项的T_Dest_Addr建立新路由项，并将这些路由项设为已计算。

新路由项中数据项取值方式为：路由项的数据项R_Dest_Addr为拓扑项的T_Dest_Addr；路由项的R_Last_Addr为拓扑项的T_Last_Addr；路由项的R_Next_Addr为原路由项的R_Next_Addr；路由项的R_Dist_Num为原路由项的R_Dist _Num加1。

步骤3：判断拓扑集中所有的拓扑项是否均已经计算，若是则计算结束，否则继续执行步骤2。

3.2 路由表的FPGA实现

目前ad hoc网络路由协议的实现大多基于NS2、GloMoSim、OPNET等软件平台，但是在工程应用中，路由协议还需要在嵌入式硬件平台上实现。本文拟采用FPGA实现路由协议，以更快地建立和更新动态网络拓扑。

本文基于有限状态机（finite state machine，FSM）^[8-9]实现路由表管理，其流程图如图3所示。

当ad hoc网络的拓扑运行至图2所示状态时，拓扑集变化使能触发路由表生成功能。设R_Dest_Addr[n]，R_Last_Addr[n]，R_Next_Addr[n]分别表示R_Dest_Addr，R_Last_Addr和R_Next_Addr数组寄存器的第n个寄存器单元，n=0，1，···，5。根据图3，路由表的实现步骤如下。

步骤1：路由项初始化。设三个寄存器的初始值为0；T_Last_Addr等于本地节点地址即节点1地址时，根据路由算法将对应数据缓存至R_Dest_Addr、R_Last_Addr、R_Next_Addr数组寄存器。具体缓存情况为：

a） 节点1地址对应的T_Dest_Addr为节点2地址和节点4地址，则将节点2地址缓存至R_Dest_Addr^[1]、节点4地址缓存至R_Dest_Addr^[3]；

b） 节点1地址缓存至R_Last_Addr^[1]和R_Last_Addr^[3]；

c） 节点1地址对应的T_Dest_Addr为节点2地址和节点4地址，则将节点2地址缓存至R_Next_Addr^[1]、节点4地址缓存至R_Next_Addr^[3]。

步骤2：寻找T_Last_Addr等于该路由项的R_Dest_Addr且T_Dest_Addr 不等于本平台地址的拓扑项，即令T_Last_Addr为节点2地址和节点4地址，建立新的路由项。具体缓存情况为：

a） 节点2地址对应的T_Dest_Addr为节点1地址和节点3地址，由于节点1地址为本地节点地址，则将节点3地址缓存至R_Dest_Addr^[2]；

b） 节点2地址缓存至R_Last_Addr^[2]；

c） 原路由中节点1地址对应路由项的寄存单元R_Next_Addr^[2]缓存节点2地址，则将节点2地址缓存至R_Next_Addr^[2]；

d） 节点4地址对应的T_Dest_Addr为节点1地址、节点3地址和节点5地址，由于节点1地址为本节点地址，节点3地址已经计算，则将节点5地址缓存至R_Dest_Addr^[4]；

e） 节点4地址缓存至R_Last_Addr^[4]；

f） 原路由中节点1地址对应路由项的寄存单元R_Next_Addr^[4]存储节点4地址，则将节点4地址缓存至R_Next_Addr^[4]。

根据图2可知，节点1到节点3的路径有两条，即节点1—节点2—节点3、节点1—节点4—节点3，由于节点2—节点3路径先进行了计算，则节点4—节点3的路径不再进行计算。

步骤3：寻找T_Last_Addr等于该路由项的R_Dest_Addr且T_Dest_Addr 不等于本平台地址的拓扑项，即令T_Last_Addr为节点3地址和节点5地址，建立新的路由项。具体缓存情况为：

a） 节点3地址对应的T_Dest_Addr为节点2地址和节点4地址，由于节点2地址和节点4地址均已经计算，则不再进行计算；

b） 节点5地址对应的T_Dest_Addr为节点4地址和节点6地址，由于节点4地址已经计算，则将节点6地址缓存至R_Dest_Addr^[5]；

c） 节点5地址缓存至R_Last_Addr^[5]；

d） 原路由中节点5地址对应路由项的寄存单元R_Next_Addr^[5]存储节点4地址，则将节点4地址缓存至R_Next_Addr^[5]。

根据上述步骤可得到节点1到其余节点的路由表，再根据目的节点地址，查询R_Dest_Addr数组对应的编号，通过R_Next _Addr数组得到下一跳的节点地址。

3.3 路由性能分析

本文提出的路由协议在Xilinx公司的FPGA芯片XC7K410T上实现。当节点拓扑项发生变化时，若网内节点个数为N，则路由表生成的最长时间为2N²+3个时钟周期。以图2所示网络为例，当N为6时，在100MHz时钟下，路由表生成的最长时间为750 ns，芯片功耗为0.006 W。芯片各部分资源使用情况如表3所示。

可见，使用嵌入式硬件平台实现路由协议可以快速响应拓扑变化，路由时延低，硬件资源占用少且功耗小。

4 结论

本文提出了一种基于表驱动的ad hoc网络路由协议设计和FPGA硬件实现方法，该设计和实现方法的核心为拓扑项的实现和路由表有限状态机的设计与实现。经验证，使用FPGA平台实现路由协议，路由时延低，资源占用少且功耗小。

参考文献