Heuristic and Metaheuristic Approaches for the Multi-Node Allocation Problem in Large-Scale IoT Networks

Abstract

The Multi-Node Allocation (MNA) problem in Internet of Things (IoT) networks arises when application requirements exceed the capacity of a single node, requiring job distribution across multiple devices. This problem is challenging in large-scale heterogeneous environments once it involves optimizing resource utilization, bandwidth consumption, and latency within a rapidly expanding search space. This paper proposes two scalable approaches: a greedy heuristic called Demand Index Multi-Node Allocation (DI-MNA) and a hybrid evolutionary algorithm (NSGA-Hyb) that combines DI-MNA with NSGA-III. Both methods use bounded combinatorial exploration and a normalized demand index to guide the search efficiently. The approaches are evaluated on IoT networks ranging from 10 to 1000 nodes under different workload conditions and compared with an optimal Branch and Bound (B&B) algorithm for small instances. Results show that DI-MNA achieves near-optimal solutions in small networks while maintaining low computational cost as network size grows. In large-scale scenarios, DI-MNA consistently matches or outperforms the evolutionary methods and sustains runtime speedups of up to 51× over NSGA-Hyb and more than 7.8×106 over B&B. These findings demonstrate that DI-MNA provides an effective balance between solution quality, scalability, and computational efficiency for resource allocation in large-scale IoT networks.