楊 斌 任 平 劉 義

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

?

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

楊 斌1任 平2劉 義2

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

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

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

Class Number TP301.6

1 引言

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

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

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

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

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

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

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

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

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

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

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

(1)

T0=781.25ms;

當(dāng)采用自適應(yīng)令牌傳遞方式時,Nmax_info_frame的值隨著報文的分布情況而動態(tài)改變,N1～N9發(fā)送完所有數(shù)據(jù)幀所需的時間為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é)點的報文負(fù)荷情況為Dmessage,Dmessage:單個令牌傳遞周期內(nèi),有數(shù)據(jù)發(fā)送的節(jié)點在所有節(jié)點中所占的比例:

(4)

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

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

(5)

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

4 OPNET仿真及性能分析

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

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

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

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

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

2) 進(jìn)程建模

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

4.2 性能評估的方法

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

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

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

(6)

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

4.3 仿真結(jié)果分析

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

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

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

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

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

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

2) 令牌傳遞算法對報文丟棄率的改善

第二組實驗:令牌傳遞算法對報文丟棄率的影響,如圖3所示。

圖3 令牌傳遞算法對報文丟棄率的改善

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

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

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

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

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

5 結(jié)語

基于WTRP協(xié)議的自適應(yīng)令牌傳遞算法,通過改變令牌在邏輯環(huán)上的傳遞順序和節(jié)點在持有令牌時發(fā)生報文的數(shù)目,解決了原有WTRP協(xié)議中令牌只能固定順序傳遞的問題,從而使整個網(wǎng)絡(luò)的令牌傳遞和帶寬分配更加合理。OPNET軟件仿真結(jié)果表明,該算法減少了WTRP網(wǎng)絡(luò)的報文平均服務(wù)延時,降低了報文丟失率,提高了網(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é)報,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)璞,張艷玲,宋彬.采用動態(tài)令牌的MANET多址接入?yún)f(xié)議[J].電子學(xué)報,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] 張艷玲,宋彬.采用動態(tài)令牌的MANET多址接入?yún)f(xié)議[J].電子學(xué)報,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