Information Technology Journal

Year: 2011 | Volume: 10 | Issue: 7 | Page No.: 1359-1366
DOI: 10.3923/itj.2011.1359.1366

An Efficient Data Delivery Mechanism by Exploring Multipath Routes for Wireless Sensor Networks

Zhiqiang Ruan and Xingming Sun

Abstract: This paper study the data delivery mechanisms that can with high probability thwarting node capture attacks in unattended or distributed wireless sensor networks. Classic cryptographic approaches are vulnerable to such attacks, mainly due to their deterministic nature. Because once the adversary compromises the sensor nodes, it can acquire the credential as well as the data collected and held by sensors. Furthermore, the adversary can easily insert bogus sensor readings or change the processing results and then use these keys to authenticate forged information. This study proposes and analyzes the application of Reed-Solomon (RS) codes to address the problem. In the proposed scheme, each sensor node encodes the original data into multiple redundancy data shares by applying predefined (n, k) RS codes and applies non-uniform allocation through multiple node-disjoint paths to the destination. Analysis and simulation results demonstrate that the proposed scheme is efficient and resilient against node capture attack.

Keywords: Wireless sensor network, data delivery, node capture, fault tolerant and probabilistic analysis

INTRODUCTION

Wireless sensor networks (WSNs) are envisioned to be extremely useful for a broad spectrum of emerging civil and military applications (Akyildiz et al., 2002), such as remote surveillance, hazard leak detection and battlefield sensing. Security issue is still in its early stage of development. Of the various possible security threats encountered in a wireless sensor networks, this study specifically interested in combating compromised-node attacks (Meng et al., 2008). Due to the unattended nature of WSNs, an adversary can physically compromise a subset of nodes to eavesdrop information; they can interfere with the normal operation of the network by actively disrupting, changing, or even paralyzing the functionality of a subset of nodes. One important feature that separates it from other adversarial models is its mobility (Ruan et al., 2010). Specifically, the adversary has one central goal: to prevent certain data collected by sensors from ever reaching the sink or provide forged information to mislead the user to make incorrect decisions.

Existing approaches are achieved by cryptographic techniques (Wei et al., 2007) or watermarking method (Wang et al., 2011). However, due to the limited resource of sensor nodes coupled with the unattended operation of such networks, an adversary who can potentially capture nodes, recover their cryptographic material. Internal adversaries (or compromised nodes) can further alter and insert bogus data and pose as an authorized node in the network. If the sensor networks deployed in hostile environment and always provides highly valuable information to the end user but when most of the information has been forged and misleads the user to make incorrect decisions (Ruan et al., 2010). Attaching message authentication codes can verify the modification of data but cannot verify its validity (Wang et al., 2011). In general, the conventional view of security based on cryptography and authentication alone is not sufficient to provide a complete solution for developing secure and dependable sensor data delivery mechanism due to the unique characteristics and novel misbehaviours encountered in unattended sensor networks.

The intent of this work is to develop an efficient in-network data delivery mechanism for sensor data, while simultaneously robust to stop forwarding as well as filtering out bogus data. The work is motivated from the well studied secret sharing and multipath routing. The strategy is for each node to partition the original data into multiple redundancy data shares by applying predefined Reed-Solomon (RS) codes (Goodson et al., 2004) and utilize non-uniform allocation of data shares through multiple node-disjoint paths to the sink. It is noted that the proposed scheme does not eliminate the utilization of any conventional cryptography approaches, such as data encryption and pairwise key establishment and it works as a complementary component to provide an enhanced security solution with the imperfect unattended WSN.

PRELIMINARIES

This section gives the preliminaries to be used in this study. For the sake of clarity and convenience description, the notations used in the following sections are given in Table 1.

The (n, k) codes are used to share secrets among n users, any k of which can recover the secret cooperatively. The Shamir scheme (Shamir, 1979) is one of such schemes. As pointed out in (Goodson et al., 2004), an RS code may be treated as a special (n, k) secret-sharing scheme with tamper-resistant capability, because it can correct errors.

Let GF(2^a) be the finite field of order 2^a such that each element in GF(2^a) can be represented by a bits. An (n, k) RS code is a linear code, where each symbol is in GF(2^a), with parameters: n = 2^a -1 and n-k = 2t, where n is the total number of code symbols in the coded block, k is the total number of information symbols and t is the symbol-error-correcting capability of the code. Let m(x) be the information polynomial represented as m(x) = m₀+m₁x+…+m_k-1x^k-1, where m_i is a a bits code.

The codeword polynomial c(x) corresponding to m(x) can be encoded as:

Where:

is the parity check polynomial and g(x) is a publicly known generator polynomial which can be obtained as:

where, β is a primitive element in GF(2^a) and g_iεGF(2^a), note that g(x) has β, β², …, β^2t as roots.

Since each symbol is represented by a bits, an (n, k) RS code can be expended to a (an, ak) binary linear block code. For example, a (17, 9) RS code with four symbol-error-correcting capabilities is of 8x9 = 72 information bits.

The computational cost of encoder is roughly k(n-k) additions and k(n-k) multiplications.

The decoding processes of RS code are more complex. Let r(x) = r₀+r₁x+...+r_k-1x^k-1, e(x) = e₀+e₁x+…+e_k-1x^k-1, c (x)=c₀+c₁x+…+c_k-1x^k-1, where e_i, r_i, r_i∈GF (2^a), r (x) is the received polynomial, e (x) is error polynomial and c (x) is original data polynomial, then e (x) = r (x)-c(x). From Eq. 1-3 it is known that the roots of g(x) must also be the roots of c (x), r (x) evaluated at each of the roots of g (x) should yield zero only when it is a valid codeword. Any errors will result in one or more of the computations yielding a nonzero result. The computation of a syndrome symbol can be described as follows:

If there exists v errors, where 0≤v≤t, in the unknown locations j₁, j₂, …, j_v of the received polynomial. Then:

Define the error values to be Y_l=e_j1, where l = 1, 2, …, v and the error locators to be X_l =β^jt, where l = 1, 2, …, v. Utilize Forney’s algorithm ( Lin and Costello, 2004) to derive the error values Y_l. Thus, the error correcting polynomial:

To recover the original data c (x), using

THE PROPOSED SCHEME

Description of the Proposed scheme: This study uses symbols or shares interchange and the concept of node or path compromising characteristics gives as follows:

According to Definition 1, the cost of sending a packet through one path is proportional to its hop count, more importantly, as the length of a multi-hop path increases, the possibility of path compromise is higher. Definition 2 shows the benefit of using node-disjoint path. Note that a compromised source makes the data delivery scheme meaningless, thus it is reasonable to assume that the source are trustworthy.

Let c= (c₀ , c₁,…, c_n-1) be a codeword of an (n, k) RS code over GF(2^a), where c_i ∈ GF (2^a) (1≤i≤n) is a symbol. Here, c₀, c₁, …, c_n-1 are the information that the sensor node needs to send to the destination node or sink. Since an (n, k) RS code can recover up to t=(n-k)/2 errors, n should satisfy n=k+2t.

In order to minimize transmission overhead and simultaneously maximize the security of the scheme, the sender should choose an appropriate value of (n, k) and send different numbers of symbols through difference paths according to their hop counts and path quality. The select of (n, k) reflect the security requirement of the user and the symbol allocation on path reflects the current condition of the network. Assume that basic security mechanisms such as pairwise key establishment between two neighbouring nodes (Ren et al., 2011) are already in place to provide basic communication security.

Suppose a sensor node U has data D to be sent to destination M. Without loss of generality, to secure D, basic encryption and integrity operation are performed before applying RS coding scheme.

The operational procedures of the proposed scheme given as follows:

Note that the proposed scheme does not need know the identification of the compromised paths to decode the data successfully. The RS decoder at the destination node will automatically correct any modification by the compromised nodes in these paths.

Non-uniform allocation: Assume that the sender transmits f_j fraction of the total n symbols through path j, where 1≤j≤m and

Due to the lack of the knowledge of which paths may be compromised, the sensor node has the best option of making sure that the expected number of symbols compromised on each path is more or less the same.

Let h_j be the hop count of path j, 1≤j≤m and x the probability of nodes being compromised, given that the source and destination are not compromised, the probability that path is compromised:

where 1≤j≤m. The expected number of symbols being compromised for path j is f_j p_j and the source node needs to make sure that f_j p_j=C, for all j. That is,

As mentioned earlier, the probability of path compromise is in proportion to the length of multi-hop path. It only need to derive the relation between f_j and h. when x is small, then

Therefore, C becomes

According to Eq. 8 and 9, then

Thus, a closed form for f_j, 1≤j≤m, which is related to h, is derived.

ANALYSIS AND SIMULATION

Analysis: Under the supposed adversary model, the data compromise probability p_x, which is define as the probability of compromising enough symbols to the adversary so that it can obtain the data with relative ease when the node compromised probability is x (0≤x≤1).

Let m = s₂+s₃+...+s_L, where s₂, s₃ , …, s_L, represented the source node find s₂ paths of length (hops count) 2, s₃ paths of length 3, … and s_L paths of the maximum length L (note that all these paths are node-disjoint paths). Let m_x = n₂+n₃+...+n_L, where m_x is the number of paths among m available paths that are compromised by the adversary, which contains n_2, n₃, ... n_L number of paths among s₂, s_3,... s_L that are compromised, respectively. More specifically, assume that n_j1, n_j2,..., n_jg, 0≤g≤L-1, are the nonzero term of n_2, n₃, ... n_L. Therefore, they are n_j1 paths of length j₁ compromised; n_j2 paths of length j₂ compromised…, n_jgpaths of length j_g compromised.

When the multiple node-disjoint paths are used, the source node transmits n symbols through the m paths with f_j fraction for path j, 1≤j≤m, where f_j is given by Eq. 10. Define the data compromise probability of the proposed scheme as the probability of at least k symbols being compromised to the adversary. For comparison between the proposed scheme and single path scheme, this study uses to distinguish from single path scheme, which uses . Therefore, the data compromise probability can be calculated as:

Since all found paths are node-disjoint, the total number of nodes between source node and storage node is:

Based on the independent compromised probability x, the probability that r out of r_T nodes are compromised is

Hence, the overall probability of compromising r nodes is

Now, the overall probability of compromising n_i paths (p₂) can be calculated as follows: there are n_i paths among s_i of length i are compromised, according to definition 2, each path is independent of another, with total of m_x compromised paths, p₂ can directly derive as:

where 0≤n_i≤s_i for 2≤i≤L.

According to definition 1, a path is compromised due to one or more than one node on the path is compromised, that is, r = m_x. Considering all possibilities to select r compromised nodes from nodes on the m_x compromised paths. Hence, the probability of at least one node on each compromised path must be compromised is:

where 1≤y_i,l≤j_i-1 for 1≤i≤g.

Therefore, the data compromised probability p_x^our can be calculated by Eq. 12-15.

For fair comparison, the data compromise probability in single path (SP) scheme also calculated. In the SP scheme, the data are transmitted through one randomly chosen path among the m available paths. If it selects a compromised path to transmit, then the whole data is revealed. Hence, when there are m_x compromised paths, the data compromised probability is m_x / m. Then:

where, r_T is given by Eq. 11 and p₃ is given by Eq. 15.

Simulation results: Simulations have been performed in NS-2 to evaluate the efficiency of the proposed scheme under the threat model. Unless specified otherwise, simulations were set up with the following parameters: N = 800 nodes are randomly placed on a square area of 500 m by 500 m. The area is divided into a gird of 25 = 5x5, with each grid cell of size 100mx100m. The radio transceiver range of each sensor node is 40m. The RS code is assumed to be (n, k) = (17, 9).

In order to understand the benefit of using node-disjoint paths serving in defending against of node capture, Fig. 1 investigated the probability of data compromised p_x as a function of node compromised probability x. It artificially decreased N, with half the nodes (N = 400) and allow the source node to randomly select all available paths during the path selection process for comparison purposes. Assume each sensor node has equally likely to be compromised with probability x, x = 0.01, …, 0.09. Based on Fig. 1, it can be concluded that under the same node density N (N = 400 or N = 800), the probability of data compromised increases with node compromised probability and given the same node compromised probability x, the proposed scheme using enhanced node-disjoint paths outperform randomly selected paths scheme with lower data compromised probability.

An example of these results is that when N = 800 and x = 0.07, the corresponding p_x is 0.39 and 0.1, respectively. It can further conclude that with a larger N, there have a relatively more neighbours, increasing potential more node-disjoint paths. Note that the proposed scheme uses shortest and trust-aware multi-hop paths, when the number of such paths is larger; the proposed scheme can tolerate higher node compromised probability. Due to the selection process of random path, the selected paths may intersect, that is, some nodes appear in more than one path from a source node towards to storage node and thus, the security performance worsens. This result verifies the effectiveness of the proposed idea.

Figure 2 presents the data compromise probability from another angle, where p_x is a function of node compromise probability x for different data share distribution scheme.

The uniform allocation can be regarded as f_j = 1/m for all paths and single path (SP) scheme is to send all shares through one path. Based on Fig. 2, it can be concluded that the non-uniform allocation applied in the proposed scheme outperform uniform scheme and SP scheme in terms of lower probability of data compromised. Such as if x is 0.06, then p_x for the proposed scheme, uniform scheme and SP scheme is 0.05, 0.25 and 0.6, respectively. The proposed scheme improves 5 times and 12 times over uniform scheme and SP scheme, respectively. It can further conclude that the selection of f_j has major effects on security performance. In the uniform scheme, long paths may be assigned with equally size of shares and lead to higher probability of data compromised. Moreover, the results proved again that multipath transmission is preferred over SP scheme when security is a major concern.

Figure 3 presents the probability of data compromised by varying the value of (n, k) and show data compromise probability p_x for different node compromised probability x. Based on this figure, it can be conclude that p_x is decreased by increasing both n and k, the network can tolerant faulty paths from t = 1 to 4 given m node-disjoint paths. More importantly, it provides a nice property of flexibility that a predefined threshold of p_x can be guaranteed by choosing an appropriate (n, k). For example, given a system threshold p_x = 0.4, with node compromised probability from 0.01 to 0.09, only (17, 9), (13, 7) satisfied the requirement, given p_x = 0.1, only (17, 9) satisfied the conditions when the node compromised probability lower than 0.05.

A comparison is made between the proposed scheme and H-SPREAD (Lou and Kwon, 2006); First, consider the circumstance that there is no data modification happen in the network. Define the robustness as the probability of data not compromised due to r compromised nodes, denoted as R₁, obviously, R₁ = 1-p_x. Fig. 4a shows R as a function of r for the proposed scheme and H-SPREAD. Based on this figure, it can be conclude that the proposed scheme outperforms H-SPREAD with better robustness as r increases. In H-SPREAD, the author attempts to find multiple node-disjoint paths for both security and reliability. As a result, the number of node-disjoint paths is small. Besides, each path is sent to equivalent number of symbols leading to the poor performance. An example of these results is that when r is 100, 200, 300, the robustness of H-SPREAD is 0.575, 0.175 and 0.022, respectively. When r up to 350, the robustness of the proposed scheme and H-SPREAD is 055 and 0, respectively, obviously, the proposed scheme significant improves the robustness of the network.

Further conclusion can be made that the selection of node-disjoint paths and non-uniform data allocation as well as redundancy has major effects on robustness in the proposed scheme.

Consider another circumstance that the adversary compromises r sensor nodes and they can further modify existing data and/or inject fake data into compromised sensors. Define reliability as the ratio of filtering bogus message, denoted as R₂. Figure 4b plots R₂ as a function of r for the proposed scheme and H-SPREAD. Based on this figure, it is observed that the reliability of the proposed scheme significantly improved over H-SPREAD. Actually, in H-SPREAD, it cannot address a number of important problems, such as, the authenticity of sensed data, the possibility that adversary modifies in any data found in sensor nodes. Once the sensor node is captured, the cryptographic keys as well as the data were exposed. They can easily insert bogus sensor readings or change the processing results and then use these keys to authenticate forged information. Thus, H-SPREAD fails to filter faked messages. In the proposed scheme, RS coding scheme which can tolerant at most terrors, where t = (n-k)/2. Therefore, it can achieve higher reliability. However, it has to point out that when r exceeded in 250, the reliability of the proposed scheme drops dramatically, after r up to 400, the reliability of the proposed scheme has no benefits over existing schemes. In this case, it can be explained that with the more compromised nodes in the networks, the more faulty paths exists, if the number of faulty path more than t, it cannot use the majority rule to filter out bad parity codes. However, when that happens, they are telltale signs indicate massive nodes invalid and should exclude out of the network.

DISCUSSION

The concept of multi-path routing dates back to 1970s, when it was initially proposed to spread the traffic for the purpose of load balancing and throughput enhancement (Maxemchuk, 1975). Later on, one of its sub-classes, path-disjoint multi-path routing, has attracted a lot of attention in wireless sensor networks due to its robustness in combating security issues. Some examples include the SMR (Lee and Gerla, 2007), DSR (Johnson et al., 1999), and AOMDV (Marina and Das, 2001) and AODMV (Ye et al., 2003).

The second category includes recent work that explicitly considers security metrics in constructing routes. Specifically, the SPREAD algorithm by Lou et al. (2004) attempts to find multiple most secure and node disjoint paths. The security of a path is defined as the likelihood of node compromise along that path and is labelled as the weight in path selection. A modified Dijkstra algorithm is used to iteratively find the top-k most secure node-disjoint paths. The H-SPREAD algorithm (Lou and Kwon, 2006) improves upon SPREAD by simultaneously accounting for both security and reliability requirements.

The work by Yang et al. (2005) considers the report fabrication attacks launched by compromised nodes. The work by Ren et al. (2006) further considers selective forwarding attacks, whereby a compromised node selectively drops packets to jeopardize data availability. Both works are based on a similar cryptographic method: the secret keys used by sensor nodes are specific to their geographic locations, which limits the impact of a compromised node.

Most of above mentioned works relying on a cryptographic method for resolving the node capture attacks. As a result, these approaches are no longer valid if the adversary randomly compromise or jam nodes. This is because once the adversary captures a sensor node, the credential and the encryption algorithm will be disclosed, even they can limit the impact of a compromised node within a local area. Instead of relying on a cryptographic method for resolving the issue, this work mainly exploits the routing functionality of the network to reduce the chance that the adversary can acquire a packet in the first place. Besides, by taking the advantage of the fact that different paths have different probabilities of being compromised or becoming faulty. Therefore, different amounts of symbols are sent through paths of different lengths. By doing so, the adversary has to compromise a k out of n sensors to recover the original data. Besides, by properly choosing the n and k parameters, it can give any sufficiently large majority the authority to take some action while giving any sufficiently large minority the power to block it. The experiment results are well support with the analysis and verify the effectiveness of the proposed scheme.

CONCLUSIONS

This study has presented an efficient in-network sensor data-delivering scheme in distributed wireless sensor networks. As is shown above, the presence of a powerful mobile adversary raises many challenges. The conventional view of security based on cryptography and authentication alone is not sufficient to provide a complete solution for developing secure and dependable sensor data delivery due to the unique characteristics and novel misbehaviours encountered in distributed sensor networks. This study investigates the first attempt to introduce RS code scheme and multipath routing protocol to add an additional support for an enhanced security solution. Analysis and simulation results show that proposed techniques significant improvement the data survival over existing scheme.

ACKNOWLEDGMENTS

This study is partially supported by National Basic Research Program of China (973 Program) under Grant No. 2009CB326202 (2009.4-2011.8, Hunan University) and 2010CB334706 (2010.4-2013.3, Hunan University). Key Program of National Natural Science Foundation of China under Grant No. 60736016 (2008.1-2011.12, Hunan University). National Natural Science Foundation of China under Grant No.60873198 (2009.1-2011.12, Hunan University), 60973128 (2010.1-2012.12, Hunan University), 60973113 (2010.1-2012.12, Hunan University), 61073191 (2011.01-2013.12, Hunan University) and 61070196 (2011.01-2013.12, Hunan University).

REFERENCES