臺灣博碩士論文加值系統

最近幾年來，由於科技的進步，無線感測器開始變成微小、可無線傳輸及自主運作，並且帶來了許多應用，例如戰地的偵查、醫院中病人的照護、或是探測危險區域的環境資訊。但是在這些感測網路的應用中，感測器佈署狀態的覆蓋率高低會影響後續應用的優劣，導致感測網路的覆蓋問題受到很多學者的注意並引起廣泛的討論。
在無線感測網路中覆蓋問題可以大致上分為兩類：分別為監測感興趣區域的區域覆蓋問題及監測特定目標物的目標物覆蓋問題。在此之前已經有許多的學者在研究此類型的問題，但是都感測器假設為具有全方向的感測能力，而現實生活中由於技術或是硬體的限制，大多數的感測器的感測區域是呈現一個有角度的扇形區域，稱為有向性感測器。一個有向性感測網路是由許多有向性感測器所組成，此類型感測器跟傳統的全向性 (Omni-directional) 感測器不同之處，在於有向性的感測器都有限制的感測角度跟固定的感測半徑，只具備感測一個近似於扇形的區域能力。
在本篇論文中，我們針對覆蓋問題為使用旋轉角度來達到最大的區域覆蓋率，並提出一個分散式貪婪演算法來解決此問題，希望以重疊最少的覆蓋方向優先考量之演算法，使得感測器在旋轉後可以減少與其他感測器的重疊。透過劃出Voronoi圖，藉由將感測器方向轉至最遠的頂點當作旋轉之方向，並透過與相鄰鄰居找出最少與鄰居重疊的部分，此方法是藉由Voronoi圖中找尋最少鄰居的方向來覆蓋。透過實驗模擬，利用我們提出的旋轉角度之技術，確實可以有效來提高區域覆蓋的覆蓋率。

In wireless sensor networks (WSNs), many applications in military and civilian operations, such as environmental monitoring, battlefield surveillance, health care and volcanoes monitoring become more popular in recent years, since more powerful sensors with high capabilities are being designed at rapidly decreasing costs. However, the coverage of sensor deployment which is good or bad must be affect these applications, so that the coverage problem in the sensor network has received a lot of attention of many researchers and widely discussed.
The coverage problem can be broadly divided into two categories: target coverage problem and area coverage problem. Most of the past work to solve the problem is always based on the assumption of omni-directional sensors that have an omni-angle of sensing range. In real-world, most sensors may have a limited angle of sensing range due to technical constraints or cost considerations.
In this thesis, we proposed a Maximum Coverage with Rotatable Sensors (MCRS) problem. We proposed a greed algorithm to use the Voronoi-based to decrease the overlapping area and maximize the area coverage of a randomly deployed directional sensor network. Finally, simulation results show that our proposed algorithms are more effective than the previous methods of the coverage rate.

摘要 iii
Abstract iv
致謝 v
Table of Contents vi
List of Figures viii
List of Tables xi
Chapter 1 Introduction 1
Chapter 2 Related Work 6
2.1 The Expectation Value of Coverage Rate 6
2.2 The Face Away Algorithm 7
2.3 The Distributed Minimum Overlapping-Angle First Algorithm 9
2.4 Voronoi Diagram 11
2.4.1 Formal definition 11
2.4.2 Properties 12
2.5 The Voronoi-Based Distributed Approximation (VDA) algorithm 13
2.6 The Intra-cell Working Direction Selection (IDS) Algorithm 17
Chapter 3 Directional Sensing Model and Preliminaries 21
3.1 Directional Sensing Model 21
3.2 Assumptions 23
Chapter 4 Our Proposed Scheme 24
4.1 The Definition of the Weight Function 24
4.2 The Selection Scheme 26
4.3 The Distributed Voronoi-based Minimal Side First Algorithm 29
4.4 An Example for Our Scheme 32
Chapter 5 Performance Evaluation and Simulation 39
5.1 Simulation Environment 39
5.2 Simulation results 39
5.2.1 Coverage rate vs. Number of Sensors 39
5.2.2 Coverage rate vs. Sensing Radius 43
5.2.3 Coverage rate vs. Sensing Angles 46
Chapter 6 Conclusions and Future Work 51
References 53

[1] Kuei-Ping Shih; Sheng-shih Wang; Pao-Hwa Yang; Chau-Chieh Chang, “CollECT: Collaborative Event detection and Tracking in Wireless Heterogeneous Sensor Networks,” to be appeared in IEEE Symposium on Computers and Communications, 2006. ISCC’06. Proceedings.
[2] Lindsey, S.; Raghavedra, C.S., “PEGASIS: Power-efficient gathering in sensor information systems,” to be appeared in IEEE on Aerospace Conference Proceedings, 2002. Vo1.3, no., pp. 3-1125-3-1130 vo1.3, 2002.
[3] Mo Li and Yunhao Liu, “Underground Structure Monitoring with Wireless Sensor Networks,” to be appeared in 6th International Symposium on Information Processing in Sensor Networks, 2007. IPSN 2007, pp. 69-78.
[4] R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler, “An analysis of a large scale habitat monitoring application,” to be appeared in ACM Conference on Embedded Networked Sensor Systems (SenSys), pp. 214-226, 2004.
[5] M. Rahimi, R. Baer, O. I. Iroezi, J. C. Garcia, J. Warrior, D. Estrin, and M. Srivastava, “Cyclops: In situ image sensing and interpretation in wireless sensor networks, to be appeared in ACM Conference on Embedded Networked Sensor Systems(SenSys), 2005.
[6] J. Djugash, S. Singh, G. Kantor, and W. Zhang, “Range-only slam for robots operating cooperatively with sensor networks,” to be appeared in IEEE International Conference on Robotics and Automation, 2006.
[7] M. Amac Guvensan, A. Gokhan Yavuz, “On coverage issues in directional sensor networks: A survey,” to be appeared in Ad Hoc Networks, 2011.
[8] Ren Yan, Zhang Hang Si-Dong, et al. “Theories and Algorithms of Coverage Control for WSNs,” to be appeared in Journal of Software, Vol.17, No3, pp.422-433, March, 2006
[9] S. Meguerdichian, F. Koushanfar, M. Potkonjak and M.B. Srivastava, “coverage problems in wireless ad-hoc sensor networks”, to be appeared in IEEE INFOCOM, Anchorage, AK, Apr. 2001.
[10] Weifang Cheng, Shanshan Li, Xiangke Liao, hen Changxiang and Haitao Chen , “Maximal Coverage Scheduling in Randomly Deployed Directional Sensor Networks”, to be appeared in International Conference on Parallel Processing Workshops, ICPPW 2007.
[11] Kandoth, C., Chellappan, S., “Angular Mobility Assisted Coverage in Directional Sensor Networks,” to be appeared in International Conference on Network-Based Information Systems, NBIS 2009.
[12] U. Chen, B.-S. Chiou, J.-M. Chen, W. Lin, “An Adjustable Target Coverage Method in Directional Sensor Networks”, IEEE Asia-Pacific Services Computing Conference (APSCC 2008), pp. 174–180, 2008.
[13] D. Tao, H.-D. Ma, and L. Liu, “Coverage-Enhancing Algorithm for Directional Sensor Networks”, Mobile Ad-hoc and Sensor Networks (MSN), LNCS 4325, pp. 256-267, 2006
[14] J. Ai and A. A. Abouzeid, “Coverage by directional sensors in randomly deployed wireless sensor networks,” to be appeared in Journal of Combinatorial Optimization, vol. 11, no. 1, pp. 21–41, Feb. 2006.
[15] Ma, H.D. and Liu, Y.H., “Some problems of directional sensor networks,” to be appeared in Int. J. Sensor Networks, Vol. 3.2006
[16] Yanli Cai, Wei Lou and Minglu Li, “Target-Oriented Scheduling in Directional Sensor Networks,” to be appeared in 26th IEEE International Conference on Computer Communications, INFOCOM 2007, pp.1550-1558.
[17] Uei-Ren Chen, Bo-Sheng Chiou, Jyun-Ming Chen and Woei Lin,“An Adjustable Target Coverage Method in Directional Sensor Networks,” to be appeared in IEEE APSCC, 2008, pp.174-180.
[18] J. Ai and A. A. Abouzeid, “Coverage by directional sensors in randomly deployed wireless sensor networks,” to be appeared in Journal of Combinatorial Optimization, vol. 11, no. 1, pp. 21–41, Feb. 2006.
[19] Y. Osais, M. St-Hilaire and F. Yu, “Directional sensor placement with optimal sensing range, field of view and orientation,” to be appeared in International Conference on Wireless and Mobile Computing (WIMOB’08), Avignon, France, 2008, pp. 19-24.
[20] Osais, Y., St-Hilaire, M. and Yu, F.R, "On Sensor Placement for Directional Sensor Networks," to be appeared in IEEE International Conference on Communications, 2009. ICC '09, pp. 1-5.
[21] Li Zhang, Jian Tang and Weiyi Zhang, “Strong Barrier Coverage with Directional Sensors,” to be appeared in IEEE on Global Telecommunications Conference, GLOBECOM 2009, pp. 1-6.
[22] Wang, G., Cao, G., &; La Porta, T. (2006). "Movement-assisted sensor deployment." to be appeared in Mobile Computing, IEEE Transactions on, 2006, 5.6: 640-652.
[23] Lee, H. J., Kim, Y. H., Han, Y. H., &; Park, C. Y. (2009, September). "Centroid-based movement assisted sensor deployment schemes in wireless sensor networks." to be appeared in Vehicular Technology Conference Fall (VTC 2009-Fall). IEEE, 2009. p. 1-5.
[24] Jing, L. I., Ruchuan, W. A. N. G., Huang, H., &; Lijuan, S. U. N. (2009). "Voronoi-based coverage optimization for directional sensor networks." to be appeared in Wireless Sensor Network, 2009, 1.05: 417.
[25] Sung, T. W., &; Yang, C. S. (2014). "Voronoi-based coverage improvement approach for wireless directional sensor networks." to be appeared in Journal of Network and Computer Applications, 2014, 39: 202-213.
[26] Okabe, A., Boots, B., Sugihara, K., &; Chiu, S. N. (2009). "Spatial tessellations: concepts and applications of Voronoi diagrams" to be appeared in John Wiley &; Sons, 2009.
[27] Kolahdouzan, M., &; Shahabi, C. (2004, August). "Voronoi-based k nearest neighbor search for spatial network databases." to be appeared in Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. VLDB Endowment, 2004. p. 840-851.
[28] Liang, C. K., Hsu, Y. C., &; Tsai, C. H. (2012, August). "An Effective Coverage Enhancing Algorithm in Directional Sensor Networks." to be appeared in SENSORCOMM 2012, The Sixth International Conference on Sensor Technologies and Applications. 2012. p. 182-188.