Patent ID: 12218882

DETAILED DESCRIPTION OF THE EMBODIMENTS

To make the objectives, technical solutions, and advantages of the present disclosure clearer, the present disclosure is further described below in detail with reference to the drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present disclosure, but not to limit the present disclosure. That is, the described embodiments are only some rather than all embodiments of the present disclosure. All other embodiments obtained by a person of ordinary skill in the art based on the embodiments of the present disclosure without creative efforts shall fall within the protection scope of the present disclosure.

A first specific embodiment of the present disclosure provides a hybrid time slot scheduling method for a wireless network. Specific steps are as follows.

Step 1: Select a node generating a periodic time slot request in a network to construct a set of periodic time slot request generation nodes, and construct a time slot request cycle set.

The selecting a node generating a periodic time slot request in a network in step 1 specifically includes:

defining, as a periodic time slot request generation node, the node periodically generating a time slot request in the network.

The set of the periodic time slot request generation nodes in step 1 is specifically as follows:
φk={N0,k,N1,k,N2,k, . . . Nn−1,k}

where φkrepresents a set of periodic time slot request generation nodes at a kthtime point, Ni,krepresents an ithnode in the set of the periodic time slot request generation nodes at the kthtime point, n represents a quantity of the periodic time slot request generation nodes, i∈[0, n−1], k∈[1, L], and L represents a quantity of time points.

The time slot request cycle set in step 1 is specifically as follows:
TAK={τ0,k, τ1,k, τ2,k, . . . τn−1,k}

where TAkrepresents a set of periodic time slot requests at the kthtime point, τi,krepresents a time slot request cycle of an ithnode in the set of the periodic time slot request generation nodes at the kthtime point, n represents the quantity of the periodic time slot request generation nodes, L represents the quantity of time points, i∈[0, n−1], and k∈[1, L].

Step 2: Select a node generating an aperiodic time slot request in the network to construct a set of aperiodic time slot request generation nodes, and construct a time set of the aperiodic time slot request generation nodes.

The selecting a node generating an aperiodic time slot request in the network in step 2 specifically includes:

defining, as an aperiodic time slot request generation node, the node generating the aperiodic time slot request in the network, where the aperiodic time slot request generated by the aperiodic time slot request generation node is defined as a sporadic time slot request.

The set of the aperiodic time slot request generation nodes in step 2 is specifically as follows:
δk={M0,k, M1,k, M2,k, . . . Mm−1,k}

where δkrepresents a set of aperiodic time slot request generation nodes at the kthtime point, Mj,krepresents a jthnode in the set of the aperiodic time slot request generation nodes at the kthtime point, m represents a quantity of the aperiodic time slot request generation nodes, L represents the quantity of time points,

k∈[1, L], and j∈[0, m−1].

The time set of the aperiodic time slot request generation nodes in step 2 is specifically as follows:

timek={(t0,k, D0,k), (t1,k, D1,k), . . . , (tm−1,k, Dm−1,k)}

where timekrepresents a time set of the aperiodic time slot request generation nodes at the kthtime point, tj,krepresents arrival time of an aperiodic time slot request of a jthnode in the time set of the aperiodic time slot request generation nodes at the kthtime point, Dj,krepresents a deadline of the aperiodic time slot request of the jthnode in the time set of the aperiodic time slot request generation nodes at the kthtime point, m represents the quantity of the aperiodic time slot request generation nodes, L represents the quantity of time points, k∈[1, L], and j∈[0, m−1]; and

a deadline Djof the time slot request is alternatively represented by a quantity of time slots between the deadline Djof the time slot request and arrival time tjof the time slot request after the time slot request arrives.

Step 3: Calculate a time slot contention scheduling parameter of each node in the set of the periodic time slot request generation nodes.

The time slot contention scheduling parameter of each node in the set of the periodic time slot request generation nodes in step 3 is specifically calculated according to the following formula:

ρi,k=BSNi,k∑i=0n-1⁢BSNi,k*BNi,k∑i=0n-1⁢BNi,k

K∈[1, L]

where BSNi,krepresents a maximum time slot interval of a backoff of node Ni,kbefore next time slot allocation, a maximum quantity of steps backed off by each node is 0 at the beginning of time slot allocation, L represents the quantity of time points, and n represents the quantity of the periodic time slot request generation nodes; and the backoff means that during time slot allocation for node Ni,k, due to existence of another node, a time slot required by node Ni,kis occupied, resulting in delayed allocation of the time slot required by node Ni,k; BNi,krepresents a total quantity of backoffs of node Ni,kbefore next time slot allocation; and at the beginning of time slot allocation, a total quantity of backoffs of each node is 0; and

a larger value of ρileads to more backoffs of node Niin time slot contention and more steps backed off: and the time slot contention scheduling parameter ρiis calculated and recorded during scheduling:

Step 4: If no aperiodic time slot request arrives, allocate a time slot to each time slot requesting node during periodic time slot scheduling.

The allocating a time slot to each time slot requesting node during periodic time slot scheduling in step 4 is constituted by initial time slot scheduling and subsequent time slot scheduling.

During the initial time slot scheduling, time slot scheduling is performed by giving priority to a shortest cycle.

The node periodically generating a time slot request in the network is defined as a periodic time slot request generation node, where the set of the periodic time slot request generation nodes is specifically as follows:
φk={N0,k, N1,k, N2,k, . . . Nn−1,k}

where φkrepresents the set of the periodic time slot request generation nodes at the kthtime point, Ni,krepresents the ithnode in the set of the periodic time slot request generation nodes at the kthtime point, n represents the quantity of the periodic time slot request generation nodes, i∈[0, n−1], k∈[1, L], and L represents the quantity of time points;

Traversal is performed on φkby using φk, wherein nodes in φ′kare sorted based on a time slot cycle of each node in φkin descending order:

φ′k={N′0,k,N′1,k,N′2,k, . . . N′n−1,k}

where the nodes in φ′kare sorted in ascending order based on sizes of time slot cycles, specifically: in φ′k, a first node, namely, N′0,k, is a node with a shortest time slot cycle, N′1,kis a node with a second shortest time slot cycle, N′2,kis a node with a third shortest time slot cycle, . . . , and N′n−1,kis a node with a longest time slot cycle; and if there are two or more nodes with a same time slot cycle, they are sorted based on their subscript numbers in φ′k, and a node with a smaller subscript number is sorted as a node with a shorter time slot cycle.

For three nodes in Table 1, after they are sorted based on sizes of their cycles, N0has a shortest cycle, N2has a second shortest cycle, and N1has a longest cycle. In this case, a result of time slot scheduling by giving priority to the shortest cycle is shown inFIG.2.

The subsequent time slot scheduling is constituted by subsequent contention-free time slot scheduling and subsequent contention-based time slot scheduling.

The subsequent contention-free time slot scheduling includes:

allocating a time slot to each node by cycle because the subsequent contention-free time slot scheduling belongs to periodic scheduling, which specifically includes:

allocating the time slot to each node based on a sorting in φ′k, in other words, allocating a time slot to N′0,kfirst, then allocating a time slot to N′1,k, and so on, until time slot requests of all the nodes are satisfied.

The subsequent contention-based time slot scheduling includes:

calculating the time slot contention scheduling parameter ρi,kof each contention node, and preferentially allocating a time slot to a node with a large value of the time slot contention scheduling parameter ρi,k.

The time slot contention scheduling parameter of each node in the set of the periodic time slot request generation nodes is specifically calculated according to the following formula:

ρi,k=BSNi,k∑i=0n-1⁢BSNi,k*BNi,k∑i=0n-1⁢BNi,k

K∈[1, L]

where BSNi,krepresents the maximum time slot interval of the backoff of node Ni,kbefore next time slot allocation, the maximum quantity of steps backed off by each node is 0 at the beginning of time slot allocation, L represents the quantity of time points, and n represents the quantity of the periodic time slot request generation nodes; and the backoff means that during time slot allocation for node Ni,k, due to the existence of the another node, the time slot required by node Ni,kis occupied, resulting in delayed allocation of the time slot required by node Ni,k; BNi,krepresents the total quantity of backoffs of node Ni,kbefore next time slot allocation; and at the beginning of time slot allocation, the total quantity of backoffs of each node is 0; and

the larger value of ρileads to more backoffs of node Niin time slot contention and more steps backed off; and the time slot contention scheduling parameter ρiis calculated and recorded during scheduling.

A node with a contention relationship is referred to as a contention node. The time slot contention scheduling parameter ρi,kof each contention node is calculated. Then the corresponding contention node is sorted in descending order based on a value of the time slot contention scheduling parameter ρi,k:
θk={C0,K, C1,K, C2,K, . . . Cm−1,K}

In θk, a time slot contention scheduling parameter α0of node C0,kis largest, a time slot contention scheduling parameter α1of C1,kis the second largest, and so on. Then, a time slot is allocated to node C0,kfirst, then a time slot is allocated to node C1,k, and so on, until time slot requests of all nodes in θkare satisfied.

Step 5: If an aperiodic time slot request, namely, the sporadic time slot request, arrives, perform rescheduling through hybrid time slot scheduling based on arrival time of the aperiodic time slot request.

In step 5, to-be-allocated time slot requests include the periodic time slot request and the aperiodic time slot request.

The performing rescheduling through hybrid time slot scheduling in step 5 includes the following sub-steps:

Step 5.1: Schedule the periodic time slot request according to the periodic scheduling method described in step 4.

Step 5.2: Search for an available time slot before a deadline of the aperiodic time slot request arrives; and if there is an available time slot, allocate a first available time slot found to the aperiodic time slot request, and end the scheduling; or if there is no available time slot, perform step 5.3.

Step 5.3: Return to step 5.1, and regard the aperiodic time slot request as a periodic time slot request with a cycle of 0 to perform time slot scheduling until the time slot scheduling is completed.

A second specific embodiment of the present disclosure provides a hybrid time slot scheduling method for a wireless network. Specific steps are as follows.

Step 1: Define a periodic time slot request.

Node Niin a network periodically generates a time slot request with a cycle of τi. Therefore, for n nodes connected to the network, the following node set φ is available:
φ={N0, N1, N2, . . . Nn−1}

For a network with three nodes, each of the three nodes periodically generates a periodic time slot request, and correspondingly, the following set is available:
φ={N0,N1,N2}

A time slot request cycle of each node is shown in Table 1.

Table 1 Time slot request cycles of the three nodes

NodeTime slot request cycleN0τ0= 4N1τ1= 7N2τ2= 5

Step 2: Define an aperiodic time slot request.

Node Mjin the network generates the aperiodic time slot request. This kind of aperiodic time slot request, also known as a sporadic time slot request, has arrival time tjand a deadline Dj. Therefore, for m nodes generating aperiodic time slot requests in the network, the following node set δ is available:
δ={M0, M1, M2, . . . . Mm−1}

In the above set, tjis represented by a number of a to-be-allocated time slot when the time slot request arrives; and Djrepresents time at which the slot request must be completed, which is alternatively represented by a quantity of time slots between Djand tjafter the time slot request arrives.

For a network with two nodes, each of the two nodes the aperiodic time slot request, and correspondingly, the following set is available:
δ={M0, M1}

In the above set, a time slot request cycle of each node is shown in Table 2.

Table 2 Time slot request cycles of the two nodes

NodeTime slot request cycleM0t0= 5, D0= 3M1t1= 3, D1= 2

Step 3: Determine a time slot contention scheduling parameter.

When a plurality of nodes initiate time slot requests, time slot scheduling is assisted by using the time slot contention scheduling parameter. For node Ni, the time slot contention scheduling parameter is αi:

αi=BSNi∑i=0n-1⁢BSNi*BNi∑i=0n-1⁢BNi

where BSNirepresents a maximum time slot interval of a backoff of node Nibefore next time slot allocation, and a maximum quantity of steps backed off by each node is 0 at the beginning of time slot allocation.

The backoff means that during time slot allocation for node Ni, due to existence of another node, a time slot required by node Niis occupied, resulting in delayed allocation of the time slot required by node Ni; BNirepresents a total quantity of backoffs of node Nibefore next time slot allocation; and at the beginning of time slot allocation, the total quantity of backoffs of each node is 0.

A larger value of αileads to more backoffs of node Niin time slot contention and more steps backed off. The time slot contention scheduling parameter αiis calculated and recorded during scheduling.

Step 4: Perform periodic time slot scheduling.

When no aperiodic time slot request arrives, periodic time slot scheduling is adopted. During periodic time slot scheduling, a time slot is allocated to each time slot requesting node, which is divided into two sub-steps: initial time slot scheduling and subsequent time slot scheduling.

During the initial time slot scheduling, time slot scheduling is performed by giving priority to a shortest cycle.

For the three nodes in Table 1, after they are sorted based on sizes of their cycles, N0has a shortest cycle, N2has a second shortest cycle, and N1has a longest cycle. In this case, a result of time slot scheduling by giving priority to the shortest cycle is shown inFIG.2.

The subsequent time slot scheduling includes subsequent contention-free time slot scheduling and subsequent contention-based time slot scheduling.

The subsequent contention-free time slot scheduling includes:

allocating a time slot to each node by cycle because the subsequent contention-free time slot scheduling belongs to periodic scheduling.

The subsequent contention-based time slot scheduling includes:

calculating the time slot contention scheduling parameter αiof each contention node, and preferentially allocating a time slot to a node with a large value of the time slot contention scheduling parameter αi.

For each node in Table 1, a conflict occurs in a 17thslot, namely, time slot 16, as shown inFIG.3. In this case, rescheduling needs to be performed.

Table 3 Parameters of the three nodes

NodeTime slot request cycleBSNiBNiαiN0τ0= 4BSN0= 0BN0= 0α0= 0N1τ1= 7BSN1= 2BN1= 1α1= 1/3N2τ2= 5BSN2= 1BN2= 1α2= 1/2

Based on the calculated time slot contention scheduling parameter αi, a time slot is preferentially allocated to N2, then a time slot is allocated to N1, and finally a time slot is allocated to N0. A scheduling result is shown inFIG.4.

Step 5: Perform hybrid time slot scheduling.

The aperiodic time slot request, namely, the sporadic time slot request, is rescheduled based on the arrival time of the aperiodic time slot request during periodic scheduling. In this case, to-be-allocated time slot requests include the periodic time slot request and the aperiodic time slot request.

A method for hybrid time slot scheduling includes the following steps:

Step 5.1: Schedule the periodic time slot request according to the periodic scheduling method described in step 4.

Step 5.2: Search for an available time slot before a deadline of the aperiodic time slot request arrives; and if there is an available time slot, allocate a first available time slot found to the aperiodic time slot request, and end the scheduling; or if there is no available time slot, perform step 5.3.

Step 5.3: Return to step 5.1, and regard the aperiodic time slot request as a periodic time slot request with a cycle of 0 to perform time slot scheduling until the time slot scheduling is completed.

For the nodes N1, N2, N3, M1and M2in Table 1 and Table 2, according to step 1 above, a result of periodic time slot scheduling is obtained, as shown inFIG.2; and according to step 2, a time slot request of node M1arrives first, and the time slot request can be allocated to slot2and slot3. Based on the scheduling result shown inFIG.2, slot3is available, and the aperiodic time slot request of node M1is allocated to slot3, as shown inFIG.5. When a time slot request of node M0arrives, the time slot request can be allocated to slot4, slot5and slot6. Based on a scheduling result shown inFIG.5, slot5is available, and the aperiodic time slot request of node M0is allocated to slot5.

The specific embodiments described in the present disclosure are merely illustrative of the spirit of the present disclosure. A person skilled in the art can make various modifications or supplements to the specific embodiments described or replace them in a similar manner, but it may not depart from the spirit of the present disclosure or the scope defined by the appended claims.