Research On Real-Time And Energy-Efficient Routing And Task Allocation Problems In Wireless Sensor And Actor Networks

Wireless sensor and actor networks, or WSANs, greatly enhance the existing wireless sensor network architecture by introducing powerful and even mobile actors. The actors work with the sensors, but can perform much richer application-specific actions. There are many potential applications of WSANs, such as battlefield surveillance, nuclear, biological and chemical attack detection, industrial control, home automation and environmental monitoring.To act responsively, first, data must be forwarded to the actors in time; then, the energy consumption of sensors must be considered, so as to prolong the network lifetime; furthermore, for there are many actors in the networks, task assignment problem between the actors must be solved. This thesis focuses on the questions of the balance between real-time and energy consumption in the processing of data collection, and task allocation.First, this thesis aims at the real-time requirement of WSANs applications and the low-power sensors, and studies a HBMECP (Hop-Bounded and Minimum Energy Cost Path) problem. Through limiting the number of hops from source nodes to actors, it hopes to reduce the total energy consumption in the network while guaranteeing that data collection still meets the real-time requirement simultaneously. The HBMECP problem is formulated as an integer linear programming (ILP). Through analyzing the model of energy consumption, the optimal number of hops under the ideal condition is inferred when the total energy consumption in a path can be minimized, and only when the distance of each hop is equal, the total energy consumption in the path reaches minimum. The thesis proposes a distributed approximate algorithm of the HBMECP problem. Based on the optimal number of hops and the given number of hops, each source node determines the number of hops respectively. Simultaneously the geographical routing algorithm is revised to ensure that the distance of each hop is equal as far as possible, so it achieves the goal of decreasing the total energy consumption while guaranteeing the real-time requirement of data collection. Theoretical analysis and extensive simulations demonstrate that, regardless of the single-actor model or multi-actor model, the proposed algorithm can effectively reach the balance between the real-time requirement of data collection and the total energy consumption of the network with trivial expenses, and adapt to the case of mobile actors.This thesis then considers the question that the sensors near to actors consume energy quickly, and studies the CBMMH (Capacity-Bounded and MIN-MAX Hops) problem. By setting the capacity constraint of the sensors, it can limit the number of the retransmitting packets greatly for some event, and reduce the maximal energy consumption of single sensor, and prolong the network lifetime. Meanwhile it adopts the minimal number of hops to retransmit data packets from the source nodes to the actors, and guarantees the real-time request of data collection. Then the CBMMH problem is formulated as a multi-objective programming, and two kinds of approximate algorithms of the CBMMH problem are proposed: GCBMMH and DCBMMH. Simulations show that, GCBMMH and DCBMMH can effectively reach the balance between the real-time requirement of data collection and the maximal energy consumption of single sensor, thus achieve the goal of extending the network lifetime; the DCBMMH algorithm doesn't need the global information.Next, this thesis discusses the task allocation problem in the wireless sensor and actor networks. First this thesis classifies the task allocation problem by different type of actors, different type of tasks and different time requirement. Then this thesis studies the Single-Actor Task (SAT) assignment with unlimited actor radius, and proposes two kinds of SAT assignment mechanism: central mechanism and distributed mechanism. Under these two mechanisms, the utility function of the time is adopted to determine the actor which the task will be assigned to when actors will finish a task. In the central assignment mechanism, the decision-making node records the information of the time and the position when actors finish the former tasks assigned, and determines the actor which the coming task will be assigned to. In the distributed assignment mechanism, there are three kinds of strategy for determining task assignment via the actor-actor coordination: auction strategy, auction strategy with starting price, idle strategy. Simulations indicate that, under the condition which the actor radius is unlimited, the central assignment algorithm has better performance in terms of the communication overhead and the delay, and when the number of actors is greater than the number of concurrent events, auction strategy with starting price and idle strategy in the distributed assignment mechanism can obtain a good performance too.This thesis next studies the SAT assignment mechanism under the condition of limited actor radius, and proposes two kinds of central SAT assignment mechanisms: semi-automated and automated. In the central mechanism, there are no sensor-actor coordination and actor-actor coordination. While in the distributed mechanism, there exists the sensor-actor coordination. Because the radius of the actors is limited, the decision-making node sends the task command to the selected actor via the sensors, so it must know the approximate position of the actor. Therefore, this thesis proposes an algorithm forecasting the position of the selected actor in the decision-making node, with the information of the time and the position when the actor finishes the tasks assigned before. Simulations show that the forecasting algorithm has a high precision, and that Semi-automated assignment mechanism which has a low initialization communication overhead has a lower delay under the condition of the small number of concurrent events, and that the automated assignment mechanism has a better performance at the delay and the number of the finished tasks when the number of concurrent event is greater.Finally this thesis studies the Multi-Actor Task (MAT) assignment mechanism, and proposes the problem of actors' selection under the condition of satisfying the time-constraint of tasks. The goal of the problem is to minimize the total energy consumption of the actors while at the same time balancing the energy consumption among the actors. The thesis formulates the problem as Mix Integer Non-Linear Program (MINLP), and proposes two kinds of MAT assignment mechanisms: non-preemption and preemption. Under the assignment mechanisms, decision-making node determines the actors for responding to current task according to known information. In the non-preemption mechanism, the assigned task isn't deferred or interrupted, however it may be interrupted by a task with higher priority in the preemption mechanism. Simulations show that for the above algorithms it has higher task success rate in the circumstance of idle actors moving to own region than in the circumstance of idle actors having no motion, and that the task success rate of the mechanism for only idle actors participating in task assignment is lower than either of the non-preemption and preemption mechanisms', and that for the high-priority task preemption mechanism than non-preemption mechanism has higher success rate, at the price of reducing the success rate of low-priority task and increasing energy consumption.