Detailed Description
Embodiments of the present application will be described in detail below with reference to the accompanying drawings in conjunction with the embodiments.
It should be noted that the terms "first," "second," and the like in the description and the claims of the present application and the above figures are used for distinguishing between similar objects and not necessarily for describing a particular sequential or chronological order.
The embodiment of the method for dividing the target node set provided in the embodiment of the application can be executed in a server device or a similar computing device. Taking the example of running on a server device, fig. 1 is a block diagram of a hardware structure of a server device of a method for partitioning a set of target nodes according to an embodiment of the present application. As shown in fig. 1, the server device may include one or more (only one is shown in fig. 1) processor one 102 (the processor one 102 may include, but is not limited to, a microprocessor MCU, a programmable logic device FPGA, or the like, processing means) and a memory one 104 for storing data, where the server device may further include a transmission device 106 for communication functions and an input-output device 108. It will be appreciated by those of ordinary skill in the art that the architecture shown in fig. 1 is merely illustrative and is not intended to limit the architecture of the server apparatus described above. For example, the server device may also include more or fewer components than shown in FIG. 1, or have a different configuration than shown in FIG. 1.
The first memory 104 may be used to store a computer program, for example, a software program of application software and a module, such as a computer program corresponding to a method for partitioning a target node set in an embodiment of the present application, and the first processor 102 executes the computer program stored in the first memory 104 to perform various functional applications and data processing, that is, implement the above-mentioned method. Memory one 104 may include high-speed random access memory, and may also include non-volatile memory, such as one or more magnetic storage devices, flash memory, or other non-volatile solid-state memory. In some examples, the first memory 104 may further include memory remotely located with respect to the first processor 102, which may be connected to the server device via a network. Examples of such networks include, but are not limited to, the internet, intranets, local area networks, mobile communication networks, and combinations thereof.
The transmission device 106 is used to receive or transmit data via a network. Specific examples of the network described above may include a wireless network provided by a communication provider of a server device. In one example, the transmission device 106 includes a network adapter (Network Interface Controller, simply referred to as a NIC) that can connect to other network devices through a base station to communicate with the internet. In one example, the transmission device 106 may be a Radio Frequency (RF) module, which is configured to communicate with the internet wirelessly.
For a better understanding, unicast and multicast communications are briefly described below:
unicast communication is the transmission of a message from a source node to a single destination node, while multicast communication is the transmission of a message from one source node to any number of destination nodes.
It is assumed that one source multicast message is duplicated at a source node, a plurality of source multicast messages are obtained, and each source multicast message is transmitted to a specific destination node (this is called unicast-based multicast), so that multicasting can be easily implemented without hardware overhead. However, this approach is inefficient because sending multiple copies of the same message into the network not only generates a large amount of traffic, but also introduces a significant serialization delay at the injection point. Multicast communication has a significant impact on the performance of multiprocessor systems on chip.
The current multicast method based on hardware can be roughly divided into two methods of route-like routing and tree-like routing. In the tree routing method, a spanning tree is constructed at a source node and a multicast message is sent along the tree. The source node is considered the root and the target node is the leaf of the tree. In the routing process, the message is copied at the branch node and forwarded along a plurality of output channels to reach each target node in the target node set. In the route-like routing method, nodes prepare and send source messages to target nodes through a list of target nodes in a header. The message is routed along a path to first reach the first target node in the list of target nodes in the header, at which time the source message is both absorbed by the current node and passed to the corresponding output channel to continue the path to the next target node in the list. In this way, the message is ultimately delivered to all designated target nodes. Many studies have shown that path-based methods exhibit superior performance characteristics over tree-based methods. The path-based method only copies messages at the source node, and does not copy messages at other nodes of the network, so that message contention is not increased. However, the path of a route to access all target nodes may be long. To reduce the length of the multicast path, the target node may be divided into several disjoint subsets at the network interface of the source node, each subset corresponding to a separate multicast path, and one copy of the message routed.
The path partitioning method reduces latency and improves network performance by effectively partitioning the target nodes into disjoint subsets. Several path dividing methods commonly used for 2D-mesh and n-cube networks are dual path, multi-path and column path routing methods, each of which has its advantages and disadvantages. The dual path routing algorithm performs well when the network size is small, however, as the network expands, a multicast message may require a long path to be routed to all target nodes, thereby increasing latency. Compared with the dual-path routing algorithm, the multi-path routing algorithm is better, the method increases the number of independent multicast paths, and reduces the path length to a certain extent. However, this method has a problem that the target node set is unevenly divided, which may result in some multicast paths being longer and some multicast paths being shorter. Both routing algorithms are deadlock free. The column path routing algorithm divides the network into more areas according to the columns of the network, the method reduces the length of the longest path during multicast communication and improves the parallelism of the network, but because the network is divided into more target node subsets, more source message copies are needed, the time delay of a message preparation stage is increased, and the method needs to avoid network deadlock through a virtual channel.
When the source node is not in the network center area and is positioned in the network edge area, the three multicast routing algorithms all have the problem of uneven division of the network area, the dual path routing algorithm is the most serious, the multi-path routing algorithm is the next, and the column path routing algorithm is further lightened. Based on this, it is highly demanded to provide a multicast routing algorithm for reducing network delay, improving network parallelism, and further reducing the problem of uneven network area division.
In this regard, in this embodiment, a method for partitioning a target node set is provided, and fig. 2 is a flowchart of a method for partitioning a target node set according to an embodiment of the present application, as shown in fig. 2, where the flowchart includes steps S202 to S206 as follows:
Step S202, dividing a target node set according to the number of a source network node to obtain a first node set and a second node set, wherein the number of the network node in the first node set is larger than that of the source network node, the number of the network node in the second node set is smaller than that of the source network node, a plurality of target nodes are arranged in the target node set, and the target nodes are nodes in the appointed grid network, and are used for receiving a message sent by the source network node;
optionally, the designated mesh network comprises a 2D-mesh network and an n-cube network.
In an exemplary embodiment, in case the specified mesh network is a mesh network of m×n, the method further comprises, before step S202 above, using a function ofNumbering network nodes in the specified mesh network:;
wherein,And x is an integer greater than or equal to 0 and less than or equal to M-1, and y is an integer greater than or equal to 0 and less than or equal to N-1 for the coordinates of the network nodes in the designated mesh network.
Illustratively, in the case where the designated mesh network is 4*7 mesh network, after numbering the network nodes in the designated mesh network, the numbering of each mesh node is as shown in fig. 3.
Step S204, dividing the node set to be divided according to a reference routing path length to obtain a plurality of target node subsets, wherein the reference routing path length is the longest routing path length from the source network node to the target node, and the node set to be divided comprises the first node set and the second node set.
It should be noted that, the node set to be divided is a first node set or a second node set, that is, in this embodiment, the first node set and the second node set need to be divided according to the reference routing path length at the same time, so that after a plurality of target node subsets are obtained by dividing, the longest routing path length from the source network node to all the target nodes in the designated node set does not exceed the reference routing length.
In an exemplary embodiment, the dividing the node set to be divided according to the reference routing path length includes dividing the node set to be divided when the number of nodes in the node set to be divided is greater than a preset threshold. In this embodiment, the present invention is described in detail below, in this way unnecessary partitioning operations can be avoided.
It should be noted that the designated node set includes all nodes except the specific node set in the target node set, where the longest routing path length from the source network node to each target node in the specific node set exceeds the reference routing length. It should be noted that this is because the nature of the topology of the given mesh network itself determines that, regardless of how the set of target nodes is partitioned, the longest routing path length of the source network node to each target node in the particular set of nodes exceeds the reference routing length.
Dividing a target node set according to the number of a source network node to obtain a first node set and a second node set, and dividing the first node set and the second node set according to a reference route path length to obtain a plurality of target node subsets, wherein the reference route path length is the longest route path length from the source network node to the target node. By adopting the technical scheme, the target node set can be reasonably divided, and the problem that after the target node set is divided, routing paths of all nodes in the divided node subset are long due to the fact that the routing paths are used for accessing the nodes is solved.
In an exemplary embodiment, the step S204 includes the following steps S11-S12:
And S11, initially dividing the node set to be divided to obtain k node subsets, wherein the abscissa of the network node in each node subset in the k node subsets is the same, the abscissa of the network node in the i-1 node subset is smaller than the abscissa of the network node in the i node subset, and i is an integer greater than or equal to 2 and less than or equal to k. K is a positive integer greater than or equal to 2;
and step S12, performing secondary division on the k node subsets according to the reference routing path length to obtain a plurality of target node subsets.
In an exemplary embodiment, the step S12 includes storing k node subsets in a storage set, and repeatedly performing the following steps S21-S24 until the storage set is empty, to obtain a plurality of target node subsets:
Step S21, determining whether a first node subset in a storage set needs supplementary nodes according to the reference routing path length;
Step S22, when the first node subset needs to be supplemented with nodes and a second node subset exists in the storage set, part or all of the nodes in the second node subset are moved to the first node subset, wherein when all of the nodes in the second node subset are moved to the first node subset, the second node subset is deleted from the storage set;
step S23, when the first node subset needs to be supplemented with nodes and a second node subset does not exist in the storage set, determining the first node subset as a target node subset, and deleting the first node subset from the storage set;
Step S24, in the case that the first node subset does not need supplementary nodes, determining the first node subset as a target node subset, and deleting the first node subset from the storage set.
In an exemplary embodiment, the step S204 includes performing the following steps one through seven in a loop, wherein i is equal to 1 and j is equal to 1 when the following steps are performed for the first time:
Step one, determining an ith node subset in the k node subsets as a jth target node subset, and executing a step two when the ith+1th node subset exists;
Optionally, after determining the ith node subset of the k node subsets as the jth target node subset, determining the longest path length from the source node in the ith node subset as the specified value corresponding to the jth target node subset.
Step two, determining the shortest route length between the last network node in the ith node subset and the source network node, and executing step three when the shortest route length is larger than or equal to the reference route length, wherein the network node numbers in each node subset are ordered from small to large when the node set to be divided is the first node set, and the network node numbers in each node subset are ordered from large to small when the node set to be divided is the second node set;
In an exemplary embodiment, determining the shortest routing path length of the last network node in the ith subset of nodes to the source network node includesThe coordinates of the source network node areIn the case of (a), the shortest route length of the last network node in the ith node subset to the source network node is equal to。
Step three, updating the value of i to be i+1, updating the value of j to be j+1, and jumping to the step one;
Determining the number of nodes to be supplemented, and jumping to a step five, wherein the number of nodes to be supplemented is the number of network nodes to be added to the j-th target node subset;
in one exemplary embodiment, determining the number of nodes to be replenished includes calculating the number of nodes to be replenished using the following formula:;
wherein,In order to supplement the number of nodes to be supplemented,For the difference between the reference routing path length and the shortest routing path length,For the abscissa of the target node in the ith node subset,Is the abscissa of the target node in the i+1th node subset.
Step five, executing step six under the condition that the number of the nodes to be supplemented is smaller than the number of the network nodes of the (i+1) th node subset, and executing step seven under the condition that the number of the nodes to be supplemented is larger than or equal to the number of the network nodes of the (i+1) th node subset;
Step six, moving the first Q network nodes in the ith+1th node subset to the jth target node subset, updating the value of i to be i+1, updating the value of j to be j+1, and jumping to the step one, wherein Q is equal to the number of nodes to be supplemented;
And seventhly, moving all network nodes in the (i+1) th node subset to the (j) th target node subset, recalculating the number of nodes to be supplemented under the condition that the (i+2) th node subset exists, updating the value of i to be i+1, jumping to the fifth step, and exiting the loop under the condition that the (i+2) th node subset does not exist.
In one exemplary embodiment, recalculating the number of nodes to be replenished includes:
The number of nodes to be replenished is recalculated using the following formula:;
wherein,,For the number of network nodes of the i +1 node subset,For the abscissa of the target node in the i +1 node subset,For the abscissa of the target node in the i +2 node subset,And (5) the number of the nodes to be supplemented after recalculation. Note that Z is used to indicate the number of steps seven since the last execution of step three. For example, after step three is performed, step seven is performed for the first time, then z=1.
For a better understanding, the following detailed description is given:
for the followingThe specific implementation process of dividing the target node set by the 2D-mesh network is as follows:
1. according to the source nodeDividing the set of target nodes D intoAndTwo sets of which, among others,The number of the destination node is larger than the number of the source node S,The number of the destination node is smaller than the number of the source node S.
2. The sets H and L are divided by the target node abscissa.
Dividing set H into subsetsWherein i can be taken,Is the set of all target nodes with the abscissa i in the set H;
Dividing the set L into a plurality of subsetsWherein i can be taken,Is the set of all target nodes in set L with an abscissa i.
After division is completedThe nodes in the network are arranged in ascending order according to the sequence numbers of the nodes, will beThe nodes in the network are arranged in descending order according to the node serial numbers.
3. A set of routes is obtained.
Sequentially arranging the steps from i to i in order of decreasing sizeAndThe target node in (a) is scored into the route set.
Route aggregationThe subset is obtained in the following way:
assume that the reference routing path length is,Is provided with thereinThe nodes H have k subsets, i.e,,,Wherein。
(1) Aggregation of routesTaking outLast node in (a)Calculating a shortest path length from a source node to the node,. Continuing to execute (2).
(2) JudgingWhether greater than 0.
If it isIndicating that the shortest path length is larger than the reference route path length, and gathering the routesTaking outLast node in (a)And (3) synchronizing step (1).
If it isCalculating the number of nodes to be supplementedRounding down. Continuing to execute (3).
(3) Comparing the number of the next subset nodes with the number of the supplementary nodes:
If it isNumber of nodes of (a)Then takeFront of (2)Personal nodes put into a collectionIn this caseIs left inAnd each node. Order theTaking outLast node in (a)Step 3 (1) is synchronized.
If it isNumber of nodes of (a)Will thenPut into a collection all nodes of (a)In, i.e。Calculating the number of nodes to be supplementedComparison ofNumber of nodes of (a)AndThe same as in step 3 (3).
The process is cycled untilIs drawn into a set of routesIn which t1 are finally obtainedI.e. subset of routes (i.e. subset of target nodes), i.e.,,,The target nodes in these route subsets are then arranged in ascending order.
Similarly, t2 are obtainedIs a subset of the routes of (a), i.e,,,The target nodes in these route subsets are then arranged in descending order.
In an exemplary embodiment, after the step S204, the method further includes:
Step S31, under the condition that the target node set is divided into C target node subsets, C target node lists corresponding to the C target node subsets are determined, wherein the ith target node list is provided with the number of the network node in the ith target node subset, i is a positive integer greater than or equal to 1 and less than or equal to C, and C is a positive integer greater than or equal to 2;
In an exemplary embodiment, in the case that the network nodes in the ith target node subset are network nodes in the first node set, the numbers of the network nodes in the ith target node list are ordered from small to large. And under the condition that the network nodes in the ith target node subset are the network nodes in the second node set, the numbers of the network nodes in the ith target node list are ordered from big to small.
And S32, obtaining C target messages through the source network node according to the C target node lists, wherein the head of the ith target message carries the ith target node list, and the ith target message is a message to be received by the network node in the ith target node subset.
That is, after the target node set is partitioned, the source message may be replicated at the source node, and a total ofAnd (5) source messages. Each message carries a subset of routes,。
In an exemplary embodiment, the method further comprises the steps of S41-S43:
Step S41, receiving a target message at an intermediate network node in the designated grid network, and determining whether the intermediate network node is a node corresponding to the first network node number in a target node list of the head of the target message or not through the intermediate network node;
Optionally, the intermediate network node also comprises the source network node.
Step S42, copying the load part of the target message through the intermediate network node under the condition that the intermediate network node is the node corresponding to the first network node number in the target node list of the head part of the target message, deleting the first network node number in the target node list of the head part of the target message, and forwarding the target message according to the first network node number in the target node list of the head part of the target message under the condition that the updated target node list is not empty.
Step S43, forwarding the target message according to the first network node number in the target node list of the head of the target message through the intermediate network node under the condition that the intermediate network node is not the node corresponding to the first network node number in the target node list of the head of the target message.
In an exemplary embodiment, the forwarding the target message according to the first network node number in the target node list of the header of the target message includes determining, as a network node to be forwarded, a network node with a largest number among all network nodes with numbers smaller than or equal to the first network node number and a direct connection relationship with the intermediate network node in the designated mesh network and forwarding the target message to the network node to be forwarded, where the number of the intermediate network node is greater than the number of the first network node, and determining, as a network node to be forwarded, all network nodes with numbers greater than or equal to the number of the first network node and a minimum number among network nodes with a direct connection relationship with the intermediate network node in the designated mesh network and forwarding the target message to the network node to be forwarded.
That is, the network node to be forwarded may be determined by the following routing function Q, i.e. the network node to be forwarded=q (intermediate network node, first network node).
It should be noted that, the routing methods commonly used at present are all based on Hamiltonian paths, such as dual path routing method and multi-path routing method. The Hamiltonian path ensures that the network multicast path is deadlock free. The nodes are numbered from 0 according to the sequence of the nodes in the Hamilton path, as shown in figure 3, the coordinates of the nodes at the lower left corner of the mesh network are taken asEach node is denoted asA node such as sequence number 18 is denoted as a nodeOr node 18.
In FIG. 3, ""Representing nodes""Indicates a bi-directional link and the number in the upper left hand corner of the node indicates the node number. According to the routing directions, two routing directions of the bidirectional link are respectively defined as an uplink and a downlink, wherein the uplink is a unidirectional link from a node with a small sequence number to a node with a large sequence number, and the downlink is a unidirectional link from a node with a large sequence number to a node with a small sequence number.
First, consider the case of unicast communication. If the sequence number of the target node is greater than that of the source node, the route is carried out through the uplink, otherwise, the route is carried out through the downlink. Given a source node and a destination node, it can be easily observed from fig. 3 that there is always a shortest path to deliver a message. Obviously, the performance of the routing scheme depends on the choice of Hamilton path.
Let N be the 2D-mesh node set. A routing function Q is defined which is a function of,Expressed asNode w is adjacent to node a and satisfiesWherein node g is adjacent to node a.
For any two nodes a and b, a path from a to b can be selected through a P functionWherein,,,. In channel network one,In the second channel network,。
That is, the present embodiment can route from the source node using the routing function QInitially, a routing function is usedTransmitting the message to a node adjacent to the source nodeWhen the message reaches the node, judging whether the node is a node in the routing subset, if so, judging whether the node is a node in the routing subset) Then the message is replicated and absorbed at the node and the node is removed from the subset of routes, continuing to use the routing functionTransmitting a message to a nodeIf not%) Then use the routing functionTransmitting a message to a node. And (3) circulating the process until no target node exists in the target node subset, namely, the target node subset is an empty set, and ending the routing.
It should be noted that, eventually, all routing path lengthsSatisfies the following conditionsWherein, the method comprises the steps of, wherein,,,,。And the designated value corresponding to the j-th target node subset.
I.e. the minimum length of the routing path is the minimum value of all shortest paths, the maximum length is all shortest path lengths and the reference routing path lengthIs the maximum value of (a). Because all shortest paths (the shortest route length from the source node to the network target node) are determined by the nature of the topology structure of the network itself and are not in the scope of the application, the scheme provided by the application can control the route path length within a certain range in terms of the multicast route algorithm, so that the load of each route path is balanced, the network performance is improved, and the multicast route algorithm with larger route path length difference is further lightened.
For a better understanding, the following description is given in connection with specific examples:
For one ofMesh topology network, the source node is. Setting the reference routing path length as. Assume that the set of target nodes is:
the multicast routing algorithm based on the path provided by the application comprises the following specific processes:
1. according to the source nodeDividing the set of target nodes D intoAndTwo sets.
2. The sets H and L are divided by the target node abscissa.
Dividing H according to the abscissa of the target node, andThe nodes in the network are arranged in ascending order according to the sequence numbers of the nodes, the method comprises the following steps:
;
;
;
;
;
;
dividing L according to the abscissa of the target node, andThe nodes in the network are arranged in descending order of node serial numbers, the method comprises the following steps:
;
;
;
;
;
;
;
3. a set of routes is obtained.
Route aggregationThe obtaining mode of the target node set is as follows:
First order,The last node in (a) isCalculating a shortest path length from a source node to the node,Due toThe number of the nodes to be supplemented is calculated as follows:
;
Due toNumber of nodes of (a)Taking outPut into the collection the first 3 nodes of (c)In the process,At this timeThe remaining 1 node in (a)。
Order theTaking outLast node in (a)Calculating a shortest path length from a source node to the node,The number of the nodes to be supplemented is calculated as follows:
;
Due toNumber of nodes of (a)Will thenPut into a collection all nodes of (a)In, i.e。The number of the nodes to be supplemented is calculated as follows:
;
Due toNumber of nodes of (a)Taking outIs put into the collectionIn the process,At this timeThe remaining 2 nodes, i.e。
Order theTaking outLast node in (a)Calculating a shortest path length from a source node to the node,The number of the nodes to be supplemented is calculated as follows:
;
Due toNumber of nodes of (a)Taking outPut into the collection the first 3 nodes of (c)In the process,At this timeThe remaining 2 nodes, i.e。
Order theTaking outLast node in (a)Calculating a shortest path length from a source node to the node,The number of the nodes to be supplemented is calculated as follows:
;
Due toNumber of nodes of (a)Will bePut into a collection all nodes of (a)In the process,,And the routing node subset of the routing node is divided. And (3) ascending order arrangement is carried out on the target nodes in the route subsets, and finally the following steps are obtained:
;
;
;
;
Similarly, as shown in FIG. 4, obtainThe routing subsets of (a) are:
;
;
;
4. Preparing a message.
And copying the source messages at the source node to obtain 7 source messages in total. Each message carries a list of target nodes.
5. Routing is performed using a routing function Q.
To be used forIllustratively, the slave nodeInitially, a routing function is usedTransmitting the message to a node 30 adjacent to the source node, copying and absorbing the message at the node 30, and removing the node from the list of target nodes,Continuing to use the routing functionTransmitting the message to node 29, since node 29 is not a subset of routesIs provided with a plurality of target nodes, so use the routing functionThe message is transmitted to node 28. And (3) circulating the process until no target node exists in the target node list, namely, the target node list is an empty set, and ending the routing.
The routing paths of the 7 routing subsets are as shown in fig. 5, and the path lengths are respectively as follows,,,,,,。
;
;
;
。
I.e. all routing paths are of lengthWherein in FIG. 5, ""Represents a target node""Representing nodes""Represents an unused link""Means the link and routing direction used to complete the route.
It should be noted that the present application proposes a path-based multicast routing algorithm by setting a reference path lengthThe target node subset is divided into different route subsets and then routes are completed through Hamiltonian paths. The algorithm is deadlock free, reducing cost overhead.The values are often set based on requirements and experience with network performance. In addition, the maximum value of the routing path length of the method provided by the application is the shortest routing path length from the source node to the network destination node or the set reference path length, and the shortest routing path length from the source node to the network destination node is determined by the nature of the topological structure of the network itself, which is not in the scope of the application, so the scheme provided by the application can control the routing path length in a certain range in terms of the multicast routing algorithm, so that the load of each routing path is balanced, the network performance is improved, and the problem of larger difference of the routing path lengths in the multicast routing algorithm is further alleviated.
From the description of the above embodiments, it will be clear to a person skilled in the art that the method according to the above embodiments may be implemented by means of software plus the necessary general hardware platform, but of course also by means of hardware, but in many cases the former is a preferred embodiment. Based on such understanding, the technical solution of the present application may be embodied essentially or in a part contributing to the prior art in the form of a software product stored in a storage medium (e.g. ROM/RAM, magnetic disk, optical disk) comprising instructions for causing a terminal device (which may be a mobile phone, a computer, a server, or a network device, etc.) to perform the method according to the embodiments of the present application.
The embodiment also provides a device for dividing the target node set, which is used for implementing the above embodiment and the preferred implementation, and is not described in detail. As used below, the term "module" may be a combination of software and/or hardware that implements a predetermined function. While the modules described in the following embodiments are preferably implemented in software, implementation in hardware, or a combination of software and hardware, is also possible and contemplated.
Fig. 6 is a block diagram of a structure of a target node set partitioning apparatus according to an embodiment of the present application, as shown in fig. 6, including:
A first dividing module 62, configured to divide a target node set according to a number of a source network node to obtain a first node set and a second node set, where the number of a network node in the first node set is greater than the number of the source network node, the number of a network node in the second node set is less than the number of the source network node, the target node set has a plurality of target nodes, and the target nodes are nodes in the designated mesh network to receive a packet sent by the source network node;
The second dividing module 64 is configured to divide the node set to be divided according to a reference routing path length, to obtain a plurality of target node subsets, where the reference routing path length is a preset longest routing path length from the source network node to the target node, and the node set to be divided includes the first node set and the second node set.
The device divides the target node set according to the number of the source network node to obtain a first node set and a second node set, and divides the first node set and the second node set according to the reference route path length to obtain a plurality of target node subsets, wherein the reference route path length is the longest route path length from the source network node to the target node. By adopting the technical scheme, the target node set can be reasonably divided, and the problem that after the target node set is divided, routing paths of all nodes in the divided node subset are long due to the fact that the routing paths are used for accessing the nodes is solved.
In an exemplary embodiment, the apparatus further comprises a numbering module for using the following function in case the designated mesh network is a mesh network of M x NNumbering network nodes in the specified mesh network: wherein, the method comprises the steps of,And x is an integer greater than or equal to 0 and less than or equal to M-1, and y is an integer greater than or equal to 0 and less than or equal to N-1 for the coordinates of the network nodes in the designated mesh network.
In an exemplary embodiment, the second dividing module 64 is further configured to initially divide the node set to be divided to obtain k node subsets, where the abscissa of the network node in each node subset of the k node subsets is the same, the abscissa of the network node in the i-1 th node subset is smaller than the abscissa of the network node in the i-th node subset, i is an integer greater than or equal to 2 and less than or equal to k, and perform secondary division on the k node subsets according to a reference routing path length to obtain multiple target node subsets.
In an exemplary embodiment, the second partitioning module 64 is further configured to store k node subsets in a storage set, and repeatedly perform the steps of obtaining a plurality of target node subsets by determining whether a first node subset in the storage set needs to be supplemented with nodes according to a reference routing path length, moving part or all of the second node subsets to the first node subset if the first node subset needs to be supplemented with nodes and the second node subset exists in the storage set, wherein the second node subset is deleted from the storage set if all of the second node subsets are moved to the first node subset, determining the first node subset as a target node subset if the first node subset needs to be supplemented with nodes and the second node subset does not exist in the storage set, and deleting the first node subset from the storage set if the first node subset does not need to be supplemented with nodes and the first node subset is determined to be deleted from the first node subset.
In an exemplary embodiment, the second dividing module 64 is further configured to circularly execute the following steps, where i is equal to 1 and j is equal to 1 when the shortest route path length is first executed, where step one is to determine an ith node subset of the k node subsets as a jth target node subset and execute step two when the ith+1 node subset is present, exit the loop when the ith+1 node subset is not present, determine a shortest route path length between a last network node in the ith node subset and the source network node, execute step three when the shortest route path length is greater than or equal to the reference route path length, execute step four when the shortest route path length is less than the reference route path length, wherein the number of network nodes in each node subset is ordered from small to large when the node set to be divided is the first node set, add a value from small to large when the node set to be divided is the second node set to the second node set, and add a value from small to large to the fifth node in the step 1 when the number of nodes to be divided is the value of the first node set to large, and add a value from the point to the fifth node set is equal to the value of the fifth node set to the fifth node set when the number is greater than the point set to the j is the first node set to supplement node set to be added to the fifth node set, and the step 1 is updated to supplement the step 1, step six, moving the first Q network nodes in the ith+1th node subset to the jth target node subset, updating the value of i to i+1, updating the value of j to j+1, and jumping to the step one, wherein Q is equal to the number of nodes to be supplemented, step seven, moving all network nodes in the ith+1th node subset to the jth target node subset, and recalculating the number of nodes to be supplemented when the ith+2th node subset exists, updating the value of i to i+1, and jumping to the step five, and exiting the loop when the ith+2th node subset does not exist.
In an exemplary embodiment, the second partitioning module 64 is further configured to calculate the number of nodes to be supplemented using the following formula: wherein, the method comprises the steps of,In order to supplement the number of nodes to be supplemented,For the difference between the reference routing path length and the shortest routing path length,For the abscissa of the target node in the ith node subset,Is the abscissa of the target node in the i+1th node subset.
In an exemplary embodiment, the second partitioning module 64 is further configured to recalculate the number of nodes to be replenished using the following formula: wherein, the method comprises the steps of,,For the number of network nodes of the i +1 node subset,For the abscissa of the target node in the i +1 node subset,For the abscissa of the target node in the i +2 node subset,And (5) the number of the nodes to be supplemented after recalculation.
In an exemplary embodiment, the second partitioning module 64 is further configured to coordinate the last network node in the ith node subset to beThe coordinates of the source network node areIn the case of (a), the shortest route length of the last network node in the ith node subset to the source network node is equal to。
In an exemplary embodiment, the device further includes a processing module, configured to divide the node set to be divided according to a reference routing path length to obtain a plurality of target node subsets, and determine C target node lists corresponding to the C target node subsets when the target node set is divided into the C target node subsets, where the i target node list has a number of a network node in the i target node subset, i is a positive integer greater than or equal to 1 and less than or equal to C, and obtain, by the source network node, C target packets according to the C target node lists, where a header of the i target packet carries the i target node list, and the i target packet is a packet to be received by the network node in the i target node subset.
In an exemplary embodiment, in the case that the network nodes in the ith target node subset are network nodes in the first node set, the numbers of the network nodes in the ith target node list are ordered from small to large.
In an exemplary embodiment, in the case that the network nodes in the ith target node subset are network nodes in the second node set, the numbers of the network nodes in the ith target node list are ordered from big to small.
In an exemplary embodiment, the processing module is further configured to receive a target packet at an intermediate network node in the designated mesh network, determine, by the intermediate network node, whether the intermediate network node is a node corresponding to a first network node number in a target node list of a header of the target packet, copy, by the intermediate network node, a payload portion of the target packet if the intermediate network node is a node corresponding to the first network node number in the target node list of the header of the target packet, delete the first network node number in the target node list of the header of the target packet, and forward the target packet according to the first network node number in the target node list of the header of the target packet if the updated target node list is not empty.
In an exemplary embodiment, the processing module is further configured to determine, by the intermediate network node, whether the intermediate network node is a node corresponding to a first network node number in a target node list of a header of the target packet when the intermediate network node in the designated mesh network receives the target packet, and forward, by the intermediate network node, the target packet according to the first network node number in the target node list of the header of the target packet when the intermediate network node is not a node corresponding to the first network node number in the target node list of the header of the target packet.
In an exemplary embodiment, the processing module is further configured to determine, when the number of the intermediate network node is smaller than the number of the first network node, a network node with a largest number among all network nodes with numbers smaller than or equal to the number of the first network node and a direct connection relationship with the intermediate network node in the designated mesh network, as a network node to be forwarded, and forward the target packet to the network node to be forwarded, and determine, when the number of the intermediate network node is greater than the number of the first network node, a network node with a smallest number among all network nodes with numbers greater than or equal to the number of the first network node and a direct connection relationship with the intermediate network node in the designated mesh network, as a network node to be forwarded, and forward the target packet to the network node to be forwarded.
It should be noted that each of the above modules may be implemented by software or hardware, and the latter may be implemented by, but not limited to, the above modules all being located in the same processor, or each of the above modules being located in different processors in any combination.
Embodiments of the present application also provide a computer readable storage medium having a computer program stored therein, wherein the computer program is arranged to perform the steps of any of the method embodiments described above when run.
Alternatively, in the present embodiment, the above-described computer program may be configured to execute the following steps by the computer program:
S1, dividing a target node set according to the number of a source network node to obtain a first node set and a second node set, wherein the number of the network node in the first node set is larger than that of the source network node, the number of the network node in the second node set is smaller than that of the source network node, a plurality of target nodes are arranged in the target node set, and the target nodes are nodes in the appointed grid network, and are used for receiving a message sent by the source network node;
S2, dividing the node set to be divided according to a reference routing path length to obtain a plurality of target node subsets, wherein the reference routing path length is the longest routing path length from the source network node to the target node, and the node set to be divided comprises the first node set and the second node set.
In an exemplary embodiment, the computer readable storage medium may include, but is not limited to, a U disk, a Read-Only Memory (ROM), a random access Memory (Random Access Memory, RAM), a removable hard disk, a magnetic disk, or an optical disk, etc. various media in which a computer program may be stored.
An embodiment of the application also provides an electronic device comprising a memory 702 and a processor 704, the memory 702 having stored therein a computer program, the processor 704 being arranged to perform the steps of any of the method embodiments described above by means of the computer program, as shown in fig. 7.
Alternatively, in the present embodiment, the processor 704 may be configured to execute the following steps by a computer program:
S1, dividing a target node set according to the number of a source network node to obtain a first node set and a second node set, wherein the number of the network node in the first node set is larger than that of the source network node, the number of the network node in the second node set is smaller than that of the source network node, a plurality of target nodes are arranged in the target node set, and the target nodes are nodes in the appointed grid network, and are used for receiving a message sent by the source network node;
S2, dividing the node set to be divided according to a reference routing path length to obtain a plurality of target node subsets, wherein the reference routing path length is the longest routing path length from the source network node to the target node, and the node set to be divided comprises the first node set and the second node set.
Specific examples in this embodiment may refer to the examples described in the foregoing embodiments and the exemplary implementation, and this embodiment is not described herein.
Alternatively, it will be appreciated by those of ordinary skill in the art that the configuration shown in fig. 7 is merely illustrative, and that fig. 7 is not intended to limit the configuration of the electronic device described above. For example, the electronic device may also include more or fewer components (e.g., network interfaces, etc.) than shown in FIG. 7, or have a different configuration than shown in FIG. 7.
The memory 702 may be used to store software programs and modules, such as program instructions/modules corresponding to the method and apparatus for partitioning a set of target nodes in the embodiments of the present application, and the processor 704 executes the software programs and modules stored in the memory 702, thereby performing various functional applications and data processing, that is, implementing the method for partitioning a set of target nodes described above. The memory 702 may include high-speed random access memory, and may also include non-volatile memory, such as one or more magnetic storage devices, flash memory, or other non-volatile solid state memory. In some examples, the memory 702 may further include memory remotely located relative to the processor 704, which may be connected to the terminal via a network. Examples of such networks include, but are not limited to, the internet, intranets, local area networks, mobile communication networks, and combinations thereof. The memory 702 may be used to store, but is not limited to, information such as system configuration files. As an example, as shown in fig. 7, the memory 702 may include, but is not limited to, the first partition module 62 and the second partition module 64 in the partition device including the target node set. In addition, other module units in the above-mentioned dividing apparatus of the target node set may be further included, but are not limited to, and are not described in detail in this example.
Optionally, the transmission device 706 is used to receive or transmit data via a network. Specific examples of the network described above may include wired networks and wireless networks. In one example, the transmission device 706 includes a network adapter (Network Interface Controller, NIC) that can connect to other network devices and routers via a network cable to communicate with the internet or a local area network. In one example, the transmission device 706 is a Radio Frequency (RF) module that is configured to communicate wirelessly with the internet.
The electronic device further comprises a display 708 and a connection bus 710 for connecting the various modular components of the electronic device.
In other embodiments, the electronic device may be a node in a distributed system, where the distributed system may be a blockchain system, and the blockchain system may be a distributed system formed by connecting the plurality of nodes through a network communication. The nodes may form a peer-to-peer network, and any type of computing device, such as a server, a terminal, etc., may become a node in the blockchain system by joining the peer-to-peer network.
Embodiments of the application also provide a computer program product comprising a computer program which, when executed by a processor, implements the steps of any of the method embodiments described above.
Embodiments of the present application also provide another computer program product comprising a non-volatile computer readable storage medium storing a computer program which, when executed by a processor, implements the steps of any of the method embodiments described above.
Embodiments of the present application also provide a computer program comprising computer instructions stored in a computer-readable storage medium, a processor of a computer device reading the computer instructions from the computer-readable storage medium, the computer instructions being executable by a burial device to cause the computer device to perform the steps of any of the method embodiments described above.
It will be appreciated by those skilled in the art that the modules or steps of the application described above may be implemented in a general purpose computing device, they may be concentrated on a single computing device, or distributed across a network of computing devices, they may be implemented in program code executable by computing devices, so that they may be stored in a storage device for execution by computing devices, and in some cases, the steps shown or described may be performed in a different order than that shown or described herein, or they may be separately fabricated into individual integrated circuit modules, or multiple modules or steps of them may be fabricated into a single integrated circuit module. Thus, the present application is not limited to any specific combination of hardware and software.
The above description is only of the preferred embodiments of the present application and is not intended to limit the present application, but various modifications and variations can be made to the present application by those skilled in the art. Any modification, equivalent replacement, improvement, etc. made within the principle of the present application should be included in the protection scope of the present application.