# R-bUCRP: A Novel Reputation-Based Uneven Clustering Routing Protocol for Cognitive Wireless Sensor Networks

Authors: Mingchuan Zhang; Ruijuan Zheng; Ying Li; Qingtao Wu; Liang Song
Journal: Journal of Sensors
 (2016)

---

## Abstract

Energy of nodes is an important factor that affects the performance of Wireless Sensor Networks (WSNs), especially in the case of existing selfish nodes, which attracted many researchers’ attention recently. In this paper, we present a reputation-based uneven clustering routing protocol (R-bUCRP) considering both energy saving and reputation assessment. In the cluster establishment phase, we adopt an uneven clustering mechanism which controls the competitive scope of cluster head candidates to save the energy of WSNs. In the cluster heads election phase, the residual energy and reputation value are used as the indexes to select the optimal cluster head, where the reputation mechanism is introduced to support reputation assessment. Simulation results show that the proposed R-bUCRP can save node energy consumption, balance network energy distribution, and prolong network lifetime.


---

## Body

## 1. Introduction

As a new ubiquitous network, Wireless Sensor Networks (WSNs) are widely used in various fields, such as ecological protection, energy conservation and emission reduction, and food security. As a huge network, WSNs have diverse sensor nodes and multifarious communication protocols. The resource management for WSNs is difficult and the application fields are extensive. Meanwhile, the complexity and uncertainty promote the idea that cognition becomes an important characteristic for WSNs.In 1999, Dr. Mitola and Maguire Jr. [1] proposed the concept of cognitive radio and integrated “cognitive” elements into radio networks, which has attracted a lot of researches and has achieved many research results. The thought of cognition promoted the development of network intelligence greatly. Cognitive radio network [2, 3], cognitive network [4–6], and Cognitive Internet of Things [7, 8] have greatly interested the researchers, and large numbers of achievements have been attained, which greatly promoted the evolution of network intelligence.In recent years, with the rapid development of the WSNs, the WSNs’ intelligent feature has been involved in more and more researches. The concept of the Cognitive Wireless Sensor Networks (CWSNS) is derived from the autonomic computing [9] and bioinspired theory [10], which puts the “cognitive” element into the WSNs. Since its core idea is to put the intelligent characteristic into IoT, CIoT has the characteristics of self-perception, self-decision, self-learning, self-optimization, and self-adjustment. For network communications, although nodes should cooperate with each other and provide services for others, the existing research shows that a large number of nodes only want to enjoy the services provided by other nodes due to the limited energy of nodes but do not want to provide services for others [11]. Since CWSNS is a large scale network with limited energy and different performance goals in different regional network, there could be many selfish nodes which would cause negative forwarding of packets. Scientific researches prove that forward selfish behavior will affect seriously the network performance—just only a small number of selfish nodes (10%–40%) will lead to a significant decrease (16%–32%) of network performance [12]. Therefore, how to design a reliable routing mechanism is a key problem to be solved in the information transmission field of CWSNS.Considering the characteristics of scalability and energy saving in networks, the clustering method is always applied to the heterogeneous Wireless Sensor Network protocols, especially in the large scale network. The clustering method provides a hierarchical structure for the network, which has two members, the cluster head nodes and the cluster member nodes. The cluster head nodes have better basic conditions and manage their cluster member. They fuse the information that cluster member nodes collected and then send it to the base station. In the early stage, the route clustering often used even clustering method. The typical even clustering protocols include LEACH [13], TEEN [14], and APTEEN [15]. Subsequently, Bhasker [16] proposes a genetically derived secure cluster-based data aggregation in WSN which minimizes the energy consumption, ensures data security, and reduces the transmission overhead. Lin and Uster [17] consider a mixed-integer linear programming (MILP) model to optimally determine the sink and CH locations as well as the data flow in the network, which could prolong the network lifetime. Quang and Kim [18] propose a clustering algorithm to enhance the performance of fixed wireless sensor and actuators networks (WSANs). In each cluster, a multilevel hierarchical structure can be applied to reduce the energy consumption. In addition to the cluster head, some nodes can be selected as intermediate nodes, which manages a subcluster. Li and Hua [19] propose a clustering algorithm for energy-efficiency in Wireless Sensor Networks, which is partially similar to this paper. The requirements of even clustering method are even size of clusters in networks and the same number of nodes in the cluster. Polling method used in cluster head election could balance the energy consumption. However, data collection, data fusion, and communication with the base station are usually completed alone by the cluster head node, which will cause premature death, energy consumption imbalance, and short network lifetime.In order to solve the problem, many researchers have focused in their works on the uneven clustering method to balance the energy consumption. EECS [20] not only considers the distance between cluster member nodes and cluster head nodes, but also considers the distance of the cluster head nodes to the base station and constructs uneven size of clusters to ease the problem of the uneven energy consumption. UCS [21] balanced the energy consumption of the cluster head nodes and adjusted the size of the cluster according to the expected forwarding load of the cluster head nodes. EEUC [22] made use of the uneven size of competitive radius. The number of the cluster members near the base station is relatively small, so that the cluster head nodes could save energy for the cluster data forwarding. It optimizes the energy consumption of nodes and prolongs the network lifetime significantly. CEB-UC [23] showed the reasonable partition of the network area. The closer to the base station clusters are, the less sensor nodes in each cluster are, so that the energy consumption of nodes in the network is balanced. Jiang et al. [24] achieved the uneven clustering by uneven layering of the sensor network model. Each layer forms the cluster independently to balance the energy consumption of cluster head nodes and prolong the network lifetime. Buchegger and Le Boudec [25] used cluster head competitive algorithm based time rules. The broadcast time depends on the residual energy of the cluster head candidate nodes and their neighbor nodes. The energy consumption of the nodes could be compensated by each other.The above researches use energy and distance to elect cluster heads and clustering. However, the reliability of the cluster head nodes is also very important. The reputation value of the nodes is often used to measure the reliability of the nodes. The higher the reputation value of the cluster head nodes is, the more reliable the nodes are and the higher the quality of service provided by the nodes in the cluster is. Naghizadeh and Liu [26] describe the reputation problem in a distributed multiuser system by using a mechanism design theoretic approach. They introduce a number of utility models representing users’ strategic behavior and design a mechanism that achieves the optimal performance. Due to the node collusion impairing the effectiveness of reputation systems in trustworthy node selection, Li et al. [27] identify suspicious collusion behavior by examining the overstock transaction trace of reputation ratings and propose the Social Trust mechanism that leverages a social network to combat collusion. Refaei et al. [28] introduce a time-slotted approach to allow the evaluation function to quickly and accurately capture changes in node behavior and show the ability to achieve high accuracy and promptness in dynamic environments. Labraoui et al. [29] propose a Risk-aware Reputation-based Trust (RaRTrust) model for WSNs, using both reputation and risk to evaluate trustworthiness of a sensor node. Capossele et al. [30] propose a reputation-based channel aware routing protocol (R-CARP) for underwater acoustic sensor networks (UASNs). It was tailored to such communication constrained environment. The confident protocol proposed in [31] is a kind of ad hoc nodes reputation evaluation mechanism. Through the monitoring of the neighbor nodes, the reputation value is calculated and compared with the presetting threshold to judge the reliability of the nodes. Heinzelman et al. [13] used the watchdog mechanism to monitor the next hop node’s forwarding behavior. If the next node would not transmit the data packet, it is indicated that the node’s reliability is low. Moreover, the reputation values recommended by other nodes are taken into account for collaborative computing node’s reputation value.We presented a next hop selecting algorithm for static sensor nodes in [32], a “Physarum and ants” based hybrid routing algorithm for WSNs [33], and a reputation revision algorithm in cloud circumstance [34]. In this paper, we propose a reputation-based uneven cluster routing protocol (R-bUCRP) based on the prior works. The proposed protocol introduces the reputation mechanism firstly; next calculates the value of the node’s direct reputation and relative reputation according to the node’s historical interaction information and the similarity of the collected data; then evaluates comprehensively the reputation in consideration of the node’s income and expenses value when it joins into the cluster; and finally details the cluster heads election method according to the weight value of the cluster head candidate node’s residual energy and reputation value. The proposed method could efficiently decrease the dead speed of the nodes, balance the energy consumption of all nodes, and prolong the network lifetime.The rest of the paper is organized as follows. Section2 introduces network clustering model, energy model, and the reputation model. Section 3 details the proposed R-bUCRP. Section 4 evaluates our models and algorithms with extensive simulations. Finally, the conclusion is presented in Section 5.


## 2. System Models

### 2.1. CWSNS Model

In this paper, we construct a network model for CWSNS, as shown in Figure1. The CWSNS is divided into multiple clusters based on the cluster model of Wireless Sensor Network. We use the uneven clustering method in this paper. The closer to the base station a cluster is, the smaller its radius is. Nodes in the network are divided into cluster head nodes and cluster member nodes. The cluster head is elected according to the cluster head competitive rules, such as more residual energy and less energy consumption. The cluster head node manages cluster member nodes, fuses the information collected by cluster members, and sends it to the base station. The cluster member nodes include cognitive nodes and normal nodes. Cognitive nodes are special normal nodes where “cognitive” element is introduced. Cognitive nodes have the characteristics of wisdom, perceive the change of environment, and make the corresponding decision.Figure 1
Network model.Here, we present some assumptions for the network model used in the proposed method as follows.(i)
Each node has a unique ID.
(ii)
The energy of the node is heterogeneous, is limited, and cannot be supplied, and the node could obtain its own current energy.
(iii)
The base station cannot be moved, which has infinite energy and strong capacity of computing and storage.
(iv)
The data fusion technology is used to reduce the amount of data transmission.
(v)
The node is not provided with Global Positioning System (GPS) function module, so it has no position sensing capability.


### 2.2. Energy Consumption Model

In this paper, the energy consumption model of wireless communication is adopted from [22], where both the free space and multipath fading channels are used depending on the distance between the transmitter and receiver node. If the communication distance is less than a threshold value d
0, the free space model is used. Otherwise, the multipath fading model is considered. The receiving and sending circuit models of the wireless sensor nodes are shown in Figure 2.Figure 2
Circuit model of sending and receiving data.As shown in Figure2, the energy consumption for transmitting data is mainly composed of two parts, that is, transmitting circuit and power amplifier circuit. The energy consumed by node i to transmit k bit data packet to node j with the distance d is given in(1)
E
T
x
k
,
d
=
k
E
e
l
e
c
+
k
ε
f
s
d
2
,
d
<
d
0
k
E
e
l
e
c
+
k
ε
m
p
d
4
,
d
≥
d
0
.The energy consumption for receiving data comes mainly from receiving circuit, so the energy consumed by node to receivek bit data packet is shown in(2)
E
R
x
k
=
k
E
e
l
e
c
,where E
e
l
e
c is the radio frequency energy consumption coefficient and ε
f
s and ε
m
p are energy required by amplifier in free space and multipath, respectively. Through (1), d
0 is given as d
0
=
ε
f
s
/
ε
m
p.


### 2.3. Reputation Model

Reputation mechanism provides an effective way to judge the trust relationship between nodes. The introduction of reputation can help determine the degree of cooperation between the nodes, identify the selfish nodes efficiently, and punish or incent the selfish nodes in some way. The so-called selfish nodes are the nodes which do not forward data or forward selectively data in order to maintain their own energy. Assuming that the nodei is the neighbor node of node j, if i wants to know whether j is reliable or not, it could determine by computing the reputation value of j.The traditional node reputation calculation mainly considers two aspects: direct reputation value and indirect reputation value. The reputation evaluation process is shown in Figure3. Direct reputation means that the reputation value of j is evaluated based on the direct historical interaction between nodes i and j, while indirect reputation value of j is formed from the recommended value according to the other nodes’ reputation to j.Figure 3
Reputation evaluation process.


## 2.1. CWSNS Model

In this paper, we construct a network model for CWSNS, as shown in Figure1. The CWSNS is divided into multiple clusters based on the cluster model of Wireless Sensor Network. We use the uneven clustering method in this paper. The closer to the base station a cluster is, the smaller its radius is. Nodes in the network are divided into cluster head nodes and cluster member nodes. The cluster head is elected according to the cluster head competitive rules, such as more residual energy and less energy consumption. The cluster head node manages cluster member nodes, fuses the information collected by cluster members, and sends it to the base station. The cluster member nodes include cognitive nodes and normal nodes. Cognitive nodes are special normal nodes where “cognitive” element is introduced. Cognitive nodes have the characteristics of wisdom, perceive the change of environment, and make the corresponding decision.Figure 1
Network model.Here, we present some assumptions for the network model used in the proposed method as follows.(i)
Each node has a unique ID.
(ii)
The energy of the node is heterogeneous, is limited, and cannot be supplied, and the node could obtain its own current energy.
(iii)
The base station cannot be moved, which has infinite energy and strong capacity of computing and storage.
(iv)
The data fusion technology is used to reduce the amount of data transmission.
(v)
The node is not provided with Global Positioning System (GPS) function module, so it has no position sensing capability.


## 2.2. Energy Consumption Model

In this paper, the energy consumption model of wireless communication is adopted from [22], where both the free space and multipath fading channels are used depending on the distance between the transmitter and receiver node. If the communication distance is less than a threshold value d
0, the free space model is used. Otherwise, the multipath fading model is considered. The receiving and sending circuit models of the wireless sensor nodes are shown in Figure 2.Figure 2
Circuit model of sending and receiving data.As shown in Figure2, the energy consumption for transmitting data is mainly composed of two parts, that is, transmitting circuit and power amplifier circuit. The energy consumed by node i to transmit k bit data packet to node j with the distance d is given in(1)
E
T
x
k
,
d
=
k
E
e
l
e
c
+
k
ε
f
s
d
2
,
d
<
d
0
k
E
e
l
e
c
+
k
ε
m
p
d
4
,
d
≥
d
0
.The energy consumption for receiving data comes mainly from receiving circuit, so the energy consumed by node to receivek bit data packet is shown in(2)
E
R
x
k
=
k
E
e
l
e
c
,where E
e
l
e
c is the radio frequency energy consumption coefficient and ε
f
s and ε
m
p are energy required by amplifier in free space and multipath, respectively. Through (1), d
0 is given as d
0
=
ε
f
s
/
ε
m
p.


## 2.3. Reputation Model

Reputation mechanism provides an effective way to judge the trust relationship between nodes. The introduction of reputation can help determine the degree of cooperation between the nodes, identify the selfish nodes efficiently, and punish or incent the selfish nodes in some way. The so-called selfish nodes are the nodes which do not forward data or forward selectively data in order to maintain their own energy. Assuming that the nodei is the neighbor node of node j, if i wants to know whether j is reliable or not, it could determine by computing the reputation value of j.The traditional node reputation calculation mainly considers two aspects: direct reputation value and indirect reputation value. The reputation evaluation process is shown in Figure3. Direct reputation means that the reputation value of j is evaluated based on the direct historical interaction between nodes i and j, while indirect reputation value of j is formed from the recommended value according to the other nodes’ reputation to j.Figure 3
Reputation evaluation process.


## 3. R-bUCRP Description

In the network establishment phase, the base station needs to broadcast a signal with a given transmit power. Each sensor node calculates the approximate distance to the base station based on the intensity of the received signal. The distance is not only helpful for the nodes to select the appropriate transmit power to save energy consumption, but also as one of the necessary pieces of information to construct clusters.The basic process of the R-bUCRP in each round is illuminated as follows. Firstly, each node in the cluster selects a random number between 0 and 1. If the number is below a certain threshold, the node becomes the cluster head candidate. Then, the final cluster heads are determined by using the competitive algorithm, and new cluster heads broadcast the messages to the surrounding nodes. Each node determines which cluster to join in based on the competitive function and replies to the messages to the cluster head.In the data transmission phase, all nodes in the cluster send data to the cluster head in accordance with TDMA (Time Division Multiple Access) slots. Cluster head fuses the data and then transmits to the base station. After a period of continuous operation, the network reenters the start-ups phase and begins the next round of the cluster heads selection and reestablishes the clusters.


### 3.1. Reputation Evaluation

Due to the limited energy, some nodes are selfish in order to save their own energy. So it is important to consider the reputation paradigm for network nodes. The lower the reputation value is, the more selfish the nodes are. Therefore, the node’s reputation value is one of the factors that need to be considered in the selection of cluster head.Node reputation value could be computed by similarity of collected data and the historical interaction experience between nodes. Moreover, when the nodes compete to become the cluster head, they can charge a certain reputation value from other nodes as the compensation of energy consumption.


#### 3.1.1. Calculation of Direct Reputation Value

Direct reputation is obtained by listening to the direct interaction of two nodes. It uses the historical interaction experience between nodes. The more successful interactions of nodei to node j are, the higher reliability of node i to node j is. In a period of time, if the number of interactions from node i to node j is N and the number of successful interactions is k, the reputation by direct interaction of node i to node j could be expressed as(3)
φ
i
j
=
0.5
+
k
-
N
-
k
2
N
0
,
N
<
N
0
k
N
,
N
≥
N
0
, where N
0 is the threshold of interaction frequency.Generally, interaction time is very important to the reliability of the evaluation and reputation value. Therefore, the interaction time of nodei and node j is divided into R segments. For the collected information in paragraph r of node i, the time attenuation factor ρ
r and the importance factor V
r are introduced to calculate the direct reputation value. Direct reputation value of node i could be expressed as(4)
D
R
V
i
=
∑
j
=
1
M
∑
r
=
1
R
φ
i
j
·
ρ
r
·
V
r
R
, where M is the number of neighbor nodes of node i.


#### 3.1.2. Calculation of Relative Reputation Value

In CWSNS, since the distribution of nodes is relatively dense, the observational data by the neighboring nodes often has a lot of similarities. Comparing the data of the neighbor nodes in the same period, we can see that the higher degree of similarity is, the more reliable it is.Assume that the feature vector of environmental data collected by nodei in a period of time is expressed as D
i
=
t
,
e
,
a
,
v, where t represents the type of object (the value range is set as T), e represents the event type (the value range is set as E), a represents the attribute of the observation area (the value range is set as A), and v represents the value of perceptual information (the value range is set as V).The relative reputation between nodes is calculated by the similarity of data feature vectors. There are two adjacent nodesi and j. Their data feature vectors are D
F
i
=
t
i
,
e
i
,
a
i
,
v
i and D
F
j
=
t
j
,
e
j
,
a
j
,
v
j. The similarity of data feature vectors of node i and node j in a period of time is(5)
S
i
m
D
F
i
,
D
F
j
=
cos
⁡
D
F
i
→
,
D
F
j
→
=
D
F
i
→
·
D
F
j
→
D
F
i
→
D
F
j
→
.The relative reputation value ofi in this period of time is(6)
R
R
V
i
=
∑
j
=
1
M
λ
1
+
S
i
m
D
F
i
,
D
F
j
M
,where M is the number of nodes adjacent to node i and λ
>
0 is similar parameters to calculate relative reputation value.


#### 3.1.3. Calculation of Reputation Value

The reputation value of nodei is composed of direct reputation value (DRV), relative reputation value (RRV), and income and expenses value (IEV). It is expressed as(7)
R
V
i
=
ω
1
D
R
V
i
+
ω
2
R
R
V
i
+
ω
3
I
E
V
i
,where ω
1
+
ω
2
+
ω
3
=
1. If the node i is a cluster head node, when member nodes want to join into the cluster, they need to pay some virtual reputation value to the cluster head node, where I
E
V
i
≥
0; on the contrary, if node i is a normal node and requests to join into the cluster, I
E
V
i
<
0.


### 3.2. Establishment of Cluster

#### 3.2.1. Competitive Radius of Cluster Head

The energy consumption of cluster head is different in even clustering multihop routing. The cluster head nodes near the base station take on more data forwarding tasks and consume more energy. In order to balance the energy consumption of cluster head nodes and prolong the network life, R-bUCRP uses uneven clustering in the stage of cluster establishment. The closer to the base station a cluster is, the smaller its size is. The communication radius of the cluster head node is related to the distance to the base station. Competitive radius of cluster head node is defined as(8)
R
i
=
1
-
μ
d
m
a
x
-
d
s
i
,
B
S
d
m
a
x
-
d
m
i
n
R
m
a
x
,where R
i represents the competitive radius of cluster head node i, R
m
a
x represents the maximum competitive radius of system setting, and μ is a constant whose value is [
0,1
].


#### 3.2.2. Competitive Function of Cluster Head

In the cluster head selection process, this paper constructs a competitive function to avoid the excessive energy consumption or the selfish nodes elected as the cluster head. The competitive function is shown in(9)
W
i
=
α
E
r
e
s
E
r
e
s
¯
+
β
R
V
R
V
¯
,where W
i is the comprehensive weight value of energy and reputation and the larger the value is, the more competitive to be cluster head the node is, E
r
e
s represents the current residual energy of node i, E
r
e
s
¯ represents the average residual energy of nodes in the network area, R
V represents the current reputation value of node i, and R
V
¯ represents the average reputation value of nodes in the network area.


#### 3.2.3. Competitive Function of Joining into the Cluster

After the cluster heads are determined, the cluster head nodes broadcast theC
l
u
s
t
e
r
_
M
s
g packet and then wait for other nodes to join in. In this paper, when a node selects a cluster to join in, we consider not only the residual energy of cluster head, but also the distance to the cluster head and distance between cluster head and base station. The competitive function of node i is given as(10)
F
i
,
C
H
i
=
E
r
e
s
d
i
,
C
H
i
2
+
d
C
H
i
,
B
S
2
,where C
H
i is the cluster head node, E
r
e
s is the residual energy of the cluster head node, d
i
,
C
H
i is the distance between the nodes i and the cluster head node C
H
i, and d
C
H
i
,
B
S is the distance between the cluster head C
H
i and the base station.The cluster establishment process is to achieve the purpose of load balancing. When a node wants to join into a cluster, it considers the energy residual of cluster head and transmission distance. From (10), it can be seen that there are three factors to determine the probability of joining into the cluster, that is, energy residual of cluster head, the distance between the cluster head and the normal node, and distance between the cluster head and the base station. In order to avoid the extreme situations of difficult choice (a node encounters a long distance with large energy or a short distance with low energy), especially in the later period of the network lifetime, the algorithm could give priority to the cluster head with the large signal strength when the energy of cluster head candidate is less than a certain threshold.


#### 3.2.4. Establishment Process of Cluster

Network node cluster establishment process includes the cluster head election process and the process of normal nodes joining into the cluster. The corresponding pseudocode is described as in Algorithm1.Algorithm 1:Cluster establishment.
For every node in the network
(1)t
←
R
A
N
D
(
0,1
)
(2)if  t
<
T
(3)b
e
C
l
u
s
e
r
H
e
a
d
C
a
n
d
i
d
a
t
e
←
T
R
U
E
(4)end if
(5)if  b
e
C
l
u
s
e
r
H
e
a
d
C
a
n
d
i
d
a
t
e
=
T
R
U
E
(6)   computeR
i and W
i following (8) and (9)
(7)C
o
m
p
e
t
i
t
i
v
e
H
e
a
d
M
s
g
(
I
D,R
i
,
W
i
)
(8)else
(9)   sleep
(10)end if
For every candidate nodei
(11)  receiving aC
o
m
p
e
t
i
t
i
v
e
H
e
a
d
M
s
g from candicate j
(12)if  d
(
i
,
j
)
<
R
i OR d
(
i
,
j
)
<
R
j
(13)  addj to i neighbor set N
S
i
(14)end if
For every candicate nodej
(15)if  W
i
<
W
(
N
S
i
)
(16)j give up the competition and become a normal node
(17)end if
For every normal nodei
(18)if  i is in one cluster_coverage
(19)i apply to join into the cluster
(19)i pay reputation value to the cluster head
(20)else
(21)i select cluster following (10)
(22)i pay reputation value to the cluster head
(23)end if


## 3.1. Reputation Evaluation

Due to the limited energy, some nodes are selfish in order to save their own energy. So it is important to consider the reputation paradigm for network nodes. The lower the reputation value is, the more selfish the nodes are. Therefore, the node’s reputation value is one of the factors that need to be considered in the selection of cluster head.Node reputation value could be computed by similarity of collected data and the historical interaction experience between nodes. Moreover, when the nodes compete to become the cluster head, they can charge a certain reputation value from other nodes as the compensation of energy consumption.


### 3.1.1. Calculation of Direct Reputation Value

Direct reputation is obtained by listening to the direct interaction of two nodes. It uses the historical interaction experience between nodes. The more successful interactions of nodei to node j are, the higher reliability of node i to node j is. In a period of time, if the number of interactions from node i to node j is N and the number of successful interactions is k, the reputation by direct interaction of node i to node j could be expressed as(3)
φ
i
j
=
0.5
+
k
-
N
-
k
2
N
0
,
N
<
N
0
k
N
,
N
≥
N
0
, where N
0 is the threshold of interaction frequency.Generally, interaction time is very important to the reliability of the evaluation and reputation value. Therefore, the interaction time of nodei and node j is divided into R segments. For the collected information in paragraph r of node i, the time attenuation factor ρ
r and the importance factor V
r are introduced to calculate the direct reputation value. Direct reputation value of node i could be expressed as(4)
D
R
V
i
=
∑
j
=
1
M
∑
r
=
1
R
φ
i
j
·
ρ
r
·
V
r
R
, where M is the number of neighbor nodes of node i.


### 3.1.2. Calculation of Relative Reputation Value

In CWSNS, since the distribution of nodes is relatively dense, the observational data by the neighboring nodes often has a lot of similarities. Comparing the data of the neighbor nodes in the same period, we can see that the higher degree of similarity is, the more reliable it is.Assume that the feature vector of environmental data collected by nodei in a period of time is expressed as D
i
=
t
,
e
,
a
,
v, where t represents the type of object (the value range is set as T), e represents the event type (the value range is set as E), a represents the attribute of the observation area (the value range is set as A), and v represents the value of perceptual information (the value range is set as V).The relative reputation between nodes is calculated by the similarity of data feature vectors. There are two adjacent nodesi and j. Their data feature vectors are D
F
i
=
t
i
,
e
i
,
a
i
,
v
i and D
F
j
=
t
j
,
e
j
,
a
j
,
v
j. The similarity of data feature vectors of node i and node j in a period of time is(5)
S
i
m
D
F
i
,
D
F
j
=
cos
⁡
D
F
i
→
,
D
F
j
→
=
D
F
i
→
·
D
F
j
→
D
F
i
→
D
F
j
→
.The relative reputation value ofi in this period of time is(6)
R
R
V
i
=
∑
j
=
1
M
λ
1
+
S
i
m
D
F
i
,
D
F
j
M
,where M is the number of nodes adjacent to node i and λ
>
0 is similar parameters to calculate relative reputation value.


### 3.1.3. Calculation of Reputation Value

The reputation value of nodei is composed of direct reputation value (DRV), relative reputation value (RRV), and income and expenses value (IEV). It is expressed as(7)
R
V
i
=
ω
1
D
R
V
i
+
ω
2
R
R
V
i
+
ω
3
I
E
V
i
,where ω
1
+
ω
2
+
ω
3
=
1. If the node i is a cluster head node, when member nodes want to join into the cluster, they need to pay some virtual reputation value to the cluster head node, where I
E
V
i
≥
0; on the contrary, if node i is a normal node and requests to join into the cluster, I
E
V
i
<
0.


## 3.1.1. Calculation of Direct Reputation Value

Direct reputation is obtained by listening to the direct interaction of two nodes. It uses the historical interaction experience between nodes. The more successful interactions of nodei to node j are, the higher reliability of node i to node j is. In a period of time, if the number of interactions from node i to node j is N and the number of successful interactions is k, the reputation by direct interaction of node i to node j could be expressed as(3)
φ
i
j
=
0.5
+
k
-
N
-
k
2
N
0
,
N
<
N
0
k
N
,
N
≥
N
0
, where N
0 is the threshold of interaction frequency.Generally, interaction time is very important to the reliability of the evaluation and reputation value. Therefore, the interaction time of nodei and node j is divided into R segments. For the collected information in paragraph r of node i, the time attenuation factor ρ
r and the importance factor V
r are introduced to calculate the direct reputation value. Direct reputation value of node i could be expressed as(4)
D
R
V
i
=
∑
j
=
1
M
∑
r
=
1
R
φ
i
j
·
ρ
r
·
V
r
R
, where M is the number of neighbor nodes of node i.


## 3.1.2. Calculation of Relative Reputation Value

In CWSNS, since the distribution of nodes is relatively dense, the observational data by the neighboring nodes often has a lot of similarities. Comparing the data of the neighbor nodes in the same period, we can see that the higher degree of similarity is, the more reliable it is.Assume that the feature vector of environmental data collected by nodei in a period of time is expressed as D
i
=
t
,
e
,
a
,
v, where t represents the type of object (the value range is set as T), e represents the event type (the value range is set as E), a represents the attribute of the observation area (the value range is set as A), and v represents the value of perceptual information (the value range is set as V).The relative reputation between nodes is calculated by the similarity of data feature vectors. There are two adjacent nodesi and j. Their data feature vectors are D
F
i
=
t
i
,
e
i
,
a
i
,
v
i and D
F
j
=
t
j
,
e
j
,
a
j
,
v
j. The similarity of data feature vectors of node i and node j in a period of time is(5)
S
i
m
D
F
i
,
D
F
j
=
cos
⁡
D
F
i
→
,
D
F
j
→
=
D
F
i
→
·
D
F
j
→
D
F
i
→
D
F
j
→
.The relative reputation value ofi in this period of time is(6)
R
R
V
i
=
∑
j
=
1
M
λ
1
+
S
i
m
D
F
i
,
D
F
j
M
,where M is the number of nodes adjacent to node i and λ
>
0 is similar parameters to calculate relative reputation value.


## 3.1.3. Calculation of Reputation Value

The reputation value of nodei is composed of direct reputation value (DRV), relative reputation value (RRV), and income and expenses value (IEV). It is expressed as(7)
R
V
i
=
ω
1
D
R
V
i
+
ω
2
R
R
V
i
+
ω
3
I
E
V
i
,where ω
1
+
ω
2
+
ω
3
=
1. If the node i is a cluster head node, when member nodes want to join into the cluster, they need to pay some virtual reputation value to the cluster head node, where I
E
V
i
≥
0; on the contrary, if node i is a normal node and requests to join into the cluster, I
E
V
i
<
0.


## 3.2. Establishment of Cluster

### 3.2.1. Competitive Radius of Cluster Head

The energy consumption of cluster head is different in even clustering multihop routing. The cluster head nodes near the base station take on more data forwarding tasks and consume more energy. In order to balance the energy consumption of cluster head nodes and prolong the network life, R-bUCRP uses uneven clustering in the stage of cluster establishment. The closer to the base station a cluster is, the smaller its size is. The communication radius of the cluster head node is related to the distance to the base station. Competitive radius of cluster head node is defined as(8)
R
i
=
1
-
μ
d
m
a
x
-
d
s
i
,
B
S
d
m
a
x
-
d
m
i
n
R
m
a
x
,where R
i represents the competitive radius of cluster head node i, R
m
a
x represents the maximum competitive radius of system setting, and μ is a constant whose value is [
0,1
].


### 3.2.2. Competitive Function of Cluster Head

In the cluster head selection process, this paper constructs a competitive function to avoid the excessive energy consumption or the selfish nodes elected as the cluster head. The competitive function is shown in(9)
W
i
=
α
E
r
e
s
E
r
e
s
¯
+
β
R
V
R
V
¯
,where W
i is the comprehensive weight value of energy and reputation and the larger the value is, the more competitive to be cluster head the node is, E
r
e
s represents the current residual energy of node i, E
r
e
s
¯ represents the average residual energy of nodes in the network area, R
V represents the current reputation value of node i, and R
V
¯ represents the average reputation value of nodes in the network area.


### 3.2.3. Competitive Function of Joining into the Cluster

After the cluster heads are determined, the cluster head nodes broadcast theC
l
u
s
t
e
r
_
M
s
g packet and then wait for other nodes to join in. In this paper, when a node selects a cluster to join in, we consider not only the residual energy of cluster head, but also the distance to the cluster head and distance between cluster head and base station. The competitive function of node i is given as(10)
F
i
,
C
H
i
=
E
r
e
s
d
i
,
C
H
i
2
+
d
C
H
i
,
B
S
2
,where C
H
i is the cluster head node, E
r
e
s is the residual energy of the cluster head node, d
i
,
C
H
i is the distance between the nodes i and the cluster head node C
H
i, and d
C
H
i
,
B
S is the distance between the cluster head C
H
i and the base station.The cluster establishment process is to achieve the purpose of load balancing. When a node wants to join into a cluster, it considers the energy residual of cluster head and transmission distance. From (10), it can be seen that there are three factors to determine the probability of joining into the cluster, that is, energy residual of cluster head, the distance between the cluster head and the normal node, and distance between the cluster head and the base station. In order to avoid the extreme situations of difficult choice (a node encounters a long distance with large energy or a short distance with low energy), especially in the later period of the network lifetime, the algorithm could give priority to the cluster head with the large signal strength when the energy of cluster head candidate is less than a certain threshold.


### 3.2.4. Establishment Process of Cluster

Network node cluster establishment process includes the cluster head election process and the process of normal nodes joining into the cluster. The corresponding pseudocode is described as in Algorithm1.Algorithm 1:Cluster establishment.
For every node in the network
(1)t
←
R
A
N
D
(
0,1
)
(2)if  t
<
T
(3)b
e
C
l
u
s
e
r
H
e
a
d
C
a
n
d
i
d
a
t
e
←
T
R
U
E
(4)end if
(5)if  b
e
C
l
u
s
e
r
H
e
a
d
C
a
n
d
i
d
a
t
e
=
T
R
U
E
(6)   computeR
i and W
i following (8) and (9)
(7)C
o
m
p
e
t
i
t
i
v
e
H
e
a
d
M
s
g
(
I
D,R
i
,
W
i
)
(8)else
(9)   sleep
(10)end if
For every candidate nodei
(11)  receiving aC
o
m
p
e
t
i
t
i
v
e
H
e
a
d
M
s
g from candicate j
(12)if  d
(
i
,
j
)
<
R
i OR d
(
i
,
j
)
<
R
j
(13)  addj to i neighbor set N
S
i
(14)end if
For every candicate nodej
(15)if  W
i
<
W
(
N
S
i
)
(16)j give up the competition and become a normal node
(17)end if
For every normal nodei
(18)if  i is in one cluster_coverage
(19)i apply to join into the cluster
(19)i pay reputation value to the cluster head
(20)else
(21)i select cluster following (10)
(22)i pay reputation value to the cluster head
(23)end if


## 3.2.1. Competitive Radius of Cluster Head

The energy consumption of cluster head is different in even clustering multihop routing. The cluster head nodes near the base station take on more data forwarding tasks and consume more energy. In order to balance the energy consumption of cluster head nodes and prolong the network life, R-bUCRP uses uneven clustering in the stage of cluster establishment. The closer to the base station a cluster is, the smaller its size is. The communication radius of the cluster head node is related to the distance to the base station. Competitive radius of cluster head node is defined as(8)
R
i
=
1
-
μ
d
m
a
x
-
d
s
i
,
B
S
d
m
a
x
-
d
m
i
n
R
m
a
x
,where R
i represents the competitive radius of cluster head node i, R
m
a
x represents the maximum competitive radius of system setting, and μ is a constant whose value is [
0,1
].


## 3.2.2. Competitive Function of Cluster Head

In the cluster head selection process, this paper constructs a competitive function to avoid the excessive energy consumption or the selfish nodes elected as the cluster head. The competitive function is shown in(9)
W
i
=
α
E
r
e
s
E
r
e
s
¯
+
β
R
V
R
V
¯
,where W
i is the comprehensive weight value of energy and reputation and the larger the value is, the more competitive to be cluster head the node is, E
r
e
s represents the current residual energy of node i, E
r
e
s
¯ represents the average residual energy of nodes in the network area, R
V represents the current reputation value of node i, and R
V
¯ represents the average reputation value of nodes in the network area.


## 3.2.3. Competitive Function of Joining into the Cluster

After the cluster heads are determined, the cluster head nodes broadcast theC
l
u
s
t
e
r
_
M
s
g packet and then wait for other nodes to join in. In this paper, when a node selects a cluster to join in, we consider not only the residual energy of cluster head, but also the distance to the cluster head and distance between cluster head and base station. The competitive function of node i is given as(10)
F
i
,
C
H
i
=
E
r
e
s
d
i
,
C
H
i
2
+
d
C
H
i
,
B
S
2
,where C
H
i is the cluster head node, E
r
e
s is the residual energy of the cluster head node, d
i
,
C
H
i is the distance between the nodes i and the cluster head node C
H
i, and d
C
H
i
,
B
S is the distance between the cluster head C
H
i and the base station.The cluster establishment process is to achieve the purpose of load balancing. When a node wants to join into a cluster, it considers the energy residual of cluster head and transmission distance. From (10), it can be seen that there are three factors to determine the probability of joining into the cluster, that is, energy residual of cluster head, the distance between the cluster head and the normal node, and distance between the cluster head and the base station. In order to avoid the extreme situations of difficult choice (a node encounters a long distance with large energy or a short distance with low energy), especially in the later period of the network lifetime, the algorithm could give priority to the cluster head with the large signal strength when the energy of cluster head candidate is less than a certain threshold.


## 3.2.4. Establishment Process of Cluster

Network node cluster establishment process includes the cluster head election process and the process of normal nodes joining into the cluster. The corresponding pseudocode is described as in Algorithm1.Algorithm 1:Cluster establishment.
For every node in the network
(1)t
←
R
A
N
D
(
0,1
)
(2)if  t
<
T
(3)b
e
C
l
u
s
e
r
H
e
a
d
C
a
n
d
i
d
a
t
e
←
T
R
U
E
(4)end if
(5)if  b
e
C
l
u
s
e
r
H
e
a
d
C
a
n
d
i
d
a
t
e
=
T
R
U
E
(6)   computeR
i and W
i following (8) and (9)
(7)C
o
m
p
e
t
i
t
i
v
e
H
e
a
d
M
s
g
(
I
D,R
i
,
W
i
)
(8)else
(9)   sleep
(10)end if
For every candidate nodei
(11)  receiving aC
o
m
p
e
t
i
t
i
v
e
H
e
a
d
M
s
g from candicate j
(12)if  d
(
i
,
j
)
<
R
i OR d
(
i
,
j
)
<
R
j
(13)  addj to i neighbor set N
S
i
(14)end if
For every candicate nodej
(15)if  W
i
<
W
(
N
S
i
)
(16)j give up the competition and become a normal node
(17)end if
For every normal nodei
(18)if  i is in one cluster_coverage
(19)i apply to join into the cluster
(19)i pay reputation value to the cluster head
(20)else
(21)i select cluster following (10)
(22)i pay reputation value to the cluster head
(23)end if


## 4. Simulation and Result Analysis

### 4.1. Simulation Environment

In order to evaluate the performance of the proposed algorithms, we use MATLAB to simulate LEACH, EEUC, MADSEC, and our R-bUCRP under the same conditions and compare their performances. Simulation scene is set as follows: 1500 nodes are distributed in the network area of 400 m× 400 m, the coordinates of the base station are (200, 500) m, and each node moves towards a random direction at a speed uniformly distributed [0, 20 m/s]. We use energy model of literature [22] in the simulation. Detailed parameter settings are shown in Table 1.Table 1
Network parameters and values.
Parameter
Value
Network coverage
(0,0)∼(400, 400) m
Base station location
(200, 500)  m
Node number
1500
Initial energy
0.5 J
Data packet size
4000 bits
Speed distribution
[0, 20] m
E
e
l
e
c
50 nJ/bit
ε
f
s
10 pJ/(bit⋅m2)
ε
m
p
0.0013 pJ/(bit⋅m2)
E
f
u
s
i
o
n
5 nJ/bit


### 4.2. Result Analysis

Since R-bUCRP introduces the concept of the reputation into the clustering process of CWSNS, reducing energy consumption of normal nodes when they communicate with the selfish nodes, at the same time, it balances the energy consumption of nodes in the network by using uneven clustering method. Therefore, it can be seen from Figure4 that the first node death time and network death time of R-bUCRP are significantly later than those of the LEACH protocol, EEUC protocol, and MADSEC protocol.Figure 4
The relationship between the alive node number and round number.Figure5 compares the changes of network residual energy by using four protocols over time. Smaller slope shows a slower rate of energy consumption and indicates a longer survival time. As can be seen from Figure 5, the energy consumption rate by using R-bUCRP is significantly smaller than the other three kinds of protocols, and the network has a longer survival time, with the better network quality.Figure 5
The relationship between network residual energy and round number.Figure6 shows the changes of node average energy by using four kinds of protocols over time. The node average energy by using R-bUCRP is higher than the other three kinds of protocols, which means R-bUCRP has a better performance in energy balance.Figure 6
The relationship between average residual energy and round number.Figure7 compares the changes of node average energy by using four kinds of protocols over the number of nodes in round 1000. With the increase of the node number in the network area, the node average energy is decreased. As shown from Figure 7, the speed of energy consumption by using R-bUCRP is slower than the other three kinds of protocols, which means R-bUCRP has a better performance in scalability.Figure 7
The relationship between average residual energy and node number.Figures8, 9, 10, and 11 illustrate the stability of the algorithm. A stable clustering algorithm should also generate more consistent number of clusters in order to balance the energy consumption of the network. Randomly select 100 rounds from the experimental processes of LEACH protocol, EEUC protocol, MADSEC protocol, and R-bUCRP, and count the distribution of cluster heads’ number and the results are shown in Figures 8–11. Among these, LEACH protocol only uses the random number and threshold mechanism in the cluster head election; therefore, the range of cluster head number is large by using LEACH protocol. MADSEC protocol uses the K-means algorithm to divide the network area. EEUC protocol and R-bUCRP use the competitive function of cluster head candidates, and the number of cluster heads is controlled effectively within a certain range. In addition, R-bUCRP generates a more stable number of the cluster heads, which has better reliability.Figure 8
Cluster head number distribution of LEACH.Figure 9
Cluster head number distribution of EEUC.Figure 10
Cluster head number distribution of R-bUCRP.Figure 11
Cluster head number distribution of MADSEC.


## 4.1. Simulation Environment

In order to evaluate the performance of the proposed algorithms, we use MATLAB to simulate LEACH, EEUC, MADSEC, and our R-bUCRP under the same conditions and compare their performances. Simulation scene is set as follows: 1500 nodes are distributed in the network area of 400 m× 400 m, the coordinates of the base station are (200, 500) m, and each node moves towards a random direction at a speed uniformly distributed [0, 20 m/s]. We use energy model of literature [22] in the simulation. Detailed parameter settings are shown in Table 1.Table 1
Network parameters and values.
Parameter
Value
Network coverage
(0,0)∼(400, 400) m
Base station location
(200, 500)  m
Node number
1500
Initial energy
0.5 J
Data packet size
4000 bits
Speed distribution
[0, 20] m
E
e
l
e
c
50 nJ/bit
ε
f
s
10 pJ/(bit⋅m2)
ε
m
p
0.0013 pJ/(bit⋅m2)
E
f
u
s
i
o
n
5 nJ/bit


## 4.2. Result Analysis

Since R-bUCRP introduces the concept of the reputation into the clustering process of CWSNS, reducing energy consumption of normal nodes when they communicate with the selfish nodes, at the same time, it balances the energy consumption of nodes in the network by using uneven clustering method. Therefore, it can be seen from Figure4 that the first node death time and network death time of R-bUCRP are significantly later than those of the LEACH protocol, EEUC protocol, and MADSEC protocol.Figure 4
The relationship between the alive node number and round number.Figure5 compares the changes of network residual energy by using four protocols over time. Smaller slope shows a slower rate of energy consumption and indicates a longer survival time. As can be seen from Figure 5, the energy consumption rate by using R-bUCRP is significantly smaller than the other three kinds of protocols, and the network has a longer survival time, with the better network quality.Figure 5
The relationship between network residual energy and round number.Figure6 shows the changes of node average energy by using four kinds of protocols over time. The node average energy by using R-bUCRP is higher than the other three kinds of protocols, which means R-bUCRP has a better performance in energy balance.Figure 6
The relationship between average residual energy and round number.Figure7 compares the changes of node average energy by using four kinds of protocols over the number of nodes in round 1000. With the increase of the node number in the network area, the node average energy is decreased. As shown from Figure 7, the speed of energy consumption by using R-bUCRP is slower than the other three kinds of protocols, which means R-bUCRP has a better performance in scalability.Figure 7
The relationship between average residual energy and node number.Figures8, 9, 10, and 11 illustrate the stability of the algorithm. A stable clustering algorithm should also generate more consistent number of clusters in order to balance the energy consumption of the network. Randomly select 100 rounds from the experimental processes of LEACH protocol, EEUC protocol, MADSEC protocol, and R-bUCRP, and count the distribution of cluster heads’ number and the results are shown in Figures 8–11. Among these, LEACH protocol only uses the random number and threshold mechanism in the cluster head election; therefore, the range of cluster head number is large by using LEACH protocol. MADSEC protocol uses the K-means algorithm to divide the network area. EEUC protocol and R-bUCRP use the competitive function of cluster head candidates, and the number of cluster heads is controlled effectively within a certain range. In addition, R-bUCRP generates a more stable number of the cluster heads, which has better reliability.Figure 8
Cluster head number distribution of LEACH.Figure 9
Cluster head number distribution of EEUC.Figure 10
Cluster head number distribution of R-bUCRP.Figure 11
Cluster head number distribution of MADSEC.


## 5. Conclusion

A reputation-based uneven cluster routing protocol R-bUCRP is proposed in this paper. The protocol adopts an uneven clustering method and introduces the reputation mechanism to reduce the communicational energy consumption between normal nodes and selfish nodes and increase the reliability of the network effectively. The algorithm optimizes the process of cluster head selection by competing for the cluster head among cluster head candidate nodes according to the residual energy and reputation value. Simulation results show that R-bUCRP can balance the network energy consumption, prolong the network lifetime, and increase the network reliability effectively.



---

*Source: 5986265-2016-09-20.xml*