臺灣博碩士論文加值系統

對於無線感測網路(Wireless Sensor Network)來說，覆蓋問題與存活週期一直以來都是重要的議題，如何有效的利用感測器有限的電量達到最長的存活週期並且同時保有可容許的覆蓋率為我們主要的目標。現有的相關文獻中，絕大部分的研究著重於二維的理想平面或是三維的全空間。然而實際的地形是凹凸崎嶇不平的，因此現有的解決方法無法得到較真實的結果，所以我們利用Spline Function[1]產生FoI (Field of Interest, FoI)[23][24]來建置具有起伏的三維地形。此外我們提出了EES演算法，在不同的時段當中將一部分的Sensor node當作中繼轉發節點，讓感測器間重疊感測的區域變少，以避免不必要的能量耗損，並且透過睡眠機制解決單一節點覆蓋半徑過大造成存活時間過短的問題，使得無線感測網路的整體存活時間增加並擁有相同的覆蓋率。在評價結果，我們所提出的算法提供了更高效的連接和高覆蓋率。

Coverage and connection problem have been the topic which worth exploring in wireless sensor networks (WSNs). How to effectively use the limited power to achieve the longest lifetime and keep acceptable coverage ratio are the major goals. Currently, some researchers have started to study this topic, but their proposed methods focused on 2D ideal plane or 3D full space. However, the actual terrain is rugged and uneven. Therefore, the exist solutions cannot obtain the fairest information. In order to solve this problem, we use the Spline Function [1] generated FoI (Field of Interest, FoI)[23][24] to build three-dimensional terrain. Furthermore, we propose the EES algorithm, which to select a part of the sensor nodes as the relay node at different epoch, hence the overlap areas between the sensor sensing range is reduced so that the unnecessary energy consumption can be avoided. Moverover, our proposed sleep mechanism can solve a shorter lifetime problem is causing by the coverage radius of a single node. In this way, it increasing the survival time of overall wireless sensor networks with acceptable coverage ratio. By the simulation results, the proposed algorithm indeed provides a more efficient connections and high coverage.

目錄
摘要.........................................................i
Abstract....................................................ii
第一章 緒論.................................................1
1.1 簡介.................................................1
1.2 研究目的..............................................3
1.3 本文架構..............................................4
第二章 研究相關背景...........................................5
2.1 3D-Space Coverage....................................5
2.2 Spline function......................................7
2.3 Overlapping coverage.................................9
第三章 研究環境設置...........................................11
3.1 問題定義..............................................11
3.2 條件限制..............................................12
3.3 網路模型..............................................12
3.4 覆蓋模型..............................................13
3.5 連接模型..............................................14
3.6 能量模型..............................................15
第四章 EES排程演算法..........................................17
4.1 中繼節點傳輸機制與睡眠機制...............................19
4.1.1 傳輸機制 ..........................................19
4.1.2 睡眠機制 ..........................................21
4.2 重疊區域計算...........................................22
4.3 節點的配置與排程........................................25
4.4 演算法................................................27
第五章 模擬...................................................33
5.1 模擬設置...............................................34
5.2 覆蓋與能源消耗..........................................36
5.3 生命週期與額外的能源耗損..................................41
5.4 地形的影響.............................................44
第六章 結論..................................................53
參考文獻 ......................................................55

圖目錄
圖2- 1 Coverage Hole.........................................5
圖2- 2 Spline Function curve.................................7
圖2- 3 Connected Sensor Coverage Problem.....................9
圖2- 4 Sleep rate of 25%.....................................10 圖2- 5 Sleep rate of 50%.....................................14
圖3- 1 EPC的重疊區域...........................................14
圖3- 2 節點之間的距離大於半徑和...................................14
圖3- 3 節點之間的距離等於半徑和...................................15
圖3- 4 節點之間的距離小於半徑和...................................15
圖4- 1 EES演算法流程圖..........................................18
圖4- 2 EES演算法的路徑選擇.......................................19
圖4- 3 中繼傳輸節點.............................................21
圖4- 4 重疊區域的定義...........................................22
圖4- 5 重疊面積的計算...........................................23
圖4- 6 兩個圓以上的重疊面積計算...................................24
圖4- 7 重疊面積的組成...........................................25
圖4- 8 邊界節點與內部節點的佈署...................................26
圖5- 1 由DT定義的FOI...........................................34
圖5- 2 由NURBS定義的地形........................................34
圖5- 3 情境一：斜坡(45°)........................................34
圖5- 4 Original deployment(Slope 45°-3D).....................35
圖5- 5 Original deployment(Slope 45°-2D).....................36
圖5- 6 EPC deployment(Slope 45°-3D)..........................37
圖5- 7 EPC deployment(Slope 45°-2D)..........................37
圖5- 8 EES deployment(Slope 45°-3D)..........................38
圖5- 9 EES deployment(Slope 45°-2D)..........................38
圖5- 10 The number of active nodes of the Slope...............39
圖5- 11 The power consumption of the Slope....................40
圖5- 12 The remaining power of the Slope......................41
圖5- 13 The additional energy consumption of the Slope........42
圖5- 14 Coverage rate of the Slope............................43
圖5- 15 The number of surviving nodes of the Slope............43
圖5- 16 情境二;Peak............................................44
圖5- 17 Original deployment(peak-3D)..........................45
圖5- 18 EPC deployment(peak-3D)...............................45
圖5- 19 EES deployment(peak-3D)...............................46
圖5- 20 The remaining power of the Peak.......................47
圖5- 21 The number of active nodes of the Peak................48
圖5- 22 The additional energy consumption of the Peak.........48
圖5- 23 Coverage rate of the Peak.............................49
圖5- 24 The remaining power of the Slope and the Peak.........50
圖5- 25 三種不同高度的情境。......................................51
圖5- 26 Coverage rate of different height.....................52

表目錄
TABLE I TOPOLOGY ALGORITHM....................................28
TABLE II BOUNDARY SCHEDULING..................................28
TABLE III INTERNAL SCHEDULING.................................29

[1].Santosh Kumar, Ten H. Lai, and Anish Arora, “Barrier coverage with wireless sensors,” in Proceedings of 11th ACM Annual International Conference on Mobile Computing and Networking (MobiCom 2005), pp. 284–298, New York, NY, USA, 2005.
[2].Xiaole Bai, Dong Xuan, Ziqiu Yun, Ten H. Lai, and Weijia Jia, “Complete optimal deployment patterns for full-coverage and k-connectivity (k≤6)wireless sensor networks,” in Proceedings of 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2008), pp. 401–410,New York, NY, USA, 2008.
[3].Chi-Fu Huang, Yu-Chee Tseng, and Li-Chu Lo, “The coverage problem in three-dimensional wireless sensor networks,” in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM 2004), pp. 5:3182–3186 Vol.5, Nov.-3, Dallas, Texas, USA, Dec. 2004.
[4].Mohamed K. Watfa and Sesh. Commuri, “A coverage algorithm in 3d wireless sensor networks,” in Proceedings of 1st International Symposium on Wireless Pervasive Computing (ISWPC 2006),pp. 6, Phuket, Thailand, Jan. 2006.
[5].S. M. Nazrul. Alam and Zygmunt J. Haas, “Coverage and Connectivity in Three-Dimensional Networks,” in Proceedings of 12th ACM Annual International Conference on Mobile Computing and Networking (MobiCom 2006), pp. 346-357, Los Angeles, GA, USA, Sep. 2006.
[6].Habib M. Ammari and Sajal K. Das, “Critical Density for Coverage and Connectivity in Three-Dimensional Wireless Sensor Networks Using Continuum Percolation,” IEEE Transactions on Parallel and Distributed Systems (TPDS), vol. 20, no. 6, pp. 872-885 , June 2009.
[7].Liang Liu and Huadong Ma, “On Coverage of Wireless Sensor Networks for Rolling Terrains,” IEEE Transactions on Parallel and Distributed Systems (TPDS), Vol. 23, pp. 118-125, Jan. 2011.
[8].K. Kar and S. Banerjee,” Node Placement for Connected Coverage in Sensor Networks ”, WiOpt Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks ,2003.
[9].Gupta, H , Zongheng Zhou , Das, S.R., Gu, Q ,“Connected sensor cover: self-organization of sensor networks for efficient query execution ”, IEEE/ACM Transactions on Networking , pp. 55 – 67, Feb. 2006.
[10].Habib M. Ammari and Sajal K. Das, “A Study of k-Coverage and Measures of Connectivity in 3D Wireless Sensor Networks”, IEEE Transactions on Computers (TC), pp. 243 – 257, Feb. 2009.
[11].Hongbo Jiang, Shengkai Zhang, Guang Tan and Chonggang Wang,“CABET: Connectivitybased boundary extraction of large-scale 3D sensor networks,” in Proceedings of 30th Annual IEEE International Conference on Computer Communications IEEE (INFOCOM 2011), pp.784 – 792, Shanghai, China, Apr. 2011.
[12].Hongyu Zhou, Hongyi Wu, Su Xia, Miao Jin and Ning Din, “A distributed triangulation algorithm for wireless sensor networks on 2D and 3D surface,” in Proceedings of 30th Annual IEEE International Conference on Computer Communications IEEE (INFOCOM 2011), pp. 1053 – 1061, Shanghai, China, , Apr. 2011.
[13].MATLAB, available from: http://www.mathworks.com/
[14].Weifa Liang, Baichen Chen and Jeffrey Xu Yu,”Response time constrained top-k query simulation in sensor networks,” Proceeding of 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS ’08), pp. 575-582, Dec. 8-10, 2008.
[15].Y-S Yen, Sheng Hong, R-S Chang, H-C Chao, “Controlled deployments for wireless sensor net works” IET Communications, pp. 820 – 829, May. 2009.
[16].卓信宏, 曾繁勛, 周立德, 趙涵捷, “基於樣條函數定義無線感測網路之複雜起伏地形,” 第十一屆離島資訊技術與應用研討會, Penghu, Taiwan, May, 2012 , pp 25-26
[17].Fan-Hsun Tseng , Hsin-Hung Cho , Li-Der Chou , Han-Chieh Chao ,“Efficient Power Conservation Mechanism in Spline Function Defined WSN Terrain “, IEEE Sensors Journal , Vol.14, No.3, March. 2014,pp 853-864
[18].Gupta, H , Zongheng Zhou , Das, S.R., Gu, Q ,“Connected sensor cover: self-organization of sensor networks for efficient query execution “, IEEE/ACM Transactions on Networking , Vol. 14, No. 1, Feb. 2006, pp. 55 – 67
[19].Cardei, M, Thai, M.T , Yingshu Li, Weili Wu ,“Energy-Efficient Target Coverage in Wireless Sensor Networks“, IEEE/ACM Transactions on Networking , Vol. 14, No. 1, Feb. 2006, pp. 55 – 67
[20].M.-C. Zhao, J. Lei, M.-Y. Wu, Y. Liu, and W. Shu, “Surface coverage in wireless sensor networks,” in Proc. IEEE Int. Conf. INFOCOM, Apr. 2009, pp. 109–117.
[21].H. Hatime, K. Namuduri, and J. M. Watkins, “OCTOPUS: An ondemand communication topology updating strategy for mobile sensor networks,” IEEE Sensors J., vol. 11, no. 4, pp. 1004–1012, Apr. 2011.
[22].S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava,“Worst and best-case coverage in sensor networks,” IEEE Trans. Mobile Comput., vol. 4, no. 1, pp. 84–92, Jan. 2005.
[23].Y. Bejerano, “Coverage verification without location information,” IEEE Trans. Mobile Comput., vol. 11, no. 4, pp. 631–643, Apr. 2012.
[24].Y. S. Jeong, Y. J. Chung, and J. H. Park, “Visualisation of efficiency coverage and energy consumption of sensors in wireless sensor networks using heat map,” IET Commun., vol. 5, no. 8, pp. 1129–1137, May 2011.
[25].D. Avis, D. Bremner, and R. Seidel, “How good are convex hull algorithms?” Elsevier Comput. Geometry, vol. 7, nos. 5–6, pp. 265–301, Apr. 1997.
[26].D. F. Rogers, “An Introduction to NURBS: With Historical Perspective. ” Annapolis, MD, USA: Elsevier, 2001.
[27].Wei Ye, John Heidemann, Deborah Estrin,“ An energy-efficient MAC protocol for wireless sensor networks “, IEEE Computer and Communications Societies. , Vol. 3, 2002, pp. 1567 –1576
[28].Al-Karaki, J.N., Kamal, A.E,“ Routing techniques in wireless sensor networks: a survey “, IEEE Wireless Communications , Vol. 11, Dec 2004, pp. 6 –24
[29].Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, Erdal Cayirci,“ A survey on sensor networks “, IEEE Communications Magazine , Vol. 40, Aug 2002, pp. 102 –114
[30].Chee-Yee Chong, Kumar, S.P.,“ Sensor networks: evolution, opportunities, and challenges “, IEEE Proceedings , Vol. 91, Aug 2003, pp. 1247 –1258
[31].Wei-Ming Chen, Chung-Sheng Li, Fu-Yu Chiang, Han-Chieh Chao,“ Jumping ant routing algorithm for sensor networks “, Computer Communications , Vol. 30, Oct 2007, pp. 2892 –2903
[32].Chi‐Yuan Chen, Han‐Chieh Chao,“ A survey of key distribution in wireless sensor networks “, Security and Communication Networks, published online,Vol. 30, Jul 2011
[33].Xiaofei Wang, Min Chen, Taekyoung Kwon, H-C Chao,“Multiple mobile agents' itinerary planning in wireless sensor networks: survey and evaluation “, Published in IET Communications , Vol. 5, Aug 2011, pp. 1769 –1776
[34].Y.-S. Yen, S. Hong, R.-S. Chang, H.-C. Chao,“ Controlled deployments for wireless sensor networks “, Published in IET Communications , Vol. 3, May 2009, pp. 820 –829
[35].Yi Zou, Chakrabarty, K,“ A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks “, IEEE Transactions on Computers , Vol. 54, Aug 2005, pp. 978 –991
[36].Demin Wang, Bin Xie, Agrawal, D.P,“ Coverage and Lifetime Optimization of Wireless Sensor Networks with Gaussian Distribution “, IEEE Transactions on Mobile Computing , Vol. 7, Apr 2008, pp. 1444 –1458