noe

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：12

、訪客IP：3.137.161.222

姓名

楊宗穎(Zong-Ying Yang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

noe
(The Optimal k-Connectivity Deployment Pattern of Wireless Sensors)

相關論文

★ Dynamic Overlay Construction for Mobile Target Detection in Wireless Sensor Networks	★ 車輛導航的簡易繞路策略
★ 使用傳送端電壓改善定位	★ 利用車輛分類建構車載網路上的虛擬骨幹
★ Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?	★ 針對移動性目標物的有效率無線感測網路
★ 適用於無線隨意網路中以關節點為基礎的分散式拓樸控制方法	★ A Review of Existing Web Frameworks
★ 將感測網路切割成貪婪區塊的分散式演算法	★ 無線網路上Range-free的距離測量
★ Inferring Floor Plan from Trajectories	★ An Indoor Collaborative Pedestrian Dead Reckoning System
★ Dynamic Content Adjustment In Mobile Ad Hoc Networks	★ 以影像為基礎的定位系統
★ 大範圍無線感測網路下分散式資料壓縮收集演算法	★ 車用WiFi網路中的碰撞分析

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

在現今多樣式的無線網路應用中，為了要達到多重連接，節點佈建的方式扮演了很重要的角色。然而，現有的方法在尋找k連接數的時候，並沒有提供一個有系統性的方法來尋找出最佳化的佈建圖形。
在這篇論文中，我們假設節點都是相同的，並且以對稱的形式擺放。結果顯示當我們以這種方式擺放的時候，節點的范諾圖(Voronoi diagram)會是三個regular tessellations的其中一種。基於這點想法，我們設計了一套搜尋的演算法，叫做Pruning and Search(PS) 來尋最佳化的k連接佈建圖形。我們的演算法是第一個採用系統性的方法來尋找最佳化的k連接佈建圖形。雖然PS的時間複雜度是指數型，但最佳化的圖型可以預先尋找出來。除此之外，我們可以透過PS跟RES兩個演算法的結合，來找到k連接以及L覆蓋的佈建圖形。

摘要(英)

The strategy for sensor node deployment to achieve multiple connectivity plays a critical role in various applications of wireless sensor networks. However, the existing solutions to identify optimal k-connectivity deployment patterns are heuristic in the sense that they do not provide a systematic approach to identify the optimal pattern for a given k value. In this paper, we assume that nodes are homogeneous and deployed to the ground symmetrically. As a result, the Voronoi diagram of wireless nodes will be one of the known three regular tessellations. Based on this idea, we design an intuitive searching algorithm, called Pruning and Search (PS), to identify the optimal k-connectivity deployment pattern for an arbitrary k value. To the best of our knowledge, our PS algorithm is the first one to do this task in a systematical approach. While the time complexity of the algorithm is exponential, the optimal pattern can be pre-computed offline in advance. In addition, PS can be easily combined with the RES algorithm so that the optimal k-connectivity and l-coverage deployment pattern for a given set of k and l values can be found.

關鍵字(中)

★ 連接數
★ 無線網路

關鍵字(英)

★ connectivity
★ wireless

論文目次

1 Introduction 1
2 RelatedWork 3
2.1 Random Deployment . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 k-Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Preliminary 5
3.1 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Tessellations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 Pruning and PreComputing 7
4.1 The Problem of The Optimal k-Connectivity Deployment Pattern
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 The Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Pruning and Search . . . . . . . . . . . . . . . . . . . . . . . . 11
4.4 Case Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.4.1 The Square Pattern . . . . . . . . . . . . . . . . . . . . 12
4.4.2 The Hexagon Pattern . . . . . . . . . . . . . . . . . . . 15
4.4.3 The Triangle Pattern . . . . . . . . . . . . . . . . . . . 18
4.4.4 Correctness of Algorithms . . . . . . . . . . . . . . . . 21
iii
5 Performance 23
5.1 Algorithm analysis . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Simulation Configuration . . . . . . . . . . . . . . . . . . . . . 23
5.3 Simulation Results and Analysis . . . . . . . . . . . . . . . . . 25
5.3.1 Comparison between Square, Hexagon, and Triangle
Deployment Pattern . . . . . . . . . . . . . . . . . . . 25
5.3.2 Comparison between Regular Deployment Patterns and
Random Deployment . . . . . . . . . . . . . . . . . . . 28
6 Conclusions 30
Reference 31

參考文獻

References
[1] Xiaole Bai, Santosh Kumar, Dong Xuan, Ziqiu Yun, and Ten H. Lai. Deploying wireless sensors to achieve both coverage and connectivity. In Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc ’06, pages 131–142, New York, NY, USA, 2006. ACM.
[2] Paul Balister, B ́ela Bollobas, Amites Sarkar, and Santosh Kumar. Re- liable density estimates for coverage and connectivity in thin strips of finite length. In Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, MobiCom ’07, pages 75–86, New York, NY, USA, 2007. ACM.
[3] Jill Britton. Symmetry and Tesselations: Investination Patterns. Dale Seymour Publications, 1999.
[4] Ai Chen, Santosh Kumar, and Ten H. Lai. Designing localized algo- rithms for barrier coverage. In Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, Mobi- Com ’07, pages 63–74, New York, NY, USA, 2007. ACM.
[5] Richard Kershner. The number of circles covering a set. American Journal of Mathematics, 61(3):pp. 665–671, 1939.
31
[6] W.-S. Ku, K. Sakai, and M.-T. Sun. The Optimal k-Covering Tag De- ployment for RFID-based Localization. Journal of Network and Com- puter Applications, 34(3):914–924, 2011.
[7] Mo Li, Zhenjiang Li, and Athanasios V. Vasilakos. A Survey on Topology Control in Wireless Sensor Networks: Taxonomy, Comparative Study, and Open Issues. Proceedings of the IEEE, 101(12):2538–2557, 2013.
[8] Yunhao Liu, Lei Chen, Pei Jian, Qiuxia Chen, and Yiyang Zhao. Min- ing Frequent Trajectory Patterns for Activity Monitoring Using Radio Frequency Tag Arrays. pages 37–46, 2007.
[9] Yunhao Liu, Lei Chen, Jian Pei, Qiuxia Chen, and Yiyang Zhao. Min- ing frequent trajectory patterns for activity monitoring using radio fre- quency tag arrays. In Proceedings of the Fifth IEEE International Con- ference on Pervasive Computing and Communications, PERCOM ’07, pages 37–46, Washington, DC, USA, 2007. IEEE Computer Society.
[10] Rudolf Mathar et al. Optimum positioning of base stations for cellular radio networks. Wirel. Netw., 6(6), December.
[11] Christopher Mitchell, Vikram P. Munishwar, Shailendra Singh, Xi- aoshuang Wang, Kartik Gopalan, and Nael B. Abu-Ghazaleh. Testbed design and localization in mint-2: A miniaturized robotic platform for
32
wireless protocol development and emulation. In Proceedings of the First International Conference on COMmunication Systems And NET- works, COMSNETS’09, pages 268–277, Piscataway, NJ, USA, 2009. IEEE Press.
[12] Lionel M. Ni, Yunhao Liu, Yiu Cho Lau, and Abhishek P. Patil. Land- marc: Indoor location sensing using active rfid. pages 407–415, 2003.
[13] Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. Spatial Tessella- tions: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Inc., New York, NY, USA, 1992.
[14] Yuuki Ota, Toshihiro Hori, Taiki Onishi, Tomotaka Wada, Kouichi Mut- suura, and Hiromi Okada. An adaptive likelihood distribution algorithm for the localization of passive rfid tags. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E91-A(7):1666–1675, July 2008.
[15] H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. Communications, IEEE Transac- tions on, 32(3):246–257, Mar 1984.
[16] Jin Teng, Junda Zhu, Boying Zhang, Dong Xuan, and Yuan F. Zheng. E-V: Efficient Visual Surveillance with Electronic Footprints. pages 109–117, 2012.
33
[17] Sabu M. Thampi, Nithya Aniyan, and K. Chitharanjan. Hexagonal groups based key management using deployment knowledge in wireless sensor networks. In Proceedings of the International Conference on Ad- vances in Computing, Communications and Informatics, ICACCI ’12, pages 387–391, New York, NY, USA, 2012. ACM.
[18] Peng-Jun Wan and Chih-Wei Yi. Asymptotic critical transmission ra- dius and critical neighbor number for k-connectivity in wireless ad hoc networks. In Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc ’04, pages 1–8, New York, NY, USA, 2004. ACM.
[19] Peng-Jun Wan and Chih-Wei Yi. Coverage by randomly deployed wire- less sensor networks. IEEE/ACM Trans. Netw., 14(SI):2658–2669, June 2006.
[20] You-Chiun Wang, Chun-Chi Hu, and Yu-Chee Tseng. Efficient deploy- ment algorithms for ensuring coverage and connectivity of wireless sensor networks. In Wireless Internet, 2005. Proceedings. First International Conference on, pages 114–121, July 2005.
[21] Ziqiu Yun, Xiaole Bai, Dong Xuan, Ten H. Lai, and Weijia Jia. Optimal deployment patterns for full coverage and k- connectivity (k ≤
34
6) wireless sensor networks. IEEE/ACM Trans. Netw., 18(3):934–947, June 2010.
[22] H. Zhang and J. Hou. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks. Ad Hoc and Sensor Wireless Networks, 1(1- 2):89–124, 2005.

指導教授

孫敏德(Min-Te Sun)

審核日期

2015-7-31

推文