短波令牌环协议组网算法的改善＊

（武汉船舶通信研究所 武汉 430205）

1 引言

随着信息时代的飞速发展，短波组网通信的研究与应用越来越重要。我们知道短波具有电离层反射的传输特性［2］，因此短波通信可以不使用任何中继器就能在超视距的范围内通信，这是其它任何频段都无法做到的。当前就国内外短波通信发展来看，国内的院校及科研院所均在开展短波通信组网的研发工作，希望实现短波通信向着网络通信一体化的方向发展，通过使用发展成熟的TCP／IP协议族构建短波IP 网络，采用IP 协议将其与地面InterNet网络及卫星网络统一起来，组成信道多元化的联合高频广域网。例如，美军在短波无线通信网络中，引入NATO（北约组织）的STANAG 5066［3］标准实现海军舰对舰及舰对空的电子邮件的传输。

STANAG 5066 标准定义了一个典型的短波IP网络，实现了OSI七层模型中的物理层、数据链路层及部分网络功能。STANAG 5066 标准对HFCSMA、HFTDMA 和HFTRP［4］协议分别进行了阐述。但是由于CSMA 对带宽资源利用率不高，这样，CSMA 在带宽资源本来就有限的短波组网通信中的应用受到极大限制。同时因为在短波无线通信中，时间同步存在很大问题，TDMA 也不太适合短波通信［5］，目前STANAG 5066标准还没有实现HFTDMA 协议。而短波令牌环是无竞争的组网协议，频带利用率高，提供QoS［6］。然而由于短波信道的特性，令牌环的组网和维护仍然是令牌环协议的关键问题［7］。本文将着重讨论令牌环协议的组网算法问题。

2 短波令牌环协议

1）协议概述

短波令牌环属于无竞争模式MAC 层组网协议，通过建立逻辑令牌环实现对短波信道资源的使用和管理。令牌环上每个节点都知道自己的前驱节点和后继节点，当节点收到前驱节点的令牌后，开始在规定的时间内发送数据，然后再将令牌传递给它的后继节点。如果节点发送数据的时间超出规定的时间长度，则被迫终止发送数据，而将令牌传向其后继节点。依次类推，同一令牌环上的节点按照接收令牌的次序，轮流使用同一个短波信道［8～9］。一旦逻辑令牌环建立起来，环上节点在规定的令牌持有时间内按照令牌传递的顺序发送数据。令牌环上每个节点享有同等带宽和发送权，不存在竞争和冲突，同时降低了节点接入的等待时延，提高了信道利用率。

2）令牌环组网流程

短波令牌环是自组织的，当一个节点激活后，会在某个指定的频率上监听一段时间（定时器A），这段时间它不会有任何动作，除非它收到其它节点的邀请入环令牌（Solicit successor token，SLS），此时它会发送设置后继令牌（Set successor token，SET）进行响应，或者监听到有激活的令牌环存在（即收到了一个从激活令牌环发出的令牌或者数据），节点会重新启动定时器等待SLS令牌。当定时器A 超时时，它还没有监听到任何信息，节点会声明自己为环主，向外广播SLS令牌，其他节点收到SLS令牌后，可发送SET 令牌进行响应。有限的初始情况包含两个均在SFR（selfring，自愈环）状态的节点，没有一个激活的环。通常情况下，每个节点都会产生SLS 令牌，然后进入SEK（seeking，搜索）状态。然而，它们的发送是异步和随机的，因为它们的启动的时刻是随机的。可以假定，一个节点首先监听到了其它节点的发送，进入了JON（join，加入）状态。当入网节点通过发送SET令牌响应SLS令牌，并且也接收到了有权发送令牌（RTT，right to transmit）后，两个节点的环就创建了。具体组网流程如图1、图2所示。

图1 A、B节点组网过程

图2 C、D 节点入网过程

组网过程中可能会产生冲突，从而影响组网的效率。如图1中，当A 节点发出SLS 令牌后，B、C、D可能同时响应，发送SET 令牌，这时候B、C、D发出的令牌产生冲突，A 本次邀请入环流程失败。显然冲突的次数越多，组网的效率就会越低。所以要提高组网的效率，关键是降低冲突发生的概率［10］。

3 短波令牌环组网算法分析及改进

1）现有令牌环组网算法

当前令牌环组网算法的响应机制采取的是随机退避策略。当一个节点监听到其他节点的SLS令牌，它会先进入到SRP（solicit reply，随机响应退避）状态，以减少有多个节点同时对其进行响应而产生冲突的情况。节点在SRP 等待的时间是随机的（0～3个时隙），一旦这段时间内监听到有其他节点发出SET 令牌，自己就放弃本次加入的机会，退回游离状态（FLT）继续监听，等待下一次的加入机会。当节点加入失败的次数超过三次，则下一次等待的时间往后延长三个时隙，依次类推，可将冲突的概率逐渐降低，最终使所有节点都能加入。

（1）主动邀请节点处理流程

主动邀请节点的处理流程如图3所示。

图3 主动邀请节点状态转移图

状态转移图说明：

①节点在SFR 状态状态开启TSLS 定时器。在定时器时间内监听到其他节点的SLS 令牌，进入SRP状态；监听到有激活的环存在（收到非SLS令牌），进入FLT 状态等待被邀请；否则定时器超时的时候，发送SLS令牌邀请其他节点加入令牌环网，进入SEK 状态，等待响应。

②节点在SEK 状态开启TSLW 定时器。在定时器时间内收到SET 令牌，则发送RTT 令牌给新加入节点，进入PAR（paring，匹配）状态，等待确认信息；如果监听到有其他激活的环存在（收到SLS和SET 以外的令牌），进入FLT 状态等待被邀请；否则在定时器超时后回到SFR 状态。

③节点在PAR 状态开启TPST 定时器。在定时器范围内收到新加入节点的确认信息，则表示本次邀请成功；否则表示邀请失败，回到FLT 状态。

（2）新加入节点处理流程

新加入节点的处理流程如图4所示。

图4 新加入节点状态转移图

状态转移图说明：

①节点在FLT 状态开启TCLT 定时器。FLT状态监听到有激活的环存在（收到非SLS 令牌），重启定时器，保持在FLT 状态；监听到SLS令牌，进入SRP状态等待加入令牌；否则在定时器超时后进入SFR 状态。

②节点在SRP状态开启TSRP定时器。如果在定时器时间内监听到其他节点发送的SET 令牌，则取消本次加入，进入FLT 状态，加入失败次数加1；否则在退避时间超时后发送SET 令牌，进入JON 状态。

③节点在JON 状态开启TCON 定时器。如果定时器内收到了邀请节点发送给自己的RTT 令牌，则表示入环成功，回复确认信息；否则，定时器超时仍未收到RTT 令牌，则表示本次加入失败，回到FLT 状态，等待下次加入。

2）现有算法分析

现有加入策略可以实现令牌环组网的功能，而且在节点激活间隔时间较大的时候，效率比较高。但是当节点较多且所有节点激活间隔时间比较小（极端情况是同时激活），因为随机时隙个数少，冲突比较大，令牌环组网的效率就会大大降低。本文将针对这一情况，对令牌环组网的响应加入算法进行改善，使得令牌环协议在节点较多、激活间隔时间较小的情况下也能有比较好的性能。

3）改进算法的思路

现有组网算法主要是由于随机退避的时隙个数比较小，所以我们的思路是利用令牌中携带的信息，动态规划时隙个数。由于在我们的应用场景中，最大规划节点数是已知的，而且令牌中携带有当前环内节点数，所以把时隙个数修改为如下：

时隙个数＝最大规划节点数-当前环内节点数

这样在节点数较多，开机时间间隔较小的时候（即使是同时开机），因为时隙个数的增多，冲突的概率就减小了很多，理想情况是每个节点都能分到一个唯一的时隙，这种情况下是没有冲突的。同时也随着节点不断的加入环，时隙个数也跟着减小，后续加入节点的退避等待时间也不会因此增加很多，冲突的概率仍旧比较小。

4 仿真结果

1）仿真参数

（1）Turnaround time 1．04s；

（2）信道为全连通；

（3）仿真平台为EXATA 仿真软件。

2）仿真结果

在仿真的时候，针对最大规划节点数分别为4、6、8、12、16的情况进行了仿真，节点激活的最大时间间隔由0逐步增大到（4＊最大规划节点数）s，每个节点激活的时机是随机的。仿真结果见表1和表2。

（1）现有算法组网时间仿真结果

表1 现有算法组网时间仿真结果（s）

2）算法改进后组网时间仿真结果（s）

表2 算法改进后组网时间仿真结果（s）

5 结语

本文针对现有令牌环组网算法进行了分析，针对现有算法在节点较多且激活间隔时间较短的时候组网效率较差的情况进行了改善，提出了动态规划时隙的算法，并对改进后的算法进行了仿真。依据仿真结果可知，与理论分析的结果基本相符，改善后的算法在总体上比现有算法的组网效率要高，而且在间隔时间逐步变大的过程中组网时间也比较平稳。特别是节点数大于8时，组网效率有较大的改善。在实际环境的测试时，针对4个节点进行了测试（由于设备及其他条件有限，只能对4个点进行测试），改善后的组网算法时间大概是60s～80s之间，与仿真结果基本吻合，因此该算法可用于实践。

［1］Johnson E E，Tang Z，Balakrishnan M，et al．Robust token management for unreliable networks［C］／／Military Communications Conference，IEEE，2003，1：399-404．

［2］McGhee J，Grimble M J，Mowforth P．HF radio sys-tems and techniques［J］．IEEE REVIEW，1992：195．

［3］NATO Standardization Agreement 5066：Profile for High Frequency（HF）Radio Data Communications，version 1．2［S］，NATO Standardization Activity reference 0114-C3．

［4］NATO Standardization Agreement 5066，Profile for High Frequency（HF）Radio Data Communications Version 1．2［S］，Annex L-High-Frequency Wireless Token Ring Protocol（HFTP）Requirements，Edition 2，Draft 1，NATO C3Agency，June 2004．

［5］Hong Y K，Miller，D．Performance of CSMA and TDMA protocols for break-in channel access in a frequency hopping（FH）narrowband high frequency（HF）blocked channel environment［C］／／Military Communications Conference IEEE，1993，3：763-767．

［6］E．E．Johnson，M．Balakrishnan，Z．Tang．Impact of Turnaround Time on Wireless MAC Protocols［C］／／Proceedings of MILCOM 2003，Boston，MA，2003，1：375-381．

［7］Johnson，E．E．，Tang，Z．，Balakrishnan，M．Token relay with optimistic joining［C］／／Military Communications Conference，2005．IEEE，2005：2216-2222．

［8］Ergen M，Lee D，Sengupta R，et al．WTRP-wireless token ring protocol［J］．Vehicular Technology，IEEE Transactions on，2004，53（6）：1863-1881．

［9］Xianpu S，Yanling Z，Jiaodong L．Wireless dynamic token protocol for MANET［C］／／Parallel Processing Workshops，2007．ICPPW 2007．International Conference on．IEEE，2007：5．

［10］Balakrishnan M，Johnson E E．Queueing analysis of DCHF and token-passing protocols with varying turnaround time［C］／／Performance，Computing，and Communications，2004 Internationl Conference on．IEEE，2004：315-316．