Decentralized design of consensus protocols with minimal communication links based on directed spanning tree

إليك ملخص تقني مفصل للورقة البحثية بعنوان "التصميم اللامركزي لبروتوكولات التوافق باستخدام حد أدنى من روابط الاتصال بناءً على الشجرة الموجهة الممتدة" من تأليف يانغتشو تشن ولانهو تشاو.

1. بيان المشكلة

تعالج الورقة تحديين حرجين في التحكم في التوافق للأنظمة متعددة الوكلاء (MASs):

1. التصميم اللامركزي: تعتمد بروتوكولات التوافق الحالية غالبًا على ضبط المعلمات بشكل مركزي أو تتطلب من جميع الوكلاء استخدام مصفوفات كسب تحكم متطابقة، مما يحد من المرونة والقابلية للتوسع. يسعى المؤلفون إلى إيجين طريقة يمكن لكل وكيل من خلالها تصميم مصفوفة التغذية الراجعة الخاصة به بشكل مستقل.
2. الحد الأدنى من الاتصال: تتطلب البروتوكولات الموزعة التقليدية غالبًا من الوكلاء التواصل مع جميع جيرانهم في وقت واحد، مما يؤدي إلى حركة بيانات عالية وازدحام محتمل في الشبكة. الهدف هو تحقيق التوافق باستخدام أقل عدد ممكن من روابط الاتصال.

تتمثل المشكلة الجوهرية في تصميم بروتوكول تحكم موزع للأنظمة متعددة الوكلاء الخطية يضمن توافق الحالة التقاربي باستخدام المعلومات من الجيران فقط كما هي محددة بواسطة شجرة موجهة ممتدة (DST)، بدلاً من رسم الاتصال الكامل.

2. المنهجية

تعتمد المنهجية المقترحة على نهج التحويل الخطي لتحويل مشكلة التوافق إلى مشكلة استقرار مخرجات لامركزية.

أ. تحويل المشكلة عبر الشجرة الموجهة الممتدة (DST)

• تمثيل الرسم البياني: يتم نمذجة طوبولوجيا الاتصال كرسم بياني موجه مرجح $G$. يفترض المؤلفون وجود شجرة موجهة ممتدة (DST) $T$ داخل $G$، مع عقدة جذر محددة (العقدة $N$).
• حالات الحواف الأساسية: بدلاً من تتبع حالة كل وكيل، يتم تحويل النظام لتتبع حالات الحواف الأساسية ($y_i = x_{k_i} - x_i$)، حيث $k_i$ هو العقدة الأب للعقدة $i$ في الـ DST.
• الرسم الخطي: باستخدام Lemma 1، يثبت المؤلفون أن أي حالة حافة في الرسم البياني الكامل يمكن تمثيلها خطيًا بواسطة حالات الحواف الأساسية في الـ DST. يسمح هذا باختزال نظام الـ $N$ وكيل إلى نظام من $N-1$ من ديناميكيات الحافة الأساسية.

ب. استقرار المخرجات اللامركزي

• يتم تحويل مشكلة التوافق بشكل مكافئ إلى مشكلة استقرار تغذية راجعة للمخرجات اللامركزية.
• يتم نمذجة النظام كالتالي:
  $$\dot{y} = A^* y + B^* u$$
  $$z = C^* y$$
  حيث $y$ هو متجه حالة الحافة الأساسية، والمخرج $z$ يمثل المعلومات المتاحة لكل وكيل.
• معيار الاستقرار: يحقق النظام التوافق إذا وفقط إذا كان النظام ذو الحلقة المغلقة مستقرًا تقاربيًا. يتم تحليل ذلك باستخدام مفهوم الأنماط الثابتة اللامركزية (DFM). يتم اشتقاق شرط ضروري وكافٍ: يحقق النظام التوافق إذا كانت مجموعة الـ DFM لا تحتوي على أي قيم ذاتية للنظام مفتوح الحلقة ذات أجزاء حقيقية غير سالبة.

ج. تصميم البروتوكول مع حد أدنى من الروابط

تقترح الورقة حالتين تصميميتين محددتين بناءً على دور عقدة جذر الـ DST في الرسم البياني الأصلي:

1. الحالة 1: عقدة الجذر هي جذر في الرسم البياني الأصلي

   • إذا لم يكن لعقدة جذر الـ DST أي حواف واردة في الطوبولوجيا الأصلية، فهي لا تتطلب مدخل تحكم ($u_N = 0$).
   • يستخدم الوكلاء الآخرون فقط المعلومات من الأب الخاص بهم في الـ DST.
   • النتيجة: تصبح مصفوفة النظام ذات الحلقة المغلقة مصفوفة كتلية مثلثية علوية. يتحقق التوافق إذا كانت كل مصفوفة كسب محلية $K_i$ تعمل على استقرار النظام الفرعي $A - w_{i,k_i} B K_i$ (شرط هورتويتز).

2. الحالة 2: عقدة الجذر ليست جذرًا في الرسم البياني الأصلي

   • إذا كانت عقدة جذر الـ DST تستقبل معلومات من عقد أخرى في الرسم البياني الأصلي، فيجب عليها معالجة هذه المعلومات.
   • يتضمن قانون التحكم لعقدة الجذر مجموع حالات الحواف من جيرانها.
   • تحليل الاستقرار: نظرًا لأن مصفوفة النظام لم تعد مثلثية تمامًا، يستخدم المؤلفون نظرية دوائر جيرشغورين (الممتدة للمصفوفات الكتلية) لاشتقاق شروط كافية.
   • التصميم اللامركزي: تسمح الشروط لكل وكيل بتصميم الكسب الخاص به $K_i$ بناءً على المعلومات المحلية والأسلوب المعروف لجيرانه المباشرين في الـ DST، مما يضمن وقوع جميع دوائر جيرشغورين في نصف المستوى الأيسر.

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

1. طوبولوجيا اتصال دنيا: توضح الورقة أنه يمكن تحقيق التوافق باستخدام فقط الروابط المحددة بواسطة DST، وهو الحد الأدنى النظري لعدد الروابط المطلوبة للاتصال في رسم بياني موجه. وهذا يقلل بشكل كبير من عبء الاتصالات مقارنة بالبروتوكولات التي تستخدم مجموعات الجيران الكاملة.
2. إجراء تصميم لامركزي بالكامل: على عكس الطرق التقليدية التي تتطلب غالبًا مصفوفة كسب مشتركة لجميع الوكلاء أو حسابات مركزية، يسمح هذا النهج لكل وكيل بحساب مصفوفة كسب فريدة خاصة به بشكل مستقل بناءً على المعلمات المحلية وهيكل الـ DST المحدد.
3. شروط ضرورية وكافية قائمة على DFM: يضع المؤلفون رابطًا نظريًا صارمًا بين مشكلة التوافق والأنماط الثابتة اللامركزية، مما يوفر معيارًا دقيقًا للقابلية للحل.
4. تصميم محلي قائم على جيرشغورين: بالنسبة للحالة المعقدة حيث تستقبل عقدة الجذر معلومات خارجية، تقدم الورقة طريقة تصميم لامركزية عملية باستخدام دوائر جيرشغورين، متجنبة الحاجة إلى تحليل القيم الذاتية العالمي.

4. النتائج والتحقق

يتم التحقق من النتائج النظرية من خلال مثالين عدديين:

• المثال 1 (الجذر هو عقدة جذر): نظام مكون من 4 وكلاء حيث ليس لجذر الـ DST (العقدة 4) أي حواف واردة. صمم المؤلفون مصفوفات كسب متميزة ($K_1, K_2, K_3$) للوكلاء الآخرين. أظهرت عمليات المحاكاة أن حالات جميع الوكلاء تقاربت نحو قيمة مشتركة، مما يؤكد أن استخدام روابط الـ DST فقط كافٍ.
• المثال 2 (الجذر ليس عقدة جذر): نظام مكون من 6 وكلاء حيث تستقبل عقدة جذر الـ DST (العقدة 6) معلومات من العقدة 1.
  • طبق المؤلفون شروط دوائر جيرشغورين لتصميم الأوزان بالتتابع (بدءًا من جيران الجذر).
  • أكدت عمليات المحاكاة أن النظام حقق التوافق حتى مع استقبال عقدة الجذر لبيانات خارجية.
  • أظهرت محاكاة مقارنة أنه إذا تم ضبط كسب عقدة الجذر على الصفر (تجاهل البيانات الخارجية)، فإن الوكلاء الآخرين لا يزالون يتتبعون الجذر، مما يوضح قوة الهيكل القائم على الـ DST.

5. الأهمية

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

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