A Coalitional Graph Game Approach for Minimum Transmission Broadcast in IoT Networks

Yu Wei Chan, Feng Tsun Chien, Min Kuan Chang*, Wei Chun Ho, Jason C. Hung

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


In this work, we consider the broadcast mechanisms for both reliable links and unreliable links in the Internet of Things (IoT) networks. Focusing on the minimum transmission broadcast (MTB) problem, we propose an efficient algorithm, termed as the Connected Dominating Set Algorithm based on Coalitional Graph Game (CDSA-CGG), to find the minimum connected dominating set (MCDS). Distinct from related work in the literature which adopts a non-cooperative game approach and assumes the interaction among nodes is limited to neighboring nodes, we formulate the interaction and cooperation among nodes over reliable links and over unreliable links as a connected forwarding graph based on coalitional graph game. We prove that the forwarding graph constructed by CDSA-CGG is a Nash network. In addition, we also prove that the final resulting graph is pairwise stable. The simulation results show that the proposed coalition graph game-based algorithm performs well in terms of the number of transmissions, convergence rate, and lifetime of nodes.

Original languageEnglish
Article number8978777
Pages (from-to)24385-24396
Number of pages12
JournalIEEE Access
StatePublished - 2020


  • Coalitional graph game
  • connected dominating set
  • IoT
  • minimum transmission broadcast
  • pairwise stability

Fingerprint Dive into the research topics of 'A Coalitional Graph Game Approach for Minimum Transmission Broadcast in IoT Networks'. Together they form a unique fingerprint.

Cite this