1 Introduction

Sensor network is a type of wireless ad-hoc network with the nodes of limited hardware, system and power resources. Usually, sensors collect data in order to perform simple computational tasks and to transmit the resulting data to a set of data collectors. Another type of sensors behavior, important in network management, diagnostics, routing is retransmission of data broadcasted over the network. Collecting, processing and transmitting data is energy absorbing and therefore it requires a sensor cooperation, which relies on shearing the energy between the sensors. Most of the sensor’s energy is utilized during the data transmission, this energy requirement grows with the size of the network and the amount of data transmitted over the network. Efficient use of energy by the network nodes becomes crucial to extend their operating time and the lifetime of the whole network. By a sensor network lifetime we mean the period of time until the first node runs out of energy [1,2,3,4,5]. The network lifetime can be defined as the number of cycles the network can perform its functions. Namely, if each node of the network has a battery with the initial energy \(E_0\), then by finding the optimal energy utilization of each node in one cycle of network lifetime \(E_i^{\mathrm{opt}}\) we can determine the number of cycles \(N_{\mathrm{cycles}}=[\frac{E_0 }{ E_{i^{\prime }}^{\mathrm{opt}} }]\) the network can perform its functions until the most overloaded node \(i^{\prime }\) runs out of its energy. Various aspects of the lifetime problem in wireless sensor networks were discussed in the literature [6,7,8,9,10,11,12]. In [6] the maximum lifetime broadcasting problem in sensor networks with mobile nodes was analyzed. For several mobility models of the nodes distributed algorithms for energy-efficient broadcasting was defined and evaluated. Two algorithms, designed based on trees with minimum highest cost edges and the minimum cost paths trees were compared against the algorithm for broadcast data transmission which utilizes the methods for determining the connected dominating set [7]. In [8] where analyzed polynomial time approximation algorithms for solving the set of rooted maximum network lifetime problems, defined by Nutov and Segal [9]. The objective of the problems is to find the maximum-size collection of routing trees rooted at a given node. The analysis of Nutov and Segal’s algorithms allows the authors to improve the approximations ratios for these problems. In [10] the broadcast tree lifetime problem was presented for two models of receiver energy utilization, the model in which the receiver consumes a fixed amount of energy per unit of received data, and the model in which the energy consumed by a receiver is a function of the transmitter signal power. The lifetime of a broadcast tree is the duration until the first node in the tree fails due to battery energy exhaustion. The authors proposed two algorithms which solve the problem and the solutions were proved to be optimal.

In this article we investigate sensor networks in which the solution of the maximum lifetime broadcasting problem is an equal energy, i.e., the energy consumed by the network is evenly distributed over the sensors. We assume that the sensors are static, they utilize the energy only for sending the data and use the point-to-point or point-to-multipoint data transmission. For the point-to-point data transmission scheme the sender transmits the data to a unique receiver. For the point-to-multipoint transmission the transmitter sends in parallel the same data to some set of receivers. Important future of the point-to-multipoint data transmission is the wireless multicast advantage property (the WMA property) [13, 14]. For such transmission the nodes, which are in the range of the transmitting node, can receive the data without additional costs of the transmitter. In the paper we give the solution of the maximum lifetime problem for the point-to-point and point-to-multipoint broadcast data transmission in one dimensional regular sensor networks \(L_N\). To solve the problem in networks for arbitrary dimension we propose two algorithms which allow to construct the set of trees for data broadcasting and balance the energy consumed by the network nodes. The first algorithm determines the minimum node weight spanning trees in a given network. The second algorithm allows construct the set of trees to balance the energy consumed by the network nodes transmitting data along given minimum node weight spanning tree. Similar algorithms, to discussed in this article, are proposed by Kang and Poovendran [15] and by Wieselthier et al. [13, 14]. The Kang and Poovendran algorithm is based on the transmission along the minimum spanning tree (MST) in equally distributed energy network (EDEN). The Wieselthier et al. broadcast incremental power (BIP) algorithm is similar in principle to the Prim’s algorithm for searching the MSTs, but contrary to our algorithm which uses the point-to-point transmission, it exploits the wireless multicast advantage in the construction of the broadcast tree [13]. In some special cases of graphs the minimum node weight spanning trees and the MSTs coincide, which means that to a certain extent our algorithms are a generalization of the Kang and Wieselthier algorithms.

The original contribution of this article is the application of the minimum node weight spanning trees to solve the network lifetime problems for broadcast transmission. To find such trees in a complete graph is an NP-hard problem [16]. Two polynomial time algorithms for searching the minimum node weight spanning trees in a network graph, based on the function generating trees, are defined in [16]. In this article we propose the new one which is a modification of the minimum degree spanning tree algorithm proposed by Fürer and Raghavachari [17]. In the following chapters we show that the minimum node weight spanning tree searching algorithm inherits many features of the Fürer and Raghavachari algorithm and together with the load balancing broadcast algorithm it allows efficiently find the approximation of an equal energy solutions of the maximum network lifetime broadcasting problem.

2 Definition of the Problem

Let us denote by \(S_N\) a one dimensional sensor network build of N nodes. We assume that the nodes are located at the points \(x_i\), \(i\in [1,N]\) of a real line and the k-th node generates and broadcasts the amount \(Q_k\) of data. By \(E(x_i,x_j)\) we denote the data transmission cost energy matrix, which defines the cost of transmission of one unit of data between i-th and j-th node. We assume that the matrix \(E(x_i,x_j)\) is an arbitrary function which satisfies the inequality

$$\begin{aligned} \forall _{0 \le x _i \le x_j\le x_k}\;E(x_i,x_j) + E(x_j,x_k)\le E(x_i,x_k), \end{aligned}$$
(1)

where \(x_i\) is the location of the network nodes on the line R. The data transmission flow matrix \(q^k(x_i,x_j) \equiv q^k_{i,j}\) defines the amount of data which is sent by the i-th node to the j-th node in the process of data broadcasting. If the k-th node broadcasts the amount \(Q_{k}\) of data then the energy consumed by the i-th node to retransmit the data is given by the formula

$$\begin{aligned} E_{i}(q^{k}) = \sum _{j=1, j\ne i}^{N} q_{i,j}^{k} E_{i,j}, \end{aligned}$$
(2)

where \(E_{i,j} \equiv E(x_i,x_j)\). The requirement, that each node must receive \(Q_k\) of data can be written in the form

$$\begin{aligned} \forall _{j\in [1,N], j\ne k} \;\sum _{i=1, i\ne j}^{N} q_{i,j}^{k} = Q_k. \end{aligned}$$
(3)

Our objective is to find a data transmission flow matrix \(q_{i,j}^{k}\), such that the function

$$\begin{aligned} E_{i^{\prime }}(q^{k}) = \max _{i} \{ E_{i}(q^{k}) \}, \end{aligned}$$
(4)

reaches its minimum. The maximum lifetime broadcasting problem, later referred to as MLB problem, is defined by the set of the parameters: the number of nodes \(|S_N|=N\), the amount of data \(Q_k\) which is broadcasted by the k-th node, \(k\in [1,N]\) and the data transmission cost energy matrix \(E_{i,j}\). If the matrix \(E_{i,j}\) is a function of a distance \(d(x_i,x_j)\) between two nodes, then instead of defining the matrix elements \(E_{i,j}\) we can give the location of network nodes in the space and determine the values of \(E_{i,j}\) from the metric \(d(x_i,x_j)\), \(i,j\in [1,N]\). We assume that \(E_{i,j}\) is an arbitrary polynomial function of the distance \(d(x_i,x_j)\) and satisfies (1).

We define a sensor network \(S_N\) as a directed, weighted graph \(G_N=\{S_N, V, E \}\) in which \(S_N\) is the set of graph nodes, V is the set edges and E set of weights. Each directed edge \(t_{i,j}\in V\) defines a communication link between i-th and j-th node of the network. To each edge \(t_{i,j}\) we assign a weight \(E_{i,j}\), which is the cost of transmission of one unit of data between the i-th and j-th node. By \(U^{(\mathrm{out})}_{i} \subseteq S_N\) we denote the set of the network nodes to which the i-th node can send the data

$$\begin{aligned} U^{(\mathrm{out})}_{i}=\{ x_j\in S_N | \;\exists \;t_{i,j}\in V \}. \end{aligned}$$

The set \(U^{(\mathrm{out})}_{i}\) defines the maximum transmission range of the i-th node. In the paper we assume, that each node of \(S_N\) can send the data to any other nodes of the network except to itself, i.e.,

$$\begin{aligned} \forall _{i\in [1,N]}, \;\; U^{(\mathrm{out})}_{i} = S_N\setminus \{x_i\}. \end{aligned}$$
(5)

The set of all spanning trees, which begin in the k-th node we denote by \(G_{k}^{T}\), \(k\in [1,N]\). If the assumption (5) is satisfied, then \(G_N\) is a complete graph and the number of spanning trees rooted at k-th node \(|G_{k}^{T}|\) it is equal to \(N^{N-2}\) [18]. We will identify a tree \(T^{k,r}\) with the set of its graph edges. Because tree \(T^{k,r}\) defines the data flow from the broadcasting node it is a directed tree with ordered edges in the sequence the data is transmitted along that tree. We assume, that edges of the tree \(T^{k,r}\in G_{k}^{T}\) have the natural orientation from the root node to the root child, etc., and are arranged with some fixed, initial sequence

$$\begin{aligned} T^{k,r}=\left( t^{k,r}_{i_1,j_1},\ldots , t^{k,r}_{i_{N-1},j_{N-1}}\right) . \end{aligned}$$
(6)

For a point-to-point data transmission the solution of maximum lifetime broadcasting problem does not depend on the ordering of the edges. The ordering is important for the point-to-multipoint broadcast data transmission, where different orderings of the edges in the tree \(T^{k,r}_{}\) define different wireless multicast data transmission scheme.

By \(q^{k,r}_{i,j}\) we denote the amount of data transmitted along the edge \(t^{k,r}_{i,j}\). The amount of data \(q_{i,j}^{k}\) sent by the i-th node to the j-th node along all trees is given by the formula

$$\begin{aligned} q_{i,j}^{k} = \sum _{r=1}^{N^{N-2}} q^{k,r}_{i,j} t^{k,r}_{i,j}. \end{aligned}$$
(7)

We require, that along each tree the transmitted data is the same, which means that for fixed k and r the data flows along each edge \(t^{k,r}_{i,j}\) are equal, \(\forall _{i,j,i^{\prime },j^{\prime }}\;q^{k,r}_{i,j} = q^{k,r}_{i^{\prime },j^{\prime }}\). We denote it by \(q^{k}_{r}\), i.e.,

$$\begin{aligned} \forall _{i,j} \; q^{k,r}_{i,j} = q^{k}_{r}. \end{aligned}$$
(8)

The objective function of the MLB problem (4) can be rewritten using the variables \(q^{k}_{r}\) and the trees \(T^{k,r}\) in the following formula for the energy of each sensor

$$\begin{aligned} E_{i}^{k}(q^{k}) = \sum _{j=1, j\ne i,k}^{N} \sum _{r=1}^{N^{N-2}} q^{k}_{r} \; t^{k,r}_{i,j}\; E_{i,j}. \end{aligned}$$
(9)

The requirement (3) written in terms of \(T^{k,r}\) and \(q^{k}_{r}\) has the form

$$\begin{aligned} \sum _{r} q^{k}_{r} = Q_k. \end{aligned}$$
(10)

Using the relation (9) and (10) the maximum network lifetime broadcasting problem can be defined by the set of the following formulas

$$\begin{aligned} \left\{ \begin{array}{l} \mathop {\min }\nolimits _{q^{k}} \mathop {\max }\nolimits _{i\in L_N} \{ E_{i}^{k}(q^{k}) \}_{i=1}^{N}, \;k\in [1,N], \\ E_{i}^{k}(q^{k}) = \mathop {\sum }\nolimits _{j=1}^{N} \mathop {\sum }\nolimits _{r}^{} q^{k}_{r}\; t^{k,r}_{i,j}\; E^{}_{i,j},\;\; E^{}_{i,j}\ge 0,\\ T^{k,r} \in G_{k}^{T}, \;q^{k}_{r}\ge 0,\; r\in [1,N^{N-2}], \\ \mathop {\sum }\nolimits _{r} q^{k}_{r} = Q_k,\\ \end{array} \right. \end{aligned}$$
(11)

where \(q^{k}=(q^{k}_{1}, \ldots , q^{k}_{N^{N-2}})\). A solution of the MLB problem (11), when the data is broadcasted by the k-th node, will be given by an optimal set of trees \(\{ T^{k,r}_{} \}_{r=1}^{N^{\prime }} \subset G_{k}^{T}\), \(N^{\prime }\le N\), and \(N^{\prime }\) non-negative numbers \(q^{k,\mathrm{opt}}_{r}\), which satisfy (10) and minimize the objective function (4). The following lemma describes relation between the local minima of the objective function (4) and global solutions of (11).

Lemma 1

Any minimum of the objective function (4) is a solution of the maximum lifetime broadcasting problem.

Proof

The feasible set

$$\begin{aligned} U(q^k)=\left\{ q^k \in R_{+}^{N^{N-2}}\Big | \sum _{r=1}^{N^{N-2}} q^{k}_{r} - Q_k=0 \right\} , \end{aligned}$$

where \(R_{+}\) is a set of non-negative real numbers and is a domain of the objective function \(E(q^{k})\). From the linearity of the set \(U(q^k)\) it follows, that any two points \(q^k_0, q^k_1\in U(q^k)\) can be connected by a line segment and \(\forall _{t\in [0,1]}\; tq^k_0 +(1-t)q^k_1 \in U(q^k).\) The objective function (4) of the maximum lifetime broadcasting problem (11) is piecewise linear in the \(q^k\) variable, which means that \(E(tq^k_0 +(1-t)q^k_1)= t E(q^k_0) +(1-t) E(q^k_1).\) Let us assume, that \(q^k_0\) is a minimum of \(E(q^k)\) and there exists another local minimum \(q^k_1\) such that \(E(q^k_0)< E(q^k_1),\) then from the linearity of \(E(q^k)\) it follows that \(\forall _{t\in [0,1]}\;\; E(t q^k_0 +(1-t)q^k_1)= t E(q^k_0) +(1-t)E(q^k_1) < tE(q^k_1) +(1-t)E(q^k_1)\) and \(\forall _{t\in [0,1]}\;q^k(t)\), the inequality \(E(q^k(t))< E(q^k_1)\) holds, which means that \(q^k_1\) cannot be a minimum of \(E(q^k)\) in \(U(q^k)\) and \(q^k_0\) is a global minimum. \(\quad \square\)

If we assume that \(Q_{k}, \; q_{i,j} \in Z_{+}^{}\) in (11), then we get the mixed integer linear programming problem for the network lifetime. The following lemma describes the complexity of the problem.

Lemma 2

The maximum lifetime broadcasting problem is NP-hard.

Proof

We reduce the partition problem to the MLB problem (11). To solve the MLB problem in \(Z_{0}^{+}\) we must find the set of integer numbers \(\{q^{k}_{r} \}_{r \in [1,N^{N-2}]}\) for all trees from \(G_{k}^{T}\), satisfying the constraint \(\sum _{r} q^{k}_{r} = Q_k\) and which minimizes the objective function (4). Finding such set of numbers \(q^{k}_{r}\in Z_{0}^{+}\) is equivalent to solving the partition problem [19]. \(\square\)

3 Solution of the MLB Problem in One Dimensional Network

In one dimensional networks, the property (1) of the data transmission cost energy matrix \(E_{i,j}\) means that, the lowest cost of delivery of a given amount of data from the i-th node located at \(x_i\) to the j-th node located at \(x_j\) is reached when the data is transmitted between nearest neighbors along the shortest path. By a shortest path we mean a distance between two nodes, \(d(x_i,x_j)=|x_i - x_j|\). It can be easily shown that in one dimension for \(E_{i,j}=|x_i-x_j|^a\), \(x_i,x_j \in R_+\) the inequality (1) is satisfied for any \(a\ge 1\). From the above it follows that any function of the form \(E_{i,j}(\bar{a},\bar{\lambda }) = \sum _{n=0}^{\infty } \lambda _{n} |x_i-x_j|^{a_n}\), where \(\lambda _n\ge 0\), \(a_n \ge 1\) also satisfies (1). Nodes of a regular network \(L_N\) are placed at the points \(x_i=i\) of a line and the distance between neighboring nodes is equal to one, \(d_{i,i\pm 1}=1\). We can assume, without losing the generality of the problem (11) that, \(E_{i,i\pm 1}(\bar{a},\bar{\lambda })=1\), which is equivalent to the requirement that \(\sum _{n=0}^{\infty } \lambda _{n} =1\). By \(E_{r}\) we denote the cost of transmission of one unit of data between nodes which distance is \(d_{i,i+r}=r\), \(i,r \in [1,N]\). The function \(E_{r}\) defines weight for all edges \(t_{i,i+r}\) of a given transmission tree T in \(G_{k}^{T}\) and it has the form

$$\begin{aligned} E_{r}(\bar{a},\bar{\lambda }) = \sum _{n=0}^{\infty } \lambda _{n} r^{a_n}, \;\; r \in [1,N], \end{aligned}$$
(12)

where \(\sum _{n=0}^{\infty } \lambda _{n} =1\), \(\lambda _n\ge 0\) and \(a_n \ge 1\). We show that for one dimensional, regular sensor network \(L_N\) with the data transmission cost energy matrix of the form (12) there exists an equal energy solution of the maximum lifetime broadcasting problem for the nodes which are inside the network, i.e. \(i\in [2,N-1]\), and non equal energy solution for the border nodes, \(i=1,N\) of \(L_N\). The next lemma describes the solution of the MLB problem for the first and last node of the \(L_N\) network.

Lemma 3

The solution of the maximum lifetime broadcasting problem (11) with \(E_{i,j}\) satisfying (1), for the first and last node of the \(L_N\) network is given by the transmission graphs \((t_{1,2},\ldots , t_{N-1,N})\) and \((t_{N,N-1},\ldots , t_{2,1})\) with the data flow \(Q_1\) and \(Q_N\) respectively.

Proof

From the property (1) of the data transmission cost energy matrix \(E_{i,j}\) it follows that, the nodes consume minimal energy when they send all of their data to the nearest node. Because the distance between the neighboring nodes of the regular network \(L_N\) is the same, then the energy spent by each node to transmit a given amount of data to its neighbor is also the same. From this it follows that, when the broadcasted data \(Q_1\) is transmitted along the edges \(t_{i,i+1}\), \(i\in [1,N-1]\), then each node \(i\in [1,N-1]\) spends the same, minimal amount of energy. This means that the optimal transmission graph, the solution to the MLB problem, for the first node is given by the set of graph edges \((t_{1,2} ,\ldots , t_{i,i+1},\ldots , t_{N-1,N})\) with the data flow \(Q_1\). In a similar way we can find the solution of (11) for the last node of the \(L_N\) network. It is given by the transmission graph \((t_{N,N-1} ,\ldots , t_{i,i-1},\ldots , t_{2,1})\) and the data flow \(Q_N\). \(\quad \square\)

The next theorem describes the solution of (11) for the one dimensional, regular sensor network \(L_N\), when the data is broadcasted by the internal nodes, \(k\in [2,N-1]\) of the network.

Theorem 1

The solution of the maximum lifetime broadcasting problem (11), with the data cost energy matrix of the form (12), when the data is broadcasted by the k-th node, \(k\in [2,N-1]\), is an equal energy solution and it is given by the N transmission trees \(T^{r}\), \(r\in [1,N]\)

$$\begin{aligned} \begin{array}{lll} (t^{r}_{k,k-1},\ldots ,t^{r}_{2,1}, t^{r}_{r,k+1},t^{r}_{k+1,k+2},\ldots , t^{r}_{N-1,N}), &\quad r\in [1,k-1],\\ (t^{k}_{k,k-1},\ldots , t^{k}_{2,1}, t^{k}_{k,k+1},\ldots , t^{k}_{N-1,N}), &\quad r=k,\\ (t^{r}_{k,k+1}, \ldots , t^{r}_{N-1,N}, t^{r}_{r,k-1}, t^{r}_{k-1,k-2},\ldots , t^{r}_{2,1}), &\quad r \in [k+1,N], \\ \end{array} \end{aligned}$$
(13)

with the data flows

$$\begin{aligned} q^k_r = \left\{ \begin{array}{llll} \frac{E_1}{E_k} q^k_k + \frac{E_1}{E_k} Q_k, & r=1, \\ \frac{E_1}{E_{k+1-r}} q^k_k, \;\;\;\;r\in [2, k-1], & k\ge 3,\\ \frac{E_1}{E_{r-k+1}} q^k_k, \;\;\;r\in [k+1, N-1], & k\le N-2, \\ \frac{E_1}{E_{N-k+1}} q^k_k + \frac{E_1}{E_{N-k+1}} Q_k, & r=N, \\ \end{array} \right. \end{aligned}$$
(14)

where

$$\begin{aligned} q^k_k = \frac{1 - \frac{E_1}{E_k} - \frac{E_1}{E_{N-k+1}} }{-1+ \sum _{i=1}^{k} \frac{E_1}{E_i}+ \sum _{i=1}^{N-k+1} \frac{E_1}{E_{i}} } \;Q_k. \end{aligned}$$
(15)

Proof

We assume that the formulas (13) and (14) are solution to the MLB problem for N and show that it is also true for \((N+1)\). After adding the \((N+1)\)-th node at the end of the network, the nodes from the \(L_{N}\) subnetwork can transmit data to the \((N+1)\)-th node by the trees \(T^{r^{\prime }}(L_{N+1})\), \(r^{\prime }\in [1, N^{\prime }]\) such, that \(T^{r^{\prime }}(L_{N+1})|_{L_N}=T^{r}\) and \(T^{r}\) are given by (13). Because all \(Q_{k}\) of data must be delivered to the \((N+1)\)-th node by the nodes from the \(L_N\) subnetwork, then for data transmission cost energy matrix satisfying (1) the lower costs of delivery of these data is when the N-th node passes all \(Q_{k}\) of data to the \((N+1)\)-th node by the ‘next hop’ data transmission, consuming the amount

$$\begin{aligned} E^k_{N}=E_1 Q_{k} \end{aligned}$$

of energy. The trees \(T^{r^{\prime }}(L_{N+1})\) for optimal data transmission from the \(L_N\) subnetwork are given by the ordered set of edges

$$\begin{aligned} T^r(L_{N+1}) = ( T^{r},T^{r}_{N,N+1}), \;\;r\in [1,N], i,j\in [1,N], \end{aligned}$$
(16)

where the edges of the \(T^{r}\) tree are given by (13).

Because, the \((N+1)\)-th node takes part in data retransmissions, we must find set of trees which are rooted in the k-th node such that the \((N+1)\)-th node is not a leaf. From (16) we know that all \(Q_{k}\) of data is transmitted to the \((N+1)\)-th node from the \(L_N\) subnetwork by the next hop data transmission graph, starting from the \((k+1)\)-th node. It means that the first \((N+1-k)\) edges of the optimal trees \(T^{r^{\prime \prime }}\), \(r^{\prime \prime }\in [N+1, N^{\prime }]\) are

$$\begin{aligned} T^{r^{\prime \prime }}=\left( t^{r^{\prime \prime }}_{k,k+1}, \ldots ,t^{r^{\prime \prime }}_{N,N+1}, \ldots \right) . \end{aligned}$$
(17)

The nearest node to which the \((N+1)\)-th node can send the \(q^{k}_{r^{\prime \prime }}\) data, without transmitting data in a loop, is the \((k-1)\)-th node. It means that next edge, which we must add to the set (17) is \(t^{r^{\prime \prime }}_{N+1,k-1}\). The next edges in the trees (17), which define the most efficient data transmission for \(E_{i,j}\) satisfying (1), are \(t^{r^{\prime \prime }}_{k-i,k-i+1}\), \(i\in [1,k-1]\). From the above it follows, that the optimal data transmission tree for the \((N+1)\)-th node to retransmit part of the broadcasted data in the \(L_{N+1}\) network is given by the formula

$$\begin{aligned} T^{N+1} = \left( t^{N+1}_{k,k+1}, \ldots ,t^{N+1}_{N,N+1}, t^{N+1}_{N+1,k-1}, t^{N+1}_{k-1,k-2}, \ldots , t^{N+1}_{2,1}\right) , \end{aligned}$$
(18)

which is the \((N+1)\) tree in (13) in the \(L_{N+1}\) network.

We show that, to obtain the set of trees which forms the solution of MLB problem in \(L_{N+1}\) it is enough to add a one tree \(T^{N+1}\) to the solution of the problem in \(L_N\) network. For the set of trees \(\{T^{r}, T^{N+1}\}_{r=1}^{N}\) given by (13) and (18) and the transmitted data \(\{q^{k}_{r},q^{k}_{N+1}\}_{r=1}^{N}\) an equal energy requirement can be written in the form

$$\begin{aligned} E_{i}(q^{k}) = E_{i+1}(q^{k}), \;\; i\in [1,N], \end{aligned}$$
(19)

where

$$\begin{aligned} E_{i}(q^{k}) = \left\{ \begin{array}{lllll} q^k_{1} E_{k},&\quad i=1, \\ q^k_{i} E_{k+1-i} + Q_k E_1,&\quad i\in [2,k], \\ q^k_{i} E_{i-k+1} + Q_k E_1,&\quad i\in [k+1, N-1], k \le N-1, \\ q^k_{N} E_{N-k+1} + Q_k E_1,&\quad i=N, \\ q^k_{N+1} E_{N-k+2},&\quad i=N+1. \\ \end{array} \right. \end{aligned}$$

By a direct computation we can check that the solution of the equations (19), with the requirement \(\sum _{r=1}^{N+1} q^{k}_{r} = Q_k\), is given by (14) for the \(L_{N+1}\) network. \(\quad \square\)

The Fig. 1 shows the optimal set of N trees for a solution of the MLB problem in \(L_N\) when the data is broadcasted by the k-th node, \(k\in [2,N-1]\).

Fig. 1
figure 1

A collection of trees that solve the MLB problem in \(L_N\)

Full size image

The next lemma shows that for a sufficiently large network \(L_N\), when the number of nodes grows, the energy \(E_i^{k}\), \(k\in [2,N-1]\) of each node decreases.

Lemma 4

For the solution of the MLB problem given by (13)–(15) the energy of each node \(E_{i}^{k}(L_{\infty })\), \(i\ge 1\), \(k \ge 2\) is given by

$$\begin{aligned} E_{i}^{k}(L_{\infty }) = \left( 1+ \frac{1 - \frac{E_1}{E_k} }{ \sum _{r=1}^{k} \frac{E_1}{E_r} + \sum _{r=1}^{\infty } \frac{E_1}{E_{r}}}\right) E_1 Q_k. \end{aligned}$$
(20)

Proof

The solution (13)–(15) is an equal energy solution with the energy of each node \(E^k_i(L_N) = E_1 q^k_k(L_N) + E_1 Q_k\), \(i\in [1,N]\), \(k\in [2,N-1]\), where \(q^k_k(L_N)\) is given by (14). For \(N \rightarrow \infty\) the energy \(E^k_i(L_N)\) has the limit (20). \(\quad \square\)

4 Broadcast Transmission with Wireless Multicast Advantage

In the first section we defined \(G_{k}^{T}\) as the set of all spanning trees of the graph \(\{L_N, V, E \}\) rooted at the k-th node and we assumed that edges of each tree \(T^{k,r}\) were arranged in some fixed sequence. Because any WMA transmission along given tree \(T^{k,r}\) is defined by some ordering of its edges \(t^{k,r}_{i,j}\), we extend the set \(G_{k}^{T}\) and add to it \((\alpha _r-1)\) trees \(T^{k,r,\alpha }\) obtained by reordering edges of the tree \(T^{k,r}\). Any ordered tree \(T^{k,r,\alpha }\), \(\alpha \in [1,\alpha _r]\), where \(T^{k,r,1}=T^{k,r}\) is an initial ordering (6), defines the method of WMA data transmission. We denote the set of all trees \(T^{k,r,\alpha }\), \(\alpha \in [1,\alpha _r]\), \(r\in [1,N^{N-2}]\) rooted at the k-th node by \(\overline{G}_{k}^{T}\). In Fig. 2 there are two different orderings of a tree rooted at the second node of the \(L_6\) network shown, which define different WMA data transmissions.

Fig. 2
figure 2

Two nonequivalent WMA data transmissions along the same tree in \(L_6\)

Full size image

The numbers on the edges denote the sequence the data is transmitted along the tree and the doted lines indicate the costless transmission.

Let us denote by \(E_{i,j}(q)\) the energy consumed by the i-th node to transmit the amount q of data to the j-th node. By \(U^{}_{i,j}\) we denote the set of network nodes which are in the transmission range of the i-th node, when the data is transmitted to the j-th node, and can receive the transmitted data without additional cost of the transmitter

$$\begin{aligned} U^{}_{i,j} = \{ n \in S_N | \; E_{i,j}(q)>0 \Rightarrow E^{}_{i,n}(q)=0 \}. \end{aligned}$$

From the definition of \(U^{}_{i,j}\) it follows, that the data transmitted by the i-th node to the j-th node and nodes from \(U^{}_{i,j}\) is parallel and is performed along the edges \(\{ t_{i,j}, t_{i,n}\}_{n \in U^{}_{i,j}}\) of some tree T. Definition of the a set \(U(t^{k,r}_{i,j})\equiv U^{k,r}_{i,j}\) for each edge of a tree \(T^{k,r} \in G_{k}^{T}\) is equivalent to the definition of some ordered tree \(T^{k,r,\alpha }\in \overline{G}_{k}^{T}\), \(\alpha \in [1,\alpha _r]\) and some WMA data transmissions along \(T^{k,r}\). It may happen that different trees \(T^{k,r,\alpha }\) and \(T^{k,r^{\prime },\alpha ^{\prime }}\) from \(\overline{G}_{k}^{T}\) define equivalent WMA data transmissions. Figure 3 shows an ordered tree which defines WMA data transmission equivalent to the transmission along the first tree in Fig. 2.

Fig. 3
figure 3

Parallel WMA data transmission along a tree in \(L_6\)

Full size image

By \(q^{k}_{r,\alpha }\) we denote the data transmitted along the ordered tree \(T^{k,r, \alpha }\in \overline{G}_{k}^{T}\). The WMA set \(U^{}(t^{k,r, \alpha }_{i,j})\equiv U^{k,r,\alpha }_{i,j}\) for the data transmission along the tree \(T^{k,r, \alpha }\) we define as follows

$$\begin{aligned} U^{k,r,\alpha }_{i,j} = \left\{ n \in S_N| E^{}_{i,j}(q^{k}_{r,\alpha }) >0 \Rightarrow \forall _{m\in S_N} E^{}_{m,n}(q^{k}_{r,\alpha })=0\right\} . \end{aligned}$$

We also assume that

$$\begin{aligned} E^{}_{m,n}(q^{k}_{r,\alpha })=0 \Rightarrow U^{k,r,\alpha }_{m,n}=\emptyset . \end{aligned}$$
(21)

In other words the WMA property cannot be applied to the data transmission for which \(E_{m,n}(q)=0\). Note, that 21 is a non-trivial assumption for the directional antennas. The data transmission cost energy matrix for each edge of the tree \(T^{k,r, \alpha }\), \(E^{}_{i,j}(T^{k,r, \alpha })\equiv E^{k,r,\alpha }_{i,j}\) having the WMA property and satisfying (21) can be defined by the following formulas

$$\begin{aligned} E^{k,r,\alpha }_{i_n,j_n} = \left\{ \begin{array}{lll} E^{}_{i_1,j_1}, &\quad n=1,\\ E^{}_{i_n,j_n}, \; j_n \notin \mathop {\bigcup }\nolimits _{s=1}^{n-1} U^{k,r,\alpha }_{i_s,j_s}, &\quad n\in [2,N-1],\\ 0,&\quad j_n \in \mathop {\bigcup }\nolimits _{s=1}^{n-1} U^{k,r,\alpha }_{i_s,j_s}.\\ \end{array} \right. \end{aligned}$$
(22)

The energy consumed by the i-th node, written in terms of \(E^{k,r,\alpha }_{i,j}\), equals

$$\begin{aligned} E_{i}(q^{k}) = \sum _{j=1, j\ne i,k}^{N} \sum _{r,\alpha }^{} q^{k,\alpha }_{r} \; t^{k,r,\alpha }_{i,j}\; E^{r,\alpha }_{i,j}. \end{aligned}$$
(23)

The objective function of the MLB problem with WMA property has the form (4), where the node energy \(E_{i}(q^{k})\) is given by (23). The following lemma describes a solution of the MLB problem with WMA property when the nodes of the \(L_N\) network use the bidirectional antennas.

Lemma 5

For the bidirectional antenna the solution of the MLB problem with the wireless multicast advantage property and \(E_{i,j}\) satisfying (1) is given by the transmission tree

$$\begin{aligned} \left( t_{k,k-1}^{k},\ldots ,t_{2,1}^{k}, t_{k,k+1}^{k},\ldots , t_{N-1,N}^{k}\right) \end{aligned}$$
(24)

and the data flow \(Q_k\), \(k\in [2,N-1]\).

Proof

Since the distance between the neighboring nodes in the \(L_N\) network is equal to one, then for a bidirectional antenna the data transmitted by the k-th node, \(k\in [2,N-1]\) to the \((k-1)\)-th node is delivered to the \((k+1)\)-th node without costs. In other words, the amount \(Q_k\) of data transmitted along the edges \((t_{k,k-1}^{k}, t_{k,k+1}^{k})\) are delivered to the both nodes \((k\pm 1) \in L_N\) with the minimal costs \(E_{k}^{k}=Q_k\) of the k-th node. From Lemma 3 we know that, the optimal tree to transmit the amount \(Q_k\) of data from the \((k-1)\)-th node to the nodes \(i\in [1,k-2]\) of the \(L_N\) network is given by the sequence of edges \((t_{k-1,k-2}^{k},\ldots ,t_{2,1}^{k})\) and the energy consumed by each node is qual \(E_{i}^{k}=Q_k\), \(i\in [2,k-2]\) and \(E_{1}^{k}=0\). Similarly, the optimal tree to transmit the amount \(Q_k\) of data from the \((k+1)\)-th node to the nodes \(i\in [k+2,N]\) of the \(L_N\) network is given by the sequence of edges \((t_{k+1,k+2}^{k},\ldots , t_{N-1,N}^{k})\) and the energy utilized by each node is qual \(E_{i}^{k}=Q_k\), \(i\in [k+2,N-1]\) and \(E_{N}^{k}=0\). This optimal transmission tree up to an ordering is given by (24). \(\quad \square\)

The next theorem states that for the directional antennas and for the internal nodes of the network \(L_N\), i.e. \(k\in [2,N-1]\), the solution of the MLB problem with WMA property coincides with the solution given in (13)–(15).

Theorem 2

For a directional antenna the solution of the MLB problem with the wireless multicast advantage property and \(E_{i,j}\) satisfying (1), for \(k\in [2,N-1]\), \(N\ge 3\) is an equal energy solution and it is given by (13)–(15).

Proof

The proof is basically the as the proof of Theorem 1. \(\quad \square\)

The solutions of MLB problem with the wireless multicast advantage property for the first and the last node of the \(L_N\) network and for both types of antennas, the bidirectional and directional is given by Lemma 3.

5 The Maximum Lifetime Broadcasting Algorithms

In sensor networks in which the nodes are evenly distributed on some area of the plane, we can expect that the solution of the MLB problem is an equal energy, i.e. \(\forall _{i\in S_N} E^{\mathrm{Sol}}_{i}=E_{0}\). For such problem we propose two algorithms which allow to find a set of trees to broadcast the data with balancing the energy consumed in the network nodes. The purpose of the first algorithm is to construct in \(S_N\) the set of minimum node weight spanning trees \(G^{\mathrm{M_{{ nw}}ST}}_{k}\) rooted at the broadcasting node. The second algorithm allows to construct, for a given tree T from \(G^{\mathrm{M_{{ nw}}ST}}_{k}\), the set of trees \(G^{{ LBB}}_{k}(T)\) which is used to balance the energy consumed by nodes of the network \(S_N\). To find an approximate solution of the MLB problem we define the objective function (4) over the set \(G^{{ LBB}}_{k}=\bigcup _{T\in G^{\mathrm{M_{{ nw}}ST}}_{k} } G^{{ LBB}}_{k}(T)\) and find its minimum with respect to the variables \(q^{}_{}(T^r)\), \(T^r \in G^{{ LBB}}_{k}\).

In Sect. 1 we defined the weight of an edge \(t_{i,j}\) as the cost of transmission of one unit of data between i-th and j-th nodes \(E_{i,j}\). We define the weight of a node for in given tree T as the sum of weights of its outgoing edges

$$\begin{aligned} E_{i}(T) = \sum _{j} t_{i,j} E_{i,j}. \end{aligned}$$

The minimum node weight spanning tree algorithm (the \(\hbox {M}_{{ nw}}\)ST algorithm) allows find in the weighted graph \(\{S_N,V,E\}\) a tree whose node with maximum weight is minimal among spanning tress. In [17] Fürer and Raghavachari proposed an approximation algorithm allowing to determine the minimum degree spanning tree for a directed graph. We modify this algorithm, such that it allows to construct a spanning tree with minimum node weight. In the Fürer-Raghavachari algorithm one can start with arbitrary spanning tree in the graph. To solve the MLB problem in sensor networks we start constructing the \(\hbox {M}_{{ nw}}\)ST tree with some minimum spanning tree in \(S_N\) rooted at the broadcasting node. The set of minimum spanning trees \(G^{\mathrm{MST}}_{k}\) in \(S_N\) rooted at the k-th node can be determined by standard polynomial time algorithms like Prim’s or Kruskal’s algorithm [20].

  • The minimum node weight spanning tree algorithm.

  • Step 1 For a directed, weighted graph \(G_N=\{S_N,V,E\}\) determine the set \(G^{\mathrm{MST}}_{k}\) of minimum outgoing spanning trees rooted at the broadcasting node.

  • Step 2 Select a tree T from the set \(G^{\mathrm{MST}}_{k}\) and determine in T the node with the maximum outgoing weight. To decrease the weight of this node select a local subtree \(T^{\prime }\) in T rooted at that node and replace it by another subtree \(T^{\prime \prime }\) attached to some node with lower weight in \(S_N\), such that the inequality

    $$\begin{aligned} \max \{ E(T) - E(T^{\prime }) + E(T^{\prime \prime }) \}< \max \{E(T) \} \end{aligned}$$
    (25)

    is satisfied. The leaf nodes of the subtree \(T^{\prime \prime }\) attach to the nodes of \(T^{\prime }\).

In the inequality (25) \(E(T)=(E_{1}(T), \ldots , E_{N}(T))\) and \(E_{i}(T)\), \(i\in [1,N]\) are weight of the nodes. This algorithm allows us to find a spanning tree which approximates the \(\hbox {M}_{{ nw}}\hbox {ST}\) tree in \(S_N\).

The purpose of the second algorithm, called the load balancing broadcast algorithm, is to find the set of trees \(G^{{ LBB}}_{k}(T)\) rooted at the broadcasting node which allow to split data transmitted along given M\(_{{ nw}}\)ST tree T in such a way, that the consumed energy by the network nodes is evenly distributed. To state whether the energy of a node should be decreased or increased we define the average energy consumed by network nodes for given tree T. If we assume, that the k-th node broadcasts \(Q_k\) of data, then the average energy utilized by nodes of the \(S_N\) network we calculate by means of the following formula

$$\begin{aligned} \bar{E}(T)=Q_k \frac{\sum _{i\in [1,N]}E_{i}(T)}{N^{\prime }(T)}, \end{aligned}$$
(26)

where \(N^{\prime }(T)\) is the number of relay nodes in the tree T. For the nodes which consumed energy is greater than the average \(\bar{E}(T) \le E_i(T)\) we decrease the energy and for nodes which consumed energy is less than the average \(E_i(T) < \bar{E}(T)\) we increase the energy level.

By \(V^{e}_{i}(T)=\{ t_{i,j} \}_{j}\) we denote the set of outgoing edges of the i-th node in given tree \(T \in\) \(\hbox {M}_{{ nw}}\hbox {ST}\). The following procedure is applied in the LBB algorithm to decrease the energy consumed by the node.

Procedure 1. Spanning tree graph construction for decreasing energy consumed in the node.

To decrease the energy consumed by the i-th node remove one outgoing edge \(t_{i,r}\) from the set \(V^{e}_{i}(T)\) and construct the minimum node weight spanning tree \(T^{\prime }\) for the graph \((S_N, V^{\prime }, E)\), where \(V^{\prime } = V \setminus \{ t_{i,r} \}\), such that the inequality

$$\begin{aligned} E_{i}(T^{\prime }) < E_{i}(T) \end{aligned}$$
(27)

is satisfied. Repeat the process of constructing the minimum node weight spanning tree in \(S_N\) with removed one, two and finally all the edges from the given non-broadcasting node. For the broadcasting node we leave at least one outgoing edge. \(\quad \square\)

The requirement (27) allows not only to remove edges from the node but also to add to the i-th node a set of edges \(\{t_{i,s}\}_{s}\) satisfying the inequality \(\sum _{s} t_{i,s} E_{i,s} < t_{i,r} E_{i,r}\). If the constructed tree \(T^{\prime }\) is not unique, we can select one tree from the equivalent trees or add all equivalent trees to the objective function of the MLB problem.

The second procedure is applied in the LBB algorithm to increase the energy consumed by nodes of the network.

Procedure 2. Spanning tree graph construction for increasing energy consumed in the node.

To increase the energy consumed by the i-th node add to the set of outgoing edges \(V^{e}_{i}(T)\) a new edge \(t_{i,r}\) and construct the minimum node weight spanning tree \(T^{\prime }\) in \(S_N\), such that

$$\begin{aligned} V^{e}_{i}(T^{\prime }) = V^{e}_{i}(T) \bigcup \{ t_{i,r} \}. \end{aligned}$$
(28)

Repeat the process of constructing the minimum node weight spanning trees \(T^{\prime }\) with added one, two and finally all \((N-2)\) edges to the non-broadcasting node and \((N-1)\) edges to the broadcasting node. \(\quad \square\)

The requirement (28) means, that we construct the tree \(T^{\prime }\) with a fixed set of outgoing edges of a given node. The weight of the i-th node in \(T^{\prime }\) is given by the formula \(E_{i}(T^{\prime }) = E_{i}(T) + Q_k t_{i,r} E_{i,r}\). The two procedures we use to define the LBB algorithm.

  • The load balancing broadcast algorithm.

  • Step 1 Select a minimum node weight spanning tree T from the set \(G^{\mathrm{M_{{ nw}}ST}}_{k}\). The formula (26) is used to determine the average energy \(\bar{E}(T)\) utilized by nodes of the network \(S_N\) for the tree T.

  • Step 2 For the nodes which energy is greater than the average \(\bar{E}(T) < E_i(T)\) apply the Procedure 1, i.e. construct the set of trees for decreasing the energy consumed by that nodes \(G^{LBB}_{k}(T)\). For the nodes which the consumed energy along the tree T is less than the average \(E_i(T) < \bar{E}(T)\) apply the Procedure 2, construct the set of trees for increasing the energy consumed by that nodes. \(\quad \square\)

To each minimum node weight spanning tree T in \(S_N\) we apply the LBB algorithm to construct the set of trees \(G^{\mathrm{LBB}}(T)\) to balance the energy consumed by the nodes of the network in the process of data broadcasting. In the final stage of solving the MLB problem we define the objective function (4) over the set of trees \(G^{\mathrm{LBB}}\) and determine its minimum with respect to the set of variables \(q(T^r)\), \(T^r \in G^{{ LBB}}_{k}\).

6 Applications of the Maximum Lifetime Broadcasting Algorithms

In this section we apply the proposed algorithms to find an approximate solution of the MLB problem in sensor networks \(S_5\) build of five nodes. We assume, that the nodes of network \(S_5\) are located at the points \(x_1=(0,2)\), \(x_2=(2,2)\), \(x_3=(3,0)\), \(x_4=(4,3)\), \(x_5=(5,2)\) of the plane, where \(x_i=(x_i^1,x_i^2)\in E^2\) and the second node broadcasts the amount \(Q_{2}=1\) of data. The cost of transmission of one unit of data in the graph \(S_5\) is given by the function \(E_{i,j}=d(x_i,x_j)^4\), where \(d(x_i,x_j)\) is Euclidean distance in \(E^2\).

In the network \(S_5\) there is one minimum spanning tree rooted at the \(x_2\) node. It is given by the set of edges \(T_{\mathrm{MST}}=(t_{2,1},t_{2,3},t_{2,4},t_{4,5})\) with weights of the nodes \(E(T_{\mathrm{MST}}) = (E_1,E_2,E_3,E_4,E_5)= (0,66,0,4,0)\). To construct the minimum node weight spanning tree in \(S_5\) we start the M\(_{\mathrm{nw}}\)ST algorithm from the tree \(T_{\mathrm{MST}}\). The maximum weight in the tree \(T_{\mathrm{MST}}\) has the broadcasting node, located at \(x_2\). We reduce its weight by defining the local subtree \(T^{\prime }=(t^{}_{2,3})\) rooted at \(x_2\) and ending at the \(x_3\) node. By moving the root of \(T^{\prime }\) to the \(x_5\) node and leaving the end at \(x_3\) we obtain a new subtree \(T^{\prime \prime }=(t^{}_{5,3})\). We can easily check that for \(T^{\prime }\) and \(T^{\prime \prime }\) the inequality (25) is satisfied. By replacing in \(T_{\mathrm{MST}}\) the subtree \(T^{\prime }\) by \(T^{\prime \prime }\) we obtain the first minimum node weight spanning tree \(T^{1}=(t_{2,1}^{},t_{2,4}^{},t_{4,5}^{},t_{5,3}^{})\), with weights of the nodes \(E(T^{1})=(0,41,0,4,64)\). The second minimum node weight spanning tree in \(S_5\) we obtain by replacing in \(T_{\mathrm{MST}}\) the subtree \(T^{\prime }=(t^{}_{2,4}, t^{}_{4,5})\) by \(T^{\prime \prime }=(t^{}_{3,5}, t^{}_{5,4})\). Also in this case the inequality (25) is satisfied. As a result, we obtain the M\(_{\mathrm{nw}}\)ST tree given by the edges \(T^2=(t_{2,1}^{},t_{2,3}^{},t_{3,5}^{},t_{5,4}^{})\) and weights of the nodes \(E(T^{2})=(0,41,64,0,4)\). Figure 4 shows two constructed minimum node weight spanning trees in \(S_5\).

Fig. 4
figure 4

Two minimum node weight spanning trees in \(S_5\)

Full size image

We construct the set \(G^{{ LBB}}_2(T^i)\), \(i=1,2\), to balance the energy consumed by the nodes for the data transmitted along the two minimum node weight spanning tree \(T^1\) and \(T^2\) The average energy utilized by the nodes of the network \(S_5\) transmitting broadcasted data along the tree \(T^1\) is equal to \(\bar{E}(T^1)=36.33\). Because the weights of the nodes for \(T^{1}\) are \(E(T^{1})=(0,41,0,4,64)\) and \(\bar{E}(T^1) < E_{i}(T^{1})\) for \(i=2,5\), we decrease the energy consumed by the \(x_2\) and \(x_5\) nodes and increase the energy consumed by the \(x_1\), \(x_3\), \(x_4\) nodes of the network.

To decrease the energy consumed by the \(x_5\) node we remove the edge \(t_{5,3}\) from the set \(V(S_5)\) and construct the M\(_{\mathrm{NW}}\)ST tree \(T^{\prime }\) in \(S_5\), such that the inequality \(E_{i}(T^{\prime }) < E_{i}(T^{1})\) is satisfied. In this way we obtain \(T^{\prime }=T^{2}\), the second minimum node weight spanning tree in \(S_5\). We can decrease the energy consumed by the \(x_2\) node by removing from \(V(S_5)\) the edge \(t_{2,1}\) or \(t_{2,4}\). If we remove the edge \(t_{2,4}\), then the minimum node weight spanning tree constructed in \(S_5\) with the smaller set of edges \(V(S_5) \setminus \{ t_{2,4} \}\) is \(T^{3}=(t_{2,1}, t_{1,3}, t_{3,5},t_{5,4})\) with weights of the nodes \(E(T^{3})=(169,16,64,0,4)\). The M\(_{\mathrm{nw}}\)ST tree constructed in \(S_5\) with removed edge \(t_{2,1}\) give us the tree \(T^{4}=(t_{2,4}, t_{4,5}, t_{5,3},t_{3,1})\) with weights of the nodes \(E(T^{4}) = (0, 25, 169, 4, 64)\).

To increase the energy consumed by the first node in \(S_5\) we attach to \(x_1\) the edge \(t_{1,3}\) and fix it in the new tree \(T^{\prime }\), i.e. \(V^{e}_{1}(T^{\prime })=\{ t_{1,3} \}\). Construction of the M\(_{\mathrm{nw}}\)ST tree \(T^{\prime }\) in \(S_5\), with fixed set \(V^{e}_{1}(T^{\prime })\), gives us the tree \(T^{\prime }=T^{5}=(t_{2,1}, t_{1,3}, t_{2,4},t_{4,5})\) with the weights of the nodes \(E(T^{5}) = ( 169, 41, 0, 4,0)\). Applying the LBB algorithm to increase the energy consumed by the \(x_3\) node we obtain \(T^{2}\), the second M\(_{\mathrm{nw}}\)ST in \(S_5\). To increase the energy consumed by the fourth node we attach to \(x_4\) the edge \(t_{4,3}\) and fix the node outgoing edges in \(T^{\prime }\), i.e. \(V^{e}_{4}(T^{\prime })=\{t_{4,5}, t_{4,3} \}\). For a fixed set \(V^{e}_{4}(T^{\prime })\) constructed M\(_{\mathrm{NW}}\)ST tree \(T^{\prime }\) has the form \(T^{\prime }=T^{6}=(t_{2,1}, t_{2,4}, t_{4,5}, t_{4,3})\) with the nodes weights \(E(T^{6})=(0,41,0,104,0)\).

For the set of trees \(G^{\mathrm{LBB}}_{2}(T^1)=\{T^{r}\}_{r\in [1,6]}\) we define the objective function (4) and calculate its minimum with respect to the six variables \(q=(q_1, \ldots , q_6)\). The solution of the MLB problem in \(S_5\), determined by the maximum lifetime broadcasting algorithms, is given by the set of trees \(\{ T^{1}, T^{3}, T^{4}, T^{6}\}\) and the amount of data \(q_{1}=0.393397\), \(q_{3}= 0.201039\), \(q_{4}= 0.124906\), \(q_{6}=0.280658\). The energy consumed by the nodes \(x_1\), \(x_2\), \(x_3\), \(x_5\), \(x_4\) is equal to \(E^{\mathrm{alg}}=33.9755\) and \(E^{\mathrm{alg}}_{4}=31.2616\) respectively. The solution found by means of the algorithms, i.e., \(E^{\mathrm{alg}}=33.9755\), is \(\frac{E^{\mathrm{alg}}}{E^{\mathrm{sol}}}=1.0032\) times worse than the exact solution. When we start constructing the set \(G^{\mathrm{LBB}}_{2}(T)\) from \(T^{2}\), the second M\(_{\mathrm{nw}}\)ST tree in \(S_5\), then we obtain the approximate solution \(E^{\mathrm{alg}}=34.4366\), which is \(\frac{E^{\mathrm{alg}}}{E^{\mathrm{sol }}}=1.01682\) times worse that the exact solution. The set \(G^{\mathrm{LBB}}_{2}(T^2)\) for the solution \(E^{\mathrm{alg}}=34.4366\) consists of the following trees \(T^1\), \(T^2\), \(T^3\), \(T^6\) from \(G^{\mathrm{LBB}}_{2}(T^1)\) and two new trees \(T^7=(t_{2,3}, t_{3,1},t_{3,5},t_{5,4})\) and \(T^8=(t_{2,1}, t_{1,3},t_{2,4},t_{4,5})\).

We would like to apply the maximum lifetime broadcasting algorithms to solve the MLB problem in \(L_N\) network. We show, that the algorithms can find all the trees from the exact solution of the MLB problem (11) in \(O(N^2)\) time.

Lemma 6

The minimum node weight spanning tree and the load balancing broadcast algorithms find the solution of the maximum lifetime broadcasting problem in the \(L_N\) network in \(O(N^2)\) time.

Proof

The minimum node weight spanning trees for the weighted graph \((L_N, V, E)\) are the minimum spanning trees. They can be found in \(O(N^2)\) time by the standard algorithms. For the border nodes of the \(L_N\) network the minimum spanning trees rooted at these nodes form the solution of the MLB problem, see Lemma 3. When the data is broadcasted by the internal node of the network, then the M\(_{\mathrm{NW}}\)ST tree in \(L_N\) is the \(T^k\) tree, \(k\in [2,N-1]\), defined in (13). The weights of the nodes in the \(T^k\) tree are \(E_{k}=2\), \(E_{1}=E_{N}=0\) and \(\forall _{i\ne 1,N,k} E_{i}=1\). The average energy consumed by the nodes of the network \(L_N\) transmitting the amount \(Q_k=1\) of data along the tree \(T^{k}\) is equal to \(\bar{E}(T^{k})=\frac{N-1}{N-2}\). Because of the inequalities \(\bar{E}(T^{k})< E_{k}(T^{k})\) and \(\forall _{i\ne k} \; E_{i}(T^{k}) < \bar{E}(T^{k})\) we should decrease the energy consumed by the broadcasted node and increase the energy consumed by all other nodes. Applying the LBB algorithm to decrease the load of the broadcasting node we obtain two trees, the \(T^{k-1}\) and \(T^{k+1}\) tree from (13). In the first iteration, when the LBB algorithm is applied to increase the energy consumed by the non-broadcasting nodes of the \(L_N\) network, \(i\in [1,N]\), \(i\ne k\), we add to each node one additional outgoing edge and construct the M\(_{\mathrm{NW}}\)ST tree. For the i-th node, \(i\in [2,k-1]\), we fix the existing outgoing edge \(t_{i,i-1}\) and add the \(t_{i,j}\) edge, \(j\ne k,i,i+1\). For \(i\in [k+1,N-1]\) we fix the edge \(t_{i,i+1}\), add the new edge \(t_{i,j}\), \(j\ne k,i,i+1\), \(j\ne k,i,i-1\) and construct the M\(_{\mathrm{NW}}\)ST tree in \(L_N\). In general, for each node \(i\in [2,N-1]\), \(i\ne k\), there are \((N-3)\) ways to add the additional edge. Among \((N-3)\) trees rooted the i-th node, \(i\in [2,N-1]\), \(i\ne k\) there is always one tree from the solution (13). Because the border nodes of the \(L_N\) network in the tree \(T^k\) are the leaf nodes we can attach to them a one edge in \((N-2)\) ways. Also in this case among constructed \((N-2)\) trees rooted at the border nodes there is one tree from the solution (13). Constructed by the LBB algorithm set \(G^{{ LBB}}_k(T^k)\) is composed of \((N-3)^2+2(N-2)+1\) trees. Because in this set there are all trees from the solution of the MLB problem in \(L_N\) then the algorithm finds them in \(O(N^2)\) time. \(\quad \square\)

In the last step of solving the MLB problem in \(L_N\) by means of the maximum lifetime broadcasting algorithms we have to build the objective function (4) over the set \(G^{{ LBB}}_k(T^k)\) with \(q^r\), \(r\in [1,(N-3)^2+2(N-2)+1]\) variables and calculate its minimum. Because the MLB problem (11) is equivalent to the linear programming problem to find a minimum of the objective function we can apply the Dantzig simplex algorithm or the Khachian ellipsoid algorithm [21]. In the worst case the complexity of the Dantzig algorithm is exponential and the Khachian algorithm has polynomial time complexity with the bound \(O(N^6 L^2)\), where N is the number of variables and L is the number of bits required to represent the input data.

7 Conclusions

In the paper we investigated the equal energy solutions of the maximum lifetime broadcasting problem in sensor networks. We solved the maximum lifetime problem for the point-to-point and point-to-multipoint broadcast data transmission in one dimensional regular sensor network \(L_N\). Based on the analytical solution of the problem in one dimension we proposed two algorithms which allow to find an approximate solution of the problem in sensor networks in any dimension. The first algorithm determines the minimum node weight spanning trees in a given network. The second algorithm, called the load balancing broadcast algorithm, allows construct the set of trees to balance the energy consumed by the network nodes transmitting data along given minimum node weight spanning tree. As a sample application of the proposed algorithms we solved the maximum lifetime broadcasting problem in sensor network build of five nodes. Two solutions found by means of these algorithms were \(\frac{E^{\mathrm{alg}}(T^1)}{E^{\mathrm{sol}} }=1.0032\) and \(\frac{E^{\mathrm{alg}}(T^2)}{E^{\mathrm{sol }}}=1.01682\) times worse than the exact solution. We also showed, that by means of these algorithms we can find all trees from the exact solution of the MLB problem in \(L_N\) network in \(O(N^2)\) time.

There are several unsolved problems related to the proposed algorithms. For example, it would be interesting to modify the load balancing broadcast algorithm in such a way that the unequal energy solutions of the maximum lifetime broadcasting problem can be efficiently found. Knowledge about the number of minimum node weight spanning trees in given network, the cardinality of the set \(|G^{\mathrm{M_{{ nw}}ST}}_{k}(S_N)|\), could help to find better approximation of the solution for the MLB problem. Also the minimum number of the trees necessary to solve the MLB problem for arbitrary network and broadcasting node is not known. It seems, that the solution of the MLB problem in network build of N nodes requires no more than N routing trees.