A Algorithm Pseudo Code for Approximating of Maximal Independent Set in the Unit Disc Graph

Subject Areas : Statistics

Gholam Hassan Shirdel ¹ , Mojtaba Ghanbari ² , Mehdi Jalinousi ³

1 - Associate Professor at University of Qom
2 - Department of Mathematics, Farahan Branch, Islamic Azad University, Farahan, IRAN.
3 - Department of Mathematics, Faculty of Science, University of Qom, Qom, IRAN.

Received: 2019-12-16 Accepted : 2020-01-15 Published : 2020-12-21

Keywords: شبکه لانه‌زنبوری, الگوریتم, واژه‌های کلیدی: شبکه بی‌سیم, مجموعه مستقل, مجموعه احاطه‌گر,

Abstract :

The unit disk graph is used to model a wireless sensor network when all sensors have the same communication radius. Hence, the following two optimization problems have been investigated by the researchers: maximal independent set in the network and minimal network dominating set. Since these problems are Np-hard, several algorithms have been presented for their approximation. In this paper, we have presented a honeycomb graph and algorithmic matrix methods for approximating the maximal independent set in the network. Finally, we have confirmed the validity of the algorithm and its complexity and studied it with a numerical example.Keywords: Wireless network, Independent set, Dominating set, Algorithm, Honeycomb network E. Leeuwen, Approximation Algorithms for Unit Disk Graphs, technical report, institute of information and computing sciences, utrecht university, (2004), UU-CS-2004-066. N. Bourgeois, F. Della Croce, B. Escoffier. V.Th. Paschos, Fast algorithms for min inde‌pendent dominating set, Discrete Applied Mathematics 161, (2013), pp. 558-572.

References:

 

[1] K Islam, S. Akl, H. Meijer, A constant factor distributed algorithm for computing connected dominating sets in wireless sensor networks, in: Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS08), December (2008), pp. 559- 566.

 

[2] S. Surendran, S. Vijayan, Distributed Computation of Connected Dominating Set for Mul­tihop Wireless Networks, Procedia Computer Science 63, (2015), pp. 482-487.

 

[3] N. Bourgeois, F. Della Croce, B. Escoffier. V.Th. Paschos, Fast algorithms for min inde­pendent dominating set, Discrete Applied Mathematics 161, (2013), pp. 558-572.

 

[4] S. Kamei, H. Kakugawa, A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs, Theoretical Computer Science 428, (2012), pp. 80-90.

 

[5] P. M. Wightman, M.A. Labrador, A family of simple distributed minimum connected dom­inating set-based topology construction algorithm, Journal of Network and Computer Applications 24, (2011), pp. 1997-2010.

 

[6] J. Yu, L. Jia, D. Yu, G. Li, X. Cheng, Minimum connected dominating set construction in wireless networks under the beeping model, IEEE Conference on Computer Communications, (2015), pp. 972-980.

 

[7] S. Das, S. Barman, J. D. Sinha, Energy efficient routing in wireless sensor network, Procedia Technology 6, (2012), pp. 731-738.

[8] J.P. Mohantya, C. Mandal, C. Reade, A. Das, Construction of minimum connected domi­nating set in wireless sensor networks using pseudo dominating set, Ad Hoc Networks 42, (2016), pp. 61-73.

 

[9] M. Rai, S. r. Verma. S. Tapaswi, A power aware minimum connected dominating set for wireless sensor networks, Journal of Networks 4 (6), (2009), pp. 511-519.

 

[10] J. Yu, N. Wang, G. Wang, Heuristic algorithms for constructing connected dominating sets with minimum size and bounded diameter in wireless networks, in: Proceedings of Wireless Algorithms, Systems, and Applications (WASA2010), Lecture Notes in Computer Science, vol. 6221, (2010), pp. 11-20.

 

[11] E. Leeuwen, Approximation Algorithms for Unit Disk Graphs, technical report, institute of information and computing sciences, utrecht university, (2004), UU-CS-2004-066.