On Deployment of Multiple Base Stations for Energy-Efficient Communication in Wireless Sensor Networks

Abstract

Data transmission from sensor nodes to a base station or a sink node often incurs significant energy consumption, which critically affects network lifetime. We generalize and solve the problem of deploying multiple base stations to maximize network lifetime in terms of two different metrics under one-hop and multihop communication models. In the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution and a heuristic approach based on the minimal enclosing circle algorithm to deploy a base station at the geometric center of each cluster. In the multihop communication model, both base station location and data routing mechanism need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing paths for data transmission. Simulation results show the distinguished performance of the proposed deployment algorithms in maximizing network lifetime.

1. Introduction

Wireless sensor networks (WSNs) are becoming increasingly pervasive in many military, civil, agricultural, and industrial applications. In sensor networks deployed in harsh or unstructured environments, sensor nodes are typically powered by irreplaceable batteries with a limited amount of energy supply. Minimizing the total energy consumption and optimizing the network-wide load balance to prolong the lifetime of sensor networks have been an essential task in sensor network implementation.

Data transmission from a sensor node to a base station (BS) or a sink node often consumes a significant amount of energy and to a large degree determines the operation hours of the sensor, which in turn affects the lifetime of the entire network. Typically in large-scale sensor networks, it is not always sufficient to deploy one single BS for the entire network, and the advantages of deploying multiple base stations (BSs) are fourfold: (i) shorten the distance between sensors and BSs to cut down the amount of energy consumption on data transmission; (ii) expand network connectivity to improve communication coverage (iii) increase data rate and reduce message delay of the network; and (iv) provide backup routes and sinks for better fault tolerance. However, determining the locations of these BSs is an extremely complex task because their optimal locations depend on a wide variety of factors including the network topology, communication model, routing mechanism, and lifetime metric.

We generalize and solve the problems of deploying multiple BSs in WSNs to maximize network lifetime under both one-hop and multihop communication models for different lifetime metrics. In the one-hop communication model, data messages are directly sent to BSs without any intermediate routing, and therefore the sensors far away from BSs deplete their energy faster than those close to BSs. We formulate the BS deployment problem as the NP-complete p-center problem and present an optimal solution for small-scale networks and design an efficient heuristic approach for large-scale ones based on the minimal enclosing circle (MEC) algorithm [1]. In the multihop communication model, sensor nodes that are one-hop away from the BSs, referred to as critical nodes, need to relay data packets for all other nodes, resulting in much faster energy exhaustion than other nodes. A good deployment strategy would place the BSs in the dense areas of a network to mitigate this issue. We propose an iterative algorithm based on rigorous mathematical derivations and geometric optimization techniques to maximize the network lifetime. Moreover, we develop a linear programming model to compute optimal routing paths for data transmission, which provides a theoretical lower bound for evaluating the network lifetime of any given BS deployment scheme. All these algorithms are implemented and tested on a large set of randomly generated simulation networks. Extensive simulation results illustrate the superior performance of the proposed BS deployment algorithms in comparison with existing methods.

The rest of the paper is organized as follows. In Section 2, we conduct a survey of BS deployment problems and strategies that are closely related to our work. In Section 3, we construct the energy models and formulate the BS deployment problems under different routing models. In Sections 4 and 5, we propose either optimal algorithms or heuristic approaches to deploy BSs for maximizing the lifetime of networks with one-hop and multihop communication models. The simulation results are presented in Section 6 to evaluate the efficiency of the proposed algorithms. We conclude our work in Section 7.

2. Related Work

The deployment of BSs is a fundamental and crucial task in the implementation and operation of WSNs. The number of BSs is a critical factor of the sensor network architecture that significantly affects the network performance. There exist several efforts in deploying a single BS [2, 3] or multiple BSs [4–9]. Most of these studies assume that the number of available BSs is known a priori. Sensor nodes and BSs are usually deployed in a two-dimensional planar area. In an arbitrary network graph, finding the optimal locations for a given number of BSs to maximize network lifetime is very challenging as the search space is considered infinite. Researchers often formulate this problem as an integer linear programming (ILP) task [6, 9] and restrict the possible locations of BSs to a number of given feasible sites or simply the locations of sensor nodes. Meanwhile, the optimal multihop flow-based routing is calculated by solving a linear programming-(LP) modeled problem with given BS locations. However, this approach has several limitations. First, ILP is NP-complete so it does not scale well for networks with a large number of sensors. Second, since the locations of BSs are restricted, the ILP solution can only select the optimal locations among a limited set of possible locations. Several other efforts in BS deployment [4, 5, 7] employ iterative clustering algorithms such as k-means algorithm.

The problems we consider and the solutions we propose in this paper are different from those described above in several aspects. In our problems, the locations of BSs are not restricted to a set of given sites. We consider both one-hop and multihop communication models for evaluating different types of network lifetime. Furthermore, we integrate a number of geometric optimization techniques into our solutions to the BS deployment problems for network lifetime maximization.

3. Energy Model and Problem Formulation

3.1. Energy Model

Table 1 lists all the notations used in this paper. For a sensor node, we assume that the data transmission consumes most of the energy. Each sensor generates a fixed-sized data message of s bits in every round (or period) and transmits it to one of the BSs via either a one-hop or multihop path. We further assume that sensors are able to adjust their transmission power levels on a continuous scale according to the wireless link distance. Our energy model is based on the first-order radio model described in [10]. The energy dissipation in transmitting one data message from sensor i to sensor j over a direct wireless link can be modeled as

$\begin{array}{c}{e}_{i,j}^t=\left({ϵ}_{\text{elec}}+{ϵ}_{\text{amp}}·d_{i,j}^2\right)·s,\end{array}$

(1)

where ${ϵ}_{\text{elec}}=50\hspace{0.17em}\text{nJ}/\text{bit}$ , ${ϵ}_{\text{amp}}=100\hspace{0.17em}\text{pJ}/\text{bit}/{\text{m}}^2$ , and $d_{i,j}$ is the Euclidean distance between sensors i and j. The energy dissipation in receiving one data message at sensor i can be modeled as

$\begin{array}{c}{e}_i^r={ϵ}_{\text{elec}}·s.\end{array}$

(2)

Table 1

A list of notations used in the network model.

Symbol	Definition
s	The size of one data message in bits
${ϵ}_{\text{elec}}$	Distance-independent term in energy model
${ϵ}_{\text{amp}}$	Distance-dependent term in energy model
$d_{i,j}$	Euclidean distance between sensors i and j
$e_{i,j}^t$	Energy cost for transmitting one data message
	from senor i to j
$e_i^r$	Energy cost for receiving one data message at
	sensor i
N	Number of sensors
K	Number of base stations
$(x_i,y_i)$	Coordinate of sensor i
η	Maximum percentage of sensors allowed to
	die before the network is deemed unusable
$n^{*}$	Maximum number ( $N·\eta$ ) of sensors allowed
	to die before the network is deemed unusable
T	Network lifetime in rounds
$e_0$	Initial energy of a sensor
$f_{i,j}$	Total number of data messages from sensor i
	to j in T
$f_{i,B_j}$	Total number of data messages from sensor i
	to base station $B_j$ in T
$C_i$	MEC for sensors within cluster i
$C^{*}$	MEC with maximum radius
$r_i$	Radius of $C_i$
$r^{*}$	radius of $C^{*}$
$r_c$	Radio communication range of sensor
$w_i$	Crowdedness of sensor i

3.2. Network Lifetime Definition

In general, the lifetime of WSNs is defined as the number of rounds until the network operation terminates due to the increasing number of dead sensor nodes. We use η to represent the maximum percentage of sensors that are allowed to die before the network is deemed unusable. When $\eta =0$ , the death of the first node breaks down the entire network, which defines the Cooperative Lifetime (CL) [10, 11]; when $\eta >0$ , a certain number of nodes may run out of energy without interrupting the normal operation of the network, which defines the Whole Lifetime (WL) [7, 12].

3.3. Problem Formulation

The multiple BSs deployment problem is formulated as follows. Given a WSN represented as a graph $G(V,E)$ , where V represents the set of N sensor nodes and E represents the set of wireless links, coordinates $(x_i,y_i)$ of node $v_i$ ( $v_i\in V$ ), and the number K of BSs, how to deploy K BSs so that the network lifetime is maximized? Obviously, the optimal locations of BSs depend on the communication models and lifetime metrics. For both lifetime metrics, that is, CL ( $\eta =0$ ) and WL ( $\eta >0$ ), we categorize the BSs deployment problems based on the adopted communication model as follows.

• (i)

BS deployment using one-hop communication (BSD-1). In this model, every sensor sends its data directly to the closest BS, which means that no routing is needed within the cluster.

(ii)

BS deployment using multihop communication (BSD-M). In this model, data generated by sensors is routed to BSs via multihop paths. To achieve the performance optimality, the routing path from each sensor to the BS is not fixed so that data may go through different paths at different times to reach the BS.

BSD-M needs to jointly consider the BS deployment and routing mechanism. Let T represent the network lifetime measured as the number of rounds, $(x_{B_i},y_{B_i})$ represent the coordinates of BS $B_i$ , and $f_{i,j}$ and $f_{i,B_j}$ represent the total number of data messages from sensor i to sensor j and BS $B_j$ during T, respectively. At each round, every sensor node generates and sends one data message of the same size. We consider an optimal routing mechanism where data messages are allowed to be transmitted to the BSs via multiple paths so that $f_{i,j}$ and $f_{i,B_j}$ are not restricted to be integers, neither is T. We formulate this problem as a quadratic programming task:

$\begin{array}{c}\begin{array}{c}\text{Objective}:\mathrm{Max}\hspace{0.17em}\left(T\right)\end{array}\end{array}$

(3)

subject to

$\begin{array}{c}{\displaystyle \sum }_{j=1,j\ne i}^N{f}_{j,i}+T={\displaystyle \sum }_{j=1,j\ne i}^N{f}_{i,j}+{\displaystyle \sum }_{j=1}^K{f}_{i,B_j},\end{array}$

(4)

$\begin{array}{c}{e}_i^r·{\displaystyle \sum }_{j=1,j\ne i}^N{f}_{j,i}+{\displaystyle \sum }_{j=1,j\ne i}^N{e}_{i,j}^t·f_{i,j}+{\displaystyle \sum }_{j=1}^K{e}_{i,B_j}^t·f_{i,B_j}\le e_0.\end{array}$

(5)

At every sensor node i, any valid routing solution must respect both flow balance defined in (4) and energy constraint defined in (5). The transmission cost $e_{i,B_j}^t$ in (5) can be expressed as

$\begin{array}{c}{e}_{i,B_j}^t=\left({ϵ}_{\text{elec}}+{ϵ}_{\text{amp}}·\left[{\left(x_i-x_{B_j}\right)}^2+{\left(y_i-y_{B_j}\right)}^2\right]\right)·s,\end{array}$

(6)

which is a quadratic function of BS coordinates. Since quadratic programming is NP-complete [13], so is BSD-M. We would like to point out that this optimal routing mechanism is limited to CL and is intended to provide a theoretical lower bound for evaluating the lifetime performance of any given BS deployment scheme. For WL with $\eta >0$ , we can employ a general minimal energy cost routing algorithm that minimizes the total transmission energy cost for lifetime evaluation.

4. Algorithm Design for BSD-1

In the one-hop communication model, each sensor sends its data to the closest BS directly. Thus, the sensors far away from the BSs drain their energy faster than others. The problem of deploying a single BS in one-hop communication model has been well studied in the literature [2]. Here, we consider deploying multiple BSs to maximize the network lifetime, which is denoted by parameter η, $\eta \in [\mathrm{0,1}]$ . Note that BSD-1 can be reduced to the Euclidean p-center problem in ${ℝ}^2$ when $\eta =0$ , but not when $\eta >0$ . Therefore, the optimal BS locations may not be the same under these two lifetime metrics. We propose different algorithms to BSD-1 problems with different values of η.

4.1. BSD-1 with $\eta =0$

For $\eta =0$ , all sensors must cooperate with each other so that the entire network fails when the first sensor runs out of energy, which is identified as the critical node and determines the network lifetime. In a homogeneous WSN where all sensors have identical initial energy, we prove that BSD-1 with $\eta =0$ can be reduced to the Euclidean p-center problem, which is NP-complete when p is part of the input [14]. When $p=1$ , it is called one-center problem, or Minimal Enclosing Circle (MEC) problem, which is polynomially solvable.

Theorem 1.

BSD-1 with $\eta =0$ is NP-complete.

Proof.

In the one-hop communication model, each sensor only consumes energy on transmitting data to its closest BS, so the network lifetime can be calculated by

$\begin{array}{c}T=\underset{1\le i\le N}{\min \hspace{0.17em}}\frac{e_0}{{\min \hspace{0.17em}}_{1\le j\le K}\hspace{0.17em}{e}_{i,B_j}^t},\end{array}$

(7)

where $e_0$ is a constant. Obviously, the network lifetime T is determined by the sensor that consumes the most energy on transmitting one data message to its closest BS. The transmission cost in (1) and lifetime measurement in (7) indicate that maximizing T is equivalent to minimizing the maximum distance of a sensor to its closest BS. Therefore, the optimal BS locations can be determined by minimizing the following objective function:

$\begin{array}{c}\underset{1\le i\le N}{\max \hspace{0.17em}}\underset{1\le j\le K}{\min \hspace{0.17em}}\sqrt{{\left(x_i-x_{B_j}\right)}^2+{\left(y_i-y_{B_j}\right)}^2},\end{array}$

(8)

which is exactly the Euclidean p-center problem where K BSs are the supply points and N sensors are the demand points. Since Euclidean p-center problem is NP-complete, so is BSD-1 with $\eta =0$ .

By reducing BSD-1 with $\eta =0$ to the Euclidean p-center problem, we convert lifetime optimization to geometric optimization. The Euclidean p-center problem has been well studied and there exist a number of algorithms in the literature. For a fixed value K, the best known optimal algorithm using slab dividing approach proposed by Hwang et al. runs in $O(N^{O(\sqrt{K})})$ [15].

Algorithm 1 (IMEC Algorithm).

Step 1.

Initially deploy K BSs at the locations of K sensors randomly chosen out of N sensors.

Step 2.

Cluster the sensors by assigning each of them to its closest BS.

Step 3.

Compute the MEC for the sensors within each cluster and move the BS to the center of the circle if the BS is not located there.

Step 4.

If any BS moves at the previous step, go to Step 2; otherwise, return the BS locations.

For small-scale WSNs, we can apply the optimal algorithm in [15] to solve the BSD-1 problem. Unfortunately, this algorithm does not scale well for WSNs with a large number of sensors. Based on the heuristic proposed in [16] for Euclidean p-center problem, we propose an iterative heuristic algorithm, which calls MEC algorithm for large-scale WSNs. We refer to this algorithm as Iterative Minimal Enclosing Circle algorithm (IMEC), as shown in Algorithm 1.

At each iteration of IMEC algorithm, N sensors are divided into K clusters, each of which contains one BS and at least one sensor. In fact, each BS defines a Voronoi polygon. For those sensors within the same cluster, we compute the MEC to cover them using the algorithms proposed in [1]. In order to minimize the maximum distance between a sensor and the BS, we have to deploy the BS at the center of the circle. Let $C_i$ represent the MEC for cluster i, $r_i$ represent the radius of $C_i$ , and $r^{*}={\max \hspace{0.17em}}_{1\le i\le K}\hspace{0.17em}{r}_i$ , which corresponds to circle $C^{*}$ . Obviously, $r^{*}$ determines T. We have the following lemma.

Lemma 1.

At each iteration of IMEC, $r^{*}$ decreases, T increases.

Proof.

Let $\{C_1,C_2,\dots ,C_K\}$ be the MECs at the current iteration and $r_{\text{old}}^{*}$ the corresponding maximum radius. Step 3 in Algorithm 1 moves BSs to the centers of these circles. At the next iteration, the sensors are clustered by reassigning each of them to its closest BS, so the distance from any sensor to its closest BS can not exceed $r_{\text{old}}^{*}$ ; otherwise, this sensor can not be covered by any $C_i$ . Therefore, the radius of any new MEC that covers all the sensors within the same cluster is at most $r_{\text{old}}^{*}$ . It follows that the updated radius $r_{\text{new}}^{*}\le r_{\text{old}}^{*}$ . Since $r^{*}$ decreases at each iteration, from (1) and (7) we conclude that T increases.

The time complexity of an iteration consists of two main components: one is to divide sensors into K clusters, which can be done in $O(K·N)$ , the other is to compute the MEC, which can be done in linear time $O(N)$ by using the prune-and-search techniques proposed in [1]. Therefore, the time complexity of each iteration is $O(K·N)$ , and the overall time complexity of the heuristic also depends on the number of iterations, which can be preset by the optimization progress as employed in most iteration-based algorithms.

4.2. BSD-1 with $\eta >0$

For $\eta >0$ , the WSN fails when at least $n^{*}=N·\eta$ sensors run out of energy. Therefore, those sensors far away from BSs are allowed to die first. Obviously, it is not necessary to deploy the BS at the geometric center of each cluster. BSD-1 with $\eta >0$ is at least as hard as BSD-1 with $\eta =0$ .

A naive optimal algorithm for this problem would run in time $O((N-n^{*}{)}^{\sqrt{K}}·C_N^{n^{*}})$ , where considers $C_N^{n^{*}}$ possibilities to choose $N-n^{*}$ out of N sensors and takes $O((N-n^{*}{)}^{\sqrt{K}})$ to deploy K BSs on $N-n^{*}$ sensors. This algorithm can be applied to small-scale WSNs but does not scale well to large-scale ones. We propose a heuristic by shrinking MECs and refer to it as Shrink MEC algorithm (SMEC), as shown in Algorithm 2.

Algorithm 2 (SMEC Algorithm).

Step 1.

Initialize the BS locations using IMEC algorithm and cluster the sensors by assigning each of them to its closest BS; compute $C_1,C_2,\dots ,C_K$ ; $n=0$ .

Step 2.

Compute $C^{*}$ with the largest radius.

Step 3.

Select and ignore one of the sensors located on the boundary of $C^{*}$ and recalculate MEC for the remaining sensors within $C^{*}$ such that the updated MEC achieves minimum radius; move the BS to the center of the updated MEC; $n=n+1$ .

Step 4.

If $n<n^{*}$ , go to Step 2; otherwise, return the BS locations.

SMEC uses IMEC to initialize the BS locations. At Step 2, we compute the MEC $C^{*}$ with the largest radius and shrink it at Step 3. In general, an MEC is determined by at least two and at most three sensors. Hence, at Step 3, we only need to compare at most three sensors on the boundary of $C^{*}$ , which are the critical nodes and will run out of energy first. At each iteration, we ignore one of the critical nodes to minimize the radius of MEC for the remaining sensors. Note that ignoring a sensor on the boundary in MEC calculation does not physically remove that sensor from the network, so the actual network topology is not changed. We have the following lemma.

Lemma 2.

At each iteration of SMEC, $r^{*}$ decreases, but T does not necessarily increase.

Proof.

Let $r_{\text{old}}^{*}$ be the corresponding maximum radius at the current iteration. A critical node is removed from $C^{*}$ and then the radius of the updated MEC of the remaining sensors within $C^{*}$ decreases. Meanwhile, the radius of other MECs are smaller than $r_{\text{old}}^{*}$ . Therefore, the maximum radius of the next iteration can not exceeded $r_{\text{old}}^{*}$ . It follows that the updated $r_{\text{new}}^{*}\le r_{\text{old}}^{*}$ . The example in Figure 1 shows that T does not necessarily increase at each iteration. Consider the network in Figure 1 where we allow at most two sensors to die, that is, $\eta =2/N$ . At the current iteration, the largest MEC shrinks by not considering either sensor A or sensor B. Therefore, the SMEC algorithm moves the BS to the center of the shrunk MEC, which, however, will produce a worse lifetime performance than fixing the BS at the original location. In the latter case with the fixed BS location, sensor A and sensor B run out of energy first, but the remaining sensors within the MEC have shorter distances to the BS and therefore achieve a longer lifetime.

Figure 1

An example that supports Lemma 2.

The iteration terminates when $n^{*}$ sensors are taken out of consideration in MEC calculation. The time complexity of each iteration is $O(N)$ . Since there are $n^{*}$ iterations, excluding the time for initialization, the total complexity of the algorithm is $O(n^{*}·N)$ .

5. Algorithm Design for BSD-M

In the multihop communication model, the maximum network lifetime depends on both BS locations and data routing paths. We have formulated BSD-M as an NP-complete quadratic programming problem in Section 3.3. Nevertheless, for given BS locations, since transmission cost $e_{i,j}^t$ and $e_{i,B_j}^t$ in (4) and (5) are known, we can use linear programming based on the simplex algorithm to efficiently compute the theoretically maximum achievable network lifetime T and determine $f_{i,j}$ and $f_{i,B_j}$ for optimal data routing.

We first consider a single BS deployment scenario and rigorously derive the BS location, which is then used in a heuristic designed for the deployment of multiple BSs.

5.1. Single BS Deployment

In the multihop communication model, besides transmitting its own data, a sensor also relays data from other sensors to BSs. Thus, the sensors that are one hop away from a BS need to relay all the data generated by other sensors. Different from the one-hop communication model, the sensors close to a BS may actually run out of energy first. Therefore, a good deployment strategy would consider placing the BS in an area with a high sensor density to prolong the network lifetime. We introduce a new concept, crowdedness, denoted as $w_i$ to describe the density level in sensor i's neighborhood, which is defined as the number of sensors within the radio range of this sensor. Obviously, the BS should be deployed at a place with high crowdedness. Meanwhile, we wish to minimize the total distance from sensors to the BS to reduce the number of data relays. We have the following deployment objective where the distance $d_{i,B}$ between sensor i and BS B is weighted by the sensor's crowdedness:

$\begin{array}{c}\mathrm{Min}\hspace{0.17em}\left({\displaystyle \sum }_{i=1}^N{w}_i·d_{i,B}\right).\end{array}$

(9)

It follows that the optimal BS location is given by

$\begin{array}{c}\left(x_B^{*},y_B^{*}\right)=\underset{(x_B,y_B)}{\text{argmin}}{\displaystyle \sum }_{i=1}^N{w}_i·\sqrt{{\left(x_i-x_B\right)}^2+{\left(y_i-y_B\right)}^2}.\end{array}$

(10)

The objective is achieved by setting the partial derivatives to zero as follows:

$\begin{array}{c}\frac{\partial }{\partial x_B}{\displaystyle \sum }_{i=1}^N{w}_i·{d_{i,B}|}_{x_B=x_B^{*}}={\displaystyle \sum }_{i=1}^N{w}_i·\frac{x_i-x_B^{*}}{d_{i,B}}=0,\\ \frac{\partial }{\partial y_B}{\displaystyle \sum }_{i=1}^N{w}_i·{d_{i,B}|}_{y_B=y_B^{*}}={\displaystyle \sum }_{i=1}^N{w}_i·\frac{y_i-y_B^{*}}{d_{i,B}}=0.\end{array}$

(11)

The optimal location $(x_B^{*},y_B^{*})$ of BS can be obtained by solving the nonlinear (11) using Newton-Raphson method. Let $f_1(x_B,y_B)$ and $f_2(x_B,y_B)$ be the left sides of (11), respectively. Let $(x_B,y_B)$ and $(x_B^{\prime },y_B^{\prime })$ be the BS coordinates at the current and next iterations, respectively. The iterative procedure of Newton-Raphson is defined as

$\begin{array}{c}\left(\begin{array}{c}{x}_B^{\prime }\\ y_B^{\prime }\end{array}\right)=\left(\begin{array}{c}{x}_B\\ y_B\end{array}\right)-{\mathit{J}}^{-1}\left(\begin{array}{c}{x}_B,y_B\end{array}\right)\left(\mathrm{\hspace{0.17em}\hspace{0.17em}}\begin{array}{c}{f}_1(x_B,y_B)\\ f_2(x_B,y_B)\end{array}\right),\end{array}$

(12)

where ${\mathit{J}}^{-1}(x_B,y_B)$ is the inverse of the Jacobian matrix defined as

$\begin{array}{c}\mathit{J}(x_B,y_B)=\left(\begin{array}{cc}\frac{\partial }{\partial x_B}{f}_1(x_B,y_B)& \frac{\partial }{\partial y_B}{f}_1(x_B,y_B)\\ \frac{\partial }{\partial x_B}{f}_2(x_B,y_B)& \frac{\partial }{\partial y_B}{f}_2(x_B,y_B)\end{array}\right).\end{array}$

(13)

We use MEC algorithm [1] to determine the initial values of $(x_B,y_B)$ . The iteration process terminates when the variation of the coordinates is smaller than a specified threshold. Each iteration has a linear time complexity with respect to the number of sensors N.

5.2. Multiple BSs Deployment

The multiple BSs deployment problem is more challenging than the single BS deployment problem, as we need to consider sensor clustering. We propose an iterative algorithm, Iterative Analytical Derivation (IAD), based on the analytical derivation results of the single BS deployment problem, as shown in Algorithm 3.

Algorithm 3 (IAD Algorithm).

Step 1.

Initialize the BS locations using IMEC algorithm. Initialize the number of iterations $i=0$ .

Step 2.

Compute the minimal energy consumption path from each senor to each BS; cluster the sensors by assigning each of them to the BS with the least energy consumption.

Step 3.

Compute the BS location using analytical derivation for each cluster; $i=i+1$ .

Step 4.

If $i<I_{\max \hspace{0.17em}}$ , go to Step 2; otherwise, return the BS locations.

At each iteration of IAD algorithm, we assign each sensor to the BS with highest energy efficiency to minimize the total energy consumption of the network. Inside each cluster, the new BS location is obtained using the same method presented in the single BS deployment scenario. The total energy consumption within each cluster is also minimized by simultaneously considering the deployment of BS in a crowded area to prolong the network lifetime. We set the maximum number of iterations to be $I_{\max \hspace{0.17em}}$ . The time complexity of each iteration is $O(N·(N+K{)}^2·\log \hspace{0.17em}(N+K))$ , which is dominated by the time complexity of Step 2.

6. Simulation Results

In this section, we present the simulation results from the BSs deployment experiments on a number of randomly generated networks with various sizes. We implement and evaluate the performance of the proposed deployment algorithms in comparison with several existing ones.

In the simulation setup, we consider a network of sensors that are randomly placed in a square-shaped planar area. Different networks are created by varying the network size and the number of given BSs. Each sensor has a communication radio range of $60\hspace{0.17em}\text{m}$ and an initial energy capacity of $2J$ , and generates a data message of 200 bytes during each round. The energy cost model for data transmission between each pair of sensors conforms to (1) and (2).

6.1. Performance of IMEC Algorithm

IMEC algorithm is designed for BSD-1 problem to maximize CL performance when $\eta =0$ , where the network lifetime is determined by the maximum radius of the MECs for all clusters. We randomly generate 200 sample networks with 15 sensors and 3 available BSs placed in $100\hspace{0.17em}\text{m}\times 100\hspace{0.17em}\text{m}$ region. For each of these networks, we run our IMEC algorithm and the optimal algorithm proposed in [16], and compute their corresponding lifetime. Note that this optimal algorithm is only used as a comparison base in small-scale networks. We do not compare these two algorithms in large-scale networks because the optimal algorithm has a computational complexity of $O(N^{2K+1})$ and is prohibitively expensive when network sizes are large. The histogram-like performance comparison is shown in Figure 2, where the x-axis represents the ratio of lifetime obtained by the optimal algorithm and IMEC, and y-axis represents the number of sample networks fall in each ratio range. We observed that IMEC achieves the optimal performance in 54 out of total 200 sample networks and achieves near-optimal performance (when the ratio of lifetimes is less than 1.2) in more than 130 sample networks. These measurements show that the IMEC algorithm has a probability of $27\text{\%}$ to achieve the global lifetime optimality and $65\text{\%}$ to achieve near-optimality in a statistical sense.

Figure 2

Performance comparison of IMEC and the optimal algorithm in 200 sample networks with N = 15 and K = 3.

6.2. Performance of SMEC Algorithm

SMEC algorithm is designed for BSD-1 problem to maximize WL performance when $\eta >0$ . It employs IMEC algorithm to initialize the BS locations and then shrinks the largest cluster at each iteration. Again, we randomly generate 200 sample networks with 300 sensors and 6 available BSs placed in $500\hspace{0.17em}\text{m}\times 500\hspace{0.17em}\text{m}$ region. For each of the sample networks, we run both SMEC and IMEC algorithms, and compute their corresponding lifetime. The lifetime performance comparison is shown in Figure 3, where the x-axis represents the ratio of lifetime obtained by SMEC and IMEC, and y-axis represents the number of sample networks fall in each ratio range. We observed that SMEC outperforms IMEC in 174 sample networks, achieves the same performance in 6 sample networks, and underperforms in 20 sample networks. In light of Lemma 2, we know that SMEC does not guarantee the lifetime be improved at each iteration. If we build a 2-3 search tree [2] by removing one critical sensor at each iteration, this tree-based search process will have guaranteed better performance than IMEC. However, the complexity of this tree search is exponential, and hence not scalable to large-scale WSNs. These simulation results show that the SMEC algorithm outperforms the IMEC algorithm with a probability of $87\text{\%}$ in a statistical sense.

Figure 3

Performance comparison of SMEC and IMEC algorithm in 200 sample networks with N = 300, K = 6, and $\eta =2\text{\%}$ .

6.3. Performance of IAD Algorithm

IAD algorithm is designed for BSD-M problem that uses multihop communication model to maximize network lifetime. We compare it with two existing algorithms: k-means algorithm [7] and Global algorithm [4]. Again, the sample networks are randomly generated with the placement of 500 sensors in $500\hspace{0.17em}\text{m}\times 500\hspace{0.17em}\text{m}$ region. After the sensors are generated and BSs are placed by using these algorithms, the BSD-M problem with network topology and energy information is converted into an LP task (3), (4), and (5), and the network cooperative lifetime ( $\eta =0$ ) is computed by using the GNU Linear Programming Kit (GLPK) package. In the simulation, we set the maximum number of iterations for these three iterative algorithms to be 5. We conducted two sets of experiments: (i) fix the number of BSs but varying the sensor distribution; and (ii) fix the sensor placement but vary the number of BSs. In each set of experiments, we produce one performance curve for each of these three algorithms as shown in Figures 4 and 5, respectively. In Figure 4, the case number along the x-axis represents the sample networks with different node distributions. The performance curves of all three algorithms in Figure 5 show that the lifetime performance increases almost linearly as the number of BSs increases, which justifies the motivation of deploying multiple BSs in the network. We observed that the proposed IAD algorithm outperforms the other two existing methods. Since neither Global algorithm nor k-means algorithm considers crowdedness, they may not place the BSs in dense areas, hence resulting in few critical nodes around the BSs. The IAD algorithm jointly considers minimizing the total energy cost and maximizing the number of critical nodes, therefore achieving better performance.

Figure 4

Performance comparison of IAD, k-means, and Global algorithms with 5 BSs in response to various sensor distributions.

Figure 5

Performance comparison of IAD, k-means, and Global algorithms with fixed sensor placement in response to various numbers of BSs.

7. Conclusion

In this paper, we investigated the problems of deploying multiple BSs in WSNs to maximize the network lifetime under one-hop and multihop communication models. We formulated the multiple BSs deployment problems as optimization problems and proposed various optimal or heuristic solutions based on geometric optimization techniques and rigorous mathematical derivations. The extensive simulation results illustrated the efficacy of these proposed deployment algorithms.