臺灣博碩士論文加值系統

　　在這篇論文中，我們考慮在具備多閘道多點跳躍式無線骨幹網路中傳輸資源使用的效率問題以及在閘道分支節點間負載平衡的問題。在具有多個閘道器的無線骨幹網路中，節點如果以傳統最短路徑演算法下去選擇連結的閘道會容易因為轉傳節點壅塞的關係使得某些節點須要走比較長的路徑才能到的了閘道器，相對的整體網路節點需要幫忙轉傳的資料就變得比較多，解決這問題比較直覺的方法是讓請求比較大資源的節點先連結到比較近的閘道器位置上，然而這樣可能會造成一些請求量略小一點的節點須要走更長的路徑，使得網路上節點因為幫忙轉傳資料而所消耗的資源會更多。
　　因此在本篇論文中我們針對了中控式模型的網路架構提出了一個比較有效的閘道選擇方式，根據節點到各閘道的跳躍數及節點本身發出的詢問大小計算出節點對於各閘道的權重值，再根據這個權重值優先選擇出欲建立路徑的閘道與節點，直到所有的節點都被選完。
　　另外，在閘道分支節點的負載平衡上面我們也提出了一個啟發式演算法，利用兩步驟的篩選過程選出要先建立路徑的節點和閘道。在模擬方面，我們使用c++模擬節點選擇閘道的過程，結果顯示我們的方法在相同拓樸傳送相同請求可以只消耗更少傳輸資源，另外在閘道分支節點的負載平衡方面我們跟建立平衡樹的演算法相比也可以得到更趨近1的平衡係數。

　　In this paper, we consider the two problems that are transmission resource consumption and load-balancing in gateway's branches in wireless backhaul with multiple gateways and multiple hops. In wireless backhaul network with multiple gateways, if a node select associated gateway by shortest-path algorithm may make some node become congestion will make some nodes need to pass through more hops than before. So the total consumption of transmission resource will become more. May be we can make the node which has biggest request associate the shortest gateway first, however this method may let those nodes have slightly quest compare with biggest may need to pass through more TAPs. It will cause more resource consumption in network.
Therefore, in this paper we proposed a useful gateway selection method in central mode network model. Using the distance values between the node and each gateway and the node's request, we can calculate a weighted value corresponding to each gateway. Using this weighted value we can select the node and the corresponding gateway than build the path between those until there is no node can be selected.
　　Beside, we proposed another heuristic algorithm to against the problem of load-balancing. Our step have two, in first step we select the branch that load is Lightest and consider the set those have routing path to reach the branch has Lightest load.in this set ,we select the node have minimal hop between form the gateway, finally we build the routing path between those.in simulation, we use c++ to simulate the process of gateway selection, result shows our algorithm can receive better performance compared with shortest algorithm in transmission resource consumption problem and load-balancing problem.

第一章 介紹………………………………………………………………………………………………1
1.1 背景 …………………………………………………………………………………………………1
1.2 動機……………………………………………………………………………………………………3
1.3 目的……………………………………………………………………………………………………5
1.4 研究內容……………………………………………………………………………………………5
第二章 相關研究………………………………………………………………………………………6
2.1 閘道選擇……………………………………………………………………………………………6
2.1.1負載平衡 ……………………………………………………………………………6
2.1.2資源利用度……………………………………………………………………………………7
2.2 路由選擇……………………………………………………………………………………………8
第三章 系統模型與問題定義………………………………………………………………10
3.1 系統模型…………………………………………………………………………………………10
3.2 問題定義…………………………………………………………………………………………10
3.2.1.1傳輸資源成本最佳化……………………………………………………………10
3.2.1.2 NP-complete 證明………………………………………………………12
3.2.2.1閘道負載平衡………………………………………………………………………14
3.2.2.2NP-complete 證明…………………………………………………………15
第四章LESC與TSLBR演算法…………………………………………………………………17
4.1 LESC演算法……………………………………………………………………………………17
4.2 TSLBR演算法…………………………………………………………………………………24
第五章 效能模擬………………………………………………………………………………………27
第六章 結論………………………………………………………………………………………………46
參考文獻………………………………………………………………………………………………………47

[1] G. Narlikar, G. Wilfong, and L. Zhang, "Designing multihop wireless backhaul networks with delay guarantees,” In Proc. of IEEE INFOCOM, 2006.
[2] V. Gambiroza, B. Sadeghi, and E.W. Knightly, "End-to-end performance and fairness in multihop wireless backhaul networks," In Proc. of ACM MOBICOM 2004
[3]Karrer R, Sabharwal A, KnightlyEW. "Enabling large-scalewireless broadband: the case for TAPs.” ACM Computer Communication Review 2004; 34(1): 27–32.
[4] J. Lee and Y. Hsu, "Fairness in Multi-hop Wireless Backhaul Networks: A Dynamic Estimation Approach, " In Proc. of ICST Qshine 2008
[5] J. Jun and Sichitiu, M.L., "Fairness and QoS in multihop wireless networks," In Proc. of IEEE VTC 2003
[6] Karrer R, Sabharwal A, KnightlyEW. Enabling large-scalewireless broadband: the case for TAPs. ACM Computer Communication Review 2004; 34(1): 27–32.
[7] Frank Y. S. Lin and Y. F. Wen “Fair inter-TAP routing and backhaul assignment for wireless mesh networks" In Wirel. Commun. Mob. Comput 2008
[8] Usman Ashraf ,Slim Abdellatif ,Guy Juanole, "Gateway selection in backbone wireless mesh networks", Proceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference
[9]Tada, K. Yamamoto, M. "Load-Balancing Gateway Selection Method in Multi-Hop Wireless Networks" Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE
[10] Ancillotti, Emilio ; Bruno, Raffaele ; Conti, Marco, "Load-balanced routing and gateway selection in wireless mesh networks: Design, implementation and experimentation " World of Wireless Mobile and Multimedia Networks (WoWMoM), 2010 IEEE
[11] Usman Ashraf ,Slim Abdellatif ,Guy Juanole, "Gateway selection in backbone wireless mesh networks", Proceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference
[12] Hsiao PH, Hwang A, Kung HT, Vlah D. "Load-balancing routing for Wireless Access Networks". In Proceedings of IEEE INFOCOM 2001; 986–995.
[13] B. Aoun, R. Boutaba, Youssef Iraqi, G. Kenward, "Gateway placement optimization for load balancing in wireless mesh networks",CSCWD IEEE 2009
[14] Deepti Nandiraju, Lakshmi Santhanam, Nagesh Nandiraju, and Dharma P. Agrawal, "Achieving Load Balancing in Wireless Mesh Networks Through Multiple Gateways ".c2006 IEEE
[15]V. Mhatre, F. Baccelli, H. Lundgren, and C. Diot, “Joint MAC-aware routing and load balancing in mesh networks,” in Proc. ACM CoNEXT’07, December 10–13 2007, pp. 1–12.
[16] M. Genetzakis and V. Siris, “A Contention-Aware Routing Metric for Multi-Rate Multi-Radio Mesh Networks,” in Proc. IEEE SECON’08, June 16–20, 2008, pp. 242–250.