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

Abstract

Wireless Sensor Networks (WSNs) have received the scientific attention of many researchers in the last years, because they offer unique advantages and flexibility concerning the sensing, detection and measurement of physical quantities, paving the way towards low cost and low power applications which do not require human intervention. These applications could be military, environmental monitoring, industrial and home automation, health monitoring and many other commercial (materials fatigue monitoring, building health monitoring, robotic systems, transportations and smart grid). WSNs are self-organized networks and are created from the collection of large number of sensor nodes, which are interconnected throught the wireless medium. Simple nodes are embedded systems with integrated cirtuits that allow them to receive signals, to process data and to send them to one or several intermediate destinations. Each node is perceived as an individual electromechanical system which has limited energy reserves, most of the times without the capability to renew them. To this end, the main constraint factor for the design and development of a WSN is energy.Major research has been conducted in the field of energy saving techniques, many of which focus and rely only on particular layers of OSI (Open System Interconnection) architecture (such as physical layer, data link layer and network layer). Many of the proposed solutions and protocols for node energy consumption management stem from protocols applied in ad hoc networks. Most of them are not based on cross-layer optimization techniques and do not try to optimize several variables jointly, taking into account the unique characteristics and constraints imposed in WSNs. In contrast, this PhD dissertation thesis is based on cross-layer optimization techniques.Therefore, this PhD thesis aims to prolong and maximize the total network lifetime and network coverage by applying cross-layer optimization, joint variable optimization, nodes placement optimization and energy efficiency algorithms. Initially, placement techniques were studied in precision agriculture applications and empirical topology placements techniques were proposed which satisfy certain constraints, reducing the overall network energy consumption and utilizing optimally network throughput. The problem of node placement and topology creation to cover a 2-D space applies to every of the aforementioned WSN applications. In the sequel, we propose an algorithm which distributes and total network energy reserves unequally among sensor nodes, taking into account the nodes placements and role in the network topology. The output of this algorithm is a final energy charge per node. We call this algorithm Unequal Charge Distribution (UCD) algorithm. Using UCD, we define an optimization problem which intends to prolong both the network coverage and network lifetime. We maximize these variables jointly by solving our problem using Simulated Annealing optimization technique, which is preferred for complex systems and NP-Complete problems. We therefore propose an optimal placement scheme in 2D space satisfying certain constraints. For the statistical robustness of our results, we conduct a statistical analysis applying Reliability Theory and reach the best set up scenario which is appropriate for the aforementioned optimization problem.Finally, we study the joint optimization problem of transmit power, packet length and topology deployment with the goal to minimize the total network energy consumption. To this end, we formulate a problem which we prove that is NP-Complete and we solve it using heuristic algorithms. Our goal is to minimize total energy consumption by applying error correction code techniques in the data link layer of the OSI model. Therefore we propose a final and near optimal topology, packet length and transmit power solution while satisfying the constraints imposed by the optimization problem.

Τα ασύρματα δίκτυα αισθητήρων (Α.Δ.Α.) έχουν συγκεντρώσει το ενδιαφέρον πολλών ερευνητών τα τελευταία χρόνια, δεδομένου ότι προσφέρουν μοναδικά πλεονεκτήματα και ευελιξία σχετικά με την ανίχνευση και μέτρηση φυσικών ποσοτήτων, ανοίγοντας το δρόμο για εφαρμογές χαμηλού κόστους και ισχύος οι οποίες δεν χρειάζονται ανθρώπινη παρέμβαση. Οι εφαρμογές αυτές μπορεί να είναι στρατιωτικές, περιβαλλογικές, βιομηχανική και οικιακή αυτοματοποίηση, υγείας και άλλες πολλές εμπορικές (παρακολούθηση κόπωσης υλικών, ρομποτικά συστήματα, μεταφορές, smart grid). Τα Α.Δ.Α δημιουργούνται και αυτο-οργανώνονται από τη συλλογή μεγάλου αριθμού κόμβων, οι οποίοι διασυνδέονται μεταξύ τους στο ασύρματο μέσο. Οι απλοί κόμβοι είναι ενσωματωμένα συστήματα με ολοκληρωμένα κυκλώματα που τους επιτρέπουν να λαμβάνουν σήματα, να επεξεργαστούν δεδομένα και να τα αποστείλουν σε έναν ή πολλούς τελικούς ή ενδιάμεσους προορισμούς. Κάθε κόμβος νοείται ως ένα ανεξάρτητο ηλεκτρομηχανολογικό σύστημα το οποίο διαθέτει περιορισμένα αποθέματα ενέργειας, τις περισσότερες φορές χωρίς τη δυνατότητα ανανέωσής τους. Ο κυριότερος λοιπόν περιοριστικός παράγοντας για τον σχεδιαμό και την ανάπτυξη ενός Α.Δ.Α. είναι η ενέργεια.Σημαντικές έρευνες έχουν λάβει χώρα στον τομέα των τεχνικών εξοικονόμησης ενέργειας, πολλές από τις οποίες επικεντρώνονται μόνο σε συγκεκριμένα επίπεδα της OSI αρχιτεκτονικής (physical layer, data link layer, network layer). Πολλές από τις λύσεις και τα πρωτόκολλα που εφαρμόζονται για την ενεργειακή διαχείριση σε κόμβους είναι δανεισμένα από λύσεις που αφορούν ασύρματα ad hoc δίκτυα και δεν έχουν προταθεί λύσεις βασισμένες σε cross-layer τεχνικές, λαμβάνοντας υπόψη τα μοναδικά χαρακτηριστικά και τους περιορισμούς των Α.Δ.Α. Προς αυτή την κατεύθυνση κινείται η μελέτη σε αυτή την διδακτορική διατριβή. Στόχος της διατριβής είναι μέσω εφαρμογής τεχνικών cross-layer, μεθόδου βελτιστοποίησης, βέλτιστης χωροταξικής τοποθέτησης κόμβων και έξυπνης διαχείρισης ενεργειακών αποθεμάτων στους κόμβους να επιμηκυνθεί η συνολική διάρκεια ζωής ενός Α.Δ.Α. Αρχικά μελετήθηκαν τρόποι τοποθέτησης κόμβων σε εφαρμογές γεωργίας ακριβείας και προτάθηκαν τοπολογίες που ικανοποιούν κάποιους περιορισμούς, μειώνοντας την συνολική ενεργειακή κατανάλωση και αξιοποιώντας καλύτερα την διαθέσιμη ρυθμαπόδοση (throughput). Το πρόβλημα τοποθέτησης κόμβων σε χώρο συγκεκριμένων διαστάσεων, αφορά οποιαδήποτε εφαρμογή. Στη συνέχεια, προτείνουμε έναν αλγόριθμο, ο οποίος ανισοκατανέμει το συνολικό ενεργειακό απόθεμα ενός Α.Δ.Α στους διάφορους κόμβους, λαμβάνοντας υπόψη του την τοποθέτηση και τον ρόλο τους εντός της τοπολογίας του δικτύου. Αποδεικνύουμε ότι η διάρκεια ζωής του δικτύου επιμηκύνεται σε σημαντικό βαθμό. Στη συνέχεια, εφαρμόζοντας τον αλγόριθμο άνισης φόρτισης, ορίζουμε ένα πρόβλημα βελτιστοποίησης που έχει ως στόχο να αυξήσει την κάλυψη του δικτύου (network coverage) και να επιμηκύνει την συνολική διάρκειά του (network lifetime). Λύνουμε το πρόβλημα αυτό μέσω τεχνικής βελτιστοποίησης Simulated Annealing η οποία χρησιμοποιείται σε πολύπλοκα συστήματα και NP complete προβλήματα. Αυτό που προτείνουμε είναι μία βέλτιστη χωροταξική τοποθέτηση των κόμβων στις δύο διαστάσεις, ικανοποιώντας τους περιορισμούς του προβλήματος. Για την στατιστική ευρωστία των αποτελεσμάτων μας, εφαρμόζουμε ιδέες από την θεωρία αξιοπιστίας (reliability theory), όπου προτείνουμε το καλύτερο set up το οποίο λύνει το πρόβλημα βελτιστοποίησης που ορίστηκε. Τέλος, προτείνουμε μία cross layer προσέγγιση βελτιστοποίησης ελέγχου ισχύος εκπομπής, μήκους πακέτου δεδομένων και τοπολογίας με στόχο την ελαχιστοποίηση της συνολικής κατανάλωσης ενέργειας στο δίκτυο.Αποδεικνύουμε ότι το πρόβλημα που ορίζουμε είναι NP-Complete και το λύνουμε με ευρετικό τρόπο (heuristic). Στόχος μας είναι η ελαχιστοποίηση της ενεργειακής κατανάλωσης όταν εφαρμοστούν τεχνικές error correction στο data link layer του OSI model. Προτείνουμε συνεπώς μία τελική και βέλτιστη τοπολογία κόμβων, τιμή μήκους πακέτου εκπομπής και τιμή ισχύς εκπομπής, ικανοποιώντας ταυτόχρονα τους περιορισμός του προβλήματος βελτιστοποίησης που ορίσαμε.Ως μελλοντική και φυσική συνέχεια της παρούσας εργασίας θα ήταν η 3D τοποθέτηση των κόμβων, ικανοποιώντας περισσότερους περιορισμούς και μεταβλητές που προκύπτουν από μία μορφοποίηση προβλήματος μέσω cross-layer τεχνικών.