Προσαρμοστική επιδημική διάδοση σε ασύρματα αδόμητα δίκτυα

Abstract

The focus of this research is epidemic information dissemination in wireless ad hocnetworks in an adaptive manner. The main targets are the compromise betweendemands for broad information dissemination and reduced energy cost, the assessmentof an optimal solution to the problem and also the achievement of optimal performancein the aforementioned areas with high quality inforamation.Adaptive epidemic dissemination (AED) in ad hoc networks in a noisy environment isa problem with many parameters.Using cross-layering based on channel state-awareness, one can engineer adaptivedissemination sche- mes, which save energy while retaining a fast and effective infection([1] ).This type of scheme [1] is reactive, but a flavor of proactive scheme can be devisedthat uses utility functions in order to adapt transmission characteristics. The proposedsolution is a proof of concept of this idea. With this approach energy cost is savedwhile infection remains successful [2].The above scheme can be enhanced through the use of optimization. Assessingwhich adaptation is most beneficial at every round as in [2], a ”myopic” visibility tothe future is at least achieved. Using optimal stopping theory (OST) one may obtainlonger visibility and approach optimal solutions. The actual optimality depends onsatisfaction of optimal stopping conditions. If these are not fully satisfied, then theobtained solutions are not necessarily optimal. This is displayed in [3] through theuse of the one-stage-look-ahead, (1sla) optimal stopping rule. Improvement over non-adaptive schemes in terms of energy cost save is possible. Broad network infection isstill as effective [3].Optimization is investigated in the periodic broadcast problem, which is addressed witha transition to a near-periodic framework where scheduling is performed using the sametoolcase, that is cross-layer utility functions and an optimal stopping mechanism. Thisproblem is modeled as a secretary problem where the use of OST offers optimality.Compared against non-OST [2] and non-adaptive schemes this scheme wins in theenergy cost save area and allows for successful network infection. The energy costof channel state information (CSI) retrieval may also be considered. In this case, thesystem converges to a state where dissemination cost is dramatically reduced whilea large proportion of the residual, steady-state energy cost is due to CSI acquisition.Exact relations depend on parameters of the problem [4].Furthermore, the possibility to improve information quality is investigated using schemessuch as the one in [4]. Information freshness is originally considered as the measureof quality. Adaptation of transmission characteristics based on information freshnessis suggested aiming to improve the average age of the infecting information. In thismanner, the idea of adapting transmission characteristics based on the actual payloadof the infecting information is introduced.Tuning broadcasts down to a polite gossip during the route discovery phase in routingprotocols is an additional attractive area. This problem is addressed within the frameworkof the AODV protocol. The tradeoff between energy cost save and fast routing informationdiscovery emerges here. In an effort to expand the technique to the actual routed datatransmission (i.e. the user data), we move from broadcasting to a unicast landscape.Here, the tuning down of transmissions may have significant impact on informationpropagation. It is shown that the problem is best addressed using metrics reflecting aconceived quality of service and by extension quality of information.The time scheduling problem enhanced by the additional information quality requirementcan be formally expressed as an optimal stopping problem with known finite horizon.The quality of the information may be defined based on its properties (such as freshnessas mentioned earlier) or parameters of the protocol concerned with the dissemination,such as TTL in case of AODV.In this manner, information quality emerges as a third component besides energy costand network infection, which participates the addressed tradeoff. Depending on thedefined information quality seeking a compromise between these three requirementsis possible.

Το αντικείμενο της έρευνας αυτής είναι η επιδημική διάδοση (epidemic dissemination)πληροφορίας σε ασύρματα αδόμητα (ad hoc) δίκτυα με προσαρμοστικό τρόπο. Στό-χοι είναι η συμφιλίωση των απαιτήσεων για ευρεία διάδοση της πληροφορίας και γιαμειωμένο ενεργειακό κόστος, η εκτίμηση μιας βέλτιστης λύσης του προβλήματος αλ-λά και η επίτευξη της βέλτιστης απόδοσης στους εν λόγω τομείς με υψηλής ποιότηταςπληροφορία.Η προσαρμοστική επιδημική διάδοση (Π.Ε.Δ.) σε αδόμητα δίκτυα σε θορυβώδες περι-βάλλον είναι πρόβλημα με πολλές παραμέτρους.Με τη χρήση της διαστρωμάτωσης (cross-layering) με βάση την επίγνωση κατάστασηςκαναλιού μπορούν να κατασκευαστούν σχήματα προσαρμοστικής διάδοσης, τα οποίαεξοικονομούν ενέργεια διατηρώντας ταχεία και αποτελεσματική διάχυση πληροφορίαςή μόλυνση του δικτύου, σύμφωνα με την ορολογία της επιδημικής διάδοσης [1].Αυτού του είδους η αντιμετώπιση [1] είναι αναδραστική. Μπορεί όμως να σχεδιαστείμια εκδοχή σχημάτων με πρόβλεψη η οποία χρησιμοποιεί συναρτήσεις οφέλους για τηνπροσαρμογή των χαρακτηριστικών εκπομπής. Η προτεινόμενη λύση είναι μια απόδει-ξη της αρχής λειτουργίας (proof of concept, PoC) αυτής της ιδέας. Με την αντιμετώπισηαυτή εξοικονομείται ενέργεια ενώ και η διάχυση πληροφορίας είναι επιτυχής [2].Το πιο πάνω σχήμα μπορεί να ενισχυθεί με τη χρήση βελτιστοποίησης. Ελέγχονταςποια προσαρμογή είναι η πλέον σύμφορη σε κάθε χρονική στιγμή όπως στο [2], επι-τυγχάνεται μια έστω και «μυωπική» ορατότητα στο άμεσο μέλλον. Με τη χρήση τηςθεωρίας βέλτιστης παύσης (β.π.) μπορεί να αποκτηθεί καλύτερη ορατότητα σε βάθοςχρόνου και να προσεγγιστεί η βελτιστοποίηση. Η πραγματική βελτιστοποίηση εξαρτά-ται από την ικανοποίηση συνθηκών β.π. Αν αυτές δεν ικανοποιούνται πλήρως, τότεκαι οι αποκτώμενες λύσεις δεν είναι κατ’ ανάγκη βέλτιστες. Αυτό φαίνεται στην [3] μετη χρήση του κανόνα β.π. (one-stage-look-ahead, 1sla). Μπορεί να επιτευχθεί βελτί-ωση σε σχέση με μη προσαρμοστικές λύσεις ως προς την εξοικονόμηση ενέργειας. Ηευρεία μόλυνση του δικτύου εξακολουθεί να επιτυγχάνεται [3].Εξετάζεται στη συνέχεια ως πρόβλημα Π.Ε.Δ. ο χρονοπρογραμματισμός τακτικών εκ-πομπών. Η βελτιστοποίηση προσεγγίζεται με τη μετάβαση από αυστηρά περιοδικέςεκπομπές σε πλησιοπεριοδικό καθεστώς. Ο χρονοπρογραμματισμός πραγματοποιεί-ται με τη βοήθεια των ιδίων εργαλείων, δηλαδή διαστρωματικές συναρτήσεις οφέλουςκαι χρήση μηχανισμού β.π. Το πρόβλημα αυτό μοντελοποιείται ως κλασικό πρόβλημαγραμματέως, στο οποίο η χρήση β.π. προσφέρει βελτιστοποίηση. Σε σχέση με σχή-ματα χωρίς β.π. [2] και με μη προσαρμοστικά το σχήμα αυτό είναι αποδοτικότερο στηνεξοικονόμηση ενέργειας και επιτρέπει εξ ίσου επιτυχημένη μόλυνση του δικτύου. Είναιδυνατόν να συνυπολογιστεί και το ενεργειακό κόστος απόκτησης πληροφορίας κατά-στασης καναλιού (ΠΚΚ). Με τη βοήθεια αυτού του σχήματος, το δίκτυο συγκλίνει σεκατάσταση στην οποία το κόστος διάχυσης είναι σημαντικά ελαττωμένο ενώ σημαντικόποσοστό του εναπομένοντος κόστους οφείλεται στην ανάκτηση ΠΚΚ ([4]). Οι ακριβείςσυσχετισμοί εξαρτώνται από τις παραμέτρους του προβλήματος [4].Περαιτέρω θίγεται η δυνατότητα βελτίωσης της ποιότητας πληροφορίας με την αξιο-ποίηση σχημάτων σαν αυτό της [4]. Αρχικά θεωρείται ως ποιότητα η νεότητα της δια-χεόμενης πληροφορίας. Προτείνεται προσαρμογή των χαρακτηριστικών εκπομπής μεβάση τη νεότητα της μολύνουσας πληροφορίας με στόχο τη βελτίωση της μέσης ηλικί-ας της μολύνουσας τους κόμβους πληροφορίας. Με τον τρόπο αυτό εισάγεται η ιδέατης προσαρμογής των χαρακτηριστικών εκπομπής με βάση το περιεχόμενο της ίδιαςτης φερόμενης πληροφορίας.Ο μετριασμός των ευρυεκπομπών κατά τη φάση ανακάλυψης μονοπατιού στα πρω-τόκολλα δρομολόγησης είναι ένας ακόμη ελκυστικός στόχος και αντιμετωπίζεται σταπλαίσια του πρωτοκόλλου AODV. Εδώ αναδεικνύεται ο ανταγωνισμός μεταξύ εξοικο-νόμησης ενεργειακού κόστους και ταχείας εύρεσης πληροφορίας δρομολόγησης. Σεμια απόπειρα επέκτασης της τεχνικής στην εκπομπή της ίδιας της δρομολογούμενηςπληροφορίας (των δεδομένων δηλαδή), μεταπίπτουμε σε περιβάλλον μονοεκπομπών(unicast). Εδώ, ο μετριασμός εκπομπών μπορεί να έχει σοβαρές συνέπειες στη μετά-δοση πληροφορίας και καταδεικνύεται η ανάγκη εξέτασης του προβλήματος με τη βο-ήθεια μετρικών που εκφράζουν την έννοια της ποιότητας υπηρεσίας (quality of service,QoS) και κατ’ επέκταση της ποιότητας της πληροφορίας.Το εξεταζόμενο πρόβλημα χρονοπρογραμματισμού με την πρόσθετη νέα απαίτησηςτης βελτίωσης της ποιότητας πληροφορίας μπορεί να διατυπωθεί αυστηρά ως πρό-βλημα βέλτιστης παύσης με πεπερασμένο γνωστό ορίζοντα.Η ποιότητα πληροφορίας μπορεί να ορίζεται με βάση ιδιότητές της (όπως η νεότηταπου αναφέρθηκε) ή παραμέτρους του πρωτοκόλλου στα πλαίσια του οποίου γίνεται ηδιάχυσή της, όπως το TTL (time-to-live) στην περίπτωση του AODV.Έτσι η ποιότητα πληροφορίας αναδεικνύεται σε μια τρίτη συνιστώσα πέρα από το ε-νεργειακό κόστος και το ποσοστό μόλυνσης, η οποία λαμβάνει μέρος στον υπό εξέτασηαναδυόμενο ανταγωνισμό. Ανάλογα με την οριζόμενη ποιότητα πληροφορίας είναι δυ-νατή η εύρεση συμβιβασμού μεταξύ των τριών αυτών απαιτήσεων.