(3.234.221.162) 您好!臺灣時間:2021/04/14 04:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:饒昕芳
研究生(外文):Hsin-Fang Jao
論文名稱(外文):The Optimal k-Connectivity Deployment Pattern in 3-D Wireless Sensor Networks
指導教授:孫敏德
指導教授(外文):Min-Te Sun
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:40
中文關鍵詞:無線感測網路最佳化節點佈置連接性
外文關鍵詞:Wireless sensor networkOptimal deployment patternConnectivity
相關次數:
  • 被引用被引用:0
  • 點閱點閱:224
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
在無線網感測網路研究中,佈置感測節點是一重要的議題。因為選用一個最佳化感測節點佈建模式,使得需要佈建的感測節點數量最少,降低無線網路應用的成本。而現有的研究中,僅提出在部分k 值(k<=25)的最佳化k 連接性(connectivity)三維感測網路的節點佈建模式,卻並未提出一個系統性的方法來決定在任意正整數k 時最佳化k 連接性(connectivity)的佈建圖形。
本篇研究中,假設感測節點都是均質,並以對稱之方式擺放在一個很大的空間裡。因此,由每個感測節點所組成的范諾圖(Voronoi diagram)會是立方體及菱形十二面體,這兩種對稱的空間填充凸多面體(space-filling convex polyhedra)其中一種。基於這個假設,本研究設計一套搜尋的演算法Bound and Search (BS), 計算在滿足k 連接性(connectivity)的無線感測網路下,感測節點所需的傳輸半徑。藉由比較立方體及菱形十二面體這兩種感測節點佈建模式之下,達到k 連接性(connectivity)時,感測節點所需的傳輸半徑及感測節點密度這兩個數據,本研究的演算法可以找到一個在三維無線感測網路下,最佳化的k 連接佈建圖形。此外,實驗結果顯示,除了在比較小範圍的k 值( 15 <= k <= 25 ),採用菱形十二面體的節點佈建模式,所需個節點密度較正立方體的節點佈建模式小。
To reduce the operational cost of wireless sensor networks, nding the optimal deployment pattern to achieve a given connectivity requirement with the minimum
number of sensor nodes is important. Although the optimal k-connectivity deployment pattern (k<=25) for 3-D wireless sensor networks have been studied, there is
yet to have a general framework in identifying the optimal k-connectivity deployment pattern for an arbitrary k value. In this thesis, we assume that sensor nodes are homogeneous and deployed over an very large area symmetrically. As a result, the Voronoi diagram of sensor nodes will be one of the symmetric space-lling convex polyhedra, i.e., cube and rhombic dodecahedron. An algorithm, called Bound and Search (BS), is proposed to compute the transmission radius required for sensor nodes to achieve k connectivity. By comparing the transmission radius and node density resulted from the cube and rhombic dodecahedron patterns, our algorithm is able to discovers the optimal k-connectivity deployment pattern in 3-D wireless sensor networks. Moreover, our results indicate that, other than a small range of k (i.e., 15 <= k <= 25 ), the rhombic dodecahedron pattern requires a smaller node density to achieve the same k-connectivity requirement when compared with the cube pattern.
1 Introduction 1
2 RelatedWork 3
2.1 Coverage and Connectivity of 2D wireless sensor networks . . . . . . . . . 3
2.2 Coverage and Connectivity of 3D wireless sensor networks . . . . . . . . . 4
3 Preliminary 5
3.1 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Polyhedron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Tessellations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Bound and Search 9
4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 The basic idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4 Bound and Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.5 Case Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.5.1 The Cube Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.5.2 The Rhombic Dodecahedron Pattern . . . . . . . . . . . . . . . . . 18
5 Performance 24
5.1 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2 Comparison between Cube and Rhombic Dodecahedron Deployment Patterns 25
6 Conclusions 28
[1] SM Alam and Zygmunt J Haas. Coverage and connectivity in three-dimensional
networks. In Proceedings of the 12th annual international conference on Mobile com-
puting and networking, pages 346{357. ACM, 2006.
[2] Habib M Ammari and Sajal Das. A study of k-coverage and measures of connectivity
in 3d wireless sensor networks. IEEE Transactions on Computers, 59(2):243{257,
2010.
[3] 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, pages
131{142. ACM, 2006.
[4] Bela Bollobas. The art of mathematics: Coffee time in Memphis. Cambridge Uni-
versity Press, 2006.
[5] Brent N Clark, Charles J Colbourn, and David S Johnson. Unit disk graphs. Discrete
mathematics, 86(1-3):165{177, 1990.
[6] A.S.C. Engineers. Glossary of the Mapping Sciences. American Society of Civil
Engineers, 1994.
[7] A. H. Esfahanian. Generalized measures of fault tolerance with application to n -cube
networks. IEEE Transactions on Computers, 38(11):1586{1591, Nov 1989.
[8] Li Guang-Hui, Zhao Jun, and Wang Zhi. Research on forest re detection based
on wireless sensor network. In 2006 6th World Congress on Intelligent Control and
Automation, volume 1, pages 275{279, 2006.
[9] Frank Harary. Conditional connectivity. Networks, 13(3):347{357, 1983.
[10] Paul Heckbert. Graphics Gems IV (IBM Version). Elsevier, 1994.
[11] C. Istin, D. Pescaru, and H. Ciocarlie. Performance improvements of video wsn
surveillance in case of traffic congestions. In Computational Cybernetics and Technical
Informatics (ICCC-CONTI), 2010 International Joint Conference on, pages 659{663,
May 2010.
[12] Richard Kershner. The number of circles covering a set. American Journal of Math-
ematics, 61(3):pp. 665{671, 1939.
[13] Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. Spatial Tessellations: Concepts
and Applications of Voronoi Diagrams. 1992.
[14] K. Sakai, M. T. Sun, W. S. Ku, T. H. Lai, and A. V. Vasilakos. A framework for the
optimal k -coverage deployment patterns of wireless sensors. IEEE Sensors Journal,
15(12):7273{7283, Dec 2015.
[15] Hugo Steinhaus. Mathematical snapshots. Courier Corporation, 2012.
[16] Hideaki Takagi and Leonard Kleinrock. Optimal transmission ranges for ran-
domly distributed packet radio terminals. IEEE Transactions on communications,
32(3):246{257, 1984.
[17] Peng-Jun Wan and Chih-Wei Yi. Coverage by randomly deployed wireless sensor
networks. IEEE/ACM Trans. Netw., 14:2658{2669, June 2006.
[18] Xingwei Wang, Jinrong Wu, and Lei Guo. A k-coverage algorithm in three dimen-
sional wireless sensor networks. In Broadband Network and Multimedia Technology (IC-BNMT), 2010 3rd IEEE International Conference on, pages 1089{1093. IEEE,
2010.
[19] Z. Xiao, M. Huang, J. Shi, J. Yang, and J. Peng. Full connectivity and proba-
bilistic coverage in random deployed 3d wsns. In Wireless Communications Signal
Processing, 2009. WCSP 2009. International Conference on, pages 1{4, Nov 2009.
[20] Zong-Ying Yang. The optimal k-connectivity deployment pattern of wireless sensors,
2015.
[21] Dunfan Ye, Daoli Gong, and Wei Wang. Application of wireless sensor networks
in environmental monitoring. In Power Electronics and Intelligent Transportation
System (PEITS), 2009 2nd International Conference on, volume 1, pages 205{208,
Dec 2009.
[22] Ziqiu Yun, Xiaole Bai, Dong Xuan, Ten H. Lai, and Weijia Jia. Optimal deploy-
ment patterns for full coverage and k- connectivity (k 6) wireless sensor networks.
IEEE/ACM Trans. Netw., 18(3):934{947, June 2010.
[23] Chuanlin Zhang, Xiaole Bai, Jin Teng, Dong Xuan, and Weijia Jia. Constructing
low-connectivity and full-coverage three dimensional sensor networks. IEEE Journal
on Selected Areas in Communications, 28(7):984{993, 2010.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔