近年來，無線感測網路的快速成長以及其應用越來越廣泛，由於
感測網路大多是透過無線的方式來傳送資料，使得其安全議題倍受重
視；在感測網路上金鑰加解密的研究已有多年，因此有著許多有效的
金鑰管理的方式，但是因為感測節點本身有著便宜、硬體簡單且大部
分是佈置在開放領域的特性，使得攻擊者可以簡單的就抓到某一個節
點，對他加以分析然後複製他的資料，之後再暗中放回網路上。以這
種攻擊方式，攻擊只要有少數點就可以做各種不同的攻擊，比方說竊
聽或改變網路的資料，甚至可以中斷網路重要的部分。
之前對於節點複製攻擊的研究主要是用中央控管、區域偵測或是
向網路廣播的機制，但是中央控管的方式，一旦中央的節點被攻擊，
整個網路就變的不安全；而區域偵測的機制中，多半要利用鄰居發起
投票的機制，可惜這種機制只要複製節點的行為不超過偵測臨界值，
就無法抓到分散式的複製節點攻擊，且每個複製節點沒有共同的鄰居
時，此種方式將無法偵測。
在Parrig 和Parno 的論文中[18]提出了一個新的分散式偵測節
點複製攻擊的方式，其中的Line-Selected Multicast 機制，可以用
少量的損耗達到不錯的偵測機率，我們則根據這個機制進行研究再加
以改進，一方面加強其面對於複製節點數量少時的偵測機率，並且探
討在不同的網路拓樸中，如何仍可有效的偵測到被複製的節點。最
後，我們透過分析以及模擬的方式來驗證機制的效能，並討論未來的
工作。

Applications in wireless sensor network are widely used in daily life. Communication
among sensor nodes is based on wireless signal. Therefore, security issue in wireless
sensor network has attracted much attention recently. Study of key
encryption/decription schemes in wireless sensor network has been performed for
many years, and there are already many efficient and powerful key management
schemes. But the characteristics of sensor networks, such as low-cost, simple
hardware and often placed in unshielded places, allows attackers to compromise
nodes easily. With little effort, attackers can capture nodes and replicate them, and
surreptitiously insert these replicas at strategic locations within the network. With this
attack, attackers can corrupt network data or even disconnect significant part of the
network.
Previous node replication detection scheme depend primarily on centralized
mechanism, local detection, or broadcast. But in centralized mechanism, the whole
network will be unsafe if the central node suffers attacks. Local detection schemes
depend on neighborhood voting protocol that are not efficient when no common
neighbors are shared between the replicas. Broadcast protocols, on the other hand, is a
simple way for detection replicas, but they are costly in terms of communication
overhead.
In [18], a new distributed way for detecting replication attacks has been proposed,
and their Line-selected Multicast scheme can detect replicas with reasonable
probability at low cost. Our research is based on this scheme and improve upon it by
enhancing the detection probability when replicas are few. In addition, we study how
to achieve high detection probability in different network topology. Finally, we verify
the performance by analysis.

[1] 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
[2] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, “A survey on sensor
networks,” IEEE Communications Magazine, vol. 40, pp. 102-114, 2002.
[3] M. Cardei, and J. Wu, “Coverage in Wireless Sensor Networks,” Handbook of
Sensor Networks. CRC Press, 2004.
[4] Q. Jiang, and D. Manivannan, “Routing Protocols for Sensor Networks,” Proc.
IEEE CCNC, pp. 93-98, 2004.
[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] 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.
[7] M. Kochhal, L. Schwiebert, and S. Gupta, “Role-Based Hierarchical
Self-Organization for Wireless Ad hoc Sensor Networks,” Proc. Second ACM
International Workshop on Wireless Sensor Networks and Applications, pp.
98-107, 2003.
[8] W. Diffie, and M. E. Hellman, “New directions in cryptography,” Trans.
Information Theory, vol. 22, pp.644-654, Nov. 1976.
[9] J. R. Douceur. The Sybil attack. In Proceedings of Workshop on Peer-to-Peer
Systems (IPTPS), Mar. 2002.
[10] H Fu, S Kawamura, M Zhang, L Zhang - Systems,” Replication attack on
random key pre-distribution schemes for wireless sensor networks” Man and
Cybernetics (SMC) Information Assurance Workshop, Proceedings from the Sixth
Annual IEEE,pp. 134- 141, June .2005
[11] J. Dyer, M. Lindemann, R. Perez, R. Sailer, L. van Doorn, S.W. Smith, and S.
Weingart. Building the IBM 4758 Secure Coprocessor. IEEE Computer, 2001.
[12] S. W. Smith and S. Weingart. Building a highperformance,programmable secure
coprocessor. Computer Networks, Apr. 1999. Special Issue on Computer
Network Security.
[13] S.Weingart. Physical security devices for computer subsystems:A survey of
attacks and defenses. In CryptographicHardware and Embedded Systems(CHES),Aug. 2000
[14] H. Chan, A. Perrig, and D. Song. Random key predistribution schemes for sensor
networks. In Proceedings of IEEE Symposium on Security and Privacy, May
2003.
[15] D. Malan, M.Welsh, and M. Smith. A public-key infrastructure for key
distribution in TinyOS based on elliptic curve cryptography. In Proceedings of
IEEE Conference on Sensor and Ad hoc Communications and Networks
[16] L. Eschenauer and V. Gligor. A key-management scheme for distributed sensor
networks. In Proceedings of the ACM Conference on Computer and
Communication Security (CCS), Nov. 2002.
[17] J. Newsome, E. Shi, D. Song, and A. Perrig. The Sybil attack in sensor networks:
Analysis and defenses. In Proceedings of IEEE Conference on Information
Processing in Sensor Networks (IPSN), Apr. 2004.
[18] B. Parno, A. Perrig, V. Gligor, “ Distributed detection of node replication attacks
in sensor networks” In IEEE Security and Privacy Symposium, May 2005
[19] J. Newsome and D. Song. GEM: Graph embedding for routing and data-centric
storage in sensor networks without geographic information. In ACM Conference
on Embedded Networked Sensor Systems (SenSys), Nov. 2003.
[20] L. Doherty, K. S. J. Pister, and L. E. Ghaoui. Convex position estimation in
wireless sensor networks. In Proceedings of IEEE Infocom, 2001.
[21] N. Bulusu, J. Heidemann, and D. Estrin. GPS-less lowcost outdoor localization
for very small devices. IEEE Personal Communications Magazine, October
2000.
[22] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms.
MIT Press, 2001.
[23] B. Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless
networks. In Proceedings of Conference on Mobile Computing and Networking
(MobiCom), Aug. 2000.
[24] S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker.
GHT: A geographic hash table for data-centric storage. In Proceedings of
ACMInternational Workshop on Wireless Sensor Networks and Applications
(WSNA), Sept. 2002.
[25] J. Tchakarov and N. Vaidya, “Efficient Content Location in Wireless Ad Hoc
Networks”, IEEE International Conference on Mobile Data Management (MDM), January 2004.