| Abstract : | This work formulates, studies, and solves efficiently the Delay Tolerant Network UtilityMaximization (DTNUM) Problem. This problem describes the optimization of theflow of data in a wireless Delay-Tolerant Networking (DTN), i.e., a network that may lackcontinuous connectivity due to mobility or long distance between network nodes. Thetime-varying network topology is modeled with a directed graph consisting of a cascadeof connected subgraphs. Each subgraph corresponds to the topology of the networkduring one epoch. Due to the large number of epochs needed to model the evolution ofthe network accurately and the inherent complexities of modeling a wireless channel, asolution to the problem using standard methods can be quite intractable. For this reason,this research uses an algorithm for calculating approximations of the Capacity Region (CR)of a wireless network, i.e., the set of all possible combinations of wireless link throughputthat are simultaneously achievable. For each epoch there is an associated capacityregion and during its calculation simplifying assumptions and approximations are madebecause of the complexity of the problem. Afterwards, the construction of the optimizationproblem is represented and the efficiency of the method evaluated.
Σε αυτήν την εργασία διατυπώνεται, μελετάται και λύνεται αποδοτικά το πρόβλημα της μεγιστοποίησης της ροής δεδομένων σε ένα κινητό δίκτυο με ανοχή στις καθυστερήσεις. Η κινητικότητα των κόμβων του δικτύου μεταβάλλει τόσο τη συνδεσιμότητά τους όσο και το ρυθμό μετάδοσης των δεδομένων που εξαρτώνται από την μεταξύ τους απόσταση. Η μεταβαλλόμενη σε σχέση με το χρόνο τοπολογία του δικτύου μοντελοποιείται με έναν κατευθυνόμενο γράφο που αποτελείται από διαδοχικούς υπογράφους. Κάθε υπογράφος αποτελεί την τοπολογία του δικτύου για ένα συγκεκριμένο χρονικό διάστημα που καλείται εποχή και κατά το οποίο οι κόμβοι θεωρούνται σταθεροί. Εξαιτίας του μεγάλου αριθμού των εποχών που χρειάζονται προκειμένου να παρασταθεί η κινητικότητα του δικτύου με ακρίβεια καθώς και των εγγενών δυσκολιών της ασύρματης μετάδοσης η αποδοτική επίλυση του προβλήματος με συμβατικές μεθόδους μπορεί να είναι πολύ δύσκολη. Για το λόγο αυτό, σε αυτήν την εργασία παρουσιάζεται ένας αλγόριθμος προσεγγιστικής εύρεσης της περιοχής χωρητικότητας (Capacity Region) ενός ασύρματου δικτύου με σταθερούς κόμβους που αποτελείται από όλους τους πιθανούς συνδυασμούς κόμβων και δυνατών ρυθμών μετάδοσης μεταξύ των κόμβων αυτών. Σε κάθε εποχή υπολογίζεται η περιοχή χωρητικότητας και κατασκευάζεται αλγοριθμικά το πρόβλημα βελτιστοποίησης το οποίο και επιλύεται.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.