Ajaz Ahmed Khan

2016 International Conference on Computation of Power, Energy Information and Communication (ICCPEIC) Optimization of delay of data delivery in Wireless Sensor Network using Genetic Algorithm Mrs. Himani Agrawal Ajaz Ahmed Khan Electronics and communication department SSGI FET Bhilai, India- Electronics and communication department SSG! FET Bhilai, India Abstract� Wireless sensor networks (WSN), are based on low cost devices and sensors that are able to obtain information from their environment, process locally, and communicate via wireless links to a central coordinating node, i.e. base station. Earlier static sinks were used to collect information from sensor nodes and deliver it to the base station for further processing, but using static sink causes an increase in energy consumption in sensor nodes. To solve this problem, mobile sinks are now used. However, it solves the energy consumption problem, but introduces a new problem of delay in called delivery latency data delivery to the base station problem. This delivery latency problem is described as the time movable sink take to collect data from each sensor node and deliver it to the base station in a single cycle. In this paper, we have formulated delivery latency problem as travelling salesman problem, minimized delivery latency of movable sink using genetic algorithm by finding the 'best chromosome' among the available population. Keywords- Wireless sensor network, static sink, movable sink, base station, travelling salesman problem, genetic algorithm, chromosome I. INTRODUCTION Lately, Wireless Sensor Networks are used in almost every field and have various military, environmental, medical, home and commercial applications [8]. Wireless Sensor Networks consists of several hundreds and thousands of sensors which convert environmental information into electrical signals which are then processed by special units present in a sensor node. Sensor nodes consist of sensors, memory, microcontrollers which are used to perform a specific task and battery is used to provide energy to the sensors. Sinks are used to collect information from the sensor nodes and transmit it to the Base Station. In Wireless sensor network using static sink, the continuous transfer of data from sensor to static sink causes depletion of energy in sensor nodes, thus resulting in hot spot problem [1]. Even if there is no data available in sensor nodes, then also the sensor nodes deplete energy due to the presence of a static sink between all the sensor nodes, which results in shortening the lifetime of the sensors. Thus to solve the hotspot problem, use of mobile or movable sink came into reality. This mobile sink solves the hot spot problem, however, it introduces a new problem of delay in data delivery to base station, so called delivery latency problem. It is defined as the time taken by a mobile sink in a single round to visit to each node of a sensor network, collect information from them and deliver it to the base station [1,2]. The significant reason behind the delivery latency is the immense visiting time taken by the movable sink in collecting data from sensor and delivering it to the base station. To minimize this delivery latency problem, the path of the mobile sink should be selected in such a manner, that it has to travel the least possible distance meanwhile it also visits each and every node of the network. In this paper our main goal is to reduce the delivery latency of a mobile sink in a wireless sensor network having fixed sensor nodes located randomly on a plane. For simplification, we assume that the movable sink visits each node once in a single round, i.e. no node is visited more than once. Here we can relate the delivery latency problem with travelling salesman problem since both of them have the same limitations. In travelling salesman problem, a salesman has to deliver its products in 'N' number of cities, and finishes where he was at first, following a shortest path to minimize the travelling expenses and also save its time. Similarly, in delivery latency problem, a movable sink has to visit each node in a single round, collects information from them and deliver it to the base station. The larger is the route followed by the movable sink, more is the delivery latency, which is undesired. Our main is to minimize the travel route of movable sink, to minimize the delivery latency. We have formulated delivery latency problem as travelling salesman problem where our mobile sink has the same task as that of the salesman in a Travelling Salesman Problem i.e. to follow the shortest path in visiting each node and return to the initial node where it has started. We have solved the Travelling Salesman problem using Genetic Algorithm. In Genetic Algorithm, the best solution is found by mutating and cross over of a population size. The popUlation consists of chromosomes and genes where chromosome is a threaded or string like structure and genes are the part of chromosomes. The 'best solution' or 'best chromosome' shows a chromosome formed by all genes combined together and also forming the shortest thread. The smaller is the thread, the best chromosome it is. All genes must be joined together with one thread only, if any genes is not a part of thread than it is an invalid chromosome. We will carry on the search for best chromosome until we find an optimum solution. The smallest the chromosome, the least is the -/16/$31.00 m016 IEEE 159 Ajaz Ahmed Khan et at: Optimization of delay of data delivery in Wireless Sensor Network using Genetic Algorithm path and finally covering that path will reduce the delivery latency of a movable sink. How the genes are connected in a chromosome is similar to, how the path of sink will be to collect data in a single round. So, in our paper we have to fmd the best chromosome. II. RELATED WORKS Recently, several works in the field of wireless sensor networks have shown that Wireless sensor network with mobile sink is significantly increasing the lifetime of wireless sensor network by reducing the energy consumption of sensors. In [3], Yanzhong et al. proposed a self-directed moving strategy to take the benefit of movement of mobile sink to reduce energy consumption and increase the sensor lifetime. The authors have also compared the result of network lifetime with stationary strategy and moving strategy. In [4], Messaoud Doudou et al. Proposed a Duo-Mac wake up medium access control protocol to achieve energy-time constrained data delivery, and conserves energy with minimum delay by suitably changing to a low duty cycle state from high duty cycle state or a high duty cycle state from low duty cycle state as per traffic in the sensor network. M.Borghini et al. take up a simple model of wireless sensor network where the data flow path does not change over time, multiple path routing is allowed and no data collection takes place. By means of Linear Programming optimization, authors had shown that consumption of energy at all nodes can be equalized perfectly so as to increase the lifetime of the network. Yu Wang et al. proposed an energy-efficient and delay tolerant algorithm to minimize energy consumption and delay latency in the wireless sensor network. Ronghua Xu et al. proposed a structured method to solve the delivery latency problem. First, the convex hull structure is utilized to determine a sequential order to visit nodes, then the path intervals are settled with speed control plans and lastly, the number of rounds in the path is minimized through global optimization. Huang Lee et al. multi-parent wake-up scheduling technique to provide bidirectional optimized end-to-end latency while minimizing the battery powered sensor lifetime. III. and of identical radius. The mobile sink will visit at the center to collect data from sensors, however the mobile sink can collect data within the communication range of sensors. Since the signal strength is strong near the center and reduces as we move away from the sensor so we have considered our mobile sink will move to the center to collect data as shown in fig 1. In fig.1 we have assumed five sensors present at point sl, s2, s3, s4 and s5, each having the same communication range. The line segments 'a' shows the distance between sensor sl and s2, 'b' shows the distance between s2 and s3, 'c' shows the distance between s3 and s5, 'd' shows the distance between s5 and s4, 'e' shows the distance between s4 and s1. Now, our approach to reduce the delivery latency problem is to find the shortest path between all sensor nodes. In Fig.1 we have shown the travel route of movable sink by line segment 'abcde', however, it is not necessary that it is the shortest route. Fig.1 A simple example of system Architecture There can be various possible travel routes mobile sink can follow, but we have to avoid the redundant path and follow the shortest path covering all sensor nodes in a single cycle. In Fig. 2 we have shown the other travel route for a mobile sink: PROBLEM FORMULA nON The first problem is that how the mobile sink would know the exact position of each sensor so as to collect data from each sensor in the network. The next problem is, in which order the movable sink is going to visit each sensor to collect the information. There is also possibility of failure of sensors in a wireless sensor network, but in our paper, we are going to assume that there is no such failures of sensor in the network. As there is no priority to any sensors we will assume that the movable sink will collect data in a random walk such as [5] and the position of each sensor is known to us through the Global Positioning system. IV. SYSTEM ARCHITECTURE In this paper, we have considered a Wireless Sensor Network using Movable Sink. We have supposed that each sensor has a communication range circular in shape Fig. 2 An illustration of redundant travel route of movable sink In Fig.2 there are two possibilities for mobile sink to visit all nodes, first one is the line segment 'abegh' and another line segment is 'abcdfgh'. From fig.2, it is clear that line segment 'abcdfgh' is the longest one and the line segment 'abegh' is shortest one. So, the movable sink must try to avoid the longest and the redundant path as the line segment 'cdg' can be covered by line segment 'e' only. Another alternative for a movable sink is to collect data at the edge of the communication range of each sensor as shown in Fig.3. This will certainly reduce the travel route if compared to the route followed by movable sink, in Fig.1 and Fig.2. Since the signal strength of the sensor is weak at the edge of the communication range and strong near the sensor [9], so the movable sink will take more time at the edge if it will not properly get the signal from -/16/$31.00 m016 IEEE 160 2016 International Conference on Computation of Power, Energy Information and Communication (ICCPEIC) the respective sensors. There is also possibility of data loss if we consider the mobile sink to collect the data from the edge of the communication range of sensors using the data collection protocol [7]. We have come to two conclusions now in following the path shown in Fig.3 (1) movable sink will take more time to collect the information at the edge of communication range of the sensor as the signal strength is weak at the edge (2) data loss can also occur. So in our paper, we are not going to consider the movable sink to collect data at the edge of the communication range of sensor, instead we will consider the sink to move to the sensor i.e. center of communication range sl, s2, s3, s4 and s5. work. So there are certain kind of problems, where specialized techniques will be superior to GA (genetic algorithm) and there are other problems, where getting derivatives and conjugates is difficult, for those classes of problem GA can be applied. Fig.3 Travel route of Movable Sink to collect data from the edge of the sensors. '0' is the origin point of where the sink starts its data gathering cycle and will return to the same after collecting data from each sensor. Point 0, cl, c2, c3, c4 are the points on the edge of the communication range of sensor sl, s2, s3, s4 and s5 respectively where the sink will visit to collect data. v. GENETIC ALGORITHM A Genetic algorithm is a class of algorithm which imitate the process of calculation from the biological system and try to develop computing based on it. It is based on the "survival of fittest contest" which is basically the Darwinian theory, i.e. only the best among the generation will survive. For example: average age in our country before independence was around 40's while now it is around 68 so we can say the successive generations are becoming better and better. Earlier many of the diseases were not known so they cannot be cured, however, as time goes on medical researchers have progressed rapidly. Most of the diseases now are known to us, even our body parts like kidney, eyes, ear, legs, etc., can be replaced. This leads to increase in average life and thus we can say the successive generations are becoming smarter and better. The major reason behind the success of a genetic algorithm is "robustness. For a continuous two variable problem, where it is continuous differentiable, conjugate gradient will work very fast and will beat genetic algorithm, but at the same time if we apply the conjugate gradient of a function which has got local minima, local optima and oscillating then the conjugate gradient will not Fig.4 Flow Chart of Genetic algorithm Using Travelling Salesman Problem, if we want to fmd the shortest path, then for 'N' number of cities there is (NI)! possiblities i.e. for 5 cities, there are 24 different paths, for 9 cities, there are 40320 different paths and for 11 cities number of paths drastically increases to-. It is very difficult to find optimal solutions for a large number of cities using Travelling salesman Problem however, genetic algorithm is a good option to fmd optimum solutions for a large number of cities. Genetic Algorithm is an algorithm which uses biology terms known as 'chromosomes' and 'genes' to find the optimum solution. In Biology, chromosomes are usually threaded or string like structure present in the nucleus of a cell and genes is a part of chromosomes which holds the appearance of characteristics of parents. In our paper, we have assumed genes as the locations (nodes) of WSN which must be visited by the movable sink and chromosomes are the group of those locations. The dimensions of the chromosomes is the total nodes visited by the movable sink and to have a justifiable chromosomes all locations (nodes) must be visited strictly once only and return to the initial position. -/16/$31.00 m016 IEEE 161 Ajaz Ahmed Khan et at: Optimization of delay of data delivery in Wireless Sensor Network using Genetic Algorithm In Fig.5 five locations A,B,C,D, E and the distance between each location (nodes) is also shown, now our concern is to find the optimum path among each location while visiting each location only once. Based on the assumptions we will generate an initial population of chromosomes by calculating the total distance from the initial position to the end position i.e. initial position itself as shown in Fig.5 path. In our above discussions, it has been strictly mentioned that only those chromosomes covering all genes in a single cycle will be taken only, while others will be considered invalid as shown in Fig.6 andFig.7. The Chromosome in Fig.S is not invalid, but due to cross lines it will not provide the best solution. Fig.8 Chromosome ADCBEA with cross lines Fig.S An illustration of position of genes (Nodes) and the distance between each gene (Node) Assuming , A' as initial position some of the valid chromosomes from Fig.5 are ABCDEA, AEDCBA, ADCBEA etc. each having distance equal to SO while one of the invalid chromosomes is ABCBDEA having distance equal to 140 as shown in Fig.6. Based on the principle of genetic algorithm our approach to fmd the shortest path based will be in the following ways (l)Generate an initial population of chromosomes. (2) Select the valid chromosomes only.(3) Avoid chromosomes having cross lines. (4) Select those chromosomes having the shortest path.Using the above approach we are first going to solve the travelling Salesman problem for 5 cities. In Fig. 9 a Salesman has to visit and deliver its products in five cities and return to the exact initial position from where he has started his journey. Here in our paper , we have assumed that the salesman will start from 'V' and visit each node following the shortest path to minimize the cost, time and return to 'V' again. Fig.6 Invalid chromosome ABCBDEA During reproduction, crossover and mutation will give a better chromosome having least path, but it will definitely create invalid chromosome AEDCDA that visit the same node once or more as shown in Fig.7 Fig.9 Five cities V, W,X, Y,Z and distance between them. Fig.7 Invalid chromosome AEDCDA having distance = 50 During reproduction, due to crossover chromosomes like AEDCDA can be created to get the optimum value or least distance path creating an invalid chromosome. From Fig.7 it is clear that the distance is minimized from SO to 50, but to get optimum value an invalid chromosome has been generated. In Genetic Algorithm, there must be a number of crossovers and some mutations in order to get optimum value. In Fig.S, the chromosome ADCBEA consists of cross line which is not the optimum path and so we need to avoid those crossed lines in determining the shortest From above Fig.9, some of possible chromosomes, which can be generated are 'VWXYZV', 'VYZXWV','VWXZYV', 'VWZYXV" and so on. Among the following generated chromosomes we have to discard the invalid chromosomes and select the best one. Chromosomes, which are invalid has been already depicted in Fig.6 and Fig.7. Chromosomes having cross lines should also be discarded. Now, after all the possible solutions the best valid chromosome "VYWZXV" is depicted in Fig. 10 and the distance taken to cover all those locations in one cycle is '30' only. From Fig.10, it is clear that there is no repetition of locations and cross lines in the chromosomes and each location is visited once. There are no cross lines and one must not be confused in thinking that 'VX' is forming cross lines with 'WY' or 'WZ'. Cross lines can be formed only between 'WZ' and 'XV' in Fig.10. -/16/$31.00 m016 IEEE 162 2016 International Conference on Computation of Power, Energy Information and Communication (ICCPEIC) Fig.IO showing the best chromosomes among the population size The same approach we have used to find out the best chromosome to minimize the delivery latency using Genetic Algorithm for 50 genes is located at random position later in the RESULT section. VI. RESULT First of all we have depicted 50 genes in a plane randomly placed, as shown in Fig. I I. Fig.13 Distance Matrix VII. CONCLUSIONS In our paper, we have taken 'genes' as sensors and when all of them connected together, they form a threaded like structure called 'chromosome'. When all the genes are connected together with the smallest thread containing all genes, is considered as the 'best chromosome'. After each iteration, the best chromosome is having the shortest distance, is accepted and the chromosome having a large distance, is rejected. The best chromosome has the shortest distance as it connects all the genes, thus minimizing the distance and results in minimizing the delay in data delivery to the base station. REFERENCES Fig.11 Genes randomly placed on the plane We have connected each genes together to form a chromosome in each iteration, after each iteration if a better solution is obtained, then it is taken as the best solution as shown in Fig. I2 and then further proceeded while the poor solution is discarded. In this way we will proceed to find the chromosome having best solution, i.e. the shortest path, hence results in minimizing the delivery latency. Fig.12 Best Chromosome with shortest path between all genes [I] C. Tunca, S. Isik, M. Donmez, C. Ersoy, Distributed mobile sink routing for wireless sensor networks: A survey, IEEE Commun. Surv. Tutor. 16 (2) (2014) pp.- 877-897. [2] M. Zhao, M. Ma, Y. Yang, Efficient data gathering with mobile collectors and space-division mUltiple access technique in wireless sensor networks, IEEE Trans. Comput. 60 (3) -. [3] Yanzhong Bi" Limin Sun, Jian Ma, Na Li, Imran Ali Khan, and Canfeng Chen, HUMS: An Autonomous Moving Strategy for Mobile Sinks in Data-Gathering Sensor Networks EURASIP Journal onWireless Communications and Networking Volume 2007, ArticleTO 64574, IS pages. [4] Messaoud Doudou, Mohammad Alaei, Djamel Djenouri, Jos'e M, Barcelo-Ordinas, Nadjib Badache, Duo-MAC: Energy and Time Constrained Data Delivery MAC Protocol in Wireless Sensor Networks IEEE 2013 [5] R. Shah, S. Roy, S. Jain, W, Brunette, Data mules: modeling a three-tier architecture for sparse sensor networks, in: 2003 IEEE International Workshop on Sensor Network Protocols and Applications, May 2003, pp. 30-41, [6] L. Xu, Z. Deng, W. Ren, H. Wang, A location algorithm integrating GPS and WSN in pervasive computing, in: Third International Conference on Pervasive Computing and Applications, 2008, Oct. 2008, pp. 461-466. [7] Mario de Francesco and Sajal K Das, Data Collection in Wireless Sensor Networks with Mobile Elements: A Survey, ACM Journal [8] Ajaz Ahmed Khan , Mrs Himani Agrawal, A Survey Paper on Applications and Challenges in Wireless Sensor Network, International Journal ofTnnovative Research in Science, Engineering and Technology Vol. 5, Issue I, Januray 2016, pp607-614, [9] Jerry Zhao, Ramesh Govindan, Understanding Packet Delivery Performance In Dense Wireless Sensor Networks, SenSys'03, November 5.7, 2003, Los Angeles, California, USA [10] T. Gao, D. Greenspan, M, Welsh, R.R. Juang, "A Aim, Vital signs monitoring and patient tracking over a wireless network", Proceedings of the 27th IEEE EMBS Annual International Conference. -/16/$31.00 ©2016 IEEE 163 Ajaz Ahmed Khan et at: Optimization of delay of data delivery in Wireless Sensor Network using Genetic Algorithm -/16/$31.00 m016 IEEE 164