No description available.

The allocation of resources to tasks in a computationally efficient manner is a key problem in computer science. One important application domain for solutions to this class of problem is the allocation of sensing resources for environmental monitoring, surveillance, or similar sensing tasks. Within this domain, however, the complexity of the problem is compounded by a number of factors: new tasks may arrive at any time, resources may be shared between tasks under some conditions, tasks may be composed of inter-dependent sub-tasks, and tasks may compete for sensor resources. These factors combined with the dynamic nature of the topology of sensor networks (e.g. sensors may move out of range or become damaged) mean that it is extremely difficult or impossible to have a solution using existing techniques. In this thesis, we propose an efficient, agent-based solution (FAST for Flexible Allocation for Sensing Tasks) to this complex dynamic problem. The sensing resources in FAST can be either static or mobile or a mixture of both. Particularly, each resource is managed by a task leader agent (i.e. the actual sensor that is closest to the task central point). The problem is then modelled as a coordination problem where the task agents employ a novel multi-round Knapsack-based algorithm (GAP-E) to obtain a solution. If there are dependencies between sub-tasks, such relationships are solved prior to the actual allocation. At execution time, if there is any environment change that affects the task sensing type requirements, the previously determined sensor types for tasks are revised. When applicable, the agents are cooperative through exchanging and sharing resources to maximise their profits. In addition, FAST addresses the situation where sensor resource sharing is not possible and there is no incentive for sensor resources to be exchanged. In such situations, an additional post-process step underpinned by mechanism for exchanging resources through negotiation were introduced. Through those mechanisms, agents may, in a decentralized manner, decide the means to deliver on a sensing task given local conditions, and to alleviate the impact of task arrival time on the quality of the global solution. Via empirical evaluation, these steps significantly improved the number of sensing tasks that can be successfully completed with only a minor impact on execution time.

Orientador: Claudia Maria Bauzer Medeiros / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T23:06:49Z (GMT). No. of bitstreams: 1 Koga_IvoKenji_D.pdf: 2109870 bytes, checksum: 7ac5400b2e71be3e15b3bdf5504e3adf (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The complete abstract is available with the full electronic document. / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Data Stream Management Systems (DSMSs) provide support for continuous query evaluation over data streams. Data streams provide processing challenges due to their unbounded nature and varying characteristics, such as rate and density fluctuations. DSMSs need to adapt stream processing to these changes within certain constraints, such as available computational resources and minimum latency requirements in producing results. The proposed research develops an inter-operator feedback framework, where opportunities for run-time adaptation of stream processing are expressed in terms of descriptions of substreams and actions applicable to the substreams, called feedback punctuations. Both the discovery of adaptation opportunities and the exploitation of these opportunities are performed in the query operators. DSMSs are also concerned with state management, in particular, state derived from tuple processing. The proposed research also introduces the Contracts Framework, which provides execution guarantees about state purging in continuous query evaluation for systems with and without inter-operator feedback. This research provides both theoretical and design contributions. The research also includes an implementation and evaluation of the feedback techniques in the NiagaraST DSMS, and a reference implementation of the Contracts Framework.