## 5 SCODE_plus_: Enhanced Secure Routing and Key Management Scheme
### Key Management  
Our key management scheme is an improvement of [PERSON]'s scheme [29]. [PERSON]'s scheme is not able to apply directly to sensor networks due to its memory overhead for storing keys. It uses \(n\) symmetric variables polynomials with _t-degree_ to establish key distribution for _t-secure_\(n\)-_conference_. In this scheme, each node must store \(t+l\) coefficients. Each coefficient costs _log:q_ bits. So the memory storage requirement for each node in this model is (\(t+1\))_log_q_ bits. The analysis in [29] shows that, this scheme is unconditionally secure and _t-collusion_ resistant. It means that as long as no more than \(t\) nodes are compromised, the attacker knows nothing about the pair-wise key between any two non-compromised nodes. However, the size of memory depends exponentially on the size of the network, so it is not useful for such resource-constraint devices like sensor nodes using only this model. We have tackled this problem by using pre-deployment knowledge and showed that it will take more advantages than other polynomial-based schemes applied location knowledge. The previous work [26] has demonstrated our success in solving the problem using the square-grid network topology. In this study, a new effort is made to enhance the scheme with a hexagonal topology.  
We define a key-space as derived from a bivariate polynomial in [PERSON]'s scheme. A node \(N_{A}\) picks a key-space \(f_{u,}\)(\(x\), \(y\)) if it carries the coefficients of \(f_{u,}\)(\(N_{A}\oplus\)\(nonce_{A}\), \(y\)), where \(nonce_{A}\) is a random value of node \(A\) and will be described in the _key predistribution_ phase. When two nodes are in the same key-space, they could calculate a pair-wise shared key to setup a secure channel.  
Our scheme allows sensor nodes to find a common key space with each of their neighbors after deployment. It consists of three phases: _key predistribution_, _direct key establishment_, and _indirect key establishment_. The key predistribution phase is carried out to preload the credential information to  
Figure 4: Hexagonal group-based deployment model.  
each sensor node before deployment. After setting up, two sensor nodes can establish a direct key between them if they share at least a common key-space, otherwise, they could agree on an indirect key according to the indirect key establishment phase.  
The purpose of this phase is to assign key materials to each node. Based on these key materials, neighboring nodes could setup pair-wise keys after deployment.  
This task is done by an offline server. At first, the server will generate a polynomial pool \(\mathcal{F}\) containing enough _t-degree_ symmetric bivariate polynomials for every cluster. Then it distributes each polynomial to all sensor nodes in each cluster. Since each cell belongs to three clusters, therefore every node has to store knowledge of three _t-degree_ bivariate polynomials. In other words, each node needs to pick three key-spaces. The detail algorithm for polynomials predistribution is shown in Figure 5.  
At the end of this phase, every sensor node stores node IDs, three space IDs, random values, and three vectors of coefficients equivalent to three key-spaces. These key materials will be used to setup pair-wise keys in the next phase.  
Figure 5: Polynomials predistribution.