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

Chen Hsu Yang, Hong Han Shuai, Chih Ya Shen, Ming Syan Chen

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
JournalIEEE Transactions on Knowledge and Data Engineering
DOIs
StateAccepted/In press - 2021

Keywords

  • Graph Convolutional Networks
  • Graph Optimization Problems
  • Meta Learning
  • Reinforcement Learning
  • Social Internet of Things

Fingerprint Dive into the research topics of 'Learning to Solve Task-Optimized Group Search for Social Internet of Things'. Together they form a unique fingerprint.

Cite this