Adaptive Data Aggregation based on Multi-Objective Ant Colony Optimization in Wireless Sensor Networks

Adaptive Data Aggregation based on Multi-Objective Ant Colony Optimization in Wireless Sensor Networks PhD Thesis – Yao Lu

Realization
  • HES-SO Fribourg
  • Yao Lu
  • Prof. Pierre Kuonen
  • Prof. Béat Hirsbrunner
Keywords
  • Wireless Sensor Networks
  • Data Aggregation
  • Multi-objective Ant Colony Optimization
Our skills
Wireless Routing Scheme, Swarm Intelligence Algorithm, Timing Policy, Discrete-event Simulation.
Valorisation
8 international peer reviewed publications, 2 journal papers.
Partners

Our Partners:

  • University of Fribourg
Funding
  • CSC
  • HES-SO

In Wireless Sensor Networks (WSNs), a large number of sensor nodes are autonomous, distributed and self-organized, they are connecting and cooperating with each other through multi-hop wireless communication. In order to reduce the data redundancy and the communication load, in-network data aggregation is usually applied to merge the messages during the routing process. How to efficiently transport the designated sensor readings from source nodes to sink nodes by using data aggregation functions is the most important issue concerned in this thesis. A theoretical energy consumption model is created to validate the effect of data aggregation on reducing the energy dissipation, and the value ranges of key parameters are further analyzed. Four common optimization objectives in WSNs are defined through the customized functions, all of them can be trade-off through a multi-objective optimization framework. From the spatial perspective, the explorations of the optimal routing structure for different scenarios are defined as steiner tree problem and multi-commodity network design problem respectively. From the temporal perspective, the theoretical optimal waiting intervals of unslotted aggregation timer on each intermediate node are discussed.

For the scenarios with single sink node, the many-to-one version of aggregation approach is developed. Ant Colony Optimization (ACO) is naturally embedded into the routing process. Forward ants record the routing history, which is the basis of routing structure construction on the sink node. The convergence rate of exploring optimal structure is accelerated by Genetic Algorithm (GA). Backward ants traverse the current optimal tree to deposit pheromone. The routing structure can gradually converge to a sub-optimal tree, whose links have high probability to be selected as the paths by upcoming ants. The time point of transmission and aggregation is controlled by distributed aggregation timers, their waiting interval can be dynamically adjusted according to the prediction of future messages, and the sliding windows are the basis of prediction. The convergence property of ACO routing is further validated through a theoretical model. In the meantime, the benefits of adaptive timing policy are also proved through the qualitative analysis.

For the scenarios with multiple sink nodes, the many-to-many version of data aggregation approach is proposed. The routing scheme is working in a fully distributed manner. Backward ants are removed and the routing structures are not constructed on any sink node. Forward ants carry the pheromone information, and the neighbors’ information can be updated by both overhearing the neighbors’ transmissions and receiving the forward ants. Thanks to the broadcast nature of wireless communication, multicast transmissions are used to simultaneously exchange information with multiple targets. Each aggregation timer can combine not only the messages coming from different source nodes but also the messages moving towards different sink nodes. The theoretical performance differences between two versions of our approach are qualitatively compared.

In order to quantitatively testify the efficiency of our approach, we implement a periodical data collection system on the OMNeT++ simulator. MiXiM provides the layered modeling framework to realize different components of this system. In the simulations, the best parameter settings are analyzed to maximize the performance. Comparison tests select some existing aggregation approaches as the comparatives approaches, the results verify the advantages of our approach. Besides, two versions of our approach are tested in the same scenarios, their performances on different optimization objectives are carefully observed.

Publications

  • Y. Lu, I. Comsa, P. Kuonen, and B. Hirsbrunner, “Adaptive data aggregation with probabilistic routing in wireless sensor networks,” Wireless Networks, pp. 1-15, 2015.
    [Bibtex] 
    @article{Yao:2308,
Author = {Yao Lu and Ioan-Sorin Comsa and Pierre Kuonen and Beat Hirsbrunner},
Issn = {1022-0038},
Journal = {Wireless Networks},
Keywords = {Genetic algorithm},
Month = {nov},
Pages = {1-15},
Title = {Adaptive data aggregation with probabilistic routing in wireless sensor networks},
Year = {2015}}
  • Y. Lu, I. Comsa, P. Kuonen, and B. Hirsbrunner, “Probabilistic Data Aggregation Protocol Based on ACO-GA Hybrid Approach in Wireless Sensor Networks,” 8th IFIP Wireless and Mobile Networking Conference, pp. 235-238, 2015.
    [Bibtex] 
    @article{Yao:2307,
Author = {Yao Lu and Ioan-Sorin Comsa and Pierre Kuonen and Beat Hirsbrunner},
Journal = {8th IFIP Wireless and Mobile Networking Conference},
Month = {oct},
Pages = {235 - 238},
Title = {Probabilistic Data Aggregation Protocol Based on ACO-GA Hybrid Approach in Wireless Sensor Networks},
Year = {2015}}
  • [DOI] Y. Lu, I. S. Comsa, P. Kuonen, and B. Hirsbrunner, “Dynamic data aggregation protocol based on multiple objective tree in Wireless Sensor Networks,” in 2015 IEEE Tenth International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), 2015, pp. 1-7.
    [Bibtex] 
    @INPROCEEDINGS{Yao:7106965,
author={Y. Lu and I. S. Comsa and P. Kuonen and B. Hirsbrunner},
booktitle={2015 IEEE Tenth International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP)},
title={Dynamic data aggregation protocol based on multiple objective tree in Wireless Sensor Networks},
year={2015},
pages={1-7},
abstract={Data aggregation has been widely applied as efficient techniques in order to reduce the data redundancy and the communication load in Wireless Sensor Networks (WSNs). However, for dynamic scenarios, structured protocols may incur high overhead in the construction and the maintenance of the static structure. Without the explicit downstream and upstream relationship of nodes, it is also difficult to obtain high aggregation efficiency by using structure-free protocols. In order to address these aspects, we propose a semi-structured protocol based on the multi-objective tree. The routing scheme can explore the optimal structure by using the Ant Colony Optimization (ACO). Moreover, by using the prediction model for the arriving packets based on the sliding window, the adaptive timing policy can reduce the transmission delay and enhance the aggregation probability. Therefore, the packet transmission converges from both spatial and temporal points of view for the data aggregation procedure. Finally, simulation results validate the feasibility and the high efficiency of the novel protocol when compared with other existing approaches.},
keywords={ant colony optimisation;redundancy;routing protocols;trees (mathematics);wireless sensor networks;ACO;WSNs;adaptive timing policy;aggregation probability;ant colony optimization;arriving packets;communication load;data redundancy reduction;dynamic data aggregation protocol;multiple objective tree;packet transmission;prediction model;routing scheme;sliding window;static structure maintenance;structure-free protocols;structured protocols;transmission delay reduction;wireless sensor networks;Delays;Energy consumption;Protocols;Routing;Topology;Wireless sensor networks;ACO;Data Aggregation;Sliding Window;WSNs},
doi={10.1109/ISSNIP.2015.7106965},
month={April},}
  • [DOI] J. Chen, Y. Lu, I. Comsa, and P. Kuonen, “A scalability hierarchical fault tolerance strategy: Community Fault Tolerance,” in 2014 20th International Conference on Automation and Computing, 2014, pp. 212-217.
    [Bibtex] 
    @INPROCEEDINGS{chen:6935488,
author={J. Chen and Y. Lu and I. Comsa and P. Kuonen},
booktitle={2014 20th International Conference on Automation and Computing},
title={A scalability hierarchical fault tolerance strategy: Community Fault Tolerance},
year={2014},
pages={212-217},
abstract={Most of hierarchical fault tolerance strategies did not pay much attention to scalability of fault tolerance. In distributed system, scalability is a very important feature. To tolerant failures when the scale of the system changing is a normal and important scenario. Especially in nowadays, almost all the cloud computing companies provide their computing services elastically. To add extra devices or remove devices in order to provide different services happens all the time. In such a scenario, it is very important that the fault tolerance strategy is scalable. In this paper, we introduce dynamic programming thoughts to build hierarchical regions as communities for fault tolerance strategy and apply different strategies based on communities instead of a single process. We call this fault tolerance strategy as Community Fault Tolerance. It cannot only reduce the memory overload by eliminating the number of records of messages inside the community region, but also provides a good characteristic of scalability. The scalability property of our strategy makes it handle with the scenario of adding devices or removing devices in the distributed system easily.},
keywords={cloud computing;dynamic programming;fault tolerant computing;cloud computing;community fault tolerance;distributed system;dynamic programming;memory overload reduction;scalability hierarchical fault tolerance strategy;Checkpointing;Communities;Dynamic programming;Fault tolerance;Fault tolerant systems;Parallel processing;Scalability;distributed system;dynamic programming;hierarchical fault tolerance;scalability},
doi={10.1109/IConAC.2014.6935488},
month={Sept},}
  • [DOI] I. S. Comşa, M. Aydin, S. Zhang, P. Kuonen, J. F. Wagen, and Y. Lu, “Scheduling policies based on dynamic throughput and fairness tradeoff control in LTE-A networks,” in 39th Annual IEEE Conference on Local Computer Networks, 2014, pp. 418-421.
    [Bibtex] 
    @INPROCEEDINGS{comsa:6925806,
author={I. S. Comşa and M. Aydin and S. Zhang and P. Kuonen and J. F. Wagen and Y. Lu},
booktitle={39th Annual IEEE Conference on Local Computer Networks},
title={Scheduling policies based on dynamic throughput and fairness tradeoff control in LTE-A networks},
year={2014},
pages={418-421},
abstract={In LTE-A cellular networks there is a fundamental trade-off between the cell throughput and fairness levels for preselected users which are sharing the same amount of resources at one transmission time interval (TTI). The static parameterization of the Generalized Proportional Fair (GPF) scheduling rule is not able to maintain a satisfactory level of fairness at each TTI when a very dynamic radio environment is considered. The novelty of the current paper aims to find the optimal policy of GPF parameters in order to respect the fairness criterion. From sustainability reasons, the multi-layer perceptron neural network (MLPNN) is used to map at each TTI the continuous and multidimensional scheduler state into a desired GPF parameter. The MLPNN non-linear function is trained TTI-by-TTI based on the interaction between LTE scheduler and the proposed intelligent controller. The interaction is modeled by using the reinforcement learning (RL) principle in which the LTE scheduler behavior is modeled based on the Markov Decision Process (MDP) property. The continuous actor-critic learning automata (CACLA) RL algorithm is proposed to select at each TTI the continuous and optimal GPF parameter for a given MDP problem. The results indicate that CACLA enhances the convergence speed to the optimal fairness condition when compared with other existing methods by minimizing in the same time the number of TTIs when the scheduler is declared unfair.},
keywords={Long Term Evolution;Markov processes;cellular radio;convergence;intelligent control;learning (artificial intelligence);learning automata;multilayer perceptrons;nonlinear functions;scheduling;CACLA RL algorithm;GPF parameters optimal policy;GPF scheduling rule;LTE scheduler behavior;LTE-A cellular network;MDP;MLPNN nonlinear function;Markov decision process;TTI;continuous actor-critic learning automata;convergence speed;dynamic cell throughput;dynamic radio environment;fairness tradeoff control;generalized proportional fair;intelligent controller;multidimensional scheduler state;multilayer perceptron neural network;optimal fairness condition;reinforcement learning principle;scheduling policy;transmission time interval;Approximation algorithms;Dynamic scheduling;Heuristic algorithms;Linear programming;Optimization;Telecommunication traffic;Throughput;CACLA;CQI;LTE-A;MDP;MLPNN;RL;TTI;fairness;policy;scheduling rule;throughput},
doi={10.1109/LCN.2014.6925806},
ISSN={0742-1303},
month={Sept},}
  • Y. Lu, I. Comsa, P. Kuonen, and B. Hirsbrunner, “Construction of Data Aggregation Tree for Multi-objectives in Wireless Sensor Networks through Jump Particle Swarm Optimization,” Procedia Computer Science, p. 73–82, 2014.
    [Bibtex] 
    @article{Yao:2309,
Author = {Yao Lu and Ioan-Sorin Comsa and Pierre Kuonen and Beat Hirsbrunner},
Journal = {Procedia Computer Science},
Keywords = {PSO},
Month = {dec},
Pages = {73--82},
Title = {Construction of Data Aggregation Tree for Multi-objectives  in Wireless Sensor Networks through Jump Particle Swarm Optimization},
Year = {2014}}
  • Y. Lu, J. Chen, I. Comsa, and P. Kuonen, “Backup Path with Energy Prediction based on Energy-Aware Spanning Tree in Wireless Sensor Networks,” International Conference on Cyber-enabled distributed computing and knowledge discovery (CyberC), 2013.
    [Bibtex] 
    @article{Yao:1494,
Author = {Yao Lu and Jianping Chen and Ioan Comsa and Pierre Kuonen},
Journal = {International Conference on Cyber-enabled distributed computing and knowledge discovery (CyberC)},
Month = {oct},
Title = {Backup Path with Energy Prediction based on Energy-Aware Spanning Tree in Wireless Sensor Networks},
Year = {2013}}