## 4 Problem Formulation
### The Group Number Minimization Problem  
In a massive MTC scenario, the devices transmit data or act after the applications' trigger devices. Without using the energy-saving mechanism, the devices need to switch on the antenna to wait for the triggering message. The devices in PSM can turn off the antenna when they are idle. When applications trigger the devices to finish the task or control the devices entering an active state, the signaling messages are transmitted.  
The objective is to reduce the signaling messages subject to execution time constraints. Reducing signaling messages means reducing the number of active devices. Devices that are active at the same time can form groups, and only one device can enter the active state in each group.  
The active device minimization problem can be transformed into a group number minimization problem, representing each device \(j\) as a group \(i\) of one item. Devices can be grouped into a subset of candidate groups, \(\mathcal{P}=\{1,2,\ldots,P\}\). When groups are assigned, a group to device mapping matrix \(\mathbf{G}=[g_{ij}]_{P\times N}\) can be determined as grouping results. A sub-graph from the application point of view is required to formulate the problem with latency constraint \(\tau_{m}\) per application. The task of device mapping for a specific application \(m\) is a masked version of \(\mathbf{U}\):  
\[\mathbf{U}_{m}=[u_{i,j}^{m}]_{K\times N}=[u_{i,j}\cdot a_{m,i}]_{K\times N}. \tag{16}\]  
The matrix multiplication \(\mathbf{GU}_{m}^{\mathsf{T}}\) in dimension \(P\times K\) then refers to the number of individual task runs of application \(m\) in each group.  
To minimize the number of groups created, the problem is therefore formulated as follows:  
\[\min\sum_{i\in\mathcal{P}}y_{i} \tag{17}\]  
subject to  
\[\mathbf{GU}_{m}^{\mathsf{T}}\mathbf{t}+\mathbf{w}_{m}(\mathbf{G}) \leq\tau_{m}\cdot\mathbf{y},\quad\forall m\in\mathcal{M} \tag{18}\] \[\sum_{i\in\mathcal{P}}g_{i,j}=1,\quad\forall j\in\mathcal{N} \tag{19}\]  
\[z_{i}=\left\{\begin{array}{ll}1&\text{if}\sum_{j\in\mathcal{N}}g_{i,j}\geq 1 \\ 0&\text{otherwise}\end{array}\right.\quad\forall i\in\mathcal{P} \tag{20}\]  
\[g_{i,j}=\left\{\begin{array}{ll}1&\text{if device $j$ is assigned to group $i$}\\ 0&\text{otherwise}\end{array}\right. \tag{21}\]  
The objective of (17) is to minimize the number of assigned groups. In (18), the total task execution time plus waiting time has to be less than the constraint \(\tau_{m}\) for each application \(m\). \(\mathbf{GU}_{m}^{\mathsf{T}}\mathbf{t}\) is the required task execution time for each group with dimension \(P\times 1\). The waiting time between task executions \(\mathbf{w}_{m}(\mathbf{G})\) is the outcome of task scheduling given grouping results. Due to the exclusive access opportunities of devices in a group, a task may need to wait for other tasks to be finished based on the scheduled order. Also, in (19), a device can be assigned to only one group. The binary indicator \(z_{i}\) in (20) indicates whether or not at least one device exists in the group. In (21), the variable \(g_{i,j}\) indicates that device \(j\) is assigned to group \(i\). The formulation is a variation of the bin packing problem. Devices and groups are analogies to objects and bins; latency constraints of applications reflect bin sizes. There are several obstacles to optimally solving the problem. First, the problem is NP-hard [4]. Second, the bin-size-equivalent time constraint depends on group members and is dynamic. Third, the waiting time function is scheduling algorithm-dependent and non-linear. Fourth, frequent re-grouping needs to be avoided for practical usage.