Lifetime maximization of hop-and-delay constrained wireless sensor networks with mobile agent

Wireless Sensor Networks (WSNs) have emerged as an attractive and challenging research field. One of the main challenges in such networks lies in the constrained energy resources available to sensor nodes. Since the sensors are usually deployed in hostile environments and in large quantities, it is difficult or impossible to replace or recharge their batteries. A possible solution to save energy is to allow a mobile agent to move through the WSN to collect the data, but this approach increases the delay delivery of messages. In this work we use a communication forest, where the roots (cluster heads) of the trees are the sensors visited by the mobile agent; the other sensors send their information to the cluster heads using one or more hops. The problem is to define the cluster heads, the communication forest and the mobile agent path in order to minimize the total energy consumption within a limited delay. We introduce a Genetic Algorithm (GA) that defines the set of cluster heads using a specialized heuristic to evaluate the solutions. Results are presented for WSN with up to 80 nodes using different limits for the mobile agent path length, in order to control the delivery delay of messages. The optimality of the solutions for some instances with 20 and 30 nodes were confirmed by solving a Mixed-Integer Linear Programming formulation.