M133. Hierarchical routing protocol based on evolutionary algorithms for Wireless Sensor Networks
1. Aim
We aim to develop a hierarchical routing protocol for efficient routing of data to the base station.
2. Obiectives
A hierarchical routing protocol designed to extend the life of the network by minimizing energy consumption and latency by choosing the best nodes to become cluster-heads. Minimization is realized with a multi-objective genetic algorithm executed on a central BS and the results send to the network nodes. Simulation is done in NS-2 where there is already an implementation of Leach protocol with whose results we compare.
We propose a modular approach in the deployment of the routing protocol: the base station calculates the best solutions for cluster-head position while the nodes will run the algorithm with a small footprint to reduce energy consumption.
The protocol will have the following characteristics:
- messages with fixed length, introducing the minimum information necessary for data transmission
- each cluster-head will aggregate data.
- redundancy at the level 2 routes.
- calculate a local minimum for cluster replacement in case it runs out of energy before the end of the pre-established number of rounds. Activities will be assumed by a node which belongs to that cluster, assuring minimum impact on the network.
3. Bibliography
[1] Woo, A., Tong, T., Culler, D., E., Taming the underlying challenges of reliable multihop routing in sensor networks. SenSys 2003: 14-27 (http://www.cens.ucla.edu/sensys03/proceedings/p14-woo.pdf)
[2] Al-Karaki, J.N., Kamal, A.E. Routing Techniques in Wireless Sensor Networks: A survey, IEEE Wireless Communications, Vol. 11, No. 6. (2004), pp. 6-28. (http://www.ece.iastate.edu/~kamal/Docs/kk04.pdf)
[3] Alazzawi, L.K., Elkateeb, A.M., Ramesh, A., Aljuhar, W., Scalability Analysis for Wireless Sensor Networks Routing Protocols, Proceedings of the 22nd International Conference on Advanced Information Networking and Applications, 2008
[4] Oh, S., Kim, D., Kang, H., Jeong, H., SMSR: A Scalable Multipath Source Routing Protocol for Wireless Sensor Networks, Proceedings of the 6th International Conference on Ubiquitous Intelligence and Computing, 2009
[5] http://www.hindawi.com/journals/jcsnc/2008/481046.html
4. Organizational details
- Coordinator: conf. dr. ing. Razvan Rughinis
- Team: HURUIALĂ Petre-Cosmin
- Prerequisites: networking, algorithms, artificial intelligence
- Location: EG106b
- Schedule: 6 hours a week, two semesters
5. First semester results
Hierarchical routing protocol based on evolutionary algorithms for Wireless Sensor Networks
In this paper we propose a routing protocol based on evolutionary algorithms to enhance network life and response time in WSN. We use a coordinated approach between the BS who runs a genetic algorithm with intensive memory and CPU requirements and a routing protocol with a small footprint on the nodes.
We propose a protocol that is capable of routing data accomplishing some key constraints. For this writing we used energy consumption and low latency but they can be other with minor changes in protocol design.
Suppose we have to monitor an area against unwanted access and we need a fast and viable network or we need to monitor a forest to detect fire and we need a robust and low power consuming network. A WSN network is perfect for these scenarios and our approach offers the means to solve the problems. It can find solutions taking into account more objectives and more important can find them as if the protocol is specially designed for the job. We expect this approach to consume a larger amount of energy compared with protocols like PEGASIS but bring up benefits like speed, redundancy and so on.
We intend to compare the result of our approach with the ones provided in [1] and the ones from a simulation with a Simple Genetic Algorithm (SGA).
Because is difficult to find the best fitness function for given problem, other elements can be taken into consideration to obtain better results. We can add elements like distances between clusters and number of transmissions to prolong network life. We can also find fitness functions to solve other objectives, after all this is all that must be changed in order to adapt the protocol to other requirements.
