Learning to Solve Task-Optimized Group Search for Social Internet of Things

With the maturity and popularity of Internet of Things (IoT), the notion of Social Internet of Things (SIoT) has been proposed to support novel applications and networking services for the IoT in more effective and efficient ways. In this paper, we propose a new problem family, namely, Task-Optimized SIoT Selection (TOSS), to find the best group of IoT objects for a given set of tasks in the task pool. TOSS aims to select the target SIoT group such that the target SIoT group is able to easily communicate with each other while maximizing the accuracy of performing the given tasks. We propose two problem formulations, named Bounded Communication-loss TOSS (BC-TOSS) and Robustness Guaranteed TOSS (RG-TOSS), for different scenarios and prove that they are both NP-hard and inapproximable. We propose a polynomial-time algorithm with a performance guarantee for BC-TOSS, and an efficient polynomial-time algorithm to obtain good solutions for RG-TOSS. Moreover, as RG-TOSS is NP-hard and inapproximable within any factor, we further propose Structure-Aware Reinforcement Learning (SARL) to leverage the Graph Convolutional Networks (GCN) and Deep Reinforcement Learning (DRL) to effectively solve RG-TOSS. Experimental results indicate that our proposed algorithms outperform the other deterministic and learning-based baseline approaches.