短波令牌環(huán)傳輸順序優(yōu)化

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

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

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

中圖分類號： TN915?34? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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]是實(shí)現(xiàn)多節(jié)點(diǎn)在同一廣播信道中進(jìn)行數(shù)據(jù)交互的MAC層協(xié)議，根據(jù)令牌數(shù)據(jù)對各個節(jié)點(diǎn)進(jìn)行發(fā)送權(quán)利的控制，使得每個節(jié)點(diǎn)發(fā)送數(shù)據(jù)的機(jī)會公平且無沖突，避免了信道上的碰撞。同時，短波令牌環(huán)是一個自組織網(wǎng)絡(luò)，擁有良好的自我修復(fù)能力，能有效解決單故障節(jié)點(diǎn)問題。將短波令牌環(huán)應(yīng)用于短波通信中，有利于避免數(shù)據(jù)沖突，提供了較好的網(wǎng)絡(luò)吞吐量和接入時延，強(qiáng)化了短波抗毀能力。

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

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

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

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

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

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

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

2? 問題分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

[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] 潘立彥，張大成.改進(jìn)Floyd算法在城市交通網(wǎng)絡(luò)優(yōu)化中的應(yīng)用[J].物流技術(shù)，2018，37（11）：71?74.

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

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

[6] 白云嬌.關(guān)于分支定界法求解過程的補(bǔ)充和改進(jìn)[J].科學(xué)咨詢（科技管理），2017（27）：72?73.

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

[8] 賀驍，李曼，白翔，等.短波令牌環(huán)協(xié)議的研究現(xiàn)狀與發(fā)展[J].通信技術(shù)，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)絡(luò)的MAC協(xié)議設(shè)計(jì)與仿真[J].計(jì)算機(jī)應(yīng)用與軟件，2016，33（3）：138?142.

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