# Secure Data Distribution Scheme with Two-Hop Survival Strategy for Unattended WSNs

Authors: Wei Cheng; Yong Li; Yi Jiang; Xipeng Yin
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

For distributed data storage in Unattended Wireless Sensor Networks (UWSNs), security issues have been focused on by extensive researches in recent years. In this paper, an enhanced, reliable, and secure data distribution scheme based on erasure codes for UWSNs is proposed, which adapt the MOVE-ONCE survival strategy. In the proposed scheme, two-hop neighbor set has been utilized as data shareholders of data distribution. Through the analysis, we can find that there is more number of candidate secure data holders in two-hop neighbor set than one-hop neighbor set. Thus our new scheme could further enhance both probabilistic Backward Secrecy (BSe) and the reliability on data retrieval. Theoretical analysis and dense simulations show advantages of our new scheme which is compared with several previous related schemes proposed for UWSNs.


---

## Body

## 1. Introduction

In the past decades, wireless sensor networks (WSNs) have attained tremendous attentions with development in microelectromechanical systems technology [1]. Unattended Wireless Sensor Networks (UWSNs) are the category of wireless sensor networks that operate without online data collecting entity. In UWSN, the mobile sink accesses network with irregular and even unpredictable frequency while data has to be secured by every node until the next visit of the mobile sink. This situation may happen for reasons as the sensing field is too far from the base station and sending data through intermediate nodes may result in weakening the security or increasing the energy consumption of the nodes close to the base station. UWSNs can be used typically for many military applications, where unattended underground, underwater, and airborne sensors are deployed in hostile environments to sense adversary activities [1–6]. A typical demonstration is LANdroids [7], where sensors are deployed in hostile environment, in order to collect some military information so as to upload it to affined vehicles upon their arrival.Compared with original WSNs, UWSNs have more challenges on security. Since the mobile sink accesses network periodically for information collection, each sensor node must hold its data of measurements for a definite time. Intervals between successive sink accesses could be potential periods of attacks. The major attacks that we are concerned with are mobile adversary, which is denoted as ADV hereafter. ADV may roam in UWSN periodically by compromising and releasing sensors to establish knowledge on sensing data while absence of mobile sink happens. As sensing data is stored and accumulated in these sensor nodes, Forward Secrecy (FSe) is a critical requirement, which is to guarantee that there would be no revelation on precompromise data when sensors are compromised. Furthermore, ADV might release compromised sensors and then go to compromise other sensors in UWSN. Therefore, Backward Secrecy (BSe) is the second requirement, which is to ensure that there would be no revelation on postcompromise data. Furthermore, data reliability, that is, to retain accumulated sensing data survival when partial sensors could not work, is also very critical [8–10].The main contribution of this paper is that we propose an enhanced secure data distribution scheme based on erasure codes, which adapt the MOVE-ONCE survival strategies. Our new scheme could further improve the probabilistic BSe and the reliability on data retrieval. Based on erasure codes scheme, well-designed values ofm and n could be chosen to maximize both security and reliability more efficiently. We show that our scheme could offer better FSe, enhanced probabilistic BSe, and data reliability through theoretical analysis and dense simulations.The organization of paper is as follows. Section2 gives some related works. In Section 3, network assumptions, adversary model, design goal, and evaluation metrics are presented. Section 4 provides the detailed description on design strategies and the proposed schemes. Security and efficiency of our scheme are analyzed in Section 5. Then, we evaluate the performance by numeric simulations in Section 6. Finally, Section 7 is the conclusion.


## 2. Related Work

To deal with FSe and BSe issues in UWSNs, Ma and Tsudik [3] proposed DISH protocol using key evolution and sensor cooperation to provide FSe and BSe, respectively. The proposed protocol involves each sensor sharing an initial key with the sink. At any time, sensors are either healthy or sick. Healthy sensors are currently not compromised and their current keys are unknown to the adversary, while adversary knows the current keys of all sick sensors. FSe is obtained via key evolution. To gain BSe, each sensor requests random contributions from a set of randomly selected peers and computes its next key based on its prior key and all received randomness. With this cooperative approach, a healthy sensor always keeps healthy, as long as it is not compromised directly; however, a sick sensor could become healthy if it receives randomness from healthy peers. DISH has been evaluated analytically and via simulations; one notable observation is that the ratio of sick to healthy sensors tends to stabilize after a few rounds.Di Pietro et al. [4] proposed a distributed self-healing scheme (POSH) which is based on proactive sensors cooperation. The core idea about POSH is that each sensor could supply the source of randomness for other sensors. Consequently, a sensor whose randomness is compromised could retrieve security and produce a new key unknown to ADV, if it acquires at least one “infusion” of randomness from a neighbor sensor whose randomness is secure and not currently compromised. Together with key evolution, POSH provides both FSe and BSe to deal with a powerful ADV.Although these two schemes above are proposed to achieve FSe and probabilistic BSe in an UWSN where all sensors and all communications are reliable, they could not be resilient enough to sensor failure. To address this issue, Wang et al. [8] adopt secret sharing and Reed-Solomon (RS) Codes [11], in which some portions of whole data shares need to recover original sensing data, increasing data redundancy to offer resilience to sensor failure.Since all these above schemes could not satisfy the overall secure and reliable requirements needed for UWSNs, Ren et al. [9, 10] proposed a data distributed scheme which is also based on RS Codes. Furthermore, Ren proposed an improved scheme considering that sensors might either be compromised or failing.As we discuss below, although Ren’s scheme could provide FSe, enhanced probabilistic BSe, and data reliability, it still has potential space to be improved; therefore, it could serve as a stepping stone for our work in this paper.


## 3. Problem Formulation

### 3.1. Network Assumptions

Assuming an UWSN which is composed ofN sensors, the set of the sensors is denoted by V={v1,v1,…,vn}; set of edges is denoted by E={e1,e2,…,em}, where sensor is denoted by vi(1≤i≤N), which could be modeled as undirected graph G(N,E). The sensor vi has neighbors that compose a set NBi and the two-hop neighbor that composes a set TH_NBi. There is a unique ID on each sensor node and sensor may perform some functionality and possess plenteous memory to store sensing data. There are two modes on communication: peer-to-peer message and local broadcasting. The pairwise keys between sensors are already deployed in UWSN [9, 10]. Message of local broadcasting on sensor vi could be received by sensors in NBi.These sensors are strategically deployed, while mobile sink (MS) that accesses the UWSN to gather information stored in sensors periodically and mobile adversary (ADV) can compromise the sensors to learn all secrets on sensors. Once information is collected, sensors could be reset to its original status where no MS exists. Thus, ADV’s attacks cannot be accumulative, so we focus on the discussion within one access interval, which could be denoted byT.


### 3.2. Adversary Model

The UWSNs impose some attacks on many aspects. Here, we just focus on an ADV that may cruise in the UWSN while the MS is absent. The ADV has the following abilities [3, 4, 10]:(1)
The ADV could compromisek sensors at most, where k<N, during access interval T without interfering communication between nodes, and it also would not amend any data on compromised sensors.(2)
The ADV could randomly choose some sensors to physically corrupt, such that these sensors may absolutely lose their functionality.(3)
The ADV could monitor all the communications between sensors. It could only eavesdrop between currently compromised sensors.Without loss of generality, we adopt the following assumption [4]:(1)
Time can be divided into several compromise rounds. At the end of every round, the ADV could choose a subset of at mostk sensor nodes to compromise during the following round. At the start of every round, this subset from the last round would be released and the new subset would be compromised.(2)
There is the same duration between compromise and collection rounds. Moreover, they are all synchronized.


### 3.3. Design Goals and Evaluation Metrics

In this paper, ADV is interested in stealing data stored on sensors without being detected and can also monitor the communications of the compromised sensor [9]. Thus, the design goals of our proposed scheme are to ensure security and reliability of sensing data, dealing with the attacks by ADV.As shown in Figure1, we assume that ADV compromises a sensor Si at round r1 and releases Si at round r2. Between r1 and r2, ADV is residing on Si, and this time interval can be defined as residing period Trp. Thus, FSe of Si is compromised if the data encrypted before r1 could be decrypted by ADV which obtains the secret during Trp. On the other hand, BSe of Si is compromised if the data encrypted after r2 can be decrypted by ADV which obtains the secret during Trp.Figure 1
Scenario of attacking by ADV in UWSN.We define the metrics to measure data confidentiality and data reliability.Data Confidentiality. As in Figure 1, we further make some subdivision on data confidentiality: secrecy of sensing data generated before r1 is defined as FSe, while secrecy of sensing data generated after r2 is defined as BSe [9, 10].Data Reliability. Distribution scheme should be enough resilient to failure of sensors so that sensing data could be retrieved even if some sensors have absolutely lost their functionalities.


## 3.1. Network Assumptions

Assuming an UWSN which is composed ofN sensors, the set of the sensors is denoted by V={v1,v1,…,vn}; set of edges is denoted by E={e1,e2,…,em}, where sensor is denoted by vi(1≤i≤N), which could be modeled as undirected graph G(N,E). The sensor vi has neighbors that compose a set NBi and the two-hop neighbor that composes a set TH_NBi. There is a unique ID on each sensor node and sensor may perform some functionality and possess plenteous memory to store sensing data. There are two modes on communication: peer-to-peer message and local broadcasting. The pairwise keys between sensors are already deployed in UWSN [9, 10]. Message of local broadcasting on sensor vi could be received by sensors in NBi.These sensors are strategically deployed, while mobile sink (MS) that accesses the UWSN to gather information stored in sensors periodically and mobile adversary (ADV) can compromise the sensors to learn all secrets on sensors. Once information is collected, sensors could be reset to its original status where no MS exists. Thus, ADV’s attacks cannot be accumulative, so we focus on the discussion within one access interval, which could be denoted byT.


## 3.2. Adversary Model

The UWSNs impose some attacks on many aspects. Here, we just focus on an ADV that may cruise in the UWSN while the MS is absent. The ADV has the following abilities [3, 4, 10]:(1)
The ADV could compromisek sensors at most, where k<N, during access interval T without interfering communication between nodes, and it also would not amend any data on compromised sensors.(2)
The ADV could randomly choose some sensors to physically corrupt, such that these sensors may absolutely lose their functionality.(3)
The ADV could monitor all the communications between sensors. It could only eavesdrop between currently compromised sensors.Without loss of generality, we adopt the following assumption [4]:(1)
Time can be divided into several compromise rounds. At the end of every round, the ADV could choose a subset of at mostk sensor nodes to compromise during the following round. At the start of every round, this subset from the last round would be released and the new subset would be compromised.(2)
There is the same duration between compromise and collection rounds. Moreover, they are all synchronized.


## 3.3. Design Goals and Evaluation Metrics

In this paper, ADV is interested in stealing data stored on sensors without being detected and can also monitor the communications of the compromised sensor [9]. Thus, the design goals of our proposed scheme are to ensure security and reliability of sensing data, dealing with the attacks by ADV.As shown in Figure1, we assume that ADV compromises a sensor Si at round r1 and releases Si at round r2. Between r1 and r2, ADV is residing on Si, and this time interval can be defined as residing period Trp. Thus, FSe of Si is compromised if the data encrypted before r1 could be decrypted by ADV which obtains the secret during Trp. On the other hand, BSe of Si is compromised if the data encrypted after r2 can be decrypted by ADV which obtains the secret during Trp.Figure 1
Scenario of attacking by ADV in UWSN.We define the metrics to measure data confidentiality and data reliability.Data Confidentiality. As in Figure 1, we further make some subdivision on data confidentiality: secrecy of sensing data generated before r1 is defined as FSe, while secrecy of sensing data generated after r2 is defined as BSe [9, 10].Data Reliability. Distribution scheme should be enough resilient to failure of sensors so that sensing data could be retrieved even if some sensors have absolutely lost their functionalities.


## 4. Strategies and Improved Scheme

### 4.1. Constrained Optimization on Data Distribution

Since symmetric encryption for data distribution could not provide BSe, it only retains as long as sensors rely on themselves for data security. Ren et al. [9, 10] proposed the constrained optimization scheme for data distribution, where BSe could be guaranteed probabilistically if sensor cooperates with its neighbors, while data reliability is achieved similarly if sensor cooperates with its neighbors in order to increase data redundancy. We discuss this scheme as follows.To provide FSe for sensor nodeSi, a simple way is to update the secret key Ki of it at every round by utilizing hash function: Kir=h(Kir-1). Due to one-way property of the hash functions, the key of previous rounds could not be derived by ADV. Thus, FSe of sensing data is achieved. The ADV which acquires secret key Kir,r∈[r1,r2], could derive future key used in the following rounds all the same. Therefore, when ADV returns back at the round r3(r3>r2), it could decrypt sensing data that was encrypted during interval [r2,r3] by mimicking key update.To deal with this issue, Ren et al. [9, 10] proposed an optimized scheme which is based on RS Codes. Assume each sensor has corresponding Probability Vector PVi=[Pi,1,Pi,2,…,Pi,nbi] to reflect security levels on its neighbor sensors in NBi, where Pi,j is the probability that sensor Si,j, which is one of the neighbor sensors of the sensor Si, is compromised in time interval T. Without loss of generality, Ren’s scheme further assumes Pi,1≤Pi,2≤⋯≤Pi,nbi, for simplification. Given a probability threshold value PThi, Si could choose t qualified neighbor sensors whose probabilities of being compromised are lower than the threshold value PThi, which can be denoted by a set NBqlfi={Si,1,Si,2,…,Si,t}, where these probabilities satisfy Pi,1≤Pi,2≤⋯≤Pi,t≤PThi. At last, the data distribution scheme of Si could be modeled as a constrained optimization problem:(1)minPrrecovim,n,s.t.Pi,j≤PThi,where Prrecovi(m,n) denotes the probability that original sensing data of Si is compromised. Depending on the redundancy factor τ, which is τ=n/m related (m,n) RS Codes [11], Ren’s scheme could be considered as two different cases:(1)
Maximum security without redundancy: under this situation, whereτ=1, Si encodes sensing data into n=t portions by (m,n) RS Codes and then distributes these portions to t qualified neighbor sensors in NBqlfi so that theADV must compromise these entire qualified neighbor sensors to obtain enough shareholders to recover sensing data.(2)
Maximum security with redundancy: under this situation, whereτ<1, Si encodes data by the (m,n) RS Codes similarly, where m<n. Si encodes sensing data into n portions (where n=t), and then these portions are distributed to t qualified neighbor sensors in NBqlfi. In this case, if k data portions are lost, where k≤n-m, original sensing data could be recovered all the same.We first set data redundancy as its upper bounder byτ<1+2/t, and then m could be chosen as(2)m>ntt+2.As too many qualified neighbor nodes may result in large communication and storage overhead, the tradeoff is that a required security level λi is given, which considers overhead on communication and storage, Si, could select aggregately n=te(te<t) sensor whose security levels are on the top, which satisfy (3) to distribute the sensing data(3)Prrecovim,n=∏j=1tePi,j≤λi.Since Si choose t qualified neighbor sensors, whose probabilities of being compromised are lower than threshold value PThi, from its neighbor set NBi, whether required security level λi can be archived depends on the security level of nodes in neighbor set NBi, which is the shareholder set for data distribution in this scheme. Therefore, if we increase the security level of nodes in shareholder set or find the higher security level shareholder set, compromised probability of original sensing data can be reduced efficiently. Motivated by this intuition, we propose the following improved data distribution scheme.


### 4.2. Improved with Survival Strategy

Based on the discussion in the above section, we now consider adapting the survival strategy to improve the data distribution scheme. From the network’s aspect, there are three intuitive strategies [2]:DO-NOTHING: the primal strategy is to do nothing; just leave sensing data resident on sensor which acquired it and simply wait for the MS.MOVE-ONCE: an alternative strategy is to move sensing data to another randomly selected sensor right after collection. These data then would be resident on their new data holders until MS access.KEEP-MOVING: the more complicated strategy is to move sensing data continuously; that is, at every round, every sensor moves its sensing data individually to another randomly picked sensor.Since Ren’s scheme [9, 10] can be considered as the data distribution which adapts the DO-NOTHING survival strategy, in this case neighbors of sensor with origin sensing data leave their data shares encoded by RS Codes resident on their own and wait for the MS; we would consider adapting yet another survival strategy to improve the security of data distribution scheme. As KEEP-MOVING is too heavy in the communication cost for sensor node, we choose MOVE-ONCE strategy, so that each neighbor sensor moves its data share to its neighbor sensor, which should be the two-hop neighbor of sensor with origin sensing data, right after first data distribution by RS Codes. In this case, the shareholders of data distribution are two-hop neighbor of sensor with origin sensing data, rather than sensors in neighbor set NBi in Ren’s scheme, so we define the two-hop neighbor set as TH_NBi. This scheme can be regarded as data distribution in a new range of candidate sensor, which may have more high security level sensors. We will discuss this in Section 5 for security analysis.


### 4.3. Scheme Description

The improved data distribution with MOVE-ONCE strategy is described as follows.Step 1 (network initialization).
Sensor nodes exchange their ID and prior security levelPj, which can be evaluated from feedback by MS. Then, sensor Si establishes a look-up neighborhood table which contains the information of two-hop neighbor as follows:ID;prior security level;immediate neighbor,
where immediate neighbor is the way that the sensor can send data to its two-hop neighbor.Step 2 (security initialization).
The MS adapts a specifically secure hash function denoted byh(), as well as the master key Km. Hash function and initial encryption key Ki are preloaded on each sensor by MS before the deployment of UWSN. Here, Ki=h(Km∥i). At the end of every round, encryption key Kir of current round r carries out key update as Kir=h(Kir-1); here Ki0=Ki.Step 3 (data encryption).
S
i produces the keyed hash value with key Kir at the current round, as MACir=h(Dir∥Kir), and then produces the plaintext data which is composed of sensing data Dir, MACir, and values r and Si, which can be denoted by(4)PLtextir=Dir∥MACir∥r∥Si.
And then this is encrypted by utilizing keyKir, which can be denoted by(5)EncTextir=EncKir,Dir∥MACir∥r∥Si.
Then,Dir is equipped in(6)EncMir=EncTextir,r∥Si.Step 4 (data shares generation).
S
i makes use of (mn) RS Code to encode EncTextir into n data shares denoted by(7)Dsir=dsi,1r,dsi,2r,…,dsi,nr.Step 5 (data distribution with sensor selection).
S
i selects n two-hop neighbors with high security in sensor set TH_NBi according to prior security level in the neighborhood table which is established in the network initialization. Then, it sends out one randomly picked distinct data share dsi,jr to two-hop neighbor sensor Sj through immediate neighbor sensor Sk, utilizing pairwise secret keys Ki,k and Kk,j to encrypt data packet severally.Step 6 (data reconstruction).
MS gathers anym survival data shares from these sensors and recovers sensing data based on (mn) RS Code during the period of MS visit to UWSN again.


## 4.1. Constrained Optimization on Data Distribution

Since symmetric encryption for data distribution could not provide BSe, it only retains as long as sensors rely on themselves for data security. Ren et al. [9, 10] proposed the constrained optimization scheme for data distribution, where BSe could be guaranteed probabilistically if sensor cooperates with its neighbors, while data reliability is achieved similarly if sensor cooperates with its neighbors in order to increase data redundancy. We discuss this scheme as follows.To provide FSe for sensor nodeSi, a simple way is to update the secret key Ki of it at every round by utilizing hash function: Kir=h(Kir-1). Due to one-way property of the hash functions, the key of previous rounds could not be derived by ADV. Thus, FSe of sensing data is achieved. The ADV which acquires secret key Kir,r∈[r1,r2], could derive future key used in the following rounds all the same. Therefore, when ADV returns back at the round r3(r3>r2), it could decrypt sensing data that was encrypted during interval [r2,r3] by mimicking key update.To deal with this issue, Ren et al. [9, 10] proposed an optimized scheme which is based on RS Codes. Assume each sensor has corresponding Probability Vector PVi=[Pi,1,Pi,2,…,Pi,nbi] to reflect security levels on its neighbor sensors in NBi, where Pi,j is the probability that sensor Si,j, which is one of the neighbor sensors of the sensor Si, is compromised in time interval T. Without loss of generality, Ren’s scheme further assumes Pi,1≤Pi,2≤⋯≤Pi,nbi, for simplification. Given a probability threshold value PThi, Si could choose t qualified neighbor sensors whose probabilities of being compromised are lower than the threshold value PThi, which can be denoted by a set NBqlfi={Si,1,Si,2,…,Si,t}, where these probabilities satisfy Pi,1≤Pi,2≤⋯≤Pi,t≤PThi. At last, the data distribution scheme of Si could be modeled as a constrained optimization problem:(1)minPrrecovim,n,s.t.Pi,j≤PThi,where Prrecovi(m,n) denotes the probability that original sensing data of Si is compromised. Depending on the redundancy factor τ, which is τ=n/m related (m,n) RS Codes [11], Ren’s scheme could be considered as two different cases:(1)
Maximum security without redundancy: under this situation, whereτ=1, Si encodes sensing data into n=t portions by (m,n) RS Codes and then distributes these portions to t qualified neighbor sensors in NBqlfi so that theADV must compromise these entire qualified neighbor sensors to obtain enough shareholders to recover sensing data.(2)
Maximum security with redundancy: under this situation, whereτ<1, Si encodes data by the (m,n) RS Codes similarly, where m<n. Si encodes sensing data into n portions (where n=t), and then these portions are distributed to t qualified neighbor sensors in NBqlfi. In this case, if k data portions are lost, where k≤n-m, original sensing data could be recovered all the same.We first set data redundancy as its upper bounder byτ<1+2/t, and then m could be chosen as(2)m>ntt+2.As too many qualified neighbor nodes may result in large communication and storage overhead, the tradeoff is that a required security level λi is given, which considers overhead on communication and storage, Si, could select aggregately n=te(te<t) sensor whose security levels are on the top, which satisfy (3) to distribute the sensing data(3)Prrecovim,n=∏j=1tePi,j≤λi.Since Si choose t qualified neighbor sensors, whose probabilities of being compromised are lower than threshold value PThi, from its neighbor set NBi, whether required security level λi can be archived depends on the security level of nodes in neighbor set NBi, which is the shareholder set for data distribution in this scheme. Therefore, if we increase the security level of nodes in shareholder set or find the higher security level shareholder set, compromised probability of original sensing data can be reduced efficiently. Motivated by this intuition, we propose the following improved data distribution scheme.


## 4.2. Improved with Survival Strategy

Based on the discussion in the above section, we now consider adapting the survival strategy to improve the data distribution scheme. From the network’s aspect, there are three intuitive strategies [2]:DO-NOTHING: the primal strategy is to do nothing; just leave sensing data resident on sensor which acquired it and simply wait for the MS.MOVE-ONCE: an alternative strategy is to move sensing data to another randomly selected sensor right after collection. These data then would be resident on their new data holders until MS access.KEEP-MOVING: the more complicated strategy is to move sensing data continuously; that is, at every round, every sensor moves its sensing data individually to another randomly picked sensor.Since Ren’s scheme [9, 10] can be considered as the data distribution which adapts the DO-NOTHING survival strategy, in this case neighbors of sensor with origin sensing data leave their data shares encoded by RS Codes resident on their own and wait for the MS; we would consider adapting yet another survival strategy to improve the security of data distribution scheme. As KEEP-MOVING is too heavy in the communication cost for sensor node, we choose MOVE-ONCE strategy, so that each neighbor sensor moves its data share to its neighbor sensor, which should be the two-hop neighbor of sensor with origin sensing data, right after first data distribution by RS Codes. In this case, the shareholders of data distribution are two-hop neighbor of sensor with origin sensing data, rather than sensors in neighbor set NBi in Ren’s scheme, so we define the two-hop neighbor set as TH_NBi. This scheme can be regarded as data distribution in a new range of candidate sensor, which may have more high security level sensors. We will discuss this in Section 5 for security analysis.


## 4.3. Scheme Description

The improved data distribution with MOVE-ONCE strategy is described as follows.Step 1 (network initialization).
Sensor nodes exchange their ID and prior security levelPj, which can be evaluated from feedback by MS. Then, sensor Si establishes a look-up neighborhood table which contains the information of two-hop neighbor as follows:ID;prior security level;immediate neighbor,
where immediate neighbor is the way that the sensor can send data to its two-hop neighbor.Step 2 (security initialization).
The MS adapts a specifically secure hash function denoted byh(), as well as the master key Km. Hash function and initial encryption key Ki are preloaded on each sensor by MS before the deployment of UWSN. Here, Ki=h(Km∥i). At the end of every round, encryption key Kir of current round r carries out key update as Kir=h(Kir-1); here Ki0=Ki.Step 3 (data encryption).
S
i produces the keyed hash value with key Kir at the current round, as MACir=h(Dir∥Kir), and then produces the plaintext data which is composed of sensing data Dir, MACir, and values r and Si, which can be denoted by(4)PLtextir=Dir∥MACir∥r∥Si.
And then this is encrypted by utilizing keyKir, which can be denoted by(5)EncTextir=EncKir,Dir∥MACir∥r∥Si.
Then,Dir is equipped in(6)EncMir=EncTextir,r∥Si.Step 4 (data shares generation).
S
i makes use of (mn) RS Code to encode EncTextir into n data shares denoted by(7)Dsir=dsi,1r,dsi,2r,…,dsi,nr.Step 5 (data distribution with sensor selection).
S
i selects n two-hop neighbors with high security in sensor set TH_NBi according to prior security level in the neighborhood table which is established in the network initialization. Then, it sends out one randomly picked distinct data share dsi,jr to two-hop neighbor sensor Sj through immediate neighbor sensor Sk, utilizing pairwise secret keys Ki,k and Kk,j to encrypt data packet severally.Step 6 (data reconstruction).
MS gathers anym survival data shares from these sensors and recovers sensing data based on (mn) RS Code during the period of MS visit to UWSN again.


## 5. Security Analysis

### 5.1. Forward Secrecy (FSe)

It is very hard that ADV could derive previous key from the current key it acquires as a characteristic of hash function. Hence, even if ADV compromised the sensors to get enough data portions, it only obtains the wholeEncTextir, but still it could not decrypt sensing data which are encrypted on previous rounds. Therefore, FSe is achieved, which is thesame as that in [9, 10].


### 5.2. Backward Secrecy (BSe)

The probabilistic BSe can be guaranteed which issimilar to that in Ren’s scheme [9, 10]. However, we will prove that our scheme outperforms it in BSe.Lemma 1.
BSe of sensorSi could be compromised, if and only if these conditions are met:(1)
the sensorSi is first compromised by the ADV;(2)
the ADV has the ability to compromisek sensor in UWSN, where k≥m;(3)
the ADV compromises at lowestmtwo-hop neighbor sensors of Si which store the corresponding data shares.If all three conditions are met, probability PrBSe_compi, where ADV compromises BSe of Si, can be expressed as follows:(8)PrBSe_compi=0k<m,∏j=1mPi,jPi≤PrBSecompi≤∏j=n-mmPi,jPik≥m,τ<1,Pi,j≤PThi,PrBSe_compi=∏j=1tPi,jPik≥m,τ=1,Pi,j≤PThi,where PThi is the probability threshold, τ is the redundancy factor, and Pi and Pi,j are the compromised probabilities of Si and itstwo-hop neighbor in interval T.Proof.
Since ADV could compromise the BSe if ADV could compromiseSi to obtain secret key Kir of it and could compromise simultaneity at lowest m two-hop neighbor sensors of Si which store data shares to recover EncTextir, the ADV can use Kir to decrypt EncTextir to get PLtextir. According to Lemma 1, one can get that(9)PrBSe_compi=PrC1·PrC2·PrC3,where C1, C2, and C3 refer to conditions (1), (2), and (3), respectively. We can observe that the proof is similar to that in Ren’s scheme [9, 10], so we omit the analysis on BSe for different redundancy factor and focus on the proof that our scheme outperforms Ren’s scheme in BSe.
Since the major difference between our scheme and Ren’s scheme is the candidate shareholder set of data distribution, two-hop neighbor set versus one-hop neighbor set, it is important to show which candidate set is better in this context.Lemma 2.
Assuming sensors are distributed in deployment region uniformly, the expected number of two-hop neighbors is higher than that of one-hop neighbors with different node degree.Proof.
We will prove Lemma2 according to the mathematic model in [12]. Assume N sensors distributed in the deployment region uniformly, and then arbitrary sensor Si could cover nb1 sensors within one hop on the average(10)nb1=π·R2·ρ-1=degS,where node density ρ in the scenario is strongly linked to the node degree deg⁡(S) of the sensors, which is the node degree of the sensor. These nb1 sensors compose its one-hop neighbor set. Let Sj be another arbitrary sensor whose distance to Si is d. When d≤R, Sj is the one-hop neighbor of Si; when d>2R, Sj could not be connected by Si within two hops. Hence, Sj is the two-hop neighbor of Si if the following conditions are met: (1)
R<d≤2R;(2)
Si and Si share at least one one-hop neighbor as immediate neighbor.AssumeE1 is the event that R<d≤2R, which satisfies condition (1), and let E2 be the event that Si and Sj have at least one common immediate neighbor (SA,SB) which satisfies condition (2). Given R<d≤2R, PrE2∣E1 is equal to the probability that there are at least one of nb1 immediate neighbors of Si falls into the area covered simultaneously by Si and Sj. That overlapping area is denoted by Ao, as shown in Figure 2. Then, there is(11)PrE2∣E1=1-1-Aoπ·R2nb1=1-1-Aoπ·R2deg⁡S.Here, Ao is defined as (12)Ao=2R2arccos⁡d2R-d24R2-d2.Based on (11), P2e which is the expected value on PrE2∣E1 throughout the annulus area from R to 2R (as in Figure 2) can be represented by(13)P2e=1Aa∫AaPrE2∣E1dxdy=∫02πdθ∫R2R1-1-Ao/πR2deg⁡Srdr4πR2-πR2=23∫121-1-2arccos⁡r/2-r/24-r2πdeg⁡Srdr.Therefore, nb2 which is the expected number of two-hop neighbors of Si can be represented by(14)nb2=3πR2·ρ·P2e=3deg⁡S+1·P2e.Figure 2
Effective two-hop neighbor.The expected number for one-hop and two-hop neighbors,nb1 and nb2, with different node degree is shown in Figure 3. We can find that as expected a high node degree offers more possibilities to find two-hop neighbor, and the number of two-hop neighbors is much higher than one-hop neighbors with the increase of the node degree, so Lemma 2 is proved.Figure 3
Excepted number of one-hop and two-hop neighbors.Since there are more sensors in two-hop neighbor set than one-hop neighbor set, the sensors with different compromise probability are distributed uniformly, and we can deduce that two-hop neighbor set offers more possibilities to find sensors with high security level to become the data shareholders. Overall, two-hop neighbor set is better candidate shareholder than one-hop neighbor set for security of data distribution, and then our scheme outperforms Ren’s scheme in BSe.


### 5.3. Data Reliability

MS could recover original sensing data when the number of failure sensorsn is lower than the threshold numbern-m. Thus, probability of recovering data as function of sensor failures can be expressed as(15)Prres_f=1-∑t=n-m+1nCntPrft1-Prfn-t,where Prf denotes the probability that the sensors cause random failure.


### 5.4. Efficiency

We follow the same way as in [9, 10] to analyse the proposed scheme’s performance in respect of the cost of computation and communication overhead, as well as storage overhead.Computation Cost. By comparison of detailed scheme description, we can directly find that the total cost of computation at the data source sensor in the proposed scheme is the same as Ren’s scheme.Storage and Communication Overhead. The increased overhead on storage which is caused by our improvement is the size of neighborhood table: two-hop neighbor set is larger than two-hop neighbor set as in the analysis in Section 5.2. Otherwise, the total communication overhead of the proposed scheme is twice as much as Ren’s scheme. Hence, we improve the security of data distribution at the cost of storage and communication overhead.


## 5.1. Forward Secrecy (FSe)

It is very hard that ADV could derive previous key from the current key it acquires as a characteristic of hash function. Hence, even if ADV compromised the sensors to get enough data portions, it only obtains the wholeEncTextir, but still it could not decrypt sensing data which are encrypted on previous rounds. Therefore, FSe is achieved, which is thesame as that in [9, 10].


## 5.2. Backward Secrecy (BSe)

The probabilistic BSe can be guaranteed which issimilar to that in Ren’s scheme [9, 10]. However, we will prove that our scheme outperforms it in BSe.Lemma 1.
BSe of sensorSi could be compromised, if and only if these conditions are met:(1)
the sensorSi is first compromised by the ADV;(2)
the ADV has the ability to compromisek sensor in UWSN, where k≥m;(3)
the ADV compromises at lowestmtwo-hop neighbor sensors of Si which store the corresponding data shares.If all three conditions are met, probability PrBSe_compi, where ADV compromises BSe of Si, can be expressed as follows:(8)PrBSe_compi=0k<m,∏j=1mPi,jPi≤PrBSecompi≤∏j=n-mmPi,jPik≥m,τ<1,Pi,j≤PThi,PrBSe_compi=∏j=1tPi,jPik≥m,τ=1,Pi,j≤PThi,where PThi is the probability threshold, τ is the redundancy factor, and Pi and Pi,j are the compromised probabilities of Si and itstwo-hop neighbor in interval T.Proof.
Since ADV could compromise the BSe if ADV could compromiseSi to obtain secret key Kir of it and could compromise simultaneity at lowest m two-hop neighbor sensors of Si which store data shares to recover EncTextir, the ADV can use Kir to decrypt EncTextir to get PLtextir. According to Lemma 1, one can get that(9)PrBSe_compi=PrC1·PrC2·PrC3,where C1, C2, and C3 refer to conditions (1), (2), and (3), respectively. We can observe that the proof is similar to that in Ren’s scheme [9, 10], so we omit the analysis on BSe for different redundancy factor and focus on the proof that our scheme outperforms Ren’s scheme in BSe.
Since the major difference between our scheme and Ren’s scheme is the candidate shareholder set of data distribution, two-hop neighbor set versus one-hop neighbor set, it is important to show which candidate set is better in this context.Lemma 2.
Assuming sensors are distributed in deployment region uniformly, the expected number of two-hop neighbors is higher than that of one-hop neighbors with different node degree.Proof.
We will prove Lemma2 according to the mathematic model in [12]. Assume N sensors distributed in the deployment region uniformly, and then arbitrary sensor Si could cover nb1 sensors within one hop on the average(10)nb1=π·R2·ρ-1=degS,where node density ρ in the scenario is strongly linked to the node degree deg⁡(S) of the sensors, which is the node degree of the sensor. These nb1 sensors compose its one-hop neighbor set. Let Sj be another arbitrary sensor whose distance to Si is d. When d≤R, Sj is the one-hop neighbor of Si; when d>2R, Sj could not be connected by Si within two hops. Hence, Sj is the two-hop neighbor of Si if the following conditions are met: (1)
R<d≤2R;(2)
Si and Si share at least one one-hop neighbor as immediate neighbor.AssumeE1 is the event that R<d≤2R, which satisfies condition (1), and let E2 be the event that Si and Sj have at least one common immediate neighbor (SA,SB) which satisfies condition (2). Given R<d≤2R, PrE2∣E1 is equal to the probability that there are at least one of nb1 immediate neighbors of Si falls into the area covered simultaneously by Si and Sj. That overlapping area is denoted by Ao, as shown in Figure 2. Then, there is(11)PrE2∣E1=1-1-Aoπ·R2nb1=1-1-Aoπ·R2deg⁡S.Here, Ao is defined as (12)Ao=2R2arccos⁡d2R-d24R2-d2.Based on (11), P2e which is the expected value on PrE2∣E1 throughout the annulus area from R to 2R (as in Figure 2) can be represented by(13)P2e=1Aa∫AaPrE2∣E1dxdy=∫02πdθ∫R2R1-1-Ao/πR2deg⁡Srdr4πR2-πR2=23∫121-1-2arccos⁡r/2-r/24-r2πdeg⁡Srdr.Therefore, nb2 which is the expected number of two-hop neighbors of Si can be represented by(14)nb2=3πR2·ρ·P2e=3deg⁡S+1·P2e.Figure 2
Effective two-hop neighbor.The expected number for one-hop and two-hop neighbors,nb1 and nb2, with different node degree is shown in Figure 3. We can find that as expected a high node degree offers more possibilities to find two-hop neighbor, and the number of two-hop neighbors is much higher than one-hop neighbors with the increase of the node degree, so Lemma 2 is proved.Figure 3
Excepted number of one-hop and two-hop neighbors.Since there are more sensors in two-hop neighbor set than one-hop neighbor set, the sensors with different compromise probability are distributed uniformly, and we can deduce that two-hop neighbor set offers more possibilities to find sensors with high security level to become the data shareholders. Overall, two-hop neighbor set is better candidate shareholder than one-hop neighbor set for security of data distribution, and then our scheme outperforms Ren’s scheme in BSe.


## 5.3. Data Reliability

MS could recover original sensing data when the number of failure sensorsn is lower than the threshold numbern-m. Thus, probability of recovering data as function of sensor failures can be expressed as(15)Prres_f=1-∑t=n-m+1nCntPrft1-Prfn-t,where Prf denotes the probability that the sensors cause random failure.


## 5.4. Efficiency

We follow the same way as in [9, 10] to analyse the proposed scheme’s performance in respect of the cost of computation and communication overhead, as well as storage overhead.Computation Cost. By comparison of detailed scheme description, we can directly find that the total cost of computation at the data source sensor in the proposed scheme is the same as Ren’s scheme.Storage and Communication Overhead. The increased overhead on storage which is caused by our improvement is the size of neighborhood table: two-hop neighbor set is larger than two-hop neighbor set as in the analysis in Section 5.2. Otherwise, the total communication overhead of the proposed scheme is twice as much as Ren’s scheme. Hence, we improve the security of data distribution at the cost of storage and communication overhead.


## 6. Performance Evaluation

We adopt our proposed scheme on Ren’s simulator [13] for comparison, and then we show several numerical results through dense simulations. We set an UWSN, where 200 sensors are distributed randomly in a 500 m by 500 m region. Transmission range (TR) of every sensor is equal to 60 m. The final results by simulations are averaged among the 100 randomly deployed UWSNs. Sensors are divided into 4 groups with different compromised probability Pi: 20% of sensors with probability Pi=0.5; 30% of sensors with Pi=0.4; 30% of sensors with Pi=0.2; and 20% of sensors with Pi=0.1, respectively. Probability threshold value is set as PThi=0.3 for proposed sensor selection, which means that sensors with Pi>PThi are considered too risky to be the shareholders for sensing data and will not be chosen within the sensor selection scheme. Besides, the required security level is fixed as λi=0.001. We conduct these simulations to compare our proposed scheme, Wang’s scheme [8], Ren’s scheme [9], and a naive scheme where data is encrypted by keyed hash value without distribution security mechanism.As shown in Figures4–6, we can observe that our proposed scheme could achieve best probabilistic BSe compared to Wang’s scheme [8], Ren’s scheme [9], and the naive scheme [9], whatever redundancy factor τ is. That observation nicely agrees with all discussions in Section 5.2 where two-hop neighbor set is the better candidate shareholder than one-hop neighbor set for security of data distribution, and then our scheme outperforms other schemes in BSe.Figure 4
BSe for data distribution without redundancy.Figure 5
BSe for data distribution with redundancy.Figure 6
BSe versus number of one-hop neighbors.As shown in Figures7–9, we can observe that our proposed scheme could achieve the best data reliability only when data distribution is carried out with redundancy. When τ<1, our proposed scheme could obtain the highest probability on data reliability. However, when τ=1, Wang’s scheme, Ren’s scheme, and our proposed scheme all have lower probabilities than naive scheme on data reliability. This observation shows that maximum security without redundancy could not guarantee data reliability, so that original sensing data could not be recovered when just one data portion is lost.Figure 7
Data reliability without redundancy.Figure 8
Data reliability with redundancy.Figure 9
Data reliability versus number of one-hop neighbors.Since all these sensors are distributed randomly in these simulations, the number of one-hop neighbor sensors might be different, which may influence both BSe and reliability. These effects on BSe and data reliability in UWSN are shown in Figures6 and 9. We can observe that our proposed scheme holds the best performance on data reliability no matter how nb1 are specified in the case of τ<1. That is because the number of one-hop neighbors causes effect on the number of two-hop neighbors, so as to affect data distribution with sensor selection. According to these results, when the required security level is given, it is quite simple to select the average number of neighbors while an UWSN is deployed with uniformly distributed sensors. The results demonstrate that our new proposed scheme holds the enhanced performance among all these previous studied schemes.


## 7. Conclusions

We propose a novel data distribution scheme based on erasure codes which adapt the MOVE-ONCE survival strategies. Two-hop neighbor set has been utilized as data shareholders in the proposed data distribution scheme. Since two-hop neighbor set is the better candidate shareholder than one-hop neighbor set for security of data distribution, our proposed scheme could further improve both the probabilistic BSe and the reliability of data acquisition. Numeric simulations show that the proposed approach outperforms several previous approaches developed for UWSNs.



---

*Source: 712598-2015-10-12.xml*