000212930 001__ 212930 000212930 005__ 20190509132528.0 000212930 0247_ $$2doi$$a10.5075/epfl-thesis-6762 000212930 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis6762-7 000212930 02471 $$2nebis$$a10538680 000212930 037__ $$aTHESIS 000212930 041__ $$aeng 000212930 088__ $$a6762 000212930 245__ $$aAdaptive Selection Problems in Networked Systems 000212930 269__ $$a2015 000212930 260__ $$bEPFL$$c2015$$aLausanne 000212930 300__ $$a132 000212930 336__ $$aTheses 000212930 502__ $$aProf. Emre Telatar (président) ; Prof. Martin Vetterli, Prof. Patrick Thiran (directeurs) ; Dr Leveque Olivier, Prof. Mikael Johansson, Prof. Gil Zussman (rapporteurs) 000212930 520__ $$aNetworked systems are composed of interconnected nodes that work collaboratively to maximize a given overall utility function. Typical examples of such systems are wireless sensor networks (WSNs) and participatory sensing systems: sensor nodes, either static or mobile, are deployed for monitoring a certain physical field. In these systems, there are a set of problems where we need to adaptively select a strategy to run the system, in order to enhance the efficiency of utilizing the resources available to the system. In particular, we study four adaptive selection problems as follows. We start by studying the problem of base-station (BS) selection in WSNs. Base stations are critical sensor nodes whose failures cause severe data losses. Deploying multiple fixed BSs improves the robustness, yet this scheme is not energy efficient because BSs have high energy consumptions. We propose a scheme that selects only one BS to be active at a time; other BSs are kept passive and act as regular sensor nodes. This scheme substantially reduces the energy supplies required by individual BSs. Then, we propose an algorithm for adaptively selecting the active BS so that the spatially and temporally varying energy resources are efficiently utilized. We also address implementation issues and apply the proposed algorithm on a real WSN. Field experiments have shown the effectiveness of the proposed algorithm. We generalize the BS selection problem by considering both the energy efficiency of regular sensor nodes and that of BSs. In this scheme, a subset of active BSs (instead of only one) is adaptively selected and the routing of regular sensor nodes is adjusted accordingly. Because BSs have high fixed-energy consumptions and because the number of candidate subsets of active BSs is exponential with the number of BSs, this general BS selection problem is NP-hard. We propose a polynomial-time algorithm that is guaranteed, under mild conditions, to achieve a network lifetime at least 62% of the optimal one. Through extensive numerical simulations, we verify that the lifetime achieved by the proposed algorithm is always very close to the optimum. We then study the problem of scheduling the sparse-sensing patterns in WSNs. We observe that the traditional scheme of periodically taking sensing samples is not energy efficient. Instead, we propose to adaptively schedule when and where to activate sensors for sampling a physical field, such that the energy efficiency is enhanced and the sensing precision is maintained. The schedules are learnt from the temporal signal models derived from the collected measurements. Then, using the obtained signal models and the sparse sensing-measurements, the original signal can be effectively recovered. This proposed method requires minimal on-board computation, no inter-node communications and achieves an appealing reconstruction performance. With experiments on real-world datasets, we demonstrate significant improvements over both traditional sensing schemes and the state-of-the-art sparse-sensing schemes, particularly when the measured data is characterized by a strong temporal correlation. In the last part of the thesis, we discuss the sparse-sensing framework by exploiting the spatial correlations rather than the temporal correlations among the captured measurements. In this framework, application-specific utility functions can be employed. By adaptively selecting a small subset of active sensors for sensing, a certain utility is guaranteed and the efficiency of the sensing system is enhanced. We apply this framework both in static WSNs and participatory sensing systems where sensors move in an uncoordinated manner. Through extensive simulations, we show that our proposed algorithm enhances the resource efficiency. 000212930 6531_ $$anetworked system 000212930 6531_ $$awireless sensor networks 000212930 6531_ $$aparticipatory sensing 000212930 6531_ $$aresource efficiency 000212930 6531_ $$aadaptive selection problem 000212930 6531_ $$anetwork optimization 000212930 6531_ $$asparse sampling 000212930 700__ $$0246435$$g199314$$aZhang, Runwei 000212930 720_2 $$aVetterli, Martin$$edir.$$g107537$$0240184 000212930 720_2 $$aThiran, Patrick$$edir.$$g103925$$0240373 000212930 8564_ $$uhttps://infoscience.epfl.ch/record/212930/files/EPFL_TH6762.pdf$$zn/a$$s4799994$$yn/a 000212930 909C0 $$xU10434$$0252056$$pLCAV 000212930 909CO $$pthesis-bn2018$$pDOI$$pIC$$ooai:infoscience.tind.io:212930$$qDOI2$$qGLOBAL_SET$$pthesis 000212930 917Z8 $$x108898 000212930 917Z8 $$x108898 000212930 918__ $$dEDIC2005-2015$$cISC$$aIC 000212930 919__ $$aLCAV 000212930 920__ $$b2015$$a2015-10-23 000212930 970__ $$a6762/THESES 000212930 973__ $$sPUBLISHED$$aEPFL 000212930 980__ $$aTHESIS