The Ant Algorithms And Their Applications In The Technologies Of Data Acquirement

As one of the most popular algorithms in swarm intelligence, ant colony optimi- zation has attracted more and more researchers. In the recent years, the theoretic research and the applications of the ant colony optimization have been developed rapidly and the superiority performances have been demonstrated extensively, espe- cially in solving some of the NP-hard problems and routing problems in the networks. As the dynamics of the network environments and the diversity of the network appli- cations, lots of traditional protocols are no longer suitable to some key applications, alternative approaches for the special applications are required. Ant colony optimiza- tion provides good solutions for data acquirement applications in the networks.The dissertation first summarizes the related theoretical results and applications of swarm intelligence, then introduces the anycast routing and query processing in data acquire- ment, which are the two of the key technologies in the networks. Based on them, the dissertation focuses on the research of the swarm intelligence and its applications in two of the most important data-acquirement technologies systemically and intensively–anycasting and querying for the distributed network environments. The main works are as follows:(1) Under the conditions without global network information, aiming at the NP- hard multi-constrained anycasting problem, we propose the Multiple Ant Colonies Anycast (MACA) algorithm, which can dynamically adjust the path selection accor- ding to the pheromone intensity deposited by other ants to change the local network environment and merely requiring local information. The simulation results demon- strated that the distributed MACA algorithm with positive feedback can make ants with QoS constraints select the satisfied optimum paths at higher probability, which can shorten the routing delay and improve the request reception effectively.(2) Under the conditions without node location information, aiming at the multi- constrained anycast problem in wireless sensor networks, we integrate the ant-based routing and clustering models and propose an Ant-based Reliable Multi-Constrained Anycast (ARMCA) algorithm, which introduce the ant colony optimization with positive feedback to send collected data to only one optimum sink timely, reduce the energy cost and shorten the delivery delay, considering the constraints of both the energy and delay. Meanwhile, the ARMCA integrates the ant-based clustering and proposes a self-recovery mechanism to cope with node failures including the sinks by transferring the failure state to a new stable state smoothly. The simulation results indicate that the ARMCA has better performances under the same energy and delay constraints when the network increases. As node failure occurred, the ARMCA can quickly transfer to a new stable state and ensure the reliability of data delivery.(3) Aiming at the multi-constrained anycast problem in mobile ad hoc networks with dynamic topologies, we propose an Ant-based MANET Multi-Constrained Anycast (AMMCA) algorithm, which introduce the pheromone diffusion model to intensify the links nearby the optimum paths to avoid the path break caused by node mobility. Meanwhile, AMMCA reduces the influence of path break by constructing multiple paths to balance the network load. The simulation results demonstrate that the AMMCA has better performances in data reception rate and the end-to-end routing delay when comparing it with other anycast algorithms in mobile ad hoc networks.(4) For energy constrained large-scale wireless sensor networks, how to process parallel queries for replicated data issued from multiple nodes energy-efficiently is a challenge. We propose an energy-efficient Multiple Ant Colonies Query Processing (MACQP) algorithm, which firstly performs the data random replication, then search the optimum path to one of the replicas by issuing forward ants and the search is with certain intelligence. When target replicas are found, the backward ants generated will return and perform the second replication to guide the subsequent forward ants to select the optimum path with more pheromone and get the target replicas at nearer nodes. The search paths are shortened and the energy cost is reduced by MACQP. The theoretical analysis and simulation results show that the MACQP has obvious energy superiority due to the intelligent search and dynamic replication.(5) Aiming at the real-time applications of large-scale wireless sensor networks and considering both the energy-efficiency and real-time performances, we propose an Ant-based Real-Time Query Processing (ARTQP) algorithm, in which an optimal clustering method and a ring-based storage approach are adopted to ensure events with different priority can be queried distinguishingly and the urgent ones can be detected with higher probability. When target replicas of the events are found, the backward ants generated will perform the second replication to guide the subsequent forward ants to select the optimum path with stronger pheromone intensity and get the target replicas at nearer nodes. Therefore, the average length of the paths is shortened and the average query delay is reduced significantly by ARTQP, as well as the average total energy cost. Theoretically and experimentally, the results demonstrate that not only the performance of energy-efficiency can be improved but also significant smaller query delay can be achieved by ARTQP when comparing with other existing query algorithms. Moreover, the superiority becomes more obvious when the network increases, even if the QoS constraints are more severe.