基于WTRP网络的自适应令牌传递算法*

杨 斌 任 平 刘 义

(1.海军驻武汉七〇一所军事代表室 武汉 430064)(2.电磁兼容性重点实验室,中国舰船研究设计中心 武汉 430064)



基于WTRP网络的自适应令牌传递算法*

杨 斌1任 平2刘 义2

(1.海军驻武汉七〇一所军事代表室 武汉 430064)(2.电磁兼容性重点实验室,中国舰船研究设计中心 武汉 430064)

针对WTRP网络中令牌只能按节点地址依次传递的现状,论文提出一种新的令牌传递算法,能够根据网络中各节点的报文负荷情况,动态调整令牌在逻辑环上的传递顺序,最大限度地减少令牌在逻辑环上空传的次数。OPNET仿真结果表明,该算法提高了网络吞吐量,降低了报文丢失率,减少了平均服务延时,优于WTRP协议原有的令牌传递算法。

令牌传递算法; 无线令牌环协议; 令牌逻辑环

Class Number TP301.6

1 引言

无线令牌环协议(WTRP)是一种分布式MAC层协议,适用于AdHoc网络,利用令牌实现对无线信道的访问控制[1～4]。节点沿逻辑环进行令牌传递和主动发送数据,避免冲突和碰撞,从而解决了暴露终端和隐藏终端的问题。

但是,在WTRP网络中,令牌按照各个节点的地址顺序传递,重节点和轻节点占用相同的网络带宽。一方面,重节点为了发送完所有报文,造成令牌在轻节点之间空传,容易增加报文的网络延时;另一方面,重节点不能利用轻节点发送报文后剩余的网络带宽,从而造成资源浪费。

本文提出一种新的令牌传递算法,通过在各个节点建立令牌传递队列,实时掌握WTRP网络中各节点的报文负荷情况,动态调整令牌在逻辑环上的传递顺序,自适应改变轻、重节点在持有令牌时发送的报文数目,最大限度地降低令牌在逻辑环上空传的几率,且与原有的协议相兼容。

2 WTRP协议及令牌传递算法

WTRP网络利用令牌实现对无线信道的访问控制。令牌在按节点地址组成的逻辑环中顺序传递,但节点只有在持有令牌时才能够主动发送数据,否则只能处于监听和接收状态[5～7]。令牌在逻辑环中的位置由当前持有令牌节点的地址表示,称为本站或TS(This Station)。令牌的下一个位置由TS中的参数NS(Next Station)表示,称为NS或令牌的下一站。如果令牌逻辑环出现故障,则利用节点中的参数PS(Poll Station)进行轮询[8～10]。

WTRP网络中的令牌按节点地址顺序传递,如果令牌传递到了最高地址的节点,其下一个位置为最低地址的节点,这种令牌传递方式简单但有限,当网络中各节点的报文负荷比较均衡时,具有较好的性能,否则容易造成令牌在轻节点之间空传,增加报文的网络延时,影响网络实时性。

比如,一个WTRP网络中有10个节点。在某一时刻,节点N9、N7、N5、N3、N1分别有9、7、5、3、1个不需要应答的数据帧(Data_Not_Expecting_Reply)等待发送,N8、N6、N4、N2、N0没有数据帧等待发送。

假设,请求报文长度Lr的值是23Bits;波特率B的值是19200bits/s;节点最小收发反应延时Tturnaround的值Tt是40bits;节点的两帧之间最大间隔时间Tframegap的值Tf是20bits;令牌帧的长度Lt的值是8Bits。

开始时,N0持有令牌,忽略帧的处理时间和发送数据时间,不同令牌传递方式对网络延时的影响情况如下:

当采用顺序令牌传递方式时,Nmax_info_frame的值为1,N1～N9发送完所有数据帧所需的时间为T0:

T0=(25Lr+100Tt+100Lt)/B

(1)

T0=781.25ms;

当采用自适应令牌传递方式时,Nmax_info_frame的值随着报文的分布情况而动态改变,N1～N9发送完所有数据帧所需的时间为T1:

T1=(11Tf+25Lr+19Tt+19Lt)/B

(2)

T1=353.96ms。T1比T0减少了427.29ms,网络性能提高了54.69%。

3 基于WTRP网络的令牌传递算法

步骤1 在WTRP网络中,三元组Qi(Mi,Ni,Si,Mi≠TS,0≤i

(3)

步骤2 在WTRP网络中,Q(Q1,Q2,…,Qi,0≤i

步骤3 在WTRP网络中,各节点的报文负荷情况为Dmessage,Dmessage:单个令牌传递周期内,有数据发送的节点在所有节点中所占的比例:

(4)

步骤4 在WTRP网络中,Dmessage为依据整个网络的报文负荷情况,节点Mi实时改变在持有令牌时发送的报文数目。DMax和DMin表示WTRP网络报文负荷情况Dmessage的最大门限值和最小门限值,DMax和DMin的值可以根据具体WTRP网络的报文负荷情况做出调整。默认情况下,DMax=0.5,DMin=0.2;

步骤5 在WTRP网络中,Nmax_info_frames:节点Mi在持有令牌时能够发送的报文数目,Nmax_info_frames的值与WTRP网络的报文负荷情况构成分段函数关系:Nmax_info_frames=

(5)

步骤6 在WTRP网络中,Nmax_pass_times为节点Mi在传递令牌时,能够将令牌传递给物理上不相邻的同一个节点的最大次数。默认情况下,Nmax_pass_times=1,Nmax_pass_times的值可以根据WTRP网络的最大延时时间来设定。

4 OPNET仿真及性能分析

4.1 仿真环境的建立

OPNET(Optimized Performance Network Engineering Tool),一种广泛应用的通信与计算机网络仿真软件。WTRP网络OPNET仿真环境的建立包括网络建模、节点建模和进程建模。由此建立的三层模型和实际的WTRP网络、设备完全对应;通过Packet Editer(包编辑器)建立与WTRP协议对应的报文格式,从而全面反映WTRP网络的相关特性。

1) 网络建模和节点建模

WTRP是一个令牌逻辑环网络,拓扑结构为令牌环型,仿真网络中节点的数目为10。通过Node Editor(节点编辑器)描述WTRP节点的层次结构,并通过功能模块之间的数据流来实现WTRP网络的体系结构,如图1所示。

图1 网络拓扑结构和节点模型

2) 进程建模

通过有限状态机进行建模,每个状态内写入任意的C/C++代码以及专门为WTRP协议设计的库函数,包括WTRP协议接收帧状态机和节点状态机,用于定义节点内功能模块中各事件之间的控制流。

4.2 性能评估的方法

在本文中,通过比较WTRP不同网络负荷下节点的网络吞吐量、平均服务延时和报文丢失率,来判断该令牌传递算法对网络性能是否有所改善。

其中,平均服务延时表示通过OPNET中的统计量表示Node Statistics/Token Ring/Delay(s)来反映;报文丢失率表示丢失的报文数目/所发送的报文数目;网络吞吐量表示在单位时间内,WTRP网络发送和接收的数据量,由OPNET中的统计量:Node Statistics/Token Ring/Load(bits/s)和Node Statistics/Token Ring/Traffic Received(bits/s)通过计算得到。

设WTRP网络负荷为G,G的值:0～1之间,随着网络负荷的增加而增大:

(6)

其中,Li为节点Mi发送报文的平均长度;B为数据的传输速率(bits/s);N为WTRP仿真模型中节点的数目;Ti为每个节点依据泊松分布随机产生报文的时间间隔,Ti为调整网络负荷G大小的参量。

4.3 仿真结果分析

利用该OPNET仿真模型一共进行了三组实验,通过分析数据得到如下实验结果:

1) 令牌传递算法对平均服务延时的影响

第一组实验:令牌传递算法对平均服务延时的影响,如图2所示。

从图2可以看出,网络负荷G值越大,各节点等待发送的报文也越多,发送完报文需要的时间也越长。随着G值的增加,两种令牌传递算法下的平均服务延时均逐渐增大,但在相同的网络负荷下,自适应令牌传递算法的平均服务延时明显小于顺序令牌传递算法。

图2 令牌传递算法对平均服务延时的改善

当G的值在0.2～0.5之间,该令牌传递算法对平均服务延时的改善最为明显。这是因为,当G的值较小时,报文分布的值也相应变小,令牌只在有报文需要发送的节点之间传递;同时,节点Nmax_pass_times的值增大,需要发送数据越多的节点占用的网络带宽越大,从而减少了令牌在逻辑环上空传的次数;当网络负荷G>0.5时,报文分布的值相应变大,节点Nmax_pass_times的值重新设置为1,平均服务延时逐渐接近顺序令牌传递算法。

2) 令牌传递算法对报文丢弃率的改善

第二组实验:令牌传递算法对报文丢弃率的影响,如图3所示。

图3 令牌传递算法对报文丢弃率的改善

从图3可以看出,两种令牌传递算法下的报文丢弃率随着网络负荷G的增大而增大;当G>0.5时,自适应令牌传递算法的报文丢弃率增大的速度明显加快,令牌在基本上逻辑环上顺序传递,报文丢弃率逐渐接近顺序令牌传递算法。这是因为,当G<0.5时,WTRP网络的负荷比较小,需要发送报文的节点也相对较少,自适应令牌传递算法通过动态调整令牌的传递顺序,并且改变重节点Nmax_pass_times的值,使更多的报文能够在规定的时间以内发送出去,从而降低了报文丢弃率。

3) 令牌传递算法对网络吞吐量的改善

第三组实验:令牌传递算法对网络吞吐量的影响,如图4所示。

从图4可以看出,当G<0.5时,两种令牌传递算法下的网络吞吐量与网络负荷G之间基本上呈线性关系;当G>0.5时,网络吞吐量增长的速度逐渐降低。自适应令牌传递算法网络吞吐量降低的速度明显小于顺序令牌传递算法。这是因为,网络负荷G越大,报文丢弃率也越大,当报文丢弃率增大的速度大于网络负荷G增大的速度时,网络吞吐量开始减少。因为自适应算法下的报文丢弃率优于顺序令牌传递算法,所以自适应算法下网络吞吐量降低的速度明显小于顺序令牌传递算法。

图4 令牌传递算法对网络吞吐量的改善

5 结语

基于WTRP协议的自适应令牌传递算法,通过改变令牌在逻辑环上的传递顺序和节点在持有令牌时发生报文的数目,解决了原有WTRP协议中令牌只能固定顺序传递的问题,从而使整个网络的令牌传递和带宽分配更加合理。OPNET软件仿真结果表明,该算法减少了WTRP网络的报文平均服务延时,降低了报文丢失率,提高了网络吞吐量。

[1] Menouar, F lenardi. A Survey and qualitative analysis of MAC protocols for vehicular ad hoc networks[J]. IEEE Wireless Communication,2006,13(5):30-35.

[2] Tae-Jin Park, Young-Chan Kwon, Seung-Ho Hong. Performance evaluation of BACnet WTRP protocol using experimental model[J]. ICIT 2005,2005:87-90.

[3] 孙献璞,张艳玲.一种新的令牌传递算法[J].西安邮电学院学报,2005,10(2):122-125.

[4] Abdelouahid Derhab, Nadjib Badache. A distributed mutual exclusion algorithm over multi-routing protocol for mobile ad hoc networks[J]. International Journal of Parallel,2008,23(3):197-218.

[5] 孙献璞,张艳玲,宋彬.采用动态令牌的MANET多址接入协议[J].电子学报,2006,34(1):118-122.

[6] 陈敏.OPNET网络仿真[M].北京:清华大学出版社,2004:12-16.

[7] D. Lee, R. Attias. A Wireless Token Ring Protocol for Ad Hoc Network[C]//IEEE Aerospace Conference Proceedings,2002:1219-1228.

[8] 张艳玲,宋彬.采用动态令牌的MANET多址接入协议[J].电子学报,2006:118-122.

[9] Ergen Mustafa, Lee Duke. WTRP-wireless token ring protocol[J]. IEEE Transactions on Vehicular Technology,2004,53(6):1862-1879.

[10] XU Liyang. Research on Wireless Token Network With Sub-Nodes Protocol For Wireless Ad Hoc Network[D]. Beijing: Beijing University of Posts and Telecommunications,2013.

A Self-adaptive Token Passing Algorithm for the WTRP Network

YANG Bin1REN Ping2LIU Yi2

(1. Navy Representative Office of 701 Institute, Wuhan 430064) (2. The National Key Laboratory of EMC, China Ship Development and Design Centre, Wuhan 430064)

With the actuality of token can only be passed according to the station’s address orderly, a new token passing algorithm is proposed. This algorithm adjusts the token passing order on the logic ring dynamically according to the message distribution of stations in the WTRP network, to minimize the times of token passing over the logic ring. OPNET simulation results show that the algorithm has reduced the average service delay, decreased the message drop rate, and increased the network throughput. It is better than the original token passing algorithm of WTRP protocol.

token passing algorithm, WTRP protocol, token logic ring

2014年11月8日,

2014年12月23日

杨斌,男,工程师,研究方向:通信。

TP301.6

10.3969/j.issn1672-9730.2015.05.014