基于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