臺灣博碩士論文加值系統

近年來，邊界覆蓋(Barrier Coverage)在無線感測網路中是很重要且受到廣泛討論的問題。本論文所運作的場景為國邊界上已先佈下許多固定式感測器且感測器皆有太陽能充電的能力。由於感測器工作耗電後，需要進行太陽能充電，因此，感測器的排程與合作式監控將決定感測器在國邊界上的防衛能力。本論文擬設計一分散式排程技術，透過太陽能充電機制使網路永續運作。所謂d-Trap Coverage意指監控範圍中允許直徑不大於d的空洞產生。這樣的應用可大量的節省感測器電量或硬體成本。本論文針對一個已佈建的感測網路，提出一個感測器輪流醒睡的分散式排程技術，使場景中每個感測器皆可以輪流休息和工作，相較於現有的d-Trap coverage研究，本論文的貢獻如下。首先，感測器因電量不足而無法撐過一個醒睡週期時，將使空洞大於預設的限制值，因此，本論文提出感測器醒睡排程技術，以有效維護d-Trap coverage之要求並將空洞所造成的感測風險平均分散於場景中。

In wireless sensors, trap coverage has recently been proposed as a tradeoff between the availability of sensor nodes and sensing performance. A d-trap coverage is referred to the network where the diameter of each existing hole should be smaller than d. The d-trap offers an efficient framework to tackle the challenge of limited resources in large scale sensor networks. Currently, existing works only studied the network formation for the desired trap coverage. However, how to efficiently schedule sensor nodes between active and sleep modes to satisfy the constraint of trap coverage and prolong the network lifetime is still an open issue. This paper presents an efficient working schedule for d-trap coverage, aiming to satisfy the constraint of trap coverage and prolong the network lifetime. In simulation, the proposed algorithm outperforms the existing works in terms of the number of working sensors, reaming energy ratio, and network lifetime.

目錄
圖目錄 VI
表目錄 IX
第一章、簡介 1
第二章、背景知識:BARRIER COVERAGE和D-TRAP COVERAGE 4
2.1 Barrier Coverage 4
2.2 d-Trap Coverage 5
第三章、無線感測網路在邊界覆蓋應用下具永續生命期之合作感測與太陽能充電排程技術 6
3.1 前言 6
3.2 相關研究 8
3.3 網路環境與問題描述 10
3.4 演算法 15
3.5 夜間延伸 SCH-Scheduling 29
3.6 模擬實驗 32
第四章、無線感測網路中具能源效益考量之D-TRAP覆蓋排程機制 40
4.1 前言 40
4.2 網路環境與問題描述 41
4.3 演算法 45
4.4 模擬實驗 57
第五章、結論 68
參考文獻 69
附錄-英文論文 73

圖目錄
圖一、Coverage運用的場景。 1
圖二、國家邊界防禦以及區域內防禦。 2
圖三、網路環境佈署。 11
圖四、Elfes sensing model。 11
圖五、網路環境切割。 16
圖六、格子距感測器中心最遠的頂點。 16
圖七、感測器隨機佈點範圍。 18
圖八、感測器空間貢獻值的計算。 20
圖九、國邊界覆蓋權重值計算。 25
圖十、Solar Harvesting based Cooperative Scheduling Algorithm (SHC-Scheduling)。 29
圖十一、感測器夜晚白天的工作轉換。 31
圖十二、感測器電量儲存比例與總感測器數量之比較。 33
圖十三、總感測器數量與感測機率值之比較。 34
圖十四、不同密度場景圖。 35
圖十五、感測機率值與不同密度場景之比較。 36
圖十六、格子邊長與防禦機率值之關係。 37
圖十七、不同密度場景與格子切割大小對感測機率值的關係。 38
圖十八、離散程度與感測機率之差距比較。 39
圖十九、在區域上切割出一六邊形。 46
圖二十、緊鄰紅色六邊形之第一圈六邊形排列。 47
圖二十一、六邊形規則排列。 48
圖二十二、網路環境中的六角形排列。 49
圖二十三、網路環境中的六角形排列。 52
圖二十四、公式說明圖例。 53
圖二十五、空洞維護範圍限制。 55
圖二十六、產生之空洞問題。 57
圖二十七、總感測器剩餘電量的比較。 59
圖二十八、監控區域之佈點密度。 60
圖二十九、感測器佈點密度與網路生命期之比較。 61
圖三十、空洞限制值調整與網路生命期之關係。 62
圖三十一、浪費電量與空洞限制值之關係。 63
圖三十二、不同密度場景與執行監控任務之感測器比較。 64
圖三十三、在不同密度場景中之控制成本消耗比較。 65
圖三十四、不同密度場景調整空洞限制大小與執行監控任務感測器數量之比較。 66
圖三十五、調整週期長度與網路生命期比較。 67
圖三十六、調整週期長度與感測器平均剩餘電量之比較。 67

表目錄
表一、模擬相關參數。 32
表二、與感測器C有交集之感測器帶入公式運算。 54
表三、模擬相關參數。 58

[1]J. He and H. Shi, “Finding barriers with minimum number of sensors in wireless sensor networks,” The 2010 IEEE International Conference on Communications (IEEE ICC), South Africa, May 2010.
[2]G. Yang and D. Qiao, “Multi-Round Sensor Deployment for Guaranteed Barrier Coverage,” The 2010 IEEE Conference on Computer Communications (IEEE INFOCOM), San Diego, March 2010.
[3]J. Du, Y. Li, H. Liu and K. Sha, “On Sweep Coverage with Minimum Mobile Sensors,” The 2010 IEEE International Conference on Parallel and Distributed Systems (IEEE ICPADS), Shanghai China, December 2010.
[4]M. Li, W. Cheng, K. Liu, Y. He, X. Y. Li and X. Liao, “Sweep Coverage with Mobile Sensors,” The IEEE Transactions on Mobile Computing, vol. 10, no. 11, November 2011.
[5]C. Y. Chang, C. Y. Lin, C. Y. Hsieh and Y. J. Ho, “Patrolling Mechanisms for Disconnected Targets in Wireless Mobile Data Mules Networks,” The 2011 IEEE International Conference on Parallel Processing (IEEE ICPP), Taiwan, September 2011.
[6]C. Liu, K. Wu, Y. Xiao, and B. Sun, “Random Coverage with Guaranteed Connectivity: Joint Scheduling for Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 6, June 2006, pp. 562–575.
[7]Z. Yun, X. Bai, D. Xuan, T. H. Lai, and W. Jia, “Optimal Deployment Patterns for Full Coverage and k-Connectivity (k ≤ 6) Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, vol. 18, no. 3, June 2010, pp. 934–947.
[8]D. Tian and N. D. Georganas, “A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks,” Proceedings of First International Workshop on Wireless Sensor Networks and Applications, 2002.
[9]D. Tian and N. D. Georganas, “A Node Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks,” Wireless Communications and Mobile Computing Journal, vol. 3, no.2, pp.271-290, Mar. 2003.
[10]B. Liu, O. Dousse, J. Wang and A. Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” ACM International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHOC), 2008.
[11]S. Kumar, T. Lai, M. Posner, and P. Sinha, “Maximizing the Lifetime of a Barrier of Wireless Sensors,” IEEE Trans. on Mobile Computing, 2010.
[12]T. Yan, T. He, and J. A. Stankovic, “Differentiated Surveillance Service for Sensor Networks,” ACM Conference on Embedded Networked Sensor Systems, 2003.
[13]F. Ye, G. Zhong, S. Lu, and L. Zhang, “Energy Efficient Robust Sensing Coverage in Large Sensor Networks,” UCLA Technical Report, 2002.
[14]O. M. Younis, M. M. Krunz, and S. Ramasubramanian, “ROC：Resilient Online Coverage for Surveillance Application,” IEEE/ACM Transactions on Networking, vol. 19, no. 1, pp.251-264, Feb. 2011.
[15]Balister P, Zizhan Zheng, Kumar S, Sinha P., “Trap coverage: Allowing coverage holes of bounded diameter in wireless sensor networks,” The 2009 IEEE Conference on Computer Communications (IEEE INFOCOM), Rio de Janeiro, 19-25 April 2009.
[16]Y. Liu and W. Liang, “Approximate coverage in wireless sensor networks,” IEEE LCN, Sydney, Nov 2005.
[17]Chih-Yung Chang, Li-Ling Hung, Yu-Chieh Chen, and Ming-Hsien Li “On-Supporting Energy Balanced k-Barrier Coverage In Wireless Sensor Networks,”ACM/IEEE, 2009.
[18]A. Abu-Baker, H. Huang, E. Johnson, and S. Misra, “Green Diffusion: Data Dissemination in Sensor Networks Using Solar Power,” IEEE CCNC, USA, January 2011.
[19]P. Lee, Z. A. Eu, M. Han, and H. P. Tan, “Empirical Modeling of a Solar-Powered Energy Harvesting Wireless Sensor Node for Time-Slotted Operation” IEEE WCNC, Mexico, March, 2011.
[20]Ashraf Hossain, P. K. Biswas, S. Chakrabarti “Sensing Models and Its Impact on Network Coverage in Wireless Sensor Network”, ICIIS, 2008.
[21]Junkun Li, Jiming Chen, Shibo He, Tian He, Yu Gu, Youxian Sun, “On energy-efficient trap coverage in wireless sensor networks,” ACM Transactions on Sensor Networks, vol. 10, no. 1, Article 2, Nov. 2013.
[22]G. W. Stewart. (1990). Computer Science and Applied Mathematics (1st ed). New York and London：Academic Press.