碎形幾何應用於無線感測網路之研究

The Study of Fractal Geometry in Wireless Sensor Networks

謝政達

無線感測網路 ； 碎形幾何 ； 摩爾曲線 ； 移動錨節點 ； Wireless Sensor Network ； Fractal Geometry ； Node-Gosper Curve ； Moore Curve ； Mobile Sink

義守大學資訊工程學系學位論文

2016年

碩士

陳啟彰

繁體中文

近年來有越來越多的研究專注於碎形幾何，碎形幾何是一門研究非整數維度圖形的學科，所有的碎形圖形都有一種巢狀或遞迴結構。研究發現世界上看似雜亂無規則的曲線，其實都是亂中有序，科學家已經發現有其規律可循。 本論文嘗試將碎形幾何的這種巢狀或遞迴結構特性應用於無線感測網路；我們選定Node-Gosper和Moore這兩種填充曲線作為我們的研究目標。 Node-Gosper Curve是一個以點取代(node-replacement)為基礎，碎形維度為二的曲線，其一階圖形由七個基本線段所組成，當其階層越來越大時可填充一個類似六角形的區域。我們讓移動錨節點沿著此曲線行走，可以依照感測區域與傳輸範圍等參數調整Node-Gosper Curve的階層數並保證可以拜訪整個感測區域中的所有感測器，進一步的幫助感測器自我定位、收集資料等。 眾多的空間填充曲線都有無法自我迴路的共通點，也就是起點與終點相距甚遠，這會造成移動錨節點需要花費額外的路徑從終點走回起點，然而摩爾曲線(Moore curve)就具有自我迴路的特性，其起點與終點是幾乎在同一位置上，本論文採用摩爾曲線應用於移動錨節點的路徑規劃上，讓移動錨節點依此路徑重複的走遍整個感測區域，並且沿著此路徑停留於每個正方形叢集的中心點收集感測到事件發生的節點之資訊。在本論文中，我們以實驗證明摩爾曲線的自我迴路特性，無論在傳輸延遲、能源消耗、成功接收率上都優於其他相似類型的繞境曲線。

There are a growing number of studies focused on the fractal geometry in recent years. Fractal geometry is a disciplinary research of non-integer dimension graphics, and all of them have a kind of nesting or recursive structure. Previous studies found that curves with seemingly messy irregularity in the world are actually chaos with order. Scientists have found that there are rules to produce them. This paper attempts to use the characteristics of nesting or recursive structure of fractal geometry to the routing paths of wireless sensor networks (WSNs). We selected two space filling curves, Node-Gosper Curve and Moore curve, as the goal of our study. Node-Gosper Curve is based on node-replacement curve and its fractal dimension is two. The order one of Node-Gosper Curve consists of seven segments, and when its order grows, it can fill a similar hexagonal area. To be a routing path of a mobile sink in a WSN, we can adjust the order of Node-Gosper Curve in accordance with the transmission range, size of sensing area, parameters, etc. It ensures that all sensors can be visited in the sensing area, and thus helps sensor’s self-localization, collecting and transmitting information, etc. Most of the space-filling curves have no self-loop. Thus, the distance between the start point and the end point is very large, which causes a mobile beacon node needs to spend extra path from the end point returning to the start point. However, Moore curve have the self-loop characteristic, its start point and the end point are very close. In this thesis, Moore curve was applied to the mobile beacon path planning in which the mobile beacon follows the path to travel entire sensing area and stops at the center of each square cluster to collected information from the nodes with sensing events. With the self-loop characteristic of Moore curve, we expected the Moore curve can more quickly get to each sensor to collect information than other space-filling curves, and therefore the Moore curve can reduce sensor’s transmission delay.

1. [4]王聖博, “無線感測網路的節點定位問題之研究—使用移動錨節點”, 義守大學資訊工程學系碩士論文, 2015.
   連結：
2. [9]Bahi, J. M., A. Makhoul and A. Mostefaoui, “A Mobile Beacon Based Approach for Sensor Network Localization,” Wireless and Mobile Computing, Networking and Communications, 2007, WiMOB 2007, Third IEEE International Conference on.
   連結：
3. [10]Jacques M. Bahi, Abdallah Makhoul and Ahmed Mostefaoui, “Hilbert mobile beacon for localisation and coverage in sensor networks,” International Journal of Systems Science, Vol. 39, Iss, 11, 2008.
   連結：
4. [11]C.-C. Chen and T.-C. Lin, “A Low-Cost Anchor Placement Strategy for Range-Free Localization Problems in Wireless Sensor Networks,” International Journal of Distributed Sensor Networks, vol. 2013, pp. 1-12, 2013.
   連結：
5. [12]梁進鴻, “無線感測網路的錨感測器資料收集之研究”, 義守大學資訊工程學系碩士論文, 2015.
   連結：
6. [16]Ioannis Chatzigiannakis, Athanasios Kinalis and Sotiris Nikoletseas, “Efficient data propagation strategies in wireless sensor networks using a single mobile sink,” Journal Computer Communications archive, Volume 31 Issue 5,March, 2008 Pages 896-914.
   連結：
7. [17]Zeydin PALA, “Effects of Mica2-based discrete energy levels on the lifetime of cooperation neighbor sensor networks,” Turkish Journal ofElectrical Engineering & Computer Sciences, 2016.
   連結：
8. [19]María Gabriela Calle Torres, “ENERGY CONSUMPTION IN WIRELESS SENSOR NETWORKS USING GSP,” Master's Thesis, UNIVERSITY OF PITTSBURGH SCHOOL OF INFORMATION SCIENCES, 2006.
   連結：
9. [1]王友群、胡君琪、曾煜棋, "無線感測網路系統之簡介", 2003, 取自http://people.cs.nctu.edu.tw/~wangyc/publications/reports/r001-maganize03-wsn.pdf ,2015年12月8日
10. [2]蔡佳宏、曾煜棋, “無線感測網路之通訊協定與應用前景”, 國立交通大學資訊工程系電信國際型科技計畫, vol. 1, 2006.
11. [3]J. Ventrella, "Brain-filling Curves - A Fractal Bestiary", 2012, http://www.brainfillingcurves.com, access on 2015/7/7
12. [5]Richard P. Taylor & 陳義裕, "這是藝術，還是混沌", 2003, 取自http://sa.ylib.com/MagCont.aspx?Unit=featurearticles&id=175 ,2015年8月6日
13. [6]張幼青, "碎形知多少", 1989, 取自http://web.phys.ntu.edu.tw/physhistory/spacetime/vol_25/v25_p30.pdf, 2015年8月6日
14. [7]Wikipedia, “Space-filling curve”, 2015, https://en.wikipedia.org/wiki/Space-filling_curve, access on 2016/1/17
15. [8]Wikipedia, “Hilbert curve”, 2015, https://en.wikipedia.org/wiki/Hilbert_curve, access on 2015/12/6
16. [13]C. C. Chen, Y. K. Chang, J. Y. Hung, and J. H. Liang, “Scalable Routing Protocol for Wireless Sensor Networks Based on Gosper Islands,” The Proceedings of International Computer Symposium., pp. 145–154, 2014.
17. [14]Wikipedia, “Moore curve”, 2015, https://en.wikipedia.org/wiki/Moore_curve, accesson 2015/12/6
18. [15]南e網, “等加速度直線運動公式”, 取自http://www.nani.com.tw/nani/jlearn/natu/ability/a2/5_a2_4.htm ,2016年1月18日
19. [18]Feng Zhao and Leonidas J. Guibas, “Wireless Sensor Networks,” Morgan Kaufmann, 2004.