# An Aggregate Signature Based Trust Routing for Data Gathering in Sensor Networks

Authors: Jiawei Tang; Anfeng Liu; Ming Zhao; Tian Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

An Aggregate Signature based Trust Routing (ASTR) scheme is proposed to guarantee safe data collection in WSNs. In ASTR scheme, firstly, the aggregate signature approach is used to aggregate data and keep data integrity. What is more important, a light aggregate signature based detour routing scheme is proposed to send abstract information which includes the data sending time and ID of data, nodes’ ID to the sink over different paths which can verify whether the data reaches the sink safely. In addition, the trust of a path is evaluated according to the success rate of the path. The trust of paths susceptible to frequent attack will be lowered and the path with high trust will be selected for data routing to avoid data gathering through low trust path and thereby increase the success rate of data gathering. Our comprehensive performance analysis has shown that, the ASTR scheme is able to effectively ensure an increase in success rate of data transmission by 23.23%, reduce the data amount loaded by the node by 53.59%, reduce the redundant data by 41.70%.


---

## Body

## 1. Introduction

With a large number of sensing devices’ connection to Internet of Everything (IoE) [1, 2], our life has become favorably convenient. As one of the most important parts for IoT, the wireless sensor networks (WSNs) are increasingly applied in various aspects of industry [3–6], environment monitoring [7], life [8, 9], and medical health monitoring [10]. With the emergence of edge computing [11], the network architecture is also rapidly developing in computing mode from the cloud computing [11, 12] of network center to edge computing [13], where the sensor network plays an important role [14–16]. However, preservation of information and sensitive data is one of the biggest challenges in sensor networks [17–19]. Due to the high costs, the hardware of sensor nodes is relatively simple and is often unattended in hostile environment, hence prone to different kinds of attacks [20–22]. According to the statistics, there are over 30 kinds of attacks against the sensor network [21, 23], including black attack, clone attack, selective forwarding attack, and false data injection attack [20–23]. It is necessary to provide solid as well as evident solutions as countermeasures against threats in sensor networks; otherwise the application of sensor networks will be hindered [20–23]. For example, black hole attack [23] is such an attack behavior which can drop all the data transferred through the black holes, and the selective forwarding attack (SFA) [20, 24] can intelligently drop some packets to damage network which is difficult to detect and defense such attack [23]. The false data injection attack produces much false data to consume the precious energy of the sensor network, which will cause the advanced death of network exception [21, 23]. Therefore, it is a challenge issue to evade the attack scope of malicious node and ensure the node produces safe and effective data which can reach the sink as verified [1, 21].This paper mainly studies how to defend against the attacks that adversely affect the data transmission and data integrity of WSNs. Generally speaking, this type of attack behaviors has the following characteristics: (1)Damaging the Data Integrity. Compromised node (CN) [20, 21] attack belongs to this type of attack behaviors: the adversary physically compromises a subset of nodes to eavesdrop information. In this way, the compromised node is able to forge false data and launch a false data injection attack or the malicious nodes are able to forge the signature of other nodes and send a large amount of false data or even tamper data. (2)Damaging the Data Security. This means the malicious nodes are able to impede the safe routing of data so that the data cannot reach the destination [23]. For example, black hole attack: it can drop all data through the black node; in comparison, selective forwarding attack is more complex and can intelligently drop some selected key data, which not only endangers the network but also makes the attack behavior difficult to detect. Another one is denial of service (DOS) attack [23] which refers to the following: the adversary interferes with the normal operation of the network by actively disrupting, changing, or even paralyzing the functionality of a subset of nodes. The common consequences of this type of attacks are as follows: areas within which the adversary can either passively intercept or actively block information delivery [23].Some researches have been conducted on defense against malicious nodes. Among them, some were conducted against a single type of attack behavior; for example, the literature [23] proposed the multibranch routing scheme for defense against selective forwarding attack. Some other researches were not conducted on the safety security strategy against a certain attack; for example, the traceback strategy proposed in literature [22] belongs to the defense attack strategies. In traceback strategy, the IDs of pass-through routing nodes are added to the data packet, so when an attack occurs, the attack path will be reconstructed, which helps the system obtain the location of attack source and take measures to clear the malicious node. However, the past researches have a prominent shortcoming: they only considered the circumstance where the data packets produced by the source node are directly routed to the sink, but the wireless sensor network has a typical difference with other networks; that is, its node energy is limited, and hence it is an important research issue to minimize its energy consumption. Data aggregation is an effective method to reduce the energy consumption of WSNs [1] and, due to the correlation between the data packets produced by different nodes of WSNs in time and space, if data packets produced by nodes with approximate locations and time are sent to the sink upon data aggregation, the data amount will be significantly reduced to save the energy consumption of network [1]. In practice, the data aggregation rate may reach over 70%, so the load of data by nodes is only 30%, that is, less than 1/3 of the original after the data aggregation. In some special data aggregation functions, such as the data aggregations to obtain max, min, and avg, only one data packet is output after the data aggregation of n data packets and the data aggregation rate is very high, greatly improving the performance of WSNs [1]. The data aggregation and collection are significant research issues for cloud computing and fog computing which have been studied by many researchers [25, 26].Although the data aggregation plays an important role in WSNs, it fuses multiple data packets into one, so the issues caused by attack against the fused data packet are more complex than those in the past researches [1]. Specifically speaking, the following challenges will be met: (1) Integrity issue of data packet: malicious nodes may produce much false data, so if no proper measure is taken, it will be difficult to determine whether false data exist after the data aggregation and which are source nodes that produce the false data. (2) The fact that an attack will bring more serious loss to the network: the data packet formed upon data aggregation contains more information, so an attack may cause more serious consequence. (3) Routing safety issue: when some attacks, such as black hole attack and selective forwarding attack, occur, the data packet will be attacked and dropped before reaching the sink, but the sink cannot determine whether the network has been attacked or any data packet has been lost, which is considered the most dangerous circumstance. With so many challenges existing in the data aggregation network and to the best of our knowledge, seldom researches have been made on attack defense of WSNs in data aggregation. In this paper, an aggregate signature based trust routing (ASTR) scheme is proposed to guarantee safe data collection for data aggregation in WSNs. The main contributions of this paper are as follows.(1) An aggregate signature based trust routing (ASTR) scheme is proposed to guarantee data security and data integrity of data collection in WSNs. In ASTR scheme, each node signatures its data and abstract information (i.e., the data sending time and ID of data, node ID) and sends them to aggregator, and the aggregator compresses those data signatures into a short one packet called data packet and sends it to sink overM∣M≥1 different paths. In this way, the sink can verify the data aggregate signature is valid if and only if every single signature used in the aggregation is valid. So the data integrity can be guaranteed. On the other hand, the aggregator also compresses those abstract information signatures into another short one packet called abstract packet and sends it over another N∣N≥1 detour routing to sink, which can verify whether the data has reached the sink safely. We conducted a series of analysis in theory and determined the required values of M,N to guarantee the data can reach the sink safely, so the safe routing of data to the sink can be guaranteed. The past researches often considered only one aspect, that is, data security (probability for data to reach the sink safely) or data integrity. However, the ASTR scheme proposed by this paper can ensure both the data integrity and data security, making the research more meaningful.(2) The ASTR scheme adopts the trust-based routing method to further improve the success rate of routing. Adopting the strategy of sendingM data routings and N abstract routings (called R(M,N) routing method) is able to improve the success rate of routing but at higher costs in energy consumption. Hence, the paper further proposes a method to select high trust routing based on the trust of paths, which is able to reduce the number of data and abstracts needed to ensure a high success rate of routing or is able to improve the success rate of routing while consuming the same energy and further optimize the system performance.(3) Through our extensive theoretical analysis and simulation study, we demonstrate that, for TSTR scheme which adopts theR(M,N) routing method, both data integrity and data security can be achieved simultaneously. For the network with a packet loss ratio of 10%, the probability for data to reach the sink safely is raised by 23.23%. If a routing path with high trust is selected with the trust-based method, the success rate of routing will increase by at least 3% without additional system cost. If the success rate of routing is guaranteed equal to that of the R(M,N) routing method, the data amount loaded by the nodes will be reduced by 53.95%, which demonstrates the outstanding performance of ASTR scheme.The rest of our paper is organized as follows: In Section2, a literature review of the research related to this work is presented. Then the system model and problem statement are described in Section 3. In Section 4, we proposed an efficient aggregate signature based trust routing (ASTR) scheme. The performance analysis of the ASTR scheme is provided in Section 5. Finally, Section 6 provides the conclusion.


## 2. Related Work

Data security and data integrity are the two most important concerns in data gathering of WSNs and also the objects of this research. Therefore, this section mainly discusses some research work related to data security and data integrity. At first, it introduces the existing researches on data security, which mainly focuses on the method and strategy to guarantee the safe routing of data to the sink. The functions based on this strategy can be classified into the following.(1) Guaranteeing the safe transmission of data to the sink no matter whether an attack exists in the network: the early researches did not detect the existence of attacks (such as black, DOS, and SFA attack) and, instead, adopted a multipath routing method to reliably guarantee the data can reach the sink [21, 23]. This strategy has an advantage of wide applicability in effectively overcoming similar attack behavior that impedes the transmission of data to the sink [21]. However, the strategy cannot detect the existence of an attack or identify malicious nodes [15].Karlof and Wagner [21] first suggest that multipath routing can be used to counter these types of attacks. Messages routed over k paths whose nodes are completely disjoint are completely protected against such selective forwarding attacks or black hole attacks involving at most k compromised nodes and still offer some probabilistic protection when over k nodes are compromised. In literature [23], a SEDR scheme is proposed to defense black hole attack. In SEDR scheme, a data packet is divided into m shares which are sent to the sink over different nonintersected paths. Even if some shares are dropped by attacker during routing, the sink can restore the whole data packet with only k shares. The attacker cannot get the contents of data packet from less than k shares. The shortcoming of these researches lies in the following: (a) it can neither detect the existence of attacker in the network nor determine the location of malicious node [22]; (b) it consumes much energy, especially when the number of paths is large [21].(2) Being able to detect the existence of attacker but not identify malicious nodes: this type of strategy has a main point: detect whether attacks exist during the data transmission and once you find the attacks, send an alarm message to inform the system of the existence of attacks. However, the strategy is not or weakly able to identify malicious nodes.Sun et al. [24] have proposed a multidataflow topologies (MDT) method to countermeasure such attacks. In MDT, the sensor nodes are divided into two-dataflow topologies, and both dataflow topologies can cover the whole network; therefore it is sufficient to control the entire network that the sink only gets one report from either topology. Through two topologies the sink can defend against similar attacks. If a malicious node exists in one topology, the sink can still obtain packets from other topologies. The shortcoming of this method lies in the following: too weak to resist the attacks and both dataflow topologies can be attacked when the number of attackers is large, which will cause a failure of the strategy. In addition, the method will pay high prices in energy consumption and so forth.(3) Being able to detect the existence of attacker and identify malicious nodes: the type of strategies has a main point: firstly detect whether an attacker exists in the network and if any attacker is detected, use a certain mechanism to identify malicious nodes and expel the malicious nodes from the data routing, eliminating their adverse effects.Xiao et al. [20] have proposed a checkpoint-based multihop acknowledgement (CHEMAS) scheme for identifying suspect nodes in selective forwarding attack. In CHEMAS scheme, some intermediate nodes over a forwarding path are randomly selected as checkpoint nodes which are responsible for generating acknowledgements for each packet received. Each intermediate node in a forwarding path has the potential to detect abnormal packet loss and identify suspect nodes if it does not receive enough acknowledgements from the downstream checkpoint nodes.Besides, the attack detecting strategies can be classified into distributed detection strategies and centralized detection strategies based on their execution characteristics. In distributed detection strategy, each source node and participant node of the data routing or neighbor node monitors and detects the existence of attack. Generally the source node summarizes the detection results and reports them to the system (or sink). In centralized detection strategy, a central information processing center (such as sink) is in place and monitoring information from all nodes is reported to and processed by the information processing center. Generally speaking, the distributed strategy has robust performance and the centralized strategy has a shortcoming of single-point failure.The above classification is only one of the commonly used methods. Actually, different attack detecting strategies usually have multiple characteristics; for example, a distributed strategy may be able to identify malicious nodes; some centralized strategies may have only detection function.Another group of researches were conducted not against specific attack behaviors but on a widely applicable method to defend against attacks. Among them, traceback is a common method different from the above ones that adopt active defense against attacks. In the abovementioned methods, the strategies usually aim to design some methods to avoid attacks to nodes and send data packets to the sink successfully. In comparison, the main point of traceback method lies not in how to avoid attack but in designing a method to mark the origin of source nodes and routing paths, which is able to determine the attack source once an attack occurs and then take measures to eliminate the attack source to ensure the network security. The mechanism can be described as monitoring in advance and imposing punishment after an attack event occurs [22]. This type of strategies mainly adopts two methods, namely, mark and logging. The mark method adds the node ID during the routing of data packet to the sink and determines the location of malicious node with a high probability when the network is attacked. The logging method is mainly adopted based on the mark method. In the mark method, as the data packet is routed towards the sink, an increasing number of node IDs are added to the data packet, so the data packet is becoming longer, which increases the energy consumption of sensor nodes. When a node receives the data packet, the logging method checks the length of ID attached to the data packet. When the length exceeds a certain value, the ID information will be saved on the node to reduce the energy consumption of nodes. Therefore, if more information is marked in the traceback method, the sink will own more information when the network is attacked, determine the location of malicious nodes, and remove them more easily. However, when more information is marked and more IDs are attached to the data packet, the nodes will consume more energy. The main point of research on traceback method lies in how to minimize the number of marks and improve the accuracy of determining the location of source node. To achieve this target, the probability mark method is usually adopted. For details about these researches, see literature [22].The preceding paragraphs mainly discuss the existing researches on data security with the main purpose of effectively routing the data to the sink. Another important work is how to ensure the data integrity, so the next paragraph introduces some researches on this topic.The main method to ensure data integrity is the digital signature technology which ensures the source of data packet can be verified. This type of methods is widely used in WSNs [1]. The main ideas of these methods are as follows: a source node needs to provide a digital signature to each of the data when sending data packets, so the sink can determine whether the data is sent by the real node, which will prevent the illegal node from sending false data. For details of these researches, see [27], where the authors proposed an effective and safe method to defend against the false data injection attack. However, the digital signature method has shortcomings: the digital signature has a requirement on hardware and increases the length of data packet, which affects the energy consumption, delay, and communication bandwidth. Therefore, how to effectively ensure the data integrity and data security of WSNs remains an important challenge issue.


## 3. System Model and Problem Statement

### 3.1. System Model

The network model in this paper is a typical planar periodic data collection wireless sensor network similar to [28–33]. Its system model is as follows.(1)n homogeneous sensor nodes are randomly deployed in a two-dimensional planar network with a radius of R, a sink is at the center, and the node density is ρ. The node communication radius is r. The data sensed by the network is periodic data collection type. For example, the sensor network is a farm monitoring the information, such as temperature and moisture within an area. Each node produces one data packet in a sensor period and sends it to the sink via multihop relay [34, 35] and the data vector collected in a period is X=[x1,x2,…,xn]. The network lifetime is defined as the number of data collection periods when the first node dies [31, 32, 35]. The communication is considered to be perfect, so the lost packets are considered dropped as a result of attack. Although the real communication channel is not perfect, the sender may adopt various methods, such as sen-wait ARQ protocol to ensure the successful transmission of packets to the receiver. The ASTR scheme can also be used in networks with imperfect communication channels under condition that the system parameters have been modified.(2) Data aggregation model: it adopts data aggregate method for data collection to form a typical data aggregation model similar to [1]. In such data aggregation mode, when the network is collecting data, a set of aggregators are selected and other nodes are called simply nodes. Each simple node belongs to one of the aggregators in which that simple node can send its data to that aggregator directly. The node si is said to be the member of aggregator sj if the node si belongs to aggregator sj. The aggregator node receives the data of all member nodes and aggregates them into one data packet and then multihop routes the data packet to the sink with the shortest routing method. Di represents the original data packet produced by node si and S(si,sj) represents the aggregation result of data of node si and node sj and Ti represents the final aggregation result of the data of all input nodes and node si.When aggregatorsi receives the data packet sent by member node j, it aggregates the data packet Dj sent by node j and the current data packet of aggregator si (original data packet Di of aggregator si or the intermediate aggregation result Si of the data of aggregator si and its member nodes) with the following formula:(1)Tsi,sj=max⁡Si,Dj+1-ci,jmin⁡Si,Dj,where ci,j is the correlation coefficient between nodes si and sj [4, 15]. A larger ci,j indicates a higher correlation between the data of nodes and a smaller length of data packet formed after the data aggregation.


### 3.2. Security Model

The attacker is considered to have a strong intelligence [20, 22, 23]. It is actually a malicious node or a node that obtains the legal status through compromising a small portion of sensor nodes and then drops some data packets at a certain probability (if the drop probability is 1, then it is black hole attacker; others it is likely to be selective forwarding attacker or DOS attacker), the aim is to try not to expose themselves, and to make the greatest harm to the network. Those attackers can also forge real nodes to launch various attacks, such as false data injection attack. At the same time, the attackers can also collude to launch attacks. In this paper, we assume that the proportion of malicious nodes is small, for example, smaller than ϱ, most nodes in the network are normal nodes [23]. It is obvious that if most nodes in a network are malicious nodes, the network safety cannot be guaranteed.


### 3.3. Energy Consumption Model

In this paper, we adopt the topical energy consumption model in [31, 33, 35], where the transmission energy consumption, ωt, follows (2) and energy consumption, ωr, for receiving follows (3):(2)ωt,1d=lEelec+lεfsd2ifd<d0,ωt,2d=lEelec+lεampd4ifd≧d0,(3)ωr=lEelec,where Eelec represents transmitting circuit loss. Both the free space (d2 power loss) and the multipath fading (d4 power loss) channel models are used. If the transmission distance is less than the threshold d0, the power amplifier loss is based on free-space model; if the transmission distance is larger than or equal to the threshold d0, respectively, the multipath attenuation model is used. εfs and εamp are the energy required by power amplification in the two models.


### 3.4. Problem Statement

The main goal of this paper is to design a data gathering scheme for WSNs that guarantees the data integrity and data security and improves network energy utilization while ensuring long network lifetime. It can be expressed as follows.(1) Data Integrity. It is assurance to the recipient that the data came from the expected sender and has not been altered in transit [1], although the data is sent to the sink after data aggregation and multihop routed.(2) Maximizing the Probability of Successively Routing the Data and Abstract to the Sink. The probability of successively routing data packets to the sink can be defined as the ratio between the number of data packets received by the sink and the total number of data packets sent by the network. The maximum data routing success rate can be computed as follows: (4)max⁡PD=max⁡DsDt,where Dt represents the total number of data packets sent in the network and Ds represents the number of data packets successively received by the sink.Besides, abstract information reaching the sink also has positive effect on the network safety. It can indicate whether the linked data has been sent. If the sink receives the abstract information but fails to receive the linked data packet, it will recognize that the data packet has been attacked and so not received. Therefore, the ASTR scheme will also improve the success rate for abstract information to reach the sink:(5)max⁡PA=max⁡AsAt,where At represents the total amount of abstract information sent in the network and As represents the amount of abstract information received by the sink.(3) Maximizing Energy Utilization. Energy utilization is the ratio of the total energy consumed by the network to the total initial energy of the network while the network dies, as shown in (6)max⁡Ru=max⁡∑i=1nϢi∑i=1nEinii,where i is the ith node in the network, n is the total number of nodes in the network, Ϣi represents the energy consumption of ni, and Einii represents the initial energy of ni, which is given in Table 1. The maximization of network energy utilization will improve the effective use of network energy, so that the ratio of energy consumption to the initial energy in the network is largest.Table 1
Network parameters.
Symbol
Description
Value
d
0
Threshold distance (m)
87
r
s
Sensing range (m)
15
E
e
l
e
c
Transmitting circuit loss (nJ/bit)
50
e
f
s
Power amplification for the free space (pJ/bit/m2)
10
e
a
m
p
Power amplification for the multipath fading (pJ/bit/m4)
0.0013
E
i
n
i
t
Initial energy (J)
0.5(4) Maximizing Network Lifetime. Network lifetime is defined as the death time of the first node in the network [31, 34, 35]. Considering that the energy consumption of the ith node in the network is Ϣi, its initial energy is Einii, and there are n nodes in the network. To maximize the lifetime of the whole network, the network lifetime of the first node to die in the network should be maximized. Therefore, (7) can be obtained:(7)max⁡L=max⁡min1≤i≤n⁡EiniiϢi.In summary, the research objectives are as follows:(8)max⁡PD=max⁡DsDt,max⁡PA=max⁡AsAt,max⁡Ru=max⁡∑i=1nϢi∑i=1nEinii,max⁡L=max⁡min1≤i≤n⁡EiniiϢi,s.t.  data  is  integrity.


## 3.1. System Model

The network model in this paper is a typical planar periodic data collection wireless sensor network similar to [28–33]. Its system model is as follows.(1)n homogeneous sensor nodes are randomly deployed in a two-dimensional planar network with a radius of R, a sink is at the center, and the node density is ρ. The node communication radius is r. The data sensed by the network is periodic data collection type. For example, the sensor network is a farm monitoring the information, such as temperature and moisture within an area. Each node produces one data packet in a sensor period and sends it to the sink via multihop relay [34, 35] and the data vector collected in a period is X=[x1,x2,…,xn]. The network lifetime is defined as the number of data collection periods when the first node dies [31, 32, 35]. The communication is considered to be perfect, so the lost packets are considered dropped as a result of attack. Although the real communication channel is not perfect, the sender may adopt various methods, such as sen-wait ARQ protocol to ensure the successful transmission of packets to the receiver. The ASTR scheme can also be used in networks with imperfect communication channels under condition that the system parameters have been modified.(2) Data aggregation model: it adopts data aggregate method for data collection to form a typical data aggregation model similar to [1]. In such data aggregation mode, when the network is collecting data, a set of aggregators are selected and other nodes are called simply nodes. Each simple node belongs to one of the aggregators in which that simple node can send its data to that aggregator directly. The node si is said to be the member of aggregator sj if the node si belongs to aggregator sj. The aggregator node receives the data of all member nodes and aggregates them into one data packet and then multihop routes the data packet to the sink with the shortest routing method. Di represents the original data packet produced by node si and S(si,sj) represents the aggregation result of data of node si and node sj and Ti represents the final aggregation result of the data of all input nodes and node si.When aggregatorsi receives the data packet sent by member node j, it aggregates the data packet Dj sent by node j and the current data packet of aggregator si (original data packet Di of aggregator si or the intermediate aggregation result Si of the data of aggregator si and its member nodes) with the following formula:(1)Tsi,sj=max⁡Si,Dj+1-ci,jmin⁡Si,Dj,where ci,j is the correlation coefficient between nodes si and sj [4, 15]. A larger ci,j indicates a higher correlation between the data of nodes and a smaller length of data packet formed after the data aggregation.


## 3.2. Security Model

The attacker is considered to have a strong intelligence [20, 22, 23]. It is actually a malicious node or a node that obtains the legal status through compromising a small portion of sensor nodes and then drops some data packets at a certain probability (if the drop probability is 1, then it is black hole attacker; others it is likely to be selective forwarding attacker or DOS attacker), the aim is to try not to expose themselves, and to make the greatest harm to the network. Those attackers can also forge real nodes to launch various attacks, such as false data injection attack. At the same time, the attackers can also collude to launch attacks. In this paper, we assume that the proportion of malicious nodes is small, for example, smaller than ϱ, most nodes in the network are normal nodes [23]. It is obvious that if most nodes in a network are malicious nodes, the network safety cannot be guaranteed.


## 3.3. Energy Consumption Model

In this paper, we adopt the topical energy consumption model in [31, 33, 35], where the transmission energy consumption, ωt, follows (2) and energy consumption, ωr, for receiving follows (3):(2)ωt,1d=lEelec+lεfsd2ifd<d0,ωt,2d=lEelec+lεampd4ifd≧d0,(3)ωr=lEelec,where Eelec represents transmitting circuit loss. Both the free space (d2 power loss) and the multipath fading (d4 power loss) channel models are used. If the transmission distance is less than the threshold d0, the power amplifier loss is based on free-space model; if the transmission distance is larger than or equal to the threshold d0, respectively, the multipath attenuation model is used. εfs and εamp are the energy required by power amplification in the two models.


## 3.4. Problem Statement

The main goal of this paper is to design a data gathering scheme for WSNs that guarantees the data integrity and data security and improves network energy utilization while ensuring long network lifetime. It can be expressed as follows.(1) Data Integrity. It is assurance to the recipient that the data came from the expected sender and has not been altered in transit [1], although the data is sent to the sink after data aggregation and multihop routed.(2) Maximizing the Probability of Successively Routing the Data and Abstract to the Sink. The probability of successively routing data packets to the sink can be defined as the ratio between the number of data packets received by the sink and the total number of data packets sent by the network. The maximum data routing success rate can be computed as follows: (4)max⁡PD=max⁡DsDt,where Dt represents the total number of data packets sent in the network and Ds represents the number of data packets successively received by the sink.Besides, abstract information reaching the sink also has positive effect on the network safety. It can indicate whether the linked data has been sent. If the sink receives the abstract information but fails to receive the linked data packet, it will recognize that the data packet has been attacked and so not received. Therefore, the ASTR scheme will also improve the success rate for abstract information to reach the sink:(5)max⁡PA=max⁡AsAt,where At represents the total amount of abstract information sent in the network and As represents the amount of abstract information received by the sink.(3) Maximizing Energy Utilization. Energy utilization is the ratio of the total energy consumed by the network to the total initial energy of the network while the network dies, as shown in (6)max⁡Ru=max⁡∑i=1nϢi∑i=1nEinii,where i is the ith node in the network, n is the total number of nodes in the network, Ϣi represents the energy consumption of ni, and Einii represents the initial energy of ni, which is given in Table 1. The maximization of network energy utilization will improve the effective use of network energy, so that the ratio of energy consumption to the initial energy in the network is largest.Table 1
Network parameters.
Symbol
Description
Value
d
0
Threshold distance (m)
87
r
s
Sensing range (m)
15
E
e
l
e
c
Transmitting circuit loss (nJ/bit)
50
e
f
s
Power amplification for the free space (pJ/bit/m2)
10
e
a
m
p
Power amplification for the multipath fading (pJ/bit/m4)
0.0013
E
i
n
i
t
Initial energy (J)
0.5(4) Maximizing Network Lifetime. Network lifetime is defined as the death time of the first node in the network [31, 34, 35]. Considering that the energy consumption of the ith node in the network is Ϣi, its initial energy is Einii, and there are n nodes in the network. To maximize the lifetime of the whole network, the network lifetime of the first node to die in the network should be maximized. Therefore, (7) can be obtained:(7)max⁡L=max⁡min1≤i≤n⁡EiniiϢi.In summary, the research objectives are as follows:(8)max⁡PD=max⁡DsDt,max⁡PA=max⁡AsAt,max⁡Ru=max⁡∑i=1nϢi∑i=1nEinii,max⁡L=max⁡min1≤i≤n⁡EiniiϢi,s.t.  data  is  integrity.


## 4. The ASTR Scheme

### 4.1. The Research Motivation of ASTR Scheme

This section discusses the research motivation of ASTR scheme. Firstly, the energy consumption of the network data collection shows that when the network contains no attackers, the energy consumption is as shown in Figure1 (M in the figure represents that the same data packets are sent for M times, the same below). Figure 1 shows that all data in the network can successively reach the sink because no attackers exist. Therefore, the energy consumption of nodes close to the sink area is very high. However, if attackers exist, the attack behaviors of attackers will cause a certain proportion of data packets to be attacked during the routing, dropped, and not able reach the sink. In this case, the number of data packets reaching the sink is smaller than that number in network without attackers, so its energy consumption decreases. It should be noted that the decrease of energy consumption is caused by the reduction of data packets reaching the sink as a result of attack instead of improvement in network performance. This is not a good condition because the idealistic effect for guaranteeing data security is to ensure all data packets in the network can reach the sink and the highest energy consumption is the same as the network that is not attacked. One of the methods to improve the reach rate of data packets is to send the same data for M times over different paths, which is able to significantly raise the reach rate of data. As shown in Figure 1, assuming the probability of successively sending data packets under attack p=0.90, the reach rate is only 0.90 for packets routed by one hop; if the times of sending the same data packets M=2, the one-hop reach rate is 99%, apparently higher than 0.90.Figure 1
Data loaded by nodes under different data collection strategies.This method is actually the multipath routing (MPR) scheme described above. It is direct and effective and so widely researched. However, the shortcomings of the method are rarely researched. Figure1 shows that when M=2 and p=0.90, the actual number of data reaching the sink has exceeded the number of data when no data packet is lost. However, the effective reach rate of data packets is only 55%. It demonstrates that when this method is used, a large amount of repetitive data packets will reach the sink, but some data packets fail to reach the sink. The repetitive data packets (redundant data packets) reaching the sink are useless to improve the reach rate of data packets but increase the energy consumption of the network and shorten the network lifetime.If we can reduce the redundant data reaching the sink and maintain the success rate for data packets to reach the sink, the network lifetime can be extended and the reach rate of data can be ensured at the same time. Based on the above ideas, this paper proposed the ASTR scheme which sends the light abstract information join data packets to improve the network security and energy efficiency. Instead of simply sendingM data packets, this method sends N abstracts (containing the information such as node ID, time, and data packet ID) while it sends M data (relatively small and generally M=1), which is known as R(M,N) routing method. If the message received by the sink contains no data packets, the sink will notify the node to send (M+N) messages again until it receives the data packets or the number of sending times reaches the maximum value k. Compared with the past strategies, the RM,N data collection method with maximum value k can effectively reduce the energy consumption of the network. This is because of the following: if M=1 in the R(M,N) routing method, once the sink receives the data packets, the subsequent sending actions will be stopped, so the sink cannot receive repetitive data packets. As a result, the sink will receive only redundant abstracts but no redundant data packets with this method. Abstracts are lightweight packets with a length of 1/10 or 1/100 of the length of data packets; hence, sending lightweight abstracts instead of heavy data packets is conducive to reducing energy consumption.Table2 compares the data amount sent by the node 5 hops from the sink in R(M,N) routing strategy and multipath routing strategy of sending data the same packets for M times while ensuring the same reach rate of data packets. The first line of Table 2 represents the data in M multipath routing strategy and (M,data,sp) in the first line represent the number of repeatedly sent data packets, data amount sent by nodes, and the proportion of data received by the receiving nodes. For example, (2, 200, and 0.83) represent the following: the number of repeatedly sent data packets: M=2, data amount sent by the sender = 200 bits, and the proportion of data received by the receiver = 0.83. Other lines represent the parameters of the R(M,N) strategy, where M = 1 and k represents the times of repetitive sending. Table 2 shows that when M is 2 in MPR scheme and the R(M,N) routing strategy is used, the data amount loaded by nodes is only 70% of the data amount in M multipath routing strategy. As M increases, the R(M,N) routing strategy presents better performance. When M = 5, the data amount loaded by nodes is only 50% of that in M multipath routing strategy. The R(M,N) routing strategy proposed in this paper has prominent advantages.Table 2
Comparison of data amount loaded by nodes in different strategies.
(M, data, sp)  (2, 200, 0.83)
(M, data, sp)  (3, 300, 0.93)
(M, data, sp) (4, 400, 0.97)
(M, data, sp)  (5, 500, 0.99)
k = 3
131.82 (N = 1)
155.81 (N = 2)
k = 4
142.12 (N = 1)
171.56 (N = 2)
k = 5
146.51 (N = 1)
179.08 (N = 2)
223.37 (N = 4)
k = 6
148.31 (N = 1)
182.52 (N = 2)
208.03 (N = 3)
247.26 (N = 5)
k = 7
149.02 (N = 1)
184.06 (N = 2)
210.17 (N = 3)
231.35 (N = 4)The second research motivation: in the preceding research motivation, the message is set free after being sent. It is obvious that selecting a trustable routing path for every hop during the routing will effectively improve the success rate of routing and reduce the sending times of data packets. In ASTR scheme, a data packet will not be sent again once received. Therefore, adopting a trustable routing path will improve the success rate of routing, reduce the sending times of data, and thereby effectively enhance the network performance.The third research motivation is adopting the data aggregation method to reduce the energy consumption. As shown in Figure2, the network will undertake much less data after adopting the data aggregation and thereby effectively extend the network lifetime.Figure 2
Comparison of data amount in data aggregation and non-data aggregation strategies.


### 4.2. The Design of ASTR

This section introduces the detailed design of ASTR scheme. ASTR scheme is as shown in Figure3. It mainly consists of the following important parts: (1) data aggregate signature; (2) R(M,N) routing method; (3) trust routing method.Figure 3
The framework of ASTR scheme.(1) Aggregate Signature Stage. In this stage, ID-based aggregate signature technology [1] is adopted in ASTR scheme. ID-based aggregate signature can ensure the data packets of several source nodes are sent to the aggregator and, after aggregating signature and sending the data to the sink through multiple hops, the aggregator can provide assurance to the recipient that the message came from the expected sender and has not been altered in transit [1]. Hence, in ASTR scheme, the data packets are not directly sent to the sink but sent after data aggregation, which effectively reduces the data amount loaded by nodes (see Figure 2). The process of data aggregation is shown in Figure 3. When the nodes s0,s1,s2,s3,ands4 intend to send the data packets to the sink, they will select one node among them, such as node s0 as the aggregator while other nodes become the member nodes of aggregator node s0 and send data packets to the aggregator node s0. After receiving the data packets sent by all member nodes, the aggregator node s0 adopts the aggregate signature method in [1] to aggregate them into one data packet and sends the packet to the sink (if M>1, the data packet will be sent to the sink in a method similar to multipath routing). Reference [1] has shown that the data aggregation method can be authenticated for each of the data of node. Besides, the selection of aggregator is similar to that of cluster head which can be found in [36]. On the other hand, the ASTR scheme can simultaneously send N abstracts which are also produced by the aggregator. When receiving all data packets from member nodes, the aggregator will know the IDs of all member nodes, IDs of data packets, and data production time. Therefore, the aggregator can produce the abstracts from the owned information during the data aggregation with the aggregate signature method. The abstract is short in length and further shortened after the data aggregate, which effectively improves the network performance.(2)
R
(
M
,
N
)
Routing Method. After the aggregate signature, both data packet and abstract have been produced, so this section mainly describes how to effectively route the data packet to the sink, that is, R(M,N) routing method. The ASTR scheme ensures the probability for data to successively reach the sink is higher than the specified level q. The R(M,N) routing method is the method to send M data packets and N abstracts at one time and route them to the sink over different routing paths with k times of sending to the maximum. In this paper, the operation of sending M data packets and N abstracts at one time is called one sending of M+N, written as SM+N. The process of RM,N routing is as follows:(a) Sender performs oneSM+N operation; K = 1.(b) If the sink fails to receive data or abstract, the data packet sending fails and the data sending will end.(c) Otherwise, if the sink receives the data sent successfully, the sending of this data packet will stop.(d) If the sink receives only abstract but no data packet, it will notify the sender to perform theSM+N operation again.(e) The sender will detect whether the number of resending instances has reached the maximum valuek. If K<k, it will perform another SM+N operation and otherwise gives up the sending of data. k is the maximum number of operations calculated based on the probability for data to successively reach the sink required by the application (see formula (17)).The process ofSM+N operation is as follows: firstly, the aggregator copies the data packet for M times during an operation and the M data packets are routed to the sink over M paths. At the same time, it copies the abstract for N times and the N abstracts are routed to the sink over N paths. The following describes the routing process of abstract to explain the routing process of data or abstract. The routing process for sending of the ith abstract by aggregator s0 is taken as an example to describe the SM+N operation. As shown in Figure 3, aggregator s0 firstly generates a random number di in 1,d and di represents the length of the ith abstract routed horizontally before being routed to the sink with the shortest routing method. In this paper, horizontal routing refers to each time when the node selects a node on the left (right) that is the same hops as itself from the sink as the next relay node for routing. In this way, aggregator s0 selects its neighbor node s4 on the left as the relay node and sends the abstract to s4. s4 selects its neighbor node s5 following the same direction. The process proceeds until the abstract is routed to node s7 and the horizontal routing stops when its routing distance reaches di. Starting from node s7, the node will select the neighbor node closest to the sink until the abstract is routed to the sink. The routing process of other N-1 abstracts is similar to the above. However, the difference lies in that the other N-1 abstracts will select the node that has not been selected by the preceding nodes or a highly trustable node as the relay node. The routing process of data packets is very similar to the routing process of abstract. The value of M for routing of data packets is usually small; for example, M = 1, and its routing process is as shown in Figure 3.(3) Trust Routing Scheme. In ASTR scheme, the trust-based routing is established for improving the reach rate of data packets. The basis of adopting trust routing is as follows: in ASTR scheme, if the sink fails to receive the data packet but receives the abstract, the sink will notify the sender to send the data again and the sender will recognize that an attacker exists in the routing path of data packet (in this paper, the communication is assumed perfect with no loss of data packet, so the loss of data packet is caused by attack). Therefore, the sender decreases the trust of the routing path which the data just passed through to prevent another data packet from passing the path containing an attacker, which increases the success rate of routing. Actually, the sender does not know the nodes through which the data is routed, so it can only mark neighbor nodes. In other words, the sender will decrease the trust of neighbor nodes of the failing routing path to reduce the probability of another data forwarding through the neighbor node and thereby increase the success rate of routing. Ti,j represents the trust of node si on neighbor node sj. When the sender node si successfully sends the data packet through neighbor node sj, the trust of Ti,j will be lifted by ∂; on the contrary, if the data sending fails through sj, the trust of Ti,j will be decreased by ∂:(9)Ti,j=Ti,j+∂ifsi′sdata  to  sink  successfully  viasj,Ti,j=Ti,j+∂,ifsi′sdata  to  sink  failure  viasj.After the calculation of trust, the sender nodesi will select the node with high trust from the neighbor nodes for data routing, which can effectively improve the success rate of routing.The ASTR scheme has been completely introduced, so the following will briefly describe the advantages of ASTR scheme compared with the past schemes. Generally speaking, the ASTR scheme has the following advantages superior to the preceding schemes.(1) The ASTR scheme adopts the aggregate signature technology so that the source data can be authenticated by sink. In addition, after the data aggregation is adopted, the network load is significantly reduced, which greatly improves the security and extends the network lifetime compared with the past schemes.(2) The ASTR scheme proposes theR(M,N) routing method which can more effectively improve the probability for data to reach the sink safely and reduce the data amount, indicating an obvious improvement in both security and network lifetime compared with the past schemes. To ensure the data can successively reach the sink, the past schemes usually adopt the M multipath routing scheme (MPR), which forces the nodes to undertake a large amount of data, but the proportion of effective data reaching the sink is low. The ASTR scheme mainly improves the past schemes in two aspects: (a) reducing the sending of heavy data and increasing abstract to lift the success rate for data to reach the sink and reduce the data amount loaded by nodes and (b) changing the method in past MPR schemes to send M data at one time. It sends only a small number (generally 1) of data and sends again when the first sending fails, which effectively reduces the redundant data sent and achieves a high efficiency.(3) The ASTR scheme adopts a trust routing mechanism that can further improve the success rate of routing.The detailed description of ASTR scheme is provided in Algorithm1.Algorithm 1:The algorithm of aggregate signature based trust routing (ASTR) scheme.
(1) aggregate signature stage
(1)  For each node Do
(2)    running aggregator determining algorithm which is is
similar to cluster-head selection algorithm in [36];
(3)  End for
// now, nodes either belong to aggregators or belong to member nodes
(4)  For each member node Do
(5)    send its data as well as node ID, data time to its aggregator
(6)  End for
(7)  For each aggregator node s0Do
(8)    s0 aggregate its member nodes’ data into a data packet D0
using ID-based aggregate signature technology as [1];
(9)    s0 aggregate its member nodes’ abstract into an abstract A0
using ID-based aggregate signature technology as [1];
(10)  End for
(2)
R
(
M
,
N
)
stage
(11)  s0 compute k according to the q using formula (17);
//k is the maximum retransmission times of SM+N
(12)  Let K=0;
(13)  s0 select a set of values {d1,d2,…,dN} random from 1,d
(14)  s0 select N neighbor nodes s01,s02,…,s0N with higher trust
T0,? than the rest neighbor nodes;
(15)  s0 send A0 to each node in the set {s01,s02,…,s0N};
// begin abstract routing
(16)  Foreach s0j in the set {s01,s02,…,s0N}  Do
(17)   Whiledj>0Do
(18)    select its highest trust of left (right) neighbor node s0j,nex;
(19)    send A0 to s0j,nex;
(20)    dj=dj-1;
(21)    s0j←s0j,nex;
(22)   End While
(23)   Whiles0j is not sink Do
(24)    select its high trust and the nearest to sink neighbor s0j,nex;
(25)    send A0 to s0j,nex;
(26)    s0j←s0j,nex;
(27)   End While
(28)  End for //end abstract route to sink
(29)  s0 select M neighbor nodes {s01,s02,…,s0M} with higher trust
T0,? than the rest neighbor nodes;
(30)  s0 send D0 to each node in the set {s01,s02,…,s0M};
// begin data routing
(31)  Foreach s0j in the set {s01,s02,…,s0M}  Do
(32)   Whiledj>0Do
(33)    select its highest trust of left (right) neighbor node s0j,nex;
(34)    send D0 to s0j,nex;
(35)    dj=dj-1;
(36)    s0j←s0j,nex;
(37)   End While
(38)   Whiles0j is not sink Do
(39)    select its high trust & the nearest to sink neighbor s0j,nex;
(40)    send D0 to s0j,nex;
(41)    s0j←s0j,nex;
(42)   End While
(43)  End for //end data route to sink
(44)  Let K=K+1;
(45)  aggregator s0 wait for the message from sink;
(46)  If message from sink indicate that data routing failure then
(47)    IfK<k
(48)    goto step (13);
(49)    End if
(50)  End if
(3) Trust computing stage
(50)  aggregator s0 get a message from sink
(51)  If message from sink indicate that data routing failure then
(52)   T0,j=T0,j-∂;
//j is the neighbor sj of s0 that data routing through sj
(53)  Else
(54)   T0,j=T0,j+∂;
(55)  End if


## 4.1. The Research Motivation of ASTR Scheme

This section discusses the research motivation of ASTR scheme. Firstly, the energy consumption of the network data collection shows that when the network contains no attackers, the energy consumption is as shown in Figure1 (M in the figure represents that the same data packets are sent for M times, the same below). Figure 1 shows that all data in the network can successively reach the sink because no attackers exist. Therefore, the energy consumption of nodes close to the sink area is very high. However, if attackers exist, the attack behaviors of attackers will cause a certain proportion of data packets to be attacked during the routing, dropped, and not able reach the sink. In this case, the number of data packets reaching the sink is smaller than that number in network without attackers, so its energy consumption decreases. It should be noted that the decrease of energy consumption is caused by the reduction of data packets reaching the sink as a result of attack instead of improvement in network performance. This is not a good condition because the idealistic effect for guaranteeing data security is to ensure all data packets in the network can reach the sink and the highest energy consumption is the same as the network that is not attacked. One of the methods to improve the reach rate of data packets is to send the same data for M times over different paths, which is able to significantly raise the reach rate of data. As shown in Figure 1, assuming the probability of successively sending data packets under attack p=0.90, the reach rate is only 0.90 for packets routed by one hop; if the times of sending the same data packets M=2, the one-hop reach rate is 99%, apparently higher than 0.90.Figure 1
Data loaded by nodes under different data collection strategies.This method is actually the multipath routing (MPR) scheme described above. It is direct and effective and so widely researched. However, the shortcomings of the method are rarely researched. Figure1 shows that when M=2 and p=0.90, the actual number of data reaching the sink has exceeded the number of data when no data packet is lost. However, the effective reach rate of data packets is only 55%. It demonstrates that when this method is used, a large amount of repetitive data packets will reach the sink, but some data packets fail to reach the sink. The repetitive data packets (redundant data packets) reaching the sink are useless to improve the reach rate of data packets but increase the energy consumption of the network and shorten the network lifetime.If we can reduce the redundant data reaching the sink and maintain the success rate for data packets to reach the sink, the network lifetime can be extended and the reach rate of data can be ensured at the same time. Based on the above ideas, this paper proposed the ASTR scheme which sends the light abstract information join data packets to improve the network security and energy efficiency. Instead of simply sendingM data packets, this method sends N abstracts (containing the information such as node ID, time, and data packet ID) while it sends M data (relatively small and generally M=1), which is known as R(M,N) routing method. If the message received by the sink contains no data packets, the sink will notify the node to send (M+N) messages again until it receives the data packets or the number of sending times reaches the maximum value k. Compared with the past strategies, the RM,N data collection method with maximum value k can effectively reduce the energy consumption of the network. This is because of the following: if M=1 in the R(M,N) routing method, once the sink receives the data packets, the subsequent sending actions will be stopped, so the sink cannot receive repetitive data packets. As a result, the sink will receive only redundant abstracts but no redundant data packets with this method. Abstracts are lightweight packets with a length of 1/10 or 1/100 of the length of data packets; hence, sending lightweight abstracts instead of heavy data packets is conducive to reducing energy consumption.Table2 compares the data amount sent by the node 5 hops from the sink in R(M,N) routing strategy and multipath routing strategy of sending data the same packets for M times while ensuring the same reach rate of data packets. The first line of Table 2 represents the data in M multipath routing strategy and (M,data,sp) in the first line represent the number of repeatedly sent data packets, data amount sent by nodes, and the proportion of data received by the receiving nodes. For example, (2, 200, and 0.83) represent the following: the number of repeatedly sent data packets: M=2, data amount sent by the sender = 200 bits, and the proportion of data received by the receiver = 0.83. Other lines represent the parameters of the R(M,N) strategy, where M = 1 and k represents the times of repetitive sending. Table 2 shows that when M is 2 in MPR scheme and the R(M,N) routing strategy is used, the data amount loaded by nodes is only 70% of the data amount in M multipath routing strategy. As M increases, the R(M,N) routing strategy presents better performance. When M = 5, the data amount loaded by nodes is only 50% of that in M multipath routing strategy. The R(M,N) routing strategy proposed in this paper has prominent advantages.Table 2
Comparison of data amount loaded by nodes in different strategies.
(M, data, sp)  (2, 200, 0.83)
(M, data, sp)  (3, 300, 0.93)
(M, data, sp) (4, 400, 0.97)
(M, data, sp)  (5, 500, 0.99)
k = 3
131.82 (N = 1)
155.81 (N = 2)
k = 4
142.12 (N = 1)
171.56 (N = 2)
k = 5
146.51 (N = 1)
179.08 (N = 2)
223.37 (N = 4)
k = 6
148.31 (N = 1)
182.52 (N = 2)
208.03 (N = 3)
247.26 (N = 5)
k = 7
149.02 (N = 1)
184.06 (N = 2)
210.17 (N = 3)
231.35 (N = 4)The second research motivation: in the preceding research motivation, the message is set free after being sent. It is obvious that selecting a trustable routing path for every hop during the routing will effectively improve the success rate of routing and reduce the sending times of data packets. In ASTR scheme, a data packet will not be sent again once received. Therefore, adopting a trustable routing path will improve the success rate of routing, reduce the sending times of data, and thereby effectively enhance the network performance.The third research motivation is adopting the data aggregation method to reduce the energy consumption. As shown in Figure2, the network will undertake much less data after adopting the data aggregation and thereby effectively extend the network lifetime.Figure 2
Comparison of data amount in data aggregation and non-data aggregation strategies.


## 4.2. The Design of ASTR

This section introduces the detailed design of ASTR scheme. ASTR scheme is as shown in Figure3. It mainly consists of the following important parts: (1) data aggregate signature; (2) R(M,N) routing method; (3) trust routing method.Figure 3
The framework of ASTR scheme.(1) Aggregate Signature Stage. In this stage, ID-based aggregate signature technology [1] is adopted in ASTR scheme. ID-based aggregate signature can ensure the data packets of several source nodes are sent to the aggregator and, after aggregating signature and sending the data to the sink through multiple hops, the aggregator can provide assurance to the recipient that the message came from the expected sender and has not been altered in transit [1]. Hence, in ASTR scheme, the data packets are not directly sent to the sink but sent after data aggregation, which effectively reduces the data amount loaded by nodes (see Figure 2). The process of data aggregation is shown in Figure 3. When the nodes s0,s1,s2,s3,ands4 intend to send the data packets to the sink, they will select one node among them, such as node s0 as the aggregator while other nodes become the member nodes of aggregator node s0 and send data packets to the aggregator node s0. After receiving the data packets sent by all member nodes, the aggregator node s0 adopts the aggregate signature method in [1] to aggregate them into one data packet and sends the packet to the sink (if M>1, the data packet will be sent to the sink in a method similar to multipath routing). Reference [1] has shown that the data aggregation method can be authenticated for each of the data of node. Besides, the selection of aggregator is similar to that of cluster head which can be found in [36]. On the other hand, the ASTR scheme can simultaneously send N abstracts which are also produced by the aggregator. When receiving all data packets from member nodes, the aggregator will know the IDs of all member nodes, IDs of data packets, and data production time. Therefore, the aggregator can produce the abstracts from the owned information during the data aggregation with the aggregate signature method. The abstract is short in length and further shortened after the data aggregate, which effectively improves the network performance.(2)
R
(
M
,
N
)
Routing Method. After the aggregate signature, both data packet and abstract have been produced, so this section mainly describes how to effectively route the data packet to the sink, that is, R(M,N) routing method. The ASTR scheme ensures the probability for data to successively reach the sink is higher than the specified level q. The R(M,N) routing method is the method to send M data packets and N abstracts at one time and route them to the sink over different routing paths with k times of sending to the maximum. In this paper, the operation of sending M data packets and N abstracts at one time is called one sending of M+N, written as SM+N. The process of RM,N routing is as follows:(a) Sender performs oneSM+N operation; K = 1.(b) If the sink fails to receive data or abstract, the data packet sending fails and the data sending will end.(c) Otherwise, if the sink receives the data sent successfully, the sending of this data packet will stop.(d) If the sink receives only abstract but no data packet, it will notify the sender to perform theSM+N operation again.(e) The sender will detect whether the number of resending instances has reached the maximum valuek. If K<k, it will perform another SM+N operation and otherwise gives up the sending of data. k is the maximum number of operations calculated based on the probability for data to successively reach the sink required by the application (see formula (17)).The process ofSM+N operation is as follows: firstly, the aggregator copies the data packet for M times during an operation and the M data packets are routed to the sink over M paths. At the same time, it copies the abstract for N times and the N abstracts are routed to the sink over N paths. The following describes the routing process of abstract to explain the routing process of data or abstract. The routing process for sending of the ith abstract by aggregator s0 is taken as an example to describe the SM+N operation. As shown in Figure 3, aggregator s0 firstly generates a random number di in 1,d and di represents the length of the ith abstract routed horizontally before being routed to the sink with the shortest routing method. In this paper, horizontal routing refers to each time when the node selects a node on the left (right) that is the same hops as itself from the sink as the next relay node for routing. In this way, aggregator s0 selects its neighbor node s4 on the left as the relay node and sends the abstract to s4. s4 selects its neighbor node s5 following the same direction. The process proceeds until the abstract is routed to node s7 and the horizontal routing stops when its routing distance reaches di. Starting from node s7, the node will select the neighbor node closest to the sink until the abstract is routed to the sink. The routing process of other N-1 abstracts is similar to the above. However, the difference lies in that the other N-1 abstracts will select the node that has not been selected by the preceding nodes or a highly trustable node as the relay node. The routing process of data packets is very similar to the routing process of abstract. The value of M for routing of data packets is usually small; for example, M = 1, and its routing process is as shown in Figure 3.(3) Trust Routing Scheme. In ASTR scheme, the trust-based routing is established for improving the reach rate of data packets. The basis of adopting trust routing is as follows: in ASTR scheme, if the sink fails to receive the data packet but receives the abstract, the sink will notify the sender to send the data again and the sender will recognize that an attacker exists in the routing path of data packet (in this paper, the communication is assumed perfect with no loss of data packet, so the loss of data packet is caused by attack). Therefore, the sender decreases the trust of the routing path which the data just passed through to prevent another data packet from passing the path containing an attacker, which increases the success rate of routing. Actually, the sender does not know the nodes through which the data is routed, so it can only mark neighbor nodes. In other words, the sender will decrease the trust of neighbor nodes of the failing routing path to reduce the probability of another data forwarding through the neighbor node and thereby increase the success rate of routing. Ti,j represents the trust of node si on neighbor node sj. When the sender node si successfully sends the data packet through neighbor node sj, the trust of Ti,j will be lifted by ∂; on the contrary, if the data sending fails through sj, the trust of Ti,j will be decreased by ∂:(9)Ti,j=Ti,j+∂ifsi′sdata  to  sink  successfully  viasj,Ti,j=Ti,j+∂,ifsi′sdata  to  sink  failure  viasj.After the calculation of trust, the sender nodesi will select the node with high trust from the neighbor nodes for data routing, which can effectively improve the success rate of routing.The ASTR scheme has been completely introduced, so the following will briefly describe the advantages of ASTR scheme compared with the past schemes. Generally speaking, the ASTR scheme has the following advantages superior to the preceding schemes.(1) The ASTR scheme adopts the aggregate signature technology so that the source data can be authenticated by sink. In addition, after the data aggregation is adopted, the network load is significantly reduced, which greatly improves the security and extends the network lifetime compared with the past schemes.(2) The ASTR scheme proposes theR(M,N) routing method which can more effectively improve the probability for data to reach the sink safely and reduce the data amount, indicating an obvious improvement in both security and network lifetime compared with the past schemes. To ensure the data can successively reach the sink, the past schemes usually adopt the M multipath routing scheme (MPR), which forces the nodes to undertake a large amount of data, but the proportion of effective data reaching the sink is low. The ASTR scheme mainly improves the past schemes in two aspects: (a) reducing the sending of heavy data and increasing abstract to lift the success rate for data to reach the sink and reduce the data amount loaded by nodes and (b) changing the method in past MPR schemes to send M data at one time. It sends only a small number (generally 1) of data and sends again when the first sending fails, which effectively reduces the redundant data sent and achieves a high efficiency.(3) The ASTR scheme adopts a trust routing mechanism that can further improve the success rate of routing.The detailed description of ASTR scheme is provided in Algorithm1.Algorithm 1:The algorithm of aggregate signature based trust routing (ASTR) scheme.
(1) aggregate signature stage
(1)  For each node Do
(2)    running aggregator determining algorithm which is is
similar to cluster-head selection algorithm in [36];
(3)  End for
// now, nodes either belong to aggregators or belong to member nodes
(4)  For each member node Do
(5)    send its data as well as node ID, data time to its aggregator
(6)  End for
(7)  For each aggregator node s0Do
(8)    s0 aggregate its member nodes’ data into a data packet D0
using ID-based aggregate signature technology as [1];
(9)    s0 aggregate its member nodes’ abstract into an abstract A0
using ID-based aggregate signature technology as [1];
(10)  End for
(2)
R
(
M
,
N
)
stage
(11)  s0 compute k according to the q using formula (17);
//k is the maximum retransmission times of SM+N
(12)  Let K=0;
(13)  s0 select a set of values {d1,d2,…,dN} random from 1,d
(14)  s0 select N neighbor nodes s01,s02,…,s0N with higher trust
T0,? than the rest neighbor nodes;
(15)  s0 send A0 to each node in the set {s01,s02,…,s0N};
// begin abstract routing
(16)  Foreach s0j in the set {s01,s02,…,s0N}  Do
(17)   Whiledj>0Do
(18)    select its highest trust of left (right) neighbor node s0j,nex;
(19)    send A0 to s0j,nex;
(20)    dj=dj-1;
(21)    s0j←s0j,nex;
(22)   End While
(23)   Whiles0j is not sink Do
(24)    select its high trust and the nearest to sink neighbor s0j,nex;
(25)    send A0 to s0j,nex;
(26)    s0j←s0j,nex;
(27)   End While
(28)  End for //end abstract route to sink
(29)  s0 select M neighbor nodes {s01,s02,…,s0M} with higher trust
T0,? than the rest neighbor nodes;
(30)  s0 send D0 to each node in the set {s01,s02,…,s0M};
// begin data routing
(31)  Foreach s0j in the set {s01,s02,…,s0M}  Do
(32)   Whiledj>0Do
(33)    select its highest trust of left (right) neighbor node s0j,nex;
(34)    send D0 to s0j,nex;
(35)    dj=dj-1;
(36)    s0j←s0j,nex;
(37)   End While
(38)   Whiles0j is not sink Do
(39)    select its high trust & the nearest to sink neighbor s0j,nex;
(40)    send D0 to s0j,nex;
(41)    s0j←s0j,nex;
(42)   End While
(43)  End for //end data route to sink
(44)  Let K=K+1;
(45)  aggregator s0 wait for the message from sink;
(46)  If message from sink indicate that data routing failure then
(47)    IfK<k
(48)    goto step (13);
(49)    End if
(50)  End if
(3) Trust computing stage
(50)  aggregator s0 get a message from sink
(51)  If message from sink indicate that data routing failure then
(52)   T0,j=T0,j-∂;
//j is the neighbor sj of s0 that data routing through sj
(53)  Else
(54)   T0,j=T0,j+∂;
(55)  End if


## 5. Performance Analysis

### 5.1. The Calculation and Comparison of Data Amount

This section mainly compares the data amount loaded by nodes in the ASTR scheme proposed in this paper and other schemes and thereby demonstrates that the scheme proposed by this paper can effectively reduce the data amount loaded by nodes. Table3 shows all symbols used in this paper. Firstly, Theorem 1 provides the data amount loaded by nodes in the network where the data packets are transmitted as in a safe network though the network contains attackers that will cause packets loss.Table 3
Parameters related to the calculation.
Symbol
Description
R
Network radius
n
Total number of nodes in the area
r
Emission radius of nodes
h
Number of hops from a node to the base station
p
Success rate of each hop when each data packet is sent to the sink
n
x
Any node in the network
w
x
Width of the annular area where the nodenx is located
ρ
Distribution density of nodes in the network
ε
Network coefficientTheorem 1.
If packets loss ratio is 1-p, the data packet will be sent only once after data aggregation and the distance from the data packet to the sink is l, the data amount loaded by the node with l=hr+x can be calculated as follows: (10)Qx=ετ+δ+Γ·1+∑i=1zl+irl·pi∣z=R-lr.Proof.
As shown in Figure4, we should consider the data amount loaded by the wx wide annular area where the node is located. The annular area where the node nx is located will surely undertake the data transfer of nodes in wx wide annular areas at l+r,l+2r,…,l+zr. If wx is very small, the nodes in this area can be considered undertaking identical data amount. The area of annular area where the node nx is located is as follows: Snx=2πlwx
The total number of nodes in the area is(11)Nnx=Snx·ρ=2πρlwx.
It receives and transfers the data inl+ir∣i∈1,z area and the area and number of nodes of the annular area Vl+ir where l+ir is located are, respectively, (12)SVl+ir=2πl+irwx,NVl+ir=2πρl+irwx.
Similarly, the number of nodes of the areas whose data transfer is loaded byVl area: (13)2πρlwx+2πρl+rwx+2πρl+2rwx+⋯+2πρl+zrwx∣z=R-lr.
In a period, each node produces the following: one data packet, one ID packet, and one time axis. The size of data packet isτ, the size of ID packet is δ, and the size of time axis is Γ. Therefore, the data amount produced by a node in a period is τ+δ+Γ. Assume the aggregation is ε, but when the data packet is being transmitted to the base station, the probability for successful transmission of each hop is p and the node in area Vl+ir has a distance of i hops from i, so the probability of transmitting the data packet of Vl+ir area to area Vl is pi and the number of data packets of Vl+ir area loaded by the node in Vl area is 2πρl+irwx·pi. The data will time the aggregation coefficient after the data aggregation ε, so the data amount loaded by each node in Vl area can be calculated as follows: (14)Qx=ετ+δ+Γ·2πρlwx+∑i=1z2πρl+irwxpi2πρlwx=ετ+δ+Γ1+∑i=1zl+irl·pi.Figure 4
The data forwarding of each node.The ASTR scheme adopts theR(M,N) routing method. If the message received by the sink contains no data packet, the sink will notify the node to resend (M+N) message until the sink has received the data packet or the resending instances have reached the maximum value k. The following calculate the data amount of the R(M,N) routing method.Theorem 2.
Assume the node has a distance ofl from the sink, l=hr+x, the R(M,N) routing method is adopted, and the size of abstract is μ times of the size of data packet. If the number of hops of the abstract during horizontal routing is a random number in 1,d, and the data amount loaded by the node is as (15)Sx=MQx+Qx·pz+μN∑j=1d/2pj=M·ετ+δ+Γ·1+∑i=1zl+irl·pi+ετ+δ+Γ·1+∑i=1zl+irl·pi·pz+μN·∑j=1d/2pj∣z=R-lr.Proof.
Theorem1 shows that the data amount loaded by each node is Qx when one data packet is sent, so the data amount loaded by each node is MQx when M data packets are sent. Different from data packet, the abstract will be horizontally routed by d/2 hops during sending. Therefore, the incremental data amount loaded by each node is N∑j=1d/2pj and the data amount loaded by each node is Qx·pz+μN∑j=1d/2pj when N abstracts are sent.Theorem2 provides the data amount loaded by the node in the network which is l from the sink when the data aggregation is adopted with a packet loss ratio of 1-p and the R(M,N) routing method is used. It the MPR scheme is adopted, the data amount loaded by a node in the network is as shown in Figures 5–7. Figure 5 shows that, in MPR scheme, the data amount loaded by the node closed to the sink increases more rapidly with the increase of M because the node closer to the network center has to undertake all data packets routed from periphery of the network. Therefore, the energy of nodes near the sink will be consumed fast and the lifetime of the whole network is short. Figure 6 compares the data amount loaded by the node under different packet loss ratios. Figure 6 shows that when the success rate of successive transmission of each hop p decreases and the node still sends M data packets, the data amount loaded by each node will be reduced due to packet loss. Figure 6 also shows that if each node sends one less repetitive data packet and the success rate of transmission of each hop decreases by 0.1, the data amount has no change compared with the above. It should be noted that the success rate of transmission of each hop is positively correlated with the reliability of the whole network. Figure 7 compares the data amount in networks of different sizes. It shows that when other variables are all the same, the node in a larger network will undertake more data. Regardless of the network size, the broken line representing the data amount flattens at the same location which is 1 hop from the sink. According to the data, the nodes in a circle with the sink as the center and r as the radius undertake 45.87% of the total data amount of all nodes.Figure 5
Data amount loaded by a node in MPR scheme when the node sends different numbers of data packets(p=0.90).Figure 6
Data amount loaded by a node in MPR scheme with different success rate of transmission of each hop(R=300).Figure 7
Data amount loaded by a node in MPR scheme for network of different sizes (p = 0.90).It the ASTR scheme, that is,R(1,N), routing method is adopted and M=1 and N abstracts are sent, and the data amount loaded by a node in the network is as shown in Figure 8. Figure 8 shows that when the more abstracts are sent, the data amount will increase. During the comparison between Figures 8 and 5, the intersection of the broken line and longitudinal axis shows that the data amount is 115.56 when N = 5, smaller than the data amount 129.64 when M = 2, so the increase of number of abstracts has no significant impact on the data amount. Therefore, increasing the number of abstracts is a better scheme compared with increasing the number of data packets to improve the successful reach rate because the node closer to the sink undertakes less data amount, which will extend the lifetime of network and improve the network performance.Figure 8
Data amount loaded by a node in ASTR scheme when the node sends different number of abstracts (p = 0.90, M=1).Figure9 compares the data amount loaded by each node in ASTR scheme under different packet loss ratios. Figure 9 clearly shows that the increase in number of abstracts has no great impact on the data amount, but the increase of p will cause a significant increase of data amount. Figure 10 compares the data amount loaded by each node when M=1 and Nabstracts are sent.Figure 9
Data amount loaded by a node in ASTR scheme under different success rate of transmission of each hop (R=300; M=1).Figure 10
Data amount loaded by a node in ASTR scheme for network of different sizes (p=0.90; M=1).A comparison is conducted between the data amount in MPR scheme and ASTR scheme (see Figures5–7 versus Figures 8–10). In Figures 5–10, the experiment results show that, in ASTR scheme, the data amount loaded by a node decreases significantly, proving the effectiveness of the ASTR scheme.In Figures5–10, the comparison of data amount provides the comparison of data amount of the whole network. Two schemes adopt different parameters and have different data amount reaching the sink, so they are not compared under the same conditions. To effectively compare the performance of the two schemes, we compare the data amount loaded by each node under the same parameters when the data packet is only one hop from the sink.In ASTR scheme, assumeM = 1, N abstracts are sent, and the success rate of transmitting message for each hop is p. In this case, the probability for at least one message to reach the sink is σ=1-1-p(1+N) in ASTR scheme, where p represents the probability for the data packet to reach the sink. If the data packet is received, no resending is needed and the process will end; if no message is received, the sink will not know the sending of data packet and the process will also end. Otherwise, if the received message contains no data packet, the data packet will be resent and the number of packets sent for each time is also (1+N). The data packet will be sent for the second time when the first message is received but will contain no data packet and the probability of this case is (1-p)σ. In the second sending, the reach probability of data packet is still p and the probability of sending and receiving the data packet is (1-p)σp. Similarly, the data packet will be sent for the third attempt when the messages are successfully sent in the preceding two attempts but contain no data packet and the probability of this case is (1-p)2σ2. In the third sending, the reach probability of data packet is p and the probability of successively sending the message and receiving the data packet in the third attempt is (1-p)2σ2p. Therefore, the probability of the kth sending attempt is (1-p)k-1σk-1p.If the upper limit of number of sending attempts isk, the message can only be sent for k times in maximum. If the data packet has not been successfully sent at the kth attempt, it will not send again. If the data packet is successfully sent after less than k attempts, it will not be sent again either. In this case, the total success rate of sending of data packets is as follows: (16)β1+N=p+1-pσp+1-p2σ2p+⋯+1-pk-1σk-1p=p∑k=1a1-pσk-1,σ=1-1-p1+N.If the application requires a probability ofq for data to successively reach the sink, k should abide by the following formula:(17)β1+N=p∑k=1a1-pσk-1>q.Theorem 3.
In ASTR scheme, letM = 1, N abstracts are sent, the success rate of transmission of message of each hop is p, the node is on hop from the sink and the upper limit of the number of sending attempts is k, and the expected number of sending attempts can be calculated as follows:(18)w=11-σ1-p∗∑k=1a1-pσk-1∗1-σk1-pk1-σ1-p-kσk1-pk.Proof.
The probability of successively sending the data packet at one time isp and the number of sending attempts is 1; the first sending of data packet fails, the probability of successively sending at the second attempt is 1-pσp, and the number of sending attempts is 2; if the sending of data packet fails for two times, the probability of failure to send the data packet is (1-p)2σ2p and the number of sending attempts is 3.
The expected number of sending attempts is(19)w=1×pβ1+N+2×1-pσpβ1+N+3×1-p2σ2pβ1+N+⋯+k×1-pk-1σk-1pβ1+N=pβ1+N∗1-σ1-p∗1-σk1-pk1-σ1-p-kσk1-pk=11-σ1-p∗∑k=1a1-pσk-1∗1-σk1-pk1-σ1-p-kσk1-pk.Theorem 4.
In MPR scheme,M data packets are sent, the success rate of each hop of message transmission is p and the node is one hop from the sink, the actual number of data packets reaching the sink is (20)G=∑1Mi∗CMipi1-pM-i=Mp.
Assume the length of the data packet islm, and the total data amount is (21)Dm=G∗lm.Proof.
Only data packets are sent, so the probability for at least data packet to reach the sink is1-1-pM. In M attempts, the probability for only one data packet to reach the sink is CM1p∗(1-p)M-1, so the actual number of data packets sent when a data packet reaches the sink is 1CM1p∗(1-p)M-1; the probability for only two data packets to reach the sink is as follows: CM2p2∗(1-p)M-2, so the actual number of packets sent when two data packets reach the sink is as follows: 2CM2p2∗(1-p)M-2. Similarly, the actual number of data packets sent when M data packets reach the sink is as follows: MCMMpM∗1-pM-M=MpM. Therefore, when the data packet is sent for M times, the average number of data packets reaching the sink is G=∑1Mi∗CMipi1-pM-i. The length of each data packet is lm, so the total data amount is Dm=G∗lm.In MPR scheme, we take the method of routingM times and sending a packet each time. If we change it a little bit, we will get another scheme. In another scheme, we take the method of routing M times but each time c packets are sent. We call this scheme CMPR scheme. Deduction 5 is obtained by Theorem 4.Deduction 5.
In CMPR scheme, each timec packets are sent, cM data packets are sent in total, the success rate of each hop of message transmission is p, and the node is one hop from the sink, the actual number of data packets reaching the sink is (22)F=∑1cMi∗CcMipi1-pcM-i=cMp.
Assume the length of the data packet islm, and the total data amount is (23)dm=F∗lm.Proof.
Only data packets are sent, so the probability for at least data packet to reach the sink is1-1-pcM. In M attempts, the probability for only one data packet to reach the sink is CcM1p∗(1-p)cM-1, so the actual number of data packets sent when a data packet reaches the sink is 1CcM1p∗(1-p)cM-1; the probability for only two data packets to reach the sink is as follows: CcM2p2∗(1-p)cM-2, so the actual number of packets sent when two data packets reach the sink is as follows: 2CcM2p2∗(1-p)cM-2. Similarly, the actual number of data packets sent when cM data packets reach the sink is as follows: cMCcMcMpcM∗1-p0=cMpcM. Therefore, when the data packet is sent for M times, the average number of data packets reaching the sink is F=∑1cMi∗CcMipi1-pcM-i. The length of each data packet is lm, so the total data amount is dm=F∗lm.Theorem 6.
In ASTR scheme, letM = 1, N abstracts are sent, the success rate of each hop of message transmission is p, and the node is one hop from the sink. If the maximum number of resending attempts is km the actual number of data packets reaching the sink is (24)F=1+N∗w.Assume the length of each data packet is lm and the length of each abstract is ln, and the total data amount is (25)Dn=wlm+wNln.Proof.
In ASTR scheme, if 1 data packet andN abstracts are sent every time, the probability for at least one message to reach the sink is σ=1-1-p(1+N). It the data packet needs not to be sent again, the process will end; if no message is received, the sink will not know the sending of data packet and the process will also end; otherwise, if the message is received but contains no data packets, the message will be sent again and a (1+N) will be sent each time.
Therefore, the actual number of messages reaching the sink is1+N∗p when the data packet is successively sent at one time and 21+N∗1-pσp when the data packet is successively sent after two attempts. Similarly, the actual number of messages reaching the sink is k1+N∗(1-p)k-1σk-1p when the data packet is successively sent after k attempts and the average number of messages actually reaching the sink is as follows: F=1+N∗w (w is the expected sending attempts). Assume the length of each data packet is lm and the length of each abstract is ln, and the total data amount is Dn=wlm+wNln.Theorem 7.
If the success rate of each hop of message transmission isp and the node is one hop from the sink, the effective data amount received by the sink is (26)R=lm∗p.Proof.
The effective data amount is defined as the data amount of one data packet reaching the sink. There is a packet loss ratio, so the effective data amount is as follows:R=lm∗p.Theorem4 and Deduction 5 provide the actual data amount reaching the sink in MPR scheme and CMPR scheme. In the CMPR scheme, we let it send two packets at a time now. With different successful rate of transmission of each hop, Figures 11 and 12 can be gotten.Figure 11
The successful reach rate of MPR scheme and CMPR scheme with different value ofp when the number of sending times is 2, 3, 4, and 5, respectively c=2.Figure 12
The data amount of reaching the sink successfully of MPR scheme and CMPR scheme with different value ofp when the number of sending times is 2, 3, 4, and 5 c=2.Figures11 and 12 show that the successful reach rate of MPR scheme is very close to the successful reach rate of CMPR scheme, but the data amount of reaching the sink of MPR scheme is only half of the CMPR scheme. Therefore, the performance of MPR scheme is better under comprehensive consideration.Figures11 and 12 show the comparison between CMPR scheme and MPR scheme. The comparison of CMPR scheme and ASTR scheme is shown in Table 4.Table 4
The comparison between CMPR scheme and ASTR scheme whenc=2 and p=0.80.
CMPR scheme
ASTR scheme
The successful reach rate
Data amount of reaching the sink
The successful reach rate
Data amount of reaching the sink
0.9984
320
0.96
131.5241
0.999936
480
0.992
148.4281
0.999997
640
0.9984
162.1123
1
800
0.99968
174.9072As can be obtained from Table4, the CMPR scheme has improved the success rate of reaching the sink, but the limitation is that too many data packets are sent, so that the sink receives a lot of redundant data. Considering the comprehensive network condition, we do not think that CMPR scheme is a better scheme, so we will only compare MPR scheme and ASTR scheme.Theorems4 and 6 provide the actual data amount reaching the sink in MPR scheme and ASTR scheme. Figure 11 compares the data amount and effective data amount reaching the sink in two schemes when the probability for at least one data packet to reach the sink is 0.99, 0.999, 0.9999, and 0.99999.Figure13 clearly shows that as the application has higher requirement on the probability for data to reach the sink (increased from q = 0.99 to q = 0.99999), the data amount rises rapidly in MPR scheme. With the number of data packets sent plus one each time and assuming the length of a data packet is 100, the actual data amount reaching the sink will increase by 100∗p=90 each time; however, in ASTR scheme, the rise of data amount is very gentle. The number of abstracts increases by 1 each time and the number of expected sending attempts w changes insignificantly as N increases. Assuming the length of abstract is 10, the incremental data amount calculated following the formula in Theorem 6 is very small. The effective data amount calculated following Theorem 7 is 99, 99.9, 99.99, and 99.999, respectively.Figure 13
Actual data amount reaching the sink and effective data amount in two schemes whenp=0.90.Theorem7 proposes the concept of effective data. Currently, we can further propose the concept of redundant data amount which refers to part of the data amount actually reaching the sink and in excess of the effective data amount. Therefore, the redundant data amount reaching the sink in two schemes can be, respectively, calculated according to Figure 13 as follows: deducting the effective data amount from the actual data amount reaching the sink to get Figure 14 and dividing the redundant data amount by actual data amount reaching the sink to get Figure 15. Apparently, the redundant data amount and redundancy rate of the ASTR scheme are smaller than those of the MPR scheme because the ASTR scheme does not repetitively send very long data packets. Therefore, the ASTR scheme can both reduce the energy consumption of the network and extend the network lifetime.Figure 14
Comparison of redundant data amount between two schemes whenp=0.90.Figure 15
Comparison of data redundancy rate between two schemes whenp=0.90.Figures16, 17, and 18 show the experiment results when p = 0.80. According to the figures, the change of data amount is similar to the change when p = 0.90, which means the ASTR scheme has less redundant data amount and better performance than the MPR scheme regardless of the success rate of each hop of the transmission.Figure 16
Actual data amount reaching the sink and effective data amount in two schemes whenp=0.80.Figure 17
Comparison of redundant data amount between two schemes whenp=0.80.Figure 18
Comparison of data redundancy rate between two schemes whenp=0.80.Figures19 and 20 compare the probability for at least one data packet to reach the sink in MPR scheme and ASTR scheme when the actual data amount reaching the sink is the same. The experiment aims to visibly reflect the following: when consuming the same network resources, the ASTR scheme can achieve a higher probability for the sinker to receive at least one data packet compared with the MPR scheme. Figure 19 shows that when the data amount rises from 140 to 210 in ASTR scheme, the probability for at least one data packet to reach the sink increases rapidly and when the data amount reaches 210, the probability gets close to 1. To determine the causes of this condition more visibly, Figures 21 and 22 explain them clearly.Figure 19
Comparison of success rate of data transmission in two schemes when the actual data amount reaching the sink is the same.Figure 20
Difference between the success rate of data transmission in ASTR scheme and MPR scheme when the actual data amount reaching the sink is the same.Figure 21
Relationship betweenk,N and data amount (M=1) in ASTR scheme.Figure 22
Relationship betweenk,N and success rate of data transmission (M=1) in ASTR scheme.It is clear that the radian of cambered surface in Figure21 is small, but the radian of that in Figure 22 is large. The middle cambered surface has a large radian. When observing along the x-axis in two figures, we see the maximum number of sending attempts k ranges from 1 to 7, the data amount increases from 50 to 150, and the probability increases from 0 to 0.90, which demonstrates that, in ASTR scheme, increasing the number of sending attempts has significant effect on improving the probability while the data amount only increases a little. When the data amount increases to around 200, the probability has reached the saturated level. Therefore, we draw the conclusion: adopting the ASTR scheme can quickly achieve the purpose of data integrity with only small increment in data amount.


### 5.2. The Calculation and Comparison of Success Rate of Data Transmission

In this paper, the security of the network is not only related to data packets but also related to abstract. In this section, we analyze the overall probability for the sink to receive the data packet and abstract to verify that the data security can be improved under the ASTR scheme.Theorem8 and Deduction 9 show, respectively, the success rate for the data packet and abstract to reach the sink and the overall probability for the sink to receive the data packet and abstract when the success rate of the transmission of each hop is p and M data packets and N abstracts are sent at one time.Theorem 8.
Assume the success rate of each hop isp when each data packet is sent to the base station and the node sending the data packet is h hops from the base station. The number of hops is randomly selected from 1,d for horizontal routing of the abstract, so the expected length of horizontal routing is d/2 and its number of hops from the base station is h, the same as the data packet. Therefore, the average number of total hops sent by the abstract to the base station is h+d/2. Assume the number of data packets and abstracts is M, N, respectively. A1 means the sink fails to receive the data packet, A2 means the sink receives at least one data packet, A3 means the sink fails to receive the abstract, and A4 means the sink receives at least one abstract. f1M,h and f2M,h, respectively, represent the probability of case A1and case A2 and g1N,h,d and g2N,h,d, respectively, represent the probability of case A3 and case A4: (27)f1M,h=1-phM,∣caseA1,f2M,h=1-1-phM,∣caseA2,g1N,h,d=1-ph+d/2N,∣caseA3,g2N,h,d=1-1-ph+d/2N,∣caseA4.Proof.
Each data packet needsh hops when routed to the sink, so the probability for each data packet to successively reach the sink is ph and the probability for each data packet to fail in reaching the sink is 1-ph. Therefore, the probability for all of M data packets to fail in reaching the sink is 1-phM and the probability for the sink to receive at least one data packet is 1-1-phM. The distance of horizontal routing of abstract is 1,d, so the expected length of horizontal routing is d/2. The number of hops of the abstract from the base station is h, the same as the data packet, so the total expected length of sending one abstract to the base station is h+d/2. Therefore, the probability of successively routing each abstract to the sink is ph+d/2 and the probability of failing to route each data to the sink is 1-ph+d/2. Similarly, the probability for all of N data packets to fail in reaching the sink is 1-ph+d/2N and the probability for the sink to receive at least one data packet is 1-1-ph+d/2N.The overall probability for the sink to receive the data packet and abstract can be calculated based on the success rate of transmission of data packet and abstract, so Deduction9 can be obtained from Theorem 8.Deduction 9.
B
1 means the sink receives neither data packet nor abstract, B2 means the sink receives no data packet but receives at least one abstract, B3 means the sink receives no abstract but receives at least one data packet, and B4 means the sink receives at least one data packet and at least one abstract. φ1f1,g1,φ2f1,g2,φ3f2,g1, and φ4f2,g2, respectively, represent the probability of case B1, case B2, case B3, and case B4: (28)φ1f1,g1=1-phM∗1-ph+d/2N,∣caseB1,φ2f1,g2=1-phM∗1-1-ph+d/2N,∣caseB2,φ3f2,g1=1-1-phM∗1-ph+d/2N,∣caseB3,φ4f2,g2=1-1-phM∗1-1-ph+d/2N,∣caseB4.Proof.
According to Theorem8, whether the base station receives at least one data packet is independent of whether it receives at least one abstract, so the combined probability is the product of two probabilities; that is, φi,jfi,gj=fiM,h∗gjN,h,d.Deduction9 provides the occurrence probability of the cases in security analysis. The first case is that the sink receives neither data packet nor abstract. If we want to limit the probability of this case to <u, Deduction 10 can be obtained based on Deduction 9.Deduction 10.
Assume the success rate of each hop when each packet is sent to the sink, the number of hops for sending one abstract to the base station ish+d/2, the number of data packets is M, and the number of abstracts is N. To limit the probability for the sink to receive neither data packet nor abstract smaller than u, the values of M, N shall meet the following conditions: (29)M>log1-ph⁡u1-ph+d/2N,whenNis  a  fixed  value,N>log1-ph+d/2⁡u1-phM,whenMis  a  fixed  value.Proof.
According to Deduction9, the probability for the sink to receive neither data packet nor abstract is (30)φ1f1,g1=f1M,h×g1N,h,d=1-phM∗1-ph+d/2N.Now assume the value of N has been determined, 1-ph+d/2N is a constant, and the following inequation is obtained:(31)φ1f1,g1<u,i.e.1-phM∗1-ph+d/2N<u,and take the logarithm of both sides and obtain the following inequation:(32)M>log1-ph⁡u1-ph+d/2N.Similarly, assume the value of N has been determined, 1-phM is a constant, and the following inequation is obtained:(33)N>log1-ph+d/2⁡u1-phM.Figures23–26 provide the probability of the above four cases when the nodes different hops from the sink send the message to the sink with different values of parameters d,M, and N. The comparison between Figures 23 and 24 shows that when N increases by 1, the probability for the sink to receive no data packet but at least one abstract, represented by the red line, will increase and the probability for the sink to receive at least one data packet but no abstract, represented by the blue line, will decrease. According to Theorem 8, when the number of abstracts is larger, the probability for the sink to receive at least one abstract will increase. In addition, we can see that the probability for the sink to receive both data packet and abstract, represented by the green line, increases significantly, which means increasing the number of abstracts can achieve to the purpose of enhancing the data security. The comparison between Figures 23 and 25 shows that when the number of data packets and abstracts is increased by the same value, the relative probability of this case remains unchanged and the network achieves a very favorable reliability. Figure 26 shows the case where the number of hops is increased for horizontal routing of the abstract. With the four figures taken together, when M:N=1:1, the probability for the sink to receive the data packet but no abstract is larger than the probability for the sink to receive the abstract but no data packet; on the contrary, when M:N=1:2, the probability for the sink to receive the abstract but no data packet is larger than the probability for the sink to receive the data packet but no abstract. Increasing M,N improves the probability for the sink to receive both data packet and abstract.Figure 23
Probability of the four cases for nodes different hops from the sink(p=0.90,d=4,M=1, and N=1).Figure 24
Probability of the four cases for nodes different hops from the sink (p=0.90,d=4,M=1,andN=2).Figure 25
Probability of the four cases for nodes different hops from the sink (p=0.90,d=4,M=3,andN=3).Figure 26
Probability of the four cases for nodes different hops from the sink(p=0.90,d=8,M=1,andN=1).Figures27 and 28 are experiment figures prepared according to Deduction 10. The meaning of Deduction 10 is as follows: ensuring the probability for the sink to receive neither data packet nor abstract is lower than a very small value, fixing any one of M, N and alternating another variable to meet the above conditions. Figure 27 shows the minimum value obtained to meet the requirement on M when u is any value within 0.01~0.20 and N is fixed. Figure 27 shows clearly that when the distance of horizontal routing is 8, the node 10 hops from the sink have to send more data packets than the node 5 hops from the sink to guarantee a reach rate of smaller than u. In addition, when the number of hops from the sink is 5, the node whose distance of horizontal routing is 16 has to send more data packets than the node whose distance of horizontal routing is 8 to guarantee a reach rate of smaller than u. Each hop of the horizontal routing also has a packet loss ratio and more hops will decrease the reach rate of abstract. The value of N has been fixed, so the overall reach probability of both data packet and abstract can only be improved by increasing the value of M. Figure 28 shows the minimum value obtained to meet the requirement on N when the value of u is between 0.01 and 0.20 and the value of M is fixed.Figure 27
Minimum value ofM to meet the conditions when N is fixed.Figure 28
Minimum value ofN to meet the conditions when M is fixed.


### 5.3. Performance Comparison of the Whole Network with the Same Reliability

This section analyzes and compares the actual data amount reaching the sink in two schemes when the success rate of data transmission of all nodes in the whole network isq; that is, the whole network has the same reliability.Theorem 11.
Assuming the number of hops of nodenx from the sink, the MPR scheme is adopted, the reliability of the whole network is q and the success rate of each hop is p, and the number of resending attempts of nodes different hops from the sink are as follows: (34)Mhq=log⁡1-q⁡log⁡1-ph.Proof.
The success rate of each hop isp and the success rate that a message is successively sent to the sink is ph.
If the message is sent by the node forMhq times, the probability for at least one data packet to reach the sink is (35)1-1-pMhq,which is also the reliability of the network q, so the following equation is obtained: (36)q=1-1-pMhq.Take logarithm of both sides of the equation after transposition and obtain the following equation: (37)Mhq=log⁡1-qlog⁡1-ph.Figure29 shows the required resending attempts of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92, respectively. Figure 29 shows clearly that more resending attempts are required for the node farther from the sink because the node is more hops from the sink and each sink has a packet loss ratio; Figure 30 shows the number of maximum resending attempts k of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92, respectively, in our ASTR scheme. The scheme uses two variables—namely, k and N—and we fix one of them and treat the other one as a variable. For example, when N = 4, the figure clearly shows that we can determine the upper limit of resending attempts of nodes different hops from the sink.Figure 29
The number of required resending attempts of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92 in MPR scheme.Figure 30
Upper limit of the number of required resending attempts of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92 in ASTR scheme(N=4).It should also be noted that, in ASTR scheme, when the reliability is improved, the value ofN should be adjusted accordingly. For example, when the reliability is 0.95, the value of N should be increased to achieve the probability for the data to reach the sink required by the application q.Theorem 12.
Assuming the distance from the nodenx to the sink is l,l=hr+x, the MPR scheme is adopted and the reliability of the whole network is q, the data amount sent and the data amount received by node nx—Qh,x1,t and Qh,x1,r—are as follows: (38)Qh,x1,t=Mhhq+Mh+1hq·l+rl+Mh+2hq·l+2rl+⋯+Mh+zhq·l+zrl,Qh,x1,r=Qh,x1,t-Mhhq,Mhhq=log⁡1-qlog⁡1-ph,Mh+ihq=log⁡1-q⁡log⁡1-ph+i·pi.Proof.
According to Theorem11, the number of required resending attempts of nodes different hops from the sink Mhqh∈1,z is as follows:(39)Mhq=log⁡1-qlog⁡1-ph.
The data amount to be transmitted by nodenx can be calculated as follows. The node has a data packet which is h hops from the sink and should be sent to the sink, so the number of data packets that should be resent for one data packet is (40)Mhhq=Mhq=log⁡1-q⁡log⁡1-ph.
The number of required resending attempts of the data atl+ir is as follows: (41)Mh+iq=log⁡1-q⁡log⁡1-ph+i.
The number of data packets to be transmitted when the data has reached nodenx is as follows: (42)Mh+ihq=Mh+iq·pi.
There is(l+ir)/l data at l+ir, so the total number of data packets from sources with different distance from node nx and to be sent by node nx can be calculated as follows:(43)Qh,x1,t=Mhhq+Mh+1hq·l+rl+Mh+2hq·l+2rl+⋯+Mh+zhq·l+zrl.
The received data amount is calculated by deducting the data amount of the node itself from the data sent by the node; that is,Qh,x1,r=Qh,x1,t-Mhhq.Theorem 13.
Assuming the distance from the nodenx to the sink is l,l=hr+x, the ASTR scheme is adopted and the reliability of the whole network is q, the proportional coefficient of the size of abstract and data packets is μ, the data amount sent and the data amount received by node nx—Sh,x1,t and Sh,x1,r—are as follows: (44)Sh,x1,t=1+μN·whhq+wh+1hq·l+rl+wh+2hql+2rl+⋯+wh+zhq·l+zrl,Sh,x1,r=Sh,x1,t-1+μN·whhq,whhq=11-σh1-ph∗∑k=1a1-phσhk-1∗1-σhk1-phk1-σh1-ph-kσhk1-phk,where:σh=1-1-ph1+N,(45)wh+ihq=pi1-σh+i1-ph+i∗∑k=1a1-ph+iσh+ik-1∗1-σh+ik1-ph+ik1-σh+i1-ph+i-kσh+ik1-ph+ik,where:σh+i=1-1-ph+i1+N.Proof.
According to Theorem3, the number of required resending attempts of the node that is h hops from the sink whq (h∈1,z) is as follows:(46)whq=11-σh1-ph∗∑k=1a1-phσhk-1∗1-σhk1-phk1-σh1-ph-kσhk1-phk,whereσh=1-1-ph1+N.
The data amount to be transmitted by nodenx can be calculated as follows. The node has a data packet which is h hops from the sink and should be sent to the sink, so its expected data amount to be resent is as follows: (47)whhq=whq=11-σh1-ph∗∑k=1a1-phσhk-1∗1-σhk1-phk1-σh1-ph-kσhk1-phk,whereσh=1-1-ph1+N.
For data packet atl+ir, the expected number of resending attempts at the beginning is as follows: (48)wh+iq=11-σh+i1-ph+i∗∑k=1a1-ph+iσh+ik-1∗1-σh+ik1-ph+ik1-σh+i1-ph+i-kσh+ik1-ph+ik,whereσh+i=1-1-ph+i1+N.
The expected data amount to be transmitted when the data packet reaches nodenx is (49)wh+ihq=wh+iq·pi.
There is(l+ir)/l data at l+ir, each node sends 1 data packet and N abstracts each time and the proportional coefficient of the size of abstract and data packet is μ, so 1+μN data is sent. The total expected data amount from sources with different distance from node nx and to be sent by node nx can be calculated as follows: (50)Sh,x1,t=1+μN·whhq+wh+1hq·l+rl+wh+2hql+2rl+⋯+wh+zhq·l+zrl.
The received data amount is calculated by deducting the data amount of the node itself from the data sent by the node; that is,Sh,x1,r=Sh,x1,t-(1+μN)·whhq.The data amount sent and the data amount received by each node in MPR scheme and ASTR scheme are calculated according to Theorems7 and 8, respectively. The received data amount has no significant difference with the sent data amount, so we will directly compare the data amount sent by the node.Figure31 compares the data amount sent by each node in two schemes when the reliability of the whole network is 0.90 and 0.92. Figure 31 shows that the difference in data amount between the two schemes is more significant for a node closer to the sink. The data amount in MPR scheme is around twice the data amount in ASTR scheme, so the ASTR scheme can reduce the sent and received data amount while ensuring the network reliability, which both lowers the energy consumption and improves the network performance.Figure 31
Data amount sent by each node in two different schemes when the reliability of the whole network is 0.90 and 0.92.Figure31 shows that when the network reliability is improved, the data amount loaded by each node will also increase. When the network reliability is improved, the data amount loaded by each node will also increase. The data amount in MPR scheme is around 2.3 times that in ASTR scheme. Therefore, the improvement of the network reliability makes the advantage of ASTR scheme in performance more prominent.Figures32 and 34 compare the data amount reaching the sink in MPR scheme and ASTR scheme when the whole network has the same reliability. Figure 32 shows that the data amount reaching the sink in MPR scheme is more than that in ASTR scheme and the difference is increasingly significant as the reliability is improved. When q = 0.90, the data amount reaching the sink in MPR scheme is 53.95% more than that in ASTR scheme. This is because the node far from the sink has a larger number of resending attempts according to Theorem 12. The number of resending attempts is equivalent to the number of data packets and the data amount of one data packet is larger compared with the abstract, so many resent data packets are redundant. In our ASTR scheme, the data packet will be sent again when not received, so no data packet will be repetitively sent. The redundant data amount is completely produced by abstract which contains only small data amount, so the data amount reaching the sink and redundant data amount are both small. Figure 33 shows the percentage of redundant data packets in two schemes. The result is the same as the conclusion of preceding analysis: the percentage of redundant data is very high in MPR scheme and relatively low in ASTR scheme. Figure 33 also provides the information that as the reliability is improved, the redundancy of MPR scheme gradually increases. When the reliability is 0.90, the redundancy rate of MPR scheme even reaches 50.7%; on the contrary, the redundancy rate in ASTR scheme is gradually decreasing and reaches as low as 9% when the reliability is 0.90. So ASTR scheme can reduce the redundant data amount by 41.70%.Figure 32
Data amount reaching the sink and effective data amount in two schemes under different network reliability.Figure 33
Percentage of redundant data packets in two schemes.Figure 34
Percentage of redundant/effective data packets in two schemes.Figure35 is prepared based on the above related data. It compares the guaranteed network reliability in two schemes when the same data amount reaches the sink. The figure shows that when the data amount in ASTR scheme is slightly smaller than that in MPR scheme, the reliability is still 30% higher, so sending less data amount in ASTR scheme can ensure a higher reliability.Figure 35
Comparison of the guaranteed network reliability in two schemes when the same data amount reaches the sink (p=0.90).From this section, all experiment figures are prepared based on the reach rate of each hopp = 0.90. To explore the effect of the value of p on this experiment, we get the following three results. Figure 36 is obtained by repeating the same experiment as above when p = 0.80 and shows the guaranteed network reliability in two schemes when the same data amount reaches the sink. Compared with Figure 35, the data amount in both MPR scheme and ASTR scheme is improved, but the network performance in ASTR scheme is better because the guaranteed network reliability is about 23.23% higher than that in MPR scheme.Figure 36
Comparison of the guaranteed network reliability in two schemes when the same data amount reaches the sink (p=0.80).The meaning of Figure37 lies in comparing the guaranteed network reliability in two schemes when 40 data packets reach the sink with different value of p. The figure shows that when p = 0.70, the reliability of ASTR scheme is 5% higher than that of MPR scheme; when p = 0.80, the reliability of ASTR scheme increases by 20%; when p = 0.90, the reliability of ASTR scheme increases by 29%. It is concluded that when p is larger, the guaranteed network reliability of the ASTR scheme is much higher than that of the MPR scheme, which presents the advantages of ASTR scheme more prominently.Figure 37
Comparison of guaranteed network reliability in two schemes when 40 data packets reach the sink with different value ofp.Figure38 shows the following: generally speaking, when the value of p is larger, the increase of data amount is smaller in two schemes. This is because when the value of p is small in MPR scheme, the packet loss ratio of each hop of the node far from the sink will be accumulated and multiple data packets should be sent to ensure the reliability of the whole network is equal to q; for example, when the reliability of the whole network is 0.70: if p = 0.70, the node that is 8 hops from the sink should send 21 data packets; if p = 0.80, the node should send 7 data packets; if p = 0.90, the node should send only 5 data packets. When the number of data packets decreases from 21 to 7 and from 7 to 5, the increase of data amount will fall, so a larger p will cause a smaller increase of data amount in MPR scheme. Similarly, in ASTR scheme, the packet loss ratio of node far from the sink will be accumulated, so the number of abstracts sent and the upper limit of sending attempts should be greatly improved to ensure the reliability of the whole network is q. Next we will analyze the cases when q = 0.80 and q = 0.70. When q increases from 0.70 to 0.80, the comparison of increased data amount in MPR scheme and ASTR scheme clearly shows that the increased data amount in ASTR scheme is much smaller than that in MPR scheme. This is because when the same value of p, for example, 0.70, is used and the network reliability increases from 0.70 to 0.80, the number of data packets sent by each node in MPR scheme will increase greatly; the upper limit of the number of sending attempts will also increase greatly in ASTR scheme, but the calculated number of expected sending attempts w has no apparent change and the increased data amount of abstract is very small compared with the data amount of data packet. Similarly, when q = 0.90 and q = 0.80, the increase of data amount in ASTR scheme is smaller than that in MPR scheme.Figure 38
Comparison of increased data amount whenq increases by 0.10 each time with different success rate of transmission of each hop.The meaning of Figure38 lies in the following: when p = 0.90, the required increase of data amount in MPR scheme is 7.5 times that in ASTR scheme to increase the network reliability from 0.80 to 0.90.


### 5.4. Performance Comparison in Trust Routing

This section analyzes the calculation of successful reach rate and compared the performance in two schemes when the trust routing is used; that is, the trust is improved.Theorem 14.
Assuming the distance from the node to the sink isl,l=hr+x, in MPR scheme and ASTR scheme and the node is h hops from the sink, the success rate is p before the trust routing is adopted and, after the trust routing is used, the increased trust is ∂ and the probability for each message to reach the sink is Ph, the successful reach rates of data packets in MPR scheme and ASTR scheme βM,hb and β1+N,hb are, respectively, (51)βM,hb=1-1-PhM,β1+N,hb=Ph∑k=1a1-Phσhbk-1,Ph=p+∂h,σhb=1-1-Ph1+N.Proof.
In MPR scheme, if a node ish hops from the sink, the probability for each message to reach the sink is Ph=ph, so the original success rate of routing is βM,ha=1-1-PhM; after the trust routing is used, the probability for each message to reach the sink is Ph=p+∂h, so the success rate of routing becomes βM,ha=1-1-PhM.
In ASTR scheme, if a node ish hops from the sink, the probability for each message to reach the sink is Ph=ph, so the original success rate of routing is (52)β1+N,ha=Ph+1-PhσhaPh+1-Ph2σha2Ph+⋯+1-Phk-1σhak-1Ph=Ph∑k=1a1-Phσhak-1,where:σha=1-1-Ph1+N.
After the trust routing is used, the probability for each message to reach the sink isPh=p+∂h, so the success rate of routing becomes (53)β1+N,hb=Ph+1-PhσhbPh+1-Ph2σhb2Ph+⋯+1-Phk-1σhbk-1Ph=Ph∑k=1a1-Phσhbk-1,where:σhb=1-1-Ph1+N.Figures39, 40, 41, and 42 are obtained in the same network as set in Figures 32–35 in the last section. After the trust routing is adopted, if p increases from 0.90 to 0.91, the trust routing method will improve the network reliability. The horizontal coordinate in Figure 39 shows that the reliability increases by 3%, which means the trust routing can improve the reliability of the whole network and thereby enhance the data security.Figure 39
Data amount reaching the sink and effective data amount in two schemes with different network reliability after the trust is improved (p=0.91).Figure 40
Redundancy rate in two schemes after the trust is improved.Figure 41
Redundancy rate/effective rate in two schemes after the trust is improved.Figure 42
Guaranteed network reliability in two schemes when the same data amount reaches the sink after the trust is improved (p=0.91).The meaning of Figure43 lies in the following: when the increase of trust ∂ is 0.01, 0.02, or 0.03, we use the ASTR scheme to ensure the same data amount reaches the sink and compare the guaranteed network reliability in three cases. Figure 43 shows that a larger ∂ will result in a higher reliability.Figure 43
Guaranteed network reliability in ASTR scheme with different trust when the same data amount reaches the sink.Figure44 compares the improvement of network reliability when p changes to 0.91, 0.92, and 0.93 after the trust routing is adopted and when p is 0.90 before the trust routing is adopted in ASTR scheme if the same data amount reaches the sink. The figure clearly shows that, after the trust routing is adopted, the network reliability is improved and a larger increase of trust ∂ will improve the reliability more significantly. We will select the path with a higher reliability when sending data packets to improve the probability for the data packets to reach the sink and reduce the packet loss ratio. As the network operates, the packet loss ratio will be increasingly low.Figure 44
Improvement of network reliability when the same data amount reaches the sink and the value ofp increases from 0.90 to 0.91, 0.92, and 0.93 in ASTR scheme.


## 5.1. The Calculation and Comparison of Data Amount

This section mainly compares the data amount loaded by nodes in the ASTR scheme proposed in this paper and other schemes and thereby demonstrates that the scheme proposed by this paper can effectively reduce the data amount loaded by nodes. Table3 shows all symbols used in this paper. Firstly, Theorem 1 provides the data amount loaded by nodes in the network where the data packets are transmitted as in a safe network though the network contains attackers that will cause packets loss.Table 3
Parameters related to the calculation.
Symbol
Description
R
Network radius
n
Total number of nodes in the area
r
Emission radius of nodes
h
Number of hops from a node to the base station
p
Success rate of each hop when each data packet is sent to the sink
n
x
Any node in the network
w
x
Width of the annular area where the nodenx is located
ρ
Distribution density of nodes in the network
ε
Network coefficientTheorem 1.
If packets loss ratio is 1-p, the data packet will be sent only once after data aggregation and the distance from the data packet to the sink is l, the data amount loaded by the node with l=hr+x can be calculated as follows: (10)Qx=ετ+δ+Γ·1+∑i=1zl+irl·pi∣z=R-lr.Proof.
As shown in Figure4, we should consider the data amount loaded by the wx wide annular area where the node is located. The annular area where the node nx is located will surely undertake the data transfer of nodes in wx wide annular areas at l+r,l+2r,…,l+zr. If wx is very small, the nodes in this area can be considered undertaking identical data amount. The area of annular area where the node nx is located is as follows: Snx=2πlwx
The total number of nodes in the area is(11)Nnx=Snx·ρ=2πρlwx.
It receives and transfers the data inl+ir∣i∈1,z area and the area and number of nodes of the annular area Vl+ir where l+ir is located are, respectively, (12)SVl+ir=2πl+irwx,NVl+ir=2πρl+irwx.
Similarly, the number of nodes of the areas whose data transfer is loaded byVl area: (13)2πρlwx+2πρl+rwx+2πρl+2rwx+⋯+2πρl+zrwx∣z=R-lr.
In a period, each node produces the following: one data packet, one ID packet, and one time axis. The size of data packet isτ, the size of ID packet is δ, and the size of time axis is Γ. Therefore, the data amount produced by a node in a period is τ+δ+Γ. Assume the aggregation is ε, but when the data packet is being transmitted to the base station, the probability for successful transmission of each hop is p and the node in area Vl+ir has a distance of i hops from i, so the probability of transmitting the data packet of Vl+ir area to area Vl is pi and the number of data packets of Vl+ir area loaded by the node in Vl area is 2πρl+irwx·pi. The data will time the aggregation coefficient after the data aggregation ε, so the data amount loaded by each node in Vl area can be calculated as follows: (14)Qx=ετ+δ+Γ·2πρlwx+∑i=1z2πρl+irwxpi2πρlwx=ετ+δ+Γ1+∑i=1zl+irl·pi.Figure 4
The data forwarding of each node.The ASTR scheme adopts theR(M,N) routing method. If the message received by the sink contains no data packet, the sink will notify the node to resend (M+N) message until the sink has received the data packet or the resending instances have reached the maximum value k. The following calculate the data amount of the R(M,N) routing method.Theorem 2.
Assume the node has a distance ofl from the sink, l=hr+x, the R(M,N) routing method is adopted, and the size of abstract is μ times of the size of data packet. If the number of hops of the abstract during horizontal routing is a random number in 1,d, and the data amount loaded by the node is as (15)Sx=MQx+Qx·pz+μN∑j=1d/2pj=M·ετ+δ+Γ·1+∑i=1zl+irl·pi+ετ+δ+Γ·1+∑i=1zl+irl·pi·pz+μN·∑j=1d/2pj∣z=R-lr.Proof.
Theorem1 shows that the data amount loaded by each node is Qx when one data packet is sent, so the data amount loaded by each node is MQx when M data packets are sent. Different from data packet, the abstract will be horizontally routed by d/2 hops during sending. Therefore, the incremental data amount loaded by each node is N∑j=1d/2pj and the data amount loaded by each node is Qx·pz+μN∑j=1d/2pj when N abstracts are sent.Theorem2 provides the data amount loaded by the node in the network which is l from the sink when the data aggregation is adopted with a packet loss ratio of 1-p and the R(M,N) routing method is used. It the MPR scheme is adopted, the data amount loaded by a node in the network is as shown in Figures 5–7. Figure 5 shows that, in MPR scheme, the data amount loaded by the node closed to the sink increases more rapidly with the increase of M because the node closer to the network center has to undertake all data packets routed from periphery of the network. Therefore, the energy of nodes near the sink will be consumed fast and the lifetime of the whole network is short. Figure 6 compares the data amount loaded by the node under different packet loss ratios. Figure 6 shows that when the success rate of successive transmission of each hop p decreases and the node still sends M data packets, the data amount loaded by each node will be reduced due to packet loss. Figure 6 also shows that if each node sends one less repetitive data packet and the success rate of transmission of each hop decreases by 0.1, the data amount has no change compared with the above. It should be noted that the success rate of transmission of each hop is positively correlated with the reliability of the whole network. Figure 7 compares the data amount in networks of different sizes. It shows that when other variables are all the same, the node in a larger network will undertake more data. Regardless of the network size, the broken line representing the data amount flattens at the same location which is 1 hop from the sink. According to the data, the nodes in a circle with the sink as the center and r as the radius undertake 45.87% of the total data amount of all nodes.Figure 5
Data amount loaded by a node in MPR scheme when the node sends different numbers of data packets(p=0.90).Figure 6
Data amount loaded by a node in MPR scheme with different success rate of transmission of each hop(R=300).Figure 7
Data amount loaded by a node in MPR scheme for network of different sizes (p = 0.90).It the ASTR scheme, that is,R(1,N), routing method is adopted and M=1 and N abstracts are sent, and the data amount loaded by a node in the network is as shown in Figure 8. Figure 8 shows that when the more abstracts are sent, the data amount will increase. During the comparison between Figures 8 and 5, the intersection of the broken line and longitudinal axis shows that the data amount is 115.56 when N = 5, smaller than the data amount 129.64 when M = 2, so the increase of number of abstracts has no significant impact on the data amount. Therefore, increasing the number of abstracts is a better scheme compared with increasing the number of data packets to improve the successful reach rate because the node closer to the sink undertakes less data amount, which will extend the lifetime of network and improve the network performance.Figure 8
Data amount loaded by a node in ASTR scheme when the node sends different number of abstracts (p = 0.90, M=1).Figure9 compares the data amount loaded by each node in ASTR scheme under different packet loss ratios. Figure 9 clearly shows that the increase in number of abstracts has no great impact on the data amount, but the increase of p will cause a significant increase of data amount. Figure 10 compares the data amount loaded by each node when M=1 and Nabstracts are sent.Figure 9
Data amount loaded by a node in ASTR scheme under different success rate of transmission of each hop (R=300; M=1).Figure 10
Data amount loaded by a node in ASTR scheme for network of different sizes (p=0.90; M=1).A comparison is conducted between the data amount in MPR scheme and ASTR scheme (see Figures5–7 versus Figures 8–10). In Figures 5–10, the experiment results show that, in ASTR scheme, the data amount loaded by a node decreases significantly, proving the effectiveness of the ASTR scheme.In Figures5–10, the comparison of data amount provides the comparison of data amount of the whole network. Two schemes adopt different parameters and have different data amount reaching the sink, so they are not compared under the same conditions. To effectively compare the performance of the two schemes, we compare the data amount loaded by each node under the same parameters when the data packet is only one hop from the sink.In ASTR scheme, assumeM = 1, N abstracts are sent, and the success rate of transmitting message for each hop is p. In this case, the probability for at least one message to reach the sink is σ=1-1-p(1+N) in ASTR scheme, where p represents the probability for the data packet to reach the sink. If the data packet is received, no resending is needed and the process will end; if no message is received, the sink will not know the sending of data packet and the process will also end. Otherwise, if the received message contains no data packet, the data packet will be resent and the number of packets sent for each time is also (1+N). The data packet will be sent for the second time when the first message is received but will contain no data packet and the probability of this case is (1-p)σ. In the second sending, the reach probability of data packet is still p and the probability of sending and receiving the data packet is (1-p)σp. Similarly, the data packet will be sent for the third attempt when the messages are successfully sent in the preceding two attempts but contain no data packet and the probability of this case is (1-p)2σ2. In the third sending, the reach probability of data packet is p and the probability of successively sending the message and receiving the data packet in the third attempt is (1-p)2σ2p. Therefore, the probability of the kth sending attempt is (1-p)k-1σk-1p.If the upper limit of number of sending attempts isk, the message can only be sent for k times in maximum. If the data packet has not been successfully sent at the kth attempt, it will not send again. If the data packet is successfully sent after less than k attempts, it will not be sent again either. In this case, the total success rate of sending of data packets is as follows: (16)β1+N=p+1-pσp+1-p2σ2p+⋯+1-pk-1σk-1p=p∑k=1a1-pσk-1,σ=1-1-p1+N.If the application requires a probability ofq for data to successively reach the sink, k should abide by the following formula:(17)β1+N=p∑k=1a1-pσk-1>q.Theorem 3.
In ASTR scheme, letM = 1, N abstracts are sent, the success rate of transmission of message of each hop is p, the node is on hop from the sink and the upper limit of the number of sending attempts is k, and the expected number of sending attempts can be calculated as follows:(18)w=11-σ1-p∗∑k=1a1-pσk-1∗1-σk1-pk1-σ1-p-kσk1-pk.Proof.
The probability of successively sending the data packet at one time isp and the number of sending attempts is 1; the first sending of data packet fails, the probability of successively sending at the second attempt is 1-pσp, and the number of sending attempts is 2; if the sending of data packet fails for two times, the probability of failure to send the data packet is (1-p)2σ2p and the number of sending attempts is 3.
The expected number of sending attempts is(19)w=1×pβ1+N+2×1-pσpβ1+N+3×1-p2σ2pβ1+N+⋯+k×1-pk-1σk-1pβ1+N=pβ1+N∗1-σ1-p∗1-σk1-pk1-σ1-p-kσk1-pk=11-σ1-p∗∑k=1a1-pσk-1∗1-σk1-pk1-σ1-p-kσk1-pk.Theorem 4.
In MPR scheme,M data packets are sent, the success rate of each hop of message transmission is p and the node is one hop from the sink, the actual number of data packets reaching the sink is (20)G=∑1Mi∗CMipi1-pM-i=Mp.
Assume the length of the data packet islm, and the total data amount is (21)Dm=G∗lm.Proof.
Only data packets are sent, so the probability for at least data packet to reach the sink is1-1-pM. In M attempts, the probability for only one data packet to reach the sink is CM1p∗(1-p)M-1, so the actual number of data packets sent when a data packet reaches the sink is 1CM1p∗(1-p)M-1; the probability for only two data packets to reach the sink is as follows: CM2p2∗(1-p)M-2, so the actual number of packets sent when two data packets reach the sink is as follows: 2CM2p2∗(1-p)M-2. Similarly, the actual number of data packets sent when M data packets reach the sink is as follows: MCMMpM∗1-pM-M=MpM. Therefore, when the data packet is sent for M times, the average number of data packets reaching the sink is G=∑1Mi∗CMipi1-pM-i. The length of each data packet is lm, so the total data amount is Dm=G∗lm.In MPR scheme, we take the method of routingM times and sending a packet each time. If we change it a little bit, we will get another scheme. In another scheme, we take the method of routing M times but each time c packets are sent. We call this scheme CMPR scheme. Deduction 5 is obtained by Theorem 4.Deduction 5.
In CMPR scheme, each timec packets are sent, cM data packets are sent in total, the success rate of each hop of message transmission is p, and the node is one hop from the sink, the actual number of data packets reaching the sink is (22)F=∑1cMi∗CcMipi1-pcM-i=cMp.
Assume the length of the data packet islm, and the total data amount is (23)dm=F∗lm.Proof.
Only data packets are sent, so the probability for at least data packet to reach the sink is1-1-pcM. In M attempts, the probability for only one data packet to reach the sink is CcM1p∗(1-p)cM-1, so the actual number of data packets sent when a data packet reaches the sink is 1CcM1p∗(1-p)cM-1; the probability for only two data packets to reach the sink is as follows: CcM2p2∗(1-p)cM-2, so the actual number of packets sent when two data packets reach the sink is as follows: 2CcM2p2∗(1-p)cM-2. Similarly, the actual number of data packets sent when cM data packets reach the sink is as follows: cMCcMcMpcM∗1-p0=cMpcM. Therefore, when the data packet is sent for M times, the average number of data packets reaching the sink is F=∑1cMi∗CcMipi1-pcM-i. The length of each data packet is lm, so the total data amount is dm=F∗lm.Theorem 6.
In ASTR scheme, letM = 1, N abstracts are sent, the success rate of each hop of message transmission is p, and the node is one hop from the sink. If the maximum number of resending attempts is km the actual number of data packets reaching the sink is (24)F=1+N∗w.Assume the length of each data packet is lm and the length of each abstract is ln, and the total data amount is (25)Dn=wlm+wNln.Proof.
In ASTR scheme, if 1 data packet andN abstracts are sent every time, the probability for at least one message to reach the sink is σ=1-1-p(1+N). It the data packet needs not to be sent again, the process will end; if no message is received, the sink will not know the sending of data packet and the process will also end; otherwise, if the message is received but contains no data packets, the message will be sent again and a (1+N) will be sent each time.
Therefore, the actual number of messages reaching the sink is1+N∗p when the data packet is successively sent at one time and 21+N∗1-pσp when the data packet is successively sent after two attempts. Similarly, the actual number of messages reaching the sink is k1+N∗(1-p)k-1σk-1p when the data packet is successively sent after k attempts and the average number of messages actually reaching the sink is as follows: F=1+N∗w (w is the expected sending attempts). Assume the length of each data packet is lm and the length of each abstract is ln, and the total data amount is Dn=wlm+wNln.Theorem 7.
If the success rate of each hop of message transmission isp and the node is one hop from the sink, the effective data amount received by the sink is (26)R=lm∗p.Proof.
The effective data amount is defined as the data amount of one data packet reaching the sink. There is a packet loss ratio, so the effective data amount is as follows:R=lm∗p.Theorem4 and Deduction 5 provide the actual data amount reaching the sink in MPR scheme and CMPR scheme. In the CMPR scheme, we let it send two packets at a time now. With different successful rate of transmission of each hop, Figures 11 and 12 can be gotten.Figure 11
The successful reach rate of MPR scheme and CMPR scheme with different value ofp when the number of sending times is 2, 3, 4, and 5, respectively c=2.Figure 12
The data amount of reaching the sink successfully of MPR scheme and CMPR scheme with different value ofp when the number of sending times is 2, 3, 4, and 5 c=2.Figures11 and 12 show that the successful reach rate of MPR scheme is very close to the successful reach rate of CMPR scheme, but the data amount of reaching the sink of MPR scheme is only half of the CMPR scheme. Therefore, the performance of MPR scheme is better under comprehensive consideration.Figures11 and 12 show the comparison between CMPR scheme and MPR scheme. The comparison of CMPR scheme and ASTR scheme is shown in Table 4.Table 4
The comparison between CMPR scheme and ASTR scheme whenc=2 and p=0.80.
CMPR scheme
ASTR scheme
The successful reach rate
Data amount of reaching the sink
The successful reach rate
Data amount of reaching the sink
0.9984
320
0.96
131.5241
0.999936
480
0.992
148.4281
0.999997
640
0.9984
162.1123
1
800
0.99968
174.9072As can be obtained from Table4, the CMPR scheme has improved the success rate of reaching the sink, but the limitation is that too many data packets are sent, so that the sink receives a lot of redundant data. Considering the comprehensive network condition, we do not think that CMPR scheme is a better scheme, so we will only compare MPR scheme and ASTR scheme.Theorems4 and 6 provide the actual data amount reaching the sink in MPR scheme and ASTR scheme. Figure 11 compares the data amount and effective data amount reaching the sink in two schemes when the probability for at least one data packet to reach the sink is 0.99, 0.999, 0.9999, and 0.99999.Figure13 clearly shows that as the application has higher requirement on the probability for data to reach the sink (increased from q = 0.99 to q = 0.99999), the data amount rises rapidly in MPR scheme. With the number of data packets sent plus one each time and assuming the length of a data packet is 100, the actual data amount reaching the sink will increase by 100∗p=90 each time; however, in ASTR scheme, the rise of data amount is very gentle. The number of abstracts increases by 1 each time and the number of expected sending attempts w changes insignificantly as N increases. Assuming the length of abstract is 10, the incremental data amount calculated following the formula in Theorem 6 is very small. The effective data amount calculated following Theorem 7 is 99, 99.9, 99.99, and 99.999, respectively.Figure 13
Actual data amount reaching the sink and effective data amount in two schemes whenp=0.90.Theorem7 proposes the concept of effective data. Currently, we can further propose the concept of redundant data amount which refers to part of the data amount actually reaching the sink and in excess of the effective data amount. Therefore, the redundant data amount reaching the sink in two schemes can be, respectively, calculated according to Figure 13 as follows: deducting the effective data amount from the actual data amount reaching the sink to get Figure 14 and dividing the redundant data amount by actual data amount reaching the sink to get Figure 15. Apparently, the redundant data amount and redundancy rate of the ASTR scheme are smaller than those of the MPR scheme because the ASTR scheme does not repetitively send very long data packets. Therefore, the ASTR scheme can both reduce the energy consumption of the network and extend the network lifetime.Figure 14
Comparison of redundant data amount between two schemes whenp=0.90.Figure 15
Comparison of data redundancy rate between two schemes whenp=0.90.Figures16, 17, and 18 show the experiment results when p = 0.80. According to the figures, the change of data amount is similar to the change when p = 0.90, which means the ASTR scheme has less redundant data amount and better performance than the MPR scheme regardless of the success rate of each hop of the transmission.Figure 16
Actual data amount reaching the sink and effective data amount in two schemes whenp=0.80.Figure 17
Comparison of redundant data amount between two schemes whenp=0.80.Figure 18
Comparison of data redundancy rate between two schemes whenp=0.80.Figures19 and 20 compare the probability for at least one data packet to reach the sink in MPR scheme and ASTR scheme when the actual data amount reaching the sink is the same. The experiment aims to visibly reflect the following: when consuming the same network resources, the ASTR scheme can achieve a higher probability for the sinker to receive at least one data packet compared with the MPR scheme. Figure 19 shows that when the data amount rises from 140 to 210 in ASTR scheme, the probability for at least one data packet to reach the sink increases rapidly and when the data amount reaches 210, the probability gets close to 1. To determine the causes of this condition more visibly, Figures 21 and 22 explain them clearly.Figure 19
Comparison of success rate of data transmission in two schemes when the actual data amount reaching the sink is the same.Figure 20
Difference between the success rate of data transmission in ASTR scheme and MPR scheme when the actual data amount reaching the sink is the same.Figure 21
Relationship betweenk,N and data amount (M=1) in ASTR scheme.Figure 22
Relationship betweenk,N and success rate of data transmission (M=1) in ASTR scheme.It is clear that the radian of cambered surface in Figure21 is small, but the radian of that in Figure 22 is large. The middle cambered surface has a large radian. When observing along the x-axis in two figures, we see the maximum number of sending attempts k ranges from 1 to 7, the data amount increases from 50 to 150, and the probability increases from 0 to 0.90, which demonstrates that, in ASTR scheme, increasing the number of sending attempts has significant effect on improving the probability while the data amount only increases a little. When the data amount increases to around 200, the probability has reached the saturated level. Therefore, we draw the conclusion: adopting the ASTR scheme can quickly achieve the purpose of data integrity with only small increment in data amount.


## 5.2. The Calculation and Comparison of Success Rate of Data Transmission

In this paper, the security of the network is not only related to data packets but also related to abstract. In this section, we analyze the overall probability for the sink to receive the data packet and abstract to verify that the data security can be improved under the ASTR scheme.Theorem8 and Deduction 9 show, respectively, the success rate for the data packet and abstract to reach the sink and the overall probability for the sink to receive the data packet and abstract when the success rate of the transmission of each hop is p and M data packets and N abstracts are sent at one time.Theorem 8.
Assume the success rate of each hop isp when each data packet is sent to the base station and the node sending the data packet is h hops from the base station. The number of hops is randomly selected from 1,d for horizontal routing of the abstract, so the expected length of horizontal routing is d/2 and its number of hops from the base station is h, the same as the data packet. Therefore, the average number of total hops sent by the abstract to the base station is h+d/2. Assume the number of data packets and abstracts is M, N, respectively. A1 means the sink fails to receive the data packet, A2 means the sink receives at least one data packet, A3 means the sink fails to receive the abstract, and A4 means the sink receives at least one abstract. f1M,h and f2M,h, respectively, represent the probability of case A1and case A2 and g1N,h,d and g2N,h,d, respectively, represent the probability of case A3 and case A4: (27)f1M,h=1-phM,∣caseA1,f2M,h=1-1-phM,∣caseA2,g1N,h,d=1-ph+d/2N,∣caseA3,g2N,h,d=1-1-ph+d/2N,∣caseA4.Proof.
Each data packet needsh hops when routed to the sink, so the probability for each data packet to successively reach the sink is ph and the probability for each data packet to fail in reaching the sink is 1-ph. Therefore, the probability for all of M data packets to fail in reaching the sink is 1-phM and the probability for the sink to receive at least one data packet is 1-1-phM. The distance of horizontal routing of abstract is 1,d, so the expected length of horizontal routing is d/2. The number of hops of the abstract from the base station is h, the same as the data packet, so the total expected length of sending one abstract to the base station is h+d/2. Therefore, the probability of successively routing each abstract to the sink is ph+d/2 and the probability of failing to route each data to the sink is 1-ph+d/2. Similarly, the probability for all of N data packets to fail in reaching the sink is 1-ph+d/2N and the probability for the sink to receive at least one data packet is 1-1-ph+d/2N.The overall probability for the sink to receive the data packet and abstract can be calculated based on the success rate of transmission of data packet and abstract, so Deduction9 can be obtained from Theorem 8.Deduction 9.
B
1 means the sink receives neither data packet nor abstract, B2 means the sink receives no data packet but receives at least one abstract, B3 means the sink receives no abstract but receives at least one data packet, and B4 means the sink receives at least one data packet and at least one abstract. φ1f1,g1,φ2f1,g2,φ3f2,g1, and φ4f2,g2, respectively, represent the probability of case B1, case B2, case B3, and case B4: (28)φ1f1,g1=1-phM∗1-ph+d/2N,∣caseB1,φ2f1,g2=1-phM∗1-1-ph+d/2N,∣caseB2,φ3f2,g1=1-1-phM∗1-ph+d/2N,∣caseB3,φ4f2,g2=1-1-phM∗1-1-ph+d/2N,∣caseB4.Proof.
According to Theorem8, whether the base station receives at least one data packet is independent of whether it receives at least one abstract, so the combined probability is the product of two probabilities; that is, φi,jfi,gj=fiM,h∗gjN,h,d.Deduction9 provides the occurrence probability of the cases in security analysis. The first case is that the sink receives neither data packet nor abstract. If we want to limit the probability of this case to <u, Deduction 10 can be obtained based on Deduction 9.Deduction 10.
Assume the success rate of each hop when each packet is sent to the sink, the number of hops for sending one abstract to the base station ish+d/2, the number of data packets is M, and the number of abstracts is N. To limit the probability for the sink to receive neither data packet nor abstract smaller than u, the values of M, N shall meet the following conditions: (29)M>log1-ph⁡u1-ph+d/2N,whenNis  a  fixed  value,N>log1-ph+d/2⁡u1-phM,whenMis  a  fixed  value.Proof.
According to Deduction9, the probability for the sink to receive neither data packet nor abstract is (30)φ1f1,g1=f1M,h×g1N,h,d=1-phM∗1-ph+d/2N.Now assume the value of N has been determined, 1-ph+d/2N is a constant, and the following inequation is obtained:(31)φ1f1,g1<u,i.e.1-phM∗1-ph+d/2N<u,and take the logarithm of both sides and obtain the following inequation:(32)M>log1-ph⁡u1-ph+d/2N.Similarly, assume the value of N has been determined, 1-phM is a constant, and the following inequation is obtained:(33)N>log1-ph+d/2⁡u1-phM.Figures23–26 provide the probability of the above four cases when the nodes different hops from the sink send the message to the sink with different values of parameters d,M, and N. The comparison between Figures 23 and 24 shows that when N increases by 1, the probability for the sink to receive no data packet but at least one abstract, represented by the red line, will increase and the probability for the sink to receive at least one data packet but no abstract, represented by the blue line, will decrease. According to Theorem 8, when the number of abstracts is larger, the probability for the sink to receive at least one abstract will increase. In addition, we can see that the probability for the sink to receive both data packet and abstract, represented by the green line, increases significantly, which means increasing the number of abstracts can achieve to the purpose of enhancing the data security. The comparison between Figures 23 and 25 shows that when the number of data packets and abstracts is increased by the same value, the relative probability of this case remains unchanged and the network achieves a very favorable reliability. Figure 26 shows the case where the number of hops is increased for horizontal routing of the abstract. With the four figures taken together, when M:N=1:1, the probability for the sink to receive the data packet but no abstract is larger than the probability for the sink to receive the abstract but no data packet; on the contrary, when M:N=1:2, the probability for the sink to receive the abstract but no data packet is larger than the probability for the sink to receive the data packet but no abstract. Increasing M,N improves the probability for the sink to receive both data packet and abstract.Figure 23
Probability of the four cases for nodes different hops from the sink(p=0.90,d=4,M=1, and N=1).Figure 24
Probability of the four cases for nodes different hops from the sink (p=0.90,d=4,M=1,andN=2).Figure 25
Probability of the four cases for nodes different hops from the sink (p=0.90,d=4,M=3,andN=3).Figure 26
Probability of the four cases for nodes different hops from the sink(p=0.90,d=8,M=1,andN=1).Figures27 and 28 are experiment figures prepared according to Deduction 10. The meaning of Deduction 10 is as follows: ensuring the probability for the sink to receive neither data packet nor abstract is lower than a very small value, fixing any one of M, N and alternating another variable to meet the above conditions. Figure 27 shows the minimum value obtained to meet the requirement on M when u is any value within 0.01~0.20 and N is fixed. Figure 27 shows clearly that when the distance of horizontal routing is 8, the node 10 hops from the sink have to send more data packets than the node 5 hops from the sink to guarantee a reach rate of smaller than u. In addition, when the number of hops from the sink is 5, the node whose distance of horizontal routing is 16 has to send more data packets than the node whose distance of horizontal routing is 8 to guarantee a reach rate of smaller than u. Each hop of the horizontal routing also has a packet loss ratio and more hops will decrease the reach rate of abstract. The value of N has been fixed, so the overall reach probability of both data packet and abstract can only be improved by increasing the value of M. Figure 28 shows the minimum value obtained to meet the requirement on N when the value of u is between 0.01 and 0.20 and the value of M is fixed.Figure 27
Minimum value ofM to meet the conditions when N is fixed.Figure 28
Minimum value ofN to meet the conditions when M is fixed.


## 5.3. Performance Comparison of the Whole Network with the Same Reliability

This section analyzes and compares the actual data amount reaching the sink in two schemes when the success rate of data transmission of all nodes in the whole network isq; that is, the whole network has the same reliability.Theorem 11.
Assuming the number of hops of nodenx from the sink, the MPR scheme is adopted, the reliability of the whole network is q and the success rate of each hop is p, and the number of resending attempts of nodes different hops from the sink are as follows: (34)Mhq=log⁡1-q⁡log⁡1-ph.Proof.
The success rate of each hop isp and the success rate that a message is successively sent to the sink is ph.
If the message is sent by the node forMhq times, the probability for at least one data packet to reach the sink is (35)1-1-pMhq,which is also the reliability of the network q, so the following equation is obtained: (36)q=1-1-pMhq.Take logarithm of both sides of the equation after transposition and obtain the following equation: (37)Mhq=log⁡1-qlog⁡1-ph.Figure29 shows the required resending attempts of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92, respectively. Figure 29 shows clearly that more resending attempts are required for the node farther from the sink because the node is more hops from the sink and each sink has a packet loss ratio; Figure 30 shows the number of maximum resending attempts k of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92, respectively, in our ASTR scheme. The scheme uses two variables—namely, k and N—and we fix one of them and treat the other one as a variable. For example, when N = 4, the figure clearly shows that we can determine the upper limit of resending attempts of nodes different hops from the sink.Figure 29
The number of required resending attempts of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92 in MPR scheme.Figure 30
Upper limit of the number of required resending attempts of nodes different hops from the sink to ensure the reliability of the whole network reaches 0.90 and 0.92 in ASTR scheme(N=4).It should also be noted that, in ASTR scheme, when the reliability is improved, the value ofN should be adjusted accordingly. For example, when the reliability is 0.95, the value of N should be increased to achieve the probability for the data to reach the sink required by the application q.Theorem 12.
Assuming the distance from the nodenx to the sink is l,l=hr+x, the MPR scheme is adopted and the reliability of the whole network is q, the data amount sent and the data amount received by node nx—Qh,x1,t and Qh,x1,r—are as follows: (38)Qh,x1,t=Mhhq+Mh+1hq·l+rl+Mh+2hq·l+2rl+⋯+Mh+zhq·l+zrl,Qh,x1,r=Qh,x1,t-Mhhq,Mhhq=log⁡1-qlog⁡1-ph,Mh+ihq=log⁡1-q⁡log⁡1-ph+i·pi.Proof.
According to Theorem11, the number of required resending attempts of nodes different hops from the sink Mhqh∈1,z is as follows:(39)Mhq=log⁡1-qlog⁡1-ph.
The data amount to be transmitted by nodenx can be calculated as follows. The node has a data packet which is h hops from the sink and should be sent to the sink, so the number of data packets that should be resent for one data packet is (40)Mhhq=Mhq=log⁡1-q⁡log⁡1-ph.
The number of required resending attempts of the data atl+ir is as follows: (41)Mh+iq=log⁡1-q⁡log⁡1-ph+i.
The number of data packets to be transmitted when the data has reached nodenx is as follows: (42)Mh+ihq=Mh+iq·pi.
There is(l+ir)/l data at l+ir, so the total number of data packets from sources with different distance from node nx and to be sent by node nx can be calculated as follows:(43)Qh,x1,t=Mhhq+Mh+1hq·l+rl+Mh+2hq·l+2rl+⋯+Mh+zhq·l+zrl.
The received data amount is calculated by deducting the data amount of the node itself from the data sent by the node; that is,Qh,x1,r=Qh,x1,t-Mhhq.Theorem 13.
Assuming the distance from the nodenx to the sink is l,l=hr+x, the ASTR scheme is adopted and the reliability of the whole network is q, the proportional coefficient of the size of abstract and data packets is μ, the data amount sent and the data amount received by node nx—Sh,x1,t and Sh,x1,r—are as follows: (44)Sh,x1,t=1+μN·whhq+wh+1hq·l+rl+wh+2hql+2rl+⋯+wh+zhq·l+zrl,Sh,x1,r=Sh,x1,t-1+μN·whhq,whhq=11-σh1-ph∗∑k=1a1-phσhk-1∗1-σhk1-phk1-σh1-ph-kσhk1-phk,where:σh=1-1-ph1+N,(45)wh+ihq=pi1-σh+i1-ph+i∗∑k=1a1-ph+iσh+ik-1∗1-σh+ik1-ph+ik1-σh+i1-ph+i-kσh+ik1-ph+ik,where:σh+i=1-1-ph+i1+N.Proof.
According to Theorem3, the number of required resending attempts of the node that is h hops from the sink whq (h∈1,z) is as follows:(46)whq=11-σh1-ph∗∑k=1a1-phσhk-1∗1-σhk1-phk1-σh1-ph-kσhk1-phk,whereσh=1-1-ph1+N.
The data amount to be transmitted by nodenx can be calculated as follows. The node has a data packet which is h hops from the sink and should be sent to the sink, so its expected data amount to be resent is as follows: (47)whhq=whq=11-σh1-ph∗∑k=1a1-phσhk-1∗1-σhk1-phk1-σh1-ph-kσhk1-phk,whereσh=1-1-ph1+N.
For data packet atl+ir, the expected number of resending attempts at the beginning is as follows: (48)wh+iq=11-σh+i1-ph+i∗∑k=1a1-ph+iσh+ik-1∗1-σh+ik1-ph+ik1-σh+i1-ph+i-kσh+ik1-ph+ik,whereσh+i=1-1-ph+i1+N.
The expected data amount to be transmitted when the data packet reaches nodenx is (49)wh+ihq=wh+iq·pi.
There is(l+ir)/l data at l+ir, each node sends 1 data packet and N abstracts each time and the proportional coefficient of the size of abstract and data packet is μ, so 1+μN data is sent. The total expected data amount from sources with different distance from node nx and to be sent by node nx can be calculated as follows: (50)Sh,x1,t=1+μN·whhq+wh+1hq·l+rl+wh+2hql+2rl+⋯+wh+zhq·l+zrl.
The received data amount is calculated by deducting the data amount of the node itself from the data sent by the node; that is,Sh,x1,r=Sh,x1,t-(1+μN)·whhq.The data amount sent and the data amount received by each node in MPR scheme and ASTR scheme are calculated according to Theorems7 and 8, respectively. The received data amount has no significant difference with the sent data amount, so we will directly compare the data amount sent by the node.Figure31 compares the data amount sent by each node in two schemes when the reliability of the whole network is 0.90 and 0.92. Figure 31 shows that the difference in data amount between the two schemes is more significant for a node closer to the sink. The data amount in MPR scheme is around twice the data amount in ASTR scheme, so the ASTR scheme can reduce the sent and received data amount while ensuring the network reliability, which both lowers the energy consumption and improves the network performance.Figure 31
Data amount sent by each node in two different schemes when the reliability of the whole network is 0.90 and 0.92.Figure31 shows that when the network reliability is improved, the data amount loaded by each node will also increase. When the network reliability is improved, the data amount loaded by each node will also increase. The data amount in MPR scheme is around 2.3 times that in ASTR scheme. Therefore, the improvement of the network reliability makes the advantage of ASTR scheme in performance more prominent.Figures32 and 34 compare the data amount reaching the sink in MPR scheme and ASTR scheme when the whole network has the same reliability. Figure 32 shows that the data amount reaching the sink in MPR scheme is more than that in ASTR scheme and the difference is increasingly significant as the reliability is improved. When q = 0.90, the data amount reaching the sink in MPR scheme is 53.95% more than that in ASTR scheme. This is because the node far from the sink has a larger number of resending attempts according to Theorem 12. The number of resending attempts is equivalent to the number of data packets and the data amount of one data packet is larger compared with the abstract, so many resent data packets are redundant. In our ASTR scheme, the data packet will be sent again when not received, so no data packet will be repetitively sent. The redundant data amount is completely produced by abstract which contains only small data amount, so the data amount reaching the sink and redundant data amount are both small. Figure 33 shows the percentage of redundant data packets in two schemes. The result is the same as the conclusion of preceding analysis: the percentage of redundant data is very high in MPR scheme and relatively low in ASTR scheme. Figure 33 also provides the information that as the reliability is improved, the redundancy of MPR scheme gradually increases. When the reliability is 0.90, the redundancy rate of MPR scheme even reaches 50.7%; on the contrary, the redundancy rate in ASTR scheme is gradually decreasing and reaches as low as 9% when the reliability is 0.90. So ASTR scheme can reduce the redundant data amount by 41.70%.Figure 32
Data amount reaching the sink and effective data amount in two schemes under different network reliability.Figure 33
Percentage of redundant data packets in two schemes.Figure 34
Percentage of redundant/effective data packets in two schemes.Figure35 is prepared based on the above related data. It compares the guaranteed network reliability in two schemes when the same data amount reaches the sink. The figure shows that when the data amount in ASTR scheme is slightly smaller than that in MPR scheme, the reliability is still 30% higher, so sending less data amount in ASTR scheme can ensure a higher reliability.Figure 35
Comparison of the guaranteed network reliability in two schemes when the same data amount reaches the sink (p=0.90).From this section, all experiment figures are prepared based on the reach rate of each hopp = 0.90. To explore the effect of the value of p on this experiment, we get the following three results. Figure 36 is obtained by repeating the same experiment as above when p = 0.80 and shows the guaranteed network reliability in two schemes when the same data amount reaches the sink. Compared with Figure 35, the data amount in both MPR scheme and ASTR scheme is improved, but the network performance in ASTR scheme is better because the guaranteed network reliability is about 23.23% higher than that in MPR scheme.Figure 36
Comparison of the guaranteed network reliability in two schemes when the same data amount reaches the sink (p=0.80).The meaning of Figure37 lies in comparing the guaranteed network reliability in two schemes when 40 data packets reach the sink with different value of p. The figure shows that when p = 0.70, the reliability of ASTR scheme is 5% higher than that of MPR scheme; when p = 0.80, the reliability of ASTR scheme increases by 20%; when p = 0.90, the reliability of ASTR scheme increases by 29%. It is concluded that when p is larger, the guaranteed network reliability of the ASTR scheme is much higher than that of the MPR scheme, which presents the advantages of ASTR scheme more prominently.Figure 37
Comparison of guaranteed network reliability in two schemes when 40 data packets reach the sink with different value ofp.Figure38 shows the following: generally speaking, when the value of p is larger, the increase of data amount is smaller in two schemes. This is because when the value of p is small in MPR scheme, the packet loss ratio of each hop of the node far from the sink will be accumulated and multiple data packets should be sent to ensure the reliability of the whole network is equal to q; for example, when the reliability of the whole network is 0.70: if p = 0.70, the node that is 8 hops from the sink should send 21 data packets; if p = 0.80, the node should send 7 data packets; if p = 0.90, the node should send only 5 data packets. When the number of data packets decreases from 21 to 7 and from 7 to 5, the increase of data amount will fall, so a larger p will cause a smaller increase of data amount in MPR scheme. Similarly, in ASTR scheme, the packet loss ratio of node far from the sink will be accumulated, so the number of abstracts sent and the upper limit of sending attempts should be greatly improved to ensure the reliability of the whole network is q. Next we will analyze the cases when q = 0.80 and q = 0.70. When q increases from 0.70 to 0.80, the comparison of increased data amount in MPR scheme and ASTR scheme clearly shows that the increased data amount in ASTR scheme is much smaller than that in MPR scheme. This is because when the same value of p, for example, 0.70, is used and the network reliability increases from 0.70 to 0.80, the number of data packets sent by each node in MPR scheme will increase greatly; the upper limit of the number of sending attempts will also increase greatly in ASTR scheme, but the calculated number of expected sending attempts w has no apparent change and the increased data amount of abstract is very small compared with the data amount of data packet. Similarly, when q = 0.90 and q = 0.80, the increase of data amount in ASTR scheme is smaller than that in MPR scheme.Figure 38
Comparison of increased data amount whenq increases by 0.10 each time with different success rate of transmission of each hop.The meaning of Figure38 lies in the following: when p = 0.90, the required increase of data amount in MPR scheme is 7.5 times that in ASTR scheme to increase the network reliability from 0.80 to 0.90.


## 5.4. Performance Comparison in Trust Routing

This section analyzes the calculation of successful reach rate and compared the performance in two schemes when the trust routing is used; that is, the trust is improved.Theorem 14.
Assuming the distance from the node to the sink isl,l=hr+x, in MPR scheme and ASTR scheme and the node is h hops from the sink, the success rate is p before the trust routing is adopted and, after the trust routing is used, the increased trust is ∂ and the probability for each message to reach the sink is Ph, the successful reach rates of data packets in MPR scheme and ASTR scheme βM,hb and β1+N,hb are, respectively, (51)βM,hb=1-1-PhM,β1+N,hb=Ph∑k=1a1-Phσhbk-1,Ph=p+∂h,σhb=1-1-Ph1+N.Proof.
In MPR scheme, if a node ish hops from the sink, the probability for each message to reach the sink is Ph=ph, so the original success rate of routing is βM,ha=1-1-PhM; after the trust routing is used, the probability for each message to reach the sink is Ph=p+∂h, so the success rate of routing becomes βM,ha=1-1-PhM.
In ASTR scheme, if a node ish hops from the sink, the probability for each message to reach the sink is Ph=ph, so the original success rate of routing is (52)β1+N,ha=Ph+1-PhσhaPh+1-Ph2σha2Ph+⋯+1-Phk-1σhak-1Ph=Ph∑k=1a1-Phσhak-1,where:σha=1-1-Ph1+N.
After the trust routing is used, the probability for each message to reach the sink isPh=p+∂h, so the success rate of routing becomes (53)β1+N,hb=Ph+1-PhσhbPh+1-Ph2σhb2Ph+⋯+1-Phk-1σhbk-1Ph=Ph∑k=1a1-Phσhbk-1,where:σhb=1-1-Ph1+N.Figures39, 40, 41, and 42 are obtained in the same network as set in Figures 32–35 in the last section. After the trust routing is adopted, if p increases from 0.90 to 0.91, the trust routing method will improve the network reliability. The horizontal coordinate in Figure 39 shows that the reliability increases by 3%, which means the trust routing can improve the reliability of the whole network and thereby enhance the data security.Figure 39
Data amount reaching the sink and effective data amount in two schemes with different network reliability after the trust is improved (p=0.91).Figure 40
Redundancy rate in two schemes after the trust is improved.Figure 41
Redundancy rate/effective rate in two schemes after the trust is improved.Figure 42
Guaranteed network reliability in two schemes when the same data amount reaches the sink after the trust is improved (p=0.91).The meaning of Figure43 lies in the following: when the increase of trust ∂ is 0.01, 0.02, or 0.03, we use the ASTR scheme to ensure the same data amount reaches the sink and compare the guaranteed network reliability in three cases. Figure 43 shows that a larger ∂ will result in a higher reliability.Figure 43
Guaranteed network reliability in ASTR scheme with different trust when the same data amount reaches the sink.Figure44 compares the improvement of network reliability when p changes to 0.91, 0.92, and 0.93 after the trust routing is adopted and when p is 0.90 before the trust routing is adopted in ASTR scheme if the same data amount reaches the sink. The figure clearly shows that, after the trust routing is adopted, the network reliability is improved and a larger increase of trust ∂ will improve the reliability more significantly. We will select the path with a higher reliability when sending data packets to improve the probability for the data packets to reach the sink and reduce the packet loss ratio. As the network operates, the packet loss ratio will be increasingly low.Figure 44
Improvement of network reliability when the same data amount reaches the sink and the value ofp increases from 0.90 to 0.91, 0.92, and 0.93 in ASTR scheme.


## 6. Conclusions

Internet of Everything (IoE) [1–3] leverages the ubiquity of smart sensor-equipped devices such as sensor based devices, smartphones, and vehicle sensor devices to collect information at low cost and provide a new paradigm for solving the complex data sensing based applications from the significant demands of critical infrastructure such as surveillance systems, remote patient care systems in healthcare, intelligent traffic management, and automated vehicles in transportation environmental and weather monitoring systems. Despite its great potential in our lives, sensor based IoE also exposes users to new security threats, which can impact human users’ health and safety. Data authentication, as an important defense, can be used to prevent unauthorized attack in wireless sensor networks. In this paper, an aggregate signature based trust routing (ASTR) scheme is proposed to guarantee safe data collection in WSNs. Firstly, the aggregate signature approach is used to aggregate data and keep data integrity. Then, a R(M,N) routing method is proposed to improve the probability for the data to safely reach the sink and reduce the redundant data transmission in order to extend the network lifetime. The R(M,N) routing method overcomes the shortcomings of sending too much data and low data security in the past multipath routing. In R(M,N) routing, some lightweight abstracts are used to replace the heavy data, which is able to effectively reduce the network load and improve the routing security. Finally, the ASTR scheme adopts a trust routing method to further improve the security of routing. The results of our strict theoretical analysis show that the ASTR scheme can effectively increase the safe reach rate of data routing by 23.23%, reduce the data amount on the node by 53.95%, and reduce the redundant data amount by 41.70%.



---

*Source: 6328504-2018-01-23.xml*