李程文 李遲生 林夢思 吳小晴

摘? 要： 短波令牌環(huán)分布式自組織和無競爭機制有效避免了短波數(shù)據(jù)通信訪問沖突問題，為短波通信提供良好的多址接入方式。針對短波令牌環(huán)中可能存在不必要中繼節(jié)點產(chǎn)生的令牌開銷影響網(wǎng)絡吞吐量和時延等問題，轉化為求解整個短波令牌環(huán)最優(yōu)傳輸順序表，提出Floyd和遺傳算法聯(lián)合算法對短波令牌環(huán)傳輸順序進行優(yōu)化。結果顯示優(yōu)化后的傳輸順序表減少了不必要的中繼次數(shù)，驗證了算法優(yōu)化短波令牌環(huán)傳輸順序的有效性，并與單獨使用Floyd算法或遺傳算法進行對比，顯示聯(lián)合算法優(yōu)化效果更好。通過分析表明，使用聯(lián)合算法對短波令牌環(huán)傳輸順序進行優(yōu)化提升了網(wǎng)絡吞吐量，減小了網(wǎng)絡數(shù)據(jù)傳輸時延。

關鍵詞： 短波令牌環(huán); 短波通信; 中繼減少; 傳輸順序優(yōu)化; 聯(lián)合算法; 時延降低

中圖分類號： TN915?34? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）13?0011?05

Optimization of transmission order of shortwave token ring

LI Chengwen， LI Chisheng， LIN Mengsi， WU Xiaoqing

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

Abstract： The shortwave token ring distributed self?organizing and non?competitive mechanism effectively avoids the shortwave data communication access conflict and provides a good multiple access mode for shortwave communication. For the problem that the possible token overhead generated by unnecessary relay nodes in the shortwave token ring may affect network throughput and delay， it is transformed into the optimal shortwave token ring optimal transmission sequence table， so a joint algorithm combining Floyd algorithm and genetic algorithm is proposed to optimize the shortwave order of the shortwave token ring. The results show that the optimized transmission sequence table reduces the number of unnecessary relays and verifies the effectiveness of the algorithm in optimizing the transmission order of the shortwave token ring. The result got by the joint algorithm is compared with those got by both Floyd algorithm and genetic algorithm. The comparative result indicates that the joint algorithm has better effect. The analysis conclusion shows that the shortwave token ring transmission order optimized by the joint algorithm can improve the network throughout and reduce the time delay of network data transmission.

Keywords： shortwave token ring; shortwave communication; relay cutting down; transmission order optimization; joint algorithm; delay reduction

0? 引? 言

短波令牌環(huán)協(xié)議[1]是實現(xiàn)多節(jié)點在同一廣播信道中進行數(shù)據(jù)交互的MAC層協(xié)議，根據(jù)令牌數(shù)據(jù)對各個節(jié)點進行發(fā)送權利的控制，使得每個節(jié)點發(fā)送數(shù)據(jù)的機會公平且無沖突，避免了信道上的碰撞。同時，短波令牌環(huán)是一個自組織網(wǎng)絡，擁有良好的自我修復能力，能有效解決單故障節(jié)點問題。將短波令牌環(huán)應用于短波通信中，有利于避免數(shù)據(jù)沖突，提供了較好的網(wǎng)絡吞吐量和接入時延，強化了短波抗毀能力。

在節(jié)點數(shù)量多的情況下，短波令牌環(huán)由于網(wǎng)絡拓撲變化可能產(chǎn)生不必要的中繼，從而影響到整個網(wǎng)絡的性能。針對中繼引起的時延問題，考慮傳輸順序的優(yōu)化，即對整個環(huán)路長度的優(yōu)化。在求得整個環(huán)路長度之前，需要求解每個節(jié)點對之間的最短距離。短波令牌環(huán)內(nèi)節(jié)點可以監(jiān)聽其他節(jié)點是否能與自身直接通信，根據(jù)監(jiān)聽到的監(jiān)聽表，依次通過令牌傳遞給后繼節(jié)點，后繼節(jié)點更新傳遞的監(jiān)聽表，最終容易得到一個全部節(jié)點的監(jiān)聽表，再根據(jù)求解點與點之間的最短路徑算法，可以得到求解封閉環(huán)路最短路徑問題的輸入?yún)?shù)。求解兩點之間最短路徑算法有Dijkstra算法[2]和Floyd算法[3]。

求解封閉環(huán)路的最短路徑問題可以參考旅行商問題（TSP）的解法。TSP[4]是完全NP問題，目前對于TSP問題的解法有多種，包括動態(tài)規(guī)劃法、分支定界法、遺傳算法等。動態(tài)規(guī)劃法[5]運用遞歸的思想，相比于全排列的情況降低了時間復雜度，但仍舊對于節(jié)點數(shù)目過大的問題沒有快速地找出最優(yōu)解。分支定界法[6]根據(jù)一個智能化的判定函數(shù)，只產(chǎn)生部分狀態(tài)空間樹，從而加速了搜索過程，但是該算法最壞情況的時間復雜度與動態(tài)規(guī)劃法的時間復雜度一致，很少應用在大規(guī)模的問題中。遺傳算法[7]是模仿生物學的自然選擇和自然遺傳，模仿生命進化來求解問題的最優(yōu)解。遺傳算法具有算法簡單、易于實現(xiàn)、能夠并行化和全局搜索能力等特點，且較傳統(tǒng)的精確算法速度較快。

為了改善短波令牌環(huán)網(wǎng)絡吞吐量和時延問題，考慮優(yōu)化短波令牌環(huán)中的傳輸順序表，將節(jié)點之間的距離用跳數(shù)表示。本文使用Floyd算法求解最小距離矩陣作為遺傳算法的初始解，再使用遺傳算法對短波令牌環(huán)周期長度進行求解，從而求得優(yōu)化的傳輸順序表。預期優(yōu)化之后的傳輸順序表比未優(yōu)化的傳輸順序表存在更少的中繼節(jié)點個數(shù)，使環(huán)運行一周的時間減少，減少中繼帶來的時延，提高網(wǎng)絡性能。

1? 傳輸順序優(yōu)化問題

短波令牌環(huán)協(xié)議具有分布式自組織和無競爭等特點，適用于短波數(shù)據(jù)通信。節(jié)點與節(jié)點之間進行數(shù)據(jù)傳輸需要進行組網(wǎng)過程，首先當節(jié)點定時器到期后，節(jié)點將發(fā)出邀請組網(wǎng)信號，其他節(jié)點收到信號將等待一段時間后回應，節(jié)點收到回應則更新傳輸順序表放入發(fā)送令牌中發(fā)送給下一節(jié)點，下一節(jié)點收到令牌更新傳輸順序表并按照該表進行傳輸。

在短波令牌環(huán)協(xié)議中，令牌數(shù)據(jù)內(nèi)的傳輸順序表字段規(guī)定了每個節(jié)點發(fā)送數(shù)據(jù)的順序，只有發(fā)送權輪到目標節(jié)點，目標節(jié)點才能發(fā)送數(shù)據(jù)。短波令牌環(huán)相比無線令牌環(huán)，增加了中繼和環(huán)合并機制[8]。在沒有中繼機制的無線令牌環(huán)中，整個環(huán)路只與相鄰節(jié)點進行數(shù)據(jù)傳輸，若節(jié)點與另一節(jié)點之間通信發(fā)生故障，自恢復機制丟棄不可到達節(jié)點，將通信范圍內(nèi)的其他節(jié)點作為新的后繼節(jié)點，從而使整個環(huán)路封閉，此時整個環(huán)路的傳輸順序已經(jīng)是最優(yōu)情況?？紤]中繼機制[9]的短波令牌環(huán)不是直接將不可到達的節(jié)點舍棄，而是通過判斷不可到達的節(jié)點是否可以通過中繼某個節(jié)點，使得整個網(wǎng)絡形成封閉的環(huán)路。然而中繼節(jié)點的數(shù)目是不確定的，從源節(jié)點到最終的目標節(jié)點之間可能存在多個中繼節(jié)點。如果不對中繼情況下的短波令牌環(huán)進行優(yōu)化處理，整個網(wǎng)絡環(huán)路將存在很多無意義的中繼，導致環(huán)路的吞吐量下降，網(wǎng)絡性能整體下降，如圖1所示。

圖1顯示4節(jié)點情況下短波令牌環(huán)出現(xiàn)不必要中繼的情況，其中節(jié)點C和節(jié)點D可以通信。所以優(yōu)化傳輸順序表可以使得整個網(wǎng)絡的開銷減少，尤其是網(wǎng)絡節(jié)點之間需要中繼多次所產(chǎn)生的時間成本，當網(wǎng)絡節(jié)點的數(shù)據(jù)負載量過大時，將大大增加數(shù)據(jù)傳輸?shù)臅r延。

2? 問題分析

短波令牌環(huán)[10]網(wǎng)絡可以用圖[G（N，L）]來表示，其中[N]為環(huán)內(nèi)節(jié)點數(shù)，[L]為節(jié)點對之間的鏈路。將短波令牌環(huán)中節(jié)點與節(jié)點之間通信所需跳數(shù)作為節(jié)點之間的距離，其傳輸順序的優(yōu)化可以轉化為網(wǎng)絡節(jié)點之間形成封閉環(huán)路的最短路徑問題，即求環(huán)周期長度RCL的最小值：

同時，根據(jù)距離矩陣可以推出鄰接矩陣：

計算RCL的最小值需要距離矩陣，距離矩陣的計算需要通過全局的鄰接矩陣。單個節(jié)點產(chǎn)生的監(jiān)聽表只是局部鄰接矩陣，所以需要至少經(jīng)過一輪令牌傳遞將局部的距離矩陣轉換為鄰接矩陣，再與自身的局部鄰接矩陣對比更新，最后得到全局鄰接矩陣，短波令牌環(huán)傳輸順序優(yōu)化問題便可以進行求解。

根據(jù)以上分析，短波令牌環(huán)傳輸順序優(yōu)化問題的求解過程如圖2所示。

3? 傳輸順序聯(lián)合優(yōu)化算法

根據(jù)短波令牌環(huán)協(xié)議的要求，每個節(jié)點都存在一張監(jiān)聽表，記錄節(jié)點與其他節(jié)點是否相鄰，即能否直接通信。在組網(wǎng)開始時，節(jié)點與節(jié)點之間還未形成環(huán)路，所以需要通過令牌將鄰接信息傳遞，此時節(jié)點傳遞的是局部距離矩陣，一個節(jié)點到另一個節(jié)點的距離將以四位二進制的形式依次放入令牌中，一個環(huán)內(nèi)節(jié)點到節(jié)點的最長距離為15，即每個節(jié)點對之間最多能中繼15次[11]。傳輸順序表所占令牌字節(jié)數(shù)為：

式中Ceil（[x]）是大于或等于[x]的最小整數(shù)。

節(jié)點接收到前驅節(jié)點的局部距離矩陣，將根據(jù)式（2）得到局部鄰接矩陣，當環(huán)路能穩(wěn)定運行一個周期后，節(jié)點將收到所有節(jié)點的鄰接信息。通過每一次的對比更新，形成全局鄰接矩陣。以A，B，C，D四節(jié)點為例，如圖3所示。

當A節(jié)點和B節(jié)點組網(wǎng)時，B節(jié)點將收到A節(jié)點傳來的局部距離矩陣，此時B節(jié)點將其轉化為局部鄰接矩陣，并將B節(jié)點監(jiān)聽到的鄰接信息插入到局部鄰接矩陣，形成新的局部距離矩陣，并將其傳遞給C節(jié)點，C節(jié)點重復同樣的工作，直到D節(jié)點將更新完的全局鄰接信息傳遞給A，此時四節(jié)點環(huán)網(wǎng)已經(jīng)組建完成。

得到全局鄰接矩陣之后，開始考慮計算全局最小距離矩陣[DM]。根據(jù)Floyd算法得到節(jié)點對之間的最短距離之后，可以利用遺傳算法求解RCL的最小值，結合每對節(jié)點之間的路徑表得到最終優(yōu)化后的傳輸順序表。

本文聯(lián)合優(yōu)化算法步驟如下：

步驟1：節(jié)點接收到令牌數(shù)據(jù)，將得到的距離字段按式（2）進行轉換，得到全局鄰接矩陣[A]。

步驟2：初始化DM最小距離矩陣，將鄰接矩陣[A]復制給[DM]矩陣。初始化傳輸順序記錄表TL，用于記錄每對節(jié)點之間的順序路徑。

步驟3：根據(jù)下式找出每對節(jié)點之間的最小距離，更新DM矩陣和TL順序表。

步驟4：傳輸順序編碼，為每一個節(jié)點標注序號，傳輸順序用序列表示，隨機產(chǎn)生[k]個不同順序的序列。

步驟5：計算并評價每條序列的適應值[fi]。每條序列的適應值決定被選取的概率，適應值越大，被選取的概率越大。求解問題為RCL的最小值，適應值函數(shù)應選為RCL的倒數(shù)，根據(jù)所得全部序列的適應值，對所有序列進行評價，如下式：

參考文獻

[1] NC3A. STANAG 5066： profile for HF data communications annex L， high?frequency wireless – token – ring – protocol requirements [S/OL]. [2012?06?17]. https：//ishare.iask.sina.com.cn/f/24968358.html.

[2] ZULFIQAR L， ISNANTO R， NURHAYATI O. Optimal distribution route planning based on collaboration of Dijkstra and sweep algorithm [C]// 2018 10th International Conference on Information Technology and Electrical Engineering （ICITEE）. Kuta， Bali Island： IEEE， 2018： 24?26.

[3] 潘立彥，張大成.改進Floyd算法在城市交通網(wǎng)絡優(yōu)化中的應用[J].物流技術，2018，37（11）：71?74.

[4] 劉云飛.基于TSP問題的仿生算法比較[J].電子技術與軟件工程，2019（2）：110?111.

[5] 來學偉.動態(tài)規(guī)劃法在TSP問題中的應用[J].吉林化工學院學報，2017，34（3）：65?67.

[6] 白云嬌.關于分支定界法求解過程的補充和改進[J].科學咨詢（科技管理），2017（27）：72?73.

[7] 馬駿.遺傳算法TSP的Matlab求解分析[J].科技視界，2018（16）：37?38.

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

[9] JOHNSON E E， TANG Z， BALAKRISHNAN M. Token relay with optimistic joining [C]// 2005 IEEE Military Communications Conference. Atlantic City， NJ， USA： IEEE， 2005： 2216?2222.

[10] 賀驍，劉蕓江，白翔，等.短波地空IP網(wǎng)絡的MAC協(xié)議設計與仿真[J].計算機應用與軟件，2016，33（3）：138?142.

[11] 李燦.短波通信網(wǎng)令牌環(huán)協(xié)議應用研究[D].北京：中國艦船研究院，2014.