# A Novel Markov Model-Based Low-Power and Secure Multihop Routing Mechanism

Authors: Songxiang Yang; Lin Ma; Shuang Jia; Danyang Qin
Journal: Journal of Sensors
 (2019)

---

## Abstract

For the severe impact of limited energy and network attacks caused by open transmission channels on data transmission, this paper presents a low-power and secure multihop routing mechanism based on the Markov state transition theory. The random selection of transmission paths enables the network to resist typical attacks such as interference and interception, thus ensuring the security of data transmission. Meanwhile, the proposed algorithm can reduce the overall energy consumption of the network and balance the load according to the residual energy of each path. Simulation results prove that the routing mechanism proposed in this paper can improve the energy efficiency and the security of the wireless ad hoc network.


---

## Body

## 1. Introduction

A wireless ad hoc network is a kind of noncentral network which is established by a large number of sensor nodes through self-organization. A wireless ad hoc network with self-organized, distributed, and dynamic characteristics can often be deployed in a harsh environment without relying on fixed facilities [1–3]. Compared with the traditional centralized network, the distributed wireless multihop network has the advantage of lower cost, better universality, and wider application field [4–7]. However, nodes in the wireless ad hoc network are powered by energy-limited batteries. The system cannot perform normal sensing and data transmission when the node’s battery is exhausted. Therefore, how to improve the energy efficiency of nodes is a problem that the wireless ad hoc network must solve in practical applications. Security is also crucial for a wireless ad hoc network due to the openness of transmission channels. A routing mechanism should resist some common attacks taking into account energy efficiency, so a routing mechanism with high security and energy efficiency is the key to improving the performance of a wireless ad hoc network [8–14]. However, it is difficult to take both energy efficiency and security into account for existing computationally intensive routing algorithms. These practical requirements pose new challenges to the security and efficiency of wireless ad hoc network routing algorithms.To improve the security of routing in wireless ad hoc networks, researchers have proposed many relevant algorithms, such as the data encryption algorithm [15, 16], the trust-based security routing algorithm [17–20], and the game theory-based security transmission algorithm [21–23]. The large amount of computation makes it challenging to apply the traditional encryption algorithm directly to the energy-constrained wireless ad hoc networks. Specifically, the trust-based security algorithm is poor in universality, and all nodes in the system need to be trusted so that this kind of security algorithm cannot meet the actual demand of a wireless ad hoc network. The performance of the game theory-based security algorithm is significantly affected by the network environment. Reference [24] proposes a low-complexity sybil attack detection mechanism which can be implemented in both hierarchical and centralized wireless sensor networks. Extensive simulations prove that the proposed scheme is able to detect sybil attacks with higher probability and lesser computational cost and power consumption as compared to existing schemes. Reference [25] is based on the ant colony optimization algorithm to select the shortest path and balance the traffic load from the source node to the destination node, so as to prolong the network lifetime. The security of information transmission is guaranteed by anonymous services, symmetric functions, and hash functions. However, the energy consumption of data forwarding is not specifically optimized. Reference [26] proposes an energy-aware routing protocol in WSNs, which makes efficient use of energy and increases reliability in data delivery. An adaptive power-control-based energy-efficient routing is proposed in [27], which increases the network lifetime and reduces communication interference and collision.A number of researches show that reasonably selecting routing can not only improve the security of data transmission but also optimize the energy efficiency of a network. This kind of method is also known as the random routing algorithm. The random routing algorithm can search multiple neighbor nodes and select the next hop node of the transmission link according to specific probability distribution in order to guarantee the randomness and security of the routing selection. In this paper, the residual energy of nodes on the transmission link is introduced in the probability density distribution to balance the network load, which can improve the overall energy efficiency of wireless ad hoc networks. The information transmission path cannot be obtained by the intruder in the absence of the node residual energy and the state transition probability model, which can guarantee the security of the data transmission. A reasonable improvement of the energy efficiency can extend the network lifetime, thereby improving the overall performance of the network. Reference [28] adopts secret sharing and multipath routing to achieve secure information transmission. Firstly, all shared paths are determined. The traditional node-disjoint multipath constraint is relaxed to allow multiple paths within a particular elliptical region to have common nodes, thereby improving transmission security and energy efficiency. However, these methods only optimize performance for static WSN networks and do not adjust for the networks with mobile nodes. For the resource-limited multihop network, the energy efficiency needs to be taken into account while ensuring security. Therefore, the reasonable selection of a data transmission path is crucial to optimize network energy consumption, data transmission security, and network load.The main contributions of this paper can be summarized as follows: this paper establishes a data-oriented Markov state transition model and designs a low-power and secure multihop routing mechanism. The protocol randomly selects a transmission path such that the network has the ability to resist typical attacks, so as to ensure the security of data transmission. Meanwhile, the protocol can reduce the overall energy consumption of the network and balance the load according to the remaining energy of each path. We implemented the proposed LSRM in our lab and evaluated its performance. The experiment results show that LSRM can succeed to resist typical attacks and improve data transmission. Meanwhile, LSRM can distribute the network load to each path evenly and reduce the overall energy consumption. The overall research idea of this paper is shown in Figure1.Figure 1
Research framework.


## 2. Model Introduction

### 2.1. System Model

Considering the practical application of a wireless ad hoc network, the nodes in the network are limited in energy and communicate with other nodes through the wireless connection. This is because the energy consumption of a wireless transceiver is far higher than that of information collection and computing, and the energy consumption of relay nodes on transmission links is generally large due to their frequent relay forwarding. In contrast, the energy consumption of both source nodes and destination nodes is relatively small. To ensure the security of data, all nodes in the network have trust modules which are used to check the threshold of the routing measure and to adjust the threshold periodically or as required. The source node adopts the reactive routing protocol to establish multiple paths. The time lag between two successive routing discovery processes is known as a routing phase. The communication process is divided into several routing phases, and each routing phase is also divided into a few states, known as theti period. The routing mechanism updates the relevant data during ti. The routing protocol selects one of the multiple paths created in each interval to send the packet based on this value function. Figure 2 shows a communication process.Figure 2
The sequence diagrams of the routing protocol.For a random multipath routing scenario, the sequence diagram in Figure2 shows the path selection of three consecutive routing phases and each state transition cycle, as well as the path switching between different time slots.Assuming that there areN paths in a routing phase, the transmission energy consumption of the jth node on the i path during the period ti is ei,j. In different routing phases, the values of N and ei,j will change with time. The probability mass function of N is represented by e~N, and the corresponding cumulative mass function is E~N. The energy consumption vector of path l is represented by ek=el,1,el,2,⋯,el,k. Therefore, the total transmission energy consumption on the path l is El=∑j=1lel,j. The probability density function of El is e^l, and the cumulative distribution function is E^l.


### 2.2. Attack Model

In wireless ad hoc networks, mobile nodes transmit data in wireless channels through multihop, which provides an opportunity for attackers to jam and intercept data. The attacker can intercept the data from any intermediate node easily. An attacker with a high-power transmitter can generate a strong signal to suppress the destination node and to disrupt the data transmission. An attacker can also block a data channel, thus causing data loss or damage. The routing protocol of a wireless ad hoc network faces a variety of attacks, including internal attacks and external attacks. Internal attacks are mainly launched by the damaged nodes to publish false information to the network. Such attacks are difficult to identify accurately due to the frequent changes of network topology. External attacks often interfere with relay nodes and intercept and steal data transmission to affect the normal operation of a network, as shown in Figure3. In Figure 3, A~F denote the nodes in the network. Two external attacks, sniffing and tampering, are considered during the simulation in this paper.Figure 3
Attack model.The traditional routing protocol has no special security protection, so this kind of attack is prevalent. The introduction of an encryption algorithm can improve the difficulty of decoding data packets, thus playing a defensive role. However, the complex operation of such algorithms will lead to much energy consumption, so it is not effective in practical applications. The risk of these attacks can be reduced by obfuscating the data transmission path.


### 2.3. Establishment of Data Transmission Link

In wireless ad hoc networks, the routing mechanism establishes numerous paths to transmit the packets. Meanwhile, all potential paths are discovered in the routing discovery phase. All the paths between the source node and the destination node are constructed by using the on-demand routing protocol in the routing discovery phase due to the large amount of system overhead generated by the active routing protocol. These paths are selected for data transmission between nodes randomly.Each packet contains a minimum energy measure (min_em) during communication. The min_em of a path is the min_em of all nodes on a path. The source node transmits a routing request message whose min_em is 0 to establish the transmission path between nodes. An intermediate node will compare its min_em to the energy measure threshold of a routing request message when the routing request message is received. And the node will compare its min_em with that of the routing request message if the min_em is no less than the threshold. Otherwise, the routing request message will be terminated. If the min_em of the node is smaller than that of the message, the latter one will be replaced by the former, and the total hops will plus 1. The routing request message is transmitted and the intermediate node will forward it directly if the min_em node is larger than that of the routing request message. Eventually, the paths with different hops will be discovered, as shown in Figure 4.Figure 4
The model of the data transmission link.The different transmission paths will be established betweenS and D when D receives multiple routing request packets. The destination node can select the path by setting the threshold of hops in the actual operation of a network. Then, the min_em of the routing request packet selected by the destination node is attached to the routing response packet and passed back to the source node via the original path. Subsequently, the source node selects the routing with the highest initial probability distribution to transmit the packets.


### 2.4. Markov State Transfer Model

#### 2.4.1. Background

The Markov state transfer model can be used as a mathematical model for transitions between series states, and it is a common random method to predict system performance. The Markov state transfer model is based on a probability distribution, which can predict the transitions between various states. Since the number of states is limited and the transitions between different states are based on a certain probability distribution, it can adapt to the time variability of node communication. Besides, the transition probability between different states is independent of the previous phase. The set of all states in the Markov state transfer model is called the state space, i.e.,L=L1,L2,⋯,Ll. O represents the mapping between different states. The routing protocol can execute any O allowed in the state to switch the path from Li to Lj, and the transition probability of this process is pij. The system will send response rLi,Lj,O after the state transition is completed. The transition probability is pjj if the two states are consistent.


#### 2.4.2. Probability Analysis

Li represents the transmission path. P is the transition probability matrix. pi,j∈P is the transition probability from Li to Lj, as shown in Figure 5.Figure 5
Markov state transition model.Ai is the initial probability distribution. The transfer probability matrix P of the Markov state transition model can be constructed by setting pi,j. As defined above, the energy measure of path Li is represented by min_em. A path with a maximum min_em is selected as the initial path, so the initial probability distribution Ai of path Li can be determined:
(1)Ai=min_emi∑k=1lmin_emk.The energy of nodes on the path will be consumed, and the energy measure of the path will decrease gradually during the process of data transmission.em is adopted to represent all vectors of a path energy measure:
(2)em=min_em1,min_em2,⋯,min_eml.The calculation ofpi,j under different conditions is shown in (3), where ∑lpi,j=1. And αα≥2 is the performance parameter and mainly used to reduce the path transfer probability. The main reason for setting this parameter is that the probability of moving from a path with a higher energy measure to one with a lower energy measure is relatively low.
(3)pi,j=min_emi−min_emj∑lmin_emi−min_emjα,Li≠Lj,min_emi>min_emj,min_emi−min_emj∑lmin_emi−min_emj,Li≠Lj,min_emi<min_emj,1−∑k∈lpi,k,Li=Lj,Li≠Lk.SinceAi can guarantee energy efficiency, the system can ensure the security and efficiency of a transmission at the same time when switching path randomly according to Ai. The transmission path of the next phase can be determined by Ai′ when the first state transition is completed, where Ai′=Ai×pi,j.


## 2.1. System Model

Considering the practical application of a wireless ad hoc network, the nodes in the network are limited in energy and communicate with other nodes through the wireless connection. This is because the energy consumption of a wireless transceiver is far higher than that of information collection and computing, and the energy consumption of relay nodes on transmission links is generally large due to their frequent relay forwarding. In contrast, the energy consumption of both source nodes and destination nodes is relatively small. To ensure the security of data, all nodes in the network have trust modules which are used to check the threshold of the routing measure and to adjust the threshold periodically or as required. The source node adopts the reactive routing protocol to establish multiple paths. The time lag between two successive routing discovery processes is known as a routing phase. The communication process is divided into several routing phases, and each routing phase is also divided into a few states, known as theti period. The routing mechanism updates the relevant data during ti. The routing protocol selects one of the multiple paths created in each interval to send the packet based on this value function. Figure 2 shows a communication process.Figure 2
The sequence diagrams of the routing protocol.For a random multipath routing scenario, the sequence diagram in Figure2 shows the path selection of three consecutive routing phases and each state transition cycle, as well as the path switching between different time slots.Assuming that there areN paths in a routing phase, the transmission energy consumption of the jth node on the i path during the period ti is ei,j. In different routing phases, the values of N and ei,j will change with time. The probability mass function of N is represented by e~N, and the corresponding cumulative mass function is E~N. The energy consumption vector of path l is represented by ek=el,1,el,2,⋯,el,k. Therefore, the total transmission energy consumption on the path l is El=∑j=1lel,j. The probability density function of El is e^l, and the cumulative distribution function is E^l.


## 2.2. Attack Model

In wireless ad hoc networks, mobile nodes transmit data in wireless channels through multihop, which provides an opportunity for attackers to jam and intercept data. The attacker can intercept the data from any intermediate node easily. An attacker with a high-power transmitter can generate a strong signal to suppress the destination node and to disrupt the data transmission. An attacker can also block a data channel, thus causing data loss or damage. The routing protocol of a wireless ad hoc network faces a variety of attacks, including internal attacks and external attacks. Internal attacks are mainly launched by the damaged nodes to publish false information to the network. Such attacks are difficult to identify accurately due to the frequent changes of network topology. External attacks often interfere with relay nodes and intercept and steal data transmission to affect the normal operation of a network, as shown in Figure3. In Figure 3, A~F denote the nodes in the network. Two external attacks, sniffing and tampering, are considered during the simulation in this paper.Figure 3
Attack model.The traditional routing protocol has no special security protection, so this kind of attack is prevalent. The introduction of an encryption algorithm can improve the difficulty of decoding data packets, thus playing a defensive role. However, the complex operation of such algorithms will lead to much energy consumption, so it is not effective in practical applications. The risk of these attacks can be reduced by obfuscating the data transmission path.


## 2.3. Establishment of Data Transmission Link

In wireless ad hoc networks, the routing mechanism establishes numerous paths to transmit the packets. Meanwhile, all potential paths are discovered in the routing discovery phase. All the paths between the source node and the destination node are constructed by using the on-demand routing protocol in the routing discovery phase due to the large amount of system overhead generated by the active routing protocol. These paths are selected for data transmission between nodes randomly.Each packet contains a minimum energy measure (min_em) during communication. The min_em of a path is the min_em of all nodes on a path. The source node transmits a routing request message whose min_em is 0 to establish the transmission path between nodes. An intermediate node will compare its min_em to the energy measure threshold of a routing request message when the routing request message is received. And the node will compare its min_em with that of the routing request message if the min_em is no less than the threshold. Otherwise, the routing request message will be terminated. If the min_em of the node is smaller than that of the message, the latter one will be replaced by the former, and the total hops will plus 1. The routing request message is transmitted and the intermediate node will forward it directly if the min_em node is larger than that of the routing request message. Eventually, the paths with different hops will be discovered, as shown in Figure 4.Figure 4
The model of the data transmission link.The different transmission paths will be established betweenS and D when D receives multiple routing request packets. The destination node can select the path by setting the threshold of hops in the actual operation of a network. Then, the min_em of the routing request packet selected by the destination node is attached to the routing response packet and passed back to the source node via the original path. Subsequently, the source node selects the routing with the highest initial probability distribution to transmit the packets.


## 2.4. Markov State Transfer Model

### 2.4.1. Background

The Markov state transfer model can be used as a mathematical model for transitions between series states, and it is a common random method to predict system performance. The Markov state transfer model is based on a probability distribution, which can predict the transitions between various states. Since the number of states is limited and the transitions between different states are based on a certain probability distribution, it can adapt to the time variability of node communication. Besides, the transition probability between different states is independent of the previous phase. The set of all states in the Markov state transfer model is called the state space, i.e.,L=L1,L2,⋯,Ll. O represents the mapping between different states. The routing protocol can execute any O allowed in the state to switch the path from Li to Lj, and the transition probability of this process is pij. The system will send response rLi,Lj,O after the state transition is completed. The transition probability is pjj if the two states are consistent.


### 2.4.2. Probability Analysis

Li represents the transmission path. P is the transition probability matrix. pi,j∈P is the transition probability from Li to Lj, as shown in Figure 5.Figure 5
Markov state transition model.Ai is the initial probability distribution. The transfer probability matrix P of the Markov state transition model can be constructed by setting pi,j. As defined above, the energy measure of path Li is represented by min_em. A path with a maximum min_em is selected as the initial path, so the initial probability distribution Ai of path Li can be determined:
(1)Ai=min_emi∑k=1lmin_emk.The energy of nodes on the path will be consumed, and the energy measure of the path will decrease gradually during the process of data transmission.em is adopted to represent all vectors of a path energy measure:
(2)em=min_em1,min_em2,⋯,min_eml.The calculation ofpi,j under different conditions is shown in (3), where ∑lpi,j=1. And αα≥2 is the performance parameter and mainly used to reduce the path transfer probability. The main reason for setting this parameter is that the probability of moving from a path with a higher energy measure to one with a lower energy measure is relatively low.
(3)pi,j=min_emi−min_emj∑lmin_emi−min_emjα,Li≠Lj,min_emi>min_emj,min_emi−min_emj∑lmin_emi−min_emj,Li≠Lj,min_emi<min_emj,1−∑k∈lpi,k,Li=Lj,Li≠Lk.SinceAi can guarantee energy efficiency, the system can ensure the security and efficiency of a transmission at the same time when switching path randomly according to Ai. The transmission path of the next phase can be determined by Ai′ when the first state transition is completed, where Ai′=Ai×pi,j.


## 2.4.1. Background

The Markov state transfer model can be used as a mathematical model for transitions between series states, and it is a common random method to predict system performance. The Markov state transfer model is based on a probability distribution, which can predict the transitions between various states. Since the number of states is limited and the transitions between different states are based on a certain probability distribution, it can adapt to the time variability of node communication. Besides, the transition probability between different states is independent of the previous phase. The set of all states in the Markov state transfer model is called the state space, i.e.,L=L1,L2,⋯,Ll. O represents the mapping between different states. The routing protocol can execute any O allowed in the state to switch the path from Li to Lj, and the transition probability of this process is pij. The system will send response rLi,Lj,O after the state transition is completed. The transition probability is pjj if the two states are consistent.


## 2.4.2. Probability Analysis

Li represents the transmission path. P is the transition probability matrix. pi,j∈P is the transition probability from Li to Lj, as shown in Figure 5.Figure 5
Markov state transition model.Ai is the initial probability distribution. The transfer probability matrix P of the Markov state transition model can be constructed by setting pi,j. As defined above, the energy measure of path Li is represented by min_em. A path with a maximum min_em is selected as the initial path, so the initial probability distribution Ai of path Li can be determined:
(1)Ai=min_emi∑k=1lmin_emk.The energy of nodes on the path will be consumed, and the energy measure of the path will decrease gradually during the process of data transmission.em is adopted to represent all vectors of a path energy measure:
(2)em=min_em1,min_em2,⋯,min_eml.The calculation ofpi,j under different conditions is shown in (3), where ∑lpi,j=1. And αα≥2 is the performance parameter and mainly used to reduce the path transfer probability. The main reason for setting this parameter is that the probability of moving from a path with a higher energy measure to one with a lower energy measure is relatively low.
(3)pi,j=min_emi−min_emj∑lmin_emi−min_emjα,Li≠Lj,min_emi>min_emj,min_emi−min_emj∑lmin_emi−min_emj,Li≠Lj,min_emi<min_emj,1−∑k∈lpi,k,Li=Lj,Li≠Lk.SinceAi can guarantee energy efficiency, the system can ensure the security and efficiency of a transmission at the same time when switching path randomly according to Ai. The transmission path of the next phase can be determined by Ai′ when the first state transition is completed, where Ai′=Ai×pi,j.


## 3. Markov Model-Based Low-Power and Secure Multihop Routing Mechanism

The secure multihop routing under an energy constraint is very important for ensuring the security of a data transmission. Considering that each routing phase in the ad hoc network contains a large number of potential transmission paths, it is difficult to guarantee the convergence of the routing discovery model with a large amount of computation. To solve this problem, an online numerical iterative method is proposed to calculate the value function, and a convergence environment is established to reduce the computational complexity and obtain the optimal solution.


### 3.1. Markov-Based Routing Model

The characteristics of the Markov state transition model are determined by four objects, namely the state set, behavior set, transition probability, and the feedback function of each phase. The state set isL1,L2,⋯,Ll∈L, where Li denotes the selected transmission path in each routing phase. O represents the behavior set of the Markov model. OL1,OL2,⋯,OLl∈O, and OLi is defined in Definition 1. PLj∣Li,OLi denotes the transition probability matrix of the Markov model, and its definition is shown in (3). ELi,OLi=∑k=1iek,Ok represents feedback function, and ek,Ok denotes the feedback information of node k under Ok, which is determined by the energy model.Definition 1.
O is the mapping of packets switching from one path to another. Selecting the appropriate O can minimize ELi,OLi, which means the energy consumption of a packet transmission can be reduced to the minimum.ELit,OLit is the total transmission energy consumption in time slot t:
(4)Ctr=∑t=1TELit,OLit,Ct=∑r=1trCtr,where Ctr denotes the system overhead in routing phase tr, and Ct represents the total system overhead of the entire communication process. Under OLit, the theoretical minimum system overhead of Lit is
(5)Cmin=minClimT→∞∑t=1TβtELit,OLit,where β∈0,1 denotes a calculation factor, and the specific value is determined by the random state transfer process. The value of β can balance the result quality and the convergence speed. The smaller the value of β is, the faster the converge speed, and the worse the result quality is. Nonnegative terminal energy consumption FLi is generated during network operation. Li is defined as the initial state, and the minimum system overhead that can be achieved under OLi is vtLi. vtLi can be calculated by using the initial state, namely, v0Li=FLi. The random routing process Lit can be treated as a finite state Markov process because the transmission paths of packets change dynamically. State selection depends only on the initial probability distribution if t=1. Equation (3) shows the transition process of different states under the given initial probability distribution when t>1. The system cost function vLi is shown as follows:
(6)vLi=minOLiELit,OLit+β∑LjPLj∣Li,OLivLj,where v∗Li represents the minimum system overhead, and O∗Li denotes the optimal strategy. In addition, the result of (6) is unique since the Markov model is not repeatable under all stable strategies. The amount of calculation is enormous because there are many available paths in each routing phase. To solve this problem, an iterative algorithm is adopted to reduce the computation complexity.


### 3.2. An Iterative Algorithm Based on Stochastic Dynamic Approximation

The functions are iterated by the Bellman optimization principle in this paper, and the optimal solution is obtained. LetR represent the set of all v. The vector graph V: RLi→RLj is defined to calculate any v.
(7)VLiv=minOLiELit,OLit+β∑LjPLj∣Li,OLivLj.For anyv and v′, Vv−Vv′∞≤βv−v′∞ is always workable. This paper defines an iteration cycle as the minimum time interval for all paths to be accessed at least once. A routing phase is divided into several iterative cycles for operation. ℓi represents the time for path Li to be accessed, and vℓ represents the system overhead in ℓ iteration cycle. The iterative algorithm starts from v0, and the two adjacent iterative cycles satisfy
(8)vℓ+1=Vvℓ.The iterative process will eventually converge tov∗, and v∗ is the optimal solution at this time. At the end of cycle ℓ, the function of cycle ℓ+1 will be updated as follows:
(9)vℓ+1Li=vℓLi+λℓminOLiEℓ+1Lit,OLit+λℓminOLiβ∑LjPLjLi,OLivℓLj−vℓLi,where λℓ∈0,1 denotes the calculation metric in cycle ℓ. Subsequently, O is updated as shown in
(10)Oℓ+1=argminVvℓ+1.The iterative process can be summarized as Algorithm1.Algorithm 1: Iteration algorithm.
(1) Begin
(2)Initialization
(3)t=0, ℓ=0
(4)v0←ECterminal, O0←Vv0
/∗ ECterminal is the terminal energy consumption ∗/
(5) BeginL0
(6) activate algorithm
(7)for i≔1
(8)vℓ+1Li=vℓLi+λℓminOLiEℓ+1Lit,OLit+λℓminOLiβ∑LjPLj∣Li,OLivℓLj−vℓLi
(9)argminVvℓ+1=Oℓ+1
(10)if vℓ+1−vℓ<δv then
(11)    stop
(12)else
(13)    back to (8)
(14)end if
(15) End


### 3.3. Algorithm Convergence Analysis

βℓ represents the calculated factor sequence, which meets the following conditions:
(11)∑ℓβℓ=∞,βℓ≥0,∑ℓβℓ2<∞,where Cℓ represents the mathematical expectation of the system overhead, and Pℓ represents the conditional probability.
(12)YℓOLi=EℓLit,OLit+β∑LjPLjLi,OLivℓLj−vℓLi,ρMℓOLi≜YℓOLi−CℓYℓuLi,Aℓ−1≜POℓλℓ−1+1−λℓ−1Ι,Bℓ−1≜POℓ−1λℓ−1+1−λℓ−1Ι,where POℓ and I denote the I×I transmission probability matrix under Oℓ. ρMℓOLi represents the boundary of any ℓ and the calculation factor sequence that satisfies (11). For any set O0,O1,⋯,Om, ρm=βλm>0 is always workable. There is a positive integer m which makes
(13)Am,Am−1,⋯,A1LiI≥ρm,Bm,Bm−1,⋯,B1LiI≥ρm,where 1≤Li≤Ll, and ⋅LiI represents the LiI element in the matrix. e=1,1,⋯,T is a I-dimensional vector and limℓvℓ=v∞ is always workable. Steady-state value satisfies
(14)TIv∞−v∞uILie+v∞=Tv∞.The optimal result isv∗Li=TIv∞−v∞uILi, and the optimal strategy is O∗=argminTv∞. It can be concluded from (13) that state uLi can be obtained from any uLl state through some transition steps, and the transformation results are feasible in most certain cases.


## 3.1. Markov-Based Routing Model

The characteristics of the Markov state transition model are determined by four objects, namely the state set, behavior set, transition probability, and the feedback function of each phase. The state set isL1,L2,⋯,Ll∈L, where Li denotes the selected transmission path in each routing phase. O represents the behavior set of the Markov model. OL1,OL2,⋯,OLl∈O, and OLi is defined in Definition 1. PLj∣Li,OLi denotes the transition probability matrix of the Markov model, and its definition is shown in (3). ELi,OLi=∑k=1iek,Ok represents feedback function, and ek,Ok denotes the feedback information of node k under Ok, which is determined by the energy model.Definition 1.
O is the mapping of packets switching from one path to another. Selecting the appropriate O can minimize ELi,OLi, which means the energy consumption of a packet transmission can be reduced to the minimum.ELit,OLit is the total transmission energy consumption in time slot t:
(4)Ctr=∑t=1TELit,OLit,Ct=∑r=1trCtr,where Ctr denotes the system overhead in routing phase tr, and Ct represents the total system overhead of the entire communication process. Under OLit, the theoretical minimum system overhead of Lit is
(5)Cmin=minClimT→∞∑t=1TβtELit,OLit,where β∈0,1 denotes a calculation factor, and the specific value is determined by the random state transfer process. The value of β can balance the result quality and the convergence speed. The smaller the value of β is, the faster the converge speed, and the worse the result quality is. Nonnegative terminal energy consumption FLi is generated during network operation. Li is defined as the initial state, and the minimum system overhead that can be achieved under OLi is vtLi. vtLi can be calculated by using the initial state, namely, v0Li=FLi. The random routing process Lit can be treated as a finite state Markov process because the transmission paths of packets change dynamically. State selection depends only on the initial probability distribution if t=1. Equation (3) shows the transition process of different states under the given initial probability distribution when t>1. The system cost function vLi is shown as follows:
(6)vLi=minOLiELit,OLit+β∑LjPLj∣Li,OLivLj,where v∗Li represents the minimum system overhead, and O∗Li denotes the optimal strategy. In addition, the result of (6) is unique since the Markov model is not repeatable under all stable strategies. The amount of calculation is enormous because there are many available paths in each routing phase. To solve this problem, an iterative algorithm is adopted to reduce the computation complexity.


## 3.2. An Iterative Algorithm Based on Stochastic Dynamic Approximation

The functions are iterated by the Bellman optimization principle in this paper, and the optimal solution is obtained. LetR represent the set of all v. The vector graph V: RLi→RLj is defined to calculate any v.
(7)VLiv=minOLiELit,OLit+β∑LjPLj∣Li,OLivLj.For anyv and v′, Vv−Vv′∞≤βv−v′∞ is always workable. This paper defines an iteration cycle as the minimum time interval for all paths to be accessed at least once. A routing phase is divided into several iterative cycles for operation. ℓi represents the time for path Li to be accessed, and vℓ represents the system overhead in ℓ iteration cycle. The iterative algorithm starts from v0, and the two adjacent iterative cycles satisfy
(8)vℓ+1=Vvℓ.The iterative process will eventually converge tov∗, and v∗ is the optimal solution at this time. At the end of cycle ℓ, the function of cycle ℓ+1 will be updated as follows:
(9)vℓ+1Li=vℓLi+λℓminOLiEℓ+1Lit,OLit+λℓminOLiβ∑LjPLjLi,OLivℓLj−vℓLi,where λℓ∈0,1 denotes the calculation metric in cycle ℓ. Subsequently, O is updated as shown in
(10)Oℓ+1=argminVvℓ+1.The iterative process can be summarized as Algorithm1.Algorithm 1: Iteration algorithm.
(1) Begin
(2)Initialization
(3)t=0, ℓ=0
(4)v0←ECterminal, O0←Vv0
/∗ ECterminal is the terminal energy consumption ∗/
(5) BeginL0
(6) activate algorithm
(7)for i≔1
(8)vℓ+1Li=vℓLi+λℓminOLiEℓ+1Lit,OLit+λℓminOLiβ∑LjPLj∣Li,OLivℓLj−vℓLi
(9)argminVvℓ+1=Oℓ+1
(10)if vℓ+1−vℓ<δv then
(11)    stop
(12)else
(13)    back to (8)
(14)end if
(15) End


## 3.3. Algorithm Convergence Analysis

βℓ represents the calculated factor sequence, which meets the following conditions:
(11)∑ℓβℓ=∞,βℓ≥0,∑ℓβℓ2<∞,where Cℓ represents the mathematical expectation of the system overhead, and Pℓ represents the conditional probability.
(12)YℓOLi=EℓLit,OLit+β∑LjPLjLi,OLivℓLj−vℓLi,ρMℓOLi≜YℓOLi−CℓYℓuLi,Aℓ−1≜POℓλℓ−1+1−λℓ−1Ι,Bℓ−1≜POℓ−1λℓ−1+1−λℓ−1Ι,where POℓ and I denote the I×I transmission probability matrix under Oℓ. ρMℓOLi represents the boundary of any ℓ and the calculation factor sequence that satisfies (11). For any set O0,O1,⋯,Om, ρm=βλm>0 is always workable. There is a positive integer m which makes
(13)Am,Am−1,⋯,A1LiI≥ρm,Bm,Bm−1,⋯,B1LiI≥ρm,where 1≤Li≤Ll, and ⋅LiI represents the LiI element in the matrix. e=1,1,⋯,T is a I-dimensional vector and limℓvℓ=v∞ is always workable. Steady-state value satisfies
(14)TIv∞−v∞uILie+v∞=Tv∞.The optimal result isv∗Li=TIv∞−v∞uILi, and the optimal strategy is O∗=argminTv∞. It can be concluded from (13) that state uLi can be obtained from any uLl state through some transition steps, and the transformation results are feasible in most certain cases.


## 4. Simulation Results and Performance Evaluation

This section analyzes the performance of the proposed low-power secure routing mechanism in terms of security and energy efficiency.


### 4.1. Simulation Environment

NS-2 is adopted to verify the performance of the proposed low-power secure routing mechanism. The nodes in the network will be randomly deployed in a square area of1000×1000m2 according to the principle of two-dimensional uniform distribution. The MAC layer protocol is IEEE 802.11b, and the transfer agent is UDP. In the simulation process, the source node transmits data at a fixed bit rate, and the packet size is 512 bytes. Compared with AODV, AOMDV, and PAAODV, the performance of the proposed routing protocol (Low-power and Secure Routing Mechanism (LSRM)) is evaluated in terms of security and energy efficiency. The remaining simulation parameters are shown in Table 1.Table 1
Parameters and their values.
Parameter
Value
α
2
Packet number
300
Node number
100
Energy threshold
400 J
Routing phase number
20
State transition period
20 ms
Node communication distance
300 m


### 4.2. Security Simulation

The average packet delivery rate of four routing protocols under a sniffing and tampering attack is shown in Figures6 and 7.Figure 6
The average packet delivery rate under a sniffing attack.Figure 7
The average packet delivery rate under a tampering attack.It can be seen that the average packet delivery rate of LSRM under two attack conditions is higher than that of other algorithms in Figures6 and 7. The main reason is that LSRM can randomly switch between multiple paths according to the energy measure, which ensures the security of data transmission. The node energy on each link will be consumed continuously with the network operation, and the paths for data transmission will be reduced. Therefore, the packet delivery rate shows a downward trend, which also conforms to the fundamental rules of actual network operations.


### 4.3. Transmission Stability Simulation

The packet error rate comparison of four routing protocols under different data packet transmission rates is shown in Figure8.Figure 8
Packet error rate with different packet sending rates.The packet error rate of LSRM increases gradually, while the other three routing algorithms increase sharply with the increase of the packet transmission rate. LSRM can switch the path over time to reduce the probability of the data packet being attacked, which can guarantee the security of data transmission.The information throughput rate of different node moving speeds is compared as shown in Figure9 when the node density is 20. LSRM performs better than the other three routing algorithms in terms of information throughput rate. The main reason is that LSRM can transmit numerous packets through different paths. On the contrary, the source node may only send a few packets in the other three routing algorithms due to the insufficient stability of transmission links. The information throughput rate of four routing protocols will decrease as the nodes move continuously, which is in line with the fundamental rules of actual network operations.Figure 9
Data throughput with different node moving speeds.Figure10 shows the average network delay of four routing protocols at different moving speeds. The average delay of LSRM is significantly lower than that of the other three routing protocols. LSRM establishes a more stable transmission path to reduce the number of routing phases, which can optimize the average network delay. The number of routing phases is enhanced with the augmentation of node moving speed, which leads to the increase of network delay.Figure 10
Average network delay with different node moving speeds.


### 4.4. Energy Efficiency Simulation

The system energy consumption in different routing phases is shown in Figure11. LSRM has a slightly higher system energy consumption in the first six routing phases compared with the other three routing algorithms. The main reason is that LSRM sends a large number of packets during the initial routing phases. However, the total system energy consumption is still lower than the other three routing protocols.Figure 11
System energy consumption of each routing phase.Figure12 shows the load comparison of four routing protocols in different dynamic network environments. LSRM has a slightly higher routing overhead than the other three routing protocols. LSRM selects the path for data transmission randomly. Therefore, LSRM has more transmission control packages, thus resulting in higher routing overhead.Figure 12
The routing overhead with different node moving speeds.Figure13 shows the relationship between the average energy consumption of each packet and the total number of packet transmissions. The average forwarding energy consumption of each packet increases as the amount of packet transmission increases. This is because the buffer time and channel bandwidth required for the packets will also increase when the packets transmitted per second increase. In addition, the average energy consumption is proportional to the node density. The average energy consumption of a single packet in LSRM is lower than that of the other three routing protocols since the transmission path can be selected according to the energy measure randomly.Figure 13
The energy consumption of per packet.Figure14 shows the number of alive nodes versus simulation time with 100 nodes. Compared with AODV and PAAODV, LSRM takes into account the residual energy of each node in the network, rather than just look for the shortest path for information transmission. Therefore, the performance of the proposed algorithm in this paper is better in terms of network load balancing. Moreover, the average energy consumption of a single packet in LSRM is lower than that of the other three routing protocols, so the network lifetime is longer.Figure 14
Number of alive nodes versus time.


## 4.1. Simulation Environment

NS-2 is adopted to verify the performance of the proposed low-power secure routing mechanism. The nodes in the network will be randomly deployed in a square area of1000×1000m2 according to the principle of two-dimensional uniform distribution. The MAC layer protocol is IEEE 802.11b, and the transfer agent is UDP. In the simulation process, the source node transmits data at a fixed bit rate, and the packet size is 512 bytes. Compared with AODV, AOMDV, and PAAODV, the performance of the proposed routing protocol (Low-power and Secure Routing Mechanism (LSRM)) is evaluated in terms of security and energy efficiency. The remaining simulation parameters are shown in Table 1.Table 1
Parameters and their values.
Parameter
Value
α
2
Packet number
300
Node number
100
Energy threshold
400 J
Routing phase number
20
State transition period
20 ms
Node communication distance
300 m


## 4.2. Security Simulation

The average packet delivery rate of four routing protocols under a sniffing and tampering attack is shown in Figures6 and 7.Figure 6
The average packet delivery rate under a sniffing attack.Figure 7
The average packet delivery rate under a tampering attack.It can be seen that the average packet delivery rate of LSRM under two attack conditions is higher than that of other algorithms in Figures6 and 7. The main reason is that LSRM can randomly switch between multiple paths according to the energy measure, which ensures the security of data transmission. The node energy on each link will be consumed continuously with the network operation, and the paths for data transmission will be reduced. Therefore, the packet delivery rate shows a downward trend, which also conforms to the fundamental rules of actual network operations.


## 4.3. Transmission Stability Simulation

The packet error rate comparison of four routing protocols under different data packet transmission rates is shown in Figure8.Figure 8
Packet error rate with different packet sending rates.The packet error rate of LSRM increases gradually, while the other three routing algorithms increase sharply with the increase of the packet transmission rate. LSRM can switch the path over time to reduce the probability of the data packet being attacked, which can guarantee the security of data transmission.The information throughput rate of different node moving speeds is compared as shown in Figure9 when the node density is 20. LSRM performs better than the other three routing algorithms in terms of information throughput rate. The main reason is that LSRM can transmit numerous packets through different paths. On the contrary, the source node may only send a few packets in the other three routing algorithms due to the insufficient stability of transmission links. The information throughput rate of four routing protocols will decrease as the nodes move continuously, which is in line with the fundamental rules of actual network operations.Figure 9
Data throughput with different node moving speeds.Figure10 shows the average network delay of four routing protocols at different moving speeds. The average delay of LSRM is significantly lower than that of the other three routing protocols. LSRM establishes a more stable transmission path to reduce the number of routing phases, which can optimize the average network delay. The number of routing phases is enhanced with the augmentation of node moving speed, which leads to the increase of network delay.Figure 10
Average network delay with different node moving speeds.


## 4.4. Energy Efficiency Simulation

The system energy consumption in different routing phases is shown in Figure11. LSRM has a slightly higher system energy consumption in the first six routing phases compared with the other three routing algorithms. The main reason is that LSRM sends a large number of packets during the initial routing phases. However, the total system energy consumption is still lower than the other three routing protocols.Figure 11
System energy consumption of each routing phase.Figure12 shows the load comparison of four routing protocols in different dynamic network environments. LSRM has a slightly higher routing overhead than the other three routing protocols. LSRM selects the path for data transmission randomly. Therefore, LSRM has more transmission control packages, thus resulting in higher routing overhead.Figure 12
The routing overhead with different node moving speeds.Figure13 shows the relationship between the average energy consumption of each packet and the total number of packet transmissions. The average forwarding energy consumption of each packet increases as the amount of packet transmission increases. This is because the buffer time and channel bandwidth required for the packets will also increase when the packets transmitted per second increase. In addition, the average energy consumption is proportional to the node density. The average energy consumption of a single packet in LSRM is lower than that of the other three routing protocols since the transmission path can be selected according to the energy measure randomly.Figure 13
The energy consumption of per packet.Figure14 shows the number of alive nodes versus simulation time with 100 nodes. Compared with AODV and PAAODV, LSRM takes into account the residual energy of each node in the network, rather than just look for the shortest path for information transmission. Therefore, the performance of the proposed algorithm in this paper is better in terms of network load balancing. Moreover, the average energy consumption of a single packet in LSRM is lower than that of the other three routing protocols, so the network lifetime is longer.Figure 14
Number of alive nodes versus time.


## 5. Conclusion

The wireless ad hoc network is an important component of modern mobile communication systems. However, network performance is affected seriously due to the breakage of the data link and frequent changes of the network topology. Therefore, a low-power and secure multihop routing mechanism is proposed in this paper. The energy measure of the data transmission link is taken as an important parameter for the mathematical model. The mathematical model is constructed, and the optimal solution is obtained by using the iterative algorithm. The simulation results show that the routing protocol proposed in this paper can distribute the network load to each path evenly and improve the data transmission. In addition, the routing protocol can effectively resist packet interception, routing hijacking, and interference attacks. Future research will propose a novel solution to resist the attack from internal malicious nodes, which can guarantee the security and effectiveness of data transmission in the network. Meanwhile, the iterative algorithm will be optimized to reduce the computational overhead in the network.



---

*Source: 6578406-2019-10-07.xml*