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

الموضوعات :

غلام حسن شیردل ¹ , مجتبی قنبری ² , مهدی جالینوسی ³

1 - عضو هیات علمی دانشگاه قم
2 - گروه ریاضی، واحد فراهان، دانشگاه ازاد اسلامی، فراهان، ایران.
3 - گروه ریاضی، دانشکده علوم، دانشگاه قم، قم، ایران.

تاريخ الإرسال : 19 الإثنين , ربيع الثاني, 1441 تاريخ التأكيد : 20 الأربعاء , جمادى الأولى, 1441 تاريخ الإصدار : 06 الإثنين , جمادى الأولى, 1442

الکلمات المفتاحية: Keywords: Wireless network, dominating set, Honeycomb network, Independent Set, Algorithm,

ملخص المقالة :

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

المصادر:

 

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