  In this work, we utilize the framework of compressed sensing (CS) for
distributed device detection and resource allocation in large-scale
machine-to-machine (M2M) communication networks. The devices deployed in the
network are partitioned into clusters according to some pre-defined criteria.
Moreover, the devices in each cluster are assigned a unique signature of a
particular design that can be used to indicate their active status to the
network. The proposed scheme in this work mainly consists of two essential
steps: (i) The base station (BS) detects the active clusters and the number of
active devices in each cluster using a novel block sketching algorithm, and
then assigns a certain amount of resources accordingly. (ii) Each active device
detects its ranking among all the active devices in its cluster using an
enhanced greedy algorithm and accesses the corresponding resource for
transmission based on the ranking. By exploiting the correlation in the device
behaviors and the sparsity in the activation pattern of the M2M devices, the
device detection problem is thus tackled as a CS support recovery procedure for
a particular binary block-sparse signal $x\in\mathbb{B}^N$ -- with block
sparsity $K_B$ and in-block sparsity $K_I$ over block size $d$. Theoretical
analysis shows that the activation pattern of the M2M devices can be reliably
reconstructed within an acquisition time of $\mathcal{O}(\max\{K_B\log N,
K_BK_I\log d\})$, which achieves a better scaling and less computational
complexity of $\mathcal{O}(N(K_I^2+\log N))$ compared with standard CS
algorithms. Moreover, extensive simulations confirm the robustness of the
proposed scheme in the detection process, especially in terms of higher
detection probability and reduced access delay when compared with conventional
schemes like LTE random access (RA) procedure and classic cluster-based access
approaches.
