To search, Click
below search items.


All
Published Papers Search Service

Title

A New Approximation Algorithm for Maximal Independent Set in Wireless Sensor Networks

Author

M. Ghanbaria,1, D.A. Mojdehb, M. Ramezania

Citation 
Vol. 17 No. 6 pp. 216221

Abstract

The unit disk graph is a mathematical model for wireless sensor networks when all sensors have the same communication radius. There are two classical optimization problems on graphs, relevant to unit disk graph, models of mobile ad hoc networks, maximal independent set of nodes, that is also a dominating set, and minimum connected dominating set.
We propose decomposition of connected unit disk graph into 1by1 boxes and two new matrices corresponding to this graph (Packing matrix and Independent vertex matrix) for approximating maximal independent set. If the graph is bounded, then the considered problems can be solved in polynomial time. We prove this fact indirectly by presenting dynamic programming algorithm and show that these results are optimal.

Keywords

Wireless network, independent set, dominating set, algorithm.

URL

http://paper.ijcsns.org/07_book/201706/20170626.pdf

