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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:577601 |
| Date | January 2013 |
| Creators | Le, Thao P. |
| Publisher | University of Aberdeen |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://digitool.abdn.ac.uk:80/webclient/DeliveryManager?pid=196168 |
Page generated in 0.0017 seconds