# Energy Efficient Wireless Sensor Network Modelling Based on Complex Networks

Authors: Lin Xiao; Fahui Wu; Dingcheng Yang; Tiankui Zhang; Xiaoya Zhu
Journal: Journal of Sensors
 (2016)

---

## Abstract

The power consumption and energy efficiency of wireless sensor network are the significant problems in Internet of Things network. In this paper, we consider the network topology optimization based on complex network theory to solve the energy efficiency problem of WSN. We propose the energy efficient model of WSN according to the basic principle of small world from complex networks. Small world network has clustering features that are similar to that of the rules of the network but also has similarity to random networks of small average path length. It can be utilized to optimize the energy efficiency of the whole network. Optimal number of multiple sink nodes of the WSN topology is proposed for optimizing energy efficiency. Then, the hierarchical clustering analysis is applied to implement this clustering of the sensor nodes and pick up the sink nodes from the sensor nodes as the clustering head. Meanwhile, the update method is proposed to determine the sink node when the death of certain sink node happened which can cause the paralysis of network. Simulation results verify the energy efficiency of the proposed model and validate the updating of the sink nodes to ensure the normal operation of the WSN.


---

## Body

## 1. Introduction

Wireless sensor network (WSN), which combines the technology of sensors, embedded computing, and wireless communications, is the most important element in the Internet of Things.In this paper, we consider the large scale WSN which consists of sensor nodes and sink nodes. The sink node among senor nodes will play the central control function; the control information and transmission signal will be passed through the sink node. Considering the work load and efficiency of the sink node, multiple sink nodes will be deployed in the network [1].The power consumption and energy efficiency of WSN are the significant problem of the operation of the WSN. The network deployment (especially sink node placement) and topology control of the WSN have great effect on the energy efficiency of WSN [2].When mentioning sink node placement, most researches consider the influence from the location of the sink node to the network lifetime. Reference [3] researched the sink node deployment strategy under the lattice structure. Reference [4] proposed two kinds of algorithms; one is a global algorithm based on the sink node placement for the general; the other is the one-hop algorithm based on the information of adjacent nodes. They are all able to prolong the network lifetime to some extent. References [5, 6] researched sink nodes with mobility that can distribute their positions according to the energy consumption of the network so as to extend network lifetime. Reference [7] proposed a kind of heuristic algorithm on the foundation of the simple structure that assuming the distance from sensor nodes to sink nodes is only one hop. Reference [8] proposed a general energy consumption model suited for common sensor nodes and heterogeneous nodes topology. Reference [9] improved the property of [8] and proposed the constraint conditions of the death for the model.Recently, some works focus on wireless network topology modeling based on complex network theory. Reference [10] added shortcuts to the wireless mesh network taking into account practical constraints, such as radio transmission range of nodes, numbers of radios per mesh router, and available bandwidth of wireless links. Long range shortcuts can be created by either adding wired links [11] or directional beamforming [12]. The authors in [13] proposed a multicast reprogramming protocol for wireless sensor networks based on small world concepts. Reference [2] proposed energy efficiency small world ad hoc networks, which gave a tradeoff between energy consumption and network performance.In this paper, we consider the network topology optimization based on complex network theory to solve the energy efficiency problem of WSN. In this paper, sensor nodes and sink nodes will be connected in accordance with the small world characteristic. Based on the features of small world network, nodes can be randomly added or rewired so as to contract the average path length and decline energy consumption. We use clustering analysis method to separate the large numbers of sensor nodes and select sink nodes from them and maximize the energy efficiency.This paper is organized as follows. Section2 gives the proposed energy efficient WSN topology. The performance is validated by simulation in Section 3. Finally, Section 4 gives the conclusion of this paper.


## 2. Proposed Energy Efficient WSN Topology

In this energy efficient WSN model, firstly we discuss the optimization problem for the network topology by setting multiple sink nodes; then we obtain the energy efficiency of such WSN.


### 2.1. Initialize the Small World Topology

Sensor nodes in the network are arranged randomly; the adjacency matrix for them will be constructed according to the distance between any two nodes. This distance will be calculated by the distance formula based on the coordinate(
i
,
j
) of rectangular coordinate system, and the calculation formula is(1)
d
i
,
j
=
x
i
-
x
j
2
+
y
i
-
y
j
2
.After obtaining the adjacency matrix, the fundamental small world topology can be obtained by proposed method in [2].


### 2.2. Determine the Optimal Number for Sink Nodes

Sink nodes of the WSN topology should be picked up from the sensor nodes network with the small world characteristic. Since multiple sink nodes will be applied in the network, clustering analysis is used since its categories for the cluster share the similarity of the central communication function of sink nodes. The hierarchical clustering analysis is selected to implement this clustering for a series of sensor nodes from the bottom to the top level with the comparison of nodes communication distance.To start the analysis for clustering, the proper number for sink nodes should be identified at first. So as to display the energy saving and high efficiency feature of the proposed model, the number for sink nodes ought to be weighed among the network lifetime, sink node cost, and initial energy for the network. The used variables in this paper are given as follows.Variables Definition
n: number of sink nodes;
N: total number of nodes in the network;
K: number of key nodes each sink node links with;
E
t: transmission energy for communication per nodes pair;
E
r: receiving energy for communication per nodes pair;
E
o: other energy consumption when nodes do not communicate;
E
i: initial energy per key node per sink node;
P: total energy cost per key node for one time of inter node communication;
L: lifetime for key node;
C: network cost for the whole;
C
s: cost per sink node;
C
n: cost per sensor node;
CR: ratio ofC
s to C
n.During the process that sensor nodes communicate with sink nodes, data from sensor nodes will be delivered to key nodes firstly which linked directly with sink nodes. Key nodes have to pass the data from(
N
-
K
)
/
K sensor nodes.The total energy cost per key node for one time of inter node communication will be(2)
P
=
E
t
+
N
/
n
-
K
K
E
r
+
E
t
+
E
o
,
N
≥
n
·
K
.Define the function of lifetime for key nodes as(3)
L
=
E
i
P
=
E
i
E
t
+
N
/
n
-
K
/
K
E
t
+
E
r
+
E
o
,
N
≥
n
·
K
.It is easy to see that, with the increase of the number of sink nodes, the lifetime for key nodes increases as well. While sink nodes number keeps increasing, making the hop for any sensor nodes in the network be 1, just asN
=
n
·
K, the more increase for sink nodes number will be meaningless to the lifetime.Then we define the network cost function as(4)
C
=
N
·
C
n
+
n
·
C
s
.For fixed scale WSN, the value of N
·
C
n is fixed, and the value of n
·
C
s will get to change with the value of sink nodes number n. The more the sink nodes in this network, the more the cost of the network.The proper number of sink nodes can be obtained by(5)
L
C
=
E
i
·
E
t
+
N
n
·
K
-
1
E
t
+
E
r
+
E
o
N
·
C
n
+
n
·
C
s
-
1
.In order to gain the optimal number for sink nodesn, the derivation towards the ratioL/C is shown as follows:(6)
d
L
/
C
d
n
=
-
E
i
M
2
·
d
M
d
n
,where M represents(7)
M
=
E
t
+
N
n
·
K
-
1
E
t
+
E
r
+
E
o
N
·
C
n
+
n
·
C
s
.So do the second derivation towardsM:(8)
d
M
d
n
=
0
.Finally, the proper numbern can be worked out as(9)
n
=
N
C
n
C
s
·
E
t
+
E
r
K
E
o
-
E
r
.Take the resultn into the cluster analysis; the multiple sink nodes topology can identify the number of communication centres in the WSN.


### 2.3. Identify the Multiple Sink Nodes

Take the optimal value of sink nodes into cluster category and go for hierarchical clustering. Since the hierarchical clustering is the cluster method based on distance, the process of it can be divided into the following steps.At first, find the similarity among objects and define the distance that can represent the differentiation of them. In this paper, the Euclidean distance that is calculated above is selected to realize the dissimilarity of them. When the objectsi and j have a close relation, the value of d
(
i
,
j
) is rather small, even close to 0.Next, produce the hierarchical cluster tree with the linkage function. In accordance with the hierarchical clustering analysis for nodes topology, the distribution for sink nodes can be marked out; this process is shown in Figure1.Figure 1
Flow chart of the cluster process.Just as Figure1 shows, cluster nodes according to the matrix and sink nodes number which acts as cluster category; then separate individuals of the cluster based on the functionextract_clabel(T, K) and name it as cluster point; put separated cluster points into the functionstruct_property(a, b, c, d), to calculate for the solution of category node for cluster, sink node, and link distance between nodes and adjacency matrix. The details of functionextract_clabel(T, K) and functionstruct_property(a, b, c, d) are given in Algorithms 1 and 2, separately.Algorithm 1:Function of extract_clabel(T, K).
function clust_point = extract_clabel(T, K)
% T: Number of the cluster, category that each individual belongs to
% K: Category numbers of the cluster
% clust_point: Divide data points of cluster, data points which have common points ascribed as one
nT = length(T);
num = 1;
for i = 1 : K
num = 1;
for j = 1 : nT
if T(j) == i
clust_point(i, num) = j;
num = num + 1;
end
end
endAlgorithm 2:Function of struct_property(a
,
b
,
c
,
d).
function struc_data = stuct_property(clust_point, num_categ, A, D)
% Work out value for individuals, adjacency matrix, distance matrix, give back the structure struc_data
% clust_point: cluster individuals of per line
% num_categ: numbers of cluster
% A: initial data adjacency matrix
% D: initial data distance matrix
% struc_data
nc = size(clust_point);   % size
for i = 1 : num_categ
data(i).point =
[
]
;   % individual of the cluster
data(i).center =
[
]
;  % cluster center
data(i).A =
[
]
;       % adjacency matrix of the cluster
data(i).D =
[
]
;       % distance of the cluster
% cluster individuals
for j = 1 : nc(1, 2)
if clust_point(i, j) ~= 0
data(i).point = [data(i).point, clust_point(i, j)];
end
end
% adjacency + distance
np = length(data(i).point);
for j = 1 : np
for k = 1 : np
data(i).A(j, k) = A(data(i).point(j), data(i).point(k));
data(i).D(j, k) = D(data(i).point(j), data(i).point(k));
end
end
% cluster center
sum_D = sum((data(i).D)′);
[sum_min_D, flag] = min(sum_D);   % center with shortest path
data(i).center = data(i).point(flag);
end
struc_data = data;


### 2.4. Consider Dynamic Changes on Sink Nodes

For the realistic application, due to the complexity of detected environment and unknown factors for sink nodes, if they were broken and stopped working, the network may also get into trouble. So it is necessary to think about the backup to maintain the normal operation of the whole network. The sink node judgment process is shown in Figure2.Figure 2
Flow chart of the sink node judgment process.A flag that represents working state will be set up with the help of rand function. If the flag was set to be 0 which means this sink node was dead, the functionup_struct_property(data) as shown in Algorithm 3 would help to replace the dead sink node with a new one. Then the new sink node was picked up according to the node link distance. If the flag was set to be 1 which means the sink node worked as usual, nothing would be updated for this sink node, and it would continue the node communication.Algorithm 3:Function of s
t
r
u
c
t
_
p
r
o
p
e
r
t
y
(
a
,
b
,
c
,
d
).
function struc_data = up_stuct_property(data)
% Utilized for updating the dead sink nodes
% Work out value for individuals, adjacency matrix, distance matrix, give back the structure struc_data
% clust_point: cluster individuals of per line
% num_categ: numbers of cluster
% A: initial data adjacency matrix
% D: initial data distance matrix
% data: structure of different categories
% cluster center
sum_D = sum((data.D)′);
[sum_sort_D, flag] = sort(sum_D);   % distance arranged from small to lrge, the second small one as the center
data.center = data.point(flag(2)); % choose the second small one as the sink node center
struc_data = data


### 2.5. Energy Efficiency Measurement

The calculation for the energy consumption in the network is processed during the nodes communication. So firstly, the communication source and destination should be identified which concerns the judgment process of the state of sink nodes. Then, work out the calculation method for the energy consumption which is based on the formula for path loss while nodes are communicating. Within the path loss formula, the communication distance is required. And this will be achieved by the weighed shortest routing. Path loss is considered to measure the transmission loss in the topology as the energy consumption per sink node communication. Moreover, with the comparison between the initial energy of the network and total energy consumption, efficiency for the network is sure to be found out and go for optimizing. All the mentioned variables are summarized as follows.Variables Definition
Pl: path loss for one time of communication among the sink nodes;
d
min
⁡: minimum transmission distance between nodes;
E
ini: initial energy for the whole network;
η
e: energy efficiency of the network.The energy efficiency of the network is measured by the Pl between communication nodes pair, so the energy efficiency can be worked out as(10)
η
e
=
E
ini
-
∑
Pl
E
ini
=
1
-
∑
Pl
E
ini
.


## 2.1. Initialize the Small World Topology

Sensor nodes in the network are arranged randomly; the adjacency matrix for them will be constructed according to the distance between any two nodes. This distance will be calculated by the distance formula based on the coordinate(
i
,
j
) of rectangular coordinate system, and the calculation formula is(1)
d
i
,
j
=
x
i
-
x
j
2
+
y
i
-
y
j
2
.After obtaining the adjacency matrix, the fundamental small world topology can be obtained by proposed method in [2].


## 2.2. Determine the Optimal Number for Sink Nodes

Sink nodes of the WSN topology should be picked up from the sensor nodes network with the small world characteristic. Since multiple sink nodes will be applied in the network, clustering analysis is used since its categories for the cluster share the similarity of the central communication function of sink nodes. The hierarchical clustering analysis is selected to implement this clustering for a series of sensor nodes from the bottom to the top level with the comparison of nodes communication distance.To start the analysis for clustering, the proper number for sink nodes should be identified at first. So as to display the energy saving and high efficiency feature of the proposed model, the number for sink nodes ought to be weighed among the network lifetime, sink node cost, and initial energy for the network. The used variables in this paper are given as follows.Variables Definition
n: number of sink nodes;
N: total number of nodes in the network;
K: number of key nodes each sink node links with;
E
t: transmission energy for communication per nodes pair;
E
r: receiving energy for communication per nodes pair;
E
o: other energy consumption when nodes do not communicate;
E
i: initial energy per key node per sink node;
P: total energy cost per key node for one time of inter node communication;
L: lifetime for key node;
C: network cost for the whole;
C
s: cost per sink node;
C
n: cost per sensor node;
CR: ratio ofC
s to C
n.During the process that sensor nodes communicate with sink nodes, data from sensor nodes will be delivered to key nodes firstly which linked directly with sink nodes. Key nodes have to pass the data from(
N
-
K
)
/
K sensor nodes.The total energy cost per key node for one time of inter node communication will be(2)
P
=
E
t
+
N
/
n
-
K
K
E
r
+
E
t
+
E
o
,
N
≥
n
·
K
.Define the function of lifetime for key nodes as(3)
L
=
E
i
P
=
E
i
E
t
+
N
/
n
-
K
/
K
E
t
+
E
r
+
E
o
,
N
≥
n
·
K
.It is easy to see that, with the increase of the number of sink nodes, the lifetime for key nodes increases as well. While sink nodes number keeps increasing, making the hop for any sensor nodes in the network be 1, just asN
=
n
·
K, the more increase for sink nodes number will be meaningless to the lifetime.Then we define the network cost function as(4)
C
=
N
·
C
n
+
n
·
C
s
.For fixed scale WSN, the value of N
·
C
n is fixed, and the value of n
·
C
s will get to change with the value of sink nodes number n. The more the sink nodes in this network, the more the cost of the network.The proper number of sink nodes can be obtained by(5)
L
C
=
E
i
·
E
t
+
N
n
·
K
-
1
E
t
+
E
r
+
E
o
N
·
C
n
+
n
·
C
s
-
1
.In order to gain the optimal number for sink nodesn, the derivation towards the ratioL/C is shown as follows:(6)
d
L
/
C
d
n
=
-
E
i
M
2
·
d
M
d
n
,where M represents(7)
M
=
E
t
+
N
n
·
K
-
1
E
t
+
E
r
+
E
o
N
·
C
n
+
n
·
C
s
.So do the second derivation towardsM:(8)
d
M
d
n
=
0
.Finally, the proper numbern can be worked out as(9)
n
=
N
C
n
C
s
·
E
t
+
E
r
K
E
o
-
E
r
.Take the resultn into the cluster analysis; the multiple sink nodes topology can identify the number of communication centres in the WSN.


## 2.3. Identify the Multiple Sink Nodes

Take the optimal value of sink nodes into cluster category and go for hierarchical clustering. Since the hierarchical clustering is the cluster method based on distance, the process of it can be divided into the following steps.At first, find the similarity among objects and define the distance that can represent the differentiation of them. In this paper, the Euclidean distance that is calculated above is selected to realize the dissimilarity of them. When the objectsi and j have a close relation, the value of d
(
i
,
j
) is rather small, even close to 0.Next, produce the hierarchical cluster tree with the linkage function. In accordance with the hierarchical clustering analysis for nodes topology, the distribution for sink nodes can be marked out; this process is shown in Figure1.Figure 1
Flow chart of the cluster process.Just as Figure1 shows, cluster nodes according to the matrix and sink nodes number which acts as cluster category; then separate individuals of the cluster based on the functionextract_clabel(T, K) and name it as cluster point; put separated cluster points into the functionstruct_property(a, b, c, d), to calculate for the solution of category node for cluster, sink node, and link distance between nodes and adjacency matrix. The details of functionextract_clabel(T, K) and functionstruct_property(a, b, c, d) are given in Algorithms 1 and 2, separately.Algorithm 1:Function of extract_clabel(T, K).
function clust_point = extract_clabel(T, K)
% T: Number of the cluster, category that each individual belongs to
% K: Category numbers of the cluster
% clust_point: Divide data points of cluster, data points which have common points ascribed as one
nT = length(T);
num = 1;
for i = 1 : K
num = 1;
for j = 1 : nT
if T(j) == i
clust_point(i, num) = j;
num = num + 1;
end
end
endAlgorithm 2:Function of struct_property(a
,
b
,
c
,
d).
function struc_data = stuct_property(clust_point, num_categ, A, D)
% Work out value for individuals, adjacency matrix, distance matrix, give back the structure struc_data
% clust_point: cluster individuals of per line
% num_categ: numbers of cluster
% A: initial data adjacency matrix
% D: initial data distance matrix
% struc_data
nc = size(clust_point);   % size
for i = 1 : num_categ
data(i).point =
[
]
;   % individual of the cluster
data(i).center =
[
]
;  % cluster center
data(i).A =
[
]
;       % adjacency matrix of the cluster
data(i).D =
[
]
;       % distance of the cluster
% cluster individuals
for j = 1 : nc(1, 2)
if clust_point(i, j) ~= 0
data(i).point = [data(i).point, clust_point(i, j)];
end
end
% adjacency + distance
np = length(data(i).point);
for j = 1 : np
for k = 1 : np
data(i).A(j, k) = A(data(i).point(j), data(i).point(k));
data(i).D(j, k) = D(data(i).point(j), data(i).point(k));
end
end
% cluster center
sum_D = sum((data(i).D)′);
[sum_min_D, flag] = min(sum_D);   % center with shortest path
data(i).center = data(i).point(flag);
end
struc_data = data;


## 2.4. Consider Dynamic Changes on Sink Nodes

For the realistic application, due to the complexity of detected environment and unknown factors for sink nodes, if they were broken and stopped working, the network may also get into trouble. So it is necessary to think about the backup to maintain the normal operation of the whole network. The sink node judgment process is shown in Figure2.Figure 2
Flow chart of the sink node judgment process.A flag that represents working state will be set up with the help of rand function. If the flag was set to be 0 which means this sink node was dead, the functionup_struct_property(data) as shown in Algorithm 3 would help to replace the dead sink node with a new one. Then the new sink node was picked up according to the node link distance. If the flag was set to be 1 which means the sink node worked as usual, nothing would be updated for this sink node, and it would continue the node communication.Algorithm 3:Function of s
t
r
u
c
t
_
p
r
o
p
e
r
t
y
(
a
,
b
,
c
,
d
).
function struc_data = up_stuct_property(data)
% Utilized for updating the dead sink nodes
% Work out value for individuals, adjacency matrix, distance matrix, give back the structure struc_data
% clust_point: cluster individuals of per line
% num_categ: numbers of cluster
% A: initial data adjacency matrix
% D: initial data distance matrix
% data: structure of different categories
% cluster center
sum_D = sum((data.D)′);
[sum_sort_D, flag] = sort(sum_D);   % distance arranged from small to lrge, the second small one as the center
data.center = data.point(flag(2)); % choose the second small one as the sink node center
struc_data = data


## 2.5. Energy Efficiency Measurement

The calculation for the energy consumption in the network is processed during the nodes communication. So firstly, the communication source and destination should be identified which concerns the judgment process of the state of sink nodes. Then, work out the calculation method for the energy consumption which is based on the formula for path loss while nodes are communicating. Within the path loss formula, the communication distance is required. And this will be achieved by the weighed shortest routing. Path loss is considered to measure the transmission loss in the topology as the energy consumption per sink node communication. Moreover, with the comparison between the initial energy of the network and total energy consumption, efficiency for the network is sure to be found out and go for optimizing. All the mentioned variables are summarized as follows.Variables Definition
Pl: path loss for one time of communication among the sink nodes;
d
min
⁡: minimum transmission distance between nodes;
E
ini: initial energy for the whole network;
η
e: energy efficiency of the network.The energy efficiency of the network is measured by the Pl between communication nodes pair, so the energy efficiency can be worked out as(10)
η
e
=
E
ini
-
∑
Pl
E
ini
=
1
-
∑
Pl
E
ini
.


## 3. Simulation Results

In this section, we present the simulation results of the proposed energy efficient small world WSN model. The simulation is realized by MATLAB.The simulation condition is selected within a square of 100 m × 100 m. Other variables in the simulation are shown in Table1. Figure 3 shows the small world WSN topology with 64 sensor nodes. And the path loss is defined as(11)
Pl
=
50.5
+
10
×
7.4
×
log
10
⁡
d
min
⁡
10
.Table 1
Variables definition.
Variable
Values
N
64
K
8
E
t
0.02
E
r
0.02
E
i
0.5
E
ini
1000
CR
5Figure 3
Small world WSN topology.From (9) we can work out the optimal sink nodes number n in this simulation to be 3, which means there will be 3 sink nodes in this WSN. According to the function ofextract_clabel(T, K)andstruct_property(a, b, c, d), there are 3 sink nodes, in the positions 1, 17, and 26, marked with black in the topology as shown in Figure 4.Figure 4
Small world WSN with sink nodes marked.From Figure5 we can see that a minimum point with the horizontal coordinate 3 is presented with a lower energy consumption. The results in Figure 6 show that the energy efficiency of the network reached a higher point when the sink nodes number is 3.Figure 5
Relation between sink nodes number and energy consumption.Figure 6
Relation between sink nodes number and energy efficiency.However, notice that when sink node numbers increased to 50 or even more, where there were a total of 64 nodes in the network, the energy consumption can get lower and the energy efficiency can get higher even than before. So there should be another factor that can determine influence of the choice of optimal sink node numbers.According to what was showed in Figure7, sink node numbers decrease with the increase of CR. In order to realize the 50 and even more numbers of sink nodes, the value for CR should be rather small. But to get a small value of CR not only requires the small value of C
s, but also needs a large value of C
n. And the cost for C
s is not less than C
n is always set up. So in this 64-node topology, it is impossible to realize the value 50 or even more as the number of sink nodes. So the value 3 for optimal sink node numbers is the best choice for this WSN.Figure 7
Relation between CR and sink node numbers.Figure8 shows sink nodes can work as usual. When some of the sink nodes are out of work, solution can be given in Section 3, and the simulation results are given in Figure 9.Figure 8
Small world topology as usual.Figure 9
Small world topology updated.


## 4. Conclusion

In this paper, we propose a wireless sensor network model for energy efficiency, in which we first give the method of multiple sink nodes deployment and then consider the adjustment for dynamic change on sink nodes. In the proposed model, identification of the number and position of sink nodes has been considered. According to the hierarchical clustering analysis, the small world WSN with multiple sink nodes marked finally worked out. When it comes to considering the realistic application of WSN, an update function helps to update sink nodes when some of them are out of work. Finally, we give the simulation results of the proposed energy efficient small world WSN model.



---

*Source: 3831810-2015-11-30.xml*