Deterministic scheduling algorithm for wireless communication
A system and method to implement a scheduling algorithm in a communication network using time division multiple access (TDMA) are described. The system includes a plurality of devices, each device transmitting a packet of data in the communication network, and a memory device to store the scheduling algorithm. The system also includes a processor to execute the scheduling algorithm to form a deterministic packet scheduling scheme, the deterministic packet scheduling scheme being based on a base unit representing a minimum among maximum packet intervals corresponding to the plurality of devices in the communication network.
1. A system to implement a scheduling algorithm in a communication network using time division multiple access (TDMA), the system comprising:
a plurality of devices, each device transmitting a packet of data in the communication network;
a memory device configured to store the scheduling algorithm; and
a processor configured to execute the scheduling algorithm to form a deterministic packet scheduling scheme, the deterministic packet scheduling scheme being based on a base unit (BU) representing a minimum among maximum packet intervals (MPI) corresponding to the plurality of devices in the communication network.
2. The system according to claim 1 , wherein the processor is further configured to determine a packet interval based on the base unit (PIB) for each of the plurality of devices.
3. The system according to claim 2 , wherein the processor determines the PIB for each of the plurality of devices, indicated by m, using a floor function as:
PIB
m
=
⌊
log
2
MPI
m
BU
⌋
.
4. The system according to claim 2 , wherein the processor groups devices among the plurality of devices that have a same PIB into a same bin among a plurality of bins.
5. The system according to claim 4 , wherein the processor executes the scheduling algorithm in iterations, with one iteration for each of the plurality of bins, based on scheduling the packets associated with the devices in one of the plurality of bins in each of the iterations.
6. The system according to claim 1 , wherein the processor is further configured to execute the scheduling algorithm iteratively, and verify bandwidth sufficiency at each iteration based on comparing a number of unused slots and a number of the plurality of devices remaining to be scheduled.
7. The system according to claim 6 , wherein the processor verifies the bandwidth sufficiency based on determining whether:
(
2
n
+
1
*
BU
-
y
)
≥
∑
k
=
n
+
1
…
K
P
k
,
where n is a initialized to 0, y is a number of used slots, and P k is a number of the plurality of devices in each of K bins.
8. A computer-implemented method of executing a deterministic scheduling algorithm in a communication network using time division multiple access (TDMA), the method comprising:
determining a maximum packet interval (MPI) for each device among a plurality of devices of the communication network;
determining a base unit (BU) as a minimum MPI among the MPIs of the plurality of devices; and
executing iteratively, using a processor, the deterministic scheduling algorithm based on the BU.
9. The computer-implemented method according to claim 8 , further comprising determining a packet interval based on the BU (PIB) for each of the plurality of devices.
10. The computer-implemented method according to claim 9 , wherein the determining the PIB for each of the plurality of devices, indicated by m, includes using a floor function as:
PIB
m
=
⌊
log
2
MPI
m
BU
⌋
.
11. The computer-implemented method according to claim 9 , further comprising sorting the plurality of devices into bins based on the respective PIB, wherein a device among the plurality of devices with a given PIB is sorted into a same bin as another device among the plurality of devices with the given PIB.
12. The computer-implemented method according to claim 11 , wherein the executing the deterministic scheduling algorithm includes scheduling packets associated with the plurality of devices in an order corresponding to the respective bins.
13. The computer-implemented method according to claim 8 , further comprising verifying bandwidth sufficiency at each iteration of the deterministic scheduling algorithm.
14. The computer-implemented method according to claim 13 , wherein the verifying includes comparing a number of unused slots and a number of the plurality of devices remaining to be scheduled.
15. The computer-implemented method according to claim 14 , wherein the verifying includes determining whether:
(
2
n
+
1
*
BU
-
y
)
≥
∑
k
=
n
+
1
…
K
P
k
where n is a initialized to 0, y is a number of used slots, and P k is a number of the plurality of devices in each of K bins.