在具有空洞的無線感測網路中邊界點的選擇及其資訊繞徑之通訊協定設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：27

、訪客IP：3.144.212.145

姓名

謝坤穎(Kun-Ying Hsieh) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在具有空洞的無線感測網路中邊界點的選擇及其資訊繞徑之通訊協定設計
(Boundary Nodes Selection and Routing Protocol in Wireless Sensor Network with Holes)

相關論文

★ 無線行動隨建即連網路上之廣播與繞徑問題	★ 熱門電影的高效能廣播演算法
★ 無線行動隨建即連網路上之媒體存取問題	★ 使用功率調整來增加多節點封包無線網路
★ 在無線行動隨建即用網路下Geocast 之設計與實做經驗	★ 一個適用於熱門隨選視訊服務之快速排程廣播策略
★ 應用數位浮水印技術於影像之智慧財產權保護與認證	★ 在寬頻分碼多重擷取技術上分配及再分配多重正交可變展頻係數碼
★ 無線行動隨建即連網路上之廣播排程協定	★ 在無線行動隨建即連網路下支援即時多媒體傳送的媒介存取協定
★ 以樹狀結構為基礎的Scatternet建構協定	★ 在無線感應器網路中具有省電機制並且採用對角線路徑的方向性擴散
★ 隨意型無線網路上一個具有能量保存的GRID繞徑協定	★ 在無線感應器網路中具有省電機制的傳輸協定
★ 隨意型無線網路上一個具有能量保存以及平衡的繞徑協定	★ 環形藍芽網路：一個藍芽通訊網路的新拓樸及其繞徑協定

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

無線感測網路是一項新興的研究領域，其技術可廣泛應用在許多領域中，尤其是環境監測。然而，由於部署無線感測節點時的不平均，或有障礙物例如湖和山丘的存在，或感測節點的電量耗盡與被外力破壞等因素，進而造成無線感測網路中存在著空洞，而這些空洞會使許多繞徑通訊協定的效能降低。因此，如何找出這些空洞旁的邊界感測節點，並利用這些感測節點所獲得的邊界點資訊，讓封包繞徑時可事先閃避這些空洞，以及提升其他各種應用之效能，是一個相當重要的研究議題。為了解決這樣的問題，首先，我們提出一個邊界點選擇與目標偵測演算法，該演算法是在具有位置資訊的情況下，以分散式的方式，在短時間內選出位在空洞或監控區域外圍邊界上，具有座標極值之極值點，極值點將成為最初的邊界點，並用來找出剩餘之邊界點。模擬結果顯示，該演算法僅須少量的控制封包負擔，便可快速選出邊界點，且找出之邊界點個數與最佳值相當接近。然而，在某些情況下，感測節點無法取得位置資訊。因此，我們提出空洞偵測與邊界識別演算法，該演算法在無位置資訊的情況下，僅利用感測節點與鄰居感測節點間之連接狀態資訊，來挑選出邊界點。該演算法利用建立虛擬六角形地標節點，找出圍繞在空洞與感測區域旁的地標節點。再利用這些地標節點，找出正確的邊界點。模擬結果顯示，即使在低節點分支度的狀況下，該演算法正確找出邊界點的準確性仍可達到一定水準。最後，因這些邊界點的資訊，須傳送到Sink或特定的資料收集點，且資料封包須能夠避過空洞進行繞送。所以我們提出在無線感測網路中使用六角虛擬座標的繞徑協定，奠基於前一個演算法所建立的虛擬六角形地標節點，利用地標節點產生虛擬座標。傳送資料封包前，感測節點利用虛擬座標，建立從起始點到目的點的輔助繞徑路徑。資料封包將透過輔助繞徑的引導傳送，且即使多次從相同的起始點和傳送到目的點，其封包的繞徑路徑並不會固定。模擬結果顯示，該演算法能讓繞徑路徑均勻分散，而使傳送時所需承受的負擔，能均勻地分散到不同的感測節點，進而達到延長整體網路的壽命。

摘要(英)

Wireless Sensor Network (WSN) is an emerging research filed and its technology can be widely utilized in many applications especially in environmental surveillance. However, there are exist some holes within the WSNs caused by some factors such as non-uniform deployment of sensor nodes or the existence of physical obstacle such as mountains and lakes or some sensor nodes deplete their energy or be destroyed by outside forces. These holes will degrade the performance of several routing protocols. Hence, how to discover the boundary nodes surrounding the holes and then utilize the information of boundary nodes for routing protocols to avoid holes in advance and to improve the performance of various applications is a significant research issue. In order to solve this problem, firstly, we propose the Boundary Node Selection and Target Detection protocol where each node has location information. This protocol, in short time, prior to discover some extreme nodes having extreme value of coordinates as the initial boundary nodes surrounding the holes and monitoring region in distributed manner. Then the protocol finds out other remaining boundary nodes based on these extreme nodes. The simulation results show that this protocol can cost few control packets overhead to find out boundary nodes soon and the number of selected boundary nodes comparing the optimal value is approximate. However, in some situations, the sensor nodes cannot obtain location information. Therefore, we propose the Hole Detection and Boundary Recognition protocol. This protocol can discover the boundary nodes by only utilizing the connectivity information among nodes when nodes have no location information. The protocol creates the Virtual Hexagonal Landmarks and then selects the landmarks surrounding the holes and sensing field. Based on this selected landmarks, the protocol further finds out correct boundary nodes. The simulation results show that the protocol has better performance of the accuracy ratio of selecting correct boundary nodes even in low node degrees. Eventually, the information of these boundary nodes should be transmitted to the Sink or some specific data centric nodes and the data packets can avoid the holes when transmitting. Therefore, we propose Routing with Hexagonal Virtual Coordinations protocol. Based on the Virtual Hexagonal Landmarks of previous protocol, the virtual coordination is created. Before transmitting data packets, the protocol uses this virtual coordination to create an Auxiliary Routing Path to indicate the direction of the journey from the source to the destination. When transmitting the data packets, the routing paths assisted by the Auxiliary Routing Path are not always fixed even from same source to destination. The simulation results show that the protocol can find a load balancing routing path to the destination and then prolong the network lifetime.

關鍵字(中)

★ 邊界點
★ 分散式演算法
★ 目標偵測
★ 繞徑通訊協定
★ 虛擬座標
★ 無線感測網路

關鍵字(英)

★ wireless sensor network
★ Boundary node
★ distributed algorithms
★ virtual coordination
★ target detection
★ routing protocol

論文目次

Chapter 1 Introduction 1
Chapter 2 Reviews of Related Work 5
2.1. The Boundary Recognition for Wireless Sensor Networks 5
2.2. The Routing Protocol with Virtual Coordinate System 9
Chapter 3 Boundary Node Selection and Target Detection in Wireless Sensor Network 12
3.1 System Model 13
3.2 Boundary Node Selection Protocol 14
3.2.1 Sequential Boundary Node Selection (SBNS) algorithm 14
3.2.2 Distributed Boundary Nodes Selection (DBNS) algorithm 17
3.2.3 Centralized Boundary Node Selection (CBNS) algorithm 23
3.3 Target Detection Protocol 25
3.3.1 Coverage Overlapping Algorithm 25
3.3.2 Target Detection Algorithm 26
3.4 Performance Analysis 28
3.5 Summary 35
Chapter 4 Hole Detection and Boundary Recognition in Wireless Sensor Networks 36
4.1 Distributed Boundary Recognition Algorithm 37
4.1.1 Closure nodes selection 37
4.1.2 Coarse boundary cycles identification 41
4.1.3 Discover exact boundary nodes 45
4.1.4 Boundaries maintenance 51
4.2 Simulation and Performance Analysis 53
4.2.1 Effect of node degree on percentage of accurate ratio 55
4.2.2 Effect of number of holes on control packet overhead 56
4.2.3 Effect of number of holes on simulation time 58
4.3 Summery 59
Chapter 5 Routing with Hexagonal Virtual Coordinations in Wireless Sensor Networks 61
5.1 Routing Protocol with a Virtual Coordinate System 62
5.1.1 Overview of HVC 62
5.1.2 HVC Construction Protocol 64
5.1.3 Analysis of the Flooding Radius of Landmarks 69
5.2 simulations 77
5.2.1 Irregular Network Shapes 77
5.2.2 Load Balancing and Path Length 80
5.3 Summary 83
Chapter 6 Conclusions and Future Works 85
Bibliography 87

參考文獻

[1] N. Ahmed, S. S. Kanhere, and S. Jha, “The Holes Problems in Wireless Sensor Networks: A Survey,” Journal of ACM SIGMOBILE Mobile Computing and Communications Review, Vol. 9, Issue 2, pp. 4-18, Apr. 2005.
[2] J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko, and D. Rus, “Tracking a Moving Object with a Binary Sensor Network,” in Proceedings of the 1st ACM International Conference on Embedded Networked Sensor Systems (SENSYS 2003), pp. 150-161, Los Angeles, California, USA, Nov. 2003.
[3] K. Bi, K. Tu, N. Gu, W. Dong, and X. Liu, “Topological Hole Detection in Sensor Networks with Cooperative Neighbors,” in Proceedings of International Conference on Systems and Networks Communications (ICSNC 2006), pp. 31-31, Tahiti, French Polynesia, Oct. 2006.
[4] J. Bruck, J. Gao, and A. Jiang, “MAP: Medial Axis Based Geometric Routing in Sensor Networks,” in Proceedings of the 11th Annual International Conference on Mobile computing and networking (MOBICOM 2005), pp. 88-102, Cologne, Germany, Aug. 2005.
[5] Q. Cao and T. Abdelzaher, “Scalable Logical Coordinates Framework for Routing in Wireless Sensor Networks,” in Proceedings of the 25th IEEE International on Real-Time Systems Symposium (RTSS 2004), pp. 349-358, Lisbon, Portugal, Dec. 2004.
[6] A. Caruso, S. Chessa, S. De, and A. Urpi, “GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks,” in Proceedings of the 24th IEEE International Conference on Computer Communication (INFOCOM 2005), Vol. 1, pp. 150-160, Miami, Florida, USA, Mar. 2005.
[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. “Introduction to Algorithms,” Second Edition. MIT Press and McGraw-Hill, 2001.
[8] Q. Fang, J. Gao, and L. J. Guibas, “Locating and Bypassing Routing Holes in Sensor Networks,” Journal of Mobile Networks and Applications, Vol. 11, No. 2, pp. 187-200, Mar. 2006.
[9] Q. Fang, J. Gao, L. J. Guibas, V. de Silva, and L. Zhang, “Glider: Gradient Landmark-based Distributed Routing for Sensor Networks,” in Proceedings of the 24th IEEE International Conference on Computer Communication (INFOCOM 2005), Vol. 1, pp. 339-350, Miami, Florida, USA, Mar. 2005.
[10] S. P. Fekete, M. Kaufmann, A. Kröller, and N. Lehmann, “A New Approach for Boundary Recognition in Geometric Sensor Networks,” in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), pp. 82-85, Ontario, Canada, Aug. 2005.
[11] S. P. Fekete, A. Kröller, D. Pfisterer, S. Fischer, and C. Buschmann, “Neighborhood-based Topology Recognition in Sensor Networks,” in Proceedings of 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2004), Springer LNCS, Vol. 3121, pp. 123-136, Turku, Finland, July 2004.
[12] S. Funke, “Topological Hole Detection in Wireless Sensor Networks and its Applications,” in Proceedings of the 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC 2005), pp. 44–53, Cologne, Germany, Sept. 2005.
[13] S. Funke and C. Klein, “Hole Detection or: “How much Geometry hides in Connectivity?”,” in Proceedings of the 22nd ACM Annual Symposium on Computational Geometry (SCG 2006), pp. 377-385, Sedona, Arizona, USA, Jun. 2006.
[14] S. Funke and N. Milosavljević, “Guaranteed-delivery Geographic Routing Under Uncertain Node Locations,” in Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 1244-1252, Anchorage, Alaska, USA, May 2007.
[15] R. Ghrist and A. Muhammad, “Coverage and Hole-detection in Sensor Networks via Homology,” in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN 2005), pp. 254-260, Los Angeles, California, USA, April 2005.
[16] R. Gupta and S. R. Das, “Tracking Moving Targets in a Smart Sensor Network,” in Proceedings of the 58th IEEE Vehicular Technology Conference, Vol. 5, pp. 3035-3039, Orlando, Florida, USA, Oct. 2003.
[17] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-Free Localization Schemes in Large-Scale Sensor Networks,” in Proceedings of the International Conference on Mobile Computing and Networking (MOBICOM 2003), pp. 81-95, San Diego, California, USA, Sept. 2003.
[18] T. He, S. Krishnamurthy, L. Luo, T. Yan, L. Gu, R. Stoleru, G. Zhou, Q. Cao, P. Vicaire, J. A. Stankovic, T. F. Abdelzaher, J. Hui and B. Krogh, “VigilNet: An Integrated Sensor Network System for Energy-efficient Surveillance,” Journal of ACM Transaction on Sensor Networks, Vol. 2, Issue 1, pp. 1-38, Feb. 2006.
[19] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, “Global Positioning System: Theory and Practice,” Fourth Edition, Springer-Verlag, 1997.
[20] X. Ji and H. Zha, “Sensor Positioning in Wireless Ad-hoc Sensor Networks Using Multidimensional Scaling,” in Proceedings of the 23rd IEEE International Conference on Computer Communication (INFOCOM 2004), Vol. 4, pp. 2652-2661, Hong Kong, China, Mar. 2004.
[21] B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing,” in Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM 2000), pp. 243-254, Boston, Massachusetts, USA, Aug. 2000.
[22] W. Kim, K. Mechitov, J. Y. Choi, and S. Ham, “On Target Tracking with Binary Proximity Sensors,” in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN 2005), pp. 301-308, Los Angeles, California, USA, Apr. 2005.
[23] A. KrÖller, S. P. Fekete, D. Pfisterer, and S. Fischer, “Deterministic Boundary Recognition and Topology Extraction for Large Sensor Networks,” in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 1000-1009, Miami, Florida, USA, Jan. 2006.
[24] H. T. Kung and D. Vlah, “Efficient Location Tracking Using Sensor Networks,” in Proceedings of the Wireless Communications and Networking Conference (WCNC 2003), Vol. 3, pp. 1954-1961, New Orleans, Louisiana, USA, Mar. 2003.
[25] W. H. Liao, Y. C. Tseng, K. L. Lo, and J. P. Sheu, “Geo GRID: A Geocasting Protocol for Mobile Ad Hoc Networks Based on GRID,” Journal of Internet Technology, Vol. 1, No. 2, pp. 23-32, Dec. 2000.
[26] W. H. Liao, Y. C. Tseng, and J. P. Sheu, “GRID: A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks,” Journal of Telecommunication Systems, Vol. 18, No. 1, pp. 37-60, Sept. 2001.
[27] C. Y. Lin, W. C. Peng and Y. C. Tseng, “Efficient in-Network Moving Object Tracking in Wireless Sensor Networks,” Journal of IEEE Transaction on Mobile Computing, Vol. 5, Issue 8, pp.1044-1056, Aug. 2006.
[28] A. Mainwaring, R. Szewczyk, D. Culler, and J. Anderson, ”Wireless Sensor Networks for Habitat Monitoring,” in Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA 2002), pp. 88-97, Atlanta, Georgia, USA, Sept. 2002.
[29] K. Mechitov, S. Sundresh, Y. Kwon, and G.. Agha, “Cooperative Tracking with Binary-Detection Sensor Networks,” in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SENSYS 2003), pp. 332-333, Los Angeles, California, USA, Nov. 2003.
[30] T. Moscibroda, R. O’Dell, M. Wattenhofer, and R. Wattenhofer, “Virtual Coordiantes for Ad Hoc and Sensor Networks,” in Proceedings of the 2ed ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC 2004), pp. 8-16, Philadelphia, Pennsylvania, USA, Oct. 2004.
[31] J. C. Navas and T. Imielinski, “Geocast-Geographic Addressing and Routing,” in Proceedings of the 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM 1997), pp. 66-76, Budapest, Hungary, Sept. 1997.
[32] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) using AOA,” in Proceedings of the 22nd IEEE International Conference on Computer Communication (INFOCOM 2003), pp. 1734-1743, Mar. 2003.
[33] A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, “Geographic Routing Without Location Information,” in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MOBICOM 2003), pp. 96-108, San Diego, California., USA, Sept. 2003.
[34] P. K. Sahoo, K.–Y. Hsieh, and J.-P. Sheu, “Boundary Node Selection and Target Detection in Wireless Sensor Network,” in Proceedings of the IFIP International Conference on Wireless and Optical Communications Networks (WOCN 2007), Singapore, Jul. 2007.
[35] O. Saukh, R. Sauter, M. Gauger, P. J. MarrÓn, and K. Rothermel, “On Boundary Recognition without Location Information in Wireless Sensor Networks,” in Proceedings of the 7th International Symposium on Information Processing in Sensor Networks (IPSN 2008), pp.207-218, St. Louis , Missouri , USA , April 2008.
[36] J.-P. Sheu, Y.-C. Chang, and G.-H. Song, “Logical Coordinate Assignment for Geographic Routing in Wireless Sensor Networks,” International Journal of Pervasive Computing and Communication, pp. 274- 288, Vol. 3, No. 3, 2007.
[37] J.-P. Sheu, C.-S. Hsu, and J.-M. Li, “A Distributed Location Estimating Algorithm for Wireless Sensor Networks,” in Proceedings of the International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC 2006), Vol. 01, pp. 218-225, Taichung, Taiwan, Jun. 2006.
[38] K.-F. Su, C.-H. Ou, and H.-C. Jiau, "Localization with Mobile Anchor Points in Wireless Sensor Networks," Journal of IEEE Transaction on Vehicular Technology, Vol. 54, No. 3, pp. 1187-1197, May 2005.
[39] S. P. M. Tran and T.-A. Yang, “A Novel Target Movement Model and Energy Efficient Target Tracking in Sensor Networks,” in Proceedings of the 37th SIGCSE Technical Symposium on Computer Science Education, Vol. 38, Issue 1, pp. 97-101, Houston, Texas, USA, Mar. 2006.
[40] Y. Wang, J. Gao, and J. S. B. Mitchell, “Boundary Recognition in Sensor Networks by Topological Methods,” in Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MOBICOM 2006), pp. 122-133, Los Angeles, California, USA, Sept. 2006.
[41] Y. Xu and W.-C. Lee, “On Localized Prediction for Power Efficient Object Tracking in Sensor Networks,” in Proceedings of the International Workshop on Mobile Distributed Computing (MDC 2003), pp. 434-439, Providence, Rhode Island, May 2003.
[42] Y. Xu, J. Winter, and W.-C. Lee, “Prediction Based Strategies for Energy Saving in Object Tracking Sensor Networks,” in Proceedings of the IEEE International Conference on Mobile Data Management (MDM 2004), pp. 346-357, Berkeley, California, USA, Jan. 2004.
[43] Y. Xu, J. Winter, and W.-C. Lee, “Dual Prediction-based Reporting Mechanism for Object Tracking Sensor Networks,” in Proceedings of the 1st Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MOBIQUITOUS 2004), pp. 154-163, Boston, Massachusetts, USA, Aug. 2004.
[44] H. Yang and B. Sikdar, “A protocol for Tracking Mobile Targets Using Sensor Networks,” in Proceedings of the 1st IEEE Workshop on Sensor Network Protocols and Applications (SNPA 2003), pp. 71-81, Anchorage, Alaska, USA, May 2003.
[45] W. L. Yeow, C. K. Tham, W. C. Wong, “Evaluations of Target Tracking in Wireless Sensor Networks,” in Proceedings of the IEEE 61st Vehicular Technology Conference (VTC 2006), Vol. 5, pp. 2825-2829, Stockholm, Sweden, May. 2005.
[46] W. Zhang and G. Cao, “DCTC: Dynamic Convoy Tree-Based Collaboration for Target Tracking in Sensor Networks,” Journal of IEEE Transaction on Wireless Communications, Vol. 3, pp. 1689-1701, Sept. 2004.
[47] W. Zhang and G. Cao, “Optimizing Tree Reconfiguration for Mobile Target Tracking in Sensor Networks,” in Proceedings of the 23rd IEEE International Conference on Computer Communication (INFOCOM 2004), Vol. 4, pp. 2434-2445, Hong Kong, China, Mar. 2004.
[48] The Network Simulator (NS), URL.

指導教授

許健平(Jang-Ping Sheu)

審核日期

2009-7-9

推文