Sage Journals: Discover world-class research

Abstract

In recent years, wireless sensor networks have been widely used in data acquisition, surveillance, event monitoring, and so forth. Topology control is an important issue in designing sensor networks. Considering the uncertainty of distance between nodes, a distributed topology control algorithm named as LRMST, which is based on the local minimum spanning tree (LMST) algorithm, is proposed by applying the 0-1 robust discrete optimization theory. Firstly, when only the cost coefficients are subject to uncertainty, it is proved that the robust counterpart of the 0-1 discrete optimization problem on n variables can be solved by solving at most $n + 1 - Γ$ deterministic problems, where Γ denotes the number of cost coefficients which change in an uncertainty set. Then we present a robust model for the MST problem under distance uncertainty. According to the proved conclusion, an algorithm is proposed to obtain the robust solution of uncertain MST problem by solving only one deterministic MST problem, after which LRMST algorithm is designed when the distance between nodes is affected by uncertainty. Simulation results show that LRMST algorithm tends to select some edges whose estimated distance is slightly longer and obtains the robustness when the distance is uncertain at the expense of less optimal value compared with LMST algorithm.

1. Introduction

Wireless sensor networks (WSNs for short) consist of a large number of sensor nodes which are characterized by the constrained battery, memory, and processing power. Recently, WSN has been popularly used in a wide range of applications such as environment monitoring, military target tracking and surveillance, natural disaster relief, biomedical health monitoring, real-time monitoring, vehicle tracking, and so on. WSN has attracted the attention of both the academic and the industrial research communities in the last few years.

As a critical issue in energy-efficient WSN design, topology control is carried out to form an optimized network topology structure by adjusting the communication range of nodes with the desired properties such as connectivity and coverage while reducing energy consumption and increasing network capacity [1]. This technology can enhance the efficiency of routing and MAC protocol, lay a foundation for the data fusion, time synchronization, and target localization, and prolong the survival time of the whole network [2–5].

WSNs are generally deployed in harsh environments to monitor the target field and detect the occurrence of important events. Since there are measurement error, actual interference, attacks, and other external factors that seriously affect the topology control problem, new robust topology control technologies have to be established for WSN under uncertain environments. In addition, given the energy constraint, the dynamic change of network topology and the relatively poor communication quality, another challenge, have to be faced for the WSN designers: the need to operate distributedly.

There are extensive literatures [2–9] that have discussed topology control algorithms, and they are designed with accurate distance generally. However, if we consider the existence of uncertain factors, the optimality of these algorithms is very difficult to guarantee. A more successful strategy can be a solution that is less optimal for a particular distance vector but obtains efficient solutions for all likely distance measurements. Therefore, the robustness of algorithm is involved.

In this paper, we use the robust discrete optimization theory to deal with distance uncertainty for topology control problem in WSN. Considering that the distance between nodes is uncertain, a distributed topology control algorithm named as LRMST (Local Robust Minimum Spanning Tree) is proposed. With the uncertainty increasing, the robust solution for the problem provides a significant performance improvement in the worst case at the expense of a small loss in optimality when compared to LMST algorithm.

The rest of the paper is organized as follows. We first introduce a literature review of related work in Section 2. In Section 3, some results based on 0-1 robust discrete optimization theory are given and proved. Topology control protocol of LRMST under uncertain distance is designed in Section 4. In Section 5, simulation results are considered. We conclude the paper in Section 6.

2. Related Work

Many topology control algorithms are proposed under the assumption that the distance between nodes is accurate. These methods available are based mainly on traditional optimization or heuristics, without giving full consideration of the effects produced by the interference, errors, and malicious attacks in modeling the networks, so the robustness is poor. In KNeigh algorithm [6], by broadcasting its ID at maximum power, every node in the network knows its neighbor set and distance-based ordering of the neighbors. Given this information, every node computes its k-closest neighbors and its transmit power is set to the minimum value needed to reach the farthest neighbor node. DRNG algorithm [7] deals with the heterogeneous WSN with nonuniform transmission ranges; with two node positions as the center and the distance between the two nodes as the radius, two circles are generated. If there is no other node in the intersection of two disks, the two nodes are called neighbor nodes. In LIFE algorithm [8], MST is generated using the edge covering value as the weight, and the calculation of edge covering value requires information about the distance between nodes. To overcome the drawback of requiring the exchange of global information of MST, Li et al. [9] introduced LMST protocol, which computes a local approximation of the MST. After receiving the information of neighbors at maximum transmit power, each node constructs its local MST by applying classical Prim's algorithm with the distance between nodes as the link weight. In LMST each node determines its transmit power, that is, the minimum power needed to reach the farthest node in its one-hop neighbor set. By deleting or adding edges in the LMST topology, a bidirectional network formation is constructed in the end. LMST algorithm preserves that the produced network is connected and the upper bound of node degree equals 6.

The optimality of all above algorithms is guaranteed depending on the accuracy of distance between nodes. However, in many applications, the distance measurements are subject to uncertainty as they are indirectly estimated through signal strength or due to unfriendly conditions during the WSN's deployment or operation. On the other hand, since sensors have limited energy, when designing the topology protocol, distance is an important factor that influences the energy consumption because sensors transmitting data consume an amount of energy proportional to approximately the square of the distance [10]. The effect of ignoring distance uncertainty in the efficiency of the operation of WSN is unclear.

There are two principal methods that have been proposed to address data uncertainty over the years, one is stochastic programming, and the other is robust optimization. Dantzig [11] introduces stochastic programming as an approach to model data uncertainty by assuming scenarios for the data occurring with different probabilities. The two main difficulties with such an approach are as follows: (a) the stochastic programming model obtained is not easy to solve; (b) the exact probability distribution of uncertain data must be known, which in practice is very difficult to achieve. Robust optimization theory is an effective method for dealing with uncertain data. By using an uncertainty set to represent the uncertain data and translating the corresponding uncertain optimization model into a deterministic problem called its robust counterpart, the optimal solution of the robust counterpart, namely, robust solution, is given when uncertain data changes in the uncertainty set. In 1973, Soyster [12] proposed a linear optimization model to construct a solution that is feasible for all input data such that all uncertain input data can take any value from an interval. This approach, however, tends to find solutions that are overconservative. Nonetheless, the robust optimization theory is established in which we optimize against the worst instances that might arise by using a min-max objective. Later, Ben-Tal et al. carry out further research on the robust optimization theory [13–18]. Bertsimas and Sim [17] propose an approach to control the level of conservatism in the solution of a discrete optimization model. In our paper, we will extend and improve this approach to 0-1 discrete optimization problem and apply it to the robust topology control design.

For the first time, the robust optimization theory is used for solving the optimization model of WSN in the literature [19]. When the distance between nodes is uncertain, robust counterparts are given and solved of minimum energy consumption problem, maximum data extraction problem, and maximum network lifetime problem; the experiment results show that the robust optimization model has very good performance in practice. Consequently, combined with the theory and methodology of 0-1 robust discrete optimization, this paper will research the distributed topology control algorithm for WSN, aiming at solving the uncertainty problem for WSN in practical application scenarios. Belonging to problem-driven studies, this paper will have great theoretical and practical value in solving the uncertainty problem of topology control in practical applications of WSN.

3. 0-1 Robust Discrete Optimization Theory

Let $c$ , $x$ be n-vectors. We consider the following 0-1 discrete optimization model on a set of n variables:

\begin{array}{l} min c^{'} x \\ s . t . x \in X \subseteq {0, 1}^{n} . \end{array}

(1)

In this model, the decision variables are binary; that is, $x \in X \subseteq {\{0,1\}}^{n}$ , and the set X is fixed. $c$ is the cost vector and $c = {(c_{1}, c_{2}, \dots, c_{n})}^{'} \in R^{n}$ .

We assume that data uncertainty affects only the elements of cost vector c. Although it is unlikely to know the exact distribution of these coefficients in c, we can estimate its mean value and its range in typical applications. Specifically, the model of data uncertainty we consider is as follows.

Model of Data Uncertainty for Cost Vector $c$ . Let $N = \{1,2, \dots, n\}$ . Each entry $c_{j}, j \in N$ is modeled as an independent bounded random variable ${\tilde{c}}_{j}$ that takes value in $[c_{j}, c_{j} + d_{j}]$ , $d_{j} \geq 0$ , where $c_{j}$ is called the nominal value of ${\tilde{c}}_{j}$ and $d_{j}$ represents the deviation from the nominal cost coefficient $c_{j}$ . Thus the uncertainty set $U = \{\tilde{c} ∣ {\tilde{c}}_{j} \in [c_{j}, c_{j} + d_{j}], j \in N\}$ . Note that when $d_{j} = 0$ , the coefficient ${\tilde{c}}_{j}$ is deterministic.

The goal of 0-1 robust discrete optimization is to give the optimal solution of the problem when cost coefficients change in the uncertainty set, and then the optimal solution is called robust solution. Robust solution ensures the optimality of the problem in the worst case; that is, all the uncertain cost coefficients change, but at this time it is too conservative. To control the conservatism degree of the robust solution, we introduce a parameter $Γ$ called adjusting parameter [17].

Definition 1 (adjusting parameter $Γ$ ).

Let $J = \{j ∣ d_{j} > 0, j \in N\}$ . Adjusting parameter $Γ$ is used to control the number of uncertain cost coefficients ${\tilde{c}}_{j}$ that are allowed to change, and $Γ$ takes value in the interval $[0, |J|]$ .

The role of the parameter $Γ$ is to adjust the robustness of the proposed method against the conservatism level of the solution. We are interested in finding an optimal solution that optimizes against all scenarios under which a number $Γ$ of the cost coefficients can vary in such a way as to maximally influence the objective. If $Γ = 0$ , we completely ignore the influence of the cost deviations; at this time the obtained solution has the best optimality but the worst robustness; while if $Γ = |J|$ , we are considering all possible cost deviations, which is indeed most conservative, whereas the obtained solution has the best robustness. In general a higher value of $Γ$ increases the level of robustness at the expense of higher cost. The value of $Γ$ depends on the decision-maker's preference for the robustness or the optimality of the solution. If the decision-maker pays more attention to the robustness of the solution, a higher value of $Γ$ should be selected. On the contrary, if the decision-maker pays more attention to the optimality of the solution, a lower value of $Γ$ should be selected.

Under this condition, the uncertainty set is

\begin{matrix} U = \{\tilde{c} ∣ {\tilde{c}}_{j} \in [c_{j}, c_{j} + d_{j}], \sum_{j = 1}^{n} \frac{{\tilde{c}}_{j} - c_{j}}{d_{j}} \leq Γ, j \in N\} . \end{matrix}

(2)

Having used an uncertainty set to represent the uncertain data, we should then translate the corresponding uncertain optimization model into a deterministic problem called robust counterpart and then give the optimal solution when uncertain data changes in the uncertainty set. We would like to find a solution $x \in X$ that minimizes the maximum cost $c^{'} x$ such that at most $Γ$ of the coefficients ${\tilde{c}}_{j}$ is allowed to change. The robust counterpart [17] of problem (1) is equivalent to

\begin{array}{l} min {c^{'} x + max_{{s | s \subseteq N, | s | \leq Γ}} \sum_{h \in S} d_{j} x_{j}} \\ s . t . x \in X \subseteq {0, 1}^{n} . \end{array}

(3)

Without loss of generality, we assume that the indices are ordered such that $d_{1} \geq d_{2} \geq \dots \geq d_{n}$ . For notational convenience, we also define $d_{n + 1} = 0$ .

In the context of uncertain scenario, finding an optimal robust solution involves solving the above min–max problem (3). For many classical 0-1 discrete optimization problems, finding such a robust solution is NP-hard. However, the following theorem shows that if the deterministic 0-1 discrete optimization problem (1) has a polynomial solution, then the 0-1 robust discrete optimization problem (3) also has a polynomial solution.

Theorem 2 (see [17]).

Problem (3) can be solved by solving at most $n + 1$ deterministic problems:

\begin{array}{l} R^{*} = min_{l = 1, 2, \dots, n + 1} G^{l}, \\ G^{l} = Γ d_{l} + min_{x \in X} (c^{'} x + \sum_{j = 1}^{l} (d_{j} - d_{l}) x_{j}), \\ \forall l = 1, 2, \dots, n + 1, \\ s . t . x \in X \subseteq {0, 1}^{n} . \end{array}

(4)

Theorem 2 leads to the following conclusion. When only the cost coefficients are subject to uncertainty and the problem is a 0-1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most $n + 1$ instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0-1 discrete optimization problem remains polynomially solvable. Theorem 2 implies that if $|\{d_{1}, d_{2}, \dots, d_{n}\}| = k$ , problem (3) requires the solution of $k + 1$ deterministic 0-1 discrete optimization problems. In particular, if $d_{j} = d$ for all $j \in N$ , only two deterministic problems need to be solved.

The following Theorem 3 shows that the steps to calculate deterministic problems can be further reduced to solve problem (3).

Theorem 3.

Problem (3) can be solved by solving at most $n + 1 - Γ$ deterministic problems:

\begin{array}{l} R^{*} = min_{l = Γ + 1, \dots, n + 1} G^{l}, \\ G^{l} = Γ d_{l} + min_{x \in X} (c^{'} x + \sum_{j = 1}^{l} (d_{j} - d_{l}) x_{j}), \\ \forall l = Γ + 1, \dots, n + 1, \\ s . t . x \in X \subseteq {0, 1}^{n} . \end{array}

(5)

Proof.

Let $H^{l} (x) = c^{'} x + \sum_{j = 1}^{l} (d_{j} - d_{l}) x_{j}$ , $\forall l \in \{1,2, \dots, n + 1\}$ .

For any feasible solution, $x \in X$ , when $l \in \{1,2, \dots, n\}$ , we have

\begin{array}{l} H^{l} (x) - H^{l + 1} (x) = (c^{'} x + \sum_{j = 1}^{l} (d_{j} - d_{l}) x_{j}) \\ - (c^{'} x + \sum_{j = 1}^{l + 1} (d_{j} - d_{l + 1}) x_{j}) \\ = (d_{l + 1} - d_{l}) \sum_{j = 1}^{l} x_{j} . \end{array}

(6)

Thus

\begin{array}{l} G^{l} - G^{l + 1} = (Γ d_{l} + min_{x \in X} H^{l} (x)) \\ - (Γ d_{l + 1} + min_{x \in X} H^{l + 1} (x)) . \end{array}

(7)

Suppose $x^{l^{*}} = (x_{1}^{l^{*}}, \dots, x_{n}^{l^{*}})$ is the optimal solution of $\min_{x \in X} H^{l} (x)$ , and $x^{l^{*}}$ is in the feasible region of $\min_{x \in X} H^{l + 1} (x)$ , from formula (6), we get

\begin{array}{l} G^{l} - G^{l + 1} \geq Γ (d_{l} - d_{l + 1}) + H^{l} (x^{l^{*}}) - H^{l + 1} (x^{l^{*}}) \\ = Γ (d_{l} - d_{l + 1}) + (d_{l + 1} - d_{l}) \sum_{j = 1}^{l} x_{j}^{l^{*}} \\ = (d_{l} - d_{l + 1}) (Γ - \sum_{j = 1}^{l} x_{j}^{l^{*}}) . \end{array}

(8)

As $d_{l} \geq d_{l + 1}$ , $\sum_{j = 1}^{l} x_{j}^{l^{*}} \leq l$ , we have

\begin{matrix} G^{l} - G^{l + 1} \geq (d_{l} - d_{l + 1}) (Γ - l) . \end{matrix}

(9)

So that when $l \leq Γ$ , for $l \in \{1, \dots, n\}$ , $G^{l} - G^{l + 1} \geq 0$ holds. The proof is completed.

Theorem 3 shows that the optimal solution for problem (3) can be obtained by solving only one deterministic problem $G^{n + 1}$ when $Γ = n$ . If $|\{d_{Γ + 1}, \dots, d_{n}\}| = k$ , problem (3) can be solved by solving $k + 1$ deterministic problems.

4. LRMST Algorithm

In this section, based on 0-1 robust discrete optimization theory, a robust topology control algorithm named as LRMST is proposed to improve LMST algorithm.

4.1. Network Environment

Assume n sensor nodes are uniformly distributed in a two-dimensional region, and they have the same maximum transmit power $P_{\max}$ ; here sensor nodes are represented as the set $V = \{v_{1}, v_{2}, \dots, v_{n}\}$ , where $v_{i} (i = 1, \dots, n)$ denotes a node. The max power graph $G = (V, E)$ can be obtained when all the nodes transmit at maximum power, which is a connected undirected graph. The edge set $E = \{(u, v) ∣ P_{u \to v} \leq P_{\max}\}$ , where $P_{u \to v}$ denotes the minimum transmit power required when node u communicates with node v, and we suppose $P_{u \to v} = P_{v \to u}$ .

Nodes can acquire information about their neighbor nodes, including ID and the distance between them, and the distance can be obtained by some distance measurement algorithms. This can be accomplished by sending a beacon message at maximum transmit power.

Definition 4 (reachable neighbor set).

The reachable neighbor set of node $u \in V$ is the set of all the one-hop neighbors of u in the max power graph $G = (V, E)$ . Formally,

\begin{matrix} R N_{u} = \{v \in V ∣ P_{u \to v} \leq P_{\max}\} . \end{matrix}

(10)

Then the subgraph formed by the reachable neighbors of node u is denoted by

G_{u} = (R N_{u}, E_{u})

, where

E_{u} = \{(v_{i}, v_{j}) ∣ v_{i}, v_{j} \in R N_{u}, (v_{i}, v_{j}) \in E\}

Distance given by a distance measurement algorithm can suffer from many uncertain factors, such as distance measurement accuracy and existing barriers between nodes. Therefore, it is reasonable to consider the distance uncertainty. We further suppose that its mean value and its range can be estimated, and the distance uncertainty model is the same as what is described in Section 3. Specifically, for each edge $(v_{i}, v_{j}) \in E$ , let $d_{i j}$ denote the estimated distance obtained by a distance measurement algorithm, while the actual distance is ${\tilde{d}}_{i j}$ . As mentioned above, ${\tilde{d}}_{i j}$ takes value in $[d_{i j}, d_{i j} + ω_{i j}]$ ; that is, ${\tilde{d}}_{i j} \in [d_{i j}, d_{i j} + ω_{i j}]$ , where the constant $ω_{i j} \geq 0$ , which denotes the deviation between the actual distance and the estimated distance.

4.2. Robust Minimum Spanning Tree (RMST) Algorithm

Definition 5 (minimum spanning tree).

Given a connected and undirected graph $G = (V, E)$ , a spanning tree of G is a tree $T = (V, E (T))$ that contains all the nodes in G such that $E (T) \subseteq E$ . A minimum spanning tree (MST) for G is then a spanning tree of G with the minimum sum of the weights on its edges.

The MST problem has direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks, water supply networks, and electrical grids [20]. There are now two algorithms commonly used for finding an MST, namely, Prim's algorithm [21] and Kruskal's algorithm [22], and both are greedy algorithms that run in polynomial time. In LMST protocol, each node constructs its local MST. In order to enhance the robustness of LMST, we should achieve the robust counterpart of MST problem in the first place.

By taking the distance between nodes as edge weight, the optimization model for MST problem of the maximum power graph $G = (V, E)$ is given:

\begin{array}{l} min \sum_{(v_{i}, v_{j}) \in E (T)} d_{i j} x_{i j} \\ s . t . \sum_{(v_{i}, v_{j}) \in E (T)} x_{i j} = n - 1, \\ x_{i j} = {\begin{array}{l} 1 & (v_{i}, v_{j}) \in E (T) \\ 0 & (v_{i}, v_{j}) \notin E (T), \end{array} \\ x = {(x_{i j})}_{(v_{i}, v_{j}) \in E} \in X \subseteq {0, 1}^{m}, \end{array}

(11)

where

T = (V, E (T))

represents one spanning tree of the maximum power graph G and

m = |E|

. We assume that data uncertainty affects only the distance

d_{i j}

and its related uncertainty model has been mentioned in Section 4.1.

As we all know, WSNs are generally deployed in harsh environments. Distance between nodes is seriously affected by uncertain external factors, such as measurement error, actual interference, and attacks. Consequently, we pay more attention to the robust solution that is efficient for all likely distance measurements. When determining the value of adjusting parameter $Γ$ , we set it to its maximum possible value in the following.

Let $Γ = m$ ; the robust counterpart of problem (11) is

\begin{array}{l} min {\sum_{(v_{i}, v_{j}) \in E (T)} d_{i j} x_{i j} + max_{{S | S \subseteq E (T), | S | = Γ}} \sum_{(v_{i}, v_{j}) \in S} ω_{i j} x_{i j}} \\ s . t . \sum_{(v_{i}, v_{j}) \in E (T)} x_{i j} = n - 1, \\ x_{i j} = {\begin{array}{l} 1 & (v_{i}, v_{j}) \in E (T) \\ 0 & (v_{i}, v_{j}) \notin E (T), \end{array} \\ x = {(x_{i j})}_{(v_{i}, v_{j}) \in E} \in X \subseteq {0, 1}^{m} . \end{array}

(12)

Problem (12) presents a robust model under distance uncertainty for the problem of MST, and Theorem 3 shows that the robust solution of problem (12) can be obtained by solving only one deterministic MST problem. Protocol RMST is summarized in Algorithm 1.

As analyzed in [21], the time complexity of Prim's algorithm is $O (n^{2})$ . In RMST algorithm, only the weight of each edge is substituted for an uncertain distance; consequently, RMST algorithm and Prim algorithm have the same time complexity of $O (n^{2})$ .

Algorithm 1: RMST algorithm.

Step 1. Let $G = (V, E)$ be the maxpower graph with $| V | = n$ , $| E | = m \cdot \tilde{d} : E \to R^{+}$ is a

distance function and $\tilde{d}$ is uncertain, it takes value in $[d_{i j}, d_{i j} + ω_{i j}]$ , $(v_{i}, v_{j}) \in E$ , in which $d_{i j}$

denotes the estimated distance, $ω_{i j}$ is a nonnegative constant and represents the deviation from the estimated value.

Step 2. Define the weight of each edge, $e_{i j} = d_{i j} + ω_{i j}$ , $(v_{i}, v_{j}) \in E$ .

Step 3. The minimum spanning tree T is given by running the Prim's algorithm according to the defined weights.

Definition 6 (neighbor set).

The neighbor set $N_{u}$ of node u is the set of all the one-hop nodes of node u in its robust minimum spanning tree $T_{u} = (R N_{u}, E_{u} (T))$ ; that is,

\begin{matrix} N_{u} = \{v \in R N_{u} ∣ (u, v) \in E_{u} (T)\} . \end{matrix}

(13)

4.3. Local Robust Minimum Spanning Tree (LRMST) Algorithm

Taking node u as an example, the LRMST algorithm is presented in Algorithm 2.

Algorithm 2: LRMST algorithm.

(algorithm for node u)

$R N_{u}$ is the reachable neighbor set of node u

$N_{u}$ is the neighbor set of node u

$t p_{u}$ is the transmit power of node u

$(x_{u}, y_{u})$ are the coordinates of node u

(1) Information exchange

send beacon $(u, (x_{u}, y_{u}))$ at maximum power

upon receiving beacon $(v, (x_{v}, y_{v}))$ , node u can get its $R N_{u}$ and the subgraph $G_{u} = (R N_{u}, E_{u})$

(2) Topology construction

build the local robust MST on nodes in $R N_{u}$ using RMST algorithm

let $T_{u} = (R N_{u}, E_{u} (T))$ be this local robust MST

$N_{u} = {v \in R N_{u} | (u, v) \in E_{u} (T)}$

(3) Determination of transmit power

for each $v \in N_{u}$

compute the minimum power $m p_{v}$ needed to reach the farthest node in $N_{u}$

$t p_{u} = \max_{v \in N_{u}} m p_{v}$

(4) Bidirectional topology formation

similar to that of LMST, omitted here

5. Simulation and Performance Analysis

In this section, the proposed algorithm LRMST is compared with LMST algorithm in which bidirectional graph is formed by adding edges.

Firstly, the simulation environment is given. Nodes are evenly distributed in a 1000 m × 1000 m square area, the maximum communication radius of nodes is $d_{\max} = 250$ m, and the communication radius of nodes can be adjusted continuously among 0~250 m. As the node number n increases from 50 to 250, the simulation results of LMST algorithm are compared with those of LRMST algorithm in two different cases.

In the first case, for $D_{1}$ , the deviation $ω_{i j}$ between the node's estimated distance $d_{i j}$ and the actual distance ${\tilde{d}}_{i j}$ is less than one-fifth of the estimated distance; namely, $ω_{i j}$ is evenly distributed in the interval $[0, d_{i j} / 5]$ , $(v_{i}, v_{j}) \in E$ . In the second case, for $D_{2}$ , $ω_{i j}$ is evenly distributed in the interval $[d_{i j} / 5, d_{i j}]$ , $(v_{i}, v_{j}) \in E$ . It is obvious that distance uncertainty increases from case $D_{1}$ to $D_{2}$ .

In order to compare the performance of two algorithms with deterministic data and uncertain data, here we give two main indexes [19]

\begin{matrix} R^{ac} = \frac{R (d) - L (d)}{L (d)}, \\ R^{wc} = \frac{L (\tilde{d}) - R (\tilde{d})}{L (\tilde{d})}, \end{matrix}

(14)

where

L (d)

is optimal value of LMST algorithm with deterministic data.

R (d)

is objective value of LRMST algorithm with deterministic data.

L (\tilde{d})

is objective value of LMST algorithm with uncertain data.

R (\tilde{d})

is optimal value of LRMST algorithm with uncertain data.

The first ratio $R^{ac}$ quantifies the relative loss of optimality of the robust solution with deterministic data, and the second ratio $R^{wc}$ measures the relative increase of the optimal value of the algorithm in the worst case. Therefore the ratio $R^{wc}$ measures the maximum protection that a robust solution can provide, while $R^{ac}$ is the percent increase in cost for this protection.

Figures 1(a) and 1(b) show the topology generated by running LMST and LRMST algorithm in the first case $D_{1}$ as 100 nodes are uniformly distributed in the area, where the red lines represent different edges in the topology structure generated by the two algorithms. It can be seen from the figure that LRMST algorithm tends to select some edges whose estimated distance is slightly longer.

Figure 1

Comparison of the topology structure generated by LMST algorithm and LRMST algorithm.

The average node degrees of LMST algorithm and LRMST algorithm are compared in Figure 2, which are the average results of 50 simulations. The topology structure constructed by LMST algorithm in two cases $D_{1}$ and $D_{2}$ is the same, so that the two curves of LMST coincide. As can be seen from Figure 2, the topology generated by LRMST algorithm in the two cases is very sparse; the average node degree is less than 2.2. Since the average node degree of the spanning tree is 2-2/n, it is shown that the topology structure generated by LRMST algorithm is also very close to the spanning tree.

Figure 2

Comparison of the average node degree of LMST and LRMST.

Figure 3 indicates the values obtained from formula (14) after running LMST and LRMST algorithm, and they are the mean results of 50 simulations. We can see from Figure 3 that $R^{ac}$ is much smaller than $R^{wc}$ in the two cases, and, with the increase of the node number, especially in the second case $D_{2}$ , $R^{wc}$ increases very fast and its increment speed is much higher than that of $R^{ac}$ . Therefore, LRMST algorithm can provide the solution which exhibits an important improvement in the worst case performance at the expense of a small loss in optimality, and the more nodes become, the more superiority of LRMST algorithm can be reflected. As we know, distance uncertainty increases from case $D_{1}$ to $D_{2}$ . With increasing uncertainty, we observe a faster increase in $R^{wc}$ with little change in $R^{ac}$ , which shows that the robust solution becomes more attractive as the distance uncertainty increases. From this observation, it can be concluded that LMST algorithm is very sensitive to the uncertainty, while LRMST algorithm changes a little in two cases. LRMST algorithm can provide the solution which exhibits an important improvement in the worst case performance at the expense of a small loss in optimality, and the more nodes become, the more superiority of LRMST algorithm can be reflected.

Figure 3

Comparison of $R^{ac}$ and $R^{wc}$ .

6. Conclusion

Many topology control algorithms do not take into account the distance uncertainty; in fact, the distance is given by a distance measurement algorithm, which results in distance between nodes being uncertain. When the distance is uncertain, using the 0-1 robust discrete optimization theory, a distributed topology control algorithm is proposed. Simulation results show that LRMST algorithm is robust for uncertain data along with the increasing number of nodes, compared with LMST algorithm. This paper has introduced the robust optimization into the topology control technology of WSN for the first time, which provides a new idea for the future research. The robust discrete optimization theory can also be introduced into other research directions of WSN, such as location technology and routing protocol.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (no. 61373174) and the State Key Laboratory of Complex Electromagnetic Environmental Effects on Electronics and Information System (nos. CEEME2012k0207B and CEEME2014k0302A).

References

Santi

Topology control in wireless ad hoc and sensor networks

ACM Computing Surveys 2005 37 2 164 194

10.1145/1089733.1089736

2-s2.0-27344446387

Manolopoulos

Katsaros

Papadimitriou

Topology control algorithms for wireless sensor networks: a critical survey

Proceedings of the 11th International Conference on Computer Systems and Technologies (CompSysTech '10)

June 2010

1 10

10.1145/1839379.1839381

2-s2.0-77956269956

Santi

Topology Control in Wireless Ad hoc and Sensor Networks 2005

John Wiley & Sons

Vasilakos

A. V.

A survey on topology control in wireless sensor networks: taxonomy, comparative study, and open issues

Proceedings of the IEEE 2013 101 12 2538 2557

10.1109/JPROC.2013.2257631

2-s2.0-84889567969

Aziz

A. A.

Sekercioglu

Y. A.

Fitzpatrick

Ivanovich

A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks

IEEE Communications Surveys and Tutorials 2013 15 1 121 144

10.1109/SURV.2012.031612.00124

2-s2.0-84873710092

Blough

D. M.

Leoncini

Resta

Santi

The K-Neigh protocol for symmetric topology control in ad hoc networks

Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '03)

June 2003

Annapolis, Md, USA

ACM library

141 152

2-s2.0-0242443777

Hou

J. C.

Topology control in heterogeneous wireless networks: Problems and solutions

Proceedings of the IEEE Conference on Computer Communications (INFOCOM '04)

March 2004

New York, NY, USA

232 243

2-s2.0-8344232302

Burkhart

Von Rickenbach

Wattenhofer

Zollinger

Does topology control reduce interference?

Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MoBiHoc '04)

May 2004

New York, NY, USA

ACM Press

9 19

2-s2.0-4444336985

Hou

J. C.

Sha

Design and analysis of an MST-based topology control algorithm

IEEE Transactions on Wireless Communications 2005 4 3 1195 1206

10.1109/TWC.2005.846971

2-s2.0-18844404710

10.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

10.1109/TWC.2002.804190

2-s2.0-33646589837

11.

Dantzig

G. B.

Linear programming under uncertainty

Management Science 1955 1 3 197 206

MR0075511

12.

Soyster

A. L.

Convex programming with set-inclusive constraints and applications to inexact linear programming

Operations Research 1973 21 5 1154 1157

10.1287/opre.21.5.1154

13.

Ben-Tal

Nemirovski

Robust convex optimization

Mathematics of Operations Research 1998 23 4 769 805

10.1287/moor.23.4.769

MR1662410

ZBL0977.90052

2-s2.0-0032207223

14.

Ben-Tal

Nemirovski

Robust solutions of uncertain linear programs

Operations Research Letters 1999 25 1 1 13

10.1016/S0167-6377(99)00016-4

MR1702364

ZBL0941.90053

2-s2.0-0032664938

15.

Ben-Tal

Nemirovski

Robust solutions of linear programming problems contaminated with uncertain data

Mathematical Programming 2000 88 3 411 424

10.1007/PL00011380

MR1782149

2-s2.0-0442266090

16.

Ben-Tal

Nemirovski

Robust optimization—methodology and applications

Mathematical Programming: A Publication of the Mathematical Programming Society 2002 92 3 453 480

10.1007/s101070100286

MR1905762

2-s2.0-0141712989

17.

Bertsimas

Sim

Robust discrete optimization and network flows

Mathematical Programming 2003 98 1–3 49 71

10.1007/s10107-003-0396-4

MR2019367

2-s2.0-84870613023

18.

Bertsimas

Sim

The price of robustness

Operations Research 2004 52 1 35 53

10.1287/opre.1030.0065

MR2066239

2-s2.0-3042762207

19.

Ordóñez

Robust optimization models for energy-limited wireless sensor networks under distance uncertainty

IEEE Transactions on Wireless Communications 2008 7 6 2161 2169

10.1109/TWC.2008.060756

2-s2.0-45849136789

20.

Graham

R. L.

Hell

On the history of the minimum spanning tree problem

Annals of the History of Computing 1985 7 1 43 57

10.1109/MAHC.1985.10011

MR783327

ZBL0998.68003

21.

Prim

R. C.

Shortest connection networks and some generalizations

The Bell System Technical Journal 1957 36 6 1389 1401

10.1002/j.1538-7305.1957.tb01515.x

22.

Kruskal

On the shortest spanning subtree of a graph and the traveling salesman problem

Proceedings of the American Mathematical Society 1956 7 48 50

10.1090/S0002-9939-1956-0078686-7

MR0078686

ZBL0070.18404

A Topology Control Algorithm for Sensor Networks Based on Robust Optimization

Abstract

1. Introduction

2. Related Work

3. 0-1 Robust Discrete Optimization Theory

Definition 1 (adjusting parameter Γ ).

Theorem 2 (see [17]).

Theorem 3.

Proof.

4. LRMST Algorithm

4.1. Network Environment

Definition 4 (reachable neighbor set).

4.2. Robust Minimum Spanning Tree (RMST) Algorithm

Definition 5 (minimum spanning tree).

Algorithm 1: RMST algorithm.

Definition 6 (neighbor set).

4.3. Local Robust Minimum Spanning Tree (LRMST) Algorithm

Algorithm 2: LRMST algorithm.

5. Simulation and Performance Analysis

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References

Definition 1 (adjusting parameter $Γ$ ).