短波令牌環(huán)協(xié)議組網(wǎng)算法的改善＊

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

1 引言

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

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

2 短波令牌環(huán)協(xié)議

1）協(xié)議概述

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

2）令牌環(huán)組網(wǎng)流程

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

圖1 A、B節(jié)點組網(wǎng)過程

圖2 C、D 節(jié)點入網(wǎng)過程

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

3 短波令牌環(huán)組網(wǎng)算法分析及改進

1）現(xiàn)有令牌環(huán)組網(wǎng)算法

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

（1）主動邀請節(jié)點處理流程

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

圖3 主動邀請節(jié)點狀態(tài)轉移圖

狀態(tài)轉移圖說明：

①節(jié)點在SFR 狀態(tài)狀態(tài)開啟TSLS 定時器。在定時器時間內(nèi)監(jiān)聽到其他節(jié)點的SLS 令牌，進入SRP狀態(tài)；監(jiān)聽到有激活的環(huán)存在（收到非SLS令牌），進入FLT 狀態(tài)等待被邀請；否則定時器超時的時候，發(fā)送SLS令牌邀請其他節(jié)點加入令牌環(huán)網(wǎng)，進入SEK 狀態(tài)，等待響應。

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

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

（2）新加入節(jié)點處理流程

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

圖4 新加入節(jié)點狀態(tài)轉移圖

狀態(tài)轉移圖說明：

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

②節(jié)點在SRP狀態(tài)開啟TSRP定時器。如果在定時器時間內(nèi)監(jiān)聽到其他節(jié)點發(fā)送的SET 令牌，則取消本次加入，進入FLT 狀態(tài)，加入失敗次數(shù)加1；否則在退避時間超時后發(fā)送SET 令牌，進入JON 狀態(tài)。

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

2）現(xiàn)有算法分析

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

3）改進算法的思路

現(xiàn)有組網(wǎng)算法主要是由于隨機退避的時隙個數(shù)比較小，所以我們的思路是利用令牌中攜帶的信息，動態(tài)規(guī)劃時隙個數(shù)。由于在我們的應用場景中，最大規(guī)劃節(jié)點數(shù)是已知的，而且令牌中攜帶有當前環(huán)內(nèi)節(jié)點數(shù)，所以把時隙個數(shù)修改為如下：

時隙個數(shù)＝最大規(guī)劃節(jié)點數(shù)-當前環(huán)內(nèi)節(jié)點數(shù)

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

4 仿真結果

1）仿真參數(shù)

（1）Turnaround time 1．04s；

（2）信道為全連通；

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

2）仿真結果

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

（1）現(xiàn)有算法組網(wǎng)時間仿真結果

表1 現(xiàn)有算法組網(wǎng)時間仿真結果（s）

2）算法改進后組網(wǎng)時間仿真結果（s）

表2 算法改進后組網(wǎng)時間仿真結果（s）

5 結語

本文針對現(xiàn)有令牌環(huán)組網(wǎng)算法進行了分析，針對現(xiàn)有算法在節(jié)點較多且激活間隔時間較短的時候組網(wǎng)效率較差的情況進行了改善，提出了動態(tài)規(guī)劃時隙的算法，并對改進后的算法進行了仿真。依據(jù)仿真結果可知，與理論分析的結果基本相符，改善后的算法在總體上比現(xiàn)有算法的組網(wǎng)效率要高，而且在間隔時間逐步變大的過程中組網(wǎng)時間也比較平穩(wěn)。特別是節(jié)點數(shù)大于8時，組網(wǎng)效率有較大的改善。在實際環(huán)境的測試時，針對4個節(jié)點進行了測試（由于設備及其他條件有限，只能對4個點進行測試），改善后的組網(wǎng)算法時間大概是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．