## 5 Proposed mMTC Device Grouping Algorithms
### Previously Proposed Algorithms
#### 5.1.1 Best Fit Decreasing Solution with Dynamic Bin Size  
In the classic bin packing problems, the bin sizes are fixed. By mapping the grouping problem to a variation of bin packing, a modified version of the well-known best fit decreasing algorithm was proposed to effectively group mMTC devices with individual application latency requirements [4; 42]. The number of bins corresponds to the number of groups created, while the bin size is a combination of grouped applications' time constraints. The application time constraint is critical in the grouping and scheduling strategy. Thus, the devices were not only grouped to reduce the number of simultaneous RACH attempts but also scheduled based on a priority-based criterion involving the application's time constraint requiring services from these devices. This solution is designed to be practical and avoid frequent re-grouping. Doing so guarantees that the most urgent devices will access the network earlier in a group.  
The solution is designed to be practical to perform and can avoid frequent re-grouping. This strategy matches a more realistic scenario, as any re-grouping will affect the execution sequence of tasks in groups. A situation with the tightest time constraints is considered  
Figure 3: The task execution in groups from a device perspective.  
when applying the algorithm, and a relaxing factor \(\gamma\geq 1\) is introduced to control the extension of the final bin sizes. Applications are assumed to begin concurrently when grouping, and the time constraint in (18) becomes \(\gamma\cdot\tau_{m}\) for adjustment. In the long run, applications may start at different times, so less-saturated task requests are generally expected. The formed groups can remain unchanged and still meet latency requirements. Furthermore, when packing a device into a group, the expected per-device task execution time \(T_{m}\), equivalent to the object size, is defined with an application Poisson arrival rate of \(\lambda_{m}\). For example, referring to Figure 1, device \(N\) can run tasks 1 and 3, which can be triggered by application \(M\) or 1. So, the weighted duration of device \(N\) is  
\[T_{N}=\frac{\lambda_{1}t_{3}+\lambda_{M}t_{1}}{\lambda_{1}+\lambda_{M}}. \tag{22}\]  
The grouping problem shares the same objective with bin packing: optimizing group devices while minimizing the number of groups created. The BFD bin packing algorithm and the earliest deadline for the first scheduling are adopted. Devices are first sorted following the descending order of \(T_{n}\) and assigned to a group one by one. The device-linked tasks in a group are then scheduled in the order of corresponding application time constraints so that a task related to an application with the latest deadline can be executed first. The algorithm evaluates the device-dependent space of each group for all related applications. A device joins a group that has space to accommodate it with minimum remaining space. A new group is created automatically if no group fits the device. The process continues iteratively until no un-grouped device is left.  
According to the concept of exclusive access, only one device can connect to the network at a time in each group. The MTC device can use the Group ID instead of its ID to connect to the network. This alleviates the MTC identifier shortage (using the Group IMSI) and leads to a better resource management strategy [43]. The other benefit is the reduction in energy consumption, as other devices remain detached when one is attached. The BFD algorithm has a computational complexity of \(O(n\log n)\) and a packing performance of \((11/9)\cdot(\text{optimal number of bins})+1\)[4].