February 13, 2015  Engineering Optimization  articleeo

To appear in Engineering Optimization Vol. 00, No. 00, Month 20XX, 1–

Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks

Ali Kadhum Idrees^{a}, Karine Deschinkel^{a}^{∗}, Michel Salomon^{a} and Raphaël Couturier ^{a} aFEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte, Belfort, France;

(Received 00 Month 20XX; final version received 00 Month 20XX)

The most important problem in a Wireless Sensor Network (WSN) is to optimize the use of its limited energy provision, so that it can fulfill its monitoring task as long as possible. Among known available approaches that can be used to improve power management, lifetime coverage optimization provides activity scheduling which ensures sensing coverage while minimizing the energy cost. In this paper, we propose such an approach called Perimeter-based Coverage Optimization protocol (PeCO). It is a hybrid of centralized and distributed methods: the region of interest is first subdivided into subregions and our protocol is then distributed among sensor nodes in each subregion. The novelty of our approach lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. Extensive simulation experiments have been performed using OMNeT++, the discrete event simulator, to demonstrate that PeCO can offer longer lifetime coverage for WSNs in comparison with some other protocols.

Keywords: Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling.

1. Introduction

The continuous progress in Micro Electro-Mechanical Systems (MEMS) and wireless communication hardware has given rise to the opportunity to use large networks of tiny sensors, called Wireless Sensor Networks (WSN) ??, to fulfill monitoring tasks. A WSN consists of small low-powered sensors working together by communicating with one another through multi-hop radio communications. Each node can send the data it collects in its environment, thanks to its sensor, to the user by means of sink nodes. The features of a WSN made it suitable for a wide range of application in areas such as business, environment, health, industry, military, and so on ?. Typically, a sensor node contains three main components ?: a sensing unit able to measure physical, chemical, or biological phenomena observed in the environment; a processing unit which will process and store the collected measurements; a radio communication unit for data transmission and receiving.

The energy needed by an active sensor node to perform sensing, processing, and communication is supplied by a power supply which is a battery. This battery has a limited energy provision and it may be unsuitable or impossible to replace or recharge it in most applications. Therefore it is necessary to deploy WSN with high density in order to increase reliability and to exploit node redundancy thanks to energy-efficient activity scheduling approaches. Indeed, the overlap of sensing areas can be exploited to schedule alternatively some sensors in a low power sleep mode and thus save energy. Overall, the

∗Corresponding author. Email: karine.deschinkel@univ-fcomte.fr

main question that must be answered is: how to extend the lifetime coverage of a WSN as long as possible while ensuring a high level of coverage? These past few years many energy-efficient mechanisms have been suggested to retain energy and extend the lifetime of the WSNs ?.

This paper makes the following contributions.

(1) We have devised a framework to schedule nodes to be activated alternatively such that the network lifetime is prolonged while ensuring that a certain level of coverage is preserved. A key idea in our framework is to exploit spatial and temporal subdivision. On the one hand, the area of interest is divided into several smaller subregions and, on the other hand, the time line is divided into periods of equal length. In each subregion the sensor nodes will cooperatively choose a leader which will schedule nodes’ activities, and this grouping of sensors is similar to typical cluster architecture.

(2) We have proposed a new mathematical optimization model. Instead of trying to cover a set of specified points/targets as in most of the methods proposed in the literature, we formulate an integer program based on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. Hence, an optimal scheduling will be obtained by minimizing a weighted sum of these deviations.

(3) We have conducted extensive simulation experiments, using the discrete event simulator OMNeT++, to demonstrate the efficiency of our protocol. We have compared our PeCO protocol to two approaches found in the literature: DESK ? and GAF ?, and also to our previous work published in ? which is based on another optimization model for sensor scheduling.

The rest of the paper is organized as follows. In the next section we review some related work in the field. Section 3 is devoted to the PeCO protocol description and Section ?? focuses on the coverage model formulation which is used to schedule the activation of sensor nodes. Section ?? presents simulations results and discusses the comparison with other approaches. Finally, concluding remarks are drawn and some suggestions are given for future works in Section ??.

2. Related Literature

In this section, we summarize some related works