You are here

Wireless sensor networks presented at GOR-WS

On March 30 to April 1st, 2011, the Helmut-Schmidt-Universität, Hamburg, organized the Gemeinsamer Workshop der GOR-Arbeitsgruppen "Entscheidungstheorie und -praxis" und "Wirtschaftsinformatik". Marc Sevaux gave a presentation on the 1st of April on the Cover Scheduling Problem in Wireless Sensor Networks. You can download the presentation here.

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.

Several objectives are usually aimed in WSN. The most two important are minimizing the cover breach under bandwidth constraint (MCBB) or its dual problem maximize the network lifetime under bandwidth constraint (MNLB). Both problems are very efficiently solved in a previous framework based on column generation. Sensors are gathered into a number of subsets (not necessarily disjoint) such that sensors in each subset cover 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.

The output of the previous framework is the design of the covers and the time these covers should be used to satisfy one of the two objectives. Once the covers are determined, another problem appears and it consists in scheduling these covers. Most the time, this schedule part is left unanswered since producing the covers is much more important and difficult than scheduling them. While trying to solve the scheduling problem we observed that some of the targets where not covered for quite a significant time.

Our current work will describe the wireless sensor network cover scheduling problem (WSN-CSP), a non-linear mathematical model, a MILP model and a heuristic (CSH) that solves this problem. To improve the quality of the solutions, we also propose a genetic algorithm (CSGA). Both approaches will be tested on a large set of instances. Moreover, some complexity results and theorical properties are also given.

Page tag: