臺灣博碩士論文加值系統

　　無線網狀網路可視為一個用來提供寬頻存取網際網路之「最後一哩」技術的解決之道。於無線網狀網路中採用多個信道來傳輸，已經被證實是一種用來克服容量因干擾而降低之問題的有效方法。對於每個使用者而言，希望選擇低干擾且傳輸延遲最低的路徑去存取網際網路；然而，這對整個系統而言並不是最佳化的結果。
　　在這篇論文中，我們提供了一個簡單的信道分配演算法，不但容易實施而且使得每個節點能有局部的最大化平行傳輸。我們也提供一個分散式具有服務品質限制的路由演算法，將系統觀點與使用者觀點都納入考量；為了達到這個目標，我們定義一個路由衡量標準，這個路由衡量標準是由鏈結平均傳輸延遲與佇列長度之導數兩者所組成，並且由拉格蘭日鬆弛法為基礎的問題公式所推導出來。
　　我們使用鏈路狀態路由協定來作動態路由，並且提供多條最短路徑與多條最快路徑給每一個起終點配對，使這個演算法能藉由流量控制啟發式演算法而適用於更多情況之下。最後，我們透過模擬來評估近似最佳化之分散式具服務品質限制路由演算法。模擬結果顯示我們的演算法在較大的網路下於平均端對端傳輸延遲、延遲時間變化與符合服務品質限制之系統吞吐量上優於其他演算法。

　　Wireless mesh networks (WMNs) are considered as a solution to providing last-mile broadband Internet access. Employing multiple channels into WMN is shown to be an efficient way to conquer the degradation of capacity due to the interferences. For each user, it is desirable to choose the route with low interference and minimum delay to access the Internet; however, this is suboptimal for the whole system.
　　In this thesis, we propose a simple channel assignment heuristic algorithm which is easy for implementation and makes each node have locally maximal parallel transmission. We also propose a distributed QoS (Quality-of-Service) constrained routing algorithm which takes “system perspective” and “user perspective” into consideration; to achieve the goal, we define a routing metric which is composed of link mean delay and the derivative of queue length, and is derived from a Lagrangean Relaxation based problem formulation.
　　We use link-state routing protocol for distributed routing and provide both K shortest paths and K fastest paths for each Origin-Destination pair, so that, this algorithm can be suitable for much more scenarios by the admission control heuristic algorithm we proposed. Finally, we evaluate the performance of Near-Optimal Distributed QoS Constrained (NODQC) routing algorithm via simulations. The simulation results show that our routing algorithm outperforms others in terms of average end-to-end delay, delay jitter and system throughput with QoS satisfaction in large-scale networks.

謝誌.......................................................I
論文摘要.................................................III
THESIS ABSTRACT............................................V
TABLE OF CONTENTS........................................VII
LIST OF TABLES............................................IX
LIST OF FIGURES...........................................XI
CHAPTER 1 INTRODUCTION.....................................1
1.1 BACKGROUND.......................................1
1.2 MOTIVATION.......................................3
1.3 LITERATURE SURVEY................................5
1.3.1 Multichannel Wireless Mesh Networks..............5
1.3.2 Routing Algorithm Issues.........................7
1.4 PROPOSED APPROACH................................9
1.5 THESIS ORGANIZATION.............................10
CHAPTER 2 PROBLEM FORMULATION OF MULTICHANNEL WMNS.......11
2.1 PROBLEM DESCRIPTION.............................11
2.2 NOTATION........................................14
2.3 PROBLEM FORMULATION.............................16
CHAPTER 3 SOLUTION APPROACH..............................19
3.1 CHANNEL ASSIGNMENT HEURISTIC....................19
3.2 SOLUTION APPROACH FOR MULTICHANNEL WMNS FORMULATION..............................................25
3.2.1 Introduction of Lagrangean Relaxation Method....25
3.2.2 Lagrangean Relaxation...........................28
3.2.3 The Dual Problem and the Subgradient Method.....34
3.2.4 Getting Primal Feasible Solutions...............35
CHAPTER 4 DISTRIBUTED ROUTING ALGORITHM..................37
4.1 ROUTING METRIC..................................37
4.2 ESTIMATION OF ROUTING METRIC PARAMETERS.........40
4.3 DISTRIBUTED ROUTING PROTOCOL....................42
4.4 ADMISSION CONTROL HEURISTIC ALGORITHM...........45
CHAPTER 5 SIMULATION.....................................49
5.1 SIMULATION ENVIRONMENT..........................49
5.2 SIMULATION RESULTS AND DISCUSSION...............53
5.2.1 SIMULATION RESULTS..............................53
5.2.2 DISCUSSION OF SIMULATION RESULTS................58
CHAPTER 6 CONCLUSION.....................................61
6.1 SUMMARY.........................................61
6.2 FUTURE WORK.....................................63
REFERENCES...............................................65
簡　歷...................................................69

[1] T. Liu and W. Liao, “On Routing in Multichannel Wireless Mesh Networks: Challenges and Solutions,” IEEE Network, Vol. 22, NO. 1, pp. 13-18, January/February 2008.
[2] L. Badia, A. Erta, L. Lenzini, and M. Zorzi, “A General Interference-Aware Framework for Joint Routing and Link Scheduling in Wireless Mesh Networks,” IEEE Network, Vol. 22, NO. 1, pp. 32-38, January/February 2008.
[3] A. Raniwala, K. Gopalan, and T.-C. Chiueh, "Centralized Channel Assignment and Routing Algorithms for Multi-channel Wireless Mesh Networks," ACM Mobile Computing and Communications Review (MC2R), Vol. 8, NO. 2, pp. 50–65, April 2004.
[4] P. Kyasanur and N. H. Vaidya, “Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks,” Proc. IEEE WCNC, Vol. 4, pp. 2051- 2056, 2005.
[5] A.P. Subramanian, H. Gupta, S.R. Das, “Minimum Interference Channel Assignment in Multi-Radio Wireless Mesh Networks,” Proc. IEEE SECON, pp. 481-490, 2007.
[6] R. Draves, J. Padhye, and B. Zill, “Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks,” Proc. ACM MOBICOM, pp. 114-128, 2004.
[7] T. Liu and W. Liao, “Capacity-Aware Routing in Multi-Channel Multi-Rate Wireless Mesh Networks,” Proc. IEEE ICC, Vol. 5, pp. 1971-1976, 2006.
[8] Y.C. Tzeng, “Backhaul Assignment and Routing Algorithm with End-to-End QoS Constraints in Wireless Mesh Networks,” Department of Information Management, National Taiwan University, July 2006.
[9] H.T. Cheng and W. Zhuang, “Joint Power-Frequency-Time Resource Allocation in Clustered Wireless Mesh Networks,” IEEE Network, Vol. 22, NO. 1, pp. 45-51, January/February 2008.
[10] M. Alicherry, R. Bhatia, and L. Li, “Joint Channel Assignment and Routing for Throughput Optimization in Multi-Radio Wireless Mesh Networks,” Proc. ACM MOBICOM, pp. 58-72, 2005.
[11] J. Tang, G. Xue and W. Zhang, “Interference-Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks,” Proc. ACM MOBIHOC, pp. 68-77, 2005.
[12] D. Bertsekas and R.G. Gallager, Data Networks, 2nd ed., Upper Saddle River, NJ, Prentice Hall, 1992.
[13] A.S. Tanenbaum, Computer Networks, 4th ed., Upper Saddle River, NJ, Prentice Hall, 2003.
[14] B.A. Forouzan, Data Communication and Networking, 3rd ed., New York, McGraw Hill, 2003.
[15] H.H. Yen and F.Y.S. Lin, “Near-Optimal Delay Constrained Routing in Virtual Circuit Networks,” Proc. IEEE INFOCOM, Vol. 2, pp. 750-756, 2001.
[16] L. Kleinrock, Queueing Systems, Vol. 2, New York, Wiley-Interscience, 1976.
[17] Y.F. Wen, “Performance Optimization Algorithm for Wireless Networks,” Department of Information Management, National Taiwan University, July 2007.
[18] R.G. Gallager, “A Minimum Delay Routing Algorithm Using Distributed Computation,” IEEE Transactions on Communications, Vol. 25, NO. 1, pp. 73-85, January 1977.
[19] C.G. Cassandras, M.V. Abidi, and D. Towsley, “Distributed Routing with On-Line Marginal Delay Estimation,” IEEE Transactions on Communications, Vol. 38, NO. 3, pp. 348-359, March 1990.
[20] A.M. Geoffrion, “Lagrangean Relaxation and its Use in Integer Programming,” Mathematical Programming Study 2, Vol. 2, pp. 82-114, January 1974.
[21] M.L. Fisher, “An Application Oriented Guide to Lagrangean Relaxation,” Interfaces, Vol. 15, NO. 2, pp. 10-21, April 1985.
[22] K.T. Cheng and F.Y.S. Lin, "Minimax End-to-end Delay Routing and Capacity Assignment for Virtual Circuit Networks," Proc. IEEE GLOBECOM’95, pp. 2134-2138, 1995.
[23] M.L. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problems,” Management Science, Vol. 27, NO. 1, pp. 10-21, January 1981.
[24] N. Katoh, T. Ibaraki, and H. Mine, "An Efficient Algorithm for K Shortest Simple Paths," Networks, Vol. 12, NO. 4, pp. 411-427, October 1982.
[25] E. Hadjiconstantinou and N. Christofides, “An Efficient Implementation of an Algorithm for Finding K Shortest Simple Paths,” Networks, Vol. 34, NO. 2, pp. 88-101, August 1999.