令牌传递顺序表优化研究

曾曦 李迟生 温洋

摘  要： 在短波无线令牌环中，合适的令牌传递顺序表能有效减少令牌中继次数，降低令牌传递时间，提高服务质量（QoS）。传统基于中继的组网方法使一些病状拓扑也能组网成功。但在组网时，若环外节点可与令牌环内令牌传递顺序表中相邻两个节点相互通信，会因为邀请节点的不同导致节点加入后的令牌传递顺序表中需要不必要的中继。文中针对非必要中继传递的令牌传递顺序表采用最近插入法，重组优化令牌传递顺序表，最大化减少令牌中继次数，仿真结果表明该算法能有效解决不必要多次中继问题。

关键词： 令牌传递顺序表; 最近插入法; 中继; 短波令牌环; 服务质量; 多址接入

中图分类号： TN915?34                         文献标识码： A                          文章编号： 1004?373X（2019）15?0001?04

Research on optimization of token passing sequence table

ZENG Xi， LI Chisheng， WEN Yang

（School of Information Engineering， Nanchang University， Nanchang 330031， China）

Abstract： In the short wave wireless token ring， an appropriate token transmit?order?list （TOL） can reduce the number of token relays and token passing time， and improve QoS. The traditional networking method based on token relay can also make some pathological topologies network successfully. However， if the node outside the ring can communicate with the two adjacent nodes in TOL during networking， the unnecessary relay will be needed in token TOL after node is inserted because the invited node is different. The nearest insertion method is used in allusion to the token TOL for the unnecessary relay transmission to regroup and optimize the token TOL， which can reduce the quantity of the token relay. The simulation results show that the algorithm can effectively eliminate unnecessary repeated relay.

Keywords： TOL; recent insertion method; relay; high frequency token ring; service quality; multi?access

0  引  言

近年来，信息技术飞速发展，短波网络通信的研究和应用也越来越重要。短波通信是通过电离层的反射实现远距离通信[1]，由于电离层的高度和密度隨着时间、气候的变化而变化，最终使短波通信出现多径时延、信号衰落和多普勒频移等情况。故在短波网络通信中采用合适的媒体访问控制（Multi?access，MAC）协议来保证较好的服务质量（Quality of Service，QoS）是至关重要的[2]。

基于竞争机制的MAC协议由于竞争和冲突的存在，无法彻底解决隐藏终端和暴露终端[1]的问题，无法提供较好的QoS，也无法保证信道访问的公平性。非竞争MAC协议中无线令牌环协议（Wireless Token Ring Protocol，WTRP）能为时延要求高的业务提供固定QoS保证，其信道利用率在网络规模和流量较大的情况下明显高于竞争型MAC协议，故在一些无线网络中得到广泛应用[3?5]。基于短波通信系统的特点，使令牌的传递周期时间较长，故在令牌传递过程中出现问题需要有机制及时恢复。短波令牌环协议（High Frequency Token Ring Protocol，HFTRP）是在WTRP的基础上加上令牌中继机制，在令牌丢失时采用中继令牌来完成对目的节点令牌的中继传递[6?7]。克服了WTRP在令牌丢失问题上消极被动的缺点，更适合于短波无线通信。

由于短波通信中网络成员所处范围广、相互距离远、节点发射功率有限，导致实际短波通信网络存在部分节点仅能与特定对象通信，网络呈现“病态拓扑”[8]。文献[9]针对该问题采用“请求后继”机制完成节点入网过程。但是这将会引起不必要的中继，从而增加令牌的传输时间。

1  短波令牌环基本原理

1.1  协议概述

短波令牌协议是一种无竞争机制的MAC协议，它通过令牌来控制节点媒介访问的公平性。令牌环在组网后存储一个传递顺序表（Transmit?Order?List，TOL）：如节点A，B，C，D组成令牌环，B是A的后继节点，C是B的后继节点，D是C的后继节点，A是D的后继节点，则TOL为A→B→C→D→A，令牌则按照TOL依次传递。每个节点记录自己的前驱节点和后继节点，当节点接到来自前驱节点RTT令牌，若节点有信息发送则将信息发出，若没有信息发送则直接将RTT令牌传给自己的后继节点。协议同时规定了节点发送信息的最大时间，若节点在最长时间内信息没有发送完，节点被迫将传输权（Right to Transmit，RTT）令牌传出。令牌环内节点按照设定好的TOL传递，轮流使用同一个信道。保证每个节点都享有同等带宽和发送权，避免了竞争和冲突，降低节点接入时延，提高信道利用率。

1.2  中继机制组网过程

传统令牌环组网过程中，要求等待加入的节点要同时在其将要加入环的前驱节点和后继节点的通信范围内。由于在实际短波通信网络中，节点分布范围广，相互距离远，节点的发射功率有限，导致部分节点仅能与特定的几个环内节点通信。若某些节点只能与令牌环中的一个节点通信将无法进入环内。针对这个问题，文献[9]提出基于中继机制的组网方法。该方法中不要求等待加入节点要在其将来的后继节点的通信范围内。在组网成功后，该节点可以通过中继令牌将令牌传输给其后继节点。

以下简介中继机制组网过程。其中节点A与节点C之间不能相互通信，节点B可分别与节点A和节点C相互通信。

节点启动后直接进入浮动状态（Floating State，FLT），开启定时器timer1，并监听信息。若节点启动后一直没有监听到任何信息，则在定时器timer1超时后，节点会申明自己为自环，即只有自己一个节点的环，环路主节点为自己，并进入自环状态（Self Ring State，SRS）。自环节点会发出令牌邀请（Solicit Successor Token，SLS）自己通信范围内的节点入网。在发出SLS令牌后，节点转入寻求状态（Seeking State，SEK）来等待其他节点回复的设置后继节点令牌（Set Successor Token，SET）。当节点收到SET令牌后，从收到的所有SET令牌中随机选取一个节点作为自己的后继节点。节点转入持有令牌状态（Have?Token State，HVT），并将RTT令牌传输给新的后继节点。此时邀请环外节点入环的过程完成。

其他节点处于FLT状态时，在未超时接收到其他信息则不做任何反应，若收到其他节点的SLS令牌，则节点将本节点地址加入到TOL中邀请节点的后继节点位置，设置SET后回复给邀请节点。之后节点转入加入状态（Joining State，JON）等待RTT令牌。若节点收到来自前驱节点的RTT令牌，则说明节点加入令牌环的过程完成。图1为自环邀请新节点加入令牌环。

图1  自环邀请节点过程

当节点收到SLS令牌后，由于可能存在多个等待加入令牌环的节点，节点会选择一个随机的时隙来发送SET，以减少与其他回复SLS令牌节点间的碰撞。

当节点在SFR状态下，发送的SLS令牌中将设置自己的后继节点为将要加入节点的新后继节点。当等待加入节点收到SLS令牌，传统的组网机制会要求等待加入节点检查自己是否在新的后继节点的通信范围内，若在通信范围内才回复SET令牌，若不在则不能加入令牌环。而在基于中继机制的组网情况下，等待加入节点不需检查这项内容，可直接加入令牌环。若入网后，该节点不能直接将RTT令牌传给其后继节点，则可通过中继将令牌传出。如图2所示，节点A与B组网后，节点B邀请节点C加入令牌环时将A设置为C新的后继节点，而A不在C的通信范围内，则在C加入令牌环后，节点C通过给B发中继令牌最终将令牌传给A而完成令牌的传输。

图2  中继机制组网过程

2  问题分析

基于中继的组网方式会引起一些问题。如等待加入的节点与环内顺序列表上相邻的两个以上节点都可以相互通信，这种情况下最优的TOL应该是将等待加入的节点插入到这两个节点之间，但现实中会因为邀请加入的节点不同导致该节点插入到TOL中的其他位置，导致该节点需要通过中继将令牌传给其后继节点。而组网成功后，该TOL在没有意外情况下是不会改变的，则该节点将一直要执行这个不必要的中继。

以4个节点为例。节点A能与节点B，D通信，节点B能与节点A，C通信，节点C能与节点B，D通信，节点D能与节点A，C通信。A，B，C组网后，会在适当的时候邀请节点D加入令牌环。节点D只能接收到节点A，C的信息，故只有当节点A和节点C发出邀请时，节点D能接收到邀请信息。

若由节点A邀请节点D加入令牌环時，节点A设置节点D的新后继节点为节点B，故节点D加入环后，其组网后令牌传递如图3所示。令牌的TOL为A→D→B→C→A，其中，节点D不能与节点B直接通信，节点C不能与节点A直接通信，这就有两个节点需要经过中继将令牌传输给它们的后继节点。这种情况则引起两次不必要的中继。

图3  节点A邀请节点D入环

以8个节点为例。节点A，B，C，D首先组成令牌环，其中节点E与节点A，B可相互通信，节点H可与节点B，C相互通信，节点G可与节点D，C相互通信，节点F可与节点A，D相互通信。节点B邀请节点E加入令牌环，则E不能到达其后继节点C，需通过中继;节点C邀请节点H加入令牌环，则节点H不能直接到达其后继节点D，节点A邀请节点F入环，则节点F不能直接到达其后继节点B，则整个令牌环路中需要经过4次中继。其TOL为：A→F→B→E→C→H→D→G→A，其令牌传递如图4所示。

3  令牌环传递顺序优化

最近插入法是用于解决旅行商问题（Traveling Salesman Problem，TSP）的一种构造型算法[10?11]。具体的算法描述如下：

假设环路总共有[N]个节点。距离矩阵DM是一个[N×N]型矩阵，其值由每个节点与其他节点间最短距离[disti，j]（相同节点之间[disti，i=0]，不同节点间能直接通信则为1，若不能直接通信需要中继的则为1+需要中继次数）组成;环路周期长度RCL=[dist0，1]+[dist1，2]+…+[distN-1，0];添加节点后环路周期增加长度ΔRCL=[disti，j]+[distj，i+1]-[disti，i+1]。节点插入令牌环的过程如图5所示。

图4  基于中继机制组网令牌传递顺序

图5  节点[j]插入令牌环过程

具体步骤如下：

1） 在邀请新的节点加入后可判断环路周期长度RCL是否等于环内节点数[N]，若RCL>[N]，则采用最近插入法将新加入的节点插入到合适的位置。若RCL=[N]，则说明环内无需中继传输，则保持TOL不变。

2） 确定要重新插入令牌环的节点，TOL列表中相邻节点不能直接通信的节点，前驱节点到后继节点的最短距离不为1的节点。取出需要重新插入节点，假设需优化节点数为[k]，则环内剩余节点数为[N-k]。

3） 取出一个待插入节点[j]，在DM矩阵中找出该节点与令牌环内所有节点的距离，并选出离该节点最近的节点[m，n，…]。

4） 将节点[j]插入到TOL中节点[m]与其后继节点[m+1]之间，计算添加节点[j]之后RCL的增加值ΔRCL[（m，m+1）]。

5） 重复步骤4），将节点[j]插入到剩余其他离该节点最近的节点与其后继节点之间，计算对应的添加节点[j]之后RCL的增加值。

6） 比較所有ΔRCL，选出产生最小ΔRCL的位置，将节点[j]插入到该处。

7） 重复步骤2）～步骤6），直到所有节点均加入令牌环路中。

4  仿真结果

本文在Matlab仿真平台上进行仿真。对4，6，8，10，12个节点进行仿真分析，4节点（A，B，C，D）网络中设置节点A可与节点B，D通信，不能与节点C通信，节点B可与节点A，C通信，不能与节点D相互通信。依次开启节点A、节点B，待节点A，B组网后开启节点C，待节点C入网后开启节点D。6，8，10，12节点网络设置：假设节点数为[N]，节点排成圆形，节点标号按顺时针依次排号为1，2，…，[N]，其中，奇数节点可与其相邻的奇数节点通信;偶数节点只能与相邻的奇数节点通信，不能与其相邻的偶数节点通信。节点开启顺序，首先按顺时针方向依次开启两个奇数节点，待它们组网后再开启之后的奇数节点，直到所有奇数节点组网后，再按顺时针顺序依次开启偶数节点，直到所有节点组网成功。经过多次仿真实验得到结果如表1所示。

表1  中继情况仿真结果

5  结  语

针对传统基于中继机制的组网方法会导致生成的TOL需要使用不必要的中继，导致节点传输令牌的时间增长。本文采用最近插入法将需要中继的节点插入到合适的传递顺序中，以减少不必要令牌中继次数。实验结果表明，节点越多时，在节点只能与邻近节点相互通信的情况下，可能导致中继次数越多。本文中的优化TOL算法能很好地解决该问题，最大化减少令牌环中中继的次数。针对多个节点令牌环网络也能很好地解决问题。

参考文献

[1] HOSSEINABADI Ghazale， VAIDYA Nitin. Token?DCF an opportunistic MAC protocol for wireless network [J]. IEEE communication systems and networks， 2013， 1（1）： 1?9.

[2] YIGITBASI N， BUZLUCA F. A control plane for prioritized real?time communications in wireless token ring networks [J]. IEEE computer and information sciences， 2008， 10（4）： 1?6.

[3] 何敏，赵东风，刘心松.移动Ad Hoc网络分布式并行接入控制协议分析[J].系统工程与电子技术，2007，29（3）：443?448.

HE Min， ZHAO Dongfeng， LIU Xinsong. Analysis of distributed parallel access control protocol in mobile Ad Hoc networks [J]. Journal of systems engineering and electronics， 2007， 29（3）： 443?448.

[4] 张宇眉，张欣，杨大成，等.基于等待时间和信道状态的轮询多址协议[J].北京邮电大学学报，2008，31（4）：126?129.

ZHANG Yumei， ZHANG Xin， YANG Dacheng， et al. Polling multiple access protocol on the waiting time and channel state [J]. Journal of Beijing University of Posts and Telecommunications， 2008， 31（4）： 126?129.

[5] SUN Xianpu， ZHANG Yanling， LI Jiandong. Wireless dynamic token protocol for MANET [C]// Proceedings of 2007 ICPPW. Xian： [s.n.]， 2007： 5?10.

[6] ERGEN M， LEE D， SENGUPTA R， et al. WTRP ? wireless token ring protocol [J]. IEEE transactions on vehicular technology， 2004， 53（6）： 1863?1881.

[7] NATO. Profile for HF Radio Data Communications： STANAG 5066—2015 [S]. Brussels： NATO， 2015： 3.

[8] 贺骁，李曼，白翔，等.短波令牌环协议的研究现状与发展[J].通信技术，2014（10）：1167?1172.

HE Xiao， LI Man， BAI Xiang， et al. Research status and development of high frequency token ring protocol [J]. Journal of communication technology， 2014（10）： 1167?1172.

[9] JOHNSON E E， TANG Z， BALAKRISHNAN M. Token relay with optimistic joining [J]. IEEE MILCIM， 2005， 4（2）： 2216?2222.

[10] 马良.旅行推销员问题的算法综述[J].数学的实践与认识，2000，30（2）：156?165.

MA Liang. An overview of the algorithm for traveling salesman problem [J]. Journal of mathematics in practice and theory， 2000， 30（2）： 156?165.

[11] 朱丽娟，徐小明，夏必胜.SOFM神经网络最近插入法混合算法在TSP问题中应用研究[J].贵州大学学报（自然版），2009，26（6）：21?23.

ZHU Lijuan， XU Xiaoming， XIA Bisheng. Application of SOFM neural network nearest insertion hybrid algorithm in TSP problem [J]. Journal of Guizhou University （Natural edition）， 2009， 26（6）： 21?23.