令牌傳遞順序表優化研究

曾曦 李遲生 溫洋

摘 ?要： 在短波無線令牌環中，合適的令牌傳遞順序表能有效減少令牌中繼次數，降低令牌傳遞時間，提高服務質量（QoS）。傳統基于中繼的組網方法使一些病狀拓撲也能組網成功。但在組網時，若環外節點可與令牌環內令牌傳遞順序表中相鄰兩個節點相互通信，會因為邀請節點的不同導致節點加入后的令牌傳遞順序表中需要不必要的中繼。文中針對非必要中繼傳遞的令牌傳遞順序表采用最近插入法，重組優化令牌傳遞順序表，最大化減少令牌中繼次數，仿真結果表明該算法能有效解決不必要多次中繼問題。

關鍵詞： 令牌傳遞順序表; 最近插入法; 中繼; 短波令牌環; 服務質量; 多址接入

中圖分類號： TN915?34 ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）15?0001?04

Research on optimization of token passing sequence table

ZENG Xi， LI Chisheng， WEN Yang

（School of Information Engineering， Nanchang University， Nanchang 330031， China）

Abstract： In the short wave wireless token ring， an appropriate token transmit?order?list （TOL） can reduce the number of token relays and token passing time， and improve QoS. The traditional networking method based on token relay can also make some pathological topologies network successfully. However， if the node outside the ring can communicate with the two adjacent nodes in TOL during networking， the unnecessary relay will be needed in token TOL after node is inserted because the invited node is different. The nearest insertion method is used in allusion to the token TOL for the unnecessary relay transmission to regroup and optimize the token TOL， which can reduce the quantity of the token relay. The simulation results show that the algorithm can effectively eliminate unnecessary repeated relay.

Keywords： TOL; recent insertion method; relay; high frequency token ring; service quality; multi?access

0 ?引 ?言

近年來，信息技術飛速發展，短波網絡通信的研究和應用也越來越重要。短波通信是通過電離層的反射實現遠距離通信[1]，由于電離層的高度和密度隨著時間、氣候的變化而變化，最終使短波通信出現多徑時延、信號衰落和多普勒頻移等情況。故在短波網絡通信中采用合適的媒體訪問控制（Multi?access，MAC）協議來保證較好的服務質量（Quality of Service，QoS）是至關重要的[2]。

基于競爭機制的MAC協議由于競爭和沖突的存在，無法徹底解決隱藏終端和暴露終端[1]的問題，無法提供較好的QoS，也無法保證信道訪問的公平性。非競爭MAC協議中無線令牌環協議（Wireless Token Ring Protocol，WTRP）能為時延要求高的業務提供固定QoS保證，其信道利用率在網絡規模和流量較大的情況下明顯高于競爭型MAC協議，故在一些無線網絡中得到廣泛應用[3?5]。基于短波通信系統的特點，使令牌的傳遞周期時間較長，故在令牌傳遞過程中出現問題需要有機制及時恢復。短波令牌環協議（High Frequency Token Ring Protocol，HFTRP）是在WTRP的基礎上加上令牌中繼機制，在令牌丟失時采用中繼令牌來完成對目的節點令牌的中繼傳遞[6?7]。克服了WTRP在令牌丟失問題上消極被動的缺點，更適合于短波無線通信。

由于短波通信中網絡成員所處范圍廣、相互距離遠、節點發射功率有限，導致實際短波通信網絡存在部分節點僅能與特定對象通信，網絡呈現“病態拓撲”[8]。文獻[9]針對該問題采用“請求后繼”機制完成節點入網過程。但是這將會引起不必要的中繼，從而增加令牌的傳輸時間。

1 ?短波令牌環基本原理

1.1 ?協議概述

短波令牌協議是一種無競爭機制的MAC協議，它通過令牌來控制節點媒介訪問的公平性。令牌環在組網后存儲一個傳遞順序表（Transmit?Order?List，TOL）：如節點A，B，C，D組成令牌環，B是A的后繼節點，C是B的后繼節點，D是C的后繼節點，A是D的后繼節點，則TOL為A→B→C→D→A，令牌則按照TOL依次傳遞。每個節點記錄自己的前驅節點和后繼節點，當節點接到來自前驅節點RTT令牌，若節點有信息發送則將信息發出，若沒有信息發送則直接將RTT令牌傳給自己的后繼節點。協議同時規定了節點發送信息的最大時間，若節點在最長時間內信息沒有發送完，節點被迫將傳輸權（Right to Transmit，RTT）令牌傳出。令牌環內節點按照設定好的TOL傳遞，輪流使用同一個信道。保證每個節點都享有同等帶寬和發送權，避免了競爭和沖突，降低節點接入時延，提高信道利用率。

1.2 ?中繼機制組網過程

傳統令牌環組網過程中，要求等待加入的節點要同時在其將要加入環的前驅節點和后繼節點的通信范圍內。由于在實際短波通信網絡中，節點分布范圍廣，相互距離遠，節點的發射功率有限，導致部分節點僅能與特定的幾個環內節點通信。若某些節點只能與令牌環中的一個節點通信將無法進入環內。針對這個問題，文獻[9]提出基于中繼機制的組網方法。該方法中不要求等待加入節點要在其將來的后繼節點的通信范圍內。在組網成功后，該節點可以通過中繼令牌將令牌傳輸給其后繼節點。

以下簡介中繼機制組網過程。其中節點A與節點C之間不能相互通信，節點B可分別與節點A和節點C相互通信。

節點啟動后直接進入浮動狀態（Floating State，FLT），開啟定時器timer1，并監聽信息。若節點啟動后一直沒有監聽到任何信息，則在定時器timer1超時后，節點會申明自己為自環，即只有自己一個節點的環，環路主節點為自己，并進入自環狀態（Self Ring State，SRS）。自環節點會發出令牌邀請（Solicit Successor Token，SLS）自己通信范圍內的節點入網。在發出SLS令牌后，節點轉入尋求狀態（Seeking State，SEK）來等待其他節點回復的設置后繼節點令牌（Set Successor Token，SET）。當節點收到SET令牌后，從收到的所有SET令牌中隨機選取一個節點作為自己的后繼節點。節點轉入持有令牌狀態（Have?Token State，HVT），并將RTT令牌傳輸給新的后繼節點。此時邀請環外節點入環的過程完成。

其他節點處于FLT狀態時，在未超時接收到其他信息則不做任何反應，若收到其他節點的SLS令牌，則節點將本節點地址加入到TOL中邀請節點的后繼節點位置，設置SET后回復給邀請節點。之后節點轉入加入狀態（Joining State，JON）等待RTT令牌。若節點收到來自前驅節點的RTT令牌，則說明節點加入令牌環的過程完成。圖1為自環邀請新節點加入令牌環。

圖1 ?自環邀請節點過程

當節點收到SLS令牌后，由于可能存在多個等待加入令牌環的節點，節點會選擇一個隨機的時隙來發送SET，以減少與其他回復SLS令牌節點間的碰撞。

當節點在SFR狀態下，發送的SLS令牌中將設置自己的后繼節點為將要加入節點的新后繼節點。當等待加入節點收到SLS令牌，傳統的組網機制會要求等待加入節點檢查自己是否在新的后繼節點的通信范圍內，若在通信范圍內才回復SET令牌，若不在則不能加入令牌環。而在基于中繼機制的組網情況下，等待加入節點不需檢查這項內容，可直接加入令牌環。若入網后，該節點不能直接將RTT令牌傳給其后繼節點，則可通過中繼將令牌傳出。如圖2所示，節點A與B組網后，節點B邀請節點C加入令牌環時將A設置為C新的后繼節點，而A不在C的通信范圍內，則在C加入令牌環后，節點C通過給B發中繼令牌最終將令牌傳給A而完成令牌的傳輸。

圖2 ?中繼機制組網過程

2 ?問題分析

基于中繼的組網方式會引起一些問題。如等待加入的節點與環內順序列表上相鄰的兩個以上節點都可以相互通信，這種情況下最優的TOL應該是將等待加入的節點插入到這兩個節點之間，但現實中會因為邀請加入的節點不同導致該節點插入到TOL中的其他位置，導致該節點需要通過中繼將令牌傳給其后繼節點。而組網成功后，該TOL在沒有意外情況下是不會改變的，則該節點將一直要執行這個不必要的中繼。

以4個節點為例。節點A能與節點B，D通信，節點B能與節點A，C通信，節點C能與節點B，D通信，節點D能與節點A，C通信。A，B，C組網后，會在適當的時候邀請節點D加入令牌環。節點D只能接收到節點A，C的信息，故只有當節點A和節點C發出邀請時，節點D能接收到邀請信息。

若由節點A邀請節點D加入令牌環時，節點A設置節點D的新后繼節點為節點B，故節點D加入環后，其組網后令牌傳遞如圖3所示。令牌的TOL為A→D→B→C→A，其中，節點D不能與節點B直接通信，節點C不能與節點A直接通信，這就有兩個節點需要經過中繼將令牌傳輸給它們的后繼節點。這種情況則引起兩次不必要的中繼。

圖3 ?節點A邀請節點D入環

以8個節點為例。節點A，B，C，D首先組成令牌環，其中節點E與節點A，B可相互通信，節點H可與節點B，C相互通信，節點G可與節點D，C相互通信，節點F可與節點A，D相互通信。節點B邀請節點E加入令牌環，則E不能到達其后繼節點C，需通過中繼;節點C邀請節點H加入令牌環，則節點H不能直接到達其后繼節點D，節點A邀請節點F入環，則節點F不能直接到達其后繼節點B，則整個令牌環路中需要經過4次中繼。其TOL為：A→F→B→E→C→H→D→G→A，其令牌傳遞如圖4所示。

3 ?令牌環傳遞順序優化

最近插入法是用于解決旅行商問題（Traveling Salesman Problem，TSP）的一種構造型算法[10?11]。具體的算法描述如下：

假設環路總共有[N]個節點。距離矩陣DM是一個[N×N]型矩陣，其值由每個節點與其他節點間最短距離[disti，j]（相同節點之間[disti，i=0]，不同節點間能直接通信則為1，若不能直接通信需要中繼的則為1+需要中繼次數）組成;環路周期長度RCL=[dist0，1]+[dist1，2]+…+[distN-1，0];添加節點后環路周期增加長度ΔRCL=[disti，j]+[distj，i+1]-[disti，i+1]。節點插入令牌環的過程如圖5所示。

圖4 ?基于中繼機制組網令牌傳遞順序

圖5 ?節點[j]插入令牌環過程

具體步驟如下：

1） 在邀請新的節點加入后可判斷環路周期長度RCL是否等于環內節點數[N]，若RCL>[N]，則采用最近插入法將新加入的節點插入到合適的位置。若RCL=[N]，則說明環內無需中繼傳輸，則保持TOL不變。

2） 確定要重新插入令牌環的節點，TOL列表中相鄰節點不能直接通信的節點，前驅節點到后繼節點的最短距離不為1的節點。取出需要重新插入節點，假設需優化節點數為[k]，則環內剩余節點數為[N-k]。

3） 取出一個待插入節點[j]，在DM矩陣中找出該節點與令牌環內所有節點的距離，并選出離該節點最近的節點[m，n，…]。

4） 將節點[j]插入到TOL中節點[m]與其后繼節點[m+1]之間，計算添加節點[j]之后RCL的增加值ΔRCL[（m，m+1）]。

5） 重復步驟4），將節點[j]插入到剩余其他離該節點最近的節點與其后繼節點之間，計算對應的添加節點[j]之后RCL的增加值。

6） 比較所有ΔRCL，選出產生最小ΔRCL的位置，將節點[j]插入到該處。

7） 重復步驟2）～步驟6），直到所有節點均加入令牌環路中。

4 ?仿真結果

本文在Matlab仿真平臺上進行仿真。對4，6，8，10，12個節點進行仿真分析，4節點（A，B，C，D）網絡中設置節點A可與節點B，D通信，不能與節點C通信，節點B可與節點A，C通信，不能與節點D相互通信。依次開啟節點A、節點B，待節點A，B組網后開啟節點C，待節點C入網后開啟節點D。6，8，10，12節點網絡設置：假設節點數為[N]，節點排成圓形，節點標號按順時針依次排號為1，2，…，[N]，其中，奇數節點可與其相鄰的奇數節點通信;偶數節點只能與相鄰的奇數節點通信，不能與其相鄰的偶數節點通信。節點開啟順序，首先按順時針方向依次開啟兩個奇數節點，待它們組網后再開啟之后的奇數節點，直到所有奇數節點組網后，再按順時針順序依次開啟偶數節點，直到所有節點組網成功。經過多次仿真實驗得到結果如表1所示。

表1 ?中繼情況仿真結果

5 ?結 ?語

針對傳統基于中繼機制的組網方法會導致生成的TOL需要使用不必要的中繼，導致節點傳輸令牌的時間增長。本文采用最近插入法將需要中繼的節點插入到合適的傳遞順序中，以減少不必要令牌中繼次數。實驗結果表明，節點越多時，在節點只能與鄰近節點相互通信的情況下，可能導致中繼次數越多。本文中的優化TOL算法能很好地解決該問題，最大化減少令牌環中中繼的次數。針對多個節點令牌環網絡也能很好地解決問題。

參考文獻

[1] HOSSEINABADI Ghazale， VAIDYA Nitin. Token?DCF an opportunistic MAC protocol for wireless network [J]. IEEE communication systems and networks， 2013， 1（1）： 1?9.

[2] YIGITBASI N， BUZLUCA F. A control plane for prioritized real?time communications in wireless token ring networks [J]. IEEE computer and information sciences， 2008， 10（4）： 1?6.

[3] 何敏，趙東風，劉心松.移動Ad Hoc網絡分布式并行接入控制協議分析[J].系統工程與電子技術，2007，29（3）：443?448.

HE Min， ZHAO Dongfeng， LIU Xinsong. Analysis of distributed parallel access control protocol in mobile Ad Hoc networks [J]. Journal of systems engineering and electronics， 2007， 29（3）： 443?448.

[4] 張宇眉，張欣，楊大成，等.基于等待時間和信道狀態的輪詢多址協議[J].北京郵電大學學報，2008，31（4）：126?129.

ZHANG Yumei， ZHANG Xin， YANG Dacheng， et al. Polling multiple access protocol on the waiting time and channel state [J]. Journal of Beijing University of Posts and Telecommunications， 2008， 31（4）： 126?129.

[5] SUN Xianpu， ZHANG Yanling， LI Jiandong. Wireless dynamic token protocol for MANET [C]// Proceedings of 2007 ICPPW. Xian： [s.n.]， 2007： 5?10.

[6] ERGEN M， LEE D， SENGUPTA R， et al. WTRP ? wireless token ring protocol [J]. IEEE transactions on vehicular technology， 2004， 53（6）： 1863?1881.

[7] NATO. Profile for HF Radio Data Communications： STANAG 5066—2015 [S]. Brussels： NATO， 2015： 3.

[8] 賀驍，李曼，白翔，等.短波令牌環協議的研究現狀與發展[J].通信技術，2014（10）：1167?1172.

HE Xiao， LI Man， BAI Xiang， et al. Research status and development of high frequency token ring protocol [J]. Journal of communication technology， 2014（10）： 1167?1172.

[9] JOHNSON E E， TANG Z， BALAKRISHNAN M. Token relay with optimistic joining [J]. IEEE MILCIM， 2005， 4（2）： 2216?2222.

[10] 馬良.旅行推銷員問題的算法綜述[J].數學的實踐與認識，2000，30（2）：156?165.

MA Liang. An overview of the algorithm for traveling salesman problem [J]. Journal of mathematics in practice and theory， 2000， 30（2）： 156?165.

[11] 朱麗娟，徐小明，夏必勝.SOFM神經網絡最近插入法混合算法在TSP問題中應用研究[J].貴州大學學報（自然版），2009，26（6）：21?23.

ZHU Lijuan， XU Xiaoming， XIA Bisheng. Application of SOFM neural network nearest insertion hybrid algorithm in TSP problem [J]. Journal of Guizhou University （Natural edition）， 2009， 26（6）： 21?23.