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所示。

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所示。

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所示。

[1] [2]  下一页