Energy consumption optimization in wireless sensor networks

Abstract

Prolonging a wireless sensor network’s lifetime is closely related to energy consump-tion and particularly to the energy hole problem, where sensor nodes close to the sink node consume a considerable amount of their energy for relaying purposes. In order to tackle the energy hole problem’s eects, this thesis proposes two approaches that counter the problem from two perspectives: (i) the minimization of the energy consumption by approaching the sink placement problem as a k-median problem and (ii) the prolongation of the network’s lifetime by recharging its sensor nodes.In the rst approach, an analytical model for analyzing the available energy in the network is proposed. The next step is to analytically model the overall energy consumption as a k-median facility location problem, its solution corresponding to the location of k sinks in the network. As analytically shown, when k sinks are placed according to the solution of the previous facility location problem, then the overall energy consumption is minimized, resulting in a higher energy-saving system. Thus, the saved energy can be further utilized, e.g., to extend the network’s lifetime and support modern replenishing techniques such as energy harvesting and battery recharging. Simulation results validate the analytical model that is the basis of the analysis and conrm the results with respect to the available energy in the network. In particular, signicant energy savings are observed when the analytical results are applied, thus resulting in better energy utilization and subsequent network lifetime increment.The second approach is focused on two proposed recharging policies. The rst one is a simple recharging policy that permits a mobile recharger, initially stationed at the sink node, to move around and replenish any node’s exhausted battery when a certain recharging threshold is violated. This policy, as well as the second pro-posed recharging policy (i.e., the enhanced recharging policy), refer to on-demand recharging policies which base their operation on local information, allowing the mobile recharger to move – upon request – to a node of reduced energy level and re-plenish its battery. When under the enhanced recharging policy and after completing the latter replenishment, the mobile recharger continues operating in a hop-by-hop manner to the neighbor nodes of the lowest energy level, thus replenishing their batteries too. It is shown that the minimization of the recharging distance covered by the mobile recharger is a facility location problem, and particularly an 1-median one. Simulation results, regarding the simple recharging policy, investigate various aspects of it related to the recharging threshold and the level of the energy left in the network nodes’ batteries. In addition, it is shown that when the sink’s location is set to the solution of the particular facility location problem, then the recharging distance is minimized irrespectively of the recharging threshold. As for the enhanced recharging policy’s simulation results, its eectiveness is investigated using simula-tion results and compared against an existing well-known on-demand recharging policy that exploits global knowledge (i.e., knowledge of both the energy level of all nodes and the network topology). It is shown that the enhanced recharging policy, even though based on local information, maintain the average energy level and termination time higher than that under the existing one that exploits global knowledge. Furthermore, it is observed that the network’s lifetime is maximized when the basis of the mobile recharger is located at the solution of the mentioned median problem for all studied policies.The approaches studied in this thesis establish a relation between facility location problems (particularly the k-median problem) and energy consumption and battery replenishment. This is a signicant contribution that is expected to trigger future work in the area and reveal further aspects of the energy consumption issues and how lifetime may be prolonged in wireless sensor networks.

Η παράταση της διάρκειας ζωής ενός δικτύου ασύρματων αισθητήρων σχετίζεται στενά με την κατανάλωση ενέργειας και ειδικότερα με το πρόβλημα της ενεργειακής τρύπας (energy hole problem), όπου οι κόμβοι που βρίσκονται κοντά στον κόμβο-συλλέκτη (sink node) καταναλώνουν σημαντικό μέρος της ενέργειας τους για λόγους αναμετάδοσης. Για την αντιμετώπιση των επιπτώσεων του προβλήματος της ενεργειακής τρύπας, αυτή η διατριβή προτείνει δύο προσεγγίσεις που αντιμετωπίζουν το πρόβλημα από δύο οπτικές γωνίες: (i) την ελαχιστοποίηση της κατανάλωσης ενέργειας προσεγγίζοντας το πρόβλημα της τοποθέτησης του συλλέκτη (sink placement problem) ως πρόβλημα τοποθέτησης υπηρεσίας (facility location problem) και (ii) την παράταση της διάρκειας ζωής του δικτύου επαναφορτίζοντας τους κόμβους του.Στην πρώτη προσέγγιση προτείνεται ένα αναλυτικό μοντέλο για την ανάλυση της διαθέσιμης ενέργειας στο δίκτυο. Το επόμενο βήμα είναι η μοντελοποίηση της συνολικής κατανάλωσης ενέργειας ως πρόβλημα τοποθέτησης υπηρεσίας και πιο συγκεκριμένα ως πρόβλημα k-διάμεσων (k-median problem), η λύση του οποίου αντιστοιχεί στη θέση των k συλλεκτών στο δίκτυο. Όπως παρουσιάζεται αναλυτικά, όταν οι k συλλέκτες τοποθετούνται σύμφωνα με τη λύση του προηγούμενου προβλήματος τοποθέτησης υπηρεσίας, τότε ελαχιστοποιείται η συνολική κατανάλωση ενέργειας, με αποτέλεσμα ένα ενεργειακά αποδοτικότερο σύστημα. Η εξοικονόμηση ενέργειας που επιτυγχάνεται μπορεί να χρησιμοποιηθεί περαιτέρω, π.χ., για να επεκταθεί η διάρκεια ζωής του δικτύου και να υποστηριχθούν σύγχρονες τεχνικές ανανέωσης ενέργειας όπως οι εκ-μετάλλευση ανανεώσιμων πηγών ενέργειας και η επαναφόρτιση των μπαταριών των κόμβων. Τα αποτελέσματα των προσομοιώσεων επικυρώνουν το αναλυτικό μοντέλο που αποτελεί τη βάση της ανάλυσης και επιβεβαιώνουν τα αποτελέσματα σε σχέση με τη διαθέσιμη ενέργεια στο δίκτυο. Συγκεκριμένα, παρατηρείται σημαντική εξοικονόμηση ενέργειας κατά την εφαρμογή των αναλυτικών αποτελεσμάτων, με αποτέλεσμα την καλύτερη αξιοποίηση της ενέργειας και την επακόλουθη αύξηση της διάρκειας ζωής του δικτύου.Η δεύτερη προσέγγιση εστιάζεται σε δύο προτεινόμενες πολιτικές επαναφόρτισης. Η πρώτη είναι μια απλή πολιτική επαναφόρτισης που επιτρέπει σε ένα φορητό φορτιστή (mobile recharger), αρχικά τοποθετημένο στην ίδια θέση με τον κόμβοσυλλέκτη, να κινείται και να αναπληρώνει την εξαντλημένη μπαταρία ενός κόμβου όταν παραβιάζεται ένα συγκεκριμένο όριο επαναφόρτισης. Η πολιτική αυτή, όπως και δεύτερη πολιτική επαναφόρτισης που μελετάται λειτουργούν κατόπιν αιτημάτων (on-demand) και βασίζουν τη λειτουργία τους σε τοπική πληροφόρηση επιτρέποντας στο φορητό φορτιστή να μετακινηθεί – κατόπιν αιτήματος – σε έναν κόμβο με μειωμένο επίπεδο ενέργειας και να ανανεώσει την μπαταρία του. Κατά τη δεύτερη πολιτική και μετά την ολοκλήρωση της τελευταίας διαδικασίας, ο φορητός φορτιστής συνεχίζει να λειτουργεί με πολυαλματική λογική στους γειτονικούς κόμβους με το χαμηλότερο επίπεδο ενέργειας, ανανεώνοντας έτσι και τις μπαταρίες αυτών. Όπως δείχνεται, η ελαχιστοποίηση της απόστασης επαναφόρτισης που καλύπτεται από τον φορητό φορτιστή είναι ένα πρόβλημα τοποθέτησης υπηρεσίας και συγκεκριμένα ένα πρόβλημα 1-διάμεσου. Τα αποτελέσματα προσομοίωσης, σχετικά με την πρώτη προτεινόμενη πολιτική, διερευνούν διάφορες πτυχές της πολιτικής επαναφόρτισης - συμπεριλαμβανομένης μιας βελτιωμένης έκδοσής της - που σχετίζονται με το όριο επαναφόρτισης και το επίπεδο ενέργειας που απομένει στις μπαταρίες των κόμβων του δικτύου. Επιπλέον, δείχνεται πως όταν η θέση του συλλέκτη έχει επιλεγεί βάση της λύσης του συγκεκριμένου προ-βλήματος τοποθέτησης υπηρεσίας, τότε η απόσταση επαναφόρτισης ελαχιστοποιείται ανεξάρτητα από το όριο επαναφόρτισης. Όσον αφορά τα αποτελέσματα προσομοίωσης της δεύτερης προτεινόμενης πολιτικής, η αποτελεσματικότητά της διερευνάται χρησιμοποιώντας αποτελέσματα προσομοίωσης και συγκρίνεται με μια υπάρχουσα γνωστή πολιτική ανανέωσης που λειτουργεί κατόπιν αιτημάτων που εκμεταλλεύεται την γνώση όλου του δικτύου (δηλαδή γνώση τόσο του ενεργειακού επιπέδου όλων των κόμβων όσο και της τοπολογίας του δικτύου). Αποδεικνύεται ότι η προτεινόμενη πολιτική, αν και βασίζεται σε τοπική πληροφόρηση, διατηρεί το μέσο ενεργειακό επίπεδο και τον χρόνο τερματισμού υψηλότερο από εκείνο της υφιστάμενης πολιτικής που εκμεταλλεύεται την γνώση όλου του δικτύου. Επιπλέον, παρατηρείται ότι η διάρκεια ζωής του δικτύου μεγιστοποιείται όταν η βάση του φορητού φορτιστή βρίσκεται στη λύση του αναφερόμενου προβλήματος 1-διάμεσου για όλες τις πολιτικές που μελετούνται. Οι προσεγγίσεις που μελετούνται σε αυτή τη διατριβή καθιστούν μια συσχέτιση μεταξύ των προβλημάτων τοποθέτησης υπηρεσίας (ιδιαίτερα του προβλήματος k-διάμεσων) με την κατανάλωση ενέργειας και την αναπλήρωση της μπαταρίας. Πρόκειται για μια σημαντική συμβολή που αναμένεται να προκαλέσει μελλοντικές έρευνες στην περιοχή και να αποκαλύψει περαιτέρω πτυχές των ζητημάτων κατανάλωσης ενέργειας και του τρόπου με τον οποίο η διάρκεια ζωής μπορεί να παραταθεί στα ασύρματα δίκτυα αισθητήρων.