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

The Study of Fractal Geometry in Wireless Sensor Networks

謝政達(Zheng-Da Xie)

指導教授 ： 陳啟彰

義守大學/電機資訊學院/資訊工程學系/碩士(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.

並列關鍵字

Wireless Sensor Network ； Fractal Geometry ； Node-Gosper Curve ； Moore Curve ； Mobile Sink

參考文獻

[4]王聖博, “無線感測網路的節點定位問題之研究—使用移動錨節點”, 義守大學資訊工程學系碩士論文, 2015.

[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.

[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.

[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.

[12]梁進鴻, “無線感測網路的錨感測器資料收集之研究”, 義守大學資訊工程學系碩士論文, 2015.