Document
Grid based broadcast al-gorith in mobile wireless AD-HOC networks : a simulation study
Publisher
Sultan Qaboos University
Gregorian
2014
Language
English
English abstract
A mobile ad hoc network (MANET) is a set of mobile nodes communicating with each other in a peer-to-peer manner without any predefined infrastructure. In MANET, broadcasting plays a fundamental communication role for different network applications. It is defined as a process to disseminate a message from a given source node to all other nodes in the network. In MANET, the traditional broadcast approach is known as flooding where all nodes rebroadcast any received message for the first time! This process propagates in a multi-hop fashion until the whole network is covered. Although this approach can be the most suitable approach in a sparse network, the problem start to appear in dense areas where too many unnecessarily redundant retransmissions will cause a high channel contention and excessive collision. This phenomenon is known as the broadcast storm problem, Several broadcasting approaches have been proposed to address the broadcast storm problem. Most proposed approaches try to mitigate this problem by reducing the number of forwarding candidate nodes. However, due to the nature of MANETS where the network connectivity is changing over space and time, any new proposed broadcast solution has to be designed carefully in order to maintain a high reachability with a minimum network latency and overhead. Recently a new GridBased Broadcasting algorithm (GBB) was proposed in the literature. This thesis aims to simulate the new proposed GBB algorithm. The GBB algorithm relieves the broadcast storm problem by minimizing the number of participating nodes in the rebroadcast operation. In order to do that, GBB divides the entire geographïcal region into a logical 2-Dimensional grid of cells. Therefore, nodes are viewed as a cluster of cells and only one node (called gateway) per cell will rebroadcast any new message regardless of the cell density. As a consequence, the number of rebroadcast operations will be minimized significantly. The GBB algorithm uses the normal traffic in the network (broadcast or unicast) to maintain gateway nodes, therefore no gateway election or topology information is needed. A simulation model based on Network Simulator (ns-2) has been developed to measure the performance of the GBB algorithm. In order to have a clear view of GBB performance, this thesis implements the simple flooding and the probabilistic based (PROB) broadcasting algorithms available in the literature for evaluation. Most common system parameters are evaluated in this study under the following network conditions: node mobility, network density, traffic load and domain size. Simulation results revealed that GBB has improved considerably compared to simple flooding and PROB algorithms in terms of the number of saved rebroadcast packets, average reachability, collision rate and end-to-end delay.
Member of
Resource URL
Arabic abstract
تتعرض هذه الأطروحة إلى دراسة تجريبية الخوارزمية جديدة للبث في الشبكات اللاسلكية العشوائية. تختلف الشبكات اللاسلكية العشوائية عن الشبكات اللاسلكية المعروفة بأنها تعمل في بيئة من دون الحاجة إلى بنية تحتية لإدارة آلية التواصل بين جميع الأجهزه المتحركة في الشبكة، حيث يقوم كل جهاز بالمشاركة في عملية استلام البيانات و إعادة توجيهها إلى مسارات محددة من قبل خوازميات معدة من قبل.
تعرف عملية البث بأنها العملية التي تنتج عند محاولة أحد أجهزة الشبكة توزيع رسالة إلى جميع الأجهزة الموجودة في الشبكة. تهدف هذه الأطروحة إلى دراسة جدوي خوازمية جديدة للتقليل من التبعات التي تتولد عند استخدام عملية البث التقليدية حيث يقوم كل جهاز استقبل الرسالة للمرة الأولى بإعادة إرسال الرسالة من أجل إيصالها إلى من هو أبعد والذي قد يكون خارج نطاق إرسال المرسل السابق. تتم هذه العملية بشكل تتابعي حتى يتم تغطية الأجهزة الموجودة في الشبكة كلها. و من خلال الدراسات السابقة وجد أن استعمال الخوارزمية التقليدية يكلف الشبكة الكثير من الأعباء وذلك بإغراق النطاق بالكثير من الرسائل المتكرره والتي تؤثر سلبا على كفاءة الشبكة.
تتمحور فكرة الخوارزمية الجديدة المقترحة لهذه الرسالة في إيجاد آلية للتقليل من عدد الأجهزة المشاركه في عملية إعادة إرسال الرسالة مع المحافظة على ضمان إيصال الرسالة الى أكبر عدد ممكن من الأجهزة في الشبكة. و تتم هذه العملية بتقسيم المساحة التي يتوزع فيها الأجهزة إلي شبكة مكونه من خلايا على شكل مربعات افتراضية ثنائية الأبعاد، حيث سيمثل كل خلية في الشبكة جهاز واحد فقط يعتبر هو المسؤول عن إعادة إرسال الرسالة في تلك الخلية. تتم عملية صيانة بيانات ممثلي كل خلية من خلال الاعتماد على البيانات المتبادلة في الشبكة من دون الحاجة إلى إرسال رسائل خاصة لترشيح واختيار ممثلي الخلايا.
تمت دراسة جدوي هذه الخوارزمية الجديدة بالاستعانة بنظام المحاكاه للشبكات (ns2)، وقد تمت دراسة معايير مختلفة لمعرفة كفاءة الخوارزمية تحت عوامل مختلفة وهي: حركة الأجهزة و كثافة عدد الأجهزة و تأثير كمية البيانات المتبادلة في الشبكة. و لأجل اتضاح ومقارنة النتائج تمت ايضا دراسة الخوارزمية التقليدية و خوارزمية الإحتمالات. وقد أوضحت نتائج الدراسة كفاءة الخوارزمية المقترحة مقارنة بالخوارزميات المذكورة سابقا من حيث، سرعة تغطية الشبكة و معدل عمر عملية البث ونسبة استلام الرسالة لكل الأجهزة في الشبكة و عدد عمليات البث المختزلة.
تعرف عملية البث بأنها العملية التي تنتج عند محاولة أحد أجهزة الشبكة توزيع رسالة إلى جميع الأجهزة الموجودة في الشبكة. تهدف هذه الأطروحة إلى دراسة جدوي خوازمية جديدة للتقليل من التبعات التي تتولد عند استخدام عملية البث التقليدية حيث يقوم كل جهاز استقبل الرسالة للمرة الأولى بإعادة إرسال الرسالة من أجل إيصالها إلى من هو أبعد والذي قد يكون خارج نطاق إرسال المرسل السابق. تتم هذه العملية بشكل تتابعي حتى يتم تغطية الأجهزة الموجودة في الشبكة كلها. و من خلال الدراسات السابقة وجد أن استعمال الخوارزمية التقليدية يكلف الشبكة الكثير من الأعباء وذلك بإغراق النطاق بالكثير من الرسائل المتكرره والتي تؤثر سلبا على كفاءة الشبكة.
تتمحور فكرة الخوارزمية الجديدة المقترحة لهذه الرسالة في إيجاد آلية للتقليل من عدد الأجهزة المشاركه في عملية إعادة إرسال الرسالة مع المحافظة على ضمان إيصال الرسالة الى أكبر عدد ممكن من الأجهزة في الشبكة. و تتم هذه العملية بتقسيم المساحة التي يتوزع فيها الأجهزة إلي شبكة مكونه من خلايا على شكل مربعات افتراضية ثنائية الأبعاد، حيث سيمثل كل خلية في الشبكة جهاز واحد فقط يعتبر هو المسؤول عن إعادة إرسال الرسالة في تلك الخلية. تتم عملية صيانة بيانات ممثلي كل خلية من خلال الاعتماد على البيانات المتبادلة في الشبكة من دون الحاجة إلى إرسال رسائل خاصة لترشيح واختيار ممثلي الخلايا.
تمت دراسة جدوي هذه الخوارزمية الجديدة بالاستعانة بنظام المحاكاه للشبكات (ns2)، وقد تمت دراسة معايير مختلفة لمعرفة كفاءة الخوارزمية تحت عوامل مختلفة وهي: حركة الأجهزة و كثافة عدد الأجهزة و تأثير كمية البيانات المتبادلة في الشبكة. و لأجل اتضاح ومقارنة النتائج تمت ايضا دراسة الخوارزمية التقليدية و خوارزمية الإحتمالات. وقد أوضحت نتائج الدراسة كفاءة الخوارزمية المقترحة مقارنة بالخوارزميات المذكورة سابقا من حيث، سرعة تغطية الشبكة و معدل عمر عملية البث ونسبة استلام الرسالة لكل الأجهزة في الشبكة و عدد عمليات البث المختزلة.
Category
Theses and Dissertations