孫灝

摘要：在采用二叉樹模型構(gòu)建的有向雙環(huán)網(wǎng)絡(luò)路由模型的基礎(chǔ)上，研究有向雙環(huán)網(wǎng)絡(luò)的移動路由拓撲對稱構(gòu)造算法，通過二叉樹模型處理有向雙環(huán)網(wǎng)絡(luò)路由問題，確定有向雙環(huán)網(wǎng)絡(luò)的緊優(yōu)對稱無限簇，處理有向雙環(huán)網(wǎng)絡(luò)的最佳路由拓撲對稱問題;采用雙環(huán)拓撲優(yōu)化算法模擬計算有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲，確定最佳雙環(huán)網(wǎng)絡(luò)拓撲;并研究移動路由分布式容錯算法，當(dāng)有向雙環(huán)網(wǎng)絡(luò)內(nèi)個別節(jié)點出現(xiàn)故障時，提升路由算法的堅定性，使其發(fā)揮最優(yōu)化拓撲性能。通過同相關(guān)路由構(gòu)造算法的對比，證實了該路由構(gòu)造算法具有網(wǎng)絡(luò)延遲上升速度低、吞吐量高的優(yōu)勢。綜上所述，表明該算法具有較高的拓撲性質(zhì)和通信性能。

關(guān)鍵詞：有向雙環(huán)網(wǎng)絡(luò);移動路由;拓撲;對稱;構(gòu)造算法;容錯算法

中圖分類號：TP302文獻標(biāo)志碼：A

文章編號：2095-5383（2019）02-0046-05

Abstract：Efficient internet topology is of great significance for improving the efficiency and quality of information interaction in the information age. On the basis of using the binary tree model to construct the routing model of directional double-loop networks，the topology symmetric construction algorithm for mobile routing of directional double-loop networks was studied. In this paper，the routing problem of directional double-loop network was dealt with the binary tree model，the compact excellent symmetric infinite cluster of directional double-loop network was determines，and the topology symmetry problem of optimal routing of directional double-loop network was solved. The algorithm of double loop topology optimization was used to calculate the mobile routing topology of the directed double loop network. In this paper，the distributed fault tolerant algorithm of mobile routing was studied to improve the firmness of routing algorithm in case of fault of individual nodes in the dual loop network. The comparison with the correlation routing algorithm proves that the proposed routing algorithm has the advantages of low latency and high throughput. In summary，it is shown that the algorithm has high topological properties and communication performance.

Keywords： directional double-loop network; mobile routing; topology; symmetry; construct algorithms; fault-tolerant algorithm

在互聯(lián)網(wǎng)技術(shù)越發(fā)成熟的今天，受多處理機系統(tǒng)規(guī)模不斷發(fā)展的影響，計算機系統(tǒng)結(jié)構(gòu)的通信效率逐漸引起人們的關(guān)注。為了提高人們通過網(wǎng)絡(luò)進行信息交互的效率和質(zhì)量，相關(guān)人員致力于尋找一種拓撲結(jié)構(gòu)簡單、網(wǎng)絡(luò)直徑短且連接度低的移動路由拓撲結(jié)構(gòu)[1]。在計算機互聯(lián)網(wǎng)絡(luò)與通信系統(tǒng)內(nèi)，雙環(huán)網(wǎng)絡(luò)是主要的拓撲結(jié)構(gòu)[2]。文獻[3-5]描述的均是有向雙環(huán)網(wǎng)絡(luò)最佳跳躍在滿足給定范圍條件下的最優(yōu)路由算法，此類算法在節(jié)點失效等故障條件下，路由堅定性較差，無法發(fā)揮最優(yōu)化拓撲性能。因此，本文研究了新的有向雙環(huán)網(wǎng)絡(luò)的移動路由拓撲對稱構(gòu)造算法，處理有向雙環(huán)網(wǎng)絡(luò)的最佳路由拓撲對稱問題，在獲取有向雙環(huán)網(wǎng)絡(luò)移動路由最佳拓撲的基礎(chǔ)上，研究其分布式容錯算法，提升有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲結(jié)構(gòu)的性能。

1 有向雙環(huán)網(wǎng)絡(luò)的移動路由拓撲對稱構(gòu)造

1.1 構(gòu)建有向雙環(huán)網(wǎng)絡(luò)路由模型

假設(shè)有向雙環(huán)網(wǎng)絡(luò)為GN;r，s（各頂點分別是0，1，2，…，N-1），以各頂點i為出發(fā)點的兩條有向邊分別記作i→i+rmod N和i→i+smod N，r與s均為自然數(shù)，并滿足1

以往求解有向雙環(huán)網(wǎng)絡(luò)直徑時，多基于有向圖L形瓦的特征參數(shù)進行計算，然而L形瓦只能間接表現(xiàn)各節(jié)點的路由特征。因此，采用二叉樹模型反映有向雙環(huán)網(wǎng)絡(luò)GN;r，s內(nèi)各節(jié)點的最佳路由特性，二叉樹模型的樹高與有向雙環(huán)網(wǎng)絡(luò)GN;r，s的直徑一致，通過確定有向雙環(huán)網(wǎng)絡(luò)GN;r，s緊優(yōu)對稱點r，s解決其最優(yōu)路由對稱問題。

用+r、+s表示有向雙環(huán)網(wǎng)絡(luò)各節(jié)點發(fā)出的有向邊i→i+rmod N和i→i+smod N，由于有向雙環(huán)網(wǎng)絡(luò)具有對稱性[7]，節(jié)點U與節(jié)點V間距離同節(jié)點O與節(jié)點V-U間距離一致。因此，在分析有向雙環(huán)網(wǎng)絡(luò)GN;r，s的路由策略時僅分析O節(jié)點與其他節(jié)點間的了路由策略即可，一般情況下i的初始值為0。

定義1：在節(jié)點集U內(nèi)，以節(jié)點O為根節(jié)點，+r邊和+s邊為連線，r和s分別為根節(jié)點的左孩子和右孩子，搭建二叉樹模型第一層節(jié)點。在第一層節(jié)點中按序取各節(jié)點i，通過i+rmod N與i+smod N確定節(jié)點i的左孩子節(jié)點與右孩子節(jié)點。當(dāng)節(jié)點集U內(nèi)不存在孩子節(jié)點時，需在二叉樹模型下一層內(nèi)構(gòu)建節(jié)點i的孩子節(jié)點，且將其保存至節(jié)點集U內(nèi)，否則無動作。循環(huán)此過程，通過上一層的全部節(jié)點生成下一層節(jié)點，直至無法生成新節(jié)點結(jié)束，構(gòu)建的二叉樹模型用BTN;r，s表示。有向雙環(huán)網(wǎng)絡(luò)G10;3，4轉(zhuǎn)換為二叉樹模型BT（10;3，4）如圖1所示。

1）初始化同時構(gòu)建根節(jié)點。給定N，確定dN;r，s的直徑下界1bN;構(gòu)建根節(jié)點，其值data和層數(shù)layer均為0;在節(jié)點集數(shù)組N內(nèi)寫入根節(jié)點值;定義保存緊優(yōu)對稱點r，s個數(shù)的變量

2）確定緊優(yōu)對稱點r，s。分別由2至N-2和由r+1至N-1外層循環(huán)r和內(nèi)層循環(huán)s，并分別取值;在N內(nèi)節(jié)點數(shù)量低于N的條件下，按序取當(dāng)前層內(nèi)各節(jié)點，通過data+rmod N生成左孩子節(jié)點，通過data+smod N生成右孩子節(jié)點;層數(shù)提升1，再次進行左、右孩子節(jié)點生成過程，至無法生成新節(jié)點或N內(nèi)節(jié)點數(shù)量等于N結(jié)束;當(dāng)N內(nèi)節(jié)點數(shù)量等于N時，對比1bN值與層數(shù)值，在兩值相等的情況下，輸出緊優(yōu)對稱點值并存儲，同時在變量sum上加1，再次進行外層循環(huán)和內(nèi)層循環(huán)過程，至外層循環(huán)結(jié)束為止。

3）確定N、1bN、全部緊優(yōu)對稱點以及緊優(yōu)對稱點總數(shù)，并輸出。外層r、中層s和內(nèi)層分別從2至N-2、r+1至N-1和當(dāng)前層上第一個階段至最后一個節(jié)點循環(huán)，時間復(fù)雜度和空間復(fù)雜度分別為On3和On。

此算法功能為：針對任意N值，確定有向雙環(huán)網(wǎng)絡(luò)全部緊優(yōu)對稱點，可在有限時間內(nèi)確定任一N值的全部緊優(yōu)對稱點。

通過二叉樹模型處理有向雙環(huán)網(wǎng)絡(luò)G（N;r，s）的路由問題，可快速獲取有向雙環(huán)網(wǎng)絡(luò)直徑的顯示公式，確定有向雙環(huán)網(wǎng)絡(luò)的緊優(yōu)對稱無限簇，處理有向雙環(huán)網(wǎng)絡(luò)的最佳路由對稱問題。

1.2 有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲模擬計算及分析

上述過程成功構(gòu)建有向雙環(huán)網(wǎng)絡(luò)，用dmin表示有向雙環(huán)網(wǎng)絡(luò)直徑最小值，為使該有向雙環(huán)網(wǎng)絡(luò)拓撲達到最佳狀態(tài)，也就是使有向雙環(huán)網(wǎng)絡(luò)直徑最接近dmin，需確定以h表示的有向雙環(huán)網(wǎng)絡(luò)移動路由的最佳跳躍[11]。在確定h的過程中，采用雙環(huán)拓撲優(yōu)化算法，針對已知N，構(gòu)建h、x（有向雙環(huán)網(wǎng)絡(luò)邊緣長度）有所差異的有向雙環(huán)網(wǎng)絡(luò)。確定不同有向雙環(huán)網(wǎng)絡(luò)內(nèi)的d1與d2，進行對比，將最大者作為d。確定N內(nèi)全部的dmin，當(dāng)d=dmin時，確定a表示的有向雙環(huán)網(wǎng)絡(luò)平均跳躍距離，同時確定全部可能的d=dmin或最小d相應(yīng)的a，確定最小值，其相應(yīng)的h為有向雙環(huán)網(wǎng)絡(luò)最佳h。雙環(huán)拓撲優(yōu)化算法適用于全部N，通過雙環(huán)拓撲優(yōu)化算法對2.1小節(jié)內(nèi)的有向雙環(huán)網(wǎng)絡(luò)實施模擬運算，確定可靠最優(yōu)有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲參數(shù)（3≤N≤104），參數(shù)內(nèi)涵蓋各已知N的h、d和a。

最佳雙環(huán)拓撲參數(shù)具有如下規(guī)律：

1）在N≠3.5的條件下，基于有向雙環(huán)網(wǎng)絡(luò)對稱性，其具最佳h有偶數(shù)個[12]，因此最佳h個數(shù)≥2，使有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲達到最優(yōu)化。也就是最佳h以2的倍數(shù)出現(xiàn)，假設(shè)h為最佳狀態(tài)，那么1-hmod N同同樣為最佳狀態(tài)，同時基于N+1/2對稱，其任意兩值相加均等于N+1。

2）通常情況下，N的大小同d與a的大小呈正比;在同一N內(nèi)，d與a的大小呈正比;在同一N內(nèi)，d一致條件下，a也一致。

（3）特殊情況下，個別N內(nèi)確定最佳h的解析式的個數(shù)為有限個。

（4）在3≤N≤104條件下，d的上限為：

通過雙環(huán)拓撲優(yōu)化算法，能夠確定全部N（N>104）的d與a，也就是確定全部N的最佳雙環(huán)網(wǎng)絡(luò)拓撲，d與a為準(zhǔn)確解。

1.3 移動路由分布式容錯算法

移動路由選擇算法直接關(guān)系著有向雙環(huán)網(wǎng)絡(luò)的拓撲性能，對故障條件下有向雙環(huán)網(wǎng)絡(luò)移動路由的容錯算法進行分析研究，能夠提升有向雙環(huán)網(wǎng)絡(luò)移動路由算法的堅定性，發(fā)揮其最優(yōu)化拓撲性能。在有向雙環(huán)網(wǎng)絡(luò)內(nèi)節(jié)點失效等價于鏈路失效[13]，因此只研究節(jié)點失效狀態(tài)即可。通過由部分區(qū)域中地址表情報固定時間內(nèi)循環(huán)互換實現(xiàn)移動路由分是容錯算法的自適應(yīng)性[14]。在有向雙環(huán)網(wǎng)絡(luò)內(nèi)個別節(jié)點出現(xiàn)故障的條件下，與故障節(jié)點距離最近的上游節(jié)點向系統(tǒng)發(fā)送故障信息，通知相關(guān)各節(jié)點于各自地址表中對故障節(jié)點地質(zhì)好實施修正，如標(biāo)識為“∞”，使信包在尋徑過程中不接觸故障節(jié)點。

1）算法1：

規(guī)則1：有向雙環(huán)網(wǎng)絡(luò)內(nèi)隨意節(jié)點獲取的信包目的地址同自身地址一致條件下，接收此信包。

規(guī)則2：假設(shè)信包的目的地址是部分區(qū)域地址表內(nèi)本節(jié)點意外的任意節(jié)點，同時抵達該節(jié)點的路徑中不存在故障節(jié)點，那么通過短鏈傳送信包;相反：在遠親節(jié)點未出現(xiàn)故障條件下，通過長鏈傳送信包;在遠親節(jié)點出現(xiàn)故障，鄰近節(jié)點未出現(xiàn)故障條件下，通過短鏈傳送信包[15]。

規(guī)則3：假設(shè)信包的目的地址是遠程地址表內(nèi)的任意節(jié)點，同時抵達該節(jié)點的路徑中不存在故障節(jié)點，那么通過長鏈傳送信包;相反：在鄰近節(jié)點未出現(xiàn)故障的條件下，通過短鏈傳送信包;在鄰近節(jié)點出現(xiàn)故障，遠親節(jié)點未出現(xiàn)故障條件下，通過長鏈傳送信包。

規(guī)則4：假設(shè)信包的目的地址是部分區(qū)域和遠程地址表外的任意節(jié)點，那么在目的地上游出現(xiàn)故障的條件下，鄰近節(jié)點無故障時，通過短鏈傳送信包;鄰近節(jié)點出現(xiàn)故障，遠親節(jié)點未出現(xiàn)故障時，通過長鏈傳送信包。在目的地上游未出現(xiàn)故障的條件下，遠親節(jié)點未出現(xiàn)故障時，通過長鏈傳送信包;遠親節(jié)點出現(xiàn)故障，近鄰節(jié)點未出現(xiàn)故障時，通過短鏈傳送信包。

2）算法2

規(guī)則1：假設(shè)獲取信包的目的地址同本節(jié)點地址一致，那么接收信包。

規(guī)則2：對有幾率存在路由的目的節(jié)點最小坐標(biāo)值I，J實施計算。

規(guī)則3：尋找到達目的節(jié)點的路徑。假設(shè)縱坐標(biāo)低于最大值，遠親節(jié)點有效，同時未確定路由

（Y1=1），那么縱向?qū)ふ?，且重?fù)此過程;假設(shè)橫坐標(biāo)低于最大值，緊鄰節(jié)點有效，用時未確定路由（Y1=1），橫向?qū)ふ?，同時轉(zhuǎn)向縱向?qū)ふ疫^程;假設(shè)縱、橫坐標(biāo)不低于最大值，那么說明路由以確定（Y1=0）;依照尋找路徑返回，至縱坐標(biāo)值降低1結(jié)束，同時轉(zhuǎn)向橫向?qū)ふ疫^程;假設(shè)Y1=0，則記憶第一步尋找方向。

規(guī)則4：假設(shè)Y1=0，則通過記憶方法尋徑。

規(guī)則5：假設(shè)Y1=1，則轉(zhuǎn)向規(guī)則2。

2 實驗分析

平均通信延遲與平均吞吐量是拓撲構(gòu)造算法中較為關(guān)鍵的性能參數(shù)。實驗為驗證本文提出的有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲對稱構(gòu)造算法的性能，選取1條虛信道，將交換機制、鏈路速率和參數(shù)分別設(shè)置為蟲孔交換、10 Kb/s和125個。對比本文算法、基于XYZ路由機制的路由拓撲構(gòu)造算法和基于3D Torus結(jié)構(gòu)的拓撲構(gòu)造算法的平均通信延遲與平均吞吐量，結(jié)果如圖2和圖3所示。

由圖2可得，均衡負載模式下，在注入率低于0.11 flits/node/cycle的條件下，三種算法的延遲均較低，且差距較小;在注入率達到0.16 flits/node/cycle的條件下，三種算法的網(wǎng)絡(luò)延遲均逐漸上升，但本文算法的網(wǎng)絡(luò)延遲上升速度相較于其他兩種算法有顯著降低。隨機對稱負載模式下，在注入率低于0.046 5 flits/node/cycle的條件下，三種算法的延遲均較低，且差距較小;在注入率達到0.061 4 flits/node/cycle的條件下，注入率一致時，本文算法的平均消息延遲明顯小于其他兩種算法。

由圖3可得，均衡負載模式下，在注入率低于0.15 flits/node/cycle的條件下，單位時間內(nèi)三種算法獲取的數(shù)據(jù)包一致;在注入率高于0.15 flits/node/cycle的條件下，有向雙環(huán)網(wǎng)絡(luò)的飽和吞吐量是11 flits/node/cycle;隨機對稱負載模式下，在注入率高于0.059 flits/node/cycle的條件下，基于XYZ路由機制的拓撲構(gòu)造算法吞吐量趨于飽和，而本文算法吞吐量在注入率達到0.15 flits/node/cycle的條件下才趨于飽和，并且本文算法吞吐量與其他兩種算法相比，有顯著提升趨勢。圖2和圖3的綜合結(jié)果表明，本文算法的平均通信延遲低、平均吞吐量高，通信性能優(yōu)于對比算法。

3 結(jié)論

本文提出有向雙環(huán)網(wǎng)絡(luò)的移動路由拓撲對稱構(gòu)造算法，利用二叉樹構(gòu)建有向雙環(huán)網(wǎng)絡(luò)，處理有向雙環(huán)網(wǎng)絡(luò)的最佳路由拓撲對稱問題后，對有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲進行模擬計算及分析，并對故障條件下有向雙環(huán)網(wǎng)絡(luò)移動路由的容錯算法進行分析研究，增強有向雙環(huán)網(wǎng)絡(luò)移動路由算法的堅定性。經(jīng)實驗證明，本文算法的性能較好，可提升有向雙環(huán)網(wǎng)絡(luò)移動路由拓撲結(jié)構(gòu)的性能。

參考文獻：

[1]ILYUSHIN G D，PISAREVSKII Y V.Modeling of the self-organization processes in crystal-forming systems： Symmetry and topological code of cluster self-assembly of molecular （island） and framework MT structures of vanadyl sulfates[J].Crystallography Reports，2015，60（6）：776-790.

[2] 張玲，聶少華.基于粒子濾波步行長度預(yù)測的移動ad hoc網(wǎng)絡(luò)路由算法[J].電訊技術(shù)，2016，56（3）：331-336.

[3] 李貞妮，李晶皎，王愛俠，等.一種新型片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)及其自適應(yīng)路由算法[J].東北大學(xué)學(xué)報（自然科學(xué)版），2017，38（9）：1217-1221.

[4] 徐吉興，李建波，由磊，等.一種基于移動方向的容延遲網(wǎng)絡(luò)受控傳染路由算法[J].小型微型計算機系統(tǒng)，2015，36（1）：60-66.

[5] 佟寧，渾潔絮，楊琦，等.基于多層立方體簇結(jié)構(gòu)的3D-Ad hoc 網(wǎng)絡(luò)路由算法[J].計算機工程與應(yīng)用，2016，52（15）：135-140.

[6] 向敏，唐亮，王平.基于Dijkstra能量均衡的無線HART圖路由算法[J].儀器儀表學(xué)報，2016，37（11）：2628-2636.

[7] SHEVCHENKO V Y，BLATOV V A，ILYUSHIN G D.Symmetry and topology codes of cluster self-assembly for icosahedral structures of the NaZn 13-cF 112 and TRB 66-cF 1944 family[J].Glass Physics & Chemistry，2015，41（4）：341-351.

[8] 耿海軍，施新剛，王之梁，等.基于有向無環(huán)圖的互聯(lián)網(wǎng)域內(nèi)節(jié)能路由算法[J].計算機科學(xué)，2018，45（4）：112-116.

[9] 佟寧，渾潔絮，李寒.三維無線自組網(wǎng)絡(luò)的成簇及自適應(yīng)路由算法[J].小型微型計算機系統(tǒng)，2015，36（3）：508-513.

[10] 李梅，武海燕，奚建清，等.基于改進的遺傳算法的MANET最優(yōu)路由生成方法[J].電子技術(shù)應(yīng)用，2017，43（8）：119-122.

[11] 涂麗芳，張姿，黃廷磊.基于平滑移動模型的k連通網(wǎng)絡(luò)拓撲控制算法研究[J].計算機應(yīng)用研究，2015，32（8）：2465-2468.

[12] 王俊士.移動通信網(wǎng)絡(luò)路由緩沖區(qū)溢出修復(fù)優(yōu)化仿真[J].計算機仿真，2016，33（5）：200-203.

[13] 丁毓良，張劍賢，周端，等.直線引導(dǎo)的Torus結(jié)構(gòu)路由算法[J].計算機工程與科學(xué)，2017，39（2）：275-279.

[14] 宋有關(guān)，李建波，和天玥，等.基于節(jié)點相似性的容遲網(wǎng)絡(luò)概率路由算法[J].計算機工程，2016，42（9）：63-70.

[15] ILYUSHIN G D.Modeling of self-organization processes in crystal-forming systems： symmetry and topology code for cluster self-assembly of crystal structures for molecular and framework compounds [J].Russian Journal of Inorganic Chemistry，2015，60（13）：1626-1691.