2006-2007:Κατανεμημένα Συστήματα ΙΙ:Ασκήσεις:Project:Δρομολόγηση με χρήση εικονικών συντεταγμένων σε δίκτυα αισθητήρων

Από DistrSys

Τα ασύρματα δίκτυα αισθητήρων αποτελούνται, στην πλειοψηφία τους, από κόμβους με λίγες υπολογιστικές δυνατότητες (CPU, μνήμη), γεγονός το οποίο δυσκολεύει την multihop δρομολόγηση στα δίκτυα αυτά. Γενικά, δεν είναι δυνατό να υπάρχουν μεγάλοι πίνακες δρομολόγησης ώστε ο κάθε κόμβος να ξέρει πώς να δρομολόγησει τα πακέτα που στέλνει μέσα στο δίκτυο. Επιπλέον, λόγω και άλλων ειδικών συνθηκών, όπως π.χ., επειδή η τοπολογία του δικτύου αλλάζει συχνά, αν χρησιμοποιήσουμε τα παραδοσιακά πρωτόκολλα δρομολόγησης δεν θα έχουμε ικανοποιητικά αποτελέσματα, χρησιμοποιούνται πρώτοκολλα δρομολόγησης ειδικά σχεδιασμένα για τα δίκτυα αυτά.

Ένα μεγάλο μέρος από τα πρωτόκολλα αυτά χρησιμοποιεί μια greedy λογική, η οποία βασίζεται σε γεωγραφική πληροφορία. Η βασική ιδέα είναι ότι, εφόσον ο κάθε κόμβος ξέρει την τοποθεσία του με τον ένα ή τον άλλο τρόπο (π.χ. GPS, localization), όταν λαμβάνει ή στέλνει πακέτα τα προωθεί σε κάποιον γειτονικό του κόμβο, ο οποίος είναι πιο κοντά από τον ίδιο σε σχέση με τον τελικό παραλήπτη του μηνύματος.

Για να αντιμετωπιστούν κάποιες από τις αδυναμίες των πρωτοκόλλων αυτών, όπως π.χ. ότι όλοι οι κόμβοι δεν έχουν σωστή πληροφορία για την τοποθεσία τους, πρόσφατα πρόταθηκαν πρωτόκολλα δρομολόγησης που χρησιμοποιούν "εικονικές" συντεταγμένες. Στα πρωτόκολλα αυτά, οι κόμβοι του δικτύου με κάποιον επαναληπτικό αλγόριθμο υπολογίζουν συντεταγμένες χρησιμοποιώντας τις σχετικές απόστασεις μεταξύ τους (σε hops) και ίσως κάποια πραγματική γεωγραφική πληροφορία.

Στην εργασία αυτή θα μελετηθούν κάποιοι αλγόριθμοι δρομολόγησης που χρησιμοποιούν εικονικές συντεταγμένες, και θα επιλεγεί ένας αλγόριθμος για να υλοποιηθεί, αυτούσια ή με τροποποιήσεις, σε περιβάλλον nesC και TinyOS.

Ανακτήθηκε από το "http://www.ceid.upatras.gr/courses/katanemhmena/wiki/index.php/2006-2007:%CE%9A%CE%B1%CF%84%CE%B1%CE%BD%CE%B5%CE%BC%CE%B7%CE%BC%CE%AD%CE%BD%CE%B1_%CE%A3%CF%85%CF%83%CF%84%CE%AE%CE%BC%CE%B1%CF%84%CE%B1_%CE%99%CE%99:%CE%91%CF%83%CE%BA%CE%AE%CF%83%CE%B5%CE%B9%CF%82:Project:%CE%94%CF%81%CE%BF%CE%BC%CE%BF%CE%BB%CF%8C%CE%B3%CE%B7%CF%83%CE%B7_%CE%BC%CE%B5_%CF%87%CF%81%CE%AE%CF%83%CE%B7_%CE%B5%CE%B9%CE%BA%CE%BF%CE%BD%CE%B9%CE%BA%CF%8E%CE%BD_%CF%83%CF%85%CE%BD%CF%84%CE%B5%CF%84%CE%B1%CE%B3%CE%BC%CE%AD%CE%BD%CF%89%CE%BD_%CF%83%CE%B5_%CE%B4%CE%AF%CE%BA%CF%84%CF%85%CE%B1_%CE%B1%CE%B9%CF%83%CE%B8%CE%B7%CF%84%CE%AE%CF%81%CF%89%CE%BD".