مناقشة اطروحة الماجستير الموسومة “تقنيات البرمجة الديناميكية لايجاد المسار في الشبكات اللاسلكية” في قسم الحاسبات
تمت في قسم هندسة الحاسبات مناقشة اطروحة الماجستير الموسومة
“تقنيات البرمجة الديناميكية لايجاد المسار في الشبكات اللاسلكية “
Dynamic Programming Techniques for Routing in Wireless Networks
للباحثة صابرين محمود شكر محمود في اختصاص الالكترون والاتصالات /هندسة الحاسبات وبإشراف كلا من الاستاذ المساعد نهىعبد الصاحب علوان والاستاذ المساعد الدكتور ابراهيم قاسم ابراهيم وذلك في قسمهندسة الحاسبات وتكونت لجنة المناقشة من الاستاذ الدكتور محمد زكي فائز رئيسا و والمدرس الدكتورضياء جاسم كاظم عضواُ و الاستاذ المساعد عمر وليد عبد الوهاب عضواً .
أن هذا البحث يسلط الضوء على مشكلة ايجاد المسار في الشبكات اللاسلكية بسبب البنية المتغيرة وسائل النقل المشتركة. و باستخدام تقنية البرمجة الديناميكية (DP ) ،فأن مشكلة أقصرمسار والتي هي ايجاد المسارالأمثل بين عقدتين في الشبكات بالاعتماد على بعض المقاييس من جودة الخدمة (QoS ) سيتم حلها في هذه الأطروحة. فيهذا العمل، سيكون هناك نوعين من السيناريوهات اللاسلكية سيتم معالجتها.وهي الشبكة اللاسلكية أحادية الاتجاه والشبكات اللاسلكية المعشقة .
و تستخدم الرسوم البيانية الموجهة المتعددة المراحل لتمثيل الشبكات اللاسلكية أحادية الاتجاه. الخوارزميات DPالموجهة للأمام و DP الموجهة للخلف استخدمت لإيجاد الطريق الأمثل بالاعتماد على سعة المسار كمقياس لجودة الخدمة.و لتسريع حل هذه المشكلة, تمَّ اقتراح نظام متوازٍ انقباضي يعتمد على DP الموجهة للامام و الموجهة للخلف.كمية نقل البيانات هي 6fc.3/5 طرح في الثانية والتأخيرهو 10Tc فيرسم بياني مع 4 مراحل وكل مرحلة تحتوي على 3 عقد باستثناء مرحلتي المصدر والوجهة تحتوي على عقدة واحدة, حيث fc=1/Tc هي التردد الاساس للمنظومة المتوازية.
اما في الشبكات اللاسلكية المعشقة، يستخدم الرسم البياني مع حواف ثنائية الاتجاه. ولحل مشكلة ايجاد افضل طريق في هذا النوع من الشبكات الذي لايخضع لمحدد او يخضع لمحدد واحد فأنه يتم باستخدام الخوارزميات Dijkstra , Bellman-Ford , وFloyd-Warshall . و لحل مشكلة ايجاد الطريق الاقصر بدون محدد فأنه تم استخدام سعة المسار لقياس جودة الخدمة. ان خوارزمية التوجيه المعشقة (MRA ) في المؤلفات الموجودة هو نظامDP تحسب المسارات ذات اكبرسعة للمسارمع تحديد الوقت الذي تحتاجه من بداية المسارإلى نهايته. في هذه الاطروحة, التركيزهو الاستفادة المثلى الاحد الاهداف (سعة المسار) لخوارزمية Dikstraلمحدد واحد بينما إحاطة الآخر (الوقت الذي تحتاجه من بداية المسارإلى نهايته). فإن أهمية عملنا هو أنه بأستخدام خوارزمية Dijkstra فأننا نحتفظ بكفاءة كل ميزة من هذه الخوارزميات المقابلة DP , مثل سرعة حساب اقصرطريق واحتوائه حسابياً بمقدار (N2 )O , حيث Nهوعدد العقد في الشبكة اللاسلكية، وجعلها فعالة بما فيها لكفاية للشبكات الكبيرة نسبيا. الاختلافات بين الخوارزمية Dijkstra وغيرها لمحدد واحد هي وقت المعالجة وكمية المعلومات التي يجب جمعها في كل عقدة في الشبكة. استنادا إلى وقت المعالجة، Dijkstra هي أفضل من غيرها بسبب وقت المعالجة في Dijkstra هوO(N2) ، في حين فيBellman- Ford هو O(NL) ,حيثL هو عدد الروابط في الشبكة، وأنه في Floyd-Warshall هو O(N3) . خوارزمية Bellman-Ford أفضل من Dijkstra استنادا إلى النهج الآخربسبب العقد في Bellman-Ford تجمع المعلومات من العقد المجاورة فقط ولكن العقد في Dijkstraيجب أن تعرف بنية الشبكة بأكملها.
وقد عولجت مشكلة تحديد المسار للـ DP بمحددين كذلك, باقتراح خوارزمية شاملة للتوجيه التعشقي (CMRA ). هذه الاخيرة تحسن سعة المسار في حين احاطة الوقت الذي تحتاجه من بداية المسارإلى نهايته وعدد القفزات إلى الحدود العليا.
