Sage Journals: Discover world-class research

Abstract

Internet of things is characterized by limited energy and distributed topology. In this scenario, a secure and energy-saving routing algorithm plays a significant role in ensuring the performance of Internet of things. Due to different standards and communication stacks, traditional security mechanisms heavily rely on trust management to function well. In this article, we propose an energy-aware trustworthy multi-hop routing model for Internet of things. To balance energy consumption and trust, the whole routing from source to destination should be considered for trust appraisal, rather than the destination peers merely. Meanwhile, the energy consumption of wise interaction should be regarded as one criterion. We also introduce a trustworthy spanning tree algorithm that is able to balance energy consumption and reduce trust cost. The experimental results suggest that the proposed strategy can lower energy consumption significantly under the premise of trustworthy transmission.

Keywords

Internet of things trust management energy-aware multi-hop routing

Introduction

Nowadays, Internet of things (IoT) is evolving toward an attractive next-generation networking paradigm and service infrastructure.¹ It allows a great amount of smart objects (sensors, smartphones, actuators, and radio frequency identification) in the physical world to be connected to execute complex and heavy lifting tasks, like the application in surveillance, environment and habitat monitoring, healthcare, and disaster management.² In view of the IoT scenarios, the nodes are normally resource constrained, especially with limited energy, so it is necessary to design an effective topology management approach to optimize their communications and extend their lifespan.^3,4 Rault et al.⁵ propose a division method to tackle energy consumption problems such as radio optimization, data reduction, sleep/wakeup schemes, battery repletion, and energy-efficient routing. This article focuses on researching energy-efficient routing mechanisms, which can be categorized as cluster architectures, energy as a routing metric, multipath routing, relay node placement, and sink mobility. Relay node placement considers a special situation occurred during the interaction process in IoT, where energy holes are created due to the premature depletion of nodes in a given region. Sink mobility uses a mobile base station (BS) which moves around the network to collect node information to balance the load between them. Different to these two methods, which need extra and special device support, cluster architectures, energy consumption as a routing metric, and multipath routing are the main focuses of our work. Some works like Shalli et al.,⁶ Fredj et al.,⁷ and Machado et al.⁸ adopt clustering³ topology to group IoT nodes, and their results suggest that multi-layer networks perform better than the single-layer ones. Anfeng⁹ selects next hop based on the shortest route and remaining energy, which performs better even in networks with obstacles. Warrier and Kumar¹⁰ and Radi et al.¹¹ adopt the multipath routing protocol to balance energy consumption by alternating forwarding nodes as single-path routing protocols, which can rapidly drain the energy of nodes on the selected path. However, trust management plays a more important role in IoT, especially in medical care and military. Reliable data fusion and mining and qualified services with context-aware intelligence are necessary, and user privacy and information security must be ensured.¹² Therefore, network lifetime and security are two of the most important considerations in designing the novel IoT.

In terms of cluster architectures, many works, that is, classical clustering processes LEACH,¹³ use the strategy of changing cluster head (CH) periodically in order to balance load of the entire network to prolong network life cycle. Since the CH nodes consume more energy than the normal nodes, selecting them should mainly rely on their current energy consumption and the distances to other non-CH nodes. To use energy consumption as a routing metric, Anfeng⁹ introduces two new energy-aware cost functions, namely, sine cost function–based route (ESCFR), which penalized any small change in the remaining nodal energy to a large change in the cost function value, and double cost function–based route (DCFR), which considered the energy consumption rate of nodes in addition to their remaining energy. As for multipath routing, Moghadam et al.,¹⁴ based on the routing protocol for low-power and lossy networks (LLNs), proposed a proactive multipath routing algorithm (MRPL) to distribute the traffic load through a set of braided paths to prolong network lifetime. Because of the importance of security, many works, such as secure data forwarding and identification, have considered realizing the trade-off between energy consumption and security when designing the IoT management system. Chen et al.¹⁵ propose a trust management model based on fuzzy reputation. In the system, elements like the packet forwarding/delivery ratio and energy consumption are also considered when designing trust metrics for assessing nodes’ trust value. Sicari et al.¹⁶ proposed a hybrid architecture DARE, which can effectively reduce the amount of data exchanged over the wireless communication and achieve longer battery lifetime. DARE uses a secure verifiable multilateration technique to retain the trustworthiness of aggregated data even in the presence of malicious nodes.

Most current works related to IoT security management mainly focused on how to evaluate the trust value of each node and how to update them. Chen et al.¹⁷ proposed an adaptive trust management protocol that can respond to environmental conditions changing by dynamically adjusting nodes’ trust design parameter settings to provide accurate trust assessment and maximize application performance. Nitti et al.¹⁸ use statistically weighted sum, which consisted of centrality trust and service quality trust, to compute centrality trust. Meanwhile, to detect self-promoted attack, the model uses direct service quality trust assessment and feedback propagation. In terms of changing credibility, the model also treats long-term and short-term direct service quality trust assessment differently in order to defend against opportunistic service attacks. In Bao and Chen,¹⁹ for trust appraisal of IoT nodes, three different properties are considered: honesty, cooperativeness, and community interest. The honesty trust property represents the nodes’ honest degree. The cooperativeness trust property represents whether or not the trustee was socially cooperative with the trustor. The community interest trust represents whether or not the trustor and trustee were in the same social communities or having the similar capabilities. The study of Bao and Chen¹⁹ is one of the first to consider social relationships in trust management for IoT.²⁰ Saied et al.²¹ propose a trust management system to manage cooperation in a heterogeneous IoT architecture. In this system, it assesses and updates pairwise trust value based on their firsthand (i.e. direct experiences) and secondhand (i.e. indirect experiences) information. However, these works lack detailed descriptions of the change of trust transition when a node is communicating with a non-direct node. Unlike social networks, IoT has many restrictions, including radio range and energy consumption restriction. Therefore, it is incapable and unworthy for nodes to directly contact their peers in the cases of long distance and high energy consumption. In order to perform an interaction, the data are transmitted via relay nodes. Hence, when nodes evaluate their peers’ trustworthiness, the individual reputation and communication path reliability need to be considered jointly.

In this article, we propose a novel trust management method for IoT which enables higher energy efficiency under the premise of satisfying a certain trustworthy level of IoT. As the model considers internal factors (restricted resources) and external factors (the trust appraisal of communication route), the network safety and transmission efficiency can be balanced and improved simultaneously. Thus, the contributions of this article can be summarized as follows:

We proposed an evaluation model toward peers’ trust that is the final trust appraisal of peers’ should consider the route trust, including intermediate nodes’ trust value, not only rely on nodes’ individual reputation.

A trustworthy spanning tree algorithm is introduced that considers energy consumption and trust cost based on multiple hops and trust value.

The rest of the article is organized as follows: section “The proposed methods” describes our network, energy, and trust models. Section “Optimum trustworthy spanning tree” introduces the optimum trustworthy spanning tree (OTS) algorithm. Section “Experiments” describes our experiments and the conclusion discussions are given in section “Conclusion.”

The proposed methods

The method proposed in this article can be divided into three models. The first one is that we need to define a network model to discuss the network scenario. Second, all nodes’ energies are limited in IoT, and energy consumption is related with nodes transmitting power and the amount of data, so we need to define the energy model. The third is that we proposed a trust model to study the relationship between data transmission and trust transfer in multi-hop scenarios.

The network model

The network model used in our wok is similar to Heinzelman et al.²² and Latiff et al.,²³ where we assume that the following properties are met:

Each stationary IoT end node (IEN) is deployed randomly in the region of interest, and the position can be mapped into the two-dimensional (2D) space.

There is a BS located in the region of WSN, which acts as the control center for calculating and updating sink. The BS can be placed anywhere and its position is fixed once deployed.

All IENs can receive commands from the BS and switch between the sensing mode and the sink mode.

The network runs periodically and each IEN must send data to the BS to report its sensing situation and state in each cycle, and the BS judges whether the node is alive based on this information.

The sink can aggregate data collected from the sensing nodes in the same cluster.

The energy of each IEN is within a certain range and can be consumed with the transfer of information.

The energy model

In this article, the classical energy model setting^13,22 is used. There are two roles in the model to consume energy: the transmitter, in which the energy is used to run the radio electronics and the power amplifier, and the receiver, which dissipates energy to run the radio electronics. According to the distance between the transmitter and the receiver, the radio energy fading model is classified into two types: free-space model ( $d^{2}$ power loss) and the multipath model ( $d^{4}$ power loss)

$E_{Tx} (l, d) = {\begin{matrix} l E_{elec} + l ε_{fs} d^{2}, d < d_{0} \\ l E_{elec} + l ε_{mp} d^{4}, d \geq d_{0} \end{matrix}$ (1)

$E_{Rx} (l, d) = l E_{elec}$ (2)

By setting a threshold $d_{0}$ , the free-space model is used when the distance is less than $d_{0}$ ; otherwise, we use the multipath model. Thus, the energy consumption of the transmitter to transmit a l-bit message at distance d can be calculated as shown in equation (1), and the receiver receives the same message as equation (2), where $E_{elec}$ is the energy dissipated per bit to run the transmitter or the receiver. The $ε_{fs}$ and $ε_{mp}$ values depend on the transmitter amplifier model we use.

Thus, we can get a weighted directed graph $G_{E} = 〈 V, E, W^{E} 〉$ . Here, $V = V_{1}, V_{2}, \dots$ denotes the set of vertexes (IoT nodes), $E = E_{i, j}$ denotes the set of edges (reachable communication channels) from $V_{i}$ to $V_{j}$ , and $W^{E}$ denotes the set of energy consumption between adjacent nodes. On a certain routing path, the data transmitted through the routing path can be considered almost identical for each intermediate node. Thus, the weight of energy consumption for transmitting between the adjacent nodes $V_{m} and V_{n}$ is $W_{m, n}^{E} = E_{m, n}^{Tx} + E_{m, n}^{Rx}$ . For any communications from $V_{i}$ to $V_{j}$ in the weighted directed graph $G_{E}$ , we have

$W_{i, j}^{E} = \sum W_{m, n}^{E}$ (3)

where $V_{m} and V_{n}$ are the adjacent nodes along with the route path from $V_{i}$ to $V_{j}$ .

The trust model

Despite a large amount of trust-related research, the perspective standard of the trust model is still under investigation.²⁴ From social science, as shown in Figure 1, researchers consider three sources of information to judge trust: public evidences (as reputation), opinions from surroundings (as recommendation), and their own understandings (as knowledge). It is obvious that this process of trust appraisal can be applied for IoT systems.²⁵ In the proposed trust management system, when a node evaluates its peer’s trust value, it mainly bases on the following three criteria, which are adjusted from the following judge rules: (1) the recognized credibility in the current network (as reputation); (2) indirect evaluation and observations reported by neighboring nodes (as recommendation); (3) direct observation and own experience (as knowledge).

Figure 1.

Trust information sources.

To aggregate these different criteria to calculate the final trust appraisal, many aggregation techniques have been introduced, including weighted sum, belief theory, subjective logic, certain logic, Bayesian inference, fuzzy logic, and regression analysis.²⁶ These techniques can be summarized in four steps as shown in Figure 2. The value of trust appraisal ranges from 0 to 1, with 1 indicating complete trust, 0 indicating complete distrust, and a value within $(0, 1)$ indicating semi-trust. The node bases on the final value to decide whether to communicate with the targets and what interaction method can be used. Meanwhile, the peer’s reputation will be recalculated and it will be used in next trust aggregation.

Figure 2.

Trust computation.

In social networks, any two nodes can communicate directly, which means that there exits a pairwise link. Hence, a node can get its peer’s trust value directly. This method to gain trust value can also be applied in image classification²⁷ and IoT nodes that have a direct link with their peers. However, in many cases, the method is not suitable. Sometimes, nodes that send information in IoT cannot interact directly with the receiver due to constrained resources, including limited transmission range and energy capacity. That means data should be conveyed by multi-layer nodes. Therefore, the trust value in IoT depends on not only the individual trust appraisal of the receiver, but also intermediate nodes along the communication path. In the proposed trust management system, as shown in Figure 3, when a node wants to get the data receiver’s trust appraisal, it needs to get the trust appraisal of the node, hop by hop, the value will be updated accordingly, and the final trust appraisal can be calculated when the receiver reaches the final hop.

Figure 3.

Trust decay.

A weighted directed graph $G_{T} = 〈 V, E, W^{T} 〉$ can be obtained where $V = V_{1}, V_{2}, \dots$ denotes the set of vertexes (IoT nodes), $E = E_{i, j}$ denotes the set of edges (reachable communication channels) from $V_{i}$ to $V_{j}$ , and $W^{T}$ denotes the set of trust appraisal between adjacent nodes. For example, Figure 4 shows a simplistic communication topology of IoT. If node $V_{1}$ wants to interact with $V_{5}$ , the shortest route should be selected first, that is, $E_{1, 2} E_{2, 3} E_{3, 5}$ . The trust values of these three links are $W_{1, 2}^{T}, W_{2, 3}^{T}, and W_{3, 5}^{T}$ respectively, and the trust appraisal of $V_{5}$ is $W_{1, 5}^{T} = W_{1, 2}^{T} * W_{2, 3}^{T} * W_{3, 5}^{T}$ . We have

$W_{1, 2}^{T} \geq W_{1, 3}^{T} \geq W_{1, 5}^{T}$ (4)

Figure 4.

Trust decay example.

We define the phenomenon that the value of trust appraisal decreased along the communication route as trust decay. Therefore, more general cases can be confirmed. The value of $W_{i, j}^{T}$ is the product of trust appraisal computed by the adjacent node corresponding to the edge on the route from $V_{i}$ to $V_{j}$ . Namely, if $V_{m} and V_{n}$ are adjacent nodes along with the route path from $V_{i}$ to $V_{j}$ , we have

$W_{i, j}^{T} = Π W_{m, n}^{T}$ (5)

The trust decay has two features: (1) individual—each node bases on its own trust aggregation about its peers to evaluate the potential possibility dangerous of this interaction and (2) asymmetry—A trusts B, which is not equal to B trusting A.

Compared with previous works, the proposed trust model and trust appraisal have two notable differences: (1) The trust value of an interaction depends on the entire link. That is nodes do not only gain trustworthy from data receiver itself, not those intermediate nodes along the communication route are also be take into consideration. (2) The trust appraisal fully uses the safety risks from the process of trust decay, since it is obvious that there are safety risks in each intermediate transferring node.

Considering the energy consumption for transmitting in IoT assuming that the overhead of two-way communication is almost the same, we add up $G_{E} = 〈 V, E, W^{E} 〉$ and $G_{T} = 〈 V, E, W^{T} 〉$ and get a weighted directed graph $G = 〈 V, E, W 〉$ , where $V = V_{1}, V_{2}, \dots$ denotes the set of vertexes (IoT nodes) and $E = E_{i, j}$ denotes the set of edges (reachable communication channels) from $V_{i}$ to $V_{j}$ . The weight of the edge between two vertexes W, which denotes the trustworthy communication overhead, includes two factors: energy consumption and trust decay.

Thus, for any communications from $V_{i}$ to $V_{j}$ in the weighted directed graph $G = (V, E, W)$

$W_{i, j} = U (W_{i, j}^{E}, W_{i, j}^{T})$

where $V_{m} and V_{n}$ are the adjacent nodes along the route path from $V_{i}$ to $V_{j}$ and U is a function for combining the overheads of energy consumption and trust decay.

The total energy consumption and trust decay from nodes to the sink $W_{i, sink} = U (W_{i, sink}^{E}, W_{i, sink}^{T})$ are higher than the threshold. According to the unknown cluster head optimum trustworthy spanning tree (UOTS) algorithm, this node will break its communication link which is directed to its next hop in the original routing, and add a direct routing to the sink. In the current experiment, we normalize the energy consumption and trust attenuation, and divide nodes’ remaining energy by energy consumption; then the perception of energy consumption can be obtained. The cost of trust is calculated by $1 - Π W_{m, n}^{T}$ . Then, we can map energy consumption and trust cost to the interval (0,1).

Table 1 shows the comparison of seven energy models in terms of several topological features. Cluster architecture performs better in scalability due to maintaining a hierarchy in the network. Multipath routing scheme can provide nodes more routing choices even when a relay node runs out of power, which improves the robustness of the network. Those models that utilize energy as a routing metric can achieve a good trade-off between path choice and energy consumption, since the shortest routing and node energy are both considered in this method.

Table 1.

Topological features.

	LEACH	P-SEP	FICA	ESCFR	SHEAR	MRPL	MIEEPB	Our model
Single/multi-hop	S	S	S	M	S	S or M	S or M	M
HD	${0, 1}$	${0, 1}$	${0, 1}$	$[0, H - 1]$	${0, 1}$	$[0, H - 1]$	$[0, H - 1]$	$[0, H - 1]$
Routing mechanisms	A	A	A	B	A and B	C	C and D	B
Topology change trigger	Time	Time	Time or event	Time or event	Time	Time or event	Time or event	Time
Scalability	√	√	√		√			√
Robustness						√	√	√
Flexibility				√	√			√

ESCFR: sine cost function–based route; MRPL: multipath routing algorithm; A: cluster architectures; B: energy as a routing metric; C: multipath routing; D: sink mobility; HD: topological tree height difference; H: topological tree height.

In Guo et al.,²⁶ existing IoT trust computation models can be classified into five types: trust composition, trust propagation, trust aggregation, trust updates, and trust formation. Trust composition refers to what components need to be considered in trust computation, including quality of service (QoS) trust and social trust. Trust propagation refers to the way of propagating trust evidence to peers. This article mainly introduces two propagation schemes: distributed and centralized. Trust aggregation concerns aggregating trust evidence collected through either self-observation or feedback from peers. The aggregation techniques investigated in this literature include weighted sum, belief theory, Bayesian inference, fuzzy logic, and regression analysis. Trust update refers to the trust updated time. Event-driven scheme means that all trust data in a node get updated after an event, while the time-driven scheme concerns whether trust evidence is collected periodically or by applying a trust aggregation technique. Trust formation refers to how to formulate the overall trust with multiple trust properties, which includes single-trusted and multi-trusted. Table 2 shows some up-to-date methods and the differences in trust management features.

Table 2.

Trust computation.

	Trust composition	Trust propagation	Trust aggregation	Trust update	Trust formation
TRM-IoT	Social trust	Distributed	Fuzzy logic	Time driven	Multi-trust
Gu et al.²⁸	QoS trust	Centralized	Fuzzy logic	Time driven	Multi-trust
Chen et al.²	Social trust and QoS trust	Distributed	Bayesian systems and weighted sum	Time driven and event driven	Single trust
Guo et al.²⁹	QoS trust and social trust	Distributed	Bayesian systems and weighted sum	Time driven and event driven	Single trust
Josang³⁰	Social trust	Distributed	Belief theory	Time driven	Multi-trust
Namal et al.³¹	QoS trust	Centralized	Weighted sum	Time driven	Multi-trust
LogitTrust³²	Social trust	Distributed	Regression analysis	Time driven	Multi-trust
Yu and Singh³³	Social trust	Distributed	Belief theory	Time driven	Multi-trust
Alzaid et al.³⁴	QoS trust	Distributed	Weighted sum	Event driven	Single trust
DARE	Social trust	Distributed	Weighted sum	Time driven	Multi-trust
Our model	Social trust	Distributed	Weighted sum	Time driven	Multi-trust

QoS: quality of service.

OTS

One of the remarkable features of IoT is that those collected data need to pass through some middle nodes in the transmission process. In the last chapter, a weighted directed graph $G = 〈 V, E, W 〉$ has been defined as IoT trust topology. In order to build a routing tree with the lowest energy consumption and trust attenuation from non-CH node to CH node for data storage and forwarding, the directed analog of the minimum spanning tree (sometimes called optimum branching) need to be found from the weighted directed graph $G = 〈 V, E, W 〉$ . In this article, the finding process is called the OTS problem.

The directed analog of the minimum spanning tree algorithm was proposed independently first by Chu and Liu³⁵ and then by Tarjan.³⁶ However, these two algorithms cannot be applied to OTS due to two main differences:

These two algorithms focus on the message split network scenario, and their construction methods of spanning tree are traversing graphs along the direction of edge. For the network of minimum trustworthy spanning tree (MTS), the network needs to be slightly deformed to use Edmonds’ algorithm.

The root node of IoT needs to be predetermined in these two algorithms. However, in the OTS network scenario, the CH node is unknown, so optimum branching algorithm can just be used in the network with certain CH node to solve OTS.

Therefore, the solution of the MTS problem can be listed in three different cases.

Case 1: pre-known CH

In the first case, the CH is pre-known. In a cluster, if there exists a node that has absolute advantages in terms of energy, reliability, and performance, the node is certainly be chosen as the CH. For example, the BS that eventually receives and forwards all the data in the top layer of a hierarchical IoT network cluster is one of typical CH.

Edmonds’ algorithm is designed for the message split network scenario, and the single source of information of the final formed spanning tree is called the root, which is only in the network which has outgoing edges and no incoming edges. Therefore, for the OTS problem, we need to export a graph $G' = 〈 V', E', W' 〉$ from graph $G = 〈 V, E, W 〉$ . The rule of exporting $G'$ is reversing the direction of all sides, which is easy to realize in the practical scenario. More precisely, M, which is the adjacency matrix of graph G, should be calculated first, then the transposed matrix of M, $M'$ , and finally $M'$ is exchanged to $G'$ .

Afterwards, Edmonds’ algorithm is applied to graph $G'$ to generate a spanning arborescence $A'$ rooted at s of minimum weight, where the weight of a branch is defined to be the sum of its edge weights, $W (A) = \sum_{E_{i, j} \in E} W_{i, j}$ .

Reversing all the sides of spanning arborescence $A'$ provides a spanning arborescence A. The algorithm is called pre-known cluster head optimum trustworthy spanning tree (POTS). The details of such process can be described as follows: reversing all the edges of spanning arborescence $A'$ and getting a spanning arborescence A; then calculating $W_{i, CH}$ for $V_{i}$ of all the nodes except CH in A. If $W_{i, CH}$ is bigger than the trustworthy threshold, remove the outgoing edge from $V_{i}$ in A and add a direct edge from $V_{i}$ to the CH node in A, after which the final A can be obtained, which is also the solution of OTS.

Algorithm 1. Pre-known cluster head optimum trustworthy spanning tree (POTS) algorithm
1: Transform G to $G'$ ;2: Call Edmonds’ algorithm for $G'$ , and get a spanning arborescence $A'$ ;3: Transform $A'$ to A;4: for each node $V_{i} \in V$ from A do5: if W_i,CH > trustworthy threshold then6: Remove the outgoing edge from $V_{i}$ in A;7: Add a direct edge from $V_{i}$ to the CH node in A;8: end if9: end for10: A is the solution.

The running time of Edmonds’ algorithm is $O (EV)$ . A faster implementation of the algorithm given by Tarjan³⁷ runs in time $O (E \log V)$ for sparse graphs and $O (V^{2})$ for dense graphs.

Case 2: unknown CH

UOTS algorithm is proposed for the case with unknown CH.

Algorithm 2. Unknown cluster head optimum trustworthy spanning tree (UOTS) algorithm
1: Clone graph $G = 〈 V, E, W 〉$ to get a graph $D = 〈 V, E, W 〉$ ;2: for each node $V_{i} \in V$ from D do3: if exist out-degree of $V_{i}$ is 1 then4: if $V - V_{i} = ϕ$ for D then5: Add $V_{i}$ into the candidate set of cluster head, C;6: Break;7: else8: Remove $V_{i}$ from D;9: end if10: Add V, which are remaining in D, into the candidate set of cluster head, C;12: Break;13: end if14: end for15: for each node $V_{i} \in C$ do16: Call the POTS algorithm for graph $G = 〈 V, E, W 〉$ and get a candidate set of spanning arborescence ${A_{i}}$ and the corresponding candidate set of weights ${W (A_{i})}$ .17: end for18: Find the spanning arborescence A, which has the smallest weight $W (A)$ .19: for each node $V_{i} \in V$ from A do20: if W_i,CH > the trustworthy threshold then21: Remove the outgoing edge from $V_{i}$ in A;22: Add a direct edge from $V_{i}$ to the CH node in A;23: end if24: end for25: A is the solution.

Algorithm 2. Unknown cluster head optimum trustworthy spanning tree (UOTS) algorithm

1: Clone graph

G = 〈 V, E, W 〉

to get a graph

D = 〈 V, E, W 〉

;2: for each node

V_{i} \in V

from D do3: if exist out-degree of

V_{i}

is 1 then4: if

V - V_{i} = ϕ

for D then5: Add

V_{i}

into the candidate set of cluster head, C;6: Break;7: else8: Remove

V_{i}

from D;9: end if10: Add V, which are remaining in D, into the candidate set of cluster head, C;12: Break;13: end if14: end for15: for each node

V_{i} \in C

do16: Call the POTS algorithm for graph

G = 〈 V, E, W 〉

and get a candidate set of spanning arborescence

{A_{i}}

and the corresponding candidate set of weights

{W (A_{i})}

.17: end for18: Find the spanning arborescence A, which has the smallest weight

W (A)

.19: for each node

V_{i} \in V

from A do20: if W_i,CH > the trustworthy threshold then21: Remove the outgoing edge from

V_{i}

in A;22: Add a direct edge from

V_{i}

to the CH node in A;23: end if24: end for25: A is the solution.

The proposed algorithm can be described as follows: first, obtain the candidate set of the CH with a minimum number of nodes; then, using POTS algorithm generate the candidate sets of OTS solutions. Finally, the spanning arborescence with optimum weight can be regarded as the solution of OTS. However, the computing cost is too high if the node set V in graph G is directly chosen as a candidate set of CH nodes. Obviously, a node with out-degree 1 is certainly not the CH node searched for, so the loop is called to remove nodes with out-degree 1. The complexity of the UOTS algorithm is $O (E V^{2})$ .

Case 3: simplified scenario

In some centralized management scenarios, the attenuation of trust does not contain too many personalized parts. Therefore, the scenerio can be simplified as follows. Assuming that the trustworthy communication overhead between adjacent nodes in a network is constant and symmetrical. There is a threshold of trust $Γ^{*}$ , which make trustworthy communication connection can no longer be established. Then, the percentage of trustworthiness lost by data transmission through each hop node d can be computed using $Γ^{*}$ divide trustworthy communication overhead. The trustworthy decay rate per hop is $r = d - 1, r \in [- 1, 0]$ .

The trust model with weighted directed graph $G = 〈 V, E, W 〉$ can be simplified to a weighted undirected graph $U = (V, E, W)$ . Hence, the problem of OTS can be transformed into optimum spanning tree for a weighted undirected graph problem.

Classical Prim’s³⁸ algorithm is a greedy algorithm, which can be used to find an optimal spanning tree for a weighted undirected graph. The same solution of the algorithm can also be obtained following the first and the second cases. Next, we analyze the depth of the routing tree created in this case, which is given by Theorem 1.

Theorem 1 (trustworthy communication overhead)

We extend the domain of the trust value function $Γ$ to the real number field $R$ ; thus, setting $t \in R, t \geq 0$ , we get a continuous function

$Γ = Γ_{0} e^{r (t - t_{0})}, r \in [- 1, 0]$ (6)

where t denotes the number of hops and the constant trustworthy decay rate is denoted by $r \in R$ .

Proof of Theorem 1

For each $Δ t \to 0$ , we have

$Γ (t + Δ t) - Γ (t) = r Γ (t) Δ t$

In the initial case, $Γ = Γ_{0}$ where $t = t_{0}$ , and thus we have

${\begin{matrix} \frac{d Γ}{dt} = r Γ \\ Γ (t_{0}) = Γ_{0} \end{matrix}$

Therefore

${\begin{matrix} \frac{1}{Γ} d Γ = r d t \\ \ln Γ = \int r d t + c \\ Γ = e^{r t + c} \end{matrix}$

Setting $t = t_{0}$ , we get

$\begin{matrix} Γ_{0} = e^{r t_{0} + c} \begin{matrix} \end{matrix} \\ c = \ln Γ_{0} + r t_{0} \end{matrix}$

Substituting c into the equation of $Γ$ , we get

$Γ = Γ_{0} e^{r (t - t_{0})}, r \in [- 1, 0]$

Lemma 1 (trustworthy communication overhead from itself)

Considering trust decay with a constant rate r, if IET trust itself completely, means $t_{0} = 0$ and $Γ_{0} = 1$ . According to Theorem 1, we get

$Γ = e^{rt}, r \in [- 1, 0]$

Considering $t \in N$ after all, we get

$t = ⌊ \frac{\ln Γ}{r} ⌋$ (7)

If $Γ = Γ^{*}$ , it means that the trustworthy communication connection can no longer be established, and we have the maximum value of hops $t^{*}$

$t^{*} = ⌊ \frac{\ln Γ^{*}}{r} ⌋$ (8)

In a cluster, data are collected by normal nodes and sent to the sink node for aggregation. The CH node forwards the data to the upper-level node. Therefore, as a boundary, the sink node breaks the upper and lower topology nodes into two security domains. Obviously, normal nodes need to establish a trusted communication path to transmit data through the sink node, so the height of minimum spanning tree $T = 〈 V, E, W 〉$ is no larger than $t^{*}$ .

Overall, it can be found that, in these three cases proposed in this article, cases 1 and 3 are simplified versions of case 2. Therefore, the experiment in this study is mainly focused on case 2 and the results will be compared with those of the other algorithms.

Experiments

The first experiment is about the energy consumption comparison with the classical algorithm LEACH. Table 3 shows the experimental parameter settings. Figure 5 presents the experimental results. Figure 5(a) shows the initial state of node distribution and the space $100 \times 100 m^{2}$ includes 100 communication nodes distributed randomly. Figure 5(b) shows the clustering and CH selection situation by adopting LEACH (initial number of CHs is 5 and the round number is 1). For LEACH, non-CH nodes in each cluster communicate directly with their CH, which then transfers those collected data to the BS. Figure 5(c) represents the condition of only considering communication consumption without trust decay (MIT), adopting multi-hop routing to construct network topology with minimum routing tree. Red solid dots represent the single sink which is responsible for conveying all data to the BS. Figure 5(d) shows using the UOTS algorithm to build OTS. Nodes marked with blue circles send data directly to the sink, since the whole cost $W_{i, sink} = U (W_{i, sink}^{E}, W_{i, sink}^{T})$ , including energy consumption and trust decay, from them to sink along the routing path of OTS is higher than the threshold. According to UOTS, this node will break its communication link which is directed to the next hop in the original routing and add a direct routing to the sink. In our experiment, we normalize the energy consumption and trust attenuation, and divide nodes’ remaining energy by energy consumption; then the perception of energy consumption can be obtained. The cost of trust is calculated on the basis of one minus the remaining trust value from the self-attenuation to the destination node, namely, $1 - Π W_{m, n}^{T}$ . Then, we scale energy consumption and trust cost to (0,1). The results are intuitive and similar to social networks, where people do not trust a network node or a communication link, and even when accessing the network is convenient and inexpensive, more money needs to be spent to access a more reliable network for security reasons.

Table 3.

Experimental parameters setting.

	LEACH	MIT	UOTS
Distribution area $(m^{2})$	$100 \times 100$	$100 \times 100$	$100 \times 100$
Number of nodes	100	100	100
Number of CHs	5	5	5
Length of every data package (bytes)	500	500	500
Energy range	$0.2 - 0.8$	$0.2 - 0.8$	$0.2 - 0.8$
Bandwidth (MB/s)	1	1	1
Base station location	$(50, 50) or (50, 155)$	$(50, 50) or (50, 155)$	$(50, 50) or (50, 155)$
Electronic energy, $E_{elec}$ , (nJ/bit)	50	50	50
Amplifier coefficient $(d < d_{0})$ , $ε_{fs} v$ , (pJ/bit/m²)	10	10	10
Amplifier coefficient $(d \geq d_{0})$ , $ε_{fs} v$ , (pJ/bit/m⁴)	0.0013	0.0013	0.0013
Energy for data aggregation, $E_{DA}$ , (nJ/bit)	5	5	5
Trust decay	0	0	$0.99 - 0.9$

UOTS: unknown cluster head optimum trustworthy spanning tree.

Figure 5.

Topology distribution: (a) initial node distribution, (b) LEACH, (c) multi-hop ignoring trust decay, and (d) trustworthy multi-hop.

In Figure 6, we compare the LEACH algorithm, multi-hop ignoring trust decay, and trustworthy multi-hop algorithm via investigating topological distribution of routing energy consumption against the increase of the number of nodes. The results show that the energy consumed by LEACH is the highest, while the value is less than that of LEACH by about $22 %$ for multi-hop ignoring trust decay, and the figure for trustworthy multi-hop is slightly higher than that for multi-hop ignoring trust decay, but it still presents about $20 %$ more energy than LEACH.

Figure 6.

Energy consumption comparison.

Figure 7 shows the analysis toward energy consumption and trust value of information sent from each node to the sink. The ranges of trust decay are $0.95 - 0.93$ , $0.97 - 0.95$ , and $0.99 - 0.97$ . The features of energy consumption and trust value are listed as follows:

The larger the trust decay is, the slower the trust decays with the increase of the number of hops in the routing. Nodes send the message to the sink through a longer multi-hop path, and hence the node can save energy by sending the message to the nearby neighboring node. Meanwhile, it can be seen from Figure 6 that the longer the multi-hop path is, the lower the energy overhead is.

Conversely, the smaller the trust decay is, the larger the trust decays. Since some nodes are not able to establish trustworthy communication with sink nodes through multiple hops, it is evitable for some nodes to improve the power of the antenna itself and send data to the sink directly. In this case, it will consume more energy based on the characteristics of radio data transmission.

Trust value to the sink node fluctuates near a certain value. In Chen et al.,² the value is called the ground truth. In this case, the multi-hop routing of each node to the sink is relatively stable, and its communication energy consumption is relatively stable within a certain range. The experimental results showed are an example of the energy consumption of each node, which is in the range of $0.005 - 0.05$ .

Figure 7.

Energy consumption versus trust.

Conclusion

Since different standards and communication stacks are involved, traditional security mechanisms heavily rely on trust management to function well. In this article, we propose an energy-aware trustworthy multi-hop routing model for IoT and introduce a spanning tree routing algorithm to balance energy consumption and trust. The experimental results show that our algorithm is quantitative with energy of about $20 %$ than LEACH and is more robust and secure to avoid the threats posed by malicious nodes, such as abnormal transfer caused by trust appraisal failure compared with multi-hop ignoring trust decay. Our next work is to study the efficient trustworthy network routing method across multiple security domains between different services.

Footnotes

Handling Editor: Shancang Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This work was supported by the National Natural Science Funds of China (61773314,61602376,61702411,and 61602374),the Natural Science Funds of Shanxi Province (2017JQ6020 and 2016JQ6041),the Science Technology Project of Shaanxi Education Department (16JK1573 and 16JK1552),the PhD Research Startup Funds of Xi’an University of Technology (112-256081504),and the College Research Funds of Xi’an University of Technology (112-451016007).

ORCID iD

Yichuan Wang

References

Son

Kang

Gwak

et al . An adaptive IoT trust estimation scheme combining interaction history and stereotypical reputation. In: Proceedings of 2017 14th annual consumer communications & networking conference (CCNC), Las Vegas, NV, 8–11 January 2017, pp.349–352. New York: IEEE.

Chen

Guo

Bao

Trust management for SOA-based IoT and its application to service composition. IEEE T Serv Comput 2017; 9(3): 482–495.

Jabeur

Yasar

Shakshuki

et al . Toward a bio-inspired adaptive spatial clustering approach for IoT applications. Future Gener Comp Sy. Epub ahead of print 27 May 2017. DOI: 10.1016/j.future.2017.05.013.

Perles

Perezmarin

Mercado

et al . An energy-efficient Internet of Things (IoT) architecture for preventive conservation of cultural heritage. Future Gener Comp Sy 2018; 81: 566–581.

Rault

Bouabdallah

Challal

Energy efficiency in wireless sensor networks: a top-down survey. Comput Netw 2014; 67(4): 104–122.

Shalli

Rajneesh

Jyoteesh

et al . A novel scheme for an energy efficient Internet of Things based on wireless sensor networks. Sensors (Basel) 2015; 15(11): 28603–28627.

Fredj

Boussard

Kofman

et al . A scalable IoT service search based on clustering and aggregation. In: Proceedings of 2013 IEEE international conference on green computing and communications and IEEE Internet of things and IEEE cyber, physical and social computing, Beijing, China, 20–23 August 2013, pp.403–410. New York: IEEE.

Machado

Rosário

Cerqueira

et al . A routing protocol based on energy and link quality for Internet of Things applications. Sensors (Basel) 2013; 13(2): 1942–1964.

Anfeng

Design principles and improvement of cost function based energy aware routing algorithms for wireless sensor networks. Comput Netw 2012; 56(7): 1951–1967.

10.

Warrier

Kumar

An energy efficient approach for routing in wireless sensor networks. Proc Tech 2016; 25: 520–527.

11.

Radi

Dezfouli

Bakar

et al . IM2PR: interference-minimized multipath routing protocol for wireless sensor networks. Wirel Netw 2014; 20(7): 1807–1823.

12.

Yan

Zhang

Vasilakos

AV.

A survey on trust management for Internet of Things. J Netw Comput Appl 2014; 42(3): 120–134.

13.

Heinzelman

Chandrakasan

Balakrishnan

. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of 33rd annual Hawaii international conference on system sciences, Maui, HI, 7 January 2000, p.8020. New York: IEEE.

14.

Moghadam

Taheri

Karrari

Minimum cost load balanced multipath routing protocol for low power and lossy networks. Wirel Netw 2014; 20(8): 2469–2479.

15.

Chen

Chang

Sun

et al . TRM-IoT: a trust management model based on fuzzy reputation for Internet of Things. Comput Sci Inf Syst 2011; 8(4): 1207–1228.

16.

Sicari

Coen-Porisini

Riggio

DARE: evaluating Data Accuracy using node REputation. Comput Netw 2013; 57(15): 3098–3111.

17.

Chen

Bao

Guo

Trust-based service management for social Internet of Things systems. IEEE T Depend Secure 2016; 13(6): 684–696.

18.

Nitti

Girau

Atzori

Trustworthiness management in the Social Internet of Things. IEEE T Knowl Data En 2014; 26(5): 1253–1266.

19.

Bao

Chen

I-R

. Trust management for the Internet of Things and its application to service composition. In: Proceedings of 2012 IEEE international symposium on a world of wireless, mobile and multimedia networks (WoWMoM), San Francisco, CA, 25–28 June 2012, pp.1–6. New York: IEEE.

20.

Sicari

Rizzardi

Grieco

et al . Security, privacy and trust in Internet of Things: the road ahead. Comput Netw 2015; 76: 146–164.

21.

Saied

Olivereau

Zeghlache

et al . Trust management system design for the Internet of Things: a context-aware and multi-service approach. Comput Secur 2013; 39: 351–365.

22.

Heinzelman

Chandrakasan

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–670.

23.

Latiff

NMA

Tsimenidis

Sharif

. Energy-aware clustering for wireless sensor networks using particle swarm optimization. In: Proceedings of 2007 IEEE 18th international symposium on personal, indoor and mobile radio communications, Athens, 3–7 September 2007, pp.1–5. New York: IEEE.

24.

Sun

Han

et al . Information theoretic framework of trust modeling and evaluation for ad hoc networks. IEEE J Sel Area Comm 2006; 24(2): 305–317.

25.

Truong

Cao

et al . Leverage a trust service platform for data usage control in smart city. In: Proceedings of 2016 IEEE global communications conference (GLOBECOM), Washington, DC, 4–8 December 2016, pp.1–7. New York: IEEE.

26.

Guo

Chen

I-R

Tsai

JJP

. A survey of trust computation models for service management in Internet of Things systems. Comput Commun 2017; 97: 1–14.

27.

Xiao

Wang

et al . 2D-LBP: an enhanced local binary feature for texture image classification. IEEE T Circ Syst Vid. Epub ahead of print 24 September 2018. DOI: 10.1109/TCSVT.2018.2869841.

28.

Wang

Sun

Trust management mechanism for Internet of Things. China Commun 2014; 11(2): 148–156.

29.

Guo

Chen

I-R

Bao

. Scalable, adaptive and survivable trust management for community of interest based Internet of Things systems. In: Proceedings of 2013 IEEE eleventh international symposium on autonomous decentralized systems, Mexico City, MX, 6–8 March 2013, pp.1–7. New York: IEEE.

30.

Josang

A logic for uncertain probabilities. Int J Uncertain Fuzz Know Syst 2001; 9(3): 279–311.

31.

Namal

Gamaarachchi

Myounglee

et al . Autonomic trust management in cloud-based and highly dynamic IoT applications. In: Proceedings of ITU kaleidoscope: trust in the information society (K-2015), Barcelona, 9–11 December 2016, pp.1–8. New York: IEEE.

32.

Wang

Chen

I-R

et al . LogitTrust: a logit regression-based trust model for mobile ad hoc networks. In: Proceedings of the 6th ASE international conference on privacy, security, risk and trust, Cambridge, MA, 14–16 December 2014, pp.1–10. University of Georgia Law Library.

33.

Singh

. An evidential model of distributed reputation management. In: Proceedings of the first international joint conference on autonomous agents and multiagent systems: part 1, Bologna, 15–19 June 2002, pp.294–301. New York: ACM.

34.

Alzaid

Foo

Ahmed

Mitigating on-off attacks in reputation-based secure data aggregation for wireless sensor networks. Secur Commun Netw 2012; 5(2): 125–144.

35.

Chu

Liu

TH.

On the shortest arborescence of a directed graph. Sci Sinica 1965; 14: 1396–1400.

36.

Tarjan

RE.

Finding optimum branchings. Netw 1977; 7(1): 25–35.

37.

Tarjan

RE.

Depth-first search and linear graph algorithms. SIAM J Comput 1972; 1(2): 146–160.

38.

Prim

RC.

Shortest connection networks and some generalizations. BELL Syst Tech J 1957; 36(6): 1389–1401.