## 3 Multipath Data Collection  
Multipath routing has been used for different purposes in WSNs, such as load balancing, energy efficiency [10, 11], _etc._ In this paper, we make use of multipath routing for secure data collection. We use a (\(t\), \(n\))-threshold secret sharing algorithm, e.g., [PERSON]'s algorithm [12], to encode a sensed data packet. When a sensor node wants to send a packet to a destination node (often the sink), it first breaks the packet into \(N\) shares according to the secret sharing algorithm. Each share is then transmitted to some randomly picked neighbor. The (\(t\), \(n\))-threshold secret sharing algorithm is illustrated as follows:  
1. Without loss of generality, we assume that the data is denoted by a number \(D\). We choose a number \(p\) larger than both \(D\) and \(n\). 2. We generate a collection of coefficients \(a_{1}\), \(a_{2}\),..., \(a_{t-1}\) from [0, \(p\)) and construct a \(t-1\) degree polynomial \(q(\mathrm{x})=a_{0}+a_{1}x+...+a_{t-1}x^{t-1}\), in which \(a_{0}=D\). 3. We evaluate \(D_{1}=q(1)\), \(D_{2}=q(2)\),..., \(D_{n}=q(\mathrm{n})\). Here \(D_{i}\) denotes \(i^{th}\) share of the data. 4. We deliver different shares to different objects. 5. Given any subset of \(t\) of these \(D_{i}\) values, we can calculate the coefficients of \(q(\mathrm{x})\) by interpolation, and then evaluate \(D=q(0)\). However, \(t-1\) (or less) of these values does not suffice in order to calculate \(D\). Therefore, we can break a data packet into a collection of shares by using the (\(t\), \(n\))-threshold secret sharing algorithm and deliver different shares via different routing path (see Figure 1). We can extend existing multipath routing algorithms like AOMDV [13], SMR [14] to achieve secure routing in WSNs. Moreover, we intend to find as many routing paths as possible for a source node rather than using a set of disjoint paths like in AOMDV and SMR. We extend the algorithm given in [3] to generate routing path randomly for data collection. A data packet is broken into shares according to the (\(t\), \(n\))-threshold secret sharing algorithm and shares are transmitted to the sink via different paths. The algorithm in [3] does not consider the density of the sensor nodes in a WSN. If the degree or the number of neighbors of a node is small, there may be not enough candidates for delivering shares. Moreover, different nodes in a WSN have different degree values, a fixed (\(t\), \(n\))-threshold cannot satisfy every node in the WSN. We extend the algorithm in [3] with an adaptive (\(t\), \(n\))-threshold that varies according to the degree of node. The adaptive data collection (ADC) algorithm is illustrated as follows:  
1. To a source node \(S\) that intends to send a data packet \(D\), if its degree is larger than a threshold value \(k\), we set \(n\) to the degree of the node, which is the number of the neighbors of the node. Moreover, we set \(t\) to a number that is less than \(n\). Otherwise, the node sends \(D\) by normal routing until \(D\) reaches a node with enough degree. 2. We break \(D\) into \(n\) shares according to the \((t,\,n)\)-threshold secret sharing algorithm. 3. For each share, we perform node selection using one of the four distributed random propagation mechanisms in [3]. 4. In this way, the shares of \(D\) are forwarded by a collection of relay nodes until they reach the sink. In the algorithm above, we consider the degree of sensor nodes. If the degree of a sensor node is small, it is not necessary to break a data packet into shares. We use an adaptive mechanism to control process of breaking data packet into shares. We will forward a data packet until it reaches a node that has a degree value large enough for \((t,\,n)\)-threshold algorithm. In order to distinguish data shares and the original data packet, we should add an additional flag in the beginning of the data packet (see Figure 2). The data packet also contains a routing sequence field \(L_{R}\) (used later). Figure 1: A WSN with secret sharing mechanism for data collection.