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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1307200504342400
中文論文名稱 在無線感測網路上以幾何學為基礎之分散式工作排程機制
英文論文名稱 Geo-BASS: Distributed Geometric-Based Activity Scheduling Schemes for Wireless Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 93
學期 2
出版年 94
研究生中文姓名 江俊緯
研究生英文姓名 Chun-Wei Chiang
學號 692190589
學位類別 碩士
語文別 中文
口試日期 2005-06-24
論文頁數 54頁
口試委員 指導教授-黃心嘉
指導教授-石貴平
委員-簡榮宏
委員-曾煜棋
委員-許健平
委員-黃心嘉
委員-石貴平
中文關鍵字 無線感測網路  計算幾何學  Voronoi Diagram  Delaunay Triangulation  工作排程 
英文關鍵字 Wireless Sensor Networks  Computational Geometry  Voronoi Diagram  Delaunay Triangulation 
學科別分類 學科別應用科學資訊工程
中文摘要 在Wireless Sensor Networks (WSNs)中,要如何安排Sensor Nodes成為Active模式並進行感測任務,而有效地延長使WSN的工作時間,是一個非常重要的議題。本篇論文提出一個以幾何學為基礎之分散式工作排程機制(Geometric-base activity scheduling scheme, Geo-BASS)。Geo-BASS為一個分散式排程方法,透過計算幾何學中Voronoi Diagram以及Delaunay Triangulation理論基礎的設計,Sensor Nodes可以自我決定何時可以進入睡眠狀態,或是為了維持Coverage的需求而進入Active狀態。Geo-BASS在某些時間中,可以找到數量盡量少的Sensors Nodes來負責感測任務。然而,我們可以知道尋求Sensor Nodes的最佳數量是一個組合最佳化(Combinatorial Optimization)的問題,而此問題是一個NP-Complete的問題。因此,我們提出一些heuristic methods,來解決這個問題。實驗模擬結果顯示,Geo-BASS能有效地規畫Sensor Nodes何時在Active以及Sleep模式之間做切換,而當Sensor Nodes分布不平均時,更能顯示出Geo-BASS的效果,有效地延長網路的存活時間。
英文摘要 The activity scheduling of sensors to alternatively wake up for sensing obligation such that the network lifetime can be efficiently prolonged is a very important issue in wireless sensor networks (WSNs). The paper proposes three geometric-based activity scheduling schemes, named Geo-BASS, for WSNs, under the requirement of complete coverage of a sensing field. Geo-BASS is a distributed scheme. By means of computational geometry, such as Voronoi diagram and Delaunay triangulation, the sensor can self-determine when to sleep or wake up while preserving the sensing coverage. Geo-BASS can find as less number of sensors as possible to be in charge of the sensing task for some time instance. Since the optimization is a combinatorial optimization problem, which has been shown to be an NP-complete problem. Therefore, some heuristic methods are proposed. In addition, Geo-BASS can also be extended to deal with the activity scheduling problems under different requirements, such as target coverage or patrol coverage requirements. Simulation results show that Geo-BASS can efficiently schedule the sensor when to switch between active and sleeping modes, especially when the sensors are deployed unbalanced. Furthermore, the network lifetime can be protracted significantly in comparison with the state-of-the-art schemes.
論文目次 目錄
第一章、 簡 介 1
第二章、 預備知識 7
第一節、 問題描述 7
第二節、 計算幾何 8
第三節、 基本概念 11
第三章、 COMPANION SET (CP)的尋找 15
第一節、 INITIATOR的選擇 15
第二節、 COMPANION NEIGHBORS的尋找 17
第三節、 擴散至整個網路 24
第四章、 COVER SET (CV) 尋找 31
第五章、 ACTIVITY SCHEDULING SCHEMES 38
第六章、 實驗結果 44
第七章、 結 論 50
參考文獻 52

圖目錄
圖1.Voronoi diagram以及Delaunay Triangulation 10
圖2.Sensor Network運作的時間架構 11
圖3.Companion Set示意圖 13
圖4.Cover Set示意圖 14
圖5.尋找Initiator的示意圖 17
圖6.An example that VC(sj) is not within C(sj) 19
圖7.Companion Neighbors之尋找 21
圖8.s1的Companion Neighbors之間Overlap狀況 22
圖9.Sensor Nodes之間的感測區域呈60O交集 23
圖10.以 為基準距離 24
圖11.Companion Neighbors選擇衝突 25
圖12.由Initiator擴散Rule1 & Rule2 28
圖13.其他擴散Rule3 & Rule4 30
圖14.Selection Zone 1.的証明 35
圖15.Cover Set的找尋 37
圖16.Companion Set成員依據剩餘電量安排Active時間長度 39
圖17.s2記錄一步通訊範圍內,已被指定時間的Sensor Nodes 40
圖18.s2尋找Cover Sets 42
圖19.s2安排每一組Companion Set以及Cover Sets的運作時間 42
圖20.Cover Set基準時間的計算 43
圖21.Active Sensor Nodes個數與時間的比較(1800個Sensor Nodes) 46
圖22.Active Sensor Nodes個數與時間的比較(2700個Sensor Nodes) 46
圖23.Active Sensor Nodes個數與時間的比較(3600個Sensor Nodes) 47
圖24.Average remaining energy(%) (1800個Sensor Nodes) 48
圖25.Average remaining energy(%) (3600個Sensor Nodes) 48
圖26.Average remaining energy(%) (3600個Sensor Nodes) 49
參考文獻 [1]Q. Li, M. D. Rosa, and D. Rus, “Distributed algorithms for guiding navigation across a sensor network,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), Sept. 2003, pp. 313–325.

[2]Q. Huang, C. Lu, and G.-C. Roman, “Reliable mobicast via face-aware routing,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2004.

[3]M. Ding, D. Chen, A. Thaeler, and X. Cheng, “Fault-tolerant target detection in sensor networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2005.

[4]S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Worst and best-case coverage in sensor networks,” IEEE Transactions on Mobile Computing, vol. 4, no. 1, pp. 84–92, Jan./Feb. 2005.

[5]Q. Cao, T. Abdelzaher, T. He, and J. Stankovic, “Towards optimal sleep scheduling in sensor networks for rare-event detection,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2005.

[6]C. F. Hsin and M. Liu, “Network coverage using low duty-cycled sensors: Random & coordinated sleep algorithms,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2004, pp. 433–442.

[7]M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-efficient target coverage in wireless sensor networks,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2005.2

[8]M. Cardei and D.-Z. Du, “Improving wireless sensor network lifetime through power aware organization,” ACM Wireless Networks, vol. 11, no. 3, pp. 333–340, May 2005.

[9]C. Gui and P. Mohapatra, “Virtual patrol: A new power conservation design for suveillance using sensor networks,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2005.

[10]F. Ye, G. Zhong, J. Cheng, S.Lu and L. Zhong, “PEAS:A Robust Energy Conserving Protocol for Long-lived Sensor Networks,” in Proceeding of the 23rd International Conference on Distributed Computing Systems (ICDCS), 2003, pp. 28-37.

[11]D. Tian and N. D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” in Proceedings of the ACM 1st International Workshop on Wireless Sensor Networks and Applications (WSNA), 2002, pp. 32-41.

[12]J. Jiang, and W. Dou, “A Coverage-Preserving Node Scheduling Algorithm for Self-organized Wireless Sensor Networks,” in Proceedings of the Grid and Cooperative Computing Workshops (GCC), 2004, pp. 587-596.

[13]B. Carbunar, A. Grama, J. Vitek, and O. Carbunar, “Coverage Preserving Redundancy Elimination in Sensor Networks”, in Proceedings of the 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), 2004, pp. 377-386.

[14]X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless and C. Gill, "Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks," in Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys), 2003, pp. 28–39.

[15]H. Zhang and J. C. Hou, “Maintaining sensing coverage and connectivity in large sensor networks,” in NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2004.

[16]H. Gupta, S. R. Das and Q. Gu, “Connected Sensor Cover : Self-Organization of sensor networks for efficient query execution,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2003, pp. 189–200.

[17]T. Yan, T. He, and J. A. Stankovic, “Differentiated Surveillance for Sensor Networks,” in ACM International Conference on Embedded Networked Sensor Systems (SenSys), 2003, pp. 51-62

[18]C.-F. Huang, L.-C. Lo, Y.-C. Tseng, and W.-T. Chen, “Decentralized Energy - Conserving and Coverage-Preserving Protocols for Wireless Sensor Networks”, in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), 2005.

[19]D. Tian and N. D. Georganas, “Location and calculation-free nodescheduling schemes in large wireless sensor networks,” Ad Hoc Networks, vol. 2, no. 1, pp. 65–85, Jan. 2004.

[20]T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), 2003, pp. 81–95.

[21]D. Niculescu and B. Nath, “Ad hoc positioning system (APS) using AoA,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2003, pp. 1734–1743.

[22]C.-F. Huang and Y.-C. Tseng, “The coverage problem in a wireless sensor network,” in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2003, pp. 115 – 121.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-07-14公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-07-14起公開。


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