You are here

Seminar on WSN at HSU

Just after his arrival at HSU, Marc Sevaux was asked to participate in the seminar cycle "Computaional logistics". He has presented a common work with André Rossi and Alok Singh on "Wireless Sensor Network: new optimization tools for a better efficiency".

The use of wireless sensor networks (WSNs) has been increasing at a rapid pace in remote or hostile environments for data gathering. This includes battlefield surveillance, fire monitoring in forests, or undersea tsunami monitoring. In such environments, sensors are usually deployed in an ad hoc manner or at random when it is not possible to place them precisely. To compensate for this random deployment, a greater number of sensors are deployed than what is actually required. This also increases the fault tolerance as some targets are redundantly covered by multiple sensors. Each sensor operates on a battery that has a limited lifetime. Prolonging the network lifetime by making efficient use of available power is a key issue in the design of WSNs for remote or hostile environments as replacement of batteries is supposed to be impossible. The most commonly used technique for prolonging network lifetime takes advantage of redundancy in sensor deployment. Sensors are gathered into a number of subsets (not necessarily disjoint) such that sensors in each subset cover all the targets. Such subsets are referred to as covers. Covers are activated sequentially in a mutually exclusive manner, i.e., at any instant of time only sensors belonging to the active cover are used, whereas all other sensors are not. Using covers significantly increases network lifetime for two main reasons. First, sensors consume much more energy in an active state than in an inactive state. Second, a sensor battery has been shown to last longer if it oscillates frequently between active and inactive states.

Four versions of the sensor network scheduling problem (denoted SNSP) are presented and solved using a column generation scheme that involves a genetic algorithm for addressing the auxiliary problem (for generating columns efficiently) as well as an ILP version of the same problem, which is required for proving that no more attractive columns exist. The master problem is a linear program for scheduling the covers’ use, the covers being the columns that are generated by the auxiliary problem. The problem objective is to maximize the network lifetime, i.e., the time during which all the targets are covered by at least one active sensor.

The presentation can be downloaded here.

Page tag: