Efficient Task Allocation in WSNs using Mutant Binary Particle Swarm Optimization

Efficient Task Allocation in WSNs using Mutant Binary Particle Swarm Optimization

R. Dayana,

Assistant Professor, CSE Jeppiaar Institute of Technology,

Chennai.

Abstract Wireless Sensor Network (WSN) is an emerging technology used in many application areas such as military sensing, traffic surveillance, environment monitoring, building and structural monitoring. Design of sensor network has gained increasing importance due to their potential. Nodes in WSNs have limited resources and works in a dynamic environment without human participation. When deploying a WSN, the position of sensor nodes becomes one of the major concern. It is desirable to position sensor node in WSN to be able to provide maximum coverage with minimum energy consumption. Task allocation for WSN is an Multi Objective Optimization (MOO) problem. In task allocation it is essential to assign workload of each task to proper nodes in a efficient way. Existing task allocation algorithms in WSNs have reduce problem complexity, as only local areas are considered rather than the whole network. Existing algorithms were taken different metrics for optimization. In this proposed approach ,Mutant Binary Particle Swarm Optimization(MBPSO), energy efficient allocation to the nodes are provided with distributed algorithm, taking network parameters in multi hop wireless environment. Multiple Objective Metrics, which includes availability of sensor nodes, energy consumption, task execution time, average congestion of BSs can be used to evaluate the performance of this proposed approach. Our proposed approach also outperforms the approaches based on Genetic algorithm and existing other algorithms like PSO,BPSO.

Index Terms Genetic algorithms, Task allocation, BPSO, PSO Multi Objective Optimization (MOO).

1. INTRODUCTION

   In-network processing for wireless sensor network (WSN) is usually more energy-efcient than sending all the raw data to the end user. It can also reduce the com munication volume and improve the real-time performance of WSN . Many applications such as target localization , tracking and distributed visual surveillance innetwork processing task in such applications usually requires considerable processing power which may be beyond the capability of single node containing limited energy and resource series of computationally intense in-network processing tasks to be executed sequentially in the WSN. An in-network processing task in such applications usually requires considerable processing power which may be beyond the capability of single node containing limited energy and resource.

   Nodes in WSN not only act as independent processing elements, but are also able to collaborate with each other through direct and multi- hop communication link. So, the WSN can be taken as a parallel computing system through essential data exchange among nodes. Significant processing can be provided with the parallel computing of WSN. As a result, a computationally intense processing task can be decomposed into smaller subtasks and then executed concurrently on independent sensor nodes. the execution of each subtask in a single node would consume a certain amount of resources for computing and communication. To exploit the capabilities of WSN as a parallel computing system, an efficient mechanism is necessary to allocate each task to proper group of nodes while meeting the application requirements. Most of nodes in WSN are battery powered and have limited energy storage. The WSN is built of nodes from a few to several hundreds or even thousands, where each node is connected to one sensors. Each such sensor network node has typically several parts: a radio transceiver with an internal antenna or connection to an external antenna, a microcontroller, an electronic circuit for interfacing with the sensor and an energy source usually, a battery or an embedded form of energy harvesting.. Task allocation problem for WSN is a multi objective constrained optimization problem which has been proved to be NP hard. Tradition heuristic and stochastic heuristic have all been employed for this problem. Tasks should be allocated to sensor nodes with the consideration of energy conservation and balanced energy consumption to prolong the network lifetime

   Fig 1: WSNs node deployed in networks

2. RELATED WORK

   1. Cross-layer design:

      Cross-layer is becoming an important studying area for wireless communications. In addition, the traditional layered approach presents three main problems:

      1. Traditional layered approach cannot share different information among different layers ,which leads to each layer not having complete information. The traditional layered approach cannot guarantee the optimization of the entire network.

      2. The traditional layered approach does not have the ability to adapt to the environmental change.

      3. Because of the interference between the different users, access confliction, fading, and the change of environment in the wireless sensor networks, traditional layered approach for wired networks is not applicable to wireless networks.

         So the cross-layer can be used to make the optimal modulation to improve the transmission performance, such as data rate, energy efficiency, QoS (Quality of service), etc.. Sensor nodes can be imagined as small computers which are extremely basic in terms of their interfaces and their components. They usually consist of a processing unit with limited computational power and limited memory, sensors or MEMS (including specific conditioning circuitry), a communication device (usually radio transceivers or alternatively optical), and a power source usually in the form of a battery. The base stations are one or more components of the WSN with much more computational, energy and communication resources. They act as a gateway between sensor nodes and the end user as they typically forward data from the WSN on to a server. Other special components in routing based networks are routers, designed to compute, calculate and distribute the routing tables.

   2. Task allocation in multihop networks:

      Emerging applications in Multihop Wireless Networks (MHWNs) require considerable processing power which often may be beyond the capability of individual nodes. Parallel processing provides a promising solution, which partitions a program into multiple small tasks and executes each task concurrently on independent nodes. However, multihop wireless communication is inevitable in such networks and it could have an adverse effect on distributed processing. In this paper, an adaptive intelligent task mapping together with a scheduling scheme based on a genetic algorithm is proposed to provide real-time guarantees. This solution enables efficient parallel processing in a way that only possible node collaborations with cost-effective communications are considered.

      Furthermore, in order to alleviate the power scarcity of MHWN, a hybrid fitness function is derived and embedded in the algorithm to extend the overall network lifetime via workload balancing among the collaborative nodes, while still

      ensuring the arbitrary application deadlines. Simulation results show significant performance improvement in various testing environments over existing mechanisms.

      Task allocation problem of WSN is a multi- objective constrained optimization problem. Many algorithms such as Genetic algorithm, Artificial Bee Colony algorithm, Particle Swarm Optimization algorithm and Binary Particle Swarm Optimization algorithm are used to allocate tasks in a wireless sensor network. All the above approaches adopt taditional heuristic methods to search for the solution step by step. However, the drawback of traditional heuristic methods is that they may be easily stuck in local optimum and have limited ability for complex problems with high solution space. So, the bio- inspired stochastic intelligent optimization algorithms are then adopted to find the global optimum with high convergence rates. Moreover, to achieve better performance, more intelligent optimization technology should be explored for the task allocation problem of WSN. MBPSO is the Mutant binary version of PSO and has the potential to solve many optimization problems of WSN.

3. MBPSO MODEL:

   In this work, due to the shortcomings encountered by BPSO, a modified version of BPSO is proposed to search for the best task allocation scheme. The problem is firstly formulated as a multi-objective constrained optimization problem. The BPSO is modified with a different transfer function and a new position updating procedure with mutation operation to achieve better performance. The particles of proposed system are encoded with binary matrices to represent potential task allocation schemes. The task workload and the connectivity are considered as constraints to ensure the accomplishment of each task and essential data exchange among selected nodes. A hybrid fitness function involving task execution time, energy consumption and network lifetime is designed to evaluate the quality of each particle. Simulation results show that the proposed approach is feasible for the task allocation problem in WSN. The proposed system-based approach also outperforms the approaches using genetic algorithm (GA) and BPSO.

   In BPSO, the probability for a binary bit changing to 1 is S(vi,d), the probability for that bit changing to 0 is 1S(vi,d). According to the updating formula of velocity, when 1<w <1 ,vi, d would become 0 and S(0)=0.5 over time, which means that the particle bits would get changed with pure randomness. So, smaller value of velocity indicates stronger exploration, even if a good solution has been found. This is unreasonable since a velocity close to 0 indicates the convergence of algorithm and the binary bits should get changed with a lower exploration. So, the BPSO has some shortcomings on the operation of binary positions. It lacks the ability for remembering already obtained high quality positions. It is hard for the BPSO to coverage to the optimal solution since the increase of randomness as the iteration goes on. Moreover, the BPSO is also proved to suffer trapping in local minima . Several

   modified versions of BPSO have been proposed in order to overcome the above problems. These modifications have been surveyed and analyzed . It is shown that they could not resolve the problem of being trapped in local minima completely; they also have fluctuating convergence speeds in dealing with diverse optimization problems. The transfer function is the most important part of the BPSO and can significantly influence the performance of the algorithm in terms of avoiding local minima and convergence rate. Moreover, compared with other forms of transfer function, the v-shaped family of transfer functions has been proved to have significant advantages. Here, a v-shaped transfer function is adopted to map the continuous velocity to binary position.

   With the above transfer function, when the velocity is close to 0, T(·)would also get close to 0. When the absolute value of velocity gets larger, the value ofT(·)would also get larger and approximate to 1.vk+1i,d is clamped in the range of[vmin,vmax ] to avoid convergence of T(vk+1i,d) to 1.Since the above transfer function is quite different from the original S(·), the updating rules for the binary positions should also get changed.

   According to the above equation, the particle position is encouraged to stay in the current position when the velocity gets close to 0.When the velocity is positive, the binary position tends to converge to 1 as the velocity gets larger. When the velocity is negative, the binary position tends to converge to 0 as the velocity gets smaller. In this case, the memory of the particle plays an important role. It can reduce the randomness of the binary positions as the iteration goes on. The convergence speed can thus be largely improved with this new position updating formula. However, with the modified position updating formula, the problem of local minima still keeps unresolved. The algorithm would easily get stuck in local optimum and has limited ability to explore the global best positions. In order to get out of this local optimum, larger movement of particle position is required. So, a mutation operation is adopted to maintain swarm diversity and reduce the probability of proposed system getting stuck in local optimum. With the mutation operation, each binary position would get changed to its opposite value with a given probability called mutation rate. For the binary position of the ith particle in the d-th dimension at thekth iteration, the mutation operation is expressed .

   Where rand() is a random number uniformly distributed in the range of [0,1]. rmu is the mutation rate which determines the probability for a bit changing to its opposite value.Every bit of a particle has the same probability rmuto

   get changed from 1 to 0 or from 0 to 1. Overall, the modification of BPSO includes a different transfer function and a new position updating procedure with mutation operation. This is a general purpose modification to overcome the shortcomings of BPSO. The poposed system has the potential to be used for solving any other optimization prob-lems after proper evaluation. The advantage of the proposed system can be summarized as follows.

   1. The convergence speed is largely improved with the presented transfer function and position updating formula.

   2. The diversity of particles is improved and the problem of local minima is avoided with the mutation operation.

   1. Node Selection

      The MBPSO algorithm uses proportional selection, the population of the next generation is determined by n independent random experiments; the probability. This process is also called roulette wheel parent selection and may be viewed as a roulette wheel where each member of the population is represented by a slice that is directly proportional to the members tness. A selection step is then a spin of the wheel, which in the long run tends to eliminate the least t population members.

      Fig.2 Encoding of the Particle

   2. Mutation

      Mutation is another important component in CGA, though it is usually conceived as a background operator. It operates independently on each individual

      Fig.3 Encoding the Mutant Value

   3. Initialization and Optimization:

      Binary representation is needed to describe each individual in thepopulation of interest. Each individual is made up of a sequence of binary bits(0 and 1). Let stringlength and popsize denote the length of the binary sequenceand the number of individuals involved in the population. Each individual usesa string codication of the form. Using MATLAB, the wholedata structure of the population is implemented by a matrix of sizepop size×(stringlength+2).

      Fig.4 Converting into Binary value

      The rst string length column contains the bits which characterise the binary modication of the real variable x. The strings are randomly generated, but a test must be made to ensure that the corresponding values belong to the function domain. The crossover and mutation operators will be applied on this string length-bit sub-string. The (stringlength+1)-th and (stringlength+2)-th columns contain the real x value, used as auxiliary information in order to check the algorithms evolution, and the corresponding f(x), which is assumed to be the tness value of the string in this case.

   4. System Design:

      The WSN is composed of a number of heterogeneous sensor nodes deployed in the monitoring area. The sensor nodes have dfferent characteristics such as processing speed, power consumption and transmission distance. The initial energy and radio characteristics are assumed to be identical. The WSN is represented by a weighted undirected graph G

      =(N,R). N ={Nj: j = 1,2,…,n} is the set of vertices corresponding to the network nodes. R is the set of edges corresponding to the direct communication link among nodes. There is no direction for the edges since all the nodes have the same maximum transmission range and the communications are bidirectional. The jth nodeNj is characterized by (vj, ej, einit). vj is the processing speed of Nj , ej is the average power consumption (J/sec), einit is the initial energy. d={d12,d23,…,dij} is the weights of edges denoting the physical distance among nodes. dij is the physical distance between Ni and Nj. When dij is smaller than the maximum transmission range, the two nodes are directly connected to each other.

      An application requires m processing tasks to be executed in the WSN. The set of tasks is expressed as M={Mi: i =1,2,…,m}.A WSN with n heterogeneous sensor nodes is

      expressed by N = {Nj: j =1,2,…,n}. For a specialized task Mi , a set of k sensor nodes Ns ={Ns1,Ns2,…,Nsk} is selected, where 1 k n.Then Mi would be decomposed into k subtasks Mi ={Mi1,Mi2,…,Mik}.

      Fig 5. Work flow diagram of MBPSO.

      The node Nsx is thus assigned with a subtask Mix, Mix

      Mi , x{1,2,…,k}. Each task in the DAG requires different workload on computation and communication. The task allocation problem have enough resource to finish the workload required by the given task Mi. Moreover, the nodes in Ns for a specialized task should be connected with each other through direct or multi-hop links to ensure data exchange among nodes. One node can execute a sequence of subtasks with proper order. However, only one subtask can be executed by a node at one time. The aim of task allocation is to find a scheme that can achieve the best overall network performance under the required constraints on task workload and connectivity. The evaluation metrics for a task allocation scheme include task execution time, total energy consumption and net-work lifetime. So, the task allocation problem is formulated as a multi-objective optimization problem with constraints. The comprehensive objective function with weights for each metric is expressed by.f(X)=W1×T+W2×E+W3×D whereT, E and Dare the total task execution time, total energy consumption and energy distribution of the WSN withW1, W2 andW3 being their weights respectively. T, E and Dare calculated with the corresponding cost functions. Since smaller values of the three metrics indicate better network performance, the goal of task allocation is to assign tasks to WSN with minimized f(X).

   5. MBPSO Algorithm

   The MBPSO system-based task allocation approach is going to run on the sink node which is assumed to be equipped with sufficient energy and resources. For an application of WSN, an optimal task allocation scheme would be generated after the execution of task allocation algorithm. Each task would then be decomposed into smaller subtasks and assigned to a selected group of sensor nodes according to the optimal scheme. The step by step implementation details are described as follows.

   Step 1: Create the DAG of tasks and the graph of WSN. Initialize the parameters for tasks and WSN. Calculate the minimal possible number of nodes for each task.

   Step 2: Initialize the parameters for MBPSO including swarm size, maximum iteration number, inertia weight, learning factors, velocity range, mutation rate and the weights on different metrics in the fitness function.

   Step 3 : Initialize the binary positions and velocities of each particle with the satisfaction of task workload and connectivity. The binary position xi,pq in xi and the real valued velocity vi,pq in Vi are firstly randomly initialized by

   Where rand() is a random number uniformly dis- tributed in [0,1]; vmaxandvminare the upper and lower bounds of the velocity. So, xi,pq is initialized with either 0 or

   1 with the same probability,vi,pq is initialized with a real

   value randomly distributed in the range of [vmin,vmax].However, the above randomly generated particle position Xi may not satisfy the constraints on task workload and connectivity. When either of the two constraints is not satisfied, the particle position would be repaired as follows number of selected nodes and relay nodes in the network, which are beneficial for meeting the requirements on both task workload and connectivity.

   For each already selected node, its neighboring nodes would be selected with a probability of 0.5, and this process will be repeatedly executed until the constraints are satisfied. This is feasible for our problem since it can largely improve the total

   Step 5 :Update the velocity and binary position of each particle to generate a new swarm.

   Step 6 : Execute the mutation operation to change the values of the binary bits with a probability of mutation rate.

   Step 7 : For the newly generated particles, evaluate the con- straints on both task workload and connectivity

   If the constraints on either task workload or connectivity is not satisfied, the corresponding particle would be repaired based on the already obtained history information. For instance, if one row of a particle does not satisfy the required constraints, it would be replaced with the corresponding row of the existing global best positionGbest. If both the constraints on task workload and connectivity are met, each task would be evenly decomposed into a set of subtasks with each subtask allocated to one node according to the binary positions of particles and go on next step.

   Step 8 : Evaluate the fitness value of the newly updated particles, and then update Pbest, i and Gbest of the swarm. For an individual particle, if the newly updated fit-ness value is

   smaller than the history local best value, the local best position Pbest,i would be replaced by its current position. For the swarm of particles, if the current fitness value is smaller than the global best one, the global best position Gbest would be replaced by the current position.

   Step 9 : When the maximum number of iterations is reached, the search is stopped and go on to step 10. Otherwise, increase the number of iteration and return to step 5.

   Step10 : Save the finally obtained global best position Gbest as the ultimate solution for the task allocation problem

4. RESULTS AND DISCUSSION

   In this work, a task allocation approach based on our proposed system is to search for the best task allocation solution for WSN. The BPSO is modified with a different transfer function and a new position updating procedure with mutation operation to achieve better optimization performance and accommodate the application requirements. The particles of our proposed system are encoded to represent the complete potential task allocation schemes. Task execution time, energy consumption and energy distribution are simultaneously considered in the fitness function to make proper tradeoff among different metrics and get the best overall performance

   A.Transfer Function

   PARAMETER	VALUES
   Iteration number	600
   Swarm Size	50
   Acceleration constant c1	2
   Acceleration constant c2	2
   Inertia Weight (max)	0.9
   Inertia Weight (min)	0.4
   Range of velocity	[-6,6]
   Mutation Rate	0.02

   Table 1: Parameter selection for transfer function

   Fig 6.Tranfer Function

   Fig 7.Performance with varying number of tasks fitness value. The task workload and connectivity of the selected nodes is ensured by taking thm as constraints for the problem. Simulation results show the feasibility of the proposed system-based approach for task allocation problem in WSN. The proposed system-based approach also outperform the approaches based on GA and BPSO in the comparative

   Fig.7.Performance with varying network size fitness value

   Fig.8. Performance with varying network size energy distribution

   Future work of the system will be to use additional WSN concerns include the external environment, routing, data aggregation, and ensuring quality of service (QoS) and security. Solutions have been developed for various types of application scenarios, but many problems still remain as open research challenges.

5. REFERENCE

1. S.Mini, Siba K. Udgata, and Samrat L. Sabat, Sensor deployment and scheduling for target coverage problem in wireless sensor networks, IEEE sensors journal, Vol.14, No.3, March 2014.

2. D.Prasad, Manik Gupta and R.B.Patel, A system for secure and energy efficient adaptive routing in wireless sensor networks, indian journal of wireless networks and communications, vol.4, no,2, Jul-Dec 2014

3. Mao Sha, Tang Hao , Zhou Lei , Ma Xuesen, An energy conservation optimization strategy for wireless sensor network node based on Q- learning, Control Conference (ASCC), 2011 8th Asian, 15-18 May 2011.

4. Zaman. N, Abdullah, A.B., Low Tan Jung, Optimization of energy usage in Wireless Sensor Network using Position Responsive Routing Protocol (PRRP), Computers & Informatics (ISCI), 2011

5. Devesh Pratap Singh,R. H. Goudar, Bhasker Pant, Energy Aware Task Allocation with Unequal Clustering in WSN, International Journal of Computer Applications, Volume 93 – Number 3, Year of Publication: 2014

6. Feng Wang, Guangiie Han, Jinfang Jiang, and Hao Qiu, A Distributed Task Allocation Strategy for Collaborative Applications in Cluster- Based Wireless Sensor Networks, International Journal of Distributed Sensor Networks

   Volume 2014 (2014), Article ID 964595,

7. N. A. B. A. Aziz, A. W. Mohammed, and M. Y. Alias, "A Wireless Sensor Network Coverage Optimization Algorithm Based on Particle Swarm Optimization and Voronoi Diagram " presented at the 2009 IEEE International Conference on Networking, Sensing and Control, 2009

8. L. Zhang, D. Li, H. Zhu, and L. Cui, "OPEN: An Optimisation Scheme of N-node Coverage in Wireless Sensor Networks," Wireless Sensor Systems, IET, vol. 2, pp. 40-51, 2012.

9. L. Chen, X. S. Qiu, Y. Yang, Z. Gao, and Z. Qu, The contract netbased task allocation algorithm for wireless sensor network, in Proc.IEEE ISCC, Jul. 2012, pp. 600604

10. S. Lee, S. Soak, S. Oh, W. Pedrycz, and M. Jeon, Modified binaryparticle swarm optimization, Progr. Natural Sci., vol. 18, no. 9,pp. 11611166, 2008.