# A Topology Control Algorithm for Sensor Networks Based on Robust Optimization

Authors: Junfeng Qiao; Sanyang Liu; Wei Duan
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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 onn 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.


---

## Body

## 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 Section2. 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

Letc, x be n-vectors. We consider the following 0-1 discrete optimization model on a set of n variables:
(1)
min
⁡
W
c
′
x
i
s
.
t
.
W
x
∈
X
⊆
0,1
n
.In this model, the decision variables are binary; that is,x
∈
X
⊆
0,1
n, and the set X is fixed. c is the cost vector and c
=
c
1
,
c
2
,
…
,
c
n
′
∈
R
n.We assume that data uncertainty affects only the elements of cost vectorc. 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
,
…
,
n. Each entry c
j
,
j
∈
N is modeled as an independent bounded random variable c
~
j that takes value in [
c
j
,
c
j
+
d
j
], d
j
≥
0, where c
j is called the nominal value of c
~
j and d
j represents the deviation from the nominal cost coefficient c
j. Thus the uncertainty set U
=
c
~
∣
c
~
j
∈
[
c
j
,
c
j
+
d
j
]
,
j
∈
N. Note that when d
j
=
0, the coefficient 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Γ).
LetJ
=
j
∣
d
j
>
0
,
j
∈
N. Adjusting parameter Γ is used to control the number of uncertain cost coefficients 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(2)
U
=
c
~
∣
c
~
j
∈
c
j
,
c
j
+
d
j
,
∑
j
=
1
n
c
~
j
-
c
j
d
j
≤
Γ
,
j
∈
N
.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 solutionx
∈
X that minimizes the maximum cost c
′
x such that at most Γ of the coefficients c
~
j is allowed to change. The robust counterpart [17] of problem (1) is equivalent to
(3)
min
⁡
W
c
′
x
+
max
⁡
s
∣
s
⊆
N
,
s
≤
Γ
∑
j
∈
S
d
j
x
j
i
s
.
t
.
W
x
∈
X
⊆
0,1
n
.Without loss of generality, we assume that the indices are ordered such thatd
1
≥
d
2
≥
⋯
≥
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:
(4)
R
*
=
min
⁡
l
=
1,2
,
…
,
n
+
1
G
l
,
G
l
=
Γ
d
l
+
min
⁡
x
∈
X
c
′
x
+
∑
j
=
1
l
d
j
-
d
l
x
j
,
WWWWWWWWW
∀
l
=
1,2
,
…
,
n
+
1
,
s
.
t
.
W
x
∈
X
⊆
0,1
n
.Theorem2 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
,
…
,
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
∈
N, only two deterministic problems need to be solved.The following Theorem3 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:
(5)
R
*
=
min
⁡
l
=
Γ
+
1
,
…
,
n
+
1
G
l
,
G
l
=
Γ
d
l
+
min
⁡
x
∈
X
c
′
x
+
∑
j
=
1
l
d
j
-
d
l
x
j
,
WWWWWiWWW
∀
l
=
Γ
+
1
,
…
,
n
+
1
,
s
.
t
.
W
x
∈
X
⊆
0,1
n
.Proof.
LetH
l
x
=
c
′
x
+
∑
j
=
1
l
d
j
-
d
l
x
j,  ∀
l
∈
1,2
,
…
,
n
+
1.
For any feasible solution,x
∈
X,  when l
∈
1,2
,
…
,
n, we have
(6)
H
l
x
-
H
l
+
1
x
=
c
′
x
+
∑
j
=
1
l
d
j
-
d
l
x
j
-
c
′
x
+
∑
j
=
1
l
+
1
d
j
-
d
l
+
1
x
j
=
d
l
+
1
-
d
l
∑
j
=
1
l
x
j
.
Thus
(7)
G
l
-
G
l
+
1
=
Γ
d
l
+
min
⁡
x
∈
X
H
l
x
-
Γ
d
l
+
1
+
min
⁡
x
∈
X
H
l
+
1
x
.
Supposex
l
*
=
x
1
l
*
,
…
,
x
n
l
* is the optimal solution of min
⁡
x
∈
X
⁡
H
l
x, and x
l
*is in the feasible region of min
⁡
x
∈
X
⁡
H
l
+
1
x, from formula (6), we get
(8)
G
l
-
G
l
+
1
≥
Γ
d
l
-
d
l
+
1
+
H
l
x
l
*
-
H
l
+
1
x
l
*
=
Γ
d
l
-
d
l
+
1
+
d
l
+
1
-
d
l
∑
j
=
1
l
x
j
l
*
=
d
l
-
d
l
+
1
Γ
-
∑
j
=
1
l
x
j
l
*
.
Asd
l
≥
d
l
+
1, ∑
j
=
1
l
x
j
l
*
≤
l, we have
(9)
G
l
-
G
l
+
1
≥
d
l
-
d
l
+
1
Γ
-
l
.
So that whenl
≤
Γ, for l
∈
1
,
…
,
n, G
l
-
G
l
+
1
≥
0 holds. The proof is completed.Theorem3 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
,
…
,
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

Assumen 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
,
…
,
v
n, where v
i
(
i
=
1
,
…
,
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
→
v
≤
P
max
⁡, where P
u
→
v denotes the minimum transmit power required when node u communicates with node v, and we suppose P
u
→
v
=
P
v
→
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 nodeu
∈
V is the set of all the one-hop neighbors of u in the max power graph G
=
(
V
,
E
). Formally,
(10)
R
N
u
=
v
∈
V
∣
P
u
→
v
≤
P
max
⁡
.
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
∈
R
N
u
,
(
v
i
,
v
j
)
∈
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 Section3. Specifically, for each edge (
v
i
,
v
j
)
∈
E, let d
i
j denote the estimated distance obtained by a distance measurement algorithm, while the actual distance is d
~
i
j. As mentioned above, d
~
i
j takes value in d
i
j
,
d
i
j
+
ω
i
j; that is, d
~
i
j
∈
d
i
j
,
d
i
j
+
ω
i
j, where the constant ω
i
j
≥
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 graphG
=
(
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
)
⊆
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 graphG
=
V
,
E is given:
(11)
min
⁡
W
∑
v
i
,
v
j
∈
E
T
d
i
j
x
i
j
i
s
.
t
.
W
∑
v
i
,
v
j
∈
E
T
x
i
j
=
n
-
1
,
s
.
t
.
W
x
i
j
=
1
v
i
,
v
j
∈
E
T
0
v
i
,
v
j
∉
E
T
,
s
.
t
.
W
x
=
x
i
j
v
i
,
v
j
∈
E
∈
X
⊆
0,1
m
,
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
(12)
min
⁡
W
∑
v
i
,
v
j
∈
E
T
d
i
j
x
i
j
+
max
⁡
S
∣
S
⊆
E
T
,
S
=
Γ
∑
v
i
,
v
j
∈
S
ω
i
j
x
i
j
i
s
.
t
.
W
∑
v
i
,
v
j
∈
E
T
x
i
j
=
n
-
1
,
s
.
t
.
W
x
i
j
=
1
v
i
,
v
j
∈
E
T
0
v
i
,
v
j
∉
E
T
,
s
.
t
.
W
x
=
x
i
j
v
i
,
v
j
∈
E
∈
X
⊆
0,1
m
.
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
⋅
d
~
:
E
→
R
+ is a
distance function andd
~ is uncertain, it takes value in [
d
i
j
,
d
i
j
+
ω
i
j
], (
v
i
,
v
j
)
∈
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
)
∈
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 setN
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,
(13)
N
u
=
v
∈
R
N
u
∣
u
,
v
∈
E
u
T
.


### 4.3. Local Robust Minimum Spanning Tree (LRMST) Algorithm

Taking nodeu as an example, the LRMST algorithm is presented in Algorithm 2.Algorithm 2:LRMST algorithm.
(algorithm for nodeu)
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 inR
N
u using RMST algorithm
letT
u
=
(
R
N
u
,
E
u
(
T
)
) be this local robust MST
N
u
=
{
v
∈
R
N
u
|
(
u
,
v
)
∈
E
u
(
T
)
}
(3) Determination of transmit power
for eachv
∈
N
u
compute the minimum powerm
p
v needed to reach the farthest node in N
u
t
p
u
=
max
⁡
v
∈
N
u
m
p
v
(4) Bidirectional topology formation
similar to that of LMST, omitted here


## 4.1. Network Environment

Assumen 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
,
…
,
v
n, where v
i
(
i
=
1
,
…
,
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
→
v
≤
P
max
⁡, where P
u
→
v denotes the minimum transmit power required when node u communicates with node v, and we suppose P
u
→
v
=
P
v
→
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 nodeu
∈
V is the set of all the one-hop neighbors of u in the max power graph G
=
(
V
,
E
). Formally,
(10)
R
N
u
=
v
∈
V
∣
P
u
→
v
≤
P
max
⁡
.
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
∈
R
N
u
,
(
v
i
,
v
j
)
∈
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 Section3. Specifically, for each edge (
v
i
,
v
j
)
∈
E, let d
i
j denote the estimated distance obtained by a distance measurement algorithm, while the actual distance is d
~
i
j. As mentioned above, d
~
i
j takes value in d
i
j
,
d
i
j
+
ω
i
j; that is, d
~
i
j
∈
d
i
j
,
d
i
j
+
ω
i
j, where the constant ω
i
j
≥
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 graphG
=
(
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
)
⊆
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 graphG
=
V
,
E is given:
(11)
min
⁡
W
∑
v
i
,
v
j
∈
E
T
d
i
j
x
i
j
i
s
.
t
.
W
∑
v
i
,
v
j
∈
E
T
x
i
j
=
n
-
1
,
s
.
t
.
W
x
i
j
=
1
v
i
,
v
j
∈
E
T
0
v
i
,
v
j
∉
E
T
,
s
.
t
.
W
x
=
x
i
j
v
i
,
v
j
∈
E
∈
X
⊆
0,1
m
,
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
(12)
min
⁡
W
∑
v
i
,
v
j
∈
E
T
d
i
j
x
i
j
+
max
⁡
S
∣
S
⊆
E
T
,
S
=
Γ
∑
v
i
,
v
j
∈
S
ω
i
j
x
i
j
i
s
.
t
.
W
∑
v
i
,
v
j
∈
E
T
x
i
j
=
n
-
1
,
s
.
t
.
W
x
i
j
=
1
v
i
,
v
j
∈
E
T
0
v
i
,
v
j
∉
E
T
,
s
.
t
.
W
x
=
x
i
j
v
i
,
v
j
∈
E
∈
X
⊆
0,1
m
.
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
⋅
d
~
:
E
→
R
+ is a
distance function andd
~ is uncertain, it takes value in [
d
i
j
,
d
i
j
+
ω
i
j
], (
v
i
,
v
j
)
∈
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
)
∈
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 setN
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,
(13)
N
u
=
v
∈
R
N
u
∣
u
,
v
∈
E
u
T
.


## 4.3. Local Robust Minimum Spanning Tree (LRMST) Algorithm

Taking nodeu as an example, the LRMST algorithm is presented in Algorithm 2.Algorithm 2:LRMST algorithm.
(algorithm for nodeu)
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 inR
N
u using RMST algorithm
letT
u
=
(
R
N
u
,
E
u
(
T
)
) be this local robust MST
N
u
=
{
v
∈
R
N
u
|
(
u
,
v
)
∈
E
u
(
T
)
}
(3) Determination of transmit power
for eachv
∈
N
u
compute the minimum powerm
p
v needed to reach the farthest node in N
u
t
p
u
=
max
⁡
v
∈
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 isd
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, forD
1, the deviation ω
i
j between the node’s estimated distance d
i
j and the actual distance 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
)
∈
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
)
∈
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]
(14)
R
ac
=
R
d
-
L
d
L
d
,
R
wc
=
L
d
~
-
R
d
~
L
d
~
,
where L
d is optimal value of LMST algorithm with deterministic data. R
d is objective value of LRMST algorithm with deterministic data. L
d
~ is objective value of LMST algorithm with uncertain data. R
d
~ is optimal value of LRMST algorithm with uncertain data.The first ratioR
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.Figures1(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.Comparison of the topology structure generated by LMST algorithm and LRMST algorithm.
(a)
The topology structure generated by LMST
(b)
The topology structure generated by LRMSTThe average node degrees of LMST algorithm and LRMST algorithm are compared in Figure2, 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.Figure3 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 ofR
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.



---

*Source: 140709-2015-01-21.xml*