由於無線感測節點先天上的資源限制和處在數量大的通訊環境，想要在無線感測網路(Wireless Sensor Networks )產生通訊所需的密鑰並不是那麼容易達成。而傳統用於一般網路的許多密鑰產生的機制，例如對稱與非對稱演算法以及一些以公開密鑰基礎的機制(Public Key)，由於感測節點的計算能力有限，此類方法並不適用於無線感測網路上。針對此問題密鑰預先配置法(Key Pre-distribution)是較可行之方法，但是大網路規模擴大後，如何分佈配置是一個值得探討之問題。

本論文提出了一個在多組密鑰空間池(Multiple keyspace pools)以網格為基礎(Grid-based)的密鑰預先配置法，此方法將密鑰池(key pool)分成多組式的密鑰空間池(keyspace pool)，讓每個感測節點根據自己網格的座標，從所對應行和列的密鑰空間池取得所需之密鑰空間，再結合對稱密鑰產生機制(symmetric key generation)，使持有相同的密鑰空間即可計算出感測節點間通訊所需的密鑰。

此一利用多組式的密鑰空間池來預先配置感測節點密鑰之機制，可以發現其感測節點的恢復力(Resilience)比傳統的隨機配置機制及對稱密鑰產生機制效率高，而在網格的架構上，在路徑密鑰之建立也能有很高的機率，因此建立密鑰時的計算可以大幅度的縮減。

Because of resource constraints and large scale environment, it is not easy to achieve that establishing the communicating key in wireless sensor network. And traditional key exchange and key Distribution protocols are not practical. There are many key agreement schemes used in general network, such as RSA and other public-key based schemes, but they are not suitable for WSNs due to the limited computational abilities of the sensor nodes. We presents an Grid-based scheme for key pre-distribution, and the key pool is divided into multigroups as multiple keyspace pools. Each sensor nodes acquire keyspace form the corresponding row and column keyspace pool according to their location. And it will calculate a key from their same keyspace by combining the symmetric key generation scheme. The concept and analysis of this scheme compare with existing scheme in resilience to node capture. There can be very high probability and efficiency to establish the communicating key between sensor nodes. We also present an in depth analysis of our scheme in terms of network resilience and associated overhead.

[1] A. Perrig, J. Stanlovic, and D. Wagner, “Security in wireless sensor networks,” Communications of the ACM, Vol. 47, pp. 6, June 2004.

[2] C. Blundo, A. Santis, A. Herzberg, S. Kutten, U. Vaccaro, and M. Yung, “Perfectly-secure key distribution for dynamic conferences,” Lecture Notes in Computer Science, pp. 1-23,1993.

[3] C. Intanagonwiwat, R Govindan, D Estrin, J.S. Heidemann, and F. Silva, “Directed diffusion for wireless sensor networking,” IEEE/ACM Transactions on Networking, vol. 11, pp. 2-16, 2003.

[4] D. Liu, P. Ning, and R. LI, “Establishing pairwise keys in distributed sensor networks,” Trans. Information and System Security, Vol. 8, pp. 41-77, 2005.

[5] F. Zhao, J. Shin, and J. Reich, “Information-driven dynamic sensor collaboration for tracking applications,” IEEE Signal Processing Magazine, pp. 61-72, 2002.

[6] H. Chan, A. Perrig, and D. Song, “Random key predistribution schemes for sensor networks,” Proc. IEEE Security and Privacy Symposim, pp.197-213 ,2003.

[7] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, pp. 102-114, 2002.

[8] K. Chakrabarty, S. Sitharama Iyengar, H. Qi, and E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Transaction On Computers, vol. 51, pp. 12, December 2002.

[9] L. Eschenauer, and V.D. Gligor, “A key-management scheme for distributed sensor networks,” Proc. 9th ACM conference on Computer and Communications Security, pp. 41-47, 2002.

[10] M. Cardei, and J. Wu, “Coverage in Wireless Sensor Networks,” Handbook of Sensor Networks. CRC Press, 2004.

[11] M. Hall, Combinatorial Theory,Wiley-Interscience in Discrete Mathematics,1986.

[12] M.J.B. Robshaw, “Security Estimates for 51 2-bit RSA,” WESCON/'95. Conference record. 'Microelectronics Communications Technology Producing Quality Products Mobile and Portable Power Emerging Technologies', pp. 409, Nov. 1995.

[13] P. Erdös, and A. Rényi, “On random graphs,” Publicationes Mathematicae, vol. 6, pp. 290-297, 1959.

[14] Q. Jiang, and D. Manivannan, “Routing Protocols for Sensor Networks,” Proc. IEEE CCNC, pp. 93-98, 2004.

[15] R. Blom, “An optimal class of symmetric key generation systems,” Proc. Eurocrypt, pp. 335-338 1984.44

[16] S. Camtepe, and B. Yener, “Combinatorial design of key distribution mechanisms for wireless sensor networks,”Proc. 9th European Symposium On Research in Computer Security, pp. 293-308, 2004.

[17] S. Tilak, N.B. Abu-ghazaleh, and W. Heinzelman, “A Taxonomy of Wireless Micro-Sensor Network Models,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 6, pp. 28-36, Apr. 2002.

[18] S. Zhu, S. Setia and S. Jajodia, “LEAP: Efficient Security Mechanisms for Large-Scale Distributed Sensor Networks,” Proc. 10th ACM Conference on Computer and Communications Security, pp. 62-72, Oct. 2003.

[19] Sadi, M.G.; Dong Seong Kim; Jong Sou Park,“GBR: grid based random key predistribution for wireless sensor network,” Parallel and Distributed Systems, Proceedings. 11th International Conference, vol. 2, pp. 310-314, July 2005.

[20] V. Hingne, A. Joshi, E. Houstis, and J. Michopoulos, “On the Grid and Sensor Networks,” Proceedings of the Fourth International Workshop on Grid Computing, pp. 166-173, Nov. 2003.

[21] W. Diffie, and M. E. Hellman, “New directions in cryptography,” Trans. Information Theory, vol. 22, pp.644-654, Nov. 1976.

[22] W. Du, J. Deng, Y. Han, P. Varshney, J. Katz, and A. Khalili “A Pairwise Key Pre-distribution Scheme for Wireless Sensor Networks,” Trans. Information and System Security, vol. 8, pp. 228-258, 2005.

[23] Z. WU, H. Song, S. Jiang, and X. Xu, “A Grid-based Stable Routing Algorithm in Mobile Ad Hoc Networks,” Proceedings of the First Asia international Conference on Modelling & Simulation, pp. 181-186, March 2007.