臺灣博碩士論文加值系統

無線感測網路就是由許多微小的感測器組成一個系統網路，並佈署在難以深入前往的區域，經由感測器中的感測能力與無線網路技術回傳該地區之環境參數。每個感測器將監控到的資料立即回傳給收集端，此方法能夠立即獲取感測環境資訊，但若收集端是處於一個較遠距離的位置，對每個感測器在傳送資料所消耗的能源是相當龐大的，導致整體的感測時間縮減，欲繼續監控該區域，則必須前往更換電池或再佈下更多新的感測器。因此該如何佈署較少的感測器節點數與有效的使用能源策略兩個議題成為近來的主要研究。另外，近年來再生能源的議題熱絡，若將所佈署下的感測器加入轉換再生能源裝置進行自我能源回復，進而使感測網路的監控變得更加的持久。本篇研究在單一充電區與多個充電區能固定接收到太陽的照射等場景所設計之演算法，本篇論文對每個感測器中加入行動能力，在具備有充電的區域中，感測器能自我能量回復並進行資料收集，設計更有效率的救援方法讓感測節點能來回穿梭於充電區域，降低能源消耗與持久的環境監控。最後，行動感測器能自我組態前往做更換位置救援的動作，使得該區域中的感測生命週期延長甚至永久存在。由於過去並無相關文獻提出結合佈署演算法與移動節點的策略，因此在後面的模擬結果中，本篇論文將以過去的佈署演算法與本篇論文提出的佈署演算法，並結合本篇論文提出的兩種移動策略比較其整體生命週期、覆蓋率以及移動次數，另外，在不同場景下提出的移動策略在整體生命週期提升了10%，在多個充電區的場景中覆蓋率達到96%，在移動次數方面FED比MAX_COV_AVG多移動了200多次。

A wireless sensor network consists of many tiny devices. These devices are sensors deployed in the dangerous regions or the unreachable locations. Sensors collect the environmental information and transfer to the device called as sink via the wireless communication technology. When the sink locates far away from the interested area, sensors require spending much energy on delivering the collected data. This will shorten the operation time of sensors. To continue the monitoring operation, sensors need replacing the battery or more sensors should be deployed. Therefore, the research topic is how to cover the interested area with fewest numbers of sensors and how to minimize the energy consumption. In most of the current studies, sensors do not have the ability to recharge the energy. If the sensors can fulfill its power, the sensors must operate longer. Thus, this paper proposes two algorithms for energy rechargeable sensor networks. Sensors are moveable, and they will move back and forth between duty locations and the recharging areas. Single and multiple recharging areas are considered. The experimental results show that the operation duration in the multiple recharging areas improves 10% than in the single recharging area, and coverage area achieves 96%. The number of movements in the proposed two algorithms is 200 times between the MAX_COV_AVG and FED.

摘要.............................................................................................................................................i
Abstract.......................................................................................................................................ii
誌謝...........................................................................................................................................iii
表目錄.......................................................................................................................................vi
圖目錄......................................................................................................................................vii
第一章 簡介........................................................................................................................1
1.1 研究背景 ................................................................................................................ 1
1.2 研究動機 ................................................................................................................ 3
1.3 研究方法 ................................................................................................................ 4
1.4 論文架構 ................................................................................................................ 5
第二章相關研究與文獻探討..................................................................................................6
2.1 無線感測網路(WSNs) ........................................................................................... 6
2.1.1. WSNs簡介 ................................................................................................ 6
2.1.2. 無線移動感測網路(WMSNs)簡介 ........................................................... 7
2.1.3. 無線感測充電網路(WSRNs)簡介 ............................................................ 7
2.2 文獻探討 ................................................................................................................ 8
2.2.1 佈署問題(Deployment) ............................................................................. 8
2.2.2 網路拓樸協定 .......................................................................................... 16
2.2.3 排程協定 .................................................................................................. 23
第三章解決WSNs問題之演算法.......................................................................................26
3.1 解決佈署問題演算法 .......................................................................................... 26
3.1.1 有效且快速的人工佈點演算法(Fast and Efficient Deploying Algorithm, FED) ..................................................................................................... 27
3.2 解決WSNs有效能源使用演算法 ..................................................................... 33
3.2.1 節點自我組態與佈署備援演算法(Self Organization and Backup Algorithm, SOBA) .................................................................................................. 33
3.2.2 節點自我組態與佈署救援演算法(Self Organization and Dispatching Algorithm, SODA) .................................................................................................. 40
第四章模擬結果與分析........................................................................................................48
4.1. 模擬環境假設 ...................................................................................................... 48
4.2. 應用模組 .............................................................................................................. 48
4.2.1 傳遞封包能源消耗模組 .......................................................................... 49
4.2.2 節點移動與回復能源模組 ...................................................................... 49
4.3. 模擬環境 .............................................................................................................. 50
4.4 模擬結果 .............................................................................................................. 52
4.4.1 整體感測生命週期 .................................................................................. 52
v
4.4.2 整體覆蓋率 .............................................................................................. 56
4.4.3 節點移動次數 .......................................................................................... 59
4.5 結果比較與分析 .................................................................................................. 63
第五章 結論與未來展望..................................................................................................64
參考文獻..................................................................................................................................65
Extended Abstract ..................................................................................................................69
簡歷(CV)..................................................................................................................................75

[1]O.D. Incel, A. Ghosh, B. Krishnamachari, K. Chintalapudi, “Fast Data Collection in Tree-Based Wireless Sensor Networks,” in proceedings of the IEEE Transactions on Mobile Computing, Jan. 2012, pp. 86 – 99.
[2]S.D. Muruganathan, D.C.F. Ma, R.I. Bhasin, A. Fapojuwo, “A centralized energy-efficient routing protocol for wireless sensor networks,” in proceedings of the IEEE Communications Magazine, March 2005, pp. S8 – 13.
[3]S. Lindsey, C.S. Raghavendra, “PEGASIS: Power-Efficient GAthering in Sensor Information Systems,” in proceedings of the IEEE Aerospace Conference, vol.3, 2002, pp. 3-1125 - 3-1130.
[4]W.B. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” in proceedings of the IEEE Transactions on Wireless Communications, Oct 2002, pp. 660 – 670
[5]H. Luo, F. Ye, J. Cheng, S. Lu, L. Zhang, “TTDD: A Two-tier Data Dissemination Model for Large-scale Wireless Sensor Networks,” in proceedings of the ACM Journal of Mobile Networks and Applications (MONET), 2002, pp. 161-175.
[6]P.K. Poonguzhali, “Energy Efficient Realization of Clustering Patch Routing Protocol in Wireless Sensors Network,” in proceedings of the International Conference on Computer Communication and Informatics (ICCCI), 10-12 Jan. 2012, pp. 1-6.
[7]Z. Aliouat, M. Aliouat, “Effective Energy Management in Routing Protocol for Wireless Sensor Networks,” in proceedings of the International Conference on New Technologies, Mobility and Security (NTMS), 7-10 May 2012, pp. 1-5.
[8]S. Lindsey, C. Raghavendra, K.M. Sivalingam, “Data Gathering Algorithms in Sensor Networks Using Energy Metrics,” in proceedings of the IEEE Transactions on Parallel and Distributed Systems, Sep 2002, pp. 924-935.
[9]Z.H. Yuan, G.F. Wang, “Sensor Deployment Strategy for Collaborative Target Detection with Guaranteed Accuracy,” in proceedings of the 4th International Conference on Mobile Ad-hoc and Sensor Networks 2008 (MSN08), 10-12 December 2008, pp.68-71.
[10]J. Wu, J. Zhu, “Sensor Node Optimal Placement Algorithm Based on Coverage Rates,” in proceedings of the IEEE International Conference on Computer Science and Service System (CSSS), 27-29 June 2011, pp. 2547 – 2550.
[11]S.S. Dhillon, K. Chakrabarty, S.S. Iyengar, “Sensor Placement for Grid Coverage Under Imprecise Detections,” in proceedings of the 5th International Conference on Information Fusion 2002, 8-11 July 2002, vol. 2, pp.1581-1587.
[12]Y.R. Tsai, Y.J. Tsai, “Sub-optimal Step-by-Step Node Deployment Algorithm for User Localization in Wireless Sensor Networks,” in proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous and Trustworthy Computing 2008 (SUTC08), 11-13 June 2008, pp.114-121.
[13]Y. Shang, W. Ruml, “Improved MDS-based localization,” in proceedings of the IEEE International Conference on INFOCOM 2004, Mar. 2004, vol. 4, pp. 2640–2651.
[14]S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. B. Srivastava, “Coverage Problems in Wireless Ad-hoc Sensor Network,” in proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM01), vol. 3, 22-26 April 2001, pp.1380-1387.
[15]S.S. Dhillon, K. Chakrabarty, “Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks,” in proceedings of the IEEE International Conference on Wireless Communications and Networking (WCNC), vol.3, 20-20 March 2003, pp. 1609 - 1614.
[16]S.S. Dhillon, K. Chakrabarty, S.S. Iyengar, “Sensor Placement for Grid Coverage Under Imprecise Detections,” in proceedings of the 5th International Conference on Information Fusion 2002, vol. 2, 8-11 July 2002, pp.1581-1587.
[17]R. Xiaoping, C. Zixing, “A Distributed Actor Deployment Algorithm for Maximum Connected Coverage in WSAN,” in proceedings of the Fifth International Conference on Natural Computation(ICNC ''09), 14-16 Aug. 2009, pp. 283 – 287.
[18]W. Bang, W. Wei, V. Srinivasan, C. Kee-chaing, “Information coverage for wireless sensor networks,” in proceedings of the IEEE Communications Letters, Nov. 2005, pp. 967-969.
[19]W. Bang, C. Kee-chaing, V. Srinivasan, W. Wei, “Information Coverage in Randomly Deployed Wireless Sensor Networks,” in proceedings of the IEEE Transactions on Wireless Communications, August 2007, pp. 2994 – 3004.
[20]R. Saravanakumar, S.G. Susila, J. Raja, “An energy efficient cluster based node scheduling protocol for wireless sensor networks,” in proceedings of the 2010 IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), 28-29 Dec. 2010, pp. 1 – 5.
[21]Z. Yaxiong, W. Jie, L. Feng, L. Sanglu, “On Maximizing the Lifetime of Wireless Sensor Networks Using Virtual Backbone Scheduling,” in proceedings of the IEEE Transactions on Parallel and Distributed Systems, Aug. 2012, pp. 1528 – 1535.
[22]R. Chauhan, V. Gupta, “Energy Efficient Sleep Scheduled Clustering & Spanning Tree based data aggregation in wireless sensor network,” in proceedings of the International Conference on Recent Advances in Information Technology (RAIT), 15-17 March 2012, pp. 536 – 541.
[23]J.L. Zechinelli-Martini, P. Bucciol, G. Vargas-Solar, “Energy aware data aggregation in Wireless Sensor Networks,” in proceedings of the International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace & Electronic Systems Technology (Wireless VITAE), Feb. 28 2011-March 3 2011, pp.1-5.
[24]J.G. Olascuaga-Cabrera, A. Mendez-Vazquez, E. Lopez-Mellado, “Wireless Network Formation and Maintaining for Mobile Devices Based on Self-organization Strategies,” in proceedings of the International Multi-Conference on Computing in the Global Information Technology (ICCGI), 20-25 Sept. 2010, pp.131-138.
[25]M. Asim, H. Mokhtar, M.Z. Khan, M. Merabti, “A Sensor Relocation Scheme for Wireless Sensor Networks,” in proceedings of the 2011 IEEE Workshops of International Conference on Advanced Information Networking and Applications (WAINA), 22-25 March 2011, pp. 808 – 813.
[26]G. Sibley, M. Rahimi, G. Sukhatme, "Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks," in proceedings of the IEEE International Conference on Robotics and Automation (ICRA2002), 2002, pp. 1143 – 1148.
[27]M. Rahimi, H. Shah, G. Sukhatme, J. Heideman, “Studying the feasibility of energy harvesting in a mobile sensor network,” in proceedings of the IEEE International Conference on Robotics and Automation, 14-19 Sept. 2003, pp. 19 - 24.
[28]R.C. Luo, O. Chen, “Mobile Sensor Node Deployment and Asynchronous Power Management for Wireless Sensor Networks,” in proceedings of the IEEE Transactions on Industrial Electronics, May 2012, pp. 2377 – 2385.
[29]IEEE std. 1451.5 “IEEE Standard for a Smart Transducer Interface for Sensors and Actuators Wireless Communication Protocols and Transducer Electronic Data Sheet (TEDS) Formats” Oct. 5 2007.
[30]J.P.K. Gilb, SiBEAM, Sunnyvale, CA, USA “The Wireless Dictionary” 2005, pp. c1 – 113.
[31]IEEE std. 1902.1 “IEEE Standard for Long Wavelength Wireless Network Protocol” March 31 2009.