淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


  查詢圖書館館藏目錄
系統識別號 U0002-0608201417031100
中文論文名稱 用於低功耗多頻道無線感測網路之快速資料收集演算法
英文論文名稱 Fast Convergecast for Low-Duty-Cycled Multi-Channel Wireless Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 102
學期 2
出版年 103
研究生中文姓名 李奕勳
研究生英文姓名 Yi-Hsun Lee
學號 601410037
學位類別 碩士
語文別 英文
口試日期 2014-06-16
論文頁數 43頁
口試委員 指導教授-潘孟鉉
委員-黃啟富
委員-鄭建富
委員-潘孟鉉
中文關鍵字 資料收集  圖論  多頻道  排程  無線感測網路 
英文關鍵字 convergecast  graph theory  multichannel  scheduling  wireless sensor network 
學科別分類 學科別應用科學資訊工程
中文摘要 資料收集是在許多無線感測器網絡應用中的基礎工作。為了節省感測器之電量,許多先前的無線感測器網路的研究討論如何排程傳輸連結上之節點睡醒時機(或稱時槽)。為了節省資料延遲,傳輸連結所使用之時槽必須小心的指派。近年來,多頻道的概念被提出可應用於指派時槽的方法中。當網絡中有多個可用頻道時,可使得傳輸對之間的干擾可被消除,因此亦可更進一步地降低資料回報延遲。在本篇論文中,我們將上述的場景定義為一最小延遲排程問題(minimal delay scheduling problem),並證明此問題為一 NP-complete問題,我們提出了一個包含三階段的演算法。在前兩階段中,我們的目標是盡可能減少資料回報之延遲,我們透過觀察網絡拓樸及各種不同的指派策略之方式來設計我們的演算法。而在第三階段中,我們的目標是消除傳輸連接間的干擾,並仔細調整前一階段所指派之時槽。透過模擬和實作結果,我們發現我們所設計之演算法能有效地降低多頻道無線感測器網絡之資料收集延遲。
英文摘要 Convergecast is a fundamental operation in many wireless sensor network (WSN) applications. To conserve energy, many previous WSN protocols discuss to periodically schedule active timings (or say slots) of transmission links in the network. When collecting data, the slots should be carefully assigned to conserve latency. Recently, the multichannel concept is utilized to facilitate slot assignment. When the network has multiple channels, the convergecast latency can be further reduced since the interferences between transmission links can be eliminated .In this work, we model the above scenario as a minimal delay scheduling (MDS) problem, and prove it as an NP-complete problem. We propose a heuristic algorithm, which contains three phases. In the first two phases, we aim to minimize the report latency as possible as we can. Our designs are based on several observations on the shape of the network and on the assignment strategies. Then, in the third phase, we aim to eliminate interferences between links, and carefully adjust some slots if necessary. Simulation and implementation results indicate that the proposed scheme can effectively reduce the convergecast latency in WSNs with multiple channels.
論文目次 Contents
Chapter 1 Introduction 1
Chapter 2 Related works 5
Chapter 3 Network models 8
Chapter 4 The proposed scheme 12
4.1 The Tree Formation Phase 12
4.2 The Slot Assignment Phase 15
4.3 The Channel Assignment Phase 20
Chapter 5 Simulation Results 26
Chapter 6 Implementation Results 30
Chapter 7 Conclusions 33
Bibliography 34
Appendix 36
附錄 38

List of Figures
Figure 1.1: The network scenario. 3
Figure 3.1: Interference relationships. 9
Figure 4.1: An example of the step 3 in the proposed tree formation phase. 14
Figure 4.2: An example of the step 3 of the proposed slot assignment scheme. 16
Figure 4.3: A slot assignment result of the complete tree with parameters Dg and Dp. 17
Figure 4.4: The relationship between i and nodes in PI(i). 21
Figure 5.1: Simulation results on the effects of network size when there are (a) unlimited and (b) limited number of channels. 27
Figure 5.2: Simulation results on the effects of (a) network density and (b)transmission ranges of nodes. 28
Figure 5.3: Simulation results on the effects of the number of channels. 29
Figure 6.1: The tree topology and slot and channel assignment results of our implementation. 32
Figure 6.2: Experiment results of OUR and CF. 32
參考文獻 [1] Jennic JN5148. http://www.jennic.com/.
[2] T.-S. Chen, H.-W. Tsai, and C.-P. Chu. Adjustable convergecast tree protocol for wire-less sensor networks. Elsevier Computer Communications, 33(5):559–570, 2010.
[3] J. Elson, L. Girod, and D. Estrin. Fine-grained network time synchronization using reference broadcasts. In Proc. of the USENIX Symposium on Operating Systems Design and Implementation(OSDI), 2002.
[4] F. Ghods, H. Yousefi, A. M. Afshin Hemmatyar, and A. Movaghar. MC-MLAS: Multi-channel minimum latency aggregation scheduling in wireless sensor networks. Elsevier Computer Networks, 57(18):3812–3825, 2013.
[5] A. Ghosh, O‥ . D. Incel, V. Kumar, and B.Krishnamachari. Multichannel scheduling and spanning trees: throughput-delay tradeoff for fast data collection in sensor networks.
IEEE/ACM Trans. on Networking, 19(6):1731–1744, 2011.
[6] W. Guo, W. M. Healy, and M. Zhou. An experimental study of interference impacts on zigbee-based wireless communication inside buildings. In Proc. of IEEE International
Conference on Mechatronics and Automation (ICMA), 2010.
[7] J. Hayes, S. Beirne, K.-T. Lau, and D. Diamond. Evaluation of a low cost wireless chemical sensor network for environmental monitoring. In Proc. of IEEE Sensors Conference,2008.
[8] J. Hou, B. Chang, D.-K. Cho, and M. Gerla. Minimizing 802.11 interference on zigbee medical sensors. In Proc. of the International Conference on Body Area Networks.
[9] H. Huo, Y. Xu, H. Zhang, Y.-H. Chuang, and T.-C. Wu. Wireless-sensor-networks-based healthcare system: a survey on the view of communication paradigms. International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC), 8(3):135–154, 2011.
[10] IEEE Std 802.15.4e-2012 (amendment to IEEE Std 802.15.4-2011), 2012.
[11] O‥ . D. Incel, A. Ghosh, B. Krishnamachari, and K. Chintalapudi. Fast data collection in tree-based wireless sensor networks. IEEE Trans. Mobile Computing,11(1):86–99, 2012.
[12] O‥ . D. Incel and B. Krishnamachari. Enhancing the data collection rate of tree-based aggregation in wireless sensor networks. In Proc. of IEEE Sensor and Ad Hoc Communications and Networks Conference (SECON), 2008.
[13] S. Luo, X. Mao, Y. Sun, Y. Ji, and S. Tang. Delay minimum data collection in the low duty- cycle wireless sensor networks. In Proc. of IEEE Global Telecommunications
Conference (Globecom),2012.
[14] N.-H. Nguyen, Q.-T. Tran, J.-M. Leger, and T.-P. Vuong. A real-time control using wireless sensor network for intelligent energy management system in buildings. In
Proc. of IEEE Workshop on Environmental Energy and Structural Monitoring Systems(EESMS), 2010.
[15] M. R. Palattella, N. Accettura, M. Dohler, L. A. Grieco, and G. Boggia. Traffic aware scheduling algorithm for reliable low-power multi-hop IEEE 802.15.4e networks. In
Proc. of the IEEE Int’l Symposium on Personal, Indoor, and Mobile Radio Communications(PIMRC), 2012.
[16] M.-S. Pan, C.-H. Tsai, and Y.-C. Tseng. The orphan problem in ZigBee wireless networks.IEEE Trans. Mobile Computing, 8(11):1573–1584, 2009.
[17] M.-S. Pan and Y.-C. Tseng. Quick covergecast in ZigBee beacon-enabled tree-based wireless sensor networks. Computer Communications (ComCom), 31(5):999–1011,2008.
[18] H. O. Tan, I. Korpeoglu, and I. Stojmenovic. Computing localized power-efficient data aggregation trees for sensor networks. IEEE Trans. on Parallel and Distributed Systems, 22(3):489–500, 2011.
[19] D. B. West. Introduction to Graph Theory. Prentice Hall, 2001.
[20] Y. Wu, J. A. Stankovic, T. He, and S. Lin. Realistic and efficient multi-channel communications in wireless sensor networks. In Proc. of IEEE INFOCOM, 2008.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2014-08-11公開。
  • 同意授權瀏覽/列印電子全文服務,於2019-08-11起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信