基于Linux嵌入式系统按需路由协议架构设计与实现＊

谢毅勇 ，谢维波

(1.华侨大学 计算机科学与技术学院，福建 厦门 361021；2.华侨大学 厦门软件园嵌入式技术开放实验室，福建 厦门 361008)

Ad hoc网络[1]是一种特殊的对等式网络，它不需要固定的通信设施支持即可快速建立无线网络，其最初的动机是满足战场生存的军事需求。由于其自组能力、低成本、工作寿命长等特点，Ad hoc网络逐渐进入了民用和商用领域，遗憾的是发展较为缓慢。其主要原因之一就是Ad hoc路由协议通常采用新的路由模式，并不支持目前操作系统路由体系结构。若没有通用的操作系统路由体系结构解决方案，路由算法研究员就得被迫进行低级系统程序设计，而且往往会无计划地更改系统内部，以获得更多功能的Ad hoc路由要求，这容易导致系统不稳定。许多研究人员为了回避这种低级系统程序设计，大多从事基于仿真路由算法工作[2-3]而很少真正在产品或嵌入式上实现，所以实际应用价值不大。为了加速Ad hoc网络民用商用产品发展，设计一个Ad hoc通用嵌入式系统路由体系结构迫在眉睫，Ad hoc网络和嵌入式系统相结合是必然的。在嵌入式系统下实现无线自组网才有实际应用意义。

针对上述问题，本文首先分析了Linux操作系统的原有工作方式以及在此体系结构上实现按需路由协议的问题，并给出了合理的解决方案。提出一种基于Linux操作系统实现通用的按需路由协议[4]体系结构，使Ad hoc研究员易于在此路由体系结构上进行路由算法编程，而不用进行底层内核系统编程。最后，本文根据此方案实现Aodv路由协议并应用在实际的网络中，从而验证方案的性能及可行性。

1 Linux系统现有路由体系结构

目前的主流网络体系结构一般将路由功能分为两部分：分组转发功能模块和分组寻路功能模块[5]。分组转发是指根据内核路由表(转发表)的信息，将需要发送的数据分组，通过指定的网络接口发送到下一跳的节点。分组寻路是指建立转发表的过程，实现路由协议的逻辑计算，根据与其他主机交换的路由信息，计算出到其他节点的正确路由。转发表含有充分的信息来完成转发使命，而路由表中包含路由算法用于发现和维护路由的信息。

在通用的嵌入式开源操作系统之一的Linux操作系统的体系结构中，分组转发功能模块的转发表是在内核空间实现的，在查找内核转发表的时候，根据转发表项的最佳匹配原则进行转发。如果找不到匹配的转发表项，则按缺省路由发送，一般是将网关作为缺省路由的下一跳节点。如果缺省路由又不存在，操作系统则将把这个数据分组丢弃。分组寻路功能模块可以在内核空间实现，也可以在用户空间实现。本文采用在用户空间实现[6]，如图 1所示。

把分组转发功能模块和分组寻路功能模块分开的主要原因是数据分组转发必须尽可能快且有效地遍历转发表，故分组转发功能模块需驻留在内核中。然而分组寻路功能模块涉及复杂的数据分组或内存密集型读写任务，所以应该置于内核外。这种分离的原则使Linux操作系统中的路由既有效率又灵活。

2 按需路由协议实现的关键问题

目前大多数通用嵌入式操作系统中的路由体系结构都是按照有线网络路由协议的方式来构造的，这些路由协议为主动路由协议。在这种路由体系结构上，只能实现 Ad hoc主动路由协议(如 Dsdv路由协议)，而不能实现 Ad hoc按需路由协议(如 Aodv、Dsr路由协议)。本文将探讨不能在通用路由体系结构实现Ad hoc按需路由协议三个关键的难点。

(1)当发送数据分组的时候，如果不存在从节点到目的地址的路由，则需要发起路由查找过程，但在通常情况下，没有路由匹配，内核将立即删除该数据包。然而，这不是一个按需临时路由想要的情况。在按需路由中，并不是所有的路线被固定安排好，有些路线是必须在需要的时候“发现”。所以在这种情况下，正确的行为应该是请求发现路由，并在路由表更新路由或寻找结束以前，数据分组将不会被发送出去或者丢弃处理。

(2)需要建立一个缓冲区，在按需路由协议等待路由发现的过程中，数据分组需要进入一个缓冲区，该缓冲区设置在内核外，因为可减少内存和CPU的负荷。

(3)为了减少查找内核路由表的代价，就需要定期维护更新这路由表，即时把失效的路由清除。为了实现这功能，需要建立一个路由检查表。所有表都有一个相关定时器，当该表的路由被使用时，它的定时器就必须重置。当定时器的时间用完时，则该表项就要从内核路由表中删除。关键问题是内核中没有记录路由使用的机制，所以路由守护进程根本无法知道内核中使用过哪些路由或什么时候使用过路由。

以上分析可知目前通用嵌入式操作系统没有这种机制来支持上述行为，所以通用的嵌入式系统应该为Ad hoc网增加以下系统功能：

(1)判断是否是按需路由，如果是，则查看是否有路由请求；

(2)把请求告知Ad hoc守护进程；

(3)建立一个高速缓冲区，将需要路由请求的数据分组送到缓冲区；

(4)当路由发现完成或发现失败，将数据分组注入内核中或对其抛弃。

(5)建立路由检查表，且能定期对其维护，以便能更新内核路由表。

3 通用的按需路由体系设计实现方案

3.1 Ad hoc按需路由协议体系结构

针对本文提出的问题，所设计的按需路由体系如图2所示。

图2 通用的ad hoc按需路由协议体系结构图

3.2 Ad hoc按需路由协议体系结构组成

通用的Ad hoc按需路由协议架构主要组成有：操作系统原有的内核转发表(本文不对其修改)、一个可加载的内核模块route_check(即路由检查表)、netfiilter钩子程序[7]、用户空间的Ad hoc支持库 ASL(Ad hoc Support Library)和Ad hoc路由守护进程。netfiilter钩子程序是系统自带的，用来捕捉每一个发送数据分组，记录每条路由的最后使用时间，然后对路由检查表做相应的处理，路由检查表约800行代码。其中，ASL是一个共享库，约2 500行代码，用来实现按需路由功能。当ASL接到一个延时发送的数据分组，就会告知Ad hoc守护进程，以便对数据分组的目的地址进行路由发现。之后它将该数据分组储存在一个临时缓冲区中，等待守护进程返回路由发现的结果。一旦这些处理完成，相应的内核路由表就加入新的元组，数据分组移出缓冲区，重新注入到包转发功能块的队列中。ASL基本函数如表1所示。

表1 ASL基本函数

3.3 Ad hoc按需路由协议体系结构数据分组传递流程

在实现方案中，为了确认是否有路由请求，利用一个系统不用的隧道设备，Universal TUN/TAP(tun)[8]，此设备虚拟了一个网络接口，当数据分组发送的时候，如果目的地址不存在其路由，则这些数据分组将tun作为缺省路由的下一跳“接口”。这样就可以通过/dev/net/tun设备将所有需要路由发现的数据分组传递到用户空间做进一步的处理。

处理工作第一步为调用open_route_request()函数来打开。当一个新的数据包从/dev/net/tun中读出时，Ad hoc守护进程就会利用read_route_request()函数读取路由请求，之后就可以初始化路由发现。同时，数据分组会在一个临时缓冲区排队。因为缓冲区在用户空间，所以可以有一个较大的缓冲区来存储数据分组，这样即使分组在路由发现延时很大的情况下也不会出现丢失的情况。在路由发现成功完成以后，就将数据分组通过raw socket重新注入内核。

为了保持路由表的有效性，内核可加载模块route_check在Netfilter的NF_IP_POST_ROUTING钩子中注册，这样每个外出的数据包都要经过这个模块。该模块只是查看数据包的首部，更新相应的时间戳值，并输出到/proc/asl/route_check中。ASL通过 API中的query_route_idle_time()告知Ad hoc路由守护进程内核路由表的使用情况，这样守护进程就可以检查路由的更新和删除内核路由表失去时效的路由。

route_add()和 route_del()函数使用 ioct()接口加入或者删除内核中的路由。

4 Aodv按需路由协议架构

通过上述设计架构，在不用改变系统的内核情况下，就可以实现移动自组网按需路由协议在通用的操作系统上的应用。

图3是根据Aodv基本的路由功能(如 RREQ、RREP、RERR等路由功能)，置入通用分组寻路功能模块使其成为Aodv专用的分组寻路功能模块，如图3所示。

图3 Aodv按需路由协议架构

5 方案实施验证分析

实验现场为华侨大学厦门软件园嵌入式技术开放实验室(厦门软件园二期54号402，华侨大学产学研基地)。网络节点由两个PC机节点和一个嵌入式系统节点组成。PC机节点配置是DELL工作站PY597+ZD1211b无线网卡，安装CentOS 5操作系统 (内核版本号为26.18-128.e15)，加载Aodv路由协议模块，支持直接或多跳的通信。嵌入式系统节点配置则为致远MagicARM2410+Asus WL-167无线网卡，加载Aodv路由协议模块，支持直接或多跳的通信。PC1的IP为192.168.0.5；PC2 的 IP 为 192.168.0.55；K1 的 IP 为192.168.0.45。网络拓扑如图4所示。

由于测试区域较小，节点PC1不需要经过中继节点K1就可直接到达节点PC2。为了测试Aodv路由协议的“跳转”功能，采取屏蔽策略，使PC1与PC2相互屏蔽。

(1)PC1对PC2的屏蔽

图4 实验环境

在 PC1执行：iptables-A INPUT-p ALL-m mac--mac-source 00：02：72：61：ED：4B -j DROP。 其中，00：02：72：61：ED：4B 为 PC2的 Mac地址， 使得 PC1 拒绝PC2发送的数据包。

(2)PC2对PC1的屏蔽

在 PC2执行：iptables-A INPUT-p ALL-m mac--mac-source 00：02：72：61：ED：53 -j DROP。 其 中 ，00：02：72：61：ED：53 为 PC1 的 Mac地址， 使得 PC2 拒绝PC1发送的数据包。

①K1节点定期广播传送HELLO消息，发现了附近的两个节点PC1和PC2，如图5所示。

图5 K1节点发现PC1、PC2过程

②PC1节点定期广播传送HELLO消息，先发现了附近的K1节点，然后透过K1发现了PC2，并对其建立路由。如图6所示。

图6 PC1与PC2路由建立过程

③PC1节点 Ping PC2节点，信息返回成功，如图 7所示。

从Ping命令的输出结果中可以看到，数据包所经过的路径是 PC1→K1→PC2→K1→PC1。经过 K1节点上Aodv模块的路由功能将Ping数据包转发，使得不能直接通信的节点PC1和PC2实现了数据传输，具有了路由发现和网络自组的功能。

图7 路由建立成功

本文提出按需路由协议的实现方案，充分考虑了按需路由的特点，针对按需路由在linux嵌入式环境下实现的难点，提出了解决方案和设计实现方案，其功能函数具有良好的通用性。该方案为以后研究员验证和比较各种协议在实际网络中的性能提供了良好的基础。

[1]HARTENSTEIN H.Topics in ad hoc and sensor networks-A tutorial survey on vehicular ad hoc networks[J].IEEE Communications Magazine，2008，46(6).

[2]GIOVANARDI A， MAZZINI G.Ad hoc routing protocols：emulation vs simulation[C].2nd International Symposium on Wireless Communication Systems， 2005：140-144.

[3]BOUKHALKHAL A， YAGOUBI M B， DJOUDI M， et al.Simulation ofmobile ad hoc routing strategies[C].4th International Conference on Innovations in Information Technologies， Dubai， United Arab Emirates， 2007：128-132.

[4]余旭涛，毕光国.Ad Hoc网络按需路由协议的改进[J].计算机学报，2004，27(6).

[5]PETERSON L L，DAVIE B S.Computer networks：a system approach[M].Morgan Kaufmann Publishers， 2nd edition， 2000.

[6]RANDHAWA T，RICHAROS J.Implementation of a kernel mode IPv6 AODV routing daemon to improve data throughput[C].2005 IEEE International Conference on Communications(ICC 2005)， 2005(5)：16-20.

[7]Netfilter/Iptable homepage[EB/OL].http： //www.netfilter.org，2005-09.

[8]Tun/Tap universaldriver[EB/OL].http：//vtun.sourceforge.net/tun/，2005-10.