Abstract: Wireless Sensor Networks (WSN) have gained widespread popularity in recent years in the industry because of the many unique advantages they offer over conventional networks such as robustness, ability to cover wide and hard-to-reach areas, mobility of nodes and dynamic network topology among others. One of the most important areas of the application of WSNs is the execution of complex computational tasks. Due to the energy and resource constraints of a single node in the WSN these tasks often require collaborative in-network processing among multiple heterogeneous nodes. Owing to the absence of a fixed infrastructure, WSNs are forced to operate solely on limited amounts of battery capacity and processing power which limits their computational performance. Due to this limitation, development of task allocation optimization algorithms for WSNs is of paramount importance. Previously a Modified Binary Particle Swarm Optimization (MBPSO) algorithm had been proposed to optimize the process of allocating tasks to the nodes of a WSN. However, the approach has ignored an important constraint for the feasibility of the solutions when the nodes are heterogeneous. Moreover, the handling of the connectivity constraint has led to aggressive transition in the searching space which as a result creates a risk of missing the best solution or getting stuck in local minima in order to resolve these two issues a new constraint which dictates that the total energy required by the tasks from a node should be more than the initial energy of the node has been included in this approach has been added. Also, for meeting the connectivity constraint, instead of all the neighbor nodes of an already participating node, only one random node has been added. The simulation results of this approach on a WSN was performed which visibly improved the speed of convergence and prevented the algorithm from reaching a local-minima an improvement percentage of 8% in the fitness value. Moreover, the proposed approach was proven to always provide feasible solutions which satisfied the energy consideration of the nodes.