在無線感測網路中使用六角虛擬座標的繞徑協定

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：83

、訪客IP：18.191.103.46

姓名

丁銘龍(Ding-Lung Ding) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在無線感測網路中使用六角虛擬座標的繞徑協定
(Routing with Hexagonal Virtual Coordinate in Wireless Sensor Networks)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

雖然類似GPSR的地理繞徑(Geographic routing)在無線感測以及隨意網路中效能很好，但是在網路中的感測節點必須要知道他們自己的地理位置。另外，若網路中存在有洞時，使用GPSR橫越洞的繞徑會導致在洞邊界的感測節點負載過重。在本篇論文中，我們提出一個分散式的協定僅以感測節點間的跳步計數(hop count)來建立一個虛擬座標系統稱之HVC。每個感測節點最多紀錄跳步計數到七個最近的地標來當他的虛擬座標，而這些地標座落在一個六角形的頂點跟它的中心點。在HVC建立之後，在網路中的感測節點可以透過HVC航海圖來得知地標間的相對座標。然後起始點可以找到一條輔助的繞徑路徑來指引從起始點到目的地旅程之方向。最後，我們可以透過輔助繞徑節點的支援找到一條繞徑路徑到目的地去。我們的模擬結果呈現這個由我們的協定產生的虛擬座標系統可以有效率地支援地理繞徑，而且即時在這個網路中存在有一些洞在裡面，這些透過我們的協定找出來的地標仍然可以均勻地座落在網路中的每個地方。另外，我們的協定可以適用在各式各樣的網路形狀而且不論這條路徑是否會橫越洞他仍然可以找到一條均勻負載的繞徑路徑到目的地。

摘要(英)

Although geographic routing like GPSR is efficient to ad hoc and wireless sensor networks, it requires that nodes be aware of their physical positions. In addition, if there are holes in the network, routing across holes in GPSR will lead to a lot of overloaded nodes in the boundaries of holes. In this thesis, we proposed a distributed protocol to construct a virtual coordinate system named HVC merely based on hop counts among nodes. Each node records hop counts to seven nearest landmarks at most to be its virtual coordinate, and the landmarks are located in the vertices of a hexagon and its center. After the HVC is constructed, the nodes in the network are aware of the relative coordinates among the landmarks through the HVC chart. Then source node can find an Auxiliary Routing Path (ARP) to indicate the direction in the journey from source to destination. Finally, we can find a routing path to destination with the ARP support. Simulation results show that our protocol can support geographic routing efficiently, and the landmarks found by our protocol are located everywhere in the network uniformly even if there exist some holes within it. In addition, our protocol is resilient to various network shapes and it can find a load balancing routing path to destination even this path will across holes in the network.

關鍵字(中)

★ 無線感測網路
★ 虛擬座標系統
★ 地理繞徑

關鍵字(英)

★ wireless sensor networks
★ virtual coordinate system
★ Geographic routing

論文目次

Chapter 1 Introduction 1
Chapter 2 Previous Work 4
Chapter 3 Routing with Hexagonal Virtual Coordinate 7
3.1 Overview of HVC 7
3.2 HVC Construction Protocol 10
3.3 Analysis the Flooding Radius of Landmarks 18
3.4 HVC Routing Protocol 23
Chapter 4 Simulations 27
4.1 Irregular Network Shapes 27
4.2 Load Balancing and Path Length 30
Chapter 5 Conclusions 33
References 34

參考文獻

[1] B. Karp and H. Kung, “Greedy Perimeter Stateless Routing,” in Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), pp. 243-254, 2000.
[2] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, “Global Positioning System: Theory and Practice,” 4th Edited, Springer Verlag, 1997.
[3] A. Savvides, C. -C. Han and M. B. Strivastave, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” in Proceedings of the 7th annual international conference on Mobile computing and networking (MOBICOM), pp. 166-179, July, 2001.
[4] N. B. Priyantha, A. K.L. Miu, H. Balakrishnan, and S. Teller, “The Cricket Compass for Context-aware Mobile Applications,” in Proceedings of the 7th annual international conference on Mobile computing and networking (MOBICOM), pp. 1-14, July, 2001.
[5] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) using AOA,” in Proceedings of IEEE International Conference on Computer Communication (INFOCOM), pp. 1734-1743, March, 2003.
[6] D. Niculescu and B. Nath, “Error Characteristics of Ad Hoc Positioning Systems (APS),” in Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, pp. 20-30, 2004.
[7] P. Bahl and V.N. Padmanabhan, “RADAR: An In-building RF-based User Location and Tracking System,” in Proceedings of IEEE International Conference on Computer Communication (INFOCOM), pp. 775-784, March, 2000.
[8] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS),” in Proceedings of IEEE Global Communications (GLOBECOM), Vol. 5, pp. 2926-2931, November, 2001.
[9] D. Son, A. Helmy, and B. Krishnamachari, “The Effect of Mobility-Induced Location Errors on Geographic Routing in Mobile Ad Hoc and Sensor Networks: Analysis and Improvement Using Mobility Prediction, ” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Vol. 1, pp. 189-194, March, 2004
[10] K. Seada, A. Helmy, and R. Govindan, “On The Effect of Localization Errors on Geographic Face Routing in Sensor Networks,” in Proceedings of the third international symposium on Information processing in sensor networks (IPSN), pp. 71-80, 2004.
[11] T. He, C. Huang, B. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-Free Location Schemes in Large Sensor Networks,” in Proceedings of the 9th annual international conference on Mobile Computing and Networking, pp. 81-95, September, 2003.
[12] A. Nasipuri and K. Li, “A Directionality Based Location Discovery Scheme for Wireless Sensor Networks,” in First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), pp. 105-111, September, 2002.
[13] N. B. Priyantha, A. Chakraborty, and H. Padmanabhan, “The Cricket Location Support System,” in Proceeding of the 6th annual international conference on Mobile computing and networking (MOBICOM), pp. 32-43, August, 2000
[14] Y. Shang, W. Rum, Y. Zhang, and M. Fromherz, “Localization from Mere Connectivity,” in Proceedings of the 4th international symposium on Mobile ad hoc networking and computing (MOBICOM), pp. 201-212, Annapolis, MD, USA, June, 2003.
[15] A. Caruso, S. Chessa, S. De, and A. Urpi, “GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks,” in Proceedings of IEEE International Conference on Computer Communication (INFOCOM), Vol. 1, pp. 150-160, Miami, March, 2005.
[16] Q. Cao, and T. Abdelzaher, “Scalable Logical Coordinates Framework for Routing in Wireless Sensor Networks,” in Proceedings of 25th IEEE International on Real-Time Systems Symposium (RTSS), pp. 349 - 358, Lisbon, Portugal, December, 2004.
[17] Rao, 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), pp. 96-108, San Diego, CA, USA, 2003.
[18] J.-P. Sheu, Y.-C. Chang, and G.-H. Song, “Logical Coordinate Assignment for Geographic Routing in Wireless Sensor Networks,” Journal of Pervasive Computing and Communications (to appear).
[19] T. Moscibroda, R. O’Dell, M. Wattenhofer, and R. Attenhofer, “Virtual Coordiantes for Ad Hoc and Sensor Networks,” in Proceedings of the 2004 joint workshop on Foundations of mobile computing (DLALM-POMC), pp. 8-16, Philadelphia, Pennsylvania, USA, October, 2004.
[20] S. Funke, “Topological Hole Detection in Wireless Sensor Networks and its Application,” in Proceedings of the 2005 joint workshop on Foundations of mobile computing (DLALM-POMC), pp. 44-53, New York, NY, USA, 2005.
[21] 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 IEEE International Conference on Computer Communication (INFOCOM), pp. 339-350, March, 2005.
[22] 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), pp. 88-102, August, 2005.
[23] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. “Introduction to Algorithms,” Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 24.3: Dijkstra's algorithm, pp.595–601.

指導教授

許健平(Jang-Ping Sheu)

審核日期

2006-7-23

推文