- 1 -
中国科技论文在线
面向无线自组网的具有子节点的无线令牌
网协议设计
许丽阳，杨波**
作者简介：许丽阳，（1988-），女，学生，主要研究方向：无线自组网MAC层协议。
通信联系人：杨波，（1959-），男，副教授，主要研究方向：多媒体通信。
（北京邮电大学信息与通信工程学院，北京 100876） 5
摘要：无线令牌环协议（WTRP）是一种适用于 Ad Hoc 网络的，并能够在 MAC 层提供一
定 QoS 保障机制的接入控制协议，可以满足在低速移动的条件下，从错误状态中快速恢复
的要求。然而当网络拓扑结构快速变化时，则难以维护网络的稳定性。本文提出了一种改进
的具有子节点的无线令牌网协议（Wireless Token Network with Sub-nodes Protocol，WTNSP），
将闭环网络的具有前驱后继的全连接节点改进为具有子节点的节点，这样扩大了网络覆盖范10
围，能更好的支持拓扑结构快速变化。同时，动态变化的令牌持有时间也有效提高了数据吞
吐量。
关键词：无线通信技术；Ad Hoc 网络；无线令牌环协议；子节点；动态拓扑结构
Design of Wireless Token Network with Sub-nodes Protocol 15
for Ad Hoc Network
XU Liyang, YANG Bo
(School of Information and Communication Engineering, Beijing University of Posts and
Telecommunications, Beijing 100876)
Abstract: The Wireless Token Ring Protocol (WTRP) is a distributed medium access control 20
(MAC) protocol which features self-organization, self-healing and no center, etc. It also
guarantees fair node access and quality of service (QoS). It is proved to be a valuable MAC
protocol candidate for wireless sensor networks with relatively stable structure. But due to the
enclosed nature of the ring structure, WTRP is not suitable for scenarios with rapid topology
variations. This paper presents a modified protocol called WTNSP(Wireless Token Network with 25
Sub-nodes Protocol) with sub-nodes which only have predecessor but no successor. The modified
node joining mechanism expands the closed loop into net with sub-nodes, which enables better
coverage and higer moving speed; while dynamic token hold time adjusting enhances data
throughput.
Keywords: Wireless Communication Technology; Ad Hoc; WTRP; Sub-node; dynamic topology 30
0 引言
Ad Hoc网络具有无中心、自组织、可移动、灵活性等特点，有着广泛的应用场景，因
此使其备受重视。目前国内外有很多研究人员对 Ad Hoc网络的媒体介入控制层（MAC）协
议进行了大量有意义的研究。MAC 层协议主要分为两类，即基于竞争的 MAC 协议和无竞35
争的MAC协议。1994年提出的MACAW协议[1]，是很多基于竞争的MAC协议的基础。此
外还有 CSMA[2]，T-MAC[3]，IEEE DCF[4]，S-MAC[5]，这类协议基本思想都是节点在
传输前通过短控制帧握手信号预约信道，在完成预约后进行无冲突传输。但是由于在握手预
约信道时存在的竞争和冲突，使得基于竞争的MAC协议无法提供高时延要求的 QoS保障。
基于无竞争的MAC协议能够有效避免共享信道的节点间的冲突，使得系统吞吐量更高，并40
可得到较好的 QoS保障。IEEE PCF是一种基于无竞争的协议，但其轮询机制采用中
心站轮询从站的方式，这不符合无中心组网的要求。无线令牌环接入控制协议（Wireless
Token Ring Protocol，WTRP）[6]是基于分布式轮询的，可以满足 Ad Hoc的性能要求。
- 2 -
中国科技论文在线
WTRP是一种基于分布式轮询机制的控制接入协议，令牌环上节点按顺序在令牌持有时
间内发送数据包，每个节点享有同等带宽和同等的发送权。此外，WTRP还可以支持网络中45
节点的加入或者离开，并能保证令牌环网络的稳定性。但是 WTRP 协议也有其局限性。一
方面，令牌环网络上的每个节点都有前驱节点和后继节点，然而对于某些节点只在令牌环网
络中某一个节点的通讯范围内的情况，WTRP是无法将其包含到网络中的。另一方面，网络
拓扑结构快速变化时，希望网络可以支持更大范围内的通信，这对节点快速移动的情况是有
很大益处的。另外，为了确保公平性，WTRP协议中每个节点持有令牌的时间是等长的，即50
便节点没有数据发送时也会给其分配相同的令牌持有时间，这对于网络拓扑结构快速变化的
场景也是不利的。本文研究分析了 WTRP 协议，并针对网络拓扑结构快速变化的应用场景
其提出了三点改进。
本文内容主要是：第二部分详细分析了 WTRP 协议，第三部分提出了三点改进措施，
第四部分分析比较了两种协议的性能，最后进行总结。 55
1 WTRP研究
WTRP是一种基于无竞争，且采用分布式轮询的MAC协议，通过建立逻辑令牌环、环
上节点依次传递令牌的方式使用和管理无线信道资源。
WTRP协议介绍
令牌环上的每个节点都有其前驱节点和后继节点，当从前驱节点接过令牌后，当前节点60
便可在持有令牌的时间内发送数据，当时间达到最大令牌持有时间时便强行停止发送数据，
将令牌传给后继节点，循环此过程。这种方式使得网络中每个节点享有同等带宽和发送权，
不存在竞争和冲突。此外，WTRP协议允许令牌环随时有节点的加入和离开。当某个节点持
有令牌时，会对其通信范围内的节点发出邀请，处于漂移状态的节点可以申请加入令牌环。
令牌环对个别节点的失效具有鲁棒性，当环上节点主动或被动离开网络，令牌环可以在一定65
时间内恢复封闭的逻辑令牌环网络。
WTRP协议可以用八个状态的有限状态机[7]来完备描述，分别是：开始状态，漂移状态，
离线状态，空闲状态、持有令牌状态、等待加入状态、请求状态和监控状态。开始状态表示
协议的开始，是一种虚拟状态。令牌环网络建立后，环上节点在空闲状态、持有令牌状态、
邀请状态和监控状态这四个状态之间循环。节点在持有令牌状态发送数据，当其数据发送完70
毕且没有超过最大令牌持有时间时，进入请求状态邀请其他节点加入。节点将令牌递给下一
节点后进入监控状态，等收到隐含确认信息后进入空闲状态，等待下一轮令牌。不在令牌环
网络里的节点，当收到加入邀请并回应该邀请后进入等待加入状态。漂移状态和离线状态用
于避免不同环之间的干扰。
节点接入过程 75
节点加入令牌环网络的过程采用四步握手机制，如图 1 所示。环上节点 A 广播请求后
继（solicit_successor）令牌，其中包含其后继节点 C的地址。为避免接入冲突，等待接入的
节点均随机退避一个时间长度，若退避过程中没有听到其他节点的接入申请，则在退避结束
后立即发出自己的接入申请（set_successor）令牌，并记下可能的后继节点 C的地址。A收
到 B发出的 set_successor后，给 B发出设置前驱（set_predecessor）令牌，将 B记为自己的80
后继节点。B收到该令牌后，将 A记为自己的前驱节点。然后给 C发送设置前驱令牌，将
C 记为自己的后继节点。至此，采用四步握手机制，等待接入的节点 B 成功加入令牌环网
- 3 -
中国科技论文在线
络，令牌环网络闭合。
图 1 节点加入过程 85
MAC帧结构
WTRP协议通过令牌的传递控制和管理节点共享的传输媒介，因此令牌帧格式中含有大
量隐含的控制信息。WTRP的MAC帧的通用帧格式如表 1所示。
90
表 1 WTRP协议的MAC帧结构
FC RA DA SA NoN GenSeq Seq NS
1 6 6 6 2 4 4 6
Bytes
FC：帧控制字段（Frame Control），定义了帧的类型。
RA：环地址（Ring Address），定义令牌环主节点MAC地址，标识令牌所属令牌环，95
以区别不同令牌环上的令牌。该节点是在建立令牌环之初通过竞争产生的逻辑环主节点。
DA：目的地址（Destination Address），定义令牌传递的目的节点的MAC地址。
SA：源地址（Source Address），定义令牌传递的源节点MAC地址。
NoN：允许接入节点数（Number of Node），定义令牌环上允许接入的节点个数。
GenSeq：令牌序列号（Generation Sequence Number），定义令牌循环周数。初始值为 0，100
令牌每次回到环主节点认为循环一周，GenSeq加 1。
Seq：节点序列号（Sequence Number），定义一个周期内令牌传递次数。初始值为 0，
令牌经过一个传递的节点 Seq加 1，直到再次传回环主节点，Seq重置为 0。
WTRP通过建立有序的令牌环网络控制并管理共享信道，可以有效减少由于碰撞产生的
数据重传，从而极大的提高了系统效率。同时，WTRP协议可以抵抗由于一些节点离开而产105
生的鲁棒性，提供 QoS 保障，一定程度上可以适应变化的拓扑结构。但是对于网络结构快
速变化的情况，WTRP 协议存在许多不足之处，对此已经有一些科研工作者做出改进工作
[8][9]。本文在此基础上，为解决拓扑结构快速移动的问题，从网络范围覆盖面积的角度提出
了具有子节点的无线令牌网协议。
2 具有子节点的无线令牌网协议 110
WTRP协议可以满足 Ad Hoc网络部分要求，但是在解决拓扑结构快速移动方面性能欠
佳。本文提出具有子节点的无线令牌网协议，主要可以增大令牌环网络的覆盖面积，以更好
的适应 Ad Hoc网络要求。本节具体描述了具有子节点的无线令牌网协议的三个改进点：子
A
B
C D
E
F
请求后继
设置后继
设置前驱
设置前驱
时间
A B C
- 4 -
中国科技论文在线
节点、MAC帧结构、动态令牌持有时间。
子节点 115
WTRP协议中，节点接入采用四步握手机制，每个节点需要同时设置其前驱节点以及后
继节点。这使得每个节点都与两个节点相连，得到闭合的令牌环网络。但是当一个节点的通
信范围内有且仅有一个令牌环网络上的节点时，该节点就无法加入令牌环，如图 2所示。节
点 8和节点 9只在节点 3的通信范围内，所以按照WTRP协议的要求则无法加入令牌环。
此外，节点 7的通信范围如图中红圈所示，节点 2和节点 3不在其通信范围内，如果节点 1120
主动或被动离开令牌环，按照WTRP协议要求，节点 7则会试图让节点 2作为其后继节点。
但因节点 2不在其通信范围内，所以节点 7会继续往后寻找直到联系上节点 4，将节点 4作
为自己的后继节点，闭合令牌环。这种情况下，令牌环网络的覆盖范围就会因此变小，从而
不能很好的支持拓扑结构快速变化的场景。
125
图 2 WTRP拓扑结构
为了解决上述问题，具有子节点的无线令牌网协议提出子节点以半连接方式接入网络的
措施，子节点区别于令牌网主环上的节点，不要求同时具有前驱节点和后继节点。子节点的
前驱节点是令牌网主环上的节点子，不能连接后继节点。子节点使网络的拓扑结构变成具有130
主环的非闭合网状结构，这种拓扑结构能包容更多节点到网络中，使得网络的通信覆盖范围
更大。此外，如果子节点连接过多，则会影响令牌网的稳定性以及节点的数据传递效率，因
此具有子节点的无线令牌网协议规定网络中子节点总数不能超过令牌主环上节点总数，
MAC帧增加节点优先级字段，用来区分该节点为令牌主环上的节点或者子节点。如图 3所
示，节点 6是节点 3所携带的子节点，节点 5是节点 4所携带的子节点。此外，考虑到令牌135
网的公平性和稳定性，WTNSP规定节点在接入网络时优先选择以完全连接的接入方式加入
令牌网主环，也就是说，在节点同时可以听到令牌网主环上两个节点时，选择完全连接接入
方式而非作为子节点以半连接接入方式接入令牌网。
图 3 WTNSP包含子节点的拓扑结构 140
1
2
3
4
5
6
- 5 -
中国科技论文在线
基础令牌网
一方面，通常在网络建立的初期，网络中各通信节点的位置相对固定且范围相对集中，
其相对稳定集中的网络拓扑结构更适合令牌网的建立。另一方面，大多数网络系统中需要所
有节点相互传递数据信息，例如数据协同通信系统，需要网络通信覆盖范围内的所有节点相
互通信。从这两方面综合分析，令牌网建立初期只传递令牌以建立网络不传递数据信息，更145
有利于令牌网的建立并能提高网络效率及可靠性。具有子节点的无线令牌协议定义可能节点
和基础令牌网概念，以高效建立网络。
令牌网建立初期，逻辑令牌网主节点申请自环后，发出请求后继令牌邀请其通信范围内
其他节点加入网络。在逻辑令牌网主节点通信范围内的其他收听到该请求后继令牌后，若决
定加入网络便发出设置后继令牌，WTNSP将这些发出设置后继令牌的节点定义为可能节点，150
用于提高令牌网建立的效率。
基础令牌网是指尽可能包含所有可能节点的令牌网络。建立基础令牌网的过程中节点之
间不互相传送数据信息，只进行令牌的传递以建立网络。逻辑令牌网主节点申请自环成功，
在发出请求后继令牌邀请其他节点加入后，将听到反馈设置后继令牌的节点记为该令牌网的
可能节点，记下可能节点的MAC地址以及可能节点的个数 N。逻辑令牌网主节点在成功邀155
请一个后继节点后，若 N > 1则先不与其交换数据信息，继续邀请其他可能节点加入令牌网。
当逻辑令牌网主节点发出请求后继令牌后，没有收到来自可能节点的设置后继令牌，则判断
基础令牌网建立完成。基础令牌网建立完成之后，令牌网内各通信节点则进入数据信息交换
及令牌网动态维护等过程。
子节点接入过程 160
子节点加入令牌网的过程如图 4 所示。令牌网主环上节点 A 广播请求后继令牌，其中
包含其后继节点 C的地址。节点 B听到该请求后继令牌决定加入令牌网，为避免接入冲突
等待接入的节点 B 随机退避一个时间长度，在退避结束后发出自己的设置后继令牌，并记
下可能的后继节点 C的地址。节点 A收到节点 B发出的设置后继令牌后，给节点 B发出设
置前驱令牌，节点 B 收到该令牌后，给其可能的后继节点 C 发出设置前驱令牌并开启令牌165
传输定时器。若节点 C不在节点 B的通信范围内，则无法收到该设置前驱令牌，节点 C也
不会收到隐含的确认信号，令牌传输定时器到时后，重发设置前驱令牌，定时器再次到时后
仍然没有响应，节点 B则判断自己为子节点。节点 B发送设置子节点令牌给节点 A，并将
节点 A记做父节点。节点 A收到设置子节点令牌后，更新本地连接表将节点 B记做子节点，
后继节点仍为节点 C不变。 170
- 6 -
中国科技论文在线
图 4 WTNSP子节点加入过程
MAC帧结构
WTNSP协议MAC帧结构如表 1所示。FC为帧控制字段，定义帧类型为控制帧或是数175
据帧。 NA 为令牌网地址、DA、SA、NS 为地址字段，定义令牌网逻辑环主地址、当前帧
发送的目的地址、当前帧发送的源地址以及其后继节点的MAC地址。NoN表示令牌环上接
入的节点个数，Seq定义一个周期内令牌传递次数，令牌传递过一个节点该值加 1，GenSeq
描述令牌循环周数，以区分令牌环优先等级。
具有子节点的无线令牌网协议定义令牌网络中允许存在只具有前驱节点的子节点，为区180
分于令牌主环上的节点，在 WTNSP的 MAC 帧结构中用 NoS 和 SUBA 两个字段描述子节
点。NoS表示某令牌主环节点携带子节点的个数，为保证令牌主环节点的有效传输，提高系
统性能，WTNSP规定任一令牌主环节点所携带的子节点个数不得超过令牌主环节点数，即
2NoS < NoN。SUBA给出某令牌主环节点所携带的子节点的地址，按照子节点接入该主环
节点的顺序依次排列。 185
表 1 WTNSP协议MAC帧结构
FC NA DA SA NoN GenSeq Seq NS NoS SUBA
1 6 6 6 2 4 4 6 4 4
Bytes
C A
B
A B C
时间
请求后继
设置后继
设置前驱
设置前驱
无应答
设置前驱
无应答
设置子节点
- 7 -
中国科技论文在线
动态令牌持有时间
WTNSP允许令牌主环节点携带子节点，且携带子节点的个数不定，因此每个主环节点190
所携带子节点个数动态变化。为保证无线令牌网络的有效性，具有子节点的无线令牌网协议
定义动态令牌持有时间（Dynamic_Token_Holding_Timer，DTHT），用于描述令牌主环节
点持有令牌的时间，其值定义为携带子节点个数与最大令牌持有时间的乘积（即
Num_Subnodes * MTHT）。WTNSP的MAC帧中，有用于表述令牌级别及携带子节点个数
的字节，其他节点收到听该节点发出的令牌时，就可以通过此数据计算出该节点的动态令牌195
持有时间。
3 协议性能分析
本节使用 NS2 仿真工具对具有子节点的无线令牌网协议的性能进行仿真分析，在评判
MAC组网协议时，通常衡量网络覆盖范围及吞吐量等指标。下文将从通信网络覆盖范围以
及吞吐量两方面分析WTNSP协议性能，并与无线令牌环协议相应性能对比分析。 200
网络覆盖范围
由于 WTNSP 和 WTRP 的网络拓扑结构不同，覆盖范围及单个环所携带的节点数目都
不同，为方便对比在 50x50的区域内撒出 40个节点，测试两种 MAC层组网协议的网络拓
扑结构及其覆盖范围。
205
图 5 WTRP网络拓扑结构仿真结果
- 8 -
中国科技论文在线
图 6 WTNSP网络拓扑结构仿真结果
210
图 5和图 6所示的分别是在一次仿真中得到的WTRP和WTNSP网络拓扑结构。如图 5
所示，WTRP的拓扑结构中共存在 8个令牌环，其中最小的环包含 2个节点，最大的环包含
13个节点，还有一个孤立节点。如图 6所示，WTNSP的拓扑结构则是呈现节点簇形式，一
共存在 3个节点簇，最多包含 21个节点最少包含 3个节点。
进一步通过 100 次伯努利试验，分别统计使用 WTRP 协议和 WTNSP 协议，网络中单215
个环的最大节点数。结果如图 7所示。
图 7 单个环最大节点数对比
观察上图发现，WTNSP 协议中单个环携带的节点数目明显大于 WTRP 协议。由于220
WTNSP支持子节点存在于网络中，使其拓扑结构变成非闭合的环网络，因此WTNSP的网
络覆盖范围明显大于无线令牌环协议，具有子节点的无线令牌网络中可容纳更多的通信节
点，从而能更好地适应节点快速移动的应用场景。
吞吐量
假设网络包含 N 个节点，其中 n 个节点一直有数据等待发送且仅有一个数据帧，其余225
m = N – n个节点在其令牌持有时间内有数据需要发送的概率符合参数为 λ( 0<λ<1)的泊松分
布。一个数据帧的平均长度为 Ld，令牌帧长度为 Lt，MAC层和物理层开销为 L，数据传输
- 9 -
中国科技论文在线
速度为 R bps。简单计算得到传输一个数据帧的时间 Td=( Ld+L)/R，传输一个令牌帧的时间
Tt=( Lt+L)/R。忽略其他时间开销，WTRP的吞吐量可以表示成 S = Ld ( n+m ) / (NTt + nTd )。
对于 WTNSP协议，m个节点事实上完全占用其令牌持有时间，即 λ=1。因此 WTNSP230
的吞吐量可表示为 S = Ld / ( Tt + Td)。
图 8 吞吐量仿真结果
根据对WTNSP协议和WTRP协议吞吐量的理论推导，对其吞吐量性能进行仿真分析。235
具体仿真条件为：网络包含 40 个节点，其中 10 个节点按泊松分布产生数据。数据帧长 Ld
为 1024Bytes，令牌帧长 Lt为 29Bytes，MAC层和物理层开销 L为 12Bytes。数据传输速度
为 1M bps。仿真结果如图 8 所示，WTRP 的吞吐量受 λ 的线性影响，当 λ=0 时吞吐量为
，约为WTNSP吞吐量的 75%。WTNSP协议的吞吐量不受 λ影响，一直为饱和状
态。 240
4 结论
本文提出了一种具有子节点的无线令牌网协议（Wireless Token Network with Sub-nodes
Protocol，WTNSP），从协议的网络架构、MAC 帧结构、令牌网建立及维护等方面对协议
进行了详细描述。WTNSP作用于通信网络的 MAC层，协议允许无线令牌网络中存在只与
令牌主环上一个节点连接的子节点，子节点以半连接方式接入令牌网。为使子节点在令牌网245
中正常工作，具有子节点的无线令牌网协议在MAC帧结构以及令牌网维护等方面为子节点
新增了令牌帧和加入/离开机制，WTNSP还规定令牌持有时间根据携带子节点数动态变化，
有效地提高了数据吞吐量。子节点的存在扩大了通信网络覆盖范围，能更好的支持拓扑结构
快速变化。此外，WTNSP规定令牌网建立初期，只建立基础令牌网而不发送数据信息，有
效地提高了网络建立时间。 250
[参考文献] (References)
[1] Vaduvur Bharghavan. MACAW A Medium Access Protocol for Wireless LAN's[J]. ACM SIGCOMM，1994，
25：212-225.
[2] Theodore Rappaport. Wireless Communications:Principles and Practice[M]. Prentice Hall：PTR，2002. 255
[3] Tijs van Dam, Koen Langendoen. An Adaptive Energy Efficient MAC Protocol for Wireless Networks[J].
Proceedings of the First ACM Conference on Embedded Networked Sensor Systems，2003，12：213-224.
[4] Giuseppe Bianchi. Performance Analysis of the IEEE Distributed Coordination Function[J]. IEEE
Journal on selected areas in communications，2000，18：1819-1828.
- 10 -
中国科技论文在线
[5] Wei Ye, , D. Energy-Efficient MAC Protocol for Wireless Sensor Networks[J]. IEEE 260
INFOCOM，2002，2：1567-1576.
[6] token ring protocol[J]. IEEE Transactions on Wireless Technology，2004，53：512-520.
[7] Mustafa Ergen. WTRP-Wireless Token Ring Protocol[D]. California：University of California，2002.
[8] Ray-Guang Cheng, Ruei-I Chang. Improved Wireless Token Ring Protocol (IWTRP) for Wireless
Metropolitan Area Networks[J]. Vehicular Technology Conference，2007，5：31-35. 265
[9] Sun Xianpu, Zhang Yanling. Wireless Dynamic Token Protocol for MANET[Z]. Canada：International
Conference on Parallel Processing Workshop，2007.
