摘 要： 针对低速无线个域网的特点，在AODV基础上设计并实现了一种考虑节能、对硬件资源要求低、收敛速度快的路由协议，该协议包含“反馈控制标志”、“上游节点寻路”、“只限广播的扩展环搜索”等优化策略。进一步给出路由协议模型、报文格式以及算法实现流程，与同类协议进行了性能比较。实验结果表明，协议在存储资源消耗、链路修复、带宽占用等方面具有很强的优势。
    关键词： 低速无线个域网； 路由协议； AODV

    低速无线个域网（LR-WPAN）是指在个人操作空间POS（Personal Operation Space）内低速率、低功耗、低成本的设备之间建立无线通信实现各种信息交互的一种区域性联网技术，具有易于安装、可靠传输、短距离通信、极低功耗、协议简单灵活等特点，可以广泛用于智能家居、远程医疗和工业控制等领域。
    目前，LR-WPAN路由协议没有统一标准，各LR-WPAN商业和研究组织采用不同的路由协议。这些协议大多是AODV^[1]的简化和改进版本，参考文献[2-6]对基于AODV的各种协议做了详尽的介绍和比较，从中总结常见的简化措施有：
    （1）不使用目的节点序列号，同时规定只有分组的目的节点可以回复RREP（路由应答）以避免环路问题。
    （2）取消前向节点列表。传播链路失效消息的方式改为向上游广播或向源节点单播RERR（路由错误包），有的协议甚至取消RERR，完全依靠本地链路修复重建路由。
    （3）不采用IP包作为载体。路由协议直接实现在2.5层，对上层协议透明。
    本文所提出的路由协议采用了这些简化措施，同时创新性地提出了“反馈控制标志”、“上游节点寻路”、“只限广播的扩展环搜索”等技术，具有低资源消耗、低带宽占用、收敛速度快等优点，能够满足低速无线个域网的需求。
1 基于AODV的路由设计方案
1.1 LWRP的提出
    AODV的各种改进协议适用于低速无线个域网，但大部分协议还存在以下问题：
    （1）对节能考虑不周。例如AODVjr只选最快的路由，没有把链路质量、节点能量考虑在内。
    （2）路由表占用存储资源过多。例如LOAD需要建立端对端的双向通信，中间节点需要有到两个通信对端的双向路由，在网络规模较大的情况下路由表对存储资源的占用很大。
    （3）对广播风暴抑制不够。在一些监测控制应用中，LR-WPAN节点相对密集，广播包数量过多会引起通信信道的阻塞。
    针对以上问题，提出了更适合低速无线个域网的路由协议LWRP（LR-WPAN Routing Protocol)。本协议具有以下特点：
    （1）在路由请求报文中设置“弱链路条数”、“能量告警节点个数”等字段。优选路由时，综合考虑跳数、链路质量、节点能量情况，而且将节点能量作为选路最重要的指标，能够满足LR-WPAN对节能的需求。
    （2）反馈控制标志。在路由请求和路由回复报文中设置“反馈控制标志”字段，能够根据节点本身的特点决定是否建立反向路由，在不影响网络功能的前提下大大减少路由表的条数，从而减少对存储资源的占用。
    此设计基于以下考虑：LR-WPAN一般用于检测控制，数据流具有多对一单向通信特点，网络中大部分节点只关心去往Sink节点的路由，在无需反馈控制的路径上只需建立到Sink的正向路由，因此路由表可以极为精简。
    （3）只限广播的扩展环搜索。在路由请求报文中设置“广播跳数限制”字段，对报文传输范围进行灵活控制，能够在限制广播包扩散范围的情况下保证建立路由的成功率。
    图1是广播包跳数限制示意图，其中D、E没有到Sink的路由。 C请求到Sink路由，其路由请求包中“广播包跳数限制”字段为1，那么D收到此包后不会再广播该请求，E点不会受到干扰。而A点有到Sink路由，会继续单播该请求，最后C与Sink之间通过A、B两跳成功建立路由。

    设计思想来源：AODV提出“扩展环搜索”技术，以避免路由请求包整网扩散。需要注意的是，AODV允许中间节点回复路由请求，即中间节点有到目的节点路由时会回复RREP，而LR-WPAN使用的各种AODV简化协议，由于没有采用序列号机制，均规定只有目地节点可以回复路由，如果依然采用AODV中“扩展环搜索”策略，将存在以下问题：当发起RREQ的节点与目的节点相距较远时，即使中间节点有到达目的地的路由，也不能回复RREP，这样需要多次搜索，对网络带宽占用造成很大压力，可能得不偿失。
    (4)上游节点参与本地链路修复，增加了路由修复成功率，提高了网络自愈能力。
    修复算法描述如下
    收到路由修复RREQ；
　     IF有到RREQ目的节点的路由 THEN
　       IF 此路由下一跳是RREQ源节点 THEN
　          删除此路由表项；
　　　　      IF  广播包限制字段非零 THEN
                  广播RREQ；
　　　　      ELSE
                  丢弃RREQ包；
              END IF
　　　　      ELSE
                  单播RREQ到下一跳；
            END IF
　     ELSE
　　     IF  广播包限制字段非零 THEN
             广播RREQ；
　　     ELSE
         丢弃RREQ包；
         END IF
    END IF
    上游节点参与路由如图2所示，其中，A节点转发目的为Sink的数据包时没有得到下一跳节点B的确认（B节点死亡），广播源为A目的为Sink的路由请求。A的上游邻居D 收到该RREQ之后，判断出自己到Sink的路由下一跳为A，于是删除到Sink路由并继续广播该RREQ报文，最后A到Sink通过D、C建立路由。

1.2  路由协议模型
    IEEE 802.15.4^[7,8]是低速无线个域网媒体访问控制层和物理层标准，LWRP运行在这一标准之上并直接使用IEEE 802.15.4规定的EUI-64 地址作为路由依据。为了在IEEE 802.15.4上同时运行LWRP和TCP/IP等协议，需要一个中间适配层。LWRP协议所处层次如图3所示。

1.3  报文格式
    LWRP规定两种报文RREQ、RREP帧格式分别见图4(a)、(b)。

    字段说明如下：
    （1）类型：0x00表示RREQ报文；0x01表示RREP报文。
    （2）反馈控制标志：值为１表示RREQ源和目地需要双向通信，否则为单向通信。
    （3）弱链路条数：从RREQ源节点到当前节点经过的链路质量低于规定标准的链路条数。
    （4）能量告警节点个数：从RREQ源节点到当前节点经过的电量不足的节点个数。
    （5）跳数：报文从出发点到当前节点经过的跳数。
    （6）广播跳数限制：RREQ广播范围限制。
    （7）路由请求ID：与源节点一起，唯一标识一个RREQ消息。
    （8）源地址：RREQ源节点的IEEE802.15.4定义的64bit接口标识符。
    （9）目的地址：RREQ目的地址的IEEE802.15.4定义的64bit接口标识符。
2 路由算法的实现
    LWRP是按需驱动路由协议，节点不需要维护及时准确的路由信息，当向目的节点发送报文时，源节点才在网络中发起路由查找过程，协议开销小，符合低速无线个域网节能要求。
2.1 路由建立过程
    （1）发送RREQ
    当某节点发送数据到其他节点时，首先查找本地路由表，如果发现到目的地址的路由不存在，则缓存当前数据包，封装RREQ报文，广播发送RREQ消息。
    （2）中间节点接收到RREQ
    如图5所示，接收RREQ报文的节点首先判断RREQ报文目的地址是否是自己，如果不是，则查询自己的入口表。

    如果已经存在入口表项，表明已经接收过与该RREQ源地址发送ID号相同的RREQ报文。为防止广播风暴，该节点抛弃RREQ报文。
    如果不存在该入口表项，则在路由表中查询能够到达RREQ源地址的路由。如果已经存在该路由，则比较这两条路由，选择较好的路由进行存储；如果不存在该路由，则临时建立一条到RREQ源地址的逆向路由。然后，节点查询路由表中到RREQ报文中目的地址的路由，如果存在，则向目的节点单播RREQ消息，否则继续广播RREQ报文。
    （3）目的节点接收RREQ和发送RREP
    RREQ的目的节点首先缓存RREQ报文消息，由于广播RREQ寻路过程，节点接收多条路由到达的报文消息，所以需要等待合理时间T，进行多路由的优劣判断。协议构造路由优选函数f(m,h,n)：
     f(m,h,n)=Am+Bh+Cn
其中,m为源节点到目的节点经过的电量不足节点的个数，ｈ为源节点到目的节点的跳数，ｎ为从源节点到目的节点弱链路的条数。考虑到节能是其中最主要的因素，结合实际测量情况，在开阔地带室外环境下，可取A= 256，B=1，C=2。目的节点为每个到达的RREQ计算其f值，选择f值最小的路由进行回复。
    （4）接收RREP
    接收RREP的过程如图6所示。当节点接收到RREP报文，首先建立到RREP源地址的路由表项，然后判断RREP目的地址是不是自己。如果是，则发送缓存队列中的缓存数据；如果不是，则建立或者更新到RREP源地址的路由表项，并找出到RREP目的地址的路由，判断RREP中的反馈控制位是否为1，是则将此路由修改为正式路由，继续单播RREP报文。

2.2  路由维护过程
    节点向邻居节点发送数据后，在一定时间内没有收到确认帧，则认为该邻居节点失效。此时，节点缓存当前数据，并发起本地修复过程，广播RREQ寻找到该数据目的节点的路由。
    节点本地修复RREQ的“广播跳数限制”取值比较小，一般小于3，以避免RREQ报文引起网络中广播风暴。广播跳数限制不会影响单播RREQ所能到达的网络范围，因此这种设计既能避免广播包扩散又能很好地修复路由。
3  LWRP的性能分析
    实验网络采用图7所示拓扑，其中只有C需要反馈控制，各节点只与周围邻居通信。图中括号内数字是节点EUI-64地址最后一个字节的十六进制表示值。让节点发送包含自己内部路由表情况的数据包，通过Chipcon Packet Sniffer^[9]抓包并进行分析。

    （1）对存储和计算资源的占用
    图8对比了运行LWRP和LOAD协议后各节点路由表项数目。

    假设网络规模为n，Sink单跳范围内节点个数为m，反馈控制节点占总节点数比例k%，每条路由表占用存储资源为s。由于Sink周围节点路由表条数比其他节点多，用Sink单跳范围内节点路由表占用内存的平均值来衡量协议对存储资源的要求。
    运行LOAD后该平均值为：
     s*[1+(n-m-1)/m]
    而运行LWRP后，该值为:
     s*[1+nk%/m]
    在一般数据采集应用中，n>>m，而k%很小，LWRP路由表占用存储资源优势很明显。
    计算资源方面，LWRP只进行简单比较和线性查找运算，其优选函数以2的非负指数次方作为加权系数，能够利用MCU的移位运算快速得到结果。
    （2）自愈性
    图7显示拓扑条件下，F点向Sink发送数据。某时刻将B节点断电模拟实际环境中节点死亡，从实验结果观察G点流量。结果显示A点检测到AB之间链路断开，缓存了来自F的数据包，开始本地修复过程。
    运行LOAD协议时，A节点的本地修复失败，造成数据包丢失。而运行LWRP时，上游节点D参与寻找路由过程，将来自A的RREQ又广播了一次，成功完成本地修复过程，缓存的数据包通过A->D->G->Sink到达目的地。
    （3）网络带宽占用
    在更大规模网络中通过将节点断电模拟实际环境中节点失效，抓包分析不同路由协议广播包数量得出结论，相比AODVjr和LOAD，LWRP能够有效控制RREQ广播包数量，网络规模越大，优势越明显。
    表1给出了LWRP和其他基于AODV的同类路由协议的对比。

    LWRP已经在实际生产中长期稳定运行，协议在硬件资源占用、节能、无线带宽控制、网络自愈性等方面体现出优越性。下一个目标是解决Sink周围数据流密集可能造成的拥塞，将负载均衡作为路由设计中一项因素加以考虑。
参考文献
[1]  RFC3561, PERKINS C. Ad hoc On-Demand Distance Vector(AODV) Routing [S].2003.
[2]  GOMEZ C. Adapting AODV for IEEE 802.15.4 mesh sensor networks: Theoretical discussion and performance evaluation in a real environment. Proceedings of the 2006 International Symposium on a World of Wireless, Mobile and Multimedia Networks,2006.
[3]  ZigBee document 053474r07. Version 1.1,ZigBee Specification[S], 2005.
[4]  CHAKERES I, Klein-Berndt L. AODVjr, AODV Simplified[J]. Mobile Computing and Communications Review,2002,6(3):100-101.
[5]  6LowPan document．http://www.ietf.org
[6]  IETF Internet Draft, 6LoWPAN Ad Hoc On-Demand Distance Vector Routing (LOAD) [S].2006.
[7]  孙利民,李建中，陈渝，等. 无线传感器网络[M]. 北京：清华大学出版社，2005.
[8]  IEEE Std 802.15.4. IEEE standard for wireless Medium Access Control(MAC) and Physical Layer(PHY) specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs)[S]. 2003.
[9]  Chipcon Sniffer User Manual. http://www.chipcon.com.