無線感測網路(Wireless Sensor Networks, WSNs)其技術可廣泛應用在許多領域中，尤其是環境監測。然而，由於部署無線感測節點時的不平均，或有障礙物例如湖和山丘的存在，或感測節點的電量耗盡與被外力破壞等因素，進而造成無線感測網路中存在著空洞(Hole)，而這些空洞會使無線感測網路的效能降低。因此，如何找出這些空洞的位置，並利用這些空洞位置所獲得的資訊，提升無線感測網路之效能，是一個相當重要的研究議題。為了解決這樣的問題，所以我們提出一個基於網格化之無線感測器網路空洞偵測機制。藉由網格式架構的方式，利用網格首節點廣播及代傳空洞偵測資訊，並由資料收集點加以計算空洞之位置等資訊，以提高網路整體效能。

Wireless Sensor Networks (WSNs) can be widely utilized in many applications especially in environmental surveillance. However, there exist some holes within the WSNs caused by some factors such as non-uniform deployment of sensor nodes, the existence of physical obstacle such as mountains and lakes, some sensor nodes deplete their energy, and being destroyed by outside forces. These holes will degrade the performance of wireless sensor networks (WSNs). Hence, how to discover the position of the holes and utilize the information to improve the performance of WSNs is a significant issue. In order to solve this problem, we proposed a grid-based hole detection scheme in WSNs. In grid architecture, we use the grid head to broadcast and forward the hole detection request and respond. And then, sink will calculate the position of the holes for improving the performance of the WSNs.

目錄	III
圖目錄	V
表目錄	VII
第一章 緒論	1
1-1 前言	1
1-2 研究背景	2
1-3 研究動機	5
1-4 研究目的	6
1-5 論文架構	7
第二章 相關背景與研究	8
2-1 無線感測網路介紹	8
2-2 無線感測網路架構與功能	9
2-3 資料傳送模式	13
2-4 網格(Grid)	15
2-5 空洞背景	17
2-6 覆蓋空洞偵測相關研究	18
第三章 以網格式架構為基礎之無線感測器網路通訊空洞偵測機制	20
3-1 網路環境設定	23
3-2 網格化階段(Griding Phase)	25
3-3 空洞偵測階段(Hole Detection Phase)	30
3-4 空洞資訊計算階段(Hole Information Computing Phase)	40
3-5 特性與優勢	43
第四章 模擬與分析	44
4-1 模擬環境	45
4-2 模擬結果的分析與比較	46
第五章 結論與未來研究方向	48
5-1 結論	48
5-2 未來研究方向	49
參考文獻	50
附錄–英文論文  54



  圖目錄
  圖 2.1 無線感測網路的功能架構圖	10
  圖 2.2 虛擬網格劃分示意圖	15
  圖 2.3 空洞示意圖	17
  圖 2.4 pu與pv中垂線交點O	19
  圖 2.5 由p點實行右手法則繞境示意圖	19
  圖 3.1 通訊空洞偵測機制流程圖	21
  圖 3.2 無線感測器網路佈建示意圖	23
  圖 3.3 d(網格邊長)與R(傳輸半徑)之間的關係	25
  圖 3.4 節點感測範圍示意圖	26
  圖 3.5 虛擬網格編號示意圖	27
  圖 3.6 網路網格化架構階段示意圖	28
  圖 3.7 網格化架構階段流程圖	29
  圖 3.8 資料匯集點發送Det_Hole_Message封包示意圖	30
  圖 3.9 Sink於空洞偵測階段之初始工作	31
  圖 3.10 感測首節點回送Det_Hole_ACK封包示意圖	32
  圖 3.11 首節點接收Det_Hole_Message封包與回傳Det_Hole_ACK封包示意圖	33
  圖 3.12 感測首節點代傳Det_Hole_ACK封包示意圖	34
  圖 3.13 首節點收到封包時之工作流程圖	35
  圖 3.14 空洞偵測階段後之網格標示圖	38
  圖 3.15 空洞偵測階段流程圖	39
  圖 3.16 網格G(x,y)之相鄰網格示意圖	40
  圖 3.17 覆蓋空洞示意圖	42
  圖 3.18 空洞資訊計算階段之工作流程圖	42
  圖 4.1 不同感測半徑下之空洞偵測時間圖	46


  表目錄 
  表 3.1、網格實際座標資訊表	27
  表 3.2、Det_Hole_Message 格式表	31
  表 3.3、Det_Hole_Ack 格式表	34
  表 3.4、網格資訊表	36
  表 3.5、經過空洞偵測階段後之網格資訊表	37

[1]   陳麗文，在無線感測網路上部分節點覆蓋率之研究，義守大學資訊工程所碩士論文，2008。

[2]   I. F. Akyildiz, W. Su, Y. Sankarasubramainiam, and E. Cayirci, Wireless sensor networks: a survey, Journal of Computer Networks, 2002, Vol. 38, pp. 393–422.

[3]	X. Liu, H. Hou, J. Yang, H. Yu, and H.Hu, Coverage and Energy Information Gathering Protocol in Wireless Sensor Networks, In Proceedings of IEEE Parallel and Distributed Computing, Applications and Technologies (PDCAT) 2005, pp. 649-654.

[4] 	A. Ghosh, and T. Givargis, LORD: A Localized, Reactive and Distributed Protocol for Node Scheduling in Wireless Sensor Networks, In Proceedings of IEEE Design, Automation and Test in Europe 2005, Vol.1, pp. 190-195.

[5] 	E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan, Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In Proceedings of ACM MobiCom, 2001, pp. 272–286.



[6] 	Y. Sankarasubramaniam, I. F. Akyiliz, Su Weilian and E. Cayirci, A survey on sensor networks. In Proceedings of IEEE Communications Magazine, 2002, Vol. 40, pages 102–114.

[7] 	S. Tilak, B. Abu-Ghazaleh, and W. Heinzelman, A taxonomy of wireless micro-sensor network models, In Mobile Computing and Communications Review, 2002, Vol. 1, pp. 28-36.

[8]	N. Ahmed, S. S. Kanhere, and S. Jha, The holes problem in wireless sensor networks: a survey, In Proceedings of ACM SIGMOBILE Mobile Computing and Communications Review, 2005, Vol. 9, pp.4-18.

[9]	Shakkottai S, Srikant R, Shroff N, Unreliable sensor grids: Coverage, connectivity and diameter, In Proceedings of IEEE Conference on Computer Communications, 2003, pp. 1073-1083.

[10]	Kumar S, Lai T H, Balogh J, On k-coverage in a mostly sleeping sensor network, In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. Philadelphia, 2004, pp. 144-158.

[11]	Meguerdichian S, Koushanfar F, Potkonjak M, Srivastava M B. Coverage problems in wireless Ad-hoc sensor networks, In Proceedings of the IEEE Conference on Computer Communications. Anchorage, Alaska, 2001, pp.1380-1387.
[12]	Qing Fang, Jie Gao, Leonidas, J. Guibas, Locating and Bypassing Holes in Sensor Networks, In Proceedings of IEEE INFOCOM’04, 2004, pp. 187-200.

[13]	Wang G, Cao G, La Porta T, Movement-assisted sensor deployment, In Proceedings of the IEEE Conference on Computer Communications, 2004, pp. 2469-2479.

[14]	So Man Cho A, Ye Y, On solving coverage problems in a wireless sensor network using voronoi diagrams, In Proceedings of the International Workshop on Internet and Network Economics(WINE), 2005, pp. 584-593.

[15]	Rao A, Ratnasamy S, Papadimitriou C, Shenker S, Stoica I, Geographic routing without location information, In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. SanDiego, 2003, pp.96-108.

[16]	Lederer S, Wang Y, Gao J, Connectivity-based localization of large scale sensor networks with complex shape, In Proceedings of the IEEE Conference on Computer Communications. Phoenix A Z, 2008, pp. 789-797.

[17]	Li X, Hunter DK, Yang K, Distributed coordinate-free hole detection & recovery, In Proceedings of the IEEE Globe Com, 2006, pp.1-5.
[18]	Bejerano Y, Simple and efficient k-coverage verification without location information, In Proceedings of the IEEE Conference on Computer Communications, 2008, pp. 291-295.

[19]	張庭瑋，應用於網格式無線感測器網路之有效的移動目標物追蹤機制，淡江大學資訊工程所碩士論文，2008。

[20] 	Y. Hu, J. Heidemann and D. Estrin, Geography-Informed Energy Conservation for Ad Hoc Routing, In Proceedings of the 7th ACM Annual International Conference on Mobile Computing and Networking,  Rome, 2001, pp. 70-84.

[21] 	Mohamed A. Sharaf, Jonathan Beaver, Alexandros Labrinidis and Panos K. Chrysanthis, Balancing Energy Efficiency and Quality of Aggregate Data in Sensor Networks, The Journal of Very Large Data Bases archive, 2004, Vol. 13, Issue 4, pp.384-403.

[22] Harshavardhan Sabbineni and Krishnendu Chakrabarty, Location-Aided Flooding: An Energy-Efficient Data Dissemination Protocol for Wireless Sensor Networks, In Proceedings of IEEE Transactions on Computers, 2005, Vol. 54, pp. 10-22.