Μέθοδοι μετάδοσης πληροφορίας με εξοικονόμηση ενέργειας σε ασύρματα μη δομημένα τηλεπικοινωνιακά δίκτυα

Abstract

In this dissertation the routing problem with energy conservation in wireless ad hoc networks is studied. Due to the importance of the problem, there is a large amount of recent papers in the literature addressing the issue of energy-aware routing across multiple hops with different transmission energy requirements. The objective of this doctoral thesis is to propose and study new criteria for the efficient management of the available energy resources, provide the appropriate routing algorithms, analyze their performance and complexity, and compare them with existing algorithms. The study is composed of three parts. The first part of the dissertation addresses the problem of broadcasting (and multicasting) in wireless multi-hop networks, so that the power consumed by any node in the network individually is as small as possible. The problem is formulated as a lexicographic node power optimization one. According to this optimization criterion, provided that the kth maximum consumed node power is minimized, the (k+1)th maximum power is minimized next. The problem is in general NP-complete. An optimal polynomial time algorithm is provided first for a special case of the problem. Next, this algorithm is extended to provide an optimal solution for the general case. The derived algorithm runs in reasonable time for moderate size random networks, where it can be employed to test the efficiency of proposed heuristics. However, as expected, its worst case running time is exponential in the size of the network. To deal with networks of larger sizes, a heuristic is developed that is based on the steps of the optimal algorithm and avoids the most computing intensive operations. Numerical results show that the proposed heuristic has good running times and provides fairly satisfactory performance relative to the optimal algorithm. Hence, it presents a good compromise between running time and achieved performance. The algorithms developed in this part can also be used to solve many other interesting problems. A useful application for example is to implement broadcasting so that the residual energy of any node in the network after the broadcast process is as large as possible (lexicographic maximization of residual node energies). In the second part the minimum-energy broadcast problem in wireless multi-hop networks is examined. This criterion minimizes the sum of consumed node powers during a broadcast process. Although this problem has been studied extensively in the literature, most of previous approaches provide a solution for it which depends on the source node that initiates the broadcast request. That is, every time a node needs to broadcast some information to all other nodes in the network, the algorithm is executed for the specific source node. Hence, in general, each node in the network has to keep track of a large number of different broadcast trees (the number is equal to the size of the network in the worst case). This requires large memory space and processing capabilities on behalf of the nodes, a demand that cannot always be met. To overcome this restriction, a polynomial time approximation algorithm is presented, so that all broadcast requests initiated by different source nodes take place on the same broadcast tree. This approach simplifies considerably the tree maintenance problem and allows scaling to larger networks. The performance analysis indicates that the approximation ratio provided by the algorithm is close to the best achievable bound in polynomial time. Moreover, it is better than any other existing approximation factor. Numerical results show that there are some interesting instances of general networks for which the proposed algorithm outperforms significantly other algorithms. In general, it presents a good compromise between simplicity and achieved performance. The third part addresses the issue of maximizing the lifetime in a wireless sensor network with energy and power constrained sensor nodes and mobile data collection point (sink). Information generated by the monitoring sensors needs to be routed efficiently to the location where the sink is currently located. The capability of the sink to be located in different places during network operation is exploited in order to maximize network lifetime. A novel linear programming formulation of the problem is provided. It is shown that maximum lifetime can be achieved by solving optimally two joint problems: 1) a scheduling problem that determines the sojourn times of the sink at different locations, and 2) a routing problem in order to deliver the sensed data to the sink in an energy-efficient way. The proposed model provides the optimal solution to both of these problems and gives the best achievable network lifetime. It also results in a fair balancing of the energy depletion among the sensor nodes. The implementation of the model implies the need of a central controller where the solution to the linear programming problem will be computed. An interesting issue for further study is to propose new heuristic on-line algorithms to be used in an adaptive and distributed environment, where the sink sojourn times are not determined a priori. In any case, the proposed model, providing the optimal solution, can be used as a yardstick against which one can compare the performance of other heuristics that might be proposed in the future. The formulation can also be used as a starting point on which new algorithms can be implemented.

Στην παρούσα μελέτη εξετάζεται το πρόβλημα της μετάδοσης της πληροφορίας σε ασύρματα μη δομημένα δίκτυα πολλαπλών αλμάτων με αποδοτική διαχείριση των διαθέσιμων ενεργειακών πόρων. Στη διεθνή βιβλιογραφία έχουν προταθεί αρκετοί αλγόριθμοι δρομολόγησης που λαμβάνουν υπ' όψη την κατανάλωση ενέργειας από τους κόμβους του δικτύου. Σκοπός της διδακτορικής διατριβής είναι η πρόταση νέων κριτηρίων αποδοτικής διαχείρισης της διαθέσιμης ενέργειας, η ανάπτυξη των κατάλληλων αλγόριθμων δρομολόγησης της πληροφορίας, η θεωρητική ανάλυση και μελέτη της απόδοσης και της πολυπλοκότητάς τους, και η σύγκρισή τους με υπάρχοντες αλγόριθμους. Η εργασία χωρίζεται σε τρία μέρη. Στο πρώτο μέρος τίθεται το πρόβλημα της δρομολόγησης από έναν κόμβο προς όλους τους υπόλοιπους κόμβους του δικτύου (ή ένα υποσύνολό τους), με βασικό κριτήριο η ενέργεια που καταναλώνεται σε κάθε κόμβο ξεχωριστά να είναι όσο το δυνατό μικρότερη. Το πρόβλημα διατυπώνεται ως πρόβλημα ελαχιστοποίησης των καταναλισκόμενων ενεργειών κατά λεξικογραφικό τρόπο. Σύμφωνα με αυτό το κριτήριο, με δεδομένη την ελαχιστοποίηση της k-οστής μέγιστης ενέργειας, επιτυγχάνεται στη συνέχεια η ελαχιστοποίηση και της (k + 1)-οστής μέγιστης ενέργειας. Αποδεικνύεται ότι το πρόβλημα είναι NP-complete. Για το λόγο αυτό, αρχικά εξετάζεται μία ειδική περίπτωση για την οποία προτείνεται ένας αλγόριθμος που λύνει το πρόβλημα με το βέλτιστο τρόπο και έχει πολυωνυμικό χρόνο εκτέλεσης. Στη συνέχεια εξετάζεται το πρόβλημα στη γενική του μορφή. Παρουσιάζεται ένας βέλτιστος αλγόριθμος ο οποίος εκτελείται σε ικανοποιητικό χρόνο για τυχαία δίκτυα μεσαίου μεγέθους. Όμως, ο χρόνος εκτέλεσης του αλγόριθμου στη χειρότερη περίπτωση εξακολουθεί να παραμένει εκθετικός σε σχέση με το μέγεθος του δικτύου. Για δίκτυα μεγαλύτερου μεγέθους προτείνεται ένας αλγόριθμος ευρετικής μεθόδου που βασίζεται στα βήματα του βέλτιστου αλγόριθμου και στοχεύει στη μεθοδικότερη αναζήτηση λύσης προκειμένου να αποφευχθούν ανώφελοι εξαντλητικοί υπολογισμοί. Ο προτεινόμενος αλγόριθμος ευρετικής μεθόδου συμβιβάζει με ικανοποιητικό τρόπο το χρόνο που απαιτείται για την εκτέλεσή του σε σχέση με τα αποτελέσματα που δίνει συγκρινόμενος με τη βέλτιστη λύση. Όλοι οι αλγόριθμοι μπορούν να χρησιμοποιηθούν σε εφαρμογές όπως η μεγιστοποίηση των ενεργειών που απομένουν στους κόμβους μετά το πέρας της διαδικασίας δρομολόγησης κατά λεξικογραφικό τρόπο. Στο δεύτερο μέρος της διατριβής εξετάζεται το κριτήριο της ελαχιστοποίησης του αθροίσματος των ενεργειών που καταναλώνονται κατά τη δρομολόγηση από έναν κόμβο προς όλους τους υπόλοιπους κόμβους του δικτύου. Στις μελέτες που έχουν γίνει προτείνονται συνήθως αλγόριθμοι οι οποίοι εξαρτώνται από την πηγή των πακέτων. Έτσι, κάθε φορά εκτελείται ο αλγόριθμος με βάση το συγκεκριμένο αποστολέα. Αυτό όμως συνεπάγεται ότι κάθε κόμβος θα πρέπει να έχει αποθηκευμένη πληροφορία και να την επεξεργάζεται αναλόγως, σχετικά με τους επόμενους κόμβους στους οποίους πρέπει να κάνει αναμετάδοση, ανάλογη με το μέγεθος του δικτύου στη χειρότερη περίπτωση. Απαιτούνται έτσι μεγάλες δυνατότητες αποθήκευσης στη μνήμη και επεξεργασίας δεδομένων, μία απαίτηση η οποία δεν μπορεί να ικανοποιείται πάντα. Για το λόγο αυτό, προτείνεται ένας προσεγγιστικός αλγόριθμος πολυωνυμικού χρόνου ο οποίος χρησιμοποιεί τις ίδιες ζεύξεις ανεξάρτητα από την πηγή των πακέτων. Απλοποιείται έτσι η διαδικασία δρομολόγησης και γίνεται ευκολότερη η εφαρμογή του σε μεγαλύτερα δίκτυα. Από τη θεωρητική ανάλυση αποδεικνύεται ότι η προσεγγιστική λύση που δίνει ο αλγόριθμος είναι πολύ κοντά στην καλύτερη θεωρητική λύση που μπορεί να επιτευχθεί σε πολυωνυμικό χρόνο. Επιπρόσθετα, η προσέγγιση που επιτυγχάνεται είναι καλύτερη από τις μέχρι τώρα γνωστές που υπάρχουν στη βιβλιογραφία. Τα αριθμητικά αποτελέσματα επιβεβαιώνουν το γεγονός ότι ο προτεινόμενος αλγόριθμος επιτυγχάνει μία καλή ισορροπία μεταξύ της απλοποίησης της διαδικασίας δρομολόγησης και της απόδοσης που παρουσιάζει. Στο τρίτο μέρος εξετάζεται το πρόβλημα της μεγιστοποίησης της διάρκειας ζωής ενός δικτύου αισθητήρων. Οι πληροφορίες που συλλέγονται από τους αισθητήρες δρομολογούνται προς έναν κόμβο-συλλέκτη που μετακινείται σε διαφορετικές θέσεις στο δίκτυο. Έτσι, δεν επιβαρύνονται με κατανάλωση μεγαλύτερων ποσών ενέργειας συνεχώς οι ίδιοι αισθητήρες. Το πρόβλημα διατυπώνεται ως πρόβλημα γραμμικού προγραμματισμού και καταδεικνύεται ότι το ζητούμενο κριτήριο μπορεί να επιτευχθεί αν αντιμετωπιστούν με βέλτιστο τρόπο δύο αλληλένδετα θέματα: 1) το θέμα καθορισμού του χρόνου παραμονής του κόμβου-συλλέκτη στις διάφορες θέσεις, και 2) το θέμα της δρομολόγησης των πακέτων κατά έναν ενεργειακά αποδοτικό τρόπο. Το προτεινόμενο μοντέλο παρέχει τη βέλτιστη λύση και στα δύο θέματα και εξασφαλίζει τη μεγαλύτερη διάρκεια ζωής που μπορεί να επιτευχθεί. Επίσης, εγγυάται μία πιο δίκαιη και ισορροπημένη κατανάλωση ενεργειών από τους αισθητήρες. Η υλοποίησή του προϋποθέτει την ύπαρξη ενός κόμβου που θα αναλαμβάνει κεντρικό ρόλο ελέγχου. Ένα ενδιαφέρον θέμα για περαιτέρω μελέτη είναι η υλοποίηση του μοντέλου σε κατανεμημένο περιβάλλον, αλλά και η ανάπτυξη νέων αλγόριθμων ευρετικής μεθόδου. Σε κάθε περίπτωση, το προτεινόμενο μοντέλο, παρέχοντας τη βέλτιστη λύση, μπορεί να χρησιμοποιηθεί ως μέτρο σύγκρισης για μελλοντικούς αλγόριθμους.