Κεφάλαιο 1
Διάδοση Δεδομένων σε Ασύρματα Δίκτυα Αισθητήρων¶
Καλύπτει: Flooding, Directed Diffusion, Omniscient Multicast, Flat vs Hierarchical Routing
1.1 Το Θεμελιώδες Πρόβλημα¶
Φανταστείτε ένα πεδίο καλυμμένο με εκατοντάδες μικροσκοπικούς, αυτόνομους αισθητήρες που τροφοδοτούνται από μπαταρία. Ένας από αυτούς ανιχνεύει κάτι ενδιαφέρον — μια απότομη αύξηση θερμοκρασίας, μια χημική ανωμαλία, μια κίνηση. Η μέτρηση αυτή δεν έχει καμία αξία αν παραμείνει αποθηκευμένη στον κόμβο. Πρέπει να φτάσει σε ένα κέντρο ελέγχου — τον λεγόμενο sink ή Base Station (BS) — όπου μπορεί κάποιος να δράσει.
Το ερώτημα που κινεί ολόκληρη αυτή τη θεματική ενότητα, όπως διατυπώνεται στις διαφάνειες του μαθήματος, είναι:
«How can sensor p, via cooperation with the rest of the sensors in the network, propagate information about event E to the control center(s)?»
Οι αισθητήρες δεν μπορούν να εκπέμψουν απευθείας στο BS — είναι συσκευές χαμηλής ισχύος με περιορισμένη εμβέλεια ραδιοεπικοινωνίας. Κάθε κόμβος επικοινωνεί μόνο με τους άμεσους γείτονές του. Τα δεδομένα πρέπει λοιπόν να μεταπηδήσουν (hop) από κόμβο σε κόμβο μέχρι να φτάσουν στον sink. Ο τρόπος οργάνωσης αυτών των «πηδημάτων» ονομάζεται πρωτόκολλο δρομολόγησης (routing protocol), και η επιλογή πρωτοκόλλου καθορίζει πόσο θα επιβιώσει το δίκτυο, πόσο γρήγορα φτάνουν τα δεδομένα, και πόση ενέργεια σπαταλιέται στη διαδρομή.
Υπάρχουν δύο θεμελιωδώς διαφορετικές φιλοσοφίες αντιμετώπισης αυτού του προβλήματος:
- Επίπεδη δρομολόγηση (flat routing): κάθε κόμβος-αισθητήρας είναι ισότιμος — κανείς δεν αναλαμβάνει ειδικό ρόλο. Τα δεδομένα ρέουν στο δίκτυο με βάση το περιεχόμενο της πληροφορίας. Χαρακτηριστικό παράδειγμα: Directed Diffusion (DD).
- Ιεραρχική δρομολόγηση (hierarchical routing): ορισμένοι κόμβοι αναλαμβάνουν ρόλους αρχηγών, οργανώνοντας τους γείτονές τους σε ομάδες (clusters). Χαρακτηριστικό παράδειγμα: LEACH.
Πριν εμβαθύνουμε στο Directed Diffusion, αξίζει να κατανοήσουμε την πιο απλή δυνατή προσέγγιση — και γιατί αποτυγχάνει.
1.2 Flooding: Η Ωμή Βία ως Σημείο Αναφοράς¶
Το Flooding είναι ακριβώς αυτό που υποδηλώνει το όνομά του — πλημμύρα. Όταν ένας αισθητήρας ανιχνεύει ένα γεγονός, εκπέμπει (broadcast) τα δεδομένα σε κάθε γείτονά του. Κάθε γείτονας τα αναμεταδίδει σε κάθε δικό του γείτονα. Η διαδικασία συνεχίζεται μέχρι κάθε κόμβος του δικτύου να έχει λάβει το μήνυμα — συμπεριλαμβανομένου του sink.
Ο μηχανισμός λειτουργεί ως εξής:
- Ο κόμβος-πηγή ανιχνεύει ένα γεγονός και το εκπέμπει.
- Κάθε κόμβος που λαμβάνει το μήνυμα το αναμεταδίδει ακριβώς μία φορά, ώστε να αποφευχθούν άπειροι βρόχοι.
- Τελικά, το μήνυμα κατακλύζει ολόκληρο το δίκτυο.
Αν υπάρχουν \(n\) πηγές και \(N\) συνολικοί κόμβοι, έχουμε \(nN\) μεταδόσεις. Σε ένα τετραγωνικό πλέγμα (square grid) μεγέθους \(\sqrt{N} \times \sqrt{N}\), κάθε μήνυμα στέλνεται δύο φορές σε κάθε κανάλι, οπότε οι συνολικές λήψεις είναι \(2n(2\sqrt{N}(\sqrt{N}-1) + 2(\sqrt{N}-1)^2)\). Το συνολικό κόστος μετάδοσης και λήψης υπολογίζεται ως:
Κόστος Flooding — τάξη μεγέθους: \(\mathcal{O}(nN)\)
Αυτό το κόστος αυξάνεται γραμμικά με το \(N\) — αν διπλασιάσουμε το μέγεθος του δικτύου, διπλασιάζουμε περίπου και τον ενεργειακό λογαριασμό. Στην πράξη, αυτό σημαίνει ότι το flooding εξαντλεί τις μπαταρίες με ανησυχητικό ρυθμό, επειδή κάθε γεγονός σπρώχνεται σε κάθε γωνιά του δικτύου ανεξάρτητα από το αν κάποιος εκεί ενδιαφέρεται.
Πέρα από τη σπατάλη ενέργειας, υπάρχουν και πρακτικά προβλήματα. Όταν εκατοντάδες κόμβοι προσπαθούν να αναμεταδώσουν ταυτόχρονα, τα ραδιοσήματά τους συγκρούονται στο επίπεδο MAC (Media Access Control), προκαλώντας καθυστερήσεις (delays) και αναγκαστικές επαναμεταδόσεις. Επιπλέον, ακόμα και οι κόμβοι που δεν εκπέμπουν καταναλώνουν ενέργεια κρατώντας τους πομποδέκτες τους ενεργοποιημένους — φαινόμενο γνωστό ως idle listening, που αποδεικνύεται εκπληκτικά δαπανηρό.
Το flooding χρησιμεύει ως αναλυτικό σημείο αναφοράς (baseline): αν ένα νέο πρωτόκολλο δεν μπορεί να νικήσει το flooding, κάτι έχει πάει πολύ στραβά. Κανείς όμως δεν θα το ανέπτυσσε σε πραγματικό δίκτυο αισθητήρων.
1.3 Directed Diffusion: Data-Centric, Demand-Driven¶
Το Directed Diffusion (DD), που παρουσιάστηκε από τους Intanagonwiwat, Govindan και Estrin στο 6ο Διεθνές Συνέδριο Mobile Computing and Networking (2000), ακολουθεί την αντίθετη λογική από το flooding. Αντί να σπρώχνει δεδομένα παντού ελπίζοντας ότι κάποιος τα θέλει, το DD επιτρέπει στον sink να τραβήξει (pull) μόνο τα δεδομένα που πραγματικά χρειάζεται.
Είναι ένα data-centric πρωτόκολλο — ενδιαφέρεται για το τι λένε τα δεδομένα, όχι ποιος τα παρήγαγε. Είναι επίσης application-aware (αναγνωρίζει το είδος των δεδομένων) και energy-efficient (σχεδιασμένο για ενεργειακή αποδοτικότητα).
Σύμφωνα με τις διαφάνειες, τα βασικά στοιχεία (elements) του DD είναι τέσσερα: Interest messages, Data messages, Gradients, και Reinforcements of gradients. Αυτά αντιστοιχούν στις τέσσερις φάσεις λειτουργίας που επαναλαμβάνονται κυκλικά.
Φάση 1 — Διάδοση Ενδιαφέροντος (Interest Propagation)¶
Ο sink κατασκευάζει ένα μήνυμα που περιγράφει το είδος δεδομένων που θέλει, εκφρασμένο ως ζεύγη ιδιότητας-τιμής (attribute-value pairs). Αυτό το μήνυμα ονομάζεται interest. Ένα παράδειγμα από τις διαφάνειες:
type = wheeled vehicle // ανίχνευση τοποθεσίας οχήματος
interval = 100 ms // αποστολή γεγονότων κάθε 100ms
duration = 10 seconds // για τα επόμενα 10 δευτερόλεπτα
rect = [-100, 100, 200, 400] // από κόμβους εντός ορθογωνίου
Ο sink πλημμυρίζει (flood) το interest στο δίκτυο. Ναι, αυτό χρησιμοποιεί flooding — αλλά πρόκειται για εφάπαξ κόστος εγκατάστασης, όχι κόστος ανά γεγονός. Σημαντικό: το interest δεν περιέχει πληροφορία για τον sink — ο sink μαθαίνεται μόνο μέσω των gradients.
Κάθε κόμβος διατηρεί ένα interest cache. Όταν ένα interest φτάσει, αποθηκεύεται τοπικά. Αν ήδη υπάρχει ίδιο interest στο cache, δημιουργείται μόνο ένα νέο gradient. Τα interests σβήνονται μόνο όταν εκπνεύσουν όλα τα σχετιζόμενα gradients.
Φάση 2 — Δημιουργία Κλίσεων (Gradient Setup)¶
Καθώς το interest κυματίζει προς τα έξω από τον sink, κάθε κόμβος που το λαμβάνει δημιουργεί ένα gradient — ένα βέλος που δείχνει πίσω προς τον γείτονα που του παρέδωσε το interest. Κάθε gradient αποθηκεύει δύο πληροφορίες: data rate (ρυθμός δεδομένων) και duration (διάρκεια).
Σκεφτείτε τα gradients σαν βέλη ζωγραφισμένα στο πάτωμα ενός κτιρίου, που δείχνουν όλα προς την έξοδο. Δεν μεταφέρουν δεδομένα — σημαδεύουν την κατεύθυνση που πρέπει να ακολουθήσουν τα δεδομένα όταν εμφανιστούν. Μπορούν να υπάρχουν πολλαπλά gradients σε κάθε κόμβο (ένα για κάθε γείτονα που προώθησε το interest), δημιουργώντας εφεδρικά μονοπάτια.
Φάση 3 — Διάδοση Δεδομένων (Data Propagation)¶
Όταν ένας κόμβος-αισθητήρας ανιχνεύσει ένα γεγονός που ταιριάζει με κάποιο αποθηκευμένο interest, αρχίζει να αισθητηριάζει (sensing). Υπολογίζει τον υψηλότερο ρυθμό αποστολής (data rate) μεταξύ των gradients του και δημιουργεί δείγματα γεγονότων (event samples) σε αυτόν τον ρυθμό.
Ένα data message, σύμφωνα με τις διαφάνειες, μοιάζει κάπως έτσι:
type = wheeled vehicle // τύπος γεγονότος
instance = truck // στιγμιότυπο
location = [125, 220] // τοποθεσία κόμβου
intensity = 0.6 // πλάτος σήματος
confidence = 0.85 // βαθμός εμπιστοσύνης
timestamp = 01:20:40 // τοπικός χρόνος
Τα data messages αποστέλλονται ως unicast στους γείτονες προς τους οποίους δείχνουν τα gradients. Κάθε κόμβος διατηρεί ένα data cache: αν λάβει μήνυμα χωρίς αντίστοιχο interest στο cache ή αν τα δεδομένα ήδη υπάρχουν, το μήνυμα απορρίπτεται. Αλλιώς, αποθηκεύεται και προωθείται.
Φάση 4 — Ενίσχυση (Reinforcement)¶
Αρχικά, ο sink εκπέμπει interests χαμηλού ρυθμού — τα αντίστοιχα gradients ονομάζονται exploratory gradients. Μόλις ο sink αρχίσει να λαμβάνει διερευνητικά δεδομένα, ενισχύει (reinforce) τον γείτονα που του τα παρέδωσε πρώτος, στέλνοντας ξανά το ίδιο interest αλλά με μικρότερο interval (δηλαδή υψηλότερο ρυθμό).
Η επιλογή γείτονα προς ενίσχυση βασίζεται σε τοπικά κριτήρια — για παράδειγμα, ενισχύεται ο γείτονας που ανέφερε πρώτος ένα νέο γεγονός. Τα αντίστοιχα gradients ονομάζονται data gradients (υψηλού ρυθμού). Τα exploratory gradients στα μη-ενισχυμένα μονοπάτια σταδιακά εκπνέουν (timeout) εκτός αν ανανεωθούν.
Αυτό το σχήμα είναι αντιδραστικό (reactive): όποτε ένα μονοπάτι παραδίδει γεγονός ταχύτερα από τα υπόλοιπα, ενισχύεται αυτόματα. Υποστηρίζει επίσης πολλαπλούς sinks και πολλαπλές πηγές ταυτόχρονα.
Τοπική Επισκευή και Αρνητική Ενίσχυση¶
Τα μονοπάτια μπορούν να υποβαθμιστούν με τον χρόνο — κόμβοι εξαντλούν τη μπαταρία τους ή αυξάνονται οι παρεμβολές. Ένας ενδιάμεσος κόμβος μπορεί να ανιχνεύσει αυτή την υποβάθμιση (π.χ. παρατηρώντας μειωμένο ρυθμό γεγονότων) και να εφαρμόσει τοπική επισκευή (local repair) ενισχύοντας έναν εναλλακτικό γείτονα.
Η αρνητική ενίσχυση (negative reinforcement) λειτουργεί στην αντίθετη κατεύθυνση: ένα interest αποστέλλεται ξανά αλλά με χαμηλό ρυθμό (exploratory), σηματοδοτώντας ότι αυτό το μονοπάτι δεν χρειάζεται πλέον υψηλό ρυθμό. Αν όλα τα εξερχόμενα gradients ενός κόμβου γίνουν exploratory, ο κόμβος εφαρμόζει αρνητική ενίσχυση στους γείτονές του.
In-Network Aggregation¶
Η μεγάλη κομψότητα του DD βρίσκεται στη δυνατότητα in-network aggregation: καθώς τα δεδομένα ρέουν κατά μήκος των gradients, οι ενδιάμεσοι κόμβοι μπορούν να συνδυάσουν μετρήσεις από πολλαπλές πηγές. Αν δύο αισθητήρες αναφέρουν πανομοιότυπα δεδομένα, ένας ενδιάμεσος κόμβος μπορεί να καταστείλει το διπλότυπο (duplicate suppression) και να προωθήσει μόνο ένα αντίγραφο. Η προσομοίωση δείχνει ότι χωρίς aggregation, το DD καταναλώνει 3× έως 5× περισσότερη ενέργεια.
Σημείωση Εξεταστικής
Στο Θέμα Α.1 της εξεταστικής 2026, ζητήθηκε συνοπτική περιγραφή της λειτουργίας του DD. Τα κλειδιά: data-centric, τέσσερις φάσεις (interests → gradients → data → reinforcement), in-network aggregation, local repair.
1.4 Omniscient Multicast: Το Θεωρητικό Ανώτατο Όριο¶
Για να αξιολογηθεί σωστά το DD, η αναλυτική σύγκριση (από τις διαφάνειες 23–27) χρησιμοποιεί ένα ιδεατό πρωτόκολλο: Omniscient Multicast. Δεν πρόκειται για πραγματικό πρωτόκολλο — υποθέτει ότι κάθε πηγή γνωρίζει το shortest-path multicast tree προς κάθε sink, και τα δεδομένα ταξιδεύουν χωρίς συγκρούσεις.
Έστω \(T_i\) το δέντρο multicast με ρίζα την πηγή \(i\), και \(C(T_i)\) το κόστος παράδοσης δεδομένων γι' αυτό το δέντρο. Αποδεικνύεται ότι:
Κόστος Omniscient Multicast
Αξιοσημείωτο: το DD, αν και πλήρως κατανεμημένο (κανένας κόμβος δεν γνωρίζει την καθολική τοπολογία), πετυχαίνει κόστος ίδιας τάξης μεγέθους — \(C_d = \mathcal{O}(n\sqrt{N})\). Μάλιστα, χάρη στο in-network aggregation, η προσομοίωση σε ns-2 δείχνει ότι \(C_d < C_o\) σε πραγματικές συνθήκες.
1.5 Αναλυτική Σύγκριση¶
Η σύγκριση βασίζεται σε τετραγωνικό πλέγμα \(\sqrt{N} \times \sqrt{N}\) με \(n\) πηγές και \(m\) sinks. Τα αποτελέσματα προσομοίωσης (ns-2) μετρούν τρεις μετρικές: μέση ενέργεια, μέση καθυστέρηση, και delivery ratio.
| Μετρική | Flooding | Omniscient Multicast | Directed Diffusion |
|---|---|---|---|
| Πολυπλοκότητα κόστους | \(\mathcal{O}(nN)\) | \(\mathcal{O}(n\sqrt{N})\) | \(\mathcal{O}(n\sqrt{N})\) |
| Μηχανισμός | Broadcast σε όλους | Shortest-path multicast tree | Interests, gradients, reinforcement |
| Ενεργειακή απόδοση | Πολύ χαμηλή | Υψηλή | Υψηλότερη (aggregation) |
| Μέση καθυστέρηση | Πολύ υψηλή (collisions) | Χαμηλή | Χαμηλή (συγκρίσιμη) |
| Ανοχή σε σφάλματα | Εγγενώς ανθεκτικό | Ευάλωτο (ένα δέντρο) | Ανθεκτικό (local repair) |
| Aggregation | Καμία | Καμία | Ναι (duplicate suppression) |
1.6 Πλεονεκτήματα και Περιορισμοί του DD¶
Πλεονεκτήματα¶
- Ενεργειακή αποδοτικότητα: Κόστος \(\mathcal{O}(n\sqrt{N})\) — τάξεις μεγέθους κάτω από flooding.
- Ανοχή σε σφάλματα: Η μέση ενέργεια δεν αυξάνεται σημαντικά ακόμα και με αστοχίες κόμβων. Η καθυστέρηση αυξάνεται το πολύ 20% (σύμφωνα με προσομοίωση, διαφ. 34).
- In-network aggregation: Μειώνει 3×–5× την ενέργεια σε σχέση με DD χωρίς aggregation.
- Αρνητική ενίσχυση: Χωρίς αυτή, η ενέργεια διπλασιάζεται (διαφ. 37).
Περιορισμοί¶
- Idle listening: Αν οι πομποδέκτες καταναλώνουν σημαντική ενέργεια σε κατάσταση αναμονής, η απόδοση του DD μειώνεται δραματικά. Η ενέργεια αδράνειας κυριαρχεί σε όλα τα πρωτόκολλα (διαφ. 38).
- MAC layer dependency: Ο σχεδιασμός του MAC επηρεάζει σημαντικά την τελική απόδοση.
1.7 Επίπεδη vs Ιεραρχική Δρομολόγηση¶
Το DD αποτελεί παράδειγμα επίπεδης δρομολόγησης (flat routing) στα καλύτερά της: κανείς κόμβος δεν χρειάζεται ειδικό ρόλο, δεν απαιτείται σχηματισμός συστάδων, και το δίκτυο αυτο-οργανώνεται γύρω από τη ζήτηση δεδομένων.
Η flat δρομολόγηση έχει όμως μια δομική αδυναμία σε πυκνά δίκτυα με υψηλή κυκλοφορία: όλα τα gradients συγκλίνουν προς τον sink, οπότε οι κόμβοι στη γειτονιά του προωθούν την κυκλοφορία όλων και εξαντλούνται πρώτοι. Αυτό δημιουργεί ενεργειακές τρύπες (energy holes).
| Χαρακτηριστικό | Flat Routing (DD) | Hierarchical (LEACH) |
|---|---|---|
| Ρόλοι κόμβων | Ισότιμοι | Cluster Heads vs Members |
| Πολυπλοκότητα | Σχετικά απλή | Πιο περίπλοκη (CH election, TDMA) |
| Κόστος οργάνωσης | Χαμηλό | Υψηλότερο (set-up phase) |
| Επεξεργασία δεδομένων | Aggregation στους ενδιάμεσους κόμβους | Compression από τις κεφαλές συστάδων |
| Ενεργειακές τρύπες | Πιθανές (κοντά στο sink) | Μετριάζονται (rotation) |
Αυτό ακριβώς είναι το πρόβλημα που σχεδιάστηκαν να λύσουν τα ιεραρχικά πρωτόκολλα — κάτι που θα εξετάσουμε στο Κεφάλαιο 2: LEACH.
Σημείωση Εξεταστικής
Στο Θέμα Α.2 της εξεταστικής 2026, ζητήθηκε συγκριτική αξιολόγηση DD vs EBP ως προς την κατανάλωση ενέργειας σε κάθε κόμβο και συνολικά. Το DD είναι energy-efficient αλλά δεν εγγυάται ομοιόμορφη κατανομή ενέργειας (energy balance) — αυτό ακριβώς προσφέρει το EBP.
Πηγές: Lecture 2 (DD & LEACH), Lecture 3 (EBP), χειρόγραφες σημειώσεις σελ. 1–6, Θέματα 2026.