تم انجاز رسالة الماجستير للطالبة صابرين محمود شكر في قسم الهندسة الالكترونية والاتصالات عن بحثها الموسوم “تقنيات البرمجة الديناميكية لايجاد المسار في الشبكات اللاسلكية “وبأشراف أ.م. نهى عبد الصاحب علوان أ.م.د. ابراهيم قاسم ابراهيم,وتألفت لجنة المناقشة برئاسة أ.د. محمد زكي فائز وعضوية كل من أ.م. عمر وليد عبدالوهاب , د. ضياء جاسم كاظم
وتلخص بحثة بما يلي :
مشكلة ايجاد المسار هي مسألة هامة في الشبكات اللاسلكية بسبب البنية المتغيرة وسائل النقل المشتركة. وباستخدام تقنية البرمجة الديناميكية (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). هذه الاخيرة تحسن سعة المسار في حين احاطة الوقت الذي تحتاجه من بداية المسار إلى نهايته وعدد القفزات إلى الحدود العليا.
وتلخص بحثة بما يلي :
مشكلة ايجاد المسار هي مسألة هامة في الشبكات اللاسلكية بسبب البنية المتغيرة وسائل النقل المشتركة. وباستخدام تقنية البرمجة الديناميكية (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). هذه الاخيرة تحسن سعة المسار في حين احاطة الوقت الذي تحتاجه من بداية المسار إلى نهايته وعدد القفزات إلى الحدود العليا.
