多移动微机器人的实时无线通信机制研究

毛玲，李振波，陈佳品

(1. 上海电力学院 电气工程学院， 上海 200090;2. 上海交通大学 电子与电气工程学院，上海 200240)

0 引 言

对于多移动微机器人应用系统而言，机器人之间的通信是必要的,通常微机器人通信采用的是RF方式。考虑到微机器人需实时地进行数据交换以便机器人之间合作快速完成任务，这意味着其个体之间的数据传输是有时间限制的，因此RF通信协议必须保证数据传输的实时性[1]。而且，因为移动微机器人RF网络的特点，RF通信协议需支持节点的移动性及多跳通信能力。然而，目前典型的Ad-Hoc网络协议重点放在解决最大吞吐量、最小时间延迟等问题上，而且大多数底层的商用网络协议(如802.11、802.15.4等)因数据包冲突、随机后退、错误包阻塞等问题而不能保证数据包在网络中的实时传输。Lee等基于802.4的令牌环总线机制设计了WTRP协议[2]，当网络中的某节点接收到了令牌，在一定时间内它可以发送数据，并把令牌发送给它的前驱。然而，该协议不支持多跳通信，节点只能跟它的前驱或者后驱通信。Donatiello 和Furini[3]提出一个相似令牌传递机制，节点组成一个环，谁持有令牌谁有权发送数据，如果一定时间内，发送失败，就把令牌传给下个节点，但是令牌只能朝着一个方向传递，需要网络环一直保持连接，这限制了节点的移动性。Facchinetti[4]等用隐含的EDF机制保障了数据传输的实时性，然而该通信机制不支持多跳通信。802.15.4的无线通信方式保证了数据发送的安全性和多跳通信，但它允许任意推迟数据传输的时间，故不能实现数据的实时通信。通过以上文献调研可知，即使存在无线通信协议支持无线数据传输的实时性，但大多数不支持多跳通信。

本文在实时以太网协议(Real Time Ethernet Protocol,RT-EP)基础上，设计了实时微机器人通信机制(Real Time Micro Robot Communication Protocol，RT-MRCP)，其使用令牌(消息优先权)传送机制及时间槽通信机制来保证微机器人之间数据传输的实时性，该协议可以满足多移动微机器人这种小规模无线网络通信的应用场景，网络中的节点数最多可达15个。

1 多微机器人的实时无线通信协议的设计

在设计的RT-MRCP协议中，每个节点都有一个发送消息队列和一个接收消息队列。消息队列应用程序可将消息优先级设置成0～127之间的任何值，其中127是最高优先级。具有同一优先级的消息根据先入先出(FIFO)规则放置在队列中。当节点欲把消息发送给另一个节点时，把消息压进发送队列。RT-MRCP协议根据需要,处理从发送队列中弹出的消息，并通过网络把它发送到目的节点。接收节点把消息压进接收消息队列，根据应用所需弹出队列中的消息。

为了描述网络拓扑结构，RT-MRCP定义了一个网络连接图。网络连接图中边的值是两个节点之间无线射频信号质量的函数，即两节点间的链路质量。其值表示成矩阵的格式即(Link Quality Matrix, LQM)，矩阵中的元素lqmij∈[0, max_lq]描述了节点Pi和Pj之间的链路质量，其中max_lq为网络中节点数，如图1所示。LQM的每一列LQMk表示节点和它邻居链路质量。节点利用LQM选择哪个节点传输令牌，并利用LQM决定源节点到目的节点的路径。所有节点的lqmij都是LQM一个局部复制，当帧到达时，每个节点负责更新相应的列，并告知其他节点局部拓扑的改变。

图1 网络图及相应的LQM及协议跳数的顺序数

帧的结构如图2所示。所有类型的帧有同样的帧头，不同类型的帧其余部分不同。RT-MRCP帧描述成一系列指定的顺序域，帧的传输按从左到右的顺序，最先传输最左边位。

图2 帧的结构

帧结构具体分为：

1)header(帧头)

(1)serial：帧的序列号域，2个字节的长度，用在错误恢复机制中。

(2)type：帧的类型域，1字节的长度分别定义了“token”、“authorization”和“message或drop”几种类型的帧。

(3)src：源地址域，长度为1字节，指定了帧发起方的地址。

(4)dst：帧的目的地址域，长度为1字节，指定了帧接收方的地址。

事实上，RT-MRCP协议中，节点能够被0～n-1地址识别，此地址称为RT-MRCP地址。当节点欲发送数据时，填充src和dst域。因为无线信道共享，所有邻居节点都会受到监听，但是仅有目的节点对其进行处理。

2)token(令牌帧)

(1)max_pri：最高优先级数，长度为1字节，指定了MPM的优先等级

(2)max_pri_id：最高优先级数消息持有者的ID，长度为1字节，指定了MPM持有者的ID。

(3)age：年龄域，长度为2字节，用来找到具有同优先级消息中最老的一个。

(4)lack：延迟确认域，长度为1字节，发送者的延迟确认域。

(5)nstat：节点的状态域。是n个字节的数组，nstat[i]代表节点Pi的状态为“reached”，“unreached“，“lost”，“search”，即“到达”、“没有到达”、“丢失”、“搜索”。

(6)LQM:链路质量矩阵域，n2-n个字节，代表链路质量矩阵。

3)authorization(授权帧)

authorization帧增加了aut_src域和aut_dst域。

(1)aut_src域：令牌持有者的源地址域，长度为1字节，指定了令牌持有者的源地址。

(2)aut_dst域：令牌持有者的目的地址域，长度为1字节，指定了令牌持有者的目的地址。

4)message(消息帧)

(1)priority域：消息帧优先级数，长度为1字节，指定了消息的优先级。

(2)msg_src域：消息源地址域，长度为1字节，指定了消息的源地址。

(3)msg_dst域：消息目的地址域，长度为1字节，指定了消息的目的地址。

(4)len:消息的长度域，长度为2字节，指定了消息的长度。

(5)data:帧的净载荷域，帧净载荷域的长度可变，长度为0-MTU字节, MTU为帧净载荷的最大长度。

通信协议RT-MRCP假设所有节点知道网络拓扑(即所有的节点有同样的LQM)且网络是连通的，其包含的三个阶段具体地如下所述：

(1)优先权仲裁阶段(Priority arbitration phase, PAP)：当一个节点Pk初始化了PAP，它创建了一个新的令牌帧，填充它的局部LQM到令牌帧的相关域，设nstat[i]为“unreached“∀i∈[0,n-1]:i≠k。设置nstat[k]为“reached”。这就意味着在当前的PAP阶段，令牌只到达了节点Pk还没有到达其他的节点。节点Pk核对它发送队列里具有最高优先级消息的优先级，然后用此优先级的值和它的RT-MRCP地址分别设置max_pri和max_pri_id域。用消息age域的值设置令牌的age域(消息在队列中等待的时间单位为milliseconds)。用这种方式节点Pk声明它是MPM的持有者。节点Pk通过分析LQM，它知道哪个邻居节点Pbl有最好的链路质量并发送令牌给它。当节点Pbl收到此令牌，它设置nstat[bl]状态为“reached”，然后用它局部的LQM更新令牌的LQM域，并保存它。然后它查找令牌的max_pri域并与它发送消息队列的最高优先级比较，如果它有更高的优先级消息，则调整max_pri和max_pri_id域。如果优先级相同，它核对age域，如果持有的消息更老，它更新此令牌。然后，它选择一个具有最好链路质量且令牌没有到达的节点，发送令牌给此节点。如果它只监听到了前驱(发送令牌给它的节点)，它归还令牌给它的前驱。这意味着在同一个PAP阶段，节点可能接收到令牌数次。这个过程一直被重复直到令牌到达过所有节点即nstat[i]=reached∀i。令牌到达的最后一个节点，其知道谁是MPM的持有者，并且负责发送“authorization(授权)”给MPM持有者。

(3)消息传递阶段(Message transmission phase, MTP)：当MPM的持有者接收到了“authorization”消息后，从消息队列中取出最高优先级的消息并创建“message”消息，设置data域并填充msg_src和msg_dst，然后发送消息给这路径的第一个节点。当第一个节点接收到这个消息，它核对msg_dst域，如果是自己则停止MTP，并开始ATP。否则，它把消息发送给路径中它的下一个节点，重复这个过程，直到消息到达目的节点。如果消息到达了目的节点，在初始化PAP之前，目的节点用它的RT-MRCP地址填充新令牌的lack域，此令牌能够到达前面消息的发送者，它能够通过查找lack域知道消息是否发送成功。

每个机器人节点通过传送封装局部LQM的帧了解频繁变动的RF网络拓扑结构。每个节点通过填充其LQM矩阵的相应列，从而可容易获得实时的RF网络拓扑信息。事实上，当节点发送数据帧时，由于采用无线广播的方式，它的邻居节点都能够监听到，每个节点收到后，自动更新其自己LQM，然后将其转发给其他邻居节点。因为LQM被频繁地传输到每个节点，故节点都能及时地更新网络的拓扑信息。

2 通信协议的协议的实时特性

RT-MRCP协议之所以能够保证数据传输的实时性，因为协议的每一阶段持续的时间有界且已知。如果网络是连通的，保持网络图连通的最少的边数为n-1，其中n为图中顶点数，所以在PAP阶段最糟糕的情况应该是2n-3跳，如图3所示。此外，如果发生错误例如节点失败、节点重新插入或者丢失，此阶段有同样的持续时间，因为传输失败的令牌所花费的时间与需要发送和返回一个令牌所花费的时间一致。例如，假设节点Pk是节点Pa仅有的邻居，如果协议正常运作，节点Pk发送令牌给节点Pa，为了继续PAP，节点Pa返回令牌给Pk，节点Pk继续PAP。如果节点Pa发送令牌以后，出现异常，节点Pk将等待一段时间(timeout)，传递令牌给另一个节点，继续PAP。实际上，上述两种情况所花费的时间相同，因为节点Pa需要返回令牌的时间与Pk等待的时间(timeout)相等。

图3 PAP阶段最糟糕的情况

在ATP和MTP阶段，路径由Dijkstra’s Algorithm决定[5]。根据此算法，如果网络连通，从源节点到目的节点最大的跳数是n-1，n是图中总顶点数。因此每个阶段都有一个有界的持续时间。然后在节点失败或者丢失的情况下，为了不妨碍网络的正常运行节点将舍弃authorization和message的发送。例如，假设节点Pk计算一条到目的节点Pd由n-1个节点组成的路径，如果沿着此路径的第一跳就失败了，例如Pk传递给了Pb，Pb失败或者丢失，Pk将寻找另一条到Pd路径。但是，路径总的跳数可能大于允许的最大跳数n-1，所以为了不妨碍网络的正常运行，节点将舍弃传递authorization和message消息。

图4 RT-MRCP协议每个阶段的跳数

通信协议RT-MRCP的连续地重复着每一阶段，如图4所示。最糟糕的情况下，PAP持续时间为tpa= (2n-3)tt，ATP持续时间为tat= (n-1)ta，MTP持续时间为tmt= (n-1)tm。tt是token消息传递的最大持续时间，ta是authorization消息传递的最大持续时间，tm是message消息传递的最大持续时间。tt、ta、tm值取决于协议的参数例如节点数量、数据速率、最大发送单元的长度和802.15.4协议。802.15.4的操作细节不是本文讨论的重点。无论怎样，802.15.4帧的发送速率是250 kbps。一个节点在发送之前总是等一段时间，大概是120 μs。与网络速率无关，802.15.4帧的一部分(preadble and header)总是要以250 kbps的速度发送大概是986 μs。帧发送的持续时间如下：

(1)

L是扩展的802.15.4帧的负载包括整个帧头(令牌帧L=11+n2，authorization帧:L=8,message帧：L=11+MTU)，tx_rate为帧的发送速率，在最糟糕的情况下，令牌消息到达每个节点的间隔为：ttoken= 2ta+tat+tmt。具有最高优先权的消息在最糟糕的情况下，遭受的延迟为twc=2(tpa+tat+tmt)。

3 试验

为了验证通信协议RT-MRCP的性能，试验中用四个装备 IEEE802.15.4设备的微机器人做了如下试验[6]。

图5 协议的优先级行为

第一个试验的目的是验证RT-MRCP协议基于优先级的消息交换机制。在由四个节点组成的网络中，所有的节点都产生饱和交通的情形。每个节点都有一个包含20条消息的发送消息队列。发送消息队列应用程序可将消息的消息优先级设置成1～20之间的任何值，目标是测量不同优先级消息遭受的延迟，结果如图5所示。从图5可知，消息的优先级越高所遭受的的消息延迟越少，换句话说消息延迟与消息优先级成反比。

第二个试验目的是验证通信协议RT-MRCP端到端的吞吐率。做了两种情况下的试验，一种是在最好的情况下，另一种是在最糟糕的情况下。在最好的情况下，分别创建两个、三个和四个节点完全连通的网络。在PAP阶段，总是持续n-1跳，ATP阶段和MTP都是一跳。为了确定有效的瞬时带宽，某一节点以一定的速率发送新令牌消息，如果能够收到隐含确认消息，那么就将发送速率提高重新进行测试，直至得出最终的结果。测量的结果如表1所示。

表1 端到端带宽的实验测量结果 kbps

在最糟糕的情况下，分别创建两个、三个和四个节点完全连通的网络。在PAP阶段，总是持续2n-3跳，ATP阶段和MTP都是n-1跳。为了确定有效的瞬时带宽，正如最好的情况所采用的方法，某一节点以一定的速率发送新令牌消息，如果能够收到隐含确认消息，那么就将发送速率提高重新进行测试，直至得出最终的结果。理论上网络节点越多字节数越大带宽应该越小，但从表1可以看出，实测结果和理论上的不同，节点越多字节数越大带宽越大，这是因为协议程序执行时间比较少，瓶颈由额外的UDP/IP层组成。事实上，根据试验的测量数据可知，从产生通信中断到应用层接收到数据的延时大概有0.5 ms～1.5 ms，此延时对较小的数据包影响比较大，对较大的数据包影响比较小。

4 结束语

本文使用令牌传送机制及时间槽通信机制设计了通信协议RT-MRCP，其满足了数据传输的实时性，可以运行在802.15.4基础之上。所设计的RT-MRCP协议通过共享节点间的链路质量矩阵来了解频繁变动的网络拓扑结构。并设计了实时通信RT-MRCP协议的错误处理机制，分析了通信RT-MRCP协议的实时特性，试验证明了通信协议RT-MRCP能满足检测系统对微机器人通信协议实时性的要求即最大消息传输时延小于1 s。所设计的RT-MRCP协议比较适合小规模网络的应用，虽然允许的网络中最大节点数只有15，但是这足以满足多移动微机器人系统应用的需求。