本論文假設無線感測環境內佈置的感測點具有相同的感測、通訊、移動、電力功能及能力。在指定的目標區域內，以自然界物質結晶的觀念，由初始種子感測點開始尋找適合的鄰居點，並指定鄰居感測點移動到恰當的位置。當鄰居感測點開始移動後，再由這些鄰居感測點當作下一輪的種子感測點，重復進行上述的動作，直到種子感測點接觸到邊界，或是沒有鄰居感測點為止。我們命名此方法為擴散結晶排列佈點演算法(Crystal-Lattice Permutation)。

　　相較於類似的演算法(VF演算法)，VF演算法需要全部感測點的位置資訊，才能計算出感測點的目的位置。並且，在VF演算法中，每回合的計算都會使感測點移動，因此感測點會走曲線的路徑，而耗費多餘的電力。而本論文提出的擴散結晶排列佈點演算法(Crystal-Lattice Permutation)不需知道所有感測點座標，並以分散計算方式達到自行協調責任區域、移動路徑為直線的功能，並具有最大覆蓋、感測點平均移動路徑最短的特性。另外，本論文除了提出佈點演算法，也提出CLP演算法的容錯處理方式，並進行模擬測試，並展示有錯誤感測點發生時，對於覆蓋率及移動路徑的影響。

　　In this thesis, we consider the coverage problem in wireless sensor networks. Each node is assumed to have the same mobility, sensing ability, communication ability, and battery. We use a greedy method to select proper mobile nodes as seeds, which trigger neighboring mobile nodes to exact positions. These nodes then become new seeds to trigger other nodes. The progressive process is named the Crystal-Lattice Permutation (CLP) algorithm.

　　The Crystal-Lattice Permutation (CLP) algorithm is distributed, which means it doesn’t need to have all nodes’ positions. It obtains maximal coverage with minimal average moving distance. The process of handling faulty nodes during CLP algorithm’s operating is also discussed.

[1] Edgar H. Callaway, Jr., Wireless Sensor Networks Architectures and Protocols, AUERBACH publications, 2003
[2] Nojeong Heo and Pramod K. Varshney, “A Distributed Self Spreading Algorithm for Mobile Wireless Sensor Networks”, Proc. 2003 IEEE Wireless Communications and Networking Conference, New Orleans, Louisians, UAS, pp.1597-1602, Mar, 2003.
[3] Chih-fan Hsin, and Mingyan Liu, “Network Coverage Using Low Duty-Cycled Sensors: Random & Coordinated Sleep Algorithms”, Proc. 3rd ACM International Symposium on Information Processing in Sensor Networks, Berkeley, CA, USA, pp. 433–442, April, 2004.
[4] Dragos Niculescu, “Positioning in Ad Hoc Sensor Networks”, IEEE Network, Vol. 18, Issue 4, pp24-29, July-Aug., 2004.
[5] Guiling Wang, Guohong Cao, and Tom La Porta, “A Bidding Protocol for Deploying Mobile Sensors”, Prof. of 11th IEEE International Conference on Network Protocols, Atlanta, Georgia, pp315-324, November,2003.
[6]. Guiling Wang, Guohong Cao, and Tom La Porta, “Proxy-Based Sensor Deployment for Mobile Sensor Networks”, Proc. 2004 IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Fort Lauderdale, FL pp493-502,Oct, 2004.
[7] TheinLai Wong, Tatsuhiro Tsuchiya, and Tohru Kikuno, “A Self-organizing Technique for Sensor Placement in Wireless Micro-Sensor Networks”, Proc. IEEE AINA04, Fukuoka, Japan,pp78-83, Mar, 2004.
[8] Jie Wu and Shuhui Yang, “Coverage Issue in Sensor Networks with Adjustable Ranges”, Proc. 23th ICPP Workshop, Montreal, Quebec, CANADA, pp61-68, Aug, 2004.
[9] Y. Xu, J. Heidermann, and D.Estrin, “Geography-informed energy conservation for ad hoc routing”, Proc. ,of ACM MOBICOM’01, Rome, Italy, Vol. 1, pp70-84, July 2001.
[10] Honghai Zhang and Jennifer C. Hou, “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks”, Technical Report, Computer Science Department, UIUC, UIUCDCS-R-2003-2351, 2003
[11] Yi Zou and Krishnendu Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks”, ACM Transactions on Embedded Computing Systems (TECS), vol. 3, Issue 1, pp 61 - 91,Feb, 2004.