摘  要： 针对无线Ad Hoc网络系统的需求，基于VxWorks操作系统，设计并实现了一种基于多信道的邻居管理协议，用于实现邻居的发现、删除以及全网节点的连通性维护。测试结果表明，该协议能确保网络节点之间高效可靠地完成邻居管理功能。 

    关键词： 无线Ad Hoc； 多信道； 邻居管理； 连通表

    在无线Ad Hoc网络中，邻居管理^[1]是网络正常工作的基础。唯有通过与邻居节点的信息交互，无线自组网才能通过路由控制消息的交换建立正确的路由，从而在网络中实现多跳通信。现有的邻居管理协议大多作为其他协议的子模块为主协议提供支持，如典型的DSDV（Destination-Sequenced Distance-Vector）路由协议^[2]，通过周期性地交换HELLO消息检测邻居节点。除了基于定时消息的邻居管理协议之外，事件驱动的邻居管理协议是另一类分支^[3]，其主要特点为：(1)仅在需要维护更新拓扑信息时才发送HELLO消息；(2)使用序列号检测邻居信息的新旧程度与拓扑的变化状态。在上述协议中，由于每个节点都需要实时维护邻居信息，这样在拓扑变化较快的环境中，大量的拓扑更新消息会占用过多的信道资源，使得系统效率下降。比较方便的解决方法是：采用基于多信道的方式，使用多个信道即可在物理上增加信道带宽，又能降低节点冲突的机会，显著提高了网络性能。针对某特定环境对无线Ad Hoc网络的需要，本文设计并实现了一种基于多信道的邻居管理协议。 

1 基于多信道的NM协议功能需求 

    传统的无线自组网吞吐量不高，尤其随着网络规模的增大，节点吞吐量下降。近年来通过在MAC层使用多个信道，无线自组网的吞吐量得到显著提高^[4]。本文研究的无线Ad Hoc网络，针对某特定应用环境的需要，采用TDMA的信道接入机制，节点分为物理层、链路层、网络层。由于网络规模比较小（节点数不超过12），采用固定信道分配方式，每个节点分配固定的控制信道和业务信道，使控制报文和数据报文相分离，这使得在TDMA模式下，帧的发送具有无冲突、周期性、固定帧长等特点。虽然链路层并不关心邻居信息，但是由于链路层可以比网络层更有效地侦测到邻居信息，能减少网络层的路由开销，提高信道利用率。基于上述特点，使得在链路层完成NM功能极具优势。本文针对无线Ad Hoc网络的功能需求，在VxWorks嵌入式系统下设计并实现了一种基于多信道的邻居管理NM(Neighbor Management)协议。该协议针对网络初始化的邻居发现和全网的链路维护两个场景。在邻居发现阶段，采用时间驱动方式，定时与邻居节点交换HELLO消息，查询邻居链路的双向连通，检测邻居链路的变化;在全网链路维护阶段，采用事件驱动方式，泛洪邻居变化信息，建立和维护全网活动节点的拓扑分布（连通表）。 

2 NM协议的设计与实现 

2.1 邻居管理操作 

    基于多信道的NM机制，采用TDMA的方式，将信道划分为M个控制信道和多个业务信道，每个节点分配固定的控制信道，节点在控制信道公告NM信息分组，同时监听邻居节点的公告信息。 

    为了不影响节点的正常信道接入，每个节点建立一个帧号，帧号取16位（0～65 535）,在达到最大值时从0开始循环取值。控制信道每发送一个时帧，帧号就增1，并把该帧号添加到链路分组中，刚入网的节点收到邻居节点的链路分组，修改本地帧号使之与邻居节点一致，从而达到全网节点在同一时间帧号一致。对于HELLO信息的公告，全网节点在帧号范围(1 024×n～1 024×n＋10)发送，避免了在控制信道的HELLO信息与其他控制报文的冲突，并使节点在统一时间段内进行HELLO消息广播，缩短了邻居发现时间。另外，公告邻居变化表时，如果节点有控制报文等待发送，节点将其缓冲，等待公告发送结束后，再继续发送。由于只有邻居发现和删除时才广播邻居变化表，占用控制信道时间比较少，所以造成的控制报文延迟很小。 

    HELLO消息的格式为ID号、邻居数、邻居列表。邻居列表是一个动态的一维数组，列出了它最近检测到的与它单向连通的邻居节点的ID号。邻居变化表的格式为源节点ID号、节点ID号、链路状态和序列号SEQ。链路状态‘1’表示连通，‘0’表示不连通。为了重复分组检测，每个节点维护一个序列号SEQ，节点每次发送一个邻居变化分组其维护的SEQ单调增1，其他节点收到一个信息分组依靠序列号和源节点ID号来判断自己是否转发过该分组。 

    每个节点维护一个连通表，表示全网节点链路的双向连通性，用矩阵A[i][j]表示。 

其中，i、j表示节点的ID号，构成矩阵的行和列，行数和列数等于网内活动节点数，对应的元素表示双向连通状态。 

    基于多信道的邻居管理的操作主要分为以下三步： 

    (1) 初始连通表的建立 

    连通表的初始值为全零，当节点入网成功后，以请求的方式从邻居节点得到全网最新的连通表，建立初始连通表。当节点第一个开始组网时，连通表为初始值全零。 

    (2) 邻居发现和删除 

    节点通过帧号的范围，周期性地广播HELLO消息，同时监听邻居节点的HELLO信息，图1是一个邻居发现的例子。假设两个节点A与B分别处于不同的控制信道Ta和Tb。首先节点A在Ta上公告的HELLO消息被B接收，B将A的ID号添加到其维护的邻居列表NLb中，同时在信道Tb上公告HELLO消息（NLb），A收到公告后，将B的ID号添加到NLa中，同时查看NLb，发现B已经接收到之前A所发出的公告，A认定两者是邻居关系。在下一次公告时，B收到A的公告信息，同样也可以判断与A为邻居关系。通过这种握手机制完成了相互发现过程。容易推导，节点在前两次公告后即可实现相互发现过程。 

    实现邻居发现后，节点通过链路监测机制，当在一连续时间段内没有收到邻居节点的HELLO消息时，表示链路断开，则从邻居列表中将邻居节点ID号删除。 

    (3) 泛洪邻居变化信息 

    节点通过邻居的发现与删除机制，修改连通表，并全网广播邻居变化信息，使全网节点的连通表达到同步。节点收到邻居变化信息分组后，查看分组中的源节点ID号和SEQ，判断是否有该ID和SEQ的记录，如果没有则更新连通表，转发该分组，否则丢弃。 

2.2 实现方案 

    在本系统中，链路层设计采用“底层驱动软件＋嵌入式实时多任务操作系统＋协议栈”的设计结构，主要完成TDMA信道接入协议与NM协议的设计，本文主要实现NM协议。链路层总体软件结构如图2所示。硬件平台采用S3C2510的32位网络处理器和相应的外设构成硬件平台，RTOS采用VxWorks，使用I/O口进行NM数据分组的收发，使用串口将连通表发送给网络层。 

　　VxWorks操作系统是一种嵌入式实时操作系统(RTOS)，是嵌入式开发环境的主要组成部分，具有可靠性高、实时性强、可裁减等特点。VxWorks为程序员提供了高效的实时任务调度、中断管理、实时的系统资源以及任务间通信。 

基于NM的功能需求和VxWorks操作系统的实时性，遵循H.Gomma原则[5]，将系统划分为六个任务，如图3所示。 

    图3中，每一个虚线框图对应一个独立的任务，并建立邻居列表和连通表两个全局变量。其设计思想如下： 

    (1) 首先从接收任务I/O口中检测到链路数据，取出其中的NM消息包，通过消息队列Msg发送到数据处理任务。 

    (2) 数据处理任务对不同的NM信息进行不同的处理。首先通过邻居连通表的接收，建立初始的连通表。通过HELLO消息包实现邻居的发现，维护邻居列表和连通表；通过邻居变化信息包来判断两跳范围外的节点链路变化情况，若第一次收到，则修改连通表，转发邻居变化信息。  

    (3) 链路检测任务通过taskdelay（int ticks）函数，每30s查看邻居HELLO消息的接收情况，监测邻居链路的变化，若在连续30s内没有收到邻居节点的HELLO消息，则在邻居列表中删除邻居ID号，修改连通表，泛洪邻居变化信息。 

    (4) 数据处理任务产生二进制信号量Sem1和Sem2，分别触发I/O口发送任务和串口发送任务，完成任务的同步，泛洪邻居变化信息和发送连通表到网络层。 

    (5) 通过硬件定时器，设定时帧的帧号，在帧号为(1 024×n~1 024×n+10)范围内广播HELLO消息。 

3 功能测试 

    NM协议模块位于无线Ad Hoc网络系统体系结构框架内，现有的网络节点已研制成功，本文在真实的网络节点上对NM模块功能进行设计开发和测试，如图4所示为测试环境。 

    在该测试场景中，节点1(ID号为1)开始组网，节点2（ID号为2）通过节点1接入网络中，节点3(ID号为3)通过节点2接入网络中，节点1与节点2互为邻居，节点2与节点3互为邻居。测试的目的是检验NM的功能，PC机与链路控制器中的VxWorks平台通过控制台串口相连，用于观测节点NM数据包的收发和处理，通过超级终端从节点1抓包如图5：节点1周期性地发送HELLO数据(-1-0-0-0)，当第一次检测到节点2的HELLO消息包(-2-1-0-0)时，在邻居列表中添邻居ID号(-1-2-0-0)，并更新连通表，泛洪邻居变化信息(-1-2-1-1)。节点1第一次收到节点2发送的邻居变化信息(-2-3-1-1)后，发现节点2和节点3为邻居，修改连通表，并转发该邻居变化信息包(-2-3-1-1)时，对于再次收到同样的邻居变化信息包（判断SEQ，仍为1）时，不作处理。 

    根据NM的功能测试结果可以看出：此方案能提供实时、充分的邻居节点信息，建立全网统一的连通表，有助于提高上层应用的性能。 

    本文针对某工作于特定环境的无线Ad Hoc网络的需要，在链路层设计了一种基于多信道的邻居管理协议，该协议不仅能准确地掌握邻居节点信息，还能维护全网节点统一的连通表，有效地服务于网络层，并在VxWorks操作系统下对该协议进行了设计，功能测试结果表明，该协议稳定、可靠、准确。本文提出的邻居管理协议适用于网络规模较小的无线Ad Hoc网络。 

参考文献 

[1] 郑少仁,王海涛,赵志峰,等. Ad Hoc网络技术. 北京：人民邮电出版社, 2005. 

[2] PERKINS C E, BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. In: Proceedings of SIGCOMM 4. NEW York:ACM Press, 1994:234-244. 

[3] MOSKO M, GARCIA-LUNA-ACEVES. A self-correcting neighbor protocol for mobile Ad Hoc wireless networks.Proc. IEEE ICCCN′02, 2002：556-560. 

[4] KYASANUR P, VAIDYA N H. Capacity of multi-channel   wireless networks: impact of number of channels and interfaces. ACM MOBICOM'O5, Cologne,Germanv:43- 57. 

[5] 风河公司. VxWorks开发人员指南丛书VxWorks程序员指南. 北京：清华大学出版社, 2003