Shawn

Από DistrSys

Πίνακας περιεχομένων 1 Εισαγωγή 2 Σχεδιαστικοί Στόχοι 3 Αρχιτεκτονική 3.1 Μοντέλα (Models) 3.1.1 Communication Model 3.1.2 Edge Model 3.1.3 Transmission Model 3.1.4 Ετερόκλητα Μοντέλα (Miscellaneous Models) 3.2 Διαδοχέας (Sequencer) 3.2.1 Simulation Tasks 3.2.2 Simulation Controller 3.2.3 Event Scheduler 3.3 Περιβάλλον Εξομοίωσης (Simulation Environment) 3.3.1 Κόμβοι και Επεξεργαστές 3.3.2 Διαχωρίζοντας τις Μεταβλητές Κατάστασης από τις Μεταβλητές Μέλη 3.3.3 Μοντελοποιώντας Αισθητήρες και τις Τιμές τους

Εισαγωγή

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

• Αναλυτικές Μέθοδοι: Οι αναλυτικές μέθοδοι τυπικά δεν είναι κατάλληλες για την υποστήριξη εφαρμογών σε ασύρματα δίκτυα αισθητήρων.Παρά την εκφραστικότητα και την γενικότητα τους είναι αρκετά δύσκολο να κατανοήσουν τις λεπτομέρειες τέτοιων πολύπλοκων κατανεμημένων εφαρμογών με επίσημο τρόπο.
• Πειράματα σε Πραγματικές Συσκευές: Τα πειράματα σε πραγματικές συσκευές είναι μια δελεαστική επιλογή και αποτελούν πειστικά μέσα καθώς μπορούν να επιδείξουν (εφόσον η τεχνολογία είναι διαθέσιμη) ότι μια εφαρμογή πραγματοποιεί μια συγκεκριμένη εργασία.Παρόλα αυτά λόγω απρόβλεπτων περιβαλλοντικών συνθηκών είναι δύσκολο να αναπαραχθούν τα αποτελέσματα ή να απομονωθούν οι πηγές λάθους.Επιπλέον,οι αναπτύξεις δικτύων στον πραγματικό κόσμο είναι επίπονες και περιλαμβάνουν εργασίες διαχείρισης που δεν σχετίζονται άμεσα με το πρόβλημα.Για το λόγο αυτό τα πειράματα περιορίζονται σε μερικές δεκάδες συσκευές, ενώ μελλοντικά σενάρια προυποθέτουν δίκτυα χιλιάδων εώς και εκατομυρίων κόμβων.
• Εξομοιώσεις με Χρήση Υπολογιστών: Οι εξομοιώσεις σε υπολογιστές αποτελούν ένα μέσο που υπόσχεται την αντιμετώπιση της δημιουργίας αλγορίθμων και πρωτοκόλλων σε δίκτυα αισθητήρων.Κατά τις εξομοιώσεις με χρήση υπολογιστών είναι διαθέσιμο ένα σύνολο από εργαλεία προσομοίωσης, τα οποία αναπαράγουν συνθήκες πραγματικού κόσμου(όπως ιδιότητες της διάδοσης του ραδίου,περιβαλλοντικές συνθήκες) μέσα σε ένα περιβάλλον εξομοίωσης.Το γεγονός αυτό μετριάζει τις απαραίτητες προσπάθειες για ανάπτυξη ενός δικτύου στον πραγματικό κόσμο και βοηθάει στην αύξηση του μεγέθους του.Τα εργαλεία αυτά παρέχουν πολύ μεγάλο επίπεδο λεπτομέρειας όμως δεν λαμβάνουν υπόψιν έναν σημαντικό συντελεστή: το πλήθος των παραγόντων που επηρεάζουν τη συμπεριφορά ολόκληρου του δικτύου καθιστά σχεδόν αδύνατη την απομόνωση μιας συγκεκριμένης παραμέτρου.

Για παράδειγμα, ας θεωρήσουμε την ανάπτυξη ενός νέου πρωτοκόλλου δρομολόγησης.Στην περίπτωση που η ρυθμαπόδοση του πρωτοκόλλου είναι χαμηλή, κάποιος δεν μπορεί να γνωρίζει εξαρχής ποια είναι η πηγή του προβλήματος καθώς υπάρχουν πολλά πιθανά αίτια: το επίπεδο MAC μπορεί να έχει λάθη,δικτυακή κίνηση από άλλους αποστολείς μπορεί να περιορίζει το εύρος ζώνης,καποιες ιδιότητες της διάδοσης του ραδίου μπορεί να έχουν αλλάξει ή ο αλγόριθμος δρομολόγησης δεν είναι ακόμα βέλτιστος.Έτσι, δεν είναι αρκετό μόνο να εξοιμοιώσουμε ένα μεγάλο αριθμό κόμβων με μεγάλο επίπεδο λεπτομέρειας.Αντιθέτως, οι προγραμματιστές απαιτούν την ικανότητα να συγκεντρώνονται στο πραγματικό πρόβλημα.Όταν σχεδιάζεται ένας αλγόριθμος είναι σημαντικό να κατανοείται η δομή του υποκείμενου δικτύου που αναλύεται συνήθως ένα επίπεδο παραπάνω από τις τεχνικές λεπτομέρειες των κόμβων.

Τα χαρακτηριστικά της επικοινωνίας παίζουν σίγουρα σημαντικό ρόλο στην απόδοση ενός πρωτοκόλλου καθώς επηρεάζουν τους χρόνους μετάδοσης,τα μονοπάτια επικοινωνίας και την απώλεια πακέτων.Από την πλευρά του αλγορίθμου δεν υπάρχει διαφορά ανάμεσα σε μια πλήρης εξομοίωση του φυσικού περιβάλλοντος και της εναλλακτικής προσέγγισης χρησιμοποιώντας γνωστές τυχαίες διανομές πάνω στην καθυστέρηση και απώλεια μηνύματος.Έτσι, χρησιμοποιώντας λεπτομερή εξομοίωση μπορεί να καταλήξουμε σε μία κατάσταση όπου ο εξομοιωτής σπαταλάει χρόνο για την παραγωγή αποτελεσμάτων χωρίς ιδιαίτερο ενδιαφέρον.Για την βελτίωση αυτής της κατάστασης προτάθηκε το εξομοιωτικό εργαλείο Shawn του οποίου η βασική ιδέα είναι να αντικαταστήσει τις χαμηλού επιπέδου επιδράσεις με αφηρημένα μοντέλα έτσι ώστε να είναι δυνατή η εξομοίωση μεγάλου μεγέθους δικτύων σε λογικό χρόνο με συγκέντρωση πάντα στο ερευνητικό πρόβλημα.

Σχεδιαστικοί Στόχοι

Οι πρωταρχικοί σχεδιαστικοί στόχοι του εργαλείου Shawn αναφέρονται παρακάτω:

• Εξομοίωση των Αποτελεσμάτων που Προκαλούνται από ένα Φαινόμενο: Τα περισσότερα εργαλεία εξομοίωσης προσομοιώνουν πλήρως το MAC επίπεδο συμπεριλαμβανομένων των ιδιοτήτων της διάδοσης του ραδίου όπως εξασθένηση,σύγκρουση και διάδοση μέσω πολλαπλών μονοπατιών.Μία βασική σχεδιαστική ιδέα του Shawn είναι η εξομοίωση των αποτελεσμάτων ενός φαινομένου και όχι μόνο το φαινόμενο.Έτσι το Shawn εξομοιώνει μόνο τα αποτελέσματα ενός MAC επιπέδου (απώλεια πακέτων, καθυστέρηση,φθορά) στην εκάστοτε εφαρμογή. Αυτό έχει διάφορες επιπτώσεις στις εξομοιώσεις που γίνονται με το εργαλείο Shawn.Αφενός, οι εξομοιώσεις είναι προβλέψιμες και υπάρχει κέρδος απόδοσης καθώς ένα τέτοιο μοντέλο μπορεί να υλοποιηθεί αποδοτικά, αφετέρου, το εργαλείο αυτό δεν μπορεί να παρέχει λεπτομέρεια ίδιου επιπέδου π.χ. με το εργαλείο NS-2 σχετικά με το φυσικό επίπεδο ή με φαινόμενα επιπέδου πακέτου.Παρόλα αυτά, εάν το μοντέλο επιλεχθεί σωστά τα αποτελέσματα της εξομοίωσης είναι τα ίδια.Θεωρήστε, για παράδειγμα, δύο διαφορετικές υλοποιήσεις ενός MAC επιπέδου: μια αφηρημένη που αποφέρει αυξημένη απώλεια πακέτων σε υψηλή τοπική κίνηση και μία που υπολογίζει την παρεμβολή μοναδικών πακέτων xρησιμοποιώντας μοντέλα διάδοσης ραδίου.Και οι δύο υλοποιήσεις θα παράγουν τα ίδια αποτελέσματα στο επίπεδο εφαρμογής. Στο σημείο αυτό πρέπει να ανφερθεί ότι η ερμηνεία των αποτελεσμάτων πρέπει να λαμβάνει υπόψιν τις ιδιότητες των μοντέλων.Για παράδειγμα, η χρήση ενός απλοποιημένου μοντέλου επικονωνίας για την παροχή των αποτελεσμάτων ενός αλγορίθμου εντοπισμού δεν επηρεάζει την ποιότητα της λύσης αλλά ο χρόνος εκτέλεσης του αλγορίθμου δεν είναι αντιπροσωπευτικός για πραγματικές εφαρμογές καθώς δεν υπάρχει καθυστέρηση ή απώλεια μηνυμάτων.
• Επεκτασιμότητα και Υποστήριξη Μεγάλων Δικτύων: Ένας κεντρικός στόχος του Shawn είναι να υποστηρίξει σημαντικά μεγαλύτερες τάξεις μεγέθους δικτύων από τους υπάρχοντες εξομοιωτές.Το εργαλείο Shawn μπορεί να εξομοιώσει τεράστια δίκτυα καθώς απλοποιεί τη δομή πολλών χαμηλού-επιπέδου παραμέτρων.Για την επίτευξη χαμηλών χρόνων εξομοίωσης μπορούν να επιλεγούν οι κατάλληλες επιλογές διαμόρφωσης.Αυτό επιτρέπει στους προγραμματιστές να βελτιστοποιούν την απόδοση του Shawn για κάθε διαφορετικό σενάριο.Για παράδειγμα, ένα σενάριο που δεν προυποθέτει κινητικότητα των κόμβων μπορεί να εξεταστεί διαφορετικά από ένα άλλο στο οποίο οι κόμβοι κινούνται.
• Ελεύθερη Επιλογή του Μοντέλου Υλοποίησης: Το εργαλείο Shawn υποστηρίζει ένα πολυ-επίπεδο κύκλο ανάπτυξης στον οποίο οι προγραμματιστές μπορούν ελεύθερα να επιλέξουν το μοντέλο υλοποίησης όπως φαίνεται και στο παρακάτω σχήμα.

• Καζίνο-Ονλάϊν

Η λογική πίσω από αυτήν την προσέγγιση είναι ότι δεδομένης μιας ιδέας για έναν αλγόριθμο, δεν σχεδιάζεται άμεσα ένα κατανεμημένο πρωτόκολλο αλλά γίνεται πρώτα μια δομική ανάλυση του προβλήματος.Για την καλύτερη κατανόηση του προβλήματος προτείνεται η δομική ανάλυση διαφορετικών δικτύων. Το επόμενο βήμα είναι η υλοποίηση μιας κεντρικοποιημένης εκδοχής του αλγορίθμου για την επίτευξη μιας πρωτότυπης εκδοχής.Ένας κεντρικοποιημένος αλγόριθμος έχει πλήρη πρόσβαση σε όλους τους κόμβους και επίπεδη όψη του δικτύου.Από την διαδικασία αυτή δημιουργείται μια πρώτη εκτίμηση για την απόδοση του αλγορίθμου καθώς και τρόποι βελτίωσης του. Αφού μια κεντρικοποιημένη εκδοχή του αλγορίθμου έχει υλοποιηθεί εξετάζεται η δυνατότητα επίτευξης μιας κατανεμημένης εκδοχής.Για το σκοπό αυτό χρησιμοποιείται ένα απλοποιημένο μοντέλο επικονωνίας μεταξύ των κόμβων το οποίο επιτρέπει μια αποτελεσματική και γρήγορη υλοποίηση με σημαντικά αποτελέσματα. Τέλος, η απλοποιημένη εκδοχή μεταμορφώνεται σε ένα πρωτόκολλο το οποίο ανταλλάσει μηνύματα στο δίκτυο.Με το πρωτόκολλο και τις κατάλληλες δομές έτοιμες, η απόδοση της κατανεμημένης υλοποίσης μπορεί να αξιολογηθεί ως πρός διάφορα θέματα όπως αριθμό μηνυμάτων, κατανάλωση ενέργειας και ελαστικότητα στην απώλεια και φθορά μηνυμάτων.Ο παραπάνω κύκλος ανάπτυξης που περιγράφηκε βοηθάει έναν προγραμματιστή να φτάσει από την αρχική ιδέα σε ένα πλήρως κατανεμημένο πρωτόκολλο.

Αρχιτεκτονική

Η αρχιτεκτονική του εξομοιωτή Shawn αποτελείται από τρία βασικά μέρη τα οποία φαίνονται παρακάτω:

• Τα μοντέλα (Models)
• Διαδοχέας (Sequencer)
• Περιβάλλον Εξομοίωσης (Simulation Environment)

Το εργαλείο Shawn επηρεάζεται από ένα ή περισσότερα μοντέλα (Models), τα οποία αποτελούν κλειδί για την ευελιξία και επεκτασιμότητα του.Ο διαδοχέας Sequencer είναι η κεντρική συνεργατική μονάδα που διαμορφώνει και ελέγχει την εξομοίωση και εκτελεί διαδοχικά τις εργασίες.To περιβάλλον εξομοίωσης είναι αυτό που φιλοξενεί τον εικονικό κόσμο στον οποίο βρίσκονται οι κόμβοι του δικτύου.Παρακάτω, καθένα από τα στοιχεία της αρχιτεκτονικής εξετάζεται ξεχωριστά.

Μοντέλα (Models)

Τα μοντέλα είναι οι διεπαφές (interfaces) που χρησιμοποιεί το Shawn για να ελέγχει την εξομοίωση χωρίς να γνωρίζει την δομή μιας υλοποίησης.Το Shawn διατηρεί μια αποθήκη από υλοποιήσεις μοντέλων που μπορούν να χρησιμοποιηθούν για τον ορισμό μιας εξομοίωσης επιλέγοντας την επιθυμητή συμπεριφορά.Η υλοποίηση ενός μοντέλου μπορεί να είναι απλοποιημένη και γρήγορη, ή να παρέχει κοντινή προσέγγιση της πραγματικότητας.Αυτό επιτρέπει στον χρήστη να διαλέξει την πιο κατάλληλη υλοποίηση μοντέλου για μια συγκεκριμένη εργασία.Όπως φαίνεται και στο παραπάνω σχήμα τα βασικά μοντέλα που υποστηρίζει το Shawn είναι τα παρακάτω:

• Communication Model
• Edge Model
• Transmission Model

Τα μοντέλα αυτά παρουσιάζονται εκτενώς στη συνέχεια.

Communication Model

Όταν ένας κόμβος του εικονικού δικτύου μεταδίδει ένα μήνυμα, οι πιθανοί παραλήπτες πρέπει να αναγνωρίζονται από τον εξομοιωτή.Το μοντέλο επικοινωνίας ορίζει εαν δύο κόμβοι μπορούν να επικοινωνήσουν.Ο παρακάτω κώδικας παρουσιάζει τη C++ διεπαφή του Communication Model.Μία απλή μέθοδος καθορίζει ο κόμβος b μπορεί να επικοινωνήσει με τον κόμβο a.

class CommunicationModel
{
   ...
   bool can_communicate_uni (Node& a, Node& b);
   ...
};

Υλοποιώντας την παραπάνω διεπαφή με κώδικα ορισμένο από τον χρήστη, διάφορα πρότυπα επικοινωνίας μπορούν να υλοποιηθούν.Κάποιες υλοποιήσεις του Communication Modelφαίνονται παρακάτω:

Οι παραπάνω υλοποιήσεις αναπαριστούν πρότυπα επικοινωνίας που χρησιμοποιούνται συχνά στα ασύρματα δίκτυα αισθητήρων.Στα σχήματα φαίνονται οι γειτονικοί κόμβοι (κόμβοι που φαίνονται με μαύρες τελείες) των κόμβων n1 και n2(κόμβοι που φαίνονται με μαύρες τελείες με ένα επιπλέον δακτύλιο).Το μοντέλο Unit Disk Graphβασίζεται στην παρατήρηση ότι η ισχύς ενός σήματος εξασθενίζει αντιστρόφως ανάλογα με το τετράγωνο της απόστασης από τον αποστολέα.Δεδομένης μιας ισχύς σήματος που απαιτείται για λήψη εκπομπής, δύο κόμβοι μπορούν να επικοινωνήσουν αν η ευκλείδια απόσταση τους είναι μικρότερη από rmax.Το μοντέλο αυτό χρησιμοποιείται συχνά στην έρευνα γύρω από τα ασύρματα δίκτυα αισθητήρων λόγω της απλότητας του.

Το μοντέλο ραδίου Quasi-Unit Disk Graph ορίζει δύο αποστάσεις r1 και r2 για τις οποίες ισχύει r1<r2.Στην περίπτωση όπου 0<d<r1 ή d>r2 η συμπεριφορά του είναι ίδια με αυτήν του Unit Disk Graph.Στην περίπτωση όπου r1 <= d <= r2, η πιθανότητα λήψης ενός πακέτου μειώνεται γραμμικά από το 1 στο 0.Ισχύει δηλαδή το γεγονός ότι η πιθανότητα επιτυχημένης λήψης μειώνεται καθώς η απόσταση αυξάνεται.Στην παραπάνω εικόνα φαίνεται ένα παράδειγμα με r1=0.75*r_max και r2=1.25*r_max.

Βασιζόμενο σε πραγματικά πειράματα, το μοντέλο Radio Irregularity Model, προτείνει ένα υπο γωνία εύρος εκπομπής ανάμεσα σε ένα ελάχιστο και ένα μέγιστο εύρος επικοινωνίας (r_min,r_max).Ένας παράγοντας καθορίζει τη μέγιστη αλλαγή στο εύρος εκπομπής και έτσι ελέγχεται η αταξία που φαίνεται στο παραπάνω σχήμα.Σε αντίθεση με τα προηγούμενα μοντέλα επικονωνίας το Radio Irregularity Model υποστηρίζει και συνδέσμους μονής κατεύθυνσης.

Εκτός από τα παραπάνω μοντέλα υπάρχουν και τα μοντέλα Permanent Link και Chained Communication Model.Το πρώτο επιτρέπει τον προσδιορισμό στατικών συνδέσμων όπως για παράδειγμα κάποιες ενσύρματες συνδέσεις που υποστηρίζουν οι κόμβοι πύλης(gateway nodes).Το Chained Communication Model υποστηρίζει τον συνδυασμό πολλών μοντέλων επικοινωνίας σε ένα καινούριο.Για παράδειγμα μπορεί όλοι οι κόμβοι του δικτύου να χρησιμοποιούν το Unit Disk Graph μοντέλο επικοινωνίας ενώ οι κόμβοι πύλης να υποστηρίζουν κάποιες ενσύρματες συνδέσεις που να μοντελοποιούνται με το μοντέλο Permanent Link.

Edge Model

Το μοντέλο Edge Model προσφέρει μια γραφική αναπαράσταση του δικτύου.Οι εξομοιωμένοι κόμβοι αποτελούν τις κορυφές του γραφήματος και μία ακμή ανάμεσα σε δύο κόμβους προστίθεται όποτε το Communication Modelεπιστρέφει true.Για τη συναρμολόγηση του γραφήματος το Edge Model συνέχεια θέτει ερωτήσεις (query) στο Communication Model, προσπελαύνοντας με τον τρόπο αυτό τους άμεσους γείτονες ενός κόμβου,τους γείτονες των γειτόνων και ούτω καθ'εξής.Έτσι το Shawn παρατηρώντας τους γείτονες ενός κόμβου αναγνωρίζει τους πιθανούς παραλήπτες ενός μηνύματος.Απλοί, κεντρικοποιημένοι αλγόριθμοι που χρειάζονται τις πληροφορίες από το γράφημα επικοινωνίας μπορούν να υλοποιηθούν εύκολα και αποτελεσματικά καθώς δεν χρειάζεται να γίνει ανταλλαγή μηνυμάτων για την εύρεση των γειτόνων των κόμβων.

Παρακάτω φαίνεται η C++ διεπαφή για την υλοποίηση Edge Model στο εργαλείο Shawn.Οι δύο μέθοδοι που περιέχονται στη διεπαφή δίνουν τη δυνατότητα εύρεσης των γειτόνων ενός κόμβου για μια συγκεκριμένη κατεύθυνση επικοινωνίας.Η παράμετρος επικοινωνίας CommunicationDirection μπορεί να πάρει τις τιμές in, out, bidirectional ή any και ορίζει τον τρόπο επικοινωνίας με τον οποίο ένας κόμβος αποτελεί γείτονα ενός άλλου.

class EdgeModel
{
  ...
  adjacency_iterator begin_adjacent_nodes (Node &,
  CommunicationDirection d = bidi);

  adjacency_iterator end_adjacent_nodes (Node &);
  ...
};

Η κατεύθυνση επικοινωνίας ορίζεται ως εξής: οι κόμβοι u και v είναι γείτονες εάν για την κατεύθυνση επικοινωνίας :

• 'in': ο κόμβος v μπορεί να επικοινωνήσει με τον u (uni(v,u)).
• 'out': ο κόμβος u μπορεί να επικοινωνήσει με τον v (uni(u,v)).
• 'bidi': ο κόμβος v μπορεί να επικοινωνήσει με τον u και ο κόμβος u μπορεί να επικοινωνήσει με τον v (uni(v,u) και uni(u,v)).
• 'any': ο κόμβος v μπορεί να επικοινωνήσει με τον u ή ο κόμβος u μπορεί να επικοινωνήσει με τον v (uni(v,u) ή uni(u,v)).

Ανάλογα τις απαιτήσεις και τις ιδιότητες της εκάστοτε εφαρμογής χρειάζονται διαφορετικά μοντέλα αποθήκευσης των γραφημάτων.Για παράδειγμα, σενάρια που υποθέτουν κινητικότητα των κόμβων απαιτούν διαφορετικό μοντέλο αποθήκευσης του γραφήματος του δικτύου από εκείνα που θεωρούν τους κόμβους του δικτύου στατικούς.Επιπλεόν, εξοιμοιώσεις μικρών δικτύων επιτρέπουν την αποθήκευση ολόκληρης της γειτονιάς ενός κόμβου στη μνήμη του κάτι που είναι πολύ δύσκολο σε τεράστια δίκτυα λόγω μεγάλων απαιτήσεων μνήμης.Για τους παραπάνω λόγους, παρέχει τις παρακάτω υλοποιήσεις του Edge Model.

Το μοντέλο Grid Edge Model χρησιμοποιεί ένα πλέγμα δύο διαστάσεων για την διευθέτηση των κόμβων βάσει της γεωμετρικής τους θέσης.Έτσι η αναζήτηση γειτονικών κόμβων περιορίζεται σε αυτούς που βρίσκονται σε κοντινές θέσεις, βελτιώνοντας τον χρόνο αναζήτησης και ταυτόχρονα υποστηρίζοντας σενάρια κινητικότητας των κόμβων.Το μοντέλο List Edge Model στην αρχή της εξομοίωσης αποθηκεύει όλο το γράφημα του δικτύου στη μνήμη.Το γεγονός αυτό επιτρέπει πολύ γρήγορη αναζήτηση γειτονικών κόμβων όμως έχει υψηλές απαιτήσεις σε μνήμη και σε χρόνο(διαδικασία κατασκευής της λίστας στην αρχή της εξομοίωσης).Ακόμα επειδή η λίστα με τους γειτονικούς κόμβους δημιουργείται στην αρχή της εξομοίωσης υποστηρίζει μόνο σενάρια που θεωρούν στατικούς τους κόμβους του δικτύου.Το μοντέλο Fast List Model συνδυάζει την λειτουργικότητα των μοντέλων Grid και List σε ένα νέο.Eσωτερικά, χρησιμοποιεί το μοντέλο Grid για την κατασκευή ενός περιεχόμενου List μοντέλου. Ως αποτέλεσμα παρέχει τα χαρακτηριστικά του μοντέλου List με γρήγορη αρχική κατασκευή της λίστας με κόστος υψηλότερων απαιτήσεων σε μνήμη.

Transmission Model

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

Αυτό σημαίνει ότι ένα μήνυμα μπορεί να μην φτάσει ποτέ στον προορισμό του ακόμα και αν το Communication Modelδηλώνει ότι οι δύο κόμβοι μπορούν να επικοινωνήσουν και το Edge Model δηλώνει τους δύο κόμβους αυτούς ως γείτονες.Ο παρακάτω κώδικας παρουσιάζει τη C++ διεπαφή για την υλοποίηση Transmission Model στο εργαλείο Shawn.

class TransmissionModel
{
  struct MessageInfo
  {
    Node* src_;
    Vec src_pos_;
    double time_;
    MessageHandle msg_;
  };
  ...
  void send_message (MessageInfo&);
  ...
};

Επαναλαμβάνουμε ότι η επιλογή μιας υλοποίησης του Transmission Model εξαρτάται από τον σκοπό της εξομοίωσης.Αν μας ενδιαφέρει μόνο η ποιότητα του αλγορίθμου και όχι ο χρόνος εκτέλεσης, τότε ένα απλό μοντέλο μετάδοσης χωρίς καθυστέρηση, τροποποίηση και απώλεια μηνυμάτων είναι αρκετό.Μοντέλα που είναι πιο εξηζητημένα,λαμβάνουν υπόψιν την σύγκρουση μηνυμάτων, τον χρόνο μετάδοσης και τα λάθη μετάδοσης για την μέτρηση της απόδοσης του πρωτοκόλλου.Παρακάτω φαίνονται τα βασικά Transmission Models που υποστηρίζει το Shawn.

Το Reliable Transmission Model παραδίδει αμέσως όλα τα μηνύματα χωρίς απώλειες ή φθορά στους γειτονικούς κόμβους.Το μοντέλο Random Drop απορίπτει κάποια πακέτα με μια δεδομένη πιθανότητα αλλά δεν τα καθυστερεί ούτε τα τροποποιεί.Η υλοποίηση Statistics δεν παραδίδει κανένα μήνυμα αλλά καταγράφει στατιστικές πληροφορίες όπως αριθμός μηνυμάτων, διαφορετικοί τύποι μηνυμάτων κτλ.Για την χρήση ενός τέτοιου μη-λειτουργικού Transmission Model το Chainable Transmission Model επιτρέπει μια σειρά από μοντέλα να επεξεργαστούν ένα μήνυμα διαδοχικά.Με τον τρόπο αυτό ένα μήνυμα μπορεί να μεταδοθεί κανονικά, στη συνέχεια να καθυστερήσει και μετά να αποριφθεί χρησιμοποιώντας διαφορετικά μοντέλα μετάδοσης κάθε φορά.

Τέλος υπάρχουν δύο υλοποιήσεις Transmission Model που πλησιάζουν περισσότερο τις πραγματικές συνθήκες.Εξοιμοιώνουν τα αποτελέσματα των γνωστών Reliable Transmission Model και slotted Aloha σχημάτων πρόσβασης μέσου.Στο σημείο αυτό επισημαίνουμε ότι δεν εξομοιώνεται το MAC πρωτόκολλο, αλλά μοντελοποιούνται τα χαρακτηριστικά καθυστέρησης και απώλειας για λόγους απόδοσης.

Ετερόκλητα Μοντέλα (Miscellaneous Models)

Εκτός από τα βασικά μοντέλα που αναφέρθηκαν παραπάνω, το Shawn παρέχει και άλλα πιο εξειδικευμένα όπως μοντέλα για τυχαίες μεταβλητές, μοντέλα υπολογισμού αποστάσεων και μοντέλα που υποστηρίζουν την κινητικότητα των κόμβων.

Οι τυχαίες μεταβλητές xρησιμοποιούνται συχνά στις εξομοιώσεις για να μιμηθούν την αβεβαιότητα και την τυχαιότητα που υπάρχει στον πραγματικό κόσμο.Το μοντέλο Random Variable εισάγει ένα αφηρημένο επίπεδο ανάμεσα στις πηγές των τυχαίων δεδομένων και της εφαρμογής με αποτέλεσμα να μπορούν να εξετασθούν οι αλγόριθμοι, με υποκείμενες τυχαίες μεταβλητές, χωρίς να αλλάζει η υλοποίηση τους.Οι κόμβοι στα ασύρματα δίκτυα αισθητήρων συνήθως χρειάζονται κάποια εκτίμηση της απόστασης τους σε σχέση με άλλους κόμβους ώστε να μπορέσουν να ανακαλύψουν τη θέση τους μέσα στο δίκτυο.Στο Shawn το μοντέλο Node Distance Estimate προσφέρει αυτές τις εκτιμήσεις και βοηθάει στην αξιολόγηση των αλγορίθμων εντοπισμού (localization).Η τυχαία κίνηση των κόμβων μέσα σε ένα δίκτυο μοντελοποιείται από το Node Movements.Το μοντέλο αυτό όταν διερωτάται από την εφαρμογή ή από το μοντέλο επικοινωνίας παρέχει την τρέχουσα θέση ενός κόμβου.

Διαδοχέας (Sequencer)

Ο Sequencer αποτελεί το κέντρο ελέγχου της εξομοίωσης: προετοιμάζει τον κόσμο μέσα στον οποίο οι κόμβοι θα αναπτυχθούν, αρχικοποιεί και παραμετροποιεί τις υλοποιήσεις των μοντέλων που έχουν επιλεχθεί από την διαμόρφωση εισόδου.Αποτελείται από:

• Simulation Tasks
• Simulation Controller
• Event Scheduler

Simulation Tasks

Τα Simulation Tasks αποτελούν κομμάτια κώδικα που καλούνται από την διαμόρφωση της εξομοίωσης που παρέχεται από τον χρήστη.Δεν είναι άμεσα συνδεδεμένα με την εφαρμογή αλλά έχουν πρόσβαση στο περιβάλλον εξομοίωσης και είναι ικανά να εκτελέσουν ένα σύνολο από εργασίες (tasks), όπως π.χ. διαχείριση της εξομοίωσης, εκτέλεση κεντρικοποιημένων αλγορίθμων και συλλογή δεδομένων από τους κόμβους.

Το εργαλείο Shawn χρησιμοποιεί τα tasks για να αποκαλύψει τα εσωτερικά του χαρακτηριστικά στον χρήστη.Περιλαμβάνει ένα σύνολο εργασιών που δημιουργούν κόσμους εξομοίωσης, κόμβους μέσα σε αυτούς, πρωτόκολλα δρομολόγησης, τυχαίες μεταβλητές κτλ.Ακόμα και η εξομοίωση ενεργοποιείται χρησιμοποιώντας μια εργασία στην οποία ο χρήστης μπορεί να ορίσει το χρόνο εξομοίωσης.

Τα Simulation Tasks ελέγχονται από τον Simulation Controller ο οποίος αναλύεται παρακάτω.Αναγνωρίζονται από ένα μοναδικό όνομα και οι παράμετροι εισάγονται σε μορφή ζευγαριών (όνομα,τιμή).Ο παρακάτω κώδικας παρουσιάζει την διεπαφή ενός Simulation Task.Αποτελείται από μια μέθοδο που επιστρέφει το όνομα της εργασίας, μία που επιστέφει την περιγραφή της και μία την εκτελεί.

class SimulationTask
{
  ...
  void run (SimulationController&);
  string name ();
  string description ();
  ...
};

Simulation Controller

Ο Simulation Controller αποτελεί την κεντρική αποθήκη για όλες τις υλοποιήσεις των μοντέλων και εκτελεί την εξομοίωση μετατρέποντας τη διαμόρφωση εισόδου (configuration) σε παραμετροποιημένες επικλήσεις των Simulation Tasks.Με τον τρόπο αυτό ο Simulation Controller αποτελεί το μέσο ανάμεσα στον πυρήνα της εξομοίωσης και τον χρήστη.Όπως και τα υπόλοιπα στοιχεία του Shawn, o Simulation Controller μπορεί να προσαρμοστεί από έναν προγραμματιστή ώστε αυτός να αποκτήσει τον έλεγχο της εξομοίωσης.Η βασική υλοποίηση διαβάζει τις εντολές διαμόρφωσης από ένα αρχείο ή από το ρεύμα εισόδου.Ο παρακάτω κώδικας δείχνει πως είναι δομημένες οι εντολές.

  ...
  global_name1=global_value1
  ...
  task_name name1=value1 name2=value2

Η πρώτη γραμμή δείχνει πως δηλώνεται ένα καθολικό ζευγάρι-(όνομα,τιμή), το οποίο είναι έγκυρο μέχρι η εξομοίωση να τελειώσει.Η τρίτη γραμμή παρουσιάζει πως καλείται ένα task καθορίζοντας το όνομα του ακολουθούμενο από ζευγάρια-(όνομα,τιμή) κατάλληλα για την εκτέλεση του.Εάν το simulation task με το αντίστοιχο όνομα βρεθεί, επικαλείται η run() μέθοδος του με ορίσματα το σύνολο ζευγών (όνομα,τιμή).Μια δεύτερη υλοποίση του Shawn που ονομάζεται JShawn επιτρέπει τη χρήση Java scripts για την καθοδήγηση της εξομοίωσης, προσφέροντας την ίδια λειτουργικότητα με πιο πολύπλοκες κατασκευές εικονικών κόσμων.

Event Scheduler

Το εργαλείο Shawn χρησιμοποιεί τον Event Scheduler για να μοντελοποιήσει τον χρόνο.Τα αντικείμενα που χρειάζονται την έννοια του χρόνου καταχωρούνται στον Event Scheduler και ειδοποιούνται σε τυχαία στιγμή.Η εξομοίωση πάντα προχωράει προς το επόμενο γεγονός και αντίστοιχα ειδοποιεί τον κατάλληλο χειριστή του γεγονότος αυτού.Η διαδικασία συνεχίζεται μέχρι όλοι οι κόμβοι του δικτύου να γίνουν ανενεργοί ή μέχρι να τελειώσει ο χρόνος εξομοίωσης.

Η χρήση του Event Scheduler έχει κάποια πλεονεκτήματα σε σχέση με εκείνες τις προσεγγίσεις που χρησιμοποιούν προκαθορισμένα διαστήματα χρόνου (όπως το clock-tick κάθε 1 ms): Πρώτον, οι χειριστές καλούνται μόνο κατά την ακριβή ώρα που έχουν ζητήσει αποφεύγοντας έτσι κλήσεις σε κόμβους που είναι αδρανείς ή σε αναμονή.Δεύτερον, ένα γεγονός μπορεί να συμβεί με τη μέγιστη ακρίβεια που προσφέρεται από τους αριθμούς κινητής υποδιαστολής.Στην παρακάτω εικόνα φαίνεται πως ο Event Scheduler επιτρέπει στις εξομοιώσεις να χρησιμοποιήσουν αυτόν το χρονο-μηχανισμό.

To Shawn οργανώνει λογικά τις εξομοιώσεις σε γύρους ( r=0,1,2,...).Ένας χρήστης μπορεί να καταχωρήσει Simulation Tasks ως pre-step ή ως post-step εργασίες οι οποίες εκτελούνται αμέσως πριν ή αμέσως μετά αντίστοιχα, από τον γύρο της εξομοίωσης.Αυτό είναι χρήσιμο για την παραγωγή πληροφορίας από την εξομοίωση χωρίς να αναμειχθεί κώδικας της εξομοίωσης με κώδικα που αφορά την απόδοση του αλγορίθμου.Στην αρχή κάθε γύρου, καλείται η work() μέθοδος ενός κόμβου.Οι εφαρμογές μπορούν να επιλέξουν να χρησιμοποιήσουν αυτή τη μέθοδο για μία πιο άνετη υλοποίηση εφόσον δεν απαιτείται ακριβής συγχρονισμός.Εκτός από αυτά τα σταθερά διαστήματα, οι κόμβοι μπορούν να καταχωρήσουν ένα γεγονός σε οποιοδήποτε σημείο στο χρόνο.Με τον τρόπο αυτό οι εφαρμογές έχουν την ευελιξία να ενσωματώσουν χρονικά πλαίσια στην εξομοίωση χωρίς να υποβαθμίσουν την απόδοση τους.

Περιβάλλον Εξομοίωσης (Simulation Environment)

Το περιβάλλον εξομοίωσης (Simulation Environment) φιλοξενεί τον εικονικό κόσμο μέσα στον οποίο τα αντικείμενα της εξομοίωσης αναπτύσονται.Όπως φαίνεται και στο Σχήμα 1.2 [[#Αρχιτεκτονική|] οι κόμβοι ανήκουν σε ένα στιγμιότυπο του εικονικού κόσμου και περιέχουν τους λεγόμενους επεξεργαστές(processors).

Κόμβοι και Επεξεργαστές

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

Παρακάτω φαίνεται η διεπαφή του επεξεργαστή.Όταν ένας επεξεργαστής αρχικοποιείται, καλείται η boot() μέθοδος του.Ένας επεξεργαστής μπορεί να στείλει ένα μήνυμα καλώντας τη μέθοδο send().Όταν ένας κόμβος λαμβάνει ένα μήνυμα το προωθεί στους επεξεργαστές του.Ο επεξεργαστής για τον οποίο το μήνυμα προορίζεται,χρησιμοποιώντας την αντίστοιχη μέθοδο process_message() το λαμβάνει.Όπως αναφέρθηκε και προηγουμένως η μέθοδος work() του κάθε επεξεργαστή καλείται κάθε φορά ο Event Scheduler ξεκινά έναν νέο γύρο εξομοίωσης.

class Processor
{
  ...
  void boot( );
  bool process_message( MessageHandle& );
  void work( );
  Node& owner( );
  void send( MessageHandle& );
  ...
};

Ένας κόμβος προσφέρει κάποιες υπηρεσίες στους επεξεργαστές οι οποίες διευκολύνουν την υλοποίηση των αλγορίθμων και απλοποιούν την εργασία της εξομοίωσης.Όπως αναφέραμε και προηγουμένως το μοντέλο Edge Model χρησιμοποιείται για να αναγνωρίζει τους γείτονες ενός κόμβου.Σε αντίθεση με άλλους εξομοιωτές το Shawn δεν περιορίζει τον χρήστη σε προγραμματισμό προσανατολισμένο στα μηνύματα αλλά υποστηρίζει και συντομεύσεις όπως π.χ. απευθείας κλήση της μεθόδου execute() σε άλλο κόμβο.Κάτι τέτοιο είναι επικερδές όταν για παράδειγμα υλοποιείται ένας κεντρικοποιημένος αλγόριθμος.

Διαχωρίζοντας τις Μεταβλητές Κατάστασης από τις Μεταβλητές Μέλη

Είναι σύνηθες το φαινόμενο ένας αλγόριθμος να απαιτεί ώς είσοδο τα αποτελέσματα κάποιων άλλων (πιθανότατα πολύπλοκων) αλγορίθμων.Για την αποφυγή της αναμονής των αποτελεσμάτων από προηγούμενα βήματα σε κάθε εξομοίωση, το Shawn παρέχει τη δυνατότητα να συνάψει κανείς ασφαλείς πληροφορίες στους κόμβους, στον εικονικό κόσμο και στο περιβάλλον εξομοίωσης.Δύο Simulation Tasks, τα load_world και save_world επιτρέπουν την φόρτωση Tags από XML έγγραφα και την αποθήκευση Tags σε αυτά.Υπάρχουν τρία είδη Tags:

• Simple Tags : περιέχουν μια τιμή συγκεκριμένου τύπου π.χ. string,boolean.
• Group Tags : περιέχουν άλλα Tags.
• Map Tags : περιέχουν ζευγάρια τιμών συγκεκριμένου τύπου.

<scenario>
 <snapshot id="0">
  <node id="runner12">
   <location x="135.0" y="5.0" z="0.0"/>

   //Simple Boolean Tag
   <tag type="bool" name="base station" value="false"/>

  </node>
 </snapshot>
</scenario>

//Find the Tag
ConstTagHandle th=owner().find_tag("base station");

//Cast to the expected type (error checking omitted)
const BoolTag* bt = 
             dynamic cast(th.get());
 
//Retrieve the Tags value
bool is_basestation=bt -> value ();

Στην πρώτη εικόνα φαίνεται ένα XML αρχείο που περιέχει ένα Simple Tag τύπου boolean και στην δεύτερη παρουσιάζεται ο τρόπος με τον οποίο ένας κόμβος θα προσπέλαυνε αυτό το Boolean Tag που ονομάζεται base station.

Το πλεονέκτημα αυτής της σύλληψης είναι ότι διαχωρίζονται οι μεταβλητές κατάστασης από τις μεταβλητές μέλη στον κώδικα της εξομοίωσης.Έτσι, κομμάτια ενός πολύπλοκου πρωτοκόλλου μπορούν να αντικατασταθούν χωρίς αλλαγή του κώδικα καθώς η εσωτερική κατάσταση αποθηκεύεται σε Tags και όχι στις μεταβλητές μέλη της υλοποίησης.

Μοντελοποιώντας Αισθητήρες και τις Τιμές τους

Για τη μοντελοποίηση των αισθητήρων και των τιμών τους παρέχονται τα γενικά πλαίσια που ονομάζεται Sensors και Readings.Το Readings παραδίδει τιμές εξαρτώμενες από τη θέση και το χρόνο.Το Sensors είναι συνδεδεμένο με ένα συγκεκριμένο κόμβο και παραδίδει τις τιμές των αισθητήρων.Τα παραπάνω πλαίσια μπορούν να καθοριστούν από τον χρήστη και προσπελαύνονται στην εξομοίωση με τα μοναδικά τους ονόματα.Ο διαχωρισμός αυτός επιτρέπει την αλλαγή στις υποκείμενη Readings ή Sensors υλοποίηση χωρίς να αλλάζει ο κώδικας της προσωμοίωσης.Το Shawn παρέχει κάποιες υλοποιήσεις Sensors και Readings, οι οποίες παίρνουν τις τιμές τους από XML αρχεία.