European Journal of Operational Research 181 (2007) 390–402

www.elsevier.com/locate/ejor

O.R. Applications

Maximizing system lifetime in wireless sensor networks

A. Alfieri a, A. Bianco b, P. Brandimarte a,*, C.F. Chiasserini b

a Dipartimento di Sistemi di Produzione ed Economia dell’Azienda, Politecnico di Torino,

Corso Duca degli Abruzzi 24, 10129 Torino, Italyb Dipartimento di Elettronica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy

Received 17 May 2004; accepted 17 May 2006Available online 10 August 2006

Abstract

One of the most critical issues in wireless sensor networks is represented by the limited availability of energy on networknodes; thus, making good use of energy is necessary to increase network lifetime. In this paper, we define network lifetimeas the time spanning from the instant when the network starts functioning properly, i.e., satisfying the target level of cov-erage of the area of interest, until the same level of coverage cannot be guaranteed any more due to lack of energy in sen-sors. To maximize system lifetime, we propose to exploit sensor spatial redundancy by defining subsets of sensors active indifferent time periods, to allow sensors to save energy when inactive. Two approaches are presented to maximize networklifetime: the first one, based on column generation, must run in a centralized way, whereas the second one is based on aheuristic algorithm aiming at a distributed implementation. To assess their performance and provide guidance to networkdesign, the two approaches are compared by varying several network parameters. The column generation based approachtypically yields better solutions, but it may be difficult to implement in practice. Nevertheless it provides both a goodbenchmark against which heuristics may be compared and a modeling framework which can be extended to deal with addi-tional features, such as reliability.� 2006 Elsevier B.V. All rights reserved.

Keywords: Heuristics; Telecommunications; Column generation; Routing; Distributed algorithms

1. Introduction

Sensor networks are composed of small elec-tronic devices, the sensors, that monitor areas,objects, animals, persons, or sense temperature,humidity, the presence of acoustic or seismic waves,etc., in a given area of interest. Wireless sensors can

0377-2217/$ - see front matter � 2006 Elsevier B.V. All rights reserved

doi:10.1016/j.ejor.2006.05.037

* Corresponding author. Fax: +39 011 564 7299.E-mail address: paolo.brandimarte@polito.it (P. Brandi-

marte).

be used for remote monitoring and object-trackingin different environments and for a wide range ofapplications. Typically, they consist of a Micro-Electromechanical System (MEMS), a low-powerDigital Signal Processor (DSP), a radio frequencycircuit, and a battery. Due to their low-cost andlow-complexity nature, sensors are characterizedby several constraints, such as a short transmissionrange, poor computation and processing capabili-ties, low reliability and data transmission rates,and a limited available energy. Therefore, sensornetworks should be designed with the aim to

.

A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402 391

overcome these limitations, e.g., by exploiting thesynergy between multiple nodes.

The limited availability of energy on networknodes is one of the most critical issues in sensor net-works; thus, we focus in this paper on the reductionof energy consumption in sensor networks. Indeed,re-charging or replacing the nodes’ battery may beinconvenient, or even impossible in disadvantagedworking environments. This implies that the timeduring which all sensors are able to sense, transmit,receive and process information is limited; thus, thenetwork lifetime, i.e., the interval during which thenetwork functions properly, becomes an importantperformance measure. There are various possibledefinitions of network lifetime, depending on thenetwork application. For example, it can be consid-ered as the time spanning from the instant when thenetwork starts functioning till a certain percentageof sensors run out of energy, or until the networkgets disconnected. In this paper, we define networklifetime as the time spanning from the instant whenthe network starts functioning properly, i.e., satisfy-ing the target level of coverage of the area of inter-est, until the same level of coverage cannot beguaranteed any more due to lack of energy in sen-sors. Our objective is to devise solutions that maxi-mize network lifetime under such a minimalcoverage constraint.

We take as a case study a video-surveillance net-work for monitoring a given territorial area (forsimplicity, a rectangular area), called area of inter-est, with a desired level of coverage. While monitor-ing the area of interest, sensors gather information(i.e., images), and send it to some gateway node,conveniently located within the area of interest. Sen-sors that are unable to reach the gateway node bydirect transmission, deliver the collected informa-tion by using intermediate sensor nodes as relays(multi-hop transmission). We assume that sensorscan be switched off if needed to reduce power con-sumption. We also assume that the number ofdeployed sensors is large enough that sensors sub-sets can provide the desired level of coverage, if theyare properly chosen. Given that sensor battery life-time should be spared to maximize network lifetime,a fairly intuitive approach is to switch on, at a giventime, only the minimum number of sensors neededto guarantee the desired level of coverage in thearea. Based on the above observation, we dividesensors into subsets, each subset being active in dif-ferent periods of time, and devise an optimal sched-uling of sensors’ activity, so that the sensor battery

lifetime is maximized and the quality requirementsare met. Since subsets of active sensors form asub-network, we will use the terms subset and subnet

interchangeably.Our problem can be regarded as a generalization

of the set partitioning approach proposed by [10].There, the authors consider a set of points in the areaof interest and a set of sensors. Each sensor is able tocover a subset of points, and the aim is to generate apartition of the set of sensors in disjoint subsets, suchthat each subset of sensors is able to cover the set ofpoints. The lifetime of each subset will correspond tothe lifetime of a single sensor, and by maximizing thenumber of disjoint subsets the overall network life-time is maximized. Their problem is basically a setpacking problem, which is NP-hard [8], and solutionheuristics are proposed by the authors.

The idea of switching sensors on and off in order toincrease the system lifetime may be pursued in a moregeneral setting. In fact, in [10] the authors do not con-sider multihop routing, which is necessary whentransmission range limits connectivity, nor the trade-off between quality of coverage and system lifetime.The problem described in [10] can be reduced to oursif we assume that energy is consumed only for sensingand not for transmitting data and we require 100%coverage. Hence, our problem is NP-hard as well,and we must rely on heuristic solution methods. Inthis paper we propose two approaches: the first oneis based on a mathematical programming model.The second one is a greedy approach that should bemore easily implemented in a distributed way in arealistic scenario, although the definition of a properprotocol to support the proposed approach is beyondthe scope of this paper.

The mathematical programming model is basedon a decomposition of the overall problem, whichincludes both routing and scheduling issues, by acolumn generation scheme [12, Chapter 11]. Thegreedy approach is based on an ad hoc solutiondevised to exploit sensor spatial redundancy; evenif this approach is simplistic, it better scales to verylarge networks and proved to be effective in terms ofperformance in some scenarios.

The main critical point of the first approach isthat we assume a centralized management scheme,in contrast to the literature concerned with distrib-uted protocols and decentralized management (see,e.g., [11]). While this is a debatable assumption,and there are application fields in which thisapproach would probably be too difficult to pursue,we think that the most interesting feature of this

392 A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402

approach is in providing a flexible framework thatcan be extended to deal with more complex scenar-ios, as hinted later. Furthermore, it may work as abenchmark against which the quality of distributed,and possibly more practical heuristics may be com-pared. Actually, we may also envisage solutionmethods integrating the two approaches. The over-all problem entails at least two dimensions: routingand scheduling. To these, we could also add a thirdone: reliability. This is not within the scope of thepresent paper, but we want to stress that the columngeneration framework is well suited to tackle thisissue. Finally, even in those cases in which the math-ematical programming model approach is not feasi-ble, having a good target for system lifetime can bevaluable in designing and evaluating distributedprotocols [2]. Furthermore, checking if, in a specificapplication, significant advantages are obtained bya more complex management method may help indesigning the system architecture.

To increase the generality of the approach and tokeep the model relatively simple, we do not takeinto account many important technological con-straints. As such, for example, we do not specifythe access protocol used by sensors to transmit data;our model is general enough to allow us to abstractfrom these details. Obviously, a more detailedmodel would provide results closer to reality. How-ever, increasing the model complexity would makevery difficult to solve the problem in reasonablecomputation time. Moreover, the importance ofthe presented results resides in the general trendsthat can be deduced by looking at performance indi-ces, which are marginally influenced by specificimplementation details.

The remainder of the paper is organized in thefollowing way. First we describe our system modeland assumptions in Section 2. Then a formal defini-tion of the optimization problem is provided in Sec-tion 3. In Sections 4 and 5, we describe the twoalgorithms proposed to solve the network lifetimemaximization problem. The two approaches arecompared and system performance, as a functionof network parameters, is analyzed in Section 6.Finally, we draw some conclusions and providehints for future work in Section 7.

2. System model description and assumptions

Different models have been proposed for sensornetworks, depending on the type of sensing involvedand the specific application. The basic network set-

ting that we assume in this paper relies on the workdescribed in [2,6,10].

We consider a set of sensors, indexed byj = 1, . . . ,N, whose placement is known. Sensorsmay be used in different roles; indeed, in the follow-ing we will often speak of nodes rather than sensorsto point out the multiple role they may take. Exam-ples of roles are: sensing (which we assume periodicrather than event-driven), compressing data, rout-ing data (which implies either sensing and transmit-ting, or receiving and transmitting) to another nodeor to the gateway. Roles are not mutually exclusive.

Sensors should cover a discrete set of points inthe area of interest, indexed by i = 1, . . . ,M. Suchan approach differs from other solutions based oncomputational geometry [4], since, given a regionin the plane and a sensing range, we do not addressthe problem of ensuring that each point in theregion (an infinite set of points) is covered. Rather,we adopt a simplified approach considering a dis-crete set of points as a good sampling of the region.On the one hand this is an approximation, but onthe other one it provides us with a flexible modelingapproach which allows us to deal both with planarand spatial problems, possibly complicated byobstacles. It should also be mentioned that withinthis modeling framework we may also deal withproblems in which the set of points to cover isexplicitly assigned.

The quality of coverage may be measured and aminimal quality level is required; for instance, wemay require that at least a certain percentage ofpoints are covered. When a point is covered, wemay assume that it is covered by multiple sensorsor by exactly one sensor. In the following, we con-sider the case of points covered by at most one sen-sor (of course, a sensor may cover different points).Multiple coverage may be considered (see Section7), but, unless it is required only because of reliabil-ity issues, it requires a way to measure the increasein the quality of coverage and a way to model theelimination of redundancy, unless this is performedin the gateway node.

For each point of interest i, we know the set Si ofsensor nodes which can cover i. Then, for each sensornode j, we also know the set of points Cj which can becovered, and the set Rj of reachable sensor nodes,i.e., nodes which can be reached directly, withoutrouting through intermediate nodes, given transmis-sion constraints, as communication may be limitedboth by distance and natural obstacles. All sensorsare equal and have an initial energy endowment E.

A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402 393

A special node, the gateway, is denoted by G; itsenergy is unbounded. The gateway is the node towhich all the data must be routed. We denote byRG the set of nodes that can reach the gatewaydirectly, without the need for multihop routing.

Data compression may be performed by a sens-ing node to minimize energy consumption, whichdepends also on the roles played by that node andon the transmission power required by distance.

For each point i, we define as qi the correspond-ing data flow rate, that is input into the network ifpoint i is covered (e.g., number of images per unittime). In the following we assume that the data rateis the same for any point. We also assume as known

• ETjk: the energy required to transmit data (e.g., an

image) from node j to node k per unit of flow; itdepends on distance between nodes;

• ER: the energy required by any node to receivedata per unit of flow;

• E C: the energy required to sense and compressdata per unit of flow.

Here we take a minimal quality of sensing as a con-straint, which is expressed as a lower bound L oncoverage, i.e., the minimal percentage of pointswhich must be covered. Hot spots and more refinedmeasures of coverage may be easily dealt with byadapting the models below. Indeed, a potentiallyuseful way of using the models below is in assessingthe trade-off between quality of coverage and net-work lifetime; this is easily obtained by solving themodels repeatedly for different values of L.

We point out that our work relies on variousassumptions, which are related to the specific net-work application. Some of these assumptions maybe relaxed or changed with no difficulty, while oth-ers may be changed in principle (e.g., we modelenergy consumption in a very simple way), but theywould probably lead to an overly difficult modelfrom the computational point of view, at least forthe mathematical programming approach.

3. Problem statement

As a first step, we leave aside the concept of sen-sor subnets and consider a unique set of sensors. Weintroduce the following decision variables:

• xij 2 {0,1}, set to 1 if point i is covered by node j,in which case point i contributes an input flow qi

into node j;

• fjk P 0: data flow rate from node j to node k

(measured, e.g., by the number of compressedimages transmitted per unit time);

• wj P 0: data flow rate from node j to thegateway.

We write the power required by node j as

P j ¼Xi2Cj

ECqixij þXk2Rj

ETjkfjk þ

Xk2Rj

ERfkj þ ETjGwj;

which means that the power is given by the sum ofthe data flow (rate) from points i 2 Cj actually as-signed to and covered by sensor j times the energyconsumed by sending one unit of data, plus the dataflow from node j to reachable nodes k 2 Rj times therequired transmission energy, plus the data flow re-ceived at node j from nodes k 2 Rj times the re-quired receiving energy, plus a term accounting fordata sent to the gateway. Actually, this term shouldbe considered only for nodes j 2 RG and we shouldwrite two equations, one for nodes that can reachthe gateway directly and another one for nodesj 62 RG; for the sake of simplicity we avoid doingso, enforcing a constraint like wj � 0 for the secondcase. By multiplying the power by the system life-time T, we get the total energy consumption, whichcannot exceed the energy available in any node. Toget a linear model, the objective of maximizing sys-tem lifetime can be rephrased in terms of balancingthe power requirement across nodes. In otherwords, by minimizing the maximum power con-sumed, Pmax � maxj Pj, across the nodes, subjectto coverage constraints, we maximize system life-time. This basic problem (BP) may be expressed asthe following MILP (Mixed Integer Linear Pro-gramming) model:

ðBPÞ min P max

s:t:Xi2Cj

qixijþXk2Rj

fkj¼Xk2Rj

fjkþwj; j¼ 1; . . . ;N ;

ð1ÞXj2Si

xij6 1; i¼ 1; . . . ;M ; ð2ÞX

i

Xj2Si

xij P L �M ; ð3Þ

P max PXi2Cj

ECqixijþXk2Rj

ETjkfjk

þXk2Rj

ERfkjþETjGwj; j¼ 1; . . . ;N ; ð4Þ

xij 2f0;1g; wj P 0; fjk P 0; ð5Þwj� 0; 8j 62RG: ð6Þ

394 A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402

Eq. (1) expresses conservation of flows. Constraint(2) states that each point must be assigned to atmost one sensor, whereas (3) enforces the minimalrequired coverage. Finally, (4) sets the maximumpower Pmax and (6) eliminates the possibility ofrouting data to the gateway if it is not reachablefrom node j.

The above formulation does not exploit the possi-bility of switching sensors on and off; it is a routingproblem, with a sort of plant-location component,and it disregards scheduling issues. To improve sys-tem lifetime, provided enough redundancy in thesensors is available, we may exploit the concept ofsensor subnets, which can be switched on and offto save energy. This leads to the column generationapproach described in the next section.

However, apart from being a first modeling stepthat we include for the sake of exposition, thismodel is useful for different reasons.

1. It should be noted that by relaxing the integralityrequirement on the assignment variables xij, weget a LP problem which may be used to find anupper bound on the system lifetime. In this con-tinuous relaxation, we allow shared coverage of apoint: this means, e.g., that 60% images from apoint are taken by one sensor and 40% byanother one. In practice this is difficult to imple-ment, and this is the reason for requiring that apoint is covered by at most one sensor.

2. Given a point-to-node assignment, i.e., a set ofvalues of the decision variables xij meeting cover-age constraint (3), we may build a feasible subnetby solving the remaining routing problem withrespect to the continuous decision variables wj

and fjk. This will be useful in initializing the col-umn generation approach.

4. A column-generation based decomposition

framework

We describe here the mathematical programmingapproach based on column generation. As we havepointed out before, the overall problem we considerhas two main components:

1. a routing component, which is linked to definingroles for each node and assigning points tonodes;

2. a scheduling component, since a node may playdifferent roles in different time instants. It is

worth noting that the scheduling componentinvolves non-renewable resources [3].

The idea is to decompose the two issues by gen-erating a set of network configurations (subnets),each of which is connected and meets the minimalcoverage requirements. Then we should decidehow much time each subnet is used. By alternatingthe configurations, we exploit the available redun-dancy in sensors.

Column generation is a general purpose frame-work which have been often proposed either as acomputationally efficient alternative to standardmethods or as a modeling tool when a directapproach is infeasible. See, e.g., [12, Chapter 11]for a tutorial treatment, or [1] for a recent survey.

In our case, columns correspond to subnets, i.e.,network configurations. The aim of the master prob-lem, described below, is to select the columns and todecide the length of the time interval a subnet is used,subject to energy budget constraints for each node.From the dual variables of the energy budget con-straints we derive costs which are used in the column(subnet) generation subproblem. The subnet genera-tion subproblem aims at finding a feasible subnetensuring the minimal required covering.

4.1. The subnet selection (master) problem

Let s be an index referring to the subnets gener-ated so far by the subnet generation subproblem.Each subnet is characterized by the role of eachnode and by the power required by that role. Sincewe do not assume mutually exclusive roles (eachnode may both sense and route data from other sen-sors), the role is basically characterized by the inputand the output flows through each node.

Let P sj be the power required for node j in subnet

s (it is 0 if the node is not active in that subnet) andlet ts P 0 be a decision variable corresponding tothe amount of time subnet s is used. Then, to max-imize network lifetime we solve the master problem(MP):

ðMPÞ maxX

s

ts

s:t:X

s

P sj ts 6 E 8j;

ts P 0:

ð7Þ

This problem is a classical LP problem, solved bythe standard simplex algorithm. As stated before,columns P s represent network configurations, that

A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402 395

is subsets of nodes playing defined roles to which agiven power requirement is associated. They aregenerated on a as-needed basis by the subnet gener-ation subproblem described in the next section. Letpj be the dual variable (shadow price) associated tothe energy budget constraint (7) for node j. This isused to define the cost objective for subnet genera-tion. Intuitively, a large shadow price for a node im-plies that using the corresponding node is costly.

Note that further constraints could be easilydealt with, such as the maximum number of subnetswe want to use and a minimal time an activated sub-net must be used. These constraints would help inreducing the burden of switching roles, in order tomake the approach more manageable in practice.In this case, we would not have a continuous LPas a master, but a MILP model, possibly solvedby branch and price.

4.2. The subnet generation subproblem

In this subproblem, denoted by (GEN), we donot consider energy limitations directly; the energyconsumed by each node is priced by the dual vari-ables pj from the master problem (MP). The objec-tive is to cover the set of points with minimum cost,subject to quality constraints. Thus the problem is amodification of model (BP) of Section 3

ðGENÞ minX

j

pj

Xi2Cj

ECqixijþXk2Rj

ETjkfjkþ

Xk2Rj

ERfkj

" #

þXj2RG

pjETjGwj

s:t: ð1Þ–ð3Þ ð5Þ; ð6Þ: ð8ÞGiven an optimal solution to this subproblem, i.e.,x�ij, f �kj, w�j , we compute the power requirement foreach node as,

P sj ¼

Xi2Cj

ECqix�ij þ

Xk2Rj

ETjkf �jk þ

Xk2Rj

ERf �kj þ ETjGw�j ;

which is the information needed by the master prob-lem (MP).

The generation subproblem is a possibly hardMILP model. We solve the subnet generation prob-lem at optimality by standard branch-and-bound;however, from a practical point of view, we shouldnote that it can be solved sub-optimally by introduc-ing some sub-optimality tolerance. Actually, thiscould be useful during the first iterations, to enrichthe initial set of subnets as quickly as possible toget good shadow prices. It is important to note that

many variations may be accommodated within thiscolumn generation framework: in some applica-tions, even using constraint-based search within col-umn generation has been proposed [9]. Solving thesubnet generation subproblem by sophisticated heu-ristic procedures might be important in the case reli-ability constraints are considered.

4.3. Initializing the column set and stopping criteria

To start-up the column generation process, aninitial set of columns is required, to be able to solvethe master problem (MP) once and obtain the firstset of dual variables. It is also important to startwith a good set of columns. To this aim we havebasically followed the set partitioning approachproposed in [10]. We find a certain number of dis-joint sets of sensors meeting the minimal coverageconstraint, using a pure 0/1 programming formula-tion solved by branch and bound. For each subsetof sensors, corresponding to an assignment ofpoints to sensors, we build a subnet by solving basicproblem (BP) with the covering variables xij setaccordingly. This provides us with an initial set ofcolumns.

The termination criterion is the standard one forcolumn generation [12]. Considering master prob-lem (MP), we see that in order to generate a usefulcolumn we must find a new subnet s* such that itsreduced cost 1�

PjpjP s�

j is positive. Strictly speak-ing, this is not quite correct, as there is the possibil-ity of stalling. Just like in the simplex algorithm, wemay have a subset of neighboring solutions with thesame objective, such that you do not improve thesolution for some steps of the algorithm. However,computational tests, not reported in the following,have shown that results do not change significantly,if they change at all. Furthermore, the contributionof later columns to the overall solution tends to bemarginally decreasing, so we have considered thisstopping criterion in order to reduce computationaleffort and prevent issues with cycling. In terms ofthe subnet generation subproblem (GEN), thismeans that we aim at finding a solution whose valueof objective function (8) is strictly less than one. Ifthe objective value from (GEN) does not meet thisrequirement, it is impossible to find a new columnthat, added to the master problem, increases the net-work lifetime and we stop the algorithm.

We have observed that sometimes the last col-umns which are generated do not contribute signif-icantly to the increase of network lifetime. In such

396 A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402

cases, a possible alternative (that we did not use inthis work) is to stop the master/subproblem itera-tions when the maximum lifetime is not increasedsignificantly.

5. A greedy approach

The general idea of the distributed approach isalso based on the fact that we can use the high spa-tial redundancy in sensor nodes by making a smallsubset of nodes active in a given sub-area, thusexploiting sensor activities in different periods oftime. In other words, only a subset of sensors isactive for a given period of time, named schedulingperiod, whereas all other sensors are in inactivestate, saving energy for future scheduling periods.

The proposed approach consists of the followingsteps:

1. form a proper (i.e., covering) subset of sensorsthat will be switched on (active sensors); if thesubset does not guarantee the required level ofcoverage, discard this instance and repeat step 1;

2. put all other sensors in off state (inactive sensors);3. determine a suitable minimum cost routing to

transfer the sensed information from all activesensors to the gateway node; if this is not possiblewith the selected subset of sensors to guaranteefull connectivity, i.e., if not all of the activesensors are able to communicate, possibly viamulti-hop transmission, with the gateway node,the subset is discarded and the process is restartedfrom step 1;

4. determine the scheduling period duration, i.e.,the amount of time for which this sensor subnetlasts, while guaranteeing the target level ofcoverage;

5. compute sensors energy consumption over thistime interval, subtract it from each sensor energybudget, and eventually consider some of the sen-sors as unavailable in the future due to energydepletion;

6. iterate through this process until no other subsetof covering and fully connected sensors can befound.

Let us now describe the above steps in moredetail. For what concerns the selection of the sensorsubset (step 1), we simply allow each sensor todecide independently with a given probability (equalfor all sensor nodes) whether to be in the off (inac-tive) or on (active) state in the current scheduling

period. We check whether the selected subset is fea-sible, i.e., able to guarantee the required coverage. Ifinfeasible, this subset is discarded and the algorithmrestarts. For each point to be covered in the area ofinterest, only one randomly chosen sensor amongthe currently active sensors is really activated,whereas all other sensors are put in inactive state(step 2).

If the subset is feasible, we solve the routingproblem (step 3) among sensors building a tree rou-ted in the gateway, obviously taking into accountsensors transmission capabilities. Standard tech-niques to determine a tree on an unknown topology(e.g., finding a spanning tree on a network in a dis-tributed fashion, without centralized knowledge ofnode placement) could be used to solve this prob-lem. However, we implemented a simpler subopti-mal algorithm to determine paths among sensornodes. Each node is assumed to know the reachableand active sensors closer to the gateway; this couldbe simply implemented by periodically broadcastingnode identity and distance from the gateway. Eachnode randomly selects one among the available sen-sors closer to the gateway, to send the sensed infor-mation in multi-hop fashion to the gateway node.All sensors not involved in either sensing or routingoperations are put in inactive state. If some sensor isnot able to find a neighbor, the subset is not con-nected and the subset is discarded.

Finally, the duration of the scheduling period isdetermined by the sensor that exhausts its residualpower budget first (steps 4 and 5).

This process is iterated until no more feasiblesubsets can be found after a fixed, large, maximumnumber of iterations was run (step 6).

Note that, if we neglect any cost in creating anddiscarding a subset, it is always convenient to haveall sensors potentially active in a scheduling period,thus setting the probability of being active equal to1. However, this parameter is important in realisticimplementations to reduce the cost of exchanginginformation among nodes in order to determinethe feasibility of a selected subset.

This algorithm is largely suboptimal; however, itmay be reasonably implemented in a distributedfashion and shows good performance in the consid-ered scenarios.

6. Testing scenario and numerical results

The column generation scheme was implementedusing the OPL STUDIO/CPLEX 8.0 optimization

Table 1Instance classes

Class Sensors Points Range

1 25 5 2.52 25 5 33 25 10 2.54 25 10 35 50 5 2.56 50 5 37 50 10 2.58 50 10 39 50 20 2.5

10 50 40 2.511 100 5 2.512 100 5 313 100 10 2.514 100 10 315 100 20 2.516 100 40 2.517 100 80 2.5

Table 2Average CPU time (seconds) required by column generation foreach instance class

Class Seconds

1 32 43 54 75 106 207 278 359 38

10 5911 13112 20713 21514 25215 26416 29317 436

A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402 397

modeling system, whereas the greedy approach wasimplemented in MATLAB. To assess the merits ofthe proposed algorithms, various instance classeswere considered, whose parameters are reported inTable 1. Each class is characterized by: number ofsensors, number of points to be monitored, andmaximum sensing range that is assumed to be equalto the maximum transmission range of sensornodes. The last choice was just made for the sakeof simplicity, to limit the number of factors. Inmany applications the sensing range is smaller thanthe transmission range.

Each class was generated according to the follow-ing specifications:

• the area to be covered is a square with sideQ = 10;

• the gateway node is located at the center (coordi-nates (5, 5)) of the covered area;

• sensors are uniformly distributed on the area, i.e.,their coordinates are generated by using apseudo-random number generator;

• to position the points of interest in such a way tocover the area as uniformly as possible we haveused Halton low-discrepancy sequences; low-dis-crepancy sequences are the basis of quasi-MonteCarlo integration methods; basically, they arejust a way to cover unit hypercubes (in ourtwo-dimensional case, a square) as uniformly aspossible by a deterministic sequence, rather thanby random sampling (see, e.g., [5, Chapter 4]); itis worth noting that sensors are placed usingpseudo-random numbers in order to simulate

random placement of sensors (which could belaunched by an aircraft in some applications);on the other hand, points are placed accordingto a low-discrepancy sequence to represent agood sampling of the area of interest; in areal-life setting, one might have more structuredinformation about the points that must becovered;

• minimal required coverage: 100% and 90%;• initial energy endowment E: 0.75Ah * 3.3 V =

8910 J;• energy requirement to transmit a compressed

image [mJ], as a function of distance d:5.0 + 0.01 * d2. This value may include the aver-age amount of energy required for retransmis-sion, if a random access protocol is used totransmit data;

• energy requirement to receive a compressedimage: 5.0 mJ;

• energy requirement to compress an image:3.6 mJ; we assume that this also includes therequired energy for sensing;

• sampling rate and transmission interval: oneimage every 15 seconds.

Numerical values are taken from [7]. Using theseinstances, we tested both the column generationscheme and the greedy algorithm; the results wereaveraged over ten instances for each class.

A first issue is CPU time. While the greedy algo-rithm has negligible requirements, the column gen-eration approach may be costly. In Table 2, we

Table 4Average features of the subnets used in the column generationsolution and in the greedy approach for 100% coverage

Class Column generation Greedy approach

Ave. LT[days]

Ave.nodes’ no.

Ave. LT[days]

Ave. nodes’no.

1 44.11 4.55 62.35 8.472 47.89 4.31 69.06 6.683 16.44 7.96 40.71 13.434 20.66 7.13 31.01 11.155 28.33 5.52 40.69 9.856 32.67 4.17 29.98 9.477 11.56 8.46 33.57 14.728 14.61 7.59 22.72 13.069 6.53 13.77 16.25 22.03

10 3.18 20.21 8.49 30.2211 24.14 4.83 25.6 10.6912 32.31 4.27 26.52 9.3213 8.54 8.60 13.11 18.5214 14.74 7.73 12.98 16.1415 4.53 15.43 7.37 26.7916 2.48 22.29 4.72 35.9717 1.21 34.80 1.93 43.71

Table 5Sensors’ power consumption in the column generation solutionand in the greedy approach for 100% coverage

Class Column generation Greedy approach

Ave. maxPW [W]

Ave. meanPW [W]

Ave. maxPW [W]

Ave. meanPW [W]

398 A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402

report average CPU times required by column gen-eration (using ILOG OPL/CPLEX 8.0, on a PCoperating under Windows NT, with a clock fre-quency of 500 MHz). We see that the CPU time issignificant if compared to negligible CPU times ofthe greedy approach, but different tricks of the trade(sub-optimality tolerances and early termination ofthe column generation process) could be used toimprove performance.

Table 3 reports, for each class of instances, theaverage total lifetime (LT) of the system achievedby sequentially using different networks and theaverage number of networks employed to monitorthe area under control. The results in the left handside refer to the optimal solution, while the resultsin the right hand side have been obtained throughthe greedy approach. For the column generationapproach Table 3 also reports the average numberof networks generated to reach the optimal solution;this metric is not reported when the greedyapproach is employed since, in this case, all gener-ated networks that meet the coverage and connec-tivity constraints are used to build the final solution.

Table 4 reports the characteristics of the net-works used in the optimal and greedy solution.The second and fourth column contains the averagelifetime of each used network, while the third andfifth one indicates how many sensors are active,on average, in each of these networks. Table 5

Table 3Average features of solutions obtained by column generation andby the greedy approach for 100% coverage

Class Column generation Greedy approach

Generatednets

Tot. LT[days]

Usednets

Tot. LT[days]

Usednets

1 12.1 147.5 4.2 113.13 2.12 15.2 160.7 4.4 105.25 1.63 13.3 67.8 4.3 32.67 2.34 15.0 89.5 5.5 48.25 1.75 58.7 318.2 13.4 226.19 6.86 85.6 470.3 14.8 373.31 13.17 64.3 143.1 13.9 69.45 2.78 125.7 236.4 17.2 158.44 8.89 66.0 72.4 12.7 36.4 2.5

10 72.2 36.7 12.9 18.7 2.611 190.4 681.1 30.0 618.9 25.312 282.0 974.8 32.0 910.3 34.913 248.6 331.7 39.2 324.3 25.214 314.9 485.1 34.3 457.4 34.915 264.0 167.0 37.9 166.6 22.916 260.0 83.8 34.3 72.2 18.717 253.9 41.7 36.5 28.5 15.4

1 1.38 0.87 1.51 0.862 1.20 0.68 1.45 0.853 2.66 1.21 3.25 1.244 2.21 1.10 3.14 1.215 1.53 0.85 1.72 0.886 1.15 0.75 1.68 0.877 2.63 1.03 3.27 1.238 1.91 0.90 3.01 1.129 5.48 1.69 4.81 1.49

10 10.23 2.64 12.31 2.6011 1.212 0.75 1.50 0.8112 1.08 0.74 1.36 0.7513 2.65 0.96 3.27 1.1114 2.19 0.96 2.90 1.0515 4.54 1.15 6.04 1.5016 9.07 1.84 13.08 2.3617 23.11 3.21 31.73 5.00

reports the performance of the optimal and greedysolution in terms of maximum and mean value ofpower consumed (PW) by a single sensor.

First, let us consider system performance whenwe fix both the number of sensors and the numberof points of interest, and vary the sensor sensing/transmission range (i.e., compare classes 1 and 2, 3

A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402 399

and 4, etc.). From Table 3, we observe that the totalsystem lifetime, as well as the number of used net-works, increases significantly. Indeed, the numberof sensors that can ensure the required coverageor successfully route data toward the gateway nodegrows, thus increasing the number of networks thatcan be employed. This also implies that the averagenumber of sensors included in a single networkdecreases for larger values of the sensing/transmis-sion range (see Table 4). As for the sensor powerconsumption reported in Table 5, we observe areduction in both the average maximum and themean value as a larger sensing/transmission rangeis considered. This behavior can be explained as fol-lows. Recall that the contribution to power con-sumption due to the output transmit power isnegligible, in the sense that we have a contribution0.01 * d2 with respect to a fixed component 5.0,while the most relevant contribution is due to thetransceiver, in transmission mode as well as inreceive mode. By increasing the sensor range, theroute length from the point of interest to the gate-way node becomes shorter; this implies that lessrelay nodes will be involved, i.e., less nodes wouldexperience both the transmission and reception cost.

Next, assume the sensor range and the number ofsensors to be fixed. Comparing classes 1 and 3, 2and 4, 5, 7, and 9, and so on, in Tables 3–5, wecan analyze system performance for increasing val-ues of the number of points of interest. As expected,the number of points to be monitored has a greatimpact on the system lifetime and power consump-tion. In particular, a large number of points leadsto an increase in the number of sensors needed ineach network and, hence, in the mean power con-sumption; as a consequence, the total system life-time decreases. Moreover, in each single network,it is more likely that a node has to gather data frommore than one point, or route a larger amount ofdata to the gateway node. It follows that the maxi-mum value of power consumption experienced bythe sensors grows and, thus, the average networklifetime decreases. Note that the number of usednetworks increases when increasing the number ofpoints if the optimal solution is applied; indeed, asthe number of points to be controlled grows, moresolutions are available to cover points, but itbecomes harder to find an optimal solution; thus,more networks are generated and tried out, but‘‘good’’ networks do not increase at the same pace.When using the greedy solution, it becomes increas-ingly difficult to find networks that satisfy the cover-

age requirements as the number of points to becovered increases; thus, the number of used netsdrops significantly.

Given the sensor range and the number of pointsof interest, consider the system performance as thenumber of sensors changes from 25 to 100 (i.e., inTables 3–5 compare classes 1,5,11, or 2,6,12, andso on). As expected, the total lifetime and the num-ber of used networks increase as the number of sen-sors grows (see Table 3). Indeed, when a largernumber of sensors are available, a greater numberof feasible networks can be found. Moreover, asthe nodes exhaust their energy resources, furtherconfigurations that meet the constraints on connec-tivity and coverage are formed by using more nodesper single network. This is confirmed by the valuesof average number of active sensors presented inTable 4. The fact that the number of used networkssignificantly increases with the increase in the num-ber of available nodes justifies the reduction in theaverage network lifetime. Indeed, most of the net-works that are created as the nodes start exhaustingtheir energy have a short lifetime, which clearlyimpacts the average lifetime. As for the averagepower consumption, we can see from Table 5 thatincreasing the number of sensors implies a lowermean power consumption per sensor. Indeed, ahigher redundancy in the available nodes allowsfor more power-efficient networks. Also, note thatin Table 3 the difference between the number of gen-erated networks and the number of used networksincreases while increasing the number of availablesensors. For instance classes from 1 to 4, the num-ber of networks used in the optimal solution isabout 1/3 of the total number of generated net-works, while, for instance classes from 11 to 14,the ratio decreases down to about 1/7. This is dueto the fact that, for a large value of the number ofnodes, the number of feasible networks increasessignificantly; however the number of ‘‘good’’ net-work configurations is limited by the given place-ment of the points under control.

We may observe that with the column generationapproach longer network lifetimes are obtained.This is not a surprise, given the complexity of theapproach with respect to the greedy heuristic. Thegreedy approach provides network lifetime valuescloser to those obtained with the column generationapproach when the network size is larger in terms ofsensor nodes. This is rather encouraging when con-sidering a realistic network scenario, since the col-umn generation approach can be barely used with

400 A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402

networks with more than hundreds of sensors due toits computational complexity. However, whenincreasing the number of points to be covered, thegreedy approach is significantly outperformed bythe column generation approach.

We have also tested the gain in lifetime that canbe obtained by relaxing the constraint on the qualityof coverage. In Table 6, we report average lifetimesobtained by requiring only 90% coverage, bothusing the column generation and the greedyapproach. To make the table more readable we listthe percentage gain with respect to the solutionobtained by the same approach when 100% cover-age is required. We do not report results for all clas-ses, as with 5 nodes relaxing the coveragerequirement from 100% to 90% makes little sense.We see that with the column generation approachlonger lifetimes are obtained when relaxing the con-straint on coverage to 90%, whereas the greedyapproach is apparently unable to exploit this possi-bility to increase network lifetime.

Finally, we also carried out a limited set of exper-iments to check the potential benefit of integratingthe two approaches. A natural way to do so is usingthe subnets provided by the greedy approach as aninitial set of columns for optimization. We used thisinitialization for classes 16 and 17, which were themost interesting candidates because of the problemsizes. The results we obtained are quite encouraging:average CPU time decreases from 293 seconds to168 for class 16 and from 436 to 277 seconds forclass. In both cases, the reduction in CPU time isabout 40% on average, while at the single instancelevel minimum and maximum reduction are about15% and 65%, respectively.

Table 6Average lifetime of solutions obtained by column generation andby the greedy approach for 90% coverage

Class Column generation Greedy approach

Tot. LT [days] Gain % Tot. LT [days] Gain %

3 82.9 22.2714 33.01 0.01044 118.6 32.5140 48.92 0.01397 170.0 18.7980 73.11 0.05278 267.6 13.1980 163.65 0.03299 85.5 18.0939 41.32 0.1352

10 42.5 15.8038 21.34 0.141213 368.2 11.0039 324.3 0.000014 545.7 12.4923 457.50 0.000215 187.4 12.2156 167.17 0.003416 94.1 12.2912 81.07 0.122917 46.5 11.5108 32.08 0.1256

7. Conclusions and possible extensions

Two approaches to extend system lifetime in sen-sor networks were presented, the more complex onebeing based on mathematical programming tech-niques, the simpler one on a greedy algorithm. Bothapproaches exploit the high spatial redundancy insensor nodes: only a proper subset of sensors isactive for a given period of time, whereas all othersensors save energy being in inactive state.

Performance analysis reported in the last sectionallowed us to obtain important insights on sensornetwork design, as well as to determine the proper-ties of the two algorithms. In particular, the obtainedresults suggested the following considerations.

(i) When we fix both the number of sensors andthe number of points of interest and vary thesensor sensing/transmission range, the numberof used networks increases significantly. Fur-thermore, under the assumption that the out-put transmit power is negligible, we alsoachieve a longer system lifetime.

(ii) In the case where the sensor range and thenumber of sensors are fixed, the number ofpoints to be monitored has a great impact onthe system lifetime and power consumption;indeed extending the coverage requirementsgreatly reduces the network lifetime.

(iii) Given the sensor range and the number ofpoints of interest, the total lifetime and thenumber of used networks increase as the num-ber of sensors grows.

(iv) Comparing the column generation and thegreedy approach, it is clear that longer net-work lifetimes are achieved through the cen-tralized solution. However, the greedyapproach is able to deal with larger networksdue to its lower computational complexity.The differences in performance between thetwo approaches tend to vanish when large net-works are considered or the number of pointsto be covered is close to the number of sen-sors. In the last case, this effect might also bedue to the fact that with 100% coverage anda large number of points, there is not muchredundancy and the network lifetime is tightlyconstrained.

It should also be mentioned that comparing thecolumn generation and the greedy approach accu-rately is actually difficult. In fact, it is not only a mat-

A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402 401

ter of trading off CPU effort against network life-time. Another issue is the really available informa-tion in a practical setting. For instance, the columngeneration approach can naturally cope with cover-age levels less than 100%. The same applies for thegreedy approach; however, in a distributed settingthis may be rather difficult. So, comparing the twoapproaches is more a form of cross-validation. Amore detailed comparison should include the simula-tion of communication protocols to implement thenetwork configuration and management approachesto assess their impact on energy consumption.

Another observation is that the greedy approachis able to generate many subnets quickly, which col-lectively yield a good solution. Since the main bot-tleneck of column generation is the solution of aMILP problem to generate a column, in particularfor a large scale problem, the two approaches couldbe easily integrated. A first pass by the greedyapproach may yield a large number of columns,which may be assembled optimally by solving themaster problem. A few iterations of column genera-tion can then be used to see if the overall solutionmay be improved. Some experiments with the mostdifficult classes have suggested that this can result ina significant reduction in computational effort.

We should also emphasize again that a possibleapplication of the column generation approach isnot for on-line network management, but for off-line network design, in order to assess designtrade-offs and to provide a performance benchmarkfor the simulation of distributed algorithms, whichdo not require complex communication protocolsto be implemented in practice.

Although the column generation approach hasthe drawback of being centralized and fairly com-plex to implement, it is very flexible and can be eas-ily generalized to deal with sensor failures anddifferent quality of service requirements. Indeed,we have noticed that relaxing the quality require-ment for coverage results in significantly larger life-times by using the mathematical programmingapproach, but not so with the greedy one. We out-line here a few interesting possibilities.

• Capacity constraints on nodes. We have not con-sidered capacity constraints on sensors nodes interms of information processing capability,assuming that this is not a bottleneck. Con-straints on node throughput may be easily addedto our model formulation.

• Multiple coverage and redundancy elimination. Wehave assumed that each point is covered by atmost one sensor. Allowing for multiple coverageis trivial per se, but dealing with it correctly mayrequire proper modeling of redundancy elimina-tion. This is easy if this task is assigned to thegateway. Redundancy elimination along therouting chain may contribute to increase networklifetime by reducing energy consumption fortransmission. In principle, this can be achievedby modeling a multi-commodity network flowproblem, where commodities are associated tothe originating points. Clearly this wouldincrease the CPU effort, and practical networkmanagement as well. However, by solving theoptimization model off-line, a network designercan gain useful insights into the possible gainsin term of network lifetime.

• Unreliable sensors. Cheap sensors may be unreli-able. Coping with reliability may take two forms.On the one hand, we may require that each subnethas some built-in quality from the point of view ofreliability. There is a fair amount of literature ondesigning redundant networks; the column gener-ation approach may be easily applied in thisframework, although the subnet generation sub-problem would be more complex. As an alterna-tive, one may store the set of columns generatedby the algorithm in order to switch network con-figuration when sensor failure is detected.

Acknowledgement

We acknowledge the support of CNR GrantCNRC00BE35, Coordinated Project Stochastic pro-gramming models for design and configuration of tele-

communication networks.

References

[1] C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P.Savelsbergh, P.H. Vance, Branch-and-price: Column gener-ation for solving huge integer programs, OperationsResearch 46 (1998) 316–329.

[2] M. Bhardwaj, A.P. Chandrakasan, Bounding the lifetime ofsensor networks via optimal role assignments, in: Proceed-ings of INFOCOM 2002. Twenty-First Annual Joint Con-ference of the IEEE Computer and CommunicationsSocieties, vol. 3, 2002, pp. 1587–1596.

[3] J. Blazewicz, W. Cellary, R. Slowinski, J. Weglarz, Sched-uling under resource constraints: Deterministic models.Annals of Operations Research, Baltzer, Basel, 1986.

402 A. Alfieri et al. / European Journal of Operational Research 181 (2007) 390–402

[4] L. Booth, J. Bruck, M. Franceschetti, R. Meester, Coveringalgorithms, continuum percolation and the geometry ofwireless networks, Annals of Applied Probability 13 (2)(2003) 722–741.

[5] P. Brandimarte, Numerical Methods in Finance: A MAT-LAB-Based Introduction, Wiley, New York, 2001.

[6] J.-H. Chang, L. Tassiulas, Energy conserving routing inwireless ad hoc networks, in: Proceedings of IEEE INFO-COM 2000, Nineteenth Annual Joint Conference of theIEEE Computer and Communications Societies, vol. 1, 2000,pp. 22–31.

[7] C.F. Chiasserini, E. Magli, Energy-efficient coding and errorcontrol for wireless video-surveillance networks, KluwerTelecommunication Systems (Special Issue on WirelessSensor Networks) 26 (2–4) (2004) 369–387.

[8] M.R. Garey, D.S. Johnson, Computers and Intractability: AGuide to the Theory of NP-completeness, W.H. Freemanand Company, San Francisco, 1979.

[9] I.J. Lustig, J.-F. Puget, Program does not equal program:Constraint programming and its relationship to mathemat-ical programming, Interfaces 31 (2001) 29–53.

[10] S. Slijepcevic, M. Potkonjak, Power efficient organization ofwireless sensor networks, in: Proceedings of IEEE ICC 2001,IEEE International Conference on Communications, vol. 2,2001, pp. 472–476.

[11] K. Sohrabi, J. Gao, V. Ailawadhi, G.J. Pottie, Protocols forthe self-organization of a wireless sensor network, IEEEPersonal Communications 7 (2000) 16–27.

[12] L.F. Wolsey, Integer Programming, Wiley, Chichester,1998.