Consider a large population containing a small number of defective items. A commonly encountered goal is to identify the defective items, for example, to isolate them. In the classical non-adaptive group testing (NAGT) approach, one groups the items into subsets, or pools, and runs tests for the presence of a defective itemon each pool. Using the outcomes the tests, a fundamental goal of group testing is to reliably identify the complete set of defective items with as few tests as possible. In contrast, this thesis studies a non-defective subset identification problem, where the primary goal is to identify a “subset” of “non-defective” items given the test outcomes. The main contributions of this thesis are: We derive upper and lower bounds on the number of nonadaptive group tests required to identify a given number of non-defective items with arbitrarily small probability of incorrect identification as the population size goes to infinity. We show that an impressive reduction in the number of tests is achievable compared to the approach of first identifying all the defective items and then picking the required number of non-defective items from the complement set. For example, in the asymptotic regime with the population size N → ∞, to identify L nondefective items out of a population containing K defective items, when the tests are reliable, our results show that O _ K logK L N _ measurements are sufficient when L ≪ N − K and K is fixed. In contrast, the necessary number of tests using the conventional approach grows with N as O _ K logK log N K_ measurements. Our results are derived using a general sparse signal model, by virtue of which, they are also applicable to other important sparse signal based applications such as compressive sensing. We present a bouquet of computationally efficient and analytically tractable nondefective subset recovery algorithms. By analyzing the probability of error of the algorithms, we obtain bounds on the number of tests required for non-defective subset recovery with arbitrarily small probability of error. By comparing with the information theoretic lower bounds, we show that the upper bounds bounds on the number of tests are order-wise tight up to a log(K) factor, where K is the number of defective items. Our analysis accounts for the impact of both the additive noise (false positives) and dilution noise (false negatives). We also provide extensive simulation results that compare the relative performance of the different algorithms and provide further insights into their practical utility. The proposed algorithms significantly outperform the straightforward approaches of testing items one-by-one, and of first identifying the defective set and then choosing the non-defective items from the complement set, in terms of the number of measurements required to ensure a given success rate. We investigate the use of adaptive group testing in the application of finding a spectrum hole of a specified bandwidth in a given wideband of interest. We propose a group testing based spectrum hole search algorithm that exploits sparsity in the primary spectral occupancy by testing a group of adjacent sub-bands in a single test. This is enabled by a simple and easily implementable sub-Nyquist sampling scheme for signal acquisition by the cognitive radios. Energy-based hypothesis tests are used to provide an occupancy decision over the group of sub-bands, and this forms the basis of the proposed algorithm to find contiguous spectrum holes of a specified bandwidth. We extend this framework to a multistage sensing algorithm that can be employed in a variety of spectrum sensing scenarios, including non-contiguous spectrum hole search. Our analysis allows one to identify the sparsity and SNR regimes where group testing can lead to significantly lower detection delays compared to a conventional bin-by-bin energy detection scheme. We illustrate the performance of the proposed algorithms via Monte Carlo simulations.

Είναι γνωστό από τη Θεωρία της Πληροφορίας, πως η δειγματοληψία σημάτων ακολουθεί το Θεώρημα των Shannon-Nyquist. Σύμφωνα με το θεώρημα αυτό, για την εκτέλεση της δειγματοληψίας ενός σήματος χωρίς απώλεια πληροφορίας, ο ρυθμός δειγματοληψίας αυτού θα πρέπει να είναι τουλάχιστον δύο φορές μεγαλύτερος από τη μεγαλύτερη συχνότητα που εμφανίζεται στο φάσμα του σήματος. Αυτή τη θεωρία κατάφερε – κατά κάποιο τρόπο - να ανατρέψει το 2006 μια νέα, αυτή της Συμπιεσμένης Καταγραφής που ξεκίνησε από δύο επιστημονικές εργασίες των Donoho, Candes, Romberg και Tao και η οποία έρχεται να αλλάξει τα έως σήμερα δεδομένα. Σήμερα, λίγα έτη αργότερα, μια αφθονία θεωρητικών πτυχών της συμπιεσμένης καταγραφής εξερευνάται ήδη σε περισσότερες από 1000 δημοσιεύσεις. Οι εφαρμογές αυτής της τεχνικής εκτείνονται και σε άλλα πεδία όπως η επεξεργασία εικόνας, η μαγνητική τομογραφία, η ανάλυση γεωφυσικών δεδομένων, η επεξεργασία εικόνας radar, η αστρονομία κ.α. Η μέθοδος της συμπιεσμένης καταγραφής ή αλλιώς Compressed Sensing ή Compressed Sampling, όπως αυτή είναι γνωστή στη βιβλιογραφία, στηρίζεται στη δυνατότητα ανακατασκευής αραιών σημάτων από πλήθος δειγμάτων αισθητά κατώτερο από αυτό που προβλέπει το θεωρητικό όριο του Nyquist. Έχει αποδειχθεί ότι, η ανακατασκευή αυτή είναι δυνατή όταν το σήμα ή έστω κάποιος μετασχηματισμός του περιέχει λίγα μη μηδενικά στοιχεία σε σχέση με το μήκος του. Στα πλαίσια αυτής της εργασίας παρουσιάζονται οι βασικές αρχές που διέπουν την ανακατασκευή αραιών σημάτων μέσω της επίλυσης υπο-ορισμένων συστημάτων γραμμικών εξισώσεων. Στη συγκεκριμένη εργασία, γίνεται μία προσπάθεια εφαρμογής της εν λόγω μεθόδου στα ανερχόμενα Cognitive Radio δίκτυα (Cognitive Radio Networks - CRN) τα οποία εμφανίζουν την ιδιότητα Spectrum Sharing. Σύμφωνα με αυτή την ιδιότητα, δηλαδή, το διαμοιρασμό του διαθέσιμου φάσματος, ο πρωταρχικός στόχος, είναι η ανίχνευση και η αναγνώριση των λεγόμενων spectrum holes σε ασύρματο περιβάλλον. Πιο συγκεκριμένα, παρουσιάζεται μια Distributed (κατανεμημένη) προσέγγιση συμπιεσμένης καταγραφής φάσματος για (τα ultra-) Wideband Cognitive Radio δίκτυα. Η τεχνική Compressed Sensing εφαρμόζεται σε τοπικά CRs του δικτύου, προκειμένου να ανιχνεύσει το υπερ-ευρύ φάσμα (ultra-wideband) με ρεαλιστική πολυπλοκότητα ανάκτησης του αρχικού σήματος. Οι φασματικές εκτιμήσεις από πολλαπλούς τοπικούς CRs του δικτύου «συνενώνονται» για να αποκομίσουν το χωρικό κέρδος ποικιλομορφίας (spatial diversity gain), το οποίο όσο αυξάνεται, βελτιώνει την ποιότητα ανίχνευσης, ειδικά στην περίπτωση των υπό εξασθένιση καναλιών (channel fading effect). Αρχικά, μελετάται ένας κατανεμημένος αλγόριθμος πλειοψηφίας (Distributed Consensus Algorithm) για να επιτευχθεί η συνεργασία κατά το στάδιο της ανίχνευσης της πληροφορίας που μεταφέρεται στο δίκτυο και έπειτα η αποστολή αυτής σε ένα fusion center. Αυτού του είδους ο distributed αλγόριθμος που χρησιμοποιεί μόνο one-hop επικοινωνία, συγκλίνει γρήγορα σε συνολικά βέλτιστες λύσεις που λειτουργούν με χαμηλό φόρτο επικοινωνίας και υπολογισμού που είναι ανάλογο του μεγέθους του δικτύου. Ένα σενάριο που εξετάζεται στο πλαίσιο αυτής της εργασίας, είναι η συγκεντρωτική ανίχνευση φάσματος ευρείας ζώνης με επικαλυπτόμενες συχνότητες ή αλλιώς κανάλια που είναι κοινά (frequency overlapping) σε Cognitive Radio δίκτυα και τα οποία, χρησιμοποιούν την τεχνική Compressed Sensing καθώς επίσης και την από κοινού ανακατασκευή (Joint Reconstruction) του αρχικού σήματος. Τέλος, προτείνεται ένα σενάριο, μιας κατανεμημένης αυτή τη φορά, τεχνικής ανίχνευσης φάσματος, που βασίζεται σε κανόνες πλειοψηφίας. Τα αποτελέσματα της προσομοίωσης, σε περιβάλλον Matlab, επιβεβαιώνουν την αποτελεσματικότητα αυτής της προτεινόμενης προσέγγισης, δηλαδή την ανίχνευση φάσματος, από συνδυασμό Cognitive Radio δικτύων με αραιά επικαλυπτόμενες συχνότητες. / It is well known from Information Theory, that the sampling of signals should be performed as dictated by the celebrated Shannon – Nyquist theorem. According to this theorem, in order to fully recover a signal from its samples, it must be sampled at a sampling rate that should be at least twice the bandwidth of the signal. This theory has been significantly extended over the past few years by the advent of the so-called Compressed Sensing theory, which first appeared in seminal scientific articles of Donoho, Candes, Romberg and Tao in 2006. Nowadays, an abundance of theoretical aspects of compressed sensing is already explored in more than 1000 articles. Τhis technique has been applied in various fields such as image processing, magnetic tomography, analysis of geophysical data, radar image processing, astronomy etc. The method of Compressed Sensing, also known as Compressed Sampling, is related to the reconstruction of sparse signals from far fewer samples or measurements than what the theoretical limit of Nyquist suggests. It has been proved that, this reconstruction is possible when the signal or a transformation of it, contains just a few non-zero elements with respect to its length. In this work, we firstly summarize the basic principles that condition the reconstruction of sparse signals via the solution of underdetermined systems of linear equations. Next, in this Master Thesis we aim at implementing Compressed Sensing method in emerging Cognitive Radio (CR) networks with spectrum sharing. The first cognitive task preceding any dynamic spectrum access is the sensing and identification of spectral holes in wireless environments. In more detail, this work is mainly concerned with a distributed compressed spectrum sensing approach for (ultra-)wideband CR networks. Compressed sensing is performed at local CRs to scan the very wide spectrum at practical signal-acquisition complexity. Meanwhile, spectral estimates from multiple local CR detectors are fused to collect spatial diversity gain, which improves the sensing quality especially under fading channels. Initially, a distributed consensus algorithm is analyzed for collaborative sensing and fusion in a scenario where all nodes are estimating the same spectral bands. Using only one-hop local communications, this distributed algorithm converges fast to the globally optimal solutions, at low communication and computation load scalable to the network size. Another scenario that has been investigated in this thesis is the joint wideband spectrum sensing in frequency overlapping cognitive radio networks, using centralized compressive sensing techniques. Finally, for the latter scenario, a distributed compressive sensing technique, based on consensus, has been proposed. Simulation results in Matlab environment verify the effectiveness of proposed joint spectrum sensing approach in jointly sparse frequency overlapping cognitive radio networks.