Σχεδιασμός ασύρματων δικτύων με δυνατότητα παροχής προηγμένων υπηρεσιών

Abstract

In this dissertation, three optimization problems in the context of wireless ad-hoc networks are solved. Specifically, a dual-hop system with non-regenerative relay under arbitrary fading is examined, where the relay is subject to instantaneous as well as average output power constraints. The problem posed is how to select the relay gain, as a function of channel state, in order to maximize a suitably defined receiver utility function, which contains, as special cases, the Shannon rate, outage probability and complementary symbol error probability of typical modulation schemes. The analysis, using tools from convex analysis and combinatorial optimization, is mostly theoretical and is easily extended to dual-branch diversity systems, of either selection (SC) or maximal ratio combining (MRC) type. The next two problems are related to battery-operated sensor networks. In the first scenario, the node batteries are non-rechargeable and the nodes need to send the generated information to a mobile sink, which is allowed to move among a set of specified locations. All links are assumed to be deterministic and a fluid model is used for the packet traffic. The question is what is the sink’s sojourn time at each allowable location and what is the corresponding routed flow so that the network “lifetime” is maximized. The latter term, which has numerous definitions in the literature, is defined in this dissertation as the time up to the (earliest) battery depletion of any node. Imposing energy and power constraints to all nodes (except for the sink), a linear program is formulated. Using analytical techniques, its dual problem is solved via an iterative subgradient projection procedure, at each step of which minimum cost flow problems must be solved, and an algorithm that is amenable to distributed implementation (a major objective in ad-hoc networks) is proposed. Finally, the scenario of rechargeable batteries is also examined, where the network lifetime is sufficiently large (in the order of many years) so that it can be approximately regarded as infinite. This shifts the design focus towards optimal network performance. The latter is quantified through a utility function of the long-term rates of the bits admitted into the network. Also, due to the infinite lifetime, stability of network queues is a crucial issue that must be addressed. Using stochastic models for the arrival, channel state and battery recharge processes, an online policy that stabilizes the network, with a guaranteed achieved performance lower bound, is proposed. The policy requires knowledge of current values only and is asymptotically optimal as, where is the maximal battery capacity and is the maximal allowable transmission power per slot. Simulations are performed for the above three problems and the obtained results demonstrate the feasibility of the proposed methods and algorithms.

Η παρούσα διδακτορική διατριβή εξετάζει και επιλύει τρία προβλήματα βελτιστοποίησης σε ασύρματα μη-δομημένα δίκτυα. Συγκεκριμένα, εξετάζεται ένα σύστημα διπλού άλματος με έναν μη-αναγεννητικό αναμεταδότη ο οποίος υπόκειται σε περιορισμούς στιγμιαίας και μέσης ισχύος σε ένα περιβάλλον αυθαίρετων διαλείψεων. Το πρόβλημα που τίθεται είναι η βέλτιστη ρύθμιση του κέρδους του αναμεταδότη, συναρτήσει των καταστάσεων των καναλιών, ώστε να μεγιστοποιείται η συνολική ωφέλεια στον δέκτη, ειδικές περιπτώσεις της οποίας είναι ο ρυθμός Shannon, η συμπληρωματική πιθανότητα σφάλματος των περισσότερων σχημάτων διαμόρφωσης και η πιθανότητα διακοπής. Η ανάλυση είναι κυρίως θεωρητική, κάνοντας χρήση τεχνικών από κυρτή ανάλυση και συνδυαστική βελτιστοποίηση, και επεκτείνεται εύκολα σε συστήματα διαφορισμού επιλογής (SC) ή μέγιστου λόγου (MRC) διπλού κλάδου. Τα δύο επόμενα προβλήματα αφορούν ασύρματα δίκτυα αισθητήρων, στα οποία οι κόμβοι τροφοδοτούνται από μπαταρίες. Αρχικά, θεωρείται ότι οι μπαταρίες είναι μη-επαναφορτιζόμενες ενώ η πληροφορία που παράγεται στους κόμβους πρέπει να συγκεντρωθεί σε έναν κόμβο-συλλέκτη, ο οποίος μπορεί να κινείται σε ένα σύνολο επιτρεπτών θέσεων. Επίδης, τα κανάλια μεταξύ των κόμβων θεωρούνται ότι είναι ντετερμινιστικά. Χρησιμοποιώντας ένα μοντέλο ροής (fluid model) για την κίνηση των πακέτων, το πρόβλημα που μελετάται είναι η εύρεση της κατάλληλης ακολουθίας παραμονής του συλλέκτη σε κάθε θέση και η αντίστοιχη ροή που του δρομολογείται ώστε να μεγιστοποιείται ο ‘χρόνος ζωής του δικτύου’. Ο τελευταίος όρος, ο οποίος δέχεται πολλούς διαφορετικούς ορισμούς στην βιβλιογραφία, ορίζεται σε αυτήν την διατριβή ως το χρονικό διάστημα μέχρι την (νωρίτερη) εξάντληση της μπαταρίας ενός κόμβου, οπότε, εξαιτίας της επιβολής περιορισμών ενέργειας και ισχύος σε όλους τους κόμβους (εκτός από τον συλλέκτη), προκύπτει τελικά ένα πρόβλημα γραμμικού προγραμματισμού. Χρησιμοποιώντας αναλυτικές μεθόδους, το δυϊκό πρόβλημα του τελευταίου λύνεται μέσω μιας επαναληπτικής διαδικασίας προβολής υποβαθμίδας (subgradient projection), όπου σε κάθε επανάληψη λύνοναι προβλήματα ροής ελάχιστου κόστους. Ο προτεινόμενος αλγόριθμος κατασκευάζεται εξ αρχής με έμφαση στην δυνατότητα κατανεμημένης υλοποίησης, το οποίο αποτελεί σημαντική επιδίωξη στα μη-δομημένα δίκτυα. Τέλος, εξετάζεται το σενάριο που οι κόμβοι του δικτύου τροφοδοτούνται από επαναφορτιζόμενες μπαταρίες. Σε αυτήν την περίπτωση, ο χρόνος ζωής του δικτύου είναι αρκετά μεγάλος (της τάξης των ετών) ώστε να μπορεί να θεωρηθεί ως άπειρος, σε πρώτη προσέγγιση, οπότε το ενδιαφέρον της μελέτης μετατοπίζεται στην βελτιστοποίηση της επίδοσης του δικτύου. Η τελευταία ορίζεται μέσω μιας συνάρτησης ανταμοιβής, με όρισμα τους μακροχρόνιους ρυθμούς των bits που εισάγονται στο δίκτυο, ενώ, λόγω της θεωρούμενης άπειρης διάρκειας λειτουργίας, πρέπει να μελετηθεί και η ευστάθεια των ουρών του συστήματος. Χρησιμοποιώντας στοχαστικά μοντέλα για τις αφίξεις, την κατάσταση των καναλιών και την επαναφόρτιση της μπαταρίας, προτείνεται μια online πολιτική, με εγγυημένο κάτω φράγμα επίδοσης, η οποία απαιτεί μόνο γνώση στιγμιαίων παραμέτρων και οδηγεί το δίκτυο σε ευστάθεια. Αποδεικνύεται ακόμη ότι η παραπάνω πολιτική είναι ασυμπτωτικά βέλτιστη καθώς , όπου είναι η μέγιστη ενεργειακή χωρητικότητα της μπαταρίας και η μέγιστη επιτρεπτή εκπεμπόμενη ισχύς ανά χρονοθυρίδα. Και για τα τρία προβλήματα, εκτελούνται προσομοιώσεις που δείχνουν την πρακτική υλοποιησιμότητα των προτεινόμενων μεθόδων και αλγορίθμων.