Configuration‐based approach for topological problems in the design of wireless sensor networks

• Author: Vinicius Morais,Geraldo Robson Mateus
• Published date: 01 May 2019
• DOI: http://doi.org/10.1111/itor.12615
• Date: 01 May 2019

Intl. Trans. in Op. Res. 26 (2019) 836–855

DOI: 10.1111/itor.12615

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Configuration-based approach for topological problems in the

design of wireless sensor networks

Vinicius Morais and Geraldo Robson Mateus

Departamento de Ciˆ

encia da Computac¸˜

ao, Universidade Federalde Minas Gerais, Av. Antˆ

onio Carlos 6627, Belo Horizonte

MG, 31270-010, Brazil

E-mail: vwcmorais@dcc.ufmg.br [Morais]; mateus@dcc.ufmg.br [Mateus]

Received 7 January 2018; received in revised form 26 September 2018; accepted 5 November 2018

Abstract

In this paper,we deal with two routing problemsthat integrate coverageand cardinality constraints to optimize

the wireless sensor networks lifetime.Problems based on arborescence and cycle topologies are defined on the

design of that kind of network.We propose configuration-based linear integer programmingformulations and

devise column-and-row generation (CRG) algorithms to evaluate the bounds. Computational experiments

showed that configuration-basedformulations dominate the formulations being compared and indicateCRG

as an alternative to solve related location–allocation problems in transportation and telecommunication

networks.

Keywords:wireless sensor network; configuration-based formulations; column-and-row generationalgorithm

1. Introduction

Monitoring events, physical or environmental phenomena in different scenarios, such as military

tactics, security, industry, and health, involve several activities such as sensing, processing, and

transmission of data related to temperature, humidity, pressure of gases or even liquids, movement,

and so on (Arampatzis et al., 2005; Kuorilehto et al., 2005; Alemdar and Ersoy, 2010; Rawat et al.,

2014; Carrabs et al., 2017). Most of the time,collecting and spreading the data requires a huge plan-

ning effort, mainly when covering places with difficult access, as mines, forests, volcanoes, or even

highly radioactive sites. Therefore, these characteristics lead to very costly activities. Consequently,

the development of efficient approaches to minimize the arising costs is a challenging issue.

The above scenario is a prominent motivation for the design of wireless sensor networks (WSNs;

Morais et al., 2016c). Consider a set of autonomous,tiny, and compact sensorscapable of performing

activities such as sensing, processing, and transmission, and a set of sinks responsible for collecting

the sensed data and managing the network.A sink has unlimited or renewable energy and it also has

the function of processing and aggregating the information received from sensors. It can be stati c

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

V.Morais and G.R. Mateus / Intl. Trans. in Op.Res. 26 (2019) 836–855 837

or mobile, visiting the monitored site and collecting data (Kim et al., 2003; Basagni et al., 2008).

The sensors are made up of sensing boards, processor, transmission radio, and battery. Because of

their purposes, size, and low cost, they have serious restrictions of energy, low performance, and

small radius of transmission. These characteristics lead to a limited lifetime of sensors and also

the network itself (Anastasi et al., 2009). In order to overcome such a problem, the sensors must

be organized and a set of routes has to be chosen defining the transmission paths among sensors

and sinks. Thereby, we aim to maximize the network lifetime by minimizing the routing costs.

Besides natural connectivity requirements, in this paper, we also deal with covering and cardinality

constraints in an integrated manner.

The definition of a WSN topology involves ensuring fundamental requirements, being coverage

probably the central point on the design of such network (Morais et al., 2016c). The coverage

level can be total or partial, but, in general, coverage of the entire sensing area is always preferred.

Therefore, one has to choose a set of active sensors such that each demand point is within a range

of at least one sensor. Indeed, guaranteeing such a need becomes a crucial problem when placing

the sensors: a subset of sensors must be deployed in order to guarantee connectivity and coverage

of the entire sensing area (Efrat et al., 2005; Casta˜

no et al., 2014).

Data transmission is one of the most expensive operationsin ter ms of energyconsumption (Aky-

ildiz et al., 2002). An alternative to maximize the network lifetime is to define hierarchical networks

and implement efficient routing approaches in order to avoid premature disconnection due to the

energy depletion. In many cases, the transmission topology is arranged in clusters, each one having

a sensor assuming the role of clu ster head . Through some wireless protocol, the cluster head is

responsible for collecting and aggregating the data from other sensors within the cluster and trans-

mitting them directly or indirectly to a sink. Regular sensors within a cluster must communicate

directly with the elected cluster head using a single-hop strategy or through other sensors using a

multihop protocol (Aioffi et al., 2011). Classical combinatorial optimization problems as p-median

(Hakimi, 1964, 1965) and k-center (Agarwal and Sharir, 1998) appear naturally in such a cluster-

ing context to efficiently manage the network energy consumption by reducing the transmission

range of the sensors. The transmission among cluster heads and sinks is typically multihop. Thus,

the connectivity requirement is enforced with a two-level sensor-to-sink scheme, intracluster and

intercluster routes. In both levels, a direct structure is defined to transmit data from sensors to

cluster heads (intracluster routes) and from cluster heads to sinks (intercluster routes).

An important requirement that stronglyimpacts on the design of WSNs and directly influences on

the complexity of meeting data routing as well as other quality of service (QoS)1parameters, is the

cardinal ity constraint. Knowing that aggregation and data transmission are the two most expensive

activities in terms of energy consumption, the cluster heads are expected to consume much more

energy compared to regular sensors, that only monitor and transmit data. In general, they deplete

their batteries very quickly, becoming isolated from the rest of the network. Thus, in order to

prolong the network lifetime, clustering protocols such as the Minimum Transmission Energy

Routing protocol, LEACH (Heinzelman et al., 2000), and LEACH-C (Heinzelman et al., 2002)

perform a periodic rotation on a fixed number of preselected cluster heads. The cardinality of such

cluster-head set is typically determined as a percentage of active sensors within each time period.

As we will discuss, restricting the cardinality of a cluster-head set and consequently the number of

1QoS usually refers to quality as perceived by the user and/or application.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies