1 动态源路由
　　路由算法是移动自组网络研究的关键技术之一。在移动自组网络中，任何2个非邻节点传递数据，必须经过其他中间节点中继，而中间节点的可移动性时常导致路由失效。因此，路由协议直接影响网络运行。路由维护是路由的一个组成部分。传统网络的路由维护需要周期发送路由信息、分析路况和更新路由。这种路由表维护机制不适合有限的带宽、能源及处理能力的移动自组网络。研究者们提出了许多针对移动自组网络的路由协议。其中，比较公认的是DSDV、AODV、ZRP和DSR等路由协议。按需路由算法已经成为当前路由算法的一个基础，其目的是减少路由建立过程中不必要的控制包数量。动态源路由^[1]DSR(Dynamic Source Route)是典型的按需路由协议，它不需要全程(从网络建立到网络解体)维护路由，只有当某节点有数据需要传送时，才进行路由发现、路由维护和路由释放三个过程。该协议的路由发现过程被证明是有效的^[2]，也因此使DSR协议成为IETF的研究重点之一。然而，该协议的路由维护过程却会消耗许多控制带宽和能源。首先，当原路由失效时，DSR将失效信息反馈给源节点，再由源节点重新发现路由，这个过程将消耗许多网络资源；其次，已被激活的数据因路由断开而必须重传，无疑又浪费前次使用过的资源。为此，DSR算法又提出优化措施，即首先在断点处查找是否有到达目标的路由，若有，则选择这条路由；否则，将断开消息反馈给源节点，并重新发现路由。但是，该方法需要看网络建立的时间长短。若网络建立时间较长，网络上曾经有过多次信息交换，则节点存储路由的可能性大；反之，这种可能性较小，就必须回到源节点重新发现路由，浪费有限资源。
2 相关工作
　　为解决资源浪费问题，许多新算法被提出。多路径路由算法是其中之一。算法RBMR^[3]提出一种冗余路由算法，根据节点冗余度选择路由。算法NDMR^[4]建立多条没有交叉节点的路由担任备份路由，以避免路由断开时对其他备用路由的影响。其不足在于源节点拥有全部路由信息，断点必须反馈一个RERR(Route Error)包给源节点，由源节点再选择一条新路由重新发送数据。由于被激活的数据流已发送到中途，再进行第二次重传，会造成能量和带宽的浪费。因此，本文提出路由快速切换算法QSRA(Quickly Switching Routing Algorithm)。这是一个完全的分布式算法，具有快速切换路由能力。QSRA算法不是将全部路由信息存储在源节点，而是仅在主节点上存储其下游节点。这个下游节点包括下游主节点以及下游切换节点信息。正常数据传输时使用下游主节点；当主路由断开时，断点首先检查本身是否有下游切换节点，若有，则选择其继续传输数据；否则，断点将向其上游节点报告断开信息，上游节点继续查找有无下游切换节点。如此下去，直到一个上游节点拥有下游切换节点继续转发数据为止。该算法适合大型非稀疏网络。例如，当人们在机场候机时接收共享娱乐节目等。
3 QSRA算法描述
　　实现算法QSRA有二个目的：(1)在路由断开之前尽快地将数据包传送到目标节点；(2)若路由断开，则尽快切换到另一路由上继续转发数据。为此，构造路由结构，其路由发现过程如图1所示。算法在路由发现过程中，完成二项工作：建立主路由和切换路由。图1所示的节点S是源节点，节点D是目标节点，节点A，B，……L是中间节点。图1中带箭头的粗实线连接部分是主路由，如从S到D的主路由是S-A-B-C-D。主路由上的点为主节点，即 A、B、C为主节点。图1中的虚线部分如S-E-F-G-H-D 和S-I-J-K-L-D是切换路由。相应的E、F、……L是切换节点。在构造这样一个路由结构的过程中，为了清晰，假定每个主节点都有下游切换节点。请注意，在实际情况中，不一定每个主节点都有下游切换节点，特别是在稀疏网络中。所以，QSRA算法更适合大型非稀疏网络环境。下面将详细描述路由发现和路由维护过程。

3.1 路由发现
3.1.1 路由请求过程
　　一个源节点依靠洪泛方式发出一个路由请求RREQ(Route Request)，如图1所示。请求包结构主要包括源节点地址、目标节点地址、路由信息、跳数以及包序列号。收到RREQ包的每个节点记录如下信息在缓存中：源节点地址、目标节点地址、上游节点地址、下游节点地址(不是下游切换节点地址)、跳数和包序列号。如果节点二次收到同一序列号或大于该序列号的RREQ包，则丢弃该包；否则，节点除记录上述有关信息外，将序列号加1，并洪泛该包。根据无线通信原理，当下游节点洪泛时，其上游节点也能够收到此信息。利用该原理，让上游节点记录比自己收到的包序列号大1的包的地址，也就是其下游节点地址。直到目标节点收到RREQ包后，停止洪泛。为获得多条路由，QSRA算法为目标节点设置一时间段，以等待RREQ包从多条路由到达目标节点。根据到达先后，QSRA算法选择最早到达的路由为主路由，选择相继到达的几个路由作为切换路由。之后，目标节点沿主路由返回主路由信息和切换路由信息。当这些信息经过每个主节点时，主节点将缓存中记录的下游节点信息与切换路由信息作比较，也就是进行节点比较，保留相同的节点。其目的是使主节点拥有切换路由上的切换点。QSRA算法选择花费时间相对少的路由作为切换路由。一个RREQ包如果在一条路由上花费的时间比其他路由少，则说明该路由没有拥塞(或拥塞较少)，有充足的带宽，或者路由较近，这样能使一个包较快到达目的地；否则，路由须排队等待带宽，拥塞较重，或跳数较多，都不能使RREQ包较快到达目标。因而选择较早到达目标节点的路由作为切换路由。
　　下面以图1为例，说明QSRA的路由发现过程。源节点S向其邻节点发送一个RREQ包，其邻节点A、E和I收到此信息包后，首先记录上游节点S、路由和跳数等信息，并将包序列号加1后，继续向其各自的邻节点发送此包。如上所述，节点S收到此包后，记录节点A、E、I为其下游节点；同时，A的下游节点B、E、I也收到加1后的请求包，并分别记录A为它们的上游节点。如此传输，每个中间节点都记录其上、下游节点。表1列出主节点拥有的下游节点。当节点E分别从S和A收到RREQ请求时，节点E自动放弃从A收到的RREQ包，以避免路由环。当目标节点D从不同路由收到该请求包后，根据到达D点的先后，选择最早到达的路由为主路由，图1中设S-A-B-C-D为主路由(假定该路由最先到达)，主路由上的节点为主节点；再依次选择S-E-F-G-H-D和S-I-J-K-L-D为切换路由，切换路由上的节点为切换点。

3.1.2 路由反馈过程
　　目标节点选择好主路由和切换路由后，将沿不同路径返回不同路由反馈包RREP(Route Reply)。沿主路由返回的RREP包，内容包括主节点信息和切换点信息。返回主节点信息主要是使主路由上的节点知道自己及其上下游节点。同样，沿主路由返回切换节点信息以使主节点知道存储在缓存中的哪一个下游节点是切换节点，以备必要时切换。当切换节点到达主节点时，主节点将记录的下游节点与切换节点比较，留下相同的节点。由此得到主节点在切换路由上的切换点；沿切换路由返回的RREP包携带切换节点信息，以便让切换路由知道目标节点选择自己为切换路由。这里假定每个节点自愿担当路由器，除非该节点离开。例如，图1中，目标节点D返回到主路由上的信息包括节点D、C、B、A、S以及节点信息D、L、K、J、I、S和D、H、G、F、E、S。对于节点C，当它接收到这些节点信息后，除标记D是其下游节点外，还留下节点K和G作为它的切换节点。
3.2 路由维护
3.2.1 路由维护模型
　　一些原有算法[2～5]的路由模型如图2(a)所示。它形成从源节点到目标节点多条非耦合结构(或者说是并联结构)。该结构的优点在于一条路由失效时不会影响其他路由，缺点是增加控制包，每次路由失效，都需要回到源节点取其他路由。QSRA算法的路由模型如图2(b)所示。它像一片叶脉形状，当主路由失效时，这种结构能够迅速切换到其他路由。QSRA除了包含这种非耦合结构外，还具有另外的结构，即主节点与切换路由有链接。这实际上是一种串并联兼有的结构。它的优点在于，当主路由失效时，断点可以迅速切换到备用路由上。当一条切换路由失效时，还可以切换到另一条切换路由上继续转发数据。而且这种结构占据的节点个数相对于MRODP^[2]的第2个算法少。这里参照多路由算法AMR^[6]，选择3~4条切换路由。

3.2.2 路由维护过程
　　为尽快传送数据到目标节点，QSRA算法建立了串并联兼有的路由结构。当主路由和切换路由都建立起来之后，源节点S 能够通过主路由发送数据到目标节点。如果主路由上的某节点移出其邻节点的传输范围，则主路由断开。此时，如果断点有切换节点，则立即选择该点继续转发数据包；否则将反馈RERR包给它的上游节点，再由该上游节点检查自己是否有切换节点。这样依次向上游推进，直到有一个上游节点具有切换节点为止。因此，算法QSRA能够保证将数据包尽快传送到目标节点。它对网络的要求是节点密度不能太稀疏，否则，不能形成串并联结构。如图2(b)中，当节点C0移出节点B0的传输范围时，主路由断开。此时，节点B0 检查自己是否存储切换节点，若B0点存储切换节点(B1，B2，B3，B4)，则选择其中的一个继续转发数据。若B0节点没有切换节点，则向上游节点A0报告此链路" title="链路">链路断开信息。A0节点再看自己是否存储切换节点。在整个路由发现和维护过程中，算法QSRA仅在路由发现过程中增加了一些控制开销，即切换节点从目标节点向源节点回传过程，但它属于单播，比DSR^[1]和MAR^[6]洪泛操作的控制包数量低得多。
4 仿真试验及结果分析
4.1 仿真试验
　　仿真试验中的数据如下：节点最大移动速度16m/s，最小移动速度1m/s，暂停时间为0秒，50个节点随机移动范围为2000m×2000m，无线传输频率2.4GHz，无线传输范围250m，802.11MAC协议，CBR10 frames/s，总数据量10MB。用端到端" title="端到端">端到端延迟、控制包数量以及包接收率来评价算法QSRA，并与DSR^[1]及NDMR^[4]作比较，进行仿真。当节点最大速率增加时，数据包的端到端延迟、总控制包数量和包接收率分别如图3～图5所示。

4.2 结果分析
　　平均端到端延迟是指包从源节点到目标节点的平均时间延迟。图3中QSRA算法的时间延迟远低于DSR和NDMR算法，且曲线比较平稳。这主要是因为当主路由失效时，QSRA有切换路由，可以立即切换，所以时延较低。而DSR算法在主路由断开时，需要重新发现新路由，所以占用时间多。NDMR算法也回到源节点，但它不是重新发现路由，而是取已经存储在源节点的路由，所以它的延迟比DSR低，比QSRA高。从曲线整体看，随着移动速度的增加，3条曲线都有上升趋势。这主要是由于移动速度的增加加速了链路断开的概率。QSRA增加了切换次数；NDMR需要频繁地回到源节点去路由；DSR需要不断地回到源节点重新发现路由，因此总的时延增加。但是，即使如此，QSRA的表现仍然比较平稳，比DSR和NDMR好许多。
　　图4中总的控制包数量包括RREQ、RREP以及ERROR包的总和。从整体看，随着移动速度的增加，曲线上升。因为移动速度加快，增加了链路断开的频率，无论是切换还是回到源节点或是重新发现路由都会增加控制包数量。但是相对来看，QSRA曲线要好于DSR和NDMR曲线。这是因为前者是及时切换到其他路由，它仅需要较少的控制包就能进入正常续传轨道，曲线较稳定；而后二种算法需要回到源节点去路由或重新找路由，这无疑增加了控制包数量，特别是DSR的曲线。
　　图5中，QSRA算法的包接收率表现得很平稳，受移动速度的影响比较小；而NDMR的包接收率比较低，DSR算法最低。包接收率低的现象，主要受移动速度的影响。当移动速度增加，加快链路断开的频率，DSR算法必须重新发现路由，传送到中途的数据包被丢弃，总的包接收率低；NDMR算法也一样有弃包操作，只是相对于DSR，它重新发现路由的概率低，弃包现象不严重，但当存储的多路由用尽后，重演DSR过程；而QSRQ算法因为有切换路由，直接将数据包切换到备用路由继续传输，故接收率相对较好。从整体曲线看，随着移动速度的增加，曲线均有下降趋势。分析原因主要是移动速度增加，链路断开的概率增加，都有弃包操作，再加上传输时间延长，重传操作频繁，加重网络负载，丢包现象严重，总的包接收率随移动速度增加而下降。
　　多路由机制已经不是新设想，但是每种多路由算法各有不同。QSRA算法主要从快速切换路由的角度考虑。因为移动自组网络的节点移动时常导致数据传输到中途时，路径失效，传输被迫中断。于是，一些算法提出回到源节点取备用路由，重新传输。而QSRA算法采用就地取材的办法，在断点或其附近迅速切换到预备路由上，保证最快时间继续传递数据。它在路由发现过程中，备份其他能够到达目标节点的节点，当路由失效时选择这些备用点。不仅如此，当一个备用点失效时，QSRA算法还可以继续取备用点传输，避免回头去重新取路由而造成的浪费。算法分析和仿真表明相对于DSR算法和NDMR算法，QSRA算法在平均端到端延迟、控制包数量、包接收率方面都有不同程度的改进。
参考文献
1 Johnson D J，Maltz D A，Hu Y C.The dynamic source route protocol for mobile Ad Hoc networks(DSR).IETF Mobile Ad Hoc Networks working Group，Internet Draft work in progress，2003
2 Nasipuri S，Castaneda R.Performance of multipath routing for On-Demand porotocols in mobile Ad Hoc networks.Mobile Networks and Applications，2001：339～349
3 Kim S K，Noh W J，An S S.Multi-path Ad Hoc route considering path redundancy.In：Proc of the 8th IEEE International Symposium on Computers and Communication，Antalya，Turkey，2003
4 Li X F，Cuthbert L.On-demand node-disjoint multipath route in wireless Ad Boc networks.In：Proc of the 29th Annual IEEE International Conference on Local Computer Networks，Tampa，Florida，USA，2004
5 Leung R，Liu J L，Poon D et al.MP-DSR：A QoS-awae multi-path dynamic source route protocol for wireless Ad-Hoc Networks.In：Proc of the 26th Annual IEEE Conference on Local Computer Networks，Tampa，Florida，2001
6 Chen Y Q，Guo X F，Zeng Q K et al.AMR：A multipath routing algorithm based on maximum flow in Ad Hoc networks.In：ACTA ELECTRONICA SINICA，China，2004：1297～1301