CN106911521B - Based on polycyclic network on mating plate Topology Structure Design method - Google Patents

Abstract

The invention discloses a kind of based on polycyclic network on mating plate Topology Structure Design method, for solving the problem that network congestion present in existing network on mating plate topological structure is serious, scalability is low and network is more complex.Realize step are as follows: setting ring group set G；Ring group set G is initialized；Ring group set G after judgement initialization⁰In each ring group g_qWhether not transannular；Calculate purpose ring group set GⁿIn all ring groups the network congestion factor；2N ring group before going out to all ring groups according to network congestion factor sequencing selection；Update is optimized to preceding 2N ring group, obtains purpose ring group set Gⁿ；Judge update times n, selects the smallest ring group g of the congestion probability factor_min.The present invention can be used for alleviating the congestion situation of network on mating plate, improve the scalability of network on mating plate, and reduced network complexity and cost using the method for the selection the smallest polycyclic topology of network congestion probability factor and the communication means of single wavelength.

Description

Based on polycyclic network on mating plate Topology Structure Design method

Technical field

The invention belongs to fields of communication technology, are related to a kind of design method of network on mating plate topological structure, and in particular to A kind of design method based on polycyclic network on mating plate topological structure, the light network that can be used on chip between IP kernel realize base Low block data transmission between IP kernel, improves the efficiency of intercore communication in the network on mating plate of optical circuit exchange.

Background technique

By the way that numerous IP kernel on chip to be carried out to the network on mating plate of light network since with high bandwidth, low-power consumption is low The advantage of time delay and low EMI can effectively solve a series of bottleneck problems of electric network-on-chip.Therefore, network on mating plate has been Through becoming the multicore interconnection technique being concerned.Very more network on mating plate topologys, such as Mesh, Torus are had proposed at present Equal frameworks, these topologys can be realized the demand of high-bandwidth, low-latency, but limited by more complex router topology, bring Excessive optical device expense and network complexity.Compared to these frameworks, consider the better simply annular framework of interconnection mode, i.e., Each node is connected in the end to end ring-like optical waveguide of closure by loop.But it due to the use of optical circuit exchange, leads It causes serious link obstructions occur in annular framework, declines network performance sharply.Researcher proposes following several thus Annular framework.

Dana Vantrease et al. 2008 in meeting International Symposium on Computer Architecture has delivered article " Corona:System Implications of Emerging Nanophotonic Technology " is disclosed a kind of based on polycyclic topology design method.Intercore communication in this method is handed over by the light of 64X64 Fork, which is closed, to be completed, and implementation is to write the light ring bus singly read more, and the nucleus number in structure is the number of required ring bus Amount.And the method arbitrated by using light token, determine which node obtains the right of communication.But existing for the program not Foot is to reduce the multi-wavelength communication means that congestion introduces to lead to that the optical devices such as a large amount of waveguides, micro-loop and electric light has been used to turn Exchange device.Write in single read avoids the communication arbitration mechanism of write conflict more complex more, increases the cost and energy consumption expense of network.When When nucleus number increases, required ring bus is synchronous to be increased, and limits scalability to a certain extent.

Se ' bastien Le Beux et al. 2011 in meeting Design, Automation&Test in Europe Conference&Exhibition IEEE Xplore has delivered article " Optical Ring Network-on-Chip (ORNoC): Architecture and Design Methodology " discloses a kind of Topology Structure Design side based on ring Method.In this method, communication is using being electrically interconnected in cluster, and communication uses dedicated ORNoC optical-fiber network between cluster.In ORNoC using WDM and Reuse wavelengths technology is communicated between the multiple stationary nodes of wavelength realization in same waveguide, is improved in network on mating plate Scalability problem and obstructing problem.But deficiency existing for the program is, causes to reduce the multi-wavelength communication that congestion introduces The optical devices such as a large amount of micro-loops and electro-optic conversion equipment have been used, the cost and energy consumption expense of network are increased, meanwhile, although phase Scalability problem was improved than last scheme, but since the number of wavelengths that can be used is limited, is still limited to a certain extent The scalability of framework is made.

Pasricha Sudeed et al. 2013 in the Integrated optical published by Springer Article " On-Chip Optical has been delivered in interconnect architectures for embedded systems Ring Bus Communication Architecture for Heterogeneous MPSoC " is disclosed a kind of based on ring Topology Structure Design method.In this method, realized using light disc waveguide it is globally interconnected design ORB topology.In ORB In, when intercore communication, request will be routed to ORB interface with ring of light shape Waveguide interface.While in order to improve the band of optical interconnection Wide density, ORB utilizes wavelength-division multiplex (WDM), using the Wavelength allocation method based on cluster, using multiple wavelength carrier signals same One waveguide transmitting data preferably improves the light network bandwidth density on being electrically interconnected.To reduce blocking probability, net is improved Network is handled up.The shortcoming of the program is, because using greater amount of wavelength to improve bandwidth, so that in transmitter and reception More processing, area and power overhead are needed at machine.Since each wavelength must be allocated to given optical network interface, have The limitation of the wavelength resource of limit, this technology greatly affected the scalability of ONoC.

Summary of the invention

It is an object of the invention to overcome the shortcomings of above-mentioned prior art, propose a kind of to open up based on polycyclic network on mating plate Construction design method is flutterred, network congestion present in existing network on mating plate topological structure is serious, scalability is low for solving, And the problem of complicated network structure.

To achieve the above object, the present invention calculates each of the links in topological structure according to the interconnection situation of nodes Acquistion probability, and then obtain the congestion factor of network, using the network congestion factor as objective function, solve congestion factor most Small ring group, specific implementation step include:

(1) ring group set G is set: including u ring group g₁,g₂,g₃,...,g_q,...,g_u, q represents the serial number of ring group, each Ring group indicates to include M ring R₁,R₂,...,R_r,...,R_MMulti-ring networks topology, r represents the serial number of ring, which opens up Flutter the node comprising N number of interconnection, ring group g_qIn each ring R_rWith the binary sequence C containing N bits_1×NIt indicates, then M A ring can use two-dimensional array C_M×NIt indicates, C_M×NIn r row s column bit c_r,sIt indicates, wherein 1≤r≤M, 1≤s≤ N does not include s-th of node c in topological network on r-th of ring_r,s=0 indicates, s-th of node in network is included on r-th of ring Use c_r,s=1 indicates；

(2) ring group set G is initialized: for u two-dimensional array C in ring group set G_M×NEach bit Position c_r,sIt is random to assign 0 or 1, ring group set G after being initialized⁰；

(3) ring group set G after judgement initialization⁰Each of ring group g_qWhether not transannular, implementation method are as follows:

Set each bit binary value 3a) as d_i,jTransannular detect array D_N×N, wherein i represents transannular detection array D_N×N Row serial number, j represent transannular detection array D_N×NColumn serial number, and 1≤i≤N, 1≤j≤N, as i ≠ j, according to d_i,jIt is corresponding Multi-ring networks topology in communication node in (i, j) node i and node j whether direct interconnection is to d_i,jAssignment, if so, To d_i,j1 is assigned, otherwise, to d_i,j0 is assigned, as i=j, to d_i,j1 is assigned, the transannular after obtaining assignment detects array D '_N×N；

Array D' 3b) is detected according to the transannular after assignment_N×NIn binary numeral d_i,jWith the presence or absence of 0, judge to initialize Ring group set G afterwards⁰In all ring group g_qWhether transannular, if so, update transannular ring group, and execute step 3a), otherwise, if mesh Ring group collection share GⁿIt indicates, ring group set G will be initialized⁰It is assigned to purpose ring group set Gⁿ, and step (4) are executed, wherein n table Show that initial value is 0 update times；

(4) purpose ring group set G is calculatedⁿIn all ring groups network congestion factor P_network1,P_network2, P_network3,...,P_networkq,...,P_networku, realize step are as follows:

4a) calculate ring group g_qIn L link link occupancy p₁,p₂,p₃,...,p_l,...,p_L:

Search ring group g_qQuantity t of the middle connection communication node to the ring of (i, j)_i,j, according to the two-way communication characteristic of waveguide, Deriving outgoing communication node is 2t to the number of path of (i, j)_i,j, communication node to (i, j) with non-uniform probability select communication path, obtain To communication node to (i, j) to 2t_i,jThe acquistion probability that each of the links on a path apply isAnd utilize acquistion probabilityCalculate ring group g_qL link link occupancy p₁,p₂,p₃,...,p_l,...,p_L, wherein l is ring group g_qLink Serial number, 1≤i≤N, 1≤j≤N, and i ≠ j；

4b) according to link occupancy p₁,p₂,p₃,...,p_l,...,p_L, calculate ring group g_qAverage acquistion probability P_averageq, Obtain purpose ring group set GⁿThe average acquistion probability P of middle u ring group_average1,P_average2,...,P_averageq,..., P_averageu, and according to sequence from small to large, to purpose ring group set GⁿThe average acquistion probability P of middle u ring group_average1, P_average2,...,P_averageq,...,P_averageuIt is ranked up, obtains average acquistion probability sequence E₁,E₂,E₃,...,E_q,..., E_u；

4c) the link occupancy p acquired according to step 4a)₁,p₂,p₃,...,p_l,...,p_LIt is averaged with what step 4b) was acquired Acquistion probability P_average1,P_average2,...,P_averageq,...,P_averageu, calculate ring group g_qLink acquistion probability variance Obtain purpose ring group set GⁿThe link acquistion probability variance of middle u ring groupAnd it is suitable according to from small to large Sequence, to purpose ring group set GⁿThe link acquistion probability variance of middle u ring groupIt is ranked up, is accounted for With probability variance sequence F₁,F₂,F₃,...,F_q,...,F_u；

4d) the average acquistion probability sequence E acquired according to step 4b)₁,E₂,E₃,...,E_q,...,E_uIt is acquired with step 4c) Acquistion probability variance sort F₁,F₂,F₃,...,F_q,...,F_u, calculate purpose ring group set GⁿIn all ring groups network congestion Factor P_network1,P_network2,P_network3,...,P_networkq,...,P_networku；

(5) according to purpose ring group set GⁿIn all ring groups network congestion factor P_network1,P_network2, P_network3,...,P_networkq,...,P_networkuSequence from small to large, by network congestion factor P_network1,P_network2, P_network3,...,P_networkq,...,P_networkuCorresponding purpose ring group set GⁿIn all ring groups be ranked up, arranged Ring group g after sequence₁,g₂,g₃,...g_q,...,g_u, and select preceding 2N ring group g₁,g₂,...,g_q,...,g_2N；

(6) to preceding 2N ring group g₁,g₂,...,g_q,...,g_2NUpdate is optimized, purpose ring group set G is obtainedⁿ, realize Step are as follows:

6a) by preceding 2N ring group g₁,g₂,...,g_q,...,g_2NRandom pair two-by-two is carried out, obtains N to ring group v₁, v₂,...,v_w,...,v_N, wherein w is the serial number of ring group pair；

6b) to N to ring group v₁,v₂,...,v_w,...,v_NIn each ring group to v_w, carry out the Bit String friendship between ring group It changes, 2N ring group g' after obtaining cross exchanged₁,g'₂,...,g'_q,...,g'_2N；

6c) 2N ring group g' after stochastic searching cross exchanged₁,g'₂,...,g'_q,...,g'_2NIn each ring group g'_q Corresponding two-dimensional array C_M×NIn 1 bit c_r,sIf c_r,s=1, to c_r,s0 is assigned, if c_r,s=0, to c_r,sAssign 1, obtain with 2N ring group g " after machine displacement₁,g”₂,...,g”_q,...,g”_2N；

2N ring group g " after 6d) judging random permutation₁,g”₂,...,g”_q,...,g”_2NWhether transannular, if so, execute 6a), otherwise, by preceding 2N ring group g₁,g₂,...,g_q,...,g_2NWith 2N ring group g " after random permutation₁,g”₂,...,g ”_q,...,g”_2NMerge, update times n is added 1, obtains purpose ring group set Gⁿ；

(7) judge purpose ring group set GⁿUpdate times n whether be less than setting optimization update threshold T, if so, holding Row step (4) otherwise calculates purpose ring group set GⁿThe network congestion factor P of middle 4N ring group_network1,P_network2, P_network3,...,P_network4N, obtain the smallest ring group g of the congestion probability factor_min, realize setting for network on mating plate topological structure Meter.

Compared with prior art, the present invention having the advantage that

First, since the present invention is based on polycyclic topologys to carry out Topology Structure Design, more waveguide links are provided, are reduced The complexity of network implementations, and the method for using the selection the smallest polycyclic topology of network congestion probability factor, reduce mating plate Upper network blocking probability, overcomes and blocks larger problem in network on mating plate, so that the present invention, which has, realizes that simply, obstruction is general The advantages of rate is low, and communication efficiency is high, improves handling capacity.

Second, since the present invention is using the communication means of single wavelength, only need optical modulator, the photodetector of fixed wave length And the devices such as micro-ring resonator.It is not required to overcome in existing multi-wavelength light network-on-chip and use using a variety of optical devices simultaneously The problem of a large amount of optical devices, so that the present invention has the advantages that low cost.

Third is not required to use multiple wavelength carrier signals simultaneously since the present invention is using the communication means of single wavelength, gram It has taken in existing multi-wavelength communication construction that wavelength available number is limited, has been unable to satisfy asking for the extensive communication requirement of network on mating plate Topic, so that the present invention has the advantages that Scalable Performance is high.

Detailed description of the invention

Fig. 1 is implementation flow chart of the invention.

Specific embodiment

With reference to the accompanying drawing, present invention is further described in detail.

Is a kind of based on polycyclic network on mating plate Topology Structure Design method referring to Fig.1, includes the following steps:

Step (1) sets ring group set G: including u ring group g₁,g₂,g₃,...,g_q,...,g_u, q represents the serial number of ring group, Each ring group indicates to include M ring R₁,R₂,...,R_r,...,R_MMulti-ring networks topology, r represents the serial number of ring, the multi-ring network Network topology includes the node of N number of interconnection, ring group g_qIn each ring R_rWith the binary sequence C containing N bits_1×NIt indicates, Then M ring can use two-dimensional array C_M×NIt indicates, C_M×NIn r row s column bit c_r,sIt indicates, wherein 1≤r≤M, 1≤s ≤ N does not include s-th of node c in topological network on r-th of ring_r,s=0 indicates, s in topological network is included on r-th of ring A node c_r,s=1 indicates；

Step (2) initializes ring group set G: for u two-dimensional array C in ring group set G_M×NEach Bit c_r,sIt is random to assign 0 or 1, ring group set G after being initialized⁰；

Ring group set G after step (3) judgement initialization⁰Each of ring group g_qWhether not transannular, implementation method are as follows:

Step 3a) each bit binary value is set as d_i,jTransannular detect array D_N×N, wherein i represents transannular detection array D_N×NRow serial number, j represent transannular detection array D_N×NColumn serial number, and 1≤i≤N, 1≤j≤N, as i ≠ j, according to d_i,j Communication node in corresponding multi-ring networks topology in (i, j) node i and node j whether direct interconnection is to d_i,jAssignment, if It is, to d_i,j1 is assigned, otherwise, to d_i,j0 is assigned, as i=j, to d_i,j1 is assigned, the transannular after obtaining assignment detects array D'_N×N；

Each binary system in transannular detection array is used to store corresponding node i and whether node j passes through a ring Direct interconnection is got up, i.e., whether meets the condition that transannular can not communicate in network between any two node；When not transannular, There is no need to complicated multiport optical routers for Interface design at each node, to simplify structure.

Step 3b) according to the transannular detection array D' after assignment_N×NIn binary numeral d_i,jWith the presence or absence of 0, judgement is just Ring group set G after beginningization⁰In all ring group g_qWhether transannular, if so, update transannular ring group, and execute step 3a), otherwise, If purpose ring group collection, which shares, indicates Gⁿ, ring group set G will be initialized⁰It is assigned to purpose ring group set Gⁿ, and step (4) are executed, wherein N indicates that initial value is 0 update times；

Ring group set G after initialization⁰In the corresponding transannular of each ring group detect array D'_N×N, corresponding to each ring group Transannular detects array D'_N×NAbove-mentioned judgement is all carried out, ring group set G after initialization can be obtained⁰In each ring group whether across Ring；

Step (4) calculates purpose ring group set GⁿIn all ring groups network congestion factor P_network1,P_network2, P_network3,...,P_networkq,...,P_networku, realize step are as follows:

Step 4a) calculate ring group g_qIn L link link occupancy p₁,p₂,p₃,...,p_l,...,p_L:

Search ring group g_qQuantity t of the middle connection communication node to the ring of (i, j)_i,j, according to the two-way communication characteristic of waveguide, Deriving outgoing communication node is 2t to the number of path of (i, j)_i,j, communication node to (i, j) with non-uniform probability select communication path, obtain To communication node to (i, j) to 2t_i,jThe acquistion probability that each of the links on a path apply isWherein 1≤i≤N, 1≤ J≤N, and i ≠ j, and utilize acquistion probabilityCalculate ring group g_qL link link occupancy p₁,p₂,p₃,..., p_l,...,p_L, its calculation formula is:

Wherein, l represents ring group g_qLink serial number, H indicates ring R where link l_rInterstitial content, x, y indicate in ring R_rOn node ID, and x ≠ y, to ring group g_qL link calculation above formula can obtain ring group g_qL link link occupy Rate p₁,p₂,p₃,...,p_l,...,p_L；

Step 4b) according to link occupancy p₁,p₂,p₃,...,p_l,...,p_L, calculate ring group g_qAverage acquistion probability P_averageq, its calculation formula is:

To purpose ring group set GⁿMiddle u ring group calculates above formula, obtains purpose ring group set GⁿMiddle being averaged for u ring group accounts for Use probability P_average1,P_average2,...,P_averageq,...,P_averageu, and according to sequence from small to large, to purpose ring group collection Close GⁿThe average acquistion probability P of middle u ring group_average1,P_average2,...,P_averageq,...,P_averageuIt is ranked up, obtains Average acquistion probability sequence E₁,E₂,E₃,...,E_q,...,E_u, for example, if average acquistion probability is P_averageqRing group g_qAccording to from Small the 3rd come to big sequence in u ring group, then E_qValue be 3；

Step 4c) the link occupancy p that is acquired according to step 4a)₁,p₂,p₃,...,p_l,...,p_LIt is acquired with step 4b) Average acquistion probability P_average1,P_average2,...,P_averageq,...,P_averageu, calculate ring group g_qLink acquistion probability varianceIts calculation formula is:

Wherein o is the serial number of link, to purpose ring group set GⁿMiddle u ring group calculates above formula, obtains purpose ring group set GⁿIn The link acquistion probability variance of u ring groupAnd according to sequence from small to large, to purpose ring group set GⁿThe link acquistion probability variance of middle u ring groupIt is ranked up, obtains acquistion probability variance sequence F₁, F₂,F₃,...,F_q,...,F_u, for example, if link acquistion probability variance isRing group g_qU are come according to sequence from small to large The 5th in ring group, then F_qValue be 5；

Step 4d) the average acquistion probability that is acquired according to step 4b) sorts E₁,E₂,E₃,...,E_q,...,E_uWith step 4c) The acquistion probability variance sequence F acquired₁,F₂,F₃,...,F_q,...,F_u, calculate purpose ring group set GⁿIn all ring groups network Congestion factor P_network1,P_network2,P_network3,...,P_networkq,...,P_networku, its calculation formula is:

P_networkq=α E_q+(1-α)F_q

Wherein α is adjustable parameter, 0.5 is taken under normal conditions, to purpose ring group set GⁿMiddle u ring group calculates above-mentioned public affairs Formula can obtain ring group set GⁿIn all ring groups network congestion factor P_network1,P_network2,P_network3,..., P_networkq,...,P_networku；

Consider link acquistion probability variance the reason of be, it is undesirable in ring group g_qIn have the link occupancy ratio of certain link Other links are much higher, although acquistion probability average in this way is smaller, due to there is the link occupancy of a link too high, hold Therefore easily blocking, when considering average acquistion probability, also needs in this way, to will lead to network blockage serious for the blocking of some link Consider link acquistion probability variance.

Step (5) is according to purpose ring group set GⁿIn all ring groups network congestion factor P_network1,P_network2, P_network3,...,P_networkq,...,P_networkuSequence from small to large, to network congestion factor P_network1,P_network2, P_network3,...,P_networkq,...,P_networkuCorresponding purpose ring group set GⁿIn all ring groups be ranked up, arranged Ring group g after sequence₁,g₂,g₃,...g_q,...,g_u, and select preceding 2N ring group g₁,g₂,...,g_q,...,g_2N；

Step (6) is to preceding 2N ring group g₁,g₂,...,g_q,...,g_2NUpdate is optimized, purpose ring group set G is obtainedⁿ, Realize step are as follows:

Step 6a) by preceding 2N ring group g₁,g₂,...,g_q,...,g_2NRandom pair two-by-two is carried out, obtains N to ring group v₁, v₂,...,v_w,...,v_N, wherein w is the serial number of ring group pair；

Step 6b) to N to ring group v₁,v₂,...,v_w,...,v_NIn each ring group to v_w, carry out the bit between ring group String exchange, 2N ring group g' after obtaining cross exchanged₁,g'₂,...,g'_q,...,g'_2N；

Step 6c) 2N ring group g' after stochastic searching cross exchanged₁,g'₂,...,g'_q,...,g'_2NIn each ring group g'_qCorresponding two-dimensional array C_M×NIn 1 bit c_r,sIf c_r,s=1, to c_r,s0 is assigned, if c_r,s=0, to c_r,s1 is assigned, is obtained 2N ring group g " after random permutation₁,g”₂,...,g”_q,...,g”_2N；

Step 6d) judge 2N ring group g " after random permutation₁,g”₂,...,g”_q,...,g”_2NWhether transannular, if so, holding Row step 6a), otherwise, by preceding 2N ring group g₁,g₂,...,g_q,...,g_2NWith 2N ring group g " after random permutation₁,g ”₂,...,g”_q,...,g”_2NMerge, update times n is added 1, obtains purpose ring group set Gⁿ, at this point, ring group set GⁿIn Ring group number u=4N；

Step (7) judges purpose ring group set GⁿUpdate times n whether be less than setting optimization update threshold T, if It is to execute step (4), otherwise, according to the calculation formula in above-mentioned steps (4), calculates purpose ring group set GⁿMiddle 4N ring group Network congestion factor P_network1,P_network2,P_network3,...,P_network4N, obtain the smallest ring group of the congestion probability factor g_min, realize the design of network on mating plate topological structure.

For the polycyclic topology of good performance as much as possible looked for, therefore, optimization updates threshold value and can do and repeatedly tastes Examination, to obtain the polycyclic topology that can reach required performance.

Above description is only example of the present invention, does not constitute any limitation of the invention.Obviously for It, all may be without departing substantially from the principle of the invention, structure after having understood the content of present invention and principle for one of skill in the art In the case where, carry out various modifications and variations in form and details, but these modifications and variations based on inventive concept Still within the scope of the claims of the present invention.

Claims (3)

1. a kind of based on polycyclic network on mating plate Topology Structure Design method, it is characterised in that include the following steps:

(1) ring group set G is set: including u ring group g₁,g₂,g₃,...,g_q,...,g_u, q represents the serial number of ring group, each ring group It indicates to include M ring R₁,R₂,...,R_r,...,R_MMulti-ring networks topology, r represents the serial number of ring, the multi-ring networks topology packet Node containing N number of interconnection, ring group g_qIn each ring R_rWith the binary sequence C containing N bits_1×NIt indicates, then M ring Two-dimensional array C can be used_M×NIt indicates, C_M×NIn r row s column bit c_r,sIt indicates, wherein 1≤r≤M, 1≤s≤N, r S-th of node c in topological network is not included on a ring_r,s=0 indicates, s-th of node in topological network is included on r-th of ring Use c_r,s=1 indicates；

(2) ring group set G is initialized: to u two-dimensional array C in ring group set G_M×NEach bit c_r,sAt random 0 or 1 is assigned, ring group set G after being initialized⁰；

(3) ring group set G after judgement initialization⁰Each of ring group g_qWhether not transannular, implementation method are as follows:

Set each bit binary value 3a) as d_i,jTransannular detect array D_N×N, wherein i represents transannular detection array D_N×NRow sequence Number, j represents transannular detection array D_N×NColumn serial number, and 1≤i≤N, 1≤j≤N, as i ≠ j, according to d_i,jIt is corresponding polycyclic Communication node in network topology in (i, j) node i and node j whether direct interconnection is to d_i,jAssignment, if so, to d_i,jIt assigns 1, otherwise, to d_i,j0 is assigned, as i=j, to d_i,j1 is assigned, the transannular after obtaining assignment detects array D'_N×N；

Array D' 3b) is detected according to the transannular after assignment_N×NIn binary numeral d_i,jWith the presence or absence of 0, ring after initialization is judged Group set G⁰In all ring group g_qWhether transannular, if so, update transannular ring group, and execute step 3a), otherwise, if purpose ring Group collection shares GⁿIt indicates, ring group set G will be initialized⁰It is assigned to purpose ring group set Gⁿ, and step (4) are executed, wherein n is indicated just The update times that initial value is 0；

(4) purpose ring group set G is calculatedⁿIn all ring groups network congestion factor P_network1,P_network2,P_network3,..., P_networkq,...,P_networku, realize step are as follows:

4a) calculate ring group g_qIn L link link occupancy p₁,p₂,p₃,...,p_l,...,p_L:

Search ring group g_qQuantity t of the middle connection communication node to the ring of (i, j)_i,j, according to the two-way communication characteristic of waveguide, derive Communication node is 2t to the number of path of (i, j)_i,j, communication node to (i, j) with non-uniform probability select communication path, communicated Node is to (i, j) to 2t_i,jThe acquistion probability that each of the links on a path applyAnd utilize acquistion probabilityIt calculates Ring group g_qL link link occupancy p₁,p₂,p₃,...,p_l,...,p_L, wherein 1≤i≤N, 1≤j≤N, and i ≠ j, p_lRepresent the link occupancy of the l articles link, calculation formula are as follows:

Wherein, l represents ring group g_qLink serial number, H indicates ring R where link l_rInterstitial content, x, y indicate in ring R_rOn Node ID, and x ≠ y, to ring group g_qL link calculation above formula can obtain ring group g_qL link link occupancy p_l；

4b) according to link occupancy p₁,p₂,p₃,...,p_l,...,p_L, calculate ring group g_qAverage acquistion probability P_averageq, obtain Purpose ring group set GⁿThe average acquistion probability P of middle u ring group_average1,P_average2,...,P_averageq,...,P_averageu, and According to sequence from small to large, to purpose ring group set GⁿThe average acquistion probability P of middle u ring group_average1,P_average2,..., P_averageq,...,P_averageuIt is ranked up, obtains average acquistion probability sequence E₁,E₂,E₃,...,E_q,...,E_u；

4c) the link occupancy p acquired according to step 4a)₁,p₂,p₃,...,p_l,...,p_LThe average occupancy acquired with step 4b) Probability P_average1,P_average2,...,P_averageq,...,P_averageu, calculate ring group g_qLink acquistion probability varianceObtain mesh Ring group set GⁿThe link acquistion probability variance of middle u ring groupAnd according to sequence from small to large, To purpose ring group set GⁿThe link acquistion probability variance of middle u ring groupIt is ranked up, obtains occupying general Rate variance sequence F₁,F₂,F₃,...,F_q,...,F_u；

4d) the average acquistion probability sequence E acquired according to step 4b)₁,E₂,E₃,...,E_q,...,E_uIt is accounted for what step 4c) was acquired With probability variance sequence F₁,F₂,F₃,...,F_q,...,F_u, calculate purpose ring group set GⁿIn all ring groups the network congestion factor P_network1,P_network2,P_network3,...,P_networkq,...,P_networku, the network congestion factor P of q-th of ring group_networkq's Calculation formula are as follows:

P_networkq=α E_q+(1-α)F_q

Wherein α is adjustable parameter, value 0.5；

(5) according to purpose ring group set GⁿIn all ring groups network congestion factor P_network1,P_network2,P_network3,..., P_networkq,...,P_networkuSequence from small to large, to network congestion factor P_network1,P_network2,P_network3,..., P_networkq,...,P_networkuCorresponding purpose ring group set GⁿIn all ring groups be ranked up, the ring group g after being sorted₁, g₂,g₃,...g_q,...,g_u, and select preceding 2N ring group g₁,g₂,...,g_q,...,g_2N；

(6) to preceding 2N ring group g₁,g₂,...,g_q,...,g_2NUpdate is optimized, purpose ring group set G is obtainedⁿ, realize step Are as follows:

6a) by preceding 2N ring group g₁,g₂,...,g_q,...,g_2NRandom pair two-by-two is carried out, obtains N to ring group v₁,v₂,..., v_w,...,v_N, wherein w is the serial number of ring group pair；

6b) to N to ring group v₁,v₂,...,v_w,...,v_NIn each ring group to v_w, the Bit String exchange between ring group is carried out, is obtained 2N ring group g ' after to cross exchanged₁,g'₂,...,g'_q,...,g'_2N；

6c) 2N ring group g ' after stochastic searching cross exchanged₁,g'₂,...,g'_q,...,g'_2NIn each ring group g'_qIt is corresponding Two-dimensional array C_M×NIn 1 bit c_r,sIf c_r,s=1, to c_r,s0 is assigned, if c_r,s=0, to c_r,s1 is assigned, is set at random 2N ring group g " after changing₁,g″₂,...,g″_q,...,g″_2N；

2N ring group g " after 6d) judging random permutation₁,g″₂,...,g″_q,...,g″_2NWhether transannular, if so, execute step 6a), otherwise, by preceding 2N ring group g₁,g₂,...,g_q,...,g_2NWith 2N ring group g " after random permutation₁,g″₂,...,g ″_q,...,g″_2NMerge, update times n is added 1, obtains purpose ring group set Gⁿ；

(7) judge purpose ring group set GⁿUpdate times n whether be less than setting optimization update threshold T, if so, executing step Suddenly (4) otherwise calculate purpose ring group set GⁿThe network congestion factor P of middle 4N ring group_network1,P_network2, P_network3,...,P_network4N, obtain the smallest ring group g of the congestion probability factor_min, realize setting for network on mating plate topological structure Meter.

2. according to claim 1 based on polycyclic network on mating plate Topology Structure Design method, it is characterised in that: step Rapid 4b) described in calculating ring group g_qAverage acquistion probability P_averageq, calculation formula is as follows:

3. according to claim 1 based on polycyclic network on mating plate Topology Structure Design method, it is characterised in that: step Rapid 4c) described in calculating ring group g_qLink acquistion probability varianceCalculation formula is as follows:

O is the serial number of link in formula.