基于WTRP網(wǎng)絡(luò)的自適應(yīng)令牌傳遞算法*

楊 斌 任 平 劉 義

(1.海軍駐武漢七〇一所軍事代表室 武漢 430064)(2.電磁兼容性重點(diǎn)實(shí)驗(yàn)室,中國(guó)艦船研究設(shè)計(jì)中心 武漢 430064)

?

基于WTRP網(wǎng)絡(luò)的自適應(yīng)令牌傳遞算法*

楊 斌1任 平2劉 義2

(1.海軍駐武漢七〇一所軍事代表室 武漢 430064)(2.電磁兼容性重點(diǎn)實(shí)驗(yàn)室,中國(guó)艦船研究設(shè)計(jì)中心 武漢 430064)

針對(duì)WTRP網(wǎng)絡(luò)中令牌只能按節(jié)點(diǎn)地址依次傳遞的現(xiàn)狀,論文提出一種新的令牌傳遞算法,能夠根據(jù)網(wǎng)絡(luò)中各節(jié)點(diǎn)的報(bào)文負(fù)荷情況,動(dòng)態(tài)調(diào)整令牌在邏輯環(huán)上的傳遞順序,最大限度地減少令牌在邏輯環(huán)上空傳的次數(shù)。OPNET仿真結(jié)果表明,該算法提高了網(wǎng)絡(luò)吞吐量,降低了報(bào)文丟失率,減少了平均服務(wù)延時(shí),優(yōu)于WTRP協(xié)議原有的令牌傳遞算法。

令牌傳遞算法; 無線令牌環(huán)協(xié)議; 令牌邏輯環(huán)

Class Number TP301.6

1 引言

無線令牌環(huán)協(xié)議(WTRP)是一種分布式MAC層協(xié)議,適用于AdHoc網(wǎng)絡(luò),利用令牌實(shí)現(xiàn)對(duì)無線信道的訪問控制[1～4]。節(jié)點(diǎn)沿邏輯環(huán)進(jìn)行令牌傳遞和主動(dòng)發(fā)送數(shù)據(jù),避免沖突和碰撞,從而解決了暴露終端和隱藏終端的問題。

但是,在WTRP網(wǎng)絡(luò)中,令牌按照各個(gè)節(jié)點(diǎn)的地址順序傳遞,重節(jié)點(diǎn)和輕節(jié)點(diǎn)占用相同的網(wǎng)絡(luò)帶寬。一方面,重節(jié)點(diǎn)為了發(fā)送完所有報(bào)文,造成令牌在輕節(jié)點(diǎn)之間空傳,容易增加報(bào)文的網(wǎng)絡(luò)延時(shí);另一方面,重節(jié)點(diǎn)不能利用輕節(jié)點(diǎn)發(fā)送報(bào)文后剩余的網(wǎng)絡(luò)帶寬,從而造成資源浪費(fèi)。

本文提出一種新的令牌傳遞算法,通過在各個(gè)節(jié)點(diǎn)建立令牌傳遞隊(duì)列,實(shí)時(shí)掌握WTRP網(wǎng)絡(luò)中各節(jié)點(diǎn)的報(bào)文負(fù)荷情況,動(dòng)態(tài)調(diào)整令牌在邏輯環(huán)上的傳遞順序,自適應(yīng)改變輕、重節(jié)點(diǎn)在持有令牌時(shí)發(fā)送的報(bào)文數(shù)目,最大限度地降低令牌在邏輯環(huán)上空傳的幾率,且與原有的協(xié)議相兼容。

2 WTRP協(xié)議及令牌傳遞算法

WTRP網(wǎng)絡(luò)利用令牌實(shí)現(xiàn)對(duì)無線信道的訪問控制。令牌在按節(jié)點(diǎn)地址組成的邏輯環(huán)中順序傳遞,但節(jié)點(diǎn)只有在持有令牌時(shí)才能夠主動(dòng)發(fā)送數(shù)據(jù),否則只能處于監(jiān)聽和接收狀態(tài)[5～7]。令牌在邏輯環(huán)中的位置由當(dāng)前持有令牌節(jié)點(diǎn)的地址表示,稱為本站或TS(This Station)。令牌的下一個(gè)位置由TS中的參數(shù)NS(Next Station)表示,稱為NS或令牌的下一站。如果令牌邏輯環(huán)出現(xiàn)故障,則利用節(jié)點(diǎn)中的參數(shù)PS(Poll Station)進(jìn)行輪詢[8～10]。

WTRP網(wǎng)絡(luò)中的令牌按節(jié)點(diǎn)地址順序傳遞,如果令牌傳遞到了最高地址的節(jié)點(diǎn),其下一個(gè)位置為最低地址的節(jié)點(diǎn),這種令牌傳遞方式簡(jiǎn)單但有限,當(dāng)網(wǎng)絡(luò)中各節(jié)點(diǎn)的報(bào)文負(fù)荷比較均衡時(shí),具有較好的性能,否則容易造成令牌在輕節(jié)點(diǎn)之間空傳,增加報(bào)文的網(wǎng)絡(luò)延時(shí),影響網(wǎng)絡(luò)實(shí)時(shí)性。

比如,一個(gè)WTRP網(wǎng)絡(luò)中有10個(gè)節(jié)點(diǎn)。在某一時(shí)刻,節(jié)點(diǎn)N9、N7、N5、N3、N1分別有9、7、5、3、1個(gè)不需要應(yīng)答的數(shù)據(jù)幀(Data_Not_Expecting_Reply)等待發(fā)送,N8、N6、N4、N2、N0沒有數(shù)據(jù)幀等待發(fā)送。

假設(shè),請(qǐng)求報(bào)文長(zhǎng)度Lr的值是23Bits;波特率B的值是19200bits/s;節(jié)點(diǎn)最小收發(fā)反應(yīng)延時(shí)Tturnaround的值Tt是40bits;節(jié)點(diǎn)的兩幀之間最大間隔時(shí)間Tframegap的值Tf是20bits;令牌幀的長(zhǎng)度Lt的值是8Bits。

開始時(shí),N0持有令牌,忽略幀的處理時(shí)間和發(fā)送數(shù)據(jù)時(shí)間,不同令牌傳遞方式對(duì)網(wǎng)絡(luò)延時(shí)的影響情況如下:

當(dāng)采用順序令牌傳遞方式時(shí),Nmax_info_frame的值為1,N1～N9發(fā)送完所有數(shù)據(jù)幀所需的時(shí)間為T0:

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

(1)

T0=781.25ms;

當(dāng)采用自適應(yīng)令牌傳遞方式時(shí),Nmax_info_frame的值隨著報(bào)文的分布情況而動(dòng)態(tài)改變,N1～N9發(fā)送完所有數(shù)據(jù)幀所需的時(shí)間為T1:

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

(2)

T1=353.96ms。T1比T0減少了427.29ms,網(wǎng)絡(luò)性能提高了54.69%。

3 基于WTRP網(wǎng)絡(luò)的令牌傳遞算法

步驟1 在WTRP網(wǎng)絡(luò)中,三元組Qi(Mi,Ni,Si,Mi≠TS,0≤i

(3)

步驟2 在WTRP網(wǎng)絡(luò)中,Q(Q1,Q2,…,Qi,0≤i

步驟3 在WTRP網(wǎng)絡(luò)中,各節(jié)點(diǎn)的報(bào)文負(fù)荷情況為Dmessage,Dmessage:單個(gè)令牌傳遞周期內(nèi),有數(shù)據(jù)發(fā)送的節(jié)點(diǎn)在所有節(jié)點(diǎn)中所占的比例:

(4)

步驟4 在WTRP網(wǎng)絡(luò)中,Dmessage為依據(jù)整個(gè)網(wǎng)絡(luò)的報(bào)文負(fù)荷情況,節(jié)點(diǎn)Mi實(shí)時(shí)改變?cè)诔钟辛钆茣r(shí)發(fā)送的報(bào)文數(shù)目。DMax和DMin表示W(wǎng)TRP網(wǎng)絡(luò)報(bào)文負(fù)荷情況Dmessage的最大門限值和最小門限值,DMax和DMin的值可以根據(jù)具體WTRP網(wǎng)絡(luò)的報(bào)文負(fù)荷情況做出調(diào)整。默認(rèn)情況下,DMax=0.5,DMin=0.2;

步驟5 在WTRP網(wǎng)絡(luò)中,Nmax_info_frames:節(jié)點(diǎn)Mi在持有令牌時(shí)能夠發(fā)送的報(bào)文數(shù)目,Nmax_info_frames的值與WTRP網(wǎng)絡(luò)的報(bào)文負(fù)荷情況構(gòu)成分段函數(shù)關(guān)系:Nmax_info_frames=

(5)

步驟6 在WTRP網(wǎng)絡(luò)中,Nmax_pass_times為節(jié)點(diǎn)Mi在傳遞令牌時(shí),能夠?qū)⒘钆苽鬟f給物理上不相鄰的同一個(gè)節(jié)點(diǎn)的最大次數(shù)。默認(rèn)情況下,Nmax_pass_times=1,Nmax_pass_times的值可以根據(jù)WTRP網(wǎng)絡(luò)的最大延時(shí)時(shí)間來設(shè)定。

4 OPNET仿真及性能分析

4.1 仿真環(huán)境的建立

OPNET(Optimized Performance Network Engineering Tool),一種廣泛應(yīng)用的通信與計(jì)算機(jī)網(wǎng)絡(luò)仿真軟件。WTRP網(wǎng)絡(luò)OPNET仿真環(huán)境的建立包括網(wǎng)絡(luò)建模、節(jié)點(diǎn)建模和進(jìn)程建模。由此建立的三層模型和實(shí)際的WTRP網(wǎng)絡(luò)、設(shè)備完全對(duì)應(yīng);通過Packet Editer(包編輯器)建立與WTRP協(xié)議對(duì)應(yīng)的報(bào)文格式,從而全面反映WTRP網(wǎng)絡(luò)的相關(guān)特性。

1) 網(wǎng)絡(luò)建模和節(jié)點(diǎn)建模

WTRP是一個(gè)令牌邏輯環(huán)網(wǎng)絡(luò),拓?fù)浣Y(jié)構(gòu)為令牌環(huán)型,仿真網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目為10。通過Node Editor(節(jié)點(diǎn)編輯器)描述WTRP節(jié)點(diǎn)的層次結(jié)構(gòu),并通過功能模塊之間的數(shù)據(jù)流來實(shí)現(xiàn)WTRP網(wǎng)絡(luò)的體系結(jié)構(gòu),如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)模型

2) 進(jìn)程建模

通過有限狀態(tài)機(jī)進(jìn)行建模,每個(gè)狀態(tài)內(nèi)寫入任意的C/C++代碼以及專門為WTRP協(xié)議設(shè)計(jì)的庫函數(shù),包括WTRP協(xié)議接收幀狀態(tài)機(jī)和節(jié)點(diǎn)狀態(tài)機(jī),用于定義節(jié)點(diǎn)內(nèi)功能模塊中各事件之間的控制流。

4.2 性能評(píng)估的方法

在本文中,通過比較WTRP不同網(wǎng)絡(luò)負(fù)荷下節(jié)點(diǎn)的網(wǎng)絡(luò)吞吐量、平均服務(wù)延時(shí)和報(bào)文丟失率,來判斷該令牌傳遞算法對(duì)網(wǎng)絡(luò)性能是否有所改善。

其中,平均服務(wù)延時(shí)表示通過OPNET中的統(tǒng)計(jì)量表示Node Statistics/Token Ring/Delay(s)來反映;報(bào)文丟失率表示丟失的報(bào)文數(shù)目/所發(fā)送的報(bào)文數(shù)目;網(wǎng)絡(luò)吞吐量表示在單位時(shí)間內(nèi),WTRP網(wǎng)絡(luò)發(fā)送和接收的數(shù)據(jù)量,由OPNET中的統(tǒng)計(jì)量:Node Statistics/Token Ring/Load(bits/s)和Node Statistics/Token Ring/Traffic Received(bits/s)通過計(jì)算得到。

設(shè)WTRP網(wǎng)絡(luò)負(fù)荷為G,G的值:0～1之間,隨著網(wǎng)絡(luò)負(fù)荷的增加而增大:

(6)

其中,Li為節(jié)點(diǎn)Mi發(fā)送報(bào)文的平均長(zhǎng)度;B為數(shù)據(jù)的傳輸速率(bits/s);N為WTRP仿真模型中節(jié)點(diǎn)的數(shù)目;Ti為每個(gè)節(jié)點(diǎn)依據(jù)泊松分布隨機(jī)產(chǎn)生報(bào)文的時(shí)間間隔,Ti為調(diào)整網(wǎng)絡(luò)負(fù)荷G大小的參量。

4.3 仿真結(jié)果分析

利用該OPNET仿真模型一共進(jìn)行了三組實(shí)驗(yàn),通過分析數(shù)據(jù)得到如下實(shí)驗(yàn)結(jié)果:

1) 令牌傳遞算法對(duì)平均服務(wù)延時(shí)的影響

第一組實(shí)驗(yàn):令牌傳遞算法對(duì)平均服務(wù)延時(shí)的影響,如圖2所示。

從圖2可以看出,網(wǎng)絡(luò)負(fù)荷G值越大,各節(jié)點(diǎn)等待發(fā)送的報(bào)文也越多,發(fā)送完報(bào)文需要的時(shí)間也越長(zhǎng)。隨著G值的增加,兩種令牌傳遞算法下的平均服務(wù)延時(shí)均逐漸增大,但在相同的網(wǎng)絡(luò)負(fù)荷下,自適應(yīng)令牌傳遞算法的平均服務(wù)延時(shí)明顯小于順序令牌傳遞算法。

圖2 令牌傳遞算法對(duì)平均服務(wù)延時(shí)的改善

當(dāng)G的值在0.2～0.5之間,該令牌傳遞算法對(duì)平均服務(wù)延時(shí)的改善最為明顯。這是因?yàn)?當(dāng)G的值較小時(shí),報(bào)文分布的值也相應(yīng)變小,令牌只在有報(bào)文需要發(fā)送的節(jié)點(diǎn)之間傳遞;同時(shí),節(jié)點(diǎn)Nmax_pass_times的值增大,需要發(fā)送數(shù)據(jù)越多的節(jié)點(diǎn)占用的網(wǎng)絡(luò)帶寬越大,從而減少了令牌在邏輯環(huán)上空傳的次數(shù);當(dāng)網(wǎng)絡(luò)負(fù)荷G>0.5時(shí),報(bào)文分布的值相應(yīng)變大,節(jié)點(diǎn)Nmax_pass_times的值重新設(shè)置為1,平均服務(wù)延時(shí)逐漸接近順序令牌傳遞算法。

2) 令牌傳遞算法對(duì)報(bào)文丟棄率的改善

第二組實(shí)驗(yàn):令牌傳遞算法對(duì)報(bào)文丟棄率的影響,如圖3所示。

圖3 令牌傳遞算法對(duì)報(bào)文丟棄率的改善

從圖3可以看出,兩種令牌傳遞算法下的報(bào)文丟棄率隨著網(wǎng)絡(luò)負(fù)荷G的增大而增大;當(dāng)G>0.5時(shí),自適應(yīng)令牌傳遞算法的報(bào)文丟棄率增大的速度明顯加快,令牌在基本上邏輯環(huán)上順序傳遞,報(bào)文丟棄率逐漸接近順序令牌傳遞算法。這是因?yàn)?當(dāng)G<0.5時(shí),WTRP網(wǎng)絡(luò)的負(fù)荷比較小,需要發(fā)送報(bào)文的節(jié)點(diǎn)也相對(duì)較少,自適應(yīng)令牌傳遞算法通過動(dòng)態(tài)調(diào)整令牌的傳遞順序,并且改變重節(jié)點(diǎn)Nmax_pass_times的值,使更多的報(bào)文能夠在規(guī)定的時(shí)間以內(nèi)發(fā)送出去,從而降低了報(bào)文丟棄率。

3) 令牌傳遞算法對(duì)網(wǎng)絡(luò)吞吐量的改善

第三組實(shí)驗(yàn):令牌傳遞算法對(duì)網(wǎng)絡(luò)吞吐量的影響,如圖4所示。

從圖4可以看出,當(dāng)G<0.5時(shí),兩種令牌傳遞算法下的網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)負(fù)荷G之間基本上呈線性關(guān)系;當(dāng)G>0.5時(shí),網(wǎng)絡(luò)吞吐量增長(zhǎng)的速度逐漸降低。自適應(yīng)令牌傳遞算法網(wǎng)絡(luò)吞吐量降低的速度明顯小于順序令牌傳遞算法。這是因?yàn)?網(wǎng)絡(luò)負(fù)荷G越大,報(bào)文丟棄率也越大,當(dāng)報(bào)文丟棄率增大的速度大于網(wǎng)絡(luò)負(fù)荷G增大的速度時(shí),網(wǎng)絡(luò)吞吐量開始減少。因?yàn)樽赃m應(yīng)算法下的報(bào)文丟棄率優(yōu)于順序令牌傳遞算法,所以自適應(yīng)算法下網(wǎng)絡(luò)吞吐量降低的速度明顯小于順序令牌傳遞算法。

圖4 令牌傳遞算法對(duì)網(wǎng)絡(luò)吞吐量的改善

5 結(jié)語

基于WTRP協(xié)議的自適應(yīng)令牌傳遞算法,通過改變令牌在邏輯環(huán)上的傳遞順序和節(jié)點(diǎn)在持有令牌時(shí)發(fā)生報(bào)文的數(shù)目,解決了原有WTRP協(xié)議中令牌只能固定順序傳遞的問題,從而使整個(gè)網(wǎng)絡(luò)的令牌傳遞和帶寬分配更加合理。OPNET軟件仿真結(jié)果表明,該算法減少了WTRP網(wǎng)絡(luò)的報(bào)文平均服務(wù)延時(shí),降低了報(bào)文丟失率,提高了網(wǎng)絡(luò)吞吐量。

[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] 孫獻(xiàn)璞,張艷玲.一種新的令牌傳遞算法[J].西安郵電學(xué)院學(xué)報(bào),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] 孫獻(xiàn)璞,張艷玲,宋彬.采用動(dòng)態(tài)令牌的MANET多址接入?yún)f(xié)議[J].電子學(xué)報(bào),2006,34(1):118-122.

[6] 陳敏.OPNET網(wǎng)絡(luò)仿真[M].北京:清華大學(xué)出版社,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] 張艷玲,宋彬.采用動(dòng)態(tài)令牌的MANET多址接入?yún)f(xié)議[J].電子學(xué)報(bào),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