Key Predistribution Scheme And Orthogonal Arrays

Recently, Distributed Sensor Networks were used widely in various situations. It has many properties as follows: the number of sensor nodes is huge in the network,and the sensors are dropped in a random way to the vast area, so the network topology is unknown before the deployment. In many applications, it is important for sensor nodes to communicate securely with each other. A better method is to use the key predistribution schemes, where a set of secret keys is installed in each sensor node before they are deployed. In this dissertation, we mainly consider the construction of key predistribution schemes in wireless distributedsensor networks and some other relevant questions. There are two type of key predistribution schemes: one is probabilistic and the other is deterministic. Among the properties of key predistribution schemes, the connective probability p and probability fail(1) are of most important. The connective probability p is defined by the probability that any pair of sensor nodes shares a link, i.e., the nodes of a pair have at least one common key, hence it measures the effectiveness of the sensor network. If a sensor node is detected as being compromised, then all the keys it possesses should no longer be used by any node in the sensor network. Then fail(1) is defined as the probability of lost links, so that it describes the resilience of the sensor network.We extend the deterministic construction of key predistribution schemes, and provide a easy computation of connective probability p and fail(1) for some special strong partially balanced design whereλ_t=1. Then, we provide three classes of key predistribution schemes based on rational normal curves over finite field, Mobius plane over finite field and orthogonal arrays separately. The resulting schemes have some better properties than the previous ones, for example, our schemes may have higher connective probability p, or lower fail(1), or can support large scale network and so on.The key predistributed schemes constructed from orthogonal arrays have some universal properties: if we select some special values of t, then the result schemes have almost the same behaviors as to the previous deterministic ones. Hence, orthogonal array is one of our research objects.The t linearly independent arrays in the vector space V_r(F_q) can be used to construct orthogonal arrays. Therefore, we study the following problem: Given the dimension r of the vector space V_r(F₂), and an integer t (2≤t≤r), find the largest integer n, such that there exists a subset of n nonzero elements∑in V_r(F₂), every t vectors of which are linearly independent. The maximal value is denoted by M(r,t). If we consider the above∑as the parity matrix of some certain linear codeφ, then the minimal distance ofφis d(φ) = t +1 (Note, when we consider∑as a t linearly independent array, we always mean that∑is not at+1 linearly independent array.) Hence, any results on such question may be useful for constructing better linear codes.We study the construction of maximal t linearly independent arrays and the value M(r,t). We get the following results: (1) we completely solve the case of t=3, i.e., M(r, 3) = 2^r-1 for every r≥3. Our method can easily find out all the maximal 3 linearly independent arrays. Furthermore, we show that all the maximal 3 linearly independent arrays are just the support of all the linear functions in r indeterminates. (2) we determine the values t such that M(r, t)= r + 1, which we call trivial case. (3) we partially determine the values t such that M(r, t)=r + 2, which we call sub-trivial case (The sufficient condition of the result is not proved now). By the above results, we construct several class of orthogonal arrays, which may reach some know bounds on orthogonal arrays. Furthermore, we construct some kind of strong partially balanced designs.If we know the parameters of a linear codeφ: length n, dimension k and the minimal distance d, then the parity check matrix H of the codeφis a t linearly independent array of length n in vector space V_r(F₂) where r = n - k and t = d+ 1. We study the construction of linear codes to get the information of maximal linearly independent arrays. The result shows that we know only a little about M(r, t).