Εξοικονόμηση ενέργειας σε αυτο-οργανούμενα δίκτυα ανεκτικά σε καθυστέρηση

Abstract

This thesis deals with energy-efficiency in wireless self-organizing delay tolerant net-works (DTNs) comprising autonomous, energy-constrained nodes. In particular, the thesis addresses energy consumption under three critical aspects of DTNs; the information overhead diffused in the network, the controlled mobility of DTN nodes and the active sensing they perform. The dynamic DTN nature, resulting from frequent disconnections of inter-nodal links, which is due to either the exhaustion of energy resources or to node sparsity, motivates the autonomous DTN nodes to perform either of the following operations (i) transmit multiple copies of stored information to ensure that the information reaches its destination (ii) move, in order to increase the encounter probability with nodes within their range or (iii) perform active sensing to exploit any chance of establishing communication with neighboring nodes. These operations may be extremely energy consuming if not properly designed. Hence, in the attempt to optimize specific network performance metrics, the relevant schemes should take into account the residual energy resources of DTN nodes. The thesis addresses the issue of information overhead diffusion in DTNs by proposing a scheme based on Network Coding (NC). As opposed to traditional routing/forwarding protocols employed in DTNs that store and forward replicas of received information, the NC technique allows the intermediate nodes to process the received packets and forward a combination of them to the next node on the end-to-end path; when linear NC is employed, the packets are linearly combined before transmission. The thesis applies the random linear NC (RLNC), which is suitable for self-organized networks with autonomous nodes. This is accomplished by multiplying the stored information with linear coefficients randomly selected by the DTN nodes from a sufficiently large finite field. The proposed NC/MMA scheme implements NC both for storing and forwarding the received information to the next node on the end-to-end path. Extensive simulations have shown that the proposed NC/MMA scheme achieves a drastic reduction (i) of the information overhead diffused in the DTN and (ii) of the energy consumption due to transmission, thus extending the network lifetime. In the framework of controlled mobility, the thesis proposes a DTN mobility scheme that regulates the nodes movement based on their residual energy resources and the contact rate characterizing the network. It has been verified in the literature that mobility increases the nodes encountering probability. However, the nodes mobility induces an energy cost due both to the nodes physical movement and to the increased sensing frequency. This energy mobility cost gives rise to the following dilemma; should DTN nodes move in order to increase their encounter probability or should they stay static expecting that other nodes will move? This dilemma along with the respective trade-off between mobility cost and encounter probability are dealt with by the thesis. To formulate the relevant DTN mobility problem, game theory is employed as it can effectively deal with such trade-offs. Extensive simulations have shown that the proposed scheme is capable of properly handling the trade-off between energy consumption and encounter probability, offering a significant reduction in energy consumption compared to standard mobility models, at the cost of a considerably smaller reduction in encounter probability. In wireless self-organizing DTNs amenable to encounter probability reduction, the proposed scheme, being capable of regulating nodes mobility, may offer a significant lifetime extension. The thesis also addresses the subject of active sensing in DTNs. An autonomous scheme is proposed that regulates nodes active sensing, taking into account their residual energy resources. Although contact probing is the only way of establishing communication between neighboring nodes, when not properly designed, it may lead to unnecessary energy consumption or to missed chances of establishing communication between nodes in sparse DTNs. The energy cost induced due to network probing gives rise to the following dilemma; should DTN nodes perform contact probing in order to increase the probability of establishing connection with neighboring nodes or not, expecting that other nodes will perform probing? This dilemma along with the respective trade-off between the energy cost due to probing and the connection probability are dealt with by the thesis employing game theory. Extensive simulations have shown that the proposed scheme handles the trade-off between energy consumption for probing and connection probability, offering a significant reduction in energy consumption, at the same time preserving a minimum acceptable connection probability level. In wireless self-organizing DTNs amenable to connection probability reduction, the proposed scheme, being capable of regulating nodes active sensing, may offer a significant lifetime prolongation. Concluding, the thesis contributes in the area of energy-efficiency in wireless self-organizing delay tolerant networks.

Η διατριβή μελετά την εξοικονόμηση ενέργειας σε αυτο-οργανούμενα δίκτυα ανεκτικά σε καθυστέρηση που αποτελούνται από αυτόνομους και ενεργειακά περιορισμένους κόμβους. Συγκεκριμένα, η διατριβή αντιμετωπίζει την κατανάλωση ενέργειας σε τρεις κρίσιμες από πλευράς ενεργειακής κατανάλωσης λειτουργίες, τη μετάδοση πολλαπλών αντιγράφων πληροφορίας στο δίκτυο, την ελεγχόμενη κινητικότητα των κόμβων του δικτύου και την ενεργητική ανίχνευση δικτύου που αυτοί επιτελούν. Η δυναμική φύση των δικτύων ανεκτικών σε καθυστέρηση, για την οποία οφείλονται οι συχνές αποσυνδέσεις λόγω εξάντλησης των ενεργειακών πόρων ή της αραιής κατανομής των κόμβων στην περιοχή ανάπτυξής τους, επιτάσσει την ανεξάρτητη δράση των ενδιάμεσων κόμβων που έχουν στόχο την παράδοση της πληροφορίας στους κόμβους-προορισμούς. Στο πλαίσιο αυτό, οι αυτόνομοι κόμβοι παρακινούνται άλλοτε στη μετάδοση πολλαπλών αντιγράφων της αποθηκευμένης πληροφορίας τους προκειμένου να εξασφαλίσουν ότι αυτή θα φθάσει στον προορισμό της, άλλοτε στην αυτο-κίνηση (κίνηση που καθορίζεται από τον ίδιο κόμβο), ώστε να αυξηθεί η πιθανότητα συνάντησης κόμβων εντός εμβέλειας, και άλλοτε στην εκπομπή συχνών σημάτων ανίχνευσης δικτύου προκειμένου να αξιοποιήσουν όποια ευκαιρία σύναψης επικοινωνίας με κόμβο εντός εμβέλειας προκύψει. Και οι τρεις αυτές διαδικασίες μπορούν να αποβούν εξαιρετικά ενεργοβόρες αν τα σχήματα που προτιμώνται για την αντιμετώπιση των αντίστοιχων επιπτώσεων δεν σχεδιαστούν κατάλληλα, κατά κύριο λόγο λαμβάνοντας υπόψη τα ενεργειακά αποθέματα των κόμβων με στόχο την εξισορρόπησή τους με το εκάστοτε προς βελτιστοποίηση μέγεθος. Η διατριβή αντιμετωπίζει το θέμα της διάχυσης πολλαπλών αντιγράφων πληροφορίας στο δίκτυο αναπτύσσοντας ένα σχήμα που βασίζεται στην τεχνική της κωδικοποίησης δικτύου. Σε αντίθεση με τα παραδοσιακά πρωτόκολλα δρομολόγησης/προώθησης που προωθούν ή αντιγράφουν την αποθηκευμένη πληροφορία, η τεχνική κωδικοποίησης δικτύου επεξεργάζεται την πληροφορία των κόμβων, συνδυάζοντας κατάλληλα τα αποθηκευμένα πακέτα και προωθώντας, τελικά, κατάλληλο συνδυασμό αυτών στον κόμβο με τον οποίο έχει συναφθεί επικοινωνία. Η διατριβή εφαρμόζει την τεχνική της γραμμικής κωδικοποίησης δικτύου, που είναι κατάλληλη για αυτο-οργανούμενα δίκτυα με αυτόνομους κόμβους, καθώς ο γραμμικός συνδυασμός των αποθηκευμένων πακέτων προκύπτει από πολλαπλασιασμό αυτών με γραμμικές συνιστώσες που οι κόμβοι επιλέγουν τυχαία από ένα αρκούντως μεγάλο πεπερασμένο πεδίο. Το προτεινόμενο NC/MMA σχήμα βασίζεται τόσο στην τεχνική κωδικοποίησης δικτύου για την προώθηση της πληροφορίας όσο και στην κατάλληλη αποθήκευση αυτής στους περιορισμένους αποθηκευτικούς πόρους των κόμβων. Τα αριθμητικά αποτελέσματα των προσομοιώσεων που πραγματοποιήθηκαν αποδεικνύουν ότι το NC/MMA σχήμα επιτυγχάνει δραστική μείωση της πλεονάζουσας πληροφορίας που διακινείται στο δίκτυο και, κατ’ επέκταση, μείωση της κατανάλωσης ενέργειας λόγω μετάδοσης μηνυμάτων, επεκτείνοντας τη διάρκεια ζωής του δικτύου. Παράλληλα, διατηρείται η πιθανότητα και η καθυστέρηση παράδοσης της πληροφορίας ενώ σε ορισμένες προσομοιώσεις παρατηρείται ακόμη και βελτίωση αυτών. Στο πλαίσιο της ελεγχόμενης κινητικότητας, η διατριβή αξιοποιεί την κίνηση των κόμβων αναπτύσσοντας ένα σχήμα που παρακινεί τους κόμβους σε αυτο-κίνηση, λαμβάνοντας υπόψη τους εναπομένοντες ενεργειακούς τους πόρους και το ρυθμό επαφών στο δίκτυο. Έχει αποδειχθεί επανειλημμένα στη σχετική βιβλιογραφία ότι η κινητικότητα των κόμβων, εκτός από τις προκλήσεις που δημιουργεί σχετικά με τη δυναμική τοπολογία του δικτύου, αυξάνει την πιθανότητα συνάντησης των κόμβων. Ωστόσο, η κινητικότητα των κόμβων σχετίζεται και με αυξημένη κατανάλωση ενέργειας λόγω της φυσικής κίνησης των κόμβων και της αυξημένης συχνότητας με την οποία αυτοί ανιχνεύουν/σαρώνουν το δίκτυο ενόσω βρίσκονται σε κίνηση. Το προτεινόμενο σχήμα καλείται να αντιμετωπίσει το εξής δίλημμα των κόμβων: να κινηθούν με στόχο την αύξηση της πιθανότητας εύρεσης κόμβου εντός εμβέλειας ή να μείνουν ακίνητοι προσδοκώντας ότι κάποιος άλλος κόμβος του δικτύου θα κινηθεί. Το δίλημμα αυτό σε συνδυασμό με την αντίστοιχη σχέση ανταλλαγής μεταξύ του κόστους κίνησης και της πιθανότητας συνάντησης κόμβων του δικτύου αντιμετωπίζονται στη δια-τριβή. Η μαθηματική διατύπωση του σχετικού προβλήματος διαχείρισης της κινητικότητας κόμβων που ανήκουν σε δίκτυα ανεκτικά σε καθυστέρηση πραγματοποιείται με χρήση της θεωρίας παιγνίων που αποτελεί το κατεξοχήν εργαλείο μαθηματικής διατύπωσης σχέσεων ανταλλαγής. Τα αριθμητικά αποτελέσματα φανερώνουν ότι το προτεινόμενο σχήμα προσφέρει σημαντική μείωση στην κατανάλωση ενέργειας σε σύγκριση με τη σχετικά μικρότερη μείωση στην πιθανότητα συνάντησης. Σε αυτο-οργανούμενα δίκτυα ανεκτικά σε μείωση της πιθανότητας συνάντησης, το προτεινόμενο σχήμα μπορεί να προσφέρει σημαντική επέκταση της διάρκειας ζωής. Στο πλαίσιο της ενεργητικής ανίχνευσης του δικτύου, η διατριβή προτείνει ένα αυτόνομο σχήμα που παρακινεί τους κόμβους σε εκπομπή σημάτων ανίχνευσης δικτύου λαμβάνοντας υπόψη τους εναπομένοντες ενεργειακούς τους πόρους και το ρυθμό επαφών στο δίκτυο. Ενώ η ανίχνευση δικτύου σε αραιά δίκτυα ανεκτικά σε καθυστέρηση αποτελεί το μόνο τρόπο σύναψης επικοινωνίας με κόμβους που βρίσκονται εντός εμβέλειας, λανθασμένη σχεδίαση της διαδικασίας αυτής ενδέχεται να οδηγήσει σε άσκοπη κατανάλωση ενέργειας ή σε απώλεια ευκαιριών σύναψης επικοινωνίας με κόμβους εντός εμβέλειας. Δεδομένου του ενεργειακού κόστους εκπομπής σήματος ανίχνευσης, το προτεινόμενο σχήμα καλείται να αντιμετωπίσει το εξής δίλημμα των κόμβων: να εκπέμψουν σήμα ανίχνευσης με στόχο τον εντοπισμό κόμβου εντός εμβέλειας ή να μην εκπέμψουν, προσδοκώντας ότι κάποιος άλλος κόμβος του δικτύου θα το πράξει. Το δίλημμα αυτό σε συνδυασμό με την αντίστοιχη σχέση ανταλλαγής μεταξύ του κόστους ανίχνευσης και της πιθανότητας επικοινωνίας μεταξύ δύο κόμβων του δικτύου αντιμετωπίζονται στη διατριβή με εφαρμογή της θεωρίας παιγνίων. Τα αριθμητικά αποτελέσματα δείχνουν ότι το προτεινόμενο σχήμα επιτυγχάνει σημαντική μείωση της μέσης κατανάλωσης ενέργειας για την ανίχνευση του δικτύου, διατηρώντας, παράλληλα, ένα ελάχιστο αποδεκτό επίπεδο της πιθανότητας επικοινωνίας. Σε αυτο-οργανούμενα δίκτυα που επιδέχονται μείωση της πιθανότητας επικοινωνίας, το προτεινόμενο σχήμα μπορεί να επεκτείνει σημαντικά τη διάρκεια ζωής. Συνοψίζοντας, η διατριβή συμβάλλει ερευνητικά στην αντιμετώπιση της εξοικονόμησης ενέργειας στα ενεργειακά περιορισμένα δίκτυα ανεκτικά σε καθυστέρηση.