Hybrid Discrete Grey Wolf Optimization Approach for solving Spectrum Assignment Problem in Elastic Optical Networks

ملخص تقني: تحسين خوارزمية الذئب الرمادي المنفصلة الهجينة لتعيين الطيف في الشبكات البصرية المرنة

بيان المشكلة
تتناول الورقة البحثية مشكلة "تعيين الطيف" (SA) ضمن تحدي "التوجيه وتعيين الطيف" (RSA) الأوسع نطاقاً في الشبكات البصرية المرنة (EONs). ومع نمو حركة البيانات مدفوعة بالتطبيقات ذات النطاق الترددي العالي، أصبحت شبكات تقسيم طول الموجة (WDM) التقليدية ذات الشبكة الثابتة غير كافية. توفر الشبكات البصرية المرنة حلاً من خلال تخصيص طيف مرن باستخدام وحدات أصغر حجماً. ومع ذلك، فإن مشكلة (RSA) هي مشكلة معقدة من فئة (NP-hard)، لا سيما في الشبكات واسعة النطاق، نظراً للحاجة إلى تلبية ثلاثة قيود حاسمة في آن واحد:

1. استمرارية الطيف (Spectrum Continuity): يجب أن تظل مؤشرات فترات التردد (Frequency slot indices) متطابقة عبر جميع الروابط الفيزيائية في المسار.
2. تتابع الطيف (Spectrum Contiguity): يجب أن يشكل عرض النطاق الترددي المخصص كتلة مستمرة من فترات التردد المتجاورة دون تفتت.
3. عدم التداخل (Non-overlapping): يمكن لفترة تردد واحدة على رابط معين أن تخدم طلباً واحداً فقط في كل مرة.

الهدف المحدد لهذا العمل هو تقليل إجمالي استخدام فترات التردد (FSs) في الشبكات البصرية الكبيرة لتعزيز سعة الشبكة وكفاءتها.

المنهجية
يقترح المؤلفون خوارزمية تحسين الذئب الرمادي المنفصلة الهجينة (GWO) مدمجة مع المحاكاة التلدينية (SA)، والتي تُسمى SA-GWO.

• محسن الذئب الرمادي (GWO): تحاكي الخوارزمية الأساسية التسلسل الهرمي الاجتماعي وسلوك الصيد للذئاب الرمادية (ألفا، بيتا، دلتا، وأوميغا). وقد تم اختيارها لقدرتها القوية على الاستكشاف العالمي. ومع ذلك، يشير المؤلفون إلى أن خوارزمية (GWO) القياسية قد تعاني من التقارب المبكر والوقوع في الحد الأدنى المحلي، خاصة في مساحات البحث الكبيرة.
• التكيف المنفصل (Discrete Adaptation): بما أن مشكلة (SA) تتضمن ترتيباً منفصلاً للطلبات بدلاً من المتغيرات المستمرة، فقد قام المؤلفون بتكييف (GWO). حيث استبدلوا حسابات المسافة المعتمدة على المتجهات القياسية بـ مسافة هامينج (Hamming distance) لقياس التباين بين متجهات الحلول (تبديلات الطلبات).
• الهجنة مع المحاكاة التلدينية (SA): لمعالجة قيود (GWO) القياسية، تم دمج (SA) في آلية تحديث الموقع.
  • بدلاً من تحديث مواقع الذئاب بشكل حتمي بناءً على القادة (ألفا، بيتا، ودلتا) فقط، تقوم الخوارزمية بتوليد حل مجاور لكل ذئب باستخدام طفرة التبديل (swap mutation) المتناسبة مع مسافة هامينج.
  • يتبع قبول هذا الحل الجديد معيار ميتروبوليس (Metropolis criterion). إذا كان الحل الجديد أفضل، يتم قبوله. وإذا كان أسوأ، يتم قبوله باحتمالية $P = e^{-\Delta E/T}$، حيث $\Delta E$ هو فرق اللياقة و $T$ هي درجة الحرارة الحالية.
  • يسمح هذا القبول الاحتمالي للخوارزمية بالهروب من النهايات الصغرى المحلية، مما يوازن بين الاستكشاف والاستغلال بشكل أكثر فعالية من (GWO) وحدها.
• التقييم: يتم تقييم الحلول بناءً على أقصى عدد من فترات التردد المستخدمة، مع الالتزام بقيود نموذج تعيين الطيف بالمسافة (DSA)، بما في ذلك متطلبات حزمة الحماية (guardband).

المساهمات الرئيسية

1. الابتكار الخوارزمي: تطوير خوارزمية استدلالية هجينة (SA-GWO) مصممة خصيصاً لمشكلة تعيين الطيف المنفصلة في الشبكات البصرية المرنة.
2. تكامل الآليات: الدمج المبتكر للمحاكاة التلدينية (SA) في مرحلة تحديث موقع (GWO) لتنقية عملية البحث ومنع التقارب المبكر.
3. الصياغة المنفصلة: تكييف (GWO) للتحسين التوافقي المنفصل باستخدام مسافة هامينج وطفرات التبديل، بدلاً من الحسابات المتجهية المستمرة.

النتائج التجريبية
تم تقييم خوارزمية (SA-GWO) المقترحة باستخدام:

• التوبولوجيا: رسوم بيانية اصطناعية متنوعة تم إنشاؤها باستخدام مكتبات بايثون (NetworkX و Matplotlib)، بما في ذلك الرسوم البيانية العشوائية والرسوم البيانية الكاملة بعدد عقد يتراوح من 14 إلى 25 عقدة.
• المقارنات: تمت مقارنة النتائج مع خوارزمية "المرحلتين" (Two-Phase) المرجعية، وخوارزمية (GWO) القياسية، والحلول المثلى التي تم إنشاؤها بواسطة برنامج (CPLEX 12.9.0) (للنماذج الأصغر).

النتائج:

• الرسوم البيانية الصغيرة والمتوسطة (14–19 عقدة): تفوقت خوارزمية (SA-GWO) بشكل كبير على خوارزمية المرحلتين المرجعية. وفي كثير من الحالات، أنتجت نتائج قريبة جداً من الحلول المثلى التي وجدها (CPLEX).
• الرسوم البيانية الكبيرة (20–25 عقدة): على الرغم من أن (SA-GWO) لم تصل إلى نتائج (CPLEX) المثلى (وهو أمر متوقع في المشكلات من فئة NP-hard بهذا الحجم)، إلا أنها أظهرت تفوقاً ملحوظاً على خوارزمية (GWO) القياسية، مما قلل من أقصى عدد من فترات التردد المستخدمة.
• القابلية للتوسع: أثبت النهج الهجين كفاءته في إدارة التعقيد المتزايد مع نمو أحجام الرسوم البيانية، بينما أظهرت (GWO) القياسية فجوة أداء أكبر مقارنة بالنسخة الهجينة.

الأهمية والادعاءات
تزعم الورقة أن نهج (SA-GWO) المقترح يعزز فعلياً سعة الشبكة من خلال تحسين تخصيص فترات التردد. تكمن الأهمية الأساسية في قدرة الخوارزمية على تحقيق توازن أفضل بين الاستكشاف العالمي والاستغلال المحلي. ومن خلال دمج المحاكاة التلدينية، تخفف الطريقة من خطر الوقوع في النهايات الصغرى المحلية، وهي مشكلة شائعة في مشكلات (RSA) واسعة النط scales.

خلص المؤلفون إلى أن التقنية الهجينة تقلل بشكل كبير من تفتت الطيف وتزيد من استغلال الموارد مقارنة بالأساليب التقليدية. ويضعون هذا العمل كخطوة نحو حل مشكلات (RSA) المعقدة وواسعة النطاق حيث تصبح الطرق الدقيقة (مثل CPLEX) مكلفة حاسوبياً، مما يوفر بديلاً استدلالياً عالي الجودة.

العمل المستقبلي
حدد المؤلفون بوضوح التوجهات المستقبلية، بما في ذلك:

• توسيع الخوارزمية لتشمل سيناريوهات تعيين الطيف الديناميكي للتعامل مع متطلبات حركة البيانات في الوقت الفعلي.
• التحقيق في التحسين متعدد الأهداف لمعالجة استهلاك الطاقة وزمن الوصول (latency) في آن واحد.
• استكشاف دمج الاستدلالات القائمة على تعلم الآلة لتحسين التخصيص التنبئي للطيف.