無線網路之效能最佳化演算法

Abstract

無線網路在現今網路中已成為主要傳輸的媒介，更將是未來網路科技的主軸，小 至個人區域網路（如：藍芽網路）、辦公室或家庭區域網路（如：HomeRF）、網狀式 之都會網路（如：網狀式網路）、WiMax、到衛星網路已延伸至任何角落，並且提供人 對人、人對機器、以及機器對機器在任何時間、任何地方存取所需的資訊服務與通訊。 因此，本論文以無線網路作為核心，探討無線區域網路與無線都會網路在效能上所面 臨的相關議題。 本論文之研究範圍主要是依網路架構與網路分層作為依據，依不同的網路結構包 括：熱點網路、網狀式網路、以及隨意網路，而跨層之網路分層包括：應用層、網路 層、媒體存取控制層、以及實體層來探討這些議題，相關文獻探討列述於第1 章，依 此將這些範圍中的網路規劃與效能最佳化作為研究標的，將參數優化以獲取近似最佳 解，依此所執行之議題列述如下： • 在熱點區網方面：[第2 章] 在熱點區網範圍內因距離差距而必須採用不同的傳輸速率，就長期而言，這使得 傳輸速率較快的行動裝置與慢速裝置的產出率是一樣的。經研究後發現在媒體存 取控制層相關參數(i)封包大小、(ii)初始競爭視窗大小、以及(iii)多重封包連續傳 送之組合調整，可達到傳輸時間公平並且提高產出率，依相關數值分析發現以競 爭視窗大小作為優先調整之參數可獲至最大的系統產出率。基於這些參數之組合 iv Wen - Performance Optimization Algorithms for Wireless Networks 無法在短時間內計算出來，所以依公平性具有單峰的特性，提出近似二元搜尋法 找出公平係數低於10-6 之參數組合與系統產出率，在RTS/CTS 模式下解出系統效 能最高可達5.92Mbps，改善幅度為21%。 • 在網狀式網路方面：[第3-4 章] 主要針對空間差異所造成系統效能的降低與個別裝置的不公平性議題，這個部分 可分為(i)最高分枝負載平衡路由與(ii)端點對端點之公平延遲路由兩個主要議 題，此外，(iii)出口匝道設施指派也是本論文研究的議題之一。上述問題均已被證 明為NP-complete 之複雜問題，故本論文將這些議題建立為混合式整數與非線性 規劃，並且採用拉格蘭日法來解對偶問題，以獲得本問題解的下界，並且依此方 法所獲得之啟發結果，在滿足所有限制之下，追求目標式傳輸流量成本最小化。 在議題(i)和(ii)中得到此兩數值之差在5%以內，雖然在議題(i)與議題(iii)結合下， 所得的差距在40%以內，但與現有相關演算法仍有10%的改善幅度。 • 在隨意網路方面：[第5 章] 許多資料傳輸都可以透過廣播與群播方式來傳送訊息，針對此一應用中，如何利 用無線網路傳輸本身之廣播特性，讓一次傳輸即可將訊息傳送給多個裝置以節省 能耗，動態調整訊號長短議題，在此考量以路徑為基礎提出最佳化混合整數之非 線性數學模式。並且依每一路徑所形成的樹狀結構計算每一裝置之訊號半徑，以 此使每一群播訊息送至接收者之所有電力消耗降至最低。此問題已被證明為 NP-complete 之複雜問題。所以，本論文採用拉格蘭日法來解對偶問題，並且由這 個方法所得的提示獲至主要問題之可行解，所得之上界與下界的差在10%以內。 此外，針對裝置移動之議題作進一步討論，在移動方向與速率給定之下，預期每 一時段現有傳輸之群播路徑是否中斷作為路由會期，若網路中斷則重新路由再傳 送剩餘的訊息，直到所需群播的訊息送完為止。同樣的，此議題也已被證明為 NP-complete 之複雜問題，以拉格蘭日法所得之上界與下界差在30%以內。在實驗 部分還包含與現有演算法比較，本論文所提的研究結果比最小路徑樹 (MSPT)、 Prim 的最小擴展樹 (MST)、廣播電力擴增 (BIP) 以及貪婪式擴展廣播樹 (GIBT) 改善幅度在5%以上。 論文摘要 v • 在感測網路方面：[第6-7 章] 基於感測裝置是一次大量部署於某特定區域，更新電力的成本相對比較高。因此， 如何延伸網路運作之壽命是主要關鍵。針對此一問題，本論文依實體層至應用層 之 (i)動態調整訊號長短；(ii)喚醒週期排程；(iii)碰撞避免；(iv)路由；以及(v)資 料集縮等跨層之省電演算法，並且結合多重終節點和群集式架構，提出以整數混 合之非線性規劃模式來探討這個問題，由於這些問題已被證實為NP-complete 之 複雜問題。所以，本論文採用拉格蘭日法作為解題方法，並且提出最佳化排程演 算法和資料集縮路由演算法。這些演算法所計算出來的最低電力消耗值，不僅與 上述所列五種議題相比較，也與其他學者所提演算法包括：貪婪擴充樹 (GIT)、 距核心最近之來源節點 (CNS)、最短路徑樹 (SPT)等，依上述所列的議題進行比 較，比較之後發現所提演算法在省電方面比現有演算法改善幅度在7%-43%之間。 於論文的最後一章中，匯整上述研究的結論，並且說明接續進行的研究議題，這 些議題除了上述之延伸研究之外，也列出寬頻都會網路WiMax 之排程和允入控制議 題。綜合上述，列出相關之後續研究議題如下： • 在網狀式網路與熱點網路方面 在網狀式網路中，縱使以多重通道作為傳輸模式，依然會因訊號過強而造成干擾， 這些干擾將使既有通訊容量縮減，亦即將增加傳輸延遲。所以，在未來延伸研究中 加入干擾議題。 • 在隨意與感測網路方面 延伸感測網路(包括：無線廣播議題、資料集縮與排程路由…等)生命週期於多個會 期連線以平衡電力消耗於所有節點上。 • 在無線寬頻網路方面 分別針對(i)在滿足服務品質下，進行排程與允入參數之優化使允入之新連線最小 化；(ii)在802.16J 下進行網路排程以達到端點對端點延遲最小化。

It is now possible to access data services anywhere, any time, via wireless networks ranging from PWANs (Personal Wireless Area Networks) to office or home area networks, from mesh networks and WiMax to satellite networks. As for the future of network technologies, it is essential that research be directed toward improving person-to-person, person-to-machine, and machine-to-machine communications. Thus, in this dissertation, we focus on wireless networks, as well as the challenges and research avenues presented by network planning and performance. Primarily focusing on network architecture and network layers, the research scope of this dissertation covers various network architectures, such as Wi-Fi hotspots, mesh networks, and ad hoc networks (including sensor networks); and considers various network layers: the application layer, the network layer, media access control (MAC), and the physical layer. Previous related research is discussed in Chapter 1. Both network planning and performance optimization issues are addressed. The following is a brief summary of the presentation of these issues to be addressed in depth in the body of this dissertation: • Wi-Fi hotspots [Chapter 2] In such hotspots, the transmission bit rate for a mobile device (MD) is dependent on its distance from the nearest base-station. A problem arises when fast and slow MDs share Abstract vii a network in that, despite the higher capability of a fast MD, the throughput of that fast MD is the same as that of a slow MD. Therefore, we address this problem and propose an algorithm to achieve channel access time fairness. Our research includes comparative studies of three adaptive MAC parameters: (i) the packet size, (ii) the initial contention window size, and (iii) multiple back-to-back packets. On the basis of that research, we have determined that adjusting the size of the initial contention window provides the most significant optimization of the maximum system throughput. It has been established that determining a global optimal solution is impossible in a reasonable time; therefore, a modified binary search algorithm is implemented to solve the problem. Experiment results show that the system throughput is 5.92 Mbps, which is a 21% improvement over the original MAC protocol. • Mesh networks [Chapter 3-4] In mesh networks, the main issues are the performance and fairness of the system or individual devices due to spatial bias. The issues addressed include: (i) top load-balanced routing; (ii) end-to-end delay fairness; and (iii) backhaul assignment problems, which have proven to be NP-complete. In this dissertation, these problems are formulated as mixed-integer nonlinear programming problems. Lagrangean Relaxation (LR) is used to solve the primal and Lagrangean dual problems, and to obtain upper and lower bounds. Gaps between research issues (i) and (ii) are shown to be less than 5%. Although a larger gap exists between issues (i) and (iii), i.e., 40%, the improvement ratio is still 10% over other modified methods. • Ad hoc networks [Chapter 5] For ad hoc networks, the main concern addressed in this dissertation is the transmission of multicast messages via broadcasting. The advantage of this method is that it obtains the so-called “wireless broadcast advantage”. The same message is sent only once, but it is received by many devices. Based on routing paths, we propose an optimization-based integer- and nonlinear-programming model. The radius of each node is calculated intelligently according to the structure of the broadcast tree, thus minimizing the total power consumption required to broadcast each multicast message to all receivers. This problem has also proven to be NP-complete. We adopt LR methods to solve the problem, and determine the gaps to be within 10%. viii Wen - Performance Optimization Algorithms for Wireless Networks This static network research problem is extended to include mobility issues in mobile networks. The message is broken down into smaller sub-sections. For a mobile node, given the direction and speed, the duration of the current broadcast tree is found. New broadcast trees are constructed to provide coverage to multicast group nodes until the complete message is sent. Like the previous static case, this is also an NP-complete problem. We solve it by LR, which obtains a gap of less than 30%. Our experiment results show that the proposed algorithms outperform the MSPT, Prim MST, BIP, and GIBT heuristics by at least 5%. • Sensor networks [Chapter 6,7] Sensors are typically scattered throughout an area of interest. As they may be located in remote areas, recharging the sensors’ batteries is often infeasible. The network lifetime of a wireless sensor network, which is interrupted when depleted batteries prevent the transmission of environmental information, is dependent on battery capacity and energy consumption efficiency, and has become a crucial issue in sensor network research. Therefore, to prolong network lifetime starting from the physical layer and extending all the way up to the application layer, we focus on: (i) multi-rate routing; (ii) dynamic adjustment of the nodal transmission radius; (iii) duty cycle scheduling; (iv) collision avoidance; (v) routing; and (vi) data aggregation. All combinations of these six issues are considered within multi-sink and cluster-based architectures. These are serial problems, formulated as mixed-integer nonlinear programming problems that have proven to be NP-complete. Thus, the LR approach is used to find solutions to the serial problems. Meanwhile, algorithms, including an O-MAC protocol and a serial DAR (data aggregation routing) algorithm, are proposed to optimize energy consumption. The feasible solution is derived from information provided by the Lagrangean multipliers, and compared with the performance of other heuristics, such as GIT, CNS, or SPT, which are modified to satisfy constraints on the research problem. Our experiment results show that the proposed heuristic outperforms the others approaches by 7%-43%. Conclusions and extensions of the work in this dissertation are presented in the final portion of the dissertation [i.e., Chapter 8], including additional issues that could be addressed in future research, such as scheduling, admission control, and end-to-end delay in Abstract ix IEEE 802.16 broadband wireless area (BWA) networks. Accordingly, these issues are listed as follows: • Mesh networks + Wi-Fi hotspot networks The signal may overshoot, even when the multi-channel is used. As the interference is considered, the transmission error reduces the link capacity C(u,v), so that the traffic flow is limited. In addition, if the interference issue is considered, it increases the number of retransmissions which means increasing the node-to-node delay. Thus, the interference issue is extended as one of our future work. • Ad hoc and sensor networks The proposed maximization of mobile network lifetime may be extended to include balancing the power consumption of all nodes within a multiple session construction. • IEEE 802.16 BWA networks Potential future research in this area includes: (i) optimization of the relative parameters and placing controls on scheduling and admission to minimize delay or maximize performance under quality of service considerations; and (ii) minimization of end-to-end delay with controls on scheduling in the IEEE 802.16j.