Design of networks with limited resources

Abstract

Scarce network resources impact the architecture design of networks. The effort to overcome network limitations is conducted both in the physical level, by developing improved hardware and devices, and in software level, where faster and smarter algorithms are invented. This thesis examines resource limitation problems in broadcast networks, wireless sensor networks and molecular nanonetworks. Broadcast networks are characterized by the limited upload capacity of clients. The main challenge is constructing a broadcast schedule that minimizes delay for the clients. The current state of the art algorithm, generates a near optimal broadcast schedule, but suffers from a prohibitive time complexity. The proposed method, presented in the rst part of this thesis, achieves near state-of-the-art performance with low computational complexity. It uses a special data structure, that stores data in accordance to their popularity. The method is computationally efcient, since it constructs the broadcast schedule simply by traversing this data structure. Wireless sensor networks contain simple sensor nodes that are limited in capabilities. Distance estimation is an important problem, since accurate localization of the sensors can benet the network performance and efciency. Current techniques to estimate distances between sensors, require that some sensor nodes contain specialized hardware. However, a basic requirement for sensor networks, is that the nodes must be kept simple. In the second part of this thesis, a method is proposed that can achieve distance estimation without any requirement for the sensor nodes. The proposed method uses a formula to estimate distances from the hop-distance of two nodes and is shown to perform similarly to other methods that require extra specialized hardware. In the nal part of this thesis, nanonetworks are introduced. Even though nanonetworks is an emerging and promising eld, one of the most important restrictions in current nanonetworks, is that they assume technology that is not yet widely available. A new method of communication is proposed, where bacteria cell concentration is used directly as a means of transmitting information. This method is relatively simple to implement, and when chemotaxis is utilized, communications up to a cm are shown to be possible. All proposed methods in this thesis are theoretically supported and their performance is evaluated through simulation. The simulation results presented in this thesis, demonstrate the validity and utility of those methods under a variety of scenarios.

Ο σχεδιασμός της αρχιτεκτονικής ενός δικτύου επηρεάζεται από τους περιορισμένους πόρους του δικτύου. Η προσπάθεια βελτίωσης ενός δικτύου διεξάγεται αφενός σε φυσικό επίπεδο, με την ανάπτυξη βελτιωμένου υλικού και συσκευών, αλλά και σε επίπεδο λογισμικού, όπου εφευρίσκονται ολοένα και πιο γρήγοροι και έξυπνοι αλγόριθμοι. Αυτή η διατριβή εξετάζει τους περιορισμούς πόρων σε δίκτυα εκπομπής, σε ασύρματα δίκτυα αισθητήρων και σε μοριακά νανοδίκτυα. Τα δίκτυα εκπομπής χαρακτηρίζονται από περιορισμένη χωρητικότητα επικοινωνίας των πελατών προς τον σταθμό βάσης. Η κύρια πρόκληση είναι η κατασκευή ενός προγράμματος εκπομπής που na ελαχιστοποιεί την καθυστέρηση για τους πελάτες. Η καλύτερη γνωστή μέθοδος, καταφέρνει πρόγραμμα εκπομπής πολύ κοντά στο βέλτιστο, αλλά πάσχει από απαγορευτική χρονική πολυπλοκότητα. Η προτεινόμενη μέθοδος, που παρουσιάζεται στο πρώτο μέρος αυτής της διατριβής, επιτυγχάνει σχεδόν βέλτιστη απόδοση με χαμηλή υπολογιστική πολυπλοκότητα. Χρησιμοποιεί μια ειδικά σχεδιασμένη δομή δεδομένων, η οποία οργανώνει τα δεδομένα αναλόγως της δημοτικότητάς τους. Η μέθοδος είναι υπολογιστικά αποδοτική, καθώς κατασκευάζει το πρόγραμμα εκπομπής απλά διασχίζοντας αυτή τη δομή δεδομένων. Τα ασύρματα δίκτυα αισθητήρων αποτελούνται από απλούς κόμβους αισθητήρων περιορισμένων δυνατοτήτων. Η εκτίμηση απόστασης είναι σημαντικό πρόβλημα αυτών των δικτύων, καθώς ο ακριβής εντοπισμός της θέσης των αισθητήρων μπορεί να ωφελήσει την απόδοση και την αποτελεσματικότητα του δικτύου. Συνήθως οι τεχνικές της βιβλιογραφίας για την εκτίμηση των αποστάσεων μεταξύ αισθητήρων απαιτούν από ορισμένους ειδικούς κόμβους να περιέχουν εξειδικευμένο υλικό, ώστε να έχουν ακριβή γνώση της θέσης τους. Όμως, βασική απαίτηση των δικτύων αισθητήρων είναι η απλότητα των κόμβων. Στο δεύτερο κομμάτι αυτής της διατριβής, προτείνεται μια μέθοδος, η οποία καταφέρνει εκτίμηση απόστασης μέσω μαθηματικής έκφρασης και χωρίς να χρειάζεται εξειδικευμένο υλικό για τους κόμβους. Στο τελευταίο κομμάτι της διατριβής γίνεται εισαγωγή στα νανοδίκτυα. Παρόλο που τα νανοδίκτυα είναι ένας πολλά υποσχόμενος χώρος, ένας από τους βασικότερους περιορισμούς τους είναι ότι προϋποθέτουν τεχνολογία, η οποία δεν είναι ακόμη ευρέως διαθέσιμη. Ένα νέο μοντέλο επικοινωνίας προτείνεται όπου η συγκέντρωση των βακτηρίων χρησιμοποιείται ως μέσο μετάδοσης πληροφοριών. Η μέθοδος αυτή είναι σχετικά απλή στην υλοποίησή της, και όταν χρησιμοποιεί χημειοτακτισμό, επιτυγχάνει επικοινωνία σε αποστάσεις ως το ένα cm. Όλες οι προτεινόμενες μέθοδοι αυτής τη διατριβής υποστηρίζονται θεωρητικά και η απόδοσή τους αξιολογείται με προσομοίωση. Τα αποτελέσματα προσομοίωσης που παρουσιάζονται σε αυτή τη διατριβή, καταδεικνύουν την εγκυρότητα και χρησιμότητα αυτών των μεθόδων υπό μια ποικιλία σεναρίων.