平衡超立方體的故障容錯(cuò)性

張欣欣，許力，林麗美,3

?

平衡超立方體的故障容錯(cuò)性

張欣欣1,2，許力1,2，林麗美1,2,3

（1. 福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建福州 350007；2. 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室，福建福州 350007；3. 福建農(nóng)林大學(xué)計(jì)算機(jī)信息學(xué)院，福建福州 350002）

故障容錯(cuò)是衡量多處理器互連網(wǎng)絡(luò)可靠性的重要方式之一。其中-限制邊連通度和-限制連通度保證了剩下每個(gè)分支之間不連通且每個(gè)分支中節(jié)點(diǎn)的鄰居數(shù)目不少于，能夠更加精準(zhǔn)地測量多處理器和多信道系統(tǒng)的容錯(cuò)性和可靠性。平衡超立方體是超立方體的一個(gè)變形，它特有的良好拓?fù)湫再|(zhì)能夠更好地滿足多處理器系統(tǒng)和多種新型網(wǎng)絡(luò)的需要。提出了維平衡超立方體的{1,2}-限制邊連通度和{1,2}-限制連通度，能夠豐富以平衡超立方體為拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)容錯(cuò)性和可靠性的評價(jià)體系，并為平衡超立方體的故障診斷算法打下良好基礎(chǔ)。

故障容錯(cuò)性；限制連通度；限制邊連通度；平衡超立方體

1 引言

連通度（邊連通度）測量容錯(cuò)性有3個(gè)明顯的缺陷：① 2個(gè)網(wǎng)絡(luò)的連通度（或邊連通度）即使相同，它們的可靠性也不一定一樣，因?yàn)樗鼈兊淖钚↑c(diǎn)割（或最小邊割）故障概率可能不同；②連通度（邊連通度）不能準(zhǔn)確地反映由于處理機(jī)（或通信信道）損壞造成的系統(tǒng)損壞程度；③在分析和應(yīng)用這2個(gè)參數(shù)時(shí)，本文不言而喻地假定了系統(tǒng)的任何部件都可能同時(shí)失靈[4]。為了彌補(bǔ)以上缺陷，人們對傳統(tǒng)的連通度（邊連通度）概念加以推廣，以適應(yīng)網(wǎng)絡(luò)容錯(cuò)性分析的需要。本文研究的限制邊連通度和限制連通度就是連通度和邊連通度的推廣。

超立方體被稱為并行計(jì)算系統(tǒng)中最流行的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一,Bhuyan[18]提出了各種性能優(yōu)良的超立方體網(wǎng)絡(luò)的變形，經(jīng)過多年的發(fā)展，新型互連網(wǎng)絡(luò)已經(jīng)提出一系列的拓?fù)浣Y(jié)構(gòu)，包括折疊立方網(wǎng)絡(luò)、交叉立方網(wǎng)絡(luò)、交換立方網(wǎng)絡(luò)、分層立方網(wǎng)絡(luò)和平衡超立方網(wǎng)絡(luò)等。由Wu和Huang[19]提出的平衡超立方體增強(qiáng)了超立方體的一些性質(zhì)。平衡超立方體中每個(gè)點(diǎn)都有一個(gè)與自己鄰點(diǎn)相同的匹配節(jié)點(diǎn)，故在平衡超立方網(wǎng)絡(luò)中一個(gè)故障節(jié)點(diǎn)的運(yùn)行任務(wù)可以轉(zhuǎn)化給它的匹配節(jié)點(diǎn)完成[20]。迄今為止，平衡超立方體的容錯(cuò)性與可靠性研究尚未求出。

2 平衡超立方體的定義與性質(zhì)

平衡超立方體的定義由Wu和Huang[19]用2種方式提出。

圖1是一維平衡超立方體和二維平衡超立方體的結(jié)構(gòu)圖。

圖1 一維和二維平衡超立方體結(jié)構(gòu)

3 平衡超立方體的限制邊連通度

圖2 ，都不在S中

4 平衡超立方體的限制連通度

圖3 圈C的鄰邊集

圖4 圈C的鄰點(diǎn)集

圖5 F是的2-限制點(diǎn)割

圖6 是連通的

圖7 是連通的

圖8 是連通的

圖9 是連通的

圖10

圖11

5 結(jié)束語

[1] 包國華, 王生玉, 李運(yùn)發(fā). 云計(jì)算中基于隱私感知的數(shù)據(jù)安全保護(hù)方法研究[J]. 信息網(wǎng)絡(luò)安全, 2017(1):84-89. BAO G H,WANG S Y, LI Y F. Research on privacy aware data security protecting method in cloud computing[J]. Netinfo Security, 2017(1):84-89.

[2] 周濤, 柏文潔, 汪秉宏, 等. 復(fù)雜網(wǎng)絡(luò)研究概述[J]. 物理, 2005, 34(1): 31-36. ZHOU T, BAI W J,WANG B H, et al. Overview of complex network Research[J]. PHYSICS, 2005, 34(1): 31-36.

[3] 滑楠, 曹志剛. 無線認(rèn)知網(wǎng)絡(luò)概念與實(shí)例研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 45(2): 1-6. HUA N, CAO Z G. The concept and examples of wireless cognitive Network[J]. Computer Engineering and Applications, 2009, 45(2): 1-6.

[4] 徐俊明. 組合網(wǎng)絡(luò)理論[M]. 北京: 科學(xué)出版社, 2007.

XU J M, Combinatorial theory in networks[M]. Beijing: Science Press,2007.

[5] 徐俊明. 圖論及其應(yīng)用[M]. 合肥: 中國科學(xué)技術(shù)出版社, 2010.

XU J M, Graph Theory with Applications[M]. Hefei: Science and Technology of China Press,2010.

[6] XU J M, ZHU Q, XOU X M, et al. On restricted connecti-vity and extra connectivity of hypercubes and folded hypercubes[J]. Journal of Shanghai Jiaotong University (Science), 2005, 10(2): 203-207.

[7] LIN L M, XU L, ZHOU S M, et al. The extra, restricted connectivity and conditional diagnosability of split-star networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(2): 533-545.

[8] LIN L M, ZHOU S M. Conditional connectivity for (n, k)- arrangement graphs[J]. Journal of Mathematical Study, 2012, 45(4): 350-364.

[9] 林麗美, 周書明, 許力. 分層立方網(wǎng)絡(luò)的/-診斷度和診斷算法[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版). 2013, 48(7):85-92. LIN L M, ZHOU S M, XU L./- diagnosability and diagnosis algorithm for hierarchical cube networks[J]. Journal of Shandong University(Natural Science), 2013,48(7):85-92.

[10] ZHOU S, CHEN L, XU J M. Conditional fault diagnosability of dual-cubes[J]. International Journal of Foundations of Computer Science, 2012, 23(8): 1729-1748.

[11] ZHOU S, XU J M. Conditional fault tolerance of arrangement graphs[J]. Inform Process. 2011, 111(21): 1037-1043.

[12] ZHU Q, XU J M. On restricted edge connectivity and extra edge connectivity of hypercubes and folded hyper cubes[J]. Journal of University of Science and Technology of China, 2006, 36(3): 249-251.

[13] PAN X F, XU J M, LV M. On restricted connectivity of some cartesian product graphs[J]. Journal of University of Science and Technology of China, 2006, 36(3):237-240.

[14] 王國亮, 師海忠. 完全對換網(wǎng)絡(luò)的限制連通度[J]. 運(yùn)籌學(xué)報(bào), 2013, 17(3): 57-64.

WANG G L, SHI H Z. The restricted connectivity of completely switched networks[J]. Operations Research Transactions, 2013, 17(3): 57-64.

[15] 馬強(qiáng), 梁家榮, 熊茜, 等. 交換交叉網(wǎng)絡(luò)的可靠性研究[J]. 高技術(shù)通訊, 2015, 25(10):919-926.

MA Q, LIANG J R, XIONG Q, et al.Research on reliability of switched cross networks[J]. High Technology Letters,2015, 25(10): 919-926.

[16] XU J M, LV M, FAN Y M. The restricted edge-connectivity of de Bruijn undirected graphs[J]. Ars Combinatoria Waterloo then Winnipeg, 2008, 83(1):321-333.

[17] 徐俊明，點(diǎn)可遷圖的限制邊連通度[J]. 數(shù)學(xué)年刊A輯(中文版), 2000, 21(5):266-272.

XU J M. Restricted edge connectivity of vertex transitive graphs[J]. Chinese Annals of Mathematics,Series A.2000, 21(5):266-272.

[18] BHUYAN L N, AGRAWAL D P. Generalized hypercube and hypercube structures for a computer network[J]. IEEE Trans Computers, 1984,32(4):323-333.

[19] WU J, HUANG K. The balanced hypercube: a cube-based systemhemat for fault-tolerant applications[J]. IEEE Transactions Comput, 1997, 46(4): 484-490.

[20] ZHOU J X, WU Z L, YANG S C, et al. Symmetric proper and reliability of balanced hypercube[J]. IEEE Transactions Comput, 2015, 64(3): 876-881.

[21] LU H Z. On extra connectivity and extraedge-connectivity of balanced hyper cubes[J]. International Journal of Computer Mathematics, 2016, 94(4): 813-820.

[22] YANG M C. Super connectivity of balanced hyper cubes[J]. Applied Mathematics and Computation, 2012, 219(3): 970-975

Fault tolerance of balanced hypercubes

ZHANG Xin-xin1,2, XU Li1,2, LIN Li-mei1,2,3

(1. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China;2. Fujian Provincial Key Laboratory of Network Security and Cryptology, Fuzhou 350007, China;3. College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China)

Fault tolerance is one of the important ways to measure the reliability of multiprocessor interconnection networks.-restricted edge connectivity and-restricted connectivity can ensure every remaining component is disconnected , the number of neighbors of vertex is no less than, which can measure the fault tolerance and reliability of multiprocessor and multichannel system more accurately. Balanced hypercubes is a variant of the hypercube, which has some specific topological properties, it can better meet the needs of the multiprocessor system and many new networks. The {1,2}-restricted edge connectivity and the {1,2}-restricted connectivity of balanced hypercubes were proposed, which could enrich the evaluation system of network fault tolerance and reliability in balanced hypercubes topology and it laid a good foundation for the fault diagnosis algorithm of balances hypercube.

fault tolerance, restricted connectivity, restricted edge-connectivity, balanced hypercubes

O157.5

A

10.11959/j.issn.2096-109x.2017.00193

2017-06-15；

2017-08-17。

許力，Xuli@fjnu.edu.cn

國家自然科學(xué)基金資助項(xiàng)目（No.61771140, No.U1405255, No.61702100）；福州市科技局基金資助項(xiàng)目（No.2015-G-59）；福建省高校產(chǎn)學(xué)合作科技重大基金資助項(xiàng)目（No.2017H6005）；福建省教育廳基金資助項(xiàng)目（No.JAT160123）；中國博士后面上基金資助項(xiàng)目（No.2017M612107）

The National Natural Science Foundation of China (No.61771140, No.U1405255, No.61702100), Fuzhou Science and Technology Bureau Project (No.2015-G-59), University Industry Cooperation of Major Science and Technology Project of Fujian Province (No.2017H6005), Fujian Provincial Education Department Project (No.JAT160123), Post-doctoral Science Foundation of China (No.2017M612107)

張欣欣（1993-），女，河南羅山人，福建師范大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。

許力（1970-），男，福建福州人，博士，福建師范大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。

林麗美（1988-），女，福建莆田人，博士，福建農(nóng)林大學(xué)講師，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。