Αυτοματοποιημένη τοποθέτηση σταθμών βάσης για βέλτιστη ραδιοκάλυψη σε ασύρματα δίκτυα

Abstract

Στόχος αυτής της εργασίας είναι η αυτοματοποιημένη τοποθέτηση σταθμών βάσης, για βέλτιστη ραδιοκάλυψη σε ασύρματα δίκτυα μιας περιοχής με το μικρότερο κόστος, δηλαδή μέσω του ελάχιστου δυνατού αριθμού σταθμών βάσης (BSs). Το κόστος και η πολυπλοκότητα ενός δικτύου, συνδέονται στενά με τον αριθμό των σταθμών βάσης (BSs) που απαιτούνται για την επίτευξη των στόχων, τους οποίους έχει ορίσει η επιχείρηση εκμετάλλευσης του συστήματος. Η τοποθεσία των BSs δεν είναι εύκολο έργο και υπάρχουν διάφοροι παράγοντες που πρέπει να ληφθούν υπόψη όταν καθορίζεται η βέλτιστη θέση του BS. Σε αυτήν την εργασία θα εξεταστούν δυο αλγόριθμοι βελτιστοποίησης, ο Συνδυαστικός Αλγόριθμος για Ολική Βελτιστοποίηση CAT (Combination Algorithm for Total Optimisation) [1] και ο Άπληστος Αλγόριθμος GR (Greedy Algorithm) [3]. Αρχικά θα εφαρμοστεί ο αλγόριθμος CAT, του οποίου η λειτουργία βασίζεται στην συνδυαστική προσέγγιση. O αλγόριθμος CAT εφαρμόζεται σε τυχαία υποσύνολα των δυνατών θέσεων των BSs στην περιοχή δοκιμής. Στην συνέχεια ο αλγόριθμος GR θα εφαρμοστεί σε όλες τις τελικές λύσεις που δίνει ο αλγόριθμος CAT, με σκοπό την περαιτέρω μείωση του αριθμού σταθμών βάσης. Επίσης οι αλγόριθμοι εξετάστηκαν ως προς την ικανότητα σύγκλισης σε μια λύση, ως προς τον αριθμό των επαναλήψεων που είναι απαραίτητος για να βρεθεί λύση και ως προς τον αριθμό των BSs που θα έχουν τα τυχαία υποσύνολα των δυνατών θέσεων των BSs . Βρέθηκε ότι χρειάζονται 8000 επαναλήψεις. Για κάθε διαφορετικό περιβάλλον που εξετάσαμε βρήκαμε διαφορετική λύση. Έτσι καταλήξαμε ότι για περιβάλλον με n=2 χρειαζόμαστε 3-4 BSs ανάλογα και την σκίαση, σε περιβάλλον με n=3 χρειαζόμαστε 4-6 BSs ανάλογα και την σκίαση και σε περιβάλλον με n=4 χρειαζόμαστε 6-7 BSs ανάλογα και την σκίαση. Οι δυο αλγόριθμοι προσομοιώθηκαν σε Matlab και συγκρίθηκαν ως προς την πολυπλοκότητα και την αποτελεσματικότητά τους στην εύρεση της βέλτιστης λύσης για την πλήρη κάλυψη της περιοχής.