2025-11-21T23:10:16.385556

A Scalable MVDR Beamforming Algorithm That is Linear in the Number of Antennas

Herath, Gerami, Wagner et al.
The Minimum Variance Distortionless Response (MVDR) beamforming technique is widely applied in array systems to mitigate interference. However, applying MVDR to large arrays is computationally challenging; its computational complexity scales cubically with the number of antenna elements. In this paper, we introduce a scalable MVDR beamforming method tailored for massive arrays. Our approach, which is specific to scenarios where the signal of interest is below the noise floor (e.g.,~GPS), leverages the Sherman-Morrison formula, low-rank Singular Value Decomposition (SVD) approximations, and algebraic manipulation. Using our approach, we reduce the computational complexity from cubic to linear in the number of antennas. We evaluate the proposed method through simulations, comparing its computational efficiency and beamforming accuracy with the conventional MVDR approach. Our method significantly reduces the computational load while maintaining high beamforming accuracy for large-scale arrays. This solution holds promise for real-time applications of MVDR beamforming in fields like radar, sonar, and wireless communications, where massive antenna arrays are proliferating.
academic

خوارزمية تشكيل شعاع MVDR قابلة للتوسع وخطية بعدد الهوائيات

المعلومات الأساسية

  • معرّف الورقة: 2510.14802
  • العنوان: خوارزمية تشكيل شعاع MVDR قابلة للتوسع وخطية بعدد الهوائيات
  • المؤلفون: Sanjaya Herath, Armin Gerami, Kevin Wagner, Ramani Duraiswami, Christopher A. Metzler
  • التصنيف: eess.SP (معالجة الإشارات)
  • تاريخ النشر: 16 أكتوبر 2025 (نسخة أولية من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2510.14802

الملخص

تُستخدم تقنية تشكيل الشعاع بالحد الأدنى من التباين بدون تشويه الاستجابة (MVDR) على نطاق واسع في الأنظمة المصفوفية لقمع التداخل. ومع ذلك، فإن تطبيق MVDR على المصفوفات الكبيرة يشكل تحديًا حسابيًا، حيث تتناسب التعقيد الحسابي مع المكعب لعدد عناصر الهوائيات. تقدم هذه الورقة طريقة MVDR قابلة للتوسع للمصفوفات الكبيرة. تم تصميم الطريقة خصيصًا للحالات التي تكون فيها الإشارة المهمة أقل من قاع الضوضاء (مثل GPS)، مستفيدة من صيغة Sherman-Morrison وتقريب تحليل القيم الذاتية (SVD) منخفض الرتبة والعمليات الجبرية. من خلال هذه الطريقة، يتم تقليل التعقيد الحسابي من مكعب عدد الهوائيات إلى علاقة خطية. تم تقييم كفاءة الحساب ودقة تشكيل الشعاع للطريقة المقترحة من خلال المحاكاة ومقارنتها مع طريقة MVDR التقليدية. تقلل الطريقة بشكل كبير من الحمل الحسابي مع الحفاظ على دقة تشكيل شعاع عالية للمصفوفات الكبيرة.

الخلفية البحثية والدافع

تعريف المشكلة

تتمحور المشكلة الأساسية التي تعالجها هذه الدراسة حول مشكلة التعقيد الحسابي لتشكيل الشعاع MVDR التقليدي في مصفوفات الهوائيات الكبيرة. بشكل محدد:

  1. اختناق التعقيد الحسابي: يتطلب MVDR التقليدي حساب معكوس مصفوفة التغاير، بتعقيد O(M³)، حيث M هو عدد الهوائيات
  2. متطلبات الوقت الفعلي: في البيئات الديناميكية، يلزم تحديث مصفوفة التغاير بشكل متكرر، مما يجعل التنفيذ في الوقت الفعلي صعبًا
  3. اتجاه المصفوفات الكبيرة: في أنظمة الرادار والسونار والاتصالات اللاسلكية الحديثة، يتزايد حجم مصفوفات الهوائيات بشكل مستمر (من مئات إلى آلاف الهوائيات)

تحليل الأهمية

تتجلى أهمية هذه المشكلة في:

  • الانتشار الواسع للتطبيقات: يُستخدم MVDR على نطاق واسع في كشف أهداف الرادار وتحليل المشاهد الصوتية
  • احتياجات تطوير التكنولوجيا: توفر مصفوفات الهوائيات الكبيرة دقة مكانية عالية وقدرة قوية على قمع التداخل
  • متطلبات المعالجة في الوقت الفعلي: تتطلب العديد من سيناريوهات التطبيق معالجة تشكيل شعاع في الوقت الفعلي

قيود الطرق الموجودة

تتمتع الطرق الموجودة في الأدبيات بالقيود التالية:

  1. الطرق الخوارزمية: التقريبات منخفضة الرتبة القائمة على Nyström وتحليل QR لا تزال ذات تعقيد حسابي عالي
  2. الطرق الموزعة: تتطلب بروتوكولات اتصال معقدة وآليات مزامنة
  3. طرق التعلم العميق: تتطلب كميات كبيرة من بيانات التدريب، مع قدرة تعميم محدودة

المساهمات الأساسية

  1. اقتراح خوارزمية MVDR بتعقيد خطي: تقليل التعقيد الحسابي من O(M³) إلى O(MK²)، حيث K≪M
  2. دمج تقنيات رياضية متعددة: دمج ماهر لصيغة Sherman-Morrison وتقريب SVD منخفض الرتبة والعمليات الجبرية
  3. تحسين للسيناريوهات المحددة: تم تصميمه خصيصًا للحالات التي تكون فيها الإشارة أقل من قاع الضوضاء، مثل تطبيقات GPS
  4. الحفاظ على دقة تشكيل الشعاع العالية: الحفاظ على أداء مماثلة لـ MVDR التقليدي مع تقليل كبير في التعقيد الحسابي
  5. توفير إطار عمل خوارزمي كامل: يوفر عملية كاملة للتهيئة والتحديث وحساب الأوزان

شرح الطريقة

تعريف المهمة

ضع في الاعتبار مصفوفة تتكون من M هوائي متساوي الخواص، تستقبل إشارة مهمة من اتجاه الهدف θ₀ وإشارات تداخل L من الاتجاهات θ₁,θ₂,...,θL. متجه الإشارة المستقبلة في الوقت t هو:

xt=a(θ0)s0(t)+∑l=1La(θl)sl(t)+sn(t)x_t = a(\theta_0)s_0(t) + \sum_{l=1}^{L} a(\theta_l)s_l(t) + s_n(t)

حيث a(θᵢ) هو متجه التوجيه، s₀(t) هي الإشارة المهمة، sₗ(t) هي إشارات التداخل، و sₙ(t) هي الضوضاء.

الحل لمشكل تشكيل الشعاع MVDR التقليدي هو: w=R−1a(θ0)a(θ0)HR−1a(θ0)w = \frac{R^{-1}a(\theta_0)}{a(\theta_0)^H R^{-1}a(\theta_0)}

معمارية النموذج

1. التحديث التكراري لمصفوفة التغاير

استخدام قاعدة التحديث التكرارية مع عامل النسيان α: Rn+1=αRn+(1−α)xnxnHR_{n+1} = \alpha R_n + (1-\alpha)x_n x_n^H

2. تطبيق صيغة Sherman-Morrison

استخدام صيغة Sherman-Morrison لتحديث معكوس مصفوفة التغاير: Rn+1−1=Rn−1α−(1−α)αRn−1xnxnHRn−1α+(1−α)xnHRn−1xnR_{n+1}^{-1} = \frac{R_n^{-1}}{\alpha} - \frac{(1-\alpha)}{\alpha} \frac{R_n^{-1}x_n x_n^H R_n^{-1}}{\alpha + (1-\alpha)x_n^H R_n^{-1}x_n}

3. تقريب SVD منخفض الرتبة

إجراء تقريب K-رتبة لمصفوفة التغاير: R≈UKDKUKHR \approx U_K D_K U_K^H

حيث U_K ∈ C^{M×K} يحتوي على أول K متجهات ذاتية، و D_K ∈ C^{K×K} يحتوي على أول K قيم ذاتية.

4. قاعدة التحديث المخفضة الأبعاد

من خلال التقريب منخفض الرتبة، تصبح قاعدة التحديث: DK,n+1−1=DK,n−1α−(1−α)αDK,n−1UKHxnxnHUKDK,n−1α+(1−α)xnHUKDK,n−1UKHxnD_{K,n+1}^{-1} = \frac{D_{K,n}^{-1}}{\alpha} - \frac{(1-\alpha)}{\alpha} \frac{D_{K,n}^{-1}U_K^H x_n x_n^H U_K D_{K,n}^{-1}}{\alpha + (1-\alpha)x_n^H U_K D_{K,n}^{-1}U_K^H x_n}

نقاط الابتكار التقني

  1. استراتيجية تقليل الأبعاد: تجنب تشكيل مصفوفة تغاير M×M بشكل صريح من خلال تقريب K≪M منخفض الرتبة
  2. آلية التحديث الإضافي: تحقيق تعقيد تحديث O(MK²) باستخدام صيغة Sherman-Morrison
  3. تحسين السيناريوهات المحددة: بالنسبة للحالات التي تكون فيها الإشارة أقل من قاع الضوضاء، يمكن عادة تعيين K إلى L+1
  4. تكامل الخوارزمية: دمج عضوي لـ SVD وصيغة Sherman-Morrison والتحديث التكراري

إعداد التجارب

معاملات المحاكاة

  • تكوين المصفوفة: مصفوفة خطية موحدة (ULA)، بمسافة هوائي نصف طول موجة
  • عدد الهوائيات: M = 50, 75, 100 (التجارب الرئيسية)، موسعة إلى 500 (اختبار التعقيد)
  • إعداد الإشارة:
    • إشارة الهدف: مسافة 10 كم، سرعة عرضية 500 م/ث
    • إشارة مرسلة: نبضة خطية التغيير، عرض نطاق 300 ميجاهرتز، مدة نبضة 100 ميلي ثانية
    • SINR: -10 ديسيبل
    • معدل العينات: 1 ميجاهرتز
  • معاملات الخوارزمية:
    • عامل النسيان α = 0.99
    • بُعد منخفض الرتبة K = 10
    • عدد اللقطات: 1000

مؤشرات التقييم

  1. عرض الفص الرئيسي (MLW): عرض الزاوية للفص الرئيسي في مخطط الشعاع
  2. مستوى الفص الجانبي (SLL): مستوى الطاقة للفص الجانبي بالنسبة للفص الرئيسي
  3. عمق الصفر: مستوى الطاقة للصفر بالنسبة للفص الرئيسي
  4. وقت الحساب: الوقت الإجمالي لتنفيذ 10000 خطوة زمنية
  5. كسب SINR: نسبة SINR الناتج إلى SINR المدخل

طرق المقارنة

  • MVDR التقليدي: طريقة معكوس مصفوفة التغاير القياسية
  • مقارنة وقت التنفيذ: الاختبار على معالج AMD EPYC 7443 بـ 24 نواة

نتائج التجارب

النتائج الرئيسية

مقارنة دقة تشكيل الشعاع

MLMLW (°)عمق الصفر (dB)SLL (dB)
MVDRالمقترحMVDRالمقترحMVDRالمقترح
5012.272.32-49.56-42.44-13.02-9.14
7521.361.33-41.02-34.84-12.75-11.05
10031.061.08-45.83-41.78-11.37-12.47

تحليل التعقيد الحسابي

  • MVDR التقليدي: تعقيد O(M³)، وقت التنفيذ يزداد مع M³
  • الطريقة المقترحة: تعقيد O(MK²)، وقت التنفيذ يزداد خطيًا مع M
  • تحسن الأداء: بالنسبة للمصفوفة بـ M=500، تم تقليل وقت الحساب بعدة رتب من الحجم

تحليل مخطط الشعاع

تُظهر نتائج التجارب أن الطريقة المقترحة تؤدي أداءً مماثلاً لـ MVDR التقليدي في الجوانب التالية:

  1. توجيه الفص الرئيسي: توجيه صحيح للفص الرئيسي نحو اتجاه الهدف
  2. تشكيل الأصفار: تشكيل أصفار فعالة في اتجاهات إشارات التداخل
  3. شكل مخطط الشعاع الكلي: توافق عالي مع MVDR التقليدي

تحليل الأداء طويل الأجل

من خلال محاكاة 100,000 خطوة زمنية، تم اكتشاف:

  1. تدهور SINR: قد يحدث انخفاض في كسب SINR مع الاستخدام طويل الأجل
  2. تأثير إعادة التهيئة: بعد إعادة التهيئة في الخطوة 50,000، يتم استعادة كسب SINR
  3. تكلفة إعادة التهيئة: تعقيد إعادة التهيئة O(M²) لا يزال أقل من طريقة MVDR التقليدية O(M³)

الأعمال ذات الصلة

الطرق الخوارزمية

  1. تقريب Nyström منخفض الرتبة: استخدام تقريب منخفض الرتبة لتقليل الحساب والتخزين
  2. طرق تحليل QR: تتبع ديناميكي للتغييرات في الكلام والضوضاء
  3. SMI-MVDR: تنفيذ تكراري باستخدام تحليل Cholesky وتحويلات Householder

الطرق الموزعة

  1. خوارزميات تمرير الرسائل: تحقيق تشكيل شعاع موزع من خلال اتصال العقد المحلية
  2. طريقة ADMM: توزيع الحمل الحسابي على معالجات متعددة

طرق التعلم العميق

  1. التعلم المعزز العدائي العميق: تحسين قدرات تشكيل الشعاع لـ MIMO الكبيرة
  2. الشبكات العصبية الالتفافية: تقليل تعقيد التدريب واستخدامها في معايرة مصفوفات الهوائيات الكبيرة

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. تقليل كبير في التعقيد الحسابي: من O(M³) إلى O(MK²)، مما يحقق قابلية توسع خطية
  2. الحفاظ على دقة تشكيل شعاع عالية: مماثلة لـ MVDR التقليدي في المؤشرات الرئيسية مثل عرض الفص الرئيسي ومستوى الفص الجانبي
  3. قابلية التطبيق في التطبيقات الفعلية: توفير حل عملي لتشكيل شعاع MVDR في الوقت الفعلي للمصفوفات الكبيرة

القيود

  1. تقييد السيناريوهات المطبقة: مصمم خصيصًا للحالات التي تكون فيها الإشارة أقل من قاع الضوضاء، مع أداء ضعيفة للحالات التي تكون فيها الإشارة أعلى من قاع الضوضاء
  2. تدهور الأداء طويل الأجل: يتطلب إعادة تهيئة دورية للحفاظ على كسب SINR
  3. تكلفة التهيئة: لا يزال حساب SVD الأولي يتطلب تعقيد O(M³)

الاتجاهات المستقبلية

  1. التوسع إلى السيناريوهات التي تكون فيها الإشارة أعلى من قاع الضوضاء
  2. طرق تهيئة أكثر كفاءة: مثل طرق SVD العشوائية
  3. استراتيجيات إعادة تهيئة تكيفية: تفعيل إعادة التهيئة تلقائيًا بناءً على تدهور الأداء

التقييم المتعمق

المميزات

  1. قوة الابتكار النظري: دمج ماهر لأدوات رياضية متعددة لحل مشكلة عملية
  2. قيمة عملية عالية: حل الاختناق الرئيسي لـ MVDR في المصفوفات الكبيرة
  3. تجارب شاملة: التحقق من دقة التعقيد والأداء طويل الأجل من زوايا متعددة
  4. اكتمال الخوارزمية: توفير عملية خوارزمية كاملة وتفاصيل التنفيذ

أوجه القصور

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

التأثير

  1. المساهمة الأكاديمية: توفير أفكار حل جديدة لتشكيل الشعاع في المصفوفات الكبيرة
  2. القيمة الهندسية: من المتوقع أن تُطبق في مجالات الرادار والسونار والاتصالات اللاسلكية
  3. قابلية التكرار: وصف الخوارزمية واضح، سهل التكرار والتحسين

السيناريوهات المطبقة

  1. استقبال GPS: حالة نموذجية للإشارة أقل من قاع الضوضاء
  2. كشف الإشارات الضعيفة: تطبيقات تتطلب قمع تداخل قوي
  3. مصفوفات الهوائيات الكبيرة: أنظمة بمئات إلى آلاف الهوائيات
  4. متطلبات المعالجة الفعلية: تطبيقات حساسة لتأخير الحساب

المراجع

تستشهد الورقة بـ 21 مرجعًا ذا صلة، تغطي نظرية أساسيات تشكيل الشعاع ومعالجة المصفوفات الكبيرة وخوارزميات SVD وجوانب أخرى متعددة، مما يوفر أساسًا نظريًا قويًا للبحث.

التقييم الشامل: هذه ورقة ذات قيمة عملية مهمة في مجال معالجة الإشارات. من خلال حيل رياضية ماهرة، تحل اختناق الحساب لتشكيل شعاع MVDR في المصفوفات الكبيرة. على الرغم من وجود قيود مثل تقييد السيناريوهات المطبقة، فإنها توفر مساهمة قيمة لتطوير هذا المجال.