Resource allocation method for coexistence of multiple line topological industrial wireless networks

Abstract

A resource allocation method for coexistence of multiple line topological industrial wireless networks is provided. It pertains to the coexistence problem of multiple TDMA-based line topological industrial wireless networks, including three parts: lower bound analysis of scheduling delay, allocation algorithm of inter-network resources and allocation algorithm of intra-network resources. The method uses overall scheduling delay and resource utilization ratio as measurement indexes when analyzing the lower bound of delay and designing resource allocation algorithms, and selects a best node combination in each time slot to occupy as many channel resources as possible to improve the resource utilization ratio and reduce the overall scheduling delay.

Claims

1. A resource allocation method for coexistence of multiple line topological industrial wireless networks, comprising the following steps: obtaining a minimum scheduling delay value required for each network to complete scheduling; allocating resources for the networks based on the minimum scheduling delay value; and allocating intra-network resources of the networks, wherein the step of allocating resources for the networks based on the minimum scheduling delay value further comprises: assessing a priority of each network according to conditions: S.sub.r=T−t+1 and N.sub.d−N.sub.e=N.sub.c−1, S.sub.r being a minimum number of time slots required for completing scheduling, N.sub.d being a set of nodes with data packets in a node buffer, N.sub.e being a set of nodes having data packets in the node buffer and an empty parent node buffer, N.sub.c being a number of nodes with continuous data packets farthest from a gateway, t being current time, and T being a minimum scheduling delay value, when the network satisfies the conditions, accessing the network as a high priority and allocating |N.sub.e| resource blocks the network, when the network fails to sasatisfy the conditions, assessing the network as low priority, and sorting the networks in a descending order of S.sub.r, according to the required minimum number S.sub.r of time slots obtained during priority assessment, and calculating a difference between every two adjacent S.sub.r according to a first scenario in which the difference is not greater than 1 and a second scenario in which the difference is greater than 1; for the networks corresponding to the first scenario: when the difference of S.sub.r is 1, sorting the networks corresponding to S.sub.r in a descending order of S.sub.r, and combining first to N.sub.l node buffers in the networks to form a new network, wherein first N.sub.l in the new network are separated by empty identifiers, and N.sub.l represents a node label of a last node buffer with data packets; when the dif erence S.sub.r is 0, comparing a number R.sub.r of required resources of the networks corresponding to S.sub.r, sorting the corresponding networks in a descending order of R.sub.r; and combining the first to N.sub.l node buffers in the networks to form a new network, wherein the first to N.sub.l node buffers in the new network are separated by empty identifiers, and recording S.sub.r of the new network as a maximum value of S.sub.r in the corresponding networks; for the networks corresponding to the second scenario: sorting the networks in a descending order of S.sub.r and allocating N.sub.p resource blocks to each network in order, until no idle resource block remains or all the networks have the allocated resource blocks, wherein N.sub.p represents a maximum number of parallel transmission nodes.

2. The resource allocation method for coexistence of multiple line topological industrial wireless networks according to claim 1, wherein the minimum scheduling delay value is: $T=.Math.\frac{R_{\mathrm{idle}}\left(j\right)+\underset{i=1}{\overset{j}{.Math.}}{R}_o\left(i\right)}{C}.Math.$ wherein R.sub.idle(.sub.j) represents a number of idle resource blocks of j networks, and R.sub.o(i) represents a number of resource blocks occupied by network i, which are respectively represented by the following expressions: $\begin{array}{c}{R}_{\mathrm{idle}}\left(N\right)=\underset{t^{\prime }=1}{\overset{t^{\prime }=.Math.2C/N.Math.}{.Math.}}\left(C-.Math.\frac{t^{\prime }}{2}.Math.N\right),t^{\prime }=\left[1,2,3,.Math.,.Math.\frac{2C}{N}.Math.\right],\\ R_o\left(i\right)=\text{}{n}_i+\left(n_i-1\right)+.Math.+1=\frac{n_i\left(n_i+1\right)}{2},\end{array}$ N is a number of wireless networks in line topology, and a number of nodes of network i is n.sub.i, i ∈ N, and a number of available channels in the networks is C.

3. The resource allocation method for coexistence of multiple line topological industrial wireless networks according to claim 1, wherein R.sub.r=Σ.sub.k=1.sup.n.sup.i(B.sub.v.sub.ik(t).Math.B.sub.v.sub.ik(t) represents a number number of data packets in the node buffer of a scheduling node v.sub.ik at the current time t, wherein k ∈ [1, n.sub.i] and n.sub.i is a number of nodes in the network.

4. The resource allocation method for coexistence of multiple line topological industrial wireless networks according to claim 1, wherein the step of allocating intra-network resources of the networks comprises a data packet filling process and a data packet collecting process, wherein the data packet filling process further comprises: searching for a node set that meets the conditions B.sub.v.sub.ik(t)>0 and B.sub.v.sub.ik−1(t)=0, sorting in an ascending order of sequence number k and assessing and allocating resources for the nodes that meet the conditions; when C.sub.i resource blocks do not remain, completing the data packet filling process, otherwise, performing a data packet collecting process, wherein C.sub.i represents a number of resource blocks allocated to network i at the current time t; wherein the data packet collecting process further comprises: searching for nodes in the descending order of node labels from the last node v.sub.iN.sub.l with data in the node buffer, and using a node with data packets in the node buffer as a node to be scheduled and comparing with the nodes recorded in a scheduling node set V.sub.tr; when the node to be scheduled appears in the scheduling node set V.sub.tr or is a neighbor node of the node in V.sub.tr, not allocating resources to the node; otherwise, assessing and allocating resources for the node to be scheduled.

5. The resource allocation method for coexistence of multiple line topological industrial wireless networks according to claim 4, of wherein the step of assessing and allocating resources comprises the following steps: assessing the nodes, wherein when a scheduling node v.sub.ik does not result in that at least two node buffers are empty, transmitting a node k; when the scheduling node v.sub.ik results in that at least two node buffers are empty, not allocating resource blocks for the scheduling node v.sub.ik; and enabling k=k+2 to assess a node again, k being the node label, until the scheduling node v.sub.ik does not result in that the node buffers are continuously empty or v.sub.ik is the last node N.sub.l with data in the node buffer; allocating the resources for the nodes in a reverse order of a node assessment in that k=k−2; allocating resource blocks for the scheduling node v.sub.ik until all the assessed nodes obtain the resource blocks or the number of the resource blocks allocated for the network i is 0; and recording all the nodes having the allocated resource blocks into the scheduling node set V.sub.tr.

6. The resource allocation method for coexistence of multiple line topological industrial wireless networks according to claim 1, wherein the resources are resource blocks and comprise a time slot and an available channel of the time slot.

7. The resource allocation method for coexistence of multiple line topological industrial wireless networks according to claim 1, wherein the resource allocation method is used for line topological industrial wireless networks for any network number and any network size.

8. The resource allocation method for coexistence of multiple line topological industrial wireless networks according to claim 1, wherein the resource allocation method is used for multiple line topological wireless networks.

9. A resource allocation method for coexistence of multiple line topological industrial wireless networks, comprising the following steps: obtaining a minimum scheduling delay value required for each network to complete scheduling; allocating resources for the networks based on the minimum scheduling delay value; and allocating intra-network resources of the networks, wherein the step of allocating intra-network resources of the networks comprises: assessing a plurality of nodes, wherein, when a scheduling node v.sub.ik does not result in that at least two node buffers are empty, transmitting the a node k; when the scheduling node v.sub.ik results in that at least two node buffers are empty, not allocating resource blocks for the scheduling node v.sub.ik ; enabling k=k+2 to assess the scheduling node v.sub.ik again, k being the node label, until the scheduling node v.sub.ik does not result in that the node buffers are continuously empty or v.sub.ik is a last node N.sub.l with data in the node buffer; allocating the resources for the nodes in a reverse order of a node assessment in that k=k−2; allocating resource blocks for the scheduling node v.sub.ik until all the assessed nodes obtain the resource blocks or the number of the resource blocks allocated for the network i is 0; and recording all the nodes having the allocated resource blocks into a scheduling node set V.sub.tr.

Description

DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a schematic diagram of coexistence of multiple line networks of the present invention;

(2) FIG. 2 is a schematic diagram of number of data packets of network node buffers;

(3) FIG. 3 is a schematic diagram of a combined new network when a difference of required minimum time slot number S.sub.r is 1; and

(4) FIG. 4 is a schematic diagram of a combined new network when a difference of required minimum time slot number S.sub.r is 0.

DETAILED DESCRIPTION

(5) To make the purpose, the technical solution and the advantages of the present invention more clear, the present invention will be further described below in detail in combination with practical examples.

(6) The present invention proposes an optimized resource allocation method for coexistence of multiple line topological industrial wireless networks. The main idea of the present invention is: a general expression of the lower bound of the scheduling delay is provided; the minimum time slot required for each network to complete the scheduling is adequately considered to provide guidance for algorithm design; different priorities are allocated for the networks based on the analysis of the lower bound of delay, and then resources are allocated for the networks; nodes in the networks are assessed, a best node combination is selected and the number of parallel transmission nodes in each time slot is maximized, to improve the resource utilization ratio. Therefore, on the whole, the method comprises three stages: lower bound analysis of scheduling delay, allocation algorithm of inter-network resources and allocation algorithm of intra-network resources.

(7) 1. Modeling of coexistence wireless networks

(8) The method considers multiple line topological wireless networks. As shown in FIG. 1, N wireless networks exist. Each network i(i ∈ N) is composed of a gateway v.sub.i0 and a plurality of nodes v.sub.ik. k ∈ [1, n.sub.i]; V.sub.10 and V.sub.N0 respectively represent the gateways in the network 1 and the network N; V.sub.1n.sub.1 and V.sub.Nn.sub.N respectively represent nodes with labels of n.sub.1 and n.sub.N in the network 1 and the network N, wherein n.sub.1 and n.sub.N respectively represent the total number of nodes included in the network 1 and the network N except the gateways. Because different networks use heterogeneous communication protocols, a central controller is required to be responsible for communicating with multiple networks. In the initialization stage before the start of a scheduling cycle, the gateways transmit information about the number of the nodes of the corresponding networks to the central controller. The central controller generates a scheduling table based on the information about the number of available channels and the number of nodes of each network, and issues the scheduling table to the corresponding networks. After the initialization stage is completed, each node generates a data packet, and transmits the data packet to the gateway through aggregation transmission according to the scheduling table. All the nodes are synchronized for time according to IEEE 1588 standard. Herein, time is divided into multiple time slots of the same length. Each time slot allows to transmit the data packet of one node and the corresponding ACK. All the networks share a set of available channels. Because all the nodes work in the same frequency band and serious mutual interference exists between the networks and inside the networks within the same geographic range, any two nodes cannot use the same channel to transmit data in the same time slot. Each node in the network adopts a half-duplex communication mode. One node cannot receive and transmit the data packets at the same time, that is, adjacent nodes cannot obtain the resources for scheduling at the same time.

(9) 2. Lower bound analysis of scheduling delay

(10) N wireless networks exist. Each network i(i ∈ N) has n.sub.i nodes, and the number of available channels is C. The current time is t; and R.sub.idle(N) represents the number of idle resources of N wireless network, and can be calculated by the following general formula:

(11) $R_{\mathrm{idle}}\left(N\right)=\underset{t^{\prime }=1}{\overset{t^{\prime }=.Math.2C/N.Math.}{.Math.}}\left(C-.Math.\frac{t^{\prime }}{2}.Math.N\right),t^{\prime }=\left[1,2,3,.Math.,.Math.\frac{2C}{N}.Math.\right]$
R.sub.0(i) represents the number of resources occupied by the network i, and can be calculated by the fol lowing formula

(12) $R_O\left(i\right)=n_i+\left(n_i-1\right)+.Math.+1=\frac{n_i\left(n_i+1\right)}{2},$
When j satisfies the following situation,

(13) $R_{\mathrm{idle}}\left(j\right)\ge R_{\mathrm{idle}}\left(j\right)+\left(\underset{i=1}{\overset{N}{.Math.}}{R}_O\left(i\right)-\underset{i=1}{\overset{j}{.Math.}}{R}_O\left(i\right)\right)$
the general formula of the urn scheduling delay value is:

(14) $T=.Math.\frac{R_{\mathrm{idle}}\left(j\right)+\underset{i=1}{\overset{j}{.Math.}}{R}_O\left(i\right)}{C}.Math.$

(15) 3. The allocation algorithm of inter-network resources comprises the following steps:

(16) Step 1: the purpose of the present invention is to design the allocation algorithm of inter-network resources to minimize the scheduling delay. Firstly, the priority of each network is assessed, and the following two conditions shall be satisfied: S.sub.r=T−t+1; N.sub.d−N.sub.e=N.sub.c−1.

(17) Specifically, the lower bound T of the scheduling delay is used as a benchmark; at the current time t, the number of the remaining time slots is (T−t+1); S.sub.r represents the minimum number of time slots required for completing scheduling; S.sub.r=N.sub.l+2sum(max((B.sub.v.sub.ik(t)−1), 0))+(|N.sub.d|−|N.sub.r|) can be obtained by the number of data packets of node buffers in the networks at the current time, wherein N.sub.i represents a last node label with data packet in the node buffer; B.sub.v.sub.ik(t) represents the number of the data packets in the node buffer of the node v.sub.ik(k ∈ [1, n.sub.i]) at the current time t; N.sub.d represents a set of nodes with data packets in a node buffer; N.sub.e represents a set of nodes having data packets in the node buffer and an empty parent node buffer, i.e., B.sub.v.sub.ik(t)>0 and B.sub.v.sub.ik−1(t)=0. When S.sub.r=T−t+1 represents that the network is in a critical state, priority must be given to the network. Taking FIG. 2 as an example, FIG. 2 shows the number of the data packets of the node buffers in the networks at the current time. Then, the network N.sub.l=7. 2sum(max)(B.sub.v.sub.ik(t)−1), 0))=2 , |N.sub.d|=5 and |N.sub.e|=3. Therefore, the number of the minimum time slots required by the networks is S.sub.r=11.

(18) N.sub.c represents the number of nodes having continuous data packets farthest from the gateway; and |N.sub.d|−|N.sub.e|=N.sub.c−1 represents the situation that nodes with continuous data in the networks only appear in the position farthest from the gateway. Taking FIG. 2 as an example, GW represents the gateway; v.sub.1-v.sub.8 represent the nodes in the networks; and the number of data packets of each node buffer at the current time is labeled in the table in sequence. The network N.sub.c=3 and |N.sub.e|=2; and the equation |N.sub.d|−|N.sub.e|=N.sub.c−1 is satisfied. The networks that satisfy the two conditions are set as high priority, and |N.sub.e| resource blocks are allocated for each network until no idle resource block remains or all the networks with high priority have the allocated resource blocks. In addition, other networks are set as low priority.

(19) Step 2: if no idle resource remains at this time, the allocation of the inter-network resources is completed in the current time slot. If the idle resources remain, the remaining resources are allocated for the networks with low priority, and step 3 is performed.

(20) Step 3: the remaining networks with low priority are sorted in the descending order of the minimum number of time slots required to complete scheduling, and searched in the descending order. For the network having the difference between the required minimum numbers of the time slots less than or equal to 1, step 4 is performed; otherwise, for the network having the difference between the required minimum numbers of the time slots greater than 1, step 7 is performed.

(21) Step 4: for the network having the difference between the required minimum numbers of the time slots not greater than 1, the node buffers of the network nodes that satisfy the conditions are combined, and different networks are separated by 0 node buffer. Specifically, when the difference is 1, step 5 is performed; otherwise, when the difference is 0, step 6 is performed.

(22) Step 5: when the difference of the minimum number S.sub.r of the time slots required by the networks is 1, the networks are sorted in a descending order of S.sub.r; the node buffers of the node v.sub.i1 to the last node v.sub.iN.sub.l with data in the corresponding networks are combined; and different networks are separated by empty identifiers (0 node buffer). As show in FIG. 3, at this moment, the minimum number of the time slots required by the network i is 11, the minimum number of the time slots required by the network j is 12, and the difference between the minimum numbers of the time slots required by the two networks is 1. Therefore, according to the step 4, the node buffers of two network nodes are combined; and the S.sub.r value of the network j is greater than the S.sub.r value of the network i according to the rule in the step 5. Therefore, the network j is placed in the front half part, network i is placed in the back half part, and an empty identifier is placed in the middle, that is, separated by 0 node buffer.

(23) Step 6: when the difference of the minimum number of the time slots required by the networks is 0, the numbers of the resources required by the networks are sorted; the required numbers R.sub.r of the resources are combined in the descending order; the buffers of the node v.sub.i1 to the last node v.sub.iN.sub.l with data in the corresponding networks are combined; and each network is separated by empty identifier (0 node buffer). R.sub.r can be calculated by the number of the data packets in the node buffers: R.sub.r=Σ.sub.k=1.sup.n.sup.i(B.sub.v.sub.ik(t).Math.k). As show in FIG. 4, at this moment, the minimum numbers of the time slots required by the network i and the network j are 11, and the difference between the minimum numbers of the time slots required by the two networks is 0. Therefore, according to the step 4, the node buffers of two network nodes are combined; and the number of the resources required by the network i is 28 and the minimum number of the time slots required by the network j is 16 according to the rule in the step 6. Therefore, the network j is placed in the front half part, the network i is placed in the back half part, and an empty identifier is placed in the middle, that is, separated by 0 node buffer.

(24) Step 7: the networks having the difference between the required minimum numbers of the time slots greater than 1 (the networks used to calculate the difference) are sorted in the descending order.

(25) Specifically, the sorted networks comprise a combined new network. Therefore, the remaining resources are firstly allocated to the network with large S.sub.r in order, and the maximum number of resources that can be transmitted in parallel is allocated. If the resources remain at this moment, the resources are allocated for the next network until no idle resource remains or all the networks are allocated with the corresponding resources.

(26) 4. Allocation algorithm of intra-network resources

(27) The allocation of the inter-network resources is completed. Each network obtains the corresponding resources. Taking an example that the network i obtains C.sub.i resource blocks at the current time, the allocation of the intra-network resources is divided into the following steps:

(28) Step 1: the nodes are assessed, and the resources are reasonably allocated for the nodes in the networks. Specifically, two situations exist lithe node v.sub.ik is transmitted, two or more node buffers are empty and step 2 is performed; otherwise, the data packet of the node with a label of k is transmitted.

(29) Step 2: the purpose of the present invention is to select an optimal node combination to maximize the resource utilization ration, thereby achieving the purpose of minimizing the scheduling delay. Therefore, before the intra-network resources are allocated, each node to be scheduled is assessed. For the network i., if the scheduling node V.sub.ik results in that two or more node buffers are empty, resource blocks are not allocated for the node V.sub.ik and k=k+2 is held to assess the node again. Until the scheduling node V.sub.ik does not result in that the node buffers are continuously empty or V.sub.ik is the last node N.sub.l with data in the node buffer, the resources are allocated for the assessed nodes in a reverse order of the node assessment, i.e., resource blocks are allocated for V.sub.ik. k=k−2; resource blocks are allocated for the node v.sub.ik until all the assessed nodes obtain the resource blocks or the number of the resource blocks allocated for the network i is C.sub.i=0. All the nodes having the allocated resource blocks are recorded into a scheduling node set V.sub.tr, to avoid repeatedly allocating the resource blocks and simultaneously allocating the resource blocks for adjacent nodes. C.sub.i represents the number of the resource blocks allocated for the network i at the current time t.

(30) Step 3: a data packet filling process: the node set that meets the conditions B.sub.v.sub.ik(t)>0 and B.sub.v.sub.ik−1(t)=0 are searched in all the nodes of the current network; the nodes are sorted in an ascending order of sequence number i; and the step 1 is performed on the nodes for assessing and allocating resources. If C.sub.i resource blocks do not remain, the data packet filling process is completed, otherwise next judgment is needed.

(31) Step 3: a data packet collecting process: the nodes are searched forwards from the node v.sub.iN.sub.l; a node with data packets in the node butler is used as a node to be scheduled and compared with the nodes recorded in V.sub.tr; if the node to be scheduled appears in V.sub.tr or is a neighbor node of the node in V.sub.tr, the resources are not allocated to the node; otherwise, the step 1 is performed on the node to be scheduled for assessing and allocating the resources.