| 摘要: | 本論文運用線性規劃提出能夠更精準定位的演算法，並且嘗試硬體的實現。除了主要題目之外，本論文也介紹現今線性規劃(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. |
