短波令牌環協議組網算法的改善＊

（武漢船舶通信研究所 武漢 430205）

1 引言

隨著信息時代的飛速發展，短波組網通信的研究與應用越來越重要。我們知道短波具有電離層反射的傳輸特性［2］，因此短波通信可以不使用任何中繼器就能在超視距的范圍內通信，這是其它任何頻段都無法做到的。當前就國內外短波通信發展來看，國內的院校及科研院所均在開展短波通信組網的研發工作，希望實現短波通信向著網絡通信一體化的方向發展，通過使用發展成熟的TCP／IP協議族構建短波IP 網絡，采用IP 協議將其與地面InterNet網絡及衛星網絡統一起來，組成信道多元化的聯合高頻廣域網。例如，美軍在短波無線通信網絡中，引入NATO（北約組織）的STANAG 5066［3］標準實現海軍艦對艦及艦對空的電子郵件的傳輸。

STANAG 5066 標準定義了一個典型的短波IP網絡，實現了OSI七層模型中的物理層、數據鏈路層及部分網絡功能。STANAG 5066 標準對HFCSMA、HFTDMA 和HFTRP［4］協議分別進行了闡述。但是由于CSMA 對帶寬資源利用率不高，這樣，CSMA 在帶寬資源本來就有限的短波組網通信中的應用受到極大限制。同時因為在短波無線通信中，時間同步存在很大問題，TDMA 也不太適合短波通信［5］，目前STANAG 5066標準還沒有實現HFTDMA 協議。而短波令牌環是無競爭的組網協議，頻帶利用率高，提供QoS［6］。然而由于短波信道的特性，令牌環的組網和維護仍然是令牌環協議的關鍵問題［7］。本文將著重討論令牌環協議的組網算法問題。

2 短波令牌環協議

1）協議概述

短波令牌環屬于無競爭模式MAC 層組網協議，通過建立邏輯令牌環實現對短波信道資源的使用和管理。令牌環上每個節點都知道自己的前驅節點和后繼節點，當節點收到前驅節點的令牌后，開始在規定的時間內發送數據，然后再將令牌傳遞給它的后繼節點。如果節點發送數據的時間超出規定的時間長度，則被迫終止發送數據，而將令牌傳向其后繼節點。依次類推，同一令牌環上的節點按照接收令牌的次序，輪流使用同一個短波信道［8～9］。一旦邏輯令牌環建立起來，環上節點在規定的令牌持有時間內按照令牌傳遞的順序發送數據。令牌環上每個節點享有同等帶寬和發送權，不存在競爭和沖突，同時降低了節點接入的等待時延，提高了信道利用率。

2）令牌環組網流程

短波令牌環是自組織的，當一個節點激活后，會在某個指定的頻率上監聽一段時間（定時器A），這段時間它不會有任何動作，除非它收到其它節點的邀請入環令牌（Solicit successor token，SLS），此時它會發送設置后繼令牌（Set successor token，SET）進行響應，或者監聽到有激活的令牌環存在（即收到了一個從激活令牌環發出的令牌或者數據），節點會重新啟動定時器等待SLS令牌。當定時器A 超時時，它還沒有監聽到任何信息，節點會聲明自己為環主，向外廣播SLS令牌，其他節點收到SLS令牌后，可發送SET 令牌進行響應。有限的初始情況包含兩個均在SFR（selfring，自愈環）狀態的節點，沒有一個激活的環。通常情況下，每個節點都會產生SLS 令牌，然后進入SEK（seeking，搜索）狀態。然而，它們的發送是異步和隨機的，因為它們的啟動的時刻是隨機的。可以假定，一個節點首先監聽到了其它節點的發送，進入了JON（join，加入）狀態。當入網節點通過發送SET令牌響應SLS令牌，并且也接收到了有權發送令牌（RTT，right to transmit）后，兩個節點的環就創建了。具體組網流程如圖1、圖2所示。

圖1 A、B節點組網過程

圖2 C、D 節點入網過程

組網過程中可能會產生沖突，從而影響組網的效率。如圖1中，當A 節點發出SLS 令牌后，B、C、D可能同時響應，發送SET 令牌，這時候B、C、D發出的令牌產生沖突，A 本次邀請入環流程失敗。顯然沖突的次數越多，組網的效率就會越低。所以要提高組網的效率，關鍵是降低沖突發生的概率［10］。

3 短波令牌環組網算法分析及改進

1）現有令牌環組網算法

當前令牌環組網算法的響應機制采取的是隨機退避策略。當一個節點監聽到其他節點的SLS令牌，它會先進入到SRP（solicit reply，隨機響應退避）狀態，以減少有多個節點同時對其進行響應而產生沖突的情況。節點在SRP 等待的時間是隨機的（0～3個時隙），一旦這段時間內監聽到有其他節點發出SET 令牌，自己就放棄本次加入的機會，退回游離狀態（FLT）繼續監聽，等待下一次的加入機會。當節點加入失敗的次數超過三次，則下一次等待的時間往后延長三個時隙，依次類推，可將沖突的概率逐漸降低，最終使所有節點都能加入。

（1）主動邀請節點處理流程

主動邀請節點的處理流程如圖3所示。

圖3 主動邀請節點狀態轉移圖

狀態轉移圖說明：

①節點在SFR 狀態狀態開啟TSLS 定時器。在定時器時間內監聽到其他節點的SLS 令牌，進入SRP狀態；監聽到有激活的環存在（收到非SLS令牌），進入FLT 狀態等待被邀請；否則定時器超時的時候，發送SLS令牌邀請其他節點加入令牌環網，進入SEK 狀態，等待響應。

②節點在SEK 狀態開啟TSLW 定時器。在定時器時間內收到SET 令牌，則發送RTT 令牌給新加入節點，進入PAR（paring，匹配）狀態，等待確認信息；如果監聽到有其他激活的環存在（收到SLS和SET 以外的令牌），進入FLT 狀態等待被邀請；否則在定時器超時后回到SFR 狀態。

③節點在PAR 狀態開啟TPST 定時器。在定時器范圍內收到新加入節點的確認信息，則表示本次邀請成功；否則表示邀請失敗，回到FLT 狀態。

（2）新加入節點處理流程

新加入節點的處理流程如圖4所示。

圖4 新加入節點狀態轉移圖

狀態轉移圖說明：

①節點在FLT 狀態開啟TCLT 定時器。FLT狀態監聽到有激活的環存在（收到非SLS 令牌），重啟定時器，保持在FLT 狀態；監聽到SLS令牌，進入SRP狀態等待加入令牌；否則在定時器超時后進入SFR 狀態。

②節點在SRP狀態開啟TSRP定時器。如果在定時器時間內監聽到其他節點發送的SET 令牌，則取消本次加入，進入FLT 狀態，加入失敗次數加1；否則在退避時間超時后發送SET 令牌，進入JON 狀態。

③節點在JON 狀態開啟TCON 定時器。如果定時器內收到了邀請節點發送給自己的RTT 令牌，則表示入環成功，回復確認信息；否則，定時器超時仍未收到RTT 令牌，則表示本次加入失敗，回到FLT 狀態，等待下次加入。

2）現有算法分析

現有加入策略可以實現令牌環組網的功能，而且在節點激活間隔時間較大的時候，效率比較高。但是當節點較多且所有節點激活間隔時間比較小（極端情況是同時激活），因為隨機時隙個數少，沖突比較大，令牌環組網的效率就會大大降低。本文將針對這一情況，對令牌環組網的響應加入算法進行改善，使得令牌環協議在節點較多、激活間隔時間較小的情況下也能有比較好的性能。

3）改進算法的思路

現有組網算法主要是由于隨機退避的時隙個數比較小，所以我們的思路是利用令牌中攜帶的信息，動態規劃時隙個數。由于在我們的應用場景中，最大規劃節點數是已知的，而且令牌中攜帶有當前環內節點數，所以把時隙個數修改為如下：

時隙個數＝最大規劃節點數-當前環內節點數

這樣在節點數較多，開機時間間隔較小的時候（即使是同時開機），因為時隙個數的增多，沖突的概率就減小了很多，理想情況是每個節點都能分到一個唯一的時隙，這種情況下是沒有沖突的。同時也隨著節點不斷的加入環，時隙個數也跟著減小，后續加入節點的退避等待時間也不會因此增加很多，沖突的概率仍舊比較小。

4 仿真結果

1）仿真參數

（1）Turnaround time 1．04s；

（2）信道為全連通；

（3）仿真平臺為EXATA 仿真軟件。

2）仿真結果

在仿真的時候，針對最大規劃節點數分別為4、6、8、12、16的情況進行了仿真，節點激活的最大時間間隔由0逐步增大到（4＊最大規劃節點數）s，每個節點激活的時機是隨機的。仿真結果見表1和表2。

（1）現有算法組網時間仿真結果

表1 現有算法組網時間仿真結果（s）

2）算法改進后組網時間仿真結果（s）

表2 算法改進后組網時間仿真結果（s）

5 結語

本文針對現有令牌環組網算法進行了分析，針對現有算法在節點較多且激活間隔時間較短的時候組網效率較差的情況進行了改善，提出了動態規劃時隙的算法，并對改進后的算法進行了仿真。依據仿真結果可知，與理論分析的結果基本相符，改善后的算法在總體上比現有算法的組網效率要高，而且在間隔時間逐步變大的過程中組網時間也比較平穩。特別是節點數大于8時，組網效率有較大的改善。在實際環境的測試時，針對4個節點進行了測試（由于設備及其他條件有限，只能對4個點進行測試），改善后的組網算法時間大概是60s～80s之間，與仿真結果基本吻合，因此該算法可用于實踐。

［1］Johnson E E，Tang Z，Balakrishnan M，et al．Robust token management for unreliable networks［C］／／Military Communications Conference，IEEE，2003，1：399-404．

［2］McGhee J，Grimble M J，Mowforth P．HF radio sys-tems and techniques［J］．IEEE REVIEW，1992：195．

［3］NATO Standardization Agreement 5066：Profile for High Frequency（HF）Radio Data Communications，version 1．2［S］，NATO Standardization Activity reference 0114-C3．

［4］NATO Standardization Agreement 5066，Profile for High Frequency（HF）Radio Data Communications Version 1．2［S］，Annex L-High-Frequency Wireless Token Ring Protocol（HFTP）Requirements，Edition 2，Draft 1，NATO C3Agency，June 2004．

［5］Hong Y K，Miller，D．Performance of CSMA and TDMA protocols for break-in channel access in a frequency hopping（FH）narrowband high frequency（HF）blocked channel environment［C］／／Military Communications Conference IEEE，1993，3：763-767．

［6］E．E．Johnson，M．Balakrishnan，Z．Tang．Impact of Turnaround Time on Wireless MAC Protocols［C］／／Proceedings of MILCOM 2003，Boston，MA，2003，1：375-381．

［7］Johnson，E．E．，Tang，Z．，Balakrishnan，M．Token relay with optimistic joining［C］／／Military Communications Conference，2005．IEEE，2005：2216-2222．

［8］Ergen M，Lee D，Sengupta R，et al．WTRP-wireless token ring protocol［J］．Vehicular Technology，IEEE Transactions on，2004，53（6）：1863-1881．

［9］Xianpu S，Yanling Z，Jiaodong L．Wireless dynamic token protocol for MANET［C］／／Parallel Processing Workshops，2007．ICPPW 2007．International Conference on．IEEE，2007：5．

［10］Balakrishnan M，Johnson E E．Queueing analysis of DCHF and token-passing protocols with varying turnaround time［C］／／Performance，Computing，and Communications，2004 Internationl Conference on．IEEE，2004：315-316．