الگوریتم شبه کد برای تقریب مجموعه مستقل ماکزیمال در گراف دیسک واحد

محورهای موضوعی : آمار

غلام حسن شیردل ¹ (عضو هیات علمی دانشگاه قم)
مجتبی قنبری ² (گروه ریاضی، واحد فراهان، دانشگاه ازاد اسلامی، فراهان، ایران.)
مهدی جالینوسی ³ (گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران.)

تاریخ دریافت : 1398/09/25 تاریخ پذیرش : 1398/10/25 تاریخ انتشار : 1399/10/01

کلید واژه: Keywords: Wireless network, dominating set, Honeycomb network, Independent Set, Algorithm,

چکیده مقاله :

در شبکه حسگر بی­ سیم وقتی که همه حسگرها دارای شعاع ارتباطی یکسانی باشند، از گراف دیسک­ واحد برای مدل­ سازی آن شبکه استفاده می‌شود. به این ترتیب دو مساله بهینه ­سازی زیر مورد تحقیق محققان واقع شده است: مجموعه مستقل ماکزیمال در شبکه و مینیمال مجموعه احاطه کننده شبکه. با توجه به NP- سخت بودن هر دو مساله فوق، الگوریتم‌های متعدّدی برای تقریب آنها تا کنون ارائه شده است. گراف لانه­ زنبوری مسطح از به هم پیوستن تعدادی شش ­ضلعی منتظم ­به ­دست می ­آید، به طوری که دو شش ضلعی مجاور دارای یک لبه مشترک هستند. چندین مطالعه در مورد رفتار ساختار لانه زنبوری انجام شده­ است. تعداد نتایج در این زمینه زیاد و همواره در حال افزایش است. در این مقاله، با استفاده از گراف لانه ­زنبوری و روش‌های ماتریسی، الگوریتمی برای تقریب مجموعه مستقل ماکزیمال شبکه ارائه داده ­ایم. اگر گراف کران­ دار باشد مساله ­های مد نظر را می ­توان در زمان چند جمله ­ای حل کرد. در پایان نیز، درستی الگوریتم و پیچیدگی آن را به دست آورده و با یک مثال عددی آن را بررسی کرده­ ایم.

چکیده انگلیسی:

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.

منابع و مأخذ:

 

[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.