خوارزمية لحساب الشبكة المخصصة الأكثر كفاءة في استخدام الطاقة

Question

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

تكلفة الطاقة لإرسال رسالة من العقدة A إلى العقدة B هي المسافة بينهما ، مربعة.

التحدي هو كيفية ربط هذه العقد ، بتنسيق شجرة ، لإنتاج أكثر شبكة كفاءة في استخدام الطاقة.

على سبيل المثال ، هناك طريقتان محتملين لربط هذه العقد ، حيث كان اليسار أكثر كفاءة في استخدام الطاقة.

أنا أعمل على خوارزمية وراثية لحل المشكلة ، لكنني كنت أتساءل عما إذا كان لدى أي شخص أي أفكار أخرى ، أو يدرك أي رمز مفتوح المصدر ذي صلة.

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

تحرير رقم 2: أنا آسف بشأن ommission في النص الأصلي للسؤال. نظرًا لأن بعض إجاباتك السابقة ليست تمامًا ما أبحث عنه ، لكنني لم أكن على دراية بخوارزميات MST ، لذا شكرًا على إخباري بها.

على أمل جعل الأمور أكثر وضوحًا ، اسمحوا لي أن أضيف هذا:

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

Answer 1

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

هذا لا يأخذ في الاعتبار تقليل البطارية على الرغم من. في هذه الحالة ، (ولست متأكدًا تمامًا مما تحاول التقليل أولاً) قد ترغب في النظر فيه Min-Cost Max Flow. ومع ذلك ، سيؤدي ذلك إلى تحسين (زيادة) "التدفق" أولاً ، قبل تقليل التكلفة. هذا قد يكون أو لا يكون مثاليًا.

لإنشاء قيد الرأس (يمكن أن تعمل كل عقدة فقط k الرسائل) ، تحتاج فقط إلى إنشاء رسم بياني آخر G_1 حيث تضيف قمة إضافية u_i لكل v_i - والحصول على التدفق v_i ل u_i كن مهما كان قيادتك ، في هذه الحالة ، k+1, ، مع التكلفة 0. لذلك إذا كانت هناك حافة (a,b) في الرسم البياني الأصلي G, ، ثم في G_1, ، سيكون هناك حافة (u_a,v_b) لكل من هذه الحواف. في الواقع ، أنت تقوم بإنشاء طبقة ثانية من القمم التي تقيد التدفق إلى k. (حالة خاصة للجذر ، إلا إذا كنت تريد أيضًا قيود رسالة على الجذر.)

حل Max-Flow القياسي على G_1 يجب أن يكفي - مصدر يشير إلى كل قمة مع تدفق 1, ، وحوض متصل بالجذر. هناك حل ل G_1 (تختلف على k) إذا كان الحد الأقصى G_1 هو N, ، عدد القمم.

Answer 2

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

لاحظ أنه مع خوارزمية Dijkstra ، من الممكن أيضًا حساب الشجرة بأكملها في ممر واحد.

Answer 3

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

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

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

أعتقد أنه يجب عليك البدء ببعض الأشجار (على سبيل المثال تلك التي تم تشكيلها عن طريق نقل كل عقدة مباشرة إلى عقدة الجذر) ثم قم بعمل عدد من خطوات التحسين.

قد يكون التحسين ممكنًا بشكل حتمي أو من خلال طريقة إحصائية مثل الصلب المحاكاة أو الخوارزمية الوراثية.

ربما تحاول الطريقة الحتمية إيجاد تحسن لأسوأ العقدة الحالية ، بحيث تكون أوزان العقدة الجديدة أصغر من وزن العقدة الحالي. من الصعب القيام بذلك بطريقة تجعل النتيجة هي الأمثل العالمي.

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

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

Answer 4

يمكنك محاولة صياغة المشكلة كمشكلة الحد الأدنى للتدفق الحد الأقصى للتكلفة. فقط بعض الأفكار:

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

إذا كنت ترغب أيضًا في حساب كفاءة الطاقة ، فيمكنك محاولة إضافة وزن لها في تكاليف الحافة في كل عقدة. لست متأكدًا من كيفية قيامك بذلك ، نظرًا لأنك تحاول تحسين هدفين (تكلفة إرسال الرسائل وكفاءة الطاقة) في نفس الوقت.

Answer 5

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

أعتقد أنه يمكنك استخدام بعض المبادئ من AHODV (http://moment.cs.ucsb.edu/aodv/aodv.html) بروتوكول ، ولكن ضع في اعتبارك أنك ستحتاج إلى زيادة المقياس بطريقة أو بأخرى. إن Count Count له علاقة كبيرة باستهلاك الطاقة ، ولكن في الوقت نفسه ، تحتاج إلى أن تضع في اعتبارك مقدار الطاقة المستخدمة لنقل الرسالة. ربما تكون بداية المقياس هي مجموع جميع استخدامات الطاقة في كل عقدة على مسار معين. عندما تقوم التعليمات البرمجية الخاصة بك بإعداد شبكتك بعد ذلك ، يمكنك ببساطة تتبع تكلفة المسار لـ "اتجاه" معين من التوجيه والسماح للبروتوكول الموزع بالقيام بالباقي في كل عقدة.

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

Answer 6

هل فكرت في استخدام رسم بياني حكيمي موجه بدلاً من شجرة؟ بمعنى آخر ، تحتوي كل عقدة على "أولياء أمور" متعددة يمكنها إرسال رسائل إليها - يضمن متطلبات الحادة أن تصل جميع الرسائل في النهاية. أسأل لأنه يبدو أن لديك شبكة لاسلكية ولأن هناك نهجًا فعالًا لحساب الحل الأمثل.

النهج هو البرمجة الخطية. دع R يكون فهرس عقدة الجذر. بالنسبة للعقد i ، j ، دع cij تكون تكلفة الطاقة لإرسال رسالة من i إلى j. دع Xij يكون متغيرًا يمثل عدد الرسائل المرسلة بواسطة Node I إلى Node J في كل خطوة زمنية. دع z يكون متغيرًا يمثل الحد الأقصى لمعدل استهلاك الطاقة في كل عقدة.

البرنامج الخطي هو

minimize z
subject to
# the right hand side is the rate of energy consumption by i
(for all i) z >= sum over all j of cij * xij
# every node other than the root sends one more message than it receives
(for all i != r) sum over all j of xij == 1 + sum over all j of xji
# every link has nonnegative utilization
(for all i, j) xij >= 0

يمكنك كتابة رمز ينشئ هذا LP في شيء يشبه هذا التنسيق إلى حد كبير ، حيث يمكن حله عند حل Solver LP (على سبيل المثال ، GLPK المجاني).

هناك بضع ميزات من LP تستحق الذكر. أولاً ، قد يبدو من الغريب أننا لم "أجبر" الرسائل على الذهاب إلى الجذر. اتضح أنه طالما كانت ثوابت CIJ إيجابية ، فإنها تضيع الطاقة فقط لإرسال الرسائل في دورات ، لذلك ليس هناك فائدة. هذا يضمن أيضًا أن الرسم البياني الموجه الذي قمنا ببنائه هو acyclic.

ثانياً ، متغيرات XIJ بشكل عام وليس الأعداد الصحيحة. كيف نرسل نصف رسالة؟ أحد الحلول الممكنة هو التوزيع العشوائي: إذا كان M هو المعدل الإجمالي للرسائل المرسلة بواسطة Node I ، فإن العقدة I ترسل كل رسالة إلى Node J مع احتمال XIJ/M. هذا يضمن أن المتوسطات تعمل مع مرور الوقت. بديل آخر هو استخدام نوع من مخطط روبن مستدير مرجح.

Answer 7

الحد الأدنى الشجرة الممتدة؟ http://en.wikipedia.org/wiki/minimum_spanning_tree

Answer 8

عملت على مشكلة مماثلة ، ولكن مع أجهزة الاستشعار اللاسلكية. استخدمنا pegasis (جمع كفاءة الطاقة في نظام معلومات المستشعر) ، وهو بروتوكول موفرة للطاقة.http://www.mast.queensu.ca/~math484/projects/pastprojects/2005/presentation05_yi_wei.ppt [http://www.technion.ac.il/~es/professional/routing_protocols_for_sensor_networks.ppt/201