應用於單形法之壓縮感知無線定位演算法及硬體設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：34

、訪客IP：3.142.124.119

姓名

吳函蓁(Han-Jhen Wu) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

應用於單形法之壓縮感知無線定位演算法及硬體設計
(Architecture Design of Simplex Algorithm for Range-Free Localization Using Compressive Sensing)

相關論文

★ 具輸出級誤差消除機制之三位階三角積分D類放大器設計	★ 應用於無線感測網路之多模式低複雜度收發機設計
★ 用於數位D類放大器的高效能三角積分調變器設計	★ 交換電容式三角積分D類放大器電路設計
★ 適用於平行處理及排程技術的無衝突定址法演算法之快速傅立葉轉換處理器設計	★ 適用於IEEE 802.11n之4×4多輸入多輸出偵測器設計
★ 應用於無線通訊系統之同質性可組態記憶體式快速傅立葉處理器	★ 3GPP LTE正交分頻多工存取下行傳輸之接收端細胞搜尋與同步的設計與實現
★ 應用於3GPP-LTE下行多天線接收系統高速行駛下之通道追蹤與等化	★ 適用於正交分頻多工系統多輸入多輸出訊號偵測之高吞吐量QR分解設計
★ 應用於室內極高速傳輸無線傳輸系統之設計與評估	★ 適用於3GPP LTE-A之渦輪解碼器硬體設計與實作
★ 下世代數位家庭之千兆級無線通訊系統	★ 協作式通訊於超寬頻通訊系統之設計
★ 適用於3GPP-LTE系統高行車速率基頻接收機之設計	★ 多使用者多輸入輸出前編碼演算法及關鍵組件設計

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

本論文運用線性規劃提出能夠更精準定位的演算法，並且嘗試硬體的實現。除了主要題目之外，本論文也介紹現今線性規劃(Linear Programming)以及無線定位(Wireless Localization)的相關知識，包含了最佳化方法中的單形法(Simplex Method)、內點法(Interior-Point Method)及正交匹配追蹤演算法(Orthogonal Matching Pursuit)，以及無線定位的量測方法及相關演算法。
單形法的步驟為：建立Tableau、找出基變數、找入基變數、轉軸。在模擬環境設定中，網路大小分別為5m×5m, 7.5m×7.5m, 10m×10m，格子點分別為12×12, 18×18, 24×24點。環境網路中會有11個感測器隨機分布在模擬網路的四周來偵測接收訊號強度(Receive Signal Strength)。論文最後會將單形法及內點法的模擬結果以l_1最小化的形式來表示，由於單形法硬體複雜度較低，所以最終選擇單形法為主要演算法。
由於演算法需要利用多層遞迴來做矩陣的計算，誤差會逐層累積，故矩陣中的資料數據經過量化之後需以浮點數的形式儲存在13塊記憶體中，每一筆資料大小為25 bits。多層遞迴的運算量相當龐大，在本論文的硬體架構中平行度會影響硬體複雜度及時脈(Cycle Time) 及在不同運算時對於記憶體的存取，經模擬推算後設定平行度為13以達到時脈及硬體複雜度之間的平衡，最後結果在遞迴一次時總共需要496個時脈來完成。

摘要(英)

In this thesis, the fundamental knowledge about wireless localization is first introduced. The compressed sensing techniques exploiting the signal sparsity can increase the efficiency of data collection and thus are widely investigated. Some linear programming algorithms can be adopted to solve the range-free localization problem from compressive sensing, such as the simplex algorithm, interior-point algorithm, and OMP algorithm.
The steps of the simplex algorithm perform as follows: listing a tableau, finding an entering variable, and pivoting. In our simulation environments, the network sizes are set to 5m×5m, 7.5m×7.5m, 10m×10m with grid sizes 12×12, 18×18, 24×24. Several sensor nodes are spread inside the network close to the boundary to provide the measurements of received signal strengths. From the simulation results, we show that the performance of the simplex algorithm approaches to that of the interior-point algorithm for l_1 optimization. However, the complexity of the former is much less. Consequently, the implementation of the simplex algorithm is considered. Since the simplex algorithm is an iterative algorithm, the error will be easily accumulated. Thus, a floating-point representation with total 25 bits is adopted for the data path. The hardware parallelism will affect the complexity and execution clock cycles. After evaluation, the degree of parallelism is set to 13 to strike a balance between processing time and hardware complexity. As a result, the total execution time are 496 clock cycles for one iteration.

關鍵字(中)

★ 單形法
★ 壓縮感知
★ 無線定位

關鍵字(英)

★ simplex method
★ compressive sensing
★ wireless localization

論文目次

摘要 I
ABSTRACT II
目錄 III
圖示目錄 VI
表格目錄 VIII
第一章緒論 1
1.1 簡介 1
1.2 研究動機及目的 1
1.3 論文架構 3
第二章無線定位原理及演算法 4
2.1 無線定位量測方法 4
2.2 接收信號強度( RECEIVE SIGNAL STRENGTH, RSS )量測方法 6
2.3 插入權重演算法(WEIGHTED INTERPOLATION , WIP)[3] 7
第三章應用於無線定位之壓縮感知與最佳化方法 12
3.1 傳統取樣過程介紹[7] 13
3.2 壓縮感知介紹[8] 14
3.3 單形法( SIMPLEX METHOD ) 15
3.3.1 單形法代數表格( Tableau )求解 16
3.3.2 單形法求解演算法 17
3.4 內點法( INTERIOR-POINT METHOD ) 20
3.4.1 仿射比例主演算法( Primal Affine Scaling Algorithm ) 22
3.4.2 兩階段法求起始可行內點 23
3.4.3 Karmarkar 投影演算法 24
3.5 正交匹配追蹤演算法(ORTHOGONAL MATCHING PURSUIT, OMP)[15] 27
第四章使用單形法之壓縮感知無線定位演算法 28
4.1 最佳化方法之單形法標準形 28
4.2 壓縮感知訊號處理 29
4.3 應用單形法之壓縮感知無線定位演算法 30
4.4 系統環境設定 31
4.4.1 感測器分佈範圍(Range)模擬結果及比較 32
4.4.2 感測網路分布型態(Realization)影響結果穩定與否及比較 36
4.4.3 Threshold影響內點法結果穩定與否及比較 40
4.5 系統模擬與比較 42
第五章硬體架構設計與實現 44
5.1 硬體設計流程 44
5.1.1 硬體複雜度評估 47
5.1.2 量化及參數之決定 48
5.1.3 記憶體擺放位置與Tableau設計 50
5.2硬體區塊圖及資料流 52
5.2.1硬體區塊圖 52
5.2.2 資料流 54
5.3預處理區塊硬體及資料流 54
5.3.1 Flip-Sign 區塊 55
5.3.2 Row Operation 區塊 59
5.4 單形法定位區塊硬體及資料流 62
5.4.2 CORDIC 除法器區塊 64
5.4.3 轉軸(Pivoting)區塊 65
5.5 硬體實現結果 68
第六章結論 71
參考文獻 72

參考文獻

[1] N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero, R. L. Moses and N. S. Correal, "Locating the nodes: cooperative localization in wireless sensor networks," in IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 54-69, July 2005.
[2] Waltenegus Dargie, Christian Poellabauer, “Fundamentals of Wireless Sensor Networks Theory and Practice”, 1st Edition, Wiley, 2010
[3] C. L. Wang, Y. W. Hong and Y. S. Dai, "A Decentralized Positioning Method for Wireless Sensor Networks Based on Weighted Interpolation," 2007 IEEE International Conference on Communications, Glasgow, 2007, pp. 3167-3172.
[4] C. H. Wang, 2012, Design and Implementation of Localization and Tracking in Wireless Sensor Network, Department of Electrical Engineering, National Central University, Taoyuan, Taiwan.
[5] 翁偉泰, (2011). 數學規劃（一）Mathematical Programming (I). [.pdf] http://wtwengkm.iem.mcut.edu.tw/xms/index.php?courseID=21
[6] R. Fourer, (2005). III. Solving Linear Programs by Interior-Point Methods. [.pdf]. http://www.4er.org/CourseNotes/
[7] C. E. Shannon, "Communication In The Presence Of Noise," Proceedings of the IEEE, vol. 86, no. 2, pp. 447-457, Feb. 1998.
[8] E. J. Candes and M. B. Wakin, "An Introduction To Compressive Sampling," IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 21-30, March 2008.
[9] L. Carin, D. Liu and B. Guo, "Coherence, Compressive Sensing, and Random Sensor Arrays," in IEEE Antennas and Propagation Magazine, vol. 53, no. 4, pp. 28-39, Aug. 2011.
[10] Zouxy09, (2012). 壓缩感知（Compressive Sensing）學習之（二）, http://blog.csdn.net/zouxy09/article/details/8118329
[11] C. Feng, S. Valaee and Z. Tan, "Multiple Target Localization Using Compressive Sensing," IEEE Global Telecommunications Conference, 2009. GLOBECOM 2009. Honolulu, HI, 2009, pp. 1-6.
[12] S. S. Chen , D. L. Donoho and M. A. Saunders, "Atomic decomposition by basis pursuit", SIAM Rev., vol. 43, no. 1, pp. 129-159, 2001
[13] R. Andraka, "A Survey of CORDIC Algorithms for FPGA-Based Computers," Proc. Sixth ACM/SIGDA Int′,l Symp. Field Programmable Gate Array (FPGA ′,98), pp. 191-200, Feb. 1998.
[14] S. Pongyupinpanich, F. A. Samman, M. Glesner and S. Singhaniyom, "Design and evaluation of a floating-point division operator based on CORDIC algorithm," Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), 2012 9th International Conference on, Phetchaburi, 2012, pp. 1-4.
[15] J. Wang, S. Kwon, and B. Shim, “Generalized orthogonal matching pursuit,”IEEE Transactions on Signal Processing, Vol. 60, pp. 6202-6216, Dec. 2012.

指導教授

蔡佩芸(Pei-Yun Tsai)

審核日期

2016-8-30

推文