Δρομολόγηση με βάση πολλαπλά κόστη σε ασύρματα αδόμητα δίκτυα

Abstract

Until now routing in wireless ad hoc networks has been studied by taking into account a single scalar metric for every network link representing the cost of transmitting through this link. In multicost routing a vector of cost parameters is assigned to each link based on which a respective cost vector is produced for every path in the network. For every source destination pair all the candidate paths are initially calculated that are non dominated to each other. At the cost vectors of the candidate paths, an optimization function is applied in order to produce a cost for each path based on which the selection of the optimal one is made. In the present thesis multicost routing in wireless ad hoc networks was studied initially using as cost parameters the node residual energy and transmission power. As a next step the interference cause by the transmission of each link was added to the cost vectors assigned to each network link. The simulation results showed that multicost routing in comparison to traditional routing practices achieves more uniform traffic distribution and energy consumption in the network prolongs the network lifetime and increases the percentage of the packets that are successfully delivered to their destinations. Expanding these ideas the multicost routing algorithm was next implemented in a fully distributed fashion in which additionally the node mobility was taken into account. The results again proved that a significant improvement was accomplished compared to minimum hop routing. Finally, multicost routing was applied in the field of multicasting and broadcasting in wireless ad hoc networks. The emphasis was again on energy efficiency by incorporating energy-related cost parameters like node residual energy and transmission power. The multicost algorithm calculates the optimal energy efficient sequence of nodes that by transmitting implement the desired communication task (multicasting or broadcasting). Simulation results illustrate a clear advantage of our algorithm over established solutions for energy efficient multicasting and broadcasting.

Μέχρι σήμερα στη δρομολόγηση στα ασύρματα αδόμητα δίκτυα λαμβάνεται ως κριτήριο ένα μοναδιαίο μέγεθος για κάθε σύνδεσμο του δικτύου το οποίο αναπαριστά το κόστος της μετάδοσης πάνω στον συγκεκριμένο σύνδεσμο. Στη δρομολόγηση με βάση πολλαπλά κριτήρια η βασική ιδέα είναι ότι σε κάθε σύνδεσμο ανατίθεται ένα διάνυσμα από παραμέτρους κόστη με βάση το οποίο προκύπτει και ένα αντίστοιχο διάνυσμα για κάθε μονοπάτι. Για κάθε ζευγάρι κόμβων αποστολέα παραλήπτη γίνεται καταρχήν η εύρεση όλων των υποψήφιων για χρήση μονοπατιών. Τα υποψήφια μονοπάτια που λαμβάνονται υπόψη κατά τη διαδικασία επιλογής έχουν την ιδιότητα να είναι μη κυριαρχημένα μεταξύ τους. Στη συνέχεια εφαρμόζεται στο σύνολο των μη κυριαρχημένων μονοπατιών μια συνάρτηση που συνδυάζοντας τις συνιστώσες του κάθε διανύσματος παράγει το κόστος χρήσης κάθε μονοπατιού και έτσι το μονοπάτι με το ελάχιστο κόστος επιλέγεται για χρήση. Στα πλαίσια της εργασίας καταρχήν μελετήθηκε ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη χρησιμοποιώντας παραμέτρους κόστη σχετικές με την ενέργεια όπως η τρέχουσα διαθέσιμη ενέργεια στους κόμβους και η ισχύς μετάδοσης τους. Στη συνέχεια στις παραμέτρους προστέθηκε και η παρεμβολή που δημιουργείται από τη μετάδοση πάνω σε ένα σύνδεσμο. Τα αποτελέσματα των προσομοιώσεων έδειξαν ότι ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη σε σχέση με τον ελάχιστου μήκους διαδρομής κατανέμει πιο ομοιόμορφα την κίνηση στο δίκτυο, επιμηκύνει τον χρόνο ζωής του δικτύου και αυξάνει το ποσοστό των παραδιδόμενων πακέτων. Στο επόμενο στάδιο της εργασίας έγινε μια κατανεμημένη υλοποίηση του αλγορίθμου δρομολόγησης με πολλαπλά κόστη που επιπλέον λαμβάνει υπόψη την κινητικότητα των κόμβων του δικτύου η οποία και πάλι φάνηκε να υπερέχει έναντι πιο παραδοσιακών πρακτικών. Τέλος η ιδέα της δρομολόγησης με πολλαπλά κόστη εφαρμόστηκε για τη λύση του προβλήματος ενεργό αποδοτικής πολλαπλής η ολικής εκπομπής (multicasting ή broadcasting αντίστοιχα). Στόχος ήταν να βρεθεί η βέλτιστη ενεργό αποδοτικά ακολουθία συνδέσμων πάνω στους οποίους πρέπει να γίνει μετάδοση ενός πακέτου προκείμενου να υλοποιηθεί η επιθυμητή εκπομπή. Σαν παράμετροι κόστη χρησιμοποιήθηκαν η τρέχουσα διαθέσιμη ενέργεια και η ισχύς μετάδοσης των κόμβων. Τα αποτελέσματα δείχνουν σαφή υπέροχη του αλγορίθμου με πολλαπλά κόστη έναντι παραδοσιακών λύσεων τόσο για πολλαπλή εκπομπή όσο και για ολική εκπομπή.