- 學位論文
無線感測網路的中繼節點佈置與節點定位問題之研究
The Study of Relay Node Placement and Localization Problems in Wireless Sensor Networks
摘要
在本論文中，我們提出了一個可以在線性時間內求解的近似演算法來解決最小幾何圓盤覆蓋問題，這個演算法可以應用解決在無線感測網路的中繼節點布置問題，在歐基里德平面上給定一個集合P中包含n個點，最小幾何圓盤覆蓋問題就是找出一組最少個數的圓盤來覆蓋平面上所有點，最佳解是可以求得但是為NP完全問題，我們提出了一種線性時間內可以解決的近似演算法，這種近似法在正六邊形網格中找尋最少圓盤覆蓋，近四法所找到的圓盤個數與最佳解的比值最多為(5+ϵ)倍(0<ϵ≤15)，在我們的實驗中證明，最差倍數的情況很少出現，平均得到的數值大都小於1.7倍的最佳解。另外我們也在論文中提出，如果在正六邊形網格中，至多不超過於七倍的最佳解近似演算法，這個方法在實驗中平均值也會低於兩倍的最佳解個數，並且針對中繼節點的聯通性，做出額外布置中繼節點的方法，維持整體網路的互聯特性。 對於解決無線感測網路中定位的問題，我們提出了使用兩個錨節點利用無線感測網路本身的多重彈跳特性，來計算未知節點本身的相對位置，這個方式是相當低成本而且容易執行的，不需要使用額外的設備像是GPS或者超音波接收器，兩個已知位置的錨節點放於左下角的X與右下角的Y，利用多重彈跳泛播的方式，不同的彈跳數可以形成一個一個的區塊，透過運算可以得到相對位置所在，並且針對邊緣的節點可以進行二次泛播，達到更精準的定位，在實驗中誤差值是半徑的0.25倍，這個方法優於眾所周知的DV-Hop方法相當多，而且DV-Hop需要使用較多的已知節點、封包通訊成本也較高，因此我們的方法具有相當的優勢。
並列摘要
In the thesis, we propose a linear time approximation algorithm for the minimum geometric disk cover (MGDC) problem in wireless sensor networks (WSNs). The proposed algorithm can be applied to the relay node placement problem of wireless sensor networks. Given a set P with n points in the Euclidean plane, the MGDC problem is to identify the smallest set of congruent disks with prescribed radius r that covers all points in P. It is known that the MGDC problem is NP-complete. A novel linear time approximation algorithm for the MGDC problem is proposed, which identifies covering disks using the regular hexagon tessellation of the plane. The approximation ratio of the proposed algorithm is (5+ϵ), where 0<ϵ≤15. Experiment results show that the worst case is rare, and on average, the proposed algorithm uses less than 1.7 times the optimal disks of the MGDC problem. Suppose in a WSN, the deployed relay nodes are homogeneous, and their communication ranges are circles with radius r, the WSN relay node placement problem can be resolved by first solving the MGDC problem and placing the relay nodes at the centers of the covering disks, and then, if necessary, deploying additional relay nodes to meet the connection requirement of relay nodes. For the case that needs to promptly deploy the relay nodes, this study provides a fast 7-approximation algorithm which uses on average less than twice the optimal number of relay nodes in the experiments. For the localization problem of the WSNs, we presents a low-cost yet effective scheme which uses only two anchor nodes and uses bilateration to estimate the coordinates of unknown nodes. Many localization algorithms of WSNs require the installation of extra components, such as a GPS, ultrasonic transceiver, and unidirectional antenna. The proposed localization scheme is range-free (i.e., not demanding any extra devices for the sensors). In this scheme, two anchor nodes are installed at the bottom-left corner (Sink X) and the bottom-right corner (Sink Y) of a square monitored region of the WSN. Sensors are identified with the same minimum hop counts pair to Sink X and Sink Y to form a zone, and the estimated location of each unknown sensor is adjusted according to its relative position in the zone. This study compares the proposed scheme with the well-known DV-Hop method. Simulation results show that the proposed scheme outperforms the DV-Hop method in localization accuracy, communication cost, and computational complexity.
參考文獻
延伸閱讀
- Chen, Y. W. (2014). 多跳中繼網路中繼站佈建與路由之研究 [master's thesis, National Formosa University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0028-2101201412395600
- Lin, S. Y. (2008). 無線感應網路下之感應節點定位機制演算法 [master's thesis, Yuan Ze University]. Airiti Library. https://doi.org/10.6838/YZU.2008.00209
- Chang, Y. Y. (2010). 無線人體區域感測網路之中繼節點佈建方法 [master's thesis, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2010.00611
- 莫志弘（2010）。A Heterogeneous Relay Placement Strategy for Energy-balancing in Wireless Sensor Networks〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2010.00228
- 王偉凱（2009）。The Study of Coverage Problem in Wireless Sensor Networks〔碩士論文，朝陽科技大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0078-1111200915521992