曾曦 李遲生 溫洋

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

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

中圖分類號： 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 ?引 ?言

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

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

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

1 ?短波令牌環(huán)基本原理

1.1 ?協(xié)議概述

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

1.2 ?中繼機制組網(wǎng)過程

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

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

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

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

圖1 ?自環(huán)邀請節(jié)點過程

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

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

圖2 ?中繼機制組網(wǎng)過程

2 ?問題分析

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

以4個節(jié)點為例。節(jié)點A能與節(jié)點B，D通信，節(jié)點B能與節(jié)點A，C通信，節(jié)點C能與節(jié)點B，D通信，節(jié)點D能與節(jié)點A，C通信。A，B，C組網(wǎng)后，會在適當?shù)臅r候邀請節(jié)點D加入令牌環(huán)。節(jié)點D只能接收到節(jié)點A，C的信息，故只有當節(jié)點A和節(jié)點C發(fā)出邀請時，節(jié)點D能接收到邀請信息。

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

圖3 ?節(jié)點A邀請節(jié)點D入環(huán)

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

3 ?令牌環(huán)傳遞順序優(yōu)化

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

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

圖4 ?基于中繼機制組網(wǎng)令牌傳遞順序

圖5 ?節(jié)點[j]插入令牌環(huán)過程

具體步驟如下：

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

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

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

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

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

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

7） 重復步驟2）～步驟6），直到所有節(jié)點均加入令牌環(huán)路中。

4 ?仿真結果

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

表1 ?中繼情況仿真結果

5 ?結 ?語

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

參考文獻

[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網(wǎng)絡分布式并行接入控制協(xié)議分析[J].系統(tǒng)工程與電子技術，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] 張宇眉，張欣，楊大成，等.基于等待時間和信道狀態(tài)的輪詢多址協(xié)議[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] 賀驍，李曼，白翔，等.短波令牌環(huán)協(xié)議的研究現(xiàn)狀與發(fā)展[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].數(shù)學的實踐與認識，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神經(jīng)網(wǎng)絡最近插入法混合算法在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.